A Unified Objective for Novel Class Discovery-有解無憂

2021/9/14

NCD：通過一個沒有類重疊的標記資料集訓練模型，以對一個無標記的資料集進行聚類，從而發現無標記資料集中的新的類別，文章通過logit連接的方式，對偽標簽和ground truth使用一個統一的交叉熵損失函式對模型進行訓練，簡化了訓練流程并大幅提升了效果，

原文地址：https://arxiv.org/abs/2108.08536
Github：https://github.com/DonkeyShot21/UNO

參考：
representation learning與clustering的結合(1)
ICCV2021 Oral | UNO：用于“新類發現”的統一目標函式，簡化訓練流程！已開源！
arXiv:1901.00544

NCD(Novel Class Discovery)新類發現

課題起源于論文Multi-class Classification without Multi-class Labels，文中通過估計為標記樣本的成對相似性，通過利用兩兩相似度來訓練聚類網路，以識別無標記資料集中的新類，解決無多類標簽的多類別分類任務，由這篇文章開始，NCD成為了一個新的課題，

背景：

通過利用包含不同但相關類的標記集的先驗知識來推斷未標記集中的新物件類別，
網路受益于在標記集上可用的監督信號，以學習豐富的影像表示，可以轉移到發現未標記集中的未知類 ，
在訓練時，資料被分割成一組標記影像和一組未標記影像（假設類集不相交），這兩組訓練集同時用來訓練單個網路來對已知類和未知類進行分類，
本文的重點在于，生成效果足以跟ground truth一同處理的pseudo-labels，

總體結構

文章提出了一個通過單個損失函式來消除自監督的預訓練步驟，并統一所有的訓練目標（如圖1所示）的方法，具體來說，使用多視圖自標記策略，生成可以用ground-truth標簽同源處理的偽標簽，這使得在標記集和未標記集上使用統一的交叉熵損失成為可能，給定一個Batch的影像，使用隨機轉換生成每個影像的兩個視圖，網路預測了每個視圖的所有類（標記為+未標記）的概率分布，這將產生了兩個獨立Batch的子集，由于是同一張圖片的不同資料增強結果，因此每個視圖都可以作為其他視圖的偽標簽，然后結合ground-truth和偽標簽，向網路提供反饋并更新其引數，

在這里插入圖片描述

圖1

方法

資料準備

在NCD任務中，訓練資料被分為兩組：

標記資料集： D l = { ( x 1 l , y 1 l ) , . . . , ( x N l , y N l ) } D^l=\lbrace (x_1^l,y_1^l), ... ,(x_N^l, y_N^l) \rbrace Dl={(x1l?,y1l?),...,(xNl?,yNl?)}
無標記資料集： D u = { x 1 u , . . . , x M u } D^u=\lbrace x_1^u, ...,x_M^u \rbrace Du={x1u?,...,xMu?}

定義 C l C^l Cl為標記資料集中的類別而 C u C^u Cu為無標記資料集中的類別，任務的目標是通過 D u D^u Du來發掘 C u C^u Cu個聚類，而 C u C^u Cu是先驗的，而 C l C^l Cl與 C u C^u Cu不相交，在測驗時，模型的目標是對標記類和未標記類對應的影像進行分類，我們將這個問題表述為學習從影像域到完整標簽集的映射: Y = { 1 , . . . , C l , . . . , C l + C u } Y=\lbrace 1, ...,C^l,...,C^l + C^u \rbrace Y={1,...,Cl,...,Cl+Cu}，總體結構圖如圖2所示，

在這里插入圖片描述

圖2. UNO總體架構圖

Unified Objective

為了解決NCD問題，作者提出訓練一個由θ引數化的神經網路 f θ ( x ) = { p ( y ∣ x ) ; y ∈ Y } f_θ(x)= \lbrace p(y|x);y\in Y \rbrace fθ?(x)={p(y∣x);y∈Y}，它由一個共享的編碼器E和兩個頭h和g組成，

其中編碼器E是一個標準的后接平均池化層的卷積網路(CNN)，用于編碼影像的特征：
z = E ( x ) , z ∈ R k z = E(x), z\in \mathbb{R^k} z=E(x),z∈Rk
head h 是一個具有 C l C^l Cl個輸出神經元的線性分類器，
head g 使用了一個多層感知機(MLP)，它將 z z z投影到一個低維表示 z ′ z' z′，然后接入一個有 C u C^u Cu輸出的線性分類器，

