NESCAI07: The Second North East Student Colloquium on Artificial Intelligence

Abstract
Many tasks require finding groups of elements in a matrix of numbers, symbols or class likelihoods. One approach is to use efficient bi- or tri-linear factorization techniques including PCA, ICA, sparse matrix factorization and plaid analysis. These techniques are not appropriate when addition and multiplication of matrix elements are not sensibly defined. More directly, methods like bi-clustering can be used to classify matrix elements, but these methods make the overly-restrictive assumption that the class of each element is a function of a row class and a column class. We introduce a general computational problem, `matrix tile analysis' (MTA), which consists of decomposing a matrix into a set of non-overlapping tiles, each of which is defined by a subset of usually nonadjacent rows and columns. MTA does not require an algebra for combining tiles, but must search over an exponential number of discrete combinations of tile assignments. We describe a loopy BP(sum-product) algorithm and an ICM algorithm for performing MTA. We compare the effectiveness of these methods to PCA and the plaid method on hundreds of randomly generated tasks. Using double-gene-knockout data, we show that MTA finds groups of interacting yeast genes that have biologically-related functions.

Abstract
Faceted classification is a flexible way of organizing information based on mutiple independent labelings. Faceting is usually contrasted with clustering. Both have similar objectives of organizing data, but while clustering does this in an automated way, faceting requires considerable manual labeling. In this paper we aim to solve the problem of generating these facets automatically. We propose a modification of the CPCM algorithm, the Ortho-CPCM to solve this orthogonal clustering problem. The resulting clusters inherit properties of CPCM, namely invariance to linear transformations and tend to eliminate noise features by driving their weights to zero.

Abstract
The objects in many real-world domains can be organized into hierarchies, where each internal node picks out a category of objects. Given a collection of fea- tures and relations defined over a set of objects, an annotated hierarchy includes a specification of the categories that are most useful for describing each individual feature and relation. We define a generative model for annotated hierarchies and the features and relations that they describe, and develop a Markov chain Monte Carlo scheme for learning annotated hierarchies. We show that our model discov- ers interpretable structure in several real-world data sets.

Abstract
In this paper we propose a suite of techniques for planning with temporally extended preferences (TEPs). To this end, we propose a method for compiling TEP planning problems into simpler domains containing only final-state (simple) preferences and metric functions. With this simplified problem in hand, we propose a variety of heuristic functions for planning with final-state preferences, together with an incremental best-first planning algorithm. A key feature of the planning algorithm is its ability to prune the search space. We identify conditions under which our planning algorithm will generate optimal plans. We implemented our algorithm as an extension to the TLPlan planning system and report on extensive testing performed to evaluate the effectiveness of our heuristics and algorithm. Our planner, HPlan-P, competed in the 5th International Planning Competition, achieving distinguished performance in the qualitative preferences track.

Abstract
Partially Observable Markov Decision Processes (POMDPs) provide a rich mathematical framework for planning under uncertainty. However, most real world systems are modelled by huge POMDPs that cannot be solved due to their high complexity. To palliate to this difficulty, we propose combining existing offline approaches with an online search process, called AEMS, that can improve locally an approximate policy computed offline, by reducing its error and providing better performance guarantees. We propose different heuristics to guide this search process, and provide theoretical guarantees on the convergence to epsilon-optimal solutions. Our experimental results show that our approach can provide better solution quality within a smaller overall time than state-of-the-art algorithms and allow for interesting online/offline computation tradeoff.

Abstract
Scalability of algorithms for solving decentralized POMDPs presents a major research challenge because of its double exponential worst-case complexity. Initial algorithms have only been able to solve very small problems. One exception is the Memory-Bounded Dynamic Programming (MBDP) algorithm--an approximation technique that has proved extremely efficient in handling large problem horizons. In this paper we make several key contributions. We generalize the MBDP algorithm and improve its scalability by reducing the complexity with respect to the size of the observation space from exponential to polynomial. We derive error bounds on solution quality with respect to this new approximation and analyze the convergence behavior. To evaluate the effectiveness of the improvements we introduce a new, larger benchmark problem. Preliminary experimental results show that despite the high complexity of decentralized POMDPs, scalable solution techniques such as MBDP perform surprisingly well. Finally, we discuss a challenging open research question and conclude with promising future directions of research.

Abstract
Collaborative filtering attempts to find items of interest for a user by utilizing the preferences of other users. In this paper we describe an approach to filtering that explicitly uses social relationships, such as friendship, to find items of interest to a user. Modeling user-item relations as a bipartite graph we augment it with user-user (social) links and propose an absorbing random walk that induces a set of stationary distributions, one per user, over all items. These distributions can be interpreted as personalized rankings for each user. We exploit sparsity of both user-item and user-user relationships to improve the efficiency of our algorithm.

Abstract
An essential part of an expert-finding task, such as matching reviewers to submitted papers, is the ability to model the expertise of a person based on documents. We evaluate several measures of the association between an author in an existing collection of research papers and a previously unseen document. We compare two language model based approaches with a novel topic model, Author-Persona-Topic (APT). In this model, each author can write under one or more "personas", which are represented as independent distributions over hidden topics. Examples of previous papers written by prospective reviewers are gathered from the Rexa database, which extracts and disambiguates author mentions from documents gathered from the web. We evaluate the models using a reviewer matching task based on human relevance judgments determining how well the expertise of proposed reviewers matches a submission. We find that the APT topic model outperforms the other models.

Abstract
Discovery of additive structure is an important step towards understanding a complex multi-dimensional function, because it allows for expressing this function as the sum of lower-dimensional components. When variables interact, their effects cannot be decomposed into independent lower-dimensional contributions and hence must be modeled simultaneously. Variable interactions make learning harder and complicate the analysis of the relationships between predictors and response. A method that reliably determined which variables do and do not interact would make model interpretation much simpler. We propose a new approach for the problem of interaction detection based on comparing performance of different regression models. Our method is based on a new machine learning algorithm, a grove of trees, which combines additive models with regression trees in a way that allows variable interactions to be carefully controlled. By comparing the performance of restricted and unrestricted groves of trees, the existence and degree of variable interactions in the response function can be reliably detected and estimated.

Abstract
We present a solution to the problem of long-range obstacle/path recognition in autonomous robots. The system uses sparse traversability information from a stereo module to train a classifier online. The trained classifier can then predict the traversability of the entire scene. A distance-normalized image pyramid makes it possible to efficiently train on each frame seen by the robot, using large windows that contain contextual information as well as shape, color, and texture. Traversability labels are initially obtained for each target using a stereo module, then propagated to other views of the same target using temporal and spatial concurrences, thus training the classifier to be view-invariant. A ring buffer simulates short-term memory and ensures that the discriminative learning is balanced and consistent. This long-range obstacle detection system sees obstacles and paths at 30-40 meters, far beyond the maximum stereo range of 12 meters, and adapts very quickly to new environments. Experiments were run on the LAGR robot platform.

Abstract
Our research explores the design of a new generation of implantable electrical stimulation devices for the treatment of epilepsy. These devices would implement an adaptive stimulation strategy by incorporating feedback from a sensor to monitor the patient's status. This adaptive approach could improve both the efficiency and the efficacy of the device. We describe a reinforcement learning agent that could serve as the control algorithm in such a device. We also present a biologically plausible model of an epileptic neural network using integrate-and-fire neurons with partially stochastic inputs and multiple time scales of firing-dependent inhibitory behavior. We show that this network can exhibit behavior ranging from gentle random firing to the violent hypersynchronous activation which is characteristic of epilepsy. We train the reinforcement learning agent to control the dynamics of this network and reduce the occurrence of seizure-like events.

Abstract
We present black-box techniques for learning how to interleave the execution of multiple heuristics in order to improve average-case performance. In our model, a user is given a set of heuristics whose only observable behavior is their running time. Each heuristic can compute a solution to any problem instance, but its running time varies across instances. The user solves each instance by interleaving runs of the heuristics according to a task-switching schedule. We present (i) exact and approximation algorithms for computing an optimal task-switching schedule offline, (ii) sample complexity bounds for learning a task-switching schedule from training data, and (iii) a no-regret strategy for selecting task-switching schedules online. We demonstrate the power of our results using data from recent solver competitions. We outline how to extend our results to the case in which the heuristics are randomized, and the user may periodically restart each heuristic with a fresh random seed.

Abstract
We address the task of learning rankings of documents from search engine logs of user behavior. Previous work on this problem has relied on passively collected clickthrough data. In contrast, we show that an active exploration strategy can provide data that leads to much faster learning. Specifically, we develop a Bayesian approach for selecting rankings to present users so that interations result in more informative training data. Our results using the TREC-10 Web corpus, as well as synthetic data, demonstrate that a directed exploration strategy quickly leads to users being presented improved rankings in an online learning setting. We find that active exploration substantially outperforms passive observation and random exploration.

Abstract
In this paper, we survey a variety of current state-of-art models for structured learning problems, such as Hidden Markov Model (HMM), Conditional Random Fields (CRF), Averaged Perceptron (AP), Support Vector Machine for structured output ($SVM^{struct}$), Max Margin Markov Networks (M$^3$N), and an integration of search and learning algorithm (SEARN). With all due tuning efforts of various parameters of each model, on the data sets we have applied the models to, we found that SVM$^{struct}$ enjoys better performance compared with the others. We also propose a new Structured Learning Ensemble (SLE) method to combine these structured learning models. Empirical results show that our SLE algorithm is able to provide more accurate solutions compared with the best results of the individual models.

Abstract
Automatic sentiment classification has been extensively studied and applied in recent years. However, sentiment is expressed differently in different domains, and annotating corpora for every possible domain of interest is impractical. We investigate domain adaptation for sentiment classifiers, focusing on online reviews for different types of products. First, we extend to sentiment classification the recently-proposed structural correspondence learning (SCL) algorithm, reducing the relative error due to adaptation between domains by an average of 30% over the original SCL algorithm and 46% over a supervised baseline. Second, we identify a measure of domain similarity that correlates well with the potential for adaptation of a classifier from one domain to another. This measure could for instance be used to select a small set of domains to annotate whose trained classifiers would transfer well to many other domains.

Abstract
We study the complexity of influencing elections through bribery: How computationally complex is it for an external actor to determine whether by a certain amount of bribing voters a specified candidate can be made the election's winner? For example, we provide a complete classification of the complexity of bribery for the broad class of elections (including plurality, Borda, k-approval, and veto) known as scoring protocols.

Abstract
We present a new probabilistic framework for finding likely variable assignments in difficult constraint satisfaction problems. Finding such assignments is key to efficient search, but practical efforts have largely been limited to random guessing and heuristically designed weighting systems. In contrast, we derive a new version of Belief Propagation (BP) using the method of Expectation Maximization (EM). This allows us to differentiate between variables that are strongly biased toward particular values and those that are largely extraneous. Using EM also eliminates the threat of nonconvergence associated with regular BP. Theoretically, the derivation exhibits appealing primal/dual semantics. Empirically, it produces an "EMBP"-based heuristic that outperforms existing techniques for guiding variable and value ordering during backtracking search.

Abstract
We consider the problem of localization in an outdoor environment using only images from a single consumer-grade camera. Our aim is to learn a representation of an environment after a small number of excursions through it, to enable localization from images on a new excursion. This task is challenging due to: the high dimensionality of the inputs; variability in images taken at the same location; and the noisy ground truth data. We propose a discriminative probabilistic framework in which a set of stable and distinctive visual features are incrementally learned to form a prediction of camera pose from the raw images. After learning these features, we show how they can be used as an observation model in a Bayesian filtering scheme for online localization. We apply our framework to a real-world dataset and compare its performance to other image-based localization methods.