Natural Language Processing (Part 2)

Database Access

The first major success of natural language processing !!!

There was a hope that databases could be controlled by natural languages instead of complicated data retrieval commands, this was a major problem in the early 1970s since the staff in charge of data retrieval could not keep up with demand of users for data.

LUNAR system was the first such interface built by William Woods in 1973 for NASA Manned Spacecraft Center, this system was able to correctly answer 78% of the questions such as: “What is the average modal plagioclase concentration for lunar samples that contain rubidium?”

• Other examples of data retrieval systems would include:
• CHAT system
• developed by Fernando Pereira in 1983
• similar level of complexity to LUNAR system
• worked on geographical databases
• was restricted
• question wording was very important
• TEAM system
• could handle a wider set of problems than CHAT
• was still restricted and unable to handle all types of input

Text Interpretation

• In early 1980s, most online information was stored in databases and spreadsheets
• Now, most of online information is text: email, news, journals, articles, books, encyclopedias, reports, essays, etc
• there is a need to sort this information to reduce it to some comprehendible amount
• Text interpretation has become a major field in natural language processing
• becoming more and more important with expansion of the Internet
• consists of:
• information retrieval
• text categorization
• data extraction

Information Retrieval

• Information Retrieval (IR) is also know as Information Extraction (IE)
• Information retrieval systems analyze unrestricted text in order to extract specific types of information
• IR systems do not attempt to understand all of the text in all of the documents, but they do analyze those portions of each document that contain relevant information
• relevance is determined by pre-defined domain guidelines which must specify, as accurately as possible, exactly what types of information the system is expected to find
• query would be a good example of such a pre-defined domain
• documents that contain relevant information are retrieved while other are ignored

Example: Commercial System (HIGHLIGHT):

It helps users find relevant information in large volumes of text and present it in a structured fashion.

It can extract information from newswire reports for a specific topic area - such as global banking, or the oil industry - as well as current and historical financial and other data.

Although its accuracy will never match the decision-making skills of a trained human expert, HIGHLIGHT can process large amounts of text very quickly, allowing users to discover more information that even the most trained professional would have time to look for

see Demo at: http://www.cgi.cam.sri.com/highlight/

It could be classified under “Extracting Data From Text”

Text Categorization

It is often desirable to sort all text into several categories

There are number of companies that provide their subscribers access to all news on a particular industry, company or geographic area

• traditionally, human experts were used to assign the categories
• in the last few years, NLP systems have proven very accurate (correctly categorizing over 90% of the news stories)

Context in which text appears is very important since the same word could be categorized completely differently depending on the context

• Example: in a dictionary, the primary definition of the word “crude” is vulgar, but in a large sample of the Wall Street Journal, “crude” refers to oil 100% of the time.

The task of data extraction is take on-line text and derive from it some assertions that can be put into a structured database

Examples of data extraction systems include:

• SCISOR system

SCISOR is able to take stock information text (such as the type released by Dow Jones News Service) and extract important stock information pertaining to:

• events that took place
• companies involved
• starting share prices
• quantity of shares that changed hands
• effect on stock prices

Natural Language Processing (Part 1)

Natural Language Processing (NLP) can be divided into two categories;

• processing written text
• processing spoken language

Steps in NLP

Roughly we can break the process down into the following five components;

• Morphological Analysis: Individual words are analyzed into their components and non-word tokens, such as punctuations, are separated. Phonetics is considered for spoken language at this phase.
• Syntactic Analysis: Linear sequences of words are transformed into structures that show how the words relate to each other. Some word sequences may be rejected if they violate the language’s rules for how words may be combined.
• Semantic Analysis: A mapping is made between the syntactic structures and objects in the task domain. Structures for which no such mapping is possible may be rejected.
• Discourse Integration: The meaning of an individual sentence may depend on the sentences that precede it. In this phase, the meaning of a sentence is analyzed depending on the information that precede it, e.g, in “John wanted it.”, “it” depends on the prior discourse context. Such as, “He always had.” would require information about previous sentences.
• Pragmatic Analysis: The structure representing what was said is reinterpreted to determine what was actually meant. For example, the sentence “Do you know the rout?”.

Practical Applications

We are going to look at some practical applications of natural language processing;

• Machine Translation
• Voice Interface for Humanoids
• Database Access
• Text Interpretation
• information retrieval
• text categorization
• extracting data from text

Machine Translation

