mtybilly/Instruct2DS huggingface dataset:
Prediction and Semantic Association
Authors: Thomas L. Griffiths, Mark Steyvers
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We  explore  the  consequences  of  viewing  semantic  association  as  the result of attempting to predict the concepts likely to arise in a  particular context.  We  argue that the success of existing accounts  of semantic representation comes as a result of indirectly addressing  this problem, and show that a closer correspondence to human data  can be obtained by taking a  probabilistic approach that explicitly  models the generative structure of language.
A Maximum Entropy Approach to Collaborative Filtering in Dynamic, Sparse, High-Dimensional Domains
Authors: Dmitry Y. Pavlov, David M. Pennock
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We develop a maximum entropy (maxent) approach to generating recom- mendations in the context of a user’s current navigation stream, suitable for environments where data is sparse, high-dimensional, and dynamic— conditions typical of many recommendation applications. We address sparsity and dimensionality reduction by ﬁrst clustering items based on user access patterns so as to attempt to minimize the apriori probabil- ity that recommendations will cross cluster boundaries and then recom- mending only within clusters. We address the inherent dynamic nature of the problem by explicitly modeling the data as a time series; we show how this representational expressivity ﬁts naturally into a maxent frame- work. We conduct experiments on data from ResearchIndex, a popu- lar online repository of over 470,000 computer science documents. We show that our maxent formulation outperforms several competing algo- rithms in ofﬂine tests simulating the recommendation of documents to ResearchIndex users.
Annealing and the Rate Distortion Problem
Authors: Albert E. Parker, Tomá\v S. Gedeon, Alexander G. Dimitrov
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: In this paper we introduce methodology to determine the bifurcation structure of optima for a class of similar cost functions from Rate Distortion Theory, Determin- istic Annealing, Information Distortion and the Information Bottleneck Method. We also introduce a numerical algorithm which uses the explicit form of the bifur- cating branches to ﬁnd optima at a bifurcation point.
Self Supervised Boosting
Authors: Max Welling, Richard S. Zemel, Geoffrey E. Hinton
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Boosting algorithms and successful applications thereof abound for clas- siﬁcation and regression learning problems, but not for unsupervised learning. We propose a sequential approach to adding features to a ran- dom ﬁeld model by training them to improve classiﬁcation performance between the data and an equal-sized sample of “negative examples” gen- erated from the model’s current estimate of the data density. Training in each boosting round proceeds in three stages: ﬁrst we sample negative examples from the model’s current Boltzmann distribution. Next, a fea- ture is trained to improve classiﬁcation performance between data and negative examples. Finally, a coefﬁcient is learned which determines the importance of this feature relative to ones already in the pool. Negative examples only need to be generated once to learn each new feature. The validity of the approach is demonstrated on binary digits and continuous synthetic data.
Convergent Combinations of Reinforcement Learning with Linear Function Approximation
Authors: Ralf Schoknecht, Artur Merke
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Convergence  for  iterative  reinforcement  learning  algorithms  like  TD(O)  depends on the sampling strategy for  the transitions.  How(cid:173) ever,  in  practical  applications  it  is  convenient  to  take  transition  data  from  arbitrary  sources  without  losing  convergence.  In  this  paper we  investigate the problem of repeated synchronous updates  based on a  fixed  set of transitions.  Our main theorem yields  suffi(cid:173) cient  conditions  of convergence for  combinations  of reinforcement  learning algorithms and linear function approximation.  This allows  to analyse if a  certain reinforcement learning algorithm and a  cer(cid:173) tain function approximator are  compatible.  For the combination of  the residual gradient algorithm with grid-based linear interpolation  we  show  that there exists  a  universal  constant  learning rate such  that the  iteration  converges  independently  of the  concrete  transi(cid:173) tion data.
Automatic Acquisition and Efficient Representation of Syntactic Structures
Authors: Zach Solan, Eytan Ruppin, David Horn, Shimon Edelman
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: The distributional principle according to which morphemes that occur in identical contexts belong, in some sense, to the same category [1] has been advanced as a means for extracting syntactic structures from corpus data. We extend this principle by applying it recursively, and by us- ing mutual information for estimating category coherence. The resulting model learns, in an unsupervised fashion, highly structured, distributed representations of syntactic knowledge from corpora. It also exhibits promising behavior in tasks usually thought to require representations anchored in a grammar, such as systematicity.
Application of Variational Bayesian Approach to Speech Recognition
Authors: Shinji Watanabe, Yasuhiro Minami, Atsushi Nakamura, Naonori Ueda
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: In this paper, we propose a Bayesian framework, which constructs shared-state triphone HMMs based on a variational Bayesian approach, and recognizes speech based on the Bayesian prediction classi(cid:2)cation; variational Bayesian estimation and clustering for speech recognition (VBEC). An appropriate model structure with high recognition perfor- mance can be found within a VBEC framework. Unlike conventional methods, including BIC or MDL criterion based on the maximum likeli- hood approach, the proposed model selection is valid in principle, even when there are insuf(cid:2)cient amounts of data, because it does not use an asymptotic assumption. In isolated word recognition experiments, we show the advantage of VBEC over conventional methods, especially when dealing with small amounts of data.
Identity Uncertainty and Citation Matching
Authors: Hanna Pasula, Bhaskara Marthi, Brian Milch, Stuart Russell, Ilya Shpitser
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Identity uncertainty is a pervasive problem in real-world data analysis. It arises whenever objects are not labeled with unique identiﬁers or when those identiﬁers may not be perceived perfectly. In such cases, two ob- servations may or may not correspond to the same object. In this paper, we consider the problem in the context of citation matching—the prob- lem of deciding which citations correspond to the same publication. Our approach is based on the use of a relational probability model to deﬁne a generative model for the domain, including models of author and title corruption and a probabilistic citation grammar. Identity uncertainty is handled by extending standard models to incorporate probabilities over the possible mappings between terms in the language and objects in the domain. Inference is based on Markov chain Monte Carlo, augmented with speciﬁc methods for generating efﬁcient proposals when the domain contains many objects. Results on several citation data sets show that the method outperforms current algorithms for citation matching. The declarative, relational nature of the model also means that our algorithm can determine object characteristics such as author names by combining multiple citations of multiple papers.
Fast Sparse Gaussian Process Methods: The Informative Vector Machine
Authors: Neil D. Lawrence, Matthias Seeger, Ralf Herbrich
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We present a framework for sparse Gaussian process (GP) methods which uses forward selection with criteria based on information- theoretic principles, previously suggested for active learning. Our goal is not only to learn d{sparse predictors (which can be evalu- ated in O(d) rather than O(n), d (cid:28) n, n the number of training points), but also to perform training under strong restrictions on time and memory requirements. The scaling of our method is at most O(n (cid:1) d2), and in large real-world classi(cid:12)cation experiments we show that it can match prediction performance of the popular support vector machine (SVM), yet can be signi(cid:12)cantly faster in training. In contrast to the SVM, our approximation produces esti- mates of predictive probabilities (‘error bars’), allows for Bayesian model selection and is less complex in implementation.
Recovering Articulated Model Topology from Observed Rigid Motion
Authors: Leonid Taycher, John Iii, Trevor Darrell
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Accurate representation of articulated motion is a challenging problem for machine perception. Several successful tracking algorithms have been developed that model human body as an articulated tree. We pro- pose a learning-based method for creating such articulated models from observations of multiple rigid motions. This paper is concerned with recovering topology of the articulated model, when the rigid motion of constituent segments is known. Our approach is based on ﬁnding the Maximum Likelihood tree shaped factorization of the joint probability density function (PDF) of rigid segment motions. The topology of graph- ical model formed from this factorization corresponds to topology of the underlying articulated body. We demonstrate the performance of our al- gorithm on both synthetic and real motion capture data.
Learning to Perceive Transparency from the Statistics of Natural Scenes
Authors: Anat Levin, Assaf Zomet, Yair Weiss
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Certain simple images are known to trigger a percept of trans- parency: the input image I is perceived as the sum of two images I(x; y) = I1(x; y) + I2(x; y). This percept is puzzling. First, why do we choose the \more complicated" description with two images rather than the \simpler" explanation I(x; y) = I1(x; y) + 0 ? Sec- ond, given the inﬂnite number of ways to express I as a sum of two images, how do we compute the \best" decomposition ? Here we suggest that transparency is the rational percept of a sys- tem that is adapted to the statistics of natural scenes. We present a probabilistic model of images based on the qualitative statistics of derivative ﬂlters and \corner detectors" in natural scenes and use this model to ﬂnd the most probable decomposition of a novel image. The optimization is performed using loopy belief propa- gation. We show that our model computes perceptually \correct" decompositions on synthetic images and discuss its application to real images.
Replay, Repair and Consolidation
Authors: Szabolcs Káli, Peter Dayan
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: A standard view of memory consolidation is that episodes are stored tem- porarily in the hippocampus, and are transferred to the neocortex through replay. Various recent experimental challenges to the idea of transfer, particularly for human memory, are forcing its re-evaluation. However, although there is independent neurophysiological evidence for replay, short of transfer, there are few theoretical ideas for what it might be doing. We suggest and demonstrate two important computational roles associated with neocortical indices.
Inferring a Semantic Representation of Text via Cross-Language Correlation Analysis
Authors: Alexei Vinokourov, Nello Cristianini, John Shawe-Taylor
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: The problem of learning a semantic representation of a text document from data is addressed, in the situation where a corpus of unlabeled paired documents is available, each pair being formed by a short En- glish document and its French translation. This representation can then be used for any retrieval, categorization or clustering task, both in a stan- dard and in a cross-lingual setting. By using kernel functions, in this case simple bag-of-words inner products, each part of the corpus is mapped to a high-dimensional space. The correlations between the two spaces are then learnt by using kernel Canonical Correlation Analysis. A set of directions is found in the ﬁrst and in the second space that are max- imally correlated. Since we assume the two representations are com- pletely independent apart from the semantic content, any correlation be- tween them should reﬂect some semantic similarity. Certain patterns of English words that relate to a speciﬁc meaning should correlate with cer- tain patterns of French words corresponding to the same meaning, across the corpus. Using the semantic representation obtained in this way we ﬁrst demonstrate that the correlations detected between the two versions of the corpus are signiﬁcantly higher than random, and hence that a rep- resentation based on such features does capture statistical patterns that should reﬂect semantic information. Then we use such representation both in cross-language and in single-language retrieval tasks, observing performance that is consistently and signiﬁcantly superior to LSI on the same data.
Cluster Kernels for Semi-Supervised Learning
Authors: Olivier Chapelle, Jason Weston, Bernhard Schölkopf
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We  propose  a  framework  to  incorporate  unlabeled  data in  kernel  classifier,  based on the idea that two points in the same cluster are  more likely  to have  the same label.  This is  achieved  by modifying  the eigenspectrum of the kernel matrix.  Experimental results assess  the validity of this  approach.
A Hierarchical Bayesian Markovian Model for Motifs in Biopolymer Sequences
Authors: Eric P. Xing, Michael I. Jordan, Richard M. Karp, Stuart Russell
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We propose a dynamic Bayesian model for motifs in biopolymer se- quences which captures rich biological prior knowledge and positional dependencies in motif structure in a principled way. Our model posits that the position-speciﬁc multinomial parameters for monomer distribu- tion are distributed as a latent Dirichlet-mixture random variable, and the position-speciﬁc Dirichlet component is determined by a hidden Markov process. Model parameters can be ﬁt on training motifs using a vari- ational EM algorithm within an empirical Bayesian framework. Varia- tional inference is also used for detecting hidden motifs. Our model im- proves over previous models that ignore biological priors and positional dependence. It has much higher sensitivity to motifs during detection and a notable ability to distinguish genuine motifs from false recurring patterns.
Speeding up the Parti-Game Algorithm
Authors: Maxim Likhachev, Sven Koenig
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: In this paper, we introduce an efﬁcient replanning algorithm for nonde- terministic domains, namely what we believe to be the ﬁrst incremental heuristic minimax search algorithm. We apply it to the dynamic dis- cretization of continuous domains, resulting in an efﬁcient implemen- tation of the parti-game reinforcement-learning algorithm for control in high-dimensional domains.
Monaural Speech Separation
Authors: Guoning Hu, Deliang Wang
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: that deals with 
Monaural speech separation has been studied in previous systems that  incorporate auditory scene analysis principles. A major problem for  these systems is their inability to deal with speech in the high- frequency range. Psychoacoustic evidence suggests that different  perceptual mechanisms are involved in handling resolved and  unresolved harmonics. Motivated by this, we propose a model for  monaural separation  low-frequency and high- frequency signals differently. For resolved harmonics, our model  generates segments based on temporal continuity and cross-channel  correlation, and groups them according to periodicity. For unresolved  harmonics, the model generates segments based on amplitude  modulation (AM) in addition to temporal continuity and groups them  according to AM repetition rates derived from sinusoidal modeling.  Underlying the separation process is a pitch contour obtained  according to psychoacoustic constraints. Our model is systematically  evaluated, and it yields substantially better performance than previous  systems, especially in the high-frequency range.
Multiplicative Updates for Nonnegative Quadratic Programming in Support Vector Machines
Authors: Fei Sha, Lawrence K. Saul, Daniel D. Lee
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We derive multiplicative updates for solving the nonnegative quadratic programming problem in support vector machines (SVMs). The updates have a simple closed form, and we prove that they converge monotoni- cally to the solution of the maximum margin hyperplane. The updates optimize the traditionally proposed objective function for SVMs. They do not involve any heuristics such as choosing a learning rate or deciding which variables to update at each iteration. They can be used to adjust all the quadratic programming variables in parallel with a guarantee of im- provement at each iteration. We analyze the asymptotic convergence of the updates and show that the coefﬁcients of non-support vectors decay geometrically to zero at a rate that depends on their margins. In practice, the updates converge very rapidly to good classiﬁers.
Rational Kernels
Authors: Corinna Cortes, Patrick Haffner, Mehryar Mohri
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We introduce a general family of kernels based on weighted transduc- ers or rational relations, rational kernels, that can be used for analysis of variable-length sequences or more generally weighted automata, in appli- cations such as computational biology or speech recognition. We show that rational kernels can be computed efﬁciently using a general algo- rithm of composition of weighted transducers and a general single-source shortest-distance algorithm. We also describe several general families of positive deﬁnite symmetric rational kernels. These general kernels can be combined with Support Vector Machines to form efﬁcient and power- ful techniques for spoken-dialog classiﬁcation: highly complex kernels become easy to design and implement and lead to substantial improve- ments in the classiﬁcation accuracy. We also show that the string kernels considered in applications to computational biology are all speciﬁc in- stances of rational kernels.
Linear Combinations of Optic Flow Vectors for Estimating Self-Motion - a Real-World Test of a Neural Model
Authors: Matthias O. Franz, Javaan S. Chahl
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: The tangential neurons in the ﬂy brain are sensitive to the typical optic ﬂow patterns generated during self-motion. In this study, we examine whether a simpliﬁed linear model of these neurons can be used to esti- mate self-motion from the optic ﬂow. We present a theory for the con- struction of an estimator consisting of a linear combination of optic ﬂow vectors that incorporates prior knowledge both about the distance distri- bution of the environment, and about the noise and self-motion statistics of the sensor. The estimator is tested on a gantry carrying an omnidirec- tional vision sensor. The experiments show that the proposed approach leads to accurate and robust estimates of rotation rates, whereas transla- tion estimates turn out to be less reliable.
Kernel Dependency Estimation
Authors: Jason Weston, Olivier Chapelle, Vladimir Vapnik, André Elisseeff, Bernhard Schölkopf
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We consider the learning problem of finding a dependency between  a  general  class  of objects  and  another,  possibly  different,  general  class of objects.  The objects can be for  example:  vectors,  images,  strings, trees or graphs.  Such a task is made possible by employing  similarity  measures  in  both  input  and  output  spaces  using  ker(cid:173) nel  functions,  thus  embedding  the  objects  into  vector  spaces.  We  experimentally  validate  our  approach  on  several  tasks:  mapping  strings to strings, pattern recognition, and reconstruction from par(cid:173) tial images.
Circuit Model of Short-Term Synaptic Dynamics
Authors: Shih-Chii Liu, Malte Boegershausen, Pascal Suter
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We describe a model of short-term synaptic depression that is derived from a silicon circuit implementation. The dynamics of this circuit model are similar to the dynamics of some present theoretical models of short- term depression except that the recovery dynamics of the variable de- scribing the depression is nonlinear and it also depends on the presynap- tic frequency. The equations describing the steady-state and transient re- sponses of this synaptic model ﬁt the experimental results obtained from a fabricated silicon network consisting of leaky integrate-and-ﬁre neu- rons and different types of synapses. We also show experimental data demonstrating the possible computational roles of depression. One pos- sible role of a depressing synapse is that the input can quickly bring the neuron up to threshold when the membrane potential is close to the rest- ing potential.
Coulomb Classifiers: Generalizing Support Vector Machines via an Analogy to Electrostatic Systems
Authors: Sepp Hochreiter, Michael Mozer, Klaus Obermayer
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We introduce a family of classiﬂers based on a physical analogy to an electrostatic system of charged conductors. The family, called Coulomb classiﬂers, includes the two best-known support-vector machines (SVMs), the ”{SVM and the C{SVM. In the electrostat- ics analogy, a training example corresponds to a charged conductor at a given location in space, the classiﬂcation function corresponds to the electrostatic potential function, and the training objective function corresponds to the Coulomb energy. The electrostatic framework provides not only a novel interpretation of existing algo- rithms and their interrelationships, but it suggests a variety of new methods for SVMs including kernels that bridge the gap between polynomial and radial-basis functions, objective functions that do not require positive-deﬂnite kernels, regularization techniques that allow for the construction of an optimal classiﬂer in Minkowski space. Based on the framework, we propose novel SVMs and per- form simulation studies to show that they are comparable or su- perior to standard SVMs. The experiments include classiﬂcation tasks on data which are represented in terms of their pairwise prox- imities, where a Coulomb Classiﬂer outperformed standard SVMs.
Robust Novelty Detection with Single-Class MPM
Authors: Laurent E. Ghaoui, Michael I. Jordan, Gert R. Lanckriet
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: the  "single-class  minimax  probabil(cid:173)
In  this  paper  we  consider  the  problem  of novelty  detection,  pre(cid:173) senting  an  algorithm that  aims  to find  a  minimal  region  in  input  space  containing  a  fraction  0:  of the  probability  mass  underlying  a  data  set.  This  algorithm- ity machine  (MPM)" - is  built  on a  distribution-free methodology  that  minimizes  the  worst-case  probability  of a  data  point  falling  outside of a convex set, given only the mean and covariance matrix  of the  distribution  and  making  no  further  distributional  assump(cid:173) tions.  We  present  a  robust  approach to  estimating  the  mean  and  covariance  matrix within  the  general  two-class  MPM setting,  and  show how this approach specializes to the single-class problem.  We  provide  empirical  results  comparing  the  single-class  MPM  to  the  single-class SVM  and a  two-class SVM method.
Feature Selection in Mixture-Based Clustering
Authors: Martin H. Law, Anil K. Jain, Mário Figueiredo
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: There exist many approaches to clustering, but the important issue of feature selection, i.e., selecting the data attributes that are relevant for clustering, is rarely addressed. Feature selection for clustering is difﬁcult due to the absence of class labels. We propose two approaches to feature selection in the context of Gaussian mixture-based clustering. In the ﬁrst one, instead of making hard selections, we estimate feature saliencies. An expectation-maximization (EM) algorithm is derived for this task. The second approach extends Koller and Sahami’s mutual-information- based feature relevance criterion to the unsupervised case. Feature selec- tion is then carried out by a backward search scheme. This scheme can be classiﬁed as a “wrapper”, since it wraps mixture estimation in an outer layer that performs feature selection. Experimental results on synthetic and real data show that both methods have promising performance.
Minimax Differential Dynamic Programming: An Application to Robust Biped Walking
Authors: Jun Morimoto, Christopher G. Atkeson
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We developed a robust control policy design method in high-dimensional state space by using differential dynamic programming with a minimax criterion. As an example, we applied our method to a simulated ﬁve link biped robot. The results show lower joint torques from the optimal con- trol policy compared to a hand-tuned PD servo controller. Results also show that the simulated biped robot can successfully walk with unknown disturbances that cause controllers generated by standard differential dy- namic programming and the hand-tuned PD servo to fail. Learning to compensate for modeling error and previously unknown disturbances in conjunction with robust control design is also demonstrated.
Theory-Based Causal Inference
Authors: Joshua B. Tenenbaum, Thomas L. Griffiths
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: People routinely make sophisticated causal inferences unconsciously, ef- fortlessly, and from very little data – often from just one or a few ob- servations. We argue that these inferences can be explained as Bayesian computations over a hypothesis space of causal graphical models, shaped by strong top-down prior knowledge in the form of intuitive theories. We present two case studies of our approach, including quantitative mod- els of human causal judgments and brief comparisons with traditional bottom-up models of inference.
FloatBoost Learning for Classification
Authors: Stan Z. Li, Zhenqiu Zhang, Heung-yeung Shum, Hongjiang Zhang
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: AdaBoost [3] minimizes an upper error bound which is an exponential function of the margin on the training set [14]. However, the ultimate goal in applications of pattern classiﬁcation is always minimum error rate. On the other hand, AdaBoost needs an effective procedure for learning weak classiﬁers, which by itself is difﬁcult especially for high dimensional data. In this paper, we present a novel procedure, called FloatBoost, for learning a better boosted classiﬁer. FloatBoost uses a backtrack mechanism after each iteration of AdaBoost to remove weak classiﬁers which cause higher error rates. The resulting ﬂoat-boosted classiﬁer consists of fewer weak classiﬁers yet achieves lower error rates than AdaBoost in both training and test. We also propose a statistical model for learning weak classiﬁers, based on a stagewise approximation of the posterior using an overcomplete set of scalar features. Experi- mental comparisons of FloatBoost and AdaBoost are provided through a difﬁcult classiﬁcation problem, face detection, where the goal is to learn from training examples a highly nonlinear classiﬁer to differentiate be- tween face and nonface patterns in a high dimensional space. The results clearly demonstrate the promises made by FloatBoost over AdaBoost.
Adaptive Scaling for Feature Selection in SVMs
Authors: Yves Grandvalet, Stéphane Canu
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: This paper introduces an algorithm for the automatic relevance determi- nation of input variables in kernelized Support Vector Machines. Rele- vance is measured by scale factors deﬁning the input space metric, and feature selection is performed by assigning zero weights to irrelevant variables. The metric is automatically tuned by the minimization of the standard SVM empirical risk, where scale factors are added to the usual set of parameters deﬁning the classiﬁer. Feature selection is achieved by constraints encouraging the sparsity of scale factors. The resulting algorithm compares favorably to state-of-the-art feature selection proce- dures and demonstrates its effectiveness on a demanding facial expres- sion recognition problem.
Adaptive Classification by Variational Kalman Filtering
Authors: Peter Sykacek, Stephen J. Roberts
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We propose in this paper a probabilistic approach for adaptive inference of generalized nonlinear classiﬁcation that combines the computational advantage of a parametric solution with the ﬂexibility of sequential sam- pling techniques. We regard the parameters of the classiﬁer as latent states in a ﬁrst order Markov process and propose an algorithm which can be regarded as variational generalization of standard Kalman ﬁlter- ing. The variational Kalman ﬁlter is based on two novel lower bounds that enable us to use a non-degenerate distribution over the adaptation rate. An extensive empirical evaluation demonstrates that the proposed method is capable of infering competitive classiﬁers both in stationary and non-stationary environments. Although we focus on classiﬁcation, the algorithm is easily extended to other generalized nonlinear models.
A Statistical Mechanics Approach to Approximate Analytical Bootstrap Averages
Authors: Dörthe Malzahn, Manfred Opper
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We apply the replica method of Statistical Physics combined with a vari- ational method to the approximate analytical computation of bootstrap averages for estimating the generalization error. We demonstrate our ap- proach on regression with Gaussian processes and compare our results with averages obtained by Monte-Carlo sampling.
Developing Topography and Ocular Dominance Using Two aVLSI Vision Sensors and a Neurotrophic Model of Plasticity
Authors: Terry Elliott, Jörg Kramer
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: A neurotrophic model for the co-development of topography and ocular dominance columns in the primary visual cortex has recently been pro- posed. In the present work, we test this model by driving it with the output of a pair of neuronal vision sensors stimulated by disparate mov- ing patterns. We show that the temporal correlations in the spike trains generated by the two sensors elicit the development of reﬁned topogra- phy and ocular dominance columns, even in the presence of signiﬁcant amounts of spontaneous activity and ﬁxed-pattern noise in the sensors.
Gaussian Process Priors with Uncertain Inputs Application to Multiple-Step Ahead Time Series Forecasting
Authors: Agathe Girard, Carl Edward Rasmussen, Joaquin Quiñonero Candela, Roderick Murray-Smith
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We consider the problem of multi-step ahead prediction in time series analysis using the non-parametric Gaussian process model.  -step ahead forecasting of a discrete-time non-linear dynamic system can be per- formed by doing repeated one-step ahead predictions. For a state-space at time model of the form is based on the point estimates of the previous outputs. In this pa-   per, we show how, using an analytical Gaussian approximation, we can formally incorporate the uncertainty about intermediate regressor values, thus updating the uncertainty on the current prediction.
Maximum Likelihood and the Information Bottleneck
Authors: Noam Slonim, Yair Weiss
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract:      
that deﬁnes partitions over the values of
The information bottleneck (IB) method is an information-theoretic formulation , this method constructs for clustering problems. Given a joint distribution a new variable that are informative . Maximum likelihood (ML) of mixture models is a standard statistical about approach to clustering problems. In this paper, we ask: how are the two methods related ? We deﬁne a simple mapping between the IB problem and the ML prob- lem for the multinomial mixture model. We show that under this mapping the problems are strongly related. In fact, for uniform input distribution over or for large sample size, the problems are mathematically equivalent. Speciﬁcally, in these cases, every ﬁxed point of the IB-functional deﬁnes a ﬁxed point of the (log) likelihood and vice versa. Moreover, the values of the functionals at the ﬁxed points are equal under simple transformations. As a result, in these cases, every algorithm that solves one of the problems, induces a solution for the other.
The Stability of Kernel Principal Components Analysis and its Relation to the Process Eigenspectrum
Authors: Christopher Williams, John S. Shawe-taylor
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: In  this paper we  analyze the relationships between the eigenvalues  of the m  x m  Gram matrix K  for  a kernel k(·, .)  corresponding to a  sample  Xl, ... ,Xm  drawn from  a  density p(x)  and the eigenvalues  of the corresponding continuous eigenproblem.  We  bound the dif(cid:173) ferences between the two spectra and provide a performance bound  on kernel peA.
Adaptive Quantization and Density Estimation in Silicon
Authors: David Hsu, Seth Bridges, Miguel Figueroa, Chris Diorio
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We present the bump mixture model, a statistical model for analog  data where the probabilistic semantics, inference, and learning  rules derive from low-level transistor behavior. The bump mixture  model relies on translinear circuits to perform probabilistic infer- ence, and floating-gate devices to perform adaptation. This system  is low power, asynchronous, and fully parallel, and supports vari- ous on-chip learning algorithms. In addition, the mixture model can  perform several tasks such as probability estimation, vector quanti- zation, classification, and clustering. We tested a fabricated system  on clustering, quantization, and classification of handwritten digits  and show performance comparable to the E-M algorithm on mix- tures of Gaussians.
Improving Transfer Rates in Brain Computer Interfacing: A Case Study
Authors: Peter Meinicke, Matthias Kaper, Florian Hoppe, Manfred Heumann, Helge Ritter
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: In this paper we present results of a study on brain computer interfacing. We adopted an approach of Farwell & Donchin [4], which we tried to improve in several aspects. The main objective was to improve the trans- fer rates based on ofﬂine analysis of EEG-data but within a more realistic setup closer to an online realization than in the original studies. The ob- jective was achieved along two different tracks: on the one hand we used state-of-the-art machine learning techniques for signal classiﬁcation and on the other hand we augmented the data space by using more electrodes for the interface. For the classiﬁcation task we utilized SVMs and, as mo- tivated by recent ﬁndings on the learning of discriminative densities, we accumulated the values of the classiﬁcation function in order to combine several classiﬁcations, which ﬁnally lead to signiﬁcantly improved rates as compared with techniques applied in the original work. In combina- tion with the data space augmentation, we achieved competitive transfer rates at an average of 50.5 bits/min and with a maximum of 84.7 bits/min.
Discriminative Learning for Label Sequences via Boosting
Authors: Yasemin Altun, Thomas Hofmann, Mark Johnson
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: This  paper  investigates  a  boosting  approach  to  discriminative  learning of label sequences based on a sequence rank loss function.  The proposed method combines many of the  advantages of boost(cid:173) ing schemes  with  the efficiency  of dynamic programming methods  and is  attractive both, conceptually and computationally.  In  addi(cid:173) tion, we also discuss alternative approaches based on the Hamming  loss for  label sequences.  The sequence boosting algorithm offers an  interesting alternative to  methods  based  on  HMMs  and  the  more  recently proposed  Conditional Random Fields.  Applications  areas  for the presented technique range from natural language processing  and  information extraction to  computational biology.  We  include  experiments  on  named  entity  recognition  and  part-of-speech  tag(cid:173) ging  which  demonstrate  the  validity  and  competitiveness  of  our  approach.
Reinforcement Learning to Play an Optimal Nash Equilibrium in Team Markov Games
Authors: Xiaofeng Wang, Tuomas Sandholm
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Multiagent learning is a key problem in AI. In the presence of multi- ple Nash equilibria, even agents with non-conﬂicting interests may not be able to learn an optimal coordination policy. The problem is exac- cerbated if the agents do not know the game and independently receive noisy payoffs. So, multiagent reinforfcement learning involves two inter- related problems: identifying the game and learning to play. In this paper, we present optimal adaptive learning, the ﬁrst algorithm that converges to an optimal Nash equilibrium with probability 1 in any team Markov game. We provide a convergence proof, and show that the algorithm’s parameters are easy to set to meet the convergence conditions.
Using Manifold Stucture for Partially Labeled Classification
Authors: Mikhail Belkin, Partha Niyogi
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We consider the general problem of utilizing both labeled and un(cid:173) labeled data to improve classification accuracy. Under t he assump(cid:173) tion that the data lie on a submanifold in a high dimensional space,  we develop an algorithmic framework to classify a partially labeled  data set in a principled manner . The central idea of our approach is  that classification functions are naturally defined only on t he sub(cid:173) manifold in question rather than the total ambient space. Using the  Laplace Beltrami operator one produces a basis for a Hilbert space  of square integrable functions on the submanifold. To recover such  a basis , only unlab eled examples are required. Once a basis is ob(cid:173) tained , training can be performed using the labeled data set. Our  algorithm models the manifold using the adjacency graph for the  data and approximates the Laplace Beltrami operator by the graph  Laplacian. Practical applications to image and text classification  are considered.
Recovering Intrinsic Images from a Single Image
Authors: Marshall F. Tappen, William T. Freeman, Edward H. Adelson
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We present an algorithm that uses multiple cues to recover shading and reﬂectance intrinsic images from a single image. Using both color in- formation and a classiﬁer trained to recognize gray-scale patterns, each image derivative is classiﬁed as being caused by shading or a change in the surface’s reﬂectance. Generalized Belief Propagation is then used to propagate information from areas where the correct classiﬁcation is clear to areas where it is ambiguous. We also show results on real images.
A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics
Authors: Eric Allender, Sanjeev Arora, Michael Kearns, Cristopher Moore, Alexander Russell
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We establish a new hardness result that shows that the difﬁculty of plan- ning in factored Markov decision processes is representational rather than just computational. More precisely, we give a ﬁxed family of fac- tored MDPs with linear rewards whose optimal policies and value func- tions simply cannot be represented succinctly in any standard parametric form. Previous hardness results indicated that computing good policies from the MDP parameters was difﬁcult, but left open the possibility of succinct function approximation for any ﬁxed factored MDP. Our result applies even to policies which yield a polynomially poor approximation to the optimal value, and highlights interesting connectionswith the com- plexity class of Arthur-Merlin games.
A Prototype for Automatic Recognition of Spontaneous Facial Actions
Authors: M.S. Bartlett, G.C. Littlewort, T.J. Sejnowski, J.R. Movellan
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We present ongoing work on a project for automatic recognition of spon- taneous facial actions. Spontaneous facial expressions differ substan- tially from posed expressions, similar to how continuous, spontaneous speech differs from isolated words produced on command. Previous methods for automatic facial expression recognition assumed images were collected in controlled environments in which the subjects delib- erately faced the camera. Since people often nod or turn their heads, automatic recognition of spontaneous facial behavior requires methods for handling out-of-image-plane head rotations. Here we explore an ap- proach based on 3-D warping of images into canonical views. We eval- uated the performance of the approach as a front-end for a spontaneous expression recognition system using support vector machines and hidden Markov models. This system employed general purpose learning mech- anisms that can be applied to recognition of any facial movement. The system was tested for recognition of a set of facial actions deﬁned by the Facial Action Coding System (FACS). We showed that 3D tracking and warping followed by machine learning techniques directly applied to the warped images, is a viable and promising technology for automatic facial expression recognition. One exciting aspect of the approach pre- sented here is that information about movement dynamics emerged out of ﬁlters which were derived from the statistics of images.
Exact MAP Estimates by (Hyper)tree Agreement
Authors: Martin J. Wainwright, Tommi S. Jaakkola, Alan S. Willsky
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We describe a method for computing provably exact maximum a poste- riori (MAP) estimates for a subclass of problems on graphs with cycles. The basic idea is to represent the original problem on the graph with cy- cles as a convex combination of tree-structured problems. A convexity argument then guarantees that the optimal value of the original problem (i.e., the log probability of the MAP assignment) is upper bounded by the combined optimal values of the tree problems. We prove that this upper bound is met with equality if and only if the tree problems share an opti- mal conﬁguration in common. An important implication is that any such shared conﬁguration must also be the MAP conﬁguration for the original problem. Next we develop a tree-reweighted max-product algorithm for attempting to ﬁnd convex combinations of tree-structured problems that share a common optimum. We give necessary and sufﬁcient conditions for a ﬁxed point to yield the exact MAP estimate. An attractive feature of our analysis is that it generalizes naturally to convex combinations of hypertree-structured distributions.