(57)【特許請求の範囲】
【請求項１】
文書のコレクションを受信する段階と、
前記文書を１又は２以上のクラスタにクラスタリングする段階と、
前記１又は２以上のクラスタの各クラスタに対するクラスタ・ベクトルを生成する段階と、
対象プロファイルに関連付けられた対象ベクトルを生成する段階であって、前記対象ベクトルは識別されたユーザに対して生成されるとともに保存される、段階と、
前記クラスタ・ベクトルの各々と前記対象ベクトルを比較する段階と、
前記クラスタ・ベクトルの各々と前記対象ベクトルとの比較に基づいて前記１又は２以上のクラスタの１又は２以上を選択する段階と、
選択された１又は２以上のクラスタから文書を使用して言語モデルを生成する段階と
を有し、
前記対象ベクトルは、少なくとも１つのユーザ辞書及びユーザ入力から生成することを特徴とする方法。
【請求項２】
言語モデルを生成する段階は、
前記選択された１又は２以上のクラスタの前記文書からＮグラムのコレクションを識別する段階を有し、
各Ｎグラムは、前記選択された１又は２以上のクラスタの前記文書中の発生に関して、対応する相対頻度を有する
ことを特徴とする請求項１に記載の方法。
【請求項３】
各クラスタは、トピック又はドメインと関連付けられる
ことを特徴とする請求項１に記載の方法。
【請求項４】
各クラスタ・ベクトルは、対応するクラスタに対する重心を表す
ことを特徴とする請求項１に記載の方法。
【請求項５】
前記文書をクラスタリングする段階は、
クラスタに各文書を無作為に割り当てる段階と、
収束するまで、各クラスタに対する重心を繰り返し計算するとともに、最近傍の重心に基づいてクラスタに各文書を再割り当てする段階と、
を有することを特徴とする請求項４に記載の方法。
【請求項６】
前記対象ベクトルは、用語頻度ベクトルを有する
ことを特徴とする請求項１に記載の方法。
【請求項７】
前記比較する段階は、
前記対象ベクトルと前記クラスタ・ベクトルの各々との間のコサイン類似度を計算する段階
を有することを特徴とする請求項１に記載の方法。
【請求項８】
１又は２以上の追加文書を受信する段階と、
前記１又は２以上の追加文書に基づいて前記言語モデルを更新する段階と
を更に有することを特徴とする請求項１に記載の方法。
【請求項９】
文書のコレクションを受信する段階と、
１又は２以上の一般クラスタに前記文書をクラスタリングする段階と、
前記１又は２以上の一般クラスタの各クラスタに対するクラスタ・ベクトルを生成する段階と、
対象プロファイルに関連付けられた対象ベクトルを生成する段階であって、前記対象ベクトルは識別されたユーザに対して生成されるとともに保存される、段階と、
前記クラスタ・ベクトルの各々と前記対象ベクトルを比較する段階と、
前記クラスタ・ベクトルの各々と前記対象ベクトルとの比較に基づいて前記１又は２以上の一般クラスタの１又は２以上を選択する段階と
を有し、
前記対象ベクトルは、少なくとも１つのユーザ辞書及びユーザ入力から生成することを特徴とする方法。
【請求項１０】
前記選択された１又は２以上の一般クラスタから文書を使用して、言語モデルを生成する段階
をさらに有することを特徴とする請求項９に記載の方法。
【請求項１１】
ユーザを識別するユーザ入力を受信する段階と、
前記ユーザに対応するユーザ・プロファイルを識別する段階であって、前記ユーザ・プロファイルは識別されたユーザに対して生成されるとともに保存される、段階と、
ユーザ固有の言語モデルを生成するために識別したプロファイルを使用する段階と、
第一クライアントに前記ユーザ固有の言語モデルを送信する段階と、
文書のコレクションを受信する段階と、
１又は２以上のクラスタに前記文書をクラスタリングする段階と、
前記１又は２以上のクラスタの各クラスタに対するクラスタ・ベクトルを生成する段階と、
前記ユーザ・プロファイルに関連付けられた対象ベクトルを生成する段階と、
前記クラスタ・ベクトルの各々と前記対象ベクトルを比較する段階と、
前記クラスタ・ベクトルの各々と前記対象ベクトルとの比較に基づいて前記１又は２以上のクラスタの１又は２以上を選択する段階と、
を有し、
前記対象ベクトルは、少なくとも１つのユーザ辞書及びユーザ入力から生成することを特徴とする方法。
【請求項１２】
第二クライアントに前記ユーザ固有の言語モデルを送信する段階
をさらに有することを特徴とする請求項１１に記載の方法。
【請求項１３】
前記ユーザ固有の言語モデルを生成する段階は、
前記選択された１又は２以上のクラスタの前記文書からＮグラムのコレクションを識別する段階をさらに有し、
各Ｎグラムは、前記選択された１又は２以上のクラスタの前記文書中の発生に関して、対応する相対頻度を有する
ことを特徴とする請求項１１に記載の方法。
【請求項１４】
文書のコレクションを受信する段階と、
１又は２以上のクラスタに前記文書をクラスタリングする段階と、
前記１又は２以上のクラスタの各クラスタに対するクラスタ・ベクトルを生成する段階と、
対象プロファイルに関連付けられた対象ベクトルを生成する段階であって、前記対象プロファイルは識別されたユーザに対して生成されるとともに保存される、段階と、
前記クラスタ・ベクトルの各々と前記対象ベクトルを比較する段階と、
前記クラスタ・ベクトルの各々と前記対象ベクトルとの比較に基づいて前記１又は２以上のクラスタの１又は２以上を選択する段階と、
選択された１又は２以上のクラスタから文書を使用して、言語モデルを生成する段階と
を有し、前記対象ベクトルは、少なくとも１つのユーザ辞書及びユーザ入力から生成することを特徴とする動作をデータ処理装置に実行させるように動作可能なコンピュータ・プログラム。
【請求項１５】
コンピュータ・プログラムを有する機械可読記録デバイスと、
１又は２以上のコンピュータと
を具備し、
前記１又は２以上のコンピュータは、前記コンピュータ・プログラムを読み込むことで、
文書のコレクションを受信する段階と、
１又は２以上のクラスタに前記文書をクラスタリングする段階と、
前記１又は２以上のクラスタの各クラスタに対するクラスタ・ベクトルを生成する段階と、
対象プロファイルに関連付けられた対象ベクトルを生成する段階であって、前記対象プロファイルは識別されたユーザに対して生成されるとともに保存される、段階と、
前記クラスタ・ベクトルの各々と前記対象ベクトルを比較する段階と、
前記クラスタ・ベクトルの各々と前記対象ベクトルとの比較に基づいて前記１又は２以上のクラスタの１又は２以上を選択する段階と、
選択された１又は２以上のクラスタから文書を使用して、言語モデルを生成する段階と
を有する処理を実行可能であり、
前記対象ベクトルは、少なくとも１つのユーザ辞書及びユーザ入力から生成する
ことを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、言語モデルに関する。
【背景技術】
【０００２】
言語モデルは、所定の語彙中のトークンの文字列（例えば、単語又は文字）が言語中で出現する確率をモデル化するために使用する。例えば、言語モデルは、限定しないが、インプット・メソッド・エディタ（IME）、自動音声認識（ARS）、機械翻訳、手書き認識、及び光学式文字認識（OCR）アプリケーションなどの入力方法で使用される。前記語彙中のトークンの文字列に対する確率をモデル化することは、一般的にチェーン・ルールを使用するとともに、所定の文字列の文脈中における、所定のトークンwの確率ｐ(w｜context)の計算を行う。ここで前記文脈は前記所定のトークンwより前にある文字列中のトークンである。
【０００３】
Ｎグラム言語モデルでは、テキスト中のｎ個の連続トークンは、Ｎグラムに形成されるとともに、現在の単語ｚの確率は、例えば、n-1個の先行単語の確率に依存している。例えば、p(zi｜context)＝p(zi｜zi-n+1,zi-n+2,...,zi-1)である。Ｎグラムは、前記Ｎグラム中のトークンの番号である順序を有する。例えば、１グラム（又はユニグラム）は、１つのトークンを有しており、２グラム（又はバイグラム）は、２つのトークンを有している。
【０００４】
テキスト（例えば、文章中の単語）中のＮグラムの確率分布は、大半が、文脈に依存しており、そのことはまた、より一般的な意味で見ることができる。例えば、テキスト中の特定のＮグラムの前記確率分布は、前記テキストによって表現されたトピック、又は前記テキストの発生するドメイン次第であることができる。スポーツ記事中に発生する「バスケットボール」の確率は、金融関連記事中に発生する「バスケットボール」の確率よりも大きい。加えて、異なるユーザが、例えば、同じアイデアを表現するのに、異なる単語を使用する（例えば、特別扱いする）可能性がある。スペインのユーザは、「フットボール」を使用し、一方アメリカ合衆国のユーザは、「サッカー」を使用するであろう。従って、テキスト中のＮグラムの確率分布は、ユーザ依存とドメイン依存の両方でありうる。
【０００５】
従来の入力方法は、汎用的な言語モデルを使用している。例えば、一つの言語モデルを、全てのユーザに対して使用することもある。他の例では、前記同じ言語モデルを使用するとともに、全てのドメイン（例えば、コンピュータ・システムのドメイン、地理的なドメイン）に対する学習用データから生成することもある。一般の言語モデルは、入力方法の用途全般に対して最適化されていない。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本明細書は、カスタム言語モデルに関する技術を記載している。
【課題を解決するための手段】
【０００７】
一般に、本明細書中に記載の要旨の一態様は、文書のコレクションを受信する動作と、前記文書を１又は２以上のクラスタにクラスタリングする動作と、前記１又は２以上のクラスタの各クラスタに対するクラスタ・ベクトルを生成する動作と、対象プロファイルに関連付けられた対象ベクトルを生成する動作と、前記クラスタ・ベクトルの各々と前記対象ベクトルを比較する動作と、比較に基づいて前記１又は２以上のクラスタの１又は２以上を選択する動作と、選択された１又は２以上のクラスタから文書を使用して言語モデルを生成する動作とを有する方法で具現化できる。この態様の他の実施形態は、対応するシステム、装置、及びコンピュータ・プログラム製品を含む。
【０００８】
これら及び他の具体例では、任意の方法で、１又は２以上の以下の特徴を有することができる。言語モデルを生成する段階は、選択された１又は２以上のクラスタの文書から、Ｎグラムのコレクションを識別する段階を有する。各Ｎグラムは、選択された前記１又は２以上のクラスタの文書中の発生に関して、対応する相対頻度を有する。各クラスタは、トピック又はドメインと関連付けされている。各クラスタ・ベクトルは、対応するクラスタに対する重心を表す。前記文書のクラスタリングは、クラスタに各文書を無作為に割り当てる段階と、収束するまで、各クラスタに対する重心を反復して計算するとともに、最近傍の重心に基づいてクラスタに各文書を再割り当てする段階とを有する。前記対象ベクトルは、用語頻度ベクトルを有する。前記対象ベクトルは、ユーザ辞書又はユーザ入力のうちの少なくとも１つから生成する。比較する段階は、前記対象ベクトル及び各前記クラスタ・ベクトルの間のコサイン類似度を計算する段階を有する。前記方法は、１又は２以上の追加の文書を受信する段階と、前記１又は２以上の追加の文書に基づいて前記言語モデルを更新する段階とをさらに有する。
【０００９】
一般に、本明細書中に記載の要旨の他の態様は、文書のコレクションを受信する動作と、１又は２以上の一般クラスタに前記文書をクラスタリングする動作と、前記１又は２以上の一般クラスタの各クラスタに対するクラスタ・ベクトルを生成する動作と、対象プロファイルに関連付けられた対象ベクトルを生成する動作と、前記クラスタ・ベクトルの各々と前記対象ベクトルを比較する動作と、前記比較に基づいて前記１又は２以上の一般クラスタの１又は２以上を選択する動作とを有する方法で具現化できる。この態様の他の具体例は、対応するシステム、装置、及びコンピュータ・プログラム製品を更に含む。
【００１０】
これら及び他の具体例は、任意の方法で、１又は２以上の以下の特徴を有することができる。前記方法は、選択された１又は２以上に汎用クラスタから文書を使用して、言語モデルを生成する段階をさらに有する。
【００１１】
一般に、本明細書中に記載の要旨の他の態様は、前記ユーザを識別するユーザ入力を受信する動作と、前記ユーザに対応するユーザ・プロファイルを識別する動作と、ユーザ固有の言語モデルを生成するために識別したプロファイルを使用する動作と、第一クライアントに前記ユーザ固有の言語モデルを送信する動作とを有する方法で具現化できる。この態様の他の具体例は、対応するシステム、装置、及びコンピュータ・プログラム製品を含む。
【００１２】
これら及び他の具体例は、任意の方法で、１又は２以上の以下の特徴を有することができる。前記方法は、第二クライアントに前記ユーザ固有の言語モデルを送信する段階をさらに有する。前記方法は、文書のコレクションを受信する段階と、１又は２以上のクラスタに前記文書をクラスタリングする段階と、前記１又は２以上のクラスタの各クラスタに対するクラスタ・ベクトルを生成する段階と、前記ユーザ・プロファイルに関連付けられた対象ベクトルを生成する段階と、前記クラスタ・ベクトルの各々と前記対象ベクトルを比較する段階と、比較に基づいて前記１又は２以上のクラスタの１又は２以上を選択する段階とを更に有する。ユーザ固有の言語モデルを生成する段階は、選択された前記１又は２以上のクラスタの文書からＮグラムのコレクションを識別する段階を有する。各Ｎグラムは、選択された前記１又は２以上のクラスタの文書中の発生に関して、対応する相対頻度を有する。
【００１３】
一般に、本明細書中に記載の要旨の他の態様は、１又は２以上の文書の第一コレクションを受信する動作と、１又は２以上の文書の前記第一コレクションに基づいてプロファイルを生成する動作と、１又は２以上の文書の第二コレクションを受信する動作と、１又は２以上の前記第二コレクションと前記プロファイルとに基づいて、カスタム言語モデルを生成する動作と、クライアントに前記カスタム言語モデルを送信する動作とを有する方法で具現化できる。この態様の他の具体例は、対応するシステム、装置、及びコンピュータ・プログラム製品を含む。
【００１４】
これら及び他の具体例は、任意の方法で、１又は２以上の以下の特徴を有することができる。１又は２以上の文書の前記第一コレクションは、ユーザ辞書又は前記ユーザの入力習慣を表すユーザ入力の少なくとも１を有する。
【００１５】
本明細書中に記載の要旨の特定の具体例は、１又は２以上の以下の利点を実現するように実施できる。サブセットへの学習用データの教師なし分類（Unsupervised classification）は、（i）カスタム言語モデルを学習させるために検討するデータ量（例えば、コーパスのサイズ）を増やすとともに、（ii）ユーザ・エラーを減らすために、ユーザの介入量を減らすことができる。
【００１６】
カスタム言語モデルは、前記入力方法の正確率、適合率、及び再呼出率を増加させ、それによって入力エラー率を下げるために、特定の入力方法の用途に対して（例えば、特定のユーザ及びドメインに対して）生成できる。加えて、カスタム言語モデルは、ユーザの習性（例えば、ユーザの習性、又はユーザ辞書を表す前記ユーザが入力した文書に基づいて生成／改良する）に適合させることができる。それによって、カスタム言語モデルは、さらに正確率、適合率、及び再呼出率を増加させるとともに、前記入力エラー率を減らすことができる。その上、カスタム言語モデルは、トピックス依存であるとともに、ユーザの現在の入力のトピックに適合させることができる。例えば、ユーザは、関心のあるトピックスに基づいて、サーバ上に保存されている、種々のトピックスの複数のカスタム言語モデルから選択してもよい。カスタム言語モデルは、前記利用可能な学習用データ全体のサブセットから学習させることができるため、前記カスタム言語モデルは、一般の言語モデルよりもメモリ・サイズをより小さくできる。結果として、前記カスタム言語モデルの使用は、（i）前記カスタム言語モデルを使用する入力方法のメモリ・フットプリントと、（ii）前記カスタム言語モデルを保存するために使用するメモリ量と、（iii）ユーザに前記カスタム言語モデルを提供するために要求される単位時間当たりの帯域幅の量とを減少させる。
【００１７】
本明細書に記載の要旨の１又は２以上の具体例の詳細は、添付の図面と以下の明細書中で明らかにする。前記要旨の他の特徴、様態、及び利点は、明細書、図面、及び請求項から明らかになる。
【００１８】
種々の図中の同様の参照番号、及び名称は、同一の要素を示す。
【図面の簡単な説明】
【００１９】
【図１】カスタム言語モデルを生成するためのシステム例を示す図である。
【図２】文書のクラスタ例を含めた図である。
【図３】図２のクラスタ例、及び対応する重心を含めた図である。
【図４】図２の文書のうちのいくつかの再分類例を説明した図である。
【図５】図４の再分類に基づいて、クラスタ例の再調整例を説明した図である。
【図６】図５の各クラスタ例に対するプロファイルの生成例を説明した図である。
【図７】１又は２以上の図６のクラスタ例の選択例を説明した図である。
【図８】カスタム言語モデルの生成例を説明した図である。
【図９Ａ】クラスタ・ベクトルを生成するための処理例を図示したフローチャートである。
【図９Ｂ】カスタム言語モデルを生成するための処理例を図示したフローチャートである。
【発明を実施するための形態】
【００２０】
概要
図１は、カスタム言語モデル１２４を生成するためのシステム例１００を図示した図である。前記システム１００は、第一クライアント１１２（例えば、デスクトップ・コンピュータ）、第二クライアント１１４（例えば、携帯電話）、及びサーバ１２０を有している。前記サーバ１２０は、対象プロファイル１２２、カスタム言語モデル１２４、及び学習用データ１２６（例えば、構造なしコーパス）を有することができる。
【００２１】
カスタム言語モデル生成の概要として、前記学習用データ１２６は、前記学習用データ１２６のコレクション内に分類できる（例えば、文書の１又は２以上のコレクション）。前記サーバ１２０は、ユーザを識別するユーザ入力を受信できる（例えば、前記第一クライアント１１２の第一ユーザ、前記第一クライアント１１２の第二ユーザ、前記第二クライアント１１４の第一ユーザ）。例えば、前記サーバ１２０は、前記ユーザを識別するために、ユーザ・ログイン情報、又はクッキーを使用できる。前記サーバ１２０は、各ユーザに対応した対象プロファイル１２２（例えば、ユーザ・プロファイル）を生成できる。
【００２２】
いくつかの実施形態では、前記対象プロファイル１２２は、予め決定されうる。例えば、前記サーバ１２０は、前記ユーザに対応した、以前に作成した対象プロファイル１２２を識別できる。いくつかの実施形態では、前記対象プロファイル１２２は、前記ユーザ又はユーザ入力の辞書に基づいて生成してもよい（例えば、前記ユーザの入力習性に対応した、前記ユーザによって提供されたデータ）。その上、前記対象プロファイル１２２は、前記サーバ１２０とクライアント（例えば、第一クライアント１１２）との間を、自動あるいは手動で同期できる。前記対象プロファイル１２２は、前記学習用データ１２６の各サブセットのプロファイルと比較できる。１又は２以上の前記学習用データ１２６のサブセットは、例えば、前記対象プロファイル１２２と各サブセットの前記プロファイルとの間の類似度に基づいて選択できる。
【００２３】
学習用データ１２６の選択されたサブセットは、カスタム言語モデル１２４（例えば、ユーザ固有の言語モデル、ドメイン固有の言語モデル）を生成するために使用できる。前記カスタム言語モデルは、ネットワークを介して、例えば第一クライアント１１２に送信できる。前記第一クライアント１１２は、前記ユーザが使用する入力メソッドのための前記カスタム言語モデルを使用できる。いくつかの実施形態では、カスタム言語モデルのコピーは、前記サーバ１２０上に保存される。前記ユーザが、前記第二クライアント１１４で入力メソッドを使用する場合、例えば、前記カスタム言語モデルのコピーを、前記第二クライアント１１４に送信できる（及び／又は、第二クライアント上で更新できる）。
【００２４】
いくつかの実施形態では、前記対象プロファイル１２２、カスタム言語モデル１２４、及び／又は学習用データ１２６は、複数のサーバ上か又は複数の他の場所に保存する。例えば、前記学習用データ１２６は、前記サーバ１２０によってアクセス可能な任意の文書を有することができる。特に、前記学習用データ１２６は、限定しないが、ユーザが使用するインプット・メソッド・エディタ（IME）、ＩＭＥユーザ辞書、ウェブ・ページ、検索クエリ・ログ、電子メール、ブログ、インスタント・メッセージ（IM）スクリプト、及びニュース記事を有し、カスタム言語モデル１２４を学習させるために使用できる。
【００２５】
対象プロファイルの生成
対象プロファイル１２２は、各ユーザ（又はドメイン）に対して生成可能である。いくつかの実施形態では、前記対象プロファイル１２２を、識別されたユーザに対して生成する。例えば、前記ユーザは、ログイン情報を提供することによって、彼自身／彼女自身を識別できるとともに、対象プロファイル１２２は、例えば、識別されたユーザに関連付けられたユーザ辞書といった、前記ユーザに関連付けられたデータに基づいて生成可能である。ユーザ辞書は、例えば、ＩＭＥから、及び／又はユーザ入力から所定の単語を有することができる。加えて、ユーザ辞書は、例えば、ユーザの入力履歴中（例として、チャット・テキスト、検索クエリ）の単語数及び頻度といった単語の使用法に関連付けられた統計を有することができる。また、ユーザ入力中に発生するＮグラムのような他の統計データは、前記対象プロファイル１２２内に保存できる。いくつかの実施形態では、対象プロファイル１２２を、前記ユーザが提供するデータに基づいて前記ユーザに対して生成する。例えば、ユーザは、彼／彼女の入力習性を表す文書を送信できるとともに、対象プロファイル１２２は、送信文書に基づいて生成可能である。いくつかの実施形態では、前記対象プロファイル１２２を、前記サーバ１２０（又はクライアント）上に保存するとともに、再利用する。
【００２６】
前記対象プロファイル１２２は、前記ユーザにとっての特定トークンの比重を表すことができる。いくつかの実施形態では、前記対象プロファイル１２２は、ベクトルを使用して表す。例えば、特徴ベクトルは、１又は２以上の特徴（例えば、用語）と、各特徴に対して対応する用語頻度（tf）加重値（weight）を有することができる。前記ｔｆ加重値は、前記ユーザにとっての特徴の重要度の統計的基準として使用できる。例えば、ユーザにとっての特徴の前記重要度は、前記ユーザ、又は前記ユーザの辞書によって入力した文書のコレクション中で、前記特徴が発生する頻度（例えば、用語頻度）に比例して増加可能である。
【００２７】
文書中の前記用語頻度は、特定用語が前記文書中に発生する相対頻度であり、かつ次のように表すことができる：
【数１】
0005475795.tif 000002
ここで、前記用語頻度は、文書（dj）中の前記特定用語の発生度数（nij）を、文書（dj）中の全ての用語の発生度数によって割ったものである。
【００２８】
いくつかの実施形態では、ｔｆ−ｉｄｆ加重値は、前記ユーザにとっての前記特徴の重みの統計的基準として使用できる。ｔｆ−ｉｄｆ加重値は、用語頻度と、逆文書頻度（idf）との積によって計算できる。
【００２９】
前記逆文書頻度（idf）は、次のように表すことができる：
【数２】
0005475795.tif 000003
ここで、文書のコレクション中の全ての文書の個数Ｄは、前記用語tiを含む文書djの個数Ｄjによって除されている。いくつかの実施形態では、１０を底とする対数の代わりに自然対数を使用する。
【００３０】
ｔｄｆ−ｉｄｆ加重値は、次のように表すことができる：
tf_idfi,j＝tfi,j・idfi,j
【００３１】
前記対象プロファイル１２２は、前記カスタム言語モデル１２４を学習させるために使用した学習用データ１２６のサブセットを決定するために、学習用データ１２６のサブセットのプロファイル（例えば、特徴ベクトル）と比較できる。
【００３２】
学習用データの分類
前記学習用データ１２６は、種々の分類方法を使用してサブセットに分類できる。いくつかの実施形態では、前記学習用データ１２６をサブセットに分類するためにクラスタリングを使用する。例えば、分割最適化クラスタリング（例として、ｋ平均法クラスタリング、ＬＳＨ（locality sensitive hashing）、グラフ理論法）、又は階層的クラスタリング（例として、凝集型階層的クラスタリング、概念クラスタリング）が、前記学習用データ１２６を分類するために使用できる。他の例として、特異値分解（ＳＶＤ）と、潜在意味解析（ＬＳＡ）と、ニューラル・ネットワークとを使用することで、文書をクラスタと相互に関係付けることができる。他の実施形態が可能である。例えば、前記学習用データ１２６をサブセットに分類するために、２次分類器、又はｋ近傍法を使用できる。
【００３３】
図２は、文書のクラスタ例（２１０、２２０、２３０、２４０、及び２５０）を含む図である。前記文書は、図２中では点によって表されている。ｋ平均法クラスタリング手法が、前記クラスタ生成のために使用できる。特に、クラスタの個数ｋを選択できる。例えば、５つのクラスタ（ｋ＝５）を図２に図示する。前記クラスタ２１０、２２０、２３０、２４０、及び２５０は、無作為に生成できる。特に、各文書を無作為にクラスタに割り当てることができる。いくつかの実施形態では、最初に文書を１クラスタ以上に割り当てることができる。以下に記載するように、クラスタ２１０、２２０、２３０、２４０、及び２５０の各々に対して重心（又はクラスタ中心）を決めることができる。
【００３４】
図３は、図２のクラスタ例と、対応する重心（２１５、２２５、２３５、２４５、及び２５５）とを含む図である。いくつかの実施形態では、クラスタの重心は、前記クラスタ中の各文書に対するｔｆ−ｉｄｆ（用語頻度−逆文書頻度）ベクトルを計算することによって決定する。前記ｔｆ−ｉｄｆベクトルは、特徴と、対応する特徴加重値（例えば、ｔｆ−ｉｄｆ加重値）とを含むことができる。クラスタの重心は、前記クラスタ中の文書に対応するｔｆ−ｉｄｆベクトル全体の平均によって表すことができる。前記ｔｆ−ｉｄｆ加重値は、上記記載の方法で計算できる。
【００３５】
例として、特定の文書（例えば、図３のクラスタ２５０内の点）は、５，０００語を含んでもよい。前記文書中で、「バスケットボール」という単語が、２００回発生してもよい。「バスケットボール」に対する用語頻度は、０．０４（２００／５，０００）である。クラスタ２５０中の文書のコレクション（例えば、クラスタ２５０中の全ての点）は、９つの文書を含む。「バスケットボール」が、９文書中１文書に出現すると仮定すると、逆文書頻度は、ｌｏｇ（９／１）≒０．９５である。その文書に対する前記ｔｆ−ｉｄｆベクトルは、前記特徴「バスケットボール」とともに、（０．０４・０．９５）≒０．０４の対応するｔｆ−ｉｄｆ加重値を有することができる。同様の計算を使用することで、特定のクラスタの文書中の別の用語に対して、別の特徴とウェイトを生成できる。
【００３６】
前記クラスタの重心は、前記クラスタ中の前記文書全体に対する前記ｔｆ−ｉｄｆベクトルの平均として計算できる。例えば、各々の文書がｔｆ−ｉｄｆベクトル（各々が３つの特徴を持つ）を有する２つの文書Ｘ及びＹを有するクラスタに対し、前記文書Ｘ及びＹは、それぞれ次のように表すことができる：Ｘ＝（ｘ１，ｘ２，ｘ３）及びＹ＝（ｙ１，ｙ２，ｙ３）。前記クラスタの重心Ｚは、次のように表すことができる：Ｚ＝（ｚ１，ｚ２，ｚ３）、ここで、ｚ１＝（ｘ１＋ｙ１）／２；ｚ２＝（ｘ２＋ｙ２）／２；ｚ３＝（ｘ３＋ｙ３）／２である。
【００３７】
前記初期クラスタに対して前記重心を計算した後、各文書は、最近傍の重心に再割り当てされる。図４は、図２のいくつかの文書の再分類例を説明する図である。特に、図４は、対応する最近傍の重心に基づいて異なるクラスタに割り当てられたいくつかの文書を図示している。例えば、クラスタ２５０中の文書４１０は、矢印４１５に図示しているように、クラスタ２２０に再割り当てできる。最近傍の重心は、文書とクラスタの各重心との間の距離を計算することで決定できる。特に、前記文書を表す前記ｔｄ−ｉｄｆベクトルと、各重心を表す前記ｔｄ−ｉｄｆベクトルとの間の距離が計算できる。前述の例に戻ると、重心Ｚと文書Ｘとの間の距離は、コサイン距離として表すことができる：
【数３】
0005475795.tif 000004
【００３８】
前記文書は、前記文書から最小距離であるクラスタに割り当てることができる。前記文書の各々を、各々の文書の最近傍の重心に再割り当てした後、新しい重心を計算できる。
【００３９】
図５は、図４中の再分類に基づいたクラスタ例５１０・５２０・５３０・５４０・５５０の再調整例を説明する図である。図２及び図３に関して上述したように、新しい重心を決定できる。特に、重心５１５・５２５・５３５・５４５・５５５を、クラスタ５１０・５２０・５３０・５４０・５５０に対して決定できる。
【００４０】
最近傍の重心に基づく文書の再分類の複数回の繰り返しと、前記再分類に基づく前記クラスタの再調整の複数回の繰り返しとは、１又はそれ以上の基準を満たすまで実行できる。例えば、前記再分類及び再調整は、収束基準を満たすまで（例えば、文書が再割り当てされなくなるまで）、実行できる。
【００４１】
分類が完了した後、前記クラスタの各々に対するプロファイルを生成できる。図６は、図５のクラスタ例５１０・５２０・５３０・５４０・５５０の各々に対するプロファイル６１０・６２０・６３０・６４０・６５０の生成例を説明する図である。例えば、前記プロファイルは、前記各クラスタ中の前記文書に応じて、前記クラスタの各々に対して計算した（上述の通りに）ｔｄ−ｉｄｆベクトルによって表すことができる。
【００４２】
結果として生じたクラスタは、各クラスタへの前記文書の初期の無作為な割り当てに依存するため、いくつかの実施形態では、前記学習用データ１２６から追加のクラスタを作り出すために、上述の処理を繰り返す。
【００４３】
さらに、学習用データ１２６のサブセットが生成されるため、トピック又はドメインを、学習用データの各サブセットに対して予め決定する必要はない。例えば、生成した前記クラスタを一般的なクラスタと考えることができる。特に、各クラスタは、当初、任意の特定のトピック／ドメインを表すために作り出されていないが、各クラスタは、本質的に、類似文書のクラスタリングの結果として、トピック又はドメインを表すことができる。結果として、例えば、前記クラスタを分類又は識別するために、トピック、キーワード、又はドメインを予め決定する必要はない。しかしながら、ユーザに対して生成したカスタム言語モデルを前記クラスタに基づいて生成できるとともに、前記カスタム言語モデルはまた、本質的に、前記クラスタによって表された１又は２以上のトピックス／ドメインを含むことができる。
【００４４】
学習用データの選択
図７は、図６の１又は２以上のクラスタ例の選択例を説明する図である。特に、クラスタ５１０・５２０は、ユーザ辞書７１０から対象プロファイルに基づいて選択されている。前述のように、前記対象プロファイルは、前記対象プロファイルと各クラスタ・プロファイルとの間の類似度を決定するために、各クラスタのプロファイルと比較できる。
【００４５】
いくつかの実施形態では、コサイン類似度を、前記対象プロファイルと各クラスタ・プロファイルとの間で計算する。前記コサイン類似度は、２つのベクトルの類似度を測定するために使用できる。前記コサイン類似度は次のように表すことができる：
【数４】
0005475795.tif 000005
ここで、ｘiは、前記対象プロファイルを表すベクトルであるとともに、ｙiはクラスタ・プロファイルを表すベクトルである。２つのベクトルの間の前記コサイン類似度が１に近づくほど、前記２つのベクトルは、近づいているか、又はより類似している。前記コサイン類似度は、前記クラスタが選択されたかどうかを判断するために閾値と比較できる。例えば、前記コサイン類似度が０．８の閾値より大きい場合、ｘ及びｙは、トピックに関して高い関連性があると考えることができ、かつｙに対応するクラスタを選択できる。
【００４６】
カスタム言語モデルの生成
図８は、カスタム言語モデル８１０の生成例を説明する図である。前記カスタム言語モデルは、選択された前記クラスタ中の前記文書に基づいて生成できる。前記カスタム言語モデルは、Ｎグラムと、前記Ｎグラムが選択された前記クラスタ中の前記文書中に発生するという、対応する確率とを有することができる。
【００４７】
特定の文字列が発生するＮグラム言語モデルに応じた確率は、連鎖法則を使用して決定できる。前記連鎖法則は、個々の確率の積として、文字列の確率を決定する。このように、所定の文字列「ｅ1，ｅ2，...，ｅk」の場合の、文字列に対する確率ｐ(ｅ1，ｅ2，...，ｅk)は、次に等しい：
【数５】
0005475795.tif 000006
【００４８】
前記Ｎグラム言語モデルは、例えば、１グラム、２グラム、３グラムなどに制限するように、Ｎグラムの特定の最大サイズに制限できる。例えば、所定の文字列「NASA officials say they hope」とし、ここで前記最大Ｎグラム・オーダーを３グラムに制限すると、前記文字列に対する確率は、次のように条件付き確率の積として決定できる：ｐ(NASA officials say they hope)＝ｐ(NASA)・ｐ(officials｜NASA)・ｐ(say｜NASA officials)・ｐ(they｜officials say)・ｐ(hope｜say they)。これは、次のように一般化できる：
【数６】
0005475795.tif 000007
ここで、ｎは、前記言語モデル中で許容される最大のＮグラムのオーダーである。
【００４９】
一般的に、選択された前記クラスタの前記文書中の相対頻度に応じて、前記条件付き確率を実験的に決定する。例えば、上述の例では、「NASA officials」の文脈という条件下で、単語「say」の確率は、次の式によって与えられる：
【数７】
0005475795.tif 000008
ここで、ｆ(NASA officials say)は、前記選択されたクラスタの前記文書中で、文字列「NASA officials say」の発生度数、又は回数である。例えば、ｐ(say｜NASA officials)といった前記Ｎグラムに対する前記言語モデル内に格納された確率に対応するＮグラム言語モデル内の最大Ｎグラム・オーダーの範囲内の文字列に対する条件付き確率は、３グラム・エントリである「NASA officials say」に対する前記言語モデル内に格納された条件付き確率である。
【００５０】
図９Ａは、クラスタ・ベクトルを生成するための処理例を示すフローチャートである。便宜のため、クラスタ・ベクトルの生成は、前記生成を実行するシステムに関して記載する。システムは、文書のコレクションを受信する（９１０）。例えば、前記サーバ１２０は、前記学習用データ１２６を受信できる。前記システムは、１又は２以上のクラスタ内に前記文書をクラスタリングする（９２０）。例えば、前記サーバ中の分類エンジン（図示せず）は、前記文書をクラスタリングできる。前記システムは、前記１又は２以上のクラスタの各クラスタに対し、クラスタ・ベクトルを生成する（９３０）。例えば、前記サーバ１２０内の前記分類エンジンはまた、各クラスタに対してクラスタ・ベクトルを生成できる。
【００５１】
図９Ｂは、カスタム言語モデルを生成するための処理例を示すフローチャートである。便宜のため、前記カスタム言語モデルの生成は、前記生成を実行するシステムに関して記載する。前記システムは、前記対象プロファイルに関連付けられた対象ベクトルを生成する（９４０）。例えば、前記分類エンジンは、対象プロファイルに関連付けられた対象ベクトルを生成できる。前記システムは、前記クラスタ・ベクトルの各々と前記対象ベクトルを比較する（９５０）。例えば、前記サーバ１２０内の比較エンジン（図示せず）は、前記クラスタ・ベクトルの各々と前記対象ベクトルを比較できる。前記システムは、該比較に基づいて１又は２以上のクラスタのうちの１又は２以上を選択する（９６０）とともに、選択された１又は２以上のクラスタから文書を使用して、言語モデル（例えば、カスタム言語モデル）を生成する（９７０）。
【００５２】
本明細書は、英単語としてＮグラムの多くの例を説明しているが、記載した要旨及び機能的動作の実施形態は、他の言語（例えば、中国語、日本語、及び韓国語）に対して実行可能である。例えば、Ｎグラムは、１又は２以上の中国語を含むことができる。
【００５３】
電子文書（簡潔に文書と呼んでいた）は、必ずしもファイルに対応していない。文書は、当の文書専用の単一ファイル中、又は複数の調整ファイル内で、他の文書を含むファイルの一部の中に保存されていてもよい。
【００５４】
本明細書中の前記要旨及び前記機能的動作の実施形態は、本明細書中で開示した構造物及び構造的均等物、又は１又は２以上のそれらの組み合わせを有する、デジタル電子回路内、又はコンピュータ・ソフトウェア、ファームウェア、又はハードウェア内で実行できる。本明細書中に記載の要旨の実施形態は、１又は２以上のコンピュータ・プログラムとして、すなわち、データ処理装置によって実行するために、又はデータ処理装置の動作を制御するために、実体的なプログラム・キャリア上に符号化した、１又は２以上のコンピュータ・プログラム命令のモジュールとして実行できる。前記実体的なプログラム・キャリアは、コンピュータ可読媒体でありうる。前記コンピュータ可読媒体は、機械可読の記録デバイス、機械可読の記録回路基板、メモリ・デバイス、機械可読の伝播信号をもたらす物体の構成物、又は１又は２以上のそれらの組み合わせでありうる。
【００５５】
「データ処理装置」という用語は、例のようにプログラム可能なプロセッサ、コンピュータ、もしくはマルチ・プロセッサ又はマルチ・コンピュータを含め、データを処理するための全ての装置、デバイス、及び機械を含む。前記装置は、ハードウェアに加え、当のコンピュータ・プログラムのための実行環境を作り出すコードを有することができる。例えば、コードは、プロセッサ・ファームウェア、プロトコル・スタック、データベース管理システム、オペレーティング・システム、又は１又は２以上のそれらの組み合わせを構成する。
【００５６】
コンピュータ・プログラム（プログラム、ソフトウェア、ソフトウェア・アプリケーション、スクリプト、又はコードとしても知られる）は、コンパイラ型又はインタプリタ型言語、若しくは宣言型又は手続き型言語を含め、プログラム言語の任意の形式で記述可能である。かつ、前記コンピュータ・プログラムは、スタンドアロン・プログラムとして、若しくは、モジュール、コンポーネント、サブルーチン、又はコンピュータ環境中で使用に適した他のユニットとしてなどの、任意の形式で展開可能である。コンピュータ・プログラムは、ファイル・システム中のファイルに対応する必要はない。プログラムは、他のプログラム又はデータ（例えば、マークアップ言語文書中に保存された１又は２以上のスクリプト）を保持するファイルの一部の中に、当のプログラム専用の単一ファイル中、又は複数の調整ファイル中（例えば、１又は２以上のモジュール、サブプログラム、又はコードの一部を保存するファイル）に保存できる。コンピュータ・プログラムは、１つのコンピュータ上、若しくは１つのサイトに配置するか、又は複数サイトにまたがって分配し、かつ通信ネットワークによって相互接続した複数のコンピュータ上で実行するように展開できる。
【００５７】
本明細書中に記載の処理及び論理フローは、インプット・データに対する動作と出力の生成とによって、機能を実行するための１又は２以上のコンピュータ・プログラムを実行する１又は２以上のプログラム可能なプロセッサによって実行できる。前記処理及び論理フローはまた、特定目的の論理回路、例えばＦＰＧＡ（field programmable gate array）又はＡＳＩＣ（application-specific integrated circuit）によって実行できるとともに、装置はまた、前記特定目的の論理回路として実装できる。
【００５８】
コンピュータ・プログラムの実行に適したプロセッサは、例として、汎用目的と特定目的の両方のマイクロプロセッサ、及び任意の種類のデジタル・コンピュータのいずれか１又は２以上のプロセッサを含む。一般に、プロセッサは、読取専用メモリ又はランダム・アクセス・メモリ、又はその両方から、命令及びデータを受け取る。コンピュータの必須要素は、命令を実行するためのプロセッサと、命令及びデータを保存するための１又は２以上のメモリ装置とである。一般に、コンピュータはまた、例えば、磁気、光磁気ディスク、又は光ディスクといったデータを保存するための１又は２以上の大容量記録装置を具備しているか、又は前記１又は２以上の大容量記録装置からデータを受信するために、又は前記１又は２以上の大容量記録装置にデータを送信するために、又はその両方のために、効果的に連結している。しかしながら、コンピュータは、そのような装置を具備していなくてもよい。その上、コンピュータは、例えば、少数の例を挙げると、携帯電話、携帯情報端末（PDA）、携帯オーディオ又はビデオ・プレイヤ、デジタル写真フレーム、ゲーム機、全地球測位システム（GPS）受信機といった他の装置内に内蔵できる。
【００５９】
コンピュータ・プログラム命令及びデータを保存するためのコンピュータ可読媒体は、例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、及びフラッシュ・メモリ装置；磁気ディスク（例えば、内蔵ハード・ディスク、又はリムーバブル・ディスク；磁気光ディスク；かつＣＤ−ＲＯＭ及びＤＶＤ−ＲＯＭディスク）といった半導体メモリ装置を含め、不揮発性メモリ、媒体、及びメモリ装置の全ての形式を含む。前記プロセッサ及び前記メモリは、特定目的の論理回路によって補足されうるか、又は前記特定目的の論理回路中に組み入れることができる。
【００６０】
ユーザとの対話を提供するために、本明細書中に記載の要旨の実施形態は、前記ユーザに情報を表示するための、例えば、ＣＲＴ（cathode ray tube）又はＬＣＤ（liquid crystal display）モニタといったディスプレイ装置と、前記ユーザを前記コンピュータに入力可能にするキーボード及びポインティング・デバイス（例えば、マウス又はトラックボール）とを有するコンピュータ上で実行できる。他の種類の装置が、同様に前記ユーザとの対話を提供するために使用可能である。例えば、前記ユーザに提供するフィードバックは、例えば、視覚的フィードバック、聴覚的フィードバック、又は触覚的フィードバックといった任意の形式の感覚的フィードバックでもよく、かつ前記ユーザからの入力は、音響入力、音声入力、又は触覚入力を含む任意の形式で受信できる。
【００６１】
本明細書中に記載の要旨の実施形態は、例えば、データ・サーバといったバックエンド構成要素を有するか、例えば、アプリケーション・サーバといったミドルウェア構成要素を有するか、又は例えば、ユーザが本明細書中に記載の要旨の実施形態と対話可能なグラフィカル・ユーザ・インターフェース又はウェブ・ブラウザを具備するクライアント・コンピュータといったフロントエンド構成要素か、又は１又は２以上のそのようなバックエンド、ミドルウェア、又はフロントエンド構成要素の任意の組み合わせを有するコンピュータ・システム内で実行できる。前記システムの前記構成要素は、例えば、通信ネットワークといったデジタル・データ通信の任意の形式又は媒体によって、相互接続可能である。通信ネットワークの例は、ローカル・エリア・ネットワーク（ＬＡＮ）と、例えば、インターネットといったワイド・エリア・ネットワーク（ＷＡＮ）とを含む。
【００６２】
前記コンピュータ・システムは、クライアントとサーバを含んでもよい。クライアントとサーバとは、一般的に互いに遠隔にあり、かつ典型的には、通信ネットワークを介して相互交信している。クライアントとサーバとの関係は、各コンピュータ上で処理するとともに、互いにクライアント−サーバ関係を有するコンピュータ・プログラムの効力によって生じている。
【００６３】
本明細書は、多くの特別の実施形態の詳細を含む一方で、これらは、任意の発明、又は請求可能な範囲の限定として解釈すべきではなく、むしろ特定の発明の特定の実施形態に特有の特徴の記載として解釈すべきである。また、個々の実施形態の文脈中で、本明細書中に記載されたある特徴は、単一の実施形態内で組み合わせて実行することができる。反対に、単一の実施形態の文脈中に記載の種々の特徴は、複数の実施形態で個々に、又は任意の適切な副組み合わせ（subcombination）の中で、実行できる。その上、特徴は、一定の組み合わせの中の動作として上述され、かつそのように最初から請求されてさえいるかもしれないが、請求した組み合わせの中の１又は２以上の特徴は、場合によっては、前記組み合わせから削除できるとともに、前記請求した組み合わせは、副組み合わせ又は種々の副組み合わせに向けることができる。
【００６４】
同じように、動作を特定順序で図面中に図示している一方で、このことは、所望の結果を達成するために、そのような動作を、図示した前記特定順序で、又は順番通りの順序で実行すること、又は図示した動作の全てを実行することを要求しているとして理解すべきではない。ある状況では、マルチタスク及び並列処理は、都合がよい場合がある。その上、上述の実施形態中の種々のシステム構成要素の分離は、全ての実施形態中でそのような分離を要求しているとして理解すべきではなく、かつ前記記載のプログラム構成要素及びシステムは、一般的に単一のソフトウェア製品に一体化できるか、又は複数のソフトウェア製品にパッケージ化できる。
【００６５】
本明細書中に記載の要旨の特定の実施形態を説明した。他の実施形態は、以降の請求項の範囲内である。例えば、前記請求項中に列挙した動作は、異なる順序で実行してもよく、かつそれでも所望の結果を達成できる。一例として、添付の図面中に図示した処理は、所望の結果を達成するために、必ずしも図示した特定の順序、又は順番通りの順序を要求していない。ある実施形態では、マルチタスク及び並列処理が、都合がよい場合がある。
【符号の説明】
【００６６】
１１２  第一クライアント
１１４  第二クライアント
１２０  サーバ
１２２  対象プロファイル
１２４  カスタム言語モデル
１２６  学習用データ
【図１】
0005475795.tif 000009
【図２】
0005475795.tif 000010
【図３】
0005475795.tif 000011
【図４】
0005475795.tif 000012
【図５】
0005475795.tif 000013
【図６】
0005475795.tif 000014
【図９Ａ】
0005475795.tif 000015
【図９Ｂ】
0005475795.tif 000016
【図７】
0005475795.tif 000017
【図８】
0005475795.tif 000018