［注］：本文約5000字，閱讀時間約12分鐘。文章儘量使用中文，但有些專有名詞翻譯成中文顯得詞不達意，因此也用括號標註了英文。
人臉識別也許是最成功也最先到達瓶頸的深度學習應用。在go deeper， more data，higher performance的思想指導下，模型更深了，資料卻越來越難增加。目前在人臉的公開資料集標到了百萬級別，人臉識別百萬裡挑一的正確率達到99。9％（
MegaFace benchmark
）之後，發現再也標不動了。標註員能標出來的資料永遠是簡單樣本，而人臉識別模型是個深淵，當你凝視深淵的時候，深淵並不想看到你。
深淵想看到這樣的資料，並且明確被告知不是同一個人：
以及這樣的資料，並且明確被告知是同一個人：
在把標註員弄瘋之前，不如先讓模型自己去猜一猜，說不定就猜對了呢？這其實就是半監督學習的思路。利用已有的模型對無標籤資料做某種預測，將預測結果用來幫助模型訓練。這種自我增強（self-enhanced）的學習方式，雖然看起來有漂移（drift）的風險，但實際用起來還挺好用 ［5］。對於閉集（close-set）的問題，也就是所有資料都屬於一個已知的類別集合（例如ImageNet， CIFAR等），只需要模型能透過各種方法，例如標籤傳播（label propagation）等，預測出無標籤資料的標籤，再把它們加入訓練即可。
然而問題來了，人臉識別是一個開集（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］，並且每一類具有相同的方差（variance），以及不同的類具有相同的先驗機率。然而對於大規模人臉聚類，無標註資料通常來源於開放的場景（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 Face Recognition
），簡稱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聚類結果訓練的人臉模型效能的增長接近全監督模型（所有資料都使用ground truth標註）。有趣的是在IJB-A上我們的結果超過了全監督模型，原因可能是訓練集的ground truth標籤會有一些噪聲（noise），例如誤標註，導致全監督模型在IJB-A的某些測試樣例上表現不佳。
下圖是切換不同的CNN模型結構後的結果：
聚類後的部分結果如下圖所示：
每一組代表聚完類後屬於同一類
我們發現CDP還可以用來做資料和標籤清理（denoise）。例如一個標註好的資料集可能有一些標錯的樣本，或者非常低質量的圖片，可以使用CDP來找到這些圖並捨棄。如下圖：
每一組人臉在原始標註中屬於同一個人，左上角數字是CDP分配的標籤，紅框中的樣本為CDP丟棄的樣本，包括：1。 被錯誤標註進該類，實際是一個孤立點的樣本。2。 低質量圖片，包括過度模糊、卡通等。
在這篇工作中我們發現，基於學習的metric能基於更多的有效資訊進行判斷，會比手動設計的metric更擅長解決比較複雜的資料分佈。另外，這種類似多模型的投票的方式在魯棒性上帶來了很大提升，這樣可以從無標籤資料中發掘出更多的難樣本。
程式碼連結：
https：//
github。com/XiaohangZhan
/cdp
，歡迎watch/star/fork以及交流。
有監督的聚類演算法
CDP屬於一種自下而上（bottom up）的方法，因此只能感知區域性的資料結構。然而感知全域性的資料結構對於聚類更為重要，為此，我們最近提出了一種自上而下（top down）的有監督聚類方法，能自動學習根據資料的結構進行聚類，更加充分地解決上述傳統聚類的問題，不過暫時需要保密。有興趣的朋友可以持續關注我們的專欄：MMLab學術視野，也可以順便關注一下我個人的知乎賬號“
Xiaohang Zhan
”。
———————————— 分割 ————————————
更新：終於可以不用保密啦。我們的“Learning to Cluster Faces on an Affinity Graph“已經被CVPR 2019接收為oral。我在“graph convolutional network有什麼比較好的應用task？”問題下寫了個粗略的介紹，更多細節可以見我們的論文：
http：//
personal。ie。cuhk。edu。hk
/~ccloy/files/cvpr_2019_cluster。pdf
和程式碼：
https：//
github。com/yl-1993/lear
n-to-cluster
References：
［1］ X。 Zhan， Z。 Liu， J。 Yan， D。 Lin， and C。 C。 Loy。 Consensus-driven propagation in massive unlabeled data for face recognition。 In
European Conference on Computer Vision （ECCV）
， September 2018。
［2］ A。 K。 Jain。 Data clustering： 50 years beyond k-means。
Pattern recognition letters
， 31（8）：651–666， 2010。 2
［3］ Y。 Sun， X。 Wang， and X。 Tang。 “Deep learning face representation from predicting 10，000 classes。” in
Proceedings of the IEEE conference on computer vision and pattern recognition （CVPR）
。 2014。
［4］ Otto， C。， Wang， D。， & Jain， A。 K。 （2018）。 Clustering millions of faces by identity。
IEEE transactions on pattern analysis and machine intelligence （PAMI）
，
40
（2）， 289-303。
［5］ Zhu， X。 （2006）。 Semi-supervised learning literature survey。
Computer Science， University of Wisconsin-Madison
，
2
（3）， 4。
［6］ Wang， H。， Wang， Y。， Zhou， Z。， Ji， X。， Li， Z。， Gong， D。， 。。。 & Liu， W。 （2018）。 CosFace： Large margin cosine loss for deep face recognition。 in
Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition （CVPR）
。 2018。
