Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

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)
自然言語処理を用いたテキスト自動要約の手法

riverwell
機械学習が好きな犬
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした