第13章 半监督学习
13.1 未标记样本
"西瓜书"两张插图可谓本节亮点: 图 13.1 直观地说
明了使用末标记样本后带来的好处; 图 13.2
对比了主动学习、(纯)半监督学习和直推学习,
尤其是巧妙地将主动学习的概念融入进来。
直推学习是综合运用手头上已有的少量有标记样本和大量末标记样本,
对这些大量末标 记样本预测其标记;
而(纯)半监督学习是综合运用手头上已有的少量有标记样本和大量末标 记样本,
对新的末标记样本预测其标记。
对于直推学习, 当然可以仅利用有标记样本训练一个学习器,
再对末标记样本进行预测, 此即传统的监督学习; 对于(纯)半监督学习,
当然也可以舍弃大量末标记样本, 仅利用有标 记样本训练一个学习器,
再对新的末标记样本进行预测。但图 13.1 直观地说明了使用末标
记样本后带来的好处, 然而利用了末标记样本后是否真的会如图 13.1
所示带来预期的好处 呢? 此即 13.7 节阅读材料中提到的安全半监督学习。
接下来在 13.2 节、13.3 节、13.4 节、13.5 节介绍的四种半监督学习方法,
都可以应用 于直推学习, 但若要应用于(纯)半监督学习, 则要有额外的考虑,
尤其是 13.4 节介绍的图半 监督学习, 因为该节最后一段也明确提到
"构图过程仅能考虑训练样本集, 难以判知新样本 在图中的位置, 因此,
在接收到新样本时, 或是将其加入原数据集对图进行重构并重新进行 标记传播,
或是需引入额外的预测机制"。
13.2 生成式方法
本节与 9.4.3 节的高斯混合聚类密切相关, 有关 9.4.3 节的公式推导参见附录,
建议将高 斯混合聚类的内容理解之后再学习本节算法。
13.2.1 式(13.1)的解释
高斯混合分布的定义式。该式即为9.4.3节的式(9.29)，式(9.29)中的k k k N N N
13.2.2 式(13.2)的推导
首先, 该式的变量 Θ ∈ { 1 , 2 , … , N } \Theta \in\{1,2, \ldots, N\} Θ ∈ { 1 , 2 , … , N } z j ∈ { 1 , 2 , … , k } z_j \in\{1,2, \ldots, k\} z j ∈ { 1 , 2 , … , k }
从公式第 1 行到第 2
行是对概率进行边缘化(marginalization)；通过引入Θ \Theta Θ ∑ i = 1 N \sum_{i=1}^N ∑ i = 1 N
p ( y = j , Θ = i ∣ x ) = p ( y = j , Θ = i , x ) p ( x ) = p ( y = j , Θ = i , x ) p ( Θ = i , x ) ⋅ p ( Θ = i , x ) p ( x ) = p ( y = j ∣ Θ = i , x ) ⋅ p ( Θ = i ∣ x ) \begin{aligned}p(y=j, \Theta=i | \boldsymbol{x}) &=\frac{p(y=j, \Theta=i, \boldsymbol{x})}{p(\boldsymbol{x})} \\&=\frac{p(y=j, \Theta=i, \boldsymbol{x})}{p(\Theta=i, \boldsymbol{x})} \cdot \frac{p(\Theta=i, \boldsymbol{x})}{p(\boldsymbol{x})} \\&=p(y=j | \Theta=i, \boldsymbol{x}) \cdot p(\Theta=i | \boldsymbol{x})\end{aligned} p ( y = j , Θ = i ∣ x ) = p ( x ) p ( y = j , Θ = i , x ) = p ( Θ = i , x ) p ( y = j , Θ = i , x ) ⋅ p ( x ) p ( Θ = i , x ) = p ( y = j ∣Θ = i , x ) ⋅ p ( Θ = i ∣ x ) p ( y = j ∣ x ) p(y=j \mid \boldsymbol{x}) p ( y = j ∣ x ) x \boldsymbol{x} x y y y j j j x ) \boldsymbol{x}) x )
p ( y = j , Θ = i ∣ x ) p(y=j, \Theta=i \mid \boldsymbol{x}) p ( y = j , Θ = i ∣ x ) x \boldsymbol{x} x y y y j j j i i i x \boldsymbol{x} x
p ( y = j ∣ Θ = i , x ) p(y=j \mid \Theta=i, \boldsymbol{x}) p ( y = j ∣ Θ = i , x ) i i i x \boldsymbol{x} x y y y j j j Θ \Theta Θ x \boldsymbol{x} x p ( y = j ∣ Θ = i , x ) p(y=j \mid \Theta=i, \boldsymbol{x}) p ( y = j ∣ Θ = i , x )
p ( Θ = i ∣ x ) p(\Theta=i \mid \boldsymbol{x}) p ( Θ = i ∣ x ) x \boldsymbol{x} x i i i x ) \boldsymbol{x}) x )
"西瓜书"第 296 页第 2 行提到 "假设样本由高斯混合模型生成,
且每个类别对应一个高斯 混合成分", 也就是说, 如果已知 x \boldsymbol{x} x p ( y = j ∣ Θ = i , x ) p(y=j \mid \Theta=i, \boldsymbol{x}) p ( y = j ∣ Θ = i , x ) Θ \Theta Θ x \boldsymbol{x} x Θ \Theta Θ x \boldsymbol{x} x
p ( y = j ∣ Θ = i , x ) = { 1 , i = j 0 , i ≠ j p(y=j \mid \Theta=i, \boldsymbol{x})= \begin{cases}1, & i=j \\ 0, & i \neq j\end{cases} p ( y = j ∣ Θ = i , x ) = { 1 , 0 , i = j i = j 13.2.3 式(13.3)的推导
根据式(13.1)
p ( x ) = ∑ i = 1 N α i ⋅ p ( x ∣ μ i , Σ i ) p(\boldsymbol{x})=\sum_{i=1}^{N} \alpha_{i} \cdot p\left(\boldsymbol{x} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right) p ( x ) = i = 1 ∑ N α i ⋅ p ( x ∣ μ i , Σ i ) 因此
p ( Θ = i ∣ x ) = p ( Θ = i , x ) P ( x ) = α i ⋅ p ( x ∣ μ i , Σ i ) ∑ i = 1 N α i ⋅ p ( x ∣ μ i , Σ i ) \begin{aligned}p(\Theta=i | \boldsymbol{x})&=\frac{p(\Theta=i , \boldsymbol{x})}{P(x)}\\&=\frac{\alpha_{i} \cdot p\left(\boldsymbol{x} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)}{\sum_{i=1}^{N} \alpha_{i} \cdot p\left(\boldsymbol{x} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)}\end{aligned} p ( Θ = i ∣ x ) = P ( x ) p ( Θ = i , x ) = ∑ i = 1 N α i ⋅ p ( x ∣ μ i , Σ i ) α i ⋅ p ( x ∣ μ i , Σ i ) 13.2.4 式(13.4)的推导
第二项很好解释，当不知道类别信息的时候，样本x j x_j x j D u D_u D u ln \ln ln ln \ln ln
p ( y = j ∣ Θ = i , x ) = { 1 , i = j 0 , i ≠ j p(y=j | \Theta=i, \boldsymbol{x})=\left\{\begin{array}{ll}1, & i=j \\0, & i \neq j\end{array}\right. p ( y = j ∣Θ = i , x ) = { 1 , 0 , i = j i = j 可知，这项限定了样本x j x_j x j y j y_j y j
13.2.5 式(13.5)的解释
参见式(13.3)，这项可以理解成样本x j x_j x j i i i i i i α i , μ i Σ i \alpha_i,\boldsymbol{\mu}_{i}\boldsymbol{\Sigma}_i α i , μ i Σ i
α i = l i ∣ D l ∣ , where ∣ D l ∣ = ∑ i = 1 N l i μ i = 1 l i ∑ ( x j , y j ) ∈ D l ∧ y j = i x j Σ i = 1 l i ∑ ( x j , y j ) ∈ D l ∧ y j = i ( x j − μ i ) ( x j − μ i ) ⊤ \begin{array}{l}\alpha_{i}=\frac{l_{i}}{\left|D_{l}\right|}, \text { where }\left|D_{l}\right|=\sum_{i=1}^{N} l_{i} \\\boldsymbol{\mu}_{i}=\frac{1}{l_{i}} \sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \boldsymbol{x}_{j} \\\boldsymbol{\Sigma}_{i}=\frac{1}{l_{i}} \sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top}\end{array} α i = ∣ D l ∣ l i , where ∣ D l ∣ = ∑ i = 1 N l i μ i = l i 1 ∑ ( x j , y j ) ∈ D l ∧ y j = i x j Σ i = l i 1 ∑ ( x j , y j ) ∈ D l ∧ y j = i ( x j − μ i ) ( x j − μ i ) ⊤ 其中 l i l_i l i i i i ∣ D l ∣ \left|D_l\right| ∣ D l ∣ ∧ \wedge ∧
13.2.6 式(13.6)的解释
这项可以由
∂ L L ( D l ∪ D u ) ∂ μ i = 0 \cfrac{\partial LL(D_l \cup D_u) }{\partial \mu_i}=0 ∂ μ i ∂ LL ( D l ∪ D u ) = 0 而得，将式
13.4 的两项分别记为：
L L ( D l ) = ∑ ( x j , y j ∈ D l ) ln ( ∑ s = 1 N α s ⋅ p ( x j ∣ μ s , Σ s ) ⋅ p ( y i ∣ Θ = s , x j ) ) = ∑ ( x j , y j ∈ D l ) ln ( α y j ⋅ p ( x j ∣ μ y j , Σ y j ) ) L L ( D u ) = ∑ x j ∈ D u ln ( ∑ s = 1 N α s ⋅ p ( x j ∣ μ s , Σ s ) ) \begin{aligned}LL(D_l)&=\sum_{(\boldsymbol{x_j},y_j \in D_l)}\ln\left(\sum_{s=1}^{N}\alpha_s \cdot p(\boldsymbol{x_j}\vert \boldsymbol{\mu}_s,\boldsymbol{\Sigma}_s) \cdot p(y_i|\Theta = s,\boldsymbol{x_j})\right)\\&=\sum_{(\boldsymbol{x_j},y_j \in D_l)}\ln\left(\alpha_{y_j} \cdot p(\boldsymbol{x_j} \vert \boldsymbol{\mu}_{y_j},\boldsymbol{\Sigma}_{y_j})\right)\\LL(D_u)&=\sum_{\boldsymbol{x_j} \in D_u} \ln\left(\sum_{s=1}^N \alpha_s \cdot p(\boldsymbol{x_j} | \boldsymbol{\mu}_s,\boldsymbol{\Sigma}_s)\right)\end{aligned} LL ( D l ) LL ( D u ) = ( x j , y j ∈ D l ) ∑ ln ( s = 1 ∑ N α s ⋅ p ( x j ∣ μ s , Σ s ) ⋅ p ( y i ∣Θ = s , x j ) ) = ( x j , y j ∈ D l ) ∑ ln ( α y j ⋅ p ( x j ∣ μ y j , Σ y j ) ) = x j ∈ D u ∑ ln ( s = 1 ∑ N α s ⋅ p ( x j ∣ μ s , Σ s ) ) 首先，L L ( D l ) LL(D_l) LL ( D l ) μ i \boldsymbol{\mu_i} μ i L L ( D l ) LL(D_l) LL ( D l ) y j = i y_j=i y j = i
∂ L L ( D l ) ∂ μ i = ∑ ( x j , y j ) ∈ D l ∧ y j = i ∂ ln ( α i ⋅ p ( x j ∣ μ i , Σ i ) ) ∂ μ i = ∑ ( x j , y j ) ∈ D l ∧ y j = i 1 p ( x j ∣ μ i , Σ i ) ⋅ ∂ p ( x j ∣ μ i , Σ i ) ∂ μ i = ∑ ( x j , y j ) ∈ D l ∧ y j = i 1 p ( x j ∣ μ i , Σ i ) ⋅ p ( x j ∣ μ i , Σ i ) ⋅ Σ i − 1 ( x j − μ i ) = ∑ ( x j , y j ) ∈ D l ∧ y j = i Σ i − 1 ( x j − μ i ) \begin{aligned}\frac{\partial L L\left(D_{l}\right)}{\partial \boldsymbol{\mu}_{i}} &=\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \frac{\partial \ln \left(\alpha_{i} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)\right)}{\partial \boldsymbol{\mu}_{i}} \\&=\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \frac{1}{p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)} \cdot \frac{\partial p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)}{\partial \boldsymbol{\mu}_{i}} \\&=\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \frac{1}{p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right) \cdot \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right) \\&=\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\end{aligned} ∂ μ i ∂ LL ( D l ) = ( x j , y j ) ∈ D l ∧ y j = i ∑ ∂ μ i ∂ ln ( α i ⋅ p ( x j ∣ μ i , Σ i ) ) = ( x j , y j ) ∈ D l ∧ y j = i ∑ p ( x j ∣ μ i , Σ i ) 1 ⋅ ∂ μ i ∂ p ( x j ∣ μ i , Σ i ) = ( x j , y j ) ∈ D l ∧ y j = i ∑ p ( x j ∣ μ i , Σ i ) 1 ⋅ p ( x j ∣ μ i , Σ i ) ⋅ Σ i − 1 ( x j − μ i ) = ( x j , y j ) ∈ D l ∧ y j = i ∑ Σ i − 1 ( x j − μ i ) L L ( D u ) LL(D_u) LL ( D u ) μ i \boldsymbol{\mu_i} μ i
∂ L L ( D u ) ∂ μ i = ∑ x j ∈ D u α i ∑ s = 1 N α s ⋅ p ( x j ∣ μ s , Σ s ) ⋅ p ( x j ∣ μ i , Σ i ) ⋅ Σ i − 1 ( x j − μ i ) = ∑ x j ∈ D u γ j i ⋅ Σ i − 1 ( x j − μ i ) \begin{aligned}
\frac{\partial L L\left(D_{u}\right)}{\partial \boldsymbol{\mu}_{i}} &=\sum_{\boldsymbol{x}_{j} \in D_{u}} \frac{\alpha_{i}}{\sum_{s=1}^{N} \alpha_{s} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{s}, \boldsymbol{\Sigma}_{s}\right)} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right) \cdot \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right) \\
&=\sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i} \cdot \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)
\end{aligned} ∂ μ i ∂ LL ( D u ) = x j ∈ D u ∑ ∑ s = 1 N α s ⋅ p ( x j ∣ μ s , Σ s ) α i ⋅ p ( x j ∣ μ i , Σ i ) ⋅ Σ i − 1 ( x j − μ i ) = x j ∈ D u ∑ γ j i ⋅ Σ i − 1 ( x j − μ i ) 综上，
∂ L L ( D l ∪ D u ) ∂ μ i = ∑ ( x j , y j ) ∈ D l ∧ y j = i Σ i − 1 ( x j − μ i ) + ∑ x j ∈ D u γ j i ⋅ Σ i − 1 ( x j − μ i ) = Σ i − 1 ( ∑ ( x j , y j ) ∈ D l ∧ y j = i ( x j − μ i ) + ∑ x j ∈ D u γ j i ⋅ ( x j − μ i ) ) = Σ i − 1 ( ∑ ( x j , y j ) ∈ D l ∧ y j = i x j + ∑ x j ∈ D u γ j i ⋅ x j − ∑ ( x j , y j ) ∈ D l ∧ y j = i μ i − ∑ x j ∈ D u γ j i ⋅ μ i ) \begin{aligned}\frac{\partial L L\left(D_{l} \cup D_{u}\right)}{\partial \boldsymbol{\mu}_{i}} &=\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)+\sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i} \cdot \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right) \\&=\boldsymbol{\Sigma}_{i}^{-1}\left(\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)+\sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i} \cdot\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\right) \\&=\boldsymbol{\Sigma}_{i}^{-1}\left(\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \boldsymbol{x}_{j}+\sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i} \cdot \boldsymbol{x}_{j}-\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \boldsymbol{\mu}_{i}-\sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i} \cdot \boldsymbol{\mu}_{i}\right)\end{aligned} ∂ μ i ∂ LL ( D l ∪ D u ) = ( x j , y j ) ∈ D l ∧ y j = i ∑ Σ i − 1 ( x j − μ i ) + x j ∈ D u ∑ γ j i ⋅ Σ i − 1 ( x j − μ i ) = Σ i − 1 ( x j , y j ) ∈ D l ∧ y j = i ∑ ( x j − μ i ) + x j ∈ D u ∑ γ j i ⋅ ( x j − μ i ) = Σ i − 1 ( x j , y j ) ∈ D l ∧ y j = i ∑ x j + x j ∈ D u ∑ γ j i ⋅ x j − ( x j , y j ) ∈ D l ∧ y j = i ∑ μ i − x j ∈ D u ∑ γ j i ⋅ μ i 令∂ L L ( D l ∪ D u ) ∂ μ i = 0 \frac{\partial L L\left(D_{l} \cup D_{u}\right)}{\partial \boldsymbol{\mu}_{i}}=0 ∂ μ i ∂ LL ( D l ∪ D u ) = 0 Σ i \Sigma_i Σ i
∑ x j ∈ D u γ j i ⋅ μ i + ∑ ( x j , y j ) ∈ D l ∧ y j = i μ i = ∑ x j ∈ D u γ j i ⋅ x j + ∑ ( x j , y j ) ∈ D l ∧ y j = i x j \sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i} \cdot \boldsymbol{\mu}_{i}+\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \boldsymbol{\mu}_{i}=\sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i} \cdot \boldsymbol{x}_{j}+\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \boldsymbol{x}_{j} x j ∈ D u ∑ γ j i ⋅ μ i + ( x j , y j ) ∈ D l ∧ y j = i ∑ μ i = x j ∈ D u ∑ γ j i ⋅ x j + ( x j , y j ) ∈ D l ∧ y j = i ∑ x j 上式中，μ i \boldsymbol{\mu_i} μ i ∑ ( x j , y j ) ∈ D l ∧ y j = i 1 = l i \sum_{\left(x_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} 1=l_{i} ∑ ( x j , y j ) ∈ D l ∧ y j = i 1 = l i i i i
( ∑ x j ∈ D u γ j i + ∑ ( x j , y j ) ∈ D l ∧ y j = i 1 ) μ i = ∑ x j ∈ D u γ j i ⋅ x j + ∑ ( x j , y j ) ∈ D l ∧ y j = i x j \left(\sum_{x_{j} \in D_{u}} \gamma_{j i}+\sum_{\left(x_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} 1\right) \boldsymbol{\mu}_{i}=\sum_{x_{j} \in D_{u}} \gamma_{j i} \cdot \boldsymbol{x}_{j}+\sum_{\left(x_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \boldsymbol{x}_{j} x j ∈ D u ∑ γ j i + ( x j , y j ) ∈ D l ∧ y j = i ∑ 1 μ i = x j ∈ D u ∑ γ j i ⋅ x j + ( x j , y j ) ∈ D l ∧ y j = i ∑ x j 即得式(13.6)。
13.2.7 式(13.7)的解释
首先L L ( D l ) LL(D_l) LL ( D l ) Σ i \boldsymbol{\Sigma_i} Σ i
∂ L L ( D l ) ∂ Σ i = ∑ ( x j , y j ) ∈ D l ∧ y j = i ∂ ln ( α i ⋅ p ( x j ∣ μ i , Σ i ) ) ∂ Σ i = ∑ ( x j , y j ) ∈ D l ∧ y j = i 1 p ( x j ∣ μ i , Σ i ) ⋅ ∂ p ( x j ∣ μ i , Σ i ) ∂ Σ i = ∑ ( x j , y j ) ∈ D l ∧ y j = i 1 p ( x j ∣ μ i , Σ i ) ⋅ p ( x j ∣ μ i , Σ i ) ⋅ ( Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ − I ) ⋅ 1 2 Σ i − 1 = ∑ ( x j , y j ) ∈ D l ∧ y j = i ( Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ − I ) ⋅ 1 2 Σ i − 1 \begin{aligned} \frac{\partial L L\left(D_{l}\right)}{\partial \boldsymbol{\Sigma}_{i}} &=\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \frac{\partial \ln \left(\alpha_{i} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)\right)}{\partial \boldsymbol{\Sigma}_{i}} \\ &=\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \frac{1}{p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)} \cdot \frac{\partial p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)}{\partial \boldsymbol{\Sigma}_{i}} \\
&=\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \frac{1}{p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right) \cdot\left(\boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top}-\boldsymbol{I}\right) \cdot \frac{1}{2} \boldsymbol{\Sigma}_{i}^{-1}\\
&=\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i}\left(\boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top}-\boldsymbol{I}\right) \cdot \frac{1}{2} \boldsymbol{\Sigma}_{i}^{-1}
\end{aligned} ∂ Σ i ∂ LL ( D l ) = ( x j , y j ) ∈ D l ∧ y j = i ∑ ∂ Σ i ∂ ln ( α i ⋅ p ( x j ∣ μ i , Σ i ) ) = ( x j , y j ) ∈ D l ∧ y j = i ∑ p ( x j ∣ μ i , Σ i ) 1 ⋅ ∂ Σ i ∂ p ( x j ∣ μ i , Σ i ) = ( x j , y j ) ∈ D l ∧ y j = i ∑ p ( x j ∣ μ i , Σ i ) 1 ⋅ p ( x j ∣ μ i , Σ i ) ⋅ ( Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ − I ) ⋅ 2 1 Σ i − 1 = ( x j , y j ) ∈ D l ∧ y j = i ∑ ( Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ − I ) ⋅ 2 1 Σ i − 1 然后L L ( D u ) LL(D_u) LL ( D u ) Σ i \boldsymbol{\Sigma_i} Σ i
∂ L L ( D u ) ∂ Σ i = ∑ x j ∈ D u γ j i ⋅ ( Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ − I ) ⋅ 1 2 Σ i − 1 \frac{\partial L L\left(D_{u}\right)}{\partial \boldsymbol{\Sigma}_{i}}=\sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i} \cdot\left(\boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top}-\boldsymbol{I}\right) \cdot \frac{1}{2} \boldsymbol{\Sigma}_{i}^{-1} ∂ Σ i ∂ LL ( D u ) = x j ∈ D u ∑ γ j i ⋅ ( Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ − I ) ⋅ 2 1 Σ i − 1 综合可得：
∂ L L ( D l ∪ D u ) ∂ Σ i = ∑ x j ∈ D u γ j i ⋅ ( Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ − I ) ⋅ 1 2 Σ i − 1 + ∑ ( x j , y j ) ∈ D l ∧ y j = i ( Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ − I ) ⋅ 1 2 Σ i − 1 = ( ∑ x j ∈ D u γ j i ⋅ ( Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ − I ) + ∑ ( x j , y j ) ∈ D l ∧ y j = i ( Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ − I ) ) ⋅ 1 2 Σ i − 1 \begin{aligned} \frac{\partial L L\left(D_{l} \cup D_{u}\right)}{\partial \boldsymbol{\Sigma}_{i}}=& \sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i} \cdot\left(\boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top}-\boldsymbol{I}\right) \cdot \frac{1}{2} \boldsymbol{\Sigma}_{i}^{-1} \\ &+\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i}\left(\boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top}-\boldsymbol{I}\right) \cdot \frac{1}{2} \boldsymbol{\Sigma}_{i}^{-1} \\=&\left(\sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i} \cdot\left(\boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top}-\boldsymbol{I}\right)\right.\\ &\left.+\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i}\left(\boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top}-\boldsymbol{I}\right)\right) \cdot \frac{1}{2} \boldsymbol{\Sigma}_{i}^{-1} \end{aligned} ∂ Σ i ∂ LL ( D l ∪ D u ) = = x j ∈ D u ∑ γ j i ⋅ ( Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ − I ) ⋅ 2 1 Σ i − 1 + ( x j , y j ) ∈ D l ∧ y j = i ∑ ( Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ − I ) ⋅ 2 1 Σ i − 1 x j ∈ D u ∑ γ j i ⋅ ( Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ − I ) + ( x j , y j ) ∈ D l ∧ y j = i ∑ ( Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ − I ) ⋅ 2 1 Σ i − 1 令∂ L L ( D l ∪ D u ) ∂ Σ i = 0 \frac{\partial L L\left(D_{l} \cup D_{u}\right)}{\partial \boldsymbol{\Sigma}_{i}}=0 ∂ Σ i ∂ LL ( D l ∪ D u ) = 0 2 Σ i 2\Sigma_i 2 Σ i
∑ x j ∈ D u γ j i ⋅ Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ + ∑ ( x j , y j ∈ D l ∧ y j = i Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ = ∑ x j ∈ D u γ j i ⋅ I + ∑ ( x j , y j ) ∈ D l ∧ y j = i I = ( ∑ x j ∈ D u γ j i + l i ) I \begin{aligned} \sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i} \cdot \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top}+& \sum_{\left(\boldsymbol{x}_{j}, y_{j} \in D_{l} \wedge y_{j}=i\right.} \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top} \\=& \sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i} \cdot \boldsymbol{I}+\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \boldsymbol{I} \\ &=\left(\sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i}+l_{i}\right) \boldsymbol{I} \end{aligned} x j ∈ D u ∑ γ j i ⋅ Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ + = ( x j , y j ∈ D l ∧ y j = i ∑ Σ i − 1 ( x j − μ i ) ( x j − μ i ) ⊤ x j ∈ D u ∑ γ j i ⋅ I + ( x j , y j ) ∈ D l ∧ y j = i ∑ I = x j ∈ D u ∑ γ j i + l i I 两边同时左乘以Σ i \Sigma_i Σ i
∑ x j ∈ D u γ j i ⋅ ( x j − μ i ) ( x j − μ i ) ⊤ + ∑ ( x j , y j ) ∈ D l ∧ y j = i ( x j − μ i ) ( x j − μ i ) ⊤ = ( ∑ x j ∈ D u γ j i + l i ) Σ i \sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i} \cdot\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top}+\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top}=\left(\sum_{\boldsymbol{x}_{j} \in D_{u}} \gamma_{j i}+l_{i}\right) \boldsymbol{\Sigma}_{i} x j ∈ D u ∑ γ j i ⋅ ( x j − μ i ) ( x j − μ i ) ⊤ + ( x j , y j ) ∈ D l ∧ y j = i ∑ ( x j − μ i ) ( x j − μ i ) ⊤ = x j ∈ D u ∑ γ j i + l i Σ i 即得式(13.7)。
13.2.8 式(13.8)的解释
类似于式(9.36)，写出L L ( D l ∪ D u ) LL(D_l \cup D_u) LL ( D l ∪ D u )
L ( D l ∪ D u , λ ) = L L ( D l ∪ D u ) + λ ( ∑ s = 1 N α s − 1 ) = L L ( D l ) + L L ( D u ) + λ ( ∑ s = 1 N α s − 1 ) \begin{aligned}\mathcal{L}\left(D_{l} \cup D_{u}, \lambda\right) &=L L\left(D_{l} \cup D_{u}\right)+\lambda\left(\sum_{s=1}^{N} \alpha_{s}-1\right) \\&=L L\left(D_{l}\right)+L L\left(D_{u}\right)+\lambda\left(\sum_{s=1}^{N} \alpha_{s}-1\right)\end{aligned} L ( D l ∪ D u , λ ) = LL ( D l ∪ D u ) + λ ( s = 1 ∑ N α s − 1 ) = LL ( D l ) + LL ( D u ) + λ ( s = 1 ∑ N α s − 1 ) 类似于式(9.37)，对α i \alpha_i α i L L ( D u ) LL(D_u) LL ( D u )
∂ L L ( D u ) ∂ α i = ∑ x j ∈ D u 1 ∑ s = 1 N α s ⋅ p ( x j ∣ μ s , Σ s ) ⋅ p ( x j ∣ μ i , Σ i ) \frac{\partial L L\left(D_{u}\right)}{\partial \alpha_{i}}=\sum_{\boldsymbol{x}_{j} \in D_{u}} \frac{1}{\sum_{s=1}^{N} \alpha_{s} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{s}, \boldsymbol{\Sigma}_{s}\right)} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right) ∂ α i ∂ LL ( D u ) = x j ∈ D u ∑ ∑ s = 1 N α s ⋅ p ( x j ∣ μ s , Σ s ) 1 ⋅ p ( x j ∣ μ i , Σ i ) 对于L L ( D l ) LL(D_l) LL ( D l )
∂ L L ( D l ) ∂ α i = ∑ ( x j , y j ) ∈ D l ∧ y j = i ∂ ln ( α i ⋅ p ( x j ∣ μ i , Σ i ) ) ∂ α i = ∑ ( x j , y j ) ∈ D l ∧ y j = i 1 α i ⋅ p ( x j ∣ μ i , Σ i ) ⋅ ∂ ( α i ⋅ p ( x j ∣ μ i , Σ i ) ) ∂ α i = ∑ ( x j , y j ) ∈ D l ∧ y j = i 1 α i ⋅ p ( x j ∣ μ i , Σ i ) ⋅ p ( x j ∣ μ i , Σ i ) = ∑ ( x j , y j ) ∈ D l ∧ y j = i 1 α i = 1 α i ⋅ ∑ ( x j , y j ) ∈ D l ∧ y j = i 1 = l i α i \begin{aligned}\frac{\partial L L\left(D_{l}\right)}{\partial \alpha_{i}} &=\sum_{\left(x_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \frac{\partial \ln \left(\alpha_{i} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)\right)}{\partial \alpha_{i}} \\&=\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \frac{1}{\alpha_{i} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)} \cdot \frac{\partial\left(\alpha_{i} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)\right)}{\partial \alpha_{i}} \\&=\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \frac{1}{\alpha_{i} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right) \\&=\sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} \frac{1}{\alpha_{i}}=\frac{1}{\alpha_{i}} \cdot \sum_{\left(\boldsymbol{x}_{j}, y_{j}\right) \in D_{l} \wedge y_{j}=i} 1=\frac{l_{i}}{\alpha_{i}}\end{aligned} ∂ α i ∂ LL ( D l ) = ( x j , y j ) ∈ D l ∧ y j = i ∑ ∂ α i ∂ ln ( α i ⋅ p ( x j ∣ μ i , Σ i ) ) = ( x j , y j ) ∈ D l ∧ y j = i ∑ α i ⋅ p ( x j ∣ μ i , Σ i ) 1 ⋅ ∂ α i ∂ ( α i ⋅ p ( x j ∣ μ i , Σ i ) ) = ( x j , y j ) ∈ D l ∧ y j = i ∑ α i ⋅ p ( x j ∣ μ i , Σ i ) 1 ⋅ p ( x j ∣ μ i , Σ i ) = ( x j , y j ) ∈ D l ∧ y j = i ∑ α i 1 = α i 1 ⋅ ( x j , y j ) ∈ D l ∧ y j = i ∑ 1 = α i l i 上式推导过程中，重点注意变量是α i \alpha_i α i p ( x j ∣ μ i , Σ i ) p(x_j|\mu_i,\Sigma_i) p ( x j ∣ μ i , Σ i ) α i \alpha_i α i l i l_i l i i i i
综合两项结果：
∂ L ( D l ∪ D u , λ ) ∂ α i = l i α i + ∑ x j ∈ D u p ( x j ∣ μ i , Σ i ) ∑ s = 1 N α s ⋅ p ( x j ∣ μ s , Σ s ) + λ \frac{\partial \mathcal{L}\left(D_{l} \cup D_{u}, \lambda\right)}{\partial \alpha_{i}}=\frac{l_{i}}{\alpha_{i}}+\sum_{\boldsymbol{x}_{j} \in D_{u}} \frac{p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)}{\sum_{s=1}^{N} \alpha_{s} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{s}, \boldsymbol{\Sigma}_{s}\right)}+\lambda ∂ α i ∂ L ( D l ∪ D u , λ ) = α i l i + x j ∈ D u ∑ ∑ s = 1 N α s ⋅ p ( x j ∣ μ s , Σ s ) p ( x j ∣ μ i , Σ i ) + λ 令∂ L L ( D l ∪ D u ) ∂ α i = 0 \cfrac{\partial LL(D_l \cup D_u) }{\partial \alpha_i}=0 ∂ α i ∂ LL ( D l ∪ D u ) = 0 α i \alpha_i α i
α i ⋅ l i α i + ∑ x j ∈ D u α i ⋅ p ( x j ∣ μ i , Σ i ) ∑ s = 1 N α s ⋅ p ( x j ∣ μ s , Σ s ) + λ ⋅ α i = 0 \alpha_{i} \cdot \frac{l_{i}}{\alpha_{i}}+\sum_{\boldsymbol{x}_{j} \in D_{u}} \frac{\alpha_{i} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)}{\sum_{s=1}^{N} \alpha_{s} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{s}, \boldsymbol{\Sigma}_{s}\right)}+\lambda \cdot \alpha_{i}=0 α i ⋅ α i l i + x j ∈ D u ∑ ∑ s = 1 N α s ⋅ p ( x j ∣ μ s , Σ s ) α i ⋅ p ( x j ∣ μ i , Σ i ) + λ ⋅ α i = 0 结合式(9.30)发现，求和号内即为后验概率γ j i \gamma_{ji} γ j i
l i + ∑ x i ∈ D u γ j i + λ α i = 0 l_i+\sum_{x_i \in D_u} \gamma_{ji}+\lambda \alpha_i = 0 l i + x i ∈ D u ∑ γ j i + λ α i = 0 对所有混合成分求和，得
∑ i = 1 N l i + ∑ i = 1 N ∑ x i ∈ D u γ j i + ∑ i = 1 N λ α i = 0 \sum_{i=1}^N l_i+\sum_{i=1}^N \sum_{x_i \in D_u} \gamma_{ji}+\sum_{i=1}^N \lambda \alpha_i = 0 i = 1 ∑ N l i + i = 1 ∑ N x i ∈ D u ∑ γ j i + i = 1 ∑ N λ α i = 0 这里∑ i = 1 N α i = 1 \sum_{i=1}^N \alpha_i =1 ∑ i = 1 N α i = 1 ∑ i = 1 N λ α i = λ ∑ i = 1 N α i = λ \sum_{i=1}^N \lambda \alpha_i=\lambda\sum_{i=1}^N \alpha_i=\lambda ∑ i = 1 N λ α i = λ ∑ i = 1 N α i = λ γ j i \gamma_{ji} γ j i
∑ i = 1 N γ j i = ∑ i = 1 N α i ⋅ p ( x j ∣ μ i , Σ i ) Σ s = 1 N α s ⋅ p ( x j ∣ μ s , Σ s ) = ∑ i = 1 N α i ⋅ p ( x j ∣ μ i , Σ i ) ∑ s = 1 N α s ⋅ p ( x j ∣ μ s , Σ s ) = 1 \sum_{i=1}^N \gamma_{ji} = \sum_{i =1}^{N} \cfrac{\alpha_i \cdot p(x_j|\mu_i,\Sigma_i)}{\Sigma_{s=1}^N \alpha_s \cdot p(x_j| \mu_s, \Sigma_s)}= \cfrac{\sum_{i =1}^{N}\alpha_i \cdot p(x_j|\mu_i,\Sigma_i)}{\sum_{s=1}^N \alpha_s \cdot p(x_j| \mu_s, \Sigma_s)}=1 i = 1 ∑ N γ j i = i = 1 ∑ N Σ s = 1 N α s ⋅ p ( x j ∣ μ s , Σ s ) α i ⋅ p ( x j ∣ μ i , Σ i ) = ∑ s = 1 N α s ⋅ p ( x j ∣ μ s , Σ s ) ∑ i = 1 N α i ⋅ p ( x j ∣ μ i , Σ i ) = 1 再结合加法满足交换律，所以
∑ i = 1 N ∑ x i ∈ D u γ j i = ∑ x i ∈ D u ∑ i = 1 N γ j i = ∑ x i ∈ D u 1 = u \sum_{i=1}^N \sum_{x_i \in D_u} \gamma_{ji}=\sum_{x_i \in D_u} \sum_{i=1}^N \gamma_{ji} =\sum_{x_i \in D_u} 1=u i = 1 ∑ N x i ∈ D u ∑ γ j i = x i ∈ D u ∑ i = 1 ∑ N γ j i = x i ∈ D u ∑ 1 = u 以上分析过程中，∑ x j ∈ D u \sum_{x_j\in D_u} ∑ x j ∈ D u ∑ j = 1 u \sum_{j=1}^u ∑ j = 1 u ∑ i = 1 N l i = l \sum_{i=1}^Nl_i=l ∑ i = 1 N l i = l l l l
∑ i = 1 N l i + ∑ i = 1 N ∑ x i ∈ D u γ j i + ∑ i = 1 N λ α i = 0 \sum_{i=1}^N l_i+\sum_{i=1}^N \sum_{x_i \in D_u} \gamma_{ji}+\sum_{i=1}^N \lambda \alpha_i = 0 i = 1 ∑ N l i + i = 1 ∑ N x i ∈ D u ∑ γ j i + i = 1 ∑ N λ α i = 0 解出l + u + λ = 0 l+u+\lambda = 0 l + u + λ = 0 l + u = m l+u =m l + u = m m m m λ = − m \lambda = -m λ = − m
l i + ∑ x j ∈ D u γ j i − λ α i = 0 l_i + \sum_{x_j \in{D_u}} \gamma_{ji}-\lambda \alpha_i = 0 l i + x j ∈ D u ∑ γ j i − λ α i = 0 即 l i + ∑ x j ∈ D u γ j i − m α i = 0 l_i+\sum_{\boldsymbol{x}_j \in D_u} \gamma_{j i}-m \alpha_i=0 l i + ∑ x j ∈ D u γ j i − m α i = 0
13.3 半监督SVM
从本节名称"半监督SVM"即可知道与第6章的SVM内容联系紧密。建议理解了SVM之后再学习本节算法，会发现实际很简单；否则会感觉无从下手，难以理解。
由本节开篇的两段介绍可知，S3VM是SVM在半监督学习上的推广，是此类算法的总称而非某个具体的算法，其最著名的代表是TSVM。
13.3.1 图13.3的解释
注意对比S3VM划分超平面穿过的区域与SVM划分超平面穿过的区域的差别，明显S3VM划分超平面周围样本较少，也就是"数据低密度区域"，即"低密度分隔"。
13.3.2 式(13.9)的解释
这个公式和式(6.35)基本一致，除了引入了无标记样本的松弛变量ξ i , i = l + 1 , ⋯ m \xi_i, i=l+1,\cdots m ξ i , i = l + 1 , ⋯ m C u C_u C u y ^ i \hat{y}_i y ^ i
13.3.3 图13.4的解释
解释一下第 6 行:
（1）y ^ i y ^ j < 0 \hat{y}_i \hat{y}_j<0 y ^ i y ^ j < 0 x i , x j \boldsymbol{x}_i, \boldsymbol{x}_j x i , x j y ^ i , y ^ j \hat{y}_i, \hat{y}_j y ^ i , y ^ j + 1 +1 + 1 − 1 -1 − 1
（2）ξ i > 0 \xi_i>0 ξ i > 0 x i \boldsymbol{x}_i x i ( 0 < ξ i < 1 ) \left(0<\xi_i<1\right) ( 0 < ξ i < 1 ) ( 1 < ξ i < 2 ) \left(1<\xi_i<2\right) ( 1 < ξ i < 2 ) ( ξ i > 2 ) \left(\xi_i>2\right) ( ξ i > 2 )
（3）ξ i + ξ j > 2 \xi_i+\xi_j>2 ξ i + ξ j > 2 ( ξ i > 1 ) ∧ ( ξ j > 1 ) \left(\xi_i>1\right) \wedge\left(\xi_j>1\right) ( ξ i > 1 ) ∧ ( ξ j > 1 )
可以发现, 当 1 < ξ i , ξ j < 2 1<\xi_i, \xi_j<2 1 < ξ i , ξ j < 2 ξ i + ξ j \xi_i+\xi_j ξ i + ξ j ξ i , ξ j > 2 \xi_i, \xi_j>2 ξ i , ξ j > 2 ξ i + ξ j \xi_i+\xi_j ξ i + ξ j
可以发现, 交换之后两个样本均被分类正确, 因此松弛变量均等于 0。至于
ξ i , ξ j \xi_i, \xi_j ξ i , ξ j 1 ∼ 2 1 \sim 2 1 ∼ 2
(II) ( 0 < ξ i < 1 ) ∧ ( ξ j > 2 − ξ i ) \left(0<\xi_i<1\right) \wedge\left(\xi_j>2-\xi_i\right) ( 0 < ξ i < 1 ) ∧ ( ξ j > 2 − ξ i )
(II.1) 1 < ξ j < 2 1<\xi_j<2 1 < ξ j < 2
可以发现, 此时两个样本位置超平面同一侧, 交换标记之后似乎没发生什么变化,
但是仔细观察会发现交换之后 ξ i + ξ j \xi_i+\xi_j ξ i + ξ j
(II.2) ξ j > 2 \xi_j>2 ξ j > 2
可以发现, 交换之后其中之一被正确分类, ξ i + ξ j \xi_i+\xi_j ξ i + ξ j ξ i + ξ j > 2 \xi_i+\xi_j>2 ξ i + ξ j > 2 y ^ i , y ^ j \hat{y}_i, \hat{y}_j y ^ i , y ^ j ξ i + ξ j \xi_i+\xi_j ξ i + ξ j C u C_u C u C l C_l C l
13.3.4 式(13.10)的解释
将该式变形为 C u + C u − = u − u + \frac{C_u^{+}}{C_u^{-}}=\frac{u_{-}}{u_{+}} C u − C u + = u + u −
13.4 图半监督学习
本节共讲了两种方法，其中式(13.11)
~式(13.17)讲述了一个针对二分类问题的标记传播方法，式(13.18)
~式(13.21)讲述了一个针对多分类问题的标记传播方法，两种方法的原理均为两种方法的原理均为"相似的样本应具有相似的标记"，只是面向的问题不同，而且具体实现的方法也不同。
13.4.1 式(13.12)的推导
注意, 该方法针对二分类问题的标记传播方法。我们希望能量函数 E ( f ) E(f) E ( f ) 0 < ( W ) i j ⩽ 1 0<(\mathbf{W})_{i j} \leqslant 1 0 < ( W ) ij ⩽ 1 x i \boldsymbol{x}_i x i x j \boldsymbol{x}_j x j ∥ x i − x j ∥ 2 \left\|\boldsymbol{x}_i-\boldsymbol{x}_j\right\|^2 ∥ x i − x j ∥ 2 ( W ) i j (\mathbf{W})_{i j} ( W ) ij ( f ( x i ) − f ( x j ) ) 2 \left(f\left(\boldsymbol{x}_i\right)-f\left(\boldsymbol{x}_j\right)\right)^2 ( f ( x i ) − f ( x j ) ) 2 E ( f ) E(f) E ( f )
E ( f ) = 1 2 ∑ i = 1 m ∑ j = 1 m ( W ) i j ( f ( x i ) − f ( x j ) ) 2 = 1 2 ∑ i = 1 m ∑ j = 1 m ( W ) i j ( f 2 ( x i ) − 2 f ( x i ) f ( x j ) + f 2 ( x j ) ) = 1 2 ∑ i = 1 m ∑ j = 1 m ( W ) i j f 2 ( x i ) + 1 2 ∑ i = 1 m ∑ j = 1 m ( W ) i j f 2 ( x j ) − ∑ i = 1 m ∑ j = 1 m ( W ) i j f ( x i ) f ( x j ) \begin{aligned}
E(f) & =\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m(\mathbf{W})_{i j}\left(f\left(\boldsymbol{x}_i\right)-f\left(\boldsymbol{x}_j\right)\right)^2 \\
& =\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m(\mathbf{W})_{i j}\left(f^2\left(\boldsymbol{x}_i\right)-2 f\left(\boldsymbol{x}_i\right) f\left(\boldsymbol{x}_j\right)+f^2\left(\boldsymbol{x}_j\right)\right) \\
& =\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m(\mathbf{W})_{i j} f^2\left(\boldsymbol{x}_i\right)+\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m(\mathbf{W})_{i j} f^2\left(\boldsymbol{x}_j\right)-\sum_{i=1}^m \sum_{j=1}^m(\mathbf{W})_{i j} f\left(\boldsymbol{x}_i\right) f\left(\boldsymbol{x}_j\right)
\end{aligned} E ( f ) = 2 1 i = 1 ∑ m j = 1 ∑ m ( W ) ij ( f ( x i ) − f ( x j ) ) 2 = 2 1 i = 1 ∑ m j = 1 ∑ m ( W ) ij ( f 2 ( x i ) − 2 f ( x i ) f ( x j ) + f 2 ( x j ) ) = 2 1 i = 1 ∑ m j = 1 ∑ m ( W ) ij f 2 ( x i ) + 2 1 i = 1 ∑ m j = 1 ∑ m ( W ) ij f 2 ( x j ) − i = 1 ∑ m j = 1 ∑ m ( W ) ij f ( x i ) f ( x j ) 然后证明
∑ i = 1 m ∑ j = 1 m ( W ) i j f 2 ( x i ) = ∑ i = 1 m ∑ j = 1 m ( W ) i j f 2 ( x j ) \sum_{i=1}^m \sum_{j=1}^m(\mathbf{W})_{i j} f^2\left(\boldsymbol{x}_i\right)=\sum_{i=1}^m \sum_{j=1}^m(\mathbf{W})_{i j} f^2\left(\boldsymbol{x}_j\right) ∑ i = 1 m ∑ j = 1 m ( W ) ij f 2 ( x i ) = ∑ i = 1 m ∑ j = 1 m ( W ) ij f 2 ( x j )
∑ i = 1 m ∑ j = 1 m ( W ) i j f 2 ( x j ) = ∑ j = 1 m ∑ i = 1 m ( W ) j i f 2 ( x i ) = ∑ i = 1 m ∑ j = 1 m ( W ) i j f 2 ( x i ) = ∑ i = 1 m f 2 ( x i ) ∑ j = 1 m ( W ) i j \begin{aligned}
\sum_{i=1}^m \sum_{j=1}^m(\mathbf{W})_{i j} f^2\left(\boldsymbol{x}_j\right) & =\sum_{j=1}^m \sum_{i=1}^m(\mathbf{W})_{j i} f^2\left(\boldsymbol{x}_i\right)=\sum_{i=1}^m \sum_{j=1}^m(\mathbf{W})_{i j} f^2\left(\boldsymbol{x}_i\right) \\
& =\sum_{i=1}^m f^2\left(\boldsymbol{x}_i\right) \sum_{j=1}^m(\mathbf{W})_{i j}
\end{aligned} i = 1 ∑ m j = 1 ∑ m ( W ) ij f 2 ( x j ) = j = 1 ∑ m i = 1 ∑ m ( W ) j i f 2 ( x i ) = i = 1 ∑ m j = 1 ∑ m ( W ) ij f 2 ( x i ) = i = 1 ∑ m f 2 ( x i ) j = 1 ∑ m ( W ) ij 其中, 第 1 个等号是把变量 i , j i, j i , j j , i j, i j , i W \mathbf{W} W ( W ) i j = W ) j i \left.(\mathbf{W})_{i j}=\mathbf{W}\right)_{j i} ( W ) ij = W ) j i f 2 ( x i ) f^2\left(\boldsymbol{x}_i\right) f 2 ( x i ) j j j d i d_i d i d i = ∑ j = 1 m ( W ) i j d_i=\sum_{j=1}^m(\mathbf{W})_{i j} d i = ∑ j = 1 m ( W ) ij W \mathbf{W} W i i i j j j W \mathbf{W} W ( W ) i j = W ) j i \left.(\mathbf{W})_{i j}=\mathbf{W}\right)_{j i} ( W ) ij = W ) j i d i = ∑ j = 1 m ( W ) j i d_i=\sum_{j=1}^m(\mathbf{W})_{j i} d i = ∑ j = 1 m ( W ) j i i i i
E ( f ) = ∑ i = 1 m d i f 2 ( x i ) − ∑ i = 1 m ∑ j = 1 m ( W ) i j f ( x i ) f ( x j ) E(f)=\sum_{i=1}^m d_i f^2\left(\boldsymbol{x}_i\right)-\sum_{i=1}^m \sum_{j=1}^m(\mathbf{W})_{i j} f\left(\boldsymbol{x}_i\right) f\left(\boldsymbol{x}_j\right) E ( f ) = i = 1 ∑ m d i f 2 ( x i ) − i = 1 ∑ m j = 1 ∑ m ( W ) ij f ( x i ) f ( x j ) 即式(13.12)的第 3 行, 其中第一项
∑ i = 1 m d i f 2 ( x i ) \sum_{i=1}^m d_i f^2\left(\boldsymbol{x}_i\right) ∑ i = 1 m d i f 2 ( x i )
= f T D f \begin{aligned}
& =\boldsymbol{f}^{\mathrm{T}} \boldsymbol{D} \boldsymbol{f} \\
&
\end{aligned} = f T D f 第二项
∑ i = 1 m ∑ j = 1 m ( W ) i j f ( x i ) f ( x j ) \sum_{i=1}^m \sum_{j=1}^m(\mathbf{W})_{i j} f\left(\boldsymbol{x}_i\right) f\left(\boldsymbol{x}_j\right) ∑ i = 1 m ∑ j = 1 m ( W ) ij f ( x i ) f ( x j )
∑ i = 1 m ∑ j = 1 m ( W ) i j f ( x i ) f ( x j ) = [ f ( x 1 ) f ( x 2 ) ⋯ f ( x m ) ] [ ( W ) 11 ( W ) 12 ⋯ ( W ) 1 m ( W ) 21 ( W ) 22 ⋯ ( W ) 2 m ⋮ ⋮ ⋱ ⋮ ( W ) m 1 ( W ) m 2 ⋯ ( W ) m m ] [ f ( x 1 ) f ( x 2 ) ⋮ f ( x m ) ] = f T W f \begin{aligned}
& \sum_{i=1}^m \sum_{j=1}^m(\mathbf{W})_{i j} f\left(\boldsymbol{x}_i\right) f\left(\boldsymbol{x}_j\right) \\
& =\left[\begin{array}{llll}
f\left(\boldsymbol{x}_1\right) & f\left(\boldsymbol{x}_2\right) & \cdots & f\left(\boldsymbol{x}_m\right)
\end{array}\right]\left[\begin{array}{cccc}
(\mathbf{W})_{11} & (\mathbf{W})_{12} & \cdots & (\mathbf{W})_{1 m} \\
(\mathbf{W})_{21} & (\mathbf{W})_{22} & \cdots & (\mathbf{W})_{2 m} \\
\vdots & \vdots & \ddots & \vdots \\
(\mathbf{W})_{m 1} & (\mathbf{W})_{m 2} & \cdots & (\mathbf{W})_{m m}
\end{array}\right]\left[\begin{array}{c}
f\left(\boldsymbol{x}_1\right) \\
f\left(\boldsymbol{x}_2\right) \\
\vdots \\
f\left(\boldsymbol{x}_m\right)
\end{array}\right] \\
& =\boldsymbol{f}^{\mathrm{T}} \boldsymbol{W} \boldsymbol{f}
\end{aligned} i = 1 ∑ m j = 1 ∑ m ( W ) ij f ( x i ) f ( x j ) = [ f ( x 1 ) f ( x 2 ) ⋯ f ( x m ) ] ( W ) 11 ( W ) 21 ⋮ ( W ) m 1 ( W ) 12 ( W ) 22 ⋮ ( W ) m 2 ⋯ ⋯ ⋱ ⋯ ( W ) 1 m ( W ) 2 m ⋮ ( W ) mm f ( x 1 ) f ( x 2 ) ⋮ f ( x m ) = f T W f 所以
E ( f ) = f T D − f T W f = f T ( D − W ) f E(f)=\boldsymbol{f}^{\mathrm{T}} \boldsymbol{D}-\boldsymbol{f}^{\mathrm{T}} \boldsymbol{W} \boldsymbol{f}=\boldsymbol{f}^{\mathrm{T}}(\boldsymbol{D}-\boldsymbol{W}) \boldsymbol{f} E ( f ) = f T D − f T W f = f T ( D − W ) f
13.4.2 式(13.13)的推导
本式就是将式(13.12)用分块矩阵形式表达而已,
拆分为标记样本和末标记样本两部分。
另外解释一下该式之前一段话中第一句的含义: "具有最小能量的函数 f f f f ( x i ) = y i ( i = 1 , 2 , … , l ) f\left(\boldsymbol{x}_i\right)=y_i(i=1,2, \ldots, l) f ( x i ) = y i ( i = 1 , 2 , … , l ) Δ f = 0 \boldsymbol{\Delta} \boldsymbol{f}=\mathbf{0} Δ f = 0 f ( x i ) = y i ( i = 1 , 2 , … , l ) f\left(\boldsymbol{x}_i\right)=y_i(i=1,2, \ldots, l) f ( x i ) = y i ( i = 1 , 2 , … , l ) f ( x i ) f\left(\boldsymbol{x}_i\right) f ( x i ) E ( f ) E(f) E ( f ) f ( x i ) f\left(\boldsymbol{x}_i\right) f ( x i ) Δ f = 0 \Delta f=0 Δ f = 0
13.4.3 式(13.14)的推导
将式(13.13)根据矩阵运算规则进行变形,
这里第一项西瓜书中的符号有歧义，应该表示成[ f l T f u T ] \left[\begin{array}{ll}
\boldsymbol{f}_{l}^{\mathrm{T}} & \boldsymbol{f}_{u}^{\mathrm{T}}
\end{array}\right] [ f l T f u T ] R 1 × ( l + u ) \mathbb{R}^{1\times(l+u)} R 1 × ( l + u )
E ( f ) = [ f l T f u T ] [ D l l − W l l − W l u − W u l D u u − W u u ] [ f l f u ] = [ f l T ( D l l − W l l ) − f u T W u l − f l T W l u + f u T ( D u u − W u u ) ] [ f l f u ] = ( f l T ( D l l − W l l ) − f u T W u l ) f l + ( − f l T W l u + f u T ( D u u − W u u ) ) f u = f l T ( D l l − W l l ) f l − f u T W u l f l − f l T W l u f u + f u T ( D u u − W u u ) f u = f l T ( D l l − W l l ) f l − 2 f u T W u l f l + f u T ( D u u − W u u ) f u \begin{aligned}
E(f) &=\left[\begin{array}{ll}
\boldsymbol{f}_{l}^{\mathrm{T}} & \boldsymbol{f}_{u}^{\mathrm{T}}
\end{array}\right]\left[\begin{array}{cc}
\boldsymbol{D}_{l l}-\boldsymbol{W}_{l l} & -\boldsymbol{W}_{l u} \\
-\boldsymbol{W}_{u l} & \boldsymbol{D}_{u u}-\boldsymbol{W}_{u u}
\end{array}\right]\left[\begin{array}{l}
\boldsymbol{f}_{l} \\
\boldsymbol{f}_{u}
\end{array}\right] \\
&=\left[\begin{array}{ll}\boldsymbol{f}_{l}^{\mathrm{T}}\left(\boldsymbol{D}_{l l}-\boldsymbol{W}_{l l}\right)-\boldsymbol{f}_{u}^{\mathrm{T}} \boldsymbol{W}_{u l} & -\boldsymbol{f}_{l}^{\mathrm{T}} \boldsymbol{W}_{l u}+\boldsymbol{f}_{u}^{\mathrm{T}}\left(\boldsymbol{D}_{u u}-\boldsymbol{W}_{u u}\right)\end{array}\right]\left[\begin{array}{l}
\boldsymbol{f}_{l} \\
\boldsymbol{f}_{u}
\end{array}\right] \\
&=\left(\boldsymbol{f}_{l}^{\mathrm{T}}\left(\boldsymbol{D}_{l l}-\boldsymbol{W}_{l l}\right)-\boldsymbol{f}_{u}^{\mathrm{T}} \boldsymbol{W}_{u l}\right) \boldsymbol{f}_{l}+\left(-\boldsymbol{f}_{l}^{\mathrm{T}} \boldsymbol{W}_{l u}+\boldsymbol{f}_{u}^{\mathrm{T}}\left(\boldsymbol{D}_{u u}-\boldsymbol{W}_{u u}\right)\right) \boldsymbol{f}_{u} \\
&=\boldsymbol{f}_{l}^{\mathrm{T}}\left(\boldsymbol{D}_{l l}-\boldsymbol{W}_{l l}\right) \boldsymbol{f}_{l}-\boldsymbol{f}_{u}^{\mathrm{T}} \boldsymbol{W}_{u l} \boldsymbol{f}_{l}-\boldsymbol{f}_{l}^{\mathrm{T}} \boldsymbol{W}_{l u} \boldsymbol{f}_{u}+\boldsymbol{f}_{u}^{\mathrm{T}}\left(\boldsymbol{D}_{u u}-\boldsymbol{W}_{u u}\right) \boldsymbol{f}_{u} \\
&=\boldsymbol{f}_{l}^{\mathrm{T}}\left(\boldsymbol{D}_{l l}-\boldsymbol{W}_{l l}\right) \boldsymbol{f}_{l}-2 \boldsymbol{f}_{u}^{\mathrm{T}} \boldsymbol{W}_{u l} \boldsymbol{f}_{l}+\boldsymbol{f}_{u}^{\mathrm{T}}\left(\boldsymbol{D}_{u u}-\boldsymbol{W}_{u u}\right) \boldsymbol{f}_{u}
\end{aligned} E ( f ) = [ f l T f u T ] [ D l l − W l l − W u l − W l u D uu − W uu ] [ f l f u ] = [ f l T ( D l l − W l l ) − f u T W u l − f l T W l u + f u T ( D uu − W uu ) ] [ f l f u ] = ( f l T ( D l l − W l l ) − f u T W u l ) f l + ( − f l T W l u + f u T ( D uu − W uu ) ) f u = f l T ( D l l − W l l ) f l − f u T W u l f l − f l T W l u f u + f u T ( D uu − W uu ) f u = f l T ( D l l − W l l ) f l − 2 f u T W u l f l + f u T ( D uu − W uu ) f u 其中最后一步，f l T W l u f u = ( f l T W l u f u ) T = f u T W u l f l \boldsymbol{f}_{l}^{\mathrm{T}} \boldsymbol{W}_{l u} \boldsymbol{f}_{u}=\left(\boldsymbol{f}_{l}^{\mathrm{T}} \boldsymbol{W}_{l u} \boldsymbol{f}_{u}\right)^{\mathrm{T}}=f_{u}^{\mathrm{T}} \boldsymbol{W}_{u l} \boldsymbol{f}_{l} f l T W l u f u = ( f l T W l u f u ) T = f u T W u l f l
13.4.4 式(13.15)的推导
首先，基于式(13.14)对f u \boldsymbol{f}_u f u
∂ E ( f ) ∂ f u = ∂ f l T ( D l l − W l l ) f l − 2 f u T W u l f l + f u T ( D u u − W u u ) f u ∂ f u = − 2 W u l f l + 2 ( D u u − W u u ) f u \begin{aligned}
\frac{\partial E(f)}{\partial \boldsymbol{f}_{u}} &=\frac{\partial \boldsymbol{f}_{l}^{\mathrm{T}}\left(\boldsymbol{D}_{l l}-\boldsymbol{W}_{l l}\right) \boldsymbol{f}_{l}-2 \boldsymbol{f}_{u}^{\mathrm{T}} \boldsymbol{W}_{u l} \boldsymbol{f}_{l}+\boldsymbol{f}_{u}^{\mathrm{T}}\left(\boldsymbol{D}_{u u}-\boldsymbol{W}_{u u}\right) \boldsymbol{f}_{u}}{\partial \boldsymbol{f}_{u}} \\
&=-2 \boldsymbol{W}_{u l} \boldsymbol{f}_{l}+2\left(\boldsymbol{D}_{u u}-\boldsymbol{W}_{u u}\right) \boldsymbol{f}_{u}
\end{aligned} ∂ f u ∂ E ( f ) = ∂ f u ∂ f l T ( D l l − W l l ) f l − 2 f u T W u l f l + f u T ( D uu − W uu ) f u = − 2 W u l f l + 2 ( D uu − W uu ) f u 令结果等于 0 即得 13.15。
注意式中各项的含义:
f u \boldsymbol{f}_u f u f f f
D u u , W u u , W u l \boldsymbol{D}_{u u}, \boldsymbol{W}_{u u}, \boldsymbol{W}_{u l} D uu , W uu , W u l
f l \boldsymbol{f}_l f l f f f
也就是说可以根据式(13.15)根据 D l D_l D l f l \boldsymbol{f}_l f l f u \boldsymbol{f}_u f u
仔细回顾该方法, 实际就是根据 "相似的样本应具有相似的标记" 的原则,
构建了目标 函数式(13.12),
求解式(13.12)得到了使用标记样本信息表示的末标记样本的预测标记。
13.4.5 式(13.16)的解释
根据矩阵乘法的定义计算可得该式，其中需要注意的是，对角矩阵D \mathbf{D} D
13.4.6 式(13.17)的推导
第一项到第二项是根据矩阵乘法逆的定义：( A B ) − 1 = B − 1 A − 1 (\mathbf{A}\mathbf{B})^{-1}=\mathbf{B}^{-1}\mathbf{A}^{-1} ( AB ) − 1 = B − 1 A − 1
P u u = D u u − 1 W u u P u l = D u u − 1 W u l \begin{aligned}
\mathbf{P}_{u u}&=\mathbf{D}_{u u}^{-1} \mathbf{W}_{u u}\\
\mathbf{P}_{ul}&=\mathbf{D}_{u u}^{-1} \mathbf{W}_{u l}
\end{aligned} P uu P u l = D uu − 1 W uu = D uu − 1 W u l 均可以根据W i j \mathbf{W}_{ij} W ij f l \mathbf{f}_l f l f u \mathbf{f}_u f u
13.4.7 式(13.18)的解释
其中Y的第 i i i i i i l l l i i i j ( 1 ≤ j ≤ ∣ Y ∣ ) j(1 \leq j \leq|\mathcal{Y}|) j ( 1 ≤ j ≤ ∣ Y ∣ ) Y \mathbf{Y} Y j j j u u u Y Y Y ∣ Y ∣ |\mathcal{Y}| ∣ Y ∣ Y \mathcal{Y} Y
13.4.8 式(13.20)的解释
F ∗ = lim t → ∞ F ( t ) = ( 1 − α ) ( I − α S ) − 1 Y \mathbf{F}^{*}=\lim _{t \rightarrow \infty} \mathbf{F}(t)=(1-\alpha)(\mathbf{I}-\alpha \mathbf{S})^{-1} \mathbf{Y} F ∗ = t → ∞ lim F ( t ) = ( 1 − α ) ( I − α S ) − 1 Y [解析]：由式(13.19)
F ( t + 1 ) = α S F ( t ) + ( 1 − α ) Y \mathbf{F}(t+1)=\alpha \mathbf{S} \mathbf{F}(t)+(1-\alpha) \mathbf{Y} F ( t + 1 ) = α SF ( t ) + ( 1 − α ) Y 当 t取不同的值时，有：
t = 0 : F ( 1 ) = α S F ( 0 ) + ( 1 − α ) Y = α S Y + ( 1 − α ) Y t = 1 : F ( 2 ) = α S F ( 1 ) + ( 1 − α ) Y = α S ( α S Y + ( 1 − α ) Y ) + ( 1 − α ) Y = ( α S ) 2 Y + ( 1 − α ) ( ∑ i = 0 1 ( α S ) i ) Y t = 2 : F ( 3 ) = α S F ( 2 ) + ( 1 − α ) Y = α S ( ( α S ) 2 Y + ( 1 − α ) ( ∑ i = 0 1 ( α S ) i ) Y ) + ( 1 − α ) Y = ( α S ) 3 Y + ( 1 − α ) ( ∑ i = 0 2 ( α S ) i ) Y \begin{aligned}
t=0: \mathbf{F}(1) &=\alpha \mathbf{S F}(0)+(1-\alpha) \mathbf{Y}\\
&=\alpha \mathbf{S} \mathbf{Y}+(1-\alpha) \mathbf{Y} \\
t=1: \mathbf{F}(2) &=\alpha \mathbf{S F}(1)+(1-\alpha) \mathbf{Y}=\alpha \mathbf{S}(\alpha \mathbf{S} \mathbf{Y}+(1-\alpha) \mathbf{Y})+(1-\alpha) \mathbf{Y} \\
&=(\alpha \mathbf{S})^{2} \mathbf{Y}+(1-\alpha)\left(\sum_{i=0}^{1}(\alpha \mathbf{S})^{i}\right) \mathbf{Y} \\
t=2:\mathbf{F}(3)&=\alpha\mathbf{S}\mathbf{F}(2)+(1-\alpha)\mathbf{Y}\\&=\alpha \mathbf{S}\left((\alpha \mathbf{S})^{2} \mathbf{Y}+(1-\alpha)\left(\sum_{i=0}^{1}(\alpha \mathbf{S})^{i}\right) \mathbf{Y}\right)+(1-\alpha) \mathbf{Y} \\
&=(\alpha \mathbf{S})^{3} \mathbf{Y}+(1-\alpha)\left(\sum_{i=0}^{2}(\alpha \mathbf{S})^{i}\right) \mathbf{Y}\\
\end{aligned} t = 0 : F ( 1 ) t = 1 : F ( 2 ) t = 2 : F ( 3 ) = α SF ( 0 ) + ( 1 − α ) Y = α SY + ( 1 − α ) Y = α SF ( 1 ) + ( 1 − α ) Y = α S ( α SY + ( 1 − α ) Y ) + ( 1 − α ) Y = ( α S ) 2 Y + ( 1 − α ) ( i = 0 ∑ 1 ( α S ) i ) Y = α SF ( 2 ) + ( 1 − α ) Y = α S ( ( α S ) 2 Y + ( 1 − α ) ( i = 0 ∑ 1 ( α S ) i ) Y ) + ( 1 − α ) Y = ( α S ) 3 Y + ( 1 − α ) ( i = 0 ∑ 2 ( α S ) i ) Y 可以观察到规律
F ( t ) = ( α S ) t Y + ( 1 − α ) ( ∑ i = 0 t − 1 ( α S ) i ) Y \mathbf{F}(t)=(\alpha \mathbf{S})^{t} \mathbf{Y}+(1-\alpha)\left(\sum_{i=0}^{t-1}(\alpha \mathbf{S})^{i}\right) \mathbf{Y} F ( t ) = ( α S ) t Y + ( 1 − α ) ( i = 0 ∑ t − 1 ( α S ) i ) Y 则
F ∗ = lim t → ∞ F ( t ) = lim t → ∞ ( α S ) t Y + lim t → ∞ ( 1 − α ) ( ∑ i = 0 t − 1 ( α S ) i ) Y \mathbf{F}^{*}=\lim _{t \rightarrow \infty}\mathbf{F}(t)=\lim _{t \rightarrow \infty}(\alpha \mathbf{S})^{t} \mathbf{Y}+\lim _{t \rightarrow \infty}(1-\alpha)\left(\sum_{i=0}^{t-1}(\alpha \mathbf{S})^{i}\right) \mathbf{Y} F ∗ = t → ∞ lim F ( t ) = t → ∞ lim ( α S ) t Y + t → ∞ lim ( 1 − α ) ( i = 0 ∑ t − 1 ( α S ) i ) Y 其中第一项由于S = D − 1 2 W D − 1 2 \mathbf{S}=\mathbf{D}^{-\frac{1}{2}} \mathbf{W} \mathbf{D}^{-\frac{1}{2}} S = D − 2 1 W D − 2 1 α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) lim t → ∞ ( α S ) t = 0 \lim _{t \rightarrow \infty}(\alpha \mathbf{S})^{t}=0 lim t → ∞ ( α S ) t = 0
lim t → ∞ ∑ i = 0 t − 1 ( α S ) i = I − lim t → ∞ ( α S ) t I − α S = I I − α S = ( I − α S ) − 1 \lim _{t \rightarrow \infty} \sum_{i=0}^{t-1}(\alpha \mathbf{S})^{i}=\frac{\mathbf{I}-\lim _{t \rightarrow \infty}(\alpha \mathbf{S})^{t}}{\mathbf{I}-\alpha \mathbf{S}}=\frac{\mathbf{I}}{\mathbf{I}-\alpha \mathbf{S}}=(\mathbf{I}-\alpha \mathbf{S})^{-1} t → ∞ lim i = 0 ∑ t − 1 ( α S ) i = I − α S I − lim t → ∞ ( α S ) t = I − α S I = ( I − α S ) − 1 综合可得式(13.20)。
13.4.9 式(13.21)的推导
这里主要是推导式(13.21)的最优解即为式(13.20)。将式(13.21)的目标函数进行变形。
第 1 部分:
先将范数平方拆开为四项
∥ 1 d i F i − 1 d j F j ∥ 2 = ( 1 d i F i − 1 d j F j ) ( 1 d i F i − 1 d j F j ) ⊤ = 1 d i F i F i ⊤ + 1 d j F j F j ⊤ − 1 d i d j F i F j ⊤ − 1 d j d i F j F i ⊤ \begin{aligned}
\left\|\frac{1}{\sqrt{d_i}} \mathbf{F}_i-\frac{1}{\sqrt{d_j}} \mathbf{F}_j\right\|^2 & =\left(\frac{1}{\sqrt{d_i}} \mathbf{F}_i-\frac{1}{\sqrt{d_j}} \mathbf{F}_j\right)\left(\frac{1}{\sqrt{d_i}} \mathbf{F}_i-\frac{1}{\sqrt{d_j}} \mathbf{F}_j\right)^{\top} \\
& =\frac{1}{d_i} \mathbf{F}_i \mathbf{F}_i^{\top}+\frac{1}{d_j} \mathbf{F}_j \mathbf{F}_j^{\top}-\frac{1}{\sqrt{d_i d_j}} \mathbf{F}_i \mathbf{F}_j^{\top}-\frac{1}{\sqrt{d_j d_i}} \mathbf{F}_j \mathbf{F}_i^{\top}
\end{aligned} d i 1 F i − d j 1 F j 2 = ( d i 1 F i − d j 1 F j ) ( d i 1 F i − d j 1 F j ) ⊤ = d i 1 F i F i ⊤ + d j 1 F j F j ⊤ − d i d j 1 F i F j ⊤ − d j d i 1 F j F i ⊤ 其中 F i ∈ R 1 × ∣ Y ∣ \mathbf{F}_i \in \mathbb{R}^{1 \times|\mathcal{Y}|} F i ∈ R 1 × ∣ Y ∣ F \mathbf{F} F i i i i i i x i \boldsymbol{x}_i x i ∑ i , j = 1 m \sum_{i, j=1}^m ∑ i , j = 1 m ∑ i = 1 m ∑ i = 1 m \sum_{i=1}^m \sum_{i=1}^m ∑ i = 1 m ∑ i = 1 m
∑ i , j = 1 m ( W ) i j 1 d i F i F i ⊤ = ∑ i = 1 m 1 d i F i F i ⊤ ∑ j = 1 m ( W ) i j = ∑ i = 1 m 1 d i F i F i ⊤ ⋅ d i = ∑ i = 1 m F i F i ⊤ ∑ i , j = 1 m ( W ) i j 1 d j F j F j ⊤ = ∑ j = 1 m 1 d j F j F j ⊤ ∑ i = 1 m ( W ) i j = ∑ j = 1 m 1 d j F j F j ⊤ ⋅ d j = ∑ j = 1 m F j F j ⊤ \begin{aligned}
& \sum_{i, j=1}^m(\mathbf{W})_{i j} \frac{1}{d_i} \mathbf{F}_i \mathbf{F}_i^{\top}=\sum_{i=1}^m \frac{1}{d_i} \mathbf{F}_i \mathbf{F}_i^{\top} \sum_{j=1}^m(\mathbf{W})_{i j}=\sum_{i=1}^m \frac{1}{d_i} \mathbf{F}_i \mathbf{F}_i^{\top} \cdot d_i=\sum_{i=1}^m \mathbf{F}_i \mathbf{F}_i^{\top} \\
& \sum_{i, j=1}^m(\mathbf{W})_{i j} \frac{1}{d_j} \mathbf{F}_j \mathbf{F}_j^{\top}=\sum_{j=1}^m \frac{1}{d_j} \mathbf{F}_j \mathbf{F}_j^{\top} \sum_{i=1}^m(\mathbf{W})_{i j}=\sum_{j=1}^m \frac{1}{d_j} \mathbf{F}_j \mathbf{F}_j^{\top} \cdot d_j=\sum_{j=1}^m \mathbf{F}_j \mathbf{F}_j^{\top} \\
&
\end{aligned} i , j = 1 ∑ m ( W ) ij d i 1 F i F i ⊤ = i = 1 ∑ m d i 1 F i F i ⊤ j = 1 ∑ m ( W ) ij = i = 1 ∑ m d i 1 F i F i ⊤ ⋅ d i = i = 1 ∑ m F i F i ⊤ i , j = 1 ∑ m ( W ) ij d j 1 F j F j ⊤ = j = 1 ∑ m d j 1 F j F j ⊤ i = 1 ∑ m ( W ) ij = j = 1 ∑ m d j 1 F j F j ⊤ ⋅ d j = j = 1 ∑ m F j F j ⊤ 以上化简过程中, 两个求和号可以交换求和次序; 又因为 W \mathrm{W} W d i = ∑ j = 1 m ( W ) i j = ∑ j = 1 m ( W ) j i d_i=\sum_{j=1}^m(\mathbf{W})_{i j}=\sum_{j=1}^m(\mathbf{W})_{j i} d i = ∑ j = 1 m ( W ) ij = ∑ j = 1 m ( W ) j i
∑ i = 1 m F i F i ⊤ = ∑ j = 1 m F j F j ⊤ = ∑ i = 1 m ∥ F i ∥ 2 = ∥ F ∥ F 2 = tr ( F F ⊤ ) \sum_{i=1}^m \mathbf{F}_i \mathbf{F}_i^{\top}=\sum_{j=1}^m \mathbf{F}_j \mathbf{F}_j^{\top}=\sum_{i=1}^m\left\|\mathbf{F}_i\right\|^2=\|\mathbf{F}\|_{\mathrm{F}}^2=\operatorname{tr}\left(\mathbf{F} \mathbf{F}^{\top}\right) i = 1 ∑ m F i F i ⊤ = j = 1 ∑ m F j F j ⊤ = i = 1 ∑ m ∥ F i ∥ 2 = ∥ F ∥ F 2 = tr ( F F ⊤ ) 以上推导过程中, 第 1 个等号显然成立, 因为二者仅是求和变量名称不同; 第 2
个等号即将 F i F i ⊤ \mathbf{F}_i \mathbf{F}_i^{\top} F i F i ⊤ ∥ F i ∥ 2 \left\|\mathbf{F}_i\right\|^2 ∥ F i ∥ 2 F \mathbf{F} F F F F F \mathrm{F} F F \mathrm{F} F F F F
∑ i , j = 1 m ( W ) i j 1 d i d j F i F j ⊤ = ∑ i , j = 1 m ( S ) i j F i F j ⊤ = tr ( S ⊤ F F ⊤ ) = tr ( S F F ⊤ ) \sum_{i, j=1}^m(\mathbf{W})_{i j} \frac{1}{\sqrt{d_i d_j}} \mathbf{F}_i \mathbf{F}_j^{\top}=\sum_{i, j=1}^m(\mathbf{S})_{i j} \mathbf{F}_i \mathbf{F}_j^{\top}=\operatorname{tr}\left(\mathbf{S}^{\top} \mathbf{F} \mathbf{F}^{\top}\right)=\operatorname{tr}\left(\mathbf{S F} \mathbf{F}^{\top}\right) i , j = 1 ∑ m ( W ) ij d i d j 1 F i F j ⊤ = i , j = 1 ∑ m ( S ) ij F i F j ⊤ = tr ( S ⊤ F F ⊤ ) = tr ( SF F ⊤ ) 具体来说, 以上化简过程为:
S = [ ( S ) 11 ( S ) 12 ⋯ ( S ) 1 m ( S ) 21 ( S ) 22 ⋯ ( S ) 2 m ⋮ ⋮ ⋱ ⋮ ( S ) m 1 ( S ) m 2 ⋯ ( S ) m m ] = D − 1 2 W D − 1 2 = [ 1 d 1 1 d 2 ⋱ 1 d m ] [ ( W ) 11 ( W ) 12 ⋯ ( W ) 1 m ( W ) 21 ( W ) 22 ⋯ ( W ) 2 m ⋮ ⋮ ⋱ ⋮ ( W ) m 1 ( W ) m 2 ⋯ ( W ) m m ] [ 1 d 1 1 d 2 ⋱ 1 d m ] \begin{aligned}
& \mathbf{S}=\left[\begin{array}{cccc}
(\mathbf{S})_{11} & (\mathbf{S})_{12} & \cdots & (\mathbf{S})_{1 m} \\
(\mathbf{S})_{21} & (\mathbf{S})_{22} & \cdots & (\mathbf{S})_{2 m} \\
\vdots & \vdots & \ddots & \vdots \\
(\mathbf{S})_{m 1} & (\mathbf{S})_{m 2} & \cdots & (\mathbf{S})_{m m}
\end{array}\right] \\
& =\mathrm{D}^{-\frac{1}{2}} \mathbf{W D}^{-\frac{1}{2}} \\
& =\left[\begin{array}{ccccc}
\frac{1}{\sqrt{d_1}} & & & \\
& \frac{1}{\sqrt{d_2}} & & \\
& & \ddots & \\
& & & \frac{1}{\sqrt{d_m}}
\end{array}\right]\left[\begin{array}{cccc}
(\mathbf{W})_{11} & (\mathbf{W})_{12} & \cdots & (\mathbf{W})_{1 m} \\
(\mathbf{W})_{21} & (\mathbf{W})_{22} & \cdots & (\mathbf{W})_{2 m} \\
\vdots & \vdots & \ddots & \vdots \\
(\mathbf{W})_{m 1} & (\mathbf{W})_{m 2} & \cdots & (\mathbf{W})_{m m}
\end{array}\right]\left[\begin{array}{cccc}
\frac{1}{\sqrt{d_1}} & & & \\
& \frac{1}{\sqrt{d_2}} & & \\
& & \ddots & \\
& & & \frac{1}{\sqrt{d_m}}
\end{array}\right] \\
&
\end{aligned} S = ( S ) 11 ( S ) 21 ⋮ ( S ) m 1 ( S ) 12 ( S ) 22 ⋮ ( S ) m 2 ⋯ ⋯ ⋱ ⋯ ( S ) 1 m ( S ) 2 m ⋮ ( S ) mm = D − 2 1 WD − 2 1 = d 1 1 d 2 1 ⋱ d m 1 ( W ) 11 ( W ) 21 ⋮ ( W ) m 1 ( W ) 12 ( W ) 22 ⋮ ( W ) m 2 ⋯ ⋯ ⋱ ⋯ ( W ) 1 m ( W ) 2 m ⋮ ( W ) mm d 1 1 d 2 1 ⋱ d m 1 由以上推导可以看出
( S ) i j = 1 d i d j ( W ) i j (\mathbf{S})_{i j}=\frac{1}{\sqrt{d_i d_j}}(\mathbf{W})_{i j} ( S ) ij = d i d j 1 ( W ) ij
F F ⊤ = [ F 1 F 2 ⋮ F m ] [ F 1 ⊤ F 2 ⊤ ⋯ F m ⊤ ] = [ F 1 F 1 ⊤ F 1 F 2 ⊤ … F 1 F m ⊤ F 2 F 1 ⊤ F 2 F 2 ⊤ ⋯ F 2 F m ⊤ ⋮ ⋮ ⋱ ⋮ F m F 1 ⊤ F m F 2 ⊤ ⋯ F m F m ⊤ ] \mathbf{F F}^{\top}=\left[\begin{array}{c}
\mathbf{F}_1 \\
\mathbf{F}_2 \\
\vdots \\
\mathbf{F}_m
\end{array}\right]\left[\begin{array}{llll}
\mathbf{F}_1^{\top} & \mathbf{F}_2^{\top} & \cdots & \mathbf{F}_m^{\top}
\end{array}\right]=\left[\begin{array}{cccc}
\mathbf{F}_1 \mathbf{F}_1^{\top} & \mathbf{F}_1 \mathbf{F}_2^{\top} & \ldots & \mathbf{F}_1 \mathbf{F}_m^{\top} \\
\mathbf{F}_2 \mathbf{F}_1^{\top} & \mathbf{F}_2 \mathbf{F}_2^{\top} & \cdots & \mathbf{F}_2 \mathbf{F}_m^{\top} \\
\vdots & \vdots & \ddots & \vdots \\
\mathbf{F}_m \mathbf{F}_1^{\top} & \mathbf{F}_m \mathbf{F}_2^{\top} & \cdots & \mathbf{F}_m \mathbf{F}_m^{\top}
\end{array}\right] FF ⊤ = F 1 F 2 ⋮ F m [ F 1 ⊤ F 2 ⊤ ⋯ F m ⊤ ] = F 1 F 1 ⊤ F 2 F 1 ⊤ ⋮ F m F 1 ⊤ F 1 F 2 ⊤ F 2 F 2 ⊤ ⋮ F m F 2 ⊤ … ⋯ ⋱ ⋯ F 1 F m ⊤ F 2 F m ⊤ ⋮ F m F m ⊤ 若令 A = S ∘ F F ⊤ \mathbf{A}=\mathbf{S} \circ \mathbf{F F}^{\top} A = S ∘ FF ⊤ S \mathbf{S} S F F ⊤ \mathbf{F} \mathbf{F}^{\top} F F ⊤
∑ i , j = 1 m ( S ) i j F i F j ⊤ = ∑ i , j = 1 m ( A ) i j \sum_{i, j=1}^m(\mathbf{S})_{i j} \mathbf{F}_i \mathbf{F}_j^{\top}=\sum_{i, j=1}^m(\mathbf{A})_{i j} i , j = 1 ∑ m ( S ) ij F i F j ⊤ = i , j = 1 ∑ m ( A ) ij 可以验证, 上式的矩阵
A = S ∘ F F ⊤ \mathbf{A}=\mathbf{S} \circ \mathbf{F} \mathbf{F}^{\top} A = S ∘ F F ⊤ ∑ i , j = 1 m ( A ) i j \sum_{i, j=1}^m(\mathbf{A})_{i j} ∑ i , j = 1 m ( A ) ij tr ( S ⊤ F F ⊤ ) \operatorname{tr}\left(\mathbf{S}^{\top} \mathbf{F F}^{\top}\right) tr ( S ⊤ FF ⊤ )
tr ( [ ( S ) 11 ( S ) 12 ⋯ ( S ) 1 m ( S ) 21 ( S ) 22 ⋯ ( S ) 2 m ⋮ ⋮ ⋱ ⋮ ( S ) m 1 ( S ) m 2 ⋯ ( S ) m m ] ⊤ ⋅ [ F 1 F 1 ⊤ F 1 F 2 ⊤ ⋯ F 1 F m ⊤ F 2 F 1 ⊤ F 2 F 2 ⊤ ⋯ F 2 F m ⊤ ⋮ ⋮ ⋱ ⋮ F m F 1 ⊤ F m F 2 ⊤ ⋯ F m F m ⊤ ] ) = [ ( S ) 11 ( S ) 21 ⋮ ( S ) m 1 ] ⊤ ⋅ [ F 1 F 1 ⊤ F 2 F 1 ⊤ ⋮ F m F 1 ⊤ ] + [ ( S ) 12 ( S ) 22 ⋮ ( S ) m 2 ] ⊤ ⋅ [ F 1 F 2 ⊤ F 2 F 2 ⊤ ⋮ F m F 2 ⊤ ] + … + [ ( S ) 1 m ( S ) 2 m ⋮ ( S ) m m ] ⊤ [ F 1 F m ⊤ F 2 F m ⊤ ⋮ F m F m ⊤ ] = ∑ i = 1 m ( S ) i 1 F i F 1 ⊤ + ∑ i = 1 m ( S ) i 2 F i F 2 ⊤ + … + ∑ i = 1 ( S ) i m F i F m ⊤ = ∑ i , j = 1 m ( S ) i j F i F j ⊤ \begin{aligned}
& \operatorname{tr}\left(\left[\begin{array}{cccc}
(\mathbf{S})_{11} & (\mathbf{S})_{12} & \cdots & (\mathbf{S})_{1 m} \\
(\mathbf{S})_{21} & (\mathbf{S})_{22} & \cdots & (\mathbf{S})_{2 m} \\
\vdots & \vdots & \ddots & \vdots \\
(\mathbf{S})_{m 1} & (\mathbf{S})_{m 2} & \cdots & (\mathbf{S})_{m m}
\end{array}\right]^{\top} \cdot\left[\begin{array}{cccc}
\mathbf{F}_1 \mathbf{F}_1^{\top} & \mathbf{F}_1 \mathbf{F}_2^{\top} & \cdots & \mathbf{F}_1 \mathbf{F}_m^{\top} \\
\mathbf{F}_2 \mathbf{F}_1^{\top} & \mathbf{F}_2 \mathbf{F}_2^{\top} & \cdots & \mathbf{F}_2 \mathbf{F}_m^{\top} \\
\vdots & \vdots & \ddots & \vdots \\
\mathbf{F}_m \mathbf{F}_1^{\top} & \mathbf{F}_m \mathbf{F}_2^{\top} & \cdots & \mathbf{F}_m \mathbf{F}_m^{\top}
\end{array}\right]\right) \\
&=\left[\begin{array}{c}
(\mathbf{S})_{11} \\
(\mathbf{S})_{21} \\
\vdots \\
(\mathbf{S})_{m 1}
\end{array}\right]^{\top} \cdot\left[\begin{array}{c}
\mathbf{F}_1 \mathbf{F}_1^{\top} \\
\mathbf{F}_2 \mathbf{F}_1^{\top} \\
\vdots \\
\mathbf{F}_m \mathbf{F}_1^{\top}
\end{array}\right]+\left[\begin{array}{c}
(\mathbf{S})_{12} \\
(\mathbf{S})_{22} \\
\vdots \\
(\mathbf{S})_{m 2}
\end{array}\right]^{\top} \cdot\left[\begin{array}{c}
\mathbf{F}_1 \mathbf{F}_2^{\top} \\
\mathbf{F}_2 \mathbf{F}_2^{\top} \\
\vdots \\
\mathbf{F}_m \mathbf{F}_2^{\top}
\end{array}\right]+\ldots+\left[\begin{array}{c}
(\mathbf{S})_{1 m} \\
(\mathbf{S})_{2 m} \\
\vdots \\
(\mathbf{S})_{m m}
\end{array}\right]^{\top}\left[\begin{array}{c}
\mathbf{F}_1 \mathbf{F}_m^{\top} \\
\mathbf{F}_2 \mathbf{F}_m^{\top} \\
\vdots \\
\mathbf{F}_m \mathbf{F}_m^{\top}
\end{array}\right] \\
&=\sum_{i=1}^m(\mathbf{S})_{i 1} \mathbf{F}_i \mathbf{F}_1^{\top}+\sum_{i=1}^m(\mathbf{S})_{i 2} \mathbf{F}_i \mathbf{F}_2^{\top}+\ldots+\sum_{i=1}(\mathbf{S})_{i m} \mathbf{F}_i \mathbf{F}_m^{\top} \\
&= \sum_{i, j=1}^m(\mathbf{S})_{i j} \mathbf{F}_i \mathbf{F}_j^{\top}
\end{aligned} tr ( S ) 11 ( S ) 21 ⋮ ( S ) m 1 ( S ) 12 ( S ) 22 ⋮ ( S ) m 2 ⋯ ⋯ ⋱ ⋯ ( S ) 1 m ( S ) 2 m ⋮ ( S ) mm ⊤ ⋅ F 1 F 1 ⊤ F 2 F 1 ⊤ ⋮ F m F 1 ⊤ F 1 F 2 ⊤ F 2 F 2 ⊤ ⋮ F m F 2 ⊤ ⋯ ⋯ ⋱ ⋯ F 1 F m ⊤ F 2 F m ⊤ ⋮ F m F m ⊤ = ( S ) 11 ( S ) 21 ⋮ ( S ) m 1 ⊤ ⋅ F 1 F 1 ⊤ F 2 F 1 ⊤ ⋮ F m F 1 ⊤ + ( S ) 12 ( S ) 22 ⋮ ( S ) m 2 ⊤ ⋅ F 1 F 2 ⊤ F 2 F 2 ⊤ ⋮ F m F 2 ⊤ + … + ( S ) 1 m ( S ) 2 m ⋮ ( S ) mm ⊤ F 1 F m ⊤ F 2 F m ⊤ ⋮ F m F m ⊤ = i = 1 ∑ m ( S ) i 1 F i F 1 ⊤ + i = 1 ∑ m ( S ) i 2 F i F 2 ⊤ + … + i = 1 ∑ ( S ) im F i F m ⊤ = i , j = 1 ∑ m ( S ) ij F i F j ⊤ 即第 2 个等号; 易知矩阵 S \mathbf{S} S ( S ⊤ = S ) \left(\mathbf{S}^{\top}=\mathbf{S}\right) ( S ⊤ = S ) F i F j ⊤ \mathbf{F}_i \mathbf{F}_j^{\top} F i F j ⊤ 1 × 1 1 \times 1 1 × 1
F i F j ⊤ = ( F i F j ⊤ ) ⊤ = ( F j ⊤ ) ⊤ ( F i ) ⊤ = F j F i ⊤ \mathbf{F}_i \mathbf{F}_j^{\top}=\left(\mathbf{F}_i \mathbf{F}_j^{\top}\right)^{\top}=\left(\mathbf{F}_j^{\top}\right)^{\top}\left(\mathbf{F}_i\right)^{\top}=\mathbf{F}_j \mathbf{F}_i^{\top} F i F j ⊤ = ( F i F j ⊤ ) ⊤ = ( F j ⊤ ) ⊤ ( F i ) ⊤ = F j F i ⊤ 因此
1 d i d j F i F j ⊤ = 1 d j d i F j F i ⊤ \frac{1}{\sqrt{d_i d_j}} \mathbf{F}_i \mathbf{F}_j^{\top}=\frac{1}{\sqrt{d_j d_i}} \mathbf{F}_j \mathbf{F}_i^{\top} d i d j 1 F i F j ⊤ = d j d i 1 F j F i ⊤ 进而上面拆分的四项中的第三项和第四项相等:
∑ i , j = 1 m ( W ) i j 1 d i d j F i F j ⊤ = ∑ i , j = 1 m ( W ) i j 1 d j d i F j F i ⊤ \sum_{i, j=1}^m(\mathbf{W})_{i j} \frac{1}{\sqrt{d_i d_j}} \mathbf{F}_i \mathbf{F}_j^{\top}=\sum_{i, j=1}^m(\mathbf{W})_{i j} \frac{1}{\sqrt{d_j d_i}} \mathbf{F}_j \mathbf{F}_i^{\top} i , j = 1 ∑ m ( W ) ij d i d j 1 F i F j ⊤ = i , j = 1 ∑ m ( W ) ij d j d i 1 F j F i ⊤ 综上所述 (以上拆分的四项中前两项相等、后两项相等, 正好抵消系数
1 2 \frac{1}{2} 2 1
1 2 ( ∑ i , j = 1 m ( W ) i j ∥ 1 d i F i − 1 d j F j ∥ 2 ) = tr ( F F ⊤ ) − tr ( S F F ⊤ ) \frac{1}{2}\left(\sum_{i, j=1}^m(\mathbf{W})_{i j}\left\|\frac{1}{\sqrt{d_i}} \mathbf{F}_i-\frac{1}{\sqrt{d_j}} \mathbf{F}_j\right\|^2\right)=\operatorname{tr}\left(\mathbf{F F}^{\top}\right)-\operatorname{tr}\left(\mathbf{S F F}^{\top}\right) 2 1 i , j = 1 ∑ m ( W ) ij d i 1 F i − d j 1 F j 2 = tr ( FF ⊤ ) − tr ( SFF ⊤ ) 第 2 部分:
西瓜书中式(13.21)的第 2 部分与原文献[@zhou2003learning]中式(4)的第 2
部分不同:
Q ( F ) = 1 2 ∑ i , j = 1 n W i j ∥ F i D i i − F j D j j ∥ 2 + μ ∑ i = 1 n ∥ F i − Y i ∥ 2 , \mathcal{Q}(F)=\frac{1}{2} \sum_{i, j=1}^n W_{i j}\left\|\frac{F_i}{\sqrt{D_{i i}}}-\frac{F_j}{\sqrt{D_{j j}}}\right\|^2+\mu \sum_{i=1}^n\left\|F_i-Y_i\right\|^2, Q ( F ) = 2 1 i , j = 1 ∑ n W ij D ii F i − D j j F j 2 + μ i = 1 ∑ n ∥ F i − Y i ∥ 2 , 原文献中第 2 部分包含了所有样本 (求和变量上限为 n n n Y i = 0 \mathbf{Y}_i=\mathbf{0} Y i = 0 过拟合 ,
可在式(13.21)中引入针对末标记样本的 L 2 \mathrm{L}_2 L 2 μ ∑ i = l + 1 l + u ∥ F i ∥ 2 \mu \sum_{i=l+1}^{l+u}\left\|\mathbf{F}_i\right\|^2 μ ∑ i = l + 1 l + u ∥ F i ∥ 2 F \mathrm{F} F
∑ i = 1 m ∥ F i − Y i ∥ 2 = ∥ F − Y ∥ F 2 \sum_{i=1}^m\left\|\mathbf{F}_i-\mathbf{Y}_i\right\|^2=\|\mathbf{F}-\mathbf{Y}\|_{\mathrm{F}}^2 i = 1 ∑ m ∥ F i − Y i ∥ 2 = ∥ F − Y ∥ F 2 综上, 式(13.21)目标函数
Q ( F ) = tr ( F F ⊤ ) − tr ( S F F ⊤ ) + μ ∥ F − Y ∥ F 2 \mathcal{Q}(\mathbf{F})=\operatorname{tr}\left(\mathbf{F} \mathbf{F}^{\top}\right)-\operatorname{tr}\left(\mathbf{S F F ^ { \top }}\right)+\mu\|\mathbf{F}-\mathbf{Y}\|_{\mathrm{F}}^2 Q ( F ) = tr ( F F ⊤ ) − tr ( SF F ⊤ ) + μ ∥ F − Y ∥ F 2
∂ Q ( F ) ∂ F = ∂ tr ( F F ⊤ ) ∂ F − ∂ tr ( S F F ⊤ ) ∂ F + μ ∂ ∥ F − Y ∥ F 2 ∂ F = 2 F − 2 S F + 2 μ ( F − Y ) \begin{aligned}
\frac{\partial \mathcal{Q}(\mathbf{F})}{\partial \mathbf{F}} & =\frac{\partial \operatorname{tr}\left(\mathbf{F} \mathbf{F}^{\top}\right)}{\partial \mathbf{F}}-\frac{\partial \operatorname{tr}\left(\mathbf{S} \mathbf{F} \mathbf{F}^{\top}\right)}{\partial \mathbf{F}}+\mu \frac{\partial\|\mathbf{F}-\mathbf{Y}\|_{\mathrm{F}}^2}{\partial \mathbf{F}} \\
& =2 \mathbf{F}-2 \mathbf{S} \mathbf{F}+2 \mu(\mathbf{F}-\mathbf{Y})
\end{aligned} ∂ F ∂ Q ( F ) = ∂ F ∂ tr ( F F ⊤ ) − ∂ F ∂ tr ( SF F ⊤ ) + μ ∂ F ∂ ∥ F − Y ∥ F 2 = 2 F − 2 SF + 2 μ ( F − Y ) 令 μ = 1 − α α \mu=\frac{1-\alpha}{\alpha} μ = α 1 − α ∂ Q ( F ) ∂ F = 2 F − 2 S F + 2 1 − α α ( F − Y ) = 0 \frac{\partial \mathcal{Q}(\mathbf{F})}{\partial \mathbf{F}}=2 \mathbf{F}-2 \mathbf{S F}+2 \frac{1-\alpha}{\alpha}(\mathbf{F}-\mathbf{Y})=0 ∂ F ∂ Q ( F ) = 2 F − 2 SF + 2 α 1 − α ( F − Y ) = 0
13.5 基于分歧的方法
"西瓜书"的伟大之处在于巧妙地融入了很多机器学习的研究分支,
而非仅简单介绍经典的 机器学习算法。比如本节处于半监督学习章节范围内,
巧妙地将机器学习的研究热点之一多视图学习[@xu2013survey](multi-view
learning) 融入进来, 类似地还有本章 第一节将主动学习融入进来, 在第 10
章第一节将 k k k
协同训练是多视图学习代表性算法之一, 本章叙述简单易懂。
13.5.1 图13.6的解释
第 2 行表示从样本集 D u D_u D u D s D_s D s
第 4 行, 当 j = 1 j=1 j = 1 ⟨ x i j , x i 3 − j ⟩ \left\langle\boldsymbol{x}_i^j, \boldsymbol{x}_i^{3-j}\right\rangle ⟨ x i j , x i 3 − j ⟩ ⟨ x i 1 , x i 2 ⟩ \left\langle\boldsymbol{x}_i^1, \boldsymbol{x}_i^2\right\rangle ⟨ x i 1 , x i 2 ⟩ j = 2 j=2 j = 2 ⟨ x i j , x i 3 − j ⟩ \left\langle\boldsymbol{x}_i^j, \boldsymbol{x}_i^{3-j}\right\rangle ⟨ x i j , x i 3 − j ⟩ ⟨ x i 2 , x i 1 ⟩ \left\langle\boldsymbol{x}_i^2, \boldsymbol{x}_i^1\right\rangle ⟨ x i 2 , x i 1 ⟩ 3 − j 3-j 3 − j ⟨ x i 1 , x i 2 ⟩ \left\langle\boldsymbol{x}_i^1, \boldsymbol{x}_i^2\right\rangle ⟨ x i 1 , x i 2 ⟩ ⟨ x i 2 , x i 1 ⟩ \left\langle\boldsymbol{x}_i^2, \boldsymbol{x}_i^1\right\rangle ⟨ x i 2 , x i 1 ⟩ D l 1 = { ( x 1 1 , y 1 ) , … , ( x l 1 , y l ) } D_l^1=\left\{\left(\boldsymbol{x}_1^1, y_1\right), \ldots,\left(\boldsymbol{x}_l^1, y_l\right)\right\} D l 1 = { ( x 1 1 , y 1 ) , … , ( x l 1 , y l ) } D l 2 = { ( x 1 2 , y 1 ) , … , ( x l 2 , y l ) } D_l^2=\left\{\left(\boldsymbol{x}_1^2, y_1\right), \ldots,\left(\boldsymbol{x}_l^2, y_l\right)\right\} D l 2 = { ( x 1 2 , y 1 ) , … , ( x l 2 , y l ) }
第 9 行 第 11 行是根据第 j j j 3 − j 3-j 3 − j
13.6 半监督聚类
13.6.1 图13.7的解释
注意算法第 4 行到第 21 行是依次对每个样本进行处理, 其中第 8 行到第 21
行是尝试将 样本 x i \boldsymbol{x}_i x i x i \boldsymbol{x}_i x i M \mathcal{M} M C \mathcal{C} C x i \boldsymbol{x}_i x i M \mathcal{M} M C \mathcal{C} C
13.6.2 图13.9的解释
算法第6行到第10行即在聚类簇迭代更新过程中不改变种子样本的簇隶属关系；第11行到第15行即对非种子样本进行普通的k-means聚类过程；第16行到第18行更新均值向量，反复迭代，直到均值向量均未更新。
参考文献
[1] Wikipedia contributors. Laplacian matrix, 2020.
[2] Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf. Learning
with local and global consistency. Advances in neural information processing systems, 16, 2003.
[3] Chang Xu, Dacheng Tao, and Chao Xu. A survey on multi-view learning. arXiv preprint
arXiv:1304.5634, 2013.
