Tuesday, December 23, 2008

[UTips. 60] zh-autoconvert

  • zh-autoconvert
  • GB, BIG5互轉工具,安裝方式如下:

    sudo apt-get install zh-autoconvert

    執行範例如下:

    可用編碼如下:

    gb, big5, hz, uni, utf7, utf8

Sunday, December 21, 2008

[C/C++] AVI Audio/Video Extractor

  • AVI Audio/Video Extractor
  • Download: AviAVExtractor.zip

    AVI Audio/Video Extractor是兩年前為了了解基本的影音架構處理而撰寫的小程式,最近終於有時間將這個小程式做些微的修正發佈出來。整個程式演算沒有什麼難度,只是大量的使用結構與檔案的輸入輸出的處理。基本的AVI結構圖如下:

    上面這張概略圖已經不是最原始的AVI架構,我參照了OpenDML標準定義所混和繪製的。

    本範例程式最原先版本是參照微軟的AVI RIFF File Reference文件定義所撰寫的,網址如下;

    http://msdn.microsoft.com/en-us/library/ms779636(VS.85).aspx

  • RIFF
  • AVI屬於RIFF(Resource Interchange File Format)標準定義內的格式,所以在圖上你可以看到一開始會有12bytes為RIFF的資訊(如右圖),每一個區塊佔用4bytes,第一個區塊紀錄著RIFF這四個字元,第二個區塊則是紀錄這整個檔案的大小,例如圖中的16進位數值轉為10進位就是13044728 bytes,會比實際檔案大小少於8 bytes,因為13044728是不包含檔案前8個bytes。第三個區塊則是紀錄著此檔案的類型。同樣的紀錄方式應用在WAVE檔也是如此。RIFF是由Microsfot跟IBM所定義的,詳細訊息可以參考wikipedia - Resource Interchange File Format

  • AVI Main Header
  • 緊接著RIFF之後就是AVI結構裡第一個主LIST區塊(標頭定義區塊),在avih識別字之後會有一個AVI Main Header,在這個範例裡我們僅使用他來判別此檔案有多少個串流(dwStreams),詳細的結構資料你可以參考微軟的AVI Main Header

  • AVI Stream Header
  • 讀取完AVI Main Header之後緊接著是第一個子LIST,一個AVI檔通常會有2~4個sub-list,而Audio跟Video通常都在前兩個sub-list裡,而其餘的則是紀錄字幕或者一些保留資訊。在這個範例裡我們只藉由Stream Header來判斷目前此串流的格式(fccType),詳細結構你可以參考微軟的AVI Stream Headers

  • Bitmap Info Header
  • 每一個子LIST區塊都會有AVI Stream Header,紀錄著此串流的類型。以第一張的AVI架構圖來說,我們假設stream0為vids(也就是視訊串流),那這時就要讀取點陣圖的標頭檔,在這個範例裡我們只將此訊息儲存保留至視訊分離時使用,詳細結構請參考微軟的Bitmap Info Header

  • Wave FormatEx
  • 讀取完視頻的標頭資訊之後,stream1則是為音頻標頭資訊,範例裡我們使用標準的wave格式標頭檔WAVEFORMETEX來讀取,同樣的也是保留原始資訊作為之後分離音訊使用,詳細結構請參考微軟的WAVEFORMETEX

  • movi
  • 讀取完第一部份的主LIST,第二部份的LIST則是紀錄著音訊視訊的實體資料,以某一區塊的已壓縮視訊區塊為例,如下:

    第一個識別字00dc代表著stream0的已壓縮視訊資料,另外還有00db(stream0未壓縮視訊),以及01wb(stream1的音訊區塊),所以前面兩個字元00/01代表著串流的位置,二後兩個字元dc/db/wb則是串流的類型,詳細資料可以參考微軟的AVI RIFF File Reference

  • Index
  • Index在AVI格式裡是optional的,但是在這個範例程式裡必須仰賴有index的AVI才能正常處理,index內每一個entry定義如下:

    struct AVIOLDINDEX_ENTRY{
    DWORD dwChunkId;
    DWORD dwFlags;
    DWORD dwOffset;
    DWORD dwSize;
    };

    除了dwFlags在這個範例我們沒有用到之外,其餘的變數我們必須依照index的數據來搜尋實體資料。dwChunkId決定所紀錄區塊的串流類型,dwOffset則是紀錄此區塊的位置(不一定是絕對位置,所以在設計時必須自行修正這個問題),dwSize則是此區塊的大小,詳細資訊請參考微軟的AVIOLDINDEX

  • Demo
  • 使用GCC4.2.4在ubuntu8.04底下編譯之後會產生AviAVExtractor這個檔案,使用方式如下(以附件所附的imagine.avi檔案為例):

    處理完後音訊跟視訊的檔案分別為audio0.wav, video0.avi。

  • Discussion
  • 原始碼只有三個:

    AviDefinition.h : AVI and its related structure definition

    AviAVExtractor.h : header for AviAvExtractor.h

    AviAVExtractor.c : Main Program

    其中我將一些常用的AVI結構定義在AviDefinition.h裡面,為了程式設計方便,我所定義的結構可能會跟微軟上所列的有些出入。

    本程式僅是簡單展示如何做音訊視訊分離,仍有許多地方並未實做:

    1. 無index區塊的處理
    2. JUNK區塊對齊
    3. OpenDML標準格式支援
    4. 字幕處理
    5. 其他影音壓縮格式支援
    6. ....

    所以還有很多地方可以繼續補強,當然如果你是要做一些影音處理的專案,為了效率還是直接使用現成的API會比較快且穩定。

  • Reference
  • Microsoft MSDN - AVI RIFF File Reference

    OpenDML AVI File Format Extensions

