JPH1166070A - 構文解析装置 - Google Patents

Abstract

(57)【要約】 【課題】 品詞付与のための辞書を用いることなく、従
来例に比較して正確に自動的に品詞を付与することがで
き、しかも素性構造付き文脈自由文法などの詳細な構文
構造の情報を付与することはできる構文解析装置を提供
する。 【解決手段】 決定木学習装置１０は、構文解析済みテ
キストデータに基づいて、所定の複数の属性を用いて、
各属性の属性値に依存して分割されるような二分木形式
の木構造をそれぞれ有する、品詞付与のための品詞決定
木、文法規則付与のための文法規則決定木、及び処理方
向決定木を生成し、非分割ノードのリーフノードに対し
て各複数のカテゴリーに対する頻度確率を計算して付与
し頻度確率付き各決定木を生成する。構文情報付与装置
１１は、各決定木を用いて、入力されるテキストデータ
に対して最大の結合確率を有する品詞列を得るように品
詞を付与しかつ構文情報を付与する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、文字列を含む文章
のテキストデータに対して、構文構造決定用の確率付き
決定木を用いて、構文構造を自動的に付与する構文解析
装置に関する。

【０００２】

【従来の技術】従来、比較的精度のよい品詞付与システ
ム（以下、第１の従来例という。）が、従来技術文献１
「E.Brill et al.,“Some Advances in Transformation
--Based Part of Speech Tagging",Proceedings of the
Twelfth National Conferenceon Artificial Intellig
ence,pp.722-727,AAAI,1994年」及び従来技術文献２
「B.Merialdo et al.,“Tagging English Text with a
Probabilistic Model",Computational Linguistics,20-
2,pp.155-171,1994年」において報告されている。この
従来例の品詞付与システムにおいては、単語表記とその
表記のとる品詞ラベルの組を記述した、品詞付与のため
の辞書を参照することによりテキストデータに対して品
詞を付与している。

【０００３】この第１の従来例の品詞付与システムにお
いては、辞書を用いて品詞を付与しているために、辞書
項目に記載されていない未知語に対する品詞付与は難し
く、また、単語と品詞ラベルとの未知の組合せに対する
処理は難しいという問題点があった。さらに、使われる
品詞体系の変更により辞書のメンテナンスを行う必要が
あるという問題点があった。また、辞書を使用しない
で、ヒューリスティックスにより（発見的に又は経験的
に）単語に対する品詞ラベルを割り当てている品詞付与
装置もあるが、品詞付与の正解率は比較的低いという問
題点があった。

【０００４】以上の問題点を解決するために、本特許出
願人は、特願平８−２３２９９３号の特許出願におい
て、品詞付与のための辞書を用いることなく、第１の従
来例に比較して正確に自動的に付与することができる品
詞付与装置（以下、第２の従来例という。）を開示して
いる。この第２の従来例の品詞付与装置は、（ａ）単語
列からなる品詞付与済みテキストデータに基づいて、各
単語の綴りの特徴と、文章内の使われ方による特徴と、
単語の相互情報量を用いた階層的な分類とを含む複数の
属性を用いて、上記各属性の属性値に依存して分割され
るような二分木形式の木構造を有し品詞付与のための決
定木を生成し、上記生成された決定木の分割されないノ
ードであるリーフノードに対して複数の品詞に対する頻
度確率を計算して付与することにより、頻度確率付き決
定木を生成する決定木学習手段と、（ｂ）上記決定木学
習手段によって生成された頻度確率付き決定木を用い
て、入力される単語列からなるテキストデータに基づい
て、上記リーフノードに付与された頻度確率の中で上位
複数ｎ個の頻度確率を選択して上記テキストデータの各
単語に対して付与し、上記テキストデータの単語列にお
いて最大の結合確率を有する品詞列を正解品詞列として
決定して出力する品詞付与手段とを備えたことを特徴と
している。

【０００５】

【発明が解決しようとする課題】さらに、英文構文解析
装置として、従来技術文献３「M.J.Collins,“A new st
atistical parser based on bigram lexical dependenc
ies",the 34th Annual Meeting of ACL Proceedings,19
96年」において、構文構造が付与されたテキストデータ
から主要語のバイグラムの統計情報を学習し、構文解析
を行うこと（以下、第３の従来例という。）が開示され
ている。

【０００６】しかしながら、第３の従来例では、素性構
造付き文脈自由文法などの詳細な構文構造の情報を付与
することはできないという問題点があった。

【０００７】本発明の目的は以上の問題点を解決し、品
詞付与のための辞書を用いることなく、従来例に比較し
て正確に自動的に品詞を付与することができ、しかも素
性構造付き文脈自由文法などの詳細な構文構造の情報を
付与することはできる構文解析装置を提供することにあ
る。

【０００８】

【課題を解決するための手段】本発明に係る請求項１記
載の構文解析装置は、単語列からなる構文解析済みテキ
ストデータに基づいて、各単語の綴りの特徴と、文章内
の使われ方による特徴と、単語の相互情報量を用いた階
層的な分類とを含む複数の属性を用いて、上記各属性の
属性値に依存して分割されるような二分木形式の木構造
を有し品詞付与のための品詞決定木を生成し、上記生成
された品詞決定木の分割されないノードであるリーフノ
ードに対して複数の品詞に対する頻度確率を計算して付
与することにより、頻度確率付き品詞決定木を生成する
品詞決定木学習手段と、単語列からなる構文解析済みテ
キストデータに基づいて、処理対象の単語の語数と、処
理対象の主辞単語の品詞、処理対象の直前の単語の品
詞、単語の相互情報量を用いた階層的な分類とを含む複
数の属性を用いて、上記各属性の属性値に依存して分割
されるような二分木形式の木構造を有し文法規則付与の
ための文法規則決定木を生成し、上記生成された文法規
則決定木の分割されないノードであるリーフノードに対
して複数の文法規則に対する頻度確率を計算して付与す
ることにより、頻度確率付き文法規則決定木を生成する
文法規則決定木学習手段と、単語列からなる構文解析済
みテキストデータに基づいて、処理対象の単語の語数
と、処理対象の主辞単語の品詞、処理対象の直前の単語
の品詞、単語の相互情報量を用いた階層的な分類とを含
む複数の属性を用いて、上記各属性の属性値に依存して
分割されるような二分木形式の木構造を有し文法規則付
与処理における各パージング状態で処理方向を決定する
ための処理方向決定木を生成し、上記生成された処理方
向決定木の分割されないノードであるリーフノードに対
して複数の処理方向に対する頻度確率を計算して付与す
ることにより、頻度確率付き処理方向決定木を生成する
処理方向決定木学習手段と、上記品詞決定木学習手段に
よって生成された頻度確率付き品詞決定木を用いて、入
力される処理対象の単語列からなるテキストデータに基
づいて、上記リーフノードに付与された頻度確率の中で
上位複数ｎ個の頻度確率を選択して上記テキストデータ
の各単語に対して付与し、上記テキストデータの単語列
において最大の結合確率を有する品詞列を正解品詞列と
して決定し、次いで、所定のスタック・デコーダ・アル
ゴリズムを用いて、文法規則付与処理における各パージ
ング状態での単語列に対する結合確率が最大の結合確率
を有するパージング状態を選択した後、上記処理方向決
定木学習手段によって生成された頻度確率付き処理方向
決定木を用いて上記処理対象の単語列における処理方向
を決定し、決定された処理方向におけるパージング状態
において、上記文法規則決定木学習手段によって生成さ
れた頻度確率付き文法規則決定木に従って文法規則を上
記処理対象の単語列に加えることにより構文解析情報を
付与して構文解析済みテキストデータを出力する構文情
報付与手段とを備えたことを特徴とする。

【０００９】また、請求項２記載の構文解析装置は、請
求項１記載の構文解析装置において、上記各決定木学習
手段は、上記二分木の形式で分割するときに、上記各属
性による分割前の属性の有効性の優先順位を表わすエン
トロピーＨ₀と分割後のエントロピーＨとの差（Ｈ₀−
Ｈ）が最大の属性を分割候補の属性として選択し、所定
の分割続行基準を満足するときに、二分木の形式で分割
して決定木を更新することを特徴とする。

【００１０】さらに、請求項３記載の構文解析装置は、
請求項２記載の構文解析装置において、上記分割続行基
準は、（Ｉ）選択された属性に基づいて分割したときの
エントロピーの差（Ｈ₀−Ｈ）が所定のエントロピーし
きい値Ｈｔｈ以上であり、かつ（II）選択された属性に
基づく分割後の属性とその属性値及び品詞の組のイベン
ト数が所定のイベント数しきい値Ｄｔｈ以上であること
を特徴とする。

【００１１】またさらに、請求項４記載の構文解析装置
は、請求項１、２又は３記載の構文解析装置において、
上記構文情報付与手段は、上記リーフノードに付与され
た頻度確率の中で上位複数ｎ個の頻度確率を選択して上
記テキストデータの各単語に対して付与した後、所定の
スタック・デコーダ・アルゴリズムを用いて、処理途中
のテキストデータの単語列に対する結合確率が所定の結
合確率以上である品詞候補のみを残して品詞候補を限定
し、品詞付与処理終了時の上記テキストデータの単語列
において最大の結合確率を有する品詞列を正解品詞列と
して決定することを特徴とする。

【００１２】

