pwc-archive/papers-with-abstracts huggingface dataset:
Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
Authors: Nathan Srebro, Ruslan R. Salakhutdinov
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Collaborative Filtering, Matrix Completion

We show that matrix completion with trace-norm regularization can be significantly hurt when entries of the matrix are sampled non-uniformly, but that a properly weighted version of the trace-norm regularizer works well with non-uniform sampling. We show that the weighted trace-norm regularization indeed yields significant gains on the highly non-uniformly sampled Netflix dataset.
Implicitly Constrained Gaussian Process Regression for Monocular Non-Rigid Pose Estimation
Authors: Mathieu Salzmann, Raquel Urtasun
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Pose Estimation, Prediction, regression

Estimating 3D pose from monocular images is a highly ambiguous problem. Physical constraints can be exploited to restrict the space of feasible configurations. In this paper we propose an approach to constraining the prediction of a discriminative predictor. We first show that the mean prediction of a Gaussian process implicitly satisfies linear constraints if those constraints are satisfied by the training examples. We then show how, by performing a change of variables, a GP can be forced to satisfy quadratic constraints. As evidenced by the experiments, our method outperforms state-of-the-art approaches on the tasks of rigid and non-rigid pose estimation.
Deterministic Single-Pass Algorithm for LDA
Authors: Issei Sato, Kenichi Kurihara, Hiroshi Nakagawa
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We develop a deterministic single-pass algorithm for latent Dirichlet allocation (LDA) in order to process received documents one at a time and then discard them in an excess text stream. Our algorithm does not need to store old statistics for all data. The proposed algorithm is much faster than a batch algorithm and is comparable to the batch algorithm in terms of perplexity in experiments.
Active Estimation of F-Measures
Authors: Christoph Sawade, Niels Landwehr, Tobias Scheffer
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We address the problem of estimating the F-measure of a given model as accurately as possible on a fixed labeling budget. This problem occurs whenever an estimate cannot be obtained from held-out training data; for instance, when data that have been used to train the model are held back for reasons of privacy or do not reflect the test distribution. In this case, new test instances have to be drawn and labeled at a cost. An active estimation procedure selects instances according to an instrumental sampling distribution. An analysis of the sources of estimation error leads to an optimal sampling distribution that minimizes estimator variance. We explore conditions under which active estimates of F-measures are more accurate than estimates based on instances sampled from the test distribution.
Trading off Mistakes and Don't-Know Predictions
Authors: Amin Sayedi, Morteza Zadimoghaddam, Avrim Blum
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We discuss an online learning framework in which the agent is allowed to say ``I don't know'' as well as making incorrect predictions on given examples. We analyze the trade off between saying ``I don't know'' and making mistakes. If the number of don't know predictions is forced to be zero, the model reduces to the well-known mistake-bound model introduced by Littlestone [Lit88]. On the other hand, if no mistakes are allowed, the model reduces to KWIK framework introduced by Li et. al. [LLW08]. We propose a general, though inefficient, algorithm for general finite concept classes that minimizes the number of don't-know predictions if a certain number of mistakes are allowed. We then present specific polynomial-time algorithms for the concept classes of monotone disjunctions and linear separators.
Sparse Inverse Covariance Selection via Alternating Linearization Methods
Authors: Katya Scheinberg, Shiqian Ma, Donald Goldfarb
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

Gaussian graphical models are of great interest in statistical learning.  Because the conditional independencies between different nodes correspond to zero entries in the inverse covariance matrix of the Gaussian distribution, one can learn the structure of the graph by estimating a sparse inverse covariance matrix from sample data, by solving a convex maximum likelihood problem with an $\ell_1$-regularization term. In this paper, we propose a first-order method based on an alternating linearization technique that exploits the problem's special structure; in particular, the subproblems solved in each iteration have closed-form solutions. Moreover, our algorithm obtains an $\epsilon$-optimal solution in $O(1/\epsilon)$ iterations. Numerical experiments on both synthetic  and real data from gene association networks show that a practical version of  this algorithm outperforms other competitive algorithms.
Spike timing-dependent plasticity as dynamic filter
Authors: Joscha Schmiedt, Christian Albers, Klaus Pawelzik
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Hippocampus