Friday, December 19, 2008

[UTips. 59] GHex

  • GHex
  • 在windows底下我們要將檔案以16進位編輯時可能會使用UltraEdit,在linux底下你可以使用GHex這個方便的小工具來完成。安裝方式如下:

    sudo apt-get install ghex

    安裝完後會在Applications->Programming->Hex Editor

    上面範例是用GHex開啟一個圖檔。

Wednesday, December 17, 2008

[Windows] SmitfraudFix

  • SmitfraudFix
  • 一段時間沒使用windows系統之後,處理中毒問題的能力就下降許多,這裡推薦一個清除malware的小工具-SmitfraudFix,官方頁面如下:

    http://siri.geekstogo.com/SmitfraudFix.php

    程式很小,下載回去依照畫面指示清除即可。

    SiRi將一些清除病毒的例行工作寫在SmitfraudFix程式裡,節省了自行一一清除的時間,想要了解更多的安全軟體資訊可以參考他的blog.

    http://siri-urz.blogspot.com/

Sunday, December 14, 2008

[UTips.58] DosBox

  • DosBox
  • Dosbox除了讓較新的windows系統可以執行dos程式之外,也可以讓linux系統藉由這個模擬器來執行dos的軟體,安裝方式如下:

    sudo apt-get install dosbox

    安裝完後會在Applications->Games找到DOSBox emulator,打開之後使用方式如下:

    mount c: /xxx

    其他/xxx是你要掛載的檔案路徑。

Friday, December 12, 2008

[C/C++] id3lib

  • id3lib
  • Download: id3_test.zip

    id3lib也是一個跨平台的ID3資訊編輯的API,當初我原本想藉由此API來設計一個多功能的ID3編輯器,後來發現網路上早已有許多現成的好用工具,因此就罷。官方網頁如下:

    http://id3lib.sourceforge.net/

    編譯方式如下:

    ./configure

    make

    sudo make install

    預設library安裝路徑如下:

    /usr/local/lib

    在程式開發編譯過程時如果出現undefined reference to 'compress' and 'uncompress'這類問題時,請在makefile載入下面的library

    -lz

    這裡我還是提供一個Linux下的簡易的範例,主要程式碼是由id3lib裡的範例複製過來的。

    範例執行畫面如下:

Thursday, December 11, 2008

