前言

夏天快要過去，本書也快接近尾聲了。

第十三章

13.1 半監督學習

在此之前，我們討論的所有學習范式都具有非常明確的邊界條件：

• 監督學習：我們擁有大量帶標簽的數據樣本$(x_i,y_i)$，目標是學習從輸入$x$到輸出$y$的映射關系$f:\mathcal{X}\to \mathcal{Y}$。這里的每個樣本$x_i$都配有對應的標簽$y_i$，模型通過這些明確的輸入-輸出對來建立預測函數。
• 無監督學習：我們只有大量無標簽的數據樣本$x_i$，目標是發現數據內在的分布模式或結構。例如通過聚類算法將數據劃分為若干組，或通過降維方法找到數據在低維空間中的表示形式。
  然而在實際應用中，最常見的情況是同時存在少量帶標簽數據和大量無標簽數據。這導致了一個兩難困境：
• 如果僅使用有限的帶標簽數據進行監督學習，由于訓練樣本不足，模型容易過擬合，即在訓練集上表現良好但在新數據上泛化能力差。
• 如果完全忽略標簽信息，僅對所有數據實施無監督學習，雖然可能發現數據中的某些聚類模式，但這些發現的模式可能與目標任務無關，無法直接提升模型在特定任務上的表現。

半監督學習正是為解決這一困境而提出的方法。其研究重點是：如何同時利用少量帶標簽數據和大量無標簽數據，構建比僅使用帶標簽數據時性能更好的模型？

這個問題看似違反直覺——無標簽數據既然沒有目標信息，如何能幫助提升模型性能？關鍵在于：雖然無標簽數據不直接提供標簽信息，但它們揭示了數據在特征空間$\mathcal{X}$中的分布特性。半監督學習的基本思想是通過特定方法，使模型能夠利用無標簽數據反映的數據分布結構來輔助監督學習過程。

為了讓未標記數據發揮作用，必須對數據分布做出基本假設：如果兩個點$x_1$和$x_2$在特征空間中彼此"接近"，那么它們對應的標簽$y_1$和$y_2$也應該相似或相同。具體有兩種常見假設：

• 聚類假設：數據傾向于形成不同的簇。同一個簇內的所有數據點，無論是否被標記，都應具有相同標簽。大量未標記數據可以幫助更準確地識別這些簇的邊界。
• 流形假設：觀察到的高維數據實際上分布在低維流形上，未標記數據幫助勾勒這個低維流形的形狀。

此外，半監督學習根據目標可以分為兩種類型：

• 直推學習：訓練模型的目的是標記訓練集中未標記的數據
• 純半監督學習：訓練模型的目的是標記任何新數據

最后討論一下主動學習：與半監督學習利用已有未標記數據不同，主動學習是一個更主動的過程。它會從大量未標記數據中智能選擇"最有價值標記"的樣本，交由專家標記。這是解決標簽稀缺問題的另一種思路，與半監督學習相輔相成。

13.2 生成式方法

生成式方法基于生成式模型構建，生成式模型在7.1 貝葉斯決策論中已有介紹，這類模型的核心目標是對數據的聯合概率分布 $p(\mathbf{x},y)$ 進行建模。

這里簡要回顧貝葉斯公式：
$$p(y|\mathbf{x})=\frac{p(\mathbf{x},y)}{p(\mathbf{x})}=\frac{p(\mathbf{x}|y)p(y)}{p(\mathbf{x})}$$
其中：

• $p(y)$ 表示任意樣本屬于類別$y$的先驗概率
• $p(\mathbf{x}|y)$ 表示在類別$y$確定的條件下，生成數據$\mathbf{x}$的似然概率
  只要能夠對這兩個概率進行建模，就能推導出后驗概率$p(y|\mathbf{x})$。

傳統貝葉斯方法完全依賴已標記數據，這些數據為直接估計$p(\mathbf{x}|y)$和$p(y)$提供了基礎。而未標記數據則來自數據的邊際分布$p(\mathbf{x})$的采樣結果。根據全概率公式：
$$p(\mathbf{x})=\sum _{y}p(\mathbf{x},y)=\sum _{y}p(\mathbf{x}|y)p(y)$$
大量未標記數據能夠反映數據點在特征空間中的整體分布結構和局部密度特征。

