JPH0855122A

JPH0855122A - 文脈タガー

Info

Publication number: JPH0855122A
Application number: JP7157872A
Authority: JP
Inventors: Shiyabisu Ibu; シャビスイブ; Roshie Emaniyueru; ロシエエマニュエル
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1994-06-24
Filing date: 1995-06-23
Publication date: 1996-02-27
Also published as: US5610812A

Abstract

(57)【要約】【目的】英語テキストに品詞タグ付けをするシステム
において、決定的有限状態トランスデューサを用いるこ
とで、大量の文書に対しても高速で正確にタグ付けでき
る文脈タガーを提供する。【構成】文脈ルールのシーケンス１３を非決定的トラ
ンスデューサのシーケンス１６に変換し、コンポーザ１
７、ディターミニスタ１９を用いて、決定的有限状態ト
ランスデューサ１１へと変換する。入力文にタグ付けを
するには、まずその文中の周囲の単語とは無関係に、最
も可能性の高い品詞タグを単語に割り当てる。その結果
の品詞タグのシーケンスを、決定的有限状態トランスデ
ューサ１１によって、周囲の単語との関連によって最終
的な品詞タグが付けられる。また品詞タグ付けに必要な
時間は、入力文中の単語の数に比例し、適用するルール
の数とは無関係である。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、英語のテキストに品
詞タグ付けをするシステム、特に、トレーニングコーパ
スから自動的に得られるルールによる、決定的有限状態
トランスデューサを用いた品詞タグ付けに関するもので
ある。

【０００２】

【従来の技術】英語という言葉は、品詞という点で不明
瞭である。つまり、ある単語が名詞であったり、動詞の
過去形であったり、動詞の過去分詞であったりする。例
えば、”ｌｅｆｔ”という単語は、”Ｉｔｏｏｋａ
ｌｅｆｔｔｕｒｎ．”（私は左の回転をした。）と
いう文では、「左の」という形容詞である。”Ｈｅｉ
ｓｏｎｍｙｌｅｆｔ．”（彼は私の左にいる。）
という文では、「左」という名詞である。”Ｈｅｌｅ
ｆｔｙｅｓｔｅｒｄａｙ．”（彼は昨日発った。）と
いう文では、”ｌｅａｖｅ”（発つ）という動詞の過去
形である。更に、”Ｈｅｈａｓｌｅｆｔ．”（彼は
発ってしまった。）という文では、”ｌｅａｖｅ”とい
う動詞の過去分詞形である。しかしながら、文脈の中で
は、英語の単語は不明瞭ではない。英語のテキストを扱
うのに必要なことは、文脈の中でのそれぞれの単語の品
詞を正しく割り当てることである。これは、品詞タグ付
けと呼ばれる問題である。

【０００３】文法チェッカ、スペルチェッカ、テキスト
検索、音声認識、ハンドライティング認識装置、文字認
識装置、テキスト要約装置等で英語のテキストを扱うに
は、文の中でこの品詞のシーケンスを見分けることが最
も重要である。品詞から品詞のシーケンスが得られる。
例えば、”Ｉｈｅａｒｄｔｈｉｓｂａｎｄｐｌ
ａｙ．”（私はこのバンドが演奏するのを聞いた。）と
いう文が入力されれば、「代名詞、動詞、限定詞、名
詞、動詞」という品詞のシーケンスとなる。

【０００４】従来の英語のテキストに品詞タグ付けをす
る方法は、統計ベースの方法かルールベースの方法かの
どちらかである。統計ベースの方法としては、「確率論
的品詞プログラムと開放テキストのための名詞句解
剖」”ＡＳｔｏｃｈａｓｔｉｃＰａｒｔｓＰｒｏ
ｇｒａｍａｎｄＮｏｕｎＰｈｒａｓｅＰａｒｓ
ｅｒｆｏｒＵｎｒｅｓｔｒｉｃｔｅｄＴｅｘｔ”
（第二回応用自然言語処理会議議事録ｔｈｅＰｒｏ
ｃｅｅｄｉｎｇｓｏｆｔｈｅＳｅｃｏｎｄＣｏ
ｎｆｅｒｅｎｃｅｏｎＡｐｐｌｉｅｄＮａｔｕｒ
ａｌＬａｎｇｕａｇｅＰｒｏｃｅｓｓｉｎｇ、オー
スティンテキサス、１９８８年）に記載されたケニス
・チャーチの確率論的品詞プログラム（Ｋｅｎｎｅｔｈ
Ｃｈｕｒｃｈ’ｓＳｔｏｃｈａｓｔｉｃＰａｒｔ
ｓＰｒｏｇｒａｍ）、「品詞タグ付けのための方程
式」”Ｅｑｕａｔｉｏｎｓｆｏｒｐａｒｔ−ｏｆ−
ｓｐｅｅｃｈｔａｇｇｉｎｇ”（ＡＡＡＩ９３第九
回全国人工知能会議議事録ｔｈｅＰｒｏｃｅｅｄｉ
ｎｇｓｏｆｔｈｅＡＡＡＩ９３，ＮｉｎｔｈＮ
ａｔｉｏｎａｌＣｏｎｆｅｒｅｃｅｏｎＡｒｔｉ
ｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ１９９３
年）に記載されたチャーニアック、ユージーン、カーテ
ィス・ヘンドリクソン、ニール・ジャコブソン、マイク
・ペルコヴィツによる方法、「隠れマルコフモデルを用
いた確定的品詞タグ付け」”Ｒｏｂｕｓｔｐａｒｔ−
ｏｆ−ｓｐｅｅｃｈｔａｇｇｉｎｇｕｓｉｎｇａ
ｈｉｄｄｅｎｍａｒｋｏｖｍｏｄｅｌ”（コンピ
ューター音声と言語ジャーナル第六巻ｔｈｅｊｏｕ
ｒｎａｌｏｆＣｏｍｐｕｔｅｒＳｐｅｅｃｈａｎ
ｄＬａｎｇｕａｇｅｖｏｌｕｍｅ６１９９２年）
に記載されたジュリアン・クーピックの方法、「確率モ
デルによる曖昧さと未知の単語への対処」”Ｃｏｐｉｎ
ｇｗｉｔｈａｍｂｉｇｕｉｔｙａｎｄｕｎｋｎ
ｏｗｎｗｏｒｄｓｔｈｒｏｕｇｈｐｒｏｂａｂｉ
ｌｉｓｔｉｃｍｏｄｅｌｓ”（コンピューター言語ジ
ャーナル第十八巻第二番ｔｈｅｊｏｕｒｎａｌｏｆ
ＣｏｍｐｕｔａｔｉｏｎＬｉｎｇｕｉｓｔｉｃｓ
ｖｏｌｕｍｅ１８，ｎｕｍｂｅｒ２１９９３年）
に記載されたラルフ・ウィスケデル、マリィ・ミター、
リチャード・シュワルツ、ランス・ラムショウ、ジェフ
・パルマッチによる方法がある。ルールベースの方法と
しては「ルールベースの品詞タガー」”Ａｓｉｍｐｌ
ｅｒｕｌｅ−ｂａｓｅｄｐａｒｔｏｆｓｐｅｅ
ｃｈｔａｇｇｅｒ”（第三回応用自然言語処理会議議
事録ｔｈｅｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ
ＴｈｉｒｄＣｏｎｆｅｒｅｎｃｅｏｎＡｐｐｌｉ
ｅｄＮａｔｕｒａｌＬａｎｇｕａｇｅＰｒｏｃｅ
ｓｓｉｎｇ１９９２年）に記載されたエリック・ブリ
ルの方法がある。

【０００５】

【発明が解決しようとする課題】従来技術による品詞タ
グ付けの方法は、入力文の単語の数、更に、適用するル
ールの数によって、品詞タグ付けの時間が決まるので、
大変時間がかかるものであった。つまり、例えば、図書
館の蔵書のような大量の英語のテキストに品詞タグ付け
をするには、従来技術によるシステムは適用できなかっ
た。

