本文根據(jù)葉杰平教授在中國(guó)人工只能學(xué)會(huì)AIDL第二期，人工智能前沿講習(xí)班-機(jī)器學(xué)習(xí)前沿所作報(bào)告《大規(guī)模稀疏和低秩學(xué)習(xí)》編輯整理而來(lái)，在未改變?cè)獾幕A(chǔ)上，略有刪減。不足之處，望指正。

葉杰平，美國(guó)密歇根大學(xué)終身教授，密歇根大學(xué)數(shù)據(jù)研究中心管理委員會(huì)成員，美國(guó)明尼蘇達(dá)大學(xué)博士畢業(yè)，現(xiàn)任滴滴研究院副院長(zhǎng)。在NIPS, KDD, IJCAI, ICDM, SDM,  ACML, and PAKDD發(fā)表多篇論文. 他擔(dān)任Data Mining and Knowledge Discovery, IEEE Transactions on Knowledge and Data Engineering, IEEE Transactions on Pattern Analysis and Machine Intelligence的編委. 2010年獲得NSF CAREER Award。2010，2011，2012年分別獲得KDD最佳論文提名，2013年獲得KDD最佳論文獎(jiǎng)。2014年獲得ICML最佳學(xué)生論文獎(jiǎng)。以下為葉杰平教授所做現(xiàn)場(chǎng)演講的一部分，主要對(duì)稀疏和低秩約束在機(jī)器學(xué)習(xí)上的應(yīng)用進(jìn)行了介紹。

大家下午好，非常高興，能夠和大家一起，分享低秩和稀疏兩種方法，主要會(huì)講解一些在large-scale方面的應(yīng)用，也會(huì)稍微提一下滴滴的一些應(yīng)用，大部分我講的很多應(yīng)用，都會(huì)用用在特征約減，與很多問(wèn)題如滴滴，都會(huì)有很多樣本，每天都有上千萬(wàn)的大規(guī)模數(shù)據(jù)量不同，很多問(wèn)題有成千上百萬(wàn)維度的特征，如何對(duì)特征進(jìn)行稀疏和低秩約束，是我們今天要講的主要內(nèi)容，今天的報(bào)告主要針對(duì)模型介紹，具體應(yīng)用可以下面查閱文獻(xiàn)，不會(huì)具體講解。

本次報(bào)告主要對(duì)一些基礎(chǔ)的稀疏模型，以及結(jié)構(gòu)的稀疏模型進(jìn)行講解，并會(huì)簡(jiǎn)單介紹低秩的模型，以及一些優(yōu)化加速算法，最后會(huì)給大家講一下large-scale，以及如何將這些算法用在大規(guī)模的數(shù)據(jù)上。

大家可能都對(duì)稀疏的含義比較了解，這里的稀疏，可能表示模型特征的稀疏，也可能表示數(shù)據(jù)的稀疏，數(shù)據(jù)稀疏主要是指文件的keyword比較稀疏，這里我們主要是指模型特征的稀疏，比如說(shuō)一維的線性回歸或者矩陣，這里的稀疏就是指模型的特征會(huì)比較少。

我們引入一個(gè)正則的概念，通過(guò)一個(gè)簡(jiǎn)單的線性擬合，建立一條線來(lái)擬合樣本點(diǎn)，假設(shè)有一個(gè)M階的多項(xiàng)式來(lái)進(jìn)行擬合，那么有M 1個(gè)參數(shù)需要估計(jì)，我們希望利用這個(gè)方式來(lái)進(jìn)行預(yù)測(cè)優(yōu)化，找到一個(gè)系數(shù)使得誤差最小。對(duì)于每一點(diǎn)我們有一個(gè)預(yù)測(cè)值y，一個(gè)ground truth，通過(guò)優(yōu)化M 1個(gè)變量，使得y與ground truth之間差異最小。當(dāng)M為0的時(shí)候我們可以知道這是一條直線，當(dāng)M等于3的時(shí)候就變成了一條曲線，等等。

