机器学习 [白板推导]（N）[谱聚类、前馈神经网络]

​

21. 谱聚类（Spectral Clustering）

21.1. 背景

​  在高斯混合模型中，假设样本有多个类别，每个类内数据遵从不同的高斯分布。但在某些数据中（如下图），其并不具有类似高斯分布的特性，则GMM或其他基于空间距离的聚类方法（例如k-means）易于失效。

​  为了应对上述问题，一种方法是使用合适的kernel函数，将难以处理的分布转换成高斯分布（或其他空间上易于分离的分布）。但实际应用中这样的kernel函数搜索困难。因此需要另一种基于连通性（Connectivity）的方法，从图的角度理解数据分布，即为谱聚类方法（对应的GMM、K-means一类方法为基于Compactness的方法）。

21.2. 模型介绍

21.2.1. 数学建模

  将数据集 $Data:X_{N\times p}=({\vec{x}}_1,\cdots ,{\vec{x}}_N{)}^T$ 视作一个图：
G = { V , E } , V = { v ⃗ i } , 其中 v ⃗ i ↔ x ⃗ i , E : W = { w i j } , 1 ⩽ i , j ⩽ N , (21.1) \begin{aligned}G&=\{V, E\}, &\\ V&=\{\vec{v}_i\}, &其中 \vec{v}_i\leftrightarrow \vec{x}_i, \\ E&: W=\{w_{ij}\}, &1\leqslant i, j \leqslant N,\end{aligned}\tag{21.1} GVE​={V,E},={v i​},:W={wij​},​其中v i​↔x i​,1⩽i,j⩽N,​(21.1)

