engaging experience

[AI@50] Selected Submitted Papers: Future Possibilities for AI

[AI@50]
Filene Auditorium, Moore Hall
Dartmouth College
Hanover, NH

Conference notes by Meg Houston Maker

Eric Steinhart
Survival as a Digital Ghost

A "digital ghost" is an instantiation of you. [MHM: A machine doppelganger.] The name comes from William Gibson. It's a personalized artificial intelligence, and it could maybe pass a personalized Turing test, convincing your friends and loved ones the machine was you. So it would have to know your history, beliefs, etc.

People now have massive amounts of personal information; there is a digital vapor trail that you leave behind you as you go through the world: videos, images, bookmarks, etc. You go through life generating data, and much of it is not saved or archived. But if you were to start archiving it, you'd get a big temporal database. A little work is being done on this, there's a SIG in the ACM for it, and MicroSoft has its "my life's bits" project.

Think of this collection as a digital diary. Of course you would have to tag all that information -- that's my wife, that's my dog. Tagging and indexing is not there yet -- they're too cumbersome. So instead, you might want a personalized AI that could look at the diary and interpret the diary data as if it were you. The AI tool would have to be a model of your psychology that would interpret it the way YOU would interpret it. Some recomendation engines (Amazon.com) are pretty promising and pretty good at capturing preferences. Mate selection in online data sites could certainly use this technology. E.g. the website Hot or Not, where you rate pictures of people; these could be sent to dating sites.

So, how do you get this? One recommendation is a questionnaire with 20,000 questions you could answer to construct a profile. No way! Too onerous. But maybe we could analyze your telephone conversations, GPS data about where you are at any given time. Or you could do simple query-response about where you were or why you did a certain action. Descriptive and explanatory, in other words. Brain implants are another possibility, or non-invasive brain scanning approaches, to create a highly-personalized analog of your own architecture.

Digital ghosts should also be a simulation of your body. These could be pretty much generic models that could then be tuned with personal history and prefs. Faces and voices are finely tuned personal features, and are interesting to others, so it would be essential to incorporate these. It would have speech synthesizers that could replicate your voice. Your medical data could be incorporated. We can then build a model that looks like you in addition to having your history.

How might we interact wtih something like this? Maybe initially it would be chat-based, but in a more advanced state it would be an animated VR or simulation. It raises a lot of privacy questions, and issues of restricted access.

C. T. A. Schmidt, LeMans and Sorbonne
Did You Lean That "Contraption" Alone with Your Little Sister?

Schmidt's research areas: the dialogical aspects of cognition and communication, and the context for learning -- the physical environment including other people. Key question that interests him: how can the machine learn if it can't communicate?

Robotics-embedded AI should be, or maybe must be, dialogical. In order for advanced humanoid robotics to be fully accepted by others, they will need the proper identity features or they will remain at the fringe of human communities.

Social roles and human institutional involvement seem to have been left out in all forms of AI. To make robots dialogical, we need to work on the pragmatic aspects of communication.

Michael Anderson, U. of Hartford
Susan Leigh Anderson , UCONN
The Status of Machine Ethics: A Report from the AAAI Symposium

Michael is a computer scientist, and Susan is a philosopher. They're here presenting summaries of the papers presented recently at the AAAI Symposium on machine ethics.

The time has come for adding an ethical dimesion to machines -- CareBots, unmanned aircraft, defense uses, etc. This will ensure their actions, especially in self-evolving or learning systems, remain ethical. (Note to contrast this with computer ethics, which concerns hacking and the like.)

The Nature of Machine Ethics:
1) Normative computer agents: computers are normative, because they're designed with a purpose in mind, but not necessarily an ethical purpose. Their performace is assessed according to how well they do what we've told them to.

2) Ethical Impact agents: these not only perform certain tasts, but have an ethical impact on the world. E.g. a robot jockey that guides camels in races, replacing young boys who are slaves who are otherwise forced to do this.

3) Implicit ethical agents: these are machines that are programmed to behave ethically and are designed to perform ethically. E.g. ATMs that are programmed not to cheat the bank or its customers, and automatic pilots entrusted with human safety.

4) Explicit Ethical Agents: machines that are able to calcuate best actions in ethical dilemmas.

5) Autonomous ethical agents: these can calculate the best action in an ethcial dilemma and function independently. E.g., a robo-soldier, sent into battle, which makes ethical decisions that guide its own behavior.