通過(guò)實(shí)驗(yàn)結(jié)果。我們可以看到訓(xùn)練誤差在M很大的時(shí)候很小，而測(cè)試誤差很大，這也就是非常常見(jiàn)的過(guò)擬合的問(wèn)題，M太小的時(shí)候，模型太簡(jiǎn)單，訓(xùn)練誤差和測(cè)試誤差都很大，這也就是欠擬合的問(wèn)題，M取中間值時(shí)才會(huì)非常合適，這過(guò)擬合和欠擬合也是兩個(gè)非常常見(jiàn)的機(jī)器學(xué)習(xí)問(wèn)題。我們對(duì)這些系數(shù)進(jìn)行分析，可以看到在，當(dāng)M等于9的時(shí)候，系數(shù)非常大，也可以發(fā)現(xiàn)，如果overfit的情況，如果稍微抖動(dòng)的話，會(huì)對(duì)系數(shù)有非常大的影響，自然而然的，我們需要對(duì)我們的模型加一個(gè)正則項(xiàng)，從而通過(guò)控制系數(shù)的大小，向可以接受的誤差逼近，通過(guò)數(shù)據(jù)擬合項(xiàng)的范式約束，使得模型的誤差變小，模型能夠更加的擬合數(shù)據(jù)，再加上一個(gè)控制系數(shù)的正則項(xiàng)，使得模型的參數(shù)更加穩(wěn)定。超參數(shù)λ用來(lái)控制稀疏的程度，當(dāng)超參數(shù)λ等于0時(shí)，模型也就退化成了一般的線性回歸，λ一般需要通過(guò)調(diào)節(jié)參數(shù)學(xué)習(xí)出來(lái)，通過(guò)實(shí)驗(yàn)可以發(fā)現(xiàn)，λ比較小的話模型就會(huì)容易過(guò)擬合，λ比較合適的話模型就會(huì)比較穩(wěn)定。

通常，我們利用正則項(xiàng)來(lái)控制參數(shù)W的大小，這里可以用q norm作為正則項(xiàng)，來(lái)保證W比較小，當(dāng)q=2的時(shí)候能夠保證W有一個(gè)光滑的解析解，q=1時(shí)，正則項(xiàng)是一個(gè)凸函數(shù)，且能夠使得W稀疏；q在大于等于1 的時(shí)候，該模型仍然是一個(gè)凸函數(shù)，好處就是能夠保證找到最優(yōu)解，q小于1時(shí)，模型就變得非凸了，但是能夠找到一個(gè)稀疏解。

自然地，我們就要思考為什么L1范式能夠得到一個(gè)稀疏解，這里我們給出一個(gè)簡(jiǎn)單的例子，前面時(shí)loss函數(shù)，后面是正則項(xiàng)，可以看到一范式為凸但不可微，會(huì)在x＝0時(shí)取到極值點(diǎn)，二范數(shù)在零點(diǎn)可微，但是不一定在零點(diǎn)取得極值點(diǎn)，另外一種對(duì)于一范數(shù)稀疏的解釋是通過(guò)等高線的方式，可以發(fā)現(xiàn)一范數(shù)的約束能夠使得loss函數(shù)在零點(diǎn)相交，而二范數(shù)是一個(gè)球，不一定與loss函數(shù)在零點(diǎn)相交，從而一范數(shù)能夠使得解稀疏。

