(57)【要約】      （修正有）【課題】限られたメモリを有するシステムにおいて、トレーニングデータセットを使用してデータを分類する。【解決手段】模範学習（ＥＬ）手順をトレーニングデータセットに適用し、メモリのサイズに適合する模範データセットを生成する。ＥＬ手順は、エントロピーベース模範学習（ＥＢＥＬ）手順と、高度ブロードバンド対応学習（ＡＢＥＬ）手順とから構成されるグループから選択される。模範データセットは、システムデータにより取得され分類するのに用いられる。【選択図】図１
2010067259.tif 000002
【特許請求の範囲】
【請求項１】
限られたメモリを有するシステムにおいてデータを分類する方法であって、
トレーニングデータセットを求めるステップと、
データを記憶するためのメモリのサイズを取得するステップと、
模範学習（ＥＬ）手順を前記トレーニングデータセットに適用して、前記メモリの前記サイズに適合する模範データセットを生成するステップであって、前記ＥＬ手順は、エントロピーベース模範学習（ＥＢＥＬ）手順と、高度ブロードバンド対応学習（ＡＢＥＬ）手順とから構成されるグループから選択される、ステップと、
分類されるデータを取得するステップと、
前記データを前記模範データセットを使用して分類するステップと
を含む、方法。
【請求項２】
前記求めるステップは、
現在の模範データセットを取得すること、
サンプルデータセットを取得すること、
前記現在の模範データセットと、前記サンプルデータセットとを結合して、トレーニングデータセットを生成すること
をさらに含む、請求項１に記載の方法。
【請求項３】
前記現在の模範データセットは最初は空である、請求項２に記載の方法。
【請求項４】
前記ＥＢＥＬ手順は、
前記トレーニングデータセットＳｎ内の各サンプルｘに関して、前記サンプルｘを条件とするクラス変数Ｃの条件付きエントロピー損失Ｈ（Ｃ｜ｘ）を求めるステップと、
前記トレーニングデータセットＳｎから、前記条件付きエントロピーＨ（Ｃ｜ｘ）の最小損失を結果的にもたらす、選択されたサンプルを除去するステップと
をさらに含む、請求項１に記載の方法。
【請求項５】
前記選択されたサンプルは、
【数１】
2010067259.tif 000054
に従って求められる、請求項４に記載の方法。
【請求項６】
前記メモリ制約は、前記模範データセットのサイズｋであり、前記方法は、前記トレーニングデータセットが前記サイズｋに達するまで、前記条件付きエントロピー損失を求めることと前記サンプルｘを除去することとを繰り返すことをさらに含む、請求項４に記載の方法。
【請求項７】
前記条件付きエントロピー損失を求めるステップは、前記トレーニングデータセットの前記サンプルの対ごとのカーネル値を使用する、請求項４に記載の方法。
【請求項８】
前記ＡＢＥＬ手順は、
検証データセット
【数２】
2010067259.tif 000055
を前記トレーニングデータセットから抽出するステップと、
前記トレーニングデータセットＳｎ内の各サンプルｘに関して、サブセット
【数３】
2010067259.tif 000056
の受信者動作曲線下面積（ＡＵＣ）を求めるステップと、
前記トレーニングデータセットから、前記ＡＵＣの最小損失に対応するサンプルｘを除去するステップと
をさらに含む、請求項１に記載の方法。
【請求項９】
前記除去するステップは
【数４】
2010067259.tif 000057
に従い、ここで、
【数５】
2010067259.tif 000058
は、前記検証データセット
【数６】
2010067259.tif 000059
及び前記トレーニングデータセットＳｎのサンプルｘに関して求められる前記ＡＵＣであり、Ｓｎ−１は、前記除去するステップ後の新しいトレーニングデータセットである、請求項８に記載の方法。
【請求項１０】
前記検証データセットのサイズは、前記トレーニングデータセットのサイズの０．１に等しい、請求項８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはデータの分類に関し、より詳細には限られたメモリを有するシステムにおけるデータの分類に関する。
【背景技術】
【０００２】
データ分類
データ分類は、或るデータ項目から抽出される何らかの定量的情報と、既にラベリングされた項目のトレーニングセットとに基づいて所定のラベルをこのデータ項目に割り当てる。たとえば、電子メール分類システムは、特定の電子メールを、電子メールの内容と、「スパム」又は「非スパム」と知られている電子メールのトレーニングデータセットとに基づいて、「スパム」又は「非スパム」にラベリングすることができる。分類器の性能は、分類されるデータの特性に大きく依存する。全ての分類問題に対して最良に動作する単一の分類器は存在しない。性能はまた、トレーニングデータの質に依存する。良好にトレーニングされる分類器は、様々な特性を有するラベリングされたサンプルを有する、大規模なトレーニングデータセットを必要とする。
【０００３】
分類器は、データ項目から情報を抽出するのに使用される数学的モデル、トレーニングデータの量、及びモデルの計算量に基づいて様々であり得る。分類器の選択は多くの場合、データ特性と、たとえばＣＰＵ使用量及びメモリ要件のような、自身の計算資源要件とに依存する。たとえば、幾つかの分類器は、カテゴリ化の結果がリアルタイムで必要とされる場合に適切でない場合がある。
【０００４】
組み込みシステム
組み込みシステムは通常、或る他の装置又は機械に一体化される。組み込みシステムは、専用機能を多くの場合リアルタイムで実行するように設計されることがある。組み込みシステムは、ポータブルビデオプレーヤ、カメラ、信号機、工場のコントローラ、及び監視システムのような多数の装置に普及している。多数の組み込みシステムが専用機能を実行するため、組み込みシステムは、サイズ、コスト、信頼性、及び性能に関して最適化される場合がある。
【０００５】
センサを備えると共に分類を実行する組み込みシステムは、トレーニングデータを使用してトレーニングすることができる。トレーニングされた組み込みシステムは、機能及び性能が向上し得る。たとえば、カメラ上の分類器は、「立入禁止」監視エリア内での侵入者の存在を警告することができる。しかしながら、組み込みシステムは典型的には、メモリが限られており、大規模なトレーニングデータセットを記憶することができない。
【０００６】
メモリが限られているという問題に対する１つの解決策は、有効な分類に十分な、トレーニングデータから入念に選択される少量の「模範」のみを記憶するということである。本明細書で定義される場合、模範は、或る大規模なトレーニングデータセットの特徴を示すサンプルデータである。
【０００７】
模範学習（ＥＬ）方法
模範学習（ＥＬ）方法を使用して、トレーニングデータの小規模なセットを大規模なトレーニングデータセットから選択することができる。ＥＬは、その名前が暗示しているように、模範によって学習する。すなわち、分類器のエラー率を低減する「良好な」サンプルを保持し、「劣った」サンプルを破棄する。したがって、ＥＬを使用して、メモリが限られている組み込みシステム内のメモリベース分類器のために、小規模なトレーニングデータセットを生成することができる。
【０００８】
従来のＥＬ方法は、或る近傍構造に基づいて模範を学習する。そして、この方法は、従来の誤分類率を使用して、サンプルが除去されることによる性能の損益を測定する。
【０００９】
ＥＬ方法は、サンプルが処理されるのにつれて、連続してトレーニングデータセットを調整することができる、すなわち、良好な新しいサンプルを保持して、劣った新しいサンプルを破棄する。したがって、分類器は、組み込みシステムが動作する環境の変化に対して動的に適応することができる。ほぼ全てのＥＬ方法は、以下の仮説に基づいてサンプルを破棄する。
【００１０】
仮説０（Ｈ０）：所与のトレーニングデータセット内でのサンプルの除去が、残りのサンプルの誤分類又はエラー率を増大しない場合、サンプルを破棄することができる。
【００１１】
ＥＬ方法は幾つかの欠点を有する。
【００１２】
インクリメンタル更新
従来のＥＬ方法は、計算集約的であり、オフラインであり、且つ全くインクリメンタルでない。従来のＥＬ方法は、トレーニングデータセット全体が、模範ＥＬ方法の実行全体を通じてメモリに記憶されることを必要とする。これは、これらの方法を、メモリが限られており且つトレーニングデータが定期的に更新される組み込みシステムに適用不可能にする。
【００１３】
クラス不均衡
仮説Ｈ０において使用される誤分類率は、クラス不均衡に鈍感である。この問題は、サンプルの除去がクラス集合を変化させるＥＬにおいて重大である。たとえば、９０個の正クラスサンプル及び１０個の負クラスサンプルを有するセットにおいて、１つの正クラスサンプルを除去することは、９回の正サンプル誤分類及び１回の負サンプル誤分類をもたらし、一方、１つの負サンプルを破棄することは、１回の正サンプル誤分類及び９回の負サンプル誤分類をもたらす。
【００１４】
エラー率が両方の場合で同じである、すなわち１０％であるため、クラス不均衡によって、負サンプルが破棄されて、正クラスサンプルのみがトレーニングデータセット内に残るおそれがある。
【００１５】
より良好な結果を生成するために、全体の分類精度とは対照的な、２つのクラスを区別する分類器の能力の推定値を提供するＥＬ方法を有することが望ましい。
【００１６】
順序除去
順序除去手順のほとんどは、アドホックであるか、又は、サイズが実行時間中に確定されるトレーニングデータセットを返す。これらの方法は、サンプルの順序除去を無視し、それによって所与のメモリサイズに最良のトレーニングデータセットを発見する。典型的には組み込みシステムにおいて見られるような所定のメモリサイズ制約を満たす最適なトレーニングデータセットを生成するＥＬ方法を有することが望ましい。
【００１７】
検証整合性
従来のＥＬ方法は、トレーニングデータセット内に残っているサンプルの分類エラー率が増大しない場合、サンプルを除去する。したがって、サンプルは２重の役割を果たす。すなわち、サンプルは、トレーニングデータセットの更新、及び分類されるセットの検定の両方に参加する。除去が進行するにつれて、トレーニングデータセットのサイズ及び性質が動的に変化し、したがって、一貫していなく且つ統計的有意性がより低い異なるセットにわたってエラー率が求められる。除去プロセス中に変化しないトレーニングデータセットとは互いに素である別個の検証データセットを有することが望ましい。
【発明の概要】
【００１８】
本発明の実施の形態は、データサンプルを分類する方法及びシステムを提供する。より詳細には、サンプルは、メモリが限られている組み込みシステム内のセンサによって検知される。したがって、この方法は、メモリのサイズに一致している所定のサイズの模範データセットを構築する。
【００１９】
一実施の形態では、この方法は、トレーニング中に変化しないままであるトレーニングデータセットと、このトレーニングデータセットとは互いに素である検証データセットとを使用する。
【００２０】
本発明の一実施の形態は、エントロピーベース模範学習（ＥＢＥＬ）手順を使用する。ＥＢＥＬ手順は、エラー率を使用する代わりに、トレーニングデータセットの情報内容に基づいてトレーニングデータセットからサンプルのインスタンスを除去する。
【００２１】
アドホック順位付けスキームを使用する代わりに、ＥＢＥＬ手順は、除去することによってクラス指示変数の条件付エントロピーの低減が最小化するトレーニングデータインスタンスを除去する。これによって、情報の損失が最小化される。ＥＢＥＬ方法は、低い計算オーバヘッドを有し、順序除去を提供し、クラス不均衡に敏感ではない。
【００２２】
本発明の別の実施の形態は、高度ブロードバンド対応学習（advanced broadband enabled learning）（ＡＢＥＬ）手順を使用して、受信者動作特性曲線下面積（ＡＵＣ）を使用し、ＡＢＥＬ手順はＡＵＣの成果（performance）に基づいてサンプルを除去する。ＡＢＥＬ手順は、検証データセットを使用し、サンプルの除去が検証データセットにわたって求められるＡＵＣを低減しない場合に当該サンプルを除去する。
【発明の効果】
【００２３】
本発明の実施の形態は、模範データセットを求めるためのＥＢＥＬ手順及びＡＢＥＬ手順を記載し、これらの手順は、メモリが限られている組み込みシステムにおけるデータ分類に使用することができる。ＥＢＥＬ手順及びＡＢＥＬ手順は、新しいトレーニングデータセットによって効率的に更新することができると同時に、任意のユーザ定義サイズを有する高品質模範データセットを維持する。
【図面の簡単な説明】
【００２４】
【図１】本発明の実施の形態による、データを分類する方法及びシステムのブロック図である。
【図２】本発明の一実施の形態による、模範データセットを求める方法及びシステムのブロック図である。
【図３】本発明の一実施の形態による、ＥＢＥＬ手順の擬似コードである。
【図４】本発明の一実施の形態による、ＡＢＥＬ手順の擬似コードである。
【発明を実施するための形態】
【００２５】
図１は、本発明の実施の形態による模範学習（ＥＬ）を使用して入力信号１０１を分類する方法及びシステム１００を示す。システムは、或る他の機械又は装置１０５内に組み込まれるか、又は依存せずに動作することができる。システム１００は、限られたサイズのメモリ１３０を有する。入力信号１０１を、リアルタイムでセンサ１１０によって取得し、分類する（１４０）。
【００２６】
センサ１１０は、信号１０１を環境１０３から取得する。本発明において、用語「環境」は概して、検知することができるあらゆるもの、たとえば温度、圧力、湿度、気体、液体、固体、機械、音響及びＥＭ波形、カメラ画像等を意味するように使用される。典型的には、環境は、システム１００が組み込まれる装置１０５の動作に関連する。センサはデータ１０２を生成する。
【００２７】
データ１０２を、分類して（１４０）、データ分類出力１４５を生成する。データ分類１４０は、プロセッサ１５０によって実行することができる。データ分類１４０は、模範データセット１３５を使用して、データ１０２を分類する。模範データセット１３５は、サイズが限られているメモリ１３０、すなわち所定の小さいサイズを有するメモリ内に記憶される。したがって、模範データセット１３５のサイズは、メモリのサイズに従ってメモリ１３０に適合するようになっている。
【００２８】
模範データセットを求めること
図２は、本発明の一実施の形態に従って模範データセット１３５を求める方法及びシステム２００のブロック図を示す。模範データセット１３５はさらに、データ分類１４０のための方法及びシステム１００において利用される。
【００２９】
本発明の実施の形態は、模範データセット１３５を学習する（２１０）ために、エントロピーベースＥＬ（ＥＢＥＬ）手順又はＡＵＣベースＥＬ（ＡＢＥＬ）手順を使用することができる。ＥＬ手順２１０は、システム１００の限られたメモリサイズｋ  ２２０に従って、トレーニングデータセット２３０から模範データセット１３５を学習する。
【００３０】
トレーニングデータセット２３０を、サンプルデータセット２６０及び現在の模範データセット２５０から求める（２４０）。本発明の一実施の形態では、本明細書で説明される場合、求めること（２４０）は、サンプルデータセット２６０と現在の模範データセット２５０とを組み合わせる。
【００３１】
サンプルデータセット２６０は、トレーニングデータセット２３０を求めるためのデータサンプルを含む。サンプルデータセット２６０は、幾つかのアプリケーションによって生成することができるか、又は、センサ１１０によって生成されるデータ１０２から構築することができる。サンプルデータセット２６０は１つ又は複数のデータサンプルを含むことができる。
【００３２】
システム及び方法２００は、模範データセット１３５を開始及び更新する。開始中、現在の模範データセット２５０は空であり、トレーニングデータセット２３０は、サンプルデータセット２６０のみから求められる（２４０）。更新中、現在の模範データセット２５０は、前に求められた模範データセット１３５である。
【００３３】
従来のＥＬ手順とは対照的に、トレーニングデータセット２３０を、前に得られたトレーニングデータセットを使用して求める必要はない。
【００３４】
パーゼンカーネル密度推定ベース（ＰＫＤＥ）分類器
本発明の分類器１４０は、パーゼンカーネル密度推定（ＰＫＤＥ）分類器を使用する。ＰＫＤＥ分類器は、非パラメトリックにランダム変数の確率密度関数（ｐｄｆ）を推定する。しかしながら、本発明は、任意の分類器に関して一般化することもできる。
【００３５】
所与のクラスｃ及びｎ個のサンプルから成るトレーニングセットＳｎに関して、サブセットＺｃｎは以下の通りである。
【００３６】
【数１】
2010067259.tif 000003
【００３７】
ＰＫＤＥ分類器に関して、カーネル関数κは帯域幅λを有する。トレーニングサブセットＳｎに関して、クラスｃに属するサンプルｘの密度推定値ｆは以下の通りである。
【００３８】
【数２】
2010067259.tif 000004
【００３９】
ここで、ｙはＺｃｎ内のサンプル要素である。
【００４０】
各クラスの事前確率πｎｃは以下の通りである。
【００４１】
【数３】
2010067259.tif 000005
【００４２】
トレーニングデータセットＳｎが与えられると、特定のクラスｃに属する任意のサンプルｘの事後確立ｐを以下のように求めることができる。
【００４３】
【数４】
2010067259.tif 000006
【００４４】
２値分類問題では、２つのクラスがＣ＋及びＣ−で表される場合、トレーニングデータセットＳｎが与えられると、サンプルｘのメリットスコア（merit score）γｎ（ｘ）は以下の通りである。
【００４５】
【数５】
2010067259.tif 000007
【００４６】
メリットスコアを使用して、受信者動作特性曲線下面積（ＡＵＣ）又は閾値選択を使用して、分類の精度を分析することができる。
【００４７】
模範学習
本発明では、トレーニングデータセットを、
【００４８】
【数６】
2010067259.tif 000008
【００４９】
となるように、
【００５０】
【数７】
2010067259.tif 000009
【００５１】
で表す。ここで、Ｎはトレーニングデータセット内のサンプル数である。ｎ個のサンプルを有するトレーニングサブセットは、
【００５２】
【数８】
2010067259.tif 000010
【００５３】
且つ
【００５４】
【数９】
2010067259.tif 000011
【００５５】
となるようなＳｎである。トレーニングサブセットＳｎが与えられると、本発明の実施の形態は、Ｓｎ＋１からＳｎへの移行における分類精度の低減が所定の閾値未満となるように、インクリメンタルに、除去されるサブセットを求める。
【００５６】
【数１０】
2010067259.tif 000012
【００５７】
単純な従来の解決策は、全てのサブセットの全ての可能な組み合わせを発見し、最良の成果を有するサブセットを選択し、これは、計算量Ｏ（２Ｎ）を有する。
【００５８】
本発明の実施の形態は、ＳｎからＳｎ−１を効率的に得るインクリメンタル解決策を使用する。
【００５９】
エントロピーベース模範学習（ＥＢＥＬ）方法
トレーニングデータセット２３０内の各サンプル
【００６０】
【数１１】
2010067259.tif 000013
【００６１】
に関して、ＥＢＥＬは、サブセット
【００６２】
【数１２】
2010067259.tif 000014
【００６３】
をトレーニングデータセット２３０として且つｘを検定サンプルとして使用して、クラス変数の条件付きエントロピー損失を求める。ＥＢＥＬは、条件付きエントロピーにおける低減が最小化されるように、選択を行い、選択されたサンプルを除去する。
【００６４】
Ｃがクラスであり、ｐ（ｘ）がトレーニングインスタンスｘに関する事前確率であり、且つＨ（Ｃ｜ｘ）が、インスタンスｘの存在を条件とするクラス変数のエントロピーである場合、ＥＢＥＬは以下に従って選択を行い、選択されたサンプルを除去する。
【００６５】
【数１３】
2010067259.tif 000015
【００６６】
トレーニングデータセットは独立同一分布（Ｉ．Ｉ．Ｄ．）であるため、任意のサンプルインスタンスに関する事前確率ｐ（ｘ）は一定であり、無視することができる。分類器
【００６７】
【数１４】
2010067259.tif 000016
【００６８】
の分類エラーは以下のように、条件付エントロピーによって下方の境界を形成される。
【００６９】
【数１５】
2010067259.tif 000017
【００７０】
したがって、最小条件付エントロピーを有するサブセットを選択することは、分類精度を低減する可能性が最も低い。
【００７１】
本発明の実施の形態は、除去に最も適切な候補サンプルを効率的に求める。トレーニングデータセットの対ごとのカーネル値の和のみを記憶することによって、除去されるサンプルをＯ（Ｎ）時間内に発見することができる。
【００７２】
トレーニングサブセットＳｎが与えられると、以下のように、各サンプル
【００７３】
【数１６】
2010067259.tif 000018
【００７４】
の、クラス内の全ての他のサンプルとのカーネル値の和を記憶する。
【００７５】
【数１７】
2010067259.tif 000019
【００７６】
そして、各インスタンス
【００７７】
【数１８】
2010067259.tif 000020
【００７８】
を有するクラス出力変数の条件付エントロピーを以下のように得ることができる。
【００７９】
【数１９】
2010067259.tif 000021
【００８０】
インスタンスｙを、式（６）を使用して除去のために選択する場合、ｖ行列は以下のように更新することができる。
【００８１】
【数２０】
2010067259.tif 000022
【００８２】
トレーニングデータセット２３０
【００８３】
【数２１】
2010067259.tif 000023
【００８４】
に関して、カーネル帯域幅は、たとえば、平均２乗誤差（ＭＳＥ）を最小化する従来の帯域幅最適化スキームを使用して得られる。サンプルの密度
【００８５】
【数２２】
2010067259.tif 000024
【００８６】
がｒ次において連続し且つサンプルサイズと共に変化しない場合、ＭＳＥを最小化する最適な帯域幅λ（ｎ）は以下のようにサンプルサイズｎに関連する。
【００８７】
【数２３】
2010067259.tif 000025
【００８８】
ここで、ｋｒはカーネル関数ｋ（．）の特有の成分である。ｒ＝２の場合、サイズｎのサンプルの最適な帯域幅は、
【００８９】
【数２４】
2010067259.tif 000026
【００９０】
である。ここで、λ（Ｎ）は、サイズＮのトレーニングデータセットを使用して得られる帯域幅であり、この帯域幅はＭＳＥを最小化する。これは、サンプルサイズの変化に伴って著しい計算量で帯域幅最適化を繰り返すことを防止するが、帯域幅更新は依然として、式（１０）におけるｖ行列の再計算を必要とする。帯域幅はｎ−０．２のようにサンプルサイズと共にゆっくりと変化するため、
【００９１】
【数２５】
2010067259.tif 000027
【００９２】
のとき、ｖ行列を定期的に更新する。ここで、Ｎｌａｓｔは、最後の帯域幅更新が生じたときのサンプルのサイズであり、αは、ユーザ指定の感度パラメータである。
【００９３】
ＥＢＥＬ手順におけるインクリメンタルステップの計算量は、トレーニングデータセット２３０のサイズにおいて線形である。したがって、サイズＮのトレーニングデータセット２３０からサイズｋの模範データセット１３５を得るためのＥＢＥＬ手順の実行時計算量は、Ｏ（（Ｎ−ｋ）α２Ｎ）である。
【００９４】
図３は、本発明の一実施の形態によるＥＢＥＬ手順の擬似コードを示す。システムが既に分類１４０のための現在の模範データセット２５０
【００９５】
【数２６】
2010067259.tif 000028
【００９６】
を使用しており且つサンプルデータセット２６０
【００９７】
【数２７】
2010067259.tif 000029
【００９８】
によって更新されている場合、学習ステップ２１０におけるＥＢＥＬ方法は、｜Ｓ｜＝ｋとなるような模範データセット１３５  Ｓを発見する。所望の模範セットのサイズｋはメモリ制約２２０によって左右される。
【００９９】
【数２８】
2010067259.tif 000030
【０１００】
に対応する帯域幅値λはオフラインで得られる。初期段階中、
【０１０１】
【数２９】
2010067259.tif 000031
【０１０２】
及び
【０１０３】
【数３０】
2010067259.tif 000032
【０１０４】
と設定することによって、サイズｋの模範データセット１３５をサンプルデータセット
【０１０５】
【数３１】
2010067259.tif 000033
【０１０６】
から得る。
【０１０７】
ＥＢＥＬ手順はまず、図３のステップ１に示されているように、現在の模範データセット２５０
【０１０８】
【数３２】
2010067259.tif 000034
【０１０９】
及びサンプルデータセット２６０
【０１１０】
【数３３】
2010067259.tif 000035
【０１１１】
の両方からのデータを結合し、これに応じて対応するカーネル帯域幅を更新する。
【０１１２】
ｖ行列を計算した後、ＥＢＥＬ手順は、サイズが所望の値ｋに達するまで、トレーニングデータセット２３０  Ｓのサイズを低減する。トレーニングデータセット２３０のインスタンスはステップ４〜８において１つずつ除去され、ステップ９〜１２において、サンプルサイズが感度パラメータαによって可能にされるサイズよりも小さくなる場合、ｖ行列が更新される。結果的に得られる模範データセット１３５  Ｓは、現在の模範データセット２５０
【０１１３】
【数３４】
2010067259.tif 000036
【０１１４】
に取って代わり、検知されたデータ１０２を分類する（１４０）のに使用される。
【０１１５】
ＡＵＣベース模範学習（ＡＢＥＬ）方法
ＡＢＥＬ手順は、一貫した検証データセットにわたるＡＵＣ成果と、保持されているサンプルとの間の依存関係に基づいて、トレーニングデータセットのサンプルを除去することによって検証整合性の問題に対処する。したがって、サンプルは、除去されない限りにおけるトレーニングサンプルの役割と、式（６）の条件付確率を求めるときの検定サンプルの役割とから成る２重の役割を有する。
【０１１６】
ＡＢＥＬ手順の異なる段階において、成果が検証される、すなわち異なるデータセットに関してエントロピーが求められ、それによって結果の統計的有意性が低減する。
【０１１７】
ＡＢＥＬ手順では、検証データセットは、除去動作の最初においてトレーニングデータセットから抽出され、トレーニングデータセットのサンプルは、ＡＵＣ成果が低減し、除去数の結果として最小化されるように除去される。
【０１１８】
【数３５】
2010067259.tif 000037
【０１１９】
となるように、トレーニングデータセット２３０  Ｓｎ及び検証データセットＶが与えられると、ＡＢＥＬ手順は、以下に従ってサンプルｘを除去する。
【０１２０】
【数３６】
2010067259.tif 000038
【０１２１】
ここで、
【０１２２】
【数３７】
2010067259.tif 000039
【０１２３】
は、検定のためにセットＸを使用すると共にトレーニングデータセットとしてセットＹを使用するＡＵＣ値である。ＡＢＥＬ手順は、任意の分類器に一般化される、単純な、しかし有効なＥＬフレームワークを提供する。
【０１２４】
検証データセット内のサンプルのメリットスコアが与えられると、
【０１２５】
【数３８】
2010067259.tif 000040
【０１２６】
時間内で、実際にＲＯＣ曲線を生成することなくＡＵＣが求められる。しかしながら、サンプルの有限のセットの場合、ＡＵＣは、既知の正規化ウィルコクソン・マン・ホイットニー（ＷＭＷ）統計値
【０１２７】
【数３９】
2010067259.tif 000041
【０１２８】
に等しい。
【０１２９】
【数４０】
2010067259.tif 000042
【０１３０】
ここで、
【０１３１】
【数４１】
2010067259.tif 000043
【０１３２】
は正クラスのメリットスコアであり、
【０１３３】
【数４２】
2010067259.tif 000044
【０１３４】
は
【０１３５】
【数４３】
2010067259.tif 000045
【０１３６】
における負クラスサンプルのメリットスコアである。
【０１３７】
この統計値は、２つのサンプルが同じ分布に由来するか否かを判定するために非パラメトリック検定を使用する。
【０１３８】
統計値
【０１３９】
【数４４】
2010067259.tif 000046
【０１４０】
は、Ｐ（Γ＋＞Γ−）の推定量である、すなわち、全ての正クラスサンプルが負クラスサンプルより高いメリットスコアを得る確率であり、全てのメリットスコアを、ｒｉがγ＋ｉの順位となるように非減少順にソートする場合、
【０１４１】
【数４５】
2010067259.tif 000047
【０１４２】
は、以下にさらに簡約することができる。
【０１４３】
【数４６】
2010067259.tif 000048
【０１４４】
式（１５）は、検証データセットのメリットスコアが与えられると、ＡＵＣ値を
【０１４５】
【数４７】
2010067259.tif 000049
【０１４６】
時間内に求めることができることを示す。
【０１４７】
【数４８】
2010067259.tif 000050
【０１４８】
が、分類器
【０１４９】
【数４９】
2010067259.tif 000051
【０１５０】
が、トレーニングデータセット
【０１５１】
【数５０】
2010067259.tif 000052
【０１５２】
を使用して検定サンプルを分類するのに要する時間である場合、ＡＢＥＬの実行時計算量は
【０１５３】
【数５１】
2010067259.tif 000053
【０１５４】
である。
【０１５５】
図４は、本発明の一実施の形態によるＡＢＥＬ手順の擬似コードを示している。ＡＢＥＬ手順はまず、検証データセットの部分サイズ（η）が入力パラメータとして与えられると、検証データセットをトレーニングデータ２３０から抽出し（ステップ２）、その後、トレーニングデータセット２３０の残りのサンプルからインスタンスを除去する（ステップ３〜６）。部分サイズ（η）の最適値は、メモリのサイズと、分類１４０の計算量とに依存する。サイズηの大きな値が結果的に高メモリオーバヘッドをもたらす一方、小さな値は、検証データセット要素のＡＵＣスコアの統計的有用性を低減し、より劣ったインスタンス除去決定を結果的にもたらす。本発明の一実施の形態はη＝０．１を使用する。
【０１５６】
様々な他の適合及び変更を本発明の精神及び範囲内で行うことができることを理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内に入る全てのそのような適合及び変更を包含することである。
【図１】
2010067259.tif 000060
【図２】
2010067259.tif 000061
【図３】
2010067259.tif 000062
【図４】
2010067259.tif 000063
【外国語明細書】
2010067259.tif 000064
2010067259.tif 000065
2010067259.tif 000066
2010067259.tif 000067
2010067259.tif 000068
2010067259.tif 000069
2010067259.tif 000070
2010067259.tif 000071
2010067259.tif 000072
2010067259.tif 000073
2010067259.tif 000074
2010067259.tif 000075
2010067259.tif 000076
2010067259.tif 000077
2010067259.tif 000078
2010067259.tif 000079
2010067259.tif 000080
2010067259.tif 000081
2010067259.tif 000082
2010067259.tif 000083
2010067259.tif 000084
2010067259.tif 000085
2010067259.tif 000086
2010067259.tif 000087
2010067259.tif 000088