Online Learning of Non-stationary Sequences
Item
-
Title
-
en_US
Online Learning of Non-stationary Sequences
-
Creator
-
en_US
Monteleoni, Claire
-
Date
-
2004-10-20T20:32:01Z
-
Date Available
-
2004-10-20T20:32:01Z
-
Date Issued
-
en_US
2003-06-12
-
Identifier
-
en_US
AITR-2003-011
-
Abstract
-
en_US
We consider an online learning scenario in which the learner can make predictions on the basis of a fixed set of experts. The performance of each expert may change over time in a manner unknown to the learner. We formulate a class of universal learning algorithms for this problem by expressing them as simple Bayesian algorithms operating on models analogous to Hidden Markov Models (HMMs). We derive a new performance bound for such algorithms which is considerably simpler than existing bounds. The bound provides the basis for learning the rate at which the identity of the optimal expert switches over time. We find an analytic expression for the a priori resolution at which we need to learn the rate parameter. We extend our scalar switching-rate result to models of the switching-rate that are governed by a matrix of parameters, i.e. arbitrary homogeneous HMMs. We apply and examine our algorithm in the context of the problem of energy management in wireless networks. We analyze the new results in the framework of Information Theory.
-
Extent
-
en_US
48 p.
-
1815576 bytes
-
911860 bytes
-
Format
-
application/postscript
-
application/pdf
-
Language
-
en_US
-
Relation
-
en_US
AITR-2003-011
-
Subject
-
en_US
AI
-
en_US
online learning
-
en_US
relative loss bounds
-
en_US
switching dynamics
-
en_US
wireless
-
en_US
802.11