mtybilly/Instruct2DS huggingface dataset:
Learning Hierarchical Structures with Linear Relational Embedding
Authors: Alberto Paccanaro, Geoffrey E. Hinton
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We present Linear Relational Embedding (LRE), a new method of learn- ing a distributed representation of concepts from data consisting of in- stances of relations between given concepts. Its ﬁnal goal is to be able to generalize, i.e. infer new instances of these relations among the con- cepts. On a task involving family relationships we show that LRE can generalize better than any previously published method. We then show how LRE can be used effectively to ﬁnd compact distributed representa- tions for variable-sized recursive data structures, such as trees and lists.
1 Linear Relational Embedding
Our aim is to take a large set of facts about a domain expressed as tuples of arbitrary sym- bols in a simple and rigid syntactic format and to be able to infer other “common-sense” facts without having any prior knowledge about the domain. Let us imagine a situation in which we have a set of concepts and a set of relations among these concepts, and that our data consists of few instances of these relations that hold among the concepts. We want to be able to infer other instances of these relations. For example, if the concepts are the people in a certain family, the relations are kinship relations, and we are given the facts ”Alberto has-father Pietro” and ”Pietro has-brother Giovanni”, we would like to be able to infer ”Alberto has-uncle Giovanni”. Our approach is to learn appropriate distributed rep- resentations of the entities in the data, and then exploit the generalization properties of the distributed representations [2] to make the inferences. In this paper we present a method, which we have called Linear Relational Embedding (LRE), which learns a distributed rep- resentation for the concepts by embedding them in a space where the relations between concepts are linear transformations of their distributed representations.
involve two concepts. Let us consider the case in which all the relations are binary, i.e. , and the problem In this case our data consists of triplets we are trying to solve is to infer missing triplets when we are given only few of them. Inferring a triplet is equivalent to being able to complete it, that is to come up with one of its elements, given the other two. Here we shall always try to complete the third element of the triplets 1. LRE will then represent each concept in the data as a learned vector in a
Products of Gaussians
Authors: Christopher Williams, Felix V. Agakov, Stephen N. Felderhof
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Recently Hinton (1999) has introduced the Products of Experts  (PoE) model in which several individual probabilistic models for  data are combined to provide an overall model of the data. Be(cid:173) low we consider PoE models in which each expert is a Gaussian.  Although the product of Gaussians is also a Gaussian, if each Gaus(cid:173) sian has a simple structure the product can have a richer structure.  We examine (1) Products of Gaussian pancakes which give rise to  probabilistic Minor Components Analysis, (2) products of I-factor  PPCA models and (3) a products of experts construction for an  AR(l) process. 
Recently Hinton (1999) has introduced the Products of Experts (PoE) model in  which several individual probabilistic models for data are combined to provide an  overall model of the data. In this paper we consider PoE models in which each  expert is a Gaussian. It is easy to see that in this case the product model will  also be Gaussian. However, if each Gaussian has a simple structure, the product  can have a richer structure. Using Gaussian experts is attractive as it permits a  thorough analysis of the product architecture, which can be difficult with other  models, e.g. models defined over discrete random variables. 
Below we examine three cases of the products of Gaussians construction: (1) Prod(cid:173) ucts of Gaussian pancakes (PoGP) which give rise to probabilistic Minor Compo(cid:173) nents Analysis (MCA), providing a complementary result to probabilistic Principal  Components Analysis (PPCA) obtained by Tipping and Bishop (1999); (2) Prod(cid:173) ucts of I-factor PPCA models; (3) A products of experts construction for an AR(l)  process. 
Products of Gaussians 
If each expert is a Gaussian pi(xI8i ) '" N(J1i' ( i), the resulting distribution of the  product of m Gaussians may be expressed as 
By completing the square in the exponent it may be easily shown that p(xI8)  N(/1;E, (2:), where (E l = 2::1 (i l . To simplify the following derivations we will  assume that pi(xI8i ) '" N(O, (i) and thus that p(xI8) '" N(O, (2:). J12: i ° can be 
obtained by translation of the coordinate system. 
1 Products of Gaussian Pancakes 
A Gaussian "pancake" (GP) is a d-dimensional Gaussian, contracted in one dimen(cid:173) sion and elongated in the other d - 1 dimensions. In this section we show that the  maximum likelihood solution for a product of Gaussian pancakes (PoGP) yields a  probabilistic formulation of Minor Components Analysis (MCA). 
1.1 Covariance Structure of a GP Expert 
Consider a d-dimensional Gaussian whose probability contours are contracted  in the direction w and equally elongated in mutually orthogonal directions  VI , ... , vd-l.We call this a Gaussian pancake or GP. Its inverse covariance may be  written as
The Fidelity of Local Ordinal Encoding
Authors: Javid Sadr, Sayan Mukherjee, Keith Thoresz, Pawan Sinha
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: A key question in neuroscience is how to encode sensory stimuli such as images and sounds. Motivated by studies of response prop- erties of neurons in the early cortical areas, we propose an encoding scheme that dispenses with absolute measures of signal intensity or contrast and uses, instead, only local ordinal measures. In this scheme, the structure of a signal is represented by a set of equalities and inequalities across adjacent regions. In this paper, we focus on characterizing the (cid:12)delity of this representation strategy. We develop a regularization approach for image reconstruction from ordinal measures and thereby demonstrate that the ordinal repre- sentation scheme can faithfully encode signal structure. We also present a neurally plausible implementation of this computation that uses only local update rules. The results highlight the robust- ness and generalization ability of local ordinal encodings for the task of pattern classi(cid:12)cation.
Correlation Codes in Neuronal Populations
Authors: Maoz Shamir, Haim Sompolinsky
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Population codes often rely on the tuning of the mean responses to the stimulus parameters. However, this information can be greatly sup- pressed by long range correlations. Here we study the efﬁciency of cod- ing information in the second order statistics of the population responses. We show that the Fisher Information of this system grows linearly with the size of the system. We propose a bilinear readout model for extract- ing information from correlation codes, and evaluate its performance in discrimination and estimation tasks. It is shown that the main source of information in this system is the stimulus dependence of the variances of the single neuron responses.
The Steering Approach for Multi-Criteria Reinforcement Learning
Authors: Shie Mannor, Nahum Shimkin
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We consider the problem of learning to attain multiple goals in a dynamic envi- ronment, which is initially unknown. In addition, the environment may contain arbitrarily varying elements related to actions of other agents or to non-stationary moves of Nature. This problem is modelled as a stochastic (Markov) game between the learning agent and an arbitrary player, with a vector-valued reward function. The objective of the learning agent is to have its long-term average reward vector belong to a given target set. We devise an algorithm for achieving this task, which is based on the theory of approachability for stochastic games. This algorithm com- bines, in an appropriate way, a ﬂnite set of standard, scalar-reward learning algo- rithms. Su–cient conditions are given for the convergence of the learning algorithm to a general target set. The specialization of these results to the single-controller Markov decision problem are discussed as well.
Stabilizing Value Function Approximation with the BFBP Algorithm
Authors: Xin Wang, Thomas G. Dietterich
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We address the problem of non-convergence of online reinforcement learning algorithms (e.g., Q learning and SARSA(A)) by adopt(cid:173) ing an incremental-batch approach that separates the exploration process from the function fitting process. Our BFBP (Batch Fit to Best Paths) algorithm alternates between an exploration phase (during which trajectories are generated to try to find fragments of the optimal policy) and a function fitting phase (during which a function approximator is fit to the best known paths from start states to terminal states). An advantage of this approach is that batch value-function fitting is a global process, which allows it to address the tradeoffs in function approximation that cannot be handled by local, online algorithms. This approach was pioneered by Boyan and Moore with their GROWSUPPORT and ROUT al(cid:173) gorithms. We show how to improve upon their work by applying a better exploration process and by enriching the function fitting procedure to incorporate Bellman error and advantage error mea(cid:173) sures into the objective function. The results show improved per(cid:173) formance on several benchmark problems.
Tree-based reparameterization for approximate inference on loopy graphs
Authors: Martin J. Wainwright, Tommi Jaakkola, Alan S. Willsky
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We  develop  a  tree-based  reparameterization framework  that  pro(cid:173) vides a  new conceptual view of a  large class of iterative algorithms  for  computing  approximate  marginals  in  graphs  with  cycles.  It  includes  belief propagation  (BP),  which  can  be  reformulated  as  a  very local form of reparameterization.  More generally, we  consider  algorithms  that  perform  exact  computations  over  spanning  trees  of  the  full  graph.  On  the  practical  side,  we  find  that  such  tree  reparameterization (TRP)  algorithms have convergence properties  superior  to  BP.  The  reparameterization perspective  also  provides  a  number  of  theoretical  insights  into  approximate  inference,  in(cid:173) cluding  a  new  characterization  of fixed  points;  and  an  invariance  intrinsic  to  TRP /BP.  These  two  properties  enable  us  to  analyze  and  bound  the  error  between  the  TRP /BP  approximations  and  the  actual  marginals.  While  our  results  arise  naturally  from  the  TRP perspective, most of them apply in an algorithm-independent  manner  to  any  local  minimum  of the  Bethe  free  energy.  Our  re(cid:173) sults  also  have  natural  extensions  to  more  structured approxima(cid:173) tions  [e.g. ,  1,  2].
Cobot: A Social Reinforcement Learning Agent
Authors: Charles Lee Isbell Jr., Christian R. Shelton
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We report on the use of reinforcement learning with Cobot, a software agent residing in the well-known online community LambdaMOO. Our initial work on Cobot (Isbell et al.2000) provided him with the ability to collect social statistics and report them to users. Here we describe an application of RL allowing Cobot to take proactive actions in this complex social environment, and adapt behavior from multiple sources of human reward. After 5 months of training, and 3171 reward and punishment events from 254 different LambdaMOO users, Cobot learned nontrivial preferences for a number of users, modiﬁng his behavior based on his current state. Here we describe LambdaMOO and the state and action spaces of Cobot, and report the statistical results of the learning experiment.
Semi-supervised MarginBoost
Authors: Florence d'Alché-Buc, Yves Grandvalet, Christophe Ambroise
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: In many discrimination problems a large amount of data is available but  only a few of them are labeled. This provides a strong motivation to  improve or develop methods for semi-supervised learning. In this paper,  boosting is generalized to this task within the optimization framework of  MarginBoost . We extend the margin definition to unlabeled data and  develop the gradient descent algorithm that corresponds to the resulting  margin cost function. This meta-learning scheme can be applied to any  base classifier able to benefit from unlabeled data. We propose here to  apply it to mixture models trained with an Expectation-Maximization  algorithm. Promising results are presented on benchmarks with different  rates of labeled data.
ALGONQUIN - Learning Dynamic Noise Models From Noisy Speech for Robust Speech Recognition
Authors: Brendan J. Frey, Trausti T. Kristjansson, Li Deng, Alex Acero
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: A  challenging,  unsolved  problem  in  the  speech  recognition  com(cid:173) munity  is  recognizing  speech  signals  that  are  corrupted  by  loud,  highly  nonstationary noise.  One  approach to  noisy  speech  recog(cid:173) nition is  to automatically  remove the noise from  the  cepstrum se(cid:173) quence before feeding it in to a clean speech recognizer.  In previous  work published in  Eurospeech,  we  showed how  a  probability model  trained on  clean  speech  and  a  separate probability  model  trained  on noise could be combined for the purpose of estimating the noise(cid:173) free speech from the noisy speech.  We showed how an iterative 2nd  order  vector  Taylor  series  approximation  could  be  used  for  prob(cid:173) abilistic  inference  in this  model.  In  many  circumstances,  it is  not  possible to obtain  examples  of noise  without  speech.  Noise  statis(cid:173) tics  may change significantly  during an utterance,  so  that speech(cid:173) free frames are not sufficient for  estimating the noise model.  In this  paper, we  show how the noise model can be learned even when the  data contains speech.  In particular, the noise model can be learned  from the test utterance and then used to de noise the test utterance.  The approximate inference technique is  used as  an approximate E  step  in  a  generalized  EM  algorithm that learns the parameters of  the noise  model from  a  test utterance.  For both Wall  Street  J our(cid:173) nal data with added noise samples and the Aurora benchmark, we  show that the new noise adaptive technique performs as  well  as or  significantly better  than  the  non-adaptive  algorithm,  without  the  need for  a  separate training set of noise examples.
Adaptive Nearest Neighbor Classification Using Support Vector Machines
Authors: Carlotta Domeniconi, Dimitrios Gunopulos
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: The nearest  neighbor technique is  a  simple  and appealing method  to  address  classification  problems.  It relies  on  t he  assumption  of  locally  constant  class  conditional  probabilities.  This  assumption  becomes  invalid  in high  dimensions with a  finite  number of exam(cid:173) ples  due  to  the  curse  of dimensionality.  We  propose  a  technique  that computes a  locally flexible  metric by means of Support Vector  Machines  (SVMs).  The maximum margin boundary found  by the  SVM is used to determine the most discriminant direction over the  query's  neighborhood.  Such  direction  provides  a  local  weighting  scheme  for  input  features.  We  present  experimental  evidence  of  classification  performance  improvement  over  the  SVM  algorithm  alone  and  over  a  variety  of adaptive  learning  schemes,  by  using  both simulated and real data sets.
Fast, Large-Scale Transformation-Invariant Clustering
Authors: Brendan J. Frey, Nebojsa Jojic
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: In previous work on transformed mixtures of Gaussians'' andtransformed hidden Markov models'', we showed how the EM al- gorithm in a discrete latent variable model can be used to jointly normalize data (e.g., center images, pitch-normalize spectrograms) and learn a mixture model of the normalized data. The only input to the algorithm is the data, a list of possible transformations, and the number of clusters to find. The main criticism of this work was that the exhaustive computation of the posterior probabili- ties over transformations would make scaling up to large feature vectors and large sets of transformations intractable. Here, we de- scribe how a tremendous speed-up is acheived through the use of a variational technique for decoupling transformations, and a fast Fourier transform method for computing posterior probabilities. For NN images, learning C clusters under N rotations, N scales,
N x-translations and N y-translations takes only (C + 2 log N)N
2
scalar operations per iteration. In contrast, the original algorithm takes CN
6
operations to account for these transformations. We give results on learning a 4-component mixture model from a video sequence with frames of size 320240. The model accounts for 360 rotations and 76,800 translations. Each iteration of EM takes only 10 seconds per frame in MATLAB, which is over 5 million times faster than the original algorithm.
A Rotation and Translation Invariant Discrete Saliency Network
Authors: Lance R. Williams, John W. Zweck
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We describe a neural network which enhances and completes salient closed contours. Our work is different from all previous work in three important ways. First, like the input provided to V1 by LGN, the in- put to our computation is isotropic. That is, the input is composed of spots not edges. Second, our network computes a well deﬁned function of the input based on a distribution of closed contours characterized by a random process. Third, even though our computation is implemented in a discrete network, its output is invariant to continuous rotations and translations of the input pattern.
A theory of neural integration in the head-direction system
Authors: Richard Hahnloser, Xiaohui Xie, H. S. Seung
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Integration in the head-direction system is a computation by which hor- izontal angular head velocity signals from the vestibular nuclei are in- tegrated to yield a neural representation of head direction. In the thala- mus, the postsubiculum and the mammillary nuclei, the head-direction representation has the form of a place code: neurons have a preferred head direction in which their ﬁring is maximal [Blair and Sharp, 1995, Blair et al., 1998, ?]. Integration is a difﬁcult computation, given that head-velocities can vary over a large range. Previous models of the head-direction system relied on the assumption that the integration is achieved in a ﬁring-rate-based attractor network with a ring structure. In order to correctly integrate head-velocity signals during high-speed head rotations, very fast synaptic dynamics had to be assumed. Here we address the question whether integration in the head-direction system is possible with slow synapses, for example excitatory NMDA and inhibitory GABA(B) type synapses. For neural networks with such slow synapses, rate-based dynamics are a good approximation of spik- ing neurons [Ermentrout, 1994]. We ﬁnd that correct integration during high-speed head rotations imposes strong constraints on possible net- work architectures.
(Not) Bounding the True Error
Authors: John Langford, Rich Caruana
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We present a new approach to bounding the true error rate of a continuous valued classiﬁer based upon PAC-Bayes bounds. The method ﬁrst con- structs a distribution over classiﬁers by determining how sensitive each parameter in the model is to noise. The true error rate of the stochastic classiﬁer found with the sensitivity analysis can then be tightly bounded using a PAC-Bayes bound. In this paper we demonstrate the method on artiﬁcial neural networks with results of a  order of magnitude im- provement vs. the best deterministic neural net bounds.
Novel iteration schemes for the Cluster Variation Method
Authors: Hilbert J. Kappen, Wim Wiegerinck
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: The  Cluster  Variation  method  is  a  class  of approximation  meth(cid:173) ods  containing  the  Bethe  and  Kikuchi  approximations  as  special  cases.  We  derive  two  novel iteration schemes  for  the  Cluster Vari(cid:173) ation Method.  One is  a fixed  point iteration scheme which gives  a  significant improvement over loopy BP, mean field  and TAP meth(cid:173) ods  on  directed  graphical  models.  The  other  is  a  gradient  based  method, that is  guaranteed to converge and is  shown to give useful  results on random graphs with mild frustration.  We  conclude that  the  methods  are  of  significant  practical  value  for  large  inference  problems.
Infinite Mixtures of Gaussian Process Experts
Authors: Carl E. Rasmussen, Zoubin Ghahramani
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We present an extension to the Mixture of Experts (ME) model, where the individual experts are Gaussian Process (GP) regression models. Us- ing an input-dependent adaptation of the Dirichlet Process, we imple- ment a gating network for an inﬁnite number of Experts. Inference in this model may be done efﬁciently using a Markov Chain relying on Gibbs sampling. The model allows the effective covariance function to vary with the inputs, and may handle large datasets – thus potentially over- coming two of the biggest hurdles with GP models. Simulations show the viability of this approach.
Relative Density Nets: A New Way to Combine Backpropagation with HMM's
Authors: Andrew D. Brown, Geoffrey E. Hinton
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Logistic units in the first  hidden layer of a  feedforward neural net(cid:173) work  compute  the  relative  probability  of a  data point  under  two  Gaussians.  This  leads  us  to  consider  substituting  other  density  models.  We  present  an architecture for  performing discriminative  learning of Hidden Markov Models using a  network of many small  HMM's.  Experiments on speech  data show it  to be superior to the  standard method of discriminatively training HMM's.
Neural Implementation of Bayesian Inference in Population Codes
Authors: Si Wu, Shun-ichi Amari
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: This study investigates a  population decoding paradigm, in  which  the  estimation  of  stimulus  in  the  previous  step  is  used  as  prior  knowledge for consecutive decoding.  We analyze the decoding accu(cid:173) racy of such a  Bayesian decoder (Maximum a Posteriori Estimate),  and  show  that  it  can  be  implemented  by  a  biologically  plausible  recurrent  network,  where  the  prior  knowledge  of stimulus  is  con(cid:173) veyed by the change in recurrent interactions as a result of Hebbian  learning.
TAP Gibbs Free Energy, Belief Propagation and Sparsity
Authors: Lehel Csató, Manfred Opper, Ole Winther
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: The adaptive TAP Gibbs free energy for a general densely connected probabilistic model with quadratic interactions and arbritary single site constraints is derived. We show how a speciﬁc sequential minimization of the free energy leads to a generalization of Minka’s expectation propa- gation. Lastly, we derive a sparse representation version of the sequential algorithm. The usefulness of the approach is demonstrated on classiﬁca- tion and density estimation with Gaussian processes and on an indepen- dent component analysis problem.
Quantizing Density Estimators
Authors: Peter Meinicke, Helge Ritter
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We suggest a nonparametric framework for unsupervised learning of projection models in terms of density estimation on quantized sample spaces. The objective is not to optimally reconstruct the data but in- stead the quantizer is chosen to optimally reconstruct the density of the data. For the resulting quantizing density estimator (QDE) we present a general method for parameter estimation and model selection. We show how projection sets which correspond to traditional unsupervised meth- ods like vector quantization or PCA appear in the new framework. For a principal component quantizer we present results on synthetic and real- world data, which show that the QDE can improve the generalization of the kernel density estimator although its estimate is based on signiﬁcantly lower-dimensional projection indices of the data.
The Concave-Convex Procedure (CCCP)
Authors: Alan L. Yuille, Anand Rangarajan
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We  introduce the  Concave-Convex procedure  (CCCP)  which  con(cid:173) structs discrete  time  iterative  dynamical  systems  which  are  guar(cid:173) anteed to monotonically decrease global optimization/energy func(cid:173) tions.  It can be applied to  (almost)  any optimization problem and  many existing algorithms can be interpreted in terms of CCCP.  In  particular, we  prove relationships to some applications of Legendre  transform techniques.  We  then illustrate CCCP by applications to  Potts models, linear assignment,  EM  algorithms,  and  Generalized  Iterative Scaling  (GIS).  CCCP  can be  used  both as  a  new  way  to  understand existing optimization algorithms and as a procedure for  generating new algorithms.
Active Learning in the Drug Discovery Process
Authors: Manfred K. Warmuth, Gunnar Rätsch, Michael Mathieson, Jun Liao, Christian Lemmen
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We investigate the following data mining problem from Computational Chemistry: From a large data set of compounds, ﬁnd those that bind to a target molecule in as few iterations of biological testing as possible. In each iteration a comparatively small batch of compounds is screened for binding to the target. We apply active learning techniques for selecting the successive batches. One selection strategy picks unlabeled examples closest to the maximum margin hyperplane. Another produces many weight vectors by running perceptrons over multiple permutations of the data. Each weight vector prediction and we pick the unlabeled examples for which votes with its the prediction is most evenly split between . For a third selec- tion strategy note that each unlabeled example bisects the version space of consistent weight vectors. We estimate the volume on both sides of the split by bouncing a billiard through the version space and select un- labeled examples that cause the most even split of the version space. We demonstrate that on two data sets provided by DuPont Pharmaceu- ticals that all three selection strategies perform comparably well and are much better than selecting random batches for testing.
and
Intransitive Likelihood-Ratio Classifiers
Authors: Jeff Bilmes, Gang Ji, Marina Meila
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: In this work, we introduce an information-theoretic based correction term to the likelihood ratio classiﬁcation method for multiple classes. Under certain conditions, the term is sufﬁcient for optimally correcting the dif- ference between the true and estimated likelihood ratio, and we analyze this in the Gaussian case. We ﬁnd that the new correction term signif- icantly improves the classiﬁcation results when tested on medium vo- cabulary speech recognition tasks. Moreover, the addition of this term makes the class comparisons analogous to an intransitive game and we therefore use several tournament-like strategies to deal with this issue. We ﬁnd that further small improvements are obtained by using an appro- priate tournament. Lastly, we ﬁnd that intransitivity appears to be a good measure of classiﬁcation conﬁdence.
Transform-invariant Image Decomposition with Similarity Templates
Authors: Chris Stauffer, Erik Miller, Kinh Tieu
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Recent work has shown impressive transform-invariant modeling and clustering for sets of images of objects with similar appearance. We seek to expand these capabilities to sets of images of an object class that show considerable variation across individual instances (e.g. pedestrian images) using a representation based on pixel-wise similarities, similarity templates. Because of its invariance to the colors of particular components of an object, this representation en- ables detection of instances of an object class and enables alignment of those instances. Further, this model implicitly represents the re- gions of color regularity in the class-speci(cid:12)c image set enabling a decomposition of that object class into component regions.
Activity Driven Adaptive Stochastic Resonance
Authors: Gregor Wenning, Klaus Obermayer
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Cortical neurons might be considered as threshold elements inte(cid:173) grating in parallel many excitatory and inhibitory inputs. Due to  the apparent variability of cortical spike trains this yields a strongly  fluctuating membrane potential, such that threshold crossings are  highly irregular. Here we study how a neuron could maximize its  sensitivity w.r.t. a relatively small subset of excitatory input. Weak  signals embedded in fluctuations is the natural realm of stochastic  resonance. The neuron's response is described in a hazard-function  approximation applied to an Ornstein-Uhlenbeck process. We an(cid:173) alytically derive an optimality criterium and give a learning rule  for the adjustment of the membrane fluctuations, such that the  sensitivity is maximal exploiting stochastic resonance. We show  that adaptation depends only on quantities that could easily be  estimated locally (in space and time) by the neuron. The main  results are compared with simulations of a biophysically more re(cid:173) alistic neuron model.
A Dynamic HMM for On-line Segmentation of Sequential Data
Authors: Jens Kohlmorgen, Steven Lemm
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We  propose  a  novel  method  for  the  analysis  of  sequential  data  that exhibits  an inherent  mode  switching.  In  particular,  the  data  might  be  a  non-stationary  time  series  from  a  dynamical  system  that switches between multiple operating modes.  Unlike other ap(cid:173) proaches, our method processes the data incrementally and without  any  training of internal  parameters.  We  use  an  HMM  with  a  dy(cid:173) namically changing number of states and an on-line variant of the  Viterbi algorithm that performs an unsupervised segmentation and  classification of the data on-the-fly,  i.e.  the method is  able to pro(cid:173) cess  incoming data in  real-time.  The main idea  of the approach is  to track and segment changes of the probability density of the data  in  a  sliding window  on the incoming  data stream.  The usefulness  of the algorithm is  demonstrated  by an application to a  switching  dynamical system.
The Intelligent surfer: Probabilistic Combination of Link and Content Information in PageRank
Authors: Matthew Richardson, Pedro Domingos
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: The PageRank algorithm, used in the Google search engine, greatly  improves the results of Web search by taking into account the link  structure  of  the  Web.  PageRank  assigns  to  a  page  a  score  propor- tional to the number of times a random surfer would visit that page,  if  it  surfed  indefinitely  from  page  to  page,  following  all  outlinks  from  a  page  with  equal  probability.  We  propose  to  improve  Page- Rank  by  using  a  more  intelligent  surfer,  one  that  is  guided  by  a  probabilistic model of the relevance of a page to a query. Efficient  execution  of  our  algorithm  at  query  time  is  made  possible  by  pre- computing  at  crawl  time  (and  thus  once  for  all  queries)  the  neces- sary  terms.  Experiments  on  two  large  subsets  of  the  Web  indicate  that  our  algorithm  significantly  outperforms  PageRank  in  the  (hu- man-rated)  quality  of the pages returned, while remaining efficient  enough to be used in today’s large search engines.
Grouping and dimensionality reduction by locally linear embedding
Authors: Marzia Polito, Pietro Perona
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: (LLE) 
Locally Linear Embedding  is an elegant nonlinear  dimensionality-reduction technique recently introduced by Roweis  and Saul [2]. It fails when the data is divided into separate groups.  We study a variant of LLE that can simultaneously group the data  and calculate local embedding of each group. An estimate for the  upper bound on the intrinsic dimension of the data set is obtained  automatically.
Partially labeled classification with Markov random walks
Authors: Martin Szummer, Tommi Jaakkola
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: To classify a large number of unlabeled examples we combine a lim- ited number of labeled examples with a Markov random walk represen- tation over the unlabeled examples. The random walk representation ex- ploits any low dimensional structure in the data in a robust, probabilistic manner. We develop and compare several estimation criteria/algorithms suited to this representation. This includes in particular multi-way clas- siﬁcation with an average margin criterion which permits a closed form solution. The time scale of the random walk regularizes the representa- tion and can be set through a margin-based criterion favoring unambigu- ous classiﬁcation. We also extend this basic regularization by adapting time scales for individual examples. We demonstrate the approach on synthetic examples and on text classiﬁcation problems.
Dynamic Time-Alignment Kernel in Support Vector Machine
Authors: Hiroshi Shimodaira, Ken-ichi Noma, Mitsuru Nakai, Shigeki Sagayama
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: A new class of Support Vector Machine (SVM) that is applica- ble to sequential-pattern recognition such as speech recognition is developed by incorporating an idea of non-linear time alignment into the kernel function. Since the time-alignment operation of sequential pattern is embedded in the new kernel function, stan- dard SVM training and classification algorithms can be employed without further modifications. The proposed SVM (DTAK-SVM) is evaluated in speaker-dependent speech recognition experiments of hand-segmented phoneme recognition. Preliminary experimen- tal results show comparable recognition performance with hidden Markov models (HMMs). 1 Introduction
Support Vector Machine (SVM) [1] is one of the latest and most successful statistical pattern classifier that utilizes a kernel technique [2, 3]. The basic form of SVM classifier which classifies an input vector x
Linear-time inference in Hierarchical HMMs
Authors: Kevin P. Murphy, Mark A. Paskin
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: The hierarchical hidden Markov model (HHMM) is a generalization of the hidden Markov model (HMM) that models sequences with structure at many length/time scales [FST98]. Unfortunately, the original infer- is ence algorithm is rather complicated, and takes the length of the sequence, making it impractical for many domains. In this paper, we show how HHMMs are a special kind of dynamic Bayesian network (DBN), and thereby derive a much simpler inference algorithm, which only takes time. Furthermore, by drawing the connection between HHMMs and DBNs, we enable the application of many stan- dard approximation techniques to further speed up inference.
Direct value-approximation for factored MDPs
Authors: Dale Schuurmans, Relu Patrascu
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We present a simple approach for computing reasonable policies for factored Markov decision processes (MDPs), when the opti(cid:173) mal value function can be approximated by a compact linear form. Our method is based on solving a single linear program that ap(cid:173) proximates the best linear fit to the optimal value function. By applying an efficient constraint generation procedure we obtain an iterative solution method that tackles concise linear programs. This direct linear programming approach experimentally yields a signif(cid:173) icant reduction in computation time over approximate value- and policy-iteration methods (sometimes reducing several hours to a few seconds). However, the quality of the solutions produced by linear programming is weaker-usually about twice the approxi(cid:173) mation error for the same approximating class. Nevertheless, the speed advantage allows one to use larger approximation classes to achieve similar error in reasonable time.
Scaling Laws and Local Minima in Hebbian ICA
Authors: Magnus Rattray, Gleb Basalyga
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We study the dynamics of a Hebbian ICA algorithm extracting a sin- gle non-Gaussian component from a high-dimensional Gaussian back- ground. For both on-line and batch learning we ﬁnd that a surprisingly large number of examples are required to avoid trapping in a sub-optimal state close to the initial conditions. To extract a skewed signal at least  examples are required for  -dimensional data and    
 exam- ples are required to extract a symmetrical signal with non-zero kurtosis.
Online Learning with Kernels
Authors: Jyrki Kivinen, Alex J. Smola, Robert C. Williamson
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We consider online learning in a Reproducing Kernel Hilbert Space. Our method is computationally efﬁcient and leads to simple algorithms. In particular we derive update equations for classiﬁcation, regression, and novelty detection. The inclusion of the  -trick allows us to give a robust parameterization. Moreover, unlike in batch learning where the  -trick only applies to the -insensitive loss function we are able to derive gen- eral trimmed-mean types of estimators such as for Huber’s robust loss.
3 state neurons for contextual processing
Authors: Ádám Kepecs, S. Raghavachari
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Neurons  receive  excitatory  inputs  via  both  fast  AMPA  and  slow  NMDA  type  receptors.  We  find  that  neurons  receiving  input  via  NMDA  receptors  can have  two  stable  membrane states  which  are  input  dependent.  Action potentials can only be initiated from  the  higher voltage state.  Similar observations have been  made in sev(cid:173) eral  brain areas  which  might  be  explained  by our model.  The  in(cid:173) teractions  between the two  kinds  of inputs lead us  to suggest that  some  neurons  may  operate in  3  states:  disabled,  enabled  and  fir(cid:173) ing.  Such  enabled,  but non-firing modes  can be used to introduce  context-dependent  processing  in  neural  networks.  We  provide  a  simple example and discuss possible implications for  neuronal pro(cid:173) cessing and response variability.
Convolution Kernels for Natural Language
Authors: Michael Collins, Nigel Duffy
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We describe the application of kernel methods to Natural Language Pro- cessing (NLP) problems. In many NLP tasks the objects being modeled are strings, trees, graphs or other discrete structures which require some mechanism to convert them into feature vectors. We describe kernels for various natural language structures, allowing rich, high dimensional rep- resentations of these structures. We show how a kernel over trees can be applied to parsing using the voted perceptron algorithm, and we give experimental results on the ATIS corpus of parse trees.
On the Convergence of Leveraging
Authors: Gunnar Rätsch, Sebastian Mika, Manfred K. Warmuth
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We give an unified convergence analysis of ensemble learning meth- ods including e.g. AdaBoost, Logistic Regression and the Least-Square- Boost algorithm for regression. These methods have in common that they iteratively call a base learning algorithm which returns hypotheses that are then linearly combined. We show that these methods are related to the Gauss-Southwell method known from numerical optimization and state non-asymptotical convergence results for all these methods. Our analysis includes ` 1 -norm regularized cost functions leading to a clean and general way to regularize ensemble learning. 1 Introduction
We show convergence rates of ensemble learning methods such as AdaBoost [10], Logistic Regression (LR) [11, 5] and the Least-Square (LS) regression algorithm called LS-Boost [12]. These algorithms have in common that they iteratively call a base learning algorithm
L (also called weak learner) on a weighted training sample. The base learner is expected to return in each iteration t a hypothesis
^
h t from some hypothesis set of weak hypotheses
H that has small weighted training error. This is the weighted number of false predictions in classification and weighted estimation error in regression. These hypotheses are then linearly combined to form the final hypothesis f ^   (x) =
A Quantitative Model of Counterfactual Reasoning
Authors: Daniel Yarlett, Michael Ramscar
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: In this paper we explore two quantitative approaches to the modelling of counterfactual reasoning – a linear and a noisy-OR model – based on in- formation contained in conceptual dependency networks. Empirical data is acquired in a study and the ﬁt of the models compared to it. We con- clude by considering the appropriateness of non-parametric approaches to counterfactual reasoning, and examining the prospects for other para- metric approaches in the future.
A Neural Oscillator Model of Auditory Selective Attention
Authors: Stuart N. Wrigley, Guy J. Brown
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: A model of auditory grouping is described in which auditory attention plays a key role. The model is based upon an oscillatory correlation framework, in which neural oscillators representing a single perceptual stream are synchronised, and are desynchronised from oscillators representing other streams. The model suggests a mechanism by which attention can be directed to the high or low tones in a repeating sequence of tones with alternating frequencies. In addition, it simulates the perceptual segregation of a mistuned harmonic from a complex tone.
Self-regulation Mechanism of Temporally Asymmetric Hebbian Plasticity
Authors: N. Matsumoto, M. Okada
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Recent biological experimental (cid:12)ndings have shown that the synap- tic plasticity depends on the relative timing of the pre- and post- synaptic spikes which determines whether Long Term Potentiation (LTP) occurs or Long Term Depression (LTD) does. The synaptic plasticity has been called \Temporally Asymmetric Hebbian plas- ticity (TAH)". Many authors have numerically shown that spatio- temporal patterns can be stored in neural networks. However, the mathematical mechanism for storage of the spatio-temporal pat- terns is still unknown, especially the e(cid:11)ects of LTD. In this paper, we employ a simple neural network model and show that inter- ference of LTP and LTD disappears in a sparse coding scheme. On the other hand, it is known that the covariance learning is in- dispensable for storing sparse patterns. We also show that TAH qualitatively has the same e(cid:11)ect as the covariance learning when spatio-temporal patterns are embedded in the network.
An Efficient, Exact Algorithm for Solving Tree-Structured Graphical Games
Authors: Michael L. Littman, Michael J. Kearns, Satinder P. Singh
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We  describe a  new  algorithm for  computing a  Nash equilibrium in  graphical  games,  a compact representation for  multi-agent systems  that  we  introduced  in  previous  work.  The  algorithm  is  the  first  to compute equilibria both efficiently  and exactly for  a  non-trivial  class of graphical games.
Unsupervised Learning of Human Motion Models
Authors: Yang Song, Luis Goncalves, Pietro Perona
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: This paper presents an unsupervised learning algorithm that can derive the probabilistic dependence structure of parts of an object (a moving hu- man body in our examples) automatically from unlabeled data. The dis- tinguished part of this work is that it is based on unlabeled data, i.e., the training features include both useful foreground parts and background clutter and the correspondence between the parts and detected features are unknown. We use decomposable triangulated graphs to depict the probabilistic independence of parts, but the unsupervised technique is not limited to this type of graph. In the new approach, labeling of the data (part assignments) is taken as hidden variables and the EM algo- rithm is applied. A greedy algorithm is developed to select parts and to search for the optimal structure based on the differential entropy of these variables. The success of our algorithm is demonstrated by applying it to generate models of human motion automatically from unlabeled real image sequences.