When stimulated with complex action potential sequences synapses exhibit spike timing-dependent plasticity (STDP) with attenuated and enhanced pre- and postsynaptic contributions to long-term synaptic modifications. In order to investigate the functional consequences of these contribution dynamics (CD) we propose a minimal model formulated in terms of differential equations. We find that our model reproduces a wide range of experimental results with a small number of biophysically interpretable parameters. The model allows to investigate the susceptibility of STDP to arbitrary time courses of pre- and postsynaptic activities, i.e. its nonlinear filter properties. We demonstrate this for the simple example of small periodic modulations of pre- and postsynaptic firing rates for which our model can be solved. It predicts synaptic strengthening for synchronous rate modulations. For low baseline rates modifications are dominant in the theta frequency range, a result which underlines the well known relevance of theta activities in hippocampus and cortex for learning. We also find emphasis of low baseline spike rates and suppression for high baseline rates. The latter suggests a mechanism of network activity regulation inherent in STDP. Furthermore, our novel formulation provides a general framework for investigating the joint dynamics of neuronal activity and the CD of STDP in both spike-based as well as rate-based neuronal network models.
A novel family of non-parametric cumulative based divergences for point processes
Authors: Sohan Seth, Park Il, Austin Brockmeier, Mulugeta Semework, John Choi, Joseph Francis, Jose Principe
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Point Processes, Two-sample testing

Hypothesis testing on point processes has several applications such as model fitting, plasticity detection, and non-stationarity detection. Standard tools for hypothesis testing include tests on mean firing rate and time varying rate function. However, these statistics do not fully describe a point process and thus the tests can be misleading. In this paper, we introduce a family of non-parametric divergence measures for hypothesis testing. We extend the traditional Kolmogorov--Smirnov and Cramer--von-Mises tests for point process via stratification. The proposed divergence measures compare the underlying probability structure and, thus, is zero if and only if the point processes are the same. This leads to a more robust test of hypothesis. We prove consistency and show that these measures can be efficiently estimated from data. We demonstrate an application of using the proposed divergence as a cost function to find optimally matched spike trains.
Online Learning in The Manifold of Low-Rank Matrices
Authors: Uri Shalit, Daphna Weinshall, Gal Chechik
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: image-classification, Image Classification, Multi-Label Image Classification

When learning models that are represented in matrix forms, enforcing   a low-rank constraint can dramatically improve the memory and run   time complexity, while providing a natural regularization of the   model.  However, naive approaches for minimizing functions over the   set of low-rank matrices are either prohibitively time   consuming (repeated singular value decomposition of the matrix) or   numerically unstable (optimizing a factored representation of the   low rank matrix). We build on recent advances in optimization over   manifolds, and describe an iterative online learning procedure, consisting of a   gradient step, followed by a second-order retraction back to the   manifold. While the ideal retraction is hard to compute, and so is   the projection operator that approximates it, we describe another   second-order retraction that can be computed efficiently, with run   time and memory complexity of O((n+m)k) for a rank-k   matrix of dimension m x n, given rank one gradients.  We use   this algorithm, LORETA, to learn a matrix-form similarity measure over pairs of   documents represented as high dimensional vectors. LORETA   improves the mean average precision over a passive-   aggressive approach in a factorized model, and also improves over   a full model trained over pre-selected features using the same   memory requirements. LORETA also showed consistent improvement over   standard methods in a large (1600 classes) multi-label image classification task.
Identifying graph-structured activation patterns in networks
Authors: James Sharpnack, Aarti Singh
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We consider the problem of identifying an activation pattern in a complex, large-scale network that is embedded in very noisy measurements. This problem is relevant to several applications, such as identifying traces of a biochemical spread by a sensor network, expression levels of genes, and anomalous activity or congestion in the Internet. Extracting such patterns is a challenging task specially if the network is large (pattern is very high-dimensional) and the noise is so excessive that it masks the activity at any single node. However, typically there are statistical dependencies in the network activation process that can be leveraged to fuse the measurements of multiple nodes and enable reliable extraction of high-dimensional noisy patterns. In this paper, we analyze an estimator based on the graph Laplacian eigenbasis, and establish the limits of mean square error recovery of noisy patterns arising from a probabilistic (Gaussian or Ising) model based on an arbitrary graph structure. We consider both deterministic and probabilistic network evolution models, and our results indicate that by leveraging the network interaction structure, it is possible to consistently recover high-dimensional patterns even when the noise variance increases with network size.
A rational decision making framework for inhibitory control
Authors: Pradeep Shenoy, Angela J. Yu, Rajesh P. Rao
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Bayesian Inference, Decision Making

