[WIP]「言語処理のための機械学習入門」"超"まとめ

0. 背景

• 勉強会で、１年かけて「言語処理のための機械学習入門」を読んだので、復習も兼ねて、個人的に振り返りを行いました。その際のメモになります。
• 細かいところまでは書けませんので、大雑把に要点だけになります。詳しくは本をお読みください。あくまでレジュメ、あるいは目次的なものとしてお考え下さい。
• 間違いがある場合は優しくご指摘ください。
• 第１版は間違いも多いので、出来る限り、最新版のご購入をおすすめします。

1. 必要な数学知識

• 基本的な数学知識について説明されている。
• 大学１年生レベルの解析・統計の知識に自信がある人は読み飛ばして良い。

1.2 最適化問題

• ある制約のもとで関数を最大化・最小化した場合の変数値や関数値を求める問題。
• 言語処理の場合、多くは凸計画問題となる。
  • 解析的に解けない場合は数値解法もある。
    • 数値解法として、最急勾配法、ニュートン法などが紹介されている。
• 最適化問題を解く方法として有名な、ラグランジュ乗数法の説明がある。この後も何度も出てくるので重要！
  • とりあえずやり方だけ覚えておくだけでもOKだと思う。

1.3 確率

• 条件付き確率
  • $Y=y$の場合の、$X=x$となる確率

P(X=x|Y=y) = P(x|y)

　　（右辺は省略して表記）

• 「$y$と$x$が同時に起こる」確率は、「$y$が起こって、さらに$y$が起こったという条件のもとで$x$が起こる」ということから

P(x,y) = P(x|y)P(y)

　　が成り立つ。

• 複数ある場合

P(x_1,x_2|x_3) = P(x_1|x_2,x_3)P(x_2|x_3)

• 数を増やして

\begin{align}
P(x_1,x_2,...,x_n|y) &= P(x_1|x_2,...,x_n,y)P(x_2|x_3,...,x_n,y) \\
&= \cdots \\
&= P(x_1|x_2,...,x_n,y)P(x_2|x_3,...,x_n,y)\cdots P(x_n|y) \\
\end{align}

• また、$x_1,...,x_n$が互いに独立の場合、$P(x_i|x_1,…,x_{i−1},x_{i+1},…,x_n,y) = P(x_i|y)$なので、

\begin{align}
P(x_1,x_2,...,x_n|y) &= P(x_1|y)P(x_2|y)\cdots P(x_n|y) \\
&= \Pi_{k=1}^{n}P(x_k|y)
\end{align}

• ベイズの定理（これもよく出てくるので重要）

P(y|x) = \frac{P(y)P(x|y)}{P(x)}

• 代表的な離散分布
  • ベルヌーイ分布
  • 多変数ベルヌーイ分布
  • 二項分布
  • 多項分布
  • ポアソン分布

1.4 連続確率変数

• 連続確率分布の例
  • 正規分布（ガウス分布）
  • ディレクレ分布
    • 各値が互いに近い場合、比較的高い確率を持ち、各値が離れている（偏っている）場合には非常に低い確率を持つ分布。
    • 最大事後確率推定（MAP推定）でパラメータがとる確率分布として仮定されることがある。

p(\boldsymbol{x};\alpha) = \frac{1}{\int \prod_i x_i^{\alpha_i-1}d\boldsymbol{x}} \prod_{i} x_i^{\alpha_i-1}

1.5 パラメータ推定法

• データが与えられ、このデータに従う確率分布を求めたい。何も手がかりがないと定式化できないので、大抵は何らかの確率分布を仮定する。離散確率分布ならベルヌーイ分布や多項分布、連続確率分布なら正規分布やポアソン分布などなど。これらの分布にはパラメータがあるので、確率分布が学習するデータにもっともフィットするように、パラメータを調整する必要がある。これがパラメータ推定。
• （補足）コメントにて、$P$と$p$の違いが分かりにくいというご指摘をいただきましたので、補足します。ここの章では、尤度を$P(D)$で、仮定する確率関数（ポアソン分布、ベルヌーイ分布等）を$p(\boldsymbol{x})$で表しています。

