Natural Language Processing(NLP)

What is Artificial Intelligence?

• According to the father of Artificial Intelligence, John
McCarthy, it is “The science and engineering of making
intelligent machines, especially intelligent computer
programs”.

• Artificial Intelligence is a way of making a computer, a

computer-controlled robot, or a software think
intelligently, in the similar manner the intelligent humans
think.

• AI is accomplished by studying how human brain thinks,

and how humans learn, decide, and work while trying to
solve a problem, and then using the outcomes of this
study as a basis of developing intelligent software and
systems.
 Goals of AI

• To Implement Human Intelligence in

Machines − Creating systems that understand,
think, learn, and behave like humans.
• To Create Expert Systems − The systems which
exhibit intelligent behavior, learn,
demonstrate, explain, and advice its users.
• Natural language processing (NLP) is a branch of
artificial intelligence within computer science that
focuses on helping computers to understand the way
that humans write and speak.
• Developing programs to understand natural
language is important in AI because a natural
form of communication with systems is essential
for user acceptance.
• One of the most critical tests for intelligent
behavior is the ability to communicate effectively.
• AI programs must be able to communicate with
their human counterparts in a natural way, and
natural language is one of the most important
mediums for that purpose.
• Natural languages are the languages used by
humans for communication.
• They are distinctly different from formal
languages, such as C++, Java, and PROLOG.
• The natural languages are ambiguous, meaning
that a given sentence can have more than one
possible meaning, and in some cases the
correct meaning can be very hard to determine.
 Overview of linguistics
• Language is the normal way humans
communicate.
• Human language has syntax, a set of rules for
connecting words together to make
statements and questions.
• The principal method of human
communication, consisting of words used in a
structured and conventional way and
conveyed by speech, writing, or gesture.
• An understanding of linguistics is not a
prerequisite to the study of natural language
understanding.
• Linguistics is the scientific study of language.
– Including properties of particular language as well
as the characteristics of language.
• It involves the analysis of language form,
language meaning, and language in context.
• To express a complete thought, a sentence
must have a subject and a predicate.
• The subject is what the sentence is about, and
the predicate says something about the subject.
• The way a sentence is used determines its
mood, declarative, imperative, interrogative
or exclamatory.
Levels of knowledge used in language
understanding
• In dealing with natural language, a computer
system needs to be able to process and
manipulate language at a number of levels.
• A language understanding program must have
considerable knowledge about the structure
of the language including what the words are
and how they combine into phrases and
sentences.
• It must also know the meanings of the words
and how they contribute to the meanings of a
sentence and to the context within which they
are being used.
• Finally, a program must have some general
world knowledge of what humans know and
how they reason.
• The component forms of knowledge needed
for an understanding of natural language are
sometimes classified according to the
following levels.
 Phonological.
• It deals with patterns of sounds .
• This is knowledge which relates sounds to the words
we recognize.
• A phoneme is the smallest unit of sound.
• Phones are aggregated into word sounds.
• Phonology is the study of the sounds that make up
words and is used to identify words from sounds.
• This is needed only if the computer is required to
understand spoken language.
• E.g.
– Pronounce Pay, Bay and eBay
 Morphological
• It means structure of words.
• This is lexical knowledge which relates to word
constructions from basic units called
morphemes.
• A morpheme is the smallest unit of meaning.
– For example, the construction of ‘friendly’ from the
root ‘friend’ and the suffix ‘ly’.
• This is the first stage of analysis that is applied
to words, once they have been identified from
speech, or input into the system.
• Morphology looks at the ways in which words
break down into components and how that
affects their grammatical status.
• For example, the letter “s” on the end of a word
can often either indicate that it is a plural noun or
a third-person present-tense verb.
• Eg
– Bird to birds
– Friend to friendly
 Syntactic
• It means the Structure of Language.
• This knowledge relates to know words are put
together or structures to form grammatically
correct sentences in the language.
• This stage involves applying the rules of the
grammar from the language being used.
• E.g.
– I hit the ball (S V O -> Subject Verb Object;
 Semantic
• It means meaning of a language.
• This knowledge is concerned with the meanings of
words and phrases and how they combine to form
sentence meanings.
• This involves the examination of the meaning of words
and sentences.
• As we will see, it is possible for a sentence to be
syntactically correct but to be semantically meaningless.
• Conversely, it is desirable that a computer system be
able to understand sentences with incorrect syntax but
that still convey useful information semantically.
• E.g. I bought a pen
 Pragmatic
• This is high-level knowledge which relates to the
use of sentences in different contexts and how
the context affects the meaning of the sentences.
• This is the application of human-like
understanding to sentences and discourse to
determine meanings that are not immediately
clear from the semantics.
– For example, if someone says, “Can you tell me the
time?”, most people know that “yes” is not a suitable
answer.
• Pragmatics enables a computer system to give a
sensible answer to questions like this.
 World

• World knowledge relates to the language a

user must have in order to understand and
carry on a conversation.
• It must include an understanding of the other
person’s beliefs and goals.
 NLP Terminology
Phonology − It is study of organizing sound systematically.
Morphology − It is a study of construction of words from primitive
meaningful units.
Morpheme − It is primitive unit of meaning in a language.
Syntax − It refers to arranging words to make a sentence. It also
involves determining the structural role of words in the sentence
and in phrases.
Semantics − It is concerned with the meaning of words and how to
combine words into meaningful phrases and sentences.
Pragmatics − It deals with using and understanding sentences in
different situations and how the interpretation of the sentence is
affected.
Discourse − It deals with how the immediately preceding sentence can
affect the interpretation of the next sentence.
World Knowledge − It includes the general knowledge about the
world.
NLP Phases
• When a string of words has been detected, the
sentences are parsed or analyzed to determine
their structure(syntax) and grammatical
correctness.
• The meanings(semantics) of the sentences are
then determined and appropriate representation
structures created for the inferencing programs.
• The whole process is a series of transformations
from the basic speech sounds to a complete set
of internal representation structures.
 Components of NLP
There are two components of NLP as given −
– Natural Language Understanding (NLU)
– Natural Language Generation (NLG)
Natural Language Understanding (NLU)

• Understanding involves the following tasks −

– Mapping the given input in natural language into
useful representations.
– Analyzing different aspects of the language.
• Syntax and semantical analysis.
• Syntactic analysis (syntax) and semantic analysis
(semantic) are the two primary techniques used to the
understanding of natural language.
 Natural Language Generation (NLG)

• It is the process of producing meaningful phrases and

sentences in the form of natural language from some
internal representation.
• It involves −
– Text planning − It includes retrieving the relevant content
from knowledge base.
– Sentence planning − It includes choosing required words,
forming meaningful phrases, setting tone of the sentence.
– Text Realization − It is mapping sentence plan into
sentence structure.
• The NLU is harder than NLG.
 Difficulties in NLU
• NL has an extremely rich form and structure.
• It is very ambiguous. There can be different levels
of ambiguity −
– Lexical ambiguity − It is at very primitive level such as
word-level.
• For example, treating the word “board” as noun or verb?
– Syntax Level ambiguity − A sentence can be parsed in
different ways.
• For example, “He lifted the beetle with red cap.”
– Did he use cap to lift the beetle or he lifted a beetle that had red
cap?
– Referential ambiguity − Referring to something using
pronouns.
• For example, Rima went to Gauri. She said, “I am tired.”
– Exactly who is tired?
 General Approaches to Natural
Language Understanding
• Three different approaches taken in the
development of natural language understanding
programs are
1)The use of keyword and pattern matching.
2) Combined syntactic(structural) and semantic
directed analysis.
3) Comparing and matching the input to real world
situations(scenario representations).
 1)The use of keyword and pattern matching.

