pwc-archive/papers-with-abstracts huggingface dataset:
Reinforcement Learning using Kernel-Based Stochastic Factorization
Authors: Andre S. Barreto, Doina Precup, Joelle Pineau
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Kernel-based reinforcement-learning (KBRL) is a method for learning a decision policy from a set of sample transitions which stands out for its strong theoretical guarantees. However, the size of the approximator grows with the number of transitions, which makes the approach impractical for large problems.  In this paper we introduce a novel algorithm to improve the scalability of KBRL. We resort to a special decomposition of a transition matrix, called stochastic factorization, to fix the size of the approximator while at the same time incorporating all the information contained in the data. The resulting algorithm, kernel-based stochastic factorization (KBSF), is much faster but still converges to a unique solution. We derive a theoretical upper bound for the distance between the value functions computed by KBRL and KBSF. The effectiveness of our method is illustrated with computational experiments on four reinforcement-learning problems, including a difficult task in which the goal is to learn a neurostimulation policy to suppress the occurrence of seizures in epileptic rat brains. We empirically demonstrate that the proposed approach is able to compress the information contained in KBRL's model. Also, on the tasks studied, KBSF outperforms two of the most prominent reinforcement-learning algorithms, namely least-squares policy iteration and fitted Q-iteration.
k-NN Regression Adapts to Local Intrinsic Dimension
Authors: Samory Kpotufe
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: regression

