落园 » ≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记(十)|专注经济视角下的互联网

≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记(十)

一个东西写到10,总会多少有点成就感...只是不知道已经磨掉了多少人的耐心了呢?

此外这节公式密集,大家看着办吧...

-----------笔记开始------------

继续上一讲,先说说EM算法。

MM、EM和GMM

1. MM(混合模型)

(1) 定义:P(x)=\sum_{k=1}^{K}\pi_{k}P_{k}(x),其中\pi_{k}\geq0\sum_{k=1}^{K}\pi_{k}=1,构成一个离散分布。同时有P_{k}(x)\geq0,且\int P_{k}(x)dx=11\leq k\leq K

(2) 隐变量

我们有数据(x,G),同时依据条件概率分布,有P(x,G)=P(G)P(x|G)。记P(G)=\pi_{k},则P(x|G=k)=P_{k}(x),其中1\leq k\leq K

则有P(x)=\sum_{G}P(x,G)=\sum_{G}P(G)P(x|G)=\sum_{k=1}^{K}\pi_{k}P_{k}(x)为x的边际分布。

(3) GMM(正态混合模型)

P_{k}(x)=\frac{1}{\sqrt{2\pi\sigma_{k}^{2}}}\exp\left(-\frac{(x-\mu_{k})^{2}}{2\sigma_{k}^{2}}\right)1\leq k\leq K,我们有P(x)=\sum_{k=1}^{K}\pi_{k}\exp\left(-\frac{(x-\mu_{k})^{2}}{2\sigma_{k}^{2}}\right),且P(x,G=k)=\pi_{k}\exp\left(-\frac{(x-\mu_{k})^{2}}{2\sigma_{k}^{2}}\right)1\leq k\leq K

(4) 对数似然函数和最大似然估计

对数似然函数写为l(\theta)=\sum_{i=1}^{N}\log P(x|\theta)=\sum_{i=1}^{N}\log\sum_{i=1}^{N}P(x_{i},G=k|\theta)=\sum_{i=1}^{N}\log(\sum_{k=1}^{K}P(G=k|\theta)P(x_{k}|G=k,\theta))。则我们要求的就是\theta^{*}=\arg\max_{\theta}l(\theta),其中\theta=\{\{\pi_{k}\},\{\mu_{k}\},\{\sigma_{k}^{2}\}\}

2. EM算法 (expectation maximum,期望最大方法)

(1) 迭代方法: 给定起始值\theta^{(0)},迭代出\theta^{(1)},..,\theta^{(t)},...。那么问题就是,如何在已知\theta^{(t)}的情况下,求\theta^{(t+1)}

(2) E1步:求P(G|x_{i},\theta^{(t)})。函数形式已知,故可以求各种条件概率什么的。所以有:

P(G|x_{i},\theta^{(t)})=\frac{P(x_{i},G=k)}{P(x_{i})}=\frac{\pi_{k}P_{k}(x)}{\sum_{l=1}^{K}\pi_{l}P_{l}(x)}\equiv \gamma_{ik}^{(t)}

E2步:计算\mathcal{L}(\theta|\theta^{(t)})=\sum_{i=1}^{N}\sum_{k=1}^{K}\underbrace{(\log P(x_{i},G=k|\theta))P(G=k|x_{i},\theta^{(t)})}_{expectation},由于函数形式已知,我们可以计算并将\sum移出来,所以换成线性形式。

(3) M步:求\theta^{(t+1)}=\arg\max_{\theta}\mathcal{L}(\theta|\theta^{(t)}),这样就完成了迭代。需要证明的性质是:随着迭代,l越来越大,且收敛。

(4) 定理:l(\theta^{(t+1)})\geq l(\theta^{(t)})

证明:
\begin{eqnarray*}\mathcal{L}(\theta|\theta^{(t)}) & = & \sum_{i=1}^{N}\sum_{k=1}^{K}\log P(x_{i}|\theta))P(G=k|x_{i},\theta^{(t)})+\sum_{i=1}^{N}\sum_{k=1}^{K}\log P(G=k|x_{i},\theta^{(t)})P(G=k|x_{i},\theta^{(t)})\\& = & l(\theta)+\sum_{i=1}^{N}\sum_{k=1}^{K}\log P(G=k|x_{i},\theta^{(t)})P(G=k|x_{i},\theta^{(t)})\\& & -\sum_{i=1}^{N}\sum_{k=1}^{K}\log P(G=k|x_{i},\theta)P(G=k|x_{i},\theta^{(t)})+\sum_{i=1}^{N}\sum_{k=1}^{K}\log P(G=k|x_{i},\theta)P(G=k|x_{i},\theta^{(t)})\\& = & l(\theta)-\sum_{i=1}^{N}H_{i}(\theta^{(t)})-\sum_{k=1}^{K}KL(\theta^{(t)}|\theta)\end{eqnarray*}