Intelligent agents are often faced with the need to choose actions with uncertain consequences, and to modify those actions according to ongoing sensory processing and changing task demands. The requisite ability to dynamically modify or cancel planned actions is known as inhibitory control in psychology. We formalize inhibitory control as a rational decision-making problem, and apply to it to the classical stop-signal task. Using Bayesian inference and stochastic control tools, we show that the optimal policy systematically depends on various parameters of the problem, such as the relative costs of different action choices, the noise level of sensory inputs, and the dynamics of changing environmental demands. Our normative model accounts for a range of behavioral data in humans and animals in the stop-signal task, suggesting that the brain implements statistically optimal, dynamically adaptive, and reward-sensitive decision-making in the context of inhibitory control problems.
Penalized Principal Component Regression on Graphs for Analysis of Subnetworks
Authors: Ali Shojaie, George Michailidis
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Dimensionality Reduction, regression

Network models are widely used to capture interactions among component of complex systems, such as social and biological. To understand their behavior, it is often necessary to analyze functionally related components of the system, corresponding to subsystems. Therefore, the analysis of subnetworks may provide additional insight into the behavior of the system, not evident from individual components. We propose a novel approach for incorporating available network information into the analysis of arbitrary subnetworks. The proposed method offers an efficient dimension reduction strategy using Laplacian eigenmaps with Neumann boundary conditions, and provides a flexible inference framework for analysis of subnetworks, based on a group-penalized principal component regression model on graphs. Asymptotic properties of the proposed inference method, as well as the choice of the tuning parameter for control of the false positive rate are discussed in high dimensional settings. The performance of the proposed methodology is illustrated using simulated and real data examples from biology.
Monte-Carlo Planning in Large POMDPs
Authors: David Silver, Joel Veness
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

This paper introduces a Monte-Carlo algorithm for online planning in large POMDPs. The algorithm combines a Monte-Carlo update of the agent's belief state with a Monte-Carlo tree search from the current belief state. The new algorithm, POMCP, has two important properties. First, Monte-Carlo sampling is used to break the curse of dimensionality both during belief state updates and during planning. Second, only a black box simulator of the POMDP is required, rather than explicit probability distributions. These properties enable POMCP to plan effectively in significantly larger POMDPs than has previously been possible. We demonstrate its effectiveness in three large POMDPs. We scale up a well-known benchmark problem, Rocksample, by several orders of magnitude. We also introduce two challenging new POMDPs: 10x10 Battleship and Partially Observable PacMan, with approximately 10^18 and 10^56 states respectively. Our Monte-Carlo planning algorithm achieved a high level of performance with no prior knowledge, and was also able to exploit simple domain knowledge to achieve better results with less search. POMCP is the first general purpose planner to achieve high performance in such large and unfactored POMDPs.
Sodium entry efficiency during action potentials: A novel single-parameter family of Hodgkin-Huxley models
Authors: Anand Singh, Renaud Jolivet, Pierre Magistretti, Bruno Weber
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

Sodium entry during an action potential determines the energy efficiency of a neuron. The classic Hodgkin-Huxley model of action potential generation is notoriously inefficient in that regard with about 4 times more charges flowing through the membrane than the theoretical minimum required to achieve the observed depolarization. Yet, recent experimental results show that mammalian neurons are close to the optimal metabolic efficiency and that the dynamics of their voltage-gated channels is significantly different than the one exhibited by the classic Hodgkin-Huxley model during the action potential. Nevertheless, the original Hodgkin-Huxley model is still widely used and rarely to model the squid giant axon from which it was extracted. Here, we introduce a novel family of Hodgkin-Huxley models that correctly account for sodium entry, action potential width and whose voltage-gated channels display a dynamics very similar to the most recent experimental observations in mammalian neurons. We speak here about a family of models because the model is parameterized by a unique parameter the variations of which allow to reproduce the entire range of experimental observations from cortical pyramidal neurons to Purkinje cells, yielding a very economical framework to model a wide range of different central neurons. The present paper demonstrates the performances and discuss the properties of this new family of models.
More data means less inference: A pseudo-max approach to structured learning
Authors: David Sontag, Ofer Meshi, Amir Globerson, Tommi S. Jaakkola
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

The problem of learning to predict structured labels is of key importance in many applications. However, for general graph structure both learning and inference in this setting are intractable. Here we show that it is possible to circumvent this difficulty when the input distribution is rich enough via a method similar in spirit to pseudo-likelihood. We show how our new method achieves consistency, and illustrate empirically that it indeed performs as well as exact methods when sufficiently large training sets are used.
Reward Design via Online Gradient Ascent
Authors: Jonathan Sorg, Richard L. Lewis, Satinder P. Singh
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

