Representing Meaning: Unambiguous representation, Canonical form and expressiveness

Meaning representations
• Vector space is one kind of meaning representation. But not
obvious how to deal with compositionality or inference.
• Instead, we can do this with representations that are symbolic
and structured.
• Next lecture, semantic analysis: how to get from sentences to
their meaning representations (using syntax to help).
• But first we need to define the semantics we’re aiming at, i.e., a
meaning representation language (MRL)
 The symbols in our meaning representations correspond to objects,
properties, and relations in the world. The world may be the real world, or
(usually) a formalized and well-specified world: a model or knowledge base of
known facts.
– Ex 1: a tiny world model containing 3 entities, and an exhaustive
table of ‘who loves whom’ relations.
_______________________________________________________
What do we want from an MRL?
Compositional: The meaning of a complex expression is a function
of the meaning of its parts and of the rules by which they are
combined.
Verifiable: Can use the MR of a sentence to determine whether the
sentence is true with respect to some given model of the world.
• In Ex 1 above, can establish the truth value of everybody loves
Mary by checking it against the model.
What do we want from an MRL?
Unambiguous: an MR should have exactly one interpretation. So,
an ambiguous sentence should have a different MR for each sense.
• Ex: each interpretation of I made her duck or time flies like an
arrow should have a distinct MR.
• The job of producing all possible MRs for a given sentence will
go to the semantic analyzer.
• We also defer the question of choosing which interpretation is
correct. Canonical form: sentences with the same (literal) meaning should
have the same MR.
• Ex: I filled the room with balloons should have the same
canonical form as I put enough balloons in the room to fill
it from floor to ceiling.
• Ex: Similarly, Tanjore serves vegetarian food and Vegetarian
dishes are served by Tanjore.
• Simplifies inference and reduces storage needs; but also makes
semantic analysis harder.
Inference: we should be able to verify sentences not only directly,
but also by drawing conclusions based on the input MR and facts in
the knowledge base.
• Ex: from the MR for a query
Did Poland reduce its carbon emissions?
• and the MRs for facts
Carbon emmissions have fallen for all countries in Central
Europe.
Poland is a country in Central Europe.
• we should be able to infer the answer: YES.
Expressivity: the MRL should allow us to handle a wide range of
meanings and express appropriate relationships between the words
in a sentence.
Advantages of Canonical Form:
Uniqueness: The canonical form of a boolean function is unique, which
means that there is only one possible canonical form for a given function.
Clarity: The canonical form of a boolean function provides a clear and
unambiguous representation of the function.
Completeness: The canonical form of a boolean function can represent
any possible boolean function, regardless of its complexity.

Disadvantages of Canonical Form:

Complexity: The canonical form of a boolean function can be complex,
especially for functions with many variables.
Computation: Computing the canonical form of a boolean function can be
computationally expensive, especially for large functions.
Redundancy: The canonical form of a boolean function can be
redundant, which means that it can contain unnecessary terms or
variables that do not affect the function.

Truth table representing minterm and maxterm –

Canonical and Standard Form

Canonical Form – In Boolean algebra, the Boolean function can be
expressed as Canonical Disjunctive Normal Form known as minterm and
some are expressed as Canonical Conjunctive Normal Form known
as maxterm.
In Minterm, we look for the functions where the output results in “1” while
in Maxterm we look for functions where the output results in “0”.
We perform the Sum of minterm also known as the Sum of products
(SOP).
We perform Product of Maxterm also known as Product of sum (POS).
Boolean functions expressed as a sum of minterms or product of
maxterms are said to be in canonical form.

Standard Form – A Boolean variable can be expressed in either true or

complementary forms. In standard form Boolean function will contain all
the variables in either true form or complemented form while in canonical
number of variables depends on the output of SOP or POS.
A Boolean function can be expressed algebraically from a given truth
table by forming a :
 minterm for each combination of the variables that produces a 1 in the
function and then takes the OR of all those terms.
 maxterm for each combination of the variables that produces a 0 in the
function and then takes the AND of all those terms.

Sum of minterms –
The minterms whose sum defines the Boolean function are those which
give the 1’s of the function in a truth table. Since the function can be either
1 or 0 for each minterm, and since there are 2^n minterms, one can
calculate all the functions that can be formed with n variables to be
(2^(2^n)). It is sometimes convenient to express a Boolean function in its
sum of minterm form.

