pwc-archive/papers-with-abstracts huggingface dataset:
Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
Authors: Rishabh K. Iyer, Jeff A. Bilmes
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Diversity

We investigate two new optimization problems — minimizing a submodular function subject to a submodular lower bound constraint (submodular cover) and maximizing a submodular function subject to a submodular upper bound constraint (submodular knapsack). We are motivated by a number of real-world applications in machine learning including sensor placement and data subset selection, which require maximizing a certain submodular function (like coverage or diversity) while simultaneously minimizing another (like cooperative cost). These problems are often posed as minimizing the difference between submodular functions [9, 23] which is in the worst case inapproximable. We show, however, that by phrasing these problems as constrained optimization, which is more natural for many applications, we achieve a number of bounded approximation guarantees. We also show that both these problems are closely related and, an approximation algorithm solving one can be used to obtain an approximation guarantee for the other. We provide hardness results for both problems thus showing that our approximation factors are tight up to log-factors. Finally, we empirically demonstrate the performance and good scalability properties of our algorithms.
Scalable Inference for Logistic-Normal Topic Models
Authors: Jianfei Chen, Jun Zhu, Zi Wang, Xun Zheng, Bo Zhang
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Data Augmentation, Topic Models

Logistic-normal topic models can effectively discover correlation structures among latent topics. However, their inference remains a challenge because of the non-conjugacy between the logistic-normal prior and multinomial topic mixing proportions. Existing algorithms either make restricting mean-field assumptions or are not scalable to large-scale applications. This paper presents a partially collapsed Gibbs sampling algorithm that approaches the provably correct distribution by exploring the ideas of data augmentation. To improve time efficiency, we further present a parallel implementation that can deal with large-scale applications and learn the correlation structures of thousands of topics from millions of documents. Extensive empirical results demonstrate the promise.
Spectral methods for neural characterization using generalized quadratic models
Authors: Il Memming Park, Evan W. Archer, Nicholas Priebe, Jonathan W. Pillow
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Form

We describe a set of fast, tractable methods for characterizing neural responses to high-dimensional sensory stimuli using a model we refer to as the generalized quadratic model (GQM). The GQM consists of a low-rank quadratic form followed by a point nonlinearity and exponential-family noise. The quadratic form characterizes the neuron's stimulus selectivity in terms of a set linear receptive fields followed by a quadratic combination rule, and the invertible nonlinearity maps this output to the desired response range. Special cases of the GQM include the 2nd-order Volterra model (Marmarelis and Marmarelis 1978, Koh and Powers 1985) and the elliptical Linear-Nonlinear-Poisson model (Park and Pillow 2011). Here we show that for canonical form" GQMs, spectral decomposition of the first two response-weighted moments yields approximate maximum-likelihood estimators via a quantity called the expected log-likelihood. The resulting theory generalizes moment-based estimators such as the spike-triggered covariance, and, in the Gaussian noise case, provides closed-form estimators under a large class of non-Gaussian stimulus distributions. We show that these estimators are fast and provide highly accurate estimates with far lower computational cost than full maximum likelihood. Moreover, the GQM provides a natural framework for combining multi-dimensional stimulus sensitivity and spike-history dependencies within a single model. We show applications to both analog and spiking data using intracellular recordings of V1 membrane potential and extracellular recordings of retinal spike trains."
Universal models for binary spike patterns using centered Dirichlet processes
Authors: Il Memming Park, Evan W. Archer, Kenneth Latimer, Jonathan W. Pillow
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Probabilistic models for binary spike patterns provide a powerful   tool for understanding the statistical dependencies in large-scale   neural recordings.  Maximum entropy (or maxent'') models, which   seek to explain dependencies in terms of low-order interactions   between neurons, have enjoyed remarkable success in modeling such   patterns, particularly for small groups of neurons. However, these   models are computationally intractable for large populations, and   low-order maxent models have been shown to be inadequate for some   datasets.  To overcome these limitations, we propose a family of   "universal'' models for binary spike patterns, where universality   refers to the ability to model arbitrary distributions over all   $2^m$ binary patterns.  We construct universal models using a   Dirichlet process centered on a well-behaved parametric base   measure, which naturally combines the flexibility of a histogram and   the parsimony of a parametric model.  We derive computationally   efficient inference methods using Bernoulli and cascade-logistic   base measures, which scale tractably to large populations. We also   establish a condition for equivalence between the cascade-logistic   and the 2nd-order maxent or "Ising'' model, making cascade-logistic   a reasonable choice for base measure in a universal model. We illustrate the performance of these models using neural data."
Synthesizing Robust Plans under Incomplete Domain Models
Authors: Tuan A. Nguyen, Subbarao Kambhampati, Minh Do
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Most current planners assume complete domain models and focus on generating correct plans. Unfortunately, domain modeling is a laborious and error-prone task, thus real world agents have to plan with incomplete domain models. While domain experts cannot guarantee completeness, often they are able to circumscribe the incompleteness of the model by providing annotations as to which parts of the domain model may be incomplete. In such cases, the goal should be to synthesize plans that are robust with respect to any known incompleteness of the domain. In this paper, we first introduce annotations expressing the knowledge of the domain incompleteness and formalize the notion of plan robustness with respect to an incomplete domain model. We then show an approach to compiling the problem of finding robust plans to the conformant probabilistic planning problem, and present experimental results with Probabilistic-FF planner.
Integrated Non-Factorized Variational Inference
Authors: Shaobo Han, Xuejun Liao, Lawrence Carin
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Variational Inference