這意味著，如果一個生成模型能夠同時準確描述已標記數據和未標記數據的統計特性，那么該模型所隱含的分類決策邊界很可能具有更高的可靠性。特別值得注意的是，這種決策邊界往往會自然地落在未標記數據揭示的低密度區域，這與半監督學習中聚類假設的核心思想完全一致。

基于高斯混合模型，我們假設數據中的$N$個類別，與高斯混合模型中的$N$個成分一一對應。即數據樣本基于如下概率密度生成：
$$p(\mathbf{x})=\sum _{i=1}^N{\alpha }_i?p(\mathbf{x}|{\mu }_i,{\Sigma }_i)=\sum _{i=1}^{N}p(y_i)p(x|y_i)$$
其中

• ${\alpha }_i$是混合系數，也代表了類別$i$的先驗概率，即$p(y=i)$
• $p(\mathbf{x}|{\mu }_i,{\Sigma }_i)$是第$i$個高斯成分的概率密度，也代表類別$i$的類條件概率密度，即$p(\mathbf{x}|y_i)$
• $({\mu }_i,{\Sigma }_i)$是第$i$個高斯成分的參數，也刻畫了第$i$類數據在特征空間中的中心位置和形狀

我們的目標是找到一組參數θ={αi,μi,Σi}i=1N\theta = \{\alpha_i, \mu_i, \Sigma_i\}_{i=1}^Nθ={αi?,μi?,Σi?}i=1N?，使得所有觀測數據出現的聯合概率最大（即最大化對數似然函數）。為了實現這個目標，我們采用EM算法進行迭代優化，具體步驟如下：

1. 參數初始化階段
首先利用少量已標記數據$D_l=\{({\mathbf{x}}_j,y_j)\}$進行初步參數估計，得到初始參數${\theta }^{(0)}$。這個初始估計不需要很精確，后續迭代會逐步優化。

2. 迭代優化階段
采用交替執行以下兩個步驟的方式進行優化：

(1) E步驟（期望步驟）
對于每個未標記樣本${\mathbf{x}}_k\in D_u$，基于當前參數${\theta }^{(t)}$計算其屬于各個類別$i$的后驗概率：
$${\gamma }_{ki}=p(y=i|{\mathbf{x}}_k,{\theta }^{(t)})=\frac{p({\mathbf{x}}_k,y=i|{\theta }^{(t)})}{p({\mathbf{x}}_k|{\theta }^{(t)})}=\frac{{\alpha }_i^{(t)}?p({\mathbf{x}}_k|{\mu }_i^{(t)},{\Sigma }_i^{(t)})}{{\sum }_{j=1}^N{\alpha }_j^{(t)}?p({\mathbf{x}}_k|{\mu }_j^{(t)},{\Sigma }_j^{(t)})}$$
這個計算過程相當于給每個未標記樣本分配了一個"軟標簽"，表示其屬于各個類別的概率權重。

(2) M步驟（最大化步驟）
結合未標記數據的"軟標簽"${\gamma }_{ki}$和已標記數據的確定標簽，重新估計所有參數：

• 均值向量${\mu }_i$的更新：
  $${\mu }_i=\frac{1}{{\sum }_{{\mathbf{x}}_j\in D_u}{\gamma }_{ji}+l_i}\left(\sum _{{\mathbf{x}}_j\in D_u}{\gamma }_{ji}{\mathbf{x}}_j+\sum _{({\mathbf{x}}_j,y_j)\in D_l\wedge y_j=i}{\mathbf{x}}_j\right)$$

• 協方差矩陣${\Sigma }_i$的更新：
  $${\Sigma }_i=\frac{1}{{\sum }_{{\mathbf{x}}_j\in D_u}{\gamma }_{ji}+l_i}\left(\sum _{{\mathbf{x}}_j\in D_u}{\gamma }_{ji}({\mathbf{x}}_j?{\mu }_i)({\mathbf{x}}_j?{\mu }_i{)}^T+\sum _{({\mathbf{x}}_j,y_j)\in D_l\wedge y_j=i}({\mathbf{x}}_j?{\mu }_i)({\mathbf{x}}_j?{\mu }_i{)}^T\right)$$

• 混合系數${\alpha }_i$的更新：
  $${\alpha }_i=\frac{1}{m}\left(\sum _{{\mathbf{x}}_j\in D_u}{\gamma }_{ji}+l_i\right)$$