Many nonparametric regressors were recently shown to converge at rates that depend only on the intrinsic dimension of data.  These regressors thus escape the curse of dimension when high-dimensional data has low intrinsic dimension (e.g. a manifold).   We show that $k$-NN regression is also adaptive to intrinsic dimension. In particular our rates are local to a query $x$   and depend only on the way masses of balls centered at $x$ vary with radius.    Furthermore, we show a simple way to choose $k = k(x)$ locally at any $x$ so as to nearly achieve the minimax rate at $x$  in terms of the unknown intrinsic dimension in the vicinity of $x$. We also establish that the minimax rate does not depend   on a particular choice of metric space or distribution, but rather that this minimax rate holds for any metric space and doubling measure.
Learning unbelievable probabilities
Authors: Zachary Pitkow, Yashar Ahmadian, Ken D. Miller
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Loopy belief propagation performs approximate inference on graphical models with loops. One might hope to compensate for the approximation by adjusting model parameters. Learning algorithms for this purpose have been explored previously, and the claim has been made that every set of locally consistent marginals can arise from belief propagation run on a graphical model. On the contrary, here we show that many probability distributions have marginals that cannot be reached by belief propagation using any set of model parameters or any learning algorithm. We call such marginals `unbelievable.' This problem occurs whenever the Hessian of the Bethe free energy is not positive-definite at the target marginals. All learning algorithms for belief propagation necessarily fail in these cases, producing beliefs or sets of beliefs that may even be worse than the pre-learning approximation. We then show that averaging inaccurate beliefs, each obtained from belief propagation using model parameters perturbed about some learned mean values, can achieve the unbelievable marginals.
A Machine Learning Approach to Predict Chemical Reactions
Authors: Matthew A. Kayala, Pierre F. Baldi
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: BIG-bench Machine Learning

Being able to predict the course of arbitrary chemical reactions is essential to the theory and applications of organic chemistry. Previous approaches are not high-throughput, are not generalizable or scalable, or lack sufficient data to be effective. We describe single mechanistic reactions as concerted electron movements from an electron orbital source to an electron orbital sink. We use an existing rule-based expert system to derive a dataset consisting of 2,989 productive mechanistic steps and 6.14 million non-productive mechanistic steps. We then pose identifying productive mechanistic steps as a ranking problem: rank potential orbital interactions such that the top ranked interactions yield the major products. The machine learning implementation follows a two-stage approach, in which we first train atom level reactivity filters to prune 94.0% of non-productive reactions with less than a 0.1% false negative rate. Then, we train an ensemble of ranking models on pairs of interacting orbitals to learn a relative productivity function over single mechanistic reactions in a given system. Without the use of explicit transformation patterns, the ensemble perfectly ranks the productive mechanisms at the top 89.1% of the time, rising to 99.9% of the time when top ranked lists with at most four non-productive reactions are considered. The final system allows multi-step reaction prediction. Furthermore, it is generalizable, making reasonable predictions over reactants and conditions which the rule-based expert system does not handle.
Dynamical segmentation of single trials from population neural data
Authors: Biljana Petreska, Byron M. Yu, John P. Cunningham, Gopal Santhanam, Stephen I. Ryu, Krishna V. Shenoy, Maneesh Sahani
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Simultaneous recordings of many neurons embedded within a  recurrently-connected cortical network may provide concurrent views into the dynamical processes of that network, and thus its computational function.  In principle, these dynamics might be identified by purely unsupervised, statistical means.  Here, we show that a Hidden Switching Linear Dynamical Systems (HSLDS) model---in which multiple linear dynamical laws approximate a nonlinear and potentially non-stationary dynamical process---is able to distinguish different dynamical regimes within single-trial motor cortical activity associated with the preparation and initiation of hand movements.  The regimes are identified without reference to behavioural or experimental epochs, but nonetheless transitions between them correlate strongly with external events whose timing may vary from trial to trial.  The HSLDS model also performs better than recent comparable models in predicting the firing rate of an isolated neuron based on the firing rates of others, suggesting that it  captures more of the "shared variance" of the data.  Thus, the method is able to trace the dynamical processes underlying the coordinated evolution of network activity in a way that appears to reflect its computational role.
Recovering Intrinsic Images with a Global Sparsity Prior on Reflectance
Authors: Carsten Rother, Martin Kiefel, Lumin Zhang, Bernhard Schölkopf, Peter V. Gehler
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We address the challenging task of decoupling material properties from lighting properties given a single image. In the last two decades virtually all works have concentrated on exploiting edge information to address this problem. We take a different route by introducing a new prior on reflectance, that models reflectance values as being drawn from a sparse set of basis colors. This results in a Random Field model with global, latent variables (basis colors) and pixel-accurate output reflectance values. We show that without edge information high-quality results can be achieved, that are on par with methods exploiting this source of information. Finally, we present competitive results by integrating an additional edge model. We believe that our approach is a solid starting point for future development in this domain.
Probabilistic Modeling of Dependencies Among Visual Short-Term Memory Representations
Authors: Emin Orhan, Robert A. Jacobs
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Extensive evidence suggests that items are not encoded independently in visual short-term memory (VSTM). However, previous research has not quantitatively considered how the encoding of an item influences the encoding of other items. Here, we model the dependencies among VSTM representations using a multivariate Gaussian distribution with a stimulus-dependent mean and covariance matrix. We report the results of an experiment designed to determine the specific form of the stimulus-dependence of the mean and the covariance matrix. We find that the magnitude of the covariance between the representations of two items is a monotonically decreasing function of the difference between the items' feature values, similar to a Gaussian process with a distance-dependent, stationary kernel function. We further show that this type of covariance function can be explained as a natural consequence of encoding multiple stimuli in a population of neurons with correlated responses.
Reconstructing Patterns of Information Diffusion from Incomplete Observations
Authors: Flavio Chierichetti, David Liben-Nowell, Jon M. Kleinberg
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Motivated by the spread of on-line information in general and   on-line petitions in particular, recent research has raised the following   combinatorial estimation problem.  There is a tree T that we cannot observe directly (representing  the structure along which the information has spread), and certain  nodes randomly decide to make their copy of the information public.  In the case of a petition, the list of names on each public copy   of the petition also reveals a path leading back to the root of the tree.  What can we conclude about the properties of the tree we observe  from these revealed paths,  and can we use the structure of the observed tree  to estimate the size of the full unobserved tree T?    Here we provide the first algorithm for this size estimation task,  together with provable guarantees on its performance.  We also establish structural properties of the observed tree, providing the  first rigorous explanation for some of the unusual structural  phenomena present in the spread of real chain-letter petitions  on the Internet.
Active Learning Ranking from Pairwise Preferences with Almost Optimal Query Complexity
Authors: Nir Ailon
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Active Learning, Learning-To-Rank

Given a set $V$ of  $n$ elements we wish to linearly order them using pairwise preference labels  which may be non-transitive (due to irrationality or arbitrary noise).  The goal is to linearly order the elements while disagreeing with  as few pairwise preference labels as possible.  Our performance is measured by two parameters:  The number of disagreements (loss) and the query complexity (number of pairwise preference labels).  Our algorithm adaptively queries  at most $O(n\poly(\log n,\eps^{-1}))$ preference labels for a regret of  $\eps$ times the optimal loss.  This is strictly better, and often significantly better than what  non-adaptive sampling could achieve.  Our main result helps settle an open problem posed by   learning-to-rank (from pairwise information) theoreticians and practitioners:  What is a provably correct way to sample preference labels?
Modelling Genetic Variations using Fragmentation-Coagulation Processes
Authors: Yee W. Teh, Charles Blundell, Lloyd Elliott
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Imputation

We propose a novel class of Bayesian nonparametric models for sequential data called fragmentation-coagulation processes (FCPs).  FCPs model a set of sequences using  a partition-valued Markov process which evolves by splitting and merging clusters.  An FCP is exchangeable, projective, stationary and reversible, and its equilibrium distributions are given by the Chinese restaurant process.  As opposed to hidden Markov models, FCPs allow for flexible modelling of the number of clusters, and they avoid label switching non-identifiability problems. We develop an efficient Gibbs sampler for FCPs which uses uniformization and the forward-backward algorithm.  Our development of FCPs is motivated by applications in population genetics, and we demonstrate the utility of FCPs on problems of genotype imputation with phased and unphased SNP data.
Prediction strategies without loss
Authors: Michael Kapralov, Rina Panigrahy
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Prediction

Consider a sequence of bits where we are trying to predict the next bit from the previous bits. Assume we are allowed to say `predict 0' or `predict 1', and our payoff is $+1$ if the prediction is correct and $-1$ otherwise. We will say that at each point in time the loss of an algorithm is the number of wrong predictions minus the number of right predictions so far.  In this paper we are interested in algorithms that have essentially zero (expected) loss over any string at any point in time and yet have small regret with respect to always predicting $0$ or always predicting $1$. For a sequence of length $T$ our algorithm has  regret $14\epsilon T $ and loss   $2\sqrt{T}e^{-\epsilon^2 T} $ in expectation for all strings. We show that the tradeoff between loss and regret is optimal up to constant factors.    Our techniques extend to the general setting of $N$ experts, where the related problem of trading off regret to the best expert for regret to the 'special' expert has been studied by Even-Dar et al. (COLT'07). We obtain essentially zero loss with respect to the special expert and optimal loss/regret tradeoff,  improving upon the results of Even-Dar et al (COLT'07) and settling the main question left open in their paper.     The strong loss bounds of the algorithm have some surprising consequences. First, we obtain a parameter free algorithm for the experts problem that has optimal regret bounds with respect to $k$-shifting optima, i.e. bounds with respect to the optimum that is allowed to change arms multiple times. Moreover, for {\em any window of size $n$} the regret of our algorithm to any expert never exceeds $O(\sqrt{n(\log N+\log T)})$, where $N$ is the number of experts and $T$ is the time horizon, while maintaining the essentially zero loss property.
Data Skeletonization via Reeb Graphs
Authors: Xiaoyin Ge, Issam I. Safa, Mikhail Belkin, Yusu Wang
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Recovering hidden structure from complex and noisy non-linear data is one of the most fundamental problems in machine learning and statistical inference. While such data is often high-dimensional, it is of interest to approximate it with a low-dimensional or even one-dimensional space, since  many important aspects of  data are often intrinsically low-dimensional.   Furthermore, there are many scenarios where the underlying structure is graph-like, e.g, river/road networks or various trajectories.   In this paper, we develop a framework to extract, as well as to simplify, a one-dimensional "skeleton" from unorganized data using the Reeb graph.   Our algorithm is very simple, does not require complex optimizations and can be easily applied to unorganized high-dimensional data such as point clouds or  proximity graphs.   It can also represent arbitrary graph structures in the data.  We also give  theoretical results to justify our method.  We  provide a number of experiments to demonstrate the effectiveness and generality of our algorithm, including comparisons to existing methods, such as principal curves.  We believe that the simplicity and practicality of our algorithm will help to promote skeleton graphs as a data analysis tool for a broad range of applications.
Information Rates and Optimal Decoding in Large Neural Populations
Authors: Kamiar R. Rad, Liam Paninski
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Many fundamental questions in theoretical neuroscience involve optimal  decoding and the computation of Shannon information rates in  populations of spiking neurons.  In this paper, we apply methods from  the asymptotic theory of statistical inference to obtain a clearer  analytical understanding of these quantities.  We find that for large  neural populations carrying a finite total amount of information, the  full spiking population response is asymptotically as informative as a  single observation from a Gaussian process whose mean and covariance  can be characterized explicitly in terms of network and single neuron  properties.  The Gaussian form of this asymptotic sufficient  statistic allows us in certain cases to perform optimal Bayesian  decoding by simple linear transformations, and to obtain closed-form  expressions of the Shannon information carried by the network.  One  technical advantage of the theory is that it may be applied easily  even to non-Poisson point process network models; for example, we find  that under some conditions, neural populations with strong  history-dependent (non-Poisson) effects carry exactly the same  information as do simpler equivalent populations of non-interacting  Poisson neurons with matched firing rates.  We argue that our findings  help to clarify some results from the recent literature on neural  decoding and neuroprosthetic design.
Selective Prediction of Financial Trends with Hidden Markov Models
Authors: Dmitry Pidan, Ran El-Yaniv
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Prediction

