Augmented Grammars

Parts-of-Speech (POS) Tagging

• Each word has a part-of-speech tag to describe its category.

• Part-of-speech tag of a word is one of major word groups (or its subgroups).

– open classes -- noun, verb, adjective, adverb

– closed classes -- prepositions, determiners, conjuctions, pronouns, particples

• POS Taggers try to find POS tags for the words.

•duck is a verb or noun? (morphological analyzer cannot make decision).

• A POS tagger may make that decision by looking the surrounding words.

– Duck! (verb)

– Duck is delicious for dinner. (noun)

Semantic Interpretation

Semantics: The meanings of the atomic symbols of the logic, and the rules for

determining the meanings of non-atomic expressions of the logic. It specifies what facts

in the world a sentence refers to. Hence, also specifies how you assign a truth value to a

sentence based on its meaning in the world. A fact is a claim about the world, and may be

true or false.

There are a number of logical systems with different syntax and semantics. We list below

a few of them.

Syntactic Processing

• Parsing -- converting a flat input sentence into a hierarchical structure that

corresponds to the units of meaning in the sentence.

• There are different parsing formalisms and algorithms.

• Most formalisms have two main components:

– grammar -- a declarative representation describing the syntactic structure

of sentences in the language.

– parser -- an algorithm that analyzes the input and outputs its structural

representation (its parse) consistent with the grammar specification.

• CFGs are in the center of many of the parsing mechanisms. But they are

complemented by some additional features that make the formalism more suitable

to handle natural languages.

Formal grammar for a fragment of English

Ambiguities are resolved using the following methods.

• models and algorithms are introduced to resolve ambiguities at different levels.

• part-of-speech tagging -- Deciding whether duck is verb or noun.

• word-sense disambiguation -- Deciding whether make is create or cook.

• lexical disambiguation -- Resolution of part-of-speech and word-sense ambiguities are two important kinds of lexical disambiguation.

• syntactic ambiguity -- her duck is an example of syntactic ambiguity, and can be addressed by probabilistic parsing.

Syntactic analysis

Syntax: The atomic symbols of the logical language, and the rules for constructing wellformed,

non-atomic expressions (symbol structures) of the logic. Syntax specifies the

symbols in the language and how they can be combined to form sentences. Hence facts

about the world are represented as sentences in logic.

Represent knowledge as formal logic:

All dogs have tails : dog(x) hasatail(x) Advantages:

• A set of strict rules.

o Can be used to derive more facts.

o Truths of new statements can be verified.

o Guaranteed correctness.

• Many inference procedures available to in implement standard rules of logic.

• Popular in AI systems. e.g Automated theorem proving.

Basic idea:

• Knowledge encoded in some procedures

o small programs that know how to do specific things, how to proceed.

o e.g a parser in a natural language understander has the knowledge that a noun phrase may contain articles, adjectives and nouns. It is represented by calls to routines that know how to process articles, adjectives and nouns.

Advantages:

• Heuristic or domain specific knowledge can be represented.

• Extended logical inferences, such as default reasoning facilitated.

• Side effects of actions may be modelled. Some rules may become false in time.

Keeping track of this in large systems may be tricky.

Disadvantages:

• Completeness -- not all cases may be represented.

• Consistency -- not all deductions may be correct.

e.g If we know that Fred is a bird we might deduce that Fred can fly. Later we might discover that Fred is an emu.

• Modularity is sacrificed. Changes in knowledge base might have far-reaching effects.

• Cumbersome control information.

The following properties should be possessed by a knowledge representation system.

Representational Adequacy

-- the ability to represent the required knowledge;

Inferential Adequacy

- the ability to manipulate the knowledge represented to produce new knowledge

corresponding to that inferred from the original;

• Representations of actions: programs that develop successor state descriptions which

represent actions.

• Representation of state: every state description is complete. This is because a

complete description of the initial state is given, and actions are represented by a program

that creates complete state descriptions.

• Representation of goals: a problem solving agent has only information about it's

goal, which is in terms of a goal test and the heuristic function.

• Representation of plans: in problem solving, the solution is a sequence of actions.

In a simple problem: "Get a quart of milk and a bunch of bananas and a variable speed

cordless drill" for a problem solving exercise we need to specify:

Initial State: the agent is at home without any objects that he is wanting.

Operator Set: everything the agent can do.