Machine learning note(1)-526互联

注：本笔记不给出完整解释

正规方程

设\(z=\theta^{T}x\)

设损失函数为\(J(\theta)\)，求令\(\frac{\partial J}{\partial \theta}=0\)的\(\theta\)

由此得出最优的\(\theta\)

牛顿迭代

回顾一下梯度下降：\(\theta'=\theta-\alpha*\frac{\partial J}{\partial \theta}\)

另一种方法是牛顿迭代

\(\theta'=\theta-\frac{\frac{\partial J}{\partial \theta}}{\frac{\partial^2 J}{\partial \theta^2}}\)

参数较少的时候相比梯度下降更快，但是参数较多的时候求解\(\frac{\partial^2 J}{\partial \theta^2}\)会很消耗时间。表示\(\frac{\partial^2 J}{\partial \theta^2}\)的矩阵也称为\(Hessian\)矩阵

局部加权回归

设\(x\)为要预测的，然后设\(w_i=e^{\frac{-(x_i-x)^2}{2}}\)，就有\(\widehat{y}=((X^T W X)^{-1}X^T W y)^{T}x\)

\(((X^T W X)^{-1}X^T W y)^{T}\)就是最优的\(\theta\)

上述\(\theta\)使得\(\sum^{m}_{i=1} w_i (y_i-\theta^T x_i)^2\)

GLM

指数族：概率密度可以写成\(P(y,\eta)=b(y)e^{\eta^T T(y)-\alpha(\eta)}\)

其数学特性是让优化变成凸优化问题

\(E(y;\eta)=\frac{\partial \alpha(\eta)}{\partial \eta}\)

\(Var(y;\eta)=\frac{\partial E(y;\eta)}{\partial \eta}\)

\(P(y|x;\theta)\)符合指数族分布的都可以用GLM解决

GLM梯度下降的方式可以表示为\(\theta_j=\theta_j+\alpha(y^{(i)}-h_{\theta}(x^{(i)}))x^{(i)}_{j}\)

根据这个式子我们可以得到一个结论：最优的\(\theta\)是\(x^{(i)}\)的线性组合，后面\(SVM\)的时候会用到

高斯判别分析

首先说一下生成学习算法。生成学习算法预测\(P(x|y)\)，而不是\(P(y|x)\)，然后根据\(P(y|x)=\frac{P(x|y)P(y)}{P(x)}\)求\(P(y|x)\)，\(P(y)\)是某种概率分布，\(P(x)\)是常数

然后我们假设\(P(x|y)\)为多元高斯分布，然后\(P(y)\)为伯努利分布

先考虑\(y=1\)的情况，对\(P(x|y=1)\)进行最大似然估计

设\(\mu_1\)为均值，\(\sum\)为协方差矩阵，可以得到以下：

\(\mu_1=\frac{\sum^{m}_{i=1}[y^{(i)}==0]x^{(i)}}{\sum^{m}_{i=1}[y^{(i)}==0]}\)

\(\sum=\frac{\sum^{m}_{i=1}(x^{(i)}-\mu_{y^{(i)}})(x^{(i)}-\mu_{y^{(i)}})^{T}}{m}\)

将上述值代入\(P(x|y=1)\)即可得到最优的\(P(x|y=1)\)，\(y=0\)的情况同理

\(P(x|y)\)为高斯分布才好用

朴素贝叶斯

同样是生成学习算法

一般情况有\(P(x_1 x_2 ... x_n|y)=\prod^{n}_{i=1}P(x_1 x_2 ... x_i|y)\)

这样子可不好算啊QAQ

然后我们假设\(x_i\)为\(IID\)，于是上式就变成\(P(x_1 x_2 ... x_n|y)=\prod^{n}_{i=1}P(x_i|y)\)

分别预测每一个\(P(x_i|y=j)\)即可，逻辑回归中\(j=0\)或\(1\)

对\(\prod^{m}_{i=1}P(x_i|y)P(y)\)进行最大似然估计，得到以下：

\(\phi_y=\frac{\sum^{m}_{i=1}[y^{(i)}==1]}{m}\)

\(\phi_{j|y=1}=\frac{\sum^{m}_{i=1}[y^{(i)}==1][x^{(i)}==1]}{\sum^{m}_{i=1}[y^{(i)}==1]}\)

\(\phi_{j|y=0}=\frac{\sum^{m}_{i=1}[y^{(i)}==0][x^{(i)}==1]}{\sum^{m}_{i=1}[y^{(i)}==0]}\)

预测的时候\(P(y=1|x)=\frac{P(x|y=1)P(y=1)}{P(x|y=1)P(y=1)+P(x|y=0)P(y=0)}\)

当然上述情况可能出现分母为零的情况，这时需要拉普拉斯平滑

SVM

最大化几何距离，构建最优边界分类器

然后问题变成：

\(min \frac{||w||^2}{2}\)

\(s.t. y^{(i)}(w^Tx^{(i)}+b) \geq 1\)

再根据最优的\(w\)可以用\(x^{(i)}\)线性表示出来（基于此的只是直觉，并非严谨证明），转化为以下问题：

\(max \sum \alpha_i - \frac{1}{2} \sum \sum y^{(i)}y^{(j)} \alpha_i \alpha_j <x^{(i)},x^{(j)}>\)

\(s.t. \alpha_i \geq 0,\sum \alpha_i y^{(i)}=0\)

一般情况下会把\(\alpha_i \geq 0\)条件加强为\(0 \leq \alpha_i \leq C\)

这样，SVM实际上就是一个约束优化问题。

具体实现：

迭代若干次，每次选取两个\(\alpha_i , \alpha_j\),然后根据约束条件\(\sum \alpha_i y^{(i)}=0\),得出\(\alpha_i\)和\(\alpha_j\)的关系，用\(\alpha_i\)表示\(\alpha_j\)，转化为二次函数区间最大值问题。优化目标对\(\alpha_j\)求导，再结合\(\alpha_j\)的范围得出最优的\(\alpha_j\)，同时得出最优的\(\alpha_i\)，然后更新b

如何选择\(\alpha_i , \alpha_j\)？\(\alpha_i\)选择一个不满足\(KKT\)条件的，然后\(\alpha_j\)选择使得\(|E_i-E_j|\)最大的\(j\)，\(E_i=\widehat{y_i}-y_i\)

更加具体的解释见这篇论文