(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 25, 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.
PREFACE
The discipline: artificial intelligence,[13]^2 "the study of agents that receive percepts from the environment and perform actions." (vii)
Aspects of the phenomenon:
I INTELLIGENCE --"Artificial Intelligence"
1 Intro:
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[14]^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 Constraint Satisfaction Problems:
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[15]^4 worlds; logic, world models and `possible worlds';[16]^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[17]^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,[18]^7 nondeterministic, adversarial[19]^8 ); belief state grows big and unlikely fast (384); agents still need a way to act; absolute certainty is impossible;[20]^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.[21]^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.
[22]^11
Belief state 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.[23]^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);[24]^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.[25]^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;[26]^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."[27]^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: [28]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 for Natural Language Processing:
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: [29]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.[30]^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'[31]^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.[32]^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),[33]^20 and changing lines without affecting intersections[34]^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.[35]^22
Experiments yield outcomes; a set of outcomes is an event; the set of all possible outcomes is the sample space.[36]^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"
__
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:
[37]https://www.amazon.com/s?k=0486409163
[38]https://www.google.com/search?q=isbn+0486409163
[39]https://lccn.loc.gov/99033023
Anderson, R. F. V. (1986). Introduction to Linear Algebra. Holt, Rinehard and Winston. ISBN: 003921835X. Searches:
[40]https://www.amazon.com/s?k=003921835X
[41]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:
[42]https://www.amazon.com/s?k=0321233867
[43]https://www.google.com/search?q=isbn+0321233867
[44]https://lccn.loc.gov/2004062480
Bulmer, M. G. (1967). Principles of Statistics. Dover, 1979 reprint ed. ISBN: 0486637603. Searches:
[45]https://www.amazon.com/s?k=0486637603
[46]https://www.google.com/search?q=isbn+0486637603
[47]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:
[48]https://www.amazon.com/s?k=9780300209570
[49]https://www.google.com/search?q=isbn+9780300209570
[50]https://lccn.loc.gov/2020947842
Frankfurt, H. G. (1988). The Importance of What We Care About. Cambridge. ISBN: 978-0521336116. Searches:
[51]https://www.amazon.com/s?k=978-0521336116
[52]https://www.google.com/search?q=isbn+978-0521336116
[53]https://lccn.loc.gov/87026941
Gerrish, S. (2018). How Smart Machines Think. The MIT Press. ISBN: 978-0262038409. Searches:
[54]https://www.amazon.com/s?k=9780262038409
[55]https://www.google.com/search?q=isbn+9780262038409
[56]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:
[57]https://www.amazon.com/s?k=978-1316507018
[58]https://www.google.com/search?q=isbn+978-1316507018
[59]https://lccn.loc.gov/2015049717
Kahneman, D. (2011). Thinking, Fast and Slow. Farrar, Straus and Giroux. ISBN: 978-0374533557. Searches:
[60]https://www.amazon.com/s?k=978-0374533557
[61]https://www.google.com/search?q=isbn+978-0374533557
[62]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:
[63]https://www.amazon.com/s?k=9781434406965
[64]https://www.google.com/search?q=isbn+9781434406965
[65]https://lccn.loc.gov/2004041359
Kramer, E. E. (1970). The Nature and Growth of Modern Mathematics. Hawthorn Books. No ISBN. Searches:
[66]https://www.amazon.com/s?k=kramer+nature+and+growth+of+modern+mathematics
[67]https://www.google.com/search?q=kramer+nature+and+growth+of+modern+mathematics
[68]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:
[69]https://www.amazon.com/s?k=0618394370
[70]https://www.google.com/search?q=isbn+0618394370
[71]https://lccn.loc.gov/00104769
Macphail, E. M. (1982). Brain and Intelligence in Vertebrates. Oxford. ISBN 0198545517. Searches:
[72]https://www.amazon.com/s?k=0198545517
[73]https://www.google.com/search?q=isbn+0198545517
[74]https://lccn.loc.gov/82166301
Manber, U. (1989). Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1st ed. ISBN: 0201120372. Searches:
[75]https://www.amazon.com/s?k=0201120372
[76]https://www.google.com/search?q=isbn+0201120372
[77]https://lccn.loc.gov/88002186
Okasha, S. (2002). Philosophy of Science: A Very Short Introduction. Oxford University Press. ISBN: 0192802836. Searches:
[78]https://www.amazon.com/s?k=0192802836
[79]https://www.google.com/search?q=isbn+0192802836
[80]https://lccn.loc.gov/2002510456
Retraice (2020/09/07). Re1: Three Kinds of Intelligence. retraice.com.
[81]https://www.retraice.com/segments/re1 Retrieved 22nd Sep. 2020.
Retraice (2020/11/02). Re10: Living to Guess Another Day. retraice.com.
[82]https://www.retraice.com/segments/re10 Retrieved 2nd Nov. 2020.
Retraice (2020/11/10). Re13: The Care Factor. retraice.com.
[83]https://www.retraice.com/segments/re13 Retrieved 10th Nov. 2020.
Retraice (2020/11/25). Re15: Trust and Sources. retraice.com.
[84]https://www.retraice.com/segments/re15 Retrieved 28th Feb. 2022.
Retraice (2022/03/07). Re18: Plan of Attack. retraice.com.
[85]https://www.retraice.com/segments/re18 Retrieved 25th Mar. 2022.
Retraice (2022/10/10). Re19: Nature Is Not F-ing Around. retraice.com.
[86]https://www.retraice.com/segments/re19 Retrieved 12th Oct. 2022.
Retraice (2022/10/19). Re23: You Need a World Model. retraice.com.
[87]https://www.retraice.com/segments/re23 Retrieved 20th Oct. 2022.
Retraice (2022/10/23). Re27: Now That's a World Model - WM4. retraice.com.
[88]https://www.retraice.com/segments/re27 Retrieved 24th Oct. 2022.
Retraice (2022/10/31). Re36: Notes on Conspiracy. retraice.com.
[89]https://www.retraice.com/segments/re36 Retrieved 4th Nov. 2022.
Retraice (2022/11/12). Re48: From Drugs to Mao to Money. retraice.com.
[90]https://www.retraice.com/segments/re48 Retrieved 14th Nov. 2022.
Retraice (2022/11/16). Re52: Big Questions About AI. retraice.com.
[91]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.
[92]https://www.retraice.com/segments/re57 Retrieved 22nd Nov. 2022.
Retraice (2022/11/22). Re58: Thinking and Uncertainty (AIMA4e chpts. 7-18). retraice.com.
[93]https://www.retraice.com/segments/re58 Retrieved 23rd Nov. 2022.
Retraice (2022/11/23). Re59: Learning, Interacting, Conclusions (AIMA4e chpts. 19-28). retraice.com.
[94]https://www.retraice.com/segments/re59 Retrieved 24th Nov. 2022.
Retraice (2022/11/24). Re60: Complexity, Linear Algebra, Probability (AIMA4e Appendix A). retraice.com.
[95]https://www.retraice.com/segments/re60 Retrieved 25th Nov. 2022.
Russell, B. (1948). Human Knowledge: Its Scope and Limits. Routledge. First published in 1948. This edition 1992. ISBN: 0415083028. Searches:
[96]https://archive.org/search.php?query=Human%20Knowledge%3A%20Its%20Scope%20and%20Limits
[97]https://www.amazon.com/s?k=0415083028
[98]https://www.google.com/search?q=isbn+0415083028
[99]https://lccn.loc.gov/94209784
Russell, B. (1959). My Philosophical Development. Wnwin Brothers. No ISBN.
[100]https://archive.org/details/myphilosophicald0000russ/page/n11/mode/2up Retrieved 06 Jun. 2021. Searches:
[101]https://www.amazon.com/s?k=Russell+My+Philosophical+Development
[102]https://www.google.com/search?q=Russell+My+Philosophical+Development
[103]https://lccn.loc.gov/59003496
Vallee, J. (1979). Messengers of Deception: UFO Contacts and Cults. And/Or Press. ISBN: 0915904381. Different edition and searches:
[104]https://archive.org/details/MessengersOfDeceptionUFOContactsAndCultsJacquesValle1979/mode/2up
[105]https://www.amazon.com/s?k=0915904381
[106]https://www.google.com/search?q=isbn+0915904381
[107]https://catalog.loc.gov/vwebv/search?searchArg=0915904381
References