研究速報
SPARSEVAL measures に基づく漸進的構文解析

NPの定量的評価

I加藤芳秀† a)（正員）稲垣康善†††∗（名誉員）

松原茂樹††（正員）

VPknowNP
theNP

student

PPwithQuantitative Evaluation of Incremental Parsing by Extending
the PARSEVAL Measures
Yasuyoshi INAGAKI†††∗ , Fellow, Honorary Member

versity, Nagoya-shi, 464-8601 Japanしている [3]．しかし，正解構文木と完全に一致する中Information Technology Center, Nagoya University, Nagoya-

間解析結果のみを正解と判定するため，解析結果が正

愛知県立大学情報科学部，愛知県

解と部分的に一致している場合，それがどの程度一致

Faculty of Information Science and Technology, Aichi Pre-しているかを評価できない．また，解析の漸進性を解

fectural University, Aichi-ken 480-1198 Japan∗

解析過程での解析精度と解析の漸進性の観点から評価

名古屋大学情報連携基盤センター，名古屋市

shi, 464-8601 Japan†††pen名古屋大学大学院国際開発研究科，名古屋市

Graduate School of International Development, Nagoya Uni††

NP

図 1 正解構文木Fig. 1 Correct parse tree.

Yoshihide KATO†a) , Shigeki MATSUBARA†† , Members, and†a析処理全体の遅れにより評価しているが，解析処理全

現在，体の遅れは漸進性に与える影響の一要因に過ぎず，漸a) E-mail: yosihide@gsid.nagoya-u.ac.jp

進性の評価としては不十分である．さらに，精度と漸あらまし

構文解析の標準的な評価指標である PAR-SEVAL measures を拡張し，漸進的構文解析を定量進性というトレードオフの関係にある２つの側面を統合的に評価することもできない．

的に評価する手法を提案する．解析途中で生成される

本論文では，理想的な漸進的構文解析が解析過程で構文解析結果と正解の部分構文木との一致の度合によ明らかにする構文構造のうち，実際の構文解析が再現り漸進的構文解析の精度と漸進性を評価する．

できた割合をその構文解析の漸進性と定義し，構文解キーワード構文解析，PARSEVAL measures，漸析の精度と漸進性を評価する方法を提案する．本手法
は，構文解析の標準的な評価指標である PARSEVAL

進性，ラベル精度，ラベル再現率

1. ま え が きmeasures [1] を拡張したものである．PARSEVAL で漸進的構文解析とは，文をその単語の出現順序には，構文木を構成素に分解し，解析結果の構成素のう従って処理し，文の入力途中の段階で，その構文構造ち正解構成素と一致するものの割合により解析精度をを捉える枠組である．同時通訳やリアルタイム字幕生評価する．本手法ではこれを拡張し，部分構文木中の成などの逐次的な言語処理システムの実現に必要不可構成素と正解構成素の一致に基づいて解析精度を評価

欠な要素技術の一つである．

する．これにより，正解構文木との部分的な一致を考

漸進的構文解析の性能評価においては，最終的に得慮した精度評価が実現できる．また，PARSEVAL でられる文全体に対する構文木のみならず，その解析過は，構文解析により再現できた正解構成素の割合を構程において生成される中間解析結果，すなわち文の断文解析の再現率と定義するが，本手法では，再現率を片に対する部分構文木も評価の対象としなければなら用いて構文解析の漸進性を評価する．精度と再現率のない．逐次的な言語処理システムにおいて構文解析の総合的な評価指標である F 値（精度と再現率の調和平中間解析結果が異なれば，その他のモジュールの動作均）により，漸進的構文解析の精度と漸進性を総合的（例えば，同時通訳システムにおける訳文生成など）にに評価することができる．

2. PARSEVAL measuresも影響を及ぼすからである．
ところが，そのような観点から漸進的構文解析を評

PARSEVAL measures [1] では，構文木を構成素の価する方法については，これまで十分に検討されてい集合として捕らえ，正解構文木に対する構成素集合とない．多くの文献，例えば [2] では，提案した漸進的構文解析結果に対する構成素集合の一致の度合により構文解析を一文単位の構文解析と同様の方法により評構文解析の性能を評価する．以下では例として，図 1

価するのみで，解析途中の振舞いについての評価は行の構文木を正解構文木とし，図 2 を構文解析結果としわれていない．一方，加藤らは，漸進的構文解析を，て説明する．

電子情報通信学会論文誌

