图解机器学习/第十七章 监督降维

监督降维算法的目的，是通过将输入$x$变换为低维的$z$，使输出$y$的预测更加容易。假设输入样本$x$的维度为$d$，低纬度下的$z$的维度为$m$，$d\times m$阶矩阵为$T$

$$z = Tx$$

并预先对训练样本$\lbrace (x_i) \rbrace_{i=1}^n$进行中心化处理

$$x_i \leftarrow x_i-\frac{1}{n}\sum_{i'=1}^n x_{i'}$$

与分类问题相对应的判别分析

Fisher判别分析

Fisher判别分析，是寻找能够使相同类别的样本尽量靠近，不同类别的样本尽量远离的矩阵$T$的方法。

定义组内分散矩阵$S^{(w)}$和组间分散矩阵$S^{(b)}$

$$S^{(w)} = \sum_{y=1}^c \sum_{i:y_i = y}(x_i-\mu_y)(x_i-\mu_y)^{\intercal} \in \mathbb{R}^{(d \times d)}\\ S^{(b)}=\sum_{y=1}^n n_y \mu_y \mu_y^{\intercal} \in \mathbb{R}^{d \times d}$$

“w”和“b”分别是“within-class”和“between-class”的首字母。$\sum_{i:y_i = y}$是所有满足$y_i = y$的$y$的和，$\mu_y$是所有属于类别$y$的输入样本的平均值

$$\mu_y = \frac{1}{n_y}\sum_{i:y_i = y}x_i$$

$n_y$是属于类别$y$的训练样本总数。使用这样的分散矩阵，Fisher判别分析的投影矩阵可由下式定义

$$\mathop{max}_{T\in \mathbb{R}^{m \times d}} tr((TS^{(w)}T^{\intercal})^{-1}TS^{(b)}T^{\intercal})$$

---

Fisher判别分析，是通过使投影后的组间分散矩阵$TS^{(b)}T$变大，组内分散矩阵$TS^{(w)}T$变小，来决定矩阵$T$的*。

考虑对与矩阵对$(S^{(b)},S^{(w)})$相关的一般化特征值问题

$$S^{(b)}\xi = \lambda S^{(W)} \xi$$

与一般化特征值对应的一般化特征向量分别用$\lambda_1 \ge,\dots,\ge \lambda_d \ge 0$和$\xi_1,\dots,\xi_d$来表示。这样，Fisher判别分析即可进行解析求解。

$$\hat{T} = (\xi_1,\dots,\xi_m)^{\intercal}$$

即Fisher判别分析的投影矩阵，是依据与矩阵对$(S^{(b)},S^{(w)})$的较大的$m$个一般化特征值相对应的一般化特征向量来确定的。

局部Fisher判别分析

当某些类别的输入样本具有多峰值特性的时候，往往不能得到理想的结果。Fisher判别分析也会无视簇构造，强行把它们撮合为相同的类别，这样有时就不能得到理想的降维效果。

为了解决上述问题，局部Fisher判别分析使用如下的局部组内分散矩阵$S^{(lw)}$和局部组间分散矩阵$S^{(lb)}$

$$S^{(lw)}=\frac{1}{2}\sum_{i:i'=1}^n Q_{i:i'}^{(lw)}(x_i-x_{i'})(x_i-x_{i'})^{\intercal}$$ $$S^{(lb)}=\frac{1}{2}\sum_{i:i'=1}^n Q_{i:i'}^{(lb)}(x_i-x_{i'})(x_i-x_{i'})^{\intercal}$$

其中，$Q_{i:i’}^{(lw)}$和$Q_{i:i’}^{(lb)}$由下式定义

$$Q_{i:i'}^{(lw)}= \begin{cases} W_{i,i'}/n_y &\text{$(y_i=y_{i'}=y)$} \\ 0 &\text{$(y_i \not= y_{i'})$}\end{cases}$$ $$Q_{i:i'}^{(lb)}= \begin{cases} W_{i,i'}(1/n-1/n_y) &\text{$(y_i=y_{i'}=y)$} \\ 1/n &\text{$(y_i \not= y_{i'})$}\end{cases}$$

