[0:00:42] 今天是9月24號,可以掃一下這個slide,等一下如果直接連到slide稍微留個幾秒鐘時間。

[0:09:57] 實際上課注意事項,首先主要是這個,我們下禮拜呢,10月1號的課會是,因為我要出國開會,所以10月1號的課呢,我們會事先錄影的方式來呈現。所以呢,我們會把連結放在NTU COOL的這個頁面上面。那請大家自己去看影片。那順帶一提,過去幾次上課,我們這已經是我們的第一、二、三、第三次上課了,再講一次。如果你還沒有收到NTU COOL系統的邀請的同學,原因可能是因為時間差。因為你加退選之後,你可能後來才加學了,那你們學校需要時間,會證名單送到NTU COOL的團隊。那這件事情不會馬上發生,可能時間差,這是一個可能的原因。另外一個就是說,你不是去收你學校的名單。你學校的官方的帳號。所以我的確,我在NTU COOL的系統上面,我有看到好像還有300多位同學沒有接受邀請。

[0:11:33] 所以,這個是你們要注意的事情。然後,所以下禮拜的課會是非同步式的上課,就是看影片上課。大家在下週四,10月1號晚上11點59分之下,要交你們的第一個作業。那我們在系統上面有陸陸續續有看到,有的同學,有的主別已經交上去了。那請特別注意這個繳交的時間。因為時間一到,系統就會自動關起來。那我們下週四,會在線上也會同時公告你的第二個作業。OK。好。所以請大家注意。好。那另外有一個新的事情,是本週第一次宣佈。就是說呢,我們說我們現在上這個課呢,其實是線上線下同步上課。所以現在在現場呢,有成大的同學。然後呢,在線上有其他學校的同學,線上上課。那因為是線上線下同時上課,而且我們直播之後,其實都會YouTube上面就會有影片。好。所以很多同學呢,就會選擇不會來實體教室上課。好。他可能就是自己在宿舍看直播啦。或者說他根本也沒在看,他是事後才看影片。

[0:13:05] 甚至他根本也沒有在最近就看影片。他搞不好是到學期末、快要考試的時候,才在那邊看影片。好。那當然這個後果你們要自己承擔啦。好。那但是對於我,在實際課堂上課,實際課堂上課的老師來講,我今天提供這樣的服務,尤其是成大的同學,我們號稱有130個人休課。一堆人說,老師拜託啊,可不可以有加簽啊,什麼怎麼樣啊。然後呢,然後你又沒有來上課。你在那邊加簽什麼東西。好。那的確啦,你說沒有啊老師,你這個本來就可以,你看影片就好了嘛。誒,說的好像也對啦。但是對於我在實際課堂上課的老師來講,如果課堂上幾乎都沒什麼人的話,那,我就覺得好像我在對空氣講話,很奇怪嘛。那事實上呢,這個也是整個開咖課程,所有各校開開咖課程的老師,都一致有在反應的事情。就是說,因為我們必須得要線上線上,同步上課嘛。所以上到後來呢,自己本身那個學校的同學呢,都不來課堂上課了。那老師上課的時候,就一個人在那邊對著空氣講話。那反應給TICA的推動小組之後呢,誒,他們也覺得說,誒,對,這樣子對老師的心靈受到一些傷害。

[0:14:41] 所以為了讓老師心裡好過一點,其實TICA也提供一些資源,希望能夠,鼓勵大家,實際到課堂上來上課。因此呢,其實,我們最近有接收到TICA的這個,總部的這個通知,他提供給我們一些資源,來讓我們應用,鼓勵大家實際來上課。那怎麼做呢?事實上呢,根據去年的做法,我們研習去年的做法是這樣,包含今天,今天9月24號,如果包含今天,一直到學期末為止,會有我站在這邊實際上課,實體上課的次數,應該還有10次,今天9月24號,1,下禮拜不算,1,2,3,4,5,6,7,8,9,10,還會有10次,是我會站在這裡實際上課。那我們拿到一些算力,OK,事實上TICA,總部給我們一些算力,所以呢,為了鼓勵大家實際來課堂上上課,我們有來上課的呢,我們等一下會發號碼牌,每個人會有一個編號,然後我們最後,我們就會抽算力給大家。那你說,那線上上課的同學呢,因為我們當年也鼓勵大家同時在線上,要真正的有在聽嘛,對不對?

[0:16:13] 所以,我們其實也會給線上的同學,抽算力。那我們目前規劃的是這樣,我們每一次上課,每一次實體的上課,在場的成大的同學,我們會抽出6位,OK?那線上上課的同學,我們會請大家,你有在線上上課的同學,你要上去填一個線上的表單,OK?那我們會從有填線上表單,而且符合某一些資格的同學呢,我們會抽出5位。所以這樣Totally,就會有11位同學,會抽到,可以拿到算力。好,那我們其實每一次上課,有6000塊的額度。好,那我們的想法是,這11位同學,其實都會拿到算力,但是呢,我們只有,再從這11位裡面,又隨機抽出1位,會拿到最大獎。2000塊。好,2000塊的算力。然後呢,剩下的10位一個人,400塊的算力。因為我們一定要把大獎跟普獎,那個集聚要拉開嘛。好,鼓勵大家,專心聽課,以及來線上上課。好,所以等於,現在在,在場的同學,今天在場的同學不多太好了,你們得到算力的機率是很高的。好,在場的同學,等一下,呃,其實我覺得你現在可以放下去,

[0:17:45] 就反正到時候,我們等一下會隨機,調出6位出來。好,線上的同學,來。線上的同學是這樣子的。線上的同學呢,你可以掃一下,目前畫面上的這個QR code。抽算力QR code。那你,你如果點進去,可以看得到畫面嗎?什麼東西?還在上一個QR code。來,又來了,又來了。又跟上次一樣。對不起啊。又要哪裡要換,是不是?欸,還在slide喔。呃,我們上次也出現這種情況。上次怎麼解決啦?上次有一個同學,救了我。好像是這個,是不是?然後,我都是整個螢幕輸出啊。有有有,確定。確定。這樣子。好,那,我再重新切換過啦。來,這樣。這樣。線上的同學有沒有看到?好,看一下。可能要有一個時間差了。有了嗎?有換成抽算力這一個QR code嗎?慢。有了齁?好。

[0:19:15] 線上的同學呢,你可以掃這個QR code。那你就會連到一個Google表單。好,那上面就會要求。喂。喂。好,上面就會要求你要輸入你的,什麼學號啦,姓名啊,學校啊,還有你的E-mail。不過,我印象中就是,我們會要求大家要輸入的E-mail是Gmail的帳號。你的個人Gmail帳號。因為臺華那邊提供的算力的廠商,必須得要透過你的Gmail來給你算力。好,那填的,就代表你有在聽課嗎?不是。我們要要求大家,要填兩個通關密語。你必須回答對那個通關密語,你才能夠有具備資格,收算力。好,你看我們上這個課很麻煩耶,搞得很麻煩,還要設計這些橋段。好,通關密語呢,就是,我什麼時候會說出通關密語呢?就是,不知道。看我高興。隨機的。好,我突然就說出一個。好,這通關,第一個通關密語是什麼?好,然後就開始繼續上課。上課,上課完之後呢,可能又在某一個random的某一個時間,又random的說出一個通關密語。好,那當然在場的助教,會幫我記下,我今天隨便隨口說出的通關密語。然後呢,在下午4點,我們下課。

[0:20:46] 好,我們這整個線上表單,就會截止。所以說呢,助教回去之後呢,就會從有符合資格的線上的同學裡面,會抽出5位。然後在場的,剛剛拿了號碼牌的同學,會抽出6位,可以獲得的算力。所以總共11位。那這11位裡面,只有一位會拿到最大獎,2000塊,其他都400塊。好,就是這樣。所以我們實在是用心良苦啦。為了,為了要鼓勵大家上課,我們還要用這樣,實在是。好,那所以,線上的同學,當然你就仔細聽,我們,我也不知道,我什麼時候會說出通關密語。好,那這樣子,有沒有什麼問題?好,我們大概交代了一下,我們下一次,下禮拜上課是線上,是那個錄影上課。然後,我們下週要交第一個作業。好。然後,我們會馬上公佈第二個作業。OK。來,我確認一下線上看到的畫面,有沒有對的。我這滑鼠。

[0:22:17] 這樣子。可以。好,那我們就開始上課囉。好,有沒有問題?先停一下。那個後來才看影片的同學,當你聽到,你看到那個線上的表單,跟聽到通關密語之後,你當然會知道通關密語啦,如果你真的有在看影片的話。但是後來,反正我們線上的表單就已經截止了,你填了也沒有用了。好,我們有點煩。上個課還要弄那麼煩。好,我們先公佈第一個通關密語,順便亂講。9527,你幫我記一下。好,那什麼時候會說出第二個通關密語,我也會知道。好,來。那我們繼續來上第四章。好,第四章。好,第四章呢,我們要解的就是一個,我們現在在做一個最佳化的動作。那就是說呢,我們在整個solution space裡面,整個解空間裡面,我們希望能夠找到一個最佳解。什麼叫最佳解呢?那就是,你讓你的這個目標函數的值,能夠越大的那樣子的解,就是所謂的最佳解。你可能帶入各種不同的solution,

[0:23:47] 你對應的目標函數,可能高高低低,有這樣子的一個變動。那你怎麼去,照理講以這個例子來講,我們的最佳解就出現在,大概在這個地方,因為這個地方你推上去,你對上去,這裡就是你的最佳的目標函數的值。所以你的最佳解,就是在excel的這個地方。好,那大家不要誤會喔,最佳解呢,我們現在雖然是用這張圖來表示,我們的solution好像是一個數值,一個值,但實際上,我們的這個state space,可以是在一個非常高維的空間。所以你可以帶入一組向量,就是我的一組值,那它是在高維的空間當中,會對應到一個objective function value,一個目標函數的值。所以其實在一個這麼複雜的,高維的空間當中,找到哪一組向量,是對應到最大的函數的值,是很困難的。好,那所以呢,我們在接下來呢,就介紹了一些演算法。好,那我們很快的複習一下,我們上週最後介紹的這個演算法,叫做Hear Climbing,它是一個最典型,簡單的local search的演算法。那為什麼叫local search呢?因為它就是local嘛,只看局部,區域內的相關的解。

[0:25:20] 它的概念也很簡單,我不知道我的解在,最佳解在哪裡,我就隨機的,先從某一個solution出發,某一個,某一個地點出發,好,或者說,這個stay space的某一組解出發,這樣子,好。從它出發之後呢,我去看看它周圍的鄰居,有沒有人的objective function value,比我現在的objective function value,來得更高,來得更好。好,因為每一個solution,都對應到一個objective function value,都對待一個目標分數的值。好,所以我去看一下我的鄰居們,有沒有人表現得比我好。好,那所以以我為中心,方圓,比如說,5公尺以內的這些鄰居們的這些解,如果有比我好的,好,可能有10個都比我來得好,那我就從這10個裡面,挑最棒的那個鄰居,用它來取代掉我。所以呢,我經過這一次update之後呢,我就得到了一個相對比較好的一個解,對不對。好,那再從剛剛最好的那個鄰居,現在變成我自己走到那個位置了,以它為中心,再去看方圓5公尺之內,好,所謂的方圓5公尺,只是一個比喻,其實你不同的問題,你的鄰居的利益會不一樣。OK,好,那你去看一下你的鄰居,再看看說,

