PumpkinBook/docs/chapter10/chapter10.md

## 10.4 $$\sum^m{i=1}dist^2{ij}=tr(\boldsymbol B)+mb{jj}$$ [推导]： $$\begin{aligned} \sum^m{i=1}dist^2{ij}&= \sum^m{i=1}b{ii}+\sum^m{i=1}b{jj}-2\sum^m{i=1}b{ij}\ &=tr(B)+mb{jj} \end{aligned}​$$

10.10

$$b{ij}=-\frac{1}{2}(dist^2{ij}-dist^2{i\cdot}-dist^2{\cdot j}+dist^2{\cdot\cdot})$$ [推导]：由公式（10.3）可得， $$b{ij}=-\frac{1}{2}(dist^2{ij}-b{ii}-b{jj})$$ 由公式（10.6）和（10.9）可得， $$\begin{aligned} tr(\boldsymbol B)&=\frac{1}{2m}\sum^m{i=1}\sum^m{j=1}dist^2{ij}\ &=\frac{m}{2}dist^2{\cdot\cdot} \end{aligned}$$ 由公式（10.4）和（10.8）可得， $$\begin{aligned} b{jj}&=\frac{1}{m}\sum^m{i=1}dist^2{ij}-\frac{1}{m}tr(\boldsymbol B)\ &=dist^2{\cdot j}-\frac{1}{2}dist^2{\cdot\cdot} \end{aligned}$$ 由公式（10.5）和（10.7）可得， $$\begin{aligned} b{ii}&=\frac{1}{m}\sum^m{j=1}dist^2{ij}-\frac{1}{m}tr(\boldsymbol B)\ &=dist^2{i\cdot}-\frac{1}{2}dist^2{\cdot\cdot} \end{aligned}$$ 综合可得， $$\begin{aligned} b{ij}&=-\frac{1}{2}(dist^2{ij}-b{ii}-b{jj})\ &=-\frac{1}{2}(dist^2{ij}-dist^2{i\cdot}+\frac{1}{2}dist^2{\cdot\cdot}-dist^2{\cdot j}+\frac{1}{2}dist^2{\cdot\cdot})\ &=-\frac{1}{2}(dist^2{ij}-dist^2{i\cdot}-dist^2{\cdot j}+dist^2{\cdot\cdot}) \end{aligned}$$

10.14

$$\begin{aligned} \sum^m{i=1}| \sum^{d'}{j=1}z_{ij}\boldsymbol w_j-\boldsymbol x_i |^22&=\sum^m{i=1}\boldsymbol z^T_i\boldsymbol zi-2\sum^m{i=1}\boldsymbol z^T_i\boldsymbol W^T\boldsymbol xi + const\ &\propto -tr(\boldsymbol W^T(\sum^m{i=1}\boldsymbol x_i\boldsymbol x^T_i)\boldsymbol W) \end{aligned}$$ [推导]：已知$\boldsymbol W^T \boldsymbol W=\boldsymbol I$和$\boldsymbol z_i=\boldsymbol W^T \boldsymbol xi$， $$\begin{aligned} \sum^m{i=1}| \sum^{d'}{j=1}z{ij}\boldsymbol w_j-\boldsymbol x_i |^22&=\sum^m{i=1}| \boldsymbol W\boldsymbol z_i-\boldsymbol x_i |^22\ &=\sum^m{i=1}(\boldsymbol W\boldsymbol z_i)^T(\boldsymbol W\boldsymbol zi)-2\sum^m{i=1}(\boldsymbol W\boldsymbol z_i)^T\boldsymbol xi+\sum^m{i=1}\boldsymbol x^T_i\boldsymbol xi\ &=\sum^m{i=1}\boldsymbol z_i^T\boldsymbol zi-2\sum^m{i=1}\boldsymbol z_i^T\boldsymbol W^T\boldsymbol xi+\sum^m{i=1}\boldsymbol x^T_i\boldsymbol xi\ &=\sum^m{i=1}\boldsymbol z_i^T\boldsymbol zi-2\sum^m{i=1}\boldsymbol z_i^T\boldsymbol zi+\sum^m{i=1}\boldsymbol x^T_i\boldsymbol xi\ &=-\sum^m{i=1}\boldsymbol z_i^T\boldsymbol zi+\sum^m{i=1}\boldsymbol x^T_i\boldsymbol xi\ &=-tr(\boldsymbol W^T(\sum^m{i=1}\boldsymbol x_i\boldsymbol x^Ti)\boldsymbol W)+\sum^m{i=1}\boldsymbol x^T_i\boldsymbol xi\ &\propto -tr(\boldsymbol W^T(\sum^m{i=1}\boldsymbol x_i\boldsymbol x^Ti)\boldsymbol W) \end{aligned}$$ 其中，$\sum^m{i=1}\boldsymbol x^T_i\boldsymbol x_i$是常数。