• It is the simplest approach.

• This approach was first used in programs such
as ELIZA.
• It is based on the use of sentence templates
which contain key words or phrases such as “--
------- my mother ----------,”, “ I am ---------,” and
“I don’t like -------,”that are matched against
input sentences.
• The advantage of this approach is that
ungrammatical, but meaningful sentences are
still accepted.
• The disadvantage is that no actual knowledge
structures are created, so the program does
not really understand.
 2) Combined syntactic(structural) and semantic
directed analysis.

• The most popular approach currently being

used.
• With this approach, knowledge structures are
constructed during a syntactical and
semantical analysis of the input sentences.
• Parsers are used to analyze individual
sentences and to build structures that can be
used directly or transformed into the required
knowledge formats.
• The advantage of this approach is in the
power and versatility it provides.
• The disadvantage is the large amount of
computation required and the need for still
further processing to understand the
contextual meanings of more than one
sentence.
 3) Comparing and matching the input to real
world situations(scenario representations).
• It is based on the use of structures.
• This approach relies more on a mapping of the
input to prescribed primitives which are used
to build larger knowledge structures.
• It depends on the use of constraints imposed
by context and world knowledge to develop an
understanding of the language inputs.
• Its advantage is that much of the computation
required for syntactical analysis is bypassed.
• The disadvantage is that a substantial amount
of specific, as well as general world knowledge
must be pre stored.
 Grammars and Languages
• A language L can be considered as a set of
strings of finite or infinite length, where a
string is constructed by concatenating basic
atomic elements called symbols.
• The finite set of v of symbols of the language
is called the alphabet or vocabulary.
• Well - formed sentences are constructed using
a set of rules called a grammar.
• A grammar G is a formal specification of the
sentence structures that are allowable in the
language, and the language generated by the
grammar G is denoted by L(G).
• We define a grammar G in automata as
G=(vn, vt, S, P) where vn is the set of non terminal
symbols and vt a set of terminal symbols, S is a
starting symbol, and P is a finite set of productions
or rewrite rules.
• Non terminals (variables)
– Symbols which take part in the generation of the
sentence and can be expanded.
– Represented using capital letter.
– Ex: A, N
• Terminals(constants)
– Symbols which take part in the generation of the
sentence and cannot be expanded.
– Represented using small case letter.
– Ex: a, b
• Production rule
– How language is generated from grammar.
• The alphabet v is the union of the disjoint sets
vn and vt which includes the empty string e.
• The terminals vt are symbols which cannot be
decomposed further whereas the non
terminals can be decomposed.
• A general production rule from P has the form
xyz xwz where x,y,z and w are strings
from v.
• This rule states that y should be rewritten as w
in the context of x to z where x and z can be
any string including the empty string e.
• As an example of a simple grammar G, we
choose one which has component parts or
constituents from English with vocabulary Q
given by
• QN={S,NP,N,VP,V,ART}
• QT={ boy, popsicle, frog, ate, kissed, flew, the,
a}
• S is the initial symbol
• NP stands for noun phrase.
• VP stands for verb phrase.
• N stands for noun.
• V stands for verb.
• ART stands for article.
• Rewrite rules by
P: S NP VP
NP ART N
VP V NP
N boy | popsicle | frog
V ate |kissed | flew
ART the |a
Where the vertical bar indicates alternative
choices.
• With the above G, sentences such as the
following can be generated.
– The boy ate a popsicle.
– The frog kissed a boy
– A boy ate the frog
• To generate a sentence ,the rules from P are
applied sequentially starting with S and
proceeding until all nonterminal symbols are
eliminated.
• The first sentence given above can be
generated using the following sequence of
rewrite rules.
 S NP VP
ART N
VP V NP
N boy | popsicle | frog
v ate |kissed | flew
ART the |a
Where the vertical bar indicates alternative
choices.
• Rewrite rules by
S NP VP
NP ART N VP
the N VP
the boy VP
the boy V NP
the boy ate NP
the boy ate ART N
the boy ate a N
the boy ate a popsicle.
The Chomsky Hierarchy of Generative
Grammars
• Noam Chomsky defined a hierarchy of
grammars.
– Type 0
– Type 1
– Type 2
– Type 3
 Type 0 or Unrestricted