Recent work has demonstrated that when artificial agents are limited in their ability to achieve their goals, the agent designer can benefit by making the agent's goals different from the designer's. This gives rise to the optimization problem of designing the artificial agent's goals---in the RL framework, designing the agent's reward function. Existing attempts at solving this optimal reward problem do not leverage experience gained online during the agent's lifetime nor do they take advantage of knowledge about the agent's structure. In this work, we develop a gradient ascent approach with formal convergence guarantees for approximately solving the optimal reward problem online during an agent's lifetime. We show that our method generalizes a standard policy gradient approach, and we demonstrate its ability to improve reward functions in agents with various forms of limitations.
Smoothness, Low Noise and Fast Rates
Authors: Nathan Srebro, Karthik Sridharan, Ambuj Tewari
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We establish an excess risk bound of O(H R_n^2 + sqrt{H L*} R_n) for ERM with an H-smooth loss function and a hypothesis class with Rademacher complexity R_n, where L* is the best risk achievable by the hypothesis class. For typical hypothesis classes where R_n = sqrt{R/n}, this translates to a learning rate of ̃ O(RH/n) in the separable (L* = 0) case and O(RH/n + sqrt{L* RH/n}) more generally. We also provide similar guarantees for online and stochastic convex optimization of a smooth non-negative objective.
Efficient Minimization of Decomposable Submodular Functions
Authors: Peter Stobbe, Andreas Krause
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

Many combinatorial problems arising in machine learning can be reduced to the problem of minimizing a submodular function. Submodular functions are a natural discrete analog of convex functions, and can be minimized in strongly polynomial time. Unfortunately, state-of-the-art algorithms for general submodular minimization are intractable for practical problems. In this paper, we introduce a novel subclass of submodular minimization problems that we call decomposable. Decomposable submodular functions are those that can be represented as sums of concave functions applied to linear functions. We develop an algorithm, SLG, that can efficiently minimize decomposable submodular functions with tens of thousands of variables. Our algorithm exploits recent results in smoothed convex minimization. We apply SLG to synthetic benchmarks and a joint classification-and-segmentation task, and show that it outperforms the state-of-the-art general purpose submodular minimization algorithms by several orders of magnitude.
Layered image motion with explicit occlusions, temporal consistency, and depth ordering
Authors: Deqing Sun, Erik B. Sudderth, Michael J. Black
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Motion Estimation, Optical Flow Estimation, Scene Segmentation

Layered models are a powerful way of describing natural scenes containing smooth surfaces that may overlap and occlude each other. For image motion estimation, such models have a long history but have not achieved the wide use or accuracy of non-layered methods. We present a new probabilistic model of optical flow in layers that addresses many of the shortcomings of previous approaches. In particular, we define a probabilistic graphical model that explicitly captures: 1) occlusions and disocclusions; 2) depth ordering of the layers; 3) temporal consistency of the layer segmentation. Additionally the optical flow in each layer is modeled by a combination of a parametric model and a smooth deviation based on an MRF with a robust spatial prior; the resulting model allows roughness in layers. Finally, a key contribution is the formulation of the layers using an image-dependent hidden field prior based on recent models for static scene segmentation. The method achieves state-of-the-art results on the Middlebury benchmark and produces meaningful scene segmentations as well as detected occlusion regions.
Improving the Asymptotic Performance of Markov Chain Monte-Carlo by Inserting Vortices
Authors: Yi Sun, Jürgen Schmidhuber, Faustino J. Gomez
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12

We present a new way of converting a reversible finite Markov chain into a nonreversible one, with a theoretical guarantee that the asymptotic variance of the MCMC estimator based on the non-reversible chain is reduced. The method is applicable to any reversible chain whose states are not connected through a tree, and can be interpreted graphically as inserting vortices into the state transition graph. Our result confirms that non-reversible chains are fundamentally better than reversible ones in terms of asymptotic performance, and suggests interesting directions for further improving MCMC.
Semi-Supervised Learning with Adversarially Missing Label Information
Authors: Umar Syed, Ben Taskar
Date: 2010-12-01 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Generalization Bounds, parameter estimation

We address the problem of semi-supervised learning in an adversarial setting. Instead of assuming that labels are missing at random, we analyze a less favorable scenario where the label information can be missing partially and arbitrarily, which is motivated by several practical examples. We present nearly matching upper and lower generalization bounds for learning in this setting under reasonable assumptions about available label information. Motivated by the analysis, we formulate a convex optimization problem for parameter estimation, derive an efficient algorithm, and analyze its convergence. We provide experimental results on several standard data sets showing the robustness of our algorithm to the pattern of missing label information, outperforming several strong baselines.