作者：邱陸陸
上周，今日頭條人工智慧實驗室在清華大學舉辦了第二期 AI 技術沙龍，邀請到上海科技大學信息科學與技術學院的馬毅教授帶來題為「高維數據的低維結構與深度模型」的主題分享。馬毅教授以計算機視覺為例，展示了低維模型和深度模型如何從不同角度試圖攻克同一個問題：高維數據的信息提取。並且詳細展示了從低維模型角度如何分解並逐步攻克這個問題，有哪些應用，以及低維模型如何給深度模型帶來可解釋性。以下為機器之心對講座內容進行的整理。
對於做機器學習，和做圖像視覺的研究者來說，過去的十年是非常激動人心的十年。以我個人來講，非常有幸接觸了兩件事情：第一件是壓縮感知（compressive sensing），高維空間的低維模型，利用其稀疏低秩的性質，帶來一場圖像處理的革命。第二件就是大家非常熟悉的深度學習。今天我以視覺為例，探討低維模型和深度模型如何為了一個共同的目的從兩個完全對立的方向走到了一起。
從結果來看，壓縮感知和深度學習都讓我們能在像素級別處理圖像的全局信息。而從方法論來看，這二者是互補的。壓縮感知完全基於模型（model-based），有很好的結構，經過嚴謹的數學建模。深度學習則完全反過來，模型非常靈活，需要通過數據進行監督學習，是一種基於實證的方法。更有趣的是，二者取得突破的原因也和方法論一樣完全對等。壓縮感知的突破來自數學純理論的突破，深度學習的突破則來自於應用和經驗，結果是都得到了同樣強大而可擴展的算法，而且其結構和流程都非常相似。
很多人覺得壓縮感知和深度學習是完全不同的東西，兩個領域的研究者互不理解。然而 CNN 的發明者 Yann LeCun 在深度學習流行起來之前就在做壓縮感知，自編碼器（autoencoder）就是從壓縮感知來的概念。今天我希望講解這二者螺旋發展的歷史過程，和大家分享一些經驗和教訓。
背景
大數據的「大」體現在兩個方面，量多、維度高。然而數據再大也不是隨機的，它們通過結構承載信息。高維數據並不填滿整個空間，由於存在特定的生成機制，其自由度其實很低。在圖像裡，這些特點是能被「看」到的：諸如對稱性、周期性這樣規律在圖像的局部和整體都有體現。
如何通過數學建模量化描述這些特點呢？舉個例子，把一張圖像用 100*100 的矩陣表示，線性代數告訴我們，周期性會使它的各列線性相關，矩陣的秩肯定比矩陣的規模小很多，可能只有 10。也就是說，如果你把每一列看成一個向量，看成一個 100 維空間中的點，當我們把這些點畫出來，會發現他們不是散布得到處都是，而是集中在某一個子空間中，這個子空間就是我們要找的低維結構。如果我的數據來自上述的低秩結構，哪怕加上一些高斯噪聲，我只需要對矩陣做做奇異值分解（SVD），把小的奇異值扔掉，就能得到包含的主要信息。這個過程在統計裡面也叫 PCA（主成分分析），有超過 100 年的歷史了。全世界計算機運行起來，大部分電費就花在做這件事上。谷歌的工作就是解線性方程、找特徵向量、算佩奇排名（PageRank）。這個方法的弱點在於不魯棒，如果矩陣中的數據有隨機損毀，算出來的子空間就會和真實情況（ground truth）差很遠，因此大家都在想辦法提高系統的魯棒性。
我們已經有了信號處理、信息理論，為什麼還要學習壓縮感知和深度學習？因為工程實踐變了。信息理論是上世紀五、六十年代的發明，那時候的工程實踐是由工程師掌控全過程的。工程師從布置傳感器採集數據開始參與全程，花了大量時間在降噪，如果行不通，就從數據收集開始重頭再來。但是現今的數據科學家面對的工程實踐條件完全不同，我們使用的數據極少有自己採集的，採集數據時也沒有目的性。因此數據中有大量的缺失、損毀、變形，使得原來的數據處理方法變得有局限乃至於失效。今天我們不能因為做人臉識別的時候遇到一位女士帶著墨鏡無法識別就把她找回來重新拍一張照片、不能因為做三維重建的時候樹擋住了建築物就把樹砍掉，我們要學會處理這樣不完美的數據。舊的方法行不通並不代表數據中不含有正確的信息，只不過需要我們發現新的理論和方法，從不完美的數據中把信息提取出來。
理論：稀疏和低秩的信息恢復
原來解線性方程的時候方程數一定要多於未知量，參數矩陣 L 是長的，噪聲則用高斯的方法求個最小方差。這個方法有兩百年歷史。1756 年，Boscovich 提出，如果噪聲不是高斯的話，應該用一範數而不是二範數。有趣的是高斯是這篇文章的評審人，他評價道，「如果噪聲比較大的時候一範數的效果確實比較好。」當時這只是一個想法，並沒有相應的理論。
現在我們要應對的問題是，未知量遠比方程數多。以前處理這種問題的方法是等，天文學家可以等待十年只為看到一個現象。現在大家等不及了，要從不全而且有損毀的數據中找到這種信息。如何尋找呢？求解此類方程不幸是個 NP 困難的問題，因此之前沒人關注。然而常見的高維數據有稀疏的特點，即 x 不是所有維度都有值，只有少數非零。大約十年前，陶哲軒和 Candès 發表了文章，發現這類方程在很寬鬆的條件下可以用一範數求解，算法是可在多項式時間內完成的（polynomial）。
解下方用一範數懲罰過的方程（其中 x 有稀疏要求），然後進行迭代。將上一次迭代算出的 x 帶入做一個線性變換，得到 w，w 經過一個軟閾值函數（soft thresholding）後就得到這一次迭代的輸出 x，重複該過程直到收斂。熟悉深度學習的同學會發現，如果我把用詞改一改，把一次「迭代」叫做一個「層」，然後把這個迭代過程畫出來，我們得到的結構是線性算子加閾值函數，而且閾值函數的樣子和激活函數 ReLU 長得很像——這就是一個神經網絡。
完全從模型推導出來的最優的、收斂速度最快的算法，和深度學習通過經驗找到的神經網絡非常相似。
這些理論可以被用於圖像處理。我們將人臉識別表示成一個線性方程，把一張人臉圖像表達為一個庫的線性疊加（x），把我表達不了的像素當成誤差剔除出去（e）。其中 x 和 e 都是未知的，未知量個數遠超過方程數。我們還將像素隨機損毀，損毀 60% 的像素後，人已經無法對人臉進行識別，然而計算機仍然識別並實現接近百分之百的恢復。
這個例子讓我們很震驚：在高維的世界裡，數據攜帶的信息是我們難以想像的魯棒的。有多魯棒呢？隨著圖像的解析度越來越高，你可以損毀的像素的比例可以無限接近百分之百。這是數學的神奇之處：我們本來只想要損毀一小部分像素，但得到了遠遠超出想像的結論。
這些理論剛出現的時候，陶哲軒等人都是不相信的。高維空間的統計和幾何現象和低維空間中發展的幾何和統計的直覺是完全相反的。你認為在低維空間一定會發生的事情在高維空間基本不發生，你認為在低維空間中絕對不會發生的事情往往在高維空間中以概率為 1 發生，即使世界一流的數學家在此也會犯錯，這是我們學到的極其寶貴的經驗。
我們也可以把一維的稀疏向量的上述性質擴展到二維的低秩矩陣：如何很少的特徵把矩陣表示出來？網際網路都靠解決這個問題吃飯。無論是淘寶還是臉書，都面臨著同一個的問題：我只有關於用戶的部分信息，我需要根據這些不完整的信息猜測一個人對一樣事物是否感興趣，有多感興趣。這就是一個矩陣恢復問題，我們要「把表填滿」。
有些同學可能會問，我們做深度學習的人為什麼要關注這個問題？因為這實際上是一個普遍的問題，不管你用任何方法，只要你想通過觀測來恢復隱藏節點，它的本質就會回到同一個問題：從低秩、稀疏的數據中找到信息。就像陶哲軒說過，「物理裡面有能量守恆，數學中有難度守恆。」你可以使用任何啟發式（heuristic）方法，但是核心必須是解決這個問題。什麼是低秩？就是模型的自由度少。什麼是稀疏？稀疏代表網絡為零的項特別多。所有為零的項都代表了網絡的條件獨立性（conditional independence）。
如何解決這個問題？與深度學習從應用到算法的路相反，還有一條從理論到算法再到應用的路。
我們把過程拆分為兩步：
第一，尋找矩陣的秩最小化這個 NP 困難的問題的可計算（tractable）條件。第二，在可計算的條件下尋找最快的、不能再優化的算法。
很長時間內，大家的辦法都是啟發式的，好用就是好用，也不知道為什麼好用。壓縮感知告訴我們，不要試圖最小化 0 範式，要最小化它的凸包（convex hull）。矩陣的秩的凸包就是它的核範數（nuclear norm），即奇異值的和，就像 0 範數的凸包就是 1 範數（絕對值的和）。最小化凸包問題是一個凸優化問題，可以證明，該問題可以用多項式算法完成
接下來就需要尋找凸優化的解和原問題的解在什麼條件下是一致的了。我們做了一些模擬，結果非常令人振奮。
下圖中，橫軸是秩佔矩陣規模的比例，縱軸是損毀比例，在不同的比例裡面我們多次求凸優化的解，看看凸優化的解和原問題的解是否一致。白色區域意味著所有模擬的解都一致，黑色區域代表所有模擬的解都不一致。之前我們認為整個區域都是黑的，這個 NP 困難的問題無法求解，結果發現了非常漂亮的相變過程，在曲線上，凸優化的解完全可用。而可用區域也剛好是工程實踐最關心的區域：數據確實有結構，損毀也沒那麼嚴重。
當矩陣的秩足夠小，同時損毀足夠少時，凸優化幾乎可以恢復任何矩陣。原來還要設定損毀的權重因子 λ 並交叉檢驗，現在做完數學分析後連 λ 都不用設，直接用 1/√m，整個算法沒有任何自由參數。對於任何一個凸函數，只有一個全局最小值，而且找到了就是最優解。同時我也不需要矩陣的全部信息，給我 10% 甚至更少的信息就夠了，隨著矩陣越大，需要的信息佔比就越小。能夠接受的損毀上限在哪裡？當誤差的符號是隨機的時候，隨著矩陣越來越大，可以損毀的比例接近 100%。當你的數據足夠高維，你幾乎可以隨意損毀，信息仍然在，而且可以用很魯棒的算法把信息都找到。
剛才的矩陣修復定理證明了下圖的綠線，傳統 PCA 是橫軸的紅線，模擬顯示，紅色曲線下方的區域都有效，但尚未有理論證明。
理論的突破讓大家興奮了一陣子隨即冷靜了下來：可計算並不等於實用。一張 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）試出來的結構殘差神經網絡一模一樣。
做深度學習的同學可能之前不知道為什麼深度神經網絡、殘差神經網絡這麼神奇，今天回去你可以理直氣壯地說：這不就是有約束優化問題嗎！我要找出的就是低維結構，而且這些結構一定滿足這些條件。拉格朗日算子就是要以這種方式更新，這就是最有效的方法。雖然不是很嚴格，低維模型為神經網絡的有效性提供了一個可能的解釋。
因此大家看文獻不要只看過去兩三個月的，人類的歷史這麼長，有太多寶貴的思路已經被想過了，太多高效的工具已經被發明過了。我們今天遇到的問題，前人們在控制領域、優化領域早就遇到過了，適用範圍不同，然而本質不變。
新的問題：為什麼收斂這麼快？它的收斂速度明明應該很慢，是 O(k^(-2))，為什麼 20 次迭代就夠了？Agarwal 證明了，我們對這一類問題在高維空間的認識又是有局限性的。在高維空間如果你的目標函數滿足限制性強凸條件（restricted strong convex），一階算法的收斂速度和二階算法的收斂速度一樣，就是指數的。
應用
上述理論有十分廣泛的應用。在視覺方面，有：
從有部分測量缺失的結構化圖像中恢復低維結構：低秩紋理修復（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.）等。
結論
稀疏和低秩是高維空間中一大類低維模型的兩個特例。事實上有一大類低維結構都有很好的性質，可以用很少的度量（measurement）很魯棒地恢復出來。這種結構的特性叫可分解性（decomposable）。
我們知道圖像是由小的元素組成的，它們可以分開也可以相加，然而大家還不清楚這些結構和圖像中實際的結構是如何對應的。從這個意義上來說，理論是超前於應用的，還需要大家繼續探索。
低維模型和深度神經網絡的聯繫
壓縮感知對深度學習的指導意義有以下這三個方面。
第一個問題，一層神經網絡能做什麼？最好能做到什麼程度？
Yann LeCun 最早做的 autoencoder 就是這個思路。給定一個數據（Y），如何找到一個一層的線性變換（Q），使得變換後數據（X）最稀疏、維數最低。信號處理就是找到傅立葉變換（FT）或離散餘弦變換（DCT）使得我的數據變得儘可能的可壓縮。
現在問題變成找到一個「黃金變換」，讓我的數據最可壓縮。這個問題的難點在於，這是一個非凸、非線性問題。Y ≈ Q * X，其中 Q 和 X 都不知道，而且通常對 Q 還有很多額外的結構上的要求（比如正交性）。之前的做法都是啟發式的，固定 Q 找 X 或者反過來。甚至很長時間大家認為找這樣的結構是沒有意義的：即使找到了 Q，所需的數據也是指數倍的。如果 Q 是一個 n*n 矩陣，X 的秩是 k，那麼 Y 需要的樣本數就至少是從 n 選 k，是一個 n 和 k 的指數倍量級。15 年，哥倫比亞的學者發現：第一，需要的數據不用指數倍，達到 n^3 即可，第二，稀疏程度小於 1/3，滿足上述兩條件的情況下，利用 70 年代的信賴域算法（Trust Region Method），就能保證找到全局最優的變換。
第二個問題，神經網絡如何找到全局最優解？
深度神經網絡可以分解為串聯的矩陣操作，14 年，CMU 的學者證明，如果你通過訓練找到的網絡參數足夠稀疏，那麼對於優化函數來說就是全局最優的。這就解釋了 Hinton 當年為什麼能通過 Dropout 讓深度神經網絡變得真正可用。可以看出稀疏矩陣和深度學習之間是有根本性聯繫的。
第三個問題，「深度」是神經網絡的必要條件嗎？淺層神經網絡的局限性在哪裡？
學控制的同學知道，控制有兩招：如果對系統了解得很透徹，用前置控制器（feedforward）即可；如果對系統的了解有很多誤差，則通過反饋（feedback）進行控制。把前饋和反饋用機器學習的語言表達，就是無監督學習和監督學習。
為了證明深度的必要性，我們打算先搭建一個最簡單的網絡結構 PCANet 做基線：兩層的 PCA 篩選器，激活函數用比 ReLU 還簡單的 Binary，並且直方圖統計（histogram）替代均值或者最大值池化輸出。結果很震驚：這個結構 15 年在 FERET 資料庫上成為了當前最佳（state-of-art）。
今年的 ICLR 最佳論文，伯克利和 MIT 的研究者就用了兩層神經網絡，加上核方法（kernel），不需要任何反向傳播，在 CIFAR10 上達到了和 ResNet 差一個點的效果，而他們的網絡實現起來只需要 3 分鐘，而 Inception 這種神經網絡至少需要一兩天。
結語與擴展
現在計算能力上來了，數據更多了，然而這隻代表我們有更豐富的資源了，什麼是處理海量高維數據真正有壁壘的技術，什麼樣的算法是可用的、可遷移的、可擴展的，才是值得我們思考的問題。
今天我們講了在一個子空間上如何魯棒地高效地尋找一個低維結構，如果數據分布在多個子空間，涉及到無監督學習，如何把數據分到不同子空間。這也是 Yann LeCun 等一系列學者所說的，機器學習的未來就是從監督學習到無監督學習。在效率上，強化學習的效率最低，每次實驗只生成一個比特的信息（成功、不成功），監督學習每一批大概總結幾十個比特的信息，非監督學習，要生成一張圖所需的信息量就非常大。如果能通過無監督的方法把結構找出來，算法的效率會大幅提高，計算的成本會大幅降低。如果未來機器學習以效率優先為目標，那麼一定會從監督學習到無監督學習，從深的模型到淺的模型，從大的模型到小的模型，從大的數據到小的數據。
愛因斯坦說，「Everything should be made as simple as possible, but no simpler.」。這是科學和工程領域共同的奮鬥目標：深刻的應該是我們對問題的理解，而不是模型本身。