mtybilly/Instruct2DS huggingface dataset:
Training a Quantum Neural Network
Authors: Bob Ricks, Dan Ventura
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: Jason Palmer, Bhaskar D. Rao, David P. Wipf
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: Tomohiro Nakatani, Masato Miyoshi, Keisuke Kinoshita
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: Stuart Andrews, Thomas Hofmann
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: David Ferguson, Aaron Morris, Dirk Hähnel, Christopher Baker, Zachary Omohundro, Carlos Reverte, Scott Thayer, Charles Whittaker, William Whittaker, Wolfram Burgard, Sebastian Thrun
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: Aaron C. Courville, Geoffrey J. Gordon, David S. Touretzky, Nathaniel D. Daw
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: Ting liu, Andrew W. Moore, Alexander Gray
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: Peter L. Bartlett, Michael I. Jordan, Jon D. Mcauliffe
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.
Efficient and Robust Feature Extraction by Maximum Margin Criterion
Authors: Haifeng Li, Tao Jiang, Keshu Zhang
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: Xuerui Wang, Rebecca Hutchinson, Tom M. Mitchell
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: Joelle Pineau, Geoffrey J. Gordon, Sebastian Thrun
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: Roland Vollgraf, Michael Scholz, Ian A. Meinertzhagen, Klaus Obermayer
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: Michael J. Quinlan, Stephan K. Chalup, Richard H. Middleton
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: Edward Snelson, Zoubin Ghahramani, Carl E. Rasmussen
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: Xavier Carreras, Lluís Màrquez
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: Eiji Mizutani, James Demmel
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: Corinna Cortes, Mehryar Mohri
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: Charles Kemp, Thomas L. Griffiths, Sean Stromsten, Joshua B. Tenenbaum
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: Chen Yanover, Yair Weiss
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: Matthew R. Rudary, Satinder P. Singh
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: Jeff Bondy, Ian Bruce, Suzanna Becker, Simon Haykin
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: Saori C. Tanaka, Kenji Doya, Go Okada, Kazutaka Ueda, Yasumasa Okamoto, Shigeto Yamawaki
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 Bousquet, Olivier Chapelle, Matthias Hein
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: Susanne Still, William Bialek, Léon Bottou
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.
Gaussian Processes in Reinforcement Learning
Authors: Malte Kuss, Carl E. Rasmussen
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: Yuval Aviel, David Horn, Moshe Abeles
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: Thomas L. Griffiths, Michael I. Jordan, Joshua B. Tenenbaum, David M. Blei
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: Lyndsey C. Pickup, Stephen J. Roberts, Andrew Zisserman
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: Bernd Porr, Ausra Saudargiene, Florentin Wörgötter
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: Thomas R. Strohmann, Andrei Belitski, Gregory Z. Grudic, Dennis DeCoste
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: Alan Fern, Sungwook Yoon, Robert Givan
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: Gal Chechik, Amir Globerson, Naftali Tishby, Yair Weiss
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: Eleazar Eskin, Alex J. Smola, S.v.n. Vishwanathan
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: Tom Heskes, Onno Zoeter, Wim Wiegerinck
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: Daniel B. Neill, Andrew W. Moore
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: Noam Shental, Aharon Bar-hillel, Tomer Hertz, Daphna Weinshall
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: Tijl D. Bie, Nello Cristianini
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: Kenji Fukumizu, Francis R. Bach, Michael I. Jordan
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: Dengyong Zhou, Olivier Bousquet, Thomas N. Lal, Jason Weston, Bernhard Schölkopf
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: Ben Taskar, Carlos Guestrin, Daphne Koller
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.
Factorization with Uncertainty and Missing Data: Exploiting Temporal Coherence
Authors: Amit Gruber, Yair Weiss
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The problem of \Structure From Motion" is a central problem in vision: given the 2D locations of certain points we wish to recover the camera motion and the 3D coordinates of the points. Un- der simpliﬂed camera models, the problem reduces to factorizing a measurement matrix into the product of two low rank matrices. Each element of the measurement matrix contains the position of a point in a particular image. When all elements are observed, the problem can be solved trivially using SVD, but in any realistic sit- uation many elements of the matrix are missing and the ones that are observed have a diﬁerent directional uncertainty. Under these conditions, most existing factorization algorithms fail while human perception is relatively unchanged. In this paper we use the well known EM algorithm for factor analy- sis to perform factorization. This allows us to easily handle missing data and measurement uncertainty and more importantly allows us to place a prior on the temporal trajectory of the latent variables (the camera position). We show that incorporating this prior gives a signiﬂcant improvement in performance in challenging image se- quences.
Sequential Bayesian Kernel Regression
Authors: Jaco Vermaak, Simon J. Godsill, Arnaud Doucet
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We propose a method for sequential Bayesian kernel regression. As is the case for the popular Relevance Vector Machine (RVM) [10, 11], the method automatically identiﬁes the number and locations of the kernels. Our algorithm overcomes some of the computational difﬁculties related to batch methods for kernel regression. It is non-iterative, and requires only a single pass over the data. It is thus applicable to truly sequen- tial data sets and batch data sets alike. The algorithm is based on a generalisation of Importance Sampling, which allows the design of in- tuitively simple and efﬁcient proposal distributions for the model param- eters. Comparative results on two standard data sets show our algorithm to compare favourably with existing batch estimation strategies.
PAC-Bayesian Generic Chaining
Authors: Jean-yves Audibert, Olivier Bousquet
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: There exist many different generalization error bounds for classiﬁcation. Each of these bounds contains an improvement over the others for cer- tain situations. Our goal is to combine these different improvements into a single bound. In particular we combine the PAC-Bayes approach intro- duced by McAllester [1], which is interesting for averaging classiﬁers, with the optimal union bound provided by the generic chaining technique developed by Fernique and Talagrand [2]. This combination is quite nat- ural since the generic chaining is based on the notion of majorizing mea- sures, which can be considered as priors on the set of classiﬁers, and such priors also arise in the PAC-bayesian setting.
Ambiguous Model Learning Made Unambiguous with 1/f Priors
Authors: Gurinder S. Atwal, William Bialek
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: What happens to the optimal interpretation of noisy data when there exists more than one equally plausible interpretation of the data? In a Bayesian model-learning framework the answer depends on the prior ex- pectations of the dynamics of the model parameter that is to be inferred from the data. Local time constraints on the priors are insufﬁcient to pick one interpretation over another. On the other hand, nonlocal time constraints, induced by a 1/f noise spectrum of the priors, is shown to permit learning of a speciﬁc model parameter even when there are in- ﬁnitely many equally plausible interpretations of the data. This transition is inferred by a remarkable mapping of the model estimation problem to a dissipative physical system, allowing the use of powerful statisti- cal mechanical methods to uncover the transition from indeterminate to determinate model learning.