3. 经典机器学习方法¶

大量经典机器学习算法，如支持向量机(Support Vector Machine，SVM), K最近邻(K-Nearest Neighbor, KNN)分类算法和K均值聚类算法(K-Means Clustering Algorithm)等，虽然它们有的有网络参数，有的没有网络参数，有的是监督学习算法，有的是无监督学习算法，训练过程也不一样，但是从系统的角度，它们都是以矩阵运算为基础的。下面，我们来简要介绍一下这些算法。

3.1. 支持向量机¶

支持向量机(Support Vector Machine，SVM)，是一种经典的机器学习分类算法，其核心思想在于最大化决策边界到数据点的距离。在这里，我们以线性可分数据为例；对于非线性可分的数据，运用核方法(Kernel Method)即可类似处理。

如果训练数据是线性可分的，SVM的目标则是最大化间隔(Margin)。首先，我们先来定义最大化间隔的分类器，如下：

(3.1.1)¶\[\min_{{w},b} ~~~\frac{1}{2} ||{w}||^2\]

(3.1.2)¶\[s.t. ~~~y_i ({w}^T {x_i} + b) \geq 1, ~~~\forall 1 \leq i \leq n\]

其拉格朗日乘子为

(3.1.3)¶\[L({w},b,{\lambda}) = \frac{1}{2} ||{w}||^2 + \sum_{i=1}^n \lambda_i (1-y_i({w}^T {x_i} + b))\]

由于\(\frac{1}{2} ||{w}||^2\)是凸的，并且\(\lambda_i (1-y_i({w}^T {x_i} + b))\)是线性的（也是凸的），所以优化问题的解为

(3.1.4)¶\[\max_{\lambda>0} \min_{{w},b} L({w},b, {\lambda})\]

求\(L\)关于\({w},b\)的导数有

(3.1.5)¶\[\nabla_{{w}} L= {w} - \sum_{i=1}^n \lambda_i y_i {x_i}\]

(3.1.6)¶\[\nabla_b L = - \sum_{i=1}^n \lambda_i y_i\]

令\(L\)关于\({w},b\)的导数均为0得到，\({w}^* = \sum_{i=1}^n \lambda_i y_i {x_i}\)以及\(\sum_{i=1}^n \lambda_i y_i = 0\)。由于当\(\lambda\)固定的时候，\(b\)的值对目标函数无贡献，所以可以令\(b^* = 0\)。这时，由对偶性理论和KTT条件，我们得到：

(3.1.7)¶\[y_i ({w}^{*T} {x_i} + b^*) > 1 \Rightarrow \lambda_i^* = 0\]

(3.1.8)¶\[\lambda_i^* > 0 \Rightarrow y_i ({w}^{*T} {x_i} + b^*) = 1\]

(3.1.9)¶\[{w}^* = \sum_{i=1}^n \lambda_i^* y_i {x_i}\]

如果\(y_i ({w}^{*T} {x_i} + b^*) = 1\)，那么\({x_i}\)就是离超平面\(({w}^*,b^*)\)最近的点之一，否则就不是。因此，\({w}^*\)就是离超平面\(({w}^*,b^*)\)最近的点\({x_i}\)的线性组合。

如此，通过SVM算法，我们实现了数据的分类，并且能够最大化了决策边界到最近点的距离。我们定义满足\(y_i ({w}^{*T} {x_i} + b^*) = 1\)的\({x_i}\)为支持向量(Support Vectors)，同时把分类器\(\hat{y}=sgn({w}^{*T} {x_i} + b^*)\)称为支持向量机。

3.2. K最近邻算法¶

K最近邻算法(K-Nearest Neighbor，KNN)也是一种传统的机器学习算法，可用于分类、回归等基本的机器学习任务。和上面介绍的SVM算法不同，K最近邻算法的核心思想并不是用一个决策边界把属于不同类的数据分开，而是依靠每个数据点周围几个距离最近的数据的性质，来预测数据点本身的性质。

KNN用于分类时，为了预测某个样本点的类别，会进行一次投票。投票的对象为离这个观测样本点最近的K个样本点，每个要投票的样本点可能会被赋予不同的权重，而投票的“内容”则是样本点的类别。处理投票结果的时候，采用的是少数服从多数的决策方法(Majority Vote)。也就是说，若一个样本点最近的K个样本点中大多数属于某个类别，那么该样本点也属于这个类别。

