(57)【要約】【課題】特徴情報の分布を仮定することなく，未分類の標本を用いて分類尺度を決定可能な分類装置、分類方法、およびプログラムを提供する。【解決手段】クラスに分類された分類済標本の相関作用素と、分類済標本に基づき重み付けされ、かつクラスに分類されない未分類標本の相関作用素と、に基づきクラス毎の相関作用素を算出する。この相関作用素に基づき、入力された標本について、クラス毎の分類尺度を決定し、決定された分類尺度に基づき、入力された標本のクラスへの分類を決定する。【選択図】図１
2006235953.tif 000002
【特許請求の範囲】
【請求項１】
所定の複数のクラス毎に分類された分類済標本の相関作用素と、前記分類済標本に基づき重み付けされ、かつ前記所定の複数のクラスに分類されない未分類標本の相関作用素とに基づき算出された、前記所定の複数のクラス毎の拡張相関作用素を記憶する拡張相関作用素記憶部と、
標本の情報を入力する入力部と、
前記記憶された拡張相関作用素と、前記入力された標本の情報とに基づき、前記入力された標本の前記所定の複数のクラス毎の分類尺度を決定する分類尺度決定部と、
前記決定された分類尺度に基づき、前記入力された標本の前記所定の複数のクラスへの分類を決定するクラス分類決定部と、
を具備することを特徴とする分類装置。
【請求項２】
前記入力された標本の情報から、前記複数のクラスへの分類についての特徴となる特徴情報を抽出する特徴抽出部をさらに具備し、
前記分類尺度決定部が前記抽出された標本の特徴情報に基づき、前記分類尺度を決定する
ことを特徴とする請求項１記載の分類装置。
【請求項３】
所定の複数のクラス毎に分類された分類済標本の第１の相関作用素を算出する第１の相関作用素算出部と、
前記分類済標本に基づき重み付けされ、かつ前記所定の複数のクラスに分類されない未分類標本の第２の相関作用素を算出する第２の相関作用素算出部と、
前記第１、第２の相関作用素に基づき、前記所定の複数のクラス毎の拡張相関作用素を算出する拡張相関作用素算出部と、
をさらに具備することを特徴とする請求項１記載の分類装置。
【請求項４】
前記第１の相関作用素算出部が、前記分類済標本に関するノイマン・シャッテン積に基づき、第１の相関作用素を算出する
ことを特徴とする請求項３記載の分類装置。
【請求項５】
前記第２の相関作用素算出部が、前記未分類標本に関するノイマン・シャッテン積に基づき、第２の相関作用素を算出する
ことを特徴とする請求項３記載の分類装置。
【請求項６】
前記分類尺度決定部が、前記拡張相関作用素と、前記拡張相関作用素のムーア・ペンローズ一般逆作用素と、前記標本の情報とに基づき、前記分類尺度を決定する
ことを特徴とする請求項３記載の分類装置。
【請求項７】
所定の複数のクラス毎に分類された分類済標本の第１の相関作用素を算出するステップと、
前記分類済標本に基づき重み付けされ、かつ前記所定の複数のクラスに分類されない未分類標本の第２の相関作用素を算出するステップと、
前記第１、第２の相関作用素に基づき、前記所定の複数のクラス毎の拡張相関作用素を算出するステップと、
標本の情報を入力するステップと、
前記記憶された拡張相関作用素と、前記入力された標本の情報とに基づき、前記入力された標本の前記所定の複数のクラス毎の分類尺度を決定するステップと、
前記決定された分類尺度に基づき、前記入力された標本の前記所定の複数のクラスへの分類を決定するステップと、
を具備することを特徴とする分類方法。
【請求項８】
所定の複数のクラス毎に分類された分類済標本の第１の相関作用素を算出するステップと、
前記分類済標本に基づき重み付けされ、かつ前記所定の複数のクラスに分類されない未分類標本の第２の相関作用素を算出するステップと、
前記第１、第２の相関作用素に基づき、前記所定の複数のクラス毎の拡張相関作用素を算出するステップと、
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、標本を所定のクラスに分類する分類装置、分類方法、およびプログラムに関する。
【背景技術】
【０００２】
未分類の標本を所定のクラスに分類する分類方法が種々の分野で用いられている。例えば、文字認識は読み取った文字のパターンを所定のクラスに分類するものである。また、文書分類は、文書を構成する文字に基づき、文書を所定のクラスに分類するものである。
ここで、クラスに未分類の標本を用いて分類器を構成する技術が公開されている。例えば、未分類の標本のクラスを隠れ変数として用いるExpectation-Maximization法(以下「EM法」という)，exponential-mixture 法(以下「em法」という)がある。また、Transductive Support Vector Machine 法(以下「TSVM法」という)，Co-Training法が挙げられる（非特許文献１〜４参照）。
【非特許文献１】“Maximum likelihood from incomplete data via the EM algorithm," J. of Royal Statistical Society Series B, 1977, Vol. 39, p. 1-38
【非特許文献２】”The EM Algorithm and Information Geometry in Neural Network Learning," Neural Computation, 1994, Vol. 7, p. 13-18
【非特許文献３】“Transductive inference for text classification using support vector machines," Proc. of 16th International Conference on Machine Learning, 1999, p 200-209
【非特許文献４】“Combining Labeled and Unlabeled Data with Co-Training," Proc. of 11th Annual Conference on Computational Learning Theory, 1998, p. 92-100
【発明の開示】
【発明が解決しようとする課題】
【０００３】
EM法やem法では，クラスの特徴情報の分布が既知であったり、正規分布などの特定の分布に従っていることを仮定したりする必要がある。しかしながら、分類問題一般について、このような条件は必ずしも満たされない。即ち、EM法やem法を適用することは、このような条件を設定したモデルを扱うことになり、このモデルの近似の精度は実際の特徴情報の分布に依存する。このため、すべての分類問題において精度を保証することが困難である。
TSVM法では，SVM（Support Vector Machine）を用いることで、クラスの特徴情報の分布を仮定することなくクラスに分類することが可能である。しかし、クラスに分類するための分類尺度を算出することができない。このため，標本を複数のクラスに重複して分類することや，分類尺度順に並び替えることが困難である。
Co-Training法は，未分類の標本をクラスに分類した後に，分類手段を作り替える方法である。しかし、最終的な分類手段が学習の順番に依存することから，精度の保証が困難である。また，すべてのクラスで共通な相関や情報を共有することが困難である。
【０００４】
以上述べたように，EM法、em法、TSVM法、Co-Training法いずれにおいても特徴情報の分布を仮定することなく，未分類の標本を使用して，クラスへの分類尺度を決定することは困難である。
上記に鑑み、本発明は、特徴情報の分布を仮定することなく、未分類の標本を用いて分類尺度を決定可能な分類装置、分類方法、およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明に係る分類装置は、所定の複数のクラス毎に分類された分類済標本の相関作用素と、前記分類済標本に基づき重み付けされ、かつ前記所定の複数のクラスに分類されない未分類標本の相関作用素とに基づき算出された、前記所定の複数のクラス毎の拡張相関作用素を記憶する拡張相関作用素記憶部と、標本の情報を入力する入力部と、前記記憶された拡張相関作用素と、前記入力された標本の情報とに基づき、前記入力された標本の前記所定の複数のクラス毎の分類尺度を決定する分類尺度決定部と、前記決定された分類尺度に基づき、前記入力された標本の前記所定の複数のクラスへの分類を決定するクラス分類決定部と、を具備することを特徴とする。
【発明の効果】
【０００６】
特徴情報の分布を仮定することなく，未分類の標本を用いて分類尺度を決定可能な分類装置、分類方法、およびプログラムを提供できる。
【発明を実施するための最良の形態】
【０００７】
以下、図面を参照して、本発明の実施の形態を詳細に説明する。
図１は本発明の一実施形態に係る分類装置１０を表すブロック図である。
分類装置１０は、標本の情報を入力し、標本をクラスに分類した結果を出力するものであり、コンピュータ（ハードウェア）とソフトウェアとの組み合わせから構成可能である。
分類装置１０は、入力部１１、前処理部１２、特徴抽出部１３、クラス分類尺度決定部１４、クラス決定部１５，後処理部１６、拡張相関作用素記憶部１７を有する。
【０００８】
入力部１１は、標本の情報を入力する入力手段、例えば、テレビカメラ、スキャナ、マイクロホン、タブレット、キーボード、マウス、ディスクドライブ（ＣＤ−ＲＯＭドライブ、ＤＶＤドライブ等）、通信線である。
「標本」は、所定のクラスに分類される対象である。即ち、「標本の情報」は、それぞれの分類対象を表すデータを意味し、画像情報、音声情報、テキスト情報等が挙げられる。
【０００９】
入力部１１での入力処理として、対象（標本）のテレビカメラによる撮影（録画），スキャナによるスキャンニング，マイクによる録音を挙げることができる。また、タブレットでの描画，キーボードによるタイピングも入力部１１での入力処理に含めることができる。
なお、「クラス」は、対象を分類するための区分を意味する。例えば、文字認識では文字の区分、顔画像の分類では顔の分類区分、文書分類では文書の分類区分がそれぞれ該当する。
【００１０】
前処理部１２は、入力部１１で入力された標本の情報に対して，特徴抽出部１３での特徴抽出処理に先立って行う処理をいい、例えば、入力された標本の情報からのノイズ除去や二値化処理が挙げられる。また、入力された標本の情報からの分類に不必要な情報の削除や分類に必要な情報の抽出も前処理に含められる。前処理の具体例として、画像からの文字分類の際の画像からのノイズ除去，二値化，文字の切出を挙げることができる。また、顔画像の分類であれば顔画像の切出し，文書の分類であれば，フォーマットの変換や、HTMLタグの除去を挙げることができる。
【００１１】
特徴抽出部１３は、前処理部１２で処理された標本の情報から、クラスへの分類に必要な特徴情報を１つまたは複数抽出する。
この抽出は、前処理部１２からの出力の集合から、特徴抽出部１３からの出力の集合である原特徴空間への写像に対応する。このとき，原特徴空間はヒルベルト（Hilbert）空間で表現することが可能である。
特徴抽出の具体例として、文字認識では文字を構成するドットの方向分布（例えば、加重方向指数ヒストグラム法（「“加重方向指数ヒストグラムと疑似マハラノビス距離を用いた手書き数字，ひらがな認識”信学技報，Vol. PRL82-79, pp.105-112, Jan. 1983」参照））を挙げることができる。また、文書分類では，文書中の各単語の数（例えば、Bug Of Words法（「”Foundations of statistical natural language processing," MIT press, Cambridge, 1999」参照））を挙げることができる。
【００１２】
クラス分類尺度決定部１４は、分類したい標本の特徴情報と、拡張相関作用素記憶部１７に記憶された拡張相関作用素Ｒ’とを用いて，分類したい標本のクラスへの分類尺度（クラス分類尺度、例えば、類似度、相違度）を決定する。なお、拡張相関作用素Ｒ’の詳細は後述する。
クラス分類尺度の決定には，CAFESSM法（「“Subspace Method and Projection Operators," Proc. of 4th International Joint Conf. on Pattern Recognition, p.449-451」参照），またはカーネル標本空間射影法（「”Kernel Sample Space Projection Method for Pattern Recognition," Proc. of 17th International Conference on Pattern Recognition, 2004, p. 435-438」参照）を用いることができる。
CAFESSM法やカーネル標本空間射影法では、相関作用素Ｒｉを用いてクラス分類尺度を決定するのが通例である。これに対して、本実施形態では、相関作用素Ｒｉに換えて拡張相関作用素Ｒｉ’を用いて、クラス分類尺度を決定する。
【００１３】
クラス決定部１５は、クラス分類尺度決定部１４で決定されたクラス分類尺度に基づいて、標本それぞれのクラスを決定する。例えば、類似度が最大値、または所定の閾値以上のクラスに、標本のクラスを決定する。
後処理部１６は、クラス分類尺度決定部１４で決定されたクラスの検索，並び替え等を行う。
拡張相関作用素記憶部１７は、拡張相関作用素Ｒ’を記憶する記憶装置、例えば、ハードディスクドライブ、半導体メモリである。
【００１４】
以下、拡張相関作用素Ｒ’の詳細を説明する。拡張相関作用素Ｒ’は分類済みの標本と未分類の標本を統合することで生成される。
図２は、本発明の一実施形態に係る拡張相関作用素生成装置２０を表すブロック図である。拡張相関作用素生成装置２０は、拡張相関作用素Ｒ’を生成するものであり、コンピュータ（ハードウェア）とソフトウェアとの組み合わせから構成可能である。
なお、本実施形態では、分類装置１０と拡張相関作用素生成装置２０とを別体で構成しているが、これらを一体として構成してもよい。このようにすると、単一の分類装置で、拡張相関作用素Ｒ’の生成およびそれを用いた標本の分類の双方を実行可能である。
【００１５】
本図に示すように、分類済みの標本の情報および未分類の標本の情報をそれぞれ、入力部２１，２２，前処理部２３，２４，特徴抽出部２５，２６で処理し、特徴情報統合部２７で統合することで、拡張相関作用素Ｒ’が生成される。
【００１６】
入力部２１，２２，前処理部２３，２４，特徴抽出部２５，２６はそれぞれ、図１の入力部１１、前処理部１２、特徴抽出部１３に対応するものであり、標本の情報の入力、前処理、特徴抽出を行う。
特徴情報統合部２７は、分類済みの標本の特徴情報および未分類の標本の特徴情報を統合して、予め定義されたクラスｉをそれぞれ表現する拡張相関作用素Ｒｉ’を生成する。
【００１７】
図３は、特徴情報統合部２７での拡張相関作用素Ｒ’の生成プロセスを表す概念図である。
本図に示すように、クラスiの拡張相関作用素Ｒｉ’は，クラスｉに分類済みの標本から得られる相関作用素Ｒｉと，分類済みの標本から得られる関数ｆで重みづけされた未分類の標本に関する相関作用素Ｑｉとの和として定義できる。
【００１８】
以下、拡張相関作用素Ｒ’の決定、クラス分類尺度の決定の詳細を数学的に表す。
既述のように、クラス分類尺度の決定（算出）にCAFESSM 法、カーネル標本空間射影法を用いることができる。これらの方法では，標本のクラスへの分類尺度（クラス分類尺度）を類似度として測る。このため、以降の議論では，クラス分類尺度を類似度とする。
【００１９】
Ａ．CAFESSM 法による算出
まず、CAFESSM 法による拡張相関作用素Ｒ’およびクラス分類尺度の算出につき説明する。
（１）拡張相関作用素Ｒ’の算出
まず、拡張相関作用素Ｒ’の算出の詳細を説明する。
クラスｉに分類済みの標本の総数をNi，クラスｉに分類済みの標本の集合をＬｉ、クラスｉに分類済みのn番目の標本から得られた特徴情報をｘｉｎ，未分類の標本の総数をＭ，未分類の標本の集合をＵ，未分類のｍ番目の標本から得られた特徴情報をｙｍとおく。
【００２０】
このとき、クラスｉの分類済みの標本から得られる相関作用素Ｒｉは以下の式（１）で与えられる。
【数１】
2006235953.tif 000003
【００２１】
クラスiの拡張相関作用素Ｒｉ’は以下の式（２）で与えられる。
【数２】
2006235953.tif 000004
式（２）の「Ｒｉ＋」以降が分類済みの標本から得られる関数fで重みづけされた未分類の標本に関する相関作用素Ｑｉに対応する。
【００２２】
式（２）の関数fの例として，以下の式（３）、（４）を挙げることができる。
【数３】
2006235953.tif 000005
ここでαは，予め定められた定数である。
【００２３】
（２）類似度の算出
次に類似度の算出の詳細を説明する。
図４は、CAFESSM 法による類似度の算出法の概念を表す模式図である。
本図に示すように、各クラスｉのサンプル（標本）ベクトル（｛ｘｉｎ｝n=1Ｎｉ）が張る部分空間（クラスｉに分類済みの標本の集合Ｌｉが配置される空間）に未知の入力ｘを射影する。
【００２４】
このとき、入力ｘがクラスｉのサンプルベクトルが張る部分空間（｛ｘｉｎ｝n=1Ｎｉ）への射影ノルムをＳｉ（ｘ）とする。入力ｘの分類済標本集合Ｌｉへの類似度はこの射影ノルムＳｉ（ｘ）で測られる。
【００２５】
即ち，未知の入力ｘの分類済みの標本の集合Ｌｉへの類似度は、次の式（５）で表される射影ノルムＳｉ（ｘ）で表される。
【数４】
2006235953.tif 000006
【００２６】
Ｂ．カーネル標本空間射影法による算出
次にカーネル標本空間射影法による類似度の算出につき説明する。
図５は、カーネル標本空間射影法による類似度の決定の算出法の概念を表す模式図である。
本図に示すように、入力空間Ｈ１の標本ｘが関数Φによりカーネル特徴空間に写像される。写像後の標本（写像標本）Φ（ｘ）は、カーネル標本空間に写像後のサンプル（標本）ベクトル（｛Φ（ｘｉｎ）｝n=1Ｎｉ）が張る空間（カーネル標本空間）に射影される。
このとき、クラスｉのサンプルベクトルが張る部分空間（｛Φ（ｘｉｎ）｝n=1Ｎｉ）への入力ｘの射影ノルムをＳｉＫＳＰ（ｘ）とする。入力ｘの分類済標本集合Ｌｉへの類似度はこの射影ノルムＳｉＫＳＰ（ｘ）で計られる。
【００２７】
（１）カーネル拡張相関作用素Ｒｉ’Φの算出
カーネル標本空間射影法を適用した場合，拡張相関作用素Ｒ’に換えて、後述するカーネル拡張相関作用素Ｒｉ’Φを用いる。カーネル標本空間射影法での相関作用素Ｒｉは，行列ではないため，Moore-Penrose（ムーア・ペンローズ）一般逆作用素を求めることができないからである。
拡張相関作用素Ｒｉ’を以下のように変形する。なお、式（２）の拡張相関作用素Ｒｉ’の第２項は非負定値自己共役作用素となるので、固有値分解ができ、その固有値はすべて非負の実数となる（「”Nonlinear component analysis as a kernel eigenvalue problem," Neural Computation, Vol. 10, No. 5, pp. 1299-1319, 1998」参照）。
【００２８】
カーネル標本空間射影法による原特徴空間Ｒｄからカーネル特徴空間Ｆへの写像をΦ: Ｒｄ→Ｆとするとカーネル拡張相関作用素Ｒｉ’Φは、以下の式（６）、（７）によって表される。
【数５】
2006235953.tif 000007
なお、固有値は降順に選び，適当な次元Ｄで打ち切ることができる。
【００２９】
以上のように、カーネル標本空間射影法では、拡張相関作用素Ｒ’に換えて、カーネル拡張相関作用素Ｒｉ’Φを用いる。即ち、図１〜図３での拡張相関作用素Ｒ’がカーネル拡張相関作用素Ｒｉ’Φに置き換えられることになる。
拡張相関作用素Ｒ’と、カーネル拡張相関作用素Ｒｉ’Φは本質的に相違する訳ではなく、拡張相関作用素であることには変わりがない。但し、前者が行列で表されるのに対して、後者は数式（あるいはパラメータ）として表現される点が相違する。
【００３０】
（２）類似度ＳｉＫＳＰ（ｘ）の算出
εn をＲN+D のｎ番目の自然基底とする。作用素S : ＲN+D → F を次の式（８）と置く。
【数６】
2006235953.tif 000008
【００３１】
カーネル標本空間射影法を適用した場合の相関作用素Ｒｉは，次の式（９）で表すことができる。
【数７】
2006235953.tif 000009
【００３２】
カーネル標本空間射影法での類似度ＳｉＫＳＰ（ｘ）は，次の式（１０）で表すことができる。
【数８】
2006235953.tif 000010
【００３３】
ここで、（Ｓｉ＊Ｓｉ），（Ｓｉ＊Φ（ｘ））は，それぞれＲ(N+D)×(N+D)の行列，ＲN+D のベクトルとなり，類似度を計算することができる。
具体的には、式（１０）は以下の式（１１）のように変形することができる。
【数９】
2006235953.tif 000011
【００３４】
式（１１）中の（Ｓｉ＊Ｓｉ）＋は、次の式（１２）のように（Ｎｉ＋Ｄ）次元の正方行列となり、特異値分解法やノイマン級数法により、ＭＰ（Moore-Penrose）一般逆作用素を求めることができる。
【数１０】
2006235953.tif 000012
【００３５】
一方、（Ｓｉ＊Φ（ｘ））は、次の式（１３）のように、（Ｎｉ＋Ｄ）次元のベクトルとなる。これにより、行列のＭＰ一般逆作用素（ＭＰ一般逆行列）を求める演算と行列とベクトルの積の演算、内積演算により、類似度を算出できる。
【数１１】
2006235953.tif 000013
【００３６】
図６は、式（１１）で表されるカーネル標本空間射影法での類似度ＳｉＫＳＰ（ｘ）の算出手順の一例を表すフロー図である。
行列（Ｓｉ＊Ｓｉ）およびベクトル（Ｓｉ＊Φ（ｘ））を算出し（ステップＳ１１），（Ｓｉ＊Ｓｉ）のＭＰ一般逆作用素の算出（ステップＳ１２），（Ｓｉ＊Ｓｉ）＋とΦ（ｘ）の積の算出（ステップＳ１３）、Φ（ｘ）と（Ｓｉ＊Ｓｉ）＋Φ（ｘ）との内積の算出（ステップＳ１４）によって、類似度を算出できる。
【００３７】
Ｃ．クラスの決定
クラス決定部１５では，クラス類似度決定部１４において得られた類似度Ｓｉ（ｘ）あるいは，ＳｉＫＳＰ（ｘ）に対し，最大値に属するクラスへ決定する，または，適当な閾値以上のクラスへ決定する。ここで閾値は，予め決められた定数または，Ｓｉ（ｘ） (ｉ=１，２，… ) によって決まる関数，または，ＳｉＫＳＰ（ｘ）、(ｉ=１，２，… )によって決まる関数を用いる。
【００３８】
以上のように、本実施形態では，予め定められた複数のクラスに分類済みの有限の標本と有限の未分類の標本から分類に必要な特徴情報を抽出する。なお、1つのクラスに対し，分類済み標本は1つ以上存在するとする。そして，得られた特徴情報の組からクラスごとにクラスの特徴を表現する拡張相関作用素を得る。この拡張相関作用素は，分類済みの標本から得られる特徴情報と未分類の特徴から得られる特徴情報の両方に基づく。
分類したい入力に対しても，同様に特徴情報を得る。分類したい入力から得られた特徴情報と各クラスの拡張相関作用素を用いて，分類したい入力と各クラスとの分類尺度を得る。得られた分類尺度を基にクラスの決定等を行う。
【００３９】
以上のように本実施形態では，予め定義されたクラスに分類済みの標本と，未分類の標本とを用いて，特定の入力とクラスの類似度を決定できる。
また、特徴情報の分布を特定の分布に仮定しないで，分類済みの標本から得られる特徴情報と未分類の標本から得られる特徴情報を用いて、入力された標本とそれぞれのクラスの類似度を求め，入力を複数のクラスへ分類することができる。
特徴情報の分布を特定の分布に仮定しないことにより，どのような入力に対しても高精度の類似度を求めることができる。また，類似度を用いて複数のクラスへ分類させることや，類似度順に並び替えを行うことも可能である。
【００４０】
（その他の実施形態）
本発明の実施形態は上記の実施形態に限られず拡張、変更可能であり、拡張、変更した実施形態も本発明の技術的範囲に含まれる。
【図面の簡単な説明】
【００４１】
【図１】本発明の一実施形態に係る分類装置を表すブロック図である。
【図２】本発明の一実施形態に係る拡張相関作用素生成装置を表すブロック図である。
【図３】図２の特徴情報統合部での拡張相関作用素の生成プロセスを表す概念図である。
【図４】CAFESSM 法による類似度の算出法の概念を表す模式図である。
【図５】カーネル標本空間射影法によるクラス分類尺度の決定法の概念を表す模式図である。
【図６】カーネル標本空間射影法での類似度の算出手順の一例を表すフロー図である。
【符号の説明】
【００４２】
１０…分類装置、１１…入力部、１２…前処理部、１３…特徴抽出部、１４…クラス分類尺度決定部、１５…クラス決定部、１６…後処理部、１７…拡張相関作用素記憶部、２１，２２…入力部、２３，２４…前処理部、２５，２６…特徴抽出部、２７…特徴情報統合部
【図１】
2006235953.tif 000014
【図２】
2006235953.tif 000015
【図３】
2006235953.tif 000016
【図４】
2006235953.tif 000017
【図５】
2006235953.tif 000018
【図６】
2006235953.tif 000019