Viterbi algorithm: what are the most probable tags?

Loading...

來自 National Research University Higher School of Economics 的課程

Natural Language Processing

143 個評分

National Research University Higher School of Economics

Natural Language Processing

143 個評分

課程 6（共 7 門，Specialization Advanced Machine Learning）

This course covers a wide range of tasks in Natural Language Processing from basic to advanced: sentiment analysis, summarization, dialogue state tracking, to name a few. Upon completing, you will be able to recognize NLP tasks in your day-to-day work, propose approaches, and judge what techniques are likely to work well. The final project is devoted to one of the most hot topics in today’s NLP. You will build your own conversational chat-bot that will assist with search on StackOverflow website. The project will be based on practical assignments of the course, that will give you hands-on experience with such tasks as text classification, named entities recognition, and duplicates detection. Throughout the lectures, we will aim at finding a balance between traditional and deep learning techniques in NLP and cover them in parallel. For example, we will discuss word alignment models in machine translation and see how similar it is to attention mechanism in encoder-decoder neural networks. Core techniques are not treated as black boxes. On the contrary, you will get in-depth understanding of what’s happening inside. To succeed in that, we expect your familiarity with the basics of linear algebra and probability theory, machine learning setup, and deep neural networks. Some materials are based on one-month-old papers and introduce you to the very state-of-the-art in NLP research.

從本節課中

Language modeling and sequence tagging

In this module we will treat texts as sequences of words. You will learn how to predict next words given some previous words. This task is called language modeling and it is used for suggests in search, machine translation, chat-bots, etc. Also you will learn how to predict a sequence of tags for a sequence of words. It could be used to determine part-of-speech tags, named entities or any other tags, e.g. ORIG and DEST in "flights from Moscow to Zurich" query. We will cover methods based on probabilistic graphical models and deep learning.

Hidden Markov Models13:42

Viterbi algorithm: what are the most probable tags?11:22

MEMMs, CRFs and other sequential models for Named Entity Recognition11:53

與講師見面

Anna Potapenko
Researcher
HSE Faculty of Computer Science
Alexey Zobnin
Accosiate professor
HSE Faculty of Computer Science
Anna Kozlova
Team Lead
Yandex
Sergey Yudin
Analyst-developer
Yandex
Andrei Zimovnov
Senior Lecturer
HSE Faculty of Computer Science

[MUSIC]

Hey, in the previous video we discussed that there is Hidden Markov Model that can

be used for part-of-speech tagging.

We have briefly discussed how to train this model,

now how can we apply this to our texts?

This slide is just a motivation for

the next video, to show you that it is actually not that simple problem.

So for example, you can see a sequence of words, a bear likes honey, and

you can see that it can be decoded in different ways.

So the sequence of text in the top and in the bottom of the slides are both valid.

So both sequences could generate this piece of text, right?

This is because we have very ambiguous language.

For example, likes can be noun, or

verb, or something else maybe, if we think about it.

Okay, then how can we generate the most

probable sequence of text given a piece of text?

This is called decoding problem, and this is formalized in the bottom of the slide.

So we need to find y which maximizes the probability of y given x.

And as we have briefly discussed, it would be the same as y

that maximizes the probability of both variables.

Now could we probably just compute the probabilities of

all ys, and then choose the best one?

Well not actually,

because this brute force approach would be really slow, right?

Or maybe not feasible at all,

because you have very many different sequences of text.

Let's say you have big T which is the length of the sentence, and

you have 10 possible states.

Then you will have T to the power of 10 different sequences, right?

So this is too much, but fortunately there is

an algorithm based on dynamic programming that can help us to do this effectively.

Before we go to it, I just want to recap the main formula for Hidden Markov Model.

So please remember that we have the probabilities of y given the previous y,

which are called transition probabilities, and then we have output probabilities.

And we multiply them by the positions to get our total

probability of both variables.

Okay, so this is probably the main slide here,

which tells you what is Viterbi algorithm.

Let us go through it slowly.

We would like to find a sequence of text that is

the most probable to generate our output sentence.

However, we can do it straightforwardly.

So let us first start with finding the most probable sequences of text,

up to the moment t, that finishes in the state s.

So those big Qt,s things.

And let us denote by small qt,s the probabilities of those sequences.

