Recommended Readings in AI
Every once in a
while I read a rare book or paper
that completely changes my
views on AI or is quite simply so well-written that it gives
me deeper insights and intuitions about topics that I
already feel reasonably comfortable with. Following are some of these
books and papers along with a brief description of why I found them so
intriguing.
Sciences of the Artificial (Herb Simon)
-
Why I Recommend It: This is a classic book in the field of AI
and in it,
Simon considers many ideas including the nature of thought and
whether it can be simulated, the architecture of complexity,
AI as an empirical science, and topics for tractable system
implementation such as partial decomposability and
hierarchical structure. This is a book with many profound
ideas and it is not surprising that these ideas continually manifest
themselves throughout modern AI research.
Unified Theories of Cognition (Allen Newell)
-
Why I Recommend It: In this book, Newell proposes that the state
of cognitive science has become so fragmented that progress
toward the goal of a "Unified Theory of Cognition" is no
longer being made. In response, Newell makes the case for the
study of cognitive architectures (i.e. operating systems for the
human mind) in order to validate the
research being done in the different subfields of cognitive
science and to
ensure that these individual theories are mutually compatible
on a cognitive scale. Only through this combined analytic and
empirical approach does Newell believe that we can achieve a unified
theory of cognition, and I believe these same ideas are equally
applicable to a unified theory of AI.
Situations and Attitudes (Jon Barwise and John Perry)
-
Why I Recommend It: This book deals with the limitations
of standard mathematical logic in dealing with the subject of
"meaning" as we experience it in everyday life. Barwise and
Perry do a wonderful job of elucidating many properties of
meaning with respect to natural language and the shortcomings of
the traditional logical semantics for modelling these
properties. In response, they propose an alternate natural
language semantics that they term situation semantics
(essentially an intensional logic and semantics). This logic
and semantics naturally captures many of the context-specific
properties of natural language that prove otherwise difficult to
model and reason with under the standard model-theoretic
semantics. In this way, Barwise and Perry demonstrate that
useful logics for AI may differ quite substantially from the
logic that we use in mathematics... not that one is correct and
one is wrong, but that one must use a logic and semantics
appropriate to the structure of the task.
Hermeneutics (Richard Palmer)
-
Why I Recommend It:
In an effort to model the phenomenon of context-dependent
reasoning, the rationalist approach to AI has
predicated most of its theories on a highly structured, explicit
model of context. However, these approaches have often been of
limited use in practice. In contrast,
phenomenologically oriented
approaches treat context reasoning as a more
dynamic phenomenon, involving horizon and
readiness-to-hand,
quite simply the notion that context is simply a process of
bringing to bear all experience and information required to deal
with the specific situation at hand. In such a framework,
context is simply an ephemeral and emergent notion that
corresponds to the appropriate information required for
communicating, reasoning, and acting - in general, for
being in the world. And in this way it is much
more adapted to the types of human context reasoning that
we are often trying to imitate in AI.
This book introduces many of these notions through the
work of Heidegger and Gadamer and their phenomenological
approach to hermeneutics, i.e. the theory of understanding, or
interpretation.
Understanding Computers and Cognition (Terry Winograd and Fernando Flores)
-
Why I Recommend It: Winograd and Flores were two of the
first researchers to explicitly introduce
phenomenological ideas into the fields of AI and HCI and in
doing so, they sparked a revolution whose effects are still felt
today (see Dourish, below). In short, the ideas expressed in
this book propose a reorientation for how we think about
ourselves, our cognitive processes, and our language abilities.
These notions in turn radically affect how we should design
"intelligent" computers, i.e., how they should represent
knowledge, and how they should process and communicate language.
- General Thoughts: There are many fascinating ideas in
this book that counter rationalist intuitions in AI and replace the
objective models of traditional AI with purely goal-directed behavior.
With respect to the meaning of language,
W&F cite Gadamer, stating that "no statement simply has an
unambiguous meaning based on its linguistic and logical
construction, as such, but on the contrary, each is motivated.
A question is behind each statement that first gives it
meaning." (p. 112) And so, W&F proceed to move away from the
rationalist paradigm of language that attempts to model
knowledge abstracted from any particular goal, and move instead
to a framework where all reasoning is performed with respect to
an explicit goal derived from subjective experience. In this
way, W&F manage to avoid the issue of "meaning" by redefining
knowledge with respect to its ability to achieve a goal, and its
value as such.
And contrary to many people's beliefs, I don't
think such a pragmatic approach to knowledge representation
precludes logic as a modelling language, it simply redefines the
way in which logic should be used (in the spirit of what Perry
and Barwise have proposed above, but even more radical).
Where the Action Is (Paul Dourish)
-
Why I Recommend It: In this extremely lucid book,
Dourish continues the infusion of phenomenological ideas into
HCI as begun by Winograd and Flores. Based on phenomenological
foundations, he encourages a design perspective that emphasizes
"embodied interaction" over "disembodied rationality", i.e.,
that we should design with interaction as the primary purpose
instead of designing for an explicit task, requirement, or
application (especially since it is easier to learn and repair
interactions than it is to learn and repair models). In doing
this, Dourish suggests that we can build systems that are more
adapted to their place and usage in the world. In addition to
its implications for software engineering and HCI,
this book also provides a clear and concise
introduction to the philosophy of phenomenology.
- General Thoughts: A reader familiar with AI will
probably note that these ideas are not new and were also
introduced in the domain of robotics in the late 1980's and
early 1990's by Rodney Brooks in the form of "embodied
intelligence" (although he makes it explicit that he was not
influenced by Heidegger and phenomenology but rather by pure
engineering considerations). While Brooks was undoubtedly
correct in many of his criticisms of AI and his approach was
well-motivated (see his excellent discussion in "Knowledge
without Representation"), he took such an extreme stance and
made such specific prescriptions that it often obscured
many of his more practical and general views.
In contrast, I think Dourish takes a broader philosophical
approach to the idea of "embodied interaction", posing the
general principles without committing to overly-specific
blueprints for achieving practical interactive systems. In this
way, I think Dourish ultimately provides the seeds for a
framework that allows the successes of the rationalist and
phenomenological paradigms to be synthesized into a system that
avoids the pitfalls of the individual approaches.
(Read: Hegelian Dialectic. :)
While specifically intended for HCI, I think all of these ideas
generalize equally well to AI and the notion of embodied
systems. Ultimately I believe embodiment (even in a
cyber-sense) will be the only way to achieve the goals of Strong
AI.
Arenas of Language Use (Herb Clark)
-
Why I Recommend It: In this book, Clark proposes that in
the domain of natural language, context is simply the common
ground (i.e. collective shared knowledge and experience) of the
participants. In this way, we can simply define context as a
set of experiences that yield information relevant to the
interpretation of discourse between two or more participants.
Thus, rather than treating natural language communication as an
umambiguous conduit of information, Clark proposes that
communication is instead a collaborative process where the goal
is to mutually establish the meaning of what is being
communicated. In doing this, he provides a fascinating account
of human language understanding, incorporating many other
pragmatic theories such as Austin's speech acts.
- General Thoughts: In general, I believe these ideas
(and a lot of others floating around similar to these) can have
a huge impact on the way that we go about natural language
processing (NLP) in AI. Rather than treating NLP problems as
one-step, isolated machine learning tasks, we can generalize
them to sequential decision processes (i.e. most likely
POMDPs) where there is a value associated with gathering more
information and understanding is more of a value-directed
interactive process than a rote, disembodied algorithm. And I
believe that computers will only ever come close to
"understanding" in the field of NLP through such value-directed
elaborative and collaborative processes.
"What's in a Link", "Important Issues in Knowledge Representation", "Don't Blame the Tool", "Understanding Subsumption and Taxonomy" (Bill Woods)
-
Why I Recommend Them: It's hard to pick
just one paper from Bill Woods since he has introduced so many
interesting ideas into AI and related fields over the years.
Consequently I have chosen four of his papers which are a
representative sample of some of his views on knowledge
representation (KR).
The first paper, "What's in a Link", was a seminal
paper in the field of knowledge representation that sought to
provide logical foundations for the semantic network community,
which ironically up until that point, lacked a well-defined
semantics. This paper presents some beautiful and intuitive
ideas on the need for logic as a semantic substrate in
knowledge representation languages.
"Important Issues in Knowledge Representation" and
"Don't Blame the Tool" both introduce some practical notions
into the field of KR. In the first paper, Woods proposes the
idea of notational efficacy for representation languages
(offering a nice explanation for why variable-free
object-oriented logics are a very natural, useful, and efficient
representational formalism despite their somewhat limited
expressive power). In the latter paper, Woods cautions
researchers not to decry logical knowledge representation simply
because it is inadequate for solving certain tasks. In doing
this, he cites the adage that "a poor craftsman blames his
tools", explaining that one cannot blame logic if it was
inappropriate for the task or if it was used incorrectly.
The last paper, "Understanding
Subsumption and Taxonomy", is a beautiful paper that outlines at
least 15 years of Woods' research in knowledge representation.
It covers many ideas, but perhaps one of the most important is
a recurring theme: The idea
that subsumption and taxonomy are actually quite general
mechanisms for reasoning about generality and specificity in the
world, i.e., that these concepts are much more general than
their specific uses for object-oriented or conceptual logics.
- General Thoughts: I think this latter idea of
subsumption and taxonomy as a general framework is one of
the most powerful ideas not fully realized in the field of AI.
And I don't believe this is because it's such a difficult idea
(certainly, it's very straightforward), but rather because most
research is looking at isolated learning and reasoning problems,
and the need to transfer knowledge between tasks in an on-line,
continuous environment has not been an immediate research need
to-date. However, I think the advent of autonomous systems
(e.g. robots, web agents, etc...) will significantly alter
the nature of research in AI, and I think the need to analogize
and generalize from experience will be central to the issue of
building systems that can adapt to tasks for which
they were not explicitly programmed. (Also note how the
previously discussed phenomenological concepts of context fit in
nicely here.)
Reinforcement Learning (Rich Sutton and Andy Barto)
-
Why I Recommend It: This is an extremely accessible
book that beautifully covers one of the most important
topics in AI -- learning to act in an uncertain and unknown environment.
Not only does this book cover an important area of AI, it does
so succinctly and in an explanatory manner that makes reasonably
difficult concepts easily accessible to a wide body of readers.
This book covers just enough material to give researchers a
fairly comprehensive overview of the main results in reinforcement
learning (RL) and in doing this, it serves as a general reference that
helps prevent redundant work that is a plague of many other fields.
However, one of the most remarkable things about this book is that
after reading it, you can go out and immediately apply the ideas
contained therein. If there was a book like this for every core
topic of AI, I can only imagine that the entire field would
progress much more rapidly.
- General Thoughts: If I had to decompose AI into
three constituent components, I would be inclined to choose the
following: learning, search, and acting. However, the
decomposition is not so clean as to make each of these
components independent of the others; rather each specifies an
independent problem that must be solved in the context of the
others (read: a unified theory). As argued in a lot of
Daniel
Dennett's work, the whole of all three systems working together
is greater than the sum of the individual parts.
To this end, RL spells out an interesting framework in which
learning, searching, and acting can be intertwined. Clearly one
can see how reinforcement learning involves the interaction of
learning and search: an agent takes exploratory actions in an
unknown environment and receives feedback that it uses to learn
about it's environment. As the agent learns more, it may be
more inclined to exploit its current model of the environment
when acting so that it can maximize its future expected reward. And
eventually, if the agent has managed to build an approximate
model of its environment, it can apply search techniques within
this model to make predictions about the outcomes of sequences
of actions without ever having to act, i.e., the act of planning
(most likely under uncertainty).
This last idea -- the notion of searching or planning under
uncertainty within an (approximated) model -- is another large
topic area in AI. While much RL work has sought to address this
issue, there is also a large body of work independent of RL that
has dedicated itself to this problem. I think it is important
to draw on ideas from this body of work to further inform RL
techniques (as many have previously done), and this brings me to
the next set of papers on decision-theoretic planning, which can
help us do just that.
"Decision-Theoretic Planning: Structural Assumptions and Computational Leverage" (Craig Boutilier et al.)
-
Why I Recommend It: Very rarely is it the case that
general theories are also accompanied by tractable methods for
implementing them. However, I think this paper qualifies as one
of these rare cases. The primary purpose of this paper is to
synthesize work from the fields of search, planning, and their
stochastic variants into a general decision theoretic Markov
Decision Process (MDP) framework based on efficient factored
representations and dynamic Bayes nets. Not only is this
framework a beautiful generalization of search, but it also has
a very well developed theory (Puterman, 1994) for the existence
of decision theoretic optimal solutions and a variety of
dynamic programming algorithms for efficiently finding them.
(This is not to say that we have "solved" all MDP-related
problems but simply that we understand the problem well and that
we have made significant advances in tractably solving many
problems that can be cast as MDPs.)
- General Thoughts: I think these ideas present the
foundation for a theoretic revolution in AI, one that is being
spearheaded by a number of researchers in the field. The idea
is to recast all of the traditional search and learning problems
into a general theoretic framework, where each individual
problem becomes a specialization or set of assumptions over the
general model. Probably one of the most general models defined
to date is the partially observable Markov decision process
(POMDP), which can seemingly model any partially observable
stochastic sequential decision problem in AI - one where the
environment is a process having stochastic action outcomes,
reinforcement for certain behaviors, and stochastic observations
of its hidden state, i.e., every problem we encounter in
life. :)
Of course, the point to all of this theory and
modelling is not that we expect to create omniscient agents that
optimally solve all problems (or that this is even possible),
but rather that we have now correctly defined the model for
these problems. As Craig has often quoted Rich Sutton, "Don't
approximate the model, approximate the solution!"
And, now that we know how to efficiently model problems
in AI (due in part to papers such as the above), we have the
more concrete task of 1) finding structural regularities in
real-world domains that can be exploited for efficiency and 2)
finding tractable approximations (e.g. abstraction, hierarchy,
macro induction) of optimal solutions in which we have some
worst-case bound on reward loss. While this may not strike many
people as ground-breaking, it is important to note that an
understanding of these general models of AI is only something
that the field, as a whole, has come to realize within the past
decade - millenia after the first inquiry into the nature of
human thought and over 40 years since the birth of the field of
AI.