西瓜书研读——第三章 线性模型： 线性判别分析 LDA

西瓜书研读系列：
西瓜书研读——第三章 线性模型：一元线性回归

西瓜书研读——第三章 线性模型：多元线性回归

西瓜书研读——第三章 线性模型：线性几率回归（逻辑回归）

• 主要教材为西瓜书，结合南瓜书，统计学习方法，B站视频整理~
• 人群定位：学过高数会求偏导、线代会矩阵运算、概率论知道啥是概率
• 原理讲解，公式推导，课后习题，实践代码应有尽有，欢迎订阅

3.4 线性判别分析 LDA

3.4.1 核心思想

给定训练样例集，设法将高维的样例投影到一条直线（最佳鉴别矢量空间）上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离，即模式在该空间中有最佳的可分离性。

将训练样本投影到一条直线上，使得同类的样例尽可能近，不同类的样例尽可能远。如图所示：

​

​

• 数据集 D = { ( x _ i , y i ) } i = 1 m , y i ∈ { 0 , 1 } D=\left\{ (\boldsymbol{x}\_i,y_i) \right\}_{i=1}^m,y_i \in \left\{0,1\right\} D={(x_i,yi​)}i=1m​,yi​∈{0,1}

• $X_i$ 表示第 i ∈ { 0 , 1 } i \in \left\{0,1\right\} i∈{0,1} 类示例的集合

• ${\mathbf{\mu }}_i$ 表示第 i ∈ { 0 , 1 } i \in \left\{0,1\right\} i∈{0,1} 类示例的均值向量(样本的中心)

• ${\mathbf{\Sigma }}_i$ 表示第 i ∈ { 0 , 1 } i \in \left\{0,1\right\} i∈{0,1} 类示例的协方差矩阵

---

知识补充：

1、协方差

• 方差：方差是用来度量单个随机变量的离散程度，当随机变量的可能值集中在数学期望的附近时，方差较小； 反之， 则方差较大。方差能反映随机变量的一切可能值在数学期望周围的分散程度。

• 而协方差则一般用来刻画两个随机变量的相似程度，如果结果为正值，则说明两者是正相关的，否则是负相关的。需要注意的是，协方差是计算不同特征之间的统计量，不是不同样本之间的统计量。

  • 其中，方差的计算公式为
    $${\sigma }_x^2=\frac{1}{n-1}\sum _{i=1}^n{\left(x_i-\bar{x}\right)}^2$$

• 协方差的计算公式被定义为

$$\sigma \left(x,y\right)=\frac{1}{n-1}\sum _{i=1}^n\left(x_i-\bar{x}\right)\left(y_i-\bar{y}\right)$$

我们发现：方差 ${\sigma }_x^2$可视作随机变量$x$关于其自身的协方差$\sigma \left(x,x\right)$

根据方差的定义，给定$d$个随机变量 $x_k,k=1,2,...,d，$则这些随机变量的方差为
$$\sigma (x_k,x_k)=\frac{1}{n-1}\sum _{i=1}^n{\left(x_{ki}-{\bar{x}}_k\right)}^2,k=1,2,...,d$$
$x_{ki}$ 表示随机变量 $x_k$ 中的第$ i $个观测样本， $n $表示样本量，每个随机变量所对应的观测样本数量均为$ n $。

对于这些随机变量，我们还可以根据协方差的定义，求出两两之间的协方差，即
$$\sigma \left(x_m,x_k\right)=\frac{1}{n-1}\sum _{i=1}^n\left(x_{mi}-{\bar{x}}_m\right)\left(x_{ki}-{\bar{x}}_k\right)$$

因此，协方差矩阵为:
$$\Sigma =\left[\begin{array}{c}\sigma (x_1,x_1)\cdots \sigma \left(x_1,x_d\right)\\ ⋮\ddots ⋮\\ \sigma \left(x_d,x_1\right)\cdots \sigma (x_d,x_d)\end{array}\right]\in {\mathbb{R}}^{d\times d}$$
其中，对角线上的元素为各个随机变量的方差，非对角线上的元素为两两随机变量之间的协方差，根据协方差的定义，我们可以认定：矩阵$\Sigma$ 为对称矩阵(symmetric matrix)，其大小为$ d×d$ 。

