背景

　コンピュータビジョンやロボットの知的制御などの分野では，事象と事象の間にある関係を物理則に基づく因果関係としてとらえ，それを数理モデルで表現する研究が数多く行われてきた．しかし，このような方法で現実世界で起きる様々な事象を記述しようとすると，

• 法則やルールが非常に複雑かつ膨大になってしまう．
• そもそも，因果関係を解き明かすことが非常に困難な問題が多数存在する．

などの問題に直面し，結局は現実世界での知的な行動を実現するシステムは構築できないことになってしまう．事象間の因果関係が不明であり，具体的な事例から相関関係を求めることしかできない問題は数多く存在する．
　そこで，本研究では,因果関係を数理的モデルとして表現しなくても「こうすれば，こうなる」という相関関係のみを学習しておけば実世界での知的な活動はある程度のレベルまで実現できるはずであると考え，そのような相関関係を事象間の非線形写像としてとらえ，この写像関係を高速・高精度に推定するアルゴリズムを開発する．

従来法の問題点

　これまでに提案されてきた非線形写像の学習法は，ニューラルネットワーク(NN)法，Group Method of　DataHandling(GMDH)法，RBFネットワーク(RBFnet)法やNGnet法，そして，事例そのものを記憶しておくk近傍(k-NN)法などが主なものである.　これらの手法には以下のような問題点がある.

NN,GMDH,RBFnet,NGnet法では，

• ネットワークの構造を決定するためのパラメータを予め設定しなければならず，複雑な写像を学習する場合，ネットワークの初期重み係数値を適切に設定しないと学習が収束しない．
• データ毎に非線形写像の推定精度が保障できない．

k-NN法では，

• 入力次元数が大きい場合に，複数の類似事例を検索する(k近傍探索)処理に多大な時間を費やしてしまい写像の計算が高速に行えない．
• 大量のデータをそのまま記憶しておく必要があり，大量のメモリを消費してしまう．

などの問題がある．

原理と特徴

　基本的なアイデアは，非線形写像を区分的な線形写像群に分解することと，スカラーではなくベクトルに対する線形写像を計算するというものである．また，推定される線形写像の汎化性を向上させるため，画像の領域分割処理として有名なsplit&mergeアルゴリズムに基づいた処理も行う．ある入力ベクトルに対して適用すべき線形写像は，2分探索木によって高速に探索される．このような特性から，本手法を Partially　Linear Mapping tree (以下略してPaLM-treeと呼ぶ)アルゴリズムと呼んでいる．

PaLM-treeアルゴリズムは，入力空間を推定誤差に基づいて複数の定義域に自動的に分割して，各定義域とそれに対応する値域に含まれる入力・出力変量データに対して線形写像を推定することで，入力変量xと出力変量yの間の非線形写像関係Ｆを複数の線形写像に分解する.

PaLM-treeを構築する詳しい手順については，参考文献[1]を参照してください.

PaLM-treeは，空でないノードの集合と辺(枝)で構成された2分木の形をした非線形写像を推定するためのデータ構造である．最上位層のノードを根(rootノード)，最下位層のノードを終端ノード，それら以外のノードを内部ノードと呼ぶ．内部ノードには，次元を表す数値，分割基準値，左の枝に結合されたノードへのポインタ，右の枝に結合されたノードへのポインタが格納されている．終端ノードには，，回帰変数とその定義域を表す変数が格納されている.

PaLM-treeは以下のような特徴を持つ．

• NN,GMDH,RBFnet,NGnet法との比較
  
  1. 定義域ごとに推定誤差の評価を行っているので，定義域毎に推定精度が保証できる．
  2. 設定するパラメータは推定誤差の許容値のみで，従来法のように複数のパラメータを調整する必要がない．
• k-NN法との比較
  
  1. 木の深さが浅いため,k-NNより推定計算速度が速い．
  2. データ一点毎の入出力間関係を覚えておく必要がなく各定義域での回帰変数を覚えておくだけでよいのでk-NNと比べてメモリ消費量が少ない．

結果

という式を基に生成されたデータに対して，PaLM-treeにより写像を推定した例．
以下の図で縦軸はｙ軸を表す.　緑の点は，生成されたデータ，赤い4辺形は，局所的に推定された線形写像（入力次元数が2の場合は，平面の方程式）を表す．

応用事例

• 画像の領域分割（CVへの応用）
• 監視カメラ（CVへの応用）
• カメラキャリブレーション（CVへの応用）
• ロボットの運動のモデリング（ロボット制御への応用）
• 物体表面の反射特性のモデリング（CGへの応用）
• 多クラス識別器（パターン認識への応用）

など多種多様な分野で応用が可能．

参考文献

1. 中村恭之，加藤英介，和田俊和，”非線形写像学習のためのPaLM-treeの提案とその応用”，第9回ロボティクスシンポジア予稿集，pp.360-366, 2004. [PDF]
2. 川原輝美，中村恭之，和田俊和，”PaLM-treeによる車輪型移動ロボットの行動計画”，ロボティクスメカトロニクス講演会’04　講演論文集． 2P1-L1-27, 2004. [PDF]
3. 中村恭之，加藤丈和，和田俊和，”非線形写像学習のためのPaLM-treeの提案”，日本ロボット学会誌，Vol.23,No.6,pp.732-742,2005．

ソフトウェア
　本アルゴリズムに興味があり，試してみたい方は，中村 (ntakayuk@sys.wakayama-u.ac.jp)までメールで御連絡下さい．
注意
個人や研究目的での使用に限らせて頂きます．　また，本ソフトウェアを使用して生じたいっさいの問題に対して責任は負えませんので御了承下さい．

• Linux版(CLAPACKが必要です.)
• Windows版（CLAPACKが必要です.VC++6.0でコンパイル確認）