本課程分為人工智慧（上）、人工智慧（下）兩部份，第一部分除了人工智慧概論外，著重在目標搜尋、meta heuristic、電腦對弈、演繹學習（包含證言邏輯、一階邏輯及 planning ）等技術。這些技術主要發展時機為人工智慧的第一波及第二波熱潮，也就是 1950 年代至 1990 年代附近的主流發展，即使到現在也在各個領域廣為應用。 課程教學目標： 使同學對人工智慧有基礎概念 同學能夠理解如何運用目標搜尋技術及演繹學習方式達成人工智慧 同學能將相關技術應用到自己的問題上
4-3 Simulated Annealing
Loading...
來自 National Taiwan University 的課程
人工智慧：搜尋方法與邏輯推論 (Artificial Intelligence - Search & Logic)
140 個評分
從本節課中
Non-classic search
與講師見面
于天立(Tian-Li,Yu)副教授（Associate Professor）
電機工程學系(Electrical Engineering)
好接下來我們談第二個技巧叫Simulated Annealing，
那中文翻譯成模擬退火法。好那它主要是想要修正steepest descent，它只會給 最近的local optimum的這個特性，那如果是像
steepest descent，那基本上就是如果 我們有一個比較低的local optimum這邊是global optimum的話，
我們這樣爬上，那 steepest descent 如果你的點在這裡，那你我們就知道它永遠只會到，永遠只會往上，只會到這個地方。
那我們希望說它某個程度上在steepest descent的情況下， 我們有個幾率，它可以下山，
它可以下來，然後往回爬，然後就回到這邊了。
好那 所以我們希望也就是說我們希望大致上它在後期的時候是一個 steepest descent，
因為你如果呃前期就後期你還是需要 比較像steepest descent，所以你可以如果已經在那個global
optimum山頭的話，你可以在那個hill的話， 你可以登上那個山頭。那可在初期的時候我們希望它比較能夠
廣一點的，廣泛一點地去做，去做探索，好那也就我們希望初期的時候有一點 random walk的行為。
那後期的時候我們可以做比較比較就是 steepest descent 的行為。 所以在simulated annealing裡面
它introduce一個參數我們稱為T，就是溫度。好那整個模擬退火法其實就真的在模- 擬退火， 那退火是那個打鐵的一項技術，不知道大家，不知道，
我對這個整個過程也不是很熟，但是大致上你要煉鐵的情況你是基本上先給金屬的能量，
你先把它弄到非常高溫，在高溫的情況下，然後讓它慢慢溫度降下來，
然後降下來的時候，根據你不同的狀態，就是你它可以落到不同的
optimum上。就所以所以我們煉鐵你可能有需要急速冷卻， 有需要慢慢冷卻，有需要在過程中加一些，
加一些，加一些事情，比如說打擊它，比如說加一些別的元素等等。好這根據你不同的
狀態它最後就會落到不同的optimum去。 我們如果說降溫的話，那所以等到溫度，高溫的時候，
它其實各種可能都有，那等到溫度越來越低的時候到最後 你如果到常溫的話那個鐵就已經進入某一種性質，不會到
不會換成別的性質。好所以整個過程就是你用一個這個參數
這個T的參數來控制，一開始就T很高，所以你很容易接受，
比現在狀態還差的state，就是即使現在， 就是比較容易下山了，就是即使你的neighbor裡面有幾個比較低，
但是你還是有蠻高的技術去take它們。那如果 等到溫度越來越低的時候開始降溫的時候，
你就越來越不願意去接受那個比較低比較差的state。
好那這個過程中就是你的neighbor裡面， 這些new state，如果它比原本還好，
比你現在的current state還好，那你永遠都接受它。好這個接受它幾率就是1。
接受它的幾率就是1。那如果你的state狀態比較差， 那你，我們不是直接拒絕，而是用一個我們去算一個這個
就是△E啦，我們，我這邊就測定能量來測，那實際上就是那個F，就是我們剛f(x)的值，
好那如果你是比較好的，我們就說你的△E是正的，就是你用
現在的減掉將要到的那個地方，就是你現在這個狀態比較高， 你要往下降的話，那它比較低，所以你就一定take。那，
否則的話你就take，就是△E小於零的時候，好如果這△E小於零， 在steepest descent的話就直接拒絕。
那在Simulated Annealing裡的話，它就是用這個幾率來接受， 就你，就算這個值然後這個值一定，因為是負的嘛，
所以 exponential 的負某個值，所以基本上是一個小於，就介於0-1之間的數字。 那你就丟一個骰子，好丟一個骰子。
如果ok的話就你如果有丟到，那你還是會接受它，即使它比較差，你還是接受。
那你可以看到隨著我的時間，如果我的T越來越小，
T這個T一直下降，那上面這個就會負什麼東西越來越大對不對，就是
不管△E是多少，那如果我T降到非常非常小，比如說接近零的時候， 上面基本上變一個負無窮大，那這個東西就等於零了。
ok就隨著我T一直降降降，降到也就是，概念上就是用物理講，就是你會降到絕對零度，
那你這整個物質就stablized，那你就，你就不會去變化其他的狀態。
好也就是說當T等於零的時候基本上SA大致上是reduce回原來的 就是steepest descent。
但是當T很大的時候你會很容易下山。
好那這裡面有各種證明瞭，那SA基本上有被證明 說就是你只要T
decrease夠慢的話， 夠慢的話它永遠都會給你， global optimum。
那好在無窮久的時間，但是我們就這樣講， 一般來說我們不太認為這樣的證明是在實際上真的很有用。
但對於我們實際上可能沒有太大意義了，因為反正就是你將要用 nonzero 的幾率你會穿global optimum， 那其實你只要給他無窮長的時間你永遠都一定會拿到global optimum。
好但是這裡面 當然還有很多研究，SA裡面研究還蠻多，包含T要怎麼下降。
我們剛只講T是隨著時間慢慢下降，然後一開始是很大，然後如何下降，基本上它也可能，
你這個設的溫度基本上是時間的函數，那這個你要怎麼下降， 有些比較advanced的技巧，包含你可能看，
目前狀態比如說有些有些比較advanced的技巧會說，你如果 你會記錄一些歷史資訊，就是你如果目前還在很陡的地方，
很這種很亂的地方那你可能就讓溫度下降得慢一點，就不要那麼快，不然你很容易
掉到一個你其實不是很喜歡的state，就找不到那個 local optimum。那你如果是很平緩，
你的例子看起來是蠻平緩，你的 f值沒有上上下下太多，那其實，
你讓它，你讓它掉快一點沒關係，就是這一帶其實差不多， 你就去收煉到你的optimum 就好了。
好那這部分一樣，類似的研究其實還一樣很多，有興趣的同學可以去參考一下其他的書籍。
好那這個是它的 pseudo code 。那其實也很單純，基本上就是，就是我們講的這邊 T， 大 T 就是溫度 是一個時間的函數，這個schedule就是一個，
其實是一個蠻複雜的研究課題，那反正 anyway在這個， 在這個 pseudo code裡面很單純就是我如果給你一個時間點，
然後你可以給我一個相對應的T，那概念上當然是遞減函數了，
就是，大T還是，T，小T很小的時候，它是大的，
然後小T很大的時候，就無窮大的時候它很小的。好那之後就，你就去計算這一個△E，
好就是你現在的state跟下一個state的差距，那如果，如果基本上如果這是正的， 你就一定接受，好就一定接受。不然的話你就只用這個機率接受。
好那我們這邊再繼續談下去之前，那所有的， 不管是simulated Annealing或是steepest descent，
其實我們剛剛講都單點就是一個點然後去算它 neighbor， 然後利用它 neighbor各種資訊決定我要不要接受這個狀態。
是那有一種技術是用多點就我們稱為beam search。
好為什麼叫 beam呢？就是想像成一個光速，就是像一個 spotlight，就是，就是，
就是不是單一個點，你就看的是一塊，就是你是一群，一個 beam這樣來看的。
好概念上就很單純就是我們之前就是keep一個state，然後你再
選擇你就，你就看它 neighbor這個 state，你說我可以到個 S'。 那在這時候neighbor裡面你選擇一個
最好的去走steepest這樣，那如果是simulated annealing的話， 就是每一個state你都算下機率，對不對。
如果就是比你好，接受的幾率是1，比你差接受的幾率比如說 0.2
0.3，然後你就全部 iii然後丟骰子，好這樣。
那如果今天這 Keep不是 keep一個單一的 state， 如果是 keep 某 K個 state的話，
那會怎麼樣？ 就是我可以多撒幾個點，對不對，然後這幾個點同時爬， 就想像一種概念是一種多點爬山。
好這裡面當然產生一個研究課題就是說，你 如果我們想回到我們講單純steepest descent好了，
那你一次丟十個點，然後讓這十個點開始去 爬山，跟你，
一次丟一個點，然後這件事repeat十次，這兩個有什麼不一樣？那其實說真的還蠻
不太一樣的。那不一樣的地方是你這K個點，你如果你一次keep K個點，
這K個點之間會有些交互作用。 它其實會 在steepest descent的話，其實會加快那種，一種效應，
就是西瓜偎大邊，就是反正就是一堆人， 譬如說一堆人看這一點好那你很容易會很多點就會往那個地方收斂。
比如說我們舉個例子好了。
那這邊我有兩個 兩個hill，那假設，一開始，假設initial
我隨便亂丟，假設這邊丟掉兩個點好了， 好這邊丟掉一個點，好在這三個點來說就右邊比較高，
那你之後算它的neighbor，比如說我每一個每一個點假設我產生一個 就一個neighbor好了，那這個點假設產生新的在這邊，
那新的，假設運氣好多好一點點好了。
好接下來所謂k，如果我接下來做的事情就是這邊有六個點，對不對，
就包含舊的那一帶，全部六個點，就是我取，就是取三個好的。
就是說我是三個點，這樣去做search，那我取得，很明顯會取這一個，
這一個還有就是f值越高的越好。還有比如說這一個，好你會發現原本我是兩個點在左邊，
一個點在右邊，那經過一帶以後，因為它們各自產生一個neighbor， 然後全部有六個點，然後我再選三個點就好了，下來那你會發現這邊變兩個，
好兩個，這邊是一個。
那隨著時間的演變也會發現很容易就我剛講群聚效應，只要你有一個看起來不錯，
不久大家就都覺得，呃這個，就有那種很奇怪的現象，就好像是大家覺得這個不錯，就全部聚- 集過來，那其實
嚴格講也不是這樣，其實是這個比較好的點它的state其實能比其它的neighbor都好，
所以不久就只剩下它的state。
好就是這個效應有好有壞，那當然就是說，你說一個比較高的hill，有多一點人在，
多一點點在那邊探索，在那邊爬， 這當然聽起來是很好嘛，對不對，你比較低的就比較沒必要，我就可以不要有人在那邊探索。
這一般來說是好的，但是當然另外一個可能就是， 你可能那個看似高的還是錯的，然後就是我可能有一個低的，
然後這邊是高一點，其實有更高的，它細一點，但是目前沒有人在， 那你很快的不久一堆人就會爬，一堆點就會跑到這裡來。
好這個若高的一直都沒有人去看，那這是也是一個問題，就是你如果， 就是好處就是，
比較好的hill會比較多的人看，但是壞處就是如果太多人一次往好的，看似好的
hill聚集的話，那你其它的領域全部都忽略了。好所以這個也衍生新的問題， 所以有另外一種方法是用Stochastic beam search.
原則上就是你選擇像我剛剛舉的例子三個， 然後產生三個舊的點，產生三個新的點，然後就六個點，
你要選擇三個的時候你不是直接選擇最好的三個，不然的話你會群聚的太快， 那另外的方法就是你選擇一個，
就是那個六個點每個都被選到的機率然後正比他們的goodness， 那這個goodness要怎麼算， 就depend
on不同的，不同的問題你可能有不同的做法， 那最簡單方法就是正比它們的f(x)。
那如果你要最大化的話，
你就正比它們的f(x)，f(x)越高，給它更大的機率被選到， 但是你不是百分之百一定會選到。
Stochastic beam search其實我剛剛講的那個做法裡面還有很多
細部的技巧，那包含說如果你每個都是有機率選的話，有一件事我們很不喜歡發生的就是，
那你可能是世界上最高的點可是因為你是機率算， 它有一個的 none zero的機率沒被選到，
比如說你最高點正比於它們的goodness，那可能，你即使很高， 比如你零點九好了，好但是你還是有，
你 run 這個 algorism run10次，你就有可能一次目前最好的也被丟掉，那這可能也不是我們
喜歡的。所以基本上這背後就有很多很複雜的技巧包含比如說我們可能keep
前面十個，五個看起來很好的點，就是無條件留下來，然後 剩下的我再丟骰子，那這裡面就很多參數，然後很多都是trade off，
很多都是trade off，
就是一般來說你不希望點聚集的太分散， 但是你也不希望點聚集得太快，好這裡面都是一些研究的課題。
