# Difference between revisions of "Eleisha's Segment 30: Expectation Maximization (EM) Methods"

Line 2: | Line 2: | ||

1. For a set of positive values <math> \{x_i\} </math> , use Jensen's inequality to show (a) the mean of their square is never less than the square of their mean, and (b) their (arithmetic) mean is never less than their harmonic mean. | 1. For a set of positive values <math> \{x_i\} </math> , use Jensen's inequality to show (a) the mean of their square is never less than the square of their mean, and (b) their (arithmetic) mean is never less than their harmonic mean. | ||

− | 2. Sharpen the argument about termination of E-M methods that was given in slide 4, as follows: Suppose that <math> g(x) \ge f(x) </math> for all x, for some two functions <math> f </math> and <math> g </math> . Prove that, at any local maximum <math> x_m </math> of <math> f </math>, one of these two conditions must hold: (1) <math> g(x_m) > f(x_m) </math> [in which case the E-M algorithm has not yet terminated], or (2) <math> g(x_m) </math> is a local maximum of <math>g </math> [in which case the E-M algorithm terminates at a maximum of g, as advertised]. You can make any reasonable assumption about continuity of the functions. | + | 2. Sharpen the argument about termination of E-M methods that was given in slide 4, as follows: Suppose that <math> g(x) \ge f(x) </math> for all <math> x </math>, for some two functions <math> f </math> and <math> g </math> . Prove that, at any local maximum <math> x_m </math> of <math> f </math>, one of these two conditions must hold: (1) <math> g(x_m) > f(x_m) </math> [in which case the E-M algorithm has not yet terminated], or (2) <math> g(x_m) </math> is a local maximum of <math>g </math> [in which case the E-M algorithm terminates at a maximum of g, as advertised]. You can make any reasonable assumption about continuity of the functions. |

<b> To Think About </b> | <b> To Think About </b> | ||

+ | |||

1. Jensen's inequality says something like "any concave function of a mixture of things is greater than the same mixture of the individual concave functions". What "mixture of things" is this idea being applied to in the proof of the E-M theorem (slide 4)? | 1. Jensen's inequality says something like "any concave function of a mixture of things is greater than the same mixture of the individual concave functions". What "mixture of things" is this idea being applied to in the proof of the E-M theorem (slide 4)? | ||

## Revision as of 12:10, 3 April 2014

** To Calculate **
1. For a set of positive values **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{x_i\} }**
, use Jensen's inequality to show (a) the mean of their square is never less than the square of their mean, and (b) their (arithmetic) mean is never less than their harmonic mean.

2. Sharpen the argument about termination of E-M methods that was given in slide 4, as follows: Suppose that **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x) \ge f(x) }**
for all **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x }**
, for some two functions **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f }**
and **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g }**
. Prove that, at any local maximum **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_m }**
of **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f }**
, one of these two conditions must hold: (1) **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x_m) > f(x_m) }**
[in which case the E-M algorithm has not yet terminated], or (2) **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x_m) }**
is a local maximum of **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g }**
[in which case the E-M algorithm terminates at a maximum of g, as advertised]. You can make any reasonable assumption about continuity of the functions.

** To Think About **

1. Jensen's inequality says something like "any concave function of a mixture of things is greater than the same mixture of the individual concave functions". What "mixture of things" is this idea being applied to in the proof of the E-M theorem (slide 4)?

2. So slide 4 proves that some function is less than the actual function of interest, namely **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L(\theta) }**
. What makes this such a powerful idea?

** Back To: ** Eleisha Jackson