Edited at
NewsPicksDay 23

ニュース記事からのトレンドキーワード抽出〜サービスインまでをふりかえる

こんにちは。 NewsPicks アドベントカレンダー 2018 23日目 :santa: を担当する打田です。NewsPicks では,サーバサイド開発(+ときどきフロント)と,検索サービスの開発運用を担当しています。個人では,python製の形態素解析ライブラリApache Lucene の GUI ツール を開発・メンテしたり,少し前には Apache Solr の本を執筆(共著) したりしています。


[お知らせ] トレンドキーワード機能をリリースしました!

NewsPicks では,これまで Pick された全ニュース記事の検索機能を提供していますが,先週,Web 版 NewsPicks の検索補助機能として,「トレンドキーワード」機能をリリースしました。これは,いまホットな話題に関連する単語を,検索キーワードとしておすすめする機能です。

Web 版 NewsPicks にアクセスして左上の検索キーワード入力フォームにカーソルを当てると,検索履歴と併せて「トレンドキーワード」が表示されます。こちらは 12/18 時点のトレンドキーワードです。

スクリーンショット 2018-12-18 11.07.21.png

同様の機能を iOS/Android アプリにも実装予定なので,もうしばらくお待ち下さい。:bow:

日々多数のニュースが届く中で,ユーザーのみなさまには,いまホットな話題は何かを素早く発見してもらい,さらに,検索結果に表示されるニュースを追うことで話題へのキャッチアップに役立ててもらえれば,という想いで開発しました。タブに掲載されるニュース(こちらは,編成専門チームが掲載記事を選び,構成を練り,運用しています)とはまた違った観点での情報収集の一助となれば幸いです。

本記事では,リリースしたばかりのトレンドキーワード開発の裏側をご紹介したいと思います。

なお,トレンドキーワードのコア部分はほぼほぼ,2018年にインターンとしてジョインしてくれた高橋翔大さんが担当してくれました。私含む周囲からの沢山の わがまま フィードバックを受けながら,プロダクション運用に耐えうるレベルまで,きっちり性能を高めてくれました。 :clap:

(API 開発や既存システムとのつなぎ込み,周辺ツールなど,サービスインにまつわる作業は私のほうで実施しています。)


どうやってトレンドキーワードを抽出しているのか

今回リリースした「トレンドキーワード」では,ニュース記事のタイトル(HTML の title メタタグ)とサマリー(HTML の description メタタグ)のテキストデータから,「ここ直近で急激に出現確率が高くなったワード」を抽出しています。

メールやニュース記事のようなテキストストリームにおいて,「あるワードの出現確率が急激に高くなっている」状況を,自然言語処理/時系列分析の文脈では「バースト (burst) している」といい,バーストを特定することを「バースト検知 (burst detection)」と呼びます。

バーストを検知するアルゴリズムとして Kleinberg の手法(Bursty and Hierarchical Structure in Streams)が有名で,機械学習フレームワーク Jubatusjubaburst として実装されています。今回のトレンドキーワード機能開発では, jubaburst を利用してバースト検知を行いました。


Kleinberg のバースト検知

Kleinberg のバースト検知は,教師なし機械学習に位置づけられます。

学習モデルのイメージをざっくり掴んでもらうため,概要の説明を試みてみます。(詳しい方,数式が苦手な方は読み飛ばしてください。誤りがあったらコメントでご指摘お願いします!)

数理モデル導出の詳細については オリジナルの論文 と,高橋さんの 論文紹介 を参照ください。


Two-state model (2状態モデル)

Kleinberg のバースト検知のもっとも基本となるのは 2 状態の確率付き有限状態オートマトンです。なんとなく難しそうな用語が出てきて,実際真面目に数式を追うのは簡単ではないのですが,コンセプトはシンプルです(私が学んだときは,スマートに抽象化されたモデルに感動しました)。

たとえば,Twitter のツイートを常時監視して,「バルス」という単語が出てくるツイートだけをすべて抜き出して,タイムスタンプ順で並べたと考えてください。普段は時々ツイートされるくらいですが,天空の城ラピュタ放映時,とくにパズーとシータが叫ぶシーンでは,普段よりもあきらかに大量のバルスツイートが現れるでしょう(実際調べたことはないですが,たぶんきっと)。