一范數(shù)最經(jīng)典的就是96年的LASSO問(wèn)題，我們有數(shù)據(jù)矩陣A，每一行代表樣本，列代表特征，有標(biāo)簽y，可以代表分類和回歸問(wèn)題，我們這里用一個(gè)簡(jiǎn)單的線性模型取取預(yù)測(cè)y，呢么Ax-y就是一個(gè)擬合項(xiàng)，一范數(shù)就是正則項(xiàng)，使得x的系數(shù)稀疏，從而去掉一些無(wú)關(guān)項(xiàng)，如對(duì)疾病不相關(guān)的基因，從而增強(qiáng)了模型的可解釋性，自動(dòng)做了特征選擇，有效的避免過(guò)擬合，這樣子，稀疏可以同時(shí)選擇特征，并且建立了模型。下面我們會(huì)講一些結(jié)構(gòu)性的計(jì)算，這個(gè)模型能夠同時(shí)作特征選擇和進(jìn)行回歸或分類。這里我們舉一個(gè)在MRI上面的應(yīng)用。利用簡(jiǎn)單的logit回歸，加上一個(gè)稀疏先驗(yàn)，利用MRI圖像進(jìn)行病人和正常人的分類，并且同時(shí)實(shí)現(xiàn)了探尋哪一些腦區(qū)信號(hào)與疾病的相關(guān)與否，找到了與疾病相關(guān)的一些特征，之前提到的y都是比較簡(jiǎn)單的，只有一列，但是很多場(chǎng)景下，y可能有很多值，我們特征可能時(shí)很多的特征，y可能是1維的比如說(shuō)有病無(wú)病，也可能多維的比如說(shuō)每個(gè)腦區(qū)的一些判別，這樣不僅每個(gè)點(diǎn)都是多維的，label也可能是有很多維，這樣就是一個(gè)兩邊都是多維的big data問(wèn)題，模型也從從一個(gè)一列，變成了一個(gè)矩陣，擴(kuò)展了一個(gè)平方的關(guān)系。如果不增加正則項(xiàng)，這種問(wèn)題將會(huì)非常難以解決。假設(shè)有一千個(gè)數(shù)據(jù)，x和y都是一百萬(wàn)維，這個(gè)模型就會(huì)是一個(gè)非常大的矩陣，如果沒(méi)有正則項(xiàng)，這個(gè)模型將幾乎無(wú)法求解。需要加入很多的假設(shè)，如低秩假設(shè)，這個(gè)模型也就可以對(duì)數(shù)據(jù)矩陣進(jìn)行分解，也就使得我們的維度降低，最后在假設(shè)稀疏，進(jìn)一步降低了系數(shù)的維度，現(xiàn)在的數(shù)據(jù)量都比較低，特征特別大，我的一個(gè)合作者進(jìn)行了一個(gè)比較大的項(xiàng)目，把所有的數(shù)據(jù)整合在一起，有兩三萬(wàn)個(gè)數(shù)據(jù)，但仍然不算很多，未來(lái)的數(shù)據(jù)如果越來(lái)越大的話，模型會(huì)越來(lái)約精確，現(xiàn)有數(shù)據(jù)不足，所以只能對(duì)模型加入很多假設(shè)，從而保證模型的有效性，當(dāng)然，數(shù)據(jù)還是第一重要的。

系數(shù)學(xué)習(xí)在很多領(lǐng)域中都有很廣泛的應(yīng)用，如生物醫(yī)學(xué)，圖像處理，neuroscience，機(jī)器學(xué)習(xí)等等，我們最終的目的是找到一個(gè)超參數(shù)，一個(gè)常用的方法是使用交叉檢驗(yàn)，在一個(gè)廣泛的超參數(shù)空間中，選擇一個(gè)最優(yōu)的超參數(shù)，這種方法可能會(huì)存在一種缺陷，一個(gè)更好的方法是使用stability selection. 相當(dāng)于對(duì)每個(gè)數(shù)據(jù)進(jìn)行子采樣，然后進(jìn)行多次篩選，選擇最好的參數(shù)，具體的可以在文章中查閱，里面有很強(qiáng)的理論證明。它會(huì)對(duì)問(wèn)題進(jìn)行很多子采樣，所以會(huì)進(jìn)行很多次的lasso求解，因此需要一個(gè)特別快的算法，這也是我們今天主要要講得，如何在大規(guī)模的數(shù)據(jù)上進(jìn)行計(jì)算。

