# Expectation Maximization intuitive explanation

Given a set of events {A, B, C, D, E} that occur once each month for n years:

 [A, B, C, C, B, D, A, B, C, C, B, D] [E, B, C, B, B, D, E, B, C, B, B, D] [C, B, C, D, E, A, A, D, C, C, B, D] //12 months x 3 years pictured ... 

I have the probability function p(w, r) = ... which computes the probability of an event to follow another (e.g. A after B), where w and r are parameters that model the output in such way that when correctly picked should fit the sample data.

My final goal is to predict events in a year, but I'm stuck at using EM to determine w and r.

Intuitively, what I do now is:

1. Start with a total random value for w and r
2. Compute the probability for each pair in a year (e.g. A and B) using p function, compare it with the actual probability distribution extracted from the samples and basically getting how probable (v) is for the current w and r to be to fit the samples.
3. Now my 3rd step would be to modify w and r so that v should converge towards 1. This is where I'm stuck.

How should I use v to get new values for w and r so that v will eventually converge towards 1?

EDIT:

I'd like to add that p basically gives me the estimated probability distribution for the event succession. Which means that I have two 2D surfaces: the estimate and the sampled probability distributions and I want to use w and r to shift and scale the estimated surface in such way that it fits best the sampled one.

So my problem is, how can I compare the two after a step and how should I get new w and r values for the next step.

E.g.: I was thinking that I could use some kind of matrix norm, to get the degree of similarity between the two and then use this to decide, based on previous iterations if I should increase w/r or decrease.

• what do w and r represent? – Tilefish Poele Sep 20 '17 at 6:23
• w, r are the parameters of my model. I'm looking to find the maximum likelihood estimates for them. – Valentin Radu Sep 20 '17 at 12:48
• okay, but what do they represent. As in, are they the representative of the letters? or some scale and location parameters? – Tilefish Poele Sep 20 '17 at 13:34
• 'w' and 'r' are shifting and scaling the distribution generated by p. – Valentin Radu Sep 20 '17 at 14:05
• I´m not sure EM is the algorithm you need since it is designed to find MAP estimates of models with latent variables and your problem description resembles a vanilla classification where model parameters can be learned by standard optimization techniques like gradient descent. – xboard Sep 22 '17 at 4:56

Essentially you want to hill climb by differentiating $p(w,r)$ with respect to $w$ and $r$ and adjust $w$ and $r$ by some small constant amount with sign corresponding to the largest increase in gradient and then repeat until you reach a maxima.
Since you're choosing $w$ and $r$ randomly and you haven't told us how $p(w,r)$ behaves you might not be able to find the global maximum though depending on the shape of the 2d surface. If the surface does have local minima and maxima, you'd want to reduce this localisation error by initialising multiple random pairs of points at the start of this algorithm then choosing the best amongst the trials.
• Thanks for the answer. I tried something similar to what you mentioned above, however, my problem still remains, because I'm still not sure what should I use to compare the estimate with the sampled data and how can I transform the resulting value into the correct w or/and r step. Sorry if this is a stupid question, I'm actually quite new to this. I added an edit, maybe it clears out the questions you had. – Valentin Radu Sep 22 '17 at 3:58