線形時間学習及び定数時間識別の一パターン識別手法(情報理論)

概要

論文の詳細を見る
本論文では,学習サンプル数に比例する空間計算量を上限として,学習サンプル数に対して線形オーダの学習時間と定数オーダの認識時間をもつパターン認識手法を提示する.これらの処理時間は理論上最小のオーダである.学習サンプル集合から識別器を構築するパターン識別方法には,これまでに多くの手法が提案されている.しかし,その多くは学習サンプル数に対して線形を超えるオーダの学習時間がかかる.一方,k-NN法は学習サンプル数に比例した時間で学習が行えるが,学習サンプル数が多くなると識別時間が線形に増大する問題がある.そこで,本論文では,学習と認識の両方の時間計算量を最小化する新しい手法を提案し,考察を与える.公開された手書き数字データベースなどに対する認識実験を行ったところ,同一の識別率の条件で識別速度を比較すると,1-NN法の100から500倍以上,また,高速なNN探索手法であるLocality Sensitive Hashingの5から50倍以上高速に識別できることが確認できた.
社団法人電子情報通信学会の論文
2006-11-01