剛剛對(duì)基礎(chǔ)進(jìn)行了講解，下面我們對(duì)幾個(gè)模型進(jìn)行講解，剛剛提到過(guò)LASSO可以同時(shí)解決提取參數(shù)和預(yù)測(cè)兩個(gè)任務(wù)，并且具有是的提取的特征具有理論可解釋性，同時(shí)非常容易推廣。我們知道，很多特征是有結(jié)構(gòu)的，特征與特征之間并不是獨(dú)立的，特征之間是可以分組，我們首先介紹一些結(jié)構(gòu)LASSO，這里給出一個(gè)例子，特征之間會(huì)有光滑性，我們給出了一個(gè)所有腦區(qū)的特征，我們可以發(fā)現(xiàn)向鄰近的點(diǎn)會(huì)比較類似，特征的光滑性有時(shí)間和空間上的光滑性，比如說(shuō)，相鄰時(shí)刻之間的數(shù)據(jù)以及相鄰空間的數(shù)據(jù)是具有相似性的，所以很多問(wèn)題都是有光滑性的，也會(huì)有一些問(wèn)題具有一些樹(shù)的結(jié)構(gòu)，以及一些問(wèn)題可能具有一些網(wǎng)的結(jié)構(gòu)，得到特征值之間的相似性。當(dāng)我們獲得我們的這些特征之間的先驗(yàn)知識(shí)之后，如果對(duì)lasso進(jìn)行推廣，利用我們的特征之間的信息，結(jié)構(gòu)的lasso也就應(yīng)運(yùn)而生。和lasso類似，損失函數(shù)可以根據(jù)問(wèn)題相關(guān)設(shè)計(jì)，如logit回歸或者最小二乘回歸等等，來(lái)表示對(duì)數(shù)據(jù)的擬合程度，重點(diǎn)是如何設(shè)計(jì)我們的penalty，lasso是L1-norm，僅僅是稀疏，特征之間沒(méi)有任何假設(shè)，但是如果我們有特征直接結(jié)構(gòu)的先驗(yàn)知識(shí)，那么我們可以在正則項(xiàng)這里進(jìn)行推廣，一般是利用一個(gè)凸的方法，來(lái)得到我們需要的結(jié)構(gòu)，這里我們根據(jù)結(jié)構(gòu)的先驗(yàn)信息，有Fused LASSO（光滑性），Graph LASSO（圖結(jié)構(gòu)）, Group LASSO（組結(jié)構(gòu)）以及樹(shù)結(jié)構(gòu)LASSO（樹(shù)結(jié)構(gòu)）。

考慮到光滑性，可以通過(guò)增加一項(xiàng)差分項(xiàng)的方式，有效的保證相鄰的兩項(xiàng)是相近的，參數(shù)是類似的，最終的結(jié)果我們會(huì)發(fā)現(xiàn)最后的結(jié)果相鄰的系數(shù)都是相同的。每一段都是一個(gè)常數(shù)，而且很多都是稀疏的，這樣子就能夠簡(jiǎn)化模型，降低模型的復(fù)雜性，同時(shí)實(shí)驗(yàn)發(fā)現(xiàn)，這種方式能夠有效的提升符合這種特點(diǎn)的數(shù)據(jù)的效果。

第二個(gè)推廣是考慮到很多數(shù)據(jù)的特征是相關(guān)的，比如說(shuō)是蛋白質(zhì)的特征之間是相關(guān)的，類似fused LASSO，我們?cè)黾右粋€(gè)penalty，使得相關(guān)的特征具有相同的結(jié)構(gòu)，考慮到相關(guān)性可能是反向，可以增加一個(gè)絕對(duì)值解決這個(gè)問(wèn)題，解決相關(guān)但是符號(hào)不一致的問(wèn)題，這個(gè)問(wèn)題會(huì)稍微復(fù)雜一點(diǎn)，是一個(gè)非凸問(wèn)題，同樣在試驗(yàn)中，我們發(fā)現(xiàn)，加了graph結(jié)構(gòu)之后，模型效果會(huì)好很多。

