pwc-archive/papers-with-abstracts huggingface dataset:
Minimax Localization of Structural Information in Large Noisy Matrices
Authors: Mladen Kolar, Sivaraman Balakrishnan, Alessandro Rinaldo, Aarti Singh
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Clustering, Two-sample testing

We consider the problem of identifying a sparse set of relevant columns and rows in a large data matrix with highly corrupted entries. This problem of identifying groups from a collection of bipartite variables such as proteins and drugs, biological species and gene sequences, malware and signatures, etc is commonly referred to as biclustering or co-clustering. Despite its great practical relevance, and although several ad-hoc methods are available for biclustering, theoretical analysis of the problem is largely non-existent. The problem we consider is also closely related to structured multiple hypothesis testing, an area of statistics that has recently witnessed a flurry of activity. We make the following contributions: i) We prove lower bounds on the minimum signal strength needed for successful recovery of a bicluster as a function of the noise variance, size of the matrix and bicluster of interest. ii) We show that a combinatorial procedure based on the scan statistic achieves this optimal limit. iii) We characterize the SNR required by several computationally tractable procedures for biclustering including element-wise thresholding, column/row average thresholding and a convex relaxation approach to sparse singular vector decomposition.
Maximum Covariance Unfolding : Manifold Learning for Bimodal Data
Authors: Vijay Mahadevan, Chi W. Wong, Jose C. Pereira, Tom Liu, Nuno Vasconcelos, Lawrence K. Saul
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Cross-Modal Retrieval, Dimensionality Reduction, EEG, Electroencephalogram (EEG), Metric Learning, Retrieval

We propose maximum covariance unfolding (MCU), a manifold learning algorithm for simultaneous dimensionality reduction of data from different input modalities.   Given high dimensional inputs from two different but naturally aligned sources, MCU computes a common low dimensional embedding that maximizes the cross-modal (inter-source) correlations while preserving the local (intra-source) distances.  In this paper, we explore two applications of MCU.  First we use MCU to analyze EEG-fMRI data, where an important goal is to visualize the fMRI voxels that are most strongly correlated with changes in EEG traces.  To perform this visualization, we augment MCU with an additional step for metric learning in the high dimensional voxel space.  Second, we use MCU to perform cross-modal retrieval of matched image and text samples from Wikipedia.  To manage large applications of MCU, we develop a fast implementation based on ideas from spectral graph theory.  These ideas transform the original problem for MCU, one of semidefinite programming, into a simpler problem in semidefinite quadratic linear programming.
Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression
Authors: Sham M. Kakade, Varun Kanade, Ohad Shamir, Adam Kalai
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: regression

Generalized Linear Models (GLMs) and Single Index Models (SIMs) provide powerful generalizations of linear regression, where the target variable is assumed to be a (possibly unknown) 1-dimensional function of a linear predictor. In general, these problems entail non-convex estimation procedures, and, in practice, iterative local search heuristics are often used.  Kalai and Sastry (2009) provided the first provably efficient method, the \emph{Isotron} algorithm, for learning SIMs and GLMs, under the assumption that the data is in fact generated under a GLM and under certain monotonicity and Lipschitz (bounded slope) constraints. The Isotron algorithm interleaves steps of perceptron-like updates with isotonic regression (fitting a one-dimensional non-decreasing function). However, to obtain provable performance, the method requires a fresh sample every iteration. In this paper, we provide algorithms for learning GLMs and SIMs, which are both computationally and statistically efficient. We modify the isotonic regression step in Isotron to fit a Lipschitz monotonic function, and also provide an efficient $O(n \log(n))$ algorithm for this step, improving upon the previous $O(n^2)$ algorithm. We provide a brief empirical study, demonstrating the feasibility of our algorithms in practice.
On the Analysis of Multi-Channel Neural Spike Data
Authors: Bo Chen, David E. Carlson, Lawrence Carin
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Dictionary Learning, Spike Sorting

