Machine Learning Course Summary

Where it from

这份summary是研一上学期上卿老师的机器学习时候做的总结。考试前几个人成立了个讨论组，借着CSDN上面的一些博文，比如浙大的研究生Rachel Zhang ，并把课件内容做了一个总结，后来，这份资料就不知道哪里去了。记得当时就是按着课件内容，大略做了一个记录，对Machine Learning一直是云里雾里，直到后来，参加了阿里的大数据竞赛，之后又做了一个基于神经网络模型的时间序列数据分析方面的工作，以及一个kaggle的ctr方面的竞赛，才对ML的模型，特征有了一个相对清晰的认识。有一次尹叔准备阿里实习生的面试，还问我要过这一份资料，直到最近，偶然又从移动硬盘里翻了出来，Machine Learning的道路，要继续往前走，而这，仅仅当作对逝去光阴的缅怀。

Text Classification.

分类所需的类别体系预先设定,且长时间不改变。一篇文档分配给不同类别,置信度不同。人类的判断大多依据经验以及直觉,如何让机器像人类一样自己来通过对大量同类文档的观察来自己总结经验,作为今后分类的依据。这便是统计学习方法,亦是机器学习的基本思想。其中需要一批由人工进行了准确分类的文档作为学习的材料,计算机从这些文档重挖掘出一些能够有效分类的规则,这个过程被称为训练,而总结出的规则集合常常被称为分类器。训练完成之后,需要计算机用该分类器对于从来没有见过的文档进行分类时。

进行文本分类时,不光文本中是包含哪些词很重要,这些词出现的次数对分类也很重要。这一前提使得向量模型(俗称的VSM,向量空间模型)成了适合文本分类问题的文档表示模型。在这种模型中,一篇文章被看作特征项集合来看, 利用加权特征项构成向量进行文本表示,利用词频信息对文本特征进行加权。当特征集过大,容易引起过拟合。通过特征提取或特征重构降维。讨论的几种分类算法:朴素贝叶斯、支持向量机、k-NN、线性回归、逻辑回归。

Naive Bayes

关注文档属于某类别的概率。文档属于某个类别的概率等于文档中每个词属于该类别的概率的综合表达式。而每个词属于该类别的概率又在一定程度上可以用这个词在该类别训练文档中的词频信息来粗略估计,使用朴素贝叶斯算法时,在训练阶段的主要任务就是估计这些值。
[P(C_i|D)=\frac{P(D|C_i)P(C_i)}{P(D)}=\frac{P(w_1|C_i)P(w_2|C_i)…P(w_n|C_i)}{P(D)}]
朴素贝叶斯的缺陷:成立的前提条件是各特征条件独立,使用某个特征值在类别中出现的数目来估计P(w_i|C_i),只有在训练样本非常多的情况下结果才会准确。

k-NN Classification

在kNN算法看来,训练样本代表类别的准确信息(基于实例的分类器),而不管样本是使用什么特征表示的。其基本思想是在给定新文档后,计算新文档特征向量和训练文档集中各个文档的向量的相似度,得到K篇与该新文档距离最近最相似的文档,根据这K篇文档所属的类别判定新文档所属的类别,即该算法不存在真正意义上的训练阶段。kNN唯一的也可以说最致命的缺点就是判断一篇新文档的类别时,需要把它与现存的所有训练文档全都比较一遍,计算代价太大。

Supervised Learning && Unsupervised Learning

监督学习:学习过程中使用的样例是由输入/输出对给出时。最典型的监督学习例子就是文本分类问题,训练集是一些已经明确分好了类别文档组成,文档就是输入,对应的类别就是输出。非监督学习:学习过程中使用的样例不包含输入/输出对,学习的任务是理解数据产生的过程。典型的非监督学习例子是聚类,类别的数量,名称,事先全都没有确定,由计算机自己观察样例来总结得出。。

Overfitting && 线性可分

为了得到一致假设而使假设变得过度复杂称为过拟合。想像某种学习算法产生了一个过拟合的分类器,这个分类器能够百分之百的正确分类样本数据,但也就为了能够对样本完全正确的分类,使得它的构造如此精细复杂,规则如此严格,以至于任何与样本数据稍有不同的文档它全都认为不属于这个类别,即扩展性差。如果存在一个超平面能够正确分类训练数据,并且这个程序保证收敛,这种情况称为线形可分。如果这样的超平面不存在,则称数据是线性不可分。过拟合解决办法:减少特征数量,可以选用模型选择法;正则化,即保留所有特征,但降低参数值的影响。

特征提取算法:开方检验与信息增益

