Abstract
Formal methods and machine learning can inform each other from deductive and inductive reasoning perspectives. This talk aims to facilitate the dialogue between the two communities by establishing some fundamental concepts in learning theory. We start with the classic stochastic (i.i.d.) training data view of statistical learning, which naturally leads to the concepts of empirical risk minimization, overfitting, VC-dimension, concentration of measure, and Probably-Approximately-Correct guarantees. We immediately realize that the interactions between the learner and the environment can be significantly enriched: in formal methods often the learner has the power to ask informative questions. Such power leads to faster learning guarantees in the form of active learning and query-based learning. Meanwhile, we notice that the environment oracle who answers learner questions can have different levels of helpfulness. The most helpful oracle is a teacher who encodes the ground truth in concise answers to the learner. This leads to the notion of machine teaching (a.k.a. optimal teaching, algorithmic teaching) which achieves the fastest learning possible, and is characterized by the concept of teaching dimension. At this point, we will venture out into sequential decision making, and introduce the goals and basic guarantees in online learning, multi-armed bandits, and reinforcement learning. Interestingly, the notion of a helpful teacher permeates throughout. Such non-standard interactions between the learner and the environment may offer new research perspectives for formal methods.
Bio: Jerry Zhu is a professor in the Department of Computer Sciences at the University of Wisconsin-Madison. Jerry received his Ph.D. from Carnegie Mellon University in 2005. His research interest is in machine learning, particularly machine teaching and adversarial sequential decision making. He currently serves or has served the following roles: conference chair for AISTATS and CogSci, Action Editor of Machine Learning Journal, member of DARPA ISAT advisory group. He is a recipient of a NSF CAREER Award, and winner of multiple best paper awards including an ICML classic paper prize in 2013.