人工智能模型与算法：博弈安全

《人工智能模型与算法：博弈安全》由会员分享，可在线阅读，更多相关《人工智能模型与算法：博弈安全（63页珍藏版）》请在金锄头文库上搜索。

1、人工智能博弈与安全 人工智能 模型与算法人工智能 模型与算法 提纲提纲 1 博弈相关博弈相关概念概念 2 遗憾最小化算法 遗憾最小化算法 3 虚拟遗憾最小化算法 虚拟遗憾最小化算法 4 人工智能安全 人工智能安全 博弈论的诞生 博弈论的诞生 中国古代博弈思想中国古代博弈思想 子曰 饱食终日 无所用心 难矣哉 不有博 弈者乎 为之 犹贤乎已 论语 阳货 朱熹集注曰 博 局戏 弈 围棋也 颜师古注 博 六博 弈 围碁也 古语博弈所指下围棋 围棋之道又蕴含古人谋 划策略的智慧 略观围棋 法于用兵 怯者无功 贪者先亡 围棋赋 孙子兵法 等讲述兵书战法的古代典籍更是 凸显了古人对策略的重视 博弈论的诞生

2、 博弈论的诞生 田忌赛马田忌赛马 齐将田忌善而客待之 忌数与齐诸公子 驰逐重射 孙子见其马足不甚相远 马有上 中 下辈 于是孙子谓田忌曰 君弟重射 臣能令君胜 田忌信然之 与王及诸公子 逐射千金 及临质 孙子曰 今以君之下 驷与彼上驷 取君上驷与彼中驷 取君中驷 与彼下驷 既驰三辈毕 而田忌一不胜而 再胜 卒得王千金 于是忌进孙子于威王 威王问兵法 遂以为师 史记 孙子吴起列传 对局对局 齐王马齐王马 田忌马田忌马 结果结果 1 A A 齐王胜 2 B B 齐王胜 3 C C 齐王胜 对局对局 齐王马齐王马 田忌马田忌马 结果结果 1 A C 齐王胜 2 B A 田忌胜 3 C B 田忌胜 3

3、 0 1 2 以己之长以己之长 攻彼之短攻彼之短 博弈论的诞生博弈论的诞生 现代博弈论的建立现代博弈论的建立 博弈论 game theory 又称对策论 博弈行为 带有相互竞争性质的主体 为了达到 各自目标和利益 采取的带有对抗性质的行为 博弈论主要研究博弈行为中最优的对抗策略及其 稳定局势 协助人们在一定规则范围内寻求最合 理的行为方式 1944年冯 诺伊曼与奥斯卡 摩根斯特恩合著 博 弈论与经济行为 以数学形式来阐述博弈论及 其应用 标志着现代系统博弈理论的初步形成 冯 诺伊曼被称为现代博弈论之父 John von Neumann 1903 1957 Oskar Morgenstern 1

4、902 1977 Theory of Games and Economic Behavior Princeton University Press 1944 博弈论的相关概念 博弈论的相关概念 博弈的要素博弈的要素 参与者或玩家 player 参与博弈的决策主体 策略 strategy 参与者可以采取的行动方案 是一整套在采取行动之前就已经准备好的完 整方案 某个参与者可采纳策略的全体组合形成了策略集 strategy set 所有参与者各自采取行动后形成的状态被称为局势 outcome 如果参与者可以通过一定概率分布来选择若干个不同的策略 这样的策略称为混合策略 mixed strategy

5、 若参与者每次行动都选择某个确定的策略 这样的策略称为纯策略 pure strategy 收益 payoff 各个参与者在不同局势下得到的利益 混合策略意义下的收益应为期望收益 expected payoff 规则 rule 对参与者行动的先后顺序 参与者获得信息多少等内容的规定 建模者对参与者 player 规定可采取的策略集 strategy sets 和取 得的收益 观察当参与者选择若干策略以最大化其收益时会产生什 么结果 两害相权取其轻 两利相权取其重 博弈论的相关概念博弈论的相关概念 研究范式研究范式 博弈论的相关概念 博弈论的相关概念 囚徒困境 囚徒困境 prisoner s di

