構文木の再帰構造除去に基づく文圧縮手法と複数正解に基づく評価
江川誠二†

加藤†名古屋大学大学院情報科学研究科

芳秀‡

茂樹§

松原‡名古屋大学大学院国際開発研究科§名古屋大学情報連携基盤センター

egawa@el.itc.nagoya-u.ac.jp

1

はじめに

文圧縮とは，文の主要な情報を保持したまま，より短い文を生成するタスクであり，テキスト自動要約の実現に必要不可欠な技術である．また，テレビの字幕やニュースのヘッドラインの自動生成など文の長さに制限がある場面で有用である．
文圧縮によって生成される文を圧縮文と呼ぶ．圧縮文は次の条件を満たす必要がある．

S1
NP2

VP4

PRP3 AUX5
Itis

ADJP6

JJ7

SBAR8

likelyIN9that• 原文の主要な情報を保持している

NP11

VP15

DT12 NN13 NN14 MD16a• 文法的である

S10

Macintosh version

will

VP17

AUX18 ADJP19 ADVP21
beJJ20RB22

availablesoon

これまでに様々な文圧縮手法が提案されている．それ
図 1: 構成素の削除のみでは圧縮が難しい例
らの多くは，構文木に基づき句や節などを認識し，原文から単語，句，あるいは節などを取り除くことにより圧縮文を生成する [6, 7, 9, 10, 11]．しかし，実際には，単2 構成素の除去に基づく文圧縮
純な構成素の削除では対処することが難しい，構文木の構造の変更が必要な場合が存在する．
従来の文圧縮手法の多くは，入力として文 l を受け取
そこで本稿では，構文木の構造的な変更による文圧 り，l からいくつかの単語を取り除いた文を返す [6, 7,縮手法を提案する．本手法では，構文木の再帰構造に注 9, 10, 11]．
目する．再帰構造は，付加詞や等位構造，埋め込み文な
このうち，Knight ら [7] や Unno ら [11] は，構文木ど，構文木中に頻出するが，構成素の削除による文圧縮 に基づく文圧縮手法を提案している．入力文 l を構文解手法では，これを文法的に自然な形で処理することがで 析し，得られた構文木中の生成規則を縮約することによきない．本手法では，構文木に出現する再帰的な構造を り，構成素を削除し，圧縮文を生成する．
検出し，これを除去する操作を導入する．操作の適用にしかし，生成規則の縮約では実現が難しい文圧縮が存
は曖昧性があるため，操作が適用される確率を圧縮文 在する．次のような場合である．
コーパスから学習する．
(1) It is likely that a Macintosh version will be
圧縮文コーパスを用いて評価実験を実施した．被験available soon.
者実験により，圧縮文の文法性において，提案手法が既(2)A
Macintosh version will be available.
存の手法に比べて優れていることを確認した．さらに，
文圧縮の多様性という観点から，複数の正解を用意し， (1) は原文で，(2) はその圧縮文である．この圧縮におこれを用いて評価実験を行った．その結果，提案手法が いて，“It is likely that” は 1 つのまとまりとして削除
既存の手法と比べ，人手の圧縮に近い圧縮文を生成する されたと考えられる．“It is likely that” の一部を残すことを確認した．
ような削除のいずれも，圧縮文を不適格文にしてしまうからである．
ところが，従来の文圧縮手法によりこのような圧縮を行う場合，これをまとまりとして削除することはできな

い．図 1 は原文 (1) の構文木である．従来の文圧縮手法
では，構文木中の下線を引いたノードをそれぞれ単独で削除することになる．すなわち，原文・圧縮文の対からなる圧縮文コーパスから圧縮のプロセスを学習するとき，それぞれの構成素を独立に削除するプロセスを学習することになり，その結果，不適格な圧縮文を生成してしまう危険性がある．

S10NP11

VP15

DT12 NN13 NN14 MD16aMacintosh version

will

VP17

AUX18 ADJP19 ADVP21
beJJ20RB22

availablesoon

図 2: 圧縮操作の例

3

再帰構造の除去に基づく文圧縮

