学生実験2 : 探索アルゴリズムその2・ニューラルネットワーク





更新情報
  • [2008-12-07] 作成中．
  • [2008-12-12] 参考文献のリンク切れを修正．



進め方

内容と目標
  • 探索アルゴリズム1の目標に加えて，
  • （計算機実験を通して探索や最適化のイメージを掴む．）
  • （計算機実験を効率良く実施するために何を考慮すべきかを理解する．）
  • システムの挙動を観察し，入出力特性を考察する能力を養う．
課題と提出方法
  • オプションを除く全ての Level にトライし，レポートとしてまとめよ．口頭試問は希望するグループのみやります（加点対象）．
  • 1グループ1レポート提出．
  • メンバ（氏名・学籍番号）と担当内容を記載すること．
  • 提出物は以下の2つです．それらを「groupX」というフォルダに準備し，規定の場所に提出（アップロード）してください．印刷する必要はありません．
    • 提出物1: レポートファイル

      補足：LaTeXで作成し，PDF化したもの．

    • 提出物2: プログラム等の関連ファイル一式を圧縮したもの

      補足：tar.gz で圧縮する事．

  • 提出（アップロード）の方法

    1. 上記2つを「naha:~tnal/2008-search2-xxx/」に rsync で提出してください．保存する際のディレクトリ名は「groupX」のようにグループ名を使用する事．
    例えば，MacBook 上の ~/group1/ に提出物を保存しているならば，以下のように rsync する事で提出できます． rsync 自体の説明は例えばここを参照してください． 

    #実施日によってアップロード先が異なります！
#月曜日のクラスは「2008-search2-mon」へ．
prompt> rsync -auvze ssh ~/group1/ \
e0657xx@naha:/net/home/teacher/tnal/2008-search2-mon/group1/

#金曜日のクラスは「2008-search2-fri」へ．
prompt> rsync -auvze ssh ~/group1/ \
e0657xx@naha:/net/home/teacher/tnal/2008-search2-fri/group1/

    2. 提出後，提出報告をメールにて連絡ください． 確認次第リプライを返します．

  • プログラムのソースをレポート中に含める場合には，必要十分に留めること．不必要に全ソースを掲載するのは×．
  • レポート提出期限：実験日の1週間後までに 705 室へ（12/12のクラスの期限は12/19日，12/22のクラスは12/29．

    提出期限を過ぎたら，原則的に，受け取りません． 期限内に仕上げる事も重要なタスクです． ただし，一般社会でも通用する理由で遅れてしまう場合にはこの限りではありませんので，なるべく早く相談してください．

  • （希望グループのみ）口頭試問期限：レポート提出時が望ましいが，別日程にて行う場合には，遅くともレポート提出から4日程度を目安に予約する事．
  • 採点後，優秀なレポートを期間限定で公表します．

1. ニューラルネットワークとは？

人の脳を情報処理モデルとして単純化したシステムで，ニューロンと呼ばれる脳細胞を結合したネットワークの総称がニューラルネットワークである． 様々なモデルがあるが，目標の一つは「人間の脳そのものの処理をコンピュータで表現する事で，それまでコンピュータが不得手としていた/解けない問題を解決する」ことである．

各ニューロンは，入力信号 xi に重要度（重み） wi を掛け合わせた値の総和を算出し，その値に応じて自身が興奮（発火）するか否かを決定するシンプルな機械として定義される．

学習・探索のイメージ
単一のニューロン（単純パーセプトロン）のみで構成される2入力1出力の例を示す． 入力と出力は 0 or 1 を取るとした時，入力 x1, x2 の AND を出力させるように学習させる事は，「w1, w2, θをどのように設定するのが最適か（最も適切に分類する線引きをするためのパラメータ値の組み合わせは何か）？」という探索問題として定式化することができる．

Level 0: 実験環境の準備
  1. cvs の設定．
    1. ディレクトリ ~/bin を作成し，そのディレクトリを path 指定．

      ヒント：tcsh なら「~/.tcshrc」を参照．source するのを忘れない事．

    2. cvs-ie.sh を作成し，~/bin/ に保存．
    3. 実行権限を付加． 
      prompt> chmod u+x cvs-ie.sh
  2. 作業用ディレクトリの作成． 
    prompt> cd
prompt> mkdir info2
  3. 今回使用するソースファイルを cvs から取得（checkout）． 
    prompt> cd info2
prompt> cvs-ie.sh co teacher/tnal/nn
  4. 正常に checkout 出来れば，~/info2/teacher/tnal/nn 以下に3つのディレクトリ"CVS"(cvs管理用)，"bp_mo"(Level 1, 2), "nn_num"(Level 3) が作成されているはずです．