【発明の実施の形態】以下、図面を参照して本発明に係
る実施形態について説明する。図１は、本発明に係る一
実施形態である、決定木学習装置１０及び構文情報付与
装置１１を備えた構文解析システムのブロック図であ
る。この品詞付与システムは、英語のテキストデータに
対して、品詞付与のための辞書を参照しないで、品詞を
付与した後、素性構造付き文脈自由文法などの詳細な構
文構造の情報を付与することはできる構文解析システム
であって、（ａ）品詞付与済みテキストメモリ２１に格
納された品詞付与済みテキストデータに基づいて、属性
リストメモリ２２に格納された属性リストと、品詞リス
トメモリ２３に格納された品詞リストとを参照して、詳
細後述する品詞決定木学習処理を実行して学習すること
により、頻度確率付き品詞決定木を生成して品詞決定木
ファイルメモリ２５に格納し、次いで、品詞付与済みテ
キストメモリ２１に格納された品詞付与済みテキストデ
ータに基づいて、属性リストメモリ２２に格納された属
性リストと、文法規則リストメモリ２４に格納された文
法規則リストとを参照して、詳細後述する文法規則決定
木学習処理を実行して学習することにより、頻度確率付
き文法規則決定木を生成して文法規則決定木ファイルメ
モリ２６に格納し、さらに、品詞付与済みテキストメモ
リ２１に格納された品詞付与済みテキストデータに基づ
いて、属性リストメモリ２２に格納された属性リスト
と、文法規則リストメモリ２４に格納された文法規則リ
ストとを参照して、詳細後述する処理方向決定木学習処
理を実行して学習することにより、頻度確率付き処理方
向決定木を生成して処理方向決定木ファイルメモリ２７
に格納する決定木学習装置１０と、（ｂ）スタックメモ
リ１２が構文情報付与装置１１に接続され、品詞決定木
ファイルメモリ２５に格納された頻度確率付き品詞決定
木と、文法規則決定木ファイルメモリ２６に格納された
頻度確率付き文法規則決定木と、処理方向決定木ファイ
ルメモリ２７に格納された頻度確率付き処理方向決定木
とを用いて、属性リストメモリ２２に格納された属性リ
ストと、品詞リストメモリ２３に格納された品詞リスト
と、文法規則リストメモリ２４に格納された文法規則リ
ストを参照して、テキストデータメモリ３０に格納され
入力されるテキストデータに対して、詳細後述する品詞
付与処理（図７）及び文法規則付与処理（図８）を含む
構文情報付与処理を実行することにより、品詞を付与し
かつ文法規則を付与して、構文解析済みテキストデータ
を生成して構文解析済みテキストデータ３１に格納する
構文情報付与装置１１とを備えたことを特徴とする。本
実施形態においては、テキストデータとは、英語の単語
列からなる英文である。

【００１３】まず、本実施形態の構文解析システムにお
いて用いる文法規則と知識について説明する。この中
で、まず、本実施形態で用いる詳細な文法規則について
述べる。学習用テキストデータベースであるコーパスに
現れる言語現象の中には、ある単位としてまとまること
により、言語的な特徴を持つ場合が少なくない。また、
この特徴が構文解析に非常に有効な情報となる場合も多
い。しかしながら、このような特徴は、スケルトン・パ
ージングにより構文情報を付与されたコーパスのみか
ら、学習することは困難である。本発明者は、詳細な文
法を用いることで、この問題を回避する。文法として
は、素性構造つき文脈自由文法を用いる。これは、文法
規則の子供のノードには現れない特徴を親ノードに付与
することで、より詳細な情報を付与でき、各素性の特徴
を利用しやすいと考えたためである。文法体系は、６６
種の素性が持つ値（平均１２種の値）の組み合わせで表
現され、品詞タグとしては、統語カテゴリに加えて意味
カテゴリの情報を付与することにより、２，８４３種の
タグセットを用いている。このタグセットに基づく規則
数は、１，１５５種であり、各規則には、第１の主辞、
第２の主辞の情報が付与されている。

【００１４】上述の文法規則に従う構造から、正しい構
造を得るために、様々な特徴を利用する。まず、文法に
与えられている各素性の持つ値の特徴を利用する。この
特徴に加えて、単語自身が持つ語彙の特徴、文の持つ特
徴を利用する。様々な文脈において、文法規則の素性が
取る値の統計的な性質を調べることで、どの文法規則が
確らしいかの指標を与えることができる。単語自身が持
つ語彙の特徴は、単語に対するタグを決めるのに非常に
有効な情報であるとともに、構文構造のある範囲での第
１の主辞となる語の情報としても利用される。本実施形
態において取り扱う語彙の情報は、辞書より得られる情
報ではなく、語を構成しているサフィックスやプレフィ
ックス、単語の文字数等により特徴づけられている。ま
た、文の持つ特徴は、１文に含まれる単語数や句読法、
あるいは、同じ単語が複数回現れているか等により特徴
づけられる。さらに、文脈的な情報を利用できるよう
に、直前の単語や文末、文頭、処理対象の文法規則のカ
バーする範囲の先頭の単語、末尾の単語等に関する特徴
も利用できるようにしている。文法家（文法規則を生成
する専門家をいう。）が様々な特徴を記述するために、
語法の特徴を記述するための枠組みを用いる。

【００１５】次いで、本実施形態で用いる統計的構文解
析法について述べる。本実施形態では、上述した特徴を
効率的に利用するために、統計的な性質を学習用コーパ
スを用いて計算し、確率付決定木として学習している。
本手法で用いる決定木では、枝刈りに、最小コスト−コ
ンプレキシティアルゴリズムを用い、スムージングに
は、フォワード−バックワードアルゴリズムを用いた。
この決定木は、２分木となっている。そのため、上述し
た特徴を決定木の分岐点の情報としては、直接利用でき
ない。そこで、各特徴の値に“０”，“１”の固有のビ
ット列を与え、特定のビットを利用する。また、その特
徴が有効な特徴であるかどうかの分岐も行っている。こ
こで、例えば、文頭の単語を処理する場合に、直前の単
語に関する特徴は利用できない。

【００１６】本手法の構文解析は、部分的な解析木を表
現する状態を、連続的に構築する処理として捉えられ
る。ある状態から次の状態に移るために、以下の処理の
いずれかが行われている。この各処理に対して上述した
決定木が構成されている。 （ａ）単語にタグを付与し、統語的な素性を決めた後、
意味的な素性を決める。 （ｂ）現在の処理対象が構成要素の終りかどうかを判断
する。 （ｃ）現在の処理対象の構成要素に文法規則を付与す
る。 これらの処理の順序関係には、何通りかの可能性がある
が、本実施形態では、まず、全ての単語に品詞のタグ付
を行い、左から右に、ボトム・アップで解析を進めてい
る。文法から生成される候補は、非常に膨大であり、最
適な候補を見いだすことが困難に思われるが、本手法で
は、決定木で文脈に依存した確率の推定を行っており、
詳細後述するスタック・デコーダ・アルゴリズムを利用
することで、処理の効率化をはかっている。

【００１７】次いで、図１の構文解析システムの構成及
び動作について説明する。決定木学習装置１０は、メモ
リ２１から読み出された単語列からなる品詞付与済みテ
キストデータに基づいて、各単語の綴りの特徴と、文章
内の使われ方による特徴と、単語の相互情報量を用いた
階層的な分類とを含み属性リストメモリ２２に格納され
た複数の属性を用いて、上記各属性の属性値に依存して
分割されるような二分木形式の木構造を有し品詞付与の
ための品詞決定木を生成し、上記生成された品詞決定木
の分割されないノードであるリーフノードに対して複数
の品詞に対する頻度確率を計算して付与することによ
り、頻度確率付き品詞決定木を生成して品詞決定木ファ
イルメモリ２５に格納する。次いで、決定木学習装置１
０は、メモリ２１から読み出された単語列からなる品詞
付与済みテキストデータに基づいて、処理対象の単語の
語数と、処理対象の主辞単語の品詞、処理対象の直前の
単語の品詞、単語の相互情報量を用いた階層的な分類と
を含み属性リストメモリ２２に格納された複数の属性を
用いて、上記各属性の属性値に依存して分割されるよう
な二分木形式の木構造を有し文法規則付与のための文法
規則決定木を生成し、上記生成された文法規則決定木の
分割されないノードであるリーフノードに対して複数の
文法規則に対する頻度確率を計算して付与することによ
り、頻度確率付き文法規則決定木を生成して文法規則決
定木ファイルメモリ２６に格納する。

【００１８】さらに、決定木学習装置１０は、メモリ２
１から読み出された単語列からなる品詞付与済みテキス
トデータに基づいて、処理対象の単語の語数と、処理対
象の主辞単語の品詞、処理対象の直前の単語の品詞、単
語の相互情報量を用いた階層的な分類とを含み属性リス
トメモリ２２に格納された複数の属性を用いて、上記各
属性の属性値に依存して分割されるような二分木形式の
木構造を有し文法規則付与処理における各パージング状
態で処理方向を決定するための処理方向決定木を生成
し、上記生成された処理方向決定木の分割されないノー
ドであるリーフノードに対して複数の処理方向に対する
頻度確率を計算して付与することにより、頻度確率付き
処理方向決定木を生成して処理方向決定木ファイルメモ
リ２７に格納する。ここで、決定木学習装置１０は、上
記二分木の形式で分割するときに、上記各属性による分
割前の属性の有効性の優先順位を表わすエントロピーＨ
₀と分割後のエントロピーＨとの差（Ｈ₀−Ｈ）が最大の
属性を分割候補の属性として選択し、所定の分割続行基
準を満足するときに、二分木の形式で分割して決定木を
更新する。

