mtybilly/Instruct2DS huggingface dataset:
An Online Algorithm for Large Scale Image Similarity Learning
Authors: Uri Shalit, Varun Sharma, Samy Bengio Gal Chechik
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Learning a measure of similarity between pairs of objects is a fundamental problem in machine learning. It stands in the core of classification methods like kernel machines, and is particularly useful for applications like searching for images that are similar to a given image or finding videos that are relevant to a given video. In these tasks, users look for objects that are not only visually similar but also semantically related to a given object. Unfortunately, current approaches for learning similarity may not scale to large datasets with high dimensionality, especially when imposing metric constraints on the learned similarity. We describe OASIS, a method for learning pairwise similarity that is fast and scales linearly with the number of objects and the number of non-zero features. Scalability is achieved through online learning of a bilinear model over sparse representations using a large margin criterion and an efficient hinge loss cost. OASIS is accurate at a wide range of scales: on a standard benchmark with thousands of images, it is more precise than state-of-the-art methods, and faster by orders of magnitude. On 2 million images collected from the web, OASIS can be trained within 3 days on a single CPU. The non-metric similarities learned by OASIS can be transformed into metric similarities, achieving higher precisions than similarities that are learned as metrics in the first place. This suggests an approach for learning a metric from data that is larger by an order of magnitude than was handled before.
Functional network reorganization in motor cortex can be explained by reward-modulated Hebbian learning
Authors: Andrew Schwartz, Wolfgang Maass, Robert A. Legenstein Steven Chase
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The control of neuroprosthetic devices from the activity of motor cortex neurons benefits from learning effects where the function of these neurons is adapted to the control task. It was recently shown that tuning properties of neurons in monkey motor cortex are adapted selectively in order to compensate for an erroneous interpretation of their activity. In particular, it was shown that the tuning curves of those neurons whose preferred directions had been misinterpreted changed more than those of other neurons. In this article, we show that the experimentally observed self-tuning properties of the system can be explained on the basis of a simple learning rule. This learning rule utilizes neuronal noise for exploration and performs Hebbian weight updates that are modulated by a global reward signal. In contrast to most previously proposed reward-modulated Hebbian learning rules, this rule does not require extraneous knowledge about what is noise and what is signal. The learning rule is able to optimize the performance of the model system within biologically realistic periods of time and under high noise levels. When the neuronal noise is fitted to experimental data, the model produces learning effects similar to those found in monkey experiments.
The Infinite Partially Observable Markov Decision Process
Authors: Finale Doshi-velez
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The Partially Observable Markov Decision Process (POMDP) framework has proven useful in planning domains that require balancing actions that increase an agents knowledge and actions that increase an agents reward.  Unfortunately, most POMDPs are complex structures with a large number of parameters.  In many realworld problems, both the structure and the parameters are difficult to specify from domain knowledge alone.  Recent work in Bayesian reinforcement learning has made headway in learning POMDP models; however, this work has largely focused on learning the parameters of the POMDP model.  We define an infinite POMDP (iPOMDP) model that does not require knowledge of the size of the state space; instead, it assumes that the number of visited states will grow as the agent explores its world and explicitly models only visited states.  We demonstrate the iPOMDP utility on several standard problems.
Accelerated Gradient Methods for Stochastic Optimization and Online Learning
Authors: Weike Pan, James T. Kwok Chonghai Hu
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Regularized risk minimization often involves non-smooth optimization, either because of the loss function (e.g., hinge loss) or the regularizer (e.g., $\ell_1$-regularizer). Gradient descent methods, though highly scalable and easy to implement, are known to converge slowly on these problems. In this paper, we develop novel accelerated gradient methods for stochastic optimization while still preserving their computational simplicity and scalability. The proposed algorithm, called SAGE (Stochastic Accelerated GradiEnt), exhibits fast convergence rates on stochastic optimization with both convex and strongly convex objectives. Experimental results show that SAGE is faster than recent (sub)gradient methods including FOLOS, SMIDAS and SCD. Moreover, SAGE can also be extended for online learning, resulting in a simple but powerful algorithm.
Robust Value Function Approximation Using Bilinear Programming
Authors: Shlomo Zilberstein Marek Petrik
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Existing value function approximation methods have been successfully used in many applications, but they often lack useful a priori error bounds. We propose approximate bilinear programming, a new formulation of value function approximation that provides strong a priori guarantees. In particular, it provably finds an approximate value function that minimizes the Bellman residual. Solving a bilinear program optimally is NP hard, but this is unavoidable because the Bellman-residual minimization itself is NP hard. We, therefore, employ and analyze a common approximate algorithm for bilinear programs. The analysis shows that this algorithm offers a convergent generalization of approximate policy iteration. Finally, we demonstrate that the proposed approach can consistently minimize the Bellman residual on a simple benchmark problem.
Parallel Inference for Latent Dirichlet Allocation on Graphics Processing Units
Authors: Ningyi Xu, Yuan Qi Feng Yan
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The recent emergence of Graphics Processing Units (GPUs) as general-purpose parallel computing devices provides us with new opportunities to develop scalable learning methods for massive data. In this work, we consider the problem of parallelizing two inference methods on GPUs for latent Dirichlet Allocation (LDA) models, collapsed Gibbs sampling (CGS) and collapsed variational Bayesian (CVB). To address limited memory constraints on GPUs, we propose a novel data partitioning scheme that effectively reduces the memory cost. Furthermore, the partitioning scheme balances the computational cost on each multiprocessor and enables us to easily avoid memory access conflicts. We also use data streaming to handle extremely large datasets. Extensive experiments showed that our parallel inference methods consistently produced LDA models with the same predictive power as sequential training methods did but with 26x speedup for CGS and 196x speedup for CVB on a GPU with 30 multiprocessors; actually the speedup is almost linearly scalable with the number of multiprocessors available. The proposed partitioning scheme and data streaming can be easily ported to many other models in machine learning.
Local Rules for Global MAP: When Do They Work ?
Authors: Pushmeet Kohli, Devavrat Shah Kyomin Jung
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We consider the question of computing Maximum A Posteriori (MAP) assignment in an arbitrary pair-wise Markov Random Field (MRF). We present a randomized iterative algorithm based on simple local updates. The algorithm, starting with an arbitrary initial assignment, updates it in each iteration by first, picking a random node, then selecting an (appropriately chosen) random local neighborhood and optimizing over this local neighborhood. Somewhat surprisingly, we show that this algorithm finds a near optimal assignment within $2n\ln n$ iterations on average and with high probability for {\em any} $n$ node pair-wise MRF with {\em geometry} (i.e. MRF graph with polynomial growth) with the approximation error depending on (in a reasonable manner) the geometric growth rate of the graph and the average radius of the local neighborhood -- this allows for a graceful tradeoff between the complexity of the algorithm and the approximation error. Through extensive simulations, we show that our algorithm finds extremely good approximate solutions for various kinds of MRFs with geometry.
Bayesian estimation of orientation preference maps
Authors: Leonard White, Matthias Kaschube, Matthias Bethge, Jakob H. Macke Sebastian Gerwinn
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: 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.
A Bayesian Analysis of Dynamics in Free Recall
Authors: Samuel Gershman, Per Sederberg, Kenneth Norman, Adler J. Perotte, David M. Blei Richard Socher
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We develop a probabilistic model of human memory performance in free recall experiments. In these experiments, a subject first studies a list of words and then tries to recall them.  To model these data, we draw on both previous psychological research and statistical topic models of text documents.  We assume that memories are formed by assimilating the semantic meaning of studied words (represented as a distribution over topics) into a slowly changing latent context (represented in the same space).  During recall, this context is reinstated and used as a cue for retrieving studied words.  By conceptualizing memory retrieval as a dynamic latent variable model, we are able to use Bayesian inference to represent uncertainty and reason about the cognitive processes underlying memory.  We present a particle filter algorithm for performing approximate posterior inference, and evaluate our model on the prediction of recalled words in experimental data. By specifying the model hierarchically, we are also able to capture inter-subject variability.
Structural inference affects depth perception in the context of potential occlusion
Authors: Konrad Koerding Ian Stevenson
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: In many domains, humans appear to combine perceptual cues in a near-optimal, probabilistic fashion: two noisy pieces of information tend to be combined linearly with weights proportional to the precision of each cue. Here we present a case where structural information plays an important role. The presence of a background cue gives rise to the possibility of occlusion, and places a soft constraint on the location of a target – in effect propelling it forward. We present an ideal observer model of depth estimation for this situation where structural or ordinal information is important and then fit the model to human data from a stereo-matching task. To test whether subjects are truly using ordinal cues in a probabilistic manner we then vary the uncertainty of the task. We find that the model accurately predicts shifts in subject’s behavior. Our results indicate that the nervous system estimates depth ordering in a probabilistic fashion and estimates the structure of the visual scene during depth perception.
Indian Buffet Processes with Power-law Behavior
Authors: Dilan Gorur Yee W. Teh
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The Indian buffet process (IBP) is an exchangeable distribution over binary matrices used in Bayesian nonparametric featural models.  In this paper we propose a three-parameter generalization of the IBP exhibiting power-law behavior.  We achieve this by generalizing the beta process (the de Finetti measure of the IBP) to the \emph{stable-beta process} and deriving the IBP corresponding to it.  We find interesting relationships between the stable-beta process and the Pitman-Yor process (another stochastic process used in Bayesian nonparametric models with interesting power-law properties).  We show that our power-law IBP is a good model for word occurrences in documents with improved performance over the normal IBP.
Boosting with Spatial Regularization
Authors: Uri Hasson, Peter J. Ramadge, Zhen J. Xiang Yongxin Xi
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: By adding a spatial regularization kernel to a standard loss function formulation of the boosting problem, we develop a framework for spatially informed boosting.  From this regularized loss framework we derive an efficient boosting algorithm that uses additional weights/priors on the base classifiers.  We prove that the proposed algorithm exhibits a ``grouping effect, which encourages the selection of all spatially local, discriminative base classifiers.  The algorithms primary advantage is in applications where the trained classifier is used to identify the spatial pattern of discriminative information, e.g. the voxel selection problem in fMRI.  We demonstrate the algorithms performance on various data sets.
Time-rescaling methods for the estimation and assessment of non-Poisson neural encoding models
Authors: Jonathan W. Pillow
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Recent work on the statistical modeling of neural responses has focused on modulated renewal processes in which the spike rate is a function of the stimulus and recent spiking history. Typically, these models incorporate spike-history dependencies via either: (A) a conditionally-Poisson process with rate dependent on a linear projection of the spike train history (e.g., generalized linear model); or (B) a modulated non-Poisson renewal process (e.g., inhomogeneous gamma process). Here we show that the two approaches can be combined, resulting in a {\it conditional renewal} (CR) model for neural spike trains. This model captures both real and rescaled-time effects, and can be fit by maximum likelihood using a simple application of the time-rescaling theorem [1]. We show that for any modulated renewal process model, the log-likelihood is concave in the linear filter parameters only under certain restrictive conditions on the renewal density (ruling out many popular choices, e.g. gamma with $\kappa \neq1$), suggesting that real-time history effects are easier to estimate than non-Poisson renewal properties. Moreover, we show that goodness-of-fit tests based on the time-rescaling theorem [1] quantify relative-time effects, but do not reliably assess accuracy in spike prediction or stimulus-response modeling. We illustrate the CR model with applications to both real and simulated neural data.
Semi-supervised Regression using Hessian energy with an application to semi-supervised dimensionality reduction
Authors: Florian Steinke, Matthias Hein Kwang I. Kim
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Semi-supervised regression based on the graph Laplacian suffers from the fact that the solution is biased towards a constant and the lack of extrapolating power. Outgoing from these observations we propose to use the second-order Hessian energy for semi-supervised regression which overcomes both of these problems, in particular, if the data lies on or close to a low-dimensional submanifold in the feature space, the Hessian energy prefers functions which vary ``linearly with respect to the natural parameters in the data. This property makes it also particularly suited for the task of semi-supervised dimensionality reduction where the goal is to find the natural parameters in the data based on a few labeled points. The experimental result suggest that our method is superior to semi-supervised regression using Laplacian regularization and standard supervised methods and is particularly suited for semi-supervised dimensionality reduction.
Localizing Bugs in Program Executions with Graphical Models
Authors: Valentin Dallmeier, Andreas Zeller, Tobias Scheffer Laura Dietz
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We devise a graphical model that supports the process of debugging software by guiding developers to code that is likely to contain defects. The model is trained using execution traces of passing test runs; it reflects the distribution over transitional patterns of code positions. Given a failing test case, the model determines the least likely transitional pattern in the execution trace. The model is designed such that Bayesian inference has a closed-form solution. We evaluate the  Bernoulli graph model on data of the software projects AspectJ and Rhino.
Human Rademacher Complexity
Authors: Bryan R. Gibson, Timothy T. Rogers Xiaojin Zhu
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We propose to use Rademacher complexity, originally developed in computational learning theory, as a measure of human learning capacity.  Rademacher complexity measures a learners ability to fit random data, and can be used to bound the learners true error based on the observed training sample error.  We first review the definition of Rademacher complexity and its generalization bound.  We then describe a learning the noise" procedure to experimentally measure human Rademacher complexities.  The results from empirical studies showed that: (i) human Rademacher complexity can be successfully measured, (ii) the complexity depends on the domain and training sample size in intuitive ways, (iii) human learning respects the generalization bounds, (iv) the bounds can be useful in predicting the danger of overfitting in human learning.  Finally, we discuss the potential applications of human Rademacher complexity in cognitive science."
Beyond Convexity: Online Submodular Minimization
Authors: Satyen Kale Elad Hazan
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We consider an online decision problem over a discrete space in which the loss function is submodular. We give algorithms which are computationally efficient and are Hannan-consistent in both the full information and bandit settings.
Learning from Multiple Partially Observed Views - an Application to Multilingual Text Categorization
Authors: Nicolas Usunier, Cyril Goutte Massih R. Amini
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We address the problem of learning classifiers when observations have multiple views, some of which may not be observed for all examples.  We assume the existence of view generating functions which may complete the missing views in an approximate way.  This situation corresponds for example to learning text classifiers from multilingual collections where documents are not available in all languages.  In that case, Machine Translation (MT) systems may be used to translate each document in the missing languages.  We derive a generalization error bound for classifiers learned on examples with multiple artificially created views. Our result uncovers a trade-off between the size of the training set, the number of views, and the quality of the view generating functions. As a consequence, we identify situations where it is more interesting to use multiple views for learning instead of classical single view learning.  An extension of this framework is a natural way to leverage unlabeled multi-view data in semi-supervised learning.  Experimental results on a subset of the Reuters RCV1/RCV2 collections support our findings by showing that additional views obtained from MT may significantly improve the classification performance in the cases identified by our trade-off.
Measuring model complexity with the prior predictive
Authors: Wolf Vanpaemel
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: In the last few decades, model complexity has received a lot of press. While many methods have been proposed that jointly measure a model’s descriptive adequacy and its complexity, few measures exist that measure complexity in itself. Moreover, existing measures ignore the parameter prior, which is an inherent part of the model and affects the complexity. This paper presents a stand alone measure for model complexity, that takes the number of parameters, the functional form, the range of the parameters and the parameter prior into account. This Prior Predictive Complexity (PPC) is an intuitive and easy to compute measure. It starts from the observation that model complexity is the property of the model that enables it to fit a wide range of outcomes. The PPC then measures how wide this range exactly is.
Nonparametric Bayesian Texture Learning and Synthesis
Authors: Yuanahao Chen, Bill Freeman, Antonio Torralba Long Zhu
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We present a nonparametric Bayesian method for texture learning and synthesis.  A texture image is represented by a 2D-Hidden Markov Model (2D-HMM) where the hidden states correspond to the cluster labeling of textons and the transition matrix encodes their spatial layout (the compatibility between adjacent textons). 2D-HMM is coupled with the Hierarchical Dirichlet process (HDP) which allows the number of textons and the complexity of transition matrix grow as the input texture becomes irregular. The HDP makes use of Dirichlet process prior which favors regular textures by penalizing the model complexity. This framework (HDP-2D-HMM) learns the texton vocabulary and their spatial layout jointly and automatically.  The HDP-2D-HMM results in a compact  representation of textures which allows fast texture synthesis with comparable rendering quality over the state-of-the-art image-based rendering methods. We also show that HDP-2D-HMM can be applied to perform image segmentation and synthesis.
A Bayesian Model for Simultaneous Image Clustering, Annotation and Object Segmentation
Authors: Lu Ren, Lawrence Carin, David B. Dunson Lan Du
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: A non-parametric Bayesian model is proposed for processing multiple images. The analysis employs image features and, when present, the words associated with accompanying annotations. The model clusters the images into classes, and each image is segmented into a set of objects, also allowing the opportunity to assign a word to each object (localized labeling). Each object is assumed to be represented as a heterogeneous mix of components, with this realized via mixture models linking image features to object types. The number of image classes, number of object types, and the characteristics of the object-feature mixture models are inferred non-parametrically. To constitute spatially contiguous objects, a new logistic stick-breaking process is developed. Inference is performed efficiently via variational Bayesian analysis, with example results presented on two image databases.
Whose Vote Should Count More: Optimal Integration of Labels from Labelers of Unknown Expertise
Authors: Ting-fan Wu, Jacob Bergsma, Javier R. Movellan, Paul L. Ruvolo Jacob Whitehill
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Modern machine learning-based approaches to computer vision require very large databases of labeled images. Some contemporary vision systems already require on the order of millions of images for training (e.g., Omron face detector). While the collection of these large databases is becoming a bottleneck, new Internet-based services that allow labelers from around the world to be easily hired and managed provide a promising solution.  However, using these services to label large databases brings with it new theoretical and practical challenges: (1) The labelers may have wide ranging levels of expertise which are unknown a priori, and in some cases may be adversarial; (2) images may vary in their level of difficulty; and (3) multiple labels for the same image must be combined to provide an estimate of the actual label of the image. Probabilistic approaches provide a principled way to approach these problems. In this paper we present a probabilistic model and use it to simultaneously infer the label of each image, the expertise of each labeler, and the difficulty of each image. On both simulated and real data, we demonstrate that the model outperforms the commonly used ``Majority Vote heuristic for inferring image labels, and is robust to both adversarial and noisy labelers.
Reading Tea Leaves: How Humans Interpret Topic Models
Authors: Sean Gerrish, Chong Wang, Jordan L. Boyd-graber, David M. Blei Jonathan Chang
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Probabilistic topic models are a popular tool for the unsupervised analysis of text, providing both a predictive model of future text and a latent topic representation of the corpus. Practitioners typically assume that the latent space is semantically meaningful. It is used to check models, summarize the corpus, and guide exploration of its contents. However, whether the latent space is interpretable is in need of quantitative evaluation. In this paper, we present new quantitative methods for measuring semantic meaning in inferred topics. We back these measures with large-scale user studies, showing that they capture aspects of the model that are undetected by previous measures of model quality based on held-out likelihood. Surprisingly, topic models which perform better on held-out likelihood may infer less semantically meaningful topics.
Segmenting Scenes by Matching Image Composites
Authors: Alyosha Efros, Josef Sivic, Bill Freeman, Andrew Zisserman Bryan Russell
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: In this paper, we investigate how similar images sharing the same global description can help with unsupervised scene segmentation in an image.  In contrast to recent work in semantic alignment of scenes, we allow an input image to be explained by partial matches of similar scenes.  This allows for a better explanation of the input scenes.  We perform MRF-based segmentation that optimizes over matches, while respecting boundary information.  The recovered segments are then used to re-query a large database of images to retrieve better matches for the target region. We show improved performance in detecting occluding boundaries over previous methods on data gathered from the LabelMe database.
Generalization Errors and Learning Curves for Regression with Multi-task Gaussian Processes
Authors: Kian M. Chai
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We provide some insights into how task correlations in multi-task Gaussian process (GP) regression affect the generalization error and the learning curve.  We analyze the asymmetric two-task case, where a secondary task is to help the learning of a primary task. Within this setting, we give bounds on the generalization error and the learning curve of the primary task. Our approach admits intuitive understandings of the multi-task GP by relating it to single-task GPs. For the case of one-dimensional input-space under optimal sampling with data only for the secondary task, the limitations of multi-task GP can be quantified explicitly.
Breaking Boundaries Between Induction Time and Diagnosis Time Active Information Acquisition
Authors: Eric Horvitz Ashish Kapoor
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: There has been a clear distinction between induction or training time and diagnosis time active information acquisition. While active learning during induction focuses on acquiring data that promises to provide the best classification model, the goal at diagnosis time focuses completely on next features to observe about the test case at hand in order to make better predictions about the case. We introduce a model and inferential methods that breaks this distinction. The methods can be used to extend case libraries under a budget but, more fundamentally, provide a framework for guiding agents to collect data under scarce resources, focused by diagnostic challenges. This extension to active learning leads to a new class of policies for real-time diagnosis, where recommended information-gathering sequences include actions that simultaneously seek new data for the case at hand and for cases in the training set.
An Integer Projected Fixed Point Method for Graph Matching and MAP Inference
Authors: Martial Hebert, Rahul Sukthankar Marius Leordeanu
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: Graph matching and MAP inference are essential problems in computer vision and machine learning. We introduce a novel algorithm that can accommodate both problems and solve them efficiently. Recent graph matching algorithms are based on a general quadratic programming formulation, that takes in consideration both unary and second-order terms reflecting the similarities in local appearance as well as in the pairwise geometric relationships between the matched features. In this case the problem is NP-hard and a lot of effort has been spent in finding efficiently approximate solutions by relaxing the constraints of the original problem. Most algorithms find optimal continuous solutions of the modified problem, ignoring during the optimization the original discrete constraints. The continuous solution is quickly binarized at the end, but very little attention is put into this final discretization step. In this paper we argue that the stage in which a discrete solution is found is crucial for good performance. We propose an efficient algorithm, with climbing and convergence properties, that optimizes in the discrete domain the quadratic score, and it gives excellent results either by itself or by starting from the solution returned by any graph matching algorithm. In practice it outperforms state-or-the art algorithms and it also significantly improves their performance if used in combination. When applied to MAP inference, the algorithm is a parallel extension of Iterated Conditional Modes (ICM) with climbing and convergence properties that make it a compelling alternative to the sequential ICM. In our experiments on MAP inference our algorithm proved its effectiveness by outperforming ICM and Max-Product Belief Propagation.
Efficient Bregman Range Search
Authors: Lawrence Cayton
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: We develop an algorithm for efficient range search when the notion of dissimilarity is given by a Bregman divergence.  The range search task is to return all points in a potentially large database that are within some specified distance of a query.  It arises in many learning algorithms such as locally-weighted regression, kernel density estimation, neighborhood graph-based algorithms, and in tasks like outlier detection and information retrieval.  In metric spaces, efficient range search-like algorithms based on spatial data structures have been deployed on a variety of statistical tasks.  Here we describe the first algorithm for range search for an arbitrary Bregman divergence.   This broad class of dissimilarity measures includes the relative entropy,  Mahalanobis distance, Itakura-Saito divergence, and a variety of matrix divergences.  Metric methods cannot be directly applied since Bregman divergences do not in general satisfy the triangle inequality.  We derive geometric properties of Bregman divergences that yield an efficient algorithm for range search based on a recently proposed space decomposition for Bregman divergences.
Complexity of Decentralized Control: Special Cases
Authors: Shlomo Zilberstein Martin Allen
Published in: Advances in Neural Information Processing Systems 22  (NIPS 2009) (Main Conference Track), 2009

