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

时间:2022-10-02 07:54:18

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

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

西瓜书研读——第三章 线性模型:线性几率回归(逻辑回归)

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

3.4 线性判别分析 LDA

3.4.1 核心思想

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

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

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

  • 数据集 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 X_i Xi 表示第 i ∈ { 0 , 1 } i \in \left\{0,1\right\} i{0,1} 类示例的集合

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

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


知识补充:

1、协方差

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

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

    • 其中,方差的计算公式为
      σ x 2 = 1 n − 1 ∑ i = 1 n ( x i − x ˉ ) 2 \sigma_x^2=\frac{1}{n-1}\sum_{i=1}^n\left(x_i-\bar{x}\right)^2 σx2=n11i=1n(xixˉ)2
  • 协方差的计算公式被定义为

σ ( x , y ) = 1 n − 1 ∑ i = 1 n ( x i − x ˉ ) ( y i − y ˉ ) \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) σ(x,y)=n11i=1n(xixˉ)(yiyˉ)

我们发现:方差 σ x 2 \sigma_x^2 σx2可视作随机变量 x x x关于其自身的协方差 σ ( x , x ) \sigma\left(x,x\right) σ(x,x)

根据方差的定义,给定 d d d个随机变量 x k , k = 1 , 2 , . . . , d , x_k,k=1,2,...,d , xk,k=1,2,...,d则这些随机变量的方差
σ ( x k , x k ) = 1 n − 1 ∑ i = 1 n ( x k i − x ˉ k ) 2 , 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 σ(xk,xk)=n11i=1n(xkixˉk)2,k=1,2,...,d
x k i x_{ki} xki 表示随机变量 x k x_k xk 中的第$ i $个观测样本, $n 表示样本量,每个随机变量所对应的观测样本数量均为 表示样本量,每个随机变量所对应的观测样本数量均为 表示样本量,每个随机变量所对应的观测样本数量均为 n $。

对于这些随机变量,我们还可以根据协方差的定义,求出两两之间的协方差,即
σ ( x m , x k ) = 1 n − 1 ∑ i = 1 n ( x m i − x ˉ m ) ( x k i − x ˉ k ) \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) σ(xm,xk)=n11i=1n(xmixˉm)(xkixˉk)

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

2、内积

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

如下所示,对于向量a和向量b:
a = [ a 1 ; ⋯   ; a n ] ∈ R n × 1 b = [ b 1 ; ⋯   ; b n ] ∈ R n × 1 ⟨ a ⃗ , b ⃗ ⟩ = a ⃗ ⋅ b ⃗ = a ′ b = ∑ i = 1 n a i b i \mathbf{a}=\left[a_1;\cdots;a_n\right]\in\mathbb{R}^{n\times1}\\ \mathbf{b}=\left[b_1;\cdots;b_n\right]\in\mathbb{R}^{n\times1}\\ \langle\vec{a},\vec{b}\rangle=\vec{a}\cdot\vec{b}=\mathbf{a}^\prime\mathbf{b}=\sum_{i=1}^na_ib_i a=[a1;;an]Rn×1b=[b1;;bn]Rn×1a ,b =a b =ab=i=1naibi

由此想到矩阵乘法,相乘得到的矩阵就是对应向量
c 1 = [ a 1 a 2 a 3 ] [ b 1 b 2 b 3 ] = ∑ i = 1 3 a i b i c_1=\begin{bmatrix}a_1&a_2&a_3\end{bmatrix}\begin{bmatrix}b_1\\b_2\\b_3\end{bmatrix}=\sum_{i=1}^{3}{a_ib_i} c1=[a1a2a3] b1b2b3 =i=13aibi

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

几何意义

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

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

一般地, a ⃗ ⋅ b ⃗ = ∥ a ⃗ ∥ ∥ b ⃗ ∥ cos ⁡ θ \vec{a}\cdot\vec{b}=\parallel\vec{a}\parallel\parallel\vec{b}\parallel\cos\theta a b =∥a ∥∥b cosθ

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

