NESCAI: North East Student Colloquium on Artificial Intelligence

Abstract
Boosted ensemble classifiers have a demonstrated ability to discover regularities in large, poorly modeled datasets. In this paper we present an application of multi-hypothesis AdaBoost to detect epileptic activity from electrophysiological recordings. While existing boosting methods do not account automatically for the sequence information that is available when analyzing time-series data, we present a recurrent extension to AdaBoost, and show that it improves classification accuracy in our application domain.

Abstract
Supervised clustering is the problem of training a clustering algorithm to produce desirable clusterings: given sets of items and complete clusterings over these sets, we learn how to cluster future sets of items. Example applications include noun-phrase coreference clustering, and clustering news articles by whether they refer to the same topic. In this paper we present an SVM algorithm that trains a clustering algorithm by adapting the item-pair similarity measure. The algorithm may optimize a variety of different clustering functions to a variety of clustering performance measures. We empirically evaluate the algorithm for noun-phrase and news article clustering.

Abstract
The use of zero-norm rather than the classical two-norm regularization in Support Vector Machines (SVMs) for binary classification is considered. This converts the easily solvable quadratic program to a NP-complete combinatorial optimization problem. The approach presented here converts the problem to a Mixed Integer Linear Program (MILP) and explores various relaxations. It is shown that these relaxations lead to computationally tractable algorithms and produce solutions that generalize comparably to SVMs while using fewer support vectors.

Abstract
We present a family of approximation techniques for probabilistic graphical models, based on the use of graphical preconditioners developed in the scientific computing literature. Our framework yields rigorous upper and lower bounds on event probabilities and the log partition function of undirected graphical models, using non-iterative procedures that have low time complexity. As in mean-field approaches, the approximations are built upon tractable subgraphs; however, we recast the problem of optimizing the tractable distribution parameters and approximate inference in terms of the well-studied linear systems problem of obtaining a good matrix preconditioner. Experiments are presented that compare the new approximation schemes to variational methods.

Abstract
Factored representations, model-based learning, and hierarchies are well-studied techniques for improving the learning efficiency of reinforcement-learning algorithms in large-scale state spaces. We bring these three ideas together in a new algorithm. Our algorithm tackles two open problems from the reinforcement-learning literature, and provides a solution to those problems in deterministic domains. First, it shows how models can improve learning speed in the hierarchy-based MaxQ framework without disrupting opportunities for state abstraction. Second, we show how hierarchies can augment existing factored exploration algorithms to achieve not only low sample complexity for learning, but provably efficient planning as well. We illustrate the resulting performance gains in example domains. We prove polynomial bounds on the computational effort needed to attain near optimal performance within the hierarchy.

Abstract
Neural networks have been used very successfully to represent value functions for reinforcement learning algorithms in several applications. However, considerable hand-crafting is needed in order to obtain a good network structure. To address this problem, cite{rivest03combining} proposed an approach to using cascade correlation neural networks with reinforcement learning. Their approach relies on a cache of data, which is used to accumulate a batch of patterns for training the network. In this paper, we explore a version of cascade correlation which has a more on-line flavor. Empirical results on the game of Backgammon show that the variations we discuss are more robust to the noise inherent in RL tasks.

Abstract
This paper takes an empirical approach to evaluating three model-based reinforcement-learning methods. All methods intend to speed the learning process by mixing exploitation of learned knowledge with exploration of possibly promising alternatives. We consider $epsilon$-greedy exploration, which is computationally cheap and popular, but unfocused in its exploration effort; R-Max exploration, a simplification of an exploration scheme that comes with a theoretical guarantee of efficiency; and a well-grounded approach, model-based interval estimation, that better integrates exploration and exploitation. Our experiments indicate that effective exploration can result in dramatic improvements in the observed rate of learning.

Abstract
Conformant planners solve problems with a correct but incomplete description of the initial state, by finding plans that are valid for all possible assignments of the unknown atoms. Most conformant planners, however, do not handle universal quantification, which is a problem when the set of all domain objects is unknown or very large, and thus can not be enumerated. This paper discusses PSIGRAPH, a conformant planner that operates with universally quantified statements in the initial and goal states, as well as in the action preconditions. Thus, PSIGRAPH does not need to know the complete set of domain objects. PSIGRAPH is based on Graphplan (Blum and Furst 1995), but differs from previous approaches such as Conformant Graphplan (Smith and Weld 1998) in that it does not create multiple planning graphs. We present the algorithm and the results of its experimental evaluation, showing that PSIGRAPH is competitive with other planners. Finally, we discuss recent additions to the algorithm that have been performed since the original publication of PSIGRAPH.

