Transcript ppt - UTRGV Faculty Web

Artificial intelligence and
language
Emmett Tomai
University of Texas – Pan American
What is Artificial Intelligence?

Generally, the study of computation as a model
of human-like thought
◦ The human mind is our best exemplar of an artifact
capable of intelligent thought








Pattern recognition
Logical reasoning
Problem solving
Planning
Learning
Language
Social interaction
Creativity
Goals and questions

AI is a broad field, with many goals, approaches,
assumptions and unresolved questions
◦ For some, the goal is to create an artificial mind
◦ For others, to discover a formal model of thought
◦ Others, to build machines (programs) that perform
difficult human-like tasks
Is computation sufficient to model human
mental processes?
 How do those processes differ from existing
algorithms?

A bit of history
AI was established as a field in 1956 at a
research conference
 Early work was largely symbolic and deductive

◦ Concepts represented as symbols in a formal logical
system
◦ Reasoning carried out through step-by-step
deduction, attempting to mirror human processes
Logical problem solving

Many logical problems reduce to search, trying
to find an optimal path among many possibilities
◦ Theorem proving
◦ Constraint satisfaction (flight planning, logistics
problems)
◦ Checkers, chess, go, etc.

However, complete logical search has serious
problems with combinatoric explosion
The Traveling Salesman

Consider a salesman who wants to visit a
bunch of small towns
◦ He has a list of distances between pairs of towns
◦ How should he figure out what order to visit them
in?

Can be solved by straightforward search
◦ How long do you think it would take you to figure out the best
path for 25 towns?
The Traveling Salesman

Consider a salesman who wants to visit a
bunch of small towns
◦ He has a list of distances between pairs of towns
◦ How should he figure out what order to visit them
in?

Finding the answer by straightforward search has
complexity O(n!)
◦ So it would take a 2GHz computer around a billion years
◦ Some more clever solutions are O(2n)
So how do people do it?

Unlike complete logical formalisms, people solve
problems quickly and easily using approximate
methods
◦ We don’t prove the best solution, we come up with
reasonable solutions (and quickly)
◦ We use poorly understood mechanisms like intuition,
experience and creative thinking

Modern AI is largely concerned with numerous
approaches to bridge that gap
Successes

Mechanical self-diagnosis
◦ Used in autonomous spacecraft

Expert systems
◦ Aide humans in identifying and solving known
problems

Deep blue, etc.
◦ Far better than the average human chess player, can
even beat the best humans

Google
◦ Uses AI language processing techniques for search
Learn more about AI

The Association for the Advancement of
Artificial Intelligence (AAAI)
◦ The biggest, general society for AI research

AI Topics at AAAI
◦ Great resource
◦ Seminal references for all major sub-fields of AI
◦ http://www.aaai.org/AITopics/pmwiki/pmwiki.php/AIT
opics/HomePage
◦ (click on “Browse Topics”)
Language understanding and AI

Why would you want a computer to be
competent at natural language (e.g. English,
Spanish, etc.)
◦
◦
◦
◦
◦
◦
◦

Machine translation
Intelligent tutoring systems
Information retrieval (search engines)
Question answering systems
Information management (emails, blogs, news, etc.)
Speech recognition
Storytelling tools (generation, editing, evaluation, etc.)
Bottom line: people use language to do a lot of
things
Language understanding and AI

People have been studying language for a long time
◦ Literature, philosophy, linguistics
◦ Anthropology, psychology

This has resulted in common levels of analysis
◦
◦
◦
◦
◦
Morphology: how words are constructed
Lexicon: the words that are available in a language
Syntax: structural relationships between words
Semantics: the meaning or a word of combination of words
Discourse: how meaning evolves over time in a monologue or
dialogue
◦ Pragmatics: the purpose behind an utterance, how language is
used
◦ World knowledge: facts about the world, common sense
Language understanding and AI
Early work (1950s) in machine translation
assumed that translation was a matter of
lexicon (changing the words) and syntax
(changing the order)
 That proved far too simplistic:

◦ hydraulic ram
 = water sheep
◦ out of sight, out of mind
 = blind, crazy
◦ The spirit is willing but the flesh is weak.
 = The vodka is good but the meat is rotten.
Language understanding and AI


Chomsky (1957) provided a robust linguistic theory that
was specific enough to inform a computational model
Montague (1970) presented a formal, logical grammar
casting syntax and semantics as a precise mathematical
system
male( he )
studies( he, linguistics )
…
Language understanding and AI

