(57)【要約】  言語におけるセンテンスの分類を作成し、さらに、地理的ロケーションおよび／または他の人口統計上の基準に基づいて関連のローカルバージョンの言語モデルを構築するシステムと方法が開示されており、かかるローカル言語モデルは、選択された人口統計上の基準に応じて異なるレベルの粒度にすることが可能になっている。本発明は、センテンスの分類（例：ツリー構造）を形成する分類エンコーダコンポーネント、およびローカル化言語モデルを構築するためにセンテンスの分類を使用するローカル言語モデルエンコーダコンポーネントを使用している。そのあと、デコーダコンポーネントは、ユーザの人口統計に合致する人口統計粒度を変化させるローカル言語モデルからのｋ個の最良応答をブレンドすることによって、ローカルワードホイーリングおよび／またはローカルＷｅｂサーチを可能にしている。従って、ある人口統計上の地域における入力データに対するｋ個の最良合致は、別の地域における他のユーザによる同じ入力に対するｋ個の最良合致と異なることができる。
2009535732.tif 000002
【特許請求の範囲】
【請求項１】
センテンスを人口統計に基づいた分類に要約する分類エンコーダコンポーネントと、
前記分類を拡張して、ローカル化言語モデルを形成し、ローカル関心事のサーチを容易にするローカル言語モデルエンコーダコンポーネントと、
を含むことを特徴とするコンピュータ実装システム。
【請求項２】
ローカルセンテンスはクエリログの形態になっていることを特徴とする請求項１に記載のコンピュータ実装システム。
【請求項３】
前記分類はクエリログを要約するツリー構造の形態になっていることを特徴とする請求項２に記載のコンピュータ実装システム。
【請求項４】
ローカル言語モデルの分類を通して入力データを評価して、拡張の集合を生成する拡張コンポーネントを備えたデコーダコンポーネントをさらに含むことを特徴とする請求項１に記載のコンピュータ実装システム。
【請求項５】
ツリー構造は、所定の基準に基づいてクエリをプロモートするノードを備えたことを特徴とする請求項３に記載のコンピュータ実装システム。
【請求項６】
所定の基準は有意性テスト基準であることを特徴とする請求項５に記載のコンピュータ実装システム。
【請求項７】
ローカル関心事に対する拡張を生成するためにユーザの地域に関する情報を提供するローカルコンテキストコンポーネントをさらに含むことを特徴とする請求項１に記載のコンピュータ実装システム。
【請求項８】
人口統計は時間と空間の少なくとも一方に基づいていることを特徴とする請求項１に記載のコンピュータ実装システム。
【請求項９】
ツリー構造はＫｄツリー構造であることを特徴とする請求項３に記載のコンピュータ実装システム。
【請求項１０】
ユーザから入力データを受け取るインタフェースコンポーネントをさらに含むことを特徴とする請求項１に記載のコンピュータ実装システム。
【請求項１１】
分類の平滑化を容易にする人口知能コンポーネントをさらに含むことを特徴とする請求項１に記載のコンピュータ実装システム。
【請求項１２】
人口統計に基づいた分類の形態にセンテンスを要約するアクトと、
前記分類からローカル化言語モデルを形成するアクトと、
を含むことを特徴とするコンピュータ実装方法。
【請求項１３】
センテンスを分類のレベル間で移動することによって分類を平滑化するアクトをさらに含むことを特徴とする請求項１２に記載のコンピュータ実装方法。
【請求項１４】
要約するアクトは、ノードを持つツリー構造の形態にクエリログを要約することを含むことを特徴とする請求項１２に記載のコンピュータ実装方法。
【請求項１５】
形成するアクトは、ノードに対するローカル言語モデルを形成することを含むことを特徴とする請求項１４に記載のコンピュータ実装方法。
【請求項１６】
ローカル化言語に基づいて入力を拡張することをさらに含むことを特徴とする請求項１３に記載のコンピュータ実装方法。
【請求項１７】
所定の基準に基づいてツリー構造を平滑化することをさらに含むことを特徴とする請求項１４に記載のコンピュータ実装方法。
【請求項１８】
所定の有意性基準に基づいてノードをプロモートすることをさらに含むことを特徴とする請求項１５に記載のコンピュータ実装方法。
【請求項１９】
ツリーのリーフノードからルートノードまでの経路上のすべてのノードにおいてｋ個の最良合致を取得することと、前記ｋ個の最良合致を結合することとをさらに含むことを特徴とする請求項１５に記載の」コンピュータ実装方法。
【請求項２０】
人口統計に基づいたローカル言語の分類構造を形成する手段と、
ローカル化言語モデルを前記分類から作成する手段と、
前記ローカル言語の分類構造を使用してローカル関心事の入力拡張を容易化する手段と、
を含むことを特徴とするコンピュータ実装システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ローカルなワードホイーリング／Ｗｅｂサーチのための人口統計に基づく分類に関する。
【背景技術】
【０００２】
コンピュータハードウェア、ソフトウェアおよびネットワーキングにおける技術的進歩により、実際に世界のほぼどこからでも相互に通信できる効率的で、費用効果的であるコンピューティングシステムが提供されている。このようなシステムは、インターネットにアクセスし、ブラウズし、サーチしたり、ｅメールを構成し、送信し、受信したり、ドキュメントを表示して編集したり、テキストメッセージ、インスタントメッセージを送信し、取得したり、などをするために使用されている。例えば、ユーザは、映画の時間についてインターネットをサーチしたり、ｅメール、テキストメッセージまたはインスタントメッセージを送信することによって特定の上演に友人を招待したりするために、セル電話やパーソナルデジタルアシスタンス（ＰＤＡ）を使用することができる。
【０００３】
キーボード、マウス、タッチセンシティブスクリーン、ペンデバイス、光学文字認識、音声認識などを使用してデータを入力するといったように、かかるデバイスで情報を入力するために様々な手法が採用されている。例えば、従来のシステムでは、ホストデバイスのタイプ、すなわち、パーソナルコンピュータであるか、ラップトップコンピュータであるかに応じてサイズが変わることのあるキーボードがしばしば使用されている。このようなデバイスは、ＱＷＥＲＹＴＹレイアウトに基づくキーボードを使用することができ、このレイアウトでは、各英数字はそれぞれのキーと関連付けることができるのに対し、セル電話では、キーの数が少なくなっているため、いくつかの英文字は１つのキーを数字と共有している。例えば、セル電話キーパッド上の“２”キーは、英文字“Ａ”、“Ｂ”、および“Ｃ”と関連付けられているのが普通である。
【０００４】
さらに、限定されたキーボードを使用してテキストを入力するために複数の手法が一般に採用されているが、１つ以上の英数字が特定のキーと関連付けられているとき多義性が発生している。例えば、マルチプルタップアプローチ(multiple-tap approach)を取り入れることができるが、このアプローチでは、ユーザは望みの英字または数字を入力するために数字キーを何回か押している。従って、“２”キーを一回押すと、数字２が入力され、二回押すと英字Ａが入力され、三回押すと英字Ｂが入力され、四回押すと英字Ｃが入力されている。ポーズすると、および／またはカーソルを動かすキー（例：矢印キー）を押すと、異なる英数字間の区別が容易化されている。しかし、この手法は、１つの英数字を入力するために１つのキーが複数回押されることがあるため、一般にユーザにとっては時間を要し、非効率的である。数字キーを使用してテキストを入力する別の一般的アプローチはシングルタップアプローチ(single-tap approach)であり、このアプローチでは、ユーザは望みの英字と関連付けられた数字キーを一回押している。そのあと、入力された文字は、あるワードに対応する文字のシーケンスを、例えば、メモリにストアされたシーケンスと突き合わせることによって、多義性が取り除かれている。従って、ワード“cell”を入力するには、ユーザは2-3-5-5のシーケンスで押すことができるので、このシーケンスはメモリにストアされたシーケンスと比較することができる。シングルタップアプローチによると、テキストを入力することが効率化されるが、このアプローチには欠点がある。
【０００５】
【特許文献１】米国特許出願公開２００７−０１６４７８２号公報
【特許文献２】米国特許出願公開２００７−０１６７９４２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
代表例として、従来のＷｅｂサーチおよびマルチワードホイーリング(multi-word wheeling)（サーチクエリを入力しやすくする）は、どちらも、Ｗｅｂページおよびクエリを人気度基準および／または所定の尺度に従ってランク付けできる言語モデル（またはインデックス）に基づいている。一般的に、このようなアプリケーションのローカルでないバージョンは１つの汎用言語モデルとやりとりするため、サーチまたはワードホイーリングからは、ロケーションに関係なく同じ入力に対して同じ応答が得られている（例えば、ユーザが同じクエリをSeattleから開始したか、New Yorkから開始したかに関係なく同じ応答が得られている）。言語モデルコンポーネントは、どの言語モデルでも一般的には採用できる（例えば、ワードのシーケンス上に定義された確率分布）。例えば、三重字言語モデルを利用することができる。さらに、限定された言語モデルを採用することができる。一例によれば、Ｗｅｂクエリのために利用される言語モデルは、クエリのリストおよびそれと関連付けられた確率に基づくことができる。別の例によれば、音節要素上に構築された言語モデルは、暗黙的および／または明示的ワイルドカードを拡張することに関連して使用することができる。
【課題を解決するための手段】
【０００７】
以下は、本明細書に記載されているいくつかの側面を基本的に理解できるように簡単に説明したものである。この簡単な説明は請求項に記載の主題を網羅的に概観したものではない。請求項に記載の主題の主要または重要エレメントを特定するものでもなく、その範囲を限定するものでもない。その唯一の目的は、以下に記載されているより詳細な説明の序論としていくつかの概念を簡単に紹介することである。
【０００８】
本発明によれば、言語からのセンテンスの分類が人口統計（例えば、時間、空間、その他のユーザ人口統計などに基づいたツリー構造とその平滑化の形態をしたクエリログ(query log)）に基づいて行なわれ、（センテンスの分類、例えばツリー構造、を人口統計に従って形成する）分類エンコーダコンポーネントと、（ローカル言語モデルの関連するエンコーディングを生成する）ローカル言語モデルエンコーダコンポーネントと、（分類構造とローカル言語モデルに基づいて、ユーザによって与えられた入力データ（例：サーチクエリの一部）に対して人口統計に関係する合致を効率よく見つける）デコーダコンポーネントとを採用することによって、所定の人口統計基準と関連付けられたローカルなワードホイーリングおよびローカルなＷｅｂサーチを可能にしている。センテンスには、言語モデルにおいて異なる確率を異なる人口統計（例：空間、時間など）と関連付けることができる。従って、ある地域におけるユーザによる入力データに対するｋ個の最良拡張（k-best expansion）は、別の地域における他のユーザによる同一入力に対するｋ個の最良拡張と異なることがありえる。このようにすると、人口統計基準に基づいて効率的なクエリまたはサーチを行なうことができると共に、システムリソースの使用が効率化される。
【０００９】
エンコーダコンポーネントは、センテンス（例えば、ユーザのロケーション、時間、その他の人口統計情報などの基準に基づいたログからのクエリ）を選択的に取得または引き出すことによって、センテンスのログ（例えばクエリログ）にストアされた情報を活用し、分類フォーマット（例えば、ルートノードとリーフを持つツリー構造の形態をしており、そこではノードまたはリーフは、例えば、矩形の形態をした領域を定義する経度と緯度によって識別可能な領域から出されたクエリを表わすことができる）に基づいてそのデータを要約する。このような分類は、そのあと、分類と関連付けられた異なるレベルにセンテンスを移動することによって平滑化することができ、そこでは、非常に多数のユーザが関心を持つセンテンスは、特定の人口統計のユーザが関心を持つセンテンスよりも上位レベルに移動し、後者のセンテンスは分類の下位レベルに移動される（例えば、大陸や国のような、非常に多数のユーザが関心を持つクエリをツリー構造の上方に移動し、同時に、都市、都市内の地域のような、非常に少数のユーザが関心のあるクエリはツリーの下位部分に移動する）。
【００１０】
１つの特定側面によれば、分類ツリー構造は、有意性基準に従って平滑化が向上したＫｄツリーの形態にすることができる。デコーダコンポーネントは、例えば、地域的に、国家的に、または国際的に関心のある結果を生成するためにワードホイーリングおよび／またはサーチでこのようなツリー構造を採用することができる。従って、各ノードは、地域に基づいてそのノードに合わせて調整された言語モデルをもち、ユーザによって入力された明示的／暗黙的ワイルドカードに対してｋ個の最良拡張を得ることができる。
【００１１】
以下の説明および添付図面は、請求項に記載の主題のいくつかの例示側面を詳しく説明している。なお、これらの側面は、その主題の原理を採用することができる種々方法のいくつかを示したものであり、請求項に記載の主題は、そのような側面のすべてとその同等側面を含むことを目的としている。その他の利点および新規特徴は、添付図面を参照して以下に記載されている詳細説明の中で明らかにする。
【発明を実施するための最良の形態】
【００１２】
以下、添付図面を参照して本発明の種々な側面について説明するが、図面において類似エレメントまたは類似エレメントに対応するエレメントは類似の参照符号で示されている。なお、当然に理解されるように、図面および図面に関連する詳細説明は請求項に記載の主題を、開示した特定の形態に限定するものではない。むしろ、本発明は、請求項に記載の主題の精神および範囲内に属するすべての変更、同等物および代替物を包含するものである。
【００１３】
図１は、言語におけるセンテンスの分類を作成し、さらに、地理的ロケーションおよび／またはその他の人口統計上の基準に基づいて、関連するローカルバージョンの言語モデルを構築するシステム１００を示す図であり、そこでは、かかるローカル言語モデルは選択された人口統計上の基準に応じて異なる粒度レベルにすることが可能になっている。一般的に、言語は文法によって生成されるセンテンス（ストリングとしても知られる）の集まりである。このような文法は、有限の状態の文法、コンテキストフリー文法、または単なるリスト（クエリログからのクエリのリスト）として存在することができる。さらに、言語モデルは、言語におけるセンテンスの各々に確率を関連付けている。システム１００はローカルバージョンの言語モデル１１０（１からｎ個まで。ただし、ｎは整数である）を用意している。このようなローカルバージョンの言語モデル（ローカル化言語モデル１１０）は、センテンスの確率が人口統計（例えば、時間、空間、その他のユーザ人口統計など）に依存するような言語モデルである。図１に示すように、分類エンコーダコンポーネント１０４によってセンテンス１０２（例：クエリログ）から作成される分類１０６（例えば、ツリー構造）の形態にエンコードすること、およびローカル化言語モデルを構築するためにセンテンス１０６の分類を使用するローカル言語モデルエンコーダ１０８によって、人口統計上の粒度が変化するローカル言語モデルの構築は容易化されている。
【００１４】
エンコードされた分類構造および関連のローカル言語モデルを使用することにより、デコーダコンポーネント（図示せず）は、以下で詳しく説明するように、人口統計上の粒度が変化するローカル言語モデルからの応答をブレンドすることにより、ローカルなワードホイーリングおよび／またはローカルＷｅｂサーチを、そのあとで可能にすることができる。このデコーダコンポーネントは、分類構造およびシステムを利用するユーザの人口統計に従って特定の言語モデルをブレンドして、ローカル化ワードホイーリングおよび／またはＷｅｂサーチを可能にすることができる。例えば、Seattleに所在のユーザによって開始された“Zoo”を探すサーチクエリは、Seattle zoo（Seattleから遠く離れた地域にある他の結果に加えて）などの応答を検索することができる。これは、非ローカル化言語モデルを採用する従来のサーチシステムとは対照的であり、従来のサーチでは、米国内および／または世界で最も人気のある動物園が返される可能性がある（Seattleに所在する動物園が返されないのが代表的である）。従って、本発明によれば、ある地域にいるユーザによる入力データに対するｋ個の最良拡張(k-best expansion)が、別の地域にいる他のユーザによる同じ入力に対するｋ個の最良拡張と異なることを可能にしている。このようにすると、実行されるクエリまたはサーチが効率化されると共に、システムリソースが効果的に使用される。エンコーダコンポーネント１０４は、センテンス１０２（例：クエリログ）にストアされた情報を、そのようなセンテンス１０２（例えば、ユーザのロケーション、時間、その他の人口統計情報などの基準に基づいている）からクエリを選択的に取得または引き出すことによって活用し、そのデータを分類１０６（例：ツリー構造）の形態に要約している。図１に示すように、例示のツリー構造（これは特定の分類を示している）は、任意のファンアウトおよび／または非バイナリの分岐と深さを可能にしている。当然に理解されるように、他の分類構造（ツリー構造のほかに）を採用することも可能であり、これは本発明の範囲内に完全に属するものである。
【００１５】
図２は、本発明の特定の側面によるツリー構造２００の形態の分類の特定側面を示す図である。構造内のどのノードも、領域を定義する経度と緯度によって定義可能である領域（例えば、矩形の形態をした）から出されたクエリを表わすことが可能である。あるノードがツリー２００をさらに下って現れると、そのノードがカバーする領域はさらに特定化される。ツリー構造２００は、そのあと、有意性基準に基づいてクエリをノード間に移動することにより（例えば、ノード２０７からその親ノード２０４に、次に２０４から２０３に、さらに２０３から２０２に）ほぼ平滑化することが可能であり、そこでは最も一般的なクエリ／エレメントはツリー２００のルートに向かって移動するのに対し（例えば、大陸または国などの非常に大きな人口統計グループのユーザが関心のあるクエリ）、非常に小さい人口統計グループのユーザが関心のあるクエリ（例：都市、都市内の地域など）はツリーの下方部分に置かれている。
【００１６】
ツリー構造２００は、以下で詳しく説明するように、有意性基準に従って平滑化が向上したＫｄツリーの形態にすることができる。クエリのツリー構造は、地域に基づいて言語モデルを構築するためにローカル言語モデルコンポーネントによって使用することができる。従って、各ノードは地域に基づいてそのノードに合わせて調整された言語モデルをもつことができる。従って、デコーダコンポーネントは、関連のローカル言語モデルをもつこのツリー構造をワードホイーリングで使用して、例えば、地域的に、国家的にまたは国際的に関心を持たれる結果を出力またはブレンドすることができる。結果は、ユーザによって入力された明示的／暗黙的ワイルドカードをもつテキストストリングに対してｋ個の最良拡張の形態にすることができる。
【００１７】
本発明の一特定側面によれば、エレメントのリストを得ることが可能であり、各エレメントは、出現頻度、クエリ、緯度、経度、およびその他の人口統計を含むことができる。ロケーションツリーは、世界（またはカバーされる特定エリア）をタイルに分割するバイナリツリーの形態にすることができる。本発明によれば、緯度上の分割と経度上の分割をツリーの異なるレベルで交互に行なうことができる。分割は、エレメントの出現頻度の総和が分割の両側で同じままであるように行なうことができる。従って、エレメントは、そのエレメントの緯度と経度という成分に従ってツリー内のリーフに分割することができる。
【００１８】
例えば、リーフ２１０はSeattleエリアに対応付けることができ、リーフ２０７はMiamiエリアにすることができる。その場合、リーフ２１０はそのロケーションに関するすべてのクエリとその出現頻度を含むことができる。理論的には、言語モデルは各ロケーションに構築することができ、そのあと、テキストを入力するユーザのロケーションに応じて正しい言語モデルを選択して利用することができる。このようなアプローチは、調整されたロケーションツリーを構築することによって強化することができ、リーフ上の分散エレメントは、類似するエレメントをツリーの上方に（再帰的に）プロモートすることによりまばらにされる。２つの兄弟（例：２０６、２０７）における同じクエリの出現頻度が類似しているが、必ずしも等しくない場合には、２つのエレメントは共にロケーションツリー内のそれぞれの親にプロモートされる。従って、このようなケースでは、プロモーションは兄弟内のエレメントを削除し（これは出現頻度をゼロにセットするのと同じである）、そのあと、代わりにそのエレメントを親に挿入することにより行なわれる（なお、出現頻度は兄弟における実際の出現頻度の総和に等しくなっている）。他方、出現頻度が類似していない場合は、最小出現頻度を持つ兄弟は、２出現頻度のうち最小出現頻度の２倍に等しい出現頻度を持つエレメントを親に挿入し、次に、その出現頻度を両兄弟から減算する（最小出現頻度の兄弟をゼロ値で残しておき、実際にはそのエレメントをその兄弟から削除する）ことによりプロモートすることができる。以上から理解されるように、一般的に、兄弟のプロモーションを決定するとき、出現頻度の類似性のテストが合理的であれば、どのテストを採用することも可能であり、その選択は、例えば、部分的にアプリケーションに応じて行なうことができる。
【００１９】
さらに、「サインテスト」を取り入れることが可能であり、このテストからは、例えば、等しく起り得るとの仮説の下で、小さい出現頻度が高い出現頻度よりも小さいとする代替的仮説に帰する（片寄った）有意性レベルが返される。従って、この仮説（Ｈ０）はp=0.5の二項分布を示すことができ、有意性レベルは（片寄った）二項末尾(Binomial trail）に等しく、これは小さい出現頻度について計算することができる（例：<= 50）。高い出現頻度については、二項分布は正規分布によって効率的に近似することができる。従って、有意性レベルはよりローカルなノードからよりグローバルなノード（例：２０４）に向かう（リーフからルートに向かう）エレメントのプロモーションの度合いを決定することができる。有意性レベルが小さいときは、２つの出現頻度が類似であるとするＨ０仮説に違反することが困難であり、エレメントは、このケースでは、ロケーションツリーの上方に移動する確率が高くなる。ロケーションツリーでは、すべてのテストについて単一の有意性レベルを使用することが可能である。別の方法として、有意性レベルは、有意性レベル調整を使用することによって、Bonferroniに似たスタイルで調節することができる。すなわち、
【００２０】
【数１】
2009535732.tif 000003
【００２１】
上記において、αは選択された有意性レベル、Ｄはツリーの深さである。例えば、
【００２２】
【数２】
2009535732.tif 000004
【００２３】
上記プロモーション方式に従うエレメントの再分布が与えられているとき、言語モデルは、ロケーションツリー内の各ノードについて作成することができる。有意性レベルが小さいときは、構造内の多数のリーフノードでの言語モデルは、実質的に小さくすることができ、真にローカルの情報だけを収めているのが一般的である。ツリー内を上方に移動するのに従い、言語モデルは大きなエリアをカバーし、ルートはロケーションに関係なく等しく出現し得る情報を収めることになる。例えば、“pizza”のクエリはルートに現れる可能性があるのに対し、ある地域に特有の“Joe's pizza joint”は、このまさに特定のpizzaの場所のロケーションに対応するリーフに現れることになる。
【００２４】
ロケーションツリー２００は、ツリー内の各ノードにローカル化言語モデルをもつことができる。このローカル化言語モデルの各々は、汎用／非ローカルWildThing（またはSearch）のために使用されたタイプと同じタイプにすることができるが、個々のモデルは実質的に小さくなっているのが一般である。従って、デコーダは、テキスト入力とのｋ個の最良合致を検索するために言語モデルのロケーションツリーを使用することができる。例えば、特定のロケーションが与えられているとき、本発明によれば、ツリーのリーフノード（特定の人口統計ロケーションと関連付けられた）からツリーのルートノードまでの経路上のすべてのノードでｋ個の最良合致とその出現頻度を見つけることができる。特許文献１と特許文献２の汎用WildThing（またはSearch）の場合と同じ方法は、特定のノードでのモデル内の合致を見つけるために使用することができる。ｋ個の最良合致の一部は異なるノードにわたって同じにすることができるのに対し、その他はそうでないことがある。あるノードではｋ個の最良合致の中に現れ、他方のノードでは現れない合致については、ｋ個の最良合致の中に現れないノードにおいて、その合致とその出現頻度を特に調べる必要がある。すべてのユニークな合致について、各ノードにおける合致の出現頻度をこの合致の集合において追加することが可能になり、局在のツリー内の中間ノードで得られた出現頻度を割り引くことにより、特定のロケーション上の平均分布を反映されることになる。このような割り引いた出現頻度は次のように計算することができる。
【００２５】
【数３】
2009535732.tif 000005
【００２６】
上記において、Ｌは中間ノードからリーフまでの経路の長さである。
【００２７】
前述したように、本発明は地理的ロケーションに限定されず、時間、時間と空間およびその他の人口統計上の基準などの他の基準を使用することも可能である。従って、最も一般的なクエリは、実質的に大きな人口統計上のユーザグループが関心のある（例えば、大陸または国などで関心のある）クエリを上方に移動するといったように、ツリーのトップに移動することができる。同時に、都市、都市内の地域などの、実質的に小さな人口統計上のユーザグループが関心のあるクエリは、ツリーの下方部分に移動する。
【００２８】
図３は本発明の一側面による関連方法３００を示す図である。本明細書では、例示方法は種々のイベントおよび／アクトを表わす一連のブロックとして図示され、説明されているが、本発明はかかるブロックの図示順序に限定されない。例えば、いくらかのアクトまたはイベントは、本発明によれば、本明細書に図示の順序とは別に、異なる順序で実行されることもあれば、他のアクトまたはイベントと同時並行に実行されることもある。さらに、本発明によれば、すべての図示ブロック、イベントまたはアクトが方法を実現するために必要になるとは限らない。さらに、当然に理解されるように、本発明による例示方法および他の方法は、本明細書に図示され、説明されている方法と関連付けて実現することも、図示または説明されていない他のシステムおよび装置と関連付けて実現することも可能である。最初に、３０２において、センテンスを言語から収集することができ（例えば、クエリがクエリログから収集される）、そのセンテンスは、そのあと３０４において人口統計に基づいて分類される（例えば、そのクエリが出された元の地理的ロケーションに基づいて、ツリー構造を形成するためにノード間に分布される）。理解されるように、地理的ロケーションに基づくクエリの分布は例示の基準を表わしているが、ノード間の分布とツリー形成のために他の人口統計上の基準を使用することも可能である。３０６において、センテンスからのデータを前記分類に基づいて要約することができる（例えば、クエリログはツリー構造の形態に要約される）。そのあと、３０８において、この分類（例：ツリー構造）は、有意性基準に基づいてセンテンスを異なるレベル間で移動させる（例えば、ツリーの下方部分にあるノードから上方部分にクエリを移動させる）ことにより平滑化することができる。
【００２９】
図４は、本発明の一側面に従ってツリーの形態の特定の分類を平滑化する特定の方法４００を示す図である。最初に、４０２において、子ノードを特定することができる。そのあと、４０４において、親ノードを共有する子ノードは、そのノード内のいくらかのクエリをツリーの上方にプロモートすべきか否かを確かめるために、所定の基準（例：有意性テスト基準）に基づいて比較される。４０６において、あるノードにおけるクエリ出現頻度が兄弟の子ノードにおけるよりも十分に大であるか否かの判断が行なわれる。２つの子ノードの一方におけるクエリのカウントの方が十分に大であれば（所定の基準に基づく比較時に）、そのクエリのカウントは部分的にプロモートすることができる。例えば、兄弟におけるクエリの最低カウントは両方の兄弟からプロモートされる。例えば、左端の兄弟は特定のクエリに対して３のカウントを取得し、右端の兄弟は同じクエリに対してカウントが１３になっている場合は、３のカウントはその兄弟の各々から親まで移動するので、兄弟に関連付けられた親ノードではカウントが６のままになっている。このように部分的にプロモートすると、そのあと右端の兄弟はカウントが１０になり、左端の兄弟はカウントが０になる。上記とは別に、子ノードにおけるクエリの比較が相対的に等しいカウント（または所定のしきい値以下の差）を示している場合は、そのクエリのカウントは両方の子から親ノードにプロモートされる。従って、ノードを上方に移動させるための有意性基準は、例えば、ユーザ間の人気度基準に似せることができる。一般的に、最上のルートノードはすべてのユーザに人気のあるクエリをカバーすることになる（例えば、ユーザの人口統計に関係なく）。理解されるように、出現頻度の類似性の任意の妥当な（例えば、アプリケーションに依存する）テストは、どのようなテストでも兄弟のプロモーションを判断する場合に使用することができる。
【００３０】
関連の側面において、人工知能（ＡＩ）コンポーネントは、円滑化されたツリーをクエリログから作成することを容易にするために使用することができる。本明細書の中で用いられているように、「推論(inference)」の用語は一般的に、イベントおよび／またはデータを通してキャプチャされた情報の集合からシステム、環境および／またはユーザのステート（状態）について推論（reasoning about）し、または推断(inferring)するプロセスを意味している。推論は、特定のコンテキストまたはアクションを特定するために使用することができ、あるいは例えば、ステート全体にわたる確率分布を生成することができる。推論は確率論的にすることができる。すなわち、関心のあるステート全体にわたる確率分布の計算はデータおよびイベントの考慮に基づくことができる。また、推論は高レベルのイベントをイベントおよび／またはデータの集合から構成するために使用される手法を意味することもある。このような推論の結果として、イベントが時間的に近接した相関関係にあるか否かに関係なく、およびイベントとデータが１つまたは複数のイベントとデータソースからのものであるか否かに関係なく、観察されたイベントおよび／またはストアされたイベントデータの集合から新しいイベントまたはアクションが構築される。
【００３１】
図５は、エンコーダコンポーネント５０２（これは、ノードの分類構造内の地域に従ってセンテンスを移動させ、関連のローカル言語モデルを構築することを容易にする）とやりとりすることができる人工知能コンポーネント５１０、およびデコーダコンポーネント５０４（これは、以下で詳しく説明するように、構築されたエンコーディングに従ってユーザによる入力の拡張を容易にする）を示す図である。例えば、センテンスをいつ分類（例：ツリー構造）の上方にプロモートするかを判断するプロセスは、自動分類機能のシステムおよびプロセスによって容易にすることができる。この分類機能は、入力属性ベクトル、x=(xl,x2,x3,x4,xn)を、入力があるクラスに属するとの確信(confidence：コンフィデンス)にマップする関数、すなわち、f(x)=confidence(class)である。この分類は、確率および／または統計に基づく分析を使用して（例えば、分析の効用と費用を考慮に入れる）、ユーザが自動的に実行させることを望んでいるアクションを予測または推論することができる。
【００３２】
サポートベクトルマシン(support vector machine  SVM)は使用できる分類機能の一例である。ＳＶＭは、起り得る入力のスペース内にハイパサーフェスを見つける働きをし、そのハイパサーフェスは、トリガリング基準を非トリガリングイベントから分割することを試みる。直観的に、これにより、分類は、トレーニングデータに近いが、同一でないデータをテストするのに妥当なものにされる。他の有向および非有向モデル分類アプローチの例として、ナイーブベイズ、ベイジアンネットワーク、判定ツリー、ニューラルネットワーク、ファジーロジックモデル、および異なる独立パターンを提供する確率論的分類モデルが使用できる。本明細書で用いられている分類は、優先度モデルを開発するために利用される統計的回帰も含んでいる。
【００３３】
本明細書から容易に理解されるように、本発明によれば、明示的にトレーニングされた（例えば、汎用トレーニングデータにより）分類機能だけでなく、暗黙的にトレーニングされた（例えば、ユーザ行動を観察し、外部情報を受信することにより）分類機能を使用することができる。例えば、ＳＶＭは、分類機能コンストラクタおよびフィーチャ選択モジュール内の学習またはトレーニングフェーズを通して構成されている。従って、これらの分類機能は、複数の関数を自動的に学習し、実行するために使用することができ、以前に推論されたスキーマをいつ更新または改良し、処理されるデータの種類に基づいて推論アルゴリズムの基準を強化し、および強化した基準コントロールを一日のどの時刻に実現するかを、所定の基準に従って判断することを含むが、これに限定されない。
【００３４】
図６は、ローカル化言語モデルコンポーネント６０６に基づいて入力データを拡張するシステム６００を示す図である。ローカル化言語モデルコンポーネント６０６は、汎用応答を、ローカルユーザに十分に大きな関心を持たれているローカル応答とブレンドできるのが一般である。このローカル化言語モデルコンポーネント６０６はある範囲の言語モデルを含み、そこではセンテンスの確率は人口統計（例：時間、空間、その他のユーザ人口統計など）に依存している。一般的に、ローカル言語モデルコンポーネントにおける言語モデルはすべてが、与えられた人口統計に準拠しているが、その人口統計上の地域性／一般性を変化させて、地域性の度合いが変化する応答をブレンドすることを可能にしている。例えば、ツリー構造の形態の分類では、ローカル言語コンポーネントは、ツリー内のリーフ（特定の人口統計ロケーション）からツリーのルート（すべてによって共有される汎用人口統計ロケーション）までの経路上のノードと関連付けられたすべてのローカル化言語モデルを典型的に含み得る。
【００３５】
システム６００は、入力データを取得するインタフェース６０２およびその入力データを利用して拡張データの候補リストを生成する拡張コンポーネント６０２を備えることができる。インタフェース６０２はどのタイプの入力デバイス（図示せず）からでも入力データを受信することができる。例えば、入力データはパーソナルコンピュータ、ラップトップ、ハンドヘルド、セルラ電話、サーバなどによって生成することができる。当然に理解されるように、インタフェース６０２および／または拡張コンポーネント６０４は入力デバイスに結合することが可能であり、その全体または一部を入力デバイス内に装備させることが可能であり、および／またはスタンドアロンコンポーネントにすることが可能である。
【００３６】
一般的に、どのタイプの入力データでもインタフェース６０２によって受信することができる。例えば、ユーザがパーソナルコンピュータを使用しているときは、インタフェース６０２は、ユーザによって押されたキーと関連付けられた英数字を取得することができる。さらに、ユーザの発声入力を解析するために音声認識を使用することができ、および／または書かれたデータを識別するために手書き認識を利用することができる。従って、インタフェース６０２は可聴データおよび／または可視データを受信することができる。別の例を挙げると、インタフェース６０２はセルラ電話のキーパッドと関連付けられた数字を受信することができ、そこでは数字の各々を複数の英数字と関係付けることができる。
【００３７】
入力データには、１または２以上の明示的ワイルドカードを含めることができる。このワイルドカードは“＊“で表わすことができる。なお、ワイルドカードの任意の種々の表現はいずれも本発明の範囲に属している（例えば、＊、サウンド、マークなどの代わりに、他のどの文字でもワイルドカードとして使用することができる）。明示的ワイルドカードは入力データ内のどこにでも入れることができる。従って、例えば、ユーザが“Lincoln“のワードを入力することを望んでいれば、パーソナルコンピュータに関連するキーボードから入力“Linc*n“とタイプして、インタフェース６０２に与えることができる。別の例によれば、ユーザは“m-star-t“と発声し、この入力データを拡張コンポーネント６０４に渡すことができると、拡張コンポーネント６０４は、音声認識を使用してその入力データを、例えば、“m*t“と特定することができる。
【００３８】
入力データを取得したあと、インタフェース６０２はその入力データを拡張コンポーネント６０４に渡すことができる。前述したように、拡張コンポーネント６０４は、入力データと関連付けられたワイルドカードの適当な拡張を、人口統計に基づいて提供するローカル化言語モデルの採用を可能にするローカル化言語モデルコンポーネント６０６を備えることができる。従って、ローカル化言語モデルとその分類構造を使用することにより、拡張コンポーネント６０４は入力データと関連付けられた明示的ワイルドカードを拡張して、拡張データの候補リストを生成することができる。さらに、拡張コンポーネント６０４は、暗黙的ワイルドカードを入力データに挿入することができ、そこでは暗黙的ワイルドカードは同じように拡張することができる。ローカル化言語モデルとその分類構造は、ローカル化言語モデルコンポーネント６０６の一部として、ｋ個の最良拡張を見つけるために使用することができ、そこではある地域におけるユーザによる入力データに対するｋ個の最良拡張は、別の地域における他のユーザによる同じ入力に対するｋ個の最良拡張と異なることができる。さらに、ローカル化言語モデルコンポーネント６０６によって使用されたローカル化言語モデルは、ブレーキングニューズストーリ(breaking news stories)をタイムリに特定するのを可能にするために頻繁に更新することができる。
【００３９】
インタフェース６０２は拡張コンポーネント６０４とは別のものとして示されているが、拡張コンポーネント６０４はインタフェース６０２またはその一部を含むことが可能であることが意図されている。また、インタフェース６０２は、拡張コンポーネント６０４とのやりとりを可能にするために種々のアダプタ、コネクタ、チャネル、通信経路などを備えることが可能である。
【００４０】
拡張コンポーネント６０４は、拡張データの候補リストのローカル関心事を出力し、これはあとで利用することができる。例えば、候補リストのローカル関心事は、ユーザに表示することができ（例えば、インタフェース６０２を通して）、および／またはユーザはそのローカル関心事から選択を行なうことができる。候補リストから選択した拡張はサーチの実行と共に利用したり、構成中のドキュメントまたはメッセージに入力したり、アドレスバーに挿入したり、といったことができる。本発明の意図によれば、インタフェース６０２は、図示のように拡張データの候補リストを提供することができる（例えば、ユーザや入力デバイスなどに）。拡張コンポーネント６０４または異種のコンポーネント（図示せず）は候補リストを出力することができる。例えば、ローカル化候補リストはｋ個の最良拡張を含むことができる。
【００４１】
図７は、暗黙的ワイルドカードを入力データに挿入するシステム７００を示す図である。システム７００は、入力データを受け取って、その入力データを拡張コンポーネント７０４に渡すインタフェース７０２を備えている。拡張コンポーネント７０４は、入力データを拡張して拡張データのローカル候補リストを得ることができる。例えば、拡張コンポーネント７０４を使用すると、ｋ個の最良拡張(k-best expansion)を生成することができる。拡張は、少なくともその一部は、ローカル化言語モデルコンポーネント７０６によって得られた言語モデルとその分類構造を利用して実行することができる。
【００４２】
拡張コンポーネント７０４は、さらに、１または２以上の暗黙的ワイルドカードを入力データに挿入できるワイルドカード挿入コンポーネント７０８を備えることができる。当然に理解されるように、ワイルドカード挿入コンポーネント７０８は、暗黙的ワイルドカードを入力データのどこにでも置くことができる。暗黙的ワイルドカードを挿入したあと、入力データ内の任意の明示的ワイルドカードのみならず暗黙的ワイルドカードを、ローカル化言語モデルに基づいて拡張することができる。
【００４３】
関連する側面では、ワイルドカード挿入コンポーネント７０８は、入力データ内の目的のワードの終わりを特定することができる。例えば、ワイルドカード挿入コンポーネント７０８は、その特定されたロケーションにワイルドカードを挿入することができる。当然に理解されるように、このようないくらかのロケーションが判断できるので、任意の適当な数の暗黙的ワイルドカードを入力データと共に挿入することができる。ワイルドカード挿入コンポーネント７０８は、入力データの終わりと共にスペースを特定することによって目的のワードの終わりを見つけ、入力データ内のこれらのロケーションの各々の前に暗黙的ワイルドカードを挿入することができる。
【００４４】
ワイルドカード挿入コンポーネント７０８および／または拡張コンポーネント７０４は、ワードホイーリングを使用可能にすることができる。例えば、ユーザはキーボード機能が限定されているセルラ電話やＰＤＡなどのモバイルデバイスにデータを入力でき、その入力には非効率および／または時間のかかる英数字の入力が付きものである。さらに、ワードホイーリングは、目的の入力の正しいスペリングをユーザが知らなくても、それを埋め合わせることができる。さらに、ワードホイーリングは、入力するクエリについて漠然とした考えしか持たず（例えば、Ｗｅｂサーチコンテキストの中で）、または現在人気があって、部分的な入力に合致することについて関心のあるユーザを助けることができる。
【００４５】
図８は、ローカルの関心事に基づいて入力データを拡張することを容易にする方法８００を示す図である。最初に、８０２において、入力データを取得することができ、その入力データは、例えば、どのようなタイプのデバイス（例：デスクトップコンピュータ、ラップトップ、ハンドヘルド、セルラ電話、サーバなど）についても受信することができる。さらに、入力データは、サーチクエリ、テキストメッセージ（例：ショートメッセージサービス (SMS)のメッセージ)、インスタントメッセージ、生成および／または編集されるドキュメントなどと関係付けることができる。さらに、この入力データは、例えば、アルファベット文字、数字、手書きデータ、発声データ、これらを組み合わせたものを含むことができる。８０４において、１または２以上の暗黙的ワイルドカードを入力データに挿入することができる。例えば、暗黙的ワイルドカードは入力データの終わりに挿入することができる。さらに、暗黙的ワイルドカードは、入力データ内の１または２以上の目的のワードの終わりに挿入することができる。例えば、暗黙的ワイルドカードは、入力データ内の各スペースの前に挿入することができる。８０６において、ローカル化言語モデルとその分類構造を使用することができる。ローカル化言語モデル内のセンテンスの確率は人口統計（例：時間、空間、その他のユーザ人口統計など）に依存する。従って、ある地域におけるユーザによる入力データに対するｋ個の最良拡張は、別の地域における他のユーザによる同じ入力に対するｋ個の最良拡張と異なることができる。そのあと、入力データと関連付けられたワイルドカードのｋ個の最良拡張を生成することができ、これはローカル関心事と関係付けることができる。例えば、特定のロケーションが与えられているとき、本発明によれば、８０８において（その特定人口統計ロケーションと関連付けられた）ツリーのリーフノードからツリーのルートノードまでの経路上のすべてのノードにおけるｋ個の最良合致とその出現頻度を判断し、そのあとｋ個の最良合致を結合することができる。
【００４６】
本明細書の中で用いられている「例示」の用語は、例、事例または図例を意味するものとして用いられている。本明細書に例示として記載されているどの側面または設計も、必ずしも、他の側面または設計よりも好ましいまたは有利であると解される必要はない。同様に、本明細書に記載されている例は、単に明確化と理解しやすくすることを目的としており、本発明またはその一部をどのような態様においても限定することを意味していない。当然に理解されるように、追加例や代替例は多数存在するが、これらを省いたのは説明を簡略化するためである。
【００４７】
さらに、本発明のすべてまたは一部は、ソフトウェア、ファームウェア、ハードウェアまたはこれらを任意に組み合わせたものを生成する標準的プログラミングおよび／またはエンジニアリング手法を用いて、開示した本発明を実現するようにコンピュータを制御するシステム、方法、装置、または製造製品として実現することが可能である。本明細書の中で用いられている「コンポーネント」の用語はコンピュータ関連のエンティティ、すなわち、ハードウェア、ハードウェアとソフトウェアを組み合わせたもの、ソフトウェア、または実行中のソフトウェアのことを意味している。例えば、コンピュータ可読記録媒体として可能なものに、磁気ストレージデバイス（例：ハードディスク、フロッピディスク、磁気ストリップなど）、光ディスク（例：ＣＤ(compact disk)、ＤＶＤ(digital versatile disk)など）、スマートカード、およびフラッシュメモリデバイス（例：カード、スティック、キードライブなど）があるが、これらに限定されない。そのほかに、当然に理解されるように、電子メールを送受信し、またはインターネットやローカルエリアネットワーク（ＬＡＮ）などのネットワークにアクセスするときに使用されるようなコンピュータ可読電子データを搬送するために搬送波を使用することができる。この分野の精通者ならば当然に理解されるように、請求項に記載の主題の範囲または精神から逸脱しない限り、この構成に対し多くの変更を行なうことが可能である。
【００４８】
開示した主題の種々側面のためのコンテキストを提供するために、図９と図１０並びに以下の説明は、開示した主題の種々側面を実現することができる適当な環境の概要を簡単に説明することを目的としている。コンピュータおよび／または複数のコンピュータ上で実行されるコンピュータプログラムのコンピュータ実行可能命令の一般的コンテキストの中で主題を上述してきたが、この分野の精通者ならば理解されるように、本発明は他のプログラムモジュールとの組み合わせで実現することも可能である。一般的に、プログラムモジュールの中には、特定のタスクを実行し、および／または特定の抽象データ型を実現するルーチン、プログラム、コンポーネント、データ構造などが含まれている。さらに、この分野の精通者ならば理解されるように、本発明の方法は他のコンピュータシステム構成と共に実施することが可能であり、その中には、シングルプロセッサまたはマルチプロセッサコンピュータシステム、ミニコンピューティングデバイス、メインフレームコンピュータのほかに、パーソナルコンピュータ、ハンドヘルドコンピューティングデバイス（例：パーソナルデジタルアシスタント（ＰＤＡ）、電話、時計など）、マイクロプロセッサベースまたはプログラマブルコンシューマエレクトロニクスやインダストリアルエレクトロニクスなどが含まれている。図示の側面は、通信ネットワークを通してリンクされたリモート処理デバイスによってタスクが実行されるような分散コンピューティング環境で実施することも可能である。なお、請求項に記載の本発明のすべての側面でないとしても、その一部はスタンドアロンコンピュータ上で実施することが可能である。分散コンピューティング環境では、プログラムモジュールは、ローカルとリモートの両方のメモリストレージデバイスに置かれていることがある。
【００４９】
図９を参照して説明すると、本明細書に開示されている種々の側面を実現する例示環境は、コンピュータ９１２（例：デスクトップ、ラップトップ、サーバ、ハンドヘルド、プログラマブルコンシューマまたはインダストリアルエレクトロニクスなど）を含んでいる。コンピュータ９１２は処理ユニット９１４、システムメモリ９１６、およびシステムバス９１８を装備している。システムバス９１８は、システムメモリ９１６（これに限定されない）を含むシステムコンポーネントを処理ユニット９１４に結合している。処理ユニット９１４は、利用可能な種々のマイクロプロセッサの任意のものであり得る。デュアルマイクロプロセッサおよびその他のマルチプロセッサアーキテクチャ（例：マルチコア）を処理ユニット９１４として使用することも可能である。
【００５０】
システムバス９１８は、数種タイプのバス構造の任意のものにすることも可能であり、その中には、任意の種類の利用可能な種々のバスアーキテクチャを採用したメモリバスまたはメモリコントローラ、周辺バスまたは外部バス、および／またはローカルバスが含まれており、バスアーキテクチャの中には、１１ビットバス、ＩＳＡ(Industrial Standard Architecture)、ＭＳＡ(Micro-Channel Architecture)、ＥＩＳＡ(Extended ISA)、ＩＤＥ(Intelligent Drive Electronics)、ＶＬＢ(VESA Local Bus)、ＰＣＩ(Peripheral Component Interconnect)、ＵＳＢ(Universal Serial Bus)、ＡＧＰ(Advanced Graphics Port)、ＰＣＭＣＩＡ(Personal Computer Memory Card International Association bus)、およびＳＣＳＩ(Small Computer Systems Interface)が含まれているが、これらに限定されない。
【００５１】
システムメモリ９１６には揮発性メモリ９２０と不揮発性メモリ９２２が含まれている。スタートアップ時の期間のように、コンピュータ９１２内のエレメント間で情報を転送する基本ルーチンで構成された基本入出力システム(basic input/output system-BIOS)は不揮発性メモリ９２２に格納されている。不揮発性メモリ９２２を例示すると、ＲＯＭ(read only memory)、ＰＲＯＭ(programmable ROM)、ＥＥＰＲＯＭ (electrically programmable ROM)、ＥＥＰＲＯＭ(electrically erasable ROM)、またはフラッシュメモリがあるが、これらに限定されない。揮発性メモリ９２０には、外部キャッシュメモリの働きをするＲＡＭ(random access memory)が含まれている。
【００５２】
コンピュータ９１２は、取り外し可能／取り外し不能で揮発性／不揮発性のコンピュータ記憶媒体も装備している。図９は、大容量または補助ストレージ９２４を例示している。大容量ストレージ９２４としては、磁気ディスクドライブ、フロッピディスクドライブ、テープドライブ、Ｊａｚドライブ、Ｚｉｐドライブ、ＬＳ−１００ドライブ、フラッシュメモリカード、またはメモリスティックなどのドライブがあるが、これらに限定されない。そのほかに、大容量ストレージ９２４として可能なものに、他の記憶媒体とは独立または併用される記憶媒体があり、その中には、ＣＤ−ＲＯＭドライブ(compact disk ROM drive)、ＣＤ−Ｒドライブ(CD recordable drive)、ＣＤ−ＲＷドライブ(CD rewritable drive)またはＤＶＤ−ＲＯＭドライブ(digital versatile disk ROM drive)などの光ディスクドライブが含まれているが、これらに限定されない。大容量ストレージデバイス９２４をシステムバス９１８に接続するのを容易にするために、インタフェース９２６のような取り外し可能または取り外し不能インタフェースが使用されるのが代表的である。
【００５３】
当然に理解されるように、図９には、ユーザと、適当な動作環境９１０に記載されている基本的コンピュータリソースとの間の仲介の働きするソフトウェアが記載されている。そのようなソフトウェアとして、オペレーティングシステム９２８がある。オペレーティングシステム９２８は大容量ストレージ９２４にストアしておき、システムメモリ９１６にロードすることが可能であり、システム９１２のリソースを制御し、割り振る働きをする。システムアプリケーション９３０は、システムメモリ９１６または大容量ストレージ９２４のどちらかにストアされたプログラムモジュール９３２およびプログラムデータ９３４を通して、オペレーティングシステム９２８によるリソースの管理を利用している。当然に理解されるように、本発明は種々のオペレーティングシステムまたはオペレーティングシステムを組み合わせたものと共に実現することができる。
【００５４】
ユーザは、入力デバイス９３６を通してコマンドまたは情報をコンピュータ９１２に入力する。入力デバイス９３６としては、マウス、トラックボール、スタイラス、タッチパッド、キーボード、マイクロホン、ジョイスティック、ゲームパッド、サテライトディッシュ、スキャナ、ＴＶチューナカード、デジタルカメラ、デジタルビデオカメラ、Ｗｅｂカメラなどがあるが、これらに限定されない。これらの入力デバイスおよびその他の入力デバイスは、インタフェースポート９３８経由でシステムバス９１８を通して処理ユニット９１４に接続されている。インタフェースポート９３８としては、例えば、シリアルポート、パラレルポート、ゲームポート、ＵＳＢ(universal serial bus)がある。アウトプットデバイス９４０は、入力デバイス９３６と同じタイプのポートを使用している。従って、例えば、ＵＳＢポートは、コンピュータ９１２に入力を与え、コンピュータ９１２からの情報をアウトプットデバイス９４０に出力するために使用されることがある。アウトプットアダプタ９４２が用意されているのは、特殊なアダプタを必要とする他のアウトプットデバイス９４０の中には、ディスプレイ（例：フラットパネル、ＣＲＴ、ＬＣＤ、プラズマなど）、スピーカ、およびプリンタなどの、いくらかのアウトプットデバイス９４０が存在することを示すためである。アウトプットアダプタ９４２を例示すると、アウトプットデバイス９４０とシステムバス９１８との間を接続する手段となるビデオカードおよびサウンドカードがあるが、これらに限定されない。当然に理解されるように、リモートコンピュータ９４４のように入出力機能を備えたデバイスおよび／またはデバイスのシステムがほかにも存在する。
【００５５】
コンピュータ９１２は、リモートコンピュータ９４４のような、１または２以上のリモートコンピュータとの論理的コネクションを使用したネットワーキング環境で動作することができる。リモートコンピュータ９４４となり得るものとして、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ワークステーション、マイクロプロセッサベースのアプライアンス、ピアデバイスまたは他の共通ネットワークノードなどがあり、コンピュータ９１２に関連して説明したエレメントの多くまたはすべてを含んでいるのが代表的である。説明を簡単にするために、メモリストレージデバイス９４６だけがリモートコンピュータ９４４と共に示されている。リモートコンピュータ９４４は、ネットワークインタフェース９４８を通して論理的にコンピュータ９１２に接続されたあと、通信コネクション９５０を介して物理的に接続されている（例えば、有線または無線で）。ネットワークインタフェース９４８には、ローカルエリアネットワーク（ＬＡＮ）およびワイドエリアネットワーク（ＷＡＮ）などの通信ネットワークが含まれている。
【００５６】
通信コネクション９５０とは、ネットワークインタフェース９４８をバス９１８に接続するために使用されるハードウェア／ソフトウェアのことである。通信コネクション９５０は図を明確化するためにコンピュータ９１６内部に示されているが、コンピュータ９１２の外部に設けることも可能である。ネットワークインタフェース９４８に接続するために必要なハードウェア／ソフトウェアのとしては、通常の電話のグレードのモデム、ケーブルモデム、パワーモデムやＤＳＬモデム、ＩＳＤＮアダプタ、およびEthernet（登録商標）カードまたはコンポーネントがあるが、これらは単なる例示である。
【００５７】
図１０は、本発明がやりとりすることのできるサンプルコンピューティング環境１０００を示す概略ブロック図である。システム１０００は１または２以上のクライアント１０１０を含んでいる。クライアント１０１０は、ハードウェアおよび／またはソフトウェア（例：スレッド、プロセス、コンピューティングデバイス）にすることができる。システム１０００は、１または２以上のサーバ１０３０も含んでいる。従って、システム１０００は、他のモデルの中で、２層クライアント・サーバモデルに対応付けることも、多層モデル（例：クライアント、中間層サーバ、データサーバ）に対応付けることもできる。サーバ１０３０も、ハードウェアおよび／またはソフトウェア（例：スレッド、プロセス、コンピューティングデバイス）にすることができる。サーバ１０３０は、例えば、本発明を採用することにより変換を行なうスレッドを収容することができる。クライアント１０１０とサーバ１０３０との間の１つの可能なコミュニケーションは、２または３以上のコンピュータプロセス間で伝送されるデータパケットの形態になっていることがある。
【００５８】
システム１０００は、クライアント１０１０とサーバ１０３０の間のコミュニケーションを容易にするために使用できる通信フレームワーク１０５０を備えている。クライアント１０１０は、クライアント１０１０に独自の情報をストアするために使用できる１または２以上のクライアントデータストア１０６０に動作可能に接続されている。同様に、サーバ１０３０は、サーバ１０３０に独自の情報をストアするために使用できる１または２以上のサーバデータストア１０４０に動作可能に接続されている。例を挙げると、上述したアノニマイザシステム(anonymization system)およびその変種は、少なくとも１つのサーバ１０３０に対するＷｅｂサービスとして用意することができる。このＷｅｂサービスサーバは、複数の他のサーバ１０３０とだけでなく、関連のデータストア１０４０とも通信可能に結合すると、クライアント１０１０のプロキシとして機能させることもできる。
【００５９】
上述した内容には、請求項に記載の主題の側面の例が含まれている。当然のことであるが、請求項に記載の主題を説明するためにコンポーネントまたは方法の想到し得る組み合わせをすべて記載することは不可能であるが、この分野の通常知識を有するものならば理解されるように、開示した主題の別の組み合わせおよび置換も多数可能である。従って、開示した主題は、請求項に記載の本発明の精神および範囲内に属する改変、変更および変形をすべて包含するものである。さらに、「含む」、「備えた」や「備えている」の用語またはこれらの変形が詳細説明または請求項のどちらかに使用されている限りにおいて、これらの用語は、「含む」が請求項の中で移行語として使用されるときに意味するのと同じように、「含む」の用語と同じように包含的であることを目的としている。
【図面の簡単な説明】
【００６０】
【図１】センテンスからのクエリ（例えばクエリログ）を分類ツリー構造にエンコードし、さらにかかるセンテンスの分類をツリー構造内のノードと関連付けられたローカル言語モデルにエンコードする例示システムを示すブロック図である。
【図２】本発明の一側面に従って平滑化されるツリー構造を示す図である。
【図３】本発明の一側面に従ってツリー構造を取得する特定のエンコード方法を示す図である。
【図４】本発明の一側面に従ってツリー構造をデコードする別の方法を示す図である。
【図５】人口知能コンポーネントを使用してツリー構造の平滑化を容易にする例示のエンコーダ／デコーダを示す図である。
【図６】ローカル化言語モデルコンポーネントに基づいて入力データを拡張するシステムを示す図である。
【図７】本発明の一側面に従ってローカル化言語に基づいて暗黙的ワイルドカードを入力データに挿入するシステムを示す図である。
【図８】ローカル関心事に基づいて入力データの拡張を容易にする方法を示す図である。
【図９】請求項に記載の主題に従って使用できる例示動作環境を示す図である。
【図１０】請求項に記載の主題の種々新規側面の使用を可能にする例示ネットワーキング環境を示す図である。
【図１】
2009535732.tif 000006
【図２】
2009535732.tif 000007
【図３】
2009535732.tif 000008
【図４】
2009535732.tif 000009
【図５】
2009535732.tif 000010
【図６】
2009535732.tif 000011
【図７】
2009535732.tif 000012
【図８】
2009535732.tif 000013
【図９】
2009535732.tif 000014
【図１０】
2009535732.tif 000015
【国際調査報告】
2009535732.tif 000016
2009535732.tif 000017