机器学习笔记

线性回归、逻辑斯蒂回归、支持向量机、神经网络、异常检测和主成分分析参照Andrew Ng主讲课程《机器学习》

线性回归

单变量回归

损失函数为
$\begin{equation*} J(\pmb{\theta}) = \frac{1}{2m} \sum_{i=1}^m (h_{\pmb{\theta}}(X^i) - y^i)^2 \end{equation*}$

其中 $X_i$ 为二维向量（第一维值为1，是常数项），而 $\pmb{\theta} = (\theta_0, \theta_1)^T$ ，损失函数关于参数值的梯度如下
$\begin{equation*} \frac{\partial J}{\partial \theta_j} = \frac{1}{m} \sum_{i=1}^m (h_{\pmb{\theta}}(X^i) - y^i) * X_j^i \end{equation*}$

用矩阵形式表示为
$\begin{equation*} \pmb{h} = X * \pmb{\theta} \\ J(\pmb{\theta}) = \frac{1}{m} (\pmb{h} - \pmb{y})^T * (\pmb{h} - \pmb{y}) \\ \frac{\partial J}{\partial \pmb{\theta}} = \frac{1}{m} X^T * (\pmb{h} - \pmb{y}) = \frac{1}{m} \left( X^T X \pmb{\theta} - X^T \pmb{y} \right) \end{equation*}$

多变量回归

计算公式

同单变量回归。在确定最优参数 $\pmb{\theta}$ 的过程中可以采用梯度更新的方法，也可以直接计算其值。
$\begin{equation*} \pmb{\theta} = \left( X^T X \right)^{-1} X^T \pmb{y} \end{equation*}$
其中 $X$ 为 $m \times (n+1)$ (n为输入特征数目)，矩阵，当 $m < n+1$ 时， $X^T X$ 一定不是满秩矩阵，不可逆，此时可能有多个局部最优解。
标准化

使用梯度更新求参数最优值时可以先标准化以减少收敛所需迭代次数。除常数项外，对于每一个特征标准化
$\begin{equation*} x = \frac{x - \mu}{s} = \frac{x - \frac{1}{m} \sum_{i=1}^m x_m}{\sqrt{\frac{\sum_{i=1}^m (x_i - \frac{1}{m} \sum_{i=1}^m x_m)^2}{m-1}}} \end{equation*}$

如果对训练集应用标准化，验证集和待预测变量应该以相同的均值和标准差应用标准化。

直接计算梯度最优值时不需要标准化。
正则化 (Regularization)

当输入特征过多时，模型容易过拟合。此时可以通过正则化限制参数 $\pmb{\theta}$ 的大小，也就是
$\begin{equation*} \pmb{h} = X * \pmb{\theta} \\ J(\pmb{\theta}) = \frac{1}{m} (\pmb{h} - \pmb{y})^T * (\pmb{h} - \pmb{y}) + \frac{\lambda}{2m} \left( \pmb{\theta}^T \pmb{\theta} - \theta_0^2 \right) \\ \frac{\partial J}{\partial \pmb{\theta}} = \frac{1}{m} \left[ X^T * (\pmb{h} - \pmb{y}) + \lambda (\pmb{\theta} - \theta_0 * \pmb{e}) \right] = \frac{1}{m} \left[ (X^T X + * \lambda L) \pmb{\theta} - X^T \pmb{y} \right] \end{equation*}$

其中
$$
\begin{equation*}
L =
\begin{bmatrix}
0 & 0 & \cdot & \cdot & \cdot & 0 \
0 & 1 & \cdot & \cdot & \cdot & 0 \
\cdot & \cdot & \cdot & & & \cdot \
\cdot & \cdot & & \cdot & & \cdot \
\cdot & \cdot & & & \cdot & \cdot \
0 & 0 & \cdot & \cdot & \cdot & 1 \
```
 \end{bmatrix}
```
\end{equation*}
$$

最优化的参数值为
$\begin{equation*} \pmb{\theta} = \left( X^T X + \lambda L \right)^{-1} X^T \pmb{y} \end{equation*}$

可以证明 $X^T X + \lambda L$ 一定是满秩矩阵。证明如下：

假设其不是满秩矩阵，则 $\exists \pmb{x} \neq \pmb{0}, s.t. (X^T X + \lambda L) \pmb{x} =\pmb{0}$ ，那么 $\pmb{x}^T (X^T X + \lambda L) \pmb{x} = \pmb{x}^T X^T X \pmb{x} + \lambda \pmb{x}^T L \pmb{x} = 0.$

假设 $x_1 = 0$ ，则 $\exists j \in [2, n+1], s.t. x_j \neq 0$ ，那么当 $\lambda > 0$ 将有 $\lambda \pmb{x}^T L \pmb{x} > 0.$

假设 $x_1 \neq 0$ ，由于 $X_{1,1} = 1.0 > 0$ ，必有 $\pmb{x}^T X^T X \pmb{x} = (X \pmb{x})^T X \pmb{x} > 0.$

因此无论对于哪种情况都不会有 $\pmb{x}^T (X^T X + \lambda L) \pmb{x} = 0.$ ，与前面结论矛盾， $X^T X + \lambda L$ 一定是满秩矩阵。

Logistic回归

Logistic回归是一个线性分类方法，将权重与变量相乘通过激活函数后判断目标类别，其损失函数为对数似然函数
$\begin{align*} \begin{split} J(\pmb{\theta}) &= - \frac{1}{m} \sum_{i=1}^m \left[ y^i \log(h_{\pmb{\theta}}(x^i)) + (1 - y^i) \log(1 - h_{\pmb{\theta}}(x^i)) \right] + \frac{\lambda}{2m} \sum_{j=1}^n \theta_j^2 \\ &= -\frac{1}{m} \left[ \pmb{y}^T \log(\pmb{h}) + (1-\pmb{y}^T) \log(1-\pmb{h}) \right] + \frac{\lambda}{2m} \left( \pmb{\theta}^T \pmb{\theta} - \theta_0^2 \right) \end{split} \end{align*}$

