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

MAP estimation

Introduction

Today, I will explain MAP estimation(maximum a posteriori estimation).
MAP estimation is used Bayes' thorem. If sample data is few, we can not belive value by Maximum likelihood estimation. Then, MAP estimation is enable to include our sense. 

Overveiw

  • Bayes' theorem
  • MAP estimation
  • Conjugate distribution



Bayes' theorem 
Bayes' theorem is

$$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$

$P(A|B)$ is Probability when B occur.

Please go on http://takutori.blogspot.com/2018/04/bayes-theorem.html to know detail of Bayes' theorem.

Map estimation
Map estimation is used Bayes' theorem. Map estimation estimate parameter of population by maximuzing posterior probability.

Now, suppoce we get data $x_1,x_2,...,x_n$ from population which have parameter $\theta$. Then, we want to $P(\theta|x_1,x_2,...,x_n)$.

Here, we use Bayes' theorem.
$$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)}$$

here, $P(\theta)$ is Prior distribution of $\theta$.

Because $x_1,x_2,...,x_n$ is indpendence each other,
$$P(x_1,x_2,...,x_n | \theta ) = \Pi_{i=1}^n P(x_i|\theta)$$.

Therefore, MAP estimation is
$$\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)$ do not dependent on $\theta$, Therefore MAP estimation is express as follows.

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


Conjugate distribution
Conjugate distribution is a convenient distribution.  In general, 
The posterior distribution is consist of complex form. However, It is possible to simplify it by using conjugate distribution. When conjugate distribution is chosen for prior distribution, posterior distribution' from consistent prior distribution' from. Actually, I will calculate it next section. The famous conjugate distribution is


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

.

Example
$$ Beta(\theta|a,b) = \frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}\theta^{a-1}(1-\theta)^{b-1} $$
This is beta distribution. When we MAP estimate beta distribution, prior distribution is gamma distribution.

$$ \Gamma(x) = \int_0^\infty u^{x-1}e^{-u}du $$

posterior distribution is 


$$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}$$


Because $x_i$is $1~or~0$,
$$ p(x=1,\theta)p(x=1,\theta)p(x=,\theta) =\theta\theta(1-\theta) $$.
Thus,
$$ \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) = \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}$$
Thus,
$$P(\theta|D) \propto \theta^{(\sum_{i=1}^{n}x_i)+a-1}(1-\theta)^{(\sum_{i=1}^{n}(1-x_i))+b-1}$$

This optimazing problem is solve by $\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$$
Because
$$ \sum_{i=1}^{n}x_i + \sum_{i=1}^{n}(1-x_i) = n $$, optimize value is
$$ \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-平均法とも呼ばれています。初めに、適当なクラスに分け、各クラスの中で平均となるベクトルを求めます。そして、各データに対して、すべての平均ベクトルとの距離を求めます。そして、最小となる距離になるクラスに改めて、そのデータをクラスタリングします。そして、新たに得られたクラスの中でそれぞれ平均ベクトルを求め、これを繰り返し、平均ベクトルが動かな...

カーネルK-means 理論編

Introduction English ver 今日は、カーネルK-meansの理論について書きます。カーネルK-meansは通常のK-meansの欠点を補うことができます。通常のK-meansの欠点とカーネルK-meansの強みも説明します。もし、まだ御覧になられていなければ、通常の K-means 理論編 の記事を見ていただけるとよいのではないかと思います。 カーネルK-meansの実装編 も併せてご覧ください。 概要 K-meansの弱点 カーネルトリック カーネルK-means アルゴリズム K-meansの弱点 例えば、次のようなデータを用意します。 このデータはK-meansによってうまく分類することはできません。なぜなら通常のK-meansでは、データとプロトタイプのユークリッド距離に依存しているからです。そのため、このような円状に分布しているデータはうまく分類することができません。 プロトタイプとはそれぞれのクラスにあり、そのクラスを代表するようなもののことです。K-meansでは各クラスの平均ベクトルとなります。それゆえ、以下のような分類になってしまいます。 このようなデータではK-meansはうまくいきません。 K-meansで分類できるデータセットは次のように各クラスで固まっている必要があります。 カーネルK-meansはK-meansの弱点を補います。 カーネルトリック 初めに、カーネルトリックを説明します。 線形分離できないようなデータ$X$を例えば次のように線形分離できるように$\phi(x)$に送る写像$\phi$を考えます。 カーネルは次のように定義されます。 $$K(x,y) = \phi(x)^T \phi(y)$$ $\phi$を具体的に計算することは難しいですが、$K(x,y)$を計算することなら簡単です。 この手法をカーネルトリックと呼ばれます。 カーネルK means K-meansの目的関数を復習しておきます。 $$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$$ ここで、 プロトタイプは$\mu_i ~\forall k \in K$としま...

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

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