NO IMAGE

Yang, C., et al., Semi-supervised low-rank representation for image classification. Signal Image & Video Processing, 2016: p. 1-8.
本文是這篇 SIViP 期刊論文的筆記,主要是對文中的理論方法進行展開詳解。本人學術水平有限,文中如有錯誤之處,敬請指正。

摘要: LRR 可以構建低秩的、稀疏的係數矩陣,和字典矩陣的線性組合表示影象,但是實際上很不實用,因為缺少了影象資訊。這是一個非監督的方法。基於 LRR ,此文提出了一種半監督的方法,標籤約束稀疏低秩表示(label constrained sparse low-rank representation, LCSLRR),把標籤資訊加入作為硬約束條件。加入了這個約束之後,提升了低秩分解的判別能力。構建了LCSLRR 圖來表示資料結構,用於半監督學習,並在圖中提供邊緣權值通過搜尋一個低秩、稀疏的矩陣(在論文中沒有看到)。

1 簡介

LRR 1 通過在所有候選資料中,尋找最低秩的表達,並用已有的字典的線性組合表示資料樣本。它已經能應用到人臉識別 2,顯著目標檢測 3,背景提取 4,追蹤 5,3D 視覺恢復 6 等。LRR 是一種非監督的方法,實際使用時非常有限制。為了彌補這樣的缺陷,一些額外的約束,比如非負 7 和稀疏,顯示或隱式加入 LRR 中,推匯出一些半監督的 LRR 演算法。比如,一種非負低秩、稀疏圖模型 (non-negative low-rank and sparse (NNLRS) graph 8) 是一種半監督的方法,新增約束使係數矩陣必須滿足非負、稀疏和低秩,來構建一個資訊圖,用於半監督學習。NNLRS 的稀疏約束捕捉到資料的區域性、低維的聯絡;而非負約束確保每一個資料都在其鄰點的凸包之內(不知道有什麼意義)。
此文提出了一個半監督的方法,label constrained sparse low-rank representation (LCSLRR),其加入了標籤資訊作為額外的約束。該方法的核心思想是有相同標籤的資料有類似的表示。LCSLRR 將標籤資訊以一個指示矩陣的形式加入目標函式中,推匯出優化過程。在推導優化方法之後,推匯出圖鄰近結構和圖權值矩陣,用於半監督學習(論文只有一段簡短的文字表述,沒有圖???)。
此文的主要貢獻有:

  • 提出了一種半監督的學習框架,加入了標籤資訊到優化函式中;

  • 提出了一種解決圖特徵表示的方法,基於資訊圖(沒看到???)。該方法同時推導了圖結構和圖權值。其避免了微調引數的代價,可以適用於很多的實際應用場合。

2 標籤約束、低秩圖

LRR 是一個有效的影象表示模型。X=[x1,x2,⋯,xn]∈Rd×nX = [x_1, x_2, \cdots, x_n] \in \mathbb{R}^{d \times n} 是一個 mm 維的資料向量集合,來自一組線性子空間 {Si}di=1 \{ S_i \}_{i=1}^d,其中 SiS_i 的維度是 rir_i。資料的每一列都可以用字典 A=[a1,a2,⋯,am]A = [a_1, a_2, \cdots, a_m] 的線性組合表示,

X=AZ,(1)

\begin{equation} \tag{1}
X = A Z ,
\end{equation}
其中 Z=[z1,z2,⋯,zn]Z = [z_1, z_2, \cdots, z_n] 是係數矩陣,每一個 ziz_i 表示一個 xix_i。字典通常是過飽和的,為了使方程有解。

2.1 半監督有約束 LRR

加入標籤資訊作為約束,資料 XX 有 nn 個訓練樣本,設定前 ss 個資料 {x1,⋯,xs}(s≤n)\{x_1, \cdots, x_s\} (s \leq n) 有標籤表示,而剩餘的 n−sn-s 個資料 {xs 1,⋯,xn}(s≤n)\{ x_{s 1}, \cdots, x_n \}(s \leq n) 沒有標籤。假設一共有 cc 個類別,並且資料 {x1,⋯,xs}\{x_1, \cdots, x_s\} 中都有類別標籤,那麼就有一個 c×sc \times s 的指示矩陣 SS,表示為

