Processing math: 0%
スキップしてメイン コンテンツに移動

MAP推定

Introduction

今日はMAP推定(事後確率最大化法)について書きました。MAP推定ではベイズの定理を使います。データが少ないとき、最尤推定の結果をあまり信用できない話は、最尤推定の時に書きました。この時、MAP推定では自分の事前に持っている情報を取り入れることができます。


概要

  • ベイズの定理
  • MAP推定
  • 共役分布
  • MAP推定の例



ベイズの定理
ベイズの定理は
P(A|B) = \frac{P(B|A)P(A)}{P(B)}
です。

ただし、
P(A|B) はBが起こった時のAの起こる確率です。
詳しくは http://takutori.blogspot.com/2018/04/bayes-theorem.html を見てください。

Map推定
MAP推定ではベイズの定理を使います。MAP推定は事後確率が最大になるようなパラメータを選びます。
いま、x_1,x_2,...,x_nというデータを\thetaというパラメータを持つ分布から得られたとする。この時P(\theta|x_1,x_2,...,x_n)を求めたい。

ここで、ベイズの定理を使う。
P(\theta|x_1,x_2,...,x_n) = \frac{P(x_1,x_2,...,x_n | \theta ) P(\theta)}{P(x_1,x_2,...,x_n)}

ここで、P(\theta)\thetaの事前分布である。

x_1,x_2,...,x_nはそれぞれ独立であるので、
P(x_1,x_2,...,x_n | \theta ) = \Pi_{i=1}^n P(x_i|\theta).

よって、マップ推定は
\theta^{\star} = \arg \max_{\theta} \frac{\Pi_{i=1}^n P(x_i|\theta) P(\theta)}{P(x_1,x_2,...,x_n)}
となる。
P(x_1,x_2,...,x_n)という値は\thetaには依存しない。よって、定数であり、最適化に定数は関係ないので、排除すると、MAP推定は次のようになる。

\theta^{\star} = \arg \max_{\theta}\Pi_{i=1}^n P(x_i|\theta) P(\theta)


共役分布
共役分布とはある便利な分布です。どう便利なのかを簡単に説明します。一般的に事後分布は複雑な形をしている。しかし、共役分布と呼ばれる分布を事前分布に用いることで、事後分布の計算が簡単になる。 事前分布は尤度関数、つまり、 P(x_i|\theta)に依存して決まる。有名な分布に対する共役分布は以下のようになっている。


ABC
1
Conjugate distribution
likelihood
posterior distribution
2
betaBernoullibeta
3
betaBinomialbeta
4
GaussianGaussian(sigma is known)Gaussian
5
inverse gamma
Gaussian(sigma is unknown)
inverse gamma
6
gammaPoissongamma

.

Beta(\theta|a,b) = \frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}\theta^{a-1}(1-\theta)^{b-1}
これはベータ分布と呼ばれる確率分布です。この分布をMAP推定するとき、事前分布にはガンマ分布を使う。ここで、

\Gamma(x) = \int_0^\infty u^{x-1}e^{-u}du
である。

事前分布と尤度関数の積は


P(\theta|D) = P(D|\theta)P(\theta)
=\Pi_{i=1}^{n}\theta^{x_i}(1-\theta)^{1-x_i}\frac{\Gamma(a+b}{\Gamma(a)\Gamma(b)}\theta^{a-1}(1-\theta)^{b-1}
となる。


x_iis 1~or~0であるので、
p(x=1,\theta)p(x=1,\theta)p(x=,\theta) =\theta\theta(1-\theta) .
よって、
\Pi_{i=1}^{n}\theta^{x_i}(1-\theta)^{x_i} = \theta^{\sum_{i=1}^{n}x_i}(1-\theta)^{\sum_{i=1}^{n}(1-x_i)}
P(\theta|D)
P(\theta|D) = \theta^{\sum_{i=1}^{n}x_i}(1-\theta)^{\sum_{i=1}^{n}(1-x_i)}\frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}\theta^{a-1}(1-\theta)^{b-1}
= \frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}\theta^{(\sum_{i=1}^{n}x_i)+a-1}(1-\theta)^{(\sum_{i=1}^{n}(1-x_i))+b-1}
となる。よって、
P(\theta|D) \propto \theta^{(\sum_{i=1}^{n}x_i)+a-1}(1-\theta)^{(\sum_{i=1}^{n}(1-x_i))+b-1}

この最適化は\logを使うことによって、解ける。

\log P(\theta|D) \propto \{(\sum_{i=1}^{n}x_i)+a-1\}\log \theta + \{(\sum_{i=1}^{n}(1-x_i))+b-1\}\log (1-\theta) \nonumber

