pwc-archive/papers-with-abstracts huggingface dataset:
Dynamic Pruning of Factor Graphs for Maximum Marginal Prediction
Authors: Christoph H. Lampert
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Image Inpainting, Multi-Label Classification, MUlTI-LABEL-ClASSIFICATION, Prediction

We study the problem of maximum marginal prediction (MMP) in probabilistic graphical models, a task that occurs, for example, as the Bayes optimal decision rule under a Hamming loss. MMP is typically performed as a two-stage procedure: one estimates each variable's marginal probability and then forms a prediction from the states of maximal probability. In this work we propose a simple yet effective technique for accelerating MMP when inference is sampling-based: instead of the above two-stage procedure we directly estimate the posterior probability of each decision variable. This allows us to identify the point of time when we are sufficiently certain about any individual decision. Whenever this is the case, we dynamically prune the variable we are confident about from the underlying factor graph. Consequently, at any time only samples of variable whose decision is still uncertain need to be created. Experiments in two prototypical scenarios, multi-label classification and image inpainting, shows that adaptive sampling can drastically accelerate MMP without sacrificing prediction accuracy.
Local Supervised Learning through Space Partitioning
Authors: Joseph Wang, Venkatesh Saligrama
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: General Classification

We develop a novel approach for supervised learning based on adaptively partitioning the feature space into different regions and learning local region-specific classifiers. We formulate an empirical risk minimization problem that incorporates both partitioning and classification in to a single global objective. We show that space partitioning can be equivalently reformulated as a supervised learning problem and consequently any discriminative learning method can be utilized in conjunction with our approach. Nevertheless, we consider locally linear schemes by learning linear partitions and linear region classifiers. Locally linear schemes can not only approximate complex decision boundaries and ensure low training error but also provide tight control on over-fitting and generalization error. We train locally linear classifiers by using LDA, logistic regression and perceptrons, and so our scheme is scalable to large data sizes and high-dimensions. We present experimental results demonstrating improved performance over state of the art classification techniques on benchmark datasets. We also show improved robustness to label noise.
A Generative Model for Parts-based Object Segmentation
Authors: S. Eslami, Christopher Williams
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: model, Object, Semantic Segmentation

The Shape Boltzmann Machine (SBM) has recently been introduced as a state-of-the-art model of foreground/background object shape. We extend the SBM to account for the foreground object's parts. Our model, the Multinomial SBM (MSBM), can capture both local and global statistics of part shapes accurately. We combine the MSBM with an appearance model to form a fully generative model of images of objects. Parts-based image segmentations are obtained simply by performing probabilistic inference in the model. We apply the model to two challenging datasets which exhibit significant shape and appearance variability, and find that it obtains results that are comparable to the state-of-the-art.
Super-Bit Locality-Sensitive Hashing
Authors: Jianqiu Ji, Jianmin Li, Shuicheng Yan, Bo Zhang, Qi Tian
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Dimensionality Reduction, Retrieval

