Notes and Resources
Notes and Resources
The problem of induction, computational learning theory, machine learning & cognitive perspectives
Lectures, Notes, & Exercises:
Additional Reading:
Systems that Learn (Ch 1) by Osherson, Royer, & Sharma (1999), for further discussion on learning paradigms and the game of learner & nature
Resoning about Knowledge (Ch 1,2,3) by Fagin, Halpern, Moses, & Vardi (2004), for further discussion and technical details of Epistemic Logic. We have included some pages on topics beyond today's lecture, e.g. common knowledge & proving completeness. This selection also includes some discussion of the Muddy Children Puzzle, which offers a sneak peak for tomorrow's lecture :-)
Mechanizing induction by Ortner & Leitgeb (2011). This one is more optional than the other two -- it is a long read, and the topics it covers are complementary yet orthogonal to our course. It introduces many topics on learning that we merely hint at, including Occam's razor, no-free-lunch theorems, PAC learning, compressibility, neural network model completeness, and more. We recommend you sample those chapters that seem the most interesting to you as we continue through the week.
Dynamic epistemic logic, public announcement, plausibility models, soft upgrades
Lectures, Notes, & Exercises:
Additional Reading:
Dynamic Epistemic Logic (Ch 4) by Ditmarsch, van der Hoek, & Kooi (2008) for further discussion on public announcement / conditioning update. There is a bit more material than what we covered in class, especially concerning common knowledge (knowledge shared among a group). Historically, the development of public announcement logic was motivated by these sorts of multi-agent scenarios. But in this course, we are more interested in what's going on inside an individual's head -- an individual's learning policy. So we skip common knowledge.
Dynamic logic for belief revision by van Benthem (2007) for more technical details on those epistemic and doxastic update operators we talked about today (public announcement, Lex, and Mini). This paper is actually quite inspirational -- it teaches a unified way of thinking about dynamic epistemic logic together with belief revision. It also has a very nice passage on the philosophy of DEL in general, and the "reduction" trick we saw in class.
Neural networks and DEL, single-step updates on neural nets, the Hebbian update rule
Lectures, Notes, & Exercises:
Additional Reading:
Neural Network Models of Conditionals: An Introduction by Leitgeb (2007). This paper summarizes the approach we take in using neural networks as models for a logic. The author also puts forward justification for why we can think of the input-output behavior of a neural network as its conditional belief. Note that this work is done in conditional logic, whereas in our class we used a slightly generalized modal logic. Unfortunately, we are unaware of any nice interpretation of the closure modality C in terms of knowledge or belief (but you should think of it as encoding a kind of soft information, similar to belief).
Reduction Axioms for Iterated Hebbian Learning by Schultz Kisby, Blanco, & Moss (2024) for more technical details on this Hebbian update operator and its axiomatization. The "T" operator in this paper is really our closure modality C. Beware that this is a very technical read, not so much introductory material -- these ideas are still very recent!
Naturally Intelligent Systems (Ch 9) by Caudill & Butler (1992) gives a great discussion of Hebbian learning, its history, and common variations of the learning policy & how they tend to be used in practice.
Also, we strongly recommend this 3Blue1Brown Youtube Video on Gradient Descent. We only spoke about backpropagation in brief terms in class. But if you would like to understand it better, consider this video required reading. :-)
Iterated updates on data streams, properties of iterated learners, truth-tracking and learning in the limit
Lectures, Notes, & Exercises:
Additional Reading:
Inductive Inference and Epistemic Modal Logic, by Gierasimczuk (2023) is an introduction and overview of this approach to learning in epistemic spaces.
Truth-tracking by belief revision, by Baltag, Gierasimczuk, & Smets (2019) is the primary source for this work on the truth-tracking and learning ability of the Cond, Lex, and Mini belief revision policies. Today's class followed it very closely, and we recommend you give it a read!
AGM-style belief revision, belief revision and backpropagation, gradual belief change
Lectures, Notes, & Exercises:
Additional Reading:
The Stanford Encyclopedia page on Belief Revision, by Hansson (2021) is an excellent overview of the wide variety of AGM-style belief revision operators & ways to model them.
Towards machine learning as AGM-style belief change, by Aravanis (2024) is the paper that considers training via backpropagation as a gradual revision of a belief set. The main result is that the effects of backpropagation (over a binary neural net) on a belief set can be viewed as an AGM revision ∗φ, followed by a contraction ∸Ψ. Note that the revision operator ∗, the contraction operator ∸, and the formulas φ,Ψ are carefully chosen to match the effects of backprop (see the proof of Theorem 21).
Dynamic doxastic logic: why, how, and where to? by Leitgeb & Segerberg (2007) discusses the key technical differences between our primary approach in this class so far -- belief revision as a DEL upgrade, expressible in the language -- and AGM belief revision. A highlight of this paper is that it translates each standard AGM postulate into the DEL language.
On the Solvability of Inductive Problems: A Study in Epistemic Topology, by Baltag, Gierasimczuk, & Smets (2015) bridges our approach from yesterday (iterated updates and learnability) with our approach from today (AGM-style belief set revision).