2. 動作確認実験

Level 1: 線形分離可．　　(2+5=7点)

実験内容

ソースのあるディレクトリ（~/info2/teacher/tnal/nn/bp_mo/）に移動し，以下の実験（Level 1.1, 1.2）を実施せよ．

  1. Level 1.1: サンプルソース（bp_mo.c）は「OR問題」を設定している．この問題においてシード値を変更して適当回数実行し，大抵の場合簡単に解けている事を確認せよ．

    コメント：初期重みを設定している乱数シード値を 10000,20000,...,50000 と変更し，実行し，重みが変わったとしても数100回程度の学習で誤差がほぼゼロになる事を確認する． 

    使い方：
  prompt> gcc bp_mo.c -lm
  prompt> ./a.out $random_seed

  2. Level 1.2: 「OR問題」を学習させた際の学習結果をグラフ化せよ．ただし，横軸は学習回数，縦軸は誤差とする．

    コメント：学習に成功（収束）した回数を Epoch（エポック）数と呼ぶ．学習結果をグラフ化する際にはエポック数を5とし，平均化したグラフを作成する事．shell/perl等のスクリプト言語/表計算ソフト/gnuplot等を利用すると楽になるでしょう．ソースファイルそのものを改変するのもOK．

Level 2: 線形分離不可　　(5+8=13点)

実験内容

bp_mo.c をコピーして bp_mo_exor.c を作成し，Level 2.1, 2.2 を実施せよ．

  1. Level 2.1: bp_mo_exor.c を編集して「ExOR問題」へ変更し，シード値を変更して複数回実行せよ．OR問題と異なり，学習が適切に収束しない事を確認し，何故 ExOR 問題が OR より困難なのかを説明せよ．
  2. Level 2.2: 「ExOR問題」をうまく学習する為に，以下に示す各パラメータを変更して実験せよ．最も効率良く学習が収束する組み合わせを検討せよ．

    パラメータ変更目安
    学習係数 ETA0以上〜2.0未満
    慣性項 ALPHA0以上〜1.0未満
    中間層のユニット数 HIDDEN1以上

    注記：1つの組み合わせで収束するかどうかを確認する為に，エポック数はシード値を変更して実行した結果5回中3回以上（エポック数3以上）となること．これは，たまたま初期重みが適切な値に設定されたことにより学習が収束したのでは無い事を確認する為である．

  3. （オプション）どうやれば効率良く最適な組み合わせを探すことができるか？可能な限り人の手間を省いて自動化する方法を検討し，実験せよ．

3. 応用事例（文字認識）

Level 3: 文字認識サンプル　　(5+10+10+6+7=38点)

実験内容

ソースのあるディレクトリ（~/info2/teacher/tnal/nn/nn_num/）に移動し，Level 3.1 〜 3.5 まで（全て必須）を実施せよ． 

動かし方は 0README_ja.txt を参照．
  1. Level3.1: サンプルソースを動かし，0〜9の文字を認識するように重みを学習させよ．本プログラムでは，学習用には learn0.txt ... learn9.txt を用いているが，類似した文字 eva1-1.txt, eva1-2.txt を適切に1として認識するか，確認せよ．

    コメント：eva1-1.txt, eva1-2.txt で確認する前に，0〜9を認識出来るように学習を収束させる必要があります．そのためには，中間層（デフォルトでは1）を増やした上で，数千〜数万回程度学習させてみてください．

  2. Level3.2: Level 3.1 において，2.2 と同様にパラメータを調整し，学習後の誤差が最も早く収束する（＝学習に向いているパラメータの）組み合わせを検討せよ．なお，エポック数5以上での平均回数での収束度合いを求める事．

    コメント：エポック数5以上での収束度合いが最速のグループには，ボーナスポイントとして優(加点+12)を与えます！

  3. Level3.3: Level 3.2 で得られたパラメータによる学習曲線を出力し，パラメータと収束能力の関連性について考察せよ．
  4. Level3.4: 各自で任意の評価用データを複数作成し，学習時のデータとの違いが少ないほど認識率が高い事を示せ．
  5. Level3.5: 下図のように入力されたデータが想定していた入力と比べてサイズが異なったり，位置がずれている等，文字の一部が欠けている以外にも様々なデータ（情報）の欠落が考えられる．認識率を高めるにはどのような点を工夫すれば良いか？どのような方法でも構わないので，検討せよ．

4. 検討課題

Level 4: NNの応用例を検討　　(4+6=10点)

手書き文字認識の様に，（通常の）コンピュータの持つ特徴と異なり，曖昧な処理（認識・予測・類推・連想・分析・解析・・・）が得意である一方，厳密な処理は苦手である．