Product of maxterms –
When dealing with Boolean algebra, the product of maxterms is a handy
way to express how combinations of inputs lead to a result of 0. Maxterms
basically tell us which combinations of inputs won’t give us a 1 as an
output. They are the opposite of minterms, which tell us when we get a 1.
 Example – Express the Boolean function F = A + B’C as standard sum
of minterms.
o Solution –
A = A(B + B’) = AB + AB’
This function is still missing one variable, so
A = AB(C + C’) + AB'(C + C’) = ABC + ABC’+ AB’C + AB’C’
The second term B’C is missing one variable; hence,
B’C = B’C(A + A’) = AB’C + A’B’C
Combining all terms, we have
F = A + B’C = ABC + ABC’ + AB’C + AB’C’ + AB’C + A’B’C
But AB’C appears twice, and
according to theorem 1 (x + x = x), it is possible to remove
one of those occurrences. Rearranging the minterms in
ascending order, we finally obtain
 F = A’B’C + AB’C’ + AB’C + ABC’ + ABC
= m1 + m4 + m5 + m6 + m7
SOP is represented as Sigma(1, 4, 5, 6, 7)
 Example – Express the Boolean function F = xy + x’z as a product of
maxterms
o Solution –
F = xy + x’z = (xy + x’)(xy + z) = (x + x’)(y + x’)(x + z)(y + z) =
(x’ + y)(x + z)(y + z)
x’ + y = x’ + y + zz’ = (x’+ y + z)(x’ + y + z’)
x + z = x + z + yy’ = (x + y + z)(x + y’ + z)
y + z = y + z + xx’ = (x + y + z)(x’ + y + z)
F = (x + y + z)(x + y’ + z)(x’ + y + z)(x’ + y + z’)
= M0*M2*M4*M5
POS is represented as Pi(0, 2, 4, 5)
 Example –
o Solution – F(A, B, C) = Sigma(1, 4, 5, 6, 7)
F'(A, B, C) = Sigma(0, 2, 3) = m0 + m2 + m3
Now, if we take the complement of F’ by DeMorgan’s theorem,
we obtain F in a different form:
F = (m0 + m2 + m3)’
= m0’m2’m3′
= M0*M2*M3
= PI(0, 2, 3)
 Example – Convert Boolean expression in standard form F=y’+xz’+xyz
o Solution – F = (x+x’)y'(z+z’)+x(y+y’)z’ +xyz
F = xy’z+ xy’z’+x’y’z+x’y’z’+ xyz’+xy’z’+xyz

Advantages of Standard Form:

Simplicity: The standard form of a boolean function is simpler than the
canonical form, making it easier to understand and work with.
Efficiency: The standard form of a boolean function can be implemented
using fewer logic gates than the canonical form, which makes it more
efficient in terms of hardware and computation.
Flexibility: The standard form of a boolean function can be easily
modified and combined with other functions to create new functions that
meet specific design requirements.

Disadvantages of Standard Form:

Non-uniqueness: The standard form of a boolean function is not unique,
which means that there can be multiple possible standard forms for a
given function.
Incompleteness: The standard form of a boolean function may not be
able to represent some complex boolean functions.
Ambiguity: The standard form of a boolean function can be ambiguous,
especially if it contains multiple equivalent expressions.

Machine learning-based approaches for Word Sense Disambiguation

Word sense disambiguation, in natural language processing (NLP), may be

defined as the ability to determine which meaning of word is activated by the
use of word in a particular context. Lexical ambiguity, syntactic or semantic, is
one of the very first problem that any NLP system faces. Part-of-speech (POS)
taggers with high level of accuracy can solve Words syntactic ambiguity. On the
other hand, the problem of resolving semantic ambiguity is called WSD (word
sense disambiguation). Resolving semantic ambiguity is harder than resolving
syntactic ambiguity.

For example, consider the two examples of the distinct sense that exist for the
word bass −

I can hear bass sound.

He likes to eat grilled bass.

