3.5 Probabilistic Topic Models: Expectation-Maximization Algorithm: Part 2

Loading...

From the course by University of Illinois at Urbana-Champaign

Text Mining and Analytics

345 ratings

University of Illinois at Urbana-Champaign

Text Mining and Analytics

345 ratings

Course 3 of 6 in the Specialization Data Mining

This course will cover the major techniques for mining and analyzing text data to discover interesting patterns, extract useful knowledge, and support decision making, with an emphasis on statistical approaches that can be generally applied to arbitrary text data in any natural language with no or minimum human effort. Detailed analysis of text data requires understanding of natural language text, which is known to be a difficult task for computers. However, a number of statistical approaches have been shown to work well for the "shallow" but robust analysis of text data for pattern finding and knowledge discovery. You will learn the basic concepts, principles, and major algorithms in text mining and their potential applications.

From the lesson

Week 3

During this module, you will learn topic analysis in depth, including mixture models and how they work, Expectation-Maximization (EM) algorithm and how it can be used to estimate parameters of a mixture model, the basic topic model, Probabilistic Latent Semantic Analysis (PLSA), and how Latent Dirichlet Allocation (LDA) extends PLSA.

3.1 Probabilistic Topic Models: Mixture of Unigram Language Models12:39

3.2 Probabilistic Topic Models: Mixture Model Estimation: Part 110:16

3.3 Probabilistic Topic Models: Mixture Model Estimation: Part 28:15

3.4 Probabilistic Topic Models: Expectation-Maximization Algorithm: Part 111:05

3.5 Probabilistic Topic Models: Expectation-Maximization Algorithm: Part 210:39

3.6 Probabilistic Topic Models: Expectation-Maximization Algorithm: Part 36:25

3.7 Probabilistic Latent Semantic Analysis (PLSA): Part 110:38

3.8 Probabilistic Latent Semantic Analysis (PLSA): Part 210:15

3.9 Latent Dirichlet Allocation (LDA): Part 110:20

3.10 Latent Dirichlet Allocation (LDA): Part 212:03

Meet the Instructors

ChengXiang Zhai
Professor
Department of Computer Science

[SOUND] So

this is indeed a general idea of the Expectation-Maximization, or EM,

Algorithm.

So in all the EM algorithms we introduce a hidden variable

to help us solve the problem more easily.

In our case the hidden variable is a binary variable for

each occurrence of a word.

And this binary variable would indicate whether the word has

been generated from 0 sub d or 0 sub p.

And here we show some possible values of these variables.

For example, for the it's from background, the z value is one.

And text on the other hand.

Is from the topic then it's zero for z, etc.

Now, of course, we don't observe these z values, we just imagine they're all such.

Values of z attaching to other words.

And that's why we call these hidden variables.

Now, the idea that we talked about before for

predicting the word distribution that has been used when we generate the word

is it a predictor, the value of this hidden variable?

And, so, the EM algorithm then, would work as follows.

First, we'll initialize all the parameters with random values.

In our case, the parameters are mainly the probability.

of a word, given by theta sub d.

So this is an initial addition stage.

These initialized values would allow us to use base roll to take a guess

of these z values, so we'd guess these values.

We can't say for sure whether textt is from background or not.

But we can have our guess.

This is given by this formula.

It's called an E-step.

And so the algorithm would then try to use the E-step to guess these z values.

After that, it would then invoke another that's called M-step.

In this step we simply take advantage of the inferred z values and

then just group words that are in the same distribution like these

from that ground including this as well.

We can then normalize the count to estimate the probabilities or

to revise our estimate of the parameters.

So let me also illustrate that we can group the words

that are believed to have come from zero sub d, and

that's text, mining algorithm, for example, and clustering.

And we group them together to help us

re-estimate the parameters that we're interested in.

So these will help us estimate these parameters.

Note that before we just set these parameter values randomly.

But with this guess, we will have somewhat improved estimate of this.

Of course, we don't know exactly whether it's zero or one.

So we're not going to really do the split in a hard way.

But rather we're going to do a softer split.

And this is what happened here.

