JP4809441B2 - ユーザログからの検索カテゴリ同義語の推定 - Google Patents

Description

発明の分野
本発明の原理に合致する実施形態は、一般的にクエリ処理に関し、さらに詳しくは、検索クエリの洗練化をもたらすことに関する。

背景
インターネットは１９６０年代末にさかのぼるが、パーソナルコンピューティングおよびインターネットワーキングが広く利用可能になりかつ受け入れられた結果、情報共有化技術の爆発的成長および空前の躍進がもたらされた。特に、ワールドワイドウェブ（「ウェブ」）は、アーカイブフォーマットおよびリアルタイムフォーマットの両方で、書面、発話（音声）、および視覚的（画像およびビデオ）情報を含め、世界中の視聴者に対する格納された電子形式の莫大な量の情報へのアクセス性に革命をもたらした。要するに、ウェブは、接続された全てのユーザに世界中のほとんどすべての言語の事実上無限の情報ライブラリへのデスクトップアクセスを提供してきた。

検索エンジンはウェブの増大する使用とテンポを合わせて進化し、ユーザが関連ウェブコンテンツを効率的にかつ適時に見つけて取り出すことを可能にした。ウェブコンテンツの量および種類が増大するにつれて、検索エンジンの精巧さおよび正確さも同様に改善された。一般的に、検索エンジンは検索クエリに応答して最高品質の結果を提供するように努める。しかし、検索されたウェブコンテンツの妥当性（適合率）は本質的に主観的であり、ユーザの関心、知識、および態度に依存するので、品質を決定することは難しい。

検索エンジンによって使用される既存の方法は、検索クエリ語をウェブページからインデックス化された語と照合することに基づく。より高度の方法は、例えばハイパーリンク構造に基づく解析を用いて、検索されたウェブコンテンツの重要度を決定する。

典型的な検索クエリシナリオは、自然言語質問またはしばしばキーワードの形の個別語のいずれかを検索エンジンに提出することから始まる。検索エンジンは、潜在的に検索可能なウェブコンテンツの情報特性を記述するデータリポジトリに対して検索を実行し、候補ウェブページを識別する。検索はしばしば数千または数百万もの結果を返すことがあり得るので、ほとんどの検索エンジンは一般的に最も有望な結果の部分集合だけをランク付けまたは点数化する。次いでトップのウェブページが、通常、ウェブコンテンツのタイトル、ハイパーリンク、およびウェブページから取り出されたテキストの抜粋のような他の記述的情報の形で、ユーザに提示される。

良質の検索結果の提供は、検索クエリ自体の字義通りおよび暗黙の範囲によって複雑になることがあり得る。適切にフレーム化されない検索クエリは曖昧であるか、または一般的もしくは特定的過ぎて、即応的な高品質の検索結果を生み出すことができないであろう。例えば、検索クエリ内の語は、統語論的または意味論的レベルで曖昧になり得る。統語論的曖昧さは、同じ発音およびおそらく同じ綴りを有するが、実際に意図する語とは異なる意味を持つ間違った語を指定する、偶発的同音異義語の結果、起こり得る。例えば語「ｂｅａｒ」は、動物または衣服の欠如を意味または指すことがあり得る。意味論的曖昧さは、不適切な文脈の結果、起こり得る。例えば、語「ｊａｇｕａｒ」は動物、マッキントッシュのオペレーティングシステムのバージョン、または自動車のブランドを指すことがあり得る。同様に、一般的過ぎる検索語は過度に広範囲の検索結果を生じる一方、狭すぎる検索語は不当に制限された非即応的な検索結果を生じる。

したがって適切にフレーム化された検索クエリで生じる曖昧さまたは過度の一般性もしくは過度の特異性を解消する、検索クエリの洗練化のための提案を提供する方法が必要である。好ましくは、そのような方法は、発行された場合に、元の検索クエリの意図の根底にある実際のトピックに密接に関係する検索結果を生じると共に、潜在的検索語として概念的独立性および明確な意味を反映する提案を提供する、洗練された検索クエリを提供する。

概要
本発明の原理に合致する一実施形態によると、方法は、先行の結果データに関する少なくともクエリ情報およびカテゴリ情報を含む先行のクエリデータを識別し、クエリ情報がカテゴリ情報の同義語であるか否かを判断し、およびクエリ情報がカテゴリ情報の同義語であると判断された場合、クエリ情報およびカテゴリ情報を後続の検索要求で使用する。

本発明の原理に合致する別の実施形態によると、システムは、先行の検索結果内に含まれるクエリデータおよびカテゴリデータがカテゴリ同義語であるか否かを決定するための手段と、クエリデータおよびカテゴリデータがカテゴリ同義語であると決定された場合、カテゴリデータに関連付けられたクエリデータを後続の検索要求に組み込むための手段とを含むことができる。

本発明の原理に合致するさらに別の実施形態によると、装置は、先行の検索要求に関連付けられる少なくとも１つのクエリ・カテゴリ対を含む履歴ログデータを識別するためのロジックと、クエリ・カテゴリ対におけるクエリが名前クエリであるかカテゴリクエリであるかを決定するためのロジックと、クエリがカテゴリクエリであると決定された場合、クエリがカテゴリの同義語であるか否かを決定するためのロジックとを含むことができる。

本発明の原理に合致するさらに別の実施形態によると、方法は、クライアントから検索クエリを受信し、受信した検索クエリに基づいて結果カテゴリを識別し、識別された結果カテゴリのカテゴリ同義語を識別し、結果カテゴリおよび識別されたカテゴリ同義語に基づいて結果検索を実行することができる。