The occurrence of the word bass clearly denotes the distinct meaning. In first
sentence, it means frequency and in second, it means fish. Hence, if it would be
disambiguated by WSD then the correct meaning to the above sentences can be
assigned as follows −

I can hear bass/frequency sound.

He likes to eat grilled bass/fish.

Evaluation of WSD
The evaluation of WSD requires the following two inputs −

A Dictionary
The very first input for evaluation of WSD is dictionary, which is used to
specify the senses to be disambiguated.
Test Corpus
Another input required by WSD is the high-annotated test corpus that has the
target or correct-senses. The test corpora can be of two types &minsu;

Lexical sample − This kind of corpora is used in the system, where it is required
to disambiguate a small sample of words.

All-words − This kind of corpora is used in the system, where it is expected to

disambiguate all the words in a piece of running text.
Approaches and Methods to Word Sense Disambiguation (WSD)
Approaches and methods to WSD are classified according to the source of
knowledge used in word disambiguation.

Four conventional methods to WSD −

Dictionary-based or Knowledge-based Methods

As the name suggests, for disambiguation, these methods primarily rely on
dictionaries, treasures and lexical knowledge base. They do not use corpora
evidences for disambiguation. The Lesk method is the seminal dictionary-based
method introduced by Michael Lesk in 1986. The Lesk definition, on which the
Lesk algorithm is based is measure overlap between sense definitions for all
words in context. However, in 2000, Kilgarriff and Rosensweig gave the
simplified Lesk definition as measure overlap between sense definitions of word
and current context, which further means identify the correct sense for one word
at a time. Here the current context is the set of words in surrounding sentence or
paragraph.

Supervised Methods
For disambiguation, machine learning methods make use of sense-annotated
corpora to train. These methods assume that the context can provide enough
evidence on its own to disambiguate the sense. In these methods, the words
knowledge and reasoning are deemed unnecessary. The context is represented
as a set of features of the words. It includes the information about the
surrounding words also. Support vector machine and memory-based learning
are the most successful supervised learning approaches to WSD. These methods
rely on substantial amount of manually sense-tagged corpora, which is very
expensive to create.

Semi-supervised Methods
Due to the lack of training corpus, most of the word sense disambiguation
algorithms use semi-supervised learning methods. It is because semi-supervised
methods use both labelled as well as unlabelled data. These methods require
very small amount of annotated text and large amount of plain unannotated text.
The technique that is used by semi supervised methods is bootstrapping from
seed data.

Unsupervised Methods
These methods assume that similar senses occur in similar context. That is why
the senses can be induced from text by clustering word occurrences by using
some measure of similarity of the context. This task is called word sense
induction or discrimination. Unsupervised methods have great potential to
overcome the knowledge acquisition bottleneck due to non-dependency on
manual efforts.

Applications of Word Sense Disambiguation (WSD)

Word sense disambiguation (WSD) is applied in almost every application of
language technology.

Scope of WSD −

Machine Translation
Machine translation or MT is the most obvious application of WSD. In MT,
Lexical choice for the words that have distinct translations for different senses,
is done by WSD. The senses in MT are represented as words in the target
language. Most of the machine translation systems do not use explicit WSD
module.

Information Retrieval (IR)

Information retrieval (IR) may be defined as a software program that deals with
the organization, storage, retrieval and evaluation of information from
document repositories particularly textual information. The system basically
assists users in finding the information they required but it does not explicitly
return the answers of the questions. WSD is used to resolve the ambiguities of
the queries provided to IR system. As like MT, current IR systems do not
explicitly use WSD module and they rely on the concept that user would type
enough context in the query to only retrieve relevant documents.

Text Mining and Information Extraction (IE)

In most of the applications, WSD is necessary to do accurate analysis of text.
For example, WSD helps intelligent gathering system to do flagging of the
correct words. For example, medical intelligent system might need flagging of
illegal drugs rather than medical drugs

Lexicography
WSD and lexicography can work together in loop because modern lexicography
is corpusbased. With lexicography, WSD provides rough empirical sense
groupings as well as statistically significant contextual indicators of sense.

Difficulties in Word Sense Disambiguation (WSD)

Followings are some difficulties faced by word sense disambiguation (WSD) −

Differences between dictionaries

