系列教程4,主要是几个classical的机器学习算法。

参考的资源有:
吴恩达机器学习课程笔记(需要的可以留下邮箱)
Udacity 机器学习工程师
以及文中各种blog链接

梯度下降算法

讲的很好的一个
深入浅出–梯度下降法及其实现

随机梯度和batch梯度的区别:随机梯度更新一个数据,有时不易收敛,收敛结果波动。而batch一次需要样本多,耗时,尽管收敛效果更好。

极大似然估计

深入浅出最大似然估计

最大似然估计是利用已知的样本的结果,在使用某个模型的基础上,反推最有可能导致这样结果的模型参数值。

当这个正态分布的期望为多少时,产生这个采样数据的概率为最大?

Linear Regression

简单来说就是用 y=ax+b 去拟合得到最好的a和b。怎么得到最好的a,b呢?用cost function 去寻找这个最佳的参数。
cost function 公式:mean quare error.

然后求这个cost function 的梯度值,下降到最小的梯度值时,那么就得到了最佳参数。

公式推导,西瓜书
这里注意。在推导过程中,很容易遇到矩阵不是满秩矩阵的情况,这个时候需要加上正则化项,L1,L2。具体参考note

Logistic Regression

事实上,逻辑回归是一个分类算法,之所以这样弄,是因为逻辑回顾应用了线性回归类似的方法,只是增加了一个sigmod层。
事实上,logical regression是仅含有一个神经元的单层的神经网络。

因为加入sigmod函数,使得结果在0~1之间,把它当成概率,$\phi (z)$ 可以视为类1的后验估计,所以可以写成:
$$P(y=1\mid x;w) = \phi(w^{T}x+b)=\phi(z)$$
$$P(y=0\mid x;w) =1- \phi(z)$$

一般形式: $$P(y\mid x;w)=\phi(z)^y(1-\phi(z))^{(1-y)}$$

极大似然:$$L(w)=\prod_{i=1}^{n}p(y^{i}\mid x^{i};w)=\phi(z)^y(1-\phi(z))^{(1-y)}$$

然后log取导数,sigmod函数有一个很好的性质$$\phi{(z)}=\phi(z)(1-\phi(z))$$

求导具体过程参考以下。最后得出更新公式。

参考:逻辑回归(logistic regression)的本质——极大似然估计
逻辑回归L1与L2正则,L1稀疏,L2全局最优(凸函数梯度下降)

Softmax regression其实是多维的Logistic regression,它其实可以看做是单层多个神经元的神经网络!

参考:逻辑回归和神经网络之间有什么关系?

Naive Bayes

知道先验概率,知道条件概率,然后根据贝叶斯公式,知道后验概率是多少。多用于分类。全概率公式展开 $$[p(y=c_{k}|x)=\frac{\prod_{i=1}^{M}p(x^{i}|y=c_{k})p(y=c_{k})}{\sum_{k}p(y=c_{k})\prod_{i=1}^{M}p(x^{i}|y=c_{k})}]$$

例子:朴素贝叶斯算法之过滤垃圾邮件
非常好多解释资源,可以帮助你理解贝叶斯,及文本分类。