本明細書に組み込まれ、その一部を構成する添付の図面は本発明の実施形態を示し、記述と共に本発明を説明する。

詳細な説明
本発明の原理に合致する実施形態の以下の詳細な説明は、添付の図面を参照する。異なる図面における同一参照番号は、同一または同様の要素を識別するかもしれない。また、以下の詳細な説明は本発明を限定するものではない。

概説
検索エンジンを介して探索可能になるドキュメントの量は実質的に増加している。したがって、関連ドキュメントを見つけるために送信される検索クエリは、潜在的曖昧さまたは一般性の問題を生じ易くなるかもしれない。初期クエリの不備を是正することができ、または追加的関連ドキュメントを識別するように初期検索クエリを拡張することができる、検索クエリの洗練化（ｒｅｆｉｎｅｍｅｎｔｓ）を識別して提供することが有益である。本書で説明するように、検索クエリの洗練化は、ユーザがより迅速かつより正確に望ま
しい検索結果を識別するのを助けるように、自動的に生成することができる。さらに詳しくは、検索可能な情報を予め定められた様々なカテゴリに割り当てるか、または分解することができる。例えば「Ｊｏｅ’ｓ Ｂａｒ ａｎｄ Ｇｒｉｌｌ」に対するリストは、「バー」および「居酒屋」の両方のカテゴリに割り当てることができる。本発明の原理によると、カテゴリ同義語は以前の結果データ内から識別することができ、それによって検索可能な情報の検索強化を可能にすることができる。次いで、要求された検索を実行する際に、識別されたカテゴリ同義語を、予め定められたカテゴリと共に使用することができる。

図１は、本発明の原理に合致する概念を示す例示的図である。（Ａ）に示す通り、ユーザは、ウェブブラウザを用いて、ウェブページ１００のようなウェブドキュメントにアクセスすることができる。また（Ａ）に示す通り、ウェブブラウザは、ユーザから初期検索クエリを受け取るための検索クエリ入力ボックス１０２を含む。例示的実現では、検索クエリ入力ボックス１０２は、おそらくバージニア州フェアファックスの弁護士に関する情報を要求して、「弁護士 バージニア州フェアファックス（ａｔｔｏｒｎｅｙ Ｆａｉｒｆａｘ，ＶＡ）」のような語句を含むことができる。

本発明の原理によると、入力されたクエリの送信により、送信されたクエリに基づくだけでなく、クエリ語に対して識別されたカテゴリ同義語にも基づく検索結果を含む、（Ｂ）に示すウェブページ１０４のようなウェブドキュメントが得られるかもしれない。例示的実施形態では、次の修正されたクエリ、すなわち（単数の弁護士（ａｔｔｏｒｎｅｙ）ＯＲ複数の弁護士（ａｔｔｏｒｎｅｙｓ）ＯＲ単数の法律家（ｌａｗｙｅｒ）ＯＲ複数の法律家（ｌａｗｙｅｒｓ））ＡＮＤ「バージニア州フェアファックス（Ｆａｉｒｆａｘ，ＶＡ）」に基づいて、結果を表示することができる。以下でさらに詳述するように、検索クエリに適用される識別されたカテゴリの同義語は、提供された検索結果を得る際に、識別して使用することができる。さらに詳しくは、受信したクエリに対する後続の検索は、クエリ語、最初に識別されたカテゴリのみならず、先行の適正な検索結果に基づいてその後に識別されたカテゴリ同義語をも用いて、実行することができる。このようにして、検索結果の正確さおよび機能性の向上を達成することができる。

本書で使用される用語としての「ドキュメント」は、機械可読かつ機械格納可能な作業成果物を含むように広義に解釈される。ドキュメントは例えば電子メール、ウェブサイト、ファイル、ファイルの組合せ、他のファイルへのリンクが埋め込まれた１つまたはそれ以上のファイル、ニュースグループ投稿、ブログ、ビジネスリスティング、印刷テキストの電子バージョン、ウェブ広告等を含む。インターネットの文脈では、一般的なドキュメントはウェブページである。ドキュメントはしばしば文字情報を含み、（メタ情報、画像、ハイパーリンク等のような）埋込み情報および／または（Ｊａｖａｓｃｒｉｐｔ（登録商標）等のような）埋込み命令を含むことができる。本書で使用される用語としての「リンク」は、ドキュメントと別のドキュメントとの間の、または同一ドキュメント間の参照を含むように広義に解釈される。

例示的ネットワーク構成
図２は、本発明の原理に合致するシステムおよび方法が実現されるネットワーク２００の例示的図である。ネットワーク２００は、ネットワーク２５０を介して複数のサーバ２２０〜２４０に接続された複数のクライアント２１０を含む。分かり易くするために、２つのクライアント２１０および３つのサーバ２２０〜２４０が、ネットワーク２５０に接続されているように図示されている。実際には、より多数またはより少数のクライアントおよびサーバが存在する。また、場合によっては、クライアントがサーバの機能を果たすことがあり、かつサーバがクライアントの機能を果たすことがある。

クライアント２１０はクライアントエンティティを含む。エンティティは、パーソナルコンピュータ、ワイヤレス電話機、パーソナルデジタルアシスタント（ＰＤＡ）、ラップトップ、または別の種類のコンピューテーションもしくは通信装置のような装置、これらの装置の１つで実行されるスレッドもしくはプロセス、および／またはこれらの装置の１つによって実行可能なオブジェクトと定義することができる。クライアント２１０はさらに、クライアント２１０とサーバ２２０〜２４０との間のユーザインタフェースとして動作するように構成されたブラウザソフトウェアを含む。

