越來越多人發現，自動駕駛不是隻依靠神經網路就能成功。
作者 | 陳彩嫻
編輯 | 文靚
上個月，雷鋒網「AI科技評論」報道了MIT在讀中國博士生、清華大學機械工程系校友楊珩開發用於提高自動駕駛安全性的可認證感知演算法一文，引起了部分讀者的關注。然而，當時的報道較簡略，因此AI科技評論聯絡了楊珩本人，圍繞「可認證感知演算法」這一較為陌生的概念再次進行了補充交流。
那麼，什麼叫做「可認證感知演算法」（Certifiable Perception Algorithm）？它對自動駕駛，或其他機器人（Robotics）方向的研究意義是什麼？它的研究難點又是什麼？
事實上，「可認證感知演算法」最早是一個數學上的概念，在2016年由蘇黎世聯邦理工學院（ETH）數學系的教授、2018年斯隆研究獎獲得者 Afonso S。 Bandeira 在“A Note on Probably Certifiably Correct Algorithms”一文中提出。
針對許多最佳化問題在獲得一個解時、沒有後驗（a posteriori）證明該解是否為最優解的情況，Bandeira 提出了一個 PCC（Probably Correct Certifiable）演算法，不僅可以解決經典的最佳化例項問題，還可以提供一個「後驗證書」（a posteriori certificate），向研究人員證明該解為最優解。
在 Bandeira 的這篇工作中，PCC演算法也被應用於機器學習的某些場景，比如學習隨機塊模型（stochastic block model）。本質上，“certificate”是一個數學測度，揭示了研究人員求得的解與全域性最優解之間的差距。例如，當差距非常小，只有一億分之一時，那麼研究人員就能知道，該解已是近似最優，可以視為全域性最優。
受此啟發，楊珩從2018年開始研究可認證感知演算法，如今已取得一系列成果。
1. 什麼是可認證演算法？
在自動駕駛中，可認證感知演算法存在的核心意義，是提高車輛在駕駛過程中的安全性，防止意外事故的發生。
如下圖所示，自動駕駛車輛A（即“robot”，機器人）在路上行駛的過程中，如“看”到一輛車B，用攝像頭拍攝一張照片，照片中會包含該車輛 B。我們假設車輛A的記憶體裡有B的3D模型，而車輛A的任務是估測B的位置和姿態（6D pose， 3D rotation and translation）。這時，A 會用一個神經網路檢測出所攝2D平面圖像上的所有關鍵點（keypoints），如車輪、車燈、鏡子等等，然後將這些所識別出的目標與3D模型上的關鍵點進行資料關聯（data association），識別物體是車鏡、車燈或其他元件。
如果神經網路所檢測出的關鍵點與資料關聯都是正確的，那麼自動駕駛的視覺感知挑戰（比如估測車輛B的位置和姿態）在轉為數學最佳化問題時則相對好解。但在實踐中，神經網路往往會出錯。神經網路的前端可能會輸出錯誤的關鍵點，比如，有可能將檢測出來的鏡子識別為汽車的輪子，從而建立一些不正確的關聯，也就是所謂的「
異常值
」（outliers，上圖的紅色連線）。
在這種情況下，我們往往難以區分 2D 平面圖像與 3D 汽車模型中的對應關係中，哪些是正確資料（inliers）、哪些是異常資料（outliers）。這時，自動駕駛車輛 A 在估測車輛 B 的姿態時，如果估計正確，那麼線框圖會對應地重疊在 A 所拍攝的 2D 影象上；若估計錯誤，則 2D 影象上會出現許多紅點（如上圖最右上角所示）。
一旦估計出錯，自動駕駛車輛則可能發生碰撞等安全事故問題。比方說，自動駕駛車輛A感知到同時行駛在一條馬路上的車輛 B 的存在。B 距離 A 實際只有3米，但如果估計錯誤，判斷 B 距離 A 有10米，那麼 A 可能就會加速行駛，造成嚴重的事故。
所以，用於估計車輛姿態的演算法不僅要告訴研究人員一個正確的結果，還要解釋這個結果有多麼地正確（即解與最優解之間的距離）。當演算法失敗時，演算法也應向駕駛自動車輛的人（或者系統）傳遞一個訊號，使駕駛員能採取其他的行動，比如接管方向盤、停車或及時尋求他人支援等。這，也是「
可認證感知演算法
」的具體內涵。因此，
在「安全第一」的自動駕駛領域，可認證感知演算法具有深遠的現實意義。
但話說回來，「可認證演算法」所扮演的角色雖然聽起來很簡單，研究起來卻並不容易，因為在這個研究的過程中涉及到了對截斷最小二乘法（Truncated Least Squares， TLS）的求解。TLS是一個非凸最佳化問題，其可行域集合可能存在區域性最優點，但求解全域性最優的難度相當於NP難題。
因此，儘管早期歐洲有些學校也沿著可認證演算法的方向研究，但他們解決問題的切入點只停留在建模階段，且面向的場景為沒有異常值的情況。
基於Bandeira的工作，楊珩與他的博士導師 Luca Carlone 還就「可認證演算法」制定了更高的標準。
假設演算法為 A，A 的目標是解決最佳化問題 P，而最佳化問題取決於輸入資料 D。那麼，如果該演算法是可認證的，則必須同時滿足三個條件：
1）A 必須是多項式演算法（polynomial algorithm），理論上必須要快；
2）在解決 P 後，A 要麼得到一個全域性最優解，以及證明該解為全域性最優的“證書”（certificate）；要麼失敗，沒有得到全域性最優解，只得到所謂的“measurable suboptimality”，即所求得的解與全域性最優解之間的距離；
3）對於大部分 D，A 都能將 P 解到全域性最優。
第三個條件由楊珩與 Luca Carlone 新增，目的是為了排除近似演算法。所謂“近似演算法”（approximate algorithm），指的是演算法得到的解永遠只能是近似最優。在自動駕駛中，近似演算法相當於在任何情況下都無法取得全域性最優解，一直“報錯”，這會對駕駛安全造成極大隱患。
所以，在楊珩與團隊的假設中，A 只有在處理大多數不同情形時能得到全域性最優解，才能被稱為「可認證演算法」，滿足自動駕駛的安全需求。
2. “非凸”轉“凸”
2018年12月，楊珩加入麻省理工學院資訊與決策系統實驗室（Laboratory for Information & Decision Systems， LIDS），師從MIT萊納多職業發展副教授 Luca Carlone，開始從事計算機視覺與機器人的結合研究。
一開始，他們只是從一個小的點雲配準/重建（point cloud registration）問題出發。所謂“點雲配準”，指的是求兩個點雲之間的旋轉平移矩陣，將源點雲變換到與目標點雲相同的座標系下。比如，一輛車無人車分別處在 a 點與 b 點，用無人車點雷達分別對著一棟樓掃一下，再把兩張掃描的圖融合在一起。
他們針對這個問題設定了一個可認證演算法，並在2019年1月投了一篇文章到機器人頂會 RSS（Robotics： Science and System），文章被接收。在這篇工作中，
他們使用TLS來重新設計點雲最佳化估測問題，使估計對大部分虛假的點到點對應關係不敏感，可以容忍高達 99% 的異常值（outliers）。
圖注：楊珩被 RSS 2019 接收的工作，https://arxiv.org/pdf/1903.08588.pdf
但是，他們在 RSS 2019 中提出的可認證演算法精確度並不夠突出，有時無法滿足上述所說的第三個條件（對大部分輸入資料都能獲得最優解）。許多時候，該演算法得到的差距至多是 1e-2、1e-3，而不是1e-6或1e-10等接近0的差距。
從 RSS 2019 開始，他們就一直在研究可認證演算法。
2019年2月左右，楊珩用兩週時間獨自琢磨，看了許多數學資料，嘗試換一種對原問題（TLS）的求解方法。他
從一個數學思維出發，提出了半正定規劃（Semidefinite Programming）鬆弛，將非凸最佳化問題 TLS 轉化為凸最佳化問題。
這個方法十分成功，他們投到了 ICCV 2019，被成功接收。
圖注：楊珩被 ICCV 2019 接收的工作，https://arxiv.org/pdf/1905.12536.pdf
對楊珩來說，ICCV 2019 的這篇工作有里程碑式的紀念意義：
因為那篇文章是第一個能將有異常值（outliers）的機器人感知問題在多項式時間內（polynomial time）解到全域性最優（global optimality）的工作。我們設計的半正定規劃鬆弛（SDP relaxation）是extremely tight，那個演算法幾乎對所有問題都能得到全域性最優，而且它解的原問題是一個帶有二元變數（+1 和 -1，mixed integer）的非凸問題。這種問題是一個NP-hard問題。
Wahba 問題，又稱為“旋轉搜尋”，旨在找到最佳旋轉以在給定的對應關係下對齊兩組向量觀察，是許多計算機視覺和機器人應用中的基本研究（比如可以用作衛星的定位）。在 ICCV 2019 中，楊珩針對大量向量觀測值為異常值（outliers）的情況，提出了第一個多項式時間可證明的最優方法來解決 Wahba 問題。
在這篇工作中，除了使用 TLS 成本來制定 Wahba 問題，他們還開發了凸半定規劃（SDP）鬆弛來解決非凸問題。他們提出可認證演算法 QUASAR （基於 QUAternion 的半定鬆弛法，用於魯棒對齊），即使在面臨大量噪聲與異常值的情況下（比如多餘95%的異常值），他們的鬆弛也很“緊”，算出可證明的全域性最優解（即鬆弛是精確的），優於魯棒的區域性最佳化演算法 RANSAC。
“非凸”轉“凸”，是楊珩提出的演算法能夠在大部分輸入資料中求得全域性最優解的關鍵點
。憑藉這一主導思想以及後續的一系列工作，楊珩獲得 ICRA 2020 的機器視覺最佳論文獎，還入圍了 RSS 2021 最佳論文獎最終名單。
如前所述，TLS是一個非凸最佳化問題，基本框架如下：
非凸問題幾乎是無法快速求得全域性最優解的，但是，我們可以透過凸鬆弛方法，將非凸問題轉為凸問題。這個過程就相當於以退為進：當你面對一道難題（如非凸問題）、不知所措時，你可以先把它轉化成一個較為簡單的問題（如凸問題），然後去求解這個簡單的問題。解完簡單的問題後，你會知道簡單的問題 B 與原問題 A 是否等價。
更有意思的是，在解出簡單問題 B 之前，你並不知道簡單問題 B 是否與難問題 A 是否等價。但當你解完 B 後，你會檢驗該解是否滿足原問題的某些條件、從而推測問題 B 與問題 A 是否等價。如果滿足，那麼凸問題被解，實際上也就意味著原來的非凸問題已經解決。
「有點“事後諸葛亮”的感覺。」
楊珩形容。從理論上講，一般性的凸問題也是NP-hard問題，目前在多項式時間內是不可求解的，但極個別凸問題，比如SDP的優點是：
可以在多項式時間內求出全域性最優解。在這個凸問題中，所有區域性最優都是全域性最優。
在“非凸”轉“凸”的過程中，楊珩的靈感也源自一個非常著名的數學“鬆弛”理論：2001年，法國數學家 Jean B。 Lasserre 在數學頂刊《SIAM Journal on Optimization》上發表了一篇著名的文章，叫“Global optimization with polynomials and the problem of moments”（引用量已超過2600），裡面提到：
非凸問題永遠不可能等價於凸問題，但如果滿足一定條件，我們就可以用一個足夠大的凸問題來逼近/解決一個非凸問題。不過，我們並不明確該非凸問題有多大，它可能是無限大。
這是一個十分優美的理論。假設非凸問題是迷霧中的一座小島，那麼凸問題就是一片不斷在尋找島嶼邊界的汪洋，摸索，定義，直至幾乎全部包圍，不斷接近真實的全貌。
但也不難推測，在這個“鬆弛”的過程中，研究會面臨兩個難點：
1）如何用一個足夠小的凸問題來解決非凸問題？比方說，原來的非凸問題可能只有100個引數要求解，但你要解的凸問題可能有100萬個引數。也就是說，你需要解一個非常大的凸問題，才能解原來的非凸問題。
2）楊珩觀察到，雖然只要解決一個包含100萬引數的凸問題、就能解原來只有100個引數的凸問題，但目前在數學上，沒有一個求解器可以解決這麼大的凸問題。在楊珩的研究中，他所用於求解非凸問題的凸問題是“半正定規劃”問題（Semidefinite Programming， SDP），屬於凸問題裡最難的一類。
從理論上講，要解決原來的非凸問題 TLS，轉換的凸問題可能要無限大，不止100萬個引數，也可能是1000萬、1億、10億甚至上百億。針對第一個難點，楊珩及團隊用真實計算顯示：
轉化的凸問題（即SDP問題）不需要無限大，只需要一個最小的凸問題（引數量為100萬)，即可解決原來的非凸問題。
而且，在將非凸問題（下圖左）轉為凸問題（下圖右）的過程中，演算法不僅在凸問題上求解，還會將凸問題的解投射到原來的非凸問題中，來回求解。在這個過程中，非凸問題的解會加速凸問題的求解，非凸問題的區域性最優也可以對映到凸問題的頂點（vertexes），加速求解。目前，他們的工作是第一次在SDP求解中用到了這種「不捨原問題」的求解思想，極具創新。
而對於第二個難點，楊珩他們所面臨的難點是：目前市面上現有的求解器最多隻能求解規模為小到中等的 SDP 問題。所以，他們只能自己研發求解器。
3. 研發求解器 STRIDE
找到全域性最優解，與證明全域性最優解，是兩碼事。比如，在ICRA 2020的機器視覺最佳論文獎中，楊珩所提出的演算法便能快速找到全域性最優解，但是無法證明該解是全域性最優，即找不到一個明確的“證書”（certificate）來佐證。
楊珩解釋，從本質上看，Robotics（關於機器的學科）的核心是最佳化，車輛的3D姿態估計便是在解一個最佳化問題。不僅是感知，自動駕駛中的車輛控制、規劃等，都是在解決最佳化問題。
針對不同的最佳化問題，研究人員會使用不同的最佳化框架，並根據某個特定的框架尋找是否有合適的求解器。研究分為兩步進行：建模（modeling）與求解（solving）。
所謂「建模」，就是將一個真實世界的問題（如上述所說的自動駕駛汽車感知周圍事物）轉化為一個數學問題。建模完成後，解決這個數學最佳化問題的過程就叫做「求解」。一般情況下，目前在機器人（Robotics）領域，大多數工作都是隻做建模，僅依靠現存的求解器來解決數學上的最佳化問題。楊珩的博士導師 Luca Carlone 此前便主要做建模。
但在研究可認證演算法的過程中，他們發現，如果只做建模是無法解決100萬引數量的問題。市面上也沒有成熟的SDP求解器可以幫助他們解決這個問題，所以他們只能自己去開發求解器。
從2019年開始，他們就在尋找適合的求解器。一開始，他們的問題也沒有包含那麼多的變數，現有求解器已能滿足這個凸問題的計算要求。直到去年9月，他們的研究要面臨越來越多的引數量，才發現「還是得自己開發求解器，因為現有的求解器解決不了我們的問題。」
從去年9月到今年4月，他們一直在嘗試不同的求解器，發現結果均不盡如人意。於是，他們就去找了新加坡國立大學數學系的系主任 Kim-Chuan Toh 和他的學生 Ling Liang，與他們一起合作，針對待解凸問題的特質，用大約 4 個月的時間開發出了一個主要面向 SDP 問題的約束求解器——STRIDE。（STRIDE的原始碼目前已在Github上公開：https：//github。com/MIT-SPARK/STRIDE）
開發求解器的難點，主要是利用好待解決問題的優勢。半正定規劃（SDP）是一個很大的數學問題，而楊珩要解決的SDP問題除了通用特徵，還有一些特殊的性質。比如，它的最優解是低階（low rank）。
而有了 STRIDE 的助力後，楊珩所提出的可認證感知演算法在求解速度與準確度上均有了明顯的提升。
如下圖所示，原來的非凸問題 TLS 只有 54 個變數時，它所對應的凸問題 SDP 至少有 8154 個變數；TLS 只有 1004 個變數時，SDP 問題的變數超過了 300 萬。MOSEK 與 SDPT3 被視為目前最出色的 SDP 求解器，但隨著問題的變數越來越多，MOSEK 與 SDPT3 不僅無法求解，甚至連儲存該問題的記憶體都沒有。
在上圖中，1e-10、1e-12等數值為精確度。數值越低，求解的精確度越高。從第 1 行到第 5 行，最佳化的問題越來越大，測度（measurement）越來越多。回到一開始的例子，就是自動駕駛車輛周圍的汽車越來越多，汽車的關鍵點與連線也會越來越多。
實驗證明，當問題的維度（dimension）較低時，SDPT3 和 MOSEK 可以求解，但速度不到 STRIDE 的二分之一。比如，在維度為 104 時，MOSEK 的求解時間是 870 秒，而 STRIDE 只需 45 秒；維度為 204 時，MOSEK 無法求解，而其他演算法雖然可以解，但卻解不到全域性最優，精確度不夠。當維度達到 1004 時，即使給再多的執行時間，其他求解器也無法達到與 STRIDE 相匹配的精確度。
楊珩介紹，
他們所提出的演算法是目前唯一能夠解決大規模一階（rank-one）SDP問題的方法
。他們在百度的自動駕駛資料集 Apollo Scape （影象採集自北京、上海與深圳）上做過實驗，STRIDE 的效能明顯優於 MOSEK 等求解器。
此前，他們的工作曾發表在 NeurIPS 2020 上，但當時，演算法只解決了 4 個常見的感知問題。加上 STRIDE 後，他們嘗試將演算法拓展至更廣泛的設定下進行，解決了 6 個感知問題，包括單點旋轉均勻（single rotation averaging）、多點旋轉均勻（multiple rotation averaging）、點雲配準、網格配準、絕對姿態估計與分類感知。
求解器的核心思想是最佳化與決策，而自動駕駛的執行就是“robot”（汽車）一直在做決策。比如，自動駕駛車輛要從 a 點走到 b 點，而 a 點與 b 點之間有一個障礙物，那麼，規劃一條從 a 點到 b 點的最短路線，便是一個近似最佳化問題。
楊珩還介紹，STRIDE求解器不僅可以解決機器視覺問題，還有望解決一些數學問題。他們最近做了一些新的工作，便計劃投到數學類的期刊與會議上。
4. 數學不可或缺
目前，楊珩的工作還處於學者討論的階段，距離落地還有一段很長的距離。
儘管他們的演算法在求解速度上已經很快，但實際的求解時間也要 1 個小時。如果可認證演算法要在現實中落地，那麼求解時間至少要從 1 個小時縮減到 1 秒。
「
很多人認為自動駕駛很簡單，那或許是因為他們還沒有體會到數學和科學計算有多難。
」楊珩感嘆，「
從 L1 到 L5，自動駕駛要解決的都是數學問題。越來越多人發現，自動駕駛不是隻依靠神經網路就能成功。
」
儘管如此，楊珩的可認證感知演算法仍有存在的意義：「
我可以認證，只是我現在認證的時間比較長而已
。」在未來，計算硬體的提升可能會帶來問題的突破。
對楊珩等痴迷理論研究的科研者來說，在研究可認證演算法的過程中，「非凸」轉「凸」的成功，才是一件比求解時間從 1 小時縮減到 1 秒更令人激動的突破。
在研究的過程中，楊珩受到許多數學知識的幫助與啟發，也取得了不少突破性的成果。因此，他覺得數學在視覺演算法研究（和其他科學研究）中是一門十分重要的學科：
硬核數學問題會非常考驗人的耐心。我覺得有時候也不是難不難的問題，而是你能不能花一天的時間看一篇數學文章，搞懂這篇文章的所有細節。有可能你看了5遍之後，你就會醍醐灌頂。在那一瞬間，這個方法成為了你自己的方法。一旦你掌握了這個方法之後，你就會發現這個方法特別地 powerful（強大），可以將它應用到很多別的方案中。
如果有一天，你能想明白數學家是怎麼理解問題的，可能你的境界就高了一層。
談到未來的研究方向，楊珩的願望之一是用可認證演算法來指導神經網路的訓練過程，提高神經網路的安全性。
少年新馬，未來可期。
參考連結：
1。 A。 Bandeira。 A note on probably certifiably correct algorithms。 Comptes Rendus Mathematique， https：//arxiv。org/pdf/1509。00824。pdf
END
新加坡的「自動駕駛」新名片：成於國小，憂也國小
誰是中國智慧駕駛中上游產業鏈的業績王？
