レポート課題

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


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

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

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

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

原則として、 締め切りは出題日(講義日)から一か月とする。 厳密にいえば、翌月の講義日と同じ日の前日の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回講義:15点:課題番号05) 大学の講義に家から通う問題を考える。 この問題を解決するには次のような知識を利用する。

    1. この問題を解くのに必要な事実のTMS型(あるいはATMS型)のデータベースを作成せよ。 上のほかにも面白いデータを加えてより現実味のあるデータベースにするとポイントが高い。
    2. 問題がどのように解決されるのかを示せ。また、利用する事実( 例えば、季節や台風、雨降り状況など)が変わると解がどのように変化するかを 示せ。

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


    1. S
      M
      E
      O
      N
      R
      D
      E
      M O
      N
      E
      Y

    2.   
        
       
       

    3. 以下の条件を満たすような10桁の数字abcdefghijを求めよ。ここで各アルファベットは異なる数字であり、 先頭に0はあり得ない。
      • aは1で割り切れる
      • abは2で割り切れる
      • abcは3で割り切れる
      • abcdは4で割り切れる
      • abcdeは5で割り切れる
      • abcdefは6で割り切れる
      • abcdefgは7で割り切れる
      • abcdefghは8で割り切れる
      • abcdefghiは9で割り切れる
      • abcdefghijは10で割り切れる

    これらの問題を1つ以上選び、人間が解く過程を非単調推論として説明せよ。 図などを用いて平易に解説すること。できればプログラムを作成すること。その 実行結果を示すとポイントが高い。

    単なるバックトラックのプログラムを求めているのではない。 人間が解くようにNogoodや制約を順次作成することが大切である。

    Hint1: たとえば最初の問題に関しては はじめ次のように考えるだろう。

    Hint2: 講義で説明した4色問題 の地図を塗り分けるTSMのデモが ここ にある。その詳細説明は ここ にある。このプログラムを理解して参考にしてもよい。

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

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

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

    三段論法推論のデモプログラムが以下にある。 これを利用してもよいが、 内容をよく理解してレポートを作成すること。 少なくともプログラムの動作・アルゴリズムなどの説明は 詳しくすること。また、バグや拡張すべき点があるかもしれないので、 各自改良して使用してほしい。 とくに、モデルの拡張をしたり、GUIやその他便利な機能を追加するとポイントが高い。

    さらに、参考書の『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によるサンプルコードが ここ にある。

    また、また別の 数独(shidoku)の代数的探索プログラム は、 数式処理システム sage notebookから動作する。 実行のイメージは ここにある。

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

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

    もしもとくに思いつかなければ、 強化学習用の練習問題セット Open AI gym の中の問題を利用するとよい。

    講義で説明したQ学習のデモ・MazeExplorerはここにある。

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

  12. (第4回講義:20点:課題番号12) 畳パズル を解いてみよう。これは 様々な形の部屋を2x1の畳で敷き詰める問題である。 畳は重なってはならず、全ての部屋の床が畳で覆われなくてはならない。

    以下のような問題を解くこと。

    1. 6x5の大きさの部屋を畳15枚で覆う。ただし4枚の畳が角で接してはならない。

    2. 6x5の大きさの部屋を畳15枚で覆う。ただし部屋を横断する直線(畳の縁の線)が一本もないようにする。4枚の畳が角で接しても構わない。

      ダメな例:

    3. 6x5の大きさの部屋から互いに反対端の隅を切り落とした部屋を畳14枚で覆う。 この場合、横断する直線や4枚の畳が接する角ができても構わない。

    4. 6x6の大きさの部屋から2か所をランダムに取り除いた場所を、 畳17枚で覆う。ただし解けない場合もあることに注意せよ(なぜか?、どういうときに解けるか?)。

    A*,深さ優先,広さ優先探索をそれぞれ実行して探索の効率(解に到達するまでのノー ドの展開数)を比較すること。 適当なヒューリスティックスを考案して、A*探索を工夫すること。

    講義で説明した以下のプログラムを拡張するとよい。 オリジナルな実装でないものは採点しない。

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

    講義で説明した以下のプログラムを拡張するとよい。 オリジナルな実装でないものは採点しない。

    もしも良いパズルの例が思い浮かばないなら、 2048を解いてみよう。 2048のAIについての比較は この論文 に説明されている。 自分でA*用の(効果的な)ヒューリスティックスを考えて実験してみよう。

    Hint: 教科書「ゲームAI と深層学習―ニューロ進化と人間性―(伊庭斉志, オーム社)」 を提供するので、参考にしてほしい。 ゲームやパズルのサンプルソースも提供されている。 詳細は ここ を見てほしい。 このなかのどれかを拡張してもよい。

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

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

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

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

    Hint: 教科書「ゲームAI と深層学習―ニューロ進化と人間性―(伊庭斉志, オーム社)」 の4.4節にマリオのA*探索の解説がなされている。またサンプルソースについても 説明されている。 詳細は ここ を見てほしい。

  15. (第5回講義:15点:課題番号15) じゃんけんのゲームを行う サイト がある。 ほとんどの人は20回を超えると勝つことができない。 このAIは単にランダムに手を出しているのではない。

       

    まずは何回かこのジャンケンAIと対戦してみよう。

    このジャンケンAIを作るのにどのような戦略を使えるのかを 解説せよ。 ただし「ナッシュ均衡解」という用語を必ず使用して説明すること。

    Hint1: 人間はジャンケンをするときに ある行動パターンに従うことを発見した論文が ここ にある。

    Hint2: このジャンケンAIは 20万回以上のジャンケンで得られた知識に基づいているらしい。 そのデータを集めるサイトは ここ にある(Prof. Shawn Bayernによる)。これを基にしたジャンケンAIの サンプルプログラムは ここ にある。

  16. (第5回講義:15点:課題番号16)講義で説明したチャンプというゲームについて、先手が勝つ方法は1通りであると信じられていた。 ところが、「勝ちにつながる最初の手は1通りしかない」という予測は裏切られた。 この予測の反例を探してみよう。

           

    Hint1: できるだけ効率的に探すこと。さもないと計算が終わらない。

    Hint2: 反例の1つは8x10のものである。これ以外にみつかるだろうか?

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

    もし何も良い例が思いつかなければ、 ゲームに関しての以下のようなサイトを参考にして もよい。

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

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

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

    もし何も良い例が思いつかなければ、 ゲームに関しての以下のようなサイトを参考にして もよい。

  19. (第6回講義:10点:課題番号19) 進化計算の原理を身近な例を用いて分かりやすく説明せよ。少なくとも以 下の項目についてアナロジーで解説すること。
    • 交叉
    • 突然変異
    • 世代交代
    • 集団初期化
    • 選択・淘汰
    • 適合度計算
    • 探索が上手くいくようす
    図と例証を用いて示すと良い。 講義では、飛行機、鉄道、動物などの例を用いた。 オリジナルでないものは採点しない。

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

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

       

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

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

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

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

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

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

    たとえば以下のような問題を扱うとよい。

    1. 自動車の構造設計の最適化問題を解く。

      これは 応答曲面法を用いた複数車種の同時最適化ベンチマーク問題 (2017年4月にマツダ(株),宇宙航空研究開発機構,東京理科大学 から公開されたコンペティション課題)である。

      このページ にある「単目的最適化部門」の解法を行いなさい。 データや最適化の詳細はホームページに説明されている。

         

    2. A*マリオのGA版

      参考書の5.3節に進化するマリオの説明がある。またサンプルとなるコードは ここにある。

      より強力なマリオを進化させること。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Hint: 上のデータセットでそのまま実験すれば84%程度の正答率(テストデータ)となる。 特徴の選択をうまくすると成績が向上するはずである。 できるだけ正答率のUPを行うための工夫(特徴選択など)をしてみよう。


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

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


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