开楼庆典~[em23]
其实，更自然的方法是先使用无监督的学习，在使用监督的学习，但是一般课程设置的顺序却是相反的。
一.k均值聚类：一个序列收敛应用的例子
1.这种聚类方法一般被用在生物蛋白质的分类和市场调查方面。Google新闻用分类就用这个算法。对图片像素进行分类。
\[输入一组无标记的数据集\{x^{(1)},x^{(2)},\cdots,x^{(m)}\}算法步骤：\]
\[\begin{alignat}{1}&1.初始化聚类重心\mu_1,\mu_2,\cdots,\mu_k \in \mathcal{R^{n}}\\&2.重复步骤1直到算法收敛:\\&(1)令c^{(i)}=\arg \underset{j}{min}\|x^{(i)}-\mu_j\|,j=1,2,\cdots,k\\&(2)\mu_j:=\frac{\sum_{i=1}^{m}1\{c_i=j\}\cdot x_i}{\sum_{i=1}^{m}1\{c_i=j\}}\end{alignat}\]
—>给定k个中心依然是十分强的假设。
\[关于算法的收敛性，定义失真函数：J(c,\mu)=\frac{1}{2}\sum_{i=1}^{m}\|x^{(i)}-\mu_{c_i}\|^2\]
—>启示我们可以利用序列收敛准则定义很多很多种算法，因为计算机的强项在于重复的运算，对于很多的目标情况可以定义
很多序列去计算逼近，这就算法分析的核心了啊。
—>怎样的算法能得到全局最优解怎样的算法只能得到局部最优解。

二.用观测服从高斯分布的EM算法做密度估计
可用来检测异常，比如飞机引擎(发热，振动)，再比如信用卡消费记录。先定义一个联合分布：
\[有一个隐藏的随机变量z,以及x^{(i)},z^{(i)}一个联合分布:P(x^{(i)},z^{(i)})=P(x^{(i)}|z^{(i)})P(z^{(i)}),\\其中z^{(i)}服从多项分布：\sum_{j}^{}\Phi_j=1,\quad x^{(i)}服从正态分布：\mathcal{N}(\mu_j,\Sigma_j)\]
对联合分布进行最大似然估计[协方差阵]：
\[l(\Phi,\mu,\Sigma)=\sum_{i=1}^{m}\log p(x^{(i)},z^{(i)};\Phi,\mu,\Sigma)\]
\[\begin{alignat}{1}&\Phi_j=\frac{\sum_{i=1}^{m}1\{z^{(i)}=j\}}{m}\quad\mu_j=\frac{\sum_{i=1}^{m}1\{z^{(i)}=j\}x^{(i)}}{\sum_{i=1}^{m}1\{z^{(i)}=j\}}\end{alignat}\]
最大化期望参数估计方法EM算法(bootstrap procedure)：重复E步和M步
\[\begin{alignat}{1}E:&对z^{(i)}的值进行猜测，令\omega_{j}^{i}:=P(z^{(i)}=j|x^{(i)},\Phi,\mu,\Sigma)=\frac{P(x^{(i)}|z^{(i)}=j)P(z^{(i)}=j)}{\sum_{l=1}^{}P(x^{(i)}|z^{(i)}=l)P(z^{(i)}=l)}\end{alignat}\]
\[\begin{alignat}{1}M:&\Phi_j:=\frac{1}{m}\sum_{i=1}^{m}\omega_j^{(i)}\quad u_j=\frac{\sum_{i=1}^{m}\omega_j^{(i)}x^{(i)}}{\sum_{i=1}^{m}\omega_j^{(i)}}\quad \Sigma_i=\frac{\sum_{i=1}^{m}\omega_j^{(i)}(x^{(i)}-\mu_j)(x^{(i)}-\mu_j)^T}{\sum_{i=1}^{m}\omega_j^{(i)}}\end{alignat}\]
—>协方差的估计为什么是这样的？

