(57)【要約】      （修正有）【課題】分類器をトレーニングするために、大量のラベル付きトレーニングデータを必要としない能動学習法を提供する。【解決手段】終了条件に達するまで、以下のステップを繰返し実行することによってマルチクラス分類器をトレーニングする。ラベル無しデータのアクティブプールから得られるラベル無しデータのためのクラスメンバーシップの確率が推定される。最も大きな確率と、２番目に大きな確率との間の差が求められる。最も小さな差を有するラベル無しデータが選択され、ラベル付けされ、分類器をトレーニングするためのトレーニングデータセットに追加される。【選択図】図１
2010231768.tif 000002
【特許請求の範囲】
【請求項１】
マルチクラス分類器をトレーニングする方法であって、該マルチクラス分類器は、終了条件に達するまで該方法のステップを繰返し実行するためのプロセッサを備え、該方法は、
ラベル無しデータのアクティブプールから得られるラベル無しデータのためのクラスメンバーシップの確率を推定するステップと、
最も大きな確率と２番目に大きな確率との間の差を求めるステップと、
最も小さな差を有する前記ラベル無しデータを選択するステップと、
前記選択されたラベル無しデータにラベル付けするステップと、
前記ラベル付けされたデータをトレーニングデータセットに追加するステップと、
前記トレーニングデータセットを用いて前記分類器をトレーニングするステップとを含む、マルチクラス分類器をトレーニングする方法。
【請求項２】
前記分類器は、ラベル付きデータのシードセットを用いてトレーニングされる、請求項１に記載の方法。
【請求項３】
前記シードセットは、前記ラベル付きデータの２つのサンプルを含む、請求項２に記載の方法。
【請求項４】
前記トレーニング後に、テストデータセットを用いて前記分類器の性能を評価することであって、前記終了条件が満たされたか否かを判断することをさらに含む、請求項１に記載の方法。
【請求項５】
前記マルチクラス分類器は、サポートベクトルマシンを使用する、請求項１に記載の方法。
【請求項６】
前記クラスの数は未知である、請求項１に記載の方法。
【請求項７】
前記推定するステップは、シグモイド関数を使用する、請求項１に記載の方法。
【請求項８】
サンプルｘの確率は、
【数１】
2010231768.tif 000008
であり、ただし、ｆ（ｘ）は決定関数であり、Ａ及びＢは推定されるパラメータである、請求項１に記載の方法。
【請求項９】
前記パラメータを推定することは、以下の式に従って、最尤推定を用いて前記パラメータについて解くことを含み、
【数２】
2010231768.tif 000009
ただし、ｌは前記アクティブプール内のサンプルの数であり、ｔは正及び負のラベル付き例の重要度を調整するためのサンプル毎のパラメータであり、ｍｉｎは最も小さな値を選択する関数であり、ｉは前記トレーニングデータセット内のサンプルの数であり、
【数３】
2010231768.tif 000010
Ｎｐ及びＮｎはそれぞれ、前記トレーニングデータセット内の正のサンプル１０３及び負のサンプル１０４である、請求項８に記載の方法。
【請求項１０】
前記最尤は、ニュートンの勾配法及び後戻り直線探索を用いて求められる、請求項９に記載の方法。
【請求項１１】
前記サポートベクトルマシンによる比較はペアワイズである、請求項５に記載の方法。
【請求項１２】
前記クラスの数はｋであり、前記トレーニングデータセット内のサンプル数はＩであり、クラスメンバーシップの離散エントロピーＹは、
【数４】
2010231768.tif 000011
である、請求項８に記載の方法。
【請求項１３】
前記クラスの数は１００よりも大きく、前記トレーニングデータセット内のサンプル数は６０００よりも大きい、請求項６に記載の方法。
【請求項１４】
前記トレーニング後に、妥当性検証データセットを用いて前記分類器の性能を評価することであって、前記終了条件が満たされたか否かを判断することをさらに含む、請求項１に記載の方法。
【請求項１５】
前記終了条件として成熟度スコアを評価することをさらに含む、請求項１に記載の方法。
【請求項１６】
固定数の最新のトレーニングサイクルにわたって、新たに見つけられたクラスの数の比を求めること、及び
前記成熟度スコアとして前記比の逆数を割り当てることをさらに含む、請求項１５に記載の方法。
【請求項１７】
固定数の最新のトレーニングサイクルにわたって、前記最も小さな差の平均スコアを求めること、及び
前記成熟度スコアとして前記平均スコアを割り当てることをさらに含む、請求項１５に記載の方法。
【請求項１８】
前記トレーニングされた分類器を前記妥当性検証データ又は前記テストデータに適用すること、
ラベルを用いて、正確に分類されたサンプルの比を計算すること、
成熟度スコアとして、前記正確に分類されたサンプルの比を割り当てること、及び
前記終了条件として前記成熟度スコアを評価することをさらに含む、請求項１４に記載の方法。
【請求項１９】
ラベル付きシードデータを用いて前記トレーニングデータを初期化することをさらに含む、請求項１に記載の方法。
【請求項２０】
前記シードデータセットは２つのラベル付きサンプルを含む、請求項１９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はマルチクラス分類器をトレーニングすることに関し、より詳細には、能動学習を用いて分類器をトレーニングすることに関する。
【背景技術】
【０００２】
画像内の物体のような物体を分類するための大部分の方法は、ラベル付きトレーニングデータを用いてトレーニングされる統計モデルを使用する。典型的には、受動学習法は、選択されたトレーニングデータをランダムに受け入れる。しかしながら、大量のラベル付きトレーニングデータセットを与え、ラベル付けすることは時間がかかり、その一方で、ラベル付きトレーニングデータセットの数が少ないと分類の精度が低下する。
【０００３】
能動学習では、その方法は、ランダムに選択されたデータを受動的に受け入れる代わりに、ユーザがラベル付けするのに「有用な」データを選択する。能動学習は、受動学習と同程度の分類精度を達成しながら、受動学習と比べて要求されるトレーニングデータの量を著しく少なくすることができる。
【０００４】
能動学習の重要な概念は、疎な解を有する分類器の場合に特に、全てのデータが、その分類器に対して等しい値を有するとは限らないことである。たとえば、サポートベクトルマシン（ＳＶＭ）分類器の場合、その分類は、分離超平面のサポートベクトルを除く全てのトレーニングデータが省略されるときに同じである。したがって、サポートベクトルは超平面を定義し、他の全てのデータは不要である。
【０００５】
１つの能動学習法は、画像を探索するために、関連するフィードバックフレームワークにおいてＳＶＭを用いることである。その方法は、ラベル無しの例の場合のマージンを当てにしており、２クラス分類器の場合にのみ有効である。
【０００６】
別の能動学習法は、反復する度にバージョン空間を最小にする。バージョン空間は、トレーニングデータと一致する全ての仮説を含む部分集合である。しかしながら、この方法もマルチクラスの事例に容易に拡張することはできない。
【０００７】
別の方法は、能動学習のためにガウス過程を使用する。この方法は、ガウス過程回帰を通して得られる、複数の例の不確定推定値を基にしており、ガウス過程回帰は計算に費用がかかり（Ｏ（Ｎ３））、トレーニング例の数に関して３次である。この方法は、ワン・バーサス・オール（one-versus-all）ＳＶＭ定式化を用いて、マルチクラス分類を処理する。この能動学習法は主に２値分類を目的とするので、マルチクラス問題を組み入れるために、その方法は、一巡する度に分類器当たり１つの例を追加する。
【０００８】
マルチクラスの状況における能動学習のための別の方法は、アクティブプールからランダムな例を追加した後にシステムの予想されるエントロピーを最小にする例を見つける。Holub他著「Entropy-based active learning for object recognition」（CVPR, Workshop on Online Learning for Classification, 2008）を参照されたい。基本的には、その方法は、エントロピーを最小にするために未知のラベルついての最も多くの情報を入手しようと試みるので、情報ベースの手法である。これは計算負荷が極めて高い。この方法は、ラベル無し画像の数Ｎ及びクラスの数ｋの両方に関して時間３次式である。すなわちＯ（ｋ３Ｎ３）である。
【０００９】
画像探索のタスクの場合に、ＳＶＭを用いるバッチモードにおける能動学習が記述されている。その方法は、最適フレームワークを通して反復する度に、多数の画像の選択を明示的に処理する。その方法は画像探索を目的とするので、主な分類タスクは２値であり、すなわち、画像が問い合わせ画像のクラスに属するか否かを判断することである。
【００１０】
確信度ベース能動学習法は、各例の不確定の測定基準として条件付きエラーを用いる。しかしながら、この方法は、２値分類問題にのみ焦点を合わせる。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
従来の分類器をトレーニングするには、大量のラベル付きトレーニングデータを必要とする。このトレーニングデータを準備するのは時間がかかる。本発明の実施の形態は、能動学習法を提供する。ランダムなトレーニングデータを受動的に受け入れる代わりに、この能動学習法は、ユーザがラベル付けするために、ラベル無しデータを繰返し選択するので、その努力は最も有用なデータにラベル付けすることに集中する。
【課題を解決するための手段】
【００１２】
本方法は不確定サンプリングを使用し、分類するのが「最も困難である」ラベル無しデータのみが選択される。大部分の従来の方法とは異なり、本方法は、計算が効率的であり、多数のクラスを容易に取り扱うことができる。
【００１３】
本方法では、クラスの数を予め知る必要はない。本方法は、トレーニングデータを正確に分類する確率を推定することに基づいて、トレーニングデータを選択する。本方法は、クラスの数が予め分かっていない場合がある現実世界の問題において極めて重要であり得る。本方法はクラスの数を基にしないので、時間と共にクラスの数を増やすことができる。本方法は、ランダムに選択する場合よりも必要とされるトレーニングデータの数を減らし、また同程度の分類精度を達成する。
【発明の効果】
【００１４】
本発明の実施の形態は、マルチクラス分類のための能動学習法を提供する。本方法では、クラスの全数を知る必要はない。本方法は、クラスの数が多く、且つデータサイズが大きい場合に効率的である。
【図面の簡単な説明】
【００１５】
【図１】マルチクラス分類器をトレーニングする方法の流れ図である。
【図２Ａ】１０クラス問題において２つのラベル無しの例の場合に推定される確率分布のグラフである。
【図２Ｂ】１０クラス問題において２つのラベル無しの例の場合に推定される確率分布のグラフである。
【図３】本発明の実施の形態による、クラスの関数としての選択時間のグラフである。
【発明を実施するための形態】
【００１６】
プールベース学習
図１は、本発明の実施の形態による包括的な方法を示す。この方法のステップは、適当なメモリを有するプロセッサ１０において実行される。プールベース学習は能動学習において一般的である。シードデータセット１０６と呼ばれる、ランダムに選択された少数のラベル付きデータセットを用いて、分類器をトレーニングする（１５０）。２つのサンプルで十分である。その後、この能動学習法は、アクティブプール１００のラベル無しデータから、ラベル付けするのに有用なデータ１３３を選択する。必要に応じて、そのプールに新たなデータ９９を追加することができる。本発明は、分類器の分類精度を向上させるデータを参照するために、用語「有用な」を用いる。分類器の精度は最も重要である。
【００１７】
その後、ユーザによって与えられたラベルを有する、能動的に選択されたデータをトレーニングデータに追加する。ユーザフィードバックが繰り返される度に分類器がトレーニングし直されるように、この過程を繰り返す（１６２）。最後に、テストデータセット１０５を用いて性能評価を行ない、成熟度スコア１６１を生成する。テストデータセットはシードセット及びアクティブプールとは異なる。能動学習の巡回数はｋであり、繰り返す度に選択されるテスト例の数はｎである。
【００１８】
主分類器としてのサポートベクトルマシン
本発明は主分類器１６０としてサポートベクトルマシン（ＳＶＭ）を用いる。従来のＳＶＭ分類器では、典型的には、クラスの数は予め分かっている。ＳＶＭは、分類及び回帰のための管理された学習法である。たとえば、従来のＳＶＭ２クラス分類器は、２つのデータセットを２つのクラスに分離する超平面を構成する。この平面は、２つのデータセット間のマージンを最大にする。
【００１９】
マルチクラス能動学習
本発明による手法は不確定サンプリングを使用し、ユーザ１４１がラベル付けするために、分類器にとって不確定なデータが選択される。マージンベース分類器の場合の超平面からの距離が、不確定性の指標として用いられてきた。しかしながら、その不確定サンプリングは、多数の超平面が必要であることに起因して、マルチクラス分類に拡張するのは容易ではない。
【００２０】
本発明は、多数のクラスに容易に適用することができる不確定性の概念を使用する。この不確定性は、マルチクラス分類器によって出力されるような、ラベル無しデータのためのクラスメンバーシップ確率値から得られる。
【００２１】
確率的モデルの場合、それらの値は直接入手することができる。ＳＶＭのような他の分類器の場合、本発明は最初に、ラベル無しデータのクラスメンバーシップ確率１１１を推定する（１１０）。以下において、本発明は、マルチクラスＳＶＭのための確率値を推定することを記述する。しかしながら、本発明による確率推定は、他の弁別的なマルチクラス分類器と共に用いることもできる。
【００２２】
確率推定
本発明による不確定サンプリング方法は、全てのラベル無しデータ１００のためのクラスメンバーシップの確率１１１の推定値を基にする。クラス確率は、たとえば、シグモイド関数を用いて推定され、この関数は一般的にｐ（ｘ）＝１／（１＋ｅ−ｘ）と表すことができる。これらの推定値を得るために、本発明は、以下の手順を用いて、ＳＶＭから確率的出力を得る。
【００２３】
図１に示されるように、本発明のトレーニングデータセット１５０は、対応するラベルｙｉ１０２を有する特徴ベクトルｘｉ１０１の形をとり、負（−１）、正（１）いずれかである。ＳＶＭの決定関数はｆ（ｘ）である。この関数は、しきい値と比較すること（thresholding）によって予測を決定するために用いることができる。クラスメンバーシップの条件付き確率Ｐ（ｙ＝１｜ｘ）は以下の式を用いて推定することができる。
【００２４】
【数１】
2010231768.tif 000003
【００２５】
ただし、Ａ及びＢは、推定されるパラメータである。そのパラメータについて解くために、以下のような正規化された最尤推定が用いられる。
【００２６】
【数２】
2010231768.tif 000004
【００２７】
ただし、ｌはアクティブプール内のサンプルのための特徴ベクトルの数であり、ｍｉｎは最も小さな値を選択する関数であり、ｔは、以下のように定義される正及び負のラベル付き例の重要度を調整するためのサンプル毎のパラメータである。
【００２８】
【数３】
2010231768.tif 000005
【００２９】
Ｎｐ及びＮｎはそれぞれ、トレーニングデータセット内の正のサンプル１０３及び負のサンプル１０４である。後戻り直線探索（backtracking line search）を用いるニュートンの勾配降下法を用いて、上記の最適化問題を解き、確率推定値を得ることができる。
【００３０】
本発明は、ペアワイズ比較ＳＶＭ分類器１６０を使用し、この分類器はｋ個のクラスの取り得るペア毎にトレーニングされるので、結果として、このＳＶＭ分類器はマルチクラス分類に適している。ペアワイズＳＶＭは、計算が効率的であり、且つ正確である。
【００３１】
マルチクラス事例のための確率１１１は、そのようなペアワイズカップリングを通して推定することができる（１１０）。確率を推定するために、本発明は最初に、２値確率推定値を必要とし、これは先に説明されたようにして得ることができる。ｒｉｊがＰ（ｙ＝Ｉ｜ｙ＝ｉ，ｏｒｊ，ｘ）の２値確率推定値であると仮定する。
【００３２】
マルチクラス事例では、本発明は、クラスｉのための確率１１１をＰｉと表す。ペアワイズカップリングを用いるとき、その問題は以下のようになる。
【００３３】
【数４】
2010231768.tif 000006
【００３４】
ただし、ｋはクラスの数を表す。上記の最適化問題は、簡単な反復法を用いて解くことができる。
【００３５】
以下において、本発明は、クラスメンバーシップ確率推定値を用いる不確定サンプリングベース能動学習のための実施の形態を記述する。
【００３６】
エントロピー指標（ＥＰ）
各ラベル付きトレーニングデータ１０１〜１０２は、ｙ∈｛１，...，ｋ｝によって表される或る特定のクラスに属する。ただし、ｋはトレーニング以前には分からない。しかしながら、本発明は、アクティブプール内のデータのための真のクラスラベルを知らない。ラベル無しデータ毎に、本発明は、クラスメンバーシップ変数を、Ｙによって表される確率変数であると見なすことができる。
【００３７】
本発明は、上記のようにして求められる推定されたクラスメンバーシップ確率１１１のＹのための分布ｐを有する。エントロピーは、確率変数の不確定性の指標であり、たとえば、大きなエントロピーは低い確率を意味する。本発明は、クラスメンバーシップＹにおける不確定性を指示する指標を探すものであるので、そのクラスの離散エントロピーは自然な選択である。Ｙの離散エントロピーは以下の式によって推定される。
【００３８】
【数５】
2010231768.tif 000007
【００３９】
エントロピーの値が大きいほど、その分布における不確定性が大きいこと、たとえば、確率が低いことを意味する。これは、例の不確定性の指示子として用いることができる。或る例が、エントロピーが大きい分布を有する場合には、分類器はそのクラスメンバーシップについて不確定である。
【００４０】
本発明による方法は、Holubのエントロピーベース方法と混同されるべきではない。本発明による方法は、「不確定サンプリング」手法として分類することができる。この方法は、情報ベース手法である。本発明は、最も多くの情報を得ることを試みない。本発明は単に、本発明の不確定性の概念に従って、「最も不確かな」テストデータを選択する。本発明による方法及びHolubによる方法は、概念的には大きく異なっており、容易に区別される。さらに、Holub他は、ラベル無し画像の数及びクラスの数の両方に関して３次の時間を必要とする。これにより、この方法は、クラス及びサンプルの数が多くなると実用的ではなくなる。本発明の方法は、実験によれば、広範囲のクラス、たとえば、＜１００、及び６０００よりも多くの数のサンプルにわたって、アクティブプール内のラベル無しデータの数への線形時間依存性を示す。図３を参照されたい。
【００４１】
包括的方法
図１は本発明の方法を示す。能動学習を繰り返す度に（１６２）、本発明は、アクティブプール１００内の全てのデータ（ベクトル）のためのクラスメンバーシップ確率１１１を推定する（１１０）。離散エントロピー又は不確定性１１１の最も大きな推定値、すなわち最も低い確率を有するデータ１３２が、ユーザ１４１によってラベル付けする（１４０）ために選択される（１３０）。ユーザラベル１３２が得られた後に、対応するラベル付きトレーニングデータを用いて、分類器１６０を更新し、トレーニングする（１４５）。
【００４２】
テストデータ１０５を用いて、分類器の成熟度スコア１６１（精度）を測定することができ、成熟度スコアが所定のしきい値を超えるときに、トレーニングを終了する（１６２）。
【００４３】
ベスト・バーサス・セカンドベスト（Best-Versus-Second Best：ＢＶＳＢ）
図２Ａ〜図２Ｂに示されるように、エントロピーベース能動学習が多くの場合に、ランダム選択よりも良好であるにしても、不都合な点はある。エントロピー指標の問題は、その値が、重要でないクラスの確率値によって大きく影響を及ぼされることである。
【００４４】
そのプロットは、１０クラス問題における２つのラベル無し例のための推定される確率分布を示す。図２Ａのプロットは、分類器がクラス４と５との間で大きく混乱しており、２つのクラスに対して同程度の確率を割り当てることを示す。図２Ｂでは、分類器は、その例がクラス４に属することを相対的に強く確信する。それゆえ、エントロピー指標は、重要でないクラス、すなわち、その例が属する可能性が低いクラスの確率値の影響に起因して、例により大きな不確定性を割り当てる。純粋に分類判断に関して、分類器は図２Ａの例についてより混乱している。
【００４５】
不確定性
この問題は、多数のクラスが存在するときにさらに深刻になる。エントロピーは確率変数の不確定性の真の指示子であるが、本発明は、「最も混乱しているクラス間の分類にのみ関連するさらに具体的なタイプの不確定性」に関心があり、すなわち、そのデータは、小さな確率推定値を有するクラスに属さないことを事実上保証される。
【００４６】
確率１１１を直接当てにする代わりに、本発明は、上記の問題を考慮に入れるために、より貪欲な手法をとる。本発明は、確率１１１の指標として、最も大きな推定確率値を有する２つのクラスの確率値間の差１２１を求める（１２０）。これは、最良の（最も大きな）確率と２番目に良い（大きな）確率との比較であるので、本発明はこれをベスト・バーサス・セカンドベスト（ＢｖＳＢ）手法と呼ぶ。ＢｖＳＢ１２１指標は、分類の観点から、クラスメンバーシップについての混乱を推定する、さらに正確な方法である。
【００４７】
上記のように、確信度推定値は、低い確率を割り当てられたクラスがデータの真のクラスであることがめったにないという意味において信頼性がある。しかしながら、これは、初期トレーニングデータセットサイズが良好な確率を推定するだけの十分な大きさを有する場合にのみ当てはまる。本発明は、１００クラス分類器１６０においてトレーニングするために、２つほどの少ない例を有するシードデータ１０６を用いて開始することができる。
【００４８】
推定された確率
最初に、確率推定値１１１はあまり信頼性がなく、ランダムに例を選択しても、同様の結果が与えられる。トレーニングデータ１５０の量が増えると、ＢｖＳＢ１２１を用いる能動学習は、大きなマージンによって、ランダムな選択よりも急速に良好になる。マージンを使用しない大部分の方法は、データに関する或る種のモデルに頼る。それゆえ、小さなデータセットを用いる確率推定は、大部分の能動学習法にとって問題を提起する。
【００４９】
終了判定基準
そのトレーニングは、新たなデータセット毎にバッチ単位で行なわれる。トレーニングサイクル毎に、本発明は性能を評価する。これは、テストデータセットを用いることによって、又は既知又は未知のラベルを有する妥当性検証サンプルデータセットを用いることによって果たされる。テストデータ及び妥当性検証データ内のラベルが分かっている場合には、本発明は分類器の精度を測定する。この精度は、全てのテスト又は妥当性検証サンプルに対する正確にラベル付けされたサンプルの比である。本発明は、成熟度スコアとして、その比を割り当てる。成熟度スコアがしきい値に達するとき、本発明は、トレーニングを中止する。その精度がターゲット性能目標を満たす場合には、本発明はトレーニングを中止する。そうでない場合には、本発明は、性能目標に到達するまで、分類器をトレーニングし直し続ける。
【００５０】
別個のテストデータ又は妥当性検証データが与えられない場合には、本発明は、アクティブプールデータに関する分類器の反応を観測する。本発明は、固定数の最新のトレーニングサイクル、たとえば最後の１０トレーニングサイクルにわたって、新たに見つけられたクラスの数の比を計算する。言い換えると、本発明は、マルチクラス分類器のクラス発見動作を観測する。トレーニングサイクルが分類器内の現在のクラスの数において大きく変化しない場合には、本発明は、分類器が成熟しており、トレーニングを終了することができるものと考える。本発明は、成熟度スコアとして、その比の逆数を割り当てる。
【００５１】
代替的には、本発明は、最も低い差スコアの平均スコアを計算することによって、分類器の適性を観測する。これは、固定数の最新のトレーニングサイクルにわたって行なわれる。その後、本発明は、成熟度スコアとして平均スコアを割り当てる。
【００５２】
本発明による方法は、１組の最も有用なトレーニングサンプルも生成する。本発明は、この１組の有用なサンプル内に、初期シードサンプルと、トレーニングサイクルにおいて選択されたサンプルとを含む。この１組のサンプルは、クラス毎の、及び多数のクラスの集合の場合の、最適な１組のトレーニングサンプルを表す。この集合を用いて、他のマルチクラス分類器を、より実効的にトレーニングすることができる。
【００５３】
計算コスト
能動的な選択のコストには２つの側面がある。１つ目は、繰り返す度に、トレーニングセットにおいてＳＶＭをトレーニングするコストであり、２つ目は、アクティブプールにおいて確率を推定し、最も大きなＢｖＳＢスコアを有するサンプルを選択するコストである。
【００５４】
ＳＶＭトレーニングは、全過程の中で圧倒的に最も計算負荷が高い要素である。しかしながら、能動学習の本質は、インテリジェントなデータ選択によってトレーニングデータセットのサイズを最小にすることである。それゆえ、トレーニングデータの相対的にはるかに大きなアクティブプールにおいて確率推定及び例選択のコストを考えることがさらに重要である。第１のコストは、２値ＳＶＭ分類器における確率推定に由来する。二次の収束率を保証する後戻り直線探索を用いるニュートンの方法を用いて実行されるので、この推定は効率的である。
【００５５】
図３に示されるように、選択時間は、アクティブプールサイズの関数である。その関係は線形である。これは、その方法が現実の用途において一般的である大きなアクティブプールサイズに拡張可能であることを実証する。
【００５６】
本発明は好ましい実施の形態によって例示されてきたが、本発明の精神及び範囲内で種々の他の改変及び変更を行なうことができることは理解されたい。それゆえ、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲に入るような全ての変形及び変更を包含することである。
【図１】
2010231768.tif 000012
【図２Ａ】
2010231768.tif 000013
【図２Ｂ】
2010231768.tif 000014
【図３】
2010231768.tif 000015
【外国語明細書】
2010231768.tif 000016
2010231768.tif 000017
2010231768.tif 000018
2010231768.tif 000019
2010231768.tif 000020
2010231768.tif 000021
2010231768.tif 000022
2010231768.tif 000023
2010231768.tif 000024
2010231768.tif 000025
2010231768.tif 000026
2010231768.tif 000027
2010231768.tif 000028
2010231768.tif 000029
2010231768.tif 000030
2010231768.tif 000031
2010231768.tif 000032
2010231768.tif 000033
2010231768.tif 000034
2010231768.tif 000035
2010231768.tif 000036
2010231768.tif 000037
2010231768.tif 000038
2010231768.tif 000039