Log In

An online learning game

Posted on: November 21st, 2013 by
Comments Disabled

Suppose X_1(t),X_2(t),\dots X_n(t) are input bits (i.e. 0 or 1) at time t, and Y(t) is the output bit. You are given samples for t=1,2,3,4,\dots. You know that Y(t) is the OR (or disjunction) of a subset of X_1(t),X_2(t),\dots X_n(t). For example Y=X_1 OR X_n, Y=X_3 OR X_5 OR X_6. You want to use online learning to learn the function that maps the inputs X_1,\dots X_n to Y. At each time t, you will try to predict the output Y(t) given the input X_1(t),X_2(t),\dots X_n(t). Every time you make a mistake in your prediction, I will charge you $1. Y(t) is the OR (or disjuction) of exactly k values among X_1(t)\dots X_n(t). I am free to choose the input samples (X_1(t),X_2(t)\dots X_n(t). I will first ask you for the output Y(t). If you are wrong, I will tell the correct value of Y(t) and charge you $1. How will you minimize your loss if I play optimally to maximize your minimum loss? What is that minimum loss? We need the optimal online learning algorithm.

- Via Subhashini V

Comments are closed.

{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}