サーバ２２０〜２４０は、本発明の原理に合致する方法でドキュメントまたは他の情報を収集、処理、検索、および／または維持するサーバエンティティを含む。本発明の原理に合致する実施形態では、サーバ２２０はクライアント２１０によって使用可能な検索エンジン２２５を含む。サーバ２２０はドキュメントの集積を巡回（ｃｒａｗｌ）し、ドキュメントをインデックス化し、ドキュメントに関連する情報をドキュメントのリポジトリに格納する。サーバ２３０および２４０は、サーバ２２０によって巡回または解析されるドキュメントを格納または維持してもよい。さらに、サーバ２２０〜２４０は、ドキュメントまたは情報のクライアント２１０への送信に関する１つまたはそれ以上のログをも維持してもよい。本発明の原理に合致する一実施形態では、そのようなログは、受信したユーザのクエリまたは要求に応答してどのドキュメントまたは情報がクライアント２１０に送信されたかに関する情報を含むかもしれない。さらに、サーバ２２０〜２４０からのドキュメントまたは情報の送信に応答してクライアント２１０がとったアクションを含め、追加の情報がログされてもよい。

サーバ２２０〜２４０は別個のエンティティとして図示されているが、サーバ２２０〜２４０の１つまたはそれ以上が、サーバ２２０〜２４０の別の１つまたはそれ以上の機能の１つまたはそれ以上を実行することが可能である。例えば、サーバ２２０〜２４０の２つまたはそれ以上を単一のサーバとして実現することが可能である。また、サーバ２２０〜２４０の１つを、２つまたはそれ以上の別個の（かつおそらく分散した）装置として実現することも可能である。

ネットワーク２５０はローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、公衆交換電話網ネットワーク（ＰＳＴＮ）のような電話網、イントラネット、インターネット、またはネットワークの組合せを含む。クライアント２１０およびサーバ２２０〜２４０は、有線、無線、および／または光接続を介して、ネットワーク２５０に接続することができる。

例示的クライアント／サーバアーキテクチャ
図３は、クライアント２１０および／またはサーバ２２０〜２４０の１つまたはそれ以上に対応する、クライアントまたはサーバエンティティ（以下、「クライアント／サーバエンティティ）という）の例示的図である。クライアント／サーバエンティティはバス３１０、プロセッサ３２０、主メモリ３３０、読出し専用メモリ（ＲＯＭ）３４０、記憶装置３５０、入力装置３６０、出力装置３７０、および通信インタフェース３８０を含む。バス３１０は、クライアント／サーバエンティティの要素の間の通信を可能にする経路を含む。

プロセッサ３２０は、プロセッサ、マイクロプロセッサ、または命令を解釈して実行する処理ロジックを含む。主メモリ３３０は、ランダムアクセスメモリ（ＲＡＭ）、またはプロセッサ３２０による実行のための情報および命令を格納する、別の種類のダイナミック記憶装置を含む。ＲＯＭ３４０はＲＯＭデバイス、またはプロセッサ３２０によって使用されるスタテック情報および命令を格納する、別の種類のスタテック記憶装置を含む。記憶装置３５０は、磁気および／または光記録媒体ならびにその対応するドライブを含む
。

入力装置３６０は、キーボード、マウス、ペン、音声認識および／またはバイオメトリックメカニズム等のような、オペレータが情報をクライアント／サーバエンティティに入力することを可能にするメカニズムを含む。出力装置３７０は、ディスプレイ、プリンタ、スピーカ等をはじめ、情報をオペレータに出力するメカニズムを含む。通信インタフェース３８０は、クライアント／サーバエンティティが他の装置および／またはシステムと通信することを可能にする、任意のトランシーバ類似のメカニズムを含む。例えば通信インタフェース３８０は、ネットワーク２５０のようなネットワークを介して、別の装置またはシステムと通信するためのメカニズムを含む。

以下で詳述するように、本発明の原理に合致するクライアント／サーバエンティティは、特定のクエリ処理関連動作を実行することができる。クライアント／サーバエンティティは、プロセッサ３２０がメモリ３３０のようなコンピュータ読取可能媒体に含まれるソフトウェア命令を実行することに応答して、これらの動作を実行する。コンピュータ読取可能媒体は、物理的または論理的メモリデバイスおよび／または搬送波として定義することができる。ソフトウェア命令は、記憶装置３５０のような別のコンピュータ読取可能媒体から、または別の装置から通信インタフェース３８０を介してメモリ３３０に読み込まれる。メモリ３３０に含まれるソフトウェア命令は、プロセッサ３２０に後述するプロセスを実行させる。代替的に、本発明の原理に合致するプロセスを実現するために、ソフトウェア命令の代わりに、またはそれと組み合わせて、配線された回路構成を使用することもできる。したがって、本発明の原理に合致する実現は、配線された回路構成およびソフトウェアの特定の組合せに限定されない。

例示的コンピュータ読取可能媒体
図４は、サーバ２２０〜２４０によって使用される例示的コンピュータ読取可能媒体４００の一部分の図である。一実施形態では、コンピュータ読取可能媒体４００はサーバ２２０のメモリ３３０に対応する。図４に示すコンピュータ読取可能媒体４００の部分は、オペレーティングシステム４１０、検索エンジンソフトウェア／ロジック４２０、およびクエリ洗練化ソフトウェア４３０を含む。

