pwc-archive/papers-with-abstracts huggingface dataset:
A Denoising View of Matrix Completion
Authors: Weiran Wang, Miguel Á. Carreira-Perpiñán, Zhengdong Lu
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Denoising, Matrix Completion

In matrix completion, we are given a matrix where the values of only some of the entries are present, and we want to reconstruct the missing ones. Much work has focused on the assumption that the data matrix has low rank. We propose a more general assumption based on denoising, so that we expect that the value of a missing entry can be predicted from the values of neighboring points. We propose a nonparametric version of denoising based on local, iterated averaging with mean-shift, possibly constrained to preserve local low-rank manifold structure. The few user parameters required (the denoising scale, number of neighbors and local dimensionality) and the number of iterations can be estimated by cross-validating the reconstruction error. Using our algorithms as a postprocessing step on an initial reconstruction (provided by e.g. a low-rank method), we show consistent improvements with synthetic, image and motion-capture data.
Efficient Online Learning via Randomized Rounding
Authors: Nicolò Cesa-Bianchi, Ohad Shamir
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: BIG-bench Machine Learning, Collaborative Filtering, Open-Ended Question Answering

Most online algorithms used in machine learning today are based on variants of mirror descent or follow-the-leader. In this paper, we present an online algorithm based on a completely different approach, which combines ``random playout'' and randomized rounding of loss subgradients. As an application of our approach, we provide the first computationally efficient online algorithm for collaborative filtering with trace-norm constrained matrices. As a second application, we solve an open question linking batch learning and transductive online learning.
Efficient Methods for Overlapping Group Lasso
Authors: Lei Yuan, Jun Liu, Jieping Ye
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: feature selection

The group Lasso is an extension of the Lasso for feature selection on (predefined) non-overlapping groups of features. The non-overlapping group structure limits its applicability in practice. There have been several recent attempts to study a more general formulation, where groups of features are given, potentially with overlaps between the groups. The resulting optimization is, however, much more challenging to solve due to the group overlaps. In this paper, we consider the efficient optimization of the overlapping group Lasso penalized problem. We reveal several key properties of the proximal operator associated with the overlapping group Lasso, and compute the proximal operator by solving the smooth and convex dual problem, which allows the use of the gradient descent type of algorithms for the optimization. We have performed empirical evaluations using both synthetic and the breast cancer gene expression data set, which consists of 8,141 genes organized into (overlapping) gene sets. Experimental results show that the proposed algorithm is more efficient than existing state-of-the-art algorithms.
Differentially Private M-Estimators
Authors: Jing Lei
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Privacy Preserving

This paper studies privacy preserving M-estimators using perturbed histograms. The proposed approach allows the release of a  wide class of M-estimators with both differential privacy and statistical utility without knowing a priori the particular inference procedure. The performance of the proposed method is demonstrated through a careful study of the convergence rates. A practical algorithm is given and applied on a real world data set containing both continuous and categorical  variables.
Multiple Instance Filtering
Authors: Kamil A. Wnuk, Stefano Soatto
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Multiple Instance Learning, Visual Tracking

