1.

• 结合前几次中国经济困境和解决方案，分析当前情况。资产阶级分层严重，需要从数据分析角度分析民众承受力。
• 市场宣传和愿景与实际情况往往相反，特别是房价方面。
• 房子以后作为资产，可在银行存取，需要结合租售比，来确定房价。

1. 股票交易规则和制度

• 交易时间
• 做T

2. 股价形成机制

3. 集合竞价

1. BP 算法

对训练例 $(x_k, y_k)$，假定神经网络的输出为 $\hat{y_k}$，则神经网络在 $(x_k, y_k)$ 上的均方误差为：
\begin{eqnarray}
E_k = \frac{1}{2}(\hat{y_k} - y_k)^2
\end{eqnarray}

其中，
\begin{eqnarray}
\hat{y_k} = f(\sum \limits_{h=1}^q wb - \theta)
\end{eqnarray}
其中，$w$ 为隐层与输出层之间的连接权，$b$ 为隐层的输出，$\theta$ 为输出层的阈值，$q$ 为隐层的神经元个数。 $f = \frac{1}{1+e^{-x}}$ 为 Sigmoid 函数，具有 $\frac{\partial{f}}{\partial{x}} = f(x)(1-f(x))$ 性质。

BP 算法是基于梯度下降策略，以目标的负梯度方法对参数进行调整。下面以 $w$ 的求解为例讲解过程。
\begin{eqnarray}
\begin{aligned}
&w \leftarrow w + \Delta{w}\
&\Delta{w} = -\eta \frac{\partial{E_k}}{\partial{w}}
\end{aligned}
\end{eqnarray}
其中，
\begin{eqnarray}
\frac{\partial{E_k}}{\partial{w}} &=& \frac{\partial{E_k}}{\partial{\hat{y}_k}} \frac{ \partial{\hat{y_k}} } {\partial{(\sum \limits_{h=1}^q wb - \theta)}}
\frac{\partial{(\sum \limits_{h=1}^q wb - \theta)}}{\partial{w}}
\end{eqnarray}
其中，
\begin{eqnarray}
\begin{aligned}
&\frac{\partial{E_k}}{\partial{\hat{y}_k}} = (\hat{y_k} - y_k) \
& \frac{ \partial{\hat{y_k}} } {\partial{(\sum \limits_{h=1}^q wb - \theta)}} = \frac{\partial{f}}{\partial{x}} = \hat{y_k}(1-\hat{y_k}) \
& \frac{\partial{(\sum \limits_{h=1}^q wb - \theta)}}{\partial{w}} = b
\end{aligned}
\end{eqnarray}
则，
\begin{eqnarray}
\Delta{w} = \eta \hat{y_k} (1-\hat{y_k})(y_k-\hat{y_k})b
\end{eqnarray}

类似可得 $\Delta{\theta}, \Delta{v}, \Delta{\gamma}$，$\Delta{v}, \Delta{\gamma}$ 分别为输入层到隐层的连接权和隐层的阈值。

上面介绍的标准 BP 算法每次仅针对一个训练样本更新连接权和阈值。如果类似推导出基于累计误差最小化的更新规则就得到了累计误差逆传播。一般来说，标准 BP 算法参数更新非常频繁，对不同样本可能出现“抵消”现象。累计误差在下降一定程度后，进一步下降会非常缓慢，这时标准 BP 往往会更快的获得较好的解。

由于 BP 神经网络的强大表示能力，经常遭遇过拟合。有两种策略常用来缓和过拟合：

• 早停：将数据分为训练集和验证集，若训练集误差降低但验证机误差升高，则停止训练，同时返回具有最小验证集误差的结果；
• 正则化。

1. 支持向量机

给定训练样本集 $\left { (x_i,y_i)\right }_{i=1}^N$，其中 $x_i \in \mathbb{R}^n $ 为特征空间，$y_i \in { -1,+1 }$ 为类标签。支持向量机是基于划分超平面 (separating hyperplane) 将数据分类的分类器。如图 1 所示，二维数据的线性划分超平面为一条直线。

可以看到，具有多个划分超平面可以将数据分类，我们需要找出唯一的划分超平面，使得划分效果最优，SVM 采用的是最大间隔 (maximum margin) 划分超平面。如图 2 所示。

图 2 中的实心点，刚好处在划分超平面上，这些点确定了划分超平面，称之为支持向量。

在样本空间中，划分超平面可以用一个线性方程表示：
\begin{equation}
\mathbf{w}^T \cdot \mathbf{x} +b= 0
\end{equation}

样本点 $x_i$ 到划分超平面的几何距离为：
\begin{equation}
\gamma_i = \frac{|\mathbf{w} \cdot x_i +b|}{||\mathbf{w}||}
\end{equation}
$||\mathbf{w}||$ 为 $\mathbf{w}$ 的 $L_2$ 范数。

1. 感知机

感知机由两层神经元组成，输入层接受外界输入传递给输出层，输出层是 M-P 神经元，也称“阈值逻辑单元”。感知机模型是寻找线性超平面，将线性可分的样本点正确的分成两类。

记超平面为 $w\mathbf{X}+b=0$，则分类结果为：
\begin{eqnarray}
y = sign(w\mathbf{X}+b)=\begin{cases}
1 &\mbox{$w\mathbf{X}+b > 0$}\
-1 &\mbox{$w\mathbf{X}+b <= 0$}
\end{cases}
\end{eqnarray}

若存在某个点 ${x_i, y_i}$ 的分类结果错误，则 $y_i(w\mathbf{x_i}+b) < 0$，据此可以判断点是否误分类。我们采用误分类点到超平面的距离来衡量分类失败的程度，希望误分类点到超平面的距离越小越好。假设所有的误分类点集合为 $M$，则损失函数为：
\begin{eqnarray}
L(w,b)=\sum_{x_i \in M} \frac{-y_i(wx_i + b)}{||w||}
\end{eqnarray}