其中H_{i}(\theta^{(t)})=-\sum_{k=1}^{K}\log P(G|x_{i},\theta)P(G|x_{i},\theta^{(t)}),且KL(\theta^{(t)}|\theta)\equiv\sum_{k=1}^{K}[\log P(G|x_{i},\theta^{(t)})P(G|x_{i},\theta^{(t)})-\log P(G|x_{i},\theta)P(G|x_{i},\theta^{(t)})]=\sum_{k=1}^{K}\log\frac{P(G|x_{i},\theta^{(t)})}{P(G|x_{i},\theta)}-P(G|x_{i},\theta^{(t)})>0,定义为两分布的KL距离。

所以\mathcal{L}(\theta^{(t+1)}|\theta^{(t)})=l(\theta^{(t+1)})-\sum_{i=1}^{N}H_{i}(\theta^{(t)})-\sum_{k=1}^{K}KL(\theta^{(t)}|\theta^{(t+1)}),且\mathcal{L}(\theta^{(t)}|\theta^{(t)})=l(\theta^{(t)})-\sum_{i=1}^{N}H_{i}(\theta^{(t)})-\underbrace{\sum_{k=1}^{K}KL(\theta^{(t)}|\theta^{(t)})}_{0}。而由M步,\mathcal{L}(\theta^{(t+1)}|\theta^{(t)})-\mathcal{L}(\theta^{(t)}|\theta^{(t)})\geq0,故有l(\theta^{(t+1)})-l(\theta^{(t)})=KL(\theta^{(t)}|\theta^{(t+1)})\geq0

在GMM的情况下,应用EM算法,则有:

(1) E1步:\gamma_{ik}^{(t)}=\frac{\pi_{k}(2\pi\sigma_{k}^{2})^{-1/2}\exp(-(x_{i}-\mu_{k})^{2}/2\sigma^{2})}{\sum_{l=1}^{K}\pi_{l}P_{l}(x)},可以直接计算。

(2) E2步:\mathcal{L}(\theta|\theta^{(t)})=\sum_{i=1}^{N}\sum_{k=1}^{K}\gamma_{ik}^{(t)}[\log\pi_{k}^{(t)}-\frac{1}{2}\log\pi-\frac{1}{2}\log(\sigma_{k}^{2})-\frac{(x-\mu_{k})^{2}}{2\left(\sigma_{k}^{(t)}\right)^{2}}]

(3) M步:注意有约束条件\sum_{k=1}^{K}\pi_{k}=1,所以使用拉格朗日乘子法:

L(\theta)=\mathcal{L}(\theta|\theta^{t})+\lambda(\sum\pi_{k}-1),故有一阶条件:\frac{\partial L}{\partial\pi_{k}}=\sum_{i=1}^{N}\gamma_{ik}^{(t)}\frac{1}{\pi_{k}^{(t)}}+\lambda=0。从而\pi_{k}^{t+1}=\frac{N_{k}^{(t)}}{N},其中N_{k}^{(t)}=\sum_{i=1}^{N}\gamma_{ik}^{(t)}

还有一阶条件:\frac{\partial L}{\partial\mu_{k}}=\sum_{i=1}^{N}-\frac{2(x_{i}-\mu_{k}^{(t)})(-1)}{2\left(\sigma_{k}^{(t)}\right)^{2}}=0,得到\mu_{k}^{(t+1)}=\frac{1}{N_{k}}\sum_{i=1}^{N}x_{i}

最后,\frac{\partial L}{\partial(\sigma_{k}^{2})}=0,有\left(\sigma_{k}^{t+1}\right)^{2}=\frac{1}{N_{k}}\sum_{i=1}^{N}(x_{i}-\mu_{k}^{(t+1)})^{2}

对GMM而言,E步和M步在k=2的时候,求解过程可参见书上。

第七章:模型评估与选择

1. 概念: 我们有数据集D,函数族\mathcal{F}和损失函数\mathcal{L},这样得到最优的f(x)\in\mathcal{F},然后求得\hat{y}=f(x)

(有监督的学习)。之后就是对模型进行评估:\hat{y}的精度如何(使用测试集)?模型的选择就是\mathcal{F}的选择,使得测试误差比较小。

2. 方法:

(1) 数据充分:分成三块,1/2用来训练(train),1/4用来检验(validation),1/4用来测试(test)。其中validation

的概念是,在\sum_{i=1}^{N}\mathcal{L}(y_{i},f(x_{i}))+\lambda J(f)中,加入J函数来考虑函数族的复杂度,以避免过拟合。而validation就是来调正和选择这里的\lambda,再用train和validation重新训练模型。

最后,用test数据集,测试并且评估测试误差。

(2) 数据不充分:一种是cross-validation,分成k(比如5-10)份,极端的就是K=N,ave-win-out;另一种是bootstrap,后续章节详述。


Comments

Leave a Reply

Your email address will not be published. Required fields are marked *