The major problem of WSD is to decide the sense of the word because different
senses can be very closely related. Even different dictionaries and thesauruses
can provide different divisions of words into senses.
Different algorithms for different applications
Another problem of WSD is that completely different algorithm might be
needed for different applications. For example, in machine translation, it takes
the form of target word selection; and in information retrieval, a sense inventory
is not required.

Inter-judge variance
Another problem of WSD is that WSD systems are generally tested by having
their results on a task compared against the task of human beings. This is called
the problem of interjudge variance.

Word-sense discreteness
Another difficulty in WSD is that words cannot be easily divided into discrete
sub meanings.

Natural Language Discourse Processing

Concept of Coherence
Coherence and discourse structure are interconnected in many ways. Coherence,
along with property of good text, is used to evaluate the output quality of
natural language generation system. The question that arises here is what does it
mean for a text to be coherent? Suppose we collected one sentence from every
page of the newspaper, then will it be a discourse? Of-course, not. It is because
these sentences do not exhibit coherence. The coherent discourse must possess
the following properties −

Coherence relation between utterances

The discourse would be coherent if it has meaningful connections between its
utterances. This property is called coherence relation. For example, some sort of
explanation must be there to justify the connection between utterances.

Relationship between entities

Another property that makes a discourse coherent is that there must be a certain
kind of relationship with the entities. Such kind of coherence is called entity-
based coherence.
Discourse structure
An important question regarding discourse is what kind of structure the
discourse must have. The answer to this question depends upon the
segmentation we applied on discourse. Discourse segmentations may be defined
as determining the types of structures for large discourse. It is quite difficult to
implement discourse segmentation, but it is very important for information
retrieval, text summarization and information extraction kind of applications.

Algorithms for Discourse Segmentation

In this section, we will learn about the algorithms for discourse segmentation.
The algorithms are described below −

Unsupervised Discourse Segmentation

The class of unsupervised discourse segmentation is often represented as linear
segmentation. We can understand the task of linear segmentation with the help
of an example. In the example, there is a task of segmenting the text into multi-
paragraph units; the units represent the passage of the original text. These
algorithms are dependent on cohesion that may be defined as the use of certain
linguistic devices to tie the textual units together. On the other hand, lexicon
cohesion is the cohesion that is indicated by the relationship between two or
more words in two units like the use of synonyms.

Supervised Discourse Segmentation

The earlier method does not have any hand-labeled segment boundaries. On the
other hand, supervised discourse segmentation needs to have boundary-labeled
training data. It is very easy to acquire the same. In supervised discourse
segmentation, discourse marker or cue words play an important role. Discourse
marker or cue word is a word or phrase that functions to signal discourse
structure. These discourse markers are domain-specific.

Text Coherence
Lexical repetition is a way to find the structure in a discourse, but it does not
satisfy the requirement of being coherent discourse. To achieve the coherent
discourse, we must focus on coherence relations in specific. As we know that
coherence relation defines the possible connection between utterances in a
discourse. Hebb has proposed such kind of relations as follows −

We are taking two terms S0 and S1 to represent the meaning of the two related
sentences −

Result
It infers that the state asserted by term S0 could cause the state asserted by S1.
For example, two statements show the relationship result: Ram was caught in
the fire. His skin burned.

Explanation
It infers that the state asserted by S1 could cause the state asserted by S0. For
example, two statements show the relationship − Ram fought with Shyams
friend. He was drunk.

Parallel
It infers p(a1,a2,) from assertion of S0 and p(b1,b2,) from assertion S1. Here ai
and bi are similar for all i. For example, two statements are parallel − Ram
wanted car. Shyam wanted money.

Elaboration
It infers the same proposition P from both the assertions − S0 and S1 For
example, two statements show the relation elaboration: Ram was from
Chandigarh. Shyam was from Kerala.

Occasion
It happens when a change of state can be inferred from the assertion of S0, final
state of which can be inferred from S1 and vice-versa. For example, the two
statements show the relation occasion: Ram picked up the book. He gave it to
Shyam.

Building Hierarchical Discourse Structure

The coherence of entire discourse can also be considered by hierarchical
structure between coherence relations. For example, the following passage can
be represented as hierarchical structure −

S1 − Ram went to the bank to deposit money.

