[0:00:00] 來來你過來你過來幫我來來來因為我說實在我這字很小我眼睛都看不到來來幫我來看一下這個嗎這個夾好嗎好像說這裡我會選擇來源這裡好試一下試一下長頸兒哦這個嗎應該是應該是螢幕螢幕解決好了看一下誰來幫我一下我試試看好欸直播中好那應該沒問題那看一下那如果切到這個畫面這樣子是不是會有呢是不是剛剛的關鍵是什麼要選輸出的來源是不是

[0:01:37] 奇怪好我以前都沒有做過這件事啊好anyway謝謝同學的幫忙好謝謝好欸好來那回到這裡重點呢就是說要寫清楚你的研究動機你問題的定義你預計要解決的辦法跟文獻那你怎麼寫得出來呢當然就是要想啊然後要找資料啊啊所以這個其實就是不許大家去完成第一個作業你最主要需要花的功夫在這裡你要想要去做一個什麼題目那你就得要先去研究一下目前人家大概都怎麼解的那你預計要怎麼解好那因為你根本就還沒有開始做嘛所以所以說呢在第一個作業裡面我們其實是會把introduction我們其實是會把introduction這一塊的分數放最高的比例ok我們可以跟大家講啊到時候你的第三個作業也是一個也是要寫上這個東西不過你不同區塊的分數佔比就會不一樣因為到時候我們就會更在乎你已經執行的進度有多少那第一次我們是把introduction這邊佔的比例是最高的好那方法的話就是說你預計可能要用什麼方法來做好那方法的話就是說你預計可能要用什麼方法來做ok那你會說我都還沒有學了我怎麼知道用什麼方法所以你要去找相關的文獻然後要做一個做一個整理啊你至少學一下人家怎麼用什麼方法

[0:03:10] 所以這邊會佔75%的比例其實都是目標都是為了要push大家去把這個報告寫出來你預期的結果是怎麼樣那你說我都還沒有做我怎麼知道預期結果所以這裡就是叫你用想的就是叫你比如說你也可以自己手繪一個圖你預計最後出來的結果應該要什麼樣ok你可以畫一個示意圖你可以比如說你如果是要去做一個什麼亂講Image generation你要把某一個人的人臉加上鬍子那你就預計他應該要有什麼樣子那最後呢就是有一些參考文獻好那再來一個很重要的就是好那再來一個很重要的就是有一些參考文獻好那再來一個很重要的就是有一些參考文獻好那再來一個很重要的就是有一些參考文獻請第三點喔請到這個網址你的分組名單來這個網址你點進去這裡呢你就是要填入你想要做的題目你是什麼學校你的學校是什麼你叫什麼名字ok你填了之後對不起你填你填了之後呢你就會有一個你能組的編號好現在變成一大堆了你們就得到一個組的編號

[0:04:41] ok所以呢我們會要求大家在報告裡面就要寫出你的編號好所以請大家我再重開一次好請大家依照有幾個原則喔你不要在那邊亂填因為這是所有人都可以寫入的所以你不要去改到別人的你不要去改到別人的任何的資料然後呢你也不要去弄一些有的沒有的比如說現在這裡就有人在那邊亂寫不知道在幹嘛好然後按照順序寫比如說你不要在那邊弄一些有的沒的你說我不想當一號這個第一編號一號的組別我就一直拉拉拉我就是要當編號253號253號是我信心之母我跟你講你這樣子搞到時候就會漏掉所以呢這只是一個組別的編號不是你報告的數據所以請大家老老實實的如果一號有人填了你就填二號二號有人填了就填三號以此類為中間不要空格不要空好中間不要空不要做一些有的沒的事情好那比如說我最後填到編號453號10號這一組那回到你要講的那個報告報告完成之後呢

[0:06:12] 你的檔名就是homework1底線分組編號就是底線10假設你編號10號或者編號27或者怎麼樣那當然你也可以把你的組別編號寫在你的報告裡面比如說寫在你的title底下你是第27組這樣子ok好為什麼要講那麼慢這麼簡單的事情要這樣講那麼慢因為就是會有人沒在聽不符合規則我就不知道為什麼都長這麼大了好那格式的話呢就是CPPR的格式ok基本上第一個作業呢就是讓大家寫一到兩頁的體驗報告就好了好那角角的期限從今天開始就可以開始講截止的日期是10月1號晚上11點59分結束之後系統就會自動關掉好就兩個禮拜的時間事實上這個作業我們在上週都已經透露給大家知道了所以理論上如果你要修正輪課你應該都已經動起來在找組員了好然後開始很快來看一下slide

[0:07:52] 有一些學校的同學在反映說要加簽首先我先講成大的名額都已經用完了就是說都已經加滿了不要再加簽了我不會再加了那如果其他同校其他學校的同學其實不同應該是幾乎每個學校大概是50個名額好那反正各校就依照各校自己的加簽程序下去做那有同學說他們學校加簽是需要什麼授課老師簽名同意的那我覺得請各校的同學自己去問清楚教務處如果今天這門課是拍卡的課的話難道也需要我一個一個去簽嗎那如果全國60幾間學校每一個要加簽的都要我去簽名這樣子是不是很沒有效率會不會比如說針對臺卡聯盟的課其實是教務處你們貴校的教務處有自己的做法所以請去問清楚回應一下

[0:09:26] 這個相關的問題線上課的人怎麼分組你們自己去分組吧我們上次有回答過就是你們反正自己找自己學校裡面的人分組線上揪團分組你們可以自己在MTUCOOL的類似討論區裡面徵求組員whatever然後你們自己去約自己去分組YouTube會留直播的錄影啊有啊這顯然上週沒有上課我們上週直播就有錄影然後我們還附旁白咧我可以再強調一次但是以後不要再問這個問題12月10號實體考試沒有錯線上上課的同學也是實體考試比如說隨便亂講臺南大學的同學你現在在線上上課到時候12月10號你就在臺南大學考試好理論上根據我們往年的執行的經驗你們學校會幫你借一間電腦教室然後可以讓你只能連上MTU COOL然後你就在那一間考試然後學校會派監考人員去進行監考

[0:10:56] 所以超過4個人剛剛規則已經講過了這種事情就不要再問了這個分組的事情不要再回答這個也不用回答了沒有點名這個自己有意願的自己想辦法什麼IG啊這個回答過了好我第一次遇到有這種問題不要擔你們自己分組的自己去想辦法大家都長大了你們是大人了你們自己去處理線上組隊的這個謝謝剛剛應該是有同學反映我們剛剛直播畫面有問題謝謝的確我們現在已經進入到第三次的直播現在終於大家糾團的這個就不用再slide啦這是要問我的問題不是要問同學們的問題助教的共同信箱剛剛畫面裡面沒有看到你到intucor就可以看到了你可以再秀一次這個不是聊天室

[0:12:53] 這是在問我好題目當然是自己定的簡短的回答到這邊要糾團的你們自己想辦法去糾再來就要進入到我們的課程來再來我們開始正式的上課我們今天要很快的把第二章講完第二章講的是Intelligent Agents那很快復習什麼叫一個agent呢agent就是一個東西這個東西可以透過sensor感測到一些資訊然後根據感測到的資訊可以做一些動作做一些事情透過這個所謂的accurator去做一些事情那他做完這件事情之後可能會影響到這個環境所以他可能可以從環境裡面感測到一些資訊那我可以做一些動作那我做完動作之後呢也有可能會改變這整個環境的狀態好那在這邊大家要注意的是這裡講的感測器不見得一定是什麼IoT的什麼物聯網感測器溫度時度感測器喔不是喔

[0:14:23] 他是很廣泛的一種講法基本上就是他可以收到一些資料的意思然後呢我收到一些資料之後做了某一些判斷跟決定之後我會做某一些事情那這些事情呢也不見得一定是真正的實體世界當中動物比如說往右走往左走機器手臂舉起來或者是什麼他也有可能只是我傳送一個什麼資料出去傳送一個什麼樣子的聲音出去都有可能為了做某一個動作所以agent的定義是很廣很廣的好那我們上次呢就提到說當我們在談論一個agent的時候一個完整的談論法其實是這個定義的我們稱呼它叫做一個Task Environment那講到Task Environment呢就會牽涉到四個元素PEASPerformance Environment Actuator跟SensorsPerformance指的就是我如何去評判這一個agent他的效能好不好所以這裡舉了一個例子我們上次提到最後提到的是比如說計程車司機他的Performance好不好我們可能有很多種比如說他能夠讓我優快抵達目的地越好或者是說他開的路線道路最平穩

[0:15:53] 或者是說我花的錢越少越好這都是屬於一種Performance那就看你的需求而定你可以有不同的Performance的定義那計程車司機所處在的環境當然就是道路嘛所以一般的道路平面然後道路有顛簸的有石頭路有柏油路然後呢道路上面可能會有交通耗製可能有其他的行人騎腳踏車的這個都是他所謂的環境因素Actuator就是他可以做什麼事比如說以計程車司機來講他可以加速煞車往右轉往左轉按喇叭這些都是他可以做的事那Sensor呢身為一個計程車司機他接收到訊號的來源如果是人的話可能就是耳朵聽得到眼睛看得到如果是自駕車CyberCab他可能有攝影機那或者說其他的自駕車的Solution可能有聲浪、光達等等等等的這些都是所謂的Sensor所以在傳統定義上當我們在講一個Asian的時候我們就是要定義好他的PEAS好那Asian這個詞呢其實大家在今年應該聽了非常多次了對不對今年Asian大爆發嘛但是我們必須跟大家講Asian的這個概念其實在過去幾十年的

[0:17:23] 人工智慧的開發當中老早人家就定義好Asian就是就是這樣子的東西那不過以現在這個年代來講其實啊PEAS這樣的地理還缺了一個很重要的東西就是大腦這個Asian的大腦是什麼OK好那在過去傳統的AI裡面比較避免比較沒有在談大腦這件事因為大腦有各式各樣不同的做法那當然以現在Right now這個時間點2026年來講很重要的就是說我們用LLM來當成是Asian的大腦由它來決定我收到什麼樣的訊息我要做哪些動作好那後續呢當然有很多其他的例子啦比如說醫療診斷系統也可以是一個Asian啊然後這個衛星影像的分析系統也可以是一個Asian啊或者是互動式的英語教學也可以是一個Asian啊所以任何的東西只要符合有這個PEAS的都可以視為是一種Asian那整個Task也就是Task Environment有幾種特性其實當你的Task Environment變的時候我們去設計Agent的做法可能就會不一樣因為它的狀態它的條件就不一樣所以有幾個不同的角度來去分類你的這個Task Environment

