(Maximum A-Posteriori Estimation (MAP))
 
(33 intermediate revisions by 10 users not shown)
Line 1: Line 1:
 +
[[Category:ECE302Fall2008_ProfSanghavi]]
 +
[[Category:probabilities]]
 +
[[Category:ECE302]]
 +
[[Category:cheat sheet]]
 +
 +
=[[ECE302]] Cheat Sheet number 4=
 
==Maximum Likelihood Estimation (ML)==
 
==Maximum Likelihood Estimation (ML)==
 
:<math>\hat a_{ML} = \overset{max}{a}  f_{X}(x_i;a)</math> continuous
 
:<math>\hat a_{ML} = \overset{max}{a}  f_{X}(x_i;a)</math> continuous
  
 
:<math>\hat a_{ML} = \overset{max}{a}  Pr(x_i;a)</math> discrete
 
:<math>\hat a_{ML} = \overset{max}{a}  Pr(x_i;a)</math> discrete
 +
 +
 +
==Chebyshev Inequality==
 +
"Any RV is likely to be close to its mean"
 +
 +
:<math>\Pr(\left|X-E[X]\right|\geq C)\leq\frac{var(X)}{C^2}.</math>
 +
  
 
==Maximum A-Posteriori Estimation (MAP)==
 
==Maximum A-Posteriori Estimation (MAP)==
<math>\hat \theta_{MAP}(x) = \text{arg }\overset{max}{\theta} P_{X|\theta}(x|\theta)P_
+
:<math>\hat \theta_{MAP}(x) = \text{arg }\overset{max}{\theta} P_{X|\theta}(x|\theta)P_
 
{\theta}(\theta)</math>
 
{\theta}(\theta)</math>
  
<math>\hat \theta_{MAP}(x) = \text{arg }\overset{max}{\theta} f_{X|\theta}(x|\theta)P_
+
:<math>\hat \theta_{MAP}(x) = \text{arg }\overset{max}{\theta} f_{X|\theta}(x|\theta)P_
 
{\theta}(\theta)</math>
 
{\theta}(\theta)</math>
  
 
==Minimum Mean-Square Estimation (MMSE)==
 
==Minimum Mean-Square Estimation (MMSE)==
  
<math>\hat{y}_{\rm MMSE}(x) = \int\limits_{-\infty}^{\infty}\ {y}{f}_{\rm Y|X}(y|x)\, dy={E}(Y|X=x)</math>
+
:<math>\hat{y}_{\rm MMSE}(x) = \int_{-\infty}^{\infty} {y}{f}_{\rm Y|X}(y|x)\, dy={E}[Y|X=x]</math>
  
== '''Law Of Iterated Expectation''' ==
+
==Law Of Iterated Expectation==
 +
:<math>E[E[X|Y]] =
 +
\begin{cases}
 +
\sum_{y} E[X|Y = y]p_Y(y),\,\,\,\,\,\,\,\,\,\,\mbox{      Y discrete,}\\
 +
\int_{-\infty}^{+\infty} E[X|Y = y]f_Y(y)\,dy,\mbox{      Y continuous.}
 +
\end{cases}</math>
  
 +
Using the total expectation theorem:
  
Unconditional Expectaion--<math>\ E[X] = E[E[x|\theta]]</math>
+
:<math>E\Big[ E[X|Y]] = E[X]</math>
  
--[[User:Umang|Umang]] 16:10, 13 December 2008 (UTC)umang
+
==Mean Square Error==
                                                                   
+
  
 +
:<math>MSE = E[(\Theta - \hat \theta(x))^2]</math>
  
=='''Mean square error :'''==
+
:<math>MSE(E(\Theta)) = var(\Theta) \,</math>
 
+
<math>MSE = E[(\theta - \hat \theta(x))^2]</math>
+
  
 
==Linear Minimum Mean-Square Estimation (LMMSE)==
 
==Linear Minimum Mean-Square Estimation (LMMSE)==
  
<math>\hat{y}_{\rm LMMSE}(x) = E[\theta]+\frac{COV(x,\theta)}{Var(x)}*(x-E[x])</math>
+
The LMMS estimator <math>\hat{Y}</math> of Y based on the variable X is
 +
 
 +
:<math>\hat{Y}_{LMMSE}(x) = E[Y]+\frac{COV(Y,X)}{Var(X)}(X-E[X]) = E[Y] + \rho \frac{\sigma_{Y}}{\sigma_{X}}(X-E[X])</math>
 +
 
 +
where
 +
::<math>\rho = \frac{COV(Y,X)}{\sigma_{Y}\sigma_{X}}</math>
  
 
Law of Iterated Expectation: E[E[X|Y]]=E[X]
 
Law of Iterated Expectation: E[E[X|Y]]=E[X]
  
==Hypothesis Testing: ML Rule==
+
COV(X,Y)=E[XY] - E[X]E[Y]
 +
 
 +
==Hypothesis Testing==
 +