[C/C++] IrrKlang

  • IrrKlang
  • Download: IrrKlang_test.zip

    IrrKlang是一套跨平台的Sound API,在程式開發過程中如果需要載入音效的功能倒是可以考慮使用這個API。IrrKlang還有Pro版是給商業用途的開發者,需要付費。官方頁面如下:

    http://www.ambiera.com/irrklang/index.html

    下載完解壓縮即可使用,不需自行編譯libary。支援.Net, Linux, Mingw等開發平台,只需將對應的library和include複製到你的開發環境上即可呼叫使用,相關說明文件已經包含在官方的下載包裡。

    我提供的下載範例是適用於Linux的系統,裡面只有簡單的讀取音樂播放的範例,由於音樂檔案較大,我就沒有附上了。

Monday, December 08, 2008

[SQL] MySQL++

  • MySQL++
  • Download : MySQL_linux.zip

    MySQL++是一套跨平台的C++與MySQL互通的API,下載頁面如下:

    http://tangentsoft.net/mysql++/

    編譯方式如下,跟一般的程式編譯沒有兩樣:

    ./configure

    make

    sudo make install

    編譯完後的libary跟include的路徑如下:

    mysql++ include : /usr/local/include/mysql++

    mysql++ library : /usr/local/lib

    除此之外你還需要連結mysql的inlcude:

    mysql include : /usr/include/mysql

    編譯程式時你還需要以下的library:

    mysqlpp
    mysqlclient

    下載範例裡是使用MySQL預設的資料庫(mysql)內的資料表(help_keyword)。mysql相關程式安裝可以參考這一篇[UTips. 52] Apache, PHP, MySQL, phpMyAdmin

    執行範例畫面如下:

Saturday, December 06, 2008

[ANN] Fast Artificial Neural Network (FANN)

  • Fast Artificial Neural Network (FANN)
  • FANN是一個基於BackPropagation的Neural Network API,其中還包含了quickprop和RPROP (Resilient backpropagation ) 。對於初學卻又不想寫程式的人來說這個API可以幫你節省許多時間,但是話說過來,如果您真的想要使用neural network設計程式,到頭來還是多要自己寫。

    官方頁面如下:

    http://leenissen.dk/

    Reference Manual:

    http://leenissen.dk/fann/html/files/fann-h.html

    下載頁面如下:

    http://leenissen.dk/fann/

  • 編譯
  • For Linux:

    ./configure

    make

    sudo make install

    編譯完後的library會在/usr/local/lib裡,可以參考這一篇[UTips. 57] Shared Libary Path來設定library的路徑,或者直接寫在makefile裡面。

    我利用FANN API簡單寫了一個範例如下:

    Download: FANN_linux.zip

    範例畫面:

[UTips. 57] Shared Libary Path

  • shared Library Path
  • 常常要編譯程式卻老是忘記shared library的編輯位置,這裡做個簡單的紀錄。

    在ubuntu底下要編輯下面的檔案:

    sudo nano /etc/ld.so.conf

    編輯完後執行下面的指令即可:

    sudo ldconfig

Friday, December 05, 2008

[ANN] Probabilistic Neural Network

  • Probabilistic Neural Network
  • Download: Probabilistic.c

    機率神經網路(Probabilistic Neural Network)是由D.F.Specht於1988年所發表的,此網路是基於貝氏分類器(Bayesian Classifier)所設計出來的,固然機率神經網路比較適合應用在分類問題上。其優點是採一次學習,運算速度極快,但是缺點是隱藏層裡的節點數會受訓練範例所影響,在處理較複雜的問題時所需的記憶空間就會比其他類型的神經網路大了許多。

  • Table for XOR Probelm
  • XOR輸入輸出分類表格如上

  • Architecture for XOR Problem
  • 依照上面的表格所設計的架構

    輸入層:2個nodes (對應到兩個輸入)。

    隱藏層:4個nodes(對應到4個訓練範例)。

    輸出層:2個nodes(對應到兩種輸出可能性)。

  • 網路計算公式
  • 網路加權值初始化:

    Whi: inputs到hidden nodes的weights值

    Who: hidden nodes 到 output nodes的weight值

    跟之前的網路架構不一樣的是他們的初始值是由訓練範例而定。

    sigma是平滑曲度,這裡設定為 1。

    網路計算公式:

    隱藏節點計算公式

    加總各output的weight值:

    計算output:

    最後設定最大輸出值為1,其餘為0(這個範例裡只有兩個輸出,所以其中為1,另一則為0):

  • 範例輸出畫面
  • 這裡我只是介紹最簡易的Probabilistic Neural Network的簡單應用,改良後的PNN(MPNN)能分類的問題就不僅如此了。

