Foundations and Properties of AI/ML Systems

The chapter provides a broad introduction to the foundations of health AI and ML systems and is organized as follows: (1) Theoretical properties and formal vs. heuristic systems: computability, incompleteness theorem, space and time complexity, exact vs. asymptotic complexity, complexity classes and how to establish complexity of problems even in the absence of known algorithms that solve them, problem complexity vs. algorithm and program complexity, and various other properties. Moreover, we discuss the practical implications of complexity for system tractability, the folly of expecting Moore’s Law and large-scale computing to solve intractable problems, and common techniques for creating tractable systems that operate in intractable problem spaces. We also discuss the distinction between heuristic and formal systems and show that they exist on a continuum rather than in separate spaces. (2) Foundations of AI including logics and logic based systems (rule based systems, semantic networks, planning systems search, NLP parsers), symbolic vs. non-symbolic AI, Reasoning with Uncertainty, Decision Making theory, Bayesian Networks, and AI/ML programming languages. (3) Foundations of Computational Learning Theory: ML as search, ML as geometrical construction and function optimization, role of inductive biases, PAC learning, VC dimension, Theory of Feature Selection, Theory of Causal Discovery. Optimal Bayes Classifier, No Free Lunch Theorems, Universal Function Approximation, generative vs. discriminative models; Bias-Variance Decomposition of error and essential concepts of mathematical statistics.