← Back to papers
2016 JMLR JMLR 2016

The Teaching Dimension of Linear Learners

Abstract

Teaching dimension is a learning theoretic quantity that specifies the minimum training set size to teach a target model to a learner. Previous studies on teaching dimension focused on version-space learners which maintain all hypotheses consistent with the training data, and cannot be applied to modern machine learners which select a specific hypothesis via optimization. This paper presents the first known teaching dimension for ridge regression, support vector machines, and logistic regression. We also exhibit optimal training sets that match these teaching dimensions. Our approach generalizes to other linear learners. [abs] [ pdf ][ bib ] © JMLR 2016. (edit, beta)

🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Robotics, Security & Privacy, Speech & Audio
🧭 Keyword Pioneer — version-space learning
🐣 Hot Topic Early Bird — logistic regression

Authors

Ji Liu , Xiaojin Zhu

Topics

Machine Learning > Core Methods > Classification Machine Learning > Core Methods > Regression Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Learning Types > Supervised Learning

Keywords

logistic regression ridge regression teaching dimension support vector machine linear learner version-space learning
Download PDF

Related papers

Trend Filtering on Graphs 2016
Causal Inference through a Witness Protection Program 2016
A Characterization of Linkage-Based Hierarchical Clustering 2016
How to Center Deep Boltzmann Machines 2016
Minimax Rates in Permutation Estimation for Feature Matching 2016