S2 − He then took a train to Shyams cloth shop.

S3 − He wanted to buy some clothes.

S4 − He do not have new clothes for party.

S5 − He also wanted to talk to Shyam regarding his health

Building Hierarchical Discourse Structure

Reference Resolution
Interpretation of the sentences from any discourse is another important task and
to achieve this we need to know who or what entity is being talked about. Here,
interpretation reference is the key element. Reference may be defined as the
linguistic expression to denote an entity or individual. For example, in the
passage, Ram, the manager of ABC bank, saw his friend Shyam at a shop. He
went to meet him, the linguistic expressions like Ram, His, He are reference.

On the same note, reference resolution may be defined as the task of

determining what entities are referred to by which linguistic expression.
Terminology Used in Reference Resolution:
Referring expression − The natural language expression that is used to perform
reference is called a referring expression. For example, the passage used above
is a referring expression.

Referent − It is the entity that is referred. For example, in the last given example
Ram is a referent.

Corefer − When two expressions are used to refer to the same entity, they are
called corefers. For example, Ram and he are corefers.

Antecedent − The term has the license to use another term. For example, Ram is
the antecedent of the reference he.

Anaphora & Anaphoric − It may be defined as the reference to an entity that has
been previously introduced into the sentence. And, the referring expression is
called anaphoric.

Discourse model − The model that contains the representations of the entities
that have been referred to in the discourse and the relationship they are engaged
in.

Types of Referring Expressions

Let us now see the different types of referring expressions. The five types of
referring expressions are described below −

Indefinite Noun Phrases

Such kind of reference represents the entities that are new to the hearer into the
discourse context. For example − in the sentence Ram had gone around one day
to bring him some food − some is an indefinite reference.
Definite Noun Phrases
Opposite to above, such kind of reference represents the entities that are not
new or identifiable to the hearer into the discourse context. For example, in the
sentence - I used to read The Times of India The Times of India is a definite
reference.

Pronouns
It is a form of definite reference. For example, Ram laughed as loud as he could.
The word he represents pronoun referring expression.

Demonstratives
These demonstrate and behave differently than simple definite pronouns. For
example, this and that are demonstrative pronouns.

Names
It is the simplest type of referring expression. It can be the name of a person,
organization and location also. For example, in the above examples, Ram is the
name-refereeing expression.

Reference Resolution Tasks

The two reference resolution tasks are described below.

Coreference Resolution
It is the task of finding referring expressions in a text that refer to the same
entity. In simple words, it is the task of finding corefer expressions. A set of
coreferring expressions are called coreference chain. For example - He, Chief
Manager and His - these are referring expressions in the first passage given as
example.

Constraint on Coreference Resolution

In English, the main problem for coreference resolution is the pronoun it. The
reason behind this is that the pronoun it has many uses. For example, it can refer
much like he and she. The pronoun it also refers to the things that do not refer to
specific things. For example, Its raining. It is really good.

Pronominal Anaphora Resolution

Unlike the coreference resolution, pronominal anaphora resolution may be
defined as the task of finding the antecedent for a single pronoun. For example,
the pronoun is his and the task of pronominal anaphora resolution is to find the
word Ram because Ram is the antecedent.

Part of Speech (PoS) Tagging

Tagging is a kind of classification that may be defined as the automatic
assignment of description to the tokens. Here the descriptor is called tag, which
may represent one of the part-of-speech, semantic information and so on.
Now, if we talk about Part-of-Speech (PoS) tagging, then it may be defined as
the process of assigning one of the parts of speech to the given word. It is
generally called POS tagging. In simple words, we can say that POS tagging is a
task of labelling each word in a sentence with its appropriate part of speech. We
already know that parts of speech include nouns, verb, adverbs, adjectives,
pronouns, conjunction and their sub-categories.
Most of the POS tagging falls under Rule Base POS tagging, Stochastic POS
tagging and Transformation based tagging.
Rule-based POS Tagging
One of the oldest techniques of tagging is rule-based POS tagging. Rule-based
taggers use dictionary or lexicon for getting possible tags for tagging each word.
If the word has more than one possible tag, then rule-based taggers use hand-
written rules to identify the correct tag. Disambiguation can also be performed
in rule-based tagging by analyzing the linguistic features of a word along with
its preceding as well as following words. For example, suppose if the preceding
word of a word is article then word must be a noun.
As the name suggests, all such kind of information in rule-based POS tagging is
coded in the form of rules. These rules may be either −
Context-pattern rules

