pwc-archive/papers-with-abstracts huggingface dataset:
Manifold-based Similarity Adaptation for Label Propagation
Authors: Masayuki Karasuyama, Hiroshi Mamitsuka
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Label propagation is one of the state-of-the-art methods for semi-supervised learning, which estimates labels by propagating label information through a graph. Label propagation assumes that data points (nodes) connected in a graph should have similar labels. Consequently, the label estimation heavily depends on edge weights in a graph which represent similarity of each node pair. We propose a method for a graph to capture the manifold structure of input features using edge weights parameterized by a similarity function. In this approach, edge weights represent both similarity and local reconstruction weight simultaneously, both being reasonable for label propagation. For further justification, we provide analytical considerations including an interpretation as a cross-validation of a propagation model in the feature space, and an error analysis based on a low dimensional manifold model. Experimental results demonstrated the effectiveness of our approach both in synthetic and real datasets.
Non-Uniform Camera Shake Removal Using a Spatially-Adaptive Sparse Penalty
Authors: Haichao Zhang, David Wipf
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Bayesian Inference, Deblurring

Typical blur from camera shake often deviates from the standard uniform convolutional assumption, in part because of problematic rotations which create greater blurring away from some unknown center point.  Consequently, successful blind deconvolution for removing shake artifacts requires the estimation of a spatially-varying or non-uniform blur operator.  Using ideas from Bayesian inference and convex analysis, this paper derives a non-uniform blind deblurring algorithm with several desirable, yet previously-unexplored attributes.  The underlying objective function includes a spatially-adaptive penalty that couples the latent sharp image, non-uniform blur operator, and noise level together.  This coupling allows the penalty to automatically adjust its shape based on the estimated degree of local blur and image structure such that regions with large blur or few prominent edges are discounted.  Remaining regions with modest blur and revealing edges therefore dominate the overall estimation process without explicitly incorporating structure-selection heuristics.  The algorithm can be implemented using an optimization strategy  that is virtually parameter free and simpler than existing methods.  Detailed theoretical analysis and empirical validation on real images serve to validate the proposed method.
Learning to Prune in Metric and Non-Metric Spaces
Authors: Leonid Boytsov, Bilegsaikhan Naidan
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Density Estimation, Retrieval

Our focus is on approximate nearest neighbor retrieval in metric and non-metric spaces. We employ a VP-tree and explore two simple yet effective learning-to prune approaches: density estimation through sampling and “stretching” of the triangle inequality. Both methods are evaluated using data sets with metric (Euclidean) and non-metric (KL-divergence and Itakura-Saito) distance functions. Conditions on spaces where the VP-tree is applicable are discussed. The VP-tree with a learned pruner is compared against the recently proposed state-of-the-art approaches: the bbtree, the multi-probe locality sensitive hashing (LSH), and permutation methods. Our method was competitive against state-of-the-art methods and, in most cases, was more efficient for the same rank approximation quality.
Online learning in episodic Markovian decision processes by relative entropy policy search
Authors: Alexander Zimin, Gergely Neu
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

We study the problem of online learning in finite episodic Markov decision processes where the loss function is allowed to change between episodes. The natural performance measure in this learning problem is the regret defined as the difference between the total loss of the best stationary policy and the total loss suffered by the learner. We assume that the learner is given access to a finite action space $\A$ and the state space $\X$ has a layered structure with $L$ layers, so that state transitions are only possible between consecutive layers. We describe a variant of the recently proposed Relative Entropy Policy Search algorithm and show that its regret after $T$ episodes is $2\sqrt{L\nX\nA T\log(\nX\nA/L)}$ in the bandit setting and $2L\sqrt{T\log(\nX\nA/L)}$ in the full information setting. These guarantees largely improve previously known results under much milder assumptions and cannot be significantly improved under general assumptions.
Optimistic policy iteration and natural actor-critic: A unifying view and a non-optimality result
Authors: Paul Wagner
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Policy Gradient Methods, Reinforcement Learning

Approximate dynamic programming approaches to the reinforcement learning problem are often categorized into greedy value function methods and value-based policy gradient methods. As our first main result, we show that an important subset of the latter methodology is, in fact, a limiting special case of a general formulation of the former methodology; optimistic policy iteration encompasses not only most of the greedy value function methods but also natural actor-critic methods, and permits one to directly interpolate between them. The resulting continuum adjusts the strength of the Markov assumption in policy improvement and, as such, can be seen as dual in spirit to the continuum in TD($\lambda$)-style algorithms in policy evaluation. As our second main result, we show for a substantial subset of soft-greedy value function approaches that, while having the potential to avoid policy oscillation and policy chattering, this subset can never converge toward any optimal policy, except in a certain pathological case. Consequently, in the context of approximations, the majority of greedy value function methods seem to be deemed to suffer either from the risk of oscillation/chattering or from the presence of systematic sub-optimality.
Bayesian Hierarchical Community Discovery
Authors: Charles Blundell, Yee Whye Teh
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Model Selection