不考虑 $||w||$，则损失函数为：
\begin{equation}
L(w,b)=\sum_{x_i \in M} -y_i(wx_i + b)
\end{equation}

不考虑 $||w||$，相当于对超平面方程进行了规范化，可以理解为最终解算的 $w$ 实际上是 $\frac{w}{||w||}$。

最终，问题变成最小化损失函数问题。

由于损失函数里面有限定，只有误分类的 $M$ 集合里面的样本才能参与损失函数的优化，所以不能用最普通的批量梯度下降。感知机采用的是随机梯度下降法，每次仅采用一个误分类点来更新梯度。

损失函数的梯度为：
\begin{eqnarray}
\begin{aligned}
& \nabla_w L(\boldsymbol{w},b) = -\sum_{x_i \in M}y_i x_i\
&\nabla_b L(w,b) = -\sum_{x_i \in M}y_i
\end{aligned}
\end{eqnarray}

由于采用随机梯度法，采用的迭代公式为：
\begin{eqnarray}
\begin{aligned}
&w \leftarrow w + \eta y_i x_i\
&b \leftarrow b + \eta y_i
\end{aligned}
\end{eqnarray}

上式与西瓜书有一定差别，原因在于 $sign$ 函数的定义不一致。

1. 线性判别分析

1.1 二类LDA原理

给定数据集 $D={(\mathbf{x}_i, y_i)}_{i=1}^m,~ y_i \in {0,1}$，令 $\mathbf{X_i}, \mathbf{\mu_i}, \mathbf{\sum_i}$ 表示第 $i \in {0,1}$ 类示例的集合、均值向量和协方差矩阵。若将数据投影到直线 ${\omega}$ 上，则两类样本的中心在直线上的投影分别为 ${\omega}^T \mu_0$ 和 ${\omega}^T \mu_1$，两类样本在直线上投影的协方差为 $\omega^T \mathbf{\sum_0} \omega$ 和 ${\omega}^T \mathbf{\sum_1} \omega$（协方差传播）。

若是同类尽可能近，则协方差尽可能小；异类尽可能远则要求类中心距离大。同时考虑两者，则最大化目标为：

\begin{eqnarray}
J &=& \frac{||{\omega}^T \mu_0-{\omega}^T \mu_1||_2^2}{\omega^T \mathbf{\sum_0} \omega+\omega^T \mathbf{\sum_1} \omega }
\nonumber \
&=& \frac{\omega^T (\mu_0-\mu_1) (\mu_0-\mu_1)^T \omega}{\omega^T (\sum_0 +\sum_1) \omega}
\label{eqn1}
\end{eqnarray}

定义类内散度矩阵和类间散度矩阵为：
\begin{eqnarray}
S_w &=& \sum_0 + \sum_1 \nonumber \
&=& \sum_{x \in \mathbf{X_0}} (x-\mu_0)(x-\mu_0)^T+
\sum_{x \in \mathbf{X_1}} (x-\mu_1)(x-\mu_1)^T \
\nonumber \
S_b &=& (\mu_0-\mu_1) (\mu_0-\mu_1)^T
\end{eqnarray}

带入 ($\ref{eqn1}$) 式：
\begin{eqnarray}
J = \frac{\omega^T S_b \omega}{\omega^T S_w \omega}
\label{eqn4}
\end{eqnarray}

上式就是广义瑞利商，广义瑞利商有个性质为：$J$ 的最大值为矩阵$S_w^{-1}S_b$ 的最大特征值，而对应的 $\omega$ 为 $S_w^{-1}S_b$ 的最大特征值对应的特征向量（特征值最大，意味着在对应的特征向量上的变化最大，分类越大），即：

\begin{eqnarray}
S_w^{-1}S_b \omega = \lambda \omega
\label{eqn5}
\end{eqnarray}

上式就是Fisher Linear Discriminantion 公式，推导过程可参见西瓜书。$S_w^{-1}S_b$ 不一定是对称矩阵，在求它的特征向量时不能使用奇异值分解，这样就只能使用普通的求特征向量的方式。注意到 $S_b \omega = (\mu_0-\mu_1)(\mu_0-\mu_1)^T \omega$，其中 $c = (\mu_0-\mu_1)^T \omega$ 为常数。(\ref{eqn5}) 式可以重写为：
\begin{eqnarray}
\omega = \frac{c}{\lambda}S_w^{-1}(\mu_0-\mu_1)
\end{eqnarray}

注意到 (\ref{eqn4}) 式分子和分母都是关于 $\omega$ 的二次型，因此 (\ref{eqn4}) 式的解与 $\omega$ 的大小无关，至于方向有关。则上式等价于:
\begin{eqnarray}
\omega = S_w^{-1}(\mu_0-\mu_1)
\end{eqnarray}

在实践中，通常对 $S_w$ 进行奇异值分解，求取 $\omega$。

LDA 可从贝叶斯决策理论的角度来阐释，并可证明，当两类数据同先验、满足高斯分布且协方差相等时，LDA 可达到最优分类。

1.2 多类LDA原理

给定数据集 $D={(\mathbf{x}_i, y_i)}_{i=1}^m,~ y_i \in {0,1,…,k}$，类似地，目标函数为：
\begin{eqnarray}
J = \frac{W^T S_b W}{W^T S_w W}
\end{eqnarray}
其中，$W$ 为一个超平面，
\begin{eqnarray}
S_b &=& \sum\limits_{1 \leq i,j \leq k}^{k}(\mu_i-\mu_j)(\mu_i-\mu_j)^T
\nonumber \
S_w &=& \sum\limits_{j=1}^{k}S_{wj} = \sum\limits_{j=1}^{k}\sum\limits_{x \in X_j}(x-\mu_j)(x-\mu_j)^T
\end{eqnarray}

按照上式计算 $S_b$ 较复杂，LDA 采用一个间接的方式。等价？