Saturday, November 29, 2008

[UTips. 56] uif2iso

  • uif2iso
  • 前幾天才發現原來AcetoneISO2不支援uif格式,這裡推薦一個小程式可以把uif轉成iso:

    http://linux.softpedia.com/get/Utilities/UIF2ISO-35316.shtml

    把他解開來make編譯即可,使用方式如下:

    ./uif2iso src.uif dest

    src.uif:你要轉換的來源檔名

    dest:轉換後的檔名,不需要加上副檔名

    哪天有閒時間再幫uif2iso轉成GTK版好了。

Wednesday, November 19, 2008

[ANN] Hidden Layers Effect

  • Hidden Layers Effect
  • 連續幾篇的Neural Network的介紹與最佳化,我們已經可以透過Trainer有效的讓神經網路學習玩Tic-Tac-Toe遊戲,從上一篇[ANN] Self-Adaptation Gaussian Mutation的結果我們可以看到網路學習能力因為使用自適應參數而下降。這裡我們依然延續著[ANN] Spatial Layer Effect這一篇的架構移除Self-Adaptation Gaussian Mutation去探討多一層隱藏層的影響。

  • Neural Network Architecture
  • 跟之前的架構相比只是多了一層隱藏層,且節點數為9個,總共的weights和biases值為166,比原先的76大了一倍多。Total weights & biases計算方式如下:

    Spatial Layer : (5+1)+(7+1)+(5+1)+(5+1)+(9+1)+(5+1)+(7+1)+(5+1)+(7+1) = 66

    Hidden Layer: (9+1) * 9 = 90

    Output Layer: (9+1) * 1 = 10

    Total: 66+ 90 +10 = 166

  • Simulation Parameters
  • Population: 100

    Generation: 1000

    Win/Lose Score: Winner: +1, Loser: -1 , Draw: 0

    Number of Games: 10

    Selection : Tournament Selection

    Trainer: AI_Level III with random moves

    除此之外為了因應多一層隱藏層的效應,我將activation function的參數調大了一點。

  • Results
    • Neural Network v.s. AI
    • 多了一層隱藏層的數據跟沒有隱藏層的數據幾乎是一樣的。

    • Survival Times
    • 因為沒有了Self-Adaptation Parameters平均存活曲線圖自然會是呈現震盪的狀態,值得注意的是曲線的每一次震盪轉折代表著網路能力的改變,多數情況下,網路存活次數有巨大改變時,代表那是網路能力的轉折點(也有可能會變差喔!如果網路設定存在著衝突或缺陷時),只是在這個例子不好觀察出這個效應。

    • Standard Deviation for Number of Win Games
    • 分值標準差在100代左右之後都在1.2上下震盪,並沒有太大的變化。

  • Discussion
  • 在這個例子裡多了一層隱藏層之後,整體網路的學習能力並沒有什麼提升,但不能就這樣否決掉多一層隱藏層的所帶來的優點。我在其他模擬實例中,多一層隱藏層確實有效的幫助提昇網路的網定性。連續幾篇的介紹,我們分別討論Spatial Layer, Self-Adaptation Gaussian Mutation 和 Hidden Layer對網路學習能力的影響,在數據的比較分析中我們一直執意在有多少個網路能更贏過我預先設計好的專家程式,但是事實上我們並不能一味的追求整體的學習能力,因為在這個模擬案例裡我並不是使用嚴謹的Supervised Learing,所以學習後的網路整體的能力我們是無法在在上面的數據可以得知的。但是在更深層的數據分析之下,我發現多一層隱藏層的Spatial Layer的Neural Network在多次模擬下僅能產生出Average Strong的fitness function。但是在沒有多一層隱藏層的spatial layer的神經網路卻能產生出extraordinary strong的fitness function。

    總結一下這一系列的主題研究我調整了什麼

    • Randomizing Trainer
    • Spatial Layer
    • Self-Adaptation Parameters
    • Activation Function Coefficient
    • Population
    • Mutation Rate Coefficient
    • Hidden Layers
    • Selection Mechanism
    • Win/Lose Value Assignment
    • 紅色的部份代表極具影響力的因子,綠色的部份代表著必須小心的細節設定,而藍色的部份則是為可選擇性調整的部份,重要性依顏色深淺而定。雖然藍色部份我列為可選擇性調整替代,但不代表他不影響著結果,除了像本主題Hidden Layers改變會有劇烈的結果變動之外,另外像是Selection的使用也是有不少人在研究的議題,不同的選擇方式會有不同的選擇壓力,影響也是不小的,有機會的話再針對這部份做說明。

      總結一下這一系列使用的文章:

      [ANN] FeedForward MultiLayer Perceptron

      [ANN] Gaussian Random

      [EP/GP] Random Opponent

      [EP/GP] Evolution with Internal Observer

      [ANN] Spatial Layer Effect

      [ANN] Self-Adaptation Gaussian Mutation

  • 參考
    • D.B. Fogel "Using evolutionary programing to create neural networks that are capable of playing tic-tac-toe," Neural Networks, 1993., IEEE International Conference on Volume , Issue , Page(s):875 - 880 vol.2
    • D.B. Fogel "Blondie24: Playing at the Edge of AI, San Francisco, CA: Morgan Kaufmann, 2002.
    • "Training an artificial neural network to play tic-tac-toe," Sebastian Siegel, ECE 539 Term Project, 2001.
    • Lucas, S. M. "Learning to Play Othello with N-Tuple Systems, Australian Journal of Intelligent Information Processing Systems," Special Issue on Game Technology, Vol 9, No. 4 pp 01--20, 2007.
    • Hornik, K., Stinchcombe, M. and White, H. "Multilayer feedforward networks are universal approximators," Neural Networks, 1989., 2, 359-366.
    • Chester, D.L. "Why Two Hidden Layers are Better than One," IJCNN-90-WASH-DC, Lawrence Erlbaum, 1990., volume 1, 265-268.
    • Weigend, A. "On overfitting and the effective number of hidden units," Proceedings of the 1993 Connectionist Models Summer School, 335-342, 1994.
    • Geman, S., Bienenstock, E. and Doursat, R. "Neural Networks and the Bias/Variance Dilemma", Neural Computation, 4, 1-58, 1992.
    • AI FAQ, http://www.faqs.org/faqs/ai-faq/