Abstract: The worst-case complexity of general decentralized POMDPs, which are equivalent to partially observable stochastic games (POSGs) is very high, both for the cooperative and competitive cases.  Some reductions in complexity have been achieved by exploiting independence relations in some models.  We show that these results are somewhat limited:  when these independence assumptions are relaxed in very small ways, complexity returns to that of the general case.
Modelling Cellular Perturbations with the Sparse Additive Mechanism Shift Variational Autoencoder
Authors: Theofanis Karaletsos Michael Bereket
Published in: Advances in Neural Information Processing Systems 36  (NeurIPS 2023) (Main Conference Track), 2023

Abstract: Generative models of observations under interventions have been a vibrant topic of interest across machine learning and the sciences in recent years. For example, in drug discovery, there is a need to model the effects of diverse interventions on cells in order to characterize unknown biological mechanisms of action. We propose the Sparse Additive Mechanism Shift Variational Autoencoder, SAMS-VAE, to combine compositionality, disentanglement, and interpretability for perturbation models. SAMS-VAE models the latent state of a perturbed sample as the sum of a local latent variable capturing sample-specific variation and sparse global variables of latent intervention effects. Crucially, SAMS-VAE sparsifies these global latent variables for individual perturbations to identify disentangled, perturbation-specific latent subspaces that are flexibly composable. We evaluate SAMS-VAE both quantitatively and qualitatively on a range of tasks using two popular single cell sequencing datasets.In order to measure perturbation-specific model-properties, we also introduce a framework for evaluation of perturbation models based on average treatment effects with links to posterior predictive checks. SAMS-VAE outperforms comparable models in terms of generalization across in-distribution and out-of-distribution tasks, including a combinatorial reasoning task under resource paucity, and yields interpretable latent structures which correlate strongly to known biological mechanisms. Our results suggest SAMS-VAE is an interesting addition to the modeling toolkit for machine learning-driven scientific discovery.
Cross-Episodic Curriculum for Transformer Agents
Authors: Yunfan Jiang, Jake Grigsby, Linxi Fan, Yuke Zhu Lucy Xiaoyang Shi
Published in: Advances in Neural Information Processing Systems 36  (NeurIPS 2023) (Main Conference Track), 2023

