19th Sept (Wed) Machine learning 102

上一部分

開始和結束

初始化人口並不困難,只要填滿隨機的基因。例子中,一個隨機基因和最佳點的距離(費用值)應該是巨大的。下面的代碼的平均費用值達30000之多,但這無相干,這正是進化交配存在的原因。至於停止的時機則比較麻煩。這個例子中比較簡單,基因和目標的基因完全一樣就完成了,即費用值為零。但也有複雜的時候。或者你並不知道最低的值,或者找尋的是最高值,而你事前不知道絕對的最高值。在這些情況之下你需要定義一個完成的條件,可以是任何你想要的條件,例如一千個世代之內,最佳值維持不變。這樣的條件可能令你沒有達到全局的最佳點,但有時候「接近最佳點」已經足夠。我即將會寫另一篇關於使用 PHP基因算法的文章,但些許不同的題目,會應用到以上的「接近最佳點」的概念。

代碼
終於到了代碼的時間,我們會使用物件導向的方法,盡量使用簡單的代碼完成工作。

var Gene = function(code) {
        if (code)
                this.code = code;
        this.cost = 9999;
};
Gene.prototype.code = '';
Gene.prototype.random = function(length) {
        while (length--) {
                this.code += String.fromCharCode(Math.floor(Math.random()*255));
        }
};

簡單的類。使用字符串作為構造構造函數,預設一個高的費用,一個隨機的方法隨機一組基因。
Gene.prototype.calcCost = function(compareTo) {
        var total = 0;
        for(i = 0; i < this.code.length; i++) {
                total += (this.code.charCodeAt(i) - compareTo.charCodeAt(i)) * (this.code.charCodeAt(i) - compareTo.charCodeAt(i));
        }
        this.cost = total;
};

費用函數傳入目標字符串,一個一個比較ASCII ,方根
Gene.prototype.mate = function(gene) {
        var pivot = Math.round(this.code.length / 2) - 1;

        var child1 = this.code.substr(0, pivot) + gene.code.substr(pivot);
        var child2 = gene.code.substr(0, pivot) + this.code.substr(pivot);

        return [new Gene(child1), new Gene(child2)];
};

交配函數傳入另一組基因,找出中間點,切開組合,返回兩組新的基因。
Gene.prototype.mutate = function(chance) {
    if (Math.random() > chance)
            return;

    var index = Math.floor(Math.random()*this.code.length);
    var upOrDown = Math.random()<= 0.5 ? -1 : 1;
    var newChar = String.fromCharCode(this.code.charCodeAt(index) + upOrDown);
    var newString = '';
    for (i = 0; i < this.code.length; i++) {
        if (i == index)
        newString += newChar;
        else
        newString += this.code[i];
    }

    this.code = newString;
}

變化函數傳入變化的機率,如果發生變化的話則隨機抽一個字符變化。變化的算法是隨機ASCII 加或減一。
var Population = function(goal, size) {
        this.members = [];
        this.goal = goal;
        this.generationNumber = 0;
        while (size--) {
                var gene = new Gene();
                gene.random(this.goal.length);
                this.members.push(gene);
        }
};

人口的構造函數傳入目標的字符串和人口的大小,隨機產生人口數量的基因。
Population.prototype.sort = function() {
        this.members.sort(function(a, b) {
                return a.cost - b.cost;
        });
}

人口中的基因需要一個由小至大的費用值排序函數。
Population.prototype.generation = function() {
        for (var i = 0; i < this.members.length; i++) {
                this.members[i].calcCost(this.goal);   
        }

        this.sort();
        this.display();
        var children = this.members[0].mate(this.members[1]);
        this.members.splice(this.members.length - 2, 2, children[0], children[1]);

        for (var i = 0; i < this.members.length; i++) {
                this.members[i].mutate(0.5);
                this.members[i].calcCost(this.goal);
                if (this.members[i].code == this.goal) {
                        this.sort();
                        this.display();
                        return true;
                }
        }
        this.generationNumber++;
        var scope = this;
        setTimeout(function() { scope.generation(); } , 20);
};

人口類中最難明的部份是 generation 函數。display() 會輸出世代中費用最低的基因和完成的時候將世代間最低費用值的變化圖像化,再加入一點時間上的推遟。
這個例子中交配只包括兩個最佳基因,而你絕對可以使用其化的算法。
window.onload = function() {
        var population  = new Population("Hello, world!", 20);
        population.generation();
};

初始化。

這算法並不快,你可以簡單的找出緩慢的部分改進,我支持你修改我的算法。

以上的代碼其實可以使用任何的其化程式語言完成

完整代碼: https://github.com/joetsuihk/machine-learning

18th Sept (Tue) Day 7

Extremely busy day.
So sorry that the Machine learning translation had to postpone to tomorrow
I should really write some blogs in advance.

Actually other than writing 30 blogs in 30 days,
I also run 20 minutes every other day now.
Running had slowly become popular in HK (with cycling)
the habit might came from Japan, cycling from Taiwan
As my only purpose is do some exercise,
running is dead easy to start and no cost at all.
I listen to L-arc-en-cial "Clicked 13 best single" every time I run,
and i know I ran around 20 minutes when the music hits "dive to blue"
I want to run until "Honey" which is my favorite song in the album,
but that is a few more minutes to go....
I will start running faster instead of running longer period when I am very comfortable with 20 min running.

Tomorrow will setup ubuntu server 12.04 on latest CPU E3-1245V2, god bless me.

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 都可以。數量的多少有各有好處壞處,也是同一句,自己實驗下下吧。

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

﹣﹣﹣﹣譯文暫完

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

16 Sept 2012 (Sunday)

一連補了兩日的 blog
連續寫三十日的blog 還真的不容易呀

我剛看過我的 Google analytics
Raspberry PI 的 impression 比 Drupal 或者技術相關的其他關鍵字多數倍
看來我都需要順應民意努力鑽研一下 Raspberry PI
和為大家更新 Raspberry Pi 的最新消息了

15 Sept (Sat) Fabric 初心使用

Fabric 是一個 command line 的 工具
一個remote ssh 的工具
之前我已經介紹過我在南華早報時deploy 的 scripts
使用的是 rsync + mysqldump + ssh tunneling
沒有辦法記住全部命令的情況下使用copy & paste commands
也使用得很好
只是 fabric 的好處是你可以將這些 command 簡單的包裝起來
你便可以fab deploy來完成

先定義 user, host:

env.user = 'joe'
env.host = 'example.com'

def deploy():
  domain = 'example.com'

  with cd('/srv/www/' + domain + '/public_html'):
    run('git pull')
    run('git checkout master')

以上的代碼便會在指定的資料夾內執行 git pull
使用 git 代替 rsync 將代碼上傳到伺服器

又或者

def restart():
  run('sudo service apache2 restart')

重新啟動伺服器

然後可以直接串起: fab deploy restart

你也可以定義環境變數:

def staging():
  env.host = 'dev.example.com'

def live():
  env.host = 'example.com'

然後fab staging deploy restart deploy 到 staging
fab live deploy restart deploy 到 live

Fabric 還有很多方便的進階功能可以使用
但以上的簡單代碼已經可以帶來使用的快感,令你喜歡它
其他的階用法還是以後再談

(文為16日後補)

Pages

Google