オペレーティングシステム４１０は、ウィンドウズ（登録商標）、ユニックス、またはリナックスオペレーティングシステムのようなオペレーティングシステムソフトウェアを含む。検索エンジンソフトウェア／ロジック４２０は、１つまたはそれ以上のクライアント２１０からクエリ情報を受信し、かつ受信したクエリに基づき関連検索結果を識別するためのメカニズムを提供する。クエリ洗練化ソフトウェア４３０は、以下で詳述する本発明の原理に従って受信したクエリに基づきクエリ洗練化を識別するソフトウェアを含む。本発明の原理に合致する一実施形態では、クエリ洗練化ソフトウェア４３０は検索エンジンソフトウェア／ロジック４２０に組み込むことができる。

同義語を識別するための例示的処理
図５は、本発明の原理に合致する実現において、同義語を識別するための例示的プロセスのフローチャートである。上で簡単に述べた通り、受信したユーザ検索クエリは多数の語または語句を含むことがあり、その一部分はクエリの全体的文脈に応じて適用される多数の同義語を有するかもしれない。例えば、本発明の原理に合致する一実施形態では、受信した検索クエリは、地方に限定されるビジネスまたは商業情報の検索に関連するかもしれない。一般的に、この形の検索クエリは名前および／またはカテゴリ情報を含む。さらに、そのような検索クエリは、ユーザに関連する予め定められた位置、表示される地図によって限定される地理的領域、または受信した検索クエリ自体に含まれる位置情報のような、何らかの形の位置情報をさらに含むかもしれない。ここでは主に地域検索情報につい
て説明するが、追加の実施形態では、他の標識化またはカテゴリ化された「ドキュメント」または情報を同様の仕方で検索することができる。例えば製品情報または価格検索では、予め定められた製品カテゴリに基づく製品の検索または識別が得られる。

地域検索の実行で認識される１つの問題は、検索可能な情報が一般的に名前、位置、およびカテゴリに基づいてリストされ格納されることである。多くの場合、そのような情報は、地域イエローページまたはビジネスリストディレクトリのようなリストソースによって提供される。リスト情報はそれ以外では事業名から収集されない情報（例えばカテゴリ情報）を含むので、強化された検索を実行することができる。残念ながら、割り当てられたカテゴリ情報は１つの特定の語もしくは語句に、または幾つかの特定の語もしくは語句にさえ限定されることがある。例えば、全ての軽食屋は「レストラン」カテゴリの下にリストされる一方、検索クエリは語「食堂」を含むかもしれない。検索クエリの純粋な統語論を使用して関連検索を実行すると、場合によっては「レストラン」が「食堂」の適切な同義語であることを認識し損なう。したがって関連検索は、検索の実行にレストランカテゴリを含まず、代わりに「食堂」を排他的に検索する。

本発明の原理によると、受信した検索クエリは、クエリ洗練化ソフトウェア４３０によって、以前の検索クエリ／結果の組合せに基づく増強または追加カテゴリを含むように洗練化される。図５を参照すると、処理は過去の検索および結果のログから「適正な（ｇｏｏｄ）」または関連する「トリプル（ｔｒｉｐｌｅｓ）」を識別することによって開始される（アクト（ａｃｔ）５００）。本書で使用する場合、用語「トリプル」は、一般的に先行するクエリ結果を表わすデータを含むように定義することができる。さらに詳しくは、「トリプル」は、１）クエリ語、２）結果の事業名、および、３）結果のビジネスカテゴリを含む。さらに、識別された「トリプル」が「適正」であるか否かの決定は、適切な因子に基づく。

本発明の原理に合致する一実施形態では、「適正な」トリプルは、それにより予め定められたアクションが受信されたトリプルと識別される。例えば１つの例示的実施形態では、ビジネスリストを含む情報をクライアント２１０に供給することに加えて、サーバ２２０〜２４０は、ドライビング（ｄｒｉｖｉｎｇ）方向、電子メールリンク、リストに関連付けられたウェブサイトへのリンク等のような、各リストに関する追加情報または機能性をも提供することができる。そのような実施形態では、適正なトリプルは、クライアント２１０がそれに関して予め定められたユーザアクションをサーバ２２０〜２４０に送信したリストに関連付けられるトリプルと識別することができる。１つの特定の実施形態では、ユーザ行動は、ドライビング方向のためのリンク上でクリックすることであるかもしれない。

多くの格納されたリストは複数の事業名およびそれに関連付けられる複数のカテゴリを持つことに注目されたい。したがって、ドライビング方向のクリック（または他の「適合度」標識）は複数のクエリ‐名前‐カテゴリのトリプルを生じさせる。例えば、受信した「バー」のクエリは、２つのカテゴリすなわち「バー」および「居酒屋」を持つ特定のリスト「Ｊｏｅ’ｓ Ｂａｒ ａｎｄ Ｇｒｉｌｌ」と適合するかもしれない。この実施例では、１）（単数バー（ｂａｒ）、「Ｊｏｅ’ｓ Ｂａｒ ａｎｄ Ｇｒｉｌｌ」、複数バー（ｂａｒｓ））、および、２）（バー（ｂａｒ）、「Ｊｏｅ’ｓ Ｂａｒ ａｎｄ Ｇｒｉｌｌ」、居酒屋（ｔａｖｅｒｎｓ））の２つの個別のクエリ‐名前‐カテゴリのトリプルが観察される。リストに対して２つの適正な「トリプル」が存在すると仮定して、トリプルをどのようにカウントするかの問題が生じる。本発明の原理に合致する一実施形態では、上記トリプルの各々が０．５のカウント（１．０ではなく）を有するものとして取り扱うことができる。同様に、クエリの結果３つのトリプルが識別される実施例では、各トリプルを０．３３３のカウントとして取り扱うことができる。すなわち、単一リスト
加重（１．０）が、それに関連付けられる複数のトリプルの間で均等に分配される。このようにして、データセット全体の総和が正確に観察結果になる。