[0:26:50] 唉,有沒有比他更好的,唉,有比他更好的,就挑最好的那一個,用它來取代掉我原本的位置。就這樣,一直往下做下去,看你願意做幾步,比如說你可以做1萬步,10萬步,或者是說,你可以設定一些終止的條件,比如說,唉,後來呢,我用鄰居來update掉我之後呢,我的objective function value,變動,微乎其微,那我就知道說,差不多,我已經找不到其他的,這個,更好的企業了,你就可以停了。這樣子的做法呢,就叫做Heel Climbing,好,爬山啦,那你可以想,比如說,我假設我隨機,我從這個點出發,我從這一組企業出發,它的objective function value呢,是在這裡嘛,好,那我去看一下它的鄰居,以目前來講,它的鄰居,其實就是以這個領域作為中心,左右附近的人嘛,唉,我就發現說,唉,這個鄰居,這個鄰居表現最好啊,所以我就用它來取代掉我,好,這樣,然後以此類推,我再以它為核心,我去左右看,又發現右邊一點,又有一個更棒的鄰居,以此類推,一直走到,比如說這個點為止,好,也就是說,我以它為中心,往左右看,發現沒有任何鄰居,比我表現得更好了,那我就回傳這一組答案,好,那這個做法,很顯然的,你可以發現,

[0:28:20] 可能有一個問題啦,就是它可能會卡在local maximum,對不對,因為你到了這個小山丘這裡了,你這個周圍繞一圈一看,發現沒有任何鄰居比你更強的,那你就覺得你自己是最強的,好,那你就卡在local maximum,但事實上以我們,我們現在如果從上帝的視角,遠遠的來看,其實我們知道真正的最佳解在這裡啦,OK,好,那你說,不對啊老師,那我對不對,我一看,我就知道最佳解在這裡,我幹嘛要用什麼local search,原因就是,當你實際的解一個真正的問題的時候,你根本就沒有上帝視角,你根本就不知道,你整個objective function value的curve,這個曲線,或這個復長的曲面長什麼樣子,你根本就不知道,好,所以你就從這個local search這裡開始來做,好,那這個我們就不再贅述啦,所以它有可能會卡在local maximum,那所以呢,你可以為這個所謂的hear climbing演算法,做一點變形啊,有沒有可能我盡可能的減少它,卡在local maximum,的狀態的次數呢,所以後來就有一些變形,比如說stochastic hear climbing,它的意思就是說,我今天我看一下我周圍的鄰居,剛剛最原始的版本就是,

[0:29:50] 我用我最好的鄰居來取代掉我,OK,好,那我有沒有可能,我根本,比如說我周圍有十個鄰居,都表現得比我來得好,我是隨機的從這十個表現比我好的鄰居裡面,挑一個來取代掉我,我不是永遠都挑最好的那一個,也就是說你不要走那個貪婪的,最貪婪的路線,因為說不定你取到一個,你選擇一個表現第三好的那個鄰居,他說不定他看到的東西,他看到的視野,比起你在現階段你挑最好的那個鄰居,看到的是更好的風景,那所以你如果選擇第三好的那一個,再往外去找,說不定他會找到更好的,而且不知道也不保證,所以我這裡並沒有保證說,這個Stochastic Hill Climbing,表現的一定會比基礎的Hill Climbing來得好,不見得,要看問題而定,那也有另外一種變形,就是First Choice,就是我找到的鄰居裡面,我第一個找到比我表現來得好的那個鄰居,我就用他來取代掉我,我不用把方圓,5公尺內的那100個鄰居全部都掃完一次,我只要找到第一個表現比我好的,我就走過去了,這叫First Choice,那再來就是說,你不管是Stochastic,First Choice,或一般的,你都有可能會卡在,

[0:31:21] 都還是有可能卡在Local Max,那原因,除了演算法本身的侷限之外,還跟你一開始,你是落在這個崎嶇不平的,這整個山脈的哪個地方有關,所以有另外一個就是說,那我可不可以做很多次的Hill Climbing,每次出發的地點,隨機的不一樣,那這個叫做Random Restart的Hill Climbing,那這是我們上次講的最後的內容,那再進一步一點,現在演算法叫做Semantic Unnealing,Unnealing這個字就是退夥,Semantic Unnealing就是模擬退夥,這什麼意思呢,在一些,比如說我們看一些古裝劇,舊的,或者是電影,以前古時候的人,不是會在那邊打鐵嗎,比如說他要鑄造出一把劍,有沒有,那他就會把那個鐵燒熱之後呢,在那邊打,然後塑形,原因是什麼,原因是你燒熱之後呢,他的這個,這個,這個裡面的這個分子啊,就會比較鬆動,OK,那你有機會透過外力去塑造他的形狀,

[0:32:52] OK,然後呢,等你塑造差不多這個形狀之後呢,然後是不是又給他降溫,讓他有冷熱冷熱的這個變動,所以我們知道說,當溫度高的時候,分子之間比較容易變動,比較容易塑形,溫度低的時候,他的整個結構就固定了,好,那Simulated Aligning呢,就是有一點想要模仿,這樣子的一個程序,好,他什麼概念呢,他其實跟Heal Academy非常的像,我們看一下這個修道口,好,呃,今天一樣,我隨機從某一個Solution出發,那我去看一下週圍的鄰居,好,所以我現在的Objective Function Value的詞,叫做Current.Value,就是我現在這一組解,好,我的目標函數的詞,叫Current.Value,我的鄰居,某一個鄰居,某一個鄰居,比如說我看到的第一個鄰居,Next.Value,他的Objective Function Value的詞是這樣,我把鄰居的函數值減掉,我的函數值,叫做Delta1,OK,可以吧,好,如果Delta1大於0,什麼意思,就是鄰居表現得比我好嘛,如果鄰居表現得比我好,那我就用這個鄰居Next,來取代掉我,這樣可以嗎,對目前為止,完全跟剛剛的那個First Choice的Hear Climbing,

[0:34:24] 一模一樣,如果鄰居表現得比我好,我就用他來取代掉我,好,再來,那如果鄰居表現得比我不好呢,也就是說當Delta1等於0,或小於等於0的時候,當Delta1小於等於0的時候,我依舊有一定的機率,用鄰居來取代掉我,也就是說在Seminating and Nearing的,這個演算法裡面,我有可能用一個比較爛的解答,來取代掉,目前這個比較好的解答,它的原因就在於,說不定,我退一步海闊天空嘛,我先用一個暫時稍微爛一點的,的解答,來取代掉我,我走過去之後,說不定那邊的視野更好,這樣懂我意思嗎?這有點像是,以後大家畢業,一開始出去找工作,你是不是永遠都要,你的第一份工作是不是都一定要,去給你薪水最高的那個工作,不見得,說不定你是選擇,第二或第三高的某一個工作,說不定那個地方,雖然是一個小公司,但是未來發展的潛力可能更高,或怎麼樣,所以這裡的概念就是說,我會有一定的一個機率,去接受一個比較爛的鄰居,來取代掉我,那現在的重點就在於說,

[0:35:55] 那這個機率怎麼設定?這個機率怎麼設定?我們可以看一下,這個機率叫設定成,Exponential Delta E over T,它是一個指數,然後呢,Delta E over T,首先我們知道,會走到這一行,一定代表Delta E是什麼?是負的,對不對?所以這其實是一個,Exponential的一個負的指數次法,代表它是什麼?Exponential,它其實是,你知道Exponential,比如說Exponential負二,其實就是什麼?Exponential二次方分之一的意思吧,好,那我們來看一下,Delta E,如果負的越多,代表這個鄰居表現得比我爛,而且爛很多,那它的Delta E就會負很多,對不對?如果Delta E負很多,這整個值算出來就,怎麼樣?比較大還是比較小?就比較小,這整個值,因為是,比如說Exponential負二次方,跟Exponential負零點五次方,哪一個數字比較小?Exponential負二次方,數字比較小,這樣聽懂嗎?可以吧,Exponential可以吧,指數為理嘛,所以今天翻一層白話的意思是,

[0:37:25] 如果鄰居比我爛很多,我用它來取代掉,我的機率就很低,就這個意思,相較之下,如果Delta E,只是負一點點,比如說負0.001,這樣子,代表什麼?代表這個鄰居,雖然表現得比我差,但是其實只差一點點,好,所以呢,這裡的機率就是Exponential,負0.001,除上大T,那相較之下,這個就是一個比較大的機率,當然我們都知道,機率一定都在Delta E之間嘛,所以我們這是相對的,相較之下,如果一個,跟我比起來,沒有那麼差的鄰居,我就有比較高的機率,會用它來取代掉我,表現得比我好,那沒什麼好說的,那就是剛剛上面第一條路,我一定會用那個比較好的鄰居,來取代掉我,OK,好,那這是第一個特性,第二個特性是,你除上大T,這什麼意思?好,這個其實才是Semitic Annuity,最主要的一個,的一個參數,這個大T啊,指的就是溫度,在一般來講呢,它會,這個溫度呢,會隨著時間,一開始的溫度是高的,

[0:38:56] 後來呢,就慢慢慢慢降溫,所以這個大T的指會越來越小,好,那你想一下喔,在Delta E不變的情況之下,T如果大,這是你指,Delta E不變的情況之下,T如果越大,我整個指數的數字就越小,好,越小,數字的部分就越小,但是不要忘記喔,這個指數,是負的,那個數字,所以說呢,如果你這個指數的數字越小,Exponential負越小,就代表,這個機率算起來就越大,的意思,可以嗎?這簡單的數學,好,如果你聽起來有點吃力,你稍微看一下Exponential的定義,好,或者指數的定義,好,所以這句話翻成白話什麼意思?這整個演算法一開始在跑的時候,溫度比較高,所以呢,這一開始,我會比較傾向於,用比較爛的鄰居來取代掉我,我比較願意,用比較高的機率,用比較爛的鄰居來取代掉我,當演算法一開始跑的時候,那你看啊,這個是一個Fall Loop嘛,T的,從1到無限大,對不對?好,隨著你的T,

[0:40:26] 隨著你的時間一直往下走走走,當你這個演算法已經跑了100個Iteration,或者1000個Iteration,隨著Iteration數量增加,我的溫度就會急劇的下降,當大T這個值,越來越小的時候,Delta1除上T,就越大,也就是說Exponential,負的越大次方,那機率,就是什麼?越小,可以嗎?好,所以翻譯成白話的意思就是說,隨著你的這個演算法,跑了很多很多次的Iteration之後呢,我就越來越不願意,用比較爛的鄰居來取代掉我的意思,這個就是Seminatic的年齡,啊你如果覺得這個很難記,你就想,這個跟我們的人生是一樣的嘛,對不對?在座的年輕的同學們,你們現在還年輕,不要怕失敗,對不對?你們應該要勇於冒險,所以呢,你們應該有越高的機率,願意去接受一個,越Risky,越有冒險性的一個選擇,投資理財也一樣嘛,比如說你們現在,理論上你們還年輕,對不對?你們應該可以去投,比較高風險性的資產,

[0:41:59] 等到已經快要退休了,老年人快要退休了,他投的資產,就應該要風險性比較低的,因為他比較不能夠接受,用比較爛的結果,來取代掉現有的結果嘛,所以隨著生命,隨著人生也是一樣,一開始溫度比較高,你可以比較接受比較爛的結果,因為蹲下是為了跳起來,你可以這麼說,好,只要你年紀大了,你就比較不願意,用比較爛的選擇,來取代掉你現在的選擇,這樣懂我意思嗎?就跟人生的哲理是一樣的,這個就是Seminity Unlimited,講完了,就這樣,那這個請大家自己去看,這就是Seminity Unlimited的概念,好,那接下來,繼續進階,下一個叫做Local Bean Search,好,剛剛前面的Hear Climbing,跟Seminity Unlimited,一次就是看一組姐,比如說我以一個姐為中心,我去看周圍的鄰居,然後去決定要不要取代,對不對,好,那Local Bean Search是說,我為什麼一次只看一個姐,我可不可以一次就看K個姐啊,對不對,有沒有,我在這個State Space裡面,我一次就灑K個,Random灑,K個不同的點嘛,對不對,那以每一個點為中心,去看一下週圍的鄰居嘛,一次看K個,好,那所以說呢,

