mtybilly/Instruct2DS huggingface dataset:
Entrainment of Silicon Central Pattern Generators for Legged Locomotory Control
Authors: Ralph Etienne-Cummings, M. A. Lewis Francesco Tenore
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We have constructed a second generation CPG chip capable of generating the necessary  timing  to  control  the  leg  of  a  walking  machine.  We  demonstrate  improvements  over  a  previous  chip  by  moving  toward  a  significantly  more  versatile  device.  This  includes  a  larger  number  of  silicon  neurons,  more  sophisticated  neurons  including  voltage  dependent  charging  and  relative  and  absolute  refractory  periods,  and  enhanced  programmability of neural networks. This chip builds on the basic results achieved on a  previous  chip  and  expands  its  versatility  to  get  closer  to  a  self-contained  locomotion  controller for walking robots.    1
Fast Embedding of Sparse Similarity Graphs
Authors: John C. Platt
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: This paper applies fast sparse multidimensional scaling (MDS) to a large graph of music similarity, with 267K vertices that represent artists, al- bums, and tracks; and 3.22M edges that represent similarity between those entities. Once vertices are assigned locations in a Euclidean space, the locations can be used to browse music and to generate playlists. MDS on very large sparse graphs can be effectively performed by a family of algorithms called Rectangular Dijsktra (RD) MDS algorithms. These RD algorithms operate on a dense rectangular slice of the distance matrix, created by calling Dijsktra a constant number of times. Two RD algorithms are compared: Landmark MDS, which uses the Nystr(cid:246)m ap- proximation to perform MDS; and a new algorithm called Fast Sparse Embedding, which uses FastMap. These algorithms compare favorably to Laplacian Eigenmaps, both in terms of speed and embedding quality.
Online Passive-Aggressive Algorithms
Authors: Koby Crammer, Ofer Dekel, Yoram Singer Shai Shalev-shwartz
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We present a uniﬁed view for online classiﬁcation, regression, and uni- class problems. This view leads to a single algorithmic framework for the three problems. We prove worst case loss bounds for various algorithms for both the realizable case and the non-realizable case. A conversion of our main online algorithm to the setting of batch learning is also dis- cussed. The end result is new algorithms and accompanying loss bounds for the hinge-loss.
Training a Quantum Neural Network
Authors: Dan Ventura Bob Ricks
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Most proposals for quantum neural networks have skipped over the prob- lem of how to train the networks. The mechanics of quantum computing are different enough from classical computing that the issue of training should be treated in detail. We propose a simple quantum neural network and a training method for it. It can be shown that this algorithm works in quantum systems. Results on several real-world data sets show that this algorithm can train the proposed quantum neural networks, and that it has some advantages over classical learning algorithms.
Perspectives on Sparse Bayesian Learning
Authors: Bhaskar D. Rao, David P. Wipf Jason Palmer
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Recently, relevance vector machines (RVM) have been fashioned from a sparse Bayesian learning (SBL) framework to perform supervised learn- ing using a weight prior that encourages sparsity of representation. The methodology incorporates an additional set of hyperparameters govern- ing the prior, one for each weight, and then adopts a speciﬁc approxi- mation to the full marginalization over all weights and hyperparameters. Despite its empirical success however, no rigorous motivation for this particular approximation is currently available. To address this issue, we demonstrate that SBL can be recast as the application of a rigorous vari- ational approximation to the full model by expressing the prior in a dual form. This formulation obviates the necessity of assuming any hyperpri- ors and leads to natural, intuitive explanations of why sparsity is achieved in practice.
One Microphone Blind Dereverberation Based on Quasi-periodicity of Speech Signals
Authors: Masato Miyoshi, Keisuke Kinoshita Tomohiro Nakatani
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Speech dereverberation is desirable with a view to achieving, for exam- ple, robust speech recognition in the real world. However, it is still a chal- lenging problem, especially when using a single microphone. Although blind equalization techniques have been exploited, they cannot deal with speech signals appropriately because their assumptions are not satisﬁed by speech signals. We propose a new dereverberation principle based on an inherent property of speech signals, namely quasi-periodicity. The present methods learn the dereverberation ﬁlter from a lot of speech data with no prior knowledge of the data, and can achieve high quality speech dereverberation especially when the reverberation time is long.
Multiple Instance Learning via Disjunctive Programming Boosting
Authors: Thomas Hofmann Stuart Andrews
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Learning from ambiguous training data is highly relevant in many applications. We present a new learning algorithm for classiﬁcation problems where labels are associated with sets of pattern instead of individual patterns. This encompasses multiple instance learn- ing as a special case. Our approach is based on a generalization of linear programming boosting and uses results from disjunctive programming to generate successively stronger linear relaxations of a discrete non-convex problem.
An Autonomous Robotic System for Mapping Abandoned Mines
Authors: Aaron Morris, Dirk Hähnel, Christopher Baker, Zachary Omohundro, Carlos Reverte, Scott Thayer, Charles Whittaker, William Whittaker, Wolfram Burgard, Sebastian Thrun David Ferguson
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We present the software architecture of a robotic system for mapping abandoned mines. The software is capable of acquiring consistent 2D maps of large mines with many cycles, represented as Markov random £elds. 3D C-space maps are acquired from local 3D range scans, which are used to identify navigable paths using A* search. Our system has been deployed in three abandoned mines, two of which inaccessible to people, where it has acquired maps of unprecedented detail and accuracy.
Model Uncertainty in Classical Conditioning
Authors: Geoffrey J. Gordon, David S. Touretzky, Nathaniel D. Daw Aaron C. Courville
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We develop a framework based on Bayesian model averaging to explain how animals cope with uncertainty about contingencies in classical con- ditioning experiments. Traditional accounts of conditioning ﬁt parame- ters within a ﬁxed generative model of reinforcer delivery; uncertainty over the model structure is not considered. We apply the theory to ex- plain the puzzling relationship between second-order conditioning and conditioned inhibition, two similar conditioning regimes that nonethe- less result in strongly divergent behavioral outcomes. According to the theory, second-order conditioning results when limited experience leads animals to prefer a simpler world model that produces spurious corre- lations; conditioned inhibition results when a more complex model is justiﬁed by additional experience.
New Algorithms for Efficient High Dimensional Non-parametric Classification
Authors: Andrew W. Moore, Alexander Gray Ting liu
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Alexander Gray
Computer Science Dept.
Carnegie Mellon University
Pittsburgh, PA 15213 agray@cs.cmu.edu
This paper is about non-approximate acceleration of high dimensional nonparametric operations such as k nearest neighbor classiﬁers and the prediction phase of Support Vector Machine classiﬁers. We attempt to exploit the fact that even if we want exact answers to nonparametric queries, we usually do not need to explicitly ﬁnd the datapoints close to the query, but merely need to ask questions about the properties about that set of datapoints. This offers a small amount of computational lee- way, and we investigate how much that leeway can be exploited. For clarity, this paper concentrates on pure k-NN classiﬁcation and the pre- diction phase of SVMs. We introduce new ball tree algorithms that on real-world datasets give accelerations of 2-fold up to 100-fold compared against highly optimized traditional ball-tree-based k-NN. These results include datasets with up to 106 dimensions and 105 records, and show non-trivial speedups while giving exact answers.
Large Margin Classifiers: Convex Loss, Low Noise, and Convergence Rates
Authors: Michael I. Jordan, Jon D. Mcauliffe Peter L. Bartlett
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Many classiﬁcation algorithms, including the support vector machine, boosting and logistic regression, can be viewed as minimum contrast methods that minimize a convex surrogate of the 0-1 loss function. We characterize the statistical consequences of using such a surrogate by pro- viding a general quantitative relationship between the risk as assessed us- ing the 0-1 loss and the risk as assessed using any nonnegative surrogate loss function. We show that this relationship gives nontrivial bounds un- der the weakest possible condition on the loss function—that it satisfy a pointwise form of Fisher consistency for classiﬁcation. The relationship is based on a variational transformation of the loss function that is easy to compute in many applications. We also present a reﬁned version of this result in the case of low noise. Finally, we present applications of our results to the estimation of convergence rates in the general setting of function classes that are scaled hulls of a ﬁnite-dimensional base class.
Design of Experiments via Information Theory
Authors: Liam Paninski
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We discuss an idea for collecting data in a relatively efﬁcient manner. Our point of view is Bayesian and information-theoretic: on any given trial, we want to adaptively choose the input in such a way that the mutual in- formation between the (unknown) state of the system and the (stochastic) output is maximal, given any prior information (including data collected on any previous trials). We prove a theorem that quantiﬁes the effective- ness of this strategy and give a few illustrative examples comparing the performance of this adaptive technique to that of the more usual nonadap- tive experimental design. For example, we are able to explicitly calculate the asymptotic relative efﬁciency of the “staircase method” widely em- ployed in psychophysics research, and to demonstrate the dependence of this efﬁciency on the form of the “psychometric function” underlying the output responses.
Efficient and Robust Feature Extraction by Maximum Margin Criterion
Authors: Tao Jiang, Keshu Zhang Haifeng Li
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: A new feature extraction criterion, maximum margin criterion (MMC), is proposed in this paper. This new criterion is general in the sense that, when combined with a suitable constraint, it can actually give rise to the most popular feature extractor in the literature, linear discriminate analysis (LDA). We derive a new feature extractor based on MMC using a different constraint that does not depend on the nonsingularity of the within-class scatter matrix Sw. Such a dependence is a major drawback of LDA especially when the sample size is small. The kernelized (nonlin- ear) counterpart of this linear feature extractor is also established in this paper. Our preliminary experimental results on face images demonstrate that the new feature extractors are efﬁcient and stable.
Training fMRI Classifiers to Detect Cognitive States across Multiple Human Subjects
Authors: Rebecca Hutchinson, Tom M. Mitchell Xuerui Wang
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We consider learning to classify cognitive states of human subjects, based on their brain activity observed via functional Magnetic Resonance Imaging (fMRI). This problem is important because such classiﬁers con- stitute “virtual sensors” of hidden cognitive states, which may be useful in cognitive science research and clinical applications. In recent work, Mitchell, et al. [6,7,9] have demonstrated the feasibility of training such classiﬁers for individual human subjects (e.g., to distinguish whether the subject is reading an ambiguous or unambiguous sentence, or whether they are reading a noun or a verb). Here we extend that line of research, exploring how to train classiﬁers that can be applied across multiple hu- man subjects, including subjects who were not involved in training the classiﬁer. We describe the design of several machine learning approaches to training multiple-subject classiﬁers, and report experimental results demonstrating the success of these methods in learning cross-subject classiﬁers for two different fMRI data sets.
Applying Metric-Trees to Belief-Point POMDPs
Authors: Geoffrey J. Gordon, Sebastian Thrun Joelle Pineau
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Recent developments in grid-based and point-based approximation algo- rithms for POMDPs have greatly improved the tractability of POMDP planning. These approaches operate on sets of belief points by individ- ually learning a value function for each point. In reality, belief points exist in a highly-structured metric simplex, but current POMDP algo- rithms do not exploit this property. This paper presents a new metric-tree algorithm which can be used in the context of POMDP planning to sort belief points spatially, and then perform fast value function updates over groups of points. We present results showing that this approach can re- duce computation in point-based POMDP algorithms for a wide range of problems.
Nonlinear Filtering of Electron Micrographs by Means of Support Vector Regression
Authors: Michael Scholz, Ian A. Meinertzhagen, Klaus Obermayer Roland Vollgraf
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Nonlinear (cid:12)ltering can solve very complex problems, but typically involve very time consuming calculations. Here we show that for (cid:12)lters that are constructed as a RBF network with Gaussian basis functions, a decomposition into linear (cid:12)lters exists, which can be computed e(cid:14)ciently in the frequency domain, yielding dramatic improvement in speed. We present an application of this idea to image processing. In electron micrograph images of photoreceptor terminals of the fruit (cid:13)y, Drosophila, synaptic vesicles containing neurotransmitter should be detected and labeled automatically. We use hand labels, provided by human experts, to learn a RBF (cid:12)lter using Support Vector Regression with Gaussian kernels. We will show that the resulting nonlinear (cid:12)lter solves the task to a degree of accuracy, which is close to what can be achieved by human experts. This allows the very time consuming task of data evaluation to be done e(cid:14)ciently.
Application of SVMs for Colour Classification and Collision Detection with AIBO Robots
Authors: Stephan K. Chalup, Richard H. Middleton Michael J. Quinlan
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: This article addresses the issues of colour classiﬁcation and collision de- tection as they occur in the legged league robot soccer environment of RoboCup. We show how the method of one-class classiﬁcation with sup- port vector machines (SVMs) can be applied to solve these tasks satisfac- torily using the limited hardware capacity of the prescribed Sony AIBO quadruped robots. The experimental evaluation shows an improvement over our previous methods of ellipse ﬁtting for colour classiﬁcation and the statistical approach used for collision detection.
Warped Gaussian Processes
Authors: Zoubin Ghahramani, Carl E. Rasmussen Edward Snelson
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We generalise the Gaussian process (GP) framework for regression by learning a nonlinear transformation of the GP outputs. This allows for non-Gaussian processes and non-Gaussian noise. The learning algo- rithm chooses a nonlinear transformation such that transformed data is well-modelled by a GP. This can be seen as including a preprocessing transformation as an integral part of the probabilistic modelling problem, rather than as an ad-hoc step. We demonstrate on several real regression problems that learning the transformation can lead to signiﬁcantly better performance than using a regular GP, or a GP with a ﬁxed transformation.
Online Learning via Global Feedback for Phrase Recognition
Authors: Lluís Màrquez Xavier Carreras
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: This work presents an architecture based on perceptrons to recognize phrase structures, and an online learning algorithm to train the percep- trons together and dependently. The recognition strategy applies learning in two layers: a ﬁltering layer, which reduces the search space by identi- fying plausible phrase candidates, and a ranking layer, which recursively builds the optimal phrase structure. We provide a recognition-based feed- back rule which reﬂects to each local function its committed errors from a global point of view, and allows to train them together online as percep- trons. Experimentation on a syntactic parsing problem, the recognition of clause hierarchies, improves state-of-the-art results and evinces the advantages of our global training method over optimizing each function locally and independently.
Iterative Scaled Trust-Region Learning in Krylov Subspaces via Pearlmutter's Implicit Sparse Hessian
Authors: James Demmel Eiji Mizutani
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The online incremental gradient (or backpropagation) algorithm is widely considered to be the fastest method for solving large-scale neural-network (NN) learning problems. In contrast, we show that an appropriately implemented iterative batch-mode (or block-mode) learning method can be much faster. For example, it is three times faster in the UCI letter classiﬁcation problem (26 outputs, 16,000 data items, 6,066 parameters with a two-hidden-layer multilayer perceptron) and 353 times faster in a nonlinear regression problem arising in color recipe prediction (10 outputs, 1,000 data items, 2,210 parameters with a neuro-fuzzy modular network). The three principal innovative ingredients in our algorithm are the following: First, we use scaled trust-region regularization with inner-outer it- eration to solve the associated “overdetermined” nonlinear least squares problem, where the inner iteration performs a truncated (or inexact) Newton method. Second, we employ Pearlmutter’s implicit sparse Hessian matrix-vector multiply algorithm to con- struct the Krylov subspaces used to solve for the truncated New- ton update. Third, we exploit sparsity (for preconditioning) in the matrices resulting from the NNs having many outputs.
AUC Optimization vs. Error Rate Minimization
Authors: Mehryar Mohri Corinna Cortes
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The area under an ROC curve (AUC) is a criterion used in many appli- cations to measure the quality of a classiﬁcation algorithm. However, the objective function optimized in most of these algorithms is the error rate and not the AUC value. We give a detailed statistical analysis of the relationship between the AUC and the error rate, including the ﬁrst exact expression of the expected value and the variance of the AUC for a ﬁxed error rate. Our results show that the average AUC is monotonically in- creasing as a function of the classiﬁcation accuracy, but that the standard deviation for uneven distributions and higher error rates is noticeable. Thus, algorithms designed to minimize the error rate may not lead to the best possible AUC values. We show that, under certain conditions, the global function optimized by the RankBoost algorithm is exactly the AUC. We report the results of our experiments with RankBoost in several datasets demonstrating the beneﬁts of an algorithm speciﬁcally designed to globally optimize the AUC over other existing algorithms optimizing an approximation of the AUC or only locally optimizing the AUC.
Semi-Supervised Learning with Trees
Authors: Thomas L. Griffiths, Sean Stromsten, Joshua B. Tenenbaum Charles Kemp
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We describe a nonparametric Bayesian approach to generalizing from few labeled examples, guided by a larger set of unlabeled objects and the assumption of a latent tree-structure to the domain. The tree (or a distribution over trees) may be inferred using the unlabeled data. A prior over concepts generated by a mutation process on the inferred tree(s) allows efﬁcient computation of the optimal Bayesian classiﬁcation func- tion from the labeled examples. We test our approach on eight real-world datasets.
Finding the M Most Probable Configurations using Loopy Belief Propagation
Authors: Yair Weiss Chen Yanover
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Loopy belief propagation (BP) has been successfully used in a num- ber of di–cult graphical models to ﬂnd the most probable conﬂgu- ration of the hidden variables. In applications ranging from protein folding to image analysis one would like to ﬂnd not just the best conﬂguration but rather the top M . While this problem has been solved using the junction tree formalism, in many real world prob- lems the clique size in the junction tree is prohibitively large. In this work we address the problem of ﬂnding the M best conﬂgura- tions when exact inference is impossible. We start by developing a new exact inference algorithm for calculat- ing the best conﬂgurations that uses only max-marginals. For ap- proximate inference, we replace the max-marginals with the beliefs calculated using max-product BP and generalized BP. We show em- pirically that the algorithm can accurately and rapidly approximate the M best conﬂgurations in graphs with hundreds of variables.
A Nonlinear Predictive State Representation
Authors: Satinder P. Singh Matthew R. Rudary
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Predictive state representations (PSRs) use predictions of a set of tests to represent the state of controlled dynamical systems. One reason why this representation is exciting as an alternative to partially observable Markov decision processes (POMDPs) is that PSR models of dynamical systems may be much more compact than POMDP models. Empirical work on PSRs to date has focused on linear PSRs, which have not allowed for compression relative to POMDPs. We introduce a new notion of tests which allows us to deﬁne a new type of PSR that is nonlinear in general and allows for exponential compression in some deterministic dynami- cal systems. These new tests, called e-tests, are related to the tests used by Rivest and Schapire [1] in their work with the diversity representation, but our PSR avoids some of the pitfalls of their representation—in partic- ular, its potential to be exponentially larger than the equivalent POMDP.
Predicting Speech Intelligibility from a Population of Neurons
Authors: Ian Bruce, Suzanna Becker, Simon Haykin Jeff Bondy
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Simon Haykin 
Dept. of Electrical Engineering 
McMaster University  haykin@mcmaster.ca 
A  major  issue  in  evaluating  speech  enhancement  and  hearing  compensation algorithms is  to come up with a suitable  metric that  predicts  intelligibility  as  judged  by  a  human  listener.  Previous  methods such as the widely used Speech Transmission Index (STI)  fail  to  account  for  masking  effects  that  arise  from  the  highly  nonlinear  cochlear  transfer  function.  We  therefore  propose  a  Neural  Articulation  speech  intelligibility  from  the  instantaneous  neural  spike  rate  over  time,  produced when a signal is  processed by an auditory  neural model.  By  using  a  well  developed  model  of  the  auditory  periphery  and  detection  theory  we  show  that  human  perceptual  discrimination  closely  matches  the  modeled  distortion  in  the  instantaneous  spike  rates  of  the  auditory  nerve.  In  highly  rippled  frequency  transfer  conditions  the  NAI’s  prediction  error  is  8%  versus  the  STI’s  prediction error of 10.8%.
Different Cortico-Basal Ganglia Loops Specialize in Reward Prediction at Different Time Scales
Authors: Kenji Doya, Go Okada, Kazutaka Ueda, Yasumasa Okamoto, Shigeto Yamawaki Saori C. Tanaka
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: To understand the brain mechanisms involved in reward prediction  on different time scales, we developed a Markov decision task that  requires prediction of both immediate and future rewards, and ana- lyzed subjects’ brain activities using functional MRI. We estimated  the time course of reward prediction and reward prediction error on  different time scales from subjects' performance data, and used them  as  the  explanatory  variables  for  SPM  analysis.  We  found  topog- raphic  maps  of  different  time  scales  in  medial  frontal  cortex  and  striatum.  The  result  suggests  that  different  cortico-basal  ganglia  loops are specialized for reward prediction on different time scales.
Measure Based Regularization
Authors: Olivier Chapelle, Matthias Hein Olivier Bousquet
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We address in this paper the question of how the knowledge of the marginal distribution P (x) can be incorporated in a learning algorithm. We suggest three theoretical methods for taking into account this distribution for regularization and provide links to existing graph-based semi-supervised learning algorithms. We also propose practical implementations.
Geometric Clustering Using the Information Bottleneck Method
Authors: William Bialek, Léon Bottou Susanne Still
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We argue that K–means and deterministic annealing algorithms for geo- metric clustering can be derived from the more general Information Bot- tleneck approach. If we cluster the identities of data points to preserve information about their location, the set of optimal solutions is massively degenerate. But if we treat the equations that deﬁne the optimal solution as an iterative algorithm, then a set of “smooth” initial conditions selects solutions with the desired geometrical properties. In addition to concep- tual uniﬁcation, we argue that this approach can be more efﬁcient and robust than classic algorithms.
Sample Propagation
Authors: Mark A. Paskin
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Rao–Blackwellization is an approximation technique for probabilistic in- ference that ﬂexibly combines exact inference with sampling. It is useful in models where conditioning on some of the variables leaves a sim- pler inference problem that can be solved tractably. This paper presents Sample Propagation, an efﬁcient implementation of Rao–Blackwellized approximate inference for a large class of models. Sample Propagation tightly integrates sampling with message passing in a junction tree, and is named for its simple, appealing structure: it walks the clusters of a junction tree, sampling some of the current cluster’s variables and then passing a message to one of its neighbors. We discuss the application of Sample Propagation to conditional Gaussian inference problems such as switching linear dynamical systems.
Gaussian Processes in Reinforcement Learning
Authors: Carl E. Rasmussen Malte Kuss
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We exploit some useful properties of Gaussian process (GP) regression models for reinforcement learning in continuous state spaces and dis- crete time. We demonstrate how the GP model allows evaluation of the value function in closed form. The resulting policy iteration algorithm is demonstrated on a simple problem with a two dimensional state space. Further, we speculate that the intrinsic ability of GP models to charac- terise distributions of functions would allow the method to capture entire distributions over future values instead of merely their expectation, which has traditionally been the focus of much of reinforcement learning.
The Doubly Balanced Network of Spiking Neurons: A Memory Model with High Capacity
Authors: David Horn, Moshe Abeles Yuval Aviel
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: A balanced network leads to contradictory constraints on memory  models, as exemplified in previous work on accommodation of  synfire chains. Here we show that these constraints can be  overcome by introducing a 'shadow' inhibitory pattern for each  excitatory pattern of the model. This is interpreted as a double- balance principle, whereby there exists both global balance  between average excitatory and inhibitory currents and local  balance between the currents carrying coherent activity at any  given time frame. This principle can be applied to networks with  Hebbian cell assemblies, leading to a high capacity of the  associative memory. The number of possible patterns is limited by  a combinatorial constraint that turns out to be P=0.06N within the  specific model that we employ. This limit is reached by the  Hebbian cell assembly network. To the best of our knowledge this  is the first time that such high memory capacities are demonstrated  in the asynchronous state of models of spiking neurons.
Hierarchical Topic Models and the Nested Chinese Restaurant Process
Authors: Michael I. Jordan, Joshua B. Tenenbaum, David M. Blei Thomas L. Griffiths
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We address the problem of learning topic hierarchies from data. The model selection problem in this domain is daunting—which of the large collection of possible trees to use? We take a Bayesian approach, gen- erating an appropriate prior via a distribution on partitions that we refer to as the nested Chinese restaurant process. This nonparametric prior al- lows arbitrarily large branching factors and readily accommodates grow- ing data collections. We build a hierarchical topic model by combining this prior with a likelihood that is based on a hierarchical variant of latent Dirichlet allocation. We illustrate our approach on simulated data and with an application to the modeling of NIPS abstracts.
A Sampled Texture Prior for Image Super-Resolution
Authors: Stephen J. Roberts, Andrew Zisserman Lyndsey C. Pickup
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Super-resolution aims to produce a high-resolution image from a set of one or more low-resolution images by recovering or inventing plausible high-frequency image content. Typical approaches try to reconstruct a high-resolution image using the sub-pixel displacements of several low- resolution images, usually regularized by a generic smoothness prior over the high-resolution image space. Other methods use training data to learn low-to-high-resolution matches, and have been highly successful even in the single-input-image case. Here we present a domain-speciﬁc im- age prior in the form of a p.d.f. based upon sampled images, and show that for certain types of super-resolution problems, this sample-based prior gives a signiﬁcant improvement over other common multiple-image super-resolution techniques.
Analytical Solution of Spike-timing Dependent Plasticity Based on Synaptic Biophysics
Authors: Ausra Saudargiene, Florentin Wörgötter Bernd Porr
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Spike timing plasticity (STDP) is a special form of synaptic plasticity where the relative timing of post- and presynaptic activity determines the change of the synaptic weight. On the postsynaptic side, active back- propagating spikes in dendrites seem to play a crucial role in the induc- tion of spike timing dependent plasticity. We argue that postsynaptically the temporal change of the membrane potential determines the weight change. Coming from the presynaptic side induction of STDP is closely related to the activation of NMDA channels. Therefore, we will calculate analytically the change of the synaptic weight by correlating the deriva- tive of the membrane potential with the activity of the NMDA channel. Thus, for this calculation we utilise biophysical variables of the physi- ological cell. The ﬁnal result shows a weight change curve which con- forms with measurements from biology. The positive part of the weight change curve is determined by the NMDA activation. The negative part of the weight change curve is determined by the membrane potential change. Therefore, the weight change curve should change its shape de- pending on the distance from the soma of the postsynaptic cell. We ﬁnd temporally asymmetric weight change close to the soma and temporally symmetric weight change in the distal dendrite.
Sparse Greedy Minimax Probability Machine Classification
Authors: Andrei Belitski, Gregory Z. Grudic, Dennis DeCoste Thomas R. Strohmann
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The Minimax Probability Machine Classiﬁcation (MPMC) framework [Lanckriet et al., 2002] builds classiﬁers by minimizing the maximum probability of misclassiﬁcation, and gives direct estimates of the proba- bilistic accuracy bound Ω. The only assumptions that MPMC makes is that good estimates of means and covariance matrices of the classes exist. However, as with Support Vector Machines, MPMC is computationally expensive and requires extensive cross validation experiments to choose kernels and kernel parameters that give good performance. In this paper we address the computational cost of MPMC by proposing an algorithm that constructs nonlinear sparse MPMC (SMPMC) models by incremen- tally adding basis functions (i.e. kernels) one at a time – greedily select- ing the next one that maximizes the accuracy bound Ω. SMPMC auto- matically chooses both kernel parameters and feature weights without us- ing computationally expensive cross validation. Therefore the SMPMC algorithm simultaneously addresses the problem of kernel selection and feature selection (i.e. feature weighting), based solely on maximizing the accuracy bound Ω. Experimental results indicate that we can obtain reli- able bounds Ω, as well as test set accuracies that are comparable to state of the art classiﬁcation algorithms.
Approximate Policy Iteration with a Policy Language Bias
Authors: Sungwook Yoon, Robert Givan Alan Fern
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We explore approximate policy iteration, replacing the usual cost- function learning step with a learning step in policy space. We give policy-language biases that enable solution of very large relational Markov decision processes (MDPs) that no previous technique can solve. In particular, we induce high-quality domain-speciﬁc planners for clas- sical planning domains (both deterministic and stochastic variants) by solving such domains as extremely large MDPs.
Information Bottleneck for Gaussian Variables
Authors: Amir Globerson, Naftali Tishby, Yair Weiss Gal Chechik
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The problem of extracting the relevant aspects of data was ad- dressed through the information bottleneck (IB) method, by (soft) clustering one variable while preserving information about another - relevance - variable. An interesting question addressed in the current work is the extension of these ideas to obtain continuous representations that preserve relevant information, rather than dis- crete clusters. We give a formal deﬂnition of the general continuous IB problem and obtain an analytic solution for the optimal repre- sentation for the important case of multivariate Gaussian variables. The obtained optimal representation is a noisy linear projection to eigenvectors of the normalized correlation matrix §xjy§¡1 x , which is also the basis obtained in Canonical Correlation Analysis. How- ever, in Gaussian IB, the compression tradeoﬁ parameter uniquely determines the dimension, as well as the scale of each eigenvector. This introduces a novel interpretation where solutions of diﬁerent ranks lie on a continuum parametrized by the compression level. Our analysis also provides an analytic expression for the optimal tradeoﬁ - the information curve - in terms of the eigenvalue spec- trum.
Laplace Propagation
Authors: Alex J. Smola, S.v.n. Vishwanathan Eleazar Eskin
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We present a novel method for approximate inference in Bayesian mod- els and regularized risk functionals. It is based on the propagation of mean and variance derived from the Laplace approximation of condi- tional probabilities in factorizing distributions, much akin to Minka’s Expectation Propagation. In the jointly normal case, it coincides with the latter and belief propagation, whereas in the general case, it provides an optimization strategy containing Support Vector chunking, the Bayes Committee Machine, and Gaussian Process chunking as special cases.
Approximate Expectation Maximization
Authors: Onno Zoeter, Wim Wiegerinck Tom Heskes
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We discuss the integration of the expectation-maximization (EM) algorithm for maximum likelihood learning of Bayesian networks with belief propagation algorithms for approximate inference. Specifically we propose to combine the outer-loop step of convergent belief propagation algorithms with the M-step of the EM algorithm. This then yields an approximate EM algorithm that is essentially still double loop, with the important advantage of an inner loop that is guaranteed to converge. Simulations illustrate the merits of such an approach.
A Fast Multi-Resolution Method for Detection of Significant Spatial Disease Clusters
Authors: Andrew W. Moore Daniel B. Neill
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Given an N(cid:2)N grid of squares, where each square has a count and an un- derlying population, our goal is to ﬁnd the square region with the highest density, and to calculate its signiﬁcance by randomization. Any density measure D, dependent on the total count and total population of a re- gion, can be used. For example, if each count represents the number of disease cases occurring in that square, we can use Kulldorff’s spatial scan statistic DK to ﬁnd the most signiﬁcant spatial disease cluster. A naive approach to ﬁnding the maximum density region requires O(N 3) time, and is generally computationally infeasible. We present a novel algorithm which partitions the grid into overlapping regions, bounds the maximum score of subregions contained in each region, and prunes re- gions which cannot contain the maximum density region. For sufﬁciently dense regions, this method ﬁnds the maximum density region in optimal O(N2) time, in practice resulting in signiﬁcant (10-200x) speedups.
Computing Gaussian Mixture Models with EM Using Equivalence Constraints
Authors: Aharon Bar-hillel, Tomer Hertz, Daphna Weinshall Noam Shental
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Density estimation with Gaussian Mixture Models is a popular gener- ative technique used also for clustering. We develop a framework to incorporate side information in the form of equivalence constraints into the model estimation procedure. Equivalence constraints are deﬁned on pairs of data points, indicating whether the points arise from the same source (positive constraints) or from different sources (negative con- straints). Such constraints can be gathered automatically in some learn- ing problems, and are a natural form of supervision in others. For the estimation of model parameters we present a closed form EM procedure which handles positive constraints, and a Generalized EM procedure us- ing a Markov net which handles negative constraints. Using publicly available data sets we demonstrate that such side information can lead to considerable improvement in clustering tasks, and that our algorithm is preferable to two other suggested methods using the same type of side information.
Convex Methods for Transduction
Authors: Nello Cristianini Tijl D. Bie
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The 2-class transduction problem, as formulated by Vapnik [1], involves ﬁnding a separating hyperplane for a labelled data set that is also maximally distant from a given set of unlabelled test points. In this form, the problem has exponential computational complexity in the size of the working set. So far it has been attacked by means of integer programming techniques [2] that do not scale to reasonable problem sizes, or by local search procedures [3]. In this paper we present a relaxation of this task based on semi- deﬁnite programming (SDP), resulting in a convex optimization problem that has polynomial complexity in the size of the data set. The results are very encouraging for mid sized data sets, however the cost is still too high for large scale problems, due to the high di- mensional search space. To this end, we restrict the feasible region by introducing an approximation based on solving an eigenproblem. With this approximation, the computational cost of the algorithm is such that problems with more than 1000 points can be treated.
Kernel Dimensionality Reduction for Supervised Learning
Authors: Francis R. Bach, Michael I. Jordan Kenji Fukumizu
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We propose a novel method of dimensionality reduction for supervised learning. Given a regression or classiﬁcation problem in which we wish to predict a variable Y from an explanatory vector X, we treat the prob- lem of dimensionality reduction as that of ﬁnding a low-dimensional “ef- fective subspace” of X which retains the statistical relationship between X and Y . We show that this problem can be formulated in terms of conditional independence. To turn this formulation into an optimization problem, we characterize the notion of conditional independence using covariance operators on reproducing kernel Hilbert spaces; this allows us to derive a contrast function for estimation of the effective subspace. Un- like many conventional methods, the proposed method requires neither assumptions on the marginal distribution of X, nor a parametric model of the conditional distribution of Y .
Learning with Local and Global Consistency
Authors: Olivier Bousquet, Thomas N. Lal, Jason Weston, Bernhard Schölkopf Dengyong Zhou
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We consider the general problem of learning from labeled and unlabeled data, which is often called semi-supervised learning or transductive in- ference. A principled approach to semi-supervised learning is to design a classifying function which is suf(cid:2)ciently smooth with respect to the intrinsic structure collectively revealed by known labeled and unlabeled points. We present a simple algorithm to obtain such a smooth solution. Our method yields encouraging experimental results on a number of clas- si(cid:2)cation problems and demonstrates effective use of unlabeled data.
Max-Margin Markov Networks
Authors: Carlos Guestrin, Daphne Koller Ben Taskar
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: In typical classiﬁcation tasks, we seek a function which assigns a label to a sin- gle object. Kernel-based approaches, such as support vector machines (SVMs), which maximize the margin of conﬁdence of the classiﬁer, are the method of choice for many such tasks. Their popularity stems both from the ability to use high-dimensional feature spaces, and from their strong theoretical guaran- tees. However, many real-world tasks involve sequential, spatial, or structured data, where multiple labels must be assigned. Existing kernel-based methods ig- nore structure in the problem, assigning labels independently to each object, los- ing much useful information. Conversely, probabilistic graphical models, such as Markov networks, can represent correlations between labels, by exploiting problem structure, but cannot handle high-dimensional feature spaces, and lack strong theoretical generalization guarantees. In this paper, we present a new framework that combines the advantages of both approaches: Maximum mar- gin Markov (M3) networks incorporate both kernels, which efﬁciently deal with high-dimensional features, and the ability to capture correlations in structured data. We present an efﬁcient algorithm for learning M3 networks based on a compact quadratic program formulation. We provide a new theoretical bound for generalization in structured domains. Experiments on the task of handwrit- ten character recognition and collective hypertext classiﬁcation demonstrate very signiﬁcant gains over previous approaches.