レポート課題

締め切り 原則として出題日(講義日)から一か月とする


講義の内容により変更の可能性がある。 最終的な内容は必ず講義の際に確認すること。

提出する課題数は任意である。

提出した場合は、その内容によってポイントを獲得する。 ただしそれぞれの問題の満点以上のポイントを得ることはない。 また同じ回の課題を複数答えることはできない。

問題は講義と同時進行で出題されるので、随時増えていく予定である。

原則として、 締め切りは出題日(講義日)から一か月とする。 厳密にいえば、翌月の講義日と同じ日の前日の23:59まで。 例えば、講義日が11月13日の場合には、 12月12日の23:59までである。

原則として、締切日より遅れて提出された場合は 採点の対象としない。 ただし、何らかの理由があれば、 締め切りまでに提出したレポートについて更新・修正版をのちに 提出することは認めることがある。 また、特段の理由(わたしはAIを作ります!!、 など)があれば提出期限を延長する。

レポート採点方針について:


  1. (第1回講義:15点:課題番号01)以下の本の1つ以上を読んで、人工知能の実現可能性に ついて考察せよ。A4で3〜5ページ程度とする。少なすぎる もの・内容がないものは採点しない。 レポートには以下の項目に関して記述すること。

  2. (第1回講義:10点:課題番号02)つぎの各文をもとにしてAIについて論ぜよ。どれか1つを詳しく論 じてもよいし、2つまたはそれ以上について論じてもよい。A4で3〜5ページ 程度とする。少なすぎるもの・内容がないものは採点しない。 なお、単なる感想文ではないので、必要なら参考文献などを付けるとポイントが高い。

  3. (第1回講義:15点:課題番号03) 以下のようなコンテンツをもとにして チューリング・テストの有効性や「強いAI」の実現可能性(すでにAIはできている?)などについて論ぜよ。 A4で3〜5ページ程度とする。少なすぎるもの・内容がないものは採点しない。 必要なら参考文献などを付けるとポイントが高い。

  4. (第1回講義:10点:課題番号04)フレーム問題は、 PL法(消費者保護法)に関して生じる注意書きのように 実世界の知識表現と密接に関連している。 例えば、 などがその例である。 たとえば、Michigan Lawsuit Abuse Watch(訴訟の乱用を監視するアメリカの団体) では、毎年「最も妙な注意書きコンテスト(WACKY WARNING LABEL CONTEST)」が開催されている。

    このようなフレーム問題の実世界での実例(フレーム問題が「問題」となる例)をいくつかあげ、 人工知能の実現との関連性について考察せよ。

    注意:PL法にまつわる馬鹿げた注意書き例を求めているのではない。 フレーム問題が実際に問題となるような実世界での実例をもとに議論すること。 A4で3〜5ページ 程度とする。少なすぎるもの・内容がないものは採点しない。

  5. (第2回講義:20点:課題番号05)TMSあるいはATMSを用いて,制約従属問題 を人間が解くように解決することができる。

    たとえば以下のような地図を4色で塗り分ける問題を考えよう。 これらの解法について説明せよ。

    1. この問題を解くのに必要な事実のTMS型(あるいはATMS型)のデータベースを作成せよ。
    2. 問題がどのように解決されるのかを示せ。

    図などを用いて平易に解説すること。できればプログラムを作成すること。 実行結果を示すとポイントが高い。 TMSやATMSの言葉で説明すること。

    これらの解法について、図などを用いて平易に解説すること。できればプログラムを作成すること。 実行結果を示すとポイントが高い。

    単なるバックトラックのプログラムを求めているのではない。 より複雑な例や任意の地図への解法を自分で考えるとなおよい。

    たとえば以下の地図はどうだろう???

    なお、この地図は4色問題の証明がなされていなかった1975年に、 マーチンガードナーがエイプリルフールのいたずらで「サイエンティフィック・アメリカン」に反例として出したものである。 その後この地図は大きな騒動となった。

    Hint: 上のカラーの地図を塗り分けるTSMのデモが ここ にある。その詳細説明は ここ にある。このプログラムを理解して参考にしてもよい。

  6. (第2回講義:25点:課題番号06)TMSあるいはATMSを用いて以下のような制約従属問題 (覆面算や虫食い算)を 解くことができる。

      EEO
      OO
     EOEO
    EOO 
    OOOOO

      PPP
      PP
     PPPP
    PPPP 
    PPPPP

    これらの解法について説明せよ。ここでE,O,Pはそれぞれ偶数、奇数、素数を表す。 ただし、左端に数字のゼロは登場しないことに注意せよ。 同じ英語文字が同じ数字とは限らない。。

    図などを用いて平易に解説すること。できればプログラムを作成すること。 実行結果を示すとポイントが高い。

    Hint: 前問の地図を塗り分けるTSMのデモ を 参考にしてもよい。 にある。その詳細説明は

  7. (第2回講義:20点:課題番号07) 三段論法推論のメンタルモデル による 解法について、具体例をあげてメンタルモデルの表現を構成して説明せよ。 とくに 教科書 の13ページにある表をもとにして、以下の点について考察すること。 講義で説明したのと異なる三段論法の例を使うこと。

    人手で実行結果を作成してもよいが、 自分でプログラムを作成するとなおよい。

    なおLISPによるプログラムが ここ にある。これを利用してもよいが、 内容をよく理解してレポートを作成すること。 少なくともプログラムの動作・アルゴリズムなどの説明は 詳しくすること。

    また参考書の『4.4節:三段論法推論:ソクラテスは死ぬか?』では三段論法のメンタルモデルの詳細が説明されている。

  8. (第3回講義:15点:課題番号08)下に示すのは典型的な幾何図形類推問題である。

    「図Aを変えて図Bにする規則をみつけ、それを図Cに適用せよ。 その結果できる図形を図1−5から選べ。」

    1. EvansのプログラムANALOGYがどのようにこのような問題を解くことができ たかを 説明せよ。次のような点を例をもとにして解説すること。 上以外の例を用いても良い。より面白い例の方が ポイントが高い。
      • 図A,B,C間の類似点と相違点とを記述するプログラムでは、これらの 各図を どのように記述しておけばよいだろうか?
      • 図Aを図Bに変える規則の記号的な記述を与え、この規則を上で与えた記 述から どのように機械的につくることができるかを説明せよ。
      • 自分の作った規則を図Cに対して自分の作った記述に適用せよ。 その結果どのような記述が得られ、それはどのような図であるかを説明せよ。 この図と図Cとの間の類似点を記述せよ。
      • 図Cの記述方法を変えて、同じ規則をその記述に適用すると、前とは違っ た結果 になるようにせよ。
    2. EvansのプログラムANALOGYでは解くことができないであろう幾何図形類推 問題の例を示し、 なぜ解けないのかを説明せよ。
    3. EvansのプログラムANALOGYとIQテストに用いられるような幾何図形類推 問題に関する以下の命題について、上で示した例 などを利用して論ぜよ。
      • 幾何学的図形類推問題を解く知的行為の基 本的な要素は、純粋に機械的なものであることを示した。
      • 幾何学的図形類推問題を解くのに必要な知的な能力は、もとになる記号的 記述体系をどのように選ぶかというところにのみ存在する。
    4. また余裕があれば以下のようなMENSA(IQの上位2%の人達が参加する国際グループ)問題がどのように解かれるか、あるいは解けないのかを考察せよ。

    なお、EvansのプログラムANALOGYの詳細 は 参考書 の 2.2節を参照するとよい。

  9. (第3回講義:25点:課題番号09)Wuの定理に基づく幾何の定理証明の プログラムを作成せよ。 自分で多項式の割り算を実現してもいいが, 大学内で使用可能な数式処理システム(Mathematicaなど)を利用しても構わ ない。 例えばWolfram Cloudを利用するとよい。 長谷川先生のホームページ 「計算論のサイト」 が参考になる。 入力は制約条件の式と証明すべき式とする(記号からの変換は実装不要)。 を実装すること。 いくつかのおもしろい幾何定理の証明例を示せ。

    とくに思いつかなければ、 中線問題(参考書の51ページ) を解いてみよう。

  10. (第3回講義:25点:課題番号10)Groebner 基底のプログラムを利用して、定理証明の実験を行え。

    大学内で使用可能な数式処理システム(Mathematicaなど)を利用しても構わ ない。 例えばWolfram Cloudを利用するとよい。 長谷川先生のホームページ 「計算論のサイト」 が参考になる。

    いくつかのおもしろい幾何定理の証明例を示すか、または Groebner 基底による数独の解法 を行う実験を行ってみよう。 Mapleによるサンプルコードが ここ にある。

  11. (第3回講義:20点:課題番号11)強化学習 を用いたAI学習の例を作成せよ。

    必ずしも完全に成功しなくてもよいが、面白いタスクであることが望まれる。 タスクの面白さやオリジナルさも評価の基準となる。

    なおこの課題を含めて、他の講義で作成したようなレポートを再提出することは 認めない。 大幅に改変している場合は、自ら申告するように。

  12. (第4回講義:20点:課題番号12)面白いパズルの探索プログラムを実装せよ。A*,深 さ優先,広さ優先探索をそれぞれ実行して探索の効率(解に到達するまでのノー ドの展開数)を比較すること。 講義で説明した以下のプログラムを拡張するとよい。 オリジナルな実装でないものは採点しない。

    もしも良いパズルの例が思い浮かばないなら、 ペグソリテイアを解いてみよう。以下の問題に挑戦せよ。

  13. (第4回講義:25点:課題番号13)講義で説明したMarioゲームの 探索を実行せよ。

    Mario AI Competitionの情報は ここにある。 A*マリオについての説明は、 ここ ここにある。 また、A*マリオのソースコードは ここから入手できる。

    A*探索のヒューリスティックスをさまざまに工夫すること。

    A*探索の他に,深さ優先,広さ優先探索やその他の(ヒューリスティックな,人間の) 探索を実装して,成績を比較するとなおいい。 講義で説明した以下のプログラムを拡張するとよい。 オリジナルな実装でないものは採点しない。 講義で説明した以下のプログラムを拡張するとよい。

  14. (第4回講義:20点:課題番号14)

    8×8のチェス盤に互いに攻撃しないようにできるだけ多くの駒を配置することを考えよう。

    たとえば、以下はできるだけ多くのルークを互いに攻撃しないように配置するやや自明な例である。

    以下のそれぞれの条件でできるだけ多く駒を多く配置せよ。

    対称性や鏡像を考えて、ことなる配置をすべて求めるとポイントが高い。

  15. (第5回講義:15点:課題番号15)制約充足問題である線画の解釈の実験をせよ。自分でプログラムを作製してもよいし、あるいは以下のサンプルプログラムを利用してもよい。 最低でも コマンドラインで簡単に入力するように工夫すればよい。

    具体的な実装例や仕様の詳細については、例えば、 平賀先生のページ を参照するとよい。 なおこのページは平賀先生のご厚意で利用可能となっている。 著作権には十分留意すること。

    講義で説明したサンプルプログラムは ここ にある。 この プログラムはJavascript で実装されており、 適当なWebブラウザでai.html を開くと実行できる。 使用方法と実験例はここにある。

    以下の実験・拡張などを行うこと。

  16. (第5回講義:25点:課題番号16)面白いゲームの探索プログラムを実装せよ。 講義で説明した以下のプログラムを拡張するとよい。 以下のような項目について探索の効率(展開されたノード数)の比較を 行うとポイントが高い。 オリジナルな実装でないものは採点しない。

    もし何も良い例が思いつかなければ、以下のミニチェス、ミニチェッカーの探索を行ってみよう。 ミニチェッカーでは双方が最善を尽くすと引き分けに終わることが分かっている。 ミニチェスでは先手・後手のどちらが有利だろうか?

  17. (第5回講義:25点:課題番号17) ゲームのモンテカルロ木(UCT)探索を用いた面白いゲームの探索プログラムを実装せ よ。

    探索の効率(展開されたノード数、実行時間など)を従来手法(min-max,α/βカット を用いた場合) と比較するとなおよい。

    講義で説明した以下のプログラムを拡張してもよい。 いずれのプログラムもmakeコマンドでコンパイルできるはず(warningは無視してよい)。

  18. (第6回講義:10点:課題番号18) 進化計算の原理を身近な例を用いて分かりやすく説明せよ。少なくとも以 下の項目についてアナロジーで解説すること。 図と例証を用いて示すと良い。 講義では、飛行機、鉄道、動物などの例を用いた。 オリジナルでないものは採点しない。

  19. (第6回講義:20点:課題番号19) GAの探索問題として、適当な例題を考えよ。 もし何もアイディアがないなら、講義で説明した、 などでよい。

    このとき、その問題に関して次の3つの異なったGAの性能を比較しなさい。

    これら3つのGAについて、得られた解の品質と解を見つけるまでにかかった時間について 比較せよ。

    Hint1: ナップザック問題の定義、計算量、ヒューリスティックの解説は ここにある。また、 解くべき例題については、 ここにあるベンチマークなどを利用するとよい。

    Hint2: ボールドウィン進化とラマルク進化の詳細は 参考書 の5.1節にある。

  20. (第6回講義:30点:課題番号20) GAまたはGPの応用例を各自作成し、その実行結果を観察せよ。 応用例としてはできるだけ独自で考えた(独創的で面白い)ものが望まれる。    を様々に変化させ、実験結果を比較・考察すること。

    パラメータ(GA,GPでは集団数、世 代数、交叉率、突然変異率など)や問題の難しさ(サイズ、質の違い)が探索 の効率にどのように影響するのかを観察すること。

    GAのCプログラムとしては、 このファイルを参考にするといい (他のプログラム言語や自分で作成したものでももちろん可)。

    たとえば以下のようなのもがある。

    もしも何も思いつかなくてチャレンジャーなら、 パックマンの戦略 をGAやGPで進化させてみよう。 パックマンのゲームプログラムやAI competitionについては、 Ms. Pac-Man Vs. Ghost Team Competition 2016 を参考にするといい。 Javaのソースプログラムが入手できる。 他のプログラム言語や自分で作成したものでよい。

    GA/GPによるパックマンの論文や情報はWWW上に多くあるので参考にすること。たとえば、

    は、比較的理解しやすい。

    進化の前進化の後 (luring strategy)

    なお、必ずしもベストな戦略が得られなくても成績評価には関係しない。 GA/GPを試し、人間などの他の手法と 成績を比較することが重要である。 もちろん良い成績であればベストであるが。。。

  21. (第7回講義:10点:課題番号21) 進化計算の面白い応用例・実用例について調べて考察せよ。

    講義などで説明した例や以下のような著名な例は除く

    なおこの課題で求めているのはわかりやすいデモや応用であり、 技術的詳細ではない。

    実応用例については、 特許・新聞記事・論文などの出典とともに、どのように応用されているかをわかりやすく平易な言葉で説明すること。

  22. (第7回講義:15点:課題番号22) 文字認識による数独の解法のプログラムが ここにある。 このプログラムを改良・拡張してみよ。    次の課題とは重複して提出できない。

  23. (第7回講義:20点:課題番号23) ニューラルネットワークまたはボルツマンマシンの 応用例を各自作成し、その実行結果を観察せよ。 応用例としてはできるだ け独自で考えた(独創的で面白い)ものが望まれる。    を様々に変化させ、実験結果を比較・考察すること。 講義で説明した以下のプログラムを拡張するとよい。 オリジナルでないもの、すでにいずれかの課題で提出されたものなどは 採点しない。

    とくに思いつかなければ、 speed-datingの予測問題 を解いてみよう。4分間の交流をもとに、交流した人間ともう1度 デートしたいかを予測する問題である。 加工したデータ( 欠損データや不要データの削除などの処理) は以下にある。

    実験の回ごとにアンケートへの回答の仕方が異なっていたため正規化などを している。なお、 このデータ加工が正しいとは限らないので、適宜可能なら自分で加工してほしい。

    評価にはランダムに選んだ70%の訓練データに対してNNを学習させ、 残りをテストデータとして成績を求めよ。 このパーセンテージは適当に変更してもよい。

  24. (第8回講義:20点:課題番号24) Deep learningの人気のあるフレームワークとして、C++で実装されたCaffeがある。 グーグルのYangqing Jiaらにより開発されたものである。

    一般に、Deep Learningでは学習に多大な労力(時間、データ数)が必要となる。 そのため適切なネットワーク定義を一から作るのはかなりの苦労を伴う。

    ところが、CaffeではCaffe Model Zooという学習済みのモデルを配布する枠組がある。

    目的にあったものがあれば、このモデルを使用したり、fine tuningするのが良いかもしれない。 そのため、この枠組は非常によく利用されている。

    そこでレポートでは、Caffeを使ったモデルでの画像分類を実行してみよう。 自分で最初から作る必要はなく、Model Zooから適当な学習済みモデルをダウンロードして使用してよい。

    ただし実験では自前のデータや特徴抽出を行って、成績を比較・吟味せよ。

    Caffeの使用法、自分なりに設定したパラメータ、データの特性などについて 説明すること。

  25. (第8回講義:15点:課題番号25) 以下の本の1つ以上を読んで、人工生命・人工知能の実現可能性に ついて考察せよ。A4で3〜5ページ程度とする。少なすぎるものは採点しない。

    レポートには以下の項目に関して記述すること。

  26. (第8回講義:25点:課題番号26)ACO(アントコロニー・アルゴリズム)を応用し、ジョブショップ・スケジューリング問題(JSSP)を解くプログラムを作成せよ。    を様々に変化させ、実験結果を比較・考察すること。

    講義で説明したJSSPのスライドの一部は ここにある。

    遺伝的アルゴリズム(Genetic Algorithms, GA)によるシミュ レータとそのソースファイルなどを以下からダウンロードできる。

    解くべき例題については、上のGAシミュレータにある MT6x6, MT20x5, MT10x10の例題を利用してみよ。 なおMT10x10は極めて困難な問題であることが分かっている。

    また、よりチャレンジャーなら、 abz7, abz8, abz9, la21, la24, la25, la27, la29, la38, la40 と呼ばれる10 tough problemsのいくつかを解いてみよう。

    以下の論文などが参考になる。

  27. (第9回講義:25点:課題番号27) ABCアルゴリズムを応用し、JSSP問題を解くプログラムを作成せよ。 パラメータをさまざに変えて性能の差異を観察すること. とくに働 きバチ、傍観バチ、斥候バチがどう働くか、あるいはサボるか. GUIを作るとポイントが高い。

    JSSPの詳細や解くべき問題例は問題26を参考にせよ。

    以下の論文などが参考になる。

  28. (第9回講義:15点:課題番号28) メタヒューリスティクスには、新しい手法が 数多く提案されている。たとえば以下のようなものがある。

    これらのどれか少なくとも2つを選んで、そのアルゴリズム、実験例、実用性などについて説明せよ。

    なお、講義で詳しく説明した、 ABC,ACO,PSO,GA,SA,NNなどのメタヒューリスティクスはのぞく。

    また、メタヒューリスティクスに対しての批判的な(?)論文として、 これ を挙げておくので参考にしてもよい。

  29. (第6回講義:15点:課題番号29) GAの理論の1つとして 2レバー・スロットマシンというのがある。 これは以下のようなものである。2本のレバーがあるスロットマシンに使うた めにN枚のコインが与えられたとしよう。それぞれのレバーA1,A2を一回引くこ とにそれぞれ平均 m1,m2、標準偏差σ1,σ2で賞金が得られる。2本のレバーから出てくる賞金は 毎回独立で定常(時間により不変)とする。あなたはm1,m2,σ1, σ2の値は知らない。目標はN回の試行で得られる賞金総額を最大化することで ある。

    このとき各レバーへの試行配分(残りのコインの賭け方)はどのようにすれば いいだろうか?

    このような問題(MAB:Multi-armed bandit problem)への最適な戦略の1つとして、ゲームAIで用いられるUCB値に基づくアルゴリズム が知られている。

    つまり、どのようなアルゴリズムもある条件下では以下のようなUCB値に基づくものを 超えられないとされている。

    ただしnはレバーを引く総数、n_iはi番目のレバーを引く回数、Q_n(i)はi番目のレバー のこれまでの総賞金額である。

    最適性を与える証明については この論文を参照すること。 また、UCB値を使った実験例の詳細は この参考書 の5.3節に解説されている。

    本レポートでは、UCB値の最適性について、その証明や理論展開をある程度数学的に(自分なりに)理解してわかりやすく説明せよ.

    とくに、最適解となる条件について考察すること。 実際に応用する場合にはどのような限界があるか、など。


以下のものを提出すること。

レポートは電子的な媒体でのみ受け付ける。原則として 紙レポートは受け付けない。 提出方法は ここに示す通りである。


伊庭研のホームページに戻る