We present a non-factorized variational method for full posterior inference in Bayesian hierarchical models,  with the goal of capturing the posterior variable dependencies via efficient and possibly parallel computation. Our approach unifies the integrated nested Laplace approximation (INLA) under the variational framework. The proposed method is applicable in more challenging scenarios than typically assumed by INLA,  such as Bayesian Lasso,  which is characterized by the non-differentiability of the $\ell_{1}$ norm arising from independent Laplace priors. We derive an upper bound for the Kullback-Leibler divergence,  which yields a fast closed-form solution via decoupled optimization. Our method is a reliable analytic alternative to Markov chain Monte Carlo (MCMC), and it results in a tighter evidence lower bound than that of mean-field variational Bayes (VB) method.
Symbolic Opportunistic Policy Iteration for Factored-Action MDPs
Authors: Aswin Raghavan, Roni Khardon, Alan Fern, Prasad Tadepalli
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

We address the scalability of symbolic planning under uncertainty with factored states and actions. Prior work has focused almost exclusively on factored states but not factored actions, and on value iteration (VI) compared to policy iteration (PI). Our ﬁrst contribution is a novel method for symbolic policy backups via the application of constraints, which is used to yield a new efﬁcient symbolic imple- mentation of modiﬁed PI (MPI) for factored action spaces. While this approach improves scalability in some cases, naive handling of policy constraints comes with its own scalability issues. This leads to our second and main contribution, symbolic Opportunistic Policy Iteration (OPI), which is a novel convergent al- gorithm lying between VI and MPI. The core idea is a symbolic procedure that applies policy constraints only when they reduce the space and time complexity of the update, and otherwise performs full Bellman backups, thus automatically adjusting the backup per state. We also give a memory bounded version of this algorithm allowing a space-time tradeoff. Empirical results show signiﬁcantly improved scalability over the state-of-the-art.
Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions
Authors: Yasin Abbasi, Peter L. Bartlett, Varun Kanade, Yevgeny Seldin, Csaba Szepesvari
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

We study the problem of online learning Markov Decision Processes (MDPs) when both the transition distributions and loss functions are chosen by an adversary. We present an algorithm that, under a mixing assumption, achieves $O(\sqrt{T\log|\Pi|}+\log|\Pi|)$ regret with respect to a comparison set of policies $\Pi$.  The regret is independent of the size of the state and action spaces. When expectations over sample paths can be computed efficiently and the comparison set $\Pi$ has polynomial size, this algorithm is efficient.  We also consider the episodic adversarial online shortest path problem.  Here, in each episode an adversary may choose a weighted directed acyclic graph with an identified start and finish node. The goal of the learning algorithm is to choose a path that minimizes the loss while traversing from the start to finish node. At the end of each episode the loss function (given by weights on the edges) is revealed to the learning algorithm. The goal is to minimize regret with respect to a fixed policy for selecting paths. This problem is a special case of the online MDP problem. For randomly chosen graphs and adversarial losses, this problem can be efficiently solved. We show that it also can be efficiently solved for adversarial graphs and randomly chosen losses.  When both graphs and losses are adversarially chosen, we present an efficient algorithm whose regret scales linearly with the number of distinct graphs.  Finally, we show that designing efficient algorithms for the adversarial online shortest path problem (and hence for the adversarial MDP problem) is as hard as learning parity with noise, a notoriously difficult problem that has been used to design efficient cryptographic schemes.
One-shot learning by inverting a compositional causal process
Authors: Brenden M. Lake, Ruslan R. Salakhutdinov, Josh Tenenbaum
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: General Classification, One-Shot Learning

