言語処理のための機械学習入門第1章まとめ

前から自然言語処理を勉強したいなと思っていたので今回この本を読んでまとめてみます。

https://www.amazon.co.jp/dp/4339027510

最適化問題

最適化問題とはある制約の下で関数を最適化する変数値とその関数値を求める問題である。

例：次の最大化問題を解け（ただしaは定数）

max. $-x_1x_2$
s.t. $x_1-x_2 -a =0$

この例題では$-x_1x_2$という関数を最大化した。このように最適化したい関数をこの最適化問題の目的関数という。また最適値を与える変数値を最適解という。

一般的に最適化問題は次のように書かれる ：

max. $f(x)$
s.t. $g(x)\geq 0$
$h(x)=0$
「s.t.」いかに制約を記述するのが一般的である。
制約を満たす解のことを実行可能解という。また実行可能解の集合を実行可能領域という。

上の例題では$x_1=a/2, x_2=-a/2$が最適解であるが、このように「$x_1=$」のような解の表し方を閉形式という。全ての問題について閉経式の解が得られるわけではない。閉形式の解が得られる問題を解析的に解ける問題という。

凸計画問題

これ以降の部分では最適化問題の中の凸計画問題と呼ばれる問題を取り扱う。 凸計画問題とは大雑把に言うと目的関数の値が改善する方向に進んで行けば解にたどり着く、それゆえ凸計画問題は比較的解き易い問題であり、その解法はある程度確立している。 つまり解きたい問題を凸計画問題で表すことに成功すれば問題解決に向けて大躍進したことになる

凸集合と凸関数

凸集合とは直感的に言えばへこみのない集合である。 数式による厳密な定義と図はめんどうなので割愛するが、もう少し厳密にいうと、集合内の任意の点を結ぶ線分が集合自身からはみ出ないことが凸集合である条件となる。
さらに、平面だけでなく、半空間も凸集合となる。

次に関数に対して凸性という概念を導入する。
こちらも大雑把にいうと、上に凸な関数とは、$f(x)=-x^2$のように上に出っ張っている関数である。
もう少し厳密に言うとある関数が上に凸であるとはこの関数を表すグラフ上の任意の点を結ぶ線分が常にグラフの下側もしくは同じ高さにあることを言う。

凸計画問題

ある最適化問題が凸計画問題であるとはその目的関数が凸関数であってかつ実行可能領域が凸集合であることを言う。 例えば、
max. $-x_1^2-x_2^2$
s.t. $x_1-x_2-a=0$

は凸計画問題である。
AとBが凸集合でもAまたはBは凸集合とは限らないが、Aでの最適解、Bでの最適解をそれぞれ求め、それらの良いほうを選べば、AまたはBでの最適解が求められる。

まず、変数のとりうる範囲について特に制約がない場合は非常に素直な問題であり、微分して0になる点を求めれば良い。
閉形式で解が求まらない場合は、再急勾配法やニュートン法といった、なんらかの初期値を与えて徐々に良い解へと更新していくような解法が用いられる。このような解法を数値解法と呼ぶ。

等式制約付凸計画問題

次に等式制約がある場合を考える。目的関数は$f(x)$でこれを最大化したいとする。しかし今回は、$g(x)=0$という条件を満たす解でなくてはならない。
偏微分が0になる点がたまたま制約を満たしていればよいが、一般的にそれは期待できない。そのため、基本的な戦略として制約を明示的に考えなくてもよい形にもっていく。

ここで、変数$\lambda$を導入し、次のような関数$L(x, \lambda)$を定義する。

$L(x, \lambda)=f(x)+\lambda g(x)$

この関数をラグランジュ関数と呼び、この変数をラグランジュ乗数と呼ぶ。この関数$L(x, \lambda)$の$x$に関する偏微分が0となり、かつ与えられた制約が満たされるとき、最適な解が得られることが知られている。つまり、

$$∇xf(x)+\lambda \nabla_x g(x)=0 \\ g(x)=0$$

という連立方程式を解くことになる。このようにして最適点を求める手法を、ラグランジュの未定乗数法と呼ぶ。

不等式制約付き凸計画問題

以下のように制約が不等式で与えられる場合を考える。
max. $f(x)$
s.t. $g(x)0$

この場合、ラグランジュ関数は、

$$L(x, \lambda)=f(x)+\lambda g(x)$$

であり、等式制約の場合と同じだが、$\lambda \geq 0$という条件がつく。

