能玩德撲也能保障國家安全,南洋理工安波博士闡述演算法博弈論的魅力何在?
雷鋒網編者按:德州撲克的人機大戰是繼圍棋之後最受關注的人工智慧應用之一,而以其為代表的博弈問題也成為了學者們關心和討論的話題。演算法博弈論實際上在安全領域有著非常重要的指導意義,
安波,新加坡南洋理工大學電腦科學與工程學院南洋助理教授,
曾獲 2010 年國際智慧體及多智慧體系統協會 (IFAAMAS) 傑出博士論文獎、2011 年美國海岸警衛隊的卓越運營獎、2012 年國際智慧體及多智慧體系統年會 (AAMAS) 最佳應用論文獎、2016 年人工智慧創新應用會議 (IAAI) 創新應用論文獎,
雷鋒網 AI 科技評論:最近關於德州撲克的人機大戰很火,能否請您為我們介紹一下求解這類博弈問題的挑戰?
安博士:德撲的人機大戰是 AlphaGo 的圍棋大戰之後最火爆的話題,
雷鋒網 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 研究。
從德州撲克到安全領域,演算法博弈論的魅力就在於能在有限的資源下最大限度地進行優化利用,而基於演算法的實用性,也擁有廣泛的應用空間。相信在未來,不只限於安全領域,演算法博弈論還能在更多的方向為人類帶來便利。
並據此來選擇最優的攻擊策略。一種降低對手觀察偵查能力的方式是隨機調度安全部門的保護行為,如員警巡邏、行李檢測、車輛檢查以及其他安全程式。然而,安全部門在進行有效的隨機安全性原則調度時面臨許多困難,特別是有限的安全資源不能無處不在或者每時每刻提供安全保護。安全領域資源配置的關鍵問題是如何找出有限的安全資源最優配置方案,以獲取最佳的安全保護方案。博弈論提供了一個恰當的數學模型來研究有限的安全資源的部署,以最大限度地提高資源配置的有效性。安全博弈論研究是由南加州大學 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 研究。
從德州撲克到安全領域,演算法博弈論的魅力就在於能在有限的資源下最大限度地進行優化利用,而基於演算法的實用性,也擁有廣泛的應用空間。相信在未來,不只限於安全領域,演算法博弈論還能在更多的方向為人類帶來便利。