# W3_人工智慧導論_朱威達.m4a｜長度 02:57:09｜model large-v3 on cuda

[00:00:42] 今天是9月24號,可以掃一下這個slide,等一下如果直接連到slide稍微留個幾秒鐘時間。
[00:09:57] 實際上課注意事項,首先主要是這個,我們下禮拜呢,10月1號的課會是,因為我要出國開會,
[00:10:22] 所以10月1號的課呢,我們會事先錄影的方式來呈現。
[00:10:29] 所以呢,我們會把連結放在NTU COOL的這個頁面上面。
[00:10:35] 那請大家自己去看影片。
[00:10:39] 那順帶一提,過去幾次上課,我們這已經是我們的第一、二、三、第三次上課了,再講一次。
[00:10:49] 如果你還沒有收到NTU COOL系統的邀請的同學,原因可能是因為時間差。
[00:10:58] 因為你加退選之後,你可能後來才加學了,那你們學校需要時間,會證名單送到NTU COOL的團隊。
[00:11:09] 那這件事情不會馬上發生,可能時間差,這是一個可能的原因。
[00:11:15] 另外一個就是說,你不是去收你學校的名單。
[00:11:19] 你學校的官方的帳號。
[00:11:23] 所以我的確,我在NTU COOL的系統上面,我有看到好像還有300多位同學沒有接受邀請。
[00:11:33] 所以,這個是你們要注意的事情。
[00:11:37] 然後,所以下禮拜的課會是非同步式的上課,就是看影片上課。
[00:11:45] 大家在下週四,10月1號晚上11點59分之下,
[00:11:51] 要交你們的第一個作業。
[00:11:54] 那我們在系統上面有陸陸續續有看到,有的同學,有的主別已經交上去了。
[00:12:02] 那請特別注意這個繳交的時間。
[00:12:06] 因為時間一到,系統就會自動關起來。
[00:12:10] 那我們下週四,會在線上也會同時公告你的第二個作業。
[00:12:19] OK。好。所以請大家注意。
[00:12:21] 好。那另外有一個新的事情,是本週第一次宣佈。
[00:12:27] 就是說呢,我們說我們現在上這個課呢,其實是線上線下同步上課。
[00:12:35] 所以現在在現場呢,有成大的同學。
[00:12:38] 然後呢,在線上有其他學校的同學,線上上課。
[00:12:42] 那因為是線上線下同時上課,而且我們直播之後,其實都會YouTube上面就會有影片。
[00:12:50] 好。
[00:12:51] 所以很多同學呢,就會選擇不會來實體教室上課。
[00:12:56] 好。他可能就是自己在宿舍看直播啦。
[00:13:01] 或者說他根本也沒在看,他是事後才看影片。
[00:13:05] 甚至他根本也沒有在最近就看影片。
[00:13:09] 他搞不好是到學期末、快要考試的時候,才在那邊看影片。
[00:13:13] 好。那當然這個後果你們要自己承擔啦。
[00:13:17] 好。
[00:13:18] 那但是對於我,
[00:13:19] 在實際課堂上課,
[00:13:20] 實際課堂上課的老師來講,
[00:13:22] 我今天提供這樣的服務,
[00:13:25] 尤其是成大的同學,
[00:13:27] 我們號稱有130個人休課。
[00:13:30] 一堆人說,老師拜託啊,可不可以有加簽啊,什麼怎麼樣啊。
[00:13:36] 然後呢,
[00:13:37] 然後你又沒有來上課。
[00:13:39] 你在那邊加簽什麼東西。
[00:13:41] 好。那的確啦,你說沒有啊老師,你這個本來就可以,你看影片就好了嘛。
[00:13:47] 誒,說的好像也對啦。
[00:13:49] 但是對於我在實際課堂上課的老師來講,
[00:13:52] 如果課堂上幾乎都沒什麼人的話,
[00:13:56] 那,我就覺得好像我在對空氣講話,很奇怪嘛。
[00:14:02] 那事實上呢,這個也是整個開咖課程,
[00:14:08] 所有各校開開咖課程的老師,
[00:14:12] 都一致有在反應的事情。
[00:14:15] 就是說,因為我們必須得要線上線上,
[00:14:19] 同步上課嘛。
[00:14:21] 所以上到後來呢,
[00:14:23] 自己本身那個學校的同學呢,都不來課堂上課了。
[00:14:27] 那老師上課的時候,就一個人在那邊對著空氣講話。
[00:14:31] 那反應給TICA的推動小組之後呢,
[00:14:34] 誒,他們也覺得說,誒,對,這樣子對老師的心靈受到一些傷害。
[00:14:41] 所以為了讓老師心裡好過一點,
[00:14:44] 其實TICA也提供一些資源,
[00:14:47] 希望能夠,
[00:14:49] 鼓勵大家,
[00:14:51] 實際到課堂上來上課。
[00:14:53] 因此呢,其實,
[00:14:55] 我們最近有接收到TICA的這個,
[00:14:59] 總部的這個通知,
[00:15:02] 他提供給我們一些資源,
[00:15:04] 來讓我們應用,
[00:15:07] 鼓勵大家實際來上課。
[00:15:09] 那怎麼做呢?
[00:15:10] 事實上呢,根據去年的做法,我們研習去年的做法是這樣,
[00:15:14] 包含今天,今天9月24號,
[00:15:17] 如果包含今天,一直到學期末為止,
[00:15:21] 會有我站在這邊實際上課,實體上課的次數,
[00:15:27] 應該還有10次,
[00:15:29] 今天9月24號,1,下禮拜不算,
[00:15:31] 1,2,3,4,5,6,7,8,9,10,
[00:15:37] 還會有10次,
[00:15:39] 是我會站在這裡實際上課。
[00:15:42] 那我們拿到一些算力,
[00:15:45] OK,事實上TICA,
[00:15:46] 總部給我們一些算力,
[00:15:48] 所以呢,為了鼓勵大家實際來課堂上上課,
[00:15:52] 我們有來上課的呢,
[00:15:53] 我們等一下會發號碼牌,
[00:15:56] 每個人會有一個編號,
[00:15:58] 然後我們最後,我們就會抽算力給大家。
[00:16:03] 那你說,那線上上課的同學呢,
[00:16:05] 因為我們當年也鼓勵大家同時在線上,
[00:16:09] 要真正的有在聽嘛,對不對?
[00:16:13] 所以,我們其實也會給線上的同學,
[00:16:16] 抽算力。
[00:16:17] 那我們目前規劃的是這樣,
[00:16:19] 我們每一次上課,
[00:16:21] 每一次實體的上課,
[00:16:23] 在場的成大的同學,
[00:16:25] 我們會抽出6位,OK?
[00:16:30] 那線上上課的同學,
[00:16:33] 我們會請大家,
[00:16:36] 你有在線上上課的同學,
[00:16:38] 你要上去填一個線上的表單,OK?
[00:16:43] 那我們會從有填線上表單,
[00:16:45] 而且符合某一些資格的同學呢,
[00:16:48] 我們會抽出5位。
[00:16:50] 所以這樣Totally,
[00:16:52] 就會有11位同學,
[00:16:54] 會抽到,可以拿到算力。
[00:16:57] 好,那我們其實每一次上課,
[00:17:01] 有6000塊的額度。
[00:17:03] 好,那我們的想法是,
[00:17:05] 這11位同學,其實都會拿到算力,
[00:17:08] 但是呢,我們只有,
[00:17:09] 再從這11位裡面,
[00:17:11] 又隨機抽出1位,
[00:17:13] 會拿到最大獎。
[00:17:15] 2000塊。
[00:17:16] 好,2000塊的算力。
[00:17:18] 然後呢,剩下的10位一個人,
[00:17:20] 400塊的算力。
[00:17:22] 因為我們一定要把大獎跟普獎,
[00:17:24] 那個集聚要拉開嘛。
[00:17:26] 好,鼓勵大家,
[00:17:28] 專心聽課,以及來線上上課。
[00:17:31] 好,所以等於,
[00:17:33] 現在在,在場的同學,
[00:17:35] 今天在場的同學不多太好了,
[00:17:37] 你們得到算力的機率是很高的。
[00:17:40] 好,在場的同學,等一下,
[00:17:42] 呃,其實我覺得你現在可以放下去,
[00:17:45] 就反正到時候,
[00:17:47] 我們等一下會隨機,
[00:17:48] 調出6位出來。
[00:17:50] 好,線上的同學,來。
[00:17:53] 線上的同學是這樣子的。
[00:17:56] 線上的同學呢,
[00:17:59] 你可以掃一下,
[00:18:00] 目前畫面上的這個QR code。
[00:18:04] 抽算力QR code。
[00:18:07] 那你,你如果點進去,
[00:18:10] 可以看得到畫面嗎?
[00:18:12] 什麼東西?
[00:18:15] 還在上一個QR code。
[00:18:16] 來,又來了,又來了。
[00:18:17] 又跟上次一樣。
[00:18:19] 對不起啊。
[00:18:20] 又要哪裡要換,是不是?
[00:18:22] 欸,還在slide喔。
[00:18:23] 呃,我們上次也出現這種情況。
[00:18:30] 上次怎麼解決啦?
[00:18:32] 上次有一個同學,救了我。
[00:18:34] 好像是這個,是不是?
[00:18:40] 然後,我都是整個螢幕輸出啊。
[00:18:45] 有有有,確定。
[00:18:46] 確定。
[00:18:47] 這樣子。
[00:18:48] 好,那,我再重新切換過啦。
[00:18:52] 來,這樣。
[00:18:54] 這樣。
[00:18:55] 線上的同學有沒有看到?
[00:18:57] 好,看一下。
[00:18:58] 可能要有一個時間差了。
[00:19:00] 有了嗎?
[00:19:06] 有換成抽算力這一個QR code嗎?
[00:19:09] 慢。
[00:19:10] 有了齁?
[00:19:14] 好。
[00:19:15] 線上的同學呢,
[00:19:16] 你可以掃這個QR code。
[00:19:18] 那你就會連到一個Google表單。
[00:19:20] 好,那上面就會要求。
[00:19:22] 喂。
[00:19:23] 喂。
[00:19:24] 好,上面就會要求你要輸入你的,
[00:19:27] 什麼學號啦,
[00:19:28] 姓名啊,
[00:19:29] 學校啊,
[00:19:30] 還有你的E-mail。
[00:19:31] 不過,我印象中就是,
[00:19:33] 我們會要求大家要輸入的E-mail是Gmail的帳號。
[00:19:37] 你的個人Gmail帳號。
[00:19:38] 因為臺華那邊提供的算力的廠商,
[00:19:42] 必須得要透過你的Gmail來給你算力。
[00:19:46] 好,那填的,就代表你有在聽課嗎?
[00:19:49] 不是。
[00:19:50] 我們要要求大家,
[00:19:52] 要填兩個通關密語。
[00:19:56] 你必須回答對那個通關密語,
[00:19:59] 你才能夠有具備資格,
[00:20:03] 收算力。
[00:20:04] 好,你看我們上這個課很麻煩耶,
[00:20:08] 搞得很麻煩,
[00:20:09] 還要設計這些橋段。
[00:20:11] 好,通關密語呢,
[00:20:13] 就是,我什麼時候會說出通關密語呢?
[00:20:16] 就是,不知道。
[00:20:18] 看我高興。
[00:20:19] 隨機的。
[00:20:20] 好,我突然就說出一個。
[00:20:22] 好,這通關,第一個通關密語是什麼?
[00:20:24] 好,然後就開始繼續上課。
[00:20:25] 上課,上課完之後呢,
[00:20:28] 可能又在某一個random的某一個時間,
[00:20:30] 又random的說出一個通關密語。
[00:20:32] 好,那當然在場的助教,
[00:20:34] 會幫我記下,
[00:20:35] 我今天隨便隨口說出的通關密語。
[00:20:39] 然後呢,在下午4點,
[00:20:44] 我們下課。
[00:20:46] 好,我們這整個線上表單,
[00:20:50] 就會截止。
[00:20:52] 所以說呢,助教回去之後呢,
[00:20:54] 就會從有符合資格的線上的同學裡面,
[00:21:03] 會抽出5位。
[00:21:05] 然後在場的,剛剛拿了號碼牌的同學,
[00:21:09] 會抽出6位,
[00:21:11] 可以獲得的算力。
[00:21:13] 所以總共11位。
[00:21:14] 那這11位裡面,
[00:21:15] 只有一位會拿到最大獎,
[00:21:17] 2000塊,其他都400塊。
[00:21:19] 好,就是這樣。
[00:21:25] 所以我們實在是用心良苦啦。
[00:21:28] 為了,
[00:21:30] 為了要鼓勵大家上課,
[00:21:32] 我們還要用這樣,
[00:21:33] 實在是。
[00:21:34] 好,那所以,
[00:21:37] 線上的同學,
[00:21:38] 當然你就仔細聽,
[00:21:39] 我們,我也不知道,
[00:21:40] 我什麼時候會說出通關密語。
[00:21:42] 好,那這樣子,
[00:21:44] 有沒有什麼問題?
[00:21:45] 好,我們大概交代了一下,
[00:21:48] 我們下一次,
[00:21:50] 下禮拜上課是線上,
[00:21:52] 是那個錄影上課。
[00:21:55] 然後,我們下週要交第一個作業。
[00:22:00] 好。
[00:22:02] 然後,我們會馬上公佈第二個作業。
[00:22:05] OK。
[00:22:06] 來,我確認一下線上看到的畫面,
[00:22:08] 有沒有對的。
[00:22:12] 我這滑鼠。
[00:22:17] 這樣子。
[00:22:18] 可以。
[00:22:19] 好,那我們就開始上課囉。
[00:22:21] 好,有沒有問題?
[00:22:25] 先停一下。
[00:22:34] 那個後來才看影片的同學,
[00:22:38] 當你聽到,
[00:22:40] 你看到那個線上的表單,
[00:22:42] 跟聽到通關密語之後,
[00:22:44] 你當然會知道通關密語啦,
[00:22:46] 如果你真的有在看影片的話。
[00:22:48] 但是後來,
[00:22:49] 反正我們線上的表單就已經截止了,
[00:22:52] 你填了也沒有用了。
[00:22:53] 好,我們有點煩。
[00:22:57] 上個課還要弄那麼煩。
[00:22:59] 好,我們先公佈第一個通關密語,
[00:23:02] 順便亂講。
[00:23:03] 9527,
[00:23:04] 你幫我記一下。
[00:23:07] 好,那什麼時候會說出第二個通關密語,
[00:23:09] 我也會知道。
[00:23:10] 好,來。
[00:23:12] 那我們繼續來上第四章。
[00:23:16] 好,第四章。
[00:23:19] 好,第四章呢,
[00:23:20] 我們要解的就是一個,
[00:23:22] 我們現在在做一個最佳化的動作。
[00:23:26] 那就是說呢,
[00:23:27] 我們在整個solution space裡面,
[00:23:30] 整個解空間裡面,
[00:23:32] 我們希望能夠找到一個最佳解。
[00:23:34] 什麼叫最佳解呢?
[00:23:35] 那就是,
[00:23:37] 你讓你的這個目標函數的值,
[00:23:39] 能夠越大的那樣子的解,
[00:23:42] 就是所謂的最佳解。
[00:23:44] 你可能帶入各種不同的solution,
[00:23:47] 你對應的目標函數,
[00:23:49] 可能高高低低,
[00:23:50] 有這樣子的一個變動。
[00:23:52] 那你怎麼去,
[00:23:55] 照理講以這個例子來講,
[00:23:57] 我們的最佳解就出現在,
[00:23:59] 大概在這個地方,
[00:24:00] 因為這個地方你推上去,
[00:24:02] 你對上去,
[00:24:03] 這裡就是你的最佳的目標函數的值。
[00:24:07] 所以你的最佳解,
[00:24:08] 就是在excel的這個地方。
[00:24:11] 好,那大家不要誤會喔,
[00:24:13] 最佳解呢,
[00:24:14] 我們現在雖然是用這張圖來表示,
[00:24:17] 我們的solution好像是一個數值,
[00:24:20] 一個值,
[00:24:21] 但實際上,
[00:24:22] 我們的這個state space,
[00:24:24] 可以是在一個非常高維的空間。
[00:24:27] 所以你可以帶入一組向量,
[00:24:30] 就是我的一組值,
[00:24:31] 那它是在高維的空間當中,
[00:24:33] 會對應到一個objective function value,
[00:24:37] 一個目標函數的值。
[00:24:40] 所以其實在一個這麼複雜的,
[00:24:42] 高維的空間當中,
[00:24:43] 找到哪一組向量,
[00:24:46] 是對應到最大的函數的值,
[00:24:50] 是很困難的。
[00:24:51] 好,那所以呢,
[00:24:54] 我們在接下來呢,
[00:24:55] 就介紹了一些演算法。
[00:24:58] 好,那我們很快的複習一下,
[00:25:01] 我們上週最後介紹的這個演算法,
[00:25:03] 叫做Hear Climbing,
[00:25:05] 它是一個最典型,
[00:25:07] 簡單的local search的演算法。
[00:25:10] 那為什麼叫local search呢?
[00:25:12] 因為它就是local嘛,
[00:25:15] 只看局部,
[00:25:16] 區域內的相關的解。
[00:25:20] 它的概念也很簡單,
[00:25:22] 我不知道我的解在,
[00:25:23] 最佳解在哪裡,
[00:25:24] 我就隨機的,
[00:25:26] 先從某一個solution出發,
[00:25:29] 某一個,某一個地點出發,
[00:25:32] 好,或者說,
[00:25:33] 這個stay space的某一組解出發,
[00:25:35] 這樣子,好。
[00:25:37] 從它出發之後呢,
[00:25:38] 我去看看它周圍的鄰居,
[00:25:41] 有沒有人的objective function value,
[00:25:44] 比我現在的objective function value,
[00:25:47] 來得更高,來得更好。
[00:25:49] 好,因為每一個solution,
[00:25:51] 都對應到一個objective function value,
[00:25:55] 都對待一個目標分數的值。
[00:25:57] 好,所以我去看一下我的鄰居們,
[00:25:59] 有沒有人表現得比我好。
[00:26:01] 好,那所以以我為中心,
[00:26:03] 方圓,比如說,
[00:26:05] 5公尺以內的這些鄰居們的這些解,
[00:26:09] 如果有比我好的,
[00:26:11] 好,可能有10個都比我來得好,
[00:26:16] 那我就從這10個裡面,
[00:26:17] 挑最棒的那個鄰居,
[00:26:19] 用它來取代掉我。
[00:26:21] 所以呢,我經過這一次update之後呢,
[00:26:24] 我就得到了一個相對比較好的一個解,
[00:26:27] 對不對。
[00:26:28] 好,那再從剛剛最好的那個鄰居,
[00:26:31] 現在變成我自己走到那個位置了,
[00:26:34] 以它為中心,
[00:26:35] 再去看方圓5公尺之內,
[00:26:38] 好,所謂的方圓5公尺,
[00:26:40] 只是一個比喻,
[00:26:42] 其實你不同的問題,
[00:26:43] 你的鄰居的利益會不一樣。
[00:26:45] OK,好,那你去看一下你的鄰居,
[00:26:49] 再看看說,
[00:26:50] 唉,有沒有比他更好的,
[00:26:52] 唉,有比他更好的,
[00:26:53] 就挑最好的那一個,
[00:26:55] 用它來取代掉我原本的位置。
[00:26:57] 就這樣,一直往下做下去,
[00:26:59] 看你願意做幾步,
[00:27:01] 比如說你可以做1萬步,
[00:27:03] 10萬步,
[00:27:04] 或者是說,
[00:27:05] 你可以設定一些終止的條件,
[00:27:07] 比如說,
[00:27:08] 唉,後來呢,
[00:27:09] 我用鄰居來update掉我之後呢,
[00:27:12] 我的objective function value,
[00:27:14] 變動,
[00:27:15] 微乎其微,
[00:27:16] 那我就知道說,
[00:27:17] 差不多,
[00:27:18] 我已經找不到其他的,
[00:27:19] 這個,
[00:27:20] 更好的企業了,
[00:27:21] 你就可以停了。
[00:27:23] 這樣子的做法呢,
[00:27:24] 就叫做Heel Climbing,
[00:27:26] 好,爬山啦,
[00:27:28] 那你可以想,
[00:27:29] 比如說,
[00:27:30] 我假設我隨機,
[00:27:31] 我從這個點出發,
[00:27:32] 我從這一組企業出發,
[00:27:34] 它的objective function value呢,
[00:27:36] 是在這裡嘛,
[00:27:37] 好,
[00:27:38] 那我去看一下它的鄰居,
[00:27:40] 以目前來講,
[00:27:41] 它的鄰居,
[00:27:42] 其實就是以這個領域作為中心,
[00:27:43] 左右附近的人嘛,
[00:27:45] 唉,我就發現說,
[00:27:46] 唉,這個鄰居,
[00:27:48] 這個鄰居表現最好啊,
[00:27:50] 所以我就用它來取代掉我,
[00:27:53] 好,這樣,
[00:27:54] 然後以此類推,
[00:27:55] 我再以它為核心,
[00:27:57] 我去左右看,
[00:27:58] 又發現右邊一點,
[00:28:00] 又有一個更棒的鄰居,
[00:28:02] 以此類推,
[00:28:03] 一直走到,
[00:28:04] 比如說這個點為止,
[00:28:06] 好,
[00:28:07] 也就是說,
[00:28:08] 我以它為中心,
[00:28:09] 往左右看,
[00:28:10] 發現沒有任何鄰居,
[00:28:11] 比我表現得更好了,
[00:28:13] 那我就回傳這一組答案,
[00:28:16] 好,
[00:28:17] 那這個做法,
[00:28:18] 很顯然的,
[00:28:19] 你可以發現,
[00:28:20] 可能有一個問題啦,
[00:28:21] 就是它可能會卡在local maximum,
[00:28:25] 對不對,
[00:28:26] 因為你到了這個小山丘這裡了,
[00:28:28] 你這個周圍繞一圈一看,
[00:28:32] 發現沒有任何鄰居比你更強的,
[00:28:35] 那你就覺得你自己是最強的,
[00:28:37] 好,
[00:28:38] 那你就卡在local maximum,
[00:28:40] 但事實上以我們,
[00:28:41] 我們現在如果從上帝的視角,
[00:28:44] 遠遠的來看,
[00:28:45] 其實我們知道真正的最佳解在這裡啦,
[00:28:48] OK,
[00:28:49] 好,
[00:28:50] 那你說,
[00:28:51] 不對啊老師,
[00:28:52] 那我對不對,
[00:28:53] 我一看,
[00:28:54] 我就知道最佳解在這裡,
[00:28:55] 我幹嘛要用什麼local search,
[00:28:56] 原因就是,
[00:28:57] 當你實際的解一個真正的問題的時候,
[00:29:00] 你根本就沒有上帝視角,
[00:29:02] 你根本就不知道,
[00:29:03] 你整個objective function value的curve,
[00:29:06] 這個曲線,
[00:29:07] 或這個復長的曲面長什麼樣子,
[00:29:09] 你根本就不知道,
[00:29:11] 好,
[00:29:12] 所以你就從這個local search這裡開始來做,
[00:29:16] 好,
[00:29:17] 那這個我們就不再贅述啦,
[00:29:20] 所以它有可能會卡在local maximum,
[00:29:24] 那所以呢,
[00:29:26] 你可以為這個所謂的hear climbing演算法,
[00:29:29] 做一點變形啊,
[00:29:31] 有沒有可能我盡可能的減少它,
[00:29:34] 卡在local maximum,
[00:29:36] 的狀態的次數呢,
[00:29:39] 所以後來就有一些變形,
[00:29:41] 比如說stochastic hear climbing,
[00:29:44] 它的意思就是說,
[00:29:45] 我今天我看一下我周圍的鄰居,
[00:29:48] 剛剛最原始的版本就是,
[00:29:50] 我用我最好的鄰居來取代掉我,
[00:29:52] OK,
[00:29:53] 好,
[00:29:54] 那我有沒有可能,
[00:29:56] 我根本,
[00:29:57] 比如說我周圍有十個鄰居,
[00:29:59] 都表現得比我來得好,
[00:30:00] 我是隨機的從這十個表現比我好的鄰居裡面,
[00:30:04] 挑一個來取代掉我,
[00:30:06] 我不是永遠都挑最好的那一個,
[00:30:09] 也就是說你不要走那個貪婪的,
[00:30:13] 最貪婪的路線,
[00:30:15] 因為說不定你取到一個,
[00:30:17] 你選擇一個表現第三好的那個鄰居,
[00:30:21] 他說不定他看到的東西,
[00:30:23] 他看到的視野,
[00:30:24] 比起你在現階段你挑最好的那個鄰居,
[00:30:27] 看到的是更好的風景,
[00:30:30] 那所以你如果選擇第三好的那一個,
[00:30:33] 再往外去找,
[00:30:34] 說不定他會找到更好的,
[00:30:36] 而且不知道也不保證,
[00:30:39] 所以我這裡並沒有保證說,
[00:30:42] 這個Stochastic Hill Climbing,
[00:30:44] 表現的一定會比基礎的Hill Climbing來得好,
[00:30:47] 不見得,
[00:30:48] 要看問題而定,
[00:30:51] 那也有另外一種變形,
[00:30:53] 就是First Choice,
[00:30:55] 就是我找到的鄰居裡面,
[00:30:57] 我第一個找到比我表現來得好的那個鄰居,
[00:31:02] 我就用他來取代掉我,
[00:31:04] 我不用把方圓,
[00:31:05] 5公尺內的那100個鄰居全部都掃完一次,
[00:31:09] 我只要找到第一個表現比我好的,
[00:31:11] 我就走過去了,
[00:31:13] 這叫First Choice,
[00:31:15] 那再來就是說,
[00:31:16] 你不管是Stochastic,
[00:31:17] First Choice,
[00:31:18] 或一般的,
[00:31:19] 你都有可能會卡在,
[00:31:21] 都還是有可能卡在Local Max,
[00:31:24] 那原因,
[00:31:27] 除了演算法本身的侷限之外,
[00:31:29] 還跟你一開始,
[00:31:31] 你是落在這個崎嶇不平的,
[00:31:34] 這整個山脈的哪個地方有關,
[00:31:38] 所以有另外一個就是說,
[00:31:40] 那我可不可以做很多次的Hill Climbing,
[00:31:43] 每次出發的地點,
[00:31:45] 隨機的不一樣,
[00:31:49] 那這個叫做Random Restart的Hill Climbing,
[00:31:53] 那這是我們上次講的最後的內容,
[00:31:58] 那再進一步一點,
[00:32:00] 現在演算法叫做Semantic Unnealing,
[00:32:03] Unnealing這個字就是退夥,
[00:32:07] Semantic Unnealing就是模擬退夥,
[00:32:10] 這什麼意思呢,
[00:32:11] 在一些,
[00:32:13] 比如說我們看一些古裝劇,
[00:32:17] 舊的,
[00:32:18] 或者是電影,
[00:32:20] 以前古時候的人,
[00:32:27] 不是會在那邊打鐵嗎,
[00:32:29] 比如說他要鑄造出一把劍,
[00:32:32] 有沒有,
[00:32:33] 那他就會把那個鐵燒熱之後呢,
[00:32:36] 在那邊打,
[00:32:37] 然後塑形,
[00:32:38] 原因是什麼,
[00:32:39] 原因是你燒熱之後呢,
[00:32:41] 他的這個,
[00:32:42] 這個,
[00:32:44] 這個裡面的這個分子啊,
[00:32:46] 就會比較鬆動,
[00:32:47] OK,
[00:32:48] 那你有機會透過外力去塑造他的形狀,
[00:32:52] OK,
[00:32:53] 然後呢,
[00:32:54] 等你塑造差不多這個形狀之後呢,
[00:32:56] 然後是不是又給他降溫,
[00:32:57] 讓他有冷熱冷熱的這個變動,
[00:33:00] 所以我們知道說,
[00:33:01] 當溫度高的時候,
[00:33:03] 分子之間比較容易變動,
[00:33:05] 比較容易塑形,
[00:33:07] 溫度低的時候,
[00:33:08] 他的整個結構就固定了,
[00:33:11] 好,
[00:33:12] 那Simulated Aligning呢,
[00:33:13] 就是有一點想要模仿,
[00:33:17] 這樣子的一個程序,
[00:33:19] 好,
[00:33:20] 他什麼概念呢,
[00:33:21] 他其實跟Heal Academy非常的像,
[00:33:23] 我們看一下這個修道口,
[00:33:25] 好,
[00:33:26] 呃,
[00:33:27] 今天一樣,
[00:33:28] 我隨機從某一個Solution出發,
[00:33:32] 那我去看一下週圍的鄰居,
[00:33:34] 好,
[00:33:35] 所以我現在的Objective Function Value的詞,
[00:33:37] 叫做Current.Value,
[00:33:39] 就是我現在這一組解,
[00:33:40] 好,
[00:33:41] 我的目標函數的詞,
[00:33:44] 叫Current.Value,
[00:33:45] 我的鄰居,
[00:33:46] 某一個鄰居,
[00:33:48] 某一個鄰居,
[00:33:49] 比如說我看到的第一個鄰居,
[00:33:51] Next.Value,
[00:33:53] 他的Objective Function Value的詞是這樣,
[00:33:56] 我把鄰居的函數值減掉,
[00:33:59] 我的函數值,
[00:34:00] 叫做Delta1,
[00:34:02] OK,
[00:34:03] 可以吧,
[00:34:04] 好,
[00:34:05] 如果Delta1大於0,
[00:34:06] 什麼意思,
[00:34:07] 就是鄰居表現得比我好嘛,
[00:34:10] 如果鄰居表現得比我好,
[00:34:12] 那我就用這個鄰居Next,
[00:34:14] 來取代掉我,
[00:34:17] 這樣可以嗎,
[00:34:19] 對目前為止,
[00:34:20] 完全跟剛剛的那個First Choice的Hear Climbing,
[00:34:24] 一模一樣,
[00:34:25] 如果鄰居表現得比我好,
[00:34:27] 我就用他來取代掉我,
[00:34:29] 好,
[00:34:30] 再來,
[00:34:31] 那如果鄰居表現得比我不好呢,
[00:34:33] 也就是說當Delta1等於0,
[00:34:36] 或小於等於0的時候,
[00:34:38] 當Delta1小於等於0的時候,
[00:34:40] 我依舊有一定的機率,
[00:34:43] 用鄰居來取代掉我,
[00:34:46] 也就是說在Seminating and Nearing的,
[00:34:49] 這個演算法裡面,
[00:34:51] 我有可能用一個比較爛的解答,
[00:34:56] 來取代掉,
[00:34:57] 目前這個比較好的解答,
[00:35:00] 它的原因就在於,
[00:35:02] 說不定,
[00:35:03] 我退一步海闊天空嘛,
[00:35:06] 我先用一個暫時稍微爛一點的,
[00:35:09] 的解答,
[00:35:12] 來取代掉我,
[00:35:13] 我走過去之後,
[00:35:14] 說不定那邊的視野更好,
[00:35:18] 這樣懂我意思嗎?
[00:35:20] 這有點像是,
[00:35:21] 以後大家畢業,
[00:35:22] 一開始出去找工作,
[00:35:24] 你是不是永遠都要,
[00:35:26] 你的第一份工作是不是都一定要,
[00:35:29] 去給你薪水最高的那個工作,
[00:35:32] 不見得,
[00:35:33] 說不定你是選擇,
[00:35:35] 第二或第三高的某一個工作,
[00:35:38] 說不定那個地方,
[00:35:40] 雖然是一個小公司,
[00:35:41] 但是未來發展的潛力可能更高,
[00:35:44] 或怎麼樣,
[00:35:45] 所以這裡的概念就是說,
[00:35:47] 我會有一定的一個機率,
[00:35:49] 去接受一個比較爛的鄰居,
[00:35:52] 來取代掉我,
[00:35:53] 那現在的重點就在於說,
[00:35:55] 那這個機率怎麼設定?
[00:35:57] 這個機率怎麼設定?
[00:35:58] 我們可以看一下,
[00:35:59] 這個機率叫設定成,
[00:36:01] Exponential Delta E over T,
[00:36:04] 它是一個指數,
[00:36:06] 然後呢,
[00:36:07] Delta E over T,
[00:36:08] 首先我們知道,
[00:36:09] 會走到這一行,
[00:36:10] 一定代表Delta E是什麼?
[00:36:12] 是負的,對不對?
[00:36:14] 所以這其實是一個,
[00:36:16] Exponential的一個負的指數次法,
[00:36:20] 代表它是什麼?
[00:36:22] Exponential,
[00:36:24] 它其實是,
[00:36:26] 你知道Exponential,
[00:36:28] 比如說Exponential負二,
[00:36:30] 其實就是什麼?
[00:36:31] Exponential二次方分之一的意思吧,
[00:36:34] 好,
[00:36:35] 那我們來看一下,
[00:36:37] Delta E,
[00:36:38] 如果負的越多,
[00:36:40] 代表這個鄰居表現得比我爛,
[00:36:47] 而且爛很多,
[00:36:48] 那它的Delta E就會負很多,
[00:36:51] 對不對?
[00:36:52] 如果Delta E負很多,
[00:36:54] 這整個值算出來就,
[00:36:57] 怎麼樣?
[00:36:58] 比較大還是比較小?
[00:36:59] 就比較小,
[00:37:03] 這整個值,
[00:37:04] 因為是,
[00:37:05] 比如說Exponential負二次方,
[00:37:07] 跟Exponential負零點五次方,
[00:37:09] 哪一個數字比較小?
[00:37:11] Exponential負二次方,
[00:37:13] 數字比較小,
[00:37:15] 這樣聽懂嗎?
[00:37:19] 可以吧,
[00:37:20] Exponential可以吧,
[00:37:21] 指數為理嘛,
[00:37:22] 所以今天翻一層白話的意思是,
[00:37:25] 如果鄰居比我爛很多,
[00:37:30] 我用它來取代掉,
[00:37:32] 我的機率就很低,
[00:37:35] 就這個意思,
[00:37:37] 相較之下,
[00:37:38] 如果Delta E,
[00:37:40] 只是負一點點,
[00:37:42] 比如說負0.001,
[00:37:43] 這樣子,
[00:37:44] 代表什麼?
[00:37:45] 代表這個鄰居,
[00:37:46] 雖然表現得比我差,
[00:37:48] 但是其實只差一點點,
[00:37:50] 好,所以呢,
[00:37:51] 這裡的機率就是Exponential,
[00:37:53] 負0.001,
[00:37:56] 除上大T,
[00:37:58] 那相較之下,
[00:37:59] 這個就是一個比較大的機率,
[00:38:01] 當然我們都知道,
[00:38:02] 機率一定都在Delta E之間嘛,
[00:38:05] 所以我們這是相對的,
[00:38:06] 相較之下,
[00:38:08] 如果一個,
[00:38:09] 跟我比起來,
[00:38:10] 沒有那麼差的鄰居,
[00:38:12] 我就有比較高的機率,
[00:38:14] 會用它來取代掉我,
[00:38:22] 表現得比我好,
[00:38:23] 那沒什麼好說的,
[00:38:24] 那就是剛剛上面第一條路,
[00:38:26] 我一定會用那個比較好的鄰居,
[00:38:29] 來取代掉我,
[00:38:30] OK,好,
[00:38:31] 那這是第一個特性,
[00:38:33] 第二個特性是,
[00:38:35] 你除上大T,
[00:38:37] 這什麼意思?
[00:38:38] 好,這個其實才是Semitic Annuity,
[00:38:41] 最主要的一個,
[00:38:43] 的一個參數,
[00:38:45] 這個大T啊,
[00:38:46] 指的就是溫度,
[00:38:48] 在一般來講呢,
[00:38:49] 它會,
[00:38:51] 這個溫度呢,
[00:38:53] 會隨著時間,
[00:38:54] 一開始的溫度是高的,
[00:38:56] 後來呢,
[00:38:57] 就慢慢慢慢降溫,
[00:38:59] 所以這個大T的指會越來越小,
[00:39:02] 好,那你想一下喔,
[00:39:04] 在Delta E不變的情況之下,
[00:39:07] T如果大,
[00:39:09] 這是你指,
[00:39:10] Delta E不變的情況之下,
[00:39:14] T如果越大,
[00:39:15] 我整個指數的數字就越小,
[00:39:20] 好,
[00:39:23] 越小,
[00:39:24] 數字的部分就越小,
[00:39:25] 但是不要忘記喔,
[00:39:26] 這個指數,
[00:39:27] 是負的,
[00:39:29] 那個數字,
[00:39:31] 所以說呢,
[00:39:32] 如果你這個指數的數字越小,
[00:39:35] Exponential負越小,
[00:39:38] 就代表,
[00:39:39] 這個機率算起來就越大,
[00:39:42] 的意思,
[00:39:43] 可以嗎?
[00:39:44] 這簡單的數學,
[00:39:45] 好,如果你聽起來有點吃力,
[00:39:48] 你稍微看一下Exponential的定義,
[00:39:50] 好,
[00:39:51] 或者指數的定義,
[00:39:52] 好,
[00:39:53] 所以這句話翻成白話什麼意思?
[00:39:55] 這整個演算法一開始在跑的時候,
[00:39:58] 溫度比較高,
[00:40:01] 所以呢,
[00:40:02] 這一開始,
[00:40:03] 我會比較傾向於,
[00:40:05] 用比較爛的鄰居來取代掉我,
[00:40:10] 我比較願意,
[00:40:11] 用比較高的機率,
[00:40:13] 用比較爛的鄰居來取代掉我,
[00:40:16] 當演算法一開始跑的時候,
[00:40:19] 那你看啊,
[00:40:20] 這個是一個Fall Loop嘛,
[00:40:21] T的,
[00:40:22] 從1到無限大,
[00:40:23] 對不對?
[00:40:24] 好,
[00:40:25] 隨著你的T,
[00:40:26] 隨著你的時間一直往下走走走,
[00:40:28] 當你這個演算法已經跑了100個Iteration,
[00:40:32] 或者1000個Iteration,
[00:40:33] 隨著Iteration數量增加,
[00:40:35] 我的溫度就會急劇的下降,
[00:40:39] 當大T這個值,
[00:40:41] 越來越小的時候,
[00:40:45] Delta1除上T,
[00:40:48] 就越大,
[00:40:50] 也就是說Exponential,
[00:40:51] 負的越大次方,
[00:40:54] 那機率,
[00:40:55] 就是什麼?
[00:40:56] 越小,
[00:40:57] 可以嗎?
[00:41:00] 好,
[00:41:01] 所以翻譯成白話的意思就是說,
[00:41:03] 隨著你的這個演算法,
[00:41:04] 跑了很多很多次的Iteration之後呢,
[00:41:07] 我就越來越不願意,
[00:41:10] 用比較爛的鄰居來取代掉我的意思,
[00:41:14] 這個就是Seminatic的年齡,
[00:41:16] 啊你如果覺得這個很難記,
[00:41:22] 你就想,
[00:41:23] 這個跟我們的人生是一樣的嘛,
[00:41:25] 對不對?
[00:41:26] 在座的年輕的同學們,
[00:41:28] 你們現在還年輕,
[00:41:30] 不要怕失敗,
[00:41:31] 對不對?
[00:41:32] 你們應該要勇於冒險,
[00:41:34] 所以呢,
[00:41:35] 你們應該有越高的機率,
[00:41:39] 願意去接受一個,
[00:41:41] 越Risky,
[00:41:43] 越有冒險性的一個選擇,
[00:41:48] 投資理財也一樣嘛,
[00:41:50] 比如說你們現在,
[00:41:51] 理論上你們還年輕,
[00:41:53] 對不對?
[00:41:54] 你們應該可以去投,
[00:41:55] 比較高風險性的資產,
[00:41:59] 等到已經快要退休了,
[00:42:02] 老年人快要退休了,
[00:42:03] 他投的資產,
[00:42:04] 就應該要風險性比較低的,
[00:42:06] 因為他比較不能夠接受,
[00:42:08] 用比較爛的結果,
[00:42:10] 來取代掉現有的結果嘛,
[00:42:12] 所以隨著生命,
[00:42:14] 隨著人生也是一樣,
[00:42:15] 一開始溫度比較高,
[00:42:17] 你可以比較接受比較爛的結果,
[00:42:19] 因為蹲下是為了跳起來,
[00:42:22] 你可以這麼說,
[00:42:23] 好,
[00:42:24] 只要你年紀大了,
[00:42:26] 你就比較不願意,
[00:42:28] 用比較爛的選擇,
[00:42:30] 來取代掉你現在的選擇,
[00:42:33] 這樣懂我意思嗎?
[00:42:34] 就跟人生的哲理是一樣的,
[00:42:36] 這個就是Seminity Unlimited,
[00:42:38] 講完了,
[00:42:40] 就這樣,
[00:42:41] 那這個請大家自己去看,
[00:42:43] 這就是Seminity Unlimited的概念,
[00:42:45] 好,
[00:42:49] 那接下來,
[00:42:50] 繼續進階,
[00:42:52] 下一個叫做Local Bean Search,
[00:42:54] 好,
[00:42:55] 剛剛前面的Hear Climbing,
[00:42:57] 跟Seminity Unlimited,
[00:42:59] 一次就是看一組姐,
[00:43:02] 比如說我以一個姐為中心,
[00:43:04] 我去看周圍的鄰居,
[00:43:05] 然後去決定要不要取代,
[00:43:07] 對不對,
[00:43:08] 好,
[00:43:09] 那Local Bean Search是說,
[00:43:10] 我為什麼一次只看一個姐,
[00:43:12] 我可不可以一次就看K個姐啊,
[00:43:14] 對不對,
[00:43:15] 有沒有,
[00:43:16] 我在這個State Space裡面,
[00:43:17] 我一次就灑K個,
[00:43:19] Random灑,
[00:43:20] K個不同的點嘛,
[00:43:21] 對不對,
[00:43:22] 那以每一個點為中心,
[00:43:23] 去看一下週圍的鄰居嘛,
[00:43:25] 一次看K個,
[00:43:27] 好,
[00:43:28] 那所以說呢,
[00:43:29] It begins with K,
[00:43:30] Randomly generated state,
[00:43:32] 好,
[00:43:33] 那以每一個State為中心,
[00:43:36] 我去看,
[00:43:39] 第一個人,
[00:43:40] 以第一個人為中心,
[00:43:41] 去看一下他周圍的鄰居,
[00:43:43] 然後呢,
[00:43:44] 用最好的來取代掉他,
[00:43:45] 第二組姐,
[00:43:46] 我以他為中心,
[00:43:47] 看一下週圍的鄰居,
[00:43:49] 對不對,
[00:43:50] 不對,
[00:43:51] 我剛剛講太誇張,
[00:43:52] 應該是這樣講,
[00:43:53] 我第一個,
[00:43:54] Random的solution,
[00:43:56] 我去看一下他周圍的鄰居,
[00:43:58] 每一個,
[00:43:59] 我都可以知道他的objective function value嘛,
[00:44:02] 第二個,
[00:44:03] 以他為中心,
[00:44:04] 看一下他的鄰居,
[00:44:05] 第三個,
[00:44:06] 我也看一下他的鄰居,
[00:44:07] 假設,
[00:44:08] 每一個人,
[00:44:09] 都看10個鄰居,
[00:44:10] 那我現在一開始就隨機灑,
[00:44:12] 10個可能的解,
[00:44:14] 所以呢,
[00:44:15] Totally,
[00:44:16] 你是不是會有100個鄰居啊,
[00:44:18] 對不對,
[00:44:19] 因為一個人就看10個鄰居,
[00:44:21] 10個人就看,
[00:44:22] 10乘10,
[00:44:23] 100個鄰居,
[00:44:24] 他再從這100個,
[00:44:27] 所有官看到的鄰居裡面,
[00:44:30] 挑10個最好的出來,
[00:44:33] 這個就叫做Local Research,
[00:44:36] 講完了,
[00:44:39] 就這麼簡單,
[00:44:40] 好,
[00:44:41] 那,
[00:44:42] 這麼簡單,
[00:44:43] 你會想說,
[00:44:44] 這個跟,
[00:44:46] 這個跟我剛剛那個什麼,
[00:44:48] Random Restart Here Climbing,
[00:44:50] 有什麼不一樣,
[00:44:51] 剛剛Random Restart Here Climbing是說,
[00:44:53] 我隨機挑一個點,
[00:44:55] 以它為中心,
[00:44:56] 去看周圍的鄰居,
[00:44:58] 對不對,
[00:44:59] 然後一直跑Here Climbing,
[00:45:01] 好,
[00:45:02] 跑完,
[00:45:03] 得到一個最佳解,
[00:45:05] 啊,
[00:45:06] 我再隨機又再挑一個,
[00:45:07] 又再跑跑跑,
[00:45:08] 找到一個最佳解,
[00:45:09] 好,
[00:45:10] 那跟剛剛聽起來很像啊,
[00:45:11] 好,
[00:45:12] 我跟你講,
[00:45:13] 差別在哪裡,
[00:45:14] 差別在於Local Research,
[00:45:17] 它其實有不同Solution之間的溝通,
[00:45:23] 再講一次,
[00:45:25] 再講一次,
[00:45:26] 怎麼樣一個溝通方式呢,
[00:45:28] 它其實它的意思就是說,
[00:45:29] 比如說我今天,
[00:45:30] 我隨機灑十個,
[00:45:33] 我為了避免重複,
[00:45:35] 我隨機灑五個Solution好了,
[00:45:39] 我第一個Solution,
[00:45:40] 以第一個Solution為中心,
[00:45:42] 我去看周圍的十個鄰居,
[00:45:46] 好,
[00:45:47] 然後第二個Solution,
[00:45:48] 我也去看周圍,
[00:45:49] 找十個鄰居,
[00:45:50] 所以Totally我是不會找到五十個,
[00:45:53] 對不對,
[00:45:54] 這五十個裡面,
[00:45:56] 我要挑最好的五個出來,
[00:46:00] 有可能喔,
[00:46:01] 有可能我挑出來的這五個,
[00:46:04] 全部來自剛剛的第一個Solution的那十個鄰居裡面,
[00:46:13] 這樣大家懂我意思嗎,
[00:46:15] 它跟剛剛一開始那個Random Restart Here Climbing,
[00:46:19] 是不一樣的,
[00:46:21] 因為它是把所有這五個Random Start,
[00:46:26] Random State,
[00:46:28] 開頭的這五十個鄰居是一起同胞,
[00:46:31] 一起去PK得到最好的那五個,
[00:46:37] 好,
[00:46:38] 那當然也有可能說,
[00:46:39] 我是從第一個Random State的十個鄰居裡面挑出兩個,
[00:46:44] 然後呢,
[00:46:45] 第二個Random State挑出一個,
[00:46:46] 第三個又挑出兩個,
[00:46:48] 這樣去抽到所謂的最好的五個,
[00:46:50] 也是有可能的,
[00:46:52] 所以呢,
[00:46:53] 這一段的話,
[00:46:54] 這字比較多,
[00:46:55] 但講的就是在講這個意思,
[00:46:58] 你會覺得說呢,
[00:46:59] 這個做法好像Seem to Nothing More Than Running K Random Restart,
[00:47:04] 但其實不一樣,
[00:47:05] 好,
[00:47:06] 在Random Restart,
[00:47:07] 每一次Restart,
[00:47:09] 都是一個獨立的開始,
[00:47:11] 那如果是Local Bean Search呢,
[00:47:13] Useful Information is Passed Among the Parallel Search Threat,
[00:47:18] 好,
[00:47:19] OK,
[00:47:20] 好,
[00:47:21] 那這個,
[00:47:22] 所以,
[00:47:23] 嚴格來講,
[00:47:24] Local Bean Search啊,
[00:47:26] 它其實不是一種,
[00:47:28] 演算法,
[00:47:29] 它其實是一種,
[00:47:30] 搜尋策略啦,
[00:47:32] 你今天,
[00:47:36] 我隨機灑五個Random State出去,
[00:47:39] 接下來你要怎麼運作,
[00:47:41] 你可以搭配Hear Climbing來運作,
[00:47:43] 你可以搭配Symmetric Engineering來運作,
[00:47:46] 所以Local Bean Search其實是一個,
[00:47:51] 一個策略,
[00:47:53] 一個策略這樣子,
[00:47:55] 好,
[00:47:56] 那你也可以有一些變形啊,
[00:47:58] 比如說今天我,
[00:48:00] 不是永遠取,
[00:48:02] 這五十個,
[00:48:04] 鄰居裡面的最好的那五個出來,
[00:48:06] 你可能是隨機挑五個出來,
[00:48:09] 好,
[00:48:11] 或者也不是隨機,
[00:48:12] 而是根據某一個機率,
[00:48:14] 來挑五個出來,
[00:48:16] 好,
[00:48:17] 那這機率怎麼設定呢,
[00:48:18] 那就是看,
[00:48:19] 一樣嘛,
[00:48:20] 這邊跟剛剛Symmetric Engineering很像,
[00:48:22] 就是,
[00:48:23] 跟我目前現有的Solution,
[00:48:27] 差不多的,
[00:48:29] 我挑的機率就越高嘛,
[00:48:31] 好,
[00:48:32] 甚至贏越多的,
[00:48:33] 我挑的機率就更高,
[00:48:35] 甚至是必挑嘛,
[00:48:37] 好,
[00:48:38] 那這個就叫做Stochastic的Bean Search,
[00:48:41] 好,
[00:48:42] 那大家不要覺得這個Local Bean Search,
[00:48:44] 這個好像是,
[00:48:45] 老Coco,
[00:48:46] 現在沒有人在用演算法,
[00:48:47] 現在你,
[00:48:48] even你是在訓練Deep Learning的模型,
[00:48:51] 有的時候你的一個訓練策略裡面,
[00:48:53] 你就會看到,
[00:48:54] 它是講Bean Search,
[00:48:56] Bean Search,
[00:48:57] 所謂的Bean Search,
[00:48:58] Bean就是一束,
[00:49:00] 一束的意思,
[00:49:01] 就是一次看一堆結的意思,
[00:49:03] 一束,
[00:49:05] 把什麼稻草捆成一束,
[00:49:07] 的那個Bean Search,
[00:49:09] OK,
[00:49:11] 這樣可以嗎?
[00:49:12] 好,
[00:49:13] 所以我們用一頁,
[00:49:14] 把Local Bean Search的策略講完了,
[00:49:17] 再來下一個,
[00:49:22] Genetic Algorithm,
[00:49:24] 基因演算法,
[00:49:26] 一樣,
[00:49:27] 其實基因演算法呢,
[00:49:28] 它可以是一本書,
[00:49:30] 但是我們打算用三頁頭影片,
[00:49:33] 講談基因演算法,
[00:49:36] 基因演算法,
[00:49:37] 它其實是Stochastic Bean Search的一個變形,
[00:49:42] 好,
[00:49:43] 那你一聽你就知道,
[00:49:44] OK,
[00:49:45] 它是Bean Search的變形,
[00:49:47] 代表它一次會看一堆結的意思,
[00:49:50] 然後呢,
[00:49:51] 前面又加一個Stochastic,
[00:49:52] 就代表說,
[00:49:53] 它有這個隨機性,
[00:49:55] 對吧,
[00:49:56] 好,
[00:49:57] 那基因演算法呢,
[00:49:59] 它其實是受到,
[00:50:01] 這個,
[00:50:02] 演化論的這個啟發,
[00:50:05] 好,
[00:50:06] 它的概念是這樣,
[00:50:07] 一樣的,
[00:50:08] 基因演算法呢,
[00:50:09] 它會從K個Random Generated State出發,
[00:50:14] 好,
[00:50:15] 等於說它一開始呢,
[00:50:16] 就會隨機出K個結,
[00:50:19] 好,
[00:50:20] 那在基因演算法裡面呢,
[00:50:22] 它稱呼這K個結呢,
[00:50:24] 稱為是一個Population,
[00:50:26] 一個群體,
[00:50:28] 好,
[00:50:29] 一個群體,
[00:50:30] 好,
[00:50:31] 一個結,
[00:50:32] 我們又稱呼它這樣,
[00:50:33] 一個一個個體,
[00:50:36] OK,
[00:50:37] 這個群體裡面有一個個個體,
[00:50:39] 每一個個體,
[00:50:40] 其實就是一個結的意思,
[00:50:43] 好,
[00:50:44] 那比較特別的事情是,
[00:50:46] 它為了要套用這整個染色體,
[00:50:51] 演化的這整個過程,
[00:50:53] 好,
[00:50:54] 所以它會把它的Solution呢,
[00:50:56] 都表達成一個字串,
[00:51:00] 一個序列,
[00:51:01] 一個字串,
[00:51:02] 好,
[00:51:03] 然後這個字串通常都會定義在,
[00:51:06] 一個現有的這個字母,
[00:51:09] Alphabet裡面,
[00:51:10] 好,
[00:51:11] 等一下我們會看到一些例子,
[00:51:12] 好,
[00:51:13] 那一般來講,
[00:51:14] 這個Alphabet,
[00:51:15] 或者這個,
[00:51:16] 常常是隻有0或1,
[00:51:17] 所以一個Solution表達成,
[00:51:19] 一堆011010100,
[00:51:22] 這樣子的一個Binary String,
[00:51:24] 這是一個常見的一個情況,
[00:51:26] 另外一種常見的情況是,
[00:51:28] 我可能是定義好,
[00:51:30] 這些字母,
[00:51:32] 來表達一組結,
[00:51:34] 這樣子,
[00:51:35] 好,
[00:51:36] 那講這樣子,
[00:51:37] 講這樣子,
[00:51:38] 好像搞不清楚你在講什麼,
[00:51:39] 我們直接舉一個例子,
[00:51:41] 八皇后問題,
[00:51:43] 大家還記得吧,
[00:51:44] 好,
[00:51:45] 在這個八乘八的棋盤裡面呢,
[00:51:47] 我要放八隻皇后,
[00:51:49] 對不對,
[00:51:50] 然後希望八隻放上去之後呢,
[00:51:52] 彼此之間沒有互相衝突,
[00:51:54] 好,
[00:51:55] 那我怎麼放,
[00:51:56] 我現在,
[00:51:57] 我就先隨便放,
[00:51:58] 假設我的,
[00:51:59] 我的這個限制就是說,
[00:52:02] 我一個Colon,
[00:52:03] 只能放一隻皇后,
[00:52:05] 所以,
[00:52:06] 我八個Colon,
[00:52:07] 我就放八隻皇后,
[00:52:09] 所以呢,
[00:52:10] 我就把八隻皇后放好之後,
[00:52:13] 這個盤面,
[00:52:15] 它基本上就是一個結,
[00:52:17] 它是一個Solution,
[00:52:18] 只是,
[00:52:19] 這個Solution是一個蠻爛的Solution,
[00:52:21] 因為我們可以蠻輕易的看出,
[00:52:23] 有好多衝突的地方嘛,
[00:52:25] But anyway,
[00:52:26] 它就是一個Solution,
[00:52:27] 一個Possible的Solution,
[00:52:29] 如何來表達這個Solution呢,
[00:52:31] 我們可以設計說,
[00:52:33] 我們根據它在盤面上的位置,
[00:52:37] 比如說,
[00:52:38] 今天第一隻皇后,
[00:52:39] 是在第一個Colon的由下往上數,
[00:52:41] 第三個位置,
[00:52:43] 第二隻皇后,
[00:52:44] 就是第二個Colon的,
[00:52:46] 第二個這個,
[00:52:47] 由下往上的第二個位置,
[00:52:49] 以此類推,
[00:52:50] 所以我可以把這個盤面,
[00:52:51] 表達成,
[00:52:52] 3,
[00:52:53] 2,
[00:52:54] 7,
[00:52:55] 5,
[00:52:56] 2,
[00:52:57] 4,
[00:52:58] 這裡,
[00:52:59] 3,
[00:53:00] 2,
[00:53:01] 7,
[00:53:02] 5,
[00:53:03] 2,
[00:53:04] 4,
[00:53:05] 1,
[00:53:06] 這個,
[00:53:07] 這一串,
[00:53:08] 就代表,
[00:53:09] 那個8皇后的那個盤面,
[00:53:10] 可以吧,
[00:53:11] 好,
[00:53:12] 所以,
[00:53:13] 我們可以把每一組解,
[00:53:14] 表達成,
[00:53:15] 一個字串,
[00:53:16] 而我們在經驗的演算法裡面呢,
[00:53:17] 我們稱呼這個字串呢,
[00:53:18] 叫做一個Colon,
[00:53:19] 一個染色體,
[00:53:20] 好,
[00:53:21] 一個染色體,
[00:53:22] 其中呢,
[00:53:23] 呃,
[00:53:24] 這個染色體裡面的每一個質啊,
[00:53:25] 這個染色體裡面的每一個質啊,
[00:53:27] 3,
[00:53:28] 2,
[00:53:29] 7,
[00:53:30] 5,
[00:53:31] 2,
[00:53:32] 4,
[00:53:33] 這個每一個質,
[00:53:34] 叫做,
[00:53:35] 就是一個基因啦,
[00:53:36] 一串基因串起來,
[00:53:37] 變成一個染色體,
[00:53:38] 這個意思,
[00:53:39] OK,
[00:53:40] 好,
[00:53:41] 所以,
[00:53:42] 這只是,
[00:53:43] solution 的表達法喔,
[00:53:44] 接下來,
[00:53:45] 針對每一組染色體,
[00:53:46] 我們都可以去評估,
[00:53:47] 它的好壞,
[00:53:48] 在經驗的演算法裡面,
[00:53:49] 叫做,
[00:53:50] Fitness,
[00:53:51] Fitness,
[00:53:52] 哦,
[00:53:53] Fitness,
[00:53:54] 指的就是,
[00:53:55] Fitness,
[00:53:56] Fitness,
[00:53:57] 適應程度,
[00:53:58] 好,
[00:53:59] 因為它基本上就是搭建在,
[00:54:00] 因為它基本上就是搭建在,
[00:54:01] 因為它基本上就是搭建在,
[00:54:02] 演化論裡面嘛,
[00:54:03] 就適者生存,
[00:54:04] 不適者失敗嘛,
[00:54:05] 對不對,
[00:54:06] 好,
[00:54:07] 在八皇后問題裡面的Fitness,
[00:54:08] 在八皇后問題裡面的Fitness,
[00:54:09] 可能是設計成,
[00:54:10] 可能是設計成,
[00:54:11] 欸,
[00:54:12] 今天,
[00:54:13] 你的皇后的衝突的,
[00:54:14] 你的皇后的衝突的,
[00:54:15] 這個,
[00:54:16] 這個,
[00:54:17] 這個,
[00:54:18] 這個,
[00:54:19] 這個,
[00:54:20] 這個,
[00:54:21] 這個,
[00:54:22] 這個,
[00:54:23] 這個,
[00:54:24] 這個,
[00:54:25] 這個,
[00:54:26] 這個,
[00:54:27] 這個,
[00:54:28] 會去算出需要Fitness的頻率,
[00:54:29] 會去算出需要Fitness的頻率,
[00:54:30] 這樣,
[00:54:34] 那再來,
[00:54:35] 那再來,
[00:54:36] 講設今天,
[00:54:37] 我們要用經易演算法,
[00:54:38] 我們要用經易演算法,
[00:54:39] 要用經易演算法,
[00:54:40] 來處理八皇后問題,
[00:54:41] 那首先呢,
[00:54:42] 那首先呢,
[00:54:43] 我就先隨機產生出,
[00:54:44] 我就先隨機產生出,
[00:54:46] 四組不同的結,
[00:54:47] 那當然就是表達成,
[00:54:48] 那當然就是表達成,
[00:54:49] 四種不同的染色體,
[00:54:50] 四種不同的染色體,
[00:54:52] measure 3 種不同的劑다車 種,
[00:54:53] 譬如說,
[00:54:54] 第1種檯面,
[00:54:55] 比如說,
[00:54:56] 第一種 erlebt,
[00:54:57] omination,
[00:54:58] 的分數
[00:54:59] 第一種盤面給24分
[00:55:01] 第二種盤面23
[00:55:02] 第三種盤面20
[00:55:03] 第四個盤面11
[00:55:05] 分數 數字越大的就代表表現越好
[00:55:09] 這裡你可以自己定
[00:55:10] 你可以自己定你自己的
[00:55:12] 這個所謂的
[00:55:13] 適者生存的這個條
[00:55:16] 這個所謂的適應程度
[00:55:18] 你可以給它一個原則
[00:55:20] 好 根據這個Fitness Value
[00:55:25] 我們要從
[00:55:27] 這四個人呢
[00:55:28] 我們就說它形成了一個Population
[00:55:32] 每一個都是一個Individual
[00:55:33] 那每一個Individual也都表達
[00:55:35] 就是都表達成染色體的形式
[00:55:39] 好啦 那這次這個群體裡面呢
[00:55:42] 我們要先做第一件事情就是
[00:55:44] 我們要先挑出優秀的人出來
[00:55:48] 來結婚產生出下一個子彈
[00:55:52] 那什麼叫優秀呢
[00:55:53] 那就是看這個Fitness的值
[00:55:56] OK 有24 23 20 11
[00:55:58] 好 所以基本上呢
[00:56:00] 它就是我挑到第一個染色體的機率
[00:56:05] 31%
[00:56:06] 挑到第二個29%
[00:56:08] 挑到第二個26%
[00:56:09] 挑到第四個14%
[00:56:11] 好 那我就挑
[00:56:13] 那假設我也挑四次
[00:56:15] 好 第一次我挑到這個327521
[00:56:18] 第二次我挑到24748552
[00:56:21] 第三次又很巧的
[00:56:23] 又挑到327521
[00:56:25] 第四次我挑到2441512
[00:56:28] 四次
[00:56:28] 那之前被挑出來的
[00:56:31] 我挑的時候是菁英原則
[00:56:35] 就是說你表現越好的
[00:56:38] 就越有可能被挑出來
[00:56:40] 當成是產生出下一代的那個群體
[00:56:46] 那同一個Chromosome可能被挑很多次
[00:56:48] 如果它表現超優秀的話
[00:56:53] 好 挑出來之後
[00:56:55] 接下來兩兩兩兩之間
[00:56:58] 比如說第一個跟第二個結婚
[00:57:00] 好 第一個盤面跟第二個盤面結婚
[00:57:03] 那在這裡就會做兩種不同的動作
[00:57:06] 第一個動作叫Crossover
[00:57:08] 其實就是交配啦
[00:57:09] 好 交配
[00:57:10] 那我們會隨機的在這個染色體這邊
[00:57:15] 隨機找某一個位置
[00:57:16] 好 交配之後呢
[00:57:19] 我就是把第一個Chromosome的前半部分
[00:57:23] 會接上第二個Chromosome的第二個部分
[00:57:26] 第二個Chromosome的第一部分會接上
[00:57:29] 第一個Chromosome的第二部分
[00:57:31] 這個就是交配生出的小孩
[00:57:36] 好 所以這叫子代
[00:57:38] 這是父母
[00:57:40] 這是Parent
[00:57:41] 這是Children
[00:57:43] 好 那同樣的
[00:57:44] 後面這兩個也結婚
[00:57:46] 然後呢進行Crossover得到什麼
[00:57:48] 那不要忘記這是什麼意思
[00:57:50] 這個其實就是新的Solution的意思
[00:57:54] 新的盤面的意思
[00:57:56] 好 這叫Crossover
[00:57:58] 那Crossover
[00:57:59] 這個完呢
[00:58:00] 我們也知道在生物界
[00:58:04] 產生出像一個子代的
[00:58:05] 這個整個繁衍的過程當中
[00:58:07] 有可能會發生突變嘛
[00:58:09] 除了父親跟母親交換染色體之外
[00:58:13] 有可能產生突變
[00:58:15] 所以呢
[00:58:16] 每一個Individual
[00:58:20] 都有可能有一個很小的機率
[00:58:22] 可能某一個基因會變
[00:58:26] 比如說這裡本來是五的
[00:58:27] 它就變成了一
[00:58:29] 有很小很小的機率
[00:58:31] 那像第二個
[00:58:33] 這個就沒有產生任何的突變
[00:58:35] 那第三個又有某一個隨機某一個位置
[00:58:37] 產生一個突變
[00:58:39] 好 第四個這樣子
[00:58:40] 這個叫做Mutation
[00:58:44] 好 那所以說呢
[00:58:46] 這裡你看
[00:58:47] 所謂的
[00:58:48] 這是第一個染色體
[00:58:50] 這是第二個染色體
[00:58:51] 第二個染色體就是
[00:58:52] 2 4 7 4 8
[00:58:56] 8嗎 8
[00:58:58] 5 5 2
[00:58:59] 這樣子
[00:59:01] 有沒有
[00:59:01] 還有 在這裡
[00:59:02] 就是這兩個Crossover
[00:59:05] 我得到的
[00:59:06] 比如說我把它的
[00:59:07] 左邊這個盤面接上這裡的
[00:59:09] 右邊這個盤面
[00:59:10] 接起來就長這樣
[00:59:12] 所以你看它接起來就變成
[00:59:13] 3 2 7 4 8 5 5 2
[00:59:19] 就是對應到這個
[00:59:23] 產生出下一代之後
[00:59:26] 那同樣的啦
[00:59:27] 這樣的步驟可以繼續往下走
[00:59:30] 產生出下一代之後一樣
[00:59:32] 我就可以去計算這裡面每一個新的Solution
[00:59:37] 你的Fitness的值是怎麼樣
[00:59:41] 對不對
[00:59:42] 你現在產生出新的解嗎
[00:59:43] 產生出來你的新的Fitness是怎麼樣
[00:59:47] 然後呢
[00:59:48] 再根據Fitness的值去挑出能夠繁衍下一代的Chromosome
[00:59:53] 然後又繼續Crossover Mutation
[00:59:56] 那依此類推
[00:59:57] 你可以繁衍很多代
[01:00:00] 最終
[01:00:01] 在這整個繁衍了之後呢
[01:00:01] 最終在這整個繁衍了之後呢
[01:00:01] 最終在這整個繁衍了之後呢
[01:00:02] 這個過程當中
[01:00:03] 可能繁衍到最後
[01:00:04] 你比如說你讓它繁衍100代
[01:00:07] 你就去挑出第100代的
[01:00:11] 表現最好的那一個盤面
[01:00:12] 來當成你的解
[01:00:14] 或者是說你讓它繁衍100個世代
[01:00:18] 然後你再去看說
[01:00:20] 每一個世代最強的那個你都留下來
[01:00:23] 那你繁衍完100個世代之後
[01:00:25] 再把100個世代祖孫
[01:00:27] 從這個曾祖父祖父對不對
[01:00:31] 父母自己小孩孫子什麼玄孫
[01:00:35] 全部最強的拿出來再PK
[01:00:37] 再挑出一個最好的
[01:00:39] 這個就是基因演算法
[01:00:41] 講完了
[01:00:45] 就這樣
[01:00:46] 這就是基因演算法的最核心的概念
[01:00:50] 那當然其實基因演算法
[01:00:52] 或者說講得更廣一點
[01:00:54] 所謂的演化式計算
[01:00:56] 它根本就是一個學問
[01:00:58] 它根本就是一門課
[01:01:00] 它有根本就是有一門課
[01:01:04] 有一本教科書完全就是在講這個的
[01:01:07] 那裡面呢
[01:01:08] 整個大體的概念
[01:01:10] 就是我們這三頁頭裡面所說的
[01:01:13] 那裡面有很多小細節
[01:01:14] 比如說你這個挑
[01:01:16] 你要怎麼挑啊
[01:01:19] 比如說你這個挑
[01:01:21] 你是用什麼樣的策略來挑出
[01:01:23] 優秀的個體
[01:01:26] 產生出下一個子彈
[01:01:28] 那還有啊
[01:01:30] 還有另外一種做法就是
[01:01:31] 你允許假設其中某一彈
[01:01:34] 有某一個個體
[01:01:36] 超級優秀
[01:01:38] 你可以給它一個特權
[01:01:40] 就是長生不老
[01:01:41] 就是它永遠
[01:01:43] 下一代要生
[01:01:45] 就是說它超級優秀
[01:01:47] 你可以讓它在下一次
[01:01:49] 下一個世代
[01:01:51] 也永遠都會保留
[01:01:53] 它一定就可以再生出
[01:01:55] 下一代
[01:01:56] 它一定會被選
[01:01:57] 你可以給它一個特權
[01:01:59] 或者是怎麼樣
[01:02:01] 這裡有一大堆各式各樣不同的
[01:02:04] 變形
[01:02:06] 包含像你的chromazone
[01:02:08] 一定是binary的嗎
[01:02:09] 還是說你可以像現在畫面上的這種
[01:02:12] 你是real number的
[01:02:16] 那所以只要你的想法
[01:02:20] 你所想要求的解
[01:02:23] 有辦法表達成chromazone的形式
[01:02:27] 你就可能可以應用經驗演算法
[01:02:30] 來解這個問題
[01:02:32] 所以我們目前在書上
[01:02:34] 我們這裡是用八王二問題來表達
[01:02:37] 那接下來其他的
[01:02:39] 你自己比如說你自己final project
[01:02:41] 你假設你要做
[01:02:42] 那就看你自己的創意
[01:02:43] 比如說在過去以前
[01:02:45] 我們曾經
[01:02:47] 我們實驗室也用過
[01:02:49] 經驗演算法來幫忙我們解決
[01:02:51] 比如說棒球比賽
[01:02:54] 棒球影片分析的問題
[01:02:56] 那重點在於說你如何把那個問題
[01:02:58] 轉化成chromazone的形式
[01:03:01] 讓它去求一個最佳解
[01:03:03] 好
[01:03:04] 這當然就是各自看你的
[01:03:06] 個人的這個功力
[01:03:09] 看你個人的設計而定
[01:03:12] 好
[01:03:13] 以上就是這個基因演算法
[01:03:16] 好
[01:03:18] 講到這邊一個段落
[01:03:20] 我們來看一下snide上面有沒有問題
[01:03:22] 我如果一開始就存在整體最佳解
[01:04:00] 根據模擬退火的機制
[01:04:03] 它會為了尋找更最佳
[01:04:05] 更佳的解而有機率容許問題嗎
[01:04:08] 就是溫度更高的解存在
[01:04:10] 如果最後發現溫度越來越高
[01:04:14] 它怎麼會回傳原本一開始的最佳解
[01:04:17] 我覺得問這個問題可能有點誤解
[01:04:20] 就是說溫度一定不會越來越高
[01:04:23] 因為根據定義溫度一定是一開始最高溫
[01:04:27] 然後溫度會一路下降
[01:04:29] 所以你的溫度是肯定一路下降的
[01:04:33] 那溫度下降是什麼意思呢
[01:04:35] 就是你越來越不容易用
[01:04:38] 比較爛的解來取代掉現有的解的意思
[01:04:44] 那我在猜這位同學問這個問題是說
[01:04:48] 會不會比如說我本來我在某一個位置
[01:04:53] 然後我用一個比較爛的解來取代掉我
[01:04:58] 那我就變爛了啊
[01:05:00] 你的意思應該是說
[01:05:02] 當我變爛了之後
[01:05:04] 我會不會又一路爛下去
[01:05:06] 我再也就回不到
[01:05:08] 我剛剛比如說我現在在時間t等於3的時候
[01:05:11] 其實我的解比t等於4的時候的解來得更好
[01:05:15] 那你走到t等於4
[01:05:17] 你變爛了
[01:05:18] 然後又跑到t等於5
[01:05:20] 會不會又更爛
[01:05:22] 你的意思是說有沒有可能再回歸到
[01:05:27] 當時t等於3的時候的那個
[01:05:29] 真正在歷史上曾經掌握的最佳解呢
[01:05:32] 我覺得有可能可以
[01:05:36] 也有可能不可以
[01:05:40] 我可以講說
[01:05:42] 因為機率嘛
[01:05:43] 所以它沒有一定會怎麼樣
[01:05:45] 我只能夠說它最終
[01:05:47] 它的解
[01:05:51] 你找到的解會變得越來越爛的
[01:05:53] 那個機率是非常非常低的
[01:05:55] 非常非常低的
[01:05:57] 應該有很高的機會
[01:05:59] 你的解是會朝好的方向來走
[01:06:03] 我只能夠跟你這麼講
[01:06:05] 那當然你如果要很嚴謹的數學證明
[01:06:08] 這個一定也有證明
[01:06:10] 只是我們書上這個證明的部分
[01:06:12] 就略過不談
[01:06:14] 好
[01:06:15] 所以同學你這個問得不錯
[01:06:19] 信件這個我已經說過N次了
[01:06:23] N次了
[01:06:24] 我不想要再回答
[01:06:28] 成大同學不可以填線上保單
[01:06:31] 我們說過了
[01:06:34] 我們為什麼要弄這個算力
[01:06:36] 就是我們要鼓勵大家來實體上課
[01:06:39] 你只要成大同學
[01:06:41] 你填再多也沒有用
[01:06:43] 因為你必須在現場
[01:06:45] 當場領號碼牌
[01:06:46] 這個我講過太多次了
[01:06:56] 老師說會卡在極大值
[01:06:59] 應該說local maxima
[01:07:01] 但老師後來又說
[01:07:03] 正常來講根本不可能像現在看一眼就知道
[01:07:06] 最大值在哪裡
[01:07:07] 對
[01:07:08] 那這個問題是不是隻能
[01:07:11] 只能怎樣
[01:07:12] 不同方法多找幾個極大值再來比較
[01:07:15] OK
[01:07:16] 好
[01:07:17] 我稍微
[01:07:19] 對
[01:07:20] 就是說很多時候
[01:07:22] 在現實世界當中
[01:07:24] 我們根本就不知道
[01:07:25] 真正的極大值在哪裡
[01:07:29] 這是很正常的
[01:07:31] 那所以呢
[01:07:32] 很多時候我們找到的解
[01:07:34] 都只是local maxima
[01:07:38] 即使
[01:07:39] 你現在看全世界AI最強的
[01:07:42] 對不對GPT-6 Ultra
[01:07:45] 你認為它現在的這個模型
[01:07:47] 找到的就已經是這個宇宙裡面的最佳解嗎
[01:07:50] 一定不是
[01:07:52] 我們只能夠說
[01:07:53] 它是目前地球上
[01:07:55] 我們能夠所使用的training data裡面
[01:07:58] 能夠找到
[01:07:59] 目前人類能夠找到的
[01:08:01] 某一組
[01:08:03] 你認為是很不錯的一個解而已
[01:08:06] 但它是不是在數學上是一個
[01:08:08] 真正的最佳解
[01:08:10] 事實上我覺得一定不是
[01:08:13] 如果是的話
[01:08:15] 它就再也不會有GPT-7
[01:08:17] GPT-8
[01:08:18] GPT-9了嘛
[01:08:19] 一定不是
[01:08:20] 它就不可能再進步了
[01:08:22] 所以一定不是
[01:08:23] 好
[01:08:24] 好那再來
[01:08:25] 所以你的問題是說
[01:08:26] 那怎麼辦呢
[01:08:28] 不能怎麼辦
[01:08:29] 或者是說
[01:08:30] 我們剛剛講了有幾種做法
[01:08:32] 比如說Random Restart
[01:08:34] 我們就多做幾次
[01:08:36] 然後再從這幾次的結果裡面
[01:08:39] 找到相對最好的那一個
[01:08:42] 但是你可能永遠都無法保證
[01:08:45] 你找到的是數學上的最佳解
[01:08:49] OK我希望這樣有回答到你的問題
[01:08:53] 很多時候我們
[01:08:55] 那你說
[01:08:56] 那這樣子我沒有找到真正的最佳解
[01:08:59] 會不會怎麼樣啊
[01:09:00] 答案是也不會怎麼樣
[01:09:02] 我們還活得好好的
[01:09:04] 很多時候在人類的真正的應用上
[01:09:07] 你找到的解
[01:09:09] 只要夠好就行了
[01:09:13] 我們就覺得Happy了
[01:09:15] 我們就覺得Happy了
[01:09:16] 這樣子
[01:09:17] 像你現在用GPT-6
[01:09:19] 你蠻Happy的吧
[01:09:20] 用得還行吧
[01:09:22] 事實上在GPT-6出來之前
[01:09:24] 你GPT-5
[01:09:25] 你用得也還蠻Happy的吧
[01:09:27] 所以其實沒有一定要找到最佳解
[01:09:32] 只有什麼人要找到
[01:09:34] 真正窮極意義上的最佳解呢
[01:09:37] 大概就是數學家吧
[01:09:39] 在概念上consecually要找到最佳解
[01:09:43] 在實際工程應用上
[01:09:45] 通常我們大部分接受的都是
[01:09:47] 到目前為止能夠找到的那個解
[01:09:50] 可用的解這樣子
[01:09:55] 而且沒有公認最好的最佳化的方法
[01:09:57] 沒有
[01:09:58] 根據不同的問題
[01:10:00] 你所使用的策略
[01:10:01] 先休息一下再回來
[01:10:16] 你不是有提到那個
[01:10:32] 炊火它有可能越來越爛
[01:10:34] 然後你說可能性很低
[01:10:36] 那我剛剛的想法就是
[01:10:38] 就是在演算法為什麼就是先不要記住
[01:10:40] 哎我有個時間的最佳解
[01:10:42] 然後往下走
[01:10:43] 然後它會有一個最終的重點
[01:10:45] 然後如果最後真的最爛
[01:10:46] 那我就用一個額外的能源去把那個
[01:10:49] 可以啊
[01:10:50] 可以啊
[01:10:51] 剛剛我有回答問題的時候
[01:10:53] 我有提到類似像這樣
[01:10:54] 可以可以
[01:10:55] 實際上真正應用的時候
[01:10:57] 的確是可以
[01:10:58] 另外一個問題是
[01:11:02] 我剛剛看到教授說下禮拜有開會
[01:11:04] 然後希望下週不知道能不能約教授
[01:11:07] 就是在meeting一次
[01:11:08] 開會
[01:11:10] 你不是說
[01:11:11] 我希望約教授meeting
[01:11:13] 假設下禮拜
[01:11:14] 我要出國
[01:11:15] 整個禮拜要出國
[01:11:16] 對
[01:11:17] OKOK
[01:11:30] 那這個聽課跟用什麼電腦
[01:17:28] 呃我需要
[01:17:33] 那你就去做其他的啊
[01:17:34] 你就不用聽課啊
[01:17:36] 哎不然你就專心聽課啊
[01:17:38] 我並沒有這樣子
[01:17:46] 所以呢你現在是要怎麼樣
[01:17:47] 要拿號碼牌
[01:17:48] 對我想
[01:17:49] 那要找助教
[01:17:51] 哦好
[01:17:52] 我們在這一張的前半段那一邊呢
[01:21:32] 在講的大部分的情況
[01:21:34] 我們都是假設它是discrete的case
[01:21:38] 就是說比如說八皇后問題
[01:21:40] 以皇后的位置一定就是在固定的某個位置嘛
[01:21:44] 不會是連續的一個什麼東西啊
[01:21:47] 那呃當然你如果是hear climbing的話
[01:21:51] 你可能是在一個連續的solution space裡面
[01:21:54] 去找到最好的一個解
[01:21:56] 好
[01:21:57] 那其實如果專門針對continuous space裡面的問題的話
[01:22:03] 呃我們有其他的辦法來去做local search
[01:22:07] 好
[01:22:08] 做到所謂的更有效率的local search
[01:22:10] 所以你應該可以感覺的到
[01:22:12] 剛剛在呃剛剛前面講的hear climbing也好
[01:22:16] 然後seminating而已而已
[01:22:19] GA也好
[01:22:20] 他都他都有一種
[01:22:22] 好像試試看隨機性的感覺
[01:22:25] 有沒有啊
[01:22:26] 我看一下
[01:22:27] 欸隔壁的鄰居比我好
[01:22:28] 我就用他來取代掉我
[01:22:30] 啊我再去看
[01:22:31] 啊然後就是有一種隨機性
[01:22:34] 但在某一些問題呢
[01:22:36] 其實我們是可以有更有效率的解法的啊
[01:22:39] 所以我們底下來看一個例子
[01:22:41] 角色呢
[01:22:43] 之前有給大家看過一個例子
[01:22:46] 就是一個羅馬尼亞的地圖嘛
[01:22:48] 對不對
[01:22:49] 什麼要從A走到B這個
[01:22:50] 好
[01:22:51] 假設呢
[01:22:52] 我現在想要在羅馬尼亞蓋三座新的機場
[01:22:56] OK
[01:22:57] 那要蓋在哪裡呢
[01:22:58] 在這個地圖裡面你要蓋在哪裡呢
[01:23:00] 呃我們希望達到的目標是
[01:23:02] the sum of square distance from each city on the map to its nearest airport is minimized
[01:23:08] 我們希望
[01:23:11] 每一個城市到它最近的那個機場
[01:23:15] 的距離
[01:23:17] 接下來要越想越好
[01:23:20] 這是我們的目標
[01:23:21] 好等於說
[01:23:22] 這個各個都市都有一個最接近的機場
[01:23:26] 那它都選在一個很不錯的一個位置
[01:23:29] 讓大家很方便可以到那個機場去
[01:23:32] 好
[01:23:33] 那所以呢
[01:23:34] 我們要決定的就是這三座機場的XY座標
[01:23:38] X1 Y1 X2 Y2跟X3 Y3
[01:23:41] 好也就是我們要決定這六個變數的值的意思
[01:23:46] 好
[01:23:47] 這六個變數的值呢
[01:23:49] 它的一個solution存在一個六維的空間當中
[01:23:54] 對不對
[01:23:55] 因為我們就是要決定X1 Y1 X2 Y2 X3 Y3
[01:23:58] 我們決定這六個值
[01:24:00] 我們要決定一個六維的向量
[01:24:02] 代表這三座機場的位置
[01:24:05] 這樣
[01:24:06] 所以我們是在一個六維的空間當中
[01:24:08] 來找最佳解的一個問題
[01:24:10] 好
[01:24:13] 那首先先寫出我們的objective function value
[01:24:16] 因為我們的目標就是說
[01:24:18] 比例而言
[01:24:19] 每一個都市到距離它最近的那個airport
[01:24:23] 的距離總和加起來會越來越好
[01:24:25] 所以我們可以寫下這個式子
[01:24:27] 我們可以列出一個function
[01:24:29] 代入不同的X跟Y
[01:24:32] 那我這個function的詞呢
[01:24:34] 就定義成summationI等於1到3
[01:24:36] 因為三座機場
[01:24:38] 然後呢summationC屬於C1
[01:24:40] 這什麼意思
[01:24:41] 就是說
[01:24:42] 某一個程式C
[01:24:44] 它是在Di座機場的中間
[01:24:47] Di座機場的最近的
[01:24:50] 應該說它是屬於離Di座機場最近的
[01:24:53] 那些都市的集合之一
[01:24:56] 叫做小C
[01:24:57] 所以xi-sc就是指
[01:25:00] C這座都市離它最近的那個機場的
[01:25:03] X座標的差距的平方
[01:25:05] 加上Yi-Yc的平方
[01:25:08] 這樣
[01:25:10] 那所以說離Ci Di座機場最近的
[01:25:14] 可能有比如說五個都市
[01:25:16] 這五個都市
[01:25:17] 距離Di座機場的距離平方
[01:25:19] 加上
[01:25:21] 有可能有三個都市
[01:25:23] 距離第二座機場最接近
[01:25:25] 那它們的
[01:25:26] 跟機場的距離的平方加起來
[01:25:28] 以此類推
[01:25:29] 整個全部加起來
[01:25:31] 我希望能夠minimize
[01:25:34] 這個objective function代入
[01:25:36] 好我們要最小化
[01:25:38] 那請大家記得
[01:25:39] 當我們在找所謂的最佳解
[01:25:41] 我們在找
[01:25:42] 我們在做最佳化的時候
[01:25:45] 剛剛我們前面舉的例子
[01:25:47] 都是說我們要最大化
[01:25:49] 那個objective function value
[01:25:51] 這OK沒問題
[01:25:53] 那我們有的時候呢
[01:25:54] 我們是要去最小化
[01:25:56] 那個objective function value
[01:25:57] 也OK
[01:25:59] 只不過普遍來講
[01:26:01] 在整體而言各式各樣不同的
[01:26:03] 最佳化的這個工作裡面
[01:26:07] 我們傾向於
[01:26:09] 把問題都轉成
[01:26:11] 我們要去最小化這個cause
[01:26:14] 我們稱呼它叫做cause
[01:26:16] 或者叫做loss
[01:26:18] 因為在數學上
[01:26:19] 你要去最大化一個東西
[01:26:21] 容易造成那個數字會爆掉
[01:26:24] 那如果是最小化那個loss
[01:26:26] 因為loss會
[01:26:28] 一般來講
[01:26:29] 一般正常的心魔教
[01:26:31] loss最小等於0
[01:26:32] 所以我們去minimize這個loss
[01:26:34] 或minimize這個cost
[01:26:36] 我們一路就會
[01:26:38] 最小化到接近0
[01:26:40] 它不會產生出
[01:26:41] 那個數值的overflow
[01:26:43] 所以
[01:26:44] 即使在
[01:26:45] 概念上
[01:26:46] 我們要去最大化
[01:26:47] 某一個objective function value
[01:26:48] 我們也會把數學改寫一下
[01:26:50] 變成是
[01:26:51] 我們要去最小化那個cost
[01:26:53] 這樣子
[01:26:55] 好
[01:26:56] 那所以我們現在的objective function value
[01:26:58] 是長這樣嗎
[01:26:59] 或者說我們的cause長這樣嗎
[01:27:01] 那為了避免呢
[01:27:03] 這個如果說
[01:27:05] 你今天你要去決定
[01:27:06] 這個機場的位置
[01:27:08] XI YI的話
[01:27:10] 呃
[01:27:12] 你可以把這個
[01:27:14] 它在這個連續空間當中
[01:27:16] 你XI跟YI有幾種變化
[01:27:18] 有無限多種變化
[01:27:20] 對不對
[01:27:21] 因為它是在一個連續的空間當中
[01:27:23] 如果你為了要避開
[01:27:25] 這種continuous
[01:27:26] 無限多種變化的情況
[01:27:27] 你可以把這個問題呢
[01:27:29] discritize
[01:27:30] 把它離散化
[01:27:32] 這是一個妥協的方案
[01:27:34] 也就是說呢
[01:27:35] 假設
[01:27:36] 我永遠呢
[01:27:37] 當我在決定
[01:27:39] 任何一座機場的時候
[01:27:42] 我永遠
[01:27:43] 每次我在變動我的選擇的時候呢
[01:27:46] 我只選擇X或Y
[01:27:48] 來進行變動
[01:27:50] 然後呢
[01:27:51] 我每次變動
[01:27:52] 要嘛是加delta
[01:27:53] 要嘛是減delta
[01:27:56] OK
[01:27:57] 好
[01:27:58] 所以整體而言呢
[01:27:59] 我每
[01:28:01] 我隨機的
[01:28:03] 選某一個XI
[01:28:05] YI
[01:28:06] X1 Y1
[01:28:07] X2 Y2
[01:28:08] X3 Y3
[01:28:09] 我隨機挑出一組解之後
[01:28:12] 我要怎麼去
[01:28:14] 定義它的鄰居
[01:28:16] 它的鄰居
[01:28:17] 根據這裡的定義就是說
[01:28:18] 我每次只挑
[01:28:19] 機場的X或機場的Y來變
[01:28:22] 而且每次變
[01:28:23] 都是加delta或者是減delta
[01:28:26] 所以整體而言呢
[01:28:28] 我一定只會有12個鄰居
[01:28:31] 為什麼
[01:28:32] 因為你選X或Y有兩種選擇
[01:28:35] 然後呢
[01:28:36] 你選了之後
[01:28:38] 你可以做的變動
[01:28:39] 要嘛是加delta
[01:28:40] 要嘛是減delta
[01:28:42] 所以就是2乘2
[01:28:44] 一組機場
[01:28:45] 一個機場有2乘2
[01:28:46] 有4個選擇
[01:28:47] 有3個機場
[01:28:48] 4乘3
[01:28:49] 所以總共12種選擇
[01:28:51] 來去
[01:28:53] 所以每一個初始的state
[01:28:56] 我都只有12個鄰居
[01:28:59] 對意思
[01:29:00] 這個是離散化的情況
[01:29:02] 不過
[01:29:04] 如果你要從數學上
[01:29:06] 比較更妥善的來解這個問題呢
[01:29:09] 你其實你可以直接
[01:29:10] work on continual space
[01:29:12] 你在一個連續的空間當中
[01:29:14] 你去找到
[01:29:16] 能夠使得這個function value
[01:29:19] objective function value
[01:29:21] 能夠有極值的地方
[01:29:24] 能夠有極值的地方
[01:29:26] 好
[01:29:27] 那這裡呢
[01:29:28] 就牽涉到微積分
[01:29:29] 大家學過微積分吧
[01:29:31] 以前呢
[01:29:32] 告訴你一個函數
[01:29:35] 要你求極值
[01:29:37] 怎麼做
[01:29:39] 口訣就是什麼
[01:29:41] 對它進行一次微分
[01:29:42] 令它等於0
[01:29:43] 然後求解
[01:29:45] 對不對
[01:29:46] 你找出來的那個
[01:29:48] variable的值
[01:29:49] 就是能夠造成
[01:29:50] 這個function
[01:29:52] 有極大值或極小值
[01:29:54] 有極值的地方就可以了
[01:29:58] OK
[01:29:59] 這是以前大家學微積分的時候
[01:30:01] 或者高中數學
[01:30:02] 你要求極值的時候
[01:30:04] 老師告訴你的口訣
[01:30:06] 那至於為什麼
[01:30:08] 怎麼那麼好用啊
[01:30:09] 我給它做一次
[01:30:10] 對它做一次微分
[01:30:12] 令它等於0
[01:30:13] 然後求解
[01:30:14] 為什麼
[01:30:16] 好
[01:30:17] 我們在這門課裡面
[01:30:18] 不會告訴你為什麼
[01:30:19] 因為你有興趣的話
[01:30:21] 你可以去修最佳化導論
[01:30:23] 那是一門博大精深的課
[01:30:26] 我們這裡沒辦法
[01:30:27] 跟大家講為什麼
[01:30:29] 我也開過這門課啦
[01:30:31] 另外一門
[01:30:32] 不過那已經是另外一門課了
[01:30:33] 總而言之
[01:30:34] 你還是照用
[01:30:35] 你之前學過的那個口訣
[01:30:37] 你要去找到這個function的極值
[01:30:41] 這個function是一個什麼
[01:30:42] 有六個變數
[01:30:43] 所形成的一個函數
[01:30:46] 你要找到這個函數的極值在哪裡
[01:30:49] 你要找到最好的S1應該是多少
[01:30:51] 最好的S2是多少
[01:30:52] 最好的S3是多少
[01:30:54] S2是多少
[01:30:55] S1 Y1 S2 Y2是多少
[01:30:57] 就是對它做一次微分
[01:30:59] 那因為它有六個變數啊
[01:31:00] 所以其實對它做一次微分
[01:31:02] 的意思就是
[01:31:04] 我先對S1做偏微分
[01:31:06] 再對S2
[01:31:07] 再對Y1做偏微分
[01:31:09] 再對S2偏微分
[01:31:10] 再對Y2偏微分
[01:31:11] 再對S3偏微分
[01:31:12] Y3偏微分
[01:31:13] 所以這個function的一次微分
[01:31:16] 就等於是
[01:31:18] 我個別對這六個變數
[01:31:20] 個別做偏微分的結果
[01:31:22] 利他等於零
[01:31:24] 然後你去找到
[01:31:26] 最好的那一組
[01:31:28] S1一直到Y3的那一組結
[01:31:31] 這是數學上
[01:31:34] 概念上你可以這麼做
[01:31:36] However
[01:31:38] 但是
[01:31:39] 事情總是沒有那麼容易嘛
[01:31:41] 對不對
[01:31:42] 今天要是你這個function
[01:31:44] 非常的複雜
[01:31:45] 你微分
[01:31:46] 你做不出來
[01:31:47] 或者你找
[01:31:48] 你整理不出一個
[01:31:49] close form solution的時候
[01:31:51] 你找到一個數學式
[01:31:53] 你代入那個數學式
[01:31:54] 直接求出最好解
[01:31:56] 最佳解的時候
[01:31:58] 你就沒有辦法用這樣子的一個來做
[01:32:00] This equation cannot be solved in close form
[01:32:03] In many cases
[01:32:04] 在很多的情況之下
[01:32:06] 這一個問題根本沒有
[01:32:08] close form solution
[01:32:13] 那這件事情
[01:32:15] 就會跟
[01:32:17] 等一下我們要講的這個計法
[01:32:19] 其實就跟你現在在
[01:32:21] Trend Deep Learning Model的時候
[01:32:23] 用的計法是一樣的
[01:32:25] Deep Learning
[01:32:27] 裡面隨隨便便就是幾百萬個參數
[01:32:29] 幾億個參數
[01:32:31] 現在我們在畫面上
[01:32:33] 看到的這個例子只有六個參數
[01:32:35] 但是在New World Network裡面
[01:32:37] 有幾百萬個
[01:32:39] 但是找到這最好的那一組
[01:32:41] 幾百萬個參數的做法
[01:32:43] 跟我們現在在這裡在講的
[01:32:45] 是一樣的做法
[01:32:47] 原則上是一樣的
[01:32:49] 那我們舉個例子
[01:32:51] 現在三座機場
[01:32:53] 假設我現在先對S1做偏微分
[01:32:55] 大家會偏微分吧
[01:32:57] 微完之後呢就長這樣
[01:32:59] OK
[01:33:01] 那我怎麼去找到
[01:33:03] 最好的
[01:33:05] 這個是有close form solution的
[01:33:07] 情況之下
[01:33:09] 那如果沒有close form solution
[01:33:11] 你今天你如果要去
[01:33:13] 逐步的去
[01:33:15] 你的XY的話
[01:33:17] 你可以怎麼做呢
[01:33:19] 我們可以做
[01:33:21] State Piste
[01:33:23] Assent Here Climbing
[01:33:25] By updating the current state according to the formula
[01:33:27] 我們可以用
[01:33:29] 最陡峭的
[01:33:31] T這個Here Climbing
[01:33:33] 來找
[01:33:35] 來去update我的X
[01:33:37] 什麼叫做最陡峭的
[01:33:39] Here Climbing
[01:33:41] 大家懂了吧對不對
[01:33:43] 我從某一個地方出發看一下週圍的鄰居
[01:33:45] 然後我去update到那個鄰居
[01:33:47] 如果今天
[01:33:49] 你找你周圍的鄰居
[01:33:51] 你永遠都是找最強的
[01:33:53] 那個鄰居
[01:33:55] 你update過去的話
[01:33:57] 在概念上你是不是就是說
[01:33:59] 從你現在原本的objective function value
[01:34:01] 變成是
[01:34:03] 那個objective function value
[01:34:05] 所以你objective function value的變動
[01:34:07] 是一個最陡峭的狀況
[01:34:09] 一路走上去
[01:34:11] 你用最快的速度
[01:34:13] 爬到你目前眼見所及
[01:34:15] 的高度對不對
[01:34:17] 就是這一個
[01:34:19] 就是這一個
[01:34:21] 那這個式子呢Xupdate成什麼
[01:34:23] X加上Alpha倍的
[01:34:25] 這個是function f
[01:34:27] 的一次微分
[01:34:29] 其實這個就是T度的意思
[01:34:31] 在
[01:34:33] 微細本裡面
[01:34:35] 你對某一個方向做一次微分
[01:34:37] 代表的就是
[01:34:39] 你在某一個方向上面的
[01:34:41] T度的意思
[01:34:43] 這講的再更白一點
[01:34:45] 你想像成
[01:34:47] 你現在是站在一個山坡上
[01:34:49] 假設你現在是在一個
[01:34:51] 三維的空間當中
[01:34:53] 你在一個山坡上
[01:34:55] 你的海拔高度就是你的
[01:34:57] objective function value
[01:34:59] 然後呢
[01:35:01] 你往右邊走
[01:35:03] 你的右左這個
[01:35:05] 維度叫做X
[01:35:07] 你的前後這個維度叫做Y
[01:35:09] OK
[01:35:11] 那我對X做偏微分
[01:35:13] 是什麼意思
[01:35:15] 意思就是說
[01:35:17] 我要去算
[01:35:19] 我如果往右邊走
[01:35:21] 一個單位的話
[01:35:23] 我的海拔高度會怎麼變動
[01:35:25] 是會上升一公尺呢
[01:35:27] 還是下降0.5公尺呢
[01:35:29] 這個就是叫做
[01:35:31] 我在X方向做偏微分
[01:35:33] 的意義
[01:35:35] 我們也稱呼這個叫做
[01:35:37] 這個叫做T度
[01:35:39] 我們在X方向上面的T度的意思
[01:35:41] 那我也可以在Y方向上面
[01:35:43] 我做一次偏微分
[01:35:45] 物理意義就代表說
[01:35:47] 我現在站在一個山坡上
[01:35:49] 我往前走一步
[01:35:51] 我的海拔高度會變動的情況
[01:35:53] 這個就是我在Y方向上面的T度
[01:35:55] 所以
[01:35:59] 回到這個數學
[01:36:01] 你可以看到說
[01:36:03] 我這個X
[01:36:05] 我用誰來取代掉它呢
[01:36:07] 就是我原本的X再加上
[01:36:09] 我去看我往
[01:36:11] 哪一個
[01:36:13] 我往X這個方向
[01:36:15] 我走一步
[01:36:17] 我能夠造成的
[01:36:19] 海拔高度的變動
[01:36:23] 不止
[01:36:25] 應該是說
[01:36:27] 我要走多遠
[01:36:29] 這個是運作在X上面
[01:36:31] 我這裡是決定方向
[01:36:33] 這是決定方向
[01:36:35] 比如說我到底是
[01:36:37] 我應該往右走
[01:36:39] 海拔高度會變高
[01:36:41] 還是我往左走
[01:36:43] 海拔高度會變高
[01:36:45] 所以這個倒三角的這個gradient FLS
[01:36:47] 走多遠呢
[01:36:49] 就是這個Alpha
[01:36:51] 你是走一步呢
[01:36:53] 還是走十步呢
[01:36:55] 那基本上這個Alpha
[01:36:57] 就成為是Step size
[01:36:59] 你要走幾步的意思
[01:37:01] 一旦你決定好你要走的方向
[01:37:03] 接下來你就看說
[01:37:05] 你要走幾步
[01:37:10] 這個Alpha你要走幾步啊
[01:37:12] 其實沒有一定要走幾步
[01:37:14] 你也不知道要走幾步
[01:37:16] 這基本上是一個參數
[01:37:18] 你要去決定的
[01:37:20] 這個Alpha太小
[01:37:22] 代表說你雖然決定好一個
[01:37:24] 能夠提升你海拔高度的方向
[01:37:26] 但是你每次都走小碎步
[01:37:28] 慢慢走
[01:37:30] 那你可能就要走很久
[01:37:32] 你還要跑到很高的地方嗎
[01:37:34] 所以如果Alpha太小
[01:37:36] 你就要走很多步
[01:37:38] 才會跑到最高的地方
[01:37:40] 那如果Alpha很大
[01:37:42] 太大了
[01:37:44] 你決定好往右邊走那個方向
[01:37:46] 你一口氣就衝兩公里
[01:37:48] 一下就衝兩公里
[01:37:50] 越過山丘
[01:37:52] 又跑到山的另外一頭
[01:37:54] 你的高度搞不好還會下降
[01:37:56] 這樣懂我意思嗎
[01:37:58] 所以過猶不及
[01:38:00] 你Alpha太小
[01:38:02] 你整個update的過程要走很多步
[01:38:04] Alpha太大
[01:38:06] 你可能就會錯失了
[01:38:08] 你真正最好該走的那個步數
[01:38:10] 這樣子
[01:38:12] OK
[01:38:14] 所以呢
[01:38:16] 這裡告訴我們說
[01:38:18] 你做梯度
[01:38:20] 是決定
[01:38:22] 你要走的方向
[01:38:24] 那你要走多遠呢
[01:38:26] 你要走多遠
[01:38:28] 其實這又是另外一個
[01:38:30] 最佳化的問題
[01:38:32] 我怎麼知道我現在往右走
[01:38:34] 我到底是要走十步還是要走兩公里
[01:38:36] 說不定是我往右邊走
[01:38:38] 150公尺是最好的
[01:38:40] 我如果真的往這邊走
[01:38:42] 走右邊150公尺
[01:38:44] 我能夠造成的海拔高度提升
[01:38:46] 是最多的
[01:38:48] 這又是另外一個
[01:38:50] 最佳化的問題
[01:38:52] 那你可以用
[01:38:54] 所謂的line search的做法
[01:38:56] 來解決
[01:38:58] 來找到所謂的最佳化的
[01:39:00] 最好的Alpha
[01:39:02] 那在很多的問題裡面呢
[01:39:04] 其實line search
[01:39:06] 有很多種做法
[01:39:08] 那其中很有名的呢
[01:39:12] 就是牛頓法
[01:39:14] 似曾相識對不對
[01:39:16] 大家以前學過只是你忘記了嘛
[01:39:18] 牛頓法
[01:39:20] 牛頓法在幹嘛呢還記得嗎
[01:39:22] 牛頓法用來找
[01:39:24] 求一個function的root
[01:39:26] 求一個function的解
[01:39:28] Finding root of function
[01:39:30] that is solving equation of the form
[01:39:32] g of x等於0
[01:39:34] 就是說當我們要求
[01:39:36] g of x等於0的時候
[01:39:38] 哪一個x代進去它會接近0
[01:39:40] 對不對
[01:39:42] 這是牛頓法的功用
[01:39:44] 如果你還記得的話
[01:39:46] 那沒辦法現在告訴你
[01:39:48] 或者是你可以回去翻一下你以前的數學書
[01:39:50] 牛頓法的功用
[01:39:52] 牛頓法update的功用是這樣
[01:39:54] 牛頓法的概念也是
[01:39:56] 我怎麼知道這個x
[01:39:58] 哪一個x代進去
[01:40:00] 我x要代入什麼樣的值
[01:40:02] g of x等於0
[01:40:04] 其實不知道
[01:40:06] 我就亂猜
[01:40:08] 我先隨便亂猜一個x
[01:40:10] 然後我再去update這個x
[01:40:12] 讓它很接近
[01:40:14] 我新的x代進去之後
[01:40:16] 能夠比較
[01:40:18] g of x會比較接近0
[01:40:20] 這樣
[01:40:22] x減掉
[01:40:24] g of x除上g prime x
[01:40:26] 這個prime代表的就是
[01:40:28] 我對x做
[01:40:30] 一次微分的意思
[01:40:32] 這個是牛頓法update公式
[01:40:36] 有了這個基礎之後
[01:40:38] 我們再從另外一個角度
[01:40:40] 應該說把剛剛講的
[01:40:42] 再重述一次
[01:40:44] 底下這兩頁投影片
[01:40:46] 是我之前教
[01:40:48] 最佳化的時候
[01:40:50] 的兩頁投影片
[01:40:52] 現在你就把它想像成
[01:40:54] 我呢
[01:40:56] 我的參數有s1跟x2
[01:40:58] 然後呢
[01:41:00] 我的objective function value
[01:41:02] 是這個z
[01:41:04] 所以你代入不同的s1跟s2
[01:41:06] 你的z的一個
[01:41:08] 變動
[01:41:10] 可能長得像是這樣的一個曲面
[01:41:12] 好像一個碗
[01:41:14] 假設我們講一個比較簡單的case
[01:41:16] 事實上這個曲面
[01:41:18] 可能是高高低低
[01:41:20] 很崎嶇的一個奇怪的
[01:41:22] 曲面
[01:41:24] 好假設現在這個曲面
[01:41:26] 就是好像一個碗這個樣子
[01:41:28] 那我要找到最佳解
[01:41:30] 我要找到極值
[01:41:32] 什麼樣子的s1y1
[01:41:34] s1跟s2代進去
[01:41:36] 能夠讓我找到
[01:41:38] 最低的
[01:41:40] 這一個點呢
[01:41:42] 好那其實假設我隨機
[01:41:44] 挑選了某一個
[01:41:46] x1等於這麼多
[01:41:48] x2等於這麼多
[01:41:50] 那大概就對應到這個位置吧
[01:41:52] 那我可以去它的objective function value
[01:41:54] 大概在這裡
[01:41:56] 好
[01:41:58] 那相當於
[01:42:01] 我現在站在這個碗的這個山腰上
[01:42:03] 對不對我在山腰上
[01:42:05] 那
[01:42:07] 跟我這個位置
[01:42:09] 同樣高度的
[01:42:11] 這一圈
[01:42:13] 假設我們把它投影下來
[01:42:15] 這個叫做level set
[01:42:17] level set你把它想像的就是
[01:42:19] 等高線的意思
[01:42:21] 在我們地理課裡面的等高線
[01:42:23] 那我們現在
[01:42:25] 假設這個向量叫做x0
[01:42:27] 如果我們
[01:42:29] 去算
[01:42:31] f 的t度
[01:42:33] 代表的就是這一圈
[01:42:40] 跟這一圈等高線的
[01:42:42] 切線垂直的
[01:42:44] 這個方向
[01:42:46] 的意思
[01:42:48] 好那其實
[01:42:50] 也就是你想一下這個需要一點點想像力
[01:42:52] 你想一下
[01:42:54] 這個切線這個方向相當於是說
[01:42:56] 你現在只能站在這個地方
[01:42:59] 你要往
[01:43:01] 切線的這個方向走
[01:43:03] 你的海拔高度會增加最快
[01:43:05] 你想一下你現在人站在這個
[01:43:07] 你如果往
[01:43:09] 那個方向走
[01:43:11] 你是不是就很快的沿著這個
[01:43:13] 碗的這個高度
[01:43:15] 一路就爬升
[01:43:17] 你只要走一個單位
[01:43:19] 他就一路就爬升到這個地方
[01:43:21] 或者相反假設你今天
[01:43:23] 你是要去minimize你的高度
[01:43:25] 那你就是走切線的反方向
[01:43:27] 就是往切線的
[01:43:29] 反方向來走
[01:43:31] 所以你就是往這個方向走
[01:43:33] 其實你沒有辦法
[01:43:35] 直接往因為你不會說往這個方向走
[01:43:37] 掉下去啦其實往這個方向走的意思
[01:43:39] 其實就是你會快速的
[01:43:41] 走到這個碗的
[01:43:43] 底端的意思
[01:43:45] 這樣可以嗎這需要一點想像力
[01:43:47] 稍微抽象一點
[01:43:49] 好所以大家
[01:43:51] 只需要記得一件事情就是說
[01:43:53] 你在這個function裡面的
[01:43:55] 某一組體你去算他的t度
[01:43:57] t度代表的意義是
[01:43:59] 你能夠
[01:44:01] 快能夠用
[01:44:03] 最快速讓你提升
[01:44:05] 海拔高度的那個
[01:44:07] 方向就是他的t度
[01:44:09] 反之
[01:44:11] t度的反方向就是能夠讓
[01:44:13] 你快速降低
[01:44:15] 海拔高度的那個方向
[01:44:17] ok
[01:44:19] 好那現在
[01:44:21] 我們現在假設
[01:44:23] 人在這裡我們已經
[01:44:25] 假設我們現在是要去走到碗的
[01:44:27] 最底處好了我們知道
[01:44:29] 他是這個方向可是要走多遠
[01:44:31] 要走多遠
[01:44:33] 這時候
[01:44:35] 牛頓法出來了
[01:44:37] 牛頓法大家以前高中
[01:44:39] 或者大學有幾分一定看過
[01:44:41] 這張圖
[01:44:43] 今天假設我這個曲線長這樣
[01:44:45] 就是說我這個碗啦
[01:44:47] 我現在站在碗的這個地方
[01:44:49] 我這個碗的這個高度
[01:44:51] 一路曲線是這樣走
[01:44:53] 所謂的牛頓法大家還記得嗎牛頓法是怎麼做的
[01:44:55] 就是什麼
[01:44:57] 我現在這個點
[01:44:59] 我對應的
[01:45:01] x在這裡
[01:45:03] 我的高度在這裡
[01:45:05] 我站在山腰上的這裡
[01:45:07] 我在這裡我做一個切線
[01:45:09] 有沒有我做一個切線
[01:45:11] 碰到
[01:45:14] x這個地方
[01:45:16] 這個點x
[01:45:18] k加1就是我要
[01:45:20] update過去的位置
[01:45:22] 我本來從sk出發
[01:45:24] 我要update到哪一個
[01:45:26] sk加1就是我這樣切線過去
[01:45:28] 到這裡
[01:45:30] 這個sk加1就是我要update的地方
[01:45:32] 好
[01:45:34] 我在從它的高度這個點
[01:45:36] 我在做一個切線
[01:45:38] 我就下一次update
[01:45:40] 我就跑到這個地方
[01:45:42] 如果你還記得的話
[01:45:44] 高中老師數學老師就告訴你說
[01:45:46] 牛頓法真的厲害
[01:45:48] 你只要update兩三次之後
[01:45:50] 你幾乎就
[01:45:52] 非常非常接近真正的
[01:45:54] 標準答案
[01:45:56] x star這個點
[01:45:58] 你看幾乎我update到第三次
[01:46:00] 我幾乎就已經達到
[01:46:02] 真正數學上的
[01:46:04] 最接近的點
[01:46:06] 你以前一定算過這個
[01:46:08] 牛頓法非常厲害
[01:46:10] 好那現在回到這裡
[01:46:12] 我們現在人在這裡
[01:46:14] 我要走到我的最低點
[01:46:16] 我要走多遠呢
[01:46:18] 我就是用牛頓法
[01:46:20] 那牛頓法怎麼推的
[01:46:22] 你看一下
[01:46:24] gprom sk
[01:46:26] 所謂的gprom sk是什麼意思
[01:46:28] 就是代表這個切線
[01:46:30] 的
[01:46:34] 斜率
[01:46:36] 對吧
[01:46:38] 數學課
[01:46:40] 斜率那斜率怎麼算
[01:46:42] 就是你高度的變化
[01:46:44] 除上
[01:46:46] 寬度的變化
[01:46:48] 你高度就是g of sk
[01:46:50] 寬度的變化
[01:46:52] 就是sk減掉sk加1
[01:46:54] 對不對
[01:46:56] 這裡整理一下
[01:46:58] 牛頓法的update公式寫成
[01:47:00] sk加1等於sk減掉
[01:47:02] g of sk除上gprom sk
[01:47:04] 這就是牛頓法的公式
[01:47:11] 所以我們可以利用牛頓法
[01:47:13] 決定說
[01:47:16] 我們怎麼去
[01:47:18] 達到最好的
[01:47:21] 那個α
[01:47:23] 好回過頭來
[01:47:25] 我們回到剛剛一開始的這個式子
[01:47:32] 這裡的t度包括三角形的
[01:47:36] f of x
[01:47:38] 它扮演的角色就如同是
[01:47:40] 欸
[01:47:42] 牛頓法裡面的這個gx
[01:47:44] 所以
[01:47:46] 不要忘記
[01:47:48] 倒三角fx
[01:47:50] 已經是fx的一次微分了
[01:47:52] 它的角色就如同是這裡的
[01:47:54] gx
[01:47:56] 所以這裡的gprom x呢
[01:47:58] 就相當於是fx的二次微分的意思
[01:48:00] 二次微分的意思
[01:48:02] 所以
[01:48:04] to find a maximum or minimum of f
[01:48:06] we need to find x
[01:48:08] such that the gradient is 0
[01:48:10] 為了要找到
[01:48:12] 最好的那一組結
[01:48:14] x
[01:48:16] 我們其實要對f做一次微分
[01:48:18] 令它等於0
[01:48:20] 所以你看一下這個式子
[01:48:22] 所以相當於是
[01:48:24] 我們要找到適合的x
[01:48:26] 使得它帶進去之後等於0
[01:48:28] 你看一下這個臉
[01:48:30] 這個
[01:48:32] 跟我們牛頓法裡面
[01:48:34] 要求的
[01:48:36] 這個臉不是長一樣嗎
[01:48:38] 所以我們要如何找到最好的
[01:48:40] x使得
[01:48:42] f的gradient等於0呢
[01:48:44] 就等於是
[01:48:46] 我們要同樣的那個x能夠使得這裡的gx等於0
[01:48:48] 所以代入牛頓法
[01:48:50] gx
[01:48:52] in Newton's formula
[01:48:54] becomes the gradient of fx
[01:48:56] 所以說呢
[01:48:58] 原本update的那個式子
[01:49:00] 牛頓法的那個式子就變成是
[01:49:02] x等於是x減掉
[01:49:04] 這是gx
[01:49:06] 然後呢
[01:49:08] 除上gprom x
[01:49:10] 其實就是等於是fx的兩次微分
[01:49:12] 寫成這個樣子
[01:49:14] 它基本上
[01:49:16] 是一個hessian matrix
[01:49:18] 一個
[01:49:20] 多函數
[01:49:22] 的
[01:49:24] 一個多變數的函數
[01:49:26] 你對它做二次微分之後
[01:49:28] 它會變成一個矩陣
[01:49:30] 這個矩陣叫做
[01:49:32] hessian matrix
[01:49:34] 裡面的值hij
[01:49:36] 這個裡面的dij這個值
[01:49:38] 其實就是f
[01:49:40] 對xi做偏微分
[01:49:42] 再對xj做偏微分
[01:49:44] 的意思
[01:49:46] ok
[01:49:48] 如果你聽起來有點吃力呢
[01:49:50] 你就是要稍微複習一下以前的數學
[01:49:52] 這其實沒有到那麼難
[01:49:54] 那這裡寫成是hof f
[01:49:56] hof x的
[01:49:58] 什麼-1
[01:50:00] 這個是代表它其實是
[01:50:02] 除再分五的意思
[01:50:04] 但因為它是矩陣嘛
[01:50:06] 大家知道說在時數裡面我們做除法
[01:50:08] 在矩陣的運算裡面就相當於是在
[01:50:10] inverse的意思
[01:50:12] 好
[01:50:14] 總而言之呢整個update的式子是這樣
[01:50:16] 好
[01:50:18] 那local search method呢
[01:50:20] 它還是有可能會卡在local max嘛
[01:50:22] 卡在這個屋極上面
[01:50:24] 或者是平原上面
[01:50:26] 高原上面
[01:50:28] 那
[01:50:30] 所以即使你看起來用這種
[01:50:32] 比較高級的
[01:50:34] 厲害的continuous的這種
[01:50:36] update的方式呢
[01:50:38] 你還是有可能卡在local min
[01:50:40] 所以說呢
[01:50:42] 你可以搭配random restart的策略
[01:50:44] 或者是simulated annealing的策略
[01:50:46] 來解決
[01:50:48] 這個local max嘛的問題
[01:50:52] 好
[01:50:54] 這樣可以齁
[01:50:56] 那其實這個整個的update的
[01:50:58] 這個整個原理呢
[01:51:00] 後來其實它一直都沿用在
[01:51:02] 包含你現在一直
[01:51:04] 有些人可能都已經在寫
[01:51:06] 這個
[01:51:08] deep learning的程式對不對
[01:51:10] 好
[01:51:12] 那我們剛剛雖然講說
[01:51:14] 這個alpha
[01:51:16] 沒有alpha要怎麼決定
[01:51:18] 我們後來就變成是
[01:51:20] 我們常常是設定一個固定的
[01:51:22] 一個值啦
[01:51:24] 根據經驗設定一個固定的值
[01:51:26] 大概你跑夠多次
[01:51:28] 也不會差太多啦
[01:51:30] 那你如果現在已經開始有在寫
[01:51:32] 一些deep learning的
[01:51:34] 程式的話
[01:51:36] 其實這個alpha就是learning rate
[01:51:38] 的意思
[01:51:40] 你設定learning rate
[01:51:42] 其實就是這個意思
[01:51:44] 你根據你的gradient
[01:51:46] 你找到你的方向
[01:51:48] 你要調多多元
[01:51:50] 這是learning rate的意思
[01:51:52] 是同一件事
[01:51:55] 好那各式各樣的
[01:51:57] 最佳化問題有很多嘛
[01:51:59] 有一類的問題叫做constraint optimization problem
[01:52:01] 就是有一些限制的
[01:52:03] 最佳化問題
[01:52:05] 好
[01:52:07] 那它就會要求說
[01:52:09] 你這些變數一定要符合
[01:52:11] 某些規範
[01:52:13] 比如說我們剛剛講這個
[01:52:15] 羅馬尼亞的機場
[01:52:17] 這個很顯然它一定有一個規範就是說
[01:52:19] 你的S跟Y不可以是負的
[01:52:21] 這是肯定的
[01:52:23] 你地圖上怎麼會有什麼負的座標
[01:52:25] 那
[01:52:27] 有一類的constraint optimization
[01:52:29] problem呢
[01:52:31] 首先constraint optimization problem
[01:52:33] 這本身就是一門課
[01:52:35] 也可以是一本書
[01:52:37] 的內容
[01:52:39] 在constraint optimization
[01:52:41] 這個大範圍的情況之下
[01:52:43] 有一種類別的問題
[01:52:45] 叫做linear programming的問題
[01:52:47] again
[01:52:49] linear programming
[01:52:51] 也可以是一本書
[01:52:53] 也可以是一本課
[01:52:55] 那它只是constraint optimization problem
[01:52:57] 或者是convex optimization problem的
[01:52:59] 一個字集合而已
[01:53:01] 那他說呢
[01:53:03] 這種linear programming的問題呢
[01:53:05] 在實際的生活應用上
[01:53:07] 其實還蠻常出現的
[01:53:09] 它呢
[01:53:11] 它也許是最著名
[01:53:13] 而且被廣為研究的一類的問題
[01:53:15] 那
[01:53:17] 它是屬於convex optimization problem的一個special case
[01:53:23] 什麼叫做convex optimization呢
[01:53:25] 就是說它的constraint
[01:53:27] 它的objective function
[01:53:29] 可以寫
[01:53:31] 寫成一個convex function
[01:53:33] convex function就是
[01:53:35] convex function
[01:53:37] 我不想要講
[01:53:39] 它的數學定義
[01:53:41] 總之你可以自己去翻
[01:53:43] 來我們舉個例子
[01:53:45] 這也是
[01:53:47] 從我另外一門課的同學拿過來的
[01:53:49] 一個linear programming的問題呢
[01:53:51] 通常會長這個樣子
[01:53:53] 比如說
[01:53:55] 我要去minimize
[01:53:57] c transpose x
[01:53:59] 這是什麼東西
[01:54:01] 這其實沒有什麼了不起
[01:54:03] 學過線性代數的都知道
[01:54:05] 線性代數裡面我們喜歡
[01:54:07] 把內積兩項量的內積寫成矩陣相乘的形式
[01:54:09] 就長這樣
[01:54:11] 所以這其實就是
[01:54:13] c這個項量跟s這個項量在做內積
[01:54:15] 比如說
[01:54:17] c1s1加上c2s2加上c3s3
[01:54:19] c這個項量就是
[01:54:21] c1c2c3
[01:54:23] s這個項量就是
[01:54:25] s1s2s3對不對
[01:54:27] 所以c1s1加上c2s2
[01:54:29] 加上c3s3
[01:54:31] 我可以寫成這個樣子
[01:54:35] 我要去minimize這個值
[01:54:39] 但是呢
[01:54:41] 我要這個條件
[01:54:43] 線性代數整本課本整個學期
[01:54:45] 不是都在解這個問題嗎
[01:54:47] a s等於b
[01:54:49] 它是一個線性系統
[01:54:51] 就是說我的這些
[01:54:53] x應該要符合什麼特性
[01:54:55] 比如說都要大於0
[01:54:57] 然後
[01:54:59] s1加s2加s3
[01:55:01] 要等於7
[01:55:03] 2s1加上3s2
[01:55:05] 加上5s3
[01:55:07] 要等於5
[01:55:09] 合在一起就變成一個線性系統
[01:55:11] a s等於b
[01:55:13] 就是一個
[01:55:15] 你在objective function
[01:55:18] 是一個linear equation
[01:55:20] 是一個線性方程式
[01:55:22] 你的constraint也是一個線性方程式
[01:55:24] 你的constraint也是一個線性方程式
[01:55:26] 你的constraint呢
[01:55:28] 你的constraint呢
[01:55:30] 你可以是a s等於b
[01:55:32] 當然也有可能是a s大於b
[01:55:34] 或者是a s等於b
[01:55:36] 不過在最佳化的
[01:55:38] 不過在最佳化的
[01:55:40] 整個演算法的推導過程當中
[01:55:42] 整個演算法的推導過程當中
[01:55:44] 都會把這個a s等於b
[01:55:46] 都會把這個a s等於b
[01:55:48] 都改寫成這種形式
[01:55:50] 都改寫成這種形式
[01:55:52] 有一套SOP
[01:55:54] 有一套制式的做法
[01:55:56] 你可以把問題改寫一下
[01:55:58] 那我們就是專門針對這一類的
[01:56:00] 問題
[01:56:02] 有一些演算法來求解
[01:56:04] 當然這是另外一門課的內容
[01:56:06] 國道精深的
[01:56:08] 最佳化導論的內容
[01:56:10] 最佳化導論的內容
[01:56:12] 那麼舉一個例子讓大家有感覺
[01:56:14] 這其實很實際的例子
[01:56:16] 這一類的
[01:56:18] linear programming的研究
[01:56:20] 大約是在二次大戰期間
[01:56:22] 大約是在二次大戰期間
[01:56:24] 快速的發展
[01:56:28] 所以後來它廣泛的用在
[01:56:30] 像經濟學
[01:56:33] 作業研究的這個領域裡面
[01:56:35] 作業研究的這個領域裡面
[01:56:37] 為什麼在戰爭期間
[01:56:39] 它發展速度那麼快呢
[01:56:41] 我們看一下這個例子
[01:56:43] 它說現在有一個製造商
[01:56:45] 它會製造四種產品
[01:56:47] 一二三四這四種產品
[01:56:51] 那為了要製作出這四種產品
[01:56:53] 那為了要製作出這四種產品
[01:56:55] 我可能需要一些人工
[01:56:57] 我要A這個原料
[01:56:59] 我要B這個原料
[01:57:01] 我要A這個原料
[01:57:03] 所以這四種產品
[01:57:05] 都得要有這三種資源
[01:57:07] 都得要有這三種資源
[01:57:09] 才能夠完成
[01:57:11] 那生產每一種產品
[01:57:13] 它對於人力
[01:57:15] 以及材料的需求不一樣
[01:57:17] 那為了要決定
[01:57:20] 我的
[01:57:22] 我的製造的這個安排
[01:57:24] 我到底要製造
[01:57:26] 一號產品要製造多少份
[01:57:28] 二號產品要多少份
[01:57:30] 三號產品要多少份
[01:57:32] 我基本上這個就是一個最佳化問題
[01:57:34] 我基本上這個就是一個最佳化問題
[01:57:36] 這個製造商呢
[01:57:38] 不能夠用超出你現有資源
[01:57:40] 不能夠用超出你現有資源
[01:57:42] 來製造這些產品
[01:57:44] 所以底下這個例子就是說
[01:57:46] 我要製造一號產品呢
[01:57:48] 我要製造一號產品呢
[01:57:50] 一種人 州
[01:57:52] 一個 One May Week
[01:57:54] 然後6公斤的A跟三合的B
[01:57:56] 然後呢
[01:57:58] 二號產品呢
[01:58:00] 我要兩個人 州
[01:58:02] 5公斤的A
[01:58:04] 4合的B
[01:58:06] 所以我到底
[01:58:10] 1234這四種產品
[01:58:12] 我要生產幾份
[01:58:14] 那我們先假設
[01:58:16] 一號產品生產S1份
[01:58:18] 二號產品生產S2份
[01:58:20] 一匙類推
[01:58:22] 我只有20個人中
[01:58:24] 我只有100公斤的A材料
[01:58:26] 我只有75盒的B材料
[01:58:29] 所以我的限制就是
[01:58:33] X1乘以1加上2X2
[01:58:39] 加上1乘以X3加上2乘以X4
[01:58:42] 一定要小於等於20
[01:58:44] 因為這是我所有的人力資源總和
[01:58:47] 你生產這些產品
[01:58:50] 你用的人力資源一定要小於等於20
[01:58:53] 那同樣的
[01:58:55] 6乘X1加上5乘X2加上3乘X3加上2乘X4
[01:58:59] 一定要小於等於100
[01:59:01] 然後呢
[01:59:03] 一樣
[01:59:04] 針對B這個材料
[01:59:06] 它要符合這個條件
[01:59:09] 這個是我的限制
[01:59:11] 那我想要
[01:59:12] 我可能我要做的事情可能是說
[01:59:14] 我這四個產品
[01:59:16] 1234這四個產品
[01:59:18] 它的售價
[01:59:20] 可能不一樣
[01:59:21] 假設我這個生產商
[01:59:23] 我的目標是
[01:59:24] 我這一週
[01:59:26] 我這個整個生產的結果
[01:59:29] 我希望能夠獲得最高的利潤
[01:59:34] 所以我要去Maximize
[01:59:36] 假設
[01:59:38] 一號產品
[01:59:39] 它每一個賣100塊
[01:59:41] 100乘X1
[01:59:43] 二號產品每一個賣50塊
[01:59:45] 加上50乘以X2
[01:59:47] 一直類推
[01:59:48] 我要去Maximize
[01:59:50] 我所得
[01:59:51] 我得到的利潤
[01:59:53] 但是呢
[01:59:54] 我要怎麼樣
[01:59:55] 我要去符合這個條件
[01:59:58] 所以你想一下
[01:59:59] 我剛剛的這個問題
[02:00:00] 是不是就是這種形式的問題
[02:00:03] 這就是一個Linear Programming的問題
[02:00:07] 好
[02:00:08] 那
[02:00:09] 這種問題怎麼求解呢
[02:00:11] 很抱歉
[02:00:12] 這個是一整個學期的課
[02:00:15] 有興趣的話請去修最佳化導論
[02:00:18] 我們在這門課裡面呢
[02:00:20] 我們就不再講
[02:00:21] 怎麼求解
[02:00:22] 這裡
[02:00:23] 這是一個博大計深的學問
[02:00:24] 有一大堆的最佳化的這個演算法在裡面
[02:00:30] 好
[02:00:32] 來
[02:00:33] 那
[02:00:34] 這是一個小段落
[02:00:35] 我們來看一下
[02:00:37] 有沒有問題
[02:00:39] 重新計算時我們理論上會偏向找
[02:00:46] 和原先結果差距較遠的解
[02:00:50] 那有沒有可能在計算上
[02:00:52] 會一直引導我們回取原先結果
[02:00:55] 例如一個寬度很高的丘陵
[02:00:58] 在遠處有一個很窄的山峰
[02:01:04] 你說在重新計算時
[02:01:12] 我們理論上會找
[02:01:14] 離原先結果比較遠的解
[02:01:17] 好
[02:01:18] 這句話呢
[02:01:19] 對
[02:01:21] 但是也錯
[02:01:23] 這其實在大部分的演算法設計裡面
[02:01:26] 這一樣又跟人生的大道理一樣
[02:01:28] 你在演算法一開始跑的時候
[02:01:31] 我們的確傾向於
[02:01:32] 一次就走遠一點
[02:01:36] 這也牽涉到我們剛剛前面講的
[02:01:39] 在continuous space裡面
[02:01:41] 我們在update我們原本的解X的時候
[02:01:44] 我們那個α
[02:01:45] 其實有一個策略是
[02:01:47] 當我演算法一開始開跑的時候
[02:01:49] 我的α要大一點
[02:01:52] 然後呢
[02:01:53] 等到你iteration跑很多很多次了
[02:01:55] 我傾向於就把α再縮減一點
[02:01:58] 然後再慢慢縮減一點
[02:01:59] 所以你講這句話
[02:02:01] 對
[02:02:02] 也不對
[02:02:03] 對是指說
[02:02:04] 在一開始跑的時候呢
[02:02:05] 我們的確傾向於
[02:02:07] 可以大步走
[02:02:10] 一開始找遠一點的
[02:02:12] 可是等到你跑了一萬個iteration
[02:02:15] 或多少個iteration之後呢
[02:02:17] 你要慢慢的
[02:02:19] 不要那麼的冒險
[02:02:21] 你的α就小一點
[02:02:23] 你就會找跟你周圍鄰居相對近的一點解
[02:02:27] 因為當你已經跑了一萬個iteration之後
[02:02:30] 你應該有足夠的自信
[02:02:31] 你已經找到一個還蠻不錯的解了
[02:02:34] 這樣瞭解嗎
[02:02:39] 那你說有沒有可能在計算上
[02:02:41] 引導我們去找原先
[02:02:43] 一直去找原先的解
[02:02:45] 我覺得不能排除有這種情況
[02:02:49] 不排除有這種情況
[02:02:51] 你如果在某種
[02:02:52] 剛好某種很特殊的case裡面
[02:02:56] 它就在兩邊在那邊震盪
[02:02:58] 是有可能的
[02:03:00] 所以我們剛剛在講說
[02:03:02] 我們那個α
[02:03:04] 事實上是可以隨著時間變動的
[02:03:06] 我們的seminary annealing的那個t
[02:03:09] 也是隨著時間變動的
[02:03:11] 那一旦有變動
[02:03:13] 你從這邊走過去
[02:03:15] 你下一次不見得再走回來了
[02:03:17] 因為你的有一些參數已經變了
[02:03:20] 這樣瞭解嗎
[02:03:21] 所以附帶一提
[02:03:22] 如果現在現場或者是線上的同學
[02:03:25] 有些人你已經在跑deep learning的程式了
[02:03:29] 你就會發現
[02:03:30] 你的learning rate
[02:03:32] 很多人會建議說
[02:03:35] 你在前面100個aerop的時候
[02:03:37] 你learning rate是多少
[02:03:38] 你過了100個aerop之後
[02:03:40] 每過50個aerop
[02:03:41] learning rate就乘上0點多
[02:03:44] 是不是這個意思
[02:03:46] 就是這樣的意思
[02:03:48] 一開始冒險一點
[02:03:50] 後來就越來越保守
[02:03:52] 所以這個最佳化
[02:03:57] 跟我們人生的哲藝是一樣的
[02:03:59] 我講過很多次
[02:04:04] 在座的有沒有什麼問題
[02:04:09] 這只有兩根
[02:04:10] 這是local沒什麼根
[02:04:12] 這是最大的沒什麼
[02:04:13] 然後這個都沒什麼
[02:04:14] 山丘就是
[02:04:16] 所以只要在那個範圍內
[02:04:18] 都一定會遇到阿宗
[02:04:20] 然後一個很窄的山峰
[02:04:22] 所以它只有在那個階段
[02:04:24] 往上跳就會找到那個最大的
[02:04:26] 它意思應該是一個比較奇怪的地方
[02:04:29] 所以我剛剛講了
[02:04:31] 如果在一個這麼特別的狀態之下
[02:04:36] 有可能就是會發生
[02:04:38] 剛剛同學所講的
[02:04:40] 這麼奇怪的事情
[02:04:42] 不過那個
[02:04:43] 我覺得那個都是要
[02:04:44] 特殊設計的問題才會這樣子
[02:04:47] 我們一般在做真正實體世界的
[02:04:51] 最佳化的時候
[02:04:53] 是很少遇到這樣子的東西的
[02:04:55] OK
[02:04:58] 那我們講到這邊再休息一下
[02:05:00] 再來
[02:05:01] 範圍內呢
[02:16:36] 有一類的問題是屬於這種
[02:16:41] 在之前講
[02:16:50] 有一些題目是
[02:16:52] 你可以完全知道
[02:16:54] 它整體的狀態
[02:16:57] 比如說八黃或五穩
[02:17:00] 那有一些呢
[02:17:02] 是你只能夠部分觀察到
[02:17:05] 現有相對侷限範圍內的狀態
[02:17:11] 比如說
[02:17:12] Here climate
[02:17:13] 你從某個地方出發
[02:17:14] 你只看到周圍的鄰居的一小部分
[02:17:17] 所以你就做local search
[02:17:19] 所以你如果只有一部分的觀察
[02:17:25] 那就所謂的
[02:17:27] Search with partial observation
[02:17:29] 那我們這裡舉一個例子
[02:17:31] 假設有一個機器人
[02:17:34] 他是在一個類似迷宮的環境裡面
[02:17:37] 他大概長這樣
[02:17:39] 在一個類似迷宮的環境裡面
[02:17:41] 然後呢
[02:17:43] 他配備了四個sensor
[02:17:47] 這四個sensor
[02:17:49] 分別可以去感應
[02:17:50] 東西南北四個方向
[02:17:52] 有沒有障礙物
[02:17:54] 那假設呢
[02:17:56] 這些sensor
[02:17:58] 都永遠都正常運作
[02:18:02] 那如果是這樣子的話呢
[02:18:04] 而且呢這個機器人呢
[02:18:06] 他知道這整個環境的地圖
[02:18:12] 那他說呢
[02:18:14] 這個機器人的導航系統呢
[02:18:16] 壞掉了
[02:18:17] 所以說呢
[02:18:18] 他只能夠做移動這個動作
[02:18:22] 那他可能會隨機的從
[02:18:24] 四個可以走的這個方塊裡面
[02:18:28] 去進行走動
[02:18:30] 那我們的目標呢
[02:18:32] 就是說
[02:18:33] 當他具備的能力是什麼
[02:18:35] 他能夠去感測一下
[02:18:37] 周圍的有沒有障礙物
[02:18:40] 然後呢
[02:18:41] 你可以走向沒有障礙物那個地方
[02:18:44] 走過去
[02:18:45] 然後他去感測一下
[02:18:47] 周圍的障礙物這樣子
[02:18:49] 然後呢
[02:18:50] 他也擁有一整個地圖
[02:18:53] 在這樣的情境設計之下呢
[02:18:55] 我們的任務是要去決定
[02:18:57] 目前這隻機器人
[02:19:00] 他是走到哪個位置吧
[02:19:02] 那這個問題
[02:19:06] in this case
[02:19:07] 這個case他其實也不難
[02:19:08] 比如說假設一開始
[02:19:11] 我們只知道說
[02:19:12] 我們不知道他在哪裡
[02:19:14] 但是我們有這個地圖
[02:19:16] 然後呢
[02:19:17] 一開始呢
[02:19:18] 這個機器人
[02:19:19] 他就透過他的sensor
[02:19:22] 然後就感應到說
[02:19:24] 北邊
[02:19:25] 南邊跟西邊
[02:19:26] 有障礙物
[02:19:28] ok
[02:19:29] 那如果是這樣子的話
[02:19:30] 其實我們很輕易的就可以知道說
[02:19:33] 他應該在這幾個位置
[02:19:36] 因為假設感測器永遠都是
[02:19:39] 百分之百完美運作的話
[02:19:42] 因為像這個位置
[02:19:43] 他的北邊
[02:19:44] 西邊跟南邊都是障礙物
[02:19:47] 對不對
[02:19:48] 這個位置也是啊
[02:19:49] 北邊這是一個圍牆嘛
[02:19:51] 北邊西邊南邊有障礙物
[02:19:54] 所以他應該在這邊
[02:19:56] 或者在這邊
[02:19:57] 或者在這邊
[02:19:58] 或者在這邊
[02:19:59] 這樣
[02:20:00] 所以這第一個時間點
[02:20:02] 我們大概就可以大幅縮減
[02:20:04] 他可能所在的位置
[02:20:06] 然後他就可能就做了某一個動作
[02:20:09] 那看起來他一定是往東邊走嘛
[02:20:11] 因為
[02:20:12] 北
[02:20:13] 南
[02:20:14] 西
[02:20:15] 都有障礙物
[02:20:16] 那就往東邊走
[02:20:17] 往東邊走之後呢
[02:20:18] 下一個瞬間
[02:20:19] 他又再感測一次
[02:20:21] 就發現了
[02:20:22] 北邊跟南邊
[02:20:24] 有障礙物
[02:20:26] 那其實我們就可以很輕易的推斷出
[02:20:29] 在這個case裡面
[02:20:30] 他一定是在這個位置
[02:20:32] 對不對
[02:20:33] 因為你這個如果往右走
[02:20:35] 北邊就沒有障礙物啊
[02:20:36] 你這往右走北邊沒有障礙物
[02:20:38] 你這個如果往右走南邊沒有障礙物啊
[02:20:40] 只有你這個往右走北邊跟南邊有障礙物
[02:20:44] 所以我們就可以去推算出
[02:20:46] 他真正的位置是如何
[02:20:48] 好
[02:20:49] 那當然這是一個簡單的例子啦
[02:20:51] 以這個例子來講
[02:20:53] 我們如果已經知道地圖了
[02:20:55] 我們用一些規則
[02:20:56] 我們大概就可以知道人在什麼位置
[02:20:59] 但是如果你把這個問題延伸到
[02:21:02] 更複雜的情況
[02:21:04] 比如說今天你的感測器
[02:21:07] 事實上在未來
[02:21:08] 我們有一些內容就會提到
[02:21:10] 假設你的感測器
[02:21:12] 只有八成是對的
[02:21:15] 有兩成有可能回答給你錯的答案
[02:21:20] 這個時候呢
[02:21:21] 你就要花更多的時間
[02:21:23] 更多的力氣
[02:21:24] 去推算你可能在哪個位置
[02:21:27] 那這個是之後會出現
[02:21:31] 好
[02:21:32] 那這個chapter的最後一部分
[02:21:35] 在講的是online search
[02:21:37] 有一大堆的名詞啊
[02:21:39] 他說到目前為止呢
[02:21:41] 我們講的這些agent呢
[02:21:42] 大部分是offline search
[02:21:44] 就我告訴你一個環境
[02:21:45] 然後你就去解它
[02:21:47] they compute a solution
[02:21:49] after setting foot in the real world
[02:21:51] and then execute the solution
[02:21:54] 那online search的agent呢
[02:21:56] interlive computation and action
[02:21:59] 就是他一邊做動作
[02:22:00] 做完動作之後呢
[02:22:01] 又去感測環境
[02:22:02] 然後再去決定下一個動作
[02:22:05] 那所以最經典的例子呢
[02:22:09] 就是我今天把一個robot
[02:22:12] 丟在一個新的這個
[02:22:15] beauty裡面去
[02:22:16] 然後請他呢
[02:22:18] 自己去走
[02:22:19] 然後去建構地圖
[02:22:21] 其實就是你家的掃地機器人啦
[02:22:23] 你家的掃地機器人就是這樣
[02:22:25] 所以他在做的是一個online search
[02:22:28] 即時的有根據
[02:22:30] 觀察到的東西以及過去的歷史
[02:22:33] 來去建構你對於這個世界的理解
[02:22:36] 這樣
[02:22:37] 那online search演算法呢
[02:22:39] 有幾個特性
[02:22:41] 它規定呢
[02:22:42] 這個agent只知道說
[02:22:44] 他可以做什麼動作
[02:22:46] 以及他做了某一個動作之後
[02:22:50] 得到某一個結果
[02:22:52] 你的cost是多少
[02:22:54] 以及呢
[02:22:55] 你是不是已經完成了你的目的
[02:22:57] 這樣子
[02:22:58] 那
[02:23:00] 你在真正做這個動作
[02:23:03] 你在S這個地方出發
[02:23:05] 你做了A這個動作
[02:23:07] 你在真正得到這個動作的結果之前呢
[02:23:11] 你是不會知道
[02:23:13] 你做這個動作要花的花費有多少
[02:23:18] ok
[02:23:23] 那所以這是另外一個例子啊
[02:23:25] 在一個類似迷宮的環境裡面
[02:23:28] 你要從S走到G
[02:23:30] ok
[02:23:31] 那
[02:23:33] 你真正你從S我們一看
[02:23:36] 我們就知道說S要往右往右
[02:23:38] 往上往上
[02:23:39] 就得到G了嘛
[02:23:41] 那是因為你從上帝的視角來看
[02:23:43] 如果你今天你只知道S
[02:23:45] 然後呢
[02:23:46] 你有一些感測器
[02:23:47] 你發現你上面也可以走
[02:23:48] 右邊也可以走嘛
[02:23:49] 那你可能就會走到上面
[02:23:51] 走到上面你再感測一下
[02:23:53] 你才發現說
[02:23:54] 欸
[02:23:55] 是這個
[02:23:57] 上面右邊左邊都不能再走了
[02:23:59] 你只好再走回來
[02:24:00] 所以你就浪費了一步了
[02:24:04] 那你就是得要一邊走
[02:24:05] 一邊受到阻擋
[02:24:07] 然後再重新
[02:24:09] 然後再一路往下走
[02:24:10] 就是所謂的online search
[02:24:12] 好
[02:24:14] 所以說呢
[02:24:15] finally the agent might have access to an admission
[02:24:18] ok
[02:24:19] 那這個是如果你是盲目的走
[02:24:21] 反正你就是到處亂踹
[02:24:22] 從S要走到G
[02:24:24] 那其實這個很像是什麼
[02:24:26] 我們在上一張
[02:24:28] 我們就講過
[02:24:29] 你可以用比如說DFS
[02:24:31] 或者是BFS
[02:24:33] 對不對
[02:24:34] 你可以做所謂的盲目的搜尋
[02:24:36] 那同樣的
[02:24:37] 如果你有heuristic function的話
[02:24:41] 對不對
[02:24:42] 或者說
[02:24:43] 甚至你是automisible的
[02:24:44] automisible的heuristic function的話
[02:24:47] 你就可以用A star search
[02:24:49] 對不對
[02:24:50] 來去找到最佳的那一組接
[02:24:52] 好
[02:24:53] 如果你走迷宮來講
[02:24:55] 你可以把這個題目
[02:24:57] 把這個問題描寫成在一棵樹上面走
[02:25:03] ok
[02:25:04] 如果是這個題目的話
[02:25:07] 那當然不見得每個題目都有辦法
[02:25:09] 所以這裡你會遇到各式各樣不同的題目
[02:25:12] 那你在評估一個online search的效能
[02:25:17] 它的演算法的效能的時候呢
[02:25:20] 你當然你可以去算它的cost
[02:25:24] 你當然希望你的cost能夠越低越好
[02:25:27] 那這裡的cost的定義可能是
[02:25:30] 比如說你走的步
[02:25:32] 步數要越少越好
[02:25:35] 或者說你走到某些地方
[02:25:37] 可能會扣很多分
[02:25:39] 那個cost就很高
[02:25:41] 也是有可能
[02:25:44] 那所以如果在走地圖這個例子來講的話呢
[02:25:47] the cost is the total pass cost
[02:25:51] 那你開發出好多不同的演算法
[02:25:58] 都可以從起點走到終點
[02:26:00] 那你如何去評估
[02:26:02] 哪一個演算法比較好呢
[02:26:04] 因為最終其實大家都能夠走到終點啦
[02:26:07] 那有一種方式就是
[02:26:09] 你去算它的所謂的competitive ratio
[02:26:13] competitive ratio是說呢
[02:26:15] compare its cost with the pass cost of the pass
[02:26:19] the agent will follow if he knew the search space in advance
[02:26:23] 就是它跟最好的情況比起來
[02:26:27] 最好的情況是它已經知道整個地圖的結構了
[02:26:31] 所以它可以算出一個
[02:26:34] 最佳解
[02:26:36] 跟你不知道地圖的結構
[02:26:38] 你在那邊搜尋
[02:26:39] 你在那邊找
[02:26:41] 那相較之下
[02:26:43] 你的這個cost
[02:26:45] 花的是完美的多少倍
[02:26:49] 這叫competitive ratio這樣子
[02:26:52] 那我們當然希望說
[02:26:53] 這個competitive ratio越小越好
[02:26:55] 因為它就是越接近最佳解的意思
[02:27:00] 好
[02:27:02] 所以說
[02:27:04] 這個online agent呢
[02:27:06] 基本上最後
[02:27:08] 它可以知道說它走到哪一個
[02:27:11] telling what state it has reached
[02:27:14] 然後你知道你
[02:27:18] 你可以把之前你走過的那個歷史
[02:27:22] 都儲存下來
[02:27:23] 所以你對於這整個環境
[02:27:25] 你就越來越理解
[02:27:27] 那所以你對於目前整個地圖環境的理解
[02:27:32] 就可以幫助你去如何走到
[02:27:36] 你怎麼走下一步
[02:27:38] 你可以去做最好的一個決策
[02:27:40] 所以你一邊在決定你怎麼走
[02:27:42] 然後一邊執行完這個動作之後
[02:27:44] 你也去觀察新的這個環境是怎麼樣
[02:27:49] 所以說呢
[02:27:52] 這裡就提到說
[02:27:53] 你可能你可以用DFS
[02:27:56] 來做這樣子的一個問題
[02:28:00] 好
[02:28:02] 那here climbing的話呢
[02:28:03] 其實也是可以這樣
[02:28:05] 就是說
[02:28:06] Climbing你是站在某一個點
[02:28:08] 看它周圍的環境
[02:28:10] 對不對
[02:28:11] 然後呢
[02:28:12] 如果可以走
[02:28:13] 那你就走過去
[02:28:14] 或者是說
[02:28:15] 你用某種譬如Risk的話
[02:28:17] 你知道說
[02:28:18] 往右走其實更接近你的目標
[02:28:21] 好
[02:28:22] 相當於這個往右走
[02:28:23] 右邊的這個鄰居
[02:28:25] 是一個比往上走
[02:28:27] 這個鄰居更好的一個鄰居
[02:28:29] 那你就選擇往右走
[02:28:31] 好
[02:28:32] 所以你也可以把
[02:28:33] 之前我們在這一張
[02:28:34] 先前所講到的一些
[02:28:36] 策略也用進來
[02:28:38] OK
[02:28:40] 那所以說
[02:28:41] 雖然我們這裡講Online Search Agent
[02:28:44] 或者這個Online Search Agent
[02:28:46] 但它其實只是說
[02:28:48] 你不同的問題的定義
[02:28:51] 雖然說我們講了好多的Search
[02:28:53] 對不對
[02:28:54] Online Search
[02:28:55] Bean Search
[02:28:56] 然後什麼什麼Search
[02:28:57] 什麼什麼Search
[02:28:58] 但雖然它都叫Search
[02:29:00] 但是有時候它們的地位
[02:29:02] 是不太一樣的
[02:29:03] 有的時候是針對不同問題的定義
[02:29:05] 有的時候是不同的
[02:29:06] 不同的搜尋的策略
[02:29:08] 有的時候根本就是一種演算法
[02:29:10] 但是我們都叫它什麼什麼Search
[02:29:13] OK
[02:29:14] 好
[02:29:15] 那所以
[02:29:17] 最後面這裡就稍微講一下
[02:29:19] 這個所謂的Online Local Search
[02:29:21] 這樣子
[02:29:22] 所以最後面這一塊
[02:29:23] 是比較聊聊天的
[02:29:25] 比較沒有具體的例子
[02:29:29] 好
[02:29:30] 所以講到這裡
[02:29:31] 我們就完成了第四章
[02:29:37] 接下來呢
[02:29:39] 我們就要進入到第十二章
[02:29:42] 一下怎麼跳那麼多
[02:29:44] 好
[02:29:46] 還記得我們在講那個
[02:29:48] 人工智慧的歷史的時候
[02:29:50] 我們就講說
[02:29:51] 在什麼1950年代
[02:29:54] 1955年
[02:29:55] 1956年出現了AI這個詞
[02:29:57] 後來就開始大幅的進展
[02:29:59] 然後大概到了
[02:30:01] 1980年代開始
[02:30:05] 就是會引入這個機率來進行
[02:30:09] 這個AI的發展
[02:30:11] 對不對
[02:30:12] 所以我們現在呢
[02:30:13] 其實就是直接從
[02:30:15] 整個General的AI的一些定義
[02:30:19] 我們直接就跳到1980年代1990年代
[02:30:22] 中間大概在冷戰時期
[02:30:27] 那時候大部分的AI的學者
[02:30:30] 在走的是符號邏輯學派
[02:30:33] 的那一些東西
[02:30:35] 因為到現在已經
[02:30:37] 真的幾乎沒有了
[02:30:39] 所以我們完全跳過
[02:30:42] 所以你從第四章
[02:30:44] 所以你如果去看我們那本很厚的書
[02:30:46] 第二個part
[02:30:48] 什麼五六七八九十
[02:30:50] 這幾章
[02:30:51] 都在講那些符號邏輯學派的那些東西
[02:30:54] 那因為在現在這個年代
[02:30:57] 我等一下要講的這個東西
[02:30:59] 你都覺得很老了
[02:31:00] 更不用講那些東西就更老了
[02:31:02] 所以我們直接跳過
[02:31:04] 我們直接進入到第十二章
[02:31:06] 第十二章呢
[02:31:09] 我們開始要考慮一些所謂的
[02:31:12] 不確定性進來
[02:31:14] 所以在剛剛前面的第四章
[02:31:17] 我們已經有稍微講到一點點
[02:31:19] 就是說
[02:31:20] 如果今天這個環境裡面的資訊
[02:31:22] 我們只能夠部分觀察到
[02:31:25] 所以當我們在做一些決策的時候
[02:31:27] 有時候我們得要
[02:31:29] 我們可以盲目的嘗試
[02:31:33] 這是blind search
[02:31:35] 那如果我們多知道一點點
[02:31:38] 我們有某種heuristic的話
[02:31:40] 我們可以用A star search
[02:31:42] 對不對
[02:31:44] 好
[02:31:45] 那如果我們沒有heuristic
[02:31:47] 或者說我們有heuristic
[02:31:49] 我們如果去評判
[02:31:50] 走哪一步會比較好
[02:31:52] 那這時候呢
[02:31:53] 就有人提出說
[02:31:55] 我們應該要引入機率
[02:31:57] 因為機率天生
[02:31:59] 就是可以拿來表達所謂的不確定性
[02:32:02] 某一條路可能有用的機率有多高
[02:32:07] 你可以去進行這樣的一個評判
[02:32:09] 所以第十二章呢
[02:32:11] 我們其實主要是為大家複習機率
[02:32:15] 那你在整個AI發展的過程當中
[02:32:18] 你可以把它自己想像成
[02:32:20] OK我現在已經開始進入到90年代了
[02:32:23] 1990年代了
[02:32:25] 那種感覺
[02:32:27] 好
[02:32:29] 那他說啊
[02:32:30] 為什麼要引入uncertainty
[02:32:32] 不確定性
[02:32:34] 我們需要處理不確定性
[02:32:36] 因為很多時候呢
[02:32:37] 我們只有partial observable
[02:32:41] 我們只是部分知道
[02:32:43] 我們所處在這個agent
[02:32:45] 只有部分知道你這整個環境的資訊
[02:32:48] 這整個PAS你只有部分知道的資訊
[02:32:52] 或者是說呢
[02:32:53] 你是non-determinant
[02:32:57] 還記得這什麼意思嗎
[02:33:00] 就是說
[02:33:01] 有沒有你還記得那個
[02:33:02] 吸塵器的例子
[02:33:04] 假設你叫它往右轉
[02:33:06] 它沒有真的往右走呢
[02:33:09] 因為機器故障的關係
[02:33:11] 或者因為某種控制什麼的關係
[02:33:13] 或者是某一些noise的關係
[02:33:15] 你叫它往右走
[02:33:16] 它就沒有真的往右走
[02:33:18] 實體世界有這種情況啊
[02:33:20] 這就是non-deterministic
[02:33:24] 或者是說你根本就是
[02:33:25] 環境也看得不清不楚
[02:33:27] 然後呢
[02:33:28] 你這臺機器也爛爛的
[02:33:30] 那種一些爛東西
[02:33:33] 然後呢
[02:33:34] 你叫它做一個什麼事情
[02:33:35] 然後就是
[02:33:36] 就是做不好
[02:33:38] 也許混合在一起
[02:33:40] 所以你的agent
[02:33:41] 就是必須要處理一些uncertainty
[02:33:46] 那agent呢
[02:33:48] may never know
[02:33:50] for certain what state it's in
[02:33:53] or where it will end up
[02:33:55] after a sequence of actions
[02:33:57] 所以很多實體世界當中的情況是這樣子的
[02:34:02] 那底下呢
[02:34:03] 我們就要來
[02:34:04] 主要用一個例子
[02:34:05] 來引導這整個說明
[02:34:09] 牙醫的例子
[02:34:11] OK
[02:34:12] 假設呢
[02:34:13] 牙痛了
[02:34:14] 你牙痛了
[02:34:15] 你就看牙醫
[02:34:16] 這樣子
[02:34:17] 欸
[02:34:18] 如果你牙痛
[02:34:19] 你就看牙醫
[02:34:20] 我們現在牙醫要進行診斷呢
[02:34:22] 怎麼診斷
[02:34:23] 我們先試著
[02:34:25] 寫規則看看
[02:34:27] 所以
[02:34:28] Write a rule for dental diagnosis
[02:34:31] using propositional logic
[02:34:33] 這個propositional logic
[02:34:35] 就是我們跳調的那幾個chapter
[02:34:38] 在講的東西
[02:34:41] 它花了好幾個chapter
[02:34:42] 在講這種propositional logic
[02:34:45] 那我們來看一下
[02:34:46] 我們來看一下
[02:34:48] 為什麼寫propositional logic
[02:34:50] 不會work
[02:34:52] 所以可能是這樣啊
[02:34:53] 今天你牙痛了
[02:34:55] 你去看牙醫
[02:34:56] 假設這個牙醫心中
[02:34:58] 只有一條規則就是
[02:35:00] 你牙痛是不是
[02:35:01] 啊你蛀牙了
[02:35:03] 這樣子
[02:35:04] 你覺得這樣對嗎
[02:35:06] 事實上常常是不對的
[02:35:08] 你今天是會牙痛
[02:35:11] 有可能是引發
[02:35:13] 有可能
[02:35:14] 我就
[02:35:15] 我聽到你的描述說你牙痛
[02:35:17] OK
[02:35:18] 如果我給你的結論
[02:35:21] 只有唯一一個就是
[02:35:22] 你有蛀牙
[02:35:24] 那這樣子常常會判斷錯
[02:35:27] 事實上這個規則有可能是
[02:35:29] 你牙痛是不是
[02:35:30] OK
[02:35:31] 你可能是因為蛀牙
[02:35:33] 或者是你的牙齦有問題
[02:35:36] 或者是
[02:35:37] 你嘴巴有潰牙
[02:35:39] 你嘴巴破
[02:35:42] 或者是怎麼樣怎麼樣怎麼樣
[02:35:44] 或者是怎麼樣怎麼樣怎麼樣
[02:35:46] 這樣子才是一個距離實體環境
[02:35:49] 比較正確的一個描述嘛
[02:35:51] 對不對
[02:35:52] 好
[02:35:53] 當然不幸的是
[02:35:55] 你為了要讓這整個描述變得
[02:35:58] 合理而完整
[02:36:00] 你這個後面這個or
[02:36:02] or or
[02:36:03] 你可能or不完啊
[02:36:04] 你這個條件太多了
[02:36:06] OK
[02:36:08] 你牙痛
[02:36:09] 你牙痛說不定是因為
[02:36:10] 你剛剛走路撞到門
[02:36:12] 你牙齒在那邊流血啊
[02:36:14] 對不對
[02:36:15] 有可能是這樣啊
[02:36:16] 你有可能是神經痛啊
[02:36:18] 你牙沒有問題
[02:36:20] 你是神經在痛啊
[02:36:21] 好
[02:36:22] 各自怎麼樣
[02:36:23] 好那你說
[02:36:24] 不然這樣子
[02:36:25] 我可不可以改過來
[02:36:26] 寫另外一個規則
[02:36:27] 就是說
[02:36:28] 你只要有蛀牙
[02:36:30] 你就會牙痛這樣子
[02:36:32] 但其實這個規則也是錯的
[02:36:36] 也是錯的
[02:36:38] 不是所有的蛀牙都會造成牙痛啊
[02:36:42] 這樣子
[02:36:43] 所以這個也不對
[02:36:45] 好所以這裡就用這個例子來告訴你說
[02:36:48] 如果你要用logic
[02:36:52] propositional的方式
[02:36:54] 來診斷牙痛的話
[02:36:58] 這根本就不切實際
[02:37:00] 所以這直接打臉
[02:37:02] 有沒有1960年代當時
[02:37:04] 理論那些
[02:37:06] 特級符號學派
[02:37:08] 當然當時還很久以前啊
[02:37:10] 他們就弄很多這種logic
[02:37:12] 他就不是
[02:37:13] 我們在開學立唐課都講說
[02:37:15] OK
[02:37:16] 只要你能夠把你的知識寫成logic
[02:37:18] 我就一定有辦法證明啊
[02:37:20] 對不對
[02:37:21] 就講一大堆嘛
[02:37:22] 但你就從這個簡單的例子裡面
[02:37:25] 你就知道說
[02:37:26] 你光牙痛診斷這件事情
[02:37:28] 你就沒有辦法完整的寫出
[02:37:32] 原因是什麼
[02:37:33] 第一個
[02:37:34] laziness
[02:37:36] 懶惰
[02:37:37] 就是說
[02:37:38] 你不管你這個proposition
[02:37:40] 你是前項還是後項
[02:37:42] 可能都有一大堆要寫的
[02:37:45] 而且搞不好寫不完
[02:37:47] 你無法窮取出所有的原因
[02:37:49] 或者窮取出所有的結果
[02:37:52] 這是第一種阻礙
[02:37:55] 第二種阻礙是
[02:37:56] 有些東西
[02:37:58] 你可能由到目前為止
[02:38:01] 你也不知道為什麼會
[02:38:05] 會這樣子
[02:38:09] 當然牙痛可能已經研究很透徹了
[02:38:11] 但是比如說
[02:38:13] 失智症
[02:38:14] 比如說肺症
[02:38:15] 為什麼老人會失智
[02:38:17] 可能目前在醫學界
[02:38:18] 也沒有一個完整的理論來說
[02:38:21] 因為什麼什麼什麼
[02:38:23] 而什麼什麼什麼
[02:38:24] 你根本也沒有一個理論
[02:38:26] 完整的理論來描述它
[02:38:28] 所以你根本就寫不完
[02:38:30] 那個logic
[02:38:32] 那也有可能是
[02:38:34] practical ignorance
[02:38:36] 就算我們知道這些規則
[02:38:39] 我們
[02:38:40] ok
[02:38:43] 就算我們有一個完整的規則
[02:38:45] 我們很多時候呢
[02:38:47] 也無法排除所有的情況
[02:38:51] 因為你可能要做各式各樣不同的檢查
[02:38:55] 比如說假設我們現在已經完全知道
[02:38:58] 為什麼老人會失智
[02:38:59] 他是因為腦子裡面的什麼
[02:39:02] 某種蛋白的累積
[02:39:04] 再加上血糖
[02:39:06] 血壓
[02:39:08] 等等等等
[02:39:09] 再加上某一種
[02:39:12] 細胞裡面的什麼什麼病變
[02:39:14] 整個綜合起來就一定會有失智
[02:39:17] 你即使你知道
[02:39:20] 你也變成你要做好多不同的檢查
[02:39:23] 你才知道說
[02:39:24] 他的什麼什麼什麼
[02:39:25] Alpha蛋白
[02:39:26] 濃度有到多少累積多少
[02:39:28] 再加上你的血液裡面的什麼指數等
[02:39:31] 你可能也
[02:39:33] 就實際應用上也太貴
[02:39:36] 這就是為什麼
[02:39:38] 沒有辦法光靠Peper-Z去模仿
[02:39:41] 那怎麼辦呢
[02:39:42] 我們現在的工具就是我們引入機率
[02:39:45] 講半天就是為了引入機率
[02:39:47] 那機率呢
[02:39:49] 提供了一個辦法
[02:39:50] 讓我們去摘要所謂的不確定性
[02:39:55] 這個不確定性有可能源自於
[02:39:58] 我們懶惰懶得寫這些前後項
[02:40:02] 或者是說
[02:40:03] 你實際在真正應用上
[02:40:05] 你就是沒有辦法做出百分之百的檢測
[02:40:08] 你只能夠用機率來summarize這件事情
[02:40:11] 那
[02:40:16] 所以你可以這樣子啊
[02:40:17] 比如說根據過去的統計經驗
[02:40:19] 你可以說
[02:40:20] 過去啊
[02:40:21] 百分之八十的牙痛的病患
[02:40:24] 我過去
[02:40:25] 我是一個老醫生
[02:40:27] 根據我過去看診三十年的經驗
[02:40:30] 百分之八十有牙痛的病人
[02:40:33] 他
[02:40:35] 有助療
[02:40:37] 這句話沒有錯
[02:40:39] 對不對
[02:40:40] 沒有錯
[02:40:41] 但是呢
[02:40:42] 可能可以幫助我進行診斷
[02:40:45] OK
[02:40:46] 那你可以根據
[02:40:47] OK
[02:40:48] 你說你牙痛了是吧
[02:40:49] 那我心中就已經大概知道
[02:40:51] 你八成是有助療
[02:40:53] 那接下來我再做一些檢測
[02:40:55] 我再多看了一些證據之後
[02:40:57] 那我就可以
[02:40:59] 百分之九十五認定
[02:41:01] 你有沒有助療過
[02:41:03] 有助療過沒助療過
[02:41:04] 以此類推
[02:41:06] 好
[02:41:07] 那
[02:41:08] 所以說呢
[02:41:09] 他說機率啊
[02:41:10] 基本上有修過機率統計
[02:41:12] 應該大概會有很多修過機率統計吧
[02:41:14] 好我們接下來就是複習
[02:41:16] 機率基本上是根據你目前已知的資訊
[02:41:20] 它是跟你目前已知的資訊是搭配在一起的
[02:41:24] 好
[02:41:25] 比如說
[02:41:26] the probability that the patient has a cavity
[02:41:29] given that she has a toothache is 0.8
[02:41:33] 好
[02:41:34] 就是說
[02:41:35] 他有牙痛的情況下
[02:41:37] 他有助療的機率是百分之八十
[02:41:40] 好所以我觀測到的是他已經牙痛了
[02:41:44] 在他已經牙痛
[02:41:45] 我知道我看到這個事實的情況之下
[02:41:48] 他有助療的機率是百分之八十
[02:41:51] 這樣
[02:41:52] 那也許
[02:41:53] 接下來醫生就看一下他這個人的病歷呀
[02:41:56] 發現他過去有牙齦的一些疾病的歷史
[02:42:01] 好那這時候
[02:42:03] 我有了新的evidence
[02:42:04] 我有新的資訊了
[02:42:08] 給第一個這個病人有牙痛
[02:42:10] 而且他有牙齦
[02:42:11] 他有牙齦的疾病史
[02:42:15] 他有助療的機率是0.4
[02:42:19] 因為我有了一個新的knowledge進來
[02:42:23] 我多參考了一個新的knowledge
[02:42:26] 所以我去update
[02:42:28] 我整個機率的推算
[02:42:30] 好
[02:42:31] 那我收集越多的evidence
[02:42:34] 我就可以越精準的來描述他的狀況
[02:42:37] 他說
[02:42:38] 這個病人呢
[02:42:40] 我們
[02:42:41] 根據目前我們所得知的所有的證據
[02:42:46] 他有牙痛
[02:42:47] 他有牙齦的疾病史
[02:42:50] 我給他拍了S光
[02:42:52] 我看得到的嘴巴用燈去照
[02:42:58] 去看
[02:42:59] 根據這以上所有的證據
[02:43:02] 他有助療的機率等於0
[02:43:06] 這樣子
[02:43:07] 這是有可能的
[02:43:08] 我看到任何
[02:43:10] 我基於這些證據
[02:43:12] 我就判別說
[02:43:14] 他有助療的機率等於0.4
[02:43:17] 以上這三句話
[02:43:18] 每一句都是對的
[02:43:20] 好
[02:43:21] All these statements do not contradict each other
[02:43:26] 這些句子
[02:43:27] 這些statements
[02:43:29] 都沒有矛盾喔
[02:43:31] 所以他基於不同的knowledge base的情況之下
[02:43:35] 我去預估這個機率就會不一樣
[02:43:38] 每一句都是對的
[02:43:39] 對
[02:43:40] 所以這邊只是要跟大家強調說
[02:43:43] 你在預估一個機率的時候
[02:43:45] 其實是根據你現有已知的某一些資訊來去預估這個機率
[02:43:49] 這樣
[02:43:53] 好
[02:43:54] 那
[02:43:55] OK
[02:43:56] 所以引入機率之後呢
[02:43:57] 我們之前提到一些
[02:44:01] utility based agent
[02:44:03] 大家還記得嗎
[02:44:04] 我們在第二章
[02:44:05] 介紹我們的agent是什麼
[02:44:07] 從最簡單的基本反射的agent
[02:44:10] 然後再來goal based agent
[02:44:11] model based agent
[02:44:12] 再來是utility based agent
[02:44:14] 對不對
[02:44:15] 我們現在進入到utility based agent
[02:44:17] 當你面對你觀測到某一些訊息
[02:44:20] 你要決定哪一些動作效益最高的時候
[02:44:24] 你就可以引入機率
[02:44:28] 那所以就讓agent呢
[02:44:32] 他對你不同的動作有一些偏好
[02:44:36] utility theory says that
[02:44:38] every state has a degree of usefulness or utility
[02:44:41] 有某一些效益
[02:44:44] 那我們應該會偏向於
[02:44:47] 讓效益最大化的那樣子的動作
[02:44:51] 好
[02:44:54] 那所以說呢
[02:44:55] 考慮到機率
[02:44:57] 考慮到效益兩個整合起來呢
[02:44:59] 就是你可以做決策
[02:45:01] 你做決策
[02:45:03] 那
[02:45:04] 所以說呢
[02:45:05] 這個所謂的discipline theory
[02:45:07] 他其實就是說
[02:45:09] 一個agent呢
[02:45:10] 我們說他是理性的
[02:45:12] if and only if
[02:45:14] he choose the action that yields the highest expected utility
[02:45:18] 這句話我們在第二章也講過
[02:45:20] 什麼叫做是一個理性的agent呢
[02:45:23] 就是根據他現有的資訊
[02:45:26] 他去做出能夠極大化效益的那種agent
[02:45:32] 就叫做rational agent
[02:45:34] ok
[02:45:36] 那這個principle呢
[02:45:37] 也叫做maximal expected utility
[02:45:39] 就是極大化
[02:45:41] 預估的效益
[02:45:47] 機率呢
[02:45:48] 基本上就是在描述
[02:45:50] 某一個世界出現的狀況
[02:45:53] 去描述它的uncertainty
[02:45:55] 好
[02:45:56] 那所有可能出現的狀況呢
[02:45:59] 就稱呼叫做simple space
[02:46:02] 好
[02:46:03] 所以舉個例子來講
[02:46:04] 丟兩顆骰子
[02:46:06] 你可能可以出現36種狀況
[02:46:09] 好
[02:46:10] 比如說兩顆都丟出1啊
[02:46:12] 一顆丟出1
[02:46:13] 第一顆丟出1
[02:46:14] 第二顆丟出2啊
[02:46:16] 好
[02:46:17] 或者一直到第一顆丟出6
[02:46:18] 第二顆丟出6啊
[02:46:20] 所以總共
[02:46:21] 第一顆有6種狀況
[02:46:22] 第二顆有6種狀況
[02:46:24] 36種狀況
[02:46:26] 這36種狀況呢
[02:46:27] 我們稱呼它叫做simple space
[02:46:30] 我們習慣呢
[02:46:31] 用大寫
[02:46:33] 大寫的字母來表達它
[02:46:35] 比如說
[02:46:36] 這個希臘字母大寫omega
[02:46:38] 來代表這整個simple space
[02:46:40] 小寫的omega呢
[02:46:42] 來代表了
[02:46:43] 在這個simple space裡面的某一個狀態
[02:46:47] 某一個狀態
[02:46:49] 好
[02:46:50] 那我們都知道嘛
[02:46:51] 你任何的某一個狀態出現的機率
[02:46:54] 介於0到1之間
[02:46:55] 你所有的狀態
[02:46:56] 在這個simple space裡面所有的狀態
[02:46:59] 出現的機率加起來要等於1嘛
[02:47:01] 那所以說呢
[02:47:04] 你是這36種狀態裡面的
[02:47:06] 任何某一個狀態出現的機率
[02:47:08] 就是36分之1嘛
[02:47:10] 這是古典機率
[02:47:11] 那很多時候
[02:47:15] 我們
[02:47:16] 有興趣的
[02:47:18] 可能不是單一的某一個狀態
[02:47:20] 我們可能是對某一種組合
[02:47:23] 我們比較有興趣
[02:47:24] 比如說我們對於
[02:47:26] 兩顆骰子的點數加起來
[02:47:28] 等於11的這件事情
[02:47:30] 我們感覺到有興趣
[02:47:32] 我們稱呼這種
[02:47:33] 叫做一個event
[02:47:35] 一個event
[02:47:37] 那或者是說呢
[02:47:38] 在AI裡面呢也稱呼
[02:47:40] 這是一個proposition
[02:47:42] 你可以用文字來描述出一個proposition
[02:47:45] 就是說
[02:47:46] 是對於
[02:47:47] 兩個骰子的點數加起來等於11
[02:47:49] 這件事情有興趣
[02:47:50] 請幫我估算
[02:47:51] 兩個骰子丟出
[02:47:53] 總和是11的機率這樣子
[02:47:56] 那對於每一個proposition呢
[02:48:00] 它的機率怎麼估
[02:48:04] 比如說一個proposition
[02:48:06] 5
[02:48:07] 這個5出現的機率
[02:48:10] 就等於是
[02:48:11] 能夠造成
[02:48:13] 這個proposition的
[02:48:15] 所有的
[02:48:17] element
[02:48:19] 所有的可能的情況的機率加總
[02:48:22] 講得文燒燒的
[02:48:24] 什麼意思啊
[02:48:25] 就是說假設我今天有興趣的是
[02:48:27] 總和為11點的情況
[02:48:30] 那有可能是什麼
[02:48:31] 就只有兩種狀況嘛
[02:48:32] 第一顆丟出5點
[02:48:34] 第二顆丟出6點
[02:48:35] 或者是第一顆丟出6點
[02:48:36] 第二顆丟出5點
[02:48:38] 對不對
[02:48:39] 所以我想要去預估說
[02:48:40] 總和是11點的機率
[02:48:43] 我就是把剛剛那兩種狀況的機率
[02:48:45] 個別都是1 3 6分之1
[02:48:47] 兩個加起來
[02:48:48] 6分之2
[02:48:50] 就這意思
[02:48:52] 寫成數學就是這樣
[02:48:55] OK
[02:48:59] 所以這裡就講到這件事
[02:49:02] 講到這件事
[02:49:04] OK
[02:49:05] 所以說呢
[02:49:06] 我們有興趣的proposition
[02:49:08] 可能是
[02:49:09] 比如說總和41點的啦
[02:49:11] 或者說我們丟出來的
[02:49:13] 兩顆骰子
[02:49:14] 是同樣點數的啦
[02:49:16] 這些東西
[02:49:17] 那這些機率呢
[02:49:18] 到目前為止我們講的這些機率呢
[02:49:20] 都是unconditional
[02:49:22] unconditional
[02:49:25] 那也就是說沒有一些附帶的先決條件的
[02:49:30] 就是說某件事情出現的機率是怎麼樣
[02:49:32] 某件事情出現的機率是怎麼樣
[02:49:34] 好附帶一體
[02:49:37] 我現在看到一些數字
[02:49:38] 所以我要講第二個通關密因
[02:49:40] 這這麼突然
[02:49:42] 5665好了
[02:49:44] 請助教幫我記一下
[02:49:46] 因為等一下也快下課了
[02:49:48] 還活著的人應該不多了
[02:49:51] 第二個通關密因就是這一
[02:49:53] 剛剛講的這個
[02:49:55] 好
[02:49:57] 好
[02:49:58] 那
[02:49:59] 所以我們剛剛前面講的這些都是
[02:50:01] unconditional的probability
[02:50:03] 那很
[02:50:04] 你在學機率的時候你就知道嘛
[02:50:06] 其實很多時候是
[02:50:07] 我們觀察到一些evidence
[02:50:09] 我們當我們在看到某一個evidence的情況之下
[02:50:12] 某一件事情發生的機率
[02:50:14] 那這個機率就是所謂的conditional probability
[02:50:17] conditional probability
[02:50:20] 條件機率
[02:50:21] 所以比如說
[02:50:24] 在我看到第一顆骰子是五點的情況之下
[02:50:29] 那麼我兩顆骰子丟出來的點數是
[02:50:33] 一模一樣的機率是多少
[02:50:36] 是多少
[02:50:40] 第一顆已經是五點了
[02:50:42] 那其實你要讓它丟出來點數一模一樣
[02:50:45] 代表你第二個骰子也必須丟出五點
[02:50:48] 這件事情就會發生嘛
[02:50:50] 所以說呢這個機率就是等於多少
[02:50:52] 六分之一對不對
[02:50:54] 所以呢在數學上呢我們通常
[02:50:56] 用這個直線的這一槓
[02:50:58] 代表的是given
[02:51:00] given
[02:51:01] 第一個骰子等於五點的情況之下
[02:51:04] 你會丟出一雙的機率是多少
[02:51:08] ok
[02:51:10] 好
[02:51:11] 那所以一樣回到這個牙醫的例子
[02:51:15] 今天
[02:51:17] 在某一個小鎮裡面
[02:51:19] 蛀牙的機率其實根據過去醫師的統計結果呢
[02:51:24] 可能是25%
[02:51:26] 這樣子
[02:51:27] 好
[02:51:28] 那但是呢今天有一個人走進了我的診所
[02:51:33] 他說他牙痛
[02:51:35] 那他有蛀牙的機率呢
[02:51:38] 可能就上升到60%
[02:51:40] 這樣子
[02:51:41] 好
[02:51:42] 那請注意喔
[02:51:44] 這兩個句話
[02:51:45] 這兩個機率都是對的
[02:51:47] 沒有互相衝突
[02:51:49] 沒有互相衝突
[02:51:55] probability
[02:51:56] 只是這樣
[02:52:00] probability a given b
[02:52:01] 是什麼意思呢
[02:52:02] 在知道b的
[02:52:04] 情況之下
[02:52:05] a的機率是多少
[02:52:07] 那這機率怎麼算呢
[02:52:09] 好在conditional probability裡面呢
[02:52:11] 大家以前學機率應該學過這個
[02:52:14] 它等於是probability b分之probability a and b
[02:52:19] 的意思嘛
[02:52:21] 如果要講成白話
[02:52:22] 來我用白話把這個數學式子講一次
[02:52:26] 在知道b的情況之下
[02:52:28] a發生的機率怎麼算
[02:52:31] 那就等於是
[02:52:33] b發生的機率
[02:52:35] 分之a b都發生的機率
[02:52:39] 這就是把這個數學式子
[02:52:41] 翻譯成白話的意思嘛
[02:52:43] 對不對
[02:52:44] 在知道第一顆骰子是五點的情況之下
[02:52:47] 我會丟出一頓的機率是多少
[02:52:52] 就等於是丟出五點的機率
[02:52:55] 分之丟出五點
[02:52:58] 而且產生出一頓的機率
[02:53:02] 這個就是conditional probability
[02:53:05] 我這邊可以講得比較快
[02:53:08] 因為大家應該都學過
[02:53:10] 那把剛剛上面的式子上面轉一下
[02:53:13] 你就變成是這個啊
[02:53:14] a b都發生的機率
[02:53:17] 就等於是什麼
[02:53:18] b發生的機率在乘上
[02:53:20] b發生的情況之下
[02:53:22] a發生的機率
[02:53:23] 那就叫做a b都發生的機率
[02:53:27] 這叫product rule
[02:53:32] ok
[02:53:33] 好
[02:53:34] 那所以呢
[02:53:36] 很快的走完這幾頁的影片
[02:53:38] 這完全都是複習
[02:53:40] 其實接下來也是複習啦
[02:53:42] 好接下來也是複習
[02:53:43] 不過呢
[02:53:44] 剛好這裡是一個小小段落
[02:53:46] 而且呢我們時間好像也快差不多了
[02:53:49] 我們看一下slide頭上面
[02:53:53] 沒有問題啦
[02:53:55] 那我們最後就要走一下抽獎的環節
[02:54:03] 我們用checkgpt
[02:54:16] 我們才15
[02:54:17] 你才發出15張汗毛牌啊
[02:54:20] 確定喔
[02:54:21] 1到15
[02:54:22] 人不在場的就抽到也不算喔
[02:54:25] 從1到15
[02:54:27] 隨機抽出6位
[02:54:33] 6個數字
[02:54:35] 不能重複
[02:54:38] 確定喔
[02:54:41] 1到15
[02:54:42] 所以啊
[02:54:43] 線上的同學
[02:54:44] 我們成大才15個同學
[02:54:46] 坐在實體的這個課堂上
[02:54:48] 你看多可憐
[02:54:49] 我們號稱有130個人修啊
[02:54:52] 好來
[02:54:53] 等一下抽到的同學呢
[02:54:55] 欸你有沒有
[02:54:56] 你有沒有準備紙筆
[02:54:58] 要請同學來
[02:54:59] 獲獎的同學要來前面填
[02:55:02] 學號Email
[02:55:05] 學號姓名Email
[02:55:06] 等一下獲獎的同學要來
[02:55:08] 超大獎是事後
[02:55:12] 我們只是先抽出誰得獎
[02:55:14] 因為我們要連同線上的同學
[02:55:17] 總共有11位會得獎
[02:55:19] 這11位裡面會再抽出
[02:55:20] 隨機抽出1位
[02:55:22] 那一位隨機抽出1位就是由
[02:55:24] 今天的值班助教來抽的
[02:55:27] 好
[02:55:28] 開始
[02:55:30] 誰
[02:55:32] 他這有需要思考嗎
[02:55:35] 我不好意思
[02:55:36] 我弄太思考模式是不是
[02:55:38] 來
[02:55:39] 1 3 6 8 10 4 15
[02:55:41] 舉手
[02:55:42] 1 3 6 8
[02:55:44] 1 2 3 4 5 6
[02:55:46] 6個好
[02:55:47] 這6位同學
[02:55:48] 等一下來前面找助教
[02:55:49] 填你的學號姓名
[02:55:52] 好
[02:55:53] 還有Gmail的帳號
[02:55:56] OK
[02:55:57] 好
[02:55:58] 那我們今天上到這邊
[02:56:01] 下禮拜記得叫作業
[02:56:03] 作業一
[02:56:04] 然後我們會公佈作業二
[02:56:06] 然後下禮拜的上課
[02:56:08] 就是看影片
[02:56:10] OK
[02:56:11] 因為我出國開會
[02:56:13] 好
[02:56:14] 線上的同學
[02:56:16] 線上同學呢
[02:56:17] 我們最後再讓大家喵一下
[02:56:20] 線上表單的QR code
[02:56:25] 但是這個線上表單呢
[02:56:27] 我們只會開放到4點
[02:56:31] 先讓大家喵一下
[02:56:36] 好
[02:56:37] 好
[02:56:38] 那我們今天就上到這邊