线性回归

给定由$d$个属性描述的样本$\boldsymbol{x}=(x_1; x_2; \dots ; x_d)$（列向量），数据集$D=\left\{\left(\boldsymbol{x}_{1}, y_{1}\right),\left(\boldsymbol{x}_{2}, y_{2}\right), \ldots,\left(\boldsymbol{x}_{m}, y_{m}\right)\right\}$，线性回归试图学得一个线性组合来进行预测的函数：

$$
f(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b
$$

其中权重$\boldsymbol{w}=\left(w_{1} ; w_{2} ; \ldots ; w_{d}\right)$，偏置$b$为标量

一元线性回归

先考虑最简单的情况：样本只有一个属性，即一元线性回归。此问题试图学得

$$
f\left(x_{i}\right)=w x_{i}+b, 使得 f\left(x_{i}\right) \simeq y_{i}
$$

这里使用均方误差来衡量$f(x)$与$y$之间的差别，使得均方误差最小的$w$和$b$即为所求，即：

$$
\begin{aligned}
\left(w^{\ast}, b^{\ast}\right) &=\underset{(w, b)}{\arg \min } \sum_{i=1}^{m}\left(f\left(x_{i}\right)-y_{i}\right)^{2} \\
&=\underset{(w, b)}{\arg \min } \sum_{i=1}^{m}\left(y_{i}-w x_{i}-b\right)^{2} \end{aligned}
$$

基于均方误差最小化来求解模型的方法称为最小二乘法，就是试图找到一条直线，是所有样本到直线上的欧式距离之和最小。设损失$E=\sum_{i=1}^{m}\left(f\left(x_{i}\right)-y_{i}\right)^{2}$，将$E$对$w$和$b$分别求导，得到：

$$
\begin{aligned} \frac{\partial E_{(w, b)}}{\partial w} &=2\left(w \sum_{i=1}^{m} x_{i}^{2}-\sum_{i=1}^{m}\left(y_{i}-b\right) x_{i}\right) \\
\frac{\partial E_{(w, b)}}{\partial b} &=2\left(m b-\sum_{i=1}^{m}\left(y_{i}-w x_{i}\right)\right)
\end{aligned}
$$

然后令两式都为0，得到解析解：

$$
w=\frac{\sum_{i=1}^{m} y_{i}\left(x_{i}-\overline{x}\right)}{\sum_{i=1}^{m} x_{i}^{2}-\frac{1}{m}\left(\sum_{i=1}^{m} x_{i}\right)^{2}} \\
b=\frac{1}{m} \sum_{i=1}^{m}\left(y_{i}-w x_{i}\right)
$$

其中$\overline{x}=\frac{1}{m} \sum_{i=1}^{m} x_{i}$为均值。

多元线性回归

而更一般的情况是本文开头所给出的数据集的形式，样本有$d$个属性，此时我们试图学得

$$
f\left(\boldsymbol{x}_{i}\right)=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b, 使得f\left(x_{i}\right) \simeq y_{i}
$$

这里我们将权重$\boldsymbol{w}$和偏置$b$整合在一起：$\hat{\boldsymbol{w}}=(\boldsymbol{w} ; b)$，同样得数据集$D$表示为一个$m \times (d+1)$大小的矩阵$\boldsymbol{X}$，即：

$$
\mathbf{X}=\left(\begin{array}{ccccc}{x_{11}} & {x_{12}} & {\dots} & {x_{1 d}} & {1} \\ {x_{21}} & {x_{22}} & {\dots} & {x_{2 d}} & {1} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} & {\vdots} \ {x_{m 1}} & {x_{m 2}} & {\dots} & {x_{m d}} & {1}\end{array}\right)=\left(\begin{array}{cc}{\boldsymbol{x}_{1}^{\mathrm{T}}} & {1} \\ {\boldsymbol{x}_{2}^{\mathrm{T}}} & {1} \\ {\vdots} & {\vdots} \\ {\boldsymbol{x}_{m}^{\mathrm{T}}} & {1}\end{array}\right)
$$

标签也写成向量形式$\boldsymbol{y}=\left(y_{1} ; y_{2} ; \ldots ; y_{m}\right)$，我们同样使用均方误差最小化：

