博弈论(一)

在之前的讨论中,一场游戏只有一个智能体。而在博弈论中,智能体评估它们的决策如何与其他人的决策相互作用以产生不同的结果。 简单博弈 看一个具体的博弈游戏: 圆圈中的数字代表一个状态。L/R/M 代表智能体可采取的动作。叶子节点的数字代表智能体 A 的得分(B的得分是相反数) 首先 A 做出一个选择(动作),随后 B 做出一个动作,然后 A 可视情况再次做出一个动作。 博弈论一个基本前提是:假设所有玩家都想最大化自己的得分,并都可以正确做出最佳动作,并都相信其他玩家也会这样做。 这是博弈问题最简单的一种:两个玩家的零和有限确定性完美信息博弈。 **两个玩家:**顾名思义,就是在这个博弈游戏中只有2个玩家(智能体)。 **零和:**两个玩家获得的奖励(得分)之和是一个常量。(不一定为0) **有限性:**显然,这场博弈的一切元素例如:状态、动作等都是有限的。 **确定性:**从 MDP 角度理解,即博弈中没有随机转换。从某一状态采取某一动作得到的结果是确定的。 **完美信息:**我们能够确定当前智能体所处的状态。 STRATEGIES(策略) 在 MDP 中有个名词叫 POLICIES (策略),它是状态到动作的映射。博弈论中有类似的概念,称为 STRATEGIES (策略),它是所有可能的状态到动作的映射。 对于 A 来说 (1→L, 4→L) 就是一个策略。不难看出,在这个特定的游戏中,A 有4个策略,B 有3个策略,如下:(这种策略被称为纯策略) A: (1→L, 4→L) (1→L, 4→R) (1→R, 4→L) (1→R, 4→R) B: (2→L, 3→R) (2→M, 3→R) (2→R, 3→R) 我们可以以表格的形式写出这些策略,并在中间填入最后的得分。(由于B得分是A的相反数,所以这里省略B) 最终可以得到一个矩阵(红框部分),这个矩阵包含了此场博弈的一切信息,即:有了它我们不再需要一开始的博弈树了。 极小极大原理 试想这样一个游戏过程: A 为了最大化得分,也许会选择策略 (L,L) 或策略 (L,R) ,也就是矩阵的前两行。因为只有这样才有可能得到最高分7. 然而 B 同样希望最大化自己的得分,所以在 A 先选择的情况下,B 自然会选择当前状态下对自己最有利的。例如当 A 选择 (L,L),B 就会选择 (R,R)....

May 19, 2018 · Chenhe

Q-learning 算法

Q-learning 是一个经典的强化学习算法。 为了便于描述,这里依然定义一个“世界”: 令空白格子的奖励为1. Q-Table Q-table 是 Q-learning 的核心。它是一个表格,记录了每个状态下采取不同动作,所获取的最大长期奖励期望。通过此,就可以知道每一步的最佳动作是什么。 Q-table 的每一列代表一个动作,每一行表示一个状态。则每个格子的值就是此状态下采取此动作获得的最大长期奖励期望。例如: U↑ D↓ L← R→ START ? 0 0 ? (2,1) 0 0 ? ? (1,2) ? ? 0 0 … … … … … 上表表示,对于状态 STRAT 向下或左的奖励期望是0(因为无法移动),其余两个方向由于未探索,所以奖励未知。状态(2,1)和状态(1,2)同理。 如果能求出整个表的所有值,那么这个问题就解决了。为了做到这一点,需要使用 Q-learning 算法。 Q-learning 算法 算法流程可以表述为: 初始化 Q-table. 选择一个动作 A. 执行动作 A. 获得奖励。 更新 Q....

May 18, 2018 · Chenhe

Markov 决策过程