首先定义X的整体散度矩阵:
\begin{eqnarray}
S_t = S_b + S_w = \sum_{j=1}^k(x_j-\mu)(x_j-\mu)^T
\end{eqnarray}
$\mu$ 是所有示例的均值向量。则：
\begin{eqnarray}
S_b = S_t - S_w = \sum\limits_{j=1}^{k}N_j(\mu_j-\mu)(\mu_j-\mu)^T
\end{eqnarray}
$N_j$ 为第 $j$ 个类别的示例个数。

由于 $W^T S_b W$ 和 $W^T S_w W$ 都是矩阵，无法使用标量的最优化方法，一般来说，常使用的优化目标为：
\begin{eqnarray}
J = \frac{tr(W^T S_b W)}{tr(W^T S_w W)}
\end{eqnarray}

1.3 LDA 分类

对二分类问题。由于只有两个类别，在经过上面的求解后，最后所有样本将会映射到一维空间中，一般将两个类别的中心点之间中心点作为分类点。

对于多类的情况主要考虑用来数据降维，那么降维后的维度是多少呢？
$W$ 是一个利用了样本的类别得到的投影矩阵，是 $S_w^{-1}S_b$ 的特征向量，该特征向量的维数不超过 $S_w^{-1}S_b$ 的秩。
\begin{eqnarray}
R(S_w^{-1}S_b) \leq \min(R(S_w^{-1}), R(S_b)) \leq R(S_b)
\nonumber \
&=& R(\sum\limits_{j=1}^{k}N_j(\mu_j-\mu)(\mu_j-\mu)^T)
\nonumber \
&\leq& \sum\limits_{j=1}^{k}N_j R[(\mu_j-\mu)(\mu_j-\mu)^T]
\nonumber \
&=& \sum\limits_{j=1}^{k} R(\mu_j-\mu)
\end{eqnarray}
由于存在线性组合 $\sum\limits_{j=1}^{k} N_j (\mu_j-\mu) =0 $，故上式的秩最大为 $k-1$，即特征向量最多有 $k-1$ 个。

1. Boosting

Boosting 是一族将弱学习器提升为强学习器的算法。工作机制类似：

1. 从初始训练集中训练出一个基学习器；
2. 根据基学习器的表现调整样本的权值，使得先前基学习器做错的样本权值更大；
3. 然后基于调整之后的权值训练下一个基学习器；
4. 反复学习，得到一系列基学习器，组合这些基学习器。

对于 Boosting 算法来说，关键点在于以下两个问题：

1. 如何改造权值？
2. 如果组合基学习器？

Boosting 族算法最著名的代表是 AdaBoost。

2. AdaBoost 算法

简单来说，AdaBoost 算法就是根据指定参数 $M$，进行 $M$ 轮训练，得到 $M$ 个弱学习器 $G_i$ 及每个弱学习器的权重 $\alpha_i$，最终将这些弱学习器进行线性组合得到最终的学习器 $G$。

给定训练样本集 $\left { (x_i,y_i)\right }_{i=1}^N$，其中 $x_i \in \mathbb{R}^n $ 为特征空间，$y_i \in { -1,+1 }$ 为类标签。 AdaBoost 算法流程如下：

(1). 初始化训练集的权值分布：

\begin{equation}
D_{1}=(w_{11},…,w_{1i},…,w_{1N}),~w_{1i}=\frac{1}{N},~i=1,2,…,N
\end{equation}

(2) 对 $m=1,2,3…,M$:
(2.1) 使用权值分布 $D_m$ 的训练集学习，得到基学习器：
\begin{equation}
G_{m}(x):~X{\rightarrow}{-1,+1}
\end{equation}
(2.2) 计算 $G_{m}(x)$ 在训练集上的误差率：
\begin{equation}
e_{m}=P(G_{m}(x_{i})\neq y_{i}) =\sum_{i=1}^n w_{mi}I(G_{m}(x_{i})\neq y_{i})
\end{equation}
其中，

