(57)【特許請求の範囲】
【請求項１】
検索クエリに応じてユーザに提示されたドキュメントの結果リスト内のドキュメントを格付けする格付け方法において、
ａ．ユーザクライアントによって、上記ドキュメントの結果リストをユーザに提示するステップと、
ｂ．検索エンジンによって、上記ドキュメントの結果リスト内のドキュメントのユーザに対する関連性に関するユーザからの入力を、受信するとともに、上記検索クエリに関連したユーザによる最新の入力と、該ユーザに対するドキュメントの関連性に関するドキュメントのみを記憶するステップと、
ｃ．上記検索エンジンによって、上記ユーザ入力を上記検索クエリ及び上記ドキュメントに関連させるステップと、
ｄ．機械学習モジュールによって、複数の特徴からなる変数と、該複数の特徴のそれぞれに対応する複数の重み係数からなるパラメータとを有し、上記ドキュメントと上記検索クエリとの関連性スコアを計算する関連式を決定するステップと、
ｅ．上記検索エンジンによって、上記関連性スコアに基づいてドキュメントを格付けするステップとを有し、上記関連性スコアは、上記ドキュメント及び検索クエリに関連したユーザ入力に依存することを特徴とする格付け方法。
【請求項２】
検索クエリに応じて返された検索結果リストを並び替える検索結果並び替え方法において、
ａ．ユーザクライアントによって、上記検索クエリに応じた検索結果リストをユーザに提示するステップと、
ｂ．検索エンジンによって、上記検索結果リスト内の複数の結果のそれぞれのユーザに対する関連性であるユーザからの入力を、受信するとともに、該複数の結果のそれぞれに関連したユーザによる最新の入力と、該検索結果リスト内の複数の結果のそれぞれのユーザに対する関連性に関する検索クエリのみを記憶するステップと、
ｃ．上記検索エンジンによって、上記ユーザ入力をその結果及びドキュメントに関連させるステップと、
ｄ．機械学習モジュールによって、複数の特徴からなる変数と、該複数の特徴のそれぞれに対応した複数の重み係数からなるパラメータとを含み、上記複数の結果毎の関連性スコアを決定する関連式を、該複数の結果毎のユーザ入力を用いて更新するステップと、
ｅ．上記検索エンジンによって、複数の結果を含む検索結果リストを並び替えるステップとを有し、
上記複数の結果は、該複数の結果毎の関連性スコアを用いて格付けされることを特徴とする検索結果並び替え方法。
【請求項３】
第１の検索エンジンによってユーザクライアントのユーザに返される結果を格付けする格付け方法において、
ａ．ウェブサーバによって、検索クエリに応じて、上記第１の検索エンジンによって格付けされたドキュメントを含む第１の結果リストを受信するステップと、
ｂ．上記ウェブサーバによって、上記検索クエリに応じて、第２の検索エンジンによって格付けされたドキュメントを含む第２の結果リストを受信するステップと、
ｃ．ユーザクライアントによって、上記第１の結果リストをユーザに提示するステップと、
ｄ．上記第１の検索エンジンによって、上記第１の結果リスト内のドキュメントのユーザに対する関連性に関するユーザからの入力を、受信するとともに、上記ドキュメントに関連したユーザによる最新の入力と、該ユーザに対するドキュメントの関連性に関する検索クエリのみを記憶するステップと、
ｅ．上記第１の検索エンジンによって、上記ユーザ入力を上記ドキュメント及び上記検索クエリに関連させるステップと、
ｆ．機械学習モジュールによって、複数の特徴をからなる変数と、該複数の特徴のそれぞれに対応する複数の重み係数からなるパラメータとを有し、上記検索クエリに応じて、ドキュメントの関連性スコアを決定する式を決定するステップと、
ｇ．上記第１の検索エンジンによって、上記検索クエリに応じて、各ドキュメント毎の関連性スコアを用いて格付けされた上記第１の結果リスト及び上記第２の結果リスト内のドキュメントを含む第３の結果リストを並び替えるステップとを有し、
上記式は、上記ユーザ入力と、該ユーザ入力の上記ドキュメント及び上記検索クエリとの関連性とを用いて、決定されることを特徴とする格付け方法。
【請求項４】
検索クエリに応じて結果の格付けされたリストを返す格付けシステムにおいて、
ａ．第１の検索クエリに応じて返された複数の結果から結果を格付けする最新のユーザ入力のみを、該複数の結果からの結果を検索クエリに関連させるとともに、ユーザに対する結果の関連性に関するユーザ入力に関連させる記録として、保存する第１のデータベースと、
ｂ．上記第１のデータベースに接続され、複数の特徴からなる変数と、該複数の特徴のそれぞれに対応する複数の重み係数からなるパラメータとを有し、該第１のデータベースに保存され、上記第１の検索クエリに関連されるとともに、該第１の検索クエリに応じて返された複数の結果に関連されたユーザ入力を用いて、第２の検索クエリに応じて返された複数の結果から各結果毎の関連性スコアを計算する関連性モデルとを備え、
上記複数の結果から結果を上記検索クエリに関連させる記録として、上記ユーザによって以前に上記第１のデータベースに保存された入力は、破棄されることを特徴とする格付けシステム。
【請求項５】
検索クエリに応じて返された検索結果リスト内の複数の結果を並び替える検索結果並び替えシステムにおいて、
ａ．複数の結果におけるドキュメントのユーザに対する関連性を示し、最新のユーザ入力のみを記憶し、複数の特徴からなる変数と、該複数の特徴のそれぞれに対応する複数の重み係数からなるパラメータとを有し、ドキュメントと検索クエリに関連させる、ユーザによるユーザ入力を用いて、該ドキュメントと上記検索クエリとの関連性スコアを決定する関連性モデルと、
ｂ．上記関連性モデルに接続され、上記検索クエリを受信し、上記ドキュメントと検索クエリとの関連性スコアに基づいて格付けされた結果を含む検索結果リストを返す検索エンジンと、
ｃ．上記検索エンジン及び上記関連性モデルに接続され、上記ドキュメントと検索クエリとの関連性スコアを決定する関連性モデルによって用いられる特徴のセットを保存するデータベースとを備えることを特徴とする検索結果並び替えシステム。
【発明の詳細な説明】
【関連出願】
【０００１】
本出願は、米国特許法第１１９条（ｅ）項に基づき、２００５年３月１８日に出願された係属中の米国仮特許出願番号第６０／６６３，３６１号、発明の名称「ユーザからのフィードバックを適用して検索結果を向上させる検索エンジン（Search  Engine  that  Applies  Feedback  from  Users  to  Improve  Search  Results）」の優先権を主張する。この文献は、引用によって本願に援用される。
【技術分野】
【０００２】
本発明は、インターネット検索を行う検索アプリケーションに関し、詳しくは、検索アプリケーションを使用するユーザからのフィードバックをインターネット検索を行う検索アプリケーションに適用して検索結果の質を改善するための技術に関する。
【背景技術】
【０００３】
インターネット検索エンジンは、インターネットに含まれている膨大な情報から、望ましいサイトを発見するように設計されている。ユーザは、自らが探している検索タームを含むクエリを入力することによって、情報を記述する。検索エンジンは、ユーザが探している情報に関連する可能性が高いウェブページを特定するために、様々な相関性に関する演算を用いて、ウェブページのインデクスに対して検索タームを照合する。そして、検索エンジンは、これらのウェブページへのハイパーリンクの格付けされたリストを返し、このリストでは、関連性が高いと判定されたリンクが上位に格付けされる。
【０００４】
検索エンジンの目的は、所定のクエリに最も関連性が高いウェブページを発見することである。初期の検索エンジンは、例えば、ドキュメント内におけるタームの存在、密度、検索タームの類義語等、各ページ内に含まれている情報を用いて、ウェブページの関連性を判定していた。より高度な検索エンジンは、関連性を判定する際、ウェブページ間のリンクに関連する情報を考慮する。
【０００５】
インターネットのウェブページの数は膨大であり、増加し続けており、ユーザのクエリを表面上満足させるウェブページが多数あることも多いため、どのウェブページが関連性が高いかを判定する処理は非常に難しい。同じ又は類似するタームが多くの異なる概念を参照することもある。殆どのユーザは、高度に定義されたクエリを作成して、入力することに慣れていないので、ユーザが探している情報の種類は、曖昧となることも多い。
【０００６】
また、検索エンジンによって返される結果を操作することもできる。ウェブサイトのオーナは、コンテンツ又はメタデータ、若しくは他のウェブサイトから自らのウェブサイトへのハイパーリンクを追加することができ、これにより、ウェブページが、ユーザのクエリへの関連性が高い情報を含んでいなくても、これらのウェブページが結果リストの上位に表示されるようにすることができる。この結果、ユーザが探している情報を含まない幾つかのウェブページが結果リストにおいて高く格付けされ、したがって、検索結果の総合的な精度が低下することがある。この手法は、検索エンジン最適化（Search  Engine  Optimization：ＳＥＯ）と呼ばれることも多い。検索エンジンは、ＳＥＯに対して、関連性のレベルを妥当に維持するためだけに、常に努力をし続けなくてはならない。検索エンジンは、どのウェブページがユーザのクエリを満たすか、又は満たさないかを判定し、同じ又は異なるユーザによる後のクエリに対して、より関連性が高い結果を提供するために、ユーザからフィードバックを直接収集することが望ましい。
【０００７】
検索エンジンのオペレータは、時間の経過に伴い、検索エンジンの精度を維持又は改善するために、関連性を判定するために用いられるメソッド及びこれらのメソッドに適用される重みを調整する。通常、この処理は、例えば、異なるクエリについて検索エンジンが提供した結果に対するユーザのスコアを検査するような実験を含む。そして、如何なるメソッドを用いるか及び如何なる重みを適用するかを決定するために、このスコアをコンパイル及び分析することができる。しかしながら、この処理は、時間が掛かり、不正確であり、普遍的ではなく、柔軟性に欠ける。検索エンジンの精度を向上させるためには、実際
のユーザから直接入力された情報を用いるフィードバックメカニズムを用いて、検索関連性メソッド及び重みを調整することが望ましい。
【０００８】
更に、検索タームへの理解がユーザにより異なり、ユーザの嗜好及び関心が異なり、又は検索の「モード」が異なるために、複数のユーザがクエリを入力する場合、各ユーザの意図が異なる場合もある。例えば、３人の異なるユーザがクエリ「ｉＰｏｄ」を入力した場合、第１のユーザは、ｉＰｏｄの購買を意図し、第２のユーザは、ｉＰｏｄに関するニュースの検索を意図し、第３のユーザは、ｉＰｏｄに関する情報又はレビューを検索することを意図していることがある。ユーザは、検索を行う際に、自らの興味及び目的に関してある種の指示を与えることもできる。したがって、どの結果がユーザクエリに関連性が
高いかを判定する際、異なる検索モード及びユーザの興味の違いを考慮できる検索エンジンの開発が望まれる。
【発明の開示】
【課題を解決するための手段】
【０００９】
本発明は、検索クエリに対するドキュメントの関連性を予測し、検索を実行するユーザに対して、より関連性が高い結果を返す方法及びシステムを提供する。好ましい実施の形態では、本発明に基づく格付け方法は、式を用いて検索クエリに対する複数のドキュメントの関連性を予測し、それぞれの関連性に基づいてドキュメントを格付けし、検索クエリに応じて格付けされたリストをユーザに返す。好ましくは、ユーザ入力を用いて、式のパラメータを調整し、返されるドキュメントが検索クエリに関連している可能性を高める。
【００１０】
本発明の第１の実施の形態においては、検索クエリに応じてドキュメントを格付けする格付け方法は、（ａ）ドキュメントと検索クエリとの関連性スコアを算出する変数及びパラメータを有する式を判定するステップと、（ｂ）関連性スコアに基づいてドキュメントを格付けするステップとを有する。格付け方法は、好ましくは、検索クエリに応じて、結果リストを返すステップを更に有する。結果リストは、関連性スコアに基づいて格付けされた結果リスト内のドキュメントへのリンクを含む。
【００１１】
他の実施の形態においては、式を判定するステップは、ユーザ入力に基づいてパラメータを調整するステップを有する。式は、タグ、ドキュメント内のターム、ドキュメント内のタームの位置、ドキュメントの構造、ドキュメントへのリンク、検索結果リスト内のドキュメントの位置、検索結果リストからドキュメントがアクセスされた回数、タームスコア、セクション情報、リンク構造、アンカーテキスト、及び要約からなるグループから選択される１つ以上の特徴から導出してもよい。これに代えて又はこれに加えて、特徴は、ユーザ表現、ユーザ入力の時刻、ブロック、ユーザ識別子、及びドキュメントのユーザ格付けを含んでいてもよい。
【００１２】
一実施の形態においては、式は、ユーザモデル及びグループモデルに対応する。ユーザモデルは、ドキュメントとユーザの検索クエリとの関連性スコアを判定するためのものである。グループモデルは、ドキュメントとユーザグループの検索クエリの関連性スコアを判定するためのものである。格付け方法は、更に、ユーザモデルをグループモデルと比較して、ドキュメントへのバイアスを判定するステップを有していてもよい。
【００１３】
パラメータは、好ましくは、機械学習技術を用いて判定される。機械学習技術は、ロジスティック回帰分析、サポートベクトルマシン、ニューラルネットワーク、ブーストされた決定木（boosted  trees）、ランダムフォレスト（random  forests）、ナイーブベイズ（naive  Bayes）、グラフィックモデル等の統計的分類の形式を含む。他の実施の形態においては、機械学習技術は、共役勾配降下法（conjugate  gradient  descent）を用いる。
【００１４】
他の実施の形態においては、式の１又は複数の変数は、ユーザ入力から生成される。このユーザ入力は、ドキュメントへのタグ付け、ドキュメントの関連性の格付け、ドキュメントのブロック、又はこれらの任意の組合せであってもよい。
【００１５】
一実施の形態においては、関連性スコアは、検索エンジンサイトに登録されたユーザのためのものであり、ドキュメントと検索エンジンサイトに登録されていないユーザの検索クエリとの関連性スコアを判定するために使用される。
【００１６】
本発明の第２の側面である検索結果並び替え方法は、検索結果リストを並び替える検索結果並び替え方法において、（ａ）検索クエリに応じて返された複数の結果のそれぞれの関連性スコアを判定するための変数及びパラメータを含む関連式を更新するステップと、（ｂ）検索クエリに応じて、それぞれの結果が関連性スコアを用いて格付けされた複数の結果を含む検索結果リストを返すステップとを有する。一実施の形態においては、関連式を更新するステップは、パラメータを更新するステップを含む。パラメータは、好ましくは、ドキュメントへのタグ付け、ドキュメントの関連性の格付け、ドキュメントのブロック等  のユーザ入力を用いて更新される。
【００１７】
関連式は、例えば、統計的分類の形式を含む機械学習技術を用いて導出される。統計的分類は、例えば、ロジスティック回帰分析、サポートベクトルマシン、ニューラルネットワーク、ブーストされた決定木、ランダムフォレスト、ナイーブベイズ、グラフィックモデルの何れかである。他の実施の形態においては、機械学習技術は、共役勾配降下法を用いる。
【００１８】
本発明の第３の側面である格付け方法は、第１の検索エンジンによって返された結果を格付けする格付け方法において、検索クエリに応じて、第１の検索エンジンによって格付けされたドキュメントを含む第１の結果リストを受信するステップと、検索クエリに応じて、第２の検索エンジンによって格付けされたドキュメントを含む第２の結果リストを受信するステップと、検索クエリに応じて、ドキュメントの関連性スコアを判定するための変数及びパラメータを含む式を判定するステップと、検索クエリに応じて、各ドキュメントの関連性スコア用いて格付けされた第１の結果リスト及び第２の結果リスト内のドキュ
メントを含む第３の結果リストを返すステップとを有する。この結果、本発明の実施の形態は、１又は複数の検索エンジンによって返された結果を用いて機能できる。式は、好ましくは、ユーザ入力を用いて判定される。
【００１９】
一実施の形態においては、式は、第１の結果リストにおけるドキュメントのランクと、第２の結果リストにおけるドキュメントのランクとを用いて判定される。パラメータは、統計的分類の形式を含む機械学習技術を用いて判定される。他の実施の形態においては、統計的分類は、ロジスティック回帰分析、サポートベクトルマシン、ニューラルネットワーク、ブーストされた決定木、ランダムフォレスト、ナイーブベイズ、グラフィックモデルの何れかである。
【００２０】
本発明の第４の側面である格付けシステムは、検索クエリに応じて結果の格付けされたリストを返す格付けシステムにおいて、関連性モデルに接続された第１のデータベースを備える。第１のデータベースは、第１の検索クエリに応じて、複数の結果から結果を格付けするユーザ入力を保存する。関連性モデルは、複数の特徴からなる変数と、該複数の特徴のそれぞれに対応する複数の重み係数からなるパラメータとを有し、ユーザ入力を用いて、第２の検索クエリの複数の結果から、各結果の関連性スコアを算出する。
【００２１】
一実施の形態においては、格付けシステムは、第１のデータベースに接続された検索エンジンを備える。検索エンジンは、検索クエリを受信し、各結果の関連性スコアに基づいて複数の結果を格付けし、該格付けされた複数の結果を含む検索結果リストを返す。好ましくは、関連性モデルは、ユーザ入力を用いて更新される。他の実施の形態においては、関連性モデルは、統計的分類の形式を含む機械学習技術を用いる。他の実施の形態においては、統計的分類は、ロジスティック回帰分析、サポートベクトルマシン、ニューラルネットワーク、ブーストされた決定木、ランダムフォレスト、ナイーブベイズ、グラフィックモデルの何れかである。他の実施の形態においては、機械学習技術は、共役勾配降下法を用いる。
【００２２】
一実施の形態においては、関連性モデルは、特定のユーザについて、検索クエリとドキュメントとの関連性スコアを判定するための一組のユーザ固有のパラメータを判定する。他の実施の形態においては、関連性モデルは、ユーザのグループの検索クエリとドキュメントとの関連性スコアを判定するためのグループモデルのパラメータを判定する。
【００２３】
一実施の形態においては、格付けシステムは、関連性モデルを更新するための１つ以上の特徴を保存する第２のデータベースを更に備える。特徴は、タグ、ドキュメント内のターム、ドキュメント内のタームの位置、ドキュメントの構造、ドキュメントへのリンク、検索結果リスト内のドキュメントの位置、検索結果リストからドキュメントがアクセスされた回数、タームスコア、セクション情報、リンク構造、アンカーテキスト、要約、ユーザ表現、ユーザ入力の時刻、ブロック、ユーザ識別情報、ドキュメントのユーザ格付けのうちの１つ以上を含む。
【００２４】
本発明の第５の側面である検索結果並び替えシステムは、検索結果リスト内の複数の結果を並び替える検索結果並び替えシステムにおいて、検索エンジンに接続された、関連性モデルと、検索エンジン及び関連性モデルに接続されたデータベースとを備える。関連性モデルは、複数の特徴からなる変数と、該複数の特徴のそれぞれに対応する複数の重み係数からなるパラメータとを有し、ユーザ入力を用いて、ドキュメントと検索クエリとの関連性スコアを判定するために用いられる。検索エンジンは、関連性モデルに接続され、検索クエリを受信し、各ドキュメントと検索クエリとの関連性スコアに基づいて格付けされた結果を含む検索結果リストを返す。データベースは、ドキュメントと検索クエリとの関連性スコアを決定するために関連性モデルによって用いられる一組の特徴を保存する。
【００２５】
一実施の形態においては、データベースは、検索エンジンに接続されたユーザデータベースと、関連性モデルに接続されたユーザ入力データベースとを備える。ユーザデータベースは、ユーザ入力を保存し、ユーザ入力データベースは、特徴のセットを保存する。特徴のセットは、タグ、ドキュメント内のターム、ドキュメント内のタームの位置、ドキュメントの構造、ドキュメントへのリンク、検索結果リスト内のドキュメントの位置、検索結果リストからドキュメントがアクセスされた回数、タームスコア、セクション情報、リンク構造、アンカーテキスト、要約、ユーザ表現、ユーザ入力の時刻、ブロック、ユーザ
識別子、及びドキュメントのユーザ格付けのうちの１つ以上を含む。
【００２６】
検索結果並び替えシステムは、好ましくは、データベースに接続されたウェブサーバと、関連性モデル及び検索エンジンの両方に接続されたドキュメントインデクスとを更に備える。
【００２７】
関連性モデルは、好ましくは、例えば、統計的分類の形式を含む機械学習技術を用いる。代替となる実施の形態においては、統計的分類は、ロジスティック回帰分析、サポート  ベクトルマシン、ニューラルネットワーク、ブーストされた決定木、ランダムフォレスト、ナイーブベイズ、グラフィックモデルの何れかである。他の実施の形態においては、機械学習技術は、共役勾配降下法を用いる。
【発明を実施するための最良の形態】
【００２８】
本発明の実施の形態は、従来の検索エンジンとは異なり、ユーザフィードバックを用いて、インターネットを検索するユーザに、より関連性が高い情報を提供する。例えば、本発明では、検索を実行する第１のユーザは、その検索の結果を格付けできる。第１のユーザは、自らの検索と、その検索の結果との関連性、結果リストで返された特定のウェブページに含まれている情報の豊富さ、又は他の何らかの基準に基づいて結果を格付けできる。同様の又は関連する検索を実行する第２のユーザは、次に、第１のユーザの格付けに基づく又は第１のユーザの格付けに影響を受けた結果リストを見ることができ、したがって、自らの検索に対して関連性が高い検索結果を表示させることができる。また、この第２のユーザも検索結果を格付けできる。このように、ユーザのコミュニティは、探し求める情報に可能な限り関連性が高い検索結果を受信できるようにユーザを補助するフィードバックを提供できる。ユーザフィードバックを用いるシステム及び方法は、２００６年２月２７日に出願された米国特許出願番号未定、代理人整理番号ＭＰＳ−００１０１、発明の名称「ユーザが入力した情報を組み込むことにより検索を行うシステム及び方法（Methods  of  and  Systems  for  Searching  by  Incorporating  User-Entered  Information）」に開示されており、この出願は、引用により本願に援用される。
【００２９】
本発明の他の実施の形態では、検索結果を格付けする手法として、例えば、以下に限定されるものではないが、（１）結果リストのリンクの関連性に関してフィードバックを提供するためのメカニズム、（２）個人的な検索ページ上に表示できるリンクを削減し、又は関連するリンクに投票するためのメカニズム及び（３）検索結果に関係ない又は内容が不快なウェブページへのリンクを「ブロックする」メカニズムが含まれる。他の実施の形態では、関連する検索ターム及びスポンサー付きのリンクへの表示及びリンクを含む。
【００３０】
本発明の他の実施の形態では、検索結果ページは、以下に限定されるわけではないが、（１）検索に関連しているウェブページからのテキスト、（２）クエリタームに関連する異なる概念の記述、（３）提案されたクエリターム（４）他の概念への「ここも参照（see  also）」リンク、（５）スポンサー付きのリンク等を表示するための選択されたアイテムを含む。
【００３１】
以下の説明では、「検索エンジン」という用語は、クエリが入力され、電子文書又はウェブページへのハイパーリンクの結果リストを返す装置（又は汎用コンピュータで実行されるプログラム）を意味する。検索エンジンは、コーパス内のドキュメントのインデクス、各ドキュメントの関連性を決定するコード及びアルゴリズム、及び結果リストをユーザに提供するグラフィカルユーザインタフェースを含む。
【００３２】
また、以下の説明において、「クエリ」という用語は、タイピングされ、発話され、既に一組の検索タームを埋め込んだ「リンク」を介して提供され、又は他の何らかのインタフェースによって、検索エンジンに提供される一組のタームを意味する。クエリは、単一の単語、複数の単語又は語句の何れであってもよい。クエリは、質問を表す語句（例えば、「自然言語」によるクエリ）、スペースで区切られたタームの組、又は構造化されたブール表現の何れであってもよい。実際には、クエリは、検索文字を含み又は検索文字に関連する電子文書又はウェブページを検索するために、検索エンジンで用いられるシンボル
又は他の如何なる文字を含んでいてもよい。
【００３３】
以下の説明では、「ウェブサイト」という用語は、互いにリンクされ、ワールドワイドウェブで閲覧可能なウェブページの集合を意味する。また、「ウェブページ」という用語は、任意の数のホストからワールドワイドウェブを介してアクセス可能な情報を意味し、これらの情報は、以下に限定されるわけではないが、テキスト、ビデオ、画像、音楽及びグラフィクスを含む。
【００３４】
以下の説明において、「結果リスト」という用語は、ハイパーテキストトランスファープロトコル（Hypertext  Transfer  Protocol：ＨＴＴＰ）又は以下に限定されるわけではないが、ドキュメントのタイトル、ドキュメントの要約、ドキュメントのキャッシングされたコピーへのリンク、ドキュメントが最後にインデクスを付され又は最後に更新された日時、ドキュメントに関連し、又はドキュメントに含まれる画像、及びドキュメントから抽出された情報を含む各リンクの他の関連する情報と共に、ウェブページ又は他の電子文書にアクセスするための他の何らかのプロトコルを用いてアクセスできるドキュメント又はウェブページを参照するハイパーリンクのリストを意味する。
【００３５】
また、本明細書において、「ドキュメント」という用語は、広義に定義され、通常の意味に加えて、実際に保存されているか、表示の要求に応じて動的に生成されるかにかかわらず、コンピュータファイル及びウェブページも包含する。「ドキュメント」という用語は、テキストを含むコンピュータファイルに限定されず、グラフィクス、オーディオ、ビデオ及び他のマルチメディアデータを含むコンピュータファイルも包含する。
【００３６】
また、本明細書において、「機械学習」という用語は、ソフトウェアシステムが、ある事象を観測することによって又はある情報を分析することによって、最適な結果を生成するように振る舞いを適応化する処理及びアルゴリズムを示す。
【００３７】
また、本明細書において、「統計モデル」という用語は、一組の入力のスコアを算出する数学的（例えば、数値的又は解析的）式を意味する。このパラメータは、機械学習処理を用いて導出することができる。本発明においては、統計モデルは、ユーザフィードバック検索イベントからの他の情報又はこれらの組合せに基づいていてもよく、様々な数学的手法の何れを用いて生成してもよい。
【００３８】
後に詳細に説明するように、検索エンジンは、ユーザによって入力されたクエリを受信し、ユーザが探している情報に関連する可能性が高いウェブページを特定するために、様々な相関性に関する演算を用いて、ウェブページのインデクスに対して検索タームを照合する。そして、検索エンジンは、これらのウェブページへのハイパーリンクの格付けされたリストを返し、このリストでは、関連性が高いと判定されたリンクが上位に格付けされる。本発明に基づく検索エンジンは、ユーザ入力に基づいて結果リストを返し、ユーザは、例えば、ドキュメント又は結果リストに示されたリンクの順序に影響を与える情報をシステムに入力できる。本発明では、ユーザが関連性が高いと考えるサイトにユーザ自身がタグ付けすることによって、検索結果を格付けでき、この格付けは、ユーザが検索のコンテキスト内にないサイトを閲覧しているときにも行ってもよく、又は第１の検索における検索クエリ以外のタームをタグ付けしてもよい。
【００３９】
後に詳細に説明するように、検索エンジンは、ユーザによって入力されたクエリを受信し、ユーザが探している情報に関連する可能性が高いウェブページを特定するために、様々な相関性に関する演算を用いて、ウェブページのインデクスに対して検索タームを照合する。そして、検索エンジンは、これらのウェブページへのハイパーリンクの格付けされたリストを返し、このリストでは、関連性が高いと判定されたリンクが上位に格付けされる。一般的な検索では、主に検索エンジンが結果リストを返し、ユーザは、システムに情報を入力することはできない。
【００４０】
本発明では、結果リストを含むページをユーザに提供する際、ユーザは、選択的に、ページ上の結果に対してフィードバックを提供することができ、このフィードバックは、フィードバックを解析して、関連性メソッドを調整し、重み付けを行い、後に、同じ又は異なるクエリを入力することによって検索エンジンにアクセスするユーザに提供される結果の関連性を高めるモデルに提供される。
【００４１】
図１は、本発明に基づくクエリに応じて返された結果ページ１００を表示する例示的なグラフィカルユーザインタフェース（graphical  user  interface：ＧＵＩ）を示している。このＧＵＩによって、ユーザは、個々の検索結果を格付けし、個々の検索結果をブロックし、又は個々の検索結果を保存することができる。更に、このＧＵＩによって、ユーザは、クエリタームに関連する１又は複数の概念に関する記述を追加し、編集し、閲覧することができ、及びこの概念に関する情報をどのように検索したらよいかを示すアドバイスを追加し、編集し、閲覧することができる。
【００４２】
結果ページ１００は、クエリタームを挿入するボックス１１０と、検索エンジンによって返された結果リストを含む領域１６０を備える。また、領域１６０は、ユーザフィードバックを入力するためのユーザフィードバックメカニズム１７０と、検索エンジンが返す各結果に関連するリンクを削減するメカニズム１９０とを含む。結果ページ１００は、更に、クエリタームに関連する概念の記述を表示する領域１２０と、クエリタームに関連する異なる概念の記述を含む領域１３０と、他のクエリタームにリンクする「ここも参照（see  also）」リンクを含む領域１４０（以下、「ここも参照（see  also）」リンク１４０とも言う。）と、関連するクエリタームを実行するリンクのリストを含む領域１５０と、スポンサー付きのリンクの領域１８０とを備える。後に詳細に説明するように、好ましい実施の形態では、後のクエリについては、後の表示のための格付け又はブロックをするユーザフィードバックメカニズム１７０、又は保存するメカニズム１９０に基づき、他のユーザによって、領域１６０の結果を変更できる。            
【００４３】
図１の具体例に示すように、ユーザがボックス１１０内にクエリターム「Ｕ２」を入力し、検索を要求すると、結果ページ１００がユーザに返される。領域１２０は、ユーザによって入力されたクエリターム「Ｕ２」に関連する１つの概念の記述、この具体例では、バンド「Ｕ２」の説明を表示する。領域１３０は、ユーザによって入力されたクエリ「Ｕ２」の異なる概念の記述、この具体例では、Ｕ２偵察機（U2  spy  plane）の説明を表示する。領域１５０は、ユーザによって入力され、又はアルゴリズムから導出された、ユーザが検索エンジンに実行させることを望む可能性がある「Ｕ２コンサートチケット」又は「
Ｕ２ｉＰｏｄ」等、関連する検索のためのクエリタームを表示する。領域１４０は、例えば、「バンドＵ２」の概念のための「ボノ（Bono）」又は「偵察機Ｕ２」の概念のための「ドラゴンレディ（Dragon  Lady）」等、ユーザによって入力され、又はアルゴリズムから導出された、他のクエリタームに関連する概念への「ここも参照（see  also）」ハイパーリンクを含む。
【００４４】
領域１６０は、検索の結果だけではなく、ユーザフィードバックメカニズム１７０を含む。ユーザは、ユーザフィードバックメカニズム１７０を用いて、対応するウェブページが、自ら検索を望んでいた情報にどれ程一致していたかを評価できる。換言すれば、領域１６０にリストされた第１のウェブページが、ユーザが検索したロックバンドＵ２に関する関連情報を含んでいる場合、ユーザは、ユーザフィードバックメカニズム１７０を用いて、このリンクを高いスコア（例えば、５つ星）で格付けすることができる。一方、領域１６０にリストされている「Ｕ２」と呼ばれる洋服の型（clothing  line）の名称に関する第２のウェブページは、ユーザが検索した概念とは無関係であり、この場合、低いスコア（例えば、１つ星）で格付けすることができる。また、本発明では、バンド「Ｕ２」に興味を有する別のユーザが、後にクエリ「Ｕ２」で検索を行った場合、このユーザに返される結果リストは、第１のウェブページ（５つ星で、格付けされている。）を結果リストの上位に表示し、第２のウェブページ（１つ星で格付けされている。）を結果リストの下位に表示し、又は表示しない。このように、関連性が高い結果だけを上位に表示した結果リストをユーザに提供することができる。結果リスト内のサイトを後に閲覧するユーザは、自らが検索している概念に関連性が高いサイトのみに訪れる可能性が高くなる。このように、結果リストにおけるアイテムの順序は、ユーザフィードバックに基づいて決定され、更に、この順序の決定には、メタデータ及びユーザが入力していない他の情報も利用することができる。
【００４５】
ユーザは、クエリタームに関連する概念に関する説明を領域１２０、１３０に追加し、その概念に関してどのように情報を検索するかに関するクエリ又はアドバイスによって、概念に関する何らかの背景情報を提供することができる。また、ユーザは、自らが又は他のユーザが以前に追加又は変更したクエリタームに関連する概念に関する説明を変更し、捕捉し、又は削除することができる。更に、ユーザは、異なるクエリタームに関連する概念にリンクする「ここも参照（see  also）」リンク１４０を変更し、追加し、削除することができる。ユーザは、概念に対して提案されたクエリを領域１５０に追加することができ、これらがクリックされると、検索エンジンにクエリが送信される。また、検索エンジンは、コンピュータアルゴリズムを用いて、提案されたクエリタームを生成することができる。
【００４６】
ユーザは、その概念に関連性が非常に高いと思われるドキュメントへのリンクを追加又は保存することができる。また、ユーザは、その概念に関連性が非常に高いと思われるドキュメントへのリンクを保存することができる。これは、リンクを手動で入力することによって、又はハイパーリンク又は「セーブ（Save）」のマークが付された、又は例えば、「ブックマーク（Bookmark）」、「タグ（Tag）」又は「お気に入りに追加（Add  to  Favo
rites）」等の他のタームで表される領域１９０のアイコンをクリックすることによって行われる。ユーザが異なれば、どのサイトが関連性が高いかに関する結論も異なるので、本発明に基づくアルゴリズムがリストされたサイトの順序を決定してもよい。一実施の形態においては、アルゴリズムは、「多数決」処理を用いて、最も多くの「票」が投票された（例えば、最も多くのユーザによって「セーブ」された）ドキュメントを結果リストの上位に表示する。
【００４７】
「セーブ」されたドキュメントへのリンクを、検索エンジンが生成する結果リストに表示する場合、アイコン１６５を用いて、このリンクは、ユーザによって投票されたリンクであることを明示することもできる。また各検索結果の下には、結果リストの一部としてリンクを追加したユーザ名を示す「Ｂｙ」エントリ１６７及びユーザがリンクにタグ付けし、又は以前の検索で生成されたタームを示す「タグ」エントリ１６８が表示される。
【００４８】
本発明では、ウェブサイトへのリンクを、結果リスト（アルゴリズムによって生成される。）及びユーザが入力したリンクの２つの独立したリスト又は上述したようにアイコンによってマークされたユーザが入力したリンクを含む１つのリストに統合されたリストとして、２通りの手法で表示することができる。
【００４９】
なお、本発明に基づく多くの変形例を想到できる。例えば、ユーザが生成したフィードバックは、端末装置からユーザが直接入力するのではなく、ファイルから読み出してもよい。更に、結果ページ１００は、例えば、「ここも参照（see  also）」リンク１４０等の領域を表示しているが、本発明に基づき、ユーザが入力した情報を含む結果ページは、図１に示す領域を含む又はこれらの領域以外の領域の如何なる組合せと共に表示してもよい。これらの情報は、検索結果をより判りやすく、正確に、及び有意義にするために用いられる。
【００５０】
図２は、本発明の一実施の形態に基づくインターネット検索アプリケーション２００の動作のフローチャートである。インターネット検索アプリケーション２００によって、ユーザは、システムに情報を入力することができ、他のユーザは、これらのユーザ入力に基づいて、より関連性が高い検索結果を閲覧することができる。この情報に基づき、特定のクエリに応じて生成される結果リストにおけるドキュメントを格付けするために検索エンジンが使用するメソッド及び重みが調整される。この結果、結果リストは、より関連性が高い結果が返されるように、ユーザフィードバックに応じて「調整」される。
【００５１】
ステップ２１０では、ユーザは、検索エンジンにクエリを入力する。そして、処理は、ステップ２２０に進み、ここで、検索エンジンは、クエリを照合し、最も関連性が高い結果のリストを構築する。処理は、ステップ２２０からステップ２３０に進み、ここで、結果ページ（例えば、図１の結果ページ１００）をユーザに送信する。処理は、ステップ２３０から、ステップ２４０又は２５０の何れかに進む。
【００５２】
ステップ２４０では、ユーザは、１つ以上のリンクを介して、結果リスト内のウェブページを閲覧する。これに代えて、ステップ２５０において、ユーザは、検索エンジンにフィードバックを提供するために、フィードバックメカニズム（例えば、図１の領域１７０）とインタラクトしてもよい。また、ユーザは、ステップ２５０において、検索エンジンによってリンクを記録するために、リンクを保存するためのメカニズム（例えば、図１の領域１９０）をクリックしてもよい。ユーザは、ステップ２４０において、ウェブサイトを訪問し、これに続いて、ステップ２５０において、フィードバックを行ってもよく、或いは、ユーザは、ステップ２５０からステップ２４０に進むこともできる。ステップ２４０及びステップ２５０の何れも、ステップ２６０に続き、検索エンジンは、このステップ２６０において、ユーザからのフィードバックを記録する。ステップ２６０に続くステップ２７０においては、検索関連性のためのモデルが、その後の検索の使用のために更新される。処理は、ステップ２７０からステップ２２０に戻り、検索エンジンは、後のクエリに対して、更新後のモデルによって提供された値を用いて、どのリンクが関連性が高いかを判定する。
【００５３】
なお、本発明の実施の形態は、１又は複数の検索エンジンに適用することができる。一具体例として、第１の検索エンジンは、第１の検索エンジンによって採用された適合率に基づいて、ドキュメントのリストを返す。次に、第２の検索エンジンは、これらの結果を単独で格付けしてもよく、或いは、これらの結果と、本発明に基づく第２の検索エンジンが生成した結果とを組み合わせて格付けを行ってもよい。そして、これらの結果の全て又は如何なる組合せを用いて、本発明に基づく関連性モデルを更新してもよい。このように、本発明に基づく検索は、メタ検索エンジン上で実行してもよい。
【００５４】
一実施の形態に基づくシステムは、登録されたユーザ及び未登録のビジタを含むインターネット検索エンジンのポータルサイトに基づいている。ユーザクエリに基づく多くの検索エンジンと同様に、ドキュメントのユニフォームリソースロケータ（Uniform  Resource  Locator：ＵＲＬ）が関連性スコアの降順に格付けされ、この順序でユーザに提供される。関連性スコアは、Ｘに含まれている所定の特徴（又は、観測された根拠）が与えられた場合にドキュメントｄがクエリｑに関連している確率ｐ（Ｒ｜Ｘ）として表される。なお、ここでは、説明を明瞭にするために、後に説明する添字を省略している。ｐ（Ｒ｜Ｘ）は、関数μ（Ｘ）＝１／［１＋ｅ−θ＊Ｘ］によって近似され、ここで、Ｘは、特徴ベクトルを表し、θは、１．０の定数入力によって乗算された切片項を含むパラメータのベクトルを表し、正の係数が、関連性に関する肯定的な根拠を示すように、θの負の値が用いられている。なお、この確率は、ロジスティック回帰（logistic  regression）を用いてモデル化され、Ｘは、ドキュメント固有の特徴（例えば、ドキュメントの長さ等）及び例えば、ドキュメントタイトルにおけるクエリの出現等のクエリ−ドキュメント特徴の両方から構成され、ドキュメントは、検索エンジンＥ等からランクＫを獲得し、後に、クエリとドキュメントに亘るユーザ格付けのためのインジケータ変数の疎集合Ｕによって昇格される。
【００５５】
ユーザは、検索エンジンによるクエリの結果を見て、クエリに関連するドキュメントに対して、最低の格付け（例えば、１つ星）が無関連を意味し、最高の格付け（例えば、５つ星）が完全な又は略々完全な関連性を示す何らかの序列形式で、フィードバックを行うことができる。そして、このフィードバックは、ユーザｕによって指定された星の数をｓとして、新たなクエリ−ドキュメント特徴（ｑ，ｄ，ｕ）＝ｓとして登録される。如何なる時点においても、この値は、ドキュメントｄ及びクエリｑに関するユーザｕの現在の格付けを表す。ここでは、この特徴は、ユーザがクエリを実行した回数に依存せず、ユーザによる最後の格付けを保存している点が重要である。所定のクエリ−ドキュメント対について全てのユーザフィードバックを収集することによって、ユーザｕが与えられたクエリｑに対するドキュメントｄについて５つ星を付与した場合、インジケータ変数の新たな疎集合Ｕ（ｑ，ｄ）ｕ，ｓ＝１が得られる。特徴集合は、Ｕ内の特徴によって拡大され、完全モデルは、ベクトルθによってパラメータ化される。ユーザフィードバックを収集する前には、星の数は未知又は中立的であり、これは、ユーザが未だドキュメントの関連性を
明示的に評価していないことを意味する。これは、データセットが、純粋に、ユーザによって格付けされたドキュメントのみから構成されるという意味で重要である。
【００５６】
システムは、ユーザフィードバックを用いて、３つの基本機能を実行する。第１に、システムは、フィードバックを用いて、θ内の包括的モデルパラメータへの加算の形式で、ユーザ固有のパラメータのベクトルψを算出する。第２に、システムは、ユーザのベクトルψが分布する空間に亘ってユーザをクラスタ化させることができる。ここでは、次元が例えば、同じスケール、独立性等非常に明瞭な数学的特性を有する回帰係数であるので、例えば、Ｋ平均クラスタリング等の単純な手法が成功すると予想される。これを用いて、例えば、ユーザ固有のベクトルψと同様の手法で、ベクトルθに加算できるパラメータのクラスタ固有のベクトルγ等を構築できる。第３に、システムは、θ及びユーザのベクトルψのプロパティを推定し、特定のイベントの重要性に重みを与えるためのモデリング処理におけるデータポイントとして、ユーザフィードバックイベントを組み込むことができる。
【００５７】
ユーザが、クエリ−ドキュメント対に対して星の数による格付けを行うと、ユーザ固有のデータセット内にデータポイントが生成される。１．０の値は、非常に関連性が高い格付けに対応し、０．０の値は、関連性が低い又は無関連の格付けに対応する。最大５個の星で格付けを行う方式では、５つ星は、非常に関連性が高いことを示し、１つ星は、関連性がないことを示すために使用される。システムは、他のユーザパラメータ及び包括的パラメータのための特徴として、他の格付けを用いる。技術的には、完全な分布をモデル化することが望まれた場合、出力変数は、多項分布から抽出されたように処理する必要があ
る。そして、データポイントは、何らかの確立された期間又は何らかのある最大データセットサイズに戻るシステム内の全ての格付けイベントデータポイントから構成される更新データベースに加えられる。疎ロジスティック回帰（sparse  logistic  regression）演算は、数百万個のデータポイントに対して実行できる。この制限に達すると、最後のＮ個のデータポイントに対して、回帰演算が実行される。ここで、Ｎは、数百万以内の数と予測することができる。推定されるモデルは、以下の式に基づき、与えられたクエリ−ドキュメントの対について、ユーザ格付けイベント毎に特定される。
【００５８】
【数１】
0005632124.tif 000002
【００５９】
ここで、θは、固定の値であり、回帰は、ψ内のユーザパラメータに亘って実行される。また、ψｕが、Ｖ内の他のユーザのインジケータＵ（ｑ，ｄ）ｖ，ｓ＝１の係数を潜在的に含むように、Ｕ内のユーザ格付けインジケータも組み込まれる。例えば、ユーザｕが、クエリｑについて、ドキュメントを５つ星で格付けした場合、そのドキュメントがユーザｕについて非常に関連性が高い肯定的証拠であることを示す正の係数を与えてもよい。拡大された特徴集合は、このインスタンスがデータセットに含まれたメカニズムのために、高い関連性について、自己インジケータ変数Ｕ（ｑ，ｄ）ｕ，５を含む。非常に疎である自己インジケータのこの包含によって、回帰は、過去の潜在的矛盾に移動し、このクエリ及びユーザについてドキュメントが高いスコアを獲得するように、モデルを進化させる。一方、ユーザｕが包括的な効果を見出している場合、この疎である自己インジケータには、大きな重みを与えない。処理の終わりには、格付けイベントを行った各ユーザｕは、クラスタリングのために検査及び使用でき、そのユーザのために関連性スコアモデルを個人化する固有のψｕを有する。
【００６０】
システム内の特定された各ユーザについてψベクトルが得られると、これらのベクトルを座標空間に並び替えることができ、クラスタリングが実行される。これは、パラメータの遠心率が大きい検索エンジンのオプティマイザ又はスパマを、自らの又は関連するコンテンツに向かう任意のバイアスを反映するように分離することが望まれる場合に役立つ。更に、不特定のユーザ（すなわち、登録されていない「訪問者」）について、より良好なデフォルトパラメータを提供するために、特定されたユーザの固定のクラスタを用いることもできる。例えば、クエリｑを発行する不特定のユーザに基づいて、Ｃをユーザクラスタの集合として、ベイズ規則を用いて、以下の演算によって、ユーザがクラスタｃによって表される確率を算出できる。
【００６１】
【数２】
0005632124.tif 000003
【００６２】
そして、関連性スコアｐ（Ｒ｜Ｘ）は、各クラスタメンバシップ確率に関連性スコアを乗算した値の加重和又は以下に示すような、所定のクラスタメンバシップｐｃ（Ｒ｜Ｘ）の確率に等しくなる。
【００６３】
【数３】
0005632124.tif 000004
【００６４】
ここで、各クラスタγｃのためのパラメータは、包括的パラメータθへの加算として計算される。このための処理については後述する。
【００６５】
ユーザ固有のパラメータγｃの推定に続いて、θにおいてパラメータ化されたオリジナルモデルが更新される。これは、ψｕの推定のために算出された同じユーザ格付けデータの集合を用いて実行されるが、ここでは、ψパラメータは、固定されている。全てのユーザから収集された経験から、第１のユーザの特定の効果に続いて包括的な効果といった具合に、交互に、一般的な効果を推定することが試みられる。各ユーザのψパラメータの推定においては、各ケースの重みの過不足が適切に弁別的に学習される（単一の大規模な回帰を介して実行される）。例えば、ψ内の係数の独立性を仮定すると、各データポイントの値は、以下の式に示すように、ユーザｕによって提出されたカーネル関数を用いて、ユーザ母集団の平均へのユーザの類似性として算出できる。
【００６６】
【数４】
0005632124.tif 000005
【００６７】
この値の最大値は、１．０であり、全てのψベクトルの面積中心からのψベクトルを有するユーザについて、レートαで減衰する。この手法では、回帰の形式は、以下に示すように、所定のθが与えられて、データの対数尤度の合計を最大にする。
【００６８】
【数５】
0005632124.tif 000006
【００６９】
ここで、θに関して極大が取られ、データセットＤ内のデータポイントの数をＮとして、ｉ＝１〜Ｎの総和が算出され、ｙｉは、データポイントが非常に関連していると格付けされた場合１．０であり、関連していないと格付けされた場合０．０であり、ωｉは、提出者のψｕパラメータのプロパティに基づくデータセット内の各観測値ｉの重みであり、データＤへの依存は、明瞭化のために省いている。
【００７０】
これに代えて、上述したハードクラスタリングステップの結果を用いて、パラメータγｃを適応化し、これにより格付けデータポイントを提出したユーザにどのクラスタが割り当てられたかに応じて、θを修正してもよい。ハードクラスタリングとは、各ユーザを単一のクラスタに割り当てることを意味し、一方、ソフトクラスタリングとは、ユーザを、それぞれ何らかの度合いのメンバシップとともに、複数のクラスタに割り当てることを意味する。この場合、回帰は、式（３）用いて実行され、最適化は、以下に示すように、μを指定して、θ及びγｃの両方に対して実行される。
【００７１】
【数６】
0005632124.tif 000007
【００７２】
γｃは、特徴Ｘを生成し、μ（θ，γ）ｉを算出するために用いられた特定のデータポイントを提出したユーザのクラスタメンバシップに基づいて割り当てられる。ユーザ固有のψ回帰に付いて上述したように、格付けの挙動における如何なる矛盾もγｃに含まれる各パラメータのためのクラスタ固有の修飾子に吸収される。
【００７３】
γを用いる具体例として、数個乃至数百個の格付けイベントを提出する２００人のユーザからのデータセットにおいて、各ユーザについて、クラスタＣの集合からクラスタ割当ｃが生成されるとする。θの推定（例えば、θ（ＥｎｇｉｎｅＲａｎｋＥ，４））の際、例えば、ユーザがクラスタｋに含まれているという仮定に基づき、γｋ（ＥｎｇｉｎｅｒａｎｋＥ，４）のように、対応するγｃの推定も行われる。他のデータポイント内では、θ（ＥｎｇｉｎｅＲａｎｋＥ，４）が推定されるが、ここでは、ドキュメントがクエリについて（ＥｎｇｉｎｅＲａｎｋＥ，４）を有しており、２人のユーザがそれぞれクラスタｋ及びクラスタｍに由来すると仮定し、クラスタｍについてγｍ（ＥｎｇｉｎｅｒａｎｋＥ，４）が推定される。この結果、θ（ＥｎｇｉｎｅＲａｎｋＥ，４）は、変数の平均的効果となり、γ（ＥｎｇｉｎｅｒａｎｋＥ，４）は、クラスタ固有の変数の効果を含む（例えば、ＳＥＯクラスタは、良好な変数に対する感度が平均より劣ることが多いが、これらの好ましくない影響は、包括的モデルから効果的に除外されるため、負の係数を有することがある）。これは、モデル適応化処理において、ユーザのクラスタ割当に基づいて特徴ベクトルを収集したときから常に変化しない。
【００７４】
包括的な更新について記述した両方のスキームにおいて、ユーザによる格付けは、包括的パラメータの適応化に関する各ユーザの影響を決定する。何れの場合も、ユーザの格付け操作に基づくユーザ入力の効果は、自動的に制限される。
【００７５】
ユーザについて、パラメータの最初の一組を最適化し、次に、包括的な及び／又はクラスタ効果について最適化を行うことによって、適応化処理は、２つの独立した解析のレベル間でフォーカスを交替する。最適化をモデリングの実行に亘って連続して実行するべきか、交互の最適化の個々の反復について実行するべきかは完全には明らかではない。
【００７６】
図３は、本発明に基づくシステム３００の構成を示している。システム３００は、ウェブサーバ３１０に接続されたユーザクライアント３０５を備える。ウェブサーバ３１０は、検索エンジン３２０、ユーザデータベース３３０及びフィードバックデータベース３４０に接続されている。検索エンジン３２０は、ドキュメントインデクスを含むデータレポジトリ３５０（以下、ドキュメントインデクス３５０とも言う。）に接続されている。また、ユーザデータベース３３０は、検索エンジン３２０にも接続されている。フィードバックデータベース３４０は、適合率を算出するために機械学習モデル３６０に接続されている。また、機械学習モデル３６０は、ドキュメントインデクスを含むデータレポジトリ３５０に接続され、データレポジトリ３５０は、インデクス生成器３７０に接続されている。インデクス生成器３７０は、ウェブコンテンツデータベース３８０に接続され、ウェブコンテンツデータベース３８０は、ウェブクローラ３９０に接続されている。ウェブクローラ３９０は、インターネット３９５を介して、１つ以上のウェブサイト３９９に接続される。
【００７７】
実際の動作では、ウェブクローラ３９０は、インターネット３９５をナビゲートし、ウェブサイト３９９に訪問し、ウェブコンテンツデータベース３８０のデータを収集する。インデクス生成器３７０は、ウェブコンテンツデータベース３８０を用いて、ドキュメントインデクス３５０を生成する。ユーザがユーザクライアント３０５を介してクエリを生成すると、ウェブサーバ３１０は、検索エンジン３２０に検索要求を送信する。検索エンジン３２０は、上述したユーザが生成したフィードバックに基づき、どのウェブページがクエリに最も関連している可能性が高いかを判定して、結果リストを生成し、ウェブサーバ３１０に送信する。そして、ウェブサーバ３１０は、ユーザクライアントに表示するための結果ページを供給する。
【００７８】
また、ユーザは、検索を行う際、ユーザクライアント３０５を用いてクエリを入力し、ウェブサーバ３１０に送信する。ウェブサーバ３１０は、検索エンジン３２０にクエリを送信し、検索エンジン３２０は、クエリをドキュメントインデクス３５０に対して照合し、最も関連性が高いドキュメントを判定し、ウェブサーバ３１０に結果リストを返す。また、ユーザデータベース３３０は、クエリに応じて、例えば、保存リンクメカニズム（例えば、図１の領域１９０）を用いて保存されたリンク、クリックされたリンク（例えば、図１の領域１６０）、フィードバックメカニズム（例えば、図１の領域１７０）を用いて行われたフィードバック等、ユーザの検索に関する情報を記録する。この情報は、ウェブサーバ３１０及び検索エンジン３２０によって、そのユーザのための後の検索結果をカスタマイズするために使用される。また、クエリに応じて、フィードバックメカニズム（例えば、図１の領域１７０）からのフィードバックもフィードバックデータベース３４０に記録される。本発明の実施の形態においては、ユーザデータベース３３０及びフィードバックデータベース３４０に保存されるフィードバック情報は、２つの独立したデータベースとして実現してもよく、同じデータベース内に実現してもよい。
【００７９】
何らかのタイミングで、例えば、クエリが実行された際、フィードバックデータベース３４０に格納されているフィードバック情報は、機械学習モデル３６０に送信され、ここで処理され、クエリに対して最も関連性が高いウェブページを判定するために検索エンジンで用いられるメソッド及び重みが生成される。機械学習モデル３６０は、後の検索で使用するために、このフィードバック情報をドキュメントインデクス３５０に記録する。
【００８０】
フィードバックデータベース３４０は、以下に限定されるわけではないが、クエリターム、ユーザ識別情報、ドキュメント識別情報、ドキュメントリンク、結果リスト内の位置、ユーザによる格付け、ユーザによるクリック等の特徴を機械学習モデル３６０に送信する。また、機械学習モデル３６０は、以下に限定されるわけではないが、タームスコア、セクション情報、リンク構造、アンカーテキスト、要約、タグ、ドキュメント内のターム、ドキュメント内のタームの位置、ドキュメントの構造、検索結果リストからドキュメントがアクセスされた回数、タームスコア、セクション情報、リンク構造、ユーザ表現、ユーザ入力の時刻、ブロック等、所定のドキュメントの他の特徴を参照することができる。
【００８１】
機械学習モデル３６０は、これらの特徴を用いて、包括的モデルパラメータに追加される形式で、ユーザ固有のパラメータのセットを生成する。これらのパラメータは、以下のように導出される：各フィードバックイベントは、データポイントを構成し、これらは、フィードバックデータベース３４０内の全てのデータポイントのデータベースに加えられる。モデルを用いて、上述した式（１）に基づき、与えられたクエリ−ドキュメント対について、ユーザ格付けイベントを推定する。
【００８２】
以前に参照された入力データに対して回帰演算が実行される。最良のパラメータが発見されると、これらのパラメータを用いて、包括的モデル及びユーザ固有のモデルが更新される。通常、最良のパラメータは、最良の予測力を有するパラメータであり、これは、未知のデータに関して最良の結果が得られるパラメータと解釈される。本発明の一実施の形態においては、モデリング処理の一部として共役勾配降下法を用いる論理的回帰演算が実行される。なお、本発明に基づくモデリング処理は、他のメソッドと同様に、他の形式の回帰を用いて実行してもよい。
【００８３】
なお、本発明では、統計的分類の形式を用いる機械学習技術を含む多くの種類の機械学習技術を用いることができる。統計的分類には、以下に限定されるものではないが、ロジスティック回帰分析、サポートベクトルマシン、ニューラルネットワーク、ブーストされた決定木（boosted  trees）、ランダムフォレスト（random  forests）、ナイーブベイズ、グラフィックモデル及び事後確率最大推定（maximum  a  posteriori）等が含まれる。他の実施の形態では、機械学習技術は、共役勾配降下法を用いる。
【００８４】
図４は、本発明の一実施の形態に基づき、ユーザフィードバックデータを用いて結果を算出するステップ４００を示すフローチャートである。図４に示す式番号及び図４の説明にいて用いる式番号は、上述した式に対応する。
【００８５】
図４に示すように、ステップ４１０において、ユーザは、フィードバックデータを入力し、ステップ４２０において、入力データを正規化する。この処理は、包括的なデータ及びユーザ毎のデータの抽出及び正規化を含む。ステップ４３０では、式（１）を用いてデータポイントにスコアを付け、ステップ４４０では、式（３）を用いて、目的関数を算出する。式（１）は、クラスタリングを用いたスコア付けを含む多くの形式を含むことができる。ステップ４５０では、共役勾配を算出し、ステップ４６０では、新たな勾配を用いて、パラメータを更新する。ステップ４７０では、１つ以上の停止基準が満たされたかを
判定する。１つ以上の停止基準が満たされていない場合、処理は、ステップ４３０に戻り、この他の場合、処理は、ステップ４８０に進み、包括的モデル及びユーザモデルが更新される。
【００８６】
ステップ４７０における停止基準として如何なる数及び種類の基準を用いてもよい。停止基準としては、例えば、以下に限定されるものではないが、（１）反復が所定の最大回
数実行された場合、（２）交差検定に失敗した場合（例えば、テストデータがトライアルデータと異なっていた場合）、（３）ソリューションが修飾した場合、すなわち、先の実行におけるパラメータと、次の実行におけるパラメータとの間の差分が、所定の値を下回る場合等がある。
【００８７】
図５は、ユーザ５１０が使用する、本発明に基づくインターネット検索アプリケーションシステム５００のためのハードウェア構成を示している。インターネット検索アプリケーションシステム５００は、インターネット５３０を介してウェブサーバ５４０に接続されるクライアント装置５２０を備えている。クライアント装置５２０は、例えば、以下に限定されるわけではないが、ハイパーテキストトランスファープロトコル（Hypertext  Transfer  Protocol：ＨＴＴＰ）、ワイヤレスアプリケーションプロトコル（Wireless  Application  Protocol：ＷＡＰ）等のインターネットプロトコルを用いてウェブサーバ５４０にアクセスし、通信を行うように構成された機器である。クライアント装置５２０は、好ましくは、パーソナルコンピュータである。これに代えて、クライアント装置５２０は、以下に限定されるわけではないが、例えば、ハイパーテキストマークアップランゲージ（Hypertext  Markup  Language：ＨＴＭＬ）、ハンドヘルドデバイスマークアップランゲージ（Handheld  Device  Markup  Language：ＨＤＭＬ）、ワイヤレスマークアップランゲージ（wireless  markup  language：ＷＭＬ）等の規格に基づいて情報を提供できる携帯型機器、例えば、携帯電話機又は携帯情報端末（personal  digital  assistant：ＰＤＡ）を始めとする他の機器であってもよい。
【００８８】
ウェブサーバ５４０は、検索サーバ５５０及びフィードバックデータ蓄積装置５６０の両方に接続される。フィードバックデータ蓄積装置５６０は、機械学習サーバ５７０に接続され、検索サーバ５５０は、インデクスデータ蓄積装置５８０に接続されている。更に、機械学習サーバ５７０は、インデクスデータ蓄積装置５８０に接続されている。
【００８９】
添付の特許請求の範囲によって定義されている本発明の精神及び範囲から逸脱することなく、実施の形態を変更できることは、当業者にとって明らかである。
【図面の簡単な説明】
【００９０】
【図１】ユーザフィードバック及びユーザがフィードバックを提供するメカニズムを組み込んだ、検索結果リストを表示する例示的なグラフィカルユーザインタフェースを示す図である。
【図２】ドキュメント格付け処理にユーザフィードバックを適用できる例示的なインターネット検索アプリケーションの動作を示すフローチャートである。
【図３】本発明に基づく例示的なインターネット検索システムの構成を示す図である。
【図４】本発明に基づき、ユーザフィードバックデータを用いて、結果リストに含まれる結果を算出するステップを示すフローチャートである。
【図５】本発明に基づく例示的なインターネット検索アプリケーションシステムのハードウェア構成を示す図である。
【図１】
0005632124.tif 000008
【図２】
0005632124.tif 000009
【図３】
0005632124.tif 000010
【図４】
0005632124.tif 000011
【図５】
0005632124.tif 000012