Numerous problems remain, starting with ambiguity
◦ There is often more than one syntactically correct parse:
◦ “Time flies like an arrow.”
 What’s the verb?
◦ “I saw the Grand Canyon flying to New York.”
 Who or what was flying?
◦ “I saw the man on the hill with the telescope.”
 Who was on the hill? Where was the telescope?


This creates the same problem of combinatorial
explosion as the traveling salesman problem
Worse, real language is often syntactically incorrect
Language understanding and AI

Syntax alone isn’t enough to understand
language, you need semantics, pragmatics and
world knowledge
◦ How did you know the Grand Canyon wasn’t the one
flying?
◦ Unfortunately, each of those bring in their own
ambiguities and difficulties
Language understanding and AI

Lexical ambiguity
◦ I walked to the bank ...
 of the river.
 to get money.
◦ The bug in the room ...
 was planted by spies.
 flew out the window.
◦ I work for John Hancock ...
 and he is a good boss.
 which is a good company.
Language understanding and AI

Co-reference resolution
◦
◦
◦
◦
◦
◦
President John F. Kennedy was assassinated.
The president was shot yesterday.
Relatives said that John was a good father.
JFK was the youngest president in history.
His family will bury him tomorrow.
Friends of the Massachusetts native will hold a
candlelight service in Mr. Kennedy’s home town.
Language understanding and AI

Pragmatics
◦ Mostly studied in conversational dialogue, but applies
to any linguistic communication
◦ Rules of Conversation
 Can you tell me what time it is?
 4:30.
 Could I please have the salt?
 <passes the salt>
 What platform does the 5:00 train leave from?
 It already left.
◦ Speech Acts
 I bet you $50 that the Jazz will win.
 You’re on.
 You’re fired!
Language understanding and AI

World Knowledge
◦ John went to the diner. He ordered a steak. He left a
tip and went home.
◦ John wanted to commit suicide. He got a rope.
Language understanding and AI
A very hard problem, with a big potential payoff
 All the levels of analysis (lexical, syntactic, etc.)
must work together in understanding

◦ But this leads to seemingly insurmountable
complexity

Many approaches being pursued
◦ The same as for AI in general, trying to bridge the gap
between explosive complexity in the formal system
and the ease with which people do it every day
Knowledge is power

Problem: people know a lot of things
◦ Common sense reasoning (where the gap is huge)
seems to involve using that knowledge
◦ Understanding the pragmatics of language requires
being able to reason about the situation surrounding
what is being said

Solutions?
◦ Build huge knowledge bases filled with common sense
information that people might have
Experience is the best teacher

Problem: part of what people know is a huge
number of experiences
◦ We remember prior events and apply them to the
current situation
◦ We can even adapt similar but not identical situations
and ideas to understand new situations and ideas

Solutions?
◦ Case-based reasoning, storing logical representations
of prior events
◦ Analogical reasoning, being reminded of similar things
and appreciating how they compare and contrast
Learning is fundamental

Problem: people learn as they go
◦ We continue to adapt and expand our knowledge and
capabilities
◦ It’s not clear what we start with and what we learn
◦ We don’t do the same stupid thing twice

Solutions?
◦ Perhaps this is the answer to the previous two
problems
◦ Many researchers think that a legitimate AI must
involve learning, otherwise you’re just tweaking it to
work on specific problems
Reactive approaches

Problem: something as simple as an ant or a
fruit fly is capable of amazing navigation
◦ Our models of intelligence require massive computing
power to simulate a fruit fly
◦ Modern robots have trouble crossing the room
without crashing into things

Solutions?
◦ Reactive architectures concentrate on doing simple
operations really fast and really well
 Put enough of those together and maybe we’ll get intelligence
◦ It may not scale up to writing poetry, but at least it
can avoid running into walls
The statistical revolution

Problem: formal, logical systems are fragile and
struggle with environments far less complex
than reality
◦ Can these really scale up to working in the real world
with ambiguity, vagueness and incomplete knowledge?
◦ With something as “inherent” as language, are we
really reasoning about each sentence or are we
relying on more subconscious, fast-acting
mechanisms?

Solutions?
◦ Most NL work in the last two decades has focused on
statistical methods
The statistical revolution

Statistical methods use machine learning
algorithms to fit a model to the data
◦ Given 1000s of training examples, a statistical parser
can achieve robust, high-performance results on
similar text
 Effective on parsing, named entity extraction, noun-noun coreference resolution, semantic role labeling
