Defensive Prediction with Expert Advice

Author: Vladimir Vovk

Source: Algorithmic Learning Theory, 16th International Conference, ALT 2005, Singapore, October 2005, Proceedings, (Sanjay Jain, Hans Ulrich Simon and Etsuji Tomita, Eds.), Lecture Notes in Artificial Intelligence 3734, pp. 444 - 458, Springer 2005.

Abstract. inite-dimensional pools of experts. In this paper we give similar results for pools of decision rules belonging to an infinite-dimensional functional space which we call the Fermi–Sobolev space. For example, it is shown that for a wide class of loss functions (including the standard square, absolute, and log loss functions) the average loss of the master algorithm, over the first N steps, does not exceed the average loss of the best decision rule with a bounded Fermi–Sobolev norm plus O(N–1/2). Our proof techniques are very different from the standard ones and are based on recent results about defensive forecasting. Given the probabilities produced by a defensive forecasting algorithm, which are known to be well calibrated and to have high resolution in the long run, we use the Expected Loss Minimization principle to find a suitable decision.

©Copyright 2005, Springer