(57)【要約】本発明の学習システムにはテンプレート・オートマトンの概念が導入されており、「正しい」回答と「誤った」回答からなる多くの「多様な学習者の予想される例」を収集し、効率的なエラー診断エンジンとしてＨＣＳ（最重共通文字列）またはＬＣＳ（最長共通文字列）アルゴリズム等の代表的なＮＬＰ技術を言語学習システムに用い、テンプレート内に埋め込まれたこれらの例を学習者の回答の診断解析のために用いる。この診断は、テンプレートデータベースの膨大な数の候補パスの中から学習者の入力文に最も近似度の高いパスを選択することによって行われる。言語指向インテリジェント学習システムに使用される時間の掛かるオーサリング・タスクの自動化と簡素化が実現される。
2004084156.tif 000002
【特許請求の範囲】
【請求項１】
抽出ルール・ベースのテンプレート−テンプレート構造およびバギー・ルールの拡張性を用いた対話式学習システムにおいて、テンプレート−テンプレート構造内のノードのいくつかが、多くのテンプレートまたはいわゆる大きいテンプレートに抽出することができる抽出ルールに関連付けられたシンボルでマーク付けされるテンプレート−テンプレート構造を用いた対話式学習システム。
【請求項２】
展開テンプレートのノードのいくつかに抽出ルールに関連付けられた特別なシンボルが割り当てられており、これによってテンプレートの１つまたは複数を抽出することができるようになされたテンプレート−テンプレート・スキームを用いる請求項１記載の対話式学習システム。
【請求項３】
単一テンプレート−テンプレートから複数のテンプレートを抽出するためにテンプレート−テンプレート内のノードをマーク付けするために使用される抽出ルール基く請求項１記載の対話式学習システム。
【請求項４】
スリムなテンプレート−テンプレートをより大きなテンプレート−テンプレートまたはよりファットなテンプレート−テンプレートに展開するために用いられるバギー・ルール基く請求項１記載の対話式学習システム。
【請求項５】
前記抽出ルールが常に一組のシンボル、すなわち｛ｓ１，ｓ２，．．．，ｓｎ｝に関連付けられ、このシンボルのそれぞれはテンプレートの１つまたは複数のノードに割り当てられ、これらの関連付けられたシンボルには１つまたは複数の値が割り当てられてなる抽出ルール基く請求項１記載の対話式学習システム。
【請求項６】
入力文を抽出ルールが埋め込まれたテンプレート−テンプレートと照合するためのＨＣＳマッチング・アルゴリズムを用いる請求項１記載の対話式学習システム。
【発明の詳細な説明】
【技術分野】  本発明は、抽出ルール・ベースのテンプレート−テンプレート構造およびバギー・ルールの拡張性に富む機能を利用した新しい対話式学習システムに関する。
【背景技術】  言語指向インテリジェント学習システムに使用される時間の掛かるオーサリング・タスクの自動化と簡素化が切望されていることが発明の動機となっている。想定される模範回答数は合理的に制限するとしても、理想的な学習システムを開発しようとする場合、学習者が実際に犯す可能性のあるエラーは理論的には無限個に近い数にのぼる場合がしばしばあるからである。本発明者らが判断する限り、少なくとも予見できる将来においては、最先端の自然言語処理技術をもってしても、完全な自由形式でしかもエラーの多い文章の自動訂正を即座に提供出来るレベルには達していない。多くの有能な人間教師のようにシステムがこのような対処ができるには、いわゆる常識と呼ばれる世界の知識ベースをこのシステムに導入することができる場合にのみ可能であろう。
【発明の開示】
本発明の学習システム（Ａｚａｌｅａ）にはテンプレート・オートマトンの概念が導入されており、「正しい」回答と「誤った」回答からなる多くの「多様な学習者の予想される例」を収集する。言語学習システムで使われる効率的なエラー診断エンジンとしてＨＣＳ（最重共通文字列）またはＬＣＳ（最長共通文字列）アルゴリズムという代表的なＮＬＰ技術が決定的な役割を担っており、テンプレート内に埋め込まれたこれらの例は学習者の回答の診断解析のために使用される。この診断は、テンプレート・データベースの膨大な数の候補パスの中から学習者の入力文に最も近似度の高いパスを選択することによって行われる。適格なモデル翻訳文と不適格な誤った文章から構成されるテンプレート・コーパスを構築するオーサリング・タスクは、多くの時間を費やし、人手を浪費させる。
本発明の新しいシステムには、通常であれば時間の掛かるテンプレート生成のオーサリング・タスクを簡素化、すなわち低減することにおいてのみならず（徳田  尚之、陳  亮、笹井  紘幸らによる特開２００２−４９６１７号等を参照のこと）、システム性能の向上においても有効である。導入されたテンプレート−テンプレート・アーキテクチャがシステムの簡素化と性能の向上をもたらす第１の理由は、このアーキテクチャが、単一のテンプレート−テンプレートの遷移ノードのいくつかに割り当てられた抽出ルールを適用することによって、単一のテンプレート−テンプレートに多くの異なるテンプレートを統合したり、また逆にいうとそこから多くの異なるテンプレートを同様に抽出することが可能になることであり、第２の理由は、導入されたバギー・ルールが学習者の誤った回答を自動的に識別・分類し、したがってそこからバグを生成する機能を有することである。ＮＬＰ（自然言語処理）技術がこのシステム開発で主要な役割を担う理由は、学習者の自由形式回答の構文構造を調べるためにはパーサが使用されるており、その意味論的構造は、学習者からの回答を準備されたテンプレート・データベースの意味論的に等価のパスとの文字列照合により調べることから明らかであろう。
新しい抽出ルール・ベースの、またバギー・ルール・ベースのテンプレート−テンプレート構造は、文字入力および会話方式による学習システム、音声利用技術によるコール・センターまたは音声ポータル・システム、あるいはシステムと人間との間でより自然な人間とコンピュータの対話を実施するより強化されたヒューマン・コンピュータ・インターフェースに焦点を合わせたシステムならばどのシステムをも含めて多くのアプリケーションで重要な役割を担うことが期待される。
この発明では以下のような機能が与えられる。
１．ある制約条件の下で選択したテンプレート−テンプレート遷移図のノードに抽出ルールを埋め込むと、単一テンプレート−テンプレートは様々な異なるタイプの既存のテンプレートを表現することができる。
２．導入されたバギー・ルールの拡張力に富む機能を利用することによって、多くの誤り表現および／または多くの誤った構文構造は、バグ分類学を記述するその自動機能によって、新しいテンプレート−テンプレートを「よりファットな」テンプレート−テンプレート形式に展開できるように整合性を保って自動的に記述することができる。語学教師は、テンプレート−テンプレートを制作する際に誤った翻訳文の分類に費やす必要はなく、したがってエラー分類学の負担を低減し、学習者らの特定のエラーの特徴を評価しクラスタ化する。
３．ＨＣＳマッチング・アルゴリズムは、入力文をより簡素なテンプレート−テンプレートに直接照合し、したがって実際にテンプレート−テンプレートを展開せずにすべての抽出されたテンプレートのすべての予想されるパスから最適なパスを探索する際の照合処理の空間および時間計算量を低減するように開発することができる。
【発明を実施するための最良の形態】テンプレート−テンプレート構造
まず「テンプレート−テンプレート」という用語を以下の様に定義する。テンプレート−テンプレートは、ノードのいくつかが抽出ルールに関連付けられたシンボルでマーク付けされており、そのテンプレート−テンプレートが多くのテンプレート、または一組の非連結型テンプレートが１つのテンプレートとみなされる場合はいわゆる大きいテンプレートに展開することができる場合の特別なテンプレートと定義される。このような一組の切断されたテンプレートによって、単一のＬ１文章の様々な予想される翻訳文は、一群の翻訳されたＬ２文章から構成される大きな単一のテンプレート−テンプレートを形成することが可能になる。展開テンプレートであるので、テンプレート−テンプレート・スキームによってテンプレート−テンプレートはいわば１つまたは複数のテンプレートを抽出することが可能になる。
通常、抽出ルールは常に一組のシンボル、例えば｛ｓ１，ｓ２，．．．，ｓｎ｝に関連付けられており、そのシンボルのそれぞれにはテンプレートの１つまたは複数のノードが割り当てられている。それらの関連付けられたシンボルには１つまたは複数の値が割り当てられており、その機能は、テンプレート−テンプレートから抽出された１つ以上のテンプレートに現れるノードのスタイルを表現することである。本発明ではこれらのシンボルを「ラベル・シンボル」と呼ぶ。単一ルールに関係付けられたシンボルは「関係シンボル」と呼ばれる。関係シンボルはある種の制約を有するべきである。一般的な制約としては、所与のｓｉ＝１に際して，ｓｋはしばしば２に制約されるか、あるいは１以外のいくつかの正の整数に制約される必要がある。ｓｉの値が一組の他のシンボルに割り当てられた値に依存する場合、ｓｉの値の選択は他のシンボルの必須選択肢と呼ばれる。
語学教師が容易に理解できるように抽出ルールのいくつかの例を以下に示す。
タイプＡルール  ＡＰ（出現）−ＮＡＰ（非出現）ルール
ノードによってＡＰｉでマーク付けされているノードと、ＮＡＰｉでマーク付けされているノードがあると想定する（ｉは任意の整数で別のタイプのＡルールを示す）。タイプＡルールのＡＰ−ＮＡＰルールは、展開された時に新たに展開されたテンプレートはＡｐｉでマーク付けされたノードかまたはＮＡＰｉでマーク付けされたノードを含むことができるが、これらの両方を同時に含むことはできないという条件を課す。本発明においては、ＡＰｉでマーク付けされたノードがテンプレートに現れないという場合を示すためにＡＰｉ＝０を使用する。この時、ＮＡＰｉは、ＮＡＰｉでマーク付けされたノードがそのテンプレートに現れるであろうことを意味する１である必要がある。したがって本発明ではＮＡＰｉ＝１はＡＰｉ＝０の必須選択肢であると言うことができる。同様の理由から、ＮＡＰｉ＝０の場合、ＮＡＰｉ＝０がＡＰｉ＝１の必須選択肢となるように、ＡＰｉは１の値を有する必要がある。
タイプＢルール  ＰＰＲ（人称代名詞）−ＰＰＲＰ（人称代名詞所有格）ルール
タイプＡルールと同様に、テンプレート−テンプレート・ルールは、一組のテンプレートに現れるＰＰＲｉでマーク付けされたノードとＰＰＲＰｉでマーク付けされた他のノード（ｉは任意の整数）は、それぞれに代名詞の自然言語文法が必要とする人称代名詞のフォームと代名詞の人称代名詞所有格のフォームでなければならないという条件を課す。ＰＰＲＰｉ（またはＰＰＲｉ）の場合、ＰＰＲｉ（またはＰＰＲＰｉ）に要求される値は代名詞の自然言語文法によって定義される必要がある。
タイプＣルール  ＡＮ（任意数）ルール
タイプＣルールは、ＡＮｉでマーク付けされたノードには任意のポジティブな実数を割り当てることができるという条件を課す。「Ｉ  ｈａｖｅ  ５  ｂｏｏｋｓ  ｏｎ  Ｚｅｎ」が真ならば、５以外の数はどの数も誤りなので、このルールＡＮｉはエラー・ノード５に割り当てることができる。
タイプＤルール  ＣＨＯ（択一）ルール
タイプＤルールは、ＣＨＯｉ１，ＣＨＯｉ２，．．．，ＣＨＯｉｋでマーク付けされたテンプレート−テンプレートのすべてのノードの中で、テンプレート−テンプレートから抽出されたどのテンプレートにもただ一組だけのノードしか現れることができないという条件を課す。ここで異なるｉは異なるタイプＤルールを表している。したがって、ＣＨＯｉｊ＝０はＣＨＯｉｊでマーク付けされたノードは現れないことを意味し、ＣＨＯｉｊ＝１はその指定されたノードが現在現れていることを意味している。明らかに、１が１つのＣＨＯｉｋ，に割り当てられている場合、０は他のすべてのＣＨＯｉｊに割り当てられるべきである。
テンプレート−テンプレートを拡張するためのバギー・ルール
ここでいうバギー・ルールは、正確な構文規則からの予想される逸脱によって特徴付けられる一般的な構文上の誤り表現のプロダクション・ルールと定義される。具体的に、バギー・ルールの以下のフォームを想定する。
Ｈ１Ｈ２．．．ＨＮ→Ｒ１Ｒ２．．．ＲＭ
ここでＨ１Ｈ２．．．ＨＮは任意のテンプレート−テンプレートの構文上正確なパスを追跡する一組のノードまたは正確な表現の基本的な構成要素またはセグメントを表す一組の文法的な品詞タグを表す。Ｒ１Ｒ２．．．ＲＭは、正確なフォームがＨ１Ｈ２．．．ＨＮである典型的誤り表現を表すノードのセットである。エラーがテンプレート−テンプレートの正確なパスからのずれによって識別されることが即座に理解される。一例を示す。
ＥＸ  ＶＢＰ→ＥＸ  ＶＢＺ
（ここでＥＸは「ｔｈｅｒｅ  ｉｓ」（〜がある）というような存在を表すものであり、ＶＢＰは１人称および２人称の現在形の動詞であり、ＶＢＺは３人称単数現在形の動詞である）。この例は、構文上正確な表現である「ｔｈｅｒｅ  ａｒｅ  ５  ｂｏｏｋｓ」が、主語と動詞の属性一致を誤って理解している生徒によって誤用されており、この例では誤り表現である「ｔｈｅｒｅ  ｉｓ  ５  ｂｏｏｋｓ」が生じたことを意味している。
【図面の簡単な説明】  図１は本発明のテンプレート−テンプレートの構造を示す図である。
図２は展開ルールにより展開されたテンプレート−テンプレート構造を示す図である。
図３は「Ｊａｐａｎ  ｉｓ  ｄｏｔｔｅｄ  ｗｉｔｈ  ｂｅａｕｔｉｆｕｌ  ｐａｒｋｓ  ｎａｔｉｏｎｗｉｄｅ」という意味の文章の例で展開されたテンプレート１を示す図である。
図４は「Ｊａｐａｎ  ｉｓ  ｄｏｔｔｅｄ  ｗｉｔｈ  ｂｅａｕｔｉｆｕｌ  ｐａｒｋｓ  ｎａｔｉｏｎｗｉｄｅ」という意味の文章の例で展開されたテンプレートを示す図である。
【符号の説明】
エラー・メッセージ：
ＡＳ：名詞の量に仮定が行われている、
ＡＴ：冠詞は必要ない、
ＣＭ：コンマが必要である、
ＣＴ：短縮形が不正確である、
ＭＮ：意味が不正確である、
ＮＰ：名詞は複数形でなければならない、
ＶＳ：主語が単数形なので動詞は単数形でなければならない、
ＰＲ：前置詞が不正確である、
ＰＰ：句は複数形である必要がある、
一般的な品詞タグ：
ＤＴ：限定詞                        ＥＸ：存在を表す
ＩＮ：前置詞／従属接続詞            ＪＪ：形容詞
ＮＮ：名詞、単数または集合          ＮＮＳ：名詞、複数
ＮＮＰ：固有名詞、単数              ＲＢ：副詞
ＶＢＮ：動詞、過去分詞              ＶＢＰ：動詞、非３人称単数、現在形
ＶＢＺ：動詞、３人称単数、現在形
以下本発明を図面に示す具体例によって説明する。
図１はオリジナルなテンプレート−テンプレートの構成を示す図であり、図２は上記の展開ルールにより展開されたテンプレート−テンプレートを示す図、図３はテンプレート１を示す図であり、図４はテンプレート２を示す図である。
テンプレート−テンプレート、抽出ルールによるテンプレート拡張、およびバギー・ルールの例
本発明の実施例においては、まず「Ｊａｐａｎ  ｉｓ  ｄｏｔｔｅｄ  ｗｉｔｈ  ｂｅａｕｔｉｆｕｌ  ｇａｒｄｅｎｓ  ｎａｔｉｏｎｗｉｄｅ．」という意味の日本語の文章の英語への翻訳文に関するテンプレート−テンプレートを構築する。図１等に示される番号は、文中における各単語の相対的重要性を強調する各単語の重みを示している。テンプレートの単語のデフォルトの重みは１にセットされており、これらはこの分野の専門家によって判断されるその単語の重要性に関連付けて割り当てられる必要がある。徳田  尚之、陳  亮、笹井  紘幸による特開２００２−４９６１７号を詳細な説明のために参照する。「［」と「］」の間のシンボルは品詞タグである。図中左端に示すノードは開始ノードである。
前記バギー・ルールを単純に適用することによって、それを図２のテンプレート−テンプレートに展開することができる。
これは、前記のバギー・ルールがバグの分類法を生成することができ、それによってそれらの誤り表現をテンプレート−テンプレートに構築することを自動的に可能にするので、語学教師がテンプレート−テンプレートを構築する際に多くの一般的なエラーを分類することの詳細に配慮する必要はないということを示している。
次に、前記タイプＡルールを適用すると、ＡＰ１でマーク付けされたノードがそのテンプレートに現れることを可能にし、したがって図２のＮＡＰ１でマーク付けされたノードを削除することによって図２のテンプレート−テンプレートから図３のテンプレート１を抽出し、ならびに図２のＡＰ１でマーク付けされたノードを削除し、したがってＮＡＰ１でマーク付けされたノードがそのテンプレートに現れるようにすることによって図４のテンプレート２を抽出することができることが容易に分かる。
語学教師がより簡素なラベル・シンボルに関してテンプレートの１つの大きな組み合わせを完成させてテンプレート−テンプレートを構築することができることが理解される。
テンプレート−テンプレートおよび入力文に対する最重共通文字列マッチング・アルゴリズム
前記の詳細な説明から明らかなように、単一テンプレート−テンプレートから多くのテンプレートを抽出することができる。テンプレート−テンプレートが遷移図上のあるノードに関連付けられるべきラベル・シンボルｓ１，ｓ２，．．．，ｓｎを有すると仮定すると、テンプレート−テンプレートから抽出された異なるテンプレートはそれらのシンボルをノードに割り当てることによって獲得することができる。本発明ではテンプレートから抽出された各テンプレートをｎタプル｛ｓ１，ｐ１，ｓ２，ｐ２．．．，ｓｎ，ｐｎ｝で示すことができる。ここで、ｐｉはシンボルｓｉに対する適切な割り当てである。上記のセクションで既に議論した通り、ｐｉは使用される抽出ルールに従って数字または単語のどちらかであってもよい。
２つの文章の最重共通文字列はａ１の次にａ２、その次に．．．、その次にａｍという順番で両方の文章に現れる順番付けされた単語の最重共通文字列ａ１，ａ２，．．．，ａｍであると定義される。共通文字列の定義は、Ａ．Ｖ．ＡｈｏおよびＪ．Ｄ．Ｕｌｌｍａｎ著（Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  Ｐｒｅｓｓ，１９９２，ｐｐ．３２１−３２７）の教科書『Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ［情報化学の基礎］』に記載されている。
テンプレート内の各単語または各語句には重みが割り当てられているので、テンプレート内のパスと入力文の最重共通文字列は、その合計の重みが最大であるすべての予想可能な共通文字列内の最重共通文字列と定義される。
次に、テンプレートのすべての予想可能な有効パスから入力文の単語および／または語句の最重共通文字列を検索する。
テンプレートおよび入力文の最重共通文字列は、それぞれがテンプレートと入力文１つのパスから獲得される最重共通文字列中で最も重い合計重量を有する単語の最重共通文字列と定義される。
言語翻訳学習システムに関係するアプリケーションでテンプレート−テンプレートが獲得されると、次のステップは、入力文をすべての予想可能なテンプレートのそれぞれと照合し、次いで最も近いパスを選択することである。文章に対するテンプレートのＤＰ（ダイナミックプログラミング）ベースの照合手順の詳細な説明は、徳田  尚之、陳  亮、笹井  紘幸らによる特開２００２−４９６１７号等に記載されている。
本発明の方法では、テンプレート−テンプレートからすべてのテンプレートを物理的に抽出せずに、抽出ルールによって（しかしバギー・ルールにはよらずに）直接的に抽出することができるテンプレートのすべての有効なパスの中から最も近いパスを探索する。そのような照合を行う前にテンプレート−テンプレートにはいかなるバギー・ルールをも含めないように、まずバギー・ルールが埋め込まれたテンプレート−テンプレートを展開する必要がある。これはすでに述べた図２のステップに従って実行することができる。
アルゴリズムで必要とされる第１のステップは、適用可能な空ノードごとに□というラベルの弧に重み０を加算してテンプレートの各ノードをグラフの１つまたは複数の弧として単純に表現することによって、テンプレート−テンプレートを非循環的な重み付けされた有限有向グラフ（有向グラフ）の２重数値に変換することである。有向グラフはテンプレート−テンプレートから変換されるので、その関数がそのシンボルに割り当てられた値に決定的に依存するラベル・シンボルに関連付けられた多くの弧を含む。したがってそのような１つの有向グラフがあると仮定すると、異なる一組のラベル・シンボルが弧に割り当てられている場合は完全に異なるテンプレートを抽出することができる。すなわち、そのような有向グラフがあると仮定すると、テンプレート−テンプレートから抽出することができるテンプレートにそれぞれが対応する多くの有向グラフを獲得することができる。テンプレート−テンプレートから抽出された有向グラフを、以後、テンプレート有向グラフと呼ぶ。
本発明者らは、次にすべての有向グラフのパスと入力文の共通文字列から最重共通文字列を探索する手順を以下で定義する。
有向グラフの任意の特定のノードＮで終了するパスと入力文の最重共通文字列は、有向グラフＮで終了する１つのパスと入力文からそれぞれが獲得されるすべての最重共通文字列中最も重い合計重量を有する単語のシーケンスと定義される。
さらに、テンプレート有向グラフから抽出され、しかしノードＮｉで終了するすべての有向グラフのパスをＮｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝で表現する。ここでシンボルｓｉは値ｐ１（ｉ＝１，２，．．．，ｎ）に割り当てられる。ｎタプル｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝をノードＮｉのラベルと呼ぶ。ここでｓ１をｐ１に、ｓ２をｐ２に、．．．，ｓｎをｐｎにセットするときにルールの矛盾がないものと仮定すべきである。このようなラベル｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝を矛盾なしラベルと呼ぶ。
Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝でラベルされたノードと入力文の最重共通文字列は、矛盾なしラベル｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝でマーク付けされたノードを有する有向グラフ・テンプレートから抽出された１つの有向グラフの最重共通文字列としてそれぞれが獲得されるすべての最重共通文字列中で最も重い合計の重みを有する単語の最重共通文字列と定義される。
ノードによっては、１つの有向グラフのＡＰ２でラベルされたノードとＮＡＰ２でラベルされたノードのように有向グラフ・テンプレートから抽出された１つの有向グラフで同時に現れない場合があることに留意されたい。その結果、Ｎｉ（．．．，ＡＰ２，１，．．．，ＮＡＰ２，１．．．）のようにルール違反のラベルは、有向グラフ・テンプレートのノードと入力文の共通文字列のどの計算計画にも入ることを許可されるべきではない。以下のアルゴリズムはテンプレート−テンプレートと入力文の最重共通文字列を計算するための手順を記述する。以下の計算では、ラベル・シンボルの非常に特別の値として「λ」が使用され、それによってその値は計算の特定の段階に達するまで未指定のままである。
１．テンプレート−テンプレートを、その有向エッジ（遷移）がテンプレートの対応する単語によってラベルされるテンプレート有向グラフに変換する。
２．有向グラフのすべてのノードを、ノードＮｉおよびＮｊの対ごとにｊ＞ｉの場合にＮｊからＮｉへの遷移がないようにＮ１，Ｎ２，．．．，Ｎｔのノードにトポロジカリーに分類する。
３．空のノードＮ０を有向グラフに追加し、Ｎ０からの弧をテンプレート−テンプレートのすべての開始ノードに加える。
４．ＣＭ（Ｎ０，Ｍ０）＝０にセットする。
５．ｉ＝０からｔの場合、以下のステップを実行する。
６．１つのシンボルに関連付けられたＮｉに対して少なくとも１つの弧があり、ノードＮｉ以降にｓの関係ラベルがまったく存在しない場合、すべてのｉに関してｊ＝０からｍの場合は以下を実行する。
ｓ関係ラベルが｛ｓ１，ｓ２，．．．，ｓｎ｝に現れておらず少なくとも１つの｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，ｓｘ１，ｐｘ１，ｓｘ２，ｐｘ２，．．．，ｓｘｈ，ｐｘｈ｝が存在する場合、任意のラベル｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝に関してすべてのＣＭ（Ｎｉ｛．．．｝，Ｍｊ）をチェックする。ここでＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，ｓｘ１，ｐｘ１，ｓｘ２，ｐｘ２，．．．，ｓｘｈ，ｐｘｈ｝，Ｍｊ）が定義されるように、ｓｘ１，ｓｘ２，．．．，ｓｘｈはｓ関係ラベルである。
ＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ）を最大のＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，ｓｘ１，ｐｘ１，ｓｘ２，ｐｘ２，．．．，ｓｘｈ，ｐｘｈ｝，Ｍｊ）と定義し、すでに定義されているすべてのＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，ｓｘ１，ｐｘ１，ｓｘ２，ｐｘ２，．．．，ｓｘｈ，ｐｘｈ｝，Ｍｊ）を定義解除する。
７．ｊ＝０からｍの場合、以下のステップを実行する。
８．Ｎｉからの弧があるノードＮｋのそれぞれに対しては以下を実行する。
（１）弧ＮｉＮｋがラベルを有しない場合、すでに定義されているＣＭ（Ｎｉ｛．．．｝，Ｍｊ）、ＣＭ（Ｎｉ（．．．），Ｍｊ＋１），ＣＭ（Ｎｋ｛．．．｝，Ｍｊ）、ＣＭ（Ｎｋ（．．．），Ｍｊ＋１）をすべてチェックし、ＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ）、ＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ＋１）、ＣＭ（Ｎｋ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ）、ＣＭ（Ｎｋ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ＋１の１つが既に定義されている場合はＣＭ（Ｎｋ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ＋１）を以下のデータの最大と定義する。
・  既に定義されている場合はＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ）である。
・  ＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ）が既に定義されており、弧ＮｉＮｋがＷｋと一致する場合はＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ）＋Ｗ（ＮｉＮｋ）である。
・  既に定義されている場合はＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ＋１）である。
・  既に定義されている場合はＣＭ（Ｎｋ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ）である。
既に定義されている場合はＣＭ（Ｎｋ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ＋１）である。
（２）弧ＮｉＮｋがシンボルｓに関連付けられている場合、既に定義されているＣＭ（Ｎｉ（．．．），Ｍｊ），ＣＭ（Ｎｉ｛．．．｝，Ｍｊ＋１）、ＣＭ（Ｎｋ（．．．），Ｍｊ）、ＣＭ（Ｎｋ｛．．．｝，Ｍｊ＋１）をチェックする。
（ｉ）ノード・ラベル｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，ｓ，λ｝が矛盾なしラベルであり、以下の少なくとも１つが既に定義されている場合：
・  ＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ）、ＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ＋１）
・  ＣＭ（Ｎｋ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ）、ＣＭ（Ｎｋ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ＋１）
・  ＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，ｓ，λ｝，Ｍｊ）、ＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，ｓ，λ｝，Ｍｊ＋１）
・  ＣＭ（Ｎｋ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，ｓ，λ｝，Ｍｊ）、ＣＭ（Ｎｋ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，，ｓ，λ｝，Ｍｊ＋１）
・ＣＭ（Ｎｋ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，ｓ，λ｝，Ｍｊ＋１）を上記で定義されたデータの最大のデータと定義する。
（ｉｉ）ラベル｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝があると仮定して、ラベル｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，ｓ，ｐ｝が矛盾なしラベルであり、以下の少なくとも１つが真である場合：
・  ＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ）がすでに定義されており、ｓからｐまでのセッティングが｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝の必須選択肢であるか、ｐがｓに割り当てられた後でＮｉＮｋがＭｊ＋１と一致する場合
・  ＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ＋１）がすでに定義されており、ｓからｐまでのセッティングが｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝の必須選択肢の場合
・  ＣＭ（Ｎｋ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ）がすでに定義されており、ｓからｐまでのセッティングが｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝の必須選択肢である場合
・  ＣＭ（Ｎｋ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，ｓ，ｐ｝，Ｍｊ＋１）が既に定義されている場合
・  ＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，ｓ，ｐ，｝，Ｍｊ）が既に定義されている場合
・  ＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，，ｓ，ｐ｝，Ｍｊ＋１）が既に定義されている場合
・  ＣＭ（Ｎｋ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，，ｓ，ｐ｝，Ｍｊ）が既に定義されている場合
・  ＣＭ（Ｎｋ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，，ｓ，ｐ｝，Ｍｊ＋１）が既に定義されている場合
・  ＣＭ（Ｎｋ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，ｓ，ｐ｝，Ｍｊ＋１）を上記で定義されたデータと以下のデータの最大データと定義する。
・  ＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ）が定義されており、ｐがｓにセットされた後でＮｉＮｋがＭｊ＋１に一致する場合、ＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ｝，Ｍｊ）＋Ｗ（Ｍｊ＋１）である。
・  ＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，ｓ，ｐ｝，Ｍｊ）が定義されており、ｐがｓに割り当てられた後でＮｉＮｋがＭｊ＋１と一致する場合、
・  ＣＭ（Ｎｉ｛ｓ１，ｐ１，ｓ２，ｐ２，．．．，ｓｎ，ｐｎ，ｓ，ｐ｝，Ｍｊ）＋Ｗ（Ｍｊ＋１）である。
また、ｓとして割り当てられたｐに従い、これらのｓｉをλから値の必須選択肢まで変更する。
Ｎｘを最終的な頂点であると既に定義しているすべてのＣＭ（Ｎｘ，Ｍｍ）の中で最大のＣＭ（Ｎｘ，Ｍｍ）はテンプレート−テンプレートおよびパスの最重共通文字列の重みになる。
上記のアルゴリズムでは、いくつかの候補からいつＣＭ（Ｎ．（．．），Ｍ．）を選択したとしても選択したその１つに対して一種のバック・リンクをセットすることに留意されたい。テンプレート−テンプレートとパスの最長共通文字列の重みを探索したように、このバック・リンクを追跡することによって、最重共通文字列を有する抽出されたテンプレートのパスを入力文と共に即座に獲得することができることに留意されたい。
【産業上の利用可能性】  本発明を明細書中では代表的な応用例である自然言語翻訳の技術分野に関して記載したが、本発明の用途は自然言語学習システムに限定されるものではなく、本発明は音声利用技術、プログラミング言語学習システム、または例えば人間とコンピュータの対話を可能にするより自然な拡張型インターフェースを必要とするシステムであればどのようなシステムのためにも利用することができる。
【図１】
2004084156.tif 000003
【図２】
2004084156.tif 000004
【図３】
2004084156.tif 000005
【図４】
2004084156.tif 000006
【手続補正書】
【提出日】平成16年12月9日(2004.12.9)
【手続補正００１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【書類名】特許請求の範囲
【請求項１】自然言語表現を記述するテンプレート構造において、自然言語の正規文法を記述するプロダクション・ルールからのづれに基くバギー・ルールの拡張性を用い、テンプレート−テンプレート構造内のノードのいくつかが、多くのテンプレートまたはいわゆる大きいテンプレートに抽出することができる抽出ルールに関連付けられたシンボルでマーク付けされるテンプレート−テンプレート構造を用いたコンピュータ方式による対話式学習システム。
【請求項２】単一のスリムなテンプレートーテンプレートから複数のまたはより大きなテンプレートに抽出展開するため、テンプレートのノードのいくつかに抽出ルールに関連づけられた遷移ノードに対応する特別シンボルを割り当て、これによってファットなテンプレートまたは多数のテンプレートに抽出・展開することが出来るように設計されたテンプレートーテンプレート・スキームを用いる請求の範囲１記載の対話式学習システム。
【請求項３】前記抽出ルールが常に一組のシンボル、すなわち｛ｓ１，ｓ２，．．．，ｓｎ｝に関連付けられ、このシンボルのそれぞれはテンプレートの１つまたは複数のノードに割り当てられ、これらの関連付けられたシンボルには１つまたは複数の値が割り当てられてなる抽出ルール基く請求の範囲１記載の対話式学習システム。
【請求項４】学習者が修得する言語の正規文法を記述するプロダクション・ルールを不適切に応用したために生じるルールからのずれをバグとして定義する従来のバギー・ルールを拡張したバグの自動解釈機能によりスリムなテンプレートーテンプレートをより大きなテンプレートーテンプレートまたはよりファットなテンプレートーテンプレートに展開し、学習者の文法誤りを自動的に診断するバギー・ルールに基づく請求の範囲１記載の対話式学習システム。
【請求項５】入力文をテンプレートーテンプレートからより大きなテンプレートまたはよりファットなテンプレートに展開することなくテンプレートーテンプレートのままの状態で直接抽出可能な全てのパスの内、各テンプレート上の単語に割り当てられている共通文字列の中から最重の共通文字列をダイナミック・プログラミング法で有効グラフ上から選ぶようにしたＨＣＳマッチング（最重共通文字列）アルゴリズムを使い入力文に最適なパスを見出す請求の範囲１記載の対話式学習システム。




【国際調査報告】
2004084156.tif 000007
2004084156.tif 000008