mtybilly/Instruct2DS huggingface dataset:
Nonparanormal Belief Propagation (NPNBP)
Authors: Gal Elidan, Cobi Cario
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: The empirical success of the belief propagation approximate inference algorithm has inspired numerous theoretical and algorithmic advances. Yet, for continuous non-Gaussian domains performing belief propagation remains a challenging task: recent innovations such as nonparametric or kernel belief propagation, while useful, come with a substantial computational cost and offer little theoretical guarantees, even for tree structured models.  In this work we present Nonparanormal BP  for performing efficient inference on distributions parameterized by  a Gaussian copulas network and any univariate marginals. For  tree structured networks, our approach is guaranteed to be exact for  this powerful class of non-Gaussian models. Importantly, the method  is as efficient as standard Gaussian BP, and its convergence properties do not depend on the complexity of the univariate marginals, even when a nonparametric representation is used.
Adaptive Stratified Sampling for Monte-Carlo integration of Differentiable functions
Authors: Alexandra Carpentier, Rémi Munos
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We consider the problem of adaptive stratified sampling for Monte Carlo integration of a differentiable function given a finite number of evaluations to the function. We construct a sampling scheme that samples more often in regions where the function oscillates more, while allocating the samples such that they are well spread on the domain (this notion shares similitude with low discrepancy). We prove that the estimate returned by the algorithm is almost as accurate as the estimate that an optimal oracle strategy (that would know the variations of the function everywhere) would return, and we provide a finite-sample analysis.
Bayesian Nonparametric Modeling of Suicide Attempts
Authors: Francisco Ruiz, Isabel Valera, Carlos Blanco, Fernando Pérez-Cruz
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: The National Epidemiologic Survey on Alcohol and Related Conditions (NESARC) database contains a large amount of information, regarding the way of life, medical conditions, depression, etc., of a representative sample of the U.S. population. In the present paper, we are interested in seeking the hidden causes behind the suicide attempts, for which we propose to model the subjects using a nonparametric latent model based on the Indian Buffet Process (IBP). Due to the nature of the data, we need to adapt the observation model for discrete random variables. We propose a generative model in which the observations are drawn from a multinomial-logit distribution given the IBP matrix. The implementation of an efficient Gibbs sampler is accomplished using the Laplace approximation, which allows us to integrate out the weighting factors of the  multinomial-logit likelihood model. Finally, the experiments over the NESARC database show that our model properly captures some of the hidden causes that model suicide attempts.
Non-linear Metric Learning
Authors: Dor Kedem, Stephen Tyree, Fei Sha, Gert R. Lanckriet, Kilian Q. Weinberger
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: In this paper, we introduce two novel metric learning algorithms, χ2-LMNN and GB-LMNN, which are explicitly designed to be non-linear and  easy-to-use. The two approaches achieve this goal in fundamentally different ways: χ2-LMNN inherits the computational benefits of a linear mapping from linear metric learning, but uses a non-linear χ2-distance to explicitly capture similarities within histogram data sets; GB-LMNN applies gradient-boosting to learn non-linear mappings directly in function space and takes advantage of this approach's robustness, speed, parallelizability and insensitivity towards the single additional hyper-parameter. On various benchmark data sets, we demonstrate these methods not only match the current state-of-the-art in terms of kNN classification error, but in the case of χ2-LMNN, obtain best results in 19 out of 20 learning settings.
Putting Bayes to sleep
Authors: Dmitry Adamskiy, Manfred K. Warmuth, Wouter M. Koolen
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We consider sequential prediction algorithms that are given the predictions from a set of models as inputs. If the nature of the data is changing over time in that different models predict well on different segments of the data, then adaptivity is typically achieved by mixing into the weights in each round a bit of the initial prior (kind of like a weak restart). However, what if the favored models in each segment are from a small subset, i.e. the data is likely to be predicted well by models that predicted well before? Curiously, fitting such ''sparse composite models'' is achieved by mixing in a bit of all the past posteriors. This self-referential updating method is rather peculiar, but it is efficient and gives superior performance on many natural data sets. Also it is important because it introduces a long-term memory: any model that has done well in the past can be recovered quickly. While Bayesian interpretations can be found for mixing in a bit of the initial prior, no Bayesian interpretation is known for mixing in past posteriors.  We build atop the ''specialist'' framework from the online learning literature to give the Mixing Past Posteriors update a proper Bayesian foundation. We apply our method to a well-studied multitask learning problem and obtain a new intriguing efficient update that achieves a significantly better bound.
Sparse Approximate Manifolds for Differential Geometric MCMC
Authors: Ben Calderhead, Mátyás A. Sustik
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: One of the enduring challenges in Markov chain Monte Carlo methodology is the development of proposal mechanisms to make moves distant from the current point, that are accepted with high probability and at low computational cost. The recent introduction of locally adaptive MCMC methods based on the natural underlying Riemannian geometry of such models goes some way to alleviating these problems for certain classes of models for which the metric tensor is analytically tractable, however computational efficiency is not assured due to the necessity of potentially high-dimensional matrix operations at each iteration. In this paper we firstly investigate a sampling-based approach for approximating the metric tensor and suggest a valid MCMC algorithm that extends the applicability of Riemannian Manifold MCMC methods to statistical models that do not admit an analytically computable metric tensor. Secondly, we show how the approximation scheme we consider naturally motivates the use of l1 regularisation to improve estimates and obtain a sparse approximate inverse of the metric, which enables stable and sparse approximations of the local geometry to be made. We demonstrate the application of this algorithm for inferring the parameters of a realistic system of ordinary differential equations using a biologically motivated robust student-t error model, for which the expected Fisher Information is analytically intractable.
Bayesian active learning with localized priors for fast receptive field characterization
Authors: Mijung Park, Jonathan W. Pillow
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Active learning can substantially improve the yield of neurophysiology experiments by adaptively selecting stimuli to probe a neuron's receptive field (RF) in real time. Bayesian active learning methods maintain a posterior distribution over the RF, and select stimuli to maximally reduce posterior entropy on each time step.  However, existing methods tend to rely on simple Gaussian priors, and do not exploit uncertainty at the level of hyperparameters when determining an optimal stimulus.  This uncertainty can play a substantial role in RF characterization, particularly when RFs are smooth, sparse, or local in space and time.  In this paper, we describe a novel framework for active learning under hierarchical, conditionally Gaussian priors.  Our algorithm uses sequential Markov Chain Monte Carlo sampling (''particle filtering'' with MCMC) over hyperparameters to construct a mixture-of-Gaussians representation of the RF posterior, and selects optimal stimuli using an approximate infomax criterion.  The core elements of this algorithm are parallelizable, making it computationally efficient for real-time experiments.  We apply our algorithm to simulated and real neural data, and show that it can provide highly accurate receptive field estimates from very limited data, even with a small number of hyperparameter samples.
Deep Neural Networks Segment Neuronal Membranes in Electron Microscopy Images
Authors: Dan Ciresan, Alessandro Giusti, Luca M. Gambardella, Jürgen Schmidhuber
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We address a central problem of neuroanatomy, namely, the automatic segmentation of neuronal structures  depicted in stacks of electron microscopy (EM) images. This is necessary to efficiently map 3D brain structure and connectivity. To segment {\em biological} neuron membranes, we use a special type of deep {\em artificial} neural network as a pixel classifier. The label of each pixel (membrane or non-membrane) is predicted from raw pixel values in a square window centered on it. The input layer maps each window pixel to a neuron. It is followed by a succession of convolutional and max-pooling layers which preserve 2D information and extract features with increasing levels of abstraction. The output layer produces a calibrated probability for each class. The classifier is trained by plain gradient descent on a $512 \times 512 \times 30$ stack with known ground truth, and tested on a stack of the same  size (ground truth unknown to the authors) by the organizers of the ISBI 2012 EM Segmentation Challenge.  Even without problem-specific post-processing, our approach outperforms competing techniques by a large margin in all three considered metrics, i.e. \emph{rand error}, \emph{warping error} and \emph{pixel error}.  For pixel error, our approach is the only one outperforming a second human observer.
Learning from the Wisdom of Crowds by Minimax Entropy
Authors: Dengyong Zhou, Sumit Basu, Yi Mao, John C. Platt
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: An important way to make large training sets is to gather noisy labels from crowds of nonexperts. We propose a minimax entropy principle to improve the quality of these labels. Our method assumes that labels are generated by a probability distribution over workers, items, and labels. By maximizing the entropy of this distribution, the method naturally infers item confusability and worker expertise. We infer the ground truth by minimizing the entropy of this distribution, which we show minimizes the Kullback-Leibler (KL) divergence between the probability distribution and the unknown truth. We show that a simple coordinate descent scheme can optimize minimax entropy. Empirically, our results are substantially better than previously published methods for the same problem.
Parametric Local Metric Learning for Nearest Neighbor Classification
Authors: Jun Wang, Alexandros Kalousis, Adam Woznica
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We study the problem of learning local metrics for nearest neighbor classification. Most previous works on local metric learning learn a number of local unrelated metrics. While this ''independence'' approach delivers an increased flexibility its downside is the considerable risk of overfitting. We present a new parametric local metric learning method in which we learn a smooth metric matrix function over the data manifold. Using an approximation error bound of the metric matrix function we learn local metrics as linear combinations of basis metrics defined on anchor points over different regions of the instance space.  We constrain the metric matrix function by imposing on the linear combinations manifold regularization which makes the learned metric matrix function vary smoothly along the geodesics of the data manifold. Our metric learning method has excellent performance both in terms of predictive power and scalability. We experimented with several large-scale classification problems, tens of thousands of instances, and compared it with several state of the art metric learning methods, both global and local, as well as to SVM with automatic kernel selection, all of which it outperforms in a significant manner.
The topographic unsupervised learning of natural sounds in the auditory cortex
Authors: Hiroki Terashima, Masato Okada
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: The computational modelling of the primary auditory cortex (A1) has been less fruitful than that of the primary visual cortex (V1) due to the less organized properties of A1. Greater disorder has recently been demonstrated for the tonotopy of A1 that has traditionally been considered to be as ordered as the retinotopy of V1. This disorder appears to be incongruous, given the uniformity of the neocortex; however, we hypothesized that both A1 and V1 would adopt an efficient coding strategy and that the disorder in A1 reflects natural sound statistics. To provide a computational model of the tonotopic disorder in A1, we used a model that was originally proposed for the smooth V1 map. In contrast to natural images, natural sounds exhibit distant correlations, which were learned and reflected in the disordered map. The auditory model predicted harmonic relationships among neighbouring A1 cells; furthermore, the same mechanism used to model V1 complex cells reproduced nonlinear responses similar to the pitch selectivity. These results contribute to the understanding of the sensory cortices of different modalities in a novel and integrated manner.
Efficient Sampling for Bipartite Matching Problems
Authors: Maksims Volkovs, Richard S. Zemel
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Bipartite matching problems characterize many situations, ranging from ranking in information retrieval to correspondence in vision. Exact inference in real-world applications of these problems is intractable, making efficient approximation methods essential for learning and inference. In this paper we propose a novel {\it sequential matching} sampler based on the generalization of the Plackett-Luce model, which can effectively make large moves in the space of matchings. This allows the sampler to match the difficult target distributions common in these problems: highly multimodal distributions with well separated modes. We present experimental results with bipartite matching problems - ranking and image correspondence - which show that the sequential matching sampler efficiently approximates the target distribution, significantly outperforming other sampling approaches.
Volume Regularization for Binary Classification
Authors: Koby Crammer, Tal Wagner
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We introduce a large-volume box classification for binary   prediction, which maintains a subset of weight vectors, and   specifically axis-aligned boxes. Our learning algorithm seeks for a   box of large volume that contains ``simple'' weight vectors which   most of are accurate on the training set. Two versions of the   learning process are cast as convex optimization problems, and it   is shown how to solve them efficiently.  The formulation yields a   natural PAC-Bayesian performance bound and it is shown to minimize a   quantity directly aligned with it. The algorithm outperforms SVM and   the recently proposed AROW algorithm on a majority of $30$ NLP   datasets and binarized USPS optical character recognition datasets.
Causal discovery with scale-mixture model for spatiotemporal variance dependencies
Authors: Zhitang Chen, Kun Zhang, Laiwan Chan
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: In conventional causal discovery, structural equation models (SEM) are directly applied to the observed variables, meaning that the causal effect can be represented as a function of the direct causes themselves. However, in many real world problems, there are significant dependencies in the variances or energies, which indicates that causality may possibly take place at the level of variances or energies. In this paper, we propose a probabilistic causal scale-mixture model with spatiotemporal variance dependencies to represent a specific type of generating mechanism of the observations. In particular, the causal mechanism including contemporaneous and temporal causal relations in variances or energies is represented by a Structural Vector AutoRegressive model (SVAR). We prove the identifiability of this model under the non-Gaussian assumption on the innovation processes. We also propose algorithms to estimate the involved parameters and discover the contemporaneous causal structure. Experiments on synthesis and real world data are conducted to show the applicability of the proposed model and algorithms.
Neurally Plausible Reinforcement Learning of Working Memory Tasks
Authors: Jaldert Rombouts, Pieter Roelfsema, Sander M. Bohte
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: A key function of brains is undoubtedly the abstraction and maintenance of information from the environment for later use. Neurons in association cortex play an important role in this process: during learning these neurons become tuned to relevant features and represent the information that is required later as a persistent elevation of their activity. It is however not well known how these neurons acquire their task-relevant tuning. Here we introduce a biologically plausible learning scheme that explains how neurons become selective for relevant information when animals learn by trial and error. We propose that the action selection stage feeds back attentional signals to earlier processing levels. These feedback signals interact with feedforward signals to form synaptic tags at those connections that are responsible for the stimulus-response mapping. A globally released neuromodulatory signal interacts with these tagged synapses to determine the sign and strength of plasticity. The learning scheme is generic because it can train networks in different tasks, simply by varying inputs and rewards. It explains how neurons in association cortex learn to (1) temporarily store task-relevant information in non-linear stimulus-response mapping tasks and (2) learn to optimally integrate probabilistic evidence for perceptual decision making.
Simultaneously Leveraging Output and Task Structures for Multiple-Output Regression
Authors: Piyush Rai, Abhishek Kumar, Hal Daume
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Multiple-output regression models require estimating multiple functions, one for each output. To improve parameter estimation in such models, methods based on structural regularization of the model parameters are usually needed. In this paper, we present a multiple-output regression model that leverages the covariance structure of the functions (i.e., how the multiple functions are related with each other) as well as the conditional covariance structure of the outputs. This is in contrast with existing methods that usually take into account only one of these structures. More importantly, unlike most of the other existing methods, none of these structures need be known a priori in our model, and are learned from the data. Several previously proposed structural regularization based  multiple-output regression models turn out to be special cases of our model. Moreover, in addition to being a rich model for multiple-output regression, our model can also be used in estimating the graphical model structure of a set of variables (multivariate outputs) conditioned on another set of variables (inputs). Experimental results on both synthetic and real datasets demonstrate the effectiveness of our method.
Feature Clustering for Accelerating Parallel Coordinate Descent
Authors: Chad Scherrer, Ambuj Tewari, Mahantesh Halappanavar, David Haglin
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Large scale $\ell_1$-regularized loss minimization problems arise in numerous applications such as compressed sensing and high dimensional supervised learning, including classification and regression problems.  High performance algorithms and implementations are critical to efficiently solving these problems.  Building upon previous work on coordinate descent algorithms for $\ell_1$ regularized problems, we introduce a novel family of algorithms called block-greedy coordinate descent that includes, as special cases, several existing algorithms such as SCD, Greedy CD, Shotgun, and Thread-greedy.  We give a unified convergence analysis for the family of block-greedy algorithms.  The analysis suggests that block-greedy coordinate descent can better exploit parallelism if features are clustered so that the maximum inner product between features in different blocks is small.  Our theoretical convergence analysis is supported with experimental results using data from diverse real-world applications.  We hope that algorithmic approaches and convergence analysis we provide will not only advance the field, but will also encourage researchers to systematically explore the design space of algorithms for solving large-scale $\ell_1$-regularization problems.
Phoneme Classification using Constrained Variational Gaussian Process Dynamical System
Authors: Hyunsin Park, Sungrack Yun, Sanghyuk Park, Jongmin Kim, Chang D. Yoo
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: This paper describes a new acoustic model based on variational Gaussian process dynamical system (VGPDS) for phoneme classification. The proposed model overcomes the limitations of the classical HMM in modeling the real speech data, by adopting a nonlinear and nonparametric model. In our model, the GP prior on the dynamics function enables representing the complex dynamic structure of speech, while the GP prior on the emission function successfully models the global dependency over the observations. Additionally, we introduce variance constraint to the original VGPDS for mitigating sparse approximation error of the kernel matrix. The effectiveness of the proposed model is demonstrated with extensive experimental results including parameter estimation, classification performance on the synthetic and benchmark datasets.
Fast Variational Inference in the Conjugate Exponential Family
Authors: James Hensman, Magnus Rattray, Neil D. Lawrence
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We present a general method for deriving collapsed variational inference algorithms for probabilistic models in the conjugate exponential family. Our method unifies many existing approaches to collapsed variational inference. Our collapsed variational inference leads to a new lower bound on the marginal likelihood. We exploit the information geometry of the bound to derive much faster optimization methods based on conjugate gradients for these models. Our approach is very general and is easily applied to any model where the mean field update equations have been derived. Empirically we show significant speed-ups for probabilistic models optimized using our bound.
Identifiability and Unmixing of Latent Parse Trees
Authors: Daniel J. Hsu, Sham M. Kakade, Percy Liang
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: This paper explores unsupervised learning of parsing models along two directions.  First, which models are identifiable from infinite data?  We use a general technique for numerically checking identifiability based on the rank of a Jacobian matrix, and apply it to several standard constituency and dependency parsing models.  Second, for identifiable models, how do we estimate the parameters efficiently?  EM suffers from local optima, while recent work using spectral methods cannot be directly applied since the topology of the parse tree varies across sentences.  We develop a strategy, unmixing, which deals with this additional complexity for restricted classes of parsing models.
On the (Non-)existence of Convex, Calibrated Surrogate Losses for Ranking
Authors: Clément Calauzènes, Nicolas Usunier, Patrick Gallinari
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We study surrogate losses for learning to rank, in a framework where the rankings are induced by scores and the task is to learn the scoring function. We focus on the calibration of surrogate losses with respect to a ranking evaluation metric, where the calibration is equivalent to the guarantee that near-optimal values of the sur- rogate risk imply near-optimal values of the risk deﬁned by the evaluation metric. We prove that if a surrogate loss is a convex function of the scores, then it is not calibrated with respect to two evaluation metrics widely used for search engine evaluation, namely the Average Precision and the Expected Reciprocal Rank. We also show that such convex surrogate losses cannot be calibrated with respect to the Pairwise Disagreement, an evaluation metric used when learning from pair- wise preferences. Our results cast lights on the intrinsic difﬁculty of some ranking problems, as well as on the limitations of learning-to-rank algorithms based on the minimization of a convex surrogate risk.
Learning with Partially Absorbing Random Walks
Authors: Xiao-ming Wu, Zhenguo Li, Anthony M. So, John Wright, Shih-fu Chang
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We propose a novel stochastic process that is with probability $\alpha_i$ being absorbed at current state $i$, and with probability $1-\alpha_i$ follows a random edge out of it. We analyze its properties and show its potential for exploring graph structures. We prove that under proper absorption rates, a random walk starting from a set $\mathcal{S}$ of low conductance will be mostly absorbed in $\mathcal{S}$. Moreover, the absorption probabilities vary slowly inside $\mathcal{S}$, while dropping sharply outside $\mathcal{S}$, thus implementing the desirable cluster assumption for graph-based learning. Remarkably, the partially absorbing process unifies many popular models arising in a variety of contexts, provides new insights into them, and makes it possible for transferring findings from one paradigm to another. Simulation results demonstrate its promising applications in graph-based learning.
Relax and Randomize : From Value to Algorithms
Authors: Sasha Rakhlin, Ohad Shamir, Karthik Sridharan
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We show a principled way of deriving online learning algorithms from a minimax analysis. Various upper bounds on the minimax value, previously thought to be non-constructive, are shown to yield algorithms. This allows us to seamlessly recover known methods and to derive new ones, also capturing such ''unorthodox'' methods as Follow the Perturbed Leader and the R^2 forecaster. Understanding the inherent complexity of the learning problem thus leads to the development of algorithms. To illustrate our approach, we present several new algorithms, including a family of randomized methods that use the idea of a ''random play out''. New versions of the Follow-the-Perturbed-Leader algorithms are presented, as well as methods based on the Littlestone's dimension, efficient methods for matrix completion with trace norm, and algorithms for the problems of transductive learning and prediction with static experts.
Inverse Reinforcement Learning through Structured Classification
Authors: Edouard Klein, Matthieu Geist, Bilal Piot, Olivier Pietquin
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: This paper adresses the inverse reinforcement learning (IRL) problem, that is inferring a reward for which a demonstrated expert behavior is optimal. We introduce a new algorithm, SCIRL, whose principle is to use the so-called feature expectation of the expert as the parameterization of the score function of a multi-class classifier. This approach produces a reward function for which the expert policy is provably near-optimal. Contrary to most of existing IRL algorithms, SCIRL does not require solving the direct RL problem. Moreover, with an appropriate heuristic, it can succeed with only trajectories sampled according to the expert behavior. This is illustrated on a car driving simulator.
Efficient and direct estimation of a neural subunit model for sensory coding
Authors: Brett Vintch, Andrew Zaharia, J Movshon, Eero P. Simoncelli
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Many visual and auditory neurons have response properties that are well explained by pooling the rectified responses of a set of self-similar linear filters. These filters cannot be found using spike-triggered averaging (STA), which estimates only a single filter. Other methods, like spike-triggered covariance (STC), define a multi-dimensional response subspace, but require substantial amounts of data and do not produce unique estimates of the linear filters. Rather, they provide a linear basis for the subspace in which the filters reside. Here, we define a 'subunit' model as an LN-LN cascade, in which the first linear stage is restricted to a set of shifted ("convolutional") copies of a common filter, and the first nonlinear stage consists of rectifying nonlinearities that are identical for all filter outputs; we refer to these initial LN elements as the 'subunits' of the receptive field. The second linear stage then computes a weighted sum of the responses of the rectified subunits. We present a method for directly fitting this model to spike data. The method performs well for both simulated and real data (from primate V1), and the resulting model outperforms STA and STC in terms of both cross-validated accuracy and efficiency.
Discriminative Learning of Sum-Product Networks
Authors: Robert Gens, Pedro Domingos
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Sum-product networks are a new deep architecture that can perform fast, exact in- ference on high-treewidth models. Only generative methods for training SPNs have been proposed to date. In this paper, we present the ﬁrst discriminative training algorithms for SPNs, combining the high accuracy of the former with the representational power and tractability of the latter. We show that the class of tractable discriminative SPNs is broader than the class of tractable generative ones, and propose an efﬁcient backpropagation-style algorithm for computing the gradient of the conditional log likelihood. Standard gradient descent suffers from the diffusion problem, but networks with many layers can be learned reliably us- ing “hard” gradient descent, where marginal inference is replaced by MPE infer- ence (i.e., inferring the most probable state of the non-evidence variables). The resulting updates have a simple and intuitive form. We test discriminative SPNs on standard image classiﬁcation tasks. We obtain the best results to date on the CIFAR-10 dataset, using fewer features than prior methods with an SPN architec- ture that learns local image structure discriminatively. We also report the highest published test accuracy on STL-10 even though we only use the labeled portion of the dataset.
Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions
Authors: Alekh Agarwal, Sahand Negahban, Martin J. Wainwright
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We develop and analyze stochastic optimization algorithms for problems in which the expected loss is strongly convex, and the optimum is (approximately) sparse. Previous approaches are able to exploit only one of these two structures, yielding a $\order(\pdim/T)$ convergence rate for strongly convex objectives in $\pdim$ dimensions and $\order(\sqrt{\spindex( \log\pdim)/T})$ convergence rate when the optimum is $\spindex$-sparse. Our algorithm is based on successively solving a series of $\ell_1$-regularized optimization problems using Nesterov's dual averaging algorithm. We establish that the error of our solution after $T$ iterations is at most $\order(\spindex(\log\pdim)/T)$, with natural extensions to approximate sparsity. Our results apply to locally Lipschitz losses including the logistic, exponential, hinge and least-squares losses. By recourse to statistical minimax results, we show that our convergence rates are optimal up to constants. The effectiveness of our approach is also confirmed in numerical simulations where we compare to several baselines on a least-squares regression problem.
Bandit Algorithms boost Brain Computer Interfaces for motor-task selection of a brain-controlled button
Authors: Joan Fruitet, Alexandra Carpentier, Maureen Clerc, Rémi Munos
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: A brain-computer interface (BCI) allows users to “communicate” with a computer without using their muscles. BCI based on sensori-motor rhythms use imaginary motor tasks, such as moving the right or left hand to send control signals. The performances of a BCI can vary greatly across users but also depend on the tasks used, making the problem of appropriate task selection an important issue. This study presents a new procedure to automatically select as fast as possible a discriminant motor task for a brain-controlled button. We develop for this purpose an adaptive algorithm UCB-classif based on the stochastic bandit theory. This shortens the training stage, thereby allowing the exploration of a greater variety of tasks. By not wasting time on inefficient tasks, and focusing on the most promising ones, this algorithm results in a faster task selection and a more efficient use of the BCI training session. Comparing the proposed method to the standard practice in task selection, for a fixed time budget, UCB-classif leads to an improve classification rate, and for a fix classification rate, to a reduction of the time spent in training by 50%.
Localizing 3D cuboids in single-view images
Authors: Jianxiong Xiao, Bryan Russell, Antonio Torralba
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: In this paper we seek to detect rectangular cuboids and localize their corners in uncalibrated single-view images depicting everyday scenes. In contrast to recent approaches that rely on detecting vanishing points of the scene and grouping line segments to form cuboids, we build a discriminative parts-based detector that models the appearance of the cuboid corners and internal edges while enforcing consistency to a 3D cuboid model. Our model is invariant to the different 3D viewpoints and aspect ratios and is able to detect cuboids across many different object categories. We introduce a database of images with cuboid annotations that spans a variety of indoor and outdoor scenes and show qualitative and quantitative results on our collected database. Our model out-performs baseline detectors that use 2D constraints alone on the task of localizing cuboid corners.
A Convex Formulation for Learning Scale-Free Networks via Submodular Relaxation
Authors: Aaron Defazio, Tibério S. Caetano
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: A key problem in statistics and machine learning is the determination of network structure from data. We consider the case where the structure of the graph to be reconstructed is known to be scale-free. We show that in such cases it is natural to formulate structured sparsity inducing priors using submodular functions, and we use their Lovasz extension to obtain a convex relaxation. For tractable classes such as Gaussian graphical models, this leads to a convex optimization problem that can be efficiently solved. We show that our method results in an improvement in the accuracy of reconstructed networks for synthetic data. We also show how our prior encourages scale-free reconstructions on a bioinfomatics dataset.
Hamming Distance Metric Learning
Authors: Mohammad Norouzi, David J Fleet, Ruslan Salakhutdinov
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Motivated by large-scale multimedia applications we propose to learn mappings from high-dimensional data to binary codes that preserve semantic similarity. Binary codes are well suited to large-scale applications as they are storage efficient and permit exact sub-linear kNN search. The framework is applicable to broad families of mappings, and uses a flexible form of triplet ranking loss. We overcome discontinuous optimization of the discrete mappings by minimizing a piecewise-smooth upper bound on empirical loss, inspired by latent structural SVMs.  We develop a new loss-augmented inference algorithm that is quadratic in the code length.  We show strong retrieval performance on CIFAR-10 and MNIST, with promising classification results using no more than kNN on the binary codes.
Co-Regularized Hashing for Multimodal Data
Authors: Yi Zhen, Dit-Yan Yeung
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Hashing-based methods provide a very promising approach to large-scale similarity search.  To obtain compact hash codes, a recent trend seeks to learn the hash functions from data automatically.  In this paper, we study hash function learning in the context of multimodal data.  We propose a novel multimodal hash function learning method, called Co-Regularized Hashing (CRH), based on a boosted co-regularization framework.  The hash functions for each bit of the hash codes are learned by solving DC (difference of convex functions) programs, while the learning for multiple bits proceeds via a boosting procedure so that the bias introduced by the hash functions can be sequentially minimized.  We empirically compare CRH with two state-of-the-art multimodal hash function learning methods on two publicly available data sets.
The Coloured Noise Expansion and Parameter Estimation of Diffusion Processes
Authors: Simon Lyons, Amos J. Storkey, Simo Särkkä
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Stochastic differential equations (SDE) are a natural tool for modelling systems that are inherently noisy or contain uncertainties that can be modelled as stochastic processes. Crucial to the process of using SDE to build mathematical models is the ability to estimate parameters of those models from observed data. Over the past few decades, significant progress has been made on this problem, but we are still far from having a definitive solution. We describe a novel method of approximating a diffusion process that we show to be useful in Markov chain Monte-Carlo (MCMC) inference algorithms. We take the ‘white’ noise that drives a diffusion process and decompose it into two terms. The first is a ‘coloured noise’ term that can be deterministically controlled by a set of auxilliary variables. The second term is small and enables us to form a linear Gaussian ‘small noise’ approximation. The decomposition allows us to take a diffusion process of interest and cast it in a form that is amenable to sampling by MCMC methods. We explain why many state-of-the-art inference methods fail on highly nonlinear inference problems. We demonstrate experimentally that our method performs well in such situations. Our results show that this method is a promising new tool for use in inference and parameter estimation problems.
How Prior Probability Influences Decision Making: A Unifying Probabilistic Model
Authors: Yanping Huang, Timothy Hanks, Mike Shadlen, Abram L. Friesen, Rajesh P. Rao
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: How does the brain combine prior knowledge with sensory evidence when making decisions under uncertainty? Two competing descriptive models have been proposed based on experimental data.  The first posits an additive offset to a decision variable, implying a static effect of the prior. However, this model is inconsistent with recent data from a motion discrimination task involving temporal integration of uncertain sensory evidence. To explain this data, a second model has been proposed which assumes a time-varying influence of the prior. Here we present a normative model of decision making that incorporates prior knowledge in a principled way.  We show that the additive offset model and the time-varying prior model emerge naturally when decision making is viewed within the framework of partially observable Markov decision processes (POMDPs).  Decision making in the model reduces to (1) computing beliefs given observations and prior information in a Bayesian manner, and (2) selecting actions based on these beliefs to maximize the  expected sum of future rewards. We show that the model can explain both  data previously explained using the additive offset model as well as more  recent data on the time-varying influence of prior knowledge on decision making.
Structured Learning of Gaussian Graphical Models
Authors: Karthik Mohan, Mike Chung, Seungyeop Han, Daniela Witten, Su-in Lee, Maryam Fazel
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We consider estimation of multiple high-dimensional Gaussian graphical models corresponding to a single set of nodes under several distinct conditions. We assume that most aspects of the networks are shared, but that there are some structured differences between them. Specifically, the network differences are generated from node perturbations: a few nodes are perturbed across networks, and most or all edges stemming from such nodes differ between networks. This corresponds to a simple model for the mechanism underlying many cancers, in which the gene regulatory network is disrupted  due to the aberrant activity of a few specific genes. We propose to solve this problem using the structured joint graphical lasso, a convex optimization problem that is based upon the use of a novel symmetric overlap norm penalty, which we solve using  an alternating directions method of multipliers algorithm. Our proposal is illustrated on synthetic data and on an application to brain cancer gene expression data.
Entropy Estimations Using Correlated Symmetric Stable Random Projections
Authors: Ping Li, Cun-hui Zhang
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Methods for efficiently estimating the Shannon entropy of data streams have important applications in learning, data mining, and network anomaly detections (e.g., the DDoS attacks). For nonnegative data streams, the method of Compressed Counting (CC) based on maximally-skewed stable random projections can provide accurate estimates of the Shannon entropy using small storage. However, CC is no longer applicable when entries of data streams can be below zero, which is a common scenario when comparing two streams. In this paper, we propose an algorithm for entropy estimation in general data streams which allow negative entries. In our method, the Shannon entropy is approximated by the finite difference of two correlated frequency moments estimated from correlated samples of symmetric stable random variables. Our experiments confirm that this method is able to substantially better approximate the Shannon entropy compared to the prior state-of-the-art.
Nyström Method vs Random Fourier Features: A Theoretical and Empirical Comparison
Authors: Tianbao Yang, Yu-feng Li, Mehrdad Mahdavi, Rong Jin, Zhi-Hua Zhou
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Both random Fourier features and the Nyström method have been successfully applied to efficient kernel learning. In this work, we investigate the fundamental difference between these two approaches, and how the difference could affect their generalization performances. Unlike approaches based on random Fourier features  where the basis functions (i.e., cosine and sine functions) are sampled from a distribution  {\it independent} from the training data, basis functions used by the Nyström method are randomly sampled from the training examples and are therefore {\it data dependent}. By exploring this difference, we show that when there is a large gap in the eigen-spectrum of the kernel matrix, approaches based the Nyström method can yield  impressively  better generalization error bound than random Fourier features based approach. We empirically verify our theoretical findings on a wide range of large data sets.
Spiking and saturating dendrites differentially expand single neuron computation capacity
Authors: Romain Cazé, Mark Humphries, Boris S. Gutkin
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: The integration of excitatory inputs in dendrites is non-linear: multiple excitatory inputs can produce a local depolarization departing from the arithmetic sum of each input's response taken separately. If this depolarization is bigger than the arithmetic sum, the dendrite is spiking; if the depolarization is smaller, the dendrite is saturating. Decomposing a dendritic tree into independent dendritic spiking units greatly extends its computational capacity, as the neuron then maps onto a two layer neural network, enabling it to compute linearly non-separable Boolean functions (lnBFs). How can these lnBFs be implemented by dendritic architectures in practise? And can saturating dendrites equally expand computational capacity? To adress these questions we use a binary neuron model and Boolean algebra. First, we confirm that spiking dendrites enable a neuron to compute lnBFs using an architecture based on the disjunctive normal form (DNF). Second, we prove that saturating dendrites as well as spiking dendrites also enable a neuron to compute lnBFs using an architecture based on the conjunctive normal form (CNF). Contrary to the DNF-based architecture, a CNF-based architecture leads to a dendritic unit tuning that does not imply the neuron tuning, as has been observed experimentally. Third, we show that one cannot use a DNF-based architecture with saturating dendrites. Consequently, we show that an important family of lnBFs implemented with a CNF-architecture can require an exponential number of saturating dendritic units, whereas the same family implemented with either a DNF-architecture or a CNF-architecture always require a linear number of spiking dendritic unit. This minimization could explain why a neuron spends energetic resources to make its dendrites spike.