机器学习
主要介绍基于统计学的Machine Learning方法，主要的参考书：
- 周志华《机器学习》（西瓜书）
- 鲁伟《机器学习公式推导与代码实现》
- 刘建平-机器学习随笔-博客园
预备知识
机器学习三要素：模型、策略、算法。
统计知识
统计学的目标是利用概率论的数学工具，去推断总体的信息。一般分为两个学派：频率派（frequencist）和贝叶斯派（Bayesianist），前者认为描述总体分布的参数是一个确定的未知量，后者则认为参数未知，本身就是一个随机变量并服从一定的分布。基于两者对于统计模型认识的差异，衍生出的机器学习模型分别称为统计机器学习（Statistical Machine Learning）和概率图模型（Probabilistic Graphical Model）。
频率派最常用的手段是极大似然估计（maximized likelihood estimation, MLE），指的是在一定概率分布假设下，求解参数值使得生成当前样本的可能性最大。
最大熵模型
最大熵模型的基本思想是：在一定约束下，保证预测结果在除了约束条件之外，其分布不能反映多余的信息和先验判断，也就是说其条件熵最大化。
假设$x$和$y$之间有约束，则当约束满足时取$f(x,y)=1$否则取$0$。这个特征函数本身是有随机性的（因为预测和响应变量都有随机性），因此存在关于联合分布的期望。可以写为如下形式。
$$
\begin{aligned}
E(f) &= \sum_{x,y}P(x,y)f(x,y) \
&= \sum_{x,y}P(x)P(y|x)f(x,y)
\end{aligned}$$
注意，上面第一行的联合分布是未知的，但可以从数据中估计经验值，计算出的期望也是经验值（即均值）。
$${\tilde{E}}(f)=\sum_{x,y}\tilde{P}(x,y)f(x,y)$$
同理从第二行也可以得到类似的经验值公式，预测变量的概率可以经验化估计，而条件概率正是要求的模型预测。
$$E_P(f)=\sum_{x,y}\tilde{P}(x)P(y|x)f(x,y)$$
最大熵模型就是要极大化条件熵，问题形式化为：
$$ \begin{aligned}
\max\limits_P H(P)
&=-\sum_{x}P(x)H(Y|X=x)\
&=-\sum_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)
\end{aligned} \
\begin{aligned}
s.t.\quad
& {\tilde{E}}(f_i)=E_P(f_i),,i=1,2,\dots,k\
& \sum_yP(y|x)=1
\end{aligned}
$$
利用Lagrange解有约束的优化问题，由当熵达到最大时对条件概率梯度为零，可以解出：
$$P_w(y|x) \propto \mathrm{exp}\left(\sum_{i=1}kw_if(x,y)\right)=\mathrm{exp}(\boldsymbol{w}T\boldsymbol{f}(x,y))$$
其中，$\boldsymbol{w}$是乘子。熵最大时对乘子也需要梯度为零，因此在上式基础上对乘子求梯度并优化即可得到问题解。
最大熵逆向强化学习（MaxEnt-IRL）算法是一个典型的例子。
EM算法
期望最大化算法（expectation-maximization, EM）主要解决在MLE过程中，样本构成异质性的问题，也就是说数据集当中还存在一个隐藏变量$Z$，学习任务收集的数据称为不完全数据。来自知乎的一个例子能较好说明这种情况。
EM算法的推导需要Jensen不等式的支持，但是这里不深入探讨推导，仅简单介绍一下其步骤：
- E步（固定$\theta$，调整$z$）：在第$t$步，对于第$i$个样本，有
$$Q_i(z{(i)})=P(z|x^{(i)}, \theta^t)$$ - M步（固定$z$，调整$\theta$）：构造似然函数，然后最大化之。
$$L(\theta,\thetat)=\sum_{i=1}n\sum_{z{(i)}}Q_i(z)\log P(x{(i)},z|\theta)$$
$$\theta^{t+1} = \argmax\limits_\theta L(\theta, \theta^{(t)})$$
不断迭代至收敛即可。
线性模型
线性回归
- 梯度下降法
- 最小二乘法：直接矩阵运算求解
正则化的线性回归
岭回归
最小二乘法
Lasso回归
- 坐标轴下降法（coordinate descent）
- 最小角回归法（least angle regression）
ElasticNet弹性网络
线性判别
广义线性模型
Logistic回归
广义可加模型
树模型和集成学习
这个部分讲解三种经典树模型：ID3、C4.5和CART，以及由树作为基模型通过提升法（Boosting）和装袋法（Bagging）集成方法搭建的学习模型。
树模型
信息熵度量了概率分布的不确定性，以离散的情况为例，如果$C$代表所有的类别数，那么信息熵计算如下：
$$H(\mathcal{D}) = -\sum_{k=1}^C p_k\log p_k$$
条件熵是在给定条件之后，每种条件下信息熵的期望。设模型对数据集进行划分有$T$个类别，则条件熵为：
$$\begin{aligned}
H(\mathcal{D|}X) & = E_\mathcal{X}(H(\mathcal{D}|X)) \
& = \sum_{i=1}^T p_{x_i} H({\mathcal{D}|X = x_i})
\end{aligned}$$
不同的树模型在选择，对于条件熵相对于全局信息熵的优化目标不同。
- ID3：最大化信息增益，即信息熵和条件熵之差：$$g(\mathcal{D},X) = H(\mathcal{D}) - H(\mathcal{D|}X)$$
- C4.5：最大化信息增益比：$$g_r(\mathcal{D},X) = \frac{g(\mathcal{D},X)}{H(X)}$$
其中，X的熵值为：$$H(X)=-\sum_{i=1}^{n_i}\frac{|\mathcal{D_i}|}{|\mathcal{D}|}\log\frac{|\mathcal{D_i}|}{|\mathcal{D}|}$$ - CART：最大化Gini系数
装袋法
随机森林（Random Forest, RF）的随机性同时包括：
- 样本的随机性：每次学习都需要bootstrap方法重抽样
- 特征的随机性：每次学习的特征待选择集合都会被重新抽取
提升法
这里介绍两个比较经典的提升模型：自适应提升（AdaBoost）和梯度提升决策树（GBDT）。他们都属于加性模型。
AdaBoost会根据：
- 精度调整学习器权重，准确率高的权重更大
- 误差调整样本权重，误差更大的权重更大
然后将基模型加起来代表最终的预测结果。
GBDT的思想是在每一步学习中，求取上一步损失函数的负梯度，作为本轮学习的数据集，得到新的决策树学习器，然后把所有的学习器相加即可。
GBDT可以通过样本筛选来加速学习。类似于AdaBoost的样本赋权思想，对梯度值较小的样本，认为当前模型已经学习得较为不错，在下一步学习中，丢弃小梯度的样本，从而加速学习。但这种算法可能会导致样本分布发生变化，进而影响精度。
提升法的工程化实现
XGBoost是GBDT的改进版本，具有非常优秀的预测性能。这一节介绍这个模型及其变式。参考资料
XGBoost
全称极度梯度提升树，相对于GBDT有几方面改进：
- 在模型中加入正则项，对于叶子个数和预测权值做出惩罚
- 损失函数用一阶和二阶导数逼近，各个实例的梯度已知
为了计算结点分裂条件，基于上述的条件可以求出分裂结点取值，以及损失函数的解析解。然后根据损失函数的增益值$\mathrm{Gain} = L_{\mathrm{before}} - L_{\mathrm{after}}$来选择合适的分裂点。
分裂方式是level-wise，即从目前节点出发考虑当前所有叶节点是否分裂。
由于损失函数需要二阶可导，因此XGBoost只执行回归任务。
LightGBM
XGBoost的算法复杂度是比较高的。轻量梯度提升机（LightGBM）从三个方面对XGBoost进行算法优化。
- 针对特征分裂点遍历：直方图算法。将特征空间离散化和分箱操作，可以加速分裂特征点的检索，同时有差加速特性：父节点的直方图减去其中一个子节点的直方图即为另一个子节点的直方图。
- 针对样本量：单边梯度抽样算法（gradient-based one-side sampling, GOSS）。根据特征的绝对值进行降序排序，然后选择大绝对值的样本，将小绝对值样本的绝对值放大，将特别小的绝对值的样本丢弃。
- 针对特征数：互斥特征捆绑算法（exclusive feature bundling, GFB）。互斥特征指的是两个特征总有至少取零，因此可以捆绑为一个特征。利用图论的图着色问题选择捆绑集，通过调整取值范围融合两个feature。
另外，LightGBM采用了leaf-wise的树生长策略。
CatBoost
是GBDT的变体，对GBDT的改进有两方面。
- 类别变量处理。这也是CatBoost名字由来（Categorical Boosting），本技术可以对类别特征及其组合做转换变为数值特征，称为目标变量统计法（target statistics, TS）。最典型的greedy TS用每个类别的平均值代替类别标签，而不是生成一大堆哑变量。其他方法还包括holdout TS、leave-one-out TS、ordered TS等技术。
- 解决预测偏移问题。预测偏移（prediction shift）指的是训练集和测试集的数据的特征分布不同，导致学习器泛化能力变弱的问题。解决方法是排序提升法（ordered boosting），即每次基模型学习的训练集都比上一次学习的要多一个，用上一次训练得到的模型计算本轮学习的残差。
另外，CatBoost模型生成的是相对平衡的对称树。
支持向量机
这是统计学习领域最著名的算法，以复杂的数学推导和算法实现著称。
线性可分
在SVM中响应变量集合$\mathcal{Y}={-1,1}$，主要的推导环节为：
- 计算函数间隔，目标为最大化它
- 利用解析几何知识，将函数间隔转换为几何间隔，目标是最小化参数的L2范数
- 根据凸优化理论，原始问题转换为对偶问题，将原来的极小极大化问题转换为极大极小化问题
- 对极大极小化问题，构造Lagrange优化问题，并引入KKT条件
- 求解乘子，进而解超平面
近似线性可分
比线性可分多出一个松弛变量，并对松弛变量做惩罚：加入损失函数。然后和线性可分情况一样，作为凸二次规划问题进行求解。
线性不可分
核技巧（kernel tricks）：设计非线性变换$\phi(\cdot):\mathbb{R}m\mapsto\mathbb{R}n$，将原始数据中的实例向量（m维）通过$\phi$投影到n维空间中去，变成（近似）线性可分问题。在实际的优化问题求解中，Lagrange对偶问题需要涉及到内积$x_1^Tx_2$的计算，这在投影后的空间中直接可替换为核函数$K(x_1,x_2) = \phi(x_1)^T\phi(x_2)$，也就是说根本不需要真的对数据做投影，只需要在优化过程中代入核函数即可求解。
SMO算法：全称序列最小化优化（sequential minimal optimization），用于极大化问题乘子的求解。思想是对所有乘子每次只优化两个而固定其他。
概率图模型
朴素贝叶斯
朴素贝叶斯（Naive Bayes, NB）是概率图模型中最基础的分类算法。其预假设是：同一个类内的特征彼此独立，这个极强的假设也是其名“朴素”的来源。
对于分类任务而言，每一个类本身可以计算先验概率
$$P(Y=c_K)=\frac{f_K}{N}$$
然后在了解特征信息后，可以计算似然值。由于朴素地认为特征独立，因此
$$P(X=x|Y=c_K)=\prod_{i=1}^{p}P(x_i|Y=c_K)$$
了解先验和似然，用贝叶斯定理就可以求出后验概率，即分类结果。
由于数据的稀疏性，计算某些特征的似然时很有可能求出为零，导致整个似然函数作为一个连乘结构同样为零。为此NB会有一个平滑算法阻止零结果的生成。
贝叶斯网络
这个方法同样利用贝叶斯定理，需要计算似然值$P(X=x|Y=c_K)$。但贝叶斯网络就没有NB那么朴素了，取消了特征独立性的假设，因此不可以用连乘表示似然。为此贝叶斯网络构建表示特征之间作用的有向无环图（directed acyclic graph, DAG），每个节点还可以绘制出特征概率表，根据表可以计算出如下似然值
$$P(x_1, x_2, \dots, x_n)=\prod_{i=1}^pP(x_i|\mathrm{Parents}(x_i))$$
隐马尔可夫模型
上图是隐马尔可夫模型（hidden Markov model, HMM）的一个典型例子。简言之，HMM刻画的是具有隐随机变量的随机过程序列，并且这种序列具有马尔可夫性质。对于HMM的形式化表述可以用如下三元组表达：
$$\mu=(\boldsymbol{A}, \boldsymbol{B}, \boldsymbol{\pi})$$
考虑可数的情况。假设状态集是$Q={q_1, q_2,\dots,q_N}$元素个数为$N$，观测集$V={v_1, v_2,\dots,v_M}$个数为$M$。三元组中$\boldsymbol{A}{N \times N}$是隐状态的概率转移矩阵，$\boldsymbol{B}$是生成观测的矩阵，$\boldsymbol{\pi}_{N \times 1}$是隐状态的先验概率向量。
确定HMM模型的参数后，
HMM模型的预先假设有两个：
- 齐次马尔可夫假设：除初始状态由先验概率向量$\boldsymbol{\pi}$之外，其他时刻的状态仅受前一时刻状态的影响。
$$P(z_t=q_{n(t)}|z_{t-1}=q_{n(t-1)},z_{t-2}=q_{n(t-2)},\dots)=P(z_t=q_{n(t)}|z_{t-1}=q_{n(t-1)})$$ - 观测独立假设：任意时刻的观测只取决于当前隐状态。
$$P(x_t=v_{m(t)}|x_{t-1}=v_{n(t-1)},x_{t-2}=v_{n(t-2)},\dots, z_t)=P(x_t=v_{m(t)}|z_t)$$
就会有三个关键问题需要解决： - Evaluation（概率生成问题）：在给定模型$\mu$和轨迹$\xi=(x_1,x_2,x_3,\dots)$的情况下估计出现轨迹的概率$P(\xi|\mu)$
- Learning（参数估计问题）：在给定轨迹$\xi$的情况下，求最大似然的$\mu$，即$\argmax\limits_\mu P(\xi|\mu)$
- Decoding（序列标注问题）：在给定模型$\mu$和轨迹$\xi$的情况下，求取最大似然的隐状态序列$\zeta=(z_1,z_2,z_3,\dots)$，即求$\argmax\limits_\zeta P(\zeta|\xi,\mu)$
Evaluation
有前向和后向两种算法。前向算法定义当前步的状态以及从最开始到当前得到现有观测的联合概率，记为$\alpha$，则有
$$\alpha_t(q_j) = P(x_1,x_2,\dots,x_t, z_t=q_j|\mu)=P(\xi,z_t=q_j|\mu)$$
特别当$t=1$，有
$$\alpha_1(q_j) = P(z_1=q_j|\mu)P(x_1|z_1=q_j,\mu)=\pi_jb_j(x_1)$$
如果上一步所有的$\alpha_t(\cdot)$对所有的状态均已知，那么可以试图推导$\alpha_{t+1}(\cdot)$
$$
\begin{aligned}
\alpha_{t+1}(q_j)
&= \sum_{i}^N P(\xi_{t+1}, z_t=q_i, z_{t+1}=q_j|\mu) \
&= \sum_{i}^N P(x_{t+1}|\xi_{t}, z_t=q_i, z_{t+1}=q_j,\mu) P(\xi_{t}, z_t=q_i, z_{t+1}=q_j|\mu) \
&= \sum_{i}^N P(x_{t+1}|z_{t+1}=q_j,\mu) P( z_{t+1}=q_j|\xi_{t}, z_t=q_i,\mu) P(\xi_{t}, z_t=q_i|\mu) \
&= \sum_{i}^N P(x_{t+1}|z_{t+1}=q_j,\mu) P( z_{t+1}=q_j|z_t=q_i,\mu) P(\xi_{t}, z_t=q_i|\mu)\
&= \sum_{i}^N a_{ij}b_j(x_{t+1})\alpha_tT(q_i)
\end{aligned}$$
这样就可以形成一个迭代公式，递归即可。这里只考虑了隐状态为$q_j$的前向概率。如果不考虑隐状态，得到轨迹$\xi$的边际概率，就是关于隐状态求和。根据全概率公式，有
$$\alpha_T=P(\xi|\mu)=\sum_j^NP(\xi, z_T=q_j|\mu)=\sum_j^N\alpha_T(q_j)$$
后向算法同理，这里不作详细推导，直接给出结论。定义后向概率为
$$\beta_t(q_i) = P(x_{t+1},x_{t+2},\dots,x_T|z_t=q_i,\mu)$$
后向概率的递归规则是
$$\beta_t(q_i) = \sum_{j}^N a_{ij}b_j(x_{t+1})\beta_{t+1}(q_j)$$
起始条件是从后面规定的
$$\beta_T(\cdot)=1$$
求出的轨迹概率为
$$\beta_0=P(\xi|\mu)=\sum_i^Nb_i(x_1)\pi_i\beta_1(q_i)$$
Learning
使用Baum-Welch算法求解参数。事实上就是EM算法在HMM中的应用。推导比较复杂，跳过不讲。了解是EM算法就可以。
Decoding
主要利用技术是Viterbi算法。注意这里参数和观测轨迹都已知。现在记$\rho(\cdot)$是由某个隐状态生成当前观测值的概率，也就是似然值。对于第一步，有
$$\rho_1(q_i)=\pi_ib_i(x_1)$$
当到第二步时，要让第二步观测值的似然值最大。这里第二步对应的隐状态发生的概率，同时由第一步隐状态概率和状态转移决定，可以表示为
$$\rho_2(q_j)=\left[\max\limits_{i\in1,2,\dots,N}\rho_1(q_i)\cdot a_{ij}\right]b_j(x_2)$$
从直觉上说，每次计算似然值，都是选择一条最有可能到达当前状态值的状态路径。之后对任意时刻，有
$$\rho_t(q_j)=\left[\max\limits_{i\in1,2,\dots,N}\rho_{t-1}(q_i)\cdot a_{ij}\right]b_j(x_t)$$
条件随机场
降维
降维一般分为两种子类型：投影（projection）和流形学习（manifold learning）。
投影
主成分分析及相关方法
主成分分析（principal component analysis, PCA）将数据实例视为向量，投影到最大变异的方向上，有两种理解角度。
- 提取最大方差
- 压缩最小距离成本
利用协方差矩阵（对称矩阵）进行特征值分解，分解出的特征值$\lambda$就是主成分的方差，特征向量首先是正交的（实对称矩阵的性质），然后方向与主成分轴向相同。
核主成分分析（KPCA）道理相同，只不过利用核技巧将向量投影到高维空间中去。
独立成分分析
奇异值分解
奇异值分解（singular value decomposition, SVD）是一种对矩阵的分解方法，可以将任意矩阵分解为如下形式。
$$A = U^T\Sigma V$$
右侧分别为正交矩阵、对角矩阵和正交矩阵。
流形学习
首先从最经典的多维标度法开始介绍，进而延伸介绍非线性流形学习方法
多维标度法
多维标度法（multidimensional scaling, MDS）简单来说，就是通过距离矩阵来恢复空间坐标的方法。如果原始数据实例都是高维度向量，通过定义距离函数可以求出距离矩阵，那么将数据集恢复到低维度空间当中就相当于达到了降维的目标。
MDS一共有三个子类型：古典解（classic MDS），度量解（metric MDS）和非度量解（non-metric MDS），分别对应严格恢复距离、恢复距离的单调函数和恢复距离的排序。