In hypothesis testing <math>\Theta</math> takes on one of ''m'' values, <math>\theta_1,...,\theta_m</math> where ''m'' is usually small; often ''m'' = 2, in which case it is a binary hypthothesis testing problem.
 +
 
 +
The event <math>\Theta = \theta_i</math> is the <math>i^{th}</math> hypothesis denoted by <math>H_i</math>
 +
===ML Rule===
  
 
Given a value of X, we will say H1 is true if X is in region R, else will will say H0 is true.
 
Given a value of X, we will say H1 is true if X is in region R, else will will say H0 is true.
  
'''Type I error'''
+
'''Type I Error: False Rejection'''
  
Say H1 when truth is H0. Probability of this is: <math>Pr(\mbox{Say } H_1|H_0) = Pr(x \in R|\theta_0)</math>
+
Say <math>H_1</math> when truth is <math>H_0</math>. Probability of this is:
 +
:<math>Pr(\mbox{Say } H_1|H_0) = Pr(x \in R|\theta_0)</math>
  
'''Type II error'''
+
'''Type II Error: False Acceptance'''
  
Say H0 when truth is H1. Probability of this is: <math>Pr(\mbox{Say }H_0|H_1) = Pr(x \in R^C|\theta_1)</math>
+
Say <math>H_0</math> when truth is <math>H_1</math>. Probability of this is:
 +
:<math>Pr(\mbox{Say }H_0|H_1) = Pr(x \in R^C|\theta_1)</math>
  
==Hypothesis Testing: MAP Rule==
 
  
<math>\mbox{Overall P(err)} = P_{\theta}(\theta_{0})Pr\Big[\mbox{Say }H_{1}|H_{0}\Big] +P_{\theta}(\theta_{1})Pr\Big[\mbox{Say }H_{0}|H_{1}\Big] </math>
+
Say H1 if;
 +
