人工知能概論 第9回 位置推定(2) 粒子フィルタ

Slides:



Advertisements
Similar presentations
『わかりやすいパターン認 識』 第 5 章 特徴の評価とベイズ誤り確率 5.4 ベイズ誤り確率と最近傍決定則 発表日: 5 月 23 日(金) 発表者:時田 陽一.
Advertisements

あみだくじ AMIDA-KUJI 井上 康博 Statistical analysis on Amida-kuji, Physica A 369(2006)
統計学 第3回 西山. 第2回のまとめ 確率分布=決まっている分布の 形 期待値とは平均計算 平均=合計 ÷ 個数から卒業! 平均=割合 × 値の合計 同じ平均値でも 同じ分散や標準偏差でも.
放射線の計算や測定における統計誤 差 「平均の誤差」とその応用( 1H) 2 項分布、ポアソン分布、ガウス分布 ( 1H ) 最小二乗法( 1H )
数理統計学  第9回 西山.
第1回 確率変数、確率分布 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
看護学部 中澤 港 統計学第5回 看護学部 中澤 港
コンピュータビジョン特論 第8回対象追跡 2006年11月22日 加藤丈和.
高度情報演習1A “テーマC” 実践 画像処理プログラミング 〜画像認識とCGによる画像生成〜 第四回 演習課題 画像中からの物体抽出処理(背景情報を手がかりとして) 芝浦工業大学 工学部 情報工学科 青木 義満 2006/05/15.
確率と統計 平成23年12月8日 (徐々に統計へ戻ります).
統計解析 第7回 第6章 離散確率分布.
確率・統計Ⅰ 第12回 統計学の基礎1 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
復習.
確率・統計Ⅰ 第11回 i.i.d.の和と大数の法則 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
統計学  第7回 西 山.
Pattern Recognition and Machine Learning 1.5 決定理論
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
統計解析 第9回 第9章 正規分布、第11章 理論分布.
「データ学習アルゴリズム」 第3章 複雑な学習モデル 3.1 関数近似モデル ….. … 3層パーセプトロン
心理統計学 II 第7回 (11/13) 授業の学習目標 相関係数のまとめと具体的な計算例の復習 相関係数の実習.
上坂吉則 尾関和彦 文一総合出版 宮崎大輔2003年6月28日(土)
放射線の計算や測定における統計誤差 「平均の誤差」とその応用(1H) 2項分布、ポアソン分布、ガウス分布(1H) 最小二乗法(1H)
確率・統計Ⅱ 第7回.
第2章補足Ⅱ 2項分布と正規分布についての補足
人工知能概論 第6章 確率とベイズ理論の基礎.
エージェントアプローチ 人工知能 21章 B4 片渕 聡.
「データ学習アルゴリズム」 第2章 学習と統計的推測 報告者 佐々木 稔 2003年5月21日 2.1 データと学習
データ構造と アルゴリズム 知能情報学部 新田直也.
応用統計学の内容 推測統計学(inferential statistics)   連続型の確率分布   標本分布   統計推定   統計的検定.
人工知能概論 第9回 位置推定(2) 粒子フィルタ
統計解析 第10回 12章 標本抽出、13章 標本分布.
統計学 11/08(木) 鈴木智也.
統計学  第6回 西山.
ベイズ基準によるHSMM音声合成の評価 ◎橋本佳,南角吉彦,徳田恵一 (名工大).
シミュレーション演習 G. 総合演習 (Mathematica演習) システム創成情報工学科
計測工学 復習.
スペクトル・時系列データの前処理方法 ~平滑化 (スムージング) と微分~
母集団と標本:基本概念 母集団パラメーターと標本統計量 標本比率の標本分布
第2日目第4時限の学習目標 平均値の差の検定について学ぶ。 (1)平均値の差の検定の具体例を知る。
第3回 確率変数の平均 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
独立成分分析 1.問題は何か:例:解法:全体の見通し 2007/10/17 名雪 勲.
7. 音声の認識:高度な音響モデル 7.1 実際の音響モデル 7.2 識別的学習 7.3 深層学習.
決定木とランダムフォレスト 和田 俊和.
確率・統計Ⅰ 第3回 確率変数の独立性 / 確率変数の平均 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
第9章 混合モデルとEM 修士2年 北川直樹.
混合ガウスモデルによる回帰分析および 逆解析 Gaussian Mixture Regression GMR
モデルの逆解析 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
人工知能概論 第2回 探索(1) 状態空間モデル,基本的な探索
独立成分分析 5 アルゴリズムの安定性と効率 2007/10/24   名雪 勲.
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
平成20年10月5日(月) 東京工科大学 コンピュータサイエンス学部 亀田弘之
様々な情報源(4章).
電機情報工学専門実験 6. 強化学習シミュレーション
情報処理Ⅱ 第2回:2003年10月14日(火).
ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年6月25日 3.1 関数近似モデル
第3章 線形回帰モデル 修士1年 山田 孝太郎.
「アルゴリズムとプログラム」 結果を統計的に正しく判断 三学期 第7回 袖高の生徒ってどうよ調査(3)
ベイズ最適化 Bayesian Optimization BO
シミュレーション論Ⅰ 第7回 シミュレーションの構築と実施.
統計学  第9回 西 山.
ベイズ基準による 隠れセミマルコフモデルに基づく音声合成
人工知能特論II 第8回 二宮 崇.
ポッツスピン型隠れ変数による画像領域分割
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年8月1日 3.2 競合学習
統計解析 第11回.
人工知能概論 第4回 探索(3) ゲームの理論.
Q q 情報セキュリティ 第7回:2005年5月27日(金) q q.
混合ガウスモデル Gaussian Mixture Model GMM
アルゴリズム ~すべてのプログラムの基礎~.
Presentation transcript:

人工知能概論 第9回 位置推定(2) 粒子フィルタ 立命館大学 情報理工学部 知能情報学科 谷口忠大

STORY 位置推定(2) ベイズフィルタを実装されたホイールダック2号は思った.「何だか,これ,面倒くさくないだろうか」.ベイズフィルタでは常に「自分があらゆる状態にいる確率」を考えなければならない.ところが,迷路は広いが,自分がいる場所は一箇所だし,自分がいる可能性のある場所も正直なところ限られている.ほとんどの場所で自分の存在確率はほぼ0だ. こんな,ムダな情報を持っているより,むしろ,「僕はここにいるかもしれない」という仮説をいくつか持っておいた方がいいのではないだろうか.

仮定 位置推定(2) ホイールダック2号は迷路の完全な地図を持っているものとする. ホイールダック2号は自分がどこにいればどんな観測が得られるか知っているものとする(ただし確率的に). ホイールダック2号はそれぞれの状態で自分がどんな行動をとれば,どの状態へ移動するのかを知っているものとする(ただし確率的に).

Contents 9.1 ベイズフィルタの問題点 9.2 モンテカルロ近似 9.3 粒子フィルタ 9.4 通路上のホイールダック2号の位置推定    (粒子フィルタ編)

ベイズフィルタの復習 状態stで観測otを得る確率 状態stに移動している確率 あらゆる状態を考慮(全部の確率の和が1.0)

ベイズフィルタの復習 問1.章末問題2を考えてみよう 問2. A, B, C, D という4つの状態があり、初めにAにいる   行動では確率 ½ で停留、1/6 で別の部屋 光が見える確率(A-Dの順): 1/10, 1/5, 2/5, 1/10 一度目の行動後にロボットがAにいる確率 その時光が見えたとする。Cにいる確率

9.1.1位置推定とメモリ管理 確率がゼロのところを陽に表現しない 効率的データ表現を! 前章であつかったベイズフィルタでは,実装上の非効率な点がある.それは「全ての状態に関する存在確率を常に保持しなければならない」という点である. 膨大な状態空間が存在する場合には,ロボットが絶対に存在しないであろう場所における存在確率も含めて,その状態空間全てにおいて存在確率P(st |o1:t , a1:t-1 ) の更新を行う必要がある.これは非効率である. 確率がゼロのところを陽に表現しない 効率的データ表現を!