ラグランジュ関数$L(x, \lambda)$について、つぎのような不等式を満たすような点$(x*, *)$が存在するとき、この点をLの鞍点という。

$$L(x,\lambda^*) \leq L(x^*,\lambda^*) \leq L(x^*,\lambda)$$

鞍点とは、$x$に関して最大値となり、に関しては最小値となるような点である。
凸計画問題においては鞍点$L(x^*,\lambda^*)$が最適解を与えることが知られている。
鞍点を求めるためには、まず$L(x, \lambda)$を最大化する$x$を求める。一般にそのような$x$は$\lambda$に依存するので、$\lambda$に関する式で$x^*(\lambda)$と表され。よって$L(x^*(\lambda),\lambda)$も$\lambda$のみに関する式になる。そのうえで、$L(x^*(\lambda),\lambda)$を$\lambda$について最小化する。そうすると、まず$\lambda^*$が得られ、さらに最適解$x^*$が得られる。
最大化と最小化が入れ替わることに注意。
もともとの問題を主問題と呼ぶのに対して、$L(x^*(\lambda),\lambda)$をについて最小化する問題をその双対問題と呼ぶ。
なぜわざわざに関する最小化問題に書き換えるかというと、双対問題の制約は0のみであり、扱いやすいからである。

確率

基本的なことなのでまとめはスルーします。
内容的には確率変数、期待値、分散、条件付き確率、独立性とか。

代表的な離散確率分布

ベルヌーイ分布

確率$p$で”Yes"、確率$1-p$で”No”と発言する人がいたとするとき、この人の発言一つ一つを確率的に記述するのがベルヌーイ分布である。
ベルヌーイ分布に従う確率変数$X$は、確率$p$で$a$, 確率$1-p$で$b$の値をとるとき確率$P(X=x;p)$は、

$$P(X=x;p)=p^{\delta (x,a)}(1-p)^{1-\delta (x,a)}$$

と表すことができる。ここで$\delta (x,a)$はデルタ関数と呼ばれ、$x=a$のとき1となり、そうでないときに0となる。
ベルヌーイ分布に従う確率変数を要素とするような確率変数ベクトルを作ることにより、多変数ベルヌーイ分布を考えることもできる。

二項分布

ベルヌーイ分布と同様に、確率$p$で”Yes"、確率$1-p$で”No”と発言する人がいたとし、今度はこのひとが$n$回発言したとする。このとき、その$n$回中$x$回が”Yes”である確率を与えるのが二項分布である。

$$P(X=x;p,n)= {}_n C_xp^x(1-p)^{n-x}$$

ベルヌーイ分布と二項分布の場合は”Yes”と”No”の2単語だったが、もっと多くの単語がある状況は多項分布で考えることができる。

連続確率変数

連続確率分布の例

正規分布

おそらく最も有名な連続確率分布

$$P_{gauss}(x;m,\sigma )=\frac{1}{\sqrt{2\pi\sigma^2}}\exp(-\frac{(x-m)^2}{2\sigma^2})$$

ディリクレ分布

言語処理の論文で意外とよく登場するのがディリクレ分布である。
ディリクレ分布は$x_i\geq0, \sum_ix_i=1$であるような$x$に対して確率を与える分布である。

$$p(x;\alpha)=\frac{1}{\int\prod_i x_i^{\alpha_i-1}dx}\prod_ix_i^{\alpha_i-1}$$

なぜディリクレ分布が重要かというと、ディリクレ分布の$x_i\geq0, \sum_ix_i=1$という条件は、多項分布のパラメータとなる条件が同一である。つまり、ディリクレ分布は、多項分布のパラメータの確率分布を表すことができ、実際にその目的で利用される。ただし、ある多項分布のパラメータがディリクレ分布に従うとした場合、極端なパラメータ値になりにくいことを仮定している。

パラメータ推定

データが与えられたときに、このデータがある種類の確率分布から生成されたことを知っていたとする。（例えばポアソン分布）
このような状況において、データからパラメータの値を推定することを考える。（例えばポアソン分布のパラメータ$\mu$の値）

i.i.dと尤度

データが独立に同一な確率分布に従っている場合、確率変数$X$のサンプルデータ$D=\{x^{(1)}, ...x^{(N)}\}$の生成確率$P(D)$が、
$$
P(D)=\prod_{x^{(i)}}p(x^{(i)})
$$

