From Data to Knowledge - 405 - Borja Balle
Channel: ckleinastro
Date: 2012-05-10

Slides: http://lyra.berkeley.edu/CDIConf/pdfs/borja-balle-slides.pdf

Borja Balle: "Learning Markovian Models from Time-Evolving Data Streams". A video from the UC Berkeley Conference: From Data to Knowledge: Machine-Learning with Real-time and Streaming Applications (May 7-11, 2012).

Abstract
Borja Balle (Universitat Politecnica de Catalunya, CS)
Markovian models with hidden state are widely-used formalisms for modeling sequential phenomena. Learnability of these models has been well studied when the sample is given in batch mode, and algorithms with PAC-like learning guarantees exist for specific classes of models such as Probabilistic Deterministic Finite Automata (PDFA). Our work focuses on PDFA and gives, to the best our knowledge, the first algorithm for infering models in this class under the stringent data stream scenario: unlike existing methods, our algorithm works incrementally and in one pass, uses memory sublinear in the stream length, processes input items in amortized constant time, and can react to drift revising the model and forgetting past irrelevant information. We provide rigorous guarantees for all of the above, as well as an evaluation on realistic synthetic data. Our algorithm makes a key usage of several old and new sketching techniques. In particular, we develop a new sketch for implementing bootstrapped statistical tests in a streaming setting which may be of independent interest. Experimentaly we observe that this sketch yields order-of-magnitude reductions in the examples required for performing some crucial statistical tests in our algorithm.