Eine Einführung in das Teil-der-Sprache-Tagging und das Hidden-Markov-Modell

von Sachin Malhotra und Divya Godayal

Gehen wir zurück in die Zeiten, in denen wir keine Sprache hatten, um zu kommunizieren. Der einzige Weg, den wir hatten, war Gebärdensprache. So kommunizieren wir normalerweise zu Hause mit unserem Hund, oder? Als wir ihm sagen: "Wir lieben dich, Jimmy", antwortet er mit dem Schwanz. Das bedeutet nicht, dass er weiß, was wir tatsächlich sagen. Stattdessen reagiert er einfach, weil er die Sprache der Emotionen und Gesten mehr versteht als Worte.

Wir Menschen haben mehr als jedes andere Tier auf diesem Planeten ein Verständnis für viele Nuancen der natürlichen Sprache entwickelt. Deshalb meinen wir verschiedene Dinge, wenn wir sagen "Ich liebe dich, Schatz" oder wenn wir sagen "Lass uns LIEBE machen, Schatz". Da wir den grundlegenden Unterschied zwischen den beiden Phrasen verstehen, sind unsere Antworten sehr unterschiedlich. Es sind genau diese Feinheiten des Verständnisses der natürlichen Sprache, die wir einer Maschine beibringen wollen.

Dies könnte bedeuten, dass Ihr zukünftiger Roboterhund, wenn er „Ich liebe dich, Jimmy“ hört, weiß, dass LIEBE ein Verb ist. Er würde auch erkennen, dass es eine Emotion ist, die wir ausdrücken, auf die er auf eine bestimmte Weise reagieren würde. Und wenn Sie Ihrem Partner sagen "Lets make LOVE", bleibt der Hund vielleicht einfach aus Ihrem Geschäft heraus?

Dies ist nur ein Beispiel dafür, wie das Unterrichten eines Roboters in einer uns bekannten Sprache die Kommunikation erleichtern kann.

Der primäre Anwendungsfall, der in diesem Beispiel hervorgehoben wird, ist, wie wichtig es ist, den Unterschied in der Verwendung des Wortes LIEBE in verschiedenen Kontexten zu verstehen.

Tag-of-Speech-Tagging

Schon in jungen Jahren haben wir uns daran gewöhnt, einen Teil der Sprach-Tags zu identifizieren. Lesen Sie beispielsweise einen Satz und identifizieren Sie, welche Wörter als Substantive, Pronomen, Verben, Adverbien usw. fungieren. All dies wird als Teil von Sprach-Tags bezeichnet.

Schauen wir uns die Wikipedia-Definition für sie an:

In der Korpuslinguistik ist das Teil-der-Sprache-Tagging ( POS-Tagging oder PoS-Tagging oder POST ), auch als grammatikalisches Tagging oder Wortkategorie-Disambiguierung bezeichnet , der Vorgang des Markierens eines Wortes in einem Text (Corpus) als einem bestimmten Teil entsprechend der Sprache, basierend auf ihrer Definition und ihrem Kontext, dh ihrer Beziehung zu benachbarten und verwandten Wörtern in einer Phrase, einem Satz oder einem Absatz. Eine vereinfachte Form davon wird üblicherweise Kindern im schulpflichtigen Alter bei der Identifizierung von Wörtern als Substantive, Verben, Adjektive, Adverbien usw. beigebracht.

Das Identifizieren eines Teils von Sprach-Tags ist viel komplizierter als das einfache Zuordnen von Wörtern zu ihrem Teil von Sprach-Tags. Dies liegt daran, dass POS-Tagging nicht generisch ist. Es ist durchaus möglich, dass ein einzelnes Wort in unterschiedlichen Sätzen, basierend auf unterschiedlichen Kontexten, einen anderen Teil der Sprachkennzeichnung enthält. Aus diesem Grund ist eine generische Zuordnung für POS-Tags nicht möglich.

Wie Sie sehen können, ist es nicht möglich, verschiedene Teil-der-Sprache-Tags für einen bestimmten Korpus manuell zu ermitteln. In Wörterbüchern in verschiedenen Sprachen tauchen immer wieder neue Arten von Kontexten und Wörtern auf, und die manuelle POS-Kennzeichnung ist an sich nicht skalierbar. Deshalb setzen wir auf maschinenbasiertes POS-Tagging.

Bevor wir fortfahren und untersuchen, wie ein Teil der Sprachkennzeichnung durchgeführt wird, sollten wir uns ansehen, warum eine POS-Kennzeichnung erforderlich ist und wo sie verwendet werden kann.

Warum Teil-der-Sprache-Kennzeichnung?

Part-of-Speech-Tagging an sich ist möglicherweise nicht die Lösung für ein bestimmtes NLP-Problem. Dies ist jedoch eine Voraussetzung, um viele verschiedene Probleme zu vereinfachen. Betrachten wir einige Anwendungen der POS-Kennzeichnung in verschiedenen NLP-Aufgaben.

Konvertierung von Text in Sprache

Schauen wir uns den folgenden Satz an:

They refuse to permit us to obtain the refuse permit.

Das Wort refusewird in diesem Satz zweimal verwendet und hat hier zwei verschiedene Bedeutungen. refUSE (/ rəˈfyo͞oz /) ist ein Verb, das „leugnen“ bedeutet, während REFuse (/ ˈrefˌyo͞os /) ein Substantiv ist, das „Müll“ bedeutet (dh, sie sind keine Homophone). Wir müssen also wissen, welches Wort verwendet wird, um den Text richtig auszusprechen. (Aus diesem Grund führen Text-zu-Sprache-Systeme normalerweise eine POS-Kennzeichnung durch.)