Grammar/Phrase Structured Grammar
• Type-0 grammars generate recursively
enumerable languages.
• The productions have no restrictions.
• They generate the languages that are
recognized by a Turing machine.
• Type 0 grammar is the most general.
 Type 0 or Unrestricted
Grammar/Phrase Structured Grammar
• It is obtained by making the simple restriction
that y cannot be empty string in the rewrite
form xyz xwz.
• This broad generality requires that a computer
having the power of a Turing machine be used
to recognize sentences of type 0.
• Production Rule
α β
α≠ε
Ie. LHS is not empty
α , β are strings of terminals and non terminals.
This language is recognized by Turing machine.
e.g
A Bc
Example

S → ACaB
Bc → acB
CB → DB
aD → Db
 Type 1 Grammar/ Context-Sensitive
Grammar
• CSG have the added restriction that the length
of the string on the right-hand side of the
rewrite rule must be at least as long as the
string on the left hand side.
• Furthermore, in productions of the form
xyz xwz, y must be a single non
terminal symbol and w, a nonempty string.
• Production Rule
α β
α≠ε

Β ≥ α

Ie. The length of strings on the right side must be

greater than or equal to LHS.
α , β are strings of terminals and non terminals.
This language is recognized by linear bounded
automata.
• eg
S AB
A a | Ac
B b

Here α = S, β=AB
The language generated is
S AB
S AcB
S Acb
S acb
Example

AB → AbBc
A → bcA
B→b
 Type 2 Grammar/ Context-free
Grammar
• It is characterized by rules with the general
form
<symbol> <symbol 1>..........<symbol k>
where k>=1 and where the left hand side is a
single nonterminal symbol, A xyz where A
is a single nonterminal.
• Production rule
A α
A is nonterminal can be expanded and α is terminal or
nonterminal.
LHS should be single nonterminal and RHS is any
combination.
• Productions for this type take terms such as
S aS
S aSb
S aB
S aAB
A a
B b
Type 3 Grammar/ Regular/Finite State
Grammar
• Most restrictive type grammar
• Rules are
A aB
A a
Type-3 grammars must have a single non-
terminal on the left-hand side and a right-
hand side consisting of a single terminal or
single terminal followed by a single non-
terminal.
• The languages generated by these grammars
are also termed type 0,1,2 and 4
corresponding to the grammars which
generate them.
• Example
• S aB
• B b
 Structural Representations
• It is convenient to represent sentences as a
tree or graph to expose the structure of the
constituent parts.
• The root node of the tree corresponds to the
whole sentence S, and the constituent parts of
S are sub trees.
 Basic Parsing Techniques
• The process of determining the syntactical
structure of a sentence is known as parsing.
• Parsing is the process of analyzing a sentence
by taking it apart word-by-word and
determining its structure from its constituent
parts and subparts.
• The structure of a sentence can be
represented with a syntactic tree or list.
Phrase marker or syntactic tree
• To determine the meaning of a word, a parser must
have access to a lexicon .
• When the parser selects a word from the input stream
it locates the word in the lexicon and obtains the
word’s possible function and other features, including
semantic information.
• The general parsing process is illustrated in the
following figure.
 The Lexicon
• A lexicon is a dictionary of words(usually
morphemes or root words together with their
directives) , where each word contains some
syntactic, semantic, and possibly some
pragmatic information.
• The information in the lexicon is needed to
help determine the function and meanings of
the words in a sentence.
• Each entry in the lexicon will contain a root
word called the head.
• A fragment of a simplified lexicon is
illustrated in the following figure.
• The abbreviations 1s,2s....3p stand for first
person singular...third person plural
respectively.
Word Type Features
a Determiner {3s}
b Verb Trans: intransitive
boy Noun {3s}

can Noun {1s,2s,3s,lp,2p,3p}

can Verb
carried Verb Form: past, past
participle
Orange Adjective
Noun {3s}
The Determiner {3s,3p}
to preposition
 Transition Networks
• They are another popular method to represent
formal and natural language structures.
• It is based on the application of directed
graphs(digraphs) and finite state automata.
• A transition network consists of a number of
nodes and labelled arcs.
• The nodes represent different states in traversing
a sentence, and the arcs represent rules or test
conditions required to make the transition from
one state to the next.
• A path through a transition network corresponds
to a permissible sequence of word types for a
given grammar.
• Thus, if a transition network can be successfully
traversed, it will have recognized a permissible
sentence structure.
• For eg, a network used to recognize a sentence
consisting of a determiner, a noun and a verb
would be represented by the three-node graph as
follows.
DETERMINER NOUN VERB

N1 N2 N3 N4
• Starting at node N1, the transition from node N1
to N2 will be made if a determiner is the first
input word found.
• If successful, state N2 is entered.
• The transition from N2 to N3 can then be made if
a noun is found next.
• The final transition from N3 to N4 will be made if
the last word is a verb.
• If the three-word category sequence is not found,
the parse fails.
• If several arcs were constructed between
nodes N1 and N2 where each arc represented
a different noun phrase, the number of
permissible sentence types would be
increased subtantially.
• Individual arcs could be a noun, a pronoun, a
determiner followed by a noun, a noun phrase
etc.
 Adjective

Determiner Adjective

Noun
Pronoun N3
NP: N1 N2
Proper Noun

Jump

Fig: A noun phrase segment of a transition

network
• To move from state N1 to N2 in this transition
network, it is necessary to first find an
adjective, a determiner , a pronoun, a proper
noun, or none of these by “jumping” directly to
N2.
• This transition network will recognize noun
phrases having forms such as
– Big white fluffy clouds
– Our bright children
– A large beautiful white flower
– Large green leaves
– Buildings
– Boston’s best seafood restaurants.
 Top –down vs Bottom-up parsing