圧縮操作の種類，
前節の例において，原文の構文木から何らかのプロセ注目しているノードのラベル，親ノードのラベル，子ノードのラベル，スを経て，正しい圧縮文の構文木が得られるとすれば， 左側の兄弟ノードのラベルとそれが削除されたかどうか（削除のみ），再帰ノードから足ノードまでのパス上のノードのラベル（置換のみ），それは自然な文圧縮プロセスであると考えられる．この再帰ノードから足ノードまでのパス上のノードの子ノードのラベル（置換のみ），ような構文木を得るためには，図 1 の構文木において， 足ノードのラベル（置換のみ）
S1 に埋め込まれた S10 を取り出し，S1 を S10 で置き換えればよい．このような処理を行う操作を導入できれ
図 3: 学習に使用した素性
ば，“It is likely that” をまとめて削除することが可能となる．ここで注目すべきポイントは，S1 と S10 が同一の統語範疇であるということである．すなわち，ある 3.2 確率的文圧縮モデルノードを別の構文木で置き換えるとき，その範疇が同一本手法では，原文がある圧縮文に圧縮される確率を，であれば文法性が保たれる．これが本手法において再帰原文の構文木に圧縮操作を適用して圧縮文の構文木が構造に注目する理由である．
得られる確率と定義する．各圧縮操作が適用されるか否かは，置換操作に関しては他の操作の適用・非適用とは完全に独立であるとし，また，削除操作に関しては現在
3.1 再帰構造の除去
注目しているノードの兄弟ノードに対する操作の適用・
本節では，再帰構造の除去による文圧縮操作を導入す 非適用にのみ従属であると仮定する．これにより，圧縮る．初めに，再帰ノードを定義する．
文の構文木が得られる確率を，各圧縮操作の適用（非適定義 1 (再帰ノード) T を構文木，η を T 中のノード， 用）確率の積として求めることができる．
本手法では，どのような場合に圧縮操作を適用すればX を η のラベルとする．以下の条件を満たすような η ′よいかを，原文とその圧縮文の対からなる圧縮文コーが存在するとき，η を再帰ノードと呼ぶ．
パスから学習し，圧縮操作の適用確率を，最大エント• η ′ は η の子孫ノードである
ロピー法 [1] によって推定する．使用した素性を図 3 に示す．
• η ′ のラベルが X である
図 1 において，再帰ノードは，S1 ，VP4 ，VP15 の 3
3.3 スコアの計算つである．
再帰ノード η 以下を幅優先で探索し，最初に見つか前節のモデルをもとに，原文 l に対する各圧縮文候補る η ′ を足ノードと呼ぶ．図 1 において，S1 の足ノード
s のスコアを以下のように計算する．
は S10 ，VP4 の足ノードは VP15 である．
再帰ノードに対する圧縮操作を以下のように定義する．
Score(s) = length(s)α · log P (s|l)
置換 再帰ノード η 以下の部分木を，η に対する足ノード η ′ 以下の部分木で置き換える
この操作により，再帰構造を取り除いて文を圧縮できる．図 1 中の S1 に置換操作を適用して獲得される構文木を図 2 に示す．
一方，非再帰ノードに対しては，従来の手法と同様に，ノードを削除する操作を適用する．

このスコアは，確率モデルを我々のモデルに置き換えた点を除いて，Unno らの手法 [11] と同一である．圧縮文候補の生成確率に加えて，圧縮文の長さを考慮することによって，出力される圧縮文の平均文長を調節することができる．α はそのためのパラメータである．本手法
は，このスコアを最大にするような s を圧縮文として出力する．

S1

表 1: 被験者による評価の結果
圧縮率

文法性

意味

Knight

70.4%

4.29

4.09

提案手法

68.1%

4.45

4.04

NP2
NP3 COMMA VP5
4The SCAMP ...

,VP7
COMMA6

designed and ...

contains the ...

,図 4: 原文 (4) の構文木

4

評価実験