◦ However, since it relies entirely on consistent
patterns, a parser trained on one type of text (say the
Wall Street Journal) performs poorly on another (say
a textbook, novel or blog)
 Worse, this approach hasn’t been shown to scale very far
beyond simple syntactic features
Learning semantics

Context constrains ambiguity
◦ Filters out possible meanings that don’t make sense

TRIPS (Allen et al)
◦ The Rochester Interactive Planning System
◦ Collaborative planning between human and AI
◦ Shared goal provides context
 Can reason about what the person might mean
 Enables impressive speech understanding

Learning requires constrained examples
◦ Utterances…
◦ …combined with an appropriate situation (context)
Learning semantics for…?

Virtual spaces provide flexible constraint
◦ There are only so many moves in checkers
◦ Only so many things you could try to do

Constraint enables planning, problem-solving
◦ AI systems can reason about moves

Can that constraint enable learning language?
Learning semantics in games

You are playing checkers
◦ You already know how to play
◦ Someone is giving you advice in Chinese
◦ Could you learn some Chinese that way?
Learning semantics in games

You are playing checkers
◦ You already know how to play
◦ Someone is giving you advice in Chinese
◦ Could you learn some Chinese that way?

Assume that they know what they’re talking
about
◦ Hypothesize mappings
 Words to items, actions in the game
 Phrases to reasonable moves they could be suggesting
◦ Test hypotheses as the game goes on
Learning semantics in games

You are playing mahjongg
◦ You don’t know how to play
◦ Someone is giving you advice in Chinese
◦ Could you learn some Chinese, and mahjongg at the
same time?
Learning semantics in games

You are playing mahjongg
◦ You don’t know how to play
◦ Someone is giving you advice in Chinese
◦ Could you learn some Chinese, and mahjongg at the
same time?

Assume that they know what they’re talking
about
◦ Hypothesize mappings for words, phrases
◦ Test hypotheses as the game goes on
 Much harder since you can’t filter out bad/nonsensical moves
 Have to play the game out to see what moves were good
 Requires a lot of patience and methodical testing
Learning semantics in games

Interactive learning would be faster
◦ Particularly with positive/negative feedback

Knowledge helps
◦ Syntax, lexical categories, other widely available
knowledge
◦ The more you know about games in general, the
fewer options you’ll have to try

Bootstrapping
◦ Start with very simple goals to start language learning
◦ Build up to more complex goals
Planning in real-time strategy games

Lots of recent work on planning in RTS games
◦
◦
◦
◦
Not as neat and clean as classic games (chess, etc)
Require real-time decisions, uncertainty, heuristics
Lots of player and strategy analysis available
Still a limited environment compared to reality
Learning semantics in a RTS game

Given specific goals and varied instructions to
reach those goals, can an AI learn English
semantics while learning to play an RTS game?

How can you tell if it does?
◦ Evaluating language learning is hard and subjective
◦ Evaluating performance is easy
Do the instructions help the AI learn to play
better, faster?
 Once some language has been learned, can it go
on to learn another game goal faster?

Project details
Spring – Summer 2011
 StarCraft: Brood War

◦ AI player using BroodWar API (BWAPI)




C++ dll
Event-driven programming
Expose game info, unit commands
Most likely bridge to a higher-level language (python, lisp, java)
◦ Research existing dynamic planning agents
◦ Implement a planning agent in-game
◦ Test ability to plan and reach simple in-game goals

Funded by a UTPA Faculty Research Council
grant for the summer RA position
Additional projects

Adaptive narrative in shared, virtual worlds
◦ Many dynamic virtual world simulations
 Physics, economics, politics, etc.
◦ Narrative presentation is largely static
 Cut-scenes, quest text, dialogue trees, etc.
◦ How can we use AI techniques to create and present
narrative that adapts to a dynamic, interactive
environment?

Current project
◦ Building up shared world infrastructure
 Shared interactions in a persistent, physically-based world
◦ Using publically available tools, libraries, engines, etc.
Additional projects

Simulating dramatic social interaction
◦ Physical interactions have been well simulated
 Physics-based movement and collision
 Combat abstractions
◦ Social interactions are less well explored
 Formal diplomacy (lacks emotions, personal relationships)
 Bargaining (also abstract)
 Relationship models (Fable, The Sims)
 Emergent story, independent of narrative/dramatic arcs
 Curiosity-driven, lacking communicative goals