文章要約アルゴリズムについて、興味深いブログ記事があって読んでみたのでまとめてみる。
Build your own summary tool! | The Tokenizer
アルゴリズムのquick overviewとhands on exercise, python implementationについての内容。コードはgistで公開されている。summary_tool.py
summarization technologies:
文章要約には二つのアプローチがある。
- 文章を解析して、短く書き換えたり言い換えたりする
- 筆者の知る限り、このアプローチではあまりいい結果は得られてない
- キーセンテンスを抽出して、適切に編集する
- これを実装した有名なアルゴリズムが、TextRank。
- この記事で説明するアルゴリズムもこちらのアプローチ。
Our summarization algorithm
ここからは、筆者が実装した単純なアルゴリズムの説明。
The intersection function
二つのセンテンス(s1, s2)を引数に取り、それらの類似度をスコアとして返す。
センテンスをwords/tokensに分割し、共通のトークンをカウント、二つのセンテンスの平均長で正規化。
f(s1, s2) = | { w | w in s1 and w in s2 } | / (( |s1| + |s2| ) / 2)
The sentence dictionary
ここがアルゴリズムの中心。
文章を入力として受け取り、各センテンスのスコアを返す。
計算は二つのステップで行われる。
- 文章をセンテンスに分割し、類似度を行列に格納
- values[0][2]→#1のセンテンスと#3のセンテンスの類似度。
- 文章は重み付き完全グラフに変換。各センテンスがノードで、2次元配列がエッジの重みを保持。
- センテンス毎のスコアを計算し、センテンスをキーにした辞書型に合計スコアを格納
- 合計はキーとなるセンテンス以外のセンテンスとの類似度の単純な合計。
- ノードに接続しているすべてのエッジを単純に合計することで算出。
Building the summary
アルゴリズムの最後のステップ、要約を生成する部分。
まず、文章をパラグラフに分割。
センテンス辞書を基に、パラグラフに最適なセンテンスを選択する。
各パラグラフはグラフの論理的なサブセットを表現しているので、サブセットから最適なノード＝センテンスを単に選ぶだけ
Why this works?
2つの主な理由がある
- パラグラフは文章の論理的にアトミックな単位である
- 著者が文章をそのように分割することにした最も良い理由がおそらくそこにある。
- 類似度、キーセンテンス
- もし、二つのセンテンスの類似度が高いとすると、おそらく同じ情報を保持しているはず。
- だから、あるセンテンスが他の複数のセンテンスと高い類似度であるとすると、おそらく他の複数のセンテンスの情報を保持しているはず、つまり文章のキーセンテンスである
Your turn
あなたが試せることをいくつか。
- このライブラリを使って、URLから文章を取得してサマリーを生成できるようにする
- 意図的に他のパッケージを使ってないので、NLTKやOpenNLPを使ってみるなど
- 類似度計算で遊ぶ
- 例えば、ストップワードやステミング（語幹処理）、正規化計算を変えてみる
- アルゴリズムのバリエーション
- 例えば、各パラグラフから最適なセンテンスを選ぶ代わりに、2,3の最も重要なパラグラフを選択することを試す（この場合は、センテンスではなくパラグラフをノードしたグラフ）
- タイトルを使う
- 例えば、類似度算出において何らかの要素として
- 英語以外の別の言語で試す
実行してみる
最後に、公開されているコードを実行してみる。
といっても、実行は簡単でgitでcloneして、pythonで実行するだけ。
$ git clone https://gist.github.com/5473521.git
$ cd 5473521
$ python summary_tool.py
実行すると、要約前のテキストに対して、
要約結果が得られます。
Swayy is a beautiful new dashboard for discovering and curating online content [Invites]
Lior Degani, the Co-Founder and head of Marketing of Swayy, pinged me last week when I was in California to tell me about his startup and give me beta access
One week later, I’m totally addicted to Swayy and glad I said nothing about the spam (it doesn’t send out spam tweets but I liked the line too much to not use it for this article)
What is Swayy? It’s like Percolate and LinkedIn recommended articles, mixed with trending keywords for the topics you find interesting, combined with an analytics dashboard that shows the trends of what you do and how people react to it
After I decided that I trusted the service, I added my Facebook and LinkedIn accounts
The analytics side isn’t as interesting for me right now, but that could be due to the fact that I’ve barely been online since I came back from the US last weekend
It was the suggested content that impressed me the most
Yes, we’re in the process of filing a patent for it
Ohad Frankfurt is the CEO, Shlomi Babluki is the CTO and Oz Katz does Product and Engineering, and I [Lior Degani] do Marketing
➤ Want to try Swayy out without having to wait? Go to this secret URL and enter the promotion code thenextwebOriginal Length 4529
Summary Length 1274
Summary Ratio: 71.8701700155