は，置換操作によって “Another slight downside is that”
を 1 つのまとまりとして削除し，コーパスの圧縮文と同提案手法の有効性を確認するために評価実験を行っ 様の圧縮文を生成している．それに対して，Knight らた．Knight らの手法 [7] との比較のため，実験データ の手法では原文をそのまま圧縮文としている．Knightとして，Knight らが Ziﬀ-Davis コーパスから作成した， らの手法でコーパスの圧縮文と同じ圧縮文を生成するに原文と圧縮文の対からなるコーパスを使用した．943 対 は，原文 (1) と圧縮文 (2) の例と同様，“Another slightを学習データとして使用し，32 対をテストデータとし downside”，“is”，及び “that” をそれぞれ単独で削除すた．テストデータは，Knight ら [7] の実験と同一であり， る必要があるが，このような削除が行われる確率は極め学習データとは異なる対から構成される．学習・文圧 て低いと考えられる．
縮の処理において構文木が必要であるため，Charniak
原文 (4) の構文木を図 4 に示す．この原文に対して，Parser[3] を使用し構文木を付与した．文長を制御する コーパスの圧縮文では “, designed and ... Intel proパラメータ α は，Knight らの手法の圧縮率と等しくな cess,” が削除されている．提案手法では，NP2 に置換るように定めた．その値は α = −0.50 である．
操作を適用することによって同様の箇所を 1 つのまとまりとして削除している．それに対して，Knight らの手法では，一方の “,” と “designed and ... Intel process”
4.2 被験者実験による評価を削除し，もう一方の “,” を残しており，その結果，非文法的な圧縮文が生成されている．
被験者実験により，提案手法と Knight らの手法を文法性と意味の保持の観点から評価した．英語母語話者である被験者 4 名に対し，原文と，それに対する Knight
4.4 複数の正解に基づく評価らの手法の圧縮文，及び提案手法の圧縮文を併せて提示した．被験者は，圧縮文が文法的にどれだけに正しい
文圧縮手法の評価は被験者実験によることが望ましか（文法性）と，原文の主要な意味をどれだけ保持して いが，その都度，被験者実験を行うのは大きなコストをいるか（意味保持度）の 2 つの観点で，1 から 5 の 5 段 要するため，何らかの方法で自動評価できることが望ま階で評価した．5 が最も良い評価である．圧縮文の順序 しい．本節では，文圧縮手法の自動評価法について議論
は，テストセットの文ごとにランダムに並び替えられて し，提案手法の自動評価について述べる．
いる．
これまでの文圧縮手法の自動評価では，正解圧縮文を表 1 に，2 種類の文圧縮手法それぞれの圧縮率，及び ただ 1 つだけ用意し，手法が生成する圧縮文との一致
被験者が評価した文法性と意味保持度を示す．提案手法 の度合により評価している [6, 9, 11]．しかし，一般には Knight らの手法と圧縮率，意味の保持に関してはほ は，原文に対して正しい圧縮文は必ずしも 1 つとは限ぼ同等でありながら，文法性に関して高い評価を受けて らない1 ．そこで我々は，原文に対して複数の圧縮文をいることから，提案手法がより高い文圧縮性能を備えて 用意し，文圧縮手法を評価した．
いることがわかった．
正解圧縮文は，3 人の作業者（英語母語話者）が作成した．テストデータの各文に対する圧縮文の上限を 10文とし，作成した圧縮文には，圧縮文の文法性，意味保4.3 再帰構造の除去の効果
持度，圧縮率などの観点から，作業者が総合的に判断した順位付けがなされている．
表 2 に提案手法，Knight らの手法，及びコーパス中正解圧縮文と完全一致した文の数を表 3 に示す．nの圧縮文の例を示す．2 つの原文 (3), (4) は，いずれもbest の列は，上位 n 位以内の正解圧縮文のいずれかにテストセットに含まれる文である．
圧縮された文の数を示す．コーパスの圧縮文でも，1 位
原文 (3) に対して，コーパスの圧縮文では “Another1 テキスト要約に関して同様の事柄が，石川らにより指摘されていslight downside is that” が削除されている．提案手法で4.1

実験の設定

る [5]．

表 2: 圧縮文の例
原文 (3)

