機器學習中的優化方法

此講義的部分內容取材於Jure Leskovec教授，Emmanuel Candes』s教授以及Yi Ma教授的課件

大家可能知道機器學習和最優化理論有著緊密的聯繫。今天我們從幾個具體的問題出發，具體講一下，在機器學習裡面有哪些優化模型，可以用哪些優化演算法進行求解。

我們首先看一道「小學奧數題」：在一串數列中有一個紅色的問號。大家可以用三十秒的時間找找規律，看看這個紅色的問號所對應的數字應該是多少。

如果大家沒有答案的話，我給一個提示：將這些數字換一個順序排列起來。

現在規律非常清楚了。第一行是1、2、3，第二行後兩個數是6和9。6是2的3倍，9也是3的3倍，很顯然，問號這裡對應的應該是1的3倍，也就是3。如果我們用高等數學的知識來解釋。第二行是第一行的3倍，第三行是第一行的7倍，所以這個矩陣秩為1，而這個矩陣秩1是我們能猜出數字的關鍵性質。那麼我們做這個矩陣猜字謎遊戲有什麼實際意義呢？

如果我們把矩陣的行和列加上一些標籤，就得到了一個新的矩陣。

可以看到，這個矩陣的行和列分別對應了一些人名和電影名，矩陣里的數值代表某個人對某部電影的打分。那麼，這個矩陣的第一列第一行的數字是3，表示Alice對X-Men這部電影的打分是3。我們還看到，這個矩陣有些數值是「？」，代表出於某些原因這個人沒有對這部電影進行打分。例如，Chris對Yellow Rock這個電影沒有打分，所以是「？」，David對Zoolander這部電影也沒有打分，也是「？」。

猜出「？」所對應的數值，就是推薦系統要做的事情。如果我們猜到了這個人對某個產品的打分，我們就知道這個人對這個產品的喜好程度（雖然他並沒有進行購買）。如果評分好，就可以推薦給他，他就很有可能去購買這個產品，從而提高公司的盈利。

現在推薦系統應用得非常廣泛，在國外，比如亞馬遜、Google、YouTube都有。國內的很多購物平台、視頻網站、門戶網站，都會在不同的地方推薦一些商品。這都是推薦系統應用的體現。

與推薦系統相關的一個著名事件就是The Netflix Prize。

具體來說，Netflix公司在2008年發起了一個競賽，獲獎者可以得到100萬美金的獎勵。獲獎的條件是，你要在2700多個參賽隊里拿到第一名。只拿到第一名還不行，你的結果還需要比Netflix公司原有系統Cinematch跑出的結果準確率高10%。這個問題其實就是我們剛才提到的，顧客給電影打分的例子。

在這個問題中，Netflix公司提供了2000年-2005年這6年的數據供訓練。共有大概48萬用戶，1萬7千多部電影，總共有1億個rating（打分值）。也就是說我們有一個48萬行，1萬7千列的矩陣，在這個矩陣中，我們知道了1億個元素的值。經過簡單計算，但這個矩陣總元素個數大約是100億個。可以看出我們已知數據是整個矩陣數據的百分之一。我們的任務就是要把那些未知的分數值都給猜出來。

那麼如何去衡量打分結果的好壞呢？Netflix公司保留了一個測試集，有280萬個rating不公開給參賽者,我們是不知道的。如果我們預測 這個人對第 部電影打分的情況是 ，並且其真實的打分值是 ，兩項相減取平方後就可以看成是他們的誤差。然後再對所有預測值的誤差求和後開根號，就得到一個綜合的分數。我們能看到Netflix自己的系統Cinematch的得分是0.9514。這個數越小的話表現我們的誤差越小，猜的越准，表現越好。

上圖是Netflix所提供數據的示意圖。即我們得到一個很大的矩陣，橫坐標有48萬個用戶，縱坐標是1萬7千多部電影，裡面的數字是已知的打分情況。灰色部分是Netflix的測試集，問號是我們要猜的數。

這個問題如何進行求解呢，首先我們要建模。