Abstract
This paper develops a general, formal framework for modeling term dependencies via Markov random fields. The model allows for arbitrary text features to be incorporated as evidence. In particular, we make use of features based on occurrences of single terms, ordered phrases, and unordered phrases. We explore full independence, sequential dependence, and full dependence variants of the model. A novel approach is developed to train the model by directly maximizing mean average precision. Our results show that significant improvements are possible by modeling dependencies, especially on larger web collections.

Abstract
In information retrieval, the cluster hypothesis states: closely related documents tend to be relevant to the same request. We exploit this hypothesis directly by adjusting query-based information retrieval scores from an initial retrieval so that topically related documents receive similar scores. We refer to this process as score regularization. Score regularization can be presented as an optimization problem, allowing the use of results from semi-supervised learning. We demonstrate that regularized scores consistently and significantly rank documents better than un-regularized scores, given a variety of initial retrieval algorithms.

Abstract
Some models of textual corpora employ text generation methods involving n-gram statistics, while others use latent topic variables inferred using the "bag-of-words" assumption, in which word order is ignored. Previously, these methods have not been combined. In this work, I explore a hierarchical generative probabilistic model that incorporates both n-gram statistics and latent topic variables by extending a unigram topic model to include properties of a hierarchical Dirichlet bigram language model. The model hyperparameters are inferred using a Gibbs EM algorithm. On two data sets, each of 150 documents, the new model exhibits better predictive accuracy than either a hierarchical Dirichlet bigram language model or a unigram topic model. Additionally, the inferred topics are less dominated by function words than are topics discovered using unigram statistics, potentially making them more meaningful.

Abstract
We address the symbol grounding problem for robot perception through a data-driven approach to deriving sensor categories. Unlike model-based approaches, our method learns intrinsic categories (or natural kinds) from the raw data itself. We approximate a manifold underlying sensor data using Isomap nonlinear dimension reduction and apply Bayesian clustering (Gaussian mixture models) to discover categories. We demonstrate our method through the learning of sensory kinds from trials in various indoor environments with multiple sensor modalities. Learned kinds are used to classify new sensor data (out-of-sample readings). We present results indicating greater consistency in classifying sensor data employing mixture models in low-dimensional embeddings.

Abstract
We present a method for training a similarity metric from data. The method can be used for recognition or verification applications where the number of categories is very large and not known during training, and where the number of training samples for a single category is very small. The idea is to learn a function that maps input patterns into a target space such that the $L_1$ norm in the target space approximates the ``semantic'' distance in the input space. The method is applied to a face verification task, using the Purdue/AR face database which has a very high degree of variability in pose, lighting, expression, and position, and includes artificial occlusions such as dark glasses and obscuring scarves.

Abstract
Dimensionality reduction involves mapping a set of high dimensional input points onto a low dimensional manifold so that ``similar" points in input space are mapped to nearby points on the manifold. We present a method - called Dimensionality Reduction by Learning an Invariant Mapping (DrLIM) - for learning a globally coherent non-linear function that maps the data evenly to the output manifold. The learning relies solely on neighborhood relationships and does not require any distance measure in the input space. The method can learn mappings that are invariant to certain transformations of the inputs, as is demonstrated with a number of experiments. Comparisons are made to other techniques, in particular LLE.

Abstract
Most existing approaches to clustering gene expression time course data treat the different time points as independent dimensions and are invariant to permutations, such as reversal, of the experimental time course. Approaches utilizing HMMs have been shown to be helpful in this regard, but are hampered by having to choose model architectures with appropriate complexities. Here we propose for a clustering application an HMM with a countably infinite state space; inference in this model is possible by recasting it in the hierarchical Dirichlet process (HDP) framework (Teh et al. 2006), and hence we call it the HDP-HMM. We show that the infinite model outperforms model selection methods over finite models, and traditional time-independent methods, as measured by a variety of external and internal indices for clustering on two large publicly available data sets. Moreover, we show that the infinite models utilize more hidden states and employ richer architectures (e.g. state-to-state transitions) without the damaging effects of overfitting.

