自動要約アルゴリズムLexRankでドナルド・トランプ氏の演説を3行に要約してみる

Nextremer Advent Calender 2016の15日目の記事です．

2016年ももうすぐ終わりですが，今年も様々なニュースがありました．
ドナルド・トランプ氏の大統領選勝利は，その中でも特にインパクトの強い出来事だったのではないでしょうか？

テレビではよく見ますが，きちんとスピーチを聞いたことはなかったので，演説文を読んでみようと思います．
ただし，英語は苦手なので，要約アルゴリズムで3行くらいに縮めます．

はじめに

要約の仕方は大きくは2つに分けられます．

• 抽出的要約
  • 重要文抽出
    • テキストから重要な文を抜き出す
  • 文短縮
    • 各文を短縮する
• 生成的要約
  • 抽出要約以外の要約

生成的要約は非常に難易度が高く，現在メインで研究がされているものはほとんどが抽出的予約です．
今回実装するLexRankも抽出的要約に属し，文章中の重要文抽出を行います．

LexRankとは？

LexRankはPageRankに着想を得た要約アルゴリズムです．
PageRankはGoogle創業者のL.PageとS.Brinが考案したWebページの重要度を決定するためのアルゴリズムです．
インターネット上のリンク構造を以下のようなグラフとして捉え，ページの重要度を決定していました．

ノード：Webページ
エッジ：リンク
ノードの重要度：
	1. 多くのページからリンクされているページは重要なページ
	2. 重要なページからリンクされているページは重要なページ

LexRankもPageRankと同様に文章をグラフとして捉えます．

ノード：文
エッジ：2文間の類似度(1 | 0)
ノードの重要度：
	1. 多くの文と類似する文は重要な文
	2. 重要な文と類似する文は重要な文

ここでいう類似度は簡単にいえば2文がどれだけ共通の単語を持つか，です．

LexRankはグラフ構造のみで重要度を評価しますが，考案された2004年当時，DUC2004にて最も良い精度を誇っていました．
意味解析せずに高精度に要約できるというのは，とても面白く感じます．

LexRankの計算式は以下の通りです．

Input: n 個の文からなる配列 S, コサイン類似度の閾値 t
Output: 各文のLexRankスコアを格納した配列L

Array CosineMatrix[n][n];
Array Degree[n];
Array L[n];

for i <- 1 to n do
	for j <- 1 to n do
		CosineMatrix[i][j] = idf-modified-cosine(S[i], S[j]);
		if CosineMatrix[i][j] > t then
			CosineMatrix[i][j] = 1;
			Degree[i]++;
		end
		else
			CosineMatrix[i][j] = 0;
		end
	end
end
for i <- 1 to n do
	for j<- 1 to n do
		CosineMatrix[i][j] = CosineMatrix[i][j] / Degree[i]
	end
end

L = PowerMethod(CosineMatrix, n, ε);

return L

(引用：「LexRank: Graph-based Lexical Centrality as Salience in Text Summarization」Alogorithm 3)

idf-modified-cosine は2文間の類似度計算．
PowerMethod はPageRankの計算．
です．

では，実際にこのアルゴリズムをPythonで実装していきます．

実装

import math
import numpy

def lex_rank(sentences, n, t):
	"""
	LexRankで文章を要約する．
	@param	sentences: list
		文章([[w1,w2,w3],[w1,w3,w4,w5],..]のような文リスト)
	@param	n: int
		文章に含まれる文の数
	@param	t: float
		コサイン類似度の閾値(default 0.1)
	@return	: list
		LexRank
	"""
    cosine_matrix = numpy.zeros((n, n))
    degrees = numpy.zeros((n,))
    l = []
	
	 # 1. 隣接行列の作成
    for i in range(n):
        for j in range(n):
            cosine_matrix[i][j] = idf_modified_cosine(sentences, sentences[i], sentences[j])
            if cosine_matrix[i][j] > t:
                cosine_matrix[i][j] = 1
                degrees[i] += 1
            else:
                cosine_matrix[i][j] = 0

    # 2.LexRank計算
    for i in range(n):
        for j in range(n):
            cosine_matrix[i][j] = cosine_matrix[i][j] / degrees[i]
            
    ratings = power_method(cosine_matrix, n)
    
    return zip(sentences, ratings)

このプログラムは機能別に

1. 隣接行列の作成
2. LexRank計算
   の2ブロックに分けられます．

ここでは各ブロックごとに解説していきます．

1. 隣接行列の作成

隣接行列はグラフ表現のための行列です．
ノード間にエッジが存在すれば1，存在しなければ0を代入することでグラフ表現します．
LexRankでは2文間の類似度が閾値t以上であればエッジで結びます．

類似度の実装は以下の通りです．

def idf_modified_cosine(sentences, sentence1, sentence2):
	"""
	2文間のコサイン類似度を計算
	@param	sentence1: list
		文1([w1,w2,w3]のような単語リスト)
	@param	sentence2: list
		文2([w1,w2,w3]のような単語リスト)
	@param	sentences: list
		文章([[w1,w2,w3],[w1,w3,w4,w5],..]のような単語リスト)
	@return : float
		コサイン類似度
	"""
    tf1 = compute_tf(sentence1)
    tf2 = compute_tf(sentence2)
    idf_metrics = compute_idf(sentences)
    return cosine_similarity(sentence1, sentence2, tf1, tf2, idf_metrics)

