17th Sept (Monday) Machine learning 101

Machine learning 對我來說一直有一種人工智能般的吸引力
但一直找不到一個實用又好玩的, 帶有例子的教學
因為下手寫些代碼才有實感呀

早一兩天我遇到一個 blog,
講的是基本的machine learning, 使用 javascript 實作, 介給大家
http://burakkanber.com/blog/machine-learning-genetic-algorithms-part-1-j...

而且花點時間翻譯一下 (太長的話會分成數段)

課程會從介紹基因算法開始。基因算法或者是我會談到的算法中最不實用的一個,但使用它作為開頭是因為它能很好的介紹「費用 (cost)」或者「誤差 (error)」的概念,還有局部甜點全局甜點﹣這些概念都是非常重要,也會出現在其他 Machine learning (ML) 的算法之中。

大自然的進化是基因算法的啟蒙者。還有其他例如人工自然網絡 (artificial neural networks)也取自生物學:進化本身便是最好的學習算法,大腦是人類所知最好的泛用解題工具。這兩個是重要的生物學上的存在,也是兩個成長最快的人工智能分枝。但當我談到基因算法的「學習算法」和自然網絡的「解題」的時候,我們會先放下自然網絡,專注在基因算法之中。

「泛用」是上面一個重要的字眼。相比其他特定的算法,你很容易便可以找到一個比泛用算法快。但這不是這練習的目的,也不是基因算法的目的。你使用基因算法不是因為你有一個複雜的問題,而是你有一個複雜的問題的問題。(complex problem of problems) 或者你有一組複雜的,無關的參數.

用兩足行走的機械化人作例子,這是一個非常困難的問題。手寫一個行走的步驟是注定失敗的,就算你能令它行走,下一組的機械人可能有不同的重量中心點,那麼先前的算法又會變得無效。而使用基因算法你可以「教育機械人去自行學習自走」而非「教育機械人去自走」

先介紹一下今天的題目:
建立一個可以重現 "Hello, world!" 的基因算法

很多的編程教學都使用 hello world 作開頭,而使用基因算法重現 hello world 看似很笨,而你直接在代碼之中寫一句 hello world 一定會更快。如果我們知道我們需要的結果,為何還要編程一個算法?很簡單,因為這是一個學習用的題目。下一個使用 PHP 的練習會令你開始明白,但我們始終需要一個開始的點

基因算法
基因算法的基本是產生一組「可能的答案」然後算一下這些可能和最終答案是否足夠近似。相距太遠的會被永遠放棄。接近的會和其他溶合,或者變化一點點。這個做法是一直變化,看看我們是越來越近最終答案,還是相反的,越來越遠。

這些「可能的答案」是基因 (gene)。它們會交配,產生下一代,進化。它們會因為和目標太遠而死亡,或者優質的會交配產生下一代。你可能還想像不到這些如何可以相關到 hello world,但以下例子只是其中一個基因算法可以解決的問題之一。

基因
一個基因是代表一個可能的答案。在這個例子中,基因是一串字符。我們可以假設字符長度為13 (“Hello, World!”),幾個可能的基因

Gekmo+ xosmd!
Gekln, worle”
Fello, wosld!
Gello, wprld!
Hello, world!

明顯最後一個是「正確」的,也是全局的甜點,最佳點。但我們可以如何計算其他基因的「費用 (cost)」?

費用函數 (cost function)
費用函數是種量度兩個基因的相似度的函數,而在這個例子,我們可以比較兩個學串中的每一個字符的話ASCII,再平方令數字一定為正數。例如字符 “A” (ASCII 65) 但目標的字符是 “C” (ASCII 67), 費用便是 4 (67 – 65 = 2, 2^2 = 4)。我們使用平方的原因是我們只想看對絕對相差,那一個大或小並不重要。所以你也可以使用絕對值函數 abs() 你可以自己試驗一下它們之間的差別

使用以上的費用函數,可以算出以下五組基因的費用:

Gekmo+ xosmd! (7)
Gekln, worle” (5)
Fello, wosld! (5)
Gello, wprld! (2)
Hello, world! (0)