【０００６】前述したように、近年、ブリルによってル
ールベースのタガーが提案された。これは、確率モデル
によるタガーと同様の効果が得られ、ルールベースの言
語処理へのアプローチの共通の限界を克服するものであ
る。タグ付けは確実なものであり、ルールは自動的に得
られる。更に、このタガーは、確率論的なタガーより
も、はるかに少ないスペースですむ。しかしながら、現
在実施されているブリルのタガーは、確率モデルによる
タガーよりも、かなり遅いものである。これは、Ｃ語の
文脈から得られるＲ個のルールを用いて、ｎ語の入力に
タグ付けをするためには、ＲＣｎ個のエレメンタリース
テップを要するためである。

【０００７】例えば、ブリルの方法によれば、２００個
の文脈タグ付けルールを用いれば、品詞タグを決めるの
にそれぞれの単語にこれを適用していく。これは、一つ
一つのルールをそれぞれの単語に当てはめていくもの
で、また一つのルールによる結果を、後から適用した他
のルールによる結果が変えることもある。ブリルの方法
が大変時間がかかることの原因の一つは、一つのルール
による結果を他のルールによる結果が変えることもある
という、この非決定的なアプローチにある。一方、タグ
付けのスピードを上げるためには、一つの単語を読み込
むと、ただ一つの品詞が決められ、一つ以上のパスを要
しない、決定的タグ付けシステムが望まれる。

【０００８】ブリルのタガーは、トレーニングコーパス
から推論される三つの部分からなる。辞書的タガー、未
知の単語タガー、それに文脈タガーである。未知の単語
タガーは後述することとして、ここでは主として、辞書
的タガーと文脈タガーを説明する。

【０００９】品詞タグ付けに用いる記号は、次のように
する。”ｐｐｓ”は三人称単数主格代名詞、”ｖｂｄ”
は動詞過去形、”ｎｐ”は固有名詞、”ｖｂｎ”は動詞
過去分詞形、”ｂｙ”は”ｂｙ”という単語、”ａｔ”
は限定詞、”ｎｎ”は単数名詞、”ｂｅｄｚ”は”ｗａ
ｓ”という単語を、それぞれ表している。

【００１０】ブリルによる辞書的タガーは、文脈に関わ
りなく、多くのタグ付けされたトレーニングコーパスを
調べることで、推測される最も可能性の高い品詞タグ
を、最初にそれぞれの単語に割り当てる。例えば、単
語”ｋｉｌｌｅｄ”に対して”ｖｂｎ”が最も可能性の
高いタグであり、”ｓｈｏｔ”には”ｖｂｄ”が最も可
能性の高いタグであるとすれば、辞書的タガーにより、
次のような品詞タグが付けられる。（１）Ｃｈａｐｍａｎ／ｎｐｋｉｌｌｅｄ／ｖｂｎ
Ｊｏｈｎ／ｎｐＬｅｎｏｎ／ｎｐ（２）Ｊｏｈｎ／ｎｐＬｅｎｏｎ／ｎｐｗａｓ／ｂ
ｅｄｚｓｈｏｔ／ｖｂｄｂｙ／ｂｙＣｈａｐｍａ
ｎ／ｎｐ（３）Ｈｅ／ｐｐｓｗｉｔｎｅｓｓｅｄ／ｖｂｄＬ
ｅｎｏｎ／ｎｐｋｉｌｌｅｄ／ｖｂｎｂｙ／ｂｙ
Ｃｈａｐｍａｎ／ｎｐ

【００１１】ブリルによる辞書的タガーは、文脈につい
ての情報を何も用いないために、多くの単語が間違って
タグ付けされる。上記の例では、（１）の”ｋｉｌｌｅ
ｄ”は動詞の過去分詞形と誤ってタグ付けされ、（２）
の”ｓｈｏｔ”は動詞の過去形と誤ってタグ付けされて
いる。このシステムでは、辞書的タガーによって得られ
た最初のタグ付けに対して、その後、ルールのシーケン
スを適用していき、最初のタグ付けのエラーを正すもの
である。例えば、次のようなルールが文脈タガーに用い
られる。ルール１：ｖｂｎｖｂｄＰＲＥＶＴＡＧｎｐルール２：ｖｂｄｖｂｎＮＥＸＴＴＡＧｂｙ

【００１２】ルール１は、タグ”ｖｂｎ”の前のタグ
が”ｎｐ”であれば、”ｖｂｎ”ではなく”ｖｂｄ”に
変えるよう規定している。ルール２では、タグ”ｖｂ
ｄ”の次のタグが”ｂｙ”であれば、”ｖｂｄ”ではな
く”ｖｂｎ”に変えるよう規定している。ルール１の適
用により、（１）と（３）中の”ｋｉｌｌｅｄ”に対す
るタグは”ｖｂｎ”ではなく、”ｖｂｄ”となり、タグ
付けされた文は次のようになる。（４）Ｃｈａｐｍａｎ／ｎｐｋｉｌｌｅｄ／ｖｂｄ
Ｊｏｈｎ／ｎｐＬｅｎｏｎ／ｎｐ（５）Ｊｏｈｎ／ｎｐＬｅｎｏｎ／ｎｐｗａｓ／ｂ
ｅｄｚｓｈｏｔ／ｖｂｄｂｙ／ｂｙＣｈａｐｍａ
ｎ／ｎｐ（６）Ｈｅ／ｐｐｓｗｉｔｎｅｓｓｅｄ／ｖｂｄＬ
ｅｎｏｎ／ｎｐｋｉｌｌｅｄ／ｖｂｄｂｙ／ｂｙ
Ｃｈａｐｍａｎ／ｎｐ

【００１３】更に、ルール２の適用により、（５）の”
ｓｈｏｔ”に対するタグは”ｖｂｄ”ではなく”ｖｂ
ｎ”となり、タグ付けされた文は（８）のようになる。
また、（６）の”ｋｉｌｌｅｄ”に対するタグは”ｖｂ
ｄ”から”ｖｂｎ”に戻され、タグ付けされた文は
（９）のようになる。（７）Ｃｈａｐｍａｎ／ｎｐｋｉｌｌｅｄ／ｖｂｄ
Ｊｏｈｎ／ｎｐＬｅｎｏｎ／ｎｐ（８）Ｊｏｈｎ／ｎｐＬｅｎｏｎ／ｎｐｗａｓ／ｂ
ｅｄｚｓｈｏｔ／ｖｂｎｂｙ／ｂｙＣｈａｐｍａ
ｎ／ｎｐ（９）Ｈｅ／ｐｐｓｗｉｔｎｅｓｓｅｄ／ｖｂｄＬ
ｅｎｏｎ／ｎｐｋｉｌｌｅｄ／ｖｂｎｂｙ／ｂｙ
Ｃｈａｐｍａｎ／ｎｐ

【００１４】ブリルによれば、文脈ルールは、自動的に
トレーニングコーパスから推測される。まず、辞書的タ
ガーによるタグ付けを実行する。タグ付けエラーリスト
がエラーの数とともに、辞書的タガーによるタグ付け結
果と正しい品詞付けとを比べることにより生成される。
次に、エラーリストのそれぞれのエラーに対して、一組
の文脈ルールテンプレートのどの場合がエラーを最も効
率よく減らすか決められる。そして、そのルールを適用
することによる新しいエラーが計算される。この過程
は、エラーの減少がある閾値より低くなるまで繰り返さ
れる。図１５に一組の文脈ルールテンプレートを示す。

【００１５】図１５に示す文脈ルールテンプレートをト
レーニングすることで、２８０個の文脈ルールが得られ
る。この結果、確率モデルベースのタガーと同様の効果
が得られ、ルールベースの言語処理へのアプローチに共
通の限界を克服できる。つまり、ブリルのタガーは確実
であり、ルールは自動的に得られる。更に、ブリルのタ
ガーは、確率論的タガーよりもはるかに少ないスペース
ですむ。しかしながら、ブリルのタガーは、本質的に遅
い点が問題である。