在特征提取时,选择相关性较大的量，可以通过开方检验或者计算信息增益
开方检验 (\sum_{i=1}^n\frac{(x_i-E)^2}{E}) ,小于事先设定的阀值,则假设成立,否者,假设不成立。
信息增益,信息熵的定义: (H(X)=-\sum_{i-1}^nP_i\log_2P_i \qquad H(C|X)=\sum_{i=1}^{n}P_iH(C|X=x_i))

单一参数线性回归

考虑用一条过原点的直线去拟合采样点,(Y=W^TX),未知参数w取什么值可以使得拟合最好,这是一个最小二乘法拟合问题。目标是使(\sum(Y_i^*-Y_i)^2) 最小。通过样本观察值去估算最好的W,有MLE和MAP两种方法。通过求偏导可求得最好的W.

多项式拟合

拟合函数：(Y(X,W)=\sum_{j=0}^{M}W_jX^j)
目标函数：(E(W)=0.5\sum_{i=0}^N{y(x_n,w)-t_n}^2)
过拟合：曲线和采样观察点拟合的很好但是却偏离了整体,称为过拟合,即对于多项式, 阶数越大,对采样点拟合越好,但是对噪声越敏感。而我们的终极目标是对于给定的新数据,能够做出精确的预测,应该避免过拟合。随着拟合多项式阶数的增大,训练误差减小,而测试误差先减小,后增大。对于过拟合,若增加训练样本,可以得到缓解。

正则化：最小二乘法与MLE是一致的,采用贝叶斯方法,可以避免过拟合现象,由于有效参数个数可以随着数据集的大小动态调整。从最小二乘法的角度,为了解决过度拟合的问题,我们可以改变优化目标, 加入正则化,限制W的值过大 [E(W)=0.5\sum_{i=0}^N(y(x_n,w)-t_n)^2+0.5\lambda

]

最小二乘法求解,即直接由数学公式求解, (\theta=(X^TX)^{-1}X^TY)

多元线性回归

输入为向量(包含多个特征分量),假如知道加在每个数据点上的噪声的方差,可以由MLE估计W
假定 [Y_i~N(\omega x_i,\delta_i^2)] ，求[\mbox{argmax(MLE)=argmin}\sum_{i=1}^R\frac{(y_i-\omega x_i)^2)}{\delta_i^2}]

逻辑回归

逻辑回归模型,是一个非线性函数,sigmoid函数,可以轻松处理0/1分类问题如果直接应用线性回归来拟合逻辑回归数据,就会形成很多局部最小值。是一个非凸集,而线性回归损失函数是一个凸函数,即最小极值点,即是全局极小点。模型不符。若采用逻辑回归的损失函数,损失函数就能形成一个凸函数。在线性回归中,若使模型选择与测量数据最接近,则其概率积最大,则形成一个极大似然估计,推导即得平方和最小公式;而逻辑回归采用对数形式。

正则化损失函数

线性回归： [J(\theta)=\frac{1}{2m}[\sum_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)})^2+\lambda\sum_{j=1}^{n}\theta_j^2]]
逻辑回归：[J(\theta)=-\frac{1}{m}[\sum{i=1}{m}y^{(i)}\log{h_{\theta}(x^(i))}+(1-y^{(i)})(1-y^{(i)})\log{(1-h_{\theta}(x^{(i)}))}]+\frac{\lambda}{2m}\sum_{j=1}^{m}\theta_j^2]
对损失函数正则化处理,相当于加上一个奥卡姆剃刀,把原本复杂的系数变得简单,解决由于维数增加导致的系数膨胀问题。
正则化,即给参数加惩罚项,当给不需要的参数加大的惩罚项时,为求使得损失函数最小的参数,则惩罚项大的参数将趋于0.从贝叶斯估计的角度来看,正则化项对应于模型的先验概率。可以假设复杂的模型有较大的先验概率,简单的模型有较小的先验概率。

模型选择

bias:多次训练所得的曲线的均值与实际最佳拟合情况之间的差值。
variance:多次训练所得的曲线与实际最佳拟合情况之间的差值,即方差。
欠拟合时,偏差大,即high bias,训练误差大,测试误差大;过拟合时,方差大, 即high variance,训练误差小,测试误差大(测试误差是个先减小后增大的过程)。
variance:估计本身的方差。bias:估计的期望和样本数据样本希望得到的回归函数之间的差别。
对于正则化中的λ,λ小 ,阶数大,overfit(flexible),对于不同的训练数据集的拟合结果抖动很大,则variance 大,bias是估计均值与实际值期望的偏差,bias小;反之,underfit(stable),对于不同的训练数据集的拟合结果抖动较小,则variance小, 不能很好地进行回归,bias大。
正则化:即为了避免过拟合,在误差函数中引入的一个分量。训练集越小,训练误差越小x,测试误差越大;训练集越大,训练误差越大, 测试误差越小,最终两者趋于相同。
欠拟合时,增加训练集,并不能改善性能;而在过拟合状态,增加训练集, 则可以改善性能。
欠拟合状态可采取的措施:减小λ,增加特征维数,增加多项式特征; 过拟合状态可采取的措施:增大λ,减少特征维数,增加训练样本;