6、lemma 参与者参与者 甲 乙 规则规则 甲 乙两人分别决策 无法得知 对方的选择 策略策略集集 认罪 沉默 纯策略 局势及对应收益 年 局势及对应收益 年 甲认罪 0 乙沉默 10 甲认罪 5 乙认罪 5 甲沉默 10 乙认罪 0 甲沉默 0 5 乙沉默 0 5 在囚徒困境中 最优解为两人同时沉默 但 是两人实际倾向于选择同时认罪 均衡解 1950年 兰德公司的梅里尔 弗勒德和梅尔 文 德雷希尔拟定了相关困境理论 后来美国 普林斯顿大学数学家阿尔伯特 塔克以 囚徒 方式 阐述 警方逮捕了共同犯罪的甲 乙两人 由于警方没有 掌握充分的证据 所以将两人分开审讯 若一人认罪并指证对方 而另一方保

7、持沉默 则此 人会被当即释放 沉默者会被判监禁10年 若两人都保持沉默 则根据已有的犯罪事实 无充 分证据 两人各判半年 若两人都认罪并相互指证 则两人各判5年 乙沉默 合作 乙认罪 背叛 甲沉默 合作 二人各 服刑半年 乙被释放 甲服刑10年 甲认罪 背叛 甲被释放 乙服刑10年 二人各 服刑5年 囚徒困境产生的原因 对甲而言 若乙沉默 自己认罪的收益为0 而自己也沉默则收益为 0 5 若乙认罪 自己 认罪则收益为 5 自己沉默则收益为 10 对乙而言 若甲沉默 自己认罪的收益为0 而自己也沉默则收益为 0 5 若甲认罪 自己 认罪的收益为 5 自己沉默则收益为 10 即对两人而言认罪的收益

8、在任何情况下都比沉 默的收益高 所以两人同时认罪是一个稳定的 局势 其他三种情况都不是稳定局势 囚徒困境表明稳定局势并不一定是最优局势 博弈论的相关概念 博弈论的相关概念 囚徒困境 囚徒困境 prisoner s dilemma 参与者参与者 甲 乙 规则规则 甲 乙两人分别决策 无法得知 对方的选择 策略策略集集 认罪 沉默 纯策略 局势及对应局势及对应收益 年 收益 年 甲认罪 0 乙沉默 10 甲认罪 5 乙认罪 5 甲沉默 10 乙认罪 0 甲沉默 0 5 乙沉默 0 5 在囚徒困境中 最优解为两人同时沉默 但 是两人实际倾向于选择同时认罪 均衡解 合作博弈与非合作博弈 合作博弈 co

9、operative game 部分参与者可以组成联盟以获得更大的收益 非合作博弈 non cooperative game 参与者在决策中都彼此独立 不事先达成合作意向 静态博弈与动态博弈 静态博弈 static game 所有参与者同时决策 或参与者互相不知道对方的决策 动态博弈 dynamic game 参与者所采取行为的先后顺序由规则决定 且后行动者知道先行动者所 采取的行为 完全信息博弈与不完全信息博弈 完全信息 complete information 所有参与者均了解其他参与者的策略集 收益等信息 不完全信息 incomplete information 并非所有参与者均掌握了所有

10、信息 囚徒困境是一种非合作 不完全信息的静态博弈囚徒困境是一种非合作 不完全信息的静态博弈 博弈论的相关概念博弈论的相关概念 博弈的分类博弈的分类 博弈的稳定局势即为纳什均衡 Nash equilibrium 指的是参与者所作出的这样一种策略组合 在该策 略组合上 任何参与者单独改变策略都不会得到好 处 换句话说 如果在一个策略组合上 当所有其 他人都不改变策略时 没有人会改变自己的策略 则该策略组合就是一个纳什均衡 Nash定理 若参与者有限 每位参与者的策略集有 限 收益函数为实值函数 则博弈必存在混合策略 意义下的纳什均衡 囚徒困境中两人同时认罪就是这一问题的纳什均衡 Nash J No

11、n Cooperative Games The Annals of Mathematics 54 2 1951 286 博弈论的相关概念博弈论的相关概念 纳什均衡纳什均衡 博弈论的相关概念博弈论的相关概念 混合策略混合策略下纳什均衡的例子下纳什均衡的例子 参与者 雇员 雇主 规则 雇员与雇主两人分别决策 事先无法得 知对方的选择 混合策略集 雇员 偷懒 不偷懒 雇主 检查 不检查 局势及对应收益 雇主采取检查策略时雇员工作与偷懒对 应的结果 雇主采取不检查策略时雇员工作与偷懒 对应的结果 例子 公司的雇主是否检查工作与雇员是否偷懒 是雇员的贡献 是雇员的工资 是雇员的付 出 是检查的成本 是雇

