(57)【要約】情報検索システムは、それぞれがクエリ修正方針を実行する１以上のクエリ修正を提供するクエリ修正構造を含む。クエリ・ランク・リバイザは、全てのクエリにランクを最初に割り当てること、そして既知の高ランク付けされたクエリ（ＫＨＲＱ）のセットを識別することによって、最初のクエリへ修正として既知の高ランク付けされたクエリを提案する。ＫＨＲＱに修正されることの強い確率をもつクエリは、近くのクエリ（ＮＱ）として認知される。ＫＨＲＱである変形クエリは、所定のクエリに候補修正として提供される。ＮＱである変形クエリのために、対応する既知の高ランク付けされたクエリは候補修正として提供される。【選択図】        図５
2008535090.tif 000002
【特許請求の範囲】
【請求項１】
最初のクエリに応答して既知の高ランク付けされたクエリを自動的に提案する方法であって、
索引付けされたクエリ及び該索引付けされたクエリのクエリランクに関して、前記最初のクエリの修正確率の関数として該索引付けされたクエリのための修正スコアを計算することと、
前記修正スコアに応答して、前記最初のクエリの代替クエリとして前記索引付けされたクエリを選択して取り出すことと、
既知の高ランク付けされたクエリに該当する前記代替クエリに応答して、候補修正クエリとして前記代替クエリを返すことと
で構成されることを特徴とする方法。
【請求項２】
請求項１に記載された方法であって、更に、統計学的に高い確率で或る既知の高ランク付けされたクエリに修正される前記代替クエリに応答して、候補修正クエリとして当該或る既知の高ランク付けされたクエリを返すことで構成されることを特徴とする方法。
【請求項３】
請求項１に記載された方法であって、前記最初のクエリはクエリ修正であることを特徴とする方法。
【請求項４】
請求項１に記載された方法であって、前記関数は、前記索引付けされたクエリと前記索引付けされたクエリのクエリランクに関する前記最初のクエリのための修正確率の産物であることを特徴とする方法。
【請求項５】
請求項１に記載された方法であって、更に、既知の高ランク付けされたクエリとしてクエリを識別することを特徴とする方法。
【請求項６】
請求項５に記載された方法であって、更に、
クエリに関してクエリ発生頻度を計算することと、
前記クエリに関してユーザ満足度スコアを計算することと、
クエリ発生頻度とユーザ満足度スコアの関数として、前記クエリのためのランクを計算することと
を具備することを特徴とする方法。
【請求項７】
請求項６に記載された方法であって、前記ユーザ満足度スコアは検索結果上のクリックの距離を測定しているユーザクリック動作データによって決定されることを特徴とする方法。
【請求項８】
請求項６に記載された方法であって、前記ユーザ満足度スコアは反比例の修正頻度によって決定されることを特徴とする方法。
【請求項９】
請求項８に記載された方法であって、前記反比例の修正頻度は前記クエリが修正された回数の逆数を前記クエリのためのクエリ発生頻度で割ったものであることを特徴とする方法。
【請求項１０】
請求項１に記載された方法であって、更に、前記索引付けされたクエリを含んで構成されるクエリのインデックスを生成することを特徴とする方法。
【請求項１１】
請求項１０に記載された方法であって、前記インデックスは該インデックス内のそれぞれのクエリから１以上の既知の高ランク付けされたクエリへのポインタを含むことを特徴とする方法。
【請求項１２】
請求項１に記載された方法であって、前記修正確率は前記最初のクエリに関して前記索引付けされたクエリの行動の類似度を含むことを特徴とする方法。
【請求項１３】
請求項１に記載された方法であって、前記修正確率は前記最初のクエリに関して前記索引付けされたクエリの意味の類似度を含むことを特徴とする方法。
【請求項１４】
請求項１に記載された方法であって、前記修正確率は前記最初のクエリに関して前記索引付けされたクエリの構文上の類似度を含むことを特徴とする方法。
【請求項１５】
請求項１に記載された方法であって、更に、
ユーザセションから作成されたクエリデータを記録することと、
前記クエリのインデックスを作成するために前記クエリデータを使うことと
を具備することを特徴とする方法。
【請求項１６】
請求項１に記載された方法であって、更に、
信頼性尺度として候補修正クエリのための修正スコアを使って前記候補修正クエリを評価すること
を具備することを特徴とする方法。
【請求項１７】
請求項１に記載された方法であって、更に、
前記最初のクエリへ提案する修正として前記候補修正クエリを提供すること
を具備することを特徴とする方法。
【請求項１８】
請求項１７に記載された方法であって、前記提案する修正は信頼性尺度の修正強度に依存している場所でユーザへ表示されることを特徴とする方法。
【請求項１９】
最初のクエリに応答して既知の高ランク付けされたクエリを自動的に提案する方法であって、
ユーザセションから作成されたクエリデータを記録することと、
ユーザセションの間にクエリのインデックスを作成することと、
索引付けされたクエリと前記索引付けされたクエリのためのクエリランクに関して、前記最初のクエリのための修正確率の関数として索引付けされたクエリのための修正スコアを計算することであって、前記修正確率は前記最初のクエリに関して前記索引付けされたクエリの類似度を含むものと、
前記修正スコアに対応して、前記最初のクエリのための代替クエリとして前記索引付けされたクエリを選択して取り出すことと、
既知の高ランク付けされたクエリである前記代替クエリに対応して、候補修正クエリとして前記代替クエリを返すことであって、前記既知の高ランク付けされたクエリを識別することは、
前記クエリに関してクエリ発生頻度を計算することと、
前記クエリに関してユーザ満足度スコアを計算することであって、前記ユーザ満足度スコアは検索結果上のクリックの距離を測定しているユーザクリック動作データによって決定されることと、
クエリ発生頻度とユーザ満足度スコアの関数として、前記クエリのためのランクを計算することとからなるものを含むものと、
既知の高ランク付けされたクエリである前記代替クエリに対応して、候補修正クエリとして前記代替クエリを返すことと、
信頼性尺度として候補修正クエリのための修正スコアを使って前記候補修正クエリを評価することと、
前記最初のクエリへ提案する修正として前記候補修正クエリを提供することであって、前記提案する修正は信頼性尺度の修正強度に依存している場所でユーザへ表示されるものと
で構成されることを特徴とする方法。
【請求項２０】
既知の高ランク付けされたクエリとしてクエリを識別する方法であって、
クエリに関してクエリ発生頻度を計算することと、
前記クエリに関してユーザ満足度スコアを計算することと、
クエリ発生頻度とユーザ満足度スコアを使って前記クエリについてのクエリランクを計算することと
を具備することを特徴とする方法。
【請求項２１】
請求項２０に記載された方法であって、更に、
前記クエリについての前記クエリランクを他のクエリに対応した他のクエリランクと比較し、該クエリランクが他のクエリランクよりも大きいかどうかを決定することと
を具備することを特徴とする方法。
【請求項２２】
請求項２０に記載された方法であって、前記クエリ出現頻度は単位時間当たりの前記クエリの頻度として計算されることを特徴とする方法。
【請求項２３】
請求項２０に記載された方法であって、前記ユーザ満足度スコアは反比例の修正頻度に基づくことを特徴とする方法。
【請求項２４】
請求項２３に記載された方法であって、前記反比例の修正頻度は前記クエリが修正された回数の逆数を前記クエリのためのクエリ発生頻度で割ったものであることを特徴とする方法。
【請求項２５】
請求項２０に記載された方法であって、前記ユーザ満足度スコアは品質スコアの関数であることを特徴とする方法。
【請求項２６】
請求項２５に記載された方法であって、クエリのための前記品質スコアは検索結果上のクリックの距離を測定しているユーザ行動データから測定されることを特徴とする方法。
【請求項２７】
請求項２０に記載された方法であって、前記クエリランクはクエリ出現頻度とユーザ満足度スコアの関数であることを特徴とする方法。
【請求項２８】
請求項２０に記載された方法であって、前記既知の高ランク付けされたクエリは候補修正クエリとして返されることを特徴とする方法。
【請求項２９】
最初のクエリに応答して既知の高ランク付けされたクエリを自動的に提案するためのコンピュータプログラムであって、コンピュータに、
索引付けされたクエリ及び該索引付けされたクエリのクエリランクに関して、前記最初のクエリの修正確率の関数として該索引付けされたクエリのための修正スコアを計算するステップと、
前記修正スコアに応答して、前記最初のクエリの代替クエリとして前記索引付けされたクエリを選択して取り出すステップと、
既知の高ランク付けされたクエリに該当する前記代替クエリに応答して、候補修正クエリとして前記代替クエリを返すステップと
を実行させるためのコンピュータプログラム。
【請求項３０】
請求項２９に記載されたコンピュータプログラムであって、前記コンピュータに、更に、
統計学的に高い確率で或る既知の高ランク付けされたクエリに修正される前記代替クエリに応答して、候補修正クエリとして当該或る既知の高ランク付けされたクエリを返すステップを実行させることを特徴とするコンピュータプログラム。
【請求項３１】
請求項２９に記載されたコンピュータプログラムであって、前記コンピュータに、更に、
信頼性尺度として候補修正クエリのための修正スコアを使って前記候補修正クエリを評価するステップを実行させることを特徴とするコンピュータプログラム。
【請求項３２】
既知の高ランク付けされたクエリとしてクエリを識別するためのコンピュータプログラムであって、コンピュータに、
クエリに関してクエリ発生頻度を計算するステップと、
前記クエリに関してユーザ満足度スコアを計算するステップと、
クエリ発生頻度とユーザ満足度スコアを使って前記クエリについてのクエリランクを計算するステップと
を実行させることを特徴とするコンピュータプログラム。。
【請求項３３】
請求項３２に記載されたコンピュータプログラムであって、前記ユーザ満足度スコアは品質スコアの関数であることを特徴とするコンピュータプログラム。
【請求項３４】
請求項３２に記載されたコンピュータプログラムであって、クエリのための前記品質スコアは検索結果上のクリックの距離を測定しているユーザ行動データから測定されることを特徴とするコンピュータプログラム。
【請求項３５】
請求項３２に記載されたコンピュータプログラムであって、前記クエリランクはクエリ出現頻度とユーザ満足度スコアの関数であることを特徴とするコンピュータプログラム。
【請求項３６】
既知の高ランク付けされたクエリとしてクエリに修正クエリを提供するためのシステムであって、
索引付けされたクエリ及び該索引付けされたクエリのクエリランクに関して、前記最初のクエリの修正確率の関数として該索引付けされたクエリのための修正スコアを計算する手段と、
前記修正スコアに応答して、前記最初のクエリの代替クエリとして前記索引付けされたクエリを選択して取り出す手段と、
既知の高ランク付けされたクエリに該当する前記代替クエリに応答して、候補修正クエリとして前記代替クエリを返す手段と
を具備することを特徴とするシステム。
【請求項３７】
請求項３６に記載されたシステムであって、更に、
統計学的に高い確率で或る既知の高ランク付けされたクエリに修正される前記代替クエリに応答して、候補修正クエリとして当該或る既知の高ランク付けされたクエリを返す手段を具備することを特徴とするシステム。
【請求項３８】
請求項３６に記載されたシステムであって、更に、
信頼性尺度として候補修正クエリのための修正スコアを使って前記候補修正クエリを評価する手段を含むことを特徴とするシステム。
【請求項３９】
既知の高ランク付けされたクエリとして識別されているクエリに修正クエリを提供するためのシステムであって、前記システムは
クエリに関してクエリ発生頻度を計算する手段であって、
前記クエリに関してユーザ満足度スコアを計算する手段と、
クエリ発生頻度とユーザ満足度スコアを使ってクエリランクを計算する手段と
で構成されることを特徴とするシステム。
【請求項４０】
請求項３９に記載されたシステムであって、前記ユーザ満足度スコアは品質スコアの関数であることを特徴とするシステム。
【請求項４１】
請求項３９に記載されたシステムであって、クエリのための前記品質スコアは検索結果上のクリックの距離を測定しているユーザ行動データから測定されることを特徴とするシステム。
【請求項４２】
請求項３９に記載されたシステムであって、前記クエリランクはクエリ出現頻度とユーザ満足度スコアの関数であることを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的な情報検索システムに関する。特に、利用者クエリを修正するためのシステムと方法に関する。
【０００２】
関連出願の相互参照
本出願は、２００５年３月２９日付特許出願第１１／０９４，８１４号「多重クエリ修正モデルの統合」，２００５年３月３０日付特許出願第１１／０９６，１９８号「クエリ修正モデルのための信頼性の評価」，２００５年３月３０日付特許出願第１１／０９５，９２０号「提案された修正クエリの経験的な検証」，２００５年１１月２２日付特許出願第１１／２８５，８１４号「既知の高ランク付けされたクエリを用いたクエリ修正」に基づく優先権を主張する。また、この参照により本開示に含まれる
・２００３年９月３０日付特許出願第１０／６７６，５７１号「関連付けられた言葉群に基づく文書の特徴づけのための方法及び装置」；
・２００３年１２月１５日付特許出願第１０／７３４，５８４号「大規模設備教育システム及び方法」；
・２００３年１２月３１日付特許出願第１０／７４９，９００号「ネットワークブライジングをアシストする方法及びシステム」；
・２００４年６月２８日付特許出願第１０／８７８，９２６号「相互関係プロフィールを取得して用いるためのシステム及び方法」；
のそれぞれに関連する。
【背景技術】
【０００３】
インターネット・サーチ・エンジンによって例示される情報検索システムは一般に、速く一般に利用者のクエリに関係がある文書を提供することができる。サーチ・エンジンは、クエリへの文書の関連性を定める用語及び文書頻度の、文書間の連結と共にそして用語間のいろいろな統計学的手段を使うかもしれない。ほとんどのサーチエンジンの設計の下にある主技術的な仮定は、ユーザクエリがユーザの望ましい情報目的を正確に表すことである。
【０００４】
実際、ユーザは典型的に良いクエリを立てることが苦手である。しばしば、単一のクエリは望ましい結果を提供しない。そして、ユーザは同じトピックについて頻繁にいくつかの異なったクエリを入力する。これらの多数のクエリは典型的には、推測した実在者の名前、単語の並べ方のバリエーション、単語の数などの、望ましい結果セットに達するまでにクエリの長い鎖を時々形作る、クエリ用語の幅や特定性にばらつきを含む。異なるユーザは広く成功裏にクエリを変更するさまざまな能力をもっていることから、いろいろな自動化されたクエリ修正の方法が提案されている。
【０００５】
最も一般的に、クエリ・リファインメントは一般的なクエリから自動的にいっそう正確な（すなわち、より狭い）クエリを発生させるのに使用されている。上位結果がユーザの情報ニーズと関連する文書の上位セットを含んでいる過度に広範囲なクエリをユーザが入力するときに、クエリ・リファインメントは主に有用である。例えば、三菱ギャラン自動車の情報を欲しているユーザは、処理結果が自動車会社だけでなく多くのいろいろな三菱の会社を含むけれども、過度に広義のクエリ“三菱”を入力するかもしれない。従って、クエリを洗練することは望ましいであろう（ユーザの具体的な情報要求を割り出すための付加的な用語の前後関係の不足のために困難だけれども）。
【０００６】
しかしながら、正しい修正がクエリを拡張するはずである場合に、過度に特定のクエリをユーザが入力するとき、あるいは最高の結果がユーザの情報ニーズと無関係であるとき、クエリ・リファインメントは有用ではない。例えば、クエリ“三菱ギャラン情報”は用語“情報”のために、よくない結果（この場合、三菱ギャラン自動車についてのあまりに少なすぎる結果）を導き出すかもしれない。この場合、正しい修正は「三菱ギャラン」へクエリを拡張するはずである。従って、クエリ・リファインメントがいくつかの状態で働く間に、他のクエリ修正技術を使うことによってユーザの情報ニーズが最も満たされる状態は多数ある。
【０００７】
別のクエリ修正の方針は、同義語リスト又はユーザの見込みの情報ニーズをつかむためにクエリを拡張するシソーラスを使用する。しかしながら、クエリ・リファインメントと同じように、クエリの拡張はクエリを修正するために常に適切な方法であるとは限らないし、結果の質はクエリ用語の前後関係に非常に依存している。
【発明の開示】
【０００８】
情報検索システムは、それぞれがそれ自身のクエリ修正方針を実行する１つ以上の異なるクエリ・リバイザを備える、クエリ修正構造を含む。それぞれのクエリ・リバイザは、ユーザクエリの１つ以上の見込みの修正クエリを決定するために、ユーザクエリを評価する。修正サーバは、見込みの修正クエリを取得するために、クエリ・リバイザと相互に作用する。修正サーバはまた、それぞれの見込みの修正クエリのために、１組の調査結果を取得する情報検索システム内の検索エンジンと相互に作用する。修正サーバは、選択された修正クエリそれぞれのための検索結果のサブセットと共に、ユーザに提示された１つ以上の修正クエリを選ぶ。ユーザは、修正クエリのための検索結果の質を観察することが可能であり、その上、１の実施態様に従う修正クエリのための全ての検索結果を取得するために修正クエリの１つを選択することが可能である。
【０００９】
システムと方法は、他のユーザが過去に形作ったクエリのストリングの分析に基づき、ユーザの見込みの情報ニーズをよりいっそう正確につかむためのセションベースのユーザデータを使用する。これを達成するために、修正クエリは多くの個々のユーザセションから集められるデータに基づいて提供される。例えば、そのようなデータはクリックデータ、イクスプリシットユーザデータ、あるいはホバーデータが含まれるであろう。ホバーデータを使用しているユーザフィードバックの記述については、この参照より含まれる２００３年１２月３１日に提出された特許出願第１０／７４９，４４０号“ネットワークブライジングをアシストする方法及びシステム”を参照のこと。
【００１０】
１の実施態様として、クエリ・ランク・リバイザは、最初のクエリへの修正として、１以上の既知の高ランク付けされたクエリを提案する。初めに、１つのクエリランク（等級：序列）が全てのクエリに割り当てられる。クエリ・ランク・リバイザは、最も高くランク付けされたクエリを既知の高ランクのクエリ（ＫＨＲＱ）として識別するための、クエリとそれぞれのクエリランクのテーブルを生成する。ＫＨＲＱに修正される高い確率（可能性）を持つクエリは近くのクエリ（ＮＱ）として識別され、それぞれのＮＱから対応するＫＨＲＱへとポインタがストアされ、そしてそのＫＨＲＱとＮＱのクエリは索引付けられる。
【００１１】
所定のクエリのために、クエリ・ランク・リバイザは索引付けされたクエリに関して修正確率を決定する。次に、修正スコア（ＲＳ）は、索引付けされたクエリのための修正確率とクエリランクとを使って、それぞれの索引付けされたクエリを予測する。それから、最も高い修正スコアをもつ索引付けされたクエリが変更クエリとして取り出される。インデックスにストアされたポインタを使って、ＫＨＲＱである変更クエリは候補修正とＮＱである変更クエリに提供され、対応する既知の高ランクのクエリは候補修正として提供される。
【００１２】
本発明は、種々の図、ダイアグラム、技術情報について次に記載されている。上記図面は、本発明のさまざまな実施例を例示しただけである。当業者であれば、ここで説明する発明の本質から逸脱せずに、図解及び記述された階層構造、方法、機能について他の実施例を用いることが可能であることを、以下の説明から容易に理解するであろう。
【００１３】
【００１４】
【００１５】
【００１６】
【００１７】
【発明を実施するための最良の形態】
【００１８】
システムの概要
図１ａは、本発明の一実施例に基づくシステム１００を例示する。システム１００は、フロントエンドサーバ１０２、検索エンジン１０４と関連のコンテンツサーバ１０６、修正サーバ１０７、１つ以上のクエリ・リバイザ１０８を含む。動作中、ユーザはあらゆるタイプのコンピュータ機器、例えば実行中のブラウザアプリケーションやインターネット上で関連するプロトコル（例えば、ＴＣＰ／ＩＰとＨＴＴＰ）を通信するのに適した他のアプリケーション上で動作するネットワーク（図示しない例えばインターネット）上の従来のクライアント１１８を経てシステム１００にアクセスする。ただ１つのクライアント１１８が示されている間、システム１００は多くのクライアントで多数の並行セションを支援することができる。１つの実装で、システム１００は、高い能力をもつサーバクラスのコンピュータで動作し、そしてクライアント機器１１８はあらゆるタイプのコンピュータ機器であるかもしれない。サーバ及びクライアントコンピュータのハードウェア特徴の細部は当業者に良く知られており、ここでさらに記述されない。
【００１９】
フロントエンドサーバ１０２は、クライアント１１８によって提示された探索クエリを受信する責任がある。フロントエンドサーバ１０２は、探索クエリに基づき１組の検索結果を検索するためのクエリを求め、フロントエンドサーバ１０２へその結果を返すサーチエンジン１０４へそのクエリを提供する。サーチエンジン１０４は、ユーザの検索クエリに関連する多くの文書を選択するために、１つ以上のコンテンツサーバ１０６と通信を行う。コンテンツサーバ１０６は、異なったウェブサイトから索引付けられた（及び／又は検索した）多数の文書を記憶する。代わる代わる、あるいは並行して、コンテンツサーバ１０６は、種々のウェブサイトに記憶された文書のインデックスを記憶する。ここで“文書”は、あらゆるテキストの原文文書、コンピュータグラフィックのフォーマット、画像、ビデオ、オーディオ、マルチメディア、提示物、ウェブページ（例えばジャバスクリプトでの、組み込まれたハイパーリンクや他のメタデータ、及び／又はプログラム）などを含む、インデックス付け可能なコンテンツのあらゆる形式であると理解される。一実施例において、それぞれの索引付けられた文書は、文書リンク構造に基づき１つのページランクを割り当てられる。ページランクは、クエリ毎に独立した文書の重要性の尺度として役立つ。ページランクの典型的な形式は、この参照より開示に含まれる特許出願第６，２８５，９９９号に記述されている。サーチエンジン１０４は、文書の重要性（例えば、文書内の検索用語の場所や出現頻度）のクエリ毎に独立した１以上の信号は勿論のこと、その文書のページランク（及び／又は他のクエリ毎に独立した文書の重要性の尺度）にも基づいて、それぞれの文書に点数を割り当てる。
【００２０】
フロントエンドサーバ１０２はまた、修正サーバ１０７にクエリを提供する。修正サーバ１０７は、それぞれが異なるクエリ修正方法や１連の方法を実行する１以上のクエリ・リバイザ（reviser: 修正手段）１０８と連動する。一実施例において、クエリ・リバイザ１０８は、クエリ・ランク・リバイザ１０８ａを含む。修正サーバ１０７はそれぞれのリバイザ１０８にクエリを提供し、それぞれのリバイザ１０８からの応答内にある１つ以上の見込みの修正クエリ（修正サーバ１０７によってこの時点で採用されなかったことから、ここで‘見込みの’と呼ぶ）を獲得する。システム構造は、とりわけ多くの異なるクエリ・リバイザ１０８が使用されることを許可するように、そして新規にクエリ・リバイザ１０８（一般的なリバイザ１０８ｎで示されている）を将来望まれたときに付け加えることができるように明確に設計される。これはシステム１００に特別な柔軟性を与え、そしてまたカスタマイズして特定の対象ドメイン（例えば、薬、法律等のようなドメインに用いるリバイザ）、企業（内部情報検索システムのための、特定の事業分野あるいは企業のドメインが明確なリバイザ）、または異なる言語（例えば、特定の言語と方言のためのリバイザ）に適応させることができるようにする。
【００２１】
望ましくは、それぞれの修正クエリは、その修正がよい修正である確率、すなわちその修正クエリがオリジナルのクエリよりもユーザの情報ニーズにより関連する結果をもたらすであろう確率を表す信頼性尺度に関連付けられる。従って、それぞれの見込みの修正クエリは、Ｒが見込みの修正クエリであって、Ｃが修正クエリに関連付けられた信頼性尺度であるところの、組（Ｒｉ，Ｃｉ）によって表すことができる。一実施例において、これらの信頼性尺度は、それぞれのリバイザ１０８それぞれの修正方法に関してあらかじめ手作業で見積もられる。その尺度は、試験の下でのサンプルクエリと修正クエリの結果の分析から導き出すことができる。他の実施例において、１以上のリバイザ１０８は１以上のその見込みの修正クエリのために、動的に信頼性尺度を生成するかもしれない（例えば、処理実行時に）。信頼性尺度の割り当ては、他の機材（例えば、修正サーバ１０７）によって実行されるかもしれないし、そしてクエリ毎に独立したデータとクエリ毎に独立していないデータの両方が考慮されるかもしれない。
【００２２】
修正サーバ１０７は見込みの修正クエリの１以上（又は全て）を選び、これらを検索エンジン１０４に提供する。検索エンジン１０４は、通常のクエリと同じ方法で検索クエリを処理し、提出された修正クエリそれぞれの結果を修正サーバ１０７に提供する。修正サーバ１０７は、修正クエリの成果とオリジナルのクエリの成果との比較を含めて、修正クエリそれぞれの結果を評価する。下記に示すように、修正サーバ１０７は最も良い修正クエリ（又は少なくともオリジナルのクエリにうってつけである修正クエリ）であるとして１以上の修正クエリをその後選択することができる。
【００２３】
修正サーバ１０７は全ての見込みの修正クエリＲを受け取り、最も高い信頼性から最も低い信頼性までの順に、それらに関連付けられた信頼性尺度Ｃに従ってそれらをソートする。修正サーバ１０７は見込みの修正クエリのソートされた一覧表を通じて繰り返し、検索結果を取得するために、検索エンジン１０４へそれぞれの見込みの修正クエリを受け渡す。（もう１つの方法として、修正サーバ１０７は、例えば閾値以上の信頼性尺度である見込みの修正クエリの一部を最初に選択するかもしれない。）時として一番上の検索結果は、検索方法を実行している間に、あるいは信頼性尺度を評価している際に、検索サーバ１０７がそのように得られた検索結果を使うことができる場合に、すでに取り出されているかもしれない（例えば、リバイザ１０８ａ又は修正サーバ１０７によって）。
【００２４】
見込みの修正クエリ毎に、修正サーバ１０７は見込みの修正クエリを選択するのかそれを破棄するのかを決定する。その選択は、独自性とオリジナルのクエリの検索結果に関し両方共に、修正クエリのための一番上のＮ検索結果の評価によって決めることができる。一般的に、修正クエリは、オリジナルのクエリよりユーザの情報ニーズを正確に反映するより適当である検索結果を作成するべきである。要望どおり多かれ少なかれ結果は処理されるのだけれども、典型的にトップ１０の結果が評価される。
【００２５】
一実施例において、見込みのクエリは以下の条件が適用できるならば選択される。
【００２６】
i ）修正クエリは、少なくとも検索結果の最小番号を作成する。例えば、１にこのパラメータをセットすることは、検索結果がない全て（又は１つだけ）の修正を破棄するだろう。許容できる結果の最小番号の一般的な範囲は、１から１００である。
【００２７】
ii）修正クエリは、修正の一番上の結果で“新しい”結果の最小番号を作成する。１つの結果は、オリジナルのクエリ又は前もって選択された修正クエリの一番上の結果内に生じないときに“新しい”。例えば、２にこのパラメータをセットすることは、いくつかの前もって選択された修正クエリの一番上の結果内又はオリジナルのクエリの一番上の結果内に生じない、少なくとも２つの一番上の結果を持つそれぞれ選択された修正を要求する。この制約は、少なくとも修正の１つが有用であると分かる可能性を最大にして、選択された修正の中に、結果の相違があることを保証する。例えば、図３に示すように、それぞれの修正クエリのためのトップ３の結果３０４は、他の結果セットから識別可能である。これは、修正クエリにおおいに関連した検索結果の広範な概観をユーザに与える。
【００２８】
iii）修正クエリの最大番号は、まだ選択されていない。換言すれば、修正クエリの最大番号が既に選ばれていた場合は、そのとき全ての残りの修正クエリは破棄される。一実施例において、修正クエリの最大番号は４にセットされる。他の実施例において、修正クエリの最大番号は２と１０の間にセットされる。
【００２９】
前述の選択パラメータの結果は、修正クエリページ３００に含まれるであろう選択された修正クエリの１セットである。修正サーバ１０７はこのページにリンクを構築し、既に述べたようにして、このリンクをフロントエンドサーバ１０２へ提供する。修正サーバ１０７は、修正クエリページ３００上の修正クエリの順序と様式を決定する。修正クエリは、望ましくは信頼性尺度の順に載せられる（高い順から低い順に）。
【００３０】
フロントエンドサーバ１０２は、検索結果ページの中にクライアント１１８から送られた索引付けリンクを含める。ユーザはその結果、オリジナルのクエリのための検索結果の閲覧、あるいは修正クエリページへのリンクの選択、そしてそれによって選択された修正クエリとその関連結果をみることができる。
【００３１】
修正クエリの提示
図２は、クライアント１１８へ提供されたサンプル結果ページ２００を示す図である。この簡単な実施において、検索結果２００ページはこのクエリへ結果２０４と共に［sheets］のオリジナルのクエリ２０２を盛り込む。１組の修正クエリへのリンク２０６は、ページ２００の下部に盛り込まれる。ユーザはリンク２０６をクリックして、修正クエリのページにアクセスすることができる。図３に例のページ３００を示す。ここでは、修正クエリ［linens］，［bedding］，「bedsheets」のために、修正クエリリンク３０２．１，３０２．２そして３０２．３によって表されているように、上位３つの修正クエリが示されている。それぞれの修正クエリリンク３０２の下には、それらのクエリに関してトップ３の検索結果３０４がある。
【００３２】
オリジナル結果ページ２００から分離されたページ３００上に修正クエリを提供することには、様々な利点がある。最初に、表示エリアは限定的な資源であり、そして、修正クエリをそれら自身によってリストすることは（関連付けられた結果のプレビューなしで）、可能な限り、ユーザがそれらの結果との関連で修正クエリを見ないという理由であまり望ましくない。別のページ３００に修正クエリを掲載することによって、ユーザ自身が修正クエリを選択する前に、情報ニーズを最もよく満たすと思われるどちらかの修正クエリをユーザに選ばせることができるようにして、ユーザは最も良い修正クエリとそれらに関連した最高の結果を参照することができる。単一の（たとえ長くても）ページ上にオリジナルのクエリと修正クエリの結果の両方を含むことができるであろう間、このアプローチは全ての修正クエリを閲覧させるためにユーザにページを下にスクロールさせるか、ページの冒頭の目に見える部分を乱雑にするかのどちらかを必要とするであろう。その代わりに、図２と３に示された好ましい実施態様において、それぞれの修正クエリリンク３０２をクリックし、選択した修正クエリの全ての検索結果を入手し、ユーザはクエリ修正に対応する結果を参照することができる。多くの場合、このアプローチもまた、自動的に検索結果を取得するために修正されたクエリを使って、また自動的にユーザへそれらを提示すること（例えば、ユーザ選択や相互作用なしで）が望ましい。実施例中において、クエリ修正はクエリ・ランク・リバイザと併せて記述され、この方法の利点は明らかである。「Britney Spears」が高いクエリランクである理由で提案されているクエリであるが、ユーザは望んだ情報を取得しない。それで、選択のためにユーザに結果とクエリを表示することが助けになる。加えて、このアプローチは、どのようにしてよりよいクエリを生成するかをユーザに間接的に教示する付加的な利点を持っている。他の実施例において、修正サーバ１０７は、オリジナル結果ページ２００上で、例えば別個のウィンドウ内にあるいはオリジナル結果ページ２００内に、クエリ修正を強制的に示すことができる。
【００３３】
ユーザによりよい結果の理解を手助けするための修正についての付加的な情報（例えば、検索結果３０４）の表示方法もまた、メイン結果ページ２００上を使用することができる。これは、例えばスペリングを訂正する修正の場合と同様に、１つのとても高い品質の修正クエリ（または、とても高い品質の修正の１つの小さな番号）である場合に特に有用である。スペルが訂正済みの修正クエリは、例えば表題，ＵＲＬ，そしてスペル修正提案が良いものであるかどうかをユーザが決定するのに役立つ断片的なトップ結果の付加的な情報と共に、結果ページ２００に示されることができる。
【００３４】
他の実施例において、修正サーバ１０７は全てのクエリ修正を示すかどうかを決定するために、そしてもし示すならば、どのようにしてそれへ修正やリンクを目立つように掲載するかどうかを決定するために信頼性尺度を使用する。この実施例は、以下に論じられる。
【００３５】
クエリ修正
再び図１ａに戻って、クエリ・ランク・リバイザ１０８ａの一実施例はすぐに説明される。ランク・リバイザ１０８ａは、過去に他のユーザによって作成されたクエリから、修正の連鎖の解析に基づいてユーザの情報ニーズをよりよく獲得するかもしれない既知の高ランク付けされたクエリを提案するために、多くの適切な方法を使うことができる。一般的に、高ランク付けされたクエリは他のクエリに関連して高い頻度で現れるものであるが、その発生に関連して高い頻度で訂正されるものである。ユーザがただまれにそのようなクエリを修正するだけであることは、クエリにより提供された結果がユーザの情報ニーズに十分に一致することを示唆する。
【００３６】
一実施例において、高ランク付けされたクエリは次のように識別される。初めに、クエリ・ランク・リバイザ１０８ａはログファイル１１０に記憶されている全てのクエリへ１つのクエリランクを割り当てる。この中で使用されたクエリランクは、クエリ（ＱＦ）とそのクエリを含むユーザ満足度（ＵＳ）の発生頻度、例えばＱＦとＵＳの積すなわち（ＱＲ＝ＱＦ×ＵＳ）を使って定義される。一実施例において、ユーザ満足度は反比例の修正頻度（ＩＲＦ）として評価される。換言すれば、ユーザ満足度は修正頻度が減少するにつれて増大する。一実施例における修正頻度は、クエリが修正された回数をクエリ出現の合計個数で割った数として定義される。したがって、この実施例においてクエリランクは、まれに修正されるが、高くランク付けされたクエリは高い頻度を発生することを反映している、クエリ発生頻度‐反比例の修正頻度（ＱＦ‐ＩＲＦ）として再び定義される。
【００３７】
他の実施例において、ユーザ満足度はクエリの品質によって定義される。一実施例として、クエリのための品質スコア（点数）は、検索結果上のクリックの距離を測定したユーザのクリック動作データから推定される。品質スコアを定義するための１つのそのような方式は、この参照より開示に含まれる２００４年６月２８日付特許出願第１０／８７８，９２６号「相互関係の特徴の導出と使用のためのシステムと方法」に記述されているように、相互関係の特徴の使用である。品質スコア演算は、例えばログファイル１１０に記憶される。品質スコアは、検索結果の最初の選択例えば検索結果上の最初のクリック、の推定された持続時間に基づいている。与えられたクリックの持続時間は、検索結果上で発生した最初とそれに続く選択の時刻のときに時刻から、例えばログファイル１１０に他のユーザセションクエリデータと共に記憶される時刻から推定される。点数付けは、ユーザが検索結果上で選択／クリックしていない場合の検索結果をゼロのスコアに含み、そして１の品質スコアに接近するより長いクリックと共に、最初のクリックとそれに続くクリックとの間の時間にあてはまるＳ曲線に沿って続けられる。一実施例において、曲線のための数式は1/（1＋ｅ-(X-40s)/10s）、Ｘはクリックの間の時間であり、0.1の品質スコアに対応する変曲点は２０秒であり、0.5の品質スコアに対応するのは４０秒であり、0.9の品質スコアに対応するのは６０秒である。他の実施例において、異なる曲線がユーザ満足度を示すと思われるクリック時間に従って使用される。例えば、右へ曲線を引き伸ばすことは、短期間クリックとクリックが全くない間の識別を減ずることを犠牲にして、とても長い持続時間でクリックに報いるよりよい仕事をするだろう。関係ないコンテンツ、例えばバナー広告のクリックはクリック解析から除外される。他の実施例において、ただ最初だけでなくてクエリに対する全ての結果クリックが集められる。したがって、この実施例において、クエリランクは品質（Ｑ）の時間を計るクエリ発生頻度（ＱＦ）として定義される。
【００３８】
クエリ出現頻度（ＱＦ）は、例えば一実施例によれば時間当たりの頻度のように、単位時間当たりの頻度として定義される。したがって、クエリ出現頻度と反比例の文書頻度又は品質の増加として、クエリランクは１に向かって増加する。他の実施例において、クエリ出現頻度は異なった方法で定義されるかもしれない。
【００３９】
次に、クエリ・ランク・リバイザ１０８ａは、クエリとそれぞれのクエリランクのテーブルを作成する。このデータから、クエリ・ランク・リバイザ１０８ａは既知の高ランク付けされたクエリ（ＫＨＲＱ）として、全てのクエリの部分集合を認知する。既知の高ランク付けされたクエリは、上記のように、またクエリテーブルにリストされているように、高いクエリランクを持つことが知られているクエリである。他の実施例において、既知の高ランク付けされたクエリはトップＸクエリ、例えばトップ５，０００のクエリとして定義される。
【００４０】
クエリ・ランク・リバイザ１０８ａはそれから、ＮＱとＫＨＲＱとの間で類似度によって測られたとして、ＫＨＲＱへ強い修正確率（ＰＲ）を持つクエリである、近くのクエリ（ＮＱ）を認知する。類似度は、意味に関する類似度、構文上の類似度、行動の類似度、あるいはそのどんな組み合わせに基づいてでも決定され得る。一実施例において、類似度は行動の類似度である。他の実施例において、類似度がクエリ間において、例えばそれぞれのクエリのために単語群の中で語句の類似点及び／又は重複するような要素を考慮すると、意味に関する類似度を含む。さらに他の実施例において、類似度はクエリ内において、例えば編集距離、用語の重複、あるいは情報修正に一般的に使われる他の技術のような要素を考慮すると、構文上の類似度を含む。さらに他の実施例において、類似度は意味と構文上の類似度の両方を含む。一実施例において、スコアリング類似度は、より類似したクエリが１のスコアに接近するように、０と１との間であてがわれた類似度スコアを含む。例えば、小さな用語の重複（例えば「When Harry Met Sally」対「Metropolitan Life」）を持つクエリは近い類似度スコア（例えば０．１５）を持つのに対して、単語が１つの文字（例えば、「Brittney Spears」対「「Britney Spears」）によってつづりが間違われたクエリは高い類似度スコア（例えば０．９５）を持つ。類似度のより素晴らしいタイプが使われる実施例において、パラメータ化された組み合わせ関数、例えば加重された合計が、システムの断定的な正確さを最大限に増加するパラメータとして使用される。
【００４１】
それで、一実施例において、既知の高ランク付けされたクエリの近くのクエリの修正確率（ＰＲ）は、ＫＨＲＱへＮＱの行動の類似性（ＢＳ）である。それぞれがログファイル１１０データ、すなわちＰＲ（ＮＱ，ＫＨＲＱ）＝ＢＳ（ＮＱ，ＫＨＲＱ）＝Ｒ（ＮＱ，ＫＨＲＱ）／ＱＦ（ＮＱ）から決定される近くのクエリ出現頻度を超える既知の高ランク付けされたクエリ（Ｒ（ＮＱ，ＫＨＲＱ））へ修正（Ｒ）されるであろう。近くのクエリが多重ＫＨＲＱへ修正されるごとの記録を持っているかもしれないときに、この演算はそれぞれのＫＨＲＱに対して別々に行われる。一旦ＰＲが決定されると、統計学的に重要なＰＲを持つクエリは、近くのクエリとしてのそれらの格付けを維持し、より低いＰＲを持つクエリは他のクエリ（ＯＱ）として分類される。全てのＫＨＲＱとＮＱは、それぞれのＮＱからそれぞれのＫＨＲＱのそれぞれまでポインタと共に、インデックス（索引）に記憶される。インデックス内のＫＨＲＱとＮＱは、集合的に索引付けされたクエリ（ＩＱ：indexed query）と呼ばれる、それぞれの索引付けされたクエリのためのＰＲもまたインデックスに記憶される。
【００４２】
図４は、既知の高ランク付けされたクエリ（ＫＨＲＱ）、近くのクエリ（ＮＱ）と、他のクエリ（ＯＱ）の模範的なグラフ化されたトポロジーを示す。図示のように、高ランク付けされたクエリから離れたクエリの１つのリンクは、通常近くのクエリとして分類される。しかしながら、既知の高ランク付けされたクエリからより近くのクエリは、例えば取るに足りないＰＲ（ＫＨＲＱ）だけを持つ可能性が高い他のクエリとして分類される可能性がより高い。図示のように、ＫＨＲＱからの距離が増加するにつれて、ＰＲは減少する。一実施例において、高ランク付けされたクエリと他のクエリとの間の経路の距離は、確率尺度について直接考慮に入れられる。
【００４３】
次に、上述された終端プロセスの継続時又は処理実行時のどちらかにおいて、クエリ・ランク・リバイザ１０８ａはＧＱとＩＱとの間の類似度によって測られるように、それぞれの索引付けされたクエリ（ＩＱ）へ所定のクエリ（ＧＱ）の修正確率を測る。ＰＲについて上述したように、ＲＰは意味に関する類似度、構文上の類似度、行動の類似度、あるいはそのどんな組み合わせに基づいてでも決定され得る。ある場合には、ＲＰはＰＲと同じ方法で計算され、またある場合には、ＲＰは異なる演算を使う。ここに、ＰＲは、ＰＲがＫＨＲＱへＮＱの修正確率を計算するために用いられる、ＫＨＲＱへＧＱの修正確率を評価するために用いられる。終端プロセスとして、ＲＰはログファイル１１０に記憶したように、それぞれのクエリのために計算される。フロントエンドプロセスとして、ＲＰは例えばクライアント１１８を経由してユーザによって入力されたように、１つのクエリのために計算される。
【００４４】
一実施例において、ＮＱ（ＲＰ（ＧＱ，ＮＱ））へ所定のクエリのＰＲは、行動の、意味に関する、そして構文上のＮＱへＧＱの類似度である。既知の高ランク付けされたクエリ（ＲＰ（ＧＱ，ＫＨＲＱ））へ所定のクエリのＲＰは、直接的にそして間接的にも計算される。直接の部分は、標準的なＰＲ演算を用いる。間接的な部分は、ＫＨＲＱへのポインタを持つＮＱの全体にわたる、上述したようなＲＰ（ＧＱ，ＮＱ）のプロダクトのＫＨＲＱへのＮＱのＲＰの合計として計算される。したがって、ＫＨＲＱへのＧＱのＲＰはＫＨＲＱ、すなわちＲＰ（ＧＱ，ＫＨＲＱ）＝ＲＰ（ＧＱ，ＫＨＲＱ）＋ΣNQs［ＲＰ（ＧＱ，ＮＱ）×ＰＲ（ＮＱ，ＫＨＲＱ）］のために、すべてのＮＱｓの間の関係に関して、直接的にも間接的にも計算される。結果として、ＮＱの確率がＫＨＲＱ，下位のＲＰへあまり修正されそうにない。例えば、ＲＰ（ＧＱ，ＫＨＲＱ）の間接的な特徴が上記の方程式を必要とするであろう状態の例が、図５を参照して目にすることができる。例えば、ＧＱ５０５のＲＰのためにＫＨＲＱ５１０へ、上記の方程式の後半は、ＮＱ１５１５，ＮＱ２５２０，ＮＱ３５２５，ＮＱ４５３０の演算の合計であるだろう。
【００４５】
次に、クエリ・ランク・リバイザ１０８ａは、索引付けされたクエリ（所定のクエリに関して）と索引付けされたクエリのためのクエリランクすなわちＲＳ（ＩＱ）＝（ＧＱ，ＩＱ）×ＱＲ（ＩＱ）のためのＲＰのプロダクトとして、それぞれの索引付けされたクエリのために修正スコア（ＲＳ）を計算する。最も高い修正スコアを持つ索引付けされたクエリは、代替クエリ（ＡＱ）として検索される。一実施例において、トップ１０の修正スコアを持つ索引付けされたクエリが検索して取り出される。他の実施例において、トップ１００の修正スコアを持つ索引付けされたクエリが検索して取り出される。代替クエリのリストが一度検索されると、既知の高ランク付けされたクエリである代替クエリは候補修正として提供される。近くのクエリである代替クエリのために、対応する既知の高ランク付けされたクエリはインデックスに記憶されたポインタを使って、候補修正として提供される。
【００４６】
上述したように、それぞれの候補修正は、修正がよい修正である確率に相当する信頼性尺度と関連付けできる。クエリ・ランク・リバイザ１０８ａの場合は、候補修正のための代替クエリの修正スコアがそのクエリのための信頼性尺度として用いられる。
【００４７】
その上、これあるいは他のリバイザ１０８によって既に修正されているクエリは、クエリ・ランク・リバイザ１０８ａによってさらに修正されることができる。
【００４８】
クエリ・ランク・リバイザ１０８ａを使っての既知の高ランク付けされたクエリを提案することについての例が続く。ユーザによって入力された最初のクエリは、［BBQ Skewers］４０５である。この例で、ユーザはバーベキュー串についての情報に興味がある。クエリ・ランク・リバイザ１０８ａは、索引付けされたクエリに関してクエリの修正確率を計算するか又は検索する。この例のために再び図４を参照すると、４つの索引付けされたクエリが索引付けされたクエリとして用いられる。［Britney Spears］４１０，ＫＨＲＱ，そしてそのＮＱの１つ，［Ｂ Spears］４２０，そして［Williams‐Sonoma］４３０，ＫＨＲＱ，そしてそのＮＱの１つ，［Wooden Skewers］４４０。ＮＱのために、そのそれぞれのＫＨＲＱ（ＰＲ）に修正することについてのそれぞれの確率は、インデックスから検索される。索引付けされたクエリ４１０‐４４０の修正確率は、
ＲＰ（［BBQ Skewers］，［Britney Spears］）＝0.11
ＲＰ（［BBQ Skewers］，［B Spears］）＝0.3（Ｓ）×0.8（ＰＲ）＝0.24
ＲＰ（［BBQ Skewers］，［William Sonoma］）＝0.05
ＲＰ（［BBQ Skewers］，［Wooden Skewers］）＝0.95（Ｓ）×0.3（ＰＲ）＝0.285
【００４９】
したがって、ＫＨＲＱの両方ともが［BBQ Skewers］に関してかなり低い修正確率（ＲＰ）を持つ。［B Spears］もまた比較的に低いＲＰを持つが、［Britney Spears］のために比較的に高いＰＲを持つ。［Wooden Skewers］は［BBQ Skewers］のために高いＲＰを持つが、ＫＨＲＱ［William Sonoma］に関して低いＰＲを持つ。
【００５０】
次に、クエリ・ランク・リバイザ１０８ａは、上記したのとそれぞれの索引付けされたクエリ４１０‐４４０、すなわちＲＳ（ＩＱ）＝Ｓ（ＧＱ，ＩＱ）×ＱＲ（ＩＱ）のためのクエリランクから修正確率の関数として、索引付けされたクエリあたりの修正スコア（ＲＳ）を検出する。修正スコアは次のように計算される。
ＲＳ（［Britney Spears］）＝0.11×0.93ＱＲ（［Britney Spears］）＝0.1023
ＲＳ（［B Spears］）＝0.24×0.35ＱＲ（［B Spears］）＝0.084
ＲＳ（［William Sonoma］）＝0.05×0.75ＱＲ（［William Sonoma］）＝0.0375
ＲＳ（［Wooden Skewers］）＝0.285×0.36ＱＲ（［Wooden Skewers］）＝0.1026
【００５１】
したがって、［B Spears］は［BBQ Skewers］に２番目に類似しているけれども、それは低いクエリランクを持ち、そして最終的には低いＲＳになる。その上、［William Sonoma］は高いクエリランクを持つが、そのグループの最も低いＲＳを持つあまりに低いＲＰである。索引付けされたクエリ４１０-４４０のうち２つの最も高いＲＳは、とても高いクエリランクと低いＲＰを持つ［Britney Spears］と、low-tomediumなクエリランクを持つがグループのために最も高いＲＰを持つ［Wooden Skewers］である。この例のために、修正スコアのトップ５０パーセントが代替クエリ（ＡＱｓ）として検索されると仮定する。そのために、［Britney Spears］と［Wooden Skewers］は代替クエリとして検索される。
【００５２】
ＫＨＲＱである［Britney Spears］は、候補修正クエリとして返される。その上、代替クエリ［Wooden Skewers］のためのＫＨＲＱである［William Sonoma］もまた、候補修正クエリとして返される。さらに、候補修正クエリのための信頼性尺度、すなわち関連付けられた代替クエリの修正スコアは、ユーザへ候補修正を提供するか否かを決定するのに使われるから、ユーザは最終的に［William Sonoma］だけを見るかもしれない。結果として、ユーザはユーザが探していた項目（Wooden Skewers）を売る提案されたクエリ［William Sonoma］で終わる。
【００５３】
処理実行時での修正信頼性尺度の発生
今回図１ｂを参照しながら、この発明に係る情報検索システムの他の実施例を示す。既に記述された図１ａの要素に加えて、セション・トラッカー（追跡器）１１４とリバイザ信頼性評価器１１２がある。上述したように、クエリ・リバイザ１０８は、信頼性尺度に修正サーバ１０７へ提供する１つ以上の修正クエリを提供するかもしれない。修正サーバ１０７は、考えられうる修正クエリを修正クエリページ３００上に包括のために選択する決定を行うために、信頼性尺度を使う。一実施例において、与えられたオリジナルクエリに関して選択されている修正クエリの中で少なくともこれまでのユーザの行動の一部に基づいて、信頼性尺度は処理実行時に導き出される。
【００５４】
図１ｂの実施例において、フロントエンドサーバ１０２は、オリジナルクエリと修正クエリ情報と一緒に、セション・トラッカー１１４にユーザのクリックを介した行動を提供する。セション・トラッカー１１４は、修正クエリの品質をかたどるためのオリジナルクエリと修正クエリの種々の特徴と一緒に、ユーザによってアクセスされたクエリ修正リンク３０２、それぞれの修正クエリに関連した結果に関連するそれぞれのユーザクエリを記憶するログファイル１１０を保存する。含めることが可能な記憶された情報は、例えば
【００５５】
オリジナルクエリのために、
・オリジナルクエリそれ自身
・オリジナルクエリ中のそれぞれの言葉
・オリジナルクエリの長さ
・オリジナルクエリの話題群
・オリジナルクエリのための情報検索スコア、そして
・オリジナルクエリのための結果の番号
【００５６】
修正クエリのために、
・修正クエリそれ自身
・修正クエリ中のそれぞれの言葉
・それを生み出す検索技術の識別番号
・修正クエリの長さ
・修正クエリに関連した話題群
・トップ検索結果のための情報検索スコア（例えばページランク）
・修正クエリに供給する結果の番号
・修正クエリリンク３０２上のクリックの距離、そして
・修正クエリ結果３０４上のクリックの距離
【００５７】
クエリのための話題群は、適当な話題識別方法を使って識別される。１つの適当な方法は、この参照より含まれる２００３年９月３０日に提出された特許出願第１０／６７６，５７１号“関連した言葉に基づいて文書を特徴づけるための方法と装置”に記述されている。
【００５８】
リバイザ信頼性評価器１１２は、所定のクエリのための成功した修正である修正クエリの見込みを評価するために使われるクエリと修正クエリの特徴に基づく１組のルールを発生するための予測モデル、例えば多重の、論理回帰モデルを使ってログファイル１１０を解析する。１つの適当な回帰モデルは、この参照より含まれる２００３年１２月１５日に提出された特許出願第１０／７３４，５８４号“大規模計算機学習システムと方法”に記述されている。リバイザ信頼性評価器１１２は、ある特定の動作、例えば修正クエリリンク３０２上でのユーザによる長いクリックが、ユーザのオリジナルの情報ニーズの正確な表現であるとして、ユーザがその修正に満足していることを示すことを前提として作動する。ユーザがページを通して若干の期間、例えば最低６０秒間、クリックした状態のままとなっているときに、長いクリックが生じたと判断されうる。修正クエリリンク３０２上のクリックの距離から、リバイザ信頼性評価器１１２は、修正クエリとオリジナルクエリの種々の特徴を与えられた長いクリックの見込みを予測するように、予測モデルを訓練することができる。長いクリックの高く予測された見込みを持っている修正クエリは、関連したオリジナルクエリのために、より良い（すなわち、いっそう成功した）修正であると考えられる。
【００５９】
予測モデルの一実施例において、信頼性評価器１１２は修正クエリに関連する特徴を選択し、ログファイルからクリックデータのようなユーザデータを集めて、特徴とユーザデータを使ってルールを定式化し、予測モデルにそのルールを加える。その上、信頼性評価器１１２は、ユーザデータを使って追加のルールを定式化することができ、そして選択的にモデルへ追加のルールを加える。
【００６０】
処理実行時に、修正サーバ１０７はリバイザ信頼性評価器１１２に、オリジナルクエリと種々のクエリ・リバイザ１０８から受け取った修正クエリのそれぞれを提供する。リバイザ信頼性評価器１１２はオリジナルクエリと修正クエリを、前に言及された信頼性尺度として役立つ予測尺度を獲得するための予測モデルに適用する。代わりに、それぞれのクエリ・リバイザ１０８が予測尺度を獲得し、そして次にこれらの値を修正サーバ１０７に戻すよう、直接リバイザ信頼性評価器１１２を呼び出すことができる。描写された実施例は、別個のモジュールとしてリバイザ信頼性評価器１１２を示すけれども、修正サーバ１０７が代わりに信頼性評価機能を提供するかもしれない。どちらの場合も、修正サーバ１０７はユーザに見せられるであろう修正クエリを選択し配列するために、上記のように信頼性尺度を使う。
【００６１】
一実施例において、修正サーバ１０７か仮にもクエリ修正を示すべきかどうか、そしてもしそうであるならば、どれくらい目立つようにして修正やリンクをそこへ配置するべきかを決定するために、信頼性尺度を使う。そうするために、修正サーバ１０７は、前に述べた最初の信頼性尺度か、上述した動的に生成された信頼性尺度のどちらかを使うであろう。例えば、もし最も良い信頼性尺度がしきい値の値以下に下がるならば、これは潜在的な候補修正のいずれも非常に良くないことを示すことができる。この場合には、オリジナル結果ページ２００の修正がなされない。他方、もし１つ以上の修正クエリがもう１つのしきい値の値以上の非常に高い信頼性尺度をもっているならば、修正サーバ１０７はオリジナル結果ページ２００上にとても目立つように、例えばページの最上部の近くで特殊の書体で、あるいは何か他の目立つ位置に示されるように、クエリ修正あるいはリンクを修正クエリページ３００へ強制することができる。もし、信頼性尺度が２つのしきい値の間であるならば、そのとき修正クエリページ３００へのリンクはそれ程目立たない位置（例えばリンク２０６で示されるような、例えば検索結果ページ２００の終わりに）置かれることができる。一実施例において、ユーザへ表示するかどうかあるいはどこに表示するかは、オリジナルクエリを用いたユーザの不満の一部に基づいている。例えば、ゼロや非常に少ない結果、あるいは低い情報修正スコアに基づいている。
【００６２】
上述した方法の手順は、並列に（例えば、クエリ修正に対して結果を得ることと、クエリ修正のために信頼性尺度を計算すること）実行されうるし、及び／又は（例えば、クエリ・リバイザから多重のクエリ修正を受け取ること、その場その場でクエリ修正の並べられたリストを構成すること、全てのクエリ修正を受け取ることよりむしろそれからのクエリ修正のリストを並べかえることに）介在されうる。さらに、上記実施例はクライアント／サーバ検索システムでの環境で記述されているけれども、この発明はその上スタンドアロンマシン（例えばスタンドアロンＰＣ）の部分として実装されうる。これは、（例えばグーグルデスクトップ検索のようなデスクトップ検索アプリケーションの環境で）有用でありうる。
【００６３】
この発明は、１つの可能な実施例に関して詳細な内容について記載されている。当業者は、この発明が他の実施例で実践されるかもしれないことを理解するでしょう。最初に、機器の特定の名前、表現の用語化、その特性、データ階層構造、あるいは他のいかなるプログラミングや機構的な特徴は必須あるいは重要でなく、そして発明を実行するメカニズムやその特徴が異なる名前、フォーマット、あるいはプロトコルをもつかもしれません。さらに、システムはハードウェアとソフトウェアとの組み合わせによって、説明されているように、あるいはもっぱらハードウェア要素内で実行されるかもしれません。また、ここに記述された種々のシステム構成要素間の相関性の特定部分は単に模範的にすぎず、強制的でなく、単一システム構成要素によって実行された機能がその代わりに多重の構成要素によって実行されるかもしれないし、多重の構成要素によって実行された機能がその代わりに単一の構成要素によって実行されるかもしれません。
【００６４】
上記記述の一部分は、アルゴリズムと情報操作の象徴的な説明の点に関して、この発明の特徴を示す。これらのアルゴリズム的な記述と説明は、他の当業者へ彼らの作品の内容を最も効果的に伝えるために、データ処理当業者によって使われる手段である。これらの動作は機能的にあるいは論理的に記述されるとおり、コンピュータプログラムによって実行されると理解される。さらに、それはまた、普遍性の喪失なしで、モジュールとしてあるいは関数の名前によって動作のこれらの取り決めに言及する時には都合がよいと分かる。
【００６５】
上記検討から明らかなように特に明白な検討がない限り、明細書本文を通じて記述された動作と方法は、コンピュータシステム、あるいはコンピュータシステムメモリやレジスタあるいは他のそのような情報記憶装置、伝達装置、あるいは表示装置内で物理的（電気的）な量として表されるデータを操作し変形する、類似の電気的演算素子であることが理解される。このようなコンピュータシステムに内在するハードウェアの詳細な説明は、この情報がコンピュータエンジニアリングの当業者に一般的に知られていることから、ここでは提供されない。
【００６６】
この発明の確かな特徴は、アルゴリズムの形式でここに記述された方法の手順と命令を含む。この発明の動作手順と命令は、ソフトウェア、ファームウェア、ありはハードウェアで実施されることができ、そしてソフトウェアで実施した場合には、リアルタイムネットワークオペレーティングシステムにより用いられる異なるプラットフォームから、常駐して操作されるためにダウンロードされることが指摘されるべきである。
【００６７】
この発明の確かな特徴は、単一のあるいは１つだけの例について記述された。しかしながら、この発明の動作がこの点について限定的でないことは理解される。したがって、１つだけの要素や構成要素への全ての引用は、同様に複数のそのような構成要素についても参照すると解釈されるべきである。同じように、“ａ”，“ａｎ”，“ｏｒ”,あるいは“ｔｈｅ”への引用は、もし明白に規定された別のやり方で表現されていなければ、複数個（pluralities）の引用を含むと解釈されるべきである。最終的に、用語“複数（plurality）”の使用は、検討中のこの発明の一部分にふさわしく、無限のあるいはさもなければ過度な項目の数の範囲にわたるときに、２つ以上の実在物、データの項目、またはその種のほかのものが属することが意味される。
【００６８】
この発明はまた、この点でオペレーションを実行する装置に関連がある。この装置は、必要とされる目的で特別に組み立てられるかもしれないし、あるいは選択的に作動される、又はコンピュータによってアクセスされうる読み取り可能な媒体により構成が変更される、一般的な目的のコンピュータを意味するかもしれない。このようなコンピュータプログラムは限定的ではないが、それぞれがコンピュータシステムバスに連結された、例えばフロッピーディスクを含むあらゆるタイプのディスク、光学式ディスク、CD-ROM、磁性-光学式ディスク、リードオンリーメモリ（ROM）、ランダムアクセスメモリ（RAM）、EPROM、EEPROM、磁性あるいは光カード、電気的な命令を記憶することに適したあらゆるタイプのメディアのような、コンピュータが読み取り可能な記憶媒体に記憶されるかもしれない。集積回路設計と映像コーデックの当業者は、この発明が、用途特化集積回路（ASles）を含む、上記機能的であり構造的な記載に基づいた種々のタイプの集積回路で容易に造りあげられることを理解する。さらに、この発明は種々のタイプの映像コーディング装置に組み込まれるかもしれない。
【００６９】
ここに示されたアルゴリズムと動作は、どの特定のコンピュータや他の装置と本質的に関連付けられない。様々な一般的な目的のシステムもやはりここの教示を踏まえてプログラムで用いられるかもしれない、あるいは必要とされた方法手順を実行するためのより専門の装置を組み立てるほうが都合がよいとわかるかもしれない。必要とされるこれらのシステムの多様性の仕組みは、同等の変形物に従って当業者に明白であろう。さらに、この発明は特定のプログラミング言語に関連付けられて記述されない。プログラミング言語の種類はここに記述されたようなこの発明の教示を実装するのに用いられるかもしれないこと、そして特定の言語へのどんな言及でも実施要件の開示とこの発明の最良の形態が規定されていることが分かる。
【００７０】
最後に、明細書に用いられた言語は読みやすさと教育の目的のために主に選択されること、そして発明の主題を描写する又は制限するために選択されなかったかもしれないことは指摘されるべきである。したがって、この発明の開示が説明に役立つものであることが意図されるが、発明の目的を制限するものでない。
【図面の簡単な説明】
【００７１】
【図１】本発明の一実施例に係るクエリ修正を提供する情報検索システムの一実施例を示すシステムダイアグラムである。
【図２】この発明の一実施例に係るオリジナルユーザクエリのための見本の結果ページの説明図である。
【図３】この発明の一実施例に係る見本の修正クエリページの説明図である。
【図４】この発明の一実施例に係るグラフ化されたクエリのトポロジーを示す。
【図５】この発明の他の実施例に係るグラフ化されたクエリのトポロジーを示す。
【図１ａ】
2008535090.tif 000003
【図１ｂ】
2008535090.tif 000004
【図２】
2008535090.tif 000005
【図３】
2008535090.tif 000006
【図４】
2008535090.tif 000007
【図５】
2008535090.tif 000008
【国際調査報告】
2008535090.tif 000009