【００１６】辞書的タグ付けがなされると、ブリルのア
ルゴリズムによって、トレーニングによって得られた文
脈ルールを、それぞれの文に適用しタグ付けがされる。
それぞれのルールについて、アルゴリズムが、そのルー
ルをトリガしようとする間に、入力文を左から右へスキ
ャンする。この単一アルゴリズムは、下記の二つの点で
計算上非能率的である。

【００１７】一つには、入力文のそれぞれのトークンに
一つのルールを適用する時、そのトークンが、前の位置
で、同じルールを適用されているかもしれないというこ
とを、無視して行われる点で非能率的である。ブリルの
アルゴリズムは、それぞれのルールが、入力文のタグに
対してスライドするテンプレートであるかのように作用
する。例えば、ＡＢＰＲＥＶＢＩＧＲＡＭＣＣ
（前二つのタグがＣである時、タグＡをタグＢに変え
よ。）というルールについて検討してみる。入力ＣＤ
ＣＣＡに適用すると、図１６（ａ），（ｂ），
（ｃ）に示すように、三つの列が考えられる。それぞれ
の段階で、前段階の部分的一致、又は不一致は記録され
ていない。図１６の例では、（ｂ）の列は、（ａ）の情
報が得られれば、スキップすることができるはずであ
る。

【００１８】このアルゴリズムが非能率的である二つ目
の理由は、ルール間の相互作用の可能性である。例え
ば、ルール１とルール２を、 ”Ｈｅ／ｐｐｓｗｉｔｎｅｓｓｅｄ／ｖｂｄＬｅｎ
ｏｎ／ｎｐｋｉｌｌｅｄ／ｖｂｎｂｙ／ｂｙＣｈ
ａｐｍａｎ／ｎｐ” という文に適用すると、ルール１によって、 ”Ｈｅ／ｐｐｓｗｉｔｎｅｓｓｅｄ／ｖｂｄＬｅｎ
ｏｎ／ｎｐｋｉｌｌｅｄ／ｖｂｄｂｙ／ｂｙＣｈ
ａｐｍａｎ／ｎｐ” と変化し、更に、ルール２によって、 ”Ｈｅ／ｐｐｓｗｉｔｎｅｓｓｅｄ／ｖｂｄＬｅｎ
ｏｎ／ｎｐｋｉｌｌｅｄ／ｖｂｎｂｙ／ｂｙＣｈ
ａｐｍａｎ／ｎｐ” となる。

【００１９】つまり、このアルゴリズムは不必要な計算
をする可能性があり、非能率的である。ブリルの文脈タ
ガー実施のためのアルゴリズムは、Ｃトークンの文脈か
ら得られるＲ個の文脈ルールを用いて、ｎ語の入力にタ
グ付けをするためには、ＲＣｎ個のエレメンタリーステ
ップを要する。

【００２０】この発明は、以上のような問題点を解決す
るためになされたものであり、英語のテキストに品詞タ
グを非常に高速に割り当てる文脈タガーを得ることを目
的とする。

【００２１】また、この発明は、統計やルールに基づい
た従来のアプローチに基づかずに、品詞のタグ付けを正
確に行うことが可能なルールの集合を獲得することを目
的とする。

【００２２】また、この発明は、獲得したルールの集合
を用いて最終的に決定的有限状態トランスデューサに変
換することを目的とする。

【００２３】また、この発明は、入力文に対して文脈と
は無関係に、各単語に対して最も可能性の高い品詞をタ
グ付けし、その後、文脈を用いて最終的な品詞タグを得
る文脈タガーを得ることを目的とする。

【００２４】また、この発明は、文脈ルールの数に依存
しない時間により、品詞のタグ付けを行う文脈タガーを
得ることを目的とする。

【００２５】

【課題を解決するための手段】この発明に係る文脈タガ
ーは、入力文の単語に品詞タグ付けをする文脈タガーに
おいて、入力文の単語に対し、シングルパスで、文脈に
応じてタグ付けする決定的有限状態トランスデューサを
備えたことを特徴とする。

【００２６】上記決定的有限状態トランスデューサは、
各入力単語に対し、ただ一つのタグ付けを選択する手段
を有することを特徴とする。

【００２７】上記ただ一つのタグ付けを選択する手段
は、可能なタグ付けの選択のうち、ただ一つの選択を確
定できるに充分な文脈を読み込むまで、タグ付けの選択
を延期する手段を有することを特徴とする。

【００２８】上記単語は、上記入力文において、それぞ
れが特定可能なシーケンシャルな位置を持つとともに、
上記決定的有限状態トランスデューサは、その単語の品
詞を決定するための解析のために、一つの位置で単語を
選択する手段と、上記文中の先行する単語の品詞に基づ
いて、上記選択した単語の品詞を選択する手段と、上記
文中の先行する単語の品詞が、上記選択した単語の品詞
の決定に関し、ただ一つの結論へ導かないときは、上記
選択した単語の品詞の選択を禁じる手段を有することを
特徴とする。

【００２９】上記決定的有限状態トランスデューサは、
上記選択した単語の品詞を選択する手段とともに、上記
入力文の上記選択した単語の品詞の選択が明確になるま
で、上記入力文の他の単語の品詞を解析する手段の動作
を禁止する手段を有することを特徴とする。

【００３０】上記他の単語の品詞を解析する手段は、上
記選択した単語に後続する位置にある他の単語のみを選
択することを特徴とする。

【００３１】上記入力文の単語に、周囲の単語とは関わ
りなく、最も可能性の高い品詞を割り当てることで初期
的タグ付けする手段と、周囲の単語を文脈として用い
て、最終的な品詞タグ付けをするために、上記決定的有
限状態トランスデューサを利用する手段を有することを
特徴とする。

【００３２】上記決定的有限状態トランスデューサは、
タグ付けしたテキストのトレーニングコーパスから生成
されたタグ付けルールのセットと、上記タグ付けルール
を入力とする非決定的トランスデューサと、一つ以上の
上記非決定的トランスデューサの出力をあわせて、一つ
の総合的な非決定的トランスデューサに変換するコンポ
ーザと、正しいタグ付けの選択をするため充分な量の文
脈情報が得られるまで、タグ付けの選択に関して決定を
延期するディターミニスタとから生成されることを特徴
とする。

【００３３】上記決定的有限状態トランスデューサは、
上記入力文中の単語の文脈の違いに従って、以前に決定
した品詞のシーケンスの有限個の数のみを利用すること
を特徴とする。

【００３４】

【作用】この発明における文脈タガーは、決定的有限状
態トランスデューサを備えており、入力文を左から右へ
読み込むとき、有限個の単語のみを用いてタグ付けを行
う。また、入力した単語に対して、たった一つのタグ付
けがなされるようにする。このように、決定的有限状態
トランスデューサを用いることにより、文脈タガーの処
理を一つの経路をたどって決定的なタグ付けを行う。

【００３５】また、この発明においては、一つの単語の
に対してただ一つのタグ付けを選択するので、一つの経
路をたどることによりタグ付けを行う。

【００３６】また、この発明においては、ただ一つのタ
グ付けを選択できるようになるまで充分な文脈を読み込
むので、タグ付けを延期する。

【００３７】また、この発明においては、入力文の左か
ら右に向かったただ一つの経路を用いてタグ付けを行う
ので、ある注目した単語の品詞を決定する場合に、先行
する単語の品詞に基づいて注目した単語の品詞を選択す
る。もし、注目した単語の品詞が、先行する単語の品詞
に基づいて選択できない場合には、注目した単語の品詞
の選択を行わない。

【００３８】また、この発明においては、注目した単語
の品詞が決定されるまで、後に存在する他の単語の品詞
の解析を行わない。

【００３９】また、この発明においては、単語の品詞を
解析する手段は、注目した単語より後にある単語のみを
選択する。従って、タグ付けが注目した単語よりも、先
行する単語の品詞の解析結果に基づいてなされることは
ない。