Markov 决策过程中文译为马尔可夫决策过程。英文全称为 Markov Decison Processes,简称 MDP. 为了便于描述,首先定义一个“世界”,如下: 从起点开始,每次选择往四个方向走一格子。目标是到达绿色格子,游戏结束,碰到红色则失败,游戏结束。 黑色格子为障碍物,碰到障碍物或撞到墙壁则原地不动。 但是每次移动准确率只有80%,另外有20%的概率向与目标方向垂直的方向移动,这两个垂直的方向概率各是10%. 名词定义 **STATES(状态):**顾名思义,就是智能体当前的状态。在这个世界中,表现为「坐标」。则开始状态就是(1,1),目标状态是(4,3). **ACTIONS(动作):**即在一个特定的STATE中所做的事。在这个世界中表现为四向移动。 **MODEL(转换模型):**模型描述了整个游戏规则。可以抽象为有三个参数的函数:T(s,a,s'),他生成的其实是一个概率:P(s'|s,a),即:从状态s,采取动作a,转换到状态s’的概率。 **REWARD(奖励):**即到达一个状态得到的反馈。例如到达绿色格子可以获得正数奖励。所以可以表述为与状态有关的函数:R(s),也可以变形为 R(s,a) 或 R(s,a,s'). **POLICY(策略):*上面三个定义组成了一个「问题」,则策略就是一个解决方案。它根据所处的状态,返回一个动作。可以表述为函数:π(s) → a. 而 $ \pi^ $ 则表示最优策略,它最大化长期期望奖励。 从MODEL定义,可以得出 Markov 特性,即:下一个状态的产生只和当前状态有关。 不同奖励下的策略 无穷时域是前提假设,即:只要不进入红绿格子,游戏可以一直进行下去。 当空白格子奖励为+2,甚至大于目标格子的奖励。那么智能体就会尽可能地留着游戏中不出局。基于此,可得上图策略。 需要注意,第(3,3)格子不可以向下。若向下,则有10%概率结束游戏,若向左则不可能结束游戏。 当空白格子奖励为-2,为了最大化长期期望奖励,智能体应该尽快结束游戏。基于此可得上图策略。 需要注意,第(3,1)格不可以向上。若向上则有10%概率向左,距离结束位置更远。 偏向稳定性 有一个关于状态序列的价值函数 V: $$ V(s_0,s_1,s_2,…) = \sum_{t=0}^{\infty}R(s_t) $$ 有这样一个事实: 若 $ V(s_0,s_1,s_2…) > V(s_0,s_1',s_2'…) $ 则有 $ V(s_1,s_2…) > V(s_1',s_2'…) $ 同时,价值说明了延迟奖励的意义所在。即采取某一动作当时不会获得高额奖励甚至是负数奖励,但未来可以收获较多奖励。 折扣期望 引例 假设有下面两种奖励序列: 直观上可能会认为 V2 > V1,但是实际上 V2 = V1 = ∞....

May 9, 2018 · Chenhe

准确率(Accuracy)|查准率(Precision)|查全率(Recall)

在机器学习中,对于一个模型的性能评估是必不可少的。准确率(Accuracy)、查准率(Precision)、查全率(Recall)是常见的基本指标。 为了方便说明,假设有以下问题场景: 一个班有50人,在某场考试中有40人及格,10人不及格。 现在需要根据一些特征预测出所有及格的学生。 某一模型执行下来,给出了39人,其中37人确实及格了,剩下2人实际上不及格。 样本 要了解这些指标的含义,首先需要了解两种样本: **正样本:**即属于某一类(一般是所求的那一类)的样本。在本例中是及格的学生。 **负样本:**即不属于这一类的样本。在本例中是不及格的学生。 识别结果 于是我们可以得到下面一张表: 正类 父类 被检索 True Positive False Positive 未检索 False Negative True Negative TP: 被检索到正样本,实际也是正样本(正确识别) 在本例表现为:预测及格,实际也及格。 FP: 被检索到正样本,实际是负样本(一类错误识别) 在本例表现为:预测及格,实际不及格。 FN: 未被检索到正样本,实际是正样本。(二类错误识别) 在本例表现为:预测不及格,实际及格了。 TN: 未被检索到正样本,实际也是负样本。(正确识别) 在本例表现为:预测不及格,实际也不及格。 指标计算 有了上述知识,就可以计算各种指标了。 Accuracy(准确率) 分类正确的样本数 与 样本总数之比。即:(TP + TN) / ( ALL ). 在本例中,正确分类了45人(及格37 + 不及格8),所以 Accuracy = 45 / 50 = 90%....

April 2, 2018 · Chenhe