Nonparametric Bayesian methods are developed for analysis of multi-channel  spike-train data, with the feature learning and spike sorting performed jointly.  The feature learning and sorting are performed simultaneously across all channels.  Dictionary learning is implemented via the beta-Bernoulli process, with  spike sorting performed via the dynamic hierarchical Dirichlet process (dHDP),  with these two models coupled. The dHDP is augmented to eliminate refractoryperiod  violations, it allows the “appearance” and “disappearance” of neurons over  time, and it models smooth variation in the spike statistics.
Learning Eigenvectors for Free
Authors: Wouter M. Koolen, Wojciech Kotlowski, Manfred K. Warmuth
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We extend the classical problem of predicting a sequence  of outcomes from a finite alphabet to the matrix domain.   In this extension, the alphabet of $n$ outcomes is replaced by the set of all dyads, i.e.   outer products $\u\u^\top$ where $\u$ is a vector in $\R^n$ of unit length.  Whereas in the classical case the goal is to learn   (i.e. sequentially predict as well as) the best multinomial distribution,  in the matrix case we desire to learn the density matrix  that best explains the observed sequence of dyads. We show  how popular online algorithms for learning a multinomial  distribution can be extended to learn density matrices.  Intuitively, learning the $n^2$ parameters of a density matrix is much harder than learning the $n$ parameters of a multinomial distribution. Completely surprisingly, we prove that the worst-case regrets of   certain classical algorithms and   their matrix generalizations are identical.   The reason is that the worst-case sequence of dyads share a common   eigensystem, i.e. the worst case regret is achieved in the  classical case. So these matrix algorithms learn the eigenvectors  without any regret.
Noise Thresholds for Spectral Clustering
Authors: Sivaraman Balakrishnan, Min Xu, Akshay Krishnamurthy, Aarti Singh
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Clustering

Although spectral clustering has enjoyed considerable empirical success in machine learning, its theoretical properties are not yet fully developed. We analyze the performance of a spectral algorithm for hierarchical clustering and show that on a class of hierarchically structured similarity matrices, this algorithm can tolerate noise that grows with the number of data points while still perfectly recovering the hierarchical clusters with high probability. We  additionally improve upon previous results for k-way spectral clustering to derive conditions under which spectral clustering makes no mistakes. Further, using minimax analysis, we derive tight upper and lower bounds for the  clustering problem and compare the performance of spectral clustering to these  information theoretic limits. We also present experiments on simulated and real  world data illustrating our results.
The Kernel Beta Process
Authors: Lu Ren, Yingjian Wang, Lawrence Carin, David B. Dunson
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

A new Le ́vy process prior is proposed for an uncountable collection of covariate- dependent feature-learning measures; the model is called the kernel beta process (KBP). Available covariates are handled efficiently via the kernel construction, with covariates assumed observed with each data sample (“customer”), and latent covariates learned for each feature (“dish”). Each customer selects dishes from an infinite buffet, in a manner analogous to the beta process, with the added constraint that a customer first decides probabilistically whether to “consider” a dish, based on the distance in covariate space between the customer and dish. If a customer does consider a particular dish, that dish is then selected probabilistically as in the beta process. The beta process is recovered as a limiting case of the KBP. An efficient Gibbs sampler is developed for computations, and state-of-the-art results are presented for image processing and music analysis tasks.
Statistical Performance of Convex Tensor Decomposition
Authors: Ryota Tomioka, Taiji Suzuki, Kohei Hayashi, Hisashi Kashima
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Tensor Decomposition

We analyze the statistical performance of a recently proposed convex tensor decomposition algorithm. Conventionally tensor decomposition has been formulated as non-convex optimization problems, which hindered the analysis of their performance. We show under some conditions that the mean squared error of the convex method scales linearly with the quantity we call the normalized rank of the true tensor. The current analysis naturally extends the analysis of convex low-rank matrix estimation to tensors. Furthermore, we show through numerical experiments that our theory can precisely predict the scaling behaviour in practice.
Probabilistic amplitude and frequency demodulation
Authors: Richard Turner, Maneesh Sahani
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

A number of recent scientific and engineering problems require signals to be decomposed into a product of a slowly varying positive envelope and a quickly varying carrier whose instantaneous frequency also varies slowly over time. Although signal processing provides algorithms for so-called amplitude- and frequency-demodulation (AFD), there are well known problems with all of the existing methods. Motivated by the fact that AFD is ill-posed, we approach the problem using probabilistic inference. The new approach, called probabilistic amplitude and frequency demodulation (PAFD), models instantaneous frequency using an auto-regressive generalization of the von Mises distribution, and the envelopes using Gaussian auto-regressive dynamics with a positivity constraint. A novel form of expectation propagation is used for inference. We demonstrate that although PAFD is computationally demanding, it outperforms previous approaches on synthetic and real signals in clean, noisy and missing data settings.
Directed Graph Embedding: an Algorithm based on Continuous Limits of Laplacian-type Operators
Authors: Dominique C. Perrault-Joncas, Marina Meila
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Graph Embedding

This paper considers the problem of embedding directed graphs in Euclidean space while retaining directional information. We model the observed graph as a sample from a manifold endowed with a vector field, and we design an algo- rithm that separates and recovers the features of this process: the geometry of the manifold, the data density and the vector field. The algorithm is motivated by our analysis of Laplacian-type operators and their continuous limit as generators of diffusions on a manifold. We illustrate the recovery algorithm on both artificially constructed and real data.
Complexity of Inference in Latent Dirichlet Allocation
Authors: David Sontag, Dan Roy
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

