机器学习——线性模型
本文最后更新于 545 天前,其中的信息可能已经有所发展或是发生改变。

线性回归

给定由$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也经常被视为一种监督降维方法。

参考资料

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