X Vol. Jxx–X No. xx pp. 1–5 xxxx 年 xx 月

1

電子情報通信学会論文誌 xxxx/xx Vol. Jxx–X No. xx
(a)

SNP
I

VPknow

PPNP

the

with

student

aNPpen

図 2 構文解析結果
Fig. 2 Parse tree.

(b)

SNP
INPVPknow
NPtheSS?

?

IVPNPknow
the?

図 3 “I know the” に対する部分構文木
Fig. 3 Partial parse trees for “I know the.”

構成素は 3 項組 (s, t, X) として定義される．これは，文 w1 · · · wn に含まれる部分単語列 ws+1 · · · wt

るかの観点からの評価も重要である．例として，文の(0 <= s < t <= n) が ，範 疇 X を 構 成 す る こ と断片 “I know the” について考える．これに対する部を意味する．図 1 の正解構文木に対する構成素集

分構文木としては，図 3 の (a) や (b) が考えられる．

合は，{(0, 1, NP), (1, 7, VP), (2, 7, NP), (2, 4, NP),(a) は “know” が従属節をとり，“the” はその従属節(4, 7, PP), (5, 7, NP)} であり，図 2 に対する構成素集の主語を構成する名詞句の先頭要素であるような部分合は，{(0, 1, NP), (1, 4, VP), (2, 4, NP), (4, 7, PP),

構文木，(b) は “know” が目的語をとり，“the” がそ(5, 7, NP)} である（注 1）．構文解析結果中の構成素のうの目的語を構成する名詞句の先頭要素であるような部

ち，正解と一致するものの割合をラベル精度と呼ぶ．

分構文木である．“I know the” に対する中間解析結

正解構文木に対する構成素集合を TC ，構文解析結果

果の選択方法としては，単純に (a), (b) のいずれかをに対する構成素集合を TG とするとき，ラベル精度は，選択することが考えられるが，その一方で，別のアプ

P = |TC ∩ TG |/|TG | と定義される．図 2 の構文木中のローチが存在する．すなわち，先読み処理などにより構成素のうち，正解構成素に一致するのは，(0, 1, NP),解析処理を遅らせ，部分構文木の選択を延期する方法(2, 4, NP), (4, 7, PP) 及び (5, 7, NP) であり，ラベルである．例えば，“I know the” に続く入力中に，従属精度は 4/5 となる．

節を構成する動詞が存在すれば，それを読んだ時点で一方，ラベル再現率は，正解構文木中の構成素が構(a) と決められる．このようなアプローチでは，解析文解析によりどれだけ再現できたかを示す尺度であり，精度の向上が期待できるものの，先読みした部分（例R = |TC ∩ TG |/|TC | と定義される．例において，ラでは，“student”）に関する構文構造を捉えることがベル再現率は 4/6 となる．

できず，解析の漸進性が損なわれることになる．このラベル精度とラベル再現率を統合的に評価する指標として，F 値が用いられる．F 値はラベル精度とラベル再現率の調和平均，すなわち F = 2P R/(P + R) でように，精度と漸進性の間にはトレードオフの関係があり，その両面から評価することが必要である．
また，漸進性に影響を与える別の要因として，解析ある．F 値は 0 から 1 までの値をとり，ラベル精度，戦略の違いが挙げられる．Lombardo らは，中間解析ラベル再現率がともに高い場合に高い値となり，どち結果が構文構造を明示的に示す下降型構文解析を，上らか一方でも低い場合は，低い値となる．

昇型構文解析や左隅型構文解析と比較して，漸進性が3. 漸進的構文解析の評価手法

強い構文解析と定性的に位置づけているが [4]，このよ

漸進的構文解析は，文をその単語の出現順序に従っうな解析戦略の違いに起因する漸進性の差は，解析処て処理し，段階的に構文木を生成する．解析過程で生理の遅れによる評価では捉えることができない．

成される部分構文木は，途中まで読み込んだ文の断片

これらの問題を解決するために，本節では，2. で説に対する構文構造を表現している．漸進的構文解析を明した PARSEVAL measures を拡張し，漸進的構文用いた逐次的言語処理システムにおいては，生成され解析を評価する方法を提案する．

る部分構文木が正しいか否かが問題となるため，中間

3. 1 部分構文木の構成素解析結果を対象とした精度評価が必要である．