ひとたび適正なトリプルが識別されると、適正なトリプルに関連付けられたクエリは、「名前クエリ」または「カテゴリクエリ」として分類される（アクト５０２）。本書で定義される場合、「名前クエリ」は、事業名に関連するクエリ語（例えば「中華風ビュッフェ」）を含み、「カテゴリクエリ」は潜在的ビジネスカテゴリに関するクエリ語（例えば「中華レストラン」）を含む。２種類のクエリを区別することによって、識別されたカテゴリが、名前クエリに同義語として割り当てられることが防止される。

本発明の原理に合致する一実施形態によると、名前クエリ／カテゴリクエリの決定は、各々の識別されたクエリに関連付けられる「名前エントロピ（ｎａｍｅ ｅｎｔｒｏｐｙ）」または「名前パープレキシティ（ｎａｍｅ ｐｅｒｐｌｅｘｉｔｙ）」の程度に基づいて行なわれる。この目標に向かって、各クエリの名前名前パープレキシティは次式によって表わすことができる。

ここで、クエリがアクト５００で選択された結果から推定されると仮定して、Ｈ（ｎａｍｅ|ｑｕｅｒｙ）は事業名の条件付き名前エントロピである。名前エントロピは次式によって定義することができる。

ここでＰ（ｎａｍｅ|ｑｕｅｒｙ）は、クエリを前提として名前が返される確率である。
換言すると、クエリが事業名を含む可能性は、クエリと対を成す事業名の個数に基づいて決定される。数個の事業名と対を成すクエリは名前クエリ（例えば低い名前パープレキシティ）とみなされる一方、より多くの異なる名前と対を成すクエリは、高い名前パープレキシティを有するとみなされる。エントロピの概念は、頻繁に使用される名前とまれにしか使用されない名前との間の加重を説明するために導入されることを理解されたい。

識別されたクエリが適正なクエリであり、かつカテゴリクエリであることがアクト５００および５０２でそれぞれ決定されると、結果のカテゴリおよび識別されたクエリを同義語として取り扱うべきであるか否かが決定される（アクト５０４）。例えば、アクト５００におけるクエリ‐結果の名前‐結果のカテゴリのリストの初期「適合度」の決定、およびアクト５０２で識別された高い名前パープレキシティ（すなわち多くの事業名がこのクエリと対を成す）に基づいて、カテゴリ「レストラン‐中華」はクエリ「中華レストラン」のカテゴリ同義語と決定することができる。そのような決定が成された場合、識別されたカテゴリは関連クエリ語のカテゴリ同義語として指定することができ（アクト５０４）、それにより、クエリに関連付けられる後続の検索はさらに、カテゴリに関係する検索を呼び出すことが確保される。

残念ながら、アクト５００および５０２を通して転送されたクエリを単純に検討するだけでは、クエリ／カテゴリ下位語の可能性は説明されない。周知の通り、下位語とは、従
属するものまたは下位分類を意味する語である。例えば、ペンシルベニア州民はアメリカ人の下位語である。当面の問題に戻ると、中華レストランはカテゴリ「レストラン」の下位カテゴリであるので、観察されるクエリ「中華レストラン」はカテゴリ「レストラン」の下位語である。後者のクエリ・カテゴリ対は同等であるというよりむしろ包含を伴う（例えば中華レストランはレストランの１種であり、「レストラン」と同等ではない）ので、カテゴリ「レストラン」の同義語として使用すべきではない。

図６は、包含および同等クエリ・カテゴリ対を区別するための例示的プロセスのフローチャートである。包含型クエリ・カテゴリ対の排除を容易にするために、識別されたクエリ・カテゴリ対のＦ値が計算される（アクト６００）。本書で定義する場合、各対のＦ値は、クエリ・カテゴリ対が同義語として排除すべき下位語型または包含型の対である可能性と定義することができる。そのような計算は、次式によって表わすことができる。

上の式において、Ｐ（ｑｕｅｒｙ，ｃａｔｅｇｏｒｙ）は、カテゴリおよびクエリの両方が相互に同義語である同時確率を表わす。Ｐ（ｑｕｅｒｙ，ｃａｔｅｇｏｒｙ）およびＰ（ｃａｔｅｇｏｒｙ，ｑｕｅｒｙ）の値は、カテゴリおよびクエリ語が一緒に見られかつ望ましいユーザ行動（例えばドライビング方向リンクの選択）との関連付けによって「適正」と証明されるインスタンスの回数を、所望のユーザ行動が受信されたインスタンスの回数で除算することによって、推算することができる。

Ｐ（ｑｕｅｒｙ）の値は、クエリ語の結果望ましいユーザ行動が実行されたインスタンスの回数を、望ましいユーザ行動が受信されたインスタンスの回数で除算することによって、推算することができる。同様にＰ（ｃａｔｅｇｏｒｙ）の値は、識別されたカテゴリの結果望ましいユーザ行動が実行された回数を、望ましいユーザ行動が受信されたインスタンスの回数で除算することによって、推算することができる。

