アクティブ探索法の探索効率と探索精度に関する一考察

摘要

アクティブ探索法は，パターンの探索をヒストグラムを利用して高速かつ高い精度で行う方法であり，画像，音声の探索などにおいてその効果が確認されている．しかし，どのようなパターンに対して適用可能であるかについてはよく知られていない．そこで，本研究では，アクティブ探索の探索効率と探索精度を見積もるための検討を行う．アクティブ探索法の対象として様々なパターンを考えると，記号列探索がその共通部分となるため，記号列探索め問題に焦点を絞ることにする．探索効率の指標として，照合をスキップできる幅の期待値を導出し，探索精度についてはエントロピーを使った指標を提案する．それぞれについて，人工データによる検証を行い，その有効性を示す．