People can learn a new visual class from just one example, yet machine learning algorithms typically require hundreds or thousands of examples to tackle the same problems. Here we present a Hierarchical Bayesian model based on compositionality and causality that can learn a wide range of natural (although simple) visual concepts, generalizing in human-like ways from just one image. We evaluated performance on a challenging one-shot classification task, where our model achieved a human-level error rate while substantially outperforming two deep learning models. We also used a visual Turing test" to show that our model produces human-like performance on other conceptual tasks, including generating new examples and parsing."
Statistical analysis of coupled time series with Kernel Cross-Spectral Density operators.
Authors: Michel Besserve, Nikos K. Logothetis, Bernhard Schölkopf
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Time Series, Time Series Analysis

Many applications require the analysis of complex interactions between time series. These interactions can be non-linear and involve vector valued as well as complex data structures such as graphs or strings. Here we provide a general framework for the statistical analysis of these interactions when random variables are sampled from stationary time-series of arbitrary objects. To achieve this goal we analyze the properties of the kernel cross-spectral density operator induced by positive definite kernels on arbitrary input domains. This framework enables us to develop an independence test between time series as well as a similarity measure to compare different types of coupling. The performance of our test is compared to the HSIC test using i.i.d. assumptions, showing improvement in terms of detection errors as well as the suitability of this approach for testing dependency in complex dynamical systems. Finally, we use this approach to characterize complex interactions in electrophysiological neural time series.
Fast Algorithms for Gaussian Noise Invariant Independent Component Analysis
Authors: James R. Voss, Luis Rademacher, Mikhail Belkin
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

The performance of standard algorithms for Independent Component Analysis quickly deteriorates under the addition of Gaussian noise. This is partially due to a common first step that typically consists of whitening, i.e., applying Principal Component Analysis (PCA) and rescaling the components to have identity covariance, which is not invariant under Gaussian noise.   In our paper we develop the first practical algorithm for Independent Component Analysis that is provably invariant under Gaussian noise. The two main contributions of this work are as follows: 1. We develop and implement a more efficient version of a Gaussian noise invariant decorrelation (quasi-orthogonalization) algorithm using Hessians of the cumulant functions. 2. We propose a very simple and efficient fixed-point GI-ICA (Gradient Iteration ICA) algorithm, which is compatible with quasi-orthogonalization, as well as with the usual PCA-based whitening in the noiseless case.  The algorithm is based on a special form of gradient iteration (different from gradient descent).   We provide an analysis of our algorithm demonstrating fast convergence following from the basic properties of cumulants. We also present a number of experimental comparisons with the existing methods, showing superior results on noisy data and very competitive performance in the noiseless case.
Deep Neural Networks for Object Detection
Authors: Christian Szegedy, Alexander Toshev, Dumitru Erhan
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: General Classification, image-classification, Image Classification, Object, object-detection, Object Detection, regression

Deep Neural Networks (DNNs) have recently shown outstanding performance on the task of whole image classification. In this paper we go one step further and address the problem of object detection -- not only classifying but also precisely localizing objects of various classes using DNNs. We present a simple and yet powerful formulation of object detection as a regression to object masks. We define a multi-scale inference procedure which is able to produce a high-resolution object detection at a low cost by a few network applications. The approach achieves state-of-the-art performance on Pascal 2007 VOC.
Geometric optimisation on positive definite matrices for elliptically contoured distributions
Authors: Suvrit Sra, Reshad Hosseini
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Riemannian optimization

Hermitian positive definite matrices (HPD) recur throughout statistics and machine learning. In this paper we develop \emph{geometric optimisation} for globally optimising certain nonconvex loss functions arising in the modelling of data via elliptically contoured distributions (ECDs). We exploit the remarkable structure of the convex cone of positive definite matrices which allows one to uncover hidden geodesic convexity of objective functions that are nonconvex in the ordinary Euclidean sense. Going even beyond manifold convexity we show how further metric properties of HPD matrices can be exploited to globally optimise several ECD log-likelihoods that are not even geodesic convex. We present key results that help recognise this geometric structure, as well as obtain efficient fixed-point algorithms to optimise the corresponding objective functions. To our knowledge, ours are the most general results on geometric optimisation of HPD matrices known so far. Experiments reveal the benefits of our approach---it avoids any eigenvalue computations which makes it very competitive.
Sign Cauchy Projections and Chi-Square Kernel
Authors: Ping Li, Gennady Samorodnitsk, John Hopcroft
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

The method of Cauchy random projections is popular  for computing the $l_1$ distance in high dimension. In this paper, we propose to use only the signs of the projected data and show that the  probability of collision (i.e., when the two signs differ) can be accurately approximated as a function of the chi-square ($\chi^2$) similarity, which is a popular  measure for nonnegative data (e.g., when features are generated from histograms as common in text and vision applications). Our experiments   confirm that this method of sign Cauchy random projections is promising for large-scale  learning applications. Furthermore, we extend the idea to sign $\alpha$-stable random projections and derive a bound of the collision probability.
Relevance Topic Model for Unstructured Social Group Activity Recognition
Authors: Fang Zhao, Yongzhen Huang, Liang Wang, Tieniu Tan
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Activity Recognition, Attribute, Group Activity Recognition, parameter estimation, Variational Inference