$$
\hat{\boldsymbol{w}}^{*}=\underset{\boldsymbol{\hat { w }}}{\arg \min }(\boldsymbol{y}-\mathbf{X} \hat{\boldsymbol{w}})^{\mathrm{T}}(\boldsymbol{y}-\mathbf{X} \hat{\boldsymbol{w}})
$$

令$E=(\boldsymbol{y}-\mathbf{X} \hat{\boldsymbol{w}})^{\mathrm{T}}(\boldsymbol{y}-\mathbf{X} \hat{\boldsymbol{w}})$，展开得到：

$$
E=\boldsymbol{y}^{T} \boldsymbol{y}-\boldsymbol{y}^{T} \mathbf{X} \hat{\boldsymbol{w}}-\hat{\boldsymbol{w}}^{T} \mathbf{X}^{T} \boldsymbol{y}+\hat{\boldsymbol{w}}^{T} \mathbf{X}^{T} \mathbf{X} \hat{\boldsymbol{w}}
$$

对$\hat{\boldsymbol{w}}$求导得到：

$$
\begin{array}{c}{\frac{\partial E}{\partial \hat{\boldsymbol{w}}}=0-\mathbf{X}^{T} \boldsymbol{y}-\mathbf{X}^{T} \boldsymbol{y}+\left(\mathbf{X}^{T} \mathbf{X}+\mathbf{X}^{T} \mathbf{X}\right) \hat{\boldsymbol{w}}} \\ {\frac{\partial E}{\partial \hat{\boldsymbol{w}}}=2 \mathbf{X}^{T}(\mathbf{X} \hat{\boldsymbol{w}}-\boldsymbol{y})}\end{array}
$$

此处推到用到的矢量导数公式：
$$
\frac{\partial \boldsymbol{x}^{T} \boldsymbol{a}}{\partial \boldsymbol{x}}=\frac{\partial \boldsymbol{a}^{T} \boldsymbol{x}}{\partial \boldsymbol{x}}=\boldsymbol{a}
$$

若$\boldsymbol{X}^{T} \boldsymbol{X}$为满秩矩阵或正定矩阵，令$\frac{\partial E}{\partial \hat{\boldsymbol{w}}}=0$，得：

$$
\hat{\boldsymbol{w}}^{*}=\left(\mathbf{X}^{\mathrm{T}} \mathbf{X}\right)^{-1} \mathbf{X}^{\mathrm{T}} \boldsymbol{y}
$$

正则化回归

现实中$\boldsymbol{X}^{T} \boldsymbol{X}$往往不是满秩矩阵，比如$\boldsymbol{X}$的列数多于行数，此时可能会有多个$\hat{\boldsymbol{w}}^{*}$。这时候可以引入正则化项：

$$
\hat{\boldsymbol{w}}^{*}=\underset{\boldsymbol{\hat { w }}}{\arg \min }(\boldsymbol{y}-\mathbf{X} \hat{\boldsymbol{w}})^{\mathrm{T}}(\boldsymbol{y}-\mathbf{X} \hat{\boldsymbol{w}}) + \lambda ||\hat{\boldsymbol w}||^2
$$

其中$||\hat{\boldsymbol w}||^2=\sum w_{i}^{2}$，可解得：

$$
\hat{\boldsymbol{w}}^{*}=\left(\mathbf{X}^{\mathrm{T}} \mathbf{X} + \lambda \boldsymbol I \right)^{-1} \mathbf{X}^{\mathrm{T}} \boldsymbol{y}
$$

$\boldsymbol I$为单位矩阵，相当于为$\boldsymbol{X}^{T} \boldsymbol{X}$的对角线元素增加了$\lambda$，增强矩阵求逆数值的稳定性。此形式的正则化回归称为岭回归（ridge regression）。如果将$||\hat{\boldsymbol w}||^2$（L2正则化）换成$|\hat{\boldsymbol w}|$（L1正则化），则称为lasso（least absolute shrinkage and selection operator），lasso对$\lambda$非常敏感，可以得到稀疏解，但lasso没有解析解。

线性判别分析LDA（Linear Discriminant Analysis）