我們要注意到一個事情，電影由很多元素構成。我們打開某個電影網站，會發現電影是按照國家或地區分類的，比如美國電影、大陸電影、香港電影等等十個左右；也可以按類型來分類，也有恐怖片、愛情片、科幻片等十個左右分類。

比如一部成龍的電影，我們可以說它是武打片，也可以說是喜劇片，那麼可以說它是武打片的權重佔百分之五十，喜劇片的權重佔百分之五十。左圖中items每一行表示每一個類型所佔的權重，比如標紅的0.5、0.6、0.5表示把電影進行特徵分解的話，在比如喜劇、愛情、故事片這三個元素上所佔的權重分別是這麼多。

另一方面，用戶對電影類型的偏好也不一樣。年輕人可能比較喜歡科幻的、浪漫的電影，對這類電影打分比較高。老一輩人可能更喜歡革命電影，故事片。在右圖中，標紅的這一列，可以表示不同的用戶對不同類型電影的喜好程度也不一樣。

左邊的一行是第 部電影在不同元素的佔比，右邊的一列對應的是 個人對不同類型電影的喜好程度。那麼這一行與這一列對應的元素相乘再求和的話，得到的就是第 個人在第部電影上打分的情況。這就是Latent Factor Model。

上圖是我們建立的模型。 是上述解釋的第 個人給第 部電影上的評分，通過對比訓練集上已知的分數值，我要最小化這個誤差，這就是我的優化模型。在這裡 和 可以看成是人和電影的因子。對每個因子，我們不希望 和 波動比較大，這樣容易產生過擬合。為了防止這種現象發生，我們又加入一些二模平方的正則函數。最後得到的這個模型是光滑的、無約束的。對這樣一個無約束的問題，我們可以用梯度下降法進行求解，每步迭代對 和 進行更新。要實現這個演算法，那麼就要去求目標函數的梯度。

上圖 有梯度的表達式，包含很多的求和項，把要所有的 和 相加，計算量會比較大。一個巧妙的方法是對求和項用某種無偏的採樣，這樣不用對所有項進行求和。這就是大名鼎鼎的隨機梯度演算法，當採樣算出的梯度與真實的梯度誤差比較小的話，我們仍然有一些收斂性的結果。下面，我們來看一下這個模型的效果。

一些簡單取平均的數的方法，比如User average和Movie average都是1出頭一點。Netflix自己模型的得分是0.9514， Latent Factors是0.90，如果與其他模型結合，結果會有提升。比如把biase、時間等因素都考慮進去，分數會緩慢提高。但是要拿到這個獎，需要小於0.8563，仍然是一件不太好做的事情。

下面，我們接著把這個故事講完。

在這個比賽還剩下30天結束的時候，有一個叫BellKor的隊伍在所有隊伍中排第一。但是這個比賽的規則是只有第一名可以得到100萬獎金，所以第二名和最後一名沒有任何差別。在這樣的賽制下，排名靠前的其他一些隊伍聯合了起來，把各自的模型整合在一起，組成了一個新的隊伍叫Ensemble。從我們前一張PPT可以看出，我們的Latent Factors模型得分是0.90，但是如果和其他模型整合在一起的話，會提高輸出結果的準確性。這個Ensemble隊將模型整合後，確實發現分數提高了10%。

這個比賽提交的時間也是有講究的，每個隊每天只能提交一次作為當天的結果。如果兩個隊成績一致，則是較早提交的那個隊伍贏得勝利。在比賽的最後一天，BellKor有意在比賽結束前的40分鐘提交了結果，Ensemble則是在比賽結束前的20分鐘提交。

最後，兩個隊提交的結果得到的分數都是0.8567，都超過了10%的改進幅度，可以獲獎了。但Ensemble隊伍因為晚提交了20分鐘，錯失了100萬美金。這個故事到這裡就講完了。

從這個故事裡我們可以看到，優化模型及其演算法在機器學習中的應用。具體地，我們用到了Latent Factors模型；我們用了一些優化的演算法，比如梯度下降法，隨機梯度下降法。由此可見，優化和機器學習聯繫非常緊密。

那麼，在運籌優化的社區里，我們是如何研究推薦系統這件事情呢？