稀疏编码

稀疏编码是一种无监督学习的方法,它用来寻找一组“超完备”基向量来更高效地表示样本数据,该基向量能够有效地找出隐含在输入数据内部的结构与模式, 可用于特征学习。
给定m 张nxn 的images, 希望找到一个字典,或者一组基,φi, 使得每个xi都能分解成 φi的线性组合,¬(x=\sum_{j=1}^{m}a_j\varphi_j),之所以说是sparse,是因为aj中大部分为0,而向量a就是另一种描述image的方式,也称为feature represen- tation的另一种方法,不同于raw pixels.
当引入了超完备基,系数ai不再由输入x唯一决定,因此引入稀疏性来解决由此产生的退化问题。要求系数稀疏,及要求输入向量,只有很少的几个值远大于0.通过给平方和最小加正则来定义代价函数,则可以通过控制惩罚项的参数达到稀疏的目的。

核函数

SVM即使将低维不可分的样本映射到高维空间中后就线性可分,由于最后用训练出来的模型进行分类预测时需要求高维空间中映射特征间的内积,而核函数的功能就是我们计算时不需要考虑高维空间的具体形式,降低了其计算复杂度。通过定义核函数,避免显示地定义基函数(特征映射)。核技巧:寻找一个映射X -> F,使得F维数比X高,因此模型更丰富,算法只需要计算点积,存在一个核函数,在需要计算点积的地方,都用相应核函数值替代。核函数构造方法:可以显示地定义一个特征映射,从而得到核函数的间接定义;或者直接定义,此时需要保证核函数为有效核。直接定义时:多项式核,Sigmoid核,RBF核,指数平方/高斯核,余弦相似度核,字符串核……非线性核有时能极大提升分类器性能,但在训练及预测时训练复杂度高。

SVM

SVM的目的:找到最大间隔的超平面,SVM是一种分类方法,一种监督学习方法

Boosting

一种贪心的自适应基展开算法,将一些弱规则组合得到最后的强规则。每次循环后提高误分样本的分布概率,即提高其在训练样本中的权重,使得下一次循环的弱分类机能够集中处理这些样本。最后将弱分类机进行组合,精度高的所占权重大。
训练误差为0后,测试误差还在减小的现象:训练误差只考虑了分类是否正确,却没有考虑分类的信度,随着循环次数的增加,训练样本的间隔会增大,因此,最后的强分类器越大,间隔可能更大,分类器变得简单,测试误差更小。
优缺点:Boosting亦有可能发生过拟合,但不常出现。分类快,简单且容易实现,没有参数需要调整,灵活度高;但是其依赖于弱分类器即数据,当弱分类器太强或者太弱,都会失败。

最小二乘法

求函数取得极值的方法:最小二乘法,梯度下降法; 其中最小二乘法为纯数学的方法,其推导有一个假设,即估计值与真实值之间的误差假设服从高斯分布。那么若回归所得估计值与真实值并非服从高斯分布,甚至差距很大,则算出来的模型对测试样本的预测则未必正确, 而梯度下降法是按下面的流程进行的:首先对θ赋值,这个值可以是随机的,也可以让θ是一个全零的向量。改变θ的值, 使得J (θ) 按梯度下降的方向进行减少。

线性判别分析LDA与主成分分析PCA

将带上标签的数据点,投影到维度更低的空间中,使得投影后的点,会形成按类别区分,一簇一簇的情况,相同类别的点,将会在投影后的空间中更接近。类内散度矩阵,类间散度矩阵。PCA的输入数据为不带标签的点,是一个预处理的方法,它可以将原本的数据降低维度,而使得降低了维度的数据之间的方差最大。用于特征提取,有最大化方差法,最小化损失法两种,前者类似K-L 算法,提取差异化最大的若干个特征,用于指导分类;而后者寻找D个正交的向量,用于特征重组。

Lasso与岭回归

都是对系数的模进行限制,lasso是对模的长度进行限制,岭回归是对模的平方进行限制。
Lasso: 实际建模过程中通常需要寻找对响应变量最具有解释性的自变量子集―即模型选择,以提高模型的解释性和预测精度。Lasso方法是一种压缩估计。它通过构造一个惩罚函数得到较为精炼的模型,使得它压缩一些系数,同时设定一些系数为零,因此保留了子集收缩的优点。
岭回归:是一种改良的最小二乘估计法,通过放弃最小二乘法的无偏性,以损失部分信息、降低精度为代价获得回归系数更为符合实际、更可靠的回归方法。

Published 07 October 2014

Machine_Learning