[ANN] Self-Adaptation Gaussian Mutation

  • Self-Adaptation Gaussian Mutation
  • 在上一篇[ANN] Spatial Layer Effect我們看到良好的Spatial Layer可以有效提昇學習效率,但是光只是這樣的提昇還不能滿足我們追求更好結果慾望。這一篇裡我們要更動原先的Gaussian Mutation變成Self-Adaptation Gaussian Mutation,而Gaussian Mutation部份則是沿用了Gaussian Random Distribution[ANN] Gaussian Random為基礎,藉由字適應參數的使用來觀察網路學習能力的變化。

  • Mutation
  • Mutation在演化計算裡非常的重要,因為他扮演著繁延後代的角色,而之前的模擬裡我們都只是當純的使用Gaussian Mutation或者是更簡易的[-1, 1]的Standard Random Distribution,來更改weights跟biases的值,這樣的使用方式雖然可以有效的找出最佳解,但是卻會形成網路不穩定的狀況,所以這裡我們加了一個Self-Adaptation的參數,讓突變的過程雖著網路演化的代數增加讓每一個weight依造著適應參數去調整他們的改變量,但前提是你的網路架構良好,且其他參數都沒問題時才能這樣使用。Self-Adaptation Gaussian Mutation公式如下:

    其中

    i = 1, 2, 3, ...... 50 (每一代裡有50個parents)

    j = 1, 2, 3, ...... 76 (總共有76個weights(包含biases))

    J = 76 (weights 和 biases的總數量)

    如此可以算出tau為0.239左右。

  • Simulation Parameters
  • Population: 100

    Generation: 1000

    Win/Lose Score: Winner: +1, Loser: -1 , Draw: 0

    Number of Games: 10

    Selection : Tournament Selection

    Trainer: AI_Level III with random moves

    除此之外,我還稍微對AI_Level III的亂數因子做小幅度的修正,以及activation function的a值做了一些調整。已達到有效的非線性轉換。

  • Results
    • Neural Network v.s. AI
    • 由上面的數據可以很明顯的感覺到網路學習能力下降許多,這樣的結果並不是我們所期望的。

    • Survival Times
    • 到了1000代平均存活次數已經高達到650次,從這個數據看來這個模擬沒有必要在繼續跑下去,因為他已經收斂了。

    • Standard Deviation for Number of Win Games
    • 平均得分值的數據並沒有給予我們太多的訊息。

  • Discussion
  • 在這個例子裡Self-Adaptation Parameters並沒有有效的的幫神經網路演化出好的策略,但並不代表Self-Adaptation Gaussian Mutation是一個不好的突變方式,整個模擬失敗可以從兩個方面來探討,第一,training set的部份並沒有非常的完善,也許這是導致網路收斂至某個局部最佳解。第二,網路架構的完整性,在這個範例裡網路架構只用了76個weights,以tic-tac-toe這個問題來說可以說是相當的少,在這麼少的wieght架構之下使用Self-Adaptation反而會讓網路失去尋找global maximum的解,進而導致網路演化失敗。(這部份的影響我也在解XOR的問題中發生過。)。所以解單的來講如果你的網路架構複雜,使用Self-Adaptation Gaussian Mutation的確能幫你在短時間演化出好的結果,但是不免也有失敗的可能性就是了。