[0:43:29] It begins with K,Randomly generated state,好,那以每一個State為中心,我去看,第一個人,以第一個人為中心,去看一下他周圍的鄰居,然後呢,用最好的來取代掉他,第二組姐,我以他為中心,看一下週圍的鄰居,對不對,不對,我剛剛講太誇張,應該是這樣講,我第一個,Random的solution,我去看一下他周圍的鄰居,每一個,我都可以知道他的objective function value嘛,第二個,以他為中心,看一下他的鄰居,第三個,我也看一下他的鄰居,假設,每一個人,都看10個鄰居,那我現在一開始就隨機灑,10個可能的解,所以呢,Totally,你是不是會有100個鄰居啊,對不對,因為一個人就看10個鄰居,10個人就看,10乘10,100個鄰居,他再從這100個,所有官看到的鄰居裡面,挑10個最好的出來,這個就叫做Local Research,講完了,就這麼簡單,好,那,這麼簡單,你會想說,這個跟,這個跟我剛剛那個什麼,Random Restart Here Climbing,有什麼不一樣,剛剛Random Restart Here Climbing是說,我隨機挑一個點,以它為中心,去看周圍的鄰居,對不對,

[0:44:59] 然後一直跑Here Climbing,好,跑完,得到一個最佳解,啊,我再隨機又再挑一個,又再跑跑跑,找到一個最佳解,好,那跟剛剛聽起來很像啊,好,我跟你講,差別在哪裡,差別在於Local Research,它其實有不同Solution之間的溝通,再講一次,再講一次,怎麼樣一個溝通方式呢,它其實它的意思就是說,比如說我今天,我隨機灑十個,我為了避免重複,我隨機灑五個Solution好了,我第一個Solution,以第一個Solution為中心,我去看周圍的十個鄰居,好,然後第二個Solution,我也去看周圍,找十個鄰居,所以Totally我是不會找到五十個,對不對,這五十個裡面,我要挑最好的五個出來,有可能喔,有可能我挑出來的這五個,全部來自剛剛的第一個Solution的那十個鄰居裡面,這樣大家懂我意思嗎,它跟剛剛一開始那個Random Restart Here Climbing,是不一樣的,因為它是把所有這五個Random Start,Random State,開頭的這五十個鄰居是一起同胞,

[0:46:31] 一起去PK得到最好的那五個,好,那當然也有可能說,我是從第一個Random State的十個鄰居裡面挑出兩個,然後呢,第二個Random State挑出一個,第三個又挑出兩個,這樣去抽到所謂的最好的五個,也是有可能的,所以呢,這一段的話,這字比較多,但講的就是在講這個意思,你會覺得說呢,這個做法好像Seem to Nothing More Than Running K Random Restart,但其實不一樣,好,在Random Restart,每一次Restart,都是一個獨立的開始,那如果是Local Bean Search呢,Useful Information is Passed Among the Parallel Search Threat,好,OK,好,那這個,所以,嚴格來講,Local Bean Search啊,它其實不是一種,演算法,它其實是一種,搜尋策略啦,你今天,我隨機灑五個Random State出去,接下來你要怎麼運作,你可以搭配Hear Climbing來運作,你可以搭配Symmetric Engineering來運作,所以Local Bean Search其實是一個,一個策略,一個策略這樣子,好,那你也可以有一些變形啊,比如說今天我,不是永遠取,

[0:48:02] 這五十個,鄰居裡面的最好的那五個出來,你可能是隨機挑五個出來,好,或者也不是隨機,而是根據某一個機率,來挑五個出來,好,那這機率怎麼設定呢,那就是看,一樣嘛,這邊跟剛剛Symmetric Engineering很像,就是,跟我目前現有的Solution,差不多的,我挑的機率就越高嘛,好,甚至贏越多的,我挑的機率就更高,甚至是必挑嘛,好,那這個就叫做Stochastic的Bean Search,好,那大家不要覺得這個Local Bean Search,這個好像是,老Coco,現在沒有人在用演算法,現在你,even你是在訓練Deep Learning的模型,有的時候你的一個訓練策略裡面,你就會看到,它是講Bean Search,Bean Search,所謂的Bean Search,Bean就是一束,一束的意思,就是一次看一堆結的意思,一束,把什麼稻草捆成一束,的那個Bean Search,OK,這樣可以嗎?好,所以我們用一頁,把Local Bean Search的策略講完了,再來下一個,Genetic Algorithm,基因演算法,一樣,其實基因演算法呢,它可以是一本書,但是我們打算用三頁頭影片,

[0:49:33] 講談基因演算法,基因演算法,它其實是Stochastic Bean Search的一個變形,好,那你一聽你就知道,OK,它是Bean Search的變形,代表它一次會看一堆結的意思,然後呢,前面又加一個Stochastic,就代表說,它有這個隨機性,對吧,好,那基因演算法呢,它其實是受到,這個,演化論的這個啟發,好,它的概念是這樣,一樣的,基因演算法呢,它會從K個Random Generated State出發,好,等於說它一開始呢,就會隨機出K個結,好,那在基因演算法裡面呢,它稱呼這K個結呢,稱為是一個Population,一個群體,好,一個群體,好,一個結,我們又稱呼它這樣,一個一個個體,OK,這個群體裡面有一個個個體,每一個個體,其實就是一個結的意思,好,那比較特別的事情是,它為了要套用這整個染色體,演化的這整個過程,好,所以它會把它的Solution呢,都表達成一個字串,一個序列,一個字串,好,

[0:51:03] 然後這個字串通常都會定義在,一個現有的這個字母,Alphabet裡面,好,等一下我們會看到一些例子,好,那一般來講,這個Alphabet,或者這個,常常是隻有0或1,所以一個Solution表達成,一堆011010100,這樣子的一個Binary String,這是一個常見的一個情況,另外一種常見的情況是,我可能是定義好,這些字母,來表達一組結,這樣子,好,那講這樣子,講這樣子,好像搞不清楚你在講什麼,我們直接舉一個例子,八皇后問題,大家還記得吧,好,在這個八乘八的棋盤裡面呢,我要放八隻皇后,對不對,然後希望八隻放上去之後呢,彼此之間沒有互相衝突,好,那我怎麼放,我現在,我就先隨便放,假設我的,我的這個限制就是說,我一個Colon,只能放一隻皇后,所以,我八個Colon,我就放八隻皇后,所以呢,我就把八隻皇后放好之後,這個盤面,它基本上就是一個結,它是一個Solution,只是,這個Solution是一個蠻爛的Solution,因為我們可以蠻輕易的看出,有好多衝突的地方嘛,But anyway,它就是一個Solution,一個Possible的Solution,如何來表達這個Solution呢,我們可以設計說,

[0:52:33] 我們根據它在盤面上的位置,比如說,今天第一隻皇后,是在第一個Colon的由下往上數,第三個位置,第二隻皇后,就是第二個Colon的,第二個這個,由下往上的第二個位置,以此類推,所以我可以把這個盤面,表達成,3,2,7,5,2,4,這裡,3,2,7,5,2,4,1,這個,這一串,就代表,那個8皇后的那個盤面,可以吧,好,所以,我們可以把每一組解,表達成,一個字串,而我們在經驗的演算法裡面呢,我們稱呼這個字串呢,叫做一個Colon,一個染色體,好,一個染色體,其中呢,呃,這個染色體裡面的每一個質啊,這個染色體裡面的每一個質啊,3,2,7,5,2,4,這個每一個質,叫做,就是一個基因啦,一串基因串起來,變成一個染色體,這個意思,OK,好,所以,這只是,solution 的表達法喔,接下來,針對每一組染色體,我們都可以去評估,它的好壞,在經驗的演算法裡面,叫做,Fitness,Fitness,哦,Fitness,指的就是,Fitness,Fitness,適應程度,好,因為它基本上就是搭建在,因為它基本上就是搭建在,因為它基本上就是搭建在,演化論裡面嘛,

[0:54:03] 就適者生存,不適者失敗嘛,對不對,好,在八皇后問題裡面的Fitness,在八皇后問題裡面的Fitness,可能是設計成,可能是設計成,欸,今天,你的皇后的衝突的,你的皇后的衝突的,這個,這個,這個,這個,這個,這個,這個,這個,這個,這個,這個,這個,這個,會去算出需要Fitness的頻率,會去算出需要Fitness的頻率,這樣,那再來,那再來,講設今天,我們要用經易演算法,我們要用經易演算法,要用經易演算法,來處理八皇后問題,那首先呢,那首先呢,我就先隨機產生出,我就先隨機產生出,四組不同的結,那當然就是表達成,那當然就是表達成,四種不同的染色體,四種不同的染色體,measure 3 種不同的劑다車 種,譬如說,第1種檯面,比如說,第一種 erlebt,omination,的分數第一種盤面給24分第二種盤面23第三種盤面20第四個盤面11分數 數字越大的就代表表現越好這裡你可以自己定你可以自己定你自己的這個所謂的適者生存的這個條這個所謂的適應程度你可以給它一個原則好 根據這個Fitness Value我們要從這四個人呢我們就說它形成了一個Population每一個都是一個Individual

[0:55:33] 那每一個Individual也都表達就是都表達成染色體的形式好啦 那這次這個群體裡面呢我們要先做第一件事情就是我們要先挑出優秀的人出來來結婚產生出下一個子彈那什麼叫優秀呢那就是看這個Fitness的值OK 有24 23 20 11好 所以基本上呢它就是我挑到第一個染色體的機率31%挑到第二個29%挑到第二個26%挑到第四個14%好 那我就挑那假設我也挑四次好 第一次我挑到這個327521第二次我挑到24748552第三次又很巧的又挑到327521第四次我挑到2441512四次那之前被挑出來的我挑的時候是菁英原則就是說你表現越好的就越有可能被挑出來當成是產生出下一代的那個群體那同一個Chromosome可能被挑很多次如果它表現超優秀的話好 挑出來之後接下來兩兩兩兩之間比如說第一個跟第二個結婚好 第一個盤面跟第二個盤面結婚

[0:57:03] 那在這裡就會做兩種不同的動作第一個動作叫Crossover其實就是交配啦好 交配那我們會隨機的在這個染色體這邊隨機找某一個位置好 交配之後呢我就是把第一個Chromosome的前半部分會接上第二個Chromosome的第二個部分第二個Chromosome的第一部分會接上第一個Chromosome的第二部分這個就是交配生出的小孩好 所以這叫子代這是父母這是Parent這是Children好 那同樣的後面這兩個也結婚然後呢進行Crossover得到什麼那不要忘記這是什麼意思這個其實就是新的Solution的意思新的盤面的意思好 這叫Crossover那Crossover這個完呢我們也知道在生物界產生出像一個子代的這個整個繁衍的過程當中有可能會發生突變嘛除了父親跟母親交換染色體之外有可能產生突變所以呢每一個Individual都有可能有一個很小的機率可能某一個基因會變比如說這裡本來是五的它就變成了一有很小很小的機率那像第二個

