Machine Learning笔记(7)

K-means算法

过程：略
收敛：定义代价函数
$J(c, \mu) = \sum_{i=1}^m {\lVert x^{(i)} - \mu_{c^{(i)}}\rVert}^2$
K-means可以看作对代价函数坐标下降,理论上可能在多个J相同的点上震荡,实践中很少发生,J是非凸函数,算法不能保证收敛到全局最优点

混合高斯模型

$p(x^i, z^i) = p(x^i \mid z^i)p(z^i)$
$z^i \sim Multinomial(\phi)$ where $\sum_{j=1}^k \phi_j = 1 \; \phi_j \ge 0$
$p(z^i = j) = \phi_j
x^i \mid z^i = j \sim N(\mu_j, \Sigma_j)$
其中 $z^i$是隐变量,表示 $x^i$所属的类/高斯分布,那么数据的最大似然函数是:
$l(\phi, \mu, \Sigma) = \sum_{i=1}^m{\log p(x^i;\phi, \mu, \Sigma)} \\ = \sum_{i=1}^m{\log\sum_{z^i = 1}^k p(x^i \mid z^i; \mu, \Sigma)p(z^i;\phi)}$
然鹅MLE并没有闭式解,如果 $z^i$是已知,那么可以写最大似然函数为:
$l(\phi, \mu, \Sigma) = \sum_{i=1}^m \log p(x^i, z^i; \phi, \mu, \Sigma) \\ = \sum_{i=1}^m \log p(x^i \mid z^i, \mu, \Sigma) + \log p(z^i; \phi)$
分别求对参数偏导为0得:
$\phi_j = \frac{1}{m} \sum_{i=1}^m 1\{z^i = j\} \\ \mu_j = \frac{\sum_{i=1}^m 1\{z^i = j\}x^i}{\sum_{i=1}^m 1\{z^i = j\}} \\ \Sigma_j = \frac{\sum_{i=1}^m 1\{z^i = j\}(x^i - \mu_j)(x^i - \mu_j)^T}{\sum_{i=1}^m 1\{z^i = j\}}$
此时相当于高斯判别分析模型
因此EM算法E步猜测 $z^i$,M步根据猜测的 $z^i$更新模型的其他参数。

• E-step:
  $w_j^i := p(z^i = j\mid x^i;\phi,\mu,\Sigma) = \frac{p(x^i \mid z^i = j; \mu,\Sigma)p(z^i = j;\phi)}{\sum_{l=1}^k{p(x^i \mid z^i = l; \mu,\Sigma)p(z^i = l;\phi)}}$
  是对 $x^i$的软分类
• M-step:
  $\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 := \frac{\sum_{i=1}^m w_j^i(x^i - \mu_j)(x^i - \mu_j)^T}{\sum_{i=1}^m w_j^i}$
  迭代直到收敛

• Previous
  Machine Learning笔记(6)
• Next
  Machine Learning笔记(8)