pwc-archive/papers-with-abstracts huggingface dataset:
A Sparse Non-Parametric Approach for Single Channel Separation of Known Sounds
Authors: Paris Smaragdis, Madhusudana Shashanka, Bhiksha Raj
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

In this paper we present an algorithm for separating mixed sounds from  a monophonic recording. Our approach makes use of training data which  allows us to learn representations of the types of sounds that compose the  mixture. In contrast to popular methods that attempt to extract com-  pact generalizable models for each sound from training data, we employ  the training data itself as a representation of the sources in the mixture.  We show that mixtures of known sounds can be described as sparse com-  binations of the training data itself, and in doing so produce signiﬁcantly  better separation results as compared to similar systems based on compact  statistical models.
A Bayesian Analysis of Dynamics in Free Recall
Authors: Richard Socher, Samuel Gershman, Per Sederberg, Kenneth Norman, Adler J. Perotte, David M. Blei
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Bayesian Inference, Retrieval, Topic Models

We develop a probabilistic model of human memory performance in free recall experiments. In these experiments, a subject first studies a list of words and then tries to recall them.  To model these data, we draw on both previous psychological research and statistical topic models of text documents.  We assume that memories are formed by assimilating the semantic meaning of studied words (represented as a distribution over topics) into a slowly changing latent context (represented in the same space).  During recall, this context is reinstated and used as a cue for retrieving studied words.  By conceptualizing memory retrieval as a dynamic latent variable model, we are able to use Bayesian inference to represent uncertainty and reason about the cognitive processes underlying memory.  We present a particle filter algorithm for performing approximate posterior inference, and evaluate our model on the prediction of recalled words in experimental data. By specifying the model hierarchically, we are also able to capture inter-subject variability.
Kernels and learning curves for Gaussian process regression on random graphs
Authors: Peter Sollich, Matthew Urry, Camille Coti
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: regression

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.
Time-Varying Dynamic Bayesian Networks
Authors: Le Song, Mladen Kolar, Eric P. Xing
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Computational Efficiency, Time Series, Time Series Analysis

Directed graphical models such as Bayesian networks are a favored formalism to model the dependency structures in complex multivariate systems such as those encountered in biology and neural sciences. When the system is undergoing dynamic transformation, often a temporally rewiring network is needed for capturing the dynamic causal influences between covariates. In this paper, we propose a time-varying dynamic Bayesian network (TV-DBN) for modeling the structurally varying directed dependency structures underlying non-stationary biological/neural time series. This is a challenging problem due the non-stationarity and sample scarcity of the time series. We present a kernel reweighted $\ell_1$ regularized auto-regressive procedure for learning the TV-DBN model. Our method enjoys nice properties such as computational efficiency and provable asymptotic consistency. Applying TV-DBN to time series measurements during yeast cell cycle and brain response to visual stimuli reveals interesting dynamics underlying the respective biological systems.
Code-specific policy gradient rules for spiking neurons
Authors: Henning Sprekeler, Guillaume Hennequin, Wulfram Gerstner
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Reinforcement Learning

Although it is widely believed that reinforcement learning is a suitable tool for describing behavioral learning, the mechanisms by which it can be implemented in networks of spiking neurons are not fully understood. Here, we show that different learning rules emerge from a policy gradient approach depending on which features of the spike trains are assumed to influence the reward signals, i.e., depending on which neural code is in effect. We use the framework of Williams (1992) to derive learning rules for arbitrary neural codes. For illustration, we present policy-gradient rules for  three different example codes - a spike count code, a spike timing code and the most general ``full spike train code - and test them on simple model problems. In addition to classical synaptic learning, we derive learning rules for intrinsic parameters that control the excitability of the neuron. The spike count learning rule has structural similarities with established Bienenstock-Cooper-Munro rules. If the distribution of the relevant spike train features  belongs to the natural exponential family, the learning rules have a characteristic shape that raises interesting prediction problems.
On the Convergence of the Concave-Convex Procedure
Authors: Gert R. Lanckriet, Bharath K. Sriperumbudur
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

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.
Fast Learning from Non-i.i.d. Observations
Authors: Ingo Steinwart, Andreas Christmann
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We prove an oracle inequality for generic regularized empirical risk minimization algorithms learning from  $\a$-mixing processes. To illustrate this oracle inequality, we use it to derive learning rates for some learning methods including least squares SVMs. Since the proof of the oracle inequality uses recent localization ideas developed for independent and identically distributed (i.i.d.) processes, it turns out that these learning rates are close to the optimal rates known in the i.i.d. case.
Structural inference affects depth perception in the context of potential occlusion
Authors: Ian Stevenson, Konrad Koerding
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Depth Estimation, Stereo Matching, Stereo Matching Hand

