(57)【要約】問合せに対しデータベース内のドキュメントの関連性スコアを推定するためのドキュメント関連性ファンクションを決定する方法及びコンピュータプログラム製品が提供される。複数のテスト問合せの各々に対し、結果ドキュメントの各セットが収集される。各テスト問合せに対し、各結果セット内のドキュメントのサブセットが選択され、そしてトレーニング関連性スコアのセットがサブセット内のドキュメントに指定される。一実施形態では、トレーニング関連性スコアの少なくとも幾つかが、対応する問合せに対して提示されたドキュメントの個々の関連性スコアを決定するヒューマンサブジェクトにより指定される。最終的に、複数のテスト問合せ、ドキュメントのサブセット、及びトレーニング関連性スコアのセットに基づいて関連性ファンクションが決定される。
2006524869.tif 000002
【特許請求の範囲】
【請求項１】
問合せに対してデータベース内のドキュメントの関連性スコアを推定するためのドキュメント関連性ファンクションを決定する方法において、
（ａ）複数のテスト問合せの各々に対し前記データベースからドキュメントの各結果セットを収集するステップと、
（ｂ）前記複数のテスト問合せの各テスト問合せに対し、
前記各結果セット内のドキュメントのサブセットを選択し、そして
前記サブセット内のドキュメントにトレーニング関連性スコアのセットを指定する、
というようにするステップと、
（ｃ）前記複数のテスト問合せ、前記ドキュメントのサブセット及び前記トレーニング関連性スコアのセットに基づいて関連性ファンクションを決定するステップと、
を備えた方法。
【請求項２】
前記決定された関連性ファンクションに少なくとも一部分基づいてドキュメントランク付けファンクションを決定し、該ドキュメントランク付けファンクションは、
前記データベースからドキュメントのセットを受け取り、
問合せを受け取り、そして
前記ドキュメントのセットの順序付けされたリストを出力し、このリストは、前記関連性ファンクションにより決定された最大の関連性スコアを有する前記セットにおけるドキュメントが該リストにおける第１のドキュメントとなるように順序付けされる、
請求項１に記載の方法。
【請求項３】
前記複数のテスト問合せは、
ユーザによりサーチエンジンに提示される問合せのログから問合せストリングの予備的セットをサンプリングし、
ユーザベースの知識の範囲外であると決定された問合せを前記予備的セットから排除し、そして
前記予備的セット内の残りの問合せを前記複数のテスト問合せに指定する、
ということにより選択される請求項１に記載の方法。
【請求項４】
前記複数のテスト問合せは、
１ワードエントリーの語彙集からワードをサンプリングし、そして
このようにサンプリングされたワードの各々を前記複数のテスト問合せに指定する、
ということにより選択される請求項１に記載の方法。
【請求項５】
前記複数のテスト問合せを選択する段階は、更に、前記語彙集からサンプリングされた２つ以上のワードの結合を選択しそしてそれら結合を前記複数のテスト問合せに指定することを含む、請求項４に記載の方法。
【請求項６】
前記サブセットを選択する段階は、
各テスト問合せに対し、各結果セットからドキュメントを選択し、その選択されたドキュメントを現在問合せに関連付ける代用関連性スコアを決定し、そしてその決定された代用関連性スコアに基づいて前記選択されたドキュメントを複数の関連性ティアの少なくとも１つの関連性ティアに指定し、そして
各関連性ティアが少なくとも各所定数のドキュメントを含むまで前記ドキュメント選択段階を繰り返す、
ということを含む請求項１に記載の方法。
【請求項７】
前記選択されたドキュメントを指定する段階は、前記代用関連性スコアがティアの各所定スレッシュホールド値より大きいところの前記複数の関連性ティア内の各ティアに前記選択されたドキュメントを指定することを含む、請求項６に記載の方法。
【請求項８】
前記選択されたドキュメントを指定する段階は、前記代用関連性スコアが前記ティアに関連した関連性スコアの各所定範囲内に入るところの前記複数の関連性ティア内のティアに前記選択されたドキュメントを指定することを含む、請求項６に記載の方法。
【請求項９】
前記複数のティアに関連した関連性スコアの各所定範囲は非重畳である、請求項８に記載の方法。
【請求項１０】
代用関連性スコアを決定する段階は、
問合せをサーチエンジンに提示し、そして
前記サーチエンジンにより与えられる結果ページのリストにおけるドキュメントの位置の関数として代用関連性スコアを決定する、
ということを含む請求項６に記載の方法。
【請求項１１】
トレーニング関連性スコアのセットを指定する段階は、
前記サブセット内の第１の複数のドキュメントの各々を複数のヒューマンサブジェクトに提示し、前記第１の複数のドキュメントは、所定範囲内の代用関連性スコアを有し、１つ以上のヒューマンサブジェクトが、問合せに対して提示される各ドキュメントの個々の関連性スコアを決定し、そして
前記ヒューマンサブジェクトにより決定された個々の関連性スコアに基づいて、問合せに対して提示された各ドキュメントにトレーニング関連性スコアを指定する、
ということを含む請求項６に記載の方法。
【請求項１２】
前記個々の関連性スコアは、所定範囲から選択された数字であり、そして前記指定段階は、個々の関連性スコアの演算平均を計算することを含む、請求項１１に記載の方法。
【請求項１３】
前記ドキュメントに対して決定された代用関連性スコアに基づいてトレーニング関連性スコアを前記サブセット内の第２の複数のドキュメントの各々に指定する段階を更に備えた、請求項１１に記載の方法。
【請求項１４】
前記選択されたドキュメントに対する代用関連性スコアを決定する段階は、
複数のサーチエンジンに問合せを提示し、各サーチエンジンは、データベースから結果ページの各リストを返送し、結果ページの各リストは、前記選択されたドキュメントを含み、そして
前記結果ページのリストにおける前記選択されたドキュメントの平均的数値位置に基づいて前記代用関連性スコアを決定する、
ということを含む請求項６に記載の方法。
【請求項１５】
トレーニング関連性スコアのセットを指定する段階は、
前記サブセット内の第１の複数のドキュメントの各々を各複数のヒューマンサブジェクトに提示し、各複数のヒューマンサブジェクトにおける各ヒューマンサブジェクトは、問合せに対して提示されたドキュメントの個々の関連性スコアを決定し、そして
前記ヒューマンサブジェクトにより決定された個々の関連性スコアに基づいて、問合せに対して提示される各ドキュメントにトレーニング関連性スコアを指定する、
ということを含む請求項１に記載の方法。
【請求項１６】
個々の関連性スコアは、所定範囲から選択された数字であり、そして前記指定段階は、個々の関連性スコアの演算平均を計算することを含む、請求項１５に記載の方法。
【請求項１７】
前記サブセット内の第２の複数のドキュメントの各々に所定の低いトレーニング関連性スコアを指定する段階を更に含む、請求項１５に記載の方法。
【請求項１８】
関連性ファンクションを決定する段階は、
関連性ファンクションの構成に予想変数として使用されるべき特徴のセットを決定し、該セットにおける特徴の各々は、各ドキュメント、各問合せ、又はその両方の１つ以上のプロパティのファンクションを含み、
パラメータ及びベースファンクションの限定セットに関して前記関連性ファンクションをパラメータ化し、各ベースファンクションは、前記特徴のサブセットを入力として得、そして値を出力し、
特定の問合せに対する所与のドキュメントのトレーニング関連性スコアを、その特定の問合せに対する所与のドキュメントに適用されたドキュメント関連性ファンクションにより発生される値に関連付ける部分エラーを定義し、
複数の所与のドキュメント及び複数の特定の問合せに対して部分エラーの定義を繰り返して、部分エラーのセットを発生し、そして
前記部分エラーのセットの関数である全エラーを最小にするように前記パラメータを選択する、
ということを含む請求項１に記載の方法。
【請求項１９】
前記特徴のセットは、少なくとも１つの問合せ従属特徴と、少なくとも１つの問合せ独立特徴とを含む、請求項１８に記載の方法。
【請求項２０】
前記特徴のセットは、Ｅｉｇｎｅｎｒａｎｋ(ＥＲ)、Ｈｕｂ、ＵＲＬ深さ、クオリティスコア、スパムインデックス、家族の馴染みやすさ、ドキュメントの長さ、アンカーテキストスコア、一致位置、一致頻度、用語の重み、及び接近性の少なくとも１つを含む、請求項１８に記載の方法。
【請求項２１】
前記特徴のセットは、Ｅｉｇｎｅｎｒａｎｋ(ＥＲ)、Ｈｕｂ、ＵＲＬ深さ、クオリティスコア、スパムインデックス、家族の馴染みやすさ、ドキュメントの長さ、アンカーテキストスコア、一致位置、一致頻度、用語の重み、及び接近性の少なくとも４つを含む、請求項１８に記載の方法。
【請求項２２】
部分エラーを定義する段階は、
クラスのセットを定義し、
所与のドキュメントのトレーニング関連性スコアに少なくとも一部分基づいて前記クラスの１つ以上に所与のドキュメントを指定する、
ということを含む請求項１８に記載の方法。
【請求項２３】
前記部分エラーは、比によって少なくとも一部分決定され、この比は、関連性ファンクションと差との比であり、この差は、１と関連性ファンクションとの間の差である、請求項２２に記載の方法。
【請求項２４】
前記部分エラーは、ドキュメントのトレーニング関連性スコアと、ドキュメント関連性ファンクションにより形成された値との間の差の２乗の関数となるように定義される、請求項１８に記載の方法。
【請求項２５】
前記部分エラーは、ドキュメントのトレーニング関連性スコアと、ドキュメント関連性ファンクションにより形成された値との間の差の絶対値の関数となるように定義される、請求項１８に記載の方法。
【請求項２６】
前記ベースファンクションの少なくとも１つは、ノード分類ツリーであり、そしてパラメータの限定セットは、それに関連したスプリット変数、スプリット位置、及び終端ノード値を含む、請求項１８に記載の方法。
【請求項２７】
全エラーを最小にするようにパラメータを選択する段階はブースト手順により実行される、請求項１８に記載の方法。
【請求項２８】
全エラーを最小にするようにパラメータを選択する段階は、ＧｒａｄｉｅｎｔＢｏｏｓｔ手順により達成され、そして前記ベースファンクションは、少なくとも１つの分類及び回帰ツリー（ＣＡＲＴ）を含む、請求項１８に記載の方法。
【請求項２９】
コンピュータシステムに関連して使用するためのコンピュータプログラム製品であって、該コンピュータプログラム製品は、コンピュータ読み取り可能な記憶媒体と、該媒体におけるコンピュータプログラムメカニズムとを備え、該コンピュータプログラムメカニズムは、
（ａ）複数のテスト問合せの各々に対してデータベースからドキュメントの各結果セットを収集するための収集モジュールと、
（ｂ）複数のテスト問合せの各テスト問合せに対して各結果セット内のドキュメントのサブセットを選択するためのサンプリングモジュールと、
（ｃ）各選択されたサブセット内のドキュメントにトレーニング関連性スコアのセットを指定するためのスコア付けモジュールと、
（ｄ）前記複数のテスト問合せ、前記ドキュメントのサブセット、及び前記トレーニング関連性スコアのセットに基づいて、関連性ファンクションを決定するための関連性ファンクション発生モジュールと、
を備えているコンピュータプログラム製品。
【請求項３０】
前記関連性ファンクション発生モジュールは、更に、前記決定された関連性ファンクションに少なくとも一部分基づいてドキュメントランク付けファンクションを決定するための命令を含み、このドキュメントランク付けファンクションは、
前記データベースからドキュメントのセットを受け取り、
問合せを受け取り、そして
前記ドキュメントのセットの順序付けされたリストを出力し、このリストは、前記関連性ファンクションにより決定される最も高い関連性スコアを有する前記セット内のドキュメントがこのリスト上の最初のドキュメントとなるように順序付けされる、
請求項２９に記載のコンピュータプログラム製品。
【請求項３１】
前記収集モジュールは、複数のテスト問合せを発生するための命令を含み、これは、
ユーザによりサーチエンジンへ提示された問合せのログから問合せストリングの予備的なセットをサンプリングし、
前記予備的なセットから、ユーザのベースの知識の範囲外であると決定された問合せを排除し、そして
前記予備的なセットにおける残りの問合せを前記複数のテスト問合せに指定する、
ことにより行う請求項２９に記載のコンピュータプログラム製品。
【請求項３２】
前記収集モジュールは、複数のテスト問合せを発生するための命令を含み、これは、
１ワードエントリーの語彙集からワードをサンプリングし、そして
このようにサンプリングされたワードの各々を前記複数のテスト問合せに指定する、
ことにより行う請求項２９に記載のコンピュータプログラム製品。
【請求項３３】
前記収集モジュールは、更に、前記語彙集からサンプリングされた２つ以上のワードの結合を選択し、そしてその結合を前記複数のテスト問合せに指定するための命令を含む、請求項２９に記載のコンピュータプログラム製品。
【請求項３４】
前記サンプリングモジュールは、
各々のテスト問合せに対し、各々の結果セットからドキュメントを選択し、この選択されたドキュメントを現在問合せに関連付ける代用関連性スコアを決定し、そしてその決定された代用関連性スコアに基づいて前記選択されたドキュメントを複数の関連性ティアの少なくとも１つの関連性ティアに指定し、そして
各関連性ティアが少なくとも各所定数のドキュメントを含むまで、前記ドキュメント選択段階を繰り返す、
ための命令を含む請求項２９に記載のコンピュータプログラム製品。
【請求項３５】
前記サンプリングモジュールは、更に、前記代用関連性スコアが前記ティアの各所定スレッシュホールド値より大きいところの前記複数の関連性ティア内の各ティアに前記選択されたドキュメントを指定するための命令を含む、請求項２９に記載のコンピュータプログラム製品。
【請求項３６】
前記サンプリングモジュールは、更に、前記代用関連性スコアが、前記ティアに関連した各所定の関連性スコア範囲内に入るところの前記複数の関連性ティア内のティアに前記選択されたドキュメントを指定するための命令を含む、請求項３５に記載のコンピュータプログラム製品。
【請求項３７】
前記複数のティアに関連した関連性スコアの各所定範囲は非重畳である、請求項３５に記載のコンピュータプログラム製品。
【請求項３８】
前記サンプリングモジュールは、更に、
各テスト問合せに対しサーチエンジンに問合せを提示し、そして
前記サーチエンジンにより与えられた結果ページのリストにおけるドキュメントの位置の関数として前記サブセット内のドキュメントの代用関連性スコアを決定する、
ための命令を含む請求項３５に記載のコンピュータプログラム製品。
【請求項３９】
前記スコア付けモジュールは、
前記サブセット内の第１の複数のドキュメントの各々を複数のヒューマンサブジェクトに提示し、第１の複数のドキュメントは所定範囲内の代用関連性スコアを有し、各ヒューマンサブジェクトは、問合せに対して提示されたドキュメントの個々の関連性スコアを決定するものであり、そして
前記ヒューマンサブジェクトにより決定された個々の関連性スコアに基づいて、問合せに対して提示された各ドキュメントにトレーニング関連性スコアを指定する、
ための命令を含む請求項３５に記載のコンピュータプログラム製品。
【請求項４０】
前記個々の関連性スコアは、所定範囲から選択された数字であり、そして前記指定段階は、前記個々の関連性スコアの演算平均を計算することを含む、請求項３９に記載のコンピュータプログラム製品。
【請求項４１】
前記スコア付けモジュールは、更に、前記サブセット内の第２の複数のドキュメントの各々に、前記ドキュメントに対して決定された代用関連性スコアに基づいてトレーニング関連性スコアを指定するための命令を含む、請求項３９に記載のコンピュータプログラム製品。
【請求項４２】
前記サンプリングモジュールは、更に、前記選択されたドキュメントを現在の問合せに関連付ける代用関連性スコアを決定するための命令を含み、これは、
複数のサーチエンジンに問合せを提示し、各サーチエンジンはデータベースから結果ページの各リストを返送し、結果ページの各リストは、選択されたドキュメントを含み、そして
前記結果ページのリストにおける前記選択されたドキュメントの平均数値位置に基づいて代用関連性スコアを決定する、
ことにより行う請求項３５に記載のコンピュータプログラム製品。
【請求項４３】
前記スコア付けモジュールは、
各々の選択されたサブセット内の第１の複数のドキュメントの各々を複数のヒューマンサブジェクトに提示し、各ヒューマンサブジェクトは、問合せに対して提示されたドキュメントの個々の関連性スコアを決定し、そして
前記ヒューマンサブジェクトにより決定された個々の関連性スコアに基づいて、問合せに対して提示された各ドキュメントにトレーニング関連性スコアを指定する、
ための命令を含む請求項２９に記載のコンピュータプログラム製品。
【請求項４４】
個々の関連性スコアは、所定範囲から選択された数字であり、そして前記指定段階は、個々の関連性スコアの演算平均を計算することを含む、請求項４３に記載のコンピュータプログラム製品。
【請求項４５】
前記スコア付けモジュールは、更に、各々の選択されたサブセット内の第２の複数のドキュメントの各々に所定の低いトレーニング関連性スコアを指定するための命令を含む、請求項４４に記載のコンピュータプログラム製品。
【請求項４６】
前記決定モジュールは、
パラメータ及びベースファンクションの固定セットに関して関連性ファンクションをパラメータ化し、各ベースファンクションは、特徴の各入力セットに対する値を出力し、各特徴は、各ドキュメント、各問合せ又はその両方の１つ以上のプロパティの関数を含み、
特定の問合せに対する所与のドキュメントのトレーニング関連性スコアを、前記特定の問合せに対する所与のドキュメントに適用されるドキュメント関連性ファンクションにより発生された値に関連付ける部分エラーを定義し、
複数の所与のドキュメント及び複数の特定の問合せに対して部分エラーの定義を繰り返して、部分エラーのセットを形成し、そして、
部分セラーのセットの関数である全エラーを最小にするように前記パラメータを選択する、
ための命令を含む請求項２９に記載のコンピュータプログラム製品。
【請求項４７】
前記特徴のセットは、少なくとも１つの問合せ従属特徴と、少なくとも１つの問合せ独立特徴とを含む、請求項４６に記載のコンピュータプログラム製品。
【請求項４８】
前記特徴のセットは、Ｅｉｇｎｅｎｒａｎｋ(ＥＲ)、Ｈｕｂ、ＵＲＬ深さ、クオリティスコア、スパムインデックス、家族の馴染み易さ、ドキュメントの長さ、アンカーテキストスコア、一致位置、一致頻度、用語の重み及び接近性の少なくとも１つを含む、請求項４６に記載のコンピュータプログラム製品。
【請求項４９】
前記特徴のセットは、Ｅｉｇｎｅｎｒａｎｋ(ＥＲ)、Ｈｕｂ、ＵＲＬ深さ、クオリティスコア、スパムインデックス、家族の馴染み易さ、ドキュメントの長さ、アンカーテキストスコア、一致位置、一致頻度、用語の重み及び接近性の少なくとも４つを含む、請求項４６に記載のコンピュータプログラム製品。
【請求項５０】
前記決定モジュールは、更に、
クラスのセットを定義し、
所与のドキュメントのトレーニング関連性スコアに少なくとも一部分基づいてクラスの１つ以上に所与のドキュメントを指定する、
ための命令を含む請求項４６に記載のコンピュータプログラム製品。
【請求項５１】
前記決定モジュールは、更に、部分エラーを定義するための命令を含み、この部分エラーは比によって少なくとも一部分定義され、この比は、関連性ファンクションと差との比であり、この差は、１と関連性ファンクションとの間の差である、請求項４６に記載のコンピュータプログラム製品。
【請求項５２】
前記決定モジュールは、更に、ドキュメントのトレーニング関連性スコアと、ドキュメント関連性ファンクションにより形成された値との間の差の２乗の関数であるように前記部分エラーを定義するための命令を含む、請求項４６に記載のコンピュータプログラム製品。
【請求項５３】
前記決定モジュールは、更に、ドキュメントのトレーニング関連性スコアと、前記ドキュメント関連性ファンクションにより形成された値との間の差の絶対値の関数であるように前記部分エラーを定義するための命令を含む、請求項４６に記載のコンピュータプログラム製品。
【請求項５４】
前記ベースファンクションの少なくとも１つは、ノード分類ツリーであり、そして前記パラメータの限定セットは、関連するスプリット変数、スプリット位置、及び終端ノード値を含む、請求項４６に記載のコンピュータプログラム製品。
【請求項５５】
前記決定モジュールは、更に、全エラーを最小にするパラメータの選択を、ブースト手順を経て行うようにするための命令を含む、請求項４６に記載のコンピュータプログラム製品。
【請求項５６】
上記決定モジュールは、
少なくとも１つの分類及び回帰ツリー（ＣＡＲＴ）に関して関連性ファンクションをパラメータ化し、そして
全エラーを最小にするパラメータの選択を、ＧｒａｄｉｅｎｔＢｏｏｓｔ手順を経て行うようにする、
ための命令を含む請求項４６に記載のコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネット又はイントラネットに結合されたサーバーに記憶されたドキュメントのインデックスのように、データベース内のドキュメントを探索するためのサーチエンジンの分野に係り、より詳細には、本発明は、問合せに対するデータベース内のドキュメントの関連性スコアを推定するためのドキュメント関連性ファンクションを決定する方法及び装置に係る。
【背景技術】
【０００２】
ドキュメントの大規模で多様性のあるコレクションをインデックし、しかも、問合せに応答して結果ドキュメントの短い関連性リストをユーザに返送することのできるサーチエンジンの開発は、長年、困難な問題と認識されてきた。世界中のホストコンピュータに記憶された数十億のドキュメントを現在含んでいるインターネットは、特に多様性のある大規模なドキュメントコレクションを表わしている。サーチエンジンのユーザは、通常、短い問合せをサーチエンジンに供給し、この問合せは、「危険な廃棄物」又は「カントリーミュージック」等の幾つかの用語(term)のみを含み、サーチエンジンが関連性ドキュメントのリストを返送することを期待する。現実に、サーチエンジンは、数十又は数百のドキュメントを返送できるが、ほとんどのユーザは、サーチエンジンにより返送されたリストの最上位３つ又は２つのドキュメントしか見ないことが多い。従って、ユーザにとって有用であるために、サーチエンジンは、ユーザが提示した問合せが与えられると、数十億のドキュメントの中から、人間のユーザに最も関心のある２つ又は３つのドキュメントを決定できねばならない。過去において、サーチエンジンの設計者は、問合せ及びドキュメントを入力として得て関連値を返送する関連性（リラバンス(relevance)）ファンクションを構成するよう試みていた。その関連値は、例えば、サーチエンジンによりインデックスされたドキュメントのリストを生成するのに使用でき、このリストは、この必要性に応じるために問合せに対する関連性の順序でドキュメントをランク付けする。このリストにおける最上位２つ又は３つのドキュメントがユーザにとって有用であるためには、その基礎となる関連性ファンクションが、問合せに対する所与のドキュメントの関連性を正確且つ迅速に決定できねばならない。
【０００３】
真の関連性のユーザ認識は、多数のファクタにより影響されるが、その多くは非常に主観的である。これらの好みは、一般に、関連性ファンクションを定義するルールのアルゴリズムセットにおいて捕えることが困難である。更に、これらの主観的ファクタは、時間と共に変化することがあり、例えば、現在事象が特定の問合せ用語に関連付けられたときに変化することがある。別の例として、インターネットで入手できるドキュメントの集合的コンテンツの時間的変化も、特定の問合せに対する所与のドキュメントの相対的関連性のユーザ認識を変化させ得る。強く関連していると認識しないドキュメントを含む返送リストをサーチエンジンから受け取るユーザは、直ちに苛立つ状態となり、サーチエンジンの使用を断念することになる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
上記背景に鑑み、問合せに対するドキュメント関連性の１つ以上の人間ユーザ認識を反映しながらも、コンピュータのアルゴリズムとして容易に実施することのできるドキュメントランク付けファンクションを決定する方法を案出することが要望される。更に、データベース内の基礎的なドキュメント及び時間に伴うユーザの関心の両方の変化に迅速に適応できる方法を案出することも要望される。
【課題を解決するための手段】
【０００５】
本発明は、問合せに対するデータベース内のドキュメントの関連性スコアを推定するためのドキュメント関連性ファンクションを決定する方法を提供する。第１に、複数のテスト問合せの各々に対して、結果ドキュメントの各セットがデータベースから収集される。次いで、各テスト問合せに対して、各結果セット内のドキュメントのサブセットが選択され、そしてトレーニング関連性スコアのセットがサブセット内のドキュメントに指定される。最終的に、複数のテスト問合せ、ドキュメントのサブセット、及びトレーニング関連性スコアのセットに基づいて、関連性ファンクションが決定される。
【０００６】
ある実施形態は、更に、各問合せに対してドキュメントの各結果セット内のドキュメントのサブセットを選択する方法を提供する。第１に、各結果セットからドキュメントが選択される。次いで、その選択されたドキュメントを現在問合せに関連付ける代用関連性スコアが決定される。次いで、この決定された代用関連性スコアに基づいて、その選択されたドキュメントが、複数の関連性ティア（段）の中の少なくとも１つの関連性ティアに指定される。次いで、終了条件に到達するまで、選択、決定及び指定が繰り返される。終了条件とは、各関連性ティアが少なくとも各所定数のドキュメントを含むことでもよいし、又は最も高い関連性ティアが少なくとも所定数のドキュメントを含むことでもよい。他の終了条件を使用してもよい。
【０００７】
これら実施形態のあるものは、更に、各問合せに対しドキュメントの各結果セットから選択されたドキュメントのサブセット内のドキュメントにトレーニング関連性スコアのセットを指定する方法を提供する。第１に、結果セットからのドキュメントのサブセット内の第１の複数のドキュメントの各々が、各複数のヒューマンサブジェクトに対して提示される。第１の複数のドキュメントにおけるドキュメントは、所定の範囲内の代用関連性スコアを有する。１つ以上のヒューマンサブジェクトは、問合せに対して提示されたドキュメントの個々の関連性スコアを決定する。次いで、問合せに対して提示された各ドキュメントに、ヒューマンサブジェクトにより決定された個々の関連性スコアに基づいて、トレーニング関連性スコアが指定される。
【０００８】
ある実施形態では、関連性ファンクションを決定するために、関連性ファンクションの構成に予想変数として使用されるべき特徴のセットが最初に構成される。このセットにおける特徴の各々は、各ドキュメント、各問合せ又はその両方の１つ以上のプロパティの関数でよい。従って、関連性ファンクションは、パラメータ（例えば、係数）及びベースファンクションの限定セットに関してパラメータ化される。関連性ファンクションは、特徴のセットをその入力として得て、関連値をその出力として返送する。同様に、各ベースファンクションは、特徴のサブセットをその入力として得て、値を出力する。次いで、特定の問合せに対する所与のドキュメントのトレーニング関連性スコアを、その特定の問合せに対する所与のドキュメントに適用されたドキュメントランク付けファンクションにより発生される値に関連付けるための部分エラーが定義される。複数の所与のドキュメント及び複数の特定の問合せに対してこの部分エラーの定義を繰り返して、部分エラーのセットが形成される。次いで、部分エラーのセットの関数である合計エラーを最小にするようにパラメータが選択される。最終的に、ドキュメント及び問合せが与えられたときに関連値を発生する関連性ファンクションが決定される。任意であるが、ドキュメントランク付けファンクションは、関連性ファンクションに基づいて決定される。ドキュメントランク付けファンクションは、問合せ及び複数のドキュメントが与えられると、リスト内のドキュメントの関連値が単調に減少するようなドキュメントの順序付けされたリストを発生する。
【０００９】
本発明の別の態様は、コンピュータシステムに関連して使用するためのコンピュータプログラム製品を提供する。このコンピュータプログラム製品は、コンピュータ読み取り可能な記憶媒体と、該媒体に記憶されたコンピュータプログラムメカニズムとを備えている。このコンピュータプログラムメカニズムは、次のものを含む。
（ａ）複数のテスト問合せの各々に対してデータベースからドキュメントの各結果セットを収集するための収集モジュール；
（ｂ）複数のテスト問合せの各テスト問合せに対して各結果セット内のドキュメントのサブセットを選択するためのサンプリングモジュール；
（ｃ）各選択されたサブセット内のドキュメントにトレーニング関連性スコアのセットを指定するためのスコア付けモジュール；及び
（ｄ）複数のテスト問合せ、ドキュメントのサブセット、及びトレーニング関連性スコアのセットに基づいて、関連性ファンクションを決定するための関連性ファンクション発生モジュール。
【００１０】
本発明の上記特徴及び効果、並びにその付加的な特徴及び効果は、添付図面を参照した本発明の好ましい実施形態の以下の詳細な説明から明確に理解されよう。多数の図面全体にわたり対応する部分が同じ参照番号で示されている。
【発明を実施するための最良の形態】
【００１１】
図１を参照すれば、コンピュータネットワーク１００は、ネットワーク１０５に接続された１つ以上のクライアントコンピュータ１０４を備えている。ネットワーク１０５は、インターネットでよく、又は他の実施形態では、イントラネットでよい。ネットワーク１０５がインターネットである実施形態では、ワールドワイドウェブ１０２として知られたドキュメント１０３のコレクションが、クライアントコンピュータによりネットワーク１０５を経て検索するのに利用できる。インターネットでは、ドキュメントは、「ｈｔｔｐ：／／ｗｗｗ．ａｖ．ｃｏｍ．」のようなユニフォームリソースロケータにより探索される。このＵＲＬをドキュメントサーバー（図示せず）に供給することにより、ＵＲＬに対応するドキュメント１０３をアクセスすることができる。
【００１２】
ドキュメント及びクライアントコンピュータに加えて、コンピュータネットワーク１００は、サーチエンジンを備えている。インターネットに使用できるサーチエンジンは、例えば、ＡｌｔａＶｉｓｔａ（ＵＲＬｈｔｔｐ：／／ｗｗｗ．ａｖ．ｃｏｍにおける）、Ｇｏｏｇｌｅ（ＵＲＬｈｔｔｐ：／／ｗｗｗ．ｇｏｏｇｌｅ．ｃｏｍにおける）、及びＹａｈｏｏ！（ＵＲＬｈｔｔｐ：／／ｗｗｗ．ｙａｈｏｏ．ｃｏｍにおける）を含むが、これらに限定されない。サーチエンジンは、通常、ワールドワイドウェブにおけるドキュメントをインデックスするデータベースを備えている。特定の話題に関連したドキュメントの検索を希望するが、そのようなドキュメントのＵＲＬに確信がもてないか又はそれを知らないクライアントコンピュータ１０４−１のユーザは、通常、ネットワーク１０５を経て、サーチエンジンへ問合せ１１２を提示する。サーチエンジン１０６は、問合せ１１２を受け取った後に、ドキュメントのデータベースを検査し、ユーザがその提示した問合せ１１２に強く関連しているとみなされるドキュメントを見出すよう試みる。
【００１３】
ある実施形態では、ドキュメント関連性ファンクションを決定する方法が提供され、この関連性ファンクションは、サーチエンジン１０６により使用されるもので、関連性ファンクション決定システム１０８により決定される。この関連性ファンクション決定システム１０８は、ある実施形態では、サーチエンジン１０６を実施するコンピュータシステムとは異なるコンピュータシステムにおいて実施されてもよい。他の実施形態では、単一のコンピュータシステムを使用して、サーチエンジンの機能と、関連性ファンクション決定システム１０８の機能とを実施してもよい。
【００１４】
関連性ファンクション決定システム１０８の実施形態では、複数のテスト問合せに対してドキュメントの結果セットが収集される。ある実施形態では、クライアントコンピュータ１０４のユーザによりサーチエンジン１０６へ提示された問合せのログに少なくとも一部分基づいて複数のテスト問合せが決定される。ある実施形態では、テスト問合せを１つ以上のサーチエンジン１０６へ提示し、そしてそこからの応答、通常、ＵＲＬのリストを受け取ることにより、ドキュメントの結果セットが決定される。関連性ファンクション決定システムは、任意であるが、ネットワーク１０５に結合され、従って、結果セットにおける１つ以上のドキュメントを検索することができる。関連性ファンクション決定システムの典型的な実施形態は、１つ以上のヒューマンサブジェクト１１０へのアクセスを含む。このヒューマンサブジェクトを使用して、複数のテスト問合せにおける１つ以上の問合せに対して結果セットにおけるドキュメントのトレーニング関連性スコアのセットを与えることができる。
【００１５】
図２Ａを参照すれば、典型的な問合せ１１２は、１つ以上の用語２０２を含む。例えば、図示された問合せは、３つの用語を含む。このような問合せは、「３用語」問合せと称される。同様に、１つの用語しか含まない問合せは、「１用語」問合せと称され、そして２つの用語を含む問合せは、「２用語」問合せと称される。個々の用語は、ユーザにより提示されたときに、ブランクスペース又はおそらく他の何らかの手段で境界定めされる。
【００１６】
図２Ｂを参照すれば、複数のテスト問合せ２０４は、１つ以上の問合せ１１２を含む。ある実施形態では、複数のテスト問合せ２０４は、少なくとも１つの１用語問合せ１１２−１と、少なくとも１つの２用語問合せ１１２−２とを含む。他の実施形態では、複数のテスト問合せ２０４は、１用語問合せのみ、２用語問合せのみ、３用語問合せのみ、或いはおそらく４つ以上の用語を有する問合せを含む問合せ形式の任意の組合せを含んでもよい。
【００１７】
一実施形態では、複数のテスト問合せ２０４は、サーチエンジンへユーザが提示した問合せ１１２をサーチエンジン１０６により記憶した１つ以上のログから問合せをサンプリングすることにより決定される。問合せストリングの予備的セットが最初にログからサンプリングされる。次いで、ユーザベースの知識範囲外であると決定された要旨に関する問合せが排除される。最終的に、その予備的セット内の残りの問合せが、複数のテスト問合せ２０４に指定される。
【００１８】
別の実施形態では、複数のテスト問合せは、１ワードエントリーの語彙集からワードをサンプリングし、そしてこのようにサンプリングされた各ワードを複数のテスト問合せに指定することにより、選択される。ワードをサンプリングできる語彙集は、例えば、Ｍｅｒｒｉａｍ−Ｗｅｂｓｔｅｒ’ｓ  Ｃｏｌｌｅｇｉａｔｅ  Ｄｉｃｔｉｏｎａｒｙ、メリアン−ウェブスター・インク、第１０版（１９９８年）のような辞書を含む。更に別の実施形態では、２つ以上のワードの組合せが語彙集からサンプリングされ、そしてそれらの組合せが複数のテスト問合せ２０４に指定される。
【００１９】
複数のテスト問合せ２０４が決定されると、データベースからのドキュメントの各結果セット３０４が複数個収集される（２０８）。ある実施形態では、複数のテスト問合せ２０４における各テスト問合せ１１２がサーチエンジン１０６に提示される。上述したように、ある実施形態では、データベースが、ワールドワイドウェブから検索されたドキュメントのインデックスである。これらの実施形態では、ドキュメントの結果セットは、時には、各テスト問合せをサーチエンジンに提示し、テスト問合せ内の１つ以上の用語を含むワールドワイドウェブのドキュメントのリストをサーチエンジンから受け取り、そしてそのドキュメントリストにおける１つ以上のドキュメントを各結果セットに追加することにより、収集される。サーチエンジンは、それに応答して、ドキュメント（通常、ＵＲＬにより参照される）のリストを返送し、各ドキュメントは、テスト問合せ１１２における用語の少なくとも１つを含む。このようにして、各々の結果セット３０４は、１つ以上のドキュメント２１０を含み、そして各ドキュメント２１０は、１つ以上のテスト問合せ１１２に関連付けられる。各々の結果セット３０４は、ドキュメントの完全なコンテンツではなく、ドキュメント２１０に対する識別情報（例えば、各ドキュメントのＵＲＬ、ドキュメントのタイトル又は部分タイトル、及び１つ以上の問合せ用語を含んでもよいドキュメントの小さな部分）のみを記憶するのが好ましい。
【００２０】
他の実施形態では、各テスト問合せ１１２の各結果セット３０４は、複数のテスト問合せ２０４からの各問合せ１１２を、ワールドワイドウェブのドキュメントをインデックスする２つ以上のサーチエンジンへ提示することにより収集される。例えば、ある実施形態では、テスト問合せが、ＡｌｔａＶｉｓｔａのサーチエンジン（ＵＲＬｈｔｔｐ：／／ｗｗｗ．ａｖ．ｃｏｍにおける）及び第２のサーチエンジンの両方に提示される。ある実施形態では、第２のサーチエンジンがＧｏｏｇｌｅのサーチエンジン（ＵＲＬｈｔｔｐ：／／ｗｗｗ．ｇｏｏｇｌｅ．ｃｏｍにおける）である。次いで、各サーチエンジンにより決定される２００個の最高ランクドキュメント（ランキング１−２００を有する）のＵＲＬが受け取られる。次いで、ＡｌｔａＶｉｓｔａのサーチエンジンにより位置１−５にランク付けされた５つのドキュメント（提示された問合せに対して最高の関連性に対応する）が各結果セットに追加される。更に、ランキングにおいて位置６−２００の中からランダムに選択された位置を有する５つのドキュメントが選択され、これらのドキュメントが各結果セットに追加される。次いで、第２のサーチエンジンにより位置１−５にランク付けされた５つのドキュメントが各結果セット２０８に追加される。更に、第２のサーチエンジンにより５つのランダムに選択された位置にランク付けされたドキュメントが各結果セットに追加される。第２のサーチエンジンにより返送されるＵＲＬのリストにおける各ドキュメントに対して、各結果セットが、第２のサーチエンジンにより返送されるＵＲＬのリストからドキュメントを追加する前に既にドキュメントを含む場合には、次に最も高い位置（現在位置の値に１をプラスしたものに等しいランクを有する位置）におけるドキュメントが検査され、そしてそれが各結果セットにまだない場合には、各結果セットに追加される。逆に、ドキュメントが各結果セットに既に見つかった場合には、ドキュメントのリストの終わりに到達するまで、次に最も高い位置のドキュメントが検査される。これは、もし可能であれば、第２のサーチエンジンにより返送されたＵＲＬのリストからの１０個のドキュメントが各結果セットに追加されるまで繰り返される。従って、ある実施形態では、各結果セットは、可能であれば、２０個のドキュメントを含む。
【００２１】
データベースからのドキュメントの結果セットを収集できる方法について述べたが、結果セットから又は１つ以上の各結果セットからドキュメントのサブセットを選択する方法について説明する。本明細書全体を通して、おそらくセットにおける全アイテムを含むセットの一部分を示すのに「サブセット」という述語を使用する。通常、複数の各結果セット３０４（２０８）におけるドキュメントの数が多く、これら全てのドキュメントに正確なトレーニング関連性スコアを経済的に指定するのを妨げる。更に、ある実施形態では、計算リソース（図１の関連性ファンクション決定システム１０８に対するメモリの量及び処理速度）に限度があるために、ドキュメントランク付けファンクションの決定は、比較的少数のドキュメントにトレーニング関連性スコアが指定された場合しか実施できない。この点について、比較的少数とは、全体の１％以下を意味する。例えば、好ましい実施形態では、複数の各結果セット３０４（２０８）は、４０００個以上のドキュメントを含むが、トレーニング関連性スコアが指定されるドキュメントの選択されたサブセットは、４０個のドキュメントしか含まない。別の実施形態では、トレーニング関連性スコアは、４０から２００の範囲の多数のドキュメントに指定される。
【００２２】
図３を参照すれば、１つ以上の各結果セット３０４の各々は、複数のテスト問合せの各々を参照して検索されるドキュメントを含む。ある実施形態では、各ドキュメントを、そのドキュメントを含む各結果セットの問合せに関連付ける代用関連性スコアが最初に決定される。この代用関連性スコアは、各結果セットの問合せをサーチエンジンに提示し、そしてサーチエンジンにより返送されるリストにおけるドキュメントの位置の関数としてドキュメントの代用関連性スコアを決定することにより、決定できる。例えば、図３の問合せ１がサーチエンジンに提示され、そして問合せ１の提示に応答してサーチエンジンにより与えられるリストにおけるドキュメント３０６−１の位置の関数としてドキュメント３０６−１に代用関連性スコアが指定される。
【００２３】
次いで、各々の結果セット３０４に対し、関連性ティア(tier)のセット３０８が確立される。関連性ティアの各セット３０８は、１つ以上の関連性ティア３１０を含む。ある実施形態では、各関連性ティア３１０には、最小の代用関連性スコア、及び任意であるが、最大の代用関連性スコアが関連付けされる。ある実施形態では、各結果セット３０４内の１つ以上のドキュメントは、そのドキュメントの代用関連性スコアが、関連性ティアに関連付けられた最小の代用関連性スコア以上となるように、各関連性ティア３１０に指定される。各結果セット３０４における１つ以上のドキュメントは、多数のやり方で選択することができ、例えば、各結果セット３０４内のドキュメントの中からランダムにサンプリングすることにより選択することができる。ドキュメントを指定する一例が、１０の代用関連性スコアを有するドキュメント３０６−１により示されている。関連性ティア３１０−１１に関連付けられた最小代用関連性スコアは、８でよい。従って、ドキュメント３０６−１は、ティア３１０−１１に指定される。各結果セット３０４からドキュメントを選択して関連性ティア３１０に指定する他の方法も考えられる。関連性ティアは、通常、低い代用関連性スコアをもつ結果を表わすドキュメントを含む。
【００２４】
ある実施形態では、各関連性ティア３１０は、更に、それに関連した最大の代用関連性スコアを有する。例えば、ティア３１０−Ｎ２は、それに関連した最小関連性スコアが４でよく、そしてそれに関連した最大関連性スコアが８でよい。関連性ティア３１０−Ｎ１は、それに関連した最大関連性スコアが１００でよく、そしてそれに関連した最小関連性スコアが８でよい。これらの実施形態では、ドキュメントの代用関連性スコアが、ティアに関連した最大代用関連性スコア未満であり且つティアに関連した最小代用関連性スコア以上である場合には、ドキュメントが所与の関連性ティアに指定される。例えば、ドキュメント３０６−２は、代用関連性スコアが５でよい。従って、ドキュメント３０６−２は、関連性ティア３１０−Ｎ２には指定されるが、関連性ティア３１０−Ｎ１には指定されない。これら実施形態の幾つかにおいて、各ティアの最大及び最小スコアに関連した関連性スコアの範囲は、それらの範囲が重畳しないように選択される。別の実施形態では、例えば、各ティアが指定の最小スコアを有するが、指定の最大スコアはもたない状態で、範囲が重畳する。
【００２５】
ある実施形態では、各結果セット３０４から関連性ティア３１０へドキュメントを指定するプロセスは、各関連性ティア３１０が少なくとも各所定数のドキュメントを含むまで繰り返される。例えば、ある実施形態では、指定を行うプロセスは、少なくとも１０個のドキュメントが各関連性ティアに指定されるまで繰り返される。別の実施形態では、各ティアに必要とされるドキュメントの最小数が異なってもよい。例えば、ティア１、２及び３に必要とされるドキュメントの最小数は、各々、１０、４０及び１００でよい。
【００２６】
ドキュメントのサブセットを選択する方法について説明したが、サブセット内のドキュメントにトレーニング関連性スコアを指定するための方法を説明する。ある実施形態では、関連性ティア３１０からの第１の複数のドキュメントが１つ以上のヒューマンサブジェクト（図１の要素１１０）に提示される。例えば、第１の複数のドキュメントは、複数のテスト問合せにおける各問合せに関連した第１の（即ち最も高い）関連性ティア３１０−１１、・・・３１０−Ｎ１からのドキュメントだけを含む。ヒューマンサブジェクトは、それらに提示された各ドキュメントを、関連する問合せと共に検査し、そしてドキュメントを問合せに関連付ける個々の関連性スコアを決定する。ある実施形態では、非常に多数（例えば、５０個）のヒューマンサブジェクトを使用して、各ドキュメントが評価され、個々の関連性スコアの統計学的に信頼性のあるセットが与えられる。
【００２７】
ある実施形態では、各ヒューマンサブジェクトは、多数のドキュメント−問合せの対と、次のステートメントを含む調査形態と共に与えられる。
−あなたは、お気に入りのサーチサイトにいることを想像する。あなたは、＜問合せに関連したコンテクスト＞であるので、＜問合せ＞をサーチする。例えば、あなたは、天の川の中の惑星の名前を見つけたいので、「天の川の中の惑星」をサーチする。
−あなたのお気に入りのサーチサイトにより配送される多数の問合せ結果の中には、次のＵＲＬ：＜ドキュメントのＵＲＬ＞がある。ＵＲＬをクリックし、そこに存在するドキュメントを読み取り、そしてそのドキュメントを評価した後に、数字１、２、３、４、５、６、７、８、９＆１０の中からスコアをそれに指定することによりそれが問合せにどれほど関連しているが指示する。数字１０を使用して、考えられる最も高い関連性を指示し、そして数字１を使用して、考えられる最も低い関連性を指示する。
【００２８】
従って、これらの実施形態では、ヒューマンサブジェクトは、数字１−１０の１つから個々の関連性スコアを指定し、１０は、最も高い関連性を指示し、そして１は、最も低い関連性を指示する。ある実施形態では、個々のスコアの演算平均が決定され、そしてこの平均は、ドキュメントのトレーニング関連性スコアとして使用される。ドキュメントのトレーニング関連性スコアを決定する他の方法も考えられ、これは、個々の関連性スコアの中間値を使用すると共に、所定スレッシュホールドより低いバリアンスをもつように選択された個々の関連性スコアのサンプルの演算平均を使用することを含むが、これらに限定されない。
【００２９】
ある実施形態では、トレーニングスコアは、サブセット内のドキュメントから選択された第２の複数のドキュメント内のドキュメントに指定される。第２の複数のドキュメントは、第１の複数のドキュメントの一部分として人間のユーザに提示されなかったサブセット内の全てのドキュメントを含んでもよい。ある実施形態では、第２のサブセット内のドキュメントには、所定の低い関連性トレーニングスコアが指定される。例えば、最も低い各関連性ティア３１０−Ｍ１、３１０−Ｍ２（図示されていない第２の問合せに対する）、・・・３１０−ＭＮからのドキュメントには、０の所定関連性スコアが指定されてもよい。ある実施形態では、各問合せに対する次に最も低い各関連性ティアからのドキュメントには、１．５の所定関連性スコアが指定されてもよく、そして第２サブセットにおけるドキュメントを有する他のティアについても同様である。このように、関連性ティア３１０における全てのドキュメントには、全ドキュメントをヒューマンサブジェクトに提示せずに、トレーニング関連性スコアを指定することができる。関連性ティア３１０内の全ドキュメントに対してヒューマンサブジェクトから個々の関連性スコアを得るには、禁止的に経費がかかることになり得る。更に、ヒューマンサブジェクトによりドキュメントに指定された低い個々の関連性スコアからは、通常、あまり情報が得られない。
【００３０】
トレーニング関連性スコアをドキュメントに指定する方法について上述したが、ドキュメントのサブセット、指定されたトレーニング関連性スコア、及び複数のテスト問合せに基づいて関連性ファンクションを決定する方法を説明する。ある実施形態では、マシン学習技術がこの目的で使用される。マシン学習技術は、関連性ファンクションにより発生されたトレーニング関連性スコア及び関連性スコアに関連するエラーを最小にするのに加えて、関連性ファンクションを決定し、新たな問合せ（問合せのテストセットに含まれない）又は新たなドキュメント（関連性ティアにない）に対する関連性スコアが、ドキュメントが関連性ティアにあり且つ問合せがテストセットにあるときに、問合せに対しドキュメントについて決定されたトレーニング関連性スコアに近いものとなるようにする。ある実施形態では、論理的回帰が、関連性ファンクションを決定するためのマシン学習技術として使用される。論理的回帰は、情報検索の状況における関連性ランキングを改善するために回顧的実験により立証されている。例えば、参考としてここに援用するグレー、Ｆ．Ｃの「Inferring the Probability of Relevance Using the Method of Logistic Regression」、ＳＩＧＩＲ１９９４：２２２−２３１を参照されたい。
【００３１】
図４を参照すれば、関連性ファンクションを決定する方法４００において、ステップ４０２では、予想変数として使用されるべき特徴のセットが先ず決定される。これら特徴のセットは、関連性ファンクションの構成において予想変数として使用されるべきである。特徴とは、本明細書及び特許請求の範囲での意味としては、ドキュメントに対する問合せの関係の見地、又はドキュメント自体の見地を定量化する手段である。ドキュメント及びおそらく問合せが与えられると、特徴は、値を返送する。ドキュメント自体のコンテンツのみに基づいて値を返送する特徴は、問合せ独立の特徴と称される。問合せ独立の特徴は、ドキュメント自体のプロパティに依存してもよい。更に、問合せ独立の特徴は、ドキュメントが位置するサーバーのプロパティ、及びおそらくは、このサーバーとウェブ上の他のサーバーとの関係のプロパティに依存してもよい。１つ以上の値を返送するのにドキュメント及び問合せの両方を必要とする特徴は、問合せ従属の特徴と称される。本明細書全体にわたり、ドキュメントを問合せに関連付けるために選択されるｉ番目の特徴は、ｚiで表わす。１つ以上の個々の特徴と含む、選択された特徴のセットは、表示の便宜上、ｚで表わし、ｚ＝｛ｚ1、ｚ2、・・・ｚF｝、そしてＦは、このように選択された特徴の数である。
【００３２】
特徴のセットに含ませることのできる問合せ独立の特徴は、例えば、次のものを含むが、これらに限定されない。
−Ｅｉｇｅｎｒａｎｋ（ＥＲ）：ウェブの入射マトリクスから導出された確率論的マトリクスの固有ベクトルのエレメントに関連した１つ以上の値であり、この場合、リンクが有向グラフのエッジと考えられる。参考としてここに援用するページＬ、ブリンＳ、モトワニＲ、及びウイノグラッドＴ著の「The PageRank citation ranking: Bringing order to the Web」を参照されたい。２００３年４月１０日に最後にアクセスしたウェブサイト、http://citeseer.nj.nec.com/page98pagerank.html
−ＨＵＢ：ウェブの入射マトリクスの接続性に関する値、特に、グラフに対する単一値分解のいわゆるクレインベルグ応用。参考としてここに援用する、Proceedings of the Nineth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998におけるクレインベルグＬ著の「Authoritative sources in a hyperlinked environment」を参照されたい。
−ＵＲＬ深さ：ドキュメントを検索するのに必要なウェブサイトの横断深さを表わす値で、ＵＲＬにおける「／」の数に少なくとも一部分基づいて決定された値。
−クオリティスコア：ドキュメントの権限を表わす値で、ドキュメントの他の特徴の関数として決定された値。
−スパムインデックス：ドキュメントがおそらく「スパムドキュメント」であるかどうか指示する値で、例えば、ドキュメントが用語の過剰な繰り返しを含み、ドキュメントが、用語を含む問合せに対して関連性を人為的に向上させるように設計されていることを指示するときには「１」の値。
−家族の馴染み易さ：ドキュメントが、おそらく家族向けユーザに反対されそうなことが分かるコンテンツを含むかどうか指示するのに使用される値で、例えば、ドキュメントが幾つかのポルノ的用語のリストの１つ以上を含むときには「１」の値であり、さもなければ、「０」の値である。
−ドキュメント長さ：ドキュメントにおける個々の用語の数を整数として表わしたもの。
【００３３】
特徴のセットに含まれることのある問合せ従属の特徴は、例えば、次のものを含むが、これらに限定されない。
−アンカーテキストスコア：現在ドキュメントへのリンク及び現在問合せ内の１つ以上の用語の両方を含むドキュメントの数を表わす値。
−一致位置：ドキュメント内において、問合せからの用語がドキュメントのタイトル又は本体に見つかるかどうか指示する値で、用語が本体には見つかるがタイトルには見つからない場合には、本体のどれほど深部で用語が見つかるか指示する値。
−一致頻度：問合せからの用語がドキュメントにどれほど多く見つかるか指示する値で、例えば、問合せからの用語がドキュメントに見つかる回数。
−用語の重み：情報検索（ＩＲ）の分野における標準的特徴で、例えば、問合せからの用語がドキュメントのデータベース内で見つかる回数の対数の逆数を、全データベースサイズの分数として表わしたもの。
−接近性：多用語問合せの場合に、問合せ内の用語がドキュメント内で互いに隣接して見つかるかどうか指示する値。
【００３４】
ある実施形態では、選択された特徴のセットは、上述した特徴の全部を含む。従って、これらの実施形態では、ｚ＝｛Ｅｉｇｅｎｒａｎｋ（ＥＲ）、Ｈｕｂ、ＵＲＬ深さ、クオリティスコア、スパムインデックス、家族の馴染み易さ、ドキュメント長さ、アンカーテキストスコア、一致位置、一致頻度、用語の重み、及び接近性｝である。他の実施形態では、これら特徴のサブセットを選択することができる。更に別の実施形態では、上述したものに加えて特徴のセットに特徴を含ませることができ、例えば、それ自体上記特徴のサブセットの関数である派生特徴を含ませることができる。
【００３５】
再び、図４を参照すれば、ドキュメント関連性ファンクションを決定する方法４００における次のステップは、ステップ４０４である。このステップ４０４において、関連性ファンクションは、係数及びベースファンクションの限定セットに関してパラメータ化される。ある実施形態では、ランク付けファンクションが特徴の一次関数としてパラメータ化される。
2006524869.tif 000003
但し、Ｒは、係数の数で、決定されると、関連性ファンクションｐ(ｚ)をＲ特徴ｚに関して定義するものである。他の実施形態では、関連性ファンクションのパラメータ化は、特徴のより多くの複素数関数を含み、例えば、次のようになる。
2006524869.tif 000004
但し、各ベースファンクションａr（ｚ）は、おそらく特徴のセットを全て含む特徴のセットのサブセットを入力として受け取り、そして値を出力する。ベースファンクションは、特徴のセットの幾つかの二次関数を含んでもよく、例えば、ａ1（ｚ）＝ｚ1ｚ3、ａ2（ｚ）＝ｚ22、又はａ3（ｚ）＝ｚ2ｚ3を含んでもよい。又、これらの関数は、特徴のセットのあるものの、より一般的な非一次関数、例えば、ａ4（ｚ）＝√ｚ1、ａ5（ｚ）＝｜ｚ2｜、又はａ6（ｚ）＝ｚ3／ｚ1を含んでもよい。
【００３６】
ある実施形態では、ベースファンクションそれ自身は、係数によりパラメータ化される。例えば、ベースファンクションは、ウェーブレット関数を含み、各ウェーブレット関数は、膨張、並進移動又は他の考えられるプロセスによりマザーウェーブレットに関連付けられ、その正確な関係は、付加的な係数により決定される。ある実施形態では、ベースファンクションは、神経ネットワークを含んでもよい。ベースファンクションそれ自体が係数に依存するような実施形態では、関連性ファンクションは、次のようにパラメータ化される。
2006524869.tif 000005
但し、各ベースファンクションａrに関連した係数Ｊrの数は、ベースファンクションごとに異なってもよい。ある実施形態では、関連性ファンクションが、係数及びベースファンクションの一般的な非一次関数となる。
2006524869.tif 000006
【００３７】
ある実施形態では、ベースファンクションは判断ツリーを含む。例えば、ベース学習装置は、図５に示すように、２進分類ツリー５００でよい。図５を参照すれば、２進分類ツリーは、ブロック５０２−１において、第１の「スプリット変数」ｘ1を検査し、その値を「スプリット位置」ｂ1と比較する。例えば、スプリット変数は、特徴の１つの値に等しい、ｘ1＝ｚ1。別の例では、スプリット変数は、選択された特徴のセットにおける１つ以上の特徴の一次又は非一次関数である。ブロック５０２−１において実行される比較の結果に基づいて、ツリーの流れは、ブロック５０２−２又はブロック５０２−３のいずれかに進む。各ブロック５０２には、スプリット変数及びスプリット位置が関連される。従って、スプリット変数（例えば、５０８−１）及びスプリット位置（例えば、５０８−２）は、ツリー４００で表わされるベースファンクションを決定するのに必要な係数５０８である。
【００３８】
最終的に、ブロック５０２で行われた比較に基づいて、ツリーの流れは、４つの終端ノード５０６の１つに進む。各終端ノードにおいて、終端値（例えば、５０８−３）がベースファンクションの値として指定される。図５において、ツリー４００は、２進クラシファイヤであり、終端値は、ツリー４００がドキュメントを分類する２つのクラスの一方に対応して「−１」又は「１」の値のみをとる。又、終端値（例えば、５０８−３）は、ツリー４００で表わされるベースファンクションを決定するのに必要な係数５０８でもある。
【００３９】
更に別の実施形態では、ベースファンクションは、分類及び回帰（ＣＡＲＴ）ツリーを含む。ＣＡＲＴツリーは、関連性ファンクションそれ自体をパラメータ化するのに使用されてもよいし、或いはパラメータのサブセットに対する関連性ファンクションの勾配をパラメータ化するのに使用されてもよい。エラーを最小にするようにＣＡＲＴツリーのパラメータを選択する方法を含むＣＡＲＴの完全な説明については、参考としてここに援用する、Ｌ．ブレーマン、Ｊ．Ｈ．フリードマン、Ｒ．Ａ．オルシェン、及びＣ．Ｊ．ストーン著の「Classification and Regression Tree」、カリフォルニア州ベルモント：ワズワース、１９８４年、を参照されたい。
【００４０】
ベースファンクションが２進分類ツリーである実施形態では、関連性ファンクションは、選択された特徴のセットに各ベースファンクションを適用することから返送される終端値の線形結合の関数として決定される。これらの実施形態において、関連性ファンクションを決定するために、マスタークラシファイヤが最初に構成される。このマスタークラシファイヤは、ベースファンクションの線形結合の結果の「投票(vote)」として表現することができる。
2006524869.tif 000007
但し、各ベースファンクション（ツリー）は、ａrと示され、ベースファンクションのパラメータ（スプリット変数、スプリット位置、及び終端値）は、ｄ1、．．．ｄJrと示され、ベースファンクションの結合のパラメータは、ｃrと示され、そしてｓｉｎ（．）関数は、引数が正又はゼロであるときにマスタークラシファイヤに「１」の値を指定し、さもなければ、「−１」の値を指定することにより「投票」する。これらの実施形態では、関連性ファンクションは、ベースファンクションの重み付けされた和の逆論理変換である。
2006524869.tif 000008
但し、
2006524869.tif 000009
そしてｅｘｐ(．)は、指数関数を表わす。表示ｙ＝１は、特徴が与えられると、確率は、値「１」に関連したクラスにドキュメントが属する見込みを測定することを指示する。ステップ４０６に関連して以下に述べるように、これらの実施形態では、値「１」に関連したクラスは、問合せに対して高い関連性があると考えられるドキュメントのクラスである。従って、この確率の値は、それ自体、問合せに対するドキュメントの関連性の推定値として使用される。
【００４１】
関連性ファンクションを決定する方法４００（図４）における次のステップ４０６を詳細に説明する前に、決定された関連性ファンクションと、トレーニング関連性スコアとの間の関係について更に述べる。図３を参照すれば、関連性ティア３１０は、１つ以上のドキュメントを含み、各ドキュメントには、それが発生したところの各結果セット３０４に関連した問合せにそれを関係付けるトレーニング関連性スコアが指定される。表示の便宜上、ｎ番目の問合せに関連したｍ番目の関連性ティアにおけるｊ番目のドキュメントのトレーニング関連性スコアは、ｙnmjと示される。又、特徴の値は、おそらく、問合せ及びドキュメントに依存し、従って、ｎ番目の問合せに関連したｍ番目の関連性ティアにおけるｊ番目のドキュメントに関連した特徴の値も、同様に、ｚnmjと示される。ここに開示するようなマシン学習技術は、トレーニング関連性スコアに関連した部分エラー及び関連性ティアにおける特徴の値に基づいてドキュメント関連性ファンクションを決定する。関連性ティアにおけるドキュメントは、例えば、問合せのテストセットにない問合せに対してウェブからのドキュメントを特徴付けるために関連性ファンクションを使用するときに遭遇するドキュメントの僅かな（一般的に１％未満）部分を表わす。従って、マシン学習技術は、「一般化エラー」、即ち関連性ファンクションにより発生される関連性スコアと、問合せのテストセットにない問合せ或いは関連性ティアにないドキュメントに対してユーザが決定する関連性スコアとに関連したエラー、を制御するように試みなければならない。
【００４２】
ある実施形態では、方法４００のステップ４０６は、ｍ番目の関連性ティアにおけるｊ番目のドキュメント及びｎ番目の問合せに関連した部分エラーｅnmjを、ドキュメント及び問合せに対するトレーニング関連性スコアと、関連性ファンクションにより発生された値との間の差の２乗の関数として定義することを含む。
ｅnmj＝（ｙnmj−ｐ（ｚnmj））2
他の実施形態では、このエラーは、トレーニング関連性スコアと、関連性ファンクションにより発生された値との間の差の絶対値の関数として定義される。
ｅnmj＝｜ｙnmj−ｐ（ｚnmj）｜
【００４３】
更に別の実施形態では、トレーニング分類ファンクションが最初に定義され、この分類ファンクションは、ドキュメントのトレーニング関連性スコアに少なくとも一部分基づいて多数のクラスの少なくとも１つにドキュメントを指定する。例えば、図３を再び参照すれば、トレーニング分類ファンクションは、各テスト問合せに関連した最も高い関連性ティア３１０−１１、・・・及び３１０−Ｎ１からの全てのドキュメントが第１クラスに指定されるように定義されてもよい。このクラスのメンバーは、値「１」に関連付けることができる。この第１クラスのメンバーとして分類されない関連性ティア３１０のドキュメントは、第２クラスに指定されてもよい。第２クラスのメンバーは、値「−１」に関連付けることができる。ある実施形態では、３つ以上のクラスを同様に定義することができる。
【００４４】
トレーニング分類ファンクションが２進クラシファイヤで、２つのクラスの一方にドキュメントを指定するような実施形態では、部分エラーが次のように定義される。
2006524869.tif 000010
但し、
2006524869.tif 000011
2006524869.tif 000012
【００４５】
図４を参照すれば、関連性ファンクションを決定するための方法４００は、部分エラーを定義するステップ４０６を１回以上繰り返す。ステップ４０８は、より多くの部分エラーを決定すべきかどうか決定する。ある実施形態では、各々の問合せに対して各々の関連性ティア（図３の３１０）における各ドキュメントについて部分エラーが定義されるまで、ステップ４０６により部分エラーが繰り返し定義される。次いで、方法４００のステップ４１０は、全エラーを最小にするように関連性ファンクションの係数を選択する。ある実施形態では、全エラーは、複数のテスト問合せにおける各問合せに関連した各関連性ティア内の全ドキュメントに対する部分エラーの単なる和である。
2006524869.tif 000013
他の実施形態では、全エラーは、部分エラーのより複雑な関数でもよく、例えば、部分エラーの重み付けされた和、又は部分エラーの２乗の和でもよい。
【００４６】
関連性ファンクションのパラメータ化については、関連性ファンクションのパラメータ（例えば、係数）が、全エラーを最小にするように決定される。ある実施形態では、全エラーを最小にするパラメータの選択は、ブースト手順を介して行われてもよい。例えば、ブースト手順の１つのバージョン、ＡｄａＢｏｏｓｔ（その擬似コードは、参考としてここに援用する、MSRI Workshop on Nonlinear Estimation and Classification, 2002におけるシャピアＲ．Ｅの「The Boosting Approach to Machine Learning: An Overview」から入手できる）を使用して、部分エラーの重み付けされた和として全エラーを決定するのに適用される一連の重みセットを決定することができる。重みの各セットに対する関連性ファンクションのパラメータは、重みのそのセットで決定される全エラーを最小にするように決定される。例えば、前記のシャピアを参照されたい。別の例として、勾配ブースティングアルゴリズムＧｒａｄｉｅｎｔＢｏｏｓｔの実施を使用して、全エラーを最小にする関連性ファンクションのパラメータを選択することができる。例えば、参考としてここに援用する、２００１年１０月、The Annals of Statistics 29(5)に掲載されたフリードマンＪ．Ｈの「Greedy Function Approximation: A Gradient Boosting Machine」を参照されたい。ＧｒａｄｉｅｎｔＢｏｏｓｔは、ベースファンクションが分類及び回帰（ＣＡＲＴ）ツリーであるときに、この目的で使用するのに特に魅力的な技術である。エラーを最小にするためにＣＡＲＴツリーのパラメータを選択する方法を含むＣＡＲＴツリーの完全な説明については、参考としてここに援用する、Ｌ．ブレーマン、Ｊ．Ｈ．フリードマン、Ｒ．Ａ．オルシェン、及びＣ．Ｊ．ストーン著の「Classification and Regression Tree」、カリフォルニア州ベルモント：ワズワース、１９８４年、を参照されたい。全エラーを最小にするように関連性ファンクションの係数を決定する他の方法も考えられ、これは、ファンクションの一般化エラーを、そのファンクションに対する入力及び出力のサンプルに基づいて最小にするよう求めるアルゴリズムを含む。
【００４７】
関連性ファンクションが決定されると、ある実施形態では、それを使用して、ランク付けファンクションが更に決定される。第１に、ユーザは、サーチエンジンに問合せを提示する。次いで、問合せに対する関連性についてランク付けされるべきドキュメントのセットがデータベースから検索される。ある実施形態では、問合せに１つ以上の用語を含むドキュメントだけがこのセットに含まれる。他の実施形態では、他の基準を使用して、このセットを選択してもよい。次いで、各ドキュメントに対して、選択された特徴セットの値が、問合せと対にされたドキュメントに対して評価される。次いで、関連性ファンクションを使用して、問合せと対にされたドキュメントに対する関連値が決定される。セット内の各ドキュメントに対して関連値が決定されると、ドキュメントのセットの順序付けされたリストが形成される。この順序付けされたリストは、リストのドキュメントが一連の減少する関連性で順序付けされるように決定される。従って、順序付けされたリストに最初に現われるドキュメントは、そのセットの全ドキュメントの中で数値的に最大の関連値を有し、そして順序付けされたリストに最後に現われるドキュメントは、そのセットの全ドキュメントの中で数値的に最小の関連性スコアを有する。このようにリストを順序付けする方法は、データ構造の分野で良く知られている。
【００４８】
本発明は、コンピュータ読み取り可能な記憶媒体に埋め込まれるコンピュータプログラムメカニズムを備えたコンピュータプログラム製品として実施することができる。図６を参照すれば、ある実施形態において、関連性ファンクション決定システム（図１の１０８）は、次のものを備えている。
−１つ以上の中央処理ユニット６０４；
−ネットワーク上の他のコンピュータ（例えば、図１に示すサーチエンジン１０６）と通信するためのネットワークインターフェイス６０６；
−中央処理ユニット６０４により実行するための１つ以上のデータ構造体及び１つ以上のモジュールを記憶するコンピュータ読み取り可能な媒体で構成された一次及び二次記憶装置６１０；及び
−中央処理ユニット６０４、ネットワークインターフェイス６０６、並びに一次及び二次記憶媒体６０８の中で電子信号を送信及び受信するための内部バス６０８。
【００４９】
記憶装置６１０のプログラムモジュールは、ＣＤ−ＲＯＭ、磁気ディスク記憶製品、或いは他のコンピュータ読み取り可能なデータ又はプログラム記憶製品に記憶することができる。又、コンピュータプログラム製品のソフトウェアモジュールは、電子的に、インターネットを経て、或いはさもなければ、搬送波におけるコンピュータデータ信号（ソフトウェアモジュールが埋め込まれた）の送信により、配布されてもよい。記憶装置６１０は、少なくとも次のものを備えてもよい。
−複数のテスト問合せを記憶するためのデータ構造体６１２；及び
−ドキュメントの結果セットを識別するか又は表わすデータを記憶するためのデータ構造体６１４。このデータ構造体６１４のデータは、通常、ドキュメントの結果セットにおけるドキュメントを参照するＵＲＬを含む。
【００５０】
記憶装置６１０は、更に、次のものを備えてもよい。
−複数のテスト問合せの各々に対してデータベースからドキュメントの各結果セットを収集するための収集モジュール６１６であって、通常、同じ又は異なるコンピュータシステムのサーチエンジンモジュールをコールして、ドキュメントの結果セットを発生するような収集モジュール６１６；
−複数のテスト問合せの各テスト問合せに対して各結果セットにおけるドキュメントのサブセットを選択するためのサンプリングモジュール６１８；
−トレーニング関連性スコアのセットを各選択されたサブセットにおけるドキュメントに指定するためのスコア付けモジュール６２０；及び
−複数のテスト問合せ、ドキュメントのサブセット、及びトレーニング関連性スコアのセットに基づいて関連性ファンクションを決定するための関連性ファンクション発生モジュール６２２。
【００５１】
上記で引用した各個々の出版物又は特許或いは特許出願は、あらゆる目的で、その全体をここに援用するものである。
【００５２】
本発明を完全に理解するために、上記説明では、特定の述語が使用された。しかしながら、当業者であれば、本発明を実施するために特定の細部は必要とされないことが明らかであろう。前記実施形態は、本発明の原理及びその実際の応用を最良に説明するために選択されたもので、当業者であれば、本発明及び種々の実施形態を、意図された特定の用途に適するように種々の変更を加えて、最良に利用することができよう。従って、以上の開示は、余すところのないものでもないし、又、本発明を、ここに開示する正確な形態に限定するものでもない。前記教示に鑑み、多数の変更や修正が考えられる。
【００５３】
本発明の範囲は、特許請求の範囲及びその等効物により限定されるものとする。
【図面の簡単な説明】
【００５４】
【図１】関連性ファンクション決定システムにより決定されたドキュメント関連性ファンクションを使用するサーチエンジンに問合せを提示するクライアントコンピュータを示す図である。
【図２Ａ】１つ以上の用語を含む問合せを例示する図である。
【図２Ｂ】問合せのテストセットを示すと共に、問合せのテストセットをサーチエンジンに提示してドキュメントの結果セットを得るところを示す図である。
【図３】ドキュメントの結果セットと、ドキュメントのサブセットをそれに指定するための複数の関連性ティアとを示す図である。
【図４】関連性ファンクション決定方法を示すフローチャートである。
【図５】ベースファンクション、この場合は、２進分類ツリーを例示するブロック図である。
【図６】関連性ファンクション決定システムのブロック図である。
【図１】
2006524869.tif 000014
2006524869.tif 000015
【図２Ｂ】
2006524869.tif 000016
【図３】
2006524869.tif 000017
【図４】
2006524869.tif 000018
【図５】
2006524869.tif 000019
【図６】
2006524869.tif 000020
【国際調査報告】
2006524869.tif 000021