第三個(gè)推廣是很多特征會(huì)有一種組的結(jié)構(gòu)，最典型的應(yīng)用就是在腦影像的分析中，很多腦區(qū)或者體素之間有一定的組約束的，同時(shí)滴滴也有很多場(chǎng)景，如司機(jī)，終點(diǎn)，天氣等等，還有基因的categorical variable。我們可以很多特征必須放在一組里才有一定的意義。因此group LASSO也就應(yīng)運(yùn)而生來(lái)解決這種存在組結(jié)構(gòu)的問(wèn)題， 解決思路是，通過(guò)L1-norm來(lái)篩選特征，如果有這種組的先驗(yàn)信息，可以先提供對(duì)這些組先計(jì)算Lp-norm，在計(jì)算這幾個(gè)group的L1-norm，在通過(guò)加入這種形式的penalty，會(huì)使得相同組的要么全為零，妖媚全部被調(diào)出來(lái)。具體的應(yīng)用就是multi-task，假設(shè)我們有k個(gè)task，每一行做一個(gè)group，然后用L1Lp做penalty，這樣會(huì)使得該特征對(duì)于所有的task要么都被提取，或者同時(shí)不被提取。比如說(shuō)手寫(xiě)字符識(shí)別，有兩種極端是，一種是把所有的字母放在一起，進(jìn)行訓(xùn)練，另外一種是每個(gè)人建立一個(gè)不同的模型，第一個(gè)模型不能有很好的泛化性能，第二個(gè)模型會(huì)導(dǎo)致模型很復(fù)雜，而且每個(gè)人的數(shù)據(jù)可能不足，而multi-task是介于兩者之間的一種方式，希望建立每個(gè)人的模型是相關(guān)的，每個(gè)模型提取的特征是一樣的，可以看到，字符識(shí)別的結(jié)果相較之前的兩種方法都要好。

很多時(shí)候，簡(jiǎn)單把各個(gè)特征簡(jiǎn)單的分成各個(gè)組可能是不夠的，特征之間可能會(huì)有一些更加精細(xì)的結(jié)構(gòu)，比如說(shuō)分層的結(jié)構(gòu)，這樣子特征之間會(huì)有更多的信息，如果特征的相似性具有一種樹(shù)結(jié)構(gòu)，那么簡(jiǎn)單的使用group LASSO 效果就不好，因此我們就需要引入樹(shù)的特征，這樣會(huì)使得模型有更好的效果，這里簡(jiǎn)單舉一個(gè)例子，假設(shè)每個(gè)樣本是一個(gè)圖，最上層就是整個(gè)腦區(qū)，在樹(shù)的最頂端，如果我們對(duì)腦區(qū)進(jìn)行劃分，類似的可以繼續(xù)的繼續(xù)劃分，一直到體素，這樣子就會(huì)組成一個(gè)樹(shù)的結(jié)構(gòu)，如果兩個(gè)體素在同一個(gè)樹(shù)下，它們的特征就會(huì)很類似，如果它們不類似，那么就說(shuō)明它們距離很遠(yuǎn)，這樣子就是一個(gè)樹(shù)的特征。我們也就可以基于此，建立一個(gè)樹(shù)的lasso，每一層做一個(gè)group 的LASSO，這樣會(huì)使得如果上層為零，那么，該結(jié)點(diǎn)的所有連接都會(huì)為零，在腦影像上面的實(shí)驗(yàn)也表明，樹(shù)約束能夠使得我們挑出的特征聚集在某一些腦區(qū)，使得模型結(jié)果更加具有可解釋性。

下面講一下低秩模型，這里會(huì)將的快一些，我最后會(huì)講一些screening，有很多問(wèn)題都可以用矩陣來(lái)表示，很多時(shí)候，矩陣中的一些值是未知的，因此需要用觀測(cè)值去預(yù)測(cè)丟失值，比如說(shuō)圖像，可能會(huì)有一些圖像被樹(shù)覆蓋，需要用觀測(cè)值去預(yù)測(cè)被遮擋的部分?；蛘哒f(shuō)collaborative filter，行代表用戶，列代表等級(jí)，每個(gè)用戶被要求給電影打分，但不是所有的用戶都對(duì)所有的電影打分，所以我們需要去預(yù)測(cè)這些缺失的數(shù)據(jù)。再考慮netflix問(wèn)題，很多打分都是丟失的，我們?nèi)绾斡糜邢薜臄?shù)據(jù)來(lái)預(yù)測(cè)大量的缺失的數(shù)據(jù)。如果不做任何假設(shè)，這個(gè)問(wèn)題是很難解決的，因此，我們引入低秩假設(shè)。對(duì)于每個(gè)問(wèn)題，首要核心的問(wèn)題是少量的低秩的。Rank可以通過(guò)SVD分解，通過(guò)非零的奇異特征數(shù)就是矩陣的rank。我們希望的模型就是希望矩陣的秩比較小。