In many domains, humans appear to combine perceptual cues in a near-optimal, probabilistic fashion: two noisy pieces of information tend to be combined linearly with weights proportional to the precision of each cue. Here we present a case where structural information plays an important role. The presence of a background cue gives rise to the possibility of occlusion, and places a soft constraint on the location of a target – in effect propelling it forward. We present an ideal observer model of depth estimation for this situation where structural or ordinal information is important and then fit the model to human data from a stereo-matching task. To test whether subjects are truly using ordinal cues in a probabilistic manner we then vary the uncertainty of the task. We find that the model accurately predicts shifts in subject’s behavior. Our results indicate that the nervous system estimates depth ordering in a probabilistic fashion and estimates the structure of the visual scene during depth perception.
The Wisdom of Crowds in the Recollection of Order Information
Authors: Mark Steyvers, Brent Miller, Pernille Hemmer, Michael D. Lee
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: General Knowledge

When individuals independently recollect events or retrieve facts from memory, how can we aggregate these retrieved memories to reconstruct the actual set of events or facts? In this research, we report the performance of individuals in a series of general knowledge tasks, where the goal is to reconstruct from memory the order of historic events, or the order of items along some physical dimension. We introduce two Bayesian models for aggregating order information based on a Thurstonian approach and Mallows model. Both models assume that each individuals reconstruction is based on either a random permutation of the unobserved ground truth, or by a pure guessing strategy. We apply MCMC to make inferences about the underlying truth and the strategies employed by individuals. The models demonstrate a wisdom of crowds" effect, where the aggregated orderings are closer to the true ordering than the orderings of the best individual."
Online Learning of Assignments
Authors: Matthew Streeter, Daniel Golovin, Andreas Krause
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Which ads should we display in sponsored search in order to maximize our revenue?  How should we dynamically rank information sources to maximize value of information?  These applications exhibit strong diminishing returns: Selection of redundant ads and information sources decreases their marginal utility.  We show that these and other problems can be formalized as repeatedly selecting an assignment of items to positions to maximize a sequence of monotone submodular functions that arrive one by one.  We present an efficient algorithm for this general problem and analyze it in the no-regret model.  Our algorithm is equipped with strong theoretical guarantees, with a performance ratio that converges to the optimal constant of 1-1/e.  We empirically evaluate our algorithms on two real-world online optimization problems on the web: ad allocation with submodular utilities, and dynamically ranking blogs to detect information cascades.
Entropic Graph Regularization in Non-Parametric Semi-Supervised Classification
Authors: Amarnag Subramanya, Jeff A. Bilmes
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Classification, General Classification, Transductive Learning

We prove certain theoretical properties of a graph-regularized transductive learning objective that is based on minimizing a Kullback-Leibler divergence based loss. These include showing that the iterative alternating minimization procedure used to minimize the objective converges to the correct solution and deriving a test for convergence. We also propose a graph node ordering algorithm that is cache cognizant and leads to a linear speedup in parallel computations. This ensures that the algorithm scales to large data sets. By making use of empirical evaluation on the TIMIT and Switchboard I corpora, we show this approach is able to out-perform other state-of-the-art SSL approaches. In one instance, we solve a problem on a 120 million node graph.
Efficient Recovery of Jointly Sparse Vectors
Authors: Liang Sun, Jun Liu, Jianhui Chen, Jieping Ye
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Compressive Sensing

We consider the reconstruction of sparse signals in the multiple measurement vector (MMV) model,in which the signal, represented as a matrix, consists of a set of jointly sparse vectors. MMV is an extension of the single measurement vector (SMV) model employed in standard compressive sensing (CS). Recent theoretical studies focus on the convex relaxation of the MMV problem based on the $(2,1)$-norm minimization, which is an extension of the well-known $1$-norm minimization employed in SMV. However, the resulting convex optimization problem in MMV is significantly much more difficult to solve than the one in SMV. Existing algorithms reformulate it as a second-order cone programming (SOCP) or semidefinite programming (SDP), which is computationally expensive to solve for problems of moderate size. In this paper, we propose a new (dual) reformulation of the convex optimization problem in MMV and develop an efficient algorithm based on the prox-method. Interestingly, our theoretical analysis reveals the close connection between the proposed reformulation and multiple kernel learning. Our simulation studies demonstrate the scalability of the proposed algorithm.
Modelling Relational Data using Bayesian Clustered Tensor Factorization
Authors: Ilya Sutskever, Joshua B. Tenenbaum, Ruslan R. Salakhutdinov
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Clustering

We consider the problem of learning probabilistic models for complex relational structures between various types of objects.  A model can help us ``understand a dataset of relational facts in at least two ways, by finding interpretable structure in the data, and by supporting predictions, or inferences about whether particular unobserved relations are likely to be true.  Often there is a tradeoff between these two aims: cluster-based models yield more easily interpretable representations, while factorization-based approaches have better predictive performance on large data sets.  We introduce the Bayesian Clustered Tensor Factorization (BCTF) model, which embeds a factorized representation of relations in a nonparametric Bayesian clustering framework.  Inference is fully Bayesian but scales well to large data sets.  The model simultaneously discovers interpretable clusters and yields predictive performance that matches or beats previous probabilistic models for relational data.
Adapting to the Shifting Intent of Search Queries
Authors: Umar Syed, Aleksandrs Slivkins, Nina Mishra
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Cultural Vocal Bursts Intensity Prediction

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.
Indian Buffet Processes with Power-law Behavior
Authors: Yee W. Teh, Dilan Gorur
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