Unstructured social group activity recognition in web videos is a challenging task due to 1) the semantic gap between class labels and low-level visual features and 2) the lack of labeled training data. To tackle this problem, we propose a relevance topic model" for jointly learning meaningful mid-level representations upon bag-of-words (BoW) video representations and a classifier with sparse weights. In our approach, sparse Bayesian learning is incorporated into an undirected topic model (i.e., Replicated Softmax) to discover topics which are relevant to video classes and suitable for prediction. Rectified linear units are utilized to increase the expressive power of topics so as to explain better video data containing complex contents and make variational inference tractable for the proposed model. An efficient variational EM algorithm is presented for model parameter estimation and inference. Experimental results on the Unstructured Social Activity Attribute dataset show that our model achieves state of the art performance and outperforms other supervised topic model in terms of classification accuracy, particularly in the case of a very small number of labeled training videos."
k-Prototype Learning for 3D Rigid Structures
Authors: Hu Ding, Ronald Berezney, Jinhui Xu
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Clustering

In this paper, we study the following new variant of prototype learning, called {\em $k$-prototype learning problem for 3D rigid structures}: Given a set of 3D rigid structures, find a set of $k$ rigid structures so that each of them is a prototype for a cluster of the given rigid structures and the total cost (or dissimilarity) is minimized. Prototype learning is a core problem in machine learning and has a wide range of applications in many areas. Existing results on this problem have mainly focused on the graph domain. In this paper, we present the first algorithm for learning multiple prototypes from 3D rigid structures. Our result is based on a number of new insights to rigid structures alignment, clustering, and prototype reconstruction, and is practically efficient with quality guarantee. We validate our approach using two type of data sets, random data and biological data of chromosome territories. Experiments suggest that our approach can effectively learn prototypes in both types of data.
Restricting exchangeable nonparametric distributions
Authors: Sinead A. Williamson, Steve N. Maceachern, Eric P. Xing
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Distributions over exchangeable matrices with infinitely many columns are useful in constructing nonparametric latent variable models. However, the distribution implied by such models over the number of features exhibited by each data point may be poorly-suited for many modeling tasks. In this paper, we propose a class of exchangeable nonparametric priors obtained by restricting the domain of existing models. Such models allow us to specify the distribution over the number of features per data point, and can achieve better performance on data sets where the number of features is not well-modeled by the original distribution.
Forgetful Bayes and myopic planning: Human learning and decision-making in a bandit setting
Authors: Shunan Zhang, Angela J. Yu
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Decision Making

How humans achieve long-term goals in an uncertain environment, via repeated trials and noisy observations, is an important problem in cognitive science. We investigate this behavior in the context of a multi-armed bandit task. We compare human behavior to a variety of models that vary in their representational and computational complexity. Our result shows that subjects' choices, on a trial-to-trial basis, are best captured by a forgetful" Bayesian iterative learning model in combination with a partially myopic decision policy known as Knowledge Gradient. This model accounts for subjects' trial-by-trial choice better than a number of other previously proposed models, including optimal Bayesian learning and risk minimization, epsilon-greedy and win-stay-lose-shift. It has the added benefit of being closest in performance to the optimal Bayesian model than all the other heuristic models that have the same computational complexity (all are significantly less complex than the optimal model). These results constitute an advancement in the theoretical understanding of how humans negotiate the tension between exploration and exploitation in a noisy, imperfectly known environment."
Probabilistic Movement Primitives
Authors: Alexandros Paraschos, Christian Daniel, Jan R. Peters, Gerhard Neumann
Date: 2013-12-01 00:00:00
Proceeding: NeurIPS 2013 12

Movement Primitives (MP) are a well-established approach for representing modular and re-usable robot movement generators. Many state-of-the-art robot learning successes are based MPs, due to their compact representation of the inherently continuous and high dimensional robot movements. A major goal in robot learning is to combine multiple MPs as building blocks in a modular control architecture to solve complex tasks. To this effect, a MP representation has to allow for blending between motions, adapting to altered task variables, and co-activating multiple MPs in parallel. We present a probabilistic formulation of the MP concept that maintains a distribution over trajectories. Our probabilistic approach allows for the derivation of new operations which are essential for implementing all aforementioned properties in one framework. In order to use such a trajectory distribution for robot movement control, we analytically derive a stochastic feedback controller which reproduces the given trajectory distribution. We evaluate and compare our approach to existing methods on several simulated as well as real robot scenarios.