4.9 Text Categorization: Generative Probabilistic Models

Loading...

En provenance du cours de University of Illinois at Urbana-Champaign

Text Mining and Analytics

305 notes

University of Illinois at Urbana-Champaign

Text Mining and Analytics

305 notes

Cours 3 sur 6 dans 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.

À partir de la leçon

Week 4

During this module, you will learn text clustering, including the basic concepts, main clustering techniques, including probabilistic approaches and similarity-based approaches, and how to evaluate text clustering. You will also start learning text categorization, which is related to text clustering, but with pre-defined categories that can be viewed as pre-defining clusters.

4.1 Text Clustering: Motivation15:52

4.2 Text Clustering: Generative Probabilistic Models Part 116:18

4.3 Text Clustering: Generative Probabilistic Models Part 28:37

4.4 Text Clustering: Generative Probabilistic Models Part 314:55

4.5 Text Clustering: Similarity-based Approaches17:48

4.6 Text Clustering: Evaluation10:11

4.7 Text Categorization: Motivation14:37

4.8 Text Categorization: Methods11:50

4.9 Text Categorization: Generative Probabilistic Models31:18

Rencontrer les enseignants

ChengXiang Zhai
Professor
Department of Computer Science

[SOUND] This lecture is

about how to use generative probabilistic models for text categorization.

There are in general about two kinds of approaches to text categorization

by using machine learning.

One is by generating probabilistic models.

The other is discriminative approaches.

In this lecture, we're going to talk about the generative models.

In the next lecture, we're going to talk about discriminative approaches.

So the problem of text categorization

is actually a very similar to document clustering.

In that, we'll assume that each document it belongs to one category or one cluster.

The main difference is that in clustering we don't really know

what are the predefined categories are, what are the clusters.

In fact, that's the goal of text clustering.

We want to find such clusters in the data.

But in the case of categorization, we are given the categories.

So we kind of have pre-defined categories and

then based on these categories and training data, we would like to allocate

a document to one of these categories or sometimes multiple categories.

But because of the similarity of the two problems,

we can actually get the document clustering models for text categorization.

And we understand how we can use generated models to do

text categorization from the perspective of clustering.

And so, this is a slide that we've talked about before, about text clustering,

where we assume there are multiple topics represented by word distributions.

Each topic is one cluster.

So once we estimated such a model,

we faced a problem of deciding which cluster document d should belong to.

And this question boils down to decide which theta i has been used to generate d.

Now, suppose d has L words represented as xi here.

Now, how can you compute the probability that a particular

topic word distribution zeta i has been used to generate this document?

Well, in general, we use base wall to make this influence and

you can see this prior information here that we need to consider if a topic or

cluster has a higher prior then it's more likely

that the document has been from this cluster.

And so, we should favor such a cluster.

The other is a likelihood part, it's this part.

And this has to do with whether the topic word of distribution

can explain the content of this document well.

And we want to pick a topic that's high by both values.

So more specifically, we just multiply them together and

then choose which topic has the highest product.

So more rigorously, this is what we'd be doing.

So we're going to choose the topic that would maximize.

This posterior probability at the top of a given document gets posterior

because this one, p of the i, is the prior.

That's our belief about which topic is more likely,

before we observe any document.

But this conditional probability here is

the posterior probability of the topic after we have observed the document of d.

And base wall allows us to update this probability based on the prior and

I have shown the details, below here you can see how

the prior here is related to the posterior, on the left-hand side.

And this is related to how well this word distribution

explains the document here, and the two are related in this way.

So to find the topic that has the higher

posterior probability here it's equivalent to maximize this product

as we have seen also, multiple times in this course.

And we can then change the probability of document in your product of

the probability of each word, and that's just because we've made

an assumption about independence in generating each word.

So this is just something that you have seen in document clustering.

And we now can see clearly how we can assign a document to a category

based on the information about word distributions for

these categories and the prior on these categories.

So this idea can be directly adapted to do categorization.

And this is precisely what a Naive Bayes Classifier is doing.

So here it's most really the same information except

that we're looking at the categorization problem now.

So we assume that if theta i

represents category i accurately, that means the word distribution

characterizes the content of documents in category i accurately.

Then, what we can do is precisely like what we did for text clustering.

Namely we're going to assign document d to the category

that has the highest probability of generating this document.

In other words, we're going to maximize this posterior probability as well.

And this is related to the prior and

the [INAUDIBLE] as you have seen on the previous slide.

And so, naturally we can decompose

this [INAUDIBLE] into a product as you see here.

Now, here, I change the notation so that we will write down the product as

product of all the words in the vocabulary, and

even though the document doesn't contain all the words.

And the product is still accurately representing the product

of all the words in the document because of this count here.

When a word, it doesn't occur in the document.

The count would be 0, so this time will just disappear.