【００４０】また、この発明においては、上記決定的有
限状態トランスデューサを利用する前に、初期的タグ付
けを行い、初期的タグ付けによるエラーを上記決定的有
限状態トランスデューサにより訂正する。

【００４１】また、この発明においては、上記決定的有
限トランスデューサは、トレーニングコーパスから生成
された文脈ルールを入力として、非決定的トランスデュ
ーサを生成し、生成された非決定的トランスデューサに
対して、コンポーザとディターミニスタを作用させるこ
とにより生成される。

【００４２】また、この発明においては、上記決定的有
限トランスデューサが、有限個の品詞のシーケンスを利
用してタグ付けを行い、処理時間を短縮する。

【００４３】

【実施例】本実施例では、英語のテキストに品詞タグ付
けをするシステムを構築するために、まず、タグ付けし
たテキストのトレーニングコーパスを調べることで、タ
グ付けルールのセットを得る。このトレーニング段階
で、辞書中のそれぞれの単語は、トレーニングコーパス
の中で最も可能性の高い品詞を伴う。例えば、”ｌｅｆ
ｔ”という単語は、”ＶＥＲＢ−ＰＡＳＴ−ＴＥＮＳ
Ｅ”（動詞過去形）という品詞が付いている。この”ｌ
ｅｆｔ”という単語は、”ＡＤＪＥＣＴＩＶＥ”（形容
詞）の場合もあるが、頻度がより少ないのでここでは記
録されていない。この辞書によるタグ付けでは、”Ｔｕ
ｒｎｌｅｆｔａｔｔｈｅｌｉｇｈｔ．”のよう
な文では多くのエラーを生んでしまう。この最初のタグ
付けで生じたエラーは、トレーニングコーパスから自動
的に得られる文脈ルールのシーケンスを、適用すること
で訂正される。文脈ルールの一例を挙げれば、”ＣＨＡ
ＮＧＥＶＥＲＢ−ＰＡＳＴ−ＴＥＮＳＥＴＯＡＤ
ＪＥＣＴＩＶＥＩＦＴＨＥＰＲＥＶＩＯＵＳＴ
ＡＧＩＳＶＥＲＢ．”（前の単語の品詞タグが動詞
であったら、動詞過去形は形容詞に変えよ。）というも
のである。最初のタグ付けの出力を正しい品詞付けと比
較して、タグ付けのエラーをそのエラーの数とともにリ
ストにしておく。上記の文脈ルールは、こうしたリスト
をコンパイルすることで自動的に得られる。次に、それ
ぞれのエラーに対しては、一組のルールテンプレートの
どのテンプレートがエラーを最も効率よく減らすか決め
られる。そして、そのルールを適用することによる新し
いエラーが計算され、この過程は、エラーの減少がある
閾値より低くなるまで繰り返される。一組の文脈ルール
テンプレートを用いて、正しい品詞が添えられた３０，
０００文のトレーニングコーパスについて、トレーニン
グすると、２８０個の文脈ルールが得られる。これらの
ルールは、決定的有限状態トランスデューサと呼ばれる
コンパクトな装置に変換され、文脈タガーとして機能す
る。有限状態トランスデューサは、有限状態のオートマ
トンであり、その遷移は、ペアのシンボルによってラベ
ル付けされる。ペアのシンボルのうち一つは入力であ
り、もう一つは出力である。有限状態トランスデューサ
を入力に適用することは、入力シンボルに従って文をた
どっていく一方、出力シンボルを記憶することであり、
その結果は、出力シンボルのシーケンスとなる。

【００４４】一セットのルールを適用するのに、本発明
の文脈タガーには、四つのステップがある。最初のステ
ップで、それぞれの文脈ルールをルール−トランスデュ
ーサ変換機と呼ぶ有限状態トランスデューサに変える。
文脈ルールは、それぞれローカルに規定され、そこに書
かれた変換のルールは、入力文のそれぞれの位置で適用
される。例えば、”ＡＢＰＲＥＶ１ＯＲ２ＴＡＧ
Ｃ”（一つか二つ前の品詞タグがＣであれば、品詞タグ
ＡをＢに変えよ。）というルールは、ＣＡＡにおいて
は二回適用され、出力はＣＢＢになる。二番目のス
テップで、前のステップで作られたトランスデューサ
を、一つのパスの入力に対してグローバルに動作するト
ランスデューサに変える。これは、ローカル拡張変換機
によって行われる。三番目のステップで、コンポーザを
用いて、全部のトランスデューサを単一トランスデュー
サとする。この単一トランスデューサは、各トランスデ
ューサに規定された合成動作に相当する。このステップ
で得られたトランスデューサは、非決定要素を持ってい
るためまだ最適化されたものではない。四番目の最終ス
テップでは、三番目のステップで得られた有限状態トラ
ンスデューサを、ディターミニスタを用いて同等の決定
的トランスデューサへと変換する。こうして得られた有
限状態トランスデューサは、最初にタグ付けされた文
（辞書的タグ付けと未知の単語のタグ付けがされている
文）に対して、ルールの数や文脈の長さとは無関係に、
線形時間で動作する文脈タガーである。こうして、従来
のどのシステムよりも高速で動作する文脈タガーが得ら
れる。

【００４５】（ａ）文脈タガーの構成図１に、最初にタグ付けした文のタグ付けを改良するた
めの本発明の文脈タガーの構成方法を示す。文脈ルール
のシーケンス１３を、ルール−トランスデューサ変換機
１２に入力することによって、最終的に決定的トランス
デューサ１１を出力する。この決定的トランスデューサ
１１は、有限状態トランスデューサであるとともに、文
脈タガーである。ルール−トランスデューサ変換機１２
は、ルールをトランスデューサに変換するものであり、
出力は、トランスデューサのシーケンス１４である。こ
のトランスデューサのシーケンス１４は、文脈タガーで
ある。しかし、この文脈タガーは、トランスデュースの
際、非決定的な選択をすること、また、トランスデュー
サを入力文のそれぞれの位置で適用しなければならない
ことから、大変処理スピードが遅い。

【００４６】この文脈タガーのスピードを上げるため、
ルール−トランスデューサ変換機１２の出力であるトラ
ンスデューサのシーケンス１４を、ローカル拡張変換機
１５に入力する。ローカル拡張変換機１５で、以下に述
べる特別なアルゴリズムを用いることにより、入力文の
それぞれの接尾辞に、トランスデューサを繰り返し適用
するのではなく、一回の入力に対し、ただ一度トランス
デューサを適用すればよいことになる。

【００４７】ローカル拡張変換機１５の出力は、複数の
非決定的トランスデューサから構成された非決定的トラ
ンスデューサのシーケンス１６となる。ここで、「非決
定的」というのは、入力文のそれぞれの位置で、複数の
選択がされるということである。ローカル拡張変換機１
５の特別なアルゴリズムによるこの文脈タガーは、ルー
ル−トランスデューサ変換機１２の出力である文脈タガ
ーよりは、なにがしか処理スピードが速いが、入力文に
多くのトランスデューサを適用すること、また、そのト
ランスデューサは非決定的であるため、まだかなり処理
が遅いものである。

【００４８】文脈タガーの処理スピードをあげるため
に、コンポーザ１７を用いる。コンポーザ１７は、ロー
カル拡張変換機１５から出力された非決定的トランスデ
ューサのシーケンス１６を入力する。コンポーザ１７
は、入力された複数の非決定的トランスデューサを併合
し、単一の総合的非決定的トランスデューサ１８を出力
する。この結果、入力文に対し、単一の総合的非決定的
トランスデューサ１８だけ適用すればよい文脈タガーが
得られる。

【００４９】総合的非決定的トランスデューサ１８は、
入力文にタグ付けするスピードという点では、かなり改
善されているものの、この総合的非決定的トランスデュ
ーサ１８は、なお非決定的なものでしかない。そのた
め、品詞を分析するために、タガーの処理は、正しいタ
グ付けを決定する経路を選択できるまで、複数の経路を
進まなければならない。結果の分からない経路をたどっ
ていくのは時間の無駄である。複数の経路の計算をする
ことなく、一つの単語の品詞を決定できる処理システム
が求められる。