其中 $h_{\pmb{\theta}}(\pmb{x}) = \sigma(\theta_0 + \theta_1 * x_1 + ... + \theta_n * x_n)$ ， $\sigma(z) = \frac{1}{1 + \exp(-z)}$

损失函数关于参数的导数为
$\begin{equation*} \frac{\partial J}{\partial \pmb{\theta}} = \frac{1}{m} \left[ X^T * (\pmb{h} - \pmb{y}) + \lambda (\pmb{\theta} - \theta_0 * \pmb{e}) \right] = \frac{1}{m} \left[ (X^T X + \lambda L) \pmb{\theta} - X^T \pmb{y} \right] \end{equation*}$

参数较多时可以使用梯度更新，可以调用MATLAB的无约束优化函数fminunc

options = optimset('GradObj', 'on', 'max_iter', 400);  % cost_function的返回值为[J, grad], 可直接使用返回的梯度值，同时设置最大迭代次数为400.
[theta, cost] = fminunc(@(t)cost_function(t, X, y, lambda), theta_0, options);

One vs All

对于多变量的Logistic回归，应该对每一个类别训练一组参数，预测时分别对每一个类别计算似然估计，取值最大的一个类别，此时参数 $\theta$ 的维度为 $(n+1) \times k$ ，其中 $k$ 为类别数目。

神经网络

Forward-Propagation

设输入层为第1层，输出层为第L层 (最后一层)

输入层

设输入向量 $a^1 = X$ 的维度为 $m \times C$ ，其中 $m$ 为样本数目， $C$ 为特征数目，令 $x^2 = (\pmb{e}, a^1)$ ，其维度为 $m \times (C+1)$ ，前向传播为 $z^2 = x^2 \times \left( \Theta^2 \right)^T$
输出层

对于输出层的 $z^L$ ，计算损失函数为
$\begin{equation*} J(\pmb{\Theta}) = -\frac{1}{m} \sum_{i=1}^m \sum_{k=1}^K \left[ y_k^i \log(\sigma(z_{ik}^L)) + (1-y_k^L) \log(1-\sigma(z_{ik}^L)) \right] + \frac{1}{2m} \sum_{l=2}^L ||\Theta^L||^2 \end{equation*}$
隐层

对于每一个隐层 $l$ ，前面一层的输出与 $\Theta_{l-1}^T$ 相乘，以sigmoid激活函数为例
$\begin{equation*} z^{l} = x^l * (\Theta^l)^T \\ a^{l} = \sigma(z^{l}) \end{equation*}$
而 $x^{l+1}$ 在 $a^{l}$ 加上一个常数偏置项，使得其维度为 $m \times (C^l + 1)$ ，因此 $\Theta^{l+1}$ 的维度应该为 $C^{l+1} \times (C^L + 1)$ 。

Backward-Propagation

以sigmoid激活函数为例

输出层

假设采用对数似然损失函数。
$\begin{equation*} \delta^L = \frac{\partial J}{\partial z^L} = a^L \odot (1-a^L) \odot \frac{\partial J}{\partial a^L} = \frac{1}{m} \left( a_L - y \right) \end{equation*}$
隐层
$\begin{equation*} \delta^l = \frac{\partial J}{\partial z^l} = a^l \odot (1-a^l) \odot \frac{\partial J}{\partial a^l} \end{equation*}$

而 $\frac{\partial J}{\partial x^{l+1}} = \delta^{l+1} \times \Theta^{l+1}, x^{l+1} = (\pmb{e}, a^l)$

由于损失函数中有正则化项
$\begin{equation*} \frac{\partial J}{\partial \Theta^l} = (\delta^l)^T \cdot x^l + \frac{\lambda}{m} \Theta_l \cdot A \end{equation*}$

其中
$$
\begin{equation*}
A =
\begin{bmatrix}
0 & 0 & \cdot & \cdot & \cdot & 0 \
0 & 1 & \cdot & \cdot & \cdot & 0 \
\cdot & \cdot & \cdot & & & \cdot \
\cdot & \cdot & & \cdot & & \cdot \
\cdot & \cdot & & & \cdot & \cdot \
0 & 0 & \cdot & \cdot & \cdot & 1 \
```
 \end{bmatrix}
```
\end{equation*}
$$

模型评估与选择

数据集划分

通常我们会将数据集划分为训练集和测试集，训练集用于训练模型而测试集用于评估模型，并选择在测试集上表现最好的模型。但是实际上，我们不能完全确定该模型在训练集和测试集以外的数据上的泛化能力。为了应对这个问题，可以将数据集划分为三部分：训练集（Training set, 用于训练模型）、验证集（Validation set, 用于选择模型）和测试集（Test set, 最终评估模型）。假设训练得到K个模型，其中第i个在验证集上表现最好，则最终选取该模型。这样，相当于验证集已经对模型经过更进一轮的选择，因此模型在其上的表现往往好于测试集。

Bias-Variance

当训练数据较少，而模型参数（对应于选取特征数量）较多时容易出现过拟合，此时表现为训练集误差小，而验证集误差大，这种情况称为high variance，解决方法是尝试采用更多的训练数据，减少特征数目或者应用正则化。

当模型在训练集和验证集的误差都较大时，这种情况为欠拟合，称为high bias，此时采用更多的训练数据往往不能提升模型效果，应该尝试采用更多的特征，或者减小正则化项系数。

学习曲线和交叉验证曲线

尝试使用不同的训练集规模训练数据，可以对学习算法进行调试。比较不同模型的效果时，计算其在训练集和验证集上的误差，需要注意的是这个误差不等于损失函数，不应该加上正则化项。

采用交叉验证曲线可以对不同结构的模型和参数进行选择。例如，在单变量回归时，若直接采用线性回归，模型效果可能不太好，此时可以尝试采用多项式回归，可以用不同的多项式次数和不同的正则化项参数等进行交叉验证，选取在验证集上效果最好的组合。

处理不均衡数据

