Online Learning with Automata-based Expert Sequences
We consider a general framework of online learning with expert advice where regret is defined with respect to sequences of experts accepted by a weighted automaton. Our framework covers several problems previously studied, including competing against k-shifting experts. We give a series of algorithms for this problem, including an automata-based algorithm extending weighted-majority and more efficient algorithms based on the notion of failure transitions. We further present efficient algorithms based on an approximation of the competitor automaton, in particular n-gram models obtained by minimizing the \infty-R\'{e}nyi divergence, and present an extensive study of the approximation properties of such models. Finally, we also extend our algorithms and results to the framework of sleeping experts.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Sequential Density Estimation via Nonlinear Continuous Weighted Finite Automata
Weighted finite automata (WFAs) have been widely applied in many fields. One of the classic problems for WFAs is probability distribution estimation over sequences of discrete symbols. Although WFAs have been extended to…
Density EstimationA modular architecture for transparent computation in Recurrent Neural Networks
Computation is classically studied in terms of automata, formal languages and algorithms; yet, the relation between neural dynamics and symbolic representations and operations is still unclear in traditional eliminative …
Active Automata Learning with Adaptive Distinguishing Sequences
This document investigates the integration of adaptive distinguishing sequences into the process of active automata learning (AAL). A novel AAL algorithm "ADT" (adaptive discrimination tree) is developed and presented. S…
Learning Quantitative Automata Modulo Theories
Quantitative automata are useful representations for numerous applications, including modeling probability distributions over sequences to Markov chains and reward machines. Actively learning such automata typically occu…
Active LearningvalidPrediction of Infinite Words with Automata
In the classic problem of sequence prediction, a predictor receives a sequence of values from an emitter and tries to guess the next value before it appears. The predictor masters the emitter if there is a point after wh…
Prediction