PaperlayerView exact revision on arXiv

Source-linked AI summary

Iterative Machine Teaching

Weiyang Liu, Bo Dai, Ahmad Humayun, Charlene Tay, Chen Yu, Linda B. Smith, James M. Rehg, Le Song

arXiv:1705.10470v3stat.MLcs.LG

TL;DR

The paper asks how machine teaching should work when learners update iteratively rather than from a one-shot batch. It develops sequential, feedback-based teaching algorithms and shows that, under suitable conditions, they can reduce teaching examples and accelerate convergence, with experiments supporting the theory.

  • Problem

    The paper studies how teachers should sequentially choose examples for iterative learners, rather than construct minimal one-shot datasets.

  • Method

    It defines iterative machine teaching and proposes omniscient, surrogate, and imitation teachers whose strategies depend on the information available about the student.

  • Results

    Under suitable conditions, iterative teachers achieve faster convergence than passive teaching, including exponential improvements, and experiments on synthetic and real image data verify the theoretical findings.

  • Takeaways & Limitations

    Teaching complexity in the iterative setting concerns achieving fast algorithmic convergence rather than constructing a minimal training set.

  • Takeaways & Limitations

    The proposed teachers are not necessarily optimal because exhaustively finding the fastest example sequence is computationally infeasible, and guarantees depend on suitable conditions.

Abstract

from arXiv · show

In this paper, we consider the problem of machine teaching, the inverse problem of machine learning. Different from traditional machine teaching which views the learners as batch algorithms, we study a new paradigm where the learner uses an iterative algorithm and a teacher can feed examples sequentially and intelligently based on the current performance of the learner. We show that the teaching complexity in the iterative case is very different from that in the batch case. Instead of constructing a minimal training set for learners, our iterative machine teaching focuses on achieving fast convergence in the learner model. Depending on the level of information the teacher has from the learner model, we design teaching algorithms which can provably reduce the number of teaching examples and achieve faster convergence than learning without teachers. We also validate our theoretical findings with extensive experiments on different data distribution and real image datasets.

1. Introduction

The paper extends machine teaching from one-shot batch datasets to sequential teaching for iterative learners, using feedback about learner performance to target fast convergence. It introduces information-dependent teaching algorithms, theoretical analyses, and experiments supporting their effectiveness.

  • The framework addresses how example sequences and teaching rounds should be chosen to achieve fast convergence in applications such as model compression and cyber-security.These applications motivate using observations of the learner’s current behavior to guide subsequent examples.
  • Iterative machine teaching feeds examples sequentially while observing learner information, shifting the objective from minimal datasets to fast convergence.The teacher communicates with and influences a passive student across multiple rounds, choosing one example per round.
  • Three teacher algorithms—omniscient, surrogate, and imitation—are designed according to the information available about the student.The paper provides partial theoretical analyses under different example-construction schemes.
  • Under suitable conditions, iterative teachers can outperform passive teaching and achieve exponential improvements, with teaching monotonicity and teacher capability identified as critical properties.
  • Experiments on synthetic and real image data verify the theoretical findings and the effectiveness of the proposed iterative teaching algorithms.

2. Related Work

Related work frames machine teaching as optimal dataset construction and distinguishes it from interactive learning, active learning, and curriculum learning. The paper positions iterative machine teaching as addressing iterative learners that prior work does not fully capture.

  • Prior machine-teaching work studies optimal or minimal training sets and teaching dimensions for student models, with applications including security, human-computer interaction, and education.
  • Interactive machine-learning studies consider human or crowd learners, whereas this paper focuses on learners using iterative algorithms.
  • Active learning lets learners query an oracle and explore parameters themselves, unlike machine teaching, where examples guide the learner.
  • Curriculum learning orders examples from easy to difficult, and the paper reports that its iterative teacher suggests a similar strategy in experiments.

3. Iterative Machine Teaching

The framework models a teacher that supplies one example per iteration to a student optimizing a shared convex loss, with effectiveness depending on the teacher’s information about the learner. It considers stochastic-gradient learners and uses example difficulty to motivate teaching choices.

  • The student’s accessible information includes initialization, loss, optimization algorithm, representation, model, learning rate, and parameter trackability.Teaching practicality depends on the teacher’s prior knowledge and ability to track the student.
  • The teacher provides one example per iteration so the student parameter converges to its optimum as quickly as possible.The student remains passive and applies its fixed iterative update to the supplied example.
  • Teacher and student share a convex loss function, including square, logistic, and hinge loss as representative cases.
  • The setting uses stochastic gradient descent for the student, while un guided learning is modeled as randomly selecting an example at each iteration.

4. Teaching by an Omniscient Teacher