6) Full ethical agents: this term is used to describe human ethical decision makers. Are intentionality, consciousness and free will essential to genuine ethical decision making? Would it be sufficient that machines have "as if it does" versions of these qualities? Could it pass a "Moral Turing Test" for understanding ethics?

If humans create laws that allow them to mistreat entities that resemble human beings, it increases the chances that they will find it easier to mistreat human beings.

Developing an explicit ethical agent is a compelling goal of AI. Many approaches are being pursued. Democracy-dependent algorithms have been created, wherein agents could look up ethical information on the web, giving the machine a kind of "average" or "averaged" ethics. This is probably not good enough. Other methods use neural nets, or offer the human user a case-based reasoning engine with natural language inputs and outputs. Other researchers recommend using deontic and default logics to iteratively construct a theory of ethics. The Andersons have developed a system that extrapolates from experts' intuitions about particular ethical dilemmas.

See machineethics.com

Marcello Guarini, University of Windsor
Computation, Coherence, and Ethical Reasoning

Thagard-Verbeurgt Coherence Theory of Constraints (1998): hypotheses, evidence statements, negative and positive constraints. Used in moral reasoning problems. This system can be encoded in an associative neural network.

Thadarg identifies four types of coherence reasonings contributing to ethical reasoning: explanatory, deducive, deliberative, and analogical coherence. Ethical reasoning is a "multi-coherence" problem. The idea is that it can provide prescriptive or normative recommendations.

People obviously don't arrive at ethical decisions through brute force computation. We don't work out coherence values using internal computation. And we certainly don't do so consciously.

The roll-up: Guarini is critical of the Thagard-Verbeurgt approach, and that coherence is required for moral reasoning in machines. Read his paper for more.

[AI@50] Final Poll

40% believe that to produce a successful artifact, the most important approach is to make it interact with the world in which in it operates. Meanwhile, 44% think it should primarily be made to encode and exploit knowledge in the domain

60% strongly agree that AI should take a multidiscipmalary approach, incorporating stats, machine learning, linguistics, computer science, cognitive psychology, philosophy, and biology.

[AI@50] Selected Submitted Papers: Future Strategies for AI

[AI@50]
Filene Auditorium, Moore Hall
Dartmouth College
Hanover, NH

Conference notes by Meg Houston Maker

J. Storrs Hall, autogeny.org
Self-improving AI: An Analysis

Self-improvement and self-improving machines: from Turing's "child machines" that would learn and grow, to so-called "stick-built" AI that produces intelligence but doesn't necessarily learn and grow. But human adults do learn and grow, so we need an AI that does that, too.

Universal Learning Machines
There are limits to learning: many animals learn, and have speciific learning programs, but none improve recursively without limit. On the other hand, it's not clear that there are limits to learning for some individuals, and as a species we have been successful, so it's possible that limitless learning is a factor in our collective success. Similarly, our biology is so complex that it's likely we have more capacity. And it also looks like evolution has "learned how to learn;" we didn't evolve to do physics and chemistry, so continued learning was required for these advances.

[MHM editorial: this all seems a bit unrigorous. Is he talking about the simple acquisition of knowledge, or about learning as a process? He's using a lot of analogies to make the case that a universal learning machine is possible. Also, he's conflating the capabilties of the scientific community as a whole, in its capacity to develop a machine that can learn to play chess better than Kasparaov, with the capabilities of an individual human learning agent.]

Selmer Bringsjord
The Logicist Manifesto+

Why the +? You shouldn't just use logic to do AI, you should use logic to discuss ai, too. Logic occupies a unique, indestructibly central position in human cognition.

Types of AI:

- Strong AI: We can engineer systems that have attributes constitutive of human personhood; this is replication, not simulation.
- Weak AI: engineer systems that appear to be intelligent; this is simulation
- Strong/Weak AI: we can manage to create a system that is behaviorially indistinguishable from mere animals and humans, over finite intervals of time.

Strong AI is not likely in 50 years. Weak AI we already have, and Strong/Weak AI, maybe.

How can we ensure that robots always will behave in an ethically correct manner? How can we know ahead of time, via rationales expressed in clear English? We should regulate the behavior of robots wtih computational logic, so that all robotic actions will be sure to be ethical.

How Can We Ensure This?
- Humans select an ethical theory, principles, and rules
- The selection is formalized in logic
- It is mechanized
- Every action that's performed has to be permissible according to this mechanization.