[0:18:56] 第一個角度叫做Fully Observable還是Partially Observable今天你這個環境裡面的資訊是可以全然透明的被看到的還是隻有部分被看到的所以比如說今天如果是下圍棋這個資訊一定是全然可以被看到的整個盤面你不可以蓋住某一部分的棋盤不讓對手看到不行嘛那什麼叫部分可被看到比如說比如說我們打電動世紀帝國還是什麼LOL有LOL這種東西嗎對LOL這種一開始地圖一開始的時候大部分都黑的嘛對不對你只有一小部分是你視野可及的範圍其他地方發生什麼事你都不知道那你要在這種情況之下你要做決定這是Partially Observable這是第一種觀察的角度第二種就是說你的Task Environment裡面你是單一的Agent還是會有多個Agent互動所以比如說下棋你就是有兩個下圍棋你就有兩個對手AAB兩個對手你要根據對方下了一個什麼棋下了一個什麼位置你再下一個什麼位置所以它就是Multi-Agent的形式那如果你這個這個環境裡面只有一個Agent在動作那就是Single Agent所以比如說我們上次課程裡面談到的

[0:20:26] 如果今天這整個世界就只有兩塊地磚然後我有一臺吸塵器這樣子的Task Environment就是Single Agent然後再來另外一個角度是你這個Environment你這個動作是Deterministic還是Socastic所謂的Deterministic是說當我叫它做某一個動作的時候它對於環境的影響就一定是你做了那個動作之後會發生的影響比如說吸塵器那個例子我叫它往右邊的那塊地磚走我做完這個動作之後它的環境一定就變成是吸塵器跑到右邊的那塊地磚這是肯定的這叫Deterministic那有一些環境是Socastic就是說你覺得比如說Taxi Driving就是Socastic你叫它就是說你身為一個Taxi Driver你覺得往右轉一定就是你的整個路面就一定是一定是變成一個你所預期的一個狀況這件事情大部分的時間是對的但為什麼會有車禍發生就是偶爾就是會有不確定性發生你再往右轉你轉過去之後突然有一個什麼東西掉下來

[0:21:56] 或一個行人衝出來所以它是有一些不確定性的這種就叫Socastic有隨機性另外一個觀點叫做Episodic跟Sequential就是你是情節不連貫的還是連貫的比如說比如說下騎跟開車都是連貫的你的下一個狀態一定都是源自於你上一個狀態的上一個狀態的一個連結它一定是一個連貫的一個情況那某一些情境它是不連貫的它沒有Depends on the actions taken in previous episodes那再來就是說Static跟Dynamic這意思是說當你的Agent你收到訊息你正在轉化成你動作的這段期間你的環境會不會動會不會變動也就是說你收到訊息你總是需要一點時間思考來進行決策假設你只思考了兩秒一秒好了一秒好你在這一秒之內你的環境說不定已經變動了還是沒變所以你看下騎就是我想個五分鐘盤面還是沒變那它就是Static可是如果是開車

[0:23:26] 其實開車道路上的訊息隨時都在變所以即使我只花0.5秒我收到一句只花一個0.5秒在進行決策可能路面的情況都會在變比如說後面的那臺車那臺車又跟得更近了前面有一個什麼人又突然要衝出來又變出來了這樣子然後Discrete或Continuous今天你的環境的變動是Continuous變動還是離散的變動比如說下騎就是離散的Taxi Driving就是連續的因為這個是一個實體的一個世界然後再來呢None or Unknown你今天在這個環境裡面你是知道它這個環境背後的運作的原理嗎比如說假設是實體世界你是已經知道在這個世界裡面整個所有資訊變動的它背後的物理原理嗎你知道這個規則嗎你是已經知道還是你不知道這個就是None跟Unknown所以底下呢這邊舉的例子就是說你各式各樣不同的Task Environment它在這些角度裡面個別是什麼樣子的屬性所以完全就看說你要處理的問題可能是屬於哪一種你可能你的應對的策略

[0:24:56] 就不一樣在開發Agent的時候事實上我們整體而言其實我們可以說AI人工智慧其實就是要去設計Agent那尤其呢我們要設計的是Agent Program這個Agent Program的用途就是當它收到一些資訊的時候它要透過這個Agent Program來決定它要做什麼動作它要做什麼動作這中間的這個就叫做Agent那如果說你跟一些Computing Device連結在一起或者說跟一些物理上的一些馬達啦或者說感測器連結在一起的話這些所謂的物理性的感測器跟制動器馬達啊動作機器手臂啊輪子啊這些東西它是實體的我們就稱為它是Architecture它是實體的結構因此整體而言一個Agent其實包含了Architecture加上ProgramProgram比較像是軟體的部分它是負責決策的Architecture就是可能是感測資料的或者負責做動作的所以整個Agent的部分你可以把它想像成它其實就包含硬體跟軟體

[0:26:27] 那當然啊很多時候我今天我也沒有說一定要驅動一個什麼實體的機器人在做什麼事情我完全在虛擬空間當中去進行虛擬來做一些事情模擬一些事情也可以說是一個Agent也可以說是一個Agent因為在那個模擬的空間裡面它的Sensor其實就是可能就是我輸入的資料我就已經感測到我直接輸入那些資料給我的Agent Program然後呢我的Agent Program可能操縱一個虛擬的人物往右走往左走所以它不見得一定是要搭配實體世界的這個真正的東西所以In that case在虛擬世界當中呢Architecture其實就是譬如說好像我們玩電玩我們所操縱的那個虛擬人物它其實就是你的Architecture好那我們先從一個最簡單的假設我們要開發一個Agent Program一個最簡單的做法就是我就寫規則嘛或者我寫一個表格嘛對不對我今天當我遇到一個什麼樣資料的時候我就做一個動作遇到什麼樣資料我就做一個動作或者連續我接收到哪些資料的情況下我就做什麼樣的動作就用查表的方式這是Very Very Trivial的Agent Program

[0:27:58] 但是我們很快就知道說這個東西一定不可行吧因為我們不可能列舉所有的狀況然後把這個Table寫得很長很長對不對然後不可能是用這樣子來做比較具體可行的一個最簡單的做法呢叫做Simple Reflex Agent那它簡單來講就是說我也不要看很長時間的資料我就是隻看單一一個瞬間然後呢我去寫一個規則來做動這個就是我最最簡單的Agent Program所以譬如說之前的那個吸塵器的例子欸如果現在我所在的地磚是髒的那我就吸塵嘛OK如果我所在的地方是乾淨的然後我就會進入到這裡嘛我如果現在的位置在A那我就往右走我如果現在這個地磚是乾淨的然後我的位置在B那我就往左走就這樣就這麼簡單的規則它就是一個最最簡單的Agent Program只考慮單一一個瞬間收到的資料然後我去做一個反射性的動作OK這是最簡單的Agent好那畫成示意圖的話可以長成像這樣嗎就在環境裡面我透過Sensor我取得了一些資料

[0:29:30] 然後呢我看了這個資料之後我根據這裡的規則寫出來的規則來去決定我要做什麼動作這樣子好就這麼簡單那你說那可不可以進步一點呢有下一個再進步一點的叫做Model Based Agent它的意思是說我今天我每次我收到訊息之後收到資料之後我也許這個資料不完整OK不完整我可能先往左邊看我看到左邊的資料圖那我右邊還沒有看到嘛可是我如果今天我先往左邊看看到左邊的資訊我能不能夠累積我所看到的資訊然後我再統一做一個比較好的一個反應好所以Model Based Agent跟那種簡單反射式的Agent就是說它有一個Internal State或者是有Memory的這個概念你Sense到資料進來之後它會儲存過程的資料它會儲存過去它看過的這些資料所以說它可以理解說我目前這個Involvement狀態是怎麼變動的那我現在看到了什麼然後我不只是這樣我還剛剛前面那個瞬間狀態是什麼樣

[0:31:00] 我在剛剛那個瞬間我做了什麼動作以及我在現在這個瞬間我看到了哪些資料我一起統整來去決定我要做什麼動作來去決定我要做什麼動作那在這裡呢決定做什麼動作依舊是一些規則所以它相當於是考慮到更多情況之下然後還是根據規則來進行你的動作的判斷這叫Model Based Agent好那所以呢這個依舊是相當的簡單那在下一個部分就是說很多時候呢我看到我目前的環境的狀態是如何讓我們很有效率的去運作這個Agent所以事實上呢這個Agent呢有時候是需要一些目標的你告訴他目標當我在進行決策的時候他要決定的事情是我做哪一個決策會離我的目標更快接近我的目標那這一類的Agent就叫做Goal Based AgentOK Goal Based Agent那Goal Based Agent的行為呢為什麼這個會比Model Based來得更好因為它可以當你的目標變了我其實中間的那個

[0:32:30] 他會採用的行為也就變了所以說呢他的Behavior can easily be changedto go to different destinationSimply by specifying the destination as the goal那隨著你的目標變動你已經運作到一半了你目標如果突然變了他有辦法即時的現在因應性的目標做出新的動作決策所以說跟前面兩種Condition and Action Rule這種做法不一樣的地方是說他要考慮到未來他不是隻考慮到我過去看到哪些資料然後根據某種規則來進行決策而是我考慮到我如果做了這個決策我的未來會不會變得更好會不會讓我更Happy會不會讓我覺得更好這個叫Goal Based Agents所以說呢你可以看到說他不只有過去這個世界怎麼變動的過去我怎麼做動的我另外在進行決策的時候我要考慮到我的目標是怎麼然後呢我是要往目標去前進OK而不是隻看我過去已經送到的資料這叫Goal Based Agents然後那Goal Based Agents還不夠啊他還沒有辦法做出高品質的行為在有的時候沒有辦法為什麼呢