Abstract
Automated software customization is drawing increasing attention as a means to help users deal with the scope, complexity, potential intrusiveness, and ever-changing nature of modern software. The ability to automatically customize functionality, interfaces, and advice to specific users is made more difficult by the uncertainty about the needs of specific individuals and their preferences for interaction. Following recent probabilistic techniques in user modeling, we model our user with a dynamic Bayesian network (DBN) and propose to explicitly infer the ``user's type'' --- a composite of personality and affect variables --- in real time. We design the system to reason about the impact of its actions given the user's current state. Our simulations show that user types can be inferred quickly and that a myopic policy offers considerable benefit by adapting to both different types and changing attitudes. We then develop a more realistic user model, using behavioural data from 45 users to learn model parameters and the topology of our proposed user types. With the new model, we conduct a usability experiment with 4 users and 4 different policies. These experiments, while preliminary, show encouraging results for our adaptive policy.

Abstract
With the emergence and widespread use of Tablet PCs, recognizing freehand sketches has gained importance as an enabling technology for pen-based intelligent human computer interfaces. This paper presents a sketch recognition framework based on multiscale statistical models of temporal patterns. Previous work in sketch recognition has shown that in certain domains, stroke orderings used in the course of drawing individual objects contain temporal patterns that can aid recognition. We build on this work to show how sketch recognition systems can use knowledge of both common stroke orderings and common object orderings. We describe a statistical framework based on Dynamic Bayesian Networks that can learn temporal models of object-level and stroke-level patterns for recognition. Our recognition framework supports multi-object strokes, multi-stroke objects, and it supports real-valued feature representations using a numerically stable recognition algorithm. We present recognition results for handdrawn electronic circuit diagrams. The results show that modeling temporal patterns at multiple scales provides a significant increase in correct recognition rates, with no added computational penalties.

Abstract
Classic direct mechanisms suffer from the drawback of requiring full type revelation from participating agents. In complex settings with multi-attribute utility, assessing utility functions can be very difficult, a problem addressed by recent work on preference elicitation. In this work we propose a framework for incremental, partial revelation mechanisms and study the use of \emph{minimax regret} as an optimization criterion for allocation determination with type uncertainty. We examine the incentive properties of incremental mechanisms when minimax regret is used to determine allocations with no additional elicitation of payment information; and when additional payment information is obtained. We argue that elicitation effort can be focused simultaneously on reducing allocation and payment uncertainty.

Abstract
Developing scalable algorithms for solving partially observable Markov decision processes (POMDPs) is an important challenge. One promising approach is based on representing POMDP policies as finite-state controllers. This method has been used successfully to address the intractable memory requirements that have limited POMDP algorithms. We illustrate some fundamental disadvantages of existing techniques that use controllers. We then propose a new approach that formulates the problem as a quadratically constrained linear program (QCLP), the optimal solution of which provides an optimal controller of a desired size. We consider a leading optimization method for solving QCLPs and compare its performance with existing POMDP optimization methods. While the optimization algorithm used in this paper only guarantees local optimality, it produces consistent solution quality improvement over the state-of-the-art techniques. The results show that powerful nonlinear programming methods can be used effectively to improve the performance and scalability of POMDP algorithms.

Abstract
We present an asymptotically optimal algorithm for the max variant of the k-armed bandit problem. Given a set of k slot machines, each yielding payoff from a fixed (but unknown) distribution, we wish to allocate trials to the machines so as to maximize the expected maximum payoff received over a series of n trials. Subject to certain distributional assumptions, we show that O ( ln (1/delta) ln(n)^2 / epsilon^2 ) trials are sufficient to identify, with probability at least 1-delta, a machine whose expected maximum payoff is within epsilon of optimal. This result leads to a strategy for solving the problem that is asymptotically optimal in the following sense: the gap between the expected maximum payoff obtained by using our strategy for n trials and that obtained by pulling the single best arm for all n trials approaches zero as n -> infinity.