The omniscient teacher selects examples using full knowledge of the student and seeks examples that are both easy enough to process and useful for reducing parameter error. Under suitable conditions, this strategy converges no slower than random teaching and can achieve exponential teachability, with performance depending on the available teaching capability and pool richness.

  • 4.1. Intuition and teaching algorithm: An omniscient teacher balances example difficulty T1 against usefulness T2, favoring easier examples early and more difficult examples near the optimum.Difficulty depends on the learner’s current parameters, while usefulness measures correlation with the discrepancy between the learner and teacher parameters.
  • 4.2. Teaching monotonicity and universal speedup: Under the teaching-monotonicity condition, an omniscient teacher converges no slower than a random teacher with the same initialization and learning rate.The condition requires remaining teaching effort to decrease as the student approaches the optimum; square loss satisfies it.
  • 4.3. Teaching capability and exponential speedup: The teacher’s capability ranges from synthesis to combination and rescalable pool teaching, with restricted candidate pools requiring sufficiently rich directions for exponential improvement.Pool-based teaching cannot generally realize arbitrary directions, so the candidate pool’s volume affects whether the required examples exist.
  • 4.3. Teaching capability and exponential speedup: Iterative teaching complexity is deterministic because the teacher supplies noiseless examples deliberately at each iteration rather than relying on random sampling bounds.The resulting sample complexity measures the number of teaching rounds needed for convergence.
  • 4.3. Teaching capability and exponential speedup: Lipschitz-smooth and strongly convex losses are exponentially teachable under synthesis-based teaching, and hinge and logistic losses can also satisfy this weaker teachability condition.Exponential synthesis-based teachability is weaker than requiring both strong convexity and Lipschitz smoothness.
  • 4.3. Teaching capability and exponential speedup: As pool volume increases, rescalable pool teaching needs fewer samples and approaches the convergence speed of synthesis- or combination-based teaching.The sample complexity is the iterative teaching dimension for the specified teacher, student algorithm, and training data.

5. Teaching by a less informative teacher

Less informative teachers reduce their access to the student while still selecting examples sequentially to guide iterative learning. The surrogate teacher uses observed function outputs and convexity, while the imitation teacher learns to reproduce those outputs in its own feature space.

  • 5. Teaching by a less informative teacher: Less informative teacher models are designed to require progressively less information about the student while retaining sequential teaching capability.These models extend the practical applicability of iterative teaching beyond the fully informed setting.
  • 5. Teaching by a less informative teacher: A surrogate teacher selects examples from the learner’s function output rather than directly accessing its parameter vector.The approach uses convexity of the loss and can be adapted when teacher and student use different feature spaces.
  • 5. Teaching by a less informative teacher: The imitation teacher alternates between updating its parameters and providing selected examples for the student’s iterative update.Its procedure initializes teacher and student parameters, learns from observed behavior, and repeatedly selects examples until convergence or a maximum iteration count.
  • 5. Teaching by a less informative teacher: An imitation teacher learns to imitate the student’s inner-product output while selecting examples in the teacher’s own feature space.The student remains unchanged during imitation, and the learned teacher parameter is then used for example synthesis or selection.

6. Discussion

The discussion identifies limits on teacher optimality and theory, while leaving scalability, computational efficiency, and reduced informativeness as open practical challenges.

  • Optimality of the teacher model: The proposed teacher models are not necessarily optimal, but can be effective under conditions on the loss function, student model, and training data.Exhaustive search over possible training sequences is computationally infeasible.
  • Theoretical aspects of the teacher model: Theoretical guarantees depend on conditions for optimality or faster convergence, and the analysis here focuses on stochastic gradient learners rather than all optimization algorithms.The paper notes that sufficient conditions may be adequate in practice and that better teacher models remain possible.
  • Theoretical aspects of the teacher model: For dynamic learning rates, the approach remains applicable but requires a more powerful teacher capable of synthesizing or choosing examples with larger R.The stated results mainly focus on fixed learning rates.
  • Practical aspects of the teacher model: Making teacher models scalable to large datasets, computationally efficient, and less informative to the student remains an open practical challenge.These properties are identified as desirable for practical teacher models.

7. Experiments

Experiments show that iterative teaching accelerates convergence across Gaussian data, MNIST, CIFAR-10, and infant egocentric visual data, with performance depending on teacher information and example ordering.

  • 7.2. Teaching linear models on Gaussian data: Teacher-guided examples produce much faster convergence than conventional SGD, while sequential guiding generally outperforms SGD on the same selected set.The comparison uses objective value, distance to the target model, and test classification accuracy.
  • 7.2. Teaching linear models on Gaussian data: Across different feature spaces, surrogate and imitation teachers usually outperform SGD and batch GD, with imitation teaching more stable across ridge regression, logistic regression, and SVM.The surrogate teacher performs poorly for SVM, whereas imitation teaching consistently improves convergence across the three models.
  • 7.3. Teaching Linear Classifiers on MNIST Dataset: On MNIST 0/1 and 3/5 classification, all teacher models provide significant convergence speedups, and imitation teaching nearly matches omniscient teaching without access to the student feature space.Selected examples progress from easy digits to difficult ones, connecting the ordering to curriculum learning.
  • 7.4. Teaching Fully Connected Layers in CNNs: On CIFAR-10 fully connected CNN layers, teacher models converge quickly in test accuracy and can exceed the backprop-learned layer, while omniscient teaching gives the largest objective-value speedup.Imitation teaching is slightly weaker on objective value but remains substantially better than SGD.
  • 7.5. Teaching on ego-centric visual data of infants: For infant egocentric data, omniscient teaching selects examples in an ordering qualitatively similar to naturalistic child viewing and yields significantly faster convergence than random-input SGD.Both sequences contain extended bouts of viewing the same object.

