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
uri: http://hdl.handle.net/1721.1/7107
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

Item sets: AI Technical Reports (1964 - 2004)