[0:58:33] 這個就沒有產生任何的突變那第三個又有某一個隨機某一個位置產生一個突變好 第四個這樣子這個叫做Mutation好 那所以說呢這裡你看所謂的這是第一個染色體這是第二個染色體第二個染色體就是2 4 7 4 88嗎 85 5 2這樣子有沒有還有 在這裡就是這兩個Crossover我得到的比如說我把它的左邊這個盤面接上這裡的右邊這個盤面接起來就長這樣所以你看它接起來就變成3 2 7 4 8 5 5 2就是對應到這個產生出下一代之後那同樣的啦這樣的步驟可以繼續往下走產生出下一代之後一樣我就可以去計算這裡面每一個新的Solution你的Fitness的值是怎麼樣對不對你現在產生出新的解嗎產生出來你的新的Fitness是怎麼樣然後呢再根據Fitness的值去挑出能夠繁衍下一代的Chromosome然後又繼續Crossover Mutation那依此類推你可以繁衍很多代最終在這整個繁衍了之後呢最終在這整個繁衍了之後呢最終在這整個繁衍了之後呢這個過程當中

[1:00:03] 可能繁衍到最後你比如說你讓它繁衍100代你就去挑出第100代的表現最好的那一個盤面來當成你的解或者是說你讓它繁衍100個世代然後你再去看說每一個世代最強的那個你都留下來那你繁衍完100個世代之後再把100個世代祖孫從這個曾祖父祖父對不對父母自己小孩孫子什麼玄孫全部最強的拿出來再PK再挑出一個最好的這個就是基因演算法講完了就這樣這就是基因演算法的最核心的概念那當然其實基因演算法或者說講得更廣一點所謂的演化式計算它根本就是一個學問它根本就是一門課它有根本就是有一門課有一本教科書完全就是在講這個的那裡面呢整個大體的概念就是我們這三頁頭裡面所說的那裡面有很多小細節比如說你這個挑你要怎麼挑啊比如說你這個挑你是用什麼樣的策略來挑出優秀的個體產生出下一個子彈那還有啊還有另外一種做法就是你允許假設其中某一彈

[1:01:34] 有某一個個體超級優秀你可以給它一個特權就是長生不老就是它永遠下一代要生就是說它超級優秀你可以讓它在下一次下一個世代也永遠都會保留它一定就可以再生出下一代它一定會被選你可以給它一個特權或者是怎麼樣這裡有一大堆各式各樣不同的變形包含像你的chromazone一定是binary的嗎還是說你可以像現在畫面上的這種你是real number的那所以只要你的想法你所想要求的解有辦法表達成chromazone的形式你就可能可以應用經驗演算法來解這個問題所以我們目前在書上我們這裡是用八王二問題來表達那接下來其他的你自己比如說你自己final project你假設你要做那就看你自己的創意比如說在過去以前我們曾經我們實驗室也用過經驗演算法來幫忙我們解決比如說棒球比賽棒球影片分析的問題那重點在於說你如何把那個問題轉化成chromazone的形式讓它去求一個最佳解好

[1:03:04] 這當然就是各自看你的個人的這個功力看你個人的設計而定好以上就是這個基因演算法好講到這邊一個段落我們來看一下snide上面有沒有問題我如果一開始就存在整體最佳解根據模擬退火的機制它會為了尋找更最佳更佳的解而有機率容許問題嗎就是溫度更高的解存在如果最後發現溫度越來越高它怎麼會回傳原本一開始的最佳解我覺得問這個問題可能有點誤解就是說溫度一定不會越來越高因為根據定義溫度一定是一開始最高溫然後溫度會一路下降所以你的溫度是肯定一路下降的那溫度下降是什麼意思呢

[1:04:35] 就是你越來越不容易用比較爛的解來取代掉現有的解的意思那我在猜這位同學問這個問題是說會不會比如說我本來我在某一個位置然後我用一個比較爛的解來取代掉我那我就變爛了啊你的意思應該是說當我變爛了之後我會不會又一路爛下去我再也就回不到我剛剛比如說我現在在時間t等於3的時候其實我的解比t等於4的時候的解來得更好那你走到t等於4你變爛了然後又跑到t等於5會不會又更爛你的意思是說有沒有可能再回歸到當時t等於3的時候的那個真正在歷史上曾經掌握的最佳解呢我覺得有可能可以也有可能不可以我可以講說因為機率嘛所以它沒有一定會怎麼樣我只能夠說它最終它的解你找到的解會變得越來越爛的那個機率是非常非常低的非常非常低的應該有很高的機會你的解是會朝好的方向來走我只能夠跟你這麼講

[1:06:05] 那當然你如果要很嚴謹的數學證明這個一定也有證明只是我們書上這個證明的部分就略過不談好所以同學你這個問得不錯信件這個我已經說過N次了N次了我不想要再回答成大同學不可以填線上保單我們說過了我們為什麼要弄這個算力就是我們要鼓勵大家來實體上課你只要成大同學你填再多也沒有用因為你必須在現場當場領號碼牌這個我講過太多次了老師說會卡在極大值應該說local maxima但老師後來又說正常來講根本不可能像現在看一眼就知道最大值在哪裡對那這個問題是不是隻能只能怎樣不同方法多找幾個極大值再來比較OK好我稍微對就是說很多時候在現實世界當中我們根本就不知道真正的極大值在哪裡這是很正常的那所以呢很多時候我們找到的解都只是local maxima

[1:07:38] 即使你現在看全世界AI最強的對不對GPT-6 Ultra你認為它現在的這個模型找到的就已經是這個宇宙裡面的最佳解嗎一定不是我們只能夠說它是目前地球上我們能夠所使用的training data裡面能夠找到目前人類能夠找到的某一組你認為是很不錯的一個解而已但它是不是在數學上是一個真正的最佳解事實上我覺得一定不是如果是的話它就再也不會有GPT-7GPT-8GPT-9了嘛一定不是它就不可能再進步了所以一定不是好好那再來所以你的問題是說那怎麼辦呢不能怎麼辦或者是說我們剛剛講了有幾種做法比如說Random Restart我們就多做幾次然後再從這幾次的結果裡面找到相對最好的那一個但是你可能永遠都無法保證你找到的是數學上的最佳解OK我希望這樣有回答到你的問題很多時候我們那你說那這樣子我沒有找到真正的最佳解會不會怎麼樣啊答案是也不會怎麼樣我們還活得好好的很多時候在人類的真正的應用上你找到的解

[1:09:09] 只要夠好就行了我們就覺得Happy了我們就覺得Happy了這樣子像你現在用GPT-6你蠻Happy的吧用得還行吧事實上在GPT-6出來之前你GPT-5你用得也還蠻Happy的吧所以其實沒有一定要找到最佳解只有什麼人要找到真正窮極意義上的最佳解呢大概就是數學家吧在概念上consecually要找到最佳解在實際工程應用上通常我們大部分接受的都是到目前為止能夠找到的那個解可用的解這樣子而且沒有公認最好的最佳化的方法沒有根據不同的問題你所使用的策略先休息一下再回來你不是有提到那個炊火它有可能越來越爛然後你說可能性很低那我剛剛的想法就是就是在演算法為什麼就是先不要記住

[1:10:40] 哎我有個時間的最佳解然後往下走然後它會有一個最終的重點然後如果最後真的最爛那我就用一個額外的能源去把那個可以啊可以啊剛剛我有回答問題的時候我有提到類似像這樣可以可以實際上真正應用的時候的確是可以另外一個問題是我剛剛看到教授說下禮拜有開會然後希望下週不知道能不能約教授就是在meeting一次開會你不是說我希望約教授meeting假設下禮拜我要出國整個禮拜要出國對OKOK那這個聽課跟用什麼電腦

[1:17:28] 呃我需要那你就去做其他的啊你就不用聽課啊哎不然你就專心聽課啊我並沒有這樣子所以呢你現在是要怎麼樣要拿號碼牌對我想那要找助教哦好我們在這一張的前半段那一邊呢

[1:21:32] 在講的大部分的情況我們都是假設它是discrete的case就是說比如說八皇后問題以皇后的位置一定就是在固定的某個位置嘛不會是連續的一個什麼東西啊那呃當然你如果是hear climbing的話你可能是在一個連續的solution space裡面去找到最好的一個解好那其實如果專門針對continuous space裡面的問題的話呃我們有其他的辦法來去做local search好做到所謂的更有效率的local search所以你應該可以感覺的到剛剛在呃剛剛前面講的hear climbing也好然後seminating而已而已GA也好他都他都有一種好像試試看隨機性的感覺有沒有啊我看一下欸隔壁的鄰居比我好我就用他來取代掉我啊我再去看啊然後就是有一種隨機性但在某一些問題呢其實我們是可以有更有效率的解法的啊所以我們底下來看一個例子角色呢之前有給大家看過一個例子就是一個羅馬尼亞的地圖嘛對不對什麼要從A走到B這個好假設呢我現在想要在羅馬尼亞蓋三座新的機場OK那要蓋在哪裡呢在這個地圖裡面你要蓋在哪裡呢呃我們希望達到的目標是

[1:23:02] the sum of square distance from each city on the map to its nearest airport is minimized我們希望每一個城市到它最近的那個機場的距離接下來要越想越好這是我們的目標好等於說這個各個都市都有一個最接近的機場那它都選在一個很不錯的一個位置讓大家很方便可以到那個機場去好那所以呢我們要決定的就是這三座機場的XY座標X1 Y1 X2 Y2跟X3 Y3好也就是我們要決定這六個變數的值的意思好這六個變數的值呢它的一個solution存在一個六維的空間當中對不對因為我們就是要決定X1 Y1 X2 Y2 X3 Y3我們決定這六個值我們要決定一個六維的向量代表這三座機場的位置這樣所以我們是在一個六維的空間當中來找最佳解的一個問題好那首先先寫出我們的objective function value因為我們的目標就是說比例而言每一個都市到距離它最近的那個airport的距離總和加起來會越來越好所以我們可以寫下這個式子我們可以列出一個function代入不同的X跟Y

[1:24:32] 那我這個function的詞呢就定義成summationI等於1到3因為三座機場然後呢summationC屬於C1這什麼意思就是說某一個程式C它是在Di座機場的中間Di座機場的最近的應該說它是屬於離Di座機場最近的那些都市的集合之一叫做小C所以xi-sc就是指C這座都市離它最近的那個機場的X座標的差距的平方加上Yi-Yc的平方這樣那所以說離Ci Di座機場最近的可能有比如說五個都市這五個都市距離Di座機場的距離平方加上有可能有三個都市距離第二座機場最接近那它們的跟機場的距離的平方加起來以此類推整個全部加起來我希望能夠minimize這個objective function代入好我們要最小化那請大家記得當我們在找所謂的最佳解我們在找我們在做最佳化的時候剛剛我們前面舉的例子都是說我們要最大化那個objective function value這OK沒問題那我們有的時候呢我們是要去最小化那個objective function value也OK只不過普遍來講在整體而言各式各樣不同的

[1:26:03] 最佳化的這個工作裡面我們傾向於把問題都轉成我們要去最小化這個cause我們稱呼它叫做cause或者叫做loss因為在數學上你要去最大化一個東西容易造成那個數字會爆掉那如果是最小化那個loss因為loss會一般來講一般正常的心魔教loss最小等於0所以我們去minimize這個loss或minimize這個cost我們一路就會最小化到接近0它不會產生出那個數值的overflow所以即使在概念上我們要去最大化某一個objective function value我們也會把數學改寫一下變成是我們要去最小化那個cost這樣子好那所以我們現在的objective function value是長這樣嗎或者說我們的cause長這樣嗎那為了避免呢這個如果說你今天你要去決定這個機場的位置XI YI的話呃你可以把這個它在這個連續空間當中你XI跟YI有幾種變化有無限多種變化對不對因為它是在一個連續的空間當中如果你為了要避開這種continuous無限多種變化的情況你可以把這個問題呢discritize把它離散化這是一個妥協的方案