【００１９】次いで、構文情報付与装置１１は、決定木
学習装置１０によって生成された頻度確率付き品詞決定
木を用いて、テキストデータメモリ３０から入力される
処理対象の単語列からなるテキストデータに基づいて、
上記リーフノードに付与された頻度確率の中で上位複数
ｎ個の頻度確率を選択して上記テキストデータの各単語
に対して付与し、上記テキストデータの単語列において
最大の結合確率を有する品詞列を正解品詞列として決定
し、次いで、所定のスタック・デコーダ・アルゴリズム
を用いて、文法規則付与処理における各パージング状態
での単語列に対する結合確率が最大の結合確率を有する
パージング状態を選択した後、決定木学習装置１０によ
って生成された頻度確率付き処理方向決定木を用いて上
記処理対象の単語列における処理方向を決定し、決定さ
れた処理方向におけるパージング状態において、上記決
定木学習装置１０によって生成された頻度確率付き文法
規則決定木に従って文法規則を上記処理対象の単語列に
加えることにより構文解析情報を付与して構文解析済み
テキストデータを出力する。

【００２０】ここで、構文情報付与装置１１は、上記リ
ーフノードに付与された頻度確率の中で上位複数ｎ個の
頻度確率を選択して上記テキストデータの各単語に対し
て付与した後、所定のスタック・デコーダ・アルゴリズ
ムに用いて、処理途中のテキストデータの単語列に対す
る結合確率が所定の結合確率以上である品詞候補のみを
残して品詞候補を限定し、処理終了時の上記テキストデ
ータの単語列において最大の結合確率を有する品詞列を
正解品詞列として決定する。

【００２１】本実施形態においては、品詞決定木学習処
理により、品詞付与済みテキストデータから得られる知
識を用いて、二分木形式の木構造を有し品詞付与のため
の頻度確率付き品詞決定木を生成し、品詞付与を行な
う。頻度確率付き品詞決定木で用いられる属性は、言語
学的な特徴やコーパスから得られる統計的な特徴を用い
る。従来の品詞付与では、辞書を引くことで品詞候補を
制限し、その中から、前後に現れる語との関係などを考
慮して、もっとも適切な品詞を選択するという方法が一
般的である。しかしながら、辞書の作成や保守にかかる
コストの問題となる。また、辞書項目に無い語（未知
語）や辞書の品詞候補にない品詞として使われた語に対
しては、特別な処理が必要とされる。本実施形態に係る
頻度確率付き品詞決定木を用いた方法では、単語の品詞
を決定するために、辞書を用いないため、辞書の作成や
保守にかかるコストは問題にならない。頻度確率付き品
詞決定木を、品詞付与済みテキストを用いた学習により
構築する。そのために、品詞付与済みテキストデータが
あれば、品詞体系に柔軟に対応できる。また、上記頻度
確率を用いて、品詞列の優先順位を自動的に決定するこ
とができる。品詞決定木は、対象を複数の属性とその属
性値から、適切なクラスに分類する木構造のモデルであ
る。品詞付与においては、対象が各単語に、クラスが品
詞に相当する。属性としては、各単語の綴の特徴や文内
の使われ方による特徴や単語の相互情報量を用いた階層
的分類などを用いる。

【００２２】また、構文情報付与装置１１における文法
付与処理においては、文法規則決定木と処理方向決定木
を用いて、処理対象の単語列に対して、文法規則を付与
してゆく。ここで、文法規則決定木と処理方向決定木の
属性としては、処理対象の単語の語数と、処理対象の主
辞単語の品詞、処理対象の直前の単語の品詞、単語の相
互情報量を用いた階層的な分類を用いる。文法規則決定
木と処理方向決定木を用いた方法では、文法規則の付加
を決定するために、辞書を用いないため、辞書の作成や
保守にかかるコストは問題にならない。頻度確率付き文
法規則決定木及び処理方向決定木を、構文解析済みテキ
ストを用いた学習により構築する。そのために、構文解
析済みテキストデータがあれば、文規則の体系に柔軟に
対応できる。以下、本実施形態の構文解析システムにつ
いて詳述する。

【００２３】図１において、決定木学習装置１０は、品
詞付与済みテキストメモリ２１に格納された品詞付与済
みテキストデータに基づいて、属性リストメモリ２２に
格納された属性リストと、品詞リストメモリ２３に格納
された品詞リストとを参照して、詳細後述する品詞決定
木学習処理を実行して学習することにより、頻度確率付
き品詞決定木を生成して品詞決定木ファイルメモリ２５
に格納し、次いで、品詞付与済みテキストメモリ２１に
格納された品詞付与済みテキストデータに基づいて、属
性リストメモリ２２に格納された属性リストと、文法規
則リストメモリ２４に格納された文法規則リストとを参
照して、詳細後述する文法規則決定木学習処理を実行し
て学習することにより、頻度確率付き文法規則決定木を
生成して文法規則決定木ファイルメモリ２６に格納し、
さらに、品詞付与済みテキストメモリ２１に格納された
品詞付与済みテキストデータに基づいて、属性リストメ
モリ２２に格納された属性リストと、文法規則リストメ
モリ２４に格納された文法規則リストとを参照して、詳
細後述する処理方向決定木学習処理を実行して学習する
ことにより、頻度確率付き処理方向決定木を生成して処
理方向決定木ファイルメモリ２７に格納する。次いで、
構文情報付与装置１１には、スタックメモリ１２が接続
され、構文情報付与装置１１は、品詞決定木ファイルメ
モリ２５に格納された頻度確率付き品詞決定木と、文法
規則決定木ファイルメモリ２６に格納された頻度確率付
き文法規則決定木と、処理方向決定木ファイルメモリ２
７に格納された頻度確率付き処理方向決定木とを用い
て、属性リストメモリ２２に格納された属性リストと、
品詞リストメモリ２３に格納された品詞リストと、文法
規則リストメモリ２４に格納された文法規則リストを参
照して、テキストデータメモリ３０に格納され入力され
るテキストデータに対して、詳細後述する品詞付与処理
（図７）及び文法規則付与処理（図８）を含む構文情報
付与処理を実行することにより、品詞を付与しかつ文法
規則を付与して、構文解析済みテキストデータを生成し
て構文解析済みテキストデータ３１に格納する。ここ
で、生成された構文解析済みテキストデータは、例えば
ＣＲＴディスプレイやプリンタなどの出力機器に出力し
てもよい。

【００２４】ここで、決定木学習装置１０と構文情報付
与装置１１はそれぞれ、例えば、各処理を実行するＣＰ
Ｕと、各処理のプログラム及びそれを実行するために必
要なデータを格納するＲＯＭ（読出専用メモリ）と、Ｃ
ＰＵのワーキングメモリとして用いられるＲＡＭ（ラン
ダムアクセスメモリ）とを備えたデジタル計算機で構成
される。また、メモリ１２，２１乃至２７，３０，３１
は、例えばハードディスクメモリで構成される。さら
に、構文情報付与装置１１には、スタック・デコーダ・
アルゴリズムを用いて品詞付与処理及び文法規則付与処
理を実行するためのスタック用スタックメモリ１２が接
続される。

【００２５】品詞リストメモリ２３に格納される品詞リ
ストの一例を表１に示す。また、属性リストメモリ２２
に格納される属性リストの一例を表２及び表３に示す。
さらに、文法規則リストメモリ２４に格納される文法規
則の一例を表４に示す。

【００２６】

【表１】 品詞リスト ─────────────────────────────────── 品詞タグ 意義 ─────────────────────────────────── ＮＮ１ＩＮＴＥＲ−ＡＣＴ 単数普通名詞、相互行為 ＮＰ１ＣＩＴＹＮＭ 固有名詞、都市名 ＩＩＩＮ 前置詞 ＩＮＪＪＶＶＧＩＮＴＥＲ−ＡＣＴ 形容詞的用法の現在分詞、相互行為 ＶＶＧＣＯＮＳＵＭＥ 現在分詞、消費 ＶＶＧＲＥＣＥＩＶＥ 現在分詞、受理 …………………… ………………………… ───────────────────────────────────

【００２７】

【表２】 品詞付与用属性リスト ─────────────────────────────────── 属性 属性値 ─────────────────────────────────── 単語の相互情報量を用いた 分類コード 階層的分類コード 対象単語が“〜ｉｎｇ”の単語 Ｙｅｓ，Ｎｏ 対象単語が“〜ｅｄ”の単語 Ｙｅｓ，Ｎｏ 対象単語の長さ 単語長さの数値 （例えば、“ｗｏｒｄ”なら４） 直前の単語の品詞属性の値 品詞属性の値 現在の単語の品詞属性の値 品詞属性の値 文末が“？” Ｙｅｓ，Ｎｏ ………………………… ………………………… ───────────────────────────────────

【００２８】

【表３】 文法規則付与用属性リスト ─────────────────────────────────── 属性 属性値 ─────────────────────────────────── 処理対象の主辞単語の相互情報量 分類コード に基づく階層的単語分類コード （所定ビット） 処理対象が一語のみ Ｙｅｓ，Ｎｏ 処理対象の主辞単語の品詞が名詞 Ｙｅｓ，Ｎｏ 処理対象の直前の単語の品詞が名詞 Ｙｅｓ，Ｎｏ ………………………… ……………………… ───────────────────────────────────

