(57)【要約】【課題】  本発明は、たとえ入力テキストが不完全に形成され又は断片的であったとしても、入力テキスト内の意味構造を効率的に識別する方法及び装置を提供する。【解決手段】  入力テキストから意味構造を識別する方法及び装置は、少なくとも２つの意味構造候補を形成する。意味スコアは、意味構造の尤度に基づいて各意味構造に対して判定される。構文スコアは、テキスト内の単語の位置及び単語からの形成される意味エンティティの意味構造内の位置に基づいて各意味構造に対して判定される。構文スコア及び意味スコアは、結合し、テキストの少なくとも一部に関する意味構造を選択する。多くの実施形態において、意味構造は、テキストの一部に対する候補構造を構築しスコアリングすること、低スコアリング候補を刈り込むこと及び保有された候補に追加の意味要素を加えることによって増加的に構築される。【選択図】  図３
2005115922.tif 000002
【特許請求の範囲】
【請求項１】
テキストから意味構造を識別する方法であって、
前記テキストから意味エンティティを識別し、
前記意味エンティティを結合して、少なくとも２つの意味構造候補を形成し、
前記意味構造の尤度に基づいて各意味構造候補の意味スコアを生成し、
前記テキスト内の単語の位置及び前記単語から形成される意味エンティティの前記意味構造内の位置に部分的に基づいて各意味構造候補の構文スコアを生成し、
各々の意味構造に対し構文スコアと意味スコアとを結合して、少なくともテキストの一部分に関する前記意味構造候補の１つを選択すること
を備えることを特徴とする方法。
【請求項２】
構文スコアを生成することは、意味構造候補内の意味エンティティ間の各親子関係毎に、親意味エンティティと関連する単語のトークン位置を識別することと、子意味エンティティと関連する単語のトークン位置を識別することと、前記トークン位置に基づき確率を判断することを備えることを特徴とする請求項１記載の方法。
【請求項３】
前記テキストから識別される意味エンティティが前記テキストと位置あわせされる順序に基づいて遷移スコアを生成することを更に備えることを特徴とする請求項１記載の方法。
【請求項４】
遷移スコアを生成することは、意味構造候補における同じレベルで現れる意味エンティティの各ペアに関する別々の遷移確率を生成することを備えることを特徴とする請求項３記載の方法。
【請求項５】
意味エンティティを用いて意味構造候補を形成することは、前記テキストから識別されない前記意味構造候補内に意味エンティティを含めることを備えることを特徴とする請求項１記載の方法。
【請求項６】
意味スコアを生成することは、前記意味エンティティが前記テキストから識別されなかった場合には、ペナルティ要素を用いて意味エンティティの確率を割り引くことを備えることを特徴とする請求項５記載の方法。
【請求項７】
意味エンティティを識別することは、テキストが意味エンティティと関連するスキーマを使用することを備えることを特徴とする請求項１記載の方法。
【請求項８】
単一の単語は、前記スキーマ内の複数意味エンティティと関連することを特徴とする請求項７記載の方法。
【請求項９】
意味エンティティを用いて意味構造を形成することは、スキーマ内で定義される意味エンティティ間の関係における前記意味構造を基礎とすることを備えることを特徴とする請求項７記載の方法。
【請求項１０】
意味エンティティ間の前記関係を定義する前記スキーマと、テキストと意味エンティティとを関連付ける前記スキーマとは同じスキーマであることを特徴とする請求項９記載の方法。
【請求項１１】
スキーマ内で定義される関係における意味構造を基礎づけることは、
２つの意味エンティティによってインデックスを付けられ、前記スキーマ内に見出される１組の意味構造を含むエントリを備えるテーブルを構築し、各意味構造は、前記エントリにインデックスを付けるために使用される２つの意味エンティティを含むこと、
前記２つの意味エンティティを使用してテーブルを検索し、前記意味構造の組を見つけること、および、
前記１組の意味構造内の各意味構造に関する意味構造を形成すること
を備えることを特徴とする請求項９記載の方法。
【請求項１２】
選択された意味構造と、前記テキストから識別される更なる意味エンティティとを結合して拡張意味構造を形成することを更に備えることを特徴とする請求項１記載の方法。
【請求項１３】
前記拡張意味構造に対する意味スコアと構文スコアとを生成することを更に備えることを特徴とする請求項１２記載の方法。
【請求項１４】
選択された意味構造と更なる意味エンティティとを結合することは、規則正しい検索を実行することを備え、前記検索は、
前記さらなる意味エンティティが前記選択された意味構造内のエンティティのいずれかの下方に配置することができるかどうかを判断すること、
前記選択された意味構造の頂上が前記さらなる意味エンティティの下方に配置することができるかどうかを判断すること、および、
前記さらなる意味エンティティと前記選択された意味構造の頂上とを下方に配置することができる共通祖先エンティティがあるかどうかを判断すること
を備えることを特徴とする請求項１２記載の方法。
【請求項１５】
選択された意味構造がコマンド意味構造でないことを決定すること、
コマンド意味構造内に前記選択された意味構造を配置すること、および、
前記コマンド意味構造を前記テキストの前記意味構造として識別すること
を更に備えることを特徴とする請求項１記載の方法。
【請求項１６】
前記選択された意味構造を複数コマンド意味構造に配置することを更に備えることを特徴とする請求項１５記載の方法。
【請求項１７】
各コマンド意味構造をスコアリングすること及び最も高いスコアリングコマンド意味構造を前記テキストの前記意味構造として選択することを更に備えることを特徴とする請求項１６記載の方法。
【請求項１８】
前記意味構造に対する前記構文スコアと前記意味スコアとに基づいてさらなる考慮から意味構造候補を減らすことを特徴とする請求項１記載の方法。
【請求項１９】
テキストから意味エンティティを識別するステップ、
前記意味エンティティから１組の部分的意味構造を形成するステップ、
前記部分的意味構造の各々をスコアリングして各部分的意味構造に対するスコアを提供するステップ、
少なくとも一つの部分的意味構造を刈り込み、前記部分的意味構造に対する前記スコアに基づいて少なくとも一つの部分的意味構造を保有するステップ、及び、
保有される部分的意味構造から全ての意味構造を形成するステップを
実行するコンピュータ実行可能命令を備えることを特徴とするコンピュータ可読媒体。
【請求項２０】
意味エンティティを識別することは、意味エンティティがテキストと関連するスキーマを利用することを備えることを特徴とする請求項１９記載のコンピュータ可読媒体。
【請求項２１】
１組の部分的意味構造を形成することは、
テーブルをアクセスして、前記テキストから識別される２つの意味エンティティによってインデックス付けされるエントリを見つけ、前記エントリは、前記２つの意味エンティティの両方を含む複数の意味構造を提供すること、
前記エントリによって提供される前記意味構造の各々に関する部分的意味構造を形成すること
を備えることを特徴とする請求項１９記載のコンピュータ可読媒体。
【請求項２２】
意味エンティティ間の関係を記述するスキーマから前記テーブルを構築することを更に備えることを特徴とする請求項２１記載のコンピュータ可読媒体。
【請求項２３】
少なくとも一つの部分的意味構造は、前記テキストから識別されない意味エンティティを備えることを特徴とする請求項２１記載のコンピュータ可読媒体。
【請求項２４】
部分的意味構造をスコアリングすることは、前記部分的意味構造内の各エンティティに対するスコアを計算し、エンティティに対する前記スコアは、前記エンティティが前記テキストから識別されなかった場合には減らされることを特徴とする請求項２３記載のコンピュータ可読媒体。
【請求項２５】
完全な意味構造を形成することは、前記テキストから識別される意味エンティティと、部分的意味構造とを結合することを備えることを特徴とする請求項１９記載のコンピュータ可読媒体。
【請求項２６】
完全な意味構造を形成することは、
前記意味エンティティが前記部分的意味構造内の前記エンティティのいずれかの下方に配置できるかどうかを判定すること、
前記部分的意味構造の頂点が意味エンティティの下方に配置できるかどうかを判定すること、及び
前記部分的意味構造の頂点および前記意味エンティティの両方が共通祖先エンティティの下方に配置できるかどうかを判定すること
を備えることを特徴とする請求項２５記載のコンピュータ可読媒体。
【請求項２７】
前記完全な意味構造がコマンド意味構造でないことを判定すること及びコマンド意味構造内に前記完全な意味構造を配置することを更に備えることを特徴とする請求項１９記載のコンピュータ可読媒体。
【請求項２８】
複数のコマンド意味構造内に前記完全な意味構造を配置すること、各コマンド意味構造をスコアリングすること、及び、前記スコアに基づいて前記コマンド意味構造の一つを選択することを更に備えることを特徴とする請求項２７記載のコンピュータ可読媒体。
【請求項２９】
部分的意味構造をスコアリングすることは、前記部分的意味構造内の前記意味エンティティ及び前記部分的意味構造内の前記意味エンティティ間の関係に基づいて意味スコアを決定することを備えることを特徴とする請求項１９記載のコンピュータ可読媒体。
【請求項３０】
部分的意味構造をスコアリングすることは、前記意味エンティティと関連する前記テキスト内の単語の位置に基づいて構文スコアを決定することを更に備えることを特徴とする請求項２９記載のコンピュータ可読媒体。
【請求項３１】
部分的意味構造をスコアリングすることは、意味エンティティの順序に基づいて遷移スコアを判定し、前記順序は、前記意味エンティティと関連する前記テキストへの前記意味エンティティの位置合わせによって設定されることを備えることを特徴とする請求項３０記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自然言語処理に関する。より詳細には、本発明は、テキストの意味論（ｓｅｍａｎｔｉｃ）を識別するテキスト処理に関する。
【背景技術】
【０００２】
自然言語処理の目的は、フリー形式の言語入力の意味又は意味論を解読することにある。一部のシステムは、意味規則を入力される個々の単語に直接適用することによって自然言語入力の意味を識別しようとしている。単語は複数の意味を有することができるので、これらの規則は大変複雑であり、かつ、開発するのが困難である。例えば、単語「ｒｏｏｍ」は、「Ｂｉｌｌ  ａｓｋｅｄ  ｉｆ  ｈｅ  ｃｏｕｌｄ  ｒｏｏｍ  ｗｉｔｈ  Ｊａｋｅ．」（ビルは、彼がジェイクと同宿できるかどうかを訪ねた。）のように動詞になり得、又、「Ｔｈｅ  ｔａｂｌｅ  ｉｓ  ｉｎ  ｔｈｅ  ｌｉｖｉｎｇ  ｒｏｏｍ．」のように名詞になり得る。その単語がいずれの意味で使用されているかを判断するためには、規則は、そのテキスト中に他にどのような単語が存在するかを判断しなければならない。各々が意味を有する多数の単語が使用される可能性があるため、膨大な数の規則が必要とされる。その結果、意味規則をテキスト内の単語に直接適用することは、多くの環境にあっては実行不可能と考えられている。
【０００３】
必要とされる規則の数を削減するために、多数のシステムは、テキストの意味を識別する前に、構文（ｓｙｎｔａｃｔｉｃ）分析を実行し、テキスト内の単語の品詞（ｐａｒｔ  ｏｆ  ｓｐｅｅｃｈ）及び単語間の構文関係を識別する。次に、品詞は、単語を直接使用するのではなく、規則内の条件（ｃｏｎｄｉｔｉｏｎｓ）として次に使用することができる。したがって、考えられる全ての名詞を規則内にリストアップするのではなく、単純に名詞を要求するために規則を書くことができる。この正規化は意味規則の複雑さを大幅に減らす。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ところが、別々の構文解析（ｓｙｎｔａｃｔｉｃ  ｐａｒｓｅ）の使用は２段階評価プロセスを作り出し、そのプロセスにおいては、全センテンスの内容を各段階で十分に考察しなければならない。このことは処理速度を落とす。しかも、不完全に形成された入力、断片的な入力、又は、誤った入力が原因で構文解析に失敗すると、意味処理もまた失敗することになる。
【０００５】
さらに、意味規則を書くことは難しい。なぜならば、意味規則は、一連の論理比較及び論理演算として記述されているからである。これにより、新しい意味構造を追加するには時間がかかる。
【課題を解決するための手段】
【０００６】
入力テキストから意味構造を識別する方法及びシステムは、少なくとも２つの意味構造候補を形成する。意味スコアは、意味構造の尤度（ｌｉｋｅｌｉｈｏｏｄ）に基づきそれぞれの意味構造候補毎に測定される。構文スコアは、テキスト中の単語の位置と、単語から形成される意味エンティティ（ｓｅｍａｎｔｉｃ  ｅｎｔｉｔｙ）の意味構造における位置とに基づき、それぞれの意味構造毎に測定される。構文スコアと意味スコアとを結合して、テキストの少なくとも一部についての意味構造を選択する。多くの実施形態においては、意味構造は、テキストの一部の構造候補を構築しスコアリングすること、低いスコアの候補を減らすこと（ｐｒｕｎｉｎｇ）、及び、追加の意味要素を保有されている候補に加えることによって増加的に構築される。
【発明を実施するための最良の形態】
【０００７】
図１は、本発明を実装できる好適なコンピューティングシステム環境１００の例を示す。コンピューティングシステム環境１００は、好適なコンピューティング環境１００の一例に過ぎず、本発明の使用の範囲又は機能性の範囲に関するいかなる制限も示唆する意図はない。コンピューティング環境１００は、例示的オペレーティング環境１００内に図示された構成要素のどれか一つ又は組み合わせに関連する依存状態又は必要条件を有するものとして解釈すべきでない。
【０００８】
本発明は、多数の他の汎用又は専用のコンピューティングシステム環境又は構成を伴って動作可能である。本発明とともに使用するのに適すると考えられる良く知られたコンピューティングシステム、環境、及び／又は構成の例は、限定なく、パーソナルコンピュータ、サーバーコンピュータ、ハンドヘルドデバイス又はラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラマブルコンシューマー電子機器、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、テレフォニーシステム、上記システム又はデバイスのいずれかを含んだ分散コンピューティング環境等を含む。
【０００９】
コンピュータによって実行されるプログラムモジュール等のコンピュータ実行可能命令の一般的なコンテキストで本発明を記述することができる。一般的にプログラムモジュールは、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造を含み、それらは、特定のタスクを実行し、又は、特定の抽象データ型を実装する。本発明は、分散コンピューティング環境で実施するように設計され、その環境では、通信ネットワークを介して連結されるリモート処理デバイスによってタスクが実行される。分散コンピューティング環境においては、プログラムモジュールは、メモリストレージデバイスを含むローカルコンピュータストレージメディア及びリモートコンピュータストレージメディアの両方に置かれる。
【００１０】
図１を参照すると、本発明を実行する例示的システムは、コンピュータ１１０の形式の汎用コンピューティングデバイスを含む。コンピュータ１１０の構成要素は、限定されず、処理ユニット１２０、システムメモリ１３０及び、システムメモリを含む多様なシステムコンポーネントを処理ユニット１２０に結合するシステムバス１２１を含むことができる。システムバス１２１は、メモリバス又はメモリコントローラを含む幾つかの種類のバス構造の内のいずれか、周辺バス、及び、様々なバスアーキテクチャのいずれかを使用するローカルバスであり得る。一例として、制限はなく、そのような構造は、業界標準アーキテクチャ（ＩＳＡ）バス、マイクロチャネル・アーキテクチャ（ＭＣＡ）バス、エンハンスドＩＳＡ（ＥＩＳＡ）バス、ビデオ・エレクトロニクス・スタンダード・アソシエーション（ＶＥＳＡ）ローカルバス、及び、メザニンバス（Ｍｅｚｚａｎｉｎｅ  ｂｕｓ）としても知られる周辺コンポーネントインターコネクト（ＰＣＩ）バスを含む。
【００１１】
コンピュータ１１０は、通常、多様なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータ１１０によってアクセス可能で利用可能な媒体であればよく、それは、揮発性媒体及び不揮発性媒体、取り外し可能媒体及び固定媒体を含む。一例として、制限ではなく、コンピュータ可読媒体は、コンピュータストレージ媒体と通信媒体とを備えることができる。コンピュータストレージ媒体は、コンピュータ可読命令、データ構造、プログラムモジュール又は他のデータ等の情報のストレージ方法又は技術において実装される揮発性媒体及び不揮発性媒体、取り外し可能媒体及び固定媒体を含む。コンピュータストレージ媒体は、制限ではなく、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ又は他のメモリテクノロジー、ＣＤ−ＲＯＭ、ディジタル多用途ディスク（ＤＶＤ）又はその他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ又は他の磁気ストレージデバイス、又は、所望の情報を格納するのに使用することができ、コンピュータ１１０によってアクセス可能な他の媒体を含む。通信媒体は、通常、コンピュータ可読命令、データ構造、プログラムモジュール又は他のデータを、搬送波又は他の移送機構等の被変調データ信号内に具象化し、および、情報伝達媒体を含む。「被変調データ信号」という用語は、１又は複数の特性セットを備える信号、又は、信号内の情報を符号化するための手法で変化した信号を意味する。一例として、かつ、限定では無く、通信媒体は、有線ネットワーク又は直接有線接続等の有線媒体、及び、音響、ＲＦ、赤外線及び他の無線媒体等の無線媒体とを含む。上記のいずれかの組み合わせは、コンピュータ可読媒体の範囲内に含まれるべきである。
【００１２】
システムメモリ１３０は、リードオンリメモリ（ＲＯＭ）１３１やランダムアクセスメモリ（ＲＡＭ）１３２等の揮発性及び／又は非揮発性メモリの形式のコンピュータストレージ媒体を含む。基本入力／出力システム１３３（ＢＩＯＳ）は、起動時等においてコンピュータ１１０内で構成要素間の情報転送の助けをする基本ルーチンを含み、通常、ＲＯＭ１３１内に記憶される。ＲＡＭ１３２は、通常、直ちに処理ユニット１２０によってアクセス可能であるか、及び／又は、処理ユニット１２０上で目下動作しているデータ及び／又はプログラムモジュールを含む。単なる例として、限定ではなく、図１は、オペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６及びプログラムデータ１３７を示す。
【００１３】
コンピュータ１１０は、他の着脱式／非着脱式で揮発性／不揮発性コンピュータストレージ媒体もまた含むことができる。単なる例として、図１は、非着脱式の不揮発性磁気媒体に対してリードライトをするハードディスクドライブ１４１、着脱式の不揮発性磁気ディスク１５２に対してリードライトする磁気ディスクドライブ１５１、および、ＣＤ−ＲＯＭ又は他の光媒体等の着脱式の非揮発性の光ディスク１５６に対してリードライトする光ディスクドライブ１５５を示す。例示的オペレーティング環境において使用することができるその他の着脱式／非着脱式、揮発性／不揮発性コンピュータストレージ媒体は、限定ではなく、磁気テープカセット、フラッシュメモリカード、ディジタルバーサタイルディスク、ディジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭ及び同等物を含む。ハードディスクドライブ１４１は、通常、インタフェース１４０等の不揮発性メモリインタフェースを介してシステムバス１２１に接続される。また、磁気ディスクドライブ１５１及び光ディスクドライブ１５５は、通常、インタフェース１５０等の着脱式メモリインタフェースによってシステムバス１２１に接続される。
【００１４】
上述しかつ図１に示したドライブ及びそれらと関連するコンピュータストレージ媒体は、コンピュータ１１０用のコンピュータ可読命令、データ構造、プログラムモジュール及びその他のデータを備える。図１においては、例えば、ハードディスクドライブ１４１は、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６及びプログラムデータ１４７を保存するものとして示される。尚、これらの構成要素は、オペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６及びプログラムデータ１３７と同じものであってもよいし、異なるものであってもよい。オペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６及びプログラムデータ１４７には異なる番号がふられ、最低限それらは異なるコピーであることを示す。
【００１５】
ユーザは、キーボード１６２、マイクロホン１６３及びマウス、トラックボール又はタッチパッド等のポインティングデバイス等の入力デバイスを介してコンピュータ１１０にコマンド及び情報を入力することができる。その他の入力デバイス（図示せず）は、ジョイスティック、ゲームパッド、サテライトデッイシュ、スキャナ等を含むことができる。これら入力デバイス及び他の入力デバイスは、システムバスに結合されるユーザ入力インタフェース１６０を介して処理ユニット１２０に接続される場合が多い。しかし、パラレルポート、ゲームポート又はユニバーサルシリアルバス（ＵＳＢ）等の他のインタフェース及びバス構造によって接続することができる。モニタ１９１又は他の種類の表示デバイスは、ビデオインタフェース１９０等のインタフェースを介してシステムバス１２１にも接続される。モニタのほかに、コンピュータは、スピーカ１９７及びプリンタ１９６等の他の周辺出力デバイスもまた含むことができ、これらは出力周辺インタフェース１９５を介して接続することができる。
【００１６】
コンピュータ１１０は、リモートコンピュータ１８０等の１又は複数のリモートコンピュータの論理的接続を使用してネットワーク化された環境内で動作する。リモートコンピュータ１８０は、パーソナルコンピュータ、ハンドヘルドデバイス、サーバー、ルーター、ネットワークＰＣ、ピアデバイス又は他の共通的ネットワークノードとすることができ、通常、コンピュータ１１０に関連して上述された構成要素の多くを又は全てを含む。図１に示された論理的接続は、ローカルエリアネットワーク（ＬＡＮ）１７１及び広域ネットワーク（ＷＡＮ）１７３を含むが、その他のネットワークを含むこともできる。そのようなネットワーキング環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット及びインターネット内では一般的である。
【００１７】
ＬＡＮネットワーキング環境で使用される場合、コンピュータ１１０は、ネットワークインタフェース又はアダプター１７０を介してＬＡＮ１７１に接続される。ＷＡＮネットワーキング環境において使用される場合、コンピュータ１１０は、通常、モデム１７２又はインターネット等のＷＡＮ１７３上で通信を確立する他の手段を含む。モデム１７２は、内蔵又は外付けにあり得るが、ユーザ入力インタフェース１６０又は他の適切な機構を介してシステムバス１２１に接続することができる。ネットワーク化された環境においては、コンピュータ１１０に関連して示されるプログラムモジュール、又はそれらの部分は、リモートメモリストレージデバイス内に保存することができる。一例として、及び制限ではなく、図１は、リモートコンピュータ１８０上にあるリモートアプリケーションプログラム１８５を示す。図示されるネットワーク接続は、例であり、コンピュータ間で通信リンクを確立する他の手段を用いてもよいことが理解されるであろう。
【００１８】
本発明は、たとえ入力テキストが不完全に形成され又は断片的であったとしても、入力テキスト内の意味構造を効率的に識別する方法及び装置を提供する。本発明のシステムを示すブロック図を図２に提示し、意味構造を識別する方法を図３のフロー図に示す。
【００１９】
図３のステップ３００において、意味の型と確率２０２、マルコフ確率２０４及び意味規則２０６を含むスキーマ２００を定義する。スキーマの一部の例を図４に示す。
【００２０】
図４において、＜Ｓｃｈｅｍａ＞タグ４００で開始し＜／Ｓｃｈｅｍａ＞タグ４０２で終了するＸＭＬフォーマットを使用してスキーマを定義する。意味の型は、＜Ｅｎｔｉｔｙ＞タグ４０４及び４０６等の＜Ｅｎｔｉｔｙ＞タグの内部に定義される。開始＜Ｅｎｔｉｔｙ＞タグの内部に、エンティティのアイデンティティ（ｉｄｅｎｔｉｔｙ）が、「Ｔｙｐｅ」属性に関する値としてリストアップされる。例えば、＜Ｅｎｔｉｔｙ＞タグ４０４に関しては、エンティティは、「Ｆｌｉｇｈｔ」として識別される。開始＜Ｅｎｔｉｔｙ＞タグは、「ｓｅｅｎ」属性をも含み、その属性は、このエンティティが１組のトレーニングデータ内で生じた回数を表す。例えば、「Ｆｌｉｇｈｔ」エンティティは、トレーニングデータ内で１２１回見られる。
【００２１】
開始＜ｅｎｔｉｔｙ＞タグと終了＜ｅｎｔｉｔｙ＞タグの間には、＜Ｗｉｔｈ＞タグ４０８、４１０、４１２、４１４、４１６等の１組の＜Ｗｉｔｈ＞タグを見出すことできる。各＜Ｗｉｔｈ＞タグは、開始＜Ｅｎｔｉｔｙ＞タグ内にリストアップされたエンティティに対する子エンティティ（ｃｈｉｌｄ  ｅｎｔｉｔｙ）として現れることができるエンティティを識別する「ＥｎｔｉｔｙＴｙｐｅ」の属性を備える。例えば、＜ｗｉｔｈ＞タグ４０８は、「ＴｉｍｅＥｎｔｉｔｙ」がタグ４０４内に見出される「Ｆｌｉｇｈｔ」エンティティへの子エンティティとして現れることができることを表す。各＜ｗｉｔｈ＞タグは、＜ｗｉｔｈ＞タグのエンティティが＜Ｅｎｔｉｔｙ＞タグ内のエンティティへの子エンティティとして見出された回数を示す「Ｓｅｅｎ」属性をも含む。例えば、タグ４１４は、「Ａｉｒｌｉｎｅ」エンティティが「Ｆｌｉｇｈｔ」の子エンティティとして３９回見出されたことを示す。
【００２２】
＜ｗｉｔｈ＞タグ内の幾つかのエンティティは、さらに、「Ｔｙｐｅ」属性内の制約セットによって定義される。例えば、＜Ｗｉｔｈ＞タグ４１０及び４１２は、どちらも「Ｃｉｔｙ」のエンティティに関する。しかしながら、タグ４１０は、「ｇｏａｌ」又は旅行の目的地である都市に制限され、一方、タグ４１２は、「ｓｏｕｒｃｅ」又は旅行の出発地である都市に制限される。
【００２３】
＜Ｅｎｔｉｔｙ＞タグ内の別のタグは、＜Ｄｅｎｏｔｅｄ＞タグである。二つの＜Ｄｅｎｏｔｅｄ＞タグ間の単語又はフレーズは、トレーニングデータ内に現れた単語又はフレーズであり、このエンティティと関連した。例えば、単語「ｆｌｉｇｈｔ」は、トレーニングテキスト内で見出されて、＜Ｄｅｎｏｔｅｄ＞タグ４１８によって示されるような「ｆｌｉｇｈｔ」エンティティと関連した。＜Ｄｅｎｏｔｅｄ＞タグは、＜Ｄｅｎｏｔｅｄ＞タグ間の単語又はフレーズがこのエンティティと結びついた回数を示す「ｓｅｅｎ」属性を含むことができる。例えば、単語「ｆｌｉｇｈｔｓ」は、「ｆｌｉｇｈｔ」エンティティと７９回関連した。
【００２４】
図３に戻ると、スキーマが定義された後に、ステップ３０２において、意味構造テーブル２１０を構築するテーブル構築ユニット２０８はそのスキーマを使用する。具体的には、スキーマ内の＜Ｅｎｔｉｔｙ＞タグ間で定義される意味型２０２は、意味構造テーブル２１０を構築するために使用される。
【００２５】
構造テーブル２１０は、スキーマ内の考えられるエンティティの各対に対する別個のエントリから構成される。各エントリは、構築可能な全ての構造のリストを含み、そこでは、両方のエンティティが提示されることになる。これらの構造は、２つのエンティティが直接共に連結される構造と２つのエンティティが別のエンティティを介して接続される構造とを含むことに留意されたい。例えば、１のエンティティは、別のエンティティの孫である場合があり、それらの間にはエンティティがあるか又はその２つのエンティティは共通の祖先（ａｎｃｅｓｔｏｒ）エンティティを共有することができる。その２つのエンティティ間の接続を形成するために要するこれらのエンティティだけがテーブル内の一つの構造に対してリストアップされる。このテーブルを最初に生成することによって、本発明は、ランタイムになされなければならない計算量を減らし、２つのエンティティがスキーマの下で共に接続することができる異なる方法を識別する。
【００２６】
ステップ３０４において、テキスト２１２は、意味エンティティ識別子２１４によって受け取られ、その識別子は、ステップ３０６において、テキストによって表すことができる全てのエンティティを識別する。これを行うために、エンティティ識別子は、スキーマ２００の＜ｅｎｔｉｔｙ＞タグ内の＜Ｄｅｎｏｔｅｄ＞タグを利用する。テキストからの単語又はフレーズが１組の＜Ｄｅｎｏｔｅｄ＞タグ内に見出される場合は、意味ノードは、単語又はフレーズ毎に生成され、＜Ｄｅｎｏｔｅｄ＞タグを含んだエンティティは、ノード毎の可能なエンティティとして追加される。シングルノードは、複数のエンティティをもつことができることに留意されたい。２つのエンティティ（エンティティと結びつく単語又はフレーズ）の範囲（ｓｐａｎ）が重なりあうならば、それらは同じ意味ノードの一部になると考えられる。結果は、意味エンティティ格子（ｌａｔｔｉｃｅ）である。
【００２７】
図５は、ステップ３０６を介して形成されるエンティティ格子の例を示すダイアグラムを提供する。図５において、不完全に形成された入力センテンス「Ｉ  ａｍ  ｉｎ  Ｂｏｓｔｏｎ  ａｎｄ  Ｉ  ｗａｎｔ  ｔｏ  ｂｅ  ｉｎ  Ｄｅｔｒｏｉｔ  ｏｎ  Ｔｕｅｓｄａｙ，  ｓｈｏｗ  ｍｅ  Ｕｎｉｔｅｄ  ｆｌｉｇｈｔｓ」が処理されエンティティ格子を識別する。この処理の間、「Ｂｏｓｔｏｎ」と「Ｄｅｔｒｏｉｔ」は、２つの別々の「ｃｉｔｙｎａｍｅ」エンティティ５００及び５０２にマッピングされ、それらのエンティティは、２つの連結した意味ノード（ｓｅｑｕｅｎｔｉａｌ  ｓｅｍａｎｔｉｃ  ｎｏｄｅ）を表す。「Ｔｈｅｓｄａｙ」は、第３の意味ノードで「ｄａｙｓｏｆｗｅｅｋ」エンティティ５０４にマッピングされる。単語「ｓｈｏｗ」は、４番目のノードで重なり合う４つの可能なエンティティにマッピングされる。具体的には、「ｓｈｏｗ」は、「ＳｈｏｗＡｉｒｌｉｎｅＳｅｒｖｅｄ」エンティティ５０６、「ＳｈｏｗＦｌｉｇｈｔ」エンティティ５０８、「ＬｉｓｔＴｒａｎｓｐｏｒｔ」エンティティ５１０及び「ＳｈｏｗＣａｐａｃｉｔｙ」エンティティ５１２にマッピングされる。単語「Ｕｎｉｔｅｄ」及び「ｆｌｉｇｈｔｓ」は、「Ａｉｒｌｉｎｅ」エンティティ５１４と「Ｆｒｉｇｈｔ」エンティティ５１６にそれぞれがマッピングされ、それらのエンティティは、格子内の最後の２つの意味ノードを表す。
【００２８】
ステップ３０８において、意味規則２０６は、ステップ３０６において識別されるエンティティに適用される。そのような意味規則の例を、＜ＧｒａｍｍａｒＲｕｌｅ＞タグ４２０及び４２２並びに＜ＧｒａｍｍａｒＲｕｌｅ＞タグ４２４及び４２６等の＜ＧｒａｍｍａｒＲｕｌｅ＞タグ間の図４のスキーマ例に示す。
【００２９】
＜ＧｒａｍｍａｒＲｕｌｅ＞タグの各対間には、＜Ｃｏｎｓｉｓｔ＞タグ４２８等の１又は複数の＜Ｃｏｎｓｉｓｔ＞タグがある。各々の＜Ｃｏｎｓｉｓｔ＞タグは、「Ｅｎｔｉｔｙ」属性によって＜Ｃｏｎｓｔｉｔ＞タグ内で識別されるエンティティを表す。特別な文法ルールを実行しなければならないかどうかを判断するために、ステップ３０６にて形成されたエンティティ格子が検査され、規則の＜Ｃｏｎｓｔｉｔ＞タグ内にリストアップされた全てのエンティティが格子に沿った別々の意味ノード内に存在するかどうかを確認する。一部の実施形態においては、エンティティは、＜Ｃｏｎｓｔｉｔ＞タグとして同じ順序で格子内に現れなければならない。例えば、文法ルールが以下のタグの順序を含む場合には、「Ｎｕｍｂｅｒ」エンティティは、文法ルールを実行するために、エンティティ格子内の「Ｆｌｉｇｈｔ」エンティティの左に現れなければならない。
＜Ｃｏｎｓｔｉｔ  Ｎｕｍｂｅｒ＝”０”  Ｅｎｔｉｔｙ＝”Ｎｕｍｂｅｒ”  ／＞
＜Ｃｏｎｓｔｉｔ  Ｎｕｍｂｅｒ＝”１”  Ｅｎｔｉｔｙ＝”Ｆｌｉｇｈｔ”＞
上記に示したように、＜Ｃｏｎｓｔｉｔ＞タグは、「Ｎｕｍｂｅｒ」属性をもまた含む。この属性は、規則の実行中にエンティティを識別するために使用できるエンティティに値を割り当てる。この値は、同じエンティティ型の２つのエンティティが単一の文法ルール内で使用できるため、必要とされる。
【００３０】
一般に、各文法ルールは、＜Ｃｏｎｓｔｉｔ＞タグ内で見出された構成要素エンティティを結合して、構成要素エンティティが埋め込まれている新しいエンティティを形成する。文法ルールの一つの型は、親エンティティを形成し、そこでは、各構成要素エンティティが親エンティティに対する子になる。この規則は、親として使用されるべきエンティティを識別する「Ｅｎｔｉｔｙ」属性を備えている＜Ｐａｒｅｎｔ＞タグを利用する。このタグに出くわし、＜Ｃｏｎｓｔｉｔ＞タグがエンティティ格子内に存在する場合、＜Ｃｏｎｓｔｉｔ＞タグの個々のエンティティが取り除かれ、意味構造が生成され、そこでは、＜Ｃｏｎｓｔｉｔ＞タグのエンティティが＜Ｐａｒｅｎｔ＞タグ内に見出されるエンティティへの子エンティティになる。そして、この構造の範囲（ｓｐａｎ）が子エンティティの範囲の組み合わせである。
【００３１】
文法規則は、より複雑な構造フォーメーションを備えることができ、そこでは、＜Ｃｏｎｓｔｉｔ＞タグのエンティティが複数のレベル構造を介して結合されるか、あるいは、エンティティの属性が変更されるか、あるいは、エンティティ自体が変更される。このような規則は、＜Ｃｏｎｓｔｉｔ＞タグの「ｎｕｍｂｅｒ」属性を使って割り当てられる値を使用して構成要素エンティティから形成される最終構造を指定する＜Ｒｕｌｅ＞タグを含む。例えば、
<Constit Number=”0” Entry=”City”
Restriction=”Source” />
<Constit Number=”1” Entry=”City”
Restriction=”Goal”/>
<Constit Number=”2” Entity=”City”
Restriction=”Goal” />
<Rule>{Flight[(Source,City,0)(Via, City,1)
(Goal,City,2)]}</Rule>
は、親「Ｆｌｉｇｈｔ」エンティティを有する「Ｆｌｉｇｈｔ」構造、エンティティ「０」として指定される都市エンティティで満たされる（ｆｉｌｌｅｄ  ｗｉｔｈ）子起点都市（ｓｏｕｒｃｅ  ｃｉｔｙ）エンティティ、エンティティ「１」として指定される都市エンティティで満たされる子経由都市エンティティ（ａ  ｃｈｉｌｄ  ｖｉａ  ｃｉｔｙ  ｅｎｔｉｔｙ）、及びエンティティ「２」として指定された都市エンティティで満たされた子目的地都市エンティティ（ａ  ｃｈｉｌｄ  ｇｏａｌ  ｃｉｔｙ  ｅｎｔｉｔｙ）を生成する。このルールにおいては、エンティティ「１」として指定される都市エンティティは「ｇｏａｌ」エンティティから「ｖｉａ」エンティティに変更されることに留意されたい。
【００３２】
上述の例においては、「Ｒｅｓｔｒｉｃｔｉｏｎ」属性は、エンティティの特別の型である。他のエンティティと同様に、制約エンティティは、どの単語がエンティティを生成するかを示すその定義中に＜Ｄｅｎｏｔｅｄ＞タグを備える。例えば、「Ｇｏａｌ」制約エンティティは、単語「ｔｏ」又はフレーズ「ａｒｒｉｖｉｎｇ  ａｔ」によって示される。制約エンティティは、それらが構造内の同じレベルで別のエンティティを変更する点でその他のエンティティとは異なる。したがって、Ｇｏａｌ、Ｓｏｕｒｃｅ、Ｖｉａが都市エンティティを変更する。制約エンティティと変更されたエンティティとは共に、制約を伴う単一エンティティを形成する。以下に述べるように、制約エンティティティは、単に制約として参照される場合が多い。
【００３３】
スキーマにおいて、エンティティが制約を伴う別のエンティティを受け入れるならば、制約は、＜Ｗｉｔｈ＞タグ内の「Ｔｙｐｅ」属性を使用して識別される。例えば、＜Ｗｉｔｈ＞タグ４１６は、「Ｆｌｉｇｈｔ」エンティティが「Ｖｉａ」制約を有する「Ｃｉｔｙ」エンティティを受け入れることを示す。
【００３４】
図６は、図４内に見出される文法規則を図５のエンティティ格子上で実行した結果を示す。特に、＜ＧｒａｍｍａｒＲｕｌｅ＞タグ４２４と４２６内部に見出される文法規則は、「ＣｉｔｙＮａｍｅ」エンティティ５００と５０２に適用されている。これは、親エンティティ「Ｃｉｔｙ」エンティティ６０４と６０６及び子「ＣｉｔｙＮａｍｅ」エンティティ５００と５０２を備えている「Ｃｉｔｙ」意味構造６００と６０２を作成する。＜ＧｒａｍｍａｒＲｕｌｅ＞タグ４２０と４２２内の文法規則は「ＤａｙｓｏｆＷｅｅｋ」エンティティ５０４に適用されて、「ＴｉｍｅＥｎｔｉｔｙ」親ノード６１０と「ＤａｙｓｏｆＷｅｅｋ」子エンティティ５０４を備える「ＴｉｍｅＥｎｔｉｔｙ」構造６０８を作成する。
【００３５】
意味規則が実行された後に、第１の２つの意味ノードがステップ３１０において選択される。大抵の実施形態においては、これは、２つの最も左の（ｌｅｆｔ−ｍｏｓｔ）意味ノードを選択することと関連する。
【００３６】
ステップ３１２において、構造ジェネレータ２１６は、意味構造テーブル２１０を使用して、選択された２つの意味ノードに対してリストアップされたエンティティを用いて形成することができる全ての考えられる構造を識別する。例えば、第１のノードがエンティティＡとＢとを含み、第２のノードがエンティティＣとＤとを含む場合には、別々の構造がエンティティペアＡＣ、ＡＤ、ＢＣ、ＢＤ毎に識別される。複数構造を各エンティティ対毎に識別することができることに留意されたい。このプロセスをランタイムに素早く実行することができる。なぜならば、各エンティティペア毎の考えられる構造は、予め識別されており、構造テーブル２１０に格納されているからである。
【００３７】
図６の変更エンティティ格子の第１の２つのエンティティから生成された構造の例を図７に示す。図６の第１の２つの意味ノードの各々に対してエンティティが１つしかないため、考慮すべきエンティティペアは一つだけである。しかしながら、構造ジェネレータは、この単一エンティティペアを用いて形成することができる６つの別々の構造を識別する。特に、６つの「Ｆｌｉｇｈｔ」意味構造７００、７０２、７０４、７０６、７０８、７１０は識別される。
【００３８】
識別された意味構造の全ては、「Ｆｌｉｇｈｔ」構造であるが、それらは、各々（「Ｃｉｔｙ」エンティティ６０４及び「ＣｉｔｙＮａｍｅ＝Ｂｏｓｔｏｎ」エンティティ５００から成る）「Ｃｉｔｙ」意味構造６００と（「Ｃｉｔｙ」エンティティ６０６及び「ＣｉｔｙＮａｍｅ＝Ｄｅｔｒｏｉｔ」エンティティ５０２から成る）「Ｃｉｔｙ」意味構造６０２を使用して、「Ｆｌｉｇｈｔ」構造内の異なるスロットを満たす。具体的には、各「Ｃｉｔｙ」意味構造は、「Ｆｌｉｇｈｔ」エンティティ内に見出される制約エンティティ「ｓｏｕｒｃｅ  ｃｉｔｙ」、「ｖｉａ  ｃｉｔｙ」、「ｇｏａｌ  ｃｉｔｙ」の３つのスロットのうちの一つを満たすために使用することができる。したがって、６つの「Ｆｌｉｇｈｔ」構造は、２つの「Ｃｉｔｙ」意味構造に関する６つの異なる考えられる割り当ての組み合わせを表す。
【００３９】
例えば、「Ｆｌｉｇｈｔ」構造７００内では、「Ｃｉｔｙ」エンティティ６０４は、「Ｓｏｕｒｃｅ」都市スロット７２０を満たし、「Ｃｉｔｙ」エンティティ６０６は、「Ｇｏａｌ」都市スロット７２２を満たす。しかしながら、「Ｆｌｉｇｈｔ」構造７０２においては、「Ｃｉｔｙ」エンティティ６０４は、「Ｇｏａｌ」都市スロット７２４を満たし、「Ｃｉｔｙ」エンティティ６０６は「Ｓｏｕｒｃｅ」都市スロット７２６を満たす。
【００４０】
「Ｆｌｉｇｈｔ」構造７０４においては、「Ｃｉｔｙ」エンティティ６０４は、「Ｓｏｕｒｃｅ」都市スロット７２８を満たし、「Ｃｉｔｙ」エンティティ６０６は、「Ｖｉａ」都市スロット７３０を満たし、一方、「Ｆｌｉｇｈｔ」構造７０６においては、「Ｃｉｔｙ」エンティティ６０４は、「Ｖｉａ」都市スロット７３２を満たし、「Ｃｉｔｙ」エンティティ６０６は、「Ｓｏｕｒｃｅ」都市スロット７３４を満たす。
【００４１】
最後に、「Ｆｌｉｇｈｔ」構造７０８においては「Ｃｉｔｙ」エンティティ６０４は、「Ｇｏａｌ」都市スロット７３６を満たし、「Ｃｉｔｙ」エンティティ６０６は、「Ｖｉａ」都市スロット７３８を満たし、一方、「Ｆｌｉｇｈｔ」構造７１０においては、「Ｃｉｔｙ」エンティティ６０４は、「Ｖｉａ」都市スロット７４０を満たし、「Ｃｉｔｙ」エンティティ６０６は、「Ｇｏａｌ」都市スロット７４２を満たす。
【００４２】
図７の意味構造においては、「Ｆｌｉｇｈｔ」エンティティは、都市エンティティの各々への親エンティティであり、各都市エンティティは、「Ｆｌｉｇｈｔ」エンティティの定義内の＜ｗｉｔｈ＞タグ内にリストアップされる。したがって、各都市エンティティは、意味構造内の「Ｆｌｉｇｈｔ」エンティティの下位になると考えられる子エンティティである。
【００４３】
２つのノードに関する可能な全ての構造が生成された後に、構造がスコアリングモジュール２１８に提供され、スコアリングモジュール２１８は、ステップ３１４において各構造のスコアリングをする。本発明においては、各構造のスコアは、３つのセミ直交スコア（ｔｈｒｅｅ  ｓｅｍｉ−ｏｒｔｈｏｇｏｎａｌ  ｓｃｏｒｅｓ）の積である。これらのスコアの一つは意味構造の尤度に基づき、スコアのもう一つは、意味エンティティが入力テキストにおいて表現される順序に基づく。また、最後（ｌａｓｔ）のスコアは、意味構造の構文の正確性に基づく。
【００４４】
最初のスコアは、意味スコアとして参照され、数１のように計算される。
【００４５】
【数１】
2005115922.tif 000003
【００４６】
ここでEjは、エンティティ構造Ｓ内の別々のエンティティであり、ＣEは、エンティティEjの子エンティティの全てであり、p(Ej)は、エンティティEjの確率であり、P(ci/Ej)は、エンティティEjを与えられた子エンティティciの確率である。
【００４７】
意味確率の確率は、＜Ｅｎｔｉｔｙ＞タグ及び＜ｗｉｔｈ＞タグ内の「ｓｅｅｎ」属性を使用してスキーマから判断される。具体的には、エンティティp(Ej)の確率は、そのエンティティに関する＜Eｎｔｉｔｙ＞タグ内の「Sｅｅｎ」属性の値を、スキーマ内の全てのエンティティの＜Eｎｔｉｔｙ＞タグ内の「Sｅｅｎ」属性の数値の合計で割ることによって決定される。親エンティティp(ci/Ej)を与えられた子エンティティの確率は、子エンティティに関する＜Ｗｉｔｈ＞タグ内の「Ｓｅｅｎ」属性の値を親エンティティの＜Ｅｎｔｉｔｙ＞タグ内の「Ｓｅｅｎ」属性の値によって割ることによって決定される。
【００４８】
本発明の一部の実施形態においては、式１の意味スコアは、エンティティがテキストから直接導き出されず、代わりにテキストから得られた２つのエンティティティを接続するために生成されたならば、エンティティの確率を減らすために適用されるペナルティ要素とともに増大する。例えば、図７において、「Ｆｌｉｇｈｔ」エンティティ７５０の確率は、「Ｆｌｉｇｈｔ」エンティティが意味構造内に配置され、２つの「ｃｉｔｙ」エンティティを接続し、そしてテキストから作成されたエンティティ格子から直接取られないため、ペナルティエンティティによって減らされるであろう。実施形態の一部においては、ペナルティ要素は、９０である。
【００４９】
意味エンティティが入力テキスト中に表現される順序に基づいて第２のスコアは、マルコフスコア又は遷移スコアとして参照される。一実施形態においては、マルコフスコアは、意味構造内の同じレベルにあるエンティティの各ペアの遷移確率の積として計算される。例えば、図７の意味構造７００マルコフ確率は、後に目的都市が続く出発都市を有する遷移確率として単純に計算される。目的都市の後に同じレベルの別の子ノードがあった場合には、後に追加のエンティティが続く出発都市を有する追加の遷移確率が決定されるであろう。
【００５０】
１対の同じレベルエンティティの遷移確率は、スキーマ２００内の（図２内のマルコフ確率とし２０４として示される）＜ｔｒａｎｓｉｔｉｏｎｐｒｏｂ＞タグから決定される。このような＜ｔｒａｎｓｉｔｉｏｎｐｒｏｂ＞タグの例は、＜ｔｒａｎｓｉｔｉｏｎｐｒｏｂ＞タグ４３０および４３２として図４内に見出される。
【００５１】
＜ｔｒａｎｓｉｔｉｏｎｐｒｏｂ＞タグ内でエンティティの順番は、「Ｒ１」、「Ｅ１」、「Ｒ２」、「Ｅ２」属性を使用して示される。「Ｒ１」および「Ｅ１」属性は、２つのエンティティの最も左のエンティティに関する制約とエンティティを各々識別し、「Ｒ２」と「Ｅ２」属性は、２つのエンティティの最も右の（ｒｉｇｈｔ−ｍｏｓｔ）エンティティに関する制約とエンティティを識別する。したがって、＜ｔｒａｎｓｉｔｉｏｎｐｒｏｂ＞タグ４３０内の遷移確率は、後に出発都市が続く目的都市に関し、＜ｔｒａｎｓｉｔｉｏｎｐｒｏｂ＞タグ４３２内の遷移確率は、後に目的都市が続く出発都市に関する。各＜ｔｒａｎｓｉｔｉｏｎｐｒｏｂ＞タグはまた、「Ｓｅｅｎ」属性を含み、それは、２つのエンティティがタグ内にリストアップされた順序で共に見出された回数を示す。
【００５２】
２つのエンティティの特定な順序に対する確率を判断するために、２つのエンティティを含む＜Ｔｒａｎｓｉｔｉｏｐｒｏｂ＞タグの全てが配置される。（１又は２のそのようなタグのいずれかがあるであろう。）２つのエンティティの特別な順番の確率は、その順番の「Ｓｅｅｎ」の値を、２つのエンティティを含む＜Ｔｒａｎｓｉｔｉｏｎｐｒｏｂ＞の全ての「Ｓｅｅｎ」の値の合計で割ることによって判定される。例えば、図４に示す後に出発都市が続く目的都市の確率は、２／７１であり、一方、後に目的都市が続く出発都市の確率は、６９／７１として計算される。
【００５３】
同じレベルエンティティの各対に関する個々の遷移確率の積は、次に、構造に対するマルコフ確率を形成するために判定される。２−エンティティ遷移確率だけが上記では使用されているが、いかなる数のエンティティを使用しても遷移確率を判断することができることに留意されたい。
【００５４】
最後（ｌａｓｔ）の確率は、意味構造の構文の正確さを示し、構文スコアとして参照される。このスコアは、多数の異なる方法をつかって生成することができる。一実施形態のもとでは、構文解析構造が意味構造に基づいて形成される。具体的には、意味構造内のエンティティにまたがる（ｓｐａｎｎｅｄ）単語は、意味構造内のエンティティとして同じ関連位置内の構文構造内に配置される。結果として得られる構文解析ツリーのスコアは決定され、意味構造に関する構文スコアとして使用される。
【００５５】
本発明の別の実施形態のもとでは、構文スコアは、意味構造内の各親子関係に関する別々のスコアを決定することによって計算される。各親子関係に対して、親エンティティにまたがる単語又は句のトークン（ｔｏｋｅｎ）ポジション及び子エンティティにまたがる単語又は句のトークンポジションは識別され、トークンポジションは、センテンスの開始から単語又はフレームまでのトークンの数である。トークンは、単一のエンティティとして動作する個別の単語又はフレーズを含む。例えば、ニューヨークシティ（Ｎｅｗ  Ｙｏｒｋ  Ｃｉｔｙ）は、シングルトークンである。
【００５６】
次いで、トークンポジションは、子エンティティがトークンポジションＹにあるときトークンポジションＸにある親エンティティの尤度を記述する確率を識別するために使用される。したがって、構文スコアは、次のように計算される。
【００５７】
【数２】
2005115922.tif 000004
【００５８】
ここで、ＰXは、全ての親エンティティの組であり、ＣYは、各親エンティティに対する子エンティティの組であり、Ｘは、親エンティティのトークンポジションであり、Ｙは、子エンティティのトークンポジションである。
【００５９】
意味スコアとマルコフスコアと構文スコアの積は、各意味構造に対する全スコアである。これらの３つのセミ直交スコアを統合することによって、不完全に形成されたテキストからさえも意味構造を識別することができる。というのは、このような不完全に形成された文章から生成される候補構造は低い構文スコアを有する場合があるが、それらは、意味的にスコアリングされることになり、意味スコアは構造の少なくとも一つを実行可能な意味構造にするのに非常に十分であり得る。さらに、意味構造の進歩的な構築の間にスコアの構文構成要素と意味構成要素を統合することによって、本発明は、テキストから意味構造を識別するのに必要な時間量を著しく減らす。
【００６０】
意味構造がステップ３１４でスコアリングされた後に、１又は複数の構造は、刈り込みシステム（ｐｒｕｎｉｎｇ  ｓｙｓｔｅｍ）２２０によって、ステップ３１６における考慮から刈り込まれる。このような刈り込みは、トップN意味構造を取ることによって、又は、トップスコアリング意味構造のスレシホールド内部のこれらの意味構造を取ることによって実行することができる。図７の例に関しては、トップの４つの意味構造が保有される。特に、構造７００、７０４、７０８、７１０は、保有される。
【００６１】
刈り込んだ後に、格子はステップ３１８に検査され、処理すべき他の意味ノードがあるかどうかが判断される。処理すべき追加の意味ノードがある場合には、次のノードのエンティティが構造ジェネレータ２１６によって、保有された意味構造と結合され、ステップ３２０でエンティティと保有される構造の考えられる全ての組み合わせが形成される。
【００６２】
一実施形態において、順序付けられた検索は実行され、エンティティが意味構造にどのように取り付けられるかが判断される。最初に、検索は、新しいエンティティが意味構造内のエンティティのいずれかの配下に適合する構造を見つけ出すために実行される。次に、検索は、意味構造の頂上が新しいエンティティの配下に適合する構造を見つけ出すために実行される。最後に、検索は、意味構造と新しいエンティティの間に共通祖先があるかどうかを確認するために実行される。これらの検索の各々は、意味テーブル２１０を使用して実行される。
【００６３】
図７の構造から形成される新しい構造及び「ＴｉｍｅＥｎｔｉｔｙ」エンティティの例を図８に示す。特に、構造８００、８０２、８０４、８０６は、各々、構造７００、７０４、７０８、７１０から形成されている。全ての構造において、「ＴｉｍｅＥｎｔｉｔｙ」エンティティは、「Ｆｌｉｇｈｔ」エンティティへの子ノードとして追加されている。
【００６４】
ステップ３１４及び３１６は繰り返され、意味構造の各々のスコアをとり、構造の組を刈り込む。図８の例では４つの構造があるだけなので、構造はどれ一つとして刈り込まれない。
【００６５】
ステップ３１８及び３２０は、次に、図８の構造と、「ＳｈｏｗＡｉｒｌｉｎｅＳｅｒｖｅｄ」エンティティ５０６、「ＳｈｏｗＦｌｉｇｈｔ」エンティティ５０８、「ＬｉｓｔＴｒａｎｓｐｏｒｔ」エンティティ５１０及び次の意味ノードの「ＳｈｏｗＣａｐａｃｉｔｙ」エンティティ５１２を結合することを実行する。
【００６６】
次の意味ノードでの４つのエンティティの中で、「ＳｈｏｗＦｌｉｇｔ」エンティティだけが図８の構造と結合することができる。さらに、「ＳｈｏｗＦｌｉｇｔ」エンティティは、各構造と結合することができ、「ＳｈｏｗＦｌｉｇｔ」エンティティは、その直近の子として「ｆｌｉｇｈｔ」エンティティを備える構造の頂上になる。これにより、図８の構造８００、８０２、８０４、８０６に対応する、図９の意味構造９００、９０２、９０４、９０６が得られる。
【００６７】
ステップ３１４と３１６をスコアリングすること及び刈り込むことが、ステップ３１８で処理すべきより多くの意味ノードがあることが判断される前に、新しい意味構造９００、９０２、９０４、９０６に対して繰り返される。「Ａｉｒｌｉｎｅ」エンティティは、次に、ステップ３２０で意味構造９００、９０２、９０４、９０６に加えられる。これらの構造の各々に関して、これは、「Ａｉｒｌｉｎｅ」エンティティを子ノードとして「Ｆｌｉｇｈｔ」エンティティに加えることと関係する。結果として得られる構造は、図１０における意味構造１０００、１００２、１００４、１００６として示される。
【００６８】
「Ｆｌｉｇｈｔ」エンティティを図１０の構造に加える前に、ステップ３１４、３１６、３１８が新しい構造に対して繰り返される。「Ｆｌｉｇｈｔ」エンティティは、２つの都市エンティティを接続するために生成されたので、「Ｆｌｉｇｈｔ」エンティティは構造に追加される必要はない。しかしながら、「Ｆｌｉｇｈｔ」エンティティが、意味構造をスコアする格子手段の中に見出されたという事実は、もはや、「Ｆｌｉｇｈｔ」エンティティの生成に関するペナルティ要素を含まないことを意味する。
【００６９】
新しい構造をスコアリングすること及び刈り込んだ後に、ステップ３１８で処理すべき意味ノードはもはやなく、図３のプロセスがステップ３２２で継続し、そこで、最も高いスコアリングの構造がコマンド識別子２２２によって検査されて、それがコマンド構造であるかどうかを判定される。コマンド構造は、スキーマ２００内に「Ｔｒｕｅ」が設定されている「コマンド」属性をもったエンティティによって進められるであろう。最も高いスコアリングの意味構造がコマンド構造である場合、構造は、テキストによって表されるコマンドとしてステップ３２４で戻される。
【００７０】
最も高いスコアの意味構造がステップ３２２でコマンドエンティティでない場合、コマンド識別子２２２は、ステップ３２６で最も高いスコア構造を受け入れることができるコマンドを識別することを試みる。最も高いスコア構造は、次に、これらのコマンド構造の各々の中に組み込まれ、コマンド構造は、ステップ３２８でスコアリングされる。最も高いスコアリングコマンド構造は、次に、テキストによって表されるコマンドとして戻される。
【００７１】
本発明を特定の実施形態を参照して説明しているが、この技術分野の当業者であれば、本発明の精神及び範囲を逸脱せずに形式及び詳細に変更を加えることができることを認識するであろう。特に、スコアリング機能は、本発明の範囲内で変更され結合され得る。
【図面の簡単な説明】
【００７２】
【図１】本発明を実施できる１のコンピューティング環境のブロック図である。
【図２】入力テキストから意味構造を識別するシステムのブロック図である。
【図３】本発明の一実施形態による意味構造を識別する方法のフロー図である。
【図４】本発明の一実施形態による意味型、マルコフ確率及び意味規則を定義するスキーマの一部の例を示す図である。
【図５】入力テキストからの意味エンティティの生成を示す図である。
【図６】図５の意味エンティティにおける各種意味規則の結果を示す図である。
【図７】図５の第１の２つの意味エンティティから形成される初期の意味構造を示す図である。
【図８】ＴｉｍｅＥｎｔｉｔｙ意味エンティティを追加した保有された意味構造を示す図である。
【図９】ＳｈｏｗＦｌｉｇｈｔエンティティを追加した保有された意味構造を示す図である。
【図１０】ＡｉｒｌｉｎｅエンティティとＦｌｉｇｈｔエンティティを追加した保有された意味構造を示す図である。
【符号の説明】
【００７３】
１３０    システムメモリ
１３４    オペレーティングシステム
１３５    アプリケーションプログラム
１３６    他のプログラムモジュール
１３７    プログラムデータ
１２０    処理ユニット
１９０    ビデオインタフェース
１９５    出力周辺インタフェース
１９１    モニタ
１９６    プリンタ
１９７    スピーカ
１４０    非着脱式不揮発性メモリインタフェース
１５０    着脱式不揮発性メモリインタフェース
１６０    ユーザ入力インタフェース
１７０    ネットワークインタフェース
１７１    ローカルエリアネットワーク
１４４    オペレーティングシステム
１４５    アプリケーションプログラム
１４６    他のプログラムモジュール
１４７    プログラムデータ
１７２    モデム
１６２    キーボード
１６１    ポインティングデバイス
１６３    マイクロホン
１７３    広域ネットワーク
１８０    リモートコンピュータ
１８５    リモートアプリケーションプログラム
２００    スキーマ
２０２    意味型及び確率
２０４    マルコフ確率
２０６    意味規則
２０８    テーブル構造
２１０    意味構造テーブル
２１２    テキスト
２１４    意味エンティティ識別子
２１６    構造ジェネレータ
２１８    構造スコアリング
２２０    刈り込み
２２２    コマンド識別子
【図１】
2005115922.tif 000005
【図２】
2005115922.tif 000006
【図３】
2005115922.tif 000007
【図４】
2005115922.tif 000008
【図５】
2005115922.tif 000009
【図６】
2005115922.tif 000010
【図７】
2005115922.tif 000011
【図８】
2005115922.tif 000012
【図９】
2005115922.tif 000013
【図１０】
2005115922.tif 000014