(57)【要約】【課題】収集されたテキストから自動的に因果関係を抽出する。【解決手段】本発明は、テキストデータ中の単語間の関係を抽出する方法を提供する。最初に、因果関係を記述する三連単語のような訓練関係データが、訓練関係データを含む追加テキストデータを収集するために、受け付けられ使用される。訓練データを受け付け、追加テキストデータを収集するために、分散データコレクションが使用される。これにより、多くのソースから広範囲のデータを入手し得る。統語パターンが追加テキストデータから抽出され、抽出された統語パターンを使用して、１又は複数の因果関係を記述する追加関係データを抽出するために、分散データソースが走査される。抽出された追加関係データは格納される前に教師付学習アルゴリズムによって有効化され、分類部が追加関係データを自動的に有効化するのを訓練するために使用される。【選択図】図２
2009539191.tif 000002
【特許請求の範囲】
【請求項１】
テキストデータから関係を抽出するコンピュータベースの方法であって、
前記方法は、
第１の分散データソースから、１つの動作と１つの対象との間の関係を記述した３以上の単語を含む訓練データを受け付けるステップと、
前記受け付けた訓練データを含むテキストデータを収集するステップと、
前記収集されたテキストデータから１つの統語パターンを抽出するステップと、
第２の分散データソースを走査するステップと、
前記第２の分散データソースから、前記抽出された統語パターンを使用しているターゲット関係を抽出するステップと、
前記ターゲット関係を、コンピュータストレージ媒体に格納するステップと、
を有することを特徴とする方法。
【請求項２】
前記１つの統語パターンを抽出するステップは、
前記テキストデータの単語間の関係を記述する、１つの係り受けツリーを生成するステップを有すること、
を特徴とする請求項１に記載の方法。
【請求項３】
前記１つの統語パターンを抽出するステップは、
前記係り受けツリーに対して語順を挿入するステップを更に有すること、
を特徴とする請求項２に記載の方法。
【請求項４】
前記訓練データは、
１つの対象、１つの動作、及び前記動作が前記対象に及ぼす１つの効果を記述する１つ又は複数の三連単語を有すること、
を特徴とする請求項１に記載の方法。
【請求項５】
前記１つの統語パターンを抽出するステップは、
前記係り受けツリーに対して衛星リンクを挿入するステップを更に有すること、
を特徴とする請求項２に記載の方法。
【請求項６】
前記識別された関係を格納するステップは、
１つのターゲット関係の有効性を決定すること、及び
前記識別された関係が有効であると決定された場合は、前記ターゲット関係を格納すること、
を有することを特徴とする請求項１に記載の方法。
【請求項７】
前記１つの統語パターンを抽出するステップは、
前記テキストデータを事前処理して代名詞を解析するためにすることを更に有すること、
を特徴とする請求項２に記載の方法。
【請求項８】
テキストデータから関係を抽出するシステムであって、
前記システムは、
訓練データとテキストデータを受け付ける入力装置と、
前記入力装置に接続され、前記受け付けた訓練データを示す情報を格納する記憶装置と、
前記入力装置及び記憶装置に接続され、前記テキストデータから前記受け付けた訓練データを用いている１つの統語パターンを抽出する抽出モジュールと、
前記抽出モジュール及び記憶装置に接続され、前記抽出された統語パターンによって記述された関係を分類する分類部と、
を有することを特徴とするシステム。
【請求項９】
前記抽出モジュールは、
前記テキストデータから１つの係り受けツリーを生成すること、
を特徴とする請求項８に記載のシステム。
【請求項１０】
前記抽出モジュールは、更に、
前記テキストデータを事前処理して前記テキストデータ内の代名詞を識別すること、
を特徴とする請求項８に記載のシステム。
【請求項１１】
前記抽出モジュールは、更に、
前記係り受けツリーに対して衛星リンクを挿入して前記テキストデータ内の単語間の関係を識別すること、
を特徴とする請求項９に記載のシステム。
【請求項１２】
前記抽出モジュールは、
前記抽出された統語パターンに対して１つの語順を記述するデータを挿入すること、
を特徴とする請求項８に記載のシステム。
【請求項１３】
テキストデータから関係を抽出するコンピュータが実行可能なコードを格納したコンピュータが読取可能な媒体を含むコンピュータプログラム製品であって、
前記実行可能なコードは、
第１の分散データソースから、１つの動作と１つの対象との間の関係を記述した３以上の単語を含む訓練データを受け付けるステップと、
前記受け付けた訓練データを含むテキストデータを収集するステップと、
前記収集されたテキストデータから１つの統語パターンを抽出するステップと、
第２の分散データソースを走査するステップと、
前記第２の分散データソースから、前記抽出された統語パターンを使用しているターゲット関係を抽出するステップと、
前記ターゲット関係を、コンピュータストレージ媒体に格納するステップと、
を実行することを特徴とするコンピュータプログラム製品。
【請求項１４】
前記１つの統語パターンを抽出するステップは、
前記テキストデータの単語間の関係を記述する、１つの係り受けツリーを生成するステップを有すること、
を特徴とする請求項１３に記載のコンピュータプログラム製品。
【請求項１５】
前記１つの統語パターンを抽出するステップは、更に、
前記テキストデータを事前処理して代名詞を解析すること、及び
前記係り受けツリーに対して衛星リンクを挿入すること、
を含むことを特徴とする請求項１４に記載のコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願）
本出願は、２００６年５月３０日に出願された米国特許仮出願第６０／８０９，７８０号、及び米国特許出願第１１／７５４，９６６号を基礎とする優先権を主張し、これらの出願はその全体がここに引用される。
【０００２】
本発明は、機械学習に関し、特に、テキストから関係データを抽出するシステム及び方法に関する。
【背景技術】
【０００３】
動作の識別及び分類は、機械学習においては興味深い。なぜならば、それは、異なる動作の結果をロボットに学習させるメカニズムを提供するからである。例えば、因果関係を記述するデータは、異なる動作がどのように異なる対象に影響するかを特定するために使用され得る。このような関係データは、様々な型式の対象に対してどの様に関係するかを記述する、ロボット用の“常識”データベースを生成するために使用され得る。
【０００４】
しかしながら、従来の因果関係取得技術は限定されている。既存の分散収集技術は、関係データを、ボランティアから受け取る。このことによって収集データの最初の広がり（burst）が提供される。しかしながら、収集データは、時間の経過につれて、著しくより小さな量にまで減少する。故に、従来のデータ収集方法は、データの連続ストリームを提供するために拡大縮小可能（scalable）にはなっていない。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
必要とされているのは、収集されたテキストから自動的に因果関係を抽出するためのシステム及び方法である。
【課題を解決するための手段】
【０００６】
（発明の要約）
本発明は、テキストデータから、因果関係のような関係を抽出する方法を提供する。ある実施形態においては、１つの対象と１つの動作との間の関係を記述する訓練データが、訓練データを含むテキストデータを収集するために受け付けられ、使用される。例えば、受け付けた訓練データは、１つの対象、１つの動作及び１つの効果を記述する三連単語（triplet）を含み、三連単語を含むテキストデータが収集される。
ある実施形態においては、インターネットベースのコレクション又はマルチユーザコレクションのような分散データコレクションが、多数のソースからテキストデータを収集するために使用される。次に、係り受けツリーのような統語パターンが、収集されたテキストデータから抽出され、収集されたテキストデータ内の関係を識別するために使用される。次に、分散データソースが走査され、抽出された統語パターンが、分散データソースから、１つの動作と１つの対象との間の関係を抽出するために使用される。次に、抽出された関係は、コンピュータストレージ媒体に格納され、三連単語データストアを生成する。このことは、関係データが、自動的に収集されたテキストデータから収集され、識別されることを可能とし、拡大縮小可能（scalable）なデータ収集方法を提供する。
【０００７】
ある実施形態においては、代名詞と関連付けられた名詞を識別することによって代名詞を解析するために、テキストデータの第１の事前処理を行うことによって、統語パターンが抽出される。次に、テキストデータ内の単語間の関係を記述する係り受けツリーが生成される。次に、衛星リンクが、係り受けツリーに挿入され、係り受けツリーの基本パスに沿った関係以外の関係を識別する。ある実施形態においては、異なる順序で同じ複数の単語を含む関係が区別され得るように、語順データが、係り受けツリーに挿入され、関係データの成分の順序を示す。
【０００８】
ある実施形態においては、格納され抽出された関係が分類部を訓練するために使用され、有効な三連単語を自動的に識別する。例えば、格納され抽出された関係が有効化され、有効化結果が、追加三連単語を有効又は無効の何れかに分類するために使用される。
ある実施形態においては、ユーザが手動で、格納され抽出された関係が有効であるか否かを決定する。代替的に、予め定義されたデータが、格納され抽出された関係が有効であるか否かを決定するために使用される。
【０００９】
本明細書に記載される特徴や効果は限定されたものではなく、特に、図面、明細書及び特許請求の範囲を見た当業者には多くの追加的特徴や効果が明らかになるであろう。さらに、本明細書で使用される用語は、主として読みやすさや教育目的から選択されており、本発明の主旨を限定するために選択されているのではない。
【図面の簡単な説明】
【００１０】
【図１】本発明の一実施形態に係るコンピュータシステムを示す図である。
【図２】本発明の一実施形態に係る、テキストデータから因果関係を抽出する方法を示すフローチャートである。
【図３】本発明の一実施形態に係る、観察される動作を記述する特徴ベクトルを生成する方法を示すフローチャートである。
【図４】本発明の一実施形態に係る係り受けツリーの一例を示す図である。
【図５】本発明の一実施形態に係る分類訓練入力データの一例を示す図である。
【発明を実施するための形態】
【００１１】
（発明の詳細な説明）
以降、本発明の好適な実施形態を、図面を参照しつつ説明する。同様の参照番号は同一の又は機能的に同様の要素を示している。また、各参照番号の最も左の数字は、その番号が最初に用いられた図の番号に対応している。
【００１２】
本明細書において、“ある実施形態”又は“１つの実施形態”と言う場合は、本発明の少なくとも１つの実施形態に、その実施形態に関連して記述される１つの特徴又は構造が含まれていることを意味する。本明細書のあちこちに“ある実施形態では”という語が出現しても、必ずしも同一の実施形態を指しているわけではない。
【００１３】
後記する詳細説明のいくつかの部分は、アルゴリズム用語や、コンピュータメモリ内のデータビット操作を示す象徴的な表現による。これらのアルゴリズム的な説明や表現は、情報処理分野の当業者が、自らの業績の要旨を、同分野の他の当業者に最も効率的に伝えるために用いる手段である。
アルゴリズムとは、ここでは、そして一般的にも、ある所望の結果に至る複数のステップ（命令）の首尾一貫したシーケンスのことを言う。ステップとは、物理量に対する物理的操作を要求するステップのことである。通常それらの数値は、記憶され、転送され、合成され、比較されかつ操作され得る、電子的、磁気的又は光学的信号の形を取る。これらの信号のことを、ビット、値、要素、シンボル、文字、語又は番号等と呼ぶことが主として用語の共通化の理由から便宜である。さらに、物理量に対する物理的操作を要求するステップの配列のうちいくつかのものは、一般性を失うことなく、モジュール又はコードデバイスと呼ぶことが便宜である。
【００１４】
しかし、このような用語の全ては適当な物理量と関連付けられており、これらの物理量に付された単なる便宜的なラベルに過ぎない。後記において特段の説明がない限り、明細書本文全体を通じて、“処理”、“コンピューティング”、“計算”、“決定”又は“表示”等の用語を用いた説明は、（電子的な）物理量としてのデータを、コンピュータシステムのメモリ、レジスタ又は他の情報ストレージのなかで操作しかつ変形するコンピュータシステムや同様の電子的コンピューティングデバイスの動作や処理のことを言う。
【００１５】
本発明のいくつかの側面は、アルゴリズムの形になったプロセスステップや命令を含む。本発明のプロセスステップや命令は、ソフトウエア、ファームウエア又はハードウエアによって実施され、ソフトウエアで実施される場合は、ダウンロードされることが可能であり、多様なオペレーティングシステムが用いる別のプラットフォームから操作されることも可能である。
【００１６】
本発明は、ここでの操作を実行する装置にも関する。この装置は、所与の目的を達成する専用装置であってもよいし、コンピュータに記憶されたコンピュータプログラムによって動作する汎用コンピュータであってもよい。このようなコンピュータプログラムは、コンピュータが読取り可能な媒体に記憶され得る。
その媒体とは、コンピュータシステムバスに接続可能な、フロッピー（登録商標）ディスク、光ディスク、ＣＤ−ＲＯＭ、電磁光学的ディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、電磁的又は光学的カード、ＡＳＩＣ又は電子的命令を記憶し得るあらゆる媒体を含むが、これらに限定されない。さらに、本明細書で言うコンピュータは、単体のプロセッサを含んでもよいし、コンピュータ能力を増加させるために複数のプロセッサを用いた装置であってもよい。
【００１７】
ここでいうアルゴリズムやディスプレイは、もともと特定のコンピュータや他の装置に関係している訳ではない。ここで教示される内容に従って、プログラムとともに多様な一般目的システムが使用され得る。又は、必要とされる方法ステップを実行するためにさらに特化した装置を作成することも便宜である。これらのシステムのそれぞれについてどのような構成が必要となるかは、後記する明細書本文から明らかになる。
さらには、本発明は特定のプログラム言語を参照して記述されるものではない。本発明の教示を実行するために、多様なプログラム言語が使用され得る。後記する特定の言語に言及した場合、それは本発明の実施可能性及びベストモードを開示するためである。
【００１８】
さらに、本明細書で使用される言語は、主として読み易さ及び教育目的から選択されているのであって、本発明の主旨を限定するために選択されているのではない。従って、本発明の開示は、特許請求の範囲にて記述されている本発明の範囲を例示するものであるが限定するものではない。
【００１９】
図１は、本発明の一実施形態に係るコンピュータシステムである。コンピュータシステム１００は、中央制御装置１１０、入力装置１２０、出力装置１３０、記憶装置１４０、及び通信装置１５０を含む。
【００２０】
中央制御装置１１０は、データ信号を処理し、複合命令セットコンピュータ（ＣＩＳＣ）アーキテクチャ、縮小命令セットコンピュータ（ＲＩＳＣ）アーキテクチャ、又は命令セットの組合せを実装するアーキテクチャのような様々なコンピューティングアーキテクチャを含み得る。
図１においては単一の中央制御装置が示されているが、複数の中央制御装置が含まれ得る。中央制御装置１１０は、算術論理演算ユニット、マイクロプロセッサ、汎用コンピュータ、若しくは、記憶装置１４０、入力装置１２０、出力装置１３０、又は通信装置１５０からの電子データ信号を送信し、受信し、かつ処理し得る他の情報処理製品を含む。
【００２１】
入力装置１２０は、カーソルコントローラ、又はキーボードのような、コンピュータシステム１００に対してユーザ入力を提供するあらゆる装置である。ある実施形態においては、入力装置１２０は、キーボード（例えばＱＷＥＲＴＹキーボード）、キーパッド、又は中央制御装置１１０や記憶装置１４０との間で情報や命令の遣り取りを行うタッチパネル上のこれらの代替物を含み得る。
他の実施形態においては、入力装置１２０は、ジョイスティック、マウス、トラックボール、スタイラス、ペン、タッチスクリーン、カーソル方向キー、又は画像の動きを調節し得る他のメカニズムのような、中央制御装置１１０との間で位置情報の遣り取り及び選択の指令を行うユーザ入力装置である。
【００２２】
出力装置１３０は、ここに記述されたような電子画像やデータを表示するあらゆる装置を示す。出力装置１３０は、例えば、有機発光ダイオードディスプレイ（ＯＬＥＤ）、液晶ディスプレイ（ＬＣＤ）、陰極管ディスプレイ（ＣＲＴ）、同等な他の表示装置、スクリーン又はモニターであってもよい。ある実施形態においては、出力装置１３０は、圧力感応式透明パネルが出力装置１３０のスクリーンを覆うようなタッチスクリーンを備えている。
【００２３】
記憶装置１４０は、中央制御装置１１０によって実行される命令やデータを格納する。命令やデータは、ここで記述される任意の技術を実行するためのコードを含み得る。記憶装置１４０は、動的ランダムアクセスメモリ（ＤＲＡＭ）デバイス、静的ランダムアクセスメモリ（ＳＲＡＭ）デバイス、フラッシュＲＡＭ（不揮発性ストレージ）、これらの組合せ、又は当業界に知られている他のメモリーデバイスであってもよい。記憶装置１４０は、データストア１４２、抽出モジュール１４４及び分類部１４６を含み、中央制御装置１１０、入力装置１２０、出力装置１３０及び／又は通信装置１５０と接続されている。
【００２４】
データストア１４２は、動作と対象との間の因果関係を記述する参照データを格納する。例えば、データストア１４２は、その対象、その動作及びその結果である効果を、その形を有する三連単語を用いて示すことによって１つの対象に対して１つの動作を実行する効果を記述するテキストの、グループ化された三連単語を格納する。
したがって、“（car, sell, sold）”、“（drink, refrigerated, chilled）”、“（ball, pushed, roll）”のような三連単語が格納されて、様々な動作がどの様に異なる対象に影響するかを記述する。代替的に、データストア１４２は、１つの動作が１つの対象に対して適用された結果を記述するテキストセンテンスを含む。しかしながら前記したことは例示に過ぎず、データストア１４２は、１つの対象、１つの動作及び１つの結果の間の因果関係を記述することができる又は識別することができるあらゆる情報を含み得る。
【００２５】
抽出モジュール１４４は、テキストデータからの因果関係の抽出についての情報を提供する。テキストからデータを抽出することにより、システムは、受け付けたテキストから因果関係を自動的に取得し学習して、識別され得る関係の数と型式を増加させる。したがって、センテンスのようなテキストデータは、インターネット又は多様なユーザのような多様なソースからデータを取得する分散収集システムから取得され、抽出モジュール１４４は、取得されたデータが因果関係を含むか否かを決定する。
例えば、抽出モジュール１４４は、受け取ったテキストデータを構文解析することによって又は取得されたデータ内の統語パターンを識別するためのあらゆる他の方法によって係り受けパスやツリーをどの様にして生成するかを記述したデータを含む。例えば、抽出モジュール１４４は、テキストデータを構文解析し、“if-then”、“when-then”又は他の構造を識別する。統語パターンを識別する又は係り受けツリーを生成すると前記したが、抽出モジュール１４４は、受け付けたデータの、因果関係を識別し得るあらゆる特徴を決定するための指示を含み得る。
【００２６】
分類部１４６は、抽出された因果関係の有効性の決定についての情報を提供する。例えば、分類部１４６は、教師付学習アルゴリズムを適用し、抽出された関係の特徴を検証するための指示を含む。
ある実施形態においては、分類部１４６は、抽出された関係が、データストア１４２に格納されている少なくとも１つの因果関係を満足させるか否かを決定する。例えば、分類部は、１組の事前に決定された又は手動で供給された、語彙パターン中の三連単語の有効性を記述した規則を提供し、追加の三連単語が有効であるか無効であるかを分類する。
あるいは代替的に、分類部は、語彙パターンと三連単語の間の関係を記述するデータをユーザに提供し、語彙パターン毎の三連単語の有効性を手動で特定させる。ある実施形態においては、最初の関係データと抽出された関係データとの間の関係は、例えば http://www.autonlab.org/autonweb/14618/version/3/part/5/data/komarek:cglr.pdf?branch=main&language=enにおいて提供されているKomarek and Moore“Fast Robust Logistic     Regression for Large Sparse Datasets with Binary Outputs”に記述された疎２値ロジスティック回帰（sparse binary logistic regression）を使用する分類アルゴリズムを修正するために使用される。なお、当該文献の全体がここに引用される。しかしながら、前記は単なる例示であり、分類部は、抽出されたデータが、１つの動作が１つの対象に及ぼす効果を記述しているデータであるか否かを決定し得るあらゆる情報を含み得る。
【００２７】
コンピュータシステム１００は、コンピュータデバイス１００をネットワーク（図示せず）又は他のコンピュータシステム１００に接続する通信装置１５０を更に含む。ネットワークは、ＬＡＮ、ＷＡＮ（例えばインターネット）及び／又は多数のデバイスがそれを通じて通信可能な他の相互接続可能データパスを含んでもよい。
ある実施形態においては、通信装置１５０は、ファイルや情報を分配するために他のコンピュータシステム１００と接続される、ＵＳＢ，ＩＥＥＥ１３９４又はイーサネット（登録商標）のような、従来型の有線通信機である。他の実施形態においては、通信装置１５０は、赤外線通信としての、IEEE802.11/a/b/g/n（すなわちWiFi）通信、Bluetooth（登録商標）通信、３Ｇ通信、IEEE802.16（すなわちWiMax）通信、ラジオ周波数通信のような従来型の無線通信機である。代替的に、通信装置１５０は、無線通信機と有線通信機との組合せを含む。
【００２８】
本発明の主旨と範囲を逸脱せずに図１に示された構成より多くの又はより少ない構成をコンピュータシステム１００が含んでもよいことは、当業者にとっては明らかである。例えば、コンピュータシステム１００は、一次若しくは二次キャッシュ、又は１若しくは複数の特定用途集積回路（ＡＳＩＣ）のような追加メモリを含んでもよい。同様にコンピュータシステム１００は、追加的な入力装置又は出力装置を含んでもよい。
本発明のある実施形態においては、１又は複数の構成（１１０、１２０、１３０、１４０、１４２、１４４、１４６、１５０）は相互に近接して配置され得る一方、他の実施形態においてはこれらの構成は地理的に隔離されて配置され得る。例えば、記憶装置１４０内の各ユニットは、分散コンピュータシステム１００に配置された１又は複数の中央制御装置１１０によって実行され得るプログラムであり得る。
【００２９】
図２は、本発明のある実施形態に係る、テキストデータから因果関係を抽出する方法を示すフローチャートである。
ある実施形態においては、コンピュータシステム１００は、最初に、分散キャプチャ技術を用いて、関係三連単語のような訓練関係データを受け付ける（ステップ２１０）。例えば、コンピュータシステム１００は、多数のユーザから入力装置１２０又は通信装置１５０を介して、動作の対象に及ぼす効果を記述する“（balloon, released, floating）”、“（battery, discharged, dead）”、“（drink, refrigerated, chilled）”のような関係三連単語を受け付ける（ステップ２１０）。
ある実施形態においては、受け付けた関係三連単語は、“（対象，原因，効果）”のような事前に決定された形を有する。代替的に、受け付けた関係三連単語は、係り受け構文解析を使用して、センテンスのような入力テキストから抽出される。係り受け構文解析には、ここのその全体が引用されるLin,“Dependency-Based Evaluation of MINIPAR”in  Workshop on the Evaluation of Parsing Systemsに記述されている原則パラメータベース構文解析（“MINIPAR”）又は、単語間の関係を識別するあらゆる型式の語彙統語構文解析のような例がある。分散キャプチャ技術を使用することによって、コンピュータシステム１００は、様々なソースからデータを取得し、取得した関係データの数と型式を増加させる。
【００３０】
次に、コンピュータシステム１００は、受け付けた関係三連単語を使用して、センテンスのような追加テキストデータを収集し（ステップ２２０）、また、分散データ収集方法を使用して多くのソースからデータを収集する（ステップ２２０）。少なくとも１つの最初に受け付けた三連単語を含む追加データを入手するために、テキストデータが収集される（ステップ２２０）。例えば、１つの三連単語内の３つの単語すべてが、連続する１０語以内に存在するようなテキストデータが、分散ソース又はデータから収集される（ステップ２２０）。
ある実施形態においては、通信装置１５０は、訓練関係三連単語を提供したユーザ又はソースから追加テキストデータを収集する（ステップ２２０）。代替的に、最初に受け付けた関係三連単語は、三連単語成分を含むデータを、インターネット又はマルチユーザデータベース（例えばText Retrieval Conference corpus）のような多くのソースからのデータを含む他のソースから抽出するために使用される。
他の実施形態においては、追加テキストデータを収集する（ステップ２２０）ために、インターネットでのデータ取得と、ユーザによるデータ取得が組み合わせて使用される。
【００３１】
統語パターンが、収集されたテキストデータから抽出される（ステップ２３０）。ある実施形態においては、MINIPAR構文解析又は単語間の統語関係（主語、対象、述語）を識別し得る他の適当な語彙統語構文解析方法のような係り受け構文解析を使用して、テキストデータ内の単語間の統語関係を示す１つの係り受けツリーが生成される。例えば、係り受けツリーは、（カテゴリ、関係、カテゴリ）という形を使用して単語間の統語関係を示す。カテゴリは、単語を品詞（名詞、動詞等）に分類し、関係は、２つの単語間の有向統語関係（主語、対象等）を分類する。
ある実施形態においては、係り受けツリーは、追加関係データを識別することを可能とするために更に処理される。係り受けツリーと追加係り受けツリー処理の一例が、図３に沿って後記されている。係り受けツリーによって記述された統語関係が、収集されたテキストデータ内のセンテンス構造（例えば“if-then”、“when-then”）のような統語パターンを識別するために使用される。
【００３２】
次に、分散データソースが走査され（ステップ２４０）、抽出された統語パターンが、データソースから関係三連単語を抽出されるために使用される（ステップ２５０）。ある実施形態においては、係り受けツリー内の複数のパスが、テキストデータ内の関係を決定するために使用され、同じ統語パターンを有する関係三連単語を識別する。例えば、“if-then”構造を有しかつ少なくとも１つの訓練関連三連単語を含む分散データソースの中のセンテンスから、関係三連単語が抽出される（ステップ２５０）。
次に、抽出された三連単語の１つのサブセットが選択される（ステップ２６０）。ある実施形態においては、三連単語は、ユーザによって手動で選択される。代替的には、三連単語は、事前に決定された又は所定の判断基準を使用して自動的に選択される。他の実施形態においては、１つの三連単語のサブセットがランダムに選択される。
【００３３】
次に、教師付学習アルゴリズムが、選択された三連単語の有効性を決定する（ステップ２７０）ために使用される。例えば、学習アルゴリズムは、関係三連単語を統語パターンと関連付け、１つの関係三連単語が異なる統語パターンに出現する回数を示す。ある実施形態においては、ユーザが、統語パターンと関係三連単語との関連に基づき三連単語の有効性を手動で特定する。代替的に、所定の判断基準が、三連単語の有効性を自動的に決定する（ステップ２７０）ために使用される。
次に、選択された三連単語の有効データは、追加三連単語の有効性を自動的に決定できるように分類部を訓練する（ステップ２８０）ために使用される。ある実施形態においては、２値出力を伴う大規模疎データセット用高速ロバストロジスティック回帰（Fast    Robust Logistic Regression for Large Sparse Datasets with Binary Outputs）アルゴリズムのような疎２値ロジスティック回帰を使用して分類部が訓練される（ステップ２８０）。
次に、走査されたデータから抽出された（ステップ２５０）追加三連単語を分類する（ステップ２９０）ために、訓練された分類部が使用される。オプションとして、分類部の精度を決定するために、手動で関係データを分類した分類結果を比較することによって、分類部の性能が評価される。
【００３４】
このようにして、最初に供給された訓練三連単語は、統語パターンを生成するために使用されるセンテンスを収集するために使用される。生成された統語パターンは、マルチユーザデータベース、インターネット又は他のソースのような分散データソースから追加関係三連単語を抽出するために使用される。抽出された関係三連単語の１つのサブセットは、三連単語の有効性を決定できるように分類部を訓練するために選択され使用される。このことは、収集されたテキストから関係データを取得するための拡大縮小可能（scalable）な方法を提供する。
【００３５】
図３は、本発明のある実施形態に係る、テキストデータから統語パターンを抽出する（ステップ２３０）ための方法を示すフローチャートである。ある実施形態においては、３人称代名詞を解析するためにテキストデータが事前処理される（ステップ３１０）。このことは、識別され得る語彙パターンの数と型式を増加させる。
例えば、Lapain and Leass“An Algorithm for Pronominal Anaphora Resolution”   Computational Linguistic20(4):539-545に記述されているResolution of Anaphora     Procedure（ＲＡＰ）又は他の同様な技術のような照応解析プロセスが、３人称代名詞を解析し、統語照応形（anaphor）を解析し、かつ冗語的な代名詞を識別するために適用される。３人称代名詞を解析することによって、事前処理は、解析された代名詞に関連付けられた名詞を識別する。“When water is heated, it boils,”というセンテンス例は、事前処理（ステップ３１０）がどのように因果関係を識別するかを示している。
事前処理なしの場合、統語パターン抽出は、“water”と“heated”とが関係していること、そして、“it”と“boils”とが関連していることは識別しても、“water”と“it”との間の関係を発見できない。しかしながら、事前処理は、“water”と“it”との間の関係を識別し、（“water”，“heated”，“boils”）の完全な因果関係を検知できる。
【００３６】
次に、図２に沿って前記した係り受け構文解析を使用して、１つの係り受けツリーが事前処理されたテキストデータから生成される（ステップ３２０）。ある実施形態においては、係り受け構文解析は、単語を品詞毎に分類し、データ間の統語関係の型式毎に分類する。
ある実施形態においては、係り受けツリーは、もとの三連単語を削除することによって一般化される。他の実施形態においては、係り受けツリーの生成促進のため、識別された対象が名詞であり、かつ、識別された原因及び／又は効果が形容詞又は動詞であるように係り受けツリーを制限する。図４は、詳細は後記するが、“Boots that are heavy can  be uncomfortable”というセンテンスについて生成される（ステップ３２０）係り受けツリーの一例を示し、見本係り受けツリーの要素を識別する。
【００３７】
次に、テキストデータ内の追加リンクを識別するために、生成された係り受けツリーに対して衛星リンクが挿入される（ステップ３３０）。従来の係り受け構文解析は、センテンス中の基本語彙パスを示すが、基本係り受けパスに沿ったリンク以外のリンクを識別しない。このことは、１つのセンテンス内の単語間の統語関係を決定するために従来の構文解析技術が、“be”又は“is”のような一般語を使用することを防ぐ。衛星リンク挿入が追加統語関係の識別を可能とするのは、テキストデータ内であって、基本係り受けパス内ではない。図４に示される係り受けツリーの例は、“Boots that are heavy can be     uncomfortable”というセンテンス例についての係り受けツリーに対する衛星リンクの挿入を示している。
【００３８】
次に、生成された係り受けツリーに対して、三連単語の順序を記述したデータが挿入される（ステップ３４０）。１つの語彙パスが、異なる語順で同じ語を有する別々のデータからの三連単語に対応することがあり得るので、（効果，対象，原因）又は（原因，対象，効果）の形を有する三連単語のような語順が異なる三連単語を区別するために語順データが使用される。したがって、異なる語順で同じ語を有する別々の係り受けツリーの中で語彙パスが識別される場合は、語順データが類似の三連単語間の区別を行う。
【００３９】
図４は、本発明のある実施形態に係る、係り受けツリーの例４００を示す。例示目的のため、係り受けツリーの例は、“Boots that are heavy can be uncomfortable”というセンテンスを記述する。
【００４０】
係り受けツリーは、センテンスを有する単語を示すノード４１０を含む。リンク４２０は単語間の統語関係を示し、関係を記述するためにラベル付けされている。ある実施形態においては、リンク４２０は、“カテゴリ，関係，カテゴリ”という形の組（tuple）を使用してラベル付けされる。ここで、“カテゴリ”は品詞（例えば、名詞、動詞等）を示し、“関係”は、カテゴリ分けされた２つの単語間の有向統語関係（例えば、対象、主語、接続語等）を示す。
ある実施形態においては、名詞に対する“Ｎ”、動詞に対する“ＶＢＥ”、形容詞に対する“Ａ”、主語に対する“ｓ”、述語に対する“ｐｒｅｄ”及び他の適当な略語のような略語がカテゴリと関係を記述するために使用される。例えば、リンク４２０には“-Ｎ：ｓ：Ａ”がラベル付けされており、このラベルは、形容詞“heavy”は名詞“boots”を主語として有することを示している。
【００４１】
図４は、基本係り受けパス内のリンク以外のリンクを識別するために、係り受けツリー４００の基本語彙パスに対して追加する衛星リンク４３５、４３７を示している。図４の例では、基本語彙パス４３０は、“heavy”は“boot”を主語として有し、同様に      “uncomfortable”が“boot”を主語として有することを示している。
基本語彙パス４３０は、“boot”と“uncomfortable”を接続する最短のパスを含む。しかしながら、基本語彙パス４３０からは、“be”のような一般的な単語が１つのセンテンス内の複数の単語間の語彙関係を有益に示していることはわからない。衛星リンク４３５、４３７を追加することによって、エンドノードの直近に位置する追加単語が追加され、語彙関係の追加表示を提供する。
図４においては、“boots”と“be”の間の関係を記述する衛星リンク４３５が、係り受けツリーに追加されている。例えば、図４では、衛星リンク４３７は、名詞“boots”と、動詞“are”との間に、述語（“pred”）関係が有ることを示している。“be”は  “are”の活用前の見出し語であるので、“boots”と“be”の間の関係を示す衛星リンク４３５を追加することは、“boots”と“are”の間の関係を記述する衛星リンク４３７を追加することにもなる。
【００４２】
図５は、本発明のある実施形態に係る、分類部への入力データ例５００を示す。図５に示される例においては、分類部への入力データ５００は、別々の三連単語５２０Ａ−５２０Ｄ及び語彙パターン５１０を記述するテーブルを有する。しかしながら、図５に示されるテーブルフォーマットは一例であって、多くの実施形態においては、分類部への入力データ５００は、任意の適当なフォーマットを有する。
【００４３】
ある実施形態においては、分類部への入力データは、別々の三連単語５２０Ａ−５２０Ｄが各語彙パターン内に出現する頻度を示している。例えば、行５１２は、語彙パターン１を有するセンテンス内で三連単語１が０回発生し、語彙パターン１を有するセンテンス内で三連単語２が１回発生し、語彙パターン１を有するセンテンス内で三連単語３が１回発生することを示しており、同様に、別の三連単語が、語彙パターン１を有するセンテンス内で発生する頻度を示している。
【００４４】
分類部への入力データ５００は、三連単語有効性５３０を有する。この三連単語有効性は、バイナリな値を使用して各三連単語５２０Ａ−５２０Ｄの有効性を記述する。ある実施形態においては、三連単語有効性は、三連単語５２０Ａ−５２０Ｄ及び語彙パターン５１０の頻度データの評価に基づきユーザによって手動で特定される。代替的には、三連単語有効性は、三連単語５２０Ａ−５２０Ｄ及び語彙パターン５１０の頻度データを入力値として使用して、ソフトウエア処理又はファームウエア処理によって生成される。
【００４５】
ある実施形態においては、Komarek and Mooreに記述されている、２値出力を伴う大規模疎データセット用高速ロバストロジスティック回帰（Fast Robust Logistic          Regression for Large Sparse Datasets with Binary Outputs）アルゴリズムのような疎２値ロジスティック回帰は、分類部への入力５００データを使用して分類部が自動的に有効性を決定することを訓練する。故に、分類訓練後に受け付けた関係三連単語は、分類訓練の結果を使用して、有効であると自動的に分類される。
【図１】
2009539191.tif 000003
【図２】
2009539191.tif 000004
【図３】
2009539191.tif 000005
【図４】
2009539191.tif 000006
【図５】
2009539191.tif 000007
【国際調査報告】
2009539191.tif 000008