We propose an efficient Bayesian nonparametric model for discovering hierarchical community structure in social networks. Our model is a tree-structured mixture of potentially exponentially many stochastic blockmodels. We describe a family of greedy agglomerative model selection algorithms whose worst case scales quadratically in the number of vertices of the network, but independent of the number of communities. Our algorithms are two orders of magnitude faster than the infinite relational model, achieving comparable or better accuracy.
Pass-efficient unsupervised feature selection
Authors: Crystal Maung, Haim Schweitzer
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: feature selection

The goal of unsupervised feature selection is to identify a small number of important features that can represent the data. We propose a new algorithm, a modification of the classical pivoted QR algorithm of Businger and Golub, that requires a small number of passes over the data. The improvements are based on two ideas: keeping track of multiple features in each pass, and skipping calculations that can be shown not to affect the final selection. Our algorithm selects the exact same features as the classical pivoted QR algorithm, and has the same favorable numerical stability. We describe experiments on real-world datasets which sometimes show improvements of {\em several orders of magnitude} over the classical algorithm. These results appear to be competitive with  recently proposed randomized algorithms in terms of pass efficiency and run time. On the other hand, the randomized algorithms may produce better features, at the cost of small probability of failure.
Simultaneous Rectification and Alignment via Robust Recovery of Low-rank Tensors
Authors: Xiaoqin Zhang, Di Wang, Zhengyuan Zhou, Yi Ma
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Computational Efficiency

In this work, we propose a general method for recovering low-rank three-order tensors, in which the data can be deformed by some unknown transformation and corrupted by arbitrary sparse errors. Since the unfolding matrices of a tensor are interdependent, we introduce auxiliary variables and relax the hard equality constraints by the augmented Lagrange multiplier method. To improve the computational efficiency, we introduce a proximal gradient step to the alternating direction minimization method. We have provided proof for the convergence of the linearized version of the problem which is the inner loop of the overall algorithm. Both simulations and experiments show that our methods are more efficient and effective than previous work. The proposed method can be easily applied to simultaneously  rectify and align multiple images or videos frames. In this context, the state-of-the-art algorithms RASL'' and "TILT'' can be viewed as two special cases of our work, and yet each only performs part of the function of our method."
Bayesian Mixture Modelling and Inference based Thompson Sampling in Monte-Carlo Tree Search
Authors: Aijun Bai, Feng Wu, Xiaoping Chen
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Thompson Sampling

Monte-Carlo tree search is drawing great interest in the domain of planning under uncertainty, particularly when little or no domain knowledge is available. One of the central problems is the trade-off between exploration and exploitation. In this paper we present a novel Bayesian mixture modelling and inference based Thompson sampling approach to addressing this dilemma. The proposed Dirichlet-NormalGamma MCTS (DNG-MCTS) algorithm represents the uncertainty of the accumulated reward for actions in the MCTS search tree as a mixture of Normal distributions and inferences on it in Bayesian settings by choosing conjugate priors in the form of combinations of Dirichlet and NormalGamma distributions. Thompson sampling is used to select the best action at each decision node. Experimental results show that our proposed algorithm has achieved the state-of-the-art comparing with popular UCT algorithm in the context of online planning for general Markov decision processes.
Solving inverse problem of Markov chain with partial observations
Authors: Tetsuro Morimura, Takayuki Osogami, Tsuyoshi Ide
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

The Markov chain is a convenient tool to represent the dynamics of complex systems such as traffic and social systems, where probabilistic transition takes place between internal states. A Markov chain is characterized by initial-state probabilities and a state-transition probability matrix. In the traditional setting, a major goal is to figure out properties of a Markov chain when those probabilities are known. This paper tackles an inverse version of the problem: we find those probabilities from partial observations at a limited number of states. The observations include the frequency of visiting a state and the rate of reaching a state from another. Practical examples of this task include traffic monitoring systems in cities, where we need to infer the traffic volume on every single link on a road network from a very limited number of observation points. We formulate this task as a regularized optimization problem for probability functions, which is efficiently solved using the notion of natural gradient. Using synthetic and real-world data sets including city traffic monitoring data, we demonstrate the effectiveness of our method.
Locally Adaptive Bayesian Multivariate Time Series
Authors: Daniele Durante, Bruno Scarpa, David B. Dunson
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Bayesian Inference, Time Series, Time Series Analysis