【００５０】非決定的トランスデューサに関わる問題を
なくすために、総合的非決定的トランスデューサ１８
は、ディターミニスタ１９に入力される。ディターミニ
スタ１９は、正しい品詞の選択をするのに充分なだけの
情報が得られるまで、計算の経路を決定するのを延期す
るものである。計算の経路が二つあったら、続く単語を
見て、正しい結果につながる経路がわかるまで、どちら
の経路を進むか決定しない。こうして、ディターミニス
タは、文の次の単語を一つ以上見て、正しい経路を確認
し、この時点で、計算経路を決定する。ディターミニス
タ１９の出力は、こうして決定的トランスデューサ１１
である文脈タガーとなる。ブリルによる文脈タガーとは
異なり、本発明の文脈タガーは、決定的有限トランスデ
ューサを用いている。

【００５１】それぞれの文脈ルールによって表された機
能は、非決定的な有限状態の変換を意味している。ま
た、それぞれの文脈ルールのシーケンシャルな適用も、
また、それぞれの変換の合成である非決定的な有限状態
の変換を意味している。文脈ルールの機能を非決定的な
有限状態の変換ととらえることにより、非決定的トラン
スデューサを決定的トランスデューサに変えることを可
能とする。この結果による文脈タガーは、ルールの数や
文脈の長さとは無関係に線形時間で動作する。新しい文
脈タガーは、最適な時間で動作する。つまり、一つの文
にタグ付けする時間は、有限状態マシンのただ一つの決
定的な経路を進むための時間で決まる。

【００５２】本発明のシステムには、二つの中心的概念
がある。有限状態トランスデューサの概念とシーケンシ
ャル・トランスデューサの概念である。有限状態トラン
スデューサは、有限状態のオートマトンであり、その遷
移は、シンボルのペアによってラベル付けされる。シン
ボルのペアのうち一つは入力であり、もう一つは出力で
ある。有限状態トランスデューサを入力に適用すること
は、入力シンボルに従ったパスをたどっていくととも
に、出力シンボルを記憶することを意味しており、その
結果としては、出力シンボルのシーケンスが記憶される
こととなる。

【００５３】以下、有限状態トランスデューサを図示す
る場合、有限状態は二重丸で表す。シンボルＥは、空の
ストリングを表す。状態ｉから状態ｊへの状態遷移の場
合、ａ／ｂは入力シンボルａと出力シンボルｂによる状
態遷移を表す。状態ｉから出力された弧線の状態遷移に
用いられた疑問符？（例えば、？／ｂ）は、状態ｉから
出力された他の弧線に用いられた入力シンボル以外のシ
ンボルであることを表す。

【００５４】一例として、図２を用いて文脈ルール２の
シーケンスを、文脈ルールのシーケンス１３とする場合
について説明する。文脈ルールのシーケンス１３を、ル
ール−トランスデューサ変換機１２にし、有限状態トラ
ンスデューサのシーケンス１４に変える。例えば、”ｖ
ｂｎｖｂｄＰＲＥＶＴＡＧｎｐ”というルールの
機能は、図２に示すトランスデューサになる。

【００５５】それぞれの文脈ルールは、ローカルに規定
されている。つまり、文脈ルールに規定された遷移は、
入力文のそれぞれの位置で適用されなければならない。
例えば、”ＡＢＰＲＥＶ１ＯＲ２ＴＡＧＣ”（一
つか二つ前のタグがＣであればＡをＢに変えよ。）とい
うルールは、ＣＡＡでは二回適用されなければなら
ない（その結果、出力ＣＢＢとなる）。こうした非
効率を改善したい。

【００５６】トランスデューサのシーケンス１４を、ロ
ーカル拡張変換機１５によって、新たな非決定的トラン
スデューサのシーケンス１６にする。この新たな非決定
的トランスデューサのシーケンス１６は、シングルパス
で入力文に対してグローバルに動作するものであり、処
理スピードが向上する。ここで、機能のローカル拡張の
例を示す。ｆ１は変換を表し、例えば、ａをｂに変換す
ることをｆ１（ａ）＝ｂと表す。この機能ｆ１を機能ｆ
２（例えば、ｆ２はｆ２（ｗ）＝ｗ０とする）に拡張し
ようとする。ここで、ｗ０は、ａの各オカレンスをそれ
ぞれｂに置き換えてある単語ｗから作った単語である。
機能ｆ２は、機能ｆ１のローカル拡張であると言い、ｆ
２＝ＬｏｃＥｘｔ（ｆ１）と書く。

【００５７】”ｖｂｎｖｂｄＰＲＥＶＴＡＧｎ
ｐ”というルールの、トランスデューサをローカル拡張
したものを図３に示す。同様に、文脈ルール”ｖｂｄ
ｖｂｎＮＥＸＴＴＡＧｂｙ”のトランスデューサを図
４に示し、そのローカル拡張を図５に示す。これらの拡
張方法は、後述する「（ｂ）ローカル拡張変換機」にお
いて説明する。

【００５８】以上により得られた非決定的トランスデュ
ーサのシーケンス１６では、なお、一つずつ適用してい
く必要がある。これらのトランスデューサを、コンポー
ザ１７により、単一の総合的非決定的トランスデューサ
１８にする。この操作は、トランスデューサ内に規定さ
れた合成動作による。図６に示す一例は、図３のローカ
ル拡張を、図５のローカル拡張と合成した総合的非決定
的トランスデューサ１８である。

【００５９】この有限状態トランスデューサを、ディタ
ーミニスタ１９に入力し、ディターミニスタにより同等
の決定的トランスデューサ１１に変形して、最終トラン
スデューサを得る。

【００６０】図６に示す総合的非決定的トランスデュー
サ１８は、いくつかの非決定的経路があるため非決定的
である。例えば、状態０からは、入力シンボルｖｂｄに
より二つの状態遷移が可能である。即ち、出力シンボル
がｖｂｎとなる状態０から状態２への遷移と、ｖｂｄと
なる状態０から状態３への遷移が可能である。この非決
定性は、”ｖｂｄｖｂｄＮＥＸＴＴＡＧｂｙ”と
いうルールのためである。このルールによると、どちら
のシンボルを出力すべきか知る前に、二番目のシンボル
を読み込まねばならないため、非決定性が生ずる。図７
に、決定的トランスデューサ１１を示す。図７におい
て、非決定が生じたら、決定的トランスデューサが空の
ストリングを表すシンボルＥを発し、出力シンボルの発
行は延期される。例えば、最初の状態０に対して入力シ
ンボルｖｂｄが入力されると、空のストリングが出力さ
れ、現在状態は状態２となる。次の単語が”ｂｙ”であ
れば、状態２から状態０へ遷移し、二つのトークン・ス
トリング”ｖｂｎｂｙ”が出力される。次の単語が”
ｂｙ”でなければ、その単語に応じて状態２から状態
２、又は、状態２から状態０に遷移し、”ｖｂｄ”が出
力される。ディターミニスタについては、後述する
「（ｃ）ディターミニスタ」において、更に説明する。

【００６１】以上の結果、トランスデューサ１１は、線
形時間で動作する品詞タガーとなり、この時間はルール
の数や文脈の長さとは無関係である。こうして本発明の
システムは最適な時間で動作する。

【００６２】本発明による文脈タガーのタグ付け処理過
程を図８に示す。入力文２６を辞書的タガー１６に入力
する。辞書的タガー２８は、辞書を用いて文中のそれぞ
れの単語を参照し、最も可能性の高いタグ付けをして、
部分的タグ付け文３０を出力する。この辞書的タガー２
８による出力は、辞書中に見られない単語もあるために
部分的タグ付けをした文となる。部分的タグ付け文３０
は、次に未知の単語タガー３２によってタグ付けされ
る。未知の単語タガー３２は、未知の単語に対して、例
えば、最後の三文字を元に品詞タグを推測するものであ
る。この未知の単語タガーの出力は、初期タグ付け文３
４となる。図１に示す過程で構築された文脈タガーは、
決定的トランスデューサ１１であり、図８では文脈タガ
ー３８として示している。この文脈タガー３８を初期タ
グ付け文３４に適用して、最終タグ付け文３６を得る。

