Вступ до позначення частковою мовою та прихованої моделі Маркова

Сачін Малхотра та Дівія Годаял

Давайте повернемось у часи, коли у нас не було мови для спілкування. Єдиний спосіб, яким ми мали, - це мова жестів. Ось так ми зазвичай спілкуємося з собакою вдома, так? Коли ми говоримо йому: "Ми любимо тебе, Джиммі", він відповідає, махаючи хвостом. Це не означає, що він знає, що ми насправді говоримо. Натомість його відповідь полягає просто в тому, що він розуміє мову емоцій та жестів більше, ніж слова.

Ми як люди розвинули розуміння багатьох нюансів природної мови більше, ніж будь-яка тварина на цій планеті. Ось чому, коли ми говоримо «Я КОХАЮ тебе, милий», а коли ми говоримо «Давайте зробимо ЛЮБОВ, милий», ми маємо на увазі різні речі. Оскільки ми розуміємо основну різницю між двома фразами, наші відповіді дуже різні. Саме ці тонкощі в розумінні природної мови ми хочемо навчити машині.

Що це може означати, коли ваш майбутній собака-робот почує “Я люблю тебе, Джиммі”, він знатиме ЛЮБОВ - це дієслово. Він також зрозумів би, що це емоція, яку ми виражаємо, на яку він відповість певним чином. І, можливо, коли ви говорите своєму партнерові “Давайте зробимо ЛЮБОВ”, собака просто залишатиметься поза вашим бізнесом?

Це лише приклад того, як навчити робота спілкуватися відомою нам мовою може полегшити ситуацію.

Основний випадок використання, який висвітлюється в цьому прикладі, - це те, наскільки важливо розуміти різницю у вживанні слова ЛЮБОВ у різних контекстах.

Позначення частковою мовою

З дуже малого віку ми звикли ідентифікувати частину мовних тегів. Наприклад, читаючи речення та вміючи визначати, які слова виступають як іменники, займенники, дієслова, прислівники тощо. Все це називається частиною мовних тегів.

Давайте подивимось на визначення Вікіпедії для них:

У корпусній лінгвістиці тегування частини мови ( тегування POS або тег PoS або POST ), яке також називають граматичним позначенням або неоднозначністю категорій слів , - це процес позначення слова в тексті (корпусі) як відповідного певній частині мовлення, засноване як на його визначенні, так і на контексті, тобто на його взаємозв’язку із сусідніми та спорідненими словами у фразі, реченні чи абзаці. Спрощену форму цього зазвичай викладають діти шкільного віку, визначаючи слова як іменники, дієслова, прикметники, прислівники тощо.

Визначення частин мовних тегів набагато складніше, ніж просто зіставлення слів із їх частиною мовних тегів. Це пов’язано з тим, що позначення POS не є загальним. Цілком можливо, щоб одне слово мало різну частину мови в різних реченнях на основі різних контекстів. Ось чому неможливо мати загальне відображення для POS-тегів.

Як бачите, неможливо вручну знайти різні теги часткової мови для даного корпусу. Нові типи контекстів і нові слова постійно з’являються у словниках різними мовами, а ручне позначення POS не масштабоване саме по собі. Ось чому ми покладаємося на машинне позначення POS-тегами.

Перш ніж продовжувати далі і розглядати, як робиться позначення частковою мовою, ми повинні розглянути, чому необхідне позначення POS і де його можна використовувати.

Чому позначення частковою мовою?

Позначення частковою мовою саме по собі може не бути рішенням якоїсь конкретної проблеми НЛП. Однак це робиться як необхідна умова для спрощення багатьох різних проблем. Давайте розглянемо декілька застосувань тегування POS в різних завданнях NLP.

Перетворення тексту в мову

Давайте розглянемо таке речення:

They refuse to permit us to obtain the refuse permit.