[1:27:34] 也就是說呢假設我永遠呢當我在決定任何一座機場的時候我永遠每次我在變動我的選擇的時候呢我只選擇X或Y來進行變動然後呢我每次變動要嘛是加delta要嘛是減deltaOK好所以整體而言呢我每我隨機的選某一個XIYIX1 Y1X2 Y2X3 Y3我隨機挑出一組解之後我要怎麼去定義它的鄰居它的鄰居根據這裡的定義就是說我每次只挑機場的X或機場的Y來變而且每次變都是加delta或者是減delta所以整體而言呢我一定只會有12個鄰居為什麼因為你選X或Y有兩種選擇然後呢你選了之後你可以做的變動要嘛是加delta要嘛是減delta所以就是2乘2一組機場一個機場有2乘2有4個選擇有3個機場4乘3所以總共12種選擇來去所以每一個初始的state我都只有12個鄰居對意思這個是離散化的情況不過

[1:29:04] 如果你要從數學上比較更妥善的來解這個問題呢你其實你可以直接work on continual space你在一個連續的空間當中你去找到能夠使得這個function valueobjective function value能夠有極值的地方能夠有極值的地方好那這裡呢就牽涉到微積分大家學過微積分吧以前呢告訴你一個函數要你求極值怎麼做口訣就是什麼對它進行一次微分令它等於0然後求解對不對你找出來的那個variable的值就是能夠造成這個function有極大值或極小值有極值的地方就可以了OK這是以前大家學微積分的時候或者高中數學你要求極值的時候老師告訴你的口訣那至於為什麼怎麼那麼好用啊我給它做一次對它做一次微分令它等於0然後求解為什麼好我們在這門課裡面不會告訴你為什麼因為你有興趣的話你可以去修最佳化導論那是一門博大精深的課我們這裡沒辦法跟大家講為什麼我也開過這門課啦另外一門不過那已經是另外一門課了總而言之

[1:30:34] 你還是照用你之前學過的那個口訣你要去找到這個function的極值這個function是一個什麼有六個變數所形成的一個函數你要找到這個函數的極值在哪裡你要找到最好的S1應該是多少最好的S2是多少最好的S3是多少S2是多少S1 Y1 S2 Y2是多少就是對它做一次微分那因為它有六個變數啊所以其實對它做一次微分的意思就是我先對S1做偏微分再對S2再對Y1做偏微分再對S2偏微分再對Y2偏微分再對S3偏微分Y3偏微分所以這個function的一次微分就等於是我個別對這六個變數個別做偏微分的結果利他等於零然後你去找到最好的那一組S1一直到Y3的那一組結這是數學上概念上你可以這麼做However但是事情總是沒有那麼容易嘛對不對今天要是你這個function非常的複雜你微分你做不出來或者你找你整理不出一個close form solution的時候你找到一個數學式你代入那個數學式直接求出最好解最佳解的時候你就沒有辦法用這樣子的一個來做This equation cannot be solved in close formIn many cases

[1:32:04] 在很多的情況之下這一個問題根本沒有close form solution那這件事情就會跟等一下我們要講的這個計法其實就跟你現在在Trend Deep Learning Model的時候用的計法是一樣的Deep Learning裡面隨隨便便就是幾百萬個參數幾億個參數現在我們在畫面上看到的這個例子只有六個參數但是在New World Network裡面有幾百萬個但是找到這最好的那一組幾百萬個參數的做法跟我們現在在這裡在講的是一樣的做法原則上是一樣的那我們舉個例子現在三座機場假設我現在先對S1做偏微分大家會偏微分吧微完之後呢就長這樣OK那我怎麼去找到最好的這個是有close form solution的情況之下那如果沒有close form solution你今天你如果要去逐步的去你的XY的話你可以怎麼做呢我們可以做State PisteAssent Here ClimbingBy updating the current state according to the formula我們可以用最陡峭的T這個Here Climbing來找

[1:33:35] 來去update我的X什麼叫做最陡峭的Here Climbing大家懂了吧對不對我從某一個地方出發看一下週圍的鄰居然後我去update到那個鄰居如果今天你找你周圍的鄰居你永遠都是找最強的那個鄰居你update過去的話在概念上你是不是就是說從你現在原本的objective function value變成是那個objective function value所以你objective function value的變動是一個最陡峭的狀況一路走上去你用最快的速度爬到你目前眼見所及的高度對不對就是這一個就是這一個那這個式子呢Xupdate成什麼X加上Alpha倍的這個是function f的一次微分其實這個就是T度的意思在微細本裡面你對某一個方向做一次微分代表的就是你在某一個方向上面的T度的意思這講的再更白一點你想像成你現在是站在一個山坡上假設你現在是在一個三維的空間當中你在一個山坡上你的海拔高度就是你的objective function value然後呢你往右邊走你的右左這個

[1:35:05] 維度叫做X你的前後這個維度叫做YOK那我對X做偏微分是什麼意思意思就是說我要去算我如果往右邊走一個單位的話我的海拔高度會怎麼變動是會上升一公尺呢還是下降0.5公尺呢這個就是叫做我在X方向做偏微分的意義我們也稱呼這個叫做這個叫做T度我們在X方向上面的T度的意思那我也可以在Y方向上面我做一次偏微分物理意義就代表說我現在站在一個山坡上我往前走一步我的海拔高度會變動的情況這個就是我在Y方向上面的T度所以回到這個數學你可以看到說我這個X我用誰來取代掉它呢就是我原本的X再加上我去看我往哪一個我往X這個方向我走一步我能夠造成的海拔高度的變動不止應該是說我要走多遠這個是運作在X上面我這裡是決定方向這是決定方向

[1:36:35] 比如說我到底是我應該往右走海拔高度會變高還是我往左走海拔高度會變高所以這個倒三角的這個gradient FLS走多遠呢就是這個Alpha你是走一步呢還是走十步呢那基本上這個Alpha就成為是Step size你要走幾步的意思一旦你決定好你要走的方向接下來你就看說你要走幾步這個Alpha你要走幾步啊其實沒有一定要走幾步你也不知道要走幾步這基本上是一個參數你要去決定的這個Alpha太小代表說你雖然決定好一個能夠提升你海拔高度的方向但是你每次都走小碎步慢慢走那你可能就要走很久你還要跑到很高的地方嗎所以如果Alpha太小你就要走很多步才會跑到最高的地方那如果Alpha很大太大了你決定好往右邊走那個方向你一口氣就衝兩公里一下就衝兩公里越過山丘又跑到山的另外一頭你的高度搞不好還會下降這樣懂我意思嗎所以過猶不及你Alpha太小你整個update的過程要走很多步Alpha太大

[1:38:06] 你可能就會錯失了你真正最好該走的那個步數這樣子OK所以呢這裡告訴我們說你做梯度是決定你要走的方向那你要走多遠呢你要走多遠其實這又是另外一個最佳化的問題我怎麼知道我現在往右走我到底是要走十步還是要走兩公里說不定是我往右邊走150公尺是最好的我如果真的往這邊走走右邊150公尺我能夠造成的海拔高度提升是最多的這又是另外一個最佳化的問題那你可以用所謂的line search的做法來解決來找到所謂的最佳化的最好的Alpha那在很多的問題裡面呢其實line search有很多種做法那其中很有名的呢就是牛頓法似曾相識對不對大家以前學過只是你忘記了嘛牛頓法牛頓法在幹嘛呢還記得嗎牛頓法用來找求一個function的root求一個function的解Finding root of functionthat is solving equation of the formg of x等於0就是說當我們要求

[1:39:36] g of x等於0的時候哪一個x代進去它會接近0對不對這是牛頓法的功用如果你還記得的話那沒辦法現在告訴你或者是你可以回去翻一下你以前的數學書牛頓法的功用牛頓法update的功用是這樣牛頓法的概念也是我怎麼知道這個x哪一個x代進去我x要代入什麼樣的值g of x等於0其實不知道我就亂猜我先隨便亂猜一個x然後我再去update這個x讓它很接近我新的x代進去之後能夠比較g of x會比較接近0這樣x減掉g of x除上g prime x這個prime代表的就是我對x做一次微分的意思這個是牛頓法update公式有了這個基礎之後我們再從另外一個角度應該說把剛剛講的再重述一次底下這兩頁投影片是我之前教最佳化的時候的兩頁投影片現在你就把它想像成我呢我的參數有s1跟x2然後呢我的objective function value是這個z所以你代入不同的s1跟s2

[1:41:06] 你的z的一個變動可能長得像是這樣的一個曲面好像一個碗假設我們講一個比較簡單的case事實上這個曲面可能是高高低低很崎嶇的一個奇怪的曲面好假設現在這個曲面就是好像一個碗這個樣子那我要找到最佳解我要找到極值什麼樣子的s1y1s1跟s2代進去能夠讓我找到最低的這一個點呢好那其實假設我隨機挑選了某一個x1等於這麼多x2等於這麼多那大概就對應到這個位置吧那我可以去它的objective function value大概在這裡好那相當於我現在站在這個碗的這個山腰上對不對我在山腰上那跟我這個位置同樣高度的這一圈假設我們把它投影下來這個叫做level setlevel set你把它想像的就是等高線的意思在我們地理課裡面的等高線那我們現在假設這個向量叫做x0如果我們去算f 的t度代表的就是這一圈

[1:42:40] 跟這一圈等高線的切線垂直的這個方向的意思好那其實也就是你想一下這個需要一點點想像力你想一下這個切線這個方向相當於是說你現在只能站在這個地方你要往切線的這個方向走你的海拔高度會增加最快你想一下你現在人站在這個你如果往那個方向走你是不是就很快的沿著這個碗的這個高度一路就爬升你只要走一個單位他就一路就爬升到這個地方或者相反假設你今天你是要去minimize你的高度那你就是走切線的反方向就是往切線的反方向來走所以你就是往這個方向走其實你沒有辦法直接往因為你不會說往這個方向走掉下去啦其實往這個方向走的意思其實就是你會快速的走到這個碗的底端的意思這樣可以嗎這需要一點想像力稍微抽象一點好所以大家只需要記得一件事情就是說你在這個function裡面的某一組體你去算他的t度t度代表的意義是你能夠快能夠用最快速讓你提升海拔高度的那個方向就是他的t度反之

[1:44:11] t度的反方向就是能夠讓你快速降低海拔高度的那個方向ok好那現在我們現在假設人在這裡我們已經假設我們現在是要去走到碗的最底處好了我們知道他是這個方向可是要走多遠要走多遠這時候牛頓法出來了牛頓法大家以前高中或者大學有幾分一定看過這張圖今天假設我這個曲線長這樣就是說我這個碗啦我現在站在碗的這個地方我這個碗的這個高度一路曲線是這樣走所謂的牛頓法大家還記得嗎牛頓法是怎麼做的就是什麼我現在這個點我對應的x在這裡我的高度在這裡我站在山腰上的這裡我在這裡我做一個切線有沒有我做一個切線碰到x這個地方這個點xk加1就是我要update過去的位置我本來從sk出發我要update到哪一個sk加1就是我這樣切線過去到這裡這個sk加1就是我要update的地方好我在從它的高度這個點我在做一個切線我就下一次update我就跑到這個地方

[1:45:42] 如果你還記得的話高中老師數學老師就告訴你說牛頓法真的厲害你只要update兩三次之後你幾乎就非常非常接近真正的標準答案x star這個點你看幾乎我update到第三次我幾乎就已經達到真正數學上的最接近的點你以前一定算過這個牛頓法非常厲害好那現在回到這裡我們現在人在這裡我要走到我的最低點我要走多遠呢我就是用牛頓法那牛頓法怎麼推的你看一下gprom sk所謂的gprom sk是什麼意思就是代表這個切線的斜率對吧數學課斜率那斜率怎麼算就是你高度的變化除上寬度的變化你高度就是g of sk寬度的變化就是sk減掉sk加1對不對這裡整理一下牛頓法的update公式寫成sk加1等於sk減掉g of sk除上gprom sk這就是牛頓法的公式所以我們可以利用牛頓法