2、内积

内积（点乘/数量积）是对两个向量执行点乘运算，就是对这两个向量对应位一一相乘之后求和的操作，是一个标量。

如下所示，对于向量a和向量b：
$$\begin{gathered} \mathbf{a}=\left[a_1;\cdots ;a_n\right]\in {\mathbb{R}}^{n\times 1} \\ \mathbf{b}=\left[b_1;\cdots ;b_n\right]\in {\mathbb{R}}^{n\times 1} \\ ⟨\vec{a},\vec{b}⟩=\vec{a}\cdot \vec{b}={\mathbf{a}}^{\prime }\mathbf{b}=\sum _{i=1}^n{a}_i{b}_i \end{gathered}$$

由此想到矩阵乘法，相乘得到的矩阵就是对应向量
$$c_1=\left[\begin{array}{ccc}{a}_1& a_2& a_3\end{array}\right]\left[\begin{array}{c}{b}_1\\ b_2\\ b_3\end{array}\right]=\sum _{i=1}^3{a}_i{b}_i$$

几何意义

当两个向量都是单位向量时，表示两个向量之间的夹角的余弦

当一个是单位向量时，表示另外一个向量在这个单位向量方向上的投影长度。

一般地，$\vec{a}\cdot \vec{b}=\parallel \vec{a}\parallel \parallel \vec{b}\parallel \cos \theta$

概括而言，可以这样来理解向量内积：向量a、b的内积等于向量a在b方向的分量（或投影）与b的乘积，当a、b垂直时，a在b方向上无分量，所以内积为0。

3、范数

是具有“长度”概念的函数。是矢量空间内的所有矢量赋予非零的正长度或大小。

1范数：所有元素绝对值的和。
$$||x|{|}_1=\sum _{i=1}^N|x_i|$$
2范数：所有元素平方和的开方。
$$||\text{x}|{|}_2=\sqrt{\sum _{i=1}^N{x}_i^2}$$
无穷范数：正无穷范数：所有元素中绝对值最小的。负无穷范数：所有元素中绝对值最大的。
$$||\text{x}|{|}_{\infty }=\underset{i}{\max }|x_i|$$

---

则两类样本的中心在直线上的投影分别为$w^T{u}_0、w^T{u}_1$

• 经投影后异类样本尽可能远，则：

$$\begin{gathered} max\Vert {\mathbf{w}}^{\mathrm{T}}{\mathbf{\mu }}_0-{\mathbf{w}}^{\mathrm{T}}{\mathbf{\mu }}_1{\Vert }_2^2 \\ =\Vert |{\mathbf{w}}^{\mathrm{T}}\Vert {\mathbf{\mu }}_0\Vert cos{\theta }_0-|{\mathbf{w}}^{\mathrm{T}}\Vert {\mathbf{\mu }}_1\Vert cos{\theta }_1{\Vert }_2^2 \end{gathered}$$

注：这里并不是严格的投影长度，而是放大后的，因为乘了个$|{\mathbf{w}}^{\mathrm{T}}|$，但这并不影响求最大值，乘上w的模后更方便矩阵计算。

将所有样本都投影到直线上，则两类样本的方差分别为：$w^T{\sum }_{0}w、w^T{\sum }_{1}w$，同类样本方差尽可能小，则：

$$\begin{gathered} min{w}^T\sum _{0}w=w^T(\sum (x-u_0)(x-u_0{)}^T)w \\ =\sum (w^{T}x-w^T{u}_0)(w^{T}x-w^T{u}_0{)}^T \end{gathered}$$

注：书上说是协方差，其实应该是方差，协方差是用来刻画两个随机变量的相似程度，而方差是刻画同一样本直接的离散程度。这里${\sum }_0$应该是方差。

3.4.2 目标函数

要同时考虑一类样本尽可能远，同类样本尽肯能近，同时考虑二者，所以可以用以下目标函数：

