本文主要围绕机器学习/统计学习方法进行深层次展开。《统计学习方法》是李航博士所著的关于系统、详细的统计学习相关方法的介绍书籍。主要内容覆盖统计学习方法概论、感知机、k-means，朴素贝叶斯，决策树，逻辑回归，SVM，梯度提升，EM算法，隐马尔可夫，条件随机场等。本文尽可能将所有算法加以实现，注重数理基础与实践相结合，以期更好的效果。建议先修吴恩达《机器学习》课程。

References

机器学习（周志华） “西瓜书”，教材

机器学习实战基于Python的编程练习册

统计学习方法（李航）算法的数理分析，代码实现

机器学习训练秘籍（吴恩达）面向工程应用的指南

《动手学深度学习》深度学习进阶

機器學習基石，机器学习技法（林轩田）进阶教学视频，Notes

统计学习原理

人工智能

浅谈人工智能

机器学习

机器学习：为了寻找更好数据表示的自动搜索。

模式识别

模式识别：从数据中获得规律/模式/特征。

数据 = 模式 + 噪声

统计学习要素

模型：构建从输入到输出的一类映射，从而产生假设空间。

策略：按什么样的准则在假设空间中学习最优的模型。

算法：学习模型的具体计算方法。

短见定理

短见定理：过拟合无法彻底避免。

反证：（基本假设：P$\neq$NP）

机器学习通常面临着NP-Hard问题（甚至更难），而有效的学习算法必然在多项式时间内运行完毕。

若可以彻底避免过拟合，则通过经验误差最小化就能获得最优解，意味着我们构造性地证明了“P=NP”。矛盾。

机器学习是短视、贪心的。

午餐定理

午餐定理：对完全随机问题，任意学习算法的期望性能一致。（no free lunch）

证明：（考虑二分类问题）

$（记学习算法为a，f为真实函数(问题)，X为训练集，\chi为样本空间，\mathbb{I}是布尔函数）$ $\begin{split} 对特定问题f的误差：E_{ote}(a|X,f)&=\sum _{h}\sum _{x\in \chi -X}P(x)\mathbb{I}(h(x)\neq f(x))P(h|X,a) \end{split}$ $\begin{split} 总误差：\sum _{f}E_{ote}(a|X,f) &=\sum _{f}\sum_{h}\sum_{x\in \chi -X}P(x)\mathbb{I}(h(x)\neq f(x)){\color{red}{P(h|X,a)} } \\ &=\sum _{x\in \chi -X}P(x)\sum _{h}P(h|X,a)\sum _{f}\mathbb{I}(h(x)\neq f(x)) \quad,{\color{red}{积分解耦} }\\ &=\sum _{x\in \chi -X}P(x)\sum _{h}P(h|X,a){\color{red}{\frac{1}{2}2^{|\chi|} } } \quad,设f均匀分布\\ &=2^{|\chi|-1}\sum _{x\in \chi -X}P(x)\sum _{h}P(h|X,a)\quad,条件概率求和 \\ &=2^{|\chi|-1}\sum _{x\in \chi -X}P(x)\cdot {\color{red}{1} }\quad,结果与算法a无关 \end{split}$

积分解耦（分部积分）的原理：

$P(x)表示从非训练集中选取样本x的概率，$（古典概型）

$显然与f和h无关$

$P(h|X,a)表示基于训练集X和学习算法a时，产生假设h的概率，$

$显然与真实问题f无关$

$\mathbb{I}(h(x)\neq f(x))表示基于样本x时假设h与真实f不吻合的布尔判断$，

这是一个纯判断，不含概率，因此可以首先积分

当我们引入了对$f$的积分之后，对特定问题的积分被解耦

$\sum _{f}\mathbb{I}(h(x)\neq f(x))相当于求{0,1}^{|\chi|}$（幂集）

若$f$均匀分布，则一半的f对x的预测与h(x)不一致，因此要乘上1/2

NFL定理实际上构想了一个纯粹幻想空间。
完全随机的问题等价于一个没有任何模式（Pattern）的问题，机器学习不可能从真随机之中获得规律。

通过幻想学的蛋形图来直观感受一下短见定理和午餐定理的约束：（More）

1547752453147

由直观的图像我们可以看出：

极端的欠拟合导致午餐现象

若不考虑误差，过拟合和欠拟合的泛化能力与它们的名义是相反的（过拟合的泛化能力小，欠拟合的泛化能力大）
若考虑误差，过拟合和欠拟合产生的误差类型是不同的（过拟合对变错，欠拟合错变对）