So if actively we'll just have the product over other words in the document.

So basically, with Naive Bayes Classifier,

we're going to score each category for the document by this function.

Now, you may notice that here it involves a product of a lot of small probabilities.

And this can cause and the four problem.

So one way to solve the problem is thru take logarithm of this function,

which it doesn't changes all the often these categories.

But will helps us preserve precision.

And so, this is often the function that we actually use to

score each category and then we're going to choose

the category that has the highest score by this function.

So this is called an Naive Bayes Classifier, now the keyword base is

understandable because we are applying a base rule here when we go from

the posterior probability of the topic to a product of the likelihood and the prior.

Now, it's also called a naive because we've made an assumption that every word

in the document is generated independently, and this is indeed a naive

assumption because in reality they're not generating independently.

Once you see some word, then other words will more likely occur.

For example, if you have seen a word like a text.

Than that mixed category,

they see more clustering more likely to appear than if you have not the same text.

But this assumption allows us to simplify the problem.

And it's actually quite effective for many text categorization tasks.

But you should know that this kind of model doesn't

have to make this assumption.

We could for example, assume that words may be dependent on each other.

So that would make it a bigram analogy model or a trigram analogy model.

And of course you can even use a mixture model to model what the document looks

like in each category.

So in nature, they will be all using base rule to do classification.

But the actual generating model for documents in each category can vary.

And here, we just talk about very simple case perhaps, the simplest case.

So now the question is, how can we make sure theta i

actually represents category i accurately?

Now in clustering, we learned that this category i or

what are the distributions for category i from the data.

But in our case, what can we do to make sure

this theta i represents indeed category i.

Well if you think about the question, and

you likely come up with the idea of using the training data.

Indeed in the textbook,

we typically assume that there is training data available and

those are the documents that unknown to have generator from which category.

In other words, these are the documents with known categories assigned and

of course human experts must do that.

In here, you see that T1 represents the set of documents

that are known to have the generator from category 1.

And T2 represents the documents that are known to have been

generated from category 2, etc.

Now if you look at this picture, you'll see that the model

here is really a simplified unigram language model.

It's no longer mixed modal, why?

Because we already know which distribution has been used to generate which documents.

There's no uncertainty here, there's no mixing of different categories here.

So the estimation problem of course would be simplified.

But in general, you can imagine what we want to do is

estimate these probabilities that I marked here.

And what other probability is that we have to estimate it in order to do relation.

Well there are two kinds.

So one is the prior, the probability of theta i and

this indicates how popular each category is or

how likely will it have observed the document in that category.

The other kind is the water distributions and

we want to know what words have high probabilities for each category.

So the idea then is to just use observe the training data

to estimate these two probabilities.

And in general, we can do this separately for the different categories.

That's just because these documents are known to be generated

from a specific category.

So once we know that,

it's in some sense irrelevant of what other categories we are also dealing with.

So now this is a statistical estimation problem.

We have observed some data from some model and

we want to guess the parameters of this model.

We want to take our best guess of the parameters.

And this is a problem that we have seen also several times in this course.

Now, if you haven't thought about this problem,

haven't seen life based classifier.

It would be very useful for you to pause the video for a moment and

to think about how to solve this problem.

So let me state the problem again.

So let's just think about with category 1,

we know there is one word of distribution that has been used to generate documents.

And we generate each word in the document independently, and we know that we have

observed a set of n sub 1 documents in the set of Q1.

These documents have been all generated from category 1.

Namely have been all generated using this same word distribution.

Now the question is, what would be your guess or

estimate of the probability of each word in this distribution?

And what would be your guess of the entire probability of this category?

Of course, this singular probability depends on

how likely are you to see documents in other categories?

So think for a moment, how do you use all this training data including

all these documents that are known to be in these k categories,

to estimate all these parameters?

Now, if you spend some time to think about this and

it would help you understand the following few slides.

So do spend some time to make sure that you can try to solve this problem, or

do you best to solve the problem yourself.

Now if you have thought about and then you will realize the following to it.

First, what's the bases for estimating the prior or the probability of each category.

Well this has to do with whether you have observed a lot of documents

form that category.

Intuitively, you have seen a lot of documents in sports and

very few in medical science.

Then you guess is that the probability of the sports category is larger or

your prior on the category would be larger.

And what about the basis for estimating the probability of where each category?

Well the same, and you'll be just assuming that words that are observed

frequently in the documents that are known to be generated from a category will

likely have a higher probability.

And that's just a maximum Naive Bayes made of.

Indeed, that's what we can do, so this made the probability of which category and

to answer the question, which category is most popular?

Then we can simply normalize, the count of documents in each category.

So here you see N sub i denotes the number of documents in each category.

And we simply just normalize these counts to make this a probability.

In other words, we make this probability proportional to the size

of training intercept in each category that's a size of the set t sub i.

