北京交通大学《机器学习》课程总结
| 算法 | 出处 | 解释 |
|---|---|---|
| 机器学习的定义 | 好好学习，天天向上。——毛泽东，1951年题词 | 通过定义数据表示、学习判据，实现学习算法，我们可以优化指定任务的学习结果。 |
| 归类公理 | 伯牙鼓琴，锺子期听之。方鼓琴而志在太山，锺子期曰：“善哉乎鼓琴！巍巍乎若太山。”少选之间而志在流水，锺子期又曰：“善哉乎鼓琴！汤汤乎若流水。”锺子期死，伯牙破琴绝弦，终身不复鼓琴，以为世无足复为鼓琴者。 | 机器学习是在数据中学习概念。我们认为：概念具有内蕴表示和外延表示。内蕴表示是概念的本质特征（例如：概率密度分布函数），是对概念的抽象性概括；外延表示是概念的实例集合（例如：样本的特征表示组成的集合）。
理想状况下，正如伯牙和钟子期的心意相通，内蕴表示和外延表示的归类能力是等价的，这也就是类表示唯一性公理；现实状况下，该公理只能在逼近意义下成立。 |
| 密度估计 | 桃李不言，下自成蹊。——西汉·司马迁《史记·李将军列传》 | 从服从某概率密度函数
p ( x ) p(x) p(x)的 N N N个观测样本 x 1 , x 2 , . . . , x N x_1,x_2,...,x_N x1,x2,...,xN中估计 p ( x ) p(x) p(x)，成为密度估计。如果知道 p ( x ) p(x) p(x)的分布族 p ( x ∥ θ ) p(x |theta) p(x∥θ)，则为对 θ theta θ的参数估计问题；如果不知道分布族，则是非参数估计问题。 原文中，“桃李”是指代样本，而“下自成蹊”是指代样本服从的概率分布。 |
| 回归 | 无平不陂，无往不复。——《周易》 | 给定学习数据
( x ^ , f ( x ^ ) ) N (hat{x},f(hat{x}))_N (x^,f(x^))N，学习输入变量和输出变量之间的关系，即：求拟合函数 f ( x ) f(x) f(x)。 原文的意思是：凡事没有始终平直而不遇险阻的，没有始终往前而不遇反复的。前半句论述的是数据的学习过程，后半句论述的是学习到的函数用于预测的过程。 代表性的回归算法有：线性回归、岭回归、Lasso回归。 |
| 数据降维 | 水流湿，火就燥。云从龙，风从虎。——《周易》[1]
草萤有耀终非火，荷露虽团岂是珠。——白居易《放言五首》[2] |
数据降维是指采用某种映射方法，将原高维空间中的数据点映射到低维度的空间中，使得发现数据更本质的特征、减少冗余信息和噪声信息。降维的本质是学习一个映射函数
f : x ↦ y f : x mapsto y f:x↦y，其中x是原始数据点的表达，y是数据点映射后的低维向量表达。 在文言[1]中，“湿”是“水”的本质特征，也就是低维向量表达；而文言[2]强调的是合适的、紧致的样本表示的重要性。 代表性的数据降维方法包括：主成分分析(Principal Component Analysis, PCA)、非负矩阵分解(Non-negative Matrix Fatorization, NMF)、字典学习、局部线性嵌入、典型关联分析(CCA)等 |
| 聚类 | 方以类聚，物以群分，吉凶生矣。——《周易·系辞上》[3]
天下同归而殊途，一致而百虑。——《周易·系辞下》[4] |
聚类就是指一个数据集分割成不同的簇，使得同一个簇内的数据对象的相似性尽可能大，而不在同一个簇中的数据对象的差异性尽可能地大。
虑是方法的意思，可以理解为K-means算法中的initial seed；致是结果、目标的意思，可以理解为簇的划分结果。文言[4]的意思是：可以不同的道路走到同一目的地，采取不同的方法，也可能得到相同的结果。 代表性的聚类任务有：图像分割(image segmentation)，社区发现(community detection)，协同过滤(collaborative filtering)和自然语言处理中的主题发现(topic discovery)。 |
| 分类 | 可乎可，不可乎不可。道行之而成，物谓之而然。——《庄子 · 齐物论》 | 分类是一个有监督的学习过程，即：把每一个样本归到对应的类别之中。在本章中，作者先通过归类理论推导出PAC学习理论，再用统计学习理论来分析分类问题。 |
| 神经网络 | 一发不可牵，牵之动全身。——清·龚自珍《自春徂秋偶有所感触》 | 神经网络是把分类问题转换为回归问题。 神经网络时一种黑箱算法，解释性较差；但是在大数据时代，数据相关性的重要程度远远超过因果性。
“ 一发不可牵，牵之动全身”，指的是使用ReLU、Sigmoid等激活函数时，在通过计算梯度、迭代更新参数时，单一神经元失活导致的梯度消失现象。 |
| K近邻 | 不知其子视其父，不知其人视其友，不知其君视其所使，不知其地视其草木。故曰与善人居，如入芝兰之室，久而不闻其香，即与之化矣。与不善人居，如入鲍鱼之肆，久而不闻其臭，亦与之化矣。丹之所藏者赤，漆之所藏者黑，是以君子必慎其所与处者焉。——《孔子家语》 | kNN是一种基本的分类和回归方法。kNN的输入是测试数据和训练样本数据集，输出是测试样本的类别。kNN是懒惰学习，没有训练过程，在测试时，计算测试样本和所有训练样本的距离，根据最近的K个训练样本的类别，通过多数投票的方式进行预测。 |
| 线性分类模型 | 执其两端，用其中于民。——《中庸》[5]
窗含西岭千秋雪，门泊东吴万里船。——杜甫《绝句》[6] |
闻言[5]的意思是：认清事物发展的善恶两个方向，在善中进行选择，选择一个人们可以接受的尺度，防止过犹不及，引领事物的发展。
代表模型有：线性感知机、SVM。 在求解SVM时，我们需要用到拉格朗日乘子法求解有约束优化问题；由于原规划不好解，通常要用到文言[6]中蕴含的对偶方法。 |
| 贝叶斯 | 宋有富人，天雨墙坏。其子曰：“不筑，必将有盗。”其邻人之父亦云。暮而果大亡其财，其家甚智其子，而疑邻人之父。——《韩非子·说难》 |  |
| 决策树 | 分而治之。——清·俞樾《群经平议·周官二》
古之欲明明德于天下者，先治其国；欲治其国者，先齐其家；欲齐其家者，先修其身；欲修其身者，先正其心；欲正其心者，先诚其意；欲诚其意者，先致其知，致知在格物。物格而后知至，知至而后意诚，意诚而后心正，心正而后身修，身修而后家齐，家齐而后国治，国治而后天下平。——《礼记·大学》 古之学者必有师。师者，所以传道受业解惑也。——韩愈《师说》[7] |
决策树是一种典型的分治(divide and conquer)算法；构建决策树的关键在于选择划分属性。在选择划分属性时，一种常见的度量是信息增益。
什么是信息呢？根据文言[7]，解惑意味获得了知识，也就是获得了信息，而不获取知识也就得不到信息，也无法解除困惑。所谓信息，就是所获取到的新知识(Information is the new knowledge)。 若一随机事件的概率为 p ( x ) p(x) p(x),它的自信息的数学定义为 I ( x ) = − l o g p ( x ) I(x)=-logp(x) I(x)=−logp(x)；也就是说，事件发生的概率越小，则信息量越大。随机事件x的自信息的期望就是信息熵，是度量样本集合纯度的一种指标。决策树进行划分后，我们希望信息增益越大越好，即：集合的纯度提升越大越好。 |
| 核方法(kernel method) | 一花一世界，一叶一如来。 ——《益州蒿山野竹禅师后录》 | 在处理分类问题时，将一个空间中的特征转换到另外一个空间，即可以将原来线性不好分的数据转换到另外一个空间，在这个空间中可以用一个超平面线性可分。而有时候，这个映射是不好求的；因此，我们直接核函数为高维空间的内积；这样，就可以通过核函数，就可以求导高维空间的内积了，从而可以计算出高维空间中两个数据点之间的距离和角度。 |