1.5.1. i.i.d.と尤度

• i.i.d.とは独立に同一の確率分布に従うデータ。つまり、サンプルデータ$D= { x^{(1)},・・・,x^{(N)} }$の生成確率$P(D)$（尤度）は確率分布関数$p$を用いて

P(D) = \prod_{x^{(i)}\in D} p(x^{(i)})

　と書ける。

• $p(x^{(i)})$にベルヌーイ分布や多項分布などを仮定する。この時点ではまだパラメータが残っている。（ベルヌーイ分布の$p$、正規分布の$\sigma$、ポアソン分布の$\mu$など）
• $P(D)$が最大となるようにパラメーターを決めたい。
• 積の形は扱いにくいので対数を取る。（対数尤度）

1.5.2. 最尤推定

• 対数尤度が最も高くなるようにパラメータを決定。
• 対数尤度$\log P(D) = \sum_x n_x\log p(x)$を最大化。
  • ここで$n_x$は$x$がD中で出現した回数を表す。

1.5.3 最大事後確率推定（MAP推定）

• 最尤推定で、パラメータが事前にどんな値をとりやすいか分かっている場合の方法。
• 事前確率も考慮し、$\log P(D) = \log P(\boldsymbol{p}) + \sum_x n_x\log p(x)$を最大化。
• ディリクレ分布を事前分布に仮定すると、最尤推定の場合と比較して、各パラメータの値が少しずつマイルドになる（互いに近づきあう）
• 最尤推定・MAP推定は４章. 分類で出てくるので重要！

1.5.2， 1.5.3の補足 最尤推定の簡単な例（本書とは無関係）

• （例）あるコインを5回投げたとして、裏、表、裏、表、表と出ました。このコインの表が出る確率をpとして、pを推定せよ。
• （解答例）単純に考えて、５回投げて３回表が出るのだから、$p = 3/5$である。これを最尤推定を用いて推定する。尤度$P(D)$は

\begin{align}
P(D) &= (1 - p) \times p \times (1-p) \times  p \times p \\
&= p^3(1-p)^2
\end{align}

• $P(D) = p^3(1-p)^2$が0から1の間で最大となるpを求めれば良い。
• そのまま微分すると$dP(D)/dp = p^2(5p^2 - 8p + 3)$
• 計算が大変なので対数をとれば$log(P(D)) = 3logp + 2log(1-p)$となり、計算がしやすくなる。

2. 文書および単語の数学的表現

• 基本的に読み物。
• 語句の定義や言語処理に関する説明なので難しい数式はない章。
• 勉強会では唯一１回で終わった章。

3. クラスタリング

3.2 凝集型クラスタリング

• ボトムアップクラスタリングとも言われる。
• もっとも似ている事例同士を同じクラスタとする。
• 類似度を測る方法
  • 単連結法
  • 完全連結法
  • 重心法

3.3 k-平均法

• みんな大好きk-means
• 大雑把な流れ
  • ３つにクラスタリングしたいのであれば、最初に適当に３点（クラスタの代表点）とって、各事例がどのクラスタに属するかを決める。（類似度が最も近い代表点のクラスタに属するとする）
  • クラスタの代表点を再計算する（重心をとるなど）
  • 再度各事例がどのクラスタに属するかを計算する。
  • 何回かやるとクラスタに変化がなくなるのでクラスタリング終わり。
• 最初の代表点の取り方によって結果が変わりうる。

3.4 混合正規分布によるクラスタリング

• k-平均法では、事例が属するクラスタは定まっていた。しかし、クラスタの中間付近に存在するような事例においては、代表点との微妙な距離の違いでどちらかに分けられてしまう。混合正規分布によるクラスタリングでは、確率的に所属するクラスタを決める。
• 例えば、ある事例はAというクラスタに20%の確率で属し、Bというクラスタに80%の確率で属する・・など。

3.5 EMアルゴリズム

• （追記予定）

4. 分類