さらに、Ｐ（ｑｕｅｒｙ|ｃａｔｅｇｏｒｙ）は、カテゴリが与えられた場合のクエリの確率と定義することができ、Ｐ（ｃａｔｅｇｏｒｙ|ｑｕｅｒｙ）はクエリが得られた場合のカテゴリの確率である。それらはＰ（ｑｕｅｒｙ|カテゴリ）＝Ｐ（ｑｕｅｒｙ，ｃａｔｅｇｏｒｙ）／Ｐ（ｃａｔｅｇｏｒｙ）、およびＰ（ｃａｔｅｇｏｒｙ|ｑｕｅｒｙ）＝Ｐ（ｑｕｅｒｙ，ｃａｔｅｇｏｒｙ）／Ｐ（ｑｕｅｒｙ）と定義され、構成要素の以前の推算を用いて推算される。一般統計的観点では、次の通りである。

しかし、クエリおよびカテゴリの確率の文脈では、再現率はＰ（ｃａｔｅｇｏｒｙ|ｑｕｅｒｙ）であり、精度はＰ（ｑｕｅｒｙ|ｃａｔｅｇｏｒｙ）であり、Ｆ値はＰ（ｑｕｅｒｙ，ｃａｔｅｇｏｒｙ）／（ａ＊Ｐ（ｃａｔｅｇｏｒｙ）＋（１−ａ）＊Ｐ（ｑｕｅｒｙ））に等しく、その後に上記の定義が一般Ｆ値式に入力され、簡素化される。この文脈で用語「ｒｅｃａｌｌ（再現率）」および「ｐｒｅｃｉｓｉｏｎ（精度）」は次の検索実験に対するものである。すなわち所与のクエリおよびカテゴリに対し、クエリに応答し
て、そのカテゴリに合致する全ての結果が返される。

精度と再現率との間の適切なトレードオフは、定数「ａ」の値の選択を通して確立される。約０．７ないし０．９の範囲の値が精度と再現率との間の適切な妥協をもたらし、下位語が識別されたカテゴリ同義語内に含まれる可能性が正確に除去または低減されることが決定された。１つの例示的実施形態では、「ａ」の値は０．８５である。

選択されたクエリ・カテゴリ対に対するＦ値が決定されると、次いで、計算されたＦ値が予め定められた基準を満たすか否かが決定される（アクト６０２）。満たす場合、クエリ・カテゴリ対のクエリおよびカテゴリは同義語とみなされる（アクト６０４）。満たさない場合、クエリおよびカテゴリは同義語とみなされず、対は検討から排除される（アクト６０６）。

１つの例示的実現では、Ｆ値基準は、所与のクエリに対しより高いまたはより大きいＦ値を有するクエリ・カテゴリ対を決定するための任意の適切な方法を含むことができる。例えば、最高Ｆ値を有するクエリ・カテゴリ対だけを所与のクエリに対する相互の同義語と考慮すると決定することができる。代替的に、予め定められた上位の個数のクエリ・カテゴリ対を、所与のクエリに対する同義語とみなすことができる。さらに別の実現では、最大Ｆ値を決定することができ、この値の予め定められた百分率（例えば５０％）までの全てのクエリ・カテゴリ対を所与のクエリに対する同義語とみなすことができる。さらに別の実現では、最小要求Ｆ値を決定することができ、この値に適合またはそれを超えるクエリ・カテゴリ対を所与のクエリに対する同義語と識別することができる。

別の例示的実現において、Ｆ値を名前パープレキシティ、カテゴリパープレキシティ、およびクエリ頻度のような他の因子と組み合わせることができる。例えば同義語とみなされるために、クエリ・カテゴリ対は少なくとも２５の名前パープレキシティを有し、少なくとも５０のカテゴリパープレキシティ、少なくとも１／１，０００，０００のクエリ頻度を有する必要があるかもしれず、かつ０．０３、および最大測定Ｆ値の５０％の両方を超えるＦ値を持たなければならない。

同義語の決定に続き、処理すべき追加のクエリ・カテゴリ対が残っているかどうかが次いで決定される（アクト６０８）。残っている場合、プロセスは次のクエリ・カテゴリ対のためにアクト６００に戻る。処理すべき追加のクエリ・カテゴリ対が残っていない場合、プロセスは停止する。

本発明の原理に合致する１実現では、同義語対は、推定される同義語のその後の手動による検討のために、１つまたはそれ以上の「ラベラ（ｌａｂｅｌｌｅｒ）」に渡される。このようにして、上述した様々なテストを、そのままでは通過する潜在的に不正確な同義語を、実際のユーザ検索の実行に含める前に、入念に吟味することができる。

図７は、本発明の原理に係るユーザ始動検索を実行するための例示的プロセスを示すフローチャートである。最初に、検索クエリがユーザの指示でクライアント２１０から受信される（アクト７００）。上述の通り、本発明の原理によると、検索クエリは、１つの例示的実施形態では、地域ビジネス情報の場所特定または識別に関する多数の語を含むかもしれない。代替的実施形態では、検索クエリは、製品価格および説明情報、ウェブベースの文字情報、メディア（例えば歌、画像、映像等）情報のような追加型の情報の場所特定または識別に向けられるかもしれない。

要求される情報の種類に関係なく、サーバ２２０上の検索エンジン２２５は次に、要求された情報に関連する１つまたはそれ以上のカテゴリを識別することができる（アクト７
０２）。初期カテゴリが識別される方法は本発明の範囲外であり、ここでは詳述しない。しかし、ひとたび初期カテゴリが識別されると、図５および６のプロセスを用いて決定されたカテゴリ同義語を次いで識別することができる（アクト７０４）。クエリ語、最初に決定された単数または複数のカテゴリ、および上で詳述した方法で識別されたカテゴリ同義語を用いて、検索結果が次いで生成され（アクト７０６）、要求したユーザに最終表示するためにクライアント２１０に転送される。