【００２９】

【表４】文法規則リスト ────────────────────── ｎｂａｒｑ４：Ｎ’→Ｎ’Ｉ 名詞句 ｎｂａｒ１：Ｎ’→Ｎ１ 名詞句 ｎ１ａ：Ｎ１→Ｎ＊ 名詞要素 ｉ１ｅ：Ｉ→Ｐ 前置詞句 ｐ１：Ｐ→ＩＩ＊Ｎ’ 前置詞要素 …………………………… …… ──────────────────────

【００３０】表４の文法規則リストにおいて、例えば、
第１行目は、名詞句が名詞句と前置詞句から構成される
ことを意味し、第３行目は、名詞要素が、名詞の品詞を
持つ語から構成されることを意味し、第５行目は、前置
詞要素は、前置詞と名詞要素から構成されることを意味
する。なお、処理方向は、リストとして示していない
が、本実施形態において、「右」、「左」、「上」のい
ずれかである。

【００３１】ここで、品詞属性とは、粗く品詞を３２種
類に分類した属性であり、品詞属性の値とは、例えば、
ｖ（動詞），ｎ（名詞），ｄｅｔｅｒｍｉｎ（冠詞），
ｐｕｎｃｔ（記号）である。また、単語の相互情報量を
用いた階層的分類コードとは、例えば、特願平８−０２
７８０９号の特許出願や従来技術文献４「Akira Ushiod
a,“Hierarchical Clustering of Words",Proceedings
of COLING'96,The 16th International Conference on
Computational Linguistics,Vol.2,pp.1159-1162,1996
年8月」において開示された単語分類方法を用いて分類
された階層的分類コードである。この単語分類方法で
は、テキストデータ内の単語について出現頻度の比較的
低い単語を、同一の単語に隣接する割合の多い単語を同
一のクラスに割り当てるという基準で分類した後、単語
分類結果を中間層、上側層、及び下側層の３つの階層に
分類し、テキストデータ内のすべての単語を対象とする
グローバルな（全体的な）コスト関数である所定の平均
相互情報量を用いて、中間層、上側層、及び下側層の順
序で階層別に単語の分類を実行することを特徴としてい
る。相互情報量を用いたクラスタリングの方法において
は、単語数Ｔのテキスト、語数Ｖの語彙、それに語彙の
分割関数πとが存在すると仮定し、ここで、語彙の分割
関数πは語彙Ｖから語彙の中の単語クラスセットＣへの
分割写像（マッピング）を表わす写像関数である。複数
の単語からなるテキストデータを生成するバイグラムの
クラスモデルの尤度Ｌ（π）は次式によって得られる。

【００３２】

【数１】Ｌ(π)＝−Ｈｍ＋Ｉ

【００３３】ここで、Ｈｍはモノグラムの単語分布のエ
ントロピーであり、Ｉはテキストデータ内の隣接する２
つのクラスＣ₁，Ｃ₂に関する平均的な相互情報量（Aver
ageMutual Information；以下、平均相互情報量とし、
ＡＭＩと表記する。）であり、次式で計算することがで
きる。

【００３４】

【数２】

【００３５】ここで、Ｐｒ（Ｃ₁）は第１のクラスＣ₁の
単語の出現確率であり、Ｐｒ（Ｃ₂）は第２のクラスＣ₂
の単語の出現確率であり、Ｐｒ（Ｃ₁｜Ｃ₂）は、第２の
クラスＣ₂の単語は出現した後に、第１のクラスＣ₁の単
語が出現する条件付き確率であり、Ｐｒ（Ｃ₁，Ｃ₂）は
第１のクラスＣ₁の単語と第２のクラスＣ₂の単語が隣接
して出現する確率である。従って、上記数２で表される
ＡＭＩは、互いに異なる第１のクラスＣ₁の単語と第２
のクラスＣ₂の単語とが隣接して出現する確率を、上記
第１のクラスＣ₁の単語の出現確率と第２のクラスＣ₂の
単語の出現確率との積で割った相対的な頻度の割合を表
わす。エントロピーＨは写像関数πに依存しない値であ
ることから、ＡＭＩを最大にする写像関数は同時にテキ
ストの尤度Ｌ（π）も最大にする。従って、ＡＭＩを単
語のクラス構成における目的関数として使用することが
できる。

【００３６】上記単語分類方法は、意味又は統語的特徴
が似通った単語が近接した位置に配置された点で、バラ
ンスが取れた二分木の形式を有するツリー構造を生成す
ることができる。処理の最後に、根のノード（ルートノ
ード（ｒｏｏｔ ｎｏｄｅ））から葉のノード（リーフ
ノード（ｌｅａｆ ｎｏｄｅ）に至るパスの追跡し、左
側方向の分岐又は右側方向の分岐をそれぞれ表わす０又
は１の１ビットを各分岐に割り当てることによって、語
彙の中の各単語に対して、ビットストリング（単語ビッ
ト）を割り当てることができる。

【００３７】次いで、品詞決定木、文法規則決定木及び
処理方向決定木を構築する決定木学習処理のアルゴリズ
ム、及び構文情報付与処理のアルゴリズムについて述べ
る。

【００３８】各決定木学習処理では、各属性の有効性を
他の属性と独立に計算し、クラスの決定のための効率的
な属性による分類順序を、二分木の形式で分割された構
造を有する木構造として構築する。属性の有効性は、そ
の属性による分割分類後のエントロピーＨにより評価す
る。ここでのエントロピーは、属性の有効性の優先順位
を表わす。すなわち、ある属性ＢでノードＮ₁とノード
Ｎ₂とに分割するときに、分割前のエントロピーＨ₀と、
分割後のエントロピーＨと、ノードＮ₁に対するエント
ロピーＨ₁と、ノードＮ₂に対するエントロピーＨ₂とは
次式で表される。

【００３９】

【数３】

【数４】Ｈ＝ｐ₁Ｈ₁＋（１−ｐ₁）Ｈ₂ ここで、

【数５】

【数６】

【００４０】ここで、ｐ（ｔａｇａｌｌ）は分割前のす
べての品詞タグ（品詞決定木の場合；文法規則決定木の
ときは文法規則タグであり、処理方向決定木のときは処
理方向タグ、すなわち、「上」、「左」及び「右」であ
る。）についてのイベントの数の頻度確率又は出現確率
であり、ｔａｇａｌｌについてのΣは、分割前のすべて
の品詞タグについての和を示す。また、ｐ₁は、ノード
Ｎ₁に分割したときに含まれる品詞タグのイベントの数
の頻度確率の総和である。さらに、ｐ（ｔａｇＮ₁）は
ノードＮ₁のすべての品詞タグについてのイベントの数
の頻度確率であり、ｔａｇＮ₁についてのΣは、ノード
Ｎ₁のすべての品詞タグについての和を示す。ｐ（ｔａ
ｇＮ₂）はノードＮ₂のすべての品詞タグについてのイベ
ントの数の頻度確率であり、ｔａｇＮ₂についてのΣ
は、ノードＮ₂のすべての品詞タグについての和を示
す。

【００４１】有効性の計算のために、学習用のテキスト
データから各語について「属性とその属性値、品詞」の
組からなるイベント情報（ｅｖｅｎｔ：以下、イベント
という。）を予めとりだしておく。具体的には、全ての
イベントの集合に対して、分類後のエントロピーＨが最
小となる属性を求め、最初のノードに割り当てる。この
属性の属性値により、イベントの集合を分割し、対応す
る子ノードを作る。各々の子ノードにおいて、同様の処
理を繰り返し行なうことにより、木構造を構築する。分
割の停止条件は、各ノードに含まれるイベント数が一定
数以下、あるいは分割による有効性が一定基準以下（こ
こで、分割後のエントロピーＨと分割前のエントロピー
Ｈ₀との差がある所定量を越えない場合。）とする。こ
こで、分割されないノードをリーフと呼ぶ。学習された
決定木のリーフでは、与えられたイベントの集合から各
品詞の頻度確率を計算する。

【００４２】ここで、本実施形態の構文情報付与システ
ムでは、従来技術文献５「L.E.Baum,“An inequality a
nd associated maximization technique in statistica
l estimation for probabilistic functions of a Mark
ov process",Inequalities,Vol.3,pp.1-8,1972年」に開
示されたＦｏｒｗａｒｄ−Ｂａｃｋｗａｒｄアルゴリズ
ムを用いて、スムージング用の学習データに基づいて、
スムージング用の学習データから得られる確率と決定木
から得られる確率との差が最小となるようにスムージン
グを行ない、品詞及び構文情報を付与すべき最後の頻度
確率分布を補正する。また、本実施形態のシステムで
は、上記決定木学習処理のアルゴリズムに従って、２段
階の決定木を作成している。１段目は、粗く分類した品
詞（以下、ＧＰＯＳ（Ｇｌｏｂａｌ Ｐａｒｔ Ｏｆ
Ｓｐｅｅｃｈ）という。）（ここで、実際の品詞の属性
の１つに対応しており、例えば、動詞、名詞、冠詞など
に分類される。）のための決定木であり、２段目とし
て、ＧＰＯＳの品詞毎に実際の品詞（表１に示した品詞
タグレベル）を決定するための決定木を作成する。本実
施形態では、より詳細な品詞レベルの名称を品詞タグと
呼んでいる。すなわち、２段階に分割して決定木を生成
することにより、１回の処理で必要な記憶装置の記憶容
量を大幅に減少させている。