Another slight downside is that envelopes must be fed manually.
Another slight downside is that envelopes must be fed manually.

Knight
提案手法
コーパス

Envelopes must be fed manually.
Envelopes must be fed manually.

原文 (4)The SCAMP module, designed and built by Unisys and based on an Intel process,Knightcontains the entire 48-bit A-Series processor.
The SCAMP module, contains the entire 48-bit A-Series processor.

提案手法
コーパス

The SCAMP module contains the entire 48-bit A-Series processor.
The SCAMP module contains the entire 48-bit A-Series processor.

参考文献

表 3: 複数の正解に基づく評価の結果
圧縮率

1-best3-best10-bestKnight

70.4%

336

提案手法

68.1%
53.3%

611714822

コーパス[1] A.L. Berger, V.J. Della Pietra, and S.A. Della Pietra,“A Maximum Entropy Approach to Natural Language
Processing, ” Computational Linguistics, vol. 22, num.
1, pp. 39–71, 1996.
[2] T. Briscoe and J. Carroll, “Robust Accurate Statistical
Annotation of General Text,” Proc. 3rd LREC, pp.
1499–1504 2002.

のみを正解とした場合，合致するものは 11 文に過ぎず， [3] E. Charniak, “A Maximum-Entropy-Inspired Parser, ”
Proc. 6th ANLP, pp. 132–139, 2000.
全体の 34%でしかない．一方，10 位までのすべての正解圧縮文を用いた場合では，22 文と 69%を占める．こ [4] J. Clarke, and M. Lapata, “Models for Sentence Compression: A Comparison across Domains, Training Reのことは，正解の圧縮文が複数存在していることを意味
quirements and Evaluation Measures, ” Proc. 44th
しており，複数の正解を用いての評価は有用であると考ACL, pp. 377–384, 2006.
えられる．
提案手法と Knight らの手法について見てみると，提 [5] 石川開, 安藤真一, 奥村明俊, “テキスト要約の複数の正解に基づいた評価, ” 自然言語処理，vol. 9，no. 4, pp.
案手法のほうが完全一致する文の割合が多い．このこと
33–53, 2002.
から，提案手法がより正解圧縮文に近い圧縮を行ってい[6] H. Jing, “Sentence Reduction for Automatic Text Sumると考えられる．
marization, ” Proc. 6th ANLP, pp. 310–315, 2000.

5

おわりに

[7] K. Knight, and D. Marcu, “Statistics-Based Summarization – Step One: Sentence Compression, ” Proc.
17th AAAI, pp. 703–710, 2000.

本稿では，構文木の再帰構造を除去することによって [8] I. Mani, Automatic Summarization, John Benjamins,
2001.
文圧縮する手法を提案した．本手法では，構成素の削除のみを行う既存の手法ではうまく処理できなかった付 [9] S. Riezler, T. H. King, R. Crouch, and A. Zaenen,加詞，等位構造，埋め込み文などを，再帰構造の除去に“Statistical Sentence Condensation using Ambiguity
Packing and Stochastic Disambiguation Methods for
よって，文法的に自然な形で削除できる．
Lexical-Functional Grammar, ” Proc. HLT-NAACL被験者による評価実験から，提案手法が，既存の手法
2003, pp. 118–125, 2003.と比べて，文法的に正しく圧縮できることを確認した．
また，複数の正解に基づく評価実験により，提案手法が [10] J. Turner, and E. Charniak, “Supervised and Unsupervised Learning for Sentence Compression, ” Proc.
既存の手法と比べ，人手の圧縮に近い圧縮文を生成でき
43rd ACL, pp. 290–297, 2005.
ることを示した．
今後は，再帰構造除去以外の構文木の構造的変更に [11] Y. Unno, T. Ninomiya, Y. Miyao, and J. Tsujii,“Trimming CFG Parse Trees for Sentence Compresついても検討し，より柔軟な文圧縮手法を提案したい．
sion Using Machine Learning Approaches, ” Proc. 44th
また，複数の正解に基づく評価の妥当性を，より詳細にACL, pp. 850–857, 2006.
検証する予定である．