[吃瓜教程]南瓜书第3章二分类线性判别分析

1.算法原理（模型）

线性判别分析（Linear Discriminant Analysis,LDA）是一种经典的线性学习方法，亦称为Fisher判别分析。
LDA 的思想：
给定训练样本集，将全体样本投影到一条直线上，使的：

• 同类样例的投影点总体尽可能接近/同类样本的方差尽可能小；
• 异类样本的投影点总体尽可能远离/异类样本的中心尽可能远；
• 

2.损失函数推导（策略）

2.0 补充

1.范数（Norm） 是一个在向量空间中用于量度向量大小的函数。它满足以下性质：

1. 非负性：对于任何向量x，有||x|| $\ge$ 0且||x||=0当且仅当x=0;
2. 齐次性（正齐次性）：对于任何标量$\alpha$和任何向量x,有$||\alpha x||=|\alpha |||x||$
3. 三角不等式：对于任何向量x和y，有$||x+y||\le ||x||+||y||$

一般的p-范数定义为：
$\Vert \mathbf{x}{\Vert }_p={\left({\sum }_{i=1}^n|x_i{|}^p\right)}^{\frac{1}{p}}$

2.协方差和协方差矩阵：
方差和协方差是统计学中用于描述数据分布和关系的重要指标。
方差
方差是描述一个随机变量的离散程度的度量，表示数据点与均值之间的偏离程度。
公式
样本方差：
$s^2=\frac{1}{n-1}{\sum }_{i=1}^n(x_i-\bar{x}{)}^2$
总体方差：
${\sigma }^2=\frac{1}{N}{\sum }_{i=1}^N(x_i-\mu {)}^2$
协方差
协方差是描述两个随机变量之间的线性关系的度量。它反映了一个变量变化时另一个变量的变化方向。
公式
样本方差：
$\text{cov}(X,Y)=\frac{1}{n-1}{\sum }_{i=1}^n(x_i-\bar{x})(y_i-\bar{y})$
总体方差：
${\sigma }_{XY}=\frac{1}{N}{\sum }_{i=1}^N(x_i-{\mu }_X)(y_i-{\mu }_Y)$
协方差矩阵：

2.1推导过程

设要投影的直线为 $\mathbf{\omega }$，${\mu }_0,{\mu }_1$分别表示反例集合和正例集合的均值向量，${\theta }_0,{\theta }_1$分别表示反例集合和正例集合的均值向量与投影直线的夹角， 围绕上面思想中的中心和方差两个点来进行推导：
1.异类样本的中心要尽可能远：
$$|{\mu }_0|cos\theta 表示{\mu }_0到\omega 的投影的长$$
为了实现异类样本的中心尽可能的远，那么就应该求下式：
$$max||(|{\mu }_0|cos\theta -|{\mu }_1|cos\theta )|{|}_2^2$$
在看上面的式子，发现这个$\theta$不好得到，那就进一步化，在上式中乘以一个常量（不会影响求最大值）$|\omega |$，注意这里是减完之后是个向量，因此要用到范数来衡量向量大小，而平方是为了简化计算，得到，
$$max||(|\omega ||{\mu }_0|cos\theta -|\omega ||{\mu }_1|cos\theta )|{|}_2^2$$
即得到，
$$max||{\omega }^T{\mu }_0-{\omega }^T{\mu }_1|{|}_2^2$$
2.同类样本的方差要尽可能小：
$$min({\omega }^T(\sum _0+\sum _1)\omega )$$

最终得到损失函数：
$$\begin{gathered} maxJ=max(\frac{||{\omega }^T{\mu }_0-{\omega }^T{\mu }_1|{|}_2^2}{{\omega }^T{\sum }_0\omega +{\omega }^T{\sum }_1\omega }) \\ ------------- \\ =max(\frac{||({\omega }^T{\mu }_0-{\omega }^T{\mu }_1{)}^T|{|}_2^2}{{\omega }^T({\sum }_0+{\sum }_1)\omega }) \\ ------------- \\ =max(\frac{||({\mu }_0-{\mu }_1{)}^T\omega |{|}_2^2}{{\omega }^T({\sum }_0+{\sum }_1)\omega }) \\ ------------- \\ =max(\frac{[({\mu }_0-{\mu }_1{)}^T\omega {]}^T({\mu }_0-{\mu }_1{)}^T\omega }{{\omega }^T({\sum }_0+{\sum }_1)\omega }) \\ ------------- \\ =max(\frac{{\omega }^T({\mu }_0-{\mu }_1)({\mu }_0-{\mu }_1{)}^T\omega }{{\omega }^T({\sum }_0+{\sum }_1)\omega }) \end{gathered}$$
第一步到第二步是可以这么理解：1*1的向量转置不变。
进一步，把上面的式子的中间部分记作$S_b$,下面式子的中间部分记作$S_w$,得到：
$$maxJ=\frac{w^T{S}_{b}w}{w^T{S}_{w}w}$$
转化为最小化：
$$\begin{gathered} min-w^T{S}_{b}w \\ s.t.w^T{S}_{w}w=1 \end{gathered}$$