まず，漸進的構文解析において生成される部分構文さらに，解析の漸進性の観点，すなわち，解析途中木の構成素について考える．部分構文木は，文全体にの各段階において構文構造をどの程度明らかにしてい対する構文木とは異なり，未完成の構成素が含まれて（注 1）：構文木の根に対応する構成素は開始記号であり常に一致するため，通常，これを取り除いて評価する．

2

いることが特徴である．構成素が完成しているかそうでないかを明示するために，本手法では構成素を 4 項

レター

組 (s, t, X, c) に拡張し，その構成素が完成しているか

入力： TG (j), TC (i);
出力： M (TG (j), TC (i));

否かを表現する．4 番目の要素 c は，0 か 1 のいずれかで，前者がこの構成素が完成していないことを，後者

M (TG (j), TC (i)) = φ
for each x ∈ TG (j) do
if there exists y ∈ TC (i) s.t. match(x, y)then delete a y from TC (i);add x to M (TG (j), TC (i));

がこの構成素が完成していることを意味する．例えば，
図 3 の部分構文木において，記号 ? は構成素が未完成であること示しているが，部分構文木 (a) に対する構
成素集合は，{(0, 1, NP, 1), (1, 3, VP, 0), (2, 3, S, 0),Fig. 4(2, 3, NP, 0)} である．
文 w1 · · · wn の断片 w1 · · · wi (i <= n) に対する正解
構成素集合 TC (i) は，文全体に対する正解構成素集合

TC をもとに次のように定義する．

図 4 M (TG (j), TC (i)) の計算
Computation of M (TG (j), TC (i)).

•0 （注 2）c = c0 = 1, t = t0 または，c = 0, t <.
=t•

X = X 0.

この定義を用いて，正解構成素にマッチする部分構文

TC (i)= {(s, t, X, 1) | t <= i ∧ (s, t, X) ∈ TC }∪{(s, i, X, 0) | s < i ∧ ∃t > i[(s, t, X) ∈ TC ]}例 え ば ，図 1 を 文 全 体 の 正 解 構 文 木 と す る と き ，
文の断片 “I know the student” に対する正解構成素集合は，{(0, 1, NP, 1), (1, 4, VP, 0), (2, 4, NP, 0),(2, 4, NP, 1)} である．TC (i) は，w1 · · · wi に対する構成素全体からなる集合であり，理想的な漸進的構文解析であれば，これと完全に一致する部分構文木を解
析の各段階において常に生成できる．

3. 2 漸進的構文解析のラベル精度とラベル再現率

木の構成素の集合 M (TG (j), TC (i)) を図 4 のように手続き的に定義する（注 3）．
以上を用いて，漸進的構文解析のラベル精度 P を次のように定義する．

P =|M (TG (j), TC (i))||TG (j)|(1)

例として，図 3 の部分構文木 (a) が “I know the stu-dent” に対する中間解析結果として生成された場合を考える．定義 1 の意味で正解とマッチする構成素は，(0, 1, NP, 1), (1, 3, VP, 0), (2, 3, NP, 0) であるので，ラベル精度は，3/4 となる．
次に再現率について考える．正解構成素が部分構
文木中の構成素と完全にマッチする場合，その構成素

ラベル精度は，解析結果中の構成素のうち，正解構は完全に再現されている．一方，定義 1 の意味でマッ成素とマッチするものの割合であり，部分構文木中のチしている場合，それは正解構成素の一部分しか再完成している構成素については，従来通り正解構成素現していない．例えば，(2, 3, NP, 0) は，正解構成素との完全なマッチングをとればよい．一方，未完成な(2, 4, NP, 1) の “the” に対応する部分のみを再現して構成素については，部分的なマッチングも考慮したほいる．そこで本手法では，ラベル再現率の計算においうがよいと考えられる．例として，図 3 の部分構文ては，単純にマッチする構成素を数えるのではなく，木 (a) の構成素 (2, 3, NP, 0) について考える．この構再現の度合により重み付けして計算する．重み付けは，成素は正解構成素のいずれともマッチしないものの，構成素が覆っている範囲を用いて次のように定義する．

“the” が NP の一部を構成しているという意味で，正構成素 x = (s, t, X, c) とそれにマッチする正解構成素解構成素 (2, 4, NP, 1) の一部分に相当すると捉えるこ

y = (s, t0 , X, c0 ) に対して，とができる．そこで本手法では，このような構成素も正解とマッチするものとみなす．具体的には，文の断w(x, y) =片 w1 · · · wj に対する部分構文木 TG (j) の構成素と正解構成素とのマッチングを次のように定義する．
［定義 1］ x = (s, t, X, c) ∈ TG (j)，及 び y =(s0 , t0 , X 0 , c0 ) ∈ TC (i)(j <= i) に対して，次をすべて満たすとき，かつそのときに限り，match(x, y) は成り立つ．