We consider the computational complexity of probabilistic inference in Latent Dirichlet Allocation (LDA).  First, we study the problem of finding the maximum a posteriori (MAP) assignment of topics to words, where the document's topic distribution is integrated out.  We show that, when the effective number of topics per document is small, exact inference takes polynomial time. In contrast, we show that, when a document has a large number of topics, finding the MAP assignment of topics to words in LDA is NP-hard.  Next, we consider the problem of finding the MAP topic distribution for a document, where the topic-word assignments are integrated out.  We show that this problem is also NP-hard.  Finally, we briefly discuss the problem of sampling from the posterior, showing that this is NP-hard in one restricted setting, but leaving open the general question.
ICA with Reconstruction Cost for Efficient Overcomplete Feature Learning
Authors: Quoc V. Le, Alexandre Karpenko, Jiquan Ngiam, Andrew Y. Ng
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Image Classification, Object Recognition

Independent Components Analysis (ICA) and its variants have been successfully used for unsupervised feature learning. However, standard ICA requires an orthonoramlity constraint to be enforced, which makes it difﬁcult to learn overcomplete features. In addition, ICA is sensitive to whitening. These properties make it challenging to scale ICA to high dimensional data. In this paper, we propose a robust soft reconstruction cost for ICA that allows us to learn highly overcomplete sparse features even on unwhitened data. Our formulation reveals formal connections between ICA and sparse autoencoders, which have previously been observed only empirically. Our algorithm can be used in conjunction with off-the-shelf fast unconstrained optimizers. We show that the soft reconstruction cost can also be used to prevent replicated features in tiled convolutional neural networks. Using our method to learn highly overcomplete sparse features and tiled convolutional neural networks, we obtain competitive performances on a wide variety of object recognition tasks. We achieve state-of-the-art test accuracies on the STL-10 and Hollywood2 datasets.
Lower Bounds for Passive and Active Learning
Authors: Maxim Raginsky, Alexander Rakhlin
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Active Learning

We develop unified information-theoretic machinery for deriving lower bounds for passive and active learning schemes. Our bounds involve the so-called Alexander's capacity function. The supremum of this function has been recently rediscovered by Hanneke in the context of active learning under the name of "disagreement coefficient." For passive learning, our lower bounds match the upper bounds of Gine and Koltchinskii up to constants and generalize analogous results of Massart and Nedelec. For active learning, we provide first known lower bounds based on the capacity function rather than the disagreement coefficient.
Structure Learning for Optimization
Authors: Shulin Yang, Ali Rahimi
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: global-optimization

We describe a family of global optimization procedures that automatically decompose optimization problems into smaller loosely coupled problems, then combine the solutions of these with message passing algorithms.  We show empirically that these methods excel in avoiding local minima and produce better solutions with fewer function evaluations than existing global optimization methods.  To develop these methods, we introduce a notion of coupling between variables of optimization that generalizes the notion of coupling that arises from factoring functions into terms that involve small subsets of the variables. It therefore subsumes the notion of independence between random variables in statistics, sparseness of the Hessian in nonlinear optimization, and the generalized distributive law. Despite being more general, this notion of coupling is easier to verify empirically -- making structure estimation easy -- yet it allows us to migrate well-established inference methods on graphical models to the setting of global optimization.
Inverting Grice's Maxims to Learn Rules from Natural Language Extractions
Authors: Mohammad S. Sorower, Janardhan R. Doppa, Walker Orr, Prasad Tadepalli, Thomas G. Dietterich, Xiaoli Z. Fern
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Articles

We consider the problem of learning rules from natural language text  sources. These sources, such as news articles and web texts, are  created by a writer to communicate information to a reader, where the  writer and reader share substantial domain knowledge.  Consequently,  the texts tend to be concise and mention the minimum information  necessary for the reader to draw the correct conclusions.  We study  the problem of learning domain knowledge from such concise texts,  which is an instance of the general problem of learning in the  presence of missing data.  However, unlike standard approaches to  missing data, in this setting we know that facts are more likely to be  missing from the text in cases where the reader can infer them from  the facts that are mentioned combined with the domain knowledge.  Hence, we can explicitly model this "missingness" process and invert  it via probabilistic inference to learn the underlying domain  knowledge.  This paper introduces a mention model that models  the probability of facts being mentioned in the text based on what  other facts have already been mentioned and domain knowledge in the  form of Horn clause rules.  Learning must simultaneously search the  space of rules and learn the parameters of the mention model.  We  accomplish this via an application of Expectation Maximization within  a Markov Logic framework.  An experimental evaluation on synthetic and  natural text data shows that the method can learn accurate rules and  apply them to new texts to make correct inferences.  Experiments also  show that the method out-performs the standard EM approach that  assumes mentions are missing at random.
Active Classification based on Value of Classifier
Authors: Tianshi Gao, Daphne Koller
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Classification, General Classification