[ANN] Spatial Layer Effect

  • Spatial Layer Effect
  • 在上一篇[EP/GP] Evolution with Internal Observer我們談到使用內部觀察者訓練網路時加上一點點的隨機亂數可以有效提昇學習效率,但是光是從這方面來改善並無法有很大的突破,從之前的結果可以得知,AI Level I 始終無法被大幅度的克服。這一篇我們要介紹Spatial Layer在學習效率上得影響性,用一個較好的Spatial Layer來提昇整體學習能力。

  • Spatial Layer
  • 什麼是Spatial Layer? 其實說穿了他只是一個隱藏層,只是在spatial layer裡的weight的排列計算方式不像單純的hidden layer是固定且一致的,以這一篇[ANN] FeedForward MultiLayer Perceptron的網路架構圖來說,隱藏層裡有9個節點,但是每個節點內部各有9個weight跟1個bias,所以各個節點的維度都是9(至於9這個數字是因為輸入層有9個inputs,所以才會有9個weigths),這樣的隱藏層設計非常直觀且簡單,但是卻無法有效的提昇網路學習能力,且會多計算了一些無用的節點。在這一篇範例裡我們依然是延續著之前的tic tac toe架構來設計Spatial Layer。

  • Neural Network Architecture
  • 延續著之前的三層架構,只是Hidden Layer被換至成Spatial Layer,原先的九個點被替代成九個樣式。總共用了76個weights(包含biases),比起原先的100個weights(包含biases)少了1/4。"理論上來講"計算速度會快,但是學習能力會變差。

  • Spatial Layer Patterns
  • 井字遊戲是3x3的板子,總共有9格,所以我就設計了九個patterns去對應到板子上的每一格,而樣式的設計方式則是依照此遊戲的規則。

  • Simulation Parameters
  • 依照下列的參數去模擬:

    Population: 100

    Generation: 1000

    Win/Lose Score: Winner: +1, Loser: -1 , Draw: 0

    Number of Games: 10

    Selection : Tournament Selection

    Trainer: AI_Level III with random moves

    其餘參數是跟之前的模擬一樣的,只是換製成Spatial Layer。

  • Results
    • Neural Network v.s. AI
    • 跟上一篇的圖來做比較起來整體能力並未提升許多,僅有在AI_level I 部份稍微提升一點。

    • Survival Times
    • 跟先前的存活次數的數據比起來,改成spaital layer之後的survival time似乎降低了,到了1000代平均存活次數仍在1000代左右,代表著網路還有成長的空間。

    • Standard Deviation for Number of Win Games
    • 得分值的標準差在50代之後將幾乎在1.3上下震盪,直到1000代都沒有太大的改變。

  • Discussion
  • 從這一篇的模擬我們可以得知良好的Spaital Layer設計可以節省網路節點的使用,達到同等級的學習能力。但究竟為什麼一個好的Spatial Layer卻有如此的功效,以神經網路的數學理論來看,越多的weight跟bias可以達到更複雜的切割,但是在這裡我們使用的weights(包含biases)(76)小於原先單純的hidden layer所使用的weights(包含biases)(100),所以單純以數學的high order hyperplane separation來解說是無法解釋的通。從數值分析來看,每一個pattern就是一個weight matrix,而這些weight matrix都是特別依造遊戲的規則來設計,自然我們可以減少無用的weight 值計算之外,也取得真正要使用的部份,這就是為什麼Spatial Layer能有較好的學習效果。可惜的是在這個例子裡spatial layer並沒有大量突顯出他的優點。