We propose a robust filtering approach based on semi-supervised and multiple instance learning (MIL). We assume that the posterior density would be unimodal if not for the effect of outliers that we do not wish to explicitly model. Therefore, we seek for a point estimate at the outset, rather than a generic approximation of the entire posterior. Our approach can be thought of as a combination of standard finite-dimensional filtering (Extended Kalman Filter, or Unscented Filter) with multiple instance learning, whereby the initial condition comes with a putative set of inlier measurements. We show how both the state (regression) and the inlier set (classification) can be estimated iteratively and causally by processing only the current measurement. We illustrate our approach on visual tracking problems whereby the object of interest (target) moves and evolves as a result of occlusions and deformations, and partial knowledge of the target is given in the form of a bounding box (training set).
Phase transition in the family of p-resistances
Authors: Morteza Alamgir, Ulrike V. Luxburg
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We study the family of p-resistances on graphs for p ≥ 1. This family generalizes the standard resistance distance. We prove that for any fixed graph, for p=1, the p-resistance coincides with the shortest path distance, for p=2 it coincides with the standard resistance distance, and for p → ∞ it converges to the inverse of the minimal s-t-cut in the graph. Secondly, we consider the special case of random geometric graphs (such as k-nearest neighbor graphs) when the number n of vertices in the graph tends to infinity. We prove that an interesting phase-transition takes place. There exist two critical thresholds p^* and p^** such that if p < p^*, then the p-resistance depends on meaningful global properties of the graph, whereas if p > p^**, it only depends on trivial local quantities and does not convey any useful information. We can explicitly compute the critical values: p^* = 1 + 1/(d-1) and p^** = 1 + 1/(d-2) where d is the dimension of the underlying space (we believe that the fact that there is a small gap between p^* and p^** is an artifact of our proofs. We also relate our findings to Laplacian regularization and suggest to use q-Laplacians as regularizers, where q satisfies 1/p^* + 1/q = 1.
Convergent Bounds on the Euclidean Distance
Authors: Yoonho Hwang, Hee-Kap Ahn
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Given a set V of n vectors in d-dimensional space, we provide an efficient method  for computing quality upper and lower bounds of the Euclidean distances between  a pair of the vectors in V . For this purpose, we define a distance measure, called  the MS-distance, by using the mean and the standard deviation values of vectors in  V . Once we compute the mean and the standard deviation values of vectors in V in  O(dn) time, the MS-distance between them provides upper and lower bounds of  Euclidean distance between a pair of vectors in V in constant time. Furthermore,  these bounds can be refined further such that they converge monotonically to the  exact Euclidean distance within d refinement steps. We also provide an analysis on  a random sequence of refinement steps which can justify why MS-distance should  be refined to provide very tight bounds in a few steps of a typical sequence. The  MS-distance can be used to various problems where the Euclidean distance is used  to measure the proximity or similarity between objects. We provide experimental  results on the nearest and the farthest neighbor searches.
Heavy-tailed Distances for Gradient Based Image Descriptors
Authors: Yangqing Jia, Trevor Darrell
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Many applications in computer vision measure the similarity between images or image patches based on some statistics such as oriented gradients. These are often modeled implicitly or explicitly with a Gaussian noise assumption, leading to the use of the Euclidean distance when comparing image descriptors. In this paper, we show that the statistics of gradient based image descriptors often follow a heavy-tailed distribution, which undermines any principled motivation for the use of Euclidean distances. We advocate for the use of a distance measure based on the likelihood ratio test with appropriate probabilistic models that fit the empirical data distribution. We instantiate this similarity measure with the Gamma-compound-Laplace distribution, and show significant improvement over existing distance measures in the application of SIFT feature matching, at relatively low computational cost.
RTRMC: A Riemannian trust-region method for low-rank matrix completion
Authors: Nicolas Boumal, Pierre-Antoine Absil
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Low-Rank Matrix Completion, Matrix Completion, Recommendation Systems

We consider large matrices of low rank. We address the problem of recovering such matrices when most of the entries are unknown. Matrix completion finds applications in recommender systems. In this setting, the rows of the matrix may correspond to items and the columns may correspond to users. The known entries are the ratings given by users to some items. The aim is to predict the unobserved ratings. This problem is commonly stated in a constrained optimization framework. We follow an approach that exploits the geometry of the low-rank constraint to recast the problem as an unconstrained optimization problem on the Grassmann manifold. We then apply first- and second-order Riemannian trust-region methods to solve it. The cost of each iteration is linear in the number of known entries. Our methods, RTRMC 1 and 2, outperform state-of-the-art algorithms on a wide range of problem instances.
History distribution matching method for predicting effectiveness of HIV combination therapies
Authors: Jasmina Bogojeska
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

This paper presents an approach that predicts the effectiveness of HIV combination therapies by simultaneously addressing several problems affecting the available HIV clinical data sets: the different treatment backgrounds of the samples, the uneven representation of the levels of therapy experience, the missing treatment history information, the uneven therapy representation and the unbalanced therapy outcome representation. The computational validation on clinical data shows that, compared to the most commonly used approach that does not account for the issues mentioned above, our model has significantly higher predictive power. This is especially true for samples stemming from patients with longer treatment history and samples associated with rare therapies. Furthermore, our approach is at least as powerful for the remaining samples.
Semi-supervised Regression via Parallel Field Regularization
Authors: Binbin Lin, Chiyuan Zhang, Xiaofei He
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: regression

This paper studies the problem of semi-supervised learning from the vector field perspective. Many of the existing work use the graph Laplacian to ensure the smoothness of the prediction function on the data manifold. However, beyond smoothness, it is suggested by recent theoretical work that we should ensure second order smoothness for achieving faster rates of convergence for semi-supervised regression problems. To achieve this goal, we show that the second order smoothness measures the linearity of the function, and the gradient field of a linear function has to be a parallel vector field. Consequently, we propose to find a function which minimizes the empirical error, and simultaneously requires its gradient field to be as parallel as possible. We give a continuous objective function on the manifold and discuss how to discretize it by using random points. The discretized optimization problem turns out to be a sparse linear system which can be solved very efficiently. The experimental results have demonstrated the effectiveness of our proposed approach.
Object Detection with Grammar Models
Authors: Ross B. Girshick, Pedro F. Felzenszwalb, David A. Mcallester
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Human Detection, Object, object-detection, Object Detection, Structured Prediction

Compositional models provide an elegant formalism for representing the  visual appearance of highly variable objects.  While such models are  appealing from a theoretical point of view, it has been difficult to  demonstrate that they lead to performance advantages on challenging  datasets.  Here we develop a grammar model for person detection  and show that it outperforms previous high-performance systems on the  PASCAL benchmark.  Our model represents people using a hierarchy of  deformable parts, variable structure and an explicit model of  occlusion for partially visible objects.  To train the model, we  introduce a new discriminative framework for learning structured  prediction models from weakly-labeled data.
Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning
Authors: Eric Moulines, Francis R. Bach
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: BIG-bench Machine Learning, regression

We consider the minimization of a convex objective function defined on a Hilbert space, which is only available through unbiased estimates of  its gradients.  This problem includes  standard machine learning algorithms such as kernel logistic regression and least-squares regression, and is commonly referred to as a stochastic approximation problem in the operations research community. We provide a non-asymptotic analysis of the  convergence of two well-known algorithms, stochastic gradient descent (a.k.a.~Robbins-Monro algorithm) as well as a simple modification where iterates are averaged (a.k.a.~Polyak-Ruppert averaging). Our analysis suggests that a learning rate proportional to the inverse of the number of iterations, while leading to the optimal convergence rate in the strongly convex case, is not robust to the lack of strong convexity or the setting of the proportionality constant. This situation is remedied when using slower decays together with averaging, robustly leading to the optimal rate of convergence. We illustrate our theoretical results with simulations on synthetic and standard datasets.
On fast approximate submodular minimization
Authors: Stefanie Jegelka, Hui Lin, Jeff A. Bilmes
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: BIG-bench Machine Learning

We are motivated by an application to extract a representative subset of machine learning training data and by the poor empirical performance we observe of the popular minimum norm algorithm. In fact, for our application, minimum norm can have a running time of about O(n^7 ) (O(n^5 ) oracle calls). We therefore propose a fast approximate method to minimize arbitrary submodular functions. For a large sub-class of submodular functions, the algorithm is exact. Other submodular functions are iteratively approximated by tight submodular upper bounds, and then repeatedly optimized. We show theoretical properties, and empirical results suggest significant speedups over minimum norm while retaining higher accuracies.
Emergence of Multiplication in a Biophysical Model of a Wide-Field Visual Neuron for Computing Object Approaches: Dynamics, Peaks, & Fits
Authors: Matthias S. Keil
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Many species show avoidance reactions in response to looming object approaches.  In locusts, the corresponding escape behavior correlates with the activity  of the lobula giant movement detector (LGMD) neuron.  During an object approach,  its firing rate was reported to gradually increase until a peak is reached,  and then it declines quickly.  The $\eta$-function predicts that the LGMD activity  is a product between an exponential function of angular size $\exp(-\Theta)$ and  angular velocity $\dot{\Theta}$, and that peak activity is reached before time-to-contact  (ttc).  The $\eta$-function has become the prevailing LGMD model because it  reproduces many experimental observations, and even experimental evidence for  the multiplicative operation was reported.  Several inconsistencies remain  unresolved, though.  Here we address these issues with a new model ($\psi$-model),  which explicitly connects $\Theta$ and $\dot{\Theta}$ to biophysical quantities.  The $\psi$-model avoids biophysical problems associated with implementing  $\exp(\cdot)$, implements the multiplicative operation of $\eta$ via divisive  inhibition, and explains why activity peaks could occur after ttc.  It consistently  predicts response features of the LGMD, and provides excellent fits to published  experimental data, with goodness of fit measures comparable to corresponding  fits with the $\eta$-function.
Efficient anomaly detection using bipartite k-NN graphs
Authors: Kumar Sricharan, Alfred O. Hero
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Anomaly Detection

Learning minimum volume sets of an underlying nominal distribution is a very effective approach to anomaly detection. Several approaches to learning minimum volume sets have been proposed in the literature, including the K-point nearest neighbor graph (K-kNNG) algorithm based on the geometric entropy minimization (GEM) principle [4]. The K-kNNG detector, while possessing several desirable characteristics, suffers from high computation complexity, and in [4] a simpler heuristic approximation, the leave-one-out kNNG (L1O-kNNG) was proposed. In this paper, we propose a novel bipartite k-nearest neighbor graph (BP-kNNG) anomaly detection scheme for estimating minimum volume sets. Our bipartite estimator retains all the desirable theoretical properties of the K-kNNG, while being computationally simpler than the K-kNNG and the surrogate L1O-kNNG detectors. We show that BP-kNNG is asymptotically consistent in recovering the p-value of each test point. Experimental results are given that illustrate the superior performance of BP-kNNG as compared to the L1O-kNNG and other state of the art anomaly detection schemes.
Projection onto A Nonnegative Max-Heap
Authors: Jun Liu, Liang Sun, Jieping Ye
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: regression

We consider the problem of computing the Euclidean projection of a vector of length $p$ onto a non-negative max-heap---an ordered tree where the values of the nodes are all nonnegative and the value of any parent node is no less than the value(s) of its child node(s). This Euclidean projection plays a building block role in the optimization problem with a non-negative max-heap constraint. Such a constraint is desirable when the features follow an ordered tree structure, that is, a given feature is selected for the given regression/classification task only if its parent node is selected. In this paper, we show that such Euclidean projection problem admits an analytical solution and we develop a top-down algorithm where the key operation is to find the so-called \emph{maximal root-tree} of the subtree rooted at each node. A naive approach for finding the maximal root-tree is to enumerate all the possible root-trees, which, however, does not scale well. We reveal several important properties of the maximal root-tree, based on which we design a bottom-up algorithm with merge for efficiently finding the maximal root-tree. The proposed algorithm has a (worst-case) linear time complexity for a sequential list, and $O(p^2)$ for a general tree. We report simulation results showing the effectiveness of the max-heap for regression with an ordered tree structure. Empirical results show that the proposed algorithm has an expected linear time complexity for many special cases including a sequential list, a full binary tree, and a tree with depth 1.
Improving Topic Coherence with Regularized Topic Models
Authors: David Newman, Edwin V. Bonilla, Wray Buntine
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Diversity, Retrieval, Topic Models

Topic models have the potential to improve search and browsing by extracting useful semantic themes from web pages and other text documents. When learned topics are coherent and interpretable, they can be valuable for faceted browsing, results set diversity analysis, and document retrieval. However, when dealing with small collections or noisy text (e.g. web search result snippets or blog posts), learned topics can be less coherent, less interpretable, and less useful. To overcome this, we propose two methods to regularize the learning of topic models. Our regularizers work by creating a structured prior over words that reflect broad patterns in the external data. Using thirteen datasets we show that both regularizers improve topic coherence and interpretability while learning a faithful representation of the collection of interest. Overall, this work makes topic models more useful across a broader range of text data.
A Two-Stage Weighting Framework for Multi-Source Domain Adaptation
Authors: Qian Sun, Rita Chattopadhyay, Sethuraman Panchanathan, Jieping Ye
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Domain Adaptation, Vocal Bursts Valence Prediction

Discriminative learning when training and test data belong to different distributions is a challenging and complex task. Often times we have very few or no labeled data from the test or target distribution but may have plenty of labeled data from multiple related sources with different distributions. The difference in distributions may be in both marginal and conditional probabilities. Most of the existing domain adaptation work focuses on the marginal  probability distribution difference between the domains, assuming that the conditional probabilities are similar. However in many real world applications, conditional probability distribution differences are as commonplace as marginal probability differences. In this paper we propose a two-stage domain adaptation methodology which combines weighted data from multiple sources based on marginal probability differences (first stage) as well as conditional probability differences (second stage), with the target domain data. The weights for minimizing the marginal probability differences are estimated independently, while the weights for minimizing conditional  probability differences are computed simultaneously by exploiting the potential interaction among multiple sources. We also provide a theoretical analysis on the generalization performance of the proposed multi-source domain adaptation formulation using the weighted Rademacher complexity measure. Empirical comparisons with existing state-of-the-art domain adaptation methods using three real-world datasets demonstrate the effectiveness of the proposed approach.
An ideal observer model for identifying the reference frame of objects
Authors: Joseph L. Austerweil, Abram L. Friesen, Thomas L. Griffiths
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

The object people perceive in an image can depend on its orientation relative to the scene it is in (its reference frame). For example, the images of the symbols $\times$ and $+$ differ by a 45 degree rotation. Although real scenes have multiple images and reference frames, psychologists have focused on scenes with only one reference frame. We propose an ideal observer model based on nonparametric Bayesian statistics for inferring the number of reference frames in a scene and their parameters. When an ambiguous image could be assigned to two conflicting reference frames, the model predicts two factors should influence the reference frame inferred for the image: The image should be more likely to share the reference frame of the closer object ({\em proximity}) and it should be more likely to share the reference frame containing the most objects ({\em alignment}). We confirm people use both cues using a novel methodology that allows for easy testing of human reference frame inference.