pwc-archive/papers-with-abstracts huggingface dataset:
Multiclass Learning with Simplex Coding
Authors: Youssef Mroueh, Tomaso Poggio, Lorenzo Rosasco, Jean-Jeacques Slotine
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Binary Classification, General Classification

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.
FastEx: Hash Clustering with Exponential Families
Authors: Amr Ahmed, Sujith Ravi, Alex J. Smola, Shravan M. Narayanamurthy
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Clustering

Clustering is a key component in data analysis toolbox. Despite its   importance, scalable algorithms often eschew rich statistical models   in favor of simpler descriptions such as $k$-means clustering. In   this paper we present a sampler, capable of estimating   mixtures of exponential families. At its heart lies a novel proposal distribution using random   projections to achieve high throughput in generating proposals, which is crucial   for clustering models with large numbers of clusters.
Topic-Partitioned Multinetwork Embeddings
Authors: Peter Krafft, Juston Moore, Bruce Desmarais, Hanna M. Wallach
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Descriptive, Link Prediction

We introduce a joint model of network content and context designed for exploratory analysis of email networks via visualization of topic-specific communication patterns. Our model is an admixture model for text and network attributes which uses multinomial distributions over words as mixture components for explaining text and latent Euclidean positions of actors as mixture components for explaining network attributes.  We validate the appropriateness of our model by achieving state-of-the-art performance on a link prediction task and by achieving semantic coherence equivalent to that of latent Dirichlet allocation. We demonstrate the capability of our model for descriptive, explanatory, and exploratory analysis by investigating the inferred topic-specific communication patterns of a new government email dataset, the New Hanover County email corpus.
Learning Label Trees for Probabilistic Modelling of Implicit Feedback
Authors: Andriy Mnih, Yee W. Teh
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Collaborative Filtering

User preferences for items can be inferred from either explicit feedback, such as item ratings, or implicit feedback, such as rental histories. Research in collaborative filtering has concentrated on explicit feedback, resulting in the development of accurate and scalable models. However, since explicit feedback is often difficult to collect it is important to develop effective models that take advantage of the more widely available implicit feedback. We introduce a probabilistic approach to collaborative filtering with implicit feedback based on modelling the user's item selection process. In the interests of scalability, we restrict our attention to tree-structured distributions over items and develop a principled and efficient algorithm for learning item trees from data. We also identify a problem with a widely used protocol for evaluating implicit feedback models and propose a way of addressing it using a small quantity of explicit feedback data.
Learning with Recursive Perceptual Representations
Authors: Oriol Vinyals, Yangqing Jia, Li Deng, Trevor Darrell
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Image Classification, Object Recognition

Linear Support Vector Machines (SVMs) have become very popular in vision as part of state-of-the-art object recognition and other classification tasks but require high dimensional feature spaces for good performance. Deep learning methods can find more compact representations but current methods employ multilayer perceptrons that require solving a difficult, non-convex optimization problem. We propose a deep non-linear classifier whose layers are SVMs and which incorporates random projection as its core stacking element. Our method learns layers of linear SVMs recursively transforming the original data manifold through a random projection of the weak prediction computed from each layer. Our method scales as linear SVMs, does not rely on any kernel computations or nonconvex optimization, and exhibits better generalization ability than kernel-based SVMs. This is especially true when the number of training samples is smaller than the dimensionality of data, a common scenario in many real-world applications. The use of random projections is key to our method, as we show in the experiments section, in which we observe a consistent improvement over previous --often more complicated-- methods on several vision and speech benchmarks.
Link Prediction in Graphs with Autoregressive Features
Authors: Emile Richard, Stephane Gaiffas, Nicolas Vayatis
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Link Prediction, Prediction

In the paper, we consider the problem of link prediction in time-evolving graphs. We assume that certain graph features, such as the node degree, follow a vector autoregressive (VAR) model and we propose to use this information to improve the accuracy of prediction. Our strategy involves a joint optimization procedure over the space of adjacency matrices and VAR matrices which takes into account both sparsity and low rank properties of the matrices. Oracle inequalities are derived and illustrate the trade-offs in the choice of smoothing parameters when modeling the joint effect of sparsity and low rank property. The estimate is computed efficiently using proximal methods through a generalized forward-backward agorithm.
Deep Neural Networks Segment Neuronal Membranes in Electron Microscopy Images
Authors: Dan Ciresan, Alessandro Giusti, Luca M. Gambardella, Jürgen Schmidhuber
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

We address a central problem of neuroanatomy, namely, the automatic segmentation of neuronal structures  depicted in stacks of electron microscopy (EM) images. This is necessary to efficiently map 3D brain structure and connectivity. To segment {\em biological} neuron membranes, we use a special type of deep {\em artificial} neural network as a pixel classifier. The label of each pixel (membrane or non-membrane) is predicted from raw pixel values in a square window centered on it. The input layer maps each window pixel to a neuron. It is followed by a succession of convolutional and max-pooling layers which preserve 2D information and extract features with increasing levels of abstraction. The output layer produces a calibrated probability for each class. The classifier is trained by plain gradient descent on a $512 \times 512 \times 30$ stack with known ground truth, and tested on a stack of the same  size (ground truth unknown to the authors) by the organizers of the ISBI 2012 EM Segmentation Challenge.  Even without problem-specific post-processing, our approach outperforms competing techniques by a large margin in all three considered metrics, i.e. \emph{rand error}, \emph{warping error} and \emph{pixel error}.  For pixel error, our approach is the only one outperforming a second human observer.
Scalable imputation of genetic data with a discrete fragmentation-coagulation process
Authors: Lloyd Elliott, Yee W. Teh
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Computational Efficiency, Imputation