$$maxJ=\frac{\Vert {\mathbf{w}}^{\mathrm{T}}{\mathbf{\mu }}_0-{\mathbf{w}}^{\mathrm{T}}{\mathbf{\mu }}_1{\Vert }_2^2}{w^T{\sum }_{0}w+w^T{\sum }_{1}ww}\text{\hspace{1em}(3.32)}$$
[推导]：
$$\begin{array}{rl}J& =\frac{\Vert {\mathbf{w}}^{\mathrm{T}}{\mathbf{\mu }}_0-{\mathbf{w}}^{\mathrm{T}}{\mathbf{\mu }}_1{\Vert }_2^2}{{\mathbf{w}}^{\mathrm{T}}({\mathbf{\Sigma }}_0+{\mathbf{\Sigma }}_1)\mathbf{w}}\\ & =\frac{\Vert ({\mathbf{w}}^{\mathrm{T}}{\mathbf{\mu }}_0-{\mathbf{w}}^{\mathrm{T}}{\mathbf{\mu }}_1{)}^{\mathrm{T}}{\Vert }_2^2}{{\mathbf{w}}^{\mathrm{T}}({\mathbf{\Sigma }}_0+{\mathbf{\Sigma }}_1)\mathbf{w}}\\ & =\frac{\Vert ({\mathbf{\mu }}_0-{\mathbf{\mu }}_1{)}^{\mathrm{T}}\mathbf{w}{\Vert }_2^2}{{\mathbf{w}}^{\mathrm{T}}({\mathbf{\Sigma }}_0+{\mathbf{\Sigma }}_1)\mathbf{w}}\\ & =\frac{{\left[({\mathbf{\mu }}_0-{\mathbf{\mu }}_1{)}^{\mathrm{T}}\mathbf{w}\right]}^{\mathrm{T}}({\mathbf{\mu }}_0-{\mathbf{\mu }}_1{)}^{\mathrm{T}}\mathbf{w}}{{\mathbf{w}}^{\mathrm{T}}({\mathbf{\Sigma }}_0+{\mathbf{\Sigma }}_1)\mathbf{w}}\\ & =\frac{{\mathbf{w}}^{\mathrm{T}}({\mathbf{\mu }}_0-{\mathbf{\mu }}_1)({\mathbf{\mu }}_0-{\mathbf{\mu }}_1{)}^{\mathrm{T}}\mathbf{w}}{{\mathbf{w}}^{\mathrm{T}}({\mathbf{\Sigma }}_0+{\mathbf{\Sigma }}_1)\mathbf{w}}\end{array}\text{\hspace{1em}(3.32)}$$

定义：

• 类内散度矩阵

$$\begin{array}{rl}{\mathbf{S}}_w& ={\mathbf{\Sigma }}_0+{\mathbf{\Sigma }}_1\\ & =\sum _{\mathbf{x}\in X_0}(\mathbf{x}-{\mathbf{\mu }}_0)(\mathbf{x}-{\mathbf{\mu }}_0{)}^{\text{T}}+\sum _{\mathbf{x}\in X_1}(\mathbf{x}-{\mathbf{\mu }}_1)(\mathbf{x}-{\mathbf{\mu }}_1{)}^{\text{T}}\end{array}$$

• 类间散度矩阵

$${\mathbf{S}}_b=({\mathbf{\mu }}_0-{\mathbf{\mu }}_1)({\mathbf{\mu }}_0-{\mathbf{\mu }}_1{)}^{\text{T}}$$

公式3.32可以写为：
$$\begin{array}{rl}J& =\frac{{\mathbf{w}}^{\text{T}}{\mathbf{S}}_b\mathbf{w}}{{\mathbf{w}}^{\text{T}}{\mathbf{S}}_w\mathbf{w}}\end{array}\text{\hspace{1em}(3.35)}$$
这就是LSA欲最大化的目标函数，即$S_w,S_b$的广义瑞利商（generalized Rayleigh quotient）

3.4.3 函数求解

• 分子分母都是关于 $\mathbf{w}$ 的二次项，该优化问题硬解是解不出w的，因为是比例，上下都有w，最终可以约分，如$W=aw$，这样就是多个解。但w的大小是不影响最终结果的。

