A scalable approach for online hierarchical big data mining

Abstract

We study online compound decision problems in the context of sequential prediction of real valued sequences. In particular, we consider finite state (FS) predictors that are constructed based on the sequence history, whose length is quite large for applications involving big data. To mitigate overtraining problems, we define hierarchical equivalence classes and apply the exponentiated gradient (EG) algorithm to achieve the performance of the best state assignment defined on the hierarchy. For a sequence history of length h, we combine more than 2((h/e)h) different FS predictors each corresponding to a different combination of equivalence classes and asymptotically achieve the performance of the best FS predictor with computational complexity only linear in the pattern length h. Our approach is generic in the sense that it can be applied to general hierarchical equivalence class definitions. Although we work under accumulated square loss as the performance measure, our results hold for a wide range of frameworks and loss functions as detailed in the paper.