3、范数

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

1范数:所有元素绝对值的和。
∣ ∣ x ∣ ∣ 1 = ∑ i = 1 N ∣ x i ∣ ||x||_1 = \sum_{i=1}^N|x_i| ∣∣x1=i=1Nxi
2范数:所有元素平方和的开方。
∣ ∣ x ∣ ∣ 2 = ∑ i = 1 N x i 2 ||\textbf{x}||_2 =\sqrt{\sum_{i=1}^Nx_i^2} ∣∣x2=i=1Nxi2
无穷范数:正无穷范数:所有元素中绝对值最小的。负无穷范数:所有元素中绝对值最大的。
∣ ∣ x ∣ ∣ ∞ = max ⁡ i ∣ x i ∣ ||\textbf{x}||_\infty = \max_{i}|x_i| ∣∣x=imaxxi


则两类样本的中心在直线上的投影分别为 w T u 0 、 w T u 1 w^Tu_0、w^Tu_1 wTu0wTu1

  • 经投影后异类样本尽可能远,则:

m a x   ∥ w T μ 0 − w T μ 1 ∥ 2 2 = ∥ ∣ w T ∥ μ 0 ∥ c o s θ 0 − ∣ w T ∥ μ 1 ∥ c o s θ 1 ∥ 2 2 max \, \|\boldsymbol w^{\mathrm{T}}\boldsymbol{\mu}_{0}-\boldsymbol w^{\mathrm{T}}\boldsymbol{\mu}_{1}\|_2^2 \\ = \||\boldsymbol w^{\mathrm{T}}\|\boldsymbol{\mu}_{0}\|cos\theta_0-|\boldsymbol w^{\mathrm{T}}\|\boldsymbol{\mu}_{1}\|cos\theta_1\|_2^2 \\ maxwTμ0wTμ122=∥∣wTμ0cosθ0wTμ1cosθ122

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

将所有样本都投影到直线上,则两类样本的方差分别为: w T ∑ 0 w 、 w T ∑ 1 w w^T\sum_0w、w^T\sum_1w wT0wwT1w,同类样本方差尽可能小,则:

m i n   w T ∑ 0 w = w T ( ∑ ( x − u 0 ) ( x − u 0 ) T ) w = ∑ ( w T x − w T u 0 ) ( w T x − w T u 0 ) T min \,w^T\sum_{0} w =w^T(\sum(x-u_0)(x-u_0)^T)w\\=\sum(w^Tx-w^Tu_0)(w^Tx-w^Tu_0)^T minwT0w=wT((xu0)(xu0)T)w=(wTxwTu0)(wTxwTu0)T

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

3.4.2 目标函数

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