In modeling multivariate time series, it is important to allow time-varying smoothness in the mean and covariance process. In particular, there may be certain time intervals exhibiting rapid changes and others in which changes are slow. If such locally adaptive smoothness is not accounted for, one can obtain misleading inferences and predictions, with over-smoothing across erratic time intervals and under-smoothing across times exhibiting slow variation. This can lead to miscalibration of predictive intervals, which can be substantially too narrow or wide depending on the time. We propose a continuous multivariate stochastic process for time series having locally varying smoothness in both the mean and covariance matrix. This process is constructed utilizing latent dictionary functions in time, which are given nested Gaussian process priors and linearly related to the observed data through a sparse mapping. Using a differential equation representation, we bypass usual computational bottlenecks in obtaining MCMC and online algorithms for approximate Bayesian inference. The performance is assessed in simulations and illustrated in a financial application.
Mapping paradigm ontologies to and from the brain
Authors: Yannick Schwartz, Bertrand Thirion, Gael Varoquaux
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Imaging neuroscience links brain activation maps to behavior and cognition via correlational studies. Due to the nature of the individual experiments, based on eliciting neural response from a small number of stimuli, this link is incomplete, and unidirectional from the causal point of view. To come to conclusions on the function implied  by the activation of brain regions, it is necessary to combine a wide exploration of the various brain functions and some inversion of the statistical inference. Here we introduce a methodology for accumulating knowledge towards a bidirectional link between observed brain activity and the corresponding function. We rely on a large corpus of imaging studies and a predictive engine. Technically, the challenges are to find commonality between the studies without denaturing the richness of the corpus. The key elements that we contribute are labeling the tasks performed with a cognitive ontology, and modeling the long tail of rare paradigms in the corpus. To our knowledge, our approach is the first demonstration of predicting the cognitive content of completely new brain images. To that end, we propose a method that predicts the experimental paradigms across different studies.
Noise-Enhanced Associative Memories
Authors: Amin Karbasi, Amir Hesam Salavati, Amin Shokrollahi, Lav R. Varshney
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Hippocampus

Recent advances in associative memory design through structured pattern sets and graph-based inference algorithms have allowed reliable learning and recall of an exponential number of patterns. Although these designs correct external errors in recall, they assume neurons that compute noiselessly, in contrast to the highly variable neurons in hippocampus and olfactory cortex.  Here we consider associative memories with noisy internal computations and analytically characterize performance. As long as the internal noise level is below a specified threshold, the error probability in the recall phase can be made exceedingly small. More surprisingly, we show that internal noise actually improves the performance of the recall phase. Computational experiments lend additional support to our theoretical analysis. This work suggests a functional benefit to noisy neurons in biological neuronal networks.
Exact and Stable Recovery of Pairwise Interaction Tensors
Authors: Shouyuan Chen, Michael R. Lyu, Irwin King, Zenglin Xu
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Attribute, Collaborative Filtering