• Correct translation requires an in-depth understanding of both natural languages since structure of expressions varies in every natural language
• Yehoshua Bar-Hillel declared in 60’s that Machine Translation was impossible (Bar-Hillel Paradox):
• analysis by humans of messages relies to some extent on the information which is not present in the words that make up the message
• “The pen is in the box”
• [i.e. the writing instrument is in the container]
• “The box is in the pen”
• [i.e. the container is in the playpen or the pigpen]

• Examples of poor machine translations would include:

• "the spirit is strong, but the body is weak" was translated literally as "the vodka is strong but the meat is rotten”
• "Out of sight, out of mind” was translated as "Invisible, insane”
• "hydraulic ram” was translated as "male water sheep”
• These do not imply that machine translation is a waste of time
• some mistakes are inevitable regardless of the quality and sophistication of the system
• one has to realize that human translators also make mistakes

There is a substantial start-up cost to any machine translation effort to achieve broad coverage, translation systems should have lexicons of 20,000 to 100,000 words and grammars of 100 to 10,000 rules (depending on the choice of formalism)

Privacy Policy

Privacy Policy for www.artificialintelligenceworld.blogspot.com/

If you require any more information or have any questions about our privacy policy, please feel free to contact us by email at careerpakistan@gmail.com.

At www.artificialintelligenceworld.blogspot.com, the privacy of our visitors is of extreme importance to us. This privacy policy document outlines the types of personal information is received and collected by www.artificialintelligenceworld.blogspot.com and how it is used.

Log Files
Like many other Web sites, www.artificialintelligenceworld.blogspot.com makes use of log files. The information inside the log files includes internet protocol ( IP ) addresses, type of browser, Internet Service Provider ( ISP ), date/time stamp, referring/exit pages, and number of clicks to analyze trends, administer the site, track user’s movement around the site, and gather demographic information. IP addresses, and other such information are not linked to any information that is personally identifiable.

Cookies and Web Beacons
www.artificialintelligenceworld.blogspot.com does use cookies to store information about visitors preferences, record user-specific information on which pages the user access or visit, customize Web page content based on visitors’ browser type or other information that the visitor sends.

Some of our advertising partners may use cookies and web beacons on our site. Our advertising partners include Google Adsense,etc.

These third-party ad servers or ad networks use technology to the advertisements and links that appear on www.artificialintelligenceworld.blogspot.com send directly to your browsers. They automatically receive your IP address when this occurs. Other technologies ( such as cookies, JavaScript, or Web Beacons ) may also be used by the third-party ad networks to measure the effectiveness of their advertisements and / or to personalize the advertising content that you see.

www.artificialintelligenceworld.blogspot.com has no access to or control over these cookies that are used by third-party advertisers.

You should consult the respective privacy policies of these third-party ad servers for more detailed information on their practices as well as for instructions about how to opt-out of certain practices. www.artificialintelligenceworld.blogspot.com's privacy policy does not apply to, and we cannot control the activities of, such other advertisers or web sites.

If you wish to disable cookies, you may do so through your individual browser options. More detailed information about cookie management with specific web browsers can be found at the browsers' respective websites.

Introduction to Prolog (Part 2)

Examples of Facts

• female(alison).
• “alison is a female”
• has_feathers(sparrow).
• “sparrow has feathers”
• father(“John”,”Sam”).
• ”John is the father to Sam”
• mother(”Jeanette”,”Mary”).
• “Jeanette is the mother to Mary”
• bird(type(sparrow), name(toto))).
• “toto is a bird that is of sparrow class”

Examples of Rules

• You should read the prolog operator “:-” as “if ”, “;” as an “or”, while “,” as meaning “and”.
• Rules consist of a head and a body. For example the rule “a(X) :- b(X), c(X).” has head “a(X)” and body “b(X), c(X)”.
• All arguments beginning with a capital letter (such as X and Y) are variables. Variables don't have to have values). Any constant should NOT begin with a capital letter else it will be treated as a variable.
• sister(X,Y) :- father(Z,X),father(Z,Y).
• “X and Y are sisters if Z is father to X and father to Y”

Example of a Prolog Program

PREDICATES

son(STRING, STRING)

CLAUSES

son("John", "Dan").

son("Allan","Dan").

Goal son("John", "Dan").

Example 2

PREDICATES

son(STRING,STRING)

sister(STRING,STRING)

brother(STRING,STRING)

married(STRING,STRING)

sister_in_law(STRING,STRING)

CLAUSES

son("John", "Dan").

sister("Mary","Suzan").

brother("Harold", "Larry").

married("John", "Mary").

married("Larry", "Sue").

married("Harold", "Emma").

CLAUSES

