Combining the normal hedge algorithm with weighted trees for predicting binary sequences.

摘要

This thesis presents the use of an online learning hedging technique to predict patterns in a binary sequence. It is compared to previous techniques. This technique, referenced as Normal Hedge Tree, has faster learning rates for patterns and suffers less regret with respect to Hedge(eta) [FS99, FS95] with synthetically generated sequences. Normal Hedge Tree is compared to Mindreader [Dos] over previously collected sequences. Overall, Normal Hedge Tree performs worse than Mindreader but for some sequences it has better results. We combine the two algorithms using Normal Hedge [CFH09], but the combination performs worse than either of the algorithms taken singularly.