m a x   J = ∥ w T μ 0 − w T μ 1 ∥ 2 2 w T ∑ 0 w + w T ∑ 1 w w (3.32) max \, J = \cfrac{\|\boldsymbol w^{\mathrm{T}}\boldsymbol{\mu}_{0}-\boldsymbol w^{\mathrm{T}}\boldsymbol{\mu}_{1}\|_2^2}{w^T\sum_0w+w^T\sum_1ww} \tag{3.32} maxJ=wT0w+wT1wwwTμ0wTμ122(3.32)
[推导]:
J = ∥ w T μ 0 − w T μ 1 ∥ 2 2 w T ( Σ 0 + Σ 1 ) w = ∥ ( w T μ 0 − w T μ 1 ) T ∥ 2 2 w T ( Σ 0 + Σ 1 ) w = ∥ ( μ 0 − μ 1 ) T w ∥ 2 2 w T ( Σ 0 + Σ 1 ) w = [ ( μ 0 − μ 1 ) T w ] T ( μ 0 − μ 1 ) T w w T ( Σ 0 + Σ 1 ) w = w T ( μ 0 − μ 1 ) ( μ 0 − μ 1 ) T w w T ( Σ 0 + Σ 1 ) w (3.32) \begin{aligned} J &= \cfrac{\|\boldsymbol w^{\mathrm{T}}\boldsymbol{\mu}_{0}-\boldsymbol w^{\mathrm{T}}\boldsymbol{\mu}_{1}\|_2^2}{\boldsymbol w^{\mathrm{T}}(\boldsymbol{\Sigma}_{0}+\boldsymbol{\Sigma}_{1})\boldsymbol w} \\ &= \cfrac{\|(\boldsymbol w^{\mathrm{T}}\boldsymbol{\mu}_{0}-\boldsymbol w^{\mathrm{T}}\boldsymbol{\mu}_{1})^{\mathrm{T}}\|_2^2}{\boldsymbol w^{\mathrm{T}}(\boldsymbol{\Sigma}_{0}+\boldsymbol{\Sigma}_{1})\boldsymbol w} \\ &= \cfrac{\|(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1})^{\mathrm{T}}\boldsymbol w\|_2^2}{\boldsymbol w^{\mathrm{T}}(\boldsymbol{\Sigma}_{0}+\boldsymbol{\Sigma}_{1})\boldsymbol w} \\ &= \cfrac{\left[(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1})^{\mathrm{T}}\boldsymbol w\right]^{\mathrm{T}}(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1})^{\mathrm{T}}\boldsymbol w}{\boldsymbol w^{\mathrm{T}}(\boldsymbol{\Sigma}_{0}+\boldsymbol{\Sigma}_{1})\boldsymbol w} \\ &= \cfrac{\boldsymbol w^{\mathrm{T}}(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1})(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1})^{\mathrm{T}}\boldsymbol w}{\boldsymbol w^{\mathrm{T}}(\boldsymbol{\Sigma}_{0}+\boldsymbol{\Sigma}_{1})\boldsymbol w} \end{aligned} \tag{3.32} J=wT(Σ0+Σ1)wwTμ0wTμ122=wT(Σ0+Σ1)w(wTμ0wTμ1)T22=wT(Σ0+Σ1)w(μ0μ1)Tw22=wT(Σ0+Σ1)w[(μ0μ1)Tw]T(μ0μ1)Tw=wT(Σ0+Σ1)wwT(μ0μ1)(μ0μ1)Tw(3.32)

定义:

  • 类内散度矩阵

S w = Σ 0 + Σ 1 = ∑ x ∈ X 0 ( x − μ 0 ) ( x − μ 0 ) T + ∑ x ∈ X 1 ( x − μ 1 ) ( x − μ 1 ) T \begin{align} \boldsymbol{S}_w & = \boldsymbol{\Sigma}_0 + \boldsymbol{\Sigma}_1 \\ & = \sum_{\boldsymbol{x} \in X_0}(\boldsymbol{x}-\boldsymbol{\mu}_0)(\boldsymbol{x}-\boldsymbol{\mu}_0)^{\text{T}} + \sum_{\boldsymbol{x} \in X_1}(\boldsymbol{x}-\boldsymbol{\mu}_1)(\boldsymbol{x}-\boldsymbol{\mu}_1)^{\text{T}} \end{align} Sw=Σ0+Σ1=xX0(xμ0)(xμ0)T+xX1(xμ1)(xμ1)T

  • 类间散度矩阵

S b = ( μ 0 − μ 1 ) ( μ 0 − μ 1 ) T \boldsymbol{S}_b = (\boldsymbol{\mu_{0}}-\boldsymbol{\mu_{1}})(\boldsymbol{\mu_{0}}-\boldsymbol{\mu_{1}})^{\text{T}} Sb=(μ0μ1)(μ0μ1)T

公式3.32可以写为:
J = w T S b w w T S w w (3.35) \begin{align} J & = \frac{\boldsymbol{w}^{\text{T}}\boldsymbol{S}_b\boldsymbol{w}}{\boldsymbol{w}^{\text{T}}\boldsymbol{S}_w\boldsymbol{w}} \end{align} \tag{3.35} J=wTSwwwTSbw(3.35)
这就是LSA欲最大化的目标函数,即 S w , S b S_w,S_b Sw,Sb的广义瑞利商(generalized Rayleigh quotient)

