mtybilly/Instruct2DS huggingface dataset:
Object Bank: A High-Level Image Representation for Scene Classification & Semantic Feature Sparsification
Authors: Li-jia Li, Hao Su, Li Fei-fei, Eric P. Xing
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Robust low-level image features have been proven to be effective representations for a variety of visual recognition tasks such as object recognition and scene classification; but pixels, or even local image patches, carry little semantic meanings. For high level visual tasks, such low-level image representations are potentially not enough. In this paper, we propose a high-level image representation, called the Object Bank, where an image is represented as a scale invariant response map of a large number of pre-trained generic object detectors, blind to the testing dataset or visual task. Leveraging on the Object Bank representation, superior performances on high level visual recognition tasks can be achieved with simple off-the-shelf classifiers such as logistic regression and linear SVM. Sparsity algorithms make our representation more efficient and scalable for large scene datasets, and reveal semantically meaningful feature patterns.
Using body-anchored priors for identifying actions in single images
Authors: Leonid Karlinsky, Michael Dinerstein, Shimon Ullman
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: This paper presents an approach to the visual recognition of human actions using only single images as input. The task is easy for humans but difficult for current approaches to object recognition, because action instances may be similar in terms of body pose, and often require detailed examination of relations between participating objects and body parts in order to be recognized. The proposed approach applies a two-stage interpretation procedure to each training and test image. The first stage produces accurate detection of the relevant body parts of the actor, forming a prior for the local evidence needed to be considered for identifying the action. The second stage extracts features that are ‘anchored’ to the detected body parts, and uses these features and their feature-to-part relations in order to recognize the action. The body anchored priors we propose apply to a large range of human actions. These priors allow focusing on the relevant regions and relations, thereby significantly simplifying the learning process and increasing recognition performance.
Reward Design via Online Gradient Ascent
Authors: Jonathan Sorg, Richard L. Lewis, Satinder P. Singh
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Recent work has demonstrated that when artificial agents are limited in their ability to achieve their goals, the agent designer can benefit by making the agent's goals different from the designer's. This gives rise to the optimization problem of designing the artificial agent's goals---in the RL framework, designing the agent's reward function. Existing attempts at solving this optimal reward problem do not leverage experience gained online during the agent's lifetime nor do they take advantage of knowledge about the agent's structure. In this work, we develop a gradient ascent approach with formal convergence guarantees for approximately solving the optimal reward problem online during an agent's lifetime. We show that our method generalizes a standard policy gradient approach, and we demonstrate its ability to improve reward functions in agents with various forms of limitations.
Supervised Clustering
Authors: Pranjal Awasthi, Reza B. Zadeh
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Despite the ubiquity of clustering as a tool in unsupervised learning, there is not yet a consensus on a formal theory, and the vast majority  of work in this direction has focused on unsupervised clustering. We study a recently proposed framework for supervised clustering where there is access to a teacher. We give an improved generic algorithm to cluster any concept class  in that model. Our algorithm is query-efficient in the sense that it involves only a small amount  of interaction with the teacher. We also present and study two natural generalizations of the model.  The model assumes that the teacher response to the algorithm is perfect. We eliminate  this limitation by proposing a noisy model and give an algorithm for  clustering the class of intervals in this noisy model. We also propose a dynamic model where the teacher sees  a random subset of the points. Finally, for datasets  satisfying a spectrum of weak to strong properties, we give query bounds, and show that a class  of clustering functions containing Single-Linkage will find the target clustering under the strongest  property.
Inferring Stimulus Selectivity from the Spatial Structure of Neural Network Dynamics
Authors: Kanaka Rajan, L Abbott, Haim Sompolinsky
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: How are the spatial patterns of spontaneous and evoked population responses related? We study the impact of connectivity on the spatial pattern of fluctuations in the input-generated response of a neural network, by comparing the distribution of evoked and intrinsically generated activity across the different units. We develop a complementary approach to principal component analysis in which separate high-variance directions are typically derived for each input condition. We analyze subspace angles to compute the difference between the shapes of trajectories corresponding to different network states, and the orientation of the low-dimensional subspaces that driven trajectories occupy within the full space of neuronal activity. In addition to revealing how the spatiotemporal structure of spontaneous activity affects input-evoked responses, these methods can be used to infer input selectivity induced by network dynamics from experimentally accessible measures of spontaneous activity (e.g. from voltage- or calcium-sensitive optical imaging experiments). We conclude that the absence of a detailed spatial map of afferent inputs and cortical connectivity does not limit our ability to design spatially extended stimuli that evoke strong responses.
Distributionally Robust Markov Decision Processes
Authors: Huan Xu, Shie Mannor
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We consider Markov decision processes where the values of the parameters are uncertain. This uncertainty is described by a sequence of nested sets (that is, each set contains the previous one), each of which corresponds to a probabilistic guarantee for a different confidence level so that a set of admissible probability distributions of the unknown parameters is specified. This formulation models the case where the decision maker is aware of and wants to exploit some (yet imprecise) a-priori information of the distribution of parameters, and arises naturally in practice where methods to estimate the confidence region of parameters abound. We propose a decision criterion based on distributional robustness: the optimal policy maximizes the expected total reward under the most adversarial probability distribution over realizations of the uncertain parameters that is admissible (i.e., it agrees with the a-priori information). We show that finding the optimal distributionally robust policy can be reduced to a standard robust MDP where the parameters belong to a single uncertainty set, hence it can be computed in polynomial time under mild technical conditions.
Empirical Risk Minimization with Approximations of Probabilistic Grammars
Authors: Noah A. Smith, Shay B. Cohen
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Probabilistic grammars are generative statistical models that are  useful for compositional and sequential structures. We present a framework, reminiscent of structural risk minimization, for empirical risk minimization of the parameters of a fixed probabilistic grammar using the log-loss. We derive sample complexity bounds in this framework that apply both to the supervised setting and the unsupervised setting.
MAP Estimation for Graphical Models by Likelihood Maximization
Authors: Akshat Kumar, Shlomo Zilberstein
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Computing a {\em maximum a posteriori} (MAP) assignment in graphical models is a crucial inference problem for many practical applications. Several provably convergent approaches have been successfully developed using linear programming (LP) relaxation of the MAP problem. We present an alternative approach, which transforms the MAP problem into that of inference in a finite mixture of simple Bayes nets. We then derive the Expectation Maximization (EM) algorithm for this mixture that also monotonically increases a lower bound on the MAP assignment until convergence. The update equations for the EM algorithm are remarkably simple, both conceptually and computationally, and can be implemented using a graph-based message passing paradigm similar to max-product computation. We experiment on the real-world protein design dataset and show that EM's convergence rate is significantly higher than the previous LP relaxation based approach MPLP. EM achieves a solution quality within $95$\% of optimal for most instances and is often an order-of-magnitude faster than MPLP.
Identifying graph-structured activation patterns in networks
Authors: James Sharpnack, Aarti Singh
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We consider the problem of identifying an activation pattern in a complex, large-scale network that is embedded in very noisy measurements. This problem is relevant to several applications, such as identifying traces of a biochemical spread by a sensor network, expression levels of genes, and anomalous activity or congestion in the Internet. Extracting such patterns is a challenging task specially if the network is large (pattern is very high-dimensional) and the noise is so excessive that it masks the activity at any single node. However, typically there are statistical dependencies in the network activation process that can be leveraged to fuse the measurements of multiple nodes and enable reliable extraction of high-dimensional noisy patterns. In this paper, we analyze an estimator based on the graph Laplacian eigenbasis, and establish the limits of mean square error recovery of noisy patterns arising from a probabilistic (Gaussian or Ising) model based on an arbitrary graph structure. We consider both deterministic and probabilistic network evolution models, and our results indicate that by leveraging the network interaction structure, it is possible to consistently recover high-dimensional patterns even when the noise variance increases with network size.
Size Matters: Metric Visual Search Constraints from Monocular Metadata
Authors: Mario Fritz, Kate Saenko, Trevor Darrell
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Metric constraints are known to be highly discriminative for many objects, but if training is limited to data captured from a particular 3-D sensor the quantity of training data may be severly limited. In this paper, we show how a crucial aspect of 3-D information–object and feature absolute size–can be added to models learned from commonly available online imagery, without use of any 3-D sensing or re- construction at training time. Such models can be utilized at test time together with explicit 3-D sensing to perform robust search. Our model uses a “2.1D” local feature, which combines traditional appearance gradient statistics with an estimate of average absolute depth within the local window. We show how category size information can be obtained from online images by exploiting relatively unbiquitous metadata fields specifying camera intrinstics. We develop an efficient metric branch-and-bound algorithm for our search task, imposing 3-D size constraints as part of an optimal search for a set of features which indicate the presence of a category. Experiments on test scenes captured with a traditional stereo rig are shown, exploiting training data from from purely monocular sources with associated EXIF metadata.
Near-Optimal Bayesian Active Learning with Noisy Observations
Authors: Daniel Golovin, Andreas Krause, Debajyoti Ray
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We tackle the fundamental problem of Bayesian active learning with noise, where we need to adaptively select from a number of expensive tests in order to identify an unknown hypothesis sampled from a known prior distribution. In the case of noise-free observations, a greedy algorithm called generalized binary search (GBS) is known to perform near-optimally. We show that if the observations are noisy, perhaps surprisingly, GBS can perform very poorly. We develop EC2, a novel, greedy active learning algorithm and prove that it is competitive with the optimal policy, thus obtaining the first competitiveness guarantees for Bayesian active learning with noisy observations. Our bounds rely on a recently discovered diminishing returns property called adaptive submodularity, generalizing the classical notion of submodular set functions to adaptive policies. Our results hold even if the tests have non–uniform cost and their noise is correlated. We also propose EffECXtive, a particularly fast approximation of EC2, and evaluate it on a Bayesian experimental design problem involving human subjects, intended to tease apart competing economic theories of how people make decisions under uncertainty.
Probabilistic Belief Revision with Structural Constraints
Authors: Peter Jones, Venkatesh Saligrama, Sanjoy Mitter
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Experts (human or computer) are often required to assess the probability of uncertain events. When a collection of experts independently assess events that are structurally interrelated, the resulting assessment may violate fundamental laws of probability. Such an assessment is termed incoherent. In this work we investigate how the problem of incoherence may be affected by allowing experts to specify likelihood models and then update their assessments based on the realization of a globally-observable random sequence.
Structured Determinantal Point Processes
Authors: Alex Kulesza, Ben Taskar
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We present a novel probabilistic model for distributions over sets of structures -- for example, sets of sequences, trees, or graphs. The critical characteristic of our model is a preference for diversity: sets containing dissimilar structures are more likely. Our model is a marriage of structured probabilistic models, like Markov random fields and context free grammars, with determinantal point processes, which arise in quantum physics as models of particles with repulsive interactions. We extend the determinantal point process model to handle an exponentially-sized set of particles (structures) via a natural factorization of the model into parts. We show how this factorization leads to tractable algorithms for exact inference, including computing marginals, computing conditional probabilities, and sampling. Our algorithms exploit a novel polynomially-sized dual representation of determinantal point processes, and use message passing over a special semiring to compute relevant quantities. We illustrate the advantages of the model on tracking and articulated pose estimation problems.
b-Bit Minwise Hashing for Estimating Three-Way Similarities
Authors: Ping Li, Arnd Konig, Wenhao Gui
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Computing two-way and multi-way set similarities is a fundamental problem. This study focuses on estimating 3-way resemblance (Jaccard similarity) using b-bit minwise hashing. While traditional minwise hashing methods store each hashed value using 64 bits, b-bit minwise hashing only stores the lowest b bits (where b>= 2 for 3-way). The extension to 3-way similarity from the prior work on 2-way similarity is technically non-trivial. We develop the precise estimator which is accurate and very complicated; and we recommend a much simplified estimator suitable for sparse data. Our analysis shows that $b$-bit minwise hashing can normally achieve a 10 to 25-fold improvement in the storage space required for a given estimator accuracy of the 3-way resemblance.
Auto-Regressive HMM Inference with Incomplete Data for Short-Horizon Wind Forecasting
Authors: Chris Barber, Joseph Bockhorst, Paul Roebber
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Accurate short-term wind forecasts (STWFs), with time horizons from 0.5 to 6 hours, are essential for efficient integration of wind power to the electrical power grid. Physical models based on numerical weather predictions are currently not competitive, and research on machine learning approaches is ongoing. Two major challenges confronting these efforts are missing observations and weather-regime induced dependency shifts among wind variables at geographically distributed sites. In this paper we introduce approaches that address both of these challenges. We describe a new regime-aware approach to STWF that use auto-regressive hidden Markov models (AR-HMM), a subclass of conditional linear Gaussian (CLG) models. Although AR-HMMs are a natural representation for weather regimes, as with CLG models in general, exact inference is NP-hard when observations are missing (Lerner and Parr, 2001). Because of this high cost, we introduce a simple approximate inference method for AR-HMMs, which we believe has applications to other sequential and temporal problem domains that involve continuous variables. In an empirical evaluation on publicly available wind data from two geographically distinct regions, our approach makes significantly more accurate predictions than baseline models, and uncovers meteorologically relevant regimes.
Link Discovery using Graph Feature Tracking
Authors: Emile Richard, Nicolas Baskiotis, Theodoros Evgeniou, Nicolas Vayatis
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We consider the problem of discovering links of an evolving undirected graph given a series of past snapshots of that graph. The graph is observed through the time sequence of its adjacency matrix and only the presence of edges is observed. The absence of an edge on a certain snapshot cannot be distinguished from a missing entry in the adjacency matrix. Additional information can be provided by examining the dynamics of the graph through a set of topological features, such as the degrees of the vertices.  We develop a novel methodology by building on both static matrix completion methods and the estimation of the future state of relevant graph features. Our procedure relies on the formulation of an optimization problem which can be approximately solved by a fast alternating linearized algorithm whose properties are examined. We  show experiments with both simulated and real data which reveal the interest of our methodology.
A VLSI Implementation of the Adaptive Exponential Integrate-and-Fire Neuron Model
Authors: Sebastian Millner, Andreas Grübl, Karlheinz Meier, Johannes Schemmel, Marc-olivier Schwartz
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We describe an accelerated hardware neuron being capable of emulating the adap-tive exponential integrate-and-fire neuron model. Firing patterns of the membrane stimulated by a step current are analyzed in transistor level simulation and in silicon on a prototype chip. The neuron is destined to be the hardware neuron of a highly integrated wafer-scale system reaching out for new computational paradigms and opening new experimentation possibilities. As the neuron is dedicated as a universal device for neuroscientific experiments, the focus lays on parameterizability and reproduction of the analytical model.
Sparse Inverse Covariance Selection via Alternating Linearization Methods
Authors: Katya Scheinberg, Shiqian Ma, Donald Goldfarb
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Gaussian graphical models are of great interest in statistical learning.  Because the conditional independencies between different nodes correspond to zero entries in the inverse covariance matrix of the Gaussian distribution, one can learn the structure of the graph by estimating a sparse inverse covariance matrix from sample data, by solving a convex maximum likelihood problem with an $\ell_1$-regularization term. In this paper, we propose a first-order method based on an alternating linearization technique that exploits the problem's special structure; in particular, the subproblems solved in each iteration have closed-form solutions. Moreover, our algorithm obtains an $\epsilon$-optimal solution in $O(1/\epsilon)$ iterations. Numerical experiments on both synthetic  and real data from gene association networks show that a practical version of  this algorithm outperforms other competitive algorithms.
Constructing Skill Trees for Reinforcement Learning Agents from Demonstration Trajectories
Authors: George Konidaris, Scott Kuindersma, Roderic Grupen, Andrew G. Barto
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We introduce CST, an algorithm for constructing skill trees from demonstration trajectories in continuous reinforcement learning domains. CST uses a changepoint detection method to segment each trajectory into a skill chain by detecting a change of appropriate abstraction, or that a segment is too complex to model as a single skill. The skill chains from each trajectory are then merged to form a skill tree. We demonstrate that CST constructs an appropriate skill tree that can be further refined through learning in a challenging continuous domain, and that it can be used to segment demonstration trajectories on a mobile manipulator into chains of skills where each skill is assigned an appropriate abstraction.
Trading off Mistakes and Don't-Know Predictions
Authors: Amin Sayedi, Morteza Zadimoghaddam, Avrim Blum
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We discuss an online learning framework in which the agent is allowed to say I don't know'' as well as making incorrect predictions on given examples. We analyze the trade off between sayingI don't know'' and making mistakes. If the number of don't know predictions is forced to be zero, the model reduces to the well-known mistake-bound model introduced by Littlestone [Lit88]. On the other hand, if no mistakes are allowed, the model reduces to KWIK framework introduced by Li et. al. [LLW08]. We propose a general, though inefficient, algorithm for general finite concept classes that minimizes the number of don't-know predictions if a certain number of mistakes are allowed. We then present specific polynomial-time algorithms for the concept classes of monotone disjunctions and linear separators.
Evaluation of Rarity of Fingerprints in Forensics
Authors: Chang Su, Sargur Srihari
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: A method for computing the rarity of latent fingerprints represented by minutiae is given. It allows determining the probability of finding a match for an evidence print in a database of n known prints. The probability of random correspondence between evidence and database is determined in three procedural steps. In the registration step the latent print is aligned by finding its core point; which is done using a procedure based on a machine learning approach based on Gaussian processes. In the evidence probability evaluation step a generative model based on Bayesian networks is used to determine the probability of the evidence; it takes into account both the dependency of each minutia on nearby minutiae and the confidence of their presence in the evidence. In the specific probability of random correspondence step the evidence probability is used to determine the probability of match among n for a given tolerance; the last evaluation is similar to the birthday correspondence probability for a specific birthday. The generative model is validated using a goodness-of-fit test evaluated with a standard database of fingerprints. The probability of random correspondence for several latent fingerprints are evaluated for varying numbers of minutiae.
(RF)^2 -- Random Forest Random Field
Authors: Nadia Payet, Sinisa Todorovic
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We combine random forest (RF) and conditional random field (CRF) into a new computational framework, called random forest random field (RF)^2. Inference of (RF)^2 uses the Swendsen-Wang cut algorithm, characterized by Metropolis-Hastings jumps. A jump from one state to another depends on the ratio of the proposal distributions, and on the ratio of the posterior distributions of the two states. Prior work typically resorts to a parametric estimation of these four distributions, and then computes their ratio. Our key idea is to instead directly estimate these ratios using RF. RF collects in leaf nodes of each decision tree the class histograms of training examples. We use these class histograms for a non-parametric estimation of the distribution ratios. We derive the theoretical error bounds of a two-class (RF)^2. (RF)^2 is applied to a challenging task of multiclass object recognition and segmentation over a random field of input image regions. In our empirical evaluation, we use only the visual information provided by image regions (e.g., color, texture, spatial layout), whereas the competing methods additionally use higher-level cues about the horizon location and 3D layout of surfaces in the scene. Nevertheless, (RF)^2 outperforms the state of the art on benchmark datasets, in terms of accuracy and computation time.
Online Learning in The Manifold of Low-Rank Matrices
Authors: Uri Shalit, Daphna Weinshall, Gal Chechik
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: When learning models that are represented in matrix forms, enforcing   a low-rank constraint can dramatically improve the memory and run   time complexity, while providing a natural regularization of the   model.  However, naive approaches for minimizing functions over the   set of low-rank matrices are either prohibitively time   consuming (repeated singular value decomposition of the matrix) or   numerically unstable (optimizing a factored representation of the   low rank matrix). We build on recent advances in optimization over   manifolds, and describe an iterative online learning procedure, consisting of a   gradient step, followed by a second-order retraction back to the   manifold. While the ideal retraction is hard to compute, and so is   the projection operator that approximates it, we describe another   second-order retraction that can be computed efficiently, with run   time and memory complexity of O((n+m)k) for a rank-k   matrix of dimension m x n, given rank one gradients.  We use   this algorithm, LORETA, to learn a matrix-form similarity measure over pairs of   documents represented as high dimensional vectors. LORETA   improves the mean average precision over a passive-   aggressive approach in a factorized model, and also improves over   a full model trained over pre-selected features using the same   memory requirements. LORETA also showed consistent improvement over   standard methods in a large (1600 classes) multi-label image classification task.
Variational bounds for mixed-data factor analysis
Authors: Mohammad Emtiyaz Khan, Guillaume Bouchard, Kevin P. Murphy, Benjamin M. Marlin
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We propose a new variational EM algorithm for fitting factor analysis models with mixed continuous and categorical observations. The algorithm is based on a simple quadratic bound to the log-sum-exp function.  In the special case of fully observed binary data, the bound we propose is significantly faster than previous variational methods. We show that EM is significantly more robust in the presence of missing data compared to treating the latent factors as parameters, which is the approach used by exponential family PCA and other related matrix-factorization methods.  A further benefit of the variational approach is that it can easily be extended to the case of mixtures of factor analyzers, as we show. We present results on synthetic and real data sets demonstrating several desirable properties of our proposed method.
Evidence-Specific Structures for Rich Tractable CRFs
Authors: Anton Chechetka, Carlos Guestrin
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We present a simple and effective approach to learning tractable conditional random fields with structure that depends on the evidence. Our approach retains the advantages of tractable discriminative models, namely efficient exact inference and exact parameter learning. At the same time, our algorithm does not suffer a large expressive power penalty inherent to fixed tractable structures. On real-life relational datasets, our approach matches or exceeds state of the art accuracy of the dense models, and at the same time provides an order of magnitude speedup
Beyond Actions: Discriminative Models for Contextual Group Activities
Authors: Tian Lan, Yang Wang, Weilong Yang, Greg Mori
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We propose a discriminative model for recognizing group activities. Our model jointly captures the group activity, the individual person actions, and the interactions among them. Two new types of contextual information, group-person interaction and person-person interaction, are explored in a latent variable framework. Different from most of the previous latent structured models which assume a predefined structure for the hidden layer, e.g. a tree structure, we treat the structure of the hidden layer as a latent variable and implicitly infer it during learning and inference. Our experimental results demonstrate that by inferring this contextual information together with adaptive structures, the proposed model can significantly improve activity recognition performance.
Decoding Ipsilateral Finger Movements from ECoG Signals in Humans
Authors: Yuzong Liu, Mohit Sharma, Charles Gaona, Jonathan Breshears, Jarod Roland, Zachary Freudenburg, Eric Leuthardt, Kilian Q. Weinberger
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Several motor related Brain Computer Interfaces (BCIs) have been developed over the years that use activity decoded from the contralateral hemisphere to operate devices. Many recent studies have also talked about the importance of ipsilateral activity in planning of motor movements. For successful upper limb BCIs, it is important to decode finger movements from brain activity. This study uses ipsilateral cortical signals from humans (using ECoG) to decode finger movements. We demonstrate, for the first time, successful finger movement detection using machine learning algorithms. Our results show high decoding accuracies in all cases which are always above chance. We also show that significant accuracies can be achieved with the use of only a fraction of all the features recorded and that these core features also make sense physiologically. The results of this study have a great potential in the emerging world of motor neuroprosthetics and other BCIs.
New Adaptive Algorithms for Online Classification
Authors: Francesco Orabona, Koby Crammer
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We propose a general framework to online learning for   classification problems with time-varying potential functions in the   adversarial setting. This framework allows to design and prove   relative mistake bounds for any generic loss function. The mistake   bounds can be specialized for the hinge loss, allowing to recover   and improve the bounds of known online classification   algorithms. By optimizing the general bound we derive a new online   classification algorithm, called NAROW, that hybridly uses adaptive- and fixed- second order   information. We analyze the properties of the algorithm and   illustrate its performance using synthetic dataset.
Phoneme Recognition with Large Hierarchical Reservoirs
Authors: Fabian Triefenbach, Azarakhsh Jalalvand, Benjamin Schrauwen, Jean-pierre Martens
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Automatic speech recognition has gradually improved over the years, but the reliable recognition of unconstrained speech is still not within reach. In order to achieve a breakthrough, many research groups are now investigating new methodologies that have potential to outperform the Hidden Markov Model technology that is at the core of all present commercial systems. In this paper, it is shown that the recently introduced concept of Reservoir Computing might form the basis of such a methodology. In a limited amount of time, a reservoir system that can recognize the elementary sounds of continuous speech has been built. The system already achieves a state-of-the-art performance, and there is evidence that the margin for further improvements is still significant.
Learning Multiple Tasks using Manifold Regularization
Authors: Arvind Agarwal, Samuel Gerber, Hal Daume
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We present a novel method for multitask learning (MTL) based on {\it manifold regularization}: assume that all task parameters lie on a manifold. This is the generalization of a common assumption made in the existing literature: task parameters share a common {\it linear} subspace. One proposed method uses the projection distance from the manifold to regularize the task parameters. The manifold structure and the task parameters are learned using an alternating optimization framework. When the manifold structure is fixed, our method decomposes across tasks which can be learnt independently. An approximation of the manifold regularization scheme is presented that preserves the convexity of the single task learning problem, and makes the proposed MTL framework efficient and easy to implement. We show the efficacy of our method on several datasets.
Group Sparse Coding with a Laplacian Scale Mixture Prior
Authors: Pierre Garrigues, Bruno A. Olshausen
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We propose a class of sparse coding models that utilizes a Laplacian Scale Mixture (LSM) prior to model dependencies among coefficients. Each coefficient is modeled as a Laplacian distribution with a variable scale parameter, with a Gamma distribution prior over the scale parameter. We show that, due to the conjugacy of the Gamma prior, it is possible to derive efficient inference procedures for both the coefficients and the scale parameter. When the scale parameters of a group of coefficients are combined into a single variable, it is possible to describe the dependencies that occur due to common amplitude fluctuations among coefficients, which have been shown to constitute a large fraction of the redundancy in natural images. We show that, as a consequence of this group sparse coding, the resulting inference of the coefficients follows a divisive normalization rule, and that this may be efficiently implemented a network architecture similar to that which has been proposed to occur in primary visual cortex. We also demonstrate improvements in image coding and compressive sensing recovery using the LSM model.
Fractionally Predictive Spiking Neurons
Authors: Jaldert Rombouts, Sander M. Bohte
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Recent experimental work has suggested that the neural firing rate can be interpreted as a fractional derivative, at least when signal variation induces neural adaptation. Here, we show that the actual neural spike-train itself can be considered as the fractional derivative, provided that the neural signal is approximated by a sum of power-law kernels. A simple standard thresholding spiking neuron suffices to carry out such an approximation, given a suitable refractory response. Empirically, we find that the online approximation of signals with a sum of power-law kernels is beneficial for encoding signals with slowly varying components, like long-memory self-similar signals. For such signals, the online power-law kernel approximation typically required less than half the number of spikes for similar SNR as compared to sums of similar but exponentially decaying kernels. As power-law kernels can be accurately approximated using sums or cascades of weighted exponentials, we demonstrate that the corresponding decoding of spike-trains by a receiving neuron allows for natural and transparent temporal signal filtering by tuning the weights of the decoding kernel.
Stability Approach to Regularization Selection (StARS) for High Dimensional Graphical Models
Authors: Han Liu, Kathryn Roeder, Larry Wasserman
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: A challenging problem in estimating high-dimensional graphical models is to choose the regularization parameter in a data-dependent way. The standard techniques include $K$-fold cross-validation ($K$-CV), Akaike information criterion (AIC), and Bayesian information criterion (BIC). Though these methods work well for low-dimensional problems, they are not suitable in high dimensional settings. In this paper, we present StARS: a new stability-based method for choosing the regularization parameter in high dimensional inference for undirected graphs. The method has a clear interpretation: we use the least amount of regularization that simultaneously makes a graph sparse and replicable under random sampling. This interpretation requires essentially no conditions. Under mild conditions, we show that StARS is partially sparsistent in terms of graph estimation: i.e. with high probability, all the true edges will be included in the selected model even when the graph size asymptotically increases with the sample size. Empirically, the performance of StARS is compared with the state-of-the-art model selection procedures, including $K$-CV, AIC, and BIC, on both synthetic data and a real microarray dataset. StARS outperforms all competing procedures.
More data means less inference: A pseudo-max approach to structured learning
Authors: David Sontag, Ofer Meshi, Amir Globerson, Tommi S. Jaakkola
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: The problem of learning to predict structured labels is of key importance in many applications. However, for general graph structure both learning and inference in this setting are intractable. Here we show that it is possible to circumvent this difficulty when the input distribution is rich enough via a method similar in spirit to pseudo-likelihood. We show how our new method achieves consistency, and illustrate empirically that it indeed performs as well as exact methods when sufficiently large training sets are used.
Lifted Inference Seen from the Other Side : The Tractable Features
Authors: Abhay Jha, Vibhav Gogate, Alexandra Meliou, Dan Suciu
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Lifted inference algorithms for representations that combine first-order logic and probabilistic graphical models have been the focus of much recent research. All lifted algorithms developed to date are based on the same underlying idea: take a standard probabilistic inference algorithm (e.g., variable elimination, belief propagation etc.) and improve its efficiency by exploiting repeated structure in the first-order model. In this paper, we propose an approach from the other side in that we use techniques from logic for probabilistic inference. In particular, we define a set of rules that look only at the logical representation to identify models for which exact efficient inference is possible. We show that our rules yield several new tractable classes that cannot be solved efficiently by any of the existing techniques.
Predictive State Temporal Difference Learning
Authors: Byron Boots, Geoffrey J. Gordon
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We propose a new approach to value function approximation which combines linear temporal difference reinforcement learning with subspace identification. In practical applications, reinforcement learning (RL) is complicated by the fact that state is either high-dimensional or partially observable. Therefore, RL methods are designed to work with features of state rather than state itself, and the success or failure of learning is often determined by the suitability of the selected features. By comparison, subspace identification (SSID) methods are designed to select a feature set which preserves as much information as possible about state. In this paper we connect the two approaches, looking at the problem of reinforcement learning with a large set of features, each of which may only be marginally useful for value function approximation. We introduce a new algorithm for this situation, called Predictive State Temporal Difference (PSTD) learning. As in SSID for predictive state representations, PSTD finds a linear compression operator that projects a large set of features down to a small set that preserves the maximum amount of predictive information. As in RL, PSTD then uses a Bellman recursion to estimate a value function. We discuss the connection between PSTD and prior approaches in RL and SSID. We prove that PSTD is statistically consistent, perform several experiments that illustrate its properties, and demonstrate its potential on a difficult optimal stopping problem.
Identifying Dendritic Processing
Authors: Aurel A. Lazar, Yevgeniy Slutskiy
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: In system identification both the input and the output of a system are available to an observer and an algorithm is sought to identify parameters of a hypothesized model of that system. Here we present a novel formal methodology for identifying dendritic processing in a neural circuit consisting of a linear dendritic processing filter in cascade with a spiking neuron model. The input to the circuit is an analog signal that belongs to the space of bandlimited functions. The output is a time sequence associated with the spike train. We derive an algorithm for identification of the dendritic processing filter and reconstruct its kernel with arbitrary precision.
On a Connection between Importance Sampling and the Likelihood Ratio Policy Gradient
Authors: Tang Jie, Pieter Abbeel
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Likelihood ratio policy gradient methods have been some of the most successful reinforcement learning algorithms, especially for learning on physical systems. We describe how the likelihood ratio policy gradient can be derived from an importance sampling perspective. This derivation highlights how likelihood ratio methods under-use past experience by (a) using the past experience to estimate {\em only} the gradient of the expected return $U(\theta)$ at the current policy parameterization $\theta$, rather than to obtain a more complete estimate of $U(\theta)$, and (b) using past experience under the current policy {\em only} rather than using all past experience to improve the estimates. We present a new policy search method, which leverages both of these observations as well as generalized baselines---a new technique which generalizes commonly used baseline techniques for policy gradient methods. Our algorithm outperforms standard likelihood ratio policy gradient algorithms on several testbeds.
Functional Geometry Alignment and Localization of Brain Areas
Authors: Georg Langs, Yanmei Tie, Laura Rigolo, Alexandra Golby, Polina Golland
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Matching functional brain regions across individuals is a challenging task, largely due to the variability in their location and extent. It is particularly difficult, but highly relevant, for patients with pathologies such as brain tumors, which can cause substantial reorganization of functional systems. In such cases spatial registration based on anatomical data is only of limited value if the goal is to establish correspondences of functional areas among different individuals, or to localize potentially displaced active regions. Rather than rely on spatial alignment, we propose to perform registration in an alternative space whose geometry is governed by the functional interaction patterns in the brain. We first embed each brain into a functional map that reflects connectivity patterns during a fMRI experiment. The resulting functional maps are then registered, and the obtained correspondences are propagated back to the two brains. In application to a language fMRI experiment, our preliminary results suggest that the proposed method yields improved functional correspondences across subjects. This advantage is pronounced for subjects with tumors that affect the language areas and thus cause spatial reorganization of the functional regions.
Multi-View Active Learning in the Non-Realizable Case
Authors: Wei Wang, Zhi-Hua Zhou
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: The sample complexity of active learning under the realizability assumption has been well-studied. The realizability assumption, however, rarely holds in practice. In this paper, we theoretically characterize the sample complexity of active learning in the non-realizable case under multi-view setting. We prove that, with unbounded Tsybakov noise, the sample complexity of multi-view active learning can be $\widetilde{O}(\log \frac{1}{\epsilon})$, contrasting to single-view setting where the polynomial improvement is the best possible achievement. We also prove that in general multi-view setting the sample complexity of active learning with unbounded Tsybakov noise is $\widetilde{O}(\frac{1}{\epsilon})$, where the order of $1/\epsilon$ is independent of the parameter in Tsybakov noise, contrasting to previous polynomial bounds where the order of $1/\epsilon$ is related to the parameter in Tsybakov noise.