イラストで学ぶ人工知能概論を再度勉強する 第５章 動的計画法
はじめに
とある理由で
「二重文節構造」のアイデアに触れた時から大ファンになった
谷口忠大先生の名著「イラストで学ぶ人工知能概論」を
じっくり勉強しなおしたくなって
改訂第2版を購入しなおした。
本noteは、その備忘録
ホイールダック2号、宝箱がある迷路で評価関数が最も高くなる経路でゴールに向かう
第５章 動的計画法
講義スライドと谷口忠大先生本人の講義動画が
谷口忠大先生から提供されています
5.1 多段決定問題
時刻ごとにとる行動を、利得の輪を最大化するように選択する
5.2 動的計画法
経路の評価関数を最大化する問題に定式化できる
通常計算量は莫大になるが、
特に、評価関数が隣のステップの情報のみで決まる場合は、
計算量を現実的な量まで減らすことができる
5.3 ホイールダック2号「宝箱を拾ってゴール」
3マスの迷路で5ステップの行動を最適化してみる
5.4 例：編集距離の計算
動的計画法を使って編集距離を計算する
もとの文字列を縦、編集後の文字列を横に並べた
表を作成してみる
本章の最重要ポイント
動的計画法は、問題をうまく定式化することで
・自然言語処理
・音声認識
・動作認識
・システム制御
・遺伝子解析
など、幅広い分野に活用できる
おわりに
動的計画法の威力を認識できた
いいなと思ったら応援しよう！