Abstract: We present a new algorithm, Cross-Episodic Curriculum (CEC), to boost the learning efficiency and generalization of Transformer agents. Central to CEC is the placement of cross-episodic experiences into a Transformer’s context, which forms the basis of a curriculum. By sequentially structuring online learning trials and mixed-quality demonstrations, CEC constructs curricula that encapsulate learning progression and proficiency increase across episodes. Such synergy combined with the potent pattern recognition capabilities of Transformer models delivers a powerful cross-episodic attention mechanism. The effectiveness of CEC is demonstrated under two representative scenarios: one involving multi-task reinforcement learning with discrete control, such as in DeepMind Lab, where the curriculum captures the learning progression in both individual and progressively complex settings; and the other involving imitation learning with mixed-quality data for continuous control, as seen in RoboMimic, where the curriculum captures the improvement in demonstrators' expertise. In all instances, policies resulting from CEC exhibit superior performance and strong generalization. Code is open-sourced on the project website https://cec-agent.github.io/ to facilitate research on Transformer agent learning.
PaintSeg: Painting Pixels for Training-free Segmentation
Authors: Chung-Ching Lin, Yinpeng Chen, Zicheng Liu, Jinglu Wang, Rita Singh, Bhiksha Raj Xiang Li
Published in: Advances in Neural Information Processing Systems 36  (NeurIPS 2023) (Main Conference Track), 2023

