本課程分為人工智慧（上）、人工智慧（下）兩部份，第一部分除了人工智慧概論外，著重在目標搜尋、meta heuristic、電腦對弈、演繹學習（包含證言邏輯、一階邏輯及 planning ）等技術。這些技術主要發展時機為人工智慧的第一波及第二波熱潮，也就是 1950 年代至 1990 年代附近的主流發展，即使到現在也在各個領域廣為應用。 課程教學目標： 使同學對人工智慧有基礎概念 同學能夠理解如何運用目標搜尋技術及演繹學習方式達成人工智慧 同學能將相關技術應用到自己的問題上
4-2 Steepest Descent
Loading...
Del curso dictado por National Taiwan University
人工智慧：搜尋方法與邏輯推論 (Artificial Intelligence - Search & Logic)
140 calificaciones
National Taiwan University
140 calificaciones
De la lección
Non-classic search
Conoce a los instructores
于天立副教授（Associate Professor）
電機工程學系(Electrical Engineering)
那接下來我們講第一個我們要介紹的 search 的技巧，
讓我們稱為 Steepest Descent, 那 depends on 你的問題，你如果要最大化那就 ascend。
不過習慣上，當我們講 Steepest Descent ，
我們並不特別會 假設你是最小還是最大化，這是一個通用的名詞啊，OK 好，那這還有蠻多別名，就是稱為
Gradient descent，也有這樣稱
好，那 感覺上很簡單， 這是我這邊 quote 的是一位大師說的話，感覺上就很像他說做這件事就很像你在
一個非常非常濃的霧中，然後你試著要去爬喜馬拉雅山這種感覺哦。
那就是OK，你不知道完全無法看周圍，所以你能看的就是腳邊。
就是你的腳邊這一個區域，所以你要怎麼爬山，你就只好看 以腳邊的資訊覺得哪裡會比較高一點，然後你就往你
從你四周的地形，你覺得最高的那一個斜率最高的那一個地方開始走， 好 如果我們這邊畫的是一個就是等高線圖，
那原則上就是你走的大致上會，大致上會，比如說從這一點開始，你大致上會垂直大致垂直於你目前最好的規點，
好 either 是往下， either 是往上 好那所以會形成一個比如說這樣彎曲的一條 path。
好，在這裡面，那下面這是 sudal code 那概念很單純，比如說你對每一個 states，
你就先把它的 neighbor拿出來，就是你可以這個 state 可以到達的所有的 state，那上一講的話我們把這稱為 successor，大家如果記得的話，
就是你所有從 S 然後你坐一個 A 所有可以的A， 就是你的 A 是屬於所有的 action(s)，就是你在這個
S 這個 state 裡面，你所有可以坐 value moves 所到達的 S‘，這樣的 S’ 的集合。我們上一講稱為 successor 那這邊因為
不同的不同的領域我們有時候講不同的講法，讓我們稱為neighbor， 意思就是你這個 state 你可以到達的這些地方。
在這所有的 neighbor 裡面然後基本上你就去 evaluate 它的我們剛剛講到的 F function，然後去
take 一個目前看起來最好的那一個，好就如果你要最大化，就是這是我的 S 具體算一下
剛剛的那個 f 嘛，你就算一下它的它對應的值是什麼，然後，如果你最大化就 take 那個最高的那個 f，然後更改 current state 然後這樣一直做下去。
好，那這邊其實 好，呼應到我們剛前天投影片所講的這個
shoulder 還有高原的這個問題。
在這個第四行這邊， 我們這邊採用的例子是 descent 嘛，descent 的話就是一直下降就是我們用的
小於等於，就是你只要比現在的還小 f 如果說比現在還小就是 take，那這邊有 個小問題，就是你要用小於呢還是小於等於？
好就這是一個問題，就是 如果你的 F 一樣的時候，你要不要換一個state，
好那 如果你不換的話，問題就是，我們如果在上一頁，
如果你值一樣你就不換的話，那基本上像從這一點開始爬，你爬到這裡的時候，
之後它的neighbor 值是一樣，那你不 take，那你這個 search 基本上就結束了。
也就是說你如果，我們叫 sidewalk， 就是說你如果平的這個地， 你不走的話，那你就在這個例子，你就走不到這裡。
好，可是如果你說走的話，那又產生另外一個問題，譬如說我今天的 active
譬如說就是說一個高原，這是我的 global optima，其他的就陡了一些東西。
那你爬到這邊以後呢，那你容許小於等於嗎？啊就按這邊一直走一直走一直走
好那這個procedure 就不會結束啊，就是這個這是 repeat嘛 那你就基本上你會陷入無窮迴圈，好 所以通常來說，
我們習慣上的用法是我們會用小於等於， 但是 我們會put 一個 limit，就是如果譬如說你連續一百步，
你走了半天都是平的，那我們就說好你這個 procedure 可以終止了。
好那這樣的話就是想象中就是你已經到達一個 如果一百步夠，看你一百步夠不夠了，那這邊呢，你put
一個 limit 的時候 然後你避免了無窮迴圈的問題，但是同樣你就限制了它的探索的能力，
也就是說今天如果修得寬一點， 今天我如果，這是 global optima，
我修得寬一點的話，那你爬上來在這邊走一百步， 可能走到這附近，那你還是沒辦法走到
繼續往上走，所以這本來就是， 這部分就是一個 trade off 就看你能容許的時間和你希望它探索的能力。
我們可以用 Steepest Descent解很多問題哦， 那我們回顧一下譬如說像 TSP，
我們之前談過的一些旅行員銷售問題，銷售人的問題， 那基本上就是說我要找一個 就是 n 個 city嘛，
我們要陸續著拜訪過一次，使得一個環狀那使得這 總體路線， 這個tour 的 cost 是最小。
好，那如果我們用 Steepest Descent 來做TSP 的話， 有一種做法就是你可以 random 的，你可以begin with a complete tour
那這個 complete tour 可以是 random 的，depends on 可以有不同的設定。
那習慣上如果沒有特別的原因的話，我們可能會 random 就是我們從第一個記憶體就random 挑嘛，
因為它反正是一個 permutation 就是你在解 是一個permutation 就 random 挑，挑一個 permutation
出來就是了。那 你可以用一種，譬如說，你這邊要定義自己的 operator, 像這邊我們定義如果有很著名的 operator 叫 SWAP-2,
好 SWAP-2 這個 operator 就很單純就是任意交換兩個 city，任意交換兩個 city，
那如果在任意交換兩個 city 有可能會變好，比如說像這個圖上的例子， 就是你如果交換的我這邊圖上是兩條線，等一下我會
show 出其交換兩個 city，在 permutation 上交換兩個 city 跟交換兩條 線其實是意義上是一樣的，我們等一下可以看一下。
好，那如果你 SWAP-2 是 SWAP-2 這兩條，那你把它換成這兩條的話
那根據三角不等式的話，那這兩條一定會比較好嘛，對不對， 那這兩條一定會比較短，因為你是直線 versus
這兩條，兩邊和大於等於第三邊， 就是這兩邊和大於這三邊，這兩邊和大於這第三邊，
大於等於第三邊，所以當然會有可能會比較好，有可能你換的時候會換錯， 換成另外一個例子，你可能是把這一個
state 換到這一邊，問題還沒有比較好， 所以就不take，好那如果這種 SWAP-2 的情況下
如果我們寫 permutation的話， 基本上譬如說我寫 ABC DE，好，這是如果這五個city，
那你畫出來的話就是 好，那你這一，我這 ABCED permutation，意思是我右手邊這個圖。
那你如果任意換兩個 city，譬如說我譬如說我 SWAP-2的 operator 是這樣，
你找兩個 city換，譬如我說換 C 跟 E， 那你會換成 A BEDC，那你如果到iii還不變，
那你這邊連的話，就是AB不變，然後B以後到E去。
然後E到D這一條還是原來的，然後D到C、 這一條是原來的，然後C再回到A。
好，所以你就可以看到，就是我實際上在做的時候，我們說為什麼 稱
SWAP-2 就是我是 random 挑兩個 city 換， 但它實際上造成的效果其實就是
把我剛剛這兩條 的這個，這兩條換成這個虛線的這兩條，跟這個圖上是結果是一樣的。
好，那這個概念上就是 SWAP-2你可以稱為說把兩個 city拿來換，
但是你也可以稱為把 兩條 edge 然後把它交叉把它打直，不過這個說法比較複雜一點
好，那，如果在 Steepest Descent 里利用 SWAP-2的話， 那你的做法就是你有 n 個 city 你給我 n 個 city
的話，那我的做法就是把所有可能的 state 嘛，就是你現在給我一個 state 就是 某一種 permutation 就是 ABCDE。
譬如說，這是我一開始的 state 那你的，你就做，你可以的
value move，就是你可以任意挑兩個 city 來互換， 所以基本上你有 C n 取 2個 可以的 action，
對不對，然後等到你會到達 C n 取 2 個不同的state
也就是它的 neighbor， OK，那就基本上就是你利用 SWAP-2
把所有的可能性都算 一次， 然後把Cn 取 2的結果都拿去算一下這個環狀的結果有沒有比較好，
那從這之中你挑一個最小的，就是那個 tour 總體最小的來做。
好那你什麼時候停止呢，當然就是你如果做Cn 取2
這個 state 的路線總和都比原來的還長 比原來這個 state
還長的話，那你就說好我找不到，在 SWAP-2 這個 operator 裡面 operation 裡面你沒辦法再找到更好更短的路徑，那這時候就終止。
好，那概念上當然是說你說 SWAP-2，OK，那你說SWAP-3比較好，那SWAP-3
也是蠻常用的，就是你任意挑三個 city 出來， 你 Cn 取 3 你宣佈的 action
就變成 Cn 取 3 ，然後這三個 city 就會任意的組合，任意的交換，所以基本上還要乘個 3階 這個樣子。
OK，那原來的話，原本是C，這個可能要再減1啦，就是原來的我們 SWAP-2 是Cn 取 2嘛，
那基本上兩個 City 的交換法有 2！種組合就是2 然後剛好再減掉你原來的 state，就是減1，這個1就是你原來的
original state，也就是你用 SWAP-2 check SWAP-2 所有的可行的 action 大致上這麼多。
你用 SWAP-3 的話你的可行的 action大致上這麼多， 所以當然可以這樣做，而且其實 performance
會 就是你可能會拿到找到更短的路徑，但是你從而你要付出的 cost 大致是 big O n3方 嘛。
所以原則上你除了 SWAP-3 以外，你還可以做 SWAP-4，SWAP-5 那些都可以，但是你要花的
cost 就是 n 的 k 次方，你如果 in generally 使用 SWAP-k 這個 operator 的話，那在實際問題上大部分
好，我們說這大部分就是通常你在幾十個 city 一直到大概
幾百個 city 來說，你只用靠 SWAP-2 和SWAP-3 大致上就可以， 可以做得非常好，然後再配上steepest descent
那這是一般而言，那麼你，所以你的 problem
instance 越來越大，你可能要考慮再加上 SWAP-4 如果你的時間可以 容許的話，那當然原則上，這當然不保證
optimality 會達到 TSP 是 complete problem 目前就是世界上沒有人可以找出比，你要保證最佳解我們唯一的方法就是exponential，
目前是這個樣子，所以那 SWAP-2 和SWAP-3 都還是 polynomial的， 所以它們不能保證什麼最佳的解，但它的確可以給
很多問題可以給你很不錯的解，那接下來我們看一個 n Queen 這個 problem 那我們之前提過eight Queen八皇后問題，
那typically 西洋棋，棋盤 8*8，所以一開始就問 8 皇后那如果我們 in general
來講 n 皇后問題，就是我給你 n*n 的棋盤 然後上面，你有辦法擺 n 個皇后，使得它們彼此通通都沒有
互相威脅互相攻擊，好，那這個方法其實你也可以套用 steepest descent
哦，那 做法是怎麼樣呢，就是你可以給我某一個 擺法，然後之後我每次，
我去算一個cost，這 cost 可以算成是多少 conflict 就是你 pairwise 的去看， 兩兩皇后之中有，就是你擺的皇后位置之中，
如果有兩個皇后互相攻擊，你就算一個 conflict，就算一個， 就是說你有 n個皇后的話，
基本上你就說我 C n 取 2 也是兩兩你都算一次， 你最高最高就是C n 取 2， 就是如果每次的皇后都互相攻擊的話，那你全部最高就是
C n 取 2，那我們現在要做的就是 minimize 這一個 這一個conflict，number of conflict
那概念上就像這樣，這邊如果，像這個，這個 iii 的話，裡面有四個皇后，然後你 這邊畫的線就是這兩個皇后互相攻擊嘛，這兩個互相攻擊，等等
那你去算一下，就說四個皇后裡面，你可以算 C 4 取2
6，6種組合，6條線，像這兩個皇后沒攻擊，你就不用管它 那，這時候 6 條線裡面，基本上conflict 五個，
這就是你目前的值，然後之後呢，你的 neighbor 就是你移動某一個皇后，譬如說你今天選這一個皇后好了，
就是你選擇這個皇后，然後你看移在盤， 把這個皇后移到盤上的哪一個位置會使得你的 conflict最小，
好像這個例子的話，這邊，換到這個位子的話， 這邊如果遇到原來位子這個是 5，換到這個位子是
2 那大致上你可能算一算，大概可能沒有，在這個例子可能沒有比 2 更低的位置，所以 你好，OK，你就先做這件事情，然後你現在，你等於說下山嘛，
就 descend 就取 2 最小的位置。基本上你實際上 是要把每一個棋盤的，就是你放到這邊，放到那邊，每一個都算完，
算完以後你選最小的那一個把它放過去，然後之後像這個例子的話，你再放一次，就可以 搞定了，就是把這個皇后從這邊，原本是 2，你放到這邊會變零。
就可以搞定，那如果我們用 這是，這邊講解， 那如果我們換到這一邊，好，這邊這個棋盤上我已經擺了
1，2，3，4，5，6，7，7個皇后，那我現在還剩第 8 組皇后要擺的時候， 做法也是一樣，你對這 64 個位置，好，不到
64，但是差不多啦，就是扣掉已經 在的位置，你都去算它的 number of conflict， 然後你去擺最小的地方，那在這個例子的話，
有的地方是零嘛，那你其實很單純， 你就是把這個，意思就是說你把這個皇后擺到這個零的位置。
這個 8 皇后問題就已經解掉了，好，那這個，正如我講的， 就是 steepest descent
這一類的 search algorithm 都不能保證最佳解，但是我們講 實際上大致上來說，到
n 一直到 10 的 6 次方，也就是一百萬 就是百萬乘百萬的棋盤，然後你上面要擺一百萬只皇后
大致上在這個 scale 之內，你大致上都可以用 就是我們剛剛講的
steepest descent 用這種算這個 conflict 的方法大致上都可以，幾乎都可以找到 optimal。
幾乎，而且在目前電腦的計算能力，
大概 10 的 9次方的計算能力基本上都是瞬間哦，就是你 如果程式寫的好一點，就是按個 enter 然後答案就已經出來了，當然實際上這個問題這個方法當然不能保證，
你說 n 大於，譬如說 n 等於 10 的 不到 12次方， 這一類的這麼大的問題行不行，那實際上當然做不到，因為其實我們也知道
這是 n 皇后其實也是 nphard 的問題啦， 所以我們現在 steepest descent 都是一個 polynomial 的 algorithm，所以我們只能保證這是
甚至不能保證，就是實際上在小的問題上是解的不錯， 但是你要 apply到大的問題的話，你可能還需要更複雜的一些方法。
那我們剛剛講到 steepest descent 我們不能保證它會給你最佳解，但是它的 performance
我們還是可以簡單的談一下，steepest descent 它的這個 裡面，第一個它的特性是它一定都給你最近的那一個
local optimum 嘛，就是 不管我 landscape 長什麼樣，那看你的，這當然 depend
到你的 initial state，就是你如果 initially random 的時候，random 在這一個點， 好，那它基本上
steepest descent 在我的例子，ascend 嘛，我這麼畫 ascend 的話那它就會 往這邊爬嘛，就爬到這個點，那你如果
initial 在這裡的話，那它當然就是爬到可能這一個點， 它基本上，它還有個問題，就是它的特性就會給你最近的那個opitima，
local optimum 它不能保證 global optimum，那另外一個是它，有時候它的收斂是非常慢的。
像譬如說右邊這種圖，它基本上因為 大致它爬方向垂直，垂直於你的等高線，我就是找最深的那個爬。
那，它很可能會做這種 zig-zag 的方式，它沒辦法 就 depend on 你 initial，它不容易知道，但這個
zig-zag 的 behavior 其實在 3級的時候是最明顯的， 例如說 3 級的情況下，譬如說可能像這個樣子。
就是像一個 3 級，那如果我 initial
點這， 譬如說在這裡的話，因為它基本上會垂直於等高 線去爬嘛，那它可能是往這個方向爬，往這個方向。
那 depend 到你的 step 就是你如果那一步還蠻大的話，那這一爬會爬很遠，爬到後面來。
OK，那後面我們看不到，OK，就是差不多相對的點， 那我下次再從後面爬回來的時候可能會爬到這一邊來，可能會爬到這一邊。
這個之後再爬的時候又爬到這邊， 所以它沒辦法像我們想象中這一點直接往它的最高山頭這樣衝。
這一點我們是做不到的，OK。
好，那這個是 steepest descent 它的 performance 上的一些可能，蠻不容易做到的一些事情，
那當然相對應我們有很多 technique 來解決這一類的方法，
那有興趣的同學可能還是要查一下這方面專門的書，譬如說有一種方法， 你要避免這個 zig-zag 的行為，用這種方法去算moment
就是你算它的 momentum，就是連續你記錄下 history，就是你 譬如說，這是一步兩步三步，那你譬如說
開一個 window 是 4 或是 5，那你走了 4 步，5 步以後，
你把4，5 步前的位置跟你現在的位置連起來去做一個 等於說一個向量，然後之後你的，你每次爬的時候，
你不要只根據， 只根據你現在的最高點，而是一個 combination，就是包含你現在最好最深的那個方向。
加上你歷史資訊，你歷史爬到這個方向，你把這個向量做 waited 加進來， 那這樣就比較能保證你會
比較直線的往最高點前進，不過當然你如果加上這些技巧的話，那原則上
這已經不能叫 steepest descent， 我們講 steepest descent 是很單純，不包含這些技巧的情況。
好，那我們剛剛有講過，平原當然還是蠻困難的， 那大致上還要，steepest descent
要花多少時間來 才能找到，譬如說 global opitima了， 那我們這邊要假設一些參數，假設你有個 probability
叫做 success，就是找到 global optimum 原則上如果說，因為我們都只會給你最近的那一個 local
optimum，其實也就是說這個 p 其實就相當於你 initial state 撒點的時候 一開始就撒到 global optimum 的那一個 hill 的機率。
因為要撒到那個就是 global optimum 離你最近， 然後旁邊沒有別的local optimum，那這個點因為我 steepest descent
一定可以保證跑到 local optimum，好這是我們講這個機率，好那，如果你假設這個機率為 p的話
那平均來說，你大致上需要 1/p 的次數的 trial
就是你如果這個機率是 0.1 那平均來講你要 run 10 次，你才能
才能找到那 global optimum， 那所以你全部的cost 呢，大概如果譬如說這 p 是
0.1，那你這邊 1/p 就是 run 10次 好，那基本上就是你的 cost 就是你有一次，就是那一次
10 次裡面有那 1 次是成功的，就是 success 的 cost，你要把它加上去，然後加上九次的 這邊就是九次，好，這個的話，這個就是
1 減 p 分之 1 減 p 嘛， 其實就是 1/p 就是 10 次減 1 啦，就是這個，就是你要，就是
9 次 是失敗的，那這個當然我們可以這樣算，那另外一種算法， 就是你可以說我一次，失敗一次的機率就是1-p 嘛，
1 乘上 1-p 加上你失敗兩次的機率 1-p 的平方，加上你失敗三次的機率，1-p的 三次方，
然後你這樣一直加，加到無窮項，你如果把它 submission 起來，用一些 代數技巧，你也可以得到一樣的式子，p 分之 1-p
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
