手机网站建设制作教程,如何推广网站?,全国企业信息官网网站,qq可以上网论文链接#xff1a;http://people.csail.mit.edu/branavan/papers/acl2011.pdf 文章目录1. 背景介绍2. 将攻略文本引入值函数 Q(s,a)Q(s, a)Q(s,a) 评价2.1 复杂环境下使用传统 Q(s,a)Q(s, a)Q(s,a) 函数的缺陷2.2 设计 Q(s,a,d)Q(s, a, d)Q(s,a,d) 神经网络2.3 模型训练流程…论文链接http://people.csail.mit.edu/branavan/papers/acl2011.pdf 文章目录1. 背景介绍2. 将攻略文本引入值函数 Q(s,a)Q(s, a)Q(s,a) 评价2.1 复杂环境下使用传统 Q(s,a)Q(s, a)Q(s,a) 函数的缺陷2.2 设计 Q(s,a,d)Q(s, a, d)Q(s,a,d) 神经网络2.3 模型训练流程3. 在《文明》游戏中进行算法验证3. 1 状态-行为设置3. 2 效用设置3. 3 关键句提取函数∅→\overrightarrow\varnothing∅、词性分类函数ψ→\overrightarrow\psiψ、效用值计算函数fk→\overrightarrow{f_k}fk论文主旨本文设计了一种能够读懂 “游戏攻略” 并根据 “游戏攻略” 进行行为决策的算法框架。其中游戏攻略是指前人总结出来的游戏经验以文字的形式表达。该算法将 “游戏攻略” 融入到行为值函数 Q(s,a)Q(s, a)Q(s,a) 的评价中使得在算法在评价状态 sss 下采取行为 aaa 的效用 Q(s,a)Q(s, a)Q(s,a) 时会参考人类的先验知识游戏攻略即 Q(s,a,d)Q(s, a, d)Q(s,a,d)ddd 代表游戏指引 documentdocumentdocument。 1. 背景介绍
大多数在我们玩游戏时都会接触到游戏指引它告诉你这个游戏的基本规则或是游戏的基本操作方法不仅如此每个游戏都会存在一些独特的游戏攻略这些攻略大多由一些玩过数百个小时的玩家们总结经验得到。通过这些游戏指引每个新手玩家都能从中学习到不少经验从而快速提升。那么当我们想训练一个 Agent 模型来玩一款新游戏时我们同样期望这些 “游戏指引” 能在我们 Agent 学习的时候起到启发的作用在有了先验知识辅助的情况下Agent 便能够更加快速和更加拟人化的进行行为决策。
但使用人类先验知识的一大难题在于人们之间沟通常使用文字交流攻略指引也大多使用文字进行记载机器如何能看懂文本形式的游戏指引呢本文通过蒙特卡洛学习的方法来解决该难题使得经过训练后的模型能够具备“语义分析” ”行为决策“ 这两大能力。
语义分析是指模型能够提取出一句话中对状态和行为的描述词并将这些词准确的对应到游戏状态中去。例如“在游戏的初始阶段尽量选择矿产资源丰富的地区建造基地” 这一句游戏攻略中模型需要提取出 “游戏初期” 这一代表状态的词语和 “在矿产资源丰富的地区建造基地” 这一代表行为的词语。行为决策是指在提取到了攻略中的关键词后相应地在游戏初期的状态下采取在建议地区进行基地建造的行为。
一种最直观完成上述任务的方法是训练一种 “直译” 模型能够对人类的语句进行翻译提取出语句中状态关键词并与游戏中的状态建立一对一的关系——这也是前人们大多的工作。但这种方法对于复杂的游戏环境来说是无法实现的例如想要建立 “矿产资源丰富的地区” 这个状态描述词和游戏中的某个具体状态之间的联系就非常复杂如何定义矿产资源封不丰富这对于同一局游戏中的不同时刻的定义都应该有所不同。再例如“进攻敌方基地” 这一个词语包含了许多原子行为要想与游戏内的某一个具体的行为建立一对一的关系也是非常困难的。因此本文并不采取 “直译” 再 “映射” 的方法而是直接将整个攻略文本作为一个参考输入在计算行为值函数 Q(s,a)Q(s, a)Q(s,a) 的时候会去参考攻略文本中的内容将 Q(s,a)Q(s, a)Q(s,a) 转变为 Q(s,a,d)Q(s, a, d)Q(s,a,d)通过人类先验知识来辅助行为值函数进行效用评判。
2. 将攻略文本引入值函数 Q(s,a)Q(s, a)Q(s,a) 评价
2.1 复杂环境下使用传统 Q(s,a)Q(s, a)Q(s,a) 函数的缺陷
在介绍该小节之前我们先来回顾一下行为值函数action-value functionQ(s,a)Q(s, a)Q(s,a) 的定义行为值函数的输入是一个 行为 - 状态 的组合是评价在某一特定状态下采取某个特定行为得到的效用值。但在一些复杂游戏中直接学习 Q(s,a)Q(s, a)Q(s,a) 函数会存在两个致命的缺陷
状态空间非常大进行探索学习耗费时间非常长。在复杂游戏中某些状态之间是很 “相似的” 但是 Agent 很难找到这种 “相似” 的关联关系。
引入 “游戏攻略” 能很好的解决以上两个问题由于将 “游戏攻略” 作为了一个参考输入当 Q(s,a,d)Q(s, a, d)Q(s,a,d) 在进行效用评判时攻略 ddd 中的内容会对状态 sss 和行为 aaa 起到约束的作用即引导评价函数参考人类的先验知识来评价行为的效用值另外引入 “游戏攻略” 能够帮助模型找到状态之间的 “相似性”例如 “尽量在河边建立基地” 这一句话语中对于一张复杂地图来说河边包含了若干个不同的地点但倘若没有攻略信息模型会再每一个河边尝试不同的行为得到 s, a 的效用集但加入了攻略后模型再训练过程后会意识到虽然有这么多不同的状态但它们都有一个相似之处——都在河边这样在一些相似的状态下模型就会采取相似的动作行为了。
2.2 设计 Q(s,a,d)Q(s, a, d)Q(s,a,d) 神经网络
针对较为复杂的游戏环境我们通常无法枚举所有可能状态因此本文使用近似拟合的手段来搭建评价函数模型。本文使用多层神经网络搭建模型其中隐藏层用于分析攻略文本中各句子之间的关系以及所包含的行为和状态整个神经网络结构如下 输入层 x→\overrightarrow{x}x输入 (s,a,d)(s, a, d)(s,a,d) 向量分别代表当前状态、决策行为、文本攻略。隐藏层1该层包含两个子集 y→,z→\overrightarrow{y}, \overrightarrow{z}y,z这两个子集对文本攻略进行分析提取出状态、行为的关键词。隐藏层2该层接收输入s,a,d,yi,zjs, a, d, y_i, z_js,a,d,yi,zj通过映射关系 fff 计算最后结果。输出层输出最终效用值 QQQ。
其中隐藏层的设计是本文中最重要的设计环节接下来我们着重剖析两个隐藏层的设计。 隐藏层1 —— 提取攻略文本中关键词信息 隐藏层1的主要作用是为了提取攻略文本中包含 “状态”、“行为” 的关键词信息该层一共分为两个子集 y→,z→\overrightarrow{y}, \overrightarrow{z}y,z。其中y→\overrightarrow{y}y 用于判断整段攻略文本中哪一句话和当下的状态-行为最贴切本文使用线性log函数来计算攻略文本中第iii句话的贴切程度 p(yi∣st,at,d)∝eu→⋅∅(yi,st,at,d)p(y_i|s_t, a_t, d) \propto e^{\overrightarrow{u}·\varnothing(y_i, s_t, a_t, d)} p(yi∣st,at,d)∝eu⋅∅(yi,st,at,d) note: ∅(yi,st,at,d)\varnothing(y_i, s_t, a_t, d)∅(yi,st,at,d)是一个特征函数见3.3我们需要学习的参数是向量 u→\overrightarrow{u}u。
通过上述计算我们能够选择出整段攻略中最符合当前状态的一句话隐藏层的第二个子集 z→\overrightarrow{z}z 用于判断该句子中每一个单词的词性将每个归类为以下三类中的一类状态描述词、行为描述词、背景词。具体分类方法使用 “语法树” 的结构进行词性归类在给定分类规则 qi→\overrightarrow{q_i}qi 的情况下句子中第 iii 个单词的分类标签计算如下 p(ei→∣yi,qi)∏jp(ei∣j,e1:j−1→,yi,qi)p(ei∣j,e1:j−1→,yi,qi)ev→⋅ψ(ej,j,e1:j−1→,yi,qi)p(\overrightarrow{e_i}|y_i, q_i) \prod_j p(e_i|j, \overrightarrow{e_{1:j-1}},y_i, q_i )\\ p(e_i|j, \overrightarrow{e_{1:j-1}},y_i, q_i ) e^{\overrightarrow{v}·\psi(e_j, j, \overrightarrow{e_{1:j-1}},y_i, q_i)} p(ei∣yi,qi)j∏p(ei∣j,e1:j−1,yi,qi)p(ei∣j,e1:j−1,yi,qi)ev⋅ψ(ej,j,e1:j−1,yi,qi) note: ψ(ej,j,e1:j−1→,yi,qi)\psi(e_j, j, \overrightarrow{e_{1:j-1}},y_i, q_i)ψ(ej,j,e1:j−1,yi,qi)是一个特征函数见3.3我们需要学习的参数是向量 v→\overrightarrow{v}v。
其中e1:j−1→\overrightarrow{e_{1:j-1}}e1:j−1 代表在目前到第 jjj 个单词之前根据前面的单词判断出来的词性标签。z→\overrightarrow{z}z 中包含了攻略段落中每一句话每一个单词的词性标签但由于我们只需要整个攻略段落中最符合当前v状态的句子因此 z→\overrightarrow{z}z 会根据 y→\overrightarrow{y}y 判断出的最符合语句输出相应句子的单词词性标签。 隐藏层2 —— 根据关键词、状态、行为进行效用评价 在获得了第一个隐藏层的输出 yiy_iyi 和 ziz_izi 后我们就可以进行效用计算了计算公式如下 Q(st,at,d)w→⋅fk(st,at,d,yi,zi)Q(s_t, a_t, d) \overrightarrow{w} · f_k(s_t, a_t, d, y_i, z_i) Q(st,at,d)w⋅fk(st,at,d,yi,zi) note: fk(st,at,d,yi,zi)f_k(s_t, a_t, d, y_i, z_i)fk(st,at,d,yi,zi)是一个固定的值函数见3.3我们需要学习的参数是向量 w→\overrightarrow{w}w。
2.3 模型训练流程
对于上述神经网络模型文中采取在线学习的策略
对于每一个当前状态 sts_tst 根据 Q(s,a,d)Q(s, a, d)Q(s,a,d) 函数选择行为并与环境互动得到环境反馈分数在文明游戏中玩家会得到根据当前态势评价的实时分数因此不用等到游戏结束更新神经网络模型中 u→,v→,w→\overrightarrow{u}, \overrightarrow{v}, \overrightarrow{w}u,v,w 三个参数
对于游戏中的每一个状态都会重复以上3个步骤若干次由于对每个游戏状态都枚举计算了一遍所以论文题目中才提到的是基于Monte-Carlo法进行学习。
如何进行参数更新呢由于该问题是一个非线性的问题因此文中使用随机梯度下降法来进行参数更新损失函数选择 mean-square error通过 Q(s,a,d)Q(s, a, d)Q(s,a,d) 和 R(sτ)R(s_\tau)R(sτ) 之间的差值来求解梯度 KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ \bigtriangleup… note: α\alphaα 是代表学习率。
更进一步的我们更直观的写出对三个参数 u→,v→,w→\overrightarrow{u}, \overrightarrow{v}, \overrightarrow{w}u,v,w 的更新式子 w→←w→αw[Q−R]f→(s,a,d,yi,zi)ui→←ui→αu[Q−R]Qx→[1−p(yi∣x→)]vi→←vi→αv[Q−R]Qx→[1−p(zi∣x→)]\overrightarrow{w} \leftarrow \overrightarrow{w} \alpha_w[Q - R]\overrightarrow{f}(s, a, d, y_i, z_i) \\ \overrightarrow{u_i} \leftarrow \overrightarrow{u_i} \alpha_u[Q - R]Q\overrightarrow{x}[1 - p(y_i|\overrightarrow{x})] \\ \overrightarrow{v_i} \leftarrow \overrightarrow{v_i} \alpha_v[Q - R]Q\overrightarrow{x}[1 - p(z_i|\overrightarrow{x})] \\ w←wαw[Q−R]f(s,a,d,yi,zi)ui←uiαu[Q−R]Qx[1−p(yi∣x)]vi←viαv[Q−R]Qx[1−p(zi∣x)]
3. 在《文明》游戏中进行算法验证
论文中使用 Civilization 2 游戏作为测试环境该游戏是一种战旗式游戏由多个玩家在地图上建立属于子集的国家。游戏地图是由一格一格组成的每一格土地拥有不同的属性——海洋、陆地或是其他资源等玩家需要尽快占领资源并发展自己的国家并侵略和吞并其余玩家的领土。在该实验中使用一张1000块格子的地图训练模型与游戏内置AI进行对抗直到有一方完全占领整个地图获胜为止。
3. 1 状态-行为设置
实验中将状态定义为3个部分组成
当前游戏地图状态包含地图每一小格的属性每个玩家的城市属性每个玩家的单位属性
举个例子部分属性如下所示
地图格属性- 领土类型草地、山脉等等- 资源类型小麦、煤矿等城市属性- 城市人口- 食物产量单位属性- 兵种工人、建筑师等- 该单位是否在城市里
在游戏中每一个单位在对应的状态下可采取的行为空间可以通过游戏直接获取。由于一个玩家可以同时操作它所有的城市和士兵因此实验中把属于同一个玩家的所有对象可采取的行为空间合并为该玩家的行为空间。在该实验中每个玩家可以同时控制约18个单位每个单位能选择15种行为如果做组合的话行为空间将有 102110^{21}1021 种。为了减小行为空间实验种假定同一玩家的所有单位之间的行为互不影响在相互独立的前提下就不用将所有可能的行为进行组合极大缩减了玩家的行为空间。
3. 2 效用设置
通常Monte-Carlo法需要直到游戏结束得到评分之后再反向计算考虑到文明游戏的复杂性该实验直接通过文明游戏的 “实时评分系统” 进行 reward 的获取。该游戏中会根据玩家此刻的单位分布态势对玩家进行一个目前状态的评分这个评分就被选为即时汇报 RRR。
3. 3 关键句提取函数∅→\overrightarrow\varnothing∅、词性分类函数ψ→\overrightarrow\psiψ、效用值计算函数fk→\overrightarrow{f_k}fk
在2.2节中提到有几个特定的固定函数——关键句子提取函数、词性分类的函数以及最终效用计算的函数。其中∅→\overrightarrow\varnothing∅、fk→\overrightarrow{f_k}fk 函数主要考虑状态、行为的属性和文本单词之间的关系ψ→\overrightarrow\psiψ 函数旨在对一个独立的句子进行词性分类。下图是利用文明2游戏中的生存手册游戏攻略计算出的特征以及这些特征的属性值。 在整个实验中∅→\overrightarrow\varnothing∅、ψ→\overrightarrow\psiψ、fk→\overrightarrow{f_k}fk 分别计算了 306800、158500、7900306800、158500、7900306800、158500、7900个特征值。