3.4.3 函数求解

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

  • 因此可假设, w T S w w = 1 \boldsymbol{w}^{\text{T}}\boldsymbol{S}_w\boldsymbol{w} = 1 wTSww=1,(当然也可以假设 w T S b w = 100 \boldsymbol{w}^{\text{T}}\boldsymbol{S}_b\boldsymbol{w} = 100 wTSbw=100 ∣ ∣ w ∣ ∣ = 1 ||w||=1 ∣∣w∣∣=1),这样就固定了w,则原广义瑞利商变为最大化 w T S b w \boldsymbol{w}^{\text{T}}\boldsymbol{S}_b\boldsymbol{w} wTSbw

  • 这样该优化问题就可以解了
    min ⁡ w − w T S b w s.t. w T S w w = 1 (3.36) \begin{align} \underset{\boldsymbol{w}}{\min} - \boldsymbol{w}^{\text{T}}\boldsymbol{S}_b\boldsymbol{w} \\ \text{s.t.} \quad \boldsymbol{w}^{\text{T}}\boldsymbol{S}_w\boldsymbol{w} = 1 \end{align} \tag{3.36} wminwTSbws.t.wTSww=1(3.36)
    一般优化问题都是求其最小最优解,在目标函数前加个符号就将最大化问题转换为了最小化问题。

知识补充:

拉格朗日乘子法 西瓜书研读——第三章 线性模型: 线性判别分析 LDA

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

由公式(3.36)可得拉格朗日函数为
L ( w , λ ) = − w T S b w + λ ( w T S w w − 1 ) L(\boldsymbol w,\lambda)=-\boldsymbol w^{\mathrm{T}}\mathbf{S}_b\boldsymbol w+\lambda(\boldsymbol w^{\mathrm{T}}\mathbf{S}_w\boldsymbol w-1) L(w,λ)=wTSbw+λ(wTSww1)
w \boldsymbol w w求偏导可得
∂ L ( w , λ ) ∂ w = − ∂ ( w T S b w ) ∂ w + λ ∂ ( w T S w w − 1 ) ∂ w = − ( S b + S b T ) w + λ ( S w + S w T ) w \begin{aligned} \cfrac{\partial L(\boldsymbol w,\lambda)}{\partial \boldsymbol w} &= -\cfrac{\partial(\boldsymbol w^{\mathrm{T}}\mathbf{S}_b\boldsymbol w)}{\partial \boldsymbol w}+\lambda \cfrac{\partial(\boldsymbol w^{\mathrm{T}}\mathbf{S}_w\boldsymbol w-1)}{\partial \boldsymbol w} \\ &= -(\mathbf{S}_b+\mathbf{S}_b^{\mathrm{T}})\boldsymbol w+\lambda(\mathbf{S}_w+\mathbf{S}_w^{\mathrm{T}})\boldsymbol w \end{aligned} wL(w,λ)=w(wTSbw)+λw(wTSww1)=(Sb+SbT)w+λ(Sw+SwT)w
由于 S b = S b T , S w = S w T \mathbf{S}_b=\mathbf{S}_b^{\mathrm{T}},\mathbf{S}_w=\mathbf{S}_w^{\mathrm{T}} Sb=SbT,Sw=SwT,所以
∂ L ( w , λ ) ∂ w = − 2 S b w + 2 λ S w w \cfrac{\partial L(\boldsymbol w,\lambda)}{\partial \boldsymbol w} = -2\mathbf{S}_b\boldsymbol w+2\lambda\mathbf{S}_w\boldsymbol w wL(w,λ)=2Sbw+2λSww
令上式等于0即可得
− 2 S b w + 2 λ S w w = 0 S b w = λ S w w -2\mathbf{S}_b\boldsymbol w+2\lambda\mathbf{S}_w\boldsymbol w=0 \\ \mathbf{S}_b\boldsymbol w=\lambda\mathbf{S}_w\boldsymbol w 2Sbw+2λSww=0Sbw=λSww
由于
S b w = ( μ 0 − μ 1 ) ( μ 0 − μ 1 ) T w \mathbf{S}_b\boldsymbol w = (\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1})(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1})^{\mathrm{T}}\boldsymbol{w} Sbw=(μ0μ1)(μ0μ1)Tw
所以
( μ 0 − μ 1 ) ( μ 0 − μ 1 ) T w = λ S w w \\ (\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1})(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1})^{\mathrm{T}}\boldsymbol{w}=\lambda\mathbf{S}_w\boldsymbol w (μ0μ1)(μ0μ1)Tw=λSww
若令 ( μ 0 − μ 1 ) T w = γ (\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1})^{\mathrm{T}}\boldsymbol{w}=\gamma (μ0μ1)Tw=γ(是个标量),则
γ ( μ 0 − μ 1 ) = λ S w w w = γ λ S w − 1 ( μ 0 − μ 1 ) \gamma(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1})=\lambda\mathbf{S}_w\boldsymbol w \\ \boldsymbol{w}=\frac{\gamma}{\lambda}\mathbf{S}_{w}^{-1}(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}) γ(μ0μ1)=λSwww=λγSw1(μ0μ1)

