らんだむな記憶

blogというものを体験してみようか！的なー

トップ > logic > ga136(推論・知識処理・自然言語処理)まとめ (1)

ga136(推論・知識処理・自然言語処理)まとめ (1)

logic MOOC

gacco: ga136 推論・知識処理・自然言語処理 - らんだむな記憶の適当なまとめ。

Week1

  • 人工知能 = アルゴリズムが書けない分野
  • 人工知能
    • 科学だと思う立場
      • 人間の知能とは何か？知能と同じ機能をプログラムとして実現
    • 工学だと思う立場
      • 作ったプログラムを知的なソフトウェアとして活用
  • 本
  • 「人工知能」は 1956 年のダートマス会議で使用
  • AI ブーム
    • 第 1 次: 〜 1970 年代の前半: 探索, 推論
    • 第 2 次: 1980 年代: 知識工学, ロジック。説明できるということが前提。
    • 第 3 次: 現在: 機械学習, 深層学習, エージェント, ロボティクス。最大の課題=説明責任
  • Turing Test
  • 知識
    • 暗黙知, e.g. 自転車の乗り方
    • 形式知
      • 構成的な知識: 手続き型 (how), e.g. 逆行列の計算の仕方
      • 構成的でない知識: 宣言的 (what), e.g. 逆行列の性質
  • コンピュータはミサイルを正確に飛ばすために生まれた
  • 記号
    • 第一のレイヤー: 記号が表す概念
    • 第二のレイヤー: 記号自身; “動詞は名詞でない” vs “「動詞」は名詞である”
    • 第三のレイヤー: 記号を構成する要素。atom = a- (not) + termnein (to cut) → atomos → atome → atom
  • 国語辞典 = 単語のネットワーク
  • 世の中のモデル化と解釈
  • Brooks: もう少し人間は考えないで行動している ⇒ ルンバ
  • 宣言的知識は平叙文で書ける ⇒ 一階述語論理: $\forall X (\text{human}(X) \Rightarrow \text{mortal}(X))$
  • Prolog = PROgramming in LOGic; 1970年前後から自然言語の構文解析あたりを行うためにできてきた言語。デファクトスタンダードであるものは「SWI-Prolog」
  • ド・モルガンの法則: 「野菜は食べません」: $\lnot \exists X (\text{veg}(X) \land \text{eat}(X)) = \forall X (\lnot \text{veg}(X) \lor \lnot \text{eat}(X))$
  • 探索における制約 (constraint)
  • 多項式時間で解けるアルゴリズムがない → 試行錯誤。しらみ潰し(最後の手段)。
  • 8 パズル。宣教師と人喰いの問題。覆面算。Eight-Queens Problem。Pentomino。巡回セールスマン問題。
  • 探索問題
    • 共通点
      • 問題空間(状態空間) = 状態の集合 + 操作の集合
    • 相違点
      • 手順発見型 vs 制約充足型
      • 許容解の探索 vs 最適解の探索
  • 少し考えたらプログラムで探索しなくても瞬時にわかる問題もある
  • 立方体切断問題。ハノイの塔
  • 前向き推論と後ろ向き推論。両側から探すというアプローチも大事。
  • しらみ潰し(最後の手段)の前に色々考える。
  • 探索
    • 深さ優先探索 or 縦型探索 or depth-first search (DFS)
    • 幅優先探索 or 横型探索 or breadth-first search
    • オススメ: 反復深化 or iterative deepening (1980 年代)。「最適」なしらみ潰し探索。一見効率が悪そうに見える。
  • ヒューリスティクス探索
  • 最良優先探索 (best-first search)
    • 目標状態に一番近そうなものを優先的に展開する方法
  • A* 探索
    • ヒューリスティクスがあったときに最適解を効率よく見つける方法
    • 状態 $s_k$ の「良さ」の尺度 $f(s_k) = g(s_k) + h^\prime (s_k)$
    • 楽観的な見積もりでやれば良い
    • 教訓: 「何か将来の見積もりというのは楽観的でしておくと、本当にいいものを見逃すことがなくなる」
  • 制約充足 (Constraint satisfaction)
  • 制約の能動的な利用
    • １. 未知数のうちの一つを選び、その値を仮に決める (guess)
    • ２. 仮に決めた値を用いて、制約の伝播 (constraint propagation) を行い、他の未知数のとりうる範囲を限定する
      • ある未知数の取りうる値が一つもなくなったら １. に後戻り (バックトラック)
      • さもなければ残った未知数について １. から作業を行う
  • 自然言語処理
  • 制約の下での談話理解
    • 会話 1
      • What are they?
      • They are flying airplanes.
    • 会話 2
      • What are they doing?
      • They are flying airplanes.
  • 制約の下での文字認識
  • 賢い探索のための基本ツール
    • 制約プログラミングツール
    • SAT ソルバ
    • SMT ソルバ
  • 一階述語論理