12、主发现雇员偷懒对雇 员的惩罚 没收抵押金 假定 雇员 偷懒 不偷懒 雇主 检查 不检查 是雇员的贡献 是雇员的工资 是 雇员的付出 是检查的成本 是雇主发 现雇员偷懒而对雇员的惩罚 没收抵押 金 假定 雇员 偷懒 不偷懒 雇主 检查 不检查 采取采取 策略策略 收益收益 雇 主 检查 1 1 不检查 2 1 雇 员 偷懒 3 1 不偷懒 4 1 若雇主检查的概率为 雇员偷懒的概率为 博弈论的相关概念博弈论的相关概念 混合策略混合策略下纳什均衡的例子下纳什均衡的例子 纳什均衡 其他参与者策略不变的情况下 某个 参与者单独采取其他策略都不会使得收益增加 无论雇主是否检查 雇员的收益都一样 无论雇

13、员是否偷懒 雇主的收益都一样 于是有 1 2 以及 3 4 在纳什均衡下 由于 3 4 可知雇主采取 检查策略的概率 雇主趋向于用这个概率去 检查 在纳什均衡下 由于 1 2 可知雇员采取 偷懒策略的概率 雇员趋向于用这个概率去 偷懒 在检查概率为 之下 雇主的收益 1 2 对上式中 求导 则当 时 雇主 的收益最大 其值为 2 采取采取 策略策略 收益收益 雇 主 检查 1 1 不检查 2 1 雇 员 偷懒 3 1 不偷懒 4 1 若雇主检查的概率为 雇员偷懒的概率为 混合策略纳什均衡 博弈过程中 博弈方通过概 率形式随机从可选策略中选择一个策略而达到的 纳什均衡被称为混合策略纳什均衡 博弈

14、论的相关概念博弈论的相关概念 混合策略混合策略下纳什均衡的例子下纳什均衡的例子 提纲提纲 1 博弈相关概念 博弈相关概念 2 遗憾最小化算法 遗憾最小化算法 3 虚拟遗憾最小化算法 虚拟遗憾最小化算法 4 人工智能安全 人工智能安全 博弈论与计算机科学博弈论与计算机科学 冯 诺依曼 现代计算机之父 现代博弈论之父 博弈论与计算机科学的交叉领域非常多 理论计算机科学 算法博弈论 人工智能人工智能 多智能体系统 AI游戏玩家 人机交互 机器学习 广 告推荐 互联网 互联网经济 共享经济 分布式系统 区块链 人工智能与博弈论相互结合 形成了两个主要研究方向 博弈博弈策略的求解策略的求解 博弈规则的设

15、计博弈规则的设计 博弈策略求解博弈策略求解 动机 博弈论提供了许多问题的数学模型 纳什定理确定了博弈过程问题存在解 人工智能的方法可用来求解均衡局面或者最优策略 主要问题 如何高效求解博弈参与者的策略以及博弈的均衡局势 应用领域 大规模搜索空间的问题求解 围棋 非完全信息博弈问题求解 德州扑克 网络对战游戏智能 Dota 星球大战 动态博弈的均衡解 厂家竞争 信息安全 遗憾最小化算法 遗憾最小化算法 Regret Minimization 若干定义若干定义 假设一共有 个玩家 玩家 所采用的策略表示为 对于每个信息集 0 1 是在动作集 上的概率分布函数 玩家 的策 略空间用 表示 一个策略组

16、包含所有玩家策略 用 1 2 表示 中除了 之外的策略 即除去玩家 所采用的策略 在博弈对决中 不同玩家在不同时刻会采取相应策略以及行动 策略 下对应的行动序列 发生的概率表示为 于是 这里 表示玩家 使用策略 促 使行动序列 发生的概率 除玩家 以外 其他玩家通过各自策略促使行动序列 发生的概率 可表示为 对于每个玩家 表示玩家 的收益函数 即在到达终止序列集合 中某个终 止序列时 玩家 所得到的收益 玩家 在给定策略 下所能得到的期望收益可如下计算 遗憾最小化遗憾最小化算法 算法 最佳反应策略与纳什最佳反应策略与纳什均衡均衡 玩家 对于所有其他玩家的策略组 的最佳反应策略最佳反应策略 满足如下条件 max 在策略组 中 如果每个玩家的策略相对于其他玩家的策略而言都是最佳反应策略 那么策略 组 就是一个纳什均衡纳什均衡 Nash equilibrium 策略 纳什均衡 策略组 1 2 是纳什均衡当且仅当对每个玩家 满足如下条件 max 1 2 遗憾最小化遗憾最小化算法 算法 纳什纳什均衡与均衡与平均遗憾平均遗憾值值 纳什均衡 对于给定的正实数 策略组 是 纳什均衡当且仅当对于每个玩家