JEPPIAAR UNIVERSITY

CSE 146
Natural Language Processing Notes

MODULE III

LANGUAGE MODELING & SEMANTIC PARSING

Language Modeling: Introduction, N-Gram Models, Language Model Evaluation,

Parameter Estimation, Language Model Adaptation, Types of Language Models,
Language-Specific Modeling Problems. Semantic Parsing: Introduction, Semantic
Interpretation, System Paradigms, Word Sense Systems. Discourse Processing:
Cohesion, Reference Resolution, Discourse Cohesion and Structure.
 1

Unit-3: N-gram Language Models (Part-I)

Uses of Language Modelling:

1. Predicting is difficult—especially about the future What word, for example, is likely to
follow
Please turn your homework ...
Hopefully, most of you concluded that a very likely word is in, or possibly over, but probably
not refrigerator or the.

We will formalize this intuition by introducing models that assign a probability to each possible
next word. The same models will also serve to assign a probability to an entire sentence. Such
a model, for example, could predict that the following sequence has a much higher probability
of appearing in a text:

all of a sudden I notice three guys standing on the sidewalk

than does this same set of words in a different order:
on guys all I of notice sidewalk three a sudden standing the

2. Why would you want to predict upcoming words, or assign probabilities to sentences?
Probabilities are essential in any task in which we have to identify words in noisy, ambiguous
input, like speech recognition. For a speech recognizer to realize that you said

I will be back soonish and not I will be bassoon dish, it helps to know
that back soonish is a much more probable sequence than bassoon dish.

3. For writing tools like spelling correction or grammatical error correction, we need to
find and correct errors in writing like Their are two midterms, in which There was mistyped
as Their, or Everything has improve, in which improve should have been improved. The
phrase There are will be much more probable than Their are, and has improved than has
improve, allowing us to help users by detecting and correcting these errors.

4. Assigning probabilities to sequences of words is also essential in machine translation.

Suppose we are translating a Chinese source sentence:

他 向 记者 介绍了 主要 内容

He to reporters introduced main content

 2

As part of the process we might have built the following set of potential rough
English translations:
he introduced reporters to the main contents of the statement
he briefed to reporters the main contents of the statement
he briefed reporters on the main contents of the statement

5. Probabilities are also important for augmentative and alternative communication AAC
systems. People often use such AAC devices if they are physically unable to speak or sign but
can instead use eye gaze or other specific movements to select words from a menu to be
spoken by the system. Word prediction can be used to suggest likely words for the menu.

Language Models: Models that assign probabilities to sequences of words are called language
models or LMs. The simplest model that assigns probabilities to sentences and sequences of
words are the n-gram. An n-gram is a sequence of n words: a 2-gram (which we’ll call bigram)
is a two-word sequence of words like “please turn”, “turn your”, or ”your homework”, and a
3-gram (a trigram) is a three-word sequence of words like “please turn your”, or “turn your
homework”.

We’ll see how to use n-gram models to estimate the probability of the last word of an n-gram
given the previous words, and also to assign probabilities to entire sequences. The n-gram
models are much simpler than state-of-the art neural language models based on the RNNs and
transformers.

N-Grams
P(w|h), the probability of a word w given some history h. Suppose the history h is “its water
is so transparent that” and we want to know the probability that the next word is the:

One way to estimate this probability is from relative frequency counts: take a very large corpus,
count the number of times we see its water is so transparent that, and count the number of times
this is followed by the. This would be answering the question “Out of the times we saw the
history h, how many times was it followed by the word w”, as follows:

With a large enough corpus, such as the web, we can compute these counts and estimate the
probability. While this method of estimating probabilities directly from counts works fine in
 3

many cases, it turns out that even the web isn’t big enough to give us good estimates in most
cases. This is because language is creative; new sentences are created all the time, and we won’t
always be able to count entire sentences. Even simple extensions of the example sentence may
have counts of zero on the web (such as “Walden Pond’s water is so transparent that the”; well,
used to have counts of zero). Similarly, if we wanted to know the joint probability of an entire
sequence of words like its water is so transparent, we could do it by asking “out of all possible
sequences of five words, how many of them are its water is so transparent?” We would have
to get the count of its water is so transparent and divide by the sum of the counts of all possible
five word sequences. That seems rather a lot to estimate!

For this reason, we’ll need to introduce more clever ways of estimating the probability of a
word w given a history h, or the probability of an entire word sequence W. Now, how can we
compute probabilities of entire sequences like P(w1;w2;…;wn)? One thing we can do is
decompose this probability using the chain rule of probability:
Applying the chain rule to words, we get

The chain rule shows the link between computing the joint probability of a sequence and
computing the conditional probability of a word given previous words. But using the chain rule
doesn’t really seem to help us! We don’t know any way to compute the exact probability of a
word given a long sequence of preceding words, P(wn|w1:n-1).

