为什么要接受较差的状态?
爬山法只接受改善的邻近状态,因此可能停在局部最优点。如果更好的区域隔着一道必须先变差才能越过的障碍,严格改善的路径便无法到达。模拟退火容许以受控制的概率接受暂时变差的移动。这里的“温度”是算法参数,问题本身无须有物理温度:高温较容易接受小幅损失,低温则较少接受。
定义 23.1.1
(Metropolis 接受规则)
设 为有限候选状态集合, 是要最小化的实数成本。在温度 ,先按概率 从现状 提议 。暂时假设 ,而每行概率和均为一。接受该提议的概率定为
若拒绝则留在 。成本下降或不变时必定接受;成本上升 时,以概率 接受。
提议本身也可以是现有状态。实际的一步转移中,留在原地的概率包括自我提议和其他提议遭拒的情况。每次接受判断使用新的均匀随机数;提议和接受机制均按当前状态给出条件概率。成本差的大小须与 比较:若把所有成本单位乘以一个正数而不改变 ,算法便会改变。
固定温度下的不变分布
定义 23.1.2
(固定温度分布与不变分布)
对固定的 ,定义
这些数全为正,总和为一。当 ,令 ;把剩余概率放在对角项。若 ,称 为不变分布:以它作为初始分布,走一步后分布不变。这不代表每次实际运行都留在原状态。
定理 23.1.3
(对称提议的细致平衡)
对有限状态空间、实数成本、 和对称提议概率,上述规则以 为不变分布。若由不同状态间 的边组成的图连通,则此不变分布唯一。由每个起点收敛到它还需要非周期性;每个状态都有正的自环是充分条件。
证明
(逐边验证细致平衡)
对不同的 ,利用对称性可得
对角项的等式也显然成立。对 求和,流入 的概率等于 ,所以 不变。连通性及正的接受概率使有限链不可约。有限不可约马尔可夫(Markov)链定理给出唯一性;再加非周期性,便由任意初始分布收敛。每个状态有自环即足以保证非周期。不变性本身不需要连通或非周期假设。
证明透视
对称性用在哪里
对称性使两个方向的提议因子相同,于是较小的未归一化权重配上同一因子便能逐边相等。若提议不对称而没有作修正,这种平衡可能失效。
提议不对称时,对两个方向概率都为正的状态对,可改用 Metropolis–Hastings 接受概率 。在这种可逆构造中,只有单向提议的移动以零概率接受。这点对各点度数不同的图尤其重要:均匀选择邻点通常不会得到对称的 。
反例模式
均匀选择邻点的提议并不对称
一个诱人的捷径,是均匀选择邻点作提议,再把它当作对称提议,直接套用普通接受规则 。取路径 ——,所有成本均为 ,于是每个 下的 都是均匀分布,每个状态为 。此时每个提议都被接受: 必定移到 , 以各 的概率移到 或 , 必定移到 。由均匀分布出发,流入 的概率只有 ,所以 并不是这个规则的不变分布; 才是。把接受概率乘以 即可修正: 与 的接受概率变为 , 与 则为 ,均匀分布就满足细致平衡。
搜索路径与平衡分布算例
例题 23.1.4
(跨过成本上升的搜索路径)
取 ,成本为 、、,提议时从另外两个状态均匀选一个。当 , 的接受概率是 ,而 必定接受。例如,在 提议了 ,若独立均匀随机数是 ,因 便接受。若下一个提议是 ,也接受;这条路径跨过暂时升高的成本,到达更低成本的状态。提议规则也容许直接走 ,所以这个例子不一定要经过 。若第一个随机数是 ,则拒绝并留在 。
例题 23.1.5
(温度为一时的不变分布)
在此温度下 ,故不变分布为
这些是固定转移规则下的长期边际概率,并非两步路径到达 的概率。按上述提议规则,在 拒绝上坡移动产生自环;链又是连通的,因此分布收敛至这些数值。若另行记录至今见过的最佳状态,即使目前状态后来离开 ,仍可返回 。这种记录不改变转移规则。
例题 23.1.6
(同一组状态在高温与低温下的比较)
保留三个状态,成本 、、,以及均匀提议。当 ,权重 分别为 、、,总和 ,故 。搜索几乎不理会成本:大小为 的上坡移动以 的概率被接受。
当 ,权重为 、、,所以 ,。上坡移动 的接受概率是 。离开 需要成本增加 或 ,接受概率分别为 和 ,所以链每次在 停留约 步。高温不理会成本,低温则使链几乎不动;降温表正是要在两者之间取得平衡。
降温是另一个过程
降温表选择正温度 ,每一步套用相应的转移规则。此时规则随时间改变,不能把固定温度的不变分布定理用成“每个温度下都已达平衡”。在任何固定正温度下,即使处于最优状态也可能离开,因此返回最后状态与返回曾见最佳状态是不同程序。
命题 23.1.7
(低温平衡的极限)
设 为非空有限集合, 为全局成本最小点集合。当 , 收敛至 上的均匀分布。
证明
(约去最低成本)
令最低成本为 ,把每个成本减去 。这个共同因子在分子和分母相消。当 ,新权重为 ;当 ,权重 。状态只有有限个,故分母趋向 ;每个最小点的概率趋向 ,其他点则趋向零。
反例模式
降温太快可能永远冻结
考虑三状态路径 ——,成本分别为 ;对称提议概率为 ,每行剩余概率放在对角项。由 出发,在第 步取 。若之前一直留在 ,则第 步离开的条件概率为 。因 且每个 ,无穷乘积 为正。因此有正概率永远留在 ,从不到达全局最小点 。温度趋低本身并不保证搜索收敛至最优点。
例如,因 ,而右边的级数收敛,可知上述乘积为正。慢速降温的定理须对提议图和降温表施加额外条件;单靠接受规则不能推出一般的有限时间成功保证。反过来说,在有限计算量下它仍可能有实用表现,但必须针对指定成本、邻域、降温表和起始分布评估。
常见错误
常见错误
(改变成本尺度而不调整温度)
把每个成本乘以 ,状态的高低次序不变,但大小为 的上坡移动变成大小为 。在 ,其接受概率由 降至 。温度只有相对于 的单位才有意义。
常见错误
(把最后状态当成最佳状态返回)
在任何固定的 ,链都可能离开全局最小点,所以最后到达的状态可能比较早的状态差。另行记录迄今最佳的状态只是额外记账,不会改变转移规则。
练习
快速检查
(当 ,提议使成本增加 ,接受概率是多少?若成本减少 又如何?)
对增加与减少,分别使用 。
解答 · 答案
增加 时的接受概率是 。成本减少则必定接受,概率为 。
快速检查
(两个状态的成本为 和 ,提议概率对称。求固定温度下两个不变概率的比值,以及 时的极限。)
写出比值 ,归一化常数会约去。
解答 · 答案
成本为 的概率除以成本为 的概率是 。当 ,两者分别趋向 和 。这是平衡分布的极限,不能自动视为有限降温运行的结果。
快速检查
(提议图是一条路径 ——,每个状态均匀选一个邻点。提议是否对称?找一对状态说明,并求 的修正比值。)
比较 与 ;修正比值是 。
解答 · 答案
不对称:,但 。Metropolis–Hastings 在 的提议比值为 ;接受概率仍须乘入成本差的指数因子。
快速检查
(在上述 的三状态算例中,求两步恰好走出并接受 的概率。为什么它与 不同?)
把两个提议概率与两个接受概率相乘。
解答 · 答案
每次提议概率都是 ;第一次接受概率为 ,第二次为 。故该路径的概率是 。它描述从 出发的一条指定两步路径; 则是固定温度下不变分布在 的边际概率。