mtybilly/Instruct2DS huggingface dataset:
Context-Sensitive Decision Forests for Object Detection
Authors: Samuel R. Bulò, Antonio Criminisi, Pushmeet Kohli, Marcello Pelillo, Horst Bischof Peter Kontschieder
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: In this paper we introduce Context-Sensitive Decision Forests - A new perspective to exploit contextual information in the popular decision forest framework for the object detection problem. They are tree-structured classifiers with the ability to access intermediate prediction (here: classification and regression) information during training and inference time. This intermediate prediction is available to each sample, which allows us to develop context-based decision criteria, used for refining the prediction process. In addition, we introduce a novel split criterion which in combination with a priority based way of constructing the trees, allows more accurate regression mode selection and hence improves the current context information. In our experiments, we demonstrate improved results for the task of pedestrian detection on the challenging TUD data set when compared to state-of-the-art methods.
Approximating Concavely Parameterized Optimization Problems
Authors: Jens Mueller, Soeren Laue, Sascha Swiercy Joachim Giesen
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We consider an abstract class of optimization problems that are parameterized concavely in a single parameter, and show that the solution path along the parameter can always be approximated with accuracy $\varepsilon >0$ by a set of size $O(1/\sqrt{\varepsilon})$. A lower bound of size $\Omega (1/\sqrt{\varepsilon})$ shows that the upper bound is tight up to a constant factor. We also devise an algorithm that calls a step-size oracle and computes an approximate path of size $O(1/\sqrt{\varepsilon})$. Finally, we provide an implementation of the oracle for soft-margin support vector machines, and a parameterized semi-definite program for matrix completion.
Kernel Latent SVM for Visual Recognition
Authors: Yang Wang, Arash Vahdat, Greg Mori Weilong Yang
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Latent SVMs (LSVMs) are a class of powerful tools that have been successfully applied to many applications in computer vision. However, a limitation of LSVMs is that they rely on linear models. For many computer vision tasks, linear models are suboptimal and nonlinear models learned with kernels typically perform much better. Therefore it is desirable to develop the kernel version of LSVM. In this paper, we propose kernel latent SVM (KLSVM) -- a new learning framework that combines latent SVMs and kernel methods. We develop an iterative training algorithm to learn the model parameters. We demonstrate the effectiveness of KLSVM using three different applications in visual recognition. Our KLSVM formulation is very general and can be applied to solve a wide range of applications in computer vision and machine learning.
A Linear Time Active Learning Algorithm for Link Classification
Authors: Claudio Gentile, Fabio Vitale, Giovanni Zappella Nicolò Cesa-bianchi
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We present very efficient active learning algorithms for link classification in signed networks. Our algorithms are motivated by a stochastic model in which edge labels are obtained through perturbations of a initial sign assignment consistent with a two-clustering of the nodes. We provide a theoretical analysis within this model, showing that we can achieve an optimal (to whithin a constant factor) number of mistakes on any graph $G = (V,E)$ such that $|E|$ is at least order of $|V|^{3/2}$ by querying at most order of $|V|^{3/2}$ edge labels. More generally, we show an algorithm that achieves optimality to within a factor of order $k$ by querying at most order of $|V| + (|V|/k)^{3/2}$ edge labels. The running time of this algorithm is at most of order $|E| + |V|\log|V|$.
A P300 BCI for the Masses: Prior Information Enables Instant Unsupervised Spelling
Authors: Hannes Verschore, David Verstraeten, Benjamin Schrauwen Pieter-jan Kindermans
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: The usability of Brain Computer Interfaces (BCI) based on the P300 speller is severely hindered by the need for long training times and many repetitions of the same stimulus. In this contribution we introduce a set of unsupervised hierarchical probabilistic models that tackle both problems simultaneously by incorporating prior knowledge from two sources: information from other training subjects (through transfer learning) and information about the words being spelled (through language models). We show, that due to this prior knowledge, the performance of the unsupervised models parallels and in some cases even surpasses that of supervised models, while eliminating the tedious training session.
Dynamic Pruning of Factor Graphs for Maximum Marginal Prediction
Authors: Christoph H. Lampert
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We study the problem of maximum marginal prediction (MMP) in probabilistic graphical models, a task that occurs, for example, as the Bayes optimal decision rule under a Hamming loss. MMP is typically performed as a two-stage procedure: one estimates each variable's marginal probability and then forms a prediction from the states of maximal probability. In this work we propose a simple yet effective technique for accelerating MMP when inference is sampling-based: instead of the above two-stage procedure we directly estimate the posterior probability of each decision variable. This allows us to identify the point of time when we are sufficiently certain about any individual decision. Whenever this is the case, we dynamically prune the variable we are confident about from the underlying factor graph. Consequently, at any time only samples of variable whose decision is still uncertain need to be created. Experiments in two prototypical scenarios, multi-label classification and image inpainting, shows that adaptive sampling can drastically accelerate MMP without sacrificing prediction accuracy.
Locally Uniform Comparison Image Descriptor
Authors: Eric Christiansen, David Kriegman, Serge J. Belongie Andrew Ziegler
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Keypoint matching between pairs of images using popular descriptors like SIFT or a faster variant called SURF is at the heart of many computer vision algorithms including recognition, mosaicing, and structure from motion. For real-time mobile applications, very fast but less accurate descriptors like BRIEF and related methods use a random sampling of pairwise comparisons of pixel intensities in an image patch. Here, we introduce Locally Uniform Comparison Image Descriptor (LUCID), a simple description method based on permutation distances between the ordering of intensities of RGB values between two patches. LUCID is computable in linear time with respect to patch size and does not require floating point computation. An analysis reveals an underlying issue that limits the potential of BRIEF and related approaches compared to LUCID. Experiments demonstrate that LUCID is faster than BRIEF, and its accuracy is directly comparable to SURF while being more than an order of magnitude faster.
Priors for Diversity in Generative Latent Variable Models
Authors: Ryan P. Adams James T. Kwok
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Probabilistic latent variable models are one of the cornerstones of machine learning.  They offer a convenient and coherent way to specify prior distributions over unobserved structure in data, so that these unknown properties can be inferred via posterior inference.  Such models are useful for exploratory analysis and visualization, for building density models of data, and for   providing features that can be used for later discriminative tasks. A significant limitation of these models, however, is that draws from the prior are often highly redundant due to i.i.d. assumptions   on internal parameters.  For example, there is no preference in the prior of a mixture model to make components non-overlapping, or in topic model to ensure that co-ocurring words only appear in a small number of topics.  In this work, we revisit these independence assumptions for probabilistic latent variable models, replacing the   underlying i.i.d.\ prior with a determinantal point process (DPP). The DPP allows us to specify a preference for diversity in our latent variables using a positive definite kernel function.  Using a kernel between probability distributions, we are able to define a DPP on probability measures.  We show how to perform MAP inference   with DPP priors in latent Dirichlet allocation and in mixture models, leading to better intuition for the latent variable representation and quantitatively improved unsupervised feature extraction, without compromising the generative aspects of the model.
Mixing Properties of Conditional Markov Chains with Unbounded Feature Functions
Authors: Bei Chen Mathieu Sinn
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Conditional Markov Chains (also known as Linear-Chain Conditional Random Fields  in the literature) are a versatile class of discriminative models for the distribution of a sequence of hidden states conditional on a sequence of observable variables. Large-sample properties of Conditional Markov Chains have been first studied by Sinn and Poupart [1]. The paper extends this work in two directions: first, mixing properties of models with unbounded feature functions are being established; second, necessary conditions for model identifiability and the uniqueness of maximum likelihood estimates are being given.
ImageNet Classification with Deep Convolutional Neural Networks
Authors: Ilya Sutskever, Geoffrey E. Hinton Alex Krizhevsky
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We trained a large, deep convolutional neural network to classify the 1.3 million high-resolution images in the LSVRC-2010 ImageNet training set into the 1000 different classes. On the test data, we achieved top-1 and top-5 error rates of 39.7\% and 18.9\% which is considerably better than the previous state-of-the-art results. The neural network, which has 60 million parameters and 500,000 neurons, consists of five convolutional layers, some of which are followed by max-pooling layers, and two globally connected layers with a final 1000-way softmax. To make training faster, we used non-saturating neurons and a very efficient GPU implementation of convolutional nets. To reduce overfitting in the globally connected layers we employed a new regularization method that proved to be very effective.
Stochastic Gradient Descent with Only One Projection
Authors: Tianbao Yang, Rong Jin, Shenghuo Zhu, Jinfeng Yi Mehrdad Mahdavi
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Although many variants of stochastic gradient descent have been proposed for large-scale convex optimization, most of them require projecting the solution at {\it each} iteration to ensure that the obtained solution stays within the feasible domain. For complex domains (e.g., positive semidefinite cone), the projection step can be computationally expensive, making stochastic gradient descent unattractive for large-scale optimization problems. We address this limitation by developing a novel stochastic gradient descent algorithm that does not need intermediate projections. Instead, only one projection at the last iteration is needed to obtain a feasible solution in the given domain. Our theoretical analysis shows that with a high probability, the proposed algorithms achieve an $O(1/\sqrt{T})$ convergence rate for general convex optimization, and an $O(\ln T/T)$  rate for  strongly convex optimization under mild conditions about the domain and the objective function.
Learning Probability Measures with respect to Optimal Transport Metrics
Authors: Lorenzo Rosasco Guillermo Canas
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We study the problem of estimating, in the sense of optimal transport metrics, a measure which is assumed supported on a manifold embedded in a Hilbert space. By establishing a precise connection between optimal transport metrics, optimal quantization, and learning theory, we derive new probabilistic bounds for the performance of a classic algorithm in unsupervised learning (k-means), when used to produce a probability measure derived from the data. In the course of the analysis, we arrive at new lower bounds, as well as probabilistic bounds on the convergence rate of the empirical law of large numbers, which, unlike existing bounds, are applicable to a wide class of measures.
Effective Split-Merge Monte Carlo Methods for Nonparametric Models of Sequential Data
Authors: Emily B. Fox, Erik B. Sudderth Michael C Hughes
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Applications of Bayesian nonparametric methods require learning and inference algorithms which efficiently explore models of unbounded complexity. We develop new Markov chain Monte Carlo methods for the beta process hidden Markov model (BP-HMM), enabling discovery of shared activity patterns in large video and motion capture databases. By introducing split-merge moves based on sequential allocation, we allow large global changes in the shared feature structure. We also develop data-driven reversible jump moves which more reliably discover rare or unique behaviors. Our proposals apply to any choice of conjugate likelihood for observed data, and we show success with multinomial, Gaussian, and autoregressive emission models. Together, these innovations allow tractable analysis of hundreds of time series, where previous inference required clever initialization and at least ten thousand burn-in iterations for just six sequences.
Scaling MPE Inference for Constrained Continuous Markov Random Fields with Consensus Optimization
Authors: Matthias Broecheler, Lise Getoor, Dianne O'leary Stephen Bach
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Probabilistic graphical models are powerful tools for analyzing constrained, continuous domains. However, finding most-probable explanations (MPEs) in these models can be computationally expensive. In this paper, we improve the scalability of MPE inference in a class of graphical models with piecewise-linear and piecewise-quadratic dependencies and linear constraints over continuous domains. We derive algorithms based on a consensus-optimization framework and demonstrate their superior performance over state of the art. We show empirically that in a large-scale voter-preference modeling problem our algorithms scale linearly in the number of dependencies and constraints.
A systematic approach to extracting semantic information from functional MRI data
Authors: Matthew Botvinick Francisco Pereira
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: This paper introduces a novel classification method for functional magnetic resonance imaging datasets with tens of classes. The method is designed to make predictions using information from as many brain locations as possible, instead of resorting to feature selection, and does this by decomposing the pattern of brain activation into differently informative sub-regions. We provide results over a complex semantic processing dataset that show that the method is competitive with state-of-the-art feature selection and also suggest how the method may be used to perform group or exploratory analyses of complex class structure.
Sketch-Based Linear Value Function Approximation
Authors: Joel Veness, Michael Bowling Marc Bellemare
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Hashing is a common method to reduce large, potentially infinite feature vectors to a fixed-size table. In reinforcement learning, hashing is often used in conjunction with tile coding to represent states in continuous spaces. Hashing is also a promising approach to value function approximation in large discrete domains such as Go and Hearts, where feature vectors can be constructed by exhaustively combining a set of atomic features. Unfortunately, the typical use of hashing in value function approximation results in biased value estimates due to the possibility of collisions. Recent work in data stream summaries has led to the development of the tug-of-war sketch, an unbiased estimator for approximating inner products. Our work investigates the application of this new data structure to linear value function approximation. Although in the reinforcement learning setting the use of the tug-of-war sketch leads to biased value estimates, we show that this bias can be orders of magnitude less than that of standard hashing. We provide empirical results on two RL benchmark domains and fifty-five Atari 2600 games to highlight the superior learning performance of tug-of-war hashing.
Unsupervised Structure Discovery for Semantic Analysis of Audio
Authors: Bhiksha Raj Sourish Chaudhuri
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Approaches to audio classification and retrieval tasks largely rely on detection-based discriminative models. We submit that such models make a simplistic assumption in mapping acoustics directly to semantics, whereas the actual process is likely more complex. We present a generative model that maps acoustics in a hierarchical manner to increasingly higher-level semantics. Our model has 2 layers with the first being generic sound units with no clear semantic associations, while the second layer attempts to find patterns over the generic sound units. We evaluate our model on a large-scale retrieval task from TRECVID 2011, and report significant improvements over standard baselines.
The Time-Marginalized Coalescent Prior for Hierarchical Clustering
Authors: Max Welling Levi Boyles
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We introduce a new prior for use in Nonparametric Bayesian Hierarchical Clustering. The prior is constructed by marginalizing out the time information of Kingman’s coalescent, providing a prior over tree structures which we call the Time-Marginalized Coalescent (TMC). This allows for models which factorize the tree structure and times, providing two benefits: more flexible priors may be constructed and more efficient Gibbs type inference can be used. We demonstrate this on an example model for density estimation and show the TMC achieves competitive experimental results.
Nonparametric Max-Margin Matrix Factorization for Collaborative Prediction
Authors: Jun Zhu, Bo Zhang Minjie Xu
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We present a probabilistic formulation of max-margin matrix factorization and build accordingly a nonparametric Bayesian model which automatically resolves the unknown number of latent factors. Our work demonstrates a successful example that integrates Bayesian nonparametrics and max-margin learning, which are conventionally two separate paradigms and enjoy complementary advantages. We develop an efcient variational algorithm for posterior inference, and our extensive empirical studies on large-scale MovieLens and EachMovie data sets appear to justify the aforementioned dual advantages.
Exponential Concentration for Mutual Information Estimation with Application to Forests
Authors: Larry Wasserman, John D. Lafferty Han Liu
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We prove a new exponential concentration inequality for a plug-in estimator of the Shannon mutual information. Previous results on mutual information estimation only bounded expected error. The advantage of having the exponential inequality is that, combined with the union bound, we can guarantee accurate estimators of the mutual information for many pairs of random variables simultaneously. As an application, we show how to use such a result to optimally estimate the density function and graph of a distribution which is Markov to a forest graph.
Slice Normalized Dynamic Markov Logic Networks
Authors: Henry Kautz, Daniel Stefankovic Tivadar Papai
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Markov logic is a widely used tool in statistical relational learning, which uses a weighted first-order logic knowledge base to specify a Markov random field (MRF) or a conditional random field (CRF). In many applications, a Markov logic network (MLN) is trained in one domain, but used in a different one. This paper focuses on dynamic Markov logic networks, where the domain of time points typically varies between training and testing. It has been previously pointed out that the marginal probabilities of truth assignments to ground atoms can change if one extends or reduces the domains of predicates in an MLN. We show that in addition to this problem, the standard way of unrolling a Markov logic theory into a MRF may result in time-inhomogeneity of the underlying Markov chain. Furthermore, even if these representational problems are not significant for a given domain, we show that the more practical problem of generating samples in a sequential conditional random field for the next slice relying on the samples from the previous slice has high computational cost in the general case, due to the need to estimate a normalization factor for each sample. We propose a new discriminative model, slice normalized dynamic Markov logic networks (SN-DMLN), that suffers from none of these issues. It supports efficient online inference, and can directly model influences between variables within a time slice that do not have a causal direction, in contrast with fully directed models (e.g., DBNs). Experimental results show an improvement in accuracy over previous approaches to online inference in dynamic Markov logic networks.
Continuous Relaxations for Discrete Hamiltonian Monte Carlo
Authors: Zoubin Ghahramani, Amos J. Storkey, Charles A. Sutton Yichuan Zhang
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Continuous relaxations play an important role in discrete optimization, but have not seen much use in approximate probabilistic inference. Here we show that a general form of the Gaussian Integral Trick makes it possible to transform a wide class of discrete variable undirected models into fully continuous systems. The continuous representation allows the use of gradient-based Hamiltonian Monte Carlo for inference,  results in new ways of estimating normalization constants (partition functions), and in general opens up a number of new avenues for inference in difficult discrete systems. We demonstrate some of these continuous relaxation inference algorithms on a number of illustrative problems.
Learning with Target Prior
Authors: Siwei Lyu, Gerwin Schalk, Qiang Ji Zuoguan Wang
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: In the conventional approaches for supervised parametric learning, relations between data and target variables are provided through training sets consisting of pairs of corresponded data and target variables. In this work, we describe a new learning scheme for parametric learning, in which the target variables $\y$ can be modeled with a prior model $p(\y)$ and the relations between data and target variables are estimated through $p(\y)$ and a set of uncorresponded data $\x$ in training. We term this method as learning with target priors (LTP). Specifically, LTP learning seeks parameter $\t$ that maximizes the log likelihood of $f_\t(\x)$ on a uncorresponded training set with regards to $p(\y)$. Compared to the conventional (semi)supervised learning approach, LTP can make efficient use of prior knowledge of the target variables in the form of probabilistic distributions, and thus removes/reduces the reliance on training data in learning. Compared to the Bayesian approach, the learned parametric regressor in LTP can be more efficiently implemented and deployed in tasks where running efficiency is critical, such as on-line BCI signal decoding. We demonstrate the effectiveness of the proposed approach on parametric regression tasks for BCI signal decoding and pose estimation from video.
Generalization Bounds for Domain Adaptation
Authors: Lei Zhang, Jieping Ye Chao Zhang
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: In this paper, we provide a new framework to study the generalization bound of the learning process for domain adaptation. Without loss of generality, we consider two kinds of representative domain adaptation settings: one is domain adaptation with multiple sources and the other is domain adaptation combining source and target data. In particular, we introduce two quantities that capture the inherent characteristics of domains. For either kind of domain adaptation, based on the two quantities, we then develop the specific Hoeffding-type deviation inequality and symmetrization inequality to achieve the corresponding generalization bound based on the uniform entropy number. By using the resultant generalization bound, we analyze the asymptotic convergence and the rate of convergence of the learning process for such kind of domain adaptation. Meanwhile, we discuss the factors that affect the asymptotic behavior of the learning process. The numerical experiments support our results.
Multiplicative Forests for Continuous-Time Processes
Authors: Sriraam Natarajan, David Page Jeremy Weiss
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Learning temporal dependencies between variables over continuous time is an important and challenging task. Continuous-time Bayesian networks effectively model such processes but are limited by the number of conditional intensity matrices, which grows exponentially in the number of parents per variable. We develop a partition-based representation using regression trees and forests whose parameter spaces grow linearly in the number of node splits. Using a multiplicative assumption we show how to update the forest likelihood in closed form, producing efficient model updates. Our results show multiplicative forests can be learned from few temporal trajectories with large gains in performance and scalability.
Variational Inference for Crowdsourcing
Authors: Jian Peng, Alex Ihler Qiang Liu
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Crowdsourcing has become a popular paradigm for labeling large datasets. However, it has given rise to the computational task of aggregating the crowdsourced labels provided by a collection of unreliable annotators. We approach this problem by transforming it into a standard inference problem in graphical models, and applying approximate variational methods, including belief propagation (BP) and mean field (MF). We show that our BP algorithm generalizes both majority voting and a recent algorithm by Karger et al, while our MF method is closely related to a commonly used EM algorithm. In both cases, we find that the performance of the algorithms critically depends on the choice of a prior distribution on the workers' reliability; by choosing the prior properly, both BP and MF (and EM) perform surprisingly well on both simulated and real-world datasets, competitive with state-of-the-art algorithms based on more complicated modeling assumptions.
Why MCA? Nonlinear sparse coding with spike-and-slab prior for neurally plausible image encoding
Authors: Joerg Bornschein, Abdul-saboor Sheikh, Jörg Lücke, Jacquelyn A. Shelton Philip Sterne
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Modelling natural images with sparse coding (SC) has faced two main challenges: ﬂexibly representing varying pixel intensities and realistically representing low- level image components. This paper proposes a novel multiple-cause generative model of low-level image statistics that generalizes the standard SC model in two crucial points: (1) it uses a spike-and-slab prior distribution for a more realistic representation of component absence/intensity, and (2) the model uses the highly nonlinear combination rule of maximal causes analysis (MCA) instead of a lin- ear combination. The major challenge is parameter optimization because a model with either (1) or (2) results in strongly multimodal posteriors. We show for the ﬁrst time that a model combining both improvements can be trained efﬁciently while retaining the rich structure of the posteriors. We design an exact piece- wise Gibbs sampling method and combine this with a variational method based on preselection of latent dimensions. This combined training scheme tackles both analytical and computational intractability and enables application of the model to a large number of observed and hidden dimensions. Applying the model to image patches we study the optimal encoding of images by simple cells in V1 and compare the model’s predictions with in vivo neural recordings. In contrast to standard SC, we ﬁnd that the optimal prior favors asymmetric and bimodal ac- tivity of simple cells. Testing our model for consistency we ﬁnd that the average posterior is approximately equal to the prior. Furthermore, we ﬁnd that the model predicts a high percentage of globular receptive ﬁelds alongside Gabor-like ﬁelds. Similarly high percentages are observed in vivo. Our results thus argue in favor of improvements of the standard sparse coding model for simple cells by using ﬂexible priors and nonlinear combinations.
Tractable Objectives for Robust Policy Optimization
Authors: Michael Bowling Katherine Chen
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Robust policy optimization acknowledges that risk-aversion plays a vital role in real-world decision-making. When faced with uncertainty about the effects of actions, the policy that maximizes expected utility over the unknown parameters of the system may also carry with it a risk of intolerably poor performance.  One might prefer to accept lower utility in expectation in order to avoid, or reduce the likelihood of, unacceptable levels of utility under harmful parameter realizations.   In this paper, we take a Bayesian approach to parameter uncertainty, but unlike other methods avoid making any distributional assumptions about the form of this uncertainty.  Instead we focus on identifying optimization objectives for which solutions can be efficiently approximated.  We introduce percentile measures: a very general class of objectives for robust policy optimization, which encompasses most existing approaches, including ones known to be intractable. We then introduce a broad subclass of this family for which robust policies can be approximated efficiently. Finally, we frame these objectives in the context of a two-player, zero-sum, extensive-form game and employ a no-regret algorithm to approximate an optimal policy, with computation only polynomial in the number of states and actions of the MDP.
Multiple Choice Learning: Learning to Produce Multiple Structured Outputs
Authors: Dhruv Batra, Pushmeet Kohli Abner Guzmán-rivera
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: The paper addresses the problem of generating multiple hypotheses for prediction tasks that involve interaction with users or successive components in a cascade. Given a set of multiple hypotheses, such components/users have the ability to automatically rank the results and thus retrieve the best one. The standard approach for handling this scenario is to learn a single model and then produce M-best Maximum a Posteriori (MAP) hypotheses from this model. In contrast, we formulate this multiple {\em choice} learning task as a multiple-output structured-output prediction problem with a loss function that captures the natural setup of the problem. We present a max-margin formulation  that minimizes an upper-bound on this loss-function. Experimental results on the problems of image co-segmentation and protein side-chain prediction show that our method outperforms conventional approaches used for this  scenario and leads to substantial improvements in prediction accuracy.
Robustness and risk-sensitivity in Markov decision processes
Authors: Takayuki Osogami
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We uncover relations between robust MDPs and risk-sensitive MDPs.  The objective of a robust MDP is to minimize a function, such as the expectation of cumulative cost, for the worst case when the parameters have uncertainties.  The objective of a risk-sensitive MDP is to minimize a risk measure of the cumulative cost when the parameters are known.  We show that a risk-sensitive MDP of minimizing the expected exponential utility is equivalent to a robust MDP of minimizing the worst-case expectation with a penalty for the deviation of the uncertain parameters from their nominal values, which is measured with the Kullback-Leibler divergence.  We also show that a risk-sensitive MDP of minimizing an iterated risk measure that is composed of certain coherent risk measures is equivalent to a robust MDP of minimizing the worst-case expectation when the possible deviations of uncertain parameters from their nominal values are characterized with a concave function.
Communication/Computation Tradeoffs in Consensus-Based Distributed Optimization
Authors: Sean Lawlor, Michael G. Rabbat Konstantinos Tsianos
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We study the scalability of consensus-based distributed optimization algorithms by considering two questions: How many processors should we use for a given problem, and how often should they communicate when communication is not free? Central to our analysis is a problem-specific value $r$ which quantifies the communication/computation tradeoff. We show that organizing the communication among nodes as a $k$-regular expander graph~\cite{kRegExpanders} yields speedups, while when all pairs of nodes communicate (as in a complete graph), there is an optimal number of processors that depends on $r$. Surprisingly, a speedup can be obtained, in terms of the time to reach a fixed level of accuracy, by communicating less and less frequently as the computation progresses. Experiments on a real cluster solving metric learning and non-smooth convex minimization tasks demonstrate strong agreement between theory and practice.
A Polylog Pivot Steps Simplex Algorithm for Classification
Authors: Zohar Karnin Elad Hazan
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We present a simplex algorithm for linear programming in a linear classification formulation. The paramount complexity parameter in linear classification problems is called the margin. We prove that for margin values of practical interest our simplex variant performs a polylogarithmic number of pivot steps in the worst case, and its overall running time is near linear. This is in contrast to general linear programming, for which no sub-polynomial pivot rule is known.
Fiedler Random Fields: A Large-Scale Spectral Approach to Statistical Network Modeling
Authors: Mikaela Keller, Marc Tommasi Antonino Freno
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Statistical models for networks have been typically committed to strong prior assumptions concerning the form of the modeled distributions. Moreover, the vast majority of currently available models are explicitly designed for capturing some specific graph properties (such as power-law degree distributions), which makes them unsuitable for application to domains where the behavior of the target quantities is not known a priori. The key contribution of this paper is twofold. First, we introduce the Fiedler delta statistic, based on the Laplacian spectrum of graphs, which allows to dispense with any parametric assumption concerning the modeled network properties. Second, we use the defined statistic to develop the Fiedler random field model, which allows for efficient estimation of edge distributions over large-scale random networks. After analyzing the dependence structure involved in Fiedler random fields, we estimate them over several real-world networks, showing that they achieve a much higher modeling accuracy than other well-known statistical approaches.
Majorization for CRFs and Latent Likelihoods
Authors: Anna Choromanska Tony Jebara
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: The partition function plays a key role in probabilistic modeling including conditional random fields, graphical models, and maximum likelihood estimation. To optimize partition functions, this article introduces a quadratic variational upper bound. This inequality facilitates majorization methods: optimization of complicated functions through the iterative solution of simpler sub-problems. Such bounds remain efficient to compute even when the partition function involves a graphical model (with small tree-width) or in latent likelihood settings. For large-scale problems, low-rank versions of the bound are provided and outperform LBFGS as well as first-order methods. Several learning applications are shown and reduce to fast and convergent update rules. Experimental results show advantages over state-of-the-art optimization methods.
Feature-aware Label Space Dimension Reduction for Multi-label Classification
Authors: Hsuan-tien Lin Yao-nan Chen
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Label space dimension reduction (LSDR) is an efficient and effective paradigm for multi-label classification with many classes. Existing approaches to LSDR, such as compressive sensing and principal label space transformation, exploit only the label part of the dataset, but not the feature part. In this paper, we propose a novel approach to LSDR that considers both the label and the feature parts. The approach, called conditional principal label space transformation, is based on minimizing an upper bound of the popular Hamming loss. The minimization step of the approach can be carried out efficiently by a simple use of singular value decomposition. In addition, the approach can be extended to a kernelized version that allows the use of sophisticated feature combinations to assist LSDR. The experimental results verify that the proposed approach is more effective than existing ones to LSDR across many real-world datasets.
Semantic Kernel Forests from Multiple Taxonomies
Authors: Kristen Grauman, Fei Sha Sung Ju Hwang
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: When learning features for complex visual recognition problems, labeled image exemplars alone can be insufficient.  While an \emph{object taxonomy} specifying the categories' semantic relationships could bolster the learning process, not all relationships are relevant to a given visual classification task, nor does a single taxonomy capture all ties that \emph{are} relevant.  In light of these issues, we propose a discriminative feature learning approach that leverages \emph{multiple} hierarchical taxonomies representing different semantic views of the object categories (e.g., for animal classes, one taxonomy could reflect their phylogenic ties, while another could reflect their habitats).  For each taxonomy, we first learn a tree of semantic kernels, where each node has a Mahalanobis kernel optimized to distinguish between the classes in its children nodes.  Then, using the resulting \emph{semantic kernel forest}, we learn class-specific kernel combinations to select only those relationships relevant to recognize each object class.  To learn the weights, we introduce a novel hierarchical regularization term that further exploits the taxonomies' structure.  We demonstrate our method on challenging object recognition datasets, and show that interleaving multiple taxonomic views yields significant accuracy improvements.
Spectral learning of linear dynamics from generalised-linear observations with application to neural population data
Authors: Jakob H. Macke, Maneesh Sahani Lars Buesing
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Latent linear dynamical systems with generalised-linear observation models arise in a variety of applications, for example when modelling the spiking activity of populations of neurons.  Here, we show how  spectral learning methods for linear systems with Gaussian observations   (usually called subspace identification in this context) can be extended to estimate the parameters of dynamical system models observed through non-Gaussian noise models. We use this approach to obtain estimates of parameters for a dynamical model of neural population data, where the observed spike-counts are Poisson-distributed with log-rates determined by the latent dynamical process, possibly driven by external inputs. We show that the extended system identification algorithm is consistent and accurately recovers the correct parameters on large simulated data sets with much smaller computational cost than approximate expectation-maximisation (EM) due to the non-iterative nature of subspace identification. Even on smaller data sets, it provides an effective initialization for EM, leading to more robust performance and faster convergence. These benefits are shown to extend to real neural data.
Assessing Blinding in Clinical Trials
Authors: Ognjen Arandjelovic
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: The interaction between the patient's expected outcome of an intervention and the inherent effects of that intervention can have extraordinary effects. Thus in clinical trials an effort is made to conceal the nature of the administered intervention from the participants in the trial i.e. to blind it. Yet, in practice perfect blinding is impossible to ensure or even verify. The current standard is follow up the trial with an auxiliary questionnaire, which allows trial participants to express their belief concerning the assigned intervention and which is used to compute a measure of the extent of blinding in the trial. If the estimated extent of blinding exceeds a threshold the trial is deemed sufficiently blinded; otherwise, the trial is deemed to have failed. In this paper we make several important contributions. Firstly, we identify a series of fundamental problems of the aforesaid practice and discuss them in context of the most commonly used blinding measures. Secondly, motivated by the highlighted problems, we formulate a novel method for handling imperfectly blinded trials. We too adopt a post-trial feedback questionnaire but interpret the collected data using an original approach, fundamentally different from those previously proposed. Unlike previous approaches, ours is void of any ad hoc free parameters, is robust to small changes in auxiliary data and is not predicated on any strong assumptions used to interpret participants' feedback.
Scalable Inference of Overlapping Communities
Authors: Sean Gerrish, Michael Freedman, David M. Blei, David M. Mimno Prem Gopalan
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We develop a scalable algorithm for posterior inference of overlapping communities in large networks.  Our algorithm is based on stochastic variational inference in the mixed-membership stochastic blockmodel. It naturally interleaves subsampling the network with estimating its community structure.  We apply our algorithm on ten large, real-world networks with up to 60,000 nodes. It converges several orders of magnitude faster than the state-of-the-art algorithm for MMSB, finds hundreds of communities in large real-world networks, and detects the true communities in 280 benchmark networks with equal or better accuracy compared to other scalable algorithms.
Learning Networks of Heterogeneous Influence
Authors: Le Song, Ming Yuan, Alex J. Smola Nan Du
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Information, disease, and influence diffuse over networks of entities in both natural systems and human society. Analyzing these transmission networks plays an important role in understanding the diffusion processes and predicting events in the future. However, the underlying transmission networks are often hidden and incomplete, and we observe only the time stamps when cascades of events happen. In this paper, we attempt to address the challenging problem of uncovering the hidden network only from the cascades.  The structure discovery problem is complicated by the fact that the influence among different entities in a network are heterogeneous, which can not be described by a simple parametric model. Therefore, we propose a kernel-based method which can capture a diverse range of different types of influence without any prior assumption. In both synthetic and real cascade data, we show that our model can better recover the underlying diffusion network and drastically improve the estimation of the influence functions between networked entities.