【００４３】品詞付与処理においては、入力文のテキス
トデータを左から右に処理し、結合確率を最大にする品
詞列を出力する。入力文が、ｗ₁，ｗ₂，…，ｗ_Nのよう
な複数Ｎ個の単語からなり、品詞列｛ｔ₁，ｔ₂，…，ｔ
_N｝（ここで、ｔ_iはｉ番目の単語の品詞である。）が得
られたとすると、結合確率Ｐは次式で表される。なお、
本実施形態では、品詞の出現をマルコフ情報源として取
り扱っておらず、それまでに出現した単語や品詞に依存
した情報源として取り扱っている。従って、十分に長い
文において、文の最初の語とその品詞に依存して最後の
単語の品詞を導くことが、原理的には可能である。

【００４４】

【数７】 Ｐ≡ｐ（ｔ₁，ｔ₂，…，ｔ_N│ｗ₁，ｗ₂，…，ｗ_N）

【数８】

【００４５】上記数７の右辺は、入力文ｗ₁，ｗ₂，…，
ｗ_Nが入力されたときに、品詞列ｔ₁，ｔ₂，…，ｔ_Nが与
えられる結合確率を意味し、上記数８の右辺は、入力文
ｗ₁，ｗ₂，ｗ₃，…，ｗ_n、および、ｉ−１番目の単語ま
での品詞列ｔ₁，ｔ₂，…，ｔ_i-1が与えられたときのｉ
番目の品詞の確率をｉが１からｎまで積算することによ
り得られる確率を意味する。ここで、Πの記号はｉを２
からＮまで変化したときの積和を意味する。そして、文
脈に依存する属性をもちいて、決定木のリーフｌｅａｆ
（Ｌ）を導き、Ｌに関連した頻度確率分布を、ｐ_Lによ
り表現し、決定木の条件付き分布を用いて以下のように
近似する。

【００４６】

【数９】Ｌ_i≡文脈ｗ₁，ｗ₂，…，ｗ_N，ｔ₁，ｔ₂，…，
ｔ_i-1において導かれたリーフ

【数１０】ｐ（ｔ_i│ｗ₁，ｗ₂，…，ｗ_N，ｔ₁，ｔ₂，
…，ｔ_i-1）≒ｐ_Li（ｔ_i）

【００４７】上記数９における文脈ｗ₁，ｗ₂，…，
ｗ_N，ｔ₁，ｔ₂，…，ｔ_i-1は、ｉ番目の単語ｗ_iのもつ
文脈を意味する。また、数１０の左辺は、文脈ｗ₁，
ｗ₂，…，ｗ_N,t₁，ｔ₂，…，ｔ_i-1の次に単語ｔ_iが来る
頻度確率又は出現確率を表し、それが、数１０の右辺で
ある、文脈Ｌ_iのもとで品詞ｔ_iをとる確率に近似できる
ことを意味する。従って、最大化すべき結合確率Ｐは以
下のようになる。

【００４８】

【数１１】

【００４９】上記数１１から明らかなように、結合確率
Ｐは、入力文の各単語での文脈に依存して得られる品詞
ｔ_iの確率の積で表される。さらに、入力文の各単語に
対する品詞付与処理においては、次の２段階の処理を行
なっている。 （ａ）ＧＰＯＳの各品詞の頻度確率を計算する。 （ｂ）ＧＰＯＳの各品詞に対応する決定木を用いて、品
詞の頻度確率を計算する。

【００５０】各語の頻度確率の計算では、それまでに得
られている可能性のある品詞列を全て考慮する必要があ
る。細かな品詞体系を扱う場合、探索範囲が膨大になる
ため、本システムでは、従来技術文献６「F.Jelinek,
“A fast sequential decodingalgorithm using a stac
k",IBM Journal of Research and Development,No.13,p
p.675-685,1969年」及び従来技術文献７「D.Paul,“Alg
orithms for an optimal a* search and linearizing t
he search in the stack decoder",Proceedingsof the
June 1990 DARPA Speech and Natural Language Work s
hop,1990年」において開示されたスタック・デコーダ・
アルゴリズムを用いて、頻度確率又は出現確率が最大と
なる品詞列を探索している。このアルゴリズムは、一種
のグラフサーチアルゴリズムであり、しきい値により一
時的に探索範囲を限定し、評価値の最も良いものを探す
ことができる。すなわち、各語に付与される可能性のあ
る複数の品詞から、最も頻度確率の高い品詞列を選択す
ることは、各品詞をノードとし隣接する単語に付与され
ているノードを連結したグラフの複数の経路から最適な
経路を探索することであり、スタック・デコーダ・アル
ゴリズムは、二分木形式で分割された木構造の経路にお
いて、複数のノードをスタック構造としてまとめて取り
扱い、スタック構造内で、探索範囲を変更することによ
り、最適な経路を、効率的に見い出すことができる。

【００５１】図２は、図１の決定木学習装置によって実
行される品詞決定木学習処理を示すフローチャートであ
る。図２において、まず、ステップＳ１で構文解析済み
テキストデータメモリ２１に格納された構文解析済み
（品詞付与済み）テキストデータを読み出して、決定木
学習装置１０内のＲＡＭに書き込む。次いで、ステップ
Ｓ２で、各属性と品詞タグとの組み合わせの頻度確率
（上記ｐ（ｔａｇａｌｌ），ｐ（ｔａｇＮ₁），ｐ（ｔ
ａｇＮ₂）に対応する。）を計算して決定木学習装置１
０内のＲＡＭに書き込む。さらに、ステップＳ３で決定
木作成処理を実行することにより頻度確率付き品詞決定
木を生成し、ステップＳ４で作成された確率付き品詞決
定木をメモリ２４に出力して格納する。

【００５２】図３は、図１の決定木学習装置によって実
行される文法規則決定木学習処理（ステップＳ１１−Ｓ
１４）を示すフローチャートであり、図２の品詞決定木
学習処理と同様に実行される。図４は、図１の決定木学
習装置によって実行される処理方向決定木学習処理（ス
テップＳ２１−Ｓ２４）を示すフローチャートであり、
図２の品詞決定木学習処理と同様に実行される。ここ
で、処理方向とは、文法規則付与処理における各パージ
ング状態で処理すべき方向であり、文法規則を付与する
範囲となる処理対象をどのように変更するかを限定する
ものである。ここで、パージング状態とは、図１３に示
すように、構文情報付与装置１１において部分的に解析
された状態のことをいい、現在の処理対象となるノード
又は単語の情報（具体的には、単語とその品詞情報、処
理対象はどれか）を有する。また、ゴール状態は、最終
的な構文解析結果を入力する状態であり、一文を文とし
てまとめる文法規則によりひとまとまりになったパージ
ング状態である。

【００５３】図５は、図２、図３及び図４のサブルーチ
ンである決定木作成処理（ステップＳ３，Ｓ１３，Ｓ２
３）を示すフローチャートである。まず、ステップＳ３
１ですべての各属性による分割後のエントロピーＨと、
分割前のエントロピーＨ₀とをそれぞれ数４と数３を用
いて計算する。次いで、ステップＳ３２でエントロピー
の差（Ｈ₀−Ｈ）が最大の属性を分割候補の属性として
選択し、ステップＳ３３で選択された属性について分割
続行判定基準を満足するか否かが判断される。ここで、
分割続行判定基準とは、（Ｉ）選択された属性に基づい
て分割したときのエントロピーの差（Ｈ₀−Ｈ）が所定
のエントロピーしきい値Ｈｔｈ以上であり、かつ（II）
選択された属性に基づく分割後のイベント数が所定のイ
ベント数しきい値Ｄｔｈ以上であること。ステップＳ３
３で分割続行判定基準を満足するときは、ステップＳ３
４で、選択された属性の属性値により分割した２つのノ
ードを作成して、すなわち二分木の形式で分割して、決
定木を更新する。そして、ステップＳ３５では、上記作
成した各ノードを処理対象として、ステップＳ３１に戻
り、ステップＳ３１からの処理を繰り返す。一方、ステ
ップＳ３３で分割続行判定基準を満足しないときは、元
のメインルーチンに戻る。

【００５４】これらの決定木学習処理において作成され
た品詞決定木、文法規則決定木及び処理方向決定木の一
例を示す。ここで、入力されるテキストデータとして
は、「ｍｅｅｔｉｎｇ ｉｎ Ｌｏｎｄｏｎ」を用いる
と、構文情報付与装置１１から出力される構文解析済み
テキストデータとして、「［ｎｂａｒｑ４ ［ｎｂａｒ
１ ［ｎ１ａ ｍｅｅｔｉｎｇ＿ＮＮ１ＩＮＴＥＲ−Ａ
ＣＴ ｎ１ａ］ ｎｂａｒ１］ ［ｉ１ｅ ［ｐ１ ｉ
ｎ＿ＩＩＩＮ ［ｎｂａｒ１ ［ｎ１ａ Ｌｏｎｄｏｎ
＿ＮＰ１ＣＩＴＹＮＭ ｎ１ａ］ ｎｂａｒ１］ ｐ
１］ ｉ１ｅ］ ｎｂａｒｑ４］」が出力される。

