Keywords: Human Computer Interaction, Intelligent systems, source coding,
20 questions game, Bayesian Information Gain
Modalities:
• 5-6 months at ISIR (Sorbonne Université, campus Jussieu)
• compensation ∼ 600€/month
• tutors: Julien Gori, (Sorbonne Université, gori@isir.upmc.fr), Olivier Rioul (Institut Polytechnique de Paris, olivier.rioul@telecom-paris.fr)
Context: How can we make our interaction with a computer more efficient?
A solution proposed by Liu et al. is Bayesian Information Gain (BIG): the
computer puts the user in a position where its next action will be maximally
informative (measured with Shannon’s mutual information). For example, if
navigating in a map with a few high probability targets, a system based on BIG
will place the user somewhere in the middle of these targets: indeed, the next
user action will then eliminate most of the potential targets.
Empirical results show that using BIG leads to an impressive decrease in
the number of commands issued by users in a navigating context: from about
35 to only about 5 commands in one condition, but surprisingly, this does not
translate to the same gain in terms of task completion time. Two questions are
thus:
1. Can it be shown that maximizing information gain is equivalent or close
to minimizing the number of user actions?
2. Is it possible to have a system that is more efficient at decreasing interac-
tion time?
On the other hand, the 20 questions game is a guessing game where a ques-
tionner has 20 questions to determine the object an answerer is thinking of.
Interestingly, a connection can be made between BIG, the 20 questions game, and source coding (how to best compress a sequence of symbols). In this internship, we try to reinforce this link, with the promise that we can then exploit
known algorithms from these topics to enhance interaction.
Expected work: The game of 20 questions has many variants, depending on
the potential questions that may be asked (is any question admissible? Are only
comparison questions, that partition the ordered set in two allowed? Are only
questions of restricted size allowed?), and whether the answerer is considered to
make mistakes/lie or not. We have preliminary results that establish that BIG
is equivalent to weight balancing in alphabetic trees for comparison questions.
The tasks of the intern will be to:
• based on a review of existing interactions, list all type of possible question
types (comparison, interval, arbitrary etc.), and determine the state of the
art optimal strategy for the questionner.
• adapt the existing algorithms to minimize either the expected number of
actions or the expected cumulative cost of actions.
• make a link with BIG whenever possible
• implement a demonstrator for one question type e.g., comparison questions
• conduct a controlled experiment to show the objective (minimizing actions,
minimizing interaction time) has indeed been achieved
Depending on the candidate’s profile, the work may focus more on the theoretical side or on the side of conducting experiments.
Candidate Profile:
We are looking for an M2 intern in computer science or
a related field interested in working on applied and theoretical topics, as this
internship requires both. Knowledge of source coding / information theory,
theoretical computer science will be an advantage, and so will be an interest in
computationally modeling human behavior. This topic could be pursued with
a PhD, for which we have already secured funding.