[0:34:00] 因為有的時候你只告訴他目標是不夠的原因是有時候你有好幾個目標而這幾個目標是衝突的比如說我們去搭計程車我們又希望越快抵達目的地越好然後又希望你的整個行車的過程越安全越好這兩個目標有一點點衝突你希望越快抵達那就是司機要開比較快啊可是司機開比較快就可能越危險啊對不對那我們是不是兩個目標我們都想達到所以有的時候呢我們的目標不只一個我們有多個而這多個還彼此衝突那所以在這種情況之下呢我們就要考慮的是所謂的Utility based agentUtility這個字呢就是效益的意思你做了某一個決策之後他當然是要往目標前進但是他往目標前進的效益有多高我要去取我要去做出一個整體而言效益最大化的那個動作因為我今天好幾個目標我會彼此衝突我只好權衡之下選擇比如說你今天是要越快抵達目標目的地還是說要安全的你可能想說生命層可貴

[0:35:31] 對不對我慢一點沒關係我寧可我要安全一點或者是說呢今天我知道我這一路上要經過的沒有什麼複雜的路口OK那大概不會有什麼太多安全的疑慮那我就是越快越好這個你都是可以去進行所以你的效益的定義也會根據你的這個不同的應用而定所以說呢我們這裡講說一個理性的Utility based agent什麼叫理性的我們上次有介紹過一個理性的Utility based agent他會最大化預期的效益當我做一年我在進行決策要take某一個action的時候他就是要去最大化那個可能的預期的效益好那這是一個示意圖啦就是說我不只知道過去的這個行為模式跟狀態的變化我還要去預估說現在的這幾個目標整體而言我如果做了某一個決策我帶來的效益有多高然後我可能我可以比如說我可以往右走我可以往左走我可以往前我可以多加速一點或者說我要煞車一點整體而言在這麼多種可能性裡面選擇一組最好的參數來最大化我可能達到的效益

[0:37:01] 這個就是所謂的Utility based agentOK好那最後一個就是Learning agents我們當然希望說你能夠評估效益那你最好你這個agent你在進行決策的這整個的過程不要由我們人來設計而是你自動從資料裡面去學會OK那這個就是Learning agentLearning agent is responsible for making improvement我們希望他越做越好OK好然後最好是你根據過去的你所收到的資料你做過的行為那我們現在也可以評估效益了吧那我們就發現說今天在下午三點的時候我走某一條路時數開多少我上次是這麼開效果不錯那我下一次在差不多三點的時候又有同樣的客人需要我做去某一個目的地的時候我是不是有有那個能力知道說我上次的那個很不錯那我這一次呢就繼續用這樣的模式來走譬如說上次我走某一條路很不好我是不是可以這一次我就避免做這件事這個就是Learning的一個agent要做的事情所以你看到這個設計圖就是說

[0:38:31] 資料進來之後你可以去評估我的效益然後當然你可以做一些比如說監督室的學習那來給他一些評判OK這個上次做的某些agent好或不好你給他一些監督的訊號然後呢讓他反覆不斷的去變動他的這個agent program然後呢越做越好越做越好好這個就是Learning agentOK好這個講起來非常非常的虛幻有沒有講得非常high level那講完了大家好像也不太知道這到底在幹嘛但事實上你可以想像得到這個Learning agent呢其實就是後來我們慢慢的從機率推論變成Machine learning到現在過去這十幾年的Deep learning其實基本上就是Learning agent這整個過程那以上講到這邊這個就是第二章我們說過第一章跟第二章都是聊聊天的講得非常非常的high level非常非常的high level好第二章講到這邊有沒有什麼問題在slido上面他說PPT不定時會狂散我不知道助教有看到嗎會散嗎

[0:40:12] 可以去NTU Google討論板分組表格在哪裡OK我剛剛說了請好好上課OK來那我們就先休息一下再回來休息十分鐘再回來進行下一章你說要做要偏向研究的方面會比較偏向去做改善去研究會更好會更好對如果除了這個你是想做什麼因為前陣子Google有那個蒼蠅那個model什麼蒼蠅的那個蒼蠅蒼蠅那個model對它可以拿來跑一些environment我想要拿它跟一般的Iron去做comparison可以啊我想說那這樣的話這個算是一種study嗎還是它算是就單純比較我沒有去針對它去做不如我只想要做

[0:41:42] 比較說這樣一種有什麼樣的差異可以可以啦這樣就是可以的可以啦我們要求沒有到那麼高畢竟是一門課不是一個研究論文然後說我好想怎麼improve它你能improve當然是更好啊順便就當作是你是研究生還是大學生我是研究生但是我的研究是我是說那你就要你最好是想一個你做出來之後對你研究有幫助會更好你就不是為了修課的修課你根本就是為了你的論文對啊你這樣就是為了修課所以你做一個跟你錄宏觀的這樣比較不划算

[0:43:20] 好接下來呢

[0:53:20] 我們要開始第三章OK我們先從一個最簡單廣來講說我們如果利用search我們把解決問一個所以第三章呢講的是solving problems by searchingOK沿襲我們之前所說的這個goal based agent角色呢我們現在先不管後面更所謂的utility based或者是learning agent我們先回到goal based agent這邊goal based agent呢他考慮的是說我今天收到一些訊息之後我要做一些決策然後看是不是能夠離我的目標比較接近那我們來考慮我們考慮其中一種goal based agent的方式這個叫做problem solving agent那在這一章裡面呢我們把我們的討論呢侷限在最簡單的PEAS其中呢它的solution都可以當成是一連串動作A sequence of action或者是action sequence我們的解答就是一連串的動作這一類的問題那我們呢

[0:54:52] 這一連串的動作呢我們去找一連串的動作來完成我們的目標這件事情呢我們稱呼它叫做search我們要去搜尋出一連串的動作來達到我們的目標那我們的一個解答呢其實就是這一連串動作裡面的某一串動作那它可能能夠讓我們達到我們的目標這樣子好那我們舉個例子講了半天虛擬的我們直接舉一個實際例子就像這一個這個是一個羅馬尼亞的地圖那上面的每一個點呢代表的是羅馬尼亞的一個都市那剛好為什麼舉這個例子因為恰好呢這個都市的名稱的開頭剛好就是ABCDE一直到Z幾乎啦所以它故意舉一個這樣的例子假設我們有一個羅馬尼亞的地圖然後呢有ABCDE到Z的城市比如說有Arab這個都市啦然後有什麼Sibiu的這個都市啦什麼等等等等那某一些都市之間呢有道路相連那假設呢我們也知道說比如說從Arab到Sibiu中間是離140公里比如說單位叫公里好我們現在的目標是我們現在給一個任務這個任務是呢

[0:56:22] 要你從A走到BArab走到BucharestBucharest其實是羅馬尼亞的首都我們現在給你一個任務要你由A走到B那你走哪一個路你路徑要怎麼走會最好呢這個就是我們現在要解的問題好那所以來定義一下這個問題啦一開始呢我人是在A這個都市那我在A這個都市我可以做的動作是什麼呢就是我走去S這個都市或走去T或者走去Z因為為什麼因為你看從A可以走出去的路一個是Z嘛一個是S嘛一個是T嘛對不對它可以做的動作就是這三個動作的其中一個看你是要走去哪一個都市那Transition Model的意思就是說你做了你選了某一個動作之後你做了那個動作你的狀態會怎麼變動這個叫做Transition Model那In this case就是說我本來在A這個都市我假設要走去Z這個都市的話呢我造成的結果就是我後來人會跑到Z這個都市好所以這裡回顧一下我們剛剛上一節課講的這樣子的環境是Deterministic還是Stochastic是Deterministic

[0:57:52] 因為我們是假設說一旦我們說要從A走到Z我們的下一個狀態就是我們真的會到Z這是一定的所以它是Deterministic然後呢有沒有抵達終點呢那就看說我經過多次的走訪之後我是不是身處於Butcher Ranch的這個都市如果是基本上我就達到了我的目標了那我們要定義一下我這樣子走我要花的我的花費我的Pass Cost是什麼呢就是我每一條路徑每一條路徑上面你走的里程我希望我走的里程是越小越好也就是說我花的油錢或者我花的相同數目之下我花的時間最短這個叫我的Pass Cost這樣子那這個問題裡面的一個這個問題裡面的Solution它其實可能有很多Solution對不對我可以這樣子A走到Z走到O再走到S走到F再走到B這是一個這是一個Solution我也可以A走到S走到R走到P再走到B這也是另外一個Solution對不對所以其實這個問題有很多的Solution任何的一個Solution怎麼表達呢其實就是一連串的Action對不對走到Z是一個Action

[0:59:23] 再走到O是一個Action再走到S是一個Action對不對所以一個任何的一個解答都可以用一連串的Action來表達OK那這個就是這個問題的整體的地方好那這是一個我們之後會用的例子我們順便也介紹其他在往後不只這一章在往後其他Chapter也可能會用到的例子其中一個例子是這個叫做A puzzle problem大家可能都玩過好這是一個九公格上面有八個八塊編號12345678八塊好那其中有一格呢是空的好那這一個問題呢就是我隨機的把編號1到8的方塊擺在九公格裡面然後要你去移移動這些方塊使得最後呢你的方塊的這個擺放會長這樣最左上角是這個空格然後呢12345678照這樣子排好OK好這個就是這個問題的狀態是這樣所以呢每一個狀態就是任何一個在九公格裡面有擺一個擺八塊這個木塊每一個排

[1:00:53] 每一個盤面都是一個狀態好那Initial state呢就是看你隨機從什麼樣子的狀態開始吧你的Action是什麼這個問題裡面的Action就是實際上我們是去移動那個有數字編號的木塊嘛對不對但是這樣子你有好幾塊都可以移呀所以我們把問題稍微趕一下我們把空格這個也想成是一個方塊所以我們把它想像成是我有這個空格這方塊我這空格可以往左移往右移往上移往下移比如說你這個空格往上移就等於是你二號往下移的意思嘛好所以我們把它的Action呢想像成就是我的空格這一塊是可以上下左右移的這樣那你的Transition Model就是比如說你空格如果往上移你現在一個狀態就是你二號跑到中間來空格跑到上面來嘛所以這也是一個Deterministic的一個EnvironmentEnvironment好Goal Test呢Goal Test就是看看最後的盤面是不是長這樣嘛對不對好那你的Pass Cost呢你這樣子移來CVA去你所需花的費用是什麼我們把它定義成你要移多少次我希望你移越少次你越快達到右上角這個Goal State越好所以這個就是這個定義好那你這個