【００５５】上記例において作成された頻度確率付き品
詞決定木の一例を図１０に示す。図１０に示すように、
当該頻度確率付き品詞決定木は、各属性１０１乃至１０
５で二分木の形式で分割された木構造を有し、最後のリ
ーフにおいて各品詞タグに対する頻度確率が付与されて
いる。この例では、入力文が“ｍｅｅｔｉｎｇ ｉｎＬ
ｏｎｄｏｎ”であるときに、単語“ｍｅｅｔｉｎｇ”に
対して品詞タグＮＮ１ＩＮＴＥＲ−ＡＣＴ（単数普通名
詞，相互行為）が付与される一方、単語“Ｌｏｎｄｏ
ｎ”に対して品詞タグＮＰ１ＣＩＴＹＮＭ（固有名詞，
都市名）が付与されている。

【００５６】上記例において作成された頻度確率付き文
法規則決定木の一例を図１１に示す。図１１に示すよう
に、当該頻度確率付き文法規則決定木は、各属性３０１
乃至３０５で二分木の形式で分割された木構造を有し、
最後のリーフにおいて各文法規則タグに対する頻度確率
が付与されている。この例では、入力文が“ｍｅｅｔｉ
ｎｇ ｉｎ Ｌｏｎｄｏｎ”であるときに、リーフノー
ド４０１において、文法規則タグｎｂａｒｑ４（名詞句
と前置詞要素から構成される名詞句を意味する。）が付
与される一方、リーフノード４０３において、文法規則
タグｎｂａｒ１（名詞要素一つから構成される名詞句を
意味する。）が付与されている。

【００５７】上記例において作成された頻度確率付き処
理方向決定木の一例を図１２に示す。図１２に示すよう
に、当該頻度確率付き処理方向決定木は、各属性５０１
乃至５０５で二分木の形式で分割された木構造を有し、
最後のリーフにおいて各処理方向タグに対する頻度確率
が付与されている。この例では、入力文が“ｍｅｅｔｉ
ｎｇ ｉｎ Ｌｏｎｄｏｎ”であるときに、リーフノー
ド６０１において、処理方向タグ「上」が付与されて現
在の処理対象“ｍｅｅｔｉｎｇ”のままで、この処理対
象への文法付与決定木の処理が続けられる。一方、リー
フノード６０３において、処理方向タグ「左」が付与さ
れて、現在の処理対象“［［ｉｎ［［Ｌｏｎｄｏ
ｎ］］］］”にその左にある”［ｍｅｅｔｉｎｇ］”を
加え、新たな処理対象“［ｍｅｅｔｉｎｇ］［［ｉｎ
［［Ｌｏｎｄｏｎ］］］］”とする処理が行われ、文法
付与決定木の処理が続けられる。

【００５８】図６は、図１の構文情報付与装置によって
実行される構文情報付与処理を示すフローチャートであ
る。図６において、まず、ステップＳ４１で、確率付き
品詞決定木ファイルメモリ２５に格納された頻度確率付
き品詞決定木ファイルを読み出して、構文情報付与装置
１１内のＲＡＭに書き込み、確率付き文法規則決定木フ
ァイルメモリ２６に格納された頻度確率付き文法規則決
定木ファイルを読み出して、構文情報付与装置１１内の
ＲＡＭに書き込み、確率付き処理方向決定木ファイルメ
モリ２７に格納された頻度確率付き処理方向決定木ファ
イルを読み出して、構文情報付与装置１１内のＲＡＭに
書き込む。次いで、ステップＳ４２でテキストデータメ
モリ３０に格納された解析対象のテキストデータを読み
出して構文情報付与装置１１内のＲＡＭに書き込む。さ
らに、ステップＳ４３で品詞付与処理を実行して、品詞
付与済みテキストデータを生成し、次いで、ステップＳ
４４で、ステップＳ４３で生成された品詞付与済みテキ
ストデータに対して文法規則タグを付与するための文法
規則付与処理を実行することにより、構文解析済みテキ
ストデータを生成する。そして、ステップＳ４５で生成
された構文解析済みテキストデータを、構文解析済みテ
キストデータメモリ３１に出力して書き込む。

【００５９】図７は、図６のサブルーチンである品詞付
与処理（ステップＳ４３）を示すフローチャートであ
る。まず、ステップＳ５１で解析対象のテキストデータ
の文頭の単語を対象単語とする。次いで、ステップＳ５
２で決定木の最上位置にあるルートノードを処理対象の
カレントノードとする。そして、ステップＳ５３でカレ
ントノードがリーフノードであるか否かが判断される。
ＮＯであるときは、ステップＳ５８でカレントノードの
属性値に基づいて対応する子ノードをカレントノードと
し、ステップＳ５３に戻る。一方、ステップＳ５３でＹ
ＥＳであるときは、ステップＳ５４でリーフノードに割
り当てられた頻度確率リストの中で上位ｎ個の頻度確率
（ここで、ｎは複数であり、例えば、好ましくは、３乃
至６であり、より好ましくは４である。）を選択して対
象単語に与える。そして、ステップＳ５５で上述のスタ
ック・デコーダ・アルゴリズムに従って、所定の結合確
率以上の結合確率Ｐを残して品詞タグ候補を限定する。
さらに、ステップＳ５６で次の処理単語があるか否かが
判断され、あるときはステップＳ５７で次の単語を対象
単語とし、ステップＳ５２に戻って上記の処理を繰り返
す。一方、ステップＳ５６で次の単語がないときは、ス
テップＳ５９で最大の結合確率Ｐを有する品詞タグ列を
正解品詞列に決定し、元のメインルーチンに戻る。

【００６０】図８及び図９は、図６のサブルーチンであ
る文法規則付与処理（ステップＳ４４）を示すフローチ
ャートである。まず、図８のステップＳ６１で、文頭の
単語を対象としたパージング状態を生成する。次いで、
ステップＳ６２で、処理方向決定の回数と、文法規則決
定の回数とによって決定されるスタックメモリ１２内の
スタックに直前に生成したパージング状態を追加する。
上記決定されるスタックとは、各パージング状態を、記
録しておくデータ構造を意味する。そして、ステップＳ
６３で、上述のスタック・デコーダ・アルゴリズムに従
って最大の結合確率を有するパージング状態を選択し、
ステップＳ６４で処理方向決定木を用いて処理方向を決
定する。ここで、処理方向が「右」であるときは、ステ
ップＳ６５を介してステップＳ６７で次の単語を処理対
象にしたパージング状態を生成した後、ステップＳ６２
に戻る。また、ステップＳ６４で処理方向が「上」であ
るときは、ステップＳ６５及びＳ６６を介して、ステッ
プＳ６８で処理対象のノードに文法規則決定木に従って
文法規則タグを加えたパージング状態を生成した後、ス
テップＳ７０に進む。ここで、処理方向が「上」とは、
現在の処理対象に対してステップＳ６８で、文法規則決
定木に従った処理を行うことを意味する。さらに、ステ
ップＳ６４で処理方向が「左」であるときは、ステップ
Ｓ６５及びＳ６６を介して、ステップＳ６９で処理対象
のノードの範囲を左にのばして文法規則決定木に従って
文法規則タグを加えたパージング状態を生成した後、ス
テップＳ７０に進む。

【００６１】ステップＳ７０において、処理していない
単語がなくかつ文法規則が１つの文として成立している
か否かが判断され、ＮＯのときステップＳ６２に戻る一
方、ＹＥＳのとき図９のステップＳ７１に進む。ステッ
プＳ７１では、ゴール状態に現在のパージング状態を追
加し、ステップＳ７２で予め決められた一定数（例え
ば、上位Ｎ個の結果を得たい場合は、Ｎである。）のパ
ージング状態がゴール状態となったか否かが判断され、
ＮＯのときステップＳ６２に戻る一方、ＹＥＳのとき当
該文法規則付与処理を終了して元のメインルーチンに戻
る。

【００６２】以上の実施形態においては、予め決められ
た１つの文法規則体系で構文解析済みの学習用テキスト
データを用いているが、本発明はこれに限らず、他の文
法規則体系Ｇ１で解析された一定量のテキストデータが
ある場合、他の文法規則体系Ｇ１の情報を利用するよう
に構成してもよく、このとき、構文解析の精度を向上で
きる。ここで、利用する文法規則体系をＧ０とする。文
法規則体系Ｇ１の情報を利用するために、文法規則体系
Ｇ１で解析済テキストの一部を、文法規則体系Ｇ０で解
析したテキストを作成する。文法規則体系Ｇ０及びＧ１
双方で解析済の同じテキストデータを用いて、利用する
属性に、文法規則体系Ｇ１の文法の特徴を反映させた決
定木を学習する。文法規則体系Ｇ１の文法の特徴が反映
された決定木を用いて、文法規則体系Ｇ１で解析された
テキストを入力することにより、入力の豊富な情報を利
用した解析が可能となり、構文解析の精度を向上するこ
とができる。

【００６３】

【実施例】本発明者は、以上のように構成された構文解
析システムを用いて以下の実験を行った。自動的な評価
を行う際に、正解とされるデータが複数存在し、問題が
生じることは、珍しいことではない。非常に詳細にタグ
の仕様が決められている場合においても、実際には、複
数の正解が存在することが多い。しかし、そのためにコ
ーパス上に複数の正解を付加しておくことも現実的では
ない。また、段落単位では、正解が絞り込めるが、一文
では、絞り込めない場合も多い。そこで、テスト用のデ
ータを予め設定しておき、そのデータに対してのみ複数
の正解を付加することでこの問題に対処できると考え、
評価用データを作成した。