• 因此可假设，${\mathbf{w}}^{\text{T}}{\mathbf{S}}_w\mathbf{w}=1$，（当然也可以假设${\mathbf{w}}^{\text{T}}{\mathbf{S}}_b\mathbf{w}=100$或$||w||=1$）,这样就固定了w，则原广义瑞利商变为最大化 ${\mathbf{w}}^{\text{T}}{\mathbf{S}}_b\mathbf{w}$

• 这样该优化问题就可以解了
  $$\begin{array}{r}\underset{\mathbf{w}}{\min }-{\mathbf{w}}^{\text{T}}{\mathbf{S}}_b\mathbf{w}\\ \text{s.t.}{\mathbf{w}}^{\text{T}}{\mathbf{S}}_w\mathbf{w}=1\end{array}\text{\hspace{1em}(3.36)}$$
  一般优化问题都是求其最小最优解，在目标函数前加个符号就将最大化问题转换为了最小化问题。

知识补充：

拉格朗日乘子法

只能保证是极值点，不能保证是极大值还是极小值，要具体分析

由公式(3.36)可得拉格朗日函数为
$$L(\mathbf{w},\lambda )=-{\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_b\mathbf{w}+\lambda ({\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_w\mathbf{w}-1)$$
对$\mathbf{w}$求偏导可得
$$\begin{array}{rl}\frac{\partial L(\mathbf{w},\lambda )}{\partial \mathbf{w}}& =-\frac{\partial ({\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_b\mathbf{w})}{\partial \mathbf{w}}+\lambda \frac{\partial ({\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_w\mathbf{w}-1)}{\partial \mathbf{w}}\\ & =-({\mathbf{S}}_b+{\mathbf{S}}_b^{\mathrm{T}})\mathbf{w}+\lambda ({\mathbf{S}}_w+{\mathbf{S}}_w^{\mathrm{T}})\mathbf{w}\end{array}$$
由于${\mathbf{S}}_b={\mathbf{S}}_b^{\mathrm{T}},{\mathbf{S}}_w={\mathbf{S}}_w^{\mathrm{T}}$，所以
$$\frac{\partial L(\mathbf{w},\lambda )}{\partial \mathbf{w}}=-2{\mathbf{S}}_b\mathbf{w}+2\lambda {\mathbf{S}}_w\mathbf{w}$$
令上式等于0即可得
$$\begin{gathered} -2{\mathbf{S}}_b\mathbf{w}+2\lambda {\mathbf{S}}_w\mathbf{w}=0 \\ {\mathbf{S}}_b\mathbf{w}=\lambda {\mathbf{S}}_w\mathbf{w} \end{gathered}$$
由于
$${\mathbf{S}}_b\mathbf{w}=({\mathbf{\mu }}_0-{\mathbf{\mu }}_1)({\mathbf{\mu }}_0-{\mathbf{\mu }}_1{)}^{\mathrm{T}}\mathbf{w}$$
所以
$$({\mathbf{\mu }}_0-{\mathbf{\mu }}_1)({\mathbf{\mu }}_0-{\mathbf{\mu }}_1{)}^{\mathrm{T}}\mathbf{w}=\lambda {\mathbf{S}}_w\mathbf{w}$$
若令$({\mathbf{\mu }}_0-{\mathbf{\mu }}_1{)}^{\mathrm{T}}\mathbf{w}=\gamma$（是个标量），则
$$\begin{gathered} \gamma ({\mathbf{\mu }}_0-{\mathbf{\mu }}_1)=\lambda {\mathbf{S}}_w\mathbf{w} \\ \mathbf{w}=\frac{\gamma }{\lambda }{\mathbf{S}}_w^{-1}({\mathbf{\mu }}_0-{\mathbf{\mu }}_1) \end{gathered}$$

由于最终要求解的$\mathbf{w}$不关心其大小，只关心其方向，所以其大小可以任意取值。由于${\mathbf{\mu }}_0$和${\mathbf{\mu }}_1$的大小是固定的，所以$\gamma$这个标量的大小只受$\mathbf{w}$的大小影响，因此可以调整$\mathbf{w}$的大小使得$\gamma =\lambda$

由于${\mathbf{S}}_b\mathbf{w}=({\mathbf{\mu }}_0-{\mathbf{\mu }}_1)({\mathbf{\mu }}_0-{\mathbf{\mu }}_1{)}^{\mathrm{T}}\mathbf{w}$， $({\mathbf{\mu }}_0-{\mathbf{\mu }}_1{)}^{\mathrm{T}}\mathbf{w}$是一个标量，所以${\mathbf{S}}_b\mathbf{w}$的方向与${\mathbf{\mu }}_0-{\mathbf{\mu }}_1$的方向一致，西瓜书中所说的“不妨令${\mathbf{S}}_b\mathbf{w}=\lambda ({\mathbf{\mu }}_0-{\mathbf{\mu }}_1)$”也等价于令$({\mathbf{\mu }}_0-{\mathbf{\mu }}_1{)}^{\mathrm{T}}\mathbf{w}=\gamma =\lambda$，因此，此时$\frac{\gamma }{\lambda }=1$，求解出的$\mathbf{w}$即为公式(3.39)
$$\mathbf{w}={\mathbf{S}}_w^{-1}({\mathbf{\mu }}_0-{\mathbf{\mu }}_1)\text{\hspace{1em}(3.39)}$$

---

考虑到数值解的稳定性，在实践中通常是对$S_w$进行奇异值分解。

即 $S_w=U\Sigma U^T$，$S_w^{-1}=V{\Sigma }^{-1}{U}^T$

值得注意的是，LSA还可以从贝叶斯决策理论的角度来阐释，具体在学到贝叶斯模型的时候说。

---

知识补充

广义特征值

广义瑞利商

厄米矩阵可以理解为复数 域上的转置矩阵

---

3.5 多分类学习

拆解法

基本思路

• 即将多分类任务拆分为若干个二分类任务求解
• 具体来说，先对问题进行拆分，然后为拆出的每个二分类任务训练一个分类器；在测试时，对这些分类器的预测结果进行集成以获得最终的多分类结果

拆分策略

• “一对一”（One vs. One，简称 OvO）
• “一对其余”（One vs. Rest，简称 OvR）
• “多对多”（Many vs. Many，简称 MvM）

OvO

• 将这N个类别两两配对，从而产生N(N-1)/2个二分类任务
• 在测试阶段，新样本将同时提交给所有分类器，欲使我们将得到N(N-1)/2个分类结果，最终结果通过投票产生

OvR

• 每次将一个类的样例作为正例、所有其他类的样例作为反例来训练N个分类器
• 在测试阶段，若仅有一个分类器预测为正类，则对应的类别标记作为最终结果分类

对比

• 在测试时，OvO的存储开销和测试时间开销通常比OvR更大
• 在训练时，OvR的每个分类器均使用全部的训练样例，而OvO得每个分类器仅用到两个类的样例，训练开销比较小

MvM

每次将若干个类作为正类，若干个其他类作为反类

纠错输出码（Error Correcting Output Codes，简称 ECOC）

工作过程

• 编码

  • 对N个类别做M次划分，每次划分将一部分类别划为正类，一部分划为反类，从而形成一个二分类训练集
  • 这样一共产生M个训练集，可训练出M个分类器

• 解码

  • M个分类器分别对测试样本进行预测，这些预测标记形成一个编码
  • 将这个预测编码与每个类别各自的编码进行比较，返回其中距离最小的类别作为最终预测结果

编码矩阵 （coding matrix）

• 常见形式

  • 二元码: (正类\反类)

  • 三元码:(正类\反类\停用类)

为什么称“纠错输出码”？

• 在测试阶段，ECOC编码对分类器的错误有一定的容忍和修正能力

• 一般来说，对同一个学习任务，ECOC编码越长，纠错能力越强

  • 编码越长，付出的代价是所需训练的分类器越多，计算、存储开销都会增大
  • 对有限类别数，可能的组合数目是有限的，码长超过一定范围后就失去了意义

• 对同等长度的编码，理论上来说，任意两个类别之间的编码距离越远，纠错能力越强

  • 码长较小时可根据这个原则计算出理论最优编码，然而码长稍大一些就难以有效地确定最优编码
  • 并不是编码的理论性质越好，分类性能就越好