0
本文作者: AI科技評論 | 2018-10-10 16:09 |
雷鋒網(wǎng) AI 科技評論按:8 月 9 日,為期兩周的 2018 國際數(shù)學(xué)家大會(ICM)在里約熱內(nèi)盧完美謝幕,來自全球一百多個國家的 3000 多位數(shù)學(xué)家出席了本次盛會。
ICM 是國際數(shù)學(xué)聯(lián)盟主辦的、每四年一次的全球最高標準的數(shù)學(xué)科學(xué)學(xué)術(shù)會議。其中,在 ICM 2018 最后一次全體講座中,UCB 教授 Michael I. Jordan 提出了屬于 AI 時代的新問題:「How should scientists efficiently compute the world's data in a way that addresses real-world problems.」
近年來,運籌優(yōu)化與決策算法作為數(shù)學(xué)在現(xiàn)實中的應(yīng)用領(lǐng)域,一直受到數(shù)學(xué)界的廣泛關(guān)注。而在此次面對 ICM 全體參會數(shù)學(xué)家的講座中,Jordan 教授發(fā)表了聚焦「是否存在最佳的優(yōu)化方法」問題的,主題為「Dynamical,symplectic and stochastic perspectives on Gradient-Based optimization」的講座。人工智能領(lǐng)域中運籌優(yōu)化和算法決策的重要性,再一次成為了全場的焦點。
Michael I.Jordan 是加州大學(xué)伯克利分校 UCB 電氣工程與計算機科學(xué)系、統(tǒng)計系杰出教授,美國科學(xué)院、美國工程院、美國藝術(shù)與科學(xué)院三院院士,機器學(xué)習(xí)領(lǐng)域目前唯一獲此成就的科學(xué)家,是機器學(xué)習(xí)的奠基者、人工智能領(lǐng)域的泰斗之一。
Michael I.Jordan已確認參加由雷鋒網(wǎng)、乂學(xué)教育·松鼠AI和IEEE LTSC主辦的『全球AI+智適應(yīng)教育峰會』,免費門票、VIP門票開放申請中,訪問大會官網(wǎng)即刻申請:https://gair.leiphone.com/gair/aiedu2018
以下是 Michael I.Jordan 教授演講的主要內(nèi)容:
今天演講的主題是動態(tài)的、保辛的隨機視角下的梯度優(yōu)化方法。內(nèi)容圍繞動態(tài)系統(tǒng)(dynamical systems)和優(yōu)化之間的關(guān)系展開。這在數(shù)學(xué)中是一個古老而寬泛的領(lǐng)域。動態(tài)系統(tǒng)研究涉及數(shù)學(xué)的眾多分支,主要基于對梯度流與力學(xué)變分觀點。「數(shù)據(jù)工程」通常被稱為「機器學(xué)習(xí)」或「人工智能」,是跨越統(tǒng)計學(xué)、物理學(xué)、計算機科學(xué)和數(shù)學(xué)的跨領(lǐng)域?qū)W科。
對我們來說,將計算與實際問題相結(jié)合是一項艱巨的任務(wù)。我們的目標是在這個領(lǐng)域中建立一些新的聯(lián)系,從基于梯度優(yōu)化的連續(xù)時間、變分角度研究等各個方面著手。我們超越了經(jīng)典的梯度流理論,專注于二階動態(tài),旨在展示這種動力學(xué)與快速收斂 (converge) 的優(yōu)化算法之間的相關(guān)性。
雖然我們關(guān)注理論研究,但實際的應(yīng)用背景對我們來說也同樣重要?,F(xiàn)代統(tǒng)計數(shù)據(jù)分析通常涉及非常大的數(shù)據(jù)集和參數(shù)空間,因此計算效率在實際應(yīng)用中至關(guān)重要。
在這樣的前提下,效率的概念比傳統(tǒng)的計算復(fù)雜性理論中「算法復(fù)雜度」的概念更加嚴格。我們接下來討論多項式復(fù)雜性和指數(shù)復(fù)雜性之間的區(qū)別,這是一個非常有意義的關(guān)注點。在大規(guī)模數(shù)據(jù)分析中,一個可以實際應(yīng)用的算法不僅需要多項式的復(fù)雜度階,而且需要在相關(guān)問題參數(shù)中線性或者近似線性的復(fù)雜度。優(yōu)化理論為提升算法的效率提供了實踐和理論的支持。它提供了計算效率高的算法,并提供了允許將收斂速度確定為問題參數(shù)的顯式函數(shù)的分析工具。鑒于基于 Hessian 的優(yōu)化方法在參數(shù)空間的維度上會產(chǎn)生二次或三次的復(fù)雜度,在討論非一階方法的時候,效率可能是一個有意義的討論點。
更廣泛地說,統(tǒng)計推斷(statistical inference)和計算思想的融合,是當(dāng)前世紀的主要趨勢之一——目前以諸如「數(shù)據(jù)科學(xué)」和「機器學(xué)習(xí)」這樣的術(shù)語來出現(xiàn)。這是一種尋求將計算和統(tǒng)計推斷需求共同研究的新的數(shù)學(xué)概念的趨勢。例如,人們希望將數(shù)據(jù)分析算法的運行時間的計算化成關(guān)于統(tǒng)計風(fēng)險、數(shù)據(jù)樣本數(shù)量、模型復(fù)雜度等統(tǒng)計量的函數(shù),同時考慮計算資源限制,如處理器數(shù)量、通信帶寬和異步程度。對這種權(quán)衡的基本理解似乎可以通過更低的下界的發(fā)展而出現(xiàn)——通過建立「最優(yōu)」概念,可以消除冗余的概念并揭示必然的聯(lián)系。在這里,優(yōu)化理論也很重要。
經(jīng)典統(tǒng)計理論沒有考慮時間維度,它的方程在數(shù)據(jù)復(fù)雜性、風(fēng)險和變量維度之間進行權(quán)衡,但在這些方程中并不包含運行時間。而在計算機科學(xué)的另一方面,你會發(fā)現(xiàn)算法設(shè)計需要在運行時間、運行資源等復(fù)雜性度量之間進行權(quán)衡,但統(tǒng)計風(fēng)險不在其中。所以要如何將這兩種方式放在一起是我們這個時代的一大挑戰(zhàn)。優(yōu)化起到了將這兩個領(lǐng)域結(jié)合在一起的作用,它提供了算法和對問題更深層次的理解,特別是當(dāng)我們開始考慮通過優(yōu)化去達到更優(yōu)的下界。
在 20 世紀 70 年代開始的一項開創(chuàng)性研究中,Nemirovski、Nesterov 和其他人開發(fā)了一種優(yōu)化的復(fù)雜性理論,建立了收斂速度的下界,并發(fā)現(xiàn)實現(xiàn)這些下界限的算法。此外,復(fù)雜性模型是相對的——指定了「oracle」,那么算法只能使用 oracle 可用的信息。例如,只訪問函數(shù)值和梯度的 oracle。因此,實際計算效率的相關(guān)指導(dǎo)方法可以在理論中以自然的方式施加。
計算和統(tǒng)計數(shù)據(jù)通過優(yōu)化結(jié)合在一起。而哪些領(lǐng)域會先開始組合在一起?我們?nèi)绾伍_始建立理論和實踐?在現(xiàn)實生活、公司和科學(xué)中,以下對于成功案例至關(guān)重要。一個是基于梯度的優(yōu)化,我學(xué)到的算法版本,是在關(guān)注 Hessian 矩陣和牛頓迭代法以及更高階的版本。在二三十年間,它們發(fā)揮了很多作用,特別是在大規(guī)模計算問題上得到了成功應(yīng)用,但計算 Hessian 很難,也很難去估算它們?,F(xiàn)在我們經(jīng)常會有隨機差異,在這些問題上我們沒有辦法準確地觀察事物。這些問題只是存在于統(tǒng)計領(lǐng)域,我們可能存在各種錯誤比如采樣偏差等。我們必須面對它并且利用它。最終,加速概念在前蘇聯(lián)優(yōu)化界出現(xiàn)了,它是研究優(yōu)化算法,尤其是如何獲得最快的優(yōu)化算法的概念。這類被稱為「加速算法」的優(yōu)化算法(Nesterov, 1998),通常可以達到 oracle 的最下限速率,盡管 Nesterov 加速方法為什么能夠達到 oracle 的理論原因還是個謎。
我們認為,一些謎團是出自于離散時間算法和分析的優(yōu)化的歷史焦點。在優(yōu)化中,「連續(xù)優(yōu)化」和「離散優(yōu)化」之間的區(qū)別,在于如何匹配(「空間」)變量。相比之下,我們的討論將集中在連續(xù)時間上。在連續(xù)時間中,我們可以將加速度作為一種差異概念給予數(shù)學(xué)意義,將它作為沿曲線的速度變化。我們可以提出「最快速率是多少」的問題,來作為變分分析的一個問題。本質(zhì)上,這是為給定的 oracle 本身找到「優(yōu)化的最佳方法」作為優(yōu)化的形式問題。這種變分的觀點也具有生成性的優(yōu)點——我們可以推導(dǎo)出實現(xiàn)想要的 fast rates 的算法,而不是去為某一個特殊方式得出的特定算法去分析并建立一個符合算法要求的 fast rate。
為了使連續(xù)時間上的結(jié)果能夠推廣、得出數(shù)字計算機可以實現(xiàn)的算法,我們將連續(xù)時間動態(tài)系統(tǒng)的問題離散化。有趣的是,我們會發(fā)現(xiàn),廣泛應(yīng)用于從變分或哈密頓角度獲得的動態(tài)的辛迭代積分器,與優(yōu)化有關(guān)。從辛積分獲得的算法可以更快地通過相空間移動,這為「加速」賦予了幾何意義。
考慮在某種意義上的「加速」的連續(xù)時間下的隨機動態(tài)系統(tǒng)也是有意義的。最簡單形式的基于梯度的積分微分方程是 Langevin 擴散。我們看到,通過考慮欠阻尼 Langevin 擴散,我們將獲得更類似于加速梯度下降的方法,并且實際上可證明產(chǎn)生比過阻尼擴散更快的速率。
Nesterov 在 1980 年代提出了一種建立收斂速度下界的梯度下降方法。在 1983 年 Nesterov 發(fā)表了開創(chuàng)性論文后,隨后的三十年中,各種其他問題背景下的各種加速算法得到了發(fā)展。這些包括鏡像下降、復(fù)合目標函數(shù)、非歐幾里德幾何、隨機梯度下降和高階梯度下降。我們已經(jīng)證明了以上這些算法的收斂速度:他們的收斂速率通常達到 oracle 下限??傮w來說,加速一直是現(xiàn)代優(yōu)化理論中最富有成效的思想之一。
拉格朗日公式可以在連續(xù)時間內(nèi)捕獲加速度,顯示該公式如何產(chǎn)生一系列微分方程,其收斂速度是離散的連續(xù)時間對應(yīng)物。我們強調(diào)這些微分方程的數(shù)值積分問題,建立了我們在下面討論的辛積分方法。
辛積分是微分方程離散化的一般方法,它保留了動力系統(tǒng)的各種連續(xù)對稱性。從力學(xué)獲得的微分方程的情況下,這些對稱性包括物理上有意義的積分,例如能量和動量。即使動態(tài)量只是近似值,辛積分器也能精確保存這些量,除了從物理守恒的觀點來看這一結(jié)果的吸引力之外,連續(xù)對稱性的保留意味著辛積分器比其他積分格式更穩(wěn)定。因此可以在離散時間系統(tǒng)中使用更大的步長。正是后一個事實表明辛積分器在加速優(yōu)化方法相關(guān)的微分方程中起作用。辛積分器可以從拉格朗日框架導(dǎo)出,但更自然地,可以從哈密頓框架導(dǎo)出。但事實上,辛方法在拓撲上比 Nesterov 加速法的一個三序列變種更穩(wěn)定,如果選擇更大的步長,這一事實就會更加明顯。辛集成與優(yōu)化中的加速現(xiàn)象之間存在著聯(lián)系,當(dāng)后者被解釋為連續(xù)時間現(xiàn)象時,辛積分提供了獲得離散時間近似的有效且靈活的方式。
最需要注意的是非凸優(yōu)化中的加速度與鞍點的逃逸問題?,F(xiàn)實中存在的問題大都具有非凸特性。事實證明,對于統(tǒng)計學(xué)習(xí)中的廣泛問題,非凸情形下存在足夠的數(shù)學(xué)結(jié)構(gòu),即可以獲得有用的數(shù)學(xué)結(jié)果。實際上,在許多情況下,來自凸優(yōu)化的想法和算法適當(dāng)?shù)匦薷目梢员粦?yīng)用于非凸環(huán)境。特別對于基于梯度的優(yōu)化,在凸問題中執(zhí)行良好的相同算法也傾向于在非凸問題中產(chǎn)生良好的性能。從這個意義上說,凸優(yōu)化除了擁有自己的許多自然應(yīng)用之外,還可以作為非凸優(yōu)化的實驗室。在鞍點附近存在 pancake 區(qū)域,在這個區(qū)域內(nèi)進行梯度下降將「卡住」需要指數(shù)量級的時間逃逸。這個區(qū)域并不平坦,而是隨著 Hessian 的變化而變化。Lipschitz 假設(shè)使我們能夠控制這種變化。
到目前為止關(guān)注的是動態(tài)系統(tǒng)。系統(tǒng)是確定的。隨機性以有限的方式被引入,作為一種擾動,確保從鞍點快速逃離。我們特別分析了球中的非均勻擾動,足以快速逃離,但是這不是必要的。鑒于這種簡單選擇的成功,我們用動力研究中更徹底的隨機方法來解決我們的問題。
基于梯度的優(yōu)化的一般主題及其在大規(guī)模統(tǒng)計推斷問題中的應(yīng)用,目前非?;钴S。我們要強調(diào)一下在未來幾年可能引起持續(xù)關(guān)注的一些課題。一個令人值得注意的問題是,在統(tǒng)計設(shè)置中經(jīng)常使用優(yōu)化方法來解決點估計問題,其中核心問題是在參數(shù)空間中輸出具有所需統(tǒng)計特性的單個點。
而更廣泛的問題是,使用概率分布的一些精煉的形式來提供與該相關(guān)的不確定性的指標。通過考慮作為概率分布空間的空間,優(yōu)化思想也可以在這里體現(xiàn):我們可以要求不收斂到單個點,而是收斂到點的分布上。哈密頓方法自然而然地產(chǎn)生震蕩解,并且正如我們所看到的,需要一些工作來獲得收斂到某一個點的算法。這表明哈密頓方法實際上在分布收斂的設(shè)定中比在點估計設(shè)定中更容易使用,從而提供了點估計和更廣泛的推斷問題之間的算法橋梁。事實上,在貝葉斯推斷中,哈密頓公式(以及不同積分器形式的辛積分)已經(jīng)成功地應(yīng)用于 MCMC 算法(馬爾科夫鏈蒙特卡洛算法)的設(shè)置中,其中哈密頓函數(shù)的動量分量提供了更快的混合。加速算法和高效的推斷算法之間更深層次的聯(lián)系值得研究。
數(shù)學(xué)正在成為數(shù)據(jù)領(lǐng)域的一個強大工具,已經(jīng)證明了許多定理。對力學(xué)的梯度流和變分透視的研究可以應(yīng)用于該區(qū)域。最后,我需要重申一下數(shù)學(xué)工具在解決基于數(shù)據(jù)的實際問題中的重要性。盡管有一些現(xiàn)實世界的為數(shù)據(jù)分析的數(shù)學(xué)應(yīng)用問題,我們承認這個領(lǐng)域還不是很成熟,但未來非常值得期待。
雷鋒網(wǎng)雷鋒網(wǎng)
雷峰網(wǎng)原創(chuàng)文章,未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。