显然，增大数据集能有效解决短视（过拟合）现象

机器学习的过程是从想界到数据边界的收缩过程，其目标是尽可能与实界重合

如果增加收缩能力（即学习能力，比如根据多个复杂原理进行收缩），则能有效解决欠拟合现象

注：一般认为想界和实界是固定的。

聚类分布律

聚类分布律：自然界中同一类别的高维数据，往往集中在某个低维流形附近。

流形分布律

流形分布律：不同的类对应着流形上的不同概率分布，这些分布之间的距离大到足够将这些类区分。

极大似然律

极大似然律：给定概率模型，调参，使得样本空间的概率最大化。

最大熵原理

最大熵原理：给定概率模型，调参，使得模型的熵最大化。

最大熵模型| PLM’s Notes | 好好学习，天天笔记

最大熵模型| Kubi Code’Blog

特征工程

Garbage in, garbage out.

特征工程：对原始数据进行一系列工程处理，提炼出特征。

特征工程旨在去除原始数据中的杂志和沉淀，设计更高效的特征以刻画联想规则。

结构化数据（张量）：结构化数据可以看成关系型数据库的一张表，每列都有清洗的定义，包含连续、离散两种类型；每行代表一个样本。

非结构化数据（流形）：非结构化数据包括文本、图像、音频、视频等，其包含的信息丰富、复杂、抽象、多变。

特征归一化

区间缩放和正态缩放比较常用。

归一化对于决策树模型不适用，因为节点分裂只与信息增益比例有关。（归一化不改变比例）

区间缩放

Min-Max Scaling 又称为 Rescaling，区间缩放的公式为：

$x' = \frac{x-min(x)}{max(x)-min(x)}$

缩放后的特征将分布在 [0,1] 区间。

正态缩放

(Z-Score) Standardization，缩放后的特征将服从标准正态分布：

$x' = \frac{x-\mu}{\delta}$

μ,δ分别为对应特征$x$向量的均值和标准差。缩放后的特征将分布在 (−Inf,Inf) 区间。

其它归一化手段

均态缩放

Mean normalization是区间缩放和正态缩放相结合的变种，其公式为：

$x' = \frac{x-{\color{red}{\mu} } }{max(x)-min(x)}$

μ为$x$向量的均值，缩放后的特征将分布在 (-1,1) 区间。

度量缩放

Scaling to unit length相对均态缩放，保留了更多原向量的面貌。其公式为：

$x' = \frac{x}{ {\color{red}{||} }x{\color{red}{||} } }$

缩放后的特征将分布在某个不定小区间。$||x||$是范数（Norm）。（More）

若取$||x||=|x|$绝对值，则缩放后的特征将分布在 [-1,1] 区间。

离散编码

类别型特征（Categorical Feature）：指性别（男、女）、血型（A、B、AB、O）等有限取值的离散特征。

热编码

独热编码（One-hot Encoding）：将实体映射为命中向量。（向量维数=类别数）

${\color{red}{A} },{\color{green}{B} },{\color{blue}{C} }\longrightarrow ({\color{red}{1} },0,0),(0,{\color{green}{1} },0),(0,0,{\color{blue}{1} })$

使用稀疏向量来节省空间。配合特征选择来降维。

序编码

保序编码（Ordinal Encoding）：按类别关系映射数值关系。

$低<中<高\longrightarrow 1<2<3$

二进制编码

二进制编码（Binary Encoding）：先编码为数字ID，然后映射为二进制数。

${\color{red}{A} },{\color{green}{B} },{\color{blue}{C} }\longrightarrow {\color{red}{1} },{\color{green}{2} },{\color{blue}{3} }\longrightarrow (0,0,{\color{red}{1} }),(0,{\color{green}{1} },0),(0,{\color{blue}{1} },{\color{blue}{1} })$

More：Helmert Contrast，Sum Contrast，Ploynomial Contrast，Backward Difference Contrast.

特征组合

为了提高复杂关系的拟合能力，在特征工程经常会把一阶离散特征两两组合，构成高阶组合特征。

模型评估

1558719286890

逻辑回归

高维空间易过拟合。

感知机

在机器学习-神经网络基础-感知机有基础介绍。

K-means

请问如何用数学方法证明K-means是EM算法的特例？

高维空间欧式距离度量失效。

KNN

KNN和K-mean有什么不同？ - 知乎（但感觉k-means完还是要kNN一下才能输出预测结果 anyway。。）

机器学习进阶