粒子フィルタのコンセプト 粒子フィルタ モンテカルロ近似 SIR Monte Carlo Localization (MCL) Particle Filter 粒子フィルタのコンセプト これに対して,「ロボットはここにいるかもしれない」という仮説(候補)をいくつか持って,これを更新することで,自己位置推定を進めるのが粒子フィルタ だいたいこのへんにいる・・・・ 粒子フィルタ モンテカルロ近似 SIR

Contents 9.1 ベイズフィルタの問題点 9.2 モンテカルロ近似 9.3 粒子フィルタ 9.4 通路上のホイールダック2号の位置推定    (粒子フィルタ編)

サンプル点の集合を確率分布の近似として扱う 9.2.1サンプル点の集合による 確率分布の近似 「『自らがいそうな状態』に関する候補をいくつか持つことで『すべての状態』についての情報を持つ代わりにする」 なんとなく裏に潜むイカサマサイコロの 確率分布を想像できる! サンプル点の集合を確率分布の近似として扱う

“サンプリング”とは? x(i)~P(x) 確率分布から具体的な値を抽出(サンプリング)すること. サイコロを振って値を出すことに相当. 信号処理のサンプリングとは別物だから気をつけて! 統計学の「標本調査」の標本をサンプルと呼ぶのと同じ “サンプリング”とは? 確率分布から具体的な値を抽出(サンプリング)すること. サイコロを振って値を出すことに相当. 機械学習等の分野では「確率分布からdrawする(引き出す,振り出す)」のような表現を使う. 例)確率分布P(x)からi番目のサンプルx(i)をdrawする. x(i)~P(x) 確率分布からdrawする記号 ※イメージとしては C言語における int x= rand() をイメージするのがよい.

9.2.3 モンテカルロ法 モンテカルロ法は一般的に,確率分布の式を直接扱うかわりに,その確率分布から生成されたサンプル群によって,その確率分布の代用とする方法である. 期待値の評価によく用いられる. より一般的に確率変数x についての関数値f (x) の期待値を評価する. ※ x(i) は確率分布P(x) からサンプリングされるi 番目のサンプル値

例)図形の面積を求める話 S=R*Nin/(Nin+Nout) 下記の内側の図形の面積の近似値を求めよ.長方形の面積はRとする. 領域の面積= 長方形の面積×(6/11) くらい? S=R*Nin/(Nin+Nout)

9.2.2 モンテカルロ近似 モンテカルロ法が前提にしているのは,N 点のサンプル集合が元々の確率分布のよい近似になっているという性質である. として,N 個のサンプル点によって確率分布を近似する.δはクロネッカーのデルタである.

1 2 3 4 5 6 1 2 3 4 5 6 イカサマサイコロのモンテカルロ近似 P(x) は近似のマークです. 例えば半分の確率で6がでるイカサマサイコロを10回振る. x(i)={6,6,3,2,3,4,6,6,6,1}と出たとする. P(x) 1 2 3 4 5 6 1 2 3 4 5 6

演習9-1 モンテカルロ法 あるテストについてクラスの平均点を調べようと100 人のクラスでランダムに10 人から聞き取り調査をした.すると,10 人の回答の平均値は50 点であった.モンテカルロ法に基づいてこのクラスの平均点を求めよ.

Contents 9.1 ベイズフィルタの問題点 9.2 モンテカルロ近似 9.3 粒子フィルタ 9.4 通路上のホイールダック2号の位置推定    (粒子フィルタ編)

9.3 Sampling Importance Resampling (SIR) 非常に巧妙な手法であり,ベイズ更新自体にモンテカルロ近似を適用することによって,アルゴリズム上は常に,仮説となるサンプル点群を持てばいいことになり,非常に実装しやすいアルゴリズムとなる. Sampling Importance Resampling もう一回 サンプリングする サンプリングする 重み付けする

これじゃあ,ベイズフィルタの売りの漸化式にはならない! SIRの導出(1) 第8章の導出を必ず復習! 第8章のベイズフィルタ 事後分布のモンテカルロ近似 右辺のFへの適用 モンテカルロ近似のもとになる 一個一個のサンプルのことを 粒子と呼ぶ. これじゃあ,ベイズフィルタの売りの漸化式にはならない!

