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裡,要如何製造好的競爭選擇標竿來產生出較佳解,那就是另一個研究議題了。