У refuseцьому реченні це слово вживається двічі і тут має два різні значення. refUSE (/ rəˈfyo͞oz /) - дієслово, що означає «заперечувати», тоді як REFuse (/ ˈrefˌyo͞os /) - іменник, що означає «сміття» (тобто вони не є омофонами). Отже, нам потрібно знати, яке слово використовується, щоб правильно вимовляти текст. (З цієї причини системи перетворення тексту в мову зазвичай виконують позначення POS-тегами.)

Погляньте на теги часткової мови, створені саме для цього речення пакетом NLTK.

>>> text = word_tokenize("They refuse to permit us to obtain the refuse permit")>>> nltk.pos_tag(text)[('They', 'PRP'), ('refuse', 'VBP'), ('to', 'TO'), ('permit', 'VB'), ('us', 'PRP'),('to', 'TO'), ('obtain', 'VB'), ('the', 'DT'), ('refuse', 'NN'), ('permit', 'NN')]

Як ми бачимо з результатів, наданих пакетом NLTK, POS-теги як для REFUSE, так і для REFuse відрізняються. Використовуючи ці два різні POS-теги для нашого перетворювача тексту в мову, можна створити різний набір звуків.

Подібним чином, давайте розглянемо ще одне класичне застосування позначення POS: неоднозначність сенсу слова.

Значення слова Sense

Давайте поговоримо про цього хлопця, якого звали Пітер. Оскільки його мати - невролог, вона не віддала його до школи. Його життя було позбавлене науки та математики.

Одного разу вона провела експеримент і змусила його сидіти на уроці математики. Незважаючи на те, що він не мав жодних попередніх предметних знань, Пітер думав, що пройшов перший тест. Потім його мати взяла приклад із тесту і опублікувала його, як показано нижче. (Похвала їй!)

Слова часто трапляються в різних сенсах як різні частини мови. Наприклад:

  • Вона побачила ведмедя.
  • Ваші зусилля дадуть свої плоди.

Слово ведмідь у вищезазначених реченнях має абсолютно різні значення, але що важливіше одне - це іменник, а інше - дієслово. Рудиментарне розмислення понять слів можливе, якщо ви можете позначати слова їх POS-мітками.

Словочуттєва неоднозначність (WSD) - це визначення того, який сенс слова (тобто яке значення) використовується в реченні, коли слово має кілька значень.

Спробуйте подумати про різні значення цього речення:

Час летить, як стріла

Ось різні тлумачення поданого речення. Значення і, отже, частина мови можуть відрізнятися для кожного слова.

Як ми чітко бачимо, для даного речення можливо декілька тлумачень. Різні тлумачення дають різні види міток частини мови для слів. Ця інформація, якщо вона нам доступна, може допомогти нам з’ясувати точну версію / тлумачення речення, а потім ми можемо продовжувати звідти.

Наведений вище приклад показує нам, що в одному реченні можуть бути призначені три різні послідовності тегів POS, які є однаково ймовірними. Це означає, що дуже важливо знати, який конкретний зміст передається даним реченням, коли воно з’являється. Це неоднозначність сенсу слова, оскільки ми намагаємося з’ясувати послідовність.

These are just two of the numerous applications where we would require POS tagging. There are other applications as well which require POS tagging, like Question Answering, Speech Recognition, Machine Translation, and so on.

Now that we have a basic knowledge of different applications of POS tagging, let us look at how we can go about actually assigning POS tags to all the words in our corpus.

Types of POS taggers

POS-tagging algorithms fall into two distinctive groups:

  • Rule-Based POS Taggers
  • Stochastic POS Taggers

E. Brill’s tagger, one of the first and most widely used English POS-taggers, employs rule-based algorithms. Let us first look at a very brief overview of what rule-based tagging is all about.

Rule-Based Tagging

Автоматичне позначення частини мови - це область обробки природної мови, де статистичні методи були більш успішними, ніж методи, засновані на правилах.

Типові підходи, засновані на правилах, використовують контекстну інформацію для присвоєння тегів невідомим або неоднозначним словам. Неоднозначність здійснюється шляхом аналізу мовних особливостей слова, попереднього слова, наступного слова та інших аспектів.

