南洋理工大學安波博士：除了玩德撲，演算法博弈論如何在安全領域大展拳腳？

雷鋒網編者按：德州撲克的人機大戰是繼圍棋之後最受關注的人工智慧應用之一，而以其為代表的博弈問題也成為了學者們關心和討論的話題。演算法博弈論實際上在安全領域有著非常重要的指導意義，它通過提供一個恰當的數學模型，藉助有限的安全資源進行合理的調配與部署。為此，雷鋒網邀請了新加坡南洋理工大學計算機科學與工程學院的助理教授安波博士為我們揭示演算法博弈論的魅力。

安波，新加坡南洋理工大學計算機科學與工程學院南洋助理教授，於 2011 年在美國麻省大學 Amherst 分校獲計算機科學博士學位。主要研究領域包括人工智慧、多智能體系統、博弈論及優化。有 60 余篇論文發表在人工智慧領域的國際頂級會議 AAMAS、IJCAI、AAAI、ICAPS、KDD 以及著名學術期刊 JAAMAS、AIJ、IEEE Transactions。

曾獲 2010 年國際智能體及多智能體系統協會 (IFAAMAS) 傑出博士論文獎、2011 年美國海岸警衛隊的卓越運營獎、2012 年國際智能體及多智能體系統年會 (AAMAS) 最佳應用論文獎、2016 年人工智慧創新應用會議 (IAAI) 創新應用論文獎，以及 2012 年美國運籌學和管理學研究協會 (INFORMS)Daniel H. Wagner 傑出運籌學應用獎等榮譽。受邀在 2017 年國際人工智慧聯合會議 (IJCAI) 上做 Early Career Spotlight talk. 他是 Journal of Artificial Intelligence Research (JAIR) 編委會成員以及 Journal of Autonomous Agents and Multi-agent Systems (JAAMAS) 的副主編。當選為國際智能體及多智能體系統協會理事會成員。

雷鋒網 AI 科技評論：最近關於德州撲克的人機大戰很火，能否請您為我們介紹一下求解這類博弈問題的挑戰？

安博士：德撲的人機大戰是 AlphaGo 的圍棋大戰之後最火爆的話題，特別是最近李開復老師在海南組織了卡內基梅隆大學 Libratus（中文名冷撲大師）系統與龍之隊的對決。不出意外，人類棋手再一次被 Libratus 系統碾壓。Libratus 系統之父 Tuomas Sandholm 教授是我的師兄也是我的學術偶像。Libratus 的成功與近幾年來最火的深度學習無關，其成功完全歸功於德撲博弈問題均衡策略的求解。這是最讓人興奮的。圍棋比賽本身是一種完全信息博弈，而撲克是不完全信息博弈（玩家不能觀測到對手手中的牌），因此比完全信息博弈更難解決。Libratus 系統基於一些關鍵的技術，包括博弈抽象及逆映射、基於 CFR 的均衡求解，以及殘局求解。Libratus 現在的成功不是終點，比如 Libratus 目前只能單挑，不能參與群體賽。

雷鋒網()AI 科技評論：安博士，您最近的一個主要研究方向是以演算法博弈論的研究及其在安全領域的應用。是否能和我們介紹一下這個研究方向目前的研究現狀？

安博士：保護關鍵公共基礎設施和目標，如機場、港口、歷史名勝、發電設施、政治人物，甚至珍稀動物和自然資源等，是各國安全機構面對的一項極具挑戰性的任務。有限的安全資源使得安全機構不可能在任何時候都提供全面的安全保護。此外，安全部門的對手（如恐怖分子、罪犯）可以通過觀察來發現安全機構的保護策略的固定模式和弱點，並據此來選擇最優的攻擊策略。一種降低對手觀察偵查能力的方式是隨機調度安全部門的保護行為，如警察巡邏、行李檢測、車輛檢查以及其他安全程序。然而，安全部門在進行有效的隨機安全策略調度時面臨許多困難，特別是有限的安全資源不能無處不在或者每時每刻提供安全保護。安全領域資源分配的關鍵問題是如何找出有限的安全資源最優配置方案，以獲取最佳的安全保護方案。