有三个延申的贝叶斯:
[G]aussian Naive Bayes Classifie](https://chrisalbon.com/machine_learning/naive_bayes/gaussian_naive_bayes_classifier/), 条件概率的部分变成是高斯分布PDF分布形式。

Multinomial Naive Bayes Classifier,当我们数据是离散的数据时,用这个

Bernoulli Naive Bayes Classifier The Bernoulli naive Bayes classifier assumes that all our features are binary such that they take only two values (e.g. a nominal categorical feature that has been one-hot encoded).

Decision Tree

一堆数据给你,你怎么分类呢。计算这堆数据的entropy(熵),计算公式是这样的:$$[entropy = - \sum_{i=1}^{n} p_i log_{2} p_i]$$

可从图上看出,画第1条线的时候,我们就计算画什么位置,两边的entropy最小。
然后用 Entropy(前)-Entropy(后)=信息增益。信息增益越大,说明分的越正确。

一个例子:

但是用信息增益的算法(ID3算法),缺点是信息增益偏向取值较多的特征。

C4.5决策树的提出完全是为了解决ID3决策树的一个缺点,当一个属性的可取值数目较多时,那么可能在这个属性对应的可取值下的样本只有一个或者是很少个,那么这个时候它的信息增益是非常高的,这个时候纯度很高,ID3决策树会认为这个属性很适合划分,但是较多取值的属性来进行划分带来的问题是它的泛化能力比较弱,不能够对新样本进行有效的预测。

具体公式查看下面链接。但是C4.5的缺点是偏向取值较少的特征。

还有一个基尼指数,CART算法。Cart提出了根据基尼系数划分,同时,它的树限定为二叉树,更容易解释,还能处理连续值。参见

Further reading:
决策树–信息增益,信息增益比,Geni指数的理解
决策树

Random forests: 用决策树容易overfitting, 几次随机选取几列进行训练,最后voting得到最佳的结果。

SVM

SVM 是为了使分类边界的距离(Margin)最大化, $[M = \frac{2}{\left | x \right |}]$,并且分类的错误率最低。它的loss function 包括两个部分,$classification error + Margin error$. 其中 $margin error = 1/2*||w||^2$。所以这个loss function形式很像是一般的error 加上了一个 L2(Ridge) punishment。两个error是一个tradeoff的过程,想要更好准确率,加大C,如果想要更大的margin,减小C。

$$[min\frac{1}{2}\left | w \right |^{2}+C\sum_{i=1}^{R}\varepsilon_{i} , s.t.,y_{i}(w^{T}x_{i}+b)\geq 1-\varepsilon_{i},\varepsilon_{i}\geq 0]
$$

kernal

在二维的情况下,用一条直线把两边数据分类。如果不可分的时候,通过核函数(Kernel)转换,找到一个超平面(hyper-plane)来分类。

  • polynomial kernal: (x,y) —->(x,y,xy,x^2,y^2)

  • RBF kernal: 移动每一个point到山range, 要想很好的区分出二类,得找到合适mountain weights. 怎么找呢?

    找到之后,把点利用高斯分布 lift 到高维。

    参数$\gamma $,越大越窄;越小越宽:

    <

讲svm比较好的资源如下:
第一版本:Margin方式:支持向量机基础
第二版本:cost function方式:SVM理解与参数选择(kernel和C)
英文版:Understanding Support Vector Machine algorithm from examples (along with code)
SVM参数选择:SVM参数详解

KNN

传统KNN很简单,就是通过欧式距离或者曼哈顿距离,计算要分类点a和周边K个点的距离,然后看这K个点里,最多的数据点属于哪个类别,就把该要分类的点a归到那一类去。最近邻算法原理详解

它还有几个延申:

  • Radius-based Nearest Neighbor classifier, 不是设K值,而是设一个圆周距离,在该圆里,看哪个类别最多。
  • 加权KNN 有时候各个特征对于分类的贡献是不相同的。用$1/d$距离的倒数来做权重,越远的对分类越弱。

为什么K越小,bias越小,variance越大;而K变大,high bias, low variance?

Kmeans 无监督学习

Kmeans是无监督学习聚类算法。

  • 第一步,随机选几个点作为聚类中心C。
  • 第二步,计算数据点跟聚类中心C的距离,离哪个点近就分到哪个类。
  • 第三步,重新计算聚类中心点C,C = 整个簇的平均值。
  • 第四步,重复第二步和第三步,直到没有数据会变化。

Kmeans很简单,但很容易陷入局部最优化,跟初始点的选取很有关系。所以产生了Kmeans++算法。
假如有要分K个类,第一个点跟Kmeans一样也是随机选取,但N+1的点选取确实根据$D(x)$来选取的。
相比Kmeans,Kmeans++多了几步:

  1. 从数据随机选取一个样本作为初始聚类中心$C_1$
  2. 首先计算每个样本与当前已有聚类中心之间的最短距离(即与最近的一个聚类中心的距离),用D(x)表示;接着计算每个样本被选为下一个聚类中心的概率$[\frac{D(x)^2}{\sum_x D(x)^2}]$. 最后,按照轮盘法选出下一个聚类中心。
  3. 重复第2步知道选出K个聚类中心
  4. 然后按照经典的K-means算法的第二步到第四步

参考:K-means与K-means++

各个算法的优缺点

算法的优劣主要看它的误差,一般误差有方差和偏差组成。一个模型越复杂,拟合的越好,偏差会变小,但容易造成过拟合。对小数据,选取的高偏差,低方差的模型比选取高方差,低偏差的模型要好,因为后者会发生过拟合(overfiting)。然而,随着你训练集的增长,模型对于原数据的预测能力就越好,偏差就会降低,此时低偏差/高方差的分类器就会渐渐的表现其优势(因为它们有较低的渐近误差),而高偏差分类器这时已经不足以提供准确的模型了。

Choosing a Machine Learning Classifier

机器学习算法比较

偏差和方差