LDA基本思想：将样本投影到一条直线上，使同类样本的投影点尽可能近，异类样本投影点尽可能远；在对新样本进行分类时，将其投影到这条直线上，根据投影点的位置确定类别。

两类LDA

给定数据集$D=\left\{\left(\boldsymbol{x}_{i}, y_{i}\right)\right\}_{i=1}^{m}$, $y_{i} \in\{0,1\}$，令$X_{i}, \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}$分别为第$i$类的集合、均值向量和协方差矩阵，投影到直线$\boldsymbol w$上，则两类中心在直线上的投影分别为$\boldsymbol w^{\mathrm{T}} \boldsymbol \mu_{0}$和$\boldsymbol w^{\mathrm{T}} \boldsymbol \mu_{1}$；协方差分别为$\boldsymbol w^{\mathrm{T}} \boldsymbol \Sigma_{0} \boldsymbol w$和$\boldsymbol w^{\mathrm{T}} \boldsymbol \Sigma_{1} \boldsymbol w$。

要使同类投影点尽可能近，则$\boldsymbol w^{\mathrm{T}} \boldsymbol \Sigma_{0} \boldsymbol w + \boldsymbol w^{\mathrm{T}} \boldsymbol \Sigma_{1} \boldsymbol w$要尽可能小。

要使异类投影点尽可能远，则$\left|\boldsymbol{w}^{\mathrm{T}} \boldsymbol{\mu}_{0}-\boldsymbol{w}^{\mathrm{T}} \boldsymbol{\mu}_{1}\right|_{2}^{2}$要尽可能大。

同时考虑两者，可得最大化的目标函数：

$$
\begin{aligned} J &=\frac{\left|\boldsymbol{w}^{\mathrm{T}} \boldsymbol{\mu}_{0}-\boldsymbol{w}^{\mathrm{T}} \boldsymbol{\mu}_{1}\right|_{2}^{2}}{\boldsymbol{w}^{\mathrm{T}} \boldsymbol{\Sigma}_{0} \boldsymbol{w}+\boldsymbol{w}^{\mathrm{T}} \boldsymbol{\Sigma}_{1} \boldsymbol{w}} \\ &=\frac{\boldsymbol{w}^{\mathrm{T}}\left(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}\right)\left(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}\right)^{\mathrm{T}} \boldsymbol{w}}{\boldsymbol{w}^{\mathrm{T}}\left(\boldsymbol{\Sigma}_{0}+\boldsymbol{\Sigma}_{1}\right) \boldsymbol{w}} \end{aligned}
$$

• 定义类内散度矩阵：
  $$
  \begin{aligned}
  \mathbf{S}_{w} &=\boldsymbol{\Sigma}_{0}+\boldsymbol{\Sigma}_{1} \\
  &=\sum_{\boldsymbol{x} \in X_{0}}\left(\boldsymbol{x}-\boldsymbol{\mu}_{0}\right)\left(\boldsymbol{x}-\boldsymbol{\mu}_{0}\right)^{\mathrm{T}}+\sum_{\boldsymbol{x} \in X_{1}}\left(\boldsymbol{x}-\boldsymbol{\mu}_{1}\right)\left(\boldsymbol{x}-\boldsymbol{\mu}_{1}\right)^{\mathrm{T}} \end{aligned}
  $$

• 定义类间散度矩阵：
  $$
  \mathbf{S}_{b}=\left(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}\right)\left(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}\right)^{\mathrm{T}}
  $$

可重新定义目标函数：

$$
J=\frac{\boldsymbol{w}^{\mathrm{T}} \mathbf{S}_{b} \boldsymbol{w}}{\boldsymbol{w}^{\mathrm{T}} \mathbf{S}_{w} \boldsymbol{w}}
$$

LDA即是最大化$\mathbf{S}_{b}$和$\mathbf{S}_{w}$的广义瑞利商。

瑞利商：
$$
R(A, x)=\frac{x^{H} A x}{x^{H} x}
$$
$x$为非零向量，$A$为$n \times n$的Hermitan矩阵，满足$A^{H}=A$，即共轭转置矩阵和自己相等。如果A是实矩阵，则满足$A^{T}=A$的为Hermitan矩阵。瑞利商有一个非常重要的性质，即它的最大值等于矩阵A最大的特征值，而最小值等于矩阵A的最小的特征值，也就是满足
$$
\lambda_{\min } \leq \frac{x^{H} A x}{x^{H} x} \leq \lambda_{\max }
$$