Saturday, November 08, 2008

[EP/GP] Evolution with Internal Observer

  • Evolution with Internal Observer
  • Download: Evolution_TicTacToe_Internal_Observer.zip

    多數情況下,在目前的演化程式設計上我們仍然多使用supervised的架構,因為unsupervised模式所造成的時間成本很高,以及訓練後的準確性不優於supervisered,所以多數人仍採用其他透過具有專業知識的方式來做machine learning(reinforcement learning, temporal difference learning)。這裡我沿用[ANN] FeedForward MultiLayer Perceptron的程式來介紹內部觀察者,internal observer的角色在這次的主題範例裡扮演著競爭的標竿,每一代所產生的neural network如果無法在與internal observer競爭之後取得前50%的名次就會被淘汰,這樣的設計方式廣泛使用在一些較複雜且難以以數學模組精準算出誤差的問題,遊戲就是其中之一(當然這裡的tic tac toe並不屬於複雜問題。),比起完全無監督的演化網路來說,有內部觀察者的演化會比較有效率,我的observer可分為三級,是經過我簡單設計出來的AI:

    • Level I :ADR (Attack, Defence, Random Move)
    • Level II :ADCR (Attack, Defence, Center Move, Random Move)
    • Level III :SADCR(Super Attack, Defence, , Center Move, Random Move)

    基本上就是基於tic tac toe的規則先做攻擊,再做防守,最後亂數選擇一個位置,其餘的就是選擇中心點,選擇高動線位置,或者是一些例外處理,這裡的等級一跟等級二只差了中心點的選擇而已,而等級三則是做比較多的例外處理。

    模擬參數如下:

    population size: 100 (50 parent+ 50 offspring)

    generation: 1000

    Number of games for each neural network: 10

    selection: tournament selection with expert observer

  • 結果
  • 由圖表數據可以觀察到,使用AI_level3來做observer不到50代就已經有大部分的神經網路可以贏過AI_level3,但是反觀AI_level2跟AI_level1卻發現結果沒有AI_level3來的好,難道是用什麼等級去做訓練才能得到那個等級的能力嗎?

  • Average Survival Time
  • 網路在每一代裡的平均存活次數,可以發現年代越高,存活越久,同時也表示著網路已經邁入0成長的狀態。

  • Standard Deviation for Number of Win Games
  • 很多情況下Standard Deviation的圖會對應到第一張圖(通常是在網路比較穩定的狀態時),一般來講我都會使用Survival Times跟standard deviation這兩張圖來觀察網路的收斂狀況。

    回到先前的問題,使用比較強的AI來做observer不一定比較好?是的,更準確的說應該是observer必須具有更多的隨機性,越強的observer他有更多特殊策略,但卻有可能忽略掉一些基本的策略,以及隨機的多樣性,反而會讓網路趨向只能解決特定的輸入參數,而無法去處理其他更多的輸入變化,進而導致一個網路可以贏過強的策略,卻輸給一個弱的策略。所以最簡易的解決辦法就是在trainer裡加一些隨機程序,我隨便加了一些隨機情況重跑模擬後如下:

  • Neural Network v.s. AI

  • 由上圖跟第一張圖做比較可以發現雖然在跟AI_level 3的比較能力有下降一些,AI_level 2則是沒有多大的改變,但是AI_level 1的能力比較卻有明顯的上升,其碼有一半的網路是有能力贏過level 1的。比起原先的數據平均只有10個網路能贏來說,可以說是進步很多。更仔細的觀察 AI_level 1的數據,在40代左右,網路能力瞬間提升到平均有25個網路可以贏過level 1,但是到了1000代,有上升的趨勢,這個能力的提昇是仰賴競爭選擇的方式,所以選擇的壓力控制也是影響著演化的好壞。

    一般在做演化計算上我們會特別去注意training set的廣度與深度,才能產生出較好的fitness function。最佳化除了選擇的方式可以改良之外,其他還有網路架構的設計,資料計算的轉換等等都是可以提昇網路能力的方向。同樣的,如果將這樣的觀念套用在沒有專家知識干涉的natural evolution裡,要如何製造好的競爭選擇標竿來產生出較佳解,那就是另一個研究議題了。