把剛才的案例抽象一下。我給定一個矩陣，藍色X表示數值已知的元素，紅色的問號表示未知的元素。我們要做的事情就是未知元素對應的數值準確地猜出來。這在優化領域裡叫做Matrix Completion，翻譯過來叫做矩陣補全問題。

我們剛才對Netflix問題進行求解的時候，其實就是在做矩陣分解，把原矩陣分解為兩個矩陣的乘積。矩陣 的列數和矩陣 的列數分別對應影片類別或者類型的個數，而我們知道電影的類別和類型的總數不會太多，所以列數是20、30行已經很了不起了。但是行數（即電影數量）有48萬個這麼多，是非常長的矩陣。這導致兩個矩陣乘出來之後的秩非常低。低秩表示這個矩陣的數值非常有規律性，從而比較好猜。這也是我們的演算法能工作的原因。

所以把這個規律總結起來就是，我們要去找一個矩陣，使得這個矩陣的秩很低，同時滿足求出的矩陣與我們觀測到的信息（即已知矩陣元素的數值）匹配。我們可以建這樣一個優化模型，最小化我們的秩，同時滿足一些線性約束。很遺憾的是這個問題是NP困難的問題，沒有多項式時間的演算法。那麼我們怎樣去求解呢？

我們可以將它轉化成一個關於核模的極小化問題。

一個矩陣 的核模是說把 做一個奇值分解（ 是它的奇值），然後把所有的奇值加起來。為什麼用核模的函數去代替原問題的秩函數呢? 是因為它是最接近秩函數的一個凸函數，在優化里比較容易求解。所以我們可以把它變成這樣一個問題。

這是一個半定規劃問題，變數是 和 。這也是一個比較容易求解的問題，因為我們的目標函數關於 是線性的，映射 也是線性的映射。所以我們可以調用一些現成的求解器來進行求解。比如用CVX（這個工具包里含有SDPT3,SeDuMi等多個SDP求解器），寫幾行很簡單的代碼就可以解出來。

雖然CVX可以進行求解，但是我們當矩陣的維數變大到100x100時，CVX的求解的速度就變得比較慢了。這是因為我們對SDP的主要求解方法是內點法，每步迭代涉及到矩陣求逆等運算。它這個速度比較慢，時間複雜度大概是N的3次方。所以我們要設計其他演算法進行求解。

在上圖中我們看這樣一個優化問題，目標函數仍然是最小化核模，但是把線性約束的平方作為罰函數放到目標函數里，這樣我們只需要這個線性近似滿足。這個問題雖然是凸的，但仍然不好直接求解。這裡我們對目標函數中的二次項進行線性化，其中 代表該二次項 在這一點的導數。另外我們還補上一個關於 的二次函數，其中二次項的係數關於 為「1」（這裡其實是一個單位矩陣，會給接下來的運算帶來很大的好處）。新加的這個二次函數可以控制下一步迭代點離 不會太遠。

可以通過數學推導發現上述子問題的解有一個顯式表達。這裡 是未知變數， 是已知參數。具體來說，我們可以對 做一個奇值分解，然後把 和 留下來。對中間的奇異值 做截斷，然後再把截斷後的奇值放回矩陣分解中，就得到了該問題的解。

我們可以把上述問題一般化，得到一個更廣的數學表達式。即目標函數是一個凸的可微的函數加上另一個凸的不可微的函數。同樣在演算法裡面我們對可微的部分線性化，進行迭代。演算法中的子問題其實是一個Proximal Mapping，中文叫鄰近映射。

它對於很多問題比如之前提到推薦系統中對X求核模的子問題有顯式解，著名的Lasso問題也有顯式解。我們可以證明它的收斂速度是1/k，其中k表示演算法的迭代步數，1/k表示解的精度。1/k的收斂速度意味著如果這個演算法跑100步，解的精度就是0.01。