Modern classification tasks usually involve many class labels and can be informed by a broad range of features. Many of these tasks are tackled by constructing a set of classifiers, which are then applied at test time and then pieced together in a fixed procedure determined in advance or at training time. We present an active classification process at the test time, where each classifier in a large ensemble is viewed as a potential observation that might inform our classification process. Observations are then selected dynamically based on previous observations, using a value-theoretic computation that balances an estimate of the expected classification gain from each observation as well as its computational cost. The expected classification gain is computed using a probabilistic model that uses the outcome from previous observations. This active classification process is applied at test time for each individual test instance, resulting in an efficient instance-specific decision path. We demonstrate the benefit of the active scheme on various real-world datasets, and show that it can achieve comparable or even higher classification accuracy at a fraction of the computational costs of traditional methods.
Group Anomaly Detection using Flexible Genre Models
Authors: Liang Xiong, Barnabás Póczos, Jeff G. Schneider
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Anomaly Detection, Group Anomaly Detection

An important task in exploring and analyzing real-world data sets is to detect unusual and interesting phenomena. In this paper, we study the group anomaly detection problem. Unlike traditional anomaly detection research that focuses on data points, our goal is to discover anomalous aggregated behaviors of groups of points. For this purpose, we propose the Flexible Genre Model (FGM). FGM is designed to characterize data groups at both the point level and the group level so as to detect various types of group anomalies. We evaluate the effectiveness of FGM on both synthetic and real data sets including images and turbulence data, and show that it is superior to existing approaches in detecting group anomalies.
Approximating Semidefinite Programs in Sublinear Time
Authors: Dan Garber, Elad Hazan
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

In recent years semidefinite optimization has become a tool of major importance in various optimization and machine learning problems. In many of these problems the amount of data in practice is so large that there is a constant need for faster algorithms. In this work we present the first  sublinear time approximation algorithm for semidefinite programs which we believe may be useful for such problems in which the size of data may cause even linear time algorithms to have prohibitive running times in practice. We present the algorithm and its analysis alongside with some theoretical lower bounds and an improved algorithm for the special problem of supervised learning of a distance metric.
SpaRCS: Recovering low-rank and sparse matrices from compressive measurements
Authors: Andrew E. Waters, Aswin C. Sankaranarayanan, Richard Baraniuk
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Compressive Sensing, Matrix Completion, Video Compressive Sensing

We consider the problem of recovering a matrix $\mathbf{M}$ that is the sum of a low-rank matrix $\mathbf{L}$ and a sparse matrix $\mathbf{S}$ from a small set of linear measurements of the form $\mathbf{y} = \mathcal{A}(\mathbf{M}) = \mathcal{A}({\bf L}+{\bf S})$.  This model subsumes three important classes of signal recovery problems:  compressive sensing, affine rank minimization, and robust principal component analysis.  We propose a natural optimization problem for signal recovery under this model and develop a new greedy algorithm called SpaRCS to solve it.  SpaRCS inherits a number of desirable properties from the state-of-the-art CoSaMP and ADMiRA algorithms, including exponential convergence and efficient implementation.  Simulation results with video compressive sensing, hyperspectral imaging, and robust matrix completion data sets demonstrate both the accuracy and efficacy of the algorithm.
Budgeted Optimization with Concurrent Stochastic-Duration Experiments
Authors: Javad Azimi, Alan Fern, Xiaoli Z. Fern
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12

Budgeted optimization involves optimizing an unknown function that is costly to evaluate by requesting a limited number of function evaluations at intelligently selected inputs. Typical problem formulations assume that experiments are selected one at a time with a limited total number of experiments, which fail to capture important aspects of many real-world problems. This paper defines a novel problem formulation with the following important extensions: 1) allowing for concurrent experiments; 2) allowing for stochastic experiment durations; and 3) placing constraints on both the total number of experiments and the total experimental time. We develop both offline and online algorithms for selecting concurrent experiments in this new setting and provide experimental results on a number of optimization benchmarks. The results show that our algorithms produce highly effective schedules compared to natural baselines.
Online Submodular Set Cover, Ranking, and Repeated Active Learning
Authors: Andrew Guillory, Jeff A. Bilmes
Date: 2011-12-01 00:00:00
Proceeding: NeurIPS 2011 12
Tasks: Active Learning

We propose an online prediction version of submodular set cover with connections to ranking and repeated active learning.  In each round, the learning algorithm chooses a sequence of items.  The algorithm then receives a monotone submodular function and suffers loss equal to the cover time of the function: the number of items needed, when items are selected in order of the chosen sequence, to achieve a coverage constraint.  We develop an online learning algorithm whose loss converges to approximately that of the best sequence in hindsight.  Our proposed algorithm is readily extended to a setting where multiple functions are revealed at each round and to bandit and contextual bandit settings.