3. 預測決策階段
當算法收斂得到最終參數θ?={αi?,μi?,Σi?}i=1N\theta^* = \{\alpha_i^*, \mu_i^*, \Sigma_i^*\}_{i=1}^Nθ?={αi??,μi??,Σi??}i=1N?后，對新樣本$\mathbf{x}$的預測采用貝葉斯決策規則。具體來說，我們尋找使后驗概率$p(y=j|\mathbf{x})$最大的類別$j$：

根據貝葉斯定理，后驗概率可以表示為：
$$f(\mathbf{x})=\arg \underset{j\in \mathcal{Y}}{\max }p(y=j|\mathbf{x})=\arg \underset{j\in \mathcal{Y}}{\max }\frac{p(\mathbf{x}|y=j)p(y=j)}{p(\mathbf{x})}$$

由于分母$p(\mathbf{x})$對所有類別相同，可以簡化為：
$$f(\mathbf{x})=\arg \underset{j\in \mathcal{Y}}{\max }p(\mathbf{x}|y=j)p(y=j)$$

將學習到的參數代入后，最終的預測規則為：
$$f(\mathbf{x})=\arg \underset{j\in \mathcal{Y}}{\max }\left({\alpha }_j^{?}?p(\mathbf{x}|{\mu }_j^{?},{\Sigma }_j^{?})\right)$$
這個方法簡單又嚴謹，但是該方法的成敗完全取決于我們的初始假設是否正確。如果我們假設數據是高斯混合，但實際上它長得像兩個彎月（非凸、非高斯），那么生成式方法會強制用高斯模型去擬合它，得到非常差的結果，而一個好的假設需要很強的領域知識。

13.3 半監督SVM

本節我們將學習支持向量機在半監督學習中的擴展方法：半監督支持向量機（Semi-Supervised Support Vector Machine, S3VM）。在介紹S3VM之前，我們先簡要回顧一下標準支持向量機（SVM）的基本原理。

SVM回顧
標準的支持向量機旨在找到一個決策邊界，使得離該邊界最近的樣本點（稱為支持向量）到邊界的距離最大化。最終確定的超平面位置完全由這些支持向量決定，其他樣本點不會影響決策邊界的位置。

S3VM的設計動機來源于將SVM的"最大間隔"原則與半監督學習中的"聚類假設"相結合。其核心思想體現在兩個方面：

1. 對于已有的標記數據，我們仍然要保持SVM的最大間隔分類特性；
2. 對于未標記數據，我們希望決策邊界能夠穿過數據分布中密度較低的區域，這樣可以使分類邊界位于樣本稀疏的位置，從而更好地反映數據的整體分布特征。

對于已經標記的數據樣本$({\mathbf{x}}_i,y_i)$，支持向量機(SVM)要求這些樣本必須滿足間隔約束條件：$$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1$$。而對于那些沒有標記的數據樣本${\mathbf{x}}_j$，半監督支持向量機(S3VM)可以采用軟標簽的方式進行處理。假設存在$k$個未標記樣本，那么理論上會產生$2^k$種可能的標簽組合。對于每一種標簽組合，我們都可以將其視為一個偽標記數據集，并在其上訓練一個標準的SVM模型，從而得到一個分類超平面和對應的目標函數值。我們的優化目標是從這$2^k$種可能性中，尋找能夠使SVM間隔最大化（即最小化$\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$）的最優標簽組合。

這個基于枚舉搜索的優化思想可以轉化為一個數學優化問題。
假設我們擁有：

• $l$個已標記樣本構成的集合$D_l=\{({\mathbf{x}}_i,y_i){\}}_{i=1}^l$
• $u$個未標記樣本構成的集合Du={xj}j=l+1l+uD_u = \{\boldsymbol{x}_j\}_{j=l+1}^{l+u}Du?={xj?}j=l+1l+u?

我們需要同時優化以下兩個變量：

1. 未標記樣本的偽標簽向量$\hat{\mathbf{y}}=({\hat{y}}_{l+1},\dots ,{\hat{y}}_{l+u})$
2. SVM的模型參數$(\mathbf{w},b)$
   所以目標函數為：
   $$\underset{\mathbf{w},b,\hat{\mathbf{y}}}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C_l\sum _{i=1}^l{\xi }_i+C_u\sum _{j=l+1}^{l+u}{\xi }_j$$
   約束條件：