•s = s0 .

t−st0 − s(2)と定義する．完全に再現されている場合，すなわちt = t0 のとき，w は 1 となり，一方，再現される構成（注 2）：c = 0, c0 = 1, t = t0 のときもこの条件は満たされるが，これは，構成素 x が空系列を補うことにより完成し，y と一致する場合があるためである．
（注 3）：match(x, y) の意味で x とマッチする y = (s0 , t0 , X 0 , c0 ) ∈TC (i) は複数存在する可能性があるが，4. の実験では，t0 が最小のものを選択している．

3

電子情報通信学会論文誌 xxxx/xx Vol. Jxx–X No. xx
SNPI

差を定量的に捉えることができる．
VP

漸進性をラベル再現率により評価することにより，SknowNPさらに，漸進性と精度を統合的に評価することができ?

the student

図 5 “I know the student” に対する部分構文木
Fig. 5 Partial parse tree for “I know the student.”

る．すなわち，ラベル精度とラベル再現率の F 値がその評価尺度である．

4. 評価手法の適用例
本節では，提案評価法の適用例として，上昇型構文解析，左隅型構文解析，下降型構文解析，及び，それ素の範囲が狭くなるにつれて，w は小さくなる．この重み関数を用いて，漸進的構文解析のラベル再現率 R

R=x∈M (TG (j),TC (i))

実験対象として，Penn Treebank [5] に収録されている構文木付き ATIS コーパス全 578 文を用いた．漸を次のように定義する．

Pらに先読みを導入した構文解析を評価する．

w(x, c(x))|TC (i)|

ただし，c(x) は，TC (i) の要素で match(x, c(x)) が成り立つものとする．図 3(a) の例では，ラベル再現率は，(1+ 32 + 12 )/4=13/24 となる．

進的構文解析が対象とする文の断片は 4353 個である．
構文解析には確率文脈自由文法を使用し，その文法規則は，578 文に付与された構文木から獲得した．文法規則の確率は最尤推定により計算した．
中間解析結果は，下降型構文解析については，文の断片に対する部分構文木の中で確率最大のものを選択

ここで定義したラベル再現率は，中間解析結果が正した．左隅型構文解析，及び上昇型構文解析について解構成素をどの程度再現できたかを，言い換えれば，は，文の断片に対してそれを覆うような部分構文木は解析過程で構文構造をどの程度捉えることができたか生成されず，確率の比較による選択はできないため，を表現している．すなわち，ラベル再現率は，漸進性

本実験では，それらの中間解析結果に相当するものを，を測定する尺度とみなすことができる．

下降型構文解析の中間解析結果をもとにして以下のよ

解析処理の遅れに起因する漸進性の低下について，うに生成した．なお，以下では，文の断片 w1 · · · wi

例を用いて考える．1 語先読みを用いる場合，“I knowに対する下降型構文解析の中間解析結果を T D(i) とthe student” に対して，図 3(a) のような “I know

記す．

the” に対する部分構文木が生成され，そのラベル再現

上昇型構文解析の中間解析結果

率は上述のように 13/24 である．一方，先読みを用い節点 τ について，τ が未完成な（子孫に ? が出現する）ない場合，図 5 のような “I know the student” をす節点であるならば，τ を取り除く．

べて覆う部分構文木が生成される．この部分構文木の左隅型構文解析の中間解析結果

ラベル再現率は 3/4 である．図 3(a) の部分構文木の節点 τ について，τ の左端の子が未完成であるならば，ラベル再現率は，図 5 のそれと比べて低くなっている．

τ を取り除く．

このように，ラベル再現率により，解析の遅れに起因する漸進性の差を捉えることができる．
また，ラベル再現率により，構文解析戦略の違いにT D(i) 中のすべてのT D(i) 中のすべての先読みを用いた構文解析についてもその中間解析結果を，下降型構文解析の中間解析結果をもとに生成した．以下がその手順である．

起因する漸進性の差も捉えることができる．例えば，

k 語先読み T D(i) 中のすべての節点 τ について，τ

図 5 の部分構文木は，下降型構文解析により生成されの左端の単語が wl (i − k < l) であるならば，τ を取る中間解析結果の一例であるが，これに対応する上昇り除く．

