(57)【要約】【課題】文書フォーマットを共通の所定フォーマットに変換する変換ツールを提供する。【解決手段】構造化されていない入力文書を、構造化された文書に変換する文書プロセッサであって、文書プロセッサが、入力文書のフラグメントを終端要素の集合に関して分類する分類器１４と、終端要素集合と非終端要素の集合とから選択された要素に適用する書換え規則を定義する確率文法２２と、入力文書フラグメントを、確率文法に適合させ、非終端要素のリンクで接続された終端要素に関連付けさせる、構文解析された文書構造を定義するパーサ４２とを備え、構文解析された文書構造が構造化された文書を作成するのに使用される。【選択図】図２
2007012059.tif 000002
【特許請求の範囲】
【請求項１】
構造化されていない入力文書を、構造化された文書に変換する文書プロセッサであって、前記文書プロセッサが、
前記入力文書のフラグメントを終端要素の集合に関して分類する分類器と、
前記終端要素集合と非終端要素の集合とから選択された要素に適用する書換え規則を定義する確率文法と、
入力文書フラグメントを、前記確率文法に適合させ、非終端要素のリンクで接続された終端要素に関連付けさせる、構文解析された文書構造を定義するパーサとを備え、
前記構文解析された文書構造が、前記構造化された文書を作成するのに使用されることを特徴とする文書プロセッサ。
【請求項２】
請求項１に記載の文書プロセッサにおいて、
前記分類器が、各入力文書フラグメントに対し、終端要素集合の諸要素に対応する確率値を割り当てる確率分類器から成り、
前記パーサが、前記確率文法から導出された（i）前記関連終端要素の確率値と（ii）前記非終端要素の接続リンクの確率値とで定まる同時確率に関して、前記構文解析された文書構造を最適化する同時確率最適化器を備えることを特徴とする文書プロセッサ。
【請求項３】
請求項２に記載の文書プロセッサにおいて、前記確率文法が確率文脈自由文法であり、前記同時確率最適化器が修正インサイド／アウトサイド最適化法を採用することを特徴とする文書プロセッサ。
【請求項４】
請求項２に記載の文書プロセッサが、構文解析された文書構造に適合するXML構造を備えるXML文書として前記入力文書を編成するXMLアノテータをさらに備えることを特徴とする文書プロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、入力文書を構造化された文書に変換する改良された文書プロセッサに関する。
【背景技術】
【０００２】
文書の収集は、ビジネス界、政府、およびその他の組織で行われ、維持されている。このように収集された文書は、一般に、インターネットやローカルコンピュータネットワークなどを経てアクセス可能である。文書は、ワードプロセッシング式フォーマット、表計算式フォーマット、アドビ(ADOBE)（登録商標）ポータブル文書フォーマット（PDF）、ハイパーテキストマークアップ言語（HTML）などの多様かつ多岐にわたるフォーマットで作成されている。
【０００３】
これらの多様なフォーマットの文書を共通の構造化されたフォーマットに変換することは、ある種の利点を有する。PDFやHTMLは、プラットフォームに依存しないフォーマットであって、コンピュータプラットフォーム間で文書変換が可能となる。しかし、PDFやHTMLは、文書の再利用や再構成を容易に行うにはそれほど効果的ではない。例えば、HTMLマークアップタグは、ツリー構造を構成する複雑な文書を作成するには、非常に効果的だとはいえない。さらに、PDFもHTMLも、厳格な文書フォーマット構造要件を課していない。  例えば、妥当なHTML文書は、終了タグが落ちていても、あるいはその他のフォーマット上の欠陥があっても差し支えないのである。
【０００４】
拡張可能なマークアップ言語（XML）は、厳格な文書フォーマット構造要件を課す文書型定義（DTD）部分を含んでいる。また、このDTDは、複雑な入れ子構造または木構造をサポートしている。従って、XMLは、文書の再利用、再構成、および交換に好適な共通文書フォーマットと認められつつある。XMLとともに、他の構造化されたフォーマット、例えば、構造化スキーマまたは他の明快な編成を含む他の構造化されたフォーマットを使用して、共通な構造化された文書フォーマットを提供することができる。
【０００５】
【非特許文献１】Berger et al., A maximum entropy approach to natural language processing, Computational Linguistics, 22(1):39-71, 1996
【非特許文献２】Chung et al., "Reverse Engineering for Web Data: From Visual to Semantic Structures," IEEE Computer Society, 2002
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従って、ワードプロセッシング、表計算、PDF、HTML、および他のタイプの文書フォーマットを共通のXMLまたは他の構造化されたフォーマットに変換する堅牢かつ柔軟な変換ツールを提供する強い動機が存在する。しかし、既存の変換ツールは、通常、ソース文書の構造について強固な仮定を設定しているので、これらの変換ツールは、文書の小さな部分集合に限って有効となっている。
【課題を解決するための手段】
【０００７】
幾つかの実施の形態に基づいて、文書プロセッサが本明細書に開示される。分類器により、入力文書のフラグメント（断片；fragment）が終端要素の集合に関して分類される。確率文法により、終端要素の前記集合と非終端要素の集合とから選択された要素に適用する書換え規則が定義される。パーサ（構文解析器；parser）により、構文解析された文書構造が定義され、入力文書フラグメントが、確率文法に適合して、非終端要素のリンクで接続された終端要素に関連付けされる。構文解析された文書構造は、入力文書を系統的に編成するために使用される。
【０００８】
幾つかの実施の形態に基づいて、文書をプロセッシングする方法が本明細書に開示される。入力文書のフラグメントが終端要素の集合に関して分類される。分類されたフラグメントが、構文解析され、構文解析された文書構造が決定され、前記フラグメントが、確率文法に適合して、非終端要素のリンクで接続された終端要素に関連付けされる。入力文書は、構文解析された文書構造に適合するXML構造を備えるXML文書として編成される。
【０００９】
幾つかの実施の形態に基づいて、文書プロセッサが本明細書に開示される。パーサにより、リーフ（葉；leaf）をラベル付けする終端要素の集合と、ノード（節；node）をラベル付けする非終端要素の集合と、書換え規則の集合とを備える文法を使用して文書が構文解析される。構文解析により、文書のフラグメントに対する終端要素ラベルと終端要素ラベルを結合するノード木とを含み、そして書換え規則に適合する、構文解析された文書構造が作成される。アノテータ（注釈付け器；annotator）により、構文解析された文書構造に基づく構造情報で前記文書をアノテーション（注釈付け；annotation）する。
【００１０】
本発明の１つの態様によれば、構造化されていない入力文書を、構造化された文書に変換する文書プロセッサであって、前記文書プロセッサが、前記入力文書のフラグメントを終端要素の集合に関して分類する分類器と、前記終端要素集合と非終端要素の集合とから選択された要素に適用する書換え規則を定義する確率文法を記憶するメモリと、入力文書フラグメントを、前記確率文法モジュールに適合させ、非終端要素のリンクで接続された終端要素に関連付けさせる、構文解析された文書構造を定義するパーサとを備え、前記構文解析された文書構造が、前記構造化された文書を作成するのに使用されることを特徴とする。
【発明を実施するための最良の形態】
【００１１】
図１を参照する。分類器トレーナー１０は、文書の調整セット（training set）１２を受理する。調整セット１２の各文書は、トリプレット(x,y,d)として好適に表される。ここで、x={xi}は、調整文書のフラグメント（文字片；fragment）xiの列であり、y={yi}は、フラグメントxiをラベル付けする終端要素yiの列であり、dは、構造ツリーの内部ノードを表す。文書フラグメントxiは、調整文書のリーフ、例えば、段落、脚注、後注などである。図示の例では、調整文書はHTML文書であるが、他の標準フォーマットも、入力文書フォーマットとして使用できる。
【００１２】
本明細書に記載される文書編成は、文書構造(y,d)と自然言語構文解析に使用される文法構造との間に存在する強いアナロジーに基づいて行われる。自然言語構文解析では、文または他の自然言語表現xは、(y,d)として構文解析し得る。ここでイタリック体は、自然言語処理におけるアナロジー状況に係わるパラメータを表すのに使用するものである。自然言語表現x={xi}は、単語xiの秩序ある列から構成され、例えば、英語、フランス語、または他の自然言語の文を構成するものである。パラメータy={yi}は、単語xiに対する語彙的カテゴリーラベルまたは終端要素ラベルの列を表す。これらの終端要素ラベルは、例えば、名詞、動詞、形容詞、副詞などである。パラメータdは、高次レベルの句または非終端語彙的カテゴリー、例えば、名詞句、動詞句、文などの構造化構文解析を表す。
【００１３】
アナロジーで考えると、文書は、文書フラグメント、例えば、段落、タイトル、脚注、著者表示などで定義されたリーフで構成される。構造化された文書では、リーフまたはフラグメントは、ある種の文書構造化規則に基づいて高次レベルノード構造で共にリンクされる。XMLの場合は、文書型定義（DTD）が文書構造化規則を提供し、これは、自然言語構文解析の文法にアナロジーなものである。
【００１４】
図１を再び参照する。分類器トレーナー１０は、確率分類器１４または他のタイプの分類器を適切に調整し、文書フラグメントxiを適切な終端要素ラベルyiで分類する。調整セット１２は、プレ分類された文書フラグメントを有する。すなわち、調整セット１２の各文書フラグメントxiは、対応する終端要素ラベルyiでプレ分類されている。従って、確率トレーナー１０は、確率分類器１４を適切に調整し、調整セット１２のフラグメントxiの実質的に正確な分類が確実に行われる。その後、調整を受けた分類器１４を使用して、未分類の文書フラグメントを分類することが可能となる。
【００１５】
図示の実施の形態では、確率分類器１４が使用される。好適な確率分類器の一つは、例えば、Berger et al., A maximum entropy approach to natural language processing, Computational Linguistics, 22(1):39-71, 1996に記載されているような最大エントロピー型分類器である。他の確率分類器、例えば、単純ベイズ(Naive-Bayes)型分類器も使用できる。確率分類器は、入力文書フラグメント列ｘが所与のとき、終端要素列ｙの確率を示す確率値p(y|x)を割り当てる。確率的分類器が図示されているけれども、決定性分類器も使用し得る。決定性分類器は、確率分布を与える分類でなく「最も可能性の高い」分類を行う。従って、決定性分類器は、所与の入力文書フラグメント列xに対して、確率p(y|x)を出力するのではなく、特定の終端要素列yを出力する。
【００１６】
調整セット１２は、また、文法導出モジュール２０で処理され、確率文脈自由文法２２を導出する。自然言語文脈では、文法は、４-タプル（T,N、Start,R）として表すことができる。ここで、Ｔは終端要素（例えば、名詞、動詞、形容詞など）の集合で、Nは非終端要素（例えば、名詞句、動詞句、文など）の集合で、Startは構文解析の始点（例えば、文の初めを示す大文字）で、Rは書換え規則（例えば、S→NPVP（Sは文を示し、NPは名詞句を示し、VPは動詞句を示す）、NP→ART ADJ N(ARTは冠詞を表し、ADJは形容詞を表し、Nは名詞を表す)など）の集合である。
【００１７】
自然言語処理に使用される確率文脈自由文法は、XML文書の文書型定義（DTD）に、または他のタイプの構造化された文書フォーマットの構造スキーマに容易に類似化される。XML文書のDTDは、自然言語文書の構文解析に使用される文法の書換え規則に極めて類似な方法で文書のノードまたはリーフを接続する規則を定義する。従って、自然言語処理のために開発された高次に展開・自動化された確率文脈自由文法に基づいた構文解析技法を、本発明では適用し、XMLまたは他の構造化された文書フォーマットに文書変換を行う。文書フラグメントは、自然言語構文解析において品詞ラベルで単語をラベル付けするのと類似な方法を使用して終端要素でラベル付けされる。一方、高次レベルでリンクされたXML文書ノードは、自然言語文を句または高次レベルの構文解析構造句に構文解析するのと類似な方法で構造化される。なお、確率文脈自由文法は、例えば、文書プロセッサが備えるメモリに、文書プロセッサが実行可能な言語処理プログラムとして予め記憶しておく。
【００１８】
従って、文書編成に使用される確率文脈自由文法２２は、４-タプル（T,N,Start,R）として好適に表される。終端要素Tの集合は、終端要素ラベル、例えば、「段落」、「著者」、「タイトル」、「脚注」などを含み、文書のフラグメントxiをラベル付けするのに使用し得る。非終端要素Nの集合は、構造化された文書のノードに使用されるラベルであり、例えば、「本」、「巻」、「章」、「節」などを含み得る。始点Startは、文書が、例えば、電子本（すなわち「e-book」）の場合は、「本」とし得る。文法書換え規則Rは、p:A→αとして好適に表される。ここに、Aは非終端要素を示し（すなわち、Aは集合Nに属する）、α={αi}は終端または非終端要素の列であり（すなわち、要素αiは集合T∪Nに属する）、pは、書換え規則が適用可能な確率を表す。確率ｐは、０〜１の範囲である。所与の非終端要素Aに対し、左側の非終端要素に関するすべての規則に対する確率値ｐは、一般に、合計が１になるように正規化される。
【００１９】
文法導出モジュール２０は、文書型定義（DTD）または他の文書構造スキーマの導出に好適な技法を使用して、確率文脈自由文法２２を導出することができる。好適なアプローチの一つは、Papakonstantinou et al., DTD Inference for Views of XML Data, In Proc. of 19 ACM Symposium on Principles of Database Systems (PODS), Dallas, Texas (2000), pp. 35-46に記載されている。別法としては、DTDスキーマ２６がすでに使用可能ならば、文法導出モジュール２０は確率文脈自由文法２２をDTDスキーマ２６から直接抽出可能である。
【００２０】
幾つかの実施の形態では、書換え規則に対する確率は、調整セット１２から次のように計算される。書換え規則A→αに対し、確率p:A→αは次のように好適に計算される。
【００２１】
【数１】
2007012059.tif 000003
【００２２】
式中、count(A→α)は、調整セット１２中に表れる書換え規則A→αの頻度数であり、一方、式（１）の分母は、確率文法２２の書換え規則Rの集合中に表れるすべての書換え規則の頻度数である。
【００２３】
図２を参照する。図２に示された装置は、図１の装置で作成された確率分類器と確率文脈自由文法とを使用する構文解析を採用し、XMLを注釈付けまたは構造化するのに使用される構文解析された文書構造を決定する。ここでは、確率分類器１４と確率文脈自由文法２２とを使用して、入力文書３０を編成する。入力文書３０は、HTMLのような標準化されたフォーマットでフォーマットされている。入力文書３０としては、構造化されていないものや半構造化されたもの、例えば、タブ、空白、識別された中心揃えヘッダ、または他の文書特性に基づいてフラグメントまたはテキストグループに分割することによって得られたものがある。適切ならば、ソース文書３２は最初、HTMLコンバータ３４でHTML入力文書フォーマットに変換される。例えば、ソース文書３２がPDF文書の場合、HTMLコンバータ３４は、商業的に使われているPDF/HTMLコンバータが好適である。
【００２４】
入力文書３０は、確率分類器１４で処理され、確率値が文書フラグメントに割り当てられ、従って、確率的に分類された終端要素ラベル４０が生成される。確率分類器１４は、文書フラグメントxiに対しp(yｉ|xｉ)の形の確率値を出力する。別に、幾つかの実施の形態では、決定性分類器を使用することもできる。この場合、文書フラグメントxiに対応する最も可能性の高い終端要素ラベルyiが出力される。
【００２５】
パーサ４２は、確率的に分類された終端要素ラベル４０に基づいて入力文書３０の構文解析を行う。図示の実施の形態では、パーサ４２は、チョムスキー(Chomsky)標準形を使用する。この場合、書換え規則はA→B CまたはA→bの形のバイナリ書換え規則である。ここで、A、B、およびCは、非終端要素Nの集合に属する非終端要素であり、bは、終端要素Tの集合に属する終端要素である。A→B C Dの形の非バイナリ文法書換え規則は、バイナリ規則A→B PとP→C D のペアとしてチョムスキー標準形で好適に表される。ここで、Pは、非終端要素Ｎの集合に属する「プレースホルダ（場所取り；placeholder）」非終端要素である。従って、チョムスキー標準形で構文解析すると、バイナリのノードツリー４４が作成される。
【００２６】
図２を引き続き参照し、図３も少し参照する。ランク付けプロセッサ４８は、プレースホルダ非終端要素Pを取り除くことによってバイナリのノードツリー４４のノードをランク付けする。図３で例示するのは、A→B PとP→C Dをランク付けしてランク付けされたノードツリー５２を生成するプロセスである。
【００２７】
図２を引き続き参照する。XMLアノテータ６０は、ランク付けされたノードツリー５２と確率文法２２に基づいて構成された文書構造を有する構造化されたXML文書６２、または他の構造化された文書を作成する。構造化されたXML文書６２は、確率文法２２から導出された文書型定義（DTD）や文書スキーマなどを含み、ランク付けされたノードツリー５２に対応する構文解析された文書構造を有する。
【００２８】
以上では、図１〜図３を参照して示された文書編成法を記載したので、次は文書編成法の幾つかの例を具体的に説明する。
【００２９】
アプローチの一つでは、様々な可能な終端要素ラベル列yに対する確率p（y|x）を最初、最大化し、入力文書３０に対する最も可能性の高い終端要素ラベルyを決定する。次にパーサ４２が、終端要素yの最適化された列を構文解析し、確率文法２２で与えられた様々な書換え規則の確率に基づいてノードツリーdを決定する。ノードツリーdの最適化は、例えば、Lari et al., The estimation of stochastic context-free grammars using the inside-outside algorithm, Computer Speech and Language, 4:35-56, 1990 に記載のインサイド／アウトサイド最適化法を使って行うことができる。
【００３０】
しかし、終端要素ラベルを先ず適用し、その後にツリー構造の構文解析を行うという、この逐次的アプローチは、堅牢性が限定されるという欠点が見出されている。例えば、最も可能性の高い終端要素ラベル列は、確率文法２２を使って達成される構文解析には適合しないこともあり得る。堅牢性の改良は、少数の最善と思われる列yをランク付けし、これら最善と思われる列y各々に対して最適化されたノードツリーを決定し、次いで最大の同時確率p(yr|x)・p(dr|yr,G)を選択することによって達成できる。ここで、p(yr|x)は、フラグメント列xが所与のとき、yrと記された終端要素ラベルのランク付けされた列の確率で、p(dr|yr,G)は、終端要素ラベル列yrと文法Ｇ２２とが所与のとき、ノードツリーdrの確率である。後者の確率p(dr|yr,G)は、終端要素ラベルyrの列からdrを得るために使用された確率文法２２の書換え規則の諸確率を共に乗算することによって計算される。
【００３１】
他の一つのアプローチでは、確率p (y|x)が、確率p(d|y,G)と同時に最適化される。すなわち、終端要素yの列とノードツリーdとは、同時に最適化される。好適なアプローチの一つでは、同時確率p(d,y|G,x)が、最適化される。ここで、Gは文法２２を表す。ベイズ原理を適用すると、次式で表される。
【００３２】
【数２】
2007012059.tif 000004
【００３３】
ここで、p（y|x）は、フラグメント列ｘが所与のとき、終端要素列yの確率であり、p（d|y、G）は、終端要素列ｙと文法Ｇ２２とが所与のとき、パースdの確率である。式（２）で与えられる同時確率を最大化すると、次式が得られる。
【００３４】
【数３】
2007012059.tif 000005
【００３５】
確率分類器１４は、様々な確率分類アルゴリズムを使用して確率p(y|x)を計算することができる。幾つかの実施の形態では、最大エントロピー型確率分類アルゴリズムが使われる。このアプローチでは、データから確率分布を予測する最良のモデルは、調整セット１２から導出されたある種の制約と整合するが、他は限定的な仮定となるものである。確率のフレームワークでは、これは、最大のエントロピーを有し、均一分布に最も近い分布を選択することに対応する。最大エントロピー型確率分類器に組み入れられた各制約は、調整セット１２の選択された特性を示すが、この特性は、学習された分布にも存在するはずである。各制約は、バイナリ機能に基づき、モデルの機能の期待値が調整データのその期待値と等しくなるように制約する。各機能は、好適にはバイナリの機能であり、終端ラベル列yと、入力フラグメント列xの選択された特性に依存し得る。文書構造化に対しては、コンテンツ機能の選択は、文書リーフに含まれるテキストの特性、例えば、例示の特性f1(y,x)を示すように行うことができる。f1(y,x)は、終端要素ラベルyが「タイトル」で、xが数字だけを含む場合は１に等しく、それ以外は0に等しい。上記コンテンツ機能の選択は、また、ツリー文脈を特性付けるように行うことができる。例えば、別の一つの例示の特性f2(x,y)は、終端要素ラベルyが「著者」で、フラグメント列xのペアレントがSPANである場合は、１に等しく、それ以外は0に等しい。
【００３６】
xとyに関数として依存する選択された機能に基づく制約下、最大エントロピー方法を使用して、p（y|x）の条件付き尤度が最大化され、対数線形モデルとして以下に好適に表される。
【００３７】
【数４】
2007012059.tif 000006
【００３８】
式中、 λαは、確率分類器１４の調整で最適化される制約fα(x,y) に対応するスカラで、Zα(x) は確率の和が１となるように正規化するファクタで、次式で示される。
【００３９】
【数５】
2007012059.tif 000007
【００４０】
上記の最大エントロピー型確率分類器は、単なる一例である。他の確率分類器、例えば、単純ベイズ分類器も使用することができる。
【００４１】
前に戻って図１を参照する。ここには、より具体的な文書編成の例が記載されている。文書型定義（DTD）２６の一例は以下の通りである。
<!ELEMENT Book (author, Section+)>
<!ELEMENT Section (title, (para | footnote)+)>
<!ELEMENT author (#PCDATA)>
<!ELEMENT title (#PCDATA)>
<!ELEMENT para (#PCDATA)>
<!ELEMENT footnote (#PCDATA)>
【００４２】
上記のスキーマ定義をチョムスキー標準形にすると、エキストラの非終端要素が導入される。この例示のDTDから文法導出モジュール２０で導出される好適な対応する確率文法２２はG=(T,N,Start,R)である。ここで、終端要素T={author, title, para, footnote}で、非終端要素集合N= {Book, Author, Sections, Section, Title, Elements, Element} (ここで "Elements" と"Element" とは、バイナリ書換え規則を可能とする、導入されたプレースホルダ非終端要素である)で、Start=Bookであり、バイナリ書換え規則 R は下記の規則を含む。
Book → Author Section | Author Sections
Sections → Section Section | Section Sections
Section → Title Elements | Title Element
Elements → Element Element | Element Elements
Author → author
Title → title
Element → para | footnote
【００４３】
記法上の明確さを図るため、集合Nの非終端要素は大文字で始めるが、一方、集合Tの終端要素の頭は大文字で書かない。文法導出モジュール２０は、また、例えば、式（1）を調整セット１２に適用することによって、調整セット１２に発生する頻度に基づいて多様な書換え規則に対する確率を導出し、次の確率の一例が生成される。
Book → Author Section (p=0.3) 
Book → Author Sections (p=0.7)
Sections → Section Section (p=0.4) 
Sections → Section Sections (p=0.6)
Section → Title Element (p=0.2)
Section → Title Elements (p=0.8)
Elements → Element Element (p=0.4)
Elements → Element Elements (p=0.6)
Author → author (p=1.0)
Title → title (p=1.0)
Element → para (p=0.8)
Element → footnote (p=0.2)
ここで、各書換え規則に対する括弧内(p=…)の数字は確率を示す。 
【００４４】
さらに、分類器トレーナー１０は、調整セット１２を使用して、分類器Cと記された確率分類器１４に調整を行う。フラグメントまたはリーフの列x=｛x1,x２,x３,x４,x５｝を含む文書の一例に対して、分類器Cは、以下の終端要素ラベル付け確率を与えるとする。
【００４５】
【表１】
2007012059.tif 000008
【００４６】
ここで、各フラグメントに対する最も高い確率は、太字体で示される。従って、分類器Cの出力だけを考慮すると、最も可能性の高い終端要素列は、ymax={タイトル, タイトル, 段落, 脚注, タイトル}で、最も高い確率p(ymax)=0.4×0.4×0.5×0.4×0.3=0.0096を有する。しかし、この終端列ymaxは、文法Gを参照せずに分類器Cだけを使用しただけで導出されたので、文法Gに対応する構文木を有しない。
【００４７】
図４Ａと４Ｂは、フラグメントの列x={x1,x2,x3,x4,x5}を有する文書の一例に対する二つの妥当な構文解析された文書構造(y1,d1)と(y2,d2)をそれぞれ示す。終端要素ラベルの列y２={著者(author),タイトル(title),段落(para),タイトル(title),段落(para)}を有する構文解析された文書構造(y2,d2)と、構文解析された構造d2=（Book(Author Sections(Section(Title Element) Section(Title Element)))とによって、式（２）の同時確率p(y,d|x,G)が最大化される。特に、p(y2|x)=0.3×0.4×0.5×0.3×0.2=0.0036で、一方、p(d2|y2,G)は、構造d2に使用された書換え規則の確率を共に乗算することによって計算される。すなわち、下記の通りである。
p(d2|y2,G) =  Book → Author Sections (p=0.7) ×
Author → author (p=1.0) ×
Sections → Section Section (p=0.4) ×
Section → Title Element (p=0.2) ×
Title → title (p=1.0) ×
Element → para (p=0.8) ×
Section → Title Element (p=0.2) ×
Title → title (p=1.0) ×
Element → para (p=0.8) = 0.007172
【００４８】
よって、p(y2|x) × p(d2|y2,G) = .0036 × 0.007172=2.58×10-5として同時確率が与えられる。比較すると、図４Ａの構文解析された文書構造(y1,d1)の同時確率は、これより低く、約0.885×10-5である。 従って図４Ｂの構文解析された文書構造(y2,d2)が文書ｘに対して選択される。
【００４９】
幾つかの実施の形態では、決定性分類器は、文書フラグメントまたはリーフの入力列xに対して終端要素ラベルの具体的列yを与える。次にパーサは、終端要素ラベルのその列yに対して最も可能性の高い構文解析された文書構造dを決定する。好適なアプローチでは、インサイド／アウトサイド型アルゴリズムが使用される。このアルゴリズムは、二つの条件付き確率を定義し、隠れマルコフ（Markov）モデルのビタビ（Viterbi）アルゴリズムに対する前向き／後向き確率と概念的に同じである。所与の文法G=（T,N,Start,R）と、所与の終端列yに対して、インサイド／アウトサイド型アルゴリズムは、yのあるサブ列に跨り、非終端要素の集合Nの一要素のある非終端要素Aの所でルートとなる最高確率の部分構文木としてインサイド確率を定義する。インサイド確率I(A,i,j)は、次式で適切に与えられる。
【００５０】
【数６】
2007012059.tif 000009
【００５１】
ここで、yijは、インデックスiから始まりインデックスjで終わる可能な終端サブ列yに跨るランダム変数で、Aijは、非終端 Aがインデックスiから始まりインデックスjで終わる終端サブ列に跨る部分構文木のルートである事象である。インサイド確率は、非終端 Aがパースで展開され得るすべての可能なやり方について最大値を取ることによって、再帰的に計算される。
【００５２】
【数７】
2007012059.tif 000010
【００５３】
再帰計算は、I(A,k,k) = p(A→yk) で始まり、I(Start, 1, n) で終わり、ｙに対する最尤度のパースとして次式を与える。
【００５４】
【数８】
2007012059.tif 000011
ここで、n は、観察列xと終端列yの長さである。
【００５５】
具体的な終端要素ラベル列yでなく、確率分布p（y|x）を与える説明中の確率分類器１４では、最適化は、yとdの最適化を結合することで適切に行われる。すなわち、最大尤度の構文解析された文書構造（y,d）は、式（２）の同時確率p（y,d|x,G）を最大化するものである。幾つかの実施の形態では、この最適化は、最尤度の構文解析された文書構造（y,d）を見出すために拡張された修正インサイド／アウトサイドアルゴリズムを使って行われる。ydインサイド確率は、インデックスiから始まりインデックスjで終わるサブ列yと、サブ列yijに跨り非終端要素Aの所にルートを有する最も可能性の高い部分構文木とに係わる最高の同時確率として定義される。すなわち、次式で定義される。
【００５６】
【数９】
2007012059.tif 000012
【００５７】
ｙdインサイド確率は、非終端 Aがパースで展開され得るすべての可能なやり方について最大値を取ることによって、再帰的やり方で計算される。すなわち、次式で計算される。
【００５８】
【数１０】
2007012059.tif 000013
【００５９】
確率p（y|x）について単純化のために独立仮定を行うことができる。すなわち、q, i<q<j, に対して、p(yij|x)=p(yiq|x)×p(yq+1j|x)を仮定する。この単純化を行うことによって、式（10）は次式のように書き直すことができる。
【００６０】
【数１１】
2007012059.tif 000014
【００６１】
これは、さらに次式のように書き直すことができる。
【００６２】
【数１２】
2007012059.tif 000015
【００６３】
再帰計算は、最大尤度のパース(d,y)=argmax(y,d) p(d,y|G,x)を与えるIyd(Start,1,n)の所で終了する。すなわち、次式で表される。
【００６４】
【数１３】
2007012059.tif 000016
【００６５】
初期設定は、終端要素の集合Tに属するすべての終端要素の間にykに対する有力候補を選択することを含む。すなわち、次式で表される。
【００６６】
【数１４】
2007012059.tif 000017
【００６７】
最も確率の高い同時パース(y,d)を見出すアルゴリズムの一例では、最善の同時確率 Iyd(A,i,j)に対するマトリックス bestYD[I,A,j]と、バックリファレンスのマトリックスbacktrace [i,A,j] とを用いると、xに対する最適パース（d,y）の再構成が可能となる。Backtraceマトリックス中の各アイテムは、ペア（r,k）で、Rのr番目の書換え規則が使用され、k位置でスプリットが行われることを示す。以下のアルゴリズムの例では、nは列xの長さ（|x|＝|y|に留意のこと）で、|N|は非終端要素の数で、p(yk|x)は文書フラグメントxkに対する終端要素ykの確率である。同アルゴリズムは次の通りである。
【表２】
2007012059.tif 000018
bestYD［１,Ｓ,ｎ］は、最も確率の高いパース（y,d）を返す。
Backtrace［１,Ｓ,ｎ］は、xに対する最も確率の高いパース（y,d）の軌跡を保つ。
【００６８】
上記アルゴリズム例の計算の複雑性を評価するために、二つの最上位ループを解析する。第一のfor ループは、非終端要素の集合Ｎにある各非終端要素Aに対するすべての終端確率を比較することによって、最適値bestYD［k,A,k］を設定する。次ぎに第二のfor ループは、インサイド／アウトサイドアルゴリズムと等しい方法でbestYDマトリックスのセルを満たす。従って、全アルゴリズム複雑性はO(n3・ |N|3 + n2 ・ |T | ・ |N|)である。
【図面の簡単な説明】
【００６９】
【図１】XMLに変換される文書の編成、または注釈付けを行うのに使用するのに好適な確率分類器と確率文脈自由文法とを作成する装置を示す概略図である。
【図２】ソース文書をXMLに変換する装置を示す概略図である。
【図３】プレースホルダ非終端要素「P」を使って構造化されたバイナリ構文木の一例のランク付けを示す図である。
【図４Ａ】フラグメント列x={x1,x2,x3,x4,x5}を有する文書の一例に対して妥当な構文解析された文書構造(y1,d1)を示す図である。
【図４Ｂ】フラグメント列x={x1,x2,x3,x4,x5}を有する文書の一例に対して妥当な構文解析された文書構造(y2,d2)を示す図である。
【符号の説明】
【００７０】
１０  分類器トレーナー、１２  調整セット、１４  確率分類器、２０  文法導出モジュール、２２  確率文脈自由文法、２６  DTDスキーマ、３０  入力HTML文書、３２  ソース文書、３４  HTMLコンバータ、４２  パーサ、４４  バイナリノードツリー、４８  ランク付けプロセッサ、５２  ランク付けされたノードツリー、６０  XMLアノテータ、６２  構造化されたXML文書。
【図１】
2007012059.tif 000019
【図２】
2007012059.tif 000020
【図３】
2007012059.tif 000021
【図４Ａ】
2007012059.tif 000022
【図４Ｂ】
2007012059.tif 000023