多数のクエリー修正モデルの統合
【課題】ユーザクエリーを修正するためのシステムアーキテクチャを提供する。
【解決手段】情報検索システム１００は、ユーザから最初のクエリーを受信し、これに対応する複数の修正クエリーを生成する。最初のクエリーと修正クエリーとからなる複数のクエリ対のそれぞれについて、発生頻度を計算する。各クエリー対の発生頻度とは１以上のユーザーセッションにおける最初のクエリーの発生回数に対する修正クエリーの発生回数の比である。複数のクエリー対の各クエリー対毎に、品質得点の改善分を計算する。品質得点の改善分は、該クエリー対内の前記最初のクエリーに関するクリック行動データに対比して、該クエリー対内の前記修正クエリーに関するクリック行動データから引き出される。
【解決手段】情報検索システム１００は、ユーザから最初のクエリーを受信し、これに対応する複数の修正クエリーを生成する。最初のクエリーと修正クエリーとからなる複数のクエリ対のそれぞれについて、発生頻度を計算する。各クエリー対の発生頻度とは１以上のユーザーセッションにおける最初のクエリーの発生回数に対する修正クエリーの発生回数の比である。複数のクエリー対の各クエリー対毎に、品質得点の改善分を計算する。品質得点の改善分は、該クエリー対内の前記最初のクエリーに関するクリック行動データに対比して、該クエリー対内の前記修正クエリーに関するクリック行動データから引き出される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、情報検索システムに関し、より詳細には、ユーザークエリーを修正するためのシステムアーキテクチャに関する。
【０００２】
関連出願の相互参照
本出願は以下に関連し、それぞれを引用して本明細書に組み込む。
・２００３年９月２２日出願の米国特許出願第１０／６６８，７２１号、発明の名称「検索クエリー絞り込みを提供するためのシステムおよび方法」。
・２００３年９月３０日出願の米国特許出願第１０／６７６，５７１号、発明の名称「関連ワードのクラスタに基づいて文書を特徴付けるための方法および装置」。
・２００３年１２月１５日出願の米国特許出願第１０／７３４，５８４号、発明の名称「大規模マシン学習システムおよび方法」。
・２００４年６月２８日出願の米国特許出願第１０／８７８，９２６号、発明の名称「相互作用プロファイルを導出し、使用するためのシステムおよび方法」。
・２００４年７月２６日出願の米国特許出願第１０／９００，０２１号、発明の名称「情報検索システムにおけるフレーズ識別」。
・２００５年３月２８日出願の米国特許出願第１１／ｘｘｘ，ｘｘｘ号、発明の名称「重要性が希薄なクエリー用語の決定」。
・２００５年３月３０日出願の米国特許出願第１１／ｘｘｘ，ｘｘｘ号、発明の名称「クエリー文脈内のクエリー用語の類語決定」。および、
・米国特許第６，２８５，９９９号。
【背景技術】
【０００３】
インターネット検索エンジンにより具体化されているような情報検索システムは、一般に、ユーザークエリーに概ね関連する文書を迅速に提供できる。検索エンジンは、文書間および用語間の結び付きと併せて、用語および文書の出現頻度に各種統計的尺度を用いて、クエリーに対する文書の関連性を決定できる。大部分の検索エンジン設計の基底をなす主要な技術的仮定は、ユーザークエリーが、ユーザが所望する情報目標を正確に表しているということである。
【０００４】
現実には、ユーザが有効なクエリーを考えるのは困難なのが普通である。単一のクエリーでは所望の結果をもたらさないことが多いので、ユーザは、同一の話題について幾つかの異なるクエリーを入力することが多い。これら多数のクエリーは、クエリー用語や推測企業名の範囲または特異性の変形、ワード順序やワード数の変形等を含むのが普通である。クエリーをうまく修正するよう幅広く変化させる能力を有している様々なユーザ達がいるので、クエリー修正を自動化した各種の方法がこれまでに提案されている。
【０００５】
ごく普通には、クエリー絞り込みを通じて、より一般的なクエリーから、より正確な（すなわちより狭い）クエリーを自動生成する。その上位検索結果がユーザの情報必要性に関連する文書の上位セット（上位集合）を含む、範囲が広すぎるクエリーをユーザが入力する場合、クエリー絞り込み法は最も有効である。例えば、三菱ギャラン自動車に関する情報を求めるユーザが、自動車会社だけでなく多くの異なる三菱企業を検索結果が含む広すぎるクエリー「三菱」を、入力するかもしれない。従って、クエリーを絞り込みすることが望ましい（ユーザの特定情報の必要性を決定するのは、追加文脈欠如によりここでは困難であるが）。
【０００６】
しかし、正しい修正法がクエリー範囲を広げる場合において具体的過ぎるクエリーをユーザが入力する場合、または上位結果がユーザの情報必要性に無関連である場合は、クエリー絞り込み法は有効ではない。例えば、クエリー「三菱ギャラン情報」は、用語「情報」のために貧弱な結果をもたらすかもしれない（この場合には、三菱ギャラン自動車についての結果はほとんどない）。この場合、正しい修正はクエリー範囲を「三菱ギャラン」へ広げることである。従って、クエリー絞り込み法は幾つかの状況では作用するが、他のクエリー修正技法を用いることにより、ユーザの情報必要性が最も満たされる状況が、非常に多く存在する。
【０００７】
別のクエリー修正戦略は、類義語リストつまりシソーラスを用いてクエリーを拡張し、ユーザの潜在的情報必要性を取得することである。しかし、クエリー絞り込み法と同様に、クエリー拡張法が、常にクエリー修正の適切な方法であるとは限らず、結果の品質はクエリー用語の文脈に大きく依存する。
【０００８】
一つのクエリー修正技法だけでは、あらゆる事例で所望する結果を提供できないので、幾つかの異なるクエリー修正方法（つまり戦略）を提供する方法論を持つことが望ましい。
【発明の概要】
【０００９】
情報検索システムは、自己のクエリー修正戦略をそれぞれが実施する幾つかの異なるクエリー修正手段を提供する、クエリー修正アーキテクチャを含む。それぞれのクエリー修正手段は、ユーザクエリーを評価して、ユーザクエリーの一つ以上の潜在的修正クエリーを決定する。修正サーバは、クエリー修正手段と相互交流して潜在的修正クエリーを得る。修正サーバは、情報検索システム内の検索エンジンとも相互交流して、潜在的修正クエリー毎に一組の検索結果を得る。修正サーバは、ユーザへ提示するために修正クエリーの内の一つ以上を選定し、選定した修正クエリー毎に検索結果のサブセットを添える。従って、ユーザは修正クエリーに対する検索結果の品質を観察でき、修正クエリーの内の一つを選択して、その修正クエリーに対する検索結果の全セットを得ることができる。
【００１０】
次に、各種の図、ダイヤグラム、および技術情報と関連させて本発明を説明する。図は、本発明の多様な実施の形態を、説明だけを目的として示す。当該分野の技術者には言うまでもなく、以下の説明から、図示し、かつ説明する構造、方法、および機能の代替の実施の形態は、本発明の原理から逸脱することなく利用できる。
【図面の簡単な説明】
【００１１】
【図１ａ】クエリー修正を提供する情報検索システムの実施の形態の全体システム図である。
【００１２】
【図１ｂ】代替の情報検索システムの全体システム図である。
【００１３】
【図２】元のユーザクエリーへのサンプル結果ページの図である。
【００１４】
【図３】サンプルの修正クエリーページの図である。
【発明を実施するための形態】
【００１５】
システム概観
【００１６】
図１ａは、本発明の一実施の形態によるシステム１００を示す。システム１００は、フロントエンドサーバ１０２、検索エンジン１０４ならびに関係するコンテンツサーバ１０６、修正サーバ１０７、および幾つかのクエリー修正手段（reviser: リバイザ）１０８を備える。動作中は、ユーザが、ネットワーク（不図示のインターネット等）上の任意の種類のクライアントコンピュータ装置上で動作する、例えば、インターネット関連プロトコル（例えばＴＣＰ／ＩＰおよびＨＴＴＰ）で通信するよう適合しているブラウザーアプリケーションまたは他のアプリケーションを実行する従来型クライアント１１８を経由して、システム１００にアクセスする。単一のクライアント１１８を示しているが、システム１００は、多くのクライアントに対して大量の同時セッションをサポートできる。一実施の形態では、システム１００は、高性能サーバークラスコンピュータ上で動作し、クライアント装置１１８は任意の種類のコンピュータ装置でよい。サーバおよびクライアントコンピュータのハードウエア面についての詳細は、当該分野の技術者には周知であり、本明細書ではこれ以上言及しない。
【００１７】
フロントエンドサーバ１０２は、クライアント１１８が提出した検索クエリーの受信に関与する。フロントエンドサーバ１０２はそのクエリーを検索エンジン１０４へ提供し、検索エンジンはクエリーを評価して、一セットの検索結果を検索クエリーにより検索し、その結果をフロントエンドサーバ１０２へ返す。検索エンジン１０４は、コンテンツサーバ１０６の内の一台以上と通信して、ユーザの検索クエリーと関連する複数の文書を選定する。コンテンツサーバ１０６は、異なるウェブサイトからインデックスされる（および／または検索される）大量の文書を格納する。代替としてまたは追加して、コンテンツサーバ１０６は、各種のウェブサイト上に格納される文書のインデックスを格納する。「文書」は、本明細書では、任意のテキスト形式または画像形式のテキスト文書、画像、ビデオ、オーディオ、マルチメディア、プレゼンテーション、ウェブページ（組込み型ハイパーリンクおよび他のメタデータ、および／またはプログラム、例えばＪａｖａ（登録商標）スクリプト、を含めることができる）等を含む、任意の形式のインデックス可能なコンテンツであると理解される。一実施の形態では、インデックスされる各文書は、文書のリンク構造によるページランクを割り当てられる。ページランクは、クエリーとは無関係の、文書の重要性尺度として機能する。ページランクの例示の形式は、引用して本明細書に組み込まれた、米国特許第６，２８５，９９９号に記載されている。検索エンジン１０４は、文書のページランク（および／または他のクエリーと無関係な、文書の重要性尺度）に基づく各文書の得点、および文書の重要性のクエリーと関係する一つ以上の信号（例えば、文書内の検索用語の場所および頻度）を割り当てる。
【００１８】
フロントエンドサーバ１０２は、修正サーバ１０７にもクエリーを提供する。修正サーバ１０７は、複数の異なるクエリー修正手段１０８とインターフェース（相互交流）し、該クエリー修正手段１０８の各々は、異なるクエリー修正戦略（修正計画又は修正手法）または一組のクエリー修正戦略（修正計画又は修正手法）を実行する。一実施の形態では、該クエリー修正手段１０８として、拡張型修正手段１０８．１、構文（syntax）型修正手段１０８．２、絞り込み型修正手段１０８．３、およびセッション基準型修正手段１０８．４などが含まれる。修正サーバ１０７は、クエリーを各修正手段１０８へ提供し、各修正手段１０８からの応答内で、一つ以上の潜在的修正クエリー（ここで「潜在的」と呼ぶのは、この時点では修正サーバ１０７がまだその修正クエリーを採用していないから）を得る。システムアーキテクチャは、任意の数の異なるクエリー修正手段１０８を用いることができ、低性能のクエリー修正手段１０８については削除し、新規クエリー修正手段１０８（ジェネリック修正手段１０８．ｎで示す）に対しては将来要望されるとして追加することができるよう、特別に設計されている。これはシステム１００に特別なフレキシビリティを与え、特定の主題の分野（例えば、医薬品、法律等の分野で用いるための修正手段）、企業（内部情報検索システムのための、特定ビジネス分野または企業領域に特有の修正手段）、または異なる言語（例えば、特定言語および方言のための修正手段）に対して、カスタム化し適合することもできる。
【００１９】
好ましくは、その修正が良好な修正である確率、すなわち、元のクエリーよりユーザの情報必要性に一層深く関連する結果を生成する確率、を表す信頼性尺度と、それぞれの修正クエリーが関係していることである。従って、それぞれの潜在的修正クエリーは、タプル（組）（Ｒｉ、Ｃｉ）で表すことができ、ここでＲは潜在的修正クエリー、Ｃは修正クエリーと関係する信頼性尺度である。一実施の形態では、これらの信頼性尺度は、各修正手段１０８の各修正戦略について予め手動で評価する。尺度は、試験中のサンプルクエリーおよび修正クエリーの結果解析から導出できる。例えば、絞り込み型修正手段１０８．３には、元の短いクエリー（例えば、３つ以下の用語）からの修正クエリーへ高い信頼性尺度を、元の長いクエリー（４つ以上の用語）からの修正クエリーへ低い信頼性尺度を割り当てることができる。これらの割り当ては、短いクエリーへの用語追加が、基底となる情報の必要性に対するクエリーの関連性を著しく改良する傾向がある（すなわち、短いクエリーは範囲が広くなりやすいので、そのようなクエリーの絞り込みは、より狭く、より関連のある結果セットに絞りやすい）ことを示す経験的評価に基づく。逆に、拡張型修正手段１０８．１は、長いクエリーから一つ以上の用語を削除するか、または長いクエリーへ類義語を追加した修正クエリーに、高い信頼性尺度を割り当てることができる。他の実施の形態では、一つ以上の修正手段１０８が、潜在的修正クエリーの内の一つ以上に対して、信頼性尺度を動的に（例えば、実行時間に）生成できる。このような実施の形態は、図１ｂと併せて詳細に後述する。信頼性尺度の割り当ては、他の構成体（例えば、修正サーバ１０７）により実行でき、クエリー関係データおよびクエリー無関係データをともに考慮することができる。
【００２０】
修正サーバ１０７は、前記潜在的修正クエリーの内の一つ以上（または全て）からなる該潜在的修正クエリーのサブセットを選択し、これらを検索エンジン１０４へ提供できる。検索エンジン１０４は、通常のクエリーと同一の方法で修正クエリーを処理し、提示される修正クエリーそれぞれの結果を修正サーバ１０７へ提供する。修正サーバ１０７は、修正クエリーの結果と元のクエリーの結果との比較を含む、各修正クエリーの結果を評価する。次いで、修正サーバ１０７は、以下に説明するように、最良の修正クエリー（または少なくとも、元のクエリーによく適合している修正クエリー）であるとして、修正クエリーの内の一つ以上を選定できる。
【００２１】
修正サーバ１０７は、潜在的修正クエリーＲを全て受信し、それらが関係する信頼性尺度Ｃにより、最高信頼度から最低信頼度に至るまで順にそれらを分類する。修正サーバ１０７は、潜在的修正クエリーの分類リストを通して繰り返し、潜在的修正クエリーそれぞれを検索エンジン１０４へ渡して、一セットの検索結果を得る。（代替として、修正サーバ１０７は、潜在的修正クエリーのサブセット、例えば、閾値を越える信頼性尺度を持つものを最初に選択してもよい）。場合によっては、上位検索結果は、修正戦略を実行しながらまたは信頼性尺度を評価中に、既に取得してあり（例えば、修正手段１０８または修正サーバ１０７が）、その場合、修正サーバ１０７は、そのようにして得られた検索結果を用いることができる。
【００２２】
それぞれの潜在的修正クエリーに対して、修正サーバ１０７は、潜在的修正クエリーを選択するか、またはそれを破棄するかを決定する。選択は、元のクエリーの検索結果と独立させた、および関係させた両方の、修正クエリーの上位Ｎ個の検索結果の評価に応じて行うことができる。一般に、修正クエリーは、元のクエリーよりユーザの情報必要性を正確に反映していると考えられる検索結果を生成すべきである。必要に応じて、それより多いかまたは少ない結果を処理できるが、普通は上位１０個の結果を評価する。
【００２３】
一実施の形態では、以下の条件が維持される場合、潜在的修正クエリーを選択する。
【００２４】
i）修正クエリーが少なくとも最小数の検索結果を生成する。例えば、このパラメータを１に設定すると、検索結果がない全ての（かつ唯一の）修正を破棄する。許容できる最小数の結果の範囲は、概ね１から１００までである。
【００２５】
ii）修正クエリーは、修正の上位結果内に最小数の「新規」検索結果を生成する。元のクエリーまたは以前に選択した修正クエリーの上位結果内にも生成されない場合、検索結果は「新規」である。例えば、このパラメータを２に設定すると、以前に選択したどれかの修正クエリーの上位結果内に生成されず、または元のクエリーの上位結果内にも生成されない少なくとも二つの上位結果を有するよう、それぞれの選択した修正に要求することになる。この制約により、選択した修正内に多様な結果が存在することが確実になり、修正の内の少なくとも一つが有用であることを証明する機会が最多となる。例えば、図３に見られるように、修正クエリーそれぞれに対する上位３つの結果３０４は、他の結果セットと異なっている。これにより、ユーザは、修正クエリーとの関連性が高い検索結果を幅広く見渡すことができる。
【００２６】
iii）最大数の修正クエリーはまだ選択されていない。換言すると、最大数の修正クエリーが既に選択されている場合、残りの全ての修正クエリーは破棄される。一実施の形態では、修正クエリーの最大数は４に設定される。別の実施の形態では、修正クエリーの最大数は２〜１０の間に設定される。
【００２７】
上記選択パラメータの結果は、修正クエリーのページ３００上に含まれる選択した修正クエリーのセットである。修正サーバ１０７は、先に説明したように、このページへのリンクを構築し、このリンクをフロントエンドサーバ１０２へ提供する。修正サーバ１０７は、修正クエリーのページ３００上の、修正クエリーの順序およびレイアウトを決定する。修正クエリーは信頼性尺度の順に（最高から最低まで）リストアップされることが好ましい。
【００２８】
フロントエンドサーバ１０２は、検索結果ページ内に提供されたリンクを含み、次いで、クライアント１１８へ送信される。ユーザは次いで、元のクエリーに対する検索結果を概観でき、または修正クエリーへのリンクを選択して、それにより、選択された修正クエリーおよび関係する結果を見る。
【００２９】
修正クエリーの提示
【００３０】
図２は、クライアント１１８へ提供されるサンプル結果のページ２００である。この単純な実施では、検索結果２００のページに、元のクエリー２０２の［シーツ］が、このクエリーへの結果２０４と併せて含まれる。一セットの修正クエリーへのリンク２０６が、ページ２００の下部に含まれる。次いでユーザは、リンク２０６上をクリックし、修正クエリーのページにアクセスできる。例示のページ３００を図３に示す。ここでは、修正クエリー［リネン］、［寝具類］、および［ベッドシーツ］それぞれに対する修正クエリーリンク３０２．１、３０２．２、および３０２．３が示すように、上位３つの修正クエリーが提示される。各修正クエリーリンク３０２の下が、そのクエリーに対する上位３つの検索結果３０４である。
【００３１】
元の結果ページ２００とは別のページ３００上に修正クエリーを提供するのには、様々な利点がある。第１に、画面領域は制約のあるリソースなので、修正クエリー自体によるそのリスト化は、可能ではあるが、ユーザが彼らの検索結果の文脈で修正クエリーを見ないので望ましくない。別のページ３００に修正クエリーを置くことにより、ユーザは、最良の修正クエリーおよびそれと関係する上位結果を見ることができ、ユーザは、どの修正クエリーが彼らの情報必要性を最も満たしているように見えるかを選択してから、修正クエリー自体を選択できる。元のクエリーおよび修正クエリーの結果を両方とも、単一ページ（長くはなるが）に含めることは可能ではあるが、この手法は、ユーザにページをスクロールダウンして、全ての修正クエリーを評価するよう要求するか、またはそのページの最初に見える部分に詰め込むかのどちらかとなる。代替として、図２および図３に示す好適な実施の形態では、ユーザは、クエリー修正と関係する結果を見て、それぞれの修正クエリーリンク３０２をクリックし、選択した修正クエリーに対する検索結果の全セットにアクセスすることができる。また多くの場合、この手法は、自動的に修正クエリーを用いて検索結果を取得し、それをユーザに自動的に提示することが好ましい（例えば、ユーザ選択または相互作用がなくても）。さらにこの手法は、最良の潜在的修正を示すことにより、有効なクエリーを生み出す方法をユーザに間接的に教示する、という利点を付け加える。別の実施の形態では、修正サーバ１０７は、クエリー修正を元の結果ページ２００上に、例えば別のウィンドウとするか、元の結果ページ２００内に表示させることができる。
【００３２】
クエリー修正についての追加情報（例えば検索結果３０４）を表示して、ユーザに修正をよく理解させるのに役立てる方法は、メインの結果ページ２００上で用いることもできる。これは、スペルを補正する修正の状況のような、単一の非常に高品質の修正クエリー（または少数の非常に高品質の修正）がある場合に特に有用である。スペル補正の修正クエリーは、タイトル、ＵＲＬ、および上位結果の抜粋等の、追加情報と併せて結果ページ２００上に表示し、スペル補正の示唆が正しいものかどうかをユーザが決定するのに役立てることができる。
【００３３】
別の実施の形態では、修正サーバ１０７は、信頼性尺度を用いて、クエリー修正をとにかく表示するかどうかを決定し、もし表示するなら、修正または修正へのリンクを目立つように配置する方法を決定する。この実施の形態は、後述する。
【００３４】
クエリー修正手段
【００３５】
再び図１を参照して、様々なクエリー修正手段１０８について説明する。拡張型修正手段１０８．１は、元のクエリー範囲を効果的に広げた一つ以上の修正クエリーを生成する。これらの修正は、元のクエリーが狭すぎる場合に特に有用である。拡張型修正手段１０８．１が使用できる幾つかの異なる戦略がある。
【００３６】
第１に、この修正手段１０８．１は、離接として類義語および関連用語を追加することにより、クエリーを拡張できる。ユーザは一般的概念を説明する特定ワードを何気なく選択するので、クエリーが具体的すぎることが多い。対象の文書がそのワードを含まない場合、ユーザの情報必要性は満たされないままとなる。離接として類義語を追加するクエリー修正は、クエリーを拡張し、結果セットに所望の文書をもたらすことができる。同様に、離接として、類義語そのものではなく関連語を追加することが有用なことがある。関連語、類義語、シソーラスまたは辞書等のような、クエリーを拡張する任意の適切な方法を、ここで用いることができる。クエリー拡張の一方法は、引用して本明細書に組み込まれた、２００５年３月３０日出願の米国特許出願第１１／ｘｘｘ，ｘｘｘ号、発明の名称「クエリー文脈内のクエリー用語の類語決定」、に開示されている。
【００３７】
第２に、修正手段１０８．１は、一つ以上のクエリー用語を削除することにより、クエリーを広げることができる。先に示した例示のように、時には、クエリー用語を削除すると（例示のクエリー「三菱ギャラン情報」内の「情報」のように）、良好なクエリー修正を生み出すことができる。この手法では、拡張型修正手段１０８．１は、そのクエリー用語が存在しても、それが欠如しているのと比較すると検索結果をさほど絞り込みしないという点から、クエリーのどの用語が重要でないかを決定する。検索のためには重要でない用語を識別するための技法は、引用して本明細書に組み込まれた、２００５年３月２８日出願の米国特許出願第１１／ｘｘｘ，ｘｘｘ号、発明の名称「重要性が希薄なクエリー用語の決定」、に記載されている。このような技法の結果を用いて、重要でない用語を削除することによりクエリーを修正できる。
【００３８】
構文型修正手段１０８．２は、元のクエリーに様々な種類の構文変更を加えることによりクエリーを修正できる。これらは以下の修正戦略を含む：
・元のクエリーに引用符があれば除去する。引用符内のクエリーは検索エンジン１０４が単一の文字として取り扱い、その全てのクエリー文字列をもつ文書だけが返される。この修正は、クエリー用語のどれかと文書との全関連性に基づく文書を、検索エンジン１０４に返させるので検索結果数が増加する。
・クエリー全体の前後に引用符を追加する。場合によっては、クエリーを全体フレーズとして取り扱う方が適切である。
・現実のフレーズであるかのように、クエリーのｎグラム（クエリー内の連続用語の或る数）の前後に引用符を追加する。クエリー内のｎグラムは、様々なソースを用いて識別できる。
【００３９】
Ａ）常用フレーズの手作り辞書
【００４０】
Ｂ）頻出データから作製したフレーズリスト。ここで、フレーズは、統計的に有意差のある頻度を伴って発生する連続用語に基づいて識別される。例えば、良好なバイグラム［ｔ１ ｔ２］は、［ｔ１］および［ｔ２］の両者がともに、ランダムより高い尤度（可能性）で文書内に現れる場合、バイグラム［ｔ１ ｔ２］として現れるという特性を有する。フレーズのリストを構築するための一方法は、引用して本明細書に組み込まれた、２００４年７月２６日出願の米国特許出願第１０／９００，０２１号、発明の名称「情報検索システムにおけるフレーズ識別」、に開示されている。
【００４１】
Ｃ）普通の姓および名前のリスト（例えば、人口統計データまたは何らかの他のソースから得たもの）。構文型修正手段１０８．２は、連続するクエリー用語の対［ｔ１ ｔ２］に対して、［ｔ１］が普通の名前のリストに含まれるかどうか、［ｔ２］が普通の姓のリストに含まれるかどうか決定する。含まれていれば、クエリー［ｔ１ ｔ２］の下位部分を引用符内に置いて、潜在的修正クエリーを形成する。
【００４２】
共通する問題は、クエリー内のストップワード（無視されるワード）使用である。ランク（序列）付けアルゴリズムは、「the」、「a」、「an」、「to」等のような頻出用語を無視するのが普通である。場合によっては、これらがクエリー内の、実際に重要な用語である（「to be or not to be」のようなクエリーを考えてみるとよい）。従って、構文型修正手段１０８．２は、「＋」演算子（または同様な演算子）を用いて、その演算子がクエリーに存在しているときは常に、このような用語を含めさせる幾つかの修正クエリーも創出する。例えば、クエリー［the link］に対して［+the link］を提案する。
・句読点や他のシンボルを削除する。ユーザは、時折、クエリーの意味を変化させる句読点や他の構文（シンボルのような）を付け加える。これを行うほとんどのユーザは、無意識にそれを行うので、構文型修正手段１０８．２もまた、句読点や他の同様な構文があるときは常に、それを削除することにより修正クエリーを生成する。例えば、クエリー［rear window+ movie］に対して、構文型修正手段はクエリー［rear window movie］を生成して、結果を何も生みそうにない文字列「widow+」に対して検索エンジン１０４が検索するのを防ぐ。
【００４３】
絞り込み型修正手段１０８．３は、クエリーを絞り込みする、つまり狭くする、何らかの適切な方法を用いて、ユーザの潜在的情報必要性をより特定して記述することができる。一実施の形態では、絞り込み型修正手段１０８．３は、検索クエリーの用語ベクトル表現を、以前から既に、それぞれの検索結果と関係付けられ、重み付けされている既知の検索クエリーの用語ベクトルと比較することにより、クエリー修正を生成する。最も近いベクトルを持つ既知の検索クエリー（または複数のクエリー）を潜在的修正クエリーとして選択する。
【００４４】
より詳細には、一実施の形態では、絞り込み型修正手段１０８．３は、以下のように動作する。絞り込み型修正手段１０８．３は、ユーザの元のクエリーを用いて、選定した幾つかの検索結果を検索エンジン１０４から取得する（例えば、上位１００個の結果）。絞り込み型修正手段１０８．３は、以前から存在するデータベースにアクセスし、これらの文書それぞれを、以前に用いて、結果としてその文書を含むことになった一つ以上の検索クエリーと一致させる。以前から存在するデータベースは、検索クエリーと関係する文書を格納し、クエリーと文書との関係付けは、その文書に対するクエリーの関連姓得点により重み付けされる。
【００４５】
第２に、絞り込み型修正手段１０８．３は、クラスター化アルゴリズムを用いて、一致した格納クエリーの用語から形成される用語ベクトルおよび一致の重み付けに基づいて検索結果文書のクラスターを形成する。用語ベクトルは、単位長さの正規化した多次元ベクトルであり、それぞれの次元は、個々のワードまたはワードの組み合わせとすることができる用語に対応する。クラスターは、一致する格納文書と対応する元の検索文書の関連性得点、およびクラスター毎に発生する格納文書の数に基づいてランク付けされる。最高ランクのクラスターは、潜在的細分クラスターとして選択される。クラスターは、「情報検索」（W． Frakes & R. Baeza-Yates eds. 92）内のE. Rasmussen著「クラスター化アルゴリズム」に記載されているような、階層型凝集（agglomerative）クラスター化アルゴリズム等の、各種クラスター化アルゴリズムを用いて形成することができる。この開示を引用して本明細書に組み込む。
【００４６】
第３に、絞り込み型修正手段１０８．３は、潜在的絞り込みクラスター毎にクラスター重心を計算する。絞り込み型修正手段１０８．３は次いで、クラスター毎に潜在的修正クエリーを決定する。所与の絞り込みクラスター内で、そのクラスター内の文書と関係する以前格納した検索クエリー毎に、クラスター重心までのその用語ベクトルの距離および検索クエリーが関係する格納文書の数に基づいて、絞り込み型修正手段１０８．３は格納した検索クエリーを採点する。各潜在的絞り込みクラスター内で、最高得点の以前格納したクエリーを潜在的修正クエリーとして選択する。
【００４７】
最後に、絞り込み型修正手段１０８．３は、選択した修正絞り込みクエリーを修正サーバ１０７へ提供する。適切な一絞り込み型修正手段の詳細については、引用して本明細書に組み込まれた、２００３年９月２２日出願の米国特許出願第１０／６６８，７２１号、発明の名称「検索クエリー絞り込みを提供するためのシステムおよび方法」、に記載されている。
【００４８】
セッション基準型修正手段１０８．４は、セッション基準ユーザーデータを用いる任意の適切な方法を用いて、他のユーザが過去に行った変更の解析に基づいて、ユーザの潜在的情報必要性をより正確に取得することができる。一実施の形態では、セッション基準型修正手段１０８．４は、多くの個々のユーザーセッションから収集したクリックデータに基づいて一つ以上の修正クエリーを提供する。最初に、セッション基準型修正手段１０８．４が生成した２つのテーブルを用いて、クエリー対の発生頻度を計算する。クエリー対は、単一のユーザーセッションで発生する２つのクエリーのシーケンス、例えば、第１クエリー［シーツ］、続く第２クエリー［リネン］または第２クエリー［絹シーツ］である。繰り返し発生する個々のクエリーの第１のテーブルは、例えば、図１ｂのログファイル１１０に格納されるユーザーセッションのクエリーデータから生成される。一実施の形態では、繰り返し発生するクエリーは、最小頻度、例えば一日一回、発生する。繰り返し発生するクエリー対の第２のテーブルは、同様にログファイル１１０から生成され、各クエリー対は第１クエリーとそれに続く第２クエリーとを含む。二つのテーブルから、各クエリー対の発生頻度は、第１のテーブルの第１クエリーに対する発生カウントの比として計算される。例えば、第１クエリー［シーツ］が１００回発生し、続いて第２クエリー［リネン］が１００回の内の３０回発生する場合、クエリー対［シーツ、リネン］の発生頻度は、第１クエリーに対する発生カウントの比として、３０／１００または３０％である。任意の所与の第１クエリーに対して、クエリー対は、発生頻度が特定閾値を越える場合、第１クエリーの修正候補としての第２クエリーにより維持される。一実施の形態では、この閾値は１％である。
【００４９】
候補の修正クエリーについて、クエリー対の第２クエリーの品質が該クエリー対の第１クエリーの品質を越える増加量を、セッション基準型修正手段１０８．４が、ユーザークリックデータから生成した２つの追加のテーブルを用いて計算する。対となるクエリーそれぞれに対して品質得点のテーブルを生成する。対の第１クエリーを越える該対の第２クエリーの品質の改善がもしあるなら、そのテーブルから、それを計算する。
【００５０】
一実施の形態では、品質得点は、クリック行動データからユーザ満足度を評価することにより決定する。品質得点を決定するためのそのような一方法は、引用して本明細書に組み込まれた、２００４年６月２８日出願の米国特許出願第１０／８７８，９２６号、発明の名称「相互交流プロファイルを導出し、使用するためのシステムおよび方法」に記載されているような、相互交流プロファイルの使用である。
【００５１】
一実施の形態では、品質得点計算は、例えば、ログファイル１１０内に格納されている、ユーザクリックデータに基づく。品質得点は、検索結果上の最初のクリックの推定の継続時間に基づく。一実施の形態では、特定クリックの継続時間は、例えば図１ｂのログファイル１１０内の、他のユーザーセッションクエリーデータとともに格納できる、最初のクリックおよび後続のクリックが発生した時間から推定する。採点は、クリックがない検索結果には得点ゼロを割り当て、最初のクリックと後続のクリックとの間の持続時間へ適用されるＳ曲線に沿って進み、より長いクリックは品質得点１に近づく。一実施の形態では、２０秒は０．１に、４０秒は０．５に、そして６０秒は０．９に対応する。関連のないコンテンツ、例えばバナー広告上のクリックはデータから排除する。別の実施の形態では、最初のクリックだけでなく、クエリーに対する全ての結果のクリックを収集する。
【００５２】
次いでセッション基準型修正手段１０８．４は、発生頻度および上記の品質得点データを用いて、最初のクエリーを越える候補の修正クエリーとしての第２クエリーについての予測実用性を計算できる。一実施の形態では、予測実用性は、クエリー対の発生頻度と、その対の第１クエリーを越える第２クエリーの品質改善分との積である。この実施例では、品質改善分は、第２クエリーの品質得点が、第１クエリーの品質得点より高い場合に発生する。第２クエリーの予測実用性が閾値を越える場合、第２クエリーは潜在的修正クエリーとしてマークされる。一実施の形態では、閾値は０．０２であり、これは例えば、１０％頻度と品質得点の０．２増加に対応し、あるいは２０％頻度と品質得点の０．１増加に対応する。予測実用性計算の他の変形を同様に用いることができる。
【００５３】
上記説明のように、各修正クエリーは、修正が有効な修正となる確率を表す信頼性尺度と関係付けることができる。セッション基準型修正手段１０８．４の場合には、その修正クエリーに対する信頼性尺度として、修正クエリーの予測実用性を用いることができる。
【００５４】
セッション基準型修正手段１０８．４を用いるクエリー修正の実施例を以下に挙げる。第１ユーザークエリーは［シーツ］である。格納されているデータは、［シーツ］に続く通常ユーザ入力の（第２の）クエリーは［リネン］であり、別の通常入力の第２のクエリー入力は［絹シーツ］であることを示す。ログファイル１１０に格納されるデータに基づくと、第１クエリー［シーツ］に対する発生率としては、クエリー対［シーツ、リネン］の頻度は３０％であり、クエリー対［シーツ、絹シーツ］の頻度は１％である。例えば、クエリー［シーツ］が表中で１００回発生した場合、［シーツ、リネン］は３０回発生し、［シーツ、絹シーツ］は一回発生している。候補の修正として第２クエリーに対して１％閾値を仮定すると、これらのクエリーはともに維持される。
【００５５】
次にデータが示すところによれば、［シーツ］の品質得点は０．１であり、一方、第２クエリー［リネン］および［絹シーツ］の品質得点はそれぞれ０．７および０．８である。従って、［シーツ］を越える［リネン］の品質改善分は０．６（０．７−０．１）であり、［シーツ］を越える［絹シーツ］の品質改善分は０．７（０．８−０．１）である。
【００５６】
次いで、セッション基準型修正手段１０８．４は、各修正の予測実用性を頻度得点と品質改善分との積として計算する。［シーツ、リネン］に対しては、頻度（３０％）と品質増加（０．６）との積は、予測実用性０．１８となる。［シーツ、絹シーツ］に対しては、頻度（１％）と品質増加（０．７）との積は、予測実用性０．００７となる。このように、第１クエリー［シーツ］を入力するユーザにとって、第２クエリー［リネン］は、クエリー［絹シーツ］より高い予測実用性を有し、従って、［リネン］はより有効なクエリー修正の示唆である。上記説明のように、これらの予測実用性は修正クエリーの信頼性尺度として用いることができる。
【００５７】
実行時に修正信頼性尺度を生成
【００５８】
次に図１ｂを参照して、本発明による情報検索システムの別の実施の形態を示す。図１ａの先に説明した要素の他に、ログファイル１１０、セッション追跡器１１４、および修正手段信頼性評価器１１２がある。上記説明のように、クエリー修正手段１０８は、修正サーバ１０７へ提供する修正クエリーの内の一つ以上と併せて信頼性尺度を提供する。修正サーバ１０７は、信頼性尺度を用いて、修正クエリーページ３００上に含めるためにどの潜在的修正クエリーを選択するかを決定する。一実施の形態では、所与の元のクエリーに対して修正クエリーを選択する際のユーザ活動履歴に少なくとも一部基づいて、信頼性尺度を実行時に導出できる。
【００５９】
図１ｂの実施の形態では、フロントエンドサーバ１０２は、元のクエリーおよび修正クエリー情報を伴うユーザのクリックスルー行動を、セッション追跡器１１４に提供する。セッション追跡器１１４は、ユーザがアクセスしたクエリー修正リンク３０２と関係付けられている各ユーザークエリーを格納し、修正クエリーの品質をモデル化するための元のクエリーおよび修正クエリーの様々な特徴に加えて、各修正クエリーと関係する結果を格納するログファイル１１０を維持する。格納される情報は、例えば、以下を含む。
【００６０】
元のクエリーに対しては、
・元のクエリー自体
・元のクエリー内の各ワード
・元のクエリーの長さ
・元のクエリーのトピッククラスタ
・元のクエリーの情報検索得点
・元のクエリーの結果の数。
【００６１】
修正クエリーに対しては、
・修正クエリー自体
・修正クエリー内の各ワード
・それを生成した修正技法の識別
・修正クエリーの長さ
・修正クエリーと関係するトピッククラスタ
・上位検索結果の情報検索得点（例えば、ページランク）
・修正クエリーの見付けた結果の数
・修正クエリーリンク３０２上のクリックの長さ
・修正クエリー結果３０４上をクリックする長さ。
【００６２】
クエリーのトピッククラスタは、任意の適切なトピック識別法を用いて識別される。適切な一方法は、引用して本明細書に組み込まれた、２００３年９月３０日出願の米国特許出願第１０／６７６，５７１号、発明の名称「関連ワードのクラスタに基づいて文書を特徴付けるための方法および装置」、に記載されている。
【００６３】
修正手段信頼性評価器１１２は、予測モデル、例えば論理的重回帰モデル、を用いてログファイル１１０を解析し、所与のクエリーに対して有効な修正となる修正クエリーの尤度を評価するために用いることができるクエリーおよび修正クエリーの特徴に基づく１セットの規則を生成する。適切な一回帰モデルは、引用して本明細書に組み込まれた、２００３年１２月１５日出願の米国特許出願第１０／７３４，５８４号、発明の名称「大規模マシン学習システムおよび方法」に記載されている。修正手段信頼性評価器１１２は、修正クエリーリンク３０２上のユーザによる長時間クリックが、ユーザの元の情報必要性の正確な提示となるような修正により、満足していることを示すという仮定の上で動作する。長時間クリックは、ある最小時間経過、例えば最低６０秒、の間、クリックスルーページにユーザが留まる場合に、発生すると見なすことができる。修正クエリーリンク３０２上のクリックの長さから、修正手段信頼性評価器１１２は、予測モデルを教育して、修正クエリーおよび元のクエリーの各種の特徴を与える長いクリックの尤度を予測できる。長いクリックの高い予測尤度を有する修正クエリーは、それが関係する元のクエリーに対してより良好な（すなわちより成功率が高い）修正であると考えることができる。
【００６４】
予測モデルの一実施の形態では、信頼性評価器１１２は、修正クエリーと関係する特徴を選定し、ログファイルからクリックデータを収集し、その特徴およびクリックデータを用いて規則を定式化し、そして予測モデルへその規則を加える。さらに信頼性評価器１１２は、クリックデータを用いて追加規則を公式化でき、モデルへ追加規則を選択的に追加する。
【００６５】
実行時に、修正サーバ１０７は、元のクエリー、および各種のクエリー修正手段１０８から受信するそれぞれの修正クエリーを修正手段信頼性評価器１１２に提供する。修正手段信頼性評価器１１２は、元のクエリーおよび修正クエリーを予測モデルに適用して、前述の信頼性尺度として役立つ予測尺度を得る。代替として、各クエリー修正手段１０８は、修正手段信頼性評価器１１２を直接呼び出し、予測尺度を得てこれらの値を修正サーバ１０７へ戻す。図示した実施の形態は、修正手段信頼性評価器１１２を別のモジュールとして示すが、代替として修正サーバ１０７が、信頼性評価器の機能を提供してもよい。いずれの場合でも、修正サーバ１０７は、上記説明のように信頼性尺度を用いて、どの修正クエリーがユーザに示されるかを選択し順序を定める。
【００６６】
一実施の形態では、修正サーバ１０７は、信頼性尺度を用いて、クエリー修正を全て表示するかどうか、表示するならその修正またはそれへのリンクを、どれくらい目立つように配置するかを決定する。そのために、修正サーバ１０７は、先に説明した最初の信頼性尺度か、上記の動的に生成した信頼性尺度のどちらかを用いることができる。例えば、最良の信頼性尺度が閾値未満になる場合、これは、どの潜在的候補修正も非常に良好とは言えず、その場合は、元の結果ページ２００に修正が行われないことを示唆する。他方、一つ以上の修正クエリーが、別の閾値を越える非常に高い信頼性尺度を有する場合、修正サーバ１０７は、クエリー修正、または修正クエリーページ３００へのリンクを、元の結果ページ２００上に非常に目立つように、例えば、ページの上部近くに、かつ目立つフォントで、またはどこか他の目立つ場所に、表示させることができる。信頼性尺度が、二つの閾値の間にある場合、修正クエリーページ３００へのリンクは少し目立たない場所、例えば、検索結果ページ２００の最後に、例えばリンク２０６について示すように、配置することができる。
【００６７】
上記説明の処理ステップは、並列で（例えば、クエリー修正の結果を得るステップと、クエリー修正の信頼性尺度を計算するステップとを並列に）、および／または交互に（例えば、全てのクエリー修正を受信してからクエリー修正リストを分類するステップではなく、クエリー修正手段から多数のクエリー修正を受信するステップと、オンザフライでクエリー修正の格納リストを構築するステップとを交互に）実行できる。さらに、上記実施の形態はクライアント／サーバ検索システムに関連して説明しているが、本発明は、スタンドアロン型マシン（例えば、スタンドアロン型ＰＣ）の一部として実施することもできる。これは例えば、Google Desktop Searchのようなデスクトップ検索アプリケーションの状況では有用である。
【００６８】
一つの可能性のある実施の形態に対して、特に詳細に本発明を説明してきた。当該分野の技術者には言うまでもなく、本発明は他の実施の形態で実践できる。第１に、構成体の特定の名称、用語の大文字化、属性、データ構造、または何らかの他のプログラミングもしくは構造的局面は、必須でも重要でもなく、本発明またはその特徴を実施するメカニズムは、異なる名称、フォーマット、またはプロトコルを持っていてもよい。さらに、本システムは、上記したように、ハードウエアとソフトウエアとの組み合わせにより実施してもよく、または全体的にハードウエア要素で実施してもよい。また、本明細書で説明した各種システム構成体間の特定の機能分割は、単なる例示であって必須ではなく；単一システム構成体により実行される機能は、代替として多数の構成体により実行することができ、多数の構成体により実行される機能は、代替として単一構成体により実行してもよい。
【００６９】
上記説明の幾つかの部分は、情報に関する操作のアルゴリズムおよびシンボル表現の点から本発明の特徴を表している。これらのアルゴリズム説明および表現は、データ処理分野の技術者が、彼らの業務内容を他の当該分野の技術者に伝えるために用いる最も効果的な手段である。これらの操作は、機能的または論理的に説明したが、言うまでもなくコンピュータプログラムにより実施される。さらに、これらの操作の編成を、一般性を失わずにモジュールとしてまたは機能名称により参照するのは、時として便利であることも判明している。
【００７０】
上記説明から明らかなように他に特別に言及しない限り、言うまでもなく、説明全体を通じて説明した行動および処理は、コンピュータシステムメモリもしくはレジスタまたは他のそのような情報の格納、送信、もしくはディスプレイ装置内の物理量（電子量）として表されるデータを操作し、変換するコンピュータシステム、または類似の電子計算装置によるものである。このようなコンピュータシステムの基底をなすハードウエアの詳細な説明は、コンピュータ工学分野の技術者には周知の情報なので、本明細書では提供しない。
【００７１】
本発明の特定態様は、本明細書においてアルゴリズムの形式で説明した処理ステップおよび命令を含む。注意すべきは、本発明の処理ステップおよび命令は、ソフトウエア、ファームウエア、またはハードウエアで組み込むことができ、ソフトウエアに組み込む場合は、リアルタイムのネットワークオペレーティングシステムが用いる異なるプラットフォームに常駐させて、操作するようダウンロードできる、ということである。
【００７２】
本発明の特定態様について個々または単一の実施例について説明してきたが；言うまでもなく、本発明の動作はこの観点に制限されない。従って、単一の要素または構成体への全ての参照は、複数のこのような構成体をも参照していると解釈すべきである。同様に、「或る」、または「その」への参照は、他に特別に言及しない限り、複数への参照を含むと解釈すべきである。最後に、用語「複数」の意味は、説明中の本発明の部分に見合う二つ以上の実体やデータ項目等を指し、無限またはさもなくば過剰なほどの項目数を含む。
【００７３】
本発明は、本明細書の動作を実行するための装置にも関連する。本装置は、要求する目的のために特別に構成してもよく、またはコンピュータがアクセスできるコンピュータ可読媒体上に格納されるコンピュータプログラムにより、選択的に作動または再構成される汎用コンピュータを備えてもよい。このようなコンピュータプログラムは、限定はしないが、フレキシブル磁気ディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスクを含む任意の種類のディスク、リードオンリーメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カードや光カード、または電子命令を格納するための、それぞれがコンピュータシステムバスに接続される任意の種類の媒体、のような、コンピュータ可読格納媒体内に格納できる。集積回路設計およびビデオコーデックの分野の技術者には言うまでもなく、本発明は、上記機能および構造説明に基づいて、特定用途向け集積回路（ＡＳＩＣ）を含む多様な種類の集積回路内で容易に製作できる。さらに、本発明は、多様な種類のビデオコーディング装置内に組み込むことができる。
【００７４】
本明細書で提示したアルゴリズムおよび操作は、何らかの特定コンピュータまたは他の装置とは本質的に関連しない。多様な汎用システムを本明細書の教示に基づくプログラムとともに用いることもでき、またはより専用化した装置を構築して、要求される方法ステップを実行すると好都合であることがわかる。これらの多様なシステムに要求される構成は、等価な改変と併せて、当該分野の技術者には明らかであろう。さらに、何らかの特定プログラミング言語を参照して本発明を説明していない。言うまでもなく、多様なプログラミング言語を用いて、本明細書で説明した本発明の教示を実施でき、どのような特定言語の参照であっても、本発明の可能性の開示および最良の態様が提供される。
【００７５】
最後に、注意すべきは、本明細書で用いられる言語は、原則として可読性および説明目的のために選択されていて、進歩性のある主題を範囲設定したり、または制限するために選択したものではない。従って、本発明の開示は、本発明の説明を意図したものであって、制限する意図はない。
【符号の説明】
【００７６】
１０２ フロントエンドサーバ
１０７ 修正サーバ
１１８ クライアント
【技術分野】
【０００１】
本発明は、一般に、情報検索システムに関し、より詳細には、ユーザークエリーを修正するためのシステムアーキテクチャに関する。
【０００２】
関連出願の相互参照
本出願は以下に関連し、それぞれを引用して本明細書に組み込む。
・２００３年９月２２日出願の米国特許出願第１０／６６８，７２１号、発明の名称「検索クエリー絞り込みを提供するためのシステムおよび方法」。
・２００３年９月３０日出願の米国特許出願第１０／６７６，５７１号、発明の名称「関連ワードのクラスタに基づいて文書を特徴付けるための方法および装置」。
・２００３年１２月１５日出願の米国特許出願第１０／７３４，５８４号、発明の名称「大規模マシン学習システムおよび方法」。
・２００４年６月２８日出願の米国特許出願第１０／８７８，９２６号、発明の名称「相互作用プロファイルを導出し、使用するためのシステムおよび方法」。
・２００４年７月２６日出願の米国特許出願第１０／９００，０２１号、発明の名称「情報検索システムにおけるフレーズ識別」。
・２００５年３月２８日出願の米国特許出願第１１／ｘｘｘ，ｘｘｘ号、発明の名称「重要性が希薄なクエリー用語の決定」。
・２００５年３月３０日出願の米国特許出願第１１／ｘｘｘ，ｘｘｘ号、発明の名称「クエリー文脈内のクエリー用語の類語決定」。および、
・米国特許第６，２８５，９９９号。
【背景技術】
【０００３】
インターネット検索エンジンにより具体化されているような情報検索システムは、一般に、ユーザークエリーに概ね関連する文書を迅速に提供できる。検索エンジンは、文書間および用語間の結び付きと併せて、用語および文書の出現頻度に各種統計的尺度を用いて、クエリーに対する文書の関連性を決定できる。大部分の検索エンジン設計の基底をなす主要な技術的仮定は、ユーザークエリーが、ユーザが所望する情報目標を正確に表しているということである。
【０００４】
現実には、ユーザが有効なクエリーを考えるのは困難なのが普通である。単一のクエリーでは所望の結果をもたらさないことが多いので、ユーザは、同一の話題について幾つかの異なるクエリーを入力することが多い。これら多数のクエリーは、クエリー用語や推測企業名の範囲または特異性の変形、ワード順序やワード数の変形等を含むのが普通である。クエリーをうまく修正するよう幅広く変化させる能力を有している様々なユーザ達がいるので、クエリー修正を自動化した各種の方法がこれまでに提案されている。
【０００５】
ごく普通には、クエリー絞り込みを通じて、より一般的なクエリーから、より正確な（すなわちより狭い）クエリーを自動生成する。その上位検索結果がユーザの情報必要性に関連する文書の上位セット（上位集合）を含む、範囲が広すぎるクエリーをユーザが入力する場合、クエリー絞り込み法は最も有効である。例えば、三菱ギャラン自動車に関する情報を求めるユーザが、自動車会社だけでなく多くの異なる三菱企業を検索結果が含む広すぎるクエリー「三菱」を、入力するかもしれない。従って、クエリーを絞り込みすることが望ましい（ユーザの特定情報の必要性を決定するのは、追加文脈欠如によりここでは困難であるが）。
【０００６】
しかし、正しい修正法がクエリー範囲を広げる場合において具体的過ぎるクエリーをユーザが入力する場合、または上位結果がユーザの情報必要性に無関連である場合は、クエリー絞り込み法は有効ではない。例えば、クエリー「三菱ギャラン情報」は、用語「情報」のために貧弱な結果をもたらすかもしれない（この場合には、三菱ギャラン自動車についての結果はほとんどない）。この場合、正しい修正はクエリー範囲を「三菱ギャラン」へ広げることである。従って、クエリー絞り込み法は幾つかの状況では作用するが、他のクエリー修正技法を用いることにより、ユーザの情報必要性が最も満たされる状況が、非常に多く存在する。
【０００７】
別のクエリー修正戦略は、類義語リストつまりシソーラスを用いてクエリーを拡張し、ユーザの潜在的情報必要性を取得することである。しかし、クエリー絞り込み法と同様に、クエリー拡張法が、常にクエリー修正の適切な方法であるとは限らず、結果の品質はクエリー用語の文脈に大きく依存する。
【０００８】
一つのクエリー修正技法だけでは、あらゆる事例で所望する結果を提供できないので、幾つかの異なるクエリー修正方法（つまり戦略）を提供する方法論を持つことが望ましい。
【発明の概要】
【０００９】
情報検索システムは、自己のクエリー修正戦略をそれぞれが実施する幾つかの異なるクエリー修正手段を提供する、クエリー修正アーキテクチャを含む。それぞれのクエリー修正手段は、ユーザクエリーを評価して、ユーザクエリーの一つ以上の潜在的修正クエリーを決定する。修正サーバは、クエリー修正手段と相互交流して潜在的修正クエリーを得る。修正サーバは、情報検索システム内の検索エンジンとも相互交流して、潜在的修正クエリー毎に一組の検索結果を得る。修正サーバは、ユーザへ提示するために修正クエリーの内の一つ以上を選定し、選定した修正クエリー毎に検索結果のサブセットを添える。従って、ユーザは修正クエリーに対する検索結果の品質を観察でき、修正クエリーの内の一つを選択して、その修正クエリーに対する検索結果の全セットを得ることができる。
【００１０】
次に、各種の図、ダイヤグラム、および技術情報と関連させて本発明を説明する。図は、本発明の多様な実施の形態を、説明だけを目的として示す。当該分野の技術者には言うまでもなく、以下の説明から、図示し、かつ説明する構造、方法、および機能の代替の実施の形態は、本発明の原理から逸脱することなく利用できる。
【図面の簡単な説明】
【００１１】
【図１ａ】クエリー修正を提供する情報検索システムの実施の形態の全体システム図である。
【００１２】
【図１ｂ】代替の情報検索システムの全体システム図である。
【００１３】
【図２】元のユーザクエリーへのサンプル結果ページの図である。
【００１４】
【図３】サンプルの修正クエリーページの図である。
【発明を実施するための形態】
【００１５】
システム概観
【００１６】
図１ａは、本発明の一実施の形態によるシステム１００を示す。システム１００は、フロントエンドサーバ１０２、検索エンジン１０４ならびに関係するコンテンツサーバ１０６、修正サーバ１０７、および幾つかのクエリー修正手段（reviser: リバイザ）１０８を備える。動作中は、ユーザが、ネットワーク（不図示のインターネット等）上の任意の種類のクライアントコンピュータ装置上で動作する、例えば、インターネット関連プロトコル（例えばＴＣＰ／ＩＰおよびＨＴＴＰ）で通信するよう適合しているブラウザーアプリケーションまたは他のアプリケーションを実行する従来型クライアント１１８を経由して、システム１００にアクセスする。単一のクライアント１１８を示しているが、システム１００は、多くのクライアントに対して大量の同時セッションをサポートできる。一実施の形態では、システム１００は、高性能サーバークラスコンピュータ上で動作し、クライアント装置１１８は任意の種類のコンピュータ装置でよい。サーバおよびクライアントコンピュータのハードウエア面についての詳細は、当該分野の技術者には周知であり、本明細書ではこれ以上言及しない。
【００１７】
フロントエンドサーバ１０２は、クライアント１１８が提出した検索クエリーの受信に関与する。フロントエンドサーバ１０２はそのクエリーを検索エンジン１０４へ提供し、検索エンジンはクエリーを評価して、一セットの検索結果を検索クエリーにより検索し、その結果をフロントエンドサーバ１０２へ返す。検索エンジン１０４は、コンテンツサーバ１０６の内の一台以上と通信して、ユーザの検索クエリーと関連する複数の文書を選定する。コンテンツサーバ１０６は、異なるウェブサイトからインデックスされる（および／または検索される）大量の文書を格納する。代替としてまたは追加して、コンテンツサーバ１０６は、各種のウェブサイト上に格納される文書のインデックスを格納する。「文書」は、本明細書では、任意のテキスト形式または画像形式のテキスト文書、画像、ビデオ、オーディオ、マルチメディア、プレゼンテーション、ウェブページ（組込み型ハイパーリンクおよび他のメタデータ、および／またはプログラム、例えばＪａｖａ（登録商標）スクリプト、を含めることができる）等を含む、任意の形式のインデックス可能なコンテンツであると理解される。一実施の形態では、インデックスされる各文書は、文書のリンク構造によるページランクを割り当てられる。ページランクは、クエリーとは無関係の、文書の重要性尺度として機能する。ページランクの例示の形式は、引用して本明細書に組み込まれた、米国特許第６，２８５，９９９号に記載されている。検索エンジン１０４は、文書のページランク（および／または他のクエリーと無関係な、文書の重要性尺度）に基づく各文書の得点、および文書の重要性のクエリーと関係する一つ以上の信号（例えば、文書内の検索用語の場所および頻度）を割り当てる。
【００１８】
フロントエンドサーバ１０２は、修正サーバ１０７にもクエリーを提供する。修正サーバ１０７は、複数の異なるクエリー修正手段１０８とインターフェース（相互交流）し、該クエリー修正手段１０８の各々は、異なるクエリー修正戦略（修正計画又は修正手法）または一組のクエリー修正戦略（修正計画又は修正手法）を実行する。一実施の形態では、該クエリー修正手段１０８として、拡張型修正手段１０８．１、構文（syntax）型修正手段１０８．２、絞り込み型修正手段１０８．３、およびセッション基準型修正手段１０８．４などが含まれる。修正サーバ１０７は、クエリーを各修正手段１０８へ提供し、各修正手段１０８からの応答内で、一つ以上の潜在的修正クエリー（ここで「潜在的」と呼ぶのは、この時点では修正サーバ１０７がまだその修正クエリーを採用していないから）を得る。システムアーキテクチャは、任意の数の異なるクエリー修正手段１０８を用いることができ、低性能のクエリー修正手段１０８については削除し、新規クエリー修正手段１０８（ジェネリック修正手段１０８．ｎで示す）に対しては将来要望されるとして追加することができるよう、特別に設計されている。これはシステム１００に特別なフレキシビリティを与え、特定の主題の分野（例えば、医薬品、法律等の分野で用いるための修正手段）、企業（内部情報検索システムのための、特定ビジネス分野または企業領域に特有の修正手段）、または異なる言語（例えば、特定言語および方言のための修正手段）に対して、カスタム化し適合することもできる。
【００１９】
好ましくは、その修正が良好な修正である確率、すなわち、元のクエリーよりユーザの情報必要性に一層深く関連する結果を生成する確率、を表す信頼性尺度と、それぞれの修正クエリーが関係していることである。従って、それぞれの潜在的修正クエリーは、タプル（組）（Ｒｉ、Ｃｉ）で表すことができ、ここでＲは潜在的修正クエリー、Ｃは修正クエリーと関係する信頼性尺度である。一実施の形態では、これらの信頼性尺度は、各修正手段１０８の各修正戦略について予め手動で評価する。尺度は、試験中のサンプルクエリーおよび修正クエリーの結果解析から導出できる。例えば、絞り込み型修正手段１０８．３には、元の短いクエリー（例えば、３つ以下の用語）からの修正クエリーへ高い信頼性尺度を、元の長いクエリー（４つ以上の用語）からの修正クエリーへ低い信頼性尺度を割り当てることができる。これらの割り当ては、短いクエリーへの用語追加が、基底となる情報の必要性に対するクエリーの関連性を著しく改良する傾向がある（すなわち、短いクエリーは範囲が広くなりやすいので、そのようなクエリーの絞り込みは、より狭く、より関連のある結果セットに絞りやすい）ことを示す経験的評価に基づく。逆に、拡張型修正手段１０８．１は、長いクエリーから一つ以上の用語を削除するか、または長いクエリーへ類義語を追加した修正クエリーに、高い信頼性尺度を割り当てることができる。他の実施の形態では、一つ以上の修正手段１０８が、潜在的修正クエリーの内の一つ以上に対して、信頼性尺度を動的に（例えば、実行時間に）生成できる。このような実施の形態は、図１ｂと併せて詳細に後述する。信頼性尺度の割り当ては、他の構成体（例えば、修正サーバ１０７）により実行でき、クエリー関係データおよびクエリー無関係データをともに考慮することができる。
【００２０】
修正サーバ１０７は、前記潜在的修正クエリーの内の一つ以上（または全て）からなる該潜在的修正クエリーのサブセットを選択し、これらを検索エンジン１０４へ提供できる。検索エンジン１０４は、通常のクエリーと同一の方法で修正クエリーを処理し、提示される修正クエリーそれぞれの結果を修正サーバ１０７へ提供する。修正サーバ１０７は、修正クエリーの結果と元のクエリーの結果との比較を含む、各修正クエリーの結果を評価する。次いで、修正サーバ１０７は、以下に説明するように、最良の修正クエリー（または少なくとも、元のクエリーによく適合している修正クエリー）であるとして、修正クエリーの内の一つ以上を選定できる。
【００２１】
修正サーバ１０７は、潜在的修正クエリーＲを全て受信し、それらが関係する信頼性尺度Ｃにより、最高信頼度から最低信頼度に至るまで順にそれらを分類する。修正サーバ１０７は、潜在的修正クエリーの分類リストを通して繰り返し、潜在的修正クエリーそれぞれを検索エンジン１０４へ渡して、一セットの検索結果を得る。（代替として、修正サーバ１０７は、潜在的修正クエリーのサブセット、例えば、閾値を越える信頼性尺度を持つものを最初に選択してもよい）。場合によっては、上位検索結果は、修正戦略を実行しながらまたは信頼性尺度を評価中に、既に取得してあり（例えば、修正手段１０８または修正サーバ１０７が）、その場合、修正サーバ１０７は、そのようにして得られた検索結果を用いることができる。
【００２２】
それぞれの潜在的修正クエリーに対して、修正サーバ１０７は、潜在的修正クエリーを選択するか、またはそれを破棄するかを決定する。選択は、元のクエリーの検索結果と独立させた、および関係させた両方の、修正クエリーの上位Ｎ個の検索結果の評価に応じて行うことができる。一般に、修正クエリーは、元のクエリーよりユーザの情報必要性を正確に反映していると考えられる検索結果を生成すべきである。必要に応じて、それより多いかまたは少ない結果を処理できるが、普通は上位１０個の結果を評価する。
【００２３】
一実施の形態では、以下の条件が維持される場合、潜在的修正クエリーを選択する。
【００２４】
i）修正クエリーが少なくとも最小数の検索結果を生成する。例えば、このパラメータを１に設定すると、検索結果がない全ての（かつ唯一の）修正を破棄する。許容できる最小数の結果の範囲は、概ね１から１００までである。
【００２５】
ii）修正クエリーは、修正の上位結果内に最小数の「新規」検索結果を生成する。元のクエリーまたは以前に選択した修正クエリーの上位結果内にも生成されない場合、検索結果は「新規」である。例えば、このパラメータを２に設定すると、以前に選択したどれかの修正クエリーの上位結果内に生成されず、または元のクエリーの上位結果内にも生成されない少なくとも二つの上位結果を有するよう、それぞれの選択した修正に要求することになる。この制約により、選択した修正内に多様な結果が存在することが確実になり、修正の内の少なくとも一つが有用であることを証明する機会が最多となる。例えば、図３に見られるように、修正クエリーそれぞれに対する上位３つの結果３０４は、他の結果セットと異なっている。これにより、ユーザは、修正クエリーとの関連性が高い検索結果を幅広く見渡すことができる。
【００２６】
iii）最大数の修正クエリーはまだ選択されていない。換言すると、最大数の修正クエリーが既に選択されている場合、残りの全ての修正クエリーは破棄される。一実施の形態では、修正クエリーの最大数は４に設定される。別の実施の形態では、修正クエリーの最大数は２〜１０の間に設定される。
【００２７】
上記選択パラメータの結果は、修正クエリーのページ３００上に含まれる選択した修正クエリーのセットである。修正サーバ１０７は、先に説明したように、このページへのリンクを構築し、このリンクをフロントエンドサーバ１０２へ提供する。修正サーバ１０７は、修正クエリーのページ３００上の、修正クエリーの順序およびレイアウトを決定する。修正クエリーは信頼性尺度の順に（最高から最低まで）リストアップされることが好ましい。
【００２８】
フロントエンドサーバ１０２は、検索結果ページ内に提供されたリンクを含み、次いで、クライアント１１８へ送信される。ユーザは次いで、元のクエリーに対する検索結果を概観でき、または修正クエリーへのリンクを選択して、それにより、選択された修正クエリーおよび関係する結果を見る。
【００２９】
修正クエリーの提示
【００３０】
図２は、クライアント１１８へ提供されるサンプル結果のページ２００である。この単純な実施では、検索結果２００のページに、元のクエリー２０２の［シーツ］が、このクエリーへの結果２０４と併せて含まれる。一セットの修正クエリーへのリンク２０６が、ページ２００の下部に含まれる。次いでユーザは、リンク２０６上をクリックし、修正クエリーのページにアクセスできる。例示のページ３００を図３に示す。ここでは、修正クエリー［リネン］、［寝具類］、および［ベッドシーツ］それぞれに対する修正クエリーリンク３０２．１、３０２．２、および３０２．３が示すように、上位３つの修正クエリーが提示される。各修正クエリーリンク３０２の下が、そのクエリーに対する上位３つの検索結果３０４である。
【００３１】
元の結果ページ２００とは別のページ３００上に修正クエリーを提供するのには、様々な利点がある。第１に、画面領域は制約のあるリソースなので、修正クエリー自体によるそのリスト化は、可能ではあるが、ユーザが彼らの検索結果の文脈で修正クエリーを見ないので望ましくない。別のページ３００に修正クエリーを置くことにより、ユーザは、最良の修正クエリーおよびそれと関係する上位結果を見ることができ、ユーザは、どの修正クエリーが彼らの情報必要性を最も満たしているように見えるかを選択してから、修正クエリー自体を選択できる。元のクエリーおよび修正クエリーの結果を両方とも、単一ページ（長くはなるが）に含めることは可能ではあるが、この手法は、ユーザにページをスクロールダウンして、全ての修正クエリーを評価するよう要求するか、またはそのページの最初に見える部分に詰め込むかのどちらかとなる。代替として、図２および図３に示す好適な実施の形態では、ユーザは、クエリー修正と関係する結果を見て、それぞれの修正クエリーリンク３０２をクリックし、選択した修正クエリーに対する検索結果の全セットにアクセスすることができる。また多くの場合、この手法は、自動的に修正クエリーを用いて検索結果を取得し、それをユーザに自動的に提示することが好ましい（例えば、ユーザ選択または相互作用がなくても）。さらにこの手法は、最良の潜在的修正を示すことにより、有効なクエリーを生み出す方法をユーザに間接的に教示する、という利点を付け加える。別の実施の形態では、修正サーバ１０７は、クエリー修正を元の結果ページ２００上に、例えば別のウィンドウとするか、元の結果ページ２００内に表示させることができる。
【００３２】
クエリー修正についての追加情報（例えば検索結果３０４）を表示して、ユーザに修正をよく理解させるのに役立てる方法は、メインの結果ページ２００上で用いることもできる。これは、スペルを補正する修正の状況のような、単一の非常に高品質の修正クエリー（または少数の非常に高品質の修正）がある場合に特に有用である。スペル補正の修正クエリーは、タイトル、ＵＲＬ、および上位結果の抜粋等の、追加情報と併せて結果ページ２００上に表示し、スペル補正の示唆が正しいものかどうかをユーザが決定するのに役立てることができる。
【００３３】
別の実施の形態では、修正サーバ１０７は、信頼性尺度を用いて、クエリー修正をとにかく表示するかどうかを決定し、もし表示するなら、修正または修正へのリンクを目立つように配置する方法を決定する。この実施の形態は、後述する。
【００３４】
クエリー修正手段
【００３５】
再び図１を参照して、様々なクエリー修正手段１０８について説明する。拡張型修正手段１０８．１は、元のクエリー範囲を効果的に広げた一つ以上の修正クエリーを生成する。これらの修正は、元のクエリーが狭すぎる場合に特に有用である。拡張型修正手段１０８．１が使用できる幾つかの異なる戦略がある。
【００３６】
第１に、この修正手段１０８．１は、離接として類義語および関連用語を追加することにより、クエリーを拡張できる。ユーザは一般的概念を説明する特定ワードを何気なく選択するので、クエリーが具体的すぎることが多い。対象の文書がそのワードを含まない場合、ユーザの情報必要性は満たされないままとなる。離接として類義語を追加するクエリー修正は、クエリーを拡張し、結果セットに所望の文書をもたらすことができる。同様に、離接として、類義語そのものではなく関連語を追加することが有用なことがある。関連語、類義語、シソーラスまたは辞書等のような、クエリーを拡張する任意の適切な方法を、ここで用いることができる。クエリー拡張の一方法は、引用して本明細書に組み込まれた、２００５年３月３０日出願の米国特許出願第１１／ｘｘｘ，ｘｘｘ号、発明の名称「クエリー文脈内のクエリー用語の類語決定」、に開示されている。
【００３７】
第２に、修正手段１０８．１は、一つ以上のクエリー用語を削除することにより、クエリーを広げることができる。先に示した例示のように、時には、クエリー用語を削除すると（例示のクエリー「三菱ギャラン情報」内の「情報」のように）、良好なクエリー修正を生み出すことができる。この手法では、拡張型修正手段１０８．１は、そのクエリー用語が存在しても、それが欠如しているのと比較すると検索結果をさほど絞り込みしないという点から、クエリーのどの用語が重要でないかを決定する。検索のためには重要でない用語を識別するための技法は、引用して本明細書に組み込まれた、２００５年３月２８日出願の米国特許出願第１１／ｘｘｘ，ｘｘｘ号、発明の名称「重要性が希薄なクエリー用語の決定」、に記載されている。このような技法の結果を用いて、重要でない用語を削除することによりクエリーを修正できる。
【００３８】
構文型修正手段１０８．２は、元のクエリーに様々な種類の構文変更を加えることによりクエリーを修正できる。これらは以下の修正戦略を含む：
・元のクエリーに引用符があれば除去する。引用符内のクエリーは検索エンジン１０４が単一の文字として取り扱い、その全てのクエリー文字列をもつ文書だけが返される。この修正は、クエリー用語のどれかと文書との全関連性に基づく文書を、検索エンジン１０４に返させるので検索結果数が増加する。
・クエリー全体の前後に引用符を追加する。場合によっては、クエリーを全体フレーズとして取り扱う方が適切である。
・現実のフレーズであるかのように、クエリーのｎグラム（クエリー内の連続用語の或る数）の前後に引用符を追加する。クエリー内のｎグラムは、様々なソースを用いて識別できる。
【００３９】
Ａ）常用フレーズの手作り辞書
【００４０】
Ｂ）頻出データから作製したフレーズリスト。ここで、フレーズは、統計的に有意差のある頻度を伴って発生する連続用語に基づいて識別される。例えば、良好なバイグラム［ｔ１ ｔ２］は、［ｔ１］および［ｔ２］の両者がともに、ランダムより高い尤度（可能性）で文書内に現れる場合、バイグラム［ｔ１ ｔ２］として現れるという特性を有する。フレーズのリストを構築するための一方法は、引用して本明細書に組み込まれた、２００４年７月２６日出願の米国特許出願第１０／９００，０２１号、発明の名称「情報検索システムにおけるフレーズ識別」、に開示されている。
【００４１】
Ｃ）普通の姓および名前のリスト（例えば、人口統計データまたは何らかの他のソースから得たもの）。構文型修正手段１０８．２は、連続するクエリー用語の対［ｔ１ ｔ２］に対して、［ｔ１］が普通の名前のリストに含まれるかどうか、［ｔ２］が普通の姓のリストに含まれるかどうか決定する。含まれていれば、クエリー［ｔ１ ｔ２］の下位部分を引用符内に置いて、潜在的修正クエリーを形成する。
【００４２】
共通する問題は、クエリー内のストップワード（無視されるワード）使用である。ランク（序列）付けアルゴリズムは、「the」、「a」、「an」、「to」等のような頻出用語を無視するのが普通である。場合によっては、これらがクエリー内の、実際に重要な用語である（「to be or not to be」のようなクエリーを考えてみるとよい）。従って、構文型修正手段１０８．２は、「＋」演算子（または同様な演算子）を用いて、その演算子がクエリーに存在しているときは常に、このような用語を含めさせる幾つかの修正クエリーも創出する。例えば、クエリー［the link］に対して［+the link］を提案する。
・句読点や他のシンボルを削除する。ユーザは、時折、クエリーの意味を変化させる句読点や他の構文（シンボルのような）を付け加える。これを行うほとんどのユーザは、無意識にそれを行うので、構文型修正手段１０８．２もまた、句読点や他の同様な構文があるときは常に、それを削除することにより修正クエリーを生成する。例えば、クエリー［rear window+ movie］に対して、構文型修正手段はクエリー［rear window movie］を生成して、結果を何も生みそうにない文字列「widow+」に対して検索エンジン１０４が検索するのを防ぐ。
【００４３】
絞り込み型修正手段１０８．３は、クエリーを絞り込みする、つまり狭くする、何らかの適切な方法を用いて、ユーザの潜在的情報必要性をより特定して記述することができる。一実施の形態では、絞り込み型修正手段１０８．３は、検索クエリーの用語ベクトル表現を、以前から既に、それぞれの検索結果と関係付けられ、重み付けされている既知の検索クエリーの用語ベクトルと比較することにより、クエリー修正を生成する。最も近いベクトルを持つ既知の検索クエリー（または複数のクエリー）を潜在的修正クエリーとして選択する。
【００４４】
より詳細には、一実施の形態では、絞り込み型修正手段１０８．３は、以下のように動作する。絞り込み型修正手段１０８．３は、ユーザの元のクエリーを用いて、選定した幾つかの検索結果を検索エンジン１０４から取得する（例えば、上位１００個の結果）。絞り込み型修正手段１０８．３は、以前から存在するデータベースにアクセスし、これらの文書それぞれを、以前に用いて、結果としてその文書を含むことになった一つ以上の検索クエリーと一致させる。以前から存在するデータベースは、検索クエリーと関係する文書を格納し、クエリーと文書との関係付けは、その文書に対するクエリーの関連姓得点により重み付けされる。
【００４５】
第２に、絞り込み型修正手段１０８．３は、クラスター化アルゴリズムを用いて、一致した格納クエリーの用語から形成される用語ベクトルおよび一致の重み付けに基づいて検索結果文書のクラスターを形成する。用語ベクトルは、単位長さの正規化した多次元ベクトルであり、それぞれの次元は、個々のワードまたはワードの組み合わせとすることができる用語に対応する。クラスターは、一致する格納文書と対応する元の検索文書の関連性得点、およびクラスター毎に発生する格納文書の数に基づいてランク付けされる。最高ランクのクラスターは、潜在的細分クラスターとして選択される。クラスターは、「情報検索」（W． Frakes & R. Baeza-Yates eds. 92）内のE. Rasmussen著「クラスター化アルゴリズム」に記載されているような、階層型凝集（agglomerative）クラスター化アルゴリズム等の、各種クラスター化アルゴリズムを用いて形成することができる。この開示を引用して本明細書に組み込む。
【００４６】
第３に、絞り込み型修正手段１０８．３は、潜在的絞り込みクラスター毎にクラスター重心を計算する。絞り込み型修正手段１０８．３は次いで、クラスター毎に潜在的修正クエリーを決定する。所与の絞り込みクラスター内で、そのクラスター内の文書と関係する以前格納した検索クエリー毎に、クラスター重心までのその用語ベクトルの距離および検索クエリーが関係する格納文書の数に基づいて、絞り込み型修正手段１０８．３は格納した検索クエリーを採点する。各潜在的絞り込みクラスター内で、最高得点の以前格納したクエリーを潜在的修正クエリーとして選択する。
【００４７】
最後に、絞り込み型修正手段１０８．３は、選択した修正絞り込みクエリーを修正サーバ１０７へ提供する。適切な一絞り込み型修正手段の詳細については、引用して本明細書に組み込まれた、２００３年９月２２日出願の米国特許出願第１０／６６８，７２１号、発明の名称「検索クエリー絞り込みを提供するためのシステムおよび方法」、に記載されている。
【００４８】
セッション基準型修正手段１０８．４は、セッション基準ユーザーデータを用いる任意の適切な方法を用いて、他のユーザが過去に行った変更の解析に基づいて、ユーザの潜在的情報必要性をより正確に取得することができる。一実施の形態では、セッション基準型修正手段１０８．４は、多くの個々のユーザーセッションから収集したクリックデータに基づいて一つ以上の修正クエリーを提供する。最初に、セッション基準型修正手段１０８．４が生成した２つのテーブルを用いて、クエリー対の発生頻度を計算する。クエリー対は、単一のユーザーセッションで発生する２つのクエリーのシーケンス、例えば、第１クエリー［シーツ］、続く第２クエリー［リネン］または第２クエリー［絹シーツ］である。繰り返し発生する個々のクエリーの第１のテーブルは、例えば、図１ｂのログファイル１１０に格納されるユーザーセッションのクエリーデータから生成される。一実施の形態では、繰り返し発生するクエリーは、最小頻度、例えば一日一回、発生する。繰り返し発生するクエリー対の第２のテーブルは、同様にログファイル１１０から生成され、各クエリー対は第１クエリーとそれに続く第２クエリーとを含む。二つのテーブルから、各クエリー対の発生頻度は、第１のテーブルの第１クエリーに対する発生カウントの比として計算される。例えば、第１クエリー［シーツ］が１００回発生し、続いて第２クエリー［リネン］が１００回の内の３０回発生する場合、クエリー対［シーツ、リネン］の発生頻度は、第１クエリーに対する発生カウントの比として、３０／１００または３０％である。任意の所与の第１クエリーに対して、クエリー対は、発生頻度が特定閾値を越える場合、第１クエリーの修正候補としての第２クエリーにより維持される。一実施の形態では、この閾値は１％である。
【００４９】
候補の修正クエリーについて、クエリー対の第２クエリーの品質が該クエリー対の第１クエリーの品質を越える増加量を、セッション基準型修正手段１０８．４が、ユーザークリックデータから生成した２つの追加のテーブルを用いて計算する。対となるクエリーそれぞれに対して品質得点のテーブルを生成する。対の第１クエリーを越える該対の第２クエリーの品質の改善がもしあるなら、そのテーブルから、それを計算する。
【００５０】
一実施の形態では、品質得点は、クリック行動データからユーザ満足度を評価することにより決定する。品質得点を決定するためのそのような一方法は、引用して本明細書に組み込まれた、２００４年６月２８日出願の米国特許出願第１０／８７８，９２６号、発明の名称「相互交流プロファイルを導出し、使用するためのシステムおよび方法」に記載されているような、相互交流プロファイルの使用である。
【００５１】
一実施の形態では、品質得点計算は、例えば、ログファイル１１０内に格納されている、ユーザクリックデータに基づく。品質得点は、検索結果上の最初のクリックの推定の継続時間に基づく。一実施の形態では、特定クリックの継続時間は、例えば図１ｂのログファイル１１０内の、他のユーザーセッションクエリーデータとともに格納できる、最初のクリックおよび後続のクリックが発生した時間から推定する。採点は、クリックがない検索結果には得点ゼロを割り当て、最初のクリックと後続のクリックとの間の持続時間へ適用されるＳ曲線に沿って進み、より長いクリックは品質得点１に近づく。一実施の形態では、２０秒は０．１に、４０秒は０．５に、そして６０秒は０．９に対応する。関連のないコンテンツ、例えばバナー広告上のクリックはデータから排除する。別の実施の形態では、最初のクリックだけでなく、クエリーに対する全ての結果のクリックを収集する。
【００５２】
次いでセッション基準型修正手段１０８．４は、発生頻度および上記の品質得点データを用いて、最初のクエリーを越える候補の修正クエリーとしての第２クエリーについての予測実用性を計算できる。一実施の形態では、予測実用性は、クエリー対の発生頻度と、その対の第１クエリーを越える第２クエリーの品質改善分との積である。この実施例では、品質改善分は、第２クエリーの品質得点が、第１クエリーの品質得点より高い場合に発生する。第２クエリーの予測実用性が閾値を越える場合、第２クエリーは潜在的修正クエリーとしてマークされる。一実施の形態では、閾値は０．０２であり、これは例えば、１０％頻度と品質得点の０．２増加に対応し、あるいは２０％頻度と品質得点の０．１増加に対応する。予測実用性計算の他の変形を同様に用いることができる。
【００５３】
上記説明のように、各修正クエリーは、修正が有効な修正となる確率を表す信頼性尺度と関係付けることができる。セッション基準型修正手段１０８．４の場合には、その修正クエリーに対する信頼性尺度として、修正クエリーの予測実用性を用いることができる。
【００５４】
セッション基準型修正手段１０８．４を用いるクエリー修正の実施例を以下に挙げる。第１ユーザークエリーは［シーツ］である。格納されているデータは、［シーツ］に続く通常ユーザ入力の（第２の）クエリーは［リネン］であり、別の通常入力の第２のクエリー入力は［絹シーツ］であることを示す。ログファイル１１０に格納されるデータに基づくと、第１クエリー［シーツ］に対する発生率としては、クエリー対［シーツ、リネン］の頻度は３０％であり、クエリー対［シーツ、絹シーツ］の頻度は１％である。例えば、クエリー［シーツ］が表中で１００回発生した場合、［シーツ、リネン］は３０回発生し、［シーツ、絹シーツ］は一回発生している。候補の修正として第２クエリーに対して１％閾値を仮定すると、これらのクエリーはともに維持される。
【００５５】
次にデータが示すところによれば、［シーツ］の品質得点は０．１であり、一方、第２クエリー［リネン］および［絹シーツ］の品質得点はそれぞれ０．７および０．８である。従って、［シーツ］を越える［リネン］の品質改善分は０．６（０．７−０．１）であり、［シーツ］を越える［絹シーツ］の品質改善分は０．７（０．８−０．１）である。
【００５６】
次いで、セッション基準型修正手段１０８．４は、各修正の予測実用性を頻度得点と品質改善分との積として計算する。［シーツ、リネン］に対しては、頻度（３０％）と品質増加（０．６）との積は、予測実用性０．１８となる。［シーツ、絹シーツ］に対しては、頻度（１％）と品質増加（０．７）との積は、予測実用性０．００７となる。このように、第１クエリー［シーツ］を入力するユーザにとって、第２クエリー［リネン］は、クエリー［絹シーツ］より高い予測実用性を有し、従って、［リネン］はより有効なクエリー修正の示唆である。上記説明のように、これらの予測実用性は修正クエリーの信頼性尺度として用いることができる。
【００５７】
実行時に修正信頼性尺度を生成
【００５８】
次に図１ｂを参照して、本発明による情報検索システムの別の実施の形態を示す。図１ａの先に説明した要素の他に、ログファイル１１０、セッション追跡器１１４、および修正手段信頼性評価器１１２がある。上記説明のように、クエリー修正手段１０８は、修正サーバ１０７へ提供する修正クエリーの内の一つ以上と併せて信頼性尺度を提供する。修正サーバ１０７は、信頼性尺度を用いて、修正クエリーページ３００上に含めるためにどの潜在的修正クエリーを選択するかを決定する。一実施の形態では、所与の元のクエリーに対して修正クエリーを選択する際のユーザ活動履歴に少なくとも一部基づいて、信頼性尺度を実行時に導出できる。
【００５９】
図１ｂの実施の形態では、フロントエンドサーバ１０２は、元のクエリーおよび修正クエリー情報を伴うユーザのクリックスルー行動を、セッション追跡器１１４に提供する。セッション追跡器１１４は、ユーザがアクセスしたクエリー修正リンク３０２と関係付けられている各ユーザークエリーを格納し、修正クエリーの品質をモデル化するための元のクエリーおよび修正クエリーの様々な特徴に加えて、各修正クエリーと関係する結果を格納するログファイル１１０を維持する。格納される情報は、例えば、以下を含む。
【００６０】
元のクエリーに対しては、
・元のクエリー自体
・元のクエリー内の各ワード
・元のクエリーの長さ
・元のクエリーのトピッククラスタ
・元のクエリーの情報検索得点
・元のクエリーの結果の数。
【００６１】
修正クエリーに対しては、
・修正クエリー自体
・修正クエリー内の各ワード
・それを生成した修正技法の識別
・修正クエリーの長さ
・修正クエリーと関係するトピッククラスタ
・上位検索結果の情報検索得点（例えば、ページランク）
・修正クエリーの見付けた結果の数
・修正クエリーリンク３０２上のクリックの長さ
・修正クエリー結果３０４上をクリックする長さ。
【００６２】
クエリーのトピッククラスタは、任意の適切なトピック識別法を用いて識別される。適切な一方法は、引用して本明細書に組み込まれた、２００３年９月３０日出願の米国特許出願第１０／６７６，５７１号、発明の名称「関連ワードのクラスタに基づいて文書を特徴付けるための方法および装置」、に記載されている。
【００６３】
修正手段信頼性評価器１１２は、予測モデル、例えば論理的重回帰モデル、を用いてログファイル１１０を解析し、所与のクエリーに対して有効な修正となる修正クエリーの尤度を評価するために用いることができるクエリーおよび修正クエリーの特徴に基づく１セットの規則を生成する。適切な一回帰モデルは、引用して本明細書に組み込まれた、２００３年１２月１５日出願の米国特許出願第１０／７３４，５８４号、発明の名称「大規模マシン学習システムおよび方法」に記載されている。修正手段信頼性評価器１１２は、修正クエリーリンク３０２上のユーザによる長時間クリックが、ユーザの元の情報必要性の正確な提示となるような修正により、満足していることを示すという仮定の上で動作する。長時間クリックは、ある最小時間経過、例えば最低６０秒、の間、クリックスルーページにユーザが留まる場合に、発生すると見なすことができる。修正クエリーリンク３０２上のクリックの長さから、修正手段信頼性評価器１１２は、予測モデルを教育して、修正クエリーおよび元のクエリーの各種の特徴を与える長いクリックの尤度を予測できる。長いクリックの高い予測尤度を有する修正クエリーは、それが関係する元のクエリーに対してより良好な（すなわちより成功率が高い）修正であると考えることができる。
【００６４】
予測モデルの一実施の形態では、信頼性評価器１１２は、修正クエリーと関係する特徴を選定し、ログファイルからクリックデータを収集し、その特徴およびクリックデータを用いて規則を定式化し、そして予測モデルへその規則を加える。さらに信頼性評価器１１２は、クリックデータを用いて追加規則を公式化でき、モデルへ追加規則を選択的に追加する。
【００６５】
実行時に、修正サーバ１０７は、元のクエリー、および各種のクエリー修正手段１０８から受信するそれぞれの修正クエリーを修正手段信頼性評価器１１２に提供する。修正手段信頼性評価器１１２は、元のクエリーおよび修正クエリーを予測モデルに適用して、前述の信頼性尺度として役立つ予測尺度を得る。代替として、各クエリー修正手段１０８は、修正手段信頼性評価器１１２を直接呼び出し、予測尺度を得てこれらの値を修正サーバ１０７へ戻す。図示した実施の形態は、修正手段信頼性評価器１１２を別のモジュールとして示すが、代替として修正サーバ１０７が、信頼性評価器の機能を提供してもよい。いずれの場合でも、修正サーバ１０７は、上記説明のように信頼性尺度を用いて、どの修正クエリーがユーザに示されるかを選択し順序を定める。
【００６６】
一実施の形態では、修正サーバ１０７は、信頼性尺度を用いて、クエリー修正を全て表示するかどうか、表示するならその修正またはそれへのリンクを、どれくらい目立つように配置するかを決定する。そのために、修正サーバ１０７は、先に説明した最初の信頼性尺度か、上記の動的に生成した信頼性尺度のどちらかを用いることができる。例えば、最良の信頼性尺度が閾値未満になる場合、これは、どの潜在的候補修正も非常に良好とは言えず、その場合は、元の結果ページ２００に修正が行われないことを示唆する。他方、一つ以上の修正クエリーが、別の閾値を越える非常に高い信頼性尺度を有する場合、修正サーバ１０７は、クエリー修正、または修正クエリーページ３００へのリンクを、元の結果ページ２００上に非常に目立つように、例えば、ページの上部近くに、かつ目立つフォントで、またはどこか他の目立つ場所に、表示させることができる。信頼性尺度が、二つの閾値の間にある場合、修正クエリーページ３００へのリンクは少し目立たない場所、例えば、検索結果ページ２００の最後に、例えばリンク２０６について示すように、配置することができる。
【００６７】
上記説明の処理ステップは、並列で（例えば、クエリー修正の結果を得るステップと、クエリー修正の信頼性尺度を計算するステップとを並列に）、および／または交互に（例えば、全てのクエリー修正を受信してからクエリー修正リストを分類するステップではなく、クエリー修正手段から多数のクエリー修正を受信するステップと、オンザフライでクエリー修正の格納リストを構築するステップとを交互に）実行できる。さらに、上記実施の形態はクライアント／サーバ検索システムに関連して説明しているが、本発明は、スタンドアロン型マシン（例えば、スタンドアロン型ＰＣ）の一部として実施することもできる。これは例えば、Google Desktop Searchのようなデスクトップ検索アプリケーションの状況では有用である。
【００６８】
一つの可能性のある実施の形態に対して、特に詳細に本発明を説明してきた。当該分野の技術者には言うまでもなく、本発明は他の実施の形態で実践できる。第１に、構成体の特定の名称、用語の大文字化、属性、データ構造、または何らかの他のプログラミングもしくは構造的局面は、必須でも重要でもなく、本発明またはその特徴を実施するメカニズムは、異なる名称、フォーマット、またはプロトコルを持っていてもよい。さらに、本システムは、上記したように、ハードウエアとソフトウエアとの組み合わせにより実施してもよく、または全体的にハードウエア要素で実施してもよい。また、本明細書で説明した各種システム構成体間の特定の機能分割は、単なる例示であって必須ではなく；単一システム構成体により実行される機能は、代替として多数の構成体により実行することができ、多数の構成体により実行される機能は、代替として単一構成体により実行してもよい。
【００６９】
上記説明の幾つかの部分は、情報に関する操作のアルゴリズムおよびシンボル表現の点から本発明の特徴を表している。これらのアルゴリズム説明および表現は、データ処理分野の技術者が、彼らの業務内容を他の当該分野の技術者に伝えるために用いる最も効果的な手段である。これらの操作は、機能的または論理的に説明したが、言うまでもなくコンピュータプログラムにより実施される。さらに、これらの操作の編成を、一般性を失わずにモジュールとしてまたは機能名称により参照するのは、時として便利であることも判明している。
【００７０】
上記説明から明らかなように他に特別に言及しない限り、言うまでもなく、説明全体を通じて説明した行動および処理は、コンピュータシステムメモリもしくはレジスタまたは他のそのような情報の格納、送信、もしくはディスプレイ装置内の物理量（電子量）として表されるデータを操作し、変換するコンピュータシステム、または類似の電子計算装置によるものである。このようなコンピュータシステムの基底をなすハードウエアの詳細な説明は、コンピュータ工学分野の技術者には周知の情報なので、本明細書では提供しない。
【００７１】
本発明の特定態様は、本明細書においてアルゴリズムの形式で説明した処理ステップおよび命令を含む。注意すべきは、本発明の処理ステップおよび命令は、ソフトウエア、ファームウエア、またはハードウエアで組み込むことができ、ソフトウエアに組み込む場合は、リアルタイムのネットワークオペレーティングシステムが用いる異なるプラットフォームに常駐させて、操作するようダウンロードできる、ということである。
【００７２】
本発明の特定態様について個々または単一の実施例について説明してきたが；言うまでもなく、本発明の動作はこの観点に制限されない。従って、単一の要素または構成体への全ての参照は、複数のこのような構成体をも参照していると解釈すべきである。同様に、「或る」、または「その」への参照は、他に特別に言及しない限り、複数への参照を含むと解釈すべきである。最後に、用語「複数」の意味は、説明中の本発明の部分に見合う二つ以上の実体やデータ項目等を指し、無限またはさもなくば過剰なほどの項目数を含む。
【００７３】
本発明は、本明細書の動作を実行するための装置にも関連する。本装置は、要求する目的のために特別に構成してもよく、またはコンピュータがアクセスできるコンピュータ可読媒体上に格納されるコンピュータプログラムにより、選択的に作動または再構成される汎用コンピュータを備えてもよい。このようなコンピュータプログラムは、限定はしないが、フレキシブル磁気ディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスクを含む任意の種類のディスク、リードオンリーメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カードや光カード、または電子命令を格納するための、それぞれがコンピュータシステムバスに接続される任意の種類の媒体、のような、コンピュータ可読格納媒体内に格納できる。集積回路設計およびビデオコーデックの分野の技術者には言うまでもなく、本発明は、上記機能および構造説明に基づいて、特定用途向け集積回路（ＡＳＩＣ）を含む多様な種類の集積回路内で容易に製作できる。さらに、本発明は、多様な種類のビデオコーディング装置内に組み込むことができる。
【００７４】
本明細書で提示したアルゴリズムおよび操作は、何らかの特定コンピュータまたは他の装置とは本質的に関連しない。多様な汎用システムを本明細書の教示に基づくプログラムとともに用いることもでき、またはより専用化した装置を構築して、要求される方法ステップを実行すると好都合であることがわかる。これらの多様なシステムに要求される構成は、等価な改変と併せて、当該分野の技術者には明らかであろう。さらに、何らかの特定プログラミング言語を参照して本発明を説明していない。言うまでもなく、多様なプログラミング言語を用いて、本明細書で説明した本発明の教示を実施でき、どのような特定言語の参照であっても、本発明の可能性の開示および最良の態様が提供される。
【００７５】
最後に、注意すべきは、本明細書で用いられる言語は、原則として可読性および説明目的のために選択されていて、進歩性のある主題を範囲設定したり、または制限するために選択したものではない。従って、本発明の開示は、本発明の説明を意図したものであって、制限する意図はない。
【符号の説明】
【００７６】
１０２ フロントエンドサーバ
１０７ 修正サーバ
１１８ クライアント
【特許請求の範囲】
【請求項１】
サーバコンピュータシステムによって実行される方法であって、
複数のクエリー対のそれぞれについての発生頻度を計算するステップと、前記各クエリー対は最初のクエリーと修正クエリーとからなり、前記各クエリー対の発生頻度とは１以上のユーザーセッションにおける前記最初のクエリーの発生回数に対する前記修正クエリーの発生回数の比であり、
前記複数のクエリー対の各クエリー対毎に品質得点の改善分を計算するステップと、ここで、前記品質得点の改善分は、該クエリー対内の前記最初のクエリーに関するクリック行動データに対比して、該クエリー対内の前記修正クエリーに関するクリック行動データから引き出されるものであり、
前記各クエリー対の前記計算した発生頻度と前記品質得点に少なくとも部分的に基づいて、各クエリー対の信頼性尺度を計算するステップと、
計算した前記各信頼性尺度に基づき、前記複数のクエリー対の１又は複数を選択するステップと、
前記選択された１又は複数のクエリー対のそれぞれの前記修正クエリーを、該選択されたクエリー対の前記最初のクエリーについての示唆された修正として、提供するステップと、
を備える方法。
【請求項２】
前記修正クエリーに関するクリック行動データは、該修正クエリーに応じた検索結果に対するユーザによる複数クリックの持続時間に基づくものである、請求項１の方法。
【請求項３】
前記複数クリックにおける１クリックの持続時間とは、連続的に生じた２クリック間の発生時間間隔に基づくものである、請求項２の方法。
【請求項４】
前記クエリー対における前記修正クエリーに関するクリック行動データは、該クエリー対における前記最初のクエリーに関するクリック行動データよりも高いレベルのユーザ満足度を示すものである、請求項１乃至３のいずれかの方法。
【請求項５】
前記複数のクエリー対の１又は複数を選択するステップは、各信頼性尺度に基づき複数のクエリー対を序列化することからなる、請求項１乃至4のいずれかの方法。
【請求項６】
前記選択された１又は複数のクエリー対のそれぞれは、所定の最小数以上の検索結果を生ずるものである、請求項１乃至５のいずれかの方法。
【請求項７】
前記選択された１又は複数のクエリー対のそれぞれは、所定の最小数以上の新たな検索結果を生ずるものである、請求項１乃至５のいずれかの方法。
【請求項８】
前記新たな検索結果とは、前記修正クエリーの各最初のクエリーに応じて最も高く序列化された複数の検索結果において発生していないものである、請求項７の方法。
【請求項９】
命令群を記憶したコンピュータ読み取り可能な記憶媒体と、
前記命令群を実行するために動作する１又は複数のコンピュータと
を備えるシステムであって、
前記命令群は、該コンピュータに、
複数のクエリー対のそれぞれについての発生頻度を計算する手順と、前記各クエリー対は最初のクエリーと修正クエリーとからなり、前記各クエリー対の発生頻度とは１以上のユーザーセッションにおける前記最初のクエリーの発生回数に対する前記修正クエリーの発生回数の比であり、
前記複数のクエリー対の各クエリー対毎に品質得点の改善分を計算する手順と、ここで、前記品質得点の改善分は、該クエリー対内の前記最初のクエリーに関するクリック行動データに対比して、該クエリー対内の前記修正クエリーに関するクリック行動データから引き出されるものであり、
前記各クエリー対の前記計算した発生頻度と前記品質得点に少なくとも部分的に基づいて、各クエリー対の信頼性尺度を計算する手順と
計算した前記各信頼性尺度に基づき、前記複数のクエリー対の１又は複数を選択する手順と、
前記選択された１又は複数のクエリー対のそれぞれの前記修正クエリーを、該選択されたクエリー対の前記最初のクエリーについての示唆された修正として、提供する手順と、
を実行させるものである、システム。
【請求項１０】
前記修正クエリーに関するクリック行動データは、該修正クエリーに応じた検索結果に対するユーザによる複数クリックの持続時間に基づくものである、請求項９のシステム。
【請求項１１】
前記複数クリックにおける１クリックの持続時間とは、連続的に生じた２クリック間の発生時間間隔に基づくものである、請求項１０のシステム。
【請求項１２】
前記クエリー対における前記修正クエリーに関するクリック行動データは、該クエリー対における前記最初のクエリーに関するクリック行動データよりも高いレベルのユーザ満足度を示すものである、請求項９乃至１１のいずれかのシステム。
【請求項１３】
前記複数のクエリー対の１又は複数を選択することは、各信頼性尺度に基づき複数のクエリー対を序列化することからなる、請求項９乃至１２のいずれかのシステム。
【請求項１４】
前記選択された１又は複数のクエリー対のそれぞれは、所定の最小数以上の検索結果を生ずるものである、請求項９乃至１３のいずれかのシステム。
【請求項１５】
前記選択された１又は複数のクエリー対のそれぞれは、所定の最小数以上の新たな検索結果を生ずるものである、請求項９乃至１３のいずれかのシステム。
【請求項１６】
前記新たな検索結果とは、前記修正クエリーの各最初のクエリーに応じて最も高く序列化された複数の検索結果において発生していないものである、請求項１５のシステム。
【請求項１７】
命令群を記憶したコンピュータ読み取り可能な記憶媒体であって、前記命令群は、コンピュータに、
複数のクエリー対のそれぞれについての発生頻度を計算する手順と、前記各クエリー対は最初のクエリーと修正クエリーとからなり、前記各クエリー対の発生頻度とは１以上のユーザーセッションにおける前記最初のクエリーの発生回数に対する前記修正クエリーの発生回数の比であり、
前記複数のクエリー対の各クエリー対毎に品質得点の改善分を計算する手順と、ここで、前記品質得点の改善分は、該クエリー対内の前記最初のクエリーに関するクリック行動データに対比して、該クエリー対内の前記修正クエリーに関するクリック行動データから引き出されるものであり、
前記各クエリー対の前記計算した発生頻度と前記品質得点に少なくとも部分的に基づいて、各クエリー対の信頼性尺度を計算する手順と
計算した前記各信頼性尺度に基づき、前記複数のクエリー対の１又は複数を選択する手順と、
前記選択された１又は複数のクエリー対のそれぞれの前記修正クエリーを、該選択されたクエリー対の前記最初のクエリーについての示唆された修正として、提供する手順と、
を実行させるものである、コンピュータ読み取り可能な記憶媒体。
【請求項１８】
前記修正クエリーに関するクリック行動データは、該修正クエリーに応じた検索結果に対するユーザによる複数クリックの持続時間に基づくものである、請求項１７のコンピュータ読み取り可能な記憶媒体。
【請求項１９】
前記複数クリックにおける１クリックの持続時間とは、連続的に生じた２クリック間の発生時間間隔に基づくものである、請求項１８のコンピュータ読み取り可能な記憶媒体。
【請求項２０】
前記クエリー対における前記修正クエリーに関するクリック行動データは、該クエリー対における前記最初のクエリーに関するクリック行動データよりも高いレベルのユーザ満足度を示すものである、請求項１７乃至１９のいずれかのコンピュータ読み取り可能な記憶媒体。
【請求項２１】
前記複数のクエリー対の１又は複数を選択することは、各信頼性尺度に基づき複数のクエリー対を序列化することからなる、請求項１７乃至２０のいずれかのコンピュータ読み取り可能な記憶媒体。
【請求項２２】
前記選択された１又は複数のクエリー対のそれぞれは、所定の最小数以上の検索結果を生ずるものである、請求項１７乃至２１のいずれかのコンピュータ読み取り可能な記憶媒体。
【請求項２３】
前記選択された１又は複数のクエリー対のそれぞれは、所定の最小数以上の新たな検索結果を生ずるものである、請求項１７乃至２１のいずれかのコンピュータ読み取り可能な記憶媒体。
【請求項２４】
前記新たな検索結果とは、前記修正クエリーの各最初のクエリーに応じて最も高く序列化された複数の検索結果において発生していないものである、請求項２３のコンピュータ読み取り可能な記憶媒体。
【請求項１】
サーバコンピュータシステムによって実行される方法であって、
複数のクエリー対のそれぞれについての発生頻度を計算するステップと、前記各クエリー対は最初のクエリーと修正クエリーとからなり、前記各クエリー対の発生頻度とは１以上のユーザーセッションにおける前記最初のクエリーの発生回数に対する前記修正クエリーの発生回数の比であり、
前記複数のクエリー対の各クエリー対毎に品質得点の改善分を計算するステップと、ここで、前記品質得点の改善分は、該クエリー対内の前記最初のクエリーに関するクリック行動データに対比して、該クエリー対内の前記修正クエリーに関するクリック行動データから引き出されるものであり、
前記各クエリー対の前記計算した発生頻度と前記品質得点に少なくとも部分的に基づいて、各クエリー対の信頼性尺度を計算するステップと、
計算した前記各信頼性尺度に基づき、前記複数のクエリー対の１又は複数を選択するステップと、
前記選択された１又は複数のクエリー対のそれぞれの前記修正クエリーを、該選択されたクエリー対の前記最初のクエリーについての示唆された修正として、提供するステップと、
を備える方法。
【請求項２】
前記修正クエリーに関するクリック行動データは、該修正クエリーに応じた検索結果に対するユーザによる複数クリックの持続時間に基づくものである、請求項１の方法。
【請求項３】
前記複数クリックにおける１クリックの持続時間とは、連続的に生じた２クリック間の発生時間間隔に基づくものである、請求項２の方法。
【請求項４】
前記クエリー対における前記修正クエリーに関するクリック行動データは、該クエリー対における前記最初のクエリーに関するクリック行動データよりも高いレベルのユーザ満足度を示すものである、請求項１乃至３のいずれかの方法。
【請求項５】
前記複数のクエリー対の１又は複数を選択するステップは、各信頼性尺度に基づき複数のクエリー対を序列化することからなる、請求項１乃至4のいずれかの方法。
【請求項６】
前記選択された１又は複数のクエリー対のそれぞれは、所定の最小数以上の検索結果を生ずるものである、請求項１乃至５のいずれかの方法。
【請求項７】
前記選択された１又は複数のクエリー対のそれぞれは、所定の最小数以上の新たな検索結果を生ずるものである、請求項１乃至５のいずれかの方法。
【請求項８】
前記新たな検索結果とは、前記修正クエリーの各最初のクエリーに応じて最も高く序列化された複数の検索結果において発生していないものである、請求項７の方法。
【請求項９】
命令群を記憶したコンピュータ読み取り可能な記憶媒体と、
前記命令群を実行するために動作する１又は複数のコンピュータと
を備えるシステムであって、
前記命令群は、該コンピュータに、
複数のクエリー対のそれぞれについての発生頻度を計算する手順と、前記各クエリー対は最初のクエリーと修正クエリーとからなり、前記各クエリー対の発生頻度とは１以上のユーザーセッションにおける前記最初のクエリーの発生回数に対する前記修正クエリーの発生回数の比であり、
前記複数のクエリー対の各クエリー対毎に品質得点の改善分を計算する手順と、ここで、前記品質得点の改善分は、該クエリー対内の前記最初のクエリーに関するクリック行動データに対比して、該クエリー対内の前記修正クエリーに関するクリック行動データから引き出されるものであり、
前記各クエリー対の前記計算した発生頻度と前記品質得点に少なくとも部分的に基づいて、各クエリー対の信頼性尺度を計算する手順と
計算した前記各信頼性尺度に基づき、前記複数のクエリー対の１又は複数を選択する手順と、
前記選択された１又は複数のクエリー対のそれぞれの前記修正クエリーを、該選択されたクエリー対の前記最初のクエリーについての示唆された修正として、提供する手順と、
を実行させるものである、システム。
【請求項１０】
前記修正クエリーに関するクリック行動データは、該修正クエリーに応じた検索結果に対するユーザによる複数クリックの持続時間に基づくものである、請求項９のシステム。
【請求項１１】
前記複数クリックにおける１クリックの持続時間とは、連続的に生じた２クリック間の発生時間間隔に基づくものである、請求項１０のシステム。
【請求項１２】
前記クエリー対における前記修正クエリーに関するクリック行動データは、該クエリー対における前記最初のクエリーに関するクリック行動データよりも高いレベルのユーザ満足度を示すものである、請求項９乃至１１のいずれかのシステム。
【請求項１３】
前記複数のクエリー対の１又は複数を選択することは、各信頼性尺度に基づき複数のクエリー対を序列化することからなる、請求項９乃至１２のいずれかのシステム。
【請求項１４】
前記選択された１又は複数のクエリー対のそれぞれは、所定の最小数以上の検索結果を生ずるものである、請求項９乃至１３のいずれかのシステム。
【請求項１５】
前記選択された１又は複数のクエリー対のそれぞれは、所定の最小数以上の新たな検索結果を生ずるものである、請求項９乃至１３のいずれかのシステム。
【請求項１６】
前記新たな検索結果とは、前記修正クエリーの各最初のクエリーに応じて最も高く序列化された複数の検索結果において発生していないものである、請求項１５のシステム。
【請求項１７】
命令群を記憶したコンピュータ読み取り可能な記憶媒体であって、前記命令群は、コンピュータに、
複数のクエリー対のそれぞれについての発生頻度を計算する手順と、前記各クエリー対は最初のクエリーと修正クエリーとからなり、前記各クエリー対の発生頻度とは１以上のユーザーセッションにおける前記最初のクエリーの発生回数に対する前記修正クエリーの発生回数の比であり、
前記複数のクエリー対の各クエリー対毎に品質得点の改善分を計算する手順と、ここで、前記品質得点の改善分は、該クエリー対内の前記最初のクエリーに関するクリック行動データに対比して、該クエリー対内の前記修正クエリーに関するクリック行動データから引き出されるものであり、
前記各クエリー対の前記計算した発生頻度と前記品質得点に少なくとも部分的に基づいて、各クエリー対の信頼性尺度を計算する手順と
計算した前記各信頼性尺度に基づき、前記複数のクエリー対の１又は複数を選択する手順と、
前記選択された１又は複数のクエリー対のそれぞれの前記修正クエリーを、該選択されたクエリー対の前記最初のクエリーについての示唆された修正として、提供する手順と、
を実行させるものである、コンピュータ読み取り可能な記憶媒体。
【請求項１８】
前記修正クエリーに関するクリック行動データは、該修正クエリーに応じた検索結果に対するユーザによる複数クリックの持続時間に基づくものである、請求項１７のコンピュータ読み取り可能な記憶媒体。
【請求項１９】
前記複数クリックにおける１クリックの持続時間とは、連続的に生じた２クリック間の発生時間間隔に基づくものである、請求項１８のコンピュータ読み取り可能な記憶媒体。
【請求項２０】
前記クエリー対における前記修正クエリーに関するクリック行動データは、該クエリー対における前記最初のクエリーに関するクリック行動データよりも高いレベルのユーザ満足度を示すものである、請求項１７乃至１９のいずれかのコンピュータ読み取り可能な記憶媒体。
【請求項２１】
前記複数のクエリー対の１又は複数を選択することは、各信頼性尺度に基づき複数のクエリー対を序列化することからなる、請求項１７乃至２０のいずれかのコンピュータ読み取り可能な記憶媒体。
【請求項２２】
前記選択された１又は複数のクエリー対のそれぞれは、所定の最小数以上の検索結果を生ずるものである、請求項１７乃至２１のいずれかのコンピュータ読み取り可能な記憶媒体。
【請求項２３】
前記選択された１又は複数のクエリー対のそれぞれは、所定の最小数以上の新たな検索結果を生ずるものである、請求項１７乃至２１のいずれかのコンピュータ読み取り可能な記憶媒体。
【請求項２４】
前記新たな検索結果とは、前記修正クエリーの各最初のクエリーに応じて最も高く序列化された複数の検索結果において発生していないものである、請求項２３のコンピュータ読み取り可能な記憶媒体。
【図１ａ】
【図１ｂ】
【図２】
【図３】
【図１ｂ】
【図２】
【図３】
【公開番号】特開２０１１−２４８９１４（Ｐ２０１１−２４８９１４Ａ）
【公開日】平成２３年１２月８日（２０１１．１２．８）
【国際特許分類】
【出願番号】特願２０１１−１５８４９５（Ｐ２０１１−１５８４９５）
【出願日】平成２３年７月１９日（２０１１．７．１９）
【分割の表示】特願２００８−５０４００１（Ｐ２００８−５０４００１）の分割
【原出願日】平成１７年３月３０日（２００５．３．３０）
【出願人】（５０５２８１０６７）グーグル インコーポレイテッド (58)
【氏名又は名称原語表記】ＧＯＯＧＬＥ ＩＮＣ．
【公開日】平成２３年１２月８日（２０１１．１２．８）
【国際特許分類】
【出願日】平成２３年７月１９日（２０１１．７．１９）
【分割の表示】特願２００８−５０４００１（Ｐ２００８−５０４００１）の分割
【原出願日】平成１７年３月３０日（２００５．３．３０）
【出願人】（５０５２８１０６７）グーグル インコーポレイテッド (58)
【氏名又は名称原語表記】ＧＯＯＧＬＥ ＩＮＣ．
[ Back to top ]