mtybilly/Instruct2DS huggingface dataset:
EDML for Learning Parameters in Directed and Undirected Graphical Models
Authors: Khaled S Refaat, Arthur Choi, Adnan Darwiche
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: EDML is a recently proposed algorithm for learning parameters in Bayesian networks.  It was originally derived in terms of approximate inference on a meta-network, which underlies the Bayesian approach to parameter estimation.  While this initial derivation helped discover EDML in the first place and provided a concrete context for identifying some of its properties (e.g., in contrast to EM), the formal setting was somewhat tedious in the number of concepts it drew on.  In this paper, we propose a greatly simplified perspective on EDML, which casts it as a general approach to continuous optimization. The new perspective has several advantages. First, it makes immediate some results that were non-trivial to prove initially. Second, it facilitates the design of EDML algorithms for new graphical models, leading to a new algorithm for learning parameters in Markov networks.  We derive this algorithm in this paper, and show, empirically, that it can sometimes learn better estimates from complete data, several times faster than commonly used optimization methods, such as conjugate gradient and L-BFGS.
Flexible sampling of discrete data correlations without the marginal distributions
Authors: Alfredo Kalaitzis, Ricardo Silva
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Learning the joint dependence of discrete variables is a fundamental problem in machine learning, with many applications including prediction, clustering and dimensionality reduction. More recently, the framework of copula modeling has gained popularity due to its modular parametrization of joint distributions. Among other properties, copulas provide a recipe for combining flexible models for univariate marginal distributions with parametric families suitable for potentially high dimensional dependence structures. More radically, the extended rank likelihood approach of Hoff (2007) bypasses learning marginal models completely when such information is ancillary to the learning task at hand as in, e.g., standard dimensionality reduction problems or copula parameter estimation. The main idea is to represent data by their observable rank statistics, ignoring any other information from the marginals. Inference is typically done in a Bayesian framework with Gaussian copulas, and it is complicated by the fact this implies sampling within a space where the number of constraints increase quadratically with the number of data points. The result is slow mixing when using off-the-shelf Gibbs sampling. We present an efficient algorithm based on recent advances on constrained Hamiltonian Markov chain Monte Carlo that is simple to implement and does not require paying for a quadratic cost in sample size.
Designed Measurements for Vector Count Data
Authors: Liming Wang, David E Carlson, Miguel Rodrigues, David Wilcox, Robert Calderbank, Lawrence Carin
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We consider design of linear projection measurements for a vector Poisson signal model. The projections are performed on the vector Poisson rate, $X\in\mathbb{R}_+^n$, and the observed data are a vector of counts, $Y\in\mathbb{Z}_+^m$. The projection matrix is designed by maximizing mutual information between $Y$ and $X$, $I(Y;X)$. When there is a latent class label $C\in\{1,\dots,L\}$ associated with $X$, we consider the mutual information with respect to $Y$ and $C$, $I(Y;C)$. New analytic expressions for the gradient of $I(Y;X)$ and $I(Y;C)$ are presented, with gradient performed with respect to the measurement matrix. Connections are made to the more widely studied Gaussian measurement model. Example results are presented for compressive topic modeling of a document corpora (word counting), and hyperspectral compressive sensing for chemical classification (photon counting).
Reasoning With Neural Tensor Networks for Knowledge Base Completion
Authors: Richard Socher, Danqi Chen, Christopher D. Manning, Andrew Ng
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: A common problem in knowledge representation and related fields is reasoning over a large joint knowledge graph, represented as triples of a relation between two entities. The goal of this paper is to develop a more powerful neural network model suitable for inference over these relationships. Previous models suffer from weak interaction between entities or simple linear projection of the vector space. We address these problems by introducing a neural tensor network (NTN) model which allow the entities and relations to interact multiplicatively. Additionally, we observe that such knowledge base models can be further improved by representing each entity as the average of vectors for the words in the entity name, giving an additional dimension of similarity by which entities can share statistical strength. We assess the model by considering the problem of predicting additional true relations between entities given a partial knowledge base. Our model outperforms previous models and can classify unseen relationships in WordNet and FreeBase with an accuracy of 86.2% and 90.0%, respectively.
Deep content-based music recommendation
Authors: Aaron van den Oord, Sander Dieleman, Benjamin Schrauwen
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Automatic music recommendation has become an increasingly relevant problem in recent years, since a lot of music is now sold and consumed digitally. Most recommender systems rely on collaborative filtering. However, this approach suffers from the cold start problem: it fails when no usage data is available, so it is not effective for recommending new and unpopular songs. In this paper, we propose to use a latent factor model for recommendation, and predict the latent factors from music audio when they cannot be obtained from usage data. We compare a traditional approach using a bag-of-words representation of the audio signals with deep convolutional neural networks, and evaluate the predictions quantitatively and qualitatively on the Million Song Dataset. We show that using predicted latent factors produces sensible recommendations, despite the fact that there is a large semantic gap between the characteristics of a song that affect user preference and the corresponding audio signal. We also show that recent advances in deep learning translate very well to the music recommendation setting, with deep convolutional neural networks significantly outperforming the traditional approach.
What do row and column marginals reveal about your dataset?
Authors: Behzad Golshan, John Byers, Evimaria Terzi
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Numerous datasets ranging from group memberships within social networks to purchase histories on e-commerce sites are represented by binary matrices. While this data is often either proprietary or sensitive, aggregated data, notably row and column marginals, is often viewed as much less sensitive, and may be furnished for analysis. Here, we investigate how these data can be exploited to make inferences about the underlying matrix H. Instead of assuming a generative model for H, we view the input marginals as constraints on the dataspace of possible realizations of H and compute the probability density function of particular entries H(i,j) of interest. We do this, for all the cells of H simultaneously, without generating realizations but rather via implicitly sampling the datasets that satisfy the input marginals. The end result is an efficient algorithm with running time equal to the time required by standard sampling techniques to generate a single dataset from the same dataspace. Our experimental evaluation demonstrates the efficiency and the efficacy of our framework in multiple settings.
Analyzing Hogwild Parallel Gaussian Gibbs Sampling
Authors: Matthew J Johnson, James Saunderson, Alan Willsky
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Sampling inference methods are computationally difficult to scale for many models in part because global dependencies can reduce opportunities for parallel computation.  Without strict conditional independence structure among variables, standard Gibbs sampling theory requires sample updates to be performed sequentially, even if dependence between most variables is not strong. Empirical work has shown that some models can be sampled effectively by going Hogwild'' and simply running Gibbs updates in parallel with only periodic global communication, but the successes and limitations of such a strategy are not well understood.  As a step towards such an understanding, we study the Hogwild Gibbs sampling strategy in the context of Gaussian distributions. We develop a framework which provides convergence conditions and error bounds along with simple proofs and connections to methods in numerical linear algebra.  In particular, we show that if the Gaussian precision matrix is generalized diagonally dominant, then any Hogwild Gibbs sampler, with any update schedule or allocation of variables to processors, yields a stable sampling process with the correct sample mean. "
Latent Structured Active Learning
Authors: Wenjie Luo, Alex Schwing, Raquel Urtasun
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: In this paper we present active learning algorithms in the context of structured prediction problems. To reduce the amount of labeling necessary to learn good models, our algorithms only label subsets of the output. To this end, we query examples using entropies of local marginals, which are a good surrogate for uncertainty. We demonstrate the effectiveness of our approach in the task of 3D layout prediction from single images, and show that good models are learned when labeling only a handful of random variables. In particular, the same performance as using the full training set can be obtained while only labeling ~10\% of the random variables.
Confidence Intervals and Hypothesis Testing for High-Dimensional Statistical Models
Authors: Adel Javanmard, Andrea Montanari
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Fitting high-dimensional statistical models often requires the use of non-linear parameter estimation procedures. As a consequence, it is generally impossible to obtain an exact characterization of the probability distribution of the parameter estimates. This in turn implies that it is extremely challenging to quantify the uncertainty' associated with a certain parameter estimate. Concretely, no commonly accepted procedure exists for computing classical measures of uncertainty and statistical significance as confidence intervals or p-values.  We consider here a broad class of regression problems, and propose  an efficient algorithm  for constructing confidence intervals and p-values.  The resulting confidence intervals have nearly optimal size. When testing for the null hypothesis that a certain parameter is vanishing, our method has nearly optimal power.  Our approach is based on constructing ade-biased' version of regularized M-estimators. The new construction  improves over recent work in the field in that it does not assume a special structure on the design matrix. Furthermore, proofs are remarkably simple. We test our method on a diabetes prediction problem.
Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
Authors: Edoardo M. Airoldi, Thiago B Costa, Stanley H Chan
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Given a convergent sequence of graphs, there exists a limit object called the graphon from which random graphs are generated. This nonparametric perspective of random graphs opens the door to study graphs beyond the traditional parametric models, but at the same time also poses the challenging question of how to estimate the graphon underlying observed graphs. In this paper, we propose a computationally efficient algorithm to estimate a graphon from a set of observed graphs generated from it. We show that, by approximating the graphon with stochastic block models, the graphon can be consistently estimated, that is, the estimation error vanishes as the size of the graph approaches infinity.
More Effective Distributed ML via a Stale Synchronous Parallel Parameter Server
Authors: Qirong Ho, James Cipar, Henggang Cui, Seunghak Lee, Jin Kyu Kim, Phillip B. Gibbons, Garth A Gibson, Greg Ganger, Eric P Xing
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We propose a parameter server system for distributed ML, which follows a Stale Synchronous Parallel (SSP) model of computation that maximizes the time computational workers spend doing useful work on ML algorithms, while still providing correctness guarantees. The parameter server provides an easy-to-use shared interface for read/write access to an ML model's values (parameters and variables), and the SSP model allows distributed workers to read older, stale versions of these values from a local cache, instead of waiting to get them from a central storage. This significantly increases the proportion of time workers spend computing, as opposed to waiting. Furthermore, the SSP model ensures ML algorithm correctness by limiting the maximum age of the stale values. We provide a proof of correctness under SSP, as well as empirical results demonstrating that the SSP model achieves faster algorithm convergence on several different ML problems, compared to fully-synchronous and asynchronous schemes.
On Algorithms for Sparse Multi-factor NMF
Authors: Siwei Lyu, Xin Wang
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Nonnegative matrix factorization (NMF) is a popular data analysis method, the objective of which is to decompose a matrix with all nonnegative components into the product of two other nonnegative matrices.  In this work, we describe a new simple and efficient algorithm for multi-factor nonnegative matrix factorization problem ({mfNMF}), which generalizes the original NMF problem to more than two factors.  Furthermore, we extend the mfNMF algorithm to incorporate a regularizer based on Dirichlet distribution over normalized columns to encourage sparsity in the obtained factors.  Our sparse NMF algorithm affords a closed form and an intuitive interpretation, and is more efficient in comparison with previous works that use fix point iterations. We demonstrate the effectiveness and efficiency of our algorithms on both synthetic and real data sets.
Efficient Exploration and Value Function Generalization in Deterministic Systems
Authors: Zheng Wen, Benjamin Van Roy
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We consider the problem of reinforcement learning over episodes of a finite-horizon deterministic system  and as a solution propose optimistic constraint propagation (OCP), an algorithm designed to synthesize efficient exploration and value function generalization. We establish that when the true value function lies within the given hypothesis class, OCP selects optimal actions over all but at most K episodes, where K is the eluder dimension of the given hypothesis class. We establish further efficiency and asymptotic performance guarantees that apply even if the true value function does not lie in the given hypothesis space, for  the special case where the hypothesis space is the span of pre-specified indicator functions over disjoint sets.
Parallel Sampling of DP Mixture Models using Sub-Cluster Splits
Authors: Jason Chang, John W. Fisher III
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We present a novel MCMC sampler for Dirichlet process mixture models that can be used for conjugate or non-conjugate prior distributions. The proposed sampler can be massively parallelized to achieve significant computational gains. A non-ergodic restricted Gibbs iteration is mixed with split/merge proposals to produce a valid sampler. Each regular cluster is augmented with two sub-clusters to construct likely split moves. Unlike many previous parallel samplers, the proposed sampler accurately enforces the correct stationary distribution of the Markov chain without the need for approximate models. Empirical results illustrate that the new sampler exhibits better convergence properties than current methods.
Context-sensitive active sensing in humans
Authors: Sheeraz Ahmad, He Huang, Angela J. Yu
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Humans and animals readily utilize active sensing, or the use of self-motion, to focus sensory and cognitive resources on the behaviorally most relevant stimuli and events in the environment. Understanding the computational basis of natural active sensing is important both for advancing brain sciences and for developing more powerful artificial systems. Recently, a goal-directed, context-sensitive, Bayesian control strategy for active sensing, termed C-DAC (Context-Dependent Active Controller), was proposed (Ahmad & Yu, 2013). In contrast to previously proposed algorithms for human active vision, which tend to optimize abstract statistical objectives and therefore cannot adapt to changing behavioral context or task goals, C-DAC directly minimizes behavioral costs and thus, automatically adapts itself to different task conditions. However, C-DAC is limited as a model of human active sensing, given its computational/representational requirements, especially for more complex, real-world situations. Here, we propose a myopic approximation to C-DAC, which also takes behavioral costs into account, but achieves a significant reduction in complexity by looking only one step ahead. We also present data from a human active visual search experiment, and compare the performance of the various models against human behavior. We find that C-DAC and its myopic variant both achieve better fit to human data than Infomax (Butko & Movellan, 2010), which maximizes expected cumulative future information gain. In summary, this work provides novel experimental results that differentiate theoretical models for human active sensing, as well as a novel active sensing algorithm that retains the context-sensitivity of the optimal controller while achieving significant computational savings.
On the Sample Complexity of Subspace Learning
Authors: Alessandro Rudi, Guillermo D Canas, Lorenzo Rosasco
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: A large number of algorithms in machine learning, from principal component analysis (PCA), and its non-linear (kernel) extensions, to more recent spectral embedding and support estimation methods, rely on estimating a linear subspace from samples.  In this paper we introduce  a general formulation  of this problem and derive novel learning error estimates. Our results rely on  natural  assumptions on the spectral properties of the covariance operator associated to  the data distribution, and hold for a wide class of metrics between subspaces. As special cases, we discuss sharp error estimates  for the reconstruction properties of PCA and spectral support estimation. Key to our analysis is an operator theoretic approach that has broad applicability to spectral learning methods.
Non-Linear Domain Adaptation with Boosting
Authors: Carlos J Becker, Christos M Christoudias, Pascal Fua
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: A common assumption in machine vision is that the training and test samples are drawn from the same distribution. However, there are many problems when this assumption is grossly violated, as in bio-medical applications where different acquisitions can generate drastic variations in the appearance of the data due to changing experimental conditions. This problem is accentuated with 3D data, for which annotation is very time-consuming, limiting the amount of data that can be labeled in new acquisitions for training. In this paper we present a multi-task learning algorithm for domain adaptation based on boosting. Unlike previous approaches that learn task-specific decision boundaries, our method learns a single decision boundary in a shared feature space, common to all tasks. We use the boosting-trick to learn a non-linear mapping of the observations in each task, with no need for specific a-priori knowledge of its global analytical form. This yields a more parameter-free domain adaptation approach that successfully leverages learning on new tasks where labeled data is scarce. We evaluate our approach on two challenging bio-medical datasets and achieve a significant improvement over the state-of-the-art.
Learning Trajectory Preferences for  Manipulators via Iterative Improvement
Authors: Ashesh Jain, Brian Wojcik, Thorsten Joachims, Ashutosh Saxena
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We consider the problem of learning good trajectories for manipulation tasks. This is challenging because the criterion defining a good trajectory varies with users, tasks and environments.  In this paper, we propose a co-active online  learning framework for teaching robots the preferences of its users for object  manipulation tasks. The key novelty of our approach lies in the type of feedback expected from the user: the human user does not need to demonstrate optimal trajectories as training data, but merely needs to iteratively provide trajectories that slightly improve over the trajectory currently proposed by the system. We argue that this  co-active preference feedback can be more easily elicited from the user than demonstrations of optimal trajectories, which are often challenging and non-intuitive to provide on high degrees of freedom manipulators. Nevertheless, theoretical regret bounds of our algorithm match the asymptotic rates of optimal trajectory algorithms. We also formulate a score function to capture the contextual information and demonstrate the generalizability of our algorithm on a variety of household tasks, for whom, the preferences were not only influenced by the object being manipulated but also by the surrounding environment.
Learning Chordal Markov Networks by Constraint Satisfaction
Authors: Jukka Corander, Tomi Janhunen, Jussi Rintanen, Henrik Nyman, Johan Pensar
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We investigate the problem of learning the structure of a Markov network from data. It is shown that the structure of such networks can be described in terms of constraints which enables the use of existing solver technology with optimization capabilities to compute optimal networks starting from initial scores computed from the data. To achieve efficient encodings, we develop a novel characterization of Markov network structure using a balancing condition on the separators between cliques forming the network. The resulting translations into propositional satisfiability and its extensions such as maximum satisfiability, satisfiability modulo theories, and answer set programming, enable us to prove the optimality of networks which have been previously found by stochastic search.
Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions
Authors: Rishabh K Iyer, Stefanie Jegelka, Jeff A. Bilmes
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We investigate three related and important problems connected to machine learning, namely approximating a submodular function everywhere, learning a submodular function (in a PAC like setting [26]), and constrained minimization of submodular functions. In all three problems, we provide improved bounds which depend on the “curvature” of a submodular function and improve on the previously known best results for these problems [9, 3, 7, 25] when the function is not too curved – a property which is true of many real-world submodular functions. In the former two problems, we obtain these bounds through a generic black-box transformation (which can potentially work for any algorithm), while in the case of submodular minimization, we propose a framework of algorithms which depend on choosing an appropriate surrogate for the submodular function. In all these cases, we provide almost matching lower bounds. While improved curvature-dependent bounds were shown for monotone submodular maximization [4, 27], the existence of similar improved bounds for the aforementioned problems has been open. We resolve this question in this paper by showing that the same notion of curvature provides these improved results. Empirical experiments add further support to our claims.
A New Convex Relaxation for Tensor Completion
Authors: Bernardino Romera-Paredes, Massimiliano Pontil
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We study the problem of learning a tensor from a set of linear measurements. A prominent methodology for this problem is based on the extension of trace norm regularization, which has been used extensively for learning low rank matrices, to the tensor setting.  In this paper, we highlight some limitations of this approach and propose an alternative convex relaxation on the Euclidean unit ball.  We then describe a technique to solve the associated regularization problem, which builds upon the alternating direction method of multipliers. Experiments on one synthetic dataset and two real datasets indicate that the proposed method improves significantly over tensor trace norm regularization in terms of estimation error, while remaining computationally tractable.
DESPOT: Online POMDP Planning with Regularization
Authors: Adhiraj Somani, Nan Ye, David Hsu, Wee Sun Lee
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: POMDPs provide a principled framework for planning under uncertainty, but are computationally intractable, due to the “curse of dimensionality” and the “curse of history”. This paper presents an online lookahead search algorithm that alleviates these difficulties by limiting the search to a set of sampled scenarios. The execution of all policies on the sampled scenarios is summarized using a Determinized Sparse Partially Observable Tree (DESPOT), which is a sparsely sampled belief tree. Our algorithm, named Regularized DESPOT (R-DESPOT), searches the DESPOT for a policy that optimally balances the size of the policy and the accuracy on its value estimate obtained through sampling. We give an output-sensitive performance bound for all policies derived from the DESPOT, and show that R-DESPOT works well if a small optimal policy exists. We also give an anytime approximation to R-DESPOT. Experiments show strong results, compared with two of the fastest online POMDP algorithms.
Speeding up Permutation Testing in Neuroimaging
Authors: Chris Hinrichs, Vamsi K Ithapu, Qinyuan Sun, Sterling C Johnson, Vikas Singh
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Multiple hypothesis testing is a significant problem in nearly all neuroimaging studies. In order to correct for this phenomena, we require a reliable estimate of the Family-Wise Error Rate (FWER). The well known Bonferroni correction method, while being simple to implement, is quite conservative, and can substantially under-power a study because it ignores dependencies between test statistics. Permutation testing, on the other hand, is an exact, non parametric method of estimating the FWER for a given α threshold, but for acceptably low thresholds the computational burden can be prohibitive. In this paper, we observe that permutation testing in fact amounts to populating the columns of a very large matrix P. By analyzing the spectrum of this matrix, under certain conditions, we see that P has a low-rank plus a low-variance residual decomposition which makes it suitable for highly sub–sampled — on the order of 0.5% — matrix completion methods. Thus, we propose a novel permutation testing methodology which offers a large speedup, without sacrificing the fidelity of the estimated FWER. Our valuations on four different neuroimaging datasets show that a computational speedup factor of roughly 50× can be achieved while recovering the FWER distribution up to very high accuracy. Further, we show that the estimated α threshold is also recovered faithfully, and is stable.
Neural representation of action sequences: how far can a simple snippet-matching model take us?
Authors: Cheston Tan, Jedediah M Singer, Thomas Serre, David Sheinberg, Tomaso Poggio
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: The macaque Superior Temporal Sulcus (STS) is a brain area that receives and integrates inputs from both the ventral and dorsal visual processing streams (thought to specialize in form and motion processing respectively). For the processing of articulated actions, prior work has shown that even a small population of STS neurons contains sufficient information for the decoding of actor invariant to action, action invariant to actor, as well as the specific conjunction of actor and action. This paper addresses two questions. First, what are the invariance properties of individual neural representations (rather than the population representation) in STS? Second, what are the neural encoding mechanisms that can produce such individual neural representations from streams of pixel images? We find that a baseline model, one that simply computes a linear weighted sum of ventral and dorsal responses to short action “snippets”, produces surprisingly good fits to the neural data. Interestingly, even using inputs from a single stream, both actor-invariance and action-invariance can be produced simply by having different linear weights.
Modeling Clutter Perception using Parametric Proto-object Partitioning
Authors: Chen-Ping Yu, Wen-Yu Hua, Dimitris Samaras, Greg Zelinsky
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Visual clutter, the perception of an image as being crowded and disordered, affects aspects of our lives ranging from object detection to aesthetics, yet relatively little effort has been made to model this important and ubiquitous percept. Our approach models clutter as the number of proto-objects segmented from an image, with proto-objects defined as groupings of superpixels that are similar in intensity, color, and gradient orientation features. We introduce a novel parametric method of merging superpixels by modeling mixture of Weibull distributions on similarity distance statistics, then taking the normalized number of proto-objects following partitioning as our estimate of clutter perception. We validated this model using a new $\text{90}-$image dataset of realistic scenes rank ordered by human raters for clutter, and showed that our method not only predicted clutter extremely well (Spearman's $\rho = 0.81$, $p < 0.05$), but also outperformed all existing clutter perception models and even a behavioral object segmentation ground truth. We conclude that the number of proto-objects in an image affects clutter perception more than the number of objects or features.
Relevance Topic Model for Unstructured Social Group Activity Recognition
Authors: Fang Zhao, Yongzhen Huang, Liang Wang, Tieniu Tan
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Unstructured social group activity recognition in web videos is a challenging task due to 1) the semantic gap between class labels and low-level visual features and 2) the lack of labeled training data. To tackle this problem, we propose a relevance topic model" for jointly learning meaningful mid-level representations upon bag-of-words (BoW) video representations and a classifier with sparse weights. In our approach, sparse Bayesian learning is incorporated into an undirected topic model (i.e., Replicated Softmax) to discover topics which are relevant to video classes and suitable for prediction. Rectified linear units are utilized to increase the expressive power of topics so as to explain better video data containing complex contents and make variational inference tractable for the proposed model. An efficient variational EM algorithm is presented for model parameter estimation and inference. Experimental results on the Unstructured Social Activity Attribute dataset show that our model achieves state of the art performance and outperforms other supervised topic model in terms of classification accuracy, particularly in the case of a very small number of labeled training videos."
Generalized Random Utility Models with Multiple Types
Authors: Hossein Azari Soufiani, Hansheng Diao, Zhenyu Lai, David C. Parkes
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We propose a model for demand estimation in multi-agent, differentiated product settings and present an estimation algorithm that uses reversible jump MCMC techniques to classify agents' types. Our model extends the popular setup in Berry, Levinsohn and Pakes (1995) to allow for the data-driven classification of agents' types using agent-level data. We focus on applications involving data on agents' ranking over alternatives, and present theoretical conditions that establish the identifiability of the model and uni-modality of the likelihood/posterior. Results on both real and simulated data provide support for the scalability of our approach.
(Nearly) Optimal Algorithms for Private Online Learning in Full-information and Bandit Settings
Authors: Abhradeep Guha Thakurta, Adam Smith
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We provide a general technique for making online learning algorithms differentially private, in both the full information and bandit settings. Our technique applies to algorithms that aim to minimize a \emph{convex} loss function which is a sum of smaller convex loss terms, one for each data point. We modify the popular \emph{mirror descent} approach, or rather a variant called \emph{follow the approximate leader}.    The technique leads to the first nonprivate algorithms for private online learning in the bandit setting. In the full information setting, our algorithms improve over the regret bounds of previous work.  In many cases, our algorithms (in both settings) matching the dependence on the input length, $T$, of the \emph{optimal nonprivate} regret bounds up to logarithmic factors in $T$. Our algorithms require logarithmic space and update time.
The Fast Convergence of Incremental PCA
Authors: Akshay Balsubramani, Sanjoy Dasgupta, Yoav Freund
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We prove the first finite-sample convergence rates for any incremental PCA algorithm using sub-quadratic time and memory per iteration. The algorithm analyzed is Oja's learning rule, an efficient and well-known scheme for estimating the top principal component. Our analysis of this non-convex problem yields expected and high-probability convergence rates of $\tilde{O}(1/n)$ through a novel technique. We relate our guarantees to existing rates for stochastic gradient descent on strongly convex functions, and extend those results. We also include experiments which demonstrate convergence behaviors predicted by our analysis.
Point Based Value Iteration with Optimal Belief Compression for Dec-POMDPs
Authors: Liam C MacDermed, Charles L Isbell
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: This paper presents four major results towards solving decentralized partially observable Markov decision problems (DecPOMDPs) culminating in an algorithm that outperforms all existing algorithms on all but one standard infinite-horizon benchmark problems. (1) We give an integer program that solves collaborative Bayesian games (CBGs). The program is notable because its linear relaxation is very often integral. (2) We show that a DecPOMDP with bounded belief can be converted to a POMDP (albeit with actions exponential in the number of beliefs). These actions correspond to strategies of a CBG. (3) We present a method to transform any DecPOMDP into a DecPOMDP with bounded beliefs (the number of beliefs is a free parameter) using optimal (not lossless) belief compression. (4) We show that the combination of these results opens the door for new classes of DecPOMDP algorithms based on previous POMDP algorithms. We choose one such algorithm, point-based valued iteration, and modify it to produce the first tractable value iteration method for DecPOMDPs which outperforms existing algorithms.
Summary Statistics for Partitionings and Feature Allocations
Authors: Isik B Fidaner, Taylan Cemgil
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Infinite mixture models are commonly used for clustering. One can sample from the posterior of mixture assignments by Monte Carlo methods or find its maximum a posteriori solution by optimization. However, in some problems the posterior is diffuse and it is hard to interpret the sampled partitionings. In this paper, we introduce novel statistics based on block sizes for representing sample sets of partitionings and feature allocations. We develop an element-based definition of entropy to quantify segmentation among their elements. Then we propose a simple algorithm called entropy agglomeration (EA) to summarize and visualize this information. Experiments on various infinite mixture posteriors as well as a feature allocation dataset demonstrate that the proposed statistics are useful in practice.
Learning Hidden Markov Models from Non-sequence Data via Tensor Decomposition
Authors: Tzu-Kuo Huang, Jeff Schneider
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Learning dynamic models from observed data has been a central issue in many scientific  studies or engineering tasks. The usual setting is that data are collected sequentially  from trajectories of some dynamical system operation.   In quite a few modern scientific modeling tasks, however, it turns out that  reliable sequential data are rather difficult to gather, whereas out-of-order snapshots are much easier to obtain. Examples include the modeling of galaxies, chronic diseases such Alzheimer's, or certain biological processes.  Existing methods for learning dynamic model from non-sequence data are mostly based on Expectation-Maximization, which involves non-convex optimization and is thus hard to analyze.  Inspired by recent advances in spectral learning methods, we propose to study this problem  from a different perspective: moment matching and spectral decomposition. Under that framework,  we identify reasonable assumptions on the generative process of non-sequence data,  and propose learning algorithms based on the tensor decomposition method  \cite{anandkumar2012tensor} to \textit{provably} recover first-order Markov models and hidden Markov models. To the best of our knowledge, this is the first formal guarantee on learning from non-sequence data. Preliminary simulation results confirm our theoretical findings.
On Flat versus Hierarchical Classification in Large-Scale Taxonomies
Authors: Rohit Babbar, Ioannis Partalas, Eric Gaussier, Massih R. Amini
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We study in this paper flat and hierarchical classification strategies in the context of large-scale taxonomies. To this end, we first propose a multiclass, hierarchical data dependent bound on the generalization error of classifiers deployed in large-scale taxonomies. This bound provides an explanation to several empirical results reported in the literature, related to the performance of flat and hierarchical classifiers. We then introduce another type of bounds targeting the approximation error of a family of classifiers, and derive from it features used in a meta-classifier to decide which nodes to prune (or flatten) in a large-scale taxonomy. We finally illustrate the theoretical developments through several experiments conducted on two widely used taxonomies.
Scoring Workers in Crowdsourcing: How Many Control Questions are Enough?
Authors: Qiang Liu, Alex Ihler, Mark Steyvers
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We study the problem of estimating continuous quantities, such as prices, probabilities, and point spreads, using a crowdsourcing approach.  A challenging aspect of combining the crowd's answers is that workers' reliabilities and biases are usually unknown and highly diverse.  Control items with known answers can be used to evaluate workers' performance, and hence improve the combined results on the target items with unknown answers.  This raises the problem of how many control items to use when the total number of items each workers can answer is limited: more control items evaluates the workers better, but leaves fewer resources for the target items that are of direct interest, and vice versa. We give theoretical results for this problem under different scenarios, and provide a simple rule of thumb for crowdsourcing practitioners.  As a byproduct, we also provide theoretical analysis of the accuracy of different consensus methods.
Cluster Trees on Manifolds
Authors: Sivaraman Balakrishnan, Srivatsan Narayanan, Alessandro Rinaldo, Aarti Singh, Larry Wasserman
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We investigate the problem of estimating the cluster tree for a density $f$ supported on or near a smooth $d$-dimensional manifold $M$ isometrically embedded in $\mathbb{R}^D$. We study a $k$-nearest neighbor based algorithm recently proposed by Chaudhuri and Dasgupta. Under mild assumptions on $f$ and $M$, we obtain rates of convergence that depend on $d$ only but not on the ambient dimension $D$. We also provide a sample complexity lower bound for a natural class of clustering algorithms that use $D$-dimensional neighborhoods.
Bayesian inference as iterated random functions with  applications to sequential inference in graphical models
Authors: Arash Amini, Xuanlong Nguyen
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We propose a general formalism of iterated random functions with semigroup property, under which exact and approximate Bayesian posterior updates can be viewed as specific instances. A convergence theory for iterated random functions is presented. As an application of the general theory we analyze convergence behaviors of exact and approximate message-passing algorithms that arise in a sequential change point detection problem formulated via a latent variable directed graphical model. The sequential inference algorithm and its supporting theory are  illustrated by simulated examples.
Recurrent networks of coupled Winner-Take-All oscillators for solving constraint satisfaction problems
Authors: Hesham Mostafa, Lorenz. K Mueller, Giacomo Indiveri
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: We present a recurrent neuronal network, modeled as a continuous-time dynamical system, that can solve constraint satisfaction problems. Discrete variables are represented by coupled Winner-Take-All (WTA) networks, and their values are encoded in localized patterns of oscillations that are learned by the recurrent weights in these networks. Constraints over the variables are encoded in the network connectivity. Although there are no sources of noise, the network can escape from local optima in its search for solutions that satisfy all constraints by modifying the effective network connectivity through oscillations. If there is no solution that satisfies all constraints, the network state changes in a pseudo-random manner and its trajectory approximates a sampling procedure that selects a variable assignment with a probability that increases with the fraction of constraints satisfied by this assignment. External evidence, or input to the network, can force variables to specific values. When new inputs are applied, the network re-evaluates the entire set of variables in its search for the states that satisfy the maximum number of constraints, while being consistent with the external input. Our results demonstrate that the proposed network architecture can perform a deterministic search for the optimal solution to problems with non-convex cost functions. The network is inspired by canonical microcircuit models of the cortex and suggests possible dynamical mechanisms to solve constraint satisfaction problems that can be present in biological networks, or implemented in neuromorphic electronic circuits.
Rapid Distance-Based Outlier Detection via Sampling
Authors: Mahito Sugiyama, Karsten Borgwardt
Published in: Advances in Neural Information Processing Systems 26  (NIPS 2013) (Main Conference Track), 2013

Abstract: Distance-based approaches to outlier detection are popular in data mining, as they do not require to model the underlying probability distribution, which is particularly challenging for high-dimensional data. We present an empirical comparison of various approaches to distance-based outlier detection across a large number of datasets. We report the surprising observation that a simple, sampling-based scheme outperforms state-of-the-art techniques in terms of both efficiency and effectiveness. To better understand this phenomenon, we provide a theoretical analysis why the sampling-based approach outperforms alternative methods based on k-nearest neighbor search.