Abstract: The paper introduces PaintSeg, a new unsupervised method for segmenting objects without any training. We propose an adversarial masked contrastive painting (AMCP) process, which creates a contrast between the original image and a painted image in which a masked area is painted using off-the-shelf generative models. During the painting process, inpainting and outpainting are alternated, with the former masking the foreground and filling in the background, and the latter masking the background while recovering the missing part of the foreground object. Inpainting and outpainting, also referred to as I-step and O-step, allow our method to gradually advance the target segmentation mask toward the ground truth without supervision or training. PaintSeg can be configured to work with a variety of prompts, e.g. coarse masks, boxes, scribbles, and points. Our experimental results demonstrate that PaintSeg outperforms existing approaches in coarse mask-prompt, box-prompt, and point-prompt segmentation tasks, providing a training-free solution suitable for unsupervised segmentation. Code: https://github.com/lxa9867/PaintSeg.
Bootstrapping Vision-Language Learning with Decoupled Language Pre-training
Authors: Chongyang Gao, Soroush Vosoughi Yiren Jian
Published in: Advances in Neural Information Processing Systems 36  (NeurIPS 2023) (Main Conference Track), 2023

Abstract: We present a novel methodology aimed at optimizing the application of frozen large language models (LLMs) for resource-intensive vision-language (VL) pre-training. The current paradigm uses visual features as prompts to guide language models, with a focus on determining the most relevant visual features for corresponding text. Our approach diverges by concentrating on the language component, specifically identifying the optimal prompts to align with visual features. We introduce the Prompt-Transformer (P-Former), a model that predicts these ideal prompts, which is trained exclusively on linguistic data, bypassing the need for image-text pairings. This strategy subtly bifurcates the end-to-end VL training process into an additional, separate stage. Our experiments reveal that our framework significantly enhances the performance of a robust image-to-text baseline (BLIP-2), and effectively narrows the performance gap between models trained with either 4M or 129M image-text pairs. Importantly, our framework is modality-agnostic and flexible in terms of architectural design, as validated by its successful application in a video learning task using varied base modules. The code will be made available at https://github.com/yiren-jian/BLIText.
Path following algorithms for $\ell_2$-regularized $M$-estimation with approximation guarantee
Authors: Renxiong Liu Yunzhang Zhu
Published in: Advances in Neural Information Processing Systems 36  (NeurIPS 2023) (Main Conference Track), 2023