• 對于所有已標記樣本$({\mathbf{x}}_i,y_i)\in D_l$：
  $$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1?{\xi }_i,{\xi }_i\ge 0$$
• 對于所有未標記樣本${\mathbf{x}}_j\in D_u$及其對應的偽標簽${\hat{y}}_j$：
  $${\hat{y}}_j({\mathbf{w}}^T{\mathbf{x}}_j+b)\ge 1?{\xi }_j,{\xi }_j\ge 0$$
• 偽標簽的取值限制：
  y^j∈{?1,+1}\hat{y}_j \in \{-1, +1\}y^?j?∈{?1,+1}
  其中$C_l$和$C_u$分別是對已標記數據分類錯誤的懲罰和對未標記數據分類錯誤（相對于其偽標簽）的懲罰。一般選取$C_l?C_u$因為我們對真實的標簽更有信心，不希望它們被輕易地分錯；而對未標記數據可以更“寬容”一些。

很明顯，直接窮舉所有可能的標簽組合（共$2^k$種）在計算上是不可行的，因此需要設計更高效的近似算法。這正是Transductive SVM（TSVM）的核心價值所在。

TSVM采用迭代優化的策略，具體步驟如下：

初始化：
首先僅使用已標記數據集$D_l$訓練一個標準SVM模型，得到初始分類超平面參數$(\mathbf{w},b)$。這個超平面將作為后續偽標簽預測的基準。

首次預測：
利用初始超平面對所有未標記數據$D_u$進行預測，獲得它們的初始偽標簽：
$${\hat{y}}_j=\text{sign}({\mathbf{w}}^T{\mathbf{x}}_j+b)$$
迭代優化：
此時我們獲得了一個混合數據集（包含真實標簽和偽標簽）。TSVM進入以下優化循環：

1. 模型重訓練：
   在當前完整數據集上重新訓練SVM。需要注意的是：
   • 必須保持已標記樣本的標簽不變
   • 通過調整懲罰系數$C_l$（標記數據）和$C_u$（未標記數據）來實現平衡
   • 實踐中通常采用漸進策略：從$C_u=0$開始，逐步增大至接近$C_l$的水平
2. 可疑樣本檢測：
   在未標記樣本中識別最可能錯誤的樣本對$({\mathbf{x}}_i,{\mathbf{x}}_j)$，這些樣本具有以下特征：
   • 位于當前決策邊界附近（即$|{\mathbf{w}}^T\mathbf{x}+b|$值很小）
   • 具有相反的偽標簽（${\hat{y}}_i\ne {\hat{y}}_j$）
3. 標簽交換驗證：
   • 交換候選樣本對的偽標簽（${\hat{y}}_i?{\hat{y}}_j$）
   • 重新計算SVM目標函數值
4. 優化決策：
   • 若目標函數值降低（間隔增大），則保留此次交換
   • 否則撤銷交換操作
5. 循環終止條件：
   重復步驟2-4，直到目標函數無法通過任何樣本對的交換而進一步降低。

這個迭代過程實際上是通過貪心策略調整偽標簽，引導決策邊界向數據稀疏區域移動。每次成功的交換都意味著決策邊界更符合聚類假設，即位于高密度數據區域之間的低密度間隙處。

13.4 圖半監督學習

之前的算法主要關注于劃分決策邊界，而圖半監督學習則著重考慮樣本之間的關聯性。它通過圖結構中的邊來表示樣本間的關系——若兩個樣本屬于同一類別，則它們之間的邊應具有較大的權重。在這種框架下，已標注樣本會基于自身標簽信息，通過邊權重對鄰近未標注樣本產生影響，這個過程類似于標簽信息的傳播機制。

下面我們將詳細闡述圖半監督學習的三個核心操作步驟：

圖結構構建
首先需要將離散的數據點集合$D_l\cup D_u$表示為圖結構$G=(V,E)$，其中包含以下要素：

• 頂點集：每個數據樣本（無論是否帶有標簽）對應圖中的一個頂點。對于總數為$m=l+u$的樣本集，圖中將包含$m$個頂點。
• 邊集定義：邊的權重反映頂點間的相似程度，相似度越高則權重越大。常見的鄰域定義方式是我們見過的：
  • $k$-近鄰法：為每個頂點選擇距離最近的$k$個鄰居建立連接
  • $?$-近鄰法：與中心點距離小于$?$的所有點建立連接
    其中$k$-近鄰法在實際應用中更為普遍。