[1:02:24] 我用這個我用一個我用這個我用這個我用這個我用這個我的意思是我的意思是如果你有帶我用這個有這個你其實我用這個你直接可以他就是他有一個有一個有一個有一個有一個有一個有一個有一個有一個有一個我有一個我買了一個夠小的很便宜挺便宜的皇后這個旗子呢它會攻擊跟它同一列跟同一行還有跟它同一個對角線上面的所有的其他的旗子OK 好所謂的八皇后問題呢就是說在一個這樣的盤面12345678在一個八乘八的一個旗盤上面呢要你擺八隻皇后使得你擺完之後的結果呢皇后們不會互相攻擊比如說像這個例子這個例子呢其實有沒有符合八皇后的沒有呢其實很快就知道沒有這一個會打到這一個因為這是同一個對角線對不對這個還好這個會打這裡也會打這裡然後它所有的對角線都沒有打到這個OK所以所謂的八皇后問題的目標就是你這八隻皇后應該要怎麼擺會讓我最後擺完然後盤面上的八隻皇后不會互相攻擊

[1:03:55] 這個就是這個問題的定義所以它的State是什麼它的State就是一個盤面你可能放0隻皇后到8隻皇后你一開始是什麼你一開始是一個空白的旗的一個盤旗盤然後你要一隻一隻皇后把它放上去某一個位置這樣子你的Action是什麼你的Action就是你把皇后放到某一個位置這就是你的Action傳記序Model就是什麼比如說你要放在22這個位置你把它放上去之後呢那接下來盤面就是22那個位置位於一隻皇后就這樣這個就是你的傳記序Model那你的目標就是說有8隻皇后在盤面上彼此不互相攻擊所以我們這裡介紹了三個不同的例子接下來世上還有很多很多這個實際實體世界當中有很多很多各種不同的問題那這些問題呢其實很多是資工系的同學你在大二修演算法的時候你可能都有碰過的問題比如說Traveling salesperson problem或者說你現在在做電路設計的你會有Layout problem或者說你現在在做自駕車的會有Robot Navigation problem這些廣義來講都屬於像要介紹的這些問題

[1:05:31] 來得更為複雜當然我們上課我們就先從最簡單的開始講起但從像話來看它要解的它都是一種Problem solving的agent你要建構出一個Problem solving agent好吧那我們就先從地圖這個問題開始我們要如何找到一個解答呢我們要從A走到B在這個問題裡面呢我們有一種做法是我們把這整個行走的過程它可以走的Action它可以做的Action或者說它可以走過去的都市整體而言表達成一個Search Tree表達成一棵樹這棵樹的Root出發點就是A這個都市OK那簡單的我們知道嘛你從A這個都市出發你可以走到S你可以走到T你可以走到Z那同樣的你如果走到S的話呢你可以走到你可以走回A或者走到F或者走到O或者走到R依此類推所以你是不是可以把你要從A走到B的這整個的過程你可以展開成一棵樹對不對你可以展開成一棵樹那這些事情顯然的很容易用來表達剛剛羅馬尼亞地圖這個問題那其實可能也可以用來表達

[1:07:01] 這個九宮格的這個問題啊比如說我今天在這個Tree裡面呢某一個Node代表的是某一個盤面的意思這個Node的Parent其實就是能夠造成這種盤面的上一個步驟會造成這個盤面的有可能是我前一個盤面呢4號在最右上角空白在這裡或者說前一個盤面就是8號在最右上角空格在這裡那它有可能造成我現在這個Node長這樣所以它的Parent有兩種可能那同樣它的Child呢它的Child可以是我從這個盤面可以繼續往下變動的情況所以它的State就是代表一個盤面它的Parent就是能夠造成這個盤面的上一個動作那它可以做的Action就是我今天如果把這個空白往下移那就8號跑到最上面如果往左移就是4號馬來村右上角空白跑到這裡那PassCross的其實就是你在這個Tree裡面行走你多走一個分支多走一次分支就代表我這個空格多移動一次的意思對不對就好像說剛剛這個從A走到B的這個Tree

[1:08:32] 我多走一個分支我就要付出我的里程數那就是我的PassCross所以我們剛才有把問題像這一類的問題我們可以把它描述成在一棵樹上面來找尋剛剛講P.E.A.S我們要如何去評某一個演算法我們還沒有跟大家講你可以用什麼演算法但是我們先來定義一下我們如何去評判一個演算法有幾種不同的指標第一個Completeness它的意思是說如果這個系統有解的話如果這個問題是有Solution的話它是不是一定能夠找到Solution比如說我從A走到B可能我有很多種走法對不對我有好多種Solutions那評判一個演算法的第一種指標可能是說如果它有Solution你是不是一定就能夠找到Solution當然也有一些問題是沒有Solution的那種就目前暫時不在我們的考慮如果它有Solution是不是一定能夠找到Solution這個叫做Completeness這叫Completeness第二個如果它可以找到

[1:10:02] 找到了是不是最佳的Solution這個叫做Optimality這個搜尋的策略是不是能夠找到最好的解第三個Complicity實踐複雜度是怎麼樣你要花多久的時間來找到解答OK那這邊當然就會跟電機資工的同學你可能會比較熟悉Time Completeness如果你不是電機資工的可能你自己要補充一點背景知識那再來就是Space Completeness就是你的這個演算法的運作你要花多少Memory你可以從這幾個不同的角度來去評判一個演算法那我們先來講一種最簡單的做法叫做Uninformed Search又稱呼是Blind Search就是盲目的搜尋有一大類的演算法是這種所謂的盲目搜尋這個的意思是說呢這種策略是說我除了告訴你原本問題的定義之外比如說除了這個羅馬尼亞的地圖我告訴你羅馬尼亞的地圖然後ABCD到Z的都市的都市以及它個別的道路的連結還有道路連結上面的里程數

[1:11:34] 我除了告訴你這個之外我其他全部不告訴你那你就依賴我告訴你這些資訊去找出如何從A找到B這樣子這種叫做Uninformed Search的這個分類All they can do is to generate successorsand distinguish a goal statefrom a non-goal state他能夠做的事情就是說我從某個地方出發然後往外走然後走過去之後呢判斷一下說這是我的目的地就這樣他只能夠做這件事那不同的搜尋策略它如何進行不同的分類我如果去區分它呢那就跟我今天是用什麼樣子的順序來搜尋這一棵樹是有差的那相對來講呢如果說我知道的比剛剛問題的定義更多的話比如說我大概知道往哪個方向走可能會離B這個城市更接近的話如果我額外多知道這個資訊的話那它就屬於是Informed Search或者是Heuristic Search的範圍那這個我們等一下再講我們先來講Informed Search其中一個最有名的應該大家大一大二也都學過的演算法就是BFS

[1:13:04] Bread First Search寬度廣度廣度優先的搜尋演算法那它其實概念很簡單就是說呢我就先從A我從A出發嘛那我去走去B走去S看看是不是我的目的地如果不是那我再去看從A這邊我走去T是不是我的目的地不是那再回過來我把A可以走出去的所有分子都先走一次都走一次然後呢都不是我的目的地嘛那接下來我剛剛的第一個分子是S我再試試看我從S走出去的所有分子看看有沒有走到我的目的地就這樣依此類推一路這樣子往下展開所以底下這是另外一個示意圖從A先check一下B是不是目標不是回來再走C是不是目的地不是回來再從B繼續往下走它的分子D是不是不是E是不是不是那一路這樣子展開所以它是屬於廣度優先的搜尋策略OK就這麼簡單它就這麼運作了那BFS呢你可以想像稍微分析一下假設啊在這個tree裡面每一個node都有B這麼多個successor

[1:14:34] 也就是說都有B這麼多個分子可以走好所以呢因你從root出發你就有在你往下的第一層你就有B這麼多個分子那每一個分子另外又有B這麼多個分子所以在第二層就會有B平方這麼多個node再往下一層就會有B的三次方這麼多個node因此假設你要把整顆tree假設這一顆tree它的深度是D也就是說有D這麼多層的話你會展開出多少個node呢就是B加上B平方加B正方加上B的D次方對不對好那這個東西呢就這個time complexity來講它就是BIG OF B的D次方好那抱歉如果說你沒有學過BIG OF的話同學你可能要自己去查一下我們假設你來修正門課你其實是有這些幾個素養的這其實是子宮可能大二的時候會介紹的對不對time complexity的一個說明所以它其實它的time complexity以及它的memory的需求其實很大的這是BFS好那我們來看一下這是一個範例這個多大呢有那麼嚴重嗎假設今天我平均每一個node都有十個分支

[1:16:04] 假設我走訪我去check一個node我去generate一個node所需花的時間呢是假設我一秒鐘就可以check一百萬個node好了一秒鐘好那假設每個node呢是1K1千對1K好1千個byte好那今天你的這棵樹的深度如果是兩層的話你就為110個node你要花0.11個minisecond你要花107K kilobyte如果你的深度變成十層你就為十個十次方個node你就要花三個小時去generate這些node你所需的memory就會十個terabyte如果是十六層你就要花三百五十年去generate這些node然後呢你的memory是十個exabyte所以事實上我們可以知道說當你的這個tree的深度增加的時候你所需的時間跟所需的空間會急劇的增加這是BFS好好那另外一個聰明一點一樣是Informed Search的一個策略大家可能有一些同學也都學過了就叫做Dijkstra Algorithm

[1:17:34] 這個是在理論Theoretical Computer Science這個領域裡面這個去稱呼它在AI這個領域呢其實因為當年幾十年前大家其實都各自發展嘛有時候也搞不清楚別人已經提過同樣的東西了在AI這個領域當時提出來的時候它叫做Uniform Cost Search但其實它跟Dijkstra Algorithm是一樣的意思它的意思是說呢Uniform Cost Searchexpand the node n with the lowest pass cost g n也就是說每次我在展開我要決定我要往哪一個分子走的時候像剛剛的BFS是我管它的我就每一個分子我所有可以走的分子我就走一遍嘛對不對好那它現在有一個選擇性它利用到我走過去之後需要花的里程這個資訊因為這個也算是我一開始的問題一開始問題在定義的時候就已經有給過的資訊The algorithm tests for goalsonly when you expand a nodenot when you generate a node好所以這裡舉個例子假設我現在已經走到S了我接下來可以走到R也可以走到F那我走到走去哪裡呢那我們看一下吧我如果走到R我如果去走到R我會花80