10.17

$$ \boldsymbol X\boldsymbol X^T\boldsymbol w_i=\lambda _i\boldsymbol wi $$ [推导]：已知 $$\begin{aligned} &\min\limits{\boldsymbol W}-tr(\boldsymbol W^T\boldsymbol X\boldsymbol X^T\boldsymbol W)\ &s.t. \boldsymbol W^T\boldsymbol W=\boldsymbol I. \end{aligned}$$ 运用拉格朗日乘子法可得， $$\begin{aligned} J(\boldsymbol W)&=-tr(\boldsymbol W^T\boldsymbol X\boldsymbol X^T\boldsymbol W+\boldsymbol\lambda'(\boldsymbol W^T\boldsymbol W-\boldsymbol I))\ \cfrac{\partial J(\boldsymbol W)}{\partial \boldsymbol W} &=-(2\boldsymbol X\boldsymbol X^T\boldsymbol W+2\boldsymbol\lambda'\boldsymbol W) \end{aligned}$$ 令$\cfrac{\partial J(\boldsymbol W)}{\partial \boldsymbol W}=\boldsymbol 0$，故 $$\begin{aligned} \boldsymbol X\boldsymbol X^T\boldsymbol W&=-\boldsymbol\lambda'\boldsymbol W\ \boldsymbol X\boldsymbol X^T\boldsymbol W&=\boldsymbol\lambda\boldsymbol W\ \end{aligned}$$ 其中，$\boldsymbol W={\boldsymbol w_1,\boldsymbol w_2,\cdot\cdot\cdot,\boldsymbol w_d}$和$\boldsymbol \lambda=\boldsymbol{diag}(\lambda_1,\lambda_2,\cdot\cdot\cdot,\lambda_d)$。

10.28