Наприклад, якщо попереднє слово - стаття, то це слово повинно бути іменником. Ця інформація закодована у вигляді правил.

Приклад правила:

Якщо перед двозначним / невідомим словом X стоїть визначник, а за ним - іменник, позначте його як прикметник.

Визначення набору правил вручну є надзвичайно громіздким процесом і не є масштабованим взагалі. Отже, нам потрібен якийсь автоматичний спосіб зробити це.

The Brill’s tagger is a rule-based tagger that goes through the training data and finds out the set of tagging rules that best define the data and minimize POS tagging errors. The most important point to note here about Brill’s tagger is that the rules are not hand-crafted, but are instead found out using the corpus provided. The only feature engineering required is a set of rule templates that the model can use to come up with new features.

Let’s move ahead now and look at Stochastic POS tagging.

Stochastic Part-of-Speech Tagging

The term ‘stochastic tagger’ can refer to any number of different approaches to the problem of POS tagging. Any model which somehow incorporates frequency or probability may be properly labelled stochastic.

The simplest stochastic taggers disambiguate words based solely on the probability that a word occurs with a particular tag. In other words, the tag encountered most frequently in the training set with the word is the one assigned to an ambiguous instance of that word. The problem with this approach is that while it may yield a valid tag for a given word, it can also yield inadmissible sequences of tags.

An alternative to the word frequency approach is to calculate the probability of a given sequence of tags occurring. This is sometimes referred to as the n-gram approach, referring to the fact that the best tag for a given word is determined by the probability that it occurs with the n previous tags. This approach makes much more sense than the one defined before, because it considers the tags for individual words based on context.

The next level of complexity that can be introduced into a stochastic tagger combines the previous two approaches, using both tag sequence probabilities and word frequency measurements. This is known as the Hidden Markov Model (HMM).

Before proceeding with what is a HiddenMarkov Model, let us first look at what is a Markov Model. That will better help understand the meaning of the term Hiddenin HMMs.

Markov Model

Say that there are only three kinds of weather conditions, namely

  • Rainy
  • Sunny
  • Cloudy

Now, since our young friend we introduced above, Peter, is a small kid, he loves to play outside. He loves it when the weather is sunny, because all his friends come out to play in the sunny conditions.

He hates the rainy weather for obvious reasons.

Every day, his mother observe the weather in the morning (that is when he usually goes out to play) and like always, Peter comes up to her right after getting up and asks her to tell him what the weather is going to be like. Since she is a responsible parent, she want to answer that question as accurately as possible. But the only thing she has is a set of observations taken over multiple days as to how weather has been.

How does she make a prediction of the weather for today based on what the weather has been for the past N days?

Say you have a sequence. Something like this:

Sunny, Rainy, Cloudy, Cloudy, Sunny, Sunny, Sunny, Rainy

So, the weather for any give day can be in any of the three states.

Let’s say we decide to use a Markov Chain Model to solve this problem. Now using the data that we have, we can construct the following state diagram with the labelled probabilities.

In order to compute the probability of today’s weather given N previous observations, we will use the Markovian Property.

Markov Chain is essentially the simplest known Markov model, that is it obeys the Markov property.

The Markov property suggests that the distribution for a random variable in the future depends solely only on its distribution in the current state, and none of the previous states have any impact on the future states.

For a much more detailed explanation of the working of Markov chains, refer to this link.

Also, have a look at the following example just to see how probability of the current state can be computed using the formula above, taking into account the Markovian Property.

Apply the Markov property in the following example.

We can clearly see that as per the Markov property, the probability of tomorrow's weather being Sunny depends solely on today's weather and not on yesterday's .

Let us now proceed and see what is hidden in the Hidden Markov Models.

Hidden Markov Model

It’s the small kid Peter again, and this time he’s gonna pester his new caretaker — which is you. (Ooopsy!!)

As a caretaker, one of the most important tasks for you is to tuck Peter into bed and make sure he is sound asleep. Once you’ve tucked him in, you want to make sure he’s actually asleep and not up to some mischief.