博弈論提供了一個恰當的數學模型來研究有限的安全資源的部署，以最大限度地提高資源分配的有效性。安全博弈論研究是由南加州大學 Milind Tambe 教授領導的 TEAMCORE 研究小組引導發展起來的，現在越來越多的學者參與到這項研究中，包括卡內基梅隆大學，杜克大學，牛津大學等。相關的論文廣泛發表於人工智慧領域的頂級會議 AAMAS、AAAI 和 IJCAI，安全博弈論的研究已經成為當前人工智慧研究的熱點之一。基於安全博弈論的系統已經被美國不同領域的安全機構所應用，包括機場安保、空中警察調度、海岸警衛隊巡邏調度、野生動物保護，產生了很大的反響，如美國國會聽證數次提到了相關的研究成果及應用。

雷鋒網 AI 科技評論：整個研究過程中最富挑戰的地方在哪裡？可以如何解決？

安博士：安全博弈論研究以解決實際重大安全問題為目標，而實際問題通常是非常複雜的，大規模的，且有很多不確定因素。另外安全領域的用戶有解決方案質量的保證，因此諸如遺傳演算法一類的啟髮式演算法不能被應用。

演算法設計的第一個挑戰就是求解大規模博弈問題。隨著安全部門安全策略、恐怖分子攻擊行為和安全資源數量的增加，防禦者和攻擊者的策略空間都呈指數增長。傳統的演算法無法解決此類大規模的安全博弈問題，因此，提高現有的安全博弈演算法的可擴展性是一大挑戰。

第二個主要挑戰是演算法的魯棒性。傳統的博弈論通常假設參與者是完全理性的並且具有完美記憶能力的。但在現實中這些假設可能並不准確。因此，在計算防禦者的資源分配策略時，演算法應考慮各種不確定性，包括效用誤差、執行誤差、觀測誤差以及能力的不確定性。

雷鋒網 AI 科技評論：實際上演算法博弈論在很多安全領域已經有一些嘗試和應用，例如您參與的基於博弈論為美國海防制定巡邏計劃的研究獲得了 2012 年的 Daniel H. Wagner Prize，也已經獲得了應用。此外，您還有一篇關於野生動物保護的論文獲得了 IAAI-16 的應用革新獎項。是否能簡單介紹一下這個工作特別是在演算法設計以及應用方面的難點？想了解下，和美國海防的巡邏應用相比，同樣是圍繞博弈論設計安全演算法，是否有共通和不同之處？

安博士：每一個應用都帶來新的挑戰。在 14 年底給馬來西亞的合作 NGO 給了在動物保護區的巡邏路線，但是他們無法執行我們制定的巡邏路線，我們在 15 年 4 月專程到馬來西亞的動物保護區森林裡走了 8 個小時之後，才認識到我們忽略一些地理信息，以至於巡邏人員無法完全按照我們制定的路線行走。後來通過分析地理信息，找出所有的山脊線，求解最優的巡邏策略，並成功應用起來。最後的演算法也應用了對攻擊方建模以及處理不確定信息的研究成果。

雷鋒網 AI 科技評論：從美國聯邦空軍管理局，美國海岸警衛隊到野生動物保護組織，為這些專門領域所設計的應用軟體，在未來可能有其它的應用場景嗎？如果加入了博弈論的概念，是否存在一個通用性強的安全系統，可以在多種場景中獲得普適性的應用？

安博士：目前的安全博弈論研究可以應用到更多的安全領域，如網路安全、海洋巡邏、邊境巡邏、禁毒、抑制犯罪、對抗網路謠言等。現有的一些核心演算法設計思想可以應用於新應用領域的問題，但是每個領域可能都有自己的特點，因此需要分析新應用領域的一些結構特點，並利用這些特點提高演算法的效率。

雷鋒網 AI 科技評論：目前以安全博弈論研究還存在哪些亟待解決的問題？通常需要什麼樣的數據來支撐研究及應用？

安博士：很顯然，新的應用領域會帶來很多新的研究挑戰，之前的應用也還有很大的改善空間。George Box 說過所有的模型都是錯誤的。現有的安全博弈模型都是對複雜安全領域的抽象，並做了很多簡化以及很多較強的假設。（是否能具體說明一下？）未來的研究需要設計高保真度的攻擊者行為模型 (如攻擊者的理性行為選擇)，更合理的模型來描述環境以及博弈問題的不確定性，以及博弈的時空動態特性。

