Learning Theory Analysis for Association Rules and Sequential Event Prediction
We present a theoretical analysis for prediction algorithms based on association rules. As part of this analysis, we introduce a problem for which rules are particularly natural, called “sequential event prediction." In sequential event prediction, events in a sequence are revealed one by one,...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/85071 |
| _version_ | 1811081970274271232 |
|---|---|
| author | Rudin, Cynthia Letham, Benjamin Madigan, David |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Rudin, Cynthia Letham, Benjamin Madigan, David |
| author_sort | Rudin, Cynthia |
| collection | MIT |
| description | We present a theoretical analysis for prediction algorithms based on association rules. As part of this analysis, we introduce a problem for which rules are particularly natural, called “sequential event prediction." In sequential event prediction, events in a sequence are revealed one by one, and the goal is to determine which event will next be revealed. The training set is a collection of past sequences of events. An example application is to predict which item will next be placed into a customer's online shopping cart, given his/her past purchases. In the context of this problem, algorithms based on association rules have distinct advantages over classical statistical and machine learning methods: they look at correlations based on subsets of co-occurring past events (items a and b imply item c), they can be applied to the sequential event prediction problem in a natural way, they can potentially handle the “cold start" problem where the training set is small, and they yield interpretable predictions. In this work, we present two algorithms that incorporate association rules. These algorithms can be used both for sequential event prediction and for supervised classification, and they are simple enough that they can possibly be understood by users, customers, patients, managers, etc. We 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. |
| first_indexed | 2024-09-23T11:55:18Z |
| format | Article |
| id | mit-1721.1/85071 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:55:18Z |
| publishDate | 2014 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/850712022-10-01T06:57:09Z Learning Theory Analysis for Association Rules and Sequential Event Prediction Rudin, Cynthia Letham, Benjamin Madigan, David Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Rudin, Cynthia Letham, Benjamin We present a theoretical analysis for prediction algorithms based on association rules. As part of this analysis, we introduce a problem for which rules are particularly natural, called “sequential event prediction." In sequential event prediction, events in a sequence are revealed one by one, and the goal is to determine which event will next be revealed. The training set is a collection of past sequences of events. An example application is to predict which item will next be placed into a customer's online shopping cart, given his/her past purchases. In the context of this problem, algorithms based on association rules have distinct advantages over classical statistical and machine learning methods: they look at correlations based on subsets of co-occurring past events (items a and b imply item c), they can be applied to the sequential event prediction problem in a natural way, they can potentially handle the “cold start" problem where the training set is small, and they yield interpretable predictions. In this work, we present two algorithms that incorporate association rules. These algorithms can be used both for sequential event prediction and for supervised classification, and they are simple enough that they can possibly be understood by users, customers, patients, managers, etc. We 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. National Science Foundation (U.S.) (Grant IIS-1053407) 2014-02-24T16:27:19Z 2014-02-24T16:27:19Z 2013-11 2013-07 Article http://purl.org/eprint/type/JournalArticle 1532-4435 1533-7928 http://hdl.handle.net/1721.1/85071 Rudin, Cynthia, Benjamin Letham, and David Madigan. "Learning Theory Analysis for Association Rules and Sequential Event Prediction." Journal of Machine Learning Research 14 (2013): 3441-3492. en_US http://jmlr.org/papers/volume14/rudin13a/rudin13a.pdf Journal of Machine Learning Research Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Association for Computing Machinery (ACM) Association for Computing Machinery |
| spellingShingle | Rudin, Cynthia Letham, Benjamin Madigan, David Learning Theory Analysis for Association Rules and Sequential Event Prediction |
| title | Learning Theory Analysis for Association Rules and Sequential Event Prediction |
| title_full | Learning Theory Analysis for Association Rules and Sequential Event Prediction |
| title_fullStr | Learning Theory Analysis for Association Rules and Sequential Event Prediction |
| title_full_unstemmed | Learning Theory Analysis for Association Rules and Sequential Event Prediction |
| title_short | Learning Theory Analysis for Association Rules and Sequential Event Prediction |
| title_sort | learning theory analysis for association rules and sequential event prediction |
| url | http://hdl.handle.net/1721.1/85071 |
| work_keys_str_mv | AT rudincynthia learningtheoryanalysisforassociationrulesandsequentialeventprediction AT lethambenjamin learningtheoryanalysisforassociationrulesandsequentialeventprediction AT madigandavid learningtheoryanalysisforassociationrulesandsequentialeventprediction |