The intuition of the n-gram model is that instead of computing the probability of a word given
its entire history, we can approximate the history by just the last few words. The bigram model,
approximates the probability of a word given all the previous words P(wn|w1:n-1) by using only
the conditional probability of the preceding word P(wn|wn-1). In other words, instead of
computing the probability

we approximate it with the probability

When we use a bigram model to predict the conditional probability of the next word, we are
thus making the following approximation:

The assumption that the probability of a word depends only on the previous word is Markov
called a Markov assumption. Markov models are the class of probabilistic models that assume
 4

we can predict the probability of some future unit without looking too far into the past. We can
generalize the bigram (which looks one word into the past) to the trigram (which looks two
words into the past) and thus to the n-gram (which looks n-1 words into the past).

Let’s see a general equation for this n-gram approximation to the conditional probability of the
next word in a sequence. We’ll use N here to mean the n-gram size, so N = 2 means bigrams
and N = 3 means trigrams. Then we approximate the probability of a word given its entire
context as follows:

Given the bigram assumption for the probability of an individual word, we can compute the
probability of a complete word sequence

An intuitive way to estimate probabilities is called maximum likelihood estimation or MLE.

We get the MLE estimate for the parameters of an n-gram model by getting counts from a
corpus, and normalizing the counts so that they lie between 0 and 1.

For example, to compute a particular bigram probability of a word wn given a previous word
wn-1, we’ll compute the count of the bigram C(wn-1wn) and normalize by the sum of all the
bigrams that share the same first word wn-1:

Let’s work through an example using a mini-corpus of three sentences. We’ll first need to
augment each sentence with a special symbol <s> at the beginning of the sentence, to give us
the bigram context of the first word. We’ll also need a special end-symbol. </s>

<s> I am Sam </s>

<s> Sam I am </s>
<s> I do not like green eggs and ham </s>
Here are the calculations for some of the bigram probabilities from this corpus.

Maximum Likelihood Estimate:

The above equation estimates the n-gram probability by dividing the observed frequency of a
particular sequence by the observed frequency of a prefix. This ratio is called a relative
 5

frequency. We said above that this use of frequencies as a way to estimate probabilities is an
example of maximum likelihood estimation or MLE. In MLE, the resulting parameter set
maximizes the likelihood of the training set T given the model M (i.e., P(T|M)). For example,
suppose the word Chinese occurs 400 times in a corpus of a million words like the Brown
corpus. What is the probability that a random word selected from some other text of, say, a
million words will be the word Chinese? The MLE of its probability is 400/1000000 or :0004.
Now :0004 is not the best possible estimate of the probability of Chinese occurring in all
situations; it might turn out that in some other corpus or context Chinese is a very unlikely
word. But it is the probability that makes it most likely that Chinese will occur 400 times in a
million-word corpus.
Let’s move on to some examples from a slightly larger corpus than our 14-word example above.
We’ll use data from the now-defunct Berkeley Restaurant Project, a dialogue system from the
last century that answered questions about a database of restaurants in Berkeley, California.
Here are some text normalized sample user queries (a sample of 9332 sentences is on the
website):
can you tell me about any good cantonese restaurants close by
mid priced thai food is what i’m looking for
tell me about chez panisse
can you give me a listing of the kinds of food that are available
i’m looking for a good place to eat breakfast
when is caffe venezia open during the day

Figure below shows the bigram counts from a piece of a bigram grammar from the Berkeley
Restaurant Project. Note that the majority of the values are zero. In fact, we have chosen the
sample words to cohere with each other; a matrix selected from a random set of eight words
would be even more sparse.
 6

Figure below shows the bigram probabilities after normalization (dividing each cell above
Figure by the appropriate unigram for its row, taken from the following set of unigram
probabilities):

Now we can compute the probability of sentences like I want English food or I want Chinese
food by simply multiplying the appropriate bigram probabilities together, as follows:

compute the probability of i want chinese food.