那麼我們能不能在同樣條件下把收斂速度提高呢？這就是所謂的「加速」，機器學習領域的學者們也很重視加速演算法。最早的加速演算法是Neserov在1983年的一篇俄文文獻中提出的，收斂速度可以達到到1/k 。剛才說1/k的收斂速度意味著如果這個演算法跑100步，解的精度就是0.01。那麼如果是1/k 的速度，花費同樣的迭代步數，解的精度可以達到萬分之一，所以提高幅度還是很大的。在Neserov的工作後，Beck和Teboulle於09年也提出了類似的演算法，影響力很大，不同之處是他們可以處理非光滑的目標函數。他們的演算法考慮了兩個點列，一個是{ }一個是{ }。那麼是怎麼出來的呢？它是{ }這個點列，前兩步迭代點 和 的線性組合。

下面我們看一下矩陣補全模型在生物信息學中的應用。

這是是DNA的雙螺旋結構的示意圖，連接兩個鏈的彩色物體是鹼基對。我們知道，人與人之前大部分的鹼基對的對應情況是一樣的，但是會有少部分有差異。

研究每個基因到底有什麼樣的功能是當前的一個熱門課題。而搞清楚染色體中各位置基因的情況是基礎。隨著人類技術的進步，人們研究使用的機器也在發生變化，影響到讀出的結果也有所不同。

我們可以把染色體中基金的情況轉化成數字後得到上圖。圖中藍色、綠色、黃色的部分分別代表不同機器讀出的結果。可以看出，每種機器都是只能讀出染色體中部分基因的信息。那麼如何把這些數據都用起來呢？把這些數據都拼起來其實就得到一個矩陣，我們要去猜機器沒有讀出的信息（即問號位置對應的數值），這就回到了矩陣補全的問題。我們看一下優化演算法對這個問題的效果。

我們用了兩種優化演算法，結果發表在綜合類期刊《Scientific Reports》上。

第一張表格是各種演算法的對比,前三行是在生物信息學中已有演算法得到的結果，後面幾行是我們的結果，其中有一個和他們最好的演算法精度接近，其他幾個結果精度稍微差一些。但從時間上看（第二張表格），後面幾個演算法雖然精度差一些，但是運行時間有很大提升。

矩陣是二維的數組，張量是高維的數組，矩陣補全模型還可以推廣到更高維的張量中去。我們生活中什麼數據能寫成張量呢？比如這裡的彩色視頻，其實是能寫成張量的。

我們知道一個視頻能動起來的話，每秒至少要播24幀圖像。PPT里截出了視頻中的三幀，可以看到視頻的維度包括行、列，顏色、還有時間，是一個四維的張量。為了將矩陣補全演算法應用到張量問題上，我們需要做一些變形。

具體來說，就是將張量以某種形式轉化成矩陣，然後再求助矩陣的演算法。轉換的細節我們有論文進行討論，這裡就不細說了。

下面是實驗結果。第一張PPT里，如果我們「挖去」了百分之二十的數據，看起來恢復得還不錯。

如果百分之五十被「挖去」的話也能恢復出來。

如果缺失的數據量進一步上升到了百分之八十的話，也能恢復，不過顏色是有誤差的。具體來說，缺失百分之五十數據的時候，恢復出來的花草還是綠色的，但是現在恢復出的花草就變黃了。可以看出，對於彩色視頻，我們這個演算法的工作極限大概就在這裡。

下面介紹另外一個應用，Robust PCA（在計算機視覺領域叫作前景後景分離）。

在上面這頁PPT中，第一張圖是原始數據表面有一些噪音。它其實可以分解為兩部分，即第二張圖和第三張圖之和。第二張圖的顏色排列得比較整齊、規律，可以看成一個低秩的矩陣。第三張是只保留了噪音部分，但與整個圖的面積相比，噪音部分的面積還是很小的，所以可以看成是一個稀疏的矩陣。總體來說，第一張圖所對應的矩陣可以看成一個低秩的矩陣加上一個稀疏的矩陣。

這項技術在視頻或圖像的前景後景分離中非常有用。我們可以把這個監視器里的不動的背景和行色匆匆的人物分離出來。

剛才那個彩色視頻也可以做同樣的實驗，我們取了另外幾幀圖像使得有個人在畫面中動。那麼通過我們的演算法，可以把動態的人也分離出來。

下面再回到我們抽象的優化模型。

