2018-05-27

EM算法原理与推导

EM算法

Jensen不等式

对于凸函数，有$E[f(X)]\ge f(E[X])$。如果$f$是一个严格凸函数，那么只有当$X=E[x]$成立的时候，Jensen不等式中的等号才会满足。

向上图演示的一样，如果函数是严格凸函数，那么想要满足Jensen不等式的话，只能是$X$是一个定值，从而$X=E[x]$。如果$X$可能以某分布取多个值的话，任意两个函数值之间的连线都会大于这一区间内的函数值，就好像将一个木棍放入碗里，木棍和碗之间一定存在空隙。而为什么要求函数值严格凸的，我们可以这样考虑，假设碗内有一块平面，那么木棍如果落入该区间，就会和该碗的平面完全贴合。

对应的，如果$f$是严格凹函数，那么Jensen不等式就是$E[f(X)]\le f(E[X])$，这也是我们要处理的情况，因为我们要用Jensen不等式求解对数似然的极大值。

2018-05-24

机器学习

高斯判别模型（GDA）原理与推导

GDA原理

Gaussian Discriminant Analysis模型的理论十分简单，这里写这篇文章实际上是为后面GMM和EM算法做铺垫。另外，这篇文章是第一篇加上generative标签的文章，指的是生成式模型，因此也会在这里重点说明一下生成式和判别式的区别。

Generative 与 Discriminative

判别式模型对条件概率$$$P(Y|X)$$$建模，不关注数据分布，重点关注类间的分类超平面，SVM就是典型的判别式模型，在PGM中典型的就是CRF，这点特别容易弄错，尽管CRF是无向概率图模型，属于马尔科夫网络，对无向边给定联合概率分布，但是求解计算计算概率的时候通过除以归一化因子得到条件概率，这里先说这么多，后面会有文章详细总结。还有神经网络也是判别式，现在的神经网络就是利用强大的高维拟合能力得到分类面。而生成式模型则是对数据与标签的联合概率进行建模，然后来了新的数据之后，根据贝叶斯公式，利用类别先验概率和给定数据后的似然进行分类，典型的模型包括，NaiveBayes，HMM，还有这里介绍的GDA，以及后面介绍的GMM。

2018-05-21

程序员的玩具

锋利的Bash(4):三剑客(相识)

一道残阳铺水中，半江瑟瑟半江红。

Bash

环境变量与自定义变量

env查看环境变量，set查看所有变量。两者的区别关键在于是否会被子进程所继续引用，可以使用export将自定义变量转化为环境变量。可以把这两个理解为global变量和local变量。这里注意子进程与父进程的关系。

declare和typeset用于声明变量，在iie工作记录中的脚本中我用到了bash数组，BashNote(3)中也用详细的总结，这里说说declare的另外几个功能。-i声明整形变量，-x等价于export的功能，导出环境变量，-r将变量设置为只读。

使用source或者小数点直接读取配置文件不需要注销再登录。

自定义变量的设置，参考BashNote(1)

历史命令

history是一个很简单的命令。!!执行上一条命令。HISTSIZE环境变量设置保存多少条历史，默认历史命令在注销后保存至~/.bash_history。

bash配置文件

/etc/profile所有用户都会执行。
/etc/profile.d/*.sh最好自定义的内容在这里面修改，只要用户具有读权限，该文件就会被调用。
~/.bash_profile个人配置文件，如果该文件不存在就回去读取.bash_login，如果还不存在就读取~/.profile。

2018-05-09

程序员的玩具

锋利的Bash(2)

数组

参考：

初级一点的bash数组教程
高级一点的15 个 Bash Array 数组教程

我这里就总结几点我觉得主要注意的地方:

数组特点
数组下标从0开始，支持负数索引，使用[*]或[@]将数组转化为字符串列表（这两个是存在区别的，后面说)，否则只是通过$符号只能拿到下标为0的元素。计算长度时，被删除（unset）的元素不计入长度

declare -a array
array[0]='a'
array[1]='bb'
array[2]='ccc'
echo ${#array[*]} : ${array[*]}
echo first element : $array
unset array[0]
echo ${#array[*]} : ${array[*]}
echo first element : $array
echo last element : ${array[-1]}

2018-05-07

大数据

基数估计：FM算法

LogLog算法

参考《大数据——互联网大规模数据挖掘与分布式处理一书》中所提到的FM算法，下面给出简单的python实现。

代码中比较重要的就是testFM函数。重要的参数是each_group_k，表示了LogLog中用后多少位表示桶号，然后对所有元素求平均进行估计。group_num是参考《大数据》书上提到的中位数方法的小改进，就是不只是使用平均进行估计，而是使用不同的哈希函数LogLog算法重复多遍，然后每个LogLog算法内求平均，多个LogLog算法内求中位数。
结果改进的并不多，索性直接用一组LogLog，hashmap设置的大一些来得直接。

另一个需要说明的地方就是代码返回的最后乘了一个magic number0.79402。这个的原因是值求平均的化得到的是有偏估计，需要使用这个数修正偏差得到无偏估计，这个数怎么得到的还是去看原论文吧……我是没看。