Learning Rules-First Classifiers

Deborah Cohen, Amit Daniely, Amir Globerson, Gal Elidan
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:1398-1406, 2019.

Abstract

Complex classifiers may exhibit “embarassing” failures in cases where humans can easily provide a justified classification. Avoiding such failures is obviously of key importance. In this work, we focus on one such setting, where a label is perfectly predictable if the input contains certain features, or rules, and otherwise it is predictable by a linear classifier. We define a hypothesis class that captures this notion and determine its sample complexity. We also give evidence that efficient algorithms cannot achieve this sample complexity. We then derive a simple and efficient algorithm and show that its sample complexity is close to optimal, among efficient algorithms. Experiments on synthetic and sentiment analysis data demonstrate the efficacy of the method, both in terms of accuracy and interpretability.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-cohen19a, title = {Learning Rules-First Classifiers}, author = {Cohen, Deborah and Daniely, Amit and Globerson, Amir and Elidan, Gal}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {1398--1406}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/cohen19a/cohen19a.pdf}, url = {https://proceedings.mlr.press/v89/cohen19a.html}, abstract = {Complex classifiers may exhibit “embarassing” failures in cases where humans can easily provide a justified classification. Avoiding such failures is obviously of key importance. In this work, we focus on one such setting, where a label is perfectly predictable if the input contains certain features, or rules, and otherwise it is predictable by a linear classifier. We define a hypothesis class that captures this notion and determine its sample complexity. We also give evidence that efficient algorithms cannot achieve this sample complexity. We then derive a simple and efficient algorithm and show that its sample complexity is close to optimal, among efficient algorithms. Experiments on synthetic and sentiment analysis data demonstrate the efficacy of the method, both in terms of accuracy and interpretability.} }
Endnote
%0 Conference Paper %T Learning Rules-First Classifiers %A Deborah Cohen %A Amit Daniely %A Amir Globerson %A Gal Elidan %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-cohen19a %I PMLR %P 1398--1406 %U https://proceedings.mlr.press/v89/cohen19a.html %V 89 %X Complex classifiers may exhibit “embarassing” failures in cases where humans can easily provide a justified classification. Avoiding such failures is obviously of key importance. In this work, we focus on one such setting, where a label is perfectly predictable if the input contains certain features, or rules, and otherwise it is predictable by a linear classifier. We define a hypothesis class that captures this notion and determine its sample complexity. We also give evidence that efficient algorithms cannot achieve this sample complexity. We then derive a simple and efficient algorithm and show that its sample complexity is close to optimal, among efficient algorithms. Experiments on synthetic and sentiment analysis data demonstrate the efficacy of the method, both in terms of accuracy and interpretability.
APA
Cohen, D., Daniely, A., Globerson, A. & Elidan, G.. (2019). Learning Rules-First Classifiers. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:1398-1406 Available from https://proceedings.mlr.press/v89/cohen19a.html.

Related Material