pwc-archive/papers-with-abstracts huggingface dataset:
Grouped Orthogonal Matching Pursuit for Variable Selection and Prediction
Authors: Grzegorz Swirszcz, Naoki Abe, Aurelie C. Lozano
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: feature selection, Prediction, regression, Variable Selection

We consider the problem of variable group selection for least squares regression, namely, that of selecting groups of variables for best regression performance, leveraging and adhering to a natural grouping structure within the explanatory variables. We show that this problem can be efficiently addressed by using a certain greedy style algorithm. More precisely, we propose the Group Orthogonal Matching Pursuit algorithm (Group-OMP), which extends the standard OMP procedure (also referred to as ``forward greedy feature selection algorithm for least squares regression) to perform stage-wise group variable selection. We prove that under certain conditions Group-OMP can identify the correct (groups of) variables. We also provide an upperbound on the $l_\infty$ norm of the difference between the estimated regression coefficients and the true coefficients. Experimental results on simulated and real world datasets indicate that Group-OMP compares favorably to Group Lasso, OMP and Lasso, both in terms of variable selection and prediction accuracy.
Modeling the spacing effect in sequential category learning
Authors: Hongjing Lu, Matthew Weiden, Alan L. Yuille
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We develop a Bayesian sequential model for category learning. The sequential model updates two category parameters, the mean and the variance, over time. We define conjugate temporal priors to enable closed form solutions to be obtained. This model can be easily extended to supervised and unsupervised learning involving multiple categories. To model the spacing effect, we introduce a generic prior in the temporal updating stage to capture a learning preference, namely, less change for repetition and more change for variation. Finally, we show how this approach can be generalized to efficiently performmodel selection to decide whether observations are from one or multiple categories.
Who’s Doing What: Joint Modeling of Names and Verbs for Simultaneous Face and Pose Annotation
Authors: Jie Luo, Barbara Caputo, Vittorio Ferrari
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Given a corpus of news items consisting of images accompanied by text captions, we want to find out ``whos doing what, i.e. associate names and action verbs in the captions to the face and body pose of the persons in the images. We present a joint model for simultaneously solving the image-caption correspondences and learning visual appearance models for the face and pose classes occurring in the corpus. These models can then be used to recognize people and actions in novel images without captions. We demonstrate experimentally that our joint `face and pose model solves the correspondence problem better than earlier models covering only the face, and that it can perform recognition of new uncaptioned images.
Variational Gaussian-process factor analysis for modeling spatio-temporal data
Authors: Jaakko Luttinen, Alexander Ilin
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We present a probabilistic latent factor model which can be used for studying spatio-temporal datasets. The spatial and temporal structure is modeled by using Gaussian process priors both for the loading matrix and the factors. The posterior distributions are approximated using the variational Bayesian framework. High computational cost of Gaussian process modeling is reduced by using sparse approximations. The model is used to compute the reconstructions of the global sea surface temperatures from a historical dataset. The results suggest that the proposed model can outperform the state-of-the-art reconstruction systems.
Solving Stochastic Games
Authors: Liam M. Dermed, Charles L. Isbell
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Multi-agent Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Solving multi-agent reinforcement learning problems has proven difficult because of the lack of tractable algorithms.  We provide the first approximation algorithm which solves stochastic games to within $\epsilon$ relative error of the optimal game-theoretic solution, in time polynomial in $1/\epsilon$. Our algorithm extends Murrays and Gordon’s (2007) modified Bellman equation which determines the \emph{set} of all possible achievable utilities; this provides us a truly general framework for multi-agent learning. Further, we empirically validate our algorithm and find the computational cost to be orders of magnitude less than what the theory predicts.
Bayesian estimation of orientation preference maps
Authors: Sebastian Gerwinn, Leonard White, Matthias Kaschube, Matthias Bethge, Jakob H. Macke
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Gaussian Processes

Imaging techniques such as optical imaging of intrinsic signals, 2-photon calcium imaging and voltage sensitive dye imaging can be used to measure the functional organization of visual cortex across different spatial scales. Here, we present Bayesian methods based on Gaussian processes for extracting topographic maps from functional imaging data.  In particular, we focus on the estimation of orientation preference maps (OPMs) from intrinsic signal imaging data.  We model the underlying map as a bivariate Gaussian process, with a prior covariance function that reflects known properties of OPMs, and a noise covariance adjusted to the data.  The posterior mean can be interpreted as an optimally smoothed estimate of the map, and can be used for model based interpolations of the map from sparse measurements.  By sampling from the posterior distribution, we can get error bars on statistical properties such as preferred orientations,  pinwheel locations or -counts.  Finally, the use of an explicit probabilistic model facilitates interpretation of parameters and provides the basis for decoding studies.  We demonstrate our model both on simulated data and on intrinsic signaling data from ferret visual cortex.
Convergent Temporal-Difference Learning with Arbitrary Smooth Function Approximation
Authors: Shalabh Bhatnagar, Doina Precup, David Silver, Richard S. Sutton, Hamid R. Maei, Csaba Szepesvári
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Q-Learning

We introduce the first  temporal-difference  learning algorithms that converge  with smooth value function approximators, such as neural networks. Conventional temporal-difference (TD) methods, such as TD($\lambda$), Q-learning and Sarsa have been used successfully with function approximation in many applications.  However, it is well known that off-policy sampling, as well as nonlinear function approximation, can cause these algorithms to become unstable (i.e., the parameters of the approximator may diverge). Sutton et al (2009a,b) solved the problem of off-policy learning with linear TD algorithms by introducing a new objective function, related to the Bellman-error, and algorithms that perform stochastic gradient-descent on this function. In this paper, we generalize their work to nonlinear function approximation. We present a Bellman error objective function and two gradient-descent TD algorithms that optimize it. We prove the  asymptotic almost-sure convergence  of both algorithms for any finite Markov decision process and any smooth value function approximator, under usual stochastic approximation conditions. The computational complexity per iteration scales linearly with the number of parameters of the approximator. The algorithms are incremental and are guaranteed to converge to locally optimal solutions.
Compressed Least-Squares Regression
Authors: Odalric Maillard, Rémi Munos
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: regression

We consider the problem of learning, from K input data, a regression function in a function space of high dimension N using projections onto a random subspace of lower dimension M. From any linear approximation algorithm using empirical risk minimization (possibly penalized), we provide bounds on the excess risk of the estimate computed in the projected subspace (compressed domain) in terms of the excess risk of the estimate built in the high-dimensional space (initial domain). We apply the analysis to the ordinary Least-Squares regression and show that by choosing M=O(\sqrt{K}), the estimation error (for the quadratic loss) of the ``Compressed Least Squares Regression is O(1/\sqrt{K}) up to logarithmic factors. We also discuss the numerical complexity of several algorithms (both in initial and compressed domains) as a function of N, K, and M.
Beyond Categories: The Visual Memex Model for Reasoning About Object Relationships
Authors: Tomasz Malisiewicz, Alyosha Efros
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Object, Scene Understanding

The use of context is critical for scene understanding in computer vision, where the recognition of an object is driven by both local appearance and the objects relationship to other elements of the scene (context).  Most current approaches rely on modeling the relationships between object categories as a source of context. In this paper we seek to move beyond categories to provide a richer appearance-based model of context.  We present an exemplar-based model of objects and their relationships, the Visual Memex, that encodes both local appearance and 2D spatial context between object instances. We evaluate our model on Torralbas proposed Context Challenge against a baseline category-based system. Our experiments suggest that moving beyond categories for context modeling appears to be quite beneficial, and may be the critical missing ingredient in scene understanding systems.
Efficient Large-Scale Distributed Training of Conditional Maximum Entropy Models
Authors: Ryan Mcdonald, Mehryar Mohri, Nathan Silberman, Dan Walker, Gideon S. Mann
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Training conditional maximum entropy models on massive data requires significant time and computational resources. In this paper, we investigate three common distributed training strategies: distributed gradient, majority voting ensembles, and parameter mixtures. We analyze the worst-case runtime and resource costs of each and present a theoretical foundation for the convergence of parameters under parameter mixtures, the most efficient strategy. We present large-scale experiments comparing the different strategies and demonstrate that parameter mixtures over independent models use fewer resources and achieve comparable loss as compared to standard approaches.
Toward Provably Correct Feature Selection in Arbitrary Domains
Authors: Dimitris Margaritis
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: feature selection

In this paper we address the problem of provably correct feature selection in arbitrary domains.  An optimal solution to the problem is a Markov boundary, which is a minimal set of features that make the probability distribution of a target variable conditionally invariant to the state of all other features in the domain.  While numerous algorithms for this problem have been proposed, their theoretical correctness and practical behavior under arbitrary probability distributions is unclear.  We address this by introducing the Markov Boundary Theorem that precisely characterizes the properties of an ideal Markov boundary, and use it to develop algorithms that learn a more general boundary that can capture complex interactions that only appear when the values of multiple features are considered together.  We introduce two algorithms: an exact, provably correct one as well a more practical randomized anytime version, and show that they perform well on artificial as well as benchmark and real-world data sets.  Throughout the paper we make minimal assumptions that consist of only a general set of axioms that hold for every probability distribution, which gives these algorithms universal applicability.
FACTORIE: Probabilistic Programming via Imperatively Defined Factor Graphs
Authors: Andrew Mccallum, Karl Schultz, Sameer Singh
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Probabilistic Programming

Discriminatively trained undirected graphical models have had wide empirical success, and there has been increasing interest in toolkits that ease their application to complex relational data.  The power in relational models is in their repeated structure and tied parameters; at issue is how to define these structures in a powerful and flexible way. Rather than using a declarative language, such as SQL or first-order logic, we advocate using an imperative language to express various aspects of model structure, inference, and learning.  By combining the traditional, declarative, statistical semantics of factor graphs with imperative definitions of their construction and operation, we allow the user to mix declarative and procedural domain knowledge, and also gain significant efficiencies.  We have implemented such imperatively defined factor graphs in a system we call Factorie, a software library for an object-oriented, strongly-typed, functional language.  In experimental comparisons to Markov Logic Networks on joint segmentation and coreference, we find our approach to be 3-15 times faster while reducing error by 20-25%-achieving a new state of the art.
Matrix Completion from Power-Law Distributed Samples
Authors: Raghu Meka, Prateek Jain, Inderjit S. Dhillon
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Low-Rank Matrix Completion, Matrix Completion

The low-rank matrix completion problem is a fundamental problem with many important applications. Recently, Candes & Recht, Keshavan et al. and Candes & Tao obtained the first non-trivial theoretical results for the problem assuming that the observed entries are sampled uniformly at random. Unfortunately, most real-world datasets do not satisfy this assumption, but instead exhibit power-law distributed samples. In this paper, we propose a graph theoretic approach to matrix completion that solves the problem for more realistic sampling models. Our method is easier to analyze than previous methods with the analysis reducing to computing the threshold for complete cascades in random graphs, a problem of independent interest. By analyzing the graph theoretic problem, we show that our method achieves exact recovery when the observed entries are sampled from the Chung-Lu-Vu model, which can generate power-law distributed graphs. We also hypothesize that our algorithm solves the matrix completion problem from an optimal number of entries for the popular preferential attachment model and provide strong empirical evidence for the claim. Furthermore, our method is easier to implement and is substantially faster than existing methods. We demonstrate the effectiveness of our method on examples when the low-rank matrix is sampled according to the prevalent random graph models for complex networks and also on the Netflix challenge dataset.
Extending Phase Mechanism to Differential Motion Opponency for Motion Pop-out
Authors: Yicong Meng, Bertram E. Shi
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We extend the concept of phase tuning, a ubiquitous mechanism in sensory neurons including motion and disparity detection neurons, to the motion contrast detection.  We demonstrate that motion contrast can be detected by phase shifts between motion neuronal responses in different spatial regions. By constructing the differential motion opponency in response to motions in two different spatial regions, varying motion contrasts can be detected, where similar motion is detected by zero phase shifts and differences in motion by non-zero phase shifts.  The model can exhibit either enhancement or suppression of responses by either different or similar motion in the surrounding.  A primary advantage of the model is that the responses are selective to relative motion instead of absolute motion, which could model neurons found in neurophysiological experiments responsible for motion pop-out detection.
Nonparametric Latent Feature Models for Link Prediction
Authors: Kurt Miller, Michael. I. Jordan, Thomas L. Griffiths
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Link Prediction, Prediction

As the availability and importance of relational data -- such as the friendships summarized on a social networking website -- increases, it becomes increasingly important to have good models for such data.  The kinds of latent structure that have been considered for use in predicting links in such networks have been relatively limited. In particular, the machine learning community has focused on latent class models, adapting nonparametric Bayesian methods to jointly infer how many latent classes there are while learning which entities belong to each class. We pursue a similar approach with a richer kind of latent variable -- latent features -- using a nonparametric Bayesian technique to simultaneously infer the number of features at the same time we learn which entities have each feature. The greater expressiveness of this approach allows us to improve link prediction on three datasets.
Accelerating Bayesian Structural Inference for Non-Decomposable Gaussian Graphical Models
Authors: Baback Moghaddam, Emtiyaz Khan, Kevin P. Murphy, Benjamin M. Marlin
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

In this paper we make several contributions towards accelerating approximate Bayesian structural inference for non-decomposable GGMs. Our first contribution is to show how to efficiently compute a BIC or Laplace approximation to the marginal likelihood of non-decomposable graphs using convex methods for precision matrix estimation. This optimization technique can be used as a fast scoring function inside standard Stochastic Local Search (SLS) for generating posterior samples. Our second contribution is a novel framework for efficiently generating large sets of high-quality graph topologies without performing local search. This graph proposal method, which we call Neighborhood Fusion" (NF), samples candidate Markov blankets at each node using sparse regression techniques. Our final contribution is a hybrid method combining the complementary strengths of NF and SLS. Experimental results in structural recovery and prediction tasks demonstrate that NF and hybrid NF/SLS out-perform state-of-the-art local search methods, on both synthetic and real-world datasets, when realistic computational limits are imposed."
Large Scale Nonparametric Bayesian Inference: Data Parallelisation in the Indian Buffet Process
Authors: Finale Doshi-Velez, Shakir Mohamed, Zoubin Ghahramani, David A. Knowles
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Bayesian Inference

Nonparametric Bayesian models provide a framework for flexible probabilistic modelling of complex datasets. Unfortunately, Bayesian inference methods often require high-dimensional averages and can be slow to compute, especially with the potentially unbounded representations associated with nonparametric models. We address the challenge of scaling nonparametric Bayesian inference to the increasingly large datasets found in real-world applications, focusing on the case of parallelising inference in the Indian Buffet Process (IBP).  Our approach divides a large data set between multiple processors.  The processors use message passing to compute likelihoods in an asynchronous, distributed fashion and to propagate statistics about the global Bayesian posterior.  This novel MCMC sampler is the first parallel inference scheme for IBP-based models, scaling to datasets orders of magnitude larger than had previously been possible.
Which graphical models are difficult to learn?
Authors: Andrea Montanari, Jose A. Pereira
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We consider the problem of learning the structure of Ising models (pairwise binary Markov random fields) from i.i.d. samples. While several methods have been proposed to accomplish this task, their relative merits and limitations remain somewhat obscure. By analyzing a number of concrete examples, we show that low-complexity  algorithms systematically fail when the Markov random field  develops long-range correlations. More precisely, this phenomenon  appears to be related to the Ising model phase transition  (although it does not coincide with it).
A Generalized Natural Actor-Critic Algorithm
Authors: Tetsuro Morimura, Eiji Uchibe, Junichiro Yoshimoto, Kenji Doya
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Reinforcement Learning, Reinforcement Learning (RL)

Policy gradient Reinforcement Learning (RL) algorithms have received much attention in seeking stochastic policies that maximize the average rewards.  In addition, extensions based on the concept of the Natural Gradient (NG) show promising learning efficiency because these regard metrics for the task. Though there are two candidate metrics, Kakades Fisher Information Matrix (FIM) and Morimuras FIM, all RL algorithms with NG have followed the Kakades approach. In this paper, we describe a generalized Natural Gradient (gNG) by linearly interpolating the two FIMs and propose an efficient implementation for the gNG learning based on a theory of the estimating function, generalized Natural Actor-Critic (gNAC). The gNAC algorithm involves a near optimal auxiliary function to reduce the variance of the gNG estimates. Interestingly, the gNAC can be regarded as a natural extension of the current state-of-the-art NAC algorithm, as long as the interpolating parameter is appropriately selected. Numerical experiments showed that the proposed gNAC algorithm can estimate gNG efficiently and outperformed the NAC algorithm.
Predicting the Optimal Spacing of Study: A Multiscale Context Model of Memory
Authors: Harold Pashler, Nicholas Cepeda, Robert V. Lindsey, Ed Vul, Michael C. Mozer
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

When individuals learn facts (e.g., foreign language vocabulary) over multiple study sessions, the temporal spacing of study has a significant impact on memory retention.  Behavioral experiments have shown a nonmonotonic relationship between spacing and retention:  short or long intervals between study sessions yield lower cued-recall accuracy than intermediate intervals.  Appropriate spacing of study can double retention on educationally relevant time scales.  We introduce a Multiscale Context Model (MCM) that is able to predict the influence of a particular study schedule on retention for specific material.  MCMs prediction is based on empirical data characterizing forgetting of the material following a single study session.  MCM is a synthesis of two existing memory models (Staddon, Chelaru, & Higa, 2002; Raaijmakers, 2003).  On the surface, these  models are unrelated and incompatible, but we show they share a core feature  that allows them to be integrated.  MCM can determine study schedules that  maximize the durability of learning, and has implications for education  and training.  MCM can be cast either as a neural network with inputs that  fluctuate over time, or as a cascade of leaky integrators.  MCM is  intriguingly similar to a Bayesian multiscale model of memory (Kording, Tenenbaum, Shadmehr, 2007), yet MCM is better able to account for human  declarative memory.
Statistical Analysis of Semi-Supervised Learning: The Limit of Infinite Unlabelled Data
Authors: Boaz Nadler, Nathan Srebro, Xueyuan Zhou
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We study the behavior of the popular Laplacian Regularization method for Semi-Supervised Learning at the regime of a fixed number of labeled points but a large number of unlabeled points.  We show that in $\R^d$, $d \geq 2$, the method is actually not well-posed, and as the number of unlabeled points increases the solution degenerates to a noninformative function.  We also contrast the method with the Laplacian Eigenvector method, and discuss the ``smoothness assumptions associated with this alternate method.