3.求解w（算法)

3.0 补充：拉格朗日乘子法

拉格朗日乘子法是一种在约束条件下求解多元函数极值的数学方法。它通过引入拉格朗日乘子，将约束优化问题转换为无约束优化问题。该方法特别适用于等式约束的情况。
拉格朗日乘子法的步骤
**1.构造拉格朗日函数：**将目标函数和约束条件结合，形成拉格朗日函数。
$$\mathcal{L}(x_1,x_2,\dots ,x_n,{\lambda }_1,{\lambda }_2,\dots ,{\lambda }_m)=f(x_1,x_2,\dots ,x_n)+\sum _{i=1}^m{\lambda }_i{g}_i(x_1,x_2,\dots ,x_n)$$
**2.求拉格朗日函数的偏导数：**对所有变量求偏导数，并令这些偏导数等于零，得到一组方程。
$$\frac{\partial \mathcal{L}}{\partial x_j}=0(j=1,2,\dots ,n)$$
$$\frac{\partial \mathcal{L}}{\partial {\lambda }_i}=0(i=1,2,\dots ,m)$$
3.解方程组： 通过解上一步得到的方程组,得到值。

3.1求解w过程

由拉格朗日乘子法可得到拉格朗日函数为：
$$L(w,\lambda )=-w^T{S}_{b}w+\lambda (w^T{S}_{w}w-1)$$
对w求偏导得到(使用矩阵微分公式)
$$\begin{gathered} \frac{\partial L(w,\lambda )}{\partial w}=-\frac{\partial (w^T{S}_{b}w)}{\partial w}+\lambda \frac{\partial (w^T{S}_{w}w-1)}{\partial w} \\ ------- \\ =-(S_b+S_b^T)w+\lambda (S_W+S_w^T)w \\ ------- \\ =-2S_{b}w+2\lambda S_{w}w \end{gathered}$$
令上式等于0得到，
$$-2S_{b}w+2\lambda S_{w}w=0$$
$$\lambda S_{w}w=S_{b}w$$
$$\lambda S_{w}w=({\mu }_0-{\mu }_1)({\mu }_0-{\mu }_1{)}^{T}w$$
若令$({\mu }_0-{\mu }_1{)}^{T}w=\gamma$（一个数）,则
$$\lambda S_{w}w=({\mu }_0-{\mu }_1)\gamma$$
$$w=\frac{\gamma }{\lambda }{S}_w^{-1}({\mu }_0-{\mu }_1)$$
由于不关心w的大小只关心方向，所以可令$\gamma =\lambda$,即得到最终的求解公式。

4.广义特征值和广义利瑞商

4.1广义特征值

设A,B为n阶方阵，若存在数$\lambda$,使得方程$Ax=\lambda Bx$存在非零解，则称$\lambda$为A相对于B 的广义特征值，x为A 相对于B的属于广义特征值$\lambda$的特征向量。特别的，当B=I（单位矩阵）时，广义特征值问题退化为标准特征值问题。

4.2广义利瑞商

设A，B为n阶厄米（Hermitian）矩阵，且B 正定，称$R(x)=\frac{x^{H}Ax}{x^{H}Bx}(x\ne 0)$为A相对于B 的广义瑞利商。特别的，当B=I（单位矩阵）时，广义瑞利商退化为瑞利商。
性质：
设${\lambda }_i,x_i(i=1,2,...,n)$为A相对于B的广义特征值和特征向量，且${\lambda }_1\le {\lambda }_2\le ...\le {\lambda }_n$。
$$mi{n}_{x\ne 0}R(x)=\frac{x^{H}Ax}{x^{H}Bx}={\lambda }_1,x^{\ast }=x_1$$
$$ma{x}_{x\ne 0}R(x)=\frac{x^{H}Ax}{x^{H}Bx}={\lambda }_n,x^{\ast }=x_n$$
上述性质可用来证明多分类线性判别分析