mtybilly/Instruct2DS huggingface dataset:
Adapting to the Shifting Intent of Search Queries
Authors: Umar Syed, Aleksandrs Slivkins, Nina Mishra
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Search engines today present results that are often oblivious to recent shifts in intent. For example, the meaning of the query independence day shifts in early July to a US holiday and to a movie around the time of the box office release.  While no studies exactly quantify the magnitude of intent-shifting traffic, studies suggest that news events, seasonal topics, pop culture, etc account for 1/2 the search queries.  This paper shows that the signals a search engine receives can be used to both determine that a shift in intent happened, as well as find a result that is now more relevant. We present a meta-algorithm that marries a classifier with a bandit algorithm to achieve regret that depends logarithmically on the number of query impressions, under certain assumptions.  We provide strong evidence that this regret is close to the best achievable. Finally, via a series of experiments, we demonstrate that our algorithm outperforms prior approaches, particularly as the amount of intent-shifting traffic increases.
Predicting the Optimal Spacing of Study: A Multiscale Context Model of Memory
Authors: Harold Pashler, Nicholas Cepeda, Robert Lindsey, Ed Vul, Michael Mozer
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: When individuals learn facts (e.g., foreign language vocabulary) over multiple study sessions, the temporal spacing of study has a significant impact on memory retention.  Behavioral experiments have shown a nonmonotonic relationship between spacing and retention:  short or long intervals between study sessions yield lower cued-recall accuracy than intermediate intervals.  Appropriate spacing of study can double retention on educationally relevant time scales.  We introduce a Multiscale Context Model (MCM) that is able to predict the influence of a particular study schedule on retention for specific material.  MCMs prediction is based on empirical data characterizing forgetting of the material following a single study session.  MCM is a synthesis of two existing memory models (Staddon, Chelaru, & Higa, 2002; Raaijmakers, 2003).  On the surface, these  models are unrelated and incompatible, but we show they share a core feature  that allows them to be integrated.  MCM can determine study schedules that  maximize the durability of learning, and has implications for education  and training.  MCM can be cast either as a neural network with inputs that  fluctuate over time, or as a cascade of leaky integrators.  MCM is  intriguingly similar to a Bayesian multiscale model of memory (Kording, Tenenbaum, Shadmehr, 2007), yet MCM is better able to account for human  declarative memory.
A Game-Theoretic Approach to Hypergraph Clustering
Authors: Samuel R. Bulò, Marcello Pelillo
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Hypergraph clustering refers to the process of extracting maximally coherent groups from a set of objects using high-order (rather than pairwise) similarities. Traditional approaches to this problem are based on the idea of partitioning the input data into a user-defined number of classes, thereby obtaining the clusters as a by-product of the partitioning process. In this paper, we provide a radically different perspective to the problem. In contrast to the classical approach, we attempt to provide a meaningful formalization of the very notion of a cluster and we show that game theory offers an attractive and unexplored perspective that serves well our purpose. Specifically, we show that the hypergraph clustering problem can be naturally cast into a non-cooperative multi-player ``clustering game, whereby the notion of a cluster is equivalent to a classical game-theoretic equilibrium concept. From the computational viewpoint, we show that the problem of finding the equilibria of our clustering game is equivalent to locally optimizing a polynomial function over the standard simplex, and we provide a discrete-time dynamics to perform this optimization. Experiments are presented which show the superiority of our approach over state-of-the-art hypergraph clustering techniques.
Dirichlet-Bernoulli Alignment: A Generative Model for Multi-Class Multi-Label Multi-Instance Corpora
Authors: Shuang-hong Yang, Hongyuan Zha, Bao-gang Hu
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We propose Dirichlet-Bernoulli Alignment (DBA), a generative model for corpora in which each pattern (e.g., a document) contains a set of instances (e.g., paragraphs in the document) and belongs to multiple classes. By casting predefined classes as latent Dirichlet variables (i.e., instance level labels), and modeling the multi-label of each pattern as Bernoulli variables conditioned on the weighted empirical average of topic assignments, DBA automatically aligns the latent topics discovered from data to human-defined classes. DBA is useful for both pattern classification and instance disambiguation, which are tested on text classification and named entity disambiguation for web search queries respectively.
Adaptive Design Optimization in Experiments with People
Authors: Daniel Cavagnaro, Jay Myung, Mark A. Pitt
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: In cognitive science, empirical data collected from participants are the arbiters in model selection. Model discrimination thus depends on designing maximally informative experiments.  It has been shown that adaptive design optimization (ADO) allows one to discriminate models as efficiently as possible in simulation experiments.  In this paper we use ADO in a series of experiments with people to discriminate the Power, Exponential, and Hyperbolic models of memory retention, which has been a long-standing problem in cognitive science, providing an ideal setting in which to test the application of ADO for addressing questions about human cognition. Using an optimality criterion based on mutual information, ADO is able to find designs that are maximally likely to increase our certainty about the true model upon observation of the experiment outcomes.  Results demonstrate the usefulness of ADO and also reveal some challenges in its implementation.
Riffled Independence for Ranked Data
Authors: Jonathan Huang, Carlos Guestrin
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Representing distributions over permutations can be a daunting task due to the fact that the number of permutations of n objects scales factorially in n. One recent way that has been used to reduce storage complexity has been to exploit probabilistic independence, but as we argue, full independence assumptions impose strong sparsity constraints on distributions and are unsuitable for modeling rankings. We identify a novel class of independence structures, called riffled independence, which encompasses a more expressive family of distributions while retaining many of the properties necessary for performing efficient inference and reducing sample complexity. In riffled independence, one draws two permutations independently, then performs the riffle shuffle, common in card games, to combine the two permutations to form a single permutation. In ranking, riffled independence corresponds to ranking disjoint sets of objects independently, then interleaving those rankings. We provide a formal introduction and present algorithms for using riffled independence within Fourier-theoretic frameworks which have been explored by a number of recent papers.
A Neural Implementation of the Kalman Filter
Authors: Robert Wilson, Leif Finkel
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: There is a growing body of experimental evidence to suggest that the brain is capable of approximating optimal Bayesian inference in the face of noisy input stimuli.  Despite this progress, the neural underpinnings of this computation are still poorly  understood.  In this paper we focus on the problem of Bayesian filtering of stochastic time series.  In particular we introduce a novel neural network, derived from a line attractor architecture, whose dynamics map directly onto those of the Kalman Filter in the limit where the prediction error is small.  When the prediction error is large we show that the network responds robustly to change-points in a way that is qualitatively compatible with the optimal Bayesian model.  The model suggests ways in which probability distributions are encoded in the brain and makes a number of testable experimental predictions.
3D Object Recognition with Deep Belief Nets
Authors: Vinod Nair, Geoffrey E. Hinton
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We introduce a new type of Deep Belief Net and evaluate it on a 3D object recognition task. The top-level model is a third-order Boltzmann machine, trained using a hybrid algorithm that combines both generative and discriminative gradients. Performance is evaluated on the NORB database(normalized-uniform version), which contains stereo-pair images of objects under different lighting conditions and viewpoints. Our model achieves 6.5% error on the test set, which is close to the best published result for NORB (5.9%) using a convolutional neural net that has built-in knowledge of translation invariance. It substantially outperforms shallow models such as SVMs (11.6%). DBNs are especially suited for semi-supervised learning, and to demonstrate this we consider a modified version of the NORB recognition task in which additional unlabeled images are created by applying small translations to the images in the database. With the extra unlabeled data (and the same amount of labeled data as before), our model achieves 5.2% error, making it the current best result for NORB.
Improving Existing Fault Recovery Policies
Authors: Guy Shani, Christopher Meek
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Automated recovery from failures is a key component in the management of large data centers. Such systems typically employ a hand-made controller created by an expert. While such controllers capture many important aspects of the recovery process, they are often not systematically optimized to reduce costs such as server downtime. In this paper we explain how to use data gathered from the interactions of the hand-made controller with the system, to create an optimized controller. We suggest learning an indefinite horizon Partially Observable Markov Decision Process, a model for decision making under uncertainty, and solve it using a point-based algorithm. We describe the complete process, starting with data gathering, model learning, model checking procedures, and computing a policy. While our paper focuses on a specific domain, our method is applicable to other systems that use a hand-coded, imperfect controllers.
Convex Relaxation of Mixture Regression with Efficient Algorithms
Authors: Novi Quadrianto, John Lim, Dale Schuurmans, Tibério S. Caetano
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We develop a convex relaxation of maximum a posteriori estimation of a mixture of regression models. Although our relaxation involves a semidefinite matrix variable, we reformulate the problem to eliminate the need for general semidefinite programming. In particular, we provide two reformulations that admit fast algorithms. The first is a max-min spectral reformulation exploiting quasi-Newton descent. The second is a min-min reformulation consisting of fast alternating steps of closed-form updates. We evaluate the methods against Expectation-Maximization in a real problem of motion segmentation from video data.
Hierarchical Learning of Dimensional Biases in Human Categorization
Authors: Adam Sanborn, Nick Chater, Katherine A. Heller
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Existing models of categorization typically represent to-be-classified items as points in a multidimensional space. While from a mathematical point of view, an infinite number of basis sets can be used to represent points in this space, the choice of basis set is psychologically crucial. People generally choose the same basis dimensions, and have a strong preference to generalize along the axes of these dimensions, but not diagonally". What makes some choices of dimension special? We explore the idea that the dimensions used by people echo the natural variation in the environment. Specifically, we present a rational model that does not assume dimensions, but learns the same type of dimensional generalizations that people display. This bias is shaped by exposing the model to many categories with a structure hypothesized to be like those which children encounter. Our model can be viewed as a type of transformed Dirichlet process mixture model, where it is the learning of the base distribution of the Dirichlet process which allows dimensional generalization.The learning behaviour of our model captures the developmental shift from roughly "isotropic" for children to the axis-aligned generalization that adults show."
Polynomial Semantic Indexing
Authors: Bing Bai, Jason Weston, David Grangier, Ronan Collobert, Kunihiko Sadamasa, Yanjun Qi, Corinna Cortes, Mehryar Mohri
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We present a class of nonlinear (polynomial) models that are discriminatively trained to directly map from the word content in a query-document or document-document pair to a ranking score. Dealing with polynomial models on word features is computationally challenging. We propose a low rank (but diagonal preserving) representation of our polynomial models to induce feasible memory and computation requirements. We provide an empirical study on retrieval tasks based on Wikipedia documents, where we obtain state-of-the-art performance while providing realistically scalable methods.
Neural Implementation of Hierarchical Bayesian Inference by Importance Sampling
Authors: Lei Shi, Thomas L. Griffiths
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The goal of perception is to infer the hidden states in the hierarchical process by which sensory data are generated. Human behavior is consistent with the optimal statistical solution to this problem in many tasks, including cue combination and orientation detection. Understanding the neural mechanisms underlying this behavior is of particular importance, since probabilistic computations are notoriously challenging. Here we propose a simple mechanism for Bayesian inference which involves averaging over a few feature detection neurons which fire at a rate determined by their similarity to a sensory stimulus. This mechanism is based on a Monte Carlo method known as importance sampling, commonly used in computer science and statistics. Moreover, a simple extension to recursive importance sampling can be used to perform hierarchical Bayesian inference. We identify a scheme for implementing importance sampling with spiking neurons, and show that this scheme can account for human behavior in cue combination and oblique effect.
Discriminative Network Models of Schizophrenia
Authors: Irina Rish, Benjamin Thyreau, Bertrand Thirion, Marion Plaze, Marie-laure Paillere-martinot, Catherine Martelli, Jean-luc Martinot, Jean-baptiste Poline, Guillermo A. Cecchi
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Schizophrenia is a complex psychiatric disorder that has eluded a characterization in terms of local abnormalities of brain activity, and is hypothesized to affect the collective, ``emergent working of the brain. We propose a novel data-driven approach to capture emergent features using functional brain networks [Eguiluzet al] extracted from fMRI data, and demonstrate its advantage over traditional region-of-interest (ROI) and local, task-specific linear activation analyzes. Our results suggest that schizophrenia is indeed associated with disruption of global, emergent brain properties related to its functioning as a network, which cannot be explained by alteration of local activation patterns. Moreover, further exploitation of interactions by sparse Markov Random Field classifiers shows clear gain over linear methods, such as Gaussian Naive Bayes and SVM, allowing to reach 86% accuracy (over 50% baseline - random guess), which is quite remarkable given that it is based on a single fMRI experiment using a simple auditory task.
Sparsistent Learning of Varying-coefficient Models with Structural Changes
Authors: Mladen Kolar, Le Song, Eric P. Xing
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: To estimate the changing structure of a varying-coefficient   varying-structure (VCVS) model remains an important and open problem   in dynamic system modelling, which includes learning trajectories of   stock prices, or uncovering the topology of an evolving gene   network. In this paper, we investigate sparsistent learning of a   sub-family of this model --- piecewise constant VCVS models. We   analyze two main issues in this problem: inferring time points where   structural changes occur and estimating model structure (i.e., model   selection) on each of the constant segments. We propose a two-stage   adaptive procedure, which first identifies jump points of structural   changes and then identifies relevant covariates to a response on   each of the segments. We provide an asymptotic analysis of the   procedure, showing that with the increasing sample size, number of   structural changes, and number of variables, the true model can be   consistently selected. We demonstrate the performance of the method   on synthetic data and apply it to the brain computer interface   dataset. We also consider how this applies to structure estimation   of time-varying probabilistic graphical models.
Analysis of SVM with Indefinite Kernels
Authors: Yiming Ying, Colin Campbell, Mark Girolami
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The recent introduction of indefinite SVM by Luss and dAspremont [15] has effectively demonstrated SVM classification with a non-positive semi-definite  kernel (indefinite kernel).  This paper studies the properties of the objective function introduced there. In particular, we show that the objective function  is continuously differentiable and its gradient can be explicitly computed. Indeed, we further show that its gradient is Lipschitz continuous.  The main idea behind our analysis is that the objective function is smoothed by the penalty term, in its saddle (min-max) representation, measuring the distance between the indefinite kernel matrix and the proxy positive semi-definite one. Our elementary result greatly facilitates the application of gradient-based algorithms. Based on our analysis,  we further develop  Nesterovs smooth optimization approach [16,17] for indefinite SVM which has an optimal convergence rate for smooth problems. Experiments on various benchmark datasets validate our analysis and demonstrate the efficiency of our proposed algorithms.
Exploring Functional Connectivities of the Human Brain using Multivariate Information Analysis
Authors: Barry Chai, Dirk Walther, Diane Beck, Li Fei-fei
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: In this study, we present a method for estimating the mutual information for a localized pattern of fMRI data. We show that taking a multivariate information approach to voxel selection leads to a decoding accuracy that surpasses an univariate inforamtion approach and other standard voxel selection methods. Furthermore,we extend the multivariate mutual information theory to measure the functional connectivity between distributed brain regions. By jointly estimating the information shared by two sets of voxels we can reliably map out the connectivities in the human brain during experiment conditions. We validated our approach on a 6-way scene categorization fMRI experiment. The multivariate information analysis is able to ﬁnd strong information ﬂow between PPA and RSC, which conﬁrms existing neuroscience studies on scenes. Furthermore, by exploring over the whole brain, our method identifies other interesting ROIs that share information with the PPA, RSC scene network,suggesting interesting future work for neuroscientists.
Semi-supervised Learning using Sparse Eigenfunction Bases
Authors: Kaushik Sinha, Mikhail Belkin
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We present a new framework for semi-supervised learning with sparse eigenfunction bases of kernel matrices.  It turns out that  when the \emph{cluster assumption} holds, that is, when the high density regions are sufficiently separated by  low density valleys, each high density area corresponds to a unique representative eigenvector. Linear combination of such eigenvectors (or, more precisely, of their Nystrom extensions) provide good candidates for good classification functions. By first choosing an appropriate basis of these eigenvectors from unlabeled data and then using labeled data  with Lasso to select a classifier in the span of these eigenvectors, we obtain a classifier, which has a very sparse representation in this basis. Importantly, the sparsity appears naturally from the  cluster assumption. Experimental results on a number  of real-world data-sets show that our method is competitive with the state of the art semi-supervised learning algorithms and outperforms the natural base-line algorithm (Lasso in the Kernel PCA basis).
A Gaussian Tree Approximation for Integer Least-Squares
Authors: Jacob Goldberger, Amir Leshem
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: This paper proposes a new algorithm for the linear least squares problem where the unknown variables are constrained to be in a finite set.  The factor graph that corresponds to this problem is very loopy; in fact, it is a complete graph. Hence, applying the Belief Propagation (BP) algorithm yields very poor results. The algorithm described here is based on  an optimal  tree approximation of the Gaussian density of the unconstrained linear system. It is shown that even though the approximation is not directly applied to the exact discrete distribution, applying the BP algorithm to the modified factor graph outperforms current methods in terms of both performance and complexity. The improved performance of the proposed algorithm is demonstrated  on the problem of MIMO detection.
Nonlinear directed acyclic structure learning with weakly additive noise models
Authors: Arthur Gretton, Peter Spirtes, Robert E. Tillman
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The recently proposed \emph{additive noise model} has advantages over previous structure learning algorithms, when attempting to recover some true data generating mechanism, since it (i) does not assume linearity or Gaussianity and (ii) can recover a unique DAG rather than an equivalence class. However, its original extension to the multivariate case required enumerating all possible DAGs, and for some special distributions, e.g. linear Gaussian, the model is invertible and thus cannot be used for structure learning. We present a new approach which combines a PC style search using recent advances in kernel measures of conditional dependence with local searches for additive noise models in substructures of the equivalence class. This results in a more computationally efficient approach that is useful for arbitrary distributions even when additive noise models are invertible. Experiments with synthetic and real data show that this method is more accurate than previous methods when data are nonlinear and/or non-Gaussian.
FACTORIE: Probabilistic Programming via Imperatively Defined Factor Graphs
Authors: Andrew McCallum, Karl Schultz, Sameer Singh
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Discriminatively trained undirected graphical models have had wide empirical success, and there has been increasing interest in toolkits that ease their application to complex relational data.  The power in relational models is in their repeated structure and tied parameters; at issue is how to define these structures in a powerful and flexible way. Rather than using a declarative language, such as SQL or first-order logic, we advocate using an imperative language to express various aspects of model structure, inference, and learning.  By combining the traditional, declarative, statistical semantics of factor graphs with imperative definitions of their construction and operation, we allow the user to mix declarative and procedural domain knowledge, and also gain significant efficiencies.  We have implemented such imperatively defined factor graphs in a system we call Factorie, a software library for an object-oriented, strongly-typed, functional language.  In experimental comparisons to Markov Logic Networks on joint segmentation and coreference, we find our approach to be 3-15 times faster while reducing error by 20-25%-achieving a new state of the art.
Exponential Family Graph Matching and Ranking
Authors: James Petterson, Jin Yu, Julian J. Mcauley, Tibério S. Caetano
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We present a method for learning max-weight matching predictors in bipartite graphs. The method consists of performing maximum a posteriori estimation in exponential families with sufficient statistics that encode permutations and data features. Although inference is in general hard, we show that for one very relevant application - document ranking - exact inference is efficient. For general model instances, an appropriate sampler is readily available. Contrary to existing max-margin matching models, our approach is statistically consistent and, in addition, experiments with increasing sample sizes indicate superior improvement over such models. We apply the method to graph matching in computer vision as well as to a standard benchmark dataset for learning document ranking, in which we obtain state-of-the-art results, in particular improving on max-margin variants. The drawback of this method with respect to max-margin alternatives is its runtime for large graphs, which is high comparatively.
Extending Phase Mechanism to Differential Motion Opponency for Motion Pop-out
Authors: Yicong Meng, Bertram E. Shi
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We extend the concept of phase tuning, a ubiquitous mechanism in sensory neurons including motion and disparity detection neurons, to the motion contrast detection.  We demonstrate that motion contrast can be detected by phase shifts between motion neuronal responses in different spatial regions. By constructing the differential motion opponency in response to motions in two different spatial regions, varying motion contrasts can be detected, where similar motion is detected by zero phase shifts and differences in motion by non-zero phase shifts.  The model can exhibit either enhancement or suppression of responses by either different or similar motion in the surrounding.  A primary advantage of the model is that the responses are selective to relative motion instead of absolute motion, which could model neurons found in neurophysiological experiments responsible for motion pop-out detection.
Periodic Step Size Adaptation for Single Pass On-line Learning
Authors: Chun-nan Hsu, Yu-ming Chang, Hanshen Huang, Yuh-jye Lee
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: It has been established that the second-order stochastic gradient descent (2SGD) method can potentially achieve generalization performance as well as empirical optimum in a single pass (i.e., epoch) through the training examples. However, 2SGD requires computing the inverse of the Hessian matrix of the loss function, which is prohibitively expensive. This paper presents Periodic Step-size Adaptation (PSA), which approximates the Jacobian matrix of the mapping function and explores a linear relation between the Jacobian and Hessian to approximate the Hessian periodically and achieve near-optimal results in experiments on a wide variety of models and tasks.
Adaptive Regularization for Transductive Support Vector Machine
Authors: Zenglin Xu, Rong Jin, Jianke Zhu, Irwin King, Michael Lyu, Zhirong Yang
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We discuss the framework of Transductive Support Vector Machine (TSVM) from the perspective of the regularization strength induced by the unlabeled data. In this framework, SVM and TSVM can be regarded as a learning machine without regularization and one with full regularization from the unlabeled data, respectively. Therefore, to supplement this framework of the regularization strength, it is necessary to introduce data-dependant partial regularization. To this end, we reformulate TSVM into a form with controllable regularization strength, which includes SVM and TSVM as special cases. Furthermore, we introduce a method of adaptive regularization that is data dependant and is based on the smoothness assumption. Experiments on a set of benchmark data sets indicate the promising results of the proposed work compared with state-of-the-art TSVM algorithms.
Subject independent EEG-based BCI decoding
Authors: Siamac Fazli, Cristian Grozea, Marton Danoczy, Benjamin Blankertz, Florin Popescu, Klaus-Robert Müller
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: In the quest to make Brain Computer Interfacing (BCI) more usable, dry electrodes have emerged that get rid of the initial 30 minutes required for placing an electrode cap.  Another time consuming step is the required individualized adaptation to the BCI user, which involves another 30 minutes calibration for assessing a subjects brain signature. In this paper we aim to also remove this calibration proceedure from BCI setup time by means of machine learning. In particular, we harvest a large database of EEG BCI motor imagination recordings (83 subjects) for constructing a library of subject-specific spatio-temporal filters and derive a subject independent BCI classifier. Our offline results indicate that BCI-na{i}ve users could start real-time BCI use with no prior calibration at only a very moderate performance loss."
On the Convergence of the Concave-Convex Procedure
Authors: Gert R. Lanckriet, Bharath K. Sriperumbudur
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The concave-convex procedure (CCCP) is a majorization-minimization algorithm that solves d.c. (difference of convex functions) programs as a sequence of convex programs. In machine learning, CCCP is extensively used in many learning algorithms like sparse support vector machines (SVMs), transductive SVMs, sparse principal component analysis, etc. Though widely used in many applications, the convergence behavior of CCCP has not gotten a lot of specific attention. Yuille and Rangarajan analyzed its convergence in their original paper, however, we believe the analysis is not complete. Although the convergence of CCCP can be derived from the convergence of the d.c. algorithm (DCA), their proof is more specialized and technical than actually required for the specific case of CCCP. In this paper, we follow a different reasoning and show how Zangwills global convergence theory of iterative algorithms provides a natural framework to prove the convergence of CCCP, allowing a more elegant and simple proof. This underlines Zangwills theory as a powerful and general framework to deal with the convergence issues of iterative algorithms, after also being used to prove the convergence of algorithms like expectation-maximization, generalized alternating minimization, etc. In this paper, we provide a rigorous analysis of the convergence of CCCP by addressing these questions: (i) When does CCCP find a local minimum or a stationary point of the d.c. program under consideration? (ii) When does the sequence generated by CCCP converge? We also present an open problem on the issue of local convergence of CCCP.
Orthogonal Matching Pursuit From Noisy Random Measurements: A New Analysis
Authors: Sundeep Rangan, Alyson K. Fletcher
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Orthogonal matching pursuit (OMP) is a widely used greedy algorithm for recovering sparse vectors from linear measurements.  A well-known analysis of Tropp and Gilbert shows that OMP can recover a k-sparse n-dimensional real vector from m = 4k log(n) noise-free random linear measurements with a probability that goes to one as n goes to infinity. This work shows strengthens this result by showing that a lower number of measurements, m = 2k log(n-k), is in fact sufficient for asymptotic recovery. Moreover, this number of measurements is also sufficient for detection of the sparsity pattern (support) of the vector with measurement errors provided the signal-to-noise ratio (SNR) scales to infinity. The scaling m = 2k log(n-k) exactly matches the number of measurements required by the more complex lasso for signal recovery.
Noise Characterization, Modeling, and Reduction for In Vivo Neural Recording
Authors: Zhi Yang, Qi Zhao, Edward Keefer, Wentai Liu
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Studying signal and noise properties of recorded neural data is critical in developing more efficient algorithms to recover the encoded information. Important issues exist in this research including the variant spectrum spans of neural spikes that make it difficult to choose a global optimal bandpass filter. Also, multiple sources produce aggregated noise that deviates from the conventional white Gaussian noise. In this work, the spectrum variability of spikes is addressed, based on which the concept of adaptive bandpass filter that fits the spectrum of individual spikes is proposed. Multiple noise sources have been studied through analytical models as well as empirical measurements. The dominant noise source is identified as neuron noise followed by interface noise of the electrode. This suggests that major efforts to reduce noise from electronics are not well spent. The measured noise from in vivo experiments shows a family of 1/f^{x} (x=1.5\pm 0.5) spectrum that can be reduced using noise shaping techniques. In summary, the methods of adaptive bandpass filtering and noise shaping together result in several dB signal-to-noise ratio (SNR) enhancement.
Adaptive Regularization of Weight Vectors
Authors: Koby Crammer, Alex Kulesza, Mark Dredze
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We present AROW, a new online learning algorithm that combines several properties of successful : large margin training, confidence weighting, and the capacity to handle non-separable data. AROW performs adaptive regularization of the prediction function upon seeing each new instance, allowing it to perform especially well in the presence of label noise.  We derive a mistake bound, similar in form to the second order perceptron bound, which does not assume separability. We also relate our algorithm to recent confidence-weighted online learning techniques and empirically show that AROW achieves state-of-the-art performance and notable robustness in the case of non-separable data.
Posterior vs Parameter Sparsity in Latent Variable Models
Authors: Kuzman Ganchev, Ben Taskar, Fernando Pereira, João Gama
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: In this paper we explore the problem of biasing unsupervised models to favor sparsity. We extend the posterior regularization framework [8] to encourage the  model to achieve posterior sparsity on the unlabeled training data. We apply this new method to learn ﬁrst-order HMMs for unsupervised part-of-speech (POS) tagging, and show that HMMs learned this way consistently and signiﬁcantly out-performs both EM-trained HMMs, and HMMs with a sparsity-inducing Dirichlet prior trained by variational EM. We evaluate these HMMs on three languages — English, Bulgarian and Portuguese — under four conditions. We ﬁnd that our  method always improves performance with respect to both baselines, while variational Bayes actually degrades performance in most cases. We increase accuracy with respect to EM by 2.5%-8.7% absolute and we see improvements even in a semisupervised condition where a limited dictionary is provided.
Reconstruction of Sparse Circuits Using Multi-neuronal Excitation (RESCUME)
Authors: Tao Hu, Anthony Leonardo, Dmitri B. Chklovskii
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: One of the central problems in neuroscience is reconstructing synaptic connectivity in neural circuits. Synapses onto a neuron can be probed by sequentially stimulating potentially pre-synaptic neurons while monitoring the membrane voltage of the post-synaptic neuron. Reconstructing a large neural circuit using such a “brute force” approach is rather time-consuming and inefficient because the connectivity in neural circuits is sparse. Instead, we propose to measure a post-synaptic neuron’s voltage while stimulating simultaneously multiple randomly chosen potentially pre-synaptic neurons. To extract the weights of individual synaptic connections we apply a decoding algorithm recently developed for compressive sensing. Compared to the brute force approach, our method promises significant time savings that grow with the size of the circuit. We use computer simulations to find optimal stimulation parameters and explore the feasibility of our reconstruction method under realistic experimental conditions including noise and non-linear synaptic integration. Multiple-neuron stimulation allows reconstructing synaptic connectivity just from the spiking activity of post-synaptic neurons, even when sub-threshold voltage is unavailable. By using calcium indicators, voltage-sensitive dyes, or multi-electrode arrays one could monitor activity of multiple post-synaptic neurons simultaneously, thus mapping their synaptic inputs in parallel, potentially reconstructing a complete neural circuit.
Label Selection on Graphs
Authors: Andrew Guillory, Jeff A. Bilmes
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We investigate methods for selecting sets of labeled vertices for use in predicting the labels of vertices on a graph.  We specifically study methods which choose a single batch of labeled vertices (i.e. offline, non sequential methods).  In this setting, we find common graph smoothness assumptions directly motivate simple label selection methods with interesting theoretical guarantees. These methods bound prediction error in terms of the smoothness of the true labels with respect to the graph.  Some of these bounds give new motivations for previously proposed algorithms, and some suggest new algorithms which we evaluate.  We show improved performance over baseline methods on several real world data sets.
A Fast, Consistent Kernel Two-Sample Test
Authors: Arthur Gretton, Kenji Fukumizu, Zaïd Harchaoui, Bharath K. Sriperumbudur
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: A kernel embedding of probability distributions into reproducing kernel Hilbert spaces (RKHS) has recently been proposed, which  allows the comparison of two probability measures P and Q based on the distance between their respective embeddings: for a sufficiently rich RKHS, this distance is zero if and only if P and Q coincide. In using this distance as a statistic for a  test of whether two samples are from different distributions, a major difficulty arises in computing the significance threshold, since the empirical statistic has as its null distribution (where P=Q)  an infinite weighted sum of $\chi^2$ random variables. The main result of the present work is a  novel, consistent estimate of this null distribution, computed from  the eigenspectrum of the Gram matrix on the aggregate sample from P and Q. This estimate may be computed faster than a previous consistent estimate based on the bootstrap.  Another prior approach was to compute the null distribution based on fitting a parametric family with the low order moments of the test statistic: unlike the present work, this heuristic has no guarantee of being accurate or consistent. We verify the performance of our null distribution estimate on both   an artificial example and on high dimensional multivariate data.
Kernels and learning curves for Gaussian process regression on random graphs
Authors: Peter Sollich, Matthew Urry, Camille Coti
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We investigate how well Gaussian process regression can learn functions defined on graphs, using large regular random graphs as a paradigmatic example. Random-walk based kernels are shown to have some surprising properties: within the standard approximation of a locally tree-like graph structure, the kernel does not become constant, i.e.neighbouring function values do not become fully correlated, when the lengthscale $\sigma$ of the kernel is made large. Instead the kernel attains a non-trivial limiting form, which we calculate. The fully correlated limit is reached only once loops become relevant, and we estimate where the crossover to this regime occurs. Our main subject are learning curves of Bayes error versus training set size. We show that these are qualitatively well predicted by a simple approximation using only the spectrum of a large tree as input, and generically scale with $n/V$, the number of training examples per vertex. We also explore how this behaviour changes once kernel lengthscales are large enough for loops to become important.
Beyond Categories: The Visual Memex Model for Reasoning About Object Relationships
Authors: Tomasz Malisiewicz, Alyosha Efros
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The use of context is critical for scene understanding in computer vision, where the recognition of an object is driven by both local appearance and the objects relationship to other elements of the scene (context).  Most current approaches rely on modeling the relationships between object categories as a source of context. In this paper we seek to move beyond categories to provide a richer appearance-based model of context.  We present an exemplar-based model of objects and their relationships, the Visual Memex, that encodes both local appearance and 2D spatial context between object instances. We evaluate our model on Torralbas proposed Context Challenge against a baseline category-based system. Our experiments suggest that moving beyond categories for context modeling appears to be quite beneficial, and may be the critical missing ingredient in scene understanding systems.
Conditional Random Fields with High-Order Features for Sequence Labeling
Authors: Nan Ye, Wee S. Lee, Hai L. Chieu, Dan Wu
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Dependencies among neighbouring labels in a sequence is an important source of information for sequence labeling problems. However, only dependencies between adjacent labels are commonly exploited in practice because of the high computational complexity of typical inference algorithms when longer distance dependencies are taken into account. In this paper, we show that it is possible to design efficient inference algorithms for a conditional random field using features that depend on long consecutive label sequences (high-order features), as long as the number of distinct label sequences in the features used is small. This leads to efficient learning algorithms for these conditional random fields. We show experimentally that exploiting dependencies using high-order features can lead to substantial performance improvements for some problems and discuss conditions under which high-order features can be effective.
Abstraction and Relational learning
Authors: Charles Kemp, Alan Jern
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Many categories are better described by providing relational information than listing characteristic features.  We present a hierarchical generative model that helps to explain how relational categories are learned and used. Our model learns abstract schemata that specify the relational similarities shared by members of a category, and our emphasis on abstraction departs from previous theoretical proposals that focus instead on comparison of concrete instances. Our first experiment suggests that our abstraction-based account can address some of the tasks that have previously been used to support comparison-based approaches. Our second experiment focuses on one-shot schema learning, a problem that raises challenges for comparison-based approaches but is handled naturally by our abstraction-based account.
Fast Graph Laplacian Regularized Kernel Learning via Semidefinite–Quadratic–Linear Programming
Authors: Xiao-ming Wu, Anthony M. So, Zhenguo Li, Shuo-yen R. Li
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Kernel learning is a powerful framework for nonlinear data modeling. Using the kernel trick, a number of problems have been formulated as semidefinite programs (SDPs). These include Maximum Variance Unfolding (MVU) (Weinberger et al., 2004) in nonlinear dimensionality reduction, and Pairwise Constraint Propagation (PCP) (Li et al., 2008) in constrained clustering. Although in theory SDPs can be efficiently solved, the high computational complexity incurred in numerically processing the huge linear matrix inequality constraints has rendered the SDP approach unscalable. In this paper, we show that a large class of kernel learning problems can be reformulated as semidefinite-quadratic-linear programs (SQLPs), which only contain a simple positive semidefinite constraint, a second-order cone constraint and a number of linear constraints. These constraints are much easier to process numerically, and the gain in speedup over previous approaches is at least of the order $m^{2.5}$, where m is the matrix dimension. Experimental results are also presented to show the superb computational efficiency of our approach.