Schauen Sie sich die Teil-der-Sprache-Tags an, die vom NLTK-Paket für diesen Satz generiert wurden.

>>> 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')]

Wie aus den Ergebnissen des NLTK-Pakets hervorgeht, unterscheiden sich die POS-Tags für refUSE und REFuse . Die Verwendung dieser beiden unterschiedlichen POS-Tags für unseren Text-zu-Sprache-Konverter kann zu unterschiedlichen Klängen führen.

Schauen wir uns in ähnlicher Weise eine weitere klassische Anwendung der POS-Kennzeichnung an: die Begriffsklärung.

Begriffsklärung

Reden wir über dieses Kind namens Peter. Da seine Mutter Neurologin ist, hat sie ihn nicht zur Schule geschickt. Sein Leben war frei von Naturwissenschaften und Mathematik.

Eines Tages führte sie ein Experiment durch und ließ ihn für einen Mathekurs sitzen. Obwohl er keine Vorkenntnisse hatte, glaubte Peter, seinen ersten Test bestanden zu haben. Seine Mutter nahm dann ein Beispiel aus dem Test und veröffentlichte es wie folgt. (Ein großes Lob an sie!)

Wörter kommen oft in unterschiedlichen Sinnen als unterschiedliche Wortarten vor. Zum Beispiel:

  • Sie sah einen Bären.
  • Ihre Bemühungen werden Früchte tragen .

Das Wort Bär in den obigen Sätzen hat völlig andere Sinne, aber was noch wichtiger ist, eines ist ein Substantiv und das andere ein Verb. Eine rudimentäre Begriffsklärung ist möglich, wenn Sie Wörter mit ihren POS-Tags versehen können.

Die Wortsinn-Disambiguierung (WSD) identifiziert, welcher Sinn eines Wortes (dh welche Bedeutung) in einem Satz verwendet wird, wenn das Wort mehrere Bedeutungen hat.

Versuchen Sie, sich die verschiedenen Bedeutungen für diesen Satz vorzustellen:

Die Zeit vergeht wie im Flug

Hier sind die verschiedenen Interpretationen des gegebenen Satzes. Die Bedeutung und damit der Wortart können für jedes Wort variieren.

As we can clearly see, there are multiple interpretations possible for the given sentence. Different interpretations yield different kinds of part of speech tags for the words.This information, if available to us, can help us find out the exact version / interpretation of the sentence and then we can proceed from there.

The above example shows us that a single sentence can have three different POS tag sequences assigned to it that are equally likely. That means that it is very important to know what specific meaning is being conveyed by the given sentence whenever it’s appearing. This is word sense disambiguation, as we are trying to find out THE sequence.

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

Der automatische Teil der Sprachkennzeichnung ist ein Bereich der Verarbeitung natürlicher Sprache, in dem statistische Techniken erfolgreicher waren als regelbasierte Methoden.

Typische regelbasierte Ansätze verwenden Kontextinformationen, um unbekannten oder mehrdeutigen Wörtern Tags zuzuweisen. Die Disambiguierung erfolgt durch Analyse der sprachlichen Merkmale des Wortes, seines vorhergehenden Wortes, seines folgenden Wortes und anderer Aspekte.

Wenn das vorhergehende Wort beispielsweise ein Artikel ist, muss das betreffende Wort ein Substantiv sein. Diese Informationen sind in Form von Regeln codiert.

Beispiel einer Regel:

Wenn vor einem mehrdeutigen / unbekannten Wort X ein Bestimmer steht und ein Substantiv folgt, kennzeichnen Sie es als Adjektiv.

Das manuelle Definieren eines Regelsatzes ist ein äußerst umständlicher Prozess und überhaupt nicht skalierbar. Wir brauchen also eine automatische Methode, um dies zu tun.

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.

Sie können den Raum jedoch nicht wieder betreten, da dies Peter sicherlich wecken würde. Sie müssen sich also nur für die Geräusche entscheiden, die aus dem Raum kommen können. Entweder ist der Raum ruhig oder es kommt Lärm aus dem Raum. Das sind deine Staaten.

Bevor Peters Mutter dich diesem Albtraum überließ, sagte sie:

Möge der Sound mit dir sein :)

Seine Mutter hat Ihnen das folgende Zustandsdiagramm gegeben. Das Diagramm enthält einige Zustände, Beobachtungen und Wahrscheinlichkeiten.

Beachten Sie, dass es keinen direkten Zusammenhang zwischen dem Geräusch aus dem Raum und dem Einschlafen von Peter gibt.

Es gibt zwei Arten von Wahrscheinlichkeiten, die wir aus dem Zustandsdiagramm ersehen können.

  • Eines ist die EmissionWahrscheinlichkeiten, die die Wahrscheinlichkeiten für bestimmte Beobachtungen in einem bestimmten Zustand darstellen. Zum Beispiel haben wir P(noise | awake) = 0.5. Dies ist eine Emissionswahrscheinlichkeit.
  • Der andere ist der ÜbergangWahrscheinlichkeiten, die die Wahrscheinlichkeit des Übergangs in einen anderen Zustand bei einem bestimmten Zustand darstellen. Zum Beispiel haben wir P(asleep | awake) = 0.4. Dies ist eine Übergangswahrscheinlichkeit.

Die Markovian-Eigenschaft gilt auch für dieses Modell. Machen Sie die Dinge also nicht zu kompliziert. Markov, dein Retter sagte:

Gehen Sie nicht zu viel in die Geschichte ein ...

Die Markov-Eigenschaft, wie sie für das hier betrachtete Beispiel anwendbar wäre, wäre, dass die Wahrscheinlichkeit, dass sich Peter in einem Zustand befindet, NUR vom vorherigen Zustand abhängt.

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!