We present a Bayesian nonparametric model for genetic sequence data in which a set of genetic sequences is modelled using a Markov model of  partitions. The partitions at consecutive locations in the genome are related by their clusters first splitting and then merging.  Our model can be thought of as a discrete time analogue of continuous time fragmentation-coagulation processes [Teh et al 2011], preserving the important properties of projectivity, exchangeability and reversibility, while being more scalable. We apply this model to the problem of genotype imputation, showing improved computational efficiency while maintaining the same accuracies as in [Teh et al 2011].
Gradient Weights help Nonparametric Regressors
Authors: Samory Kpotufe, Abdeslam Boularias
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: regression

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.
Sparse Approximate Manifolds for Differential Geometric MCMC
Authors: Ben Calderhead, Mátyás A. Sustik
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Computational Efficiency, valid

One of the enduring challenges in Markov chain Monte Carlo methodology is the development of proposal mechanisms to make moves distant from the current point, that are accepted with high probability and at low computational cost. The recent introduction of locally adaptive MCMC methods based on the natural underlying Riemannian geometry of such models goes some way to alleviating these problems for certain classes of models for which the metric tensor is analytically tractable, however computational efficiency is not assured due to the necessity of potentially high-dimensional matrix operations at each iteration. In this paper we firstly investigate a sampling-based approach for approximating the metric tensor and suggest a valid MCMC algorithm that extends the applicability of Riemannian Manifold MCMC methods to statistical models that do not admit an analytically computable metric tensor. Secondly, we show how the approximation scheme we consider naturally motivates the use of l1 regularisation to improve estimates and obtain a sparse approximate inverse of the metric, which enables stable and sparse approximations of the local geometry to be made. We demonstrate the application of this algorithm for inferring the parameters of a realistic system of ordinary differential equations using a biologically motivated robust student-t error model, for which the expected Fisher Information is analytically intractable.
Fast Variational Inference in the Conjugate Exponential Family
Authors: James Hensman, Magnus Rattray, Neil D. Lawrence
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Variational Inference

We present a general method for deriving collapsed variational inference algorithms for probabilistic models in the conjugate exponential family. Our method unifies many existing approaches to collapsed variational inference. Our collapsed variational inference leads to a new lower bound on the marginal likelihood. We exploit the information geometry of the bound to derive much faster optimization methods based on conjugate gradients for these models. Our approach is very general and is easily applied to any model where the mean field update equations have been derived. Empirically we show significant speed-ups for probabilistic models optimized using our bound.
Bayesian Pedigree Analysis using Measure Factorization
Authors: Bonnie Kirkpatrick, Alexandre Bouchard-Côté
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Pedigrees, or family trees, are directed graphs used to identify sites of the genome that are correlated with the presence or absence of a disease.  With the advent of genotyping and sequencing technologies, there has been an explosion in the amount of data available, both in the number of individuals and in the number of sites.  Some pedigrees number in the thousands of individuals.  Meanwhile, analysis methods have remained limited to pedigrees of <100 individuals which limits analyses to many small independent pedigrees.  Disease models, such those used for the linkage analysis log-odds (LOD) estimator, have similarly been limited.  This is because linkage anlysis was originally designed with a different task in mind, that of ordering the sites in the genome, before there were technologies that could reveal the order.  LODs are difficult to interpret and nontrivial to extend to consider interactions among sites.  These developments and difficulties call for the creation of modern methods of pedigree analysis.  Drawing from recent advances in graphical model inference and transducer theory, we introduce a simple yet powerful formalism for expressing genetic disease models.   We show that these disease models can be turned into accurate and efficient estimators.  The technique we use for constructing the variational approximation has potential applications to inference in other large-scale graphical models.  This method allows inference on larger pedigrees than previously analyzed in the literature, which improves disease site prediction.
Accelerated Training for Matrix-norm Regularization: A Boosting Approach
Authors: Xinhua Zhang, Dale Schuurmans, Yao-Liang Yu
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Multiview Learning, Sparse Learning

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.
Controlled Recognition Bounds for Visual Learning and Exploration
Authors: Vasiliy Karasev, Alessandro Chiuso, Stefano Soatto
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

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).
Distributed Probabilistic Learning for Camera Networks with Missing Data
Authors: Sejong Yoon, Vladimir Pavlovic
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

