Exact Rule Learning via Boolean Compressed Sensing

Dmitry Malioutov, Kush Varshney
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):765-773, 2013.

Abstract

We propose an interpretable rule-based classification system based on ideas from Boolean compressed sensing. We represent the problem of learning individual conjunctive clauses or individual disjunctive clauses as a Boolean group testing problem, and apply a novel linear programming relaxation to find solutions. We derive results for exact rule recovery which parallel the conditions for exact recovery of sparse signals in the compressed sensing literature: although the general rule recovery problem is NP-hard, under some conditions on the Boolean ‘sensing’ matrix, the rule can be recovered exactly. This is an exciting development in rule learning where most prior work focused on heuristic solutions. Furthermore we construct rule sets from these learned clauses using set covering and boosting. We show competitive classification accuracy using the proposed approach.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-malioutov13, title = {Exact Rule Learning via Boolean Compressed Sensing}, author = {Malioutov, Dmitry and Varshney, Kush}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {765--773}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/malioutov13.pdf}, url = {https://proceedings.mlr.press/v28/malioutov13.html}, abstract = {We propose an interpretable rule-based classification system based on ideas from Boolean compressed sensing. We represent the problem of learning individual conjunctive clauses or individual disjunctive clauses as a Boolean group testing problem, and apply a novel linear programming relaxation to find solutions. We derive results for exact rule recovery which parallel the conditions for exact recovery of sparse signals in the compressed sensing literature: although the general rule recovery problem is NP-hard, under some conditions on the Boolean ‘sensing’ matrix, the rule can be recovered exactly. This is an exciting development in rule learning where most prior work focused on heuristic solutions. Furthermore we construct rule sets from these learned clauses using set covering and boosting. We show competitive classification accuracy using the proposed approach.} }
Endnote
%0 Conference Paper %T Exact Rule Learning via Boolean Compressed Sensing %A Dmitry Malioutov %A Kush Varshney %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-malioutov13 %I PMLR %P 765--773 %U https://proceedings.mlr.press/v28/malioutov13.html %V 28 %N 3 %X We propose an interpretable rule-based classification system based on ideas from Boolean compressed sensing. We represent the problem of learning individual conjunctive clauses or individual disjunctive clauses as a Boolean group testing problem, and apply a novel linear programming relaxation to find solutions. We derive results for exact rule recovery which parallel the conditions for exact recovery of sparse signals in the compressed sensing literature: although the general rule recovery problem is NP-hard, under some conditions on the Boolean ‘sensing’ matrix, the rule can be recovered exactly. This is an exciting development in rule learning where most prior work focused on heuristic solutions. Furthermore we construct rule sets from these learned clauses using set covering and boosting. We show competitive classification accuracy using the proposed approach.
RIS
TY - CPAPER TI - Exact Rule Learning via Boolean Compressed Sensing AU - Dmitry Malioutov AU - Kush Varshney BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-malioutov13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 765 EP - 773 L1 - http://proceedings.mlr.press/v28/malioutov13.pdf UR - https://proceedings.mlr.press/v28/malioutov13.html AB - We propose an interpretable rule-based classification system based on ideas from Boolean compressed sensing. We represent the problem of learning individual conjunctive clauses or individual disjunctive clauses as a Boolean group testing problem, and apply a novel linear programming relaxation to find solutions. We derive results for exact rule recovery which parallel the conditions for exact recovery of sparse signals in the compressed sensing literature: although the general rule recovery problem is NP-hard, under some conditions on the Boolean ‘sensing’ matrix, the rule can be recovered exactly. This is an exciting development in rule learning where most prior work focused on heuristic solutions. Furthermore we construct rule sets from these learned clauses using set covering and boosting. We show competitive classification accuracy using the proposed approach. ER -
APA
Malioutov, D. & Varshney, K.. (2013). Exact Rule Learning via Boolean Compressed Sensing. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):765-773 Available from https://proceedings.mlr.press/v28/malioutov13.html.

Related Material