[音樂] [音樂] [音樂] [音樂] [音樂] 各位同學大家好, 歡迎來到人工智慧課程,我是台大電機系余天利。 好我們呢回到 agent 來看一下,那 基本上,從 agent 的角度來說,我們最簡單的 agent 就是所謂 simple reflex agent,就是反射性的,那基本上 像這個圖所看到的,你有一個 condition-action rules, 然後你從 environment 透過 sensor 拿進來,偵測到一些事情,你會知道,這個世界長什麼樣子, 然後,given if 偵測到 condition,這一路我們就決定 我接下來要做什麼行為,我做什麼行為,然後這個 action to actuator, 回饋給環境,這是最簡單的一個 agent,也就是說,你可以說是 rule based,或者是我們稱為所謂 memory-less 因為它最起碼就是一個 function,起碼就是你哪些時間點給我同樣的 input,我都給你同樣的 output, 這樣的東西基本上,這樣的 agent 很簡單,那它會 它也很 robust,它也很 robust,那它基本上 會 work,如果你的環境是 fully observable,你如果什麼東西都看得到的話,它會 work 的非常的好,但是 有些時候,如果是 partially observable 的話,這樣的 agent 會 會有點狀況,譬如說這個 agent 可能說,我現在要往前 進然後到下一個 state,但是它可能沒有看到,譬如它的 sensor 出了些問題或怎麼樣沒看到,它沒看到真有個門擋住你, 或者路上有路上擋住,所以你前進,你雖然說要前進,但你其實在原地。 那如果是這樣的 agent,因為它是 memory-less 嘛, 所以基本上它不會記得發生了什麼事情,它就下一個時間點因為它的 它偵測的事情是一樣,因為它在原地,對不對?所以它的 決策還是仍然是往前,那這個是會不斷地重複,會變成無窮迴圈,就是它其實是被擋住了, 沒辦法往前,它會認為,因為它 sensor 都一樣,sensor 過來的資料都一樣,所以它認為最好的路徑就是往前,往前,往前, 那就一直被 trap 在那裡,好這是 simple reflex agent 帶來的問題。 那如果針對剛剛我們像 partial observable 的環境,那另外 一種做法就是你可以做 model-base reflex agent,那基本上就是對這個環境裡面 你 sense 完以後你有個狀態,你有個 inner state, 你有個 inner state,有這個狀態,這個狀態然後去說,你現在 世界是怎麼樣子,然後再根據你的這個 rule 來判斷。 如果以剛剛的例子來講,就是說你可能 上個時間點說前進,結果沒前進嘛, 沒有前進,那你上次你記得這個 state,說欸我是 我剛剛是要前進,結果我沒前進,那你可能,有了這個 state 之後你就可以做很多事, 譬如說你可能會覺得,如果連續試了二十次要前進,結果都沒前進, 那你可以 model 說,我是不是被什麼東西卡住了, 你有這個能力去 model 這件事,所以我們稱為 model-based reflex agent。 好,那這個 state 基本上呢也只能算是 這個 agent 最好的猜測,given information 對這個世界你做最好的 一個猜測,那這個猜測不一定百分之百正確,那如果不爭取的話當然也有可能導致不正確的 action,當然就 depend on 你 model 的性能,複雜度,越複雜 model 也許越正確,但是日後我們也會提到,過度複雜的 模型有時候會造成 overfitting,稱為過度擬合。 Overfitting 的狀態那也不見得會帶來正確的事情。 但是這個 agent 基本上就能做比較,比剛剛 simple reflex 能做比較多一點的事情。 好那有時候光有,你有這個世界的 model,就是說這個世界你統統都知道, 但你可能還是沒辦法做事,譬如說我們講開車來說好了,你開一開,開到一個十字路口, 好,接下來請問你應該往前走,還是往左轉還是往右轉,如果問你這個問題,你一定會覺得很- 好笑,對不對? 你又沒跟我講目的地在哪裡,我怎麼知道要往哪裡開,這就是為什麼我們有些時候這個 agent 我們需要一個 goal,我們需要一個目標, 我們需要一個目標,而不是一個,一個,一個 condition-action 的一個組合,就是你有目標,我知道目的地 在哪裡,那我當然知道應該要往前,還是往右還是往左,那這個東西如果有目標,然後你要從 initial state 走到 找一個 sequence of action 使得你能夠到我的 final state 或者有時候 稱為 goal state 的話,那這樣的技術基本上是 search 還有 planning 在做的事情,那 search 基本上是 bottom up, 那 planning 我們稱為 top down,那這在日後的章節都有 cover。 那有時候光有 goal 其實還不夠,要包含,譬如說 有時候你有很多不同種的路徑到這個 goal,比如還是以開車為例,我要到同一個 目的地,但我可能,我可能有很多條路,我可以這樣走,我可以這樣走,我可以有很多種不同- 的路可以 走法可以開得到目的地,那這種情況下,哪一條路最好? 你光有目標是不夠的,所以你還必須要定義一個 utility,utility function 呢是我們就稱為是 happiness of the agent,就是這個 agent 的快樂度,那我們基本上 人也是嘛,人也是一樣,大家活在世上都盡量最大化自己的快樂度, 那怎麼樣才能快樂呢?你當然在設計 agent 的時候你必須要能夠量化它, 那像我剛剛的例子,你有不同的目標,你有不同的路徑可以到同一個目標的話,你可能有很多 量化指標,譬如說也許你希望最短的時間能夠到這個目標,也許你希望是 最舒適,最安全的一條路,那這件事仍然,一樣可以 同樣可以 apply 到多個目標,就是說 either 是單一目標,但你有多條路徑, either 是你有多個目標,就是你可以到這裡,或到這裡,或者到哪裡。 這蠻多時候也會 work,譬如說如果有時候 譬如說你到哪裡去吃飯,然後日後同事載你說,我有開車,你要不要 搭個順風車,然後問你要到哪裡,你可能會說,麻煩載我到最近的一個 捷運站,或者這種地鐵站就好了,那這裡面就是 either way 都可以,你有很多捷運站,哪一個都可以,但是你定一個 utility,就是最近的, 最近的捷運站,就是說你有很多目標,但是你定了 utility 要最近的,那最近有很多 意義,有可能時間最近,有可能距離最近,depend on 你車道的流向,有時候距離最近也不一定時間最短。 那一樣我們講,一個 rational agent 在這種情況下你要 maximize 的就是你 expected utility,就是在一個隨機環境,你要 最大化你得到的 utility 的期望值。 好,那 我們剛提到這些包含 search 到 planning,這都是在 AI 第一波浪潮裡面的最主要的技術,那它的最明顯的 achievement,可能大家印象最深刻的成就是 1997 年 IBM 的深藍這個程式,應該說是電腦,包含程式,然後打敗了世界棋王,我對這件事情印象蠻深刻- ,1997 年是我 大學四年級,所以那時候新聞,就跟它可能,各位現在看到的 alphago 這種東西感覺一樣,然後當時覺得是一個不可能的事情,結果 沒想到就打敗了,因為其實他們比過兩次,1996 年就他們就比過一次,然後 當時世界棋王是 Kasparov 算是贏了,Kasparov 其實蠻強的,他是被譽為 大概當時,被譽為是近年來最傳奇的一個世界棋王,就是世界第二 離他有一段蠻大的差距。 然後那當時 1996 年 Kasparov 贏的時候還 就誇下海口說,近年來,就是電腦程式跟他還差的很遠, 近年來是贏不了他的,結果沒想到再隔一年就被打敗了,不過打敗這件事其實也有很多 有很多小趣聞,大家可以 google 去看看,其實 Kasparov 當年 1997 年被打敗之後,他有點不服氣,他要求再戰,因為他的 argument 是說,他的 棋風都被電腦研究很透徹,但是他都沒研究過電腦的棋風,這當然是事實,任何世界棋王都是 這種宿命嘛,人家會研究你的棋,但是你可能沒辦法去研究對手的棋,那他 輸了那一局以後,他覺得他後面幾盤比價抓到電腦的想法,他認為他再下應該會贏, 所以他要求再戰,結果 IBM 拒絕了,然後而且當時把那個 deep blue 就把它拆掉了,deep blue 在當年是一個超級電腦, 它當年一秒鐘可以搜尋 10 的 8 次方,就是一億個 盤面狀況,和一個蠻強的硬體設備,那當然就把它拆掉就沒辦法再戰了,反正就 IBM 拒絕, 當時 IBM 的態度跟現在 google alphago 的態度不太一樣,anyway, 當時,無論能不能,當時再戰 Kasparov 會不會贏,我們當然 不得而知,但是近年來已經沒有可能,就是人類在西洋棋 要贏過電腦基本上已經不可能了,那你如果看一些文章可能會講說,它的 方法,deep blue 所用的方法是一個聰明的暴力搜尋,這邊我一定要強調聰明,因為有些文章如果只講暴力 搜尋是不太合理的,因為西洋棋的複雜度大概是 10 的 47 次方個牌面狀況,即使以現在的電腦仍然無法 在合理的時間內把 10 的 47 次方個牌面全部看完,這個還是做不到的,所以我們其實還是 還是只看了部分,我們不是真的完全暴力搜索,那這個部分在後面章節都會提到它的一些技術- ,包含用一些 mini-max search 以及一些聰明的 pooling,那這樣的技術除了剛剛講到的成就以外,當然它 在第一波這樣後來遇到一些瓶頸,那這個瓶頸 主要是什麼呢?就是這些 search 這些技術似乎還是比較能 work 在所謂的 toy problem,那這個 toy problem 我要 你想 double 括起來,什麼叫做 toy problem?就是大家不要以為我們講 toy problem 就是大家 都說這問題很簡單,並不是,像下西洋棋一點都不簡單,那甚至像下圍棋最近幾年才贏嘛- ,對不對 從西洋棋 97 年一直到額 [聽不清] 對不對,可能 2016、 2017,那基本上已經過了 好 20 年,對不對,20 年後我們在圍棋才真的、 真的打贏人類。 那 可是,即使這樣,圍棋我們大部分研究人員還是認為它是一個所謂的 toy problem 哦,那 我們那簡單講一下所何謂 toy problem 呢?主要就是說如果這個問 題,如果我們在解決是一個現實的問題,那你要電腦能解,你必須要做個程度抽象化 好,也就是說你要把數學、 數學模型把它抽出來。 在做這個抽象化的過程 如果沒有什麼失真,就看它失真程度,如果它失真程度非常小 那基本上我們就會認為它是比較屬於 toy problem,以西洋棋或是圍棋這個例子來講 當我把這個現實的世界、 現實的這個問題轉換成數學模型之後,基本上它是完全沒有失真的。 就是這個我可以直接說欸這個這個這個主教在哪一格,譬如 3 x 3,3 [聽不清] 3 這一格,那這件事完全描述現在棋盤的狀況。 對不對,所以這個在當這個問題在抽象化過程沒有失真,我們就認為 OK 它就是一個相對 我們稱為 toy problem,但 toy problem 可以很難,就像我剛剛講圍棋,我們認為它 OK 它是個 toy problem,但是它 非常非常非常困難。 那什麼是、 不是 toy problem 呢?譬如說,現實問題我們真正要解決的都是 不容易去抽象化,因為抽象化過程會非常多失真,譬如說 我們買哪一隻股票會賺最最多錢啊,我公司該怎麼開發產品 才會得到最大利益啊,那我問這個問題對不對,你要怎麼去抽象化它,或是醫生我要看到一個- 病人,我要怎麼樣 治療他,對不對,你要你要你怎麼把它用數學式把它描述,或是我要怎麼我們 身為老師我要講一個,要怎麼樣講英文課講得精彩,然後學生不會睡著,好這個問題你都很難用 把它,當你當然可以把它轉成一個數學模型,但是你這個轉化過程你可能丟掉很多 detail,好這個就我們所謂的在轉換過程有失真,那這個失真度、 隨著你失真度的 程度,如果當你轉換的過程失真太嚴重,會造成什麼問題呢?就是你轉換過去以後這個問題即- 使你把它 solution 解出來了,在這抽象化的問題把它解完了,你這個 solution 可能因為失真度太高,無法真的 apply 到現實的世界 好這是真正困難的地方哦。 好,那這是第一波所 search,所、 技術所帶來的面臨到的瓶頸。 好,那第一波技術裡面還有所、 還有另外一個神經網絡也是差不多就額最 早出就是它的 perceptron 是 1943 年所發展的哦,那這裡面我也稍微提一下,那 最早主要想法就是說,對人腦有一些大致的了解 人腦其實很複雜啦,我自己其實沒有學太多生物,不敢講太多,但是額 目前我們認為人、 人類的,尤其是靈長類,那額從哺乳類開始,我們有個東西叫新皮脂哦 就 neuron context 這個東西哦,那上面裡面我們對它了解比較多,那裡面有很多很多的神經,那 額大概這樣有 10 的 11 次方的神經元,大概有 20 種不同的、 20 多種不同的種類哦,那不細分。 好,那大概有 10 的 14 次方個連接哦,那也就平均來說你可以除一下,就是 10 的 14 除 10 的 11 嘛,大概 10 的 3 次方,也就是說平均每個神經元大概跟其他 1000 個神經元大概連 接。 那神經元數量很龐大,那它的傳遞是 相對於電腦、 比較於電腦是比較慢的,就是大概傳遞大概是 幾個 mini second,好,幾個 mini second,也就是說如果我給你一秒鐘的話,大概只能傳額幾百、 幾百層 最多是幾百、 幾百階,十幾到幾百階這樣的東西。 好,那在當時有個想法就是說,當時為什麼人類 就 1950 年附近,那時候會覺得人類為什麼那麼聰明,然後電腦為什麼那麼多事都做不到,主要原因是- 當時想法是 每一個 neuron 就像一個計算單元哦,OK,那我們人腦有就像你看到的這邊有 10 的 11 次方個運算單元,在當時的任 何電腦都沒有這麼大量的運算單元哦,所以被認為說當時認為人類的思考是一個大量的平- 行運算。 好,就是所以一個時間點我同時我就可以算 10 的 11 次方這麼多不同的東西,所以電腦當然比 不上,這是當時的這樣的想法,那在近年來也有很多的改變,我們晚一點會提到。 好,背上這樣的想法,我還是要強調剛這個想法近年來有很多改變,我並不能被認為是正確,但 當時是這樣想的,所以在 1943 年就提出了這個這個神經網絡的一個神經元的單元哦,基本上就是一個神經元就是 大家所看到這邊是一個神經元,OK。 那額然後你有很多 input 進來,有很多 input 進來,那這 input 都會乘上不同的 weight,然後 summation 起來以後 加總就是,你就可以想象一個 weight 的向量和一個 input 向量的內積啦,就 in the product 以後然後經過一個 activation function。 好,activation function 有很多種啦,之後就非線性,因為剛剛是線性系統嘛,那你做個非線性的 事情,然後決定說這個神經元是處在激發狀態還是非激發狀態,那如果激發狀態通常我們 叫做就稱為 1 嘛,比較接近 1,那非激發狀態肯定就是 0,然後這個狀態會再、 再傳遞下去,就我們剛剛說 可能平均連 1000 個其他的神經元,這樣。 好,這是 這我現在介紹這一個是一個單一個 perceptron 的概念哦。 那 額那這 1943 年提出來,那單一個 perceptron 能做什麼事呢?能做的事當然不多,因為它是一個 線性組合,所以它做的事情就是線性分割。 那額舉例而言,這邊大家看到的是一個貓跟狗的一個一個分割哦,那 額橫軸這邊是額馴化程度,縱軸這邊是 size 尺寸,那一般大家比較相信狗 跟貓比起來比較馴化一點啦,但怎麼馴化當然要一個量化指標哦,那額然後尺寸也稍微大一點- ,所以一般 來說越馴化的、 尺寸越大的是狗,那負的是貓。 那應該大家可以看到這個圖裡面 show 的就是一個線性分割,如果給你看到 一隻狗一隻貓,那你可能覺得欸這樣、 這樣分就可以。 那所以我例子看越來 越多,好這邊有四隻狗,看到兩隻貓那你可能找一條線性分割是這個樣子。 好,那這是一個 perceptron 能做的事情,但是在這邊我要提一個,線性分割當然很簡單,但 是額它能做一個,它能做到一個很重要的事情就是一般化,generalization,- 就是它不光是對 看過的事情知道怎麼做,而是沒看過的東西它也知道,就說你如果日後給它一個新的 一個你不知道是貓還是狗,但它落在譬如說落在這一個點,好就是馴化程度落在這個點,那 這個 perceptron 就預測說它應該是狗,那你如果落在這裡的話,它就認為欸這個應該是大概是貓。 好,它所以,所以它不是一個 table look up,它已經能夠做簡單的一般化。 那當然一個線性分割還是蠻弱的,所以基本上我們會做 額當時就做的就是一個叫 multi-layer 的 perceptron,我們又簡單稱為 MLP。 那這個技術其實到現在還在用,現在什麼深度學習到前面有很多 convolutional neural network 到 最後還是、 最後層還是基本上是個 MLP。 好,MLP 在當時就是 額我們可以證明啦,當然覺得應該還好,就是基本上你只要夠多的額 夠多的 neuron,它就可以 map 任何的 function 哦。 那它概念上是這樣,你有一層 input layer 好,你有一層的 input layer,那你有個一層 output layer,那這 input layer 和 output layer 個數當然就是你的 problem defined,就是你 problem 需要幾個 input,需要幾個 output,它就已經、 數量就已經決定了,但是你有所謂的 hidden layer。 好,當時最流行的就是這邊我個別所看到的三層架構,就是當時最流行的,但是也 沒有限定在三層啦,不過當時電腦沒有很強嘛,所以大概額比較、 就算比較多層,大概最多看到 五層哦,也就是說裡面,就 hidden layer either 是一層,或是大概最多大概到三層左右。 好,那 我們剛剛講說它可以 map 任何的 function 意思就是說你只要給它足夠多的 hidden layer 的 neuron,這個 hidden layer 的 neuron 的個數就可以增加,就是你如果覺得這樣能 力不足,你可以再增加一個 neuron,然後其他人都連到這邊,好,連過到 output 這樣。 所以你這個增加 hidden layer 的 neuron 的個數,你這個 network 的 map 的 function 就越來越 複雜,那原則上它可以 map 任何的 function,只要夠多。 那你 怎麼學習呢?就是透過一個我們日後、 之後再提到,neural network 會提到的 back propagation 的 技術哦,就是說你這個 neural network 它的輸出跟你的預期差距多遠,然後把這個 error 把它 back propagation 回去,用來調整每一個連接的強度。 好,那這邊能做的當然可以看一下這邊額,就是如果我 input 是兩個,那你看到如果我的、 我需要分割的是這樣的概念哦,就是一個 紅色的一個 class 和一個藍色的 class,那這兩個 class 它不是一個線性能分割的狀態,但是我可以透過 因為透過 hidden layer,hidden layer 就是因為它有些 non-linear 的 mapping,所以它等於說把整個空間做一個非線性的轉換,所以轉換成像 這個圖所看到這個樣子。 好,那你把空間做了轉換以後你可以發現這張圖裡面其實存在一個很簡單的線性分割。 把紅色跟藍色把它分開,所以之後就可以再做一個線性,這邊 output 就做一個線性分割,你就可以把它分開、 分開掉。 那 它的怎麼調整這些 weight 呢使得這個空間能做這樣的轉換,就是我剛講利用一些 back propagation 的技術把這些 weight 給它調整好。 好,那這是 multi-layer perceptron 的事情。 好,那這個東西出來以後 當然大家就覺得很興奮,因為我們剛剛講的就是說 只要你給足夠多的 hidden 的 perceptron 它基本上可以 map 任何的 function。 那你也可以想象人腦其實基本上也是一種 廣義來說,你也是一種 function 嘛,對不對,就是我假設我看到某些事情我會做 怎麼樣的回應,那你可以把我腦袋、 腦想象成是一個 function。 那如果既然它可以 map 任意的 function,那它同時也可以 map 我 人,人這個 function,也就是說,有一個 neural network 它基本上可以完整地模擬於天立 我這個人的角色。 那就是說我看到同樣的,它跟我一樣看到同樣的 input,它會做出跟我同樣的 output。 那如果是這樣的話,那基本上 人工智慧就實現了嘛,它會完全取代人。 好,可是,聽起來很完美,但是 1969 年那 Minsky 基本上也是 AI 的重要推手之一哦,那他提出了一個重量級的論文哦,那他提出了 在這個論文裡面他提出了兩件事情,第一個事情是 XOR problem,XOR problem 又稱為 異同問題,就像這邊大家看到的 X 和 Y 軸的話它有象限嘛,就是有 (0,1),(1,0) (0,1),(1,0), (0,1), (1,0), (0,0), (1,1),好,這四個可能有組合。 那如果他們一樣,譬如說 (1,1),我就說哦那你 output 是 0,好 (0,0) 你一樣你 output 是 0,那你不一樣的時候會有 (0,1) 或 (1,0),那你的 output 就是 1。 好,那這個就對應到,這個其實對應到邏輯的 XOR 啦。 那 所以我們又稱為 XOR problem,但實際上它就是異同問題,就是說這兩個一樣或不一樣。 那這個東西 你可以看到就像這個圖上,因為對角線是 1 嘛,然後另外兩個對角是 0,所以它沒有 辦法做單一線性分割,也就簡單講一個 perceptron 是無法分割 這樣 XOR 的概念嘛,對不對?那這有什麼問題呢?也就是我們剛剛 講 neural network 它可以 map 任意的 function,也就是說你一個不行,我用多幾個就可以嘛。 好,這是沒錯,多幾個就可以,可是 and 和 or 這個概念,譬如說 and 的概念它是這樣,它是 這一個角是 1,其他三個角是 0。 好這是 and,and 的概念基本上你可以做線性分割。 對不對?一條線就分開了。 那同樣 or 也是,or 的話,or 的概念是這三個角是 1 這個角是 0,那這個可以線性分割,這樣就割掉了。 也就是說在 神經元 perceptron 的想法來說 and or 是一個比較簡單學習的事情,而異同是一個比較難的學習。 就單一 個 perceptron 不行,我需要一個 network 比較多,比較多幾個 perceptron 才能學會的事情。 那這,OK 這有什麼問題呢? 因為在認知科學裡面有很多 evidence show 說我們人類在嬰孩的時候就一兩個月,就已經能辨 認異同,好這辨認異同怎麼知道的,做什麼做實驗,當然不是去問嬰兒說你覺得它一不一樣啦- ,當然他不會看。 但是他可以 經過 trace 你嬰幼兒的眼球的移動,就是你如果給 他兩個一樣的和給他兩個不一樣的東西,他眼球的 movement 是完全不同的。 所以我們可以認知說 人類在非常非常小的年紀的時候就已經開始有異同的這個概念。 可是,你如果回想一下 你的求學過程,你到什麼年紀你才開始有 and or 這個概念,這要成長很久。 也就是說基本上他 perceptron 跟人類的思考其實有很大的不一樣,人類在人類、 人腦來說 異同是簡單的,and or 的概念是困難的,但是在 perceptron 來說反過來 XOR 是困難的,異同,額,就異同是困難的,and or 是簡單的,所以似乎 這邊是說明了一件事,就是似乎 人類的思考並不是跟神經網絡是一樣的,似乎是這麼回事。 他先 提出了這第一個,那第二個他這是,右邊這個圖是他當年 paper 的封面哦。 他提出就是說其實上面這個連接問題,上面這一個圖 這條白線其實是一條白線,大家可以玩一下哦,就是手在上面畫一下 好,它其實是一條白線。 下面這一個圖是兩條白線,它是兩條像那種蚊香,有沒有這樣 扣起來。 好,作者聲稱啊,其實我自己也要看一陣子,作者聲稱就是說 這個人類是相對容易分辨的,可是這個例子呢要讓要讓神經網絡去分辨這件事是 非常非常困難。 好,它就像我們剛剛講的就是你其 其實只要給你夠多的 hidden perceptron 你還是可以分辨嘛,但是這個這個 數量基本上需要 exponentially 的多,好那所以這也是它的 limitation。 好,所以自從這篇 paper 出來以後,那曾經有很多人認為欸神經網絡只要給你夠多神經元就可以模擬任何 function,包含模擬人腦。 那這樣的想法就開始失望了,也就是說現實,這篇 paper 等於跟你講現實世界上,現實現實就是神經網絡它有 它的 limitation,它有它的極限,不一定能做到你以為能做到的事情。 所以在這之後,70 年代之後,神經網絡的相關研究幾乎都全部消失。 額,其實這個消失也不是研究者本身啦,因為研究者作為研究者,我們當然 本來就認為說什麼事都有一些 limitation,這是合理的。 但是投資者,就是當時想象說 額就是給錢的啦,想說欸你不是跟我說這個可以什麼都能做到 包含人腦都可以做得到,但是怎麼現在都跟我講做不到,他們就不願意繼續 給那麼多經費,所以這樣的研究又開始 decline 下啦。