The Teaching Dimension of Linear Learners

Ji Liu, Xiaojin Zhu, Hrag Ohannessian
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:117-126, 2016.

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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v48-liua16, title = {The Teaching Dimension of Linear Learners}, author = {Liu, Ji and Zhu, Xiaojin and Ohannessian, Hrag}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {117--126}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/liua16.pdf}, url = { http://proceedings.mlr.press/v48/liua16.html }, 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.} }
Endnote
%0 Conference Paper %T The Teaching Dimension of Linear Learners %A Ji Liu %A Xiaojin Zhu %A Hrag Ohannessian %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-liua16 %I PMLR %P 117--126 %U http://proceedings.mlr.press/v48/liua16.html %V 48 %X 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.
RIS
TY - CPAPER TI - The Teaching Dimension of Linear Learners AU - Ji Liu AU - Xiaojin Zhu AU - Hrag Ohannessian BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-liua16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 117 EP - 126 L1 - http://proceedings.mlr.press/v48/liua16.pdf UR - http://proceedings.mlr.press/v48/liua16.html AB - 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. ER -
APA
Liu, J., Zhu, X. & Ohannessian, H.. (2016). The Teaching Dimension of Linear Learners. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:117-126 Available from http://proceedings.mlr.press/v48/liua16.html .

Related Material