mtybilly/Instruct2DS huggingface dataset:
Using Tarjan's Red Rule for Fast Dependency Tree Construction
Authors: Andrew W. Moore Dan Pelleg
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We focus on the problem of efﬁcient learning of dependency trees. It is well-known that given the pairwise mutual information coefﬁcients, a minimum-weight spanning tree algorithm solves this problem exactly and in polynomial time. However, for large data-sets it is the construc- tion of the correlation matrix that dominates the running time. We have developed a new spanning-tree algorithm which is capable of exploiting partial knowledge about edge weights. The partial knowledge we main- tain is a probabilistic conﬁdence interval on the coefﬁcients, which we derive by examining just a small sample of the data. The algorithm is able to ﬂag the need to shrink an interval, which translates to inspec- tion of more data for the particular attribute pair. Experimental results show running time that is near-constant in the number of records, with- out signiﬁcant loss in accuracy of the generated trees. Interestingly, our spanning-tree algorithm is based solely on Tarjan’s red-edge rule, which is generally considered a guaranteed recipe for bad performance.
Approximate Inference and Protein-Folding
Authors: Yair Weiss Chen Yanover
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Side-chain prediction is an important subtask in the protein-folding  problem.  We  show  that  finding  a  minimal  energy  side-chain  con(cid:173) figuration  is  equivalent  to  performing  inference  in  an  undirected  graphical model.  The graphical model  is  relatively  sparse yet  has  many cycles.  We used this equivalence to assess the performance of  approximate inference  algorithms  in  a  real-world  setting.  Specifi(cid:173) cally we  compared belief propagation (BP), generalized BP (GBP)  and naive mean field  (MF).  In  cases  where  exact  inference  was  possible,  max-product  BP  al(cid:173) ways found the global minimum of the energy  (except  in few  cases  where it failed  to converge), while other approximation algorithms  of similar  complexity  did  not.  In  the  full  protein  data set,  max(cid:173) product  BP  always  found  a  lower  energy  configuration  than  the  other algorithms, including  a  widely  used  protein-folding software  (SCWRL).
Learning a Forward Model of a Reflex
Authors: Florentin Wörgötter Bernd Porr
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We develop a systems theoretical treatment of a behavioural system that interacts with its environment in a closed loop situation such that its mo- tor actions inﬂuence its sensor inputs. The simplest form of a feedback is a reﬂex. Reﬂexes occur always “too late”; i.e., only after a (unpleas- ant, painful, dangerous) reﬂex-eliciting sensor event has occurred. This deﬁnes an objective problem which can be solved if another sensor input exists which can predict the primary reﬂex and can generate an earlier reaction. In contrast to previous approaches, our linear learning algo- rithm allows for an analytical proof that this system learns to apply feed- forward control with the result that slow feedback loops are replaced by their equivalent feed-forward controller creating a forward model. In other words, learning turns the reactive system into a pro-active system. By means of a robot implementation we demonstrate the applicability of the theoretical results which can be used in a variety of different areas in physics and engineering.
Information Regularization with Partially Labeled Data
Authors: Tommi S. Jaakkola Martin Szummer
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Classiﬁcation with partially labeled data requires using a large number of unlabeled examples (or an estimated marginal P (x)), to further con- strain the conditional P (yjx) beyond a few available labeled examples. We formulate a regularization approach to linking the marginal and the conditional in a general way. The regularization penalty measures the information that is implied about the labels over covering regions. No parametric assumptions are required and the approach remains tractable even for continuous marginal densities P (x). We develop algorithms for solving the regularization problem for ﬁnite covers, establish a limiting differential equation, and exemplify the behavior of the new regulariza- tion approach in simple cases.
Intrinsic Dimension Estimation Using Packing Numbers
Authors: Balázs Kégl
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We propose a new algorithm to estimate the intrinsic dimension of data sets. The method is based on geometric properties of the data and re- quires neither parametric assumptions on the data generating model nor input parameters to set. The method is compared to a similar, widely- used algorithm from the same family of geometric techniques. Experi- ments show that our method is more robust in terms of the data generating distribution and more reliable in the presence of noise.
Mismatch String Kernels for SVM Protein Classification
Authors: Jason Weston, William S. Noble, Christina S. Leslie Eleazar Eskin
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We introduce a class of string kernels, called mismatch kernels, for use with support vector machines (SVMs) in a discriminative approach to the protein classiﬁcation problem. These kernels measure sequence sim- ilarity based on shared occurrences of  -length subsequences, counted with up to mismatches, and do not rely on any generative model for the positive training sequences. We compute the kernels efﬁciently using a mismatch tree data structure and report experiments on a benchmark SCOP dataset, where we show that the mismatch kernel used with an SVM classiﬁer performs as well as the Fisher kernel, the most success- ful method for remote homology detection, while achieving considerable computational savings.
Adaptive Caching by Refetching
Authors: Manfred K. Warmuth, Scott A. Brandt, Ismail Ari Robert B. Gramacy
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We are constructing caching policies that have 13-20% lower miss rates than the best of twelve baseline policies over a large variety of request streams. This represents an improvement of 49–63% over Least Recently Used, the most commonly implemented policy. We achieve this not by designing a speciﬁc new policy but by using on-line Machine Learning algorithms to dynamically shift between the standard policies based on their observed miss rates. A thorough experimental evaluation of our techniques is given, as well as a discussion of what makes caching an interesting on-line learning problem.
Timing and Partial Observability in the Dopamine System
Authors: Aaron C. Courville, David S. Touretzky Nathaniel D. Daw
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: According to a series of inﬂuential models, dopamine (DA) neurons sig- nal reward prediction error using a temporal-difference (TD) algorithm. We address a problem not convincingly solved in these accounts: how to maintain a representation of cues that predict delayed consequences. Our new model uses a TD rule grounded in partially observable semi-Markov processes, a formalism that captures two largely neglected features of DA experiments: hidden state and temporal variability. Previous models pre- dicted rewards using a tapped delay line representation of sensory inputs; we replace this with a more active process of inference about the under- lying state of the world. The DA system can then learn to map these inferred states to reward predictions using TD. The new model can ex- plain previously vexing data on the responses of DA neurons in the face of temporal variability. By combining statistical model-based learning with a physiologically grounded TD theory, it also brings into contact with physiology some insights about behavior that had previously been conﬁned to more abstract psychological models.
Multiple Cause Vector Quantization
Authors: Richard S. Zemel David A. Ross
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We propose a model that can learn parts-based representations of high- dimensional data. Our key assumption is that the dimensions of the data can be separated into several disjoint subsets, or factors, which take on values independently of each other. We assume each factor has a small number of discrete states, and model it using a vector quantizer. The selected states of each factor represent the multiple causes of the input. Given a set of training examples, our model learns the association of data dimensions with factors, as well as the states of each VQ. Inference and learning are carried out efﬁciently via variational algorithms. We present applications of this model to problems in image decomposition, collaborative ﬁltering, and text classiﬁcation.
Unsupervised Color Constancy
Authors: Erik G. Miller Kinh Tieu
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: In [1] we introduced a linear statistical model of joint color changes in images due to variation in lighting and certain non-geometric camera pa- rameters. We did this by measuring the mappings of colors in one image of a scene to colors in another image of the same scene under different lighting conditions. Here we increase the ﬂexibility of this color ﬂow model by allowing ﬂow coefﬁcients to vary according to a low order polynomial over the image. This allows us to better ﬁt smoothly vary- ing lighting conditions as well as curved surfaces without endowing our model with too much capacity. We show results on image matching and shadow removal and detection.
Value-Directed Compression of POMDPs
Authors: Craig Boutilier Pascal Poupart
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We examine the problem of generating state-space compressions of POMDPs in a way that minimally impacts decision quality. We analyze the impact of compres- sions on decision quality, observing that compressions that allow accurate policy evaluation (prediction of expected future reward) will not affect decision qual- ity. We derive a set of sufﬁcient conditions that ensure accurate prediction in this respect, illustrate interesting mathematical properties these confer on lossless lin- ear compressions, and use these to derive an iterative procedure for ﬁnding good linear lossy compressions. We also elaborate on how structured representations of a POMDP can be used to ﬁnd such compressions.
Constraint Classification for Multiclass Classification and Ranking
Authors: Dan Roth, Dav Zimak Sariel Har-Peled
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: The constraint classiﬁcation framework captures many ﬂavors of mul- ticlass classiﬁcation including winner-take-all multiclass classiﬁcation, multilabel classiﬁcation and ranking. We present a meta-algorithm for learning in this framework that learns via a single linear classiﬁer in high dimension. We discuss distribution independent as well as margin-based generalization bounds and present empirical and theoretical evidence showing that constraint classiﬁcation beneﬁts over existing methods of multiclass classiﬁcation.
Neural Decoding of Cursor Motion Using a Kalman Filter
Authors: M. J. Black, Y. Gao, M. Serruya, A. Shaikhouni, J. P. Donoghue, Elie Bienenstock W Wu
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: The direct neural control of external devices such as computer displays or prosthetic limbs requires the accurate decoding of neural activity rep- resenting continuous movement. We develop a real-time control system using the spiking activity of approximately 40 neurons recorded with an electrode array implanted in the arm area of primary motor cortex. In contrast to previous work, we develop a control-theoretic approach that explicitly models the motion of the hand and the probabilistic re- lationship between this motion and the mean ﬁring rates of the cells in 70 bins. We focus on a realistic cursor control task in which the sub- ject must move a cursor to “hit” randomly placed targets on a computer monitor. Encoding and decoding of the neural data is achieved with a Kalman ﬁlter which has a number of advantages over previous linear ﬁltering techniques. In particular, the Kalman ﬁlter reconstructions of hand trajectories in off-line experiments are more accurate than previ- ously reported results and the model provides insights into the nature of the neural coding of movement.
   