[1:19:06] 那你從R再繼續往下走你如果真的expand的時候你expand你真的走過來的你真的走過來那接下來呢你去check一下這是我的目標不是R這個都是不是我的目標我的目標是ButcherRest這個嘛所以呢我走來這裡了我花了80然後呢我去Generate它可以走出去的分支它走出去的分支就P嘛那P的話呢其實我已經知道說我如果是走P我如果走P這條路我要再加97這麼多個cost所以我就知道了我走到這裡來呢我的cost已經知道就會是80加97啦好那接下來我現在如果是走這一條的話我會需要花177的cost那接下來我看一下另外一個分支我另外這個分支這裡只要99耶那我走過來看看那我走過來了但是因為這個過來之後呢它接下來也只有一條路這一條路我Generate出來是211那我就知道說99加21所以其實我如果走這一條路啊我要刷3110那我就相較之下那我就知道說其實這個也不是那麼好所以我就回過頭來走這個1

[1:20:38] 然後expand到P然後呢再Generate到101那怎麼加起來呢是278所以相較之下呢這個278是一個比較好的一個路徑所以它到現在這個Gystra Algorithm呢它就是一個有利用到你的Cost有考慮到Pass Cost的一個演算法這樣好所以這裡要釐清一個點就是說Uninformed你看字面上的意義Uninformed的意思就是說沒有被通知沒有被告知的意思所以這裡Uninformed的意思不是說完全沒有任何資訊它不是這個意思就是說它沒有用到任何關於目標有多元的額外資訊好好那所以說呢這個Uniform Search基本上呢It's optimal in general什麼意思回到剛剛我們講評判一個演算法好不好就是說你如果可以找到解的話你找到的是不是最佳解好他說呢這個Uniform Cost Search呢基本上可以找到最佳解其實BFS也可以找最佳解啦你去全部都掃一遍然後找到Cost的最低那個就是你的最佳解好那Uniform Cost Search呢Expand node in order of their optimal Pass Cost

[1:22:10] 不過它在Expand node的時候是有稍微聰明一點稍微聰明一點那他說呢它是Guided by Pass CostRelative Depth所以你在展開的時候啊是根據你走到目前這邊為止你所需花的Cost來進行展開的確定跟BFS不一樣BFS是我就先展開第一層再來展開第二層再來展開第三層所以它是Order by DepthBFS是Order by Depth然後呢Uniform Cost Search是Order by Pass CostOK這是最主要的一個差別那到時候步驟如果假設今天你不管走哪一個分支你的Cost都一模一樣的時候呢其實Uniform Cost Search呢就類似像是BFS一樣這當然這是一個特例好那所以大家也算有學過BFS廣度優先的搜尋那你也學過DFS啊深度優先的搜尋我想很多人也都知道了那就是說呢我一條路走到黑我第一從Root出發我展開第一層那接下來呢第一層的第一個Node我再展開它的分支的第一個分支

[1:23:41] 然後呢我再走第一個分支的第一個分支的第一個分支一路我把走到最深層為止如果走到Edge這裡不是我的目的地那我就回過頭來到上一層再走上一層的另外一個分支看一下II也不是我的目的地那我再回到上面的D再回到上面的B然後再去展開這個E然後依此類推E再往下展開然後呢K再展開依此類推這叫深度優先的搜尋那DFS呢它的Time Complexity呢是Bounded by the Size ofState SpaceIn general may generate all of thebig ol' B的M字吧其中M呢是Mesmer DepthM呢對就是說假設今天你每一個Node都有B這麼多個分支然後假設你的深度是深度是最深的那個最深的那個層數比如說我今天這個數可能長得歪歪的雖然我們這裡的數看起來都好像是左右非常的平衡

[1:25:11] 但是其實有可能是左邊這個數啊一路往下長長十層然後右邊這個分支的數可能只長三層所以呢這裡的M指的是最深的那一層的深度這樣在最糟的情況之下呢DFS呢有可能會生出big ol' B的M字吧其中呢M可能遠大過於DD指的是The Depth of the Shadowless Solution你說不定啊你真正的正解是在右邊的那個指數的一個比較淺的地方就已經是你的解了可是你如果你是深度優先的展開的話你會花很多的時間去展開左邊很深的數好然後殊不知展開完之後這個根本就是你真正要的解答其實就是在右邊的這個指數的一個很淺的地方就有了OK那這個就是最糟的情況這DFS但是DFS的優點是說它的Space Complexity是比較低的比如說它只需要儲存它目前展開維持的這一條路徑上面的這些Node就好了其他都不用記

[1:26:42] 其他都不用記當然要記一下我目前展開的最深的這個它的兄弟的Node是誰吧所以它的Space Complexity是遠低於BFS的我們剛剛說過說那個廣度優先的搜尋又花時間又花Memory那DFS呢至少不太花Memory因為你光看這個其實它在展開左邊的指數到最深的時候它只需要記錄下這個啦A B D I還有這個E這裡而已啊右邊的這個這個這裡都不需要記啊這裡都不需要記那反正這個如果不是我的目標我就回過頭來我只要這都丟掉了嘛這反正不是我的目的地嘛所以它一次只要處理一個Pack幾乎是一個Path上面的Node就好我只要記這些就好這是DFS的優勢所以理論上來講呢State Space它的Branch是B然後呢它最高深度是M的話呢它大約只需要儲存Big O BxM所以它所需的Memory是小很多的OK好這個理論上大家應該都學過了都應該學過了好那當然我們知道啦這個DFS呢它有它的缺點嘛如果說今天要是很衰

[1:28:12] 我左邊的指數很深那但是我根本我的解答就在右邊指數的很淺的地方那就很衰嘛我花那麼多時間在展開左邊指數那所以要如何取得一個平衡呢有一種做法叫做Depth Limit SearchDepth Limit Search意思是說你是跑DFS沒有錯但是呢你給它一個限制你往下搜尋你最多就搜尋L這麼多層你在左邊指數你搜尋最深到L這麼多層搜尋不到你就要回來了你要去看一下右邊的指數這樣大家懂我意思嗎其實這樣子的邏輯我剛剛突然想到這到現在這個邏輯一樣是通的喔我們現在不是你跑過那個GPD-6 ASTRON沒有他幫你做一些工作嘛對不對所以你假設你今天交付給他一個工作這個工作可能有幾種方法可以完成但是哪一種方法可以完成他不知道好有三種方法可以完成如果今天他是用類似比如說第一個方法又可以拆開成三種不同的策略或子方法

[1:29:47] 那每一個子方法又有三種不同的input方式對不對然後呢每一個input方式又有三種不同的參數設定所以你看你想像一下even到今天你在跑GPD-6 ASTRON你叫他做代理他如果是笨笨的一路都把第一個方法裡面的第一種input方式裡面的第一種參數設定完再怎麼樣都弄完了然後再回過頭來看一下第二個方法DFS的話我相信你們應該很快就會覺得說他怎麼跑那麼久所以我相信呢當然我不知道他是怎麼做的但是他們一定有某些策略是讓有效尤其在之前比較早期在我們A群會產生鬼搭牆一直跑步不斷的在那邊繞然後走進一個死胡桃所以這裡就有點類似像這樣你可以做所謂的Depth Limit Search你讓他深度最多你要求他最多就是走到L位置那你也許可以避免掉那麼衰花很多時間在處理左邊的某一個指數明明答案就在右邊的一個比較淺的地方但是這裡有另外一個問題那說不定我真正的答案就是在左邊指數很深的地方

[1:31:18] 對不對所以你如果只限定他說我的深度最多可以到L那他可能就找不到解了所以如果是Depth Limit Search他就是IncompleteComplete的定義就是說如果這個問題有解的話你一定可以找得到解那如果你設定了一個Upper bound L的話那有可能找不到解然後你找到的解也有可能不是最佳解那他說有的時候這個Depth Limit的演算法其實如果你對於這個問題你有一個整體的Extra的Prior Knowledge的話有一些事前的領域知識的話其實搭配起來可能是可以更有效率來解決你的問題的比如說在這個羅馬尼亞的地圖裡面Somehow你知道說從任何某一個都市走到另外一個都市絕對不會走超過9條不同的超過9步那你如果是這樣的話你就可以把你的深度的限制設定成9因為你最多不可能走超過9步如果你有這個知識的話你就可以設定這個L那既然L

[1:32:49] 你設定了一個L你怎麼知道這個L要怎麼設定呢除非你有這個知識那你如果沒有這個事先的領域知識的話有另外一種策略叫做Iterative Depth DFS那就是我逐步的增加我的深度所以一開始我允許你展開一層DFS做一層最多往下深入一層如果都沒有找到解答那我就允許你最多深入兩層再沒有找到答案我最多允許深入三層一步一步的增加我的那個Libid L逐步的增加那個L這樣好那如果是這樣子的話呢它其實這種做法呢就有點混合了DFS跟BFS的好處那比如說就像DFS它的Memory Requirement是低的啊所需的Memory是低的啊那就好像BFS它在限定之內它真的是把所有可能的狀況都掌握了啊好The branch factors is finite and optimalwhen pass cost is a non-decreasing function of depth當然你的pass cost是你多走一步你的cost就會增加它是一個non-decreasing就是不會多走一步你的cost不會降低一定是往上增加的這叫non-decreasing

[1:34:20] 好好所以這個概念就像這樣啊我允許你一開始呢我的深度限制是1那你就是一次你一定就是展開一層沒找到答案我讓你深度限制是2沒找到答案我讓你深度限制是3這樣一步一步的放鬆我的管制直到你找到你的答案為止這樣子好可是你聽到這裡有沒有覺得這樣好嗎你不會覺得說這樣子好像浪費了很多有些地方好像重複的去展開啦比如說你看啊我假設允許你的深度最多到三層你看啊在展開到第三層之前這裡四層相似這裡不是剛剛這裡有做過嗎包括這裡有做過嗎所以你會覺得說當你把你的limit提升到三層的時候感覺從這裡到這裡的這個動作這裡到這裡的動作剛剛這裡有做過啊那我不就浪費了很多的時間我浪費時間在重複做同樣的動作會有這種感覺的確直觀上你會有這種感覺但他這裡告訴你對的確是有一點浪費但是沒有到你想像中的那麼浪費好

