Computing Community Consortium Blog

The goal of the Computing Community Consortium (CCC) is to catalyze the computing research community to debate longer range, more audacious research challenges; to build consensus around research visions; to evolve the most promising visions toward clearly defined initiatives; and to work with the funding organizations to move challenges and visions toward funding initiatives. The purpose of this blog is to provide a more immediate, online mechanism for dissemination of visioning concepts and community discussion/debate about them.

Great Innovative Idea- Machine Teaching

May 5th, 2015 / in CCC, Research News / by Helen Wright


The following Great Innovative Idea is from Dr. Xiaojin (Jerry) Zhu, Associate Professor of Computer Science at University of Wisconsin-Madison.

Zhu’s paper Machine Teaching: an Inverse Problem to Machine Learning and an Approach Toward Optimal Education won the Computing Community Consortium (CCC) sponsored Blue Sky Ideas Conference Track series at the 29th Association for the Advancement of Artificial Intelligence (AAAI) Conference on Artificial Intelligence (AAAI-15), January 25-30, 2015 in Austin, Texas.

The Innovative Idea

Machine teaching is machine learning turned upside down: it is about finding the optimal (e.g. the smallest) training set.  For example, consider a “student” who runs the Support Vector Machine learning algorithm.  Imagine a teacher who wants to teach the student a specific target hyperplane in some feature space (never mind how the teacher got this hyperplane in the first place).  The teacher constructs a training set D=(x1,y1) … (xn, yn), where xi is a feature vector and yi a class label, to train the student.  What is the smallest training set that will make the student learn the target hyperplane?  It is not hard to see that n=2 is sufficient with the two training items straddling the target hyperplane.  Machine teaching mathematically formalizes this idea and generalizes it to many kinds of learning algorithms and teaching targets. Solving the machine teaching problem in general can be intricate and is an open mathematical question, though for a large family of learners the resulting bilevel optimization problem can be approximated.


Machine teaching can have an impact in education, where the “student” is really a human student, and the teacher certainly has a target model (i.e. the educational goal).  If we are willing to assume a cognitive learning model of the student, we can use machine teaching to reverse-engineer the optimal training data — which will be the optimal, personalized lesson for that student.  We have shown feasibility in a preliminary cognitive study to teach categorization.

Other Research

I also work on foundations of human and machine learning, topological methods for machine learning, and social media for social good.  Machine teaching is an example of the first direction.  There are many other interesting questions connecting machine learning, cognitive science, and mathematics.  For instance, have you ever wondered what the VC-dimension of our mind is?  You may want to take a look at our paper “Human Rademacher Complexity.”

Researcher’s Background

I am a computer scientist by training with a PhD from CMU.


My webpage can be found here.  

To view more Great Innovative Ideas, please click here.

Great Innovative Idea- Machine Teaching