このような特徴を踏まえた上で，NNが何に応用できるか検討せよ．レポートには以下を含めること．

  • Level 4.1: 問題の解説．
  • Level 4.2: 入力層・出力層の構成案（ニューロン数，データの入れ方，出力方法）．
  • 参考文献があれば，それらの文献情報．

補足: 応用例1つにつき 4+6=10 点です．2つ目以降に関しては加点対象です．



5. オプション課題例

Level X: オプション課題例
  • Level3関連
    • Level 3.5 にて検討した事項の実装．
    • 「文字認識サンプル」を画像ファイルの読み込みに対応させる（簡易バージョンでも良いし，画像ファイル or 疑似画像ファイルを読「サンプルプログラムの読み込みフォーマット」に変換するプログラムの作成でも良い．）．
    • 「文字認識サンプル」におけるパラメータのチューニングを効率良く行うための工夫．
    • 「文字認識サンプル」を利用した他のアプリケーションへの適用（利用しにくい場合にはゼロから書き直しても ok）．
  • Level 4 にて検討した応用事例への適用．


6. 補足

Level X: 補足

実験の内容・進め方に関するコメント等

  1. 今後の為に参考にしたいので，情報工学実験2・探索アルゴリズム1〜2で扱った内容，実験の進め方等について意見があれば書いてください（当然，どのような意見であってもレポートの評価を下げる事はしません．）．「授業評価アンケート」の際に書いてもらっても構いません．参考までに，今回の実験では以下の点を考慮した内容のつもりで実施しました．
    • 扱った内容：探索アルゴリズムの考え方，NN．
    • 中心課題：

      （1）計算機実験を実施するにあたっての考え方，特に，実験計画・実験・結果収集・結果解析・レポート作成までの一連の作業をするにあたって考慮すべき点の発見と，対処方法の検討．

      （2）(1)の実験を効率良く実施する為に検討すべき項目の調査と，それを解決する手段に関する検討．

      （3）パラメータ・チューニングの必要性やそれらを効率的に実現する為の前処理・後処理のためのテキスト処理や自動化に関する考え方，

      （4）（主題ではないですが）サンプル・ソフトウェアの利用を通した，システム設計面における外部設計指針，マニュアル整備等の必要性確認．

    • 進め方

      （1）「解説→グループ討論/実施→全体討論」という形式を取り，他の人/グループが同じテーマを与えられた時にどのような事を考え，アイデアを整理し，どのように発表するのかについて，学生全員が実験時間中に把握出来るように心がけた．

      （2）「共同作業（グループ制）」とする事で，個人レベルでの理解度の底上げに努めた．これは，解説の段階で理解度の早い学生は他の人へ教示する事でそのスキルとより理解度が深まる上に，理解度が不十分であった学生は同環境にいる学生の視点からの教示により理解しやすくなる事を期待して実施した．

      （3）(2)の間接的な効果として，自分の意見を第三者へ伝えるコミュニケーション能力・レポート作成技術の向上が挙げられます．

  2. 今後，実施を検討している以下の項目に関する，賛成/反対等の意見．

    （1）レポートの開示．取りあえず，今回の分については採点後，評価の高いレポートについて了承を得てから開示の有無を決定するつもりです．

    （2）最急降下法，NN，(GA)以外のアルゴリズムを用いた実験（「アルゴリズムとデータ構造」等，他の講義で出てくるアルゴリズムを利用した実験等）．

  3. やって欲しかった内容，その他に関する意見．



7. Tips

gnuplot を用いた作図方法

  1. Excel等の表計算ソフトでデータを収集・解析した結果をグラフ化する．

    gnuplot 等 EPS 形式で出力出来る図作成ソフトを利用する． gnuplot の場合なら，それが読み込める形式（text）に保存し，以下の手順にて図を作成し，LaTeX に取り込む．

  2. LaTex に gnuplot の図を取り込む．
    1. グラフ化するデータを準備する．
    2. gnuplot でグラフ化する．以下は result.dat 内のデータを線グラフ化する例．ここでは LaTeX 用に eps 形式で作成しています． 
      gnuplot> set terminal postscript eps
gnuplot> set output "result.eps"
gnuplot> set title "figure title..."
gnuplot> set xlabel "x title..."
gnuplot> set ylabel "y title..."
gnuplot> plot "result.dat" with line
    3. LaTeX に取り込む． 
      \documentclass[a4paper,10pt]{jarticle}
\usepackage{graphicx}

\begin{document}
\begin{figure}
 \begin{center}
  \includegraphics[scale=0.5]{result.eps}
  \caption{図のテスト}
 \end{center}
\end{figure}

\end{document}



    参考文献・サイト