[1:35:50] It turns out this is not too costly為什麼呢因為啊這個樹呢他大部分的node甚至超過一半以上的node其實都是在你展開的最深的那一層這裡也就是說雖然你今天你的limit從二提升到三可是你如果仔細看一下你limit如果是二你這裡展開的node分別幾個一二三四五六如果不算 root的話就六個嘛可是你如果今天展開到三層你看三層的最底端就有一二三四五六七八光這裡就有八個node耶所以呢你不要那麼在意三層以前的這裡一二三四五六這才六個node對你可以說欸那我第二層第一層到第二層的這六個node我是又重複展開一次啦對不對對這部分的確是有一點浪費但他的浪費沒有浪費到你你覺得超浪費耶我在講什麼因為為什麼原因就在於說你越如果你這個tree越深你最底層的最細的最底層的這些node的數量一下子就會遠遠超過往上一層的所有的總和

[1:37:22] in this case他就是超過的嘛像這個就已經是包含了一二三四五六七八八個node而第二層加第一層的總共展開的node也才六個這件事情在你深入越深的時候那個差距會越大所以的確有點浪費但沒有浪費到你想像中你直覺想的那麼誇張這個就是所謂的Iterative Dimple DFS那我們把這部分講完我們再講下一個再休息好啦那所以呢我們剛剛前面講過BFS跟DFS對不對好那聰明的人就想說那我要我其實在搜尋的時候我當然目標就是說最好是越快找到答案越好那我所說的我需要的記憶體能夠越少越好好那所以呢就有人想說欸反正我從一個地方出發我要走到我的目標也如果只有一個的話我可不可以把目標也當成是一個出發點對不對我從A要走到B嘛我從A出發一路這樣展開然後呢我也從B這個地方出發一路往回推欸要是走走走走走走到中間某一個地方剛好交匯到了我就把它整個串起來

[1:38:53] 好不好對不對這就好像說這個我們在蓋那個血稅的時候臺北到宜蘭血稅的時候當時蓋啦是兩端同時兩端同時從宜蘭往臺北方向臺北往宜蘭方向兩端同時蓋然後最後接起來這樣子欸對嘛這個現實這個概念上是這樣沒有錯你可以從start出發點一路往外展開然後呢目的地一路往外展開那在完美的情況下呢概念上呢你可能只需要展開Big O B的二分之D次方D是指深度那你有兩個Big O二的二分之D次方其實就是Big OB的二分之D次方這個數值呢遠遠小於B的D次方這個叫Bidirectional Search雙向的搜尋那Bidirectional SearchIs implemented byrepressing the goal testwith the checkto see whetherthe frontier of two searchinteractintercept它不是在找說欸我是不是已經抵達某一個目的地了它反而是在確認說欸我兩條支線有沒有交匯有沒有交匯如果有交匯那我就找到一個解答了那這裡面呢

[1:40:25] 真的要做到這件事其實並不容易啊因為你從你的目的地出發往回找這件事情不見得容易好 不見得容易以這個地圖來講相對是容易的因為你就看著那個地圖嘛對不對你從B這個城市出發你往外可以走哪裡是很明確的OK所以你如果以羅馬尼亞的這個問題來講你可以用白的Rational Search好可是呢你如果然後你如果是從A puzzle problem就是那個從那個九宮格的那個問題也相對容易你的目的地在哪裡然後呢一路你去移動你那個空格好所以往回找上一步是什麼這是相對容易的但是如果說你的目標是一個比較抽象的描述比如說八皇後的問題八皇後的問題是什麼就是沒有任何一隻皇后會攻擊其他皇后你的目標組是這一種的話那白的Rational Search就很難implement就很難說某一個盤面的前一個動作一定是怎麼樣那這是白的Rational SearchOK

[1:41:56] 好那所以呢第三章這裡呢其實我們講完一半了它主要就分兩個兩大塊一塊叫做On Informed Search就是沒有額外知道目標資訊的搜尋法那下一個下半部分我們要講的就是Informed Search你如果知道一些額外的資訊的話你的找到解答的這個效率會很高OK好 講到這邊有沒有什麼問題我們看一下線上請好好上課這個我也獨宗家族園可以嗎只要不要超過四位是可以的我們過去也曾經遇到過就是說誒 本來比如說三個人一組好了後來這個課修到一半的時候撐不下去退選了落跑了然後就只剩下一個人自己一個人一組那他就覺得他撐不住他就問說那我可不可以去救命其他組這樣子

[1:43:26] 那如果你找得到的話是可以的當然了前提是另外那一組還沒有滿四個人反正不管怎麼樣變來變去動來動去就是最多四個人一組好OK還沒有其他問題我的話我們休息一下再回來這對這個作業有一點問題因為就是我感覺上整個作業它就是有一點像一個小小的論文這樣子就找一個問題然後你想一個解決方法然後那個空空就是因為可能一來就是有很多

[1:44:58] 就是通常我們想過的別人也想過了那我就好奇就是這個解決方法提出來過後有一定要比別人表現好嗎還是東西做出來就好了在第一個作業不用第一個作業只是push你們要去找資料然後把它寫出來我確定make sure你們有在找資料有想過就是開始看文獻這樣子但最後是不是嘗試提就是一個try嘗試提自己的解法或者什麼想法但它不一定是要一個最終的成品這樣子對okok那因為這個project是一個我會把它理解的就是你是為了後面的東西鋪路所以你可以問就是到最後的那個hw5的這個結果是不是就是expect最好就是自己的解法and then you review別人的解法還是有一個新的解法如果有比別人好當然是更好但是我知道大部分同學是做不到okok好所以就是就是盡可能就是盡可能做到好好好好好好好就是有自己的想法這才是那個重點對okokok

[1:49:56] 好我做的題目就是想要跟路文有關然後想要改成就是根據因為我路文是要做一個實驗設計要發文卷的然後我想說如果我把LLM當作我做實驗設計的前側然後它可以符合就是傳統理論上的那些那些model fit然後但是因為前沿用LLM做這個啊我目前查的都比較多是working paper就沒有很棒的期刊瞭解很多知識那如果只是用來這樣子做測試的看看然後做這個作業的話做這個作業那就是看你後面你只是當前側吧對然後我想說看後面如果因為我如果真的要花錢去做這件事情就是實驗那種跟經典外的我怕收回來的數據會到時候收回來的數據不漂亮如果這樣子聽起來就比較像是你只是在用LLM做事情而已對那除非覺得它假裝人你有帶入一些agent的設計你有帶入比如說你可以去看一下以現在LLM來當agent來講的話比如說你要求他要反思要能夠檢驗人家回答的然後再進一步的提出策略

[1:51:26] 然後再做動作如果你有這樣子的設計的話就不會淪為好像只是在用一個工具這樣會比較符合我們這門課希望你們真的有不要只是用一個尤其現在的工具對啊你自己要去設計一些agent的loop就是agent的反思的一些策略讓他去做不要只是用工具對要設計一下不然就變成只用工具就沒什麼啦就是除了他的possum就是那個人設以外再去限制設計他loop的那個條件再延期一點是這個意思嗎對你讓他要好像比較有智慧一點啦不是只是叫他做一個資料的統整好對好再去研究一下好第二個部分

[1:56:41] 第二個部分呢就是所謂的informed search或者是heuristic search那他的定義就是說除了原本問題的該給的資訊之外他還額外多知道了一些離目標有多遠的資訊那一般來講你多知道了一些資訊你就能夠更有效率的解決這個問題那這個額外多知道的資訊呢我們稱呼它叫做heuristic function寫成h of n那比如說這個h of n呢可以是我從某一個某一個都市某一個狀態到我的目的地的這個狀態的最小的pass cost可以定義成是這個heuristic function好所以舉個例子啊剛剛的這個羅馬尼亞的這個地圖啊我除了知道這個地圖我除了知道說我從A走到Z的里程是多少A走到S的里程是多少之外假設我還知道每一個都市到Bucharest的直線距離假設我知道那這個就成為我的heuristic所以這個heuristic呢其實就是任何的某一個都市

[1:58:11] 到B這個都市的最小的pass cost因為直線距離是直線距離它不見得真的有一條路啊它只是在地圖上的直線距離而已啊所以舉例啊A到B的直線距離是360C到B的直線距離160D到B的直線距離242這樣好這是等於說從空中往下拍空照圖然後畫一條直線這個兩個都市之間的直線距離這樣假設我知道這個好那如果是這樣子的話呢欸我就可以開發出另外一種info search的辦法這個叫做greedy best firstfirst search好貪婪的貪婪的優先搜尋演算法好比如說我今天從A要出發嘛那我知道說呢欸我的分支就是S T跟Z好那我要往哪裡走比較好勒欸我有這個啊S距離目標的直線距離253對不對T329Z374R哪一個離目標最近直線距離最近S最近所以我就決定我走到S好依次類推我從S往下走我可以走到A我可以走到F可以走到O可以走到R

[1:59:41] 好那哪一個直線距離離Bucharest的最近呢F最近欸那我就走F好那再繼續從FF再走到B結束我找到解了我從A走到SS走到F再走到B這樣這個就所謂的Greedy First Search演算法好很棒吧好我就看說我的分支裡面哪一個離Bucharest的最近這樣好這個是在有這個Huristic的情況之下但是但是以這個例子來講不幸的事情是從A走到S再走到F跟走到B它雖然是一種走法但這個走法不是最佳解好所以它是在告訴你說欸即使你有空照圖即使你有最短的直線距離的額外資訊你利用這樣子來找雖然很開心很快就找到解了但是它的解可能不是最佳解好實際上呢你如果先走到R再走到P再走到B的話呢你的整體的里程數是會最低的所以剛剛這樣子講你真正走這條路從A走到S走到F再走到B你真正所需花的Cost你還是要回歸到你地圖上面你A走到S的里程數S走到F的里程數