【００６４】本実験では、まず、品詞タグを付与してか
ら構文解析を行っている。現在、品詞タグ付のみの精度
が、１正解に対して７４％である（なお、複数の正解に
よる評価をする場合、約１０％の精度向上が見込まれて
いる。）。そこで、品詞が正しく付与されている状態で
構文解析を行った実験結果を表５に、テキストのみから
処理した実験結果を表６に示す。

【００６５】

【表５】 ─────────────────────────────────── 単語数(長さ) 文数 上位第１位 上位２０位まで クロス 構成素／文 ─────────────────────────────────── １−１０ １０４４ ８１．８％ ９５．０％ ８９．１％ ７．６ １１−１５ ２４８ ３０．２％ ７２．６％ ４３．１％ ２３．９ １６−２３ ２０１ １７．４％ ４８．３％ ２８．４％ ３４．２ ───────────────────────────────────

【００６６】

【表６】 ─────────────────────────────────── 単語数(長さ) 完全一致 統語的完全一致 ───────────── ─────────────── 上位第１位 上位１０位まで 上位第１位 上位１０位まで ─────────────────────────────────── １−１０ ３４．５％ ４０．１％ ５０．４％ ６２．３％ １１−１５ １．２％ ３．６％ １１．３％ ２５．６％ ───────────────────────────────────

【００６７】表５の「クロス」は、第１位の解析結果と
正解解析候補との全くブラケットが交差しない文の割合
である。表６の「完全一致」は、文字通り、完全に一致
した場合の割合であり、「統語的完全一致」は、ブラケ
ットの位置、文法規則名、統語的なタグが完全に一致し
た場合の割合である。

【００６８】実験結果から明らかなように、単語数が比
較的少ない場合において、非常に高い精度が得られてい
るが、一文の単語数が増えると非常に精度が悪くなって
いる。この問題は、決定木モデルに起因するものではな
く、正解を探索する手法の問題と考えている。つまり、
一文の単語数が大きくなれば、正解の構造が、処理途中
で解析候補から漏てしまっていると考えている。そのた
めにスタックデコーダアルゴリズム、あるいは探索手法
を改善する必要があり、それは設計上の問題である。ま
た、タグ付与の精度向上が必要である。

【００６９】以上説明したように、本実施形態によれ
ば、品詞の接続関係、語と品詞の関係、さらに、離れた
語あるいは品詞との依存関係を統計的に処理するため、
自動的に一意に高精度で品詞を付与でき、しかも高精度
で文法規則を付与することができ、高精度の構文解析シ
ステムを提供することができる。また、辞書を用いず
に、単語に品詞ラベルを割り当てるため、従来技術の問
題となる未知語に対する特別な処理が不必要である。さ
らに、品詞を付与した構文解析済みテキストデータを用
いて学習を行なうため、多くの品詞体系に対して柔軟な
対応ができる。さらには、自動的に詳細な構文情報を付
与することができるため、付与された構文情報を翻訳シ
ステム、音声認識システム、又は情報検索システムに利
用することができる。また、詳細な情報を含む構文構造
付きおデータを自動的に生成することができるため、構
文情報を付与したデータを大量に蓄えることができる。

【００７０】

【発明の効果】以上詳述したように本発明に係る請求項
１記載の構文解析装置によれば、単語列からなる構文解
析済みテキストデータに基づいて、各単語の綴りの特徴
と、文章内の使われ方による特徴と、単語の相互情報量
を用いた階層的な分類とを含む複数の属性を用いて、上
記各属性の属性値に依存して分割されるような二分木形
式の木構造を有し品詞付与のための品詞決定木を生成
し、上記生成された品詞決定木の分割されないノードで
あるリーフノードに対して複数の品詞に対する頻度確率
を計算して付与することにより、頻度確率付き品詞決定
木を生成する品詞決定木学習手段と、単語列からなる構
文解析済みテキストデータに基づいて、処理対象の単語
の語数と、処理対象の主辞単語の品詞、処理対象の直前
の単語の品詞、単語の相互情報量を用いた階層的な分類
とを含む複数の属性を用いて、上記各属性の属性値に依
存して分割されるような二分木形式の木構造を有し文法
規則付与のための文法規則決定木を生成し、上記生成さ
れた文法規則決定木の分割されないノードであるリーフ
ノードに対して複数の文法規則に対する頻度確率を計算
して付与することにより、頻度確率付き文法規則決定木
を生成する文法規則決定木学習手段と、単語列からなる
構文解析済みテキストデータに基づいて、処理対象の単
語の語数と、処理対象の主辞単語の品詞、処理対象の直
前の単語の品詞、単語の相互情報量を用いた階層的な分
類とを含む複数の属性を用いて、上記各属性の属性値に
依存して分割されるような二分木形式の木構造を有し文
法規則付与処理における各パージング状態で処理方向を
決定するための処理方向決定木を生成し、上記生成され
た処理方向決定木の分割されないノードであるリーフノ
ードに対して複数の処理方向に対する頻度確率を計算し
て付与することにより、頻度確率付き処理方向決定木を
生成する処理方向決定木学習手段と、上記品詞決定木学
習手段によって生成された頻度確率付き品詞決定木を用
いて、入力される処理対象の単語列からなるテキストデ
ータに基づいて、上記リーフノードに付与された頻度確
率の中で上位複数ｎ個の頻度確率を選択して上記テキス
トデータの各単語に対して付与し、上記テキストデータ
の単語列において最大の結合確率を有する品詞列を正解
品詞列として決定し、次いで、所定のスタック・デコー
ダ・アルゴリズムを用いて、文法規則付与処理における
各パージング状態での単語列に対する結合確率が最大の
結合確率を有するパージング状態を選択した後、上記処
理方向決定木学習手段によって生成された頻度確率付き
処理方向決定木を用いて上記処理対象の単語列における
処理方向を決定し、決定された処理方向におけるパージ
ング状態において、上記文法規則決定木学習手段によっ
て生成された頻度確率付き文法規則決定木に従って文法
規則を上記処理対象の単語列に加えることにより構文解
析情報を付与して構文解析済みテキストデータを出力す
る構文情報付与手段とを備える。従って、品詞の接続関
係、語と品詞の関係、さらに、離れた語あるいは品詞と
の依存関係を統計的に処理するため、自動的に一意に高
精度で品詞を付与でき、しかも高精度で文法規則を付与
することができ、高精度の構文解析システムを提供する
ことができる。また、辞書を用いずに、単語に品詞ラベ
ルを割り当てるため、従来技術の問題となる未知語に対
する特別な処理が不必要である。さらに、品詞を付与し
た構文解析済みテキストデータを用いて学習を行なうた
め、多くの品詞体系に対して柔軟な対応ができる。さら
には、自動的に詳細な構文情報を付与することができる
ため、付与された構文情報を翻訳システム、音声認識シ
ステム、又は情報検索システムに利用することができ
る。また、詳細な情報を含む構文構造付きおデータを自
動的に生成することができるため、構文情報を付与した
データを大量に蓄えることができる。

【００７１】また、請求項２記載の構文解析装置におい
ては、請求項１記載の構文解析装置において、上記各決
定木学習手段は、上記二分木の形式で分割するときに、
上記各属性による分割前の属性の有効性の優先順位を表
わすエントロピーＨ₀と分割後のエントロピーＨとの差
（Ｈ₀−Ｈ）が最大の属性を分割候補の属性として選択
し、所定の分割続行基準を満足するときに、二分木の形
式で分割して決定木を更新する。従って、品詞の接続関
係、語と品詞の関係、さらに、離れた語あるいは品詞と
の依存関係を統計的に処理するため、自動的に一意に高
精度で品詞を付与でき、しかも高精度で文法規則を付与
することができ、高精度の構文解析システムを提供する
ことができる。また、辞書を用いずに、単語に品詞ラベ
ルを割り当てるため、従来技術の問題となる未知語に対
する特別な処理が不必要である。さらに、品詞を付与し
た構文解析済みテキストデータを用いて学習を行なうた
め、多くの品詞体系に対して柔軟な対応ができる。さら
には、自動的に詳細な構文情報を付与することができる
ため、付与された構文情報を翻訳システム、音声認識シ
ステム、又は情報検索システムに利用することができ
る。また、詳細な情報を含む構文構造付きおデータを自
動的に生成することができるため、構文情報を付与した
データを大量に蓄えることができる。

【００７２】さらに、請求項３記載の構文解析装置にお
いては、請求項２記載の構文解析装置において、上記分
割続行基準は、（Ｉ）選択された属性に基づいて分割し
たときのエントロピーの差（Ｈ₀−Ｈ）が所定のエント
ロピーしきい値Ｈｔｈ以上であり、かつ（II）選択され
た属性に基づく分割後の属性とその属性値及び品詞の組
のイベント数が所定のイベント数しきい値Ｄｔｈ以上で
ある。従って、品詞の接続関係、語と品詞の関係、さら
に、離れた語あるいは品詞との依存関係を統計的に処理
するため、自動的に一意に高精度で品詞を付与でき、し
かも高精度で文法規則を付与することができ、高精度の
構文解析システムを提供することができる。また、辞書
を用いずに、単語に品詞ラベルを割り当てるため、従来
技術の問題となる未知語に対する特別な処理が不必要で
ある。さらに、品詞を付与した構文解析済みテキストデ
ータを用いて学習を行なうため、多くの品詞体系に対し
て柔軟な対応ができる。さらには、自動的に詳細な構文
情報を付与することができるため、付与された構文情報
を翻訳システム、音声認識システム、又は情報検索シス
テムに利用することができる。また、詳細な情報を含む
構文構造付きおデータを自動的に生成することができる
ため、構文情報を付与したデータを大量に蓄えることが
できる。