其中 $V$ 为节点集合，其中每个节点 ${\vec{v}}_i$ 表示对应样本 ${\vec{x}}_i$ 的特征表示；$E$ 为边集合，可以用权重矩阵（邻接矩阵，affinity matrix）$W$ 表示，其中每个元素 $w_{ij}$ 表示节点 ${\vec{v}}_i$ 和 ${\vec{v}}_j$ 的相似度。相似度可以使用多种方法计算，以高斯核函数为例：
w i j = { K ( v ⃗ i , v ⃗ j ) = exp ⁡ { − ∥ v ⃗ i − v ⃗ j ∥ 2 σ 2 } , ( i , j ) ∈ E 0 , ( i , j ) ∉ E (21.2) w_{ij}=\left\{\begin{matrix}\mathcal{K}(\vec{v}_i, \vec{v}_j)=\exp\{-\frac{\|\vec{v}_i-\vec{v}_j\|}{2\sigma^2}\},&(i, j)\in E\\0,&(i, j)\notin E\end{matrix}\right.\tag{21.2} wij​={K(v i​,v j​)=exp{−2σ2∥v i​−v j​∥​},0,​(i,j)∈E(i,j)∈/E​(21.2)

  定义相似度损失：存在节点集合 $A\subseteq V$ 和 $B\subseteq V$，则二者的相似度损失为：
$$\mathcal{W}(A,B)=\sum _{{\vec{v}}_i\in A}\sum _{{\vec{v}}_j\in B}{w}_{ij},\text{\hspace{1em}(21.3)}$$

则可以计算总聚类损失：假设一共聚为 $K$ 个类别： { A 1 , ⋯   , A K } \{A_1,\cdots,A_K\} {A1​,⋯,AK​}，定义 A ˉ i = { A j } i ≠ j , 1 ⩽ j ⩽ K \bar{A}_i=\{A_j\}_{i\neq j,1\leqslant j\leqslant K} Aˉi​={Aj​}i=j,1⩽j⩽K​，则总聚类损失计算为：
$$\begin{array}{rl}\mathcal{L}(A_1,\cdots ,A_K)& =\text{Cut}(A_1,\cdots ,A_K)\\ & =\sum _{k=1}^K\mathcal{W}(A_k,{\bar{A}}_k)\\ & =\sum _{k=1}^K\sum _{{\vec{v}}_i\in A_k}\sum _{{\vec{v}}_j\notin A_k}{w}_{ij},\end{array}\text{\hspace{1em}(21.4)}$$

则整个聚类问题可以建模为最小化总聚类损失的优化问题： min ⁡ { A k } k = 1 K L \underset{\{A_k\}_{k=1}^K}{\min}\mathcal{L} {Ak​}k=1K​min​L，但这个优化目标可能因为数据分布不均衡而导致优化过程产生偏差，因此需要对目标函数进行归一化以排除偏差：
$${\mathcal{L}}_{\text{N}}(A_1,\cdots ,A_K)=\sum _{k=1}^K\frac{\mathcal{W}(A_k,{\bar{A}}_k)}{{\Delta }_k},\text{\hspace{1em}(21.5)}$$

其中一种计算归一化因子 ${\Delta }_k$ 的方法是使用样本数，即 ${\Delta }_k=|A_k|$，但仅仅考虑样本数不足以消除偏差，因为各个节点在图中的关联度差异很大，因此可以使用基于类内总关联度的归一化因子，计算如下：
$$\begin{array}{rl}{\Delta }_k& =\text{degree}(A_k)\\ & =\sum _{{\vec{v}}_i\in A_k}\text{degree}({\vec{v}}_i)\\ & =\sum _{{\vec{v}}_i\in A_k}\sum _{j=1}^N{w}_{ij}.\end{array}\text{\hspace{1em}(21.6)}$$

21.2.2. 模型求解

  指示向量（Indicator Vector）：为了更优雅地表示优化变量，可以采用指示向量 ${\vec{y}}_i=[y_{i1},\cdots ,y_{iK}]$ 表示每个节点 ${\vec{v}}_i$ （或样本 ${\vec{x}}_i$）的类别，即 $y_{ik}=1$ 表示该节点属于类别 $A_k$，同时 ${\sum }_{k=1}^K{y}_{ik}=1,\forall i$. 因此总体优化问题可以定义为：
$$\begin{array}{rl}\text{Objective}:& \underset{Y={\left[{\vec{y}}_1,\cdots ,{\vec{y}}_N\right]}^T}{\min }{\mathcal{L}}_{\text{N}}(Y)\\ \text{s.t.}& \sum _{k=1}^K{y}_{ik}=1,\forall i\end{array}\text{\hspace{1em}(21.7)}$$

则该问题求解可以表示为：$\hat{Y}=\underset{Y}{\mathrm{argmin}}{\mathcal{L}}_{\text{N}}(Y)$.

  要求解模型，需要将其表示为矩阵形式，首先拆解聚类损失函数：
$$\begin{array}{rl}{\mathcal{L}}_{\text{N}}(Y)& =\sum _{k=1}^K\frac{\mathcal{W}(A_k,{\bar{A}}_k)}{{\sum }_{{\vec{v}}_i\in A_k}{d}_i}\\ & =\text{tr}\left[\left(\begin{array}{cccc}\frac{\mathcal{W}(A_1,{\bar{A}}_1)}{{\sum }_{{\vec{v}}_i\in A_1}{d}_i}& & & \\ & \frac{\mathcal{W}(A_2,{\bar{A}}_2)}{{\sum }_{{\vec{v}}_i\in A_2}{d}_i}& & \\ & & \ddots & \\ & & & \frac{\mathcal{W}(A_K,{\bar{A}}_K)}{{\sum }_{{\vec{v}}_i\in A_K}{d}_i}\end{array}\right)\right]\\ & =\text{tr}[\left(\begin{array}{cccc}\mathcal{W}(A_1,{\bar{A}}_1)& & & \\ & \mathcal{W}(A_2,{\bar{A}}_2)& & \\ & & \ddots & \\ & & & \mathcal{W}(A_K,{\bar{A}}_K)\end{array}\right)\cdot \\ & {\left(\begin{array}{cccc}{\sum }_{{\vec{v}}_i\in A_1}{d}_i& & & \\ & {\sum }_{{\vec{v}}_i\in A_2}{d}_i& & \\ & & \ddots & \\ & & & {\sum }_{{\vec{v}}_i\in A_K}{d}_i\end{array}\right)}^{-1}],\end{array}\text{\hspace{1em}(21.8)}$$

其中 $d_i=\text{degree}({\vec{v}}_i)={\sum }_{j=1}^N{w}_{ij}$，令式（21.8）左右两个矩阵分别为 $P$ 和 $Q^{-1}$，则 ${\mathcal{L}}_{\text{N}}=\text{tr}(P\cdot Q^{-1})$. 此时需要使用 $W$ 和 $Y$ 表示 $P$ 和 $Q$ 即可推导出模型的矩阵表示。

  根据指示矩阵 $Y$ 进行推导：
$$\begin{array}{rl}{Y}^{T}Y& =\left[{\vec{y}}_1,\cdots ,{\vec{y}}_N\right]\cdot \left[\begin{array}{c}{\vec{y}}_1\\ ⋮\\ {\vec{y}}_N\end{array}\right]=\sum _{i=1}^N{\vec{y}}_i{\vec{y}}_i^T,\end{array}\text{\hspace{1em}(21.9)}$$

其中指示向量具有一个特性：当 ${\vec{v}}_i\in A_k$ 时，
y ⃗ i y ⃗ i T = { a p q } K × K , a p q = { 1 , p = q = k 0 , otherwise , (21.10) \vec{y}_i\vec{y}_i^T=\{a_{pq}\}_{K\times K}, a_{pq}=\left\{\begin{matrix}1, p=q=k\\0, \text{otherwise}\end{matrix}\right.,\tag{21.10} y ​i​y ​iT​={apq​}K×K​,apq​={1,p=q=k0,otherwise​,(21.10)

因此联立式（21.9）和式（21.10）可得：
$$\begin{array}{rl}{Y}^{T}Y& =\sum _{i=1}^N{\vec{y}}_i{\vec{y}}_i^T=\left(\begin{array}{cccc}{\sum }_{{\vec{v}}_i\in A_1}1& & & \\ & {\sum }_{{\vec{v}}_i\in A_2}1& & \\ & & \ddots & \\ & & & {\sum }_{{\vec{v}}_i\in A_K}1\end{array}\right),\end{array}\text{\hspace{1em}(21.11)}$$

因此设关联度对角矩阵 $D=\left(\begin{array}{ccc}{d}_1& & \\ & \ddots & \\ & & d_N\end{array}\right)=\text{diag}(W\cdot {\vec{1}}_N)$，则有：
$$\begin{array}{rl}{Y}^{T}DY& =\sum _{i=1}^N{d}_i\cdot {\vec{y}}_i{\vec{y}}_i^T\\ & =\left(\begin{array}{cccc}{\sum }_{{\vec{v}}_i\in A_1}{d}_1& & & \\ & {\sum }_{{\vec{v}}_i\in A_2}{d}_2& & \\ & & \ddots & \\ & & & {\sum }_{{\vec{v}}_i\in A_K}{d}_K\end{array}\right)\\ & =Q.\end{array}\text{\hspace{1em}(21.12)}$$

  另外，相似度损失可以有如下关系：
$$\begin{array}{rl}\mathcal{W}(A_k,{\bar{A}}_k)& =\sum _{{\vec{v}}_i\in A_k}\sum _{{\vec{v}}_j\notin A_k}{w}_{ij}\\ & =\sum _{{\vec{v}}_i\in A_k}\left(\sum _{{\vec{v}}_j\in V}{w}_{ij}-\sum _{{\vec{v}}_j\in A_k}{w}_{ij}\right)\\ & =\sum _{{\vec{v}}_i\in A_k}{d}_i-\mathcal{W}(A_k,A_k),\end{array}\text{\hspace{1em}(21.13)}$$

因此将式（21.13）带入矩阵 $P$ 可得：
$$\begin{array}{rl}P& =\left(\begin{array}{cccc}\mathcal{W}(A_1,{\bar{A}}_1)& & & \\ & \mathcal{W}(A_2,{\bar{A}}_2)& & \\ & & \ddots & \\ & & & \mathcal{W}(A_K,{\bar{A}}_K)\end{array}\right)\\ & =Q-\left(\begin{array}{cccc}\mathcal{W}(A_1,A_1)& & & \\ & \mathcal{W}(A_2,A_2)& & \\ & & \ddots & \\ & & & \mathcal{W}(A_K,A_K)\end{array}\right),\end{array}\text{\hspace{1em}(21.14)}$$

  为进一步推导，先计算
$$\begin{array}{rl}{Y}^{T}WY& =\left(\begin{array}{ccc}{\vec{y}}_1& \cdots & {\vec{y}}_N\end{array}\right)\cdot \left(\begin{array}{ccc}{w}_{11}& \cdots & w_{1N}\\ ⋮& \ddots & ⋮\\ w_{N1}& \cdots & w_{NN}\end{array}\right)\cdot \left(\begin{array}{c}{\vec{y}}_1^T\\ ⋮\\ {\vec{y}}_N^T\end{array}\right)\\ & =\sum _{i=1}^N\sum _{j=1}^N{w}_{ij}\cdot {\vec{y}}_i{\vec{y}}_j^T\\ & =\left(\begin{array}{ccc}{\sum }_{{\vec{v}}_i\in A_1}{\sum }_{{\vec{v}}_j\in A_1}{w}_{ij}& \cdots & {\sum }_{{\vec{v}}_i\in A_1}{\sum }_{{\vec{v}}_j\in A_K}{w}_{ij}\\ ⋮& \ddots & ⋮\\ {\sum }_{{\vec{v}}_i\in A_K}{\sum }_{{\vec{v}}_j\in A_1}{w}_{ij}& \cdots & {\sum }_{{\vec{v}}_i\in A_K}{\sum }_{{\vec{v}}_j\in A_K}{w}_{ij}\end{array}\right),\end{array}\text{\hspace{1em}(21.15)}$$
尽管该矩阵与式（21.14）中减号后的矩阵不同，但因为最终的损失函数计算要取 $\text{tr}(\cdot )$，所以非对角线元素不影响计算结果，因此可以将损失函数表示为：
$$\begin{array}{rl}{\mathcal{L}}_{\text{N}}(Y)& =\text{tr}(P\cdot Q^{-1})\\ & =\text{tr}\left[(Y^{T}DY-Y^{T}WY)\cdot (Y^{T}DY{)}^{-1}\right]\\ & =\text{tr}\left[Y^T(D-W)Y\cdot (Y^{T}DY{)}^{-1}\right],\end{array}\text{\hspace{1em}(21.16)}$$

其中 $D-W$ 为拉普拉斯矩阵。至此便完成了矩阵表示，可以对其求导得到解析解或梯度下降逼近解，过程略。

22. 前馈神经网络

22.1. 从机器学习到深度学习

  机器学习分为频率派和贝叶斯派，分别从不同的角度深入研究得到了不同的模型，也以不同的范式进入了深度学习时代。具体来说：

• 频率派 → 统计学习
  • 正则化
  • 核化（Kernel SVM）
  • 集成化（Adaboost，Random Forest）
  • 层次化（Neural Network —— 狭义的深度学习）
    • MLP
    • AutoEncoder
    • CNN
    • RNN
• 贝叶斯派 → 概率图模型
  • 有向图：Bayesian Network → Deep Directed Network
    • Sigmoid Belief Network
    • VAE
    • GAN
  • 无向图：Markov Network → Deep Bottzmam Machine
  • 有向+无向：Mixed Network → Deep Belief Network

   贝叶斯派的深度学习范式被称为 Deep Generative Model，也属于现代深度学习的分支，但因为概率图模型本身在增加深度后学习和推理难度显著增加，因此深度学习很多时候在狭义上指 Deep Neural Network 为基础的频率派深度学习方法。