株式会社ゴクロの中路です。普段は機械学習の手法を用いたアルゴリズム改善など、サーバーサイドの開発を行っています。

SmartNewsでは様々なニュース記事を「エンタメ」「スポーツ」「グルメ」などのチャンネルに分けて表示しています。そのようなことを可能にするためには、ニュース記事がどのチャンネルに属するのかを判断する必要があるわけですが、それを行っているのは人ではありません。機械が、アルゴリズムに基づいて、自動的に行っています。 今回のエントリーでは、その「自動的にチャンネルに分類する仕組み」について書こうと思います。

SmartNewsにおける、ニュース記事のチャンネル判定を単純化すると、ベースには「ナイーブベイズ分類器」と呼ばれる、機械学習の初歩的な知見があります。このエントリーではナイーブベイズ分類器をメイントピックとして取り上げます。ナイーブベイズ分類器については、すでに様々なところで語られてはいますが、実運用するときに必要な「スムージング」を、パラメータの事前分布から導出するなど、少しモダンな機械学習手法の香りも混ぜた内容にしていますので、ナイーブベイズ分類器についてすでにご存知の方もお付き合い頂けると幸いです。

ナイーブベイズ分類器

概要

ナイーブベイズ分類器はテキストをいくつかのクラスに分類する分類器です。文章のカテゴリーを判定するのに用いられる他、メールがスパムメールであるか、そうでないかを判定するために用いられることもあります。 実装が比較的容易なのにも関わらず、精度がそれなりに高いというのが大きな利点です。また、分類に必要な計算量は、基本的には文章の長さに比例する程度で比較的高速なので、実際のサービスで運用するのにも適しているといえます。

学習データ

学習データとしてはカテゴリーがすでにわかっている文章を用意します。例えば学習データの例は以下です。

文章 カテゴリー
東京でサッカー大会が開催された。xx選手のゴールが冴え渡っていた。 スポーツ
テレビドラマ○○に出演中の××、結婚を報告。 エンタメ

はじめにこのような学習データを使って、各カテゴリーに属する文章の特徴を学ばせておいて、分類器のパラメータの値を決定します。

定式化

ここではナイーブベイズ分類器の背景にある理論を定式化します。

ある文章 $ D $ が生成されたとき、そのカテゴリーが $ C $ であるという条件付き確率を $ P(C|D) $ とします。例えばSmartNewsのチャンネル判定ならば、 $ D $ は 「今日はアイドルのコンサートがあります。たくさんの歌が披露されます。」 のような文章にあたり、カテゴリー$C$は「スポーツ」カテゴリーだったり、「エンタメ」カテゴリーなどにあたります。 $ P(C|D) $ は、スポーツカテゴリーに分類される確率: $ P(スポーツ|D) $ や、エンタメカテゴリーに分類される確率: $ P(エンタメ|D) $ を表しています。

通常は、各 $ P(C|D) $ を計算した後、

$ P(C|D) $ を最大化する $ C $ こそが、文章 $ D $ が属するカテゴリーである

というようにカテゴリーを判定します。つまり、最も属する確率の高いカテゴリーが文章Dのカテゴリーである、というわけです。

ベイズの定理を用いると

$$ P(C|D) = \frac{P(D|C) * P(C)}{P(D)} $$

と計算されるので、右辺のそれぞれの項

  • $ P(D|C) $
  • $ P(C) $
  • $ P(D) $

これら3つの値が計算できてしまえば、カテゴリー判定ができることになります。更にいえば、 $ P(D) $ はカテゴリーに依らないので、始めの2つ

  • $ P(D|C) $
  • $ P(C) $

さえ計算できればカテゴリー判定が可能です。以下では、この2つ $ P(D|C) $ , $ P(C) $ について順に見ていきます。

$P(D|C)$について

これはカテゴリー $ C $ が与えられたとき、ドキュメント $ D $ が生成される確率です。これではあまりに抽象的ですが、ナイーブベイズ分類器はこれを以下のようにモデル化します。

$$ P(D|C) = \prod_{w\;in\;D} P_{C,w} $$

$ P_{C,w} $ は後述するように、学習データの全文書数を $ N $ とし、カテゴリー $ C $ の文章の中で単語 $ w $ を含むものの数を $ N_{C,w} $ とすると

$$ P_{C,w} = \frac{N_{C,w}+1}{N} $$

になります。つまり、ざっくりいえば $ P_{C,w} $ は「学習データの文章の中でカテゴリーCでかつ単語wを含む文章の割合」です。事前に学習データによって決めるのはこの値です。例えば “サッカー” という単語はカテゴリー “コラム” の文章よりも、カテゴリー “スポーツ” の文章の中に多く含まれるでしょうから、 $ P_{スポーツ,サッカー} $ は $ P_{コラム,サッカー} $ よりも大きくなるでしょう。

$ \displaystyle\prod_{w\;in\;D} $ は「ドキュメント $ D $ の中に含まれる単語について全て積をとりなさい」ということを意味しています。

例えば $ D $ を”私はサッカーが好きです。サッカー観戦にもよく行きます。”という文章とするならば、この文章を {私, サッカー, 観戦} といった、3つの単語の集まりだとみなし、

スポーツカテゴリーによって生成された確率ならば

$$ P(D|スポーツ) = P_{スポーツ,私} * P_{スポーツ,サッカー} * P_{スポーツ,観戦} $$

エンタメカテゴリにによって生成された確率ならば

$$ P(D|エンタメ) = P_{エンタメ,私} * P_{エンタメ,サッカー} * P_{エンタメ,観戦} $$

として計算します。

