整理

回归任务，线性判别分析，多分类学习

类别不平衡问题

1、最小二乘法背景知识：

对于线性方程组Ax=b ，称能使f(x)=||Ax-b||_2 达到极小的\hat x 为方程组的最小二乘解

任意线性方程组的最小二乘解总是存在的

任意\eta 是线性方程组Ax=b 的最小二乘解当且仅当\eta 是线性方程组A^TAx=A^Tb 的解

必要性证明：

令f(x)=||Ax-b||_2^2=\sum_{i=1}^m(\sum_{j=1}^na_{ij}x_j-b_i)^2 ，则\frac{\partial f}{\partial x_j^*}=0\Leftrightarrow 2\sum_{i=1}^m(\sum_{j=1}^na_{ij}x_j-b_i)a_{ij^*}=0\Leftrightarrow \sum_{j=1}^n(\sum_{i=1}^ma_{ij^*}a_{ij})x_{ij}=\sum_{i=1}^ma_{ij^*}b_i ，

联立j^*=1,2,...,n ，得到A^TAx=A^Tb

满秩分解：对于A_{m\times n} ，若rank(A)=r ，则可做分解A=FG ，其中F_{m\times r},G_{r\times n} 分别是列满秩矩阵和行满秩矩阵

直交分解（QU分解）：对于A_{m\times n} ，若rank(A)=r ，则可做分解A=FG ，其中F_{m\times r},G_{r\times n} 分别是列满秩的正交矩阵和行满秩矩阵

直交三角分解（QR分解）：对于A_{m\times n} ，rank(A)=n ，则可做分解A=FG ，其中F_{m\times n},G_{n\times n} 分别是列满秩的正交矩阵和满秩矩阵

奇异值分解：对于A_{m\times n} ，可做分解A=UDV^T ，其中U_{m\times m},V_{n\times n} 是正交矩阵，D=diag(\sigma_1,\sigma_2,...,\sigma_p),\sigma_1\ge\sigma_2\ge...\ge\sigma_p\ge0,p=\min(m,n)

三种分解给出了求出最小二乘解的一系列方法

由前三种分解可得到极小最小二乘解\hat x=G^T(GG^T)^{-1}(F^TF)^{-1}F^Tb

2、解法

目标是求得(\omega^T,b) 使均方误差最小化，(\omega^*,b^*)=\arg\min_{(\omega,b)}\sum_{i=1}^m(f(x_i)-y_i)^2=\arg\min_{(\omega,b)}\sum_{i=1}^m(\omega^Tx_i+b-y_i)^2

其中f(x)=\omega^Tx+b,\hat \omega=(\omega^T,b)^T,\hat x=(x^T,1)^T ，则f(x)=\hat\omega^T\hat x

令E(\hat\omega)=\sum_{i=1}^m(f(x_i)-y_i)^2=\sum_{i=1}^m(\sum_{j=1}^{n+1}\hat\omega_j\hat x_{ij}-y_i)^2 ，则由上知，令\frac{\partial E}{\partial\hat\omega_{j^*}}=0 ，并联立j^*=1,2,...,n+1

得到\hat X^T\hat X\hat\omega=\hat X^T Y

因此回归任务可归结为求最小二乘解，再归结为分解矩阵\hat X ，可做满秩分解，直交分解，直交三角分解和奇异值分解从而得到最小二乘解

1、对于二分类任务

定义类间散度矩阵为S_b=(\mu_0-\mu_1)(\mu_0-\mu_1)^T

类内散度矩阵为S_\omega=(\Sigma_0+\Sigma_1)=\sum_{x\in X_0}(x-\mu_0)(x-\mu_0)^T+\sum_{x\in X_1}(x-\mu_1)(x-\mu_1)^T

则目标函数可变形为J=\frac{||\omega^T\mu_0-\omega^T\mu_1||_2^2}{\omega^T(\Sigma_0+\Sigma_1)\omega}=\frac{\omega^T(\mu_0-\mu_1)(\mu_0-\mu_1)^T\omega}{\omega^T(\Sigma_0+\Sigma_1)\omega}=\frac{\omega^TS_b\omega}{\omega^TS_\omega\omega}

由于目标函数大小与\omega 大小无关，只与其方向有关，所以原问题等价于约束优化问题\min -\omega^TS_b\omega,\omega^TS_\omega\omega=1

由拉格朗日乘子法，令L_\omega(\omega,\lambda)=0 ，即\frac{\partial(-\omega^TS_b\omega+\lambda(\omega^TS_\omega\omega-1))}{\partial\omega_i}=0,i=1,2,...,n

得到广义特征值问题S_b\omega=\lambda S_\omega\omega

2、对于多分类任务，希望将数据降维，得到降维矩阵W

令类内散度矩阵为S_W=\sum_{i=1}^NS_{W_i},S_{W_i}=\sum_{x\in X_i}(x-\mu_i)(x-\mu_i)^T

全局散度矩阵为S=\sum_{x\in X}(x-\mu)(x-\mu)^T

类间散度矩阵为S_b=S-S_W=\sum_{i=1}^Nm_i(\mu_i-\mu)(\mu_i-\mu)^T

其目标函数是\max J(W)=\frac{\det(W^TS_bW)}{\det(W^TS_WW)}or\frac{tr(W^TS_bW)}{tr(W^TS_WW)}

同样需要求解广义特征值问题S_bW=\lambda S_WW ，若需要降到d 维，则需要求前面最大的d 个特征值

考虑S_W^{-1}S_b ，由于S_b=\sum_{i=1}^ rank(S_b)=rank\{\mu_1-\mu,...,\mu_N-\mu\},\sum_{i=1}^Nm_i(\mu_i-\mu)=0 ，所以rank(S_b)\le N-1 ，于是d=rank(W)\le\min(S_W,S_b)\le rank(S_b)\le N-1