低秩模型與稀疏模型比較類似，這里我們假設(shè)紅色的是觀測(cè)點(diǎn)，白色為缺失點(diǎn)，X是我們需要預(yù)測(cè)的，該問(wèn)題第一項(xiàng)為數(shù)據(jù)擬合項(xiàng)，我們需要M與X類似，同時(shí)希望我們填補(bǔ)之后的X能夠保持低秩特性，是的主要因素?cái)?shù)量比較少，并用λ控制這個(gè)數(shù)量。由于rank是非奇異的，因此問(wèn)題的求解會(huì)存在問(wèn)題，是一個(gè)NP-難問(wèn)題，常用的方法使用rank的上確界trace-norm來(lái)逼近它，同時(shí)trace-norm是一個(gè)連續(xù)的凸問(wèn)題，使得問(wèn)題更加容易求解，且能夠使得奇異值變?yōu)榱?，最終低秩。

最近也有很多方法將其轉(zhuǎn)變成為非凸的問(wèn)題，將X轉(zhuǎn)換成U和V相乘的形式，從而使得X的秩降低，通過(guò)求解U和V對(duì)X進(jìn)行預(yù)測(cè)，，通過(guò)不斷的固定U求解V在固定V求解U，最終收斂，這樣求解更加快速。

還有一種方法是將X轉(zhuǎn)換成類似SVD的形式，把矩陣轉(zhuǎn)換為向量的問(wèn)題，將矩陣X轉(zhuǎn)化成r個(gè)秩等于1的矩陣相乘再相加，對(duì)X進(jìn)行預(yù)測(cè)，使得矩陣X的秩小于r，從而保證低秩。

下面我們主要會(huì)講一些優(yōu)化的算法，比如lasso，結(jié)構(gòu)的稀疏等等，模型大概會(huì)有怎么樣的優(yōu)化結(jié)果，我們處理的很多問(wèn)題都是連續(xù)凸不可導(dǎo)的問(wèn)題，主要會(huì)講一些流行的解放，并介紹一些加速算法。

我們的問(wèn)題幾乎都可以分解成為loss 和penalty的形式，假設(shè)loss是可微的凸問(wèn)題，penalty是不可到的凸問(wèn)題，目前主要有以下解決方法：1）將不光滑的問(wèn)題轉(zhuǎn)化為光滑的問(wèn)題，2）坐標(biāo)下降方法，3）ADMM算法，4）次梯度下降，5）梯度下降，6）加速梯度下降等等。下面會(huì)主要講解坐標(biāo)下降以及ADMM。

坐標(biāo)下降算法的想法很簡(jiǎn)單，假設(shè)模型有一百萬(wàn)維的數(shù)據(jù)，需要優(yōu)化一百萬(wàn)維的數(shù)據(jù)，那么我們會(huì)每次只優(yōu)化一維的特征，依次優(yōu)化，不斷迭代，一直到收斂。很多大問(wèn)題的解法可以用這種方法很快速的求解。

當(dāng)問(wèn)題是光滑且凸的時(shí)候，坐標(biāo)下降算法一定可以收斂，當(dāng)問(wèn)題不光滑的時(shí)候，當(dāng)不光滑的部分是可分的，那么坐標(biāo)下降算法也可以收斂。坐標(biāo)下降算法的有點(diǎn)事可以很容易的計(jì)算，同時(shí)能夠非常快的收斂。但是缺點(diǎn)是當(dāng)loss比較復(fù)雜時(shí)，會(huì)很明顯的降低速度，且不一定有解。

快速講一下ADMM，ADMM算法假設(shè)有兩個(gè)變量fx＋gz，然后給定一個(gè)約束，將其放入兩組變量，我們可以首先是生成增廣拉格朗日，再增加penalty，從此就可以通過(guò)反復(fù)依次對(duì)xzy優(yōu)化對(duì)模型求解。