sister_in_law(A, B):-married(A, C), sister(C, B).

sister_in_law(A, B):-brother(A, C), married(C, B).

GOAL

sister_in_law("John", Z).

Example 3

domains

brand, color = symbol

age, price = integer

milage = real

predicates

car(brand, milage, age, color, price)

clauses

car(chrysler, 130000, 3, red, 12000).

car(ford, 90000, 4, gray, 25000).

car(datsun, 8000, 1, red, 30000).

goal

car(renault, 13, 3.5, red, 12000).

/* car(ford, 9000, gray, 4, 25000).

car(Make, Odometer, Years_on_road, Body, 25000).

car(Make, Odometer, Years_on_road, Body, Cost) and Cost < style=""> */

Introduction to Prolog (Part 1)

History of Prolog

• Prolog was developed at the University of Marseilles, France by Alain Colmerauer in the early 1970s as a convenient tool for PROgramming in LOGic.

• In 1983 Japan chose Prolog as the main language for 5th generation computers.

• Turbo Prolog was the first implementation of Prolog for IBM PC that came out in 1986.

• Visual Prolog is developed by PDC in Denmark.

What Can Prolog be Used For?

• Expert Systems.
• Artificial Intelligent Systems.
• Translate languages, either natural human languages or from one programming language to another.
• Construct Natural Language interfaces to existing software.
• Control and monitoring of industrial processes.
• Theorem proving software in which deductive reasoning capabilities are used.
• Development of Relational Databases.
• Produce prototypes for virtually any application program.

In what Areas Prolog is Distinctively Better?

• Prolog is a Descriptive Language.

• Prolog Uses Facts and Rules.

• Prolog can make Deductions.

• Pattern Matching ability.

• Execution of Prolog Programs is Controlled automatically.

• Prolog is very User-friendly and has a short and simple syntax.

• Efficiency of Application Programs is almost as good as for C++ programs.

Glossary of Terms

• Atom: A relation possibly involving objects or variables.
• Domain: Specifies the types of values the objects may take in relation.
• Clause: A fact or rule for a particular predicate, followed by a period.
• Fact: . Facts declare things that are always true. It is a relation between objects. In the fact;
• likes(john, mary)
• likes is the name of the relation and john and mary are objects.

• Rule: Rules declare things that are true depending on some conditions. It is a relationship between a fact and a list of sub-goals which must be satisfied for that fact to be true.
• Predicate: Every Prolog fact or rule belongs to some predicate, which specifies the name of the relation involved and the types of objects involved in the relation.
• Backtracking: The mechanism built into Prolog whereby, when evaluation of a given sub-goal is complete, Prolog returns to the previous sub-goal and tries to satisfy it in a different way.

What is an (Intelligent) Agent?

• Anything that can be viewed as perceiving its environment through sensors and acting upon that environment through its effectors to maximize progress towards its goals.

• PAGE (Percepts, Actions, Goals, Environment)

• Task-specific & specialized: well-defined goals and environment

• The notion of an agent is meant to be a tool for analyzing systems, not an absolute characterization that divides the world into agents and non-agents. Much like, e.g., object-oriented vs. imperative program design approaches.

Intelligent Agents and AI

• Human mind as network of thousands or millions of agents all working in parallel. To produce real artificial intelligence, this school holds, we should build computer systems that also contain many agents and systems for arbitrating among the agents' competing results.
• Distributed decision-making
  and control
• Challenges:
• Action selection: What next action
  to choose
• Conflict resolution

Agent Types

• We can split agent research into two main strands:

• Distributed Artificial Intelligence (DAI) –
  Multi-Agent Systems (MAS) (1980 – 1990)
• Much broader notion of "agent" (1990’s – present)
• interface, reactive, mobile, information

A Windshield Wiper Agent

How do we design a agent that can wipe the windshields when needed?

• Goals?
• Percepts ?
• Sensors?
• Effectors ?
• Actions ?
• Environment ?

Interacting Agents

Collision Avoidance Agent (CAA)

• Goals: Avoid running into obstacles
• Percepts: Obstacle distance, velocity, trajectory
• Sensors: Vision, proximity sensing
• Effectors: Steering Wheel, Accelerator, Brakes, Horn, Headlights
• Actions: Steer, speed up, brake, blow horn, signal (headlights)
• Environment: Freeway

Lane Keeping Agent (LKA)

• Goals: Stay in current lane

• Percepts: Lane center, lane boundaries

• Sensors: Vision

• Effectors: Steering Wheel, Accelerator, Brakes

• Actions: Steer, speed up, brake