[1:47:13] 決定說我們怎麼去達到最好的那個α好回過頭來我們回到剛剛一開始的這個式子這裡的t度包括三角形的f of x它扮演的角色就如同是欸牛頓法裡面的這個gx所以不要忘記倒三角fx已經是fx的一次微分了它的角色就如同是這裡的gx所以這裡的gprom x呢就相當於是fx的二次微分的意思二次微分的意思所以to find a maximum or minimum of fwe need to find xsuch that the gradient is 0為了要找到最好的那一組結x我們其實要對f做一次微分令它等於0所以你看一下這個式子所以相當於是我們要找到適合的x使得它帶進去之後等於0你看一下這個臉這個跟我們牛頓法裡面要求的這個臉不是長一樣嗎所以我們要如何找到最好的x使得f的gradient等於0呢

[1:48:44] 就等於是我們要同樣的那個x能夠使得這裡的gx等於0所以代入牛頓法gxin Newton's formulabecomes the gradient of fx所以說呢原本update的那個式子牛頓法的那個式子就變成是x等於是x減掉這是gx然後呢除上gprom x其實就是等於是fx的兩次微分寫成這個樣子它基本上是一個hessian matrix一個多函數的一個多變數的函數你對它做二次微分之後它會變成一個矩陣這個矩陣叫做hessian matrix裡面的值hij這個裡面的dij這個值其實就是f對xi做偏微分再對xj做偏微分的意思ok如果你聽起來有點吃力呢你就是要稍微複習一下以前的數學這其實沒有到那麼難那這裡寫成是hof fhof x的什麼-1這個是代表它其實是除再分五的意思但因為它是矩陣嘛大家知道說在時數裡面我們做除法在矩陣的運算裡面就相當於是在inverse的意思好

[1:50:14] 總而言之呢整個update的式子是這樣好那local search method呢它還是有可能會卡在local max嘛卡在這個屋極上面或者是平原上面高原上面那所以即使你看起來用這種比較高級的厲害的continuous的這種update的方式呢你還是有可能卡在local min所以說呢你可以搭配random restart的策略或者是simulated annealing的策略來解決這個local max嘛的問題好這樣可以齁那其實這個整個的update的這個整個原理呢後來其實它一直都沿用在包含你現在一直有些人可能都已經在寫這個deep learning的程式對不對好那我們剛剛雖然講說這個alpha沒有alpha要怎麼決定我們後來就變成是我們常常是設定一個固定的一個值啦根據經驗設定一個固定的值大概你跑夠多次也不會差太多啦那你如果現在已經開始有在寫一些deep learning的程式的話其實這個alpha就是learning rate的意思你設定learning rate其實就是這個意思

[1:51:44] 你根據你的gradient你找到你的方向你要調多多元這是learning rate的意思是同一件事好那各式各樣的最佳化問題有很多嘛有一類的問題叫做constraint optimization problem就是有一些限制的最佳化問題好那它就會要求說你這些變數一定要符合某些規範比如說我們剛剛講這個羅馬尼亞的機場這個很顯然它一定有一個規範就是說你的S跟Y不可以是負的這是肯定的你地圖上怎麼會有什麼負的座標那有一類的constraint optimizationproblem呢首先constraint optimization problem這本身就是一門課也可以是一本書的內容在constraint optimization這個大範圍的情況之下有一種類別的問題叫做linear programming的問題againlinear programming也可以是一本書也可以是一本課那它只是constraint optimization problem或者是convex optimization problem的一個字集合而已那他說呢這種linear programming的問題呢在實際的生活應用上其實還蠻常出現的它呢它也許是最著名而且被廣為研究的一類的問題

[1:53:15] 那它是屬於convex optimization problem的一個special case什麼叫做convex optimization呢就是說它的constraint它的objective function可以寫寫成一個convex functionconvex function就是convex function我不想要講它的數學定義總之你可以自己去翻來我們舉個例子這也是從我另外一門課的同學拿過來的一個linear programming的問題呢通常會長這個樣子比如說我要去minimizec transpose x這是什麼東西這其實沒有什麼了不起學過線性代數的都知道線性代數裡面我們喜歡把內積兩項量的內積寫成矩陣相乘的形式就長這樣所以這其實就是c這個項量跟s這個項量在做內積比如說c1s1加上c2s2加上c3s3c這個項量就是c1c2c3s這個項量就是s1s2s3對不對所以c1s1加上c2s2加上c3s3我可以寫成這個樣子我要去minimize這個值但是呢我要這個條件線性代數整本課本整個學期

[1:54:45] 不是都在解這個問題嗎a s等於b它是一個線性系統就是說我的這些x應該要符合什麼特性比如說都要大於0然後s1加s2加s3要等於72s1加上3s2加上5s3要等於5合在一起就變成一個線性系統a s等於b就是一個你在objective function是一個linear equation是一個線性方程式你的constraint也是一個線性方程式你的constraint也是一個線性方程式你的constraint呢你的constraint呢你可以是a s等於b當然也有可能是a s大於b或者是a s等於b不過在最佳化的不過在最佳化的整個演算法的推導過程當中整個演算法的推導過程當中都會把這個a s等於b都會把這個a s等於b都改寫成這種形式都改寫成這種形式有一套SOP有一套制式的做法你可以把問題改寫一下那我們就是專門針對這一類的問題有一些演算法來求解當然這是另外一門課的內容國道精深的最佳化導論的內容最佳化導論的內容那麼舉一個例子讓大家有感覺這其實很實際的例子

[1:56:16] 這一類的linear programming的研究大約是在二次大戰期間大約是在二次大戰期間快速的發展所以後來它廣泛的用在像經濟學作業研究的這個領域裡面作業研究的這個領域裡面為什麼在戰爭期間它發展速度那麼快呢我們看一下這個例子它說現在有一個製造商它會製造四種產品一二三四這四種產品那為了要製作出這四種產品那為了要製作出這四種產品我可能需要一些人工我要A這個原料我要B這個原料我要A這個原料所以這四種產品都得要有這三種資源都得要有這三種資源才能夠完成那生產每一種產品它對於人力以及材料的需求不一樣那為了要決定我的我的製造的這個安排我到底要製造一號產品要製造多少份二號產品要多少份三號產品要多少份我基本上這個就是一個最佳化問題我基本上這個就是一個最佳化問題這個製造商呢不能夠用超出你現有資源不能夠用超出你現有資源來製造這些產品所以底下這個例子就是說

[1:57:46] 我要製造一號產品呢我要製造一號產品呢一種人 州一個 One May Week然後6公斤的A跟三合的B然後呢二號產品呢我要兩個人 州5公斤的A4合的B所以我到底1234這四種產品我要生產幾份那我們先假設一號產品生產S1份二號產品生產S2份一匙類推我只有20個人中我只有100公斤的A材料我只有75盒的B材料所以我的限制就是X1乘以1加上2X2加上1乘以X3加上2乘以X4一定要小於等於20因為這是我所有的人力資源總和你生產這些產品你用的人力資源一定要小於等於20那同樣的6乘X1加上5乘X2加上3乘X3加上2乘X4一定要小於等於100然後呢一樣針對B這個材料它要符合這個條件這個是我的限制那我想要我可能我要做的事情可能是說我這四個產品

[1:59:16] 1234這四個產品它的售價可能不一樣假設我這個生產商我的目標是我這一週我這個整個生產的結果我希望能夠獲得最高的利潤所以我要去Maximize假設一號產品它每一個賣100塊100乘X1二號產品每一個賣50塊加上50乘以X2一直類推我要去Maximize我所得我得到的利潤但是呢我要怎麼樣我要去符合這個條件所以你想一下我剛剛的這個問題是不是就是這種形式的問題這就是一個Linear Programming的問題好那這種問題怎麼求解呢很抱歉這個是一整個學期的課有興趣的話請去修最佳化導論我們在這門課裡面呢我們就不再講怎麼求解這裡這是一個博大計深的學問有一大堆的最佳化的這個演算法在裡面好來那這是一個小段落我們來看一下有沒有問題重新計算時我們理論上會偏向找

[2:00:46] 和原先結果差距較遠的解那有沒有可能在計算上會一直引導我們回取原先結果例如一個寬度很高的丘陵在遠處有一個很窄的山峰你說在重新計算時我們理論上會找離原先結果比較遠的解好這句話呢對但是也錯這其實在大部分的演算法設計裡面這一樣又跟人生的大道理一樣你在演算法一開始跑的時候我們的確傾向於一次就走遠一點這也牽涉到我們剛剛前面講的在continuous space裡面我們在update我們原本的解X的時候我們那個α其實有一個策略是當我演算法一開始開跑的時候我的α要大一點然後呢等到你iteration跑很多很多次了我傾向於就把α再縮減一點然後再慢慢縮減一點所以你講這句話對也不對對是指說在一開始跑的時候呢我們的確傾向於可以大步走一開始找遠一點的可是等到你跑了一萬個iteration或多少個iteration之後呢

[2:02:17] 你要慢慢的不要那麼的冒險你的α就小一點你就會找跟你周圍鄰居相對近的一點解因為當你已經跑了一萬個iteration之後你應該有足夠的自信你已經找到一個還蠻不錯的解了這樣瞭解嗎那你說有沒有可能在計算上引導我們去找原先一直去找原先的解我覺得不能排除有這種情況不排除有這種情況你如果在某種剛好某種很特殊的case裡面它就在兩邊在那邊震盪是有可能的所以我們剛剛在講說我們那個α事實上是可以隨著時間變動的我們的seminary annealing的那個t也是隨著時間變動的那一旦有變動你從這邊走過去你下一次不見得再走回來了因為你的有一些參數已經變了這樣瞭解嗎所以附帶一提如果現在現場或者是線上的同學有些人你已經在跑deep learning的程式了你就會發現你的learning rate很多人會建議說你在前面100個aerop的時候你learning rate是多少你過了100個aerop之後每過50個aeroplearning rate就乘上0點多是不是這個意思就是這樣的意思

[2:03:48] 一開始冒險一點後來就越來越保守所以這個最佳化跟我們人生的哲藝是一樣的我講過很多次在座的有沒有什麼問題這只有兩根這是local沒什麼根這是最大的沒什麼然後這個都沒什麼山丘就是所以只要在那個範圍內都一定會遇到阿宗然後一個很窄的山峰所以它只有在那個階段往上跳就會找到那個最大的它意思應該是一個比較奇怪的地方所以我剛剛講了如果在一個這麼特別的狀態之下有可能就是會發生剛剛同學所講的這麼奇怪的事情不過那個我覺得那個都是要特殊設計的問題才會這樣子我們一般在做真正實體世界的最佳化的時候是很少遇到這樣子的東西的OK那我們講到這邊再休息一下再來範圍內呢

[2:16:36] 有一類的問題是屬於這種在之前講有一些題目是你可以完全知道它整體的狀態比如說八黃或五穩那有一些呢是你只能夠部分觀察到現有相對侷限範圍內的狀態比如說Here climate你從某個地方出發你只看到周圍的鄰居的一小部分所以你就做local search所以你如果只有一部分的觀察那就所謂的Search with partial observation那我們這裡舉一個例子假設有一個機器人他是在一個類似迷宮的環境裡面他大概長這樣在一個類似迷宮的環境裡面然後呢他配備了四個sensor這四個sensor分別可以去感應東西南北四個方向有沒有障礙物那假設呢這些sensor都永遠都正常運作那如果是這樣子的話呢而且呢這個機器人呢

