(57)【要約】【課題】改良された、コンピュータにより実施される強分類器を構築する方法を提供する。【解決手段】方法は、弱分類器を組み合わせて１組の弱分類器組み合わせを形成することによって弱分類器から強分類器を構築する。各弱分類器組み合わせをブースティングして、弱分類器組み合わせ毎に重み付き得点を求め、所定のしきい値を超える重み付き得点を有する弱分類器組み合わせが、強分類器を形成するものとして選出される。【選択図】図１
2007157130.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータにより実施される強分類器を構築する方法であって、
複数の弱分類器を選出する工程と、
前記弱分類器を組み合わせて１組の該弱分類器の組み合わせを形成する工程と、
前記弱分類器の各組み合わせをブースティングして該弱分類器の組み合わせ毎に重み付き得点を求める工程と、
所定のしきい値を超える重み付き得点を有する前記弱分類器の組み合わせを選出し、前記強分類器を形成する工程と、
を備えたコンピュータにより実施される強分類器を構築する方法。
【請求項２】
前記弱分類器は二値分類器及びマルチクラス分類器を含む請求項１に記載のコンピュータにより実施される強分類器を構築する方法。
【請求項３】
各弱分類器の出力を事後確率で表す工程と、
各弱分類器に信頼度行列を関連付ける工程と、
をさらに含む請求項１に記載のコンピュータにより実施される強分類器を構築する方法。
【請求項４】
組み合わせは前記弱分類器の線形組み合わせ及び非線形組み合わせを含む請求項３に記載のコンピュータにより実施される強分類器を構築する方法。
【請求項５】
組み合わせは近似ベイズ結合である請求項３に記載のコンピュータにより実施される強分類器を構築する方法。
【請求項６】
各弱分類器の出力λは、クラス数である１〜Ｋの整数値をとる確率変数
【数１】
2007157130.tif 000013
であり、真のクラスのラベルωの値にわたる確率分布は、
【数２】
2007157130.tif 000014
であり、前記近似ベイズ結合は、
【数３】
2007157130.tif 000015
であり、式中、
【数４】
2007157130.tif 000016
は前記弱分類器の予測確率であり、ｗｋは該弱分類器の重みである請求項５に記載のコンピュータにより実施される強分類器を構築する方法。
【請求項７】
前記重みは前記クラスの信頼度行列に従う請求項６に記載のコンピュータにより実施される強分類器を構築する方法。
【請求項８】
前記１組の組み合わせは、
【数５】
2007157130.tif 000017
に従って形成され、式中、Ｐｋ(ωｊ|ｘ)は非線形重みβに従う重み付き弱分類器であり、Ｓｎはｎ番目の分類器組み合わせである請求項６に記載のコンピュータにより実施される強分類器を構築する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはコンピュータにより実施される分類器に関し、特に複数の弱分類器を組み合わせることによって構築される強分類器に関する。
【背景技術】
【０００２】
動き及び対象物の認識は、監視用途及びコンピュータビジョン用途で中心的な役割を果たしている。A. F. Bobick著「Movement, activity, and action: The role of knowledge in the perception of motion」(Royal Society Workshop on Knowledge-based Vision in Man and Machine, 1997)、Aggarwal他著「Human motion analysis: A review」(Computer Vision and Image Understanding, vol. 73, no. 3, pp. 428-440, 1999)、及びNevatia他著「Video-based event recognition: activity representation and probabilistic recognition methods」(Computer Vision and Image Understanding, vol. 96, no. 2, pp. 129-162, November 2004)を参照のこと。
【０００３】
認識とは、部分的には分類作業である。事象及び対象物の認識での主な問題は、事象及び対象クラスの数の多さである。このため、システムは、多数のより単純な分類作業から導き出される複雑な分類に基づいての判断が可能であるべきである。
【０００４】
その結果、多くの分類器は、多くの弱分類器を組み合わせて強分類器を構築する。分類器を組み合わせる主目的は、弱分類器の個々の出力を強分類器の構成要素としてまとめることであり、組み合わせられた分類器は、個々の各構成要素分類器よりも精度が高い。
【０００５】
分類器を組み合わせる従来技術の方法としては、和、投票、及び積の結合規則を適用する方法がある(非特許文献１〜４参照)。
【０００６】
【非特許文献１】Ross他著「Information fusion in biometrics」(Pattern Recognition Letters, vol. 24, no. 13, pp. 2115-2125, 2003)
【非特許文献２】Pekalska他著「A discussion on the classifier projection space for classifier combining」(3rd International Workshop on Multiple Classifier Systems, Springer Verlag, pp. 137-148, 2002)
【非特許文献３】Kittler他著「Combining evidence in multimodal personal identity recognition systems」(Intl. Conference on Audio- and Video-Based Biometric Authentication, 1997)
【非特許文献４】Tax他著「Combining multiple classifiers by averaging or by multiplying?」(Pattern Recognition, vol. 33, pp. 1475-1485, 2000)
【非特許文献５】Bilmes他著「Directed graphical models of classifier combination: Application to phone recognition」(Intl. Conference on Spoken Language Processing, 2000)
【非特許文献６】Ivanov著「Multi-modal human identification system」(Workshop on Applications of Computer Vision, 2004)
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、改良された、コンピュータにより実施される強分類器を構築する方法を提供する。
【課題を解決するための手段】
【０００８】
本発明は、コンピュータにより実施される強分類器を構築する方法であって、複数の弱分類器を選出する工程と、前記弱分類器を組み合わせて該弱分類器の組み合わせを形成する工程と、前記弱分類器の各組み合わせをブースティングして該弱分類器の組み合わせ毎に重み付き得点を求める工程と、所定のしきい値を超える重み付き得点を有する前記弱分類器の組み合わせを選出し、前記強分類器を形成する工程と、を備えたコンピュータにより実施される強分類器を構築する方法にある。
【発明の効果】
【０００９】
本発明の一実施の形態は、重み付きアンサンブルブースティングを用いて弱分類器を組み合わせて強分類器にする方法を提供する。重み付きアンサンブルブースティング法は、ベイズ平均戦略をブースティングの枠組みと組み合わせ、分類器の有用な連結特徴組み合わせを見つけ、従来技術のブースティングプロセスよりも低い誤り率を実現する。この方法は、分類器選出プールの構成に関して妥当なレベルの安定性を示す。
【００１０】
特に、本発明の方法は、弱分類器を組み合わせて１組の弱分類器組み合わせを形成することによって弱分類器から強分類器を構築する。各弱分類器組み合わせをブースティングして、弱分類器組み合わせ毎に重み付き得点を求め、所定のしきい値を超える重み付き得点を有する弱分類器組み合わせが、強分類器を形成するものとして選出される。
【発明を実施するための最良の形態】
【００１１】
図１は、本発明の一実施の形態による弱分類器(Ａ、Ｂ、Ｃ)１０１から強分類器１０９を構築する方法を示す。弱分類器を組み合わせて１１０、１組の組み合わせ分類器１０２を生成する。次いで、ブースティングプロセス１２０を１組の組み合わせ分類器に適用して、強分類器１０９を構築する。
【００１２】
＜弱分類器＞
弱分類器は、二値分類器及びマルチクラス分類器を含むことができる。二値分類器は、１つのクラスが認識されるか否かを判断する。マルチクラス分類器はいくつかのクラスを認識することができる。
【００１３】
各弱分類器の出力は、事後確率で表すことができる。各確率は、分類器の特定の分類についての、たとえば対象物の識別についての精度を示す。さらに、各弱分類器に信頼度行列を関連付けることができる。信頼度行列は、特定のクラスに対する分類器のパフォーマンスの程度を示す。信頼度行列は、分類器を既知の、すなわち「ラベル付き」データで訓練し、確認することによって得られる。
【００１４】
＜組み合わせ＞
組み合わせるステップは、弱分類器の考えられるすべての線形組み合わせ１０２’及び種々の非線形組み合わせ１０２’’を含むことができる。たとえば、６つの弱分類器は５００を超える組み合わせをもたらし得る。
【００１５】
組み合わせ１１０は、近似ベイズ結合の適応を利用することもできる。ベイズ結合は、分類器信頼度の或る測度を用いて、クラス毎に弱分類器に期待される精度を基準にして各弱分類器の予測確率を重み付けする。Ivanov著「Multi-modal human identification system」(Workshop on Applications of Computer Vision, 2004)及びIvanov他著「Using component features for face recognition」(International Conference on Automatic Face and Gesture Recognition, 2004)(共に参照により本明細書に援用する)を参照のこと。
【００１６】
特に、弱分類器の出力λは、１〜Ｋの整数値(すなわちクラス数)をとる確立変数
【００１７】
【数１】
2007157130.tif 000003
【００１８】
として見られる。分類器毎に、真のクラスのラベルωの値にわたる確率分布が、所与の分類器予測
【００１９】
【数２】
2007157130.tif 000004
【００２０】
について分かっている場合、近似ベイズ結合は、各弱分類器の個々のクラス予測の周辺化を介して導き出すことができる。
【００２１】
【数３】
2007157130.tif 000005
【００２２】
式中、
【００２３】
【数４】
2007157130.tif 000006
【００２４】
は弱分類器の予測確率であり、ｗｋは各弱分類器の重みである。式は、クラスに関連する信頼度行列に従って各分類器の予測に重みを付ける。
【００２５】
セット１０２中の組み合わせは、単体、２つ組、３つ組等の弱分類器１０１について形成される。非線形変換は、
【００２６】
【数５】
2007157130.tif 000007
【００２７】
に従う。式中、Ｐｋ(ωｊ|ｘ)は非線形重みβによる重み付き弱分類器であり、Ｓｎはｎ番目の分類器組み合わせである。組み合わせを網羅的に列挙する場合、あらゆる値のβについての組の総数は以下の関係
【００２８】
【数６】
2007157130.tif 000008
【００２９】
によって与えられる。式中、Ｋは弱分類器数であり、Ｎは組数である。すなわち、６つの分類器の組み合わせの形成に８つの異なる値のβを使用する場合、これらの組み合わせ１０２の総数は５０４になる。
【００３０】
＜ブースティング＞
上述したように、強分類器１０９は組み合わせられた弱分類器１０２のセットから導き出される。ブースティングは本質的に、セット中の、低い「重み」、たとえば或る所定のしきい値又は０より低い重みを有する組み合わせを「破棄」し、所定のしきい値を超える組み合わせを残す。強分類器の要素の数は、しきい値により制御することができる。
【００３１】
この方法は、既知のアダブースト(ＡｄａＢｏｏｓｔ)プロセス(Freund他著「A decision-theoretic generalization of on-line learning and an application to boosting」(Computational Learning Theory, Eurocolt '95, pp. 23-37, 1995))(参照により本明細書に援用する)を採用する。
【００３２】
アダブーストプロセスは、データの難度を上げながら組み合わせ内の各分類器を訓練してから、重み付け得点を使用する。訓練中、組み合わせ分類器を順に交替しながら調べる。反復毎に、欲張り選出(greedy selection)が行われる。前回の反復において誤って分類された、データに対しての誤り率が最小の組み合わせ分類器が選出され、その重みが誤り率の関数として求められる。アダブーストプロセスは、以下の条件が満たされるまで繰り返される。すなわち、所定数の反復が行われた、所定数の分類器が選出された、誤り率が所定のしきい値まで下がるか、又は誤り率をそれ以上に向上させることができない。
【００３３】
形式上、クラスにわたる確率分布は得点の重み付け和
【００３４】
【数７】
2007157130.tif 000009
【００３５】
として表すことができ、式中、重みＷｋはｋ番目の分類器の重みの総計
【００３６】
【数８】
2007157130.tif 000010
【００３７】
である。
【００３８】
この式は、ｋ番目の分類器の重みが、その分類器のすべてのインスタンスｔの重みの和であることを示し、ここで、分類器ｆｋはプロセスによって選出される。
【００３９】
次いで、特徴スタッキング(feature stacking)に、単一のベクトルにまとめられた弱分類器の出力で訓練された強分類器を使用することができる。すなわち、強分類器の入力
【００４０】
【数９】
2007157130.tif 000011
【００４１】
は以下
【００４２】
【数１０】
2007157130.tif 000012
【００４３】
として形成され、強分類器をデータ対(Ｘｉ，Ｙｉ)で訓練する。ここで、Ｙｉはｉ番目のデータポイントのクラスラベルである。
【００４４】
本発明を好ましい実施の形態の例に従って説明したが、本発明の精神及び範囲内で他の種々の適合及び変更を行うことが可能なことを理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内にあるこのような変形及び変更をすべて包含することである。
【図面の簡単な説明】
【００４５】
【図１】本発明の一実施の形態による弱分類器組み合わせから強分類器を構築する方法の流れ図である。
【図１】
2007157130.tif 000018
【外国語明細書】
2007157130.tif 000019
2007157130.tif 000020
2007157130.tif 000021
2007157130.tif 000022
2007157130.tif 000023
2007157130.tif 000024
2007157130.tif 000025
2007157130.tif 000026
2007157130.tif 000027
2007157130.tif 000028
2007157130.tif 000029
2007157130.tif 000030