• Environment: Freeway

Conflict Resolution by Action Selection Agents

• Override: CAA overrides LKA

• Arbitrate: if Obstacle is Close then CAA
else LKA

• Compromise: Choose action that satisfies both
agents

• Any combination of the above

• Challenges: Doing the right thing

The Right Thing = The Rational Action

• Rational Action: The action that maximizes the expected value of the performance measure given the percept sequence to date

• Rational = Best ?
• Rational = Optimal ?
• Rational = Omniscience ?
• Rational = Clairvoyant ?
• Rational = Successful ?

How is an Agent different from other software?

• Agents are autonomous, that is they act on behalf of the user

• Agents contain some level of intelligence, from fixed rules to learning engines that allow them to adapt to changes in the environment

• Agents don't only act reactively, but sometimes also proactively

• Agents have social ability, that is they communicate with the user, the system, and other agents as required

• Agents may also cooperate with other agents to carry out more complex tasks than they themselves can handle

• Agents may migrate from one system to another to access remote resources or even to meet other agents

Summary

• Intelligent Agents:
• Anything that can be viewed as perceiving its environment through sensors and acting upon that environment through its effectors to maximize progress towards its goals.
• PAGE (Percepts, Actions, Goals, Environment)
• Described as a Perception (sequence) to Action Mapping: f : P* ® A
• Using look-up-table, closed form, etc.

• Agent Types: Reflex, state-based, goal-based, utility-based

• Rational Action: The action that maximizes the expected value of the performance measure given the percept sequence to date

What is Artificial Intelligence? (Part 2)

What would a computer need to pass the Turing test?

• Natural language processing: to communicate with examiner.
• Knowledge representation: to store and retrieve information provided before or during interrogation.
• Automated reasoning: to use the stored information to answer questions and to draw new conclusions.
• Machine learning: to adapt to new circumstances and to detect and extrapolate patterns.
• Vision (for Total Turing test): to recognize the actions and various objects presented by the examiner.
• Motor control (total test): to act upon objects as requested.
• Other senses (total test): such as audition, smell, touch, etc.

How to achieve AI?

How is AI research done?

AI research has both theoretical and experimental sides. The experimental side has both basic and applied aspects.

There are two main lines of research:

• One is biological, based on the idea that since humans are intelligent, AI should study humans and imitate their psychology or physiology.
• The other is phenomenal, based on studying and formalizing common sense facts about the world and the problems that the world presents to the achievement of goals.

Branches of AI

• Logical AI
• Search
• Natural language processing
• pattern recognition
• Knowledge representation
• Inference From some facts, others can be inferred.
• Automated reasoning
• Learning from experience
• Planning To generate a strategy for achieving some goal
• Genetic programming
• Emotions???

AI State of the art

Have the following been achieved by AI?

• World-class chess playing
• Playing table tennis
• Cross-country driving
• Solving mathematical problems
• Discover and prove mathematical theories
• Engage in a meaningful conversation
• Understand spoken language
• Observe and understand human emotions
• Express emotions

Applications of AI

• Robotics
• Computer Vision
• Voice Recognition
• Natural Language Processing
• Expert Systems

Core AI Technologies

• Knowledge Representation
• Search Algorithms
• Inference
• Heuristics
• Learning
• Neural Networks
• Biomechanics

AI Programming Languages

PROLOG

PROgramming in LOGic

C++

XML

Extensible Markup Language

LISP

List Processing

What is Artificial Intelligence? (Part 1)

• Branch of computer science that deals with introducing human intelligence into machines.
• Branch of science that deals with computer programs or devices that have the ability to learn from their environment and then act rationally to change the environment.

Why Study AI?

AI enables us to build devices and applications that help us in our daily personal professional activities. Like robots, intelligent appliances, autonomous ground vehicles etc.


What tasks require AI?

AI is the science and engineering of making intelligent machines which can perform tasks that require intelligence when performed by humans …”

Tasks that require AI:

• Solving a differential equation
• Brain surgery
• Inventing stuff
• Playing Jeopardy
• Playing Wheel of Fortune
• What about walking?
• What about grabbing stuff?
• What about pulling your hand away from fire?
• What about watching TV?
• What about day dreaming?

Acting Humanly: The Full Turing Test:

• Computer needs to posses: Natural language processing, Knowledge representation, Automated reasoning, and Machine learning
• Problem: 1) Turing test is not reproducible, constructive, and amenable to mathematic analysis. 2) What about physical interaction with interrogator and environment?
• Total Turing Test: Requires physical interaction and needs perception and actuation.