由于最终要求解的 w \boldsymbol{w} w不关心其大小,只关心其方向,所以其大小可以任意取值。由于 μ 0 \boldsymbol{\mu}_{0} μ0 μ 1 \boldsymbol{\mu}_{1} μ1的大小是固定的,所以 γ \gamma γ这个标量的大小只受 w \boldsymbol{w} w的大小影响,因此可以调整 w \boldsymbol{w} w的大小使得 γ = λ \gamma=\lambda γ=λ

由于 S b w = ( μ 0 − μ 1 ) ( μ 0 − μ 1 ) T w \mathbf{S}_b\boldsymbol w = (\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1})(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1})^{\mathrm{T}}\boldsymbol{w} Sbw=(μ0μ1)(μ0μ1)Tw ( μ 0 − μ 1 ) T w (\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1})^{\mathrm{T}}\boldsymbol{w} (μ0μ1)Tw是一个标量,所以 S b w \mathbf{S}_b\boldsymbol w Sbw的方向与 μ 0 − μ 1 \boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1} μ0μ1的方向一致,西瓜书中所说的“不妨令 S b w = λ ( μ 0 − μ 1 ) \mathbf{S}_b\boldsymbol w=\lambda(\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}) Sbw=λ(μ0μ1)”也等价于令 ( μ 0 − μ 1 ) T w = γ = λ (\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1})^{\mathrm{T}}\boldsymbol{w}=\gamma= \lambda (μ0μ1)Tw=γ=λ,因此,此时 γ λ = 1 \frac{\gamma}{\lambda}=1 λγ=1,求解出的 w \boldsymbol{w} w即为公式(3.39)
w = S w − 1 ( μ 0 − μ 1 ) (3.39) \boldsymbol{w} = \boldsymbol{S}_w^{-1}(\boldsymbol{\mu}_0 - \boldsymbol{\mu}_1) \tag{3.39} w=Sw1(μ0μ1)(3.39)

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


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

S w = U Σ U T S_w=UΣU^T Sw=UΣUT S w − 1 = V Σ − 1 U T S_{w}^{-1}=VΣ^{-1}U^T Sw1=VΣ1UT

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


知识补充

广义特征值

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

广义瑞利商

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

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

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


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编码越长,纠错能力越强

    • 编码越长,付出的代价是所需训练的分类器越多,计算、存储开销都会增大
    • 对有限类别数,可能的组合数目是有限的,码长超过一定范围后就失去了意义
  • 对同等长度的编码,理论上来说,任意两个类别之间的编码距离越远,纠错能力越强

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