spq={1,0,if xq is designated the pth class,otherwise,(2)

\begin{equation} \tag{2}
s_{pq} = \begin{cases}
1, & \text{if } x_q \text{ is designated the pth class}, \\
0, & \text{otherwise},
\end{cases}
\end{equation}
有了這個指示矩陣 SS,標籤約束矩陣 HH 可以定義為

H=(Δ(n−s c)×nO(s−c)×n),(3)

\begin{equation} \tag{3}
H = \begin{pmatrix}
\Delta_{(n-s c) \times n} \\
O_{(s-c) \times n} \\
\end{pmatrix},
\end{equation}
其中 O(s−c)×nO_{(s-c) \times n} 是一個 (s−c)×n(s-c) \times n 的零矩陣,和

Δ=(Sc×s00In−s),(4)

\begin{equation} \tag{4}
\Delta = \begin{pmatrix}
S_{c \times s} & 0 \\
0 & I_{n – s} \\
\end{pmatrix},
\end{equation}
其中 In−sI_{n – s} 是一個 (n−s)×(n−s)(n-s) \times (n-s) 的單位矩陣。HH 作為標籤資訊的約束加入,

X=AHZ=A⎛⎝⎜Sc×s000In−s0⎞⎠⎟n×nZ.(5)

\begin{equation} \tag{5}
X = A H Z = A \begin{pmatrix}
S_{c \times s} & 0 \\
0 & I_{n – s} \\
0 & 0 \\
\end{pmatrix}_{n \times n}
Z.
\end{equation}

2.2 標籤約束 LRR

觀測到的資料通常是有噪聲的。所以,獲得低秩的資料表示可以被認為是恢復出低秩的資料矩陣 XX,還有稀疏的誤差 EE。接著,將原始的 LRR 擴充套件到一個半監督的演算法,LCLRR,求解 ZZ 通過如下的優化問題:

minZ,E rank(Z) λ||E||2,1s.t. X=AHZ E,(6)

\begin{equation} \tag{6}
\min_{Z,E} \ \text{rank} (Z) \lambda || E ||_{2,1} \quad \text{s.t.} \ X = A H Z E ,
\end{equation}
其中引數 λ>0\lambda > 0 用於平衡兩項的比例,經驗性賦值。範數 ||E||2,1=∑nj=1∑mi=1([E]ij)2−−−−−−−−−−−√|| E ||_{2,1} = \sum_{j=1}^{n} \sqrt{\sum_{i=1}^{m} \left( [E]_{ij} \right)^2} 用於描述稀疏誤差 EE 。然而,求解該問題是 NP-hard,因為 rank 函式的離散性質。然而可以其可以鬆弛為一種凸優化問題 9

minZ,E ||Z||∗ λ||E||2,1s.t. X=AHZ E,(7)

\begin{equation} \tag{7}
\min_{Z,E} \ || Z ||_* \lambda || E ||_{2,1} \quad \text{s.t.} \ X = A H Z E ,
\end{equation}
其中 ||⋅||∗||\cdot||_* 是核範數,定義為矩陣的奇異值之和。原始的 LRR 問題用 増廣 Lagrange 乘子法求解。於是,此文使用經典的 inexact ALM 方法求解,過程與 LRR 10 類似。

首先,加入輔助變數 JJ,使得目標函式可分

minZ,J,E ||J||∗ λ||E||2,1s.t. X=AHZ E, Z=J,(8)

\begin{equation} \tag{8}
\min_{Z,J,E} \ ||J||_* \lambda ||E||_{2,1} \quad \text{s.t.} \ X = A H Z E , \ Z = J,
\end{equation}
然後,將約束優化問題轉化為無約束的 Lagrangian 函式

L(Z,J,E,Y1,Y2)=||J||∗ λ||E||2,1 YT1(AHZ E−X) YT2(J−Z) μ2(||AHZ E−X||2F ||J−Z||2F)=||J||∗ λ||E||2,1 12μ(||Y1||2F ||Y2||2F) μ2(||X−AHZ−E Y1/μ||2F ||Z−J Y2/μ||2F),(9)

\begin{align}
\mathcal{L}(Z, J, E, Y_1, Y_2) &= ||J||_* \lambda ||E||_{2,1} Y_1^T (AHZ E – X) Y_2^T (J – Z) \frac{\mu}{2} \left( ||AHZ E – X||_F^2 ||J-Z||_F^2 \right) \\
&= ||J||_* \lambda ||E||_{2,1} \frac{1}{2\mu}\left( ||Y_1||_F^2 ||Y_2||_F^2 \right) \frac{\mu}{2} \left( ||X – AHZ – E Y_1/\mu||_F^2 ||Z-J Y_2/\mu||_F^2 \right) , \tag{9}
\end{align}
其中 Y1,Y2Y_1, Y_2 是 Lagrange 乘子,μ>0\mu > 0 是懲罰引數。完整的演算法過程總結於 Algorithm 1 中。


Algorithm 1: LCLRR

Input: X, H, λX,\ H,\ \lambda;
Initialize: Z=0, J=0, E=0, Y1=0, Y2=0, μ0=10−7, μmax=1030, ρ=1.1, ϵ=10−10, k=0.Z=0,\ J=0,\ E=0,\ Y_1=0,\ Y_2 = 0, \
\mu_0=10^{-7},\ \mu_\max=10^{30},\ \rho=1.1,\ \epsilon = 10^{-10}, \ k=0.
1: While not convergednot \ converged do
2: 更新 Jk 1J_{k 1}

Jk 1=argminJ ||J||∗ μ2||J−(Z Y2μ)||2F .(10)

\begin{equation} \tag{10}
J_{k 1} = \arg\min_J \ ||J||_* \frac{\mu}{2} || J – (Z \frac{Y_2}{\mu}) ||_F^2 \ .
\end{equation}
3: 更新 Zk 1Z_{k 1}

Zk 1=(HTATAH I)−1(J HTAT(X−E) (HTATY1−Y2)/μ) .(11)

\begin{equation} \tag{11}
Z_{k 1} = (H^T A^T A H I)^{-1} (J H^T A^T (X – E) (H^T A^T Y_1 – Y_2) / \mu) \ .
\end{equation}
4: 更新 Ek 1E_{k 1}

Ek 1=argminE λ||E||2,1 μ2||E−(X−AHZ Y1μ)||2F .(12)

\begin{equation} \tag{12}
E_{k 1} = \arg\min_E \ \lambda ||E||_{2,1} \frac{\mu}{2} || E – (X – AHZ \frac{Y_1}{\mu}) ||_F^2 \ .
\end{equation}
5: 更新 Y1,Y2Y_1, Y_2

Yk 11=Yk1 μk(X−AHZk 1−Ek 1), Yk 12=Yk2 μk(Zk 1−Jk 1).(13)

\begin{equation} \tag{13}
Y_1^{k 1} = Y_1^k \mu_k (X -AHZ_{k 1} – E_{k 1}), \ Y_2^{k 1} = Y_2^{k} \mu_k (Z_{k 1} – J_{k 1}) .
\end{equation}
6: 更新 μk 1=min(ρμk, μmax)\mu_{k 1} = \min(\rho\mu_k,\ \mu_\max).
7: 檢查收斂條件 ||X−AHZk 1−Ek 1||∞<ϵ, ||Zk 1−Jk 1||∞<ϵ || X-AHZ_{k 1} – E_{k 1} ||_\infty < \epsilon, \ || Z_{k 1} – J_{k 1} ||_\infty < \epsilon .
8: k=k 1k = k 1 .
9: End While
Output: Z, J, EZ,\ J,\ E .


2.3 標籤約束稀疏 LRR

為了獲得稀疏的資料表示,加入了稀疏正則項於 ZZ 。於是,將 LCLRR 擴充套件到了 LCSLRR (label constrained sparse low-rank representation),其優化問題的形式如下

minZ,E rank(Z) β||Z||0 λ||E||2,1s.t. X=AHZ E,(14)

\begin{equation} \tag{14}
\min_{Z,E} \ \text{rank}(Z) \beta ||Z||_0 \lambda || E ||_{2,1} \quad \mathrm{s.t.} \ X = AHZ E,
\end{equation}
其中 β>0\beta > 0 是平衡 rank 項和稀疏項的比例。||⋅||0||\cdot||_0 表示 ℓ0\ell_0 範數,計算矩陣中非零項的個數。由於其非凸性質,用 ℓ1\ell_1 範數代替 ℓ0\ell_0 範數,核範數代替 rank 函式。於是,就得到了

minZ,E ||Z||∗ β||Z||1 λ||E||2,1s.t. X=AHZ E,(15)

\begin{equation} \tag{15}
\min_{Z,E} \ ||Z||_* \beta ||Z||_1 \lambda || E ||_{2,1} \quad \mathrm{s.t.} \ X = AHZ E,
\end{equation}
其中 ||⋅||1||\cdot||_1 是計算矩陣所有元素的絕對值之和。首先加入一個輔助變數 WW,使得目標函式可分,問題轉化為

minZ,E ||Z||∗ β||W||1 λ||E||2,1s.t. X=AHZ E, W=Z.(16)

\begin{equation} \tag{16}
\min_{Z,E} \ ||Z||_* \beta ||W||_1 \lambda ||E||_{2,1} \quad \text{s.t.} \ X = AHZ E, \ W = Z .
\end{equation}
將其轉化為如下的無約束 Lagrangian 函式,

L(Z,W,E,Y1,Y2)=||Z||∗ β||W||1 λ||E||2,1 12μ(||Y1||2F ||Y2||2F) μ2(||X−AHZ−E Y1/μ||2F ||Z−W Y2/μ||2F).(17)

\begin{align}
\mathcal{L}(Z, W, E, Y_1, Y_2) &= ||Z||_* \beta ||W||_1 \lambda ||E||_{2,1} \frac{1}{2\mu}\left( ||Y_1||_F^2 ||Y_2||_F^2 \right) \\
& \quad \frac{\mu}{2} \left( ||X – AHZ – E Y_1/\mu||_F^2 ||Z-W Y_2/\mu||_F^2 \right) . \tag{17}
\end{align}
將二次項 h=μ2(||X−AHZ−E Y1/μ||2F ||Z−W Y2/μ||2F)h = \frac{\mu}{2} \left( ||X – AHZ – E Y_1/\mu||_F^2 ||Z-W Y_2/\mu||_F^2 \right) 使用上一次迭代的一階近似代替,再加上一個逼近項 11,接著給出變數 Z,W,EZ,W,E 的更新公式

Zk 1Wk 1Ek 1=argminZ ||Z||∗ ημk2||Z−Zk [−(AH)T(X−AHZk−Ek Y1,kμ) (Z−Wk Y2,kμ)]/η||2F ,=argminW β||W||1 μk2||Zk 1−W Y2,kμ||2F ,=argminE λ||E||2,1 μk2||E−(1μkY1,k X−AHZk 1)||2F ,(18)(19)(20)

\begin{align}
Z_{k 1} &= \arg\min_Z \ ||Z||_* \frac{\eta\mu_k}{2} || Z – Z_k \left[ – (AH)^T \left(X – AHZ_k – E_k \frac{Y_{1,k}}{\mu} \right) \left(Z – W_k \frac{Y_{2,k}}{\mu} \right) \right] / \eta ||_F^2 \ , \tag{18} \\
W_{k 1} & = \arg\min_W \ \beta ||W||_1 \frac{\mu_k}{2} || Z_{k 1} – W \frac{Y_{2,k}}{\mu} ||_F^2 \ , \tag{19} \\
E_{k 1} & = \arg\min_E \ \lambda ||E||_{2,1} \frac{\mu_k}{2}|| E – \left( \frac{1}{\mu_k} Y_{1,k} X – AHZ_{k 1} \right) ||_F^2 \ , \tag{20}
\end{align}
原文中的 ∇Zh\nabla_Z h 是 hh 關於 ZZ 的偏導,η=||A||22\eta = ||A||_2^2,公式中並沒有用到這個符號,而且 η\eta 也不清楚是怎麼求出來的。**Algorithm 2 給出了 LCSLRR 演算法。


Algorithm 2: LCSLRR

Input: X, H, λ, βX,\ H,\ \lambda, \ \beta;
Initialize: Z=0, W=0, E=0, Y1=0, Y2=0, μ0=10−7, μmax=1030, ρ=1.1, ϵ=10−10, η=||A||22, k=0Z=0,\ W=0,\ E=0,\ Y_1=0,\ Y_2 = 0, \
\mu_0=10^{-7},\ \mu_\max=10^{30},\ \rho=1.1,\ \epsilon = 10^{-10}, \ \eta = ||A||_2^2, \ k=0.
1: While not convergednot \ converged do
2: 固定 W,EW,E,更新 Zk 1Z_{k 1};
3: 固定 Z,EZ,E,更新 Wk 1W_{k 1};
4: 固定 Z,WZ,W,更新 Ek 1E_{k 1};
5: 更新 Y1,Y2Y_1, Y_2

Yk 11=Yk1 μk(X−AHZk 1−Ek 1), Yk 12=Yk2 μk(Zk 1−Wk 1).

\begin{equation}
Y_1^{k 1} = Y_1^k \mu_k (X -AHZ_{k 1} – E_{k 1}), \ Y_2^{k 1} = Y_2^{k} \mu_k (Z_{k 1} – W_{k 1}) .
\end{equation}
6: 更新 μk 1=min(ρμk, μmax)\mu_{k 1} = \min(\rho\mu_k,\ \mu_\max).
7: 檢查收斂條件 ||X−AHZk 1−Ek 1||∞<ϵ, ||Zk 1−Wk 1||∞<ϵ || X-AHZ_{k 1} – E_{k 1} ||_\infty < \epsilon, \ || Z_{k 1} – W_{k 1} ||_\infty < \epsilon .
8: k=k 1k = k 1 .
9: End While
Output: Z, W, EZ,\ W,\ E .


2.4 標籤約束低秩圖構建

一般選擇資料 X 自身作為字典,來學習最低秩的表達。獲得了最優解 Z∗Z^*,可以構建一個加權的無向圖 G=(V,E)G=(V,E) 和權值矩陣 W=wijW = w_{ij} 來定義圖的關係矩陣。資料向量對應的頂點集 V={vi}ni=1V=\{v_i\}_{i=1}^n,每一個節點 viv_i 對應一個資料 xix_i 。E=eijE = e_{ij} 是邊集,wijw_{ij} 是連線節點 viv_i 和 vjv_j 的權值。因為頂點已經有資料向量給出了,構建圖的問題關鍵在於確定權值矩陣 WW 。之後確定權值矩陣 W=(|Z∗^| |Z∗^|T)/2W = \left( |\hat{Z^*}| |\hat{Z^*}|^T \right)/2 。

實際問題中,用資料 XX 作為字典是很不適用的。改進的辦法是用一個字典 DD 代替 XX,字典的元素是已經校正過的資料,其維度與 HH 一致。

這裡提到的構建一個圖模型,此文中一個例圖都沒有給出?

3 實驗

用了多個資料集 Yale B, PIE, USPS, ORL, AR,都統一用表格的形式給出準確率的對比。略


  1. Liu, G., Lin, Z., Yu, Y.: Robust subspace segmentation by low-rank representation. Mach. Learn. pp. 663–670 (2010)
  2. Du,H., Hu,Q., Qiao,D., et al.: Robust face recognition via low-rank sparse representation-based classification. Int. J. Autom. Comput. 12(6), 579–587 (2015)
  3. Shen, X.,Wu, Y.: A unified approach to salient object detection via low rank matrix recovery. IEEE Conference on Computer Vision and Pattern Recognition pp. 853–860 (2012)
  4. Cui, X.,Huang, J.,Zhang, S., Metaxas, D.:Background Subtraction Using Low Rank and Group Sparsity Constraints. Springer, Berlin (2012)
  5. Zhang, T., Ghanem, B., Ahuja, N.: Low-rank Sparse Learning for Robust Visual Tracking. Springer, Berlin (2012)
  6. Lee, J., Shi, B. ,Matsushita,Y., Kweon, I., Ikeuchi,K.: Radiometric calibration by transform invariant low-rank structure. IEEE Conference on Computer Vision and Pattern Recognition, pp. 2337–2344 (2011)
  7. He, R., Zheng, W.S., Hu, B.G., Kong, X.W.: Nonnegative sparse coding for discriminative semi-supervised learning. IEEE Conference on Computer Vision and Pattern Recognition, pp. 792–801 (2011)
  8. Zhuang, L., Gao, H., Lin, Z., Ma, Y., Zhang, X., Yu, N.: Nonnegative low rank and sparse graph for semi-supervised learning. IEEE Conference on Computer Vision and Pattern Recognition pp. 2328–2335 (2012)
  9. Candés, E.J.,Li, X.,Ma,Y.,Wright, J.: Robust principal component analysis? JACM 58(3) (2011)
  10. Liu, G., Lin, Z., Yu, Y.: Robust subspace segmentation by low-rank representation. Mach. Learn. pp. 663–670 (2010)
  11. Lin, Z., Liu, R., Su, Z.: Linearized alternating direction method with adaptive penalty for low rank representation. In NIPS (2011)