Or, as Regular expression compiled into finite-state automata, intersected with

lexically ambiguous sentence representation.

We can also understand Rule-based POS tagging by its two-stage architecture −

First stage − In the first stage, it uses a dictionary to assign each word a list of
potential parts-of-speech.

Second stage − In the second stage, it uses large lists of hand-written

disambiguation rules to sort down the list to a single part-of-speech for each
word.
Properties of Rule-Based POS Tagging
Rule-based POS taggers possess the following properties −

These taggers are knowledge-driven taggers.

The rules in Rule-based POS tagging are built manually.

The information is coded in the form of rules.

We have some limited number of rules approximately around 1000.

Smoothing and language modeling is defined explicitly in rule-based taggers.

Stochastic POS Tagging

Another technique of tagging is Stochastic POS Tagging. Now, the question
that arises here is which model can be stochastic. The model that includes
frequency or probability (statistics) can be called stochastic. Any number of
different approaches to the problem of part-of-speech tagging can be referred to
as stochastic tagger.

The simplest stochastic tagger applies the following approaches for POS
tagging −

Word Frequency Approach

In this approach, the stochastic taggers disambiguate the words based on the
probability that a word occurs with a particular tag. We can also say that the tag
encountered most frequently with the word in the training set is the one
assigned to an ambiguous instance of that word. The main issue with this
approach is that it may yield inadmissible sequence of tags.

Tag Sequence Probabilities

It is another approach of stochastic tagging, where the tagger calculates the
probability of a given sequence of tags occurring. It is also called n-gram
approach. It is called so because the best tag for a given word is determined by
the probability at which it occurs with the n previous tags.

Properties of Stochastic POST Tagging

Stochastic POS taggers possess the following properties −

This POS tagging is based on the probability of tag occurring.

It requires training corpus

There would be no probability for the words that do not exist in the corpus.

It uses different testing corpus (other than training corpus).

It is the simplest POS tagging because it chooses most frequent tags associated
with a word in training corpus.

Transformation-based Tagging
Transformation based tagging is also called Brill tagging. It is an instance of the
transformation-based learning (TBL), which is a rule-based algorithm for
automatic tagging of POS to the given text. TBL, allows us to have linguistic
knowledge in a readable form, transforms one state to another state by using
transformation rules.

It draws the inspiration from both the previous explained taggers − rule-based
and stochastic. If we see similarity between rule-based and transformation
tagger, then like rule-based, it is also based on the rules that specify what tags
need to be assigned to what words. On the other hand, if we see similarity
between stochastic and transformation tagger then like stochastic, it is machine
learning technique in which rules are automatically induced from data.

Working of Transformation Based Learning(TBL)

In order to understand the working and concept of transformation-based taggers,
we need to understand the working of transformation-based learning. Consider
the following steps to understand the working of TBL −

Start with the solution − The TBL usually starts with some solution to the
problem and works in cycles.

Most beneficial transformation chosen − In each cycle, TBL will choose the
most beneficial transformation.

Apply to the problem − The transformation chosen in the last step will be
applied to the problem.
The algorithm will stop when the selected transformation in step 2 will not add
either more value or there are no more transformations to be selected. Such kind
of learning is best suited in classification tasks.

Advantages of Transformation-based Learning (TBL)

The advantages of TBL are as follows −

We learn small set of simple rules and these rules are enough for tagging.

Development as well as debugging is very easy in TBL because the learned

rules are easy to understand.

Complexity in tagging is reduced because in TBL there is interlacing of

machine learned and human-generated rules.

Transformation-based tagger is much faster than Markov-model tagger.

Disadvantages of Transformation-based Learning (TBL)

The disadvantages of TBL are as follows −

Transformation-based learning (TBL) does not provide tag probabilities.

In TBL, the training time is very long especially on large corpora.

Hidden Markov Model (HMM) POS Tagging

Before digging deep into HMM POS tagging, we must understand the concept
of Hidden Markov Model (HMM).