我們把目標矩陣 做一個分解， 是低秩的部分， 是稀疏的部分。這個0模表示非0 元素的個數，要最小化。秩函數和0模函數都不好做優化，所以我們用核模函數和1模函數來分別近似秩函數和0模函數。

我們可以進一步抽象化得到下面更一般的數學模型。其中目標函數是兩個凸函數之和，然後有一個線性約束。

上述問題可以用大名鼎鼎的交替乘子法（Alternating direction method of multipliers簡稱ADMM）進行求解。具體地先將增廣拉格朗日函數寫出來，然後對x、y和拉格朗日乘子分別做迭代。迭代x和y時，對應的兩個子問題具有如下形式：

用ADMM去求解robust PCA問題，其兩個子問題都有顯示錶達，如下圖所示：

下面我們來看一個例子。這裡有棟建築，有部分區域被旗子和海報擋住了，我們要把它們去掉。左邊的圖是用低秩的方法得到的，右邊的圖是用Photoshop得到的。對比看一下，右圖在一些細節上（比如有幾扇窗戶）恢復得不太好。

我們還可以把模型用到一些街景圖上，依然是左圖用我們的演算法，右圖是用Photoshop得到的。左圖的恢復效果還是比右圖好一些。

我們來看最後一個圖像的例子。我們把同一個人在不同光線下，拍的52張照片放在一起，組成了一個大的矩陣。

我們可以看到，在不同光線情況下，拍出的照片都有瑕疵。比如右側圖像的第一列是原始照片，我們可以看到這個人眼睛上有紅點，鼻子上有反光，還有些陰影。我們可以用低秩分解的方法把這些不好的地方分離出來。處理過後，紅點、反光點都在最右邊的圖上顯示出來。

最後我們講一下ADMM演算法的理論性質。

具體來說對兩塊變數（即x和y）的問題，ADMM的收斂速度是1/k的。對多塊變數的話，以前一直不知道是否收斂，所以是個公開問題。一直到13年的時候，南京大學的陳采華、何炳生老師，香港浸會大學的袁小明老師以及斯坦福大學的葉蔭宇老師合寫了一篇論文，舉出一個反例說明了ADMM對多塊變數的問題不一定收斂。

這個例子非常簡單，是一個找線性系統的可行解問題。這個線性系統分為三塊。

在這個具體的問題中，ADMM的迭代格式是和某個矩陣的冪法迭代是等價的，收斂需要這個矩陣的譜半徑（即絕對值最大的特徵值）小於1。但是實際算一下，這個矩陣的譜半徑是大於1的，所以是發散的。這就給出了一個反例。

Ｑ＆Ａ

Q：在實踐中到底是APG快還是ADMM快？

A：APG指的是Beck和Teboulle他們的演算法。ADMM和APG解決的問題不一樣。APG中的約束是可以分離的，ADMM問題中的約束是不可分離的。因此不能作直接比較，不存在誰快誰慢的說法。但是對ADMM這個演算法，是有人考慮做加速的，這樣得到的理論結果沒有那麼好，不能證到1/k 的收斂速度。

Q：工程上，matrix completion主要用什麼方法？

A：推薦系統的話，國內用協同過濾演算法比較多，優化的人用Latent factors演算法比較多。Netflix那個隊伍是把幾個演算法放在一起用的。我感覺很難說用一個演算法就可以，往往都是要結合起來的。

Q：矩陣分解和矩陣還原對圖像去噪和圖像恢復的效果怎麼樣？

A：矩陣分解指是Latent factors模型，矩陣還原指的是核模最小化模型。我的經驗是，如果做圖像的話，Latent factors模型是比核模最小化要好。但在生物那個例子里，核模最小化要比Latent factors模型要好。我感覺這也是具體問題具體分析。Latent factors模型其實是一個非凸的問題，現在做矩陣分解大家都是用alternating direction，很難說我們收斂到全局最優解。不過現在也有人證明在一定的條件下，也能收斂到全局最優。

Q：如何獲得生物數據？

A：生物數據的話要找人合作，還要看合作者的實力。有些生物數據是公開的，網上申請就能得到。有些數據是實驗室跑出來的，沒有途徑就比較難拿。