【００７３】またさらに、請求項４記載の構文解析装置
においては、請求項１、２又は３記載の構文解析装置に
おいて、上記品詞付与手段は、上記リーフノードに付与
された頻度確率の中で上位複数ｎ個の頻度確率を選択し
て上記テキストデータの各単語に対して付与した後、所
定のスタック・デコーダ・アルゴリズムに用いて、処理
途中のテキストデータの単語列に対する結合確率が所定
の結合確率以上である品詞候補のみを残して品詞候補を
限定し、処理終了時の上記テキストデータの単語列にお
いて最大の結合確率を有する品詞列を正解品詞列として
決定する。従って、品詞の接続関係、語と品詞の関係、
さらに、離れた語あるいは品詞との依存関係を統計的に
処理するため、自動的に一意に高精度で品詞を付与で
き、しかも高精度で文法規則を付与することができ、高
精度の構文解析システムを提供することができる。ま
た、辞書を用いずに、単語に品詞ラベルを割り当てるた
め、従来技術の問題となる未知語に対する特別な処理が
不必要である。さらに、品詞を付与した構文解析済みテ
キストデータを用いて学習を行なうため、多くの品詞体
系に対して柔軟な対応ができる。さらには、自動的に詳
細な構文情報を付与することができるため、付与された
構文情報を翻訳システム、音声認識システム、又は情報
検索システムに利用することができる。また、詳細な情
報を含む構文構造付きおデータを自動的に生成すること
ができるため、構文情報を付与したデータを大量に蓄え
ることができる。

【図面の簡単な説明】

【図１】 本発明に係る一実施形態である、決定木学習
装置及び構文情報付与装置を備えた構文解析システムの
ブロック図である。

【図２】 図１の決定木学習装置によって実行される品
詞決定木学習処理を示すフローチャートである。

【図３】 図１の決定木学習装置によって実行される文
法規則決定木学習処理を示すフローチャートである。

【図４】 図１の決定木学習装置によって実行される処
理方向決定木学習処理を示すフローチャートである。

【図５】 図２、図３及び図４のサブルーチンである決
定木作成処理（ステップＳ３，Ｓ１３，Ｓ２３）を示す
フローチャートである。

【図６】 図１の構文情報付与装置によって実行される
構文情報付与処理を示すフローチャートである。

【図７】 図６のサブルーチンである品詞付与処理（ス
テップＳ４３）を示すフローチャートである。

【図８】 図６のサブルーチンである文法規則付与処理
（ステップＳ４４）の第１の部分を示すフローチャート
である。

【図９】 図６のサブルーチンである文法規則付与処理
（ステップＳ４４）の第２の部分を示すフローチャート
である。

【図１０】 図１の決定木学習装置によって作成された
頻度確率付き品詞決定木ファイル内の品詞決定木の一例
を示す図である。

【図１１】 図１の決定木学習装置によって作成された
頻度確率付き文法規則決定木ファイル内の品詞決定木の
一例を示す図である。

【図１２】 図１の決定木学習装置によって作成された
頻度確率付き処理方向決定木ファイル内の品詞決定木の
一例を示す図である。

【図１３】 図１の構文情報付与装置における処理途中
のパージング状態及び処理方向の一例を示すフロー図で
ある。

【符号の説明】

１０…決定木学習装置、 １１…構文情報付与装置、 ２１…構文解析済みテキストデータメモリ、 ２２…属性リストメモリ、 ２３…品詞リストメモリ、 ２４…文法規則リストメモリ、 ２５…品詞決定木ファイルメモリ、 ２６…文法規則決定木ファイルメモリ、 ２７…処理方向決定木ファイルメモリ、 ３０…テキストデータメモリ、 ３１…構文解析済みテキストデータメモリ。

フロントページの続き (72)発明者 エズラ・ダブリュー・ブラック 京都府相楽郡精華町大字乾谷小字三平谷５ 番地 株式会社エイ・ティ・アール音声翻 訳通信研究所内 (72)発明者 ステファン・ジー・ユーバンク 京都府相楽郡精華町大字乾谷小字三平谷５ 番地 株式会社エイ・ティ・アール音声翻 訳通信研究所内

Claims (4)

【特許請求の範囲】
1. 【請求項１】 単語列からなる構文解析済みテキストデ
   ータに基づいて、各単語の綴りの特徴と、文章内の使わ
   れ方による特徴と、単語の相互情報量を用いた階層的な
   分類とを含む複数の属性を用いて、上記各属性の属性値
   に依存して分割されるような二分木形式の木構造を有し
   品詞付与のための品詞決定木を生成し、上記生成された
   品詞決定木の分割されないノードであるリーフノードに
   対して複数の品詞に対する頻度確率を計算して付与する
   ことにより、頻度確率付き品詞決定木を生成する品詞決
   定木学習手段と、 単語列からなる構文解析済みテキストデータに基づい
   て、処理対象の単語の語数と、処理対象の主辞単語の品
   詞、処理対象の直前の単語の品詞、単語の相互情報量を
   用いた階層的な分類とを含む複数の属性を用いて、上記
   各属性の属性値に依存して分割されるような二分木形式
   の木構造を有し文法規則付与のための文法規則決定木を
   生成し、上記生成された文法規則決定木の分割されない
   ノードであるリーフノードに対して複数の文法規則に対
   する頻度確率を計算して付与することにより、頻度確率
   付き文法規則決定木を生成する文法規則決定木学習手段
   と、 単語列からなる構文解析済みテキストデータに基づい
   て、処理対象の単語の語数と、処理対象の主辞単語の品
   詞、処理対象の直前の単語の品詞、単語の相互情報量を
   用いた階層的な分類とを含む複数の属性を用いて、上記
   各属性の属性値に依存して分割されるような二分木形式
   の木構造を有し文法規則付与処理における各パージング
   状態で処理方向を決定するための処理方向決定木を生成
   し、上記生成された処理方向決定木の分割されないノー
   ドであるリーフノードに対して複数の処理方向に対する
   頻度確率を計算して付与することにより、頻度確率付き
   処理方向決定木を生成する処理方向決定木学習手段と、 上記品詞決定木学習手段によって生成された頻度確率付
   き品詞決定木を用いて、入力される処理対象の単語列か
   らなるテキストデータに基づいて、上記リーフノードに
   付与された頻度確率の中で上位複数ｎ個の頻度確率を選
   択して上記テキストデータの各単語に対して付与し、上
   記テキストデータの単語列において最大の結合確率を有
   する品詞列を正解品詞列として決定し、次いで、所定の
   スタック・デコーダ・アルゴリズムを用いて、文法規則
   付与処理における各パージング状態での単語列に対する
   結合確率が最大の結合確率を有するパージング状態を選
   択した後、上記処理方向決定木学習手段によって生成さ
   れた頻度確率付き処理方向決定木を用いて上記処理対象
   の単語列における処理方向を決定し、決定された処理方
   向におけるパージング状態において、上記文法規則決定
   木学習手段によって生成された頻度確率付き文法規則決
   定木に従って文法規則を上記処理対象の単語列に加える
   ことにより構文解析情報を付与して構文解析済みテキス
   トデータを出力する構文情報付与手段とを備えたことを
   特徴とする構文解析装置。
2. 【請求項２】 上記各決定木学習手段は、上記二分木の
   形式で分割するときに、上記各属性による分割前の属性
   の有効性の優先順位を表わすエントロピーＨ₀と分割後
   のエントロピーＨとの差（Ｈ₀−Ｈ）が最大の属性を分
   割候補の属性として選択し、所定の分割続行基準を満足
   するときに、二分木の形式で分割して決定木を更新する
   ことを特徴とする請求項１記載の構文解析装置。
3. 【請求項３】 上記分割続行基準は、（Ｉ）選択された
   属性に基づいて分割したときのエントロピーの差（Ｈ₀
   −Ｈ）が所定のエントロピーしきい値Ｈｔｈ以上であ
   り、かつ（II）選択された属性に基づく分割後の属性と
   その属性値及び品詞の組のイベント数が所定のイベント
   数しきい値Ｄｔｈ以上であることを特徴とする請求項２
   記載の構文解析装置。
4. 【請求項４】 上記構文情報付与手段は、上記リーフノ
   ードに付与された頻度確率の中で上位複数ｎ個の頻度確
   率を選択して上記テキストデータの各単語に対して付与
   した後、所定のスタック・デコーダ・アルゴリズムを用
   いて、処理途中のテキストデータの単語列に対する結合
   確率が所定の結合確率以上である品詞候補のみを残して
   品詞候補を限定し、品詞付与処理終了時の上記テキスト
   データの単語列において最大の結合確率を有する品詞列
   を正解品詞列として決定することを特徴とする請求項
   １、２又は３記載の構文解析装置。