WORST CASE PREDICTION OVER SEQUENCES UNDER LOG LOSS
Dr Manfred Opper, NCRG, Aston University, Birmingham (present address: Isaac Newton Institute, Cambridge)
Joint work with Professor David Haussler, University of California Santa Cruz

Abstract: We consider the game of sequentially assigning probabilities to future data based on past observations under logarithmic loss. We are not making probabilistic assumptions about the generation of the data, but consider a situation, where a player tries to minimize his loss relative to the loss of the (with hindsight) best distribution from a target class for the worst sequence of data. We give bounds on the minimax regret in terms of the metric entropies of the target class with respect to suitable distances between distributions. Surprisingly, for many interesting target classes, the extra knowledge that the sequence was generated at random from a distribution of the class does not lead to much smaller extra losses.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 5 November 1997

back