MCTS
01
如果有一个10*10的正方形网格。在这个网格上画了一些图形，且我们不知道它具体是什么样的。但你可以通过一个函数f(x，y)来感知这个图形，其中(x，y)是坐标，输出是1(该点在图形内)或0(在图形外)。应如何算出图形面积?
答案很简单。用统计学的定律——大数定律就能搞定，即一个函数被随机抽样的次数越多，其近似值就越准确。那么，解法就是在10×10的网格中随机选择点，数一数有多少个点落在图形内，然后再除以采样点总数。
虽然这个关于随机抽样的思路简单而朴素，但它在很多领域都能大展身手，从法律到气候预测。不过本文写的是机器学习和统计方法：蒙特卡洛方法。
当遇到一个由确定性原理组成的问题——比如图形的面积、函数的分布，或者棋手在博弈中下一步应该走哪儿——蒙特卡洛方法从根本上假设它可以通过概率和或然性（随机性）来建模。
蒙特卡洛方法 依靠从一个分布中反复随机抽样来获得一个数值结果。这是一种方法，而不是一种算法。
02
随机抽样是一种寻找函数积分（曲线下面积）的便利方法。众所周知，圆周率pi也可以通过蒙特卡洛抽样得到近似值:
一般来说，蒙特卡洛抽样有三种:
1.直接抽样：直接从一个分布中抽样，不带任何先验信息。我们用该方法来近似一个未知外形的面积。
2.重要性抽样。在分布中抽样成本过高时，从一个更简单的近似函数中抽样。它是贝叶斯优化和代用优化的核心内容。
3.拒绝抽样。在分布未知的情况下，提出一个抽样点，若它满足某个标准，则接受它。
蒙特卡洛抽样通常在两种情况下使用:
优化寻找最优点自然需要在探索和利用之间保持很好的平衡。当蒙特卡洛抽样（探索）与其他能够控制利用的机制相配合时，它就是一个求解最优值的强大工具。
概率与函数——蒙特卡洛抽样是一种很好的方法，当用另一种方法太难求得某些概率或函数（通常是概率函数）时，可以用它间接得到近似。
03
由于蒙特卡洛方法背后的思想很简单，但用法相当复杂且颇具创造性，所以我们将通过几个例子来理解它。
其中，考虑马尔科夫链蒙特卡洛（MCMC）方法，它试图从一个目标分布中产生随机样本，且不知道该分布是什么。马尔科夫链（Markov Chains）——是一张用来表示这种分布的图，其中每个节点都是一个状态，它以概率p从一个状态跳转到另一个状态。
比如天气这个马尔科夫链，在一个（天气很糟糕的）城市里，唯一可能的天气状态是大风、冰雹/雪、雷暴或下雨。每天都可以根据当前天气推出来的概率来预测第二天的天气。例如，如果今天下雪，有80%的可能性明天会有大风，20%的可能性会下雨。
在马尔科夫链上的游走，需要从一个位置s开始，按指定概率移动到另一个位置s’。然后s’成为新的s，这个过程不断重复。虽然本例只能表示一个很小的马尔科夫链，但具有几千个节点和数十万个连接边的大图就可以用来建模复杂的概率关系了。
04
如果我们在马尔科夫链运行了相当长的时间后（比如模拟了10000天），开始达到一个 “概率平衡”。说明我们可以简单地根据转移过的状态中有多少天是下雨的来估计下雨的概率（基于大数定律）.
例如，若马尔科夫链上转移过了10000个状态，得到如下（假设）结果: 2754次大风状态 1034次雷暴状态 4301次冰雹/雪状态 1911次下雨状态 如此，将能得到如下概率: P(风) = 0.2754 P(雷) = 0.1034 P(雪) = 0.4031 P(雨) = 0.1911然后，人们可以简单地从分布中对应采样——从马尔科夫链中随机抽取一个状态，而不需要遍历它。通过对马尔科夫链的反复迭代和随机遍历（过程中的 “蒙特卡洛 “部分），系统能够被折叠并表示为一个概率分布。
马尔科夫链可以被构造成不能直接采样的复杂关系的模型，然后简化为求其隐含的概率分布。
05
有很多成熟的MCMC算法，如Metropolis-Hastings算法或Gibbs采样。所有的算法都试图对系统的隐概率进行建模。
算法要走出理论落到实地，最好的实例是蒙特卡洛树搜索（MCTS），这是智能游戏强化学习系统的一个关键部分。早期的博弈系统，比如IBM DeepBlue在1997年首次战胜国际象棋冠军Gary Kasparov，是基于极大极小搜索算法，它从当前的棋步开始，演算出所有可能的棋局，并从中确定能够确定（或最大概率）胜利的棋局。
随着搜索空间的扩大的棋局变得越来越复杂——比如围棋，甚至是像DOTA这样的高画质电脑游戏——这个算法因为要枚举所有可能的情况，所以在计算上变得不再可行，而且是不够高效。相反，对棋手来说更明智的做法是探索潜在的有益棋步的同时，放弃高概率失败的棋步，并且利用好已知的棋步。
假设我们构建这样一棵树，其中每个节点代表某种博弈状态，可以通过采取某些行动在节点之间转移。从博弈的初始起始状态开始，我们可能转移到另几种节点。
价值神经网络将会为每一步棋赋予一个值：给定一步棋，代理(agent)获胜的概率是多少？但在开始的时候，由于价值网络还没有经过训练，它会随机猜出一个值。然而当系统对弈得足够多之后，它就能更好地分析出某些棋步影响。
06
算法不是简单地选择最高概率的节点，而是进行 “加权蒙特卡洛抽样”。如果网络认为节点2的胜率为90%，那么它被选中的几率就更大，而且节点3和1被选中也是有可能的。策略——就是说如何选择可选节点——也是可以学习的。
其背后的逻辑是，某一步棋的可预见价值是有限的，并受到偶然性的约束（也许对手会做出意想不到的举动）。此外，只利用已知的招式，而不冒险去探索其他落子区域和找到更有利的棋步，会导致一个非竞争性且懒惰的模型，这在复杂的强化学习环境中是不可容忍的。
然后，选定的节点被进一步扩展，并不断重复直到游戏终止。将概率纳入决策，而不是确定性地选择一个 “最佳 “值，有助于强化学习权衡利用/探索的平衡。
07
从统计学的角度来看，蒙特卡洛抽样是用来模拟最优概率分布p(v)来选择一个节点，给定它有一些可预见的值v。
蒙特卡洛树搜索是AlphaGo的框架，DeepMind的强化学习系统击败顶级围棋选手。蒙特卡洛树搜索在其他地方有广泛的应用。
模拟退火是蒙特卡罗抽样的另一个应用，在寻找全局optima的任务中，作为非梯度函数优化的有效方法。像蒙特卡洛方法应用于其他问题一样，搜索空间是离散的（例如，我们不是要优化连续的值，比如神经网络的参数）。
在问题中，在固定的时间内找到一个近似的全局最优值比它的精确值更有价值，模拟退火实际上可能比梯度下降等算法更可取。
模拟退火的概念来自于冶金学，或者说是金属的操作。在冶金学中，退火是对材料进行可控的加热或冷却，以增大其尺寸并消除缺陷。同样，模拟退火也控制着系统中的能量，这决定了它在探索新的可能性时愿意承担多大的风险。
08
温度有一个初始值，同时它也是一个计时器。在每一个状态s，模拟退火根据状态值(移动到s’是收益还是损失?)和当前的温度T，以概率P(s，s’，T)转移到某个近邻状态s’。
温度随着每个时间步长的降低（剩余时间减少），模型的探索性变小，利用性变强。模拟退火可以实现从探索到利用依时间逐步过渡，这对寻找全局最优值非常有利。
模拟退火随着温度降低求解复变函数的全局最优解。图源：WikiMedia。图片共享自由
蒙特卡洛抽样和贝叶斯方法可以用来对概率函数P(s，s’，T)进行建模。事实上，通常使用Metropolis-Hastings算法——你可能知道它是一种马尔科夫链蒙特卡洛方法（或以它为模型的方法）——来求解转移阈值（应该发生转移的概率）。
这是很直观的，因为模拟退火将解视为状态，并试图找到最佳的转移概率——这是非常适合用马尔科夫链建模的场景。
通常情况下，蒙特卡洛方法——或类蒙特卡洛的思维——会出现在我们最不希望出现的地方。虽然它是一个简单的机制，但它已深刻而复杂地扎根于无数应用中。
总结/要点
蒙特卡洛方法的基本思路：在一个系统中注入随机性往往可以有效地解决这个问题。
一般来说蒙特卡洛抽样分为三类：直接抽样、重要性抽样和拒绝抽样.
蒙特卡洛的两个常见应用包括优化和复杂概率/函数的近似。
在离散(非连续)和确定性问题中，蒙特卡洛方法利用随机性+概率、大数定律和高效框架来解决问题。