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

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












Labels:

コメント

コメントを投稿

このブログの人気の投稿

Thorem of SVM part 2

Introduction 日本語 ver This post is written about theorem of SVM. This post is part 2. Part 1 is written about deriving the objective function. I will write about dual problem. The objective function which deriving in Part 1 is called the main problem. Typically, We optimize not the main problem, but the dual problem. I will write about deriving the dual problem from the main problem. If you until look up part 1, please look up Theorem of SVM part 1 . I implement SVM. It post is Implement linear SVM Implement kernel SVM Overview Main problem Dual problem  Lagurange function maximize L about dual variable, minimize L about primal variable minimize L about primal variable, maximize L about dual variable. Main problem I will review the main problem in Part 1. $$\min_{w,b} \frac{1}{2}||W||^2 + C\sum_{i \in N} \epsilon_i$$ $$~~s.t~~ \forall i \in N, y_i (w^T \phi(x_i) + b) \geq 1 - \epsilon_i ,~~~, \forall i \in N~\epsilon \geq 0$$ This problem is called s...
コメントを投稿
続きを読む

K-means 理論編

Introduction English ver 今日はK-meansアルゴリズムの理論について書きます。 K-meansアルゴリズムはクラスタリングのためのアルゴリズムです。 K-meansの実装の記事は カーネルK-meansの実装 を御覧ください。 この記事はカーネルK-menasの実装についての記事ですが、通常のK-meansの実装も行っています。カーネルK-meansについてはまた、今度別の記事で紹介したいと思います。 概要 1 of K 符号化法 プロトタイプ 歪み尺度 最適化 1 of K 符号化法 K-meansはK個のクラスについて分類することを考えます。 K-meansでは $x_n$がkのクラスに属していることを次のように表します。 ベクトル$r_n:1 \times K$ を $$r_n := (0,0,..,1,..,0)$$ このベクトルはk番目にのみ1を持ち、それ以外は0を要素に持つようなベクトルです。 こののような表現の仕方を1 of K符号化法と呼びます。 プロトタイプ K-meansではプロトタイプと呼ばれるベクトルを選びます。このベクトルは各クラスに一つあり、そのクラスの代表のようなベクトルです。 K-means ではそのようなベクトルは各クラスの平均ベクトルとなります。これは目的関数から自然と導かれます。 歪み尺度 プロトタイプベクトルを $\mu_i ~\forall k \in K$とします。 この時、k-meansの目的関数は次のようになります。 $$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$$ ここで、 $r_{nk}$ は$r_n$のk番目の要素です。 この目的関数について少し説明をします。$r_{n}$は$x_n$が属しているクラスのラベルの場所だけ1で他は０であるので、 $$J = \sum_{n=1}^{N} ||x_n - \mu_{x_n}||$$ ここで、$\mu_{k_n}$は$x_n$が属しているクラスのプロトタイプです。 よって、 $$J = ||x_1 - \mu_{x_1}|| + ||x_2 -\mu_{x_2}|| + ...
コメントを投稿
続きを読む

Theorem of K-means

Introduction 日本語 ver Today, I will write about the theorem of K-means algorithm. K-means algorithm is a method to do clustering about K of class. The post of implement K-means is Implement kernel K-means This post is written about kernel K-means. The kernel K-means is the method which covers the weak point of K-means. I will explain kernel K-means another post. Overview 1 of K coding scheme prototype vector Distortion measure Computing 1 of K coding scheme K-means algorithm is clustering K of class. Now, K-means algorithm expresses that $x_n$ be belong to k like as follows. Let vector $r_n:1 \times K$ is $$r_n := (0,0,..,1,..,0)$$ this vector have 1 in element of k'th and have 0 in else. This expression is called 1 of K coding scheme. Prototype vector K-means algorithm chooses vector which called a prototype. this vector has represented by the cluster. K-means algorithm is regard mean vector as representative of the cluster. I...
コメントを投稿
続きを読む