Hidden Markov Model

An HMM model may be defined as the doubly-embedded stochastic model,
where the underlying stochastic process is hidden. This hidden stochastic
process can only be observed through another set of stochastic processes that
produces the sequence of observations.

Example
For example, a sequence of hidden coin tossing experiments is done and we see
only the observation sequence consisting of heads and tails. The actual details
of the process - how many coins used, the order in which they are selected - are
hidden from us. By observing this sequence of heads and tails, we can build
several HMMs to explain the sequence. Following is one form of Hidden
Markov Model for this problem −

Hidden Markov Model

We assumed that there are two states in the HMM and each of the state
corresponds to the selection of different biased coin. Following matrix gives the
state transition probabilities −

A=[a11a21a12a22]

Here,

aij = probability of transition from one state to another from i to j.

a11 + a12 = 1 and a21 + a22 =1

P1 = probability of heads of the first coin i.e. the bias of the first coin.

P2 = probability of heads of the second coin i.e. the bias of the second coin.

We can also create an HMM model assuming that there are 3 coins or more.
This way, we can characterize HMM by the following elements −

N, the number of states in the model (in the above example N =2, only two
states).

M, the number of distinct observations that can appear with each state in the
above example M = 2, i.e., H or T).

A, the state transition probability distribution − the matrix A in the above

example.

P, the probability distribution of the observable symbols in each state (in our
example P1 and P2).

I, the initial state distribution.

Use of HMM for POS Tagging

The POS tagging process is the process of finding the sequence of tags which is
most likely to have generated a given word sequence. We can model this POS
process by using a Hidden Markov Model (HMM), where tags are the hidden
states that produced the observable output, i.e., the words.

Mathematically, in POS tagging, we are always interested in finding a tag

sequence (C) which maximizes −

P (C|W)

Where,
C = C1, C2, C3... CT

W = W1, W2, W3, WT

On the other side of coin, the fact is that we need a lot of statistical data to
reasonably estimate such kind of sequences. However, to simplify the problem,
we can apply some mathematical transformations along with some assumptions.

The use of HMM to do a POS tagging is a special case of Bayesian interference.

Hence, we will start by restating the problem using Bayes rule, which says that
the above-mentioned conditional probability is equal to −

(PROB (C1,..., CT) * PROB (W1,..., WT | C1,..., CT)) / PROB (W1,..., WT)

We can eliminate the denominator in all these cases because we are interested in
finding the sequence C which maximizes the above value. This will not affect
our answer. Now, our problem reduces to finding the sequence C that
maximizes −

PROB (C1,..., CT) * PROB (W1,..., WT | C1,..., CT) (1)

Even after reducing the problem in the above expression, it would require large
amount of data. We can make reasonable independence assumptions about the
two probabilities in the above expression to overcome the problem.

First Assumption
The probability of a tag depends on the previous one (bigram model) or
previous two (trigram model) or previous n tags (n-gram model) which,
mathematically, can be explained as follows −

PROB (C1,..., CT) = Πi=1..T PROB (Ci|Ci-n+1Ci-1) (n-gram model)

PROB (C1,..., CT) = Πi=1..T PROB (Ci|Ci-1) (bigram model)

The beginning of a sentence can be accounted for by assuming an initial

probability for each tag.

PROB (C1|C0) = PROB initial (C1)

Second Assumption
The second probability in equation (1) above can be approximated by assuming
that a word appears in a category independent of the words in the preceding or
succeeding categories which can be explained mathematically as follows −

PROB (W1,..., WT | C1,..., CT) = Πi=1..T PROB (Wi|Ci)

Now, on the basis of the above two assumptions, our goal reduces to finding a
sequence C which maximizes

Πi=1...T PROB(Ci|Ci-1) * PROB(Wi|Ci)

Now the question that arises here is has converting the problem to the above
form really helped us. The answer is - yes, it has. If we have a large tagged
corpus, then the two probabilities in the above formula can be calculated as −

PROB (Ci=VERB|Ci-1=NOUN) = (# of instances where Verb follows Noun) /

(# of instances where Noun appears) (2)

PROB (Wi|Ci) = (# of instances where Wi appears in Ci) /(# of instances where

Ci appears) (3)