Focusing on short term trend prediction in a financial context, we consider the problem of selective prediction whereby the predictor can abstain from prediction in order to improve performance. We examine two types of selective mechanisms for HMM predictors. The first is a rejection in the spirit of Chow’s well-known ambiguity principle. The second is a specialized mechanism for HMMs that identifies low quality HMM states and abstain from prediction in those states. We call this model selective HMM (sHMM). In both approaches we can trade-off prediction coverage to gain better accuracy in a controlled manner. We compare performance of the ambiguity-based rejection technique with that of the sHMM approach. Our results indicate that both methods are effective, and that the sHMM  model is superior.
Maximal Cliques that Satisfy Hard Constraints with Application to Deformable Object Model Learning
Authors: Xinggang Wang, Xiang Bai, Xingwei Yang, Wenyu Liu, Longin J. Latecki
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Object

We propose a novel inference framework for finding maximal cliques in a weighted graph that satisfy hard constraints.  The constraints specify the graph nodes that must belong to the solution as well as mutual exclusions of graph nodes, i.e., sets of nodes that cannot belong to the same solution.  The proposed inference is based on a novel particle filter algorithm with state permeations. We apply the inference framework to a challenging problem of learning part-based, deformable object models. Two core problems in the learning framework, matching of image patches and finding salient parts, are formulated as two instances of the problem of finding maximal cliques with hard constraints. Our learning framework yields discriminative part based object models that achieve very good detection rate, and outperform other methods on object classes with large deformation.
Distributed Delayed Stochastic Optimization
Authors: Alekh Agarwal, John C. Duchi
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Distributed Optimization, Stochastic Optimization

