Learning from crowds , where the labels of data instances are collected using a crowdsourcing way, has attracted much attention during the past few years. In contrast to a typical crowdsourcing setting where all data instances are assigned to annotators for labeling,  active learning from crowds actively selects a subset of data instances and assigns them to the annotators, thereby reducing the cost of labeling. This paper goes a step further. Rather than assume all annotators must provide labels, we allow the annotators to express that they are unsure about the assigned data instances. By adding the “unsure” option, the workloads for the annotators are somewhat reduced, because saying “unsure” will be easier than trying to provide a crisp label for some difficult data instances. Moreover, it is safer to use “unsure” feedback than to use labels from reluctant annotators because the latter has more chance to be misleading. Furthermore, different annotators may experience difficulty in different data instances, and thus the unsure option provides a valuable ingredient for modeling crowds’ expertise. We propose the ALCU-SVM algorithm for this new learning problem. Experimental studies on simulated and real crowdsourcing data show that, by exploiting the unsure option, ALCU-SVM achieves very promising performance.

Professor Higgins Professor of Natural Sciences at the School of Engineering and Natural Selman is recognized for expanding our understanding of problem Sciences, Harvard University. Professor Grosz is recognized for her pioneering complexity and developing new algorithms for efficient inference. Previous recipients have been Bernard outstanding young scientists in artificial intelligence. It is currently supported by income Grosz (2001), Alan Bundy (2003), Raj Reddy (2005), Ronald J. Brachman from IJCAI funds. Past recipients of this honor have been Terry (2007), Luigia Carlucci Aiello (2009), Raymond C. Perrault (2011), and Winograd (1971), Patrick Winston (1973), Chuck Rieger (1975), Douglas Wolfgang Wahlster (2013).

Most logic-based machine learning algorithms rely on an Occamist bias where textual complexity of hypotheses is minimised. Within Inductive Logic Programming (ILP), this approach fails to distinguish between the efficiencies of hypothesised programs, such as quick sort (O(n log n)) and bubble sort (O(n 2 )). This paper addresses this issue by considering techniques to minimise both the textual complexity and resource complexity of hypothesised robot strategies. We develop a general framework for the problem of minimising resource complexity and show that on two robot strategy problems, 1) Postman 2) Sorter (recursively sort letters for delivery), the theoretical resource complexities of optimal strategies vary depending on whether objects can be composed within a strategy. The approach considered is an extension of Meta-Interpretive Learning (MIL), a recently developed paradigm in ILP which supports predicate invention and the learning of recursive logic programs. We introduce a new MIL implementation, Metagol O , and prove its convergence, with increasing numbers of randomly chosen examples to optimal strategies of this kind. Our experiments show that Metagol O learns theoretically optimal robot sorting strategies, which is in agreement with the theoretical predictions showing a clear divergence in resource requirements as the number of objects grows. To the authors’ knowledge this paper is the first demonstration of a learning algorithm able to learn optimal resource complexity robot strategies and algorithms for sorting lists.

Currently, there exists a need for simple, easily-accessible methods with which individuals lacking advanced technical training can expand and customize their robot's knowledge.  This work presents a means to satisfy that need, by abstracting the task of training robots to learn about the world around them as a vision- and dialogue-based game, I Spy .  In our implementation of I Spy , robots gradually learn about objects and the concepts that describe those objects through repeated gameplay.  We show that I Spy is an effective approach for teaching robots how to model new concepts using representations comprised of visual attributes.  The results from 255 test games show that the system was able to correctly determine which object the human had in mind 67% of the time.  Furthermore, a model evaluation showed that the system correctly understood the visual representations of its learned concepts with an average of 65% accuracy.  Human accuracy against the same evaluation standard was just 88% on average.

List of committee members on the program committees of the IJCAI 2015 conference.