对于分类问题来说，如果在数据集中一个类别的比例很高而其他类别的比例很低，此时即使总体的预测错误率较低，对于少数样本的类别其错误率可能很高，这样不能仅仅依靠简单的损失函数或者总体的准确率来评估模型。引入评价指标召回率和精确率，（对于二分类）假阳率（预测为阳性样本中实际阴性样本比例）、假阴率（预测为阴性样本中实际阳性样本比例）等指标。以二分类为例
$\begin{equation*} 阳性召回率 = \frac{真阳数}{真阳数+假阴数}, Recall = \frac{TP}{TP+FN} \\ 阳性精确率 = \frac{真阳数}{真阳数+假阳数}, Precision = \frac{TP}{TP+FP} \end{equation*}$

多分类对于每个类别的召回率和精确率与上式类似。

一般来说，对于某个类别，召回率越高和精确率越低。为了提高精确率可以提高预测为该类别的阈值（比如将sigmoid损失函数值的阈值从0.5提高到0.7），反之为了提高召回率可以降低其阈值。根据精确率(Precision)和召回率(Recall)的关系可以绘制出P-R曲线，曲线的积分称为AUC(area under curve)，可以作为评价模型整体性能的一个依据。也可以采用F-score来评判，其计算公式为
$\begin{equation*} F-score = (1+\beta^2) \frac{precision * recall}{\beta^2 \cdot precision + recall} \end{equation*}$

另一种评价方法是ROC (Receiver Operating Characteristics) 曲线，其横坐标和纵坐标分别为FPR和TPR，其中
$\begin{equation*} FPR = \frac{FP}{TN+FP} \\ TPR = \frac{TP}{TP+FN} \end{equation*}$
FPR可以视为 $1-阴性样本召回率$ ，TPR可以视为阳性样本召回率，这两者是正相关关系。

支持向量机

数学推导

最大化分类间隔

在空间中，为了将正负样本区分开，可以令正负样本分别满足( $x_0$ 为常数项1)
$\begin{equation*} \pmb{\theta}^T \pmb{x}_{pos} \geq 1 \\ \pmb{\theta}^T \pmb{x}_{neg} \leq -1 \end{equation*}$