Now, how can we compute those probabilities effectively?

We can say that once we have computed them for the time moment t-1,

we can use that to compute the next probabilities for the next time moment.

How do we do this?

Well we see that we have our transition probabilities and

output probabilities, as is said by the Hidden Markov Model.

And then we have these green qt-1 probabilities that hide the transition

probabilities and output probabilities for all the previous time moments.

Okay, and then we apply maximum because remember,

we are only interested in the most probable sequences.

Now when we compute these probabilities we are also interested

in the argmax, because the argmax will tell us

what are the states where these probabilities can be found.

Okay, probably it is not yet clear for you, so during the video I am going

to show you lots of pictures and examples that explain how this algorithm works.

Let us say that we have some Hidden Markov Model, and it is already trained for us.

So this is A matrix,

which has probabilities of some states given some other states, right?

Our transition probabilities.

Each row sums into 1, which means that we have indeed correct probabilities.

Now I have a question for

you, do you think that something is missing in this matrix?

So if you remember from the previous video,

we had also our special start state.

And we will need to have a special first row in this matrix that will

have the probabilities of some states given this special start state.

For now, let's say that this row is just filled with equal probabilities, so

it is just a uniform distribution.

Okay, so we have these parameters for A matrix, and

we have this B matrix which tells us the probabilities

of the output tokens given some states.

Awesome, now let us imagine that our probability algorithm

has already computed the probabilities up to some moment.

So we have some probabilities up to the bear in our sequence.

Now how can we compute the probabilities for the next time moment?

For the first state, for ADJ state,

we can try to go from different previous states.

And we have transition probabilities, different transition probabilities for

each of them.

And we have also the output probabilities to generate likes in this case.

Now we need to find maximum, so we need to find the best way.

And in this case, it will be this one.

So we find this way, and

we say that the probability is now composed by three things.

The previous probability that we had so far, the transition probability, and

the output probability.

Now let us try to do the same for the next state.

So another state is NOUN, and we again need to compare different paths.

So we have three paths, which one would be chosen this time?

So this time we will choose this one, because the multiplication

of three components again will be maximum for this one, right?

So this will be that value, and we could compute this.

Now we perform the same thing for the last state.

So here we have this path, we choose this one, and compute the probabilities.

And are we done?

Well we could compute the probabilities for the next time moment,

and this way we can move forward.

But it is very important to remember the best transitions that we used.

Why?

Because this is how we are going to find our best path for the states.

This is what we compute for every time moment.

Now let us zoom out and see what is happening for the whole sentence.

So this is what you get if you compute all the probabilities and

remember all the best transitions.

Now once again, what are those best transitions?

So for example, the path that goes through ADJ, NOUN, VERB and

NOUN is the most probable sequence of text that generates

our sentence and finishes in the state NOUN, okay?

This is just the definition.

And the probability of this path is written down there, near the NOUN.

Okay, so what do we need to compute now?

We have these three candidates

that can finish in one of the three states for honey.

Remember, we need the most probable one ever.

So we need to compute maximum once again.

We need to compute maximum, it would be NOUN.

And then we take it and

we say that okay, the last state in our sequence should be NOUN.

And then we backtrace to VERB, to NOUN, and

to ADJ to get the sequence of text that is the best in this case.

Awesome, we are done with the pictures.

This slide just summarizes everything that we have already said.

So to create your best path you need to first allocate an array

queue of the dimension the number of words in your sentence,

by the number of states in your model.

Then you need to fill the first column in your matrix, right?

So for the first time moment it is rather easy to compute the probabilities of

the states.

This would be just the probabilities to come to these states

from the initial start state,

multiplied by the probability to output the first word in this current state.

Now after that you have a loop.

So you go through all your positions in time, and you go through all your steps,

and compute those max values and argmax values.

After that you have your last column.

You apply argmax once again to find what would be the pick for

the last word in your sentence.

After that you backtrace all your text for the path.

And you are done, you get your best path.

So this is decoding in Hidden Markov Models.

And this is real useful, not only in part-of-speech tagging actually, but also,

for example, for some signals and other source of data where

you have different states that can generate some outputs.

So this is all for this video.

And in the next one,

we will discuss a few more models that are similar to Hidden Markov Model.

[MUSIC]

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2018 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取