$$w{ij}=\cfrac{\sum\limits{k\in Qi}C{jk}^{-1}}{\sum\limits_{l,s\in Qi}C{ls}^{-1}}$$ [推导]：已知 $$\begin{aligned} \min\limits{\boldsymbol W}&\sum^m{i=1}| \boldsymbol xi-\sum{j \in Qi}w{ij}\boldsymbol x_j |^22\ s.t.&\sum{j \in Qi}w{ij}=1 \end{aligned}$$ 转换为 $$\begin{aligned} \sum^m_{i=1}| \boldsymbol xi-\sum{j \in Qi}w{ij}\boldsymbol x_j |^22 &=\sum^m{i=1}| \sum_{j \in Qi}w{ij}\boldsymbol xi- \sum{j \in Qi}w{ij}\boldsymbol x_j |^22 \ &=\sum^m{i=1}| \sum_{j \in Qi}w{ij}(\boldsymbol x_i- \boldsymbol x_j) |^22\ &=\sum^m{i=1}\boldsymbol W^T_i(\boldsymbol x_i-\boldsymbol x_j)(\boldsymbol x_i-\boldsymbol x_j)^T\boldsymbol Wi\ &=\sum^m{i=1}\boldsymbol W^T_i\boldsymbol C_i\boldsymbol W_i \end{aligned}$$ 其中，$\boldsymbol Wi=(w{i1},w{i2},\cdot\cdot\cdot,w{ik})^T$，$k$是$Q_i$集合的长度，$\boldsymbol C_i=(\boldsymbol x_i-\boldsymbol x_j)(\boldsymbol x_i-\boldsymbol x_j)^T$，$j \in Qi$。 $$ \sum{j\in Qi}w{ij}=\boldsymbol W_i^T\boldsymbol 1_k=1 $$ 其中，$\boldsymbol 1k$为k维全1向量。 运用拉格朗日乘子法可得， $$ J(\boldsymbol W)==\sum^m{i=1}\boldsymbol W^T_i\boldsymbol C_i\boldsymbol W_i+\lambda(\boldsymbol W_i^T\boldsymbol 1_k-1) $$ $$\begin{aligned} \cfrac{\partial J(\boldsymbol W)}{\partial \boldsymbol W_i} &=2\boldsymbol C_i\boldsymbol W_i+\lambda'\boldsymbol 1_k \end{aligned}$$ 令$\cfrac{\partial J(\boldsymbol W)}{\partial \boldsymbol W_i}=0$，故 $$\begin{aligned} \boldsymbol W_i&=-\cfrac{1}{2}\lambda\boldsymbol C_i^{-1}\boldsymbol 1_k\ \boldsymbol W_i&=\lambda\boldsymbol C_i^{-1}\boldsymbol 1_k\ \end{aligned}$$ 其中，$\lambda$为一个常数。利用$\boldsymbol W^T_i\boldsymbol 1_k=1$，对$\boldsymbol W_i$归一化，可得 $$ \boldsymbol W_i=\cfrac{\boldsymbol C^{-1}_i\boldsymbol 1_k}{\boldsymbol 1_k\boldsymbol C^{-1}_i\boldsymbol 1_k} $$

10.31

$$\begin{aligned} &\min\limits{\boldsymbol Z}tr(\boldsymbol Z \boldsymbol M \boldsymbol Z^T)\ &s.t. \boldsymbol Z^T\boldsymbol Z=\boldsymbol I. \end{aligned}$$ [推导]： $$\begin{aligned} \min\limits{\boldsymbol Z}\sum^m_{i=1}| \boldsymbol zi-\sum{j \in Qi}w{ij}\boldsymbol z_j |^22&=\sum^m{i=1}|\boldsymbol Z\boldsymbol I_i-\boldsymbol Z\boldsymbol W_i|^22\ &=\sum^m{i=1}|\boldsymbol Z(\boldsymbol I_i-\boldsymbol W_i)|^22\ &=\sum^m{i=1}(\boldsymbol Z(\boldsymbol I_i-\boldsymbol W_i))^T\boldsymbol Z(\boldsymbol I_i-\boldsymbol Wi)\ &=\sum^m{i=1}(\boldsymbol I_i-\boldsymbol W_i)^T\boldsymbol Z^T\boldsymbol Z(\boldsymbol I_i-\boldsymbol W_i)\ &=tr((\boldsymbol I-\boldsymbol W)^T\boldsymbol Z^T\boldsymbol Z(\boldsymbol I-\boldsymbol W))\ &=tr(\boldsymbol Z(\boldsymbol I-\boldsymbol W)(\boldsymbol I-\boldsymbol W)^T\boldsymbol Z^T)\ &=tr(\boldsymbol Z\boldsymbol M\boldsymbol Z^T) \end{aligned}$$ 其中，$\boldsymbol M=(\boldsymbol I-\boldsymbol W)(\boldsymbol I-\boldsymbol W)^T$。 [解析]：约束条件$\boldsymbol Z^T\boldsymbol Z=\boldsymbol I$是为了得到标准化（标准正交空间）的低维数据。