Probabilistic approaches to computer vision typically assume a centralized setting, with the algorithm granted access to all observed data points.  However, many problems in wide-area surveillance can benefit from distributed modeling, either because of physical or computational constraints.  Most distributed models to date use algebraic approaches (such as distributed SVD) and as a result cannot explicitly deal with missing data.  In this work we present an approach to estimation and learning of generative probabilistic models in a distributed context where certain sensor data can be missing.  In particular, we show how traditional centralized models, such as probabilistic PCA and missing-data PPCA, can be learned when the data is distributed across a network of sensors.  We demonstrate the utility of this approach on the problem of distributed affine structure from motion.  Our experiments suggest that the accuracy of the learned probabilistic structure and motion models rivals that of traditional centralized factorization methods while being able to handle challenging situations such as missing or noisy observations.
Minimizing Uncertainty in Pipelines
Authors: Nilesh Dalvi, Aditya Parameswaran, Vibhor Rastogi
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12

In this paper, we consider the problem of debugging large pipelines by human labeling. We represent the execution of a pipeline using a directed acyclic graph of AND and OR nodes, where each node represents a data item produced by some operator in the pipeline. We assume that each operator assigns a confidence to each of its output data. We want to reduce the uncertainty in the output by issuing queries to a human expert, where a query consists of checking if a given data item is correct. In this paper, we consider the problem of asking the optimal set of queries to minimize the resulting output uncertainty. We perform a detailed evaluation of the complexity of the problem for various classes of graphs. We give efficient algorithms for the problem for trees, and show that, for a general dag, the problem is intractable.
Forging The Graphs: A Low Rank and Positive Semidefinite Graph Learning Approach
Authors: Dijun Luo, Heng Huang, Feiping Nie, Chris H. Ding
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: BIG-bench Machine Learning, Clustering, Graph Learning

In many graph-based machine learning and data mining approaches, the quality of the graph is critical. However, in real-world applications, especially in semi-supervised learning and unsupervised learning, the evaluation of the quality of a graph is often expensive and sometimes even impossible, due the cost or the unavailability of ground truth. In this paper, we proposed a robust approach with convex optimization to ``forge'' a graph: with an input of a graph, to learn a graph with higher quality. Our major concern is that an ideal graph shall satisfy all the following constraints: non-negative, symmetric, low rank, and positive semidefinite. We develop a graph learning algorithm by solving a convex optimization problem and further develop an efficient optimization to obtain global optimal solutions with theoretical guarantees. With only one non-sensitive parameter, our method is shown by experimental results to be robust and achieve higher accuracy in semi-supervised learning and clustering under various settings. As a preprocessing of graphs, our method has a wide range of potential applications machine learning and data mining.
The Time-Marginalized Coalescent Prior for Hierarchical Clustering
Authors: Levi Boyles, Max Welling
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Clustering, Density Estimation

We introduce a new prior for use in Nonparametric Bayesian Hierarchical Clustering. The prior is constructed by marginalizing out the time information of Kingman’s coalescent, providing a prior over tree structures which we call the Time-Marginalized Coalescent (TMC). This allows for models which factorize the tree structure and times, providing two benefits: more flexible priors may be constructed and more efficient Gibbs type inference can be used. We demonstrate this on an example model for density estimation and show the TMC achieves competitive experimental results.
Fusion with Diffusion for Robust Visual Tracking
Authors: Yu Zhou, Xiang Bai, Wenyu Liu, Longin J. Latecki
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Clustering, Visual Tracking

A weighted graph is used as an underlying structure of many algorithms like semi-supervised learning and spectral clustering. The edge weights are usually deter-mined by a single similarity measure, but it often hard if not impossible to capture all relevant aspects of similarity when using a single similarity measure. In par-ticular, in the case of visual object matching it is beneficial to integrate different similarity measures that focus on different visual representations. In this paper, a novel approach to integrate multiple similarity measures is pro-posed. First pairs of similarity measures are combined with a diffusion process on their tensor product graph (TPG). Hence the diffused similarity of each pair of ob-jects becomes a function of joint diffusion of the two original similarities, which in turn depends on the neighborhood structure of the TPG. We call this process Fusion with Diffusion (FD). However, a higher order graph like the TPG usually means significant increase in time complexity. This is not the case in the proposed approach. A key feature of our approach is that the time complexity of the dif-fusion on the TPG is the same as the diffusion process on each of the original graphs, Moreover, it is not necessary to explicitly construct the TPG in our frame-work. Finally all diffused pairs of similarity measures are combined as a weighted sum. We demonstrate the advantages of the proposed approach on the task of visual tracking, where different aspects of the appearance similarity between the target object in frame t and target object candidates in frame t+1 are integrated. The obtained method is tested on several challenge video sequences and the experimental results show that it outperforms state-of-the-art tracking methods.
A nonparametric variable clustering model
Authors: Konstantina Palla, Zoubin Ghahramani, David A. Knowles
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Clustering, model

Factor analysis models effectively summarise the covariance structure of high dimensional data, but the solutions are typically hard to interpret. This motivates attempting to find a disjoint partition, i.e. a clustering, of observed variables so that variables in a cluster are highly correlated. We introduce a Bayesian non-parametric approach to this problem, and demonstrate advantages over heuristic methods proposed to date.
Priors for Diversity in Generative Latent Variable Models
Authors: James T. Kwok, Ryan P. Adams
Date: 2012-12-01 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: Diversity

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