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

Maximum likelihood extimation

Introduction


Today, I will write about the Maximum likelihood estimation. This is basically the Statistics estimation. I want to explain an example of Maximum likelihood estimation. Firstly, I will explain likelihood. Secondly, I will likelihood function. Thirdly, I will explain the Maximum likelihood estimation.

Overview


  • likelihood
  • Maximum likelihood estimation
  • the problem of Maximum likelihood estimation


likelihood

Let we get the observation data by a precondition.
When we estimate precondition by an observation data, the likelihood is a plausible value which indicated that its estimation is correct.

Maybe, you can not understand this meaning. Also, I could not understand.
I give you an example of likelihood.

I throw a coin. this coin land heads up by probability P, and lands head on the reverse by probability 1-P.
For example, when I throw 100 times a coin, all trial is head. Then, we estimate that probability P is 1.0.

If let P=0.5, Probability that the coin lands 100 times heads is $0.5^{100} = 7.88860e-31$. this is likelihood when let P=0.5.

If let P=0.99, Provability that the coin lands 100 times heads is $0.99^{100} = 0.3666....$. this is likelihood when let P=0.99.

when a phenomenon is fixed that the coin lands 100 times heads, P(100 times heads|P) is called likelihood function of variable P.

At result, the likelihood is that P(A|B = b) when A is fixed and it hold B=b.

We regard maximizing likelihood as reasonable value b.

For example, I use an earlier example.

when letting P=0.5, tje likelihood is 7.88860e-31. when letting P=0.99, likelihood is 0.3666.
Thus, we think that it is natural for our to regard P=0.99.

Thus, P=0.99 is optimum than P=0.5.

Maximum likelihood estimation

The Maximum likelihood estimation is a method that we estimate a parameter of the probability distribution from getting observation data.

The maximum likelihood estimation maximizes all likelihood.

Let probability distirbution function is $f$ and $X_1,X_2,...,X_n is specimen such that $$X_1,X_2, ..., X_n \sim f$.

Then, Probability that we get $X_1,X_2,..,X_n$ from $f$ is
$$\Pi_{i=1}^{N} P(X_i)$$
, because we have to think joint probability.

Thus, I define
$$L(\theta) = f(x_1,x_2,...,x_n|\theta)$$ called likelihood function.

Then,
$$\theta^{\star} \in \arg_{\theta} \max L(\theta)$$
$\theta$ is called maximum likelihood estimator,

and,
$$\frac{\partial}{\partial \theta} \log L(\theta)$$
is called likelihood equation.

I explain the reason that I use $\log$ next example of maximum likelihood estimation.

Example

I think about $x_1,x_2,...,x_n \in {0,1}$. $\forall i \in {1,2,..,n}$, If $x_i = 1$, the coin lands head i'th time. if $x_i$, the coin lands tail i'th time.

Then, likehood function is
$$L(\theta) = P(x_1,x_2,...,x_n|\theta) = \Pi_{i=1}^{n} \theta^{x_i} (1-\theta)^{1-x_i}$$
, because $\forall i \in {1,2,..,n},  \sim p(k;\theta) = \theta^k (1-\theta)^{1-k} ~~~~\textrm{for} k \in {0,1}$
here, $\theta$ is probability that the coin lands head.

I maximize $L(\theta)$ about $\theta$, but it is difficult to differentiating, because $L(\theta)$ is expressed multiplication.

I solve this problem.
Its method is $\log$ function.
$\log$ function is monotonically increasing function, thus it is consistented optimal solution of $L(\theta)$ and $\log L(\theta)$.

Thus, I think maximizing $\log L(\theta)$.

\begin{eqnarray*}
\log L(\theta) &=& \log \Pi_{i=1}^{n} \theta^{x_i} (1-\theta)^{1-x_i} \\
&=& \sum_{i=1}^N \log \theta^{x_i} + \log (1-\theta)^{1-x_i} \\
&=& \sum_{i=1}^N  x_i \log \theta + (1-x_i)\log(1-\theta)
\end{eqnarray*}

Partial of this is

\begin{eqnarray*}
\frac{\partial}{\partial \theta} \log L(\theta) &=& 0 \\
\frac{\partial}{\partial \theta} \sum_{i=1}^N x_i \log \theta + (1-x_i) \log (1-\theta) &=& 0 \\
\sum_{i=1}^N \frac{x_i}{\theta} - \frac{1-x_i}{1-\theta} &=& 0 \\
\frac{1}{\theta} \sum_{i=1}^N x_i - \frac{1}{1-\theta_i} \sum_{i=1}^N (1-x_i) &=& 0 \\
(1-\theta) \sum_{i=1}^N x_i - \theta \sum_{i=1}^N 1-x_i &=& 0 \\
\sum_{i=1}^N x_i - \theta \sum_{i=1}^N x_i - \theta \sum_{i=1}^N 1 + \theta \sum_{i=1}^N x_i &=& 0 \\
\sum_{i=1}^N x_i - n \theta &=& 0 \\
\theta &=& \frac{\sum_{i=1}^N }{n} \\
\end{eqnarray*}


This optimum is mean of $x_1,x_2,..,x_n$.
If you get the phenomenon that head is 100 times and tail is 0 times.
Then $\theta = 1$

If you get the phenomenon that head is 50 times and tail is 50 times.
Then $\theta = 0.5$


Problem of Maximum likelihood estimation

For example,
If you get the phenomenon that head is 100 times and tail is 0 times, then $\theta = 1$,
but if you get the phenomenon that is 3 times and tail 0 times, then $\theta = 1$.

However, it is dangerous to judge $\theta = 1$ by 3 times implement.

It is problem, Thus maximum likelihood estimation is dangerous when a number of the trial is few.

Reference

https://ja.wikipedia.org/wiki/%E5%B0%A4%E5%BA%A6%E9%96%A2%E6%95%B0

コメント

このブログの人気の投稿

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で他は0であるので、 $$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}|| + ...

ダイクストラ法

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))に減らせます。ヒープ構造で現時点での...

カーネル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$としま...