又基于"鄰近樣本更可能同類"的假設，邊的權重應隨樣本距離減小而單調遞增。最常用的權重計算方法是采用高斯核函數：
$$w_{ij}=\exp \left(?\frac{\Vert {\mathbf{x}}_i?{\mathbf{x}}_j{\Vert }^2}{2{\sigma }^2}\right)$$
式中各參數含義為：

• $w_{ij}$：頂點$i$與$j$之間的邊權重
• $\Vert {\mathbf{x}}_i?{\mathbf{x}}_j{\Vert }^2$：特征空間中兩樣本距離的平方
• $\sigma$：控制權重衰減速度的關鍵參數
  • 當$\sigma$取值較小時，權重隨距離增加快速衰減，僅極近鄰點能保持有效連接
  • 當$\sigma$取值較大時，權重衰減緩慢，使得較遠距離的點仍能保持一定關聯強度

所有邊的權重構成$m\times m$維的權重矩陣$W$，其中$W_{ij}=w_{ij}$表示頂點間的連接強度，無連接時$W_{ij}=0$。

定義平滑度（能量）
我們希望從圖中學習到一個映射函數$h:V\to \mathbb{R}$，該函數將圖中的每個頂點映射到一個實數值。然后通過符號函數$y_i=\text{sign}(h({\mathbf{x}}_i))$得到頂點${\mathbf{x}}_i$的分類結果。為了使這個映射函數$h$能夠滿足聚類假設和流形假設，我們需要定義一個平滑度度量來確保標簽不會在數據密集區域發生劇烈變化。

假設標簽分配向量$f=(h({\mathbf{x}}_1),h({\mathbf{x}}_2),\dots ,h({\mathbf{x}}_m))$表示所有頂點在映射$h$下的標簽分配方案。我們可以證明，二次型$f^{T}Lf$是一個有效的平滑度定義，其中$L=D?W$是圖的拉普拉斯矩陣。這里$D$是一個對角矩陣，其對角線元素$D_{ii}={\sum }_{j=1}^m{W}_{ij}$表示頂點$i$的所有邊權重之和，而$W$是圖的鄰接權重矩陣。

注意這里我用$h$替換了書中的“能量函數”$f$，我覺得用向量更易懂

接下來，我們詳細展開這個二次型的計算過程：
$$\begin{array}{rl}{f}^{T}Lf& =f^T(D?W)f\\ & =f^{T}Df?f^{T}Wf\\ & =\sum _{i=1}^m{D}_{ii}{f}_i^2?\sum _{i,j=1}^m{W}_{ij}{f}_i{f}_j\\ & =\sum _{i=1}^m\left(\sum _{j=1}^m{W}_{ij}\right)f_i^2?\sum _{i,j=1}^m{W}_{ij}{f}_i{f}_j\\ & =\frac{1}{2}\left(\sum _{i,j=1}^m{W}_{ij}{f}_i^2?2\sum _{i,j=1}^m{W}_{ij}{f}_i{f}_j+\sum _{i,j=1}^m{W}_{ij}{f}_j^2\right)\\ & =\frac{1}{2}\sum _{i,j=1}^m{W}_{ij}(f_i?f_j{)}^2\end{array}$$
從推導結果可以看出，$f^{T}Lf$的值與所有相連頂點對$(i,j)$的標簽預測值之差的平方成正比，并且由它們之間的連接權重（相似度）$W_{ij}$加權。因此，最小化$f^{T}Lf$等價于要求連接緊密（即$W_{ij}$較大）的頂點對具有盡可能接近的標簽預測值（$f_i\approx f_j$）。
該二次型是一個理想的用于衡量標簽分配$f$在圖上的平滑度工具。這個值也被稱為圖的能量。

標簽傳播算法
我們需要找到一個最優的標簽分配函數$f$，這個函數需要滿足兩個主要條件：

1. 預測一致性：對于已經標記的數據點，預測值$f_i$應當盡可能接近真實標簽$y_i$。
2. 圖結構平滑性：整個標簽分配$f$在圖結構上應該是平滑的，這意味著$f^{T}Lf$的值要盡可能小，其中$L$是上述圖的拉普拉斯矩陣。