SIRの導出(2) 粒子iごとに式を分解してみる. (Point) シグマの順番を変える!

分解した式の解釈 t-1時刻の粒子iが状態遷移したものの確率分布 粒子iが状態遷移後,観測を得て重み付けられたもの 全ての粒子についての和

SIRの導出(3) 状態遷移後の確率分布の近似 思い切ったモンテカルロ近似 以上によりFtが重み付けられた粒子群の和として表される. wiをサンプル点の”重み”と見る.

また,粒子群になった!アルゴリズミックな更新式が得られる! SIRの導出(4) resampling!!! st(i)をサンプリングしてモンテカルロ近似 また,粒子群になった!アルゴリズミックな更新式が得られる! リサンプリング(resampling) するというアイデアにより,SIR では粒子群の効率的な更新のアルゴリズムを得ている. サンプル点の集合は粒子群のように振る舞うため,各サンプル点のことを粒子(particle) と呼ぶ.

9.3.2 粒子フィルタ のアルゴリズム 簡単な実装! メモリ使用量も制御容易!

Contents 9.1 ベイズフィルタの問題点 9.2 モンテカルロ近似 9.3 粒子フィルタ 9.4 通路上のホイールダック2号の位置推定    (粒子フィルタ編)

9.5 例:通路上のホイールダック2号(粒子フィルタ編) 9.5 例:通路上のホイールダック2号(粒子フィルタ編) 移動確率を考慮した 8章と同じ問題を考える. ベイズフィルタと異なり,ロボットの位置についての確率分布を粒子の集合で表現される. 移動は80%の確率で成功する. 70% の確率で正しい観測が得られるが,誤認識が発生した場合はそれぞれ2% の確率でのこり15 個の選択肢の中から誤った観測が得られるものとする. サンプリング(乱数) × × × × × 重み付けによって サンプリング(乱数)

続き 移動確率を考慮した サンプリング(乱数) × × × × × 重み付けによって サンプリング(乱数)

9.4.2 粒子フィルタの応用 移動ロボットの自己位置推定には粒子フィルタはMCL (Monte Carlo Localization,モンテカルロ位置推定) と呼ばれ,大変よく用いられている方法である. 実際には,連続の確率システムの状態方程式に置き換え,確率分布は離散分布ではなく,システムノイズにガウス分布を仮定することが多い. また,コンピュータビジョンの研究では,古くから物体追跡(オブジェクト・トラッキング)に粒子フィルタが用いられている. (動画の例)Monte Carlo Localization demo. (Youtubeより) https://www.youtube.com/watch?v=10tvdmZ7OqU

まとめ 位置推定の問題においてベイズフィルタが持つ問題点をメモリ管理と関連して理解した. モンテカルロ法とモンテカルロ近似について学んだ. SIR のアルゴリズムを数学的に導出し,その近似の仕組みについて理解した. 粒子フィルタのアルゴリズムについて学んだ. 例を通して粒子フィルタの実行時の基本的な手続きについて確認した.

章末問題3,4の解説 まずは自分で取り組んでみよう (解答が巻末にあることはある) しばらくしたら解説する

演習9-2 ホイールダック2号はスタート時無情報である. それぞれのマスにある粒子(パーティクル)の分布の一例を 上記のセル内に書け.粒子の合計数は20とする.

演習9-3 演習9-2の状況の後にホイールダック2号が「停止行動」を とった後に観測を行ったところ右のような観測を得た. この観測を得た後に,ホイールダック2号がいる場所を リサンプリングした結果の粒子数の一例を各セルに書け (乱数は適宜,各自で生成するものとする.)

演習9-4 9-3の後にホイールダック2号は左に移動し, を観測した. その後の自己位置をリサンプリングした場合の粒子の分布 9-3の後にホイールダック2号は左に移動し, を観測した. その後の自己位置をリサンプリングした場合の粒子の分布 として妥当な数字を各セルに記入せよ

予習問題 K-means法に従って図10.6のクラスタリングの過程を確認してみよう 深層学習(ディープラーニング)について知っていることを書こう