Vincent Muller, American College of Thessaloniki
Is There a Future for AI Without Representation?

Can we do AI without representing the world?

Rodney Brooks suggests a layered subsumption architecture, and situating (embodying or grounding) the machine in the world. He rejects central control over emergence of intelligence. And he rejects representation in the classical sense.

So, what is representation? When should we say that X represents something? What are the conditions for something being a representation? And under what conditions does something represent something else? Representation is dependent on people's intention that something represents something else.

Icons - represent what they represent (e.g. portriat painting)
Indices - connected by a causal connection (e.g. smoke indicates fire)
Symbols - connected to what they represent through convention (like words of a natural language)

Information and Representation: a rock is wet if rainy, warm if sunny. The rock conveys information, but it doesn't represent anything. On the other hand, some things are made to convey informaton for us (clocks, thermometers).

Hilary Putnam, Jerry Fodor and others think that representational or intentional features of symbols and signs must be explained with the help of mental representations. But how do you find out the function (either natural or conventional) of the representation? Causal connection is necessary part of the equation.

Brooks's New AI appears strangely unmotivated -- discovering that classical AI is not represntation, we propose another system that is not representational.

Cognition without central control
Traditional AI/Cog Sci/Philosopy of mind holds that central control is assumed, and then representation is deemed necessary for the agent to succeed.

Theses:
- cognition is the processing of outside information
- the information comes in the form of representations
- the processing of representations is computational

The first two of those make the representational theory of the mind, and all three together yield the computational theory of mind (and the PSS hypothesis).

Indications against central control:
Mark Bickhard: critique of "encodingism:" - the mind does not decode and encode information: because who would do the decoding and encoding? Ways out of this: remove the notion of encoding from that of representation via natural functions, and abandon the notion of mental representation as a causal factor.

John Searle's Chinese Room Argument
Searle looked at the processor in a computer and asked what that agent understood: nothing! The systems reply agrees that the agent does not understand, but claims that the whole system, of which it is a part, might. Buty why should the system understand?

Brooks's inspried response: the system understands because there is no central agent in the system.
Abandon the cartesian theatre: searle was asking the wrotn question, just like eerybody else.

Embodiment of cognition: intelligences in the body as a whole. This involves the integration of cognition and action. Perceiving isi really a way of acting. Perception is not something that happens to us (see e.g. Noe). So there is an indication that cognition, emotion, and volition must be integrated.

We do not get conscious representation without central control. Conscious experience is the experience of "what it is like" -- the having of experience: I am the one that does the perceiving, thinking, palnning, and acting. Consciousness requries something being conscious, and this requires a central agent. The progelm is people move from that to saying that all of cognition has to be centrally organcized. But we don't know what we can do (or do without) central control.

[AI@50] Future Interactions with Intelligent Machines

[AI@50]
Filene Auditorium, Moore Hall
Dartmouth College
Hanover, NH

Conference notes by Meg Houston Maker

Daniela Rus, MIT
Making Bodies Smart

Robotics is a dream to build a machine in your ownd image; building platforms for stuying life and intelligence, intelligent conection of perception and action, outcome of visiouaries with energy and resources; the next disruptive technology. The field has been fueled by crazy dreamers.

The history of robotics is the history of automata, Golems, Frankensteins, all the way to current robotics. There has been some trepidation about these "soulless beings."

The hard problem is to capture what happens in the interaction between computation and the physical world. Hand-eye coordination, which we do to survive, is really one of the hardest problems.

Robotics methodology timeline:
- Knowledge representation -> symbolic reasoning
- Blocks world - kinematics
- Motion planning - automation and manufacturing
- Reactive control - exploration
- Probabilistic/expectation/verification - mobile/field, space, underwater
- Human-centered - home, medical, entertainment
- Modular/distributed systems - self-organization, RoboCup

Things we take for granted in robotics (and need to do our work): GPS, Real-time vision and stereo, WiFi, Rapid prototyping, GHz processors, Gumstix, Sick laster rangefindesrs, etc. These have all developed in the last 10 years, and have been a boon.

What we've gained: localization, planning and navigation, 3D perception. However, we have many challenges ahead. Of these, uncertainty is one of the biggest; the world is unpredictable, and the robot has to be able to handle it. Perception also remains a major challenge. Robotics has made huge strides in areas of navigation, but manipulation, which is just as important as navigation, is far behind. We need to be able to develop algorithms for enabling computers to interact better with humans, and we need deeper connections between perception and action.

