cs229_part6
part 6
接下来就是无监督学习算法了。
k均值聚类
问题背景
样本集描述:
\[
x\in D, x\in R^n
\]
之前的有监督学习问题中,所有的x都有对应的y。但是如果我们的x没有对应的y。但是我们还是希望对x进行分类那应该如何做呢。
迭代过程
最简单的想法就是圈地。对每个类别圈一定的样本。即类似于构造一个星团的过程,我们希望星团有一个中心,属于这个星团的星星离这个星团越近越好。不属于这个星团的星星离这个中心越远越好。但是这个中心的选取也是未知的,于是我们给出一个迭代算法:
- 任意选取k个聚类中心\(\mu_k\)
- 计算样本的类型\[c ^ { ( i ) } : = \arg \min _ { j } \| x ^ { ( i ) } - \mu _ { j } \| | ^ { 2}\]
- 重新计算各个聚类中心 \[\mu _ { j } : = \frac { \sum _ { i = 1} ^ { m } 1\left\{ c ^ { ( i ) } = j \right\} x ^ { ( i ) } } { \sum _ { i = 1} ^ { m } 1\left\{ c ^ { ( i ) } = j \right\} }\]
- 回到2直到收敛,即聚类中心重新计算变得不大时
迭代过程如下图所示
这里收敛性的证明请翻阅讲义。
EM算法
问题背景
再讲EM之前先回顾一下之前我们求分布参数用的最大似然。比如一个班级分为男生和女生,我们假设男生和女生的身高服从正态分布。那么正态分布的参数就可以用最大似然法来求解。但是如果把男生和女生混起来,我们怎么求这个分布呢。或者我们说我们手上有一个班级的身高数据,但是不知道是男生还是女生的。我们想要对其分别求出男生和女生的身高的正态分布参数。
迭代过程
那么直观理解EM算法的话,EM算法就是一个存在隐变量的最大似然法。所谓的隐变量就是对于x我们所不知道的那个类别y。于是EM算法做的事情其实就是两步:
- 拿出一个人的身高数据,先猜测它到底是男是女
- 根据猜测的结果求分布的参数
公式化描述的话就是这么个过程:
这是我们最初求参数用的对数似然:
\[
\theta ^ { * } = \arg \max _ { \theta } \ln P ( X | \theta )
\]
因为存在隐变量z:
\[
\theta ^ { * }= \arg \max _ { \theta } \ln\sum _ { z } P ( X ,z | \theta )
\]
对数似然即:
\[
\left.\begin{aligned} L ( \theta ) & = \ln P ( X | \theta ) \\ & = \ln \sum _ { z } P ( X ,z | \theta ) \end{aligned} \right.
\]
因为z不好求,稍微做一下处理:
\[
L(\theta)= \ln \sum _ { z } P ( X ,z | \theta ) \frac { Q ( z ) } { Q ( z ) }
\]
利用log函数凹函数的性质和琴声不等式得到下界:
\[
L(\theta)\geq \sum _ { z } Q ( z ) \ln \frac { P ( X ,z | \theta ) } { Q ( z ) }
\]
那么我们EM算法就是:
- E步。先似然最大化求z的分布Q(z):\[Q _ { n } ( z ) = \arg \max _ { \mathcal { Q } ( z ) } \sum _ { z } Q ( z ) \ln \frac { P \left( X ,z | \theta _ { n } \right) } { Q ( z ) }\] 利用拉格朗日算子可以得到,详细推导请翻阅参考:\[\Rightarrow Q _ { n } ( z ) = P \left( z | X ,\theta _ { n } \right)\] 这样我们就得到了隐变量的估计。
- M步。既然我们已经得到了类别,再最大似然一次\[\left.\begin{aligned} \theta ^ { n + 1} & = \arg \max _ { \theta } l ( \theta ) \\ & = \arg \max _ { \theta } \sum _ { z } P \left( z | X ,\theta ^ { n } \right) \ln \frac { P ( X ,z | \theta ) } { P \left( z | X ,\theta ^ { n } \right) } \\ & = \arg \max _ { \theta } \sum _ { z } P \left( z | X ,\theta ^ { n } \right) \ln P ( X ,z | \theta ) ) \\ & = \arg \max _ { \theta } E _ { z | X ,\theta ^ { n } } ( \ln P ( X ,z | \theta ) ) \end{aligned} \right.\] 这样就得到了其他参数的估计。
高斯混合模型
问题背景
之前生成式的分类算法里面讲到了高斯辨别分析。我们构造了一个高斯分布去拟合不同的类别。那么这个高斯混合模型也是差不多的。只是多了一个隐变量z,这个z又可以通过EM算法来进行求解。
迭代过程
和高斯判别分析一样我们的对数似然是:
\[
\ell ( \phi ,\mu ,\Sigma ) = \sum _ { i = 1} ^ { m } \log p \left( x ^ { ( i ) } ; \phi ,\mu ,\Sigma \right)
\]
注意y的分布是一个多项式分布而不是伯努利分布,然后引入隐变量z:
\[
\ell ( \phi ,\mu ,\Sigma ) = \sum _ { i = 1} ^ { m } \log \sum _ { z ^ { ( i ) } = 1} p \left( x ^ { ( i ) } | z ^ { ( i ) } ; \mu ,\Sigma \right) p \left( z ^ { ( i ) } ; \phi \right)
\]
假设我们知道z的分布,那么似然函数可以化简成:
\[
\ell ( \phi ,\mu ,\Sigma ) = \sum _ { i = 1} ^ { m } \log p \left( x ^ { ( i ) } | z ^ { ( i ) } ; \mu ,\Sigma \right) + \log p \left( z ^ { ( i ) } ; \phi \right)
\]
对参数分别求导就得到了
\[
\phi _ { j } = \frac { 1} { m } \sum _ { i = 1} ^ { m } 1\left\{ z ^ { ( i ) } = j \right\}
\]
\[
\mu _ { j } = \frac { \sum _ { i = 1} ^ { m } 1\left\{ z ^ { ( i ) } = j \right\} x ^ { ( i ) } } { \sum _ { i = 1} ^ { m } 1\left\{ z ^ { ( i ) } = j \right\} }
\]
\[
\Sigma _ { j } = \frac { \sum _ { i = 1} ^ { m } 1\left\{ z ^ { ( i ) } = j \right\} \left( x ^ { ( i ) } - \mu _ { j } \right) \left( x ^ { ( i ) } - \mu _ { j } \right) ^ { T } } { \sum _ { i = 1} ^ { m } 1\left\{ z ^ { ( i ) } = j \right\} }
\]
到目前为止。我们的求解过程还是和之前的高斯判别分析一样。但是这里有一个问题就是实际上隐类别z是不知道的。所以我们可以用E步进行估计。
EM算法如下:
- E步估计类别\[w _ { j } ^ { ( \text{i} ) } : = p \left( Z ^ { ( i ) } = j | x ^ { ( i ) } ; \Phi ,\mu ,\Sigma \right)\]利用贝叶斯可以得到\[p \left( z ^ { ( i ) } = j | x ^ { ( i ) } ; \phi ,\mu ,\Sigma \right) = \frac { p \left( x ^ { ( i ) } | z ^ { ( i ) } = j ; \mu ,\Sigma \right) p \left( z ^ { ( i ) } = j ; \phi \right) } { \sum _ { l = 1} ^ { k } p \left( x ^ { ( i ) } | z ^ { ( i ) } = l ; \mu ,\Sigma \right) p \left( z ^ { ( i ) } = l ; \phi \right) }\]
- M步更新参数\[\phi _ { j } : = \frac { 1} { m } \sum _ { i = 1} ^ { m } w _ { j } ^ { ( i ) }\] \[\mu _ { j } : = \frac { \sum _ { i = 1} ^ { m } w _ { j } ^ { ( i ) } x ^ { ( i ) } } { \sum _ { i = 1} ^ { m } w _ { j } ^ { ( i ) } }\] \[\Sigma _ { j } \quad = \frac { \sum _ { i = 1} ^ { m } w _ { j } ^ { ( i ) } \left( x ^ { ( i ) } - \mu _ { j } \right) \left( x ^ { ( i ) } - \mu _ { j } \right) ^ { T } } { \sum _ { i = 1} ^ { m } w _ { j } ^ { ( i ) } }\]
参考
最新文章
- python 数据类型 ---字符串
- 3-EM的安装和使用
- 记录一则RMAN备份策略修正案例
- 2016 Web开发资源工具大搜罗
- Linux的用户及用户组
- iOS Developer:真机测试
- poj2485&;&;poj2395 kruskal
- word-wrap:break-word和word-break:break-all的小小比较
- Java的Reference感觉很象C++的指针,但是区别是本质的
- C#语句及案例
- Java中的递归原理分析
- uboot官方FTP下载地址
- 如何创建一个自定义jQuery插件
- css.day01.eg
- Broker节点
- Java课程设计 ————五子棋 (个人博客)
- BASH 学习笔记小结
- python---内置函数,匿名函数,嵌套函数,高阶函数,序列化
- 将地图定位封装为ng指令
- Pfsense2.34中文版
热门文章
- 【loj10064】黑暗城堡
- A.出题人的RP值
- 关于 ie8不兼容的一些方法
- 牛客网Java刷题知识点之什么是JSP、JSP有哪些优点、JSP的9大内置对象、JSP的四大域对象、JSP的四种范围
- mybatis(错误) 项目启动时报“Result Maps collection already contains value forxxx”的解决方案
- [转+补]Android打包so后魅族5中安装运行崩溃问题的解决方法
- /etc/default/useradd
- Yii2.0数据格式器
- Web中打印的各种方案参考
- CPP-网络/通信:WebService