Proceedings of the Eleventh International Conference on Grammatical Inference, PMLR 21:34-48, 2012.
Abstract
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). Here we focus on PDFA and give an algorithm for infering models in this class under the stringent \emphdata stream scenario: unlike existing methods, our algorithm works incrementally and in one pass, uses memory sublinear in the stream length, and processes input items in amortized constant time. We provide rigorous PAC-like bounds for all of the above, as well as an evaluation on synthetic data showing that the algorithm performs well in practice. Our algorithm makes a key usage of several old and new sketching techniques. In particular, we develop a new sketch for implementing bootstrapping in a streaming setting which may be of independent interest. In experiments we have observed that this sketch yields important reductions in the examples required for performing some crucial statistical tests in our algorithm.
@InProceedings{pmlr-v21-balle12a,
title = {Bootstrapping and Learning PDFA in Data Streams},
author = {Borja Balle and Jorge Castro and Ricard Gavaldà},
booktitle = {Proceedings of the Eleventh International Conference on Grammatical Inference},
pages = {34--48},
year = {2012},
editor = {Jeffrey Heinz and Colin Higuera and Tim Oates},
volume = {21},
series = {Proceedings of Machine Learning Research},
address = {University of Maryland, College Park, MD, USA},
month = {05--08 Sep},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v21/balle12a/balle12a.pdf},
url = {http://proceedings.mlr.press/v21/balle12a.html},
abstract = {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). Here we focus on PDFA and give an algorithm for infering models in this class under the stringent \emphdata stream scenario: unlike existing methods, our algorithm works incrementally and in one pass, uses memory sublinear in the stream length, and processes input items in amortized constant time. We provide rigorous PAC-like bounds for all of the above, as well as an evaluation on synthetic data showing that the algorithm performs well in practice. Our algorithm makes a key usage of several old and new sketching techniques. In particular, we develop a new sketch for implementing bootstrapping in a streaming setting which may be of independent interest. In experiments we have observed that this sketch yields important reductions in the examples required for performing some crucial statistical tests in our algorithm.}
}
%0 Conference Paper
%T Bootstrapping and Learning PDFA in Data Streams
%A Borja Balle
%A Jorge Castro
%A Ricard Gavaldà
%B Proceedings of the Eleventh International Conference on Grammatical Inference
%C Proceedings of Machine Learning Research
%D 2012
%E Jeffrey Heinz
%E Colin Higuera
%E Tim Oates
%F pmlr-v21-balle12a
%I PMLR
%J Proceedings of Machine Learning Research
%P 34--48
%U http://proceedings.mlr.press
%V 21
%W PMLR
%X 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). Here we focus on PDFA and give an algorithm for infering models in this class under the stringent \emphdata stream scenario: unlike existing methods, our algorithm works incrementally and in one pass, uses memory sublinear in the stream length, and processes input items in amortized constant time. We provide rigorous PAC-like bounds for all of the above, as well as an evaluation on synthetic data showing that the algorithm performs well in practice. Our algorithm makes a key usage of several old and new sketching techniques. In particular, we develop a new sketch for implementing bootstrapping in a streaming setting which may be of independent interest. In experiments we have observed that this sketch yields important reductions in the examples required for performing some crucial statistical tests in our algorithm.
TY - CPAPER
TI - Bootstrapping and Learning PDFA in Data Streams
AU - Borja Balle
AU - Jorge Castro
AU - Ricard Gavaldà
BT - Proceedings of the Eleventh International Conference on Grammatical Inference
PY - 2012/08/16
DA - 2012/08/16
ED - Jeffrey Heinz
ED - Colin Higuera
ED - Tim Oates
ID - pmlr-v21-balle12a
PB - PMLR
SP - 34
DP - PMLR
EP - 48
L1 - http://proceedings.mlr.press/v21/balle12a/balle12a.pdf
UR - http://proceedings.mlr.press/v21/balle12a.html
AB - 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). Here we focus on PDFA and give an algorithm for infering models in this class under the stringent \emphdata stream scenario: unlike existing methods, our algorithm works incrementally and in one pass, uses memory sublinear in the stream length, and processes input items in amortized constant time. We provide rigorous PAC-like bounds for all of the above, as well as an evaluation on synthetic data showing that the algorithm performs well in practice. Our algorithm makes a key usage of several old and new sketching techniques. In particular, we develop a new sketch for implementing bootstrapping in a streaming setting which may be of independent interest. In experiments we have observed that this sketch yields important reductions in the examples required for performing some crucial statistical tests in our algorithm.
ER -
Balle, B., Castro, J. & Gavaldà, R.. (2012). Bootstrapping and Learning PDFA in Data Streams. Proceedings of the Eleventh International Conference on Grammatical Inference, in PMLR 21:34-48
This site last compiled Sun, 15 Jul 2018 07:31:50 +0000