也就是
$d_i\pmb{\theta}^T \pmb{x}-1 \geq 0$
其中
$\begin{equation*} d_i = \left\{ \begin{array}{l} 1 \;\;\;\; if \; y_i = 1 \\ -1 \; otherwise \end{array} \right. \end{equation*}$

令 $\pmb{w} = (\theta_1, \theta_2, ..., \theta^n)^T$ ，正负支持向量之间的间隔为
$\frac{\pmb{w}^T (\pmb{x^*}_{pos} - \pmb{x^*}_{neg})}{\Vert \pmb{w} \Vert} = \frac{2}{\Vert \pmb{w} \Vert}$

最小化 $\Vert \pmb{w} \Vert$ 的值即最大化分类间隔，目标函数设为 $\frac{1}{2} \pmb{w}^T \pmb{w} = \frac{1}{2} \sum_{j=1}^n \theta_j^2$ ，非线性约束可用Lagrange乘子法，令
$L(\pmb{\theta}, \pmb{\alpha}) = \frac{1}{2} \pmb{\theta}^T A \pmb{\theta} - \sum_{i=1}^m \alpha_i \left( d_i\pmb{\theta}^T \pmb{x}-1 \right)$

求解 $\max \, \min \, L$ ，应用KKT定理，函数取得极值时有
$\begin{equation*} \frac{\partial L}{\partial \pmb{\theta}} = 0 \; \to \; A \cdot \pmb{\theta} = A \sum_{i=1}^m \alpha_i d_i \pmb{x}_i \end{equation*}$

其中
$\begin{equation*} A = \begin{bmatrix} 0 & 0 & \cdot & \cdot & \cdot & 0 \\ 0 & 1 & \cdot & \cdot & \cdot & 0 \\ \cdot & \cdot & \cdot & & & \cdot \\ \cdot & \cdot & & \cdot & & \cdot \\ \cdot & \cdot & & & \cdot & \cdot \\ 0 & 0 & \cdot & \cdot & \cdot & 1 \\ \end{bmatrix} \end{equation*}$

代入函数可得
$\min \, L(\pmb{\theta}, \pmb{\alpha}) = Q(\pmb{\alpha}) = \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j d_i d_j \pmb{x}_i^T \pmb{x}_j$

引入松弛系数

对于空间中不完全线性可分问题，可以对于每一个样本引入一个松弛系数 $\xi$ ，允许一部分样本不位于正确的区域。
对于每个样本，
$d_i\pmb{\theta}^T \pmb{x} - 1 + \xi_i \geq 0$
其中 $\xi_i \geq 0$ 。设 $C$ 为松弛惩罚系数，则最小化目标函数可以设为 $\sum_{j=1}^n \theta_j^2 + C \sum_{i=1}^m \xi_i$ ，对应Lagrange函数为
$L(\pmb{\theta}, \pmb{\xi}, \pmb{\alpha}, \pmb{\mu}) = \frac{1}{2} \pmb{\theta}^T A \pmb{\theta} + C \sum_{i=1}^m \xi_i - \sum_{i=1}^m \alpha_i \left( d_i\pmb{\theta}^T \pmb{x} -1 + \xi_i \right) - \sum_{i=1}^m \mu_i \xi_i$

应用KKT定理
$\left\{ \begin{array}{l} \frac{\partial L}{\partial \pmb{\theta}} = \pmb{0} \; \to \; A \cdot \pmb{\theta} = A \sum_{i=1}^m \alpha_i d_i \pmb{x}_i \\ \frac{\partial L}{\partial \pmb{\xi}} = \pmb{0} \, \to \, C - \pmb{\mu} - \pmb{\alpha} = \pmb{0} \\ \mu_i \xi_i = 0, \, \mu_i \geq 0, \; i=1,2,...,m \\ \alpha_i \left( d_i\pmb{\theta}^T \pmb{x}-1 + \xi_i \right) = 0, \, \alpha_i \geq 0, \; i=1,2,...,m \end{array} \right.$

最终得到的 $Q(\pmb{\alpha})$ 与1中相同。且当样本点 $x_i$ 分别位于分类平面，平面之间和平面之外时
$\left\{ \begin{array}{l} d_i\pmb{\theta}^T \pmb{x} = 1, \; 0 < \alpha_i < C \; (\mu_i > 0) \\ d_i\pmb{\theta}^T \pmb{x} \geq 1, \; \alpha_i = 0 \\ d_i\pmb{\theta}^T \pmb{x} \leq 1, \; \alpha_i = C \; (\mu_i = 0) \end{array} \right.$

选取一个 $\alpha_j \; s.t. 0 < \alpha_j < C$ ，则 $d_j \pmb{\theta}_j \pmb{x}_j = 0$ ，可以求得 $\theta_0$ .

求解 $\max \, Q(\pmb{\alpha})$

$Q(\pmb{\alpha})$ 的优化问题是原优化问题的对偶。由于 $\alpha$ 参数过多，求解时可以采用SMO算法。
优化问题：
$\begin{equation*} \max Q(\pmb{\alpha}) = \sum_{i=1}^m \alpha_i - \frac{1}{2} \alpha_i \alpha_j y_i y_j \pmb{x}_i^T \pmb{x}_j \\ s.t. \left\{ \begin{array}{l} 0 \leq \alpha_i \leq C \;\; i = 1, 2, ... , m \\ A \pmb{\theta} = A \sum_{i=1}^m \alpha_i d_i \pmb{x}_i \end{array} \right. \end{equation*}$

由于优化变量众多，John Platt在1998年提出SMO算法，可以高效地求解上述问题的最优解。SMO算法每次选取两个变量，固定其他变量，求这两个变量的最优解，设选取的两个变量为 $\alpha_1$ 和 $\alpha_2$ 。为了保证原问题的约束条件成立，应有
$\alpha_1 d_1 + \alpha_2 d_2 = \alpha_{1,0} d_1 + \alpha_{2,0} d_2 ;\;\; 0 \leq \alpha_i \leq C \;\; i = 1, 2$

因此需要保证 $U \leq \alpha_2 \leq V$ ，其中
$$
\begin{equation*}
U =
\left{
\begin{array}{l}
\max(0, \alpha_{2,0} - \alpha_{1,0}) ;; d_1 \neq d_2 \
\max(0, \alpha_{1,0} + \alpha_{2,0} - C) ;; d_1 = d_2
\end{array}
\right.

V =
\left{
\begin{array}{l}
\min(C, C - \alpha_{1,0} + \alpha_{2,0}) ;; d_1 \neq d_2 \
\min(C, \alpha_{1,0} + \alpha_{2,0}) ;; d_1 = d_2
\end{array}
\right.
\end{equation*}
$$

令
$\begin{equation*} f(\pmb{x}_i) = \pmb{\theta}^T \pmb{x}_i = \sum_{j=1}^m \alpha_{j,0} d_j \pmb{x}_j^T \pmb{x}_i + \theta_0 \\ v_i = \sum_{j=3}^m \alpha_j d_j \pmb{x}_j^T \pmb{x}_i = f(\pmb{x}_i) - \theta_0 - \sum_{j=1}^2 \alpha_{j,0} d_j \pmb{x}_j^T \pmb{x}_i \end{equation*}$

由于 $\alpha_1 + \alpha_2 d_2 d_2 = \alpha_{1,0} + \alpha_{2,0} d_1 d_2 = \gamma$ ，原优化目标
$$
\begin{align*}
Q(\pmb{\alpha})
&= \sum_{i=1}^m \alpha_i - \frac{1}{2} \alpha_i \alpha_j y_i y_j \pmb{x}_i^T \pmb{x}_j \

&= \alpha_1 + \alpha_2 - \alpha_1 d_1 v_1 - \alpha_2 d_2 v_2 - \frac{1}{2} \alpha_1^2 \pmb{x}_1^T \pmb{x}_1 - \frac{1}{2} \alpha_2^2 \pmb{x}_2^T \pmb{x}_2 - \alpha_1 \alpha_2 d_1 d_2 \pmb{x}_1^T \pmb{x}_2 + const\

&= (1 - d_1 d_2) \alpha_2 - \alpha_2 y_2 v_2 - (r - d_1 d_2 \alpha_2) y_1 v_1 - \frac{1}{2} \alpha_2^2 \pmb{x}_2^T \pmb{x}_2 - \frac{1}{2} (\gamma - d_1 d_2 \alpha_2)^2 \pmb{x}_1^T \pmb{x}_1 - \alpha_2 (\gamma - d_1 d_2 \alpha_2) d_1 d_2 \pmb{x}_1^T \pmb{x}_2 + const \

&= (\pmb{x}_1^T \pmb{x}_2 - \frac{1}{2} \pmb{x}_1^T \pmb{x}_1 - \frac{1}{2} \pmb{x}_2^T \pmb{x}_2) \alpha_2^2 + (1 - d_1 d_2 - d_2 v_2 + d_2 v_1 + d_1 d_2 \gamma \pmb{x}_1^T \pmb{x}_1 - d_1 d_2 \gamma \pmb{x}_1^T \pmb{x}_2) \alpha_2 + const\
\end{align*}
$$

因此
$$
\begin{align*}
\frac{\mathrm{d} Q}{\mathrm{d} \alpha_2}
&= (2 \pmb{x}_1^T \pmb{x}_2 - \pmb{x}_1^T \pmb{x}_1 - \pmb{x}_2^T \pmb{x}_2) \alpha_2 + 1 - d_1 d_2 - d_2 v_2 + d_2 v_1 + d_1 d_2 \gamma \pmb{x}_1^T \pmb{x}_1 - d_1 d_2 \gamma \pmb{x}_1^T \pmb{x}_2 \
&= (2 \pmb{x}_1^T \pmb{x}_2 - \pmb{x}_1^T \pmb{x}_1 - \pmb{x}_2^T \pmb{x}_2) \alpha_2 + d_2 (d_2 - d_1 - v_2 + v_1 + d_1 \gamma \pmb{x}_1^T \pmb{x}_1 - d_1 \gamma \pmb{x}_1^T \pmb{x}_2) \

&= (2 \pmb{x}_1^T \pmb{x}_2 - \pmb{x}_1^T \pmb{x}_1 - \pmb{x}_2^T \pmb{x}_2) \alpha_2 + d_2 [(f(\pmb{x}1) - d_1) - (f(\pmb{x}2) - d_2) - \sum{j=1}^2 \alpha{j,0} d_j \pmb{x}_j^T (\pmb{x}1 - \pmb{x}2) + d_1 (\alpha{1,0} + d_1 d_2 \alpha{2,0}) (\pmb{x}_1^T \pmb{x}_1 - \pmb{x}_1^T \pmb{x}_2)] \

&= (2 \pmb{x}_1^T \pmb{x}_2 - \pmb{x}_1^T \pmb{x}_1 - \pmb{x}_2^T \pmb{x}_2) \alpha_2 + d_2 [(f(\pmb{x}_1) - d_1) - (f(\pmb{x}2) - d_2) + \alpha{2,0} d_2 (\pmb{x}_1 - \pmb{x}_2)^T (\pmb{x}_1 - \pmb{x}_2)] \

&= (2 \pmb{x}_1^T \pmb{x}_2 - \pmb{x}_1^T \pmb{x}_1 - \pmb{x}_2^T \pmb{x}2) (\alpha_2 - \alpha{2,0}) + d_2 [(f(\pmb{x}_1) - d_1) - (f(\pmb{x}2) - d_2) + \alpha{2,0} d_2 (\pmb{x}_1 - \pmb{x}_2)^T (\pmb{x}_1 - \pmb{x}_2)]
\end{align*}
$$

因此，当 $\frac{\mathrm{d} Q}{\mathrm{d} \alpha_2} = 0$ ， $\alpha_2 = \alpha_{2,0} + d_2 \frac{[(f(\pmb{x}_2) - d_2) - (f(\pmb{x}_2) - d_2)]}{2 \pmb{x}_1^T \pmb{x}_2 - \pmb{x}_1^T \pmb{x}_1 - \pmb{x}_2^T \pmb{x}_2}$ ，也就是
$\alpha_2 := \alpha_2 - d_2 \frac{E_1 - E_2}{\eta}$
其中 $E_1 = f(\pmb{x}_1) - d_1$ ， $E_2 = f(\pmb{x}_2) - d_2$ ， $\eta = -(\pmb{x}_1 - \pmb{x}_2)^T (\pmb{x}_1 - \pmb{x}_2)$

由于同时需要满足约束条件，因此
$\alpha_2 = \left\{ \begin{array}{l} U \;\; \alpha_2 < U\\ \alpha_2 \;\; U \leq \alpha_2 \leq V\\ V \;\; \alpha_2 > V \end{array} \right.$

$\pmb{w} = (\theta_1, \theta_2, ..., \theta_n)^T$ 可以根据 $A \pmb{\theta} = A \sum_{i=1}^m \alpha_j d_j \pmb{x}_j$ 计算，而更新 $\theta_0$ 时，也需要其使 $\alpha_1$ 和 $\alpha_2$ 满足约束条件。
$\begin{align*} f(\pmb{x}_1) - f_0(\pmb{x}_1) &= b - b_0 + \sum_{j=1}^m (\alpha_j - \alpha_{j,0}) d_j \pmb{x}_j^T \pmb{x}_1 \\ &= b - b_0 + \sum_{j=1}^2 (\alpha_j - \alpha_{j,0}) d_j \pmb{x}_j^T \pmb{x}_1 \end{align*}$
当 $0 < \alpha_1 < C$ ，则 $f(\pmb{x}_1) = d_1$ ， $x_1$ 为支持向量，因此
$f(\pmb{x}_i) - f_0(\pmb{x}_i) = b - b_0 + \sum_{j=1}^2 (\alpha_j - \alpha_{j,0}) d_j \pmb{x}_j^T \pmb{x}_1 = -E_1$
得
$b = b_0 - E_1 - \sum_{j=1}^2 (\alpha_j - \alpha_{j,0}) d_j \pmb{x}_j^T \pmb{x}_1$

当 $0 < \alpha_1 < C$ 同理，且当 $0 < \alpha_1, \alpha_2< C$ 时 $b_1 = b_2$ 。当二者都不是支持向量时（都不在边界上，可取二者的算术平均作为更新值）

因此可以如下更新( $b = \theta_0$ )
$\begin{equation*} b := \left\{ \begin{array}{l} b_1 \;\; if \; 0 < \alpha_1 < C \\ b_2 \;\; if \; 0 < \alpha_2 < C \\ (b_1 + b_2) / 2 \;\; otherwise \end{array} \right. \end{equation*}$
其中
$\begin{equation*} b_1 = b - E_1 - d_1 (\alpha_1 - \alpha_{1,0}) \pmb{x}_1^T \pmb{x}_1 - d_2 (\alpha_2 - \alpha_{2,0}) \pmb{x}_1^T \pmb{x}_2 \\ b_2 = b - E_2 - d_1 (\alpha_1 - \alpha_{1,0}) \pmb{x}_1^T \pmb{x}_2 - d_2 (\alpha_2 - \alpha_{2,0}) \pmb{x}_2^T \pmb{x}_2 \\ \end{equation*}$

在实际使用该算法时设每次选取的两个变量为 $\alpha_{k1}$ 和 $\alpha_{k2}$ ，每次循环中遍历所有变量 $\alpha_{k1}$ ，每次随机选取另一个变量 $\alpha_{k2}$ ，更新 $\alpha_{k1}$ ， $\alpha_{k2}$ 和 $b$ 后，更新 $\theta_0$ 的值直到所有变量不再变化或者达到最大循环次数为止。

引入核函数

对于线性不可分问题，可以更高维特征，但是由于每次由 $\pmb{\alpha}$ 和 $\pmb{x}$ 更新 $\pmb{\theta}$ 时需要计算內积。当维度很高时计算量过大。因此引入核函数，其与高维空间中的內积等同，常用核函数包括

多项式核函数 $\kappa(\pmb{x}, \pmb{y}) = (r_1 + \pmb{x}^T \pmb{y} + r_2)^d$

例如
$\begin{equation*} \kappa(\pmb{x}, \pmb{y}) = (\pmb{x}^T \pmb{y})^2 = (x_1 y_1 + x_2 y_2)^2 = \phi(\pmb{x})^T \phi(\pmb{y}) \end{equation*}$
其中 $\phi(\pmb{x}) = (x_1^2, \sqrt{2} x_1 x_2, x_2^2)^T$
径向基函数 $\kappa(\pmb{x}, \pmb{y}) = \exp (-r {\Vert \pmb{x} - \pmb{y} \Vert}^2)$

径向基函数也可以视为高维空间的向量內积，例如
$\begin{align*} \kappa(\pmb{x}, \pmb{y}) &= \exp (-{\Vert \pmb{x} - \pmb{y} \Vert}^2) \\ &= \exp(-\Vert \pmb{x} \Vert^2) \exp(-\Vert \pmb{y} \Vert^2) \exp(2 \pmb{x}^T \pmb{y}) \\ &= \exp(-\Vert \pmb{x} \Vert^2) \exp(-\Vert \pmb{y} \Vert^2) \sum_{n=0}^\infty \frac{\left(2\pmb{x}^T \pmb{y} \right)^n}{n!}\\ &= \phi(\pmb{x}) \phi{(\pmb{y})} \end{align*}$
其中 $\phi(\pmb{x}) = \exp(\Vert \pmb{x} \Vert^2) \cdot \left(1, \sqrt{\frac{2}{1!}} \pmb{x}^{(1)}, \sqrt{\frac{2^2}{2!}} \pmb{x}^{(2)}, ..., \sqrt{\frac{2^n}{n!}} \pmb{x}^{(n)}, ... \right)^T$ ， $\pmb{x}^{(n)}$ 的各项为 $(\sum_{k=1}^K x_k)^n$ 的各项。

径相基函数可以视为 $\pmb{x}$ 和 $\pmb{y}$ 之间的相似度，当二者较为接近时，函数值较大。当惩罚系数选取过大时容易造成过拟合 (分隔超平面很复杂)，当 $r$ 选取过大时也容易造成过拟合，因为此时新空间中计算得到的特征向量随原向量变化过大。反之则可能出现欠拟合的情况。

适用场景

设 $n$ 为特征数目， $m$ 为样本数目

当 $n$ 很大时使用Logistic回归或者不带核函数的SVM。
当 $n$ 较小， $m$ 中等时使用带高斯核的SVM。
当 $n$ 较小， $m$ 较大时应该加入更多的特征并采用Logistic回归或者采用不带核函数的SVM (核函数计算量大)。

聚类

k均值算法

k均值算法将样本集合 $D$ 中的m个样本 ${x_1,x_2,...,x_m}$ 划分为 $k$ 个簇 $\mathcal{C} = {C_1,C_2,...,C_k}$ ，划分标准为最小化平方误差
$E = \sum_{i=1}^k \sum_{x \in D_i} ||x-\mu_i||^2$
其中 $\mu_i$ 为第i个簇的中心 (各点坐标的平均值) 。
$\mu_i = \frac{1}{|C_i|} \sum_{x \in D_i} x$
首先选定k个样本作为聚类中心，然后将每个样本划分到与其距离最近的中心所对应的簇，然后更新每个簇的聚类中心为该簇样本坐标的平均值。

注意在有些情况下，k-means聚类可能陷入局部最优而不是全局最优，此时应该尝试采用不同的随机初始聚类中心位置。另外，可以尝试不同的聚类簇数量，选取效果最好的。

主成分分析

主成分分析是一种无监督降维方法，其核心思想是将高维数据映射到一个其方差较大的低维度超平面上 (其正交方向上的方差较小，可视为噪声)，且各个分量线性无关。

数学推导

对于一系列的数据点 $\pmb{x}$ ，其在将被映射到的地位超平面上的投影点为 $\pmb{x'}$ ，为了尽可能保留原信息，需要两个点尽量逼近。以二维或三维数据投影到直线为例，设 $\pmb{e}$ 为投影直线的单位向量， $a_k = \pmb{e}^T x_k$ 为其在投影平面上的模，最小化目标函数
$\begin{align*} J(\pmb{e}) &= \sum_{i=1}^m {\Vert a_k \pmb{e} - \pmb{x_i} \Vert}^2 \\ &= \sum_{i=1}^m \left[ a_k^2 {\Vert \pmb{e} \Vert}^2 - 2 a_k \pmb{e} \pmb{x_k} + {\Vert x_i \Vert}^2 \right] \\ &= \sum_{i=1}^m \left[ {\Vert \pmb{x_i} \Vert}^2 - a_k^2 \right] \\ &= \sum_{i=1}^m \left[ {\Vert \pmb{x_i} \Vert}^2 - \pmb{e}^T \pmb{x_k} \pmb{x_k}^T \pmb{e} \right] \\ &= X^T X - \pmb{e}^T X X^T \pmb{e} \end{align*}$

令 $S = X X^T$ ，则问题转换为最大化函数 $\underset{\pmb{e}}{\max} \, \pmb{e}^T S \pmb{e}$ 。等式约束条件为 $\pmb{e}^T \pmb{e} = 1$ 。

采用Lagrange乘子法求解，令
$L(\pmb{e}, \lambda) = \pmb{e}^T S \pmb{e} - \lambda (\pmb{e}^T \pmb{e} - 1)$
应用KKT定理，当函数取极值时
$\frac{\partial L}{\partial \pmb{e}} = 2 S \pmb{e} - 2 \lambda \pmb{e} = 0$
也就是
$S \pmb{e} = \lambda \pmb{e}$
而且 $L(\pmb{e}, \lambda) = \lambda$ ，因此， $\lambda$ 应为 $S$ 的特征值， $\pmb{e}$ 为对应的特征向量，需要选择特征值最大的特征向量作为投影直线的方向。

理解

在实际应用中，若采用 $\pmb{x_k} = \pmb{x} - \pmb{\mu}$ ，则矩阵 $S$ 为协方差矩阵（通常也在主成分分析之前会输入值进行标准化，标准化之后矩阵 $S$ 为协方差矩阵），必然可以相似对角化而且它是非负定矩阵，且对角化后对角线元素越大代表此特征对应的方差越大。非对角线位置值为0表明两个特征非线性相关。注意PCA只是客观降维，与样本的类别无关，因此可能出现降维之后样本非线性可分的情况。

推导如下：

令 $D(X) = \Sigma$ , $E(X) = \pmb{\mu}$ ，而 $Y = T^T X$ ，因此
$D(Y) = T^T \Sigma T$
为了最大化方差，取得主成分，设第i主成分为 $Y_i = T_i^T X$ ，则最大化目标函数
$\phi_i(T_i, \lambda) = D(Y_i) - \sum_{p=1}^P [\lambda_p (T_i^T T_p)] - \lambda_i T_i^T T_i$

应用KKT条件，则有
$\frac{\partial \phi_i}{\partial T_i} = 2 \Sigma T_i - 2\lambda_i T_i = 0$

在这里也可以看出 $T_1$ 是 $\Sigma$ 的特征向量，而 $\lambda_1$ 为对应的特征值。需要说明的一点是 $\Sigma$ 作为协方差矩阵一定是非负定的，且作为实对称矩阵一定可以对角化。

证明协方差矩阵半正定

$\forall \pmb{u} \neq \pmb{0}$ ， $\pmb{u}^T \Sigma \pmb{u} = \pmb{u}^T E \left[ (X-\overline{X}) (X-\overline{X})^T \right] \pmb{u} = E \left\{ [(X-\overline{X})^T \pmb{u}]^T [(X-\overline{X})^T \pmb{u}] \right\} \ge 0$ ，因此 $\Sigma$ 是半正定矩阵，当且仅当 $X-\overline{X}$ 是满秩矩阵时为正定矩阵(因为此时方程 $(X-\overline{X})^T \pmb{u} = \pmb{0}$ 没有非零解)。

奇异值分解

对于 $m \times n$ 的实矩阵A，其可以分解为 $A = U \Sigma V^T$ 的形式，其中 $U$ 为 $m \times m$ 正交矩阵， $V$ 为 $n \times n$ 正交矩阵， $\Sigma$ 为 $m \times n$ 对角矩阵。

不妨设 $m \geq n$ ，由于 $A$ 为实矩阵，则 $A^T A$ 为实对称矩阵，一定可以相似对角化，设其对角化后的矩阵为 $\Sigma_0$ ，则
$A^T A = V \Sigma_0 V^T$
其中 $V$ 为 $n \times n$ 正交矩阵，设 $\Sigma_0$ 的对角线元素为降序排序，且值分别为 $\lambda_1, \lambda_2, ..., \lambda_r, \lambda_{r+1}, ..., \lambda_{n}$ ，其中 $r$ 为 $A^T A$ 的秩。

令 $\sigma_k = \sqrt{\lambda_k}, k = 1, 2, ..., r$
$\Sigma_1 = \begin{bmatrix} \sigma_1 & 0 & \cdot & \cdot & \cdot & 0 \\ 0 & \sigma_2 & \cdot & \cdot & \cdot & 0 \\ \cdot & \cdot & \cdot & & & \cdot \\ \cdot & \cdot & & \cdot & & \cdot \\ \cdot & \cdot & & & \cdot & \cdot \\ 0 & 0 & \cdot & \cdot & \cdot & \sigma_r \\ \end{bmatrix} ,\;\;\;\; \Sigma = \begin{bmatrix} \Sigma_1 & 0 \\ 0 & 0 \\ \end{bmatrix}$

令 $u_j = \frac{1}{\sigma_j} A v_j, j = 1, 2, ..., r$ ，则
$\begin{align*} u_i^T u_j &= \frac{1}{\sigma_i \sigma_j} v_i^T (A^T A v_j) \\ &= \frac{1}{\sigma_i \sigma_j} v_i^T \lambda_j v_j \\ &= \frac{\sigma_j}{\sigma_i} v_i^T v_j \end{align*}$

可以看出， $U_1 = [u_1, u_2, u_r]$ 是 $\mathbb{R}^r$ ，也是 $A$ 的列空间的一组标准正交基，令 $U_2 = [u_{r+1}, ..., u_m]$ 为 $A^T$ 的零空间的一组标准正交基， $[U_1, U_2]$ 构成 $m \times m$ 正交向量。令 $V_1 = [v_1, v_2, ..., v_r]$ ，则
$\begin{align*} U \Sigma V^T &= \begin{bmatrix} U_1 & U_2 \end{bmatrix} \begin{bmatrix} \Sigma_1 & 0 \\ 0 & 0 \end{bmatrix} V^T \\ &= U_1 \Sigma_1 V_1^T \\ &= A V_1 V_1^T \\ &= A \end{align*}$
可对角化方阵的几何重数等于代数重数，其特征值分解可以视为奇异值分解的特例。

线性判别分析

由于PCA并没有涉及到样本的类别，降维之后可能导致样本线性不可分。LDA在降维的同时尽量保证不同类样本的区分。

数学推导

优化目标函数为
$\max \, J = \frac{|\mu_1' - \mu_2'|^2}{S_1^2 + S_2^2}$
其中， $\mu_1'$ 和 $\mu_2'$ 分别降维后是类别1和类别2的中心点， $S_1$ 和 $S_2$ 分别为
$S_i = \sum_{x \in w_i} (x'-\mu_i')(x'-\mu_i')^T \; i=1, 2$
目标函数也可以写成
$J = \frac{w^T S_B w}{w^T S_W w}$
其中 $S_B$ 和 $S_W$ 分别为类间和类内散布矩阵，其定义为
$S_B = (\mu_1-\mu_2)(\mu_1-\mu_2)^T$
$S_W = \sum_{i=1}^2 \sum_{x \in w_i} (x-\mu_i)(x-\mu_i)^T$

求导
$\frac{\mathrm{d} J(w)}{\mathrm{d} w} = 0$
可以化为
$S_W^{-1} S_B w = Jw$
可以认为向量 $J$ 是矩阵 $S_W^{-1} S_B$ 的特征值，而 $w$ 是对应的特征向量。只需要求矩阵最大的特征值，并找到对应的特征向量就可以得到正确的投影方向。

理解

PCA的投影坐标系是正交的，但是LDA不保证，因此降维后的维度之间可能有相关性。

对于多类别的线性判别分析，设类别数目为K，第i类的元素数目为 $n_i$ ，所有元素的均值为 $\mu$ ，类内散布矩阵和类间散布矩阵分别定义为
$S_B = \sum_{i=1}^K n_i (\mu_i-\mu)(\mu_i-\mu)^T$
$S_W = \sum_{i=1}^K \sum_{x \in w_i} (x-\mu_i)(x-\mu_i)^T$

异常检测

对于异常检测，可采用(多元)高斯分布，根据特定阈值将概率密度较低的取值判定为异常。当采用的样本有正常和异常的标签时可以寻找一个最佳的概率阈值使得分类的精度(F-score)最高。

集成学习

Boosting

Adaboost

算法流程

初始化分布 (可理解为每个样本的权重)

训练数据集样本数目为 $m$ ，用 $(x_i, \, y_i)$ 表示，初始化权重
$\mathcal{D}_1(i) = \frac{1}{m}$
训练弱分类器 $h_t$

可以选择不同的分类器训练，分类错误率为
$\epsilon_t = \sum_i^m \mathcal{D}_t(i) \cdot P \left[ y_i \not= h_t(x_i) \right] = 1-2\sum_i^m \mathcal{D}_t(i) y_i h_t(x_i)$

若计算出的错误率大于0.5，则算法结束。否则更新当前弱分类器的权重为 (之后讨论中会推导)
$\alpha_t = \frac{1}{2} \ln \frac{1-\epsilon_t}{\epsilon_t}$

更新权重
$\mathcal{D}_{t+1}(i) = \frac{\mathcal{D}_t(i) \cdot e^{-\alpha_t y_i h_t(x_i)}}{Z_t}$

其中 $Z_t = \sum_i^m {\mathcal{D}_t(i) \cdot e^{-\alpha_t y_i h_t(x_i)}}$
重复步骤2总共进行 $T$ 次

最终得到的激活函数为
$f(\pmb{x}) = {\rm sign} \left[ \sum_{t=1}^T \alpha_t h_t(\pmb{x}) \right]$

注：以上 $h_t$ 和 $f$ 的函数值均为{-1,1}

讨论

集成分类器收敛

由算法流程可知，对于第 $T+1$ 步的权重
$\mathcal{D}_{T+1}(i) = \frac{e^{-y_i \sum_t^T \alpha_t h_t(x_i)}}{\prod_t Z_t} = \frac{e^{-y_i f(x_i)}}{\prod_t Z_t} < 1 \;\; i = 1, 2, ..., m$

Adaboost采用的损失函数是指数损失函数，分类损失函数为
$J = \frac{1}{m} \sum_{i=1}^m e^{-y_i f(x_i)} \leq \prod_t Z_t$

亦即分类损失函数的上界。为了尽可能减小此上界，可以考虑在第 $t$ 步训练弱分类器时最小化 $Z_t$ ，实际上由于
$\begin{split} Z_t &= \sum_i^m {\mathcal{D}_t(i) \cdot e^{-\alpha_t y_i h_t(x_i)}} \\ &= \sum_i^m {\mathcal{D}_t(i) { \left( \sqrt {\frac{1-\epsilon_t}{\epsilon_t}} \right) }^{y_i h_t(x_i)}} \\ &= \sum_i^m {\mathcal{D}_t(i) { \sqrt {\frac{1-\epsilon_t}{\epsilon_t}} P[y_i \not= h_t(x_i)]} } + \sum_i^m {\mathcal{D}_t(i) { \sqrt {\frac{\epsilon_t}{1-\epsilon_t}} P[y_i = h_t(x_i)]} } \\ &= \sqrt {\frac{1-\epsilon_t}{\epsilon_t}} \epsilon_t + \sqrt {\frac{\epsilon_t}{1-\epsilon_t}} (1-\epsilon_t) = 2 \sqrt {\epsilon (1-\epsilon)} \leq 1 \end{split}$
由此可见，如果使用足够多的弱分类器集成，损失函数的上界可以收敛至 $0$ 。
损失函数

采用指数损失函数 ( $\mathbb{E}$ 表示期望)
$\begin{equation*} \ell_{exp}(f|\mathcal{D}) = {\mathbb{E}}_{\pmb{x} \sim \mathcal{D}} \left[ e^{-y f(\pmb{x})} \right] \end{equation*}$

其中 $f(x) = \mathrm{sign} \sum_t^T [\alpha_t h_t(x)]$ 为模型输出的分类结果。

$\frac{\partial \ell_{exp}(f|\mathcal{D})}{\partial f(\pmb{x})} = -e^{-f(\pmb{x})} P(y=1|\pmb{x}) + e^{f(\pmb{x})} P(y=-1|\pmb{x})$

函数取得最小值时
$f(\pmb{x}) = \frac{1}{2} \ln \frac{P(y=1|\pmb{x})}{P(y=-1|\pmb{x})}$

$H(\pmb{x}) = {\rm sign} f(\pmb{x}) = \underset{c \in {-1, 1}}{\rm argmax} \, P(y = c|\pmb{x})$

由此看出，指数损失函数达到最小值时，0/1损失函数也达到了最小，因此前者是一个合理的损失函数。

另外，关于弱分类器的权重，由于
$\begin{align*} \frac{\partial \ell_{exp}(h_k|\mathcal{D})}{\partial \alpha_k} &= {\mathbb{E}}_{\pmb{x} \sim \mathcal{D}} \left[- h_k(x) y \cdot e^{-\alpha_k h_k(\pmb{x}) \cdot y} \right] \\ &= -e^{-\alpha_k} P(y=h_k(\pmb{x})|\pmb{x}) + e^{\alpha_k} P(y=-h_k(\pmb{x})|\pmb{x}) \end{align*}$
指数损失函数达到最小值时有 $\alpha_k = \frac{1}{2} \log{\frac{P(y=h_k(\pmb{x})|\pmb{x})}{P(y \neq h_k(\pmb{x})|\pmb{x})}} = \frac{1}{2} \log{\frac{1-\epsilon_k}{\epsilon_k}}$