Now what about the word distribution?

Well, we do the same.

Again this time we can do this for each category.

So let's say, we're considering category i or theta i.

So which word has a higher probability?

Well, we simply count the word occurrences

in the documents that are known to be generated from theta i.

And then we put together all the counts of the same word in the set.

And then we just normalize these counts to make this distribution

of all the words make all the probabilities off these words to 1.

So in this case, you're going to see this is a proportional through the count of

the word in the collection of training documents T sub i and

that's denoted by c of w and T sub i.

Now, you may notice that we often write down probable

estimate in the form of being proportional for certain numbers.

And this is often sufficient,

because we have some constraints on these distributions.

So the normalizer is dictated by the constraint.

So in this case, it will be useful for you to think about

what are the constraints on these two kinds of probabilities?

So once you figure out the answer to this question, and

you will know how to normalize these accounts.

And so this is a good exercise to work on if it's not obvious to you.

There is another issue in Naive Bayes which is a smoothing.

In fact the smoothing is a general problem in older estimate of language morals.

And this has to do with,

what would happen if you have observed a small amount of data?

So smoothing is an important technique to address that outsmarts this.

In our case, the training data can be small and when the data set is small when

we use maximum likely estimator we often face the problem of zero probability.

That means if an event is not observed

then the estimated probability would be zero.

In this case, if we have not seen a word in the training documents for

let's say, category i.

Then our estimator would be zero for the probability of this one in this category,

and this is generally not accurate.

So we have to do smoothing to make sure it's not zero probability.

The other reason for smoothing is that this is a way to bring prior knowledge,

and this is also generally true for a lot of situations of smoothing.

When the data set is small,

we tend to rely on some prior knowledge to solve the problem.

So in this case our [INAUDIBLE] says that no word should have zero probability.

So smoothing allows us to inject these to prior initial that no

order has a real zero probability.

There is also a third reason which us sometimes not very obvious, but

we explain that in a moment.

And that is to help achieve discriminative weighting of terms.

And this is also called IDF weighting,

inverse document frequency weighting that you have seen in mining word relations.

So how do we do smoothing?

Well in general we add pseudo counts to these events,

we'll make sure that no event has 0 count.

So one possible way of smoothing the probability of the category

is to simply add a small non active constant delta to the count.

Let's pretend that every category has actually some extra number of

documents represented by delta.

And in the denominator we also add a k multiplied by delta because

we want the probability to some to 1.

So in total we've added delta k times because we have a k categories.

Therefore in this sum, we have to also add k multiply by

delta as a total pseudocount that we add up to the estimate.

Now, it's interesting to think about the influence of that data,

obvious data is a smoothing parameter here.

Meaning that the larger data is and the more we will do smoothing and

that means we'll more rely on pseudocounts.

And we might indeed ignore the actual counts if they are delta is

set to infinity.

Imagine what would happen if there are approaches positively to infinity?

Well, we are going to say every category has an infinite amount of documents.

And then there's no distinction to them so it become just a uniform.

What if delta is 0?

Well, we just go back to the original estimate based on the observed training

data to estimate to estimate the probability of each category.

Now we can do the same for the word distribution.

But in this case, sometimes we find it useful

to use a nonuniform seudocount for the word.

So here you'll see we'll add a pseudocounts to each word and

that's mule multiplied by the probability of

the word given by a background language model, theta sub b.

Now that background model in general can be estimated by using

a logic collection of tests.

Or in this case we will use the whole set of all the training data to

estimate this background language model.

But we don't have to use this one,

we can use larger test data that are available from somewhere else.

Now if we use such a background language model that has pseudocounts,

we'll find that some words will receive more pseudocounts.

So what are those words?

Well those are the common words because they get a high probability by

the background average model.

So the pseudocounts added for such words will be higher.

Real words on the other hand will have smaller pseudocounts.

Now this addition of background model would cause a nonuniform

smoothing of these word distributions.

We're going to bring the probability of those common words to a higher level,

because of the background model.

Now this helps make the difference of the probability of

such words smaller across categories.

Because every category has some help from the background four words, and

I get the, a, which have high probabilities.

Therefore, it's not always so important that each category

has documents that contain a lot of occurrences of such words or

the estimate is more influenced by the background model.

And the consequence is that when we do categorization,

such words tend not to influence the decision that much

as words that have small probabilities from the background language model.

Those words don't get some help from the background language model.

So the difference would be primary because of the differences of the occurrences

in the training documents in different categories.

We also see another smoothing parameter mu here, which controls the amount of

smoothing and just like a delta does for the other probability.

And you can easily understand why we add mu to the denominator, because that

represents the sum of all the pseudocounts that we add for all the words.

So view is also a non negative constant and

it's [INAUDIBLE] set to control smoothing.

Now there are some interesting special cases to think about as well.

