Sequential Event Prediction with Association Rules

Cynthia Rudin, Benjamin Letham, Ansaf Salleb-Aouissi, Eugene Kogan, David Madigan
Proceedings of the 24th Annual Conference on Learning Theory, PMLR 19:615-634, 2011.

Abstract

We consider a supervised learning problem in which data are revealed sequentially and the goal is to determine what will next be revealed. In the context of this problem, algorithms based on association rules have a distinct advantage over classical statistical and machine learning methods; however, there has not previously been a theoretical foundation established for using association rules in supervised learning. We present two simple algorithms that incorporate association rules, and provide generalization guarantees on these algorithms based on algorithmic stability analysis from statistical learning theory. We include a discussion of the strict minimum support threshold often used in association rule mining, and introduce an “adjusted confidence” measure that provides a weaker minimum support condition that has advantages over the strict minimum support. The paper brings together ideas from statistical learning theory, association rule mining and Bayesian analysis.

Cite this Paper


BibTeX
@InProceedings{pmlr-v19-rudin11a, title = {Sequential Event Prediction with Association Rules}, author = {Rudin, Cynthia and Letham, Benjamin and Salleb-Aouissi, Ansaf and Kogan, Eugene and Madigan, David}, booktitle = {Proceedings of the 24th Annual Conference on Learning Theory}, pages = {615--634}, year = {2011}, editor = {Kakade, Sham M. and von Luxburg, Ulrike}, volume = {19}, series = {Proceedings of Machine Learning Research}, address = {Budapest, Hungary}, month = {09--11 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v19/rudin11a/rudin11a.pdf}, url = {https://proceedings.mlr.press/v19/rudin11a.html}, abstract = {We consider a supervised learning problem in which data are revealed sequentially and the goal is to determine what will next be revealed. In the context of this problem, algorithms based on association rules have a distinct advantage over classical statistical and machine learning methods; however, there has not previously been a theoretical foundation established for using association rules in supervised learning. We present two simple algorithms that incorporate association rules, and provide generalization guarantees on these algorithms based on algorithmic stability analysis from statistical learning theory. We include a discussion of the strict minimum support threshold often used in association rule mining, and introduce an “adjusted confidence” measure that provides a weaker minimum support condition that has advantages over the strict minimum support. The paper brings together ideas from statistical learning theory, association rule mining and Bayesian analysis.} }
Endnote
%0 Conference Paper %T Sequential Event Prediction with Association Rules %A Cynthia Rudin %A Benjamin Letham %A Ansaf Salleb-Aouissi %A Eugene Kogan %A David Madigan %B Proceedings of the 24th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2011 %E Sham M. Kakade %E Ulrike von Luxburg %F pmlr-v19-rudin11a %I PMLR %P 615--634 %U https://proceedings.mlr.press/v19/rudin11a.html %V 19 %X We consider a supervised learning problem in which data are revealed sequentially and the goal is to determine what will next be revealed. In the context of this problem, algorithms based on association rules have a distinct advantage over classical statistical and machine learning methods; however, there has not previously been a theoretical foundation established for using association rules in supervised learning. We present two simple algorithms that incorporate association rules, and provide generalization guarantees on these algorithms based on algorithmic stability analysis from statistical learning theory. We include a discussion of the strict minimum support threshold often used in association rule mining, and introduce an “adjusted confidence” measure that provides a weaker minimum support condition that has advantages over the strict minimum support. The paper brings together ideas from statistical learning theory, association rule mining and Bayesian analysis.
RIS
TY - CPAPER TI - Sequential Event Prediction with Association Rules AU - Cynthia Rudin AU - Benjamin Letham AU - Ansaf Salleb-Aouissi AU - Eugene Kogan AU - David Madigan BT - Proceedings of the 24th Annual Conference on Learning Theory DA - 2011/12/21 ED - Sham M. Kakade ED - Ulrike von Luxburg ID - pmlr-v19-rudin11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 19 SP - 615 EP - 634 L1 - http://proceedings.mlr.press/v19/rudin11a/rudin11a.pdf UR - https://proceedings.mlr.press/v19/rudin11a.html AB - We consider a supervised learning problem in which data are revealed sequentially and the goal is to determine what will next be revealed. In the context of this problem, algorithms based on association rules have a distinct advantage over classical statistical and machine learning methods; however, there has not previously been a theoretical foundation established for using association rules in supervised learning. We present two simple algorithms that incorporate association rules, and provide generalization guarantees on these algorithms based on algorithmic stability analysis from statistical learning theory. We include a discussion of the strict minimum support threshold often used in association rule mining, and introduce an “adjusted confidence” measure that provides a weaker minimum support condition that has advantages over the strict minimum support. The paper brings together ideas from statistical learning theory, association rule mining and Bayesian analysis. ER -
APA
Rudin, C., Letham, B., Salleb-Aouissi, A., Kogan, E. & Madigan, D.. (2011). Sequential Event Prediction with Association Rules. Proceedings of the 24th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 19:615-634 Available from https://proceedings.mlr.press/v19/rudin11a.html.

Related Material