• クラスタリングはどんなクラスタができるかは事前にはわからない。
• 分類はあらかじめ決まったグループ(クラス)に分けることを分類(classification, categorization)と呼ぶ。クラスタリングと分類は異なる意味なので注意する。
  • 例) 単語を名詞・動詞・形容詞などの品詞に分類する
• ここでの目的はデータから自動的に分類気を構築する方法。
• つまり、ラベル付きデータ
  D = {(d⁽¹⁾, c⁽¹⁾), (d⁽²⁾, c⁽²⁾),・・・,(d^(|D|), c^(|D|))}
  が与えられている必要がある。（教師付き学習)
• 一方、クラスタリングのようにラベルなしデータを用いて行う学習を教師無し学習とよぶ。

4.2 ナイーブベイズ分類器

• $P(c|d)$を求めたい。
• $P(c|d)$とは、文書$d$の場合、クラスがcである確率を意味する。すなわち、クラスが$c^{(1)}, c^{(2)}, c^{(3)}$の3種類あった場合に、$P(c^{(1)}|d)$, $P(c^{(2)}|d)$, $P(c^{(3)}|d)$をそれぞれ求め、文書dは確率が一番大きかったクラスに分類されることになる。
• ベイズの定理より、 $$ P(c|d) = \frac{P(c)P(d|c)}{P(d)} $$
• この値が最大となるクラスcを求めるわけだが、分母のP(d)はクラスcに依存しないので、$P(c)P(d|c)$を最大にするようなcを求めれば良い。
• $P(d|c)$は容易には計算できないので、文書dに簡単化したモデルを仮定して$P(d|c)$の値を求める

4.2.1 多変数ベルヌーイモデル

• ベルヌーイ分布において、クラスcが与えられている時に各単語wが生起するかどうかを表す確率は

p_{w,c}^{\delta_{w,d}} (1-p_{w,c})^{1-{\delta_{w,d}}}

　であるので、文書dの生起確率P(d|c)は、

P(d|c) = \prod_{w\in V} p_{w,c}^{\delta_{w,d}} (1-p_{w,c})^{1-{\delta_{w,d}}}

　と表せる。したがって、

P(c)P(d|c) = p_c \prod_{w\in V} p_{w,c}^{\delta_{w,d}} (1-p_{w,c})^{1-{\delta_{w,d}}}

　を最大化するようなcを求めれば良い。このような形を仮定すればP(d|c)は計算できる。

• ラベル付きデータDの生成確率にベルヌーイ分布を仮定し、最尤推定を用いてパラメータ$p_c$、$p_{w,c}$を求めることで、分類器$P(c|d)$を導くことができる。
• 最尤推定では、訓練データにたまたま素性が出現しないと確率を0として計算してしまうため、予測がおかしくなる場合がある。
• そこでパラメータに事前分布を与えることで0にならないようにする。（例えばディリクレ分布を仮定）
• パラメータに事前分布を仮定するので、これは最大事後確率推定(MAP推定)である。

4.2.2. 多項モデル

• ベルヌーイ分布ではなく、多項分布を仮定する方法。
• 多変数ベルヌーイモデルでは単語が文書内に出現したか否かだけを考慮。多項モデルでは、文書内の単語の生起回数を考慮するという違いがある。
• 同様に一部のパラメータが0になることで予測がおかしくなるので、パラメータにディリクレ分布を仮定してMAP推定を用いることもできる。

4.3 サポートベクトルマシン（SVM）

• 線形二値分類器。分類平面を求め、区切る。
• 分離平面が存在した場合、訓練データを分類できる分離平面は複数存在するが、分離平面から一番近いデータがどちらのクラスからもなるべく遠い位置で分けるように定める（マージン最大化）。
• 厳密制約下では例外的な事例に対応できない。そこで、制約を少し緩める（緩和制約下のSVMモデル）。

4.4 カーネル法

• SVMで重要なのは結局内積の形。
• 内積だけを用いて計算をすれば良い（カーネル法）。
• カーネル関数を用いる。何種類かある。
• カーネル関数を用いると計算量の増加を抑えることができ、非線形の分類が可能となる。

4.5 対数線形モデル

• 素性表現を拡張して事例とラベルの組に対して素性を定義する。
• （追記予定）