(57)【要約】比較を通じてコンテンツをサーチする方法が提供される。ユーザに対して２つの候補オブジェクトが提供され、いずれのオブジェクトがユーザの意図するターゲット・オブジェクトに近いかが明らかにされる。開示する原理は少ない回数の比較でユーザのターゲットを見つけるアクティブな手法を提供する。ノイズレスなユーザのフィードバックのための、いわゆるランクネット手法を記載する。限界ダブリング定数を用いたターゲット分布に対し、ランクネットは、複数回のステップでターゲット分布の、したがって、最適条件のエントロピーに近いターゲットを見つける。ノイジーなユーザ・のフィードバックの場合についても考慮する。この場合において、緩やかに成長する（ダブリング対数の）最適条件の関数内のパフォーマンス境界が見つけられる、ランクネットの変形例についても記載する。動画データセットに対する数値的な評価によればランクネットは一般化されたバイナリ・サーチのサーチ効率に適合しており、その一方で演算コストを低減する。
2015516102.tif 000002
【特許請求の範囲】
【請求項１】
データベース内のターゲットをサーチする方法であって、
少なくともターゲットを包含するサイズを有する複数のノードのネットを構築するステップと、
前記ネット内のノードのセットを選定するステップと、
ターゲットから前記ノードのセットのうちの各ノードまでの距離を比較するステップと、
前記比較するステップに従って、前記ノードのセットのうち、前記ターゲットに最も近いノードを選択するステップと、
前記選択するステップに従って、前記ターゲットを依然として包含するサイズに前記ネットを縮小するステップと、
前記ネットのサイズが前記ターゲットのみを包含するのに十分小さくなるまで、前記選定するステップ、前記比較するステップ、前記選択するステップ、および前記縮小するステップを繰り返すステップと、を含む、前記方法。
【請求項２】
前記縮小するステップは、前記ネットが前記ターゲットに最も近い前記ノードを中心とし前記ネットの半径が前記最も近いノードから前記ターゲットまでの距離以下となるように、前記ネットを縮小する、請求項１に記載の方法。
【請求項３】
前記ネットはボロノイ・セルによって定義される、請求項２に記載の方法。
【請求項４】
前記ボロノイ・セルは複数のノードの距離に関する順序付け情報を使用して計算される充填を有する、請求項３に記載の方法。
【請求項５】
前記距離の比較はユークリッド距離を使用する、請求項１に記載の方法。
【請求項６】
前記繰り返すステップは少なくとも２回の繰り返しで実行される、請求項１に記載の方法。
【請求項７】
データベース内のコンテンツをサーチするコンピュータであって、
少なくともターゲットを包含するサイズを有する複数のノードのネットを構築する手段と、
前記ネット内のノードのセットを選定する手段と、
ターゲットから前記ノードのセットのうちの各ノードまでの距離を比較する比較手段と、
前記ノードのセットのうち、前記比較手段に応答して前記ターゲットに最も近いノードを選択する手段と、
前記選択する手段に応答して前記ターゲットを依然として包含するサイズに前記ネットを縮小する手段と、
前記ネットのサイズが前記ターゲットのみを包含するのに十分小さくなるまで、前記選定する手段、前記比較手段、前記選択する手段、および前記縮小する手段に各々の処理を繰り返させる制御手段と、
を備える、前記コンピュータ。
【請求項８】
前記縮小する手段は、前記ネットが前記ターゲットに最も近い前記ノードを中心とし前記ネットの半径が前記最も近いノードから前記ターゲットまでの距離以下となるように、前記ネットのサイズを縮小する、請求項７に記載の装置。
【請求項９】
前記ネットは、ボロノイ・セルによって定義される、請求項８に記載の装置。
【請求項１０】
前記ボロノイ・セルは複数のノードの距離に関する順序付け情報のみを使用して計算される充填を有する、請求項９に記載の装置。
【請求項１１】
前記比較手段はユークリッド距離を使用する、請求項７に記載の装置。
【請求項１２】
前記制御手段は、処理の反復を少なくとも２回の繰り返しで実行させる、請求項７に記載の装置。
【請求項１３】
データベース内のターゲットをサーチする方法であって、
少なくともターゲットを包含するサイズを有する複数のノードのネットを構築するステップと、
前記ネット内の少なくとも１つのペアのノードを選定するステップと、
複数回の繰り返しに対してターゲットから前記少なくとも１つのペアのノードの各々のうちの各ノードまでの距離を比較するステップと、
前記比較するステップに従って、前記少なくとも１つのペアのノードの各々のうち、前記ターゲットに最も近いノードを選択するステップと、
前記選択するステップに応答して、前記ターゲットを依然として包含するサイズに前記ネットを縮小するステップと、
前記ネットのサイズが前記ターゲットのみを包含するのに十分小さくなるまで、前記選定するステップ、前記比較するステップ、前記選択するステップ、および前記縮小するステップを繰り返すステップと、を含む、前記方法。
【請求項１４】
前記縮小するステップは、前記ネットが前記ターゲットに最も近い前記ノードを中心とし前記ネットの半径が前記最も近いノードから前記ターゲットまでの距離以下となるように、前記ネットを縮小する、請求項１３に記載の方法。
【請求項１５】
前記ネットはボロノイ・セルによって定義される、請求項１４に記載の方法。
【請求項１６】
前記ボロノイ・セルは複数のノードの距離に関する順序付け情報を使用して計算される充填を有する、請求項１５に記載の方法。
【請求項１７】
前記距離の比較はユークリッド距離を使用する、請求項１３に記載の方法。
【請求項１８】
前記繰り返すステップが少なくとも２回の繰り返しで実行される、請求項１３に記載の方法。
【請求項１９】
データベース内のコンテンツをサーチするコンピュータであって、
少なくともターゲットを包含するサイズを有する複数のノードのネットを構築する手段と、
前記ネット内の少なくとも１つのペアのノードを選定する手段と、
複数回の繰り返しに対してターゲットから前記少なくとも１つのペアのノードのうちの各ノードまでの距離を比較する比較手段と、
前記少なくとも１つのペアのノードのうち、前記比較手段に応答して前記ターゲットに最も近いノードを選択する手段と、
前記選択する手段に応答して前記ターゲットを依然として包含するサイズに前記ネットのサイズを縮小する手段と、
前記ネットのサイズが前記ターゲットのみを包含するのに十分に小さくなるまで、前記選定する手段、前記比較手段、前記選択する手段、および前記縮小する手段に各々の処理を繰り返させる制御手段と、を含む、前記コンピュータ。
【請求項２０】
前記縮小する手段は、前記ネットが前記ターゲットに最も近い前記ノードを中心とし前記ネットの半径が前記最も近いノードから前記ターゲットまでの距離以下となるように前記ネットを縮小する、請求項７に記載の装置。
【請求項２１】
前記ネットはボロノイ・セルによって定義される、請求項８に記載の装置。
【請求項２２】
前記ボロノイ・セルは複数のノードの距離に関する順序付け情報のみを使用して計算される充填を有する、請求項９に記載の装置。
【請求項２３】
前記比較手段はユークリッド距離を使用する、請求項７に記載の装置。
【請求項２４】
前記制御手段は、処理の反復を少なくとも２回の繰り返しで実行させる、請求項７に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２０１２年５月９日付で出願された米国仮特許出願第６１／６４４，５１９号の利益を主張するものであり、その開示内容全体を本明細書に盛り込んだものとする。
【０００２】
本原理は、比較ベースのアクティブ・サーチおよびラーニングに関する。
【背景技術】
【０００３】
比較を通じたコンテンツ・サーチは、ユーザが以下の対話的な方法で大規模なデータベースにおけるターゲットのオブジェクトを見つける方法である。各ステップにおいて、データベースは、ユーザに対して２つのオブジェクトを提供し、ユーザは、そのペアのうち、意図しているターゲットにより近いオブジェクトを選択する。次の繰り返しでは、データベースは、以前のユーザの選択に基づいて、新たなオブジェクトのペアを提供する。この処理は、ユーザの回答に基づいて、データベースがユーザの意図するターゲットを一意的に特定できるようになるまで続けられる。
【０００４】
この種の対話的なナビゲーションは、探索型サーチとしても知られ、多くの実生活での用途を有する。一例は、ＦｌｉｃｋｒまたはＰｉｃａｓａなどの、制御されていない環境で撮影された人々のピクチャのデータベースをナビゲートすることである。自動化された方法は、このような写真から有意な特徴を抽出できないことがある。さらに、多くの実用的なケースにおいては、（ＳＩＦＴ（Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ  Ｆｅａｔｕｒｅ  Ｔｒａｎｓｆｏｒｍ）特徴量のような）類似したローレベル記述子を提供する画像は、非常に異なったセマンティック・コンテンツおよびハイレベル記述を有することがあり、結果として、ユーザによって異なるように知覚されることがある。その一方で、特定の人物を探索する人力によるサーチは、ピクチャのリストから、意図する人物に最も近いサブジェクトを容易に選択することができる。
【０００５】
集合Ｎによって表現され、複数の異なるオブジェクト間の「距離」または「相違点」をとらえる距離メトリックｄが与えられたオブジェクトのデータベースを考える。特定のオブジェクトｔ∈Ｎが与えられたときに、「比較オラクル（ｃｏｍｐａｒｉｓｏｎ  ｏｒａｃｌｅ）」は、以下の類の質問に答えることが可能なオラクルである。
【０００６】
「Ｎに属する２つのオブジェクトｘおよびｙのうち、メトリックｄの下で、いずれがｔに近いか？」
【０００７】
形式的には、人間のユーザの挙動はこのような比較オラクルによってモデル化することができる。特に、オブジェクトのデータベースが距離メトリックｄを与えられた集合Ｎによって表現されるピクチャであると仮定する。
【０００８】
比較を通じた対話的なコンテンツのサーチの目的は、可能な限り少ないクエリーを用いてターゲットのオブジェクトが特定できるように、オラクル／人間に対して提供する、一連の候補となるオブジェクトのペアを見つけることにある。
【０００９】
比較を通じたコンテンツ・サーチは、最近傍サーチ（ｎｅａｒｅｓｔ  ｎｅｉｇｈｂｏｒ  ｓｅａｒｃｈ（ＮＮＳ））の特別なケースであり、距離空間に埋め込まれたオブジェクトのＮＮＳ問題を考慮する研究の拡張とみることができる。さらに、埋め込みが小さな固有な次元を有するものと仮定し、この仮定は、実際の慣例に従ったものである。特に、従来技術に係る手法は、ダブリング（ｄｏｕｂｌｉｎｇ）距離空間内のＮＮＳをサポートするためのナビゲート用のネット、決定論的なデータ構造を導入する。特定の球充填特性を満たす空間に埋め込まれるオブジェクトに対して同様の技術が考慮されており、その一方で、他の研究は、成長制限されたメトリック（ｇｒｏｗｔｈ  ｒｅｓｔｒｉｃｔｅｄ  ｍｅｔｒｉｃｓ）に依存している。これらの上述した仮定は、全て、本明細書において考慮されているダブリング定数（ｄｏｕｂｌｉｎｇ  ｃｏｎｓｔａｎｔ）に関連している。上述した従来技術の手法の全てにおいて、ターゲットとなるオブジェクトに対するデマンド（ｄｅｍａｎｄ）は、均一のものであると仮定されている。
【００１０】
幾つかの従来の研究において、比較オラクルに対するアクセスを用いたＮＮＳが導入されている。これらの研究の大きな利点は、オブジェクトが距離空間内に事前に埋め込まれているという仮定が取り除かれている点にある。距離メトリックによってオブジェクト間の類似度がとらえられることを必要とするよりも、むしろ、これらの従来の研究は、比較オラクルによって、任意の２つのオブジェクトを任意のターゲットに対するそれぞれの類似度を考慮してランク付け可能であると仮定しているにすぎない。しかしながら、これらの研究は、さらに、均一なデマンドが存在するものと仮定しており、本原理は、不均一性に対する比較を用いたサーチの拡張であると考えることができる。この点において、別の従来の手法もまた、不均一なデマンド分布の仮定に基づいている。しかしながら、距離空間が存在し、サーチ・アルゴリズムがその存在を認識していると仮定して、本原理を使用することにより、平均的なサーチ・コストの観点から、より良好な結果が得られる。上述した手法の主な問題は、その手法がメモリレス（ｍｅｍｏｒｙｌｅｓｓ）であること、すなわち、従前の比較結果を使用していないことである。その一方で、本原理の解決法では、この問題は、イーネット（Ｅ−ｎｅｔ）データ構造を導入することにより解決される。
【発明の概要】
【００１１】
従来技術のこれらの短所および欠点、さらに、その他の短所および欠点は、アクティブ・サーチに基づく比較のための方法に関する、本原理によって取り扱われる。
【００１２】
本原理の一態様に従って、データベース内のコンテンツをサーチする幾つかの方法および幾つかの装置が提供される。第１の方法は、データベース内のターゲットをサーチする複数のステップを含み、これらのステップは、まず、少なくともターゲットを包含するサイズを有する複数のノードのネットを構築するステップと、ネット内のノードのセットを選定するステップと、ターゲットからノードのセットのうちの各ノードまでの距離を比較するステップと、を含む。この方法は、さらに、比較するステップに従って、ノードのセットのうち、ターゲットに最も近いノードを選択するステップと、選択するステップに応答して、ターゲットを依然として包含するサイズにネットのサイズを縮小するステップと、を含む。この方法は、さらに、ネットのサイズがターゲットのみを包含するのに十分小さくなるまで、選定するステップ、比較するステップ、選択するステップ、および縮小するステップを繰り返すステップを含む。
【００１３】
本原理の別の態様によれば、第１の装置が提供される。この装置は、少なくともターゲットを包含するサイズを有するネットを構築する手段と、ネット内のノードのセットを選定する手段と、を含む。この装置は、さらに、ターゲットからノードのセットのうちの各ノードまでの距離を比較する比較手段と、ノードのセットのうち、比較手段に従ってターゲットに最も近いノードを見つける、選択する手段と、を含む。この装置は、さらに、選択する手段に応答してターゲットを依然として包含するサイズにネットのサイズを縮小する手段と、ネットのサイズがターゲットのみを包含するのに十分小さくなるまで、選定する手段、比較手段、選択する手段、および縮小する手段に各々の処理を繰り返させる制御手段と、を含む。
【００１４】
本原理の別の態様によれば、第２の方法が提供される。この方法は、少なくともターゲットを包含するサイズを有するネットを構築するステップと、ネット内の少なくとも１つのペアのノードを選定するステップと、を含む。この方法は、さらに、複数回の繰り返しのために、ターゲットから少なくとも１つのペアのノードの各々のうちの各ノードまでの距離を比較するステップと、比較するステップに従って、少なくとも１つのペアのノードの各々のうち、ターゲットに最も近いノードを選択するステップと、を含む。この方法は、さらに、選択するステップに応答して、ターゲットを依然として包含するサイズにネットを縮小するステップと、ネットのサイズがターゲットのみを包含するのに十分小さくなるまで、選定するステップ、比較するステップ、選択するステップ、および縮小するステップを繰り返すステップと、を含む。
【００１５】
本原理の別の態様によれば，第２の装置が提供される。この装置は、少なくともターゲットを包含するサイズを有する複数のノードのネットを構築する手段と、ネット内の少なくとも１つのペアのノードを選定する手段と、を含む。この方法は、さらに、複数回の繰り返しのために、ターゲットから少なくとも１つのペアのノードのうちの各ノードまでの距離を比較する比較手段と、少なくとも１つのペアのノードのうち、比較手段に応答してターゲットに最も近いノードを選択する手段と、を含む。この方法は、さらに、選択する手段に応答してターゲットを依然として包含するサイズにネットのサイズを縮小する手段と、ネットのサイズがターゲットのみを包含するのに十分小さくなるまで、選定する手段、比較手段、選択する手段、および縮小する手段に各々の処理を繰り返させる制御手段と、を含む。
【００１６】
本原理のこれらの態様、特徴、および利点、さらに、その他の態様、特徴、および利点は、添付の図面と併せて読まれるべき、以下の例示的な実施形態の詳細な説明によって明らかになるであろう。
【図面の簡単な説明】
【００１７】
【図１Ａ】各サンプル・データセットに対して構築された、サイズ、次元、さらに、ランクネット（Ｒａｎｋ  Ｎｅｔ）・ツリー階層のサイズを示した図である。
【図１Ｂ】予想されるクエリー計算量を示した図である。
【図１Ｃ】予想される演算量を示した図である。
【図２Ａ】データセット・サイズの関数とした、５つのアルゴリズムのクエリー計算量を示した図である。
【図２Ｂ】データセット・サイズの関数とした、５つのアルゴリズムの演算量を示した図である。
【図２Ｃ】誤りオラクルの下でのｎを関数とした、クエリー計算量を示した図である。
【図３】本原理によって実施される例示的なアルゴリズムを示す図である。
【図４】本原理に係る方法の第１の実施形態を示す図である。
【図５】本原理に係る装置の第１の実施形態を示す図である。
【図６】本原理に係る方法の第２の実施形態を示す図である。
【図７】本原理に係る装置の第２の実施形態を示す図である。
【発明を実施するための形態】
【００１８】
本原理は、比較ベースのアクティブ・サーチのための方法および装置に関する。この方法は、以前のステージの結果を使用して比較のステージが繰り返されるため、「アクティブ・サーチ」と呼ばれる。この方法は、オブジェクト（例えば、ピクチャ、ムービー、記事など）のデータベースをナビゲートし、比較オラクルに対してオブジェクトの複数のペアを提供する。比較オラクルは、２つのオブジェクトのうちのいずれがターゲット（例えば、ピクチャ、または、ムービー、または、記事など）に近いかを判定する。次の繰り返しにおいて、データベースは、ユーザの以前の選択に基づいて、オブジェクトの新しいペアを提供する。この処理は、ユーザの回答に基づいて、データベースがユーザの意図するターゲットを一意的に特定できるようになるまで続けられる。各ステージにおいて、比較のためにオブジェクトの小さなリストが提供される。リストの中で、１つのオブジェクトがターゲットに最も近いオブジェクトとして選択される。次に、以前の選択に基づいて新しいオブジェクトのリストが提供される。この処理は、ターゲットが提供されたリストに含まれるまで続けられ、ターゲットが提供されたリストに含まれた時点でターゲットが見つけられ、サーチが終了する。
【００１９】
本明細書中に記載する手法は、ターゲットのオブジェクトｔ∈Ｎが確率分布μからサンプリングされる、不均一なデマンドのシナリオでの問題を考慮したものである。この設定において、比較を通じた対話的なコンテンツのサーチは、古典的な「２０個の質問のゲーム」の問題に強く関係している。特に、メンバーシップ・オラクルは、以下の形式のクエリーに回答することが可能なオラクルである。
「部分集合Ａ⊆Ｎが与えられている場合、ｔはＡに属するか？」
【００２０】
ターゲットｔを見つけるためには、メンバーシップ・オラクルに対し、平均で、少なくともＨ（μ）個のクエリーを実行する必要がある。ここで、Ｈ（μ）は、μのエントロピーである。さらに、平均で、Ｈ（μ）＋１個のクエリーのみを用いてターゲットを見つけるアルゴリズム（ホフマン符号化（Ｈｕｆｆｍａｎ  ｃｏｄｉｎｇ））が存在する。
【００２１】
データベースＮにメトリックｄが与えられているものと仮定する際、比較を通じたコンテンツのサーチは、上述した設定から始められる。メンバーシップ・オラクルは、比較オラクルよりも強力である。その理由は、距離メトリックｄが既知である場合には、メンバーシップ・クエリーを通じて比較クエリーをシミュレートすることができるからである。他方で、メンバーシップ・オラクルは、実際上、実施がより困難である。Ａが簡潔に表現できない限り、ユーザは、｜Ａ｜において、線形的な時間に、メンバーシップ・クエリーに回答する。これは、回答が一定の時間に与えられる比較オラクルとは異なるものである。簡単に言えば、比較を通じたサーチのここで取り扱われる問題は、（ａ）より実施が簡単なオラクルに対し、さらに、（ｂ）データベースの構造上に追加的な仮定を有する、すなわち、距離メトリックが与えられていることを仮定した場合に、古典的な設定と同様のパフォーマンス境界を求めるものである。
【００２２】
直感的には、比較を通じたオブジェクトのサーチのパフォーマンスは、ターゲット分布のエントロピーに依存するだけでなく、メトリックｄによって記述されているような、ターゲット集合Ｎのトポロジーにも依存する。特に、比較オラクルを使用してターゲットを見つけるためには、見込みとしては、Ω（ｃＨ（μ））個のクエリーが必要であることが判明している。ここで、ｃは、メトリックｄのいわゆるダブリング定数（ｄｏｕｂｌｉｎｇ−ｃｏｎｓｔａｎｔ）である。さらに、発明者らは、以前、見込みでは、Ｏ（ｃ３Ｈｌｏｇ（１／μ＊））個のクエリーでターゲットを見つける方法を提供している。ここで、μ＊＝ｍｉｎｘ∈Ｎμ（ｘ）である。本原理に基づいて、見込みでは、Ｏ（ｃ５Ｈ（μ））個のクエリーを用いてターゲットを見つける方法を使用して、従前の限界に対する改善を得ることができる。
【００２３】
比較を通じたサーチ
オブジェクト間の「相違度」をとらえた、距離メトリックｄが与えられたサイズｎ：＝｜Ｎ｜のオブジェクトの大きな有限集合Ｎを考える。ユーザは、事前の分布μからターゲットｔ∈Ｎを選択する。本原理の目的は、ターゲットｔを発見するためのクエリーの数が可能な限り少なくなるように、オブジェクトの複数のペアを用いて、ユーザに対してクエリーを行う対話的な方法を設計することにある。
【００２４】
比較オラクルは、２つのオブジェクトｘ、ｙおよびターゲットｔが与えられたときに、ターゲットｔに最も近いオブジェクトを返すオラクルである。より形式的には、以下の通りである。
【数１】
2015516102.tif 000003
【００２５】
メトリックｄが存在すると仮定するものの、距離の見方は、オブジェクト間の順序関係を観察することのみに制約される。より正確には、比較オラクルを通じて得ることができる情報に対するアクセスしか存在しない。オブジェクトｚが与えられると、比較オラクルＯｚは順序付けられたペア（ｘ，ｙ）∈Ｎ２をクエリーとして受信し、質問「ｚはｙよりもｘに近いか？」、すなわち、
【数２】
2015516102.tif 000004
に回答する。
【００２６】
未知のターゲットｔを判定するために本明細書において説明する方法は、比較オラクルＯｔ、すなわち、ユーザにクエリーを提供する。実効的に、ユーザが複数のオブジェクトをターゲットｔからのそれぞれの距離で順序付けることができるが、これらの距離の正確な値を明らかにする必要がない（または、知る必要さえもない）と仮定する。
【００２７】
次に、オラクルが常に正しい回答を与えると仮定する。その後で、この仮定は、確率ε＜０．５の誤りオラクルを考慮することによって緩和される。
【００２８】
本原理は、距離メトリックｄの情報を必要としない、どのクエリーをＯｔに提供するかを判定することに焦点が当てられる。ここに提供する方法は、どのｚ∈Ｎも、（ａ）分布μおよび（ｂ）マッピングの値Ｏｚ：Ｎ２→｛−１，＋１｝の事前の情報のみに依存する。これは、距離メトリックｄが存在するとしても、それを直接観察できないという仮定に沿ったものである。
【００２９】
この事前のμは、過去において、オブジェクトがターゲットとなった頻度として、経験的に推定することができる。順序関係は、Θ（ｎ２ｌｏｇ  ｎ）個のクエリーを比較オラクルに提供し、Θ（ｎ２）空間を必要とすることで、オフラインで計算することができる。想定される各ターゲットｚ∈Ｎに対し、Ｎにおける複数のオブジェクトは、Ｏｚに対するΘ（ｎｌｏｇ  ｎ）個のクエリーを用いて、ｚからのそれぞれの距離で分類することができる。
【００３０】
この分類の結果は、（ａ）ｚから等距離のオブジェクトの集合を要素とするリンク付けされたリストに記憶され、並びに、（ｂ）分類されたリストにおけるランクを用いて各要素ｙを関連付けたハッシュ・マップに記憶される。なお、Ｏｚ（ｘ，ｙ）は、したがって、ｚからのそれぞれの距離でｘおよびｙの相対的なランクを比較することによって、Ｏ（１）回で取得される。
【００３１】
本原理は、適応的なアルゴリズムに焦点を当て、Ｎ２におけるどのクエリーを次に提供するかという決定はオラクルの以前の回答によって行われる。方法のパフォーマンスは２つのメトリックを通じて測定することができる。第１のメトリックはこの方法のクエリー計算量であり、この方法がターゲットを判定するためにオラクルに提供する必要のある予想されるクエリーの数によって決定される。第２のメトリックはこの方法の演算量であり、各ステップでオラクルに対して提供するクエリーを決定する時間計算量によって決定される。
【００３２】
下限（Ｌｏｗｅｒ  Ｂｏｕｎｄ）
μのエントロピーは、Ｈ（μ）＝Σｘ∈ｓｕｐｐ（μ）μ（ｘ）ｌｏｇ（１／μ（ｘ））として定義されることが理解できよう。ここで、ｓｕｐｐ（μ）は、μの台である。オブジェクトｘ∈Ｎが与えられると、Ｂｘ（ｒ）＝｛ｙ∈Ｎ：ｄ（ｘ，ｙ）≦ｒ｝を、ｘを中心とする半径ｒ≧０の閉球とする。集合Ａ⊆Ｎが与えられると、μ（Ａ）＝Σｘ∈Ａμ（ｘ）とする。分布μのダブリング定数ｃ（μ）を最小値ｃ＞０とする。ここで、任意のｘ∈ｓｕｐｐ（μ）および任意のＲ≧０に対し、μ（Ｂｘ（２Ｒ））≦ｃ・μ（Ｂｘ（Ｒ））である。
【００３３】
ダブリング定数は、距離ｄによって決定されるデータセットの基礎の次元に対して自然なつながりを有する。エントロピーおよびダブリング定数もまた双方とも比較を通じたコンテンツ・サーチに対して本質的なつながりを有する。ターゲットｔを見つけるためのどのような適応的なメカニズムであっても、少なくとも、見込みではオラクルＯｔに対して少なくともΩ（ｃ（μ）Ｈ（μ））個のクエリーを提供しなければならないことが判明している。さらに、従来の研究はＯ（ｃ３Ｈ（μ）Ｈｍａｘ（μ））個のクエリーでターゲットを判定するためのアルゴリズムについて記載している。ここで、Ｈｍａｘ（μ）＝ｍａｘｘ∈ｓｕｐｐ（μ）ｌｏｇ（１／μ（ｘ））である。
【００３４】
アクティブ・ラーニング
比較を通じたサーチは、アクティブ・ラーニングの特別なケースであると見ることができる。アクティブ・ラーニングにおいては、仮説空間Ｈは、クエリー空間と呼ばれる、有限集合Ｑに対して定義されるバイナリ値を有する関数の集合である。各仮説ｈ∈Ｈは、クエリーｑ∈Ｑ毎に、｛−１，＋１｝からラベルを生成する。ターゲット仮説ｈ＊は、幾らかの事前のμに従って、Ｈからサンプリングされ、クエリーｑを要求することにより、ｈ＊（ｑ）の値が明らかになり、これにより、候補として挙げることが可能な仮説が制限される。この目的は、可能な限り少ないクエリーを要求することによって、適応的な方法でｈ＊を一意的に判定することにある。
【００３５】
本原理では、仮説空間Ｈは、オブジェクトの集合Ｎであり、クエリー空間Ｑは、順序付けされたペアの集合Ｎ２である。μからサンプリングされるターゲット仮説は、ｔにほかならない。各仮説／オブジェクトｚ∈Ｎは、マッピングＯｚ：Ｎ２→｛−１，＋１｝によって一意的に特定され、これを事前に既知であると仮定する。
【００３６】
一般的なアクティブ・ラーニングの設定で真の仮説を決定するよく知られているアルゴリズムは、いわゆる、一般化されたバイナリ・サーチ（ｇｅｎｅｒａｌｉｚｅｄ  ｂｉｎａｒｙ  ｓｅａｒｃｈ（ＧＢＳ））、または、分割アルゴリズムである。バージョン空間Ｖ⊆Ｈを、これまでに観察されたクエリーの回答と整合性を有する想定される仮説の集合であると定義する。各ステップにおいて、ＧＢＳは、｜Σｈ∈Vμ（ｈ）ｈ（ｑ）｜を最小にするクエリーｑ∈Ｑを選択する。別の言い方をすれば、ＧＢＳは、現在のバージョン空間を概ね同一の（確率）質量の２つの集合に分けるクエリーを選択する。これにより、見込みでは、バージョン空間の質量の減少が可能な限り最大となるため、ＧＢＳを、貪欲なクエリー選択ポリシーとみることができる。
【００３７】
ＧＢＳのクエリー計算量に対する限界は、以下の定理によって与えられる。 
【００３８】
定理１．ＧＢＳは、見込みでは、最大でＯＰＴ・（Ｈｍａｘ（μ）＋１）個のクエリーを作成し、仮説ｈ＊∈Ｎを特定する。ここで、ＯＰＴは、任意の適応的なポリシーによって作成される、予想される最小の数のクエリーである。
【００３９】
比較を通じたサーチにおけるＧＢＳ
本原理では、バージョン空間Ｖは、それまでに与えられたオラクルの回答と整合するｚ∈Ｎにおける全ての想定可能なオブジェクトからなる。換言すると、それまでにオラクルに提供された全てのクエリー（ｘ，ｙ）に対し、Ｏｚ（ｘ，ｙ）＝Ｏｔ（ｘ，ｙ）であれば、ｚ∈Ｖとなる。従って、次のクエリーを選択すると、
【数３】
2015516102.tif 000005
を最小化するペア（ｘ，ｙ）∈Ｎ２が見つけられる。
【００４０】
シミュレーションによれば、実際上、ＧＢＳのクエリー計算量が優れている。これは、比較を通じたサーチの特定の状況下で、この上限が潜在的に改善する可能性があることを示唆している。
【００４１】
しかしながら、ＧＢＳの演算量は、Ｎ２における全てのペアに対してｆ（ｘ，ｙ）を最小にすることを必要とするため、クエリー毎に、Θ（ｎ２｜Ｖ｜）回の処理となる。大きな集合Ｎでは、このようなことは、まさに禁止されるべきものである。これは、本願において新たなアルゴリズムであるランクネット・サーチ（ＲＡＮＫＮＥＴＳＥＡＲＣＨ）を提案する動機付けとなるものである。このランクネット・サーチの演算量は、Ｏ（１）であり、さらに、そのクエリー計算量は、最適なものからＯ（ｃ５（μ））のファクタ（ｆａｃｔｏｒ）以内である。
【００４２】
効率的な適応的アルゴリズム
本原理を使用するこの方法は、最近傍サーチ（ＮＮＳ）との関連で以前に導入された構造であるε−ｎｅｔによって触発されたものである。ほとんど重複のない複数の球から構成されるネットを用いたバージョン空間（すなわち、現在有効な仮説／想定されるターゲット）を網羅することが主に前提となる。本方法は、ターゲットに対して各球の中心までのそれぞれの距離を比較することによって、ターゲットが属する球を特定することができる。このサーチは、この球にバージョン空間を制限し、この処理を繰り返し、この球をより細かいネットで網羅することによって進められる。本方法が直面している主な課題は、標準的なＮＮＳとは異なり、基礎となる距離メトリックへのアクセスが存在しないことである。さらに、ε−ｎｅｔによって作成される比較の数の限界が最悪のケース（すなわち、事前情報が存在しないこと）である。本方法を用いた構成は、見込み上の制限を与えるために、事前のμを考慮する。
【００４３】
ランクネット
上述した問題を取り扱うために、本方法は、この設定において、ε−ｎｅｔの役割を果たすランクネットの概念を導入する。幾つかのｘ∈Ｎに対して、球Ｅ＝Ｂｘ（Ｒ）⊆Ｎを考える。任意のｙ∈Ｅに対して、
【数４】
2015516102.tif 000006
をρμ（Ｅ）を超える質量を維持するｙを中心とする最小の球の半径であると定義する。この定義を用いて、ρ−ランクネットを以下のように定義する。
【００４４】
定義１．何らかのρ＜１に対して、Ｅ＝Ｂｘ（Ｒ）⊆Ｎのρ−ランクネットは、任意の２つの別個のｙ、ｙ’∈Ｒに対して、
【数５】
2015516102.tif 000007
となるような、複数のポイントＲ⊂Ｅを最大限に集めたものである。
【００４５】
任意のｙ∈Ｒに対し、ボロノイ・セル（Ｖｏｒｏｎｏｉ  ｃｅｌｌ）
【数６】
2015516102.tif 000008
を考慮する。
【００４６】
さらに、ボロノイ・セルＶｙの半径ｒｙをｒｙ＝ｉｎｆ｛ｒ：Ｖｙ⊆Ｂｙ（ｒ）｝と定義する。
【００４７】
特に、ここでの目的のため、ランクネットおよびこのランクネットによって定義されるボロノイ充填（ｔｅｓｓｅｌａｔｉｏｎ、テッセレーション）を、双方とも、順序付け情報のみを用いて計算することができる。
【００４８】
補題１．Ｅのρ−ランクネットＲは、Ｏ（｜Ｅ｜（ｌｏｇ｜Ｅ｜＋｜Ｒ｜）個のステップから構築することができ、Ｒを中心とするボロノイ・セルを囲む球Ｂｙ（ｒｙ）⊂Ｅは、ｚ⊆Ｅ毎に、（ａ）μおよび（ｂ）マッピングＯｚ：Ｎ２→｛−１，＋１｝のみを使用して、Ｏ（｜Ｅ｜｜Ｒ｜）個のステップから構築することができる。
【００４９】
この結果を用いて、次に、ρの選択がどのようにネットのサイズ、さらに、その周りのボロノイ球の質量に影響を与えるかに焦点を当てる。次の補題は、｜Ｒ｜を限定する。
【００５０】
補題２．ネットＲのサイズは、最大でｃ３／ρである。
以下の補題は、ネット内のボロノイ球の質量を判定する。
【００５１】
補題３．ｒｙ＞０であれば、μ（Ｂｙ（ｒｙ））≦ｃ３ρｕ（Ｅ）である。なお、補題３は、半径０（零）のボロノイ球の質量を限定しない。この補題は、実際には、必然的に、（μ（ｙ）＞ｃ３ρμ（Ｅ）である）高確率オブジェクトｙがＲに含まれ、対応する球Ｂｙ（ｒｙ）は、単集合（ｓｉｎｇｌｅｔｏｎ）となる。
【００５２】
ランクネット・データ構造およびアルゴリズム
ランクネットは、アルゴリズム１で説明した比較オラクルＯｔを使用してターゲットｔを特定するために使用することができる。最初に、Ｎを網羅するネットＲが構築される。複数のノードｙ∈Ｒが、ｔからのそれぞれの距離で比較され、ターゲットに最も近いものが特定され、それがｙ＊と呼ばれる。なお、これには、｜Ｒ｜−１個のクエリーをオラクルに提供することが必要となる。バージョン空間Ｖ（想定される仮説の集合）は、したがって、ボロノイ・セルＶｙ＊であり、これは、球Ｂｙ＊（ｒｙ＊）の部分集合である。この方法は、次に、サーチをＢｙ＊（ｒｙ＊）に限定し、上記処理を繰り返すことによって進められる。なお、常時、バージョン空間がネットによって網羅されるべき現在の球に含まれる。この処理は、この球が単集合となったときに終了し、この単集合は、ターゲットを含まなければならないように構成される。
【００５３】
上記の方法における１つの問題は、どのようにρを選択するかである。補題３では、複数の小さな値により、ボロノイ球の質量が、或るレベルから次のレベルに、急激に減少し、結果として、より少ない数の繰り返しでターゲットに到達できるようになる。他方で、補題２では、小さな値もまた、より大きなネットを示唆するため、各反復処理でオラクルにより多くのクエリーを提供することになる。ここでの方法は、アルゴリズム２の擬似コードで示されているように、反復的にρを選択する。この方法は、結果として得られるネットの全ての非単集合ボロノイ球Ｂｙ＊（ｒｙ＊）が０．５μ（Ｅ）で限定される質量を有するまで、ρを繰り返し半減させる。この選択により、ランクネット・サーチの対応するクエリー計算量および演算量が以下の限界を有することとなる。
【００５４】
定理２．ランクネット・サーチは、見込みでは、４ｃ６（１＋Ｈ（μ））回のクエリーを比較オラクルに提供することによって、ターゲットを見つける。どのクエリーを次に提供するかを判定するコストは、Ｏ（ｎ（ｌｏｇ  ｎ＋ｃ６）ｌｏｇ  ｃ）である。
【００５５】
Ω（ｃＨ（μ））のクエリー計算量の下限に鑑み、本方法、ランクネット・サーチはクエリー計算量の点では、最適なアルゴリズムのＯ（ｃ５）のファクタ以内であり、したがって、定数ｃに対して最適な次数である。さらに、クエリー毎の演算量は、ＧＢＳアルゴリズムの三次式のコスト（ｃｕｂｉｃ  ｃｏｓｔ）と異なり、Ｏ（ｎ（ｌｏｇ  ｎ  ＋ｃ６）となる。これにより、ＧＢＳと比較して、演算量が大幅に削減される。
【００５６】
なお、上記演算コストは、実際には、償却（ａｍｏｒｔｉｚａｔｉｏｎ）を通じてＯ（１）に減少させることができる。特に、ランクネット・サーチがたどる想定されるパスが階層を定義し、これにより、全てのオブジェクトが、それぞれのボロノイ球を網羅するオブジェクトに対する親としての役目を果たすことが容易に分かるであろう。このツリーは、予め構築することができ、さらに、サーチをこのツリーの系統（ｄｅｃｅｎｔ）として実施することができる。
【００５７】
ノイジーな比較オラクル
次に、任意の所与のクエリーＯ（ｘ，ｙ，ｔ）に対する回答が確率１−ｐx,y,tで正しく、確率ｐx,y,tで誤りであるノイジーなオラクルを考える。さらに、これは別個のクエリー間で独立している。結果的に誤り確率ｐx,y,tは１／２から離れた値に限定される。すなわち、全ての（ｘ，ｙ，ｔ）がｐx,y,t≦ｐｅとなるように、ｐｅ＜１／２の関係が存在する。
【００５８】
この点に関して、本原理の別の実施形態は、クエリー計算量が限定される従来のアルゴリズムの変更を提案するものである。この処理は、依然として、上述したように構築されたランクネット階層に依存するものである。しかしながら、本実施形態は、階層を１レベル下降する際に、ランクネットの誤った要素が選択されている確率を限定するために、各ラウンドでの繰り返しを使用する。
【００５９】
具体的には、所与のレベル
2015516102.tif 000009
およびランクネットのサイズｍに対し、繰り返しファクタ
2015516102.tif 000010
を以下のように定義する。ここで、β＞１および
2015516102.tif 000011
は、２つの設計パラメータである。
【数７】
2015516102.tif 000012
【００６０】
次に、変更後のアルゴリズムは、トップ・レベル（
2015516102.tif 000013
）から開始して、階層を下降する。基本的なステップは、レベル
2015516102.tif 000014
において、対応するランクネットにおけるノードの集合Ａを用いて、以下のように進められる。トーナメントが、初期にペアとなるランクネット・メンバーの中で組織される。
競合するメンバーのペアは、
2015516102.tif 000015
回比較される。ゲームの最大数の勝利を得た所与のペアからの「プレイヤ」は、次のステージに移動し、そこで、再び、第１のラウンドの別の勝利者とペアを組まされるなど、１人のプレイヤのみが残るまでこの処理が続けられる。なお、繰り返しＲの数は、レベル
2015516102.tif 000016
の対数でのみ増加する。
【００６１】
クエリー計算量、さらに、これに対応する正確にターゲットを特定できる確率に対する限界は、以下の処理を活用することによって得られる。
【００６２】
補題４．固定されたターゲットｔ、さらに、誤り確率の上界ｐｅを有するノイジー・オラクルが与えられると、
2015516102.tif 000017
回の繰り返しで、集合Ａの要素の中でのトーナメントは、少なくとも
2015516102.tif 000018
の確率でターゲットｔに最も近い、集合Ａの中の要素を返す。
【００６３】
これは、簡略化のため、結びつきが存在しないものと仮定するだけで、すなわち、ｔに最も近いＡの中の一意なポイントが存在するものと仮定することで証明される。結びつきが存在する場合には、同様に推測できる。まず、ｘおよびｙのうちから、Ｒ回のクエリーＯ（ｘ，ｙ，ｔ）を繰り返すことで大部分の比較を勝ち残ったものがｔに最も近いものではない確率ｐ（Ｒ）を限定する。誤り確率に対する上界ｐｅが存在するため、（結びつきの可能性を無視すれば）ｐ（Ｒ）≦Ｐｒ（Ｂｉｎ（Ｒ，ｐｅ）≧Ｒ／２）となる。
【００６４】
アズマ−ヘフディング（Ａｚｕｍａ−Ｈｏｅｆｆｄｉｎｇ）の不等式は、上記不等式の右辺がｅｘｐ（−Ｒ（１／２−ｐｅ）２／２）以下になるようにするものである。繰り返し回数Ｒを式（５）で置き換えることによって、対応する誤り確率の上界が
【数８】
2015516102.tif 000019
によって与えられることが分かる。
【００６５】
次に、ゲームがｔに最も近いＡ内の要素によって行われることを考える。このようなゲームは、多くても｜ｌｏｇ２（｜Ａ｜）｜個存在する。和集合上界（ｕｎｉｏｎ  ｂｏｕｎｄ）により、最も近い要素がこれらのゲームのうちのいずれか１つに敗北する確率は、理論的には、
2015516102.tif 000020
以上にもなる。
【００６６】
注１．ノイズレス・オラクルを用いてターゲットｔに最も近いターゲットを見つけるためには、明らかに、Ｏ（｜Ａ｜）個のクエリーが必要となる。提案しているアルゴリズムは、多くとも、ファクタ
2015516102.tif 000021
の比較を追加することによって、高確率で同じ目的を達成するものである。
【００６７】
この点に関し、ここで提案したアルゴリズムにより、以下の定理が証明される。
【００６８】
定理３．繰り返しおよびトーナメントを用いたアルゴリズムは、
【数９】
2015516102.tif 000022
回のクエリーで少なくとも
【数１０】
2015516102.tif 000023
の確率で正確なターゲットを出力する。 
【００６９】
注２．なお、β＞１および十分に大きな
2015516102.tif 000024
を選定することによって、エラー確率を任意に小さくすることができる。またさらに、均一分布ｐｉ≡１／ｎに対し、次数Ｈ（μ）＝ｌｏｇ（ｎ）の項に加えて、追加的なｌｏｇ  ｌｏｇ（ｎ）のファクタが生み出される。
【００７０】
これは、和集合上界および前の補題から証明することができる。条件的には、任意のターゲットｔ∈Ｎに対し、
【数１１】
2015516102.tif 000025
となる。ターゲットがＴ＝ｔであることが与えられると、比較の数は、多くても、
【数１２】
2015516102.tif 000026
となる。ここで、Ｏ項は、ダブリング定数ｃ、誤り確率ｐｅ、および設計パラメータ
2015516102.tif 000027
およびβのみに依存する。クエリーの予想される数に対する限界は、ｔ∈Ｎにわたった平均化に従う。
【００７１】
図１Ａは、各データセットに対して構築された、テーブルのサイズ、次元（特徴数）、さらに、ランクネット・ツリー階層のサイズを示している。図１Ｂは、各データセットに対して適用される５つのアルゴリズムの、サーチ毎に予想されるクエリー計算量を示している。ランクネット（ＲＡＮＫＮＥＴ）およびＴ−ランクネット（Ｔ−ＲＡＮＫＮＥＴ）は、同一のクエリー計算量を有するため、一方のみが示されている。図１Ｃは、各データセットに対して適用される５つのアルゴリズムの、サーチ毎に予想される演算量を示している。ＭＥＭＯＲＹＬＥＳＳおよびＴ−ＲＡＮＫＮＥＴについては、この予想される演算量は、クエリー計算量と等しい。
【００７２】
評価
本原理の下で提案されている方法、ランクネット・サーチは、６個の公に利用可能なデータセット、ｉｒｉｓ、ａｂａｌｏｎｅ、ａｄ、ｆａｃｅｓ、ｓｗｉｓｓ  ｒｏｌｌ（ｉｓｏｍａｐ）、およびｎｅｔｆｌｉｘ（ｎｅｔｆｌｉｘ）の下で評価することができる。後者の２つは、ｓｗｉｓｓ  ｒｏｌｌから任意に選択されたデータを取って、さらに、ｎｅｔｆｌｉｘにおける１０００個の最も評価されている映像を用いてサブサンプリングすることができる。
【００７３】
これらのデータセットは、ユークリッド空間Ｒｄにマッピングされる（カテゴリー変数は標準的な方法でバイナリ値にマッピングされる。）。次元ｄは、図１Ａの表に示されている。ｎｅｔｆｌｉｘについては、動画は、ＳＶＤを通じてユーザ／動画レーティング・マトリクスの低ランク近似を取得することによって、５０次元ベクトルにマッピングされる。次に、
2015516102.tif 000028
をオブジェクトブジェクト間の距離メトリックとして使用して、α＝０．４の冪乗則事前情報からターゲットを選択する。
【００７４】
ランクネット・サーチの２つの実施態様のパフォーマンスについて評価した。一方の実施態様は、アルゴリズム１の場合のような、ランクネットがオンラインで決定されるものであり、他方の実施態様は、Ｔ−ランクネット・サーチと呼ばれるものであり、ランクネットの階層全体が予め計算され、ツリーとして記憶されるものである。双方のアルゴリズムは、正確に同じクエリーをオラクルに提供するため、同一のクエリー計算量を有する。しかしながら、Ｔ−ランクネット・サーチは、クエリー毎にＯ（１）のみの演算量を有する。各データセットに対し、Ｔ−ランクネット・サーチによって予め計算されるツリーのサイズは、図１Ａのテーブルに示されている。
【００７５】
これらのアルゴリズムを、（ａ）１つの従来技術に係る方法によって提案されるメモリレス・ポリシーと、（ｂ）ＧＢＳに基づく２つのヒューリスティック（発見的な手法）と比較する。クエリー毎のＧＢＳの演算コストは、Θ（ｎ３）であり、ここで考慮されるデータセットでは、処理が困難なものとなっている。
【００７６】
ＧＢＳと同様に、高速化ＧＢＳ（ｆａｓｔ  ＧＢＳ）であるためＦ−ＧＢＳと呼ばれる第１のヒューリスティックは、等式（２）を最小化するクエリーを選択する。しかしながら、この処理は、現在のバージョン空間Ｖにおけるオブジェクトのペアにクエリーを制限することによって行われる。この処理により、クエリー毎の演算コストは、Θ（ｎ２｜Ｖ｜）にはならず、Θ（｜Ｖ｜３）に低減される。もちろん、この場合の演算コストは、初期のクエリーでは、依然としてΘ（ｎ３）である。スパースなＧＢＳ（ｓｐａｒｓｅ  ＧＢＳ）であるためＳ−ＧＢＳと呼ばれる第２のヒューリスティックは、以下のようにランクネットを利用する。まず、Ｔ−ランクネット・サーチの場合のように、データセットに対してランクネット階層が構築される。次に、等式（２）の値を最小化するため、同一のネットに現れるオブジェクトの複数のペア間のクエリーのみにクエリーが制限される。直感的には、Ｓ−ＧＢＳでは、オブジェクトの「良好な」（すなわち、公正な）パーティションがこのような複数のペア間で見つけられるものと仮定する。
【００７７】
クエリー計算量と演算量との対比
サーチ毎のクエリーの平均の個数で示した、複数の異なるアルゴリズムのクエリー計算量が図１Ｂに示されている。Ｆ−ＧＢＳの場合でもＳ−ＧＢＳの場合でも、保証されているものは何も知られていないが、双方のアルゴリズムは、全てのデータセットに亘ったクエリー計算量の観点からは、見込みでは、ターゲットを約１０個のクエリー以下で見つけることができるため、良好である。ＧＢＳのパフォーマンスは、これらのアルゴリズムと同様であり、これらのことより、定理１によって予想されるものと同様の良好なパフォーマンスが得られることが示唆される。ランクネット・サーチ（のクエリー計算量は、クエリー計算量が２〜１０倍多く、その影響は、ランクネット・サイズがｃダブリング定数に依存していることから予想されるように、データセットが高次元ではより大きくなる。最終的に、全ての他のアルゴリズムと比較して、メモリレス（ＭＥＭＯＲＹＬＥＳＳ）のパフォーマンスは低い。
【００７８】
図１に示されているように、上記の順序付けは、サーチ毎に行われる処理の総計を尺度とした演算度に関しては、完全に逆になる。或るアルゴリズムと次のアルゴリズムとの差異は、５０〜１００桁の範囲になる。Ｆ−ＧＢＳは、幾らかのデータセットでは、見込みでは、１０９個に近い処理を必要とするが、これに対し、ランクネット・サーチでは、１００〜１０００個の処理の範囲となる。
【００７９】
スケーラビリティおよびロバスト性
上述したアルゴリズムのスケールをデータセットのサイズとどのように合わせるかを調べるために、アルゴリズムを、一様ランダムにＲ３で配置したオブジェクトからなる合成データセット上で評価することができる。５つのアルゴリズムのクエリー計算量および演算量が図２Ａおよび図２Ｂに示されている。図２は、５つのアルゴリズムのクエリー計算量（図２Ａ）およびクエリー計算量（図２Ｂ）を、データセットのサイズの関数として示している。データセットは、半径
2015516102.tif 000029
の球から一様ランダムに選択される。図２Ｃは、クエリー計算量を誤りオラクルの下でｎの関数として示している。
【００８０】
図１で示した複数のアルゴリズム間にも同じ差異が存在する。ｌｏｇ  ｎに対して線形的な成長は、全ての方法に対し、エントロピーＨ（μ）に関し、クエリー計算量と演算量の双方の尺度で線形的な関係が存在することを示している。図２Ｂは、ロバストなランクネット・サーチのアルゴリズムのクエリー計算量をプロットしたものを示している。
【００８１】
本原理４００を使用してデータベース内でターゲットをサーチする第１の方法の一実施形態が図４に示されている。開始ブロック４０１は、制御を機能ブロック４１０に受け渡す。機能ブロック４１０は、ターゲットを包含するサイズを有する複数のノードのネットを構築する。機能ブロック４１０は、制御を機能ブロック４２０に受け渡し、機能ブロック４２０は、ネット内のノードのセットを選定する。ブロック４２０の後、制御が機能ブロック４３０に受け渡され、機能ブロック４３０は、ターゲットからノードのセットのうちの各ノードまでの距離を比較する。制御が機能ブロック４３０から機能ブロック４４０に受け渡され、機能ブロック４４０は、機能ブロック４３０の比較に従ってターゲットに最も近いノードを選択する。制御が機能ブロック４４０から機能ブロック４５０に受け渡され、機能ブロック４５０は、機能ブロック４４０で行われた選択に従って、ターゲットを依然として包含するサイズにネットを縮小する。制御が機能ブロック４５０から制御ブロック４６０に受け渡され、機能ブロック４６０は、ネットのサイズがターゲットのみを包含するのに十分に小さくなるまで、機能ブロック４２０、４３０、４４０、および４５０が繰り返されるようにする。ネットがターゲットのみを包含するようになったとき、方法が終了する。
【００８２】
本原理を使用してデータベース内でターゲットをサーチする第１の装置の一実施形態が図５に示され、参照符号５００によって概ね示されている。この装置は、スタンドアロンのハードウエアによって実施されてもよく、コンピュータによって実施されてもよい。この装置は、少なくともターゲットを包含するサイズを有する複数のノードのネットを構築する手段５１０を含む。この手段５１０の出力部は手段５２０の入力部と信号通信し、手段５２０はネット内のノードのセットを選定する。選定手段５２０の出力部は比較手段５３０の入力部と信号通信し、ターゲットからノードのセットのうちの各ノードまでの距離を比較する。比較手段５３０の出力部は選択手段５４０の入力部と信号通信し、選択手段５４０はノードのセットのうち比較手段５３０に応答してターゲットに最も近いノードを選択する。選択する手段５４０の出力部は縮小手段５５０と信号通信し、縮小手段５５０は選択手段５４０に応答してターゲットを依然として包含するサイズにネットを縮小する。縮小手段５５０の出力部は制御手段５６０と信号通信する。制御手段５６０は、ネットのサイズがターゲットのみを包含するのに十分に小さくなるまで、選定手段５２０、比較手段５３０、選択手段５４０、および縮小手段５５０に各々の処理を繰り返させる。
【００８３】
本原理を使用してデータベース内でターゲットをサーチする第２の方法６００の一実施形態が図６に示されている。開始ブロック６０１は制御を機能ブロック６１０に受け渡す。機能ブロック６１０はターゲットを包含するサイズを有する複数のノードのネットを構築する。機能ブロック６１０は制御を機能ブロック６２０に受け渡し、機能ブロック６２０はネット内から少なくとも１つのペアのノードを選定する。ブロック６２０の後、制御が機能ブロック６３０に受け渡され、機能ブロック６３０は複数回の繰り返しに対してターゲットから少なくとも１つのペアの各々のうちの各ノードまでの距離を比較する。制御が機能ブロック６３０から機能ブロック６４０に受け渡され、機能ブロック６４０は、複数回の繰り返しに亘って機能ブロック６３０の比較に従って、少なくとも１つのペアのノードの各々のうちターゲットに最も近いノードを選択する。制御が機能ブロック６４０から機能ブロック６５０に受け渡され、機能ブロック６５０は、機能ブロック６４０で行われた選択に従ってターゲットを依然として包含するサイズにネットを縮小する。制御が機能ブロック６５０から制御ブロック６６０に受け渡され、機能ブロック６６０は、ネットのサイズがターゲットのみを包含するのに十分に小さくなるまで機能ブロック６２０、６３０、６４０、および６５０が繰り返されるようにする。ネットがターゲットのみを包含するようになったとき、本方法が終了する。
【００８４】
本原理を使用してデータベース内でターゲットをサーチする第２の装置の一実施形態が図７に示され、参照符号７００によって概ね示されている。この装置は、スタンドアロンのハードウエアによって実施されてもよく、コンピュータによって実施されてもよい。この装置は、少なくともターゲットを包含するサイズを有する複数のノードのネットを構築する手段７１０を含む。手段７１０の出力部は手段７２０の入力部と信号通信し、手段７２０はネット内の少なくとも１つのペアのノードを選定する。選定手段７２０の出力部は比較手段７３０の入力部と信号通信し、比較手段７３０は複数回の繰り返しに亘ってターゲットから少なくとも１つのペアのノードのうちの各ノードまでの距離を比較する。比較手段７３０の出力部は選択手段７４０の入力部と信号通信し、選択手段７４０は少なくとも１つのペアのノードのうち比較手段７３０に応答してターゲットに最も近いノードを選択する。選択手段７４０の出力部は縮小手段７５０と信号通信し、縮小手段７５０は選択手段７４０に応答してターゲットを依然として包含するサイズにネットを縮小する。縮小手段７５０の出力部は制御手段７６０と信号通信する。制御手段７６０は、ネットのサイズがターゲットのみを包含するのに十分に小さくなるまで、選定手段７２０、比較手段７３０、選択手段７４０、および縮小手段７５０に各々の処理を繰り返させる。
【００８５】
本発明の現在好ましいとされている実施の形態の特定の特徴事項および態様を有する１つ以上の実施態様を提供した。しかしながら、説明した実施態様の特徴事項および実施態様は、他の実施態様にも適応させることができる。例えば、これらの実施態様および特徴事項は、他の映像用の装置またはシステムに関連して使用することもできる。実施態様および特徴事項は、規格内で使用される必要はない。
【００８６】
明細書において、本原理の「一実施形態」、「実施形態」、「一実施態様」、「実施態様」、または、その他のこの類の表現が言及されている場合、これは、実施形態に関して記載される特定の特徴事項、構造、特性などが本原理の少なくとも１つの実施形態に含まれることを意味する。したがって、明細書全体にわたって様々な箇所に存在する文言「一実施形態においては」、「実施形態においては」、「一実施態様においては」、「実施態様においては」、または、その他のこの類の表現は、必ずしも、全てが同一の実施形態について言及するものではない。
【００８７】
本明細書中で説明された実施態様は、例えば、方法またはプロセス、装置、ソフトウエア・プログラム、データ・ストリーム、または、信号において実施することができる。たとえ単一の形態の実施態様の関連でのみ説明されている場合であっても（例えば、方法としてのみ説明されている場合であっても）、説明されている特徴事項の実施態様を、他の形態で（例えば、装置またはコンピュータ・ソフトウエア・プログラム）で実施することも可能である。装置は、例えば、適切なハードウエア、ソフトウエア、およびファームウエアで実施することができる。方法は、例えば、装置で実施することができる。装置は、例えば、プロセッサなどであり、このプロセッサは、一般的には、例えば、コンピュータ、マイクロプロセッサ、集積回路、または、プログラマブル・ロジック・デバイスを含む処理装置などである。プロセッサは、また、例えば、コンピュータ、携帯電話、携帯／個人情報端末（ＰＤＡ）、さらに、エンドユーザ間での情報の通信を容易に行えるようにする他の装置などの通信装置を含む。
【００８８】
本明細書中で説明する様々な処理および特徴事項の実施態様は、様々な異なる機器またはアプリケーションで実施することができる。このような機器の例には、ウエブサーバ、ラップトップ、パーソナル・コンピュータ、携帯電話、ＰＤＡ、さらに他の通信装置が含まれる。機器が携帯用（移動用）である場合や、移動可能な乗り物に設置されている場合さえもあることが明らかであろう。
【００８９】
さらに、この方法は、プロセッサによって実行される命令によって実施可能であり、このような命令（および／または実施態様によって生成されるデータ値）は、プロセッサ読み取り可能な媒体に記憶することができる。プロセッサ読み取り可能な媒体は、例えば、集積回路、ソフトウエア・キャリア、または他の記憶装置などである。他の記憶装置は、例えば、ハードディスク、コンパクトディスク、ランダム・アクセス・メモリ（「ＲＡＭ」）、読み取り専用メモリ（「ＲＯＭ」）などである。命令は、プロセッサ読み取り可能な媒体上で現実的に実装されるアプリケーション・プログラムを形成することができる。命令は、例えば、ハードウエア、ファームウエア、ソフトウエアに存在していてもよく、これらを組み合わせたものに存在していてもよい。命令は、例えば、オペレーティング・システム、別個のアプリケーション、または、これらの２つを組み合わせたものに存在していてもよい。したがって、プロセッサは、例えば、処理を実行するように構成された装置、さらに、処理を実行するための命令を有する（記憶装置などの）プロセッサ読み取り可能な媒体を含む装置の双方として特徴付けることができる。さらに、プロセッサ読み取り可能な媒体は、命令に加えて、または、命令の代わりに、実施態様により生成されたデータ値を記憶することができる。
【００９０】
当業者であれば、実施態様が本明細書中に記載した手法を全て使用することも、部分的に使用することも可能であることが明らかであろう。実施態様には、例えば、方法を実行する命令、または、説明した実施形態のうちの１つによって生成されるデータが含まれる。
【００９１】
複数の実施態様について説明した。しかしながら、様々な改変を施すことが可能であることが理解できよう。例えば、複数の異なる実施態様の要素を組み合わせることも、補完することも、変更することも、除去して他の実施態様を生み出すこともできる。さらに、当業者であれば、本明細書において開示したものに、他の構造および処理を置き換えることができ、結果として得られた実施態様が、開示している実施態様と、少なくとも概ね同様の方法で、少なくとも概ね同様の機能を実行し、少なくとも概ね同様の結果を生み出すことが理解できるであろう。したがって、これらの実施態様およびその他の実施態様は、本明細書の開示内容から企図されるものであり、本原理の範囲に包含される。
【図１Ａ】
2015516102.tif 000030
【図１Ｂ】
2015516102.tif 000031
【図１Ｃ】
2015516102.tif 000032
【図２Ａ】
2015516102.tif 000033
【図２Ｂ】
2015516102.tif 000034
【図２Ｃ】
2015516102.tif 000035
【図３】
2015516102.tif 000036
【図４】
2015516102.tif 000037
【図５】
2015516102.tif 000038
【図６】
2015516102.tif 000039
【図７】
2015516102.tif 000040
【国際調査報告】
2015516102.tif 000041
2015516102.tif 000042