In this work we evaluate the performance of a policy shaping algorithm using 26 human teachers. We examine if the algorithm is suitable for human-generated data on two different boards in a pac-man domain, comparing performance to an oracle that provides critique based on one known winning policy. Perhaps surprisingly, we show that the data generated by our 26 participants yields even better performance for the agent than data generated by the oracle. This might be because humans do not discourage exploring multiple winning policies. Additionally, we evaluate the impact of different verbal instructions, and different interpretations of silence, finding that the usefulness of data is affected both by what instructions is given to teachers, and how the data is interpreted.

Stable matchings can be computed by deferred acceptance (DA) algorithms. However such algorithms become incomplete when complementarities exist among the agent preferences: they can fail to find a stable matching even when one exists. In this paper we examine stable matching problems arising from labour market with couples (SMP-C). The classical problem of matching residents into hospital programs is an example. Couples introduce complementarities under which DA algorithms become incomplete. In fact, SMP-C is NP-complete. Inspired by advances in SAT and integer programming (IP) solvers we investigate encoding SMP-C into SAT and IP and then using state-of-the-art SAT and IP solvers to solve it. We also implemented two previous DA algorithms. After comparing the performance of these different solution methods we find that encoding to SAT can be surprisingly effective, but that our encoding to IP does not scale as well. Using our SAT encoding we are able to determine that the DA algorithms fail on a non-trivial number of cases where a stable matching exists. The SAT and IP encodings also have the property that they can verify that no stable matching exists, something that the DA algorithms cannot do.

Given a class of students, and a pool of questions in the domain of study, what subset will constitute a good exam? Millions of educators are dealing with this difficult problem worldwide, yet exams are still composed manually in non-systematic ways. In this work we present a novel algorithmic framework for exam composition. Our framework requires two input components: a student population represented by a distribution over overlay models, each consisting of a set of mastered abilities, or actions; and a target model ordering that, given any two student models, defines which should be given the higher grade. To determine the performance of a student model on a potential question, we test whether it satisfies a disjunctive action landmark, i.e., whether its abilities are sufficient to follow at least one solution path. We present a novel utility function for evaluating exams, using the described components. An exam is highly evaluated if it is expected to order the student population with high correlation to the target order.The merit of our algorithmic framework is exemplified with real auto-generated questions in the domain of middle-school algebra.

In this paper we study the exchange of indivisible objects where agents’ possible preferences over the objects are strict and share a common structure among all of them, which represents a certain level of asymmetry among objects. A typical example of such an exchange model is a re-scheduling of tasks over several processors, since all task owners are naturally assumed to prefer that their tasks are assigned to fast processors rather than slow ones. We focus on designing exchange rules (a.k.a.mechanisms) that simultaneously satisfy strategyproofness, individual rationality, and Pareto efficiency. We first provide a general impossibility result for agents’ preferences that are determined in an additive manner, and then show an existence of such an exchange rule for further restricted lexicographic preferences. We finally find that for the restricted case, a previously known equivalence between the single-valuedness of the strict core and the existence of such an exchange rule does not carry over.

We study the stochastic multiple-choice knapsack problem, where a set of Kitems, whose value and weight are random variables, arrive to the system at each time step, and a decision maker has to choose at most one item to put into the knapsack without exceeding its capacity. The goal is the decision-maker is to maximise the total expected value of chosen items with respect to the knapsack capacity and a finite time horizon.We provide the first comprehensive theoretical analysis of the problem. In particular, we propose OPT-S-MCKP, the first algorithm that achieves optimality when the value-weight distributions are known. This algorithm also enjoys O(sqrt{T}) performance loss, where T is the finite time horizon, in the unknown value-weight distributions scenario.We also further develop two novel approximation methods, FR-S-MCKP and G-S-MCKP, and we prove that FR-S-MCKP achieves O(sqrt{T}) performance loss in both known and unknown value-weight distributions cases, while enjoying polynomial computational complexity per time step.On the other hand, G-S-MCKP does not have theoretical guarantees, but it still provides good performance in practice with linear running time.