【００６３】前述した各種タガー２８，３２，３８の中
で、記憶容量の点から辞書的タガー２８の用いる辞書
は、最大のものであり、コンパクトな形態にすることは
非常に重要である。また、辞書を参照するスピードは大
変速くなければならない。辞書を参照するスピードが遅
ければ、文脈操作のスピードを改善しても、実務上の利
益は望めない。この過程での処理スピードを上げるた
め、辞書をアクセスが速く記憶容量が小さい決定的有限
状態オートマトンとする。このアルゴリズムは、ドミニ
ク・レヴ（Ｒｅｖｕｚ，Ｄｏｍｉｎｉｑｕｅ）による
「辞書と語彙、方法とアルゴリズム」（”Ｄｉｃｔｉｏ
ｎｎａｉｒｅｓｅｔＬｅｘｉｑｕｅｓ，Ｍｅｔｈｏ
ｄｅｓｅｔＡｌｇｏｒｉｔｈｍｅｓ”，Ｐｈ．Ｄ．
ｔｈｅｓｉｓ，ＵｎｉｖｅｒｓｉｔｅＰａｒｉｓ
７）に１９９１年記載された。これによれば、まず文字
によりラベル付けされた枝、一つ以上の品詞タグの（ｎ
ｎ，ｖｂのような）リストによりラベル付けされた葉を
もつ木を作り、それを最小にして方向付けされた非循環
グラフＤＡＧ（ｄｉｒｅｃｔｅｄａｃｙｃｌｉｃｇ
ｒａｐｈ）とする。

【００６４】例えば、図９に示すＤＡＧには、次のよう
な単語と品詞タグが符号付けされている。単語”ａｄ
ｓ”は、複数名詞”ｎｎｓ”である；単語”ｂａｇ”
は、名詞”ｎｎ”であり、また、動詞”ｖｂ”である可
能性もある；単語”ｂａｇｇｅｄ”は、動詞過去分詞”
ｖｂｎ”か、動詞過去形”ｖｂｄ”である；単語”ｂａ
ｙｅｄ”は、動詞過去分詞”ｖｂｎ”か、動詞過去形”
ｖｂｄ”である；単語”ｂｉｄｓ”は、複数名詞”ｎｎ
ｓ”である。

【００６５】このように、辞書をＤＡＧに置き換えるこ
とにより、辞書で単語を探すという動作は、単にＤＡＧ
の一つの経路をたどっていけばよいことになる。探し出
す煩雑さは単に単語の長さによって決まり、辞書のサイ
ズとは無関係である。

【００６６】本発明のシステムは、辞書的タガー２８に
より全部の既知の単語（即ち、辞書中にある単語）への
タグ付けを終えた後、そして、文脈タガー３８により文
脈ルールのセットが適用される前に、未知の単語タガー
３２を動作させる。未知の単語タガー３２は、単語の接
尾辞によって品詞タグを推測し（例：接尾辞”ｉｎｇ”
を有する単語は動詞であることが多い）、単語の接頭辞
によって品詞タグを推測し（例：大文字で始まる単語は
固有名詞であることが多い）、その他単語の特性によっ
て品詞タグを推測する。この推測のテクニックは、辞書
を構築する場合に用いられるテクニックと基本的に同じ
ものである。

【００６７】本発明のシステムによるタガーの精度は、
統計ベースによるタグ付けの精度に匹敵する。けれど
も、統計ベースによるシステムよりもかなり高速であ
る。本発明のシステムによるタガーは、他の最も速いシ
ステムよりも十倍近く高速処理する。更に、有限状態タ
ガーは、ルール・ベースによるシステムの継承であり、
統計ベースのタガーよりもコンパクトである。実際、統
計ベースのタガーでは、単語、そしてバイグラム、トリ
グラムそれぞれの確率を記憶している必要があるが、ル
ール・ベースのタガー、そして有限状態タガーは、ほん
の少量のルール（せいぜい２００から３００）を記憶す
るだけである。

【００６８】本発明のシステムによるタガーを、エリッ
ク・ブリルの「確率論的品詞プログラムと開放テキスト
のための名詞句解剖」”ＡＳｔｏｃｈａｓｔｉｃＰ
ａｒｔｓＰｒｏｇｒａｍａｎｄＮｏｕｎＰｈｒ
ａｓｅＰａｒｓｅｒｆｏｒＵｎｒｅｓｔｒｉｃｔ
ｅｄＴｅｘｔ”（第二回応用自然言語処理会議ｔｈ
ｅＳｅｃｏｎｄＣｏｎｆｅｒｅｎｃｅｏｎＡｐ
ｐｌｉｅｄＮａｔｕｒａｌＬａｎｇｕａｇｅＰｒ
ｏｃｅｓｓｉｎｇ１９８８年）に記載されたタガー
や、チャーチによるトリグラムタガーと、実験的に比較
した。これら三つのプログラムで、大容量のファイルを
操作した。

【００６９】図１０に、実験の結果を要約して示す。統
計ベース・タガー、ルールベース・タガー、本発明のタ
ガーの全部のタガーをブラウンコーパスの一部分でトレ
ーニングした。実験は、３２メガバイトのメモリーを持
つＨＰ７２０で行われた。有限状態タガーは、ルールベ
ースによるタガーと同じ出力形態をとるように設計し
た。これら三つのタガーによるタグ付けの精度は、どれ
も殆ど同じであった（９５％のタグ付けが正確であっ
た）。

【００７０】本発明によるシステムは、図１０に示す速
度を比較すると分かるように、従来のどのシステムより
も、かなり高速で動作する。このことは、電子ライブラ
リーに含まれるような大量のテキストにタグ付けする際
には、最も重要な点である。

【００７１】（ｂ）ローカル拡張変換機ローカル拡張変換機の概念と構築について、更に、詳細
に述べる。ローカル拡張変換機の概念は、ローカルに規
定された機能を、グローバルな規定に変えるという考え
である。図１１に示す機能全体をトランスデューサＴ１
とし、単語”ａｂ”を入力するものとすると、トランス
デューサＴ１は、最初の入力文字”ａ”に対して、状態
０から状態１への遷移４０を適用して、結果として、”
ｂ”が出力され、二番目の入力文字”ｂ”に、状態１か
ら状態２への遷移４６を適用することで、”ｃ”が出力
される。その結果、入力された単語”ａｂ”は、”ｂ
ｃ”に変わる。同様に、トランスデューサＴ１によっ
て、単語”ｂ”は遷移５０を通じて単語”ｄ”へと変わ
る。トランスデューサＴ１は、ローカルにはトランスデ
ューサＴ２の規定もしている。トランスデューサＴ２
は、入力としてどんな単語でもよく、入力と同じ単語を
をのまま出力する機能であるとともに、トランスデュー
サＴ１の入力となる”ａｂ”と”ｂ”のオカレンスは、
全てそれぞれ”ｂｃ”と”ｄ”に変換する機能である。
例えば、トランスデューサＴ２は、単語”ｂｂｂｂｃｃ
ｃｃｃｃａｂｃｃｃａｂｃｃｃ”を入力すると、”ｄｄ
ｄｄｃｃｃｃｃｃｂｃｃｃｃｂｃｃｃｃ”へ変換する。

