机器学习

来自iCenter Wiki
跳转至： 导航、 搜索

机器学习的定义

机器学习（Machine Learning），是指计算机从数据中自动分析获得规律，并利用规律对未知数据进行预测。因此，机器学习又称为统计学习(statistical learning)或统计机器学习(statistical machine learning)。

机器学习的一个简洁的定义：对于某类任务T（Task）和性能度量P（Performance），一个计算机程序被认为可以从经验E（Experience）中学习是指通过经验E改进后，它在任务T上由性能度量P衡量的性能有所提升。

机器学习的目标

问题：人类的天性比较懒散，而且重复的工作容易疲劳。

解决方法：发明算法，解决重复性的劳动。

机器学习的任务

  • 预测：通过数据集，预测新的数值
  • 分类：通过数据集，对新数值进行集合分类


机器学习的内容

机器学习的内容可以分为监督学习（Supervised Learning）、非监督学习（unsupervised Learning）和半监督学习（Semi-Supervised Learning），还有强化学习(reinforcement learning)和推荐算法(Recommender algorithm)等。

机器学习的主要任务是预测（Regression）与分类（Classification）。

机器学习的特点

李航在《统计学习方法》一书中，总结为：

  1. 以计算机为平台
  2. 以数据为研究对象
  3. 以方法为中心
  4. 概率论、计算理论、最优化理论和计算机科学等学科的交叉学科
  5. 具有独有的理论体系和方法论


主要机器学习方法

感知机

感知机是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。

感知机学习旨在求出将训练数据进行线性划分的分离超平面，为此，导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。

它是神经网络与支持向量机的基础。

k近邻

k近邻法(k-nearest neighbor, k-NN)是一种基本分类与回归方法。

k近邻法假设给定一个训练数据集，其中的实例类别己定。

分类时，对新的实例，根据其k个最近邻的训练实例的类别通过多数表决等方式进行预测。

k近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。

k值的选择、距离度量及分类决策规则是k近邻法的三个基本要素。

决策树

ID3算法 

 ID3由Ross Quinlan在1986年提出。ID3决策树可以有多个分支，但是不能处理特征值为连续的情况。决策树是一种贪心算法，每次选取的分割数据的特征都是当前的最佳选择，并不关心是否达到最优。在ID3中，每次根据“最大信息熵增益”选取当前最佳的特征来分割数据，并按照该特征的所有取值来切分，也就是说如果一个特征有4种取值，数据将被切分4份，一旦按某特征切分后，该特征在之后的算法执行中，将不再起作用，所以有观点认为这种切分方式过于迅速。ID3算法十分简单，核心是根据“最大信息熵增益”原则选择划分当前数据集的最好特征，信息熵是信息论里面的概念，是信息的度量方式，不确定度越大或者说越混乱，熵就越大。在建立决策树的过程中，根据特征属性划分数据，使得原本“混乱”的数据的熵(混乱度)减少，按照不同特征划分数据熵减少的程度会不一样。在ID3中选择熵减少程度最大的特征来划分数据（贪心），也就是“最大信息熵增益”原则。

C4.5算法 

 C4.5是Ross Quinlan在1993年在ID3的基础上改进而提出的。.ID3采用的信息增益度量存在一个缺点，它一般会优先选择有较多属性值的Feature,因为属性值多的Feature会有相对较大的信息增益?(信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大).为了避免这个不足C4.5中是用信息增益比率(gain ratio)来作为选择分支的准则。信息增益比率通过引入一个被称作分裂信息(Split information)的项来惩罚取值较多的Feature。除此之外，C4.5还弥补了ID3中不能处理特征属性值连续的问题。但是，对连续属性值需要扫描排序，会使C4.5性能下降。