8. Concluding Remarks

The paper introduces iterative machine teaching, analyzes teaching monotonicity and capability, and proposes three teacher models for gradient learners. Experiments verify the theoretical findings.

  • 8. Concluding Remarks: The framework extends machine teaching to iterative learners, with three teacher models designed to achieve provably fast convergence.The proposed models are omniscient, surrogate, and imitation teachers.
  • 8. Concluding Remarks: Experimental results verify the theoretical findings across the paper’s evaluated teaching settings.

A. Details of the Proof

The proofs establish convergence guarantees for omniscient teaching under synthesis-, combination-, and pool-based constructions. They show exponential teachability for several losses under stated assumptions and compare omniscient updates with random teaching.

  • Omniscient teaching: Omniscient teaching is no slower than random SGD at each iteration under the theorem’s stated conditions.The proof compares the parameter updates produced by omniscient and random teachers and derives the convergence ordering.
  • Synthesis-based teaching: Synthesis-based teaching achieves exponential convergence when the constructed example yields bounded learning intensity.The analysis introduces a scale factor for examples aligned with the current parameter error and derives exponential decay.
  • Loss-specific guarantees: Absolute and square losses are exponentially teachable under synthesis-based teaching.The paper states separate propositions for both losses after establishing the general exponential-teachability condition.
  • Loss-specific guarantees: Hinge and logistic losses are exponentially teachable in synthesis-based teaching when the target parameter satisfies ∥w∗∥≤1.The proofs construct labels and scale factors that satisfy the required learning-intensity bounds.
  • Restricted example constructions: Combination-based teaching matches synthesis-based teaching when the relevant error lies in the feature span, while pool-based teaching converges exponentially under rescalable-pool conditions.The combination result uses linear combinations of available features; the pool result approximates a virtual synthesis example from the candidate pool.

B. Detailed Experimental Setting

The experiments evaluate linear models and CNN classifiers across synthetic, MNIST, CIFAR-10, and infant visual data. They compare teaching strategies under controlled feature, learning-rate, model, and dataset settings.

  • Model and dataset setup: The study evaluates ridge regression, logistic regression, and support vector machines as linear student models.The experimental section specifies formulations for all three models before describing the datasets and teaching comparisons.
  • Model and dataset setup: The comparison of teaching strategies uses a 30-point knowledge pool, feature dimensions 2 or 70, and learning rate 0.0001 for pool-based teaching, BGD, and SGD.The experiment uses linear regression implemented as ridge regression with λ = 0.
  • Image experiments: CIFAR-10 experiments teach the 10-class fully connected classifier using CNNs, while infant-data experiments use VGG-16 features reduced by PCA for multiclass logistic regression.The CNN classifier has dimension 32×10; the infant-data pipeline reduces 4096-dimensional VGG-16 features to 64 dimensions.
  • Teaching-strategy comparison: On the strategy comparison, synthesis-based teaching usually performs best and always achieves exponential convergence, while rescalable pool-based teaching outperforms pool-based teaching.Combination-based teaching matches synthesis-based teaching when features are sufficient but performs much worse when they are not.
  • Image experiments: MNIST experiments show teachers selecting easy examples early, shifting toward difficult examples, and achieving faster convergence.The reported visualizations include selected examples for 7/9 classification and parameter error for 0/1 and 3/5 classification.

E. Teaching linear models on uniform spherical data

On uniform spherical data, omniscient teaching consistently improves convergence in the same feature space. With different feature spaces, imitation teaching provides the consistent speedup, whereas surrogate teaching performs poorly.

  • Teaching in the same feature space: Omniscient teaching consistently improves convergence over unassisted learning in the same feature space.The reported improvement depends on the training distribution and loss function, consistent with the theoretical analysis.
  • Teaching in the same feature space: Simple SGD on examples selected by the omniscient teacher also converges faster, indicating that the selected examples are more convergence-effective than the full sample set.This observation is reported for the same-feature-space experiment.
  • Teaching in different feature spaces: In different feature spaces, imitation teaching achieves consistent and significant convergence speedup, while surrogate teaching can perform worse than SGD and BGD.The comparison is reported for logistic regression and support vector machine classification on uniform spherical data.

F. Object learning experiment on children’s ego-centric visual data

The infant ego-centric experiment evaluates omniscient teaching on naturally ordered object experiences. The teacher converges faster than random teaching and selects smooth, contiguous object-instance sequences.

  • Dataset and representation: The dataset contains annotated toy objects from four one-year-old infants, with VGG-16 features used for object classification.The recordings capture parent-child interactions, and the experiment annotates object locations and categories across frames.
  • Convergence comparison: Omniscient teaching achieves faster convergence than random teaching on the infant ego-centric data.The comparison is reported in the convergence visualization for the experiment.
  • Selected training sequences: Omniscient teaching selects contiguous bouts of the same object instance with smoothly changing adjacent inputs, unlike random selection.The selected examples resemble the ordering of the infants’ natural visual experiences.
Loading 1705.10470v3…