\sum_{i=1}^{n}x_i + \sum_{i=1}^{n}(1-x_i) = n なので、 最適解は
\theta_{MAP} = \frac{(\sum_{i=!}^{n}x_i)+a-1}{n+a+b-2}


Reference

コメント

このブログの人気の投稿

カーネルk-meansの実装

Introduction   English ver 今日はカーネルk-meansの実装をしました。k-menasアルゴリズムはクラスタリングのためのアルゴリズムです。僕がカーネルk-meansを実装しようと思ったのには一つ理由があります。それは僕の友人がk-meansのプレゼンを、僕がカーネルのプレゼンをしていた時に、k-meansにカーネルを適応できないかと思ったからです。そこで、カーネルk-meansについての論文を探しました。 ここのpdf を主に参考にさせていただきました。うまくカーネルk-meansを実装できたと思います。ここでは、普通のk-meansとカーネルを用いた,kernel k-meansについての実装の結果を紹介します。 また、この記事では実装結果のみ書きますが、理論のほうも別の記事で書くつもりです。書き終えたらリンクをこの記事にも貼っておきます。 #  理論編書きました。K-means 理論編 概要 dataset   ちょっとだけ理論の説明  k-means    kernel k-means   Dataset   English ver 今回使うのは二つのデータセットです。一つ目は、普通のk-means用のデータです。二つ目はkernel k-means用のデータセットです。 一つ目のデータは、三つのグループで構成されており、次元は2で、サンプル数は300です。以下のような分布になっています。 二つ目のデータは二つのグループで構成されており、次元は2でサンプル数は300です。   this page にデータセットを作ったコードを載せています。 ちょっとだけ理論の説明 k-meansとは、k-平均法とも呼ばれています。初めに、適当なクラスに分け、各クラスの中で平均となるベクトルを求めます。そして、各データに対して、すべての平均ベクトルとの距離を求めます。そして、最小となる距離になるクラスに改めて、そのデータをクラスタリングします。そして、新たに得られたクラスの中でそれぞれ平均ベクトルを求め、これを繰り返し、平均ベクトルが動かな...

ダイクストラ法

Introduction English ver 今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this page を見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。 この スライド はダイクストラ法を説明したスライドです。 Overview アルゴリズム 実装 アルゴリズム このアルゴリズムは スタート始点のノードを決める。そして、それをAと名付ける。 各ノードにd=\inftyを割り当てる。ただし、スタート地点はd=0 Aの隣接ノードのリストをadj_listと名付ける。  For adj in adj_list:  If d of adj > d of A + weight to adj -> d = A + weight to adj. グラフnetworkからAを取り除く グラフnetworkの中で最初のdを持っているノードをAとし、4に戻る。 となっています。 このアルゴリズムを図を用いて説明します。  このグラフを使って説明します。  初めに、スタート地点を決めます。そして、各ノードにd=\inftyを割り当てます。  Aから始まります。Aの隣接ノードであるBのdを更新します。もし、現在のBよりもAのdとA->Bへの重みを足したもののほうが小さいならdをその値に更新します。同じようにCnのdを更新します。 次にAを取り除きます。  次はBから始まります。Aと同じことをやります。 このダイクストラ法では今のような操作をグラフの全てのノードに×がつくまで続きます。 実装 このアルゴリズムではO(log(|V|^2))という計算量を持っています。最小のdを持つノードを探すのに時間がかかります。 しかし、ヒープ構造を使えばO((E+V)log(V))に減らせます。ヒープ構造で現時点での...

ヘッセ行列

Introduction English ver 今日は、ヘッセ行列を用いたテイラー展開について書こうと思います。 これは最適化を勉強するにあたって、とても大事になってくるので自分でまとめて残しておくことにしました。とくに、機械学習では最適化を必ず行うため、このブログのタイトルにもマッチした内容だと思います。 . 概要 ヘッセ行列の定義 ベクトルを用いたテイラー展開 関数の最適性 ヘッセ行列の定義 仮定 f は次のような条件を満たす関数です。. f はn次元ベクトルから実数値を出力します。 このベクトルは次のように表せます。 x = [x_1,x_2,,,,x_n] \forall x_i , i \in {1,2,,,n}, f は二回偏微分可能です。 定義 ヘッセ行列は \frac{\partial^2}{\partial x_i \partial x_j}を (i,j)要素に持ちます。 よってヘッセ行列は次のように表せます。 \[ H(f) = \left( \begin{array}{cccc} \frac{\partial^ 2}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & &\ldots \frac{\partial^2 f}{\partial x_1 \partial x_n} \\ \frac{\partial^ 2 f}{\partial x_1 \partial x_2} & \frac{\partial^ 2 f}{\partial x_2^ 2} & \ldots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^ 2 f}{\partial x_n \partial x_2} & \frac{\partial^ 2 f}{\partial x_n \partial x_2} & \ldo...