广义瑞利商是指这样的函数$R(A, B, x)$:
$$
R(A, B, x)=\frac{x^{H} A x}{x^{H} B x}
$$
其中$x$为非零向量，而$A$,$B$为$n \times n$的Hermitan矩，$B$为正定矩阵。

若$\boldsymbol{w}$是一个解，那么对于任意常数$\alpha$，$\alpha \boldsymbol{w}$也是$J$的解，因此$J$的解与$\boldsymbol{w}$的长度无关，只与其方向有关。可以令$\boldsymbol{w}^{T} \boldsymbol{S}_{w} \boldsymbol{w}=1$，则最大化$J$等价于：

$$
\begin{array}{cl}{\min_{\boldsymbol{w}}} & {-\boldsymbol{w}^{\mathrm{T}} \mathbf{S}_{b} \boldsymbol{w}} \\ {\text { s.t. }} & {\boldsymbol{w}^{\mathrm{T}} \mathbf{S}_{w} \boldsymbol{w}=1}\end{array}
$$

由朗格朗日乘子，上式等价于：

$$
\mathbf{S}_{b} \boldsymbol{w}=\lambda \mathbf{S}_{w} \boldsymbol{w}
$$

由于$\mathbf{S}_{b} \boldsymbol{w}=\left(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}\right)\left(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}\right)^{\mathrm{T}} \boldsymbol{w}$，$\left(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}\right)^{\mathrm{T}} \boldsymbol{w}$为标量，所以$\mathbf{S}_{b} \boldsymbol{w}$的方向恒为$\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}$。不妨设$\mathbf{S}_{b} \boldsymbol{w}=\lambda \left(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}\right)$，可得：

$$
\boldsymbol{w}=\mathbf{S}_{w}^{-1}\left(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}\right)
$$

推论：当两类数据同先验、满足高斯分布且协方差相等时，LDA可达到最优分类。

多分类情况

LDA推广到多分类任务，设有$N$个类，第$i$类样本数目为$m_{i}$。

• 重新定义类内散度矩阵：
  $$
  \mathbf{S}_{w}=\sum_{i=1}^{N} \mathbf{S}_{w_{i}}
  $$

其中：$\mathbf{S}_{w_{i}}=\sum_{\boldsymbol{x} \in X_{i}}\left(\boldsymbol{x}-\boldsymbol{\mu}_{i}\right)\left(\boldsymbol{x}-\boldsymbol{\mu}_{i}\right)^{\mathrm{T}}$

• 定义全局散度矩阵：

$$
\begin{aligned}
\mathbf{S}_{t} &=\sum_{i=1}^{m}\left(\boldsymbol{x}_{i}-\boldsymbol{\mu}\right)\left(\boldsymbol{x}_{i}-\boldsymbol{\mu}\right)^{\mathrm{T}}\\
&=\sum_{j=1}^{N} \sum_{\boldsymbol{x} \in X_{j}}\left(\boldsymbol{x}-\boldsymbol{\mu}_{j}+\boldsymbol{\mu}_{j}-\boldsymbol{\mu}\right)\left(\boldsymbol{x}-\boldsymbol{\mu}_{j}+\boldsymbol{\mu}_{j}-\boldsymbol{\mu}\right)^{T} \\
&=\sum_{j=1}^{N} \sum_{\boldsymbol{x} \in X_{j}}\left(\boldsymbol{x}-\boldsymbol{\mu}_{j}\right)\left(\boldsymbol{x}-\boldsymbol{\mu}_{i}\right)^{T}+\sum_{j=1}^{N} \sum_{\boldsymbol{x} \in X_{j}} \left(\boldsymbol{\mu}_{j}-\boldsymbol{\mu}\right)\left(\boldsymbol{\mu}_{j}-\boldsymbol{\mu}\right)^{T} \\ &+\sum_{j=1}^{N} \sum_{\boldsymbol{x} \in X_{j}} \left(\boldsymbol{x}-\boldsymbol{\mu}_{j}\right)\left(\boldsymbol{\mu}_{j}-\boldsymbol{\mu}\right)^{T}+\sum_{j=1}^{N} \sum_{\boldsymbol{x} \in X_{j}} \left(\boldsymbol{\mu}_{j}-\boldsymbol{\mu}\right)\left(\boldsymbol{x}-\boldsymbol{\mu}_{j}\right)^{T} \end{aligned}
$$