Abstract: Many modern machine learning algorithms are formulated as regularized M-estimation problems, in which a regularization (tuning) parameter controls a trade-off between model fit to the training data and model complexity. To select the ``best'' tuning parameter value that achieves a good trade-off, an approximated solution path needs to be computed. In practice, this is often done through selecting a grid of tuning parameter values and solving the regularized problem at the selected grid points. However, given any desired level of accuracy, it is often not clear how to choose the grid points and also how accurately one should solve the regularized problems at the selected gird points, both of which can greatly impact the overall amount of computation. In the context of  $\ell_2$-regularized $M$-estimation problem, we propose a novel grid point selection scheme and an adaptive stopping criterion for any given optimization algorithm that produces an approximated solution path with approximation error guarantee. Theoretically, we prove that the proposed solution path can approximate the exact solution path to arbitrary level of accuracy, while saving the overall computation as much as possible. Numerical results also corroborate with our theoretical analysis.
PDF: Point Diffusion Implicit Function for Large-scale Scene Neural Representation
Authors: Fukun Yin, Jiayuan Fan, Hui Li, Xin Chen, Wen Liu, Chongshan Lu, Gang Yu, Tao Chen Yuhan Ding
Published in: Advances in Neural Information Processing Systems 36  (NeurIPS 2023) (Main Conference Track), 2023

