@yamano357
2014.08.30 Sat.
内容は個人の見解であり、所属する組織・団体の公式見解ではありません
2009年に作成した資料をベースにしているので内容が古いですが、ご了承ください（残りはいろいろなところから継ぎ足し）
言語処理研究から離れて数年経っているので最新の話題には触れておりません
資料はテキスト自動要約の概要をざっくりと通したので、少し踏み込んだ話は適宜口頭で補足します
R言語の勉強会ですが、Rの話はほとんどでてきません
図を描くセンスが皆無なので文字が多くなっており、この資料を要約するシステムが欲しい
先人の方々の業績に感謝（『参考』に明記した資料が非常に役に立ちました）
自然言語処理の応用事例のひとつ（他には機械翻訳、質問応答、日本語入力など）
なぜ必要か？
=> 全部に目を通すなんて時間的に無理
=> 必要なところだけ欲しい
=> 手早くかつ安く（むしろタダで）
「なんかテキストを入力すると、人が作成したような感じでまとめてくれるんだよね？」
=> 「人の要約と同じような出力を要求するのは、現在の研究状況で無理がある」
「小説とか入力したら、あらすじになって返ってくるんだよね？」
=> 「生成型要約とかハードル高い。抽出型要約でさえも研究レベル。ましてや小説なんかは人でも難しい」
「書類が多すぎて全部読んでられないから、要約システム作ってなんとかまとめられない？」
=> 「秘書を雇って頼んだ方が断然に安い」
ひとり歩きしたキーワードから夢想する内容と関係者が抱く現実との埋まらない乖離
いやはや、どこかで聞いたような話ですね
それなんて、でーたなんたら（略）
“Summly"や"Wavii"といったニュース要約アプリが大企業に買収されるなど、社会的ニーズは高まっている
しかしながら、できることとできないことがある
「データ分析すればなんか凄い発見ができるんだろ」と言われたことはないですか
「機械学習すればなんか凄いことができるんじゃないか」と考えたことはないですか
「自然言語処理を応用すればなんか凄いシステムが作れるんじゃないか」と思ったことはないですか
人の方が凄いです
知らないとバラ色の夢ばかり広がるので、これくらいなら個人でも始められるという現実的なテキスト自動要約の話が今日の資料です
（「西川さんの資料」を一読していれば充分な内容ですが）
大昔： 専門的な文献（学術論文など）を対象にした文献抄録
1958 語の出現頻度を手がかりに重要文抽出した研究(H.P.Luhn)
1969 素性の重み付け線形総和をスコアとした研究(H.P.Edmundson)
199X Web文書の増大により新聞記事以外の多様な入力文書へ
1998 TIPSTER Text Summarization Evaluation Conference (SUMMAC)が開始（テキスト自動要約に関する評価型プロジェクトとしては最初）
2001 TIDESプロジェクトの一貫として、Document Understanding Conference (DUC)が開始
2001 NIIが主導するNTCIRのタスクのひとつとして、Text Summarization Challenge (TSC)が日本で開始
2005 質問に焦点を当てた要約生成がDUCのメインタスクとなる
2008 DUCがTREC(Text Retrieval Conference)のQAトラックと統合され、Text Analysis Conference (TAC)のトラックのひとつとなる
– TACではQuestion AnsweringやRecognizing Textual Entailmentなど、要約と関連性が高い新しい研究のトラックも行われている
2000年初期から機械学習ベースで重要文抽出する研究が増加
2000年中期以降から要約生成を数理最適化で表現する試み
指示的要約(indicative)： 原文を参照する前に用いる要約
– 原文の重要な情報を全て含んでいる必要はなく、人にとって読みやすい文章が望ましい（難易度：低-中）
– 検索システムのスニペットやニュースサイトのトピックスなど
報知的要約(informative)： 原文の代わりとして短くまとめたものを用いる要約
– 原文の重要な情報を全て含み、なおかつ人間が読みやすい（可読性が高い）文章が望ましい（難易度：高）
– ニュース番組の字幕放送や新幹線の電光掲示板で使用されるニュース記事など
自由作成要約: 原文をもとに制約を与えずに、自由に作成した要約
自由作成要約を分析した結果、人は単に重要な文を抽出したり、単語を削ったりするだけでなく、それらを編集する操作を行って要約を生成
これらの編集操作を用いる以外に、原文にない文を自ら作り出す（「生成型要約」と言える。難易度：高）
専門家の抄録作成者の場合は、「自ら文を作り出してはいけない」という制約があり、「切り貼り操作」で要約生成（「抽出型要約」と言える。難易度：低-中）
– 「理解-変形-生成」のシステム化は困難（仕組みが明確でない）
計算機上で実現可能なテキスト自動要約の方法として、下記のステップをシステム化（「切り貼り操作」による「抽出型要約」の生成）
* 「重要文抽出」と「文短縮」と「並べ替え」のみを説明
難易度が高い「報知的要約」、「生成型要約」については深く触れません
テキスト中から重要な文を抜き出し、テキスト中での出現順に並べて出力する要約手法
重要文抽出では、算出する重要度の計算方法により、出力結果が大きく変化
(1) テキスト中の単語の重要度
– 出現頻度(Term Frequency, TF)を単語重要度と考えるTF法や、これに合わせて単語の出現するテキスト数(Document Frequency, DF)の逆数を考慮したTF*IDF法が広く使われる
(2) テキスト中あるいは段落中での文の位置情報
– テキストの位置に重要な情報を含む傾向がある。最初の段落だけを要約として抜き出す手法（リード手法）は新聞記事で優れたメソッド
(3) テキストのタイトルなどの情報
– タイトルや見出し自体が本文の簡潔な要約になっているという仮定。タイトルや見出しに現れる内容語を含む文が重要であると考え、タイトルや見出し中の単語を要約文に用いる
(4) テキスト中の手がかり表現
– 重要な文を直接明示する手かがり表現（Cue Phrase）を利用。論文では、「本研究（で）は」、「まとめると」、「本稿では-述べる」など。逆に「例えば」や「つまり」などの例示の接続詞で始まる文は、理解の補助として重要度が低いという負の手がかり表現とも考えられる
(5) テキスト中の文あるいは単語間の繋がり – テキスト中の他の多くの文と強い関連がある文は、テキスト中で中心的な役割。この関連性には、反復表現、同義性、シソーラスでの意味的関連（例えば、「川」と「橋」など）がある
(6) 文間の関係を解析したテキスト構造
– テキスト中の接続詞などを基にテキスト構造を解析し、得られた情報を利用
* 上記は後述する「グラフベースの要約生成」にも利用される基準
\[ W(s) = \alpha C(s) + \beta K(s) + \gamma L(s) + \delta T(s) \]
W(s): 文sの総合的な重み
C(s): 手がかり語による文sの重み（(4) に相当）
K(s): キーワードによる文sの重み（(1) に相当）
L(s): 位置情報による文sの重み（(2) に相当）
T(s): タイトルによる文sの重み（(3) に相当）
重要文抽出では出力結果が一貫性を欠くケースが存在
代名詞が指し示す先行詞が消失してしまう場合
(1) 『エイブラハム・リンカーンは1809年2月12日にトーマス・リンカーンおよびナンシー・ハンクス夫妻の息子として生まれた』
(2) 『彼の誕生日はチャールズ・ダーウィンと同じ日である』
連文の欠落によって話題が飛躍する場合
– 「10個の文テキストから半分程度の要約（要約率50%）を出力」
=> 重要文抽出では重要と判断される約5文を抜き出す
後半部分のみから抜き出されると、内容を正しく把握しにくくなる
非常に短く圧縮しようとすると、文が歯抜けになりすぎて内容の捉えにくくなる
一文ごとになるべく情報を減らさずに、かつ文法性を保ったまま重要でない個所を削って（あるいは重要な部分を抽出し）、テキストを短く表現
– 体言止めや抽象化して言い換える（生成型要約に近い）
— 「7月中に解散します」 => 「7月中に解散」
– 「お腹が空いたので、パンと牛乳を買った」 => 「空腹だったので、食料を買った」
構文解析木から重要な個所を抽出（あるいは不要な個所の枝刈り）する手法
– 重要性の判定には重要文抽出で利用した基準や枝刈りにより構文構造が破壊される要素を重要と判断
– 英語では文中の要素に関する重要度の指標として以下を用いた研究もある
「固有名詞 > 普通名詞」 「名詞 > 形容詞 > 冠詞」
「否定は重要」 「主節 > 従属節」
構文解析木の枝刈りの例
– 西川さんの資料が秀逸すぎて参照
原文と人間が作成した自由作成要約（正解）のパラレルコーパスから、人間の要約生成過程のモデルを学習して要約
原文の情報を維持したまま文法的に正しく要約する統計的な文短縮手法として、Noisy Channel Modelを用いた研究（クエリ依存要約に拡張した研究もある）
– 自動要約を「冗長な原文」と「簡潔な要約」の翻訳と見なし、「簡潔な要約」が雑音のある通信路を経由して「原」文書の形で改竄された「冗長な原文」が得られたとする。この「冗長な原文」から「簡潔な要約」へ復号するモデルの構築が目的
重要文抽出は「重要」な文を独立に抜き出しているため、抽出された結果に似た文ばかりが集まる可能性がある
– 特に複数テキスト要約における重要文抽出では、複数入力の内容を適切に網羅した要約が望ましい
冗長な情報を除去することで他の有用な情報を追加し、要約中の情報量を増やすことが可能
単純な冗長性判定は、文間の類似度を計算し、ある閾値以上の文同士は冗長と判断
– クラスタリングして各クラスタから代表の一文のみを抽出
\[ \newcommand{\argmax}{\mathop{\rm arg~max}\limits} MMR = \argmax_{D_{i} \in T} [\lambda Sim_{1}(D_{i}, Q) - (1- \lambda) max_{D_{j} \in S} Sim_{2}(D_{i}, D_{j}))] \]
Q：検索クエリ S：すでに要約として選ばれている文集合
T：まだ要約として選ばれていない文集合
「他の文章と関連性が高い文は重要」という仮定。「テキスト中の文あるいは単語間の繋がり」と「文間の関係を解析したテキスト構造」の重要度計算基準に該当
グラフベースの重要文抽出プロセス
単語や句などをノードの単位にスコアを計算し、文に含まれるそれらの合計を文の重要度にして抽出したり、単語や句などを単位に抽出することで文短縮したりも可能
重要文抽出を「重要・非重要」の二値分類に定式化
– Naive Bayes分類器を構築した研究が最初
– 決定木(C5.0?)によるシステムがDUCにおいて高い評価結果（うろおぼえ）
教師あり・教師なし学習、半教師あり学習、転移学習、強化学習などのさまざまなアルゴリズムを使った研究が多種存在
– しかしながら、機械翻訳に比べると学習データ不足が否めない
— 機械翻訳のための対訳コーパスならば古典的なHansardsコーパスでも約130万文ペア
— 例えばDUC2004の場合は約4000文の要約文
=> 要約文の構造を活かすような大域的学習手法が効果を充分に発揮できない
（機械学習ではないが、参照要約中の高頻度単語に着目して文をスコアリングしたSumBasicは高い評価値を得ている）
\[ \newcommand{\argmax}{\mathop{\rm arg~max}\limits} \hat{S} = \argmax_{S \in D} \{ f(S):length(S) \leq K \} \]
D: 原テキスト集合 S: テキスト集合の要素となる文
f(S): Sの重要度を返す関数 length(S): Sの長さ
K: 要約サイズ
要約サイズK以下で目的関数fを最大化する文集合\( \hat{S} \) を求める
=> あるサイズのナップサックに価値を最大化する品物を詰めるにはどう選べばいいか（= ナップサック問題として求解可能）
文の並び替えを巡回セールスマン問題として扱った研究もある
\[ max. \sum_{j} b_{j} z_{j} \hspace{1.0cm} s.t \sum_{i} c_{i} x_{i} \leq K \hspace{1.0cm} \forall_{j}, \sum_{i} a_{ij} x_{i} \geq z_{j} \hspace{1.0cm} \forall_{i}, x_{i} \in \{0, 1\} \hspace{0.5cm} \forall_{j}, z_{j} \in \{0, 1\} \]
aij: 文iが単語jを含むか bj: 単語jの重要度
ci: 文iの長さ xi: 文iが選択されたか
zj: 単語jが被覆されたか K: 最大要約長
– 「被覆」しているかどうかを「含意関係」で判定することも
テキスト自動要約を数理モデルで定式化する話については、 NLP2014のチュートリアルにおいて『文書要約への数理的アプローチ』という題目で、東工大の高村先生が詳しくまとめております
被験者
– オンライン: 人間の被験者がシステムを評価
– オフライン: 人間の被験者なしでシステムを評価
手法
– 内的な評価: 生成された要約自体を評価
– 外的な評価: 何かしらのタスクに生成された要約を用いて、効果的だったかを評価（検索エンジンの結果に提示して、人的コストが軽減されたか判定。ほとんどやられていない）
側面
– 内容: 原文書の内容を反映した要約になっているかを評価
– 可読性: 読みやすい要約になっているかを評価
* 内容と可読性のオフラインで内的な評価について主に説明
F-measure(F値): Precision(精度)とRecall(再現率)の調和平均で、情報検索システムの評価に用いられる評価尺度。重要文抽出のシステムを評価可能
\[ F-measure = \frac{2 \times Precision \times Recall}{Precision + Recall}, \hspace{1.0em} Precision = \frac{|M \cap H|}{|M|}, \hspace{1.0em} Recall = \frac{|M \cap H|}{|H|} \]
M: システムによる要約文集合 H: 参照要約文集合
M <- c(1, 2, 3, 4, 7); H <- c(1, 2, 5, 7)
P <- length(intersect(M, H)) / length(M)
R <- length(intersect(M, H)) / length(H)
F <- (2 * P * R) / (P + R)
# Confusion Matrix
confusion.mat <- table(
c(1, 1, 1, 1, 0, 0, 1), c(1, 1, 0, 0, 1, 0, 1)
)
R.cf <- confusion.mat["1", "1"] / sum(confusion.mat["1", ])
P.cf <- confusion.mat["1", "1"] / sum(confusion.mat[, "1"])
F.cf <- (2 * P.cf * R.cf) / (P.cf + R.cf)
identical(F, F.cf)
[1] TRUE
ROUGE(Recall-Oriented Understudy for Gisting Evaluation): システムが作成した要約と人間による参照要約（正解）との類似度を算出
N-gram頻度を用いるROUGE-Nは下記の通り
\[ ROUGE-N = \frac{\sum_{S \in RefSummaries} \sum_{gram_{n} \in S Count_{match}(gram_{n})}}{\sum_{S \in RefSummaries} \sum_{gram_{n} \in S Count(gram_{n})}} \]
最長共通列(Longest Common Subsequence)一致を用いるROUGE-Lや、重み付き部分文字列最長一致（部分的に一致する場合よりも連続した一致により高い評価を与える）を用いるROUGE-Wや、Skip-bigramを用いるROUGE-Sなども
– 例
DUC2001からDUC2003のデータで検証した結果、「ROUGE-2, ROUGE-L. ROUGE-W, ROUGE-S」が良い結果（ROUGE-1, ROUGE-L, ROUGE-W, ROUGE-SU4は非常に短い要約の評価で優れているとも）
Pyramid: Summarization Content Units(SCUs)を単位したピラミッドモデルによる評価法
– 複数の人手による正解要約からSCUsに重みづけ
– SCUsは各正解要約の単語列から構成されたフレーズ以下の要素
– SCUs内の単語を含む文の数（複数カウントせず）がSCUsの重み。重みが高いSCUsは少なく、低いSCUsは多くなる
Basic Elements: 最小の意味的単位として「Basic Elements(BEs)」を定義し、BEを単位にした要約の内容に関する内的評価法。BEの抽出には構文解析などから得られる単語と関係を利用
– 日本では構文片（係り受け解析後の「係り」と「受け」をセットにした言語処理単位）という要素を提案した研究も
テキストの可読性尺度としてはFOG indexやKincaid indexなどがあるが、単語や文字の長さを軸に評価しているため、要約評価に向いていない
Quariry Questionというチェック項目を用いたり、DUC2005では以下の5つを人手で5段階評価(A(very good)- E(Very poor))
DUCにより作成された自動要約のロードマップでは下記のように進むことが提唱
– 簡単なジャンルから複雑なジャンルへ
– 内的な評価から外的な評価へ
– シンプルなタスクから要求型タスクへ
抽出からアブストラクトへ
単一テキストから複数テキストへ
英語から多言語へ
一般的な要約から焦点を当てた要約へ
言語処理
文脈・談話解析
– 共参照解析
統計処理
実装
テキストからどういう素性を抽出するか
知識ベース：論理形式(logical forms)やオントロジーなどを用いた意味表現を利用した手法
– 深い意味レベルの解析による高精度なシステムが期待できる
– 特定領域で特化される傾向による頑健性・汎用性を欠く
特徴ベース：原文の位置情報や特徴的なターム、手がかり句などの表層的な特徴を利用した手法
– 解析レベルが浅く精度は低めであり補正などの処理が必要
– 手軽にシステム作成でき、様々な場面で活用できる
* 体系が似た欧米の言語の汎用解析器は存在するものの日本語までカバーしたものはない
グラフベースの単一テキスト要約システムを構築
Shinyでデモを作ろうとしたら、日本語処理とか常時稼動環境が形態素解析器が使えなくて挫折
WikipediaのデータであらかじめLDAのモデルを作成して、トピック確率から文書グラフを作成しようとしたけれど、時間が足りませんでした
誰にでも手軽にできるように、今回はパッケージを多用しました
R言語ではないけれど、ちょっと調べたらこういうのが
kSetCompressionRatio <- 0.3
kSetLoadLibName <- c("stringr" ,"SnowballC", "tm", "proxy", "adagio")
is.road.lib <- suppressPackageStartupMessages(
sapply(kSetLoadLibName, library, character.only = TRUE, logical.return = TRUE)
)
all(is.road.lib)
[1] TRUE
## 1. input text
input.text <- unlist(strsplit(x = "input text", split = "\n"))
input.text <- input.text[as.integer(which(sapply(input.text, stringr::str_length) > 0))]
input.sen.len <- stringr::str_length(string = input.text)
# Stemming
input.text <- stringr::str_trim(
string = SnowballC::wordStem(
words = input.text,
language = "en"
),
side = "both"
)
## 2. crete term-doc matrix
imput.tdm <- tm::TermDocumentMatrix(
x = tm::Corpus(x = tm::VectorSource(input.text)),
control = list(
removePunctuation = TRUE,
removeNumbers = TRUE,
tolower = TRUE
)
)
## 3. create sim matrix
sim.mat <- as.matrix(proxy::dist(x = as.matrix(t(imput.tdm)), method = "cosine"))
## 4. HITS Algorithm
auth <- eigen(t(sim.mat) %*% sim.mat)$vectors[, 1]
auth <- auth / sum(auth)
hub <- eigen(sim.mat %*% t(sim.mat))$vectors[, 1]
hub <- hub / sum(hub)
## 5. Knapsack
result.sen <- adagio::knapsack(
p = (auth + hub),
w = input.sen.len,
cap = as.integer(sum(input.sen.len) * kSetCompressionRatio)
)$indices
# the number of lines
length(input.text)
[1] 9
length(result.sen)
[1] 4
# output line number of summarization
result.sen
[1] 1 2 5 8
# compression ratio
sum(stringr::str_length(input.text[result.sen]))/ sum(stringr::str_length(input.text))
[1] 0.2744
input.text[result.sen]
[1] "5 Object-oriented program"
[2] "Object-oriented programming is a style of programming that has become popular in recent years. Much of the popularity comes from the fact that it makes it easier to write and maintain complicated systems. It does this through several different mechanisms."
[3] "Another feature of most object-oriented languages is the concept of inheritance. In most programming problems there are usually many objects that are related to one another. The programming is considerably simplified if some components can be reused."
[4] "The greatest use of object oriented programming in R is through print methods, summary methods and plot methods. These methods allow us to have one generic function call, plot say, that dispatches on the type of its argument and calls a plotting function that is specific to the data supplied."
テキスト自動要約システムに関する研究を、重要文抽出をメインに説明
文にスコアリングする関数を定義して、「いい感じ」に文を選択すれば、重要文抽出なら手軽に可能
文短縮とか並び替えとかは、深く立ち入らないのが懸命
システムの評価は参照要約がないと難しいので人手作成を頑張りましょう
これであなたもテキスト自動要約システムが構築できます
テキスト自動要約システムをこれから作ろうと思っている方へ
既存のツールや言語資源を用いてテキストから言語素性を抽出して、グラフベースでスコアリングしたり、最適化問題として解いたりして、始めてみるのがオススメです
ご清聴、ありがとうございました
次回は『自動要約のための言語処理』という内容をまとめようか、とか思ったり思わなかったり
“テキスト自動要約”: 奥村学, 難波英嗣
http://www.amazon.co.jp/dp/4274200426
“自動要約”: Inderjeet Mani, 奥村学, 植田禎子, 難波英嗣
http://www.amazon.co.jp/dp/4320120736/
“Automatic Summarization”: Ani Nenkova, Kathleen McKeown
http://www.nowpublishers.com/articles/foundations-and-trends-in-information-retrieval/INR-015
“文書要約への数理的アプローチ”: 高村大也
NLP2014チュートリアル資料（『NLP2014チュートリアル資料』は著作権の関係で、言語処理学会からの後日入手は不可。先生に直接問い合わせると）
“文章要約入門”:
http://www.slideshare.net/hitoshin/introduction-to-automatic-summarization
“自動要約技術の研究動向”:
http://www.slideshare.net/hitoshin/automatic-summarization
言語情報処理ポータル:
http://www.jaist.ac.jp/project/NLP_Portal/
自然言語処理を学ぶ推薦書籍:
http://cl.sd.tmu.ac.jp/prospective/readings
言語処理100本ノック:
http://www.cl.ecei.tohoku.ac.jp/index.php?NLP%20100%20Drill%20Exercises
“Foundations of Statistical Natural Language Processing”
http://www.amazon.co.jp/dp/0262133601/
“言語と計算 (4) 確率的言語モデル”
http://www.amazon.co.jp/dp/4130654047/
自然言語処理シリーズ:
http://www.coronasha.co.jp/np/result.html?ser_id=98
高速文字列解析の世界:
http://www.amazon.co.jp/dp/4000069748/
東京工業大学 奥村・高村研究室:
http://lr-www.pi.titech.ac.jp/wp/
お茶の水大学 小林研究室:
http://www.koba.is.ocha.ac.jp/wordpress/
横浜国立大学 森研究室:
http://www.forest.eis.ynu.ac.jp/~mori/