１つの例示的実施形態では、リスト情報は受信したクエリ語に加えて、上述した方法で識別されたカテゴリ同義語を使用して、特別に探索することができる。例えば「医師」の検索は、「一般開業医」と識別されたカテゴリ同義語を含めるように改訂することができる。一実施形態では、そのような語を論理和することができる。提示した実施例では、結果的に得られるクエリは「医師ＯＲ厳密なカテゴリ合致（ＥＸＡＣＴ ＣＡＴＥＧＯＲＹ
ＭＡＴＣＨ）（一般開業医）」を含む。ここで厳密なカテゴリ合致は、定義されたカテゴリ同義語内に含まれる各語が、リスト情報で識別されたカテゴリ内で捜索されることを確実にする。このようにして、関連リストとの部分カテゴリ合致（例えば産科医）によって生じる混乱が回避される。

過去の検索情報を使用してカテゴリ同義語を推定することにより、強化された検索結果をもたらすことができる。さらに詳しくは、以前の検索から適正な検索結果を識別することによって、カテゴリ同義語を正確に推定することができる。将来の検索結果を提供する際に、推定された同義語を使用することにより、ユーザに望ましい結果を提供する可能性が増加する。

結論
本発明の原理に合致するシステムおよび方法は、検索クエリの洗練化を容易にすることができる。本発明の原理に合致する１実現では、過去の検索情報からカテゴリ同義語を推定することができる。

本発明の好適な実施形態の上記の記述は、例証および説明を提供するものであって、本発明を網羅するものでも、開示された厳密な形に限定するつもりもない。上記教示に照らして変形および変化が可能であり、または本発明の実施から得ることができる。例えば、図５〜７に関連して一連のアクトを説明したが、アクトの順序は、本発明の原理に合致する他の実現で変更することができる。また非従属アクトは、並行して実行することができる。さらに、アクトは別のやり方に変更することができる。

上述した本発明の態様は、図示した実現において多くの異なる形のソフトウェア、ファームウェア、およびハードウェアで実現することができることも、通常の当業熟練者には明白であろう。本発明に合致する態様を実現するために使用される実際のソフトウェアコードまたは専用制御ハードウェアは、本発明を限定するものではない。したがって、通常の当業熟練者は、本書の記述に基づいて態様を実現するためのソフトウェアおよび制御ハードウェアを設計することができると理解して、態様の動作および挙動については、特定のソフトウェアコードに言及することなく説明した。

本発明の説明で使用した要素、アクト、または命令は、明示的にそうであると記述しない限り、本発明に必須または不可欠であると解釈すべきではない。また、本書で使用する場合、冠詞「ａ」は１つまたはそれ以上のアイテムを含むものと意図される。単一のアイテムだけを意図する場合、「１つ（ｏｎｅ）」または同様の言語を使用する。さらに、語句「〜に基づく」は、特にそうでないことを明示しない限り、「少なくとも部分的に〜に基づく」ことを意味する。

本発明の原理に合致する概念を示す例示的図である。 本発明の原理に合致するシステムおよび方法を実現することのできるネットワークの例示的図である。 本発明の原理に合致する実現に係る図２のクライアントまたはサーバの例示的図である。 図２〜３に使用することのできる例示的コンピュータ可読媒体の一部分の図である。 本発明の原理に合致する実現において同義語を識別するための例示的プロセスのフローチャートである。 本発明の原理に合致する１実現における、包含型および同等型のクエリ・カテゴリ対を区別するための例示的プロセスのフローチャートである。 本発明の原理に係るユーザ開始検索を実行するための例示的プロセスを示すフローチャートである。

Claims (15)

1. １つ以上の検索要求を処理することによって得られたクエリデータを１つ以上のプロセッサによって識別し、前記クエリデータは、少なくともクエリ語情報および前記クエリ語情報に基づいて返された検索結果に関連付けられたカテゴリ情報を含み、
   前記カテゴリ情報が前記クエリ語情報の同義語であるか否かを前記１つ以上のプロセッサによって判断して、その判断結果を格納し、
   前記クエリ語情報に含まれる１つ以上の用語を含む検索要求、または、前記カテゴリ情報に関係する検索要求を受信し、
   格納された判断結果に基づいて、前記クエリ語情報が前記カテゴリ情報の同義語である場合に、前記クエリ語情報および前記カテゴリ情報に基づいて、前記カテゴリ情報に関連付けられたカテゴリ同義語を含むように、前記１つ以上のプロセッサによって前記検索要求を変更し、
   前記変更された検索要求に基づき前記１つ以上のプロセッサによって検索を実行し、
   前記実行された検索に基づき検索結果を前記１つ以上のプロセッサによって提供する、方法。
2. 前記クエリデータは、ビジネスリスト情報の先行の検索に関連付けられている、請求項１に記載の方法。
3. クエリデータの識別では、さらに、前記クエリデータが関連性の先行の指標に含まれているか否かを判断し、
   前記関連性の先行の指標は、前記クエリデータに関連付けられた予め定められたユーザアクションが受信されているとの情報を含む、請求項１に記載の方法。
4. 前記クエリデータに関連付けられた予め定められたユーザアクションは、複数の検索結果の１つの検索結果が与えられているリンクの選択を含む、請求項３に記載の方法。
5. さらに、前記クエリデータが名前クエリまたはカテゴリクエリに関係するか否かを前記１つ以上のプロセッサによって判断し、
   前記クエリデータが名前クエリまたはカテゴリクエリに関係するか否かの判断では、さらに、前記クエリ語情報が事業名またはビジネスカテゴリに対する要求に関係するか否かを判断する、請求項１に記載の方法。