So we're going to adjust the count by the probability that would believe

this word has been generated by using the theta sub d.

And you can see this, where does this come from?

Well, this has come from here, right?

From the E-step.

So the EM Algorithm would iteratively improve uur initial

estimate of parameters by using E-step first and then M-step.

The E-step is to augment the data with additional information, like z.

And the M-step is to take advantage

of the additional information to separate the data.

To split the data accounts and then collect the right data accounts to

re-estimate our parameter.

And then once we have a new generation of parameter, we're going to repeat this.

We are going the E-step again.

To improve our estimate of the hidden variables.

And then that would lead to another generation of re-estimated parameters.

For the word distribution that we are interested in.

Okay, so, as I said, the bridge between the two

is really the variable z, hidden variable, which indicates how likely

this water is from the top water distribution, theta sub p.

So, this slide has a lot of content and you may need to.

Pause the reader to digest it.

But this basically captures the essence of EM Algorithm.

Start with initial values that are often random themself.

And then we invoke E-step followed by M-step to get an improved

setting of parameters.

And then we repeated this, so this a Hill-Climbing algorithm

that would gradually improve the estimate of parameters.

As I will explain later there is some guarantee for

reaching a local maximum of the log-likelihood function.

So lets take a look at the computation for a specific case, so

these formulas are the EM.

Formulas that you see before, and you can also see there are superscripts,

here, like here, n, to indicate the generation of parameters.

Like here for example we have n plus one.

That means we have improved.

From here to here we have an improvement.

So in this setting we have assumed the two numerals have equal probabilities and

the background model is null.

So what are the relevance of the statistics?

Well these are the word counts.

So assume we have just four words, and their counts are like this.

And this is our background model that assigns high probabilities to common

words like the.

And in the first iteration, you can picture what will happen.

Well first we initialize all the values.

So here, this probability that we're interested in is normalized into a uniform

distribution of all the words.

And then the E-step would give us a guess of the distribution that has been used.

That will generate each word.

We can see we have different probabilities for different words.

Why?

Well, that's because these words have different probabilities in the background.

So even though the two distributions are equally likely.

And then our initial audition say uniform distribution because of the difference

in the background of the distribution, we have different guess the probability.

So these words are believed to be more likely from the topic.

These on the other hand are less likely.

Probably from background.

So once we have these z values,

we know in the M-step these probabilities will be used to adjust the counts.

So four must be multiplied by this 0.33

in order to get the allocated accounts toward the topic.

And this is done by this multiplication.

Note that if our guess says this is 100% If this is one point zero,

then we just get the full count of this word for this topic.

In general it's not going to be one point zero.

So we're just going to get some percentage of this counts toward this topic.

Then we simply normalize these counts

to have a new generation of parameters estimate.

So you can see, compare this with the older one, which is here.

So compare this with this one and we'll see the probability is different.

Not only that, we also see some

words that are believed to have come from the topic will have a higher probability.

Like this one, text.

And of course, this new generation of parameters would allow us to further

adjust the inferred latent variable or hidden variable values.

So we have a new generation of values,

because of the E-step based on the new generation of parameters.

And these new inferred values of Zs will give us then

another generation of the estimate of probabilities of the word.

And so on and so forth so this is what would actually happen when we compute

these probabilities using the EM Algorithm.

As you can see in the last row where we show the log-likelihood,

and the likelihood is increasing as we do the iteration.

And note that these log-likelihood is negative because the probability is

between 0 and 1 when you take a logarithm, it becomes a negative value.

Now what's also interesting is, you'll note the last column.

And these are the inverted word split.

And these are the probabilities that a word is believed to

have come from one distribution, in this case the topical distribution, all right.

And you might wonder whether this would be also useful.

Because our main goal is to estimate these word distributions.

So this is our primary goal.

We hope to have a more discriminative order of distribution.

But the last column is also bi-product.

This also can actually be very useful.

You can think about that.

We want to use, is to for

example is to estimate to what extent this document has covered background words.

And this, when we add this up or

take the average we will kind of know to what extent it has covered background

versus content was that are not explained well by the background.

[MUSIC]

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play