\begin{equation}
I(G_{m}(x_{i})\neq y_{i}) =
\left{
\begin{array}{ccc}
0,~ G_{m}(x_{i})&=& y_i \
1,~ G_{m}(x_{i})&\neq& y_i
\end{array}
\right.
\end{equation}
(2.3) 计算 $G_{m}(x)$ 的系数：
\begin{equation}
\alpha_{m}=\frac{1}{2}log \frac{1-e_{m}}{e_{m}}
\end{equation}
如图 1 所示，基学习器误差越大，其系数越小。

(2.4) 更新训练集的权值分布：
\begin{equation}
\begin{split}
& D_{m+1}=(w_{m+1,1},…,w_{m+1,i},…,w_{m+1,N}) \\
& w_{m+1,i}= \left{
\begin{array}{ccc}
\frac{w_{mi}}{Z_{m}}~ e^{-\alpha_i},~ G_{m}(x_{i})&=& y_i \
\frac{w_{mi}}{Z_{m}}~ e^{\alpha_i},~ G_{m}(x_{i})&\neq& y_i
\end{array}
\right.
\end{split}
\end{equation}
其中，
\begin{equation}
Z_{m} = \sum_{i=1}^{N}w_{mi}exp(-\alpha_{m}y_{i}G_{m}(x_{i}))
\end{equation}
为归一化因子。

（3） 构建线性分类器的线性组合：

\begin{equation}
f(x)=\sum_{m=1}^{M}\alpha_{m}G_{m}(x)
\end{equation}

得到最终分类器：
\begin{equation}
G(x)=sign(f(x))=sign(\sum_{m=1}^{M}\alpha_{m}G_{m}(x))
\end{equation}

3. AdaBoost 的解释之损失函数优化

上一节提及到了学习器系数和权值更新公式，但是没有解释这个公式的来源，其实它们可以从从损失函数优化问题的角度来解读。

AdaBoost 还有另一个解释，即可以认为 Adaboost 是模型为加法模型，学习算法为前向分步学习算法，损失函数为指数函数的分类问题。

3.1. 加法模型

加法模型 (additive model) 为：
\begin{equation}
f(x) = \sum_{m=1}^M \beta_m b(x; \gamma_m)
\end{equation}
其中，$b(x; \gamma_m)$ 为基函数，$\gamma_m$ 为基函数的参数，$\beta_m$ 为基函数的系数。

很明显，AdaBoost 的最终分类器等价于加法模型。现在的问题是该怎么样得到最终分类器，也就是其中的参数呢？

3.2. 指数损失函数优化

AdaBoost 的损失函数是指数损失函数，即求得的最终分类器：
\begin{equation}
f(x)=\sum_{m=1}^{M}\alpha_{m}G_{m}(x)
\end{equation}
满足最小化指数损失函数：

\begin{equation}
L(y,f(x)) = e^{-yf(x)}
\end{equation}

通常这是一个复杂的优化问题。需要采用前向分布算法来求解。

3.3 前向分布算法

前向分布算法的思想是：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近目标函数，那么就可以简化优化的复杂度。

AdaBoost 第一个基分类器是直接将基学习器算法用于初始训练集得到；此后利用前一个弱学习器的结果，迭代生成权值和基学习器系数，生成后一个弱学习器。第 $m$ 轮的学习器与第 $m-1$ 轮的学习器有如下关系：
\begin{equation}
f_{m}(x) = f_{m-1}(x) + \alpha_m G_m(x)
\end{equation}
目标是每一轮的学习过程中得到 $\alpha_m$ 和 $G_m(x)$，使得 $f_m(x)$ 的指数损失最小，从而最终分类器的指数损失最小。

根据前向分布学习算法的关系，第 $m$ 轮得到的损失函数为：
\begin{equation}
\begin{split}
&arg ~\min_{\alpha_m, G_m} e^{-y f_m{(x)}}\\
&=arg ~\min_{\alpha_m, G_m} e^{-y~(f_{m-1}(x)+\alpha_m G_m(x) )}\\
&=arg ~\min_{\alpha_m, G_m} \sum_{i=1}^N e^{-y_i~(f_{m-1}(x_i)+\alpha_m G_m(x_i) )}
\end{split}
\end{equation}
令 $w_{mi} = e^{-y_i~f_{m-1}(x_i)}$，它的值不依赖于 $\alpha_m$、$G_m(x)$，仅仅依赖于 $f_{m-1}$，随着每一轮迭代而改变。

先求得 $G^*_m(x)$，再上式对 $\alpha_m$ 求导，得到:
\begin{equation} \alpha^*{m}=\frac{1}{2}log \frac{1-e{m}}{e_{m}} \end{equation}
也就是上文的 (5) 式，即学习器系数。

根据 (13) 式和 $w_{mi} = e^{-y_i~f_{m-1}(x_i)}$，有：
\begin{equation} \begin{split} w_{m+1,i}= \left{ \begin{array}{ccc} w_{mi}~ e^{-\alpha_i},~ G_{m}(x_{i})&=& y_i \ w_{mi}~ e^{\alpha_i},~ G_{m}(x_{i})&\neq& y_i \end{array} \right. \end{split} \end{equation}
其与 (6) 式的权值更新公式只差归一化因子，因而等价。

以上，就是 AdaBoost 的另一种解释。

参考资料

[1] 《机器学习》, 周志华

[2] 《统计学习方法》, 李航

1. 随机森林相关知识

随机森林就是通过集成学习的思想将多棵决策树集成的一种算法，它的基本单元是决策树，而它的本质属于机器学习的集成学习方法。

1.1. 集成学习

集成学习是指使用某种规则把多个学习器进行整合来完成学习任务的方法。

举个例子：
假设有三根决策树，它在三个测试样本上的表现如下，正确用 对 表示，错误用 错 表示：

采用投票法规则将三个决策树整合起来，投票法即少数服从多数。集成学习之后的表现为：

上面就是集成学习的一个例子。

1.2. Bagging

为了完成集成学习，需先学习个体学习器，然后按照某种规则将个体学习器整合。对于随机森林来说，其个体学习器为决策树。

为了得到好的集成结果，需要个体学习器尽可能满足两个条件：

• 个体学习器准确；
• 个体学习器之间相互独立。

假设个体学习器为 10 个，对于给定的训练集，分为 10 个互斥的数据子集。根据数据子集训练出 10 个个体学习器，这样得到的个体学习器满足独立的条件。但是，由于数据子集的数据量占比 (10%) 较少，得到的个体学习器很可能不够准确。反之，如果数据子集中包含了训练集中的大量样本，每个个体学习器的训练数据高度相似，得到的个体学习器之间相关性很大。为了解决这个问题，需采样 Bagging 方法。

Bagging 是基于 bootstrap sampling。bootstrap 采样是有放回抽样，如果训练集的大小为 $N$，随机且有放回的从训练集中抽样 $N$ 次，得到一个新的训练集。重复上述过程 $T$ 次，可以得到 $T$ 个训练集，每个训练集的大小为 $N$。然后根据 $T$ 个训练集训练出 $T$ 个个体学习器，再将这些个体学习器整合起来，这就是 Bagging 的基本思想。

2. 随机森林

随机森林是 Bagging 的扩展。除了 bootstarp sampling 抽样过程有随机外，在决策树的生成过程中也存在“随机”。

假设数据训练集的大小为 $N$，随机森林算法中，每颗决策树的生成过程如下：

1. 随机且有放回的从训练集中抽取 $N$ 个样本，形成一个新的训练集，作为该树的训练集；
2. 传统决策树在最优特征选择时，是在当前结点的特征集中选择一个最优特征；而随机森林中，随机地从特征集中选取 $m$ 个特征，每次树进行分裂时，从这 $m$ 个特征中选取最优特征；
3. 每颗树尽量生长且没有剪枝。

通过上述方法生成组成随机森林的每颗决策树，然后采用某规则将这组决策树整合起来，在随机森林中，某规则一般指投票法。

参考资料

[1] 《机器学习》, 周志华

[2] 随机森林（Random Forest）

1. k 近邻概述

k 近邻法是一种常用的监督学习方法。给定一个训练集，其中样本的类别已定。分类时，基于某种距离度量找出训练集中与其最靠近的 k 个训练样本，然后根据这 k 个样本的类别通过多数表决等方式进行预测。k 近邻法不具有显式的训练过程，是懒惰学习 (lazy learning) 的著名代表。其中，关键的内容为距离度量和 k 值的选择。

1.1 距离度量

常用的距离度量有闵可夫斯基距离：

\begin{equation}
L_p(x_i,x_j)=(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p)^{1/p}
\end{equation}

1. $p=2$ 时，欧式距离：
   \begin{equation}
   L_p(x_i,x_j)=(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^2)^{1/2}
   \end{equation}

2. $p=1$ 时，曼哈顿距离：
   \begin{equation}
   L_p(x_i,x_j)=\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|
   \end{equation}

3. $p=\infty$ 时，切比雪夫距离：
   \begin{equation}
   L_p(x_i,x_j)=\max_l |x_i^{(l)}-x_j^{(l)}|
   \end{equation}

1.2. k 值的选择

k 值的选择会对结果产生重大影响。

k 值选择较小，则分类结果容易因为噪声点的干扰而出现错误。换句话说，k 值较小意味模型复杂，容易过拟合。

k 值选择较大，意味着与输入样本较远的训练样本也会对结果起作用，使得预测结果错误。

通常做法是利用交叉验证评估一系列不同的 k 值，选取结果最好的 k 值作为训练参数。

2. kd 树

现在我们有了 k 近邻的思想。对于一个输入样本，我们怎么样选取它的 k 个近邻呢？

最简单的方法就是线性扫描，计算输入样本和训练集中每一个样本的距离。但是当训练样本很大时，这种方法是不可取的。

为了提高 k 个近邻的搜索速度，可以采用特殊的结构存储训练数据，这里介绍 kd 树方法。

2.1. kd 树的构造

kd 树是一种对 k 维空间样本点进行存储的树形数据结构，表示对 k 维空间的划分。构造 kd 树的过程相当于用垂直于某一维度的超平面将 k 维空间切分。

构造平衡 kd 树的过程如下：

1. 在训练集中选择具有最大方差的维度 k，然后在该维度上选择中位数为切分点，对该数据集合进行划分，得到两个子集合，划分的超平面为过切分点且垂直于 k 维度坐标轴的超平面；同时，将落在划分超平面上的样本点保存为根节点。
2. 对两个子集重复 1 步骤，直至所有子集合不能再划分为止；如果某个子集合不能划分，则将该子集合中的数据保存到叶子节点。

图 1 所示为 kd 树构造过程，数据来源于 wikipedia。首先在维度 $X^{(0)}$ 上选取切分点 A，分为两个子集合，并把 A 保存为根节点…………。

2.2. kd 树搜索

假设已经构造了 kd 树，我们有一个新的输入 $x$，搜索它的最近邻。
其算法如下：

1. 在 kd 树中找出包含目标点 $x$ 的叶结点：从根结点出发，递归的向下访问 kd 树。比较当前维上 $x$ 与切分点的坐标，若小移动到左子结点，否则右边，知道叶结点为止；
2. 将到达的叶节点记为“当前最近点”，离目标点的距离为最近距离；

3. 递归向上回溯，在每个结点作如下操作：

   3.1 如果该结点上的样本离目标点更远，向上回溯；
   3.2 如果该结点上的样本距离目标点更近，将该结点标记为当前最近点，更新最近距离；并检查该结点的另一子结点对应的区域是否与以目标点为球心，最近距离为半径的超球体相交。若相交，移动到另一个子节点，向下落到叶节点，递归地进行最近邻搜索。若不相交，向上回溯。

4. 当回退到根节点时，搜索结束。

参考资料

[1] 《机器学习》, 周志华

[2] 《统计学习方法》, 李航

1. 支持向量机

给定训练样本集 $\left { (x_i,y_i)\right }_{i=1}^N$，其中 $x_i \in \mathbb{R}^n $ 为特征空间，$y_i \in { -1,+1 }$ 为类标签。支持向量机是基于划分超平面 (separating hyperplane) 将数据分类的分类器。如图 1 所示，二维数据的线性划分超平面为一条直线。

可以看到，具有多个划分超平面可以将数据分类，我们需要找出唯一的划分超平面，使得划分效果最优，SVM 采用的是最大间隔 (maximum margin) 划分超平面。如图 2 所示。

图 2 中的实心点，刚好处在划分超平面上，这些点确定了划分超平面，称之为支持向量。

上面的例子为线性分类器，即超平面可以用一个线性方程表示：
\begin{equation}
\mathbf{w}^T \cdot \mathbf{x} +b= 0
\end{equation}

对于需要非线性超平面才能分离的数据，SVM 采用核方法，这也是要引入对偶问题最大的原因。

先基于线性可分支持向量机讲述原理，之后说明线性不可分支持向量机，
最后说明非线性支持向量机。

2. 线性可分支持向量机

2.1. 最大间隔超平面

上面提到支持向量机的最优划分标准是最大间隔。在特征空间中，划分超平面可用如下线性方程表示:
\begin{equation}
\mathbf{w}^T \cdot \mathbf{x} +b= 0
\end{equation}
其中 $\mathbf{w}$ 为超平面的法向量，$b$ 为位移项。样本点 $x_i$ 到划分超平面的几何距离为：
\begin{equation}
\gamma_i = \frac{|\mathbf{w} \cdot x_i +b|}{||\mathbf{w}||}
\label{eqn3}
\end{equation}
$||\mathbf{w}||$ 为 $\mathbf{w}$ 的 $L_2$ 范数。
假设超平面能够将训练样本正确分类，即若 $\mathbf{w} \cdot x_i +b >0$，则 $y_i = 1$，反之亦然。所以 (\ref{eqn3}) 式可以去掉绝对值，几何距离重写为：

\begin{equation}
\gamma_i = y_i\frac{\mathbf{w} \cdot x_i +b}{||\mathbf{w}||}
\end{equation}

我们定义训练集中最小的几何距离为几何间隔：
\begin{equation}
\gamma = \min \gamma_i
\end{equation}
最大间隔思想就是最大化几何间隔，在满足所有样本点的几何距离大于几何间隔的条件下：
\begin{equation}
\begin{split}
&\max_{\mathbf{w},b}\gamma \ &s.t. \ \ y_i\frac{\mathbf{w} \cdot x_i +b}{||\mathbf{w}||} \ge \gamma, \ \ i = 1,2,…,N
\end{split}
\label{eqn6}
\end{equation}
为了简化问题，我们引入一个新的定义，函数间隔：
\begin{equation}
\widehat{\gamma} = \frac{\gamma }{||\mathbf{w}||}
\end{equation}
所以，(\ref{eqn6}) 式重写为：

\begin{equation}
\begin{aligned} &\max_{\mathbf{w},b} \frac{\widehat{\gamma }}{||\mathbf{w}||} \ &s.t. \ \ y_i\left ( \mathbf{w}\cdot x_i + b \right ) \ge \widehat{\gamma }, \ \ i = 1,2,…,N \end{aligned}
\label{eqn8}
\end{equation}
可以看到，我们自由缩放函数间隔 $N$ 倍：
\begin{equation}
N ~\widehat{\gamma} = N~ y_i (\mathbf{w} \cdot x_i +b)
\end{equation}
超平面 $\mathbf{w}^T \cdot \mathbf{x} +b= 0$ 与 缩放后的平面 $N~(\mathbf{w}^T \cdot \mathbf{x} +b)= 0$ 相同；几何间隔同样也不会变化。也就是说，任意缩放函数间隔，对于我们最大化几何间隔问题的解算没有影响。为了简化我们的问题，令函数间隔 $\widehat{\gamma}=1$，这也是引入函数间隔的原因。(\ref{eqn8}) 式简化为：

\begin{equation}
\begin{aligned} &\max_{\mathbf{w},b} \frac{ 1 }{||\mathbf{w}||} \ &s.t. \ \ y_i\left ( \mathbf{w}\cdot x_i + b \right ) \ge 1, \ \ i = 1,2,…,N \end{aligned}
\end{equation}

注意到最大化 $\frac{ 1 }{||\mathbf{w}||}$ 等价于最小化 $\frac{ 1 }{2}||\mathbf{w}||^2$，最终，SVM 需要解决的问题为以下有约束的最优化问题，更具体地，该问题为凸二次规划问题：
\begin{equation}
\begin{aligned} &\min_{\mathbf{w},b} \frac{ 1 }{2}||\mathbf{w}||^2 \ &s.t. \ \ y_i\left ( \mathbf{w}\cdot x_i + b \right ) \ge 1, \ \ i = 1,2,…,N \end{aligned}
\label{eqn11}
\end{equation}

2.2. 对偶问题

凸二次规划问题可以使用现成的优化计算包计算，为了引入核函数和方便计算，将原问题转为其对偶问题进行求解。

2.2.1. 原始问题

将原问题 (\ref{eqn11}) 式重写为：
\begin{equation}
\begin{aligned} &\min_{\mathbf{w},b} \frac{ 1 }{2}||\mathbf{w}||^2 \ &s.t. \ \ g(\mathbf{w},b) \le 0 , \ \ i = 1,2,…,N \end{aligned}
\label{eqn12}
\end{equation}
其中 $g(\mathbf{w},b)=1- y_i\left ( \mathbf{w}\cdot x_i + b \right )$。
首先，定义拉格朗日函数为：

\begin{equation}
L(\mathbf{w},b,\alpha) = \frac{1}{2} ||\mathbf{w}||^2 - \sum_{i=1}^N \alpha_i ~g(\mathbf{w},b)
\end{equation}
其中，$\alpha_i \ge 0$。引入 $(\mathbf{w},b)$ 的函数，记为：

\begin{equation}
\theta_p(\mathbf{w},b) = \max_{\alpha} L(\mathbf{w},b,\alpha)
\end{equation}
若上式最大化问题有解，其必满足 (\ref{eqn12}) 式的条件，且其解为：

\begin{equation}
\frac{ 1 }{2}||\mathbf{w}||^2 = \max_{\alpha} L(\mathbf{w},b,\alpha)
\end{equation}
因为 $\alpha_i \ge 0$，需要 $g(\mathbf{w},b) \le 0$ 才能有最大值解。

所以，原问题等价于如下问题：

\begin{equation}
\min_{\mathbf{w},b} \max_{\alpha} L(\mathbf{w},b,\alpha)
\end{equation}

2.2.2 原始问题的对偶问题

记原始问题的对偶问题为：
\begin{equation}
\max_{\alpha} \min_{\mathbf{w},b}L(\mathbf{w},b,\alpha)
\end{equation}
记:
\begin{equation}
\theta_d(\alpha) = \min_{\mathbf{w},b} L(\mathbf{w},b,\alpha)
\end{equation}
我们要通过对偶问题的求解来解决原始问题，那么我们的问题是：对偶问题的解和原始问题的解有什么关系呢？

2.2.3 原始问题与对偶问题的关系

对任意的 $(\mathbf{w},b,\alpha)$，有：

\begin{equation}
\theta_d(\alpha) = \min_{\mathbf{w},b} L(\mathbf{w},b,\alpha) \le L(\mathbf{w},b,\alpha) \le \max_{\alpha} L(\mathbf{w},b,\alpha) = \theta_p(\mathbf{w},b)
\end{equation}

若原始问题和对偶问题都有解，根据上式，有：

\begin{equation}
\begin{split}
&\theta_d(\alpha) \le \theta_p(\mathbf{w},b) \\
&\Rightarrow \max_{\alpha} \theta_d(\alpha) \le \min_{\mathbf{w},b}\theta_p(\mathbf{w},b) \\
&\Rightarrow \max_{\alpha} \min_{\mathbf{w},b}L(\mathbf{w},b,\alpha) \le \min_{\mathbf{w},b} \max_{\alpha} L(\mathbf{w},b,\alpha)
\end{split}
\end{equation}
即对偶问题的解小于或等于原始问题的解。在什么情况下，对偶问题的解与原始问题的解相同呢？如果能找到这个条件，那么我们直接解决对偶问题就可以得到原始问题的解，这个条件就是 KKT (Karush-Kuhn-Tucker) 条件。

KKT 条件为：

\begin{equation}
\begin{split}
\nabla_\mathbf{w} L(\mathbf{w}^*,b^*,\alpha^*) &= 0 \
\nabla_b L(\mathbf{w}^*,b^*,\alpha^*) &= 0 \
\nabla_\alpha L(\mathbf{w}^*,b^*,\alpha^*) &= 0 \
\alpha_i^* ~ g(\mathbf{w}^*,b^*) &= 0, i=1,2,…,N \
g(\mathbf{w}^*,b^*) &\le 0, i=1,2,…,N \
\alpha_i^* &\ge 0, i=1,2,…,N
\end{split}
\end{equation}

如果 $(\mathbf{w}^*,b^*,\alpha^*)$ 满足 KKT 条件，则对偶问题和原始问题的解均为 $(\mathbf{w}^*,b^*,\alpha^*)$。

\begin{equation}
\begin{split}
& \max_\alpha \min_{\mathbf{w},b}L(\mathbf{w},b,\alpha) \
&= \max_{\alpha} L(\mathbf{w}^*,b^*,\alpha) \
& = L(\mathbf{w}^*,b^*,\alpha^*) \
& = \frac{1}{2} ||\mathbf{w^*}||^2 - \sum_{i=1}^N \alpha_i^* ~g(\mathbf{w^*},b^*) \
& = \min_{\mathbf{w},b} \frac{ 1 }{2}||\mathbf{w}||^2 \ \ s.t. \ \ g(\mathbf{w^*},b^*) \le 0 , \ \ i = 1,2,…,N
\end{split}
\end{equation}

所以，SVM 问题转化为 KKT 条件下的对偶问题求解。

2.2.3 对偶问题的求解

为了得到对偶问题的解，需要先求 $L(\mathbf{w},b,\alpha)
$ 对 $(\mathbf{w},b)$ 的极小，再求对 $\alpha$ 的极大。

1. 求$\min \limits_{\mathbf{w},b}L(\mathbf{w},b,\alpha)$
   将 $L(\mathbf{w},b,\alpha)$ 分别对 $\mathbf{w}$，$b$ 求偏导数并令其等于 $0$：
   \begin{equation}
   \begin{aligned} \frac{\partial L(\mathbf{w},b,a)}{\partial \mathbf{w}} &= 0 \Rightarrow \mathbf{w} - \sum_{i=1}^N a_iy_ix_i = 0 \ \frac{\partial L(\mathbf{w},b,a)}{\partial b} &= 0 \Rightarrow - \sum_{i=1}^N a_i~y_i = 0 \end{aligned}
   \end{equation}
   将上式带入拉格朗日函数消去 $\mathbf{w}$，$b$，有：
   \begin{equation}
   \begin{aligned}
   \min_{\mathbf{w},b}L(\mathbf{w},b,\alpha) = \ &-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^Na_i a_jy_iy_j (x_i \cdot x_j) + \sum _{i=1}^Na_i \
   & \ s.t. \ \ \ \sum_{i=1}^N a_iy_i = 0 \end{aligned}
   \end{equation}

2. 求对偶问题
   \begin{equation}
   \begin{aligned} &\max_{a_i} \ -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^Na_i a_jy_iy_j (x_i \cdot x_j) + \sum _{i=1}^Na_i\ & \ s.t. \ \ \ \sum_{i=1}^N a_iy_i = 0 \end{aligned}
   \end{equation}

根据上式，可以求取对偶问题的解 $\alpha^*$，再根据 KKT 的条件求取原始问题的解 $(\mathbf{w}^*,b^*)$，从而可以得到划分超平面，这种算法为对偶学习算法。

对偶问题的解是一个凸二次规划问题，理论上任何一个凸二次规划问题的软件包都可以解决，但是通常很慢，为了能够更快找到好的解，我们采用 SMO 算法。该算法的原理先放一放。

3. 线性不可分支持向量机

上述的问题是基于所有样本点 $(x_i, y_i)$ 都能满足函数间隔大于等于 $1$ 的约束条件，即线性可分的。如果存在异常点不满足约束条件，上面的方法就不适用了。为了解决线性不可分的问题，可以对每个样本引入一个松弛变量 $\xi _i \ge 0$，使得函数间隔加上松弛变量大于等于 $1$，即约束条件变为：
\begin{equation}
y_i(\mathbf{w} \cdot x_i +b) \ge 1 – \xi_i
\end{equation}
显然，$\xi_i$ 不能任意大，否则所有样本点都满足约束条件，为了约束 $\xi_i$ 的大小，需要在目标函数中加入惩罚。最终，优化目标改成如下的形式：

\begin{equation}
\begin{aligned} &\min_{\mathbf{w},b,\xi}\ \ \frac{1}{2}||\mathbf{w}||^2 + C\sum_{i=1}^N \xi_i \ &s.t. \ \ \ \ -y_i(\mathbf{w} \cdot x_i + b) -\xi_i + 1\le 0, \ \ i = 1,2,…,N \ &\ \ \ \ \ \ \ \ \ \ -\xi_i \le 0 ,\ \ i = 1,2,…,N \end{aligned}
\end{equation}
其中，$C > 0$ 称为惩罚参数，一般由应用问题决定，$C$ 值越大对误分类的惩罚越大。

同样地，线性不可分支持向量机的学习问题也是凸二次规划问题，我们采用与线性可分支持向量机同样的方法，即：

1. 构造拉格朗日函数；
2. 原始问题转化为对偶问题；
3. 利用 KKT 条件消去其他参数，得到只包含参数 $a_i$ 的对偶问题；
4. 利用 SMO 算法解释出 $a_i$；
5. 根据 KKT 条件和 $a_i$ 解算出 $\mathbf{w}~,b,$。

这里给出对偶问题的具体形式：
\begin{equation}
\begin{aligned} &\min_a \ \ \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N a_ia_jy_iy_j(x_i \cdot x_j) - \sum_{i=1}^Na_i \ &s.t. \ \ \ \ \ 0 \le a_i \le C , \ i = 1,2,…,N\ & \ \ \ \ \ \ \ \ \ \sum_{i=1}^Na_iy_i = 0,\ i = 1,2,…,N \end{aligned}
\end{equation}

可以看到，线性可分支持向量机可以认为是松弛变量等于$0$，也就是上式的特例。线性可分和线性不可分支持向量机合称为线性支持向量机。至此，上式就是线性支持向量机待学习的问题。

4. 线性支持向量机算法

1. 构造约束最优化问题：
   \begin{aligned} &\min_a \ \ \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N a_ia_jy_iy_j(x_i \cdot x_j) - \sum_{i=1}^Na_i \ &s.t. \ \ \ \ \ 0 \le a_i \le C , \ i = 1,2,…,N\ & \ \ \ \ \ \ \ \ \ \sum_{i=1}^Na_iy_i = 0,\ i = 1,2,…,N \end{aligned}

2. 采用 SMO 算法求解 $a_, ~i = 1,2,….N$；

3. 根据 KKT 条件和 $a_i^*$ 解算出 $\mathbf{w}^*~,b^*,$。
   \begin{aligned}
   &\mathbf{w}^* = \sum_{i=1}^Na_i^*y_ix_i\ &b^* = y_j - \sum_{i=1}^N y_ia_i^*(x_i \cdot x_j) \\
   &0 < a^*_j < C
   \end{aligned}

4. 得到超平面 $\mathbf{w}^* \cdot x + b^* = 0$。对于需要分类的数据，根据 $f(x) = sign(\mathbf{w}^* \cdot x+b^*)$ 判断其类别，其中 $sign$ 为相应的决策函数。

5. 非线性支持向量机

对于给定的非线性可分数据集 $\left { (x_i,y_i)\right }_{i=1}^N$，找不到一个分类平面将数据集分类。自然的想法就是将数据映射到新的空间 $\mathbf{x} \rightarrow \phi(\mathbf{x})$，使得其在新的空间中存在分类平面 $\mathbf{w}^T \cdot \phi(\mathbf{x}) +b= 0$，将其分类。如图 3 所示。

通常来说，非线性 SVM 不显式地定义映射函数 $\phi(\mathbf{x})$，而是采用核技巧，原因下面讲。

5.1. 核技巧

针对非线性可分数据集，假设找到了映射函数 $\phi(\mathbf{x})$，使其线性可分。与线性支持向量机推导一样，约束最优化问题为：

\begin{equation}
\begin{aligned} &\min_a \ \ \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N a_ia_jy_iy_j\color{red}{(\phi{(x_i)}^T \cdot \phi{(x_j)})}- \sum_{i=1}^Na_i \ &s.t. \ \ \ \ \ 0 \le a_i \le C , \ i = 1,2,…,N\ & \ \ \ \ \ \ \ \ \ \sum_{i=1}^Na_iy_i = 0,\ i = 1,2,…,N \end{aligned}
\end{equation}
可以看到，上式的优化问题需要计算 $K(x_i,x_j)= \phi{(x_i)}^T \cdot \phi{(x_j)}$，我们称 $K(x_i,x_j)$ 为核函数。因为特征空间通常很高维，甚至是无穷维，映射函数的内积 $\phi{(x_i)}^T \cdot \phi{(x_j)}$ 并不容易计算。为了避开这个障碍，特征空间的內积用核函数 $K(,)$ 来代替，从而避免高维中的內积。所以，不需要定义映射函数 $\phi{\mathbf{x}}$，只需要定义核函数，这便是核技巧。核技巧的好处在于不需要显式定义映射函数，只需要选择合适的核函数。此外，值得说明的是，正是对偶问题的引入，才能使得应用核技巧。

5.2. 核函数

显然，若已知映射函数，则可写出核函数。但是现实任务中我们通常不知道映射函数是什么样的形式。那么，什么样的函数 $K(,)$ 可以作为一个有效的核函数呢？答案是只要 $K(,)$ 满足 Mercer 定理即可。这里不再展开叙述。

定义了核函数，实际上就定义了一个新的特征空间，这个新的特征空间称之为再生核希尔伯特空间。需要注意的是，在不知道特征映射的形式时，我们并不知道什么样的核函数是合适的，而核函数也仅是隐式的定义了新的特征空间。于是，核函数的选用成为了非线性支持向量机的最大变数。若核函数选择不合适，则意味着数据映射到了一个不合适的特征空间，很可能会导致分类效果不佳。

显然，判断一个函数是否可以当成核函数或者判断一个核函数是否适合是很困难的。这里给出一些常用的核函数。

1. 线性核
   \begin{equation*}
   K(x_i,x_j) = x_i^T~x_j +c
   \end{equation*}

2. 多项式核
   \begin{equation*}
   K(x_i,x_j) = (x_i^T~x_j +c)^d
   \end{equation*}

3. 高斯核
   \begin{equation*}
   K(x_i,x_j) = exp(\frac{-||x_i-x_j||^2}{2\sigma^2})
   \end{equation*}

4. 拉普拉斯核
   \begin{equation*}
   K(x_i,x_j) = exp(\frac{-||x_i-x_j||}{\sigma})
   \end{equation*}
   此外，也可通过函数组合得到。

参考资料

[1] 《机器学习》, 周志华

[2] 《统计学习方法》, 李航

[3] 《Convex Optimization》, Stephen Boyd and Lieven Vandenberghe