M-step details

Loading...

Del curso dictado por National Research University Higher School of Economics

Bayesian Methods for Machine Learning

345 calificaciones

National Research University Higher School of Economics

Bayesian Methods for Machine Learning

345 calificaciones

Curso 3 de 7 en SpecializationAdvanced Machine Learning

People apply Bayesian methods in many areas: from game development to drug discovery. They give superpowers to many machine learning algorithms: handling missing data, extracting much more information from small datasets. Bayesian methods also allow us to estimate uncertainty in predictions, which is a desirable feature for fields like medicine. When applied to deep learning, Bayesian methods allow you to compress your models a hundred folds, and automatically tune hyperparameters, saving your time and money. In six weeks we will discuss the basics of Bayesian methods: from how to define a probabilistic model to how to make predictions from it. We will see how one can automate this workflow and how to speed it up using some advanced techniques. We will also see applications of Bayesian methods to deep learning and how to generate new images with it. We will see how new drugs that cure severe diseases be found with Bayesian methods.

De la lección

Expectation-Maximization algorithm

This week we will about the central topic in probabilistic modeling: the Latent Variable Models and how to train them, namely the Expectation Maximization algorithm. We will see models for clustering and dimensionality reduction where Expectation Maximization algorithm can be applied as is. In the following weeks, we will spend weeks 3, 4, and 5 discussing numerous extensions to this algorithm to make it work for more complicated models and scale to large datasets.

Jensen's inequality & Kullback Leibler divergence9:40

Expectation-Maximization algorithm10:50

E-step details12:21

M-step details6:34

Example: EM for discrete mixture, E-step10:23

Example: EM for discrete mixture, M-step12:17

Summary of Expectation Maximization6:46

Conoce a los instructores

Daniil Polykovskiy
Researcher
HSE Faculty of Computer Science
Alexander Novikov
Researcher
HSE Faculty of Computer Science

In this video, we'll discuss a little bit of

details about the M-step or maximization step.

Recall that on the previous video,

we derived variational lower bound for our marginal log likelihood.

So, we wanted to maximize marginal log likelihood,

but instead we are going to maximize this lower bound.

And, on the M-step, we want to maximize

this lower bound with respect to theta or parameters.

And the lower bound looks like this.

So, it's some with respect to the objects in the data set,

then some with respect to the values of the late variable G,

and then some weighted logarithms of the ratios.

Now, we can use the property of the logarithm,

that logarithm of the ratio is difference between logarithms,

and we'll get something like this.

And note that this second term in this expression,

it is constant with respect to theta,

so it doesn't depend on theta at all.

Which means that then we can start

concerned about maximizing this value with respect to theta.

We can throw this term away and nothing will change.

So we can just ignore this and it will not change our M-step,

which means that we can maximize the first term instead of the full lower bound.

And the first term you can rewrite by using the following connotation,

just an expected value of

the Joint Distribution P of X and T with respect to the variational distribution Q.

One more thing to notice here is that

this function which we are trying to maximize

with respect to theta on the M-step is concave.

Maybe not always, but usually you choose your P of X given T and P of T yourself,

so you can choose this function to be such that the [inaudible] would fit is a concave function.

Which means that it's easy to maximize and note that

expect that the value of the concave function is still a concave function.

So, for example in the Gaussian [inaudible] case,

this joint probability pure factor T is Gaussian and logarithm of Gaussian is

just some linear function with respect to parameters minus-

at least you can prove that

logarithm of the Gaussian is concave for respect to parameters.

Which means that first of all,

this function has just unique global optimum.

Well, at least all local maximas are the same as

global maxima and maybe really easy to maximize.

And usually you can even derive the analytical expression of this M-step because

this program is so much easier than the original one in most cases.

So, to summarize the expectation maximization algorithm

repeats the following two steps in iterations until convergence.

So, first of all, the E-step where we are trying to minimize

the KL distance between

the variation distribution Q and

the posterior distribution P of T U in the data and the parameters.

And this is the same as just setting Q to be the posterior distribution itself.

And then the M-step,

where we're maximizing the expected value of

the logarithm of the joint distribution with respect to parameters theta.

So, now let's say a few words about the convergence properties of this EM algorithm.

It turns out that we can prove that it converges to

a local maximum or maybe at least to a critical point.

So, to see it, let's look at the following picture.

On the previous situation theta K,

we have chosen among all the family of lower bounds.

We have chosen the best lower bound at the current point,

which is accurate at the current point.

So, on the next M-step,

we went to the maximum of this lower bound,

of this red curve, to get theta K plus one.

Let's look how the marginal log likelihood

changed after switching from theta K to theta K plus one.

So, marginal log likelihood at the point theta K plus one is greater than or equal to

the lower bound at the point theta K plus one just because its lower bound,

so it should always hold for any point, right?

Then we can say that the value of

this lower bound at the current point, the theta K plus one,

is greater than or equal to the value of the lower bound at the previous point,

just because theta K plus one is the maximum of the lower bound with respect to theta.

So it's greater than or equal to the value of the lower bound at any other point, right?

And finally, because we have chosen Q to be such that the lower bound is optimal in

the point theta K then this lower bound at the point theta K

just equals to the log likelihood at the point theta K. So,

finally, we obtained such an equation that tells us that

the marginal log likelihood never decreases during an iteration of the EM algorithm.

Which basically means that the EM algorithm never make things worse.

And so there are two outcomes of this observation.

First of all, it's a really useful debugging tool.

So if you ever see in your implementation of the EM,

that the marginal log likelihood decreases,

then you have a bug and you have to fix it somehow.

And second of all, by using this kind of considerations,

you can prove that the EM algorithm always converge.

It may be a local maximum,

it maybe some other critical point,

but at least it's not worse than the gradient descent in this respect.

So, it's always converses at some critical point.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play