(57)【要約】【課題】通信内の文の分類に基づいて通信の優先順位を決定するための方法およびシステムを提供する。【解決手段】文分類システムは、「文モード」などの様々な分類に従って通信の文を分類することができる。この文分類システムは、トレーニングデータを使用して文分類子をトレーニングし、次いでそのトレーニングされた文分類子を使用して文を分類する。通信の文が分類されると、ドキュメントランキングシステムは、その通信内の文の分類に基づいて、その通信用のランク付けを作成することができる。このドキュメントランキングシステムは、トレーニングデータを使用してドキュメントランク分類子をトレーニングし、次いでそのトレーニングされたドキュメントランク分類子を使用して通信のランク付けを計算する。【選択図】図１
2006107464.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータシステム内で文を分類する方法であって、
トレーニング文およびその分類を提供することと、
前記文の特徴の表示を作成することと、
前記作成された特徴の表示およびそれらが表示する前記文の前記分類に基づいて文を分類するために文分類子をトレーニングすることと、
文を受け取ることと、
前記文の特徴の表示を作成することと、
前記文を分類するために前記トレーニングされた文分類子を前記作成された前記文の特徴の表示に適用することと
を含むことを特徴とする方法。
【請求項２】
前記文の分類は、平叙文、命令文、疑問文、および感嘆文を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記文の分類は、感謝文および添付文を含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記特徴の表示は、キーワードに基づく特徴を含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記特徴の表示は、語彙特徴を含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記特徴の表示は、パターン特徴を含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記パターン特徴は、文の一般化された文がトレーニングデータ内の文の一般化された文のパターンになるためのサポートに基づくことを特徴とする請求項６に記載の方法。
【請求項８】
サポートは、
ｓｕｐ（ｐ）＝｜｛ｓ｜ｓ∈Ｓ∧ｐ⊆ｓ｝｜として定義され、
ここでのｓｕｐ（ｐ）は、一般化された文ｐが、一般化された文のパターンになるための前記サポートを表し、ｓは、文Ｓの前記セット内の一般化された文であることを特徴とする請求項７に記載の方法。
【請求項９】
前記サポートは、トレーニングデータ内の文の他の一般化された文の下位集合である一般化された文に基づくことを特徴とする請求項７に記載の方法。
【請求項１０】
前記サポートは、頻出アイテムセットマイニング技術を使用して識別されることを特徴とする請求項７に記載の方法。
【請求項１１】
前記トレーニングすることは、Ａｄａ−ｂｏｏｓｔｉｎｇアルゴリズムを適用することを含むことを特徴とする請求項１に記載の方法。
【請求項１２】
前記トレーニングすることは、サポートベクトルマシンアルゴリズムを適用することを含むことを特徴とする請求項１に記載の方法。
【請求項１３】
前記受け取ること、作成すること、および適用することは、電子メールメッセージのそれぞれの文ごとに実行されることを特徴とする請求項１に記載の方法。
【請求項１４】
特徴の表示は、キーワード特徴、語彙特徴、およびパターン特徴を含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
前記パターン特徴は、文がトレーニングデータ内の文の一般化された文のパターンになるための類似性に基づくことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記トレーニングすることは、サポートベクトルマシンアルゴリズムを適用することを含むことを特徴とする請求項１４に記載の方法。
【請求項１７】
前記受け取ること、作成すること、および適用することは、前記電子メールメッセージのそれぞれの文ごとに実行されることを特徴とする請求項１４に記載の方法。
【請求項１８】
文を有するドキュメントのトレーニングセットを提供することであって、それぞれのドキュメントはランクを有することと、
前記トレーニングセット内の前記ドキュメントの前記文を分類することと、
前記ドキュメント内の前記文の分類および前記ドキュメントの前記ランクに基づいてドキュメントを分類するためにドキュメント分類子をトレーニングすることと
を含むことを特徴とする請求項１に記載の方法。
【請求項１９】
ドキュメントを受け取ることと、
前記トレーニングされた文分類子を使用して、前記ドキュメントの前記文を分類することと、
前記ドキュメントをランク付けするために前記トレーニングされたドキュメント分類子を前記文の前記分類に適用することと
を含むことを特徴とする請求項１８に記載の方法。
【請求項２０】
文を文の分類へと分類するために文分類子を提供することと、
前記文分類子およびそれぞれのドキュメントのランクによって決定されるように、その文の前記分類によってトレーニングデータのそれぞれのドキュメントを表すことによって、ドキュメントランク分類子をトレーニングすることと、
前記文分類子によって決定されるように、その文の前記分類によってドキュメントを表すことと、
前記ドキュメントの前記ランクを決定するために前記トレーニングされたドキュメントランク分類子を前記ドキュメントの前記表示に適用することと
を含む方法によって、コンピュータシステムを制御してドキュメントをランク付けするための命令を含むことを特徴とするコンピュータ可読媒体。
【請求項２１】
前記ドキュメントは電子メールメッセージであり、それらのランクに基づいて電子メールメッセージの優先順位を決定することを含むことを特徴とする請求項２０に記載のコンピュータ可読媒体。
【請求項２２】
前記文は、文モードに基づいて分類されることを特徴とする請求項２０に記載のコンピュータ可読媒体。
【請求項２３】
前記文の分類は、平叙文、命令文、疑問文、および感嘆文を含むことを特徴とする請求項２０に記載のコンピュータ可読媒体。
【請求項２４】
前記文の分類は、感謝文および添付文を含むことを特徴とする請求項２０に記載のコンピュータ可読媒体。
【請求項２５】
前記トレーニングすることは、Ａｄａ−ｂｏｏｓｔｉｎｇアルゴリズムを適用することを含むことを特徴とする請求項２０に記載のコンピュータ可読媒体。
【請求項２６】
前記トレーニングすることは、サポートベクトルマシンアルゴリズムを適用することを含むことを特徴とする請求項２０に記載のコンピュータ可読媒体。
【請求項２７】
前記文分類子を提供する前記ことは、
トレーニング文およびその分類を提供することと、
前記文の特徴の表示を作成することと、
前記作成された特徴の表示およびそれらが表示する前記文の前記分類に基づいて文を分類するために文分類子をトレーニングすることと、
文を受け取ることと、
前記文の特徴の表示を作成することと、
前記文を分類するために前記トレーニングされた文分類子を前記作成された前記文の特徴の表示に適用することと
を含むことを特徴とする請求項２０に記載のコンピュータ可読媒体。
【請求項２８】
ドキュメントをランク付けするためのコンピュータシステムであって、
文分類子と、
前記文分類子を使用して作成されたドキュメントの文の分類に基づいて、およびドキュメントのランクに基づいてトレーニングされたドキュメントランク分類子と、
前記文分類子を使用してドキュメントの文を分類し、前記ドキュメントランク分類子を前記分類された文に適用して、前記ドキュメント用のランク付けを作成するための手段と
を含むことを特徴とするコンピュータシステム。
【請求項２９】
前記ドキュメントは電子メールメッセージであることを特徴とする請求項２８に記載のコンピュータシステム。
【請求項３０】
前記文は、文モードに基づいて分類されることを特徴とする請求項２８に記載のコンピュータシステム。
【請求項３１】
前記文の分類は、平叙文、命令文、疑問文、および感嘆文を含むことを特徴とする請求項２８に記載のコンピュータシステム。
【請求項３２】
前記文の分類は、感謝文および添付文を含むことを特徴とする請求項３１に記載のコンピュータシステム。
【請求項３３】
前記分類子は、Ａｄａ−ｂｏｏｓｔｉｎｇアルゴリズムを使用してトレーニングされることを特徴とする請求項２８に記載のコンピュータシステム。
【請求項３４】
前記分類子は、サポートベクトルマシンアルゴリズムを使用してトレーニングされることを特徴とする請求項２８に記載のコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
開示する技術は、電子メールメッセージなどの通信の優先順位を決定することに関する。
【背景技術】
【０００２】
人によっては、何百もの電子通信を毎日受信することもある。電子通信は、電子メールメッセージ、音声メールメッセージ、メモ、ドキュメントなどを含むことができる。個人が受信できる通信、特に電子メールメッセージの数が多いため、ユーザが自分のすべての通信にアクセスして処理するには、非常に時間がかかる場合がある。実際に電子メールメッセージの数が多いため、ユーザにとっては、迅速な配慮を必要とする可能性のある重要な電子メールメッセージを、より重要度の低いすべての電子メールメッセージから識別することが困難な場合がある。メッセージを探し出す上で役立つように、電子メールシステムによっては、電子メールメッセージが表示される順序を個人が指定できるものもある。例えば個人は、配信時刻、送信者、件名などに基づいて電子メールメッセージを順序付けるように指定することができる。
【０００３】
しかし電子メールメッセージおよび他の通信を順序付けるためのこれらの技術は、通信の重要度に対する多くの有用な洞察を提供するものではない。例えばある従業員が、迅速な配慮を必要とする電子メールメッセージをできるだけ早く見たい場合、その従業員は、すべての電子メールメッセージを見ることができずに、送信者による電子メールメッセージに対する重要度の指定に基づく順序付けに依存する必要が生じることがある。しかしこのような重要度は、送信者にとっての重要度を反映したものであり、必ずしも受信者にとっての重要度を反映したものではない。さらに重要度は、迅速な配慮が必要かどうかを反映していない。
【０００４】
【非特許文献１】G. Heidorn, "Intelligent Writing Assistance," Handbook of Natural Language Processing, edited by R. Dale, H. Moisl, and H. Somers (M. Dekker, New York, 1999)
【非特許文献２】M. Zaki and C. Hsiao, "CHARM: An Efficient Algorithm for Closed Itemset Mining" (SDM, 2002)
【非特許文献３】Sequential Minimal Optimization, at http://research.microsoft.com/-jplatt/smo.html
【発明の開示】
【発明が解決しようとする課題】
【０００５】
自動的に通信の優先順位を決定することができ、これによって個人が、より重要度が低いまたは迅速な配慮を必要としない通信に注意を集中させる前に、重要なまたは迅速な配慮を必要とする通信に注意を集中させることができる技術を提供することが望ましいであろう。
【課題を解決するための手段】
【０００６】
通信内の文の分類に基づいて通信の優先順位を決定するための方法およびシステムを提供する。文分類システムは、「文モード」などの様々な分類に従って通信の文を分類することができる。この文分類システムは、文の特徴および対応する分類を提供するトレーニングデータを使用して、文分類子をトレーニングする。次いでこのシステムは、文の特徴を提供し、それと引き換えに分類を受け取ることによって、トレーニングされた文分類子を使用して文を分類する。通信の文が分類されると、ドキュメントランキングシステムは、その通信内の文の分類に基づいて、その通信用のランク付けを作成することができる。このドキュメントランキングシステムは、通信の文の分類および通信のランク付けを提供するトレーニングデータを使用して、ドキュメントランク分類子をトレーニングする。次いでこのシステムは、文の分類を提供して、それと引き換えにランク付けを受け取ることによって、トレーニングされたドキュメントランク分類子を使用して通信のランク付けを計算する。
【発明を実施するための最良の形態】
【０００７】
通信内の文の分類に基づいて通信の優先順位を決定するための方法およびシステムを提供する。一実施形態では、優先順位決定システムは、文分類システムおよびドキュメントランキングシステムを含む。文分類システムは、「文モード」などの様々な分類に従って通信の文を分類することができる。文モードとは、文が平叙文、疑問文、命令文、感謝文、および感嘆文などであるかどうかを指す。通信の文が分類されると、ドキュメントランキングシステムは、通信内の文の分類に基づいて通信のランキング（すなわち優先順位付け）を作成する。例えば通信ランキングシステムは、多くの命令文を有する通信に、平叙文のみを有する通信よりも高いランクを付けることができる。優先順位決定システムを使用して、電子メールメッセージの優先順位を決定することができる。このようにして、電子メールメッセージの受信者は、優先順位の低い通信に注意を集中させる前に、優先順位またはランキングの高い通信に注意を集中させることができる。以降では、電子メールメッセージの優先順位を決定する優先順位決定システムの実施形態について開示する。この優先順位決定システムを使用して、任意のタイプの通信または他のドキュメントの優先順位を決定することができる。さらに、この説明で使用される「文」という用語は、完全な文、文の断片、または単語の任意の集合を指す。
【０００８】
一実施形態では、文分類システムは、電子メールメッセージおよびそのメッセージ内のそれぞれの文の分類を含むトレーニングデータに基づいて、文分類子をトレーニングする。例えばトレーニングデータは、「Ｗｅ  ａｒｅ  ｇｏｉｎｇ  ｔｏ  Ｓｏｕｔｈ  Ｄａｋｏｔａ  ｏｎ  Ｆｒｉｄａｙ」という文を有するメッセージを含むことができ、これは平叙文として分類される。文分類システムは、キーワード特徴、語彙特徴、およびパターン特徴を含む文特徴の文特徴ベクトルによって、それぞれの文を表すことができる。したがって１つの文は、（ｋ、ｌ、ｐ）の３タプル(3-tuple)によって表すことができ、ｋはキーワード特徴を表し、ｌは語彙特徴を表し、ｐはパターン特徴を表す。１つのドキュメント用の文特徴を作成する前に、文分類システムは、単語を正規化すること、停止語(stop word)を除去すること、単語を抑制することなどによって、そのドキュメントの単語をトークン化することができる。
【０００９】
キーワード特徴は、１つのドキュメント内の１つの文のキーワードの重み付けを表すことができる。一実施形態では、逆ドキュメント頻度測定基準(inverted document frequency metric)（例えばＴＦ＊ＩＤＦ）による用語頻度を使用して、重み付けが計算される。文分類システムは、はじめにトレーニングデータ内のそれぞれのキーワードのドキュメント頻度を計算することができる。１つのキーワード用のドキュメント頻度とは、そのキーワードを含むドキュメントの総数を表す。次いで文分類システムは、１つのドキュメント用のそれぞれのキーワードの重み付けを、そのドキュメント内のそのキーワードの用語頻度および逆ドキュメント頻度に基づいて計算することができる。１つの文用のキーワード特徴ベクトルは、その文におけるキーワードの重み付けを含む。
【００１０】
語彙特徴は、１つの文の品詞、語句、および名前付きのエンティティ(named entity)を表すことができる。文分類システムは、それぞれの単語（例えば非停止語(non-stop word)）の品詞を識別し、１つの文の品詞を、その文における単語の品詞のベクトルとして表すことができる。前述の例に関して続けると、この文の単語の品詞は、「ｗｅ」が代名詞、「ａｒｅ」が助動詞、「ｇｏｉｎｇ」が分詞、「ｔｏ」が前置詞、といった具合である。語句は、文の単語のシーケンスであり、構文単位(syntactic unit)を表す。前述の例に関して続けると、この文は「Ｓｏｕｔｈ  Ｄａｋｏｔａ」という語句を含む。名前付きのエンティティは、名前を有するエンティティ（例えば人物、都市、および企業）を指す。前述の例に関して続けると、「Ｓｏｕｔｈ  Ｄａｋｏｔａ」という語句は、名前付きのエンティティであり、州を表している。１つの文用の語彙特徴ベクトルは、品詞のベクトル、語句用のベクトル、および文の名前付きのエンティティ用のベクトルを含む。
【００１１】
１つの文のパターン特徴は、その文の一般化に最も類似している一般化された文のパターンである。前述の例に関して続けると、この文の一般化は、「ｐｅｒｓｏｎ  ａｃｔｉｏｎ  ｏｂｊｅｃｔ  ｔｉｍｅ」とすることができ、これは、「ｔｈｉｎｇ  ａｃｔｉｏｎ」という一般化された文のパターンに最も類似していると言うことができる。この文用のパターン特徴ベクトルは、この一般化された文のパターンである。
【００１２】
一実施形態では、文分類システムは、トレーニングデータのそれぞれの文をその文特徴ベクトルによって表し、文モードに基づいてその文特徴ベクトルによって表された文を分類するための文分類子をトレーニングする。この文分類子は、Ａｄａ−ｂｏｏｓｔｉｎｇ分類子、サポートベクトルマシン、または他の何らかの分類子とすることができる。文分類システムは、文分類子のトレーニング用のトレーニングデータの文特徴ベクトルおよび文モードのペアを提供する。
【００１３】
文分類子がトレーニングされると、文分類システムは、その文分類子を使用して、ドキュメントの文を分類する。ドキュメントの文を分類するために、文分類システムは、前述のようにドキュメントのそれぞれの文用の文特徴ベクトルを作成する。次いで文分類システムは、それぞれの文用の文特徴ベクトルを文分類子に提示する。文分類子は、そのトレーニングに基づいてドキュメントのそれぞれの文の文モードを識別する。
【００１４】
ドキュメントランキングシステムは、それぞれのドキュメントのランキングを伴った文を有するドキュメントを含むトレーニングデータに基づいてドキュメントランク分類子をトレーニングすることができる。ドキュメントランク分類子をトレーニングするために、ドキュメントランキングシステムは、ドキュメントのそれぞれの文の分類を含むドキュメント特徴ベクトルによってドキュメントを表す。例えば「ｗｅ  ａｒｅ  ｇｏｉｎｇ  ｔｏ  Ｓｏｕｔｈ  Ｄａｋｏｔａ  ｔｈｉｓ  Ｆｒｉｄａｙ」および「ｗｈａｔ  ｓｈｏｕｌｄ  ｗｅ  ｂｒｉｎｇ」という文を有するドキュメントは、（平叙文、疑問文）というドキュメント特徴ベクトルによって表すことができる。ドキュメントランキングシステムは、文分類システムを使用して、文を分類する。ドキュメントランキングシステムは、トレーニングデータのドキュメント用のドキュメント特徴ベクトルおよびランキングのペアに基づいてドキュメントランク分類子をトレーニングする。ドキュメントランク分類子は、Ａｄａ−ｂｏｏｓｔｉｎｇ分類子、サポートベクトルマシン、または他の何らかの分類子とすることができる。ドキュメントランク分類子がトレーニングされると、ドキュメントランキングシステムは、ドキュメントをランク付けする用意が整ったことになる。ドキュメントランキングシステムは、文分類システムを使用してドキュメント用のドキュメント特徴ベクトルを作成することによって、ドキュメントをランク付けする。次いでドキュメントランキングシステムは、ドキュメントのドキュメント特徴ベクトルをドキュメントランク分類子に提示し、ドキュメントランク分類子は、そのドキュメント用のランキングを計算する。
【００１５】
図１は、一実施形態における文分類システムのコンポーネントを示すブロック図である。文分類システム１００は、文分類子作成コンポーネント１０１およびドキュメントの文分類コンポーネント１１１を含む。文分類システムはまた、ドキュメント用キーワード特徴ベクトル作成コンポーネント１０２、ドキュメント用語彙特徴ベクトル作成コンポーネント１０３、ドキュメント用パターン特徴ベクトル作成コンポーネント１０４、および文分類子トレーニングコンポーネント１０５を含む。これらのコンポーネントはまた、文用キーワード特徴ベクトル作成コンポーネント１０６、文用語彙特徴ベクトル作成コンポーネント１０７、および文用パターン特徴ベクトル作成コンポーネント１０８を呼び出す。文分類子作成コンポーネントは、トレーニングデータ１０９を使用して、文分類子をトレーニングする。トレーニングデータは、各メッセージのそれぞれの文の文モードを伴った電子メールメッセージを含む。文分類子作成コンポーネントは、ドキュメント用キーワード特徴ベクトル作成コンポーネント、ドキュメント用語彙特徴ベクトル作成コンポーネント、およびドキュメント用パターン特徴ベクトル作成コンポーネントを使用して、トレーニングデータのそれぞれの文用の文特徴ベクトルを作成する。ドキュメント用キーワード特徴ベクトル作成コンポーネントは、それぞれのドキュメント用の文用キーワード特徴ベクトル作成コンポーネントを呼び出すことによって、ドキュメントの文用のキーワード特徴ベクトルを作成する。ドキュメント用語彙特徴ベクトル作成コンポーネントは、それぞれのドキュメント用の文用語彙特徴ベクトル作成コンポーネントを呼び出すことによって、ドキュメントの文用の語彙特徴ベクトルを作成する。ドキュメント用パターン特徴ベクトル作成コンポーネントは、それぞれのドキュメント用の文用パターン特徴ベクトル作成コンポーネントを呼び出すことによって、ドキュメントの文用のパターン特徴ベクトルを作成する。ドキュメントの文分類コンポーネントは、文用キーワード特徴ベクトル作成コンポーネント、文用語彙特徴ベクトル作成コンポーネント、および文用パターン特徴ベクトル作成コンポーネントを呼び出すことによって、ドキュメントのそれぞれの文用の文特徴ベクトルを作成する。次いでドキュメントの文分類コンポーネントは、それぞれの文用の文特徴ベクトルを、トレーニングされた文分類子に提示して、文を分類する。
【００１６】
図２は、一実施形態におけるドキュメントランキングシステムのコンポーネントを示すブロック図である。ドキュメントランキングシステム２００は、ドキュメントランク分類子作成コンポーネント２０１およびドキュメントランク付けコンポーネント２１１を含む。ドキュメントランク分類子作成コンポーネントは、トレーニングデータ２０４のそれぞれのドキュメント用に、そのドキュメントの文の文分類を含むドキュメント特徴ベクトルを作成することによって、ドキュメントランク分類子を作成する。ドキュメントランク分類子作成コンポーネントは、ドキュメントの文分類コンポーネント２０２を呼び出して、トレーニングデータのそれぞれのドキュメント用のドキュメント特徴ベクトルを作成する。ドキュメントランク分類子作成コンポーネントは、ドキュメントランク分類子トレーニングコンポーネント２０３を呼び出して、それぞれのドキュメント用のドキュメント特徴ベクトルおよびランキングのペアを渡すことによって、ドキュメントランク分類子をトレーニングする。ドキュメントランク付けコンポーネントは、ドキュメントの文分類コンポーネントを呼び出して、ランク付けされるドキュメント用のドキュメント特徴ベクトルを作成する。次いでドキュメントランク付けコンポーネントは、そのドキュメント特徴ベクトルを、トレーニングされたドキュメントランク分類子に提示して、そのドキュメント用のランキングを作成する。
【００１７】
この優先順位決定システムを実施するコンピューティングデバイスは、中央処理装置、メモリ、入力デバイス（例えばキーボードおよびポインティングデバイス）、出力デバイス（例えばディスプレイデバイス）、ならびにストレージデバイス（例えばディスクドライブ）を含むことができる。メモリおよびストレージデバイスは、この優先順位決定システムを実施する命令を含むことができるコンピュータ可読媒体である。さらに通信リンク上の信号などのデータ伝送メディアを介して、データ構造およびメッセージ構造を保存または伝送することができる。インターネット、ローカルエリアネットワーク、ワイドエリアネットワーク、ポイントツーポイントのダイヤルアップ接続など、様々な通信リンクを使用することができる。
【００１８】
この優先順位決定システムは、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドデバイスまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、プログラム可能な家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記のシステムまたはデバイスのいずれかを含む分散コンピューティング環境などを含む様々な動作環境内で実施することができる。
【００１９】
この優先順位決定システムについては、１つまたは複数のコンピュータまたは他のデバイスによって実行される、プログラムモジュールなどのコンピュータ実行可能命令という一般的なコンテキストにおいて説明することができる。一般にプログラムモジュールは、特定のタスクを実行したり特定の抽象データ型を実施したりするルーチン、プログラム、オブジェクト、コンポーネント、およびデータ構造などを含む。通常、プログラムモジュールの機能は、様々な実施形態において希望に応じて結合または分散することができる。
【００２０】
この優先順位決定システムは、文モードに基づいて文を分類することができる。文モードについて、次の例によって説明する。平叙文モードは、叙述を行う文に相当する。次の文は、平叙文モードを有する文の例である。 
It's lunchtime.
We are going to South Dakota on Friday.
My car is out of gasoline.
My parents keep telling me that I should make good grades so that I can get a job or go to college.
【００２１】
疑問文モードは、質問を行う文に相当する。次の文は、疑問文モードを有する文の例である。
What time does the movie start?
How many people from your graduating class went to college?
Is there a reason why those dirty clothes are in the middle of the floor?
What are they serving in the cafeteria today?
【００２２】
命令文モードは、命令を行う文に相当する。次の文は、命令文モードを有する文の例である。
Could you please answer these questions?
Wash the car.
Please donate to the community charity fund.
I think we can have a discussion on it.
How about a meeting this Friday?
【００２３】
感嘆文モードは、感嘆を表す文に相当する。次の文は、感嘆文モードを有する文の例である。
What a beautiful night!
How happy we were when the dawn came!
What did you do to your hair!
I just won $500!
【００２４】
感謝文モードは、感謝を表す文に相当する。次の文は、感謝文モードを有する文の例である。
Thank you for the information.
It's been great meeting you all today.
We appreciate your help.
【００２５】
添付文モードは連絡文に相当し、通常は電子メールメッセージであり、これによって書き手は、この連絡文にドキュメントを添付する意図を表明する。添付文モードは、平叙文や命令文などの別の文モードにさらに分類することができる。添付文モードは、連絡の中に重大な意味を有することがあり、このような連絡のランク付けに対して特に関連性が高い場合がある。次の文は、添付文モードを有する文の例である。 
Attached is the file that needs to be reviewed.
This is the draft I received from Bill.
Please review the attached spreadsheet.
Have you reviewed the attached spreadsheet?
【００２６】
多くの異なる文分類および文モードを定義できることを当業者なら理解するであろう。例えば文分類は、個人に関連付けられたドメインに基づいて定義することができる。このような場合、病院は、予約の依頼、予約のキャンセル、予約の確認、再調剤の依頼、健診記録の要求などとして、文をさらに分類することができる。病院は、メッセージ内の文の分類に基づいて電子メール通信の優先順位を決定することができる。
【００２７】
文のパターン特徴ベクトルは、一実施形態では、一般化された文のパターンである。文分類システムは、一般化された文のパターン（「ＧＳＰ」）システムを使用して、一般化された文のパターンを識別することができる。ＧＳＰシステムは、トレーニングデータ内のそれぞれの文の「一般化された文」の形式を作成する。一般化された文とは、文の単語（例えば名詞）を抽象化または一般化したものである。例えば、ある電子メールメッセージの文を「Ｔａｌｋ  ｂｙ  Ｊｏｈｎ  Ｓｍｉｔｈ  ｏｎ  Ｍａｙ  １０，２００３」とすることができる。「Ｊｏｈｎ  Ｓｍｉｔｈ」から名詞「ｐｅｒｓｏｎ」を一般化することができ、「Ｍａｙ  １０，２００３」から名詞「ｄａｔｅ」を一般化することができ、名詞「ｔａｌｋ」は一般化することができず、停止語「ｂｙ」および「ｏｒ」は除去することができる。この例では、対応する一般化された文は「ｔａｌｋ  ｐｅｒｓｏｎ  ｄａｔｅ」となる。
【００２８】
ＧＳＰシステムは、一般化された文のセット内に現れる「一般化された文のパターン」を識別する。１つの一般化された文は、別の一般化された文の下位集合となる場合があり、上位集合の一般化された文は、下位集合の一般化された文のすべての単語を含む。例えば一般化された文「ｔａｌｋ  ｐｅｒｓｏｎ」は、一般化された文「ｔａｌｋ  ｐｅｒｓｏｎ  ｄａｔｅ」の下位集合である。ＧＳＰシステムは、他の一般化された文の下位集合として頻繁に現れる一般化された文を、一般化された文のパターンとして選択する。例えばＧＳＰシステムは、頻出アイテムセットアルゴリズム(frequent itemset algorithm)を使用して、一般化された文から一般化された文のパターンを識別することができる。
【００２９】
しかし実際には、一般化された文のパターンが多数重複して存在する場合があり、あるいは一般化された文のパターンの多くが、詳細すぎるレベルでパターン特徴を定義している場合もある。このような場合、ＧＳＰシステムは、重複を取り除き、より概略的なレベルで類似している一般化された文のパターンをまとめて、類似している一般化された文のパターンのグループを示そうと試みることができる。例えば一般化された文のパターン「ｔａｌｋ  ｐｅｒｓｏｎ  ｄａｔｅ」が、一般化された文のパターン「ｐｒｅｓｅｎｔａｔｉｏｎ  ｐｅｒｓｏｎ  ｄａｔｅ」と重複している場合があるため、ＧＳＰシステムは、これらを結合して、より概略的な一般化された文のパターンとすることができる。また、一般化された文のパターン「ｔａｌｋ  ｄａｔｅ」および「ｔａｌｋ  ｐｅｒｓｏｎ」が、詳細すぎるレベルに相当する場合もある。結果として、ＧＳＰシステムは、これらを結合して、より一般化された文のパターンとすることができる。
【００３０】
一実施形態では、文分類システムは、語彙特徴ベクトルおよびパターン特徴ベクトルの作成を補助するために自然言語プロセッサを使用する。自然言語プロセッサは、文を入力として受け取り、その文用の構文木(syntax tree)を構築する。文「Ｗｅｌｃｏｍｅ  Ｊｏｈｎ  Ｓｍｉｔｈ」用の構文木の一例は、「ｗｅｌｃｏｍｅ」が動詞で、「Ｊｏｈｎ  Ｓｍｉｔｈ」が名詞であることを示す。次いで自然言語プロセッサは、ｐｅｒｓｏｎ、ｄａｔｅ、およびｐｌａｃｅなど、名詞や名詞句用の品詞の一般化を作成する。例えば自然言語プロセッサは、名詞「Ｊｏｈｎ  Ｓｍｉｔｈ」を「ｐｅｒｓｏｎ」に一般化することができる。結果として生じる一般化された文は、「ｗｅｌｃｏｍｅ  ｐｅｒｓｏｎ」となる。この一般化は、名詞の語義的意味(semantic meaning)を取り込む。自然言語プロセッサは、統計的言語モデルを使用して、一般化を識別することができる。適切な自然言語プロセッサの１つがＮＬＰＷｉｎであり、これについては、非特許文献１に記載されている。
【００３１】
一般化された文のパターンとは、一般化された文の中でパターンを示すのに十分な「サポート」を有する一般化された文と定義することができる。一実施形態では、一般化された文が、一般化された文のパターンになるためのサポートは、一般化された文の上位集合である（または一般化された文を含む）一般化された文の数を示す。例えば一般化された文「ｗｅｌｃｏｍｅ  ｐｅｒｓｏｎ  ｄａｔｅ」は、一般化された文「ｗｅｌｃｏｍｅ  ｐｅｒｓｏｎ」を含むため、「ｗｅｌｃｏｍｅ  ｐｅｒｓｏｎ」を一般化された文のパターンとしてサポートする。サポートは、次のように、より正式に定義することができる。
ｓｕｐ（ｐ）＝｜｛ｓ｜ｓ∈Ｓ∧ｐ⊆ｓ｝｜                        （１）
ここでのｓｕｐ（ｐ）は、一般化された文ｐが、一般化された文のパターンになるためのサポートを表し、ｓは、文Ｓのセット内の一般化された文である。この定義によれば、一般化された文のサポートは、その一般化された文を含む一般化された文の総数である。一般化された文のパターンは、次の場合に定義することができる。 
ｓｕｐ（ｐ）＞＝ｍｉｎ＿ｓｕｐ                                  （２）
ここでのｍｉｎ＿ｓｕｐは、一般化された文が、一般化された文のパターンとみなされるために必要な最小限のサポートである。
【００３２】
それぞれの一般化された文用のサポートを計算すると、複雑な計算になる可能性があるため、むしろＧＳＰシステムは、頻出アイテムセットマイニング技術(frequent itemset mining technique)を一般化された文に直接適用して、一般化された文のセット内の一般化された文のパターンを識別することができる。しかし頻出アイテムセットは、多くの重複する情報を含む場合がある。例えばアイテムセットｐが、その上位集合ｑの１つと同じサポートを有し、その双方が頻出する場合、ｐは、その上位集合ｑ以上の情報を提供しないため、重複している。一般化された文のパターンの重複を除去するために、ＧＳＰシステムは、頻出する「クローズド」(closed)アイテムセットを識別するためのマイニング技術を使用する。アイテムセットがクローズドであるとは、その上位集合のアイテムセットのすべてが、そのアイテムセット自体よりも頻度が低い場合を指す。頻出するクローズドアイテムセットのセットは、頻出するアイテムセットの完全なセットよりもかなり小さくすることができるため、情報を失うことなく頻出アイテムセットの完全なセットをより簡潔に表したものと言える。ＧＳＰシステムは、「クローズド」な一般化された文のパターンをマイニングするための様々な頻出クローズドアイテムセットマイニングアルゴリズムのいずれを使用するようにも適合することができる。例えば適切な頻出クローズドアイテムセットマイニングアルゴリズムについては、非特許文献２に記載されている。ＧＳＰシステムは、クローズドな、またはクローズドでない一般化された文のパターンと共に使用できることを当業者なら理解するであろう。したがって以降では、「一般化された文のパターン」という用語は、クローズドな、またはクローズドでない一般化された文のパターンのいずれかを指すために使用される。またマイニングされる一般化された文のパターンは、一般化された文のいずれか１つとまったく同じではない場合があり、別の一般化された文から抽出された単語を含む場合もあることを当業者なら理解するであろう。
【００３３】
文分類子およびドキュメントランク分類子は、一実施形態ではサポートベクトルマシンとすることができ、別の実施形態ではＡｄａ−ｂｏｏｓｔｉｎｇ分類子とすることができる。サポートベクトルマシンは、可能な入力のスペース内に超曲面(hyper-space)を見つけ出すことによって機能する。超曲面は、その超曲面に対する正の例(positive example)および負の例(negative example)のうちの最も近いものどうしの間の距離を最大化することによって、負の例から正の例を切り離そうと試みる。これによって、トレーニングデータに類似しているがまったく同じではないデータを正しく分類することができる。サポートベクトルマシンをトレーニングするために、様々な技術を使用することができる。１つの技術は、大きな二次計画問題を、分析的に解決できる一連の小さな二次計画問題に分解する順次最小最適化アルゴリズム(sequential minimal optimization algorithm)を使用する（非特許文献３を参照されたい）。
【００３４】
Ａｄａ  ｂｏｏｓｔｉｎｇは、トレーニングデータの集合上で複数のテストを実行する反復プロセスである。Ａｄａ  ｂｏｏｓｔｉｎｇは、弱い学習アルゴリズム（偶然よりもわずかに良好なレベルでしか機能しないアルゴリズム）を強い学習アルゴリズム（低いエラー率を示すアルゴリズム）へと変える。弱い学習アルゴリズムは、トレーニングデータの様々な下位集合上で実行される。このアルゴリズムは、先行するアルゴリズムが誤りを示す傾向があった例にますます集中する。このアルゴリズムは、比較的初期の弱い学習者が犯したエラーを訂正する。このアルゴリズムは、その先行するアルゴリズムのエラー率に適応するため、適応性がある。Ａｄａ  ｂｏｏｓｔｉｎｇは、大まかで適度に厳密さを欠く経験則を組み合わせて、パフォーマンスの高いアルゴリズムを作成する。Ａｄａ  ｂｏｏｓｔｉｎｇは、別々に実行されたそれぞれのテストの結果を組み合わせて、単一の非常に精密な分類子を作成する。
【００３５】
Ａｄａ  ｂｏｏｓｔｉｎｇは、弱い分類子を組み合わせて、強い分類子を作成する。Ｓ＝｛（ｘ１，ｙ１），（ｘ２，ｙ２），．．．，（ｘｍ，ｙｍ）｝をトレーニングデータのセットとする。弱い学習アルゴリズムは、トレーニング例のシーケンスＳおよび分布(distribution)Ｄｔを入力として受け入れる（ここでのＤｔ（ｉ）は、ｉ番目のトレーニング例の誤分類コスト(misclassification cost)と解釈することができる）。この入力に基づいて、弱い学習者は弱い仮説（分類子）ｈｔを出力し、分布Ｄｔは反復ｔで更新される。この仮説は、所定の反復限度に達するまで、更新された分布を使用して反復／更新される。このアルゴリズムは、次のトレーニングデータによって開始する。 
（ｘ１，ｙ１），．．．，（ｘｍ，ｙｍ）                            （３）
ここでは、ｘｉ∈ＸおよびＹｉ⊆ｙである。例えばｘｉは文特徴ベクトルであり、Ｙｉはその文用の可能な文モードのリストである。このアルゴリズムは、次の式に従って分布を初期化する。
【００３６】
【数１】
2006107464.tif 000003
【００３７】
次いでこのアルゴリズムは、分布Ｄｔを用いて弱い学習者をトレーニングして、弱い仮説ｈｔ：Ｘ×Ｙ→□を与える。次いでこのアルゴリズムは、αｔ∈□を選び、次の式に従って分布を初期化する。
【００３８】
【数２】
2006107464.tif 000004
【００３９】
ここでのｔは反復を識別し、Ｚｔは（Ｄｔ＋１が分布になるように選ばれる）正規化係数(normalization factor)である。次いでこのアルゴリズムは、最後の仮説を出力する。
【００４０】
【数３】
2006107464.tif 000005
【００４１】
弱い分類子は、次の式によって定義することができる。
【００４２】
【数４】
2006107464.tif 000006
【００４３】
ここでのｗは単語であり、ｃ０ｌおよびｃ１ｌは実数である。現在の分布Ｄｔを与えられると、このアルゴリズムは、それぞれの可能な分類ｌに関して、ｊ＝−１／＋１かつｂ＝−１／＋１の条件で次の式を計算する。
【００４４】
【数５】
2006107464.tif 000007
【００４５】
ここでは
【００４６】
【数６】
2006107464.tif 000008
【００４７】
およびＸ１＝｛ｘ：ｗ∈ｘ｝である。文分類子がトレーニングされると、文は次の式によって分類される。 
ｌ（ｘ）＝ａｒｇｍａｘｌｆ（ｘ，ｌ）                          （１０）
ここでのｘは文特徴ベクトルであり、ｌ（ｘ）は分類である。
【００４８】
サポートベクトルマシンを分類子として使用する場合、優先順位決定システムは、それぞれの分類ごと、およびそれぞれのランクレベルごとに別々の分類子をトレーニングする必要が生じる場合がある。例えば命令文の分類用の文分類子と、平叙文の分類用の別の文分類子を使用することがある。また高いランク用のドキュメントランク分類子と、低いランク用の別のドキュメントランク分類子を使用することもある。分類またはランキングを行う際、優先順位決定システムは、それぞれの分類子を試し、最適な分類またはランキングを選択する。
【００４９】
図３は、一実施形態における文分類子作成コンポーネントの処理を示す流れ図である。文分類子作成コンポーネントは、トレーニングデータ内のドキュメントのそれぞれの文ごとに文特徴ベクトルを作成し、それぞれの文の分類を入力し、次いで文分類子をトレーニングする。ブロック３０１において、このコンポーネントは、ドキュメント用キーワード特徴ベクトル作成コンポーネントを呼び出す。ブロック３０２では、このコンポーネントは、ドキュメント用語彙特徴ベクトル作成コンポーネントを呼び出す。ブロック３０３では、このコンポーネントは、ドキュメント用パターン特徴ベクトル作成コンポーネントを呼び出す。１つの文の文特徴ベクトルは、その文のキーワード特徴ベクトル、語彙特徴ベクトル、およびパターン特徴ベクトルを含む。ブロック３０４では、このコンポーネントは、トレーニングデータ内の各ドキュメントのそれぞれの文の分類を入力する。ブロック３０５では、このコンポーネントは、文特徴ベクトルおよびその分類を使用して、文分類子をトレーニングする。次いでこのコンポーネントは終了する。
【００５０】
図４は、一実施形態における文分類コンポーネントの処理を示す流れ図である。この実施形態では、このコンポーネントは、Ａｄａ−ｂｏｏｓｔｉｎｇ分類子を使用する。このコンポーネントは、ドキュメントを渡され、そのドキュメントの文の分類を返す。ブロック４０１において、このコンポーネントは、文用キーワード特徴ベクトル作成コンポーネントを呼び出す。ブロック４０２では、このコンポーネントは、文用語彙特徴ベクトル作成コンポーネントを呼び出す。ブロック４０３では、このコンポーネントは、文用パターン特徴ベクトル作成コンポーネントを呼び出す。ブロック４０４〜４０９では、このコンポーネントは、文分類子を使用して、ドキュメントの文の分類をループする。ブロック４０４では、このコンポーネントは、ドキュメントの次の文を選択する。判定ブロック４０５では、ドキュメントのすべての文が既に選択されている場合、このコンポーネントは終了し、そうでない場合、このコンポーネントはブロック４０６において継続する。ブロック４０６〜４０８では、このコンポーネントは、それぞれの文分類を選択するステップと、文分類子を使用して、選択された文に関するその文分類用のスコアを計算するステップとをループする。ブロック４０６では、このコンポーネントは、次の文分類を選択する。判定ブロック４０７では、選択された文に関するすべての文分類が既に選択されている場合、このコンポーネントはブロック４０９において継続し、そうでない場合、このコンポーネントはブロック４０８において継続する。ブロック４０８では、このコンポーネントは、文分類子を使用して、選択された文分類および選択された文用のスコアを計算する。次いでこのコンポーネントは、ブロック４０６へループして、次の文分類を選択する。ブロック４０９では、このコンポーネントは、選択された文の分類として、最も高いスコアを有する文分類を選択する。次いでこのコンポーネントは、ブロック４０４へループして、次の文を選択する。
【００５１】
図５は、一実施形態におけるドキュメントランク分類子作成コンポーネントの処理を示す流れ図である。このコンポーネントは、トレーニングデータのそれぞれのドキュメント用のドキュメント特徴ベクトルを作成する。１つのドキュメントのドキュメント特徴ベクトルは、そのドキュメント内のそれぞれの文の分類を含む。次いでこのコンポーネントは、トレーニングデータのドキュメント用のドキュメント特徴ベクトルおよびランキングのペアを使用して、分類子をトレーニングする。ブロック５０１において、このコンポーネントは、トレーニングデータの次のドキュメントを選択する。判定ブロック５０２では、トレーニングデータのすべてのドキュメントが既に選択されている場合、このコンポーネントはブロック５０５において継続し、そうでない場合、このコンポーネントはブロック５０３において継続する。ブロック５０３では、このコンポーネントは、ドキュメントの文分類コンポーネントを呼び出して、選択されたドキュメント用のドキュメント特徴ベクトルを作成する。ブロック５０４では、このコンポーネントは、選択されたドキュメントのランキングを入力する。次いでこのコンポーネントは、ブロック５０１へループして、トレーニングデータの次のドキュメントを選択する。ブロック５０５では、このコンポーネントは、ドキュメントランク分類子をトレーニングする。次いでこのコンポーネントは終了する。
【００５２】
図６は、一実施形態におけるドキュメントランク付けコンポーネントの処理を示す流れ図である。このコンポーネントは、ドキュメントを渡される。ブロック６０１において、このコンポーネントは、ドキュメントの文分類コンポーネントを呼び出して、その渡されたドキュメント用のドキュメント特徴ベクトルを作成する。ブロック６０２では、このコンポーネントは、ドキュメント特徴ベクトルをドキュメントランク分類子に提示して、渡されたドキュメント用のランキングを作成する。
【００５３】
図７〜１７は、一実施形態における文分類システムのコンポーネントの処理を示す流れ図である。図７は、一実施形態におけるドキュメント用キーワード特徴ベクトル作成コンポーネントの処理を示す流れ図である。このコンポーネントは、ドキュメントの集合（例えばトレーニングデータ）を渡され、各ドキュメント用のそれぞれの文ごとにキーワード特徴ベクトルを作成する。ブロック７０１において、このコンポーネントは、キーワード合計計算コンポーネントを呼び出して、キーワードの合計を計算し、この合計は、キーワードの重み付けを計算する際に使用される。ブロック７０２では、このコンポーネントは、次のドキュメントを選択する。判定ブロック７０３では、すべてのドキュメントが既に選択されている場合、このコンポーネントは戻り、そうでない場合、このコンポーネントはブロック７０４において継続する。ブロック７０４では、このコンポーネントは、文用キーワード特徴ベクトル作成コンポーネントを呼び出して、選択されたドキュメントの文用のキーワード特徴ベクトルを作成する。次いでこのコンポーネントは、ブロック７０２へループして、次のドキュメントを選択する。
【００５４】
図８は、一実施形態におけるキーワード合計計算コンポーネントの処理を示す流れ図である。このコンポーネントは、ドキュメントの集合内のそれぞれのキーワードごとにドキュメント頻度を計算する。ブロック８０１において、このコンポーネントは、次のドキュメントを選択する。判定ブロック８０２では、すべてのドキュメントが既に選択されている場合、このコンポーネントは戻り、そうでない場合、このコンポーネントはブロック８０３において継続する。ブロック８０３〜８０６では、このコンポーネントは、それぞれのキーワードを選択するステップと、その選択されたキーワードが、選択されたドキュメント内にある場合に、そのキーワード用のドキュメント頻度をインクリメントするステップとをループする。ブロック８０３では、このコンポーネントは、選択されたドキュメント用の次のキーワードを選択する。判定ブロック８０４では、すべてのキーワードが既に選択されている場合、このコンポーネントは、ブロック８０１へとループして、次のドキュメントを選択し、そうでない場合、このコンポーネントはブロック８０５において継続する。判定ブロック８０５では、選択されたキーワードが、選択されたドキュメント内にある場合、このコンポーネントはブロック８０６において継続し、そうでない場合、このコンポーネントはブロック８０３へとループして、次のキーワードを選択する。ブロック８０６では、このコンポーネントは、選択されたキーワード用のドキュメント頻度をインクリメントし、次いでブロック８０３へとループして、次のキーワードを選択する。
【００５５】
図９は、一実施形態における文用キーワード特徴ベクトル作成コンポーネントの処理を示す流れ図である。このコンポーネントは、ドキュメントを渡され、そのドキュメントのそれぞれの文ごとにキーワード特徴ベクトルを作成する。ブロック９０１において、このコンポーネントは、キーワード重み付け作成コンポーネントを呼び出して、その渡されたドキュメントのキーワード用にキーワードの重み付けを作成する。ブロック９０２では、このコンポーネントは、渡されたドキュメントの次の文を選択する。判定ブロック９０３では、渡されたドキュメントのすべての文が既に選択されている場合、このコンポーネントは戻り、そうでない場合、このコンポーネントはブロック９０４において継続する。ブロック９０４〜９０６では、このコンポーネントは、選択された文のそれぞれのキーワードを選択するステップと、選択されたキーワードの重み付けを、選択された文用のキーワード特徴ベクトルに追加するステップとをループする。ブロック９０４では、このコンポーネントは、選択された文の次のキーワードを選択する。判定ブロック９０５では、選択された文のすべてのキーワードが既に選択されている場合、このコンポーネントは、ブロック９０２へとループして、渡されたドキュメントの次の文を選択し、そうでない場合、このコンポーネントはブロック９０６において継続する。ブロック９０６では、このコンポーネントは、キーワード特徴ベクトルの次の要素を、選択されたキーワードの重み付けに設定し、ブロック９０４へとループして、選択された文の次のキーワードを選択する。
【００５６】
図１０は、一実施形態におけるキーワード重み付け作成コンポーネントの処理を示す流れ図である。このコンポーネントは、ドキュメントを渡され、以前に計算されたキーワード用のドキュメント頻度を使用して、そのドキュメントのキーワードの重み付けを計算する。ブロック１００１において、このコンポーネントは、次のキーワードを選択する。判定ブロック１００２では、すべてのキーワードが既に選択されている場合、このコンポーネントは戻り、そうでない場合、このコンポーネントはブロック１００３において継続する。ブロック１００３では、このコンポーネントは、渡されたドキュメント用の選択されたキーワードの重み付けを、選択されたドキュメント内のそのキーワードの用語頻度に、ドキュメント数をそのキーワードのドキュメント頻度で割った商の対数を掛けた積に設定する。次いでこのコンポーネントは、ブロック１００１へとループして、次のキーワードを選択する。
【００５７】
図１１は、一実施形態におけるドキュメント用語彙特徴ベクトル作成コンポーネントの処理を示す流れ図である。このコンポーネントは、ドキュメントの集合を渡され、各ドキュメントのそれぞれの文ごとに語彙特徴ベクトルを作成する。ブロック１１０１において、このコンポーネントは、集合内の次のドキュメントを選択する。判定ブロック１１０２では、集合のすべてのドキュメントが既に選択されている場合、このコンポーネントは戻り、そうでない場合、このコンポーネントはブロック１１０３において継続する。ブロック１１０３では、このコンポーネントは、選択されたドキュメントを渡す文用語彙特徴ベクトル作成コンポーネントを呼び出す。次いでこのコンポーネントは、ブロック１１０１へとループして、渡された集合の次のドキュメントを選択する。
【００５８】
図１２は、一実施形態における文用語彙特徴ベクトル作成コンポーネントの処理を示す流れ図である。このコンポーネントは、ドキュメントを渡され、そのドキュメントの文用の語彙特徴ベクトルを計算する。ブロック１２０１において、このコンポーネントは、渡されたドキュメントの次の文を選択する。判定ブロック１２０２では、渡されたドキュメントのすべての文が既に選択されている場合、このコンポーネントは戻り、そうでない場合、このコンポーネントはブロック１２０３において継続する。ブロック１２０３では、このコンポーネントは、選択された文の単語にその品詞によってタグを付ける。ブロック１２０４では、このコンポーネントは、選択された文内の語句を識別する。ブロック１２０５では、このコンポーネントは、選択された文内の名前付きのエンティティを識別する。次いでこのコンポーネントは、ブロック１２０１へとループして、渡されたドキュメントの次の文を選択する。このコンポーネントは、自然言語プロセッサを使用して、品詞、語句、および名前付きのエンティティを識別することができる。
【００５９】
図１３は、一実施形態におけるドキュメント用パターン特徴ベクトル作成コンポーネントの処理を示す流れ図である。このコンポーネントは、ドキュメントの集合を渡され、各ドキュメント内のそれぞれの文ごとにパターン特徴ベクトルを作成する。ブロック１３０１において、このコンポーネントは、一般化された文のパターン識別コンポーネントを呼び出して、渡されたドキュメント内の文の一般化された文のパターンを識別する。ブロック１３０２では、このコンポーネントは、渡されたドキュメントの集合内の次のドキュメントを選択する。判定ブロック１３０３では、渡された集合のすべてのドキュメントが既に選択されている場合、このコンポーネントは戻り、そうでない場合、このコンポーネントはブロック１３０４において継続する。ブロック１３０４では、このコンポーネントは、文の一般化された文のパターン識別コンポーネントを呼び出して、選択されたドキュメントの文の一般化された文に最も類似する一般化された文のパターンを識別する。次いでこのコンポーネントは、ブロック１３０２へとループして、次のドキュメントを選択する。
【００６０】
図１４は、一実施形態における一般化された文のパターン識別コンポーネントの処理を示す流れ図である。この実施形態では、このコンポーネントは、一般化された文のそれぞれのペアが、一般化された文のパターンになるためのサポートを計算する。このコンポーネントは、前述のように頻出アイテムセットマイニングアルゴリズムを代替として使用することができる。このコンポーネントは、自然言語プロセッサを使用して、一般化された文を作成することができる。ブロック１４０１〜１４０３では、このコンポーネントは、渡されたドキュメントのそれぞれの文ごとに一般化された文を作成するステップをループする。ブロック１４０１において、このコンポーネントは、渡されたドキュメントの次の文を選択する。判定ブロック１４０２では、すべての文が既に選択されている場合、このコンポーネントはブロック１４０４において継続し、そうでない場合、このコンポーネントはブロック１４０３において継続する。ブロック１４０３では、このコンポーネントは、選択された文用の一般化された文を作成し、ブロック１４０１へとループして、次の文を選択する。ブロック１４０４〜１４１１では、このコンポーネントは、それぞれの一般化された文を選択するステップと、一般化された文のパターンを示す文を、一般化された文のパターンとしてマークするステップとをループする。ブロック１４０４では、このコンポーネントは、次の一般化された文を選択する。判定ブロック１４０５では、渡されたドキュメントのすべての一般化された文が既に選択されている場合、このコンポーネントは戻り、そうでない場合、このコンポーネントはブロック１４０６において継続する。ブロック１４０６では、このコンポーネントは、次の一般化された文を選ぶ。判定ブロック１４０７では、すべての一般化された文が既に選ばれている場合、このコンポーネントはブロック１４０４へとループして、次の一般化された文を選択し、そうでない場合、このコンポーネントはブロック１４０８において継続する。判定ブロック１４０８では、選択された一般化された文が、選ばれた一般化された文内に含まれている場合、このコンポーネントはブロック１４０９において継続し、そうでない場合、このコンポーネントはブロック１４０６へとループして、次の一般化された文を選ぶ。ブロック１４０９では、このコンポーネントは、選択された一般化された文が、一般化された文のパターンになるためのサポートをインクリメントする。判定ブロック１４１０では、選択された一般化された文が、一般化された文のパターンになるのに十分なサポートを有している場合、このコンポーネントは、ブロック１４１１において継続し、そうでない場合、このコンポーネントは、ブロック１４０６へとループして、選択された一般化された文用の次の一般化された文を選ぶ。ブロック１４１１では、このコンポーネントは、選択された一般化された文を、一般化された文のパターンとしてマークし、ブロック１４０４へとループして、次の一般化された文を選択する。このコンポーネントはまた、「ｎｏｕｎ  ｖｅｒｂ」のパターンなどの特に有益ではない一般化された文のパターンを削除することもできる。
【００６１】
図１５は、一実施形態における文の一般化された文のパターン識別コンポーネントの処理を示す流れ図である。このコンポーネントは、ドキュメントを渡され、そのドキュメント内のそれぞれの文の一般化された文のパターンを識別する。ブロック１５０１において、このコンポーネントは、渡されたドキュメントの次の文を選択する。判定ブロック１５０２では、渡されたドキュメントのすべての文が既に選択されている場合、このコンポーネントは戻り、そうでない場合、このコンポーネントはブロック１５０３において継続する。ブロック１５０３〜１５０５では、このコンポーネントは、それぞれの一般化された文のパターンを選択するステップと、それぞれの一般化された文のパターンに対する選択された文の類似性を計算するステップとをループする。ブロック１５０３では、このコンポーネントは、次の一般化された文のパターンを選択する。判定ブロック１５０４では、すべての一般化された文のパターンが既に選択されている場合、このコンポーネントはブロック１５０６において継続し、そうでない場合、  このコンポーネントはブロック１５０５において継続する。ブロック１５０５では、このコンポーネントは、選択された文の一般化された文と、選択された一般化された文のパターンとの類似性を計算し、次いでブロック１５０３へとループして、次の一般化された文のパターンを選択する。ブロック１５０６では、このコンポーネントは、最も高い類似性を有する一般化された文のパターンを選択し、次いでブロック１５０１へとループして、渡されたドキュメントの次の文を選択する。
【００６２】
図１６は、一実施形態における入力分類コンポーネントの処理を示す流れ図である。このコンポーネントは、ドキュメントの集合を渡され、各ドキュメント内のそれぞれの文の分類を入力する。ブロック１６０１において、このコンポーネントは、渡されたドキュメントの集合内の次のドキュメントを選択する。判定ブロック１６０２では、渡されたドキュメントの集合内のすべてのドキュメントが既に選択されている場合、このコンポーネントは戻り、そうでない場合、このコンポーネントはブロック１６０３において継続する。ブロック１６０３では、このコンポーネントは、選択されたドキュメントの次の文を選択する。判定ブロック１６０４では、選択されたドキュメントのすべての文が既に選択されている場合、このコンポーネントはブロック１６０１へとループして、次のドキュメントを選択し、そうでない場合、このコンポーネントはブロック１６０５において継続する。ブロック１６０５では、このコンポーネントは、選択された文の分類を受け取り、次いでブロック１６０３へとループして、次の文を選択する。
【００６３】
図１７は、一実施形態における文分類子トレーニングコンポーネントの処理を示す流れ図である。このコンポーネントは、Ａｄａ−ｂｏｏｓｔｉｎｇ分類子用のトレーニングを実施する。ブロック１７０１において、このコンポーネントは、方程式４に従って分布を初期化する。ブロック１７０２〜１７０７では、このコンポーネントは、所定の反復回数にわたって改善された仮説を計算するステップをループする。ブロック１７０２において、このコンポーネントは、反復回数をインクリメントする。判定ブロック１７０３では、反復回数が所定の反復回数を超えた場合、このコンポーネントはブロック１７０８において継続し、そうでない場合、このコンポーネントはブロック１７０４において継続する。ブロック１７０４では、このコンポーネントは、方程式８に従ってこの反復用の重み付けを計算する。ブロック１７０５では、このコンポーネントは、方程式７および９に従って分類子を設定する。ブロック１７０６では、このコンポーネントは、方程式９に従って反復の重み係数を設定する。ブロック１７０７では、このコンポーネントは、方程式５に従って新たな分布を計算する。次いでこのコンポーネントは、ブロック１７０２へとループして、次の反復の処理を開始する。ブロック１７０８では、このコンポーネントは、方程式６に従って分類子を出力し、次いで終了する。
【００６４】
上記のことから、本明細書では例示の目的で本発明の具体的な実施形態について説明しているが、本発明の趣旨および範囲から逸脱することなく様々な修正を実施できることが理解できるであろう。したがって本発明は、添付の特許請求の範囲以外のものによって限定されることはない。
【図面の簡単な説明】
【００６５】
【図１】一実施形態における文分類システムのコンポーネントを示すブロック図である。
【図２】一実施形態におけるドキュメントランキングシステムのコンポーネントを示すブロック図である。
【図３】一実施形態における文分類子作成コンポーネントの処理を示す流れ図である。
【図４】一実施形態における文分類コンポーネントの処理を示す流れ図である。
【図５】一実施形態におけるドキュメントランク分類子作成コンポーネントの処理を示す流れ図である。
【図６】一実施形態におけるドキュメントランク付けコンポーネントの処理を示す流れ図である。
【図７】一実施形態におけるドキュメント用キーワード特徴ベクトル作成コンポーネントの処理を示す流れ図である。
【図８】一実施形態におけるキーワード合計計算コンポーネントの処理を示す流れ図である。
【図９】一実施形態における文用キーワード特徴ベクトル作成コンポーネントの処理を示す流れ図である。
【図１０】一実施形態におけるキーワード重み付け作成コンポーネントの処理を示す流れ図である。
【図１１】一実施形態におけるドキュメント用語彙特徴ベクトル作成コンポーネントの処理を示す流れ図である。
【図１２】一実施形態における文用語彙特徴ベクトル作成コンポーネントの処理を示す流れ図である。
【図１３】一実施形態におけるドキュメント用パターン特徴ベクトル作成コンポーネントの処理を示す流れ図である。
【図１４】一実施形態における一般化された文のパターン識別コンポーネントの処理を示す流れ図である。
【図１５】一実施形態における文の一般化された文のパターン識別コンポーネントの処理を示す流れ図である。
【図１６】一実施形態における入力分類コンポーネントの処理を示す流れ図である。
【図１７】一実施形態における文分類子トレーニングコンポーネントの処理を示す流れ図である。
【図１】
2006107464.tif 000009
【図２】
2006107464.tif 000010
【図３】
2006107464.tif 000011
【図４】
2006107464.tif 000012
【図５】
2006107464.tif 000013
【図６】
2006107464.tif 000014
【図７】
2006107464.tif 000015
【図８】
2006107464.tif 000016
【図９】
2006107464.tif 000017
【図１０】
2006107464.tif 000018
【図１１】
2006107464.tif 000019
【図１２】
2006107464.tif 000020
【図１３】
2006107464.tif 000021
【図１４】
2006107464.tif 000022
【図１５】
2006107464.tif 000023
【図１６】
2006107464.tif 000024
【図１７】
2006107464.tif 000025
【外国語明細書】
2006107464000001.pdf