Sign-random-projection locality-sensitive hashing (SRP-LSH) is a probabilistic dimension reduction method which provides an unbiased estimate of angular similarity, yet suffers from the large variance of its estimation. In this work, we propose the Super-Bit locality-sensitive hashing (SBLSH). It is easy to implement, which orthogonalizes the random projection vectors in batches, and it is theoretically guaranteed that SBLSH also provides an unbiased estimate of angular similarity, yet with a smaller variance when the angle to estimate is within $(0,\pi/2]$. The extensive experiments on real data well validate that given the same length of binary code, SBLSH may achieve significant mean squared error reduction in estimating pairwise angular similarity. Moreover, SBLSH shows the superiority over SRP-LSH in approximate nearest neighbor (ANN) retrieval experiments.
The Bethe Partition Function of Log-supermodular Graphical Models
Authors: Nicholas Ruozzi
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Sudderth, Wainwright, and Willsky conjectured that the Bethe approximation corresponding to any fixed point of the belief propagation algorithm over an attractive, pairwise binary graphical model provides a lower bound on the true partition function. In this work, we resolve this conjecture in the affirmative by demonstrating that, for any graphical model with binary variables whose potential functions (not necessarily pairwise) are all log-supermodular, the Bethe partition function always lower bounds the true partition function.  The proof of this result follows from a new variant of the “four functions” theorem that may be of independent interest.
Putting Bayes to sleep
Authors: Dmitry Adamskiy, Manfred K. Warmuth, Wouter M. Koolen
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

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.
A new metric on the manifold of kernel matrices with application to matrix geometric means
Authors: Suvrit Sra
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Symmetric positive definite (spd) matrices are remarkably pervasive in a multitude of scientific disciplines, including machine learning and optimization. We consider the fundamental task of measuring distances between two spd matrices; a task that is often nontrivial whenever an application demands the distance function to respect the non-Euclidean geometry of spd matrices. Unfortunately, typical non-Euclidean distance measures such as the Riemannian metric $\riem(X,Y)=\frob{\log(X\inv{Y})}$, are computationally demanding and also complicated to use. To allay some of these difficulties, we introduce a new metric on spd matrices: this metric not only respects non-Euclidean geometry, it also offers faster computation than $\riem$ while being less complicated to use. We support our claims theoretically via a series of theorems that relate our metric to $\riem(X,Y)$, and experimentally by studying the nonconvex problem of computing matrix geometric means based on squared distances.
Mandatory Leaf Node Prediction in Hierarchical Multilabel Classification
Authors: Wei Bi, James T. Kwok
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Classification, General Classification, Prediction

In hierarchical classification, the prediction paths may be required to always end at leaf nodes. This is called mandatory leaf node prediction (MLNP) and is particularly useful when the leaf nodes have much stronger semantic meaning than the internal nodes. However, while there have been a lot of MLNP methods in hierarchical multiclass classification, performing MLNP in hierarchical multilabel classification is much more difficult. In this paper, we propose a novel MLNP algorithm that (i) considers the global hierarchy structure; and (ii) can  be used on hierarchies of both trees and DAGs. We show that one can efficiently maximize the joint posterior probability of all the node labels by a simple greedy algorithm. Moreover, this can be further extended to the minimization of the expected symmetric loss. Experiments are performed on a number of real-world data sets with tree- and DAG-structured label hierarchies. The  proposed method consistently outperforms other hierarchical and flat multilabel classification methods.
Coding efficiency and detectability of rate fluctuations with non-Poisson neuronal firing
Authors: Shinsuke Koyama
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Statistical features of neuronal spike trains are known to be non-Poisson. Here, we investigate the extent to which the non-Poissonian feature affects the efficiency of transmitting information on fluctuating firing rates. For this purpose, we introduce the Kullbuck-Leibler (KL) divergence as a measure of the efficiency of information encoding, and assume that spike trains are generated by time-rescaled renewal processes. We show that the KL divergence determines the lower bound of the degree of rate fluctuations below which the temporal variation of the firing rates is undetectable from sparse data. We also show that the KL divergence, as well as the lower bound, depends not only on the variability of spikes in terms of the coefficient of variation, but also significantly on the higher-order moments of interspike interval (ISI) distributions. We examine three specific models that are commonly used for describing the stochastic nature of spikes (the gamma, inverse Gaussian (IG) and lognormal ISI distributions), and find that the time-rescaled renewal process with the IG distribution achieves the largest KL divergence, followed by the lognormal and gamma distributions.
The representer theorem for Hilbert spaces: a necessary and sufficient condition
Authors: Francesco Dinuzzo, Bernhard Schölkopf
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

