mtybilly/Instruct2DS huggingface dataset:
Attentional Processing on a Spike-Based VLSI Neural Network
Authors: Yingxue Wang, Rodney J. Douglas, Shih-Chii Liu
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: The neurons of the neocortex communicate by asynchronous events called action potentials (or 'spikes'). However, for simplicity of simulation, most models of processing by cortical neural networks have assumed that the activations of their neurons can be approximated by event rates rather than taking account of individual spikes. The obstacle to exploring the more detailed spike processing of these networks has been reduced considerably in recent years by the development of hybrid analog-digital Very-Large Scale Integrated (hVLSI) neural networks composed of spiking neurons that are able to operate in real-time. In this paper we describe such a hVLSI neural network that performs an interesting task of selective attentional processing that was previously described for a simulated 'pointer-map' rate model by Hahnloser and colleagues. We found that most of the computational features of their rate model can be reproduced in the spiking implementation; but, that spike-based processing requires a modification of the original network architecture in order to memorize a previously attended target.
A Bayesian Approach to Diffusion Models of Decision-Making and Response Time
Authors: Michael D. Lee, Ian G. Fuss, Daniel J. Navarro
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We present a computational Bayesian approach for Wiener diffusion models, which are prominent accounts of response time distributions in decision-making. We first develop a general closed-form analytic approximation to the response time distributions for one-dimensional diffusion processes, and derive the required Wiener diffusion as a special case. We use this result to undertake Bayesian modeling of benchmark data, using posterior sampling to draw inferences about the interesting psychological parameters. With the aid of the benchmark data, we show the Bayesian account has several advantages, including dealing naturally with the parameter variation needed to account for some key features of the data, and providing quantitative measures to guide decisions about model construction.
Graph-Based Visual Saliency
Authors: Jonathan Harel, Christof Koch, Pietro Perona
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: A new bottom-up visual saliency model, Graph-Based Visual Saliency (GBVS), is proposed. It consists of two steps: rst forming activation maps on certain feature channels, and then normalizing them in a way which highlights conspicuity and admits combination with other maps. The model is simple, and biologically plausible insofar as it is naturally parallelized. This model powerfully predicts human xations on 749 variations of 108 natural images, achieving 98% of the ROC area of a human-based control, whereas the classical algorithms of Itti & Koch ([2], [3], [4]) achieve only 84%.
Doubly Stochastic Normalization for Spectral Clustering
Authors: Ron Zass, Amnon Shashua
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: In this paper we focus on the issue of normalization of the affinity matrix in spectral clustering. We show that the difference between N-cuts and Ratio-cuts is in the error measure being used (relative-entropy versus L1 norm) in finding the closest doubly-stochastic matrix to the input affinity matrix. We then develop a scheme for finding the optimal, under Frobenius norm, doubly-stochastic approximation using Von-Neumann's successive projections lemma. The new normalization scheme is simple and efficient and provides superior clustering performance over many of the standardized tests.
A Scalable Machine Learning Approach to Go
Authors: Lin Wu, Pierre F. Baldi
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Go is an ancient board game that poses unique opportunities and challenges for AI and machine learning. Here we develop a machine learning approach to Go, and related board games, focusing primarily on the problem of learning a good eval- uation function in a scalable way. Scalability is essential at multiple levels, from the library of local tactical patterns, to the integration of patterns across the board, to the size of the board itself. The system we propose is capable of automatically learning the propensity of local patterns from a library of games. Propensity and other local tactical information are fed into a recursive neural network, derived from a Bayesian network architecture. The network integrates local information across the board and produces local outputs that represent local territory owner- ship probabilities. The aggregation of these probabilities provides an effective strategic evaluation function that is an estimate of the expected area at the end (or at other stages) of the game. Local area targets for training can be derived from datasets of human games. A system trained using only 9 × 9 amateur game data performs surprisingly well on a test set derived from 19 × 19 professional game data. Possible directions for further improvements are brieﬂy discussed.
Stratification Learning: Detecting Mixed Density and Dimensionality in High Dimensional Point Clouds
Authors: Gloria Haro, Gregory Randall, Guillermo Sapiro
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: The study of point cloud data sampled from a stratification, a collection of manifolds with possible different dimensions, is pursued in this paper. We present a technique for simultaneously soft clustering and estimating the mixed dimensionality and density of such structures. The framework is based on a maximum likelihood estimation of a Poisson mixture model. The presentation of the approach is completed with artificial and real examples demonstrating the importance of extending manifold learning to stratification learning.
A Collapsed Variational Bayesian Inference Algorithm for Latent Dirichlet Allocation
Authors: Yee W. Teh, David Newman, Max Welling
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Latent Dirichlet allocation (LDA) is a Bayesian network that has recently gained much popularity in applications ranging from document modeling to computer vision. Due to the large scale nature of these applications, current inference pro- cedures like variational Bayes and Gibbs sampling have been found lacking. In this paper we propose the collapsed variational Bayesian inference algorithm for LDA, and show that it is computationally efﬁcient, easy to implement and signiﬁ- cantly more accurate than standard variational Bayesian inference for LDA.
Dynamic Foreground/Background Extraction from Images and Videos using Random Patches
Authors: Le Lu, Gregory D. Hager
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: In this paper, we propose a novel exemplar-based approach to extract dynamic foreground regions from a changing background within a collection of images or a video sequence. By using image segmentation as a pre-processing step, we convert this traditional pixel-wise labeling problem into a lower-dimensional supervised, binary labeling procedure on image segments. Our approach consists of three steps. First, a set of random image patches are spatially and adaptively sampled within each segment. Second, these sets of extracted samples are formed into two "bags of patches" to model the foreground/background appearance, respectively. We perform a novel bidirectional consistency check between new patches from incoming frames and current "bags of patches" to reject outliers, control model rigidity and make the model adaptive to new observations. Within each bag, image patches are further partitioned and resampled to create an evolving appearance model. Finally, the foreground/background decision over segments in an image is formulated using an aggregation function defined on the similarity measurements of sampled patches relative to the foreground and background models. The essence of the algorithm is conceptually simple and can be easily implemented within a few hundred lines of Matlab code. We evaluate and validate the proposed approach by extensive real examples of the object-level image mapping and tracking within a variety of challenging environments. We also show that it is straightforward to apply our problem formulation on non-rigid object tracking with difficult surveillance videos.
Subordinate class recognition using relational object models
Authors: Aharon B. Hillel, Daphna Weinshall
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We address the problem of sub-ordinate class recognition, like the distinction between different types of motorcycles. Our approach is motivated by observations from cognitive psychology, which identify parts as the defining component of basic level categories (like motorcycles), while sub-ordinate categories are more often defined by part properties (like 'jagged wheels'). Accordingly, we suggest a two-stage algorithm: First, a relational part based object model is learnt using unsegmented object images from the inclusive class (e.g., motorcycles in general). The model is then used to build a class-specific vector representation for images, where each entry corresponds to a model's part. In the second stage we train a standard discriminative classifier to classify subclass instances (e.g., cross motorcycles) based on the class-specific vector representation. We describe extensive experimental results with several subclasses. The proposed algorithm typically gives better results than a competing one-step algorithm, or a two stage algorithm where classification is based on a model of the sub-ordinate class.
Dirichlet-Enhanced Spam Filtering based on Biased Samples
Authors: Steffen Bickel, Tobias Scheffer
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We study a setting that is motivated by the problem of filtering spam messages for many users. Each user receives messages according to an individual, unknown distribution, reflected only in the unlabeled inbox. The spam filter for a user is required to perform well with respect to this distribution. Labeled messages from publicly available sources can be utilized, but they are governed by a distinct distribution, not adequately representing most inboxes. We devise a method that minimizes a loss function with respect to a user's personal distribution based on the available biased sample. A nonparametric hierarchical Bayesian model furthermore generalizes across users by learning a common prior which is imposed on new email accounts. Empirically, we observe that bias-corrected learning outperforms naive reliance on the assumption of independent and identically distributed data; Dirichlet-enhanced generalization across users outperforms a single ("one size fits all") filter as well as independent filters for all users.
Stability of $K$-Means Clustering
Authors: Alexander Rakhlin, Andrea Caponnetto
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We phrase K -means clustering as an empirical risk minimization procedure over a class HK and explicitly calculate the covering number for this class. Next, we show that stability of K -means clustering is characterized by the geometry of HK with respect to the underlying distribution. We prove that in the case of a unique global minimizer, the clustering solution is stable with respect to complete changes of the data, while for the case of multiple minimizers, the change of (n1/2 ) samples defines the transition between stability and instability. While for a finite number of minimizers this result follows from multinomial distribution estimates, the case of infinite minimizers requires more refined tools. We conclude by proving that stability of the functions in HK implies stability of the actual centers of the clusters. Since stability is often used for selecting the number of clusters in practice, we hope that our analysis serves as a starting point for finding theoretically grounded recipes for the choice of K .
Convergence of Laplacian Eigenmaps
Authors: Mikhail Belkin, Partha Niyogi
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Geometrically based methods for various tasks of machine learning have attracted considerable attention over the last few years. In this paper we show convergence of eigenvectors of the point cloud Laplacian to the eigen- functions of the Laplace-Beltrami operator on the underlying manifold, thus establishing the ﬁrst convergence results for a spectral dimensionality re- duction algorithm in the manifold setting.
Bayesian Policy Gradient Algorithms
Authors: Mohammad Ghavamzadeh, Yaakov Engel
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Policy gradient methods are reinforcement learning algorithms that adapt a param- eterized policy by following a performance gradient estimate. Conventional pol- icy gradient methods use Monte-Carlo techniques to estimate this gradient. Since Monte Carlo methods tend to have high variance, a large number of samples is required, resulting in slow convergence. In this paper, we propose a Bayesian framework that models the policy gradient as a Gaussian process. This reduces the number of samples needed to obtain accurate gradient estimates. Moreover, estimates of the natural gradient as well as a measure of the uncertainty in the gradient estimates are provided at little extra cost.
Handling Advertisements of Unknown Quality in Search Advertising
Authors: Sandeep Pandey, Christopher Olston
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We consider how a search engine should select advertisements to display with search results, in order to maximize its revenue. Under the standard "pay-per-click" arrangement, revenue depends on how well the displayed advertisements appeal to users. The main difficulty stems from new advertisements whose degree of appeal has yet to be determined. Often the only reliable way of determining appeal is exploration via display to users, which detracts from exploitation of other advertisements known to have high appeal. Budget constraints and finite advertisement lifetimes make it necessary to explore as well as exploit. In this paper we study the tradeoff between exploration and exploitation, modeling advertisement placement as a multi-armed bandit problem. We extend traditional bandit formulations to account for budget constraints that occur in search engine advertising markets, and derive theoretical bounds on the performance of a family of algorithms. We measure empirical performance via extensive experiments over real-world data.
Part-based Probabilistic Point Matching using Equivalence Constraints
Authors: Graham Mcneill, Sethu Vijayakumar
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Correspondence algorithms typically struggle with shapes that display part-based variation. We present a probabilistic approach that matches shapes using independent part transformations, where the parts themselves are learnt during matching. Ideas from semi-supervised learning are used to bias the algorithm towards finding `perceptually valid' part structures. Shapes are represented by unlabeled point sets of arbitrary size and a background component is used to handle occlusion, local dissimilarity and clutter. Thus, unlike many shape matching techniques, our approach can be applied to shapes extracted from real images. Model parameters are estimated using an EM algorithm that alternates between finding a soft correspondence and computing the optimal part transformations using Procrustes analysis.
Temporal dynamics of information content carried by neurons in the primary visual cortex
Authors: Danko Nikolić, Stefan Haeusler, Wolf Singer, Wolfgang Maass
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We  use  multi-electrode recordings from  cat primary visual cortex and investigate 
whether a simple linear classifier can extract information about the presented stim(cid:173)
uli.  We  find  that information is extractable and that it even lasts for several hun(cid:173)
dred milliseconds after the stimulus has been removed.  In a fast sequence of stim(cid:173)
ulus  presentation,  information  about both  new  and  old  stimuli  is  present simul(cid:173)
taneously  and nonlinear relations between  these  stimuli can  be extracted.  These 
results suggest nonlinear properties of cortical representations.  The important im(cid:173)
plications of these properties for the nonlinear brain theory are discussed.
Automated Hierarchy Discovery for Planning in Partially Observable Environments
Authors: Laurent Charlin, Pascal Poupart, Romy Shioda
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Planning in partially observable domains is a notoriously difﬁcult problem. How- ever, in many real-world scenarios, planning can be simpliﬁed by decomposing the task into a hierarchy of smaller planning problems. Several approaches have been proposed to optimize a policy that decomposes according to a hierarchy speciﬁed a priori. In this paper, we investigate the problem of automatically discovering the hierarchy. More precisely, we frame the optimization of a hierarchical policy as a non-convex optimization problem that can be solved with general non-linear solvers, a mixed-integer non-linear approximation or a form of bounded hierar- chical policy iteration. By encoding the hierarchical structure as variables of the optimization problem, we can automatically discover a hierarchy. Our method is ﬂexible enough to allow any parts of the hierarchy to be speciﬁed based on prior knowledge while letting the optimization discover the unknown parts. It can also discover hierarchical policies, including recursive policies, that are more compact (potentially inﬁnitely fewer parameters) and often easier to understand given the decomposition induced by the hierarchy.
Adaptor Grammars: A Framework for Specifying Compositional Nonparametric Bayesian Models
Authors: Mark Johnson, Thomas L. Griffiths, Sharon Goldwater
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: This paper introduces adaptor grammars, a class of probabilistic models of lan- guage that generalize probabilistic context-free grammars (PCFGs). Adaptor grammars augment the probabilistic rules of PCFGs with “adaptors” that can in- duce dependencies among successive uses. With a particular choice of adaptor, based on the Pitman-Yor process, nonparametric Bayesian models of language using Dirichlet processes and hierarchical Dirichlet processes can be written as simple grammars. We present a general-purpose inference algorithm for adaptor grammars, making it easy to deﬁne and use such models, and illustrate how several existing nonparametric Bayesian models can be expressed within this framework.
On Transductive Regression
Authors: Corinna Cortes, Mehryar Mohri
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: In many modern large-scale learning applications, the amount of unlabeled data far exceeds that of labeled data. A common instance of this problem is the transductive setting where the unlabeled test points are known to the learning algorithm. This paper presents a study of regression problems in that setting. It presents explicit VC-dimension error bounds for transductive regression that hold for all bounded loss functions and coincide with the tight classification bounds of Vapnik when applied to classification. It also presents a new transductive regression algorithm inspired by our bound that admits a primal and kernelized closedform solution and deals efficiently with large amounts of unlabeled data. The algorithm exploits the position of unlabeled points to locally estimate their labels and then uses a global optimization to ensure robust predictions. Our study also includes the results of experiments with several publicly available regression data sets with up to 20,000 unlabeled examples. The comparison with other transductive regression algorithms shows that it performs well and that it can scale to large data sets.
Large Margin Multi-channel Analog-to-Digital Conversion with Applications to Neural Prosthesis
Authors: Amit Gore, Shantanu Chakrabartty
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: A key challenge in designing analog-to-digital converters for cortically implanted prosthesis is to sense and process high-dimensional neural signals recorded by the micro-electrode arrays. In this paper, we describe a novel architecture for analog-to-digital (A/D) conversion that combines  conversion with spatial de-correlation within a single module. The architecture called multiple-input multiple-output (MIMO)  is based on a min-max gradient descent optimization of a regularized linear cost function that naturally lends to an A/D formulation. Using an online formulation, the architecture can adapt to slow variations in cross-channel correlations, observed due to relative motion of the microelectrodes with respect to the signal sources. Experimental results with real recorded multi-channel neural data demonstrate the effectiveness of the proposed algorithm in alleviating cross-channel redundancy across electrodes and performing data-compression directly at the A/D converter.
Comparative Gene Prediction using Conditional Random Fields
Authors: Jade P. Vinson, David Decaprio, Matthew D. Pearson, Stacey Luoma, James E. Galagan
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Computational gene prediction using generative models has reached a plateau, with several groups converging to a generalized hidden Markov model (GHMM) incorporating phylogenetic models of nucleotide sequence evolution. Further improvements in gene calling accuracy are likely to come through new methods that incorporate additional data, both comparative and species specific. Conditional Random Fields (CRFs), which directly model the conditional probability P (y |x) of a vector of hidden states conditioned on a set of observations, provide a unified framework for combining probabilistic and non-probabilistic information and have been shown to outperform HMMs on sequence labeling tasks in natural language processing. We describe the use of CRFs for comparative gene prediction. We implement a model that encapsulates both a phylogenetic-GHMM (our baseline comparative model) and additional non-probabilistic features. We tested our model on the genome sequence of the fungal human pathogen Cryptococcus neoformans. Our baseline comparative model displays accuracy comparable to the the best available gene prediction tool for this organism. Moreover, we show that discriminative training and the incorporation of non-probabilistic evidence significantly improve performance. Our software implementation, Conrad, is freely available with an open source license at http://www.broad.mit.edu/annotation/conrad/.
Learning annotated hierarchies from relational data
Authors: Daniel M. Roy, Charles Kemp, Vikash K. Mansinghka, Joshua B. Tenenbaum
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: The objects in many real-world domains can be organized into hierarchies, where each internal node picks out a category of objects. Given a collection of fea- tures and relations deﬁned over a set of objects, an annotated hierarchy includes a speciﬁcation of the categories that are most useful for describing each individual feature and relation. We deﬁne a generative model for annotated hierarchies and the features and relations that they describe, and develop a Markov chain Monte Carlo scheme for learning annotated hierarchies. We show that our model discov- ers interpretable structure in several real-world data sets.
A Small World Threshold for Economic Network Formation
Authors: Eyal Even-dar, Michael Kearns
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We introduce a game-theoretic model for network formation inspired by earlier stochastic models that mix localized and long-distance connectivity. In this model, players may purchase edges at distance d at a cost of d , and wish to minimize the sum of their edge purchases and their average distance to other players. In this model, we show there is a striking "small world" threshold phenomenon: in two dimensions, if  < 2 then every Nash equilibrium results in a network of constant diameter (independent of network size), and if  > 2 then every Nash equilibrium results in a network whose diameter grows as a root of the network size, and thus is unbounded. We contrast our results with those of Kleinberg [8] in a stochastic model, and empirically investigate the "navigability" of equilibrium networks. Our theoretical results all generalize to higher dimensions.
iLSTD: Eligibility Traces and Convergence Analysis
Authors: Alborz Geramifard, Michael Bowling, Martin Zinkevich, Richard S. Sutton
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We present new theoretical and empirical results with the iLSTD algorithm for policy evaluation in reinforcement learning with linear function approximation. iLSTD is an incremental method for achieving results similar to LSTD, the dataefficient, least-squares version of temporal difference learning, without incurring the full cost of the LSTD computation. LSTD is O(n2 ), where n is the number of parameters in the linear function approximator, while iLSTD is O(n). In this paper, we generalize the previous iLSTD algorithm and present three new results: (1) the first convergence proof for an iLSTD algorithm; (2) an extension to incorporate eligibility traces without changing the asymptotic computational complexity; and (3) the first empirical results with an iLSTD algorithm for a problem (mountain car) with feature vectors large enough (n = 10, 000) to show substantial computational advantages over LSTD.
Sparse Kernel Orthonormalized PLS for feature extraction in large data sets
Authors: Jerónimo Arenas-garcía, Kaare B. Petersen, Lars K. Hansen
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: In this paper we are presenting a novel multivariate analysis method. Our scheme is based on a novel kernel orthonormalized partial least squares (PLS) variant for feature extraction, imposing sparsity constrains in the solution to improve scalability. The algorithm is tested on a benchmark of UCI data sets, and on the analysis of integrated short-time music features for genre prediction. The upshot is that the method has strong expressive power even with rather few features, is clearly outperforming the ordinary kernel PLS, and therefore is an appealing method for feature extraction of labelled data.
Data Integration for Classification Problems Employing Gaussian Process Priors
Authors: Mark Girolami, Mingjun Zhong
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: By adopting Gaussian process priors a fully Bayesian solution to the problem of integrating possibly heterogeneous data sets within a classification setting is presented. Approximate inference schemes employing Variational & Expectation Propagation based methods are developed and rigorously assessed. We demonstrate our approach to integrating multiple data sets on a large scale protein fold prediction problem where we infer the optimal combinations of covariance functions and achieve state-of-the-art performance without resorting to any ad hoc parameter tuning and classifier combination.
Stochastic Relational Models for Discriminative Link Prediction
Authors: Kai Yu, Wei Chu, Shipeng Yu, Volker Tresp, Zhao Xu
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We introduce a Gaussian process (GP) framework, stochastic relational models (SRM), for learning social, physical, and other relational phenomena where interactions between entities are observed. The key idea is to model the stochastic structure of entity relationships (i.e., links) via a tensor interaction of multiple GPs, each defined on one type of entities. These models in fact define a set of nonparametric priors on infinite dimensional tensor matrices, where each element represents a relationship between a tuple of entities. By maximizing the marginalized likelihood, information is exchanged between the participating GPs through the entire relational network, so that the dependency structure of links is messaged to the dependency of entities, reflected by the adapted GP kernels. The framework offers a discriminative approach to link prediction, namely, predicting the existences, strengths, or types of relationships based on the partially observed linkage network as well as the attributes of entities (if given). We discuss properties and variants of SRM and derive an efficient learning algorithm. Very encouraging experimental results are achieved on a toy problem and a user-movie preference link prediction task. In the end we discuss extensions of SRM to general relational learning tasks.
Adaptive Spatial Filters with predefined Region of Interest for EEG based Brain-Computer-Interfaces
Authors: Moritz Grosse-wentrup, Klaus Gramann, Martin Buss
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: The performance of EEG-based Brain-Computer-Interfaces (BCIs) critically depends on the extraction of features from the EEG carrying information relevant for the classification of different mental states. For BCIs employing imaginary movements of different limbs, the method of Common Spatial Patterns (CSP) has been shown to achieve excellent classification results. The CSP-algorithm however suffers from a lack of robustness, requiring training data without artifacts for good performance. To overcome this lack of robustness, we propose an adaptive spatial filter that replaces the training data in the CSP approach by a-priori information. More specifically, we design an adaptive spatial filter that maximizes the ratio of the variance of the electric field originating in a predefined region of interest (ROI) and the overall variance of the measured EEG. Since it is known that the component of the EEG used for discriminating imaginary movements originates in the motor cortex, we design two adaptive spatial filters with the ROIs centered in the hand areas of the left and right motor cortex. We then use these to classify EEG data recorded during imaginary movements of the right and left hand of three subjects, and show that the adaptive spatial filters outperform the CSP-algorithm, enabling classification rates of up to 94.7 % without artifact rejection.
A recipe for optimizing a time-histogram
Authors: Hideaki Shimazaki, Shigeru Shinomoto
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: The time-histogram method is a handy tool for capturing the instantaneous rate of spike occurrence. In most of the neurophysiological literature, the bin size that critically determines the goodness of the fit of the time-histogram to the underlying rate has been selected by individual researchers in an unsystematic manner. We propose an objective method for selecting the bin size of a time-histogram from the spike data, so that the time-histogram best approximates the unknown underlying rate. The resolution of the histogram increases, or the optimal bin size decreases, with the number of spike sequences sampled. It is notable that the optimal bin size diverges if only a small number of experimental trials are available from a moderately fluctuating rate process. In this case, any attempt to characterize the underlying spike rate will lead to spurious results. Given a paucity of data, our method can also suggest how many more trials are needed until the set of data can be analyzed with the required resolution.
Inducing Metric Violations in Human Similarity Judgements
Authors: Julian Laub, Klaus-Robert Müller, Felix A. Wichmann, Jakob H. Macke
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Attempting to model human categorization and similarity judgements is both a very interesting but also an exceedingly difficult challenge. Some of the difficulty arises because of conflicting evidence whether human categorization and similarity judgements should or should not be modelled as to operate on a mental representation that is essentially metric. Intuitively, this has a strong appeal as it would allow (dis)similarity to be represented geometrically as distance in some internal space. Here we show how a single stimulus, carefully constructed in a psychophysical experiment, introduces l2 violations in what used to be an internal similarity space that could be adequately modelled as Euclidean. We term this one influential data point a conflictual judgement. We present an algorithm of how to analyse such data and how to identify the crucial point. Thus there may not be a strict dichotomy between either a metric or a non-metric internal space but rather degrees to which potentially large subsets of stimuli are represented metrically with a small subset causing a global violation of metricity.
Nonnegative Sparse PCA
Authors: Ron Zass, Amnon Shashua
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We describe a nonnegative variant of the "Sparse PCA" problem. The goal is to create a low dimensional representation from a collection of points which on the one hand maximizes the variance of the projected points and on the other uses only parts of the original coordinates, and thereby creating a sparse representation. What distinguishes our problem from other Sparse PCA formulations is that the projection involves only nonnegative weights of the original coordinates -- a desired quality in various fields, including economics, bioinformatics and computer vision. Adding nonnegativity contributes to sparseness, where it enforces a partitioning of the original coordinates among the new axes. We describe a simple yet efficient iterative coordinate-descent type of scheme which converges to a local optimum of our optimization criteria, giving good results on large real world datasets.
Context dependent amplification of both rate and event-correlation in a VLSI network of spiking neurons
Authors: Elisabetta Chicca, Giacomo Indiveri, Rodney J. Douglas
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Cooperative competitive networks are believed to play a central role in cortical processing and have been shown to exhibit a wide set of useful computational properties. We propose a VLSI implementation of a spiking cooperative competitive network and show how it can perform context dependent computation both in the mean firing rate domain and in spike timing correlation space. In the mean rate case the network amplifies the activity of neurons belonging to the selected stimulus and suppresses the activity of neurons receiving weaker stimuli. In the event correlation case, the recurrent network amplifies with a higher gain the correlation between neurons which receive highly correlated inputs while leaving the mean firing rate unaltered. We describe the network architecture and present experimental data demonstrating its context dependent computation capabilities.
PAC-Bayes Bounds for the Risk of the Majority Vote and the Variance of the Gibbs Classifier
Authors: Alexandre Lacasse, François Laviolette, Mario Marchand, Pascal Germain, Nicolas Usunier
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We propose new PAC-Bayes bounds for the risk of the weighted majority vote that depend on the mean and variance of the error of its associated Gibbs classiﬁer. We show that these bounds can be smaller than the risk of the Gibbs classiﬁer and can be arbitrarily close to zero even if the risk of the Gibbs classiﬁer is close to 1/2. Moreover, we show that these bounds can be uniformly estimated on the training data for all possible posteriors Q. Moreover, they can be improved by using a large sample of unlabelled data.
Generalized Regularized Least-Squares Learning with Predefined Features in a Hilbert Space
Authors: Wenye Li, Kin-hong Lee, Kwong-sak Leung
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Kernel-based regularized learning seeks a model in a hypothesis space by minimizing the empirical error and the model's complexity. Based on the representer theorem, the solution consists of a linear combination of translates of a kernel. This paper investigates a generalized form of representer theorem for kernel-based learning. After mapping predefined features and translates of a kernel simultaneously onto a hypothesis space by a specific way of constructing kernels, we proposed a new algorithm by utilizing a generalized regularizer which leaves part of the space unregularized. Using a squared-loss function in calculating the empirical error, a simple convex solution is obtained which combines predefined features with translates of the kernel. Empirical evaluations have confirmed the effectiveness of the algorithm for supervised learning tasks.
Map-Reduce for Machine Learning on Multicore
Authors: Cheng-tao Chu, Sang K. Kim, Yi-an Lin, Yuanyuan Yu, Gary Bradski, Kunle Olukotun, Andrew Y. Ng
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We are at the beginning of the multicore era. Computers will have increasingly many cores (processors), but there is still no good programming framework for these architectures, and thus no simple and unified way for machine learning to take advantage of the potential speed up. In this paper, we develop a broadly applicable parallel programming method, one that is easily applied to many different learning algorithms. Our work is in distinct contrast to the tradition in machine learning of designing (often ingenious) ways to speed up a single algorithm at a time. Specifically, we show that algorithms that fit the Statistical Query model [15] can be written in a certain "summation form," which allows them to be easily parallelized on multicore computers. We adapt Google's map-reduce [7] paradigm to demonstrate this parallel speed up technique on a variety of learning algorithms including locally weighted linear regression (LWLR), k-means, logistic regression (LR), naive Bayes (NB), SVM, ICA, PCA, gaussian discriminant analysis (GDA), EM, and backpropagation (NN). Our experimental results show basically linear speedup with an increasing number of processors.
Natural Actor-Critic for Road Traffic Optimisation
Authors: Silvia Richter, Douglas Aberdeen, Jin Yu
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Current road-traffic optimisation practice around the world is a combination of hand tuned policies with a small degree of automatic adaption. Even state-ofthe-art research controllers need good models of the road traffic, which cannot be obtained directly from existing sensors. We use a policy-gradient reinforcement learning approach to directly optimise the traffic signals, mapping currently deployed sensor observations to control signals. Our trained controllers are (theoretically) compatible with the traffic system used in Sydney and many other cities around the world. We apply two policy-gradient methods: (1) the recent natural actor-critic algorithm, and (2) a vanilla policy-gradient algorithm for comparison. Along the way we extend natural-actor critic approaches to work for distributed and online infinite-horizon problems.
Implicit Surfaces with Globally Regularised and Compactly Supported Basis Functions
Authors: Christian Walder, Olivier Chapelle, Bernhard Schölkopf
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We consider the problem of constructing a function whose zero set is to represent a surface, given sample points with surface normal vectors. The contributions include a novel means of regularising multi-scale compactly supported basis functions that leads to the desirable properties previously only associated with fully supported bases, and show equivalence to a Gaussian process with modified covariance function. We also provide a regularisation framework for simpler and more direct treatment of surface normals, along with a corresponding generalisation of the representer theorem. We demonstrate the techniques on 3D problems of up to 14 million data points, as well as 4D time series data.
Multiple Instance Learning for Computer Aided Diagnosis
Authors: Murat Dundar, Balaji Krishnapuram, R. B. Rao, Glenn M. Fung
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Many computer aided diagnosis (CAD) problems can be best modelled as a multiple-instance learning (MIL) problem with unbalanced data: i.e. , the training data typically consists of a few positive bags, and a very large number of negative instances. Existing MIL algorithms are much too computationally expensive for these datasets. We describe CH, a framework for learning a Convex Hull representation of multiple instances that is significantly faster than existing MIL algorithms. Our CH framework applies to any standard hyperplane-based learning algorithm, and for some algorithms, is guaranteed to find the global optimal solution. Experimental studies on two different CAD applications further demonstrate that the proposed algorithm significantly improves diagnostic accuracy when compared to both MIL and traditional classifiers. Although not designed for standard MIL problems (which have both positive and negative bags and relatively balanced datasets), comparisons against other MIL methods on benchmark problems also indicate that the proposed method is competitive with the state-of-the-art.
A selective attention multi--chip system with dynamic synapses and spiking neurons
Authors: Chiara Bartolozzi, Giacomo Indiveri
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Selective attention is the strategy used by biological sensory systems to solve the problem of limited parallel processing capacity: salient subregions of the input stimuli are serially processed, while nonsalient regions are suppressed. We present an mixed mode analog/digital Very Large Scale Integration implementation of a building block for a multichip neuromorphic hardware model of selective attention. We describe the chip's architecture and its behavior, when its is part of a multichip system with a spiking retina as input, and show how it can be used to implement in real-time flexible models of bottom-up attention.
High-Dimensional Graphical Model Selection Using $\ell_1$-Regularized Logistic Regression
Authors: Martin J. Wainwright, John D. Lafferty, Pradeep K. Ravikumar
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We focus on the problem of estimating the graph structure associated with a discrete Markov random ﬁeld. We describe a method based on 1- regularized logistic regression, in which the neighborhood of any given node is estimated by performing logistic regression subject to an1-constraint. Our framework applies to the high-dimensional setting, in which both the number of nodes p and maximum neighborhood sizes d are allowed to grow as a function of the number of observations n. Our main result is to estab- lish suﬃcient conditions on the triple (n, p, d) for the method to succeed in consistently estimating the neighborhood of every node in the graph simul- taneously. Under certain mutual incoherence conditions analogous to those imposed in previous work on linear regression, we prove that consistent neighborhood selection can be obtained as long as the number of observa- tions n grows more quickly than 6d6 log d + 2d5 log p, thereby establishing that logarithmic growth in the number of samples n relative to graph size p is suﬃcient to achieve neighborhood consistency.
Keywords: Graphical models; Markov random ﬁelds; structure learning; `1-regularization; model selection; convex risk minimization; high-dimensional asymptotics; concentration.
Efficient Learning of Sparse Representations with an Energy-Based Model
Authors: Marc'aurelio Ranzato, Christopher Poultney, Sumit Chopra, Yann L. Cun
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We describe a novel unsupervised method for learning sparse, overcomplete features. The model uses a linear encoder, and a linear decoder preceded by a sparsifying non-linearity that turns a code vector into a quasi-binary sparse code vector. Given an input, the optimal code minimizes the distance between the output of the decoder and the input patch while being as similar as possible to the encoder output. Learning proceeds in a two-phase EM-like fashion: (1) compute the minimum-energy code vector, (2) adjust the parameters of the encoder and decoder so as to decrease the energy. The model produces "stroke detectors" when trained on handwritten numerals, and Gabor-like filters when trained on natural image patches. Inference and learning are very fast, requiring no preprocessing, and no expensive sampling. Using the proposed unsupervised method to initialize the first layer of a convolutional network, we achieved an error rate slightly lower than the best reported result on the MNIST dataset. Finally, an extension of the method is described to learn topographical filter maps.