この状況を,数学的に状態遷移図・有限オートマトンで表せます。状態 $q_0$ が通常時,$q_1$ がバースト時( 「バルス!」 シーン前後)を表しています。$q_0$ から $q_1$, $q_1$ から $q_0$ へは確率 $p \hspace{2pt} (0 \leq p \leq 1)$ で遷移します。 $p$ は,状態の変わりやすさを決めるパラメータです。

two-state model.png

また,メッセージ(ツイート)到着間隔 $X$ は指数分布に従うとし,$q_0$ と $q_1$ にはそれぞれ到着間隔 $X$ の分布を決める確率密度関数が割り当てられます。

q_0 にいるとき: X の分布は確率密度関数 \hspace{2pt} f_0(x) = \alpha_0e^{-\alpha_0x} で表現できる \\

q_1 にいるとき: X の分布は確率密度関数 \hspace{2pt} f_1(x) = \alpha_1e^{-\alpha_1x} で表現できる \\
ここで,\alpha_1 > \alpha_0 \hspace{2pt} (\alpha \hspace{2pt} が大きいほどメッセージが短い間隔で届きやすい)

このように状態遷移モデルを定めて,メッセージ到着間隔 $x$ の系列 $(x_1, x_2, ..., x_n)$ (これはメッセージのタイムスタンプから計算できます)を与えると,もっとも起こりやすい状態 $q$ の系列 $(q_{i_1}, q_{i_2}, ..., q_{i_n})$ は下記のコスト関数を最小化することで求められます(導出について知りたい方は論文2章を参照ください)。

c(q|x) = b \ln (\frac{1-p}{p}) + (\sum_{t=1}^n -\ln f_{i_t}(x_t)) \\

ここで,\hspace{2pt} b \hspace{2pt} は状態遷移が起こった回数

$b$ と $p$ はモデルのパラメータとして指定します。

$q$ の系列 $(q_{i_1}, q_{i_2}, ..., q_{i_n})$ が推定できると,あるタイミング $t$ で $q_0$ と $q_1$ のどちらにいたか,つまり非バースト状態だったかバースト状態だったかが推定できる,ということになります。

論文では,2 状態モデルを拡張した無限状態モデルや,バーストの階層を取り入れたモデルも提案されていますが,ここでは割愛します。


Enumerating bursts (列挙型バースト)

前節で紹介したモデルでは,メッセージがひとつずつ届くことを前提にしていました。このモデルでは 1 度に多数のメッセージがまとめて届くような状況に対応できないため,メッセージを 1 つずつではなく,バッチとして処理する手法が論文 4 章で提案されています。jubaburst でもこのモデルが実装されています。

以下,バーストしているかを検知したいワードを $w$ とします。

解析するストリームは $n$ 個のバッチ(メッセージのまとまり)からなり,$t$ 番目のバッチは $d_t$ 個のメッセージを含み,そのうち $r_t$ 個のメッセージに $w$ が現れる($w$ に関連するメッセージが $r_t$ 個ある)とします。

そうすると,ストリーム全体のメッセージ数は $D =\sum_{t=1}^n d_t$, うち $w$ が現れる全メッセージ数は $R = \sum_{t=1}^n r_t$, $w$ が現れる平均的な確率は,$\frac{R}{D}$ と計算できます。

さっきとまったく同様に,$q_0$ (非バースト) と $q_1$ (バースト) からなる 2 状態モデルを考え(※論文では無限状態モデルとして一般化して,それを 2 状態に制限しています),それぞれの状態に割り当てる確率密度関数は以下で与えます。

q_0 : f_0(x) = p_0e^{-p_0x}, \hspace{4pt} p_0 = \frac{R}{D} \\

q_1 : f_1(x) = p_1e^{-p_1x}, \hspace{4pt} p_1 = p_0 s \\
ここで,\hspace{2pt} s \hspace{2pt} > 1 \hspace{2pt} はスケーリングパラメータ。\\
s \hspace{2pt} は 1 より大きいので必ず \hspace{2pt} p_1 > p_0 \hspace{2pt} となることに注意。