【００７２】この変換を最も高速に実行するための最良
の方法は、図１１のトランスデューサＴ１の表記を、あ
らかじめ図１２のトランスデューサＴ２にコンパイルし
ておくことである。その方法を次に示す。トランスデュ
ーサＴ２の状態０，１，３，６は、トランスデューサＴ
１の状態０，１，２のセットによって、指標付けされ
る。また、変換（ｔｒａｎｓｄｕｃｔｉｏｎ）か同一
（ｉｄｅｎｔｉｔｙ）かのタイプによって、指標付けさ
れる。こうしてトランスデューサＴ２の状態０，１，
３，６は、変換タイプか同一タイプのどちらかになる。

【００７３】例えば、図１１の５２で表される状態０
は、状態のセット｛０｝によって指標付けされ、同一タ
イプと表される。同一タイプというのは、入力したもの
を変えないということであり、”ｃ”が入力した文字で
あれば、”ｃ”はそのまま形であり、けっして変換され
ない。このことは、５８と５９で図示された遷移により
明らかである。変換タイプは、トランスデューサＴ１に
よる修正を受けるということであり、図１２の５４で表
される状態３に見られる。ここでは、”ａ”は、状態０
から遷移５６を通じて、”ｂ”に変換される。この遷移
は、図１１に示したトランスデューサＴ１の、状態０か
ら状態１への遷移４０に対応している。図１２の初期状
態０で、入力文字”ａ”が変換されない場合があること
を考慮すべきである（単語”ａａ”の場合）。このと
き、”ａ／ａ”とラベル付けされた遷移６０を作る。こ
の遷移は、状態１へ向けられており、ここのタイプは同
一タイプであり、この点までは入力を変化させないとい
うことを意味する。この状態１は、図１１のトランスデ
ューサＴ１の４４で表された状態１、また、図１１のト
ランスデューサＴ１の４２で表された初期状態０に対応
している。こうして、図１２の６１で表された状態１
は、状態のセット｛０，１｝とラベル付けされ、同一タ
イプと示される。図１２に示す他の遷移や状態も、同様
に構築される。例外は、図１１のトランスデューサＴ１
で４８と記された状態２、そして、図１２の状態６であ
るが、これは最終状態である。最終状態は、二重丸で書
かれている。最終状態では、遷移は完了し、初期状態０
に戻ることが可能である。これは、図１２中で、”ε／
ε”とラベル付けされた遷移６２に示されている。これ
によって、状態６４から、空のストリングεを読み、空
のストリングεを出すことにより、初期状態０へ進むこ
とができる。

【００７４】（ｃ）ディターミニスタ有限状態トランスデューサを得る場合、非決定的なもの
よりも、決定的に適用できる同等の有限状態トランスデ
ューサを得る方が望ましい。図１３に示されるような有
限状態トランスデューサを得るが、このトランスデュー
サは決定的ではない。単語”ａｄ”を入力した時、最初
の文字は”ａ”である。状態０からスタートすると、二
つの可能性がある。一つ目の選択は、”ａ”を読み”
ｂ”を出力して状態１へいく。二つ目の選択は、やは
り”ａ”を読むが、”ｃ”を出力して状態２へ進む。入
力文字の二番目を読むと、”ｄ”であり、一つ目の選択
が実際の入力に関わるものであるとわかり、最終出力
は”ｂｄ”となる。こう言った選択をしなければならな
いことは、大変な時間を要してしまう。そこで、複数の
可能性の選択をしなくてよい有限状態トランスデューサ
が必要である。このような有限状態トランスデューサ
は、決定的と呼ばれる。

【００７５】決定的トランスデューサ構築方法を次に記
す。図１３に示すトランスデューサＴ３を用いるとき、
図１４に示す決定的トランスデューサＴ４は、以下の方
法で構築される。シンボルのペアが（０，ε）であり、
この０はトランスデューサＴ３の状態０を表し、εはこ
の位置では何も発しない（空の単語εを発する）ことを
表している。まず、図１４の７２に示す初期状態０を作
る。トランスデューサＴ３の状態０で読めるのは、入力
シンボル”ａ”のみである。初期状態０では、ただ一つ
の遷移のみが可能である。この遷移には、入力シンボ
ル”ａ”とラベル付けされる。出力シンボルを決めるの
に、トランスデューサＴ３の全部の出力シンボルを見
て”ｂ”と”ｃ”を得る。出力シンボルが複数あるの
で、ここでは何を出力するか決定できない。従って、何
も出力せずεを出力し、次の７４で示す状態１に延期し
た出力が記憶される。

【００７６】７４で示す状態１では、（１，ｂ）は、延
期した出力”ｂ”を持ってトランスデューサＴ３の状態
１（図１３の６８）にいることが可能であることを表し
ている。（２，ｃ）は、延期した出力”ｃ”を持ってト
ランスデューサＴ３の状態２（図１３の７０）にいるこ
とが可能であることを表している。図１４の状態１は、
図１３の状態１又は状態２に対応しているので、この状
態１には二つの入力シンボルが可能である。即ち、状態
１に対応している”ｄ”、状態２に対応している”ｅ”
が入力可能である。

【００７７】シンボル”ｄ”が入力された場合は、トラ
ンスデューサＴ３の状態１（図１３の６８）に対応す
る。図１４の状態１に記憶されたペア（１，ｂ）によ
り、延期されたシンボルは、”ｂ”であることになる。
図１３を見ると、入力シンボル”ｄ”に対する状態１か
ら状態３への出力シンボルは、”ｄ”である。こうし
て、新たな出力シンボルと延期されたシンボルをあわせ
ると、遷移７８からの出力は、”ｂｄ”となる。更に、
ここではもはや出力を延期する必要はなくなる。こうし
て、図１４の遷移７８により状態２へと進み、状態２
は、トランスデューサＴ３の状態２と延期したシンボル
として、空のストリングとでラベル付けされる。

【００７８】同様にして、７４で示す状態１にシンボ
ル”ｅ”が入力された場合の出力は、”ｃｅ”となる。
ここでも、シンボル出力の延期は必要ない。こうして、
次の状態２は、やはり（２，ε）とラベル付けされ、遷
移８２によって状態２へと進む。以上の過程で、決定的
有限状態トランスデューサＴ４が構築される。このトラ
ンスデューサＴ４は、入力に対して同じ変換をすると言
う意味で、トランスデューサＴ３と同等である（例え
ば、トランスデューサＴ３によってもトランスデューサ
Ｔ４によっても”ａｄ”は、”ｂｄ”と変換され
る。）。しかしながら、トランスデューサＴ４は決定的
であるので、トランスデューサＴ４はトランスデューサ
Ｔ３よりもはるかに高速な処理ができる。

【００７９】（ｄ）まとめブリルの方法に比べて、本発明のシステムでは、長さｎ
の文にタグ付けをするのにｎステップあればよく、ルー
ルの数や必要な文脈の長さとは無関係である。

【００８０】ブリルのタガーにおける各ルールは、一つ
の非決定的有限状態トランスデューサとなり、ブリルの
タガーの全てのルールは、これら非決定的有限状態トラ
ンスデューサを結びつけることにより、全体として一つ
の非決定的有限トランスデューサとして構築することが
できる。

【００８１】一方、本発明の文脈タガーは、このような
非決定的有限状態トランスデューサではなく、一つの文
にシングルパスで文脈に基づいたタグ付けができる決定
的有限状態トランスデューサである。決定的有限状態ト
ランスデューサは、関連した文脈を記憶し、それを有限
状態に変換する。「有限状態」の意味は、入力文を左か
ら右へ読み込む時、入力文の有限個の文脈のみを記憶す
ることである。こうして、有限状態トランスデューサ
は、それぞれの位置で、既に読み込まれた入力文の一部
分の有限個の単語のみを用いて、入力文から、タグ付け
した文を出力するものである。

【００８２】更に、「決定的」ということは、それぞれ
の入力した単語に対し、たった一つのタグ付けがされる
ようにすることである。

【００８３】本発明の決定的有限状態トランスデューサ
は、タグ付けを決定するに必要充分な文脈を読み込まな
いうちは、タグを選択しない。つまり、可能な選択のう
ち、ただ一つのタグが文脈にふさわしいものと確認でき
てから、タグ付けをする。

