ramenjunitiメモ

自分なりに調べたものをまとめたり、文章を書く練習したり

JuliaでLexRankを実装して日本語の文書を要約してみた話

Julia 自然言語処理

どうもramenjunitiです。

完全にブログのことを忘れて、しばらく放置してました笑😱

せっかくブログを作ったので、これから頑張ってひっそり更新していきます！😤

このブログは自分なりに調べたことの整理と文章を書く練習を目的としているので、色々おかしな点はあるかと思いますがご容赦下さい。

では本題に入っていきましょう。

今回の内容は文書要約のアルゴリズムの一つであるLexRankをJuliaという言語で実装したというものです。（タイトルそのままですね笑）

はじめに

文書要約がどのようなものか軽く触れてみましょう。

文書要約がどのようなものなのかという話は、こちらの二つの記事が非常によくまとまっていて参考になりました。 qiita.com hazm.at

要約を作成する手法は抽出型と抽象型の二つあります。

抽出型

要約の対象となる文書中から重要度の高い文をそのまま抽出して要約を作成する手法

メリット

文書中の文で要約を生成するため、全く内容が異なる要約になりにくく、文法もおかしくならない。

デメリット

文書中の文しか使用することができないため、言い換えなどはできず、生成した要約は雑な印象を受ける。

抽象型

人間と同様に文書の意味を汲み取った上で要約を作成する手法

メリット

文書中に無い単語を使用することができるので、より自然な要約を作成することができる。

デメリット

文法的に正しく、前後の文脈との整合性を保つ自然な文書を生成することが難しい。


多くの自然言語処理は抽出型で行なっているみたいですね。 今回のアルゴリズムも抽出型です。

LexRank

抽出型要約のアルゴリズムの一つで、Google検索エンジンのPageRankの考え方を文書に利用した方法です。 DUC2004のテキスト要約で一番の評価を得た手法らしいです。 hazm.at

PageRankなのですが、簡単に言うと「多くのサイトにリンクされているWebサイトは良いサイトだろう」というアルゴリズムです。（語弊はありますが...）

PageRankはインターネット上のリンク構造をグラフとして捉え、Webサイトの重要度を計算します。

PageRankについての詳細はこちらへ
PageRankアルゴリズムおよびそれに関連する研究について 京都大学総合人間学部認知情報学系数理情報論分野 宮嶋健人 2009年1月30日

LexRankはその考え方を文書に利用しており、リンクの代わりに文と文の類似度を用います。 PageRankとLexRankを比べてみると以下の表のようになります。

PageRank LexRank
ノード Webサイト 文
エッジ リンク 文同士の類似度
ノードの重み 多くのサイトからリンクされているか
重要なサイトからリンクされているか		 多くの文と類似しているか
重要な文と類似しているか

LexRankの流れは以下のようになります。

  1. 各文同士の類似度を計算

  2. 求めた類似度から文書をグラフ化

  3. グラフから文書の重要度を計算

これをJulia(v1.0)という言語を用いて実装していきます。

以下のqiitaの記事を参考にしました。こちらの記事はPythonで実装していますね。 qiita.com qiita.com

類似度にはコサイン類似度を用います。その際に文をTF-IDFというものでベクトル化します。

日本語は英語のように空白で単語が切れていないので、MeCabという日本語形態素解析システムを用いて日本語を単語に切ります。

コードは以下のようになります。

index.jl

using PyCall

include("TFIDF.jl")
include("CosineSimilarity.jl")
include("LexRank.jl")

# 単語ごとに切ってくれるやつ
@pyimport MeCab
m = MeCab.Tagger("-Owakati")

# ファイル読み込み
fn = open(ARGS[1], "r") 
text = read(fn, String)
close(fn)

# 文書を句点で分割してリスト化
slicedText = split(replace(text, "\n" => ""), "。")

# 単語リストを作る
sentences = []
for i in slicedText
  if i != ""
    push!(sentences, split(m[:parse](i), " "))
  end
end

# 文のTF-IDF値を算出
tfScores = []
idfScores = Dict()
for sentence in sentences
  push!(tfScores, TFIDF.tf(sentence))
  merge!(idfScores, TFIDF.idf(sentences, sentence))
end

# 文の類似度算出 & 隣接行列作成
sentenceSum = length(sentences)
adjancencyMatrix = fill(-1 ,(sentenceSum, sentenceSum))
thoreshold = 0.1 # 閾値
for i = 1:sentenceSum, j = 1:sentenceSum
  if adjancencyMatrix[i, j] >= 0
    continue
  elseif i == j
    adjancencyMatrix[i, j] = 1
    adjancencyMatrix[j, i] = adjancencyMatrix[i, j]
    continue
  else 
    if CosineSimilarity.cosineSimilarity(sentences[i], sentences[j], tfScores[i], tfScores[j], idfScores) >= thoreshold
      adjancencyMatrix[i, j] = 1
      adjancencyMatrix[j, i] = adjancencyMatrix[i, j]
    else
      adjancencyMatrix[i, j] = 0
      adjancencyMatrix[j, i] = adjancencyMatrix[i, j]
    end
  end
end

# グラフ化し重要度算出
sentenceScores = LexRank.lexRank(adjancencyMatrix, sentenceSum)

