光明随心订网站怎么做,网站打开是目录结构图,咨询律师免费解答,网站建设商标在哪个类别一、基本知识
1. 条件概率
条件概率是指在某件事情已经发生的前提下#xff0c;另一件事情在此基础上发生的概率#xff0c;举例来说P(A丨B)表示B发生的基础上#xff0c;A也发生的概率#xff0c;基本公式为#xff1a;
2. 条件期望
在上述概率下的期望我们称之为条…一、基本知识
1. 条件概率
条件概率是指在某件事情已经发生的前提下另一件事情在此基础上发生的概率举例来说P(A丨B)表示B发生的基础上A也发生的概率基本公式为
2. 条件期望
在上述概率下的期望我们称之为条件期望。 计算
3. 随机过程
在概率论概念中随机过程是随机变量的集合。若一随机系统的样本点是随机函数则称此函数为样本函数这一随机系统全部样本函数的集合是一个随机过程。实际应用中样本函数的一般定义在时间域或者空间域。
顾名思义它其实就是个过程比如今天下雨那么明天下不下雨呢后天下不下雨呢从今天下雨到明天不下雨再到后天下雨这就是个过程。那么怎么预测N天后到底下不下雨呢这其实是可以利用公式进行计算的随机过程就是这样一个工具把整个过程进行量化处理用公式就可以推导出来N天后的天气状况下雨的概率是多少不下雨的概率是多少。说白了随机过程就是一些统计模型利用这些统计模型可以对自然界的一些事物进行预测和处理比如天气预报比如股票比如市场分析比如人工智能。 随机过程是一族时间函数的集合随机过程的每个样本函数一个随机信号是一个确定的时间函数x(t)t0~T随机过程在一个确定的时刻t1是一个随机变量X(t1)。 从上述对随机过程描述中可以看出从信号分析的角度来看一个随机过程就是针对一个实验测量无数个的样本每个样本就是一个随机信号要分清什么是随机过程和随机信号而所有样本测量的时间都是0~T这看起来很麻烦和不可思议然后我们把这些样本每个随机信号放在一起摆放见图 其实这就是一个随机过程然后我们怎样描述呢我们从两个角度来描述它和上述定义对应。 1从图中纵向的角度0~T一个随机过程是你这次针对于某个任务进行测量的所有样本信号的集合。 2从横向的角度在0-T区间的任意时刻你可以拿把“菜刀”在任意时刻横着切一下这时你会看到所有你测量的样本信号在这个时刻的幅度值都不一样它们是随机的为了表征这些幅度值的统计特性我们用此时刻的随机变量X(t)来表征那么在0~T时间区间内有多少随机变量呢当然是无数个相当于你切了无数刀这些无数个随机变量的集合就是随机过程。 如果所有工作都像这样去做的话那么所有随机信号分析就没有办法完成了所以人们将问题进行简化尽量将随机过程说成平稳的并且具有各态历经的。 二、鞅martingale
在概率论中鞅martingale是满足下述条件的随机过程已知过去某一 时刻 s 以及之前所有时刻的观测值若某一时刻 t 的观测值的条件期望等于过去某一时刻 s 的观测值则称这一随机过程是鞅。而于博弈论中鞅经常用来作为公平博弈的数学模型。
鞅的原名 martingale 原指一类于18世纪流行于法国的投注策略称为加倍赌注法[1]。这类策略中最简单的一种策略是为博弈设计的。在博弈中赌徒会掷硬币若硬币正面向上赌徒会赢得赌本若硬币反面向上赌徒会输掉赌本。这一策略使赌徒在输钱后加倍赌金投注为的是在初次赢钱时赢回之前输掉的所有钱同时又能另外赢得与最初赌本等值的收益。当赌徒的财产和可用时间同时接近无穷时他掷硬币后硬币正面向上的概率会接近1由此看来加倍赌注法似乎是一种必然能赢钱的策略。然而赌金的指数增长最终会导致使用这一策略的赌徒破产。
鞅的概念首先是由保罗·皮埃尔·莱维于 1934 年提出的但他只提出了离散时间的版本而且没有给予命名。直到 1939 年约翰・维尔将此概念推广到连续时间的情况并且首次提出 martingale 这个名称。约瑟夫·利奥·杜布Joseph Leo Doob等人在鞅的相关理论的初期发展做出重大贡献而完成这些工作的部分动机是为了表明成功的投注策略不可能存在。此外伊藤清在分析应用方面作出了重要的贡献。从 1970 年代开始鞅论就在纯粹数学和应用数学的很多领域中有广泛的应用特别是在数学物理和金融数学中。
以下我们讨论T个离散阶段下鞅的相关定义和性质。
我们将一个随机试验的所有基本结果称为样本点记为 称其构成的集合文件样本空间 其对应的概率空间记为 记每个阶段的状态为S0S1, …, ST我们定义以下集合 Ft可以理解为t时刻前所有状态的信息即整个随机过程到达当前状态的所有可能路径。我们再定义: 这样一来F就包含了所有时刻所有状态所有路径的信息。以下的性质显而易见 因为现t2时刻的信息肯定是要多于t1时刻的。 我们继续有以下定义 接下来我们给出条件期望的基本性质
2.1 Martingale的定义
我们开始讨论鞅的定义鞅有以下三种等价的定义 我们以下证明三个定义是等价的 以上便是鞅的基本定义为了更好的理解鞅我们可以举个例子。 假设赌徒在t时刻有MtM_tMt 的财富如果赌局是公平的那么他未来财富的期望应当是与当前财富相同同时不受之前赌博策略的影响因为我们求的是条件期望。事实上martingale理论最早便是用于赌博策略的研究我们现在讨论的鞅是公平赌局也存在像上鞅和下鞅这样不公平赌局。至于为什么中文会翻译成鞅呢因为在法文里martingale有两层意思一是“倍赌策略”每输一局就赌资加倍只要赢一局就扳回所有损失二是“马缰绳”将其翻译成鞅马的缰绳是用了它的第二层含义。 2.2 Martingale, supermartingale, submartingale
鞅E[Xt∣Fs]XstsE[X_t | F_s] X_s tsE[Xt∣Fs]Xsts 上鞅E[Xt∣Fs]XstsE[X_t | F_s] X_s tsE[Xt∣Fs]Xsts 下鞅E[Xt∣Fs]XstsE[X_t | F_s] X_s tsE[Xt∣Fs]Xsts。 通俗理解Fs表示你在s时刻所掌握的所有信息那么E[Xt | Fs]就表示你在s时刻所掌握的所有信息对X在未来t时刻预期的判断如何和X在s时刻是一致的说明游戏是公平的上鞅说明对过程X是看衰的下鞅则是看好。 鞅是公平赌博下鞅是有利赌博上鞅是不利赌博。
鞅直观意义是一条有固定趋势的线。 考虑一个函数f(t)横轴是时间轴纵轴是函数值。这个函数可以是平的就是f(t)cf(t)cf(t)c也可以单调增也可以单调减。因此从图像上看是一条有固定趋势的线。 如果仅仅是线那么未免太乏味无趣。概率就是把固定取值的变量XcXcXc取代为可以同时取多个值、每个值都有一定权重的随机变量XXX相当于引入了多个可能状态。随机过程进一步引入一个时间轴考虑随机变量的序列XnX_nXn或者连续版本的XtX_tXt因此如果画在刚刚那个图里Xn(w)X_n(w)Xn(w)可以看做某个大体上是线、局部有些抖动的点列而XnX_nXn就是这些点列的集合。 那么离散鞅是一种点列集随机过程这个点列集大体趋势是f(t)cf(t)cf(t)c只是会有一些抖动而且是考虑一个抖动围绕这条线的点列集整体。类似的上鞅、下鞅就是单调减、单调增函数的点列集。
2.3 Stopping time
关于随机过程 X1X2X3… 的停时是随机变量 τ这一随机变量具有如下性质对于每一个时间 事件 τ t 的发生与否仅取决于 X1X2X3…Xt 的取值。从定义中可以感受到的直觉是在任一特定时刻 t我们都可以知道在这一时刻随机过程是否到了停时。现实生活中停时的例子如赌徒离开赌桌的时刻这一时刻可能是赌徒以前赢得钱财的函数例如仅当他没有钱时他才可能离开赌桌但是他不可能根据还未完成的博弈的结果来选择离开还是留下。
上述停时定义满足强条件下面给出一个弱条件的停时定义若事件 τ t 的发生与否统计独立于 Xt1Xt2… 但并不是完全决定于时刻 t 以及之前的过程历史则随机变量 τ 是停时。虽然这是一个弱条件但在需要用到停时的证明中的一些情况也算是足够强的条件。
鞅的一个基本性质是若(Xt)t0(X_{t})_{{t0}}(Xt)t0是下\上鞅且 τ\tauτ 是停时由 Xtτ:Xmin{τ,t}X_{t}^{\tau }:X_{{\min\{\tau ,t\}}}Xtτ:Xmin{τ,t}定义的对应停止过程(Xtτ)t0(X_{t}^{\tau })_{{t0}}(Xtτ)t0也是下\上鞅。
停时鞅的概念引出了一系列定理例如可选停止定理又称可选抽样定理在特定条件下停时的鞅的期望值等于其初始值。利用这一定理我们可以证明对于一个寿命有限且房产有限的赌徒成功的投注策略不可能存在。
2.3.1 Optional stopping theorem
In probability theory, the optional stopping theorem (or Doob’s optional sampling theorem) says that, under certain conditions, the expected value of a martingale at a stopping time is equal to its initial expected value. Since martingales can be used to model the wealth of a gambler participating in a fair game, the optional stopping theorem says that, on average, nothing can be gained by stopping play based on the information obtainable so far (i.e., without looking into the future). Certain conditions are necessary for this result to hold true. In particular, the theorem applies to doubling strategies.
The optional stopping theorem is an important tool of mathematical finance in the context of the fundamental theorem of asset pricing.
2.3.1.1 discrete-time version of the theorem 2.3.1.2 Applications 2.3.1.3 Proof 三、markov chain
3.1 Markov Property
在学习马尔可夫链之前我们首先了解一下什么是马尔可夫性质或者叫马尔可夫特性Markov Property。 假设你有一个系统这个系统具有MMM 种可能的状态并且在状态之间正在移动。真实世界中我们常常见到这种例子例如天气从炎热到温和或者是股票市场从熊市到牛市再到停滞的状态stagnant states。
3.1.1 马尔可夫性的定义
关于马尔可夫性我们给出了如下的Definition 从上述的式子可以看出t1时刻的状态包含了1,…,t时刻状态的全部历史信息并且当我们知道t时刻的状态后我们只关注于环境的信息而不用管之前所有状态的信息这就是马尔可夫性当论文中说某一状态或其他信息符合马尔可夫性时我们也应当联想到这个性质。
3.1.2 State Transition Matrix状态传输矩阵 如果一个过程具有马尔可夫性质它也被成为马尔可夫过程Markov Process。
3.2 Markov Processes马尔可夫过程
在概率论及统计学中马尔可夫过程英语Markov process是一个具备了马尔可夫性质的随机过程因为俄国数学家安德雷·马尔可夫得名。马尔可夫过程是不具备记忆特质的memorylessness。换言之马尔可夫过程的条件概率仅仅与系统的当前状态相关而与它的过去历史或未来状态都是独立、不相关的。
3.3 markov chain马尔可夫链
具备离散状态的马尔可夫过程通常被称为马尔可夫链。
3.3.1 定义与解释
3.3.1.1 定义举例1 3.3.1.2 定义举例2
Markov Chain 体现的是状态空间的转换关系下一个状态只决定于当前的状态.通俗点说就是你下一时刻在哪只跟你现在在哪有关于你以前去过哪没有关系. 如下图 这个状态图的转换关系可以用一个转换矩阵 T 来表示 举一个例子如果当前状态为 u(x) (0.5, 0.2, 0.3), 那么下一个矩阵的状态就是 u(x)T (0.18, 0.64, 0.18), 依照这个转换矩阵一直转换下去最后的系统就趋近于一个稳定状态 (0.22, 0.41, 0.37) 。而事实证明无论你从那个点出发经过很长的 Markov Chain 之后都会汇集到这一点。
满足什么条件下经过很长的 Markov Chain 后系统会趋近一个稳定状态呢大概的条件如下
Irreducibility. 即图是联通的各个状态之间都有过去的办法举个不联通的例子比如爬虫爬不到内部局域网的网页Aperiodicity. 非周期性, 即图中遍历不会陷入到一个死圈里进去了再也出不来有些网站为了防机器人会专门设置这种陷阱Detailed Balance这是保证系统有稳态的一个重要条件详细说明见下面。 假设 p(x) 是最后的稳态那么 detailed balance 可以用公式表示为 什么意思呢假设上面状态图 x1 有 0.22 元 x2 有 0.41 元x3 有 0.37 元那么 0.22×1 表示 x1 需要给 x2 钱以此类推手动计算可以发现下一个状态每个人手中的钱都没有变。值得说明的是这里体现了一个很重要的特性那就是从一个高概率状态 xi 向一个低概率状态 x(i-1) 转移的概率等于从这个低概率状态向高概率状态转移的概率reversible至于要不要转移又是另外一回事)ergodicity, 遍历性是指不管事物现在出于什么状态在较长时间内马尔科夫过程逐渐趋于稳定状况而且稳定状态与初始状况无关。
3.3.1.3 通俗解释
先说说我们村智商为0的王二狗人傻不拉几的见人就傻笑每天中午12点的标配仨状态吃玩睡。这就是传说中的状态分布。 你想知道他n天后中午12点的状态么是在吃还是在玩还是在睡这些状态发生的概率分别都是多少 先看个假设他每个状态的转移都是有概率的比如今天玩明天睡的概率是几今天玩明天也玩的概率是几几看图更清楚一点。 这个矩阵就是转移概率矩阵P并且它是保持不变的就是说第一天到第二天的转移概率矩阵跟第二天到第三天的转移概率矩阵是一样的。这个叫时齐有兴趣的同学自行百度。 有了这个矩阵再加上已知的第一天的状态分布就可以计算出第N天的状态分布了。 S1 是4月1号中午12点的的状态分布矩阵 [0.6, 0.2, 0.2]里面的数字分别代表吃的概率玩的概率睡的概率。 那么 4月2号的状态分布矩阵 S2 S1 * P (俩矩阵相乘)。 4月3号的状态分布矩阵 S3 S2 * P (看见没跟S1无关只跟S2有关)。 4月4号的状态分布矩阵 S4 S3 * P (看见没跟S1S2无关只跟S3有关)。 … 4月n号的状态分布矩阵 Sn Sn-1 * P (看见没只跟它前面一个状态Sn-1有关)。
总结马尔可夫链就是这样一个任性的过程它将来的状态分布只取决于现在跟过去无关
就把下面这幅图想象成是一个马尔可夫链吧。实际上就是一个随机变量随时间按照Markov性进行变化的过程。 附S2 的计算过程 (没兴趣的同学自行略过)
3.3.2 n步转移概率
除了一步转移以外马尔科夫链还有n步转移即通过n次达到目标状态 其实是Markov Chain 的基本性质“无后效性”即事物将来的状态及其出现的概率的大小只取决于该事物现在所处的状态而与以前时间的状态无关
3.3.2.1 C-K方程
查普曼-柯尔莫格洛夫方程(Chapman-Kolmogorov equation,C-K equation)给出了计算 [公式] 步转移概率的一个方法
3.3.3 状态分类
①可达的i到j的概率为正
②常返的从i出发后还能再回到i
③非常返的从i出发后不一定能回到j
常返和非常返的区别常返指出发后可以无限次回到自身非常返并不是无法回到自身而是只能有限次回到自身。
常返类相互可达的状态组。
马尔科夫链的分解
一个马尔科夫链可以分解成一个或者多个常返类加上可能的非常返类。一个常返态从它所属的类里任何一个状态出发都是可达的但从其他类里的常返状态出法是不可达的。从任何一个常返状态出发都不可到达非常返状态从一个非常返状态出发至少有一个常返态是可达的
常返类的周期
若一个常返类能被分成几个组这几个组之间的下一个状态转移必定不在自己组。则这个常返类被称为有周期的。 命题得证。
很显然暂态也是一个类性质。而利用上述性质可以得到有限马尔可夫链的所有状态不可能都是暂态有限不可约马尔可夫链的所有状态都是常返态。
3.3.4 稳态 3.3.4.1 稳态概率举例1 3.3.4.2 稳态概率举例2
举个具体的例子。社会学家把人按其经济状况分为3类下层中层上层我们用1,2,3表示这三个阶层。社会学家发现决定一个人的收入阶层最重要的因素就是其父母的收入阶层。如果一个人的收入属于下层类别则它的孩子属于下层收入的概率为0.65属于中层收入的概率为0.28属于上层收入的概率为0.07。从父代到子代收入阶层转移概率如下 我们用P表示这个转移矩阵则 假设第1代人的阶层比例为 则前10代人的阶层分布如下 我们可以看到在相同的转移矩阵作用下状态变化最终会趋于平稳。对于第n代人的阶层分布我们有 从表达式上我们可以看到π是一维向量P是两维矩阵P进行足够多次自乘后值趋于稳定。
3.3.5 马氏链平稳分布
在转移矩阵P作用下达到的平稳状态我们称之为马氏链平稳分布。对于这个特性有如下精彩定理 我在这里直观的解释一下上面定理
条件 1非周期马氏链马氏链转移要收敛就一定不能是周期性的。不做特别处理我们处理的问题基本上都是非周期性的在此不做多余解释。 2存在概率转移矩阵P任意两个状态是连通的这里的连通可以不是直接相连只要能够通过有限次转移到达即可。比如对于a, b, c状态存在a-b, b-c则我们认为a到c是可达的。 结论 1不论初始状态是什么经过足够多次概率转移后会存在一个稳定的状态π。 2概率转移矩阵自乘足够多次后每行值相等。即 3.3.5.1 马尔科夫链平稳状态定理的物理解释
我们再用一个更加简单的例子来阐明这个定理的物理含义。假设城市化进程中农村人转移为城市人的概率为0.5城市人转移为农村人的概率为0.1。
假设一开始有100个农村人0个城市人每代转移人数如下 可以看到城市化进程中马尔科夫平稳状态就是农村人转移为城市人的速度等于城市人转移为农村人的速度。对于上述转移矩阵P平稳分布为农村人17%城市人83%。如果我们可以得到当前中国城市化转移矩阵P我们就可以算出中国最终城市化率大概为多少这里不考虑P的变化。同时如果我们知道了中国城市化人口比例我们就能知道城市化进程还可以持续多少代人。
3.3.5.2 长期频率解释 3.3.6 Birth-Death process 生灭过程 3.3.6.1 平稳分布 3.3.6.2 性质 3.3.6.3 例子 3.3.6.4 Probability balance equations 概率平衡方程 3.3.7 吸收概率和吸收期望时间 3.3.7.1 平均时间
平均吸收时间i的平均吸收时间为从状态i开始直到到达吸收态所需要的期望步数
平均吸收时间计算解平均吸收时间方程组
3.3.8 为什么马尔可夫链这么重要
因为它的静态分布或叫平稳性分布stationary distribution性质。 我们用一下Wiki上给出的股票市场的例子见下图这是一个具有静态空间的马尔可夫链a continuous-time Markov chain with state-space包含了 牛市、熊市、停滞市场三种状态Bull market, Bear market, Stagnant market 。 它各状态之间由转移概率组成的转移矩阵 transition rate matrix如下记为 Q 你可以尝试从其他状态出发但最终的静态分布一定是相同的。那么得出这个静态分布有什么用处呢
静止状态分布的重要性在于它可以让你在随机的时间里对于一个系统的任意一个状态确定其概率。The stationary state distribution is important because it lets you define the probability for every state of a system at a random time.
对于上述例子你可以说整个系统62.5%的概率系统将处于牛市31.25%的概率将处于熊市而6.25%的概率将处于停滞态。
直观上说你可以想想成在一个状态链上进行随机游走。你在一个状态出然后你决定你前往下一个状态的方法是在给定当前状态下观察下一个状态的概率分布。
3.3.9 小结
马尔科夫链是一个数学对象包含一系列状态以及状态之间的转移概率如果每个状态转移到其他状态的概率只与当前状态相关那么这个状态链就称为马尔科夫链。有这样一个马尔科夫链之后我们可以任取一个初始点然后根据状态转移概率进行随机游走。假设能够找到这样一个马尔科夫链其状态转移概率正比于我们想要采样的分布如贝叶斯分析中的后验分布采样过程就变成了简单地在该状态链上移动的过程。
3.4 连续时间马尔科夫链CTMC
3.4.1 定义
3.4.1.1 定义1:一般定义 和起始时间t无关的话我们称这是时间齐次的马尔科夫链。这个转移矩阵和离散时间不同的是离散时间给出的是一步转移概率但是连续马尔科夫链的转移概率给出的是和时间相关的。
3.4.1.2 定义2
我们考虑连续时间马尔科夫链从一个状态 i开始到状态发生变化比如变成j所经过的时间由于马尔科夫链的马尔科夫性这个时间是具有无记忆性的所以这个时间是服从指数分布的。这和离散时间马尔科夫链是密切相关的离散时间马尔科夫链中的时间是离散时间因为由无记忆性所以是服从几何分布的。
这样我们就可以这样定义连续时间马尔科夫链。马尔科夫链是这样的一个过程。
(i)在转移到不同的状态 iii前它处于这个状态的时间是速率为viv_ivi的指数分布。(ii)当离开状态 iii时以某种概率PijP_{ij}Pij进入下一个状态jjj,当然PijP_{ij}Pij满足
对比于半马尔科夫链我们可以发现连续时间马尔科夫链是一种特殊的半马尔科夫链在一个状态所待的时间是只不过是一个具体的分布–指数分布而半马尔科夫链只是说所待的时间是任意的一个随机时间。 3.4.1.3 定义3 3.4.1.4 举例 3.4.2 两个定义(1和2)之间的关系 3.4.3 CTMC的极限概率 3.4.4 CTMC极限分布的应用 3.4.5 时间可逆性 3.4.6 截止的马尔科夫链 四、martingale与markov chain的关系
二者都是随机过程中的一种过程。
Martingale的词本意是指马车上马夫控制马前进的缰绳如果我记得没错的话所以从词源来看刻画了一种过程前进未来与现在出发点关系的含义。具体来说缰绳的作用是使得马车的前进方向与现在所冲的方向一致所以在概率上来解释就是未来发生的所有路径可能性的期望值与现在的出发点一致。
从这个意义上来说Matingale的核心是说明了一个过程在向前演化的过程中的稳定性性质。但它并没有说明这个过程是如何到达这一时间点的是否由上一个时间点所在的位置决定matingale并没有说明。再用马车的例子来说Martingale告诉了你马车在未来是怎么向前走的中间会有左右的波动比如马、车夫走神了路上有坑马要绕开etc.但整体来说马是沿着一条直线向前走的。
而马尔科夫过程的核心在于点明了过程的演化是无记忆性的。还拿马车来举栗子假设车夫喝醉了他没有意识并在一个很大的广场马车下一刻前进的方向并不需要是一条直线经过车夫与马的直线这种情况下缰绳是绷直的是martingale或者说缰绳由于车夫没绷紧是松垮的这种情况下马车在下一刻可以去任何一个方向整体上来说前进方向也不必须有什么稳定性规律可循但整个过程唯一的共性是马迈出前腿的时候能够到达的所有可能范围是由它的后腿你现在所在的位置决定的但马可能扭一扭屁股身子弯曲一下所以不必须走直线不必需走直线不必需走直线而并没有由上一步马所在的位置决定这也就是所谓的无记忆性。
所以从这两个角度来理解两个名词
有共性
都从一个过程的全生命角度描画了一个过程的演进性质
有重叠 当还是马车例子的时候,martingale也是一个markov因为虽然走直线但下一刻的位置还是只由现在决定只是马身子不能扭曲不能改变方向这个例子在概率上最熟悉的模型就是brownian motion了而反过来马车未来位置由现在决定又走直线所以此时markov process 也是一个martingale 例子还是brownian motion
但更重要的是两个过程本质上不是在讲一回事比如还是马车车夫喝醉了但走在一个三维空间这时候它是一个markov process,但是由于方向不确定此时已经不是martingale而变成了一个local martingale 而反过来假设有一个错帧宇宙空间共享但时间差一天这时候同一个马车走在不同的宇宙里但行走轨迹独立缰绳拉直此时两架马车都走之前两架马车组成的系统是一个martingale但是由于下一时刻前进的方向与宇宙1中的此时有关也与宇宙2中的昨天有关所以两架马车组成的系统就不再是一个markov了。
总结一下brownian motion (wiener process)既是markov process 又是 martingale; 而markov process 与martingale是相交而非包含与反包含关系。只能说你中有我我中有你但你不属于我我也不属于你
五、Monte Carlo
5.1 蒙特卡罗方法引入
蒙特卡洛Monte Carlo方法来自于摩纳哥的蒙特卡洛赌场许多纸牌类游戏需要计算其胜利的概率。用它作为名字大概是因为蒙特卡罗方法是一种随机模拟的方法这很像赌博场里面的扔骰子的过程。最早的蒙特卡罗方法都是为了求解一些不太好求解的求和或者积分问题。比如积分 如果我们很难求解出f(x)的原函数那么这个积分比较难求解。当然我们可以通过蒙特卡罗方法来模拟求解近似值。(我们可以将蒙特卡洛理解为简单的模拟通过模拟的情景来计算其发生的概率。) 如何模拟呢假设我们函数图像如下图:
5.2 概率分布采样
上一节我们讲到蒙特卡罗方法的关键是得到x的概率分布。如果求出了x的概率分布我们可以基于概率分布去采样基于这个概率分布的n个x的样本集带入蒙特卡罗求和的式子即可求解。但是还有一个关键的问题需要解决即如何基于概率分布去采样基于这个概率分布的n个x的样本集。
5.3 接受-拒绝采样 5.4 蒙特卡罗方法小结
使用接受-拒绝采样我们可以解决一些概率分布不是常见的分布的时候得到其采样集并用蒙特卡罗方法求和的目的。但是接受-拒绝采样也只能部分满足我们的需求在很多时候我们还是很难得到我们的概率分布的样本集。比如 从上面可以看出要想将蒙特卡罗方法作为一个通用的采样模拟求和的方法必须解决如何方便得到各种复杂概率分布的对应的采样样本集的问题。而马尔科夫链就是帮助找到这些复杂概率分布的对应的采样样本集的白衣骑士。
5.5 应用场景
通常情况下许多概率的计算非常复杂甚至是无法计算的但是我们可以通过计算机对期待发生的场景进行大量的模拟从而计算出其发生的概率。简单的公式表达为 学习过概率的同学应当知道这就是典型的频率学派的观点。 对于蒙特卡洛方法经典的例子就是计算π\piπ值。在-11之间随机取两个数如果在单位圆内则记一次在圆外则不计入次数。
import random
import numpy as np
from math import sqrt, pinum1 1000 # simulation times
freq1 0
x1 []
y1 []
for i in range(1,num11):x_i, y_i random.uniform(-1, 1), random.uniform(-1, 1)square_distance x_i**2y_i**2x1.append(x_i)y1.append(y_i)if square_distance 1: # 圆的方程x^2y^21freq1 1simulation_pi1 4*freq1/num1;num2 10000 # simulation times
freq2 0
x2 []
y2 []
for i in range(num2):x_i, y_i random.uniform(-1, 1), random.uniform(-1, 1)square_distance x_i**2y_i**2x2.append(x_i)y2.append(y_i)if square_distance 1: # 圆的方程x^2y^21freq2 1simulation_pi2 4*freq2/num2;% matplotlib inline
import matplotlib.pyplot as pltfig, ax plt.subplots(figsize(8,8))theta np.linspace(0,2*pi,500)
x,y np.cos(theta), np.sin(theta)
ax.plot(x, y, colorred, linewidth1.0)ax.scatter(x1,y1,colorblue,alpha0.75)
ax.set_xlim(-1,1);
ax.set_ylim(-1,1);结果为 真实的pi值 3.141592653589793 蒙特卡洛方法下得出的pi值模拟1000次 3.188 相对误差模拟1000次 1.4771917153924754 % 蒙特卡洛方法下得出的pi值模拟10000次 3.1292 相对误差模拟10000次 0.39447041536821975 % 5.6 小结
蒙特卡洛就是一种模拟事情发生的方法。
六、MCMC
从名字我们可以看出MCMC由两个MC组成即蒙特卡罗方法Monte Carlo Simulation简称MC和马尔科夫链Markov Chain 也简称MC。 Monte Carlo 蒙特卡罗的核心是寻找一个随机的序列。
蒙特卡洛马尔可夫链 Markov Chain Monte Carlo简称MCMC是一个抽样方法用于解决难以直接抽样的分布的随机抽样模拟问题。用来在概率空间通过随机采样估算兴趣参数的后验分布。 那MCMC到底是什么呢《告别数学公式图文解读什么是马尔可夫链蒙特卡罗方法》里面这样解释MCMC方法是用来在概率空间通过随机采样估算兴趣参数的后验分布。 说的很玄蒙特卡罗本来就可以采样马尔科夫链可以采样为啥要将他们合在一起下面给出两个动机后面将从蒙特卡罗开始一直推到gibbs采样来深入了解为什么需要MCMC。 再次感谢刘建平MCMC他是网上写的最详细的——将整个脉络梳理出来了看完收获很多。本文几乎涵盖了它所有内容因此只能算一篇读书笔记。 简而言之就是用马尔科夫链方法来抽样。
抽样算法的主要任务是找到符合给定分布p(x)的一系列样本。对于简单的分布可以通过基本的抽样算法进行抽样。大多数分布都是不容易直接抽样的马尔可夫链蒙特卡罗算法解决了不能通过简单抽样算法进行抽样的问题是一种重要的实用性很强的抽样算法。
马尔可夫链蒙特卡罗算法简写为MCMC的核心思想是找到某个状态空间的马尔可夫链使得该马尔可夫链的稳定分布就是我们的目标分布p(x)。这样我们在该状态空间进行随机游走的时候每个状态x的停留时间正比于目标概率p(x)。在用MCMC进行抽样的时候我们首先引进一个容易抽样的参考分布q(x)在每步抽样的过程中从q(x)里面得到一个候选样本y, 然后按照一定的原则决定是否接受该样本该原则的确定就是要保证我们得到的原本恰好服从p(x)分布。
在了解什么是MCMC的时候我们需要考虑一个情况。举例我们已经知道一个分布例如beta分布的概率密度函数PDF那么我们怎么样从这个分布中提取样本呢
MCMC给我们提供了一种方式来从概率分布中进行采样而这种方法在贝叶斯统计中的后验概率进行采样十分方便。 6.1 动因
MCMC通常用于解决高维度的积分和最优化问题这两种问题也是机器学习、物理、统计、计量等领域的基础。比如
6.2 MCMC的定义
Wikipedia的解释如下:
Markov Chain Monte Carlo (MCMC) methods are a class of algorithms for sampling from a probability distribution based on constructing a Markov chain that has the desired distribution as its stationary distribution. The state of the chain after a number of steps is then used as a sample of the desired distribution. The quality of the sample improves as a function of the number of steps. 马尔可夫链蒙特卡罗方法是一类以期望分布为平稳分布的马尔可夫链为基础对概率分布进行抽样的算法。经过一系列步骤之后链的状态将用作期望分布的样本。样品的质量随着步骤数量的增加而提高。 MCMC方法提供了可以创建一个以Beta分布为其平稳分布stationary distribution的马尔科夫链的算法从而使取样变得简单因为我们可以从一个均匀分布中取样(这相对容易)。
如果我们基于一些算法重复地从一个随机的状态开始遍历到下一个状态我们将会创建一个马尔可夫链一个以beta分布作为其平稳分布的马尔可夫链。
这类算法一个典型的代表就是Metropolis-Hastings Algorithm算法。
MCMC由梅特罗波利斯(Metropolis)于1949年基于马尔可夫链的基本性质提出下面介绍一下与马尔可夫链相关的性质。
6.3 相关性质
一、稳定分布
稳定分布是指当我们给定状态空间的一个初始分布π0\pi_0π0以后按照转移矩阵进行跳转最终达到的稳定状态。 即每个状态的流出概率等于该状态注入的概率该方程称为全局平衡方程。满足该方程的分布称为转移矩阵A的稳定分布。
二、细致平衡
对于一个稳定分布我们可以给其一个更强的条件限制使得任意一个状态iii满足如下条件 下面我们介绍基本的梅特罗波利斯算法(Metropolis algorithm)。假设p(x)是我们的目标分布函数我们想得到一系列服从该分布的样本。我们考虑样本的产生过程构成一个马尔可夫链并且让p(x)是该马尔可夫链的稳定分布那么该样本序列就服从p(x)。现在p(x)是已知的问题的关键在于如何构造这个产生过程也即如何构造马尔可夫链。 即目标概率p(x)满足细致平衡方程因此p(x)是转移概率的稳定分布。
最后回顾一下梅特罗波利斯抽样的主要思想。我们首先构造了一个马尔可夫链接着证明了p(x)满足其细致平衡方程进而说明p(x)是该链的稳定分布。然后将抽样的过程看成是在马尔可夫链状态空间进行跳转的过程跳转的候选状态由参考分布q(x)产生。最后 得到一个的跳转序列该序列在每个状态x的停留时间与p(x)成比即服从p(x)分布。
6.4 Metropolis-Hastings (MH) Algorithm算法
梅特罗波利斯黑斯廷斯算法英语Metropolis–Hastings algorithm是统计学与统计物理中的一种马尔科夫蒙特卡洛MCMC方法用于在难以直接采样时从某一概率分布中抽取随机样本序列。得到的序列可用于估计该概率分布或计算积分如期望值等。梅特罗波利斯黑斯廷斯或其他MCMC算法一般用于从多变量尤其是高维分布中采样。对于单变量分布而言常会使用自适应判别采样adaptive rejection sampling等其他能抽取独立样本的方法而不会出现MCMC中样本自相关的问题。
该算法的名称源于美国物理学家尼古拉斯·梅特罗波利斯与加拿大统计学家W·K·黑斯廷斯
为了更形象地理解这个算法我们用下面这个例子来类比。假设我们想知道某个湖的水容量以及这个湖中最深的点湖水很浑浊以至于没法通过肉眼来估计深度而且这个湖相当大网格近似法显然不是个好办法。为了找到一个采样策略我们请来了两个好朋友小马和小萌。经过讨论之后想出了如下办法我们需要一个船当然也可以是竹筏和一个很长的棍子这比声呐可便宜多了而且我们已经把有限的钱都花在了船上。
1随机选一个点然后将船开过去。
2用棍子测量湖的深度。
3将船移到另一个地点并重新测量。
4按如下方式比较两点的测量结果。
如果新的地点比旧的地点水位深那么在笔记本上记录下新的测量值并重复过程2。如果新的地点比旧的地点水位浅那么我们有两个选择接受或者拒绝。接受意味着记录下新的测量值并重复过程2拒绝意味着重新回到上一个点再次记录下上一个点的测量值。
如何决定接受还是拒绝新的测量值呢这里的一个技巧便是使用Metropolis-Hastings准则即接受新的测量值的概率正比于新旧两点的测量值之比。
事实上理论保证了在这种情形下如果我们能采样无数次最终能得到完整的后验。幸运地是实际上对于很多问题而言我们只需要相对较少地采样就可以得到一个相当准确的近似。
6.5 数学表达 6.6 算法介绍 6.7 MCMC 采样
6.7.1 背景
给定一个的概率分布 P(x), 我们希望产生服从该分布的样本。
前面介绍过一些随机采样算法如拒绝采样、重要性采样可以产生服从特定分布的样本但是这些采样算法存在一些缺陷如难以选取合适的建议分布只适合一元随机变量等。
下面将介绍一种更有效的随机变量采样方法MCMC 和 Gibbs采样这两种采样方法不仅效率更高而且适用于多元随机变量的采样。
6.7.2 随机矩阵
在MCMC采样中先随机一个状态转移矩阵Q然而该矩阵不一定能满足细致平稳定理一次会做一些改进具体过程如下
6.7.3 算法具体流程
MCMC采样算法的具体流程如下
6.7.4 MCMC: Metropolis-Hastings algorithm
然而关于MCMC采样有收敛太慢的问题所以在MCMC的基础上进行改进引出M-H采样算法 M-H 算法的具体流程如下 M-H算法在高维时同样适用
6.7.4.1 基本概念
从一个概率分布目标分布P(x)P(x)P(x)中得到随机样本序列 这个序列可以用于a) 近似估计分布P(x)P(x)P(x); b) 计算积分(期望) 用于高维分布取样 缺陷: MCMC固有缺点, 样本自相关性
6.7.4.2 优势
可以从任意的概率分布P(x)P(x)P(x)中取样只要满足条件函数f(x)成比例于P(x)P(x)P(x)的密度。 更宽松的要求f(x)f(x)f(x)仅需要与P(x)P(x)P(x)的密度成比例。
6.7.4.3 要点
生成样本值序列样本值产生得越多这些值的分布就越近似于P(x)P(x)P(x)迭代产生样本值下一个样本的分布仅仅取决于当前样本值马尔科夫链特性接受/拒绝概率接受计算出的值为下一个样本值/拒绝并重复使用当前样本值基于P(x)P(x)P(x)接受概率通过比较f(xt)f(x_t)f(xt)当前值和f(x′)f(x)f(x′)备选值得出
6.7.5 Metropolis Algorithm (对称分布)
Input: f(x)f(x)f(x)与目标分布P(x)P(x)P(x)成比例的函数
6.7.5.1 初始化 6.7.5.2 迭代ttt 6.7.6 缺陷
样本自相关相邻的样本会相互相关虽然可以通过每nnn步取样的方式来减少相关性但这样的后果就是很难让样本近似于目标分布P(x)P(x)P(x)。 自相关性可通过增加步调长度jumping width与jumping function g(x∣y)g(x|y)g(x∣y)的方差有关来控制但同时也增加了拒绝备选样本的几率α\alphaα。过大或过小的jumping size会导致slow-mixing Markov Chain, 即高度自相关的一组样本以至于我们需要得到非常大的样本量nnn才能得到目标分布P(x)P(x)P(x)。 初始值的选择尽管Markov Chain最后都会收敛到目标分布然而初始值的选择直接影响到运算时间尤其是把初始值选在在了“低密度”区域。因此选择初值时最好加入一个“burn-in period”预烧期预选期。
6.7.7 优势
抗“高维魔咒”curse of dimensionality维度增加对于rejection sampling方法来说拒绝的概率就是呈指数增长。而MCMC则成为了解决这种问题的唯一方法多元分布中为了避免多元初始值以及 g(x∣y)g(x|y)g(x∣y)选择不当而导致的问题Gibbs sampling是另外一个更适合解决多元分布问题的MCMC 方法。Gibbs sampling从多元分布的各个维度中分别选择初始值然后这些变量分别同时取样。
6.7.8 衍生算法 6.7.9 小结
一般来说M-H采样算法较MCMC算法应用更广泛然而在大数据时代M-H算法面临着两个问题
1在高维时的计算量很大算法效率很低同时存在拒绝转移的问题也会加大计算量
2由于特征维度大很多时候我们甚至很难求出目标的各特征维度联合分布但是可以方便求出各个特征之间的条件概率分布因此就思考是否能只知道条件概率分布的情况下进行采样。
6.8 Gibbs 采样 6.8.1 二维的流程
因此可以得出在二维的情况下Gibbs采样算法的流程如下
6.8.2 多维
而在多维的情况下比如一个n维的概率分布π(x1, x2, …xn)我们可以通过在n个坐标轴上轮换采样来得到新的样本。
对于轮换到的任意一个坐标轴xi上的转移马尔科夫链的状态转移概率为 P(xi|x1, x2, …, xi−1, xi1, …, xn)即固定n−1个坐标轴在某一个坐标轴上移动。
而在多维的情况下Gibbs采样算法的流程如下
6.8.3 小结
由于Gibbs采样在高维特征时的优势目前我们通常意义上的MCMC采样都是用的Gibbs采样。
当然Gibbs采样是从M-H采样的基础上的进化而来的同时Gibbs采样要求数据至少有两个维度一维概率分布的采样是没法用Gibbs采样的这时M-H采样仍然成立。
6.9 其他算法
除了最常见的MH那几个算法后来还有很多新的比较惊艳的算法出现比如说slice samplingelliptical slice samplinggeneralized elliptical slice sampling上面说的BPS forward event chain MC还有和神经网络结合的NNGHMCA-Nice-MC以及利用了batch optimization思想的stochastic gradient HMC以及stochastic gradient Langevin dynamic等。
6.10 参考资料
以下为列表链接见原文
统计之都-MCMC
HANS-MCMC 算法及其应用
知乎-MCMC 专栏
机器学习之MCMC算法
知乎-MCMC 算法
知乎-MCMC 算法中接受概率是什么意思
MCMC 和 Metropolis–Hastings 算法
马尔可夫链蒙特卡洛(MCMC)算法
CSDN-MCMC
MCMC相关算法介绍及代码实现
算法资料 http://civs.stat.ucla.edu/MCMC/MCMC_tutorial.htm
http://www.soe.ucsc.edu/classes/cmps290c/Winter06/paps/mcmc.pdf
http://public.lanl.gov/kmh/talks/maxent00b.pdf
http://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo
google keywords MCMC tutorial
MCMC preprint service:
http://www.statslab.cam.ac.uk/~mcmc/
David MacKay’s book (electronic version availiable):
http://www.inference.phy.cam.ac.uk/mackay/itila/
Radford M. Neal’s review: Probabilistic Inference using Markov Chain Monte Carlo Methods
http://www.cs.toronto.edu/~radford/review.abstract.html
6.11 代码实现MCMC采样beta分布
import random
# Lets define our Beta Function to generate s for any particular state.
# We dont care for the normalizing constant here.def beta_s(w,a,b): # beta distribution pdfreturn w**(a-1)*(1-w)**(b-1)# This Function returns True if the coin with probability P of heads comes heads when flipped.
def random_coin(p):unif random.uniform(0,1)if unifp:return Falseelse:return True# This Function runs the MCMC chain for Beta Distribution.
def beta_mcmc(N_hops,a,b):states []cur random.uniform(0,1)for i in range(0,N_hops):states.append(cur)next random.uniform(0,1)ap min(beta_s(next,a,b)/beta_s(cur,a,b),1) # Calculate the acceptance probabilityif random_coin(ap):cur nextreturn states[-1000:] # Returns the last 1000 states of the chain在定义了相关函数后我们来检查一下我们采样的结果和实际beta概率分布之间的差距
import numpy as np
from matplotlib import pylab as pl
import scipy.special as ss
% matplotlib inline
plt.rcParams[figure.figsize] (17.0, 4.0)# Actual Beta PDF.
def beta(a, b, i):e1 ss.gamma(a b)e2 ss.gamma(a)e3 ss.gamma(b)e4 i ** (a - 1)e5 (1 - i) ** (b - 1)return (e1/(e2*e3)) * e4 * e5# Create a function to plot Actual Beta PDF with the Beta Sampled from MCMC Chain.
def plot_beta(a, b):Ly []Lx []i_list np.mgrid[0:1:100j]for i in i_list:Lx.append(i)Ly.append(beta(a, b, i))pl.plot(Lx, Ly, labelReal Distribution: astr(a), bstr(b))plt.hist(beta_mcmc(100000,a,b),densityTrue,bins 25, histtypestep,labelSimulated_MCMC: astr(a), bstr(b))pl.legend()pl.show()plot_beta(0.1, 0.1)
plot_beta(1, 1)
plot_beta(2, 3)相关图形如下所示 从上面的采样值可以看出我们的采样值还是很接近beta分布本身。虽然我们用了beta分布最为例子但实际上其他的分布也是可以类似来进行采样。
针对那些我们无法直接利用共轭分布得到的后验分布特别是高维的分布MCMC方法更显的尤为重要。
6.12 MH Algorithm的进一步说明
从贝叶斯的角度看Metropolis-Hastings算法使得我们能够从任意分布中以概率p(x)得到采样值只要我们能算出某个与p(x)成比例的值。这一点很有用因为在类似贝叶斯统计的许多问题中最难的部分是计算归一化因子也就是贝叶斯定理中的分母。Metropolis-Hastings算法的步骤如下 最后我们会得到一连串记录值有时候也称采样链或者迹。如果一切都正常进行那么这些采样值就是后验的近似。在采样链中出现次数最多的值就是对应后验中最可能的值。该过程的一个优点是后验分析很简单我们把对后验求积分的过程转化成了对采样链所构成的向量求和的过程。
强烈建议阅读以下博文作者用一个简单的例子实现了metropolis方法并将其用于求解后验分布文中用非常好看的图展示了采样的过程同时简单讨论了最初选取的步长是如何影响结果的。 https://github.com/findmyway/Bayesian-Analysis-with-Python/blob/master/MCMC-sampling-for-dummies.ipynb
6.13 一句话总结MCMC
MCMC generates samples from the posterior distribution by constructing a reversible Markov-chain that has as its equilibrium distribution the target posterior distribution. https://twiecki.io/blog/2015/11/10/mcmc-sampling/
6.14 MCMC如何解决具体问题
寻找p(x)最大值simulated annealing转换核的混搭和循环Gibbs 抽样Monte Carlo EM期望-最大化辅助变量抽样Auxiliary variable samplers)可逆跳跃MCMCReversible jump MCMC
-----------------------------------** 链接 https://zhuanlan.zhihu.com/p/83314877 https://www.zhihu.com/question/26887292/answer/310904395 https://zh.wikipedia.org/wiki/%E9%9E%85_(%E6%A6%82%E7%8E%87%E8%AE%BA) https://www.zhihu.com/question/52778636/answer/133133860 https://www.zhihu.com/question/31173033/answer/113202955 https://zhuanlan.zhihu.com/p/116725922 https://zhuanlan.zhihu.com/p/86995916 https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm https://zhuanlan.zhihu.com/p/37121528 https://houbb.github.io/2020/01/28/math-05-mcmc https://zhuanlan.zhihu.com/p/21112618