之前針對實體安全（特別是反恐）的安全博弈論研究能夠用到的數據很少，通常需要通過人工實驗來獲得一些模擬的數據。珍稀動物保護以及城市犯罪應用領域有很多數據可以用來學習模型的一些參數。

雷鋒網 AI 科技評論：深度學習系統最終需要解決知識不完備的情況，且系統在決策過程中需要考慮非常複雜的情況，實際上這與博弈論的理念非常相近，那麼結合您所做的一些工作，您認為人工智慧能如何更好地與博弈論相結合？

安博士：傳統的人工智慧技術通常考慮一個智能體（agent）的設計，多智能體系統技術的出現使得我們能夠處理分散式的學習、推理、規劃、協調等問題。隨著互聯網技術的發展，多智能體系統往往存在一些「自私」的智能體（如電子商務市場的交易方），因此需要引入博弈論來分析智能體的交互策略。我們現實社會中這種「自私」的行為比比皆是，比如司機會根據路況選擇最優的路線去目的地，計程車會選擇最優的運營時間段來獲取最多的利潤（這也是很多大城市打車難現象的主要原因），如果我們想用人工智慧技術來代替人類來做一些決策，我們需要用博弈論的方法來分析複雜的交互，設計出能真正替代人類做出理性決策的智能體，我們也做過計程車市場最優定價以及電動車充電站配置優化方面的工作。

事實上，人工智慧的開拓者比如 von Neumann 和 Simon 都對博弈論做出了傑出貢獻。博弈論和人工智慧實際上都基於決策理論。例如，有一個著名觀點把人工智慧定義為「智能體的研究和構建」。國內也有很多優秀的從事演算法博弈論研究的人工智慧學者，分佈在諸如 MSRA、清華、上財等科研機構。

雷鋒網 AI 科技評論：有觀點認為，機器學習理論認為所面對的問題可以轉變為一種找尋優化方案的過程。那麼您如何看待博弈論與機器學習的優化問題之間的聯繫？

安博士：博弈論的研究最終都被轉化為優化問題的求解，如 Libratus 系統完全基於大規模優化演算法的設計。機器學習跟統計學結合更緊密一些，而博弈論跟運籌學結合更緊密一些。

雷鋒網 AI 科技評論：這個課題聽上去並不像人臉識別、語音識別、NLP 這樣的領域一樣能廣泛應用於我們的生活中，結合您的研究經歷，談談您為何會選擇演算法博弈論的研究方向？

安博士：之前的應用更多針對於安全領域，目前有很多研究試圖將一些思想應用於包括網路安全其他領域。我在 USC 做博士后的時候開始從事這個領域的研究，後面就一直做下來了。我很幸運參與這一方面的研究，這一系列研究最讓人驕傲的地方在於，我們不僅做了高質量的研究工作，同時又有很多有巨大影響的實際應用。

雷鋒網 AI 科技評論：您將在今年的 IJCAI 發表 Early Career Spotlight 演講，介紹您最近幾年的研究工作。請順便介紹一下您了解到的其他一些熱門研究方向。

安博士：我可能會介紹我們這幾年將博弈論用於安全以及可持續發展方面的研究進展。就我熟悉的多智能體系統領域來說，熱門研究領域包括演算法博弈論、多智能體學習、分散式規劃、分散式優化等。

雷鋒網 AI 科技評論：目前 AI 在非常火熱，是否能結合您的教學經驗以及參會情況，和我們分享下新加坡的 AI 發展狀況（包括學界/業界）？

安博士：AI 在的火爆主要是工業界推動的。儘管新加坡的幾所大學都有優秀的 AI 學者，新加坡的工業界對 AI 的熱度不及。聽說新加坡政府最近在做一些大的規劃，希望這些計劃能讓真正推動 AI 研究。

從德州撲克到安全領域，演算法博弈論的魅力就在於能在有限的資源下最大限度地進行優化利用，而基於演算法的實用性，也擁有廣泛的應用空間。相信在未來，不只限於安全領域，演算法博弈論還能在更多的方向為人類帶來便利。

雷鋒網原創文章，未經授權禁止轉載。詳情見轉載須知。