Pennsylvania State University

Weekly Study Guide

Computational foundations of informatics. What is computation? Origins of computing - Leibnitz's quest for logical calculus; Hilbert's decision problem; Turing's solution of Hilbert's decision problem. Alternative models of computation and their relation to languages - Chomsky Hierarchy. Church-Turing Thesis. Algorithms. Hardness of computational problems. Power and limits of computation - Godel's incompleteness theorem. Computational lens. Computational abstractions in AI, Biology, Social Science.... Computation as an organizing framework for science.

Required Readings

• Lecture Slides
• Lewis, F. D. (2007). Essentials of Theoretical Computer Science, chapters on Computability, Automata, and Languages.

Recommended Readings

• Hillis, D. (1998). The Pattern on the Stone: The Simple Ideas that Make Computers Work. Basic Books

Quantifying information content of messages. Information, uncertainty, and entropy. Subjective nature of information. Elements of Shannon's Information Theory. Coding and decoding of messages.

Required Readings

• Lecture Slides
• Stone, J. (2019). Information Theory Tutorial.
• Guruswami, V., Rudra, A. and Sudan, M., 2019. Essentials of Coding Theory. Chapter 1.
• Schneider, T. A brief review of Molecular Information Theory

Recommended Readings

• Campbell, J. Grammatical Man - Information, Entropy, Language and Life.

What makes a string random? Descriptional complexity of a string as the length of the shortest program for generating the string. Kolmogorov complexity and conditional Kolmogorov Complexity. Kolmogorov complexity and data compression. Kolmogorov complexity and the universal distribution. Information distance and its applications.

Required Readings

• Lecture Slides
• Normalized Information distance, Vitanyi et al., 2008

Algorithmic Abstractions of (Logical) Reasoning. Introduction to Knowledge Representation. Knowledge representation using propositional logic; Review of Propositional Logic: Ontological and epistemological commitments; Syntax and Semantics; Possible worlds interpretation; Models and Logical notions of Truth and Falsehood; Logical Entailment; Inference rules; Modus ponens; Soundness and Completeness properties of inference. Extending modus ponens - the resolution principle.

FOPL (First-Order Predicate Logic). Ontological and epistemological commitments and Syntax and semantics of FOPL. Examples. Inference in FOL. Unification, instantiation, and entailment, and question answering.

• Lecture Slides, Vasant Honavar
• What is Knowledge Representation?, by Davis, Shrobe, and Szolovits.
• Algorithmic Abstractions of (Logical) Inference, Vasant Honavar
• What is an Ontology? by T. R. Gruber.
• Scribe Notes

• Concepts of Logical AI, by John McCarthy.
• Hard and Easy Distributions of SAT Problems David Mitchell, Bart Selman, Hector Levesque, Proceedings of AAAI, 1992.
• Vehicles: Experiments in Synthetic Psychology, Braitenberg, V. MIT Press. 1986.
• The Synthesis of Digital Machines With Provable Epistemic Properties. S. Rosenschein and L. Kaelbling (1986). In Proceedings of the Conference on Theoretical Aspects of Knowledge Representation (TARK)

Algorithmic Abstractions of (Probabilistic) Inference. Review of elements of probability. Probabilities as subjective measures of belief (relative to an agent's knowledge of the world). Probability. Conditional probability. Bayes theorem. Random Variables. Independence. Probability theory as a generalization of propositional logic. Ontological and epistemological commitments of probabilistic knowledge representation. Syntax and Semantics of probabilistic knowledge representation. Probabilistic inference.

Independence and Conditional Independence. Exploiting independence relations for compact representation of probability distributions. Bayesian network representations of probabilistic knowledge. Syntax and semantics. D-separation. Markov Blankets. Answering Independence Queries Using D-Separation tests.

Probabilistic Inference Using Bayesian Networks. Approximate inference using stochastic simulation (sampling, rejection sampling, and liklihood weighted sampling)

• Bayesian Networks Without Tears, Eugene Charniak
• A Brief Introduction to Graphical Models and Bayesian Networks, Kevin Murphy.
• Lecture Slides, Vasant Honavar

• Dependency Modeling Course, University of Helsinki
• A Logical Notion of Conditional Independence: Properties and Applications by A. Darwiche.
• Inference in Bayesian Networks -- A Procedural Guide Huang, C., A. Darwiche. Journal of Approximate Reasoning. Vol 15. pp. 225-263.
• Analysis of Three Bayesian Network Inference Algorithms: Variable Elimination, Likelihood Weighting, and Gibbs Sampling Rose F. Liu and Rusmin Soetjipto, 2004.
• Probabilistic Relational ModelsLise Getoor, Nir Friedman, Daphne Koller, Avi Pfeffer, and Ben Taskar.
• Open Universe Probability Models, Milch, B. and Russell, S. (2010).

Algorithmic abstractions of decision making under uncertainty. Elements of utility theory, Constraints on rational preferences, Utility functions, Utility elicitation, Multi-attribute utility functions, utility independence, decision networks, value of information. Representing and reasoning with qualitative preferences.

Required readings

• A Tutorial Introduction to Decision Theory, Warner North, 1968.
• Lecture Slides
• Decision Theory Stanford Encyclopedia of Philosophy

• Representing and Reasoning with Qualitative Preferences: Tools and Applications, Ganesh Ram Santhanam, Samik Basu, and Vasant Honavar, Morgan Claypool, 2016.