14 Natural Language Processing

Question 1

Communication

Answer 1

One definition of communication
• Communication is the intentional exchange of information brought about by the production and perception of signs drawn from a shared system of a limited number of conventional signs

Humans use language to communicate
• Language is a “shared system of a limited number of conventional signs”
• Its structure is sufficiently rich to allow an unbounded number of qualitatively different messages

Question 2

Communication and action

Answer 2

To produce messages in a language is one of the actions available to an agent. This action is called a speech act (can be spoken, written, etc.). In a speech act, an utterance consisting of words is delivered from a speaker to a hearer. Different types of speech acts serve different purposes.

Question 3

Some types of speech acts

Answer 3

• *Inform** Provide information to hearer
• *Query** Ask for information
• *Answer** Inform in response to query
• *Request** Ask hearer to perform action
• *Deny** Refuse to perform action
• *Command** Request with no option to deny
• *Promise** Commit to future action
• *Offer** Propose to do future action
• *Acknowledge** Confirm e.g. request or offer…

Question 4

Planning and understanding speech acts

Answer 4

Deciding when a speech act is called for, and decide which one to use, is equivalent to planning. Understanding a speech act is similar to diagnosis or plan recognition. I.e., one can use methods from other parts of AI in implementing perception and action in communicating agents.

Question 5

Natural and formal languages

Answer 5

Natural languages are a rich field of empirical and logical study, including in AI. Formal languages are invented ones, in contrast to natural languages, and include logic, etc. Formal language concepts are being used in analysis of natural languages.

Question 6

Formal language concepts

Answer 6

A formal language is a set of strings (sentences) (S): “The wumpus is dead”. A string is a sequence of symbols taken from a finite set called the terminal symbols (words): “dead”, “is”, “wumpus”, “the”. A phrase is a substring of a sentence. There are different categories (symbolized by nonterminal symbols) of phrases. NP (noun phrase): “the wumpus” and VP (verb phrase): “is dead”.

The structure (grammar) of a language can be defined using a phrase structure, i.e. combinations of terminal and nonterminal symbols NP VP. Rewrite rules define how a single nonterminal symbol (phrase) may be replaced by a structure S => NP VP .

Question 7

A grammar for a fragment of English

Answer 7

Lexicon:

• List of valid words
• Categories: Noun, verb, adjective, . . .

Grammar:

• Rules for valid sentences
• Nonterminals: Sentence (S), noun phrase (NP) . . .

Parsing:
- Analyze a given sequence of lexicon words as a tree - structure allowed by grammar rules

Question 8

Parsing

Answer 8

Search for a parse tree for a given sentence, e.g.
PARSE(”the wumpus is dead”, grammar, S)

Question 9

Different approaches to parsing

Answer 9

Top-down parsing:
• Initial parse tree is the root with unknown children [S: ?]
• At each step, select leftmost node in the tree with unknown children and look for grammar rules with LHS that matches the node. Replace ? with RHS and repeat
• Stop when leaves of the tree exactly matches the string

• *Bottom-up parsing:**
• Initial list of words, seen as list of singleton parse trees
• At each step, replace each sequence of parse trees that matches an RHS of a grammar rule, with the corresponding LHS, and repeat
• Stop when the tree is the single node S

Question 10

Parsing: Semantic interpretation

Answer 10

Having analyzed the sentence, we need to interpret its meaning; i.e. decide its semantic content. We adopt first-order logic (FOL) as the representation language. E.g., “the wumpus is dead and John loves Mary” has the meaning:
Dead(Wumpus) ^ Loves(John,Mary)

Compositional semantics: The meaning of the entire sentence is composed of the meanings of its constituents.

Question 11

Augmenting grammar for semantics

Answer 11

Each category of the grammar is augmented with a single argument that represents the semantics:

NP becomes NP(obj)
where obj is the FOL term that represents the noun phrase

VP becomes VP(rel)
where rel is the FOL relation (predicate) that represents the verb

Also needs λ-expressions for verbs:

• λxLoves(x, Mary) - the predicate of variable x such that x loves Mary
• (λxLoves(x, Mary))(John) - the predicate applied to the argument John, yielding Loves(J ohn, M ary)

[Semantically augmented grammar fragment]

[Deriving semantics during parsing]

Question 12

Steps of communication

Answer 12

Speaker steps
Intention: Speaker decides that there is something to say, e.g. by reasoning about beliefs and goals of hearer, Know(H,¬Alive(Wumpus,S3)).

Generation: Speaker uses knowledge about language in deciding what to say, “The wumpus is dead”.

Synthesis: Finally, the sentence is uttered via the “speech act organ” (printer, screen, speech synthesizer, . . . ).

Hearer steps
Perception:
- The utterance is received, e.g. by speech recognition, scene analysis, . . .

Analysis:
- Parsing : Recognizing constituent phrases (parse tree)
- Interpretation: Extract meaning as expression in e.g. logic
- Analysis may yield different interpretations, and the agent must choose the most probable one, e.g. using disambiguation:
probabilistic reasoning, Alive(W umpus, S3)

Incorporation:
- Finally, the agent updates its knowledge base with the new information, TELL(KB, ¬Alive(Wumpus, S3)).

Question 13

Machine translation

Answer 13

MT by deep linguistic analysis
MT by three-step process
1. Analyze source text syntactically and semantically
2. Create deep knowledge representation of meaning of source text
3. Generate target text representing the same meaning in target syntax

Can use methods described earlier for natural language communication, but problematic. Requires rich semantic model (FOL not sufficient?) and strong parsing and generation capabilities.

MT by using transfer model
Large database of translation rules and examples on lexical, syntactic and semantic levels. Can match rules/examples on any level.

Statistical machine translation
Successful MT systems (e.g. Google Translate) are built by training probabilistic models using statistics from large text collections. Does not need complex ontologies or grammars of source and target languages. Relies on large amounts of sample translations from which a transfer model can be learned.