• There are two parsing methods
– Top-down Parsing
– Bottom-up Parsing
• The Key Difference Between Top-down and
Bottom-up Parsing is that Top-down
parsing starts from the top level and moves
downwards Whereas Bottom-up
parsing starts from the bottom level and
moves upwards
• A top-down parser begins by hypothesizing a
sentence (the symbol S) and successively
predicting lower level constituents until
individual preterminal symbols are written.
• These are then replaced by the input sentence
words which match the terminal categories.
• For eg, a possible top-down parse of the sentence
“kathy jumped the horse” would be given by
S NP VP
NAME VP
KATHY VP
KATHY V NP
KATHY JUMPED NP
KATHY JUMPED ART N
KATHY JUMPED THE N
KATHY JUMPED THE HORSE
• A bottom-up parser, on the other hand,
begins with the actual words appearing in the
sentence and is, therefore, data driven.
• A possible bottom-up parse of the same
sentence might proceed as follows.
KATHY JUMPED THE HORSE
NAME JUMPED THE HORSE
NAME V THE HORSE
NAME V ART HORSE
NAME V ART N
NP V ART N
NP V NP
NP VP
S
 Deterministic Vs Nondeterministic
parsers
• Parsers also be classified as
– Deterministic or
– Nondeterministic
depending on the parsing strategy.
 Deterministic Parsers
• A deterministic parser permits only one
choice(arc) for each word category.
• Thus, each arc will have a different test
condition.
• If an incorrect test choice is accepted from
some state, the parser will fail since the parser
cannot backtrack to an alternative choice.
 Nondeterministic Parsers
• It permits different arcs to be labelled with the
same test.
• Consequently, the next test from any given
state may not be uniquely determined by the
state and the current input word.
Semantic Analysis and Representation
Structures
• Attempts to understand the meaning of Natural
Language.
• Semantic Analysis of Natural Language captures the
meaning of the given text while taking into account
context, logical structuring of sentences and grammar
roles.
• The domain refers to the knowledge that is part of the
world model the system knows about .
• This includes object descriptions, relationships, and
other relevant concepts.
• The context refers to previous expressions, the
setting and time of the utterances and the
beliefs, desires and intentions of the speakers.
• A task is part of the service the system offers
such as retrieving information from a database
providing expert advice, or performing a
language translation.
• The domain, context, and task are referred to
as semantics, pragmatics and world
knowledge.
 Transformation stages
• In the first stage, a syntactic analysis is
performed and a tree like structure is
produced using a parser.
• This stage is followed by use of a semantic
analyzer to produce either an intermediate or
final semantic structure.
• Another approach is to transform the
sentences directly into the target structures
with little syntactical analysis.
 Lexical semantics approaches
• Lexical Semantic Analysis involves
understanding the meaning of each word of the
text individually.
• It basically refers to fetching the dictionary
meaning that a word in the text is deputed to
carry.
• A second example of an informal lexical-
semantic approach is one which uses
conceptual dependency theory.
• Conceptual dependency structures provide a
form of linked knowledge that can be used in
larger structures such as scenes and scripts.
• The construction of conceptual dependency
structures is accomplished without performing
any direct syntactic analysis.
• CD representation of a sentence is not built using
words in the sentence rather build using
conceptual primitives which give the intended
meaning of words.
 Conceptual dependency structure
** PP stands for picture producer

ACTOR : (a PP with animate attributes)

OBJECT: (a PP)
ACTION: (one of the primitive acts with tense)
DIRECTION: (from-to direction of the action)
INSTRUMENT: (object with which the act is performed)
LOCATION:(event location information)
TIME: (time of the event information)
• Event structures include objects and their
attributes, picture producers(PPs) or actors ,
actions , direction of action and sometimes
instruments that participate in the actions and
the location and time of the event.
• The basic process followed in building
conceptual dependency structures is simply
the three steps listed below.
– Obtain the next lexical item(a word or phrase)
– Access the lexical entry for the item and obtain
the associated tests and actions.
– Perform the specified actions given with the entry.
• Three types of tests are performed in step2
– If a certain lexical entry is found, the indicated action
is performed. This corresponds to true(non-nil in LISP)
– Specific word orderings are checked as the structure is
being built and actions initiated as a result of the
orderings. For eg, if a PP follows the last word parsed,
action is initiated to fill the object slot.
– Checks are made for specific words or phrases and if
found, specified actions taken. For eg, if an intransitive
verb such as listen is found, an action would be
initiated to look for associated words which complete
the phrase beginning with to or for.
• For the above tests, there are four types of
actions taken.
– Adding additional structure to a partially built
conceptual dependency.
– Filling a slot with a substructure.
– Activating another action.
– Deactivating an action
• These actions build up the conceptual
dependency structure as the input string is
parsed.
• For eg, the action taken for a verb like ‘drank ‘
would be to build a substructure for the
primitive action INGEST with unfilled slots for
ACTOR,OBJECT and TENSE.
 (INGEST (ACTOR nil)
(OBJECT nil)
(ACTION drank)
(TENSE past))

Subsequent words in the input string would initiate

actions to add to this structure and fill in the
empty ACTOR and OBJECT slots.
Thus , a simple sentence like “ the boy drank a
soda”
Compositional Semantics Approaches
• In compositional semantic approach, the
meaning of an expression is derived from the
meanings of the parts of the expression.
• The target knowledge structures constructed
in this approach are typically logic expressions
such as the formulas of FOPL.
 Natural Language Generation
• Language generation is the exact inverse of language
understanding.
• A generation system must decide which form is
better(active or passive). Which words and structures
best express the intent, and when to say what.
• The study of language generation falls naturally into
three areas.
1) The determination of content.
2) Formulating and developing a text utterance plan
3) Achieving a realization of the desired utterances.
 Content determination