$t$ 番目のバッチ到着時,状態 $q_i \hspace{2pt} (i \in \{0, 1\})$ にいるコスト関数 $\sigma$ を,以下で定めます。

\sigma(i, r_t, d_t) = -\ln[(\begin{matrix} d_t \\ r_t \end{matrix}) p_i^{r_t}(1 - p_i)^{d_t - r_t}]

また,状態 $q_0$ から $q_1$ への遷移コストとして

\tau(0,1) = \gamma \hspace{2pt} (\gamma は調整用のパラメータ。大きいほどバースト状態と判定しづらくなる)

を与えます。状態 $q_1$ から $q_0$ への遷移コストは $0$ です。

区間 $[t_1, t_2]$ 間のバースト重み (burst weight) を以下で与えます。コスト関数や weight 定義の背景(気持ち)に興味があれば論文を参照していただければと思いますが,要点は,$q_1$ にいるコストが小さいほど,weight が大きくなる,という点です。

\sum_{t=t_1}^{t_2} (\sigma(0, r_t, d_t) - \sigma(1, r_t, d_t))

実用では,バーストを検知したいワードは1つではなく多数ある(可能性のあるワードすべてについてバーストしているかどうかを推定したい)ことが多いので,すべてのワード $w$ について,独立に状態モデルを定め,burst weight を計算します。


jubaburst

Jubatus の jubaburst とそのパラメータ調整については,下記参考リンクに詳しいので,解説はリンク先を参照ください。熟読させていただきました,ありがとうございます。 <(_ _)>


性能向上への道のり

初期の実装では,プロダクションに出すには厳しい抽出精度(というと語弊がありそうですが,だいぶいまいちな結果だった)でした。実用に耐えうる,いい感じの性能を出すために工夫したこと(工夫してもらったこと)をまとめたいと思います。


Jubatus パラメータ調整

参考リンクにも記載されていますが,大事なのは jubaburst 起動時に設定ファイルで与える window_batch_size, batch_interval と,キーワード追加時に与える scaling_param, gamma になります。最適なパラメータ値は試行錯誤中ですが,現在以下のパラメータで運用しています。



  • batch_interval は 1 バッチの間隔が 6 hours となるように調整


  • window_batch_size は 8

bust_window.png

scaling_paramgamma は,本来キーワード候補ごとに変更する値ですが,いまは全キーワード候補で共通の値を指定しています。



  • scaling_param: 2.01


  • gamma: 0.01

なお,window_batch_sizebatch_interval はいくつか変更して結果を見てみたところ,そこまで大きな差異はありませんでした。今回適用したデータについては,パラメータの影響を受けにくく,そこそこロバストなモデルになっているようです。


前処理(キーワード候補の選定)

バースト検知アルゴリズム自体には,$w$ としてどんなキーワードを選ぶかというのは含まれません。前処理としてキーワード候補を選ぶ必要があります。実際上はここが一番苦労するかもしれません。

課題1. 単語分割

たとえば,MeCab で形態素解析すると,「QRコード」は「QR」と「コード」に分割されるため,「QRコード」が話題になった場合「コード」という単語がバースト判定されてしまい,これでは何のことかよくわかりません。Kleinburg の論文でも,「data base」がバーストした時に「data」と「base」が別々にバースト判定されてしまう,という指摘があります。

課題2. 一般的すぎる語

「日本」「AI」「スマホ」など,あまりに一般的すぎる語がバースト判定されてしまいます。論文では「some」「on」といった一般的な用語が検出される点に触れて,特定の期間における言い回しの流行の影響を受けているのでは,という考察がなされています。

課題1 と 2 をクリアして質の良いキーワード候補を選ぶため,以下の工夫を取り入れました。ここではヒューリスティクスに泥臭いことをいろいろやっています。


  • MeCab IPADIC に加えて, NEologd を併用して新語に対応する

  • 単語 n-gram を作る

  • 文字種別を見て,(たとえば)ひらがなだけからなる短い文字列は除外する

  • 1年分の記事を解析して idf 値を計算しておき,定常的に出現頻度が高い語句は除外する

  • (上記ルールでどうしても対応できないものは)NGワードリストを作る

  • etc.


後処理(ランキングとフィルタリング)