TFは文中の単語の出現頻度．(多いほど重要)
IDFは文書全体で単語の出現頻度．(少ないほど重要)
コサイン類似度はベクトル間の類似度を余弦で求めるものです．

これらに関しては知ってる方も多いと思いますので，簡単に実装だけ載せておきます．

from collection import Counter


def compute_tf(sentence):
	"""
	TFを計算
	@param	sentence: list
		文([w1,w2,w3]のような単語リスト)
	@return : list
		TFリスト
	"""
    tf_values = Counter(sentence)
    tf_metrics = {}
    
    max_tf = find_tf_max(tf_values)
    
    for term, tf in tf_values.items():
        tf_metrics[term] = tf / max_tf

    return tf_metrics


def find_tf_max(terms):
	"""
	単語の最大出現頻度を探索
	@param	terms: list
		単語の出現頻度
	@return : int
		単語の最大出現頻度
	"""
    return max(terms.values()) if terms else 1


def compute_idf(sentences):
	"""
	文章中の単語のIDF値を計算
	@param sentences: list
		文章([[w1,w2,w3],[w1,w3,w4,w5],..]のような単語リスト)
	@return: list
		IDFリスト
	"""
    idf_metrics = {}
    sentences_count = len(sentences)

    for sentence in sentences:
        for term in sentence:
            if term not in idf_metrics:
                n_j = sum(1 for s in sentences if term in s)
                idf_metrics[term] = math.log(sentences_count / (1 + n_j))

    return idf_metrics
    
    
def cosine_similarity(sentence1, sentence2, tf1, tf2, idf_metrics):
	"""
	コサイン類似度を計算
	@param	sentence1: list
		文1([w1,w2,w3]のような単語リスト)
	@param	sentence2: list
		文2([w1,w2,w3]のような単語リスト)
	@param	tf1: list
		文1のTFリスト
	@param	tf2: list
		文2のTFリスト
	@param	idf_metrics: list
		文章のIDFリスト
	@return : float
		コサイン類似度
	"""
    unique_words1 = set(sentence1)
    unique_words2 = set(sentence2)
    common_words = unique_words1 & unique_words2

    numerator = sum((tf1[t] * tf2[t] * idf_metrics[t] ** 2) for t in common_words)
    denominator1 = sum((tf1[t] * idf_metrics[t]) ** 2 for t in unique_words1)
    denominator2 = sum((tf2[t] * idf_metrics[t]) ** 2 for t in unique_words2)

    if denominator1 > 0 and denominator2 > 0:
        return numerator / (math.sqrt(denominator1) * math.sqrt(denominator2))
    else:
        return 0.0    

最後に，コサイン類似度がt以上であれば1を代入し，隣接行列を完成させます．

次はここで作成した行列を元にLexRankを求めていきます．

2.LexRank計算

ここからは，1.で求めた隣接行列を元にLexRankを計算します．
まずは隣接行列の各要素をdegree(ノードの次数)で割り，確率行列に変換します．

そして，この確率行列を元にマルコフ定常分布を求めていきます．
マルコフ連鎖は非周期的で必ず収束することが保証されているため，べき乗法で転置行列を乗算し，ε以下になるまで反復処理を繰り返します．
ここで最終的に計算された固有ベクトルがLexRankとなります．

実装は以下の通りです．

def power_method(cosine_matrix, n, e):
	"""
	べき乗法を行なう
	@param	scosine_matrix: list
		確率行列
	@param	n: int
		文章中の文の数
	@param	e: float
		許容誤差ε
	@return: list
		LexRank
	"""
    transposed_matrix = cosine_matrix.T
    sentences_count = n
    
    p_vector = numpy.array([1.0 / sentences_count] * sentences_count)
    
    lambda_val = 1.0
    
    while lambda_val > e:
        next_p = numpy.dot(transposed_matrix, p_vector)
        lambda_val = numpy.linalg.norm(numpy.subtract(next_p, p_vector))
        p_vector = next_p
    
    return p_vector

これで，LexRankによる重要度計算が終了です．
対応するratingsの値が大きいほど重要度が高い文となります．

要約結果

では，実際に要約してみます．
要約するのはトランプ氏の大統領選勝利時のスピーチです．

# lex_rank(document)
Great people.
Great brothers, sisters, great, unbelievable parents.
We're going to get to work immediately for the American people, and we're going to be doing a job that hopefully you will be so proud of your president.

# 素晴らしい人々。
# 偉大な、信じられないほどの親、偉大な兄弟、姉妹。
# 私たちはアメリカの人々のためにすぐに働くつもりです。私たちはあなたが大統領をとても誇りに思うことを願って仕事をしていきます。

うん，，，まぁ，大統領頑張るぞ！ という意気込みは感じられるんじゃないでしょうか？

終わりに

本記事では自動要約アルゴリズムを実装し，トランプ氏の演説を要約しました．
グラフで文章を捉えられるので，LexRankはテキスト分析にも色々使えそうですね．
明日は引き続き要約+翻訳で何か書こうと思います．

参考文献

LexRank: Graph-based Lexical Centrality as Salience in Text Summarization
miso-belica/sumy
Document Summarization PART-2: LEXRank (Modified Pagerank) based Document Summarization
グラフ上のランダムウォークとGoogle のページランク
自動要約(wikipedia)
自然言語処理を用いたテキスト自動要約の手法