The Indian buffet process (IBP) is an exchangeable distribution over binary matrices used in Bayesian nonparametric featural models.  In this paper we propose a three-parameter generalization of the IBP exhibiting power-law behavior.  We achieve this by generalizing the beta process (the de Finetti measure of the IBP) to the \emph{stable-beta process} and deriving the IBP corresponding to it.  We find interesting relationships between the stable-beta process and the Pitman-Yor process (another stochastic process used in Bayesian nonparametric models with interesting power-law properties).  We show that our power-law IBP is a good model for word occurrences in documents with improved performance over the normal IBP.
Nonlinear directed acyclic structure learning with weakly additive noise models
Authors: Arthur Gretton, Peter Spirtes, Robert E. Tillman
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

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.
Compositionality of optimal control laws
Authors: Emanuel Todorov
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We present a theory of compositionality in stochastic optimal control, showing how task-optimal controllers can be constructed from certain primitives. The primitives are themselves feedback controllers pursuing their own agendas. They are mixed in proportion to how much progress they are making towards their agendas and how compatible their agendas are with the present task. The resulting composite control law is provably optimal when the problem belongs to a certain class. This class is rather general and yet has a number of unique properties - one of which is that the Bellman equation can be made linear even for non-linear or discrete dynamics. This gives rise to the compositionality developed here. In the special case of linear dynamics and Gaussian noise our framework yields analytical solutions (i.e. non-linear mixtures of linear-quadratic regulators) without requiring the final cost to be quadratic. More generally, a natural set of control primitives can be constructed by applying SVD to Greens function of the Bellman equation. We illustrate the theory in the context of human arm movements. The ideas of optimality and compositionality are both very prominent in the field of motor control, yet they are hard to reconcile. Our work makes this possible.
Maximin affinity learning of image segmentation
Authors: Kevin Briggman, Winfried Denk, Sebastian Seung, Moritz N. Helmstaedter, Srinivas C. Turaga
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: BIG-bench Machine Learning, graph partitioning, Image Segmentation, Segmentation, Semantic Segmentation

Images can be segmented by first using a classifier to predict an affinity graph that reflects the degree to which image pixels must be grouped together and then partitioning the graph to yield a segmentation. Machine learning has been applied to the affinity classifier to produce affinity graphs that are good in the sense of minimizing edge misclassification rates. However, this error measure is only indirectly related to the quality of segmentations produced by ultimately partitioning the affinity graph. We present the first machine learning algorithm for training a classifier to produce affinity graphs that are good in the sense of producing segmentations that directly minimize the Rand index, a well known segmentation performance measure. The Rand index measures segmentation performance by quantifying the classification of the connectivity of image pixel pairs after segmentation. By using the simple graph partitioning algorithm of finding the connected components of the thresholded affinity graph, we are able to train an affinity classifier to directly minimize the Rand index of segmentations resulting from the graph partitioning. Our learning algorithm corresponds to the learning of maximin affinities between image pixel pairs, which are predictive of the pixel-pair connectivity.
Help or Hinder: Bayesian Models of Social Goal Inference
Authors: Tomer Ullman, Chris Baker, Owen Macindoe, Owain Evans, Noah Goodman, Joshua B. Tenenbaum
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Everyday social interactions are heavily influenced by our snap judgments about others goals.  Even young infants can infer the goals of intentional agents from observing how they interact with objects and other agents in their environment: e.g., that one agent is `helping or `hindering anothers attempt to get up a hill or open a box. We propose a model for how people can infer these social goals from actions, based on inverse planning in multiagent Markov decision problems (MDPs).  The model infers the goal most likely to be driving an agents behavior by assuming the agent acts approximately rationally given environmental constraints and its model of other agents present.  We also present behavioral evidence in support of this model over a simpler, perceptual cue-based alternative.
Learning to Rank by Optimizing NDCG Measure
Authors: Hamed Valizadegan, Rong Jin, Ruofei Zhang, Jianchang Mao
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Information Retrieval, Learning-To-Rank, Retrieval

Learning to rank is a relatively new field of study, aiming to learn a ranking function from a set of training data with relevancy labels. The ranking algorithms are often evaluated using Information Retrieval measures, such as Normalized Discounted Cumulative Gain [1] and Mean Average Precision [2]. Until recently, most learning to rank algorithms were not using a loss function related to the above mentioned evaluation measures. The main difficulty in direct optimization of these measures is that they depend on the ranks of documents, not the numerical values output by the ranking function. We propose a probabilistic framework that addresses this challenge by optimizing the expectation of NDCG over all the possible permutations of documents. A relaxation strategy is used to approximate the average of NDCG over the space of permutation, and a bound optimization approach is proposed to make the computation efficient. Extensive experiments show that the proposed algorithm outperforms state-of-the-art ranking algorithms on several benchmark data sets.