We analyze the convergence of gradient-based optimization algorithms whose updates depend on delayed stochastic gradient information. The  main application of our results is to the development of distributed  minimization algorithms where a master node performs parameter updates while worker nodes compute stochastic gradients based on local information in parallel, which may give rise to delays due to  asynchrony. Our main contribution is to show that for smooth stochastic problems, the delays are asymptotically negligible. In  application to distributed optimization, we show $n$-node architectures whose optimization error in stochastic problems---in spite of asynchronous delays---scales asymptotically as $\order(1 / \sqrt{nT})$, which is known to be optimal even in the absence of delays.
Greedy Algorithms for Structurally Constrained High Dimensional Problems
Authors: Ambuj Tewari, Pradeep K. Ravikumar, Inderjit S. Dhillon
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Vocal Bursts Intensity Prediction

A hallmark of modern machine learning is its ability to deal with high dimensional problems by exploiting structural assumptions that limit the degrees of freedom in the underlying model.  A deep understanding of the capabilities and limits of high dimensional learning methods under specific assumptions such as sparsity, group sparsity, and low rank has been attained.  Efforts (Negahban et al., 2010, Chandrasekaran et al., 2010} are now underway to distill this valuable experience by proposing general unified frameworks that can achieve the twin goals of summarizing previous analyses and enabling their application to notions of structure hitherto unexplored. Inspired by these developments, we propose and analyze a general computational scheme based on a greedy strategy to solve convex optimization problems that arise when dealing with structurally constrained high-dimensional problems. Our framework not only unifies existing greedy algorithms by recovering them as special cases but also yields novel ones. Finally, we extend our results to infinite dimensional problems by using interesting connections between smoothness of norms and behavior of martingales in Banach spaces.
Newtron: an Efficient Bandit algorithm for Online Multiclass Prediction
Authors: Elad Hazan, Satyen Kale
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We present an efficient algorithm for the problem of online multiclass prediction with bandit feedback in the fully adversarial setting. We measure its regret with respect to the log-loss defined in \cite{AbernethyR09}, which is parameterized by a scalar \(\alpha\). We prove that the regret of \newtron is \(O(\log T)\) when \(\alpha\) is a constant that does not vary with horizon \(T\), and at most \(O(T^{2/3})\) if \(\alpha\) is allowed to increase to infinity with \(T\). For \(\alpha\) = \(O(\log T)\), the regret is bounded by \(O(\sqrt{T})\), thus solving the open problem of \cite{KST08, AbernethyR09}. Our algorithm is based on a novel application of the online Newton method \cite{HAK07}. We test our algorithm and show it to perform well in experiments, even when \(\alpha\) is a small constant.