[2:18:06] 他知道這整個環境的地圖那他說呢這個機器人的導航系統呢壞掉了所以說呢他只能夠做移動這個動作那他可能會隨機的從四個可以走的這個方塊裡面去進行走動那我們的目標呢就是說當他具備的能力是什麼他能夠去感測一下周圍的有沒有障礙物然後呢你可以走向沒有障礙物那個地方走過去然後他去感測一下周圍的障礙物這樣子然後呢他也擁有一整個地圖在這樣的情境設計之下呢我們的任務是要去決定目前這隻機器人他是走到哪個位置吧那這個問題in this case這個case他其實也不難比如說假設一開始我們只知道說我們不知道他在哪裡但是我們有這個地圖然後呢一開始呢這個機器人他就透過他的sensor然後就感應到說北邊南邊跟西邊有障礙物ok那如果是這樣子的話其實我們很輕易的就可以知道說他應該在這幾個位置

[2:19:36] 因為假設感測器永遠都是百分之百完美運作的話因為像這個位置他的北邊西邊跟南邊都是障礙物對不對這個位置也是啊北邊這是一個圍牆嘛北邊西邊南邊有障礙物所以他應該在這邊或者在這邊或者在這邊或者在這邊這樣所以這第一個時間點我們大概就可以大幅縮減他可能所在的位置然後他就可能就做了某一個動作那看起來他一定是往東邊走嘛因為北南西都有障礙物那就往東邊走往東邊走之後呢下一個瞬間他又再感測一次就發現了北邊跟南邊有障礙物那其實我們就可以很輕易的推斷出在這個case裡面他一定是在這個位置對不對因為你這個如果往右走北邊就沒有障礙物啊你這往右走北邊沒有障礙物你這個如果往右走南邊沒有障礙物啊只有你這個往右走北邊跟南邊有障礙物所以我們就可以去推算出他真正的位置是如何好那當然這是一個簡單的例子啦以這個例子來講我們如果已經知道地圖了我們用一些規則我們大概就可以知道人在什麼位置但是如果你把這個問題延伸到更複雜的情況比如說今天你的感測器

[2:21:07] 事實上在未來我們有一些內容就會提到假設你的感測器只有八成是對的有兩成有可能回答給你錯的答案這個時候呢你就要花更多的時間更多的力氣去推算你可能在哪個位置那這個是之後會出現好那這個chapter的最後一部分在講的是online search有一大堆的名詞啊他說到目前為止呢我們講的這些agent呢大部分是offline search就我告訴你一個環境然後你就去解它they compute a solutionafter setting foot in the real worldand then execute the solution那online search的agent呢interlive computation and action就是他一邊做動作做完動作之後呢又去感測環境然後再去決定下一個動作那所以最經典的例子呢就是我今天把一個robot丟在一個新的這個beauty裡面去然後請他呢自己去走然後去建構地圖其實就是你家的掃地機器人啦你家的掃地機器人就是這樣所以他在做的是一個online search即時的有根據觀察到的東西以及過去的歷史來去建構你對於這個世界的理解這樣

[2:22:37] 那online search演算法呢有幾個特性它規定呢這個agent只知道說他可以做什麼動作以及他做了某一個動作之後得到某一個結果你的cost是多少以及呢你是不是已經完成了你的目的這樣子那你在真正做這個動作你在S這個地方出發你做了A這個動作你在真正得到這個動作的結果之前呢你是不會知道你做這個動作要花的花費有多少ok那所以這是另外一個例子啊在一個類似迷宮的環境裡面你要從S走到Gok那你真正你從S我們一看我們就知道說S要往右往右往上往上就得到G了嘛那是因為你從上帝的視角來看如果你今天你只知道S然後呢你有一些感測器你發現你上面也可以走右邊也可以走嘛那你可能就會走到上面走到上面你再感測一下你才發現說欸是這個上面右邊左邊都不能再走了你只好再走回來所以你就浪費了一步了那你就是得要一邊走一邊受到阻擋

[2:24:07] 然後再重新然後再一路往下走就是所謂的online search好所以說呢finally the agent might have access to an admissionok那這個是如果你是盲目的走反正你就是到處亂踹從S要走到G那其實這個很像是什麼我們在上一張我們就講過你可以用比如說DFS或者是BFS對不對你可以做所謂的盲目的搜尋那同樣的如果你有heuristic function的話對不對或者說甚至你是automisible的automisible的heuristic function的話你就可以用A star search對不對來去找到最佳的那一組接好如果你走迷宮來講你可以把這個題目把這個問題描寫成在一棵樹上面走ok如果是這個題目的話那當然不見得每個題目都有辦法所以這裡你會遇到各式各樣不同的題目那你在評估一個online search的效能它的演算法的效能的時候呢你當然你可以去算它的cost你當然希望你的cost能夠越低越好那這裡的cost的定義可能是比如說你走的步步數要越少越好或者說你走到某些地方

[2:25:37] 可能會扣很多分那個cost就很高也是有可能那所以如果在走地圖這個例子來講的話呢the cost is the total pass cost那你開發出好多不同的演算法都可以從起點走到終點那你如何去評估哪一個演算法比較好呢因為最終其實大家都能夠走到終點啦那有一種方式就是你去算它的所謂的competitive ratiocompetitive ratio是說呢compare its cost with the pass cost of the passthe agent will follow if he knew the search space in advance就是它跟最好的情況比起來最好的情況是它已經知道整個地圖的結構了所以它可以算出一個最佳解跟你不知道地圖的結構你在那邊搜尋你在那邊找那相較之下你的這個cost花的是完美的多少倍這叫competitive ratio這樣子那我們當然希望說這個competitive ratio越小越好因為它就是越接近最佳解的意思好所以說這個online agent呢基本上最後

[2:27:08] 它可以知道說它走到哪一個telling what state it has reached然後你知道你你可以把之前你走過的那個歷史都儲存下來所以你對於這整個環境你就越來越理解那所以你對於目前整個地圖環境的理解就可以幫助你去如何走到你怎麼走下一步你可以去做最好的一個決策所以你一邊在決定你怎麼走然後一邊執行完這個動作之後你也去觀察新的這個環境是怎麼樣所以說呢這裡就提到說你可能你可以用DFS來做這樣子的一個問題好那here climbing的話呢其實也是可以這樣就是說Climbing你是站在某一個點看它周圍的環境對不對然後呢如果可以走那你就走過去或者是說你用某種譬如Risk的話你知道說往右走其實更接近你的目標好相當於這個往右走右邊的這個鄰居是一個比往上走這個鄰居更好的一個鄰居那你就選擇往右走好所以你也可以把之前我們在這一張先前所講到的一些策略也用進來

[2:28:38] OK那所以說雖然我們這裡講Online Search Agent或者這個Online Search Agent但它其實只是說你不同的問題的定義雖然說我們講了好多的Search對不對Online SearchBean Search然後什麼什麼Search什麼什麼Search但雖然它都叫Search但是有時候它們的地位是不太一樣的有的時候是針對不同問題的定義有的時候是不同的不同的搜尋的策略有的時候根本就是一種演算法但是我們都叫它什麼什麼SearchOK好那所以最後面這裡就稍微講一下這個所謂的Online Local Search這樣子所以最後面這一塊是比較聊聊天的比較沒有具體的例子好所以講到這裡我們就完成了第四章接下來呢我們就要進入到第十二章一下怎麼跳那麼多好還記得我們在講那個人工智慧的歷史的時候我們就講說在什麼1950年代1955年1956年出現了AI這個詞後來就開始大幅的進展然後大概到了1980年代開始就是會引入這個機率來進行

[2:30:09] 這個AI的發展對不對所以我們現在呢其實就是直接從整個General的AI的一些定義我們直接就跳到1980年代1990年代中間大概在冷戰時期那時候大部分的AI的學者在走的是符號邏輯學派的那一些東西因為到現在已經真的幾乎沒有了所以我們完全跳過所以你從第四章所以你如果去看我們那本很厚的書第二個part什麼五六七八九十這幾章都在講那些符號邏輯學派的那些東西那因為在現在這個年代我等一下要講的這個東西你都覺得很老了更不用講那些東西就更老了所以我們直接跳過我們直接進入到第十二章第十二章呢我們開始要考慮一些所謂的不確定性進來所以在剛剛前面的第四章我們已經有稍微講到一點點就是說如果今天這個環境裡面的資訊我們只能夠部分觀察到所以當我們在做一些決策的時候有時候我們得要我們可以盲目的嘗試這是blind search那如果我們多知道一點點我們有某種heuristic的話

[2:31:40] 我們可以用A star search對不對好那如果我們沒有heuristic或者說我們有heuristic我們如果去評判走哪一步會比較好那這時候呢就有人提出說我們應該要引入機率因為機率天生就是可以拿來表達所謂的不確定性某一條路可能有用的機率有多高你可以去進行這樣的一個評判所以第十二章呢我們其實主要是為大家複習機率那你在整個AI發展的過程當中你可以把它自己想像成OK我現在已經開始進入到90年代了1990年代了那種感覺好那他說啊為什麼要引入uncertainty不確定性我們需要處理不確定性因為很多時候呢我們只有partial observable我們只是部分知道我們所處在這個agent只有部分知道你這整個環境的資訊這整個PAS你只有部分知道的資訊或者是說呢你是non-determinant還記得這什麼意思嗎就是說有沒有你還記得那個吸塵器的例子假設你叫它往右轉它沒有真的往右走呢因為機器故障的關係

[2:33:11] 或者因為某種控制什麼的關係或者是某一些noise的關係你叫它往右走它就沒有真的往右走實體世界有這種情況啊這就是non-deterministic或者是說你根本就是環境也看得不清不楚然後呢你這臺機器也爛爛的那種一些爛東西然後呢你叫它做一個什麼事情然後就是就是做不好也許混合在一起所以你的agent就是必須要處理一些uncertainty那agent呢may never knowfor certain what state it's inor where it will end upafter a sequence of actions所以很多實體世界當中的情況是這樣子的那底下呢我們就要來主要用一個例子來引導這整個說明牙醫的例子OK假設呢牙痛了你牙痛了你就看牙醫這樣子欸如果你牙痛你就看牙醫我們現在牙醫要進行診斷呢怎麼診斷我們先試著寫規則看看所以Write a rule for dental diagnosisusing propositional logic這個propositional logic就是我們跳調的那幾個chapter在講的東西

[2:34:41] 它花了好幾個chapter在講這種propositional logic那我們來看一下我們來看一下為什麼寫propositional logic不會work所以可能是這樣啊今天你牙痛了你去看牙醫假設這個牙醫心中只有一條規則就是你牙痛是不是啊你蛀牙了這樣子你覺得這樣對嗎事實上常常是不對的你今天是會牙痛有可能是引發有可能我就我聽到你的描述說你牙痛OK如果我給你的結論只有唯一一個就是你有蛀牙那這樣子常常會判斷錯事實上這個規則有可能是你牙痛是不是OK你可能是因為蛀牙或者是你的牙齦有問題或者是你嘴巴有潰牙你嘴巴破或者是怎麼樣怎麼樣怎麼樣或者是怎麼樣怎麼樣怎麼樣這樣子才是一個距離實體環境比較正確的一個描述嘛對不對好當然不幸的是你為了要讓這整個描述變得合理而完整你這個後面這個oror or你可能or不完啊你這個條件太多了OK你牙痛你牙痛說不定是因為你剛剛走路撞到門

[2:36:12] 你牙齒在那邊流血啊對不對有可能是這樣啊你有可能是神經痛啊你牙沒有問題你是神經在痛啊好各自怎麼樣好那你說不然這樣子我可不可以改過來寫另外一個規則就是說你只要有蛀牙你就會牙痛這樣子但其實這個規則也是錯的也是錯的不是所有的蛀牙都會造成牙痛啊這樣子所以這個也不對好所以這裡就用這個例子來告訴你說如果你要用logicpropositional的方式來診斷牙痛的話這根本就不切實際所以這直接打臉有沒有1960年代當時理論那些特級符號學派當然當時還很久以前啊他們就弄很多這種logic他就不是我們在開學立唐課都講說OK只要你能夠把你的知識寫成logic我就一定有辦法證明啊對不對就講一大堆嘛但你就從這個簡單的例子裡面你就知道說你光牙痛診斷這件事情你就沒有辦法完整的寫出原因是什麼第一個laziness懶惰就是說你不管你這個proposition你是前項還是後項