其中$\sum_{j=1}^{N} \sum_{\boldsymbol{x} \in X_{j}}\left(\boldsymbol{x}-\boldsymbol{\mu}_{j}\right)\left(\boldsymbol{x}-\boldsymbol{\mu}_{i}\right)^{T}=\mathbf{S}_{w}$，$\sum_{j=1}^{N} \sum_{\boldsymbol{x} \in X_{j}} \left(\boldsymbol{\mu}_{j}-\boldsymbol{\mu}\right)\left(\boldsymbol{\mu}_{j}-\boldsymbol{\mu}\right)^{T}=\mathbf{S}_{b}$，$\sum_{j=1}^{N} \sum_{\boldsymbol{x} \in X_{j}} \left(\boldsymbol{x}-\boldsymbol{\mu}_{j}\right)\left(\boldsymbol{\mu}_{j}-\boldsymbol{\mu}\right)^{T}=\sum_{j=1}^{N} \sum_{\boldsymbol{x} \in X_{j}} \left(\boldsymbol{\mu}_{j}-\boldsymbol{\mu}\right)\left(\boldsymbol{x}-\boldsymbol{\mu}_{j}\right)^{T}=0$，因此：

$$
\begin{aligned} \mathbf{S}_{t} &=\mathbf{S}_{b}+\mathbf{S}_{w}\end{aligned}
$$

• 重新定义类间散度矩阵：

$$
\begin{aligned} \mathbf{S}_{b} &=\mathbf{S}_{t}-\mathbf{S}_{w} \\ &=\sum_{i=1}^{N} m_{i}\left(\boldsymbol{\mu}_{i}-\boldsymbol{\mu}\right)\left(\boldsymbol{\mu}_{i}-\boldsymbol{\mu}\right)^{\mathrm{T}} \end{aligned}
$$

最优化目标函数可写为：

$$
\max _{\mathbf{W}} \frac{\operatorname{tr}\left(\mathbf{W}^{\mathrm{T}} \mathbf{S}_{b} \mathbf{W}\right)}{\operatorname{tr}\left(\mathbf{W}^{\mathrm{T}} \mathbf{S}_{w} \mathbf{W}\right)}
$$

其中$\mathbf{W}=\left[\boldsymbol{w}_{1}, \boldsymbol{w}_{2}, \dots, \boldsymbol{w}_{i}, \dots, \boldsymbol{w}_{k}\right]$，$\boldsymbol{w}_{i}$为d行1列的列向量，则：

$$
\left\{\begin{array}{c}{\operatorname{tr}\left(\mathbf{W}^{T} \mathbf{S}_{b} \mathbf{W}\right)=\sum_{i=1}^{k} \boldsymbol{w}_{i}^{T} \boldsymbol{S}_{b} \boldsymbol{w}_{i}} \\ {\operatorname{tr}\left(\mathbf{W}^{T} \boldsymbol{S}_{w} \mathbf{W}\right)=\sum_{i=1}^{k} \boldsymbol{w}_{i}^{T} \boldsymbol{S}_{w} \boldsymbol{w}_{i}\\}
\end{array}\right.
$$

上式可以通过如下广义特征值问题求解：

$$
\mathbf{S}_{b} \mathbf{W}=\lambda \mathbf{S}_{w} \mathbf{W}
$$

将$\mathbf{W}$视为一个投影矩阵，则多分类LDA将样本投影到$k$维空间，$k$通常远小于样本维度$d$。LDA也经常被视为一种监督降维方法。

参考资料

• 周志华《机器学习》
• [英]Peter Flach《机器学习》
• 吴恩达《机器学习》公开课
• https://datawhalechina.github.io/pumpkin-book/#/
• https://blog.csdn.net/wyl1813240346/article/details/78548274
• https://blog.csdn.net/Oxalis_Triangularis/article/details/47420521