文章 $ D $ に含まれる単語群がカテゴリー $ C $ の文書に含まれていそうな単語であればあるほど、それがカテゴリー$C$によって生成された確率が高くなるということですから、それほど直感に反しないかと思います。

(単語の抽出の方法をどうするか、というのは重要な問題です。日本語の場合は例えば文字を3文字ずつ抽出するということもあり得ますし、形態素解析をして特定の品詞のみを抜き出すということもあり得ます。)

P(C)について

これは通常、学習データの文書の中でカテゴリーCの文書が占める割合、というように選ばれます。

学習から分類までの手順まとめ

以上のような定式化に基づき、カテゴリーが未知の文章 $ D $ のカテゴリを判定する手順を整理すると、以下のようになります。

  1. 学習データを使って $ P_{C,w} = \frac{N_{C,w} + 1}{N} $ の式から $ P_{C,w} $ を計算しておく
  2. カテゴリが未知の文章 $ D $ に対して、$ P(C|D) $ を計算する
  3. $ P(C|D) $ を最大にするカテゴリー $ C_{max} $ を探す

以上で定まった $ C_{max} $ を文書 $ D $ のカテゴリであると判定します。

分類結果をざっくりいうと

「文章 $ D $ に含まれる単語群の中に、カテゴリー $ C $ の文書に含まれていそうな単語が含まれていれば含まれているほど、カテゴリー $ C $ に分類される確率が高くなる」という直感と一致する結果になります。

補足:学習データからパラメータを決める

最後に、少し天下り的だった、学習データと分類器のパラメータの関係

$$ P_{C,w} = \frac{N_{C,w} + 1}{N} $$

について補足したいと思います。少し数式がごちゃごちゃするので、ここは読み飛ばしてくださっても構いません。

学習データを文章 $D_i $ とカテゴリ $ C_i $ のペア $ (D_i, C_i) $ (i=1〜N)と表現することにし、 $ D_i $ をまとめて $ {\bf D} $ 、 $ C_i $ をまとめて $ {\bf C} $ と書くことにします。また、 $ P_{C,w} $ をまとめて $ {\bf P} $ と書くことにします。

以下では $ P_{C,w} $ を

  • 最尤推定の方法
  • ベイズ推定の方法

の二種類を用いた導出方法について書きます(詳細な計算は省きます)。

最尤推定の方法

最尤推定を用いる場合、各 $ P_{C,w} $ の値は、学習データのペア $ (D_i, C_i) $ (i=1〜N) と、ナイーブベイズモデルの式

$$ P(D|C,{\bf P}) = \prod_{w\;in\;D} P_{C,w} $$

が与えられたとき、 $ P({\bf D}, {\bf C}|{\bf P}) $ を最大にするような $ {\bf P} $ として決めます。 詳細な計算を省くと、結果は

$$ P_{C,w}\propto N_{C,w} $$

となります。

しかし、このままだと、例えば学習データの「スポーツ」カテゴリーの文章の中に「熱狂」という単語が一つも出てこなければ、「サッカー選手権が行われた。観客たちは選手たちのプレイに熱狂した」という文章が「スポーツ」カテゴリに属する確率が0になってしまうなど、実用上問題があります(一般にゼロ頻度問題といいます)。この問題を解決するために手で1を加えて

$$ P_{C,w}\propto (N_{C,w} + 1) $$

としてしまう、「ラプラススムージング」という手法が通常とられます。

ベイズ推定の方法

ベイズ推定を用いる場合、${\bf P}$自身は事前分布$P({\bf P})$に従うと仮定し、 各$P_{C,w}$の値は、学習データのペア$ (D_i, C_i) $ (i=1〜N)

と、ナイーブベイズモデルの式 $$ P(D|C,{\bf P}) = \prod_{w\;in\;D} P_{C,w} $$ が与えられたときの$P_{C,w}$の期待値として決めます。

事前分布$P({\bf P})$としては、便利のためにディリクレ分布を選ぶことが一般的です。すなわち $$ P({\bf P}) = \frac{1}{Z}\prod_{C}\prod_{w}P_{C,w}^{\alpha_w - 1} $$ (Zは規格化定数)

こちらも詳細な計算を省くと、結果は $$ P_{C,w}\propto (N_{C,w} + \alpha_w) $$ となります。 $\alpha_w=1$のとき、結果は最尤推定+ラプラススムージングと一致します。

過学習について

上で、最尤推定を行った際に起こったゼロ頻度問題は、いわゆる「過学習」に対応します。一方ベイズ推定を行った際は、パラメータの事前分布を仮定することで過学習が防がれています。このような、「パラメータの事前分布を仮定することで過学習を防ぐ」という手法は、回帰問題においてなど、多くの機械学習の問題においてみることができます。 C

参考

今回書いたナイーブベイズ分類器など、言語処理の入門的な内容を理解するのに 言語処理のための機械学習入門 (自然言語処理シリーズ) は非常に参考にさせて頂きました。

まとめ

このエントリーでは、SmartNewsの記事を自動的にチャンネルに分類する仕組みのベースにある、ナイーブベイズ分類器について書きました。

SmartNewsがユーザーの皆様に情報をお届けするにあたって、機械学習の知見は、チャンネル分類に限らず非常に多くの点で生かされています。今後、よりよいサービスにしていくにあたって、その重要度は更に増していくと思われますので、様々な手法を取り入れながら、日々改善を続けていきたいと思っています。

P.S. 株式会社ゴクロでは、SmartNewsの成長を加速してくれるエンジニアを募集しております。興味の有る方は是非ご連絡ください！