Abstract: Recent advances in implicit neural representations have achieved impressive results by sampling and fusing individual points along sampling rays in the sampling space. However, due to the explosively growing sampling space, finely representing and synthesizing detailed textures remains a challenge for unbounded large-scale outdoor scenes. To alleviate the dilemma of using individual points to perceive the entire colossal space, we explore learning the surface distribution of the scene to provide structural priors and reduce the samplable space and propose a Point Diffusion implicit Function, PDF, for large-scale scene neural representation. The core of our method is a large-scale point cloud super-resolution diffusion module that enhances the sparse point cloud reconstructed from several training images into a dense point cloud as an explicit prior. Then in the rendering stage, only sampling points with prior points within the sampling radius are retained. That is, the sampling space is reduced from the unbounded space to the scene surface. Meanwhile, to fill in the background of the scene that cannot be provided by point clouds, the region sampling based on Mip-NeRF 360 is employed to model the background representation. Expensive experiments have demonstrated the effectiveness of our method for large-scale scene novel view synthesis, which outperforms relevant state-of-the-art baselines.
Natural Actor-Critic for Robust Reinforcement Learning with Function Approximation
Authors: Tao Liu, Min Cheng, Dileep Kalathil, P. R. Kumar, Chao Tian Ruida Zhou
Published in: Advances in Neural Information Processing Systems 36  (NeurIPS 2023) (Main Conference Track), 2023