【００８４】この結果、決定的トランスデューサは、理
想的な時間で動作する品詞タガーとなる。つまり、この
有限状態マシンで、一つの経路をたどって決定的にタグ
付けをするのに要する時間によって、一つの文にタグ付
けをする時間が決まる。本発明のシステムに用いられる
辞書も、有限状態マシンを用いて、最適化され、符号化
される。

【００８５】

【発明の効果】以上のように、この発明によれば、決定
的有限状態トランスデューサを備えることにより、入力
文に対して品詞タグを非常に高速に割り当てることがで
きる。従って、大きな文書においても、各文に対して品
詞を高速にタグ付けすることができ、結果として、高速
な文法チェック、高速なスペルチェック、高速な情報抽
出、或いは、高速な光学的文字認識を可能にすることが
できる。

【００８６】また、この発明によれば、各単語に対して
ただ一つのタグ付けを行うので、入力文を左から右にタ
グ付けを行うことにより、タグ付けが終了する。従っ
て、品詞のタグ付けに必要な時間は、入力文の単語の数
に比例し、適用するルールの数とは無関係になる。

【００８７】また、この発明によれば、タグ付けを延期
する手段を有しているので、入力文を後戻りすることな
く、品詞のタグ付けを確定することができる。

【００８８】また、この発明によれば、入力文の注目す
る単語の位置を左から右にずらしていくことにより、注
目する単語の選択とその単語の品詞の選択を順に行うこ
とができる。また、注目する単語の品詞が確定しない場
合には、単語の品詞の選択を禁ずる手段により、品詞の
選択を保留することができる。

【００８９】また、この発明によれば、後続の単語の品
詞を解析する手段の動作を禁止するとともに、先行する
単語の品詞を先に確定するので、入力文をワンパスでタ
グ付けすることができる。

【００９０】また、この発明においては、他の単語の品
詞を解析する手段は、後続する単語のみを選択するの
で、先行する単語の品詞を溯って解析するという状態が
生じない。

【００９１】また、この発明によれば、入力文に対して
文脈とは無関係に最も可能性の高い品詞タグを単語に割
り当て、その後、決定的有限状態トランスデューサを用
いて品詞タグ付けを行うため、初期的タグ付けにより生
じたエラーを文脈に基づいて訂正することができる。

【００９２】また、この発明によれば、タグ付けされた
テキストのトレーニングコーパスを調べることによりル
ールの集合を獲得するので、統計やルールに基づいた従
来のアプローチよりも、性能が優れている文脈ルールを
獲得することができる。また、コンポーザ及びディター
ミニスタを備えていることにより、トレーニングコーパ
スから得られたルールの集合から最終的に決定的有限状
態トランスデューサを生成することができる。

【００９３】また、この発明によれば、決定的有限トラ
ンスデューサは、以前に決定した有限個の品詞のシーケ
ンスに基づいてタグ付けを行うため、更に、効率の良い
タグ付けを行うことができる。

【図面の簡単な説明】

【図１】この発明による文脈タガーの構成を示すブロ
ック図。

【図２】この発明による有限状態トランスデューサの
一例を示す図。

【図３】図２の有限状態トランスデューサをローカル
拡張した有限状態トランスデューサを示す図。

【図４】この発明による有限状態トランスデューサの
別の例を示す図。

【図５】図４の有限状態トランスデューサをローカル
拡張した有限状態トランスデューサを示す図。

【図６】図３と図５の有限状態トランスデューサを合
成した有限状態トランスデューサを示す図。

【図７】図６の有限状態トランスデューサをディター
ミニスタにより変換した決定的有限状態トランスデュー
サを示す図。

【図８】この発明の文脈タガーによるタグ付け処理を
表すブロック図。

【図９】有限状態オートマトンによる辞書の符号化を
示す図。

【図１０】この発明による文脈タガーと二つの従来の
タガーによる実験の結果を示す図。

【図１１】ローカルな規定による有限状態トランスデ
ューサの一例を示す図。

【図１２】図１１と同等のグローバルな規定による有
限状態トランスデューサを示す図。

【図１３】非決定的有限状態トランスデューサの一例
を示す図。

【図１４】図１３と同等の決定的有限状態トランスデ
ューサを示す図。

【図１５】従来例による文脈ルールテンプレートのセ
ットの一例を示す図。

【図１６】従来例による文脈ルールを適用したタグ付
けの過程を示す図。

【符号の説明】

１１文脈タガー（決定的トランスデューサ）、１２
ルール−トランスデューサ変換機、１３文脈ルールの
シーケンス、１４トランスデューサのシーケンス、１
５ローカル拡張変換機、１６非決定的トランスデュ
ーサのシーケンス、１７コンポーザ、１８非決定的
トランスデューサ、１９ディターミニスタ、２６入
力文、２８辞書的タガー、３０部分的タグ付け文、
３２未知の単語タガー、３４初期タグ付け文、３６
最終タグ付け文、３８文脈タガー。

Claims

【特許請求の範囲】

【請求項１】入力文の単語に品詞タグ付けをする文脈
タガーにおいて、入力文の単語に対し、シングルパス
で、文脈に応じてタグ付けする決定的有限状態トランス
デューサを備えたことを特徴とする文脈タガー。
【請求項２】上記決定的有限状態トランスデューサ
は、各入力単語に対し、ただ一つのタグ付けを選択する
手段を有することを特徴とする請求項１記載の文脈タガ
ー。
【請求項３】上記ただ一つのタグ付けを選択する手段
は、可能なタグ付けの選択のうち、ただ一つの選択を確
定できるに充分な文脈を読み込むまで、タグ付けの選択
を延期する手段を有することを特徴とする請求項２記載
の文脈タガー。
【請求項４】上記単語は、上記入力文において、それ
ぞれが特定可能なシーケンシャルな位置を持つととも
に、上記決定的有限状態トランスデューサは、その単語の品詞を決定するための解析のために、一つの
位置で単語を選択する手段と、上記文中の先行する単語の品詞に基づいて、上記選択し
た単語の品詞を選択する手段と、上記文中の先行する単語の品詞が、上記選択した単語の
品詞の決定に関し、ただ一つの結論へ導かないときは、
上記選択した単語の品詞の選択を禁じる手段を有するこ
とを特徴とする請求項１記載の文脈タガー。
【請求項５】上記決定的有限状態トランスデューサ
は、上記選択した単語の品詞を選択する手段とともに、
上記入力文の上記選択した単語の品詞の選択が明確にな
るまで、上記入力文の他の単語の品詞を解析する手段の
動作を禁止する手段を有することを特徴とする請求項４
記載の文脈タガー。
【請求項６】上記他の単語の品詞を解析する手段は、
上記選択した単語に後続する位置にある他の単語のみを
選択することを特徴とする請求項５記載の文脈タガー。
【請求項７】上記入力文の単語に、周囲の単語とは関
わりなく、最も可能性の高い品詞を割り当てることで初
期的タグ付けする手段と、周囲の単語を文脈として用い
て、最終的な品詞タグ付けをするために、上記決定的有
限状態トランスデューサを利用する手段を有することを
特徴とする請求項１記載の文脈タガー。
【請求項８】上記決定的有限状態トランスデューサ
は、タグ付けしたテキストのトレーニングコーパスから生成
されたタグ付けルールのセットと、上記タグ付けルールを入力とする非決定的トランスデュ
ーサと、一つ以上の上記非決定的トランスデューサの出力をあわ
せて、一つの総合的な非決定的トランスデューサに変換
するコンポーザと、正しいタグ付けの選択をするため充分な量の文脈情報が
得られるまで、タグ付けの選択に関して決定を延期する
ディターミニスタとから生成されることを特徴とする請
求項１記載の文脈タガー。
【請求項９】上記決定的有限状態トランスデューサ
は、上記入力文中の単語の文脈の違いに従って、以前に
決定した品詞のシーケンスの有限個の数のみを利用する
ことを特徴とする請求項１記載の文脈タガー。