由h和g產生的logits l h ∈ R C l l_h\in\mathbb{R}^{C^l} lh?∈RCl與 l g ∈ R C u l_g\in\mathbb{R}^{C^u} lg?∈RCu進行concat得到 l = [ l h , l g ] l=[l_h,l_g] l=[lh?,lg?]，將它們輸入到共享的softmax層σ，輸出完整標簽集的后驗分布 Y : p = σ ( l / τ ) Y:p=σ(l/\tau) Y:p=σ(l/τ)，其中τ是softmax的溫度引數，得到了p的概率分數之后，我們就可以使用標準的交叉熵來訓練整個網路：
l ( x , y ) = ? Σ c = 1 C y c l o g ( p c ) (1) l(x,y)=-\Sigma_{c=1}^Cy_clog(p_c)\tag{1} l(x,y)=?Σc=1C?yc?log(pc?)(1)
其中， C = C l + C u C=C^l+C^u C=Cl+Cu，針對 x ∈ D l x\in D^l x∈Dl與 x ∈ D u x\in D^u x∈Du對y進行zero-padding，如下所示：
y = { [ y l , 0 C u ] x ∈ D l [ 0 C l , y ^ ] x ∈ D u (2) y=\left\{ \begin{array}{c} [y^l,0_{C^u}] & x \in D^l \\ [0_{C^l},\hat{y}] & x \in D^u \end{array} \right. \tag{2} y={[yl,0Cu?][0Cl?,y^?]?x∈Dlx∈Du?(2)
這里， 0 C u 0_{C^u} 0Cu?和 0 C l 0_{C^l} 0Cl?分別表示維度為 C u C^u Cu和 C l C^l Cl的零向量，依據是已知類與未知類互相之間不重合，

Multi-view and Pseudo-labeling

Multi-view

本節中介紹了如何利用多視圖策略來為統一目標生成偽標簽，給定一個影像x，作者采用常見的資料增強技術，包括對x應用隨機裁剪和顏色抖動，得到x的兩個不同的“視圖”(v1,v2)，它們被調整到原始大小并輸入給f，

如果 ( x , y l ) ∈ D l (x,y^l)\in D^l (x,yl)∈Dl，即樣本x屬于標記資料集，則 y 1 = y 2 = [ y l , 0 C u ] y_1=y_2=[y^l,0_{C^u}] y1?=y2?=[yl,0Cu?]，另一方面，如果 x ∈ D u x \in D^u x∈Du，則使用由v1與v2計算得到的 y 1 ^ \hat{y_1} y1?^?與 y 2 ^ \hat{y_2} y2?^?與 0 C l 0_{C^l} 0Cl?進行concat操作，這樣一來，公式（1）就可以獨立地應用于每個視圖，

然而，這種方法并不鼓勵網路對同一影像的不同視圖輸出一致的預測，為了強制執行這個目標，作者使用了交換的預測任務：
l ( v 1 , y 2 ) + l ( v 2 , y 1 ) (3) l(v_1,y_2)+l(v_2,y_1)\tag{3} l(v1?,y2?)+l(v2?,y1?)(3)

Pseudo-labeling

Label assignment

關于偽標簽計算，一個常規的獲取視圖 v 1 v_1 v1?的偽標簽 y 1 ^ \hat{y_1} y1?^?的方法是直接使用g來預測編碼器E產生的特征圖 z 1 = E ( v 1 ) z_1=E(v_1) z1?=E(v1?)，從而得到 g ( z 1 ) = l g 1 g(z_1)=l_g^1 g(z1?)=lg1?，然后進行softmax操作得到 p g 1 = σ ( l g 1 / τ ) p_g^1=\sigma(l_g^1/\tau) pg1?=σ(lg1?/τ)，最后令 y 2 ^ = p g 1 \hat{y_2}=p_g^1 y2?^?=pg1?并代入公式（2）的計算中，然而，文獻[27]中觀察到這樣的偽標簽設定會導致退化，具體來說就是對于任何不同的inputs，g總是給出相同的logits vector，
為了解決這個問題，論文Self-labelling via simultaneous clustering and representation learning中詳細的論述了使用label assignment進行聚類并求解偽標簽的方法，方法與DeepCluster類似，DeepCluster的結構如圖3所示，
在這里插入圖片描述

圖3 DeepCluster

用已有的clustering演算法，如K-means去獲得Pseudo-labels，見上圖，然后去supervise學習representation，這就是DeepCluster，但clustering獲得的labels畢竟不是100%的正確，所以這種naively的結合，會出現一些問題，比如，將所有的樣本都歸為同一類，
解決思路是加了一個constraint，labels必須要對所有的樣本平均分配，即是最大化樣本的indices和labels間的information，
考慮 x = Φ ( I ) x=\Phi(I) x=Φ(I)將圖片I映射到特征向量 x ∈ R D x\in \mathbb{R^D} x∈RD，則N的資料點 I 1 , . . . , I N I_1,...,I_N I1?,...,IN?對應的labels為 y 1 , . . . , y N ∈ { 1 , . . . , K } y_1,...,y_N \in \lbrace 1,...,K \rbrace y1?,...,yN?∈{1,...,K}，通常將一個但曾的線性分類器用于將特征向量轉化為class score，表述為 h : R D → R K h:\mathbb{R^D} \rightarrow \mathbb{R^K} h:RD→RK，class score再通過softmax映射為probabilities
p ( y = ? ∣ x i ) = s o f t m a x ( h ( Φ ( x i ) ) ) p(y=\cdot|x_i)=softmax(h(\Phi(x_i))) p(y=?∣xi?)=softmax(h(Φ(xi?)))
模型引數使用cross-entropy loss學習得到公式（4）：
E ( p , q ) = ? 1 N ∑ i = 1 N l o g p ( y i ∣ x i ) (4) E(p,q)=-{{1} \over {N}}\sum_{i=1}^Nlogp(y_i|x_i)\tag{4} E(p,q)=?N1?i=1∑N?logp(yi?∣xi?)(4)
但在fully unsupervised的情況下，最關鍵要解決的問題是：最小化上式將會導致模型對于所有的資料點都輸出一個單一的（任意的）label，
為了解決這個問題，首先將labels表示為后驗(posterior)分布 q ( y ∣ x i ) q(y|x_i) q(y∣xi?)，并將公式（4）重寫為：
E ( p , q ) = ? 1 N ∑ i = 1 N ∑ y = 1 k q ( y ∣ x i ) l o g p ( y ∣ x i ) (5) E(p,q)=-{1 \over N} \sum _{i=1} ^N \sum _{y=1} ^k q(y|x_i)logp(y|x_i)\tag{5} E(p,q)=?N1?i=1∑N?y=1∑k?q(y∣xi?)logp(y∣xi?)(5)
其實就是計算p和q的交叉熵，如果將后驗 q ( y ∣ x i ) = δ ( y ? y i ) q(y|x_i)=\delta(y-y_i) q(y∣xi?)=δ(y?yi?)，即使用one-hot表示，則公式（4）等同于公式（5），有 E ( p , q ) = E ( p ∣ y i , . . . , y N ) E(p,q)=E(p|y_i,...,y_N) E(p,q)=E(p∣yi?,...,yN?)，因此優化 q ( y ∣ x i ) q(y|x_i) q(y∣xi?)實際上等同于標簽再分配(reassign labels)，如果對q不加限制，則必然導致退化的結果，
因此對q作出限制：整個dataset中，每一類的數量必須是一樣的，即labels對dataset進行均分，則目標函式可以寫為：
min ? p , q E ( p , q ) s u b j e c t t o ? y : q ( y ∣ x i ) ∈ { 0 , 1 } a n d ∑ i = 1 N q ( y ∣ x i ) = N K (6) \min_{p,q}E(p,q) \quad subject \ to \quad \forall y:q(y|x_i) \in \lbrace 0,1 \rbrace \ and \ \sum _{i=1} ^N q(y|x_i) = {N \over K} \tag{6} p,qmin?E(p,q)subject to?y:q(y∣xi?)∈{0,1} and i=1∑N?q(y∣xi?)=KN?(6)
為了方便觀察，令 P y i = p ( y ∣ x i ) 1 N P_{y_i}=p(y|x_i){1 \over N} Pyi??=p(y∣xi?)N1?，由模型估算出的 K × N K \times N K×N聯合概率分布(joint probabilities)矩陣，K為類的數量，N為樣本數量； Q y i = q ( y ∣ x i ) 1 N Q_{y_i}=q(y|x_i){1 \over N} Qyi??=q(y∣xi?)N1?，這是assign的 K × N K \times N K×N聯合概率分布矩陣，則矩陣Q可表示為：
U ( r , c ) : = { Q ∈ R + K × N ∣ Q 1 = r , Q T 1 = c } r = 1 K ? 1 c = 1 N ? 1 (7) U(r,c):=\lbrace Q \in \mathbb{R_+}^{K \times N}|Q1=r,Q^T1=c \rbrace \\ r={1 \over K} \cdot 1 \tag{7} \\ c={1 \over N} \cdot 1 U(r,c):={Q∈R+?K×N∣Q1=r,QT1=c}r=K1??1c=N1??1(7)
1是全1的向量，其維度由 Q Q Q決定，所以r和c是Q在列和行上的邊緣投影，

UNO中的偽標簽計算

回到UNO中，設 L = [ l g 1 , . . . , l g B ] L=[l_g^1,...,l_g^B] L=[lg1?,...,lgB?]，其列是由g對B大小的mini-batch影像計算的logits，設 Y ^ = [ y 1 ^ , . . . , y B ^ ] \hat{Y}=[\hat{y_1},...,\hat{y_B}] Y^=[y1?^?,...,yB?^?]，其行是當前batch處理的未知偽標簽的矩陣，同時，作者添加了一個熵項 H ( Y ) H(Y) H(Y)，它懲罰所有logits相等的情況，則可以將任務轉化為：
Y ^ = max ? Y ∈ Γ T r ( Y L ) + ? H ( Y ) Γ = { Y ∈ R + C u × B ∣ Y 1 B = 1 C u × 1 C u , Y T 1 C u = 1 B × 1 B } (8) \hat{Y}=\max _{Y \in \Gamma}Tr(YL)+ \epsilon H(Y) \\ \Gamma = \lbrace Y \in \mathbb{R_+}^{C^u \times B}|Y1_B={1 \over C^u} \times 1_{C^u},Y^T1_{C^u}={1 \over B} \times 1_B \rbrace \tag{8} Y^=Y∈Γmax?Tr(YL)+?H(Y)Γ={Y∈R+?Cu×B∣Y1B?=Cu1?×1Cu?,YT1Cu?=B1?×1B?}(8)
其中， ? > 0 \epsilon > 0 ?>0是超引數， H H H是一個用于散射偽標簽的熵函式，這樣的條件強制每個聚類中心平均在一個batch中被選擇 B u C u B^u \over C^u CuBu?次， B u B^u Bu是一個batch中的無標記樣本數量，公式（8）中， Γ \Gamma Γ又稱為運輸多面體(transportation polytope)，可以用Sinkhorn-Knopp演算法進行求解，

過度聚類Overclustering

為了提高聚類性能，作者結合主要的聚類任務，采用了過度聚類（強制f生成一個更細粒度的未標記資料的另一個磁區），這能夠提高特征表示的質量，與E相連的過度聚類頭o與g相似，但是有 K = C u × m K=C^u \times m K=Cu×m個聚類輸出，
作者還嘗試使用了多個聚類頭 ( g 1 , . . . , g n ) (g_1,...,g_n) (g1?,...,gn?)與 ( o 1 , . . . , o n ) (o_1,...,o_n) (o1?,...,on?)通過使用多個頭，增加了反向傳播到網路共享部分的整體信號，在訓練時，對于給定的一個batch資料，對 g 1 , . . . , g n g_1,...,g_n g1?,...,gn?進行迭代，對 g i g_i gi?與 h ( l h ) h(l_h) h(lh?)產生的logits進行concat連接，然后將結果送入到一個 C l + C u C^l + C^u Cl+Cu的Softmax中，并計算交叉熵損失函式， o j o_j oj?也同樣進行類似的操作，接入一個 C l + K C^l + K Cl+K輸出的softmax層，