型構文解析の中間解析結果は，この部分構文木から未この手順により生成される中間解析結果は，完成な構成素を取り除いたものである．すなわち，構w1 · · · wi−k に対する部分構文木となる．すなわち，成素 (1, 4, VP, 0) や (2, 4, S, 0) は認識されておらず，wi−k+1 以降の構造はすべて未完成として扱われる．

その構成素集合は，{(0, 1, NP, 1), (2, 4, NP, 1)} であ

下降型，左隅型，上昇型，及びそれらに 0〜2 語先る．そのラベル再現率は，2/4 である．下降型構文解

読みを導入した構文解析について，ラベル精度と漸進

析のラベル再現率は，上昇型構文解析のそれと比べて性を測定した．評価結果を表 1 に示す．

高くなっており，解析戦略の違いに起因する漸進性の4

処理の遅れにより漸進性を評価する場合，下降型，

レター
表1 評価結果
Table 1 Experimental results.

種類
下降型

左隅型

上昇型

先読み (語) 再現率 (%)
086.7
165.2
251.6
078.2
160.4
248.2
042.0
141.8
235.5精度 (%)
92.1
92.5
92.6
93.7
93.8
93.8
92.3
92.2
91.9

English grammars”, Proc. Speech and Natural Language Workshop, pp.306–311, 1991.
F 値
89.3
76.5
66.3
85.2
73.5
63.7
57.8
57.5
51.2

[2]

the perceptron algorithm”, Proc. 42nd Annual Meeting of the Assoc. for Computational Linguistics,
pp.112–119, 2004.
[3]

incremental parsing, Proc. of the ACL Workshop Incremental Parsing: Bringing Engineering and Cognition Together, pp. 9–15, 2004.

Annual Conference of the Cognitive Science Society,して評価することになる．しかし，先読み語の数が同ングが同じであっても，中間解析結果の表現する構文構造は大きく異なることを意味する．逆に言えば，処V. Lombardo and P. Sturt, “Incremental Processing and Infinite Local Ambiguity”, Proc. of the 19th

左隅型，上昇型構文解析の漸進性は，先読み語の数と順に大きく減少する．このことは，解析処理のタイミ

Y. Kato, S. Matusbara and Y Inagaki, “Stochastically evaluating the validity of partial parse trees in[4]

じであっても，再現率は，下降型，左隅型，上昇型のM. Collins and B. Roark, “Incremental parsing with

pp.448–453, 1997.
[5]

M. P. Marcus, B. Santorini, and M. A. Marcinkiewicz,“Building a large annotated corpus of English: thePenn Treebank”, Computational Linguistics, vol.19,no.2, pp.310–330, 1993.

（平成 xx 年 xx 月 xx 日受付）

理の遅れによる漸進性の評価は，処理タイミングが早いのみで，文の断片の構文構造を明らかにできないよ
うな構文解析を，漸進性が高い解析と評価する危険性があることを意味する．再現率による漸進性の評価を用いれば，この問題は回避できる．一方，先読みにより解析処理が遅れるにつれて，再現率も減少していることから，再現率は，処理の遅れについても反映した漸進性の評価尺度であると位置づけることができる．

5. あ と が き
本論文では，漸進的構文解析の精度と漸進性を定量的に評価する指標を提案し，構文解析実験により，その有効性を確認した．
漸進的構文解析が用いられるアプリケーションによっては，精度，あるいは漸進性のどちらか一方が他方に優先されるケースが考えられる．精度と漸進性に重み付けを行い F 値を求めることにより，一方に重点を置いた評価ができるが，アプリケーションに依存した評価についても今後検討したい．
謝辞

本論文を改善する上で，査読者の方には貴重なご意見を頂きました．ここに深く感謝いたします．
本研究の一部は，科学研究費若手研究 (B)(課題番号:17700145) の助成を受けています．
文
[1]

献

E. Black, S. Abney, D. Flickenger, C. Gdaniec, R. Grishman, P. Harrison, D. Hindle, R. Ingria, F. Jelinek,
J. Klavans, M. Liberman, M. Marcus, S. Roukos,
B. Santorini and T. Strzalkowski, “A procedure forquantitatively comparing the syntactic coverage of5

Abstract This paper proposes a method for evaluating incremental parsers quantitatively. The method
defines two measures of incremental parser performance: precision and incrementality by extending thePARSEVAL measures, which are well-known measures for phrase-structure parsers.
Key words parsing, PARSEVAL measures, incrementality, labelled precision, labelled recall