ADMM對(duì)于大規(guī)模的問(wèn)題非常有效，能夠?qū)?fù)雜問(wèn)題變成一個(gè)較為容易求解的問(wèn)題，我們以lasso為例，一個(gè)傳統(tǒng)的LASSO是有一個(gè)loss加一個(gè)一范數(shù)約束，我們將x變成z，所以約束為z=x，就可以生成如下增廣拉格朗日模型：

對(duì)于xzu的求解都會(huì)發(fā)現(xiàn)非常容易求解，也就將一個(gè)lasso一個(gè)復(fù)雜的非凸問(wèn)題，通過(guò)幾個(gè)簡(jiǎn)單的更新，就可以對(duì)齊求解，ADMM的優(yōu)點(diǎn)是解釋非常簡(jiǎn)單，如果模型非常復(fù)雜，能夠非常有效的處理，同時(shí)可以分布式的進(jìn)行計(jì)算，并對(duì)低秩可以很快的學(xué)習(xí)，缺點(diǎn)就是收斂比較慢。

下面介紹以下大家熟悉的梯度下降法，可以對(duì)光滑問(wèn)題非常有效的求解，同過(guò)不斷的沿著梯度方向迭代，一定能求出凸光滑問(wèn)題的解。但是我們需要關(guān)注的問(wèn)題時(shí)如何將梯度下降將其推廣到非光滑的問(wèn)題上面，想法非常自然，考慮一個(gè)梯度下降算法，我們可以通過(guò)另外的方式將其表達(dá)，對(duì)其進(jìn)行一個(gè)低階的逼近，用一個(gè)低階的taylor展開(kāi)做一個(gè)一階的逼近，再利用正則項(xiàng)，使得x再可行域范圍內(nèi)。然后我們對(duì)M函數(shù)找到最優(yōu)化的x，然后不斷迭代。通過(guò)數(shù)學(xué)驗(yàn)證我們也可以發(fā)現(xiàn)最優(yōu)的x剛好等于梯度下降的值，即這種方式時(shí)梯度下降的另外一種表達(dá)方式，將梯度下降轉(zhuǎn)化為了一個(gè)有優(yōu)化問(wèn)題。

通過(guò)低階泰勒展開(kāi)，加正則，以及不光滑的部分，將梯度下降轉(zhuǎn)變?yōu)榱艘粋€(gè)能求解可微不可導(dǎo)的方法，沒(méi)有改變速度，并且能夠保證收斂到最優(yōu)解。然后我們可以對(duì)其進(jìn)行加速，之前講得時(shí)再當(dāng)前點(diǎn)進(jìn)行梯度下降，我們可以通過(guò)引入下一個(gè)點(diǎn)，并對(duì)其進(jìn)行線性組合，從而使得其加速，再si上進(jìn)行梯度下降，可以證明這樣的收斂速度是最優(yōu)的。

加速梯度下降的關(guān)鍵問(wèn)題是penalty，如果penalty簡(jiǎn)單，那么模型一定有解細(xì)節(jié)，如果penalty復(fù)雜，那么模型會(huì)很復(fù)雜，每一步的cost會(huì)很大，當(dāng)L1norm時(shí)，或者trace-norm都可以將其轉(zhuǎn)化為一個(gè)proximal操作，存在一個(gè)很好的解析解，從而使得模型的解稀疏或者低秩。

最后講一下screen，剛剛講了很多優(yōu)化的解法，比如說(shuō)CD ADMM GD 等等，這些可以解小到中型的問(wèn)題，非常有效，但是對(duì)于大規(guī)模的數(shù)據(jù)，做交叉檢驗(yàn)，訓(xùn)練，就會(huì)有很高的代價(jià)。那么我們動(dòng)機(jī)就是如何使用稀疏加快我們的算法，加快的原因主要有，模型的特征非常多，模型可能復(fù)雜，可能需要很多次交叉嚴(yán)重，并且需要對(duì)很多特征進(jìn)行統(tǒng)計(jì)上的驗(yàn)證。都會(huì)非常復(fù)雜，因此我們需要加快我們的算法。

