next up previous
: LFE: DNFに基づいたアルゴリズム : 例題からの学習 (LFE) : LFEの定義

従属ツリー

LFEアルゴリズムの内部において,正しい仮説の例は,従属ツリーとして示される. 従属ツリーは,TPsと,目標レベルの仮定が依存する中間レベルの仮定を記録するAND/ORツリーによって構成されている. 例えば,3次元的な外形の仮定は,幾何学的なマッチングアルゴリズムをによって実現され, 3次元の対象モデルから,2次元画像の線の区分の集合への射影のエラーを最小にする外形を発見する. その場合,仮定の外形は, 図3.5のように画像の線の区分を生成を必要とされる, TPの幾何学的なマッチングと,画像の線の区分に依存する. 一般的に,複数の引き数を必要とするTPsから結果として生じるANDノードと, 1つ以上,余計に同じ仮定を生成するTPが出現させるORノードを用いれば,従属は帰納的になる.

それぞれの従属ツリーは,特殊な仮定を生成する異なる方法を表している. 図3.5による例では,Pose-10が,幾何学的なTPマッチングに適用されることによる場合と, TPの平面的な距離に適用される場合のどちらによっても生成され,少なくとも2つのうち1つは要求されることを示している. さらに,幾何学的なTPマッチングが用いられる場合, 2-D-lineset-2に必ず適用される. それに対し,TPの平面的距離が代わりに用いられるなら,Region-14とOrientation-3 は必ず適用される必要がある.(TPの平面的な距離は,2つの画像に基づいた引き数をとる.)

図3.5のような従属ツリーは,SLSの探索フェーズの間生成される特殊な仮定に当てはまる. 図3.6に示すように,特徴ベクトルを用いて,特殊な仮定を取り除き, 目標レベルの仮定の生成を,より一般化された方式を推定する最初の段階とする. 置換による合理性は,TPsがどの仮定を選ぶべきかという前提条件を有する. TPが,目標への到達を保証する仮定 $H$ に適用される必要がある場合, $H$ の特徴は,TPの前提条件として,考慮される必要がある.

一般に,仮定は,従属ツリーを満足する前提条件としてのTPsのいかなる集合によっても,生成が保証されている. 従属ツリー $DT$ はANDノードを満足し,$DT$ の各サブツリーを満足する.$DT$ の根本はORノードで, 少なくとも,$DT$ の1つのサブツリーを満足する必要がある.また,$DT$ の根本はTP $g$ ,そして, $g$ のような前提条件 $P$ を有するリーフノードで,$G$ に含まれている.そして,$g$ の前提条件は, $P$ の超集合にマッチするか,それ自体でなければならない.



SATO Yoshihiro 平成12年10月3日