とかける。このデータの生成確率は$P(D)$は尤度と呼ばれる。積の形は扱いづらいので、この対数をとった値を用いることが多い。

最尤推定

データ$D=\{x^{(1)}, ...x^{(N)}\}$が与えられたとし、その対数尤度$\log P(D)=\sum_{x^{(i)}\in D}\log p(x^{(i)})$を考える。
最尤推定とは、対数尤度が最も高くなるようにパラメータを決定する方法である。
対数尤度が最も高くなるパラメータは、パラメータに関する偏微分が0になる点を求めれば良い。
パラメータに制約がついている場合には制約付き最適化問題としてラグランジュ未定乗数法を使って解く。

最大事後確率推定

つぎに、パラメータがどんな値を取りやすいかが事前にわかっている場合を考える。
具体的にいうと、パラメータ$\theta$の確率分布$P(\theta)$がわかっているとする。
これをパラメータの事前確認分布と呼ぶ。一方、データ$D$が与えられたときのパラメータ$\theta$の確率分布$P(\theta|D)$を事後確率分布と呼ぶ。
最尤推定では尤度が最も高くなるようにパラメータを決定したが、最大事後確率推定（MAP推定）では事後確率$P(\theta|D)$が最大になるようにパラメータを決定する。
事後確率の最大化は次のように表せる。

$$\begin{aligned} \text{argmax}_{\theta} P(\theta|D) &= \text{argmax}_{\theta}\frac{P(\theta)\cdot P(D|\theta)}{P(D)} \\ &=argmax_\theta P(\theta)\cdot P(D|\theta) \end{aligned}$$

を最大化するようなパラメータ$\theta$を選ぶ。
最尤推定の場合と同様に、積の形は扱いにくいので、一般にはこの値の対数をとった値

$$\log P(\theta)\cdot P(D|\theta) = \log P(\theta)+\sum_{x^{(i)}\in D} \log P(x^{(i)}|\theta)$$

を最大化する。

情報理論

エントロピー

エントロピーは乱雑さを測るための尺度であるといわれる。ここで乱雑であるとは、確率変数がどの値をとるかをいい当てにくい状態をいう。
一般に、離散確率分布$P$に対して、次のような式でエントロピー$H(P)$が定義される。

$$H(P)=\sum_x -P(X=x)\log P(X=x)$$

カルバック・ライブラー・ダイバージェンス

カルバック・ライブラー・ダイバージェンス（KLダイバージェンス）は言語処理にもよく登場する。
KLダイバージェンスは2つの確率分布に対して、それらの間の異なり具合を測るものである。
2つの確率分布$P, Q$が与えられたとき、$P$からみた$Q$のKLダイバージェンス$D_{KL}(P||Q)$はつぎのように計算される。

$$D_{KL}(P||Q)=\sum_x P(X=x)\log \frac{P(X=x)}{Q(X=x)}$$

言語処理では、例えば単語間の意味的な遠さを測るためにKLダイバージェンスを用いる。

ジェンセン・シャノン・ダイバージェンス

KL ダイバージェンスと同じような情報理論をもとにして確率分布間の異なり具合を測る尺度としてジェンセン・シャノン・ダイバージェンス（JSダイバージェンス）というものもある。
JSダイバージェンスは次のように定義される。

$$D_{JS}(P||Q)=\frac{1}{2} D_{KL}(P||R)+D_{KL}(Q||R)$$

ただし、$R$は$R(x)=(P(x)+Q(x))/2$で定義される確率分布である。
KLダイバージェンスで分母が０だと、定義できなくなる。異なる文書間で片方にしか出現しない単語があったりするときに不便であるから、JSダイバージェンスが使われることがある。

自己相互情報量（PMI）

確率変数のある実現値$x$と別の確率変数のある実現値$y$に対して自己相互情報量PMI$(x,y)$はつぎのように定義される。

$$PMI(x,y)=\log \frac{P(x,y)}{P(x)P(y)}$$

$x$と$y$が一緒に出現しやすければPMIは正の値となり、逆であれば負の値となる。
ゆえに、PMIは2つの単語が関連している度合いを測るときなどに用いられる。

相互情報量

2つの確率変数$X$と$Y$に対して、相互情報量MI$(X,Y)$はつぎのように定義される。

$$MI(X,Y)=\sum_{x,y} P(x,y) \log \frac{P(x,y)}{P(x)P(y)}$$

つまり、相互情報量は自己相互情報量の平均であるといえる。