The following is a preliminary list of the posters accepted to ICS2010. A list of the posters with titles and authors only may be found here.
- Title: Making a Clever Intelligent Agent: The Theory behind the Implementation
Authors: Roxanne Raine
Abstract: The study of how humans establish mutual understanding is intertwined with the design of artificial conversation systems [1,2,3,4,5]. The focus of this paper is perspectivetaking in and artificial imitation of communication. Regardless of whether an engineer takes psychological theory into consideration when building an agent, an underlying philosophy of perspective-taking is evident when observing the agent's performance. Furthermore, theories of perspectivetaking offer designers an advantage in two ways: 1) These agents could better imitate human behavior. 2) These agents could use common tendencies in human behavior as an advantage in communicating with humans.
- Title: Sufficient Conditions for Agnostic Active Learnable
Authors: Liwei Wang
Abstract: We study pool-based active learning in the presence of noise, i.e. the agnostic setting. Previous works have shown that the effectiveness of agnostic active learning depends on the learning problem and the hypothesis space. Although there are many cases on which active learning is very useful, it is also easy to construct examples that no active learning algorithm can have advantage. In this paper, we propose intuitively reasonable sufficient conditions under which agnostic active learning algorithm is strictly superior to passive supervised learning. We show that under some noise condition, if the Bayesian classification boundary and the underlying distribution are smooth to a finite order, active learning achieves polynomial improvement in the label complexity; if the boundary and the distribution are infinitely smooth, the improvement is exponential.
- Title: An Analysis of the Chaudhuri and Monteleoni Algorithm
Authors: Cynthia Dwork, Parikshit Gopalan, Huijia Lin, Toniann Pitassi, Guy Rothblum, Adam Smith, Sergey Yekhanin
Abstract: Logistic regression is an important machine learning technique, widely used in social science, statistics, physics and many other fields. On a high level, the algorithm takes as input a set of labeled sample data points $X=\{x_1, \dots, x_n\}$, where each $x_i \in R^d$ can be thought of as a set of attribute weights. Each $x_i$ is given a positive or negative label $y_i \in \{-1, 1\}$. The algorithm outputs a vector $w$ of weights that attempts to ``explain'' the data and describe the distribution from which they are drawn; said differently the logistic regression algorithm tries to learn a set of weights on each of the attribute, that ``best'' predicts the probability that a new sample is positive or negative. As data centers collect and analyze -- frequently using logistic regression -- data on vast numbers of people, there has been some investigation of {\em differentially private learning} [KasiviswanathanLNRS08, BeimelNO08, ChaudhuriM08, BlumLR08, McSherryW09]. A very mysterious (to us) algorithm is due to Chaudhuri and Monteleoni [ChaudhuriM08]. This enchanting algorithm departed from the now ``traditional'' methods of either programming via a privacy-preserving interface [BlumDMN05,PINQ] or computing a function and adding to it an amount of noise depending on its {\em sensitivity}, informally, the maximum amount ($\ell_1$-norm) that the addition or deletion of a single point can change the output [DworkMNS06]. Instead, this algorithm, which we denote {\em CM2} as it is the second algorithm in the paper [ChaudhuriM08]), perturbs the objective function of the linear regression optimization problem. The authors of [ChaudhuriM08] report improved experimental performance over the the compute-and-add-noise approach. And while privacy was proved, no upper bound on distortion of the output was put forward. In this work we supply such an analysis. We discover that the distortion, in any direction $u$, of the ``true'' predictor (the one obtained by solving the non-private optimization problem), is bounded by a quantity related to a new notion that we call the {\em directional local sensitivity $DLS_X(u)$}.
- Title: A Structured Wikipedia for Mathematics
Authors: Henry Lin
Abstract: In this paper, we propose an idea for developing a new collaborative online system for storing mathematical work, like Wikipedia, but much more suitable for storing mathematical results and concepts. The system would allow users to store mathematics in a structured manner with the goal of organizing mathematical work so that it would be easier to search and find related work. The structured system would link related mathematical concepts and results, and enable researchers to find relevant mathematical research much more easily. The system would be flexible in terms of letting users decide how much structure to add to each mathematical result or concept in the system, which would ensure that contributors are not burdened with having to add too much structure unnecessarily. Instead, users would be allowed to add just enough structure to link related concepts to make entries easy to search for and locate. The idea proposed in this paper may need additional refinement and improvement, but the author hopes the initial idea presented here serves as a good starting point for further discussion and new ideas.