[2:01:11] 跟F走到B的里程數你怎麼加起來其實是比你走到R再走到P再走到B會多32公里好所以什麼意思就是如果有解的話他一定會找到解但是呢他不是optimal他不見得保證找到最佳解好那一般來講啊雖然雖不中亦不遠矣嘛對不對他雖然找到的不是最佳解但是找的解也挺不錯的啦對不對才差32公里嘛那一般來講如果你的heuristic越好你你的這個complexity呢就可以大幅的下降你看嘛你有了這個heuristic你是不是就不用在那邊BFS DFS在那邊弄半天對不對你這樣子很快就找到解啦你的complexity可以大幅的降低好那可是剛剛這個畢竟不是最佳解嘛好所以說呢在info search或者heuristic search這邊呢也有很著名的演算法叫做A star search好A star search它是最著名的best first search它的概念是欸我呢就整合剛剛的past cost GN

[2:02:41] 跟還有剛剛的heuristic HN我把它合在一起來一起當作我判斷哪一條路應該優先走的依據所以GN代表的是past costHN代表的是heuristic就是the estimated cost of the cheapest path所以決定走哪一條路我是靠GN加FN的結果的這個FN來幫忙決定我要走哪一條路那我們直接先看一個例子好了直接看例子比如說我今天要從A出發A呢它可以走到S T跟Z那我現在的評估我要走哪一條路呢我從A走到S我其實要花140我的里程數是140然後呢S它距離Bucharest的直線長度是253我把這兩個加起來也就是說我考慮的點是我如果走到S呢我需要花的cost以及我從S出發走到目的地要花的預估的cost加起來是393好 一直被推我如果走到T呢4447我如果走到Z呢449哪一個最少S最少

[2:04:11] 好 那我就走去S你從S可以再繼續往下走好 你所需花的cost是多少呢比如說你S走到F的話你從S走到F你本來就要花239那你從F到Bucharest的直線距離是176所以呢你如果走F的話呢這裡要預估要花415那走到O的話671走到R的話413所以在這個時候呢我就決定走R這條路那一直被推R這個再繼續往下走我就挑P這條路P再繼續往下走然後你就可以發現就走到Bucharest所以呢它這樣子找出來的路徑呢在這裡走到PP再往下走走到這裡所以它找出來的最佳路徑就是A走到S走到R走到P再走到B那它之所以比剛剛的這個Greedy Best First Search優越的地方就在於說就是考慮了我過去的歷史我的Past Cost以及我預估未來我要走的Cost有多少兩個一起合併考量那這樣子就可以找到最好的那條路徑

[2:05:44] Cost最低的那條路徑這就是A Star Search你會有點懷疑說欸真的嗎這樣子保證一定可以找到最佳解嗎事實上這是可以證明的當然我們不會講仔細的證明啦理論上我們可以證明這樣子的A Star Search呢是Optimal它可以找到Complete and Optimal只要只要什麼呢只要你的Heuristic Function符合兩個特性一個叫做Admissibility一個叫做Consistency你的Heuristic如果你可以證明你的Heuristic Function符合Admissible跟Consistent你就一定能夠說A Star Search是OptimalOK詳細的證明我們不是不講因為那個很長那但是呢我們講一下什麼叫AdmissibleAdmissible是說如果這個Heuristic是Admissible就代表它呢Never overestimate the cost to reach the goal你這個Heuristic呢永遠不會過度估計了某一個State走到目標那個State所需花的Cost

[2:07:17] 這樣所以我們剛剛講的這個羅馬尼亞地圖這一個你從Z這個都市到B這個都市的最有可能的最短路徑就像照圖直接畫一條線的直線距離它一定會比你走實際的道路的Cost來的低對不對因為實際是實體世界上沒有一條路剛好是直通從Z直通到B的嘛那我利用Z直通到B這個都市的直線距離來當成是我的Heuristic的事所以它Never overestimate永遠不會過度估計所以呢這樣子的Heuristic我們就說它符合它的Misable這個特性另外一個它同時也要符合Consistency的特性Consistency的特性是什麼呢就是說我們如何可以說一個Heuristic是Consistent呢那就是For every node nand every successor n'of n就是n的往下分支Generated by any action不管是做哪一個動作反正就是所謂的分支的意思吧The estimated cost of reaching the goal from nis no longer than the step cost

[2:08:47] from n to n'plus the estimated costreaching the goal from n'好像在繞口令其實很簡單就是說就是說我從n裡的這個Heuristic我預估的這個Cost一定會小於等於我從n走到n'我說花的花費再加上我從n'的這個Estimation Cost還是很奇怪但事實上這件事情就是三角不等式這個就是三角不等式對不對我們畫一下這個畫很怪異嗎這很簡單啊N在這裡然後呢它的分支N'在這裡這個很難用因為我用滑鼠目的地是G在這裡對不對HN是什麼意思HN就是這個的直線距離這叫HNHN一定小於等於什麼這個是什麼這個就是從n走到N'這個是什麼這個就是從N'走到G所以說你看它是不是在講這一條距離一定小於等於這個加上這個

[2:10:17] 這不就是三角不等式嗎數學裡面的三角不等式嗎所以只要你的Heuristic Function符合三角不等式也符合Admissible過去的學者就已經證明瞭這個Amstrong Search的演算法是Active那詳細的證明我們就不講了我們只講它的特性是怎樣好那這個就是Informed Search的部分我們第三章講完了都不針對課程內容問題大家都在注意那些沒有問題我們要繼續往下走再來好

[2:11:49] 剛剛在第三章呢我們知道有一些問題我們可以把它描寫在一顆Tree上面對不對那我們就可以在Tree上面運作來找到我們的解答好那接下來到了第四章呢我們要來講一個更複雜一點的就是如果我今天我的問題無法表達在Tree上面的話怎麼辦所以他說呢這個講到這邊為止呢前面都是說我可以這個表達在Tree上面啊那我在Tree上面走來走去走走走我去做不同的Action走我就找到我的目的地我就找到我的答案了好那但是在很多的問題裡面啊呃我抵達目的地或者是抵達我達到我要的目標這件事情呢跟你怎麼走可能是沒有什麼關係的跟你執行的Action的誰先誰後是沒什麼關係的好比如說在八皇后問題裡面我們並沒有規定說你一定是要把第一隻皇后放在第一個Color第二隻皇后放在第二個Color沒有啊我高興的話我第一隻皇后我直接放在某一個位置第七個Color第二隻皇后我放在第三個Color

[2:13:20] 那反正我最後我擺起來的樣子沒有互相攻擊就好了所以他跟你擺的順序基本上沒有關係沒什麼關係沒什麼關係所以說在這種問題裡面呢他就不太適合用表達成Tree的一個形式在八皇后問題裡面呢What matters is the final configuration我在乎的是他最後有沒有互相攻擊跟你怎麼擺那個皇后的順序無關所以呢我們需要另外一種種類的演算法呢Not worry about the past at all一點都不關心誰先誰後好那其中呢我們來講最重要的一種做法就叫做Local Search它一樣是一種Search我們這裡講的Search呢是指說在好多不同可能的解答裡面找到我們要的解的這種Search所以大家不要看到Search就覺得說在做Google裡面的文件搜尋我們這裡講的Search是一個更廣泛的概念就是假設在一個空間當中一個虛擬的Solution Space當中我們要去找到我們的最佳解的那種感覺那個大家理工科的應該都上過線性代數吧

[2:14:52] 對不對線性代數就是在做這件事你回想一下你想一下回想一下線性代數是吧我現在給你好多線性方程式你要找到Solution你是不是要找到解你要去求AX等於B你要找到那個X嘛對不對好那你一定也修過就是說當你不見得每一個這個AX等於B都會有解啊對不對當A這個矩陣有反矩陣的時候才有解嘛對不對那它如果無解的話怎麼辦你就只能夠找最小平方解This Square Solution那其實它的意思就是說在眾多可能的解裡面找到一個解是最佳的那一個能夠符合這種狀態的最佳的解嘛所以這個也就是線性代數裡面就已經有這種觀唸了嘛現在Again這裡又來這種觀念也是一樣我們就是要在眾多可能的解裡面找到最好的那種解的意思好那OK那Local Search的演算法呢它的基本原則就是說我現在從某一個地方出發我就去看我周圍的鄰居現在重新定義是這裡雖然寫Node我現在從這個Node出發現在啊所謂的一個Node的意思就是

[2:16:24] 某一個可能的解的意思但是我這個解呢我這個Solution可能不是那麼好我要從我的鄰居裡面找到一個表現得比我更好的那個Solution然後我走過去Update一下我就變成新的用那個鄰居來當成是一個更好的一個解然後那從那個鄰居以它為中心又去找我鄰居的鄰居看看裡面有沒有人又表現得更好我再去Update成更好的一個解這個整個大的原則就叫做Local Search那Local Search的最內的演算法呢它用的Memory很少為什麼因為它一次只需要看少部分的鄰居們這樣子那一般來講呢They can often find reasonable solution一般來講它也能夠找到合理還不錯的解即使你的Solution Space非常大你的解空間你可能可以走的這個範圍可能很大一般來講只要你找得夠久可以找到還不錯的解我之所以講還不錯就代表它不見得是最好Local Search Algorithms are usefulfor solving pure optimization problems其中呢它就是它基本上每一個解

[2:17:55] 我都可以去評判說你這個解你這個Solution是一個多棒的Solution它有一個Objective Function有一個目標函數來去評判你這個Solution有多棒概念上來講我們可以用這張圖來表達Local Search這個問題這張圖的Excel代表的是State Space就是你這個問題的某種狀態你在不同的狀態之下你的Objective Function你的目標函數的值是怎麼樣也就是說你今天做了某一個動作讓你目前的狀態變成某一種狀態了那這個狀態到底有多棒的意思有多棒的意思那假設我們是要讓這個Objective Function的值越高越好越大越好的話那我們可以去試各種不同的狀態嗎你也可以想像剛剛我們那個九宮格的問題九宮格的問題你那八塊積木八塊木塊可以隨便亂擺嗎對不對有一種擺法可能離我真正最後的要排好1 2 3 4 5 6 7 8離得很遠那它的分數它的Objective Function Value就低嘛如果只差那個感覺1 2 3 4 5 6或者說1 2 3 4 5 6 7