Тим не менш, ти не можеш знову зайти до кімнати, оскільки це, безперечно, розбудить Петра. Отже, все, що вам потрібно вирішити, - це шуми, які можуть доноситись із кімнати. Або в кімнаті тихо, або з кімнати долинає шум . Це ваші штати.

Мати Пітера перед тим, як залишити вас до цього кошмару, сказала:

Нехай звук буде з вами :)

Його мати подала вам наступну діаграму стану. Діаграма має деякі стани, спостереження та ймовірності.

Зверніть увагу, що немає прямої кореляції між звуком із кімнати та тим, як Петро спить.

Існує два види ймовірностей, які ми можемо побачити з діаграми стану.

  • Одним з них є викидиймовірності, що представляють ймовірності здійснення певних спостережень за певного стану. Наприклад, маємо P(noise | awake) = 0.5. Це ймовірність викидів.
  • Інший - це перехідймовірності, що представляють ймовірність переходу в інший стан за певного стану. Наприклад, маємо P(asleep | awake) = 0.4. Це ймовірність переходу.

Властивість Маркова застосовується і в цій моделі. Тож не надто ускладнюйте справи. Марков, твій спаситель сказав:

Не заглиблюйтеся в історію ...

Властивість Маркова, як це було б застосовано до прикладу, який ми розглядали тут, полягала б у тому, що ймовірність перебування Петра в стані залежить ТІЛЬКИ від попереднього стану.

But there is a clear flaw in the Markov property. If Peter has been awake for an hour, then the probability of him falling asleep is higher than if has been awake for just 5 minutes. So, history matters. Therefore, the Markov state machine-based model is not completely correct. It’s merely a simplification.

The Markov property, although wrong, makes this problem very tractable.

We usually observe longer stretches of the child being awake and being asleep. If Peter is awake now, the probability of him staying awake is higher than of him going to sleep. Hence, the 0.6 and 0.4 in the above diagram.P(awake | awake) = 0.6 and P(asleep | awake) = 0.4

Before actually trying to solve the problem at hand using HMMs, let’s relate this model to the task of Part of Speech Tagging.

HMMs for Part of Speech Tagging

We know that to model any problem using a Hidden Markov Model we need a set of observations and a set of possible states. The states in an HMM are hidden.

In the part of speech tagging problem, the observations are the words themselves in the given sequence.

As for the states, which are hidden, these would be the POS tags for the words.

The transition probabilities would be somewhat like P(VP | NP) that is, what is the probability of the current word having a tag of Verb Phrase given that the previous tag was a Noun Phrase.

Emission probabilities would be P(john | NP) or P(will | VP) that is, what is the probability that the word is, say, John given that the tag is a Noun Phrase.

Note that this is just an informal modeling of the problem to provide a very basic understanding of how the Part of Speech tagging problem can be modeled using an HMM.

How do we solve this?

Coming back to our problem of taking care of Peter.

Irritated are we ? ?.

Our problem here was that we have an initial state: Peter was awake when you tucked him into bed. After that, you recorded a sequence of observations, namely noise or quiet, at different time-steps. Using these set of observations and the initial state, you want to find out whether Peter would be awake or asleep after say N time steps.

We draw all possible transitions starting from the initial state. There’s an exponential number of branches that come out as we keep moving forward. So the model grows exponentially after a few time steps. Even without considering any observations. Have a look at the model expanding exponentially below.

If we had a set of states, we could calculate the probability of the sequence. But we don’t have the states. All we have are a sequence of observations. This is why this model is referred to as the Hidden Markov Model — because the actual states over time are hidden.

So, caretaker, if you’ve come this far it means that you have at least a fairly good understanding of how the problem is to be structured. All that is left now is to use some algorithm / technique to actually solve the problem. For now, Congratulations on Leveling up!

In the next article of this two-part series, we will see how we can use a well defined algorithm known as the Viterbi Algorithm to decode the given sequence of observations given the model. See you there!