情報検索
【課題】
【解決手段】クラスタのモデルベースの概念を利用し、１以上のクエリーアイテムとして所定のアイテムが同一の分布から生成される確率を評価する式を用いてアイテムを評価するアルゴリズムが提供される。アイテムは、複数のデジタルで表される特徴Ｘｉｊを備える特徴ベクトルＸｉにより表され、方法は、クエリーアイテムを識別する入力を受信するステップと、他のアイテムが発生分布等式（Ｉ）から生成されると仮定した場合に、他のアイテムそれぞれに対して、発生分布式（Ｉ）から生成されるクエリーアイテムの特徴ベクトルＸｉｊの条件付確率の機能を有するスコアを算出するステップと、他のアイテムそれぞれのスコア、各スコアによりソートされる他のアイテムの一部あるいは総てのリスト、または最も高いスコアを有するｎ個の他のアイテムのリストを返却するステップとを備える。
【解決手段】クラスタのモデルベースの概念を利用し、１以上のクエリーアイテムとして所定のアイテムが同一の分布から生成される確率を評価する式を用いてアイテムを評価するアルゴリズムが提供される。アイテムは、複数のデジタルで表される特徴Ｘｉｊを備える特徴ベクトルＸｉにより表され、方法は、クエリーアイテムを識別する入力を受信するステップと、他のアイテムが発生分布等式（Ｉ）から生成されると仮定した場合に、他のアイテムそれぞれに対して、発生分布式（Ｉ）から生成されるクエリーアイテムの特徴ベクトルＸｉｊの条件付確率の機能を有するスコアを算出するステップと、他のアイテムそれぞれのスコア、各スコアによりソートされる他のアイテムの一部あるいは総てのリスト、または最も高いスコアを有するｎ個の他のアイテムのリストを返却するステップとを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アイテムの共通点のスコアリング（評価）に関し、特に、排他的ではないが、情報検索の分野に関し、より具体的には、関連するアイテムの用途ベースの検索に関する。
【０００２】
通常、既知の情報検索の方法は、ある基準下でクエリーに関連すると認められる文書を一群の文書内から発見することに関係する。クエリーは通常、言葉のリストから成り、典型例は、ウェブ検索または特許文献のデータベース検索である。
【０００３】
文書の関連性を家低する確率論的基準に依存する情報検索（ＩＲ）方法が、従来知られている。これらの方法は、「この文書はこのクエリーと関連する可能性はどれだけか」という質問をする。この質問に対する２つの解決手段が存在し（参照によりここに組み込まれているJohn Lafferty and Chengxiang Zhai (2003) Probabilistic relevance models based on document and query information、Language Modelling Information Retrieval, Kluwer International Series on Information Retrieval, Vol. 13に説明されているように）、
１）各クエリーに対して２つのモデルが評価され、一方が、関連する文書をモデル化し、他方が、関連しない文書をモデル化し、文書は、関連性の事後確率によりランク付けされ、
２）各クエリーに対して言語モデルが評価され、ランキングの操作手順は、各文書のモデルにしたがって、クエリーに割り振られた可能性により文書を整理することである。
特に、これらの解決手段双方は、多くの統計モデルのパラメータを評価する必要がある。
【０００４】
データベース内のテキストクエリーを検索する場合に生ずる一つの問題は、クエリーが、クエリー内の言葉に対するヒットを有する多くの文書を返却することである。これらは、クエリーが多数の概念クラスタ内でヒットを生成するため、ユーザが実際に思っていたものに関連し、または関連しない場合があり、これらの一部のみが、ユーザが意図するものである。この問題の解決手段が、例えば、参照によりここに組み込まれるＵＳ−Ｂ−６３８５６０２で提案されており、ここでは、このような結果は、動的な分類を用いて表される。これは、検索結果の属性に基づいており、好適なグループ化またはクラスタリング技術を用いる。検索結果は、ユーザが探しているものを選択するのに役立つように構成された分類で表される。しかしながら、分類は、通常管理されていないクラスタリングアルゴリズムにより生成されるため、分類が、ユーザが実際に想定したものに対応しないことがある。
【０００５】
参照によりここに組み込まれているＧｏｏｇｌｅ（登録商標）セットは、いくつかの例からアイテムセットを自動的に生成するＧｏｏｇｌｅ（登録商標）が提供する実験的なツールである。ユーザは、一組の物からいくつかのアイテムを入力し、インタフェースは、セット内の他のアイテムを予測しようとする。アイテムの僅かなセットで構成されるクエリーの場合、アルゴリズムは、クエリーにより規定されるセットに属する関連するアイテムの多くのセット（以降、クラスターと称する）を返却する。例えば、車の３つのブランドの場合、インタフェースは、車の追加のブランドを含む拡張されたセットを返却する。ユーザは、拡張されたセット内の任意のアイテムをクリックでき、そのアイテムによりウェブ検索を実行する。しかしながら、得られる検索の可能性は、拡張されたセットの検索されたアイテムのうちの一つを対象とするウェブ検索の実行に限られる。
【０００６】
従来のテキストベースのＩＲクエリーは、論理演算子により組み合わされたキーワードに基づいている。クエリー内のアイテムと同じ概念クラスタに属するアイテムを検索するという意味で共通する演算子を関数演算子として備える検索ツールあるいは一般的なアプリケーションを提供することは有益である。これは、クエリー自体が、結果が発見されるクラスタを規定する効果的な検索メカニズムを提供する。すなわち、このようなクエリーは、クエリーのアイテムおよび返却されるアイテムが、同じ概念クラスタにどれほどヒットするかに関連する共通するスコアに基づいている。
【発明の開示】
【課題を解決するための手段】
【０００７】
本発明の第１の態様では、請求項１に定義するように、クエリーと他のアイテムとの共通点をスコアリングするコンピュータが実施する方法が提供される。
【０００８】
アイテムに割り振られるスコアは、クエリーアイテムおよび他のアイテムが、同じ発生分布または統計モデルから生成される可能性に依存する。オーディオ符号化および音声認識の分野では、よりよい復元および認識が、人間の聴覚システムが機能する方法を考慮することにより実現できることが、長い時間をかけて確立されている。最近の実験的証拠は、人々は、同じ統計分布から生成されるアイテムを、心理学文献（A generative theory of similarity. Kemp, C., Bernstein, A., and Tenenbaum, J.B.(2005)。参照によりここに組み込まれている認知学会の２７周年の会議の議事録。）に提案されている他の手順を用いて生成されたアイテムよりも共通すると判断する示している。オーディオ符号化または音声認識の理論と同様の意図では、本発明の共通するスコアは、人々がどのように類似を判断するのかという心理学的な証拠により生じる。
【０００９】
発生分布は、データからこれらパラメータを評価するよりも、多くのパラメータにより決定され、スコアは、パラメータの総ての取り得る値に対して平均化され、これにより、パラメータの評価に関連する問題を阻止する。これはしばしば、「パラメータを無視する」または完全なベイズ的アプローチと称される。さらに、心理学的な証拠（参照によりここに組み込まれているGeneralization, similarity and Bayesian inference. J.B. Tenenbaum, T. L.Griffiths (2001), Behavioral and Brain Science, 24 pp. 629-641）は、人々が証拠を一般化し、（パラメータ設定に応じて）代替的な仮説を平均化することにより類似性を判断する。したがって、類似するスコアを算出する完全なベイズ的アプローチは、人間の状態および類似性の認知によく調整されていると見なしてもよい。
【００１０】
発生分布はベルヌーイ分布でもよく、パラメータは、ベータ分布より先の対応する共役（conjugate）で平均化してもよい。ベルヌーイ分布の場合、発明者は、コンピュータ的に強く、処理できないことがない関連する積分は、行列乗算により効果的に実現可能であるということを理解した。
【００１１】
本発明の別の態様では、請求項５に定義するように、クエリーと、１またはそれ以上のアイテムとの類似性をスコアリングするコンピュータが実施する方法を提供する。
【００１２】
スコアリングする方法は、アイテムが２項素性ベクトル（binary feature vector）により表される場合、発生分布において類似性のスコアリングの完全なベイジアン処理を実施する行列乗算に関連することが有利である。したがって、この方法は、行列演算のスコアの算出に関連する総ての積分を実施する。
【００１３】
スコアリング方法は、通常ではあるがアイテムの表示が希薄である場合、より効率的に実施してもよい。以下で使用するように、希薄は、入力の大部分が０（あるいは別の定数）であり、少なくとも特徴の３分の２が０（あるいは一定値）である表示を意味している。特に、非常に大きなデータセットの場合、アイテムは、クエリーアイテムと関連する少なくとも規定の数の特徴を有するアイテムのみがスコアを付されるように前処理される。これは、例えば、逆のインデックス（inverse index）を用いて実現できる。
【００１４】
ベータ分布は、２つのハイパーパラメータαおよびベータにより特徴付けられる。このパラメータは、ベイジアン分析、例えば証拠の最大化（evidence maximisation）を用いて、標準的な方法によりデータにフィットし、または試験およびエラーを用いて発見できる。ハイパーパラメータを設定する一の特定の方法は、アイテムに対するこの特徴の平均値に比例する各特徴に対応するαパラメータを設定し、１マイナス平均に比例するような各特徴に対応するβパラメータを設定する。これは、ハイパーパラメータを設定する効果的な方法であり、パラメータ分布は、データセットの構造に対する事前情報を含んでおり、ハイパーパラメータは、比例定数を調整することにより微調整できる。
【００１５】
アイテムは、ウェブページ、画像、既知および機能を有する遺伝子またはタンパク質、既知および機能を有する医薬品分子、病歴、または言葉若しくは映画のタイトルなどのデータの他のアイテムでもよい。
【００１６】
本発明は、物理的なレベルにおいて、アイテムあるいはアプリケーションの特定の種類に全く依存しないことは明らかであろう。物理的なレベルにおいて、アイテムは、（アプリケーションに応じて、様々な実在の物を表す）単にデジタルビットのグループであり、本発明は、同一のランダムな処理により生成される可能性における類似性を決定する。詳細なアルゴリズムは、ランダムアクセス（例えば、独立したベルヌーイ試行）のために選択される分析モデルにより決まるが、ビットまたはアイテムのグループに関連する目的により決定されるものではない。
【００１７】
予備的な検索クエリーの検索結果のサブセットを選択することにより、クエリーは、選択された検索結果として、同一の概念クラスタに属する可能性のあるアイテムに洗練することが有利である。
【００１８】
前記方法は、所定のキーワードを画像のサブセットに付すことにより、キーワードを用いた画像検索を提供することが有利である。キーワード検索の結果は、前述したような共通点検索の入力として用いてもよい。この方法では、大きくてラベルが付されていない画像セットからの画像は、最初に小さくてラベルの付されたサンプル画像セットを検索することにより検索される。この方法はさらに、データセットを整理し、あるいは注釈を付すのに利用してもよい。
【００１９】
本発明のさらなる態様によると、請求項２１に記載のコンピュータシステムと、請求項２２に記載のコンピュータプログラムと、請求項２３および２４に記載のコンピュータが読み取り可能な媒体および信号が提供される。
【００２０】
本発明のさらに別の態様は、請求項２５、２６および２７にそれぞれ記載の画像を検索する方法、データセットを整理する方法、およびアイテムにラベルを付す方法を利用する。
【００２１】
本発明の特定の実施例は、例示的な方法により、添付図面を参照してここに説明される。
【発明を実施するための最良の形態】
【００２２】
以下の詳細な説明では、請求の対象を完全に理解するために、多くの特定の詳細が説明されている。しかしながら、当業者であれば、請求の対象は、これらの特定の詳細なしに実施してもよいことは理解できるであろう。他の実施例では、周知な方法、処理、要素、および／または回路は、詳細には説明されていない。
【００２３】
以下の詳細な説明の一部は、コンピュータおよび／またはコンピュータシステムメモリ内のコンピュータシステム内に格納されたデータビットおよび／またはバイナリデジタル信号の処理のアルゴリズムおよび／または象徴の観点で示されている。これらのアルゴリズムの記載および／または象徴は、彼らの取り組みの本質を本分野の他の当業者に伝えるために、データ処理分野の当業者により利用される技術である。ここに記載されているアルゴリズムは通常、矛盾のない処理シーケンス、および所望の結果に通じる同様の処理と考えられる。操作および／または処理は、物理量の物理的処理を含んでもよい。通常、必ずしも必要ではないが、これらの量は、格納、移動、結合、比較および／または操作可能な電気信号および／または磁気信号でもよい。これらの信号を、ビット、データ、値、要素、シンボル、文字、用語、数、数字等と呼ぶことは、主に一般的な用途のために有用であることが何度の証明されている。しかしながら、これらの語句および同様の語句総ては、適切な物理量に関連し、単に有用なラベルに過ぎないと理解すべきである。特別に明示しない限り、以下の説明か明らかなように、本明細書全体を通して、「処理」、「演算」、「計算」、「決定」等の用語を利用した説明は、コンピュータプラットホームのプロセッサ、メモリ、レジスタ、および／または情報を記録し、転送し、および／または表示する装置内の物理的な電気量および／または磁気量および他の物理量として表されるデータを操作および／または変換するコンピュータまたは同様の電子演算装置などのコンピュータプラットフォームの動作および／または処理を意味する。
【００２４】
概要
多くのアイテムＤを検討する。アプリケーションに依存して、セットＤは、ウェブページ、映画、人々、言葉、タンパク質、画像、または誰かがクエリーを形成したいと願う他のオブジェクトで構成してもよい。ユーザは、アイテムのサブセットＤＣ⊂Ｄの形式のクエリーを提供する。ＤＣ内の要素が、データ内の概念、クラスあるいはクラスタの例であると仮定する（これより「クラスタ」の語句が使用される）。アルゴリズムは、セットＤＣ、すなわち、ＤＣ内の総ての要素および同じクラスタ内のＤ内の他の要素を含むいくつかのセットＤ’Ｃ⊂Ｄに完了を提供する。
【００２５】
特定の情報検索の問題を回ケルするアルゴリズムの目的を考えることができる。他の検索の問題のように、出力はクエリーに関連すべきであり、一つの可能性は、クエリーとの関連性によりランク付けされた上位の数アイテムに出力を限定することである。
【００２６】
ベイジアンセット
以下に説明するアルゴリズムは、参照を容易にするために剰余（remainder）内の「ベイジアンセット」と称する。
【００２７】
Ｄをアイテムのデータセットとし、ｘ∈Ｄをこのセットからのアイテムとする。ユーザは、Ｄの小さなサブセットであるクエリーセットＤＣを提供すると仮定する。目的は、要素がＤＣを含むセットにどれだけ「フィット」するのかにより、Ｄの要素をランク付けすることである。直観的に、タスクはクリアであり、セットＤが総ての映画のセットでありクエリーセットが２つのアニメのディズニー映画で構成される場合、他のアニメのディズニー映画は、上位にランク付けされると予測する。
【００２８】
ＤＣがいくつかのクラスタに属すると仮定すると、我々は、ｘもＤＣに属する可能性がどれだけなのか知りたい。これは、ＤＣの場合、クラスタに属するｘの可能性であるｐ（ｘ｜ＤＣ）により測定される。この可能性のみによるアイテムのランク付けは、いくつかのアイテムが他のよりも可能性が高いため、ＤＣに拘わらず精度が低い。例えば、最も精度の高いモデルでは、文字列の可能性は、文字の数と共に減少し、画像の可能性は、ピクセルの数と共に減少し、連続する変数は、測定される精度と共に減少する。これらの影響を取り除くために、比
を計算し、ここで分母は、ｘの事前確率である。
【００２９】
ベイズの規則を用いて、このスコアは、
のように表すことができ、これは、同じクラスタに属し、ｘおよびＤｃに属するｘおよびＤｃの観察の同時確率の比として解釈できる。最後に、ｘに依存しない乗法定数により、スコアは、
と表すことができ、これは、ｘの場合（すなわち、ｘの可能性）のクラスターに属するクエリーセットの可能性である。
【００３０】
前述の説明は、ｐ（ｘ｜Ｄｃ）およびｐ（ｘ）などの量をどのように算出するかについての取り組んではいない。クラスタを定義するモデルに基づく方法は、クラスタ内のデータポイント総てが、独立して到来し、パラメータ化された統計モデルまたは分布から分配されると仮定する。パラメータ化されたモデルは、ｐ（ｘ｜θ）であり、ここで、θはパラメータである。Ｄｃ内のデータポイントが、一つのクラスタに属する場合、この定義下では、これらは、パラメータの同一の設定から生成されるが、設定は未知である。
【００３１】
一つの可能な解決手段は、クエリー自体からパラメータを算出することであり、これは、小さなクエリーには問題である。パラメータ算出に依存しない、より理にかなった解決方法は、完全にベイズ的アプローチを利用することであり、すなわち、パラメータ値、ｐ（θ）の事前密度（prior density）または分布により重み付けされた可能性のあるパラメータ値を平均化することである。これらを考慮し、確率の基礎的な法則を利用することにより、我々は、
に達する。
【００３２】
これらの等式を用いることにより、ベイジアンセットアルゴリズムは、以下のように表すことができ、総てのアイテムまたは総てのアイテム
のスコアを計算し、例えば、
【００３３】
セットの他の各アイテムの特徴ベクトルＸｉの場合、前述のスコアは、クエリーに依存しない乗法定数に応じて、特徴ベクトルＸｉの条件付確率として表すことができるのは等式（３）から思い出されるであろう。基本的なパラメータ化された分布から生じるような特徴ベクトルを考慮すると、他の各アイテムの各特徴ベクトルが発生分布ｐ（Ｘｉ｜θ）から生じる場合、スコアは、パラメータθにより定まる発生分布ｐ（Ｘｉ｜θ）から生じるクエリーアイテムの特徴ベクトルＸｉの条件付確率の関数としてみてもよい。
【００３４】
従来よりも従順で精密な完全なベイズ法に関する２つの共通の懸念が存在する。本発明において、発明者は、完全なベイズ処理は、分析および算出双方に効果的であり、従来の分布の選択肢に比べて精密過ぎることのない方法で実現できることが分かった。
１．多くのモデルの場合、積分（４）から（６）は分析的である。実際に、モデルの場合、我々は以下のバイナリデータを考慮し、発明者は、総てのスコアを計算することにより、単一の行列の複雑さを低減できることを発見した。
２．精度の高いモデルｐ（ｘ｜θ）を従前のモデルｐ（θ）選択することは、明らかに有益であるが、これらは複雑である必要はない。以下に示す結果は、単純なモデルと従前のモデルの調整をほぼ必要としないことにより、競争力のある検出結果が得られることを示している。実際には、従来のモデルを曖昧にするが、Ｄ内のデータの平均を中心とする単純な経験的発見（empirical heuristic）が利用される。
【００３５】
バイナリデータ
前述したように、ベイジアンセットアルゴリズムは、排他的ではないが、希薄なバイナリデータに特有であることがわかる。この種のデータは、各アイテムの特徴が存在し、あるいは存在しないことにより特徴付けられる大きなデータセットの自然な式である。
【００３６】
各アイテムｘｉ∈Ｄが、バイナリベクタｘｉ＝（ｘｉ１，・・・，ｘｉＪ）であり、ｘｉｊ∈｛０，１｝であると仮定すると、ｘｉの各要素は、独立したベルヌーイ分布である。
ベルヌーイ分布のパラメータの前の共役（conjugate）は。データ分布であり、
ここで、αおよびβは、従来のハイパーパラメータであり、ガンマ関数は、階乗関数を一般化したものである。Ｎ個のベクトルで構成されるクエリーＤｃ＝｛Ｘｋ｝の場合、以下を示すことは容易であり、
ここで、
であり、
である。アイテムｘ＝（ｘｉ１・・・ｘｉＪ）の場合、ハイパーパラメータが明示的に示されたスコアは、以下のように算出できる。
この取っ付きにくい式は劇的に単純化できる。我々は、ｘ＞１の場合、
を利用することができる。各ｊに対して、我々は、２つの事例ｘｉｊ＝０およびｘｉｊ＝１をそれぞれ検討できる。ｘｉｊ＝１の場合、我々は寄与（contribution）
を有する。ｘｉｊ＝０の場合、我々は寄与（contribution）
を有する。これらを組み合わせることにより、我々は、
を得る。スコアのログは、ｘｉ内で線形的である。
ここで、
であり、
である。我々が、総てのデータセットをＪ列およびＭ行の一の大きな行列Ｘに入れる場合、我々は、Ｘの単一の行列のベクトル乗算と、クエリーベクトルｑを用いて、総てのアイテムのためのログスコアのベクトルｓを算出できる。
各クエリーＤＣは、ベクトルｑの計算に対応する。ｃを追加することは、スコアのランク付けに影響しないため省略してもよい。また、これは、クエリーが希薄である場合、ｑの多くの要素は、クエリーから独立したｌｏｇβｊ−ｌｏｇ（βｊ＋Ｎ）と等しいため、（式を予め計算することにより）効率的に行うことができる。
【００３７】
希薄なデータセットの場合、行列の乗法は、非常に効率的に行うことができる。我々は、希薄を行列の３分の２または多くの特徴要素がゼロであることと定義しているが、行列は、しばしばそれよりも希薄になることがある（例えば、ゼロでない行列の要素が１％）。希薄な行列が、エントリの３分の２が（ゼロとは反対に）定数であるような構造の場合、この行列は、定数を引き算することにより希薄な行列に変換できる。効率的なアルゴリズムは、ｘｉｊ≠０（例えば、Ｍａｔｌａｂの希薄な行列の実施例）となるために、総てのインデックス用のリスト（ｉ，ｊ，ｘｉｊ）で構成される希薄な行列データ構造を利用する。０のエントリは格納されず、メモリを占有しない。希薄な行列ベクトルの乗法は、ゼロでない要素に対してループし、対応するベクトル要素により掛け算して合計する。このアルゴリズムは、マトリックスの多くのゼロでない要素の線形時間である。参照によりここに組み込まれているＭａｔｌａｂ（登録商標）の基本的な線形代数ルーチンであるＢＬＡＳおよびＬＡＰＡＣＫと、Ｓｐａｒｓｅ ＢＬＡＳ：http://www.netlib.org/sparse-blas/を参照。
【００３８】
非常に大きなデータセット（例えば、何百万のエントリ）の場合、Ｉｎｖｅｔｅｄ Ｉｎｄｅｘ（http://www.nist.gov/dads/HTML/invertedIndex.html、参照によりここに組み込まれている）が利用でき、これは、例えば、ウェブ上のテキスト文書のための情報検索で利用される標準的なデータ構造である。これは、各文字あるいは特徴が、これらの現れる文書のリストを伴うように構成された、例えば、一群の文書（すなわち、アイテム）内の文字（すなわち、特徴）の希薄な式である。検索を実行する場合、総てのアイテムを検索するのではなく、クエリーに関連する特徴を有するアイテムのみを評価する必要があり、これにより、アルゴリズムをより一層効率的にする。
【００３９】
最後に、スコアにより、データセット内のＭ個のアイテム全部をソートする必要はなく、検索のためのいくつかの上位のアイテムを発見する必要がある。上位のいくつかのアイテムを発見する所定のスコアベクトルはＯ（Ｍ）であり、Ｏ（ＭｌｏｇＭ）である総てのアイテムをソートするよりも非常に効率的である。アルゴリズムは、Ｍに対して１回のループを必要とし、現在のトップスコアアイテムのリストを更新する。
【００４０】
前述のアルゴリズムは、ハイパーパラメータ（例えば、αおよびβ）の選択を必要とし、パラメータに対する先行する分布を定義する。ハイパーパラメータは、証拠の最大化（evidence maximisation）などの標準的なベイジアン法を用いて発見できる一方、行列Ｘの構造の従来の知識を用いる単純な方法が利用できる。
１）Ｘの列を平均化するデータの平均Ｍを計算する。ベクトルｍは、１×Ｊであり、Ｊは、Ｘの行の数である。
２）αｊ＝ｃｏｎｓｔ・ｍｊを設定する。
３）βｊ＝ｃｏｎｓｔ・（１−ｍｊ）を設定する。
ここで、ｃｏｎｓｔは、試行およびエラーにより決定でき、あるいは「証拠（evidence）」に基づいてベイズ処理を用いて最適化できる定数である。以下に示す例では、定数は、ｃｏｎｓｔ＝２に設定される。
【００４１】
通常、ハイパーパラメータは、ｐ（θ）がデータの適切なモデルを与えるように設定される。すなわち、これらのハイパーパラメータを用いてｐ（ｘｉ）から生成することにより、凡そ実際のデータと同じ統計値のＸの列が生じる。
【００４２】
前述したバイナリデータの特定の実施例は、以下の行に沿ってＭＡＴＬＡＢ（登録商標）で実現でき、データの入力、出力および処理が省略される。
【００４３】
アプリケーション
前述したベイジアンセットアルゴリズムは、この基礎的な概念クラスタの例で構成されるクエリーに基づいて、基礎的な概念クラスタの要素を発見する必要のある任意の状況に適応できる。アプリケーションは、例えば、同じような概念に関連する言葉、あるいは特定の特徴を共有する映画を発見するステップを含む。これらの例は、以下に示す結果に関連して説明される。
【００４４】
アルゴリズムは、利用される式により、すなわち、行列Ｘの行のバイナリ値により符号化される特徴により主に区別される多くの他のアプリケーションに適用してもよい。様々なアプリケーションでは、行列Ｘは以下を示す。
・ウェブサーチ：各列はウェブページを表し、各行はウェブページの特徴を表し、例えば、文字が、メタタグ、問題のページおよび／または、特定のキーワードが問題になっているウェブページの所定の閾値よりも、より頻繁に現れれるページにリンクしたウェブページにリンクしたウェブページに存在する。ウェブページ用のキーワード検索を実施することにより、リストに関連するページを節約でき、リスト内の総てのアイテムに類似する総てのページのためのクエリーを節約できる（以下を参照）。
・医療エキスパートシステム：列は患者を表し、表は、対応する病歴の特徴を表し、例えば、特定の状態あるいは症状の有無、および／または特定の生理学測定値が、所定の範囲の値内にある。値の範囲は、通常の値と病的な値を区別できるが、値の範囲の僅かな違いが認識される。特定の病気で苦しむ患者の特徴ベクトルを有するシステムを提供することにより、病気にかかる他の人の可能性を予測できる。
・遺伝子／タンパク質の機能分析：列は、遺伝子またはタンパク質、例えばヒトゲノム内で特定される遺伝子を表し、行は、特定のベースシーケンスなどのゲノムマーカー（genomic marker）、または遺伝子内の特定の位置の特定のシーケンスの存在を表す。同様にタンパク質の場合も、行はタンパク質の構造または機能的な特徴を表す。クエリーは、既知の機能を有する遺伝子を選択することにより、またベイジアンセットの同様のスコアを用いることにより定式化でき、試験対象として未知の機能の遺伝子を特定し、これらが同一または同様の機能を有するかを検証する。
・創薬：列は分子を表し、行は分子の特定の構造的な特徴あるいは機能的な影響の有無を表す。クエリーは、所望の機能あるいは治療効果を有することが分かっている選択された医薬品分子に基づく。返却された最も高いスコアの分子は、それらの活動を試験する対象として用いることができる。
・画像：列は、個人の画像を表し、行は、標準的な画像処理技術を用いて、画像から抽出される２項素性（binary featture）を表す。画像処理により画像から抽出された２項素性は、ユーザにとって意味がないため、予備的なキーワード検索は、以下に詳細に説明するように実施される。
・シソーラス：列は言語の単語を表し、行は単語の特徴を表す（以下を参照）。クエリーは、いくつかの単語を用いて定式化でき、クエリー内の総ての単語の共通の意味に関連する選択肢を返却する。
・電子商取引のための検索ツール：列は、購入に利用可能な特定のアイテムを表し（例えば、不動産、デジタルカメラ、ヨット、ホテル滞在、レストランの予約、映画チケット）、行は、アイテムの特徴を表す（例えば、位置、重量、価格）。所望の不動産を有するアイテムを選択することにより、同じような特徴を有する他のアイテムを発見することが可能である。不動産を例示的なアプリケーションとすると、現在の検索は郵便番号に依存している一方、特定の道路または他の位置は、購入者により直接関係する。購入者は、最初の検索から不動産の選択を指定し、彼らの要求により合致する他のものを発見する。
・人間の人格のための検索ツール：列は個人を表し、行は当該個人の重要な特徴を表す（例えば、特徴ベクトル、能力、興味により特定されるような様子）。所望の特徴を有する数人を選択することにより、同じような他の人を発見することができる。これは、オンラインデート、俳優の発見、モデルの発見、特定の業界の専門家の発見、潜在的な犯罪者の特定または他の警察活動、および本土防衛主導に利用してもよい。
・投資の選択：列は投資物件を表し（例えば、株、債権、デリバティブ）、行は、過去の実績、分野、成熟度などの投資物件の特徴を表す。いくつかの例示的な投資物件を選択することにより、システムは、ユーザに代替的な同様の物件を提供する。
・企業検索：列は企業を表し、行は企業の特徴を表す（例えば、産業、生産高、株価）。一組の企業を選択することにより、同様の企業を発見することが可能である。これは、調査、例えば、企業の有望な競争相手全部を見つけるのに有用である。これはまた、処理を用いる投資決定に有用である。
・特許検索：列は、単一の特許あるいは特許ファミリーを表し、行は、書誌データおよび／または特許の内容を表す。いくつかの特許が特定の分野に関連することが分かった場合に、これらを前述した検索アルゴリズムに提供し、同一領域を網羅する同様の特許を検索してもよい。
・推薦者システム：列は商品またはサービスを表し、行はその特徴を表す。購入決定（例えば、オンラインでの本の購入歴）、検索決定（例えば、検索歴の記録）または示された好み（例えば、ニュース、音楽等）のいずれかにより示された事前の関心に基づいて、関心のあるアイテムを個人に提案することが可能である。例えば、最近検索され、あるいは購入されたアイテムは、ベイジアンセットアルゴリズムのクエリーセットとして利用してもよい。
・顧客分析：列は、ビジネスの顧客を表し、行は、顧客の特徴に対応する（例えば、購入歴、個人の特徴、好み）。所望の特徴を有する一群の顧客を選択することにより、より広い同様の顧客を推定することが可能である。これは、例えば、既存の顧客に製品を販売すべく、ある地域で販売運動（例えば、ダイヤルアップインターネットの顧客にブロードバンドのインターネットアクセスを提供する）が行われる場合に有用である。促進を行う個人のグループを作ることにより、企業は、別の地域および市場の同様の顧客を確認でき、コストを低減し、理解する可能性を増加させる。
・音楽検索：列は曲を表し、行はその特徴を表す。各曲を適切な特徴ベクトルに変換することにより、音楽の選択を指定し、例えば、同じような感覚を有する他の曲を検索できる。
・研究者の出版物に基づいて、同じような主題に取り組む研究者を発見すること。（文学作品、科学論文またはウェブページの）著者のスペースは、同様のテーマを書き、関連する研究分野で働き、または共通の興味あるいは趣味を共有する人々のグループを発見すべく検索される。
・同様の論文のクラスタのための科学文献の検索：キーワードを提供する代わりに、ベイジアンセットを用いた例により検索できる：一部の関連する論文は、いくつかのキーワードよりも充実した方法により主題を取得できる。
・ここに記載されているベイジアンの検索方法を用いたタンパク質データベースの検索であり、ＵｎｉＰｒｏｔ（一般的なタンパク質のリソース（Universal Protein Resource））完全に新規なアプローチであり、「世界で最も包括的なプロテインに関する情報のカタログ（world's most comprehensive catalog of information on proteins）」が作られた［http://www.uniprot.org］。各プロテインは、ＧＯ（遺伝子存在論（Gene Ontology））注釈、ＰＤＢ（タンパク質データバンク）構造情報、キーワード注釈、および主要なシーケンス情報から由来する特徴ベクトルにより表される。ユーザは、いくつかのタンパク質の名前を与えることにより、データベースに問い合わせることができ、例えば、生物学的な特性を共有し、システムは、その特徴に基づいて、これらの生物学的な特性を共有する他のタンパク質のリストを返却する。特徴は、注釈、シーケンス、および構造情報を含むため、システムにより返却されるマッチ（match）は、通常のテキストのクエリーよりも膨大な情報を有し、したがって、より複雑な関連性を得ることができる。例えば、酵母のような特徴を示す２つの仮定のタンパク質に基づいてＵｎｉｐｒｏｔに問い合わさせし、我々のシステムは、自動的に分類「ＣＹＳ３酵母」に合致する他のタンパク質を検索するために一般化する。従来のキーワードに基づくアプローチを用いたこのようなマッチを発見することは非常に困難である。
【００４５】
図１を参照すると、ベイジアンセットのアルゴリズムは、ステップ１０において、１以上のクエリーアイテムを入力として用い、ステップ２０において、ベイジアンセットのアルゴリズムを用いて（入力クエリーのアイテムを含む可能性のある）各アイテムのスコアを計算する。ステップ３０では、アルゴリズムは、好適にはソートされた、ｎ個の最も高いスコアを有するアイテムの上位ｎ個（例えば、ｎ＝１０）リストを返却するか、あるいはユーザに表示するため、あるいは他のアルゴリズムにより利用されるスコア自体を返却する。
【００４６】
図２を参照すると、ステップ２では、従来の種類の検索、例えば、キーワード検索または他の好適な種類の検索が初めに実施され、検索結果のリストをユーザに返却する。次に、ステップ４において、ユーザが１またはそれ以上の有望な検索結果を選択し、選択が得られる。次に、ステップ６において、選択された検索結果が、入力クエリーとして用いられ、アルゴリズムは、図１のステップ１０に従い、前述したベイジアンセットのアルゴリズムにより、総ての検索結果を評価することにより、検索の精度を高める。
【００４７】
例えば、特定の実施例では、ウェブ検索インタフェースは、各検索結果に近い選択ボックス追加的に提供する従来のキーワード検索を提供する。次に、ユーザは、有望な検索結果を選択し、ウェブページにアクセスして、これらの結果を、ユーザのコンピュータに存在するアプレット、またはウェブサーバに提供し、前述した、および図１に関連するベイジアンセットのアルゴリズムにより、クエリーの精度を高める。
【００４８】
前述したように、提案された２項素性のセットはユーザには意味がないため、画像を検索する場合、画像の検索時には特別な考慮がなされる。この潜在的な問題を克服すべく、画像のサブセットは、各画像に関連する言葉のセットによりラベルが付される。未だ言葉が関連付けられていないが、前述したように２項素性が定義されている画像のラベルの付されていない大量のデータセットが存在する状況が予想される。
【００４９】
図２のステップ２に対応する最初のステップでは、ユーザは、テキストクエリー、例えば「ピンクのバラ」を入力し、アルゴリズムは、予備的な検索として、言葉のラベルを有するラベルが付されたデータセット内の総ての画像セットを発見する。次に、このクエリーの検索結果は、例えば、ラベルの付されていない大量のデータベースから最も高いランキングの１０の画像を返却するベイジアンセットのアルゴリズム用の入力クエリーとして利用される（ステップ１０）。勿論これは、図２のステップ４および６と組み合わされ、ユーザは、ベイジアンセットのアルゴリズムに対する入力クエリーとして、テキストクエリーにより返却される画像のサブセットを選択してもよい。
【００５０】
画像の特徴ベクトルは、２種類のテクスチャの特徴、例えば、４８のガボール（Ｇａｂｏｒ）テクスチャの特徴および２７のタムラのテクスチャの特徴や、例えば、１６５のカラーヒストグラムの特徴を用いて定義してもよい。参照によりここに組み込まれているH. Tamura, S. Mori, and T. Yamawaki（Texutual features corresponding to visual perception. IEEE Trans on Systems, Man and Cybernetics, 8:460-472, 1978）に示されているように、粗くて対照的な方向性を有するタムラの特徴が、９（３×３）タイルごとに計算される。６つのスケールセンシティブ（scale sensitive）および４つのオリエンテーションセンシティブ（orientation sensitive）のガボールフィルターが各画像位置に利用され、得られたフィルタ応答の分布の平均値および標準偏差を算出する。これらのテクスチャの特徴の算出の詳細については、参照によりここに組み込まれているP. Howarth and S. Ruger (Evaluation of texture features for content-based image retrieval. In International Conference on Image and Video Retrieval(CIVR), 2004)を参照。カラーの特徴の場合は、ＨＳＶ（Hue Saturation Value）３Ｄヒストグラム（参照によりここに組み込まれているD. Heesch, M. Pickering, S. Ruger, and A. Yavlinsky. Video retrival with a browsing framework using key frame. In Proceeding of TRECVID, 2003.2を参照）であり、色ごとに８つのビン（bin）が存在し、値ごとに５つ存在し、彩度が算出される。通常、最も値の低いビンは、人が区別し辛いため、色に分割される。
【００５１】
この方法により算出される特徴ベクトルは実数値である。２４０次元の特徴ベクトルは、画像ごとに算出され、データセット内の総ての画像の特徴ベクトルは、事前に処理してもよい。この処理ステージの目的は、有益な方法によりデータを２値化することである。最初に、データセットの各特徴の歪度が算出される。特定の特徴が確実に歪められる場合、パーセンタイル値が１００（１００−ｐｔｈ ｐｅｒｃｅｎｔｉｌｅ）以上、例えば、パーセンタイル値が８０の特徴の値は、値「１」をその特徴に割り当て、残りは、値「０」をその特徴に割り当てる。特徴が負に歪められる場合、パーセンタイル値が１００よりも小さい、例えば、パーセンタイル値が２０の特徴の値は、値「１」を割り当て、残りは、値「０」を割り当てる。この処理は、完全な画像データのセットを希薄なバイナリ行列に変更し、これは、各画像をデータセットの残りから最も区別する特徴に集中する。
【００５２】
ｐは、例えば異なるデータセットのために、異なる値が設定され、ｐの上下の値は、同一である必要はなく、すなわち、正に歪んだデータ用の１００−ｐ１と、負に歪んだデータ用のｐ２を有することは理解されるであろう。さらに、前述したような実数値の特徴ベクトルを２値化するアプローチは、画像データに制限されないが、特徴ベクトルに含まれる実数値のデータに適用できる。希薄なデータを取得すべく、パーセンタイル値の閾値は、正に歪んだデータの場合、５０％、好適には７０％よりも大きくすべきである。同様に、パーセンタイル値の閾値は、負に歪んだデータの場合、５０％、好適には３０％よりも小さくすべきである。得られた特徴ベクトルは、希薄であることが好適である。
【００５３】
当業者であれは、ＡＮＤあるいはＯＲ演算子により記載された単一の言葉あるいは複数の言葉を検索して、キーワード検索の異なるアプローチが可能であることが分かるであろう。さらに、画像検索の結果は、マッチのリストから最高のマッチを選択し、これらのマッチを新しいベイジアンセット検索のクエリアイテムとして用いることにより、精度を高めることができる。ユーザがデータベースの画像を検索すると、ラベルの付されていない画像は、スコアの高い画像を検索のキーワードと関連付けることにより自動的にラベルが付される。
【００５４】
ベイジアンセット以外のアルゴリズムにより生成される共通点の測定は、前述した画像検索技術に関連して用いられる。さらに、画像の他の特徴、例えば、ＳＩＦＴフィルタのフィルタ応答から生成される特徴を用いることができる。参照によりここに組み込まれているDavid G. Lowe, "Distinctive image feature form scale-invariant keypoints," International Journal of Computer Vision, 60, 2(2004), pp.91-110および"Method and apparatus for identifying scale invariant features in an image and use of same for locating an object in an image", David G. Lowe, US-B-6,711,293を参照。ベイジアンセット方法は、特徴の特定のセットの使用に限られない。また、前述した画像検索アルゴリズムは、K.A. Heller and Z. Ghahramani(2006)" A Simple Bayesian Framework for Content-Based Image Retrieval", In the IEEE Conference on Computer Vision and Pattern Recognition(参照によりここに組み込まれているCVPR 2006)に記載されている。画像検索および画像に注釈を付す方法を実施する典型的なシステムは実現され、www.inference.phy.cam.ac.uk/vr237/でオンライン化されている。
【００５５】
ベイジアンセットのアルゴリズムは、前述したようなデータセットを整理する方法の基礎として用いてもよい。
【００５６】
特定のラベルｗが付されたアイテムＤ_ｗのセットを考える。このセットのいくつかのアイテムは正確にラベルが付されている一方、いくつかのラベルは誤っており、あるいはノイズである。このようなノイズによるラベルを付すことは、実際のデータではしばしば起こることであり、例えば、Ｇｏｏｇｌｅ（登録商標）により返却された画像を探す場合、多くがクエリーとは無関係と思われる画像があり、同様に、Ｆｌｉｃｋｒ（登録商標）システムの画像が、関連性の範囲が広範である、これらに関連するラベルを有することがある。
【００５７】
この方法の目的は、Ｄｗ内のアイテムを、ラベルｗに対して最も関連するものから最も関連しないものにランク付けすることである。最も関連しないものの端数ｆ（fraction）はセットから取り除かれ、整理用のデータセットを生成する（すなわち、最も関連しないアイテムからラベルを取り除く）。この方法は、以下のＭＡＴＬＡＢ（登録商標）の擬似コードおよび図３を参照することにより理解できる。各アイテムが表される前に、ベクトルは、このアイテムの特徴を備えていることに留意すべきである。
【００５８】
各レベルに関連する上位の評価を受けたアイテムは、そのラベルのよい見本であるべきであるということである。最も評価の低いいくつかのアイテムを省略することにより（前述したような閾値を用いて、あるいはスコアの分布を調べることにより、例えば、閾値よりも低いスコアを有するこれらのアイテムを省略または取り除くことにより）、ノイズデータセットは整理される。従来と同様に、総ての処理は、希薄な行列ベクトルの乗法により実現できる。このデータセットを整理する方法は、一を除いたセット（leave-one-out set）と、一を除いたアイテム（left-one item）との間の同様のスコアを格納する好適な方法を利用できることは理解できるであろう。
【００５９】
ベイジアンセット方法は、アイテムに注釈を付すのに利用してもよい。アイテムは画像でもよいが、この方法は、他の種類のアイテムにも同様に適用される。この方法は、以下のＭＡＴＬＡＢ（登録商標）擬似コードおよび図４を参照することにより理解できる。
【００６０】
当業者であれば理解できるように、アルゴリズムは、ラベルｗが付されたアイテムｘおよびアイテムセットＤｗ用の（詳細に説明したような）ベイジアンセットスコアを用いて、一対の所定のアイテムｘおよびラベルｗのスコアを算出し、上位に評価されたラベルを、使用されるラベルとして返却する。他の好適な同様のスコアを用いてもよいことは理解できるであろう。所定の数のラベルは返却でき、あるいはスコア用の削除値（cut-off value）を用いてもよい。ラベルは、ユーザが選択するために提供され、あるいは自動的に利用される。
【００６１】
例示的な結果
例として、ベイジアンセットのアルゴリズムを２つのデータセットに適用することが、ここで説明され、Ｇｏｏｇｌｅセットウェブページから取得した対応する結果と比較される：Ｇｒｏｌｉｅｒｓ Ｅｎｃｙｃｌｏｐｅｄｉａ内の論文の文章で構成されるＥｎｃｙｃｌｏｐｅｄｉａデータセット、ＥａｃｈＭｏｖｉｅサービスのユーザにより格付けされる映画で構成されるＥａｃｈＭｏｖｉｅデータセット（例えば、P. McJones. Eachmovie collaborative filtering data set. http://reserch.compaq.com/SRC/eachmovie/,1977を参照）。
【００６２】
Ｅｎｃｙｃｌｏｐｅｄｉａデータセットは、３０９９１の論文×１５２７６単語であり、エントリは、各単語が各文書で現れる回数の数である。データは、各単語を標準化し閾値化する行により事前処理（二値化）され、（文書、単語）エントリは、その単語が文書の平均の２倍以上の頻度を有する場合、１である。ハイパーパラメータは、α＝ｃ×ｍおよびβ＝ｃ×（１−ｍ）である前述したようなセットであり、ｍは、総ての文章の平均ベクトルであり、ｃ＝２である。同じ事前（prior）が、両データセットのために用いられる。
【００６３】
ＥａｃｈＭｏｖｉｅデータセットは、最初に１５人よりも少ない人により評価された映画が取り除かれ、２００より少ない映画を評価した人により評価された映画が取り除かれることにより事前処理される。次に、データセットが二値化され、（人、映画）エントリは、三つ星以上の評価がされた映画の場合、値１を有する（可能な各付けは０から５の星である）。データは、映画の人気全体を明らかにすべく標準化された行である。事前処理後のデータセットのサイズは、１８１３の人×１５３２の映画である。
【００６４】
これらの実験の結果および単語および映画クエリー用のＧｏｏｇｌｅセットとの比較は、表２および３に示されている。３つのデータセット総てにおけるベイジアンセットアルゴリズムの動作時間が表１に示されている。総ての実験は、東芝ラップトップの２ＧＨｚＰｅｎｔｉｕｍ４でＭａｔｌａｂ（登録商標）で行われた。
【００６５】
これらの結果を客観的に評価することは、グラウンドトルースがない課題であるため、非常に困難であることに留意すべきである。よいクエリークラスタの人の考えは、他品のとは根本的に異なる。Ｇｏｏｇｌｅセットは、クエリーがウェブ上で発見できるアイテムで構成されている場合に非常によく機能した（例えば、ケンブリッジ大学）。他方、より抽象的な概念の場合（例えば、「soldier」および「warrior」、表２を参照）、ベイジアンセットアルゴリズムは、明らかにより理にかなった結果を返却した。
【００６６】
これらの結果は、以下の方法により評価された：３０の未使用のテーマが、無作為の順序のベイジアンセットおよびＧｏｏｇｌｅセットアルゴリズムのラベルの付されていない結果を示し、表２および３の６つのクエリーのために、よりよりセットの結果であると感じるものを選択するように依頼された。Ｇｏｏｇｌｅセットに対する約９０％の好適なベイジアンセットについての６のクエリーを平均化し、一方的な２項式試験は、Ｇｏｏｇｌｅセットが、６つの事例総てにおいて優れている（ｐ＜０．００１）という仮説を否定した。
【００６７】
指数分布族
ベイジアンセットアルゴリズムは、指数分布族のモデルに適用できる。このようなモデルの分布は、以下の形式により表すことができる。
ここで、ｕ（ｘ）は十分統計量のＫ次元ベクトルであり、θは普通のパラメータであり、ｆおよびｇは、負でない関数である。共役事前（conjugate prior）は、
であり、ここで、
はハイパーパラメータであり、ｈは、分布を標準化する。Ｎ個のアイテムを有するクエリーＤｃ＝｛ｘｉ｝、対象をｘとすると、対象ｘのスコアが、
であることを示すのは困難ではない。この式により、スコアが効果的に算出できる場合を理解することができる。まず第１に、スコアは、クエリー（Ｎ）のサイズ、各対象および総てのクエリから算出される十分統計量に依存する。したがって、Ｕと，Ｘに対応するＭ×Ｋ次元の十分統計量を事前に算出することは理にかなっており、ここで、ＭはアイテムまたはＸの列の数である。第２に、スコアがＵの線形操作であるか否かは、ｌｏｇｈが第２の引数（argument）で線形か否かに依存する。これは、ベルヌーイおよび離散型分布の事例であるが、総ての指数分布族に該当しない。しかしながら、対角共分散（diagonal covariance）ガウスなどの多くの分布の場合、スコアがＵ内で非線形ではないが、これは、非線形性要素（elementwise）をＵに適用することにより算出できる。したがって、希薄な行列の場合、スコアは、ゼロでない要素の数で線形時間（time linear）で算出できる。
【００６８】
結論
前述した実施例により、小さなアイテムのセットで構成されるクエリーを取得し、同じ発生分布から生じる可能性のあるアイテムという意味において、同じセットに属する可能性のある追加的なアイテムを返却するアルゴリズムを説明した。アルゴリズムの出力は、ソートされたアイテムのリストでもよく、またはアイテムが同じセットに属する可能性を判断する単なるスコアでもよい。前者の場合、固定した数のアイテムが返却され、あるいは返却されるログ確率（log probabilities）の閾値を設定してもよい。クエリーを比較できるログ確率としてスコアを解釈すべく、等式１３の項目ｃを含むスコアを算出してもよい。さらに、アルゴリズムにより返却されるアイテムの数を決定する他の動的なスキームも実現できることは当業者に明らかである。
【００６９】
前述したアルゴリズムは広範囲なデータセットされ、好適なプログラム言語を用いて任意の好適な演算プログラムで実現できることは当業者にとって明らかである。アルゴリズムは、スタンドアロンまたはネットワークコンピュータで実現してもよく、例えば、クライアントとサーバとの間のネットワークを介して分配してもよい。後者の場合、サーバが、総ての不可欠な演算を実行できる一方、クライアントはユーザのインタフェースのみを提供し、または演算は、クライアントとサーバの間で分散してもよい。
【００７０】
勿論、特定の実施例が説明されているが、請求の対象は、特定の実施例あるいは実施形態に限定されないことは理解できるであろう。例えば、ある実施例は、装置あるいは装置の組み合わせで動作するように実装されたハードウェアでもよいのに対して、例えば、別の実施例はソフトウェアでもよい。
【００７１】
同様に、実施例は、ファームウェア、あるいは例えば、ハードウェア、ソフトウェア、および／またはファームウェアの組み合わせで実現してもよい。同様に、請求の対象はこの点に限定されないが、ある実施例は、記憶媒体あるいは記憶メディアなどの物を備えてもよい。例えば、１以上のＣＤ−ＲＯＭおよび／またはディスクなどの記憶媒体は、命令を記憶してもよく、コンピュータシステム、コンピュータプラットフォーム、あるいは他のシステムなどのシステムにより実行された場合に、例えば、前述した実施例の一つなどにより実現される請求の対象による方法の実施例をもたらす。一つの例として、コンピュータプラットフォームは、１以上の処理ユニットまたはプロセッサ、ディスプレイ、キーボードおよび／またはマウスなどの１以上の入力／出力装置、スタティックＲＡＭ、ダイナミックＲＡＭ、フラッシュメモリおよび／またはハードドライブなどの１以上のメモリを備えてもよい。
【００７２】
前述した説明では、請求の対象の様々な態様が説明されている。説明の目的のために、特定の数字、システムおよび／または構成が説明され、請求の対象を完全に理解するようにしている。しかしながら、本開示による利益を享受する当業者には、請求の対象は、特定の詳細以外により実現できることは明らかである。他の実施例では、請求の対象を不明瞭にしないように、周知の特徴が省略および／または単純化されている。特定の実施例が示されおよび／または図示されているが、多くの修正例、代替例、変更例および／または均等例が当業者には明らかである。したがって、添付の請求項は、請求の対象の範囲内で、このような修正例および／または変更例を総て網羅するものであることは理解できるであろう。
【図面の簡単な説明】
【００７３】
【図１】図１は、本発明に係る実施例のフロー図である。
【図２】図２は、クエリーを図１の実施例に入力する方法のフロー図である。
【図３】図３は、データセットを整理する方法のフロー図である。
【図４】図４は、アイテムに注釈を付す方法のフロー図である。
【技術分野】
【０００１】
本発明は、アイテムの共通点のスコアリング（評価）に関し、特に、排他的ではないが、情報検索の分野に関し、より具体的には、関連するアイテムの用途ベースの検索に関する。
【０００２】
通常、既知の情報検索の方法は、ある基準下でクエリーに関連すると認められる文書を一群の文書内から発見することに関係する。クエリーは通常、言葉のリストから成り、典型例は、ウェブ検索または特許文献のデータベース検索である。
【０００３】
文書の関連性を家低する確率論的基準に依存する情報検索（ＩＲ）方法が、従来知られている。これらの方法は、「この文書はこのクエリーと関連する可能性はどれだけか」という質問をする。この質問に対する２つの解決手段が存在し（参照によりここに組み込まれているJohn Lafferty and Chengxiang Zhai (2003) Probabilistic relevance models based on document and query information、Language Modelling Information Retrieval, Kluwer International Series on Information Retrieval, Vol. 13に説明されているように）、
１）各クエリーに対して２つのモデルが評価され、一方が、関連する文書をモデル化し、他方が、関連しない文書をモデル化し、文書は、関連性の事後確率によりランク付けされ、
２）各クエリーに対して言語モデルが評価され、ランキングの操作手順は、各文書のモデルにしたがって、クエリーに割り振られた可能性により文書を整理することである。
特に、これらの解決手段双方は、多くの統計モデルのパラメータを評価する必要がある。
【０００４】
データベース内のテキストクエリーを検索する場合に生ずる一つの問題は、クエリーが、クエリー内の言葉に対するヒットを有する多くの文書を返却することである。これらは、クエリーが多数の概念クラスタ内でヒットを生成するため、ユーザが実際に思っていたものに関連し、または関連しない場合があり、これらの一部のみが、ユーザが意図するものである。この問題の解決手段が、例えば、参照によりここに組み込まれるＵＳ−Ｂ−６３８５６０２で提案されており、ここでは、このような結果は、動的な分類を用いて表される。これは、検索結果の属性に基づいており、好適なグループ化またはクラスタリング技術を用いる。検索結果は、ユーザが探しているものを選択するのに役立つように構成された分類で表される。しかしながら、分類は、通常管理されていないクラスタリングアルゴリズムにより生成されるため、分類が、ユーザが実際に想定したものに対応しないことがある。
【０００５】
参照によりここに組み込まれているＧｏｏｇｌｅ（登録商標）セットは、いくつかの例からアイテムセットを自動的に生成するＧｏｏｇｌｅ（登録商標）が提供する実験的なツールである。ユーザは、一組の物からいくつかのアイテムを入力し、インタフェースは、セット内の他のアイテムを予測しようとする。アイテムの僅かなセットで構成されるクエリーの場合、アルゴリズムは、クエリーにより規定されるセットに属する関連するアイテムの多くのセット（以降、クラスターと称する）を返却する。例えば、車の３つのブランドの場合、インタフェースは、車の追加のブランドを含む拡張されたセットを返却する。ユーザは、拡張されたセット内の任意のアイテムをクリックでき、そのアイテムによりウェブ検索を実行する。しかしながら、得られる検索の可能性は、拡張されたセットの検索されたアイテムのうちの一つを対象とするウェブ検索の実行に限られる。
【０００６】
従来のテキストベースのＩＲクエリーは、論理演算子により組み合わされたキーワードに基づいている。クエリー内のアイテムと同じ概念クラスタに属するアイテムを検索するという意味で共通する演算子を関数演算子として備える検索ツールあるいは一般的なアプリケーションを提供することは有益である。これは、クエリー自体が、結果が発見されるクラスタを規定する効果的な検索メカニズムを提供する。すなわち、このようなクエリーは、クエリーのアイテムおよび返却されるアイテムが、同じ概念クラスタにどれほどヒットするかに関連する共通するスコアに基づいている。
【発明の開示】
【課題を解決するための手段】
【０００７】
本発明の第１の態様では、請求項１に定義するように、クエリーと他のアイテムとの共通点をスコアリングするコンピュータが実施する方法が提供される。
【０００８】
アイテムに割り振られるスコアは、クエリーアイテムおよび他のアイテムが、同じ発生分布または統計モデルから生成される可能性に依存する。オーディオ符号化および音声認識の分野では、よりよい復元および認識が、人間の聴覚システムが機能する方法を考慮することにより実現できることが、長い時間をかけて確立されている。最近の実験的証拠は、人々は、同じ統計分布から生成されるアイテムを、心理学文献（A generative theory of similarity. Kemp, C., Bernstein, A., and Tenenbaum, J.B.(2005)。参照によりここに組み込まれている認知学会の２７周年の会議の議事録。）に提案されている他の手順を用いて生成されたアイテムよりも共通すると判断する示している。オーディオ符号化または音声認識の理論と同様の意図では、本発明の共通するスコアは、人々がどのように類似を判断するのかという心理学的な証拠により生じる。
【０００９】
発生分布は、データからこれらパラメータを評価するよりも、多くのパラメータにより決定され、スコアは、パラメータの総ての取り得る値に対して平均化され、これにより、パラメータの評価に関連する問題を阻止する。これはしばしば、「パラメータを無視する」または完全なベイズ的アプローチと称される。さらに、心理学的な証拠（参照によりここに組み込まれているGeneralization, similarity and Bayesian inference. J.B. Tenenbaum, T. L.Griffiths (2001), Behavioral and Brain Science, 24 pp. 629-641）は、人々が証拠を一般化し、（パラメータ設定に応じて）代替的な仮説を平均化することにより類似性を判断する。したがって、類似するスコアを算出する完全なベイズ的アプローチは、人間の状態および類似性の認知によく調整されていると見なしてもよい。
【００１０】
発生分布はベルヌーイ分布でもよく、パラメータは、ベータ分布より先の対応する共役（conjugate）で平均化してもよい。ベルヌーイ分布の場合、発明者は、コンピュータ的に強く、処理できないことがない関連する積分は、行列乗算により効果的に実現可能であるということを理解した。
【００１１】
本発明の別の態様では、請求項５に定義するように、クエリーと、１またはそれ以上のアイテムとの類似性をスコアリングするコンピュータが実施する方法を提供する。
【００１２】
スコアリングする方法は、アイテムが２項素性ベクトル（binary feature vector）により表される場合、発生分布において類似性のスコアリングの完全なベイジアン処理を実施する行列乗算に関連することが有利である。したがって、この方法は、行列演算のスコアの算出に関連する総ての積分を実施する。
【００１３】
スコアリング方法は、通常ではあるがアイテムの表示が希薄である場合、より効率的に実施してもよい。以下で使用するように、希薄は、入力の大部分が０（あるいは別の定数）であり、少なくとも特徴の３分の２が０（あるいは一定値）である表示を意味している。特に、非常に大きなデータセットの場合、アイテムは、クエリーアイテムと関連する少なくとも規定の数の特徴を有するアイテムのみがスコアを付されるように前処理される。これは、例えば、逆のインデックス（inverse index）を用いて実現できる。
【００１４】
ベータ分布は、２つのハイパーパラメータαおよびベータにより特徴付けられる。このパラメータは、ベイジアン分析、例えば証拠の最大化（evidence maximisation）を用いて、標準的な方法によりデータにフィットし、または試験およびエラーを用いて発見できる。ハイパーパラメータを設定する一の特定の方法は、アイテムに対するこの特徴の平均値に比例する各特徴に対応するαパラメータを設定し、１マイナス平均に比例するような各特徴に対応するβパラメータを設定する。これは、ハイパーパラメータを設定する効果的な方法であり、パラメータ分布は、データセットの構造に対する事前情報を含んでおり、ハイパーパラメータは、比例定数を調整することにより微調整できる。
【００１５】
アイテムは、ウェブページ、画像、既知および機能を有する遺伝子またはタンパク質、既知および機能を有する医薬品分子、病歴、または言葉若しくは映画のタイトルなどのデータの他のアイテムでもよい。
【００１６】
本発明は、物理的なレベルにおいて、アイテムあるいはアプリケーションの特定の種類に全く依存しないことは明らかであろう。物理的なレベルにおいて、アイテムは、（アプリケーションに応じて、様々な実在の物を表す）単にデジタルビットのグループであり、本発明は、同一のランダムな処理により生成される可能性における類似性を決定する。詳細なアルゴリズムは、ランダムアクセス（例えば、独立したベルヌーイ試行）のために選択される分析モデルにより決まるが、ビットまたはアイテムのグループに関連する目的により決定されるものではない。
【００１７】
予備的な検索クエリーの検索結果のサブセットを選択することにより、クエリーは、選択された検索結果として、同一の概念クラスタに属する可能性のあるアイテムに洗練することが有利である。
【００１８】
前記方法は、所定のキーワードを画像のサブセットに付すことにより、キーワードを用いた画像検索を提供することが有利である。キーワード検索の結果は、前述したような共通点検索の入力として用いてもよい。この方法では、大きくてラベルが付されていない画像セットからの画像は、最初に小さくてラベルの付されたサンプル画像セットを検索することにより検索される。この方法はさらに、データセットを整理し、あるいは注釈を付すのに利用してもよい。
【００１９】
本発明のさらなる態様によると、請求項２１に記載のコンピュータシステムと、請求項２２に記載のコンピュータプログラムと、請求項２３および２４に記載のコンピュータが読み取り可能な媒体および信号が提供される。
【００２０】
本発明のさらに別の態様は、請求項２５、２６および２７にそれぞれ記載の画像を検索する方法、データセットを整理する方法、およびアイテムにラベルを付す方法を利用する。
【００２１】
本発明の特定の実施例は、例示的な方法により、添付図面を参照してここに説明される。
【発明を実施するための最良の形態】
【００２２】
以下の詳細な説明では、請求の対象を完全に理解するために、多くの特定の詳細が説明されている。しかしながら、当業者であれば、請求の対象は、これらの特定の詳細なしに実施してもよいことは理解できるであろう。他の実施例では、周知な方法、処理、要素、および／または回路は、詳細には説明されていない。
【００２３】
以下の詳細な説明の一部は、コンピュータおよび／またはコンピュータシステムメモリ内のコンピュータシステム内に格納されたデータビットおよび／またはバイナリデジタル信号の処理のアルゴリズムおよび／または象徴の観点で示されている。これらのアルゴリズムの記載および／または象徴は、彼らの取り組みの本質を本分野の他の当業者に伝えるために、データ処理分野の当業者により利用される技術である。ここに記載されているアルゴリズムは通常、矛盾のない処理シーケンス、および所望の結果に通じる同様の処理と考えられる。操作および／または処理は、物理量の物理的処理を含んでもよい。通常、必ずしも必要ではないが、これらの量は、格納、移動、結合、比較および／または操作可能な電気信号および／または磁気信号でもよい。これらの信号を、ビット、データ、値、要素、シンボル、文字、用語、数、数字等と呼ぶことは、主に一般的な用途のために有用であることが何度の証明されている。しかしながら、これらの語句および同様の語句総ては、適切な物理量に関連し、単に有用なラベルに過ぎないと理解すべきである。特別に明示しない限り、以下の説明か明らかなように、本明細書全体を通して、「処理」、「演算」、「計算」、「決定」等の用語を利用した説明は、コンピュータプラットホームのプロセッサ、メモリ、レジスタ、および／または情報を記録し、転送し、および／または表示する装置内の物理的な電気量および／または磁気量および他の物理量として表されるデータを操作および／または変換するコンピュータまたは同様の電子演算装置などのコンピュータプラットフォームの動作および／または処理を意味する。
【００２４】
概要
多くのアイテムＤを検討する。アプリケーションに依存して、セットＤは、ウェブページ、映画、人々、言葉、タンパク質、画像、または誰かがクエリーを形成したいと願う他のオブジェクトで構成してもよい。ユーザは、アイテムのサブセットＤＣ⊂Ｄの形式のクエリーを提供する。ＤＣ内の要素が、データ内の概念、クラスあるいはクラスタの例であると仮定する（これより「クラスタ」の語句が使用される）。アルゴリズムは、セットＤＣ、すなわち、ＤＣ内の総ての要素および同じクラスタ内のＤ内の他の要素を含むいくつかのセットＤ’Ｃ⊂Ｄに完了を提供する。
【００２５】
特定の情報検索の問題を回ケルするアルゴリズムの目的を考えることができる。他の検索の問題のように、出力はクエリーに関連すべきであり、一つの可能性は、クエリーとの関連性によりランク付けされた上位の数アイテムに出力を限定することである。
【００２６】
ベイジアンセット
以下に説明するアルゴリズムは、参照を容易にするために剰余（remainder）内の「ベイジアンセット」と称する。
【００２７】
Ｄをアイテムのデータセットとし、ｘ∈Ｄをこのセットからのアイテムとする。ユーザは、Ｄの小さなサブセットであるクエリーセットＤＣを提供すると仮定する。目的は、要素がＤＣを含むセットにどれだけ「フィット」するのかにより、Ｄの要素をランク付けすることである。直観的に、タスクはクリアであり、セットＤが総ての映画のセットでありクエリーセットが２つのアニメのディズニー映画で構成される場合、他のアニメのディズニー映画は、上位にランク付けされると予測する。
【００２８】
ＤＣがいくつかのクラスタに属すると仮定すると、我々は、ｘもＤＣに属する可能性がどれだけなのか知りたい。これは、ＤＣの場合、クラスタに属するｘの可能性であるｐ（ｘ｜ＤＣ）により測定される。この可能性のみによるアイテムのランク付けは、いくつかのアイテムが他のよりも可能性が高いため、ＤＣに拘わらず精度が低い。例えば、最も精度の高いモデルでは、文字列の可能性は、文字の数と共に減少し、画像の可能性は、ピクセルの数と共に減少し、連続する変数は、測定される精度と共に減少する。これらの影響を取り除くために、比
を計算し、ここで分母は、ｘの事前確率である。
【００２９】
ベイズの規則を用いて、このスコアは、
のように表すことができ、これは、同じクラスタに属し、ｘおよびＤｃに属するｘおよびＤｃの観察の同時確率の比として解釈できる。最後に、ｘに依存しない乗法定数により、スコアは、
と表すことができ、これは、ｘの場合（すなわち、ｘの可能性）のクラスターに属するクエリーセットの可能性である。
【００３０】
前述の説明は、ｐ（ｘ｜Ｄｃ）およびｐ（ｘ）などの量をどのように算出するかについての取り組んではいない。クラスタを定義するモデルに基づく方法は、クラスタ内のデータポイント総てが、独立して到来し、パラメータ化された統計モデルまたは分布から分配されると仮定する。パラメータ化されたモデルは、ｐ（ｘ｜θ）であり、ここで、θはパラメータである。Ｄｃ内のデータポイントが、一つのクラスタに属する場合、この定義下では、これらは、パラメータの同一の設定から生成されるが、設定は未知である。
【００３１】
一つの可能な解決手段は、クエリー自体からパラメータを算出することであり、これは、小さなクエリーには問題である。パラメータ算出に依存しない、より理にかなった解決方法は、完全にベイズ的アプローチを利用することであり、すなわち、パラメータ値、ｐ（θ）の事前密度（prior density）または分布により重み付けされた可能性のあるパラメータ値を平均化することである。これらを考慮し、確率の基礎的な法則を利用することにより、我々は、
に達する。
【００３２】
これらの等式を用いることにより、ベイジアンセットアルゴリズムは、以下のように表すことができ、総てのアイテムまたは総てのアイテム
のスコアを計算し、例えば、
【００３３】
セットの他の各アイテムの特徴ベクトルＸｉの場合、前述のスコアは、クエリーに依存しない乗法定数に応じて、特徴ベクトルＸｉの条件付確率として表すことができるのは等式（３）から思い出されるであろう。基本的なパラメータ化された分布から生じるような特徴ベクトルを考慮すると、他の各アイテムの各特徴ベクトルが発生分布ｐ（Ｘｉ｜θ）から生じる場合、スコアは、パラメータθにより定まる発生分布ｐ（Ｘｉ｜θ）から生じるクエリーアイテムの特徴ベクトルＸｉの条件付確率の関数としてみてもよい。
【００３４】
従来よりも従順で精密な完全なベイズ法に関する２つの共通の懸念が存在する。本発明において、発明者は、完全なベイズ処理は、分析および算出双方に効果的であり、従来の分布の選択肢に比べて精密過ぎることのない方法で実現できることが分かった。
１．多くのモデルの場合、積分（４）から（６）は分析的である。実際に、モデルの場合、我々は以下のバイナリデータを考慮し、発明者は、総てのスコアを計算することにより、単一の行列の複雑さを低減できることを発見した。
２．精度の高いモデルｐ（ｘ｜θ）を従前のモデルｐ（θ）選択することは、明らかに有益であるが、これらは複雑である必要はない。以下に示す結果は、単純なモデルと従前のモデルの調整をほぼ必要としないことにより、競争力のある検出結果が得られることを示している。実際には、従来のモデルを曖昧にするが、Ｄ内のデータの平均を中心とする単純な経験的発見（empirical heuristic）が利用される。
【００３５】
バイナリデータ
前述したように、ベイジアンセットアルゴリズムは、排他的ではないが、希薄なバイナリデータに特有であることがわかる。この種のデータは、各アイテムの特徴が存在し、あるいは存在しないことにより特徴付けられる大きなデータセットの自然な式である。
【００３６】
各アイテムｘｉ∈Ｄが、バイナリベクタｘｉ＝（ｘｉ１，・・・，ｘｉＪ）であり、ｘｉｊ∈｛０，１｝であると仮定すると、ｘｉの各要素は、独立したベルヌーイ分布である。
ベルヌーイ分布のパラメータの前の共役（conjugate）は。データ分布であり、
ここで、αおよびβは、従来のハイパーパラメータであり、ガンマ関数は、階乗関数を一般化したものである。Ｎ個のベクトルで構成されるクエリーＤｃ＝｛Ｘｋ｝の場合、以下を示すことは容易であり、
ここで、
であり、
である。アイテムｘ＝（ｘｉ１・・・ｘｉＪ）の場合、ハイパーパラメータが明示的に示されたスコアは、以下のように算出できる。
この取っ付きにくい式は劇的に単純化できる。我々は、ｘ＞１の場合、
を利用することができる。各ｊに対して、我々は、２つの事例ｘｉｊ＝０およびｘｉｊ＝１をそれぞれ検討できる。ｘｉｊ＝１の場合、我々は寄与（contribution）
を有する。ｘｉｊ＝０の場合、我々は寄与（contribution）
を有する。これらを組み合わせることにより、我々は、
を得る。スコアのログは、ｘｉ内で線形的である。
ここで、
であり、
である。我々が、総てのデータセットをＪ列およびＭ行の一の大きな行列Ｘに入れる場合、我々は、Ｘの単一の行列のベクトル乗算と、クエリーベクトルｑを用いて、総てのアイテムのためのログスコアのベクトルｓを算出できる。
各クエリーＤＣは、ベクトルｑの計算に対応する。ｃを追加することは、スコアのランク付けに影響しないため省略してもよい。また、これは、クエリーが希薄である場合、ｑの多くの要素は、クエリーから独立したｌｏｇβｊ−ｌｏｇ（βｊ＋Ｎ）と等しいため、（式を予め計算することにより）効率的に行うことができる。
【００３７】
希薄なデータセットの場合、行列の乗法は、非常に効率的に行うことができる。我々は、希薄を行列の３分の２または多くの特徴要素がゼロであることと定義しているが、行列は、しばしばそれよりも希薄になることがある（例えば、ゼロでない行列の要素が１％）。希薄な行列が、エントリの３分の２が（ゼロとは反対に）定数であるような構造の場合、この行列は、定数を引き算することにより希薄な行列に変換できる。効率的なアルゴリズムは、ｘｉｊ≠０（例えば、Ｍａｔｌａｂの希薄な行列の実施例）となるために、総てのインデックス用のリスト（ｉ，ｊ，ｘｉｊ）で構成される希薄な行列データ構造を利用する。０のエントリは格納されず、メモリを占有しない。希薄な行列ベクトルの乗法は、ゼロでない要素に対してループし、対応するベクトル要素により掛け算して合計する。このアルゴリズムは、マトリックスの多くのゼロでない要素の線形時間である。参照によりここに組み込まれているＭａｔｌａｂ（登録商標）の基本的な線形代数ルーチンであるＢＬＡＳおよびＬＡＰＡＣＫと、Ｓｐａｒｓｅ ＢＬＡＳ：http://www.netlib.org/sparse-blas/を参照。
【００３８】
非常に大きなデータセット（例えば、何百万のエントリ）の場合、Ｉｎｖｅｔｅｄ Ｉｎｄｅｘ（http://www.nist.gov/dads/HTML/invertedIndex.html、参照によりここに組み込まれている）が利用でき、これは、例えば、ウェブ上のテキスト文書のための情報検索で利用される標準的なデータ構造である。これは、各文字あるいは特徴が、これらの現れる文書のリストを伴うように構成された、例えば、一群の文書（すなわち、アイテム）内の文字（すなわち、特徴）の希薄な式である。検索を実行する場合、総てのアイテムを検索するのではなく、クエリーに関連する特徴を有するアイテムのみを評価する必要があり、これにより、アルゴリズムをより一層効率的にする。
【００３９】
最後に、スコアにより、データセット内のＭ個のアイテム全部をソートする必要はなく、検索のためのいくつかの上位のアイテムを発見する必要がある。上位のいくつかのアイテムを発見する所定のスコアベクトルはＯ（Ｍ）であり、Ｏ（ＭｌｏｇＭ）である総てのアイテムをソートするよりも非常に効率的である。アルゴリズムは、Ｍに対して１回のループを必要とし、現在のトップスコアアイテムのリストを更新する。
【００４０】
前述のアルゴリズムは、ハイパーパラメータ（例えば、αおよびβ）の選択を必要とし、パラメータに対する先行する分布を定義する。ハイパーパラメータは、証拠の最大化（evidence maximisation）などの標準的なベイジアン法を用いて発見できる一方、行列Ｘの構造の従来の知識を用いる単純な方法が利用できる。
１）Ｘの列を平均化するデータの平均Ｍを計算する。ベクトルｍは、１×Ｊであり、Ｊは、Ｘの行の数である。
２）αｊ＝ｃｏｎｓｔ・ｍｊを設定する。
３）βｊ＝ｃｏｎｓｔ・（１−ｍｊ）を設定する。
ここで、ｃｏｎｓｔは、試行およびエラーにより決定でき、あるいは「証拠（evidence）」に基づいてベイズ処理を用いて最適化できる定数である。以下に示す例では、定数は、ｃｏｎｓｔ＝２に設定される。
【００４１】
通常、ハイパーパラメータは、ｐ（θ）がデータの適切なモデルを与えるように設定される。すなわち、これらのハイパーパラメータを用いてｐ（ｘｉ）から生成することにより、凡そ実際のデータと同じ統計値のＸの列が生じる。
【００４２】
前述したバイナリデータの特定の実施例は、以下の行に沿ってＭＡＴＬＡＢ（登録商標）で実現でき、データの入力、出力および処理が省略される。
【００４３】
アプリケーション
前述したベイジアンセットアルゴリズムは、この基礎的な概念クラスタの例で構成されるクエリーに基づいて、基礎的な概念クラスタの要素を発見する必要のある任意の状況に適応できる。アプリケーションは、例えば、同じような概念に関連する言葉、あるいは特定の特徴を共有する映画を発見するステップを含む。これらの例は、以下に示す結果に関連して説明される。
【００４４】
アルゴリズムは、利用される式により、すなわち、行列Ｘの行のバイナリ値により符号化される特徴により主に区別される多くの他のアプリケーションに適用してもよい。様々なアプリケーションでは、行列Ｘは以下を示す。
・ウェブサーチ：各列はウェブページを表し、各行はウェブページの特徴を表し、例えば、文字が、メタタグ、問題のページおよび／または、特定のキーワードが問題になっているウェブページの所定の閾値よりも、より頻繁に現れれるページにリンクしたウェブページにリンクしたウェブページに存在する。ウェブページ用のキーワード検索を実施することにより、リストに関連するページを節約でき、リスト内の総てのアイテムに類似する総てのページのためのクエリーを節約できる（以下を参照）。
・医療エキスパートシステム：列は患者を表し、表は、対応する病歴の特徴を表し、例えば、特定の状態あるいは症状の有無、および／または特定の生理学測定値が、所定の範囲の値内にある。値の範囲は、通常の値と病的な値を区別できるが、値の範囲の僅かな違いが認識される。特定の病気で苦しむ患者の特徴ベクトルを有するシステムを提供することにより、病気にかかる他の人の可能性を予測できる。
・遺伝子／タンパク質の機能分析：列は、遺伝子またはタンパク質、例えばヒトゲノム内で特定される遺伝子を表し、行は、特定のベースシーケンスなどのゲノムマーカー（genomic marker）、または遺伝子内の特定の位置の特定のシーケンスの存在を表す。同様にタンパク質の場合も、行はタンパク質の構造または機能的な特徴を表す。クエリーは、既知の機能を有する遺伝子を選択することにより、またベイジアンセットの同様のスコアを用いることにより定式化でき、試験対象として未知の機能の遺伝子を特定し、これらが同一または同様の機能を有するかを検証する。
・創薬：列は分子を表し、行は分子の特定の構造的な特徴あるいは機能的な影響の有無を表す。クエリーは、所望の機能あるいは治療効果を有することが分かっている選択された医薬品分子に基づく。返却された最も高いスコアの分子は、それらの活動を試験する対象として用いることができる。
・画像：列は、個人の画像を表し、行は、標準的な画像処理技術を用いて、画像から抽出される２項素性（binary featture）を表す。画像処理により画像から抽出された２項素性は、ユーザにとって意味がないため、予備的なキーワード検索は、以下に詳細に説明するように実施される。
・シソーラス：列は言語の単語を表し、行は単語の特徴を表す（以下を参照）。クエリーは、いくつかの単語を用いて定式化でき、クエリー内の総ての単語の共通の意味に関連する選択肢を返却する。
・電子商取引のための検索ツール：列は、購入に利用可能な特定のアイテムを表し（例えば、不動産、デジタルカメラ、ヨット、ホテル滞在、レストランの予約、映画チケット）、行は、アイテムの特徴を表す（例えば、位置、重量、価格）。所望の不動産を有するアイテムを選択することにより、同じような特徴を有する他のアイテムを発見することが可能である。不動産を例示的なアプリケーションとすると、現在の検索は郵便番号に依存している一方、特定の道路または他の位置は、購入者により直接関係する。購入者は、最初の検索から不動産の選択を指定し、彼らの要求により合致する他のものを発見する。
・人間の人格のための検索ツール：列は個人を表し、行は当該個人の重要な特徴を表す（例えば、特徴ベクトル、能力、興味により特定されるような様子）。所望の特徴を有する数人を選択することにより、同じような他の人を発見することができる。これは、オンラインデート、俳優の発見、モデルの発見、特定の業界の専門家の発見、潜在的な犯罪者の特定または他の警察活動、および本土防衛主導に利用してもよい。
・投資の選択：列は投資物件を表し（例えば、株、債権、デリバティブ）、行は、過去の実績、分野、成熟度などの投資物件の特徴を表す。いくつかの例示的な投資物件を選択することにより、システムは、ユーザに代替的な同様の物件を提供する。
・企業検索：列は企業を表し、行は企業の特徴を表す（例えば、産業、生産高、株価）。一組の企業を選択することにより、同様の企業を発見することが可能である。これは、調査、例えば、企業の有望な競争相手全部を見つけるのに有用である。これはまた、処理を用いる投資決定に有用である。
・特許検索：列は、単一の特許あるいは特許ファミリーを表し、行は、書誌データおよび／または特許の内容を表す。いくつかの特許が特定の分野に関連することが分かった場合に、これらを前述した検索アルゴリズムに提供し、同一領域を網羅する同様の特許を検索してもよい。
・推薦者システム：列は商品またはサービスを表し、行はその特徴を表す。購入決定（例えば、オンラインでの本の購入歴）、検索決定（例えば、検索歴の記録）または示された好み（例えば、ニュース、音楽等）のいずれかにより示された事前の関心に基づいて、関心のあるアイテムを個人に提案することが可能である。例えば、最近検索され、あるいは購入されたアイテムは、ベイジアンセットアルゴリズムのクエリーセットとして利用してもよい。
・顧客分析：列は、ビジネスの顧客を表し、行は、顧客の特徴に対応する（例えば、購入歴、個人の特徴、好み）。所望の特徴を有する一群の顧客を選択することにより、より広い同様の顧客を推定することが可能である。これは、例えば、既存の顧客に製品を販売すべく、ある地域で販売運動（例えば、ダイヤルアップインターネットの顧客にブロードバンドのインターネットアクセスを提供する）が行われる場合に有用である。促進を行う個人のグループを作ることにより、企業は、別の地域および市場の同様の顧客を確認でき、コストを低減し、理解する可能性を増加させる。
・音楽検索：列は曲を表し、行はその特徴を表す。各曲を適切な特徴ベクトルに変換することにより、音楽の選択を指定し、例えば、同じような感覚を有する他の曲を検索できる。
・研究者の出版物に基づいて、同じような主題に取り組む研究者を発見すること。（文学作品、科学論文またはウェブページの）著者のスペースは、同様のテーマを書き、関連する研究分野で働き、または共通の興味あるいは趣味を共有する人々のグループを発見すべく検索される。
・同様の論文のクラスタのための科学文献の検索：キーワードを提供する代わりに、ベイジアンセットを用いた例により検索できる：一部の関連する論文は、いくつかのキーワードよりも充実した方法により主題を取得できる。
・ここに記載されているベイジアンの検索方法を用いたタンパク質データベースの検索であり、ＵｎｉＰｒｏｔ（一般的なタンパク質のリソース（Universal Protein Resource））完全に新規なアプローチであり、「世界で最も包括的なプロテインに関する情報のカタログ（world's most comprehensive catalog of information on proteins）」が作られた［http://www.uniprot.org］。各プロテインは、ＧＯ（遺伝子存在論（Gene Ontology））注釈、ＰＤＢ（タンパク質データバンク）構造情報、キーワード注釈、および主要なシーケンス情報から由来する特徴ベクトルにより表される。ユーザは、いくつかのタンパク質の名前を与えることにより、データベースに問い合わせることができ、例えば、生物学的な特性を共有し、システムは、その特徴に基づいて、これらの生物学的な特性を共有する他のタンパク質のリストを返却する。特徴は、注釈、シーケンス、および構造情報を含むため、システムにより返却されるマッチ（match）は、通常のテキストのクエリーよりも膨大な情報を有し、したがって、より複雑な関連性を得ることができる。例えば、酵母のような特徴を示す２つの仮定のタンパク質に基づいてＵｎｉｐｒｏｔに問い合わさせし、我々のシステムは、自動的に分類「ＣＹＳ３酵母」に合致する他のタンパク質を検索するために一般化する。従来のキーワードに基づくアプローチを用いたこのようなマッチを発見することは非常に困難である。
【００４５】
図１を参照すると、ベイジアンセットのアルゴリズムは、ステップ１０において、１以上のクエリーアイテムを入力として用い、ステップ２０において、ベイジアンセットのアルゴリズムを用いて（入力クエリーのアイテムを含む可能性のある）各アイテムのスコアを計算する。ステップ３０では、アルゴリズムは、好適にはソートされた、ｎ個の最も高いスコアを有するアイテムの上位ｎ個（例えば、ｎ＝１０）リストを返却するか、あるいはユーザに表示するため、あるいは他のアルゴリズムにより利用されるスコア自体を返却する。
【００４６】
図２を参照すると、ステップ２では、従来の種類の検索、例えば、キーワード検索または他の好適な種類の検索が初めに実施され、検索結果のリストをユーザに返却する。次に、ステップ４において、ユーザが１またはそれ以上の有望な検索結果を選択し、選択が得られる。次に、ステップ６において、選択された検索結果が、入力クエリーとして用いられ、アルゴリズムは、図１のステップ１０に従い、前述したベイジアンセットのアルゴリズムにより、総ての検索結果を評価することにより、検索の精度を高める。
【００４７】
例えば、特定の実施例では、ウェブ検索インタフェースは、各検索結果に近い選択ボックス追加的に提供する従来のキーワード検索を提供する。次に、ユーザは、有望な検索結果を選択し、ウェブページにアクセスして、これらの結果を、ユーザのコンピュータに存在するアプレット、またはウェブサーバに提供し、前述した、および図１に関連するベイジアンセットのアルゴリズムにより、クエリーの精度を高める。
【００４８】
前述したように、提案された２項素性のセットはユーザには意味がないため、画像を検索する場合、画像の検索時には特別な考慮がなされる。この潜在的な問題を克服すべく、画像のサブセットは、各画像に関連する言葉のセットによりラベルが付される。未だ言葉が関連付けられていないが、前述したように２項素性が定義されている画像のラベルの付されていない大量のデータセットが存在する状況が予想される。
【００４９】
図２のステップ２に対応する最初のステップでは、ユーザは、テキストクエリー、例えば「ピンクのバラ」を入力し、アルゴリズムは、予備的な検索として、言葉のラベルを有するラベルが付されたデータセット内の総ての画像セットを発見する。次に、このクエリーの検索結果は、例えば、ラベルの付されていない大量のデータベースから最も高いランキングの１０の画像を返却するベイジアンセットのアルゴリズム用の入力クエリーとして利用される（ステップ１０）。勿論これは、図２のステップ４および６と組み合わされ、ユーザは、ベイジアンセットのアルゴリズムに対する入力クエリーとして、テキストクエリーにより返却される画像のサブセットを選択してもよい。
【００５０】
画像の特徴ベクトルは、２種類のテクスチャの特徴、例えば、４８のガボール（Ｇａｂｏｒ）テクスチャの特徴および２７のタムラのテクスチャの特徴や、例えば、１６５のカラーヒストグラムの特徴を用いて定義してもよい。参照によりここに組み込まれているH. Tamura, S. Mori, and T. Yamawaki（Texutual features corresponding to visual perception. IEEE Trans on Systems, Man and Cybernetics, 8:460-472, 1978）に示されているように、粗くて対照的な方向性を有するタムラの特徴が、９（３×３）タイルごとに計算される。６つのスケールセンシティブ（scale sensitive）および４つのオリエンテーションセンシティブ（orientation sensitive）のガボールフィルターが各画像位置に利用され、得られたフィルタ応答の分布の平均値および標準偏差を算出する。これらのテクスチャの特徴の算出の詳細については、参照によりここに組み込まれているP. Howarth and S. Ruger (Evaluation of texture features for content-based image retrieval. In International Conference on Image and Video Retrieval(CIVR), 2004)を参照。カラーの特徴の場合は、ＨＳＶ（Hue Saturation Value）３Ｄヒストグラム（参照によりここに組み込まれているD. Heesch, M. Pickering, S. Ruger, and A. Yavlinsky. Video retrival with a browsing framework using key frame. In Proceeding of TRECVID, 2003.2を参照）であり、色ごとに８つのビン（bin）が存在し、値ごとに５つ存在し、彩度が算出される。通常、最も値の低いビンは、人が区別し辛いため、色に分割される。
【００５１】
この方法により算出される特徴ベクトルは実数値である。２４０次元の特徴ベクトルは、画像ごとに算出され、データセット内の総ての画像の特徴ベクトルは、事前に処理してもよい。この処理ステージの目的は、有益な方法によりデータを２値化することである。最初に、データセットの各特徴の歪度が算出される。特定の特徴が確実に歪められる場合、パーセンタイル値が１００（１００−ｐｔｈ ｐｅｒｃｅｎｔｉｌｅ）以上、例えば、パーセンタイル値が８０の特徴の値は、値「１」をその特徴に割り当て、残りは、値「０」をその特徴に割り当てる。特徴が負に歪められる場合、パーセンタイル値が１００よりも小さい、例えば、パーセンタイル値が２０の特徴の値は、値「１」を割り当て、残りは、値「０」を割り当てる。この処理は、完全な画像データのセットを希薄なバイナリ行列に変更し、これは、各画像をデータセットの残りから最も区別する特徴に集中する。
【００５２】
ｐは、例えば異なるデータセットのために、異なる値が設定され、ｐの上下の値は、同一である必要はなく、すなわち、正に歪んだデータ用の１００−ｐ１と、負に歪んだデータ用のｐ２を有することは理解されるであろう。さらに、前述したような実数値の特徴ベクトルを２値化するアプローチは、画像データに制限されないが、特徴ベクトルに含まれる実数値のデータに適用できる。希薄なデータを取得すべく、パーセンタイル値の閾値は、正に歪んだデータの場合、５０％、好適には７０％よりも大きくすべきである。同様に、パーセンタイル値の閾値は、負に歪んだデータの場合、５０％、好適には３０％よりも小さくすべきである。得られた特徴ベクトルは、希薄であることが好適である。
【００５３】
当業者であれは、ＡＮＤあるいはＯＲ演算子により記載された単一の言葉あるいは複数の言葉を検索して、キーワード検索の異なるアプローチが可能であることが分かるであろう。さらに、画像検索の結果は、マッチのリストから最高のマッチを選択し、これらのマッチを新しいベイジアンセット検索のクエリアイテムとして用いることにより、精度を高めることができる。ユーザがデータベースの画像を検索すると、ラベルの付されていない画像は、スコアの高い画像を検索のキーワードと関連付けることにより自動的にラベルが付される。
【００５４】
ベイジアンセット以外のアルゴリズムにより生成される共通点の測定は、前述した画像検索技術に関連して用いられる。さらに、画像の他の特徴、例えば、ＳＩＦＴフィルタのフィルタ応答から生成される特徴を用いることができる。参照によりここに組み込まれているDavid G. Lowe, "Distinctive image feature form scale-invariant keypoints," International Journal of Computer Vision, 60, 2(2004), pp.91-110および"Method and apparatus for identifying scale invariant features in an image and use of same for locating an object in an image", David G. Lowe, US-B-6,711,293を参照。ベイジアンセット方法は、特徴の特定のセットの使用に限られない。また、前述した画像検索アルゴリズムは、K.A. Heller and Z. Ghahramani(2006)" A Simple Bayesian Framework for Content-Based Image Retrieval", In the IEEE Conference on Computer Vision and Pattern Recognition(参照によりここに組み込まれているCVPR 2006)に記載されている。画像検索および画像に注釈を付す方法を実施する典型的なシステムは実現され、www.inference.phy.cam.ac.uk/vr237/でオンライン化されている。
【００５５】
ベイジアンセットのアルゴリズムは、前述したようなデータセットを整理する方法の基礎として用いてもよい。
【００５６】
特定のラベルｗが付されたアイテムＤ_ｗのセットを考える。このセットのいくつかのアイテムは正確にラベルが付されている一方、いくつかのラベルは誤っており、あるいはノイズである。このようなノイズによるラベルを付すことは、実際のデータではしばしば起こることであり、例えば、Ｇｏｏｇｌｅ（登録商標）により返却された画像を探す場合、多くがクエリーとは無関係と思われる画像があり、同様に、Ｆｌｉｃｋｒ（登録商標）システムの画像が、関連性の範囲が広範である、これらに関連するラベルを有することがある。
【００５７】
この方法の目的は、Ｄｗ内のアイテムを、ラベルｗに対して最も関連するものから最も関連しないものにランク付けすることである。最も関連しないものの端数ｆ（fraction）はセットから取り除かれ、整理用のデータセットを生成する（すなわち、最も関連しないアイテムからラベルを取り除く）。この方法は、以下のＭＡＴＬＡＢ（登録商標）の擬似コードおよび図３を参照することにより理解できる。各アイテムが表される前に、ベクトルは、このアイテムの特徴を備えていることに留意すべきである。
【００５８】
各レベルに関連する上位の評価を受けたアイテムは、そのラベルのよい見本であるべきであるということである。最も評価の低いいくつかのアイテムを省略することにより（前述したような閾値を用いて、あるいはスコアの分布を調べることにより、例えば、閾値よりも低いスコアを有するこれらのアイテムを省略または取り除くことにより）、ノイズデータセットは整理される。従来と同様に、総ての処理は、希薄な行列ベクトルの乗法により実現できる。このデータセットを整理する方法は、一を除いたセット（leave-one-out set）と、一を除いたアイテム（left-one item）との間の同様のスコアを格納する好適な方法を利用できることは理解できるであろう。
【００５９】
ベイジアンセット方法は、アイテムに注釈を付すのに利用してもよい。アイテムは画像でもよいが、この方法は、他の種類のアイテムにも同様に適用される。この方法は、以下のＭＡＴＬＡＢ（登録商標）擬似コードおよび図４を参照することにより理解できる。
【００６０】
当業者であれば理解できるように、アルゴリズムは、ラベルｗが付されたアイテムｘおよびアイテムセットＤｗ用の（詳細に説明したような）ベイジアンセットスコアを用いて、一対の所定のアイテムｘおよびラベルｗのスコアを算出し、上位に評価されたラベルを、使用されるラベルとして返却する。他の好適な同様のスコアを用いてもよいことは理解できるであろう。所定の数のラベルは返却でき、あるいはスコア用の削除値（cut-off value）を用いてもよい。ラベルは、ユーザが選択するために提供され、あるいは自動的に利用される。
【００６１】
例示的な結果
例として、ベイジアンセットのアルゴリズムを２つのデータセットに適用することが、ここで説明され、Ｇｏｏｇｌｅセットウェブページから取得した対応する結果と比較される：Ｇｒｏｌｉｅｒｓ Ｅｎｃｙｃｌｏｐｅｄｉａ内の論文の文章で構成されるＥｎｃｙｃｌｏｐｅｄｉａデータセット、ＥａｃｈＭｏｖｉｅサービスのユーザにより格付けされる映画で構成されるＥａｃｈＭｏｖｉｅデータセット（例えば、P. McJones. Eachmovie collaborative filtering data set. http://reserch.compaq.com/SRC/eachmovie/,1977を参照）。
【００６２】
Ｅｎｃｙｃｌｏｐｅｄｉａデータセットは、３０９９１の論文×１５２７６単語であり、エントリは、各単語が各文書で現れる回数の数である。データは、各単語を標準化し閾値化する行により事前処理（二値化）され、（文書、単語）エントリは、その単語が文書の平均の２倍以上の頻度を有する場合、１である。ハイパーパラメータは、α＝ｃ×ｍおよびβ＝ｃ×（１−ｍ）である前述したようなセットであり、ｍは、総ての文章の平均ベクトルであり、ｃ＝２である。同じ事前（prior）が、両データセットのために用いられる。
【００６３】
ＥａｃｈＭｏｖｉｅデータセットは、最初に１５人よりも少ない人により評価された映画が取り除かれ、２００より少ない映画を評価した人により評価された映画が取り除かれることにより事前処理される。次に、データセットが二値化され、（人、映画）エントリは、三つ星以上の評価がされた映画の場合、値１を有する（可能な各付けは０から５の星である）。データは、映画の人気全体を明らかにすべく標準化された行である。事前処理後のデータセットのサイズは、１８１３の人×１５３２の映画である。
【００６４】
これらの実験の結果および単語および映画クエリー用のＧｏｏｇｌｅセットとの比較は、表２および３に示されている。３つのデータセット総てにおけるベイジアンセットアルゴリズムの動作時間が表１に示されている。総ての実験は、東芝ラップトップの２ＧＨｚＰｅｎｔｉｕｍ４でＭａｔｌａｂ（登録商標）で行われた。
【００６５】
これらの結果を客観的に評価することは、グラウンドトルースがない課題であるため、非常に困難であることに留意すべきである。よいクエリークラスタの人の考えは、他品のとは根本的に異なる。Ｇｏｏｇｌｅセットは、クエリーがウェブ上で発見できるアイテムで構成されている場合に非常によく機能した（例えば、ケンブリッジ大学）。他方、より抽象的な概念の場合（例えば、「soldier」および「warrior」、表２を参照）、ベイジアンセットアルゴリズムは、明らかにより理にかなった結果を返却した。
【００６６】
これらの結果は、以下の方法により評価された：３０の未使用のテーマが、無作為の順序のベイジアンセットおよびＧｏｏｇｌｅセットアルゴリズムのラベルの付されていない結果を示し、表２および３の６つのクエリーのために、よりよりセットの結果であると感じるものを選択するように依頼された。Ｇｏｏｇｌｅセットに対する約９０％の好適なベイジアンセットについての６のクエリーを平均化し、一方的な２項式試験は、Ｇｏｏｇｌｅセットが、６つの事例総てにおいて優れている（ｐ＜０．００１）という仮説を否定した。
【００６７】
指数分布族
ベイジアンセットアルゴリズムは、指数分布族のモデルに適用できる。このようなモデルの分布は、以下の形式により表すことができる。
ここで、ｕ（ｘ）は十分統計量のＫ次元ベクトルであり、θは普通のパラメータであり、ｆおよびｇは、負でない関数である。共役事前（conjugate prior）は、
であり、ここで、
はハイパーパラメータであり、ｈは、分布を標準化する。Ｎ個のアイテムを有するクエリーＤｃ＝｛ｘｉ｝、対象をｘとすると、対象ｘのスコアが、
であることを示すのは困難ではない。この式により、スコアが効果的に算出できる場合を理解することができる。まず第１に、スコアは、クエリー（Ｎ）のサイズ、各対象および総てのクエリから算出される十分統計量に依存する。したがって、Ｕと，Ｘに対応するＭ×Ｋ次元の十分統計量を事前に算出することは理にかなっており、ここで、ＭはアイテムまたはＸの列の数である。第２に、スコアがＵの線形操作であるか否かは、ｌｏｇｈが第２の引数（argument）で線形か否かに依存する。これは、ベルヌーイおよび離散型分布の事例であるが、総ての指数分布族に該当しない。しかしながら、対角共分散（diagonal covariance）ガウスなどの多くの分布の場合、スコアがＵ内で非線形ではないが、これは、非線形性要素（elementwise）をＵに適用することにより算出できる。したがって、希薄な行列の場合、スコアは、ゼロでない要素の数で線形時間（time linear）で算出できる。
【００６８】
結論
前述した実施例により、小さなアイテムのセットで構成されるクエリーを取得し、同じ発生分布から生じる可能性のあるアイテムという意味において、同じセットに属する可能性のある追加的なアイテムを返却するアルゴリズムを説明した。アルゴリズムの出力は、ソートされたアイテムのリストでもよく、またはアイテムが同じセットに属する可能性を判断する単なるスコアでもよい。前者の場合、固定した数のアイテムが返却され、あるいは返却されるログ確率（log probabilities）の閾値を設定してもよい。クエリーを比較できるログ確率としてスコアを解釈すべく、等式１３の項目ｃを含むスコアを算出してもよい。さらに、アルゴリズムにより返却されるアイテムの数を決定する他の動的なスキームも実現できることは当業者に明らかである。
【００６９】
前述したアルゴリズムは広範囲なデータセットされ、好適なプログラム言語を用いて任意の好適な演算プログラムで実現できることは当業者にとって明らかである。アルゴリズムは、スタンドアロンまたはネットワークコンピュータで実現してもよく、例えば、クライアントとサーバとの間のネットワークを介して分配してもよい。後者の場合、サーバが、総ての不可欠な演算を実行できる一方、クライアントはユーザのインタフェースのみを提供し、または演算は、クライアントとサーバの間で分散してもよい。
【００７０】
勿論、特定の実施例が説明されているが、請求の対象は、特定の実施例あるいは実施形態に限定されないことは理解できるであろう。例えば、ある実施例は、装置あるいは装置の組み合わせで動作するように実装されたハードウェアでもよいのに対して、例えば、別の実施例はソフトウェアでもよい。
【００７１】
同様に、実施例は、ファームウェア、あるいは例えば、ハードウェア、ソフトウェア、および／またはファームウェアの組み合わせで実現してもよい。同様に、請求の対象はこの点に限定されないが、ある実施例は、記憶媒体あるいは記憶メディアなどの物を備えてもよい。例えば、１以上のＣＤ−ＲＯＭおよび／またはディスクなどの記憶媒体は、命令を記憶してもよく、コンピュータシステム、コンピュータプラットフォーム、あるいは他のシステムなどのシステムにより実行された場合に、例えば、前述した実施例の一つなどにより実現される請求の対象による方法の実施例をもたらす。一つの例として、コンピュータプラットフォームは、１以上の処理ユニットまたはプロセッサ、ディスプレイ、キーボードおよび／またはマウスなどの１以上の入力／出力装置、スタティックＲＡＭ、ダイナミックＲＡＭ、フラッシュメモリおよび／またはハードドライブなどの１以上のメモリを備えてもよい。
【００７２】
前述した説明では、請求の対象の様々な態様が説明されている。説明の目的のために、特定の数字、システムおよび／または構成が説明され、請求の対象を完全に理解するようにしている。しかしながら、本開示による利益を享受する当業者には、請求の対象は、特定の詳細以外により実現できることは明らかである。他の実施例では、請求の対象を不明瞭にしないように、周知の特徴が省略および／または単純化されている。特定の実施例が示されおよび／または図示されているが、多くの修正例、代替例、変更例および／または均等例が当業者には明らかである。したがって、添付の請求項は、請求の対象の範囲内で、このような修正例および／または変更例を総て網羅するものであることは理解できるであろう。
【図面の簡単な説明】
【００７３】
【図１】図１は、本発明に係る実施例のフロー図である。
【図２】図２は、クエリーを図１の実施例に入力する方法のフロー図である。
【図３】図３は、データセットを整理する方法のフロー図である。
【図４】図４は、アイテムに注釈を付す方法のフロー図である。
【特許請求の範囲】
【請求項１】
１またはそれ以上のクエリーアイテムと、１またはそれ以上の他のアイテムとの共通点を評価するコンピュータが実施する方法であって、前記アイテムがそれぞれ、複数のデジタルで表される特徴ｘｉｊを備える特徴ベクトルｘｉにより表される方法が、
ａ）前記クエリーアイテムを識別する入力を受信するステップと、
ｂ）前記他のアイテムそれぞれの特徴ベクトルｘｉが発生分布ｐ（ｘｉ｜θ）から生じる場合、前記他のアイテムそれぞれに対して、パラメータθにより定まる発生分布ｐ（ｘｉ｜θ）から生じる前記クエリーアイテムの特徴ベクトルｘｉの条件付確率の関数であるスコアを算出するステップと、
ｃ）前記他のアイテムそれぞれのスコア、前記他のアイテムそれぞれのスコアによりソートされる前記他のアイテムの一部または全部のリスト、または最も高いスコアを有するＮ個の他のアイテムのリストを返却するステップとを備えることを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前記関数が、パラメータ値に対して確率分布ｐ（θ）により重み付けされるパラメータθの総ての取り得る値を平均化する効果を有することを特徴とする方法。
【請求項３】
請求項２に記載の方法において、前記特徴ベクトルｘｉが二値ベクトルであり、前記発生分布が、ベルヌーイ分布の生成物（product）であり、前記生成物が、各特徴ｘｉｊのベルヌーイ分布を備えており、パラメータ値に対する前記確率分布ｐ（θ）が、パラメータαおよびβを有するベータ分布ｐ（θ｜α，β）であることを特徴とする方法。
【請求項４】
請求項３に記載の方法において、前記関数が、前記他のアイテムの特徴ベクトルｘｉと、要素が、
により与えられるベクトルｑを含むマトリクスＸの生成物を備えており、
αｊおよびβｊがベータ分布のパラメータであり、
であり、
であり、Ｎが前記クエリーの数であり、和がクエリーアイテムを対象とすることを特徴とする方法。
【請求項５】
Ｎ個のクエリーアイテムと、１またはそれ以上の他のアイテムとの共通点を評価するコンピュータが実施する方法であって、前記アイテムがそれぞれ、複数の２項素性（binary feature）ｘｉｊを備える特徴ベクトルｘｉにより表される方法が、
ａ）前記クエリーアイテムを識別する入力を受信するステップと、
ｂ）要素が、
により与えられる、前記クエリー用のベクトルｑを決定するステップであって、
であり、
であり、和がクエリーアイテムを対象とするステップと、
ｃ）行列Ｘの生成物およびｑの関数としてスコアを算出するステップであって、Ｘが、前記他のアイテムの総ての特徴ベクトルを含む行列であるステップと、
ｄ）前記他のアイテムそれぞれのスコア、前記他のアイテムそれぞれのスコアによりソートされる前記他のアイテムの一部または全部のリスト、または最も高いスコアを有するＮ個の他のアイテムのリストを返却するステップと、を備えることを特徴とする方法。
【請求項６】
請求項４または請求項５に記載の方法であって、前記Ｘの生成物およびｑを算出するために希薄な行列の掛け算を用いるステップを備えることを特徴とする方法。
【請求項７】
請求項４，５または６のいずれか１項に記載の方法であって、前記クエリーアイテムと同様に少なくとも所定の数の特徴ｘｉｊを有する前記他のアイテムｘｉのみが評価されるように前記アイテムを前処理するステップを備えることを特徴とする方法。
【請求項８】
請求項４乃至７のいずれか１項に記載の方法において、前記関数が、前記スコアがクエリー内で比較できるように、
を前記スコアに追加するステップを備えることを特徴とする方法。
【請求項９】
請求項４乃至８のいずれか１項に記載の方法において、αｊ＝ｃｏｎｓｔ・ｍｊおよびβｊ＝ｃｏｎｓｔ・（１−ｍｊ）であり、ｃｏｎｓｔが定数であり、ｍｊが、前記アイテムの総てあるいは一部に対するｘｉｊの平均であることを特徴とする方法。
【請求項１０】
請求項１乃至９のいずれか１項に記載の方法において、前記クエリーアイテムを識別する入力を受信するステップが、
ｉ）検索基準のユーザ入力に応じて、１またはそれ以上のヒットを返却するためにデータベースを検索するステップと、
ｉｉ）前記ヒット内のアイテムのユーザ選択を受信するステップと、
ｉｉｉ）前記クエリーアイテムを決定するために前記選択を利用するステップとを備え、前記方法が、最も高いスコアを有するＭ個の他のアイテムのリストを返却するステップを備えることを特徴とする方法。
【請求項１１】
請求項１乃至１０のいずれか１項に記載の方法において、
前記アイテムが画像であり、
前記クエリーアイテムを識別する入力を受信するステップが、
検索基準のユーザ入力に応じて、前記検索基準に合致する検索可能なラベルに関連する１またはそれ以上の画像を識別するステップと、
前記識別された画像をクエリーアイテムとして識別するステップを備えることを特徴とする方法。
【請求項１２】
請求項１乃至１０のいずれか１項に記載の方法において、前記特徴ベクトルが、ウェブページ、画像、病歴、遺伝子配列、タンパク質、医薬品分子、映画、音楽、商品、人々、投資物件、会社、特許、および言葉から成る群のうちの一つの標本であることを特徴とする方法。
【請求項１３】
請求項１乃至１２のいずれか１項に記載の方法であって、前記クエリーアイテムと同様のアイテム一式をユーザに送信するステップを備えることを特徴とする方法。
【請求項１４】
特定のラベルが付されたアイテムのデータセットを整理する方法であって、
前記データセットのアイテムごとに、請求項１乃至９のいずれか１項に記載の方法を用いて整理用スコアを算出するステップであって、前記クエリーアイテムが、評価されるアイテムを除く、データセット内の総てのアイテムであり、前記他のアイテムが、評価されるアイテムであるステップと、
各整理用スコアに基づいてアイテムを取り除き、前記データセットを整理するステップと、を備えることを特徴とする方法。
【請求項１５】
請求項１４に記載の方法において、最も低いスコアを有する所定の数のアイテム、または閾値よりも小さいスコアを有する総てのアイテムを取り除くステップを備えることを特徴とする方法。
【請求項１６】
アイテムに注釈を付す方法であって、
請求項１乃至９のいずれか１項に記載の方法を用いて、注釈用スコアを算出するステップであって、前記クエリーアイテムが、評価されるラベルが付されたアイテムであり、前記他のアイテムが、注釈を付されたアイテムであり、前記注釈用スコアが、前記他のアイテムのための返却されたスコアであるステップと、
各注釈用スコアに基づいて注釈が付されるアイテムに付される１またはそれ以上のラベルを選択するステップと、を備えることを特徴とする方法。
【請求項１７】
請求項１６に記載の方法において、最も高い注釈用スコアを有する所定の数のアイテムが選択され、または閾値よりも大きい注釈用スコアを有するアイテムが選択されることを特徴とする方法。
【請求項１８】
請求項１乃至１７のいずれか１項に記載の方法において、前記特徴ベクトルが、前記特徴の値を閾値化することにより実数値の特徴ベクトルから生成され、生成された特徴ベクトルが希薄であることを特徴とする方法。
【請求項１９】
請求項１または請求項２に記載の方法において、前記発生分布が、指数型分布族の要素であることを特徴とする方法。
【請求項２０】
請求項１９に記載の方法において、前記発生分布が、対角共分散行列（diagonal covariance matrix）を有するガウス分布であること特徴とする方法。
【請求項２１】
請求項１乃至２０のいずれか１項に記載の方法を実施するように構成されたコンピュータシステム。
【請求項２２】
請求項１乃至２０のいずれか１項に記載の方法を実施するように構成されたコンピュータコード命令を備えるコンピュータプログラム製品。
【請求項２３】
請求項２２に記載のコンピュータプログラム製品を備えるコンピュータ読み取り可能な媒体。
【請求項２４】
請求項２２に記載のコンピュータプログラム製品を備えるデジタル信号。
【請求項２５】
画像のデータベースを検索するコンピュータが実施する方法であって、
検索基準のユーザ入力に応じて、ラベルが付された画像のデータベースを検索して、前記クエリーに合致する少なくとも１のラベルを有する１またはそれ以上の画像を返却するステップと、
前記返却された画像のうちの画像のユーザ選択を受信するステップと、
前記データベース内の前記選択された画像と、ラベルが付されていない画像の共通するスコアを算出するステップと、
ラベルが付されていない画像の各スコアに基づいてラベルの付されていない画像セットを返却するステップと、を備えることを特徴とする方法。
【請求項２６】
特定のラベルを有するラベルが付されたアイテムのデータセットを整理するコンピュータが実施する方法であって、
前記データセットのアイテムごとに、評価されるアイテムを除く、前記データセット内の総てのアイテムと、評価されるアイテムとの共通点の測定値である整理用スコアを算出するステップと、
前記各整理用スコアに基づいてアイテムを取り除き、前記データセットを整理するステップと、を備えることを特徴とする方法。
【請求項２７】
アイテムに注釈を付すコンピュータが実施する方法であって、
評価されるラベルが付されたアイテムと、注釈が付されたアイテムとの共通点の測定値としての各ラベルセット用の注釈用スコアを算出するステップと、
各注釈用スコアに基づいて注釈が付されたアイテムに付される１またはそれ以上のラベルを選択するステップと、を備えることを特徴とする方法。
【請求項１】
１またはそれ以上のクエリーアイテムと、１またはそれ以上の他のアイテムとの共通点を評価するコンピュータが実施する方法であって、前記アイテムがそれぞれ、複数のデジタルで表される特徴ｘｉｊを備える特徴ベクトルｘｉにより表される方法が、
ａ）前記クエリーアイテムを識別する入力を受信するステップと、
ｂ）前記他のアイテムそれぞれの特徴ベクトルｘｉが発生分布ｐ（ｘｉ｜θ）から生じる場合、前記他のアイテムそれぞれに対して、パラメータθにより定まる発生分布ｐ（ｘｉ｜θ）から生じる前記クエリーアイテムの特徴ベクトルｘｉの条件付確率の関数であるスコアを算出するステップと、
ｃ）前記他のアイテムそれぞれのスコア、前記他のアイテムそれぞれのスコアによりソートされる前記他のアイテムの一部または全部のリスト、または最も高いスコアを有するＮ個の他のアイテムのリストを返却するステップとを備えることを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前記関数が、パラメータ値に対して確率分布ｐ（θ）により重み付けされるパラメータθの総ての取り得る値を平均化する効果を有することを特徴とする方法。
【請求項３】
請求項２に記載の方法において、前記特徴ベクトルｘｉが二値ベクトルであり、前記発生分布が、ベルヌーイ分布の生成物（product）であり、前記生成物が、各特徴ｘｉｊのベルヌーイ分布を備えており、パラメータ値に対する前記確率分布ｐ（θ）が、パラメータαおよびβを有するベータ分布ｐ（θ｜α，β）であることを特徴とする方法。
【請求項４】
請求項３に記載の方法において、前記関数が、前記他のアイテムの特徴ベクトルｘｉと、要素が、
により与えられるベクトルｑを含むマトリクスＸの生成物を備えており、
αｊおよびβｊがベータ分布のパラメータであり、
であり、
であり、Ｎが前記クエリーの数であり、和がクエリーアイテムを対象とすることを特徴とする方法。
【請求項５】
Ｎ個のクエリーアイテムと、１またはそれ以上の他のアイテムとの共通点を評価するコンピュータが実施する方法であって、前記アイテムがそれぞれ、複数の２項素性（binary feature）ｘｉｊを備える特徴ベクトルｘｉにより表される方法が、
ａ）前記クエリーアイテムを識別する入力を受信するステップと、
ｂ）要素が、
により与えられる、前記クエリー用のベクトルｑを決定するステップであって、
であり、
であり、和がクエリーアイテムを対象とするステップと、
ｃ）行列Ｘの生成物およびｑの関数としてスコアを算出するステップであって、Ｘが、前記他のアイテムの総ての特徴ベクトルを含む行列であるステップと、
ｄ）前記他のアイテムそれぞれのスコア、前記他のアイテムそれぞれのスコアによりソートされる前記他のアイテムの一部または全部のリスト、または最も高いスコアを有するＮ個の他のアイテムのリストを返却するステップと、を備えることを特徴とする方法。
【請求項６】
請求項４または請求項５に記載の方法であって、前記Ｘの生成物およびｑを算出するために希薄な行列の掛け算を用いるステップを備えることを特徴とする方法。
【請求項７】
請求項４，５または６のいずれか１項に記載の方法であって、前記クエリーアイテムと同様に少なくとも所定の数の特徴ｘｉｊを有する前記他のアイテムｘｉのみが評価されるように前記アイテムを前処理するステップを備えることを特徴とする方法。
【請求項８】
請求項４乃至７のいずれか１項に記載の方法において、前記関数が、前記スコアがクエリー内で比較できるように、
を前記スコアに追加するステップを備えることを特徴とする方法。
【請求項９】
請求項４乃至８のいずれか１項に記載の方法において、αｊ＝ｃｏｎｓｔ・ｍｊおよびβｊ＝ｃｏｎｓｔ・（１−ｍｊ）であり、ｃｏｎｓｔが定数であり、ｍｊが、前記アイテムの総てあるいは一部に対するｘｉｊの平均であることを特徴とする方法。
【請求項１０】
請求項１乃至９のいずれか１項に記載の方法において、前記クエリーアイテムを識別する入力を受信するステップが、
ｉ）検索基準のユーザ入力に応じて、１またはそれ以上のヒットを返却するためにデータベースを検索するステップと、
ｉｉ）前記ヒット内のアイテムのユーザ選択を受信するステップと、
ｉｉｉ）前記クエリーアイテムを決定するために前記選択を利用するステップとを備え、前記方法が、最も高いスコアを有するＭ個の他のアイテムのリストを返却するステップを備えることを特徴とする方法。
【請求項１１】
請求項１乃至１０のいずれか１項に記載の方法において、
前記アイテムが画像であり、
前記クエリーアイテムを識別する入力を受信するステップが、
検索基準のユーザ入力に応じて、前記検索基準に合致する検索可能なラベルに関連する１またはそれ以上の画像を識別するステップと、
前記識別された画像をクエリーアイテムとして識別するステップを備えることを特徴とする方法。
【請求項１２】
請求項１乃至１０のいずれか１項に記載の方法において、前記特徴ベクトルが、ウェブページ、画像、病歴、遺伝子配列、タンパク質、医薬品分子、映画、音楽、商品、人々、投資物件、会社、特許、および言葉から成る群のうちの一つの標本であることを特徴とする方法。
【請求項１３】
請求項１乃至１２のいずれか１項に記載の方法であって、前記クエリーアイテムと同様のアイテム一式をユーザに送信するステップを備えることを特徴とする方法。
【請求項１４】
特定のラベルが付されたアイテムのデータセットを整理する方法であって、
前記データセットのアイテムごとに、請求項１乃至９のいずれか１項に記載の方法を用いて整理用スコアを算出するステップであって、前記クエリーアイテムが、評価されるアイテムを除く、データセット内の総てのアイテムであり、前記他のアイテムが、評価されるアイテムであるステップと、
各整理用スコアに基づいてアイテムを取り除き、前記データセットを整理するステップと、を備えることを特徴とする方法。
【請求項１５】
請求項１４に記載の方法において、最も低いスコアを有する所定の数のアイテム、または閾値よりも小さいスコアを有する総てのアイテムを取り除くステップを備えることを特徴とする方法。
【請求項１６】
アイテムに注釈を付す方法であって、
請求項１乃至９のいずれか１項に記載の方法を用いて、注釈用スコアを算出するステップであって、前記クエリーアイテムが、評価されるラベルが付されたアイテムであり、前記他のアイテムが、注釈を付されたアイテムであり、前記注釈用スコアが、前記他のアイテムのための返却されたスコアであるステップと、
各注釈用スコアに基づいて注釈が付されるアイテムに付される１またはそれ以上のラベルを選択するステップと、を備えることを特徴とする方法。
【請求項１７】
請求項１６に記載の方法において、最も高い注釈用スコアを有する所定の数のアイテムが選択され、または閾値よりも大きい注釈用スコアを有するアイテムが選択されることを特徴とする方法。
【請求項１８】
請求項１乃至１７のいずれか１項に記載の方法において、前記特徴ベクトルが、前記特徴の値を閾値化することにより実数値の特徴ベクトルから生成され、生成された特徴ベクトルが希薄であることを特徴とする方法。
【請求項１９】
請求項１または請求項２に記載の方法において、前記発生分布が、指数型分布族の要素であることを特徴とする方法。
【請求項２０】
請求項１９に記載の方法において、前記発生分布が、対角共分散行列（diagonal covariance matrix）を有するガウス分布であること特徴とする方法。
【請求項２１】
請求項１乃至２０のいずれか１項に記載の方法を実施するように構成されたコンピュータシステム。
【請求項２２】
請求項１乃至２０のいずれか１項に記載の方法を実施するように構成されたコンピュータコード命令を備えるコンピュータプログラム製品。
【請求項２３】
請求項２２に記載のコンピュータプログラム製品を備えるコンピュータ読み取り可能な媒体。
【請求項２４】
請求項２２に記載のコンピュータプログラム製品を備えるデジタル信号。
【請求項２５】
画像のデータベースを検索するコンピュータが実施する方法であって、
検索基準のユーザ入力に応じて、ラベルが付された画像のデータベースを検索して、前記クエリーに合致する少なくとも１のラベルを有する１またはそれ以上の画像を返却するステップと、
前記返却された画像のうちの画像のユーザ選択を受信するステップと、
前記データベース内の前記選択された画像と、ラベルが付されていない画像の共通するスコアを算出するステップと、
ラベルが付されていない画像の各スコアに基づいてラベルの付されていない画像セットを返却するステップと、を備えることを特徴とする方法。
【請求項２６】
特定のラベルを有するラベルが付されたアイテムのデータセットを整理するコンピュータが実施する方法であって、
前記データセットのアイテムごとに、評価されるアイテムを除く、前記データセット内の総てのアイテムと、評価されるアイテムとの共通点の測定値である整理用スコアを算出するステップと、
前記各整理用スコアに基づいてアイテムを取り除き、前記データセットを整理するステップと、を備えることを特徴とする方法。
【請求項２７】
アイテムに注釈を付すコンピュータが実施する方法であって、
評価されるラベルが付されたアイテムと、注釈が付されたアイテムとの共通点の測定値としての各ラベルセット用の注釈用スコアを算出するステップと、
各注釈用スコアに基づいて注釈が付されたアイテムに付される１またはそれ以上のラベルを選択するステップと、を備えることを特徴とする方法。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公表番号】特表２００９−５１７７５０（Ｐ２００９−５１７７５０Ａ）
【公表日】平成２１年４月３０日（２００９．４．３０）
【国際特許分類】
【出願番号】特願２００８−５４２８３８（Ｐ２００８−５４２８３８）
【出願日】平成１８年１２月１日（２００６．１２．１）
【国際出願番号】ＰＣＴ／ＧＢ２００６／００４５０４
【国際公開番号】ＷＯ２００７／０６３３２８
【国際公開日】平成１９年６月７日（２００７．６．７）
【出願人】（５０７１７０１９２）ユーシーエル ビジネス ピーエルシー (3)
【Ｆターム（参考）】
【公表日】平成２１年４月３０日（２００９．４．３０）
【国際特許分類】
【出願日】平成１８年１２月１日（２００６．１２．１）
【国際出願番号】ＰＣＴ／ＧＢ２００６／００４５０４
【国際公開番号】ＷＯ２００７／０６３３２８
【国際公開日】平成１９年６月７日（２００７．６．７）
【出願人】（５０７１７０１９２）ユーシーエル ビジネス ピーエルシー (3)
【Ｆターム（参考）】
[ Back to top ]