# 文とスコアをタプルで一つのデータとする
sentenceData =　[]
for i = 1:length(sentenceScores)
  push!(sentenceData, (i, sentenceScores[i]))
end

# スコアで降順にソート
sort!(sentenceData, rev=true, by = x -> x[2])

# 出力する文の数
n = 5

for i = 1:n
    println("==========")
    println(sentenceData[i][2])
    println(slicedText[sentenceData[i][1]])
end

TFIDF.jl

__precompile__()

module TFIDF

  function tf(sentence)
    termSum = length(sentence)
    tfScores = Dict()

    for i = 1:termSum
      count = 0
      for j = 1:termSum
        if sentence[i] == sentence[j]
          count += 1
        end
      end
      push!(tfScores, sentence[i] => count/termSum)
    end

    return tfScores
  end

  function idf(sentences, sentence)
    sentenceSum = length(sentences)
    termSum = length(sentence)
    idfScores = Dict()

    for i = 1:termSum
      count = 0
      for s in sentences
        if sentence[i] in s
          count += 1
        end
      end
      push!(idfScores, sentence[i] => log(sentenceSum/count)+1)
    end

    return idfScores
  end

end

CosineSimilarity.jl

__precompile__()

module CosineSimilarity

  function cosineSimilarity(sentence1, sentence2, tfScores1, tfScores2, idfScores)
    uniqueTerms1 = Set(sentence1)
    uniqueTerms2 = Set(sentence2)
    commonTerms = intersect(uniqueTerms1, uniqueTerms2)

    numerator::Float64 = 0
    denominator1::Float64 = 0
    denominator2::Float64 = 0

    for term in uniqueTerms1
      denominator1 = denominator1 + (tfScores1[term]*idfScores[term])^2
    end
    for term in uniqueTerms2
      denominator2 = denominator2 + (tfScores2[term]*idfScores[term])^2
    end
    for term in commonTerms
       numerator = numerator + tfScores1[term]*tfScores2[term]*idfScores[term]^2
    end

    if denominator1 > 0 && denominator2 > 0
       return numerator/(sqrt(denominator1)*sqrt(denominator2))
    else
       return 0
    end
  end
  
end

LexRank.jl

__precompile__()

module LexRank

  using LinearAlgebra

  function lexRank(adjancencyMatrix, sentenceSum)
    probabilityMatrix = zeros(sentenceSum, sentenceSum)
    for i = 1:sentenceSum, j = 1:sentenceSum
      degree = sum(adjancencyMatrix[i, :])
      probabilityMatrix[i, j] = adjancencyMatrix[i, j] / degree
    end

    return powerMethod(probabilityMatrix, sentenceSum)
  end

  function powerMethod(adjancencyMatrix, sentenceSum, errorTolerance=10e-6)
    p = fill(1.0 / sentenceSum, sentenceSum)
    error = 1.0
    while error > errorTolerance
      nextP = adjancencyMatrix' * p
      error = norm(nextP - p)
      p = nextP
    end

    return p
  end

end

使用方法は以下の通りです。

julia index.jl 要約したいテキストファイル

要約って言っても重要度の高い文を出力するだけなのですが😅

実際に要約してみます。

走れメロスの場合

$ julia index.jl ./text/hashiremerosu.txt
==========
0.002469528258634436
メロスには父も、母も無い
==========
0.002469528258634436
女房も無い
==========
0.002469528258634436
十六の、内気な妹と二人暮しだ
==========
0.002469528258634436
セリヌンティウスである
==========
0.002469528258634436
今は此のシラクスの市で、石工をしている

うーん、要約ではない笑

どうやらLexRankにとって小説やエッセイなどは難しいみたいですね。

キング牧師の演説（日本語訳）の場合

>>> julia index.jl ./text/kingubokushi.txt
==========
0.011122951656577073
だがわれわれは、正義の銀行が破産しているなどと思いたくない
==========
0.011122951656577073
この緊急事態を見過ごせば、この国にとって致命的となるであろう
==========
0.011122951656577073
黒人に公民権が与えられるまでは、米国には安息も平穏が訪れること はない
==========
0.011122951656577073
われわれは、肉体的な力に魂の力で対抗 するという荘厳な高みに、何度も繰り返し上がらなければならない
==========
0.011122951656577073
そうだ、決して、われわれは満足することはできないの だ

要約っぽいかな？笑

逆にテーマや論点がはっきりしている文書などは良い結果が出るみたいです。

要約の評価をどうするか、文をどのように組み合わせるかが課題ですね。

さいごに

今回はJuliaで実装しましたが、最初LexRankを実装した時はPythonを使用しました。

しかしなぜJuliaに変更したのかというと、大きな文書を処理する場合にPythonでは時間がかかり過ぎていたためです。

アルゴリズムの変更やnumpyでベクトル化など色々考えましたが、なんかめんどくさそうだし、最近v1.0が出たJulia気になるしということでJuliaにしました笑

実際に速度を比べてみるとJuliaにして30倍以上速くなりました笑

どうやらこちらを見るとまだまだ速くできそう🧐

Julia自体は結構書きやすかった（私のコードはまだまだですが😅）ので、Pythonから変更する時もそこまで苦労はしませんでした。

JuliaはPythonの資産も利用することができるので、今回ぐらいの規模であれば私はJuliaはありだなーって思いました笑