スキップしてメイン コンテンツに移動

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_i$is $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
Labels:

コメント

コメントを投稿

このブログの人気の投稿

Implementation of Robbins monro

Robbins monro の実装 sorry, this page is Japanese only.   今回はRobbins monro の実装をしてみました。 Robbins monroは確率勾配降下法の学習率を入りテーション回数の逆数で割っていくものです。 使っているprogram言語はpython 3です。osはwindowsです。(macほしい...) アルゴリズム 確率勾配降下方とは目的関数の最適解を求めるアルゴリズムです。目的関数をf(X)とすると、手順は以下のようになっています。 初期学習率$n_0$を決めます。訓練データDを用意します。この訓練データは複数の初期値の集まりです。 訓練データから一つ初期値をランダムに取り出し、これを$x_0$とし、最初の予測値とします。 次の式に現在の予測値$x_0$を代入し、新たな予測値$x_{n+1}$を得ます。$$x_{n+1} = x_{n} - \frac{n_0}{n} grad f(X_n)$$ 収束して入れば4へ、収束していなければ2で得られた値$x{n+1}$を新たに$x_n$としてもう一度2を行う。 訓練データを一周していなければ2へ、一周していれば各初期値から得られた解の中から目的関数を最も小さくするものを選ぶ。　　 実装例 以下の目的関数を最小化させてみましょう。 $$f(x,y) = (x-2)^2 + (y-3)^2 $$ コマンドラインでpythonを実行していきます。 予想通り、（２，３）という解を導き出してくれました。目的関数が簡単だったので、初期値をどの値でとってもばっちり正解にたどり着いてくれました。 CODE 以下にRobbins monroの関数だけ置いておきます。 こちら にすべてのコードを載せています。 def Robbins_monro(function,grad,number_variable_gradient): init_learning_rate = 1.5 stepsize = 1000 init_value = np.array([range(-1000,1020,20) for i in range(number_v...
コメントを投稿
続きを読む

ダイクストラ法

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))に減らせます。ヒープ構造で現時点での...
コメントを投稿
続きを読む

大学院試験　-外部への道しるべ-

始めに この度、 京都大学大学院情報学研究科システム科学専攻 に合格することができました！！！ 僕は現在、立命館大学という関西の私立大学に通っているので、外部受験をしたことになります。 さらに、学部は数学専攻で、大学院からは情報学(の中でも機械学習)専攻になるので、専門も変えることになります。 この記事では、外部の大学院、もしくは専攻替えを考えている人向けに書こうと思っているので、目次で気になった項目があれば、ぜひ、読んでいってくださいませ。( *´艸｀) ちなみに、予測点数は線形微積6~7割、専門科目満点、英語かなり低いので内緒です。（笑） 得点開示を要求するので、得点がわかったら、また追記します。 目次 外部受験を目指すまで、目指したきっかけ 外部受検の大変さ 専攻替えの大変さ 合格するために 英語が苦手な人へ 数学科の学部から情報学(機械学習)の大学院を目指す人へ 応援 外部受検を目指すまで、目指したきっかけ ここでは、自分の大学生活がどんなだったかを書いてるだけなので、興味のない人は飛ばしましょう。（笑） 僕が学部二回生頃に、当時数理科には機械学習の研究をされている先生が一人だけ所属されていました。その先生に、直接弟子入りさせていただき、僕の機械学習への道は始まりました。。。(メインは遺伝統計学の研究でした。) 弟子入りした直後は、タイピングもなめくじのように遅かったですし、gitもpullする前にpushしたこともありました。。。 しかし、その先生は、目的に最先端で届く道のりを用意してくださいました。 プログラミングを初めて一か月ほどで、t-SNEの実装をしたり(遺伝統計学の研究で必要だった)、四か月ほどで、カーネルc-SVMの実装をしたり(やってみなとゆわれて（笑）)することができました。その後も、学部二回生、三回生ながら、論文を読んで実装してきました。 学部二回生冬には、遺伝統計学の研究を 株式会社パーソルキャリア さん主催のハッチングフェスというデータサイエンティストのためのイベントで、発表しました。 このイベントでは、企業の方もたくさん来られて、知り合えるチャンスがかなりあります！！ (名刺を作っておくと、「えっ、学生なのに名刺持ってるの？！」ってなるので、覚えてもらえます。...
コメントを投稿
続きを読む