前処理で選んだ各キーワードについて burst weight を計算したら,Window 内でバースト度合い(以下,スコアと記載)の大きいキーワード上位 N 個を選んで保存します。(注意: Jubatus API ドキュメントに,「バーストレベルは相対的な値であり、複数のキーワード間で相互に値を比較することはできない」とあるので,単に burst weight の大きい順に並べるのではなく,正規化するなど,キーワード間で比較できるようにする必要があるでしょう。)

スコア順にランキングしたあと,いくつか課題が出たので,フィルタリング処理を実施しました。


  • あるキーワードがあるキーワードの部分文字列になっている場合,スコアの大きいほうだけ残し,片方は除去する

  • 検索結果数が少ないキーワードは除去する


    • トレンドキーワード抽出と検索エンジン側とで単語分割方法が違うため,検索結果のチェックが必要



なお,スコアの決め方にはまだ課題があり,良いキーワードに低いスコアがつくことがあります。UI上の制限もあり,ユーザー向けに表示できるのは上位数個なので,いかに上位に適切なキーワードをランクインさせるかは今後の課題です。


システム・アーキテクチャ

システム全体のアーキテクチャは以下の図のようになっています。上記で説明したトレンドキーワード抽出バッチ(コア部分),マイクロサービスとして実装された内部API,管理コンソールからなるシンプルなシステムです。

architecture.png


API

NewsPicks の検索サービスは Kotlin で実装されており(なおバックエンドの検索エンジンは Elasticsearch を使っています),トレンドキーワード API についても Kotlin で実装しました。Web フレームワークには最近 v1.0 が出たばかりの Ktor,DB層の抽象化には軽量 SQL ライブラリ Exposed を採用しました。どちらもいままで使ったことはありませんでしたが,調査含めて 1 週間程度で開発完了したので,習得しやすいフレームワークだと思います。(Ktor のほうは)ドキュメントも整っており,declarative なフレーバーを取り入れながら,Kotlin らしく簡潔さを追求したフレームワークになっているので,Kotlin をサーバサイドで採用している方は,ぜひ触ってみてください。


Web 管理ツール

トレンドキーワードは,リアルタイム性を重視するため基本的に全自動で運用されており,ユーザーの目に触れる前に露出可否のチェックなどは行っていません。

とはいえもちろん完璧ではないので,話題のトピックを表現しているとは言い難いような一般的なキーワードや,そもそも単語として成り立っていないようなキーワード(形態素解析時点での失敗)が出てしまうこともあります。

そのようなノイズについては,気づいた時にすぐ運用者が対応できるよう,Web 管理ツールを作成しました。管理ツールでは,①現在露出しているキーワードの確認,②キーワードの無効化および有効化 を数クリックでできるようにしています。

こちらが実際に本番運用している画面です。

スクリーンショット 2018-12-18 19.44.31.png

実装は React.js + TypeScript + Material UI です。ちなみにフロント音痴の私は,React と TypeScript の勉強から始めて,たったこれだけの画面を作るのに 2 ~ 3 週間かかりました・・・。が,最初はどうしても馴染めなかった JSX も慣れてみると仲良くなれそうな気がします(たぶん :sweat_smile: )。サーバサイドエンジニアでも,管理ツールをさっと作れる程度のフロントエンドスキルはキャッチアップしておきたいですね。 :wink: :thumbsup:


さいごに

少し長くなりましたが,一つの機能を開発してプロダクションリリースするまでの流れを振り返ってみました。リリースしてから,性能的に至らない点や運用上の課題も見えてきていますが,今後改善していきたいと思います。

最初にも書きましたが,コアロジックはインターンで来ていた高橋さんに開発してもらっていて,前半の内容は,彼の実装を読み解いたものです。ありがとうございました!

NewsPicks プロダクトチームでは,「経済情報で、世界を変える」というミッションのもと一緒に働く仲間を募集しています。少しでも興味をもった方は,ぜひご連絡ください。

明日は,インフラレイヤーからサービス開発まで,幅広く活躍している,期待の Under 30 エンジニア @hirofumikubo さんです。おたのしみに。

[追記] 24日目の記事が公開されました:Microservice化を検討する上で考えるべき7つのこと