為甚麼要接受較差的狀態?
爬山法只接受改善的鄰近狀態,因此可能停在局部最優點。如果更好的區域隔著一道必須先變差才能越過的障礙,嚴格改善的路徑便無法到達。模擬退火容許以受控制的概率接受暫時變差的移動。這裏的「溫度」是算法參數,問題本身無須有物理溫度:高溫較容易接受小幅損失,低溫則較少接受。
定義 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 在 的提議比值為 ;接受概率仍須乘入成本差的指數因子。
快速檢查
(在上述 的三狀態算例中,求兩步恰好走出並接受 的概率。為甚麼它與 不同?)
把兩個提議概率與兩個接受概率相乘。
解答 · 答案
每次提議概率都是 ;第一次接受概率為 ,第二次為 。故該路徑的概率是 。它描述從 出發的一條指定兩步路徑; 則是固定溫度下不變分布在 的邊際概率。