On the Dirichlet Prior and Bayesian Regularization
Authors: Tommi S. Jaakkola Harald Steck
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: A  common  objective  in  learning  a  model  from  data is  to  recover  its network structure,  while the model parameters are of minor in(cid:173) terest.  For example,  we  may  wish  to  recover  regulatory  networks  from high-throughput data sources.  In  this paper we  examine how  Bayesian  regularization  using  a  product  of independent  Dirichlet  priors over  the model  parameters affects  the  learned model  struc(cid:173) ture  in  a  domain  with  discrete  variables.  We  show  that  a  small  scale  parameter - often interpreted as  "equivalent sample size"  or  "prior  strength"  - leads  to  a  strong  regularization  of  the  model  structure (sparse graph)  given a  sufficiently large data set.  In  par(cid:173) ticular, the empty graph is obtained in the limit of a vanishing scale  parameter.  This is  diametrically opposite to what one may expect  in  this  limit,  namely  the  complete graph from  an  (unregularized)  maximum likelihood estimate.  Since  the prior affects  the parame(cid:173) ters as  expected, the scale parameter balances a  trade-off  between  regularizing  the  parameters  vs.  the  structure  of  the  model.  We  demonstrate  the  benefits  of optimizing  this  trade-off in  the  sense  of predictive accuracy.
Scaling of Probability-Based Optimization Algorithms
Authors: J. L. Shapiro
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Population-based Incremental Learning is  shown require very sen(cid:173) sitive scaling of its learning rate.  The learning rate must scale with  the system size in a  problem-dependent way.  This is  shown in two  problems:  the needle-in-a haystack, in which the learning rate must  vanish exponentially in the  system size,  and in  a  smooth function  in  which  the  learning rate must  vanish  like  the  square root of the  system size.  Two methods are proposed for  removing this sensitiv(cid:173) ity.  A learning dynamics which obeys detailed balance is shown to  give consistent performance over the entire range of learning rates.  An  analog  of mutation  is  shown  to  require  a  learning  rate  which  scales as  the inverse system size, but is  problem independent.
Forward-Decoding Kernel-Based Phone Recognition
Authors: Gert Cauwenberghs Shantanu Chakrabartty
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Forward decoding kernel machines (FDKM) combine large-margin clas(cid:173) sifiers  with  hidden  Markov  models  (HMM)  for  maximum  a  posteriori  (MAP)  adaptive sequence estimation.  State  transitions  in the  sequence  are conditioned on observed data using a kernel-based probability model  trained with a recursive scheme that deals effectively with noisy and par(cid:173) tially labeled data.  Training over very large data sets is accomplished us(cid:173) ing a sparse probabilistic support vector machine (SVM) model based on  quadratic entropy, and an  on-line stochastic steepest descent algorithm.  For speaker-independent continuous phone recognition,  FDKM trained  over 177 ,080 samples of the TlMIT database achieves 80.6% recognition  accuracy over the full  test set, without use  of a prior phonetic language  model.
Optoelectronic Implementation of a FitzHugh-Nagumo Neural Model
Authors: Kelvin Wagner Alexandre R. Romariz
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: An optoelectronic implementation of a spiking neuron model based on the FitzHugh-Nagumo equations is presented. A tunable semiconduc- tor laser source and a spectral ﬁlter provide a nonlinear mapping from driver voltage to detected signal. Linear electronic feedback completes the implementation, which allows either electronic or optical input sig- nals. Experimental results for a single system and numeric results of model interaction conﬁrm that important features of spiking neural mod- els can be implemented through this approach.
Margin-Based Algorithms for Information Filtering
Authors: Alex Conconi, Claudio Gentile Nicolò Cesa-bianchi
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: In this work, we study an information ﬁltering model where the relevance labels associated to a sequence of feature vectors are realizations of an unknown probabilistic linear function. Building on the analysis of a re- stricted version of our model, we derive a general ﬁltering rule based on the margin of a ridge regression estimator. While our rule may observe the label of a vector only by classfying the vector as relevant, experiments on a real-world document ﬁltering problem show that the performance of our rule is close to that of the on-line classiﬁer which is allowed to observe all labels. These empirical results are complemented by a theo- retical analysis where we consider a randomized variant of our rule and prove that its expected number of mistakes is never much larger than that of the optimal ﬁltering rule which knows the hidden linear model.
Half-Lives of EigenFlows for Spectral Clustering
Authors: Allan D. Jepson Chakra Chennubhotla
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Using a Markov chain perspective of spectral clustering we present an algorithm to automatically ﬁnd the number of stable clusters in a dataset. The Markov chain’s behaviour is characterized by the spectral properties of the matrix of transition probabilities, from which we derive eigenﬂows along with their halﬂives. An eigenﬂow describes the ﬂow of probabil- ity mass due to the Markov chain, and it is characterized by its eigen- value, or equivalently, by the halﬂife of its decay as the Markov chain is iterated. A ideal stable cluster is one with zero eigenﬂow and inﬁ- nite half-life. The key insight in this paper is that bottlenecks between weakly coupled clusters can be identiﬁed by computing the sensitivity of the eigenﬂow’s halﬂife to variations in the edge weights. We propose a novel EIGENCUTS algorithm to perform clustering that removes these identiﬁed bottlenecks in an iterative fashion.
The RA Scanner: Prediction of Rheumatoid Joint Inflammation Based on Laser Imaging
Authors: Volker Tresp, Peter Mayer, Alexander K. Scheel, Gerhard A. Müller Anton Schwaighofer
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We describe the RA scanner, a novel system for the examination of pa- tients suffering from rheumatoid arthritis. The RA scanner is based on a novel laser-based imaging technique which is sensitive to the optical characteristics of ﬁnger joint tissue. Based on the laser images, ﬁnger joints are classiﬁed according to whether the inﬂammatory status has improved or worsened. To perform the classiﬁcation task, various lin- ear and kernel-based systems were implemented and their performances were compared. Special emphasis was put on measures to reliably per- form parameter tuning and evaluation, since only a very small data set was available. Based on the results presented in this paper, it was con- cluded that the RA scanner permits a reliable classiﬁcation of patholog- ical ﬁnger joints, thus paving the way for a further development from prototype to product stage.
Optimality of Reinforcement Learning Algorithms with Linear Function Approximation
Authors: Ralf Schoknecht
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: There are several reinforcement learning algorithms that yield ap(cid:173) proximate solutions for the problem of policy evaluation when the  value function is represented with a linear function approximator.  In this paper we show that each of the solutions is optimal with  respect to a specific objective function. Moreover, we characterise  the different solutions as images of the optimal exact value func(cid:173) tion under different projection operations. The results presented  here will be useful for comparing the algorithms in terms of the  error they achieve relative to the error of the optimal approximate  solution.
Evidence Optimization Techniques for Estimating Stimulus-Response Functions
Authors: Jennifer F. Linden Maneesh Sahani
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: An essential step in understanding the function of sensory nervous sys- tems is to characterize as accurately as possible the stimulus-response function (SRF) of the neurons that relay and process sensory informa- tion. One increasingly common experimental approach is to present a rapidly varying complex stimulus to the animal while recording the re- sponses of one or more neurons, and then to directly estimate a func- tional transformation of the input that accounts for the neuronal ﬁring. The estimation techniques usually employed, such as Wiener ﬁltering or other correlation-based estimation of the Wiener or Volterra kernels, are equivalent to maximum likelihood estimation in a Gaussian-output-noise regression model. We explore the use of Bayesian evidence-optimization techniques to condition these estimates. We show that by learning hyper- parameters that control the smoothness and sparsity of the transfer func- tion it is possible to improve dramatically the quality of SRF estimates, as measured by their success in predicting responses to novel input.
Binary Coding in Auditory Cortex
Authors: Anthony M. Zador Michael R. Deweese
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Cortical neurons have been reported to use both rate and temporal  codes. Here we describe a novel mode in which each neuron  generates exactly 0 or 1 action potentials, but not more, in response  to a stimulus. We used cell-attached recording, which ensured  single-unit isolation, to record responses in rat auditory cortex to  brief tone pips. Surprisingly, the majority of neurons exhibited  binary behavior with few multi-spike responses; several dramatic  examples consisted of exactly one spike on 100% of trials, with no  trial-to-trial variability in spike count. Many neurons were tuned to  stimulus frequency. Since individual trials yielded at most one  spike for most neurons, the information about stimulus frequency  was encoded in the population, and would not have been accessible  to later stages of processing that only had access to the activity of a  single unit. These binary units allow a more efficient population  code than is possible with conventional rate coding units, and are  consistent with a model of cortical processing  in which  synchronous packets of spikes propagate stably from one neuronal  population to the next. 
1 B i n a r y c o d i n g i n a u d i t o r y c o r t e x 
We recorded responses of neurons in the auditory cortex of anesthetized rats to  pure-tone pips of different frequencies [1, 2]. Each pip was presented repeatedly,  allowing us to assess the variability of the neural response to multiple presentations  of each stimulus. We first recorded multi-unit activity with conventional tungsten  electrodes (Fig. 1a). The number of spikes in response to each pip fluctuated  markedly from one trial to the next (Fig. 1e), as though governed by a random  mechanism such as that generating the ticks of a Geiger counter. Highly variable  responses such as these, which are at least as variable as a Poisson process, are the  norm in the cortex [3-7], and have contributed to the widely held view that cortical  spike trains are so noisy that only the average firing rate can be used to encode  stimuli. 
Because we were recording the activity of an unknown number of neurons, we could  not be sure whether the strong trial-to-trial fluctuations reflected the underlying  variability of the single units. We therefore used an alternative technique, cell-
Learning Attractor Landscapes for Learning Motor Primitives
Authors: Jun Nakanishi, Stefan Schaal Auke J. Ijspeert
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Many control problems take place in continuous state-action spaces, e.g., as in manipulator robotics, where the control objective is of- ten deﬂned as ﬂnding a desired trajectory that reaches a particular goal state. While reinforcement learning oﬁers a theoretical frame- work to learn such control policies from scratch, its applicability to higher dimensional continuous state-action spaces remains rather limited to date. Instead of learning from scratch, in this paper we suggest to learn a desired complex control policy by transforming an existing simple canonical control policy. For this purpose, we represent canonical policies in terms of diﬁerential equations with well-deﬂned attractor properties. By nonlinearly transforming the canonical attractor dynamics using techniques from nonparametric regression, almost arbitrary new nonlinear policies can be gener- ated without losing the stability properties of the canonical sys- tem. We demonstrate our techniques in the context of learning a set of movement skills for a humanoid robot from demonstrations of a human teacher. Policies are acquired rapidly, and, due to the properties of well formulated diﬁerential equations, can be re-used and modiﬂed on-line under dynamic changes of the environment. The linear parameterization of nonparametric regression moreover lends itself to recognize and classify previously learned movement skills. Evaluations in simulations and on an actual 30 degree-of- freedom humanoid robot exemplify the feasibility and robustness of our approach.
Combining Dimensions and Features in Similarity-Based Representations
Authors: Michael D. Lee Daniel J. Navarro
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: This paper develops a new representational model of similarity data that combines continuous dimensions with discrete features. An al- gorithm capable of learning these representations is described, and a Bayesian model selection approach for choosing the appropriate number of dimensions and features is developed. The approach is demonstrated on a classic data set that considers the similarities between the numbers 0 through 9.
Bayesian Monte Carlo
Authors: Carl E. Rasmussen Zoubin Ghahramani
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We investigate Bayesian alternatives to classical Monte Carlo methods for evaluating integrals. Bayesian Monte Carlo (BMC) allows the in- corporation of prior knowledge, such as smoothness of the integrand, into the estimation. In a simple problem we show that this outperforms any classical importance sampling method. We also attempt more chal- lenging multidimensional integrals involved in computing marginal like- lihoods of statistical models (a.k.a. partition functions and model evi- dences). We ﬁnd that Bayesian Monte Carlo outperformed Annealed Importance Sampling, although for very high dimensional problems or problems with massive multimodality BMC may be less adequate. One advantage of the Bayesian approach to Monte Carlo is that samples can be drawn from any distribution. This allows for the possibility of active design of sample points so as to maximise information gain.
A Model for Learning Variance Components of Natural Images
Authors: Michael S. Lewicki Yan Karklin
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We present a hierarchical Bayesian model for learning efﬁcient codes of higher-order structure in natural images. The model, a non-linear gen- eralization of independent component analysis, replaces the standard as- sumption of independence for the joint distribution of coefﬁcients with a distribution that is adapted to the variance structure of the coefﬁcients of an efﬁcient image basis. This offers a novel description of higher- order image structure and provides a way to learn coarse-coded, sparse- distributed representations of abstract image properties such as object location, scale, and texture.
Effective Dimension and Generalization of Kernel Learning
Authors: Tong Zhang
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We investigate the generalization performance of some learning prob- lems in Hilbert function Spaces. We introduce a concept of scale- sensitive effective data dimension, and show that it characterizes the con- vergence rate of the underlying learning problem. Using this concept, we can naturally extend results for parametric estimation problems in ﬁnite dimensional spaces to non-parametric kernel learning methods. We de- rive upper bounds on the generalization performance and show that the resulting convergent rates are optimal under various circumstances.
Nash Propagation for Loopy Graphical Games
Authors: Michael Kearns Luis E. Ortiz
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We introduce NashProp, an iterative and local message-passing algo- rithm for computing Nash equilibria in multi-player games represented by arbitrary undirected graphs. We provide a formal analysis and exper- imental evidence demonstrating that NashProp performs well on large graphical games with many loops, often converging in just a dozen itera- tions on graphs with hundreds of nodes. NashProp generalizes the tree algorithm of (Kearns et al. 2001), and can be viewed as similar in spirit to belief propagation in probabilis- tic inference, and thus complements the recent work of (Vickrey and Koller 2002), who explored a junction tree approach. Thus, as for prob- abilistic inference, we have at least two promising general-purpose ap- proaches to equilibria computation in graphs.
Neuromorphic Bisable VLSI Synapses with Spike-Timing-Dependent Plasticity
Authors: Giacomo Indiveri
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We present analog neuromorphic circuits for implementing bistable syn- apses with spike-timing-dependent plasticity (STDP) properties. In these types of synapses, the short-term dynamics of the synaptic efﬁcacies are governed by the relative timing of the pre- and post-synaptic spikes, while on long time scales the efﬁcacies tend asymptotically to either a potentiated state or to a depressed one. We fabricated a prototype VLSI chip containing a network of integrate and ﬁre neurons interconnected via bistable STDP synapses. Test results from this chip demonstrate the synapse’s STDP learning properties, and its long-term bistable charac- teristics.
Dopamine Induced Bistability Enhances Signal Processing in Spiny Neurons
Authors: Sara A. Solla, James C. Houk Aaron J. Gruber
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Single  unit  activity  in  the  striatum  of  awake  monkeys  shows  a  marked  dependence  on  the  expected  reward  that  a  behavior  will  elicit.  We  present  a  computational  model  of  spiny  neurons,  the  principal neurons of the striatum, to assess the hypothesis that di(cid:173) rect  neuromodulatory  effects  of dopamine  through  the  activation  of D 1  receptors  mediate  the  reward  dependency  of spiny  neuron  activity.  Dopamine  release  results  in  the  amplification  of key  ion  currents,  leading  to  the  emergence  of  bistability,  which  not  only  modulates the peak firing  rate but also introduces a  temporal and  state dependence  of the  model's  response,  thus improving the de(cid:173) tectability of temporally correlated inputs.
An Information Theoretic Approach to the Functional Classification of Neurons
Authors: William Bialek, Michael Ii Elad Schneidman
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: A population of neurons typically exhibits a broad diversity of responses to sensory inputs. The intuitive notion of functional classiﬁcation is that cells can be clustered so that most of the diversity is captured by the iden- tity of the clusters rather than by individuals within clusters. We show how this intuition can be made precise using information theory, with- out any need to introduce a metric on the space of stimuli or responses. Applied to the retinal ganglion cells of the salamander, this approach re- covers classical results, but also provides clear evidence for subclasses beyond those identiﬁed previously. Further, we ﬁnd that each of the gan- glion cells is functionally unique, and that even within the same subclass only a few spikes are needed to reliably distinguish between cells.
An Asynchronous Hidden Markov Model for Audio-Visual Speech Recognition
Authors: Samy Bengio
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: This paper presents a  novel  Hidden  Markov Model architecture to  model the joint probability of pairs of asynchronous sequences de(cid:173) scribing the same event.  It is based on two other Markovian models,  namely  Asynchronous  Input/ Output  Hidden  Markov  Models  and  Pair Hidden Markov Models.  An EM algorithm to train the model  is  presented,  as  well  as  a  Viterbi  decoder  that can  be  used  to  ob(cid:173) tain  the  optimal  state sequence  as  well  as  the  alignment  between  the two  sequences.  The model has  been tested on an audio-visual  speech  recognition  task  using  the  M2VTS  database  and  yielded  robust performances under various noise  conditions.
Shape Recipes: Scene Representations that Refer to the Image
Authors: Antonio Torralba William T. Freeman
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: The goal of low-level vision is to estimate an underlying scene, given an observed image. Real-world scenes (eg, albedos or shapes) can be very complex, conventionally requiring high dimensional representations which are hard to estimate and store. We propose a low-dimensional rep- resentation, called a scene recipe, that relies on the image itself to de- scribe the complex scene conﬁgurations. Shape recipes are an example: these are the regression coefﬁcients that predict the bandpassed shape from image data. We describe the beneﬁts of this representation, and show two uses illustrating their properties: (1) we improve stereo shape estimates by learning shape recipes at low resolution and applying them at full resolution; (2) Shape recipes implicitly contain information about lighting and materials and we use them for material segmentation.
Real-Time Particle Filters
Authors: Dieter Fox, Marina Meila Cody Kwok
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Particle ﬁlters estimate the state of dynamical systems from sensor infor- mation. In many real time applications of particle ﬁlters, however, sensor information arrives at a signiﬁcantly higher rate than the update rate of the ﬁlter. The prevalent approach to dealing with such situations is to update the particle ﬁlter as often as possible and to discard sensor information that cannot be processed in time. In this paper we present real-time particle ﬁl- ters, which make use of all sensor information even when the ﬁlter update rate is below the update rate of the sensors. This is achieved by represent- ing posteriors as mixtures of sample sets, where each mixture component integrates one observation arriving during a ﬁlter update. The weights of the mixture components are set so as to minimize the approximation error introduced by the mixture representation. Thereby, our approach focuses computational resources (samples) on valuable sensor information. Exper- iments using data collected with a mobile robot show that our approach yields strong improvements over other approaches.
Critical Lines in Symmetry of Mixture Models and its Application to Component Splitting
Authors: Shotaro Akaho, Shun-ichi Amari Kenji Fukumizu
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We show the existence of critical points as lines for the likelihood func- tion of mixture-type models. They are given by embedding of a critical point for models with less components. A sufﬁcient condition that the critical line gives local maxima or saddle points is also derived. Based on this fact, a component-split method is proposed for a mixture of Gaus- sian components, and its effectiveness is veriﬁed through experiments.
Manifold Parzen Windows
Authors: Yoshua Bengio Pascal Vincent
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: The similarity between objects is a fundamental element of many learn- ing algorithms. Most non-parametric methods take this similarity to be ﬁxed, but much recent work has shown the advantages of learning it, in particular to exploit the local invariances in the data or to capture the possibly non-linear manifold on which most of the data lies. We propose a new non-parametric kernel density estimation method which captures the local structure of an underlying manifold through the leading eigen- vectors of regularized local covariance matrices. Experiments in density estimation show signiﬁcant improvements with respect to Parzen density estimators. The density estimators can also be used within Bayes classi- ﬁers, yielding classiﬁcation rates similar to SVMs and much superior to the Parzen classiﬁer.
Parametric Mixture Models for Multi-Labeled Text
Authors: Kazumi Saito Naonori Ueda
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We propose probabilistic generative models, called parametric mix- ture models (PMMs), for multiclass, multi-labeled text categoriza- tion problem. Conventionally, the binary classi(cid:12)cation approach has been employed, in which whether or not text belongs to a cat- egory is judged by the binary classi(cid:12)er for every category. In con- trast, our approach can simultaneously detect multiple categories of text using PMMs. We derive e(cid:14)cient learning and prediction algo- rithms for PMMs. We also empirically show that our method could signi(cid:12)cantly outperform the conventional binary methods when ap- plied to multi-labeled text categorization using real World Wide Web pages.
Transductive and Inductive Methods for Approximate Gaussian Process Regression
Authors: Volker Tresp Anton Schwaighofer
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Gaussian process regression allows a simple analytical treatment of ex- act Bayesian inference and has been found to provide good performance, yet scales badly with the number of training data. In this paper we com- pare several approaches towards scaling Gaussian processes regression to large data sets: the subset of representers method, the reduced rank approximation, online Gaussian processes, and the Bayesian commit- tee machine. Furthermore we provide theoretical insight into some of our experimental results. We found that subset of representers methods can give good and particularly fast predictions for data sets with high and medium noise levels. On complex low noise data sets, the Bayesian committee machine achieves signiﬁcantly better accuracy, yet at a higher computational cost.
Adapting Codes and Embeddings for Polychotomies
Authors: Sebastian Mika, Alex J. Smola Gunnar Rätsch
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: In this paper we consider formulations of multi-class problems based on a generalized notion of a margin and using output coding. This includes, but is not restricted to, standard multi-class SVM formulations. Differ- ently from many previous approaches we learn the code as well as the embedding function. We illustrate how this can lead to a formulation that allows for solving a wider range of problems with for instance many classes or even “missing classes”. To keep our optimization problems tractable we propose an algorithm capable of solving them using two- class classiﬁers, similar in spirit to Boosting.
Topographic Map Formation by Silicon Growth Cones
Authors: Kwabena A. Boahen Brian Taba
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We  describe  a  self-configuring  neuromorphic  chip  that  uses  a  model of activity-dependent axon remodeling to  automatically wire  topographic  maps  based  solely  on  input  correlations.  Axons  are  guided by growth cones, which are modeled in analog VLSI for the  first  time.  Growth  cones  migrate  up  neurotropin  gradients,  which  are  represented  by  charge  diffusing  in  transistor  channels.  Virtual  axons  move  by  rerouting  address-events.  We  refined  an  initially  gross topographic projection by simulating retinal wave input. 
1  Neuromorphic  Systems 
Neuromorphic  engineers  are  attempting  to  match  the  computational  efficiency  of  biological  systems  by  morphing  neurocircuitry  into  silicon  circuits  [1].  One  of the  most  detailed  implementations  to  date  is  the  silicon  retina  described  in  [2] .  This  chip  comprises  thirteen different cell types,  each  of which must be individually and  painstakingly  wired.  While  this  circuit-level  approach  has  been  very  successful  in  sensory  systems,  it  is  less  helpful  when  modeling  largely  unelucidated  and  exceedingly plastic higher processing centers in cortex. 
Instead  of  an  explicit  blueprint  for  every  cortical  area,  what  is  needed  is  a  developmental rule that can wire complex circuits from  minimal  specifications.  One  candidate  is  the  famous  "cells  that  fire  together  wire  together"  rule,  which  strengthens  excitatory  connections  between  coactive  presynaptic  and  postsynaptic  cells.  We  implemented a self-rewiring scheme  of this  type in  silicon,  taking our cue  from axon remodeling during development.
Analysis of Information in Speech Based on MANOVA
Authors: Hynek Hermansky Sachin S. Kajarekar
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We  propose  analysis  of information  in  speech  using  three  sources  - language  (phone),  speaker and channeL  Information in speech is  measured as mutual information between the source and the set of  features  extracted  from  speech  signaL  We  assume  that  distribu(cid:173) tion of features  can be modeled  using  Gaussian distribution.  The  mutual  information  is  computed  using  the  results  of  analysis  of  variability in speech.  We  observe similarity in the results of phone  variability and phone information, and show that the results of the  proposed  analysis  have  more  meaningful  interpretations  than  the  analysis of variability.
Discriminative Binaural Sound Localization
Authors: Yoram Singer Ehud Ben-reuven
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Time difference of arrival (TDOA) is commonly used to estimate the az- imuth of a source in a microphone array. The most common methods to estimate TDOA are based on ﬁnding extrema in generalized cross- correlation waveforms. In this paper we apply microphone array tech- niques to a manikin head. By considering the entire cross-correlation waveform we achieve azimuth prediction accuracy that exceeds extrema locating methods. We do so by quantizing the azimuthal angle and treating the prediction problem as a multiclass categorization task. We demonstrate the merits of our approach by evaluating the various ap- proaches on Sony’s AIBO robot.
Fractional Belief Propagation
Authors: Tom Heskes Wim Wiegerinck
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We consider loopy belief propagation for approximate inference in prob- abilistic graphical models. A limitation of the standard algorithm is that clique marginals are computed as if there were no loops in the graph. To overcome this limitation, we introduce fractional belief propagation. Fractional belief propagation is formulated in terms of a family of ap- proximate free energies, which includes the Bethe free energy and the naive mean-ﬁeld free as special cases. Using the linear response correc- tion of the clique marginals, the scale parameters can be tuned. Simula- tion results illustrate the potential merits of the approach.
Stability-Based Model Selection
Authors: Mikio L. Braun, Volker Roth, Joachim M. Buhmann Tilman Lange
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Model selection is linked to model assessment, which is the problem of comparing different models, or model parameters, for a speciﬁc learning task. For supervised learning, the standard practical technique is cross- validation, which is not applicable for semi-supervised and unsupervised settings. In this paper, a new model assessment scheme is introduced which is based on a notion of stability. The stability measure yields an upper bound to cross-validation in the supervised case, but extends to semi-supervised and unsupervised problems. In the experimental part, the performance of the stability measure is studied for model order se- lection in comparison to standard techniques in this area.