隨著模型越來越深，標注數據越來越難增加，人臉識別可能遇到瓶頸。本文來自MMLab香港中文大學-商湯科技聯合實驗室，提出一種有監督的Metric用于人臉聚類，來部分解決無標注數據內部結構復雜、依賴特定Metric、缺乏Outlier控制，以及時間復雜度等問題。

人臉識別也許是最成功也最先到達瓶頸的深度學習應用。在Go Deeper, MoreData，Higher Performance的思想指導下，模型更深了，數據卻越來越難增加。目前在人臉的公開數據集標到了百萬級別，人臉識別百萬里挑一的正確率達到99.9％（MegaFace Benchmark）之后，發現再也標不動了。標注員能標出來的數據永遠是簡單樣本，而人臉識別模型是個“深淵”，當你凝視“深淵”的時候，“深淵”并不想看到你。

“深淵”想看到這樣的數據，并且明確被告知不是同一個人：

以及這樣的數據，并且明確被告知是同一個人：

在把標注員弄瘋之前，不如先讓模型自己去猜一猜，說不定就猜對了呢？這其實就是半監督學習的思路。利用已有的模型對無標簽數據做某種預測，將預測結果用來幫助模型訓練。這種自我增強（Self-Enhanced）的學習方式，雖然看起來有漂移（Drift）的風險，但實際用起來還挺好用 [5]。對于閉集（Close-Set）的問題，也就是所有數據都屬于一個已知的類別集合（例如ImageNet, CIFAR等），只需要模型能通過各種方法，例如標簽傳播（labelPropagation）等，預測出無標簽數據的標簽，再把它們加入訓練即可。

然而問題來了，人臉識別是一個開集（Open-Set）的問題。

例如，人臉比對（Verification）、人臉鑒定（Identification）等任務中，測試樣本的身份（Identity）通常沒有在訓練樣本中出現過，測試過程通常是提取人臉特征進行比對，而非直接通過網絡推理得到標簽。同樣，對于無標注數據，在采集的過程中，人臉的身份也是未知的。可能有標注的數據的人臉屬于10萬個人，而新來的無標注數據屬于另外10萬個人，這樣一來就無法通過預測標簽的方式把這些數據利用起來。而聚類不同于半監督學習，只需要知道樣本的特征描述（Feature）和樣本之間的相似度度量標準（Metric）就可以做聚類。聚完類之后再給每個類分配新的標簽，同樣可以用來幫助提升人臉模型。

人臉聚類方法

傳統的人臉聚類一般采用LBP、HOG之類的手動設計的特征，因為這類特征過于過時，不在我們討論的范疇。而深度學習時代的人臉聚類，一般采用卷積神經網絡（CNN）中提取出來的特征 [4]。人臉識別的CNN通常把人臉圖片映射（Embedding）到一個高維的向量，然后使用一個線性分類器，加Softmax激活函數和交叉熵損失（Cross Entropy Loss）來訓練。

紫色的向量即為人臉特征（圖片來自 [3]）

這種方式決定了這些經過映射（Embedding）后的人臉在特征空間里分布在不同的錐形（Cone）中（下左圖），因而可以使用余弦相似度（Cosine Similarity）來度量相似度。或者如果對人臉特征做二范數（L2）歸一化，那么人臉特征則會分布在一個球面上（下右圖），這樣可以使用L2距離來度量。

圖示為2維，實際在高維空間（圖片來自 [6]）

有了特征和度量標準之后，就可以考慮如何選擇一個聚類算法了。現成的聚類算法包括K-Means,Spectral, DBSCAN, Hierarchical Agglomerative Clustering (HAC), Rank Order等以及它們的變種。利用這些方法聚類之后，將每一類中的樣本分配相同的標簽，不同的類分配不同的標簽，就可以用來充當訓練集了。

到此為止，似乎已經可以順利地完成這個任務了。然而

使用20萬張圖提取特征之后來測試一下這些聚類算法，K-Means花了10分鐘，HAC花了5.7小時，DBSCAN花了6.9小時, Spectral花了12小時。若使用60萬張圖片提取的特征來做聚類，K-Means超內存了，HAC花了61小時，DBSCAN花了80小時，Spectral跑到天荒地老之后也甩了一句超內存。當圖片數量增加到140萬的時候，幾乎所有的聚類算法都掛了。

K-Means, Spectral, HAC等傳統聚類方法的問題主要在于以下方面：

(a) 聚類算法具有較高的時間復雜度。例如，K-Means是O(NKT)，Spectral是O(N^3)，HAC是O(N^2)。

(b) 通常認為數據分布服從某些簡單的假設。例如，K-Means假設數據類內具有球狀的分布 [2]，并且每一類具有相同的方差（Ariance），以及不同的類具有相同的先驗概率。然而對于大規模人臉聚類，無標注數據通常來源于開放的場景（in-the-wild），數據內部的結構比較復雜，難以一致地服從這些假設。例如，我們期望數據長這樣（如下左圖）：