[2:19:25] 都已經擺好只剩下8的位置跟7的位置還沒有擺得很好那它其實就離我的目標很近我就給它比較高分嘛所以概念上那我們要解一個這個問題這個問題的時候它就如同是X軸是我各式各樣不同的StateY軸是我某一種狀態之下有多高的分數那它可能是一個很複雜崎嶇的一個曲線的變動那我們的目標是什麼我們的目標是能夠讓分數最高分的那種狀態所以它的最高分在這裡它對應的狀態就是拉下來就是這個狀態這個狀態OK好那一開始首先要怎麼擺它可能在這裡那我們就評估一下那它的分數大概就只有這麼多那我要如何讓我盡可能貼近我的目標呢那我就去如果你在玩這個遊戲的話你是會稍微移移看對不對你會盡可能的移動你的那個空白讓它盡可能去接近你想要達到那個目標的擺設嘛對不對好你可以往右移一格看看往上移一格看看往左移一格看看

[2:20:55] 往下移一格看看嘛對不對這個你往上移一格所造成的狀態就叫做你的鄰居你的鄰居這樣可以嗎你往上移一格造成一個結果那就是你的一號鄰居往右移一格造成的結果就是你二號鄰居那你可能有N個鄰居對不對那你再看看說那你這些鄰居裡面哪一個是最接近你的目標狀態的你就決定就這麼移這樣子那你聽懂嗎好那現在在這裡一樣喔我現在初始狀態可能在這邊我就找到一個最好的鄰居我就移過去然後一時之內我再移一下我可能就找到這個再移一下就找到這個好所以在某種情況下你可能就會發現某種狀態呢接下來我再怎麼移動我再也不會更好的好那你可能就說喔好我的最佳解大概就是這樣子的我目前移到這裡好那這種情況呢就是你達到了一定程度的解拔這就是所謂的local maxima那你一看這個圖你就知道說可是你這個顯然不是最好的解答嘛因為我一看我就知道最好的解答在這裡嘛對不對好但問題是喔

[2:22:25] 在你真正解一個問題的在解一個問題的時候呢你永遠不知道說你可能永遠都不知道哪邊有一個最好的解法那個解法在哪裡你永遠都不知道你只能夠說就目前我能夠看到的範圍內我能夠找到的最佳解法就是在這裡好有可能是這樣所以你在找尋的過程當中你可能會卡在這個local maxima那你也有可能會假設你今天一開始的初始條件在這裡好那你可能走走走走到這裡來囉你就發現我的鄰居們都跟我一樣好那就happy對不對我們不錯了你也有可能會卡在這邊這個叫做你走到一個高原高原的地方flatthe local maxima好或者你走到一個山腰剛好這個山腰不知道為什麼剛好有一個平臺你本來從這裡出發走走走走到這裡來你覺得你已經走到最好的殊不知其實你如果再繼續往下走你有可能會找到這裡但你不知道那你在走之前根本就不知道所以基本上這個search的演算法search的這個問題呢就是說你其實永遠也不曉得你的最佳解會是在什麼地方你只能夠邊走邊看

[2:23:55] 好那所以說呢這個local search的演算法我們介紹好幾個都屬於這一類的其中第一個就叫做heel climbing search爬山演算法那概念我剛剛其實已經講完了就是說呢我今天隨便把你丟到一個奇虛不平的一個地方你的目標就是爬到最高那裡好那這裡的策略就是什麼我隨機的把你丟到某個地一個位置好那你就去看一下我的鄰居們我就看一下方圓100公尺內哪一個地方是最高的因為方圓100公尺就是我的鄰居嘛哪個地方我就把我的鄰居全部都check過一次發現呢我往右邊走20公尺的那個地方是海拔高度最高的好然後就走過去然後我再以那個鄰居為中心再去看他方圓100公尺內的範圍的鄰居們有沒有比他再更好的如果有我就走過去就這樣就這麼簡單所以你看這個演算法很簡單啊我現在呢我是current我在這裡那我去找到我的鄰居們當然鄰居的定義有各式各樣就看你的應用核定好如果鄰居的所有鄰居的objective function value

[2:25:27] 都比我現在來的低那代表我現在已經在最高處啦那我就回答我現在的答案如果沒有有鄰居的value比我高那我就用鄰居來取代叫我好而且這裡講的鄰居是周邊鄰居裡面最高的那個鄰居他的objective function value最高的那個鄰居所以我永遠都會走到我最強的那個鄰居那裡就對了啦好如果我已經是最強的我就是答案如果我不是如果旁邊有鄰居比我更強我就用那個鄰居來取代叫我這個就叫希爾談OK來舉個例子啦剛剛講八皇后問題八皇后問題呢假設今天我隨機的放這八隻八隻皇后長這樣我放完之後長這樣好那我現在我要想辦法調整這個盤面使得我越接近我的目標越好我的目標當然就是八隻皇后我的衝突的數量要越少越好好那我現在來定義一下怎麼樣叫做鄰居呢就是說我允許你動一隻皇后然後呢這隻皇后只能夠在同一個column裡面移動好我定義我的所謂的鄰居是這樣好那我每動一個位置

[2:26:58] 我就要我都可以去評估說我動了她之後呢我皇后之間我衝突的數量是多少個所以比如說假設我動這個皇后第二個column的皇后我如果是把她移到這一格我還是會有十四個衝突十四組皇后的衝突我如果移到這一格也是十四組我如果移到這一格呢會只剩下十二組皇后的衝突以此類推所以說呢在這個盤面之下呢我就決定我要把這個皇后移到這裡來相當於我就走到一個我的鄰居那邊去好到了下一個步驟我再從那個鄰居再去看說我要移哪一個能夠讓我的衝突的數量越低越好那經過很多次很多次呢他可能就只像這個樣子OK那這個就是一個heel climbing好那heel climbing的演算法呢有時候又稱為是greedy local search就是隻看周邊的鄰居做出最貪婪的決定因為他永遠只取最強的那個鄰居來取代掉那是這麼簡單的一個想法呢it turns out that the greedy algorithmoften performs quite well事實上表現得還不錯喔他當然你可想而知

[2:28:30] 他絕對不保證永遠可以找到最佳解但一般來講可以找到還不錯的解那他也我之所以講還不錯就是因為他不是最佳解嘛他可能走走走走到一定的程度就卡住了所謂的卡住是因為他已經覺得他很厲害了他夠好了周邊的鄰居沒有在比他更好所以他可能是卡在一個local maximum也可能卡在一個無極rich就是說剛好這個無極這條線上所有旁邊的鄰居都是更弱的那我往某個方向走其實所有的鄰居都跟我一樣好對不對某個方向上的鄰居都跟我一樣好除了這個方向之外的其他鄰居都比我們來的爛那我也會覺得說我已經夠好了這是無極或者說我走到一個平原高原那你也可能會卡住那這裡有一些過去的實驗數據比如說八華貨問題裡面呢假設我永遠都取最好的那個鄰居走過去他基本上有86%的時間呢會卡在local minimum然後呢14%會找到解答那通常是這樣

[2:30:02] 它的好處是說It works quicklyTaking just 4 steps on averagewhen it succeedsand 3 when it gets done他的意思是說如果他在八華貨問題裡面如果真的有找到最佳解的話真的有找到不死即使八隻皇后不互相衝突如果有找到的話平均四步移動四次就找到了如果他找得到的話那我們說他其實大概只有14%找到大部分86%是找不到的那不過好在是這樣他就算沒找到互相衝突的case他卡住了他也很快就卡住他三步就卡住了OK那他說呢即使整體而言這不錯喔因為整體而言呢他要考慮的所有擺設的情況有8的84%17個million在這17個million可能的狀況裡面你就算卡住了也是很快就卡住了這是很不錯的至少讓你很快知道你失敗了OK那你可能會想那我可不可以稍微改良一下比如說我讓他如果允許讓他即使你走到一個高遠的地方照理講高遠的地方就是說你的鄰居們都跟你一樣好了嘛對不對你如果允許讓他用

[2:31:33] 跟你一樣的鄰居你也走過去試試看你讓他有這個彈性那效果會變好呢答案是會因為這個你有更多探索的機會嘛說不定你雖然你左邊連續5個鄰居都跟你一樣好你搞不好到了第6個左邊的第5個再往外看說不定就會找到一個更好的一個高峰可以爬上去所以在這樣的一個小巧的變形之下呢成功找到錢的機率就從14%飛到94%喔不過呢因為你允許他用一個跟你一樣好的鄰居所以呢你要找到最佳企業的這個步驟啊就遠遠變成21步那你如果要卡住也要64步之後才會卡住所以這個就是一個妥協啦那還有其他變形呢比如說Stochastic Hill Climbing他說我們剛剛前面都講說我永遠都找最好的那個鄰居嘛那我可不可以不要永遠找最好的鄰居今天我有一百個鄰居其中有十個表現比我好我從這十個裡面我隨機挑一個我不要永遠都挑最好的那一個這叫Stochastic Hill Climbing誰知道啊

[2:33:03] 說不定這個我先挑一個不是那麼好的鄰居從他去往外走搞不好有更好的一個結果啊這就好像說大家畢業的時候一開始第一份工作你一定要挑給你吸嘴最高的那個工作嘛你是Greedy First Search是不是但很難保證你未來的生涯你走這條路是最好的對不對再來First Choice Hill Climbing意思就是說你在搜尋鄰居的過程當中你碰到的第一個表現比你好的鄰居你就選他了這樣子所以這有點像是你以後出去轉工作你投了時間努力對不對第一個說要搜你的那家公司你就去了這是First Choice Hill Climbing不見得一定是不好也不見得一定好就是了啦不好說那也可以是Render Result那比如說因為不管怎麼樣不管是哪一種Hill Climbing都有可能會卡住你隨機從這個地方出發搜尋有可能卡住了那所以怎麼辦我可不可以隨機很多次出發對不對我這次從這裡出發卡在某一個Local Maxima我下一次從另外一個地方出發我可能卡在另外一個Local Maxima對不對

[2:34:33] 我做了好幾次那這些Local Maxima裡面我就取相對最厲害的那一個那這就是Render Result Hill ClimbingOK那到底Hill Climbing會不會成功呢會不會整整找到解呢Depends very much on the shape of the stateState and the state space landscape那就要看說你這個整個Objective Function隨著你不同的State你這個高高低低的複雜的情況是怎樣不見得一定不好也不見得一定好我們只是說它是一種解決它是一種Local Search的方式它是一種解法OK好那今天時間差不多了我們就今天先講到Hill Climbing就好了那看看最後有沒有什麼問題是的我之後會把它放上去沒有問題大家對課程內容全盤理解一點問題都沒有我們今天就上到這裡