博 士 （ 工 学 ） 益 山 直 人
学 位 論 文 題 名
パターン認識におけるヵ近隣法の高速化に関する研究 学位論文内容の要旨
近 年 、 情報 処 理 技 術 の進 歩 に 伴 い 人工 知 能 の 実 現 に向 け て 認 識 問題 の 自 動 化 に対 す る 気 運 が高 ま っ て い る 。認 識 問 題 で は 、画 像 認 識 、 音声 認 識 などの 各種応 用面 で個別 に技術 開発が 多く 行われ て い る も の の、 こ れ ら の 技 術の 根 底 に は パタ ー ン 認 識 にお け る 基 礎 的手 法 が 用 い ら れる 。 パ ター ン 認 識 に 関 し て は 様 々 な 研 究 が 為 さ れ て き た。 中 で も1960年 代 から1970年 代 に か け て 行わ れ た
＾ ． 近 隣 法 とそ の 関 連 の 多 くの 試 み は 、 現在 の パ ターン 認識技 術の 礎を築 き、そ の後も 地道 な努カ の 積 み 重 ね で多 方 面 に 大 き な進 歩 を 遂 げ てき て い る。ま た、近 年、 計算機 の性能 は大き く向 上し、
認 識 機 能 を 搭載 し た 機 器 が 相次 い で 実 用 化さ れ る ことに 伴いそ の基 盤であ るパタ ーン認 識技 術への 関 心も 益々高 まって いる。
パ タ ー ン認 識 に お い て古 典 的 な 手 法で あ る ん 近隣 法は 未知サ ンプル の識別 を以下 の手 順で行 う。
（1） 未知サ ンプ ルと全 ての訓 練サン プルと の間の距離を計算するー（2）距離の小さい順に/．個のサン プ ル を 選 び 出す 、 （3） 選出 した ん個 のサン プルで 多数決 を行い 、そ の中で 最も数 が多か った クラス を も って 未知 サンプ ルのク ラスと する 。この ように ＾．近 隣法は 非常 に簡単 なアル ゴリズ ムに よって 行 わ れ る に も関 わ ら ず 、 性 能評 価 が 解 析 的に 行 え 、また 容易に 実現 できる ことか ら実用 性は 非常に 高 く 、 パ タ ーン 認 識 に お け る重 要 な 手 法 とな っ て いる。 この手 法は 認識以 外にも 応用が あり 、例え ば 、密 度推定 問題な どでは 上述の アル ゴリズ ムの（1） 及び（2）の処理を行うことにより得られるふ・
個 のサ ンプル を用い て分布 密度を 推定 するこ とがで きる。
し か し 、こ の ＾ ゛ 近 隣法 は ア ル ゴ リズ ム の 性 質上 、訓 練サン プル数 が増加 すると それ に比例 して 計 算 量 が 増 して い く と ぃ う 特長 が あ り 、 訓練 サ ン プル数 が非常 に大 きな場 合にお いては 大き な障害 と な る 。 そ のた め に 計 算 量 の削 減 を 目 的 とし て 様 々な研 究がさ れて きた。 初期に は、識 別時 に用い る 訓 練 サ ン プル 集 合 の 大 き さを 減 ら す 研 究が 主 に 行われ 、多く の手 法が提 案され た。そ れら の手法 は 、 計 算 量 はか な り 小 さ く なる も の の 、 元と な る 訓練サ ンプル 集合 を正し く識別 するこ とに 主眼を 置 い てい たた めに、 未知サ ンプル を持 ってき て識別 した結 果、本 来の ＾．近 隣法と 異なる 識別 規則を 構 成 す る と ぃう 事 態 が 起 こ り得 た 。 そ の 後、 次 第 にサン プル自 体を 減らす のでは なく、 不必 要な計 算 を 減 ら す 事に よ り 計 算 量 を削 減 す る 手 法が 相 次 いで提 案され た。 今日に 至って もその 傾向 の元に 様 々 な 努 カ が続 け ら れ て い る。 本 研 究 で も本 来 の 識別結 果を保 持し ながら 計算量 の削減 を行 うこと を 目 的 と し 、訓 練 サ ン プ ル の探 索 中 に 即 座に 処 理 を終了 できる よう な条件 を付加 する事 によ って高 速 化を 計る。
本 研 究 では 識 別 結 果 が本 来 の ＾ ． 近隣 法 と 同 じで ある とぃう 条件の 下で計 算量を 減ら すこと を目 的 と す る 。 実際 に は 全 て の 訓練 サ ン プ ル との 距 離 計算を 行うこ とな しに真 のん近 隣点を 見い 出すこ と で 計 算 量 の削 減 を 行 う 。 本手 法 で は た 近隣 点 を 探索す る処理 の途 中で、 探索を 打ち切 って も解が 保 証 さ れ る 条件 を 考 察 し 、 その 有 効 性 及 び特 性 を 明らか にする 。な お、こ の条件 は分枝 限定 法など の 探索 手法と 組み合 わせる ことで 効果 を発揮 する。
本 論文 は全部 で七つ の章か ら成り 、そ の概要 は以下 の通り であ る。
第1章 は本 論 文 の 序 章で あ る 。 パ ター ン 認 識 問 題に お け る 従 来 の試 み につ いての 概説 を行う 。そ の 後、 本論文 の構成 を示し 、目的 を述 べる。
―896
第2章では、 まず、数学的な準備として本論文中で使用する用語の説明を行う。その後、本論文 の主題であるた近隣法の従来研究の概説を行い、それらの特長を示すと共に問題点を指摘する。特 に、＾ 近隣法の改良手法を分類し、本研究との関連する手法に焦点を当ててそれらの詳細を述べる。
第3章では、 提案手法の説明を行う。まず、た近隣法の問題点を指摘する。その後、提案手法の 基本アイデアを説明する。提案手法は未知サンプルの識別時に複数の条件を付加することにより任 意の探索手法の 探索途中に処理を打ち切れるようにしたものである。ここで付加する条件は十分 条件であり、必ずしも有効であるとは限らなぃ。しかし、多数の未知サンプルに対して適用した場 合，平均的に計算量の削減が期待できる。始めにクラスラベルがない場合について適用可能な条件 を説明する。クラスラペルがない場合はパターン認識以外の用途にも用いられ、様々な分野で幅広 い応用が考えられる。また、クラスラベルがない場合については即座に探索を中断する条件の他に も、実際に計算 を行うサンプルの対象を小さくする条件も提案し、その有効性に関する検討を行 う。その後、クラスラベルの付いたパターン認識問題のみに適用できる条件の提案を行い、その概 説を行う。
第4章では、 提案手法の理論的な解析を行う。提案手法の条件を満たし得る理論的な確率につい て論述すると共に、人工データを用い実験を行い、実際に条件を満たした確率を調べ、理論上の確 率との差異について議論し、提案手法の特質を明確にする。
第5章では、まず、＾．近隣法の計算量を削減する手法のーつである分枝限定法の概要を説明し、
提案手法と組み合わせた場合のアルゴリズムを述べる。そして、両者を組み合わせた場合において 実際の自然デ一夕を用い実験を行い、提案手法の効果と特質を明らかにする。実際に提案手法の有 効性を示すために、分枝限定法と分枝限定法に提案手法を組み合わせた場合の比較結果を示す。ま た、前章で述べた論理的な確率との比較検討を行う。
第6章では、 前章で用いた分枝限定法と同様にた近隣法の計算量を削減する手法のーつである大 町らの手法を用い、提案手法と組合せることを考える。大町らの手法は分枝限定法と同じように探 索木を作成する手法であり、クラス毎に部分木を作成することに特長がある。まず、大町らの手法 の概略を説明し 、その後、提案手法と組み合わせたアルゴルズムを示す。そして、第5章と同様に 実験を行い、大町らの手法と大町らの手法に提案手法を組み合わせたものとの差異を調ぺて、前章 の結果との比較検討を行い、組み合わせる手法によって提案手法の効果が変化するかを明らかにす る。また、実際 に識別を行う前の段階にお ける、提案法の有効性の推測 について議論を行う。
第7章は終章 である。本論文の結論を示し、提案手法の特質、問題点を述べる。そして、今後の 課題をまとめる。
― 897―
学位論文審査の要旨
学 位 論 文 題 名
パターン認識におけるカ近隣法の高速化に関する研究
ノくターン認識問題では、画像認識や音声認識などの各種応用面で個別に技術開発が多く 行われているものの、これらの技術の根底には対象をその物理的性質に基づぃて幾っかの カ テ ゴ り あ る い は ク ラ ス に 分 類 す る ノ く タ ー ン 認 識 の 基 礎 的 手 法 が あ る 。 パターン認識の古典的な手法であるん近隣法は、クラスが不明の未知サンプルとクラス が既知の訓練サンプル間の距離を計算し、距離の小さいん個の訓練サンプルが属するクラ スの多数決を採って、未知サンプルのクラスを決定する。ん近隣法はアルゴリズムの簡単 さにも関わらず、性能評価が解析的に行えることと実現が容易であることなどから広く応 用に用いられ、バターン認識における重要な手法となっている。しかし、ん近隣法はアル ゴリズムの性質上、訓練サンプル数の増加に比例して計算量が増す問題があり、実用性の 観点から計算量の削減が望まれている，
本論文では、このような背景から、ん近隣点を求める探索処理で探索時に終端条件を用 いて高速化する手法を提案し、その有効性を検証したものであり、成果は以下の点に要約 される。
（1）探索木を利用する代表的な方法について、探索の途中で真の解を発見した場合にそ の時点で処理を終了できる十分条件を提案し、探索を最後まで行う従来手法の高速化を計 ったー
（2）提案手法の理論的解析を行い、特徴数（次元数）と訓練サンプル数に基いて上記の条 件により探索効率が改善する割合を．亅二界として評価したーまた、次元数が大きいとき、こ の評価式が十分によい推定値を与えることを示した ・
（3）幾っかの実用的なデータベースを用いて、この手法が最大で37%、平均で170iaの計 算量を改善することを示した ・
これを要するに、著者は、情報処理の有効な技法として、ノくターン認識のみならず密度 推定問題などにも応用可能なノf近隣法の改善方法を提案し、実例による検証を行ったもの であり、数理情報工学ならびにノくターン認識工学の分野に寄与するところ大なるものがあ る，，よって著者は、北海道大学博士（亅二学）の学位を授与される資格あるものと認めるー
‑ 898―