CART算法 

 CART（Classification and Regression tree）分类回归树由L.Breiman,J.Friedman,R.Olshen和C.Stone于1984年提出。ID3中根据属性值分割数据，之后该特征不会再起作用，这种快速切割的方式会影响算法的准确率。CART是一棵二叉树，采用二元切分法，每次把数据切成两份，分别进入左子树、右子树。而且每个非叶子节点都有两个孩子，所以CART的叶子节点比非叶子多1。相比ID3和C4.5，CART应用要多一些，既可以用于分类也可以用于回归。CART分类时，使用基尼指数（Gini）来选择最好的数据分割的特征，gini描述的是纯度，与信息熵的含义相似。CART中每一次迭代都会降低GINI系数。下图显示信息熵增益的一半，Gini指数，分类误差率三种评价指标非常接近。

朴素贝叶斯方法

给出待分类项，求解在此项出现的条件下其他各个类别的出现的概率，哪个概率较大就认为待分类项属于哪个类别。

逻辑斯提回归模型和最大熵

逻辑回归(logistic regression)是统计学习中的经典分类方法。最大嫡是概率模型学习的一个准则将其推广到分类问题得到最大熵模型(maximum entropy model)。

逻辑回归模型与最大熵模型都属于对数线性模型。

支撑向量机

支持向量机(support vector machines, SVM)是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器；支持向量机还包括核技巧，这使它成为实质上的非线性分类器。

支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划(convex quadratic programming)的问题，也等价于正则化的合页损失函数的最小化问。

支持向量机的学习算法是求解凸二次规划的最优化算法。

AdaBoost

AdaBoost，是英文"Adaptive Boosting"（自适应增强）的缩写，由Yoav Freund和Robert Schapire在1995年提出。

它的自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

具体说来，整个Adaboost 迭代算法就3步：

  1. 初始化训练数据的权值分布。如果有N个样本，则每一个训练样本最开始时都被赋予相同的权值：1/N。
  2. 训练弱分类器。具体训练过程中，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它的权值就被降低；相反，如果某个样本点没有被准确地分类，那么它的权值就得到提高。然后，权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。
  3. 将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。换言之，误差率低的弱分类器在最终分类器中占的权重较大，否则较小。

隐马尔可夫

隐马尔可夫模型(hidden Markov model, HMM)是可用于标注问题的统计学习模型，描述由隐藏的马尔可夫链随机生成观测序列的过程，属于生成模型。

隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。

隐藏的马尔可夫链随机生成的状态的序列，称为状态序列(state sequence)：每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列(observation sequenoe )。序列的每一个位置又可以看作是一个时刻。

条件随机场

条件随机场(conditional random field, CRF)是给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型，其特点是假设输出随机变量构成马尔可夫随机场。

条件随机场可以用于不同的预测问题，这里主要讲述线性链(linear chain)条件随机场在标注问题的应用，这时问题变成了由输入序列对输出序列预测的判别模型，形式为对数线性模型，其学习方法通常是极大似然估计或正则化的极大似然估计。

机器学习的任务

预测

  • 线性预测：

线性回归模型

  • 房价预测：机器学习==数学建模？

数据：以往房价数据

模型：（假设）线性模型y=a*x + b

算法：求出a, b （最小二乘法）

分类

  • 二元分类的逻辑斯提回归模型
  • 多元分类的逻辑斯提回归模型

软件工具

(Python)

scikit-learn (Source Code)

阅读材料

  1. Jordan, M. I., and T. M. Mitchell. "Machine learning: Trends, perspectives, and prospects." Science 349, no. 6245 (2015): 255-260. Machine_Learning_Science_2015
  2. 李航，统计学习方法，清华大学出版社。

参考课程

  1. STA414 (U. Toronto), Statistical Methods for Machine Learning and Data Mining, https://www.cs.toronto.edu/~rsalakhu/STA414_2015/.
  2. CS229 (Stanford U.), Machine Learning, http://cs229.stanford.edu/.
取自“http://wiki.icenter.tsinghua.edu.cn/icenterwiki/index.php?title=机器学习&oldid=46287”