The representer theorem is a property that lies at the foundation of regularization theory and kernel methods. A class of regularization functionals is said to admit a linear representer theorem if every member of the class admits minimizers that lie in the finite dimensional subspace spanned by the representers of the data. A recent characterization states that certain classes of regularization functionals with differentiable regularization term admit a linear representer theorem for any choice of the data if and only if the regularization term is a radial nondecreasing function. In this paper, we extend such result by weakening the assumptions on the regularization term. In particular, the main result of this paper implies that, for a sufficiently large family of regularization functionals, radial nondecreasing functions are the only lower semicontinuous regularization terms that guarantee existence of a representer theorem for any choice of the data.
Exploration in Model-based Reinforcement Learning by Empirically Estimating Learning Progress
Authors: Manuel Lopes, Tobias Lang, Marc Toussaint, Pierre-Yves Oudeyer
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Model-based Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Formal exploration approaches in model-based reinforcement learning estimate the accuracy of the currently learned model without consideration of the empirical prediction error. For example, PAC-MDP approaches such as Rmax base their model certainty on the amount of collected data, while Bayesian approaches assume a prior over the transition dynamics. We propose extensions to such approaches which drive exploration solely based on empirical estimates of the learner's accuracy and learning progress. We provide a ``sanity check'' theoretical analysis, discussing the behavior of our extensions in the standard stationary finite state-action case. We then provide experimental studies demonstrating the robustness of these exploration measures in cases of non-stationary environments or where original approaches are misled by wrong domain assumptions.
Supervised Learning with Similarity Functions
Authors: Purushottam Kar, Prateek Jain
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: General Classification, regression

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.
Cocktail Party Processing via Structured Prediction
Authors: Yuxuan Wang, DeLiang Wang
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: General Classification, Prediction, Speech Separation, Structured Prediction

While human listeners excel at selectively attending to a conversation in a cocktail party, machine performance is still far inferior by comparison. We show that the cocktail party problem, or the speech separation problem, can be effectively approached via structured prediction. To account for temporal dynamics in speech, we employ conditional random fields (CRFs) to classify speech dominance within each time-frequency unit for a sound mixture. To capture complex, nonlinear relationship between input and output, both state and transition feature functions in CRFs are learned by deep neural networks. The formulation of the problem as classification allows us to directly optimize a measure that is well correlated with human speech intelligibility. The proposed system substantially outperforms existing ones in a variety of noises.
Robustness and risk-sensitivity in Markov decision processes
Authors: Takayuki Osogami
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Sensitivity

We uncover relations between robust MDPs and risk-sensitive MDPs.  The objective of a robust MDP is to minimize a function, such as the expectation of cumulative cost, for the worst case when the parameters have uncertainties.  The objective of a risk-sensitive MDP is to minimize a risk measure of the cumulative cost when the parameters are known.  We show that a risk-sensitive MDP of minimizing the expected exponential utility is equivalent to a robust MDP of minimizing the worst-case expectation with a penalty for the deviation of the uncertain parameters from their nominal values, which is measured with the Kullback-Leibler divergence.  We also show that a risk-sensitive MDP of minimizing an iterated risk measure that is composed of certain coherent risk measures is equivalent to a robust MDP of minimizing the worst-case expectation when the possible deviations of uncertain parameters from their nominal values are characterized with a concave function.
Adaptive Stratified Sampling for Monte-Carlo integration of Differentiable functions
Authors: Alexandra Carpentier, Rémi Munos
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

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.
Distributed Non-Stochastic Experts
Authors: Varun Kanade, Zhenming Liu, Bozidar Radunovic
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We consider the online distributed non-stochastic experts problem, where the distributed system consists of one coordinator node that is connected to k sites, and the sites are required to communicate with each other via the coordinator. At each time-step t, one of the k site nodes has to pick an expert from the set {1, . . . , n}, and the same site receives information about payoffs of all experts for that round. The goal of the distributed system is to minimize regret at time horizon T, while simultaneously keeping communication to a minimum. The two extreme solutions to this problem are: (i) Full communication: This essentially simulates the non-distributed setting to obtain the optimal O(\sqrt{log(n)T}) regret bound at the cost of T communication. (ii) No communication: Each site runs an independent copy – the regret is O(\sqrt{log(n)kT}) and the communication is 0. This paper shows the difficulty of simultaneously achieving regret asymptotically better than \sqrt{kT} and communication better than T. We give a novel algorithm that for an oblivious adversary achieves a non-trivial trade-off: regret O(\sqrt{k^{5(1+\epsilon)/6} T}) and communication O(T/k^\epsilon), for any value of \epsilon in (0, 1/5). We also consider a variant of the model, where the coordinator picks the expert. In this model, we show that the label-efficient forecaster of Cesa-Bianchi et al. (2005) already gives us strategy that is near optimal in regret vs communication trade-off.
Learning Image Descriptors with the Boosting-Trick
Authors: Tomasz Trzcinski, Mario Christoudias, Vincent Lepetit, Pascal Fua
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: object-detection, Object Detection

