（本科）P3C8决策理论规划ppt课件.pptx

课程主讲人：（本科）P3C8-决策理论规划ppt课件人工智能原理人工智能原理Principles of Artificial Intelligence某某大学某某学院某某某3第8章 决策理论规划人工智能原理n 上一章的时空关联规划基于如下假设条件：确定性、完全可观测、可达性目标。n 本章将讨论在上述假设之外如何进行规划的问题，即决策理论规划（Decision-Theoretic Planning）。n 决策理论规划的应用非常广泛，例如：高端机器人控制、医药治疗、灾害救援、等等。n 因为不同的行动会有不同的结果，某些动作可能更有利，因此需要对实现目标的潜力、风险、以及成本做出决策。第8章 决策理论规划引言4人工智能原理第8章 决策理论规划目录5o 决策理论规划概述o 马尔科夫模型o 马尔科夫决策过程的优化控制o 动态规划人工智能原理n 决策理论n 是一种决策的理论框架，用于衡量行动方案的优劣。n 决策理论的基础n 概率论（Game theory）用于在给定的状态下求得某个行动可能结果的概率分布、以及合理性偏好函数。n 效用论（Utility theory）采用效用函数，使得智能主体偏好的规划具有更高的预期效用最大期望效用（maximum expected utility, MEU）决策理论规划概述决策理论（Decision theory）6但是，决策理论并未涉猎如何构建具有高期望效用的规划。人工智能原理n 决策理论规划 = 决策理论 + 人工智能规划n形式框架：马尔科夫决策过程（Markov decision process）n优化控制：动态规划（Dynamic programming）、线性规划（Linear programming）n 决策理论规划 不确定性环境规划（planning under uncertainty）n从环境接收的信息是不完全或不完备的n动作并非总是得到同样的结果n需要在规划的不同结果之间做出权衡n 马尔科夫决策过程 马尔科夫模型（Markov models）决策理论规划概述决策理论规划（Decision-Theoretic Planning）7杰罗姆费尔德曼（Jerome Feldman）和罗伯特斯普劳尔（Robert Sproull）是最早从事决策理论规划研究的学者人工智能原理第8章 决策理论规划目录8o 决策理论规划概述o 马尔科夫模型o 马尔科夫决策过程的优化控制o 动态规划人工智能原理n 概述n一种统计模型，用于对随机变化的系统进行建模。n 性质n马尔科夫模型的下一个状态只依赖于当前的状态，而与之前发生的事件无关。马尔科夫模型马尔科夫模型（Markov models）9 完全可观测（fully observable）部分可观测（partially observable）自主（autonomous）马尔科夫过程（Markov process）隐马尔科夫模型（Hidden Markov model）控制（controlled）马尔科夫决策过程（Markov decision process）部分可观测马尔科夫决策过程（Partially observable Markov decision process）四种马尔科夫模型以俄罗斯数学家安德烈马尔科夫（Andrey Markov）的名字命名。人工智能原理n 定义马尔科夫模型随机过程（Stochastic process, SP）10随机过程的实例细菌种群的增长、由于热噪声或气体分子的移动而导致电流波动等。随机过程的应用生物学、化学、生态学、神经科学、物理学、以及工程和技术领域，如：图像处理、信号处理、信息论、计算机科学、密码学、电信等；此外，还被广泛用于金融领域。随机过程是针对随机变化的现象而建立的系统的数学模型人工智能原理n 定义马尔科夫模型马尔科夫性质（Markov property）11 所有的马尔科夫模型都具有马尔科夫性质。n 无记忆性质（memory-less property） 采用马尔科夫模型的领域：预测建模（predicate modeling）、概率预报（probabilistic forecasting）等。人工智能原理n 回置抽样 vs 无回置抽样马尔科夫模型马尔科夫性质（Markov property）12对于一个随机过程，回置抽样（sampling without replacement）具备马尔科夫性质，而无回置抽样（sampling with replacement）则不具备马尔科夫性质。例：一个坛子里有三个鸡蛋，两个红皮的，一个白皮的。昨天拿出一个，今天再拿出一个，问：明天拿出的鸡蛋的颜色？ 若只知道今天拿出的鸡蛋是红皮的，而不知道昨天拿出鸡蛋的颜色时，则明天拿出的最后一个鸡蛋颜色的概率是红白各占二分之一；只有既知道昨天、又知道今天拿出的鸡蛋的颜色时，才能判断明天拿出的最后一个鸡蛋的颜色。显然，这种观察鸡蛋颜色的随机过程问题不具有马尔科夫性质。 这是一个无回置抽样的实例。人工智能原理n 回置抽样 vs 无回置抽样马尔科夫模型马尔科夫性质（Markov property）13对于一个随机过程，回置抽样（sampling without replacement）具备马尔科夫性质，而无回置抽样（sampling with replacement）则不具备马尔科夫性质。例：用一个操纵杆控制一个玩具车，可操控玩具车朝前、后、左、右方向行进，记录仪可显示玩具车当前的方向。当记录仪显示玩具车处于前进方向时，操纵杆向左，问：玩具车的行进方向？ 这个问题的答案不言自明。 这是一个回置抽样的实例。人工智能原理n 定义马尔科夫模型马尔科夫过程（Markov process, MP）14马尔科夫过程是具有马尔科夫性质的随机过程安德烈马尔科夫早在1900年就研究了马尔科夫过程，并于1906年就此发表了论文。人工智能原理n 离散时间的马尔科夫过程马尔科夫模型马尔科夫过程（Markov process, MP）15马尔科夫过程是一类重要的随机过程，是随机模拟方法的基础，例如：机动车辆的巡航控制系统、机场旅客的队列、货币兑换率、存储系统、某些物种的增长、搜索引擎、等等。人工智能原理n 离散时间的马尔科夫过程马尔科夫模型马尔科夫过程（Markov process, MP）16v 布朗运动过程（Brownian motion process）v 一维泊松过程（Poisson process）例：赌徒破产（gamblers ruin）一个赌博成瘾的赌徒，每次赌博获胜时就将下一次赌注提高到固定比例的金额，但在输掉时不会减少。即使是每次下注都有赢钱的预期，但最终该赌徒不可避免地会输得精光。n 连续时间的马尔科夫过程人工智能原理n 定义马尔科夫模型马尔科夫链（Markov chain）17 吉布斯采样（Gibbs sampling）和马尔科夫链蒙特卡罗（Markov Chain Monte Carlo, MCMC），被用于模拟具有特定概率分布的随机对象，并且已经在贝叶斯统计中得到广泛应用。 用马尔科夫链表示某股票市场一周内的牛市、熊市或停滞的市场趋势。人工智能原理n 定义马尔科夫模型马尔科夫决策过程（Markov decision process, MDP）18马尔科夫决策过程是有限离散事件的马尔科夫过程的扩展，在自主式马尔科夫过程的基础上增加了改变状态的动作、以及环境的奖惩（reward）等。人工智能原理n 作用马尔科夫模型马尔科夫决策过程（Markov decision process, MDP）19v 是决策理论规划的形式化方法v 是一种离散时间随机控制过程（discrete time stochastic control process）v 是构建序贯决策（sequential decision-making）方法的理论框架马尔科夫决策过程中主体与环境之间的状态、奖惩、以及动作的交互过程。人工智能原理n 定义马尔科夫模型隐马尔科夫模型（Hidden Markov model）20隐马尔科夫模型可以表示为简单的动态贝叶斯网络（dynamic Bayesian network），在机器学习中发挥了重要作用，而与规划问题没有直接关系。v 是一种基于统计学的马尔科夫模型，用于描述一个含有隐含未知参数的马尔科夫过程。v 其状态可通过观测向量序列观察到，每个观测向量都是通过某些概率密度分布表现出的状态，形成一个具有相应概率密度分布的状态序列。v 隐马尔科夫模型是一个双重随机过程，即具有一定状态数的隐马尔科夫链并显示随机函数集。人工智能原理n 定义马尔科夫模型部分可观测马尔科夫决策过程（Partially observable Markov decision process , POMDP21部分可观测马尔科夫决策过程是马尔科夫决策过程在部分可观测环境下的扩展。人工智能原理第8章 决策理论规划目录22o 决策理论规划概述o 马尔科夫模型o 马尔科夫决策过程的优化控制o 动态规划人工智能原理n 定义马尔科夫决策过程的优化控制策略（Policy）23n 确定性策略（deterministic policy）n 随机策略（stochastic policy）马尔科夫决策过程优化控制的核心问题是找到一个策略。人工智能原理马尔科夫决策过程的优化控制策略（Policy）24该策略由智能主体加以实施，其目的是控制被建模为马尔科夫决策过程的环境。人工智能原理n 定义马尔科夫决策过程的优化控制奖惩（Reward）25 片段是主体与环境进行反复交互的过程中形成一些子序列。具有这种片段的任务被称为片段化任务（episodic tasks）。片段在终止状态（terminal state）下结束。n 片段（episodes）人工智能原理n 定义马尔科夫决策过程的优化控制折扣（Discounting）26考虑折扣：人工智能原理n马尔科夫决策过程的优化控制价值函数（value function）27马尔科夫决策过程的优化控制算法通过价值函数来计算最优策略。人工智能原理马尔科夫决策过程的优化控制贝尔曼公式（Bellman equation）28 上述公式被称为贝尔曼最优化方程（Bellman optimality equation）。它表明，最优策略下的状态值必须等于该状态最佳动作的预期回报。人工智能原理马尔科夫决策过程的优化控制贝尔曼公式（Bellman equation）29最优状态值是：最优动作选择可以表示为：人工智能原理马尔科夫决策过程的优化控制优化控制方法30主要方法：基于模型（Model-based）、模型无关（Model-free）。v 基于模型的方法就是动态规划（Dynamic programming）。其基本假设是已知一个MDP模型，并且可以使用贝尔曼公式来计算价值函数和策略，大多数方法是计算状态价值函数（state value functions）。 用动态规划对马尔科夫决策过程进行优化控制，属于决策理论规划的范畴 本章。v 模型无关的方法就是强化学习（Reinforcement learning）。它通过与环境的互动形成模拟策略，生成状态转换和奖惩样本，再将这些样本用于估计状态-动作价值函数（state-action value functions）。 用强化学习对马尔科夫决策过程进行优化控制，属于机器学习的范畴 第11章。基于模型 vs 模型无关动态规划 vs 强化学习人工智能原理第8章 决策理论规划目录31o 决策理论规划概述o 马尔科夫模型o 马尔科夫决策过程的优化控制o 动态规划人工智能原理动态规划动态规划（Dynamic Programming）32将Dynamic Programming译成动态规划，是因为Programming的含义使然 1950年代初，美国数学家理查德贝尔曼（Richard Bellman）在研究多步决策过程（multistep decision process）的优化问题时，将多步过程转化为一系列单步问题，利用各阶段之间的关系逐个加以解决，从而创立了动态规划理论（Theory of Dynamic Programming）。在决策理论规划中，动态规划被用于对马尔科夫决策过程进行优化控制，计算马尔科夫决策过程的最优策略。 动态规划的两个核心方法：策略迭代（Policy iteration）和价值迭代（Value iteration），分别由罗纳德霍华德（Ronald A Howard）和理查德贝尔曼提出。It was first coined by Richard Bellman in the 1950s, a time when computer programming was an esoteric activity practiced by so few people as to not even merit a name. Back then programming meant “planning,” and “dynamic programming” was conceived to optimally plan multistage processes.人工智能原理动态规划策略迭代（Policy iteration）33策略迭代算法：1）策略评估（policy evaluation），计算当前策略的价值函数；2）策略改进（policy improvement），通过价值函数的最大化来计算改善的策略；3）重复上述操作，直到收敛于一个最优策略。人工智能原理动态规划策略评估（policy evaluation）34已知贝尔曼公式：人工智能原理动态规划策略评估（policy evaluation）35策略评估算法人工智能原理动态规划策略改进（policy improvement）36人工智能原理动态规划策略改进（policy improvement）37v 策略改进，是通过选择与原始策略价值函数有关的最佳动作来计算改善的策略。v 若该策略未能得到改变，则该策略已是最优、并且其价值函数满足最优价值函数的贝尔曼公式。策略改进算法人工智能原理动态规划价值迭代（Value iteration）38价值迭代算法实时计算必要的更新，将策略评估与策略改进结合在一起。其更新规则如下：在该计算中还产生了中间的Q值函数（Q-value function），形成如下序列：人工智能原理动态规划价值迭代（Value iteration）39价值迭代算法人工智能原理动态规划例：赌徒问题（Gamblers Problem）40(a) (b) 人工智能原理n 决策理论规划是将决策理论与人工智能规划相结合的产物，可用于求解不确定性、非完全可观测环境下的规划问题。n 马尔科夫决策过程是决策理论规划的形式框架。n 其要素：策略、奖惩、折扣、价值函数、以及贝尔曼公式等。n 其优化控制方法：基于模型、模型无关。n 基于模型的方法：就是动态规划，它的两个核心方法是策略迭代和价值迭代。n 模型无关的方法：就是强化学习，将在第11章中讲述。第8章 决策理论规划小结41Q & A42