(The below text version of the notes is for search purposes and convenience. See the PDF version for proper formatting such as bold, italics, etc., and graphics where applicable. Copyright: 2022 Retraice, Inc.)
AIMA4e Annotations
A companion to the great white brick.
As of November 26, 2022
(Start date: November 21, 2022.)
[1]retraice.com
Version notes:
[2]Retraice ([3]2022/11/21) (Re57), first draft, covered Preface, Sections I, II; [4]Retraice ([5]2022/11/22) (Re58), no footnotes, covered Sections III, IV; [6]Retraice ([7]2022/11/22) (Re58) again, moved some notes from Re57 and Re58 notes to footnotes here; [8]Retraice ([9]2022/11/23) (Re59), covered Sections V, VI, VII; [10]Retraice ([11]2022/11/24) (Re60), covered Appendix A; [12]Retraice ([13]2022/11/25) (Re61), covered Appendix B.
PREFACE
The discipline: artificial intelligence,[15]^2 "the study of agents that receive percepts from the environment and perform actions." (vii)
Aspects of the phenomenon:
I INTELLIGENCE --"Artificial Intelligence"
1 Introduction
Definitions, foundations, history, philosophy, state of the art, risks-benefits.
2 Agents
Environments, `good' behavior, agent structure and types.
II SOLVING--"Problem-solving"
3 Searching:
Looking ahead to find a sequence
Algorithms, strategies, informed/heuristic[16]^3 strategies.
4 Complex Environments:
More realistic environments
Local search, optimization, continuous spaces, nondeterministic actions, partially observable env.s, online search and unknown env.s.
5 Adversarial Games:
Other agents competing against us
Theory, optimal decisions, alpha-beta tree search, Monte Carlo tree search, stochastic g.s, partially observable g.s, limitations.
6 Constraints:
States as domains, solutions as allowable combinations of states
Constraint propagation, inference, backtracking search, local search, structure of problems
III THINKING--"Knowledge, reasoning, and planning"
7 "Logical Agents":
Forming representations and reasoning before acting
Knowledge-based agents; representing[17]^4 worlds; logic, world models and `possible worlds';[18]^5 logic without objects.
8 "First-Order Logic":
A formal language for objects and their relations
`Ontological commitment' (what is assumed about reality); syntax, semantics; knowledge engineering (building formal representations of important[19]^6 objects and relations in a domain).
9 First-Order Inference:
Reasoning about objects and their relations
Algorithms to answer any 1st-order logic question.
10 "Knowledge Representation":
Representing the real world for problem solving
What content to put into a knowledge base.
Knowledge representation languages and their uses (315):
* First-order logic: reasoning about a world of objects and relations;
* Hierarchical task networks: for reasoning about plans (chpt. 11);
* Bayesian networks: for reasoning with uncertainty (chpt. 13);
* Markov models: for reasoning over time (chpt. 17);
* Deep neural networks: for reasoning about images, sounds, other data (chpt. 21).
11 "Automated Planning":
Hierarchical task networks
Planning for spacecraft, factories, military campaigns; representing actions and states; efficient algorithms and heuristics.
IV UNCERTAINTY--"Uncertain knowledge and reasoning"
12 "Quantifying Uncertainty":
An answer to the laziness and ignorance that kill formal logic
Causes of uncertainty are environment types (partially observable,[20]^7 nondeterministic, adversarial[21]^8 ); belief state grows big and unlikely fast (384); agents still need a way to act; absolute certainty is impossible;[22]^9 it comes down to importance, likelihood and degree of success (385-386).
Logic fails because laziness and ignorance; probability theory solves the qualification problem by summarizing the uncertainty.[23]^10
* Laziness: too much work to list everything, or use such a list;
* Ignorance: (theoretical) there are no complete theories; (practical) we can never run all the tests.
13 "Probabilistic Reasoning" [big]:
Bayesian networks
For reasoning with uncertainty by representing causal independence (398) and conditional independence (401) relationships to simplify probabilistic representations of the world.
14 "Probabilistic Reasoning Over Time":
Comprehending the uncertain past, present and future
Belief state[24]^11 plus transition model yields prediction (chpt 4, 7, 11); percepts and sensor model yield updated belief state; add probability theory to switch from possible states to probable states.[25]^12
15 "Probabilistic Programming":
Universal formal languages to represent any computable probability model, and they come with algorithms
Using formal logic and traditional programming languages to represent probabilistic information.
16 "Making Simple Decisions":
Agents getting what they want in an uncertain world--as much as possible, on average
Beliefs, desires; utility theory; utility functions; decision networks; the value of information (547);[26]^13 this chapter is concerned with one-shot or episodic decisions problems (as opposed to sequential) (cf. 562, below).
17 "Making Complex Decisions":
What to do today given decisions to be made tomorrow
Sequential decision problems (as opposed to one-shot episodic, cf. above): the agent's utility depends on a sequence of decisions in stochastic (explicitly probabilistic (45)) and partially observable environments. Markov models (563; cf. 463) for reasoning over time (chpt. 17).
18 "Multiagent Decision Making" [big]:
When there's more than one agent in the environment
The nature of such environments and the strategies for problem-solving depend on the relationships between agents: non-cooperative and cooperative game theory; collective decision-making.
V LEARNING--"Machine learning"
19 "Learning From Examples" [big]:
Improving behavior by observing the present (past?) and predicting the future
Learning is improving performance (behavior) after making observations.[27]^14
If the agent is a computer: Machine learning: "a computer observes some data, builds a model based on the data, and uses the model as both a hypothesis about the world and a piece of software that can solve problems." (651)
Subsections:
* supervised learning;
* learning decision trees;
* model selection and optimization;
* theory of learning;
* linear regression (finding the best-fit line, i.e. predicting future' [dependent] values based on plottingpast' [independent] values), classification;[28]^15
* nonparametric models (which retain all the examples, aka instance-based' ormemory-based' learning, which is more true to large datasets [scalable?] than parametric, which summarize, and then discard, training data in fixed numbers of parameters),
* ensemble learning (using multiple hypotheses instead of one, and averaging or voting--base' models are combined into anensemble' model);
* ML system development, the practice (software engineering and design patters in ML ops).
20 "Learning Probabilistic Models":
View `learning' as "uncertain reasoning from observations" and model the world accordingly
Agents can't use probability and decision theories until they learn them from experience: treat learning itself as an inference process in a probabilistic world. Use Bayesian networks. Key concepts: data and hypotheses. "Here, the data are evidence ...instantiations of some or all of the random variables describing the domain."[29]^16
21 "Deep Learning":
represent hypotheses as "complex algebraic circuits with tunable connection strengths"
The circuits are orginzed into layers, a multi-step computation path. Ideal for recognizing, translating and generating images (including objects in images) and speech; `neural networks'.
From chpt. 10 on knowledge rep. languages, above notes: "deep neural networks: for reasoning about images, sounds, other data."
Think: gradient descent, back-propagation, convolutional neural networks.
22 "Reinforcement Learning":
Learning from experiences of reward and punishment instead of correct examples from a supervisor
Passive and active RL., Q-learning, apprenticeships and inverse RL.
Cf. Reward is Enough, May 2021: [30]https://www.deepmind.com/publications/reward-is-enough
VI INTERACTING--"Communicating, perceiving, and acting"
23 "Natural Language Processing":
Communicating with humans and learning from what they've written
Language model: "a probability distribution describing the likelihood of any string." (824)
N-grams, grammar, syntax, semantics, parsing, vagueness, ambiguity, quantification.
24 Deep Learning NLP:
Using neural nets on natural language to effectively handle the complexity
"[R]epresenting words as points in a high-dimensional space." RNNs for "long-distance context."
Cf. Attention Is All You Need, 2017: [31]https://arxiv.org/abs/1706.03762 and AIMA4e p. 868, transformer architecture, self-attention.
25 "Computer Vision":
Connecting AI to cameras
Photons provide a lot of valuable information to agents--too much information.
Surveillance cameras--good and bad; cars. Lots of machines do better if they can see.
From the Preface: Robotics and vision: "not ...independently defined problems"..."[things] in the service of achieving goals."
26 "Robotics":
Connecting AI to sensors, effectors and actuators
To enable movement in-and of--the physical world. Cars, spacecraft, surgeons, submarines, delivery bots.
From the Preface: Robotics and vision: "not ...independently defined problems"..."[things] in the service of achieving goals."
VII CONCLUSIONS--"Conclusions"
27 "Philosophy, Ethics, and Safety of AI":
What is AI? What should we do with it? What might it do with us?
Trust--of systems, humans, ourselves, each other.
The human use of human beings. Usefulness of human beings at all?
Medicine. War.
28 "The Future of AI":
Our tools will improve dramatically; our ends might remain the same.
Our preferences, our tools, our architectures. They're ours, for now.
Minimize the negative impacts, don't maximize the positive?
A: MATH--"Appendix A: Mathematical Background"
A.1 [SOLVING per §II]: "Complexity Analysis and O() Notation":
Problem and algorithm analysis (computer science math)
Asymptotic and worst-case analysis of algorithms:
Approximately predicting the performance (and efficiency) of algorithms based on their steps in worst-case (or best or average) and infinite-case (asymptotic) input scenarios, in order to avoid actually implementing them, and to enable comparison of algorithms.[32]^17
Abstract over the input, and then the implementation, to find the key factors (string length; lines of code) that make the space/time difference. Ignore constants, usually; focus on the key variables.
Complexity analysis of problems:
Polynomial time O(n^k) problems, class P.
Non-polynomial time problems.
Nondeterministic polynomial problems: class NP. A problem with some algorithm that can guess and check a solution in polynomial time.
A.2 [THINKING per §III]: "Vectors, Matrices, and Linear Algebra":
Line equation probing (`unknowns' math)
A vector is a pile of numbers (or unknowns or variables), a matrix is a pile of piles of numbers; some of the questions we can ask are linear problems'[33]^18 (think prediction, interpolation, extrapolation), and algebra (finding unknowns by repairing [or completion] and balancing) on these things islinear algebra'.
Vectors: Ordered sequences of values--represent something in the real world as just a set of values measuring specific aspects of that thing.[34]^19
Linear algebra: Doing algebra (finding unknowns by repairing [or completion] and balancing) on systems of equations of lines in planes instead of single equations and equations of points on lines (algebra). Think: finding line or plane intersections or bounded regions (based on inequalities instead of equations),[35]^20 and changing lines without affecting intersections[36]^21 --that sort of thing.
Thinking about higher dimensional objects: left-right x, up-down y, forward-backward z, wrist-watch value (time) t, color spectrum p, texture q, weight r, etc.
A.3 [UNCERTAINTY per §IV] "Probability Distributions":
Quantifying `probably' (uncertainty math)
Probability is a controversial concept.[37]^22
Experiments yield outcomes; a set of outcomes is an event; the set of all possible outcomes is the sample space.[38]^23
"A `probability' is a measure over a set of events...." A probability model: sample space plus the probability measure for each outcome.
Cf. `random variable' note above.
B: CODE--"Appendix B: Notes on Languages and Algorithms"
B.1 "Defining Languages with Backus-Naur Form (BNF)":
Defining formal languages
Languages:
* propositional logic;
* first-order logic;
* English;
Formal language: strings, symbols, infinite strings, grammar, Chomsky hierarchy (context free).
BNF elements:
* Terminals: symbols / words;
* Non terminals that categorize: NounPhrase;
* Start symbol: Sentence (English) or Expr (math) or Program (computing);
* Rewrite rules: Sentence -> Expr Operator Expr | (Expr) | Number.
Think compilers:[39]^24 source language to target language, first syntax then semantics, reconstruct source logic in target logic.
Syntax analysis module: tokenizing + parsing (rule matching);
Code generation module: data translation and command translation.
Think also: (universal?) generative grammar, generating new strings, chat bots, GPT-3, Deep Blue, AlphaCode, Turing test.
B.2 "Describing Algorithms with Pseudocode":
Code formatting and conventions
persistent' variable as memory, which can be implemented as an object, or afunctional closure', cf braces and `end'; __
References
Aleksandrov, A. D., Kolmogorov, A. N., & Lavrent'ev, M. A. (1969). Mathematics: Its Content, Methods and Meaning (3 Volumes in One). Dover, 1999 reprint ed. ISBN: 0486409163. Searches:
[40]https://www.amazon.com/s?k=0486409163
[41]https://www.google.com/search?q=isbn+0486409163
[42]https://lccn.loc.gov/99033023
Anderson, R. F. V. (1986). Introduction to Linear Algebra. Holt, Rinehard and Winston. ISBN: 003921835X. Searches:
[43]https://www.amazon.com/s?k=003921835X
[44]https://www.google.com/search?q=isbn+003921835X
Bittinger, M. L., & Ellenbogen, D. J. (2006). Intermediate Algebra: Concepts and Applications. Addison-Wesley, 7th ed. ISBN: 0321233867. Searches:
[45]https://www.amazon.com/s?k=0321233867
[46]https://www.google.com/search?q=isbn+0321233867
[47]https://lccn.loc.gov/2004062480
Bulmer, M. G. (1967). Principles of Statistics. Dover, 1979 reprint ed. ISBN: 0486637603. Searches:
[48]https://www.amazon.com/s?k=0486637603
[49]https://www.google.com/search?q=isbn+0486637603
[50]https://lccn.loc.gov/78072991
Crawford, K. (2021). Atlas of AI: Power, Politics, and the Planetary Costs of Artificial Intelligence. Yale University Press. ISBN: 978-0300209570. Searches:
[51]https://www.amazon.com/s?k=9780300209570
[52]https://www.google.com/search?q=isbn+9780300209570
[53]https://lccn.loc.gov/2020947842
Frankfurt, H. G. (1988). The Importance of What We Care About. Cambridge. ISBN: 978-0521336116. Searches:
[54]https://www.amazon.com/s?k=978-0521336116
[55]https://www.google.com/search?q=isbn+978-0521336116
[56]https://lccn.loc.gov/87026941
Gerrish, S. (2018). How Smart Machines Think. The MIT Press. ISBN: 978-0262038409. Searches:
[57]https://www.amazon.com/s?k=9780262038409
[58]https://www.google.com/search?q=isbn+9780262038409
[59]https://lccn.loc.gov/2017059862
Horwich, P. (1982). Probability and Evidence. Cambridge. First published 1982; first paperback 2011; this Cambridge Philosophy Classics edition 2016. ISBN: 978-1316507018. Searches:
[60]https://www.amazon.com/s?k=978-1316507018
[61]https://www.google.com/search?q=isbn+978-1316507018
[62]https://lccn.loc.gov/2015049717
Kahneman, D. (2011). Thinking, Fast and Slow. Farrar, Straus and Giroux. ISBN: 978-0374533557. Searches:
[63]https://www.amazon.com/s?k=978-0374533557
[64]https://www.google.com/search?q=isbn+978-0374533557
[65]https://lccn.loc.gov/2012533187
Keynes, J. M. (1920). A Treatise on Probability: The Connection Between Philosophy and the History of Science. Wildside Press. ISBN: 978-1434406965. Searches:
[66]https://www.amazon.com/s?k=9781434406965
[67]https://www.google.com/search?q=isbn+9781434406965
[68]https://lccn.loc.gov/2004041359
Kramer, E. E. (1970). The Nature and Growth of Modern Mathematics. Hawthorn Books. No ISBN. Searches:
[69]https://www.amazon.com/s?k=kramer+nature+and+growth+of+modern+mathematics
[70]https://www.google.com/search?q=kramer+nature+and+growth+of+modern+mathematics
[71]https://lccn.loc.gov/73091317
Larson, R., Hostetler, R. P., & Edwards, B. H. (2005). College Algebra: A Graphing Approach. Houghton Mifflin, 4th ed. ISBN: 0618394370. Searches:
[72]https://www.amazon.com/s?k=0618394370
[73]https://www.google.com/search?q=isbn+0618394370
[74]https://lccn.loc.gov/00104769
Macphail, E. M. (1982). Brain and Intelligence in Vertebrates. Oxford. ISBN 0198545517. Searches:
[75]https://www.amazon.com/s?k=0198545517
[76]https://www.google.com/search?q=isbn+0198545517
[77]https://lccn.loc.gov/82166301
Manber, U. (1989). Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1st ed. ISBN: 0201120372. Searches:
[78]https://www.amazon.com/s?k=0201120372
[79]https://www.google.com/search?q=isbn+0201120372
[80]https://lccn.loc.gov/88002186
Nisan, N., & Schocken, S. (2005). The Elements of Computing Systems: Building a Modern Computer from First Principles. MIT. ISBN: 978-0262640688. Searches:
[81]https://www.amazon.com/s?k=978-0262640688
[82]https://www.google.com/search?q=isbn+978-0262640688
[83]https://lccn.loc.gov/2005042807
Okasha, S. (2002). Philosophy of Science: A Very Short Introduction. Oxford University Press. ISBN: 0192802836. Searches:
[84]https://www.amazon.com/s?k=0192802836
[85]https://www.google.com/search?q=isbn+0192802836
[86]https://lccn.loc.gov/2002510456
Retraice (2020/09/07). Re1: Three Kinds of Intelligence. retraice.com.
[87]https://www.retraice.com/segments/re1 Retrieved 22nd Sep. 2020.
Retraice (2020/11/02). Re10: Living to Guess Another Day. retraice.com.
[88]https://www.retraice.com/segments/re10 Retrieved 2nd Nov. 2020.
Retraice (2020/11/10). Re13: The Care Factor. retraice.com.
[89]https://www.retraice.com/segments/re13 Retrieved 10th Nov. 2020.
Retraice (2020/11/25). Re15: Trust and Sources. retraice.com.
[90]https://www.retraice.com/segments/re15 Retrieved 28th Feb. 2022.
Retraice (2022/03/07). Re18: Plan of Attack. retraice.com.
[91]https://www.retraice.com/segments/re18 Retrieved 25th Mar. 2022.
Retraice (2022/10/10). Re19: Nature Is Not F-ing Around. retraice.com.
[92]https://www.retraice.com/segments/re19 Retrieved 12th Oct. 2022.
Retraice (2022/10/19). Re23: You Need a World Model. retraice.com.
[93]https://www.retraice.com/segments/re23 Retrieved 20th Oct. 2022.
Retraice (2022/10/23). Re27: Now That's a World Model - WM4. retraice.com.
[94]https://www.retraice.com/segments/re27 Retrieved 24th Oct. 2022.
Retraice (2022/10/31). Re36: Notes on Conspiracy. retraice.com.
[95]https://www.retraice.com/segments/re36 Retrieved 4th Nov. 2022.
Retraice (2022/11/12). Re48: From Drugs to Mao to Money. retraice.com.
[96]https://www.retraice.com/segments/re48 Retrieved 14th Nov. 2022.
Retraice (2022/11/16). Re52: Big Questions About AI. retraice.com.
[97]https://www.retraice.com/segments/re52 Retrieved 17th Nov. 2022.
Retraice (2022/11/21). Re57: AI, Agents, Problem-solving, Searching, Environments, Games (AIMA4e chpts. 1-6). retraice.com.
[98]https://www.retraice.com/segments/re57 Retrieved 22nd Nov. 2022.
Retraice (2022/11/22). Re58: Thinking and Uncertainty (AIMA4e chpts. 7-18). retraice.com.
[99]https://www.retraice.com/segments/re58 Retrieved 23rd Nov. 2022.
Retraice (2022/11/23). Re59: Learning, Interacting, Conclusions (AIMA4e chpts. 19-28). retraice.com.
[100]https://www.retraice.com/segments/re59 Retrieved 24th Nov. 2022.
Retraice (2022/11/24). Re60: Complexity, Linear Algebra, Probability (AIMA4e Appendix A). retraice.com.
[101]https://www.retraice.com/segments/re60 Retrieved 25th Nov. 2022.
Retraice (2022/11/25). Re61: Formal Languages, Pseudocode (AIMA4e Appendix B). retraice.com.
[102]https://www.retraice.com/segments/re61 Retrieved 26th Nov. 2022.
Russell, B. (1948). Human Knowledge: Its Scope and Limits. Routledge. First published in 1948. This edition 1992. ISBN: 0415083028. Searches:
[103]https://archive.org/search.php?query=Human%20Knowledge%3A%20Its%20Scope%20and%20Limits
[104]https://www.amazon.com/s?k=0415083028
[105]https://www.google.com/search?q=isbn+0415083028
[106]https://lccn.loc.gov/94209784
Russell, B. (1959). My Philosophical Development. Wnwin Brothers. No ISBN.
[107]https://archive.org/details/myphilosophicald0000russ/page/n11/mode/2up Retrieved 06 Jun. 2021. Searches:
[108]https://www.amazon.com/s?k=Russell+My+Philosophical+Development
[109]https://www.google.com/search?q=Russell+My+Philosophical+Development
[110]https://lccn.loc.gov/59003496
Thompson, K. (1984). Reflections on trusting trust. Communications of the ACM, 27(8), 761-763. Aug. 1984.
[111]https://doi.org/10.1145/358198.358210 Also available at:
[112]https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_ReflectionsonTrustingTrust.pdf Retrieved 4th Dec. 2020.
Vallee, J. (1979). Messengers of Deception: UFO Contacts and Cults. And/Or Press. ISBN: 0915904381. Different edition and searches:
[113]https://archive.org/details/MessengersOfDeceptionUFOContactsAndCultsJacquesValle1979/mode/2up
[114]https://www.amazon.com/s?k=0915904381
[115]https://www.google.com/search?q=isbn+0915904381
[116]https://catalog.loc.gov/vwebv/search?searchArg=0915904381
References