In this paper we  apply   boosting  to  learn   complex  non-linear  local   visual  feature representations, drawing  inspiration from its successful  application to visual object detection. The main  goal of  local feature descriptors  is to distinctively  represent a salient image  region while remaining invariant to  viewpoint and illumination changes. This representation can  be improved using machine learning, however, past approaches  have been mostly limited to learning  linear feature mappings in either the original input or a  kernelized input feature space.  While kernelized  methods have proven somewhat effective for learning non-linear local  feature descriptors,  they rely heavily  on the choice  of an appropriate kernel  function whose selection is often  difficult and non-intuitive. We propose  to use the boosting-trick  to  obtain a  non-linear  mapping  of  the input  to  a high-dimensional feature space. The non-linear feature mapping  obtained with the  boosting-trick is  highly intuitive. We employ gradient-based weak learners resulting in a learned descriptor that closely resembles the well-known SIFT. As demonstrated in our experiments, the resulting descriptor   can  be  learned   directly  from   intensity  patches  achieving state-of-the-art performance.
Fast Resampling Weighted v-Statistics
Authors: Chunxiao Zhou, Jiseong Park, Yun Fu
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

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.
Multi-task Vector Field Learning
Authors: Binbin Lin, Sen yang, Chiyuan Zhang, Jieping Ye, Xiaofei He
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Multi-Task Learning

Multi-task learning (MTL) aims to improve generalization performance by learning multiple related tasks simultaneously and identifying the shared information among tasks. Most of existing MTL methods focus on learning linear models under the supervised setting. We propose a novel semi-supervised and nonlinear approach for MTL using vector fields. A vector field is a smooth mapping from the manifold to the tangent spaces which can be viewed as a directional derivative of functions on the manifold. We argue that vector fields provide a natural way to exploit the geometric structure of data as well as the shared differential structure of tasks, both are crucial for semi-supervised multi-task learning. In this paper, we develop multi-task vector field learning (MTVFL) which learns the prediction functions and the vector fields simultaneously. MTVFL has the following key properties: (1) the vector fields we learned are close to the gradient fields of the prediction functions; (2) within each task, the vector field is required to be as parallel as possible which is expected to span a low dimensional subspace; (3) the vector fields from all tasks share a low dimensional subspace. We formalize our idea in a regularization framework and also provide a convex relaxation method to solve the original non-convex problem. The experimental results on synthetic and real data demonstrate the effectiveness of our proposed approach.
Nonparametric Bayesian Inverse Reinforcement Learning for Multiple Reward Functions
Authors: Jaedeug Choi, Kee-Eung Kim
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We present a nonparametric Bayesian approach to inverse reinforcement learning (IRL) for multiple reward functions. Most previous IRL algorithms assume that the behaviour data is obtained from an agent who is optimizing a single reward function, but this assumption is hard to be met in practice. Our approach is based on integrating the Dirichlet process mixture model into Bayesian IRL. We provide an efficient Metropolis-Hastings sampling algorithm utilizing the gradient of the posterior to estimate the underlying reward functions, and demonstrate that our approach outperforms the previous ones via experiments on a number of problem domains.