Dynamic Programming
What changed.
Cites (within this list): none
Cited by (within this list): Minsky 1961, Schmidhuber 2014, Sutton 1988, Sutton & Barto 1998
Ch. 2 Symbols and perceptrons 1956–74
Symbolic AI and the first neural networks (1956–1974)
Can intelligence be written as search and logic, and how much can a perceptron learn?
Key point
- The perceptron of 1958 and LISP of 1960 share a chapter. A learning machine written in probability and symbol processing written in recursive functions: the two later traditions each got their original text within two years.
- Samuel's checkers program (1959) left the sentence that it learned to play better than its author, and Widrow and Hoff's adaptive element (1960) described training by examples. Both are cited by the reinforcement-learning papers of chapter 3.
- Minsky and Papert's Perceptrons (1969) and Werbos's thesis (1974) could not be obtained for this version, which is why their cards carry no quotation. Whether the chapter ends in a "first winter" is examined with numbers on the winters page.
Bellman's Dynamic Programming (Princeton, 1957) opens the chapter. The book could not be read for this version and its card is empty, but Sutton (1988) in chapter 3 and the Sutton–Barto textbook (1998) in chapter 4 cite it in their reference lists. It is placed as the root of the reinforcement-learning lineage.
Rosenblatt's "The perceptron" appeared in Psychological Review in November 1958. What McCulloch and Pitts had written in symbolic logic, Rosenblatt rewrote in probability theory: for "a hypothetical nervous system, or machine, called a perceptron", a system of randomly connected units can learn to associate specific responses with specific stimuli. Its references list both Hebb 1949 and McCulloch–Pitts 1943; the two traditions that ran separately in chapter 1 meet here.
The next year Samuel's "Some Studies in Machine Learning Using the Game of Checkers" (July 1959, IBM Journal) applied two procedures to checkers, rote learning and a generalization procedure that adjusts the coefficients of a scoring polynomial. The sentence reads: enough work has been done to verify that a computer can be programmed to learn to play a better game of checkers than the person who wrote the program. Samuel cited Shannon's chess paper and Rosenblatt; Sutton (1988) and Watkins (1989) in chapter 3 cite Samuel. These four papers are the oldest solid lines of the reinforcement-learning lineage.
Two points fall in 1960. In the April Communications of the ACM, McCarthy's "Recursive functions of symbolic expressions" described LISP, a programming system for the IBM 704, through recursive functions of symbolic expressions and conditional expressions; the quotation comes from the author's own re-typeset copy, as the ACM printing could not be opened. Widrow and Hoff's "Adaptive switching circuits", a technical report of 30 June, proposed an adaptive neuron element whose gains are adjusted to minimize average error, trained by "showing it examples of inputs and desired outputs". Sutton 1988 and Barto 1983 in chapter 3 cite the report.
Minsky's "Steps toward Artificial Intelligence" (1961, Proceedings of the IRE) surveyed search, pattern recognition, learning, planning and induction in one article and is cited by Barto 1983. It appeared in the January 1961 issue.
Minsky and Papert's Perceptrons (1969, MIT Press) is the most-cited book in this chapter: Rumelhart 1986, Hopfield 1982, Ackley 1985, Cybenko 1989 and Minsky 1974 all cite it. It is known for showing geometrically which functions a single-layer perceptron cannot represent, but this version could not open the 1969 printing, so the card carries no quotation; the 1988 expanded edition is in an archive but its text and pagination may differ, and it was not used.
Language and backpropagation close the chapter. Winograd's "Understanding natural language" first appeared as MIT AI Technical Report 235 in January 1971 and in Cognitive Psychology in 1972: a system (SHRDLU) that handles English dialogue about a simple robot world with knowledge represented as procedures. Werbos's Harvard thesis "Beyond Regression" (1974) is known for applying chain-rule adjustment of multilayer-network weights to prediction problems in the behavioral sciences; no public copy exists, the card is empty, and the full text is in a 1994 Wiley volume. The priority of backpropagation is treated in a box in chapter 3.
The originals of symbolic AI
McCarthy's "Programs with Common Sense" was read at the National Physical Laboratory symposium at Teddington in November 1958 and printed in the 1959 proceedings. It proposed the "advice taker", a program that keeps its knowledge and heuristics as sentences of the predicate calculus and draws immediate conclusions from them, and defined a program as having common sense "if it automatically deduces for itself a sufficiently wide class of immediate consequences" of what it is told and already knows. The 1960 LISP paper and McCarthy–Hayes 1969 cite it. The same winter, Newell, Shaw and Simon's "Report on a general problem-solving program" (RAND P-1584, written 30 December 1958, revised 9 February 1959) described GPS, which separates the content of a problem from general solving techniques and applies means-ends analysis and planning through recursive goals; its references include the 1956 Logic Theorist. Robinson's resolution principle (January 1965, JACM) gave first-order logic a complete theorem-proving system with a single inference rule that merges substitution and truth-functional analysis; Winograd 1972 cites it. Zadeh's "Fuzzy sets" (June 1965, Information and Control) defined sets whose grades of membership run continuously between 0 and 1; this version read only the abstract, so the card is "partial". Weizenbaum's ELIZA (January 1966, CACM) imitated English conversation with decomposition and reassembly rules triggered by keywords, and separated the rules into editable "scripts"; Searle in chapter 3 and Generative Agents in chapter 7 cite it.
A* (Hart, Nilsson and Raphael) (July 1968, IEEE Trans. SSC) set up a formal framework in which an estimate of the remaining path cost guides graph search, and proved that when the estimate never exceeds the true cost (is admissible), A* expands no more nodes than any admissible algorithm using the same information (ties apart). Its references include Samuel 1959; Pearl 1988 in chapter 3 and Tree of Thoughts in chapter 7 cite it. McCarthy and Hayes, "Some Philosophical Problems from the Standpoint of Artificial Intelligence" (1969, Machine Intelligence 4) formalized situations, fluents and actions in first-order logic and named the "frame problem"; its references cite McCarthy 1959, Minsky 1961, Shannon 1950 and Turing 1950, the chapter's most connected paper to chapter 1. STRIPS (Fikes and Nilsson) appeared first as SRI Technical Note 43 in October 1970 and in Artificial Intelligence in 1971: a problem solver that represents world models as sets of predicate-calculus formulas and finds operator sequences by means-ends analysis. It cites McCarthy–Hayes, and SayCan and Inner Monologue in chapter 7 cite it as the original text of planning.
The chapter ends with the Lighthill report. "Artificial Intelligence: A General Survey", written for the UK Science Research Council in July 1972 and published in 1973 with replies, divided AI research into advanced automation (A), central-nervous-system studies (C) and the bridge of building robots (B), and wrote: "In no part of the field have the discoveries made so far produced the major impact that was then promised." It named the combinatorial explosion as the main cause and mentions Winograd 1972 in the text. That the report cut British AI support is widely accepted; as the winters page says, no yearly amounts are in the sources.
What was and was not checked
Of the 18 papers, the original printings of Rosenblatt, Samuel, Widrow–Hoff (WESCON convention record), Robinson, Weizenbaum and A* were read, GPS in the RAND report scan, McCarthy 1959 and 1969 in the author's re-typeset copies, Zadeh in the abstract only, STRIPS in the technical note and the journal pages; McCarthy in the author's re-typeset copy, Winograd in the technical-report version. Bellman, Minsky–Papert and Werbos were not read. Among the period's candidates, Newell, Shaw and Simon's Logic Theorist (1956), the Dartmouth proposal (1955), Selfridge's Pandemonium (1959), the multilayer learning of Ivakhnenko (1965) and Amari (1967), and Quillian's semantic memory (1968) did not pass the two-textbook rule.
Lineage
Paper list (18)
Programs with Common Sense
The advice taker is a proposed program for solving problems by manipulating sentences in formal languages.p. 1 (author's web PDF)
What changed. Proposed the 'advice taker', a program that represents its knowledge and heuristics as sentences in a formal language (a part of the predicate calculus) and draws immediate conclusions from them, so that its behavior can be improved by telling it statements. Defined a program as having common sense if it automatically deduces a sufficiently wide class of immediate consequences of what it is told and already knows.
Cites (within this list): none
Cited by (within this list): McCarthy 1960, McCarthy & Hayes 1969, Minsky 1961
The perceptron: A probabilistic model for information storage and organization in the brain
The theory has been developed for a hypothetical nervous system, or machine, called a perceptron.p. 387
What changed. Presents a theory, formulated with probability theory rather than symbolic logic, of how information is stored and how it affects recognition, using a hypothetical nervous system called a perceptron. Concludes that a system of randomly connected units can learn to associate specific responses with specific stimuli.
Cites (within this list): Hebb 1949, McCulloch & Pitts 1943
Cited by (within this list): Samuel 1959, Schmidhuber 2014
Report on a general problem-solving program
GPS, the program described in this paper, contributes to the theory of problem solving by embodying two very general systems of heuristics — means-ends analysis and planning — within an organization that allows them to be applied to varying subject matters.p. 2
What changed. Describes GPS-I, a computer program that separates problem content (a task environment of objects and operators) from general problem-solving techniques, and applies two general heuristics, means-ends analysis and planning, through recursive goals. Examples are given in symbolic logic and trigonometric identities.
Cites (within this list): none
Cited by (within this list): McCarthy & Hayes 1969, Minsky 1961, Yao et al. 2023
Some Studies in Machine Learning Using the Game of Checkers
Enough work has been done to verify the fact that a computer can be programmed so that it will learn to play a better game of checkers than can be played by the person who wrote the program.p. 211
What changed. Investigates two machine-learning procedures, rote learning and a generalization procedure that adjusts the terms of a scoring polynomial, using checkers. Reports that a program given the rules, a sense of direction, and an incomplete list of parameters learned to play better than its author in 8 to 10 hours of machine-playing time.
Cites (within this list): Rosenblatt 1958, Shannon 1949
Cited by (within this list): Barto et al. 1983, Hart et al. 1968, Hochreiter 1991, Minsky 1961, Schmidhuber 2014, Sutton 1988, Sutton & Barto 1998, Tesauro 1995, Watkins 1989, Widrow & Hoff 1960
Recursive functions of symbolic expressions and their computation by machine, Part I
A programming system called LISP (for LISt Processor) has been developed for the IBM 704 computer by the Artificial Intelligence group at M.I.T.p. 1 (author's version)
What changed. Describes LISP, a programming system for the IBM 704, through a formalism of recursive functions of symbolic expressions (S-expressions and S-functions) using conditional expressions. Presents the universal S-function apply and the list-structure representation of S-expressions in memory.
Cites (within this list): McCarthy 1958
Cited by (within this list): Minsky 1961, Newell & Simon 1975
Adaptive switching circuits
An approach to such problems is taken in this paper which does not require an explicit use of the truth table.p. 96
What changed. Proposes adaptive switching circuits designed to minimize the average number of errors, using an adaptive neuron element whose gains are set during a training procedure by performance feedback. The designer trains the system by showing it examples of inputs and desired outputs.
Cites (within this list): Samuel 1959, Shannon 1949
Cited by (within this list): Barto et al. 1983, Sutton 1988, Sutton & Barto 1998
Steps toward Artificial Intelligence
Summary—The problems of heuristic programming—of making computers solve really difficult problems—are divided into five main areas: Search, Pattern-Recognition, Learning, Planning, and Induction.p. 8
What changed. Organized the problems of heuristic programming into five areas (Search, Pattern-Recognition, Learning, Planning, and Induction) and reviewed the problem-solving programs and literature of the time under that scheme. The paper argues that pattern recognition, learning, and planning reduce the search a problem-solving machine must otherwise perform.
Cites (within this list): Bellman 1957, Hebb 1949, McCarthy 1958, McCarthy 1960, Newell et al. 1959, Samuel 1959, Turing 1950, Wiener 1948
Cited by (within this list): Barto et al. 1983, McCarthy & Hayes 1969, Schmidhuber 2014, Sutton & Barto 1998
A Machine-Oriented Logic Based on the Resolution Principle
Presented in this paper is a formulation of first-order logic which is specifically designed for use as the basic theoretical instrument of a computer theorem-proving program.p. 23
What changed. Presented a system of first-order logic with a single inference principle, the resolution principle, which combines substitution and truth-functional analysis into one step, and proved the system complete. Discussed search principles for designing efficient proof procedures that use resolution.
Cites (within this list): none
Cited by (within this list): Winograd 1971
Fuzzy sets
A fuzzy set is a class of objects with a continuum of grades of membership.page unknown (abstract as shown on the publisher page)
What changed. Defined a fuzzy set as a class of objects with a continuum of grades of membership, characterized by a membership function with values between zero and one. Extended inclusion, union, intersection, complement, relation and convexity to such sets and proved a separation theorem for convex fuzzy sets that does not require disjointness.
Cites (within this list): none
Cited by (within this list): none
ELIZA—a computer program for the study of natural language communication between man and machine
ELIZA is a program which makes natural language conversation with a computer possible.p. 36
What changed. Described ELIZA, a program on MIT's MAC time-sharing system in which input sentences are analyzed by decomposition rules triggered by key words and responses are generated by reassembly rules, with the rules supplied as editable 'scripts'. Discussed identification of key words, minimal context, transformations, responses without key words, and psychological issues of the approach.
Cites (within this list): none
Cited by (within this list): Park et al. 2023, Searle 1980, Winograd 1971
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
This paper describes how heuristic information from the problem domain can be incorporated into a formal mathematical theory of graph searching and demonstrates an optimality property of a class of search strategies.p. 100
What changed. Gave a formal framework in which an estimate of remaining path cost drawn from the problem domain guides graph search, defining the algorithm A* and conditions under which it is admissible. Showed that A* expands no more nodes than any admissible algorithm using no more information from the problem domain (apart from ties).
Cites (within this list): Samuel 1959
Cited by (within this list): Pearl 1988, Yao et al. 2023
Some Philosophical Problems from the Standpoint of Artificial Intelligence
A computer program capable of acting intelligently in the world must have a general representation of the world in terms of which its inputs are interpreted.p. 1 (author's web PDF)
What changed. Argued that building an intelligent program requires an epistemologically adequate representation of the world, and explained 'can', 'causes' and 'knows' using a model of interacting automata. Formalised situations, fluents, actions, strategies and knowledge in first-order logic so that it can be proved that a strategy achieves a goal, and discussed the difficulties of this formalism, including the frame problem.
Cites (within this list): McCarthy 1958, Minsky 1961, Newell et al. 1959, Shannon 1949, Turing 1950
Cited by (within this list): Amodei et al. 2016, Fikes & Nilsson 1970, Pearl 1988
Perceptrons: An Introduction to Computational Geometry
What changed.
Cites (within this list): none
Cited by (within this list): Ackley et al. 1985, Cybenko 1989, Hochreiter 1991, Hopfield 1982, Hornik et al. 1988, Minsky 1974, Rumelhart et al. 1986, Schmidhuber 2014
STRIPS: A new approach to the application of theorem proving to problem solving
This paper describes a new problem-solving program called STRIPS (STanford Research Institute Problem Solver).p. 189
What changed. Described STRIPS, a problem solver that searches a space of world models, each a collection of first-order predicate calculus formulas, for a sequence of operators reaching a model in which the goal formula can be proven. It uses a resolution theorem prover to answer questions about particular models and means-ends analysis to guide the search.
Cites (within this list): McCarthy & Hayes 1969
Cited by (within this list): Ahn et al. 2022, Huang et al. 2022
Understanding natural language
This paper describes a system for the computer understanding of English.p. 3 (TR-235, Abstract)
What changed. Describes a system that answers questions, executes commands, and accepts information in English dialog about a simple robot world, using semantic information and context. Represents knowledge as procedures, with special procedural languages for grammar, semantics, and deductive logic.
Cites (within this list): Robinson 1965, Weizenbaum 1966
Cited by (within this list): Ahn et al. 2022, Lighthill 1973
Artificial Intelligence: A General Survey
In no part of the field have the discoveries made so far produced the major impact that was then promised.page unknown (section 3 'Past disappointments')
What changed. Reviewed AI research for the Science Research Council by dividing it into Advanced Automation (A), Computer-based Central Nervous System studies (C) and a bridge category of Building Robots (B), and reported disappointment with past progress, attributing failures in large part to the combinatorial explosion. Expected work in categories A and C to continue and the bridge category B to fail to reach its aims, leading to a fission of the field.
Cites (within this list): Winograd 1971
Cited by (within this list): none
Beyond Regression: New Tools for Prediction and Analysis in the Behavioral Sciences
What changed.
Cites (within this list): none
Cited by (within this list): Ciresan et al. 2010, Ciresan et al. 2012, LeCun et al. 2015, Schmidhuber 2014, Williams 1992