"Simulations are always doomed to succeed:" taking the robots from the lab to the field, from simulation to actual world, remains a big challenge.

Many robots have not been constructed with the explicit goal of understanding human intelligence. Rather, they have been more task- and motion- oriented. What is the environment of the robot? Is it fully known? What is available to it? This is robotics for structured environments, and comprises the last few items on the list above (motion).

Rus shows her work in with robotic self-organization; really smart parts that know how the whole is to be organized. In application, imagine a robot encountering a river without a bridge, and constructing a bridge for itself.

Predictions for the future:
- Robotics will give us new theoris for intelligence -- we need to account for situatedness and embedding in natural world; we will move beyond Turing intelligence
- Robots/actuation will be pervasive
- Robots will accomplish the ultimate automation -- on-demand factories
- Robots will save the environment -- biologists are overwhelmed by simple tasks like data collection; it's not just to monitor environment, but also to effectively repair processes in which the system is damaged
- Robots will extend and enhance life -- the convergence of DNA and silicon will happen.

Human-centered robotics will enable us to move from personal computers to personal robots.

Sherry Turkle, MIT
From Building Intelligences to Nurturing Sensibilities

Technologies are never just tools; technologies are "evocative objects." Computational entities (computers, agents, robots) become relational companions. They provoke anthromorphizing. Her objects are designed to provoke nurturing behavior.

What is a relational artifact? It's an evocative object. These present themselves as having states of mind affected by interactions with humans. They impress not just through their intelligence, but through their sensibilities. In how we interact with them and reflect on our relationship to them, we learn about our own inner states.

E.g. Kismet, Aibo, Furby, My Real Baby. This last wasn't so successful with children but was very successful with seniors in senior centers. Children and seniors are both somewhat vulnerable populations. With seniors, sometimes it's interactions with robotics or nothing, and in some cases the robot is "good enough" to satisfice, as it were, for human interaction. But the robot is not really empathetic. This could be misused, morally, because the question is who will be given (actively) a robot as the best our culture can do to provide them with companionship: the disabled, the elderly, children.

The art and sciene of reltional artifacts is part of the art and science of understanding human psychology and human vulnerability. Interaction wtih these objects move from the psychology of project to the psychology of engagement and object relations. In talking about relationsl artifacts, the discourse of aliveness moves from the objects competetency (physical or psychological) to the person's relationship with the object. They push our Darwinian buttons. People respond to these objects as though they were sentient and feeling objects.

Children can differentiate -- and have to learn to differentiate -- between animal alive-ness and robotic alive-ness, between animal love and robotic love. Children nurture robots; they think of a nonfunctioning robot as wounded, they show belligerence towards robots when angry, and view robots as dialogue partners in conversation.

Nurturance may turn out to be the killer app.

In the 1980s Turkle met a teenager who spoke about the pleasure of working with a personal computer because it was like putting a piece of her mind into the computer's mind. Twenty years later, children and elder nursing home residents who have robotic agents report that they feel emotionally connected with the robot. They feel love. This is a sea change.

Relational artifacts present themselves as a possible Self objects. Now, Self objects are positive psychology when the object is a person. It presents a narcissistic experience to project self onto others, but robotics might be used this way. Perhaps there is therapeutic potential here, but what are we to make of this? Is it good for us that we have robots that convince us they care? Or will our lives be enhanced because we'll have to develop new ways of feeling toward these others, and our new kinds of relationships?

[AI@50] Sixth Polling Question

Only about 10% agree with Marvin Minsky that AI chess is waste of time because it's about exploiting human weakness, not simulating human thinking

[AI@50] AI and Games

[AI@50]
Filene Auditorium, Moore Hall
Dartmouth College
Hanover, NH

Conference notes by Meg Houston Maker

James Moor, intro: Chess was thought to be difficult, so that if one could master a chess program one had achieved something. However, it turns out games are reasonably easy to master, and areas like natural language are much harder. Moor plays a video clip of Marvin Minsky, who says that chess AI projects had to be focused on the middle game, and the opening had to be programmed, so AI chess was not a very promising simulation of human intelligence.

Jonathan Schaeffer, Alberta
Games as a Test-bed for Artificial Intelligence Research