• Content determination is concerned with
what details to include in an explanation, a
request, a question or argument in order to
convey the meanings set forth by the goals of
the speaker.
• This means the speaker must know what the
hearer already knows, what the hearer needs
to know and what the hearer wants to know.
• Text planning is the process of organizing the
content to be communicated so as to best
achieve the goals of the speaker.
• Realization is the process of mapping the
organized content to actual text.
• This requires that specific words and phrases
be chosen and formulated into a syntactic
structure.
 Language planning and generation
with KAMP
• KAMP is a knowledge and modalities planner
developed for the generation of natural
language text.
• KAMP simulates the behavior of an expert
robot named Rob(a terminal) assisting John (a
person) in the disassembly and repair of air
compressors.
• KAMP uses a planner and a data base of
knowledge in logical form.
• This knowledge includes domain knowledge,
world knowledge, linguistic knowledge and
knowledge about the hearer.
• A description of actions and action summaries
are available to the planner.
• Given a goal, the planner uses heuristics to build
and refine a plan in the form of a procedural
network.
• Other procedures act as critics of the plans and
help to refine them.
• If a plan is completed, a deduction system is used
to prove that the sequence of actions do, in fact,
achieve the goal.
• If the plan fails, the planner must do further
searching for a sequence of actions that will
work.
• A completed plan states the knowledge and
intentions of the agent, the robot Rob.
• The overall process of planning and
formulating the final sentence ”Remove the
pump with the wrench in the toolbox”
 Generation from conceptual
dependency structures
• A generation component called BABEL is used
as part of several language understanding
systems.
• BABEL selects and builds an appropriate
conceptual dependency structure which
includes the intended word senses.
• To determine the proper word sense, BABEL
uses a discrimination net.
• For eg, Joe going into a fast-food restaurant,
ordering a sandwich and a soft drink in a can,
paying,eating and then leaving.
• After the understanding part of the system
builds the conceptual dependency and script
structures for the story, questions about the
events could be posed.
• If asked what Joe had in the restaurant ,
BABEL would first need to determine the
conceptual category of the question in order
to select the proper conceptual dependency
pattern to build.
• The verb in the query determines the
appropriate primitive categories of eat and
drink as being INGEST.
 Assignment on
Natural language systems
• Following are the few successful natural
language understanding systems.
– LUNAR
– LIFER
– SHRDLU
Expert System Architectures
Introduction

• A computer system which emulates the decision making ability of a

human expert.
• An expert system is a set of programs that manipulate encoded
knowledge to solve problems in a specialized domain that normally
requires human expertise.
• Using AI.
• It is a knowledge based program.
• An expert system’s knowledge is obtained from expert sources and
coded in a form suitable for the system to use in its inference or
reasoning processes.
• The expert knowledge must be obtained from specialists or other
sources of expertise such as texts, journal, articles and data bases.
• Once a sufficient body of expert knowledge has been acquired, it
must be encoded in some form, loaded into a knowledge base, then
tested and refined continually throughout the life of the system.
• Expert system is able to solve real world problems.
Characteristic features of Expert systems
1) Expert systems use knowledge rather than data to control the solution
process.
2) The knowledge is encoded and maintained as an entity separate from
the control program.
3) Expert systems are capable of explaining how a particular conclusion was
reached, and why requested information is needed during a
consultation.
5) Expert systems use symbolic representations for knowledge (rules,
networks,or frames) and perform their inference through symbolic
computations that closely resemble manipulations of natural language.
6) Expert systems often reason with metaknowledge. I.e they reason with
knowledge about themselves and their own knowledge limits and
capabilities.
Applications

• Different types of medical diagnoses.

• Diagnosis of complex electronic and electromechanical systems.
• Diagnosis of software development projects.
• Planning experiments in biology, chemistry and molecular genetics.
• Forecasting crop damage
Basic Elements of ES
• Knowledge base
• Collection of rules or other information structure.
• Knowledge is data, information, or past experience etc...
• Derived from human expert.
• Inference engine
• Main processing element in ES.
• Responsible for gathering information from the user.
• It makes use of knowledge base , in order to draw conclusions for situations.
• Provide answers, predictions etc.
• User interface
• ES interacts with the user through NLP, editors, graphical systems, documentation
etc.
Types of Expert systems
1. Rule based system
2. Nonproduction system
3. Case based systems
4. Hybrid systems
 RULE-BASED SYSTEM ARCHITECTURES
• The most common form of architecture used in expert
and other types of knowledge based systems is the
production system, also called the rule-based system.
• This system have the ability to use the experimental
knowledge acquired from a human expert.
• Here knowledge is represented in the form of
production rules.
• This type of system uses knowledge encoded in the
form of production rules, that is, if ------then rules.
• Rules have an antecedent or condition part(LHS) and
a consequent or conclusion or action part(RHS).
If <antecedent>
Then <consequent>

• If the traffic light is ‘green’, Then the action is ‘go’

• If the traffic light is ‘red’, Then the action is ‘stop’
• Inference in production systems is accomplished by a
process of chaining through the rules recursively, either
in a forward or backward direction, until a conclusion is
reached or until failure occurs.
• The selection of rules used in the chaining process is
determined by matching current facts against the
domain knowledge or variables in rules and choosing
among a candidate set of rules the ones that meet
some given criteria, such as specificity.
• The inference process is typically carried out in an
interactive mode with the user providing input
parameters needed to complete the rule chaining
process.
 The Knowledge Base
