DIMACS
DIMACS REU [2016]

General Information

me
Student: Gautam Ramasubramanian
Office: Sarwate's Lab - CoRE Room 531
School: The City College of New York
Major: Computer Engineering
E-mail: ramasubg2@gmail.com
Project: Active learning with label-based costs + Communication with feedback

Project Description

Number Guessing Game

Weekly Log

Week 1:

My Research Project (What I think it is right now)

My research is on active learning, and statistical learning theory. I am to assist in deriving some theoretical result concerning active learning.

What I have done

I have talked to my mentor, Professor Sarwate, on Thursday, in order to get a better idea on my research topic. My initial idea was that my research was on active learning, but it is actually on a specific idea, a specific game, that has applications in both active learning and communications with feedback. I have made some LaTeX papers on background material related to active learning, but I also did some math to attempt to analyze that idea. I have also made my presentation. See Presentation #1.
Week 2:

My Research Project (What I think it is right now)

My research is on the number guessing game. There are numbers in a set (1-n), and an oracle is thinking of one number. The player queries a number, and the oracle will tell you whether the number is higher or lower or the same. There is a cost for guessing a higher number and there is a cost for guessing the lower number. The basic task is to find the stategy, sequence of queries, that guesses oracle's number with the least cost.

What I have done

I introduced a heuristic risk function, which included a measure of the costs and a measure of the size of the remaining numbers you are left with after the oracle deems your guess too high or too low. The goal of an "optimal" strategy would be to minimize the expected risk at each turn. I assumed that minimizing the risk greedily at every step leads to the optimal strategy. With a little math, I was able to come up with the quartile search to be the "optimal" strategy. See An Approach to analyzing the Number Guessing Game. I also came up with elementary brute force results with n=3,4. See Results from Brute Force Analysis of Number Guessing Game for Small n.
Week 3:

My Research Project (What I think it is right now)

My research is on the number guessing game, in continuous case. An oracle is thinking of a real number from 0 to 1 inclusive, and a player will guess a number, and the oracle will tell you whether the number is higher or lower. There is also a probability p less than 1/2 that the oracle is wrong in its verdict of too high or too low. This p is constant for all guesses. There is a cost for guessing a higher number and there is a cost for guessing the lower number. The task is to find a strategy, sequency of guesses, that acheieves low error with low cost (vague).

What I have done

The Probabilistic Bisection Algorithm has been shown to achieve "optimality" when the cost of too high and too low are the same. The algorithm works under the noise conditions described above. My job was to generalize that algorithm to include asymmetric cost structures. I used the same risk function idea, and applied it to Probabilistic Bisection Algorithm to get a quantile search algorithm. See Probabilistic Quartile Search. I also coded up both Probabilistic Bisection and Probabilistic Quantile Search Strategies in C. See Zip File of PBA and PQS.
Week 4:

My Research Project (What I think it is right now)

My research is on active learning. Specifically, trying to isolate a threshold or a separator that separated 1-D data. The separator separated data labeled -1 from data labeled +1, but all of the data labels are initially unknown, and can only be known by querying. We assume the pool of data lie between 0 and 1 on the x-axis, and that -1s are to the right, while +1s are to the left. The oracle is queried for data labels, and there is a probability p less than 1/2 that oracle gives you wrong label. An equivalent formulation will be that the separator does not separate perfectly, and there may be +1s to the right and -1s to the left (This is actually not equivalent but I thought so at the time). There are costs associated with getting a verdict of +1 vs -1. What is the best strategy to locate the threshold with minimum cost.

What I have done

Reading up on a bunch of papers. Trying to see the research landscape in my area, and where my work would fit in.
Week 5:

My Research Project (What I think it is right now)

There are two settings.
The first is a pool based setting, which is most like active learning. There is a bunch of 1-D data lying in the x-axis between 0 and 1. This data is unlabelled, and cannot be perfectly separated by a threshold. The task is to find the best threshold that separates the data with the least amount of error. You are allowed to query the data, and the result of the query is 100% correct. How do you query the data as to converge to the threshold with the least error. Bayesian schemes like Probabilistic Bisection will not work in the pool-based setting, as they are prone to sampling bias.
The second is the interval-membership setting, where there exists a theta, an unknown real number, between 0 and 1. The task is to find theta with the most precision. You can choose intervals, and query an oracle, which will tell you whether theta is in the queried interval or not. The oracle has a nonzero probability of being wrong when it delivers a verdict to a query.
The task is to introduce a notion of label-based cost to either or both models.

What I have done

Still reading. Narrowing down my research question. (Add more stuff here this week)

Relevant Scientific Papers

Presentations

LaTeX papers

Code

Additional Information