原來解線性方程的時候方程數一定要多于未知量,參數矩陣 L 是長的,噪聲則用高斯的方法求個最小方差。這個方法有兩百年曆史。1756 年,Boscovich 提出,如果噪聲不是高斯的話,應該用一範數而不是二範數。有趣的是高斯是這篇文章的評審人,他評價道,「如果噪聲比較大的時候一範數的效果确實比較好。」當時這隻是一個想法,并沒有相應的理論。
今日頭條AI技術沙龍馬毅:低維模型與深度模型的殊途同歸
現在我們要應對的問題是,未知量遠比方程數多。以前處理這種問題的方法是等,天文學家可以等待十年隻為看到一個現象。現在大家等不及了,要從不全而且有損毀的資料中找到這種資訊。如何尋找呢?求解此類方程不幸是個 NP 困難的問題,是以之前沒人關注。然而常見的高維資料有稀疏的特點,即 x 不是所有次元都有值,隻有少數非零。大約十年前,陶哲軒和 Candès 發表了文章,發現這類方程在很寬松的條件下可以用一範數求解,算法是可在多項式時間内完成的(polynomial)。
解下方用一範數懲罰過的方程(其中 x 有稀疏要求),然後進行疊代。将上一次疊代算出的 x 帶入做一個線性變換,得到 w,w 經過一個軟門檻值函數(soft thresholding)後就得到這一次疊代的輸出 x,重複該過程直到收斂。熟悉深度學習的同學會發現,如果我把用詞改一改,把一次「疊代」叫做一個「層」,然後把這個疊代過程畫出來,我們得到的結構是線性算子加門檻值函數,而且門檻值函數的樣子和激活函數 ReLU 長得很像——這就是一個神經網絡。
今日頭條AI技術沙龍馬毅:低維模型與深度模型的殊途同歸
完全從模型推導出來的最優的、收斂速度最快的算法,和深度學習通過經驗找到的神經網絡非常相似。
這些理論可以被用于圖像處理。我們将人臉識别表示成一個線性方程,把一張人臉圖像表達為一個庫的線性疊加(x),把我表達不了的像素當成誤差剔除出去(e)。其中 x 和 e 都是未知的,未知量個數遠超過方程數。我們還将像素随機損毀,損毀 60% 的像素後,人已經無法對人臉進行識别,然而計算機仍然識别并實作接近百分之百的恢複。
理論的突破讓大家興奮了一陣子随即冷靜了下來:可計算并不等于實用。一張 1000*1000 的圖檔約一兆大小,D = A + E,A 和 E 都不知道時,這個優化問題的次元是兩百萬,而且目标函數不可導。傳統凸優化方法解幾百維的問題還好,數百萬維的問題,參數連存都存不下。是以隻能用一階算法,不能用二階算法。這和神經網絡是一樣的,你隻能用随機梯度下降(stochastic gradient descent)去訓練上千萬個未知量。
一階算法的問題是,雖然可擴充(scalable),但是收斂速度非常慢,大概要 1 萬次疊代才能收斂。是以我們首先想到特殊解:固定 A 求 E 和固定 E 求 A 都是有閉解的,我們利用臨近算子(proximal operator)做門檻值。我們在尋找一階算法的時候發現,80 年代的比 90 年代的快,70 年代的比 80 年代的快,最後最快的算法是 50 年代的 ADMM(Alternating Direction Method of Multipliers),而且現在訓練神經網絡的也是用 ADMM 做分布和并行。這些算法快是因為當年的算力有限,數學家們還拿着計算尺在做運算。現在模型強調越大越好越深越好,是因為資源豐富了,它并不在乎效率問題了,人工、時間、計算能力,都不計成本地投入。在傳統優化領域我們不是這樣做的,我們将 1 萬次疊代縮減到 20 次疊代。這就等價于原本要建 8000 層的神經網絡,現在用了 20 層就實作了。
最快的算法有什麼結構呢?它的資訊流為什麼如此有效呢?我們給 A 矩陣和 E 矩陣添加一個拉格朗日算子,強化 D = A + E 的限制條件。疊代過程也是線性變換和非線性門檻值計算。拉格朗日算子的更新過程和殘差神經網絡完全一樣。又一次,兩條完全不同的路通向了同一個結果:純由模型推導得出的、基于兩百年前拉格朗日發明的,有限制的優化問題(constrained optimization)得到的最有效的疊代算法和我們通過機器學習在大量的網絡結構中篩選,大浪淘沙,試各種超參數(hyperparameter)試出來的結構殘差神經網絡一模一樣。
從有部分測量缺失的結構化圖像中恢複低維結構:低秩紋理修複(Liang, Ren, Zhang, and Ma, in ECCV 2012);不同光線條件下立體結構修複(Wu, Ganesh, Li, Matsushita, and Ma, in ACCV 2010.);從視訊幀中做背景修複(Candès, Li, Ma, and Wright, JACM, May 2011.)等。
從有部分測量損壞的結構化圖像中恢複低維結構:從移動錄影機的圖像中得到全景(Panorama)(Zhou, Min, and Ma, in 2012)等。
從非線性形變和線性壓縮采樣中恢複低維結構:從旋轉、扭曲過的圖檔中提取幾何形狀和紋理(Zhang, Liang, Ganesh, Ma, ACCV'10, IJCV'12.);有徑向形變的相機位置校準、曲面形狀恢複(Zhang, Liang, and Ma, in ICCV 2011.);虛拟現實(Zhang, Liang, and Ma, in ICCV 2011);城市場景的整體三維重建(Mobahi, Zhou, and Ma, in ICCV 2011.);人臉檢測(Peng, Ganesh, Wright, Ma, CVPR'10, TPAMI'11);物體對正(Rectifying)(Zhang, Liang, Ganesh, Ma, ACCV'10 and IJCV'12.);超分辨率(Carlos Fernandez and Emmanuel Candes of Stanford, ICCV2013.)等。
在視覺領域之外,也有很多例子,比如:文本主題模組化,把文中的詞分為低秩主題「背景」和有資訊量的、有區分度的「關鍵詞」(Min, Zhang, Wright, Ma, CIKM 2010.);時間序列基因表達(Chang, Korkola, Amin, Tomlin of Berkeley, BiorXiv, 2014.);音頻中低秩的背景音和稀疏的人聲的分離(Po-Sen Huang, Scott Chen, Paris Smaragdis, Mark Hasegawa-Johnson of UIUC, ICASSP 2012.);網際網路流量資料異常檢測(Mardani, Mateos, and Giannadis of Minnesota, Trans. Information Theory, 2013.);有遮擋的 GPS 信号恢複(Dynamical System Identification, Maryan Fazel, Stephen Boyd, 2000.)等。