6. 前記クエリ語情報が事業名またはビジネスカテゴリに対する要求に関係するか否かの判断では、さらに、前記クエリ語情報の名前パープレキシティ値を判断し、
   前記クエリデータに含まれる他のクエリ情報の他の名前パープレキシティ値よりも高い名前パープレキシティ値を有するクエリ語情報は、カテゴリクエリに対応し、他の名前パープレキシティ値より低い名前パープレキシティ値を有するクエリ語情報は、名前クエリに対応する、請求項５に記載の方法。
7. さらに、前記クエリデータが名前クエリに関係するかそれともカテゴリクエリに関係するかをさらに判断し、
   前記クエリデータがカテゴリクエリに関係する場合に、前記クエリ語情報に関連付けられたクエリ語がビジネスカテゴリの候補同義語であるか否かを判断する、請求項１に記載の方法。
8. 前記クエリデータに関連付けられたクエリ・カテゴリ対のクエリが、当該クエリデータに関連付けられたクエリ・カテゴリ対のカテゴリの下位語であるか否かを前記１つ以上のプロセッサによって判断し、
   前記クエリ語は、前記クエリに含まれており、
   前記ビジネスカテゴリは、前記カテゴリに関連付けられており、
   前記クエリデータに関連付けられた前記クエリ・カテゴリ対のクエリが、当該クエリデータに関連付けられたクエリ・カテゴリ対のカテゴリの下位語である場合に、前記クエリ語をビジネスカテゴリの同義語としては拒絶し、
   前記クエリが前記カテゴリの下位語ではない場合に、前記クエリ語をビジネスカテゴリの同義語として受け入れる、請求項７に記載の方法。
9. 前記クエリデータに関連付けられた前記クエリ・カテゴリ対のクエリが、当該クエリデータに関連付けられたクエリ・カテゴリ対のカテゴリの下位語であるか否かの判断では、前記クエリ・カテゴリ対のＦ値を計算し、
   Ｆ値は、前記クエリ・カテゴリ対のクエリが、当該クエリデータに関連付けられたクエリ・カテゴリ対のカテゴリの下位語である可能性を示す、請求項８に記載の方法。
10. 前記クエリ・カテゴリ対のＦ値は次式：
    に従って計算され、式中Ｐ（ｎ）は前記クエリデータにおける発生の確率を表わし、Ｐ（ｑｕｅｒｙ，ｃａｔｅｇｏｒｙ）はクエリおよびカテゴリが同義語である可能性を示し、「ａ」は再現率および精度の均衡化のための予め定められた変数である、請求項９に記載の方法。
11. 「ａ」は約０．７から０．９の範囲内である、請求項１０に記載の方法。
12. 先行のクエリデータおよび前記先行のクエリデータに基づいて得られた先行の検索結果に関連付けられた先行のカテゴリデータがカテゴリ同義語を含むか否かを判断するための手段を備え、前記判断するための手段は、前記先行のクエリデータに含まれるクエリ語が前記先行のカテゴリデータに含まれるカテゴリのカテゴリ同義語であるか否かを判断する手段を含み、さらに、
    検索要求を受信するための手段を備え、前記検索要求は、前記先行のカテゴリデータに含まれるカテゴリのカテゴリ同義語である１つ以上の用語を含み、
    前記先行のクエリデータおよび前記先行のカテゴリデータがカテゴリ同義語を含む場合に、前記先行のクエリデータおよび先行のカテゴリデータに基づいて、カテゴリに対応する用語を含むように前記検索要求を洗練化するための手段と、
    前記洗練化された検索要求に基づき検索を実行するための手段と、
    前記検索に基づき検索結果を提供するための手段とを備える、システム。
13. 先行の検索結果に関連する先行のクエリデータおよび先行のカテゴリデータがカテゴリ同義語を含むか否かを判断するための手段は、
    前記先行の検索結果が適正であるか否かを判断するための手段を含み、前記先行の検索結果が適正であるか否かを判断するための手段は、先行の検索結果が与えられている１つ以上のリンクが選択されているか否かを判断するための手段を含み、さらに、
    前記先行の検索結果が適正である場合に、前記先行のクエリデータおよび前記先行のカテゴリデータがカテゴリ同義語を含むか否かを判断するための手段をさらに含む、請求項１２に記載のシステム。
14. 請求項１に記載の方法を実行するプロセッサを制御するための命令を含むコンピュータ読み取り可能メモリデバイス。
15. 検索クエリを受信し、
    前記検索クエリを処理するためにクエリデータを得、得られた前記クエリデータは、検索結果から得られたクエリ語情報およびカテゴリ情報を含み、前記検索結果は、前記クエリ語情報に基づいて返されるために、前記検索クエリの受信の前に選択され、前記カテゴリ情報は、前記検索結果に関連付けられており、さらに
    前記カテゴリ情報が前記クエリ語情報の同義語であるか否かを判断し、この判断では、
    前記クエリ語情報が前記カテゴリ情報の下位語であるか否かを判断し、
    前記クエリ語情報がカテゴリ情報の下位語ではない場合に、前記カテゴリ情報が前記クエリ語情報の同義語であると判断し、
    前記カテゴリ情報が前記クエリ語情報の同義語であるという判断に応答して、
    前記カテゴリ情報および前記クエリ語情報に基づいて前記検索クエリを洗練化して、洗練化された検索クエリを生成し、前記検索クエリは、前記カテゴリ情報に含まれるカテゴリに対応する用語を含めることで洗練化され、
    前記洗練化された検索クエリに基づき検索を実行し、
    前記検索に基づき検索結果を出力する、コンピュータで実行される方法。