0
| 本文作者： 奕欣 | 2017-04-19 16:05 |
雷锋网编者按：德州扑克的人机大战是继围棋之后最受关注的人工智能应用之一，而以其为代表的博弈问题也成为了学者们关心和讨论的话题。算法博弈论实际上在安全领域有着非常重要的指导意义，它通过提供一个恰当的数学模型，借助有限的安全资源进行合理的调配与部署。为此，雷锋网邀请了新加坡南洋理工大学计算机科学与工程学院的助理教授安波博士为我们揭示算法博弈论的魅力。
安波，新加坡南洋理工大学计算机科学与工程学院南洋助理教授，于 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 研究。
从德州扑克到安全领域，算法博弈论的魅力就在于能在有限的资源下最大限度地进行优化利用，而基于算法的实用性，也拥有广泛的应用空间。相信在未来，不只限于安全领域，算法博弈论还能在更多的方向为人类带来便利。
雷峰网原创文章，未经授权禁止转载。详情见转载须知。