Some practical issues: Although for pedagogical purposes we have only described trigram
bigram models, in practice it’s more common to use trigram models, which condition on the
previous two words rather than the previous word, or 4-gram or even 5-gram models, when
there is sufficient training data. Note that for these larger ngrams, we’ll need to assume extra
contexts to the left and right of the sentence end.
For example, to compute trigram probabilities at the very beginning of the sentence, we use
two pseudo-words for the first trigram (i.e., P(I|<s><s>).

We always represent and compute language model probabilities in log format as log
probabilities. Since probabilities are (by definition) less than or equal to1, the more
probabilities we multiply together, the smaller the product becomes. Multiplying enough n-
 7

grams together would result in numerical underflow. By using log probabilities instead of raw
probabilities, we get numbers that are not as small.

Evaluating Language Models

The best way to evaluate the performance of a language model is to embed it in an application
and measure how much the application improves. Such end-to-end evaluation is called extrinsic
evaluation. Extrinsic evaluation is the only way to know if a particular improvement in a
component is really going to help the task at hand. Thus, for speech recognition, we can
compare the performance of two language models by running the speech recognizer twice,
once with each language model, and seeing which gives the more accurate transcription.
Unfortunately, running big NLP systems end-to-end is often very expensive. Instead, it would
be nice to have a metric that can be used to quickly evaluate potential improvements in a
language model. An intrinsic evaluation metric is one that measures the quality of a model
independent of any application.

For an intrinsic evaluation of a language model we need a test set. As with many of the
statistical models in our field, the probabilities of an n-gram model come from the corpus it is
trained on, the training set or training corpus. We can then measure the quality of an n-gram
model by its performance on some unseen data called the test set or test corpus. So if we are
given a corpus of text and want to compare two different n-gram models, we divide the data
into training and test sets, train the parameters of both models on the training set, and then
compare how well the two trained models fit the test set. But what does it mean to “fit the test
set”? The answer is simple: whichever model assigns a higher probability to the test set—
meaning it more accurately predicts the test set, is a better model.
Perplexity
In practice we don’t use raw probability as our metric for evaluating language models, but a
variant called perplexity. The perplexity (sometimes called PPL for short) of a language model
on a test set is the inverse probability of the test set, normalized by the number of words. For a
test set W = w1w2…wN,:
 8

The perplexity of a test set W depends on which language model we use. Here’s the perplexity
of W with a unigram language model (just the geometric mean of the unigram probabilities):

The perplexity of W computed with a bigram language model is still a geometric mean, but
now of the bigram probabilities:

Minimizing perplexity is equivalent to maximizing the test set probability according to the
language model.
Given a text W, different language models will have different perplexities. Because of this,
perplexity can be used to compare different n-gram models. Let’s look at an example, in which
we trained unigram, bigram, and trigram grammars on 38 million words (including start-of-
sentence tokens) from the Wall Street Journal, using a 19,979 word vocabulary. We then
computed the perplexity of each of these models on a test set of 1.5 million words, using Eq.
for unigrams, for bigrams, and the corresponding equation for trigrams. The table below shows
the perplexity of a 1.5 million word WSJ test set according to each of these grammars.

As we see above, the more information the n-gram gives us about the word sequence, the higher
the probability the n-gram will assign to the string.

Sampling sentences from a language model

One important way to visualize what kind of knowledge a language model embodies is to
sample from it. Sampling from a distribution means to choose random points according to their
likelihood. Thus, sampling from a language model, which represents a distribution over
sentences, means to generate some sentences, choosing each sentence according to its
likelihood as defined by the model. Thus, we are more likely to generate sentences that the
model thinks have a high probability and less likely to generate sentences that the model thinks
have a low probability.
This technique of visualizing a language model by sampling was first suggested very early on
by Shannon (1951) and Miller and Selfridge (1950). It’s simplest to visualize how this works
for the unigram case. Imagine all the words of the English language covering the probability
space between 0 and 1, each word covering an interval proportional to its frequency. Figure
shows a visualization, using a unigram LM computed from the text of this book. We choose a
 9

random value between 0 and 1, find that point on the probability line, and print the word whose
interval includes this chosen value. We continue choosing random numbers and generating
words until we randomly generate the sentence-final token </s>.

We can use the same technique to generate bigrams by first generating a random bigram that
starts with <s> (according to its bigram probability). Let’s say the second word of that bigram
is w. We next choose a random bigram starting with w (again, drawn according to its bigram
probability), and so on.
Generalization and Zeros
The n-gram model, like many statistical models, is dependent on the training corpus. One
implication of this is that the probabilities often encode specific facts about a given training
corpus. Another implication is that n-grams do a better and better job of modelling the training
corpus as we increase the value of N. We can use the sampling method from the prior section
to visualize both of these facts! To give an intuition for the increasing power of higher-order
n-grams, Figure below shows random sentences generated from unigram, bigram, trigram, and
4-gram models trained on Shakespeare’s works.
 10

Figure 3.
The longer the context on which we train the model, the more coherent the sentences. In the
unigram sentences, there is no coherent relation between words or any sentence-final
punctuation. The bigram sentences have some local word-to-word coherence (especially if we
consider that punctuation counts as a word). The trigram and 4-gram sentences are beginning
to look a lot like Shakespeare. Indeed, a careful investigation of the 4-gram sentences shows
that they look a little too much like Shakespeare. The words It cannot be but so are directly
from King John. From Shakespeare (N =884,647, V=29,066), our n-gram probability matrices
are ridiculously sparse. There are V2 =844,000,000 possible bigrams alone, and the number of
possible 4-grams is V4 = 7X1017. Thus, once the generator has chosen the first 4-gram (It
cannot be but), there are only five possible continuations (that, I, he, thou, and so); indeed, for
many 4-grams, there is only one continuation.
To get an idea of the dependence of a grammar on its training set, let’s look at an n-gram
grammar trained on a completely different corpus: the Wall Street Journal (WSJ) newspaper.
Shakespeare and the Wall Street Journal are both English, so we might expect some overlap
between our n-grams for the two genres. Figure below shows sentences generated by unigram,
bigram, and trigram grammars trained on 40 million words from WSJ.
Compare these examples to the pseudo-Shakespeare in above figure. While they both model
“English-like sentences”, there is clearly no overlap in generated sentences, and little overlap
even in small phrases. Statistical models are likely to be pretty useless as predictors if the
training sets and the test sets are as different as Shakespeare and WSJ.

How should we deal with this problem when we build n-gram models? One step is to be sure
to use a training corpus that has a similar genre to whatever task we are trying to accomplish.
To build a language model for translating legal documents, we need a training corpus of legal
documents. To build a language model for a question-answering system, we need a training
corpus of questions. It is equally important to get training data in the appropriate dialect or
variety, especially when processing social media posts or spoken transcripts.
 11

Matching genres and dialects is still not sufficient. Our models may still be subject to the
problem of sparsity. For any n-gram that occurred a sufficient number of times, we might have
a good estimate of its probability. But because any corpus is limited, some perfectly acceptable
English word sequences are bound to be missing from it. That is, we’ll have many cases of
putative “zero probability n-grams” that should really have some non-zero probability.
Consider the words that follow the bigram denied the in the WSJ Treebank3 corpus, together
with their counts:

These zeros—things that don’t ever occur in the training set but do occur in the test set—are a
problem for two reasons. First, their presence means we are underestimating the probability of
all sorts of words that might occur, which will hurt the performance of any application we want
to run on this data. Second, if the probability of any word in the test set is 0, the entire
probability of the test set is 0. By definition, perplexity is based on the inverse probability of
the test set. Thus, if some words have zero probability, we can’t compute perplexity at all, since
we can’t divide by 0! There are two solutions, depending on the kind of zero. For words whose
n-gram probability is zero because they occur in a novel test set context, like the example of
denied the offer above, we’ll introduce algorithms called smoothing or discounting.
Smoothing algorithms shave off a bit of probability mass from some more frequent events and
give it to these unseen events. But first, let’s talk about an even more insidious form of zero:
words that the model has never seen below at all (in any context): unknown words!
Unknown Words
What do we do about words we have never seen before? Perhaps the word Jurafsky simply
did not occur in our training set, but pops up in the test set! We can choose to disallow this
situation from occurring, by stipulating that we already know all the words that can occur. In
such a closed vocabulary system the test set can only contain words from this known lexicon,
and there will be no unknown words.
In most real situations, however, we have to deal with words we haven’t seen before, which
we’ll call unknown words, or out of vocabulary (OOV) words. The percentage of OOV words
that appear in the test set is called the OOV rate. One way to create an open vocabulary system
 12

is to model these potential unknown words in the test set by adding a pseudo-word called
<UNK>.
There are two common ways to train the probabilities of the unknown word model <UNK>.
The first one is to turn the problem back into a closed vocabulary one by choosing a fixed
vocabulary in advance:
1. Choose a vocabulary (word list) that is fixed in advance.
2. Convert in the training set any word that is not in this set (any OOV word) to the unknown
word token <UNK> in a text normalization step.
3. Estimate the probabilities for <UNK> from its counts just like any other regular word in the
training set.
The second alternative, in situations where we don’t have a prior vocabulary in advance, is to
create such a vocabulary implicitly, replacing words in the training data by <UNK> based on
their frequency. For example, we can replace by <UNK> all words that occur fewer than n
times in the training set, where n is some small number, or equivalently select a vocabulary
size V in advance (say 50,000) and choose the top V words by frequency and replace the rest
by <UNK>. In either case we then proceed to train the language model as before, treating
<UNK> like a regular word.
Smoothing
What do we do with words that are in our vocabulary (they are not unknown words) but appear
in a test set in an unseen context (for example they appear after a word they never appeared
after in training)? To keep a language model from assigning zero probability to these unseen
events, we’ll have to shave off a bit of probability mass from some more frequent events and
give it to the events we’ve never seen. This modification is called smoothing or discounting.
Now we’ll see a variety of ways to do smoothing: Laplace (add-one) smoothing, add-k
smoothing, stupid backoff, and Kneser-Ney smoothing.
Laplace Smoothing
The simplest way to do smoothing is to add one to all the n-gram counts, before we normalize
them into probabilities. All the counts that used to be zero will now have a count of 1, the
counts of 1 will be 2, and so on. This algorithm is called Laplace smoothing. Laplace smoothing
does not perform well enough to be used smoothing in modern n-gram models, but it usefully
introduces many of the concepts that we see in other smoothing algorithms, gives a useful
baseline, and is also a practical smoothing algorithm for other tasks like text classification.
Let’s start with the application of Laplace smoothing to unigram probabilities. Recall that the
unsmoothed maximum likelihood estimate of the unigram probability of the word wi is its
count ci normalized by the total number of word tokens N:
 13

Laplace smoothing merely adds one to each count (hence its alternate name add one
smoothing). Since there are V words in the vocabulary and each one was incremented, we also
need to adjust the denominator to take into account the extra V observations.

Let’s smooth our Berkeley Restaurant Project bigrams. Figure below shows the add-one
smoothed counts for the bigrams in Berkeley Restaurant Project.

Recall that normal bigram probabilities are computed by normalizing each row of counts by
the unigram count:

For add-one smoothed bigram counts, we need to augment the unigram count by the number
of total word types in the vocabulary V:

Thus, each of the unigram counts given in the previous section will need to be augmented by
V =1446. The result is the smoothed bigram probabilities in Figure below.
 14

The sharp change in counts and probabilities occurs because too much probability mass is
moved to all the zeros.
Add-k smoothing
One alternative to add-one smoothing is to move a bit less of the probability mass from the
seen to the unseen events. Instead of adding 1 to each count, we add a fractional count k (.5?
.05? .01?). This algorithm is therefore called add-k smoothing.

Add-k smoothing requires that we have a method for choosing k; this can be done, for example,
by optimizing on a devset. Although add-k is useful for some tasks (including text
classification), it turns out that it still doesn’t work well for language modelling, generating
counts with poor variances and often inappropriate discounts.
Backoff and Interpolation
The discounting we have been discussing so far can help solve the problem of zero frequency
n-grams. But there is an additional source of knowledge we can draw on. If we are trying to
compute P(wn|wn-2wn-1) but we have no examples of a particular trigram wn-2wn-1wn, we can
instead estimate its probability by using the bigram probability P(wn|wn-1). Similarly, if we
don’t have counts to compute P(wn|wn-1), we can look to the unigram P(wn). In other words,
sometimes using less context is a good thing, helping to generalize more for contexts that the
model hasn’t learned much about. There are two ways to use this n-gram “hierarchy”. In
backoff, we use the trigram if the evidence is sufficient, otherwise we use the bigram, otherwise
the unigram. In other words, we only “back off” to a lower-order n-gram if we have zero
evidence for a higher-order n-gram.

By contrast, in interpolation, we always mix the probability estimates from all the n-gram
estimators, weighting and combining the trigram, bigram, and unigram counts. In simple linear
interpolation, we combine different order n-grams by linearly interpolating them. Thus, we
 15

estimate the trigram probability P(wn|wn-2wn-1) by mixing together the unigram, bigram, and
trigram probabilities, each weighted by a

The s must sum to 1, making Equation equivalent to a weighted average:

 1

UNIT - IV

Semantic Parsing

1. Introduction

• Two approaches have emerged in the NLP for language understanding.

• In the first approach, a specific, rich meaning representation is created for a
limited domain for use by application that are restricted to that domain, such as
travel reservations, football game simulations, or querying a geographic
database.
• In the second approach, a related set of intermediate-specific meaning representation
is created, going from low-level analysis to a middle analysis, and the bigger
understanding task is divided into multiple, smaller pieces that are more manageable,
such as word sense disambiguation followed by predicate-argument structure
recognition.
• Here two types of meaning representations: a domain-dependent, deeper
representation and a set of relatively shallow but general-purpose, low-level, and
intermediate representation.
• The task of producing the output of the first type is often called deep semantic
parsing, and the task of producing the output of the second type is often called
shallow semantic parsing.
• The first approach is so specific that porting to every new domain can require
anywhere from a few modifications to almost reworking the solution from scratch.

• In other words, the reusability of the representation across domains is very limited.
• The problem with second approach is that it is extremely difficult to construct a
general-purpose ontology and create symbols that are shallow enough to be learnable
but detailed enough to be useful for all possible applications.

• Ontology means
1. The branch of metaphysics dealing with the nature of being.
2. a set of concepts and categories in a subject area or domain that shows their properties
and the relations between them.
"what's new about our ontology is that it is created automatically from large datasets"

• Therefore, an application specific translation layer between the more general

representation and the more specific representation becomes necessary.

2. Semantic Interpretation

Semantic parsing can be considered as part of Semantic interpretation, which

involves various components that together define a representation of text that can be
fed into a computer to allow further computations manipulations and search, which
are prerequisite for any language understanding system or application. Here we
discuss the structure of semantic theory.

A Semantic theory should be able to:

➢ Explain sentence having ambiguous meaning: The bill is large is ambiguous in the
sense that is could represent money or the beak of a bird.
 2

➢ Resolve the ambiguities of words in context. The bill is large but need not be paid, the
theory should be able to disambiguate the monetary meaning of bill.
➢ Identify meaningless but syntactically well-formed sentence: Colorless green ideas
sleep furiously.
➢ Identify syntactically or transformationally unrelated paraphrasers of concept having
the same semantic content.

➢ Here we look at some requirements for achieving a semantic representation.

2.1 Structural Ambiguity

➢ Structure means syntactic structure of sentences.

➢ The syntactic structure means transforming a sentence into its underlying syntactic
representation and in theory of semantic interpretation refer to underlying syntactic
representation.

2.2 Word Sense

➢ In any given language, the same word type is used in different contexts and with
different morphological variants to represent different entities or concepts in the
world.
➢ For example, we use the word nail to represent a part of the human anatomy
and also to represent the generally metallic object used to secure other objects.

2.3 Entity and Event Resolution

➢ Any discourse consists of a set of entities participating in a series of explicit or

implicit events over a period of time.
➢ So, the next important component of semantic interpretation is the
identification of various entities that are sparkled across the discourse using the
same or different phrases.
➢ The predominant tasks have become popular over the years: named entity
recognition and coreference resolution.
➢ Coreference resolution is the task of finding all expressions that refer to the same
entity in a text.

2.4 Predicate Argument Structure

 3

➢ Once we have the word-sense, entities and events identified, another level of semantics
structure comes into play: identifying the participants of the entities in these events.
➢ Resolving the argument structure of predicate in the sentence is where we identify which
entities play what part in which event.
➢ A word which functions as the verb is called a predicate and words which function as the
nouns are called arguments. Here are some other predicates and arguments:

2.5 Meaning Representation

➢ The final process of the semantic interpretation is to build a semantic representation

or meaning representation that can then be manipulated by algorithms to various
application ends.
➢ This process is sometimes called the deep representation.

The following two examples

3. System Paradigms

• It is important to get a perspective on the various primary dimensions on which the

problem of semantic interpretation has been tackled.
• The approaches generally fall into the following three categories: [Link] architecture
 4

[Link] 3. Coverage.

1. System Architectures
a. Knowledge based: These systems use a predefined set of rules or a knowledge base to
obtain a solution to a new problem.
b. Unsupervised: These systems tend to require minimal human intervention to be
functional by using existing resources that can be bootstrapped for a particular
application or problem domain.
c. Supervised: these systems involve the manual annotation of some phenomena
that appear in a sufficient quantity of data so that machine learning algorithms can
be applied.
d. Semi-Supervised: manual annotation is usually very expensive and does not yield
enough data to completely capture a phenomenon. In such instances, researches
can automatically expand the data set on which their models are trained either
by employing machine-generated output directly or by bootstrapping off an
existing model by having humans correct its output.

2. Scope:
➢ Domain Dependent: These systems are specific to certain domains, such as
air travel reservations or simulated football coaching.
➢ Domain Independent: These systems are general enough that the techniques can be
applicable to multiple domains without little or no change.

3. Coverage
a. Shallow: These systems tend to produce an intermediate representation that can
then be converted to one that a machine can base its action on.
b. Deep: These systems usually create a terminal representation that is directly consumed by
a machine or application.

4. Word Sense
➢ Word Sense Disambiguation is an important method of NLP by which the meaning
of a word is determined, which is used in a particular context.
➢ In a compositional approach to semantics, where the meaning of the whole is
composed on the meaning of parts, the smallest parts under consideration in textual
discourse are typically the words themselves: either tokens as they appear in the text
or their lemmatized forms.
➢ Words sense has been examined and studied for a very long time.
➢ Attempts to solve this problem range from rule based and knowledge based to
completely unsupervised, supervised, and semi-supervised learning methods.
➢ Very early systems were predominantly rule based or knowledge based and used
dictionary definitions of senses of words.
➢ Unsupervised word sense induction or disambiguation techniques try to induce the
senses or word as it appears in various corpora.
➢ These systems perform either a hard or soft clustering of words and tend to allow the
tuning of these clusters to suit a particular application.
➢ Most recent supervised approaches to word sense disambiguation, usually
application- independent-level of granularity (including small details). Although the
output of supervised approaches can still be amendable to generating a ranking,
 5

or distribution, of membership sense.

➢ Word sense ambiguities can be of three principal types: [Link] [Link]
[Link] ambiguity.
➢ Homonymy defined as the words having same spelling or same form but having
different and unrelated meaning. For example, the word “Bat” is a homonymy word
because bat can be an implement to hit a ball or bat is a nocturnal flying mammal
also
➢ Polysemy is a Greek word, which means “many signs”. polysemy has the same
spelling but different and related meaning.
➢ Both polysemy and homonymy words have the same syntax or spelling. The main
difference between them is that in polysemy, the meanings of the words are related
but in homonymy, the meanings of the words are not related.
➢ For example: Bank Homonymy: financial bank and river bank
Polysemy: financial bank, bank of clouds and book bank: indicate collection of
things.
➢ Categorial ambiguity: the word book can mean a book which contain the chapters or
police register which is used to enter the charges against someone.
➢ In the above note book, text book belongs to the grammatical category of noun and
book is verb.
➢ Distinguishing between these two categories effectively helps disambiguate these two
senses.
➢ Therefore, categorical ambiguity can be resolved with syntactic information (part
of speech) alone, but polyseme and homonymy need more than syntax.
➢ Traditionally, in English, word senses have been annotated for each part of speech
separately, whereas in Chinese, the sense annotation has been done per lemma.

Resources:
➢ As with any language understanding task, the availability of resources is key
factor in the disambiguation of the word senses in corpora.
➢ Early work on word sense disambiguation used machine readable dictionaries or
thesaurus as knowledge sources.
➢ Two prominent sources were the Longman dictionary of contemporary English
(LDOCE) and Roget’s Thesaurus.
➢ The biggest sense annotation corpus OntoNotes released through Linguistic Data
Consortium (LDC).
➢ The Chinese annotation corpus is HowNet.

Systems:
Researchers have explored various system architectures to address the sense disambiguation
problem.
We can classify these systems into four main categories: i. rules based or
knowledge ii. Supervised [Link] iv. Semisupervised

Rule Based:
➢ The first-generation of word sense disambiguation systems was primarily based on
dictionary sense definitions.
➢ Much of this information is historical and cannot readily be translated and made
available for building systems today. But some of techniques and algorithms are still
available.
 6

➢ The simplest and oldest dictionary-based sense disambiguation algorithm was

introduced by Lesk.
The core of the algorithm is that the dictionary senses whose terms most closely overlap with
the terms in the context.

Another dictionary-based algorithm was suggested Yarowsky.

This study used Roget’s Thesaurus categories and classified unseen words into one
of these 1042 categories based on a statistical analysis of 100 word concordances for each
member of each category.
 7

The method consists of three steps, as shown in Fig below.

• The first step is a collection of contexts.
• The second step computes weights for each of the salient words.
• P(w|Rcat) is the probability of a word w occurring in the context of a Roget’s
Thesaurus category Rcat.
• P(w|Rcat) |Pr(w) , the probability of a word (w) appearing in the context of a Roget
category divided by its overall probability in the corpus.
• Finally, in third step, the unseen words in the test set are classified into the category
that has the maximum weight.

Supervised:
• The simpler form of word sense disambiguating systems the supervised approach,
which tends to transfer all the complexity to the machine learning machinery while
still requiring hand annotation tends to be superior to unsupervised and performs best
 8

when tested on annotated data.

• These systems typically consist of a machine learning classifier trained on various
features extracted for words that have been manually disambiguated in a given
corpus and the application of the resulting models to disambiguating words in the
unseen test sets.
• A good feature of these systems is that the user can incorporate rules and knowledge
in the form of features.
Classifier:
Probably the most common and high performing classifiers are support vector machine
(SVMs) and maximum entropy classifiers.
Features: Here we discuss a more commonly found subset of features that have been useful in
supervised learning of word sense.
Lexical context: The feature comprises the words and lemma of words occurring in the entire
paragraph or a smaller window of usually five words.
Parts of speech: the feature comprises the surrounding the word that is being sense tagged.
Bag of words context: this feature comprises using an unordered set of words in the context
window.
Local Collocations: Local collocations are an ordered sequence of phrases near the target word that
provide semantic context for disambiguation. Usually, a very small window of about three tokens
on each side of the target word, most often in contiguous pairs or triplets, are added as a list of
features.
Syntactic relations: if the parse of the sentence containing the target word is available, then we can
use syntactic features.
Topic features: The board topic, or domain, of the article that word belongs to is also a good
indicator of what sense of the word might be most frequent.

"Word sense disambiguation" (WSD) is a natural language processing (NLP) task that involves
determining the correct sense or meaning of a word within a given context. Many words in
natural language have multiple meanings or senses, and WSD aims to choose the most
appropriate sense for a word in a specific sentence or context.
 9

Supervised learning with Support Vector Machines (SVM) is one approach to solving the WSD
problem. Here's how it works:

1. Data Collection: To train an SVM for WSD, you need a labeled dataset where each word
is tagged with its correct sense in various contexts. This dataset is typically created by
human annotators who assign senses to words in sentences.
2. Feature Extraction: For each word in the dataset, you need to extract relevant features
from its context. These features could include the words surrounding the target word,
part-of-speech tags, syntactic information, and more. These features serve as the input to
the SVM.
3. Training: Once you have the labeled dataset and extracted features, you can train an
SVM classifier. The goal is to teach the SVM to learn patterns in the features that are
indicative of specific word senses.
4. Testing/Predicting: After training, you can use the SVM to predict the sense of an
ambiguous word in a new, unseen sentence. The SVM considers the context features and
assigns the word the most likely sense based on what it learned during training.
5. Evaluation: To assess the performance of your WSD system, you can use various
evaluation metrics, such as accuracy, precision, recall, and F1-score. These metrics help
you measure how well your SVM-based WSD system is performing in disambiguating
word senses.

SVMs are popular for WSD because they are effective at handling high-dimensional feature
spaces and can learn complex decision boundaries. However, the success of the SVM-based WSD
system heavily depends on the quality of the labeled dataset and the choice of features used for
training.

The identification of the head word is important in syntax because it helps determine the
grammatical structure of a phrase or sentence. For feature selection in NLP tasks like parsing or
word sense disambiguation, knowing the head word and its relationships with other words in a
 10

sentence can be valuable information. Syntactic relations often involve the relationship between a
head word and its dependents or modifiers, and these relations can be used as features in
various natural language processing applications.

Unsupervised:

Unsupervised learning in Natural Language Processing (NLP) is a category of machine

learning where the model is trained on unlabeled data without explicit supervision or
predefined categories. It aims to discover patterns, structures, or representations within the
data. One concept related to unsupervised learning in NLP is "Conceptual Density."

HyperLex
11
 12

Figure: Conceptual Density

Semi Supervised:
Semi-supervised learning is a machine learning paradigm that combines both labeled and
unlabeled data to improve model performance. In the context of word sense disambiguation
 13

(WSD) in Natural Language Processing (NLP), semi-supervised learning techniques can be

quite beneficial because labeled data for WSD is often limited and expensive to obtain. Here's
an overview of a semi-supervised learning algorithm for WSD:

Self-Training for WSD:

Self-training is a popular semi-supervised learning approach that can be adapted for WSD. In
self-training for WSD, you start with a small set of labeled examples and a larger set of
unlabeled examples. The process involves iterative steps:

1. Initialization: Begin with a small labeled dataset where each example consists of a
sentence containing an ambiguous word and its corresponding sense label.
2. Feature Extraction: Extract relevant features from the labeled examples, which
typically include information about the target word, its context words, part-of-speech
tags, syntactic relations, and more.
3. Model Training: Train a WSD model using the labeled data. This can be a
supervised machine learning model like Support Vector Machines (SVM), Naive
Bayes, or a neural network-based model.
4. Prediction: Use the trained model to predict word senses for the unlabeled data.
Apply the model to the sentences containing the ambiguous word from the unlabeled
dataset to assign senses to those instances.
5. Confidence Threshold: Introduce a confidence threshold or some criteria to filter the
predictions. For instance, you can choose to keep only the predictions where the
model is highly confident.
6. Adding Labeled Data: Add the confidently predicted examples to the labeled
dataset, marking them as newly labeled instances.
7. Iteration: Repeat steps 2-6 for a fixed number of iterations or until convergence.
8. Final Model: Train a final model using the combined labeled data (original labeled
dataset plus the newly labeled instances) to create a more robust WSD model.

Advantages of Self-Training for WSD:

• It leverages a larger pool of unlabeled data, which can be especially beneficial when
labeled data is scarce.
• It allows the model to learn from its own predictions and iteratively improve.
• Self-training is a flexible approach and can be used with various machine learning
models.

Challenges:

• Labeling errors: The initial labeled dataset should be of high quality because errors
can accumulate during self-training iterations.

Semi-supervised learning with self-training can be effective for WSD, but it's essential to
carefully design the process, monitor model performance, and apply filtering criteria to
ensure the quality of the added labeled instances.
 14

Motivation and concept of Yorowsky algorithm

15
 Discourse Processing (Unit-5 Part-2)

Definition of Discourse: Discourse is the coherent structure of language above the level of
sentences or clauses. A discourse is a coherent structured group of sentences.
What makes a passage coherent? A practical answer: It has meaningful
connections between its utterances.
Cohesion
Relations between words in two units (sentences, paragraphs) “glue” them together.
Example: Before winter I built a chimney, and shingled the sides of my house… I have thus
a tight shingled and plastered house.

There are Three Main Classes of Features for Discourse Cohesion

• Lexical overlap/lexical chains
• Coreference chains
• Cue words/discourse markers

Discourse Processing:

One of the major problems in NLP is discourse processing − building theories and models of
how utterances stick together to form coherent discourse. Actually, the language always
consists of collocated, structured and coherent groups of sentences rather than isolated and
unrelated sentences like movies. These coherent groups of sentences are referred to as
discourse.

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.

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 Shyam’s 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 Shyam’s 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

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

We use the following terminologies 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, It’s 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.