Marvin Minsky is WRONG WRONG WRONG! But he's not even here today to hear me say it! [Minsky left the conference yesterday.]

Building a chess program was viewed as a grand challenge of AI research. It was a goal that seemed attainable, and worthwhile, and was something that the public could relate to (unlike missle trajectories). This was a coup for AI, because this made it accessible to the media. The first computer chess tournaments started in 1970. So this is really the longest-running experiement in AI, and we can see the evolution of successes. Also, chess products were AI's first big commercial success.

Schaeffer clarifies he's not a games researcher -- he's an AI researcher who uses games as his testbed, rather than defense or engineering proglems, etc. He takes an application and does whatever it takes to build a powerful and successful program. It's an overall strategy of building a high-performance system.

In the chess world, we have seen lots of effort in the last 40-50 years. There was a lot of effort that went into building a grand master chess program. It took a lot of effort and money to build it. Visionaries include Claude Shannon, Alan Turing, John McCarthy, Newell and Simon. They underestimated the challenge!

But it turns out that to make a winning chess program, you need an Alpha-beta search algorithm, an evaluation function to decide good and bad chess positions (these are pretty simple), and fast computing hardware. Wtih hindshigt, this all seems obvious, but it was not evident until the 1980s. Hardware was the key to Deep Blue's success. It had 512 special "chess chips" running in parallel. It was a very fast parallel process. But it's an idiot-savant: it plays brilliant chess, but it can't do anything else.

Brute-force search: use a comptuer to do fast searching. Many researchers felt this was not actually AII because it's not how a human would play chess. But there's no argument that can be made that says humans play chess the "right" way. Computer hardware is fundamentally different from hnuman hardwared, so it shouldn't be surprising that these machines operate differently in solving the same problem.

So one of the most profound contributions of chess is the effectiveness of brute force search. It's simple, elegant, and a good match fo the capabilities of the computer. Other AI chess contributions include search enhancements, hardwares colutions, and an appreciation for the difficulty of building high-performance AI systems.

Chess itself was not as interesting for AI researcher (limited, 2-player game) as other games, which were more representative of the real world, involving randomness, etc.

Checkers: Arthur Samuel used checkers for pioneering AI research. This work, from the 1950s and 1960s, is still cited today. Marion Tinsley was a checkers grand master who only lost 3 games in 40 years, but he was beaten in 1994 by Schaeffer's team developed. This system earned the right to play Tinsley by winning up through competition.

Other games: Othello is another game in which the AI machine version completely overwhelmed the human chamption. Backgammon and TD-gammon, a neural-net program, showed other successes. Scrabble also fell (1998), using Brian Sheppard's Maven. To a computer, words are just sequences of letters. Crossword puzzles (1999): Michael Littman and a team built Proverb by building a database of past crossword puzzles. It turns out about 1/3 of clues are repeats from previous puzzles. So just looking up clues can get you 30% performance. If you take the clues and send them to an internet search engine, you get the result pretty quickly. The program does 96% on the NYTimes Crossword Puzzle, without understanding the meanings (semantics) of the clues at all. Poker, Bridge, and Shogi AI products are coming soon. Go still needs a lot of work.

Games are great becuase you have no trouble attracting grad students!

But chess is the past. So what's going on now? Commercial computer games are now a $25 billion a year industry. This isthe new grand challenge in using games as an experimental testbed. Interactive games are the killer app for human-level AI (see John Laird and Michael van Lent).

Example game: Oblivion. It boasts "radiant AI" with realistic characters. Schaeffer plays a clip that is laughably unrealistic. Characters don't react in naturalistic ways to actions in the game.

Why is Game AI Hard?
Games have to be developed to run on a 2-year-old computer, and can't use the whole CPU (just 10-20%). You have to use limited memory and limited disk, and the program has to be thoroughly tested. You need real-time response (no long computing times). Content generation is the dominant cost in R&D. Realism is essential, and the game has to be fun. The Academic AI community doesn't develop solutions useful in the game AI community. Researchers think nothing of using lots of memory, long processing times, etc.

Random numbers are the most powerful AI tool. Because from a random sequence of events, users discern intelligent behavior. It's not truly random, it's controlled; it's not as if the character walks randomly choosing directions. Rather, it's controlled in that having made a random decision, the character's next decision is consistent with that first decision. So it looks like flow, it looks naturalistic to users.