(c) 通常使用某種特定的Metric。例如上述提及的Cosine Similarity和L2距離。同樣，對于復雜的數據結構，衡量兩個樣本是否屬于同一類，單純靠樣本之間的局部相似度是不夠的，這個metric需要融合更多信息。

(d) 缺乏較好的離群值（Outliers）控制機制。Outliers來源于人臉識別模型對難樣本的Embedding誤差，以及觀測到的數據不完整。盡管部分聚類算法例如DBSCAN理論上對Outliers魯棒，但從其實際表現來講這個問題遠沒有得到解決。

有監督的Metric

終于可以說說自己的工作了。我們被ECCV2018接收的一篇論文（Consensus-Driven Propagation in Massive Unlabeled Data for FaceRecognition），簡稱CDP [1]，嘗試解決上述這些問題中的一部分。我們提出了一種有監督的Metric用于人臉聚類，來部分解決無標注數據內部結構復雜、依賴特定Metric、缺乏Outlier控制的問題，順便還解決了一下時間復雜度的問題（CDP做到了線性復雜度），當然性能也提升了一大截。

介紹方法之前我們先來介紹一下Affinity Graph。Graph在半監督學習和聚類上經常出現。Affinity Graph的節點是數據樣本，邊代表數據之間的相似度。一種常見的Affinity Graph是KNN Graph，即對所有樣本搜索K近鄰之后將樣本與其近鄰連接起來得到。我們的方法CDP基于KNN Graph來構建數據的結構。

CDP本質是學習一個Metric，也就是對樣本對（Pairs）進行判斷。如下圖，CDP首先使用多個人臉識別模型構建成一個委員會（Committee）， Committee中每個成員對基礎模型中相連的Pairs提供包括關系（是否是Neighbor）、相似度、局部結構等信息，然后使用一個多層感知機（MLP）來整合這些信息并作出預測（即這個Pair是否是同一個人）。

這個過程可以類比成一個投票的過程，Committee負責考察一個候選人（Pair）的各方面信息，將信息匯總給MLP進行決定。最后將所有的Positive Pairs組成一個新的Graph稱為Consensus-driven Graph。在此Graph上使用簡單的連通域搜索并動態剪枝即可快速得到聚類。由于MLP需要使用一部分有標簽的數據來訓練得到，所以CDP是一種基于有監督的Metric的聚類方法。

CDP框架

接下來就是激fei動chang人wu心liao的結果分析了。

在復雜度上，CDP由于只需要探索局部結構，因此除了KNN搜索之外，聚類部分的復雜度是接近線性的。在20萬數據上，不計入KNN搜索（依賴別的庫）的時間的話，CDP單模型的耗時是7.7秒，多模型的耗時是100秒。在140萬數據上，CDP單模型的耗時是48秒，多模型的耗時是585秒。試驗結果上看時間復雜度甚至低于線性（小于7倍）。

在聚類結果上，例如對20萬數據聚類，即使使用單模型也達到了89%的fsCore，多模型可以達到95.8%，強于大部分傳統聚類算法。各種聚類算法運行時間和性能測試見GitHub。

我們的實驗中使用CDP聚類后的數據加入人臉識別模型的訓練之后，可以讓模型達到接近全監督（使用Ground Truth標簽）的結果。如下圖所示：

在兩個測試集（Benchmark）上，隨著數據的增多，用CDP聚類結果訓練的人臉模型性能的增長接近全監督模型（所有數據都使用Groundtruth標注）。有趣的是在IJB-A上我們的結果超過了全監督模型，原因可能是訓練集的Ground Truth標簽會有一些噪聲（Noise），例如誤標注，導致全監督模型在IJB-A的某些測試樣例上表現不佳。

下圖是切換不同的CNN模型結構后的結果：

聚類后的部分結果如下圖所示：

每一組代表聚完類后屬于同一類

我們發現CDP還可以用來做數據和標簽清理（Denoise）。例如一個標注好的數據集可能有一些標錯的樣本，或者非常低質量的圖片，可以使用CDP來找到這些圖并舍棄。如下圖：

每一組人臉在原始標注中屬于同一個人，左上角數字是CDP分配的標簽，紅框中的樣本為CDP丟棄的樣本，包括：1. 被錯誤標注進該類，實際是一個孤立點的樣本。2. 低質量圖片，包括過度模糊、卡通等。

在這篇工作中我們發現，基于學習的Metric能基于更多的有效信息進行判斷，會比手動設計的Metric更擅長解決比較復雜的數據分布。另外，這種類似多模型的投票的方式在魯棒性上帶來了很大提升，這樣可以從無標簽數據中發掘出更多的難樣本。