:<math>\{f_{X|\theta}(x|\theta1)</math>  >  <math>\{f_{X|\theta}(x|\theta0)</math>
 +
Else H0
  
==Likelihood Ratio TEST==
+
Say H0 if;
 +
:<math>\{f_{X|\theta}(x|\theta1)</math>  <=  <math>\{f_{X|\theta}(x|\theta0)</math>
 +
Else H1
 +
 
 +
===MAP Rule===
 +
 
 +
:<math>\mbox{Overall P(err)} = P_{\theta}(\theta_{0})Pr\Big[\mbox{Say }H_{1}|H_{0}\Big] +P_{\theta}(\theta_{1})Pr\Big[\mbox{Say }H_{0}|H_{1}\Big] </math>
 +
 
 +
Note that for Overall P(error), cannot use values from ML estimate.
 +
 
 +
===Likelihood Ratio Test===
  
 
'''''How to find a good rule?'''''
 
'''''How to find a good rule?'''''
 
--[[User:Khosla|Khosla]] 16:44, 13 December 2008 (UTC)
 
--[[User:Khosla|Khosla]] 16:44, 13 December 2008 (UTC)
  
<math>\ L(x) = \frac{P_{\rm X|\theta} (x|\theta_1)}{P_{\rm X|\theta} (x|\theta_1)} </math>
+
For X is discrete
 +
 
 +
:<math>\ L(x) = \frac{p_{X|\theta} (x|\theta_1)}{p_{X|\theta} (x|\theta_0)} </math>
  
 
Choose threshold  (T),
 
Choose threshold  (T),
  
<math>\mbox{Say }
+
:<math>\mbox{Say }
 
\begin{cases}  
 
\begin{cases}  
 
   H_{1}; \mbox{    if    } L(x) > T\\
 
   H_{1}; \mbox{    if    } L(x) > T\\
Line 65: Line 108:
 
\end{cases}</math>
 
\end{cases}</math>
  
so ML Rule is an LRT with T = 1
+
The Maximum Likelihood rule is a Likelihood Ratio Test with T = 1
 
+
The MAP rule is a Likelihood Ratio Test with <math>T=\frac{P_\theta(\theta_0)}{P_\theta(\theta_1)}</math>
as T increases Type I Error Increases
+
 
+
as T increases Type II Error Decreases
+
  
& Vice Versa
+
'''Observations''':
 +
#as T decreases Type I Error Increases
 +
#as T decreases Type II Error Decreases
 +
#as T increases Type I Error Decreases
 +
#as T increases Type II Error Increases
 +
(<math>T = 0 \Rightarrow R = \{x|P_{X|\theta}(x|\theta_1) > 0\}</math>.  So, Type I error (<math>Pr(x\in R | H_0)</math>) is maximized as T is minimized.)
  
so ML Rule is an Likelihood Ratio Test with T = 1
+
The threshold value T=1, corresponds to the ML rule.
 +
----
 +
[[Main_Page_ECE302Fall2008sanghavi|Back to ECE302 Fall 2008 Prof. Sanghavi]]

Latest revision as of 13:06, 22 November 2011


ECE302 Cheat Sheet number 4

Maximum Likelihood Estimation (ML)

$ \hat a_{ML} = \overset{max}{a} f_{X}(x_i;a) $ continuous
$ \hat a_{ML} = \overset{max}{a} Pr(x_i;a) $ discrete


Chebyshev Inequality

"Any RV is likely to be close to its mean"

$ \Pr(\left|X-E[X]\right|\geq C)\leq\frac{var(X)}{C^2}. $


Maximum A-Posteriori Estimation (MAP)

$ \hat \theta_{MAP}(x) = \text{arg }\overset{max}{\theta} P_{X|\theta}(x|\theta)P_ {\theta}(\theta) $
$ \hat \theta_{MAP}(x) = \text{arg }\overset{max}{\theta} f_{X|\theta}(x|\theta)P_ {\theta}(\theta) $

Minimum Mean-Square Estimation (MMSE)

$ \hat{y}_{\rm MMSE}(x) = \int_{-\infty}^{\infty} {y}{f}_{\rm Y|X}(y|x)\, dy={E}[Y|X=x] $

Law Of Iterated Expectation

$ E[E[X|Y]] = \begin{cases} \sum_{y} E[X|Y = y]p_Y(y),\,\,\,\,\,\,\,\,\,\,\mbox{ Y discrete,}\\ \int_{-\infty}^{+\infty} E[X|Y = y]f_Y(y)\,dy,\mbox{ Y continuous.} \end{cases} $

Using the total expectation theorem:

$ E\Big[ E[X|Y]] = E[X] $

Mean Square Error

$ MSE = E[(\Theta - \hat \theta(x))^2] $
$ MSE(E(\Theta)) = var(\Theta) \, $

Linear Minimum Mean-Square Estimation (LMMSE)

The LMMS estimator $ \hat{Y} $ of Y based on the variable X is

$ \hat{Y}_{LMMSE}(x) = E[Y]+\frac{COV(Y,X)}{Var(X)}(X-E[X]) = E[Y] + \rho \frac{\sigma_{Y}}{\sigma_{X}}(X-E[X]) $

where

$ \rho = \frac{COV(Y,X)}{\sigma_{Y}\sigma_{X}} $

Law of Iterated Expectation: E[E[X|Y]]=E[X]

COV(X,Y)=E[XY] - E[X]E[Y]

Hypothesis Testing

In hypothesis testing $ \Theta $ takes on one of m values, $ \theta_1,...,\theta_m $ where m is usually small; often m = 2, in which case it is a binary hypthothesis testing problem.

The event $ \Theta = \theta_i $ is the $ i^{th} $ hypothesis denoted by $ H_i $

ML Rule

Given a value of X, we will say H1 is true if X is in region R, else will will say H0 is true.

Type I Error: False Rejection

Say $ H_1 $ when truth is $ H_0 $. Probability of this is:

$ Pr(\mbox{Say } H_1|H_0) = Pr(x \in R|\theta_0) $

Type II Error: False Acceptance

Say $ H_0 $ when truth is $ H_1 $. Probability of this is:

$ Pr(\mbox{Say }H_0|H_1) = Pr(x \in R^C|\theta_1) $


Say H1 if;

$ \{f_{X|\theta}(x|\theta1) $ > $ \{f_{X|\theta}(x|\theta0) $

Else H0

Say H0 if;

$ \{f_{X|\theta}(x|\theta1) $ <= $ \{f_{X|\theta}(x|\theta0) $

Else H1

MAP Rule

$ \mbox{Overall P(err)} = P_{\theta}(\theta_{0})Pr\Big[\mbox{Say }H_{1}|H_{0}\Big] +P_{\theta}(\theta_{1})Pr\Big[\mbox{Say }H_{0}|H_{1}\Big] $

Note that for Overall P(error), cannot use values from ML estimate.

Likelihood Ratio Test

How to find a good rule? --Khosla 16:44, 13 December 2008 (UTC)

For X is discrete

$ \ L(x) = \frac{p_{X|\theta} (x|\theta_1)}{p_{X|\theta} (x|\theta_0)} $

Choose threshold (T),

$ \mbox{Say } \begin{cases} H_{1}; \mbox{ if } L(x) > T\\ H_{0}; \mbox{ if } L(x) < T \end{cases} $

The Maximum Likelihood rule is a Likelihood Ratio Test with T = 1 The MAP rule is a Likelihood Ratio Test with $ T=\frac{P_\theta(\theta_0)}{P_\theta(\theta_1)} $

Observations:

  1. as T decreases Type I Error Increases
  2. as T decreases Type II Error Decreases
  3. as T increases Type I Error Decreases
  4. as T increases Type II Error Increases

($ T = 0 \Rightarrow R = \{x|P_{X|\theta}(x|\theta_1) > 0\} $. So, Type I error ($ Pr(x\in R | H_0) $) is maximized as T is minimized.)

The threshold value T=1, corresponds to the ML rule.


Back to ECE302 Fall 2008 Prof. Sanghavi

Alumni Liaison

Abstract algebra continues the conceptual developments of linear algebra, on an even grander scale.

Dr. Paul Garrett