First, let's think about when mu approaches infinity what would happen?

Well in this case the estimate would approach

to the background language model we'll attempt to the background language model.

So we will bring every word distribution to the same background language model and

that essentially remove the difference between these categories.

Obviously, we don't want to do that.

The other special case is the thing about the background model and

suppose, we actually set the two uniform distribution.

And let's say, 1 over the size of the vocabulary.

So each one has the same probability, then this smoothing formula is

going to be very similar to the one on the top when we add delta.

It's because we're going to add a constant pseudocounts to every word.

So in general,

in Naive Bayes categorization we have to do such a small thing.

And then once we have these probabilities,

then we can compute the score for each category.

For a document and

then choose the category where it was the highest score as we discussed earlier.

Now, it's useful to further understand whether

the Naive Bayes scoring function actually makes sense.

So to understand that, and also to understand why adding a background model

will actually achieve the effect of IDF weighting and to penalize common words.

So suppose we have just two categories and

we're going to score based on their ratio of probability, right?

So this is the.

Lets say this is our scoring function for

two categories, right?

So, this is a score of a document for these two categories.

And we're going to score based on this probability ratio.

So if the ratio is larger,

then it means it's more likely to be in category one.

So the larger the score is the more likely

the document is in category one.

So by using Bayes' rule,

we can write down this ratio as follows, and you have seen this before.

Now, we generally take logarithm of this ratio, and to avoid small probabilities.

And this would then give us this formula in the second line.

And here we see something really interesting,

because this is our scoring function for deciding between the two categories.

And if you look at this function, we'll see it has several parts.

The first part here is actually log of probability ratio.

And so this is a category bias.

It doesn't really depend on the document.

It just says which category is more likely and then we would then favor

this category slightly, right?

So, the second part has a sum of all the words, right?

So, these are the words that are observed in the document but

in general we can consider all the words in the vocabulary.

So here we're going to collect the evidence

about which category is more likely, right?

So inside of the sum you can see there is product of two things.

The first, is a count of the word.

And this count of the word serves as a feature to represent the document.

And this is what we can collect from document.

The second part is the weight of this feature,

here it's the weight on which word, right?

This weight tells us to what extent observing

this word helps contribute in our decision

to put this document in category one.

Now remember, the higher the scoring function is,

the more likely it's in category one.

Now if you look at this ratio, basically, sorry this weight it's basically based

on the ratio of the probability of the word from each of the two distributions.

Essentially we're comparing the probability of the word from the two

distributions.

And if it's a higher according to theta 1,

then according to theta 2, then this weight would be positive.

And therefore it means when we observe such a word,

we will say that it's more likely to be from category one.

And the more we observe such a word,

the more likely the document will be classified as theta 1.

If, on the other hand, the probability of the word from

theta 1 is smaller than the probability of the word from theta 2,

then you can see that this word is negative.

Therefore, this is negative evidence for supporting category one.

That means the more we observe such a word,

the more likely the document is actually from theta 2.

So this formula now makes a little sense, right?

So we're going to aggregate all the evidence from the document,

we take a sum of all the words.

We can call this the features

that we collected from the document that would help us make the decision.

And then each feature has a weight that tells us how

does this feature support category one or just support category two.

And this is estimated as the log of probability ratio here in naïve Bayes.

And then finally we have this constant of bias here.

So that formula actually is a formula that can

be generalized to accommodate more features and

that's why I have introduce some other symbols here.

To introduce beta 0 to denote the Bayes and fi to denote the each feature and

beta sub i to denote the weight on each feature.

Now we do this generalisation, what we see is that in

general we can represent the document by feature vector fi,

here of course in this case fi is the count of a word.

But in general, we can put any features that we think are relevant for

categorization.

For example, document length or

font size or count of other patterns in the document.

And then our scoring function can be defined as a sum of a constant beta 0 and

the sum of the feature weights of all the features.

So if each f sub i is a feature value then we multiply the value

by the corresponding weight, beta sub i, and we just take the sum.

And this is the aggregate of all evidence that we can collect from all these

features.

And of course there are parameters here.

So what are the parameters?

Well, these are the betas.

These betas are weights.

And with a proper setting of the weights, then we can expect such a scoring function

to work well to classify documents, just like in the case of naive Bayes.

We can clearly see naive Bayes classifier as a special case of

this general classifier.

Actually, this general form is very close to a classifier called a logistical

regression, and this is actually one of those conditional approaches or

discriminative approaches to classification.

And we're going to talk more about such approaches later, but

here I want you to note that there is a strong connection,

a close connection between the two kinds of approaches.

And this slide shows how naive Bayes classifier can be connected to

a logistic regression.

And you can also see that in discriminative classifiers

that tend to use more general form on the bottom,

we can accommodate more features to solve the problem.

[MUSIC]

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play