Saturday, October 11, 2008

[ANN] FeedForward MultiLayer Perceptron

  • FeedForward Multilayer Perceptron
  • FeedForward Multilayer Perceptron(FFMLP),是典型的unsupervised neural network,了解[ANN] BackPropagation之後,FFMLP架構就更容易懂,因為在非監督的網路基本型裡的數學模組非常單純,但是要使用FFMLP來找出合適的fitness function就相當的困難。

    這裡以最簡易的tic tac toe遊戲來展示簡易的FFMLP應用範例,在這個範例裡是使用Evolutionary Neural Network的方式來訓練,且沒有經過特別的參數調整和適應函式的使用,自然學習能力一定比監督型的較差。

    Download : Evolution_TicTacToe.zip

    網路架構如下:

    很精簡的三層架構,輸入層、隱藏層、輸出層。

    輸入層:9個nodes(因為典型tic tac toe是3x3的板子,共九格)。

    隱藏層:9個nodes(簡單的對應到輸入層)。

    輸出層:1個node(輸出值範圍為-1~+1,我們任意定義+1為優,-1為劣)。

    網路計算公式如下(跟BackPropagation類似):

    Transfer Function(Input Activity):


    a值的調整必須視網路的複雜度來決定。

    Mutation(weight跟bias的調整):

    weight跟bias的改變量,則是簡單由Gaussian Random來給予可想而知,這樣的網路要達到好的收斂值勢必有一定的困難。

    這裡的mutation並不是針對原先的neural network做調整,而是由原先的neural network突變出下一代,例如原先有10個neural network,經過mutation之後就變成20個neural network,其中新產生出來的10個neural network就是原先的子代(offspring)。

    模擬參數如下:

    • Population : 100
    • Number of opponents for each neural network: 10
    • Generation: 200
    • Value Assign: Win: +1 point, Draw: 0 point, Lose: -1 point.

    演化流程圖:

    其中Tournament Selection的對手選擇方式使用了這一篇的程式碼[EP/GP] random opponent

    範例畫面:

    下面是經過200代的演化之後,挑出第一名的網路與人類對戰的情況,正常情況下,只要你有一點點的智商,基本上你是不可能會輸給電腦,最佳預期的狀況應該是平手,下面的Cross Player是我,Circle Player是電腦,我先取得優先權下了1,1這個中心位置(最佳位置),在第七步的時候我放一個水,最後電腦與我和局收場。

    在大部分的情況下所找出來的fitness function都有缺陷,有可能只會攻擊不會防守,或者反之,要解決這個問題就要從如何找出合適的fitness function方向下手,有興趣的人可以把程式碼下回去玩玩看。

    如果你想要讓程式圖形化,可以參考這一篇的[Gtk] Gtk Go/Reversi Board Template的原始碼,改成Tic Tac Toe的板子樣式修改即可。