其中$0 \le W_{i,i’} \le 1$为训练样本$x_i$和$x_{i’}$的相似度。通过这样的方法，对于属于相同类别但不相似的样本，强行把他们撮合为相同类别的能力就会变弱，簇构造就可以得到保护。

局部Fisher判别分析的投影矩阵可由下式进行定义

$$\mathop{max}_{T\in \mathbb{R}^{m \times d}} tr((TS^{(lw)}T^{\intercal})^{-1}TS^{(lb)}T^{\intercal})$$

上式与原始Fisher判别分析形式完全一致，故对局部Fisher判别分析求解

$$\hat{T} = (\xi_1,\dots,\xi_m)^{\intercal}$$

半监督局部Fisher判别分析

半监督局部Fisher判别分析，是把无监督的降维方法中的主成分分析法和局部Fisher判别分析法组合起来进行学习的一种方法。主成分分析的解，对应的是分散矩阵

$$S^{(t)} = \sum_{i=1}^{n+n'} (x_i-\mu^{(t)})(x_i-\mu^{(t)})^{\intercal},\mu^{(t)}=\frac{1}{n+n'}\sum_{i=1}^{n+n'}x_i$$

的较大的特征值所对应的特征向量。其中$\mu^{(t)}$表示的是全部输入样本$\lbrace x_i \rbrace_{i=n+1}^{n+n’}$的平均值。

半监督局部Fisher判别分析将对特征值问题加以组合，具体而言就是采用半监督分散矩阵

$$S^{(slw)}=(1-\beta)S^{(lw)}+\beta S^{(t)},S^{(slb)}=(1-\beta)S^{(lb)}+\beta I$$

半监督局部Fisher判别分析的解$\hat{T}$，可以使用与一般化特征值问题

$$S^{(slb)}\xi = \lambda S^{(slw)} \xi$$

的一般化特征值$\lambda_1 \ge,\dots,\ge \lambda_d \ge 0$和对应的一般化特征向量$\xi_1,\dots,\xi_d$进行解析求解

$$\hat{T} = (\xi_1,\dots,\xi_m)^{\intercal}$$

这个解在$\beta =0$的时候与局部Fisher判别分析的解一致，在$\beta = 1$的时候与主成分分析的解一致。

充分降维

充分降维是一种适用于回归问题的监督降维算法，主要着眼于输入和输出的依赖关系。就是在给定投影后的数据$z=Tx$的时候，使原始的输入$x$和输出$y$条件独立，以此来确定投影矩阵$T$

$$p(x,y|z)=p(x|z)p(y|z)$$

在给定$z$之后，$x$和$y$在统计上是相互独立的，$y$中包含的所有信息在$z$中均可以找到。这种条件独立性，是通过确定$z=Tx$和$y$最相互依存时对应的矩阵$T$来实现的。通过引入平方损失互信息，来确定下式为最大值时所对应的$T$，这时候$z$和$y$的从属关系也将达到最大

$$\frac{1}{2} \iint p(z)p(y)(\frac{p(z,y)}{p(z)p(y)}-1)^2dzdy$$

利用最小二乘互信息估计法来计算平方损失互信息，可以得到

$$J(T)=\frac{1}{2}\hat{h}^{\intercal}(\hat{G}+ \lambda I)^{-1}\hat{h}-\frac{1}{2}$$

上式中，

$$\hat{G}=\frac{1}{n^2}\sum_{i:i'=1}^n \psi(z_i,y_{i'})\psi(z_i,y_{i'})^{\intercal},\hat{h}=\frac{1}{n}\sum_{i=1}^n \psi(z_i,y_i)$$

$\psi(z,y)\in \mathbb{R}^b$表示的是基函数

与上式的规则$J$中的$T$中编号为$(j,j’)$的元素$T_{j,j’}$相关的微分为

$$\hat{h}^{\intercal}(\hat{G}+\lambda I)^{-1} \frac{\part \hat{h}}{\part T_{j.j'}}-\frac{1}{2}\hat{h}^{\intercal}(\hat{G}+\lambda I)^{-1}\frac{\part \hat{G}}{\part T_{j,j'}}(\hat{G}+\lambda I)^{-1} \hat{h}$$

使用这样的表示方式，通过梯度法就可以求得$J$的局部最优解。