在這個例子,因為問題是簡單,我們的目標是 0費用,然後便完成了。但有些情況便不同,我們只需要找到我們能找到的最低費用,然後符合某些條件之下完結,停止再尋找。或者你要找出的是最高的費用,相同的你需要一些條件去總結為「完成」。

費用函數是基因算法的重要組成部份,因為如果你聰明的話,你可以混合完全不相關的參數。這一次的例子之中只有字符,但如果你要建立一個導航應用,你需要將重量,距離,速度,交通燈等的參數,它們完全不相關但你可以將它們化為一個整潔的費用函數,而使用不同的參數比重。

交配和死亡
交配是生命的必然,基因算法之中也經常使用。交配本質是兩組基因結合,交換,產生和父母不一樣的下一代。

人口是基因算法的另一個重要概念。在算法之中,我們看的是一組的基因,而非單一基因。人口 (基因數量)可能從 20至100至2000 不等。有如進化,你會將基因最好的一對交配,產生出最好的下一代,期望它們的下一代比父母更好。

交配的字符串,例如 “Hello, World!” 是很簡單的。你可以從兩個字符串從中間或者隨機的一點切開,再組合為新的兩組字符串,例如:

Hello, wprld! (1)
Iello, world! (1)
從中間切開再組合為:
Iello, wprld! (2)
Hello, world! (0)

你可以看到,其中一個是集合了兩者的最差部份,但另一個則為「完美體」。交配就是帶給下一代基因的過程。

進化/變化
交配本身有一個問題,近親相交。如果你一直一代一代的自我繁殖,你會到達一個局部最佳點,然後無辦法離開,結果可能很好但不一定是全局的最佳點。所以要帶入變化。

要強調的一點是只有交配的話,基因算法能做的東西並不多。基因算法一定要組合交配和變化才會帶來滿意的結果。交配可以找出更優秀的基因,而變化則帶來更多的可能性。

試想像世界有很多高山,其中有一個最深的山谷,但也有很多其他的山谷。山谷的中心點都比附近其他的地形低,但只有一個最低點。找出這個最低點就像隨機將球放到山中不同的地方。球會停在低點,但只有一個球找到最低點,而其他會停在相對的低點。你要令到最少一個球找到山中的最低點,做法是踢一下在低點的球,令它不要在低點停留太久。

變化是完全隨機的,帶入一個隨機的字符到字符串中,例如以下兩組基因:

Hfllp, worlb!
Hfllp, worlb!

以上有兩組完全一樣的基因,所以它們之間的下一代也會完全沒有變化,便不會找到最低點。但如果100組基因之中有一個字符是隨機的話,隨著時間,#2基因會變化為 “Ifllp, worlb!” ﹣然後整個過程便會有進展因為它們的下一代會和它們的父母不一樣。

你可以自已決定如何和何時進行變化。自己實驗一下。我的代碼例子有一個非常高變化率 (50%),這只是一個例子,你可以使用 1%。我的代碼也只改變一個字符,上或下一個 ASCII 但你可以使用其他更強烈的變化。實驗,測試是唯一的方法。

總結
基因是代表你的問題的一些可能的答案。例子中的基因有一組長度13字符,可以計算費用值,可以交配,變化。

將這些都化為物件導向的概念,基因就是一個類
屬性:
Genetic code
Cost/fitness score

方法:
Mate
Mutate
Calculate Fitness Score

人口
最後還有幫助基因互相作用的「人口」類
人口是一組基因,基本上人口維持不變 (基因會死亡,交配) 人口中的基因會慢慢降低費用,向最佳點進發。人口中的基因的數量是可選的 10,100,10,000 都可以。數量的多少有各有好處壞處,也是同一句,自己實驗下下吧。

人口還有一個屬性,是世代。一個世代的工作有:
計算每一條基因的費用值
用費用值排序
最弱的基因死亡
最強的交配,生出下一代
隨機的基因變化
檢查問題是否已經到了「最佳點」

﹣﹣﹣﹣譯文暫完

基本概念完成了,下一篇會真正進入代碼的實現方法。
我也會加入一些我的代碼,令基因進化的過程加入一點圖像

Google