mtybilly/Instruct2DS huggingface dataset:
$\theta$-MRF: Capturing Spatial and Semantic Structure in the Parameters for Scene Understanding
Authors: Congcong Li, Ashutosh Saxena, Tsuhan Chen
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: For most scene understanding tasks (such as object detection or depth estimation), the classifiers need to consider contextual information in addition to the local features. We can capture such contextual information by taking as input the features/attributes from all the regions in the image. However, this contextual dependence also varies with the spatial location of the region of interest, and we therefore need a different set of parameters for each spatial location. This results in a very large number of parameters. In this work, we model the independence properties between the parameters for each location and for each task, by defining a Markov Random Field (MRF) over the parameters. In particular, two sets of parameters are encouraged to have similar values if they are spatially close or semantically close. Our method is, in principle, complementary to other ways of capturing context such as the ones that use a graphical model over the labels instead. In extensive evaluation over two different settings, of multi-class object detection and of multiple scene understanding tasks (scene categorization, depth estimation, geometric labeling), our method beats the state-of-the-art methods in all the four tasks.
Maximum Covariance Unfolding : Manifold Learning for Bimodal Data
Authors: Vijay Mahadevan, Chi W. Wong, Jose C. Pereira, Tom Liu, Nuno Vasconcelos, Lawrence K. Saul
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: 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.
Noise Thresholds for Spectral Clustering
Authors: Sivaraman Balakrishnan, Min Xu, Akshay Krishnamurthy, Aarti Singh
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: 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.
Kernel Embeddings of Latent Tree Graphical Models
Authors: Le Song, Eric P. Xing, Ankur P. Parikh
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Latent tree graphical models are natural tools for expressing long range and hierarchical dependencies among many variables which are common in computer vision, bioinformatics and natural language processing problems. However, existing models are largely restricted to discrete and Gaussian variables due to computational constraints; furthermore, algorithms for estimating the latent tree structure and learning the model parameters are largely restricted to heuristic local search. We present a method based on kernel embeddings of distributions for latent tree graphical models with continuous and non-Gaussian variables. Our method can recover the latent tree structures with provable guarantees and perform local-minimum free parameter learning and efficient inference. Experiments on simulated and real data show the advantage of our proposed approach.
Learning a Distance Metric from a Network
Authors: Blake Shaw, Bert Huang, Tony Jebara
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Many real-world networks are described by both connectivity information and features for every node.  To better model and understand these networks, we present structure preserving metric learning (SPML), an algorithm for learning a Mahalanobis distance metric from a network such that the learned distances are tied to the inherent connectivity structure of the network.  Like the graph embedding algorithm structure preserving embedding, SPML learns a metric which is structure preserving, meaning a connectivity algorithm such as k-nearest neighbors will yield the correct connectivity when applied using the distances from the learned metric.  We show a variety of synthetic and real-world experiments where SPML predicts link patterns from node features more accurately than standard techniques.  We further demonstrate a method for optimizing SPML based on stochastic gradient descent which removes the running-time dependency on the size of the network and allows the method to easily scale to networks of thousands of nodes and millions of edges.
Selective Prediction of Financial Trends with Hidden Markov Models
Authors: Dmitry Pidan, Ran El-Yaniv
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Focusing on short term trend prediction in a financial context, we consider the problem of selective prediction whereby the predictor can abstain from prediction in order to improve performance. We examine two types of selective mechanisms for HMM predictors. The first is a rejection in the spirit of Chow’s well-known ambiguity principle. The second is a specialized mechanism for HMMs that identifies low quality HMM states and abstain from prediction in those states. We call this model selective HMM (sHMM). In both approaches we can trade-off prediction coverage to gain better accuracy in a controlled manner. We compare performance of the ambiguity-based rejection technique with that of the sHMM approach. Our results indicate that both methods are effective, and that the sHMM  model is superior.
Blending Autonomous Exploration and Apprenticeship Learning
Authors: Thomas J. Walsh, Daniel K. Hewlett, Clayton T. Morrison
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We present theoretical and empirical results for a framework  that combines the benefits of apprenticeship and autonomous reinforcement learning.  Our approach modifies an existing apprenticeship learning framework that relies on teacher demonstrations and does not necessarily explore the environment.  The first change is replacing previously used Mistake Bound model learners with a recently proposed framework that melds the  KWIK and Mistake Bound supervised learning protocols.  The second change is introducing a communication of expected utility from the student to the teacher.   The resulting system only uses teacher traces when the agent needs to learn concepts it cannot efficiently learn on its own.
Transfer Learning by Borrowing Examples for Multiclass Object Detection
Authors: Joseph J. Lim, Ruslan Salakhutdinov, Antonio Torralba
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Despite the recent trend of increasingly large datasets for object detection, there still exist many classes with few training examples. To overcome this lack of train- ing data for certain classes, we propose a novel way of augmenting the training data for each class by borrowing and transforming examples from other classes. Our model learns which training instances from other classes to borrow and how to transform the borrowed examples so that they become more similar to instances from the target class. Our experimental results demonstrate that our new object detector, with borrowed and transformed examples, improves upon the current state-of-the-art detector on the challenging SUN09 object detection dataset.
A blind sparse deconvolution method for neural spike identification
Authors: Chaitanya Ekanadham, Daniel Tranchina, Eero P. Simoncelli
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider the problem of estimating neural spikes from extracellular voltage recordings. Most current methods are based on clustering, which requires substantial human supervision and produces systematic errors by failing to properly handle temporally overlapping spikes. We formulate the problem as one of statistical inference, in which the recorded voltage is a noisy sum of the spike trains of each neuron convolved with its associated spike waveform.  Joint maximum-a-posteriori (MAP) estimation of the waveforms and spikes is then a blind deconvolution problem in which the coefficients are sparse. We develop a block-coordinate descent method for approximating the MAP solution.  We validate our method on data simulated according to the generative model, as well as on real data for which ground truth is available via simultaneous intracellular recordings. In both cases, our method substantially reduces the number of missed spikes and false positives when compared to a standard clustering algorithm, primarily by recovering temporally overlapping spikes.  The method offers a fully automated alternative to clustering methods that is less susceptible to systematic errors.
Clustering via Dirichlet Process Mixture Models for Portable Skill Discovery
Authors: Scott Niekum, Andrew G. Barto
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Skill discovery algorithms in reinforcement learning typically identify single states or regions in state space that correspond to task-specific subgoals.  However, such methods do not directly address the question of how many distinct skills are appropriate for solving the tasks that the agent faces.  This can be highly inefficient when many identified subgoals correspond to the same underlying skill, but are all used individually as skill goals.  Furthermore, skills created in this manner are often only transferable to tasks that share identical state spaces, since corresponding subgoals across tasks are not merged into a single skill goal.  We show that these problems can be overcome by clustering subgoal data defined in an agent-space and using the resulting clusters as templates for skill termination conditions.  Clustering via a Dirichlet process mixture model is used to discover a minimal, sufficient collection of portable skills.
Unsupervised learning models of primary cortical receptive fields and receptive field plasticity
Authors: Maneesh Bhand, Ritvik Mudur, Bipin Suresh, Andrew Saxe, Andrew Y. Ng
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: The efficient coding hypothesis holds that neural receptive fields are adapted to the statistics of the environment, but is agnostic to the timescale of this adaptation, which occurs on both evolutionary and developmental timescales. In this work we focus on that component of adaptation which occurs during an organism's lifetime, and show that a number of unsupervised feature learning algorithms can account for features of normal receptive field properties across multiple primary sensory cortices. Furthermore, we show that the same algorithms account for altered receptive field properties in response to experimentally altered environmental statistics. Based on these modeling results we propose these models as phenomenological models of receptive field plasticity during an organism's lifetime. Finally, due to the success of the same models in multiple sensory areas, we suggest that these algorithms may provide a constructive realization of the theory, first proposed by Mountcastle (1978), that a qualitatively similar learning algorithm acts throughout primary sensory cortices.
Improved Algorithms for Linear Stochastic Bandits
Authors: Yasin Abbasi-yadkori, Dávid Pál, Csaba Szepesvári
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We improve the theoretical analysis and empirical performance of algorithms for the stochastic multi-armed bandit problem and the linear stochastic multi-armed bandit problem. In particular, we show that a simple modification of Auer’s UCB algorithm (Auer, 2002) achieves with high probability constant regret. More importantly, we modify and, consequently, improve the analysis of the algorithm for the for linear stochastic bandit problem studied by Auer (2002), Dani et al. (2008), Rusmevichientong and Tsitsiklis (2010), Li et al. (2010). Our modification improves the regret bound by a logarithmic factor, though experiments show a vast improvement. In both cases, the improvement stems from the construction of smaller confidence sets. For their construction we use a novel tail inequality for vector-valued martingales.
From Bandits to Experts: On the Value of Side-Observations
Authors: Shie Mannor, Ohad Shamir
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider an adversarial online learning setting where a decision maker can choose an action in every stage of the game. In addition to observing the reward of the chosen action, the decision maker gets side observations on the reward he would have obtained had he chosen some of the other actions. The observation structure is encoded as a graph, where node i is linked to  node j if sampling i provides information on the reward of j. This setting naturally interpolates between the well-known ``experts'' setting, where the decision maker can view all rewards, and the multi-armed bandits setting, where the decision maker can only view the reward of the chosen action. We develop practical algorithms with provable regret guarantees, which depend on non-trivial graph-theoretic properties of the information feedback structure. We also provide partially-matching lower bounds.
An Empirical Evaluation of Thompson Sampling
Authors: Olivier Chapelle, Lihong Li
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Thompson sampling is one of oldest heuristic to address the exploration / exploitation trade-off, but it is surprisingly not very popular in the literature. We present here some empirical results using Thompson sampling on simulated and real data, and show that it is highly competitive. And since this heuristic is very easy to implement, we argue that it should be part of the standard baselines to compare against.
Efficient Offline Communication Policies for Factored Multiagent POMDPs
Authors: João V. Messias, Matthijs Spaan, Pedro U. Lima
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Factored Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) form a powerful framework for multiagent planning under uncertainty, but optimal solutions require a rigid history-based policy representation. In this paper we allow inter-agent communication which turns the problem in a centralized Multiagent POMDP (MPOMDP). We map belief distributions over state factors to an agent's local actions by exploiting structure in the joint MPOMDP policy.  The key point is that when sparse dependencies between the agents' decisions exist, often the belief over its local state factors is sufficient for an agent to unequivocally identify the optimal action, and communication can be avoided. We formalize these notions by casting the problem into convex optimization form, and present experimental results illustrating the savings in communication that we can obtain.
Maximal Cliques that Satisfy Hard Constraints with Application to Deformable Object Model Learning
Authors: Xinggang Wang, Xiang Bai, Xingwei Yang, Wenyu Liu, Longin J. Latecki
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We propose a novel inference framework for finding maximal cliques in a weighted graph that satisfy hard constraints.  The constraints specify the graph nodes that must belong to the solution as well as mutual exclusions of graph nodes, i.e., sets of nodes that cannot belong to the same solution.  The proposed inference is based on a novel particle filter algorithm with state permeations. We apply the inference framework to a challenging problem of learning part-based, deformable object models. Two core problems in the learning framework, matching of image patches and finding salient parts, are formulated as two instances of the problem of finding maximal cliques with hard constraints. Our learning framework yields discriminative part based object models that achieve very good detection rate, and outperform other methods on object classes with large deformation.
Quasi-Newton Methods for Markov Chain Monte Carlo
Authors: Yichuan Zhang, Charles A. Sutton
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: The performance of Markov chain Monte Carlo methods is often sensitive to the scaling and correlations between the random variables of interest. An important source of information about the local correlation and scale is given by the Hessian matrix of the target distribution, but this is often either computationally expensive or infeasible. In this paper we propose MCMC samplers that make use of quasi-Newton approximations from the optimization literature, that approximate the Hessian of the target distribution from previous samples and gradients generated by the sampler. A key issue is that MCMC samplers that depend on the history of previous states are in general not valid. We address this problem by using limited memory quasi-Newton methods, which depend only on a fixed window of previous samples. On several real world datasets, we show that the quasi-Newton sampler is a more effective sampler than standard Hamiltonian Monte Carlo at a fraction of the cost of MCMC methods that require higher-order derivatives.
Inference in continuous-time change-point models
Authors: Florian Stimberg, Manfred Opper, Guido Sanguinetti, Andreas Ruttor
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider the problem of Bayesian inference for continuous time multi-stable stochastic systems which can change both their diffusion and drift parameters at discrete times. We propose exact inference and sampling methodologies for two specific cases where the discontinuous dynamics is given by a Poisson process and a two-state Markovian switch. We test the methodology on simulated data, and apply it to two real data sets in finance and systems biology. Our experimental results show that the approach leads to valid inferences and non-trivial insights.
A Convergence Analysis of Log-Linear Training
Authors: Simon Wiesler, Hermann Ney
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Log-linear models are widely used probability models for statistical pattern recognition. Typically, log-linear models are trained according to a convex criterion. In recent years, the interest in log-linear models has greatly increased. The optimization of log-linear model parameters is costly and therefore an important topic, in particular for large-scale applications. Different optimization algorithms have been evaluated empirically in many papers. In this work, we analyze the optimization problem analytically and show that the training of log-linear models can be highly ill-conditioned. We verify our findings on two handwriting tasks. By making use of our convergence analysis, we obtain good results on a large-scale continuous handwriting recognition task with a simple and generic approach.
On the accuracy of l1-filtering of signals with block-sparse structure
Authors: Fatma K. Karzan, Arkadi S. Nemirovski, Boris T. Polyak, Anatoli Juditsky
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We discuss new methods for the recovery of signals with block-sparse structure, based on l1-minimization. Our emphasis is on the efficiently computable error bounds for the recovery routines. We optimize these bounds with respect to the method parameters to construct the estimators with improved statistical properties. We justify the proposed approach with an oracle inequality which links the properties of the recovery algorithms and the best estimation performance.
Group Anomaly Detection using Flexible Genre Models
Authors: Liang Xiong, Barnabás Póczos, Jeff G. Schneider
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: 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.
Randomized Algorithms for Comparison-based Search
Authors: Dominique Tschopp, Suhas Diggavi, Payam Delgosha, Soheil Mohajer
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: This paper addresses the problem of finding the nearest neighbor (or    one of the $R$-nearest neighbors) of a query object $q$ in a    database of $n$ objects, when we can only use a comparison    oracle. The comparison oracle, given two reference objects and a    query object, returns the reference object most similar to the query    object.  The main problem we study is how to search the database for    the nearest neighbor (NN) of a query, while minimizing the    questions.  The difficulty of this problem depends on properties of    the underlying database. We show the importance of a    characterization: \emph{combinatorial disorder} $D$ which defines    approximate triangle inequalities on ranks. We present a lower bound    of $\Omega(D\log \frac{n}{D}+D^2)$ average number of questions in    the search phase for any randomized algorithm, which demonstrates    the fundamental role of $D$ for worst case behavior. We develop a    randomized scheme for NN retrieval in $O(D^3\log^2 n+ D\log^2 n    \log\log n^{D^3})$ questions.  The learning requires asking $O(n    D^3\log^2 n+ D \log^2 n \log\log n^{D^3})$ questions and    $O(n\log^2n/\log(2D))$ bits to store.
Multiple Instance Learning on Structured Data
Authors: Dan Zhang, Yan Liu, Luo Si, Jian Zhang, Richard D. Lawrence
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Most existing Multiple-Instance Learning (MIL) algorithms  assume data instances and/or data bags are independently and  identically distributed. But there often exists rich additional  dependency/structure information between instances/bags within many  applications of MIL. Ignoring this structure information limits the  performance of existing MIL algorithms. This paper explores the  research problem as multiple instance learning on structured  data (MILSD) and formulates a novel framework that considers  additional structure information. In particular, an effective and  efficient optimization algorithm has been proposed to solve the  original non-convex optimization problem by using a combination of  Concave-Convex Constraint Programming (CCCP) method and an adapted  Cutting Plane method, which deals with two sets of constraints caused  by learning on  instances within individual bags and learning on  structured data. Our method has the nice convergence property,  with specified precision on each set of constraints. Experimental  results on three different applications, i.e., webpage  classification, market targeting, and protein fold identification,  clearly demonstrate the advantages of the proposed method over  state-of-the-art methods.
Probabilistic Joint Image Segmentation and Labeling
Authors: Adrian Ion, Joao Carreira, Cristian Sminchisescu
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We present a joint image segmentation and labeling model (JSL) which, given a bag of figure-ground segment hypotheses extracted at multiple image locations and scales, constructs a joint probability distribution over both the compatible image interpretations (tilings or image segmentations) composed from those segments, and over their labeling into categories.  The process of drawing samples from the joint distribution can be interpreted as first sampling tilings, modeled as maximal cliques, from a graph connecting spatially non-overlapping segments in the bag, followed by sampling labels for those segments, conditioned on the choice of a particular tiling. We learn the segmentation and labeling parameters jointly, based on Maximum Likelihood with a novel Incremental Saddle Point estimation procedure. The partition function over tilings and labelings is increasingly more accurately approximated by including incorrect configurations that a not-yet-competent model rates probable during learning.   We show that the proposed methodology matches the current state of the art in the Stanford dataset, as well as in VOC2010, where 41.7% accuracy on the test set is achieved.
Learning to Search Efficiently in High Dimensions
Authors: Zhen Li, Huazhong Ning, Liangliang Cao, Tong Zhang, Yihong Gong, Thomas S. Huang
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: High dimensional similarity search in large scale databases becomes an important challenge due to the advent of Internet. For such applications, specialized data structures are required to achieve computational efficiency. Traditional approaches relied on algorithmic constructions that are often data independent (such as Locality Sensitive Hashing) or weakly dependent (such as kd-trees, k-means trees). While supervised learning algorithms have been applied to related problems, those proposed in the literature mainly focused on learning hash codes optimized for compact embedding of the data rather than search efficiency. Consequently such an embedding has to be used with linear scan or another search algorithm. Hence learning to hash does not directly address the search efficiency issue. This paper considers a new framework that applies supervised learning to directly optimize a data structure that supports efficient large scale search. Our approach takes both search quality and computational cost into consideration. Specifically, we learn a boosted search forest that is optimized using pair-wise similarity labeled examples. The output of this search forest can be efficiently converted into an inverted indexing data structure, which can leverage modern text search infrastructure to achieve both scalability and efficiency. Experimental results show that our approach significantly outperforms the start-of-the-art learning to hash methods (such as spectral hashing), as well as state-of-the-art high dimensional search algorithms (such as LSH and k-means trees).
Learning a Tree of Metrics with Disjoint Visual Features
Authors: Kristen Grauman, Fei Sha, Sung Ju Hwang
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We introduce an approach to learn discriminative visual representations while exploiting external semantic knowledge about object category relationships.  Given a hierarchical taxonomy that captures semantic similarity between the objects, we learn a corresponding tree of metrics (ToM).  In this tree, we have one metric for each non-leaf node of the object hierarchy, and each metric is responsible for discriminating among its immediate subcategory children.  Specifically, a Mahalanobis metric learned for a given node must satisfy the appropriate (dis)similarity constraints generated only among its subtree members' training instances.  To further exploit the semantics, we introduce a novel regularizer coupling the metrics that prefers a sparse disjoint set of features to be selected for each metric relative to its ancestor supercategory nodes' metrics.  Intuitively, this reflects that visual cues most useful to distinguish the generic classes (e.g., feline vs. canine) should be different than those cues most useful to distinguish their component fine-grained classes (e.g., Persian cat vs. Siamese cat).  We validate our approach with multiple image datasets using the WordNet taxonomy, show its advantages over alternative metric learning approaches, and analyze the meaning of attribute features selected by our algorithm.
Monte Carlo Value Iteration with Macro-Actions
Authors: Zhan Lim, Lee Sun, David Hsu
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: POMDP planning faces two major computational challenges: large state spaces and long planning horizons. The recently introduced Monte Carlo Value Iteration (MCVI) can tackle POMDPs with very large discrete state spaces or continuous state spaces, but its performance degrades when faced with long planning horizons. This paper presents Macro-MCVI, which extends MCVI by exploiting macro-actions for temporal abstraction. We provide sufficient conditions for Macro-MCVI to inherit the good theoretical properties of MCVI. Macro-MCVI does not require explicit construction of probabilistic models for macro-actions and is thus easy to apply in practice. Experiments show that Macro-MCVI substantially improves the performance of MCVI with suitable macro-actions.
Non-parametric Group Orthogonal Matching Pursuit for Sparse Learning with Multiple Kernels
Authors: Vikas Sindhwani, Aurelie C. Lozano
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider regularized risk minimization in a large dictionary of Reproducing  kernel Hilbert Spaces (RKHSs) over which the target function has a sparse representation.  This setting, commonly referred to as Sparse Multiple Kernel Learning  (MKL), may be viewed as the non-parametric extension of group sparsity in linear  models. While the two dominant algorithmic strands of sparse learning, namely  convex relaxations using l1 norm (e.g., Lasso) and greedy methods (e.g., OMP),  have both been rigorously extended for group sparsity, the sparse MKL literature  has so farmainly adopted the former withmild empirical success. In this paper, we  close this gap by proposing a Group-OMP based framework for sparse multiple  kernel learning. Unlike l1-MKL, our approach decouples the sparsity regularizer  (via a direct l0 constraint) from the smoothness regularizer (via RKHS norms)  which leads to better empirical performance as well as a simpler optimization  procedure that only requires a black-box single-kernel solver. The algorithmic  development and empirical studies are complemented by theoretical analyses in  terms of Rademacher generalization bounds and sparse recovery conditions analogous  to those for OMP [27] and Group-OMP [16].
Distributed Delayed Stochastic Optimization
Authors: Alekh Agarwal, John C. Duchi
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We analyze the convergence of gradient-based optimization algorithms whose updates depend on delayed stochastic gradient information. The  main application of our results is to the development of distributed  minimization algorithms where a master node performs parameter updates while worker nodes compute stochastic gradients based on local information in parallel, which may give rise to delays due to  asynchrony. Our main contribution is to show that for smooth stochastic problems, the delays are asymptotically negligible. In  application to distributed optimization, we show $n$-node architectures whose optimization error in stochastic problems---in spite of asynchronous delays---scales asymptotically as $\order(1 / \sqrt{nT})$, which is known to be optimal even in the absence of delays.
An Unsupervised Decontamination Procedure For Improving The Reliability Of Human Judgments
Authors: Michael Mozer, Benjamin Link, Harold Pashler
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Psychologists have long been struck by individuals' limitations in expressing their internal sensations, impressions, and evaluations via rating scales.  Instead of using an absolute scale, individuals rely on reference points from recent experience.  This relativity of judgment limits  the informativeness of responses on surveys, questionnaires, and evaluation forms. Fortunately, the cognitive processes that map stimuli to responses are not simply noisy, but rather are influenced by recent experience in a lawful manner.  We explore techniques to remove sequential dependencies, and thereby  decontaminate a series of ratings to obtain more meaningful human  judgments.  In our formulation, the problem is to infer latent (subjective) impressions from a sequence of stimulus labels (e.g., movie names) and responses.  We describe an unsupervised approach that simultaneously recovers  the impressions and parameters of a contamination model that predicts how  recent judgments affect the current response.  We test our iterated  impression inference, or I^3, algorithm in three domains:  rating the gap between dots, the desirability of a movie based on an advertisement, and the morality of an action. We demonstrate significant objective improvements  in the quality of the recovered impressions.
Contextual Gaussian Process Bandit Optimization
Authors: Andreas Krause, Cheng S. Ong
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: How should we design experiments to maximize performance of a complex system, taking into account uncontrollable environmental conditions? How should we select relevant documents (ads) to display, given information about the user? These tasks can be formalized as contextual bandit problems, where at each round, we receive context (about the experimental conditions, the query), and have to choose an action (parameters, documents). The key challenge is to trade off exploration by gathering data for estimating the mean payoff function over the context-action space, and to exploit by choosing an action deemed optimal based on the gathered data. We model the payoff function as a sample from a Gaussian process defined over the joint context-action space, and develop CGP-UCB, an intuitive upper-confidence style algorithm. We show that by mixing and matching kernels for contexts and actions, CGP-UCB can handle a variety of practical applications. We further provide generic tools for deriving regret bounds when using such composite kernel functions. Lastly, we evaluate our algorithm on two case studies, in the context of automated vaccine design and sensor management. We show that context-sensitive optimization outperforms no or naive use of context.
Learning with the weighted trace-norm under arbitrary sampling distributions
Authors: Rina Foygel, Ohad Shamir, Nati Srebro, Ruslan Salakhutdinov
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We provide rigorous guarantees on learning with the weighted trace-norm under arbitrary sampling distributions.  We show that the standard weighted-trace norm might fail when the sampling distribution is not a product distribution (i.e. when row and column indexes are not selected independently), present a corrected variant for which we establish strong learning guarantees, and demonstrate that it works better in practice.  We provide guarantees when weighting by either the true or empirical sampling distribution, and suggest that even if the true distribution is known (or is uniform), weighting by the empirical distribution may be beneficial.
Demixed Principal Component Analysis
Authors: Wieland Brendel, Ranulfo Romo, Christian K. Machens
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In many experiments, the data points collected live in high-dimensional observation spaces, yet can be assigned a set of labels or parameters. In electrophysiological recordings, for instance, the responses of populations of neurons generally depend on mixtures of experimentally controlled parameters. The heterogeneity and diversity of these parameter dependencies can make visualization and interpretation of such data extremely difficult. Standard dimensionality reduction techniques such as principal component analysis (PCA) can provide a succinct and complete description of the data, but the description is constructed independent of the relevant task variables and is often hard to interpret. Here, we start with the assumption that a particularly informative description is one that reveals the dependency of the high-dimensional data on the individual parameters. We show how to modify the loss function of PCA so that the principal components seek to capture both the maximum amount of variance about the data, while also depending on a minimum number of parameters. We call this method demixed principal component analysis (dPCA) as the principal components here segregate the parameter dependencies. We phrase the problem as a probabilistic graphical model, and present a fast Expectation-Maximization (EM) algorithm. We demonstrate the use of this algorithm for electrophysiological data and show that it serves to demix the parameter-dependence of a neural population response.
Reconstructing Patterns of Information Diffusion from Incomplete Observations
Authors: Flavio Chierichetti, David Liben-nowell, Jon M. Kleinberg
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Motivated by the spread of on-line information in general and   on-line petitions in particular, recent research has raised the following   combinatorial estimation problem.  There is a tree T that we cannot observe directly (representing  the structure along which the information has spread), and certain  nodes randomly decide to make their copy of the information public.  In the case of a petition, the list of names on each public copy   of the petition also reveals a path leading back to the root of the tree.  What can we conclude about the properties of the tree we observe  from these revealed paths,  and can we use the structure of the observed tree  to estimate the size of the full unobserved tree T?    Here we provide the first algorithm for this size estimation task,  together with provable guarantees on its performance.  We also establish structural properties of the observed tree, providing the  first rigorous explanation for some of the unusual structural  phenomena present in the spread of real chain-letter petitions  on the Internet.
Target Neighbor Consistent Feature Weighting for Nearest Neighbor Classification
Authors: Ichiro Takeuchi, Masashi Sugiyama
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider feature selection and weighting for nearest neighbor classifiers. A technical challenge in this scenario is how to cope with the discrete update of nearest neighbors when the feature space metric is changed during the learning process. This issue, called the target neighbor change, was not properly addressed in the existing feature weighting and metric learning literature.  In this paper, we propose a novel feature weighting algorithm that can exactly and efficiently keep track of the correct target neighbors via sequential quadratic programming. To the best of our knowledge, this is the first algorithm that guarantees the consistency between target neighbors and the feature space metric. We further show that the proposed algorithm can be naturally combined with regularization path tracking, allowing computationally efficient selection of the regularization parameter. We demonstrate the effectiveness of the proposed algorithm through experiments.
Hierarchical Matching Pursuit for Image Classification: Architecture and Fast Algorithms
Authors: Liefeng Bo, Xiaofeng Ren, Dieter Fox
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Extracting good representations from images is essential for many computer vision tasks. In this paper, we propose hierarchical matching pursuit (HMP), which builds a feature hierarchy layer-by-layer using an efficient matching pursuit encoder. It includes three modules: batch (tree) orthogonal matching pursuit, spatial pyramid max pooling, and contrast normalization. We investigate the architecture of HMP, and show that all three components are critical for good performance. To speed up the orthogonal matching pursuit, we propose a batch tree orthogonal matching pursuit that is particularly suitable to encode a large number of observations that share the same large dictionary. HMP is scalable and can efficiently handle full-size images. In addition, HMP enables linear support vector machines (SVM) to match the performance of nonlinear SVM while being scalable to large datasets. We compare HMP with many state-of-the-art algorithms including convolutional deep belief networks, SIFT based single layer sparse coding, and kernel based feature learning. HMP consistently yields superior accuracy on three types of image classification problems: object recognition (Caltech-101), scene recognition (MIT-Scene), and static event recognition (UIUC-Sports).
Solving Decision Problems with Limited Information
Authors: Denis D. Maua, Cassio Campos
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We present a new algorithm for exactly solving decision-making problems represented as an influence diagram. We do not require the usual assumptions of no forgetting and regularity, which allows us to solve problems with limited information. The algorithm, which implements a sophisticated variable elimination procedure, is empirically shown to outperform a state-of-the-art algorithm in randomly generated problems of up to 150 variables and $10^{64}$ strategies.
How Do Humans Teach: On Curriculum Learning and Teaching Dimension
Authors: Faisal Khan, Bilge Mutlu, Xiaojin Zhu
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We study the empirical strategies that humans follow as they teach a target concept with a simple 1D threshold to a robot.  Previous studies of computational teaching, particularly the teaching dimension model and the curriculum learning principle, offer contradictory predictions on what optimal strategy the teacher should follow in this teaching task. We show through behavioral studies that humans employ three distinct teaching strategies, one of which is consistent with the curriculum learning principle, and propose a novel theoretical framework as a potential explanation for this strategy. This framework, which assumes a teaching goal of minimizing the learner's expected generalization error at each iteration, extends the standard teaching dimension model and offers a theoretical justification for curriculum learning.
A rational model of causal inference with continuous causes
Authors: Thomas L. Griffiths, Michael James
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Rational models of causal induction have been successful in accounting for people's judgments about the existence of causal relationships. However, these models have focused on explaining inferences from discrete data of the kind that can be summarized in a 2 ✕ 2 contingency table. This severely limits the scope of these models, since the world often provides non-binary data. We develop a new rational model of causal induction using continuous dimensions, which aims to diminish the gap between empirical and theoretical approaches and real-world causal induction. This model successfully predicts human judgments from previous studies better than models of discrete causal inference, and outperforms several other plausible models of causal induction with continuous causes in accounting for people's inferences in a new experiment.