Obstacles to Quality AI in Gaming
There is little research money in industry, and the game industry is suspicious of academic research: about 90% of what's published as "useful for games" is not actually usable by the gaming AI community.

Want a challenge?
Get rid of your fast hardware, use little time and memory, try to create realism and give real-time response. Human-level AI is needed today.

Danny Kopec, Brooklyn
Chess and AI

What you see in matches between humans and computers relies on human frailties. Machines can learn from humans, and humans can learn from machines.

Chess is very much alive. It hasn't really been solved yet. In May 1997, IBM's Deeper Blue defeated Kasparov, but Kopec doesn't put much stock into this, because it was a very quick match, and Kasparov changed his usual strategy, and the machine exploited that. Kopec gives many other examples of chess matches between humans and computers over the last 5-10 years. Results are mixed, but adding complexity is that the tournaments and exhibitions are being run often with times controls -- 60- or 90-minute time control (match length) with a 10- or 30-second increment (time to make a move).

Is the machine "thinking" when it's calculating? There is disagreement here. There's nothing to say that they have to "think" the same as humans. Kopec shows many examples in which the right play is counterintuitive. Humans play by heuristics, experience, knowledge, intuition, knowledge, and pattern matching. Human chess involves psychology: gambling your own knowledge against your opponent's knowledge. Humans search what's important on the board, and know how to choose what's important. Chess is way more than search.

[AI@50] The Future of the Future

[AI@50]
Filene Auditorium, Moore Hall
Dartmouth College
Hanover, NH

Conference notes by Meg Houston Maker

Ray Kurzweil, Kurzweil Technologies, Inc.
Why We Can Be Confident of Turing Test Capability Within a Quarter Century

Kurzweil demonstrates some new developments: he takes a picture of a page of his recent book, then in a few seconds we hear the text read through his laptop. This is not your daddy's OCR and text-to-speech system; it is managing the natural image distortions that arise when you take a picture of a book with a hand-held camera.

The pace of progress is not constant. The paradigm shift rate is now doubling every decade. The pace of technological evolution and of technological adoption is accelerating. Exponential systems go on until that particular paradigm runs out of steam. And then we're ready for the next paradigm.

Moore's Law was actually the fifth paradigm for computing; right before that there were vacuum tubes, which were shrinking as capacity grew exponentially. Then we got chips, and pretty soon we won't be able to get further exponential growth from our existing silicone architecture and we'll have to move to 3-dimensional chips. Intel's pretty confident these will be ready so that capacity will continue to follow that exponential trajectory predicted by Moore's Law.

But, what are the limits of growth? In computation, it looks like there are limits, but it turns out theyre not very limiting to what we're trying to do in AI. By about 2020, we'll have enough computational power to simulate all the features of the human brain. So what about the software? Some think that reverse engineering the brain will provide the ultimate source of the template of intelligence. Our brain scanning software is getting more powerful, with more resolution, each year.

What is the complexity of the human brain? There are trillions of interconnections. But there are only a few genes that control it; the design is in the genome, and the genome just doesn't have that much information in it (it has a lot of redundancies). It's managable complexity.

[AI@50] The Future of Language and Cognition

[AI@50]
Filene Auditorium, Moore Hall
Dartmouth College
Hanover, NH

Conference notes by Meg Houston Maker

Trenchard More, IBM (retired)
The Birth of Array Theory and NIAL

More dives into a discussion of both simple and elaborate Cartesian products of arrays and array nesting. I bet it's beautiful to a mathematician. I can't possibly summarize it. See more on Array Theory and NIAL (Nested Interactive Array Language).

Eugene Charniak, Brown
Why Natual Language Processing is Now Statistical Natural Language Processing

NLP has experienced a revolution in the last 15 years, and gone from being a domain based on logic to a domain based only on statistics. Non-statistical approaches are now quite rare.

Parsing
Going from a string of words to a parst tree. "Alice ate yellow squash" gets decomposed to noun, noun phrases, verbs, etc., in a complete analysis of the sentence in tree structure. This is much like what a grammar school student does when diagramming sentences. Parsing gives us a first pass at a meaning of a sentence, breaking up the meaning of the whole sentence into the meanings of its parts. But if you don't know the rules of the language, or grammar, you're not going to be able to get a correct parsing or correct interpretation.

Adding complexity, a single string can have multiple parses. So, which is the correct parse? Different parses yield different meanings:

"The salesman sold the dog biscuits."

Did he sell dog biscuits?
Did he sell biscuits to the dog?
Did he sell a dog named Biscuits?

Parsing in the "old days" assumed that sentences had only a handful of correct parses. Most research was concerned with either designing a parsing algorithm or developing better algorithms. As late as 1990 there was no parser that could find a semi-reasonable parse for every sentence on, e.g., the front page of today's New York Times. Which is a perfectly reasonable requirement.

So why is this problem so hard? First, grammars "leak" -- it's hard to write a grammar that handles all the complexities that natural language can throw at you. The second problem is ambiguity. To prevent a grammar from leaking, you have to write a grammar parser that is overly complex (and unrealistic).

We have to recharacterize the problem as a probablisitc/statistical one to find the most probable parse for a sentence. Probablistic context-free grammar offers a set of rules that define derivations for strings in the language of the grammar, with derivations represented by trees. The probabilities are then interpreted.

Training corpus: The Penn Wall Street Journal Tree-bank, which contains about 1 million words, and was compiled by humans. Lexical statistical parsing is achieving decent accuracy, and very promising future results.

But still... how to get at meaning? Take it gradually. Start with the stuff you know. E.g., you know that if a sentence has "tomorrow," that's it signifies temporal meaning.

Pat Langley, Stanford
Intelligent Behavior in Humans and Machines

We need a renewed emphasis on cognitive psychology. Simon and Newell, the early pioneers, viewed themselves as psychologists trying to explain human thought. This approach was well respected at that time. Much other early work on representation dealt with the structure and organization of human knowledge. Not all research in AI was motivated by psychological concerns, but it had a strong impact on the field.

There were studies of human problem solving in early AI work and these led to key insights about both state-space and goal-directed heuristic search. The 1980s saw many developmetns in knowledge-based reasoning that incorporated ideas from psych: expert systems, model-based reasoning, analogical reasoning, and natual language work.

Early AI modeled human learning and discovery, problem solving, categorization, natural language, and scientific discovery. Modern AI has moved away from human cognition and is unfamiliar with results from psychology, despite the historical benefits. E.g., in knowledge representation, the work focuses on efficient processing. In problem solving and planning, and NLP, there are focuses on statiscial methods that have few links to linguistics or psycho-linguistics. And in machine learning, statistical techniques are dominant, but you need larger data sets and training cases than a human would need to achieve the same level of expertise.

Technhology is one reason for this shift. We have faster computers that allow us to mine large data sets for more predictive models. But we should combine this computing power with insights from psychology. Additionally, AI is typically housed in computer science departments, which often grew out of math departments. Mathematicians are usually more concerned with tractability, even if that restricts the work to narrow classes of problems, and many mathematicians also view psychology with some skepticism. There has been commercial success with AI, but this tends to encourage niche works. In academic settings, we should reach for higher goals.

One reason to renew the interchange between the two fields is to achieve better understanding of human cognition. Human abilities serve as important sources of tasks for study: studies show that people can do some pretty impressive things.

Cognitive psychology makes important representational claims, e.g. that humans resort to problem solving and search to solve novel and unfamiliar problems, and that they use heuristics (not algorithms) to find good solutions. In learning, cognitive psych shows us that people create new cognitive structures in problem solving, and that learning is incremental and interleaved with perfomance.

The AI curriculum should include cognitive psychology, structural linguistics, logical reasoning, and the philosophy of mind.

[AI@50] Sixth Polling Question

[AI@50]
40% say it will be more than 50 years before machines will be able to simulate learning and other aspects of human intelligence

[AI@50] The Future of Reasoning

[AI@50]
Filene Auditorium, Moore Hall
Dartmouth College
Hanover, NH

Conference notes by Meg Houston Maker

Alan Bundy, University of Edinburgh
Constructing, Selecting, and Repairing Representations of Knowledge

Two hypotheses
1) The representation of a problem is often the key to its solution
2) Problem representations can be automatically formed and automatically repaired

Representation as the Key to Problem Solving
- McCarthy's mutilated checkerboard example
- Saul Amarels Missiories and Cannibals example -- illustrating how a change of representataion affects the size of the search space, making the problem easier to solve
- Andy DeSessa's Bouncing Ball, in which it's asked: where does the energy of a bouncing ball go at the moment of impact? The answer is that the ball and floor both become deformed. It is essential to understsand that neither is fixed.