Abstract: We study robust reinforcement learning (RL) with the goal of determining a well-performing policy that is robust against model mismatch between the training simulator and the testing environment. Previous policy-based robust RL algorithms mainly focus on the tabular setting under uncertainty sets that facilitate robust policy evaluation, but are no longer tractable when the number of states scales up. To this end, we propose two novel uncertainty set formulations, one based on double sampling and the other on an integral probability metric. Both make large-scale robust RL tractable even when one only has access to a simulator. We propose a robust natural actor-critic (RNAC) approach that incorporates the new uncertainty sets and employs function approximation. We provide finite-time convergence guarantees for the proposed RNAC algorithm to the optimal robust policy within the function approximation error. Finally, we demonstrate the robust performance of the policy learned by our proposed RNAC approach in multiple  MuJoCo environments and a real-world TurtleBot navigation task.
Adaptive Selective Sampling for Online Prediction with Experts
Authors: Fredrik Hellström, Tim van Erven Rui M. Castro
Published in: Advances in Neural Information Processing Systems 36  (NeurIPS 2023) (Main Conference Track), 2023

Abstract: We consider online prediction of a binary sequence with expert advice. For this setting, we devise label-efficient forecasting algorithms, which use a selective sampling scheme that enables collecting much fewer labels than standard procedures. For the general case without a perfect expert, we prove best-of-both-worlds guarantees, demonstrating that the proposed forecasting algorithm always queries sufficiently many labels in the worst case to obtain optimal regret guarantees, while simultaneously querying much fewer labels in more benign settings. Specifically, for a scenario where one expert is strictly better than the others in expectation, we show that the label complexity of the label-efficient forecaster is roughly upper-bounded by the square root of the number of rounds. Finally, we present numerical experiments empirically showing that the normalized regret of the label-efficient forecaster can asymptotically match known minimax rates for pool-based active learning, suggesting it can optimally adapt to benign settings.
Gigastep - One Billion Steps per Second Multi-agent Reinforcement Learning
Authors: lianhao yin, Tim Seyde, Tsun-Hsuan Johnson Wang, Wei Xiao, Ramin Hasani, Joshua Rountree, Daniela Rus Mathias Lechner
Published in: Advances in Neural Information Processing Systems 36  (NeurIPS 2023) (Datasets and Benchmarks Track), 2023

Abstract: Multi-agent reinforcement learning (MARL) research is faced with a trade-off: it either uses complex environments requiring large compute resources, which makes it inaccessible to researchers with limited resources, or relies on simpler dynamics for faster execution, which makes the transferability of the results to more realistic tasks challenging. Motivated by these challenges, we present Gigastep, a fully vectorizable, MARL environment implemented in JAX, capable of executing up to one billion environment steps per second on consumer-grade hardware. Its design allows for comprehensive MARL experimentation, including a complex, high-dimensional space defined by 3D dynamics, stochasticity, and partial observations. Gigastep supports both collaborative and adversarial tasks, continuous and discrete action spaces, and provides RGB image and feature vector observations, allowing the evaluation of a wide range of MARL algorithms. We validate Gigastep's usability through an extensive set of experiments, underscoring its role in widening participation and promoting inclusivity in the MARL research community.