高校数学ではじめる機械学習 #5: 分類(その2): カテゴリを予測する - この記事のジャンルは何?

[目次はこちら](https://qiita.com/tomo_t/items/25035a9487bd5014754b)
##今回の問題
前回では、数値のデータ(模試の点数)をもとに、分類(大学の合格/不合格)を予測する方法を解説しました。
今回は数値データではなく、文章のデータをもとに分類する、<b>ナイーブベイズ</b>という方法を解説します。

今回のケースですが、あなたはメールでニュースを購読しているとしましょう。送られてくるヘッドラインから、ニュースをジャンル別に分類したいとします。学習用のデータとして、

|番号|ヘッドライン|ジャンル|
|---|---|---|
|1|フランスがワールドカップ優勝|スポーツ|
|2|メッシの得点でバルセロナ勝利|スポーツ|
|3|東京オリンピック延期へ|スポーツ|
|4|日本、ワールドカップ招致に立候補|スポーツ|
|5|巨人、坂本の感染を確認|スポーツ|
|6|政府、入国制限の緩和を検討|社会|
|7|東京の感染が落ち着きを見せる|社会|
|8|小池氏、東京都知事選に立候補か|社会|
|9|フランスがロックダウンを緩和|社会|
|10|バルセロナの観光地が再開|社会|

というニュースのヘッドラインを考えます。
これらのデータを使うと、

|番号|ヘッドライン|
|---|---|
|11|ワールドカップに向け感染警戒|
|12|東京の観光地、閑散とした週末|
|13|フランス大統領選の立候補者出そろう|

というニュースは、どのように分類できるでしょうか。

直感的には「ワールドカップ」というような言葉が入っていたらスポーツのニュース、「立候補」というような言葉が入っていたら政治のニュースだと思うのではないでしょうか。ナイーブベイズというのは、こういった、「XXという単語が入っているからジャンルはXX」という推論をコンピューターに行わせる推論です。

##条件付確率とベイズの定理
###条件付確率
ナイーブベイズの話をするには、<b>ベイズの定理</b>の話をしなければなりません。
ベイズの定理というのは、条件付確率についての重要な関係式です。

高校数学のおさらいですが、条件付確率$P(A|B)$というのは、条件Bが満たされたときのAの確率でした。たとえば、サイコロを振って$P(X=2|Xは偶数)$というのは、Xが偶数という条件下のもとで2が出る確率、つまり$1/3$です。

では、条件付確率にはどのような関係式があるのでしょう。まず、

```math
P(A \land B)=P(A|B)P(B)=P(B|A)P(A)
```
です。$P(A \land B)$はA「かつ」Bである確率で、上の式はそれがP(A|B)とP(B)の積であると主張しています。これは、AかつBであるためには、まずBである必要があって($P(B)$)、さらにその条件のもとでAである必要もある($P(A|B)$)、と考えると飲み込みやすいのではないでしょうか。
例えば実際に先ほどのさいころの例では、$P(X=2 \land Xは偶数)=1/6$ですが、

```math
\begin{align}
P(X=2|Xは偶数) \times P(Xは偶数)&=\frac{1}{3} \times \frac{1}{2} = \frac{1}{6} \\
P(Xは偶数|X=2) \times P(X=2)&=1 \times \frac{1}{6} = \frac{1}{6}
\end{align}
```
となり、確かにこの公式は成立しています。

###ベイズの定理
ベイズの定理というのは、さきほどの式をわずかに変形して、

```math
P(A|B)=\frac{P(B|A)P(A)}{P(B)}
```
と書いたものを言います。先ほどの式の右側の2辺だけを見て、$P(B)$で両辺を割りました。
若干複雑な形をしていますが、導出を考えれば簡単に思い出せます。

さて、これがどのようにニュースの分類に使えるのでしょう。まず単純に、"ワールドカップ"という単語だけに注目してみましょう。$P(カテゴリ|"ワールドカップ"が入る)$が最大になるようなカテゴリにニュースを分類するのが自然でしょう。
Aを「スポーツニュースである」Bを「ワールドカップという単語が含まれる」と考えてみましょう。すると、

```math
P(スポーツ|"ワールドカップ")=\frac{P("ワールドカップ"|スポーツ)P(スポーツ)}{P("ワールドカップ")}
```
と書くことができました。これは何を意味しているかというと、「ワールドカップ」という文字列が入るニュースがスポーツニュースである確率は、
$P("ワールドカップ"|スポーツ)$: スポーツニュースに「ワールドカップ」が入る確率
$P(スポーツ)$: ランダムにニュースを選んだ時にスポーツニュースである確率
の積で表せます。同じ式が「社会」カテゴリにも書けます。

分母にある$P("ワールドカップ")$は無視していいのでしょうか？実は分類問題に分母の$P("ワールドカップ")$は関係ありません。なぜかというと、上の「スポーツ」を「社会」に置き換えても、分母は変わらず、$P(スポーツ|"ワールドカップ")$と$P(社会|"ワールドカップ")$の大小比較に影響を与えないからです。

右辺にある、$P("ワールドカップ"|スポーツ)$と$P(スポーツ)$は学習用のデータから計算できます。例えば最初に出した例でいうと、それぞれ$2/5$と$5/10$ですので、積は$1/5$です。逆に、$P("ワールドカップ"|社会)=0/5$、$P(社会)=5/10$なので、積は$0$となり、スポーツニュースである確率の方が高いという結論になりました。

##ラプラススムージング
大層な名前がついていますが、この節で説明する内容はシンプルです。
上の計算で、$P("ワールドカップ"|社会)=0$という計算をしましたが、確率の掛け算で$0$が一度出てきてしまうと他が何であっても答えが$0$になってしまい、不便です。そこまでではないですが、確率が$1$なのも、世の中に「絶対」があると言っているようなものなので、若干気持ち悪いです。

そこで、学習用データから条件付確率の計算をするときに、(約分前に)分母に2、分子に1を足そうというのがラプラススムージングのアイデアです。こうすると、

```math
P("ワールドカップ"|スポーツ)=\frac{2+1}{5+2} = \frac{3}{7} \\
P("ワールドカップ"|社会)=\frac{0+1}{5+2} = \frac{1}{7} 
```
のように計算できて、確率が$0$になる問題を回避できました。

##ナイーブベイズ
###ナイーブベイズとは何か
実際の文章には、単語が複数含まれています。例えば、「ワールドカップ」という単語が含まれていればスポーツニュースっぽい、「立候補」という単語が含まれていれば政治、社会のニュースっぽいという判断ができますが、「ワールドカップに立候補」という文章も考えられます。単語を$w$で書いて、$w_1$と$w_2$が両方含まれている文章の分類を考えましょう。素直にベイズの定理を使って書くと、$C$をカテゴリとして

```math
P(C|w_1 \land w_2) \propto L(C|w_1 \land w_2) = P(w_1 \land w_2|C)P(C)
```
となります。ちなみに、右辺の分母は先ほど説明したように関係ないので省略して尤度$L$を定義しました。

しかしこの方法には問題があります、$P(w_1 \land w_2|C)$というのはあるカテゴリの文章に$w_1$と$w_2$が両方同時に含まれている確率ですが、実用的にはこれをすべての組み合わせについて計算するのは面倒です。例えば100万種類の単語があると、2種類の単語の組み合わせだけで2乗になって兆に近い桁の組み合わせがあり得ます。しかも、実際の文章には単語が2個ということはないでしょう。すると、3種類なら3乗、4種類なら4乗となって、指数関数的に増えていってしまいます。
そこで、ナイーブベイズという方法では、

```math
 P(w_1 \land w_2|C) = P(w_1|C)P(w_2|C)
```
という<b>仮定</b>を置いて計算します(各単語が出現する条件付確率は独立)。これがナイーブ(単純)と呼ばれる所以です。

さらに拡張を考えましょう。もしかすると、「ある単語が入っていない」ということも情報かもしれません。なので、これまでは入っている単語だけに注目して「ある単語が入っている条件下での条件付確率」を見てきましたが、「$w_1$と$w_2$は入っているが$w_3$は入っていない」という条件を考えてもいいでしょう。この場合、

```math
 P(w_1 \land w_2 \land \lnot w_3|C) = P(w_1|C)P(w_2|C)P(\lnot w_3|C)
```
と同様に計算することになります。$\lnot$というのは否定を表す記号です。

###コーパス
学習用データから単語を集めたものを「コーパス(辞書)」と呼びます。例えば、今回の学習用データからは、「フランス、が、ワールドカップ、優勝、メッシ、の、得点、で、・・・」というコーパスが得られます。

しかし、このコーパスを使って文章の分類を行うには問題があります。最も大きいのは<b>ストップワード</b>の問題です。ストップワードというのは、どんな文章にも出てくるありふれた単語で、「が、は、です、ます」のような助詞や「私、あなた」のような代名詞が思いつきます。英語では"a"や"the"のような冠詞も入ります。こういった単語を文章の分類の情報として利用することにあまり価値がないことは想像に難くないのではないでしょうか。

ちなみになお、ストップワードを除いてもなお、コーパスは膨大になってしまいます。コーパスにN=100万の単語があると、ある文章(例えば$w_1,w_2$が入っていて他が入っていないとします)が与えられたときに

```math
 P(C|文章) \propto L(C|文章) = P(C)P(w_1|C)P(w_2|C)P(\lnot w_3|C)P(\lnot w_4|C)\cdots P(\lnot w_N|C)
```
を計算しなければなりません。100万項の掛け算はそれなりに大変な計算です。そこで、各カテゴリに特徴的な言葉(「ワールドカップ」「メッシ」「得点」など)を選んできて、それらだけでコーパスを構成することで計算量を削減する工夫も可能です。

また、実際に$ P(C|文章)$を計算する際に、掛け算をたくさん計算すると、あまりにも小さい数になってしまうことが懸念されます。そこで対数を取ることで、

```math
\log L(C|文章) = \log P(C)+\log P(w_1|C)+\log P(w_2|C) + \cdots
```
と計算して大小関係を比較することでこの問題を避けられます。

##ニュースの分類
さて、実際に最初に紹介したニュースを分類してみましょう。(再掲)

|番号|ヘッドライン|ジャンル|
|---|---|---|
|1|フランスがワールドカップ優勝|スポーツ|
|2|メッシの得点でバルセロナ勝利|スポーツ|
|3|東京オリンピック延期へ|スポーツ|
|4|日本、ワールドカップ招致に立候補|スポーツ|
|5|巨人、坂本の感染を確認|スポーツ|
|6|政府、入国制限の緩和を検討|社会|
|7|東京の感染が落ち着きを見せる|社会|
|8|小池氏、東京都知事選に立候補か|社会|
|9|フランスがロックダウンを緩和|社会|
|10|バルセロナの観光地が再開|社会|
すべての単語(ストップワード除く)を使ってしまうと計算が大変なので、まず学習データから特徴的な単語を選びましょう。ここでは、「フランス」「東京」「立候補」「感染」「観光地」「ワールドカップ」「オリンピック」「得点」の8つの単語に注目してみます。



すると、まず各カテゴリにおける単語出現の条件付確率はラプラススムージングを使って、

|単語|$P(w &#124; スポーツ)$|$P(\lnot w &#124; スポーツ)$|$P(w &#124; 社会)$|$P(\lnot w &#124; 社会)$|
|---|---|---|---|---|
|フランス|2/7|5/7|2/7|5/7|
|東京|2/7|5/7|3/7|4/7|
|立候補|2/7|5/7|2/7|5/7|
|感染|2/7|5/7|2/7|5/7|
|観光地|1/7|6/7|2/7|5/7|
|ワールドカップ|3/7|4/7|1/7|6/7|
|オリンピック|2/7|5/7|1/7|6/7|
|得点|2/7|5/7|1/7|6/7|
となります。

ここから次のニュースのカテゴリを予測してみましょう。

|番号|ヘッドライン|
|---|---|
|11|ワールドカップに向け感染警戒|
|12|東京の観光地、閑散とした週末|
|13|フランス大統領選の立候補者出そろう|

まず「ワールドカップに向け感染警戒」は、スポーツの話である尤度は

```math
\begin{align}
&L(スポーツ|「ワールドカップに向け感染警戒」)\\
 &= P(スポーツ) P(\lnot フランス|スポーツ) P(\lnot 東京|スポーツ) P(\lnot 立候補|スポーツ) P(感染|スポーツ) P(\lnot 観光地|スポーツ) P(ワールドカップ|スポーツ) P(\lnot オリンピック|スポーツ) P(\lnot 得点|スポーツ) \\
&= \frac{5}{10} \times \frac{5}{7} \times \frac{5}{7} \times \frac{5}{7} \times \frac{2}{7} \times\frac{6}{7}\times \frac{4}{7} \times \frac{4}{7} \times \frac{5}{7} \\
&=0.0104
\end{align}
```
一方、社会の話である尤度は、

```math
\begin{align}
&L(社会|「ワールドカップに向け感染警戒」)\\
 &= P(社会) P(\lnot フランス|社会) P(\lnot 東京|社会) P(\lnot 立候補|社会) P(感染|社会) P(\lnot 観光地|社会) P(ワールドカップ|社会) P(\lnot オリンピック|社会) P(\lnot 得点|社会) \\
&= \frac{5}{10} \times \frac{5}{7} \times \frac{4}{7} \times \frac{5}{7} \times \frac{2}{7} \times \frac{5}{7} \times \frac{1}{7} \times \frac{6}{7} \times \frac{6}{7} \\
&=0.0031
\end{align}
```
となり、$L(スポーツ|「ワールドカップに向け感染警戒」)>L(社会|「ワールドカップに向け感染警戒」)$なので、これはスポーツの話であると分類されました。
他の例についての計算は~~面倒なので~~割愛しますので、ぜひ手を動かしてみてください。

今回は注目する単語を恣意的(なんとなくジャンルに関連しそうな単語)で選びましたが、実際にはすべての単語とカテゴリで$P(単語|カテゴリ)$を計算してから、この値がカテゴリごとに大きく異なる単語を抽出します。今回でいうと「ワールドカップ」がそれにあたります。実際、「フランス」という単語などは$P(フランス|スポーツ)=P(フランス|社会)$なので、判別のために何の役にも立っていないことに注目してください。

##まとめ
今回は文章の分類の方法を紹介しました。今回の例題ではスポーツと社会の分類問題でしたが、これはカテゴリが3つ以上であっても方法は同じで、$P(カテゴリ|文章)$が最大となるカテゴリに文章を分類すればいいです。

もっとも有名なナイーブベイズの適用はメールのスパムフィルターで、「振込」「登録」などのキーワードで迷惑メールを見分けて(いると言われて)います。