mtybilly/Instruct2DS huggingface dataset:
A Unifying Perspective of Parametric Policy Search Methods for Markov Decision Processes
Authors: David Barber Thomas Furmston
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Parametric policy search algorithms are one of the methods of choice for the optimisation of Markov Decision Processes, with Expectation Maximisation and natural gradient ascent being considered the current state of the art in the field. In this article we provide a unifying perspective of these two algorithms by showing that their step-directions in the parameter space are closely related to the search direction of an approximate Newton method. This analysis leads naturally to the consideration of this approximate Newton method as an alternative gradient-based method for Markov Decision Processes. We are able show that the algorithm has numerous desirable properties, absent in the naive application of Newton's method, that make it a viable alternative to either Expectation Maximisation or natural gradient ascent. Empirical results suggest that the algorithm has excellent convergence and robustness properties, performing strongly in comparison to both Expectation Maximisation and natural gradient ascent.
Convergence and Energy Landscape for Cheeger Cut Clustering
Authors: Thomas Laurent, David Uminsky, James V. Brecht Xavier Bresson
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Unsupervised clustering of scattered, noisy and high-dimensional data points is an important and difficult problem. Continuous relaxations of balanced cut problems  yield excellent clustering results. This paper provides rigorous convergence results for two algorithms that solve the relaxed Cheeger Cut minimization.  The first algorithm is a new steepest descent algorithm and the second one is a slight modification of the Inverse Power Method algorithm \cite{pro:HeinBuhler10OneSpec}. While the steepest descent algorithm has better theoretical convergence properties,  in practice both algorithm perform equally.  We also completely characterize the local minima of the relaxed problem in terms of the original balanced cut problem, and relate this characterization to the convergence of the algorithms.
A Divide-and-Conquer Method for Sparse Inverse Covariance Estimation
Authors: Arindam Banerjee, Inderjit S. Dhillon, Pradeep K. Ravikumar Cho-jui Hsieh
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: In this paper, we consider the $\ell_1$ regularized sparse inverse covariance matrix estimation problem with a very large number of variables. Even in the face of this high dimensionality, and with limited number of samples, recent work has shown this estimator to have strong statistical guarantees in recovering the true structure of the sparse inverse covariance matrix, or alternatively the underlying graph structure of the corresponding Gaussian Markov Random Field. Our proposed algorithm divides the problem into  smaller sub-problems, and uses the solutions of the sub-problems to build a good approximation for the original problem. We derive a bound on the distance of the approximate solution to the true solution. Based on this bound, we propose a clustering algorithm that attempts to minimize this bound, and in practice, is able to find effective partitions of the variables. We further use the approximate solution, i.e., solution resulting from solving the sub-problems,  as an initial point to solve the original problem, and achieve a much faster computational procedure.  As an example, a recent state-of-the-art method, QUIC requires 10 hours to solve a problem (with 10,000 nodes) that arises from a climate application, while our proposed algorithm, Divide and Conquer QUIC (DC-QUIC) only requires one hour to solve the problem.
Nonconvex Penalization Using Laplace Exponents and Concave Conjugates
Authors: Bojun Tu Zhihua Zhang
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: In this paper we study sparsity-inducing nonconvex penalty functions using L´evy processes. We deﬁne such a penalty as the Laplace exponent of a subordina- tor. Accordingly, we propose a novel approach for the construction of sparsity- inducing nonconvex penalties. Particularly, we show that the nonconvex logarith- mic (LOG) and exponential (EXP) penalty functions are the Laplace exponents of Gamma and compound Poisson subordinators, respectively. Additionally, we explore the concave conjugate of nonconvex penalties. We ﬁnd that the LOG and EXP penalties are the concave conjugates of negative Kullback-Leiber (KL) dis- tance functions. Furthermore, the relationship between these two penalties is due to asymmetricity of the KL distance.
How They Vote: Issue-Adjusted Models of Legislative Behavior
Authors: David M. Blei Sean Gerrish
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We develop a probabilistic model of legislative data that uses the text of the bills to uncover lawmakers' positions on specific political issues.  Our model can be used to explore how a lawmaker's voting patterns deviate from what is expected and how that deviation depends on what is being voted on. We derive approximate posterior inference algorithms based on variational methods. Across 12 years of legislative data, we demonstrate both improvement in heldout predictive performance and the model's utility in interpreting an inherently multi-dimensional space.
Multiclass Learning Approaches: A Theoretical Comparison with Implications
Authors: Sivan Sabato, Shai S. Shwartz Amit Daniely
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We theoretically analyze and compare the following five popular multiclass classification methods: One vs. All, All Pairs, Tree-based classifiers, Error Correcting Output Codes (ECOC) with randomly generated code matrices, and Multiclass SVM. In the first four methods, the classification is based on a reduction to binary classification. We consider the case where the binary classifier comes from a class of VC dimension $d$, and in particular from the class of halfspaces over $\reals^d$. We analyze both the estimation error and the approximation error of these methods. Our analysis reveals interesting conclusions of practical relevance, regarding the success of the different approaches under various conditions. Our proof technique employs tools from VC theory to analyze the \emph{approximation error} of hypothesis classes. This is in sharp contrast to most, if not all, previous uses of VC theory, which only deal with estimation error.
Dynamical And-Or Graph Learning for Object Shape Modeling and Detection
Authors: Liang Lin Xiaolong Wang
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: This paper studies a novel discriminative part-based model to represent and recognize object shapes with an “And-Or graph”. We define this model consisting of three layers: the leaf-nodes with collaborative edges for localizing local parts, the or-nodes specifying the switch of leaf-nodes, and the root-node encoding the global verification. A discriminative learning algorithm, extended from the CCCP [23], is proposed to train the model in a dynamical manner: the model structure (e.g., the configuration of the leaf-nodes associated with the or-nodes) is automatically determined with optimizing the multi-layer parameters during the iteration. The advantages of our method are two-fold. (i) The And-Or graph model enables us to handle well large intra-class variance and background clutters for object shape detection from images. (ii) The proposed learning algorithm is able to obtain the And-Or graph representation without requiring elaborate supervision and initialization. We validate the proposed method on several challenging databases (e.g., INRIA-Horse, ETHZ-Shape, and UIUC-People), and it outperforms the state-of-the-arts approaches.
Augmented-SVM: Automatic space partitioning for combining multiple non-linear dynamics
Authors: Aude Billard Ashwini Shukla
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Non-linear dynamical systems (DS) have been used extensively for building generative models of human behavior. Its applications range from modeling brain dynamics  to encoding motor commands. Many schemes have been proposed for encoding robot motions using dynamical systems with a single attractor placed at a predefined target in state space. Although these enable the robots to react against sudden perturbations without any re-planning, the motions are always directed towards a single target. In this work, we focus on combining several such DS with distinct attractors, resulting in a multi-stable DS. We show its applicability in reach-to-grasp tasks where the attractors represent several grasping points on the target object. While exploiting multiple attractors provides more flexibility in recovering from unseen perturbations, it also increases the complexity of the underlying learning problem. Here we present the Augmented-SVM (A-SVM) model which inherits region partitioning ability of the well known SVM classifier and is augmented with novel constraints derived from the individual DS. The new constraints modify the original SVM dual whose optimal solution then results in a new class of support vectors (SV). These new SV ensure that the resulting multi-stable DS incurs minimum deviation from the original dynamics and is stable at each of the attractors within a finite region of attraction. We show, via implementations on a simulated 10 degrees of freedom mobile robotic platform, that the model is capable of real-time motion generation and is able to adapt on-the-fly to perturbations.
Coupling Nonparametric Mixtures via Latent Dirichlet Processes
Authors: John W. Fisher Dahua Lin
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Mixture distributions are often used to model complex data. In this paper, we develop a new method that jointly estimates mixture models over multiple data sets by exploiting the statistical dependencies between them. Specifically, we introduce a set of latent Dirichlet processes as sources of component models (atoms), and for each data set, we construct a nonparametric mixture model by combining sub-sampled versions of the latent DPs. Each mixture model may acquire atoms from different latent DPs, while each atom may be shared by multiple mixtures. This multi-to-multi association distinguishes the proposed method from prior constructions that rely on tree or chain structures, allowing mixture models to be coupled more flexibly. In addition, we derive a sampling algorithm that jointly infers the model parameters and present experiments on both document analysis and image modeling.
Multiclass Learning with Simplex Coding
Authors: Tomaso Poggio, Lorenzo Rosasco, Jean-jeacques Slotine Youssef Mroueh
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: In this paper we dicuss a novel  framework for multiclass learning,  defined by  a suitable coding/decoding strategy,  namely the simplex coding, that allows to generalize to multiple classes a relaxation approach commonly used in binary classification. In this framework a  relaxation error analysis can be developed avoiding constraints on the considered hypotheses class.  Moreover, we show that in this setting it is possible to derive the first provably consistent  regularized methods with training/tuning complexity which is {\em independent} to the number of classes. Tools from convex analysis are introduced that can be used beyond the scope of this paper.
Clustering Sparse Graphs
Authors: Sujay Sanghavi, Huan Xu Yudong Chen
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We develop a new algorithm to cluster sparse unweighted graphs -- i.e. partition the nodes into disjoint clusters so that there is higher density within clusters, and low across clusters. By sparsity we mean the setting where both the in-cluster and across cluster edge densities are very small, possibly vanishing in the size of the graph. Sparsity makes the problem noisier, and hence more difficult to solve.   Any clustering involves a tradeoff between minimizing two kinds of errors: missing edges within clusters and present edges across clusters. Our insight is that in the sparse case, these must be {\em penalized differently}. We analyze our algorithm's performance on the natural, classical and widely studied ``planted partition'' model (also called the stochastic block model); we show that our algorithm can cluster sparser graphs, and with smaller clusters, than all previous methods. This is seen empirically as well.
On-line Reinforcement Learning Using Incremental Kernel-Based Stochastic Factorization
Authors: Doina Precup, Joelle Pineau Andre Barreto
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: The ability to learn a policy for a sequential decision problem with continuous state space using on-line data is a long-standing challenge. This paper presents a new reinforcement-learning algorithm, called iKBSF, which extends the benefits of kernel-based learning to the on-line scenario. As a kernel-based method, the proposed algorithm is stable and has good convergence properties. However, unlike other similar algorithms,iKBSF's space complexity is independent of the number of sample transitions, and as a result it can process an arbitrary amount of data. We present theoretical results showing that iKBSF can approximate (to any level of accuracy) the value function that would be learned by an equivalent batch non-parametric kernel-based reinforcement learning approximator. In order to show the effectiveness of the proposed algorithm in practice, we apply iKBSF to the challenging three-pole balancing task, where the ability to process a large number of transitions is crucial for achieving a high success rate.
Accelerated Training for Matrix-norm Regularization: A Boosting Approach
Authors: Dale Schuurmans, Yao-liang Yu Xinhua Zhang
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Sparse learning models typically combine a smooth loss with a nonsmooth penalty, such as trace norm. Although recent developments in sparse approximation have offered promising solution methods, current approaches either apply only to matrix-norm constrained problems or provide suboptimal convergence rates. In this paper, we propose a boosting method for regularized learning that guarantees $\epsilon$ accuracy within $O(1/\epsilon)$ iterations. Performance is further accelerated by interlacing boosting with fixed-rank local optimization---exploiting a simpler local objective than previous work. The proposed method yields state-of-the-art performance on large-scale problems. We also demonstrate an application to latent multiview learning for which we provide the first efficient weak-oracle.
Supervised Learning with Similarity Functions
Authors: Prateek Jain Purushottam Kar
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We address the problem of general supervised learning when data can only be accessed through an (indefinite) similarity function between data points. Existing work on learning with indefinite kernels has concentrated solely on binary/multiclass classification problems. We propose a model that is generic enough to handle any supervised learning task and also subsumes the model previously proposed for classification. We give a ''goodness'' criterion for similarity functions w.r.t. a given supervised learning task and then adapt a well-known landmarking technique to provide efficient algorithms for supervised learning using ''good'' similarity functions. We demonstrate the effectiveness of our model on three important supervised learning problems: a) real-valued regression, b) ordinal regression and c) ranking where we show that our method guarantees bounded generalization error. Furthermore, for the case of real-valued regression, we give a natural goodness definition that, when used in conjunction with a recent result in sparse vector recovery, guarantees a sparse predictor with bounded generalization error. Finally, we report results of our learning algorithms on regression and ordinal regression tasks using non-PSD similarity functions and demonstrate the effectiveness of our algorithms, especially that of the sparse landmark selection algorithm that achieves significantly higher accuracies than the baseline methods while offering reduced computational costs.
A Simple and Practical Algorithm for Differentially Private Data Release
Authors: Katrina Ligett, Frank Mcsherry Moritz Hardt
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We present a new algorithm for differentially private data release, based on a simple combination of the Exponential Mechanism with the Multiplicative Weights update rule.  Our MWEM algorithm achieves what are the best known and nearly optimal theoretical guarantees, while at the same time being simple to implement and experimentally more accurate on actual data sets than existing techniques.
Persistent Homology for Learning Densities with Bounded Support
Authors: Hedvig Kjellström, Danica Kragic, Carl Ek Florian T. Pokorny
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We present a novel method for learning densities with bounded support which enables us to incorporate `hard' topological constraints. In particular, we show how emerging techniques from computational algebraic topology and the notion of Persistent Homology can be combined with kernel based  methods from Machine Learning for the purpose of density estimation. The proposed formalism facilitates learning of models with bounded support in a principled way, and -- by incorporating Persistent Homology techniques in our approach -- we are able to encode algebraic-topological constraints which are not addressed in current state-of the art probabilistic models. We study the behaviour of our method on two synthetic examples for various sample sizes and exemplify the benefits of the proposed approach on a real-world data-set by learning a motion model for a racecar. We show how to learn a model which respects the underlying topological structure of the racetrack, constraining the trajectories of the car.
Proper losses for learning from partial labels
Authors: Jesús Cid-sueiro
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: This paper discusses the problem of calibrating posterior class probabilities from partially labelled data. Each instance is assumed to be labelled as belonging to one of several candidate categories, at most one of them being true. We generalize the concept of proper loss to this scenario, establish a necessary and sufficient condition for a loss function to be proper, and we show a direct procedure to construct a proper loss for partial labels from a conventional proper loss. The problem can be characterized by the mixing probability matrix relating the true class of the data and the observed labels. An interesting result is that the full knowledge of this matrix is not required, and losses can be constructed that are proper in a subset of the probability simplex.
Predicting Action Content On-Line and in Real Time before Action Onset – an Intracranial Human Study
Authors: Shengxuan Ye, Ian Ross, Adam Mamelak, Christof Koch Uri Maoz
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: The ability to predict action content from neural signals in real time before the ac- tion occurs has been long sought in the neuroscientiﬁc study of decision-making, agency and volition. On-line real-time (ORT) prediction is important for under- standing the relation between neural correlates of decision-making and conscious, voluntary action as well as for brain-machine interfaces. Here, epilepsy patients, implanted with intracranial depth microelectrodes or subdural grid electrodes for clinical purposes, participated in a “matching-pennies” game against an opponent. In each trial, subjects were given a 5 s countdown, after which they had to raise their left or right hand immediately as the “go” signal appeared on a computer screen. They won a ﬁxed amount of money if they raised a different hand than their opponent and lost that amount otherwise. The question we here studied was the extent to which neural precursors of the subjects’ decisions can be detected in intracranial local ﬁeld potentials (LFP) prior to the onset of the action. We found that combined low-frequency (0.1–5 Hz) LFP signals from 10 electrodes were predictive of the intended left-/right-hand movements before the onset of the go signal. Our ORT system predicted which hand the patient would raise 0.5 s before the go signal with 68±3% accuracy in two patients. Based on these results, we constructed an ORT system that tracked up to 30 electrodes simultaneously, and tested it on retrospective data from 7 patients. On average, we could predict the correct hand choice in 83% of the trials, which rose to 92% if we let the system drop 3/10 of the trials on which it was less conﬁdent. Our system demonstrates— for the ﬁrst time—the feasibility of accurately predicting a binary action on single trials in real time for patients with intracranial recordings, well before the action occurs.
Classification Calibration Dimension for General Multiclass Losses
Authors: Shivani Agarwal Harish G. Ramaswamy
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We study consistency properties of surrogate loss functions for general multiclass classification problems, defined by a general loss matrix. We extend the notion of classification calibration, which has been studied for binary and multiclass 0-1 classification problems (and for certain other specific learning problems), to the general multiclass setting, and derive necessary and sufficient conditions for a surrogate loss to be classification calibrated with respect to a loss matrix in this setting. We then introduce the notion of \emph{classification calibration dimension} of a multiclass loss matrix, which measures the smallest size' of a prediction space for which it is possible to design a convex surrogate that is classification calibrated with respect to the loss matrix. We derive both upper and lower bounds on this quantity, and use these results to analyze various loss matrices. In particular, as one application, we provide a different route from the recent result of Duchi et al.\ (2010) for analyzing the difficulty of designinglow-dimensional' convex surrogates that are consistent with respect to pairwise subset ranking losses. We anticipate the classification calibration dimension may prove to be a useful tool in the study and design of surrogate losses for general multiclass learning problems.
Analog readout for optical reservoir computers
Authors: François Duport, Yvon Paquot, Benjamin Schrauwen, Marc Haelterman, Serge Massar Anteo Smerieri
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Reservoir computing is a new, powerful and flexible machine learning technique that is easily implemented in hardware. Recently, by using a time-multiplexed architecture, hardware reservoir computers have reached performance comparable to digital implementations. Operating speeds allowing for real time information operation have been reached using optoelectronic systems. At present the main performance bottleneck is the readout layer which uses slow, digital postprocessing. We have designed an analog readout suitable for time-multiplexed optoelectronic reservoir computers, capable of working in real time. The readout has been built and tested experimentally on a standard benchmark task. Its performance is better than non-reservoir methods, with ample room for further improvement. The present work thereby overcomes one of the major limitations for the future development of hardware reservoir computers.
Perfect Dimensionality Recovery by Variational Bayesian PCA
Authors: Ryota Tomioka, Masashi Sugiyama, S. D. Babacan Shinichi Nakajima
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: The variational Bayesian (VB) approach is one of the best tractable approximations to the Bayesian estimation, and it was demonstrated to perform well in many applications. However, its good performance was not fully understood theoretically. For example, VB sometimes produces a sparse solution, which is regarded as a practical advantage of VB, but such sparsity is hardly observed in the rigorous Bayesian estimation. In this paper, we focus on probabilistic PCA and give more theoretical insight into the empirical success of VB. More specifically, for the situation where the noise variance is unknown, we derive a sufficient condition for perfect recovery of the true PCA dimensionality in the large-scale limit when the size of an observed matrix goes to infinity. In our analysis, we obtain bounds for a noise variance estimator and simple closed-form solutions for other parameters, which themselves are actually very useful for better implementation of VB-PCA.
Compressive neural representation of sparse, high-dimensional probabilities
Authors: Zachary Pitkow
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: This paper shows how sparse, high-dimensional probability distributions could be represented by neurons with exponential compression. The representation is a novel application of compressive sensing to sparse probability distributions rather than to the usual sparse signals. The compressive measurements correspond to expected values of nonlinear functions of the probabilistically distributed variables. When these expected values are estimated by sampling, the quality of the compressed representation is limited only by the quality of sampling. Since the compression preserves the geometric structure of the space of sparse probability distributions, probabilistic computation can be performed in the compressed domain. Interestingly, functions satisfying the requirements of compressive sensing can be implemented as simple perceptrons. If we use perceptrons as a simple model of feedforward computation by neurons, these results show that the mean activity of a relatively small number of neurons can accurately represent a high-dimensional joint distribution implicitly, even without accounting for any noise correlations. This comprises a novel hypothesis for how neurons could encode probabilities in the brain.
Shifting Weights: Adapting Object Detectors from Image to Video
Authors: Vignesh Ramanathan, Li Fei-fei, Daphne Koller Kevin Tang
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Typical object detectors trained on images perform poorly on video, as there is a clear distinction in domain between the two types of data. In this paper, we tackle the problem of adapting object detectors learned from images to work well on videos. We treat the problem as one of unsupervised domain adaptation, in which we are given labeled data from the source domain (image), but only unlabeled data from the target domain (video). Our approach, self-paced domain adaptation, seeks to iteratively adapt the detector by re-training the detector with automatically discovered target domain examples, starting with the easiest first. At each iteration, the algorithm adapts by considering an increased number of target domain examples, and a decreased number of source domain examples. To discover target domain examples from the vast amount of video data, we introduce a simple, robust approach that scores trajectory tracks instead of bounding boxes. We also show how rich and expressive features specific to the target domain can be incorporated under the same framework. We show promising results on the 2011 TRECVID Multimedia Event Detection and LabelMe Video datasets that illustrate the benefit of our approach to adapt object detectors to video.
Minimization of Continuous Bethe Approximations: A Positive Variation
Authors: Erik B. Sudderth Jason Pacheco
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We develop convergent minimization algorithms for Bethe variational approximations which explicitly constrain marginal estimates to families of valid distributions.  While existing message passing algorithms define fixed point iterations corresponding to stationary points of the Bethe free energy, their greedy dynamics do not distinguish between local minima and maxima, and can fail to converge. For continuous estimation problems, this instability is linked to the creation of invalid marginal estimates, such as Gaussians with negative variance. Conversely, our approach leverages multiplier methods with well-understood convergence properties, and uses bound projection methods to ensure that marginal approximations are valid at all iterations. We derive general algorithms for discrete and Gaussian pairwise Markov random fields, showing improvements over standard loopy belief propagation. We also apply our method to a hybrid model with both discrete and continuous variables, showing improvements over expectation propagation.
Optimal Regularized Dual Averaging Methods for Stochastic Optimization
Authors: Qihang Lin, Javier Pena Xi Chen
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: This paper considers a wide spectrum of regularized stochastic optimization problems where both the loss function and regularizer can be non-smooth.  We develop a novel algorithm based on the regularized dual averaging (RDA) method, that can simultaneously achieve the optimal convergence rates for both convex and strongly convex loss. In particular, for strongly convex loss, it achieves the optimal  rate of $O(\frac{1}{N}+\frac{1}{N^2})$ for $N$  iterations, which improves the best known rate $O(\frac{\log N }{N})$ of previous stochastic dual averaging algorithms. In addition, our method constructs the final solution directly from the proximal mapping instead of averaging of all previous iterates. For widely used sparsity-inducing regularizers (e.g., $\ell_1$-norm), it has the advantage of encouraging sparser solutions. We further develop a multi-stage extension using the proposed algorithm as a subroutine, which achieves the uniformly-optimal rate $O(\frac{1}{N}+\exp\{-N\})$ for strongly convex loss.
Gradient Weights help Nonparametric Regressors
Authors: Abdeslam Boularias Samory Kpotufe
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: In regression problems over $\real^d$, the unknown function $f$ often varies more in some coordinates than in others. We show that weighting each coordinate $i$ with the estimated norm of the $i$th derivative of $f$  is an efficient way to significantly improve the performance of distance-based regressors, e.g. kernel and $k$-NN regressors.  We propose a simple estimator of these derivative norms and prove its consistency. Moreover, the proposed  estimator is efficiently learned online.
Regularized Off-Policy TD-Learning
Authors: Sridhar Mahadevan, Ji Liu Bo Liu
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We present a novel $l_1$ regularized off-policy convergent TD-learning method (termed RO-TD), which is able to learn sparse representations of value functions with low computational complexity. The algorithmic framework underlying RO-TD integrates two key ideas: off-policy convergent gradient TD methods, such as TDC, and a convex-concave saddle-point formulation of non-smooth convex optimization, which enables first-order solvers and feature selection using online convex regularization. A detailed theoretical and experimental analysis of RO-TD is presented. A variety of experiments are presented to illustrate the off-policy convergence, sparse feature selection capability and low computational cost of the RO-TD algorithm.
Locating Changes in Highly Dependent Data with Unknown Number of Change Points
Authors: Daniil Ryabko Azadeh Khaleghi
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: The problem of multiple change point estimation is  considered for sequences  with unknown number of change points.  A consistency framework is suggested that is suitable for highly dependent time-series, and an asymptotically consistent algorithm is proposed.   In order for the consistency to be established the only assumption  required is that the data is generated by stationary ergodic time-series distributions. No modeling, independence or parametric assumptions are made; the data are allowed to be dependent and the dependence can be of arbitrary form.  The theoretical results are complemented with experimental evaluations.
Controlled Recognition Bounds for Visual Learning and Exploration
Authors: Alessandro Chiuso, Stefano Soatto Vasiliy Karasev
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: We describe the tradeoff between the performance in a visual recognition problem and the control authority that the agent can exercise on the sensing process. We focus on the problem of “visual search” of an object in an otherwise known and static scene, propose a measure of control authority, and relate it to the expected risk and its proxy (conditional entropy of the posterior density). We show this analytically, as well as empirically by simulation using the simplest known model that captures the phenomenology of image formation, including scaling and occlusions. We show that a “passive” agent given a training set can provide no guarantees on performance beyond what is afforded by the priors, and that an “omnipotent” agent, capable of infinite control authority, can achieve arbitrarily good performance (asymptotically).
Multi-Stage Multi-Task Feature Learning
Authors: Jieping Ye, Chang-shui Zhang Pinghua Gong
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Multi-task sparse feature learning aims to improve the generalization performance by exploiting the shared features among tasks. It has been successfully applied to many applications including computer vision and biomedical informatics. Most of the existing multi-task sparse feature learning algorithms are formulated as a convex sparse regularization problem, which is usually suboptimal, due to its looseness for approximating an $\ell_0$-type regularizer. In this paper, we propose a non-convex formulation for multi-task sparse feature learning based on a novel regularizer. To solve the non-convex optimization problem, we propose a Multi-Stage Multi-Task Feature Learning (MSMTFL) algorithm. Moreover, we present a detailed theoretical analysis showing that MSMTFL achieves a better parameter estimation error bound than the convex formulation. Empirical studies on both synthetic and real-world data sets demonstrate the effectiveness of MSMTFL in comparison with the state of the art multi-task sparse feature learning algorithms.
Fast Resampling Weighted v-Statistics
Authors: Jiseong Park, Yun Fu Chunxiao Zhou
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: In this paper, a novel, computationally fast, and alternative algorithm for com- puting weighted v-statistics in resampling both univariate and multivariate data is proposed. To avoid any real resampling, we have linked this problem with finite group action and converted it into a problem of orbit enumeration. For further computational cost reduction, an efficient method is developed to list all orbits by their symmetry order and calculate all index function orbit sums and data function orbit sums recursively. The computational complexity analysis shows reduction in the computational cost from n! or nn level to low-order polynomial level.
Rational inference of relative preferences
Authors: Paul R. Schrater Nisheeth Srivastava
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Statistical decision theory axiomatically assumes that the relative desirability of different options that humans perceive is well described by assigning them option-specific scalar utility functions. However, this assumption is refuted by observed human behavior, including studies wherein preferences have been shown to change systematically simply through variation in the set of choice options presented. In this paper, we show that interpreting desirability as a relative comparison between available options at any particular decision instance results in a rational theory of value-inference that explains heretofore intractable violations of rational choice behavior in human subjects. Complementarily, we also characterize the conditions under which a rational agent selecting optimal options indicated by dynamic value inference in our framework will behave identically to one whose preferences are encoded using a static ordinal utility function.
Latent Graphical Model Selection: Efficient Methods for Locally Tree-like Graphs
Authors: Ragupathyraj Valluvan Anima Anandkumar
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Graphical model selection refers to the problem of estimating the unknown graph structure given observations at the nodes in the model. We consider a challenging instance of this problem when some of the nodes are latent or hidden.  We  characterize  conditions for tractable graph estimation and develop efficient methods with provable guarantees. We consider the class of Ising models Markov on  locally tree-like graphs, which are in the regime of correlation decay. We  propose an efficient method for graph estimation, and establish its structural consistency when the number of samples $n$ scales as $n = \Omega(\theta_{\min}^{-\delta \eta(\eta+1)-2}\log p)$, where $\theta_{\min}$ is the minimum edge potential, $\delta$ is the depth (i.e., distance from a hidden node to the nearest  observed nodes), and $\eta$ is a parameter which depends on the minimum and maximum node and edge potentials in the Ising model. The proposed method is practical to implement and provides  flexibility to control  the number of latent variables and the cycle lengths in the output graph.  We also present necessary conditions for graph estimation by any method and show that our method nearly matches the lower bound  on sample requirements.
On the connections between saliency and tracking
Authors: Nuno Vasconcelos Vijay Mahadevan
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: A model connecting visual tracking and saliency has recently been proposed. This model is based on the saliency hypothesis for tracking which postulates that tracking is achieved by the top-down tuning, based on target features, of discriminant center-surround saliency mechanisms over time. In this work, we identify three main predictions that must hold if the hypothesis were true: 1) tracking reliability should be larger for salient than for non-salient targets, 2) tracking reliability should have a dependence on the defining variables of saliency, namely feature contrast and distractor heterogeneity, and must replicate the dependence of saliency on these variables, and 3) saliency and tracking can be implemented with common low level neural mechanisms. We confirm that the first two predictions hold by reporting results from a set of human behavior studies on the connection between saliency and tracking. We also show that the third prediction holds by constructing a common neurophysiologically plausible architecture that can computationally solve both saliency and tracking. This architecture is fully compliant with the standard physiological models of V1 and MT, and with what is known about attentional control in area LIP, while explaining the results of the human behavior experiments.
Symbolic Dynamic Programming for Continuous State and Observation POMDPs
Authors: Scott Sanner, Pascal Poupart, Kristian Kersting Zahra Zamani
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Partially-observable Markov decision processes (POMDPs) provide a powerful model for real-world sequential decision-making problems. In recent years, point- based value iteration methods have proven to be extremely effective techniques for ﬁnding (approximately) optimal dynamic programming solutions to POMDPs when an initial set of belief states is known. However, no point-based work has provided exact point-based backups for both continuous state and observation spaces, which we tackle in this paper. Our key insight is that while there may be an inﬁnite number of possible observations, there are only a ﬁnite number of observation partitionings that are relevant for optimal decision-making when a ﬁnite, ﬁxed set of reachable belief states is known. To this end, we make two important contributions: (1) we show how previous exact symbolic dynamic pro- gramming solutions for continuous state MDPs can be generalized to continu- ous state POMDPs with discrete observations, and (2) we show how this solution can be further extended via recently developed symbolic methods to continuous state and observations to derive the minimal relevant observation partitioning for potentially correlated, multivariate observation spaces. We demonstrate proof-of- concept results on uni- and multi-variate state and observation steam plant control.
Imitation Learning by Coaching
Authors: Jason Eisner, Hal Daume He He
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Imitation Learning has been shown to be successful in solving many challenging real-world problems. Some recent approaches give strong performance guarantees by training the policy iteratively. However, it is important to note that these guarantees depend on   how well the policy we found can imitate the oracle on the training data.  When there is a substantial difference between the oracle's ability  and the learner's policy space, we may fail to find a policy that has low error on the training set. In such cases, we propose to use a coach that demonstrates easy-to-learn actions for the learner  and gradually approaches the oracle. By a reduction of learning by demonstration to online learning,  we prove that coaching can yield a lower regret bound than using the oracle. We apply our algorithm to a novel cost-sensitive dynamic feature selection problem, a hard decision problem that considers a user-specified accuracy-cost trade-off.  Experimental results on UCI datasets show that our method outperforms state-of-the-art imitation learning methods in dynamic features selection and two static feature selection methods.
Learning about Canonical Views from Internet Image Collections
Authors: Yair Weiss Elad Mezuman
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Although human object recognition is supposedly robust to viewpoint, much research on human perception indicates that there is a preferred or “canonical” view of objects. This phenomenon was discovered more than 30 years ago but the canonical view of only a small number of categories has been validated experimentally. Moreover, the explanation for why humans prefer the canonical view over other views remains elusive. In this paper we ask: Can we use Internet image collections to learn more about canonical views? We start by manually finding the most common view in the results returned by Internet search engines when queried with the objects used in psychophysical experiments. Our results clearly show that the most likely view in the search engine corresponds to the same view preferred by human subjects in experiments. We also present a simple method to find the most likely view in an image collection and apply it to hundreds of categories. Using the new data we have collected we present strong evidence against the two most prominent formal theories of canonical views and provide novel constraints for new theories.
A lattice filter model of the visual pathway
Authors: Dmitri B. Chklovskii Karol Gregor
Published in: Advances in Neural Information Processing Systems 25  (NIPS 2012) (Main Conference Track), 2012

Abstract: Early stages of visual processing are thought to decorrelate, or whiten, the incoming temporally varying signals. Because the typical correlation time of natural stimuli, as well as the extent of temporal receptive fields of lateral geniculate nucleus (LGN) neurons, is much greater than neuronal time constants, such decorrelation must be done in stages combining contributions of multiple neurons. We propose to model temporal decorrelation in the visual pathway with the lattice filter, a signal processing device for stage-wise decorrelation of temporal signals. The stage-wise architecture of the lattice filter maps naturally onto the visual pathway (photoreceptors -> bipolar cells -> retinal ganglion cells -> LGN) and its filter weights can be learned using Hebbian rules in a stage-wise sequential manner. Moreover, predictions of neural activity from the lattice filter model are consistent with physiological measurements in LGN neurons and fruit fly second-order visual neurons. Therefore, the lattice filter model is a useful abstraction that may help unravel visual system function.