mtybilly/Instruct2DS huggingface dataset:
Temporal Coding using the Response Properties of Spiking Neurons
Authors: Thomas Voegtlin
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: In biological neurons, the timing of a spike depends on the timing of synaptic currents, in a way that is classically described by the Phase Response Curve. This has implications for temporal coding: an action potential that arrives on a synapse has an implicit meaning, that depends on the position of the postsynaptic neuron on the firing cycle. Here we show that this implicit code can be used to perform computations. Using theta neurons, we derive a spike-timing dependent learning rule from an error criterion. We demonstrate how to train an a uto-encoder neural network using this rule.
A Nonparametric Bayesian Method for Inferring Features From Similarity Judgments
Authors: Thomas L. Griffiths Daniel J. Navarro
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: The additive clustering model is widely used to infer the features of a set of stimuli from their similarities, on the assumption that similarity is a weighted linear function of common features. This paper develops a fully Bayesian formulation of the additive clustering model, using methods from nonparametric Bayesian statistics to allow the number of features to vary. We use this to explore several approaches to parameter estimation, showing that the nonparametric Bayesian approach provides a straightforward way to obtain estimates of both the number of features used in producing similarity judgments and their importance.
Hierarchical Dirichlet Processes with Random Effects
Authors: Padhraic Smyth Seyoung Kim
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Data sets involving multiple groups with shared characteristics frequently arise in practice. In this paper we extend hierarchical Dirichlet processes to model such data. Each group is assumed to be generated from a template mixture model with group level variability in both the mixing proportions and the component parameters. Variabilities in mixing proportions across groups are handled using hierarchical Dirichlet processes, also allowing for automatic determination of the number of components. In addition, each group is allowed to have its own compo- nent parameters coming from a prior described by a template mixture model. This group-level variability in the component parameters is handled using a random effects model. We present a Markov Chain Monte Carlo (MCMC) sampling algo- rithm to estimate model parameters and demonstrate the method by applying it to the problem of modeling spatial brain activation patterns across multiple images collected via functional magnetic resonance imaging (fMRI).
Bayesian Model Scoring in Markov Random Fields
Authors: Max Welling Sridevi Parise
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Scoring structures of undirected graphical models by means of evaluating the marginal likelihood is very hard. The main reason is the presence of the parti- tion function which is intractable to evaluate, let alone integrate over. We propose to approximate the marginal likelihood by employing two levels of approximation: we assume normality of the posterior (the Laplace approximation) and approxi- mate all remaining intractable quantities using belief propagation and the linear response approximation. This results in a fast procedure for model scoring. Em- pirically, we ﬁnd that our procedure has about two orders of magnitude better accuracy than standard BIC methods for small datasets, but deteriorates when the size of the dataset grows.
Isotonic Conditional Random Fields and Local Sentiment Flow
Authors: Guy Lebanon Yi Mao
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We examine the problem of predicting local sentiment flow in documents, and its application to several areas of text analysis. Formally, the problem is stated as predicting an ordinal sequence based on a sequence of word sets. In the spirit of isotonic regression, we develop a variant of conditional random fields that is well suited to handle this problem. Using the Mobius transform, we express the model as a simple convex optimization problem. Experiments demonstrate the model and its applications to sentiment prediction, style analysis, and text summarization.
Logistic Regression for Single Trial EEG Classification
Authors: Kazuyuki Aihara, Klaus-Robert Müller Ryota Tomioka
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We propose a novel framework for the classification of single trial ElectroEncephaloGraphy (EEG), based on regularized logistic regression. Framed in this robust statistical framework no prior feature extraction or outlier removal is required. We present two variations of parameterizing the regression function: (a) with a full rank symmetric matrix coefficient and (b) as a difference of two rank=1 matrices. In the first case, the problem is convex and the logistic regression is optimal under a generative model. The latter case is shown to be related to the Common Spatial Pattern (CSP) algorithm, which is a popular technique in Brain Computer Interfacing. The regression coefficients can also be topographically mapped onto the scalp similarly to CSP pro jections, which allows neuro-physiological interpretation. Simulations on 162 BCI datasets demonstrate that classification accuracy and robustness compares favorably against conventional CSP based classifiers.
A Local Learning Approach for Clustering
Authors: Bernhard Schölkopf Mingrui Wu
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We present a local learning approach for clustering. The basic idea is that a good clustering result should have the property that the cluster label of each data point can be well predicted based on its neighboring data and their cluster labels, using current supervised learning methods. An optimization problem is formulated such that its solution has the above property. Relaxation and eigen-decomposition are applied to solve this optimization problem. We also briefly investigate the parameter selection issue and provide a simple parameter selection method for the proposed algorithm. Experimental results are provided to validate the effectiveness of the proposed approach.
Temporal and Cross-Subject Probabilistic Models for fMRI Prediction Tasks
Authors: Gal Chechik, Daphne Koller Alexis Battle
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We present a probabilistic model applied to the fMRI video rating prediction task of the Pittsburgh Brain Activity Interpretation Competition (PBAIC) [2]. Our goal is to predict a time series of subjective, semantic ratings of a movie given functional MRI data acquired during viewing by three subjects. Our method uses conditionally trained Gaussian Markov random fields, which model both the relationships between the subjects' fMRI voxel measurements and the ratings, as well as the dependencies of the ratings across time steps and between subjects. We also employed non-traditional methods for feature selection and regularization that exploit the spatial structure of voxel activity in the brain. The model displayed good performance in predicting the scored ratings for the three subjects in test data sets, and a variant of this model was the third place entrant to the 2006 PBAIC.
Particle Filtering for Nonparametric Bayesian Matrix Factorization
Authors: Thomas L. Griffiths Frank Wood
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Many unsupervised learning problems can be expressed as a form of matrix factorization, reconstructing an observed data matrix as the product of two matrices of latent variables. A standard challenge in solving these problems is determining the dimensionality of the latent matrices. Nonparametric Bayesian matrix factorization is one way of dealing with this challenge, yielding a posterior distribution over possible factorizations of unbounded dimensionality. A drawback to this approach is that posterior estimation is typically done using Gibbs sampling, which can be slow for large problems and when conjugate priors cannot be used. As an alternative, we present a particle filter for posterior estimation in nonparametric Bayesian matrix factorization models. We illustrate this approach with two matrix factorization models and show favorable performance relative to Gibbs sampling.
Large-Scale Sparsified Manifold Regularization
Authors: James T. Kwok Ivor W. Tsang
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Semi-supervised learning is more powerful than supervised learning by using both labeled and unlabeled data. In particular, the manifold regularization framework, together with kernel methods, leads to the Laplacian SVM (LapSVM) that has demonstrated state-of-the-art performance. However, the LapSVM solution typically involves kernel expansions of all the labeled and unlabeled examples, and is slow on testing. Moreover, existing semi-supervised learning methods, including the LapSVM, can only handle a small number of unlabeled examples. In this paper, we integrate manifold regularization with the core vector machine, which has been used for large-scale supervised and unsupervised learning. By using a sparsified manifold regularizer and formulating as a center-constrained minimum enclosing ball problem, the proposed method produces sparse solutions with low time and space complexities. Experimental results show that it is much faster than the LapSVM, and can handle a million unlabeled examples on a standard PC; while the LapSVM can only handle several thousand patterns.
Non-rigid point set registration: Coherent Point Drift
Authors: Xubo Song, Miguel Á. Carreira-Perpiñán Andriy Myronenko
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We introduce Coherent Point Drift (CPD), a novel probabilistic method for nonrigid registration of point sets. The registration is treated as a Maximum Likelihood (ML) estimation problem with motion coherence constraint over the velocity field such that one point set moves coherently to align with the second set. We formulate the motion coherence constraint and derive a solution of regularized ML estimation through the variational approach, which leads to an elegant kernel form. We also derive the EM algorithm for the penalized ML optimization with deterministic annealing. The CPD method simultaneously finds both the non-rigid transformation and the correspondence between two point sets without making any prior assumption of the transformation model except that of motion coherence. This method can estimate complex non-linear non-rigid transformations, and is shown to be accurate on 2D and 3D examples and robust in the presence of outliers and missing points.
Learning Nonparametric Models for Probabilistic Imitation
Authors: Daniel R. Rashid, Rajesh P. Rao David B. Grimes
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Learning by imitation represents an important mechanism for rapid acquisition of new behaviors in humans and robots. A critical requirement for learning by imitation is the ability to handle uncertainty arising from the observation process as well as the imitator's own dynamics and interactions with the environment. In this paper, we present a new probabilistic method for inferring imitative actions that takes into account both the observations of the teacher as well as the imitator's dynamics. Our key contribution is a nonparametric learning method which generalizes to systems with very different dynamics. Rather than relying on a known forward model of the dynamics, our approach learns a nonparametric forward model via exploration. Leveraging advances in approximate inference in graphical models, we show how the learned forward model can be directly used to plan an imitating sequence. We provide experimental results for two systems: a biomechanical model of the human arm and a 25-degrees-of-freedom humanoid robot. We demonstrate that the proposed method can be used to learn appropriate motor inputs to the model arm which imitates the desired movements. A second set of results demonstrates dynamically stable full-body imitation of a human teacher by the humanoid robot.
Active learning for misspecified generalized linear models
Authors: Francis R. Bach
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Active learning refers to algorithmic frameworks aimed at selecting training data points in order to reduce the number of required training data points and/or im- prove the generalization performance of a learning method. In this paper, we present an asymptotic analysis of active learning for generalized linear models. Our analysis holds under the common practical situation of model misspeciﬁca- tion, and is based on realistic assumptions regarding the nature of the sampling distributions, which are usually neither independent nor identical. We derive un- biased estimators of generalization performance, as well as estimators of expected reduction in generalization error after adding a new training data point, that allow us to optimize its sampling distribution through a convex optimization problem. Our analysis naturally leads to an algorithm for sequential active learning which is applicable for all tasks supported by generalized linear models (e.g., binary clas- siﬁcation, multi-class classiﬁcation, regression) and can be applied in non-linear settings through the use of Mercer kernels.
Tighter PAC-Bayes Bounds
Authors: Emilio Parrado-hernández, John S. Shawe-taylor Amiran Ambroladze
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: This paper proposes a PAC-Bayes bound to measure the performance of Support Vector Machine (SVM) classiﬁers. The bound is based on learning a prior over the distribution of classiﬁers with a part of the training samples. Experimental work shows that this bound is tighter than the original PAC-Bayes, resulting in an enhancement of the predictive capabilities of the PAC-Bayes bound. In addition, it is shown that the use of this bound as a means to estimate the hyperparameters of the classiﬁer compares favourably with cross validation in terms of accuracy of the model, while saving a lot of computational burden.
Near-Uniform Sampling of Combinatorial Spaces Using XOR Constraints
Authors: Ashish Sabharwal, Bart Selman Carla P. Gomes
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We propose a new technique for sampling the solutions of combinatorial problems in a near-uniform manner. We focus on problems specified as a Boolean formula, i.e., on SAT instances. Sampling for SAT problems has been shown to have interesting connections with probabilistic reasoning, making practical sampling algorithms for SAT highly desirable. The best current approaches are based on Markov Chain Monte Carlo methods, which have some practical limitations. Our approach exploits combinatorial properties of random parity (X O R) constraints to prune away solutions near-uniformly. The final sample is identified amongst the remaining ones using a state-of-the-art SAT solver. The resulting sampling distribution is provably arbitrarily close to uniform. Our experiments show that our technique achieves a significantly better sampling quality than the best alternative.
Recursive Attribute Factoring
Authors: Deepak Verma, Karl Pfleger David Cohn
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Clustering, or factoring of a document collection attempts to “explain” each ob- served document in terms of one or a small number of inferred prototypes. Prior work demonstrated that when links exist between documents in the corpus (as is the case with a collection of web pages or scientiﬁc papers), building a joint model of document contents and connections produces a better model than that built from contents or connections alone. Many problems arise when trying to apply these joint models to corpus at the scale of the World Wide Web, however; one of these is that the sheer overhead of representing a feature space on the order of billions of dimensions becomes impractical. We address this problem with a simple representational shift inspired by proba- bilistic relational models: instead of representing document linkage in terms of the identities of linking documents, we represent it by the explicit and inferred at- tributes of the linking documents. Several surprising results come with this shift: in addition to being computationally more tractable, the new model produces fac- tors that more cleanly decompose the document collection. We discuss several variations on this model and show how some can be seen as exact generalizations of the PageRank algorithm.
Information Bottleneck for Non Co-Occurrence Data
Authors: Noam Slonim, Naftali Tishby Yevgeny Seldin
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We present a general model-independent approach to the analysis of data in cases when these data do not appear in the form of co-occurrence of two variables X, Y , but rather as a sample of values of an unknown (stochastic) function Z (X, Y ). For example, in gene expression data, the expression level Z is a function of gene X and condition Y ; or in movie ratings data the rating Z is a function of viewer X and movie Y . The approach represents a consistent extension of the Information Bottleneck method that has previously relied on the availability of co-occurrence statistics. By altering the relevance variable we eliminate the need in the sample of joint distribution of all input variables. This new formulation also enables simple MDL-like model complexity control and prediction of missing values of Z . The approach is analyzed and shown to be on a par with the best known clustering algorithms for a wide range of domains. For the prediction of missing values (collaborative filtering) it improves the currently best known results.
A Probabilistic Algorithm Integrating Source Localization and Noise Suppression of MEG and EEG data
Authors: Hagai T. Attias, Kensuke Sekihara, Srikantan S. Nagarajan Johanna M. Zumer
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: We have developed a novel algorithm for integrating source localization and noise suppression based on a probabilistic graphical model of stimulus-evoked MEG/EEG data. Our algorithm localizes multiple dipoles while suppressing noise sources with the computational complexity equivalent to a single dipole scan, and is therefore more ef(cid:2)cient than traditional multidipole (cid:2)tting procedures. In simulation, the algorithm can accurately localize and estimate the time course of several simultaneously-active dipoles, with rotating or (cid:2)xed orientation, at noise levels typical for averaged MEG data. Furthermore, the algorithm is superior to beamforming techniques, which we show to be an approximation to our graphical model, in estimation of temporally correlated sources. Success of this algorithm for localizing auditory cortex in a tumor patient and for localizing an epileptic spike source are also demonstrated.
Attentional Processing on a Spike-Based VLSI Neural Network
Authors: Rodney J. Douglas, Shih-Chii Liu Yingxue Wang
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: Ian G. Fuss, Daniel J. Navarro Michael D. Lee
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: Christof Koch, Pietro Perona Jonathan Harel
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: Amnon Shashua Ron Zass
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: Pierre F. Baldi Lin Wu
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: Gregory Randall, Guillermo Sapiro Gloria Haro
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: David Newman, Max Welling Yee W. Teh
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: Gregory D. Hager Le Lu
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: Daphna Weinshall Aharon B. Hillel
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: Tobias Scheffer Steffen Bickel
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: Andrea Caponnetto Alexander Rakhlin
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: Partha Niyogi Mikhail Belkin
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: Yaakov Engel Mohammad Ghavamzadeh
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: Christopher Olston Sandeep Pandey
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: Sethu Vijayakumar Graham Mcneill
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.
Optimal Change-Detection and Spiking Neurons
Authors: Angela J. Yu
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: Survival in a non-stationary, potentially adversarial environment requires animals to detect sensory changes rapidly yet accurately, two oft competing desiderata. Neurons subserving such detections are faced with the corresponding challenge to discern "real" changes in inputs as quickly as possible, while ignoring noisy fluctuations. Mathematically, this is an example of a change-detection problem that is actively researched in the controlled stochastic processes community. In this paper, we utilize sophisticated tools developed in that community to formalize an instantiation of the problem faced by the nervous system, and characterize the Bayes-optimal decision policy under certain assumptions. We will derive from this optimal strategy an information accumulation and decision process that remarkably resembles the dynamics of a leaky integrate-and-fire neuron. This correspondence suggests that neurons are optimized for tracking input changes, and sheds new light on the computational import of intracellular properties such as resting membrane potential, voltage-dependent conductance, and post-spike reset voltage. We also explore the influence that factors such as timing, uncertainty, neuromodulation, and reward should and do have on neuronal dynamics and sensitivity, as the optimal decision strategy depends critically on these factors.
Temporal dynamics of information content carried by neurons in the primary visual cortex
Authors: Stefan Haeusler, Wolf Singer, Wolfgang Maass Danko Nikolić
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.
A Switched Gaussian Process for Estimating Disparity and Segmentation in Binocular Stereo
Authors: Oliver Williams
Published in: Advances in Neural Information Processing Systems 19  (NIPS 2006) (Main Conference Track), 2006

Abstract: This paper describes a Gaussian process framework for inferring pixel-wise disparity and bi-layer segmentation of a scene given a stereo pair of images. The Gaussian process covariance is parameterized by a foreground-backgroundocclusion segmentation label to model both smooth regions and discontinuities. As such, we call our model a switched Gaussian process. We propose a greedy incremental algorithm for adding observations from the data and assigning segmentation labels. Two observation schedules are proposed: the first treats scanlines as independent, the second uses an active learning criterion to select a sparse subset of points to measure. We show that this probabilistic framework has comparable performance to the state-of-the-art.
Automated Hierarchy Discovery for Planning in Partially Observable Environments
Authors: Pascal Poupart, Romy Shioda Laurent Charlin
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: Thomas L. Griffiths, Sharon Goldwater Mark Johnson
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: Mehryar Mohri Corinna Cortes
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: Shantanu Chakrabartty Amit Gore
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: David Decaprio, Matthew D. Pearson, Stacey Luoma, James E. Galagan Jade P. Vinson
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: Charles Kemp, Vikash K. Mansinghka, Joshua B. Tenenbaum Daniel M. Roy
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: Michael Kearns Eyal Even-dar
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.