基于這兩個要求，我們可以寫出以下正則化的目標函數：
$$J(f)=\sum _{i=1}^l(f_i?y_i{)}^2+\lambda f^{T}Lf$$
這里$\lambda$是調節兩項相對重要性的超參數。雖然這個目標函數是凸的，但直接求解需要對一個大矩陣求逆，計算復雜度很高。因此實際應用中通常采用迭代的標簽傳播算法。

算法思想：每個節點通過不斷接收鄰居節點的標簽信息，并根據連接邊的權重來更新自己的標簽。這個過程持續迭代，直到整個網絡的標簽分布達到穩定狀態。

首先進行初始化：

• 構建一個$m\times C$的標簽概率矩陣$F$，其中$C$是類別數量。矩陣的第$i$行$F_i$表示樣本${\mathbf{x}}_i$的標簽概率分布。
• 初始化固定的標簽矩陣$Y$（大小也是$m\times C$），它保存已知的標簽信息，通常設$F_0=Y$。
• 對于已標記節點$i$（真實標簽為$y_i$），將$F_i$初始化為one-hot向量：在$y_i$對應位置為$1$，其他位置為$0$。
• 對于未標記節點，可以將其對應的$F_i$初始化為全$0$向量或均勻分布。

然后開始迭代過程：

1. 計算轉移矩陣$S$：

   • 首先計算上述對角矩陣$D$。
   • 定義對稱的轉移矩陣：$$\mathbf{S}={\mathbf{D}}^{?\frac{1}{2}}\mathbf{W}{\mathbf{D}}^{?\frac{1}{2}}$$
   • 矩陣乘積$SF$的第$i$行${\left(\mathbf{SF}(t)\right)}_i={\sum }_{j=1}^m{S}_{ij}{F}_j(t)$表示節點$i$從所有鄰居節點$j$獲得的加權標簽信息（因為只有臨近節點的權重$W_{ij}$不為零，對應$S_{ij}\ne 0$）。

2. 標簽傳播更新：

   • 在每次迭代$t$時執行更新：$$\mathbf{F}(t+1)=\alpha \mathbf{SF}(t)+(1?\alpha )\mathbf{Y}$$
   • 其中$\alpha$控制新接收的鄰居信息權重，$(1?\alpha )Y$項保留初始標簽信息。

3. 重復迭代直到標簽矩陣$F$收斂（變化小于某個閾值）。

最終得到的收斂矩陣$F^{?}$即為預測結果。對于未標記節點$j$，取其對應行$F_j^{?}$中最大概率值對應的類別作為預測標簽：
y^j=arg?max?c∈{1,…,C}Fjc? \hat{y}_j = \arg\max_{c \in \{1, \dots, C\}} F^*_{jc} y^?j?=argc∈{1,…,C}max?Fjc??

13.5 基于分歧的方法

在之前的方法中，我們主要依賴于數據的平滑性假設來最大化利用未標記數據并劃分決策邊界。然而，僅依靠這一假設可能無法得到最優的邊界。由于平滑性假設已經被充分挖掘，為了進一步提升邊界質量，我們可以引入新的假設：多視角/冗余性假設。其思想是：數據的不同“視角”（例如不同的特征子集或模型架構）都應當能夠獨立地給出正確的預測。換句話說，問題的解并不唯一，可以通過多種不同的途徑獲得。
對于如何利用未標記數據，其價值主要體現在作為不同學習器之間達成共識的媒介。具體來說：

• 如果多個基于不同視角構建的、性能良好的學習器對某個未標記樣本的預測出現顯著分歧，則表明該樣本很可能位于當前決策邊界附近，具有較高的信息量。
• 反之，如果這些學習器對某個未標記樣本的預測表現出高度一致且置信度高，那么這個預測結果就具有較高的可靠性。
  整個學習過程的目標依舊是在確保已標記數據上預測準確性的同時，最大化不同學習器在未標記數據上的預測一致性。

這類方法的一個典型代表是Co-Training算法，其設計初衷是為了處理天然具有多視角特征的數據。為了使Co-Training算法在理論上能夠有效工作，需要滿足兩個重要條件：