自然的想法就是對(duì)數(shù)據(jù)進(jìn)行約減，將該問(wèn)題壓縮，從而有效的加快算法，把大問(wèn)題變?yōu)樾?wèn)題，最近有很多這方面的研究，比如說(shuō)隨機(jī)的選擇特征，或者做heuridtic，通過(guò)將相關(guān)性大的特征選擇出來(lái)，從而達(dá)到數(shù)據(jù)壓縮，但這種方法都不能達(dá)到一個(gè)精確的結(jié)果。所以有一些方向是盡可能的保證與精確解的誤差最小，這里我要介紹一種方法，這種方法沒(méi)有誤差，核心思想是將維度約減之后，保證和不screen之前的解一樣，我們用lasso做一個(gè)例子，data是需要約減，假設(shè)系數(shù)稀疏，這里我們假設(shè)大部分的數(shù)據(jù)系數(shù)是等于零的，那么我們可以直接去掉這些數(shù)據(jù)，從而有效的實(shí)現(xiàn)對(duì)數(shù)據(jù)的約見(jiàn)，screen的核心是在不求解lasso的情況下，盡可能找到系數(shù)為零的參數(shù)，實(shí)現(xiàn)對(duì)數(shù)據(jù)約減。核心方法是是第一步找到對(duì)偶解，Lasso的對(duì)偶問(wèn)題有很好的幾何解釋，也就是對(duì)數(shù)據(jù)做一個(gè)投影，有時(shí)有些對(duì)偶解，可能不好求解，但是可以通過(guò)一個(gè)近似解，來(lái)對(duì)數(shù)據(jù)進(jìn)行screen，第二補(bǔ)在將系數(shù)可能為零特征screen掉，第三步最后在小的數(shù)據(jù)上進(jìn)行訓(xùn)練，這樣就可以非?？焖偾蠼?。

大家知道從primal到duel有一個(gè)KKT，我們給定一個(gè)KTT θ是對(duì)偶變量，xi是特征，在不同sample的值，我們需要關(guān)心的是那些β等于0，從而能夠有效screen數(shù)據(jù)，我們發(fā)現(xiàn)，當(dāng)θx＜1時(shí)，βi一定等于0，這也是我們需要利用到的核心，但是這里的θ是不知道的，因此我們需要找到一個(gè)近似解。當(dāng)在一個(gè)鄰域內(nèi)，max θx＜1，那么最優(yōu)解一定給在這個(gè)鄰域內(nèi)。這個(gè)區(qū)域需要越簡(jiǎn)單越小越好。實(shí)驗(yàn)發(fā)現(xiàn)模型，在不加入新的資源的情況下，運(yùn)算加速可以有幾百倍，而精度幾乎不變化。而且該screen方法可以用在別的模型上，對(duì)其進(jìn)行加速。

剛剛我們講的是特征很大，對(duì)其進(jìn)行壓縮，更加流行的問(wèn)題是樣本是無(wú)窮大，但是特征并不多，因此需要對(duì)樣本的數(shù)量進(jìn)行screen，比如說(shuō)SVM，我們需要進(jìn)行分類，需要找到一個(gè)超平面，吧兩類分開(kāi)，最重要的是如何找到支持向量，問(wèn)題是如何在沒(méi)有求解svm的時(shí)候找到支持向量，因此我們可以用screen找到支持向量，去掉對(duì)問(wèn)題沒(méi)有影響的點(diǎn)，從而對(duì)數(shù)據(jù)進(jìn)行壓縮，快速找到超平面。LASSO是在挑樣本，SVM是用來(lái)挑樣本，都是通過(guò)一個(gè)screen操作，去掉無(wú)用樣本或者特征，問(wèn)題減少，從而速度加快。與lasso類似，我們首先對(duì)對(duì)偶問(wèn)題進(jìn)行預(yù)估，再接兩個(gè)優(yōu)化問(wèn)題，找到一個(gè)鄰域，從而找到解得判斷，從而加快速度。當(dāng)然也會(huì)遇到一些特征和樣本都大的問(wèn)題，我們可以同時(shí)對(duì)樣本和特征都進(jìn)行壓縮的情況下，同時(shí)保證解一樣，同時(shí)這個(gè)方法很容易推廣。