KNN算法的具体描述如下：（1）计算待分类点到各已知类别点的距离；（2）将这些点按照距离排序，并按照距离挑选出最近的K个点；（3）按照每个点的权重进行“统票”，票面内容为点所处的类别；（4）返回得票最高的类别，并作为待分类点的预测类别。

KNN算法有几个需要注意的关键问题，包括超参数K的选择，距离的度量方式，还有分类决策规则。对于超参数K，不宜过大，否则会导致很大的近似误差，反之亦不宜过小，否则会导致很大的估计误差。距离的度量，则可以选择曼哈顿距离、欧式距离和闵可夫斯基距离等等。为了降低K值对于预测结果产生的误差和影响，我们通常可以对分类决策规则做一定的规定，比如在投票决策时让距离小的点有更大的权重，距离较大的点权重较小。在编程实现KNN算法的时候，权重等参数都会以矩阵的形式进行运算，以提高运算效率。

3.3. K均值聚类算法¶

K均值聚类算法(K-Means Clustering Algorithm)是机器学习中一种常见的无监督聚类算法。在这里，我们首先定义聚类问题：给定数据点\({x_1},\cdots, {x_n} \in \mathbb{R}^d\)和\(K\in \mathbb{N}\)，需要划分为\(K\)个簇\({C_1}, \cdots, {C_K} \in \mathbb{R}^d\)以及每个数据点所对应的分类中心点\({ C_{(1)}}, \cdots, {C_{(n)}}\)，以最小化距离和\(\sum_i ||{x_i} - {C_{(i)}}||^2\)。

K均值聚类算法是一种解决聚类问题的算法，算法过程如下：

随机选择\({C_1}, \cdots, {C_K}\)
把\({x_i}\)所对应的分类置为距离其最近的聚类中心点的分类
计算并赋值\({C_K} = \frac{\sum_{{C_{(i)}}={C_K}} {x_i}}{\sum_{{C_{(i)}}={C_K}} 1}\)
重复以上步骤直到算法收敛

可以证明，K均值聚类算法会使得距离和\(\sum_i ||{x_i} - {C_{(i)}}||^2\)不断地单调减小，并且最终能够收敛。不过，算法可能收敛到局部最小值。

本章结束语：

在系统角度，机器学习的算法无论是什么算法，涉及到高维数据任务的现都是矩阵运算实现的。

4. 参考文献¶

Duchi et al., 2011: Duchi, J., Hazan, E., & Singer, Y. (2011). Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research (JMLR), 12(Jul), 2121–2159.
He et al., 2016: He, K., Zhang, X., Ren, S., & Sun, J. (2016). Deep Residual Learning for Image Recognition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
Hochreiter et al., 1997: Hochreiter, S., Hochreiter, S., Schmidhuber, J., & Schmidhuber, J. (1997). Long Short-Term Memory. Neural Computation, 9(8), 1735–80.
Kingma & Ba, 2014: Kingma, D., & Ba, J. (2014). Adam: a method for stochastic optimization. Proceedings of the International Conference on Learning Representations (ICLR).
Krizhevsky et al., 2012: Krizhevsky, A., Sutskever, I., & Hinton, G. E. (2012). Imagenet classification with deep convolutional neural networks. Advances in Neural Information Processing Systems (pp. 1097–1105).
LeCun et al., 2015: LeCun, Y., Bengio, Y., & Hinton, G. (2015). Deep learning. Nature, 521(7553), 436.
LeCun et al., 1989: LeCun, Y., Boser, B., Denker, J. S., Henderson, D., Howard, R. E., Hubbard, W., & Jackel, L. D. (1989). Backpropagation applied to handwritten zip code recognition. Neural computation, 1(4), 541–551.
Rosenblatt, 1958: Rosenblatt, F. (1958). The perceptron: a probabilistic model for information storage and organization in the brain. Psychological Review, 65(6), 386.
Rumelhart et al., 1986: Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986). Learning representations by back-propagating errors. Nature, 323(6088), 533.
Tieleman & Hinton, 2017: Tieleman, T., & Hinton, G. (2017). Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning. Technical Report.
Vaswani et al., 2017: Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., … Polosukhin, I. (2017). Attention is all you need. Advances in Neural Information Processing Systems (pp. 5998–6008).