1. 視角充分性：要求數據的特征空間能夠被劃分為兩個獨立的視角，即特征集合可以表示為笛卡爾積形式$X=X_1\times X_2$。其中每個視角$X_1$或$X_2$都必須包含足夠的信息，使得僅憑該視角就能獨立完成學習任務并做出有效預測。舉例來說，在網頁分類任務中，$X_1$可以表示網頁本身的文本內容，而$X_2$可以表示指向該網頁的所有錨文本。在這種情況下，無論是僅使用$X_1$還是僅使用$X_2$，都應該能夠訓練出具有一定準確率的分類器。

2. 視角條件獨立性：在給定樣本真實標簽$y$的條件下，兩個視角$X_1$和$X_2$必須滿足條件獨立性，其數學表達為$$P(X_1,X_2|y)=P(X_1|y)P(X_2|y)$$。雖然這個假設在理論上要求較強，但在實際應用中發現，即便是弱相關的視角往往也能取得不錯的效果。這個條件的直觀理解是：兩個視角是從不同角度對同一對象的描述，因此它們產生錯誤的模式應該是相互獨立的。

假設我們有一個少量的已標記數據集$L$和一個大量的未標記數據集$U$。基于這兩個數據集，我們首先需要找到數據的兩個不同視角：$X_1$和$X_2$。在初始階段，我們使用已標記數據集$L$分別訓練兩個分類器$h_1$和$h_2$。需要注意的是，$h_1$只能使用視角$X_1$的特征進行訓練和預測，而$h_2$只能使用視角$X_2$的特征。

接下來是迭代協同訓練的過程，該過程會持續進行，直到未標記數據集$U$為空或者達到預設的最大迭代次數。具體步驟如下：

1. 分類器進行預測與篩選：
   • 首先，分類器$h_1$對當前所有未標記數據$U$進行預測。
   • 從這些預測結果中，我們篩選出$k$個$h_1$預測置信度最高的正樣本和$k$個置信度最高的負樣本（如果是多分類問題，則從每個類別中選出置信度最高的若干樣本）。這些樣本及其由$h_1$賦予的偽標簽組成一個新的集合$L_1^{\prime }$。
   • 對分類器$h_2$執行相同的操作，得到另一個高置信度樣本集$L_2^{\prime }$。
2. 交叉提供偽標簽數據：
   • 將$h_1$篩選出的高置信度樣本集$L_1^{\prime }$從$U$中移除，并將其添加到$h_2$的訓練集中。
   • 同樣地，將$h_2$篩選出的高置信度樣本集$L_2^{\prime }$從$U$中移除，并將其添加到$h_1$的訓練集中。
3. 再訓練：
   • 分類器$h_1$使用更新后的訓練集（即原始標記數據$L$加上之前所有由$h_2$提供的偽標簽數據）進行重新訓練。
   • 分類器$h_2$同樣使用更新后的訓練集（即原始標記數據$L$加上之前所有由$h_1$提供的偽標簽數據）進行重新訓練。
4. 進入下一輪迭代，重復執行上述步驟，直至達到結束條件。

Co-Training的有效性源于不同視角提供的互補信息以及通過偽標簽實現的信息交換。具體來說：

• 分類器$h_1$是視角$X_1$的“專家”，能夠在其專業領域內找到一些它非常有把握的樣本。
• 當$h_1$將這些樣本（例如$\mathbf{x}$）及其偽標簽（例如$y^{\prime }$）傳遞給$h_2$時，實際上是為$h_2$提供了一個新的監督信息：$({\mathbf{x}}_2,y^{\prime })$。
• 對于$h_2$來說，它獲得了一個新的帶有標簽的訓練樣本，而這個樣本的特征${\mathbf{x}}_2$屬于它自己的專業領域。由于視角的條件獨立性，$h_1$和$h_2$的錯誤模式是不同的。因此，$h_1$自信提供的標簽有很大概率是$h_2$難以通過自身視角獨立判斷的，從而幫助$h_2$修正和完善其決策邊界。
• 這一過程是雙向的，兩個分類器互相“教學”，利用對方的專長彌補自身的不足，逐步在大量未標記數據上擴展已標記數據集的規模，最終提升泛化性能。

最后，雖然Co-Training最初要求樣本具有多視角，但研究發現只要學習器之間存在明顯差異（例如參數不同、算法不同等），都可以提高泛化性能。因此，這類方法也被稱為基于分歧的方法。