• Contains facts and rules about some specialized
knowledge domain.
• Two types of knowledge in KB is
• Static knowledge
• Facts stored before the processing of knowledge
• Dynamic knowledge
• Knowledge gathered through online dialogues.
The Inference Process
• The inference engine accepts user input queries and responses to
questions through the I/O interface.
• Uses both static and dynamic knowledge.
• The inferring process is carried out recursively in three stages:
• Match : contents in working memory is compared with the KB.
• Select : Selecting the best rules.
• Execute: The selected best rule is executed.
• During the match stage, the contents of working
memory are compared to facts and rules contained in
the knowledge base.
• When consistent matches are found, the corresponding
rules are placed in a conflict set.
• To find an appropriate and consistent match,
substitutions (instantiations) may be required.
• Once all the matched rules have been added to the
conflict set during a given cycle, one of the rules is
selected for execution.
• The selected rule is then executed and the right-hand
side or action part of the rule is then carried out.
Forward chaining and backward chaining
• In forward chaining or data driven inference,
• it starts with facts.
• If the given condition or facts is matched with the left part of the rule , move to the
next facts and finally reached the goal state.
• A chain to forward to show that when a student is encouraged, is healthy,
and has goals , the student will succeed.

ENCOURAGED(student)→MOTIVATED(student)
MOTIVATED(student) & HEALTHY(student) →WORKHARD(student)
WORKHARD(student) & HASGOALS(student) →EXCELL(student)
EXCELL(student) →SUCCEED(student)
• In backward chaining or goal-driven inference, the right side of the rule is
initiated first, the left hand conditions become subgoals.
• These subgoals may in turn cause sub-subgoals to be established and so on until
facts are found to match the lowest subgoal conditions.
For eg,
• In MYCIN the initial goal in a conclusion is “does the patient have a certain
disease?”
• This causes subgoals to be extablished such as “are certain bacteria present in
the patient?”
• Determining if certain bacteria are present may require tests as cultures from the
patient.
• This process of setting up subgoals to confirm a goal continues untill all the
subgoals are eventually satisfied or fail.
• If satisfied, the backward chain is established thereby confirming the main goal.
Editor

• To create new rules for addition to the knowledge base or

• To delete the unwanted rules or modify the existing rules.
• An intelligent editor can greatly simplify the process of building
knowledge base.
• Ex: THEIRESIUS
Explaining How or Why
• The explanation module provides the user with an explanation of the
reasoning process when requested.
• This is done in response to a how query or a why query.
• To respond to a how query, the explanation module traces the chain of
rules fired during a consolation with the user.
• The sequence of rules that led to the conclusion is then printed for the
user in an easy to understand human language style. This permits the
user to actually see the reasoning process followed by the system in
arriving at the conclusion.
• If the user does not agree with the reasoning steps presented, they may
be changed using the editor.
• To respond to a why query, the explanation module must be able to
explain why certain information is needed by the inference engine to
complete a step in the reasoning process before it can proceed.
 The I/O Interface

• The input-output interface permits the user to

communicate with the system in a more natural way by
permitting the use of simple selection menus or the use
of a restricted language which is close to a natural
language.
• The learning module and history file are not common components of
expert systems.
• When they are provided, they are used to assist in building and
refining the knowledge base.
NONPRODUCTION SYSTEM
ARCHITECTURES
• Other, less common expert system architectures (although no less
important) are those based on nonproduction rule-representation
schemes.
• Instead of rules, these systems employ more structured
representation schemes like
• Associative or Semantic Network Architectures,
• Frame Architectures
• Decision Tree Architectures,
• Backboard System Architectures
• Analogical Reasoning Architectures
• Neural Network Architectures.
Associative or Semantic Network Architectures
• Associative network is a network made up of nodes
connected by directed arcs.
• The nodes represent objects, attributes, concepts, or other
basic entities, and the arcs, which are labeled, describe the
relationship between the two nodes they connect.
• Special network links include the IS and HASPART links
which designate an object as being a certain type of object.
• Associative network representations are especially useful in depicting
hierarchical knowledge structures, where property inheritance and
default reasoning in common.
• Objects belonging to a class of other objects may inherit many of the
characteristics of the class.
• Associative network representations are not a popular form of
representation for standard expert systems.
• One expert system based on the use of an associative network
representation is CASNET (Causal Associational Network).
• CASNET is used to diagnose and recommend treatment for
glaucoma, one of the leading causes of blindness.
The network in CASNET is divided into three planes or types of
knowledge as depicted in the next figure.
The different knowledge types are
⚫ Patient observations (tests, symptoms, other signs)

⚫ Pathophysiological states

⚫ Disease categories
 Frame Architectures
• Frames are structured sets of closely related knowledge, such as an
object or concept name, the object's main attributes and their
corresponding values, and possibly some attached procedures.
• The attributes, values and procedures are stored in specific slots.
• Property inheritance and default reasoning can be effectively
implemented.
• Individual frames are usually linked together as a network much like
the nodes in an associative network.
Example of a frame-based system is the PIP system (Present Illness
Program) developed at M.I.T. during the late 1970s and 1980s
(Szolovits and Pauker. 1978).
This system was used to diagnose patients using low cost, easily
•

obtained information, the type of information obtained by a general

practitioner during an office examination.
The medical knowledge in PIP is organized in frame structures, where
•

each frame is composed of categories of slots with names such as

⚫ Typical findings

⚫ Logical decision criteria

⚫ Complimentary relations to other frames

⚫ Differential diagnosis

⚫ Scoring
 Decision Tree Architectures
• Knowledge for expert systems is stored in the form of a decision
tree.
• For example, the identification of objects, fault finding and
diagnosis of diseases can be made through a decision tree
structure.
• Initial and intermediate nodes in the tree - object attributes,
• Final nodes or leaf nodes - the identities of objects.
• Identification of object is done by creating a path through attribute
values to a leaf node.
⚫A segment of a decision tree knowledge structure taken from
an expert system used to identify objects such as liquid
chemical waste products is illustrated below.
⚫Each node in the tree corresponds to an identifying
attribute such as molecular weight, boiling point, burn
test color, or solubility test results.
⚫Each branch emanating from a node corresponds to a
value or range of values for the attribute such as 20-37
degrees C, yellow, or insoluble in sulphuric acid.
Blackboard System Architectures
⚫Blackboard architectures refer to a special type of
knowledge-based system which uses a form of
opportunistic reasoning(Direction is specific, can
change at any time)
⚫This differs from pure forward or pure backward

