(57)【特許請求の範囲】
【請求項１】
コンピュータに規則帰納処理を実行させるためのプログラムであって、該規則帰納処理は、
分類されるべきノードを分類するために広い候補規則を選択するステップと、
候補規則を特殊化するステップであって、
（ｉ）特徴付けられるべきノードに対する親ノードレベル、子ノードレベル、及び兄弟ノードレベルのうちの少なくとも１つのノードレベルの構造化トレーニング例に対応するルールノードを追加し、
（ｉｉ）対応するノードレベルの少なくとも１つのノードの属性に関連する規則を前記追加したルールノードに含めて、特殊化された候補規則を作成し、
（ｉｉｉ）前記特殊化された候補規則を前記構造化トレーニング例のそれぞれに対して評価することで、
候補規則を特殊化する前記ステップと、
を含む、プログラム。
【請求項２】
前記規則を含めるステップが、前記ノードレベルの各ラベルに対応する属性−値候補規則を前記追加したルールノードに含めるステップを含む、請求項１記載のプログラム。
【請求項３】
前記規則を含めるステップが、前記ノードレベルのノードのＩＤまたはＩＤＲＥＦ属性の各値に対応する属性−値規則の論理積を前記追加したルールノードに含めるステップを含む、請求項１又は２に記載のプログラム。
【請求項４】
前記特殊化された候補規則が満足のいくものになるかまたは予め選択した最大数のノードを有するまで、前記ルールノードを追加するステップと前記規則を含めるステップを繰り返すステップをさらに含む、請求項１〜３のいずれか１項に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
以下は、データ分類、データマイニングそして関連技術に関する。特に、構造化ＸＭＬデータに適用される規則（ルール）帰納に関し、これを特に参照して本明細書中で説明する。しかしながら、以下を他の同様のアプリケーションのために修正可能である。
【背景技術】
【０００２】
規則帰納は、予測規則の自動決定を要する。典型的には、規則を学習するためにトレーニングデータセットを使用する。トレーニングセットにおける各例は、その値または値の範囲が予測される注目の属性を含む属性(例えば、ブール属性、離散属性または連続属性)の値のセットによって記述される。規則は、特定された他の属性が特定の値または範囲を有するときに注目の属性が特定の値または値の範囲を有するであろうことを予測するトレーニングセットに基づいて構成される。
【０００３】
例えば、人物を列挙したトレーニングセットは、それぞれが属性Ｆ３、Ｆ４、Ｆ６そしてＦ１０を含めた属性を有する例を含むことができる。ここで、Ｆ３は最高到達教育レベルを示し、Ｆ４は教育の年数を示し、Ｆ６は職種を示し、Ｆ１０は給与レベルを示す。導かれる規則は、ある人物が＄５０，０００より高い収入レベルを有する場合を予測することが意図される。導かれ得るある１つの規則は、以下の通りである。
【数１】
0005226198.tif 000002
【０００４】
１つの方法では、一般的なまたは広い初期候補規則を特殊化によって絞り込んで、最終的な規則を作成する。例えば、初期候補規則はトレーニングセットの全ての例に対してあてはまる空の規則であるかもしれない。属性−値対を論理積的に追加して、予測精度の閾値レベルを有する規則などの選択した終了基準に到達するまで、規則を特殊化する。このプロセスを繰り返して、それぞれが属性−値対の論理積的組み合わせである規則のセットを作成することができる。
【０００５】
これまで規則帰納は一般に、各例が属性−値対のセットによって定義されるフラットデータに適用されてきた。こういった規則帰納を構造化データに適用するのは難しい。例えば、拡張マークアップ言語（ＸＭＬ）、ハイパーテキストマークアップ言語（ＨＴＭＬ）、そして他の構造化形式は、データが木状構造で編成される構造を提供する。例えばＸＭＬドキュメントは、「ドキュメント（"document"）」として定義されたルートノードを有し、このルートノードが「序文（"introduction"）」、「第１章（"chapter 1"）」、「第２章（"chapter 2"）」・・・「結論（"conclusions"）」などのそのドキュメントのセクションに対応する子ノードを有することができる。各子ノードはそれぞれ自身の子ノードを有することができる。例えば、各章ノードは段落などに対応する子ノードを有することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
構造化データに適用される規則帰納方法を提供する。
【課題を解決するための手段】
【０００７】
本明細書中に例示した態様によると、規則帰納方法が提供される。分類されるべきノードを分類するために、広い候補規則が選択される。この候補規則は、（ｉ）ＸＭＬ構造インタフェースを使用して新しいノードを追加し、（ｉｉ）新しい属性をノードに追加し、（ｉｉｉ）特殊化された候補規則をトレーニング例のセットのそれぞれに対して評価し、（ｉｖ）特殊化された候補規則が終了基準を満たしたときに特殊化を終了することで、特殊化される。
【０００８】
本明細書中に例示した態様によると、規則帰納システムが提供される。一般−特殊化規則インデューサが、広い候補規則をトレーニングＸＭＬドキュメントのセットのそれぞれに対して特殊化することで、ＸＭＬドキュメントの分類されるべきノードを分類する規則を生成する。一般−特殊化規則インデューサは、ノードと属性を候補規則に選択的に追加するルール（規則）ノードアダーを含む。
【０００９】
本明細書中に例示した態様によると、規則帰納方法が提供される。分類されるべきノードを分類するために、広い候補規則が選択される。この候補規則は、（ｉ）あるノードレベルの構造化トレーニング例に対応するルールノードを追加し、（ｉｉ）対応するノードレベルの少なくとも１つのノードの属性をルールノードに含めて特殊化された候補規則を作成し、（ｉｉｉ）特殊化された候補規則を構造化トレーニング例それぞれに対して評価することで、特殊化される。
【００１０】
本明細書中に例示した態様によると、分類されるべきノードを分類するために広い候補規則を選択するステップと、候補規則を特殊化するステップとを含む規則帰納方法が提供される。候補規則を特殊化するステップは、（ｉ）あるノードレベルの構造化トレーニング例に対応するルールノードを追加し、（ｉｉ）対応するノードレベルの少なくとも１つのノードの属性に関連する規則を、前記追加したルールノードに含めて特殊化された候補規則を作成し、（ｉｉｉ）前記特殊化された候補規則を前記構造化トレーニング例のそれぞれに対して評価することで、候補規則を特殊化する。
【発明を実施するための最良の形態】
【００１１】
図１を参照すると、規則帰納システム１０は、ＸＰａｔｈまたはドキュメントオブジェクトモデル（ＤＯＭ）インタフェースなどの適当なＸＭＬ構造インタフェース１４を介してアクセス可能なトレーニングドキュメントのセット１２に基づいて、広い初期規則を特殊化することで、分類規則を生成する。
【００１２】
プリプロセッサ２０はオプションで、トレーニングドキュメント１２を処理して規則帰納にとって注目のノードの属性を定義し、規則帰納にとって注目のコンテンツを抽出するさらなるセグメント化ノードを定義する。自然言語処理のアプリケーションでは、例えば、各コンテンツストリーム（＃ＰＣＤＡＴＡ）はＸｅｒｏｘ  Ｉｎｃｒｅｍｅｎｔａｌ  Ｐａｒｓｅｒ（ＸＩＰ）などの言語ツールを使用して、トークンに適当にセグメント化される。これについては、例えば本明細書中に参照によって援用されるAitMokhtar et al., "Robustness beyond Shallowness: Incremental Deep Parsing, in Journal of Natural Language Engineering, Special Issue on Robust Methods in Analysis of Natural Language Data, ed. A. Ballim & V. Pallotta (Cambridge University Press, 2002)や、こちらも本明細書中に参照によって援用されるAitMokhtar, Incremental FiniteState Parsing, Proceedings of Applied Natural Language Processing (ANLP97), Washington, D.C. April 1997に記載されている。或いは、このセグメント化にトークナイザを使用することもできる。セパレータのリストが、十分なセグメント化を成すことができる。各トークンに対して、新しいノードが特定の属性を有する構造に付加される。（その目的が例えばインスタンスの形態構造を学習することであるならば）各トークンを文字などのより小さな単位に分割することもできる。新しいノード（単語または文字）それぞれを属性で強化することができる。例えば各「単語（word）」ノードを、その品詞（名詞（noun）、動詞（verb）、前置詞（preposition）などの言語学上の分類）、標準型、特定の用語データベースでの存在などで強化することができる。同様に、各「文字（letter）」要素を、「母音（vowel）」、「子音（consonant）」、「大文字（capital letter）」などの属性で強化することができる。
【００１３】
図２は、この前処理の例示的な出力を示す。この前処理は、元のドキュメントの構造を維持し、例示の文字葉などの新しい葉および／または例示の「外観（surface）」、「品詞（pos (part of speech)）」、「見出し語（lemme）」属性などの新しいノード属性を付加する。パーサなどの言語ツールを前処理に使用すると、ＩＤＲＥＦ属性を使用して説明される言語要素間の言語学上の依存などの、より優れた言語情報を統合することができる。学習タスクに応じて、他の前処理ステップをコンテンツ要素に適用することができる。例えばドキュメント分類の場合、＃ＰＣＤＡＴＡノードを、＃ＰＣＤＡＴＡで見られる単語または見出し語のセットのノードに置き換えることができる。これは、ドキュメント分類で通常使用される典型的なバッグオブワーズ（ｂａｇ−ｏｆ−ｗｏｒｄｓ）表示に対応する前処理である。ドキュメントがタイトル、セクション、パラグラフなどで構成されるならば、この構造を保持できる。
【００１４】
トレーニングドキュメントのセット１２が最初ＸＭＬ形式でないならば、プリプロセッサ２０がトレーニングドキュメントをＸＭＬ形式に適当に変換する。データベースなどの構造化データは、簡単にＸＭＬ形式に変換される。ＵＣＩデータベースなどの機械学習で使用される典型的なベンチマークは＜属性−値＞形式を利用し、これも簡単にＸＭＬに変換できる。例えば、以下のような＜属性−値＞形式の例は、
【数２】
0005226198.tif 000003
以下にしたがって適当にＸＭＬに変換される。
【数３】
0005226198.tif 000004
こういった例を多く含む（のが通例である）トレーニングセットの場合、各例は＜ＥＸ／＞の例示のマークアップを使用して＜ＤＡＴＡ＞＜／ＤＡＴＡ＞マークアップ対内に同様に配置される。
【００１５】
オプションの前処理後、初期候補規則セレクタ２２が、分類されるべきノードを分類するために広い初期候補規則を選択する。例えば、広い初期候補規則を生成するために、関数buildEmptyRule()を使用できる。カテゴリーGUIDENAMEのためにbuildEmptyRule()関数によって構成された適当な広い初期規則は以下のようになる。
【数４】
0005226198.tif 000005
ここで属性ＴＢＣは、この規則によって分類される構造化要素またはノードを示す（「ＴＢＣ」は、「Ｔｏ  Ｂｅ  Ｃａｔｅｇｏｒｉｚｅｄ」を意味する）。広い初期規則は、以下のような適当な学習アルゴリズムを使用して特殊化される。
【数５】
0005226198.tif 000006
ここで、関数learnSetOfRuleは以下によって与えられる。
【数６】
0005226198.tif 000007
ここで、関数specializeRule()は以下によって与えられる。
【数７】
0005226198.tif 000008
関数addNewNode()は以下によって与えられる。
【数８】
0005226198.tif 000009
そして、関数addNewAttribute()は以下によって与えられる。
【数９】
0005226198.tif 000010
上に説明したアルゴリズムは、ＡＬＬｉＳで適当に実施され、これについては、例えばDejean, "Learning Rules and Their Exceptions", Journal of Machine Learning Research vol. 2, pp. 66993 (2002)やDejean, "ALLiS: a Symbolic Learning System for Natural Language Learning", in Proceedings of CoNLL2000, Lisbon, Portugal (2000) pp. 9598に記載されており、どちらも本明細書中に参照として援用される。或いは、こういったアルゴリズムは、Ｐｒｏｌｏｇなどの規則帰納を実施するのに適した他のシステムを使用して実施することもできる。例示のlearnSetOfRule()関数は、一般−特殊学習方法を実施する。決定木アルゴリズムなどの特殊化動作を含む他の学習機能を使用することもできる。
【００１６】
続けて図１を参照すると、evaluation()関数は候補規則エバリュエータ２６の役目を果たし、規則のスコアを計算するために種々の方法で実施可能である。精度、ラプラス推定、ｍ−推定、情報ゲインなどをスコアリング基準として使用できる。決定オペレータ３０では、候補規則のスコアが閾値θ以上ならば、帰納規則コレクタ３２が候補規則を規則のセットに入れる。そうでなければ、specializeRule()関数を使用して新しい情報を付加することで特殊化される。
【００１７】
続けて図１を参照すると、specializeRule()関数は、候補規則を特殊化し新しい候補規則のセットを候補リストに追加する規則スペシャライザ４０の役目を果たす。新しい情報は、例えばトレーニング例を記述する属性−値対に対応する。属性−値対は、addNewAttribute()関数４２によって追加される。より一般的には、規則スペシャライザ４０は、ＸＭＬトレーニングデータ１２によって提供される実質的にあらゆる種類の情報を追加することで候補規則を特殊化することができる。この一般化された能力は、例示のaddNewNode()関数４４などのルールノードアダーによってもたらされる。ＩＤまたはＩＤＲＥＦに対応する情報の追加によって規則が特殊化されると、得られる規則は木ではなく、構造化規則を記述する森になる。
【００１８】
規則特殊化は、終了基準が満たされるまで行われる。この終了基準には、例えば、トレーニングデータにおける候補規則の頻度が所与の閾値に達したときに特殊化を終了する決定オペレータ３０が含まれる。さらに、または或いは、別の決定オペレータ４８が、規則が最大数の要素（ノードおよび属性）、最大数のノードなどを有したときに候補規則の特殊化を終了してもよい。この場合、規則候補は捨てられる（５２）。終了基準閾値および決定オペレータ４８の最大の複雑度が、適当なユーザ選択可能パラメータである。
【００１９】
規則スペシャライザ４０は、新しい属性と属性の種類に依存する新しい値を有する新しい候補規則を生成する。表１は、規則スペシャライザ４０が種々のノードの追加によってどのようにして候補規則を特殊化するかを概説する。
【００２０】
【表１】
0005226198.tif 000011
表２は、規則スペシャライザ４０が種々の属性の追加によってどのようにして候補規則を特殊化するかを概説する。
【００２１】
【表２】
0005226198.tif 000012
より特殊化された候補規則を作成するために追加される新しい要素に関する情報は、Ｘｐａｔｈ、ＤＯＭまたは他の構造インタフェース１４を介してトレーニングデータ１２に問合せを行うことによって収集される。
【００２２】
一例として、広い初期候補規則から始める。
【数１０】
0005226198.tif 000013
以下のリストは、特殊化によって適切に作成される幾つかの新しい候補の例を示す。
【数１１】
0005226198.tif 000014
新しい候補はそれぞれ候補規則エバリュエータ２６によって評価され、そのスコアが決定オペレーション３０によって判定されたときに十分高くない場合は、その新しい候補規則は、決定オペレータ４８が指定した最大の複雑度まで規則スペシャライザ４０によってさらに特殊化される。
【００２３】
以下は、図１の規則帰納システム１０によって適切に生成された、複数のルールノードを含む構造化規則の一例である。
【数１２】
0005226198.tif 000015
この規則では、「コンテンツ（"content"）」のコンテキスト（単語「Ｇｕｉｄｅ」に続く）において、また比較的複雑な構造のコンテキストにおいて何らかの特定の属性（大文字）を有する単語（属性ＴＢＣを有する要素ＮＯＤＥ）は、所与のカテゴリー（Ｇｕｉｄｅ  Ｎａｍｅ）に分類される。
【００２４】
ＩＤおよびＩＤＲＥＦ属性によって、変数を規則形式に導入することができる。ＸＭＬでは、タイプＩＤＲＥＦはノード要素の固有の識別子であるＩＤを指す。ＸＭＬにおけるＩＤ／ＩＤＲＥＦ属性の使用例は以下の通りである。
【数１３】
0005226198.tif 000016
ここで、パラメータＰＡＲ１およびＰＡＲ２はＩＤＲＥＦ属性で、ＩＤはＩＤ属性である。
【００２５】
規則帰納の際のＩＤ／ＩＤＲＥＦ属性に対する適当な処理は以下の通りである。タイプＩＤＲＥＦまたはＩＤの属性が規則に追加される。本例では、タイプＩＤ＝“＿３”の属性が以下のように追加される。
【数１４】
0005226198.tif 000017
参照要素のリストが収集される（ＩＤのためのＩＤＲＥＦまたはＩＤＲＥＦのためのＩＤ）。本例では、ＩＤ＝“＿３”の参照要素は以下の通りである。
【数１５】
0005226198.tif 000018
各参照要素に対して、論理積規則がＩＤ／ＩＤＲＥＦ属性と共に追加される。
【数１６】
0005226198.tif 000019
追加された新しい規則は、規則スペシャライザ４０によって他の規則と同様に特殊化される。
【数１７】
0005226198.tif 000020
ＩＤ／ＩＤＲＥＦ属性の値を変数に置き換える（存在量化）。典型的には、第１の変数を「＿Ｘ１」、第２の変数を「＿Ｘ２」などとする。こういった変数のリストを候補の頭に追加する。全称記号が各変数に潜在的に関連付けられる。新しい候補が候補リストに追加される。ＩＤ／ＩＤＲＥＦ処理では、学習済みの規則はもはや木ではなく森であり、そこでは１本の木の枝が別の木の枝に連結している。
【００２６】
変数ＩＤＲＥＦのＡＬＬｉＳ形式における規則の一例は、以下の通りである。
【数１８】
0005226198.tif 000021
この規則は、３つの論理積部分（ＴＲＥＥ要素）と２つの変数＿Ｘ１および＿Ｘ２からなる。この規則は、動詞「ｅｎｃｏｄｅ」の主語である単語「ｇｅｎｅ」に続く単語は、ＢＩＯＥＮＴＩＴＹカテゴリーに属する、と解釈できる。
【００２７】
本明細書中に開示した規則帰納システムの実施形態を、幾つかのコレクションでテストしてきた。１つのテストでは、欧州特許庁によって提供されたドキュメントの参考文献一覧部分を構成することが目的であった。そこでの問題は、構造的ＸＭＬ要素を分類することであった。コンテンツの使用ありとなしの場合の評価を表３に示す。
【００２８】
【表３】
0005226198.tif 000022
表３では、Ｆ１−スコアは調和平均を示す。別のテストでは、ゼロックスコーポレーションが開発したバイオインフォマティックスコンテンツのＢｉｏＴＩＰ（商標）コレクションを利用し、ＢｉｏＴＩＰ（商標）コレクションの記事の要約にある遺伝子、タンパク質、ＲＮＡなどの生物学的エンティティにタグを付けることが目的であった。評価を表４に示す。
【００２９】
【表４】
0005226198.tif 000023
この試験から、構造情報とコンテンツ情報の組み合わせが規則のセットの予測性能を向上させることができる、ということが分かる。適合率が僅かに低下すると（−１．５％）、再現率が＋６．５％向上し、Ｆ１（調和平均）が＋３％向上する。
【図面の簡単な説明】
【００３０】
【図１】ＸＭＬデータに作用し、分類されるべきノード以外のノードに対応するルールノードを含む構造化規則を生成可能な規則帰納システムを概略的に示す。
【図２】前処理された例示的なＸＭＬトレーニングドキュメントの構造を概略的に示す。
【図１】
0005226198.tif 000024
【図２】
0005226198.tif 000025