机器学习 [白板推导](N)[谱聚类、前馈神经网络]
21. 谱聚类(Spectral Clustering)
21.1. 背景
在高斯混合模型中,假设样本有多个类别,每个类内数据遵从不同的高斯分布。但在某些数据中(如下图),其并不具有类似高斯分布的特性,则GMM或其他基于空间距离的聚类方法(例如k-means)易于失效。
为了应对上述问题,一种方法是使用合适的kernel函数,将难以处理的分布转换成高斯分布(或其他空间上易于分离的分布)。但实际应用中这样的kernel函数搜索困难。因此需要另一种基于连通性(Connectivity)的方法,从图的角度理解数据分布,即为谱聚类方法(对应的GMM、K-means一类方法为基于Compactness的方法)。
21.2. 模型介绍
21.2.1. 数学建模
将数据集
D
a
t
a
:
X
N
×
p
=
(
x
⃗
1
,
⋯
,
x
⃗
N
)
T
Data: X_{N\times p}=(\vec{x}_1, \cdots, \vec{x}_N)^T
Data:XN×p=(x1,⋯,xN)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},={vi},:W={wij},其中vi↔xi,1⩽i,j⩽N,(21.1)
其中
V
V
V 为节点集合,其中每个节点
v
⃗
i
\vec{v}_i
vi 表示对应样本
x
⃗
i
\vec{x}_i
xi 的特征表示;
E
E
E 为边集合,可以用权重矩阵(邻接矩阵,affinity matrix)
W
W
W 表示,其中每个元素
w
i
j
w_{ij}
wij 表示节点
v
⃗
i
\vec{v}_i
vi 和
v
⃗
j
\vec{v}_j
vj 的相似度。相似度可以使用多种方法计算,以高斯核函数为例:
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(vi,vj)=exp{−2σ2∥vi−vj∥},0,(i,j)∈E(i,j)∈/E(21.2)
定义相似度损失:存在节点集合
A
⊆
V
A\subseteq V
A⊆V 和
B
⊆
V
B\subseteq V
B⊆V,则二者的相似度损失为:
W
(
A
,
B
)
=
∑
v
⃗
i
∈
A
∑
v
⃗
j
∈
B
w
i
j
,
(21.3)
\mathcal{W}(A, B)=\sum_{\vec{v}_i \in A}\sum_{\vec{v}_j \in B}w_{ij},\tag{21.3}
W(A,B)=vi∈A∑vj∈B∑wij,(21.3)
则可以计算总聚类损失:假设一共聚为
K
K
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,则总聚类损失计算为:
L
(
A
1
,
⋯
,
A
K
)
=
Cut
(
A
1
,
⋯
,
A
K
)
=
∑
k
=
1
K
W
(
A
k
,
A
ˉ
k
)
=
∑
k
=
1
K
∑
v
⃗
i
∈
A
k
∑
v
⃗
j
∉
A
k
w
i
j
,
(21.4)
\begin{aligned}\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{aligned}\tag{21.4}
L(A1,⋯,AK)=Cut(A1,⋯,AK)=k=1∑KW(Ak,Aˉk)=k=1∑Kvi∈Ak∑vj∈/Ak∑wij,(21.4)
则整个聚类问题可以建模为最小化总聚类损失的优化问题:
min
{
A
k
}
k
=
1
K
L
\underset{\{A_k\}_{k=1}^K}{\min}\mathcal{L}
{Ak}k=1KminL,但这个优化目标可能因为数据分布不均衡而导致优化过程产生偏差,因此需要对目标函数进行归一化以排除偏差:
L
N
(
A
1
,
⋯
,
A
K
)
=
∑
k
=
1
K
W
(
A
k
,
A
ˉ
k
)
Δ
k
,
(21.5)
\mathcal{L}_{\text{N}}(A_1,\cdots,A_K)=\sum_{k=1}^K \frac{\mathcal{W}(A_k, \bar{A}_k)}{\Delta_k}, \tag{21.5}
LN(A1,⋯,AK)=k=1∑KΔkW(Ak,Aˉk),(21.5)
其中一种计算归一化因子
Δ
k
\Delta_k
Δk 的方法是使用样本数,即
Δ
k
=
∣
A
k
∣
\Delta_k=|A_k|
Δk=∣Ak∣,但仅仅考虑样本数不足以消除偏差,因为各个节点在图中的关联度差异很大,因此可以使用基于类内总关联度的归一化因子,计算如下:
Δ
k
=
degree
(
A
k
)
=
∑
v
⃗
i
∈
A
k
degree
(
v
⃗
i
)
=
∑
v
⃗
i
∈
A
k
∑
j
=
1
N
w
i
j
.
(21.6)
\begin{aligned}\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}^Nw_{ij}.\end{aligned}\tag{21.6}
Δk=degree(Ak)=vi∈Ak∑degree(vi)=vi∈Ak∑j=1∑Nwij.(21.6)
21.2.2. 模型求解
指示向量(Indicator Vector):为了更优雅地表示优化变量,可以采用指示向量
y
⃗
i
=
[
y
i
1
,
⋯
,
y
i
K
]
\vec{y}_i=[y_{i1}, \cdots, y_{iK}]
yi=[yi1,⋯,yiK] 表示每个节点
v
⃗
i
\vec{v}_i
vi (或样本
x
⃗
i
\vec{x}_i
xi)的类别,即
y
i
k
=
1
y_{ik}=1
yik=1 表示该节点属于类别
A
k
A_k
Ak,同时
∑
k
=
1
K
y
i
k
=
1
,
∀
i
\sum_{k=1}^Ky_{ik}=1, \forall i
∑k=1Kyik=1,∀i. 因此总体优化问题可以定义为:
Objective
:
min
Y
=
[
y
⃗
1
,
⋯
,
y
⃗
N
]
T
L
N
(
Y
)
s.t.
∑
k
=
1
K
y
i
k
=
1
,
∀
i
(21.7)
\begin{aligned}\text{Objective}:&\min_{Y=\left[\vec{y}_1, \cdots, \vec{y}_N\right]^T}\mathcal{L}_{\text{N}}(Y)\\ \text{s.t.}&\sum_{k=1}^Ky_{ik}=1, \forall i\end{aligned}\tag{21.7}
Objective:s.t.Y=[y1,⋯,yN]TminLN(Y)k=1∑Kyik=1,∀i(21.7)
则该问题求解可以表示为: Y ^ = arg min Y L N ( Y ) \hat{Y}=\underset{Y}{\argmin}\mathcal{L}_{\text{N}}(Y) Y^=YargminLN(Y).
要求解模型,需要将其表示为矩阵形式,首先拆解聚类损失函数:
L
N
(
Y
)
=
∑
k
=
1
K
W
(
A
k
,
A
ˉ
k
)
∑
v
⃗
i
∈
A
k
d
i
=
tr
[
(
W
(
A
1
,
A
ˉ
1
)
∑
v
⃗
i
∈
A
1
d
i
W
(
A
2
,
A
ˉ
2
)
∑
v
⃗
i
∈
A
2
d
i
⋱
W
(
A
K
,
A
ˉ
K
)
∑
v
⃗
i
∈
A
K
d
i
)
]
=
tr
[
(
W
(
A
1
,
A
ˉ
1
)
W
(
A
2
,
A
ˉ
2
)
⋱
W
(
A
K
,
A
ˉ
K
)
)
⋅
(
∑
v
⃗
i
∈
A
1
d
i
∑
v
⃗
i
∈
A
2
d
i
⋱
∑
v
⃗
i
∈
A
K
d
i
)
−
1
]
,
(21.8)
\begin{aligned} \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{matrix} \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{matrix}\right)\right]\\ &=\text{tr}\left[\left(\begin{matrix} \mathcal{W}(A_1,\bar{A}_1) & & & \\ & \mathcal{W}(A_2,\bar{A}_2) & & \\ & & \ddots & \\ & & & \mathcal{W}(A_K,\bar{A}_K) \end{matrix}\right)\cdot\right.\\ &\left. \left(\begin{matrix} {\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{matrix}\right)^{-1}\right], \end{aligned}\tag{21.8}
LN(Y)=k=1∑K∑vi∈AkdiW(Ak,Aˉk)=tr
∑vi∈A1diW(A1,Aˉ1)∑vi∈A2diW(A2,Aˉ2)⋱∑vi∈AKdiW(AK,AˉK)
=tr
W(A1,Aˉ1)W(A2,Aˉ2)⋱W(AK,AˉK)
⋅
∑vi∈A1di∑vi∈A2di⋱∑vi∈AKdi
−1
,(21.8)
其中 d i = degree ( v ⃗ i ) = ∑ j = 1 N w i j d_i=\text{degree}(\vec{v}_i)=\sum_{j=1}^Nw_{ij} di=degree(vi)=∑j=1Nwij,令式(21.8)左右两个矩阵分别为 P P P 和 Q − 1 Q^{-1} Q−1,则 L N = tr ( P ⋅ Q − 1 ) \mathcal{L}_{\text{N}}=\text{tr}(P\cdot Q^{-1}) LN=tr(P⋅Q−1). 此时需要使用 W W W 和 Y Y Y 表示 P P P 和 Q Q Q 即可推导出模型的矩阵表示。
根据指示矩阵
Y
Y
Y 进行推导:
Y
T
Y
=
[
y
⃗
1
,
⋯
,
y
⃗
N
]
⋅
[
y
⃗
1
⋮
y
⃗
N
]
=
∑
i
=
1
N
y
⃗
i
y
⃗
i
T
,
(21.9)
\begin{aligned} Y^TY&=\left[\vec{y}_1, \cdots, \vec{y}_N\right]\cdot\left[\begin{matrix}\vec{y}_1\\\vdots\\\vec{y}_N\end{matrix}\right]=\sum_{i=1}^N\vec{y}_i\vec{y}_i^T, \end{aligned}\tag{21.9}
YTY=[y1,⋯,yN]⋅
y1⋮yN
=i=1∑NyiyiT,(21.9)
其中指示向量具有一个特性:当
v
⃗
i
∈
A
k
\vec{v}_i\in A_k
vi∈Ak 时,
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}
yiyiT={apq}K×K,apq={1,p=q=k0,otherwise,(21.10)
因此联立式(21.9)和式(21.10)可得:
Y
T
Y
=
∑
i
=
1
N
y
⃗
i
y
⃗
i
T
=
(
∑
v
⃗
i
∈
A
1
1
∑
v
⃗
i
∈
A
2
1
⋱
∑
v
⃗
i
∈
A
K
1
)
,
(21.11)
\begin{aligned} Y^TY&=\sum_{i=1}^N\vec{y}_i\vec{y}_i^T=\left(\begin{matrix} \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{matrix}\right), \end{aligned}\tag{21.11}
YTY=i=1∑NyiyiT=
∑vi∈A11∑vi∈A21⋱∑vi∈AK1
,(21.11)
因此设关联度对角矩阵
D
=
(
d
1
⋱
d
N
)
=
diag
(
W
⋅
1
⃗
N
)
D=\left(\begin{matrix}d_1&&\\&\ddots&\\&&d_N\end{matrix}\right)=\text{diag}(W\cdot \vec{1}_N)
D=
d1⋱dN
=diag(W⋅1N),则有:
Y
T
D
Y
=
∑
i
=
1
N
d
i
⋅
y
⃗
i
y
⃗
i
T
=
(
∑
v
⃗
i
∈
A
1
d
1
∑
v
⃗
i
∈
A
2
d
2
⋱
∑
v
⃗
i
∈
A
K
d
K
)
=
Q
.
(21.12)
\begin{aligned} Y^TDY&=\sum_{i=1}^Nd_i\cdot\vec{y}_i\vec{y}_i^T\\&=\left(\begin{matrix} \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{matrix}\right)\\&=Q. \end{aligned}\tag{21.12}
YTDY=i=1∑Ndi⋅yiyiT=
∑vi∈A1d1∑vi∈A2d2⋱∑vi∈AKdK
=Q.(21.12)
另外,相似度损失可以有如下关系:
W
(
A
k
,
A
ˉ
k
)
=
∑
v
⃗
i
∈
A
k
∑
v
⃗
j
∉
A
k
w
i
j
=
∑
v
⃗
i
∈
A
k
(
∑
v
⃗
j
∈
V
w
i
j
−
∑
v
⃗
j
∈
A
k
w
i
j
)
=
∑
v
⃗
i
∈
A
k
d
i
−
W
(
A
k
,
A
k
)
,
(21.13)
\begin{aligned}\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{aligned}\tag{21.13}
W(Ak,Aˉk)=vi∈Ak∑vj∈/Ak∑wij=vi∈Ak∑
vj∈V∑wij−vj∈Ak∑wij
=vi∈Ak∑di−W(Ak,Ak),(21.13)
因此将式(21.13)带入矩阵
P
P
P 可得:
P
=
(
W
(
A
1
,
A
ˉ
1
)
W
(
A
2
,
A
ˉ
2
)
⋱
W
(
A
K
,
A
ˉ
K
)
)
=
Q
−
(
W
(
A
1
,
A
1
)
W
(
A
2
,
A
2
)
⋱
W
(
A
K
,
A
K
)
)
,
(21.14)
\begin{aligned} P&=\left(\begin{matrix} \mathcal{W}(A_1,\bar{A}_1) & & & \\ & \mathcal{W}(A_2,\bar{A}_2) & & \\ & & \ddots & \\ & & & \mathcal{W}(A_K,\bar{A}_K) \end{matrix}\right)\\ &=Q-\left(\begin{matrix} \mathcal{W}(A_1,A_1) & & & \\ & \mathcal{W}(A_2,A_2) & & \\ & & \ddots & \\ & & & \mathcal{W}(A_K,A_K) \end{matrix}\right) ,\end{aligned}\tag{21.14}
P=
W(A1,Aˉ1)W(A2,Aˉ2)⋱W(AK,AˉK)
=Q−
W(A1,A1)W(A2,A2)⋱W(AK,AK)
,(21.14)
为进一步推导,先计算
Y
T
W
Y
=
(
y
⃗
1
⋯
y
⃗
N
)
⋅
(
w
11
⋯
w
1
N
⋮
⋱
⋮
w
N
1
⋯
w
N
N
)
⋅
(
y
⃗
1
T
⋮
y
⃗
N
T
)
=
∑
i
=
1
N
∑
j
=
1
N
w
i
j
⋅
y
⃗
i
y
⃗
j
T
=
(
∑
v
⃗
i
∈
A
1
∑
v
⃗
j
∈
A
1
w
i
j
⋯
∑
v
⃗
i
∈
A
1
∑
v
⃗
j
∈
A
K
w
i
j
⋮
⋱
⋮
∑
v
⃗
i
∈
A
K
∑
v
⃗
j
∈
A
1
w
i
j
⋯
∑
v
⃗
i
∈
A
K
∑
v
⃗
j
∈
A
K
w
i
j
)
,
(21.15)
\begin{aligned} Y^TWY&=\left(\begin{matrix}\vec{y}_1&\cdots&\vec{y}_N\end{matrix}\right)\cdot \left(\begin{matrix}w_{11}&\cdots&w_{1N}\\\vdots&\ddots&\vdots\\w_{N1}&\cdots&w_{NN}\end{matrix}\right)\cdot \left(\begin{matrix}\vec{y}_1^T\\\vdots\\\vec{y}_N^T\end{matrix}\right)\\ &=\sum_{i=1}^N\sum_{j=1}^N w_{ij}\cdot \vec{y}_i\vec{y}_j^T\\ &=\left(\begin{matrix}\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}\\\vdots&\ddots&\vdots\\\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{matrix}\right), \end{aligned}\tag{21.15}
YTWY=(y1⋯yN)⋅
w11⋮wN1⋯⋱⋯w1N⋮wNN
⋅
y1T⋮yNT
=i=1∑Nj=1∑Nwij⋅yiyjT=
∑vi∈A1∑vj∈A1wij⋮∑vi∈AK∑vj∈A1wij⋯⋱⋯∑vi∈A1∑vj∈AKwij⋮∑vi∈AK∑vj∈AKwij
,(21.15)
尽管该矩阵与式(21.14)中减号后的矩阵不同,但因为最终的损失函数计算要取
tr
(
⋅
)
\text{tr}(\cdot)
tr(⋅),所以非对角线元素不影响计算结果,因此可以将损失函数表示为:
L
N
(
Y
)
=
tr
(
P
⋅
Q
−
1
)
=
tr
[
(
Y
T
D
Y
−
Y
T
W
Y
)
⋅
(
Y
T
D
Y
)
−
1
]
=
tr
[
Y
T
(
D
−
W
)
Y
⋅
(
Y
T
D
Y
)
−
1
]
,
(21.16)
\begin{aligned} \mathcal{L}_{\text{N}}(Y)&=\text{tr}(P\cdot Q^{-1})\\ &=\text{tr}\left[(Y^TDY-Y^TWY)\cdot(Y^TDY)^{-1}\right]\\ &=\text{tr}\left[Y^T(D-W)Y\cdot(Y^TDY)^{-1}\right], \end{aligned}\tag{21.16}
LN(Y)=tr(P⋅Q−1)=tr[(YTDY−YTWY)⋅(YTDY)−1]=tr[YT(D−W)Y⋅(YTDY)−1],(21.16)
其中 D − W D-W 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
- 有向图:Bayesian Network → Deep Directed Network
贝叶斯派的深度学习范式被称为 Deep Generative Model,也属于现代深度学习的分支,但因为概率图模型本身在增加深度后学习和推理难度显著增加,因此深度学习很多时候在狭义上指 Deep Neural Network 为基础的频率派深度学习方法。