LexRankを実装してみる

# はじめに
[前回](https://qiita.com/t2hk/items/a010b72d290479d8d7a8)はMarkLogic10のCNTKを使ってword2vecを実装しました。word2vecを使えば文章要約のLexRankも実装できる、ということでやってみました。

今回のソースコードは以下に公開しています。
https://github.com/t2hk/lexrank

# 環境
| 環境 | バージョン |
| --- | --- |
| MarkLogic | 10.0-1 |
| CentOS | 7.6 |
| CUDA | 10.1 |

# LexRankについて
LexRankについては各所で解説されているので詳細は省きますが、抽出型の要約アルゴリズムです。
文章中の単語をベクトル化してCosine類似度を計算し、類似する文章の多さから重要度を求めます。以下の考えに基づいて重要度の高い文章を要約と考えます。

* 類似する文章が多い文章は重要な文章
* 重要な文章に類似する文章は重要

# 処理の流れ

1. 文書中の全文章をトークナイズし、各単語をword2vecで学習したベクトルに変換する
2. 各文章の単語ベクトルを平均し、文書ベクトルを求める
3. 文書間のCosine類似度を求める（文章数ｘ文章数の行列になる）
4. Cosine類似度が閾値を超えた文章同士は1、超えない場合は0とした隣接行列を作成する
5. その隣接行列を各要素の合計が1となる確立行列に変換する
6. この確率行列に対する固有ベクトルをべき乗法で算出し、これを各文章のスコアとする
7. スコアの上位を要約文とする

# MarkLogicのCNTKで実装する
処理の流れの1～5までは前回までのMarkLogic CNTK関連の投稿で実装できます。
文書のトークナイズは[cts:tokenize](https://docs.marklogic.com/cts:tokenize)関数を使います。それをword2vecのモデルを使ってベクトル化し、Cosine類似度を求めて隣接行列、確率行列を作ります。

問題はその後のべき乗法の実装です。
Numpyなら数行で記述できますが、XQueryの場合は行列の計算にCNTKを使う必要があり手間がかかります。
以下、べき乗法の処理です。

```xquery
(: $cosinme_matrix : 文章同士の確率行列
   $N : 文章数
   $p_old : 前回のpの値 :)
declare function local:power-method($cosine_matrix, $N, $p_old){
  let $error_tolerance := 10e-6  (:pの収束判定の閾値:)
  
  (:::::::::::::::::::::::::::::::::::::::::::::::
    p = np.dot(CosineMatrix.T, p_old) の計算
  :::::::::::::::::::::::::::::::::::::::::::::::)  
  (: 確率行列をモデルの入力データとして組み立てる:)
  let $input-variable-cos-mat := cntk:input-variable(cntk:shape(($N, $N)), "float")
  let $input-value-cos-mat := cntk:batch(cntk:shape(($N, $N)), 
                                         json:to-array(($cosine_matrix)), cntk:gpu(0), "float")  
  let $input-pair-cos-mat := json:to-array(($input-variable-cos-mat, $input-value-cos-mat))

  (: 算出する固有ベクトルpをモデルの入力データとして組み立てる :)
  let $input-variable-p-old := cntk:input-variable(cntk:shape(($N)), "float")
  let $input-value-p-old := cntk:batch(cntk:variable-shape($input-variable-p-old), 
                                       json:to-array(($p_old)), cntk:gpu(0), "float")
  let $input-pair-p-old := json:to-array(($input-variable-p-old, $input-value-p-old))
  
  let $input-pair := json:to-array(($input-pair-cos-mat, $input-pair-p-old))

  (:pを計算する。:)
  let $p := cntk:times($input-variable-cos-mat, $input-variable-p-old, 1, -1)
  let $p-eval := cntk:evaluate($p, $input-pair, cntk:function-output($p), cntk:gpu(0))
  let $p-value := cntk:value-to-array(cntk:function-output($p), $p-eval)

  return
    (:::::::::::::::::::::::::::::::::::::::::::::::
     err = np.linalg.norm(p - p_old) の計算
     pの差分(err)が閾値未満になるまで再帰的に実行する。
    :::::::::::::::::::::::::::::::::::::::::::::::)
    let $p-minus-p_old := cntk:minus($p, $input-variable-p-old )
    let $L2-norm := cntk:reduce-l2($p-minus-p_old, (cntk:axis(0)))
    let $L2-norm-eval := cntk:evaluate($L2-norm, $input-pair,
                                       cntk:function-output($L2-norm), cntk:gpu(0))
    let $err-value := cntk:value-to-array(cntk:function-output($L2-norm), $L2-norm-eval)

    return
      if ($err-value[1] > $error_tolerance) then 
        local:power-method($cosine_matrix, $N, $p-value)
      else $p-value
  )};
```

な、長すぎる・・・。ちょっとした計算なのに・・・。
でもXQueryで行列演算が出来るようになったのはちょっとすごいと思います。

# 要約してみる

* Wikipediaの[NoSQL](https://ja.wikipedia.org/wiki/NoSQL)の項目を5つの文章に要約すると以下のようになりました。

NoSQLの主要な内容は抽出できているのでは無いかと思います。
もともとWikipediaを使って学習した単語ベクトルを使っていますしね。

```
  - NoSQL（一般に "Not only SQL" と解釈される）とは、関係データベース管理システム (RDBMS) 以外のデータベース管理システムを指すおおまかな分類語である。
  - NoSQL
  - NoSQLという用語は1998年、SQLインタフェースを持たない軽量な関係データベースのオープンソースソフトウェアの名前として最初に用いられた。
  - キー・バリュー型 (Key Value Store) - キーに対してバリュー（値）という単純な構造。
  - 関係データベースを杓子定規に適用してきた長い歴史を打破し、それ以外の構造のデータベースの利用・発展を促進させようとする運動の標語としての意味合いを持つ。
```

* [青空文庫](https://www.aozora.gr.jp/)から、[芥川龍之介の「鼻」](https://www.aozora.gr.jp/cards/000879/files/42_15228.html)を要約してみました。

なんとなく顔について書かれている事は察しが付きますが、話の内容までは把握できないですね。
小説を要約するには、もう少し工夫した学習が必要そうです。
※ ルビを削らなかったので文章中に埋め込まれてしまっていますね。

```
  - しかしこうして飯を食うと云う事は、持上げている弟子にとっても、持上げられている内供にとっても、決して容易な事ではない。
  - それは折から、用事があって、池の尾の寺を訪れた侍さむらいが、前よりも一層可笑おかしそうな顔をして、話も碌々ろくろくせずに、じろじろ内供の鼻ばかり眺めていた事である。
  - 時によると、苦心すればするほど、かえって長く見えるような気さえした。
  - 勿論竜樹りゅうじゅや馬鳴めみょうも、人並の鼻を備えた菩薩ぼさつである。
  - 脂は、鳥の羽の茎くきのような形をして、四分ばかりの長さにぬけるのである。
```

* [Livedoorニュースコーパス](https://www.rondhuit.com/download.html#ldcc)

Livedoorニュースもいくつか要約してみましたが、概ねキーとなる文章を抽出していました。
これはプロが執筆したニュースブログということもあり、キーポイントをわかりやすく記述している事が要因では無いかと思います。

# まとめ
* 前回までで実装したword2vecを使ってLexRankも実装してみました。
* データベースに格納している文書を、データベース上で簡単に要約できるようになりました。
* 比較的簡単なアルゴリズムで、精度の高い抽出が期待できそうです。
* 種類の異なる文書を要約してみました。学習したモデルや対象の文書の種類によって、要約の質が大きく変わりそうです。