13.6 半監督聚類

現在我們將討論重點從有監督學習轉向無監督學習。與有監督學習類似，在無監督學習的訓練集中也經常包含少量額外的輔助信息，這些信息主要分為兩類：

1. 約束條件：

   • 必聯約束和勿聯約束：對于數據點對$({\mathbf{x}}_i,{\mathbf{x}}_j)$，前者要求它們必須被劃分到同一個簇中，后者則要求它們必須被劃分到不同的簇中。
   • 數學可表示為：
     • 必聯約束集：$ML=\{({\mathbf{x}}_i,{\mathbf{x}}_j)\}$
     • 勿聯約束集：$CL=\{({\mathbf{x}}_i,{\mathbf{x}}_j)\}$

2. 部分標記數據：少量數據點帶有已知的類別標簽。
   下面我們以K均值算法（參見9.3.1節）為基礎，分別說明如何處理這兩類信息。
   約束式半監督聚類算法
   我們將標準K均值算法改進為約束K均值算法，主要區別體現在樣本的簇分配階段。具體步驟如下：
   首先，與標準K均值算法相同，隨機選擇$k$個數據點作為初始簇中心（質心）${\mathbf{\mu }}_1,{\mathbf{\mu }}_2,\dots ,{\mathbf{\mu }}_k$。
   然后，根據給定的約束信息初始化兩個集合：必聯約束集$ML$和勿聯約束集$CL$

接著進入迭代循環過程：

1. 簇分配步驟：
   對于每個數據點${\mathbf{x}}_i$，執行以下操作：
   • 計算${\mathbf{x}}_i$到所有簇中心${\mathbf{\mu }}_k$的距離$d({\mathbf{x}}_i,{\mathbf{\mu }}_k)$
   • 對每個可能的簇分配目標$k$，進行約束檢查：
     • 勿聯約束檢查：
       遍歷$CL$中所有與${\mathbf{x}}_i$相關的約束$({\mathbf{x}}_i,{\mathbf{x}}_j)$。如果存在${\mathbf{x}}_j$已經被分配到簇$k$，則${\mathbf{x}}_i$不能被分配到$k$，否則會違反勿聯約束。
     • 必聯約束檢查：
       遍歷$ML$中所有與${\mathbf{x}}_i$相關的約束$({\mathbf{x}}_i,{\mathbf{x}}_j)$。如果存在${\mathbf{x}}_j$已經被分配到另一個簇$l$（$l\ne k$），則${\mathbf{x}}_i$不能被分配到$k$，否則會違反必聯約束。
   • 從所有滿足約束條件的簇中，選擇距離${\mathbf{x}}_i$最近的簇進行分配。如果沒有符合條件的簇，則標記分配失敗（實際應用中可采用啟發式方法處理）。
2. 簇中心更新步驟：與標準K均值算法完全相同。對于每個簇$k$，重新計算其中心：$${\mathbf{\mu }}_k=\frac{1}{|C_k|}\sum _{{\mathbf{x}}_j\in C_k}{\mathbf{x}}_j$$
3. 終止條件：當簇分配不再發生變化或達到最大迭代次數時，算法終止。

種子式半監督聚類
這種方法利用少量帶標簽的樣本（稱為種子集）作為聚類的起點和錨點。基于K均值算法的Seeded K均值算法主要修改的是初始化階段，具體步驟如下：

1. 初始化階段

   • 不再隨機選擇初始中心，而是根據種子集計算初始的$K$個簇中心。
   • 對于每一個類別$k$，其初始簇中心${\mathbf{\mu }}_k$通過以下公式計算：$${\mathbf{\mu }}_k^{(0)}=\frac{1}{|S_k|}\sum _{{\mathbf{x}}_j\in S_k}{\mathbf{x}}_j$$
     其中，$S_k$表示屬于類別$k$的種子點集合，$|S_k|$是該集合的大小。
   • 所有未標記的數據點在初始時均未分配到任何簇。

2. 迭代階段

   • 剩余步驟與標準K均值算法基本一致，包括以下兩步：
     • 分配步驟：將每個數據點分配到最近的簇中心。
     • 更新步驟：重新計算每個簇的中心。
   • 區別：種子數據點始終保持其初始分配的類別，不會在迭代過程中改變隸屬關系。