三. 利用Jensen不等式实现缺少目标观测时的最大似然参数估计：EM算法
\[\begin{alignat}{1}Jensen不等式:&f是凸函数,f''(x)\ge 0,设X是随机变量,那么恒有f(E(x))\ge E(f(x)),如果还有f'(x)\ge 0,\\&f(x)是严格凸函数,此时f(E(x))=E(f(x))等价于E(x)=x.\\&如果f是凹函数\end{alignat}\]
\[\begin{alignat}{1}&1.建立概率模型P(x,z;\theta),能观测到变量x,目标是:\underset{\theta}{\max} l(\theta)=\sum_{i=1}^{m}\log P(x^{(i)};\theta)=\sum_{i=1}^{m}\log \sum_{z^{(i)}}^{}P(x^{(i)},z^{(i)};\theta)\\&2.引入非观测随机变量的分布Q_i(z^{(i)}),需要做好z^{(i)}的引入需要满足\sum_{z^{(i)}}^{}Q_i(z^{(i)})=1\end{alignat}\]
\[\begin{alignat}{1}此时令l(\theta)变成一个构造随机变量期望的函数l(\theta)=&\sum_{i=1}^{m}\log \sum_{z^{(i)}}^{}Q_i(z^{(i)})\frac{P(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\\=&\sum_{i=1}^{m}\log \underset{z^{(i)}\sim Q_i}{E}\left(\frac{P(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\right)\\若构造函数是凹函数,利用Jensen不等式\ge & \sum_{i=1}^{m} \underset{z^{(i)}\sim Q_i}{E} \log \left(\frac{P(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\right) \\构造z^{(i)}的分布使构造函数为常数和等式成立=&\sum_{i=1}^{m} \underset{z^{(i)}\sim Q_i}{E} \log \left(\frac{P(x^{(i)},z^{(i)};\theta)}{\frac{P(x^{(i)},z^{(i)};\theta)}{\sum_{i=1}^{m}P(x^{(i)},z^{(i)};\theta)}}\right)\\会看到构造出条件概率=&\sum_{i=1}^{m} \underset{z^{(i)}\sim Q_i}{E} \log \left(\frac{P(x^{(i)},z^{(i)};\theta)}{\frac{P(x^{(i)},z^{(i)};\theta)}{P(x^{(i)};\theta)}} \right)\\=&\sum_{i=1}^{m} \underset{z^{(i)}\sim Q_i}{E} \log \left(\frac{P(x^{(i)},z^{(i)};\theta)}{P(z^{(i)}|x^{(i)};\theta)}\right) \end{alignat}\]
\[\begin{alignat}{1}3.写成两步骤EM算法——&E:令Q_i(z^{(i)})=P(z^{(i)},z^{(i)};\theta)\\&M: \underset{\theta}{\arg \max}\sum_{i=1}^{m}\log \sum_{z^{(i)}}^{}Q_i(z^{(i)})\frac{P(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\end{alignat}\]
—>并非所有的构造函数都是凹的，可以构造很怪的函数在对数里面！构造的合理性尚不知！！十二分值得探究。为什么M步直接写最开始的似然函数构造呢？EM的步调都是怎样控制的？
—>直接对似然函数求导求极值的方法行不通，找不到解析解。

四.混合高斯模型是一般EM算法的特例
另一角度看EM算法[更多思考,感觉不是很明了]：\[\begin{alignat}{1}&目标函数:J(\theta,Q)=\underset{\theta}{\arg \max}\sum_{i=1}^{m}\log \sum_{z^{(i)}}^{}Q_i(z^{(i)})\frac{P(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \quad 约束条件:l(\theta) \ge J(\theta,Q)\\ &E步就是最大化Q的过程,M步就是最大化\theta的过程。引入的协变量起到如此作用。每步都使得J(Q,\theta)单调上升。\end{alignat}\]
从新角度出发，考虑隐藏随机变量服从mutinomial，条件观测服从混合高斯分布时，假设同样有那些观测样本，我们使用EM算法要做具体的参数估计时，将他们的密度函数带入一般EM算法估计结果。

文本聚类的例子：
\[\begin{alignat}{1}&给定m个训练文本样本{x^{(1)},x^{(2)},...,x^{(m)}},x^{(i)}\in \{0,1\}^n,{x_j}^{(i)}=1\{单词j是否出现在样本i中\}\\&z^{(i)}\in {1,0}是隐藏随机变量\end{alignat}\]


五.用来降维的主成分分析
\[\begin{alignat}{1}&高斯分布随机向量X=\binom{X_1}{X_2},X \sim N(\mu, \Sigma)=N\left (\begin{bmatrix}\mu_1\\ \mu_2\end{bmatrix},\begin{bmatrix}\Sigma_{11}&\Sigma_{12}\\\Sigma_{21}&\Sigma_{22}\end{bmatrix}\right )\\&性质1:X的边际分布X_1~N(\mu_1,\Sigma_{11}),X_2\sim N(\mu_2,\Sigma_{22})\\&性质2：条件分布P(X_1|X_2),X_1|X_2 \sim N(\mu_{1|2},\Sigma_{1|2})=N\left( \mu_1+\Sigma_{12}{\Sigma_{22}}^{-1}(X_1-\mu_2),\Sigma_{11}-\Sigma_{12}{\Sigma_{22}}^{-1}\Sigma_{21}\right)\end{alignat}\]
\[\begin{alignat}{1}问题：&无标签的训练集{x^{(1)},x^{(2)},x^{(3)},\cdots,x^{(m)}},x^{(i)}\in R^n,对概率P(x)建模，\\&假设x=u+\Lambda z+\epsilon,其中,u \in R^n ,z \in R^d ,z~N(0,I),\epsilon \in R^n ,\epsilon\sim N(0,\Phi),\Phi是对角矩阵，\Lambda \in R^{n*d}\\ &\binom{z}{\lambda} \sim N(u_{xz},\Sigma) , \binom{z}{\lambda} \sim N \left( \binom{0}{mu}, \begin{bmatrix}I & \lambda^T\\ \lambda & \lambda^T \lambda +\Phi \end{bmatrix}\right)\\&\prod_{i=1}^m P(x^{(i)},\Lambda \mu \Phi)=\prod_{i=1}^m \frac{1}{(2 \pi)^{m\2}|\Lambda^T \Lambda +\Phi|}\exp(-\frac{1}{2}(x-\mu)^T(\Lambda^T \Lambda + \Phi)^{-1}(x-\mu))\end{alignat}\]
\[&算法流程\\&E-Step:Find Q_i(z_i)=P(z_i|x_i,\theta)\\&M-Step:\arg \underset{\theta}{\max} \sum_{i}^{} \int_{z^{(i)}}^{} Q_i(z^{(i)}) \log \frac{P(x^{(i)}),z^{(i),\theta}}{Q_i(z^{(i)})} \d z^{(i)}\]
——>将x映射到u+\Lambda z使用二维高斯分布