この記事は Retty Advent Calendar 12日目の記事です。
昨日はのりPさん(@noripi)のKotlinで論理回路を実装して遊ぶでした。
こんにちはみなさん、RettyのVBA担当こと@RyosukeMuraiです。
VBAはベジタリアンベーコンアボカドの略です。
普段はテキストを書いたりしないのでこの記事はMRKだと思います。
MRKはMaji Rare Kijiの略です。
さて、RettyのiPhoneアプリはDNAコンピュータで実装、ビルドしています。
今回は五反田ランチの検索フィルターを、アデニンとチミンの水素結合を使って実装したところ、AppleStoreからリジェクトを食らったお話です。
嘘です。
今回は、お店検索のアルゴリズムにベイジアンフィルターを適用した時のお話です。
これはマジですが、Rettyではアルゴリズムの実装時に数理的な証明が求められる場合があります。
今後の幅広い展開を見据え、よりスケーラブルなシステムを構築していく上での文化です。
@RyosukeMurai は数学よりは古典の方がマシ、古典よりは昼寝の方が好きな人間だったので、この文化はマジキチだと思っていますが、これも時代の流れと思って絶賛勉強中です。
以下、簡単に適用した時の背景と、ベイジアンフィルターの説明を書いていきます。
ベイジアンフィルターを適用した背景
Rettyではお店の検索ワードが与えられた時に、類似したお店をサジェストする機能があります。
これまでそういった機能はルールベースなアルゴリズムを作っていたのですが、
投稿していただくユーザーさんが全国的に増加しており、手作りのルールでは網羅性・汎用性に難が出てきました。
そこで、試験導入としてベイジアンフィルターを適用してみようという話になりました。
用語整理
この記事で登場する単語を簡単に整理しておきます。
- キーワード
- ユーザーさんに入力いただいたキーワード。このワードを元にサジェスト候補を抽出する。
- サジェストリスト
- 特定のキーワードに沿って抽出された、サジェスト対象に最適なお店群。
- １つのキーワードに3~10件のお店候補を抽出。
- 切り口
- キーワードをザックリ分類するカテゴリ。
- デート、合コン、女子会、観光などの切り口が存在する。
単純ベイズ分類器（ベイジアンフィルター）とは
ナイーブベイズ（Naive Bayes）というアルゴリズムを利用して、テキストの自動分類などに応用することのできるフィルタの総称。
ナイーブベイズには、ベイズの定理という条件付き確率の定理が前提になっています。
ベイズの定理とは
ベイズの定理とは、条件付き確率密度関数における式の変換。
P(B|A)×P(A) = P(A|B)×P(B)
条件付き確率とは
条件付き確率とは、確率の計算で、事象Aが起こったという条件のもとに考えます事象Bの確率は、AのもとでのBが起こる条件つき確率といわれ、記号で$P(B|A)$と書かれます。
つまり、ある事象Aが起っている上で、さらに事象Bの起こる事象A∩Bの割合を求めるものです。以下に考え方を示します。
すべての場合のうちAが起こる確率$P(A)$は
P(A)=\frac{Aが起こる場合の数} {起こりうる全ての場合の数}
です。
すべての場合のうちAが起こりかつBも起こる同時確率$P(A∩B)$は
P(A∩B)=\frac{A∩B} {起こりうる全ての場合の数}
です。
ここで、Aが起こった上でかつBが起こる条件付き確率$P(B|A)$は、
Aが発生する確率$P(A)$のうち、AかつBが発生する確率$P(A∩B)$ですから、
P(B|A) = \frac{P(A∩B)}{P(A)} \\
と表現できます。これが条件付き確率の考え方です。
同時確率
ここでAとBが同時に起こる確率$P(A∩B)$について考えます。
先ほどの式を変形すると、
P(A∩B) = P(B|A)×P(A)
ですから、Aの起こる確率とAのもとBが起こる確率がわかっているとき、AかつBの確率=同時確率を導けます。
条件付き確率とベイズの定理
ここまでの考えを踏まえ、逆にBのもとAが起こる条件付き確率を考えるのが、ベイズの定理です。
まず、BのもとでのAが起こる条件つき確率$P(A|B)$は
P(A|B)=\frac{P(B∩A)}{P(B)}
です。
式を変形すると
P(B∩A)=P(A|B)×P(B)
であり、ここで、$P(B∩A) = P(A∩B)$なので、
P(A|B)×P(B) =P(B|A)×P(A)
です。
左辺から$P(A|B)$を取り除くと
P(A|B) =\frac{P(B|A)×P(A)}{P(B)}
これがベイズの定理です。
ナイーブベイズの適用
以下にナイーブベイズをどう適用するか考えます。
本プロジェクトでは、あるレストランが、特定の切り口にふさわしいかどうか分類します。
以降、レストランを文書、切り口をカテゴリと一般化して考えます。
ナイーブベイズにおいてのカテゴリの推定は、ある文書が与えられた時にその文書がどのカテゴリに属するのが「もっともらしいか」を単語の出現確率から求めます。
今回は文書$（doc）$が与えられた時、カテゴリ$（cat）$に属する確率$P(cat|doc)$を求める。前述のベイズの定理を用い、下記の式で表現します。
P(cat|doc) = \frac{P(doc|cat)P(cat)}{P(doc)}
すべてのカテゴリに対し確率$P(cat|doc)$を求め、その確率が最も大きいカテゴリに分類します。
さて、今回知りたいのは各カテゴリ間の確率の大小関係です。
分母の$P(doc)$はすべてのカテゴリ間で共通であるため、大小関係に影響しない。よって、ナイーブベイズのアルゴリズムでは不要になります。
したがって、求める式は
P(cat|doc) ≈ P(doc|cat)P(cat)
となる。
まず、$P(cat)$について考えます。
これは単純に、全てのカテゴリの中でcatに該当する確率を求めればよいです。
サジェストリストを例に考えますと、下記の通り。
イタリアンデートのサジェストリスト = {吉田商店,pizzaliatsuko}
フレンチのサジェストリスト = {ブラッスリーKondo,ビストロ・ノグチ,レストラン・洋,ブラッスリー江坂}
という分類があったとすると、イタリアンデートのサジェストリストに分類される確率は
\begin{align*}
P(イタリアンデートのサジェストリスト) &= \frac{イタリアンデートに分類された数}{お店の総数} \\
&=\frac{2}{6}
\end{align*}
となります。
次に$P(doc|cat)$を考えます。
これは、$cat$に分類されたすべての文書のうち、$doc$に該当する確率です。
$doc$に該当するという条件を文書の完全一致としてしまうと、1文字でも異なると該当しなくなってしまう。そこで、文章を単語に分解して考えます。
$cat$に含まれる全文書中の全単語のうち、$doc$内の全単語がすべて同時に存在する確率を求める。その値を$cat$が与えられた時に$doc$に該当する確率とみなして考えます。
P(doc|cat)≈∏_{i}P(word_{i}|cat)
イメージとしては、下記の通り。
- カテゴリを一つの箱とみなす
- その箱の中にカテゴリ内のすべての文書の単語をバラバラにしていれる
- すべてのカテゴリについて同様の箱を準備する
- 分類したい文書の単語をすべてバラバラにする
- 一つのカテゴリの箱からランダムに1単語取り出す
- 4でバラバラにした単語をすべて取り出すまで、5を繰り返す
- 1~6をすべてのカテゴリの箱に対して行ったとき、各カテゴリごとに何回施行すればすべての単語を取り出せるか
$doc$と同じような単語が多く使われている文書が含まれているカテゴリ（箱）のほうが、ヒット率が高くなることから、この確率を$P(doc|cat)$の近似と考えます。
この考え方は文書の単語に限定しているので、多くの情報が失われています。そこが、ナイーブベイズのナイーブと呼ばれる所以です。
ベイジアンフィルターでは、これを用いて事後確率がもっとも高いカテゴリへ分類します。（MAP推定といいます）
上記を整理し、数式として表現すると下記の通り。
\begin{align*}
cat_{map} &=argmax_{cat}P(cat|doc)\\
& = argmax_{cat}P(cat)∏_{i}P(word_{i}|cat)
\end{align*}
argmaxf(x)はf(x)が最大になるようなxを返すという意味です。
この式を使うことで、$doc$が与えられたときに適切な$cat$を推論することができます。
参考にさせていただいた記事
いつも勉強させていただいております。ありがとうございます。
まとめ
いかがでしたでしょうか？
ちなみに$Σ$と$∏$はスライドに入れておくだけでグッと偉そうになる魔法のツールです。Rettyではシグマ理論と親しみを込めて呼ばれています。
この記事に触れた方が、Rettyで数学やりたい！と思っていただければ幸いです。
もちろんRettyではぼくのような数学より昼寝派エンジニアも絶賛募集中です。
みんなで解の公式からはじめましょう！
それでは。