chaining in production systems in that either direction

may be chosen dynamically at each stage in the
problem solution process.
⚫Blackboard systems are composed of three functional
components .
1.) Knowledge Sources
• There are a number of knowledge sources which are
separate and independent sets.
• Each knowledge source is like a specialist
• A source is limited to a specific subset of a problem
• The sources may contain knowledge in the form of
procedures, rules, or other schemes.
[Link]
• A globally accessible data base structure,called a
blackboard,
• It contains the current problem state and information
needed by the knowledge sources (input data, partial
solutions, control data, alternatives, final solutions).
• The knowledge sources make changes to the blackboard
data that incrementally lead to a solution.
• Communication and interaction between the knowledge
sources takes place solely through the blackboard.
3. Control information

• Monitors the change in the blackboard

• May be contained within the sources, on the blackboard or
possibly in a separate module
• The control information is used by the control module to
determine the focus of attention.
• This determines the next item to be processed.
• Eg. HEARSAY- Speech understanding system
 Analogical Reasoning Architectures
• Expert systems based on analogical architectures solve new
problems like humans, by finding a similar problem solution that
is known and applying the known solution to the new problem,
possibly with some modifications.
• Humans use our previous experience in solving everyday problem
• Here the system using a similar technique like humans.
• For example, if we know a method of proving that the product of
two even integers is even, we can successfully prove that the
product of two odd integers is odd through much the same proof
steps. Only a slight modification will be required when collecting
product terms in the result.
• Expert systems using analogical architectures will require a large
knowledge base having numerous problem solutions and other
previously encountered situations or episodes.
• Each such situation should be stored as a Unit in memory and be
content-indexed for rapid retrieval.
• The inference mechanism must be able to extend known situations or
solutions to fit the current problem and verify that the extended
solution is reasonable
 Neural Network Architectures
⚫ Neural networks are large networks of simple processing
elements or nodes which process information dynamically in
response to external inputs.
⚫ The nodes are simplified models of neurons. The knowledge in a

neural network is distributed throughout the network in the

form of internode connections and weighted links which form
the inputs to the nodes.
• Large network of nodes
• Each node is a processing element
• Nodes are similar to neurons
• Able to process information dynamically in response to inputs
• Weighted links are the inputs to nodes.
• The link weight may enhance or inhibit input stimuli.
• Several such weighted inputs are added together at the nodes.
• A threshold value of input T is set for each node to produce output.
• Output is produced only when a node is stimulated by the inputs.
threshold amount T, the node fires, and produces an output y.
This output may then be the input to other nodes or the final
output response from the network.
Dealing with uncertainty
• Refer 3 rd module
 ROBOTICS

INTRODUCTION

Robots are devices that are programmed to move parts, or to do work with a tool. Robotics is a
multidisciplinary engineering field dedicated to the development of autonomous devices,
including manipulators and mobile vehicles. Robotics develop man-made mechanical devices
that can move by themselves, whose motion must be modeled, planned, sensed, actuated and
controlled, and whose motion behavior can be influenced by “programming”. Robots are called
“intelligent” if they succeed in moving in safe interaction with an unstructured environment,
while autonomously achieving their specified tasks.

Characteristics of a robot

1) A robot must be produced by manufacture rather than by biology.

2) It must be able to move physical objects or be mobile itself.

3) It must be a power or force source or amplifier.

4) It must be capable of some sustained action without intervention by an external agent.

5) It must be able to modify its behavior in response to sensed properties of its environment, and
therefore must be equipped with sensors.

Definitions of 'robot' and 'robotics'

The term 'robotics' was coined by Isaac Asimov in about 1940. An example is that of the Robot
Institute of America (RIA):

“A robot is a reprogrammable and multifunctional manipulator, devised for the transport of

materials, parts, tools or specialized systems, with varied and programmed movements, with the
aim of carrying out varied tasks.

• A machine that resembles a living creature in being capable of moving independently (as
by walking or rolling on wheels) and performing complex actions (such as grasping and
moving objects)
• A robot is a machine-especially one programmable by a computer—capable of carrying
out a complex series of actions automatically.
Components of Robot

The anatomy of robot is also known as structure of robot. Robots typically include key
components such as sensors, actuators, a control system, and sometimes an end effector,
enabling them to perform tasks autonomously or semi-autonomously.

The various components of robots are:

1. Manipulator:

o A robot's manipulator is similar to the human arm, consisting of multiple joints and links.
o It provides flexibility and movement to the robot, allowing it to perform various tasks.
o Just as the human arm can bend and reach, the manipulator's joints and links enable the
robot to reach different positions and orientations.

2. End effector:

o The end effector is located at the free end of the robot's manipulator.
o It serves a function similar to the human hand and fingers, allowing the robot to interact
with its environment.
o The end effector performs tasks like gripping, picking up objects, or performing precise
actions.

3. Locomotion Device:

o While humans rely on muscles for arm and hand movement, robots use motors for
locomotion.
o These motors provide the power needed for the robot's movement, and they come in
various types, including electric, hydraulic, and pneumatic.
 o The choice of motor type depends on the robot's design and intended application.

4. Controller:

o The controller in a robot is analogous to the human brain, directing its actions.
o It consists of both hardware and software components that enable the robot to carry out
assigned tasks.
o The controller coordinates and controls the movements of the manipulator, end effector,
and other components, making the robot perform specific functions.

5. Sensors:

o Sensors are vital components of a robot, serving as its "sense organs."

o They provide data and feedback to the robot's controller, allowing it to perceive its
environment.
o Sensors measure various quantities such as position, velocity, force, torque,
proximity, temperature, and more.
o This sensory input enables the robot to make informed decisions and adapt to changing
conditions while executing tasks.