[2:37:42] 可能都有一大堆要寫的而且搞不好寫不完你無法窮取出所有的原因或者窮取出所有的結果這是第一種阻礙第二種阻礙是有些東西你可能由到目前為止你也不知道為什麼會會這樣子當然牙痛可能已經研究很透徹了但是比如說失智症比如說肺症為什麼老人會失智可能目前在醫學界也沒有一個完整的理論來說因為什麼什麼什麼而什麼什麼什麼你根本也沒有一個理論完整的理論來描述它所以你根本就寫不完那個logic那也有可能是practical ignorance就算我們知道這些規則我們ok就算我們有一個完整的規則我們很多時候呢也無法排除所有的情況因為你可能要做各式各樣不同的檢查比如說假設我們現在已經完全知道為什麼老人會失智他是因為腦子裡面的什麼某種蛋白的累積再加上血糖血壓等等等等再加上某一種

[2:39:12] 細胞裡面的什麼什麼病變整個綜合起來就一定會有失智你即使你知道你也變成你要做好多不同的檢查你才知道說他的什麼什麼什麼Alpha蛋白濃度有到多少累積多少再加上你的血液裡面的什麼指數等你可能也就實際應用上也太貴這就是為什麼沒有辦法光靠Peper-Z去模仿那怎麼辦呢我們現在的工具就是我們引入機率講半天就是為了引入機率那機率呢提供了一個辦法讓我們去摘要所謂的不確定性這個不確定性有可能源自於我們懶惰懶得寫這些前後項或者是說你實際在真正應用上你就是沒有辦法做出百分之百的檢測你只能夠用機率來summarize這件事情那所以你可以這樣子啊比如說根據過去的統計經驗你可以說過去啊百分之八十的牙痛的病患我過去我是一個老醫生根據我過去看診三十年的經驗百分之八十有牙痛的病人他有助療這句話沒有錯對不對沒有錯但是呢

[2:40:42] 可能可以幫助我進行診斷OK那你可以根據OK你說你牙痛了是吧那我心中就已經大概知道你八成是有助療那接下來我再做一些檢測我再多看了一些證據之後那我就可以百分之九十五認定你有沒有助療過有助療過沒助療過以此類推好那所以說呢他說機率啊基本上有修過機率統計應該大概會有很多修過機率統計吧好我們接下來就是複習機率基本上是根據你目前已知的資訊它是跟你目前已知的資訊是搭配在一起的好比如說the probability that the patient has a cavitygiven that she has a toothache is 0.8好就是說他有牙痛的情況下他有助療的機率是百分之八十好所以我觀測到的是他已經牙痛了在他已經牙痛我知道我看到這個事實的情況之下他有助療的機率是百分之八十這樣那也許接下來醫生就看一下他這個人的病歷呀發現他過去有牙齦的一些疾病的歷史好那這時候我有了新的evidence我有新的資訊了給第一個這個病人有牙痛而且他有牙齦他有牙齦的疾病史

[2:42:15] 他有助療的機率是0.4因為我有了一個新的knowledge進來我多參考了一個新的knowledge所以我去update我整個機率的推算好那我收集越多的evidence我就可以越精準的來描述他的狀況他說這個病人呢我們根據目前我們所得知的所有的證據他有牙痛他有牙齦的疾病史我給他拍了S光我看得到的嘴巴用燈去照去看根據這以上所有的證據他有助療的機率等於0這樣子這是有可能的我看到任何我基於這些證據我就判別說他有助療的機率等於0.4以上這三句話每一句都是對的好All these statements do not contradict each other這些句子這些statements都沒有矛盾喔所以他基於不同的knowledge base的情況之下我去預估這個機率就會不一樣每一句都是對的對所以這邊只是要跟大家強調說你在預估一個機率的時候

[2:43:45] 其實是根據你現有已知的某一些資訊來去預估這個機率這樣好那OK所以引入機率之後呢我們之前提到一些utility based agent大家還記得嗎我們在第二章介紹我們的agent是什麼從最簡單的基本反射的agent然後再來goal based agentmodel based agent再來是utility based agent對不對我們現在進入到utility based agent當你面對你觀測到某一些訊息你要決定哪一些動作效益最高的時候你就可以引入機率那所以就讓agent呢他對你不同的動作有一些偏好utility theory says thatevery state has a degree of usefulness or utility有某一些效益那我們應該會偏向於讓效益最大化的那樣子的動作好那所以說呢考慮到機率考慮到效益兩個整合起來呢就是你可以做決策你做決策那所以說呢這個所謂的discipline theory他其實就是說一個agent呢我們說他是理性的if and only ifhe choose the action that yields the highest expected utility

[2:45:18] 這句話我們在第二章也講過什麼叫做是一個理性的agent呢就是根據他現有的資訊他去做出能夠極大化效益的那種agent就叫做rational agentok那這個principle呢也叫做maximal expected utility就是極大化預估的效益機率呢基本上就是在描述某一個世界出現的狀況去描述它的uncertainty好那所有可能出現的狀況呢就稱呼叫做simple space好所以舉個例子來講丟兩顆骰子你可能可以出現36種狀況好比如說兩顆都丟出1啊一顆丟出1第一顆丟出1第二顆丟出2啊好或者一直到第一顆丟出6第二顆丟出6啊所以總共第一顆有6種狀況第二顆有6種狀況36種狀況這36種狀況呢我們稱呼它叫做simple space我們習慣呢用大寫大寫的字母來表達它比如說這個希臘字母大寫omega來代表這整個simple space小寫的omega呢來代表了在這個simple space裡面的某一個狀態某一個狀態

[2:46:49] 好那我們都知道嘛你任何的某一個狀態出現的機率介於0到1之間你所有的狀態在這個simple space裡面所有的狀態出現的機率加起來要等於1嘛那所以說呢你是這36種狀態裡面的任何某一個狀態出現的機率就是36分之1嘛這是古典機率那很多時候我們有興趣的可能不是單一的某一個狀態我們可能是對某一種組合我們比較有興趣比如說我們對於兩顆骰子的點數加起來等於11的這件事情我們感覺到有興趣我們稱呼這種叫做一個event一個event那或者是說呢在AI裡面呢也稱呼這是一個proposition你可以用文字來描述出一個proposition就是說是對於兩個骰子的點數加起來等於11這件事情有興趣請幫我估算兩個骰子丟出總和是11的機率這樣子那對於每一個proposition呢它的機率怎麼估比如說一個proposition5這個5出現的機率就等於是能夠造成這個proposition的所有的element

[2:48:19] 所有的可能的情況的機率加總講得文燒燒的什麼意思啊就是說假設我今天有興趣的是總和為11點的情況那有可能是什麼就只有兩種狀況嘛第一顆丟出5點第二顆丟出6點或者是第一顆丟出6點第二顆丟出5點對不對所以我想要去預估說總和是11點的機率我就是把剛剛那兩種狀況的機率個別都是1 3 6分之1兩個加起來6分之2就這意思寫成數學就是這樣OK所以這裡就講到這件事講到這件事OK所以說呢我們有興趣的proposition可能是比如說總和41點的啦或者說我們丟出來的兩顆骰子是同樣點數的啦這些東西那這些機率呢到目前為止我們講的這些機率呢都是unconditionalunconditional那也就是說沒有一些附帶的先決條件的就是說某件事情出現的機率是怎麼樣某件事情出現的機率是怎麼樣好附帶一體我現在看到一些數字所以我要講第二個通關密因這這麼突然5665好了請助教幫我記一下因為等一下也快下課了還活著的人應該不多了

[2:49:51] 第二個通關密因就是這一剛剛講的這個好好那所以我們剛剛前面講的這些都是unconditional的probability那很你在學機率的時候你就知道嘛其實很多時候是我們觀察到一些evidence我們當我們在看到某一個evidence的情況之下某一件事情發生的機率那這個機率就是所謂的conditional probabilityconditional probability條件機率所以比如說在我看到第一顆骰子是五點的情況之下那麼我兩顆骰子丟出來的點數是一模一樣的機率是多少是多少第一顆已經是五點了那其實你要讓它丟出來點數一模一樣代表你第二個骰子也必須丟出五點這件事情就會發生嘛所以說呢這個機率就是等於多少六分之一對不對所以呢在數學上呢我們通常用這個直線的這一槓代表的是givengiven第一個骰子等於五點的情況之下你會丟出一雙的機率是多少ok好那所以一樣回到這個牙醫的例子今天在某一個小鎮裡面蛀牙的機率其實根據過去醫師的統計結果呢

[2:51:24] 可能是25%這樣子好那但是呢今天有一個人走進了我的診所他說他牙痛那他有蛀牙的機率呢可能就上升到60%這樣子好那請注意喔這兩個句話這兩個機率都是對的沒有互相衝突沒有互相衝突probability只是這樣probability a given b是什麼意思呢在知道b的情況之下a的機率是多少那這機率怎麼算呢好在conditional probability裡面呢大家以前學機率應該學過這個它等於是probability b分之probability a and b的意思嘛如果要講成白話來我用白話把這個數學式子講一次在知道b的情況之下a發生的機率怎麼算那就等於是b發生的機率分之a b都發生的機率這就是把這個數學式子翻譯成白話的意思嘛對不對在知道第一顆骰子是五點的情況之下我會丟出一頓的機率是多少就等於是丟出五點的機率

[2:52:55] 分之丟出五點而且產生出一頓的機率這個就是conditional probability我這邊可以講得比較快因為大家應該都學過那把剛剛上面的式子上面轉一下你就變成是這個啊a b都發生的機率就等於是什麼b發生的機率在乘上b發生的情況之下a發生的機率那就叫做a b都發生的機率這叫product ruleok好那所以呢很快的走完這幾頁的影片這完全都是複習其實接下來也是複習啦好接下來也是複習不過呢剛好這裡是一個小小段落而且呢我們時間好像也快差不多了我們看一下slide頭上面沒有問題啦那我們最後就要走一下抽獎的環節我們用checkgpt我們才15你才發出15張汗毛牌啊確定喔1到15人不在場的就抽到也不算喔

[2:54:25] 從1到15隨機抽出6位6個數字不能重複確定喔1到15所以啊線上的同學我們成大才15個同學坐在實體的這個課堂上你看多可憐我們號稱有130個人修啊好來等一下抽到的同學呢欸你有沒有你有沒有準備紙筆要請同學來獲獎的同學要來前面填學號Email學號姓名Email等一下獲獎的同學要來超大獎是事後我們只是先抽出誰得獎因為我們要連同線上的同學總共有11位會得獎這11位裡面會再抽出隨機抽出1位那一位隨機抽出1位就是由今天的值班助教來抽的好開始誰他這有需要思考嗎我不好意思我弄太思考模式是不是來1 3 6 8 10 4 15舉手1 3 6 81 2 3 4 5 66個好這6位同學等一下來前面找助教填你的學號姓名好還有Gmail的帳號

[2:55:56] OK好那我們今天上到這邊下禮拜記得叫作業作業一然後我們會公佈作業二然後下禮拜的上課就是看影片OK因為我出國開會好線上的同學線上同學呢我們最後再讓大家喵一下線上表單的QR code但是這個線上表單呢我們只會開放到4點先讓大家喵一下好好那我們今天就上到這邊