We have to think of representation as fluid, as something that changes as we reason. The world is infinitely rich, and we cannot model every aspect. Fixed representations cannot cope with a changing world and new challenges. If we want to build agents that can deal with a changing world, then we'll have to have representations that are under machine control and will evolve according to new situations.

This is not a question of changing your beliefs about the world. Rather, it's a change in the "signature" -- the predicates and functions in your algorithms. You might need new functions, you might change their arguments, their types, etc. Even the logic might have to change. And all this has to be under machine control during the processing of problems. Computers can form representations and then be made to repair faulty representations.

Repair of Representations
Cynthia, e.g., is a program that helps users write computer programs, creating new concepts and conjectrures from examples. Underlying the system is a proof that the current program was not meeting expectations of well-formedness. Other systems work to identify faulty proofs that end up causing bugs in the system. The ORS Program, e.g., repairs faulty ontologies by analyzing failed multi-agent plans. Changes include abstraction and refinement of signatures by adding arguments, changing predicates, etc.

This technology is essential for realizing the Semantic Web, in which huge numbers of agents are going to have to share ontologies. The changing community of systems will never really share any single ontology -- there will be sublte differences no matter what we do. The idea is that one can dynamically repair those differences as a result of faulty interactions between the systems. It's not possible to do static repair when you have huge numbers of agents independently developed.

Conclusion
- The formation of representation must be under machine control in order to deal with a mutli-agent, changing world.
- Representational change can be triggered by reasoning failures

Edwina Rissland, UMass
The Exquisite Centrality of Examples

The world is rich, it's got exceptions, it's not regular, and yet we can deal with it. Rissland calls this the inevitable intertwining of knowledge -- a Yin and Yang intertwingling of (Examples) with (Concepts, theorems, models, statistics).

Examples are grist for the mill of learning. Rissland's interest is in the Example side of the equation:

- in learning and in teaching
- in explanation and argument
- in concept representation and concept change
- examples built to suit; in how you build examples that satisfy the problem you're trying to solve

Categories of examples (or hypotetheticals, which are equivalent):
- startups, which are easily used without much background
- references, which are standard or useful anytime
- models or prototypes that capture generalites or abstractions about the world
- anomalies that are atypical or borderline
- counter-examples used to refute or limit

There is structure implicit in probing with hypothetical examples.

Examples are useful when we're dealing with real world concepts. Our analysis shoudln't be all representation, or all examples, or all statistics. She advocates a hybrid approach: open-textured (messy) + non-convex + non-stationary

Conclusion:
Examples are really halfway between statistics and generalities. Don't throw the examples away as you try to abstract up. Examples are useful in concert with other information (from the domain), plus logic, statistics, etc.

Q&A
Q: Wouldn't it be useful to have a knowledge base of examples?
A: Some fields do: medical bases, legal case books, etc. These tend to be domain-specific. The trick is how to represent these and put them into your knowledge base. Building examples with constrained example generators works when you know what you want. But how do you know what you want?

Q: Are examples mostly concrete instances?
A: They don't have to be. Once you start developing hypotheticals, you start expanding beyond examples to logical models (at the extreme).

Bart Selman, Cornell
The Quest for Machine Reasoning

From the 1960s to the 1990s, computational limitations made machine reasoning nearly impossible. McCarthy (1956-59) proposed an intelligent system architecture with declarative representation and inference. But inference was computationally infeasible. From car repair (with about 100 variables) to military logistics (with 200,000-600,000 variables) and more, the computational requirements are enormous.

But in the last 15 years we've made progress in processing in these combinatorial search spaces. Applications include pattern generation, e-commerce and e-auctions, scheduling, hardware and software verification, multi-agent systems, etc. Significant advances have brought us from being able to handle 200 variables to 1 million+ variables.

Selman shows a chart showing the time required to solve specific reasoning problems, using technology available over the last decades. Now, the time to solve some of these classic problems has been driven to zero. (Someone interrupts to ask what zero means. The response: "That's very fast" [laughter].)

Backdoor variables: real-world structure hidden in the networks can be exploited by automated reasoning engines. You can reduce a many-hundred-variable information space by isolating a few backdoor variables that will solve the problem.

Summary
Automated reasoning tools might serve as a true "cognitive assistant" helping humans apply their creativity to a system, and use the solvers to analyze the implications of these choices, and for validation and feedback.