Need of Robot and its Application

Industrial Applications

Industrial robots are used to assemble the vehicle parts. As the assembly of the machine parts is
a repetitive task to be performed, the robots are conveniently used instead of using mankind
(which is more costly and less précised compared to robots.)
Auto Industry:

The auto industry is the largest users of robots, which automate the production of various
components and then help, assemble them on the finished vehicle. Car production is the primary
example of the employment of large and complex robots for producing products. Robots are used
in that process for the painting, welding and assembly of the cars.

Material Transfer, Machine Loading And Unloading

There are many robot applications in which the robot is required to move a work part or other
material from one location to another. The most basic of these applications is where the robot
picks the part up from one position and transfers it to another position. In other applications, the
robot is used to load and/or unload a production machine of some type. The machine loading and
unloading applications are material handling operations in which the robot is used to service a
production machine by transferring parts to and/or from the machine.

Robotic arm

The most developed robot in practical use today is the robotic arm and it is seen in applications
throughout the world. We use robotic arms to carry out dangerous work such as when dealing
with hazardous materials. We use robotic arms to carry out work in outer space where man
cannot survive and we use robotic arms to do work in the medical field such as conducting
experiments without exposing the research.

Medical Applications

Medical robotics is a growing field and regulatory approval has been granted for the use of
robots in minimally invasive procedures. Robots are being used in performing highly delicate,
accurate surgery, or to allow a surgeon who is located remotely from their patient to perform a
procedure using a robot controlled remotely. More recently, robots can be used autonomously in
surgery.
 Connections between robotics and some related subjects
From a scientific or philosophical point of view the most interesting area of the AI -robotics
interaction lies in the possibilities for making robots which are more like those of science fiction,
i.e. mobile intelligent autonomous agents. In terms of the practical robotics of today and the
immediate future, however, the relevance of AI is mainly that it provides, or promises to provide,
a number of useful techniques for enhancing performance. The general theme of these is making
robots more intelligent, in a down to earth sense, by incorporating adaptability, sensing, problem
solving and so on. There is also an opposite connection: robots for AI instead of AI for robotics;
robots can be useful tools for developing AI techniques.
The most obvious example of robots for households using AI is Amazon’s upcoming Astro bot.

Flexible Manufacturing System (FMS)

A flexible manufacturing system (FMS) is a coordinated set of machine tools and their loading
devices (often robots), which can produce a range of items. It implies that there is a
communications network associated with the machines so that they can be programmed, while
the system is running, with the settings for each item to be made.

The reason the FMS is called flexible is that it is capable of processing a variety of different part
styles simultaneously at the various workstations, and the mix of part styles and quantities of
production can be adjusted in response to changing demand patterns.

Other names for flexible manufacturing systems include: computer integrated manufacturing
systern (CIMS), computer managed parts manufacturing (CMPM)

Need of FMS due to its benefits

Increased machine utilization.

Fewer machines required because of higher machine utilization.
Greater responsiveness to change.
Reduced inventory requirements
Lower manufacturing lead times.
Reduced direct labor
What is CAM?

CAM is the acronym for Computer Aided Manufacturing. In simple terms - using the computers
to carry out various manufacturing related activities is called as Computer Aided Manufacturing.
The use of the computers can be to plan the manufacturing of the product, to carry out actual
manufacturing of the product by linking the computers to machines and programming the
computers etc.

Functions Performed by CAM

The functions performed by the computer systems in CAM applications fall under two broad
categories, which have been described below:

1. Computer monitoring and control:

In these applications the computer is connected directly to the manufacturing process for the
purpose of monitoring or controlling the manufacturing process.

2. Manufacturing Support Applications:

In these applications the computer systems are used to assist in various productions related
activities like production planning, scheduling, making forecasts, giving manufacturing
instructions and other relevant information that can help manage company’s manufacturing
resources more effectively. There is no direct interface between the computers and the
manufacturing process in this case.

Advantages of CAM

➢ Manufacturing requires minimum supervision and can be accomplished

during unsocial work hours.
➢ Manufacture is less labour intensive and saves labour cost.
➢ Machines are accurate, and manufacturing can be repeated consistently
with large batches.
➢ Error occurrence is negligible, and machines can run continuously.
➢ Prototype models can be prepared very speedily for elaborated inspection
before finalizing designs for manufacture.
➢ Virtual machining can be used to evaluate machining routines and
outcomes on the screen.

Disadvantages of CAM

➢ It requires high initial investment and start-up cost.

➢ Machine maintenance is also costly.
➢ May result in loss of a workforce with high-level manual skill.
➢ To assure proper tooling and set up procedures it needs highly trained
operatives and technicians

AUTOMATION & ROBOTICS

Automation or automatic control, is the use of various control systems for operating equipment
such as machinery, processes in factories, boilers and heat treating ovens, switching in telephone
networks, steering and stabilization of ships, aircraft and other applications with minimal or
reduced human intervention. Some processes have been completely automated.

The biggest benefit of automation is that it saves labor, however, it is also used to save energy
and materials and to improve quality, accuracy and precision.
Automation has been achieved by various means including mechanical, hydraulic, pneumatic,
electrical, and electronic and computers, usually in combination. Complicated systems, such as
modern factories, airplanes and ships typically use all these combined techniques.

The main advantages of automation are:

•Increased throughput or productivity.

•Improved quality or increased predictability of quality.

•Improved robustness (consistency), of processes or product.

•Increased consistency of output.

•Reduced direct human labor costs and expenses.

The main disadvantages of automation are:

•Causing unemployment and poverty by replacing human labor.

•Unpredictable/excessive development costs: The research and development cost of automating a

process may exceed the cost saved by the automation itself.

•High initial cost: The automation of a new product or plant typically requires a very large initial
investment