Tensor completion from incomplete observations is a problem of significant practical interest.  However, it is unlikely that there exists an efficient algorithm with provable guarantee to recover a general tensor from a limited number of observations. In this paper, we study the recovery algorithm for pairwise interaction tensors, which has recently gained considerable attention for modeling multiple attribute data due to its simplicity and effectiveness. Specifically, in the absence of noise, we show that one can exactly recover a pairwise interaction tensor by solving a constrained convex program which minimizes the weighted sum of nuclear norms of matrices from $O(nr\log^2(n))$ observations.  For the noisy cases, we also prove error bounds for a constrained convex program for recovering the tensors. Our experiments on the synthetic dataset demonstrate that the recovery performance of our algorithm agrees well with the theory. In addition, we apply our algorithm on a temporal collaborative filtering task and obtain state-of-the-art results.
Bayesian entropy estimation for binary spike train data using parametric prior knowledge
Authors: Evan W. Archer, Il Memming Park, Jonathan W. Pillow
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Shannon's entropy is a basic quantity in information theory, and a  fundamental building block for the analysis of neural codes.   Estimating the entropy of a discrete distribution from samples is an important and difficult problem that has received considerable   attention in statistics and theoretical neuroscience.  However,  neural responses have characteristic statistical structure that   generic entropy estimators fail to exploit.  For example, existing  Bayesian entropy estimators make the naive assumption that all spike   words are equally likely a priori, which makes for an  inefficient allocation of prior probability mass in cases where   spikes are sparse.  Here we develop Bayesian estimators for the  entropy of binary spike trains using priors designed to flexibly   exploit the statistical structure of simultaneously-recorded spike  responses.  We define two prior distributions over spike words using   mixtures of Dirichlet distributions centered on simple parametric  models.  The parametric model captures high-level statistical   features of the data, such as the average spike count in a spike  word, which allows the posterior over entropy to concentrate more   rapidly than with standard estimators (e.g., in cases where the  probability of spiking differs strongly from 0.5). Conversely, the   Dirichlet distributions assign prior mass to distributions far from  the parametric model, ensuring consistent estimates for arbitrary   distributions.  We devise a compact representation of the data and  prior that allow for computationally efficient implementations of   Bayesian least squares and empirical Bayes entropy estimators with  large numbers of neurons.  We apply these estimators to simulated   and real neural data and show that they substantially outperform  traditional methods.
Perfect Associative Learning with Spike-Timing-Dependent Plasticity
Authors: Christian Albers, Maren Westkott, Klaus Pawelzik
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Recent extensions of the Perceptron, as e.g. the Tempotron, suggest that this theoretical concept is highly relevant also for understanding networks of spiking neurons in the brain. It is not known, however, how the computational power of the Perceptron and of its variants might be accomplished by the plasticity mechanisms of real synapses. Here we prove that spike-timing-dependent plasticity having an anti-Hebbian form for excitatory synapses as well as a spike-timing-dependent plasticity of Hebbian shape for inhibitory synapses are sufficient for realizing the original Perceptron Learning Rule if the respective plasticity mechanisms act in concert with the hyperpolarisation of the post-synaptic neurons. We also show that with these simple yet biologically realistic dynamics Tempotrons are efficiently learned. The proposed mechanism might underly the acquisition of mappings of spatio-temporal activity patterns in one area of the brain onto other spatio-temporal spike patterns in another region and of long term memories in cortex. Our results underline that learning processes in realistic networks of spiking neurons depend crucially on the interactions of synaptic plasticity mechanisms with the dynamics of participating neurons.
On Poisson Graphical Models
Authors: Eunho Yang, Pradeep K. Ravikumar, Genevera I. Allen, Zhandong Liu
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: valid

Undirected graphical models, such as Gaussian graphical models, Ising, and multinomial/categorical graphical models, are widely used in a variety of applications for modeling distributions over a large number of variables. These standard instances, however, are ill-suited to modeling count data, which are increasingly ubiquitous in big-data settings such as genomic sequencing data, user-ratings data, spatial incidence data, climate studies, and site visits. Existing classes of Poisson graphical models, which arise as the joint distributions that correspond to Poisson distributed node-conditional distributions, have a major drawback: they can only model negative conditional dependencies for reasons of normalizability given its infinite domain. In this paper, our objective is to modify the Poisson graphical model distribution so that it can capture a rich dependence structure between count-valued variables. We begin by discussing two strategies for truncating the Poisson distribution and show that only one of these leads to a valid joint distribution; even this model, however, has limitations on the types of variables and dependencies that may be modeled. To address this, we propose two novel variants of the Poisson distribution and their corresponding joint graphical model distributions.  These models provide a class of Poisson graphical models that can capture both positive and negative conditional dependencies between count-valued variables. One can learn the graph structure of our model via penalized neighborhood selection, and we demonstrate the performance of our methods by learning simulated networks as well as a network from microRNA-Sequencing data.
Extracting regions of interest from biological images with convolutional sparse block coding
Authors: Marius Pachitariu, Adam M. Packer, Noah Pettit, Henry Dalgleish, Michael Hausser, Maneesh Sahani
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Biological tissue is often composed of cells with similar morphologies replicated throughout large volumes and many biological applications rely on the accurate identification of these cells and their locations from image data. Here we develop a generative model that captures the regularities present in images composed of repeating elements of a few different types. Formally, the model can be described as convolutional sparse block coding. For inference we use a variant of convolutional matching pursuit adapted to block-based representations. We extend the K-SVD learning algorithm to subspaces by retaining several principal vectors from the SVD decomposition instead of just one. Good models with little cross-talk between subspaces can be obtained by learning the blocks incrementally. We perform extensive experiments on simulated images and the inference algorithm consistently recovers a large proportion of the cells with a small number of false positives. We fit the convolutional model to noisy GCaMP6 two-photon images of spiking neurons and to Nissl-stained slices of cortical tissue and show that it recovers cell body locations without supervision. The flexibility of the block-based representation is reflected in the variability of the recovered cell shapes.