mtybilly/Instruct2DS huggingface dataset:
A Kullback-Leibler Divergence Based Kernel for SVM Classification in Multimedia Applications
Authors: Pedro J. Moreno, Purdy P. Ho, Nuno Vasconcelos
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Over the last years signiﬁcant efforts have been made to develop kernels that can be applied to sequence data such as DNA, text, speech, video and images. The Fisher Kernel and similar variants have been suggested as good ways to combine an underlying generative model in the feature space and discriminant classiﬁers such as SVM’s. In this paper we sug- gest an alternative procedure to the Fisher kernel for systematically ﬁnd- ing kernel functions that naturally handle variable length sequence data in multimedia domains. In particular for domains such as speech and images we explore the use of kernel functions that take full advantage of well known probabilistic models such as Gaussian Mixtures and sin- gle full covariance Gaussian models. We derive a kernel distance based on the Kullback-Leibler (KL) divergence between generative models. In effect our approach combines the best of both generative and discrim- inative methods and replaces the standard SVM kernels. We perform experiments on speaker identiﬁcation/veriﬁcation and image classiﬁca- tion tasks and show that these new kernels have the best performance in speaker veriﬁcation and mostly outperform the Fisher kernel based SVM’s and the generative classiﬁers in speaker identiﬁcation and image classiﬁcation.
A Model for Learning the Semantics of Pictures
Authors: Victor Lavrenko, R. Manmatha, Jiwoon Jeon
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We propose an approach to learning the semantics of images which al- lows us to automatically annotate an image with keywords and to retrieve images based on text queries. We do this using a formalism that models the generation of annotated images. We assume that every image is di- vided into regions, each described by a continuous-valued feature vector. Given a training set of images with annotations, we compute a joint prob- abilistic model of image features and words which allow us to predict the probability of generating a word given the image regions. This may be used to automatically annotate and retrieve images given a word as a query. Experiments show that our model signiﬁcantly outperforms the best of the previously reported results on the tasks of automatic image annotation and retrieval.
Margin Maximizing Loss Functions
Authors: Saharon Rosset, Ji Zhu, Trevor J. Hastie
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Margin maximizing properties play an important role in the analysis of classi£- cation models, such as boosting and support vector machines. Margin maximiza- tion is theoretically interesting because it facilitates generalization error analysis, and practically interesting because it presents a clear geometric interpretation of the models being built. We formulate and prove a suf£cient condition for the solutions of regularized loss functions to converge to margin maximizing separa- tors, as the regularization vanishes. This condition covers the hinge loss of SVM, the exponential loss of AdaBoost and logistic regression loss. We also generalize it to multi-class classi£cation problems, and present margin maximizing multi- class versions of logistic regression and support vector machines.
Inferring State Sequences for Non-linear Systems with Embedded Hidden Markov Models
Authors: Radford M. Neal, Matthew J. Beal, Sam T. Roweis
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We describe a Markov chain method for sampling from the distribution of the hidden state sequence in a non-linear dynamical system, given a sequence of observations. This method updates all states in the sequence simultaneously using an embedded Hidden Markov Model (HMM). An update begins with the creation of “pools” of candidate states at each time. We then deﬁne an embedded HMM whose states are indexes within these pools. Using a forward-backward dynamic programming algo- rithm, we can efﬁciently choose a state sequence with the appropriate probabilities from the exponentially large number of state sequences that pass through states in these pools. We illustrate the method in a simple one-dimensional example, and in an example showing how an embed- ded HMM can be used to in effect discretize the state space without any discretization error. We also compare the embedded HMM to a particle smoother on a more substantial problem of inferring human motion from 2D traces of markers.
Self-calibrating Probability Forecasting
Authors: Vladimir Vovk, Glenn Shafer, Ilia Nouretdinov
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: In the problem of probability forecasting the learner’s goal is to output, given a training set and a new object, a suitable probability measure on the possible values of the new object’s label. An on-line algorithm for probability forecasting is said to be well-calibrated if the probabilities it outputs agree with the observed frequencies. We give a natural non- asymptotic formalization of the notion of well-calibratedness, which we then study under the assumption of randomness (the object/label pairs are independent and identically distributed). It turns out that, although no probability forecasting algorithm is automatically well-calibrated in our sense, there exists a wide class of algorithms for “multiprobability forecasting” (such algorithms are allowed to output a set, ideally very narrow, of probability measures) which satisfy this property; we call the algorithms in this class “Venn probability machines”. Our experimental results demonstrate that a 1-Nearest Neighbor Venn probability machine performs reasonably well on a standard benchmark data set, and one of our theoretical results asserts that a simple Venn probability machine asymptotically approaches the true conditional probabilities regardless, and without knowledge, of the true probability measure generating the examples.
Synchrony Detection by Analogue VLSI Neurons with Bimodal STDP Synapses
Authors: Adria Bofill-i-petit, Alan F. Murray
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We present test results from spike-timing correlation learning ex- periments carried out with silicon neurons with STDP (Spike Tim- ing Dependent Plasticity) synapses. The weight change scheme of the STDP synapses can be set to either weight-independent or weight-dependent mode. We present results that characterise the learning window implemented for both modes of operation. When presented with spike trains with di(cid:11)erent types of synchronisation the neurons develop bimodal weight distributions. We also show that a 2-layered network of silicon spiking neurons with STDP synapses can perform hierarchical synchrony detection.
Semi-supervised Protein Classification Using Cluster Kernels
Authors: Jason Weston, Dengyong Zhou, André Elisseeff, William S. Noble, Christina S. Leslie
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: A key issue in supervised protein classiﬁcation is the representation of in- put sequences of amino acids. Recent work using string kernels for pro- tein data has achieved state-of-the-art classiﬁcation performance. How- ever, such representations are based only on labeled data — examples with known 3D structures, organized into structural classes — while in practice, unlabeled data is far more plentiful. In this work, we de- velop simple and scalable cluster kernel techniques for incorporating un- labeled data into the representation of protein sequences. We show that our methods greatly improve the classiﬁcation performance of string ker- nels and outperform standard approaches for using unlabeled data, such as adding close homologs of the positive examples to the training data. We achieve equal or superior performance to previously presented cluster kernel methods while achieving far greater computational efﬁciency.
When Does Non-Negative Matrix Factorization Give a Correct Decomposition into Parts?
Authors: David Donoho, Victoria Stodden
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We interpret non-negative matrix factorization geometrically, as the problem of ﬁnding a simplicial cone which contains a cloud of data points and which is contained in the positive orthant. We show that under certain conditions, basically requiring that some of the data are spread across the faces of the positive orthant, there is a unique such simpli- cial cone. We give examples of synthetic image articulation databases which obey these conditions; these require separated support and facto- rial sampling. For such databases there is a generative model in terms of ‘parts’ and NMF correctly identiﬁes the ‘parts’. We show that our theoretical results are predictive of the performance of published NMF code, by running the published algorithms on one of our synthetic image articulation databases.
Pairwise Clustering and Graphical Models
Authors: Noam Shental, Assaf Zomet, Tomer Hertz, Yair Weiss
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Signi(cid:2)cant progress in clustering has been achieved by algorithms that are based on pairwise af(cid:2)nities between the datapoints. In particular, spectral clustering methods have the advantage of being able to divide arbitrarily shaped clusters and are based on ef(cid:2)cient eigenvector calcu- lations. However, spectral methods lack a straightforward probabilistic interpretation which makes it dif(cid:2)cult to automatically set parameters us- ing training data. In this paper we use the previously proposed typical cut framework for pairwise clustering. We show an equivalence between calculating the typical cut and inference in an undirected graphical model. We show that for clustering problems with hundreds of datapoints exact inference may still be possible. For more complicated datasets, we show that loopy be- lief propagation (BP) and generalized belief propagation (GBP) can give excellent results on challenging clustering problems. We also use graph- ical models to derive a learning algorithm for af(cid:2)nity matrices based on labeled data.
Link Prediction in Relational Data
Authors: Ben Taskar, Ming-fai Wong, Pieter Abbeel, Daphne Koller
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Many real-world domains are relational in nature, consisting of a set of objects related to each other in complex ways. This paper focuses on predicting the existence and the type of links between entities in such domains. We apply the relational Markov network framework of Taskar et al. to deﬁne a joint probabilis- tic model over the entire link graph — entity attributes and links. The application of the RMN algorithm to this task requires the deﬁnition of probabilistic patterns over subgraph structures. We apply this method to two new relational datasets, one involving university webpages, and the other a social network. We show that the collective classiﬁcation approach of RMNs, and the introduction of subgraph patterns over link labels, provide signiﬁcant improvements in accuracy over ﬂat classiﬁcation, which attempts to predict each link in isolation.
Human and Ideal Observers for Detecting Image Curves
Authors: Fang Fang, Daniel Kersten, Paul R. Schrater, Alan L. Yuille
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: This paper compares the ability of human observers to detect target im- age curves with that of an ideal observer. The target curves are sam- pled from a generative model which speciﬁes (probabilistically) the ge- ometry and local intensity properties of the curve. The ideal observer performs Bayesian inference on the generative model using MAP esti- mation. Varying the probability model for the curve geometry enables us investigate whether human performance is best for target curves that obey speciﬁc shape statistics, in particular those observed on natural shapes. Experiments are performed with data on both rectangular and hexagonal lattices. Our results show that human observers’ performance approaches that of the ideal observer and are, in general, closest to the ideal for con- ditions where the target curve tends to be straight or similar to natural statistics on curves. This suggests a bias of human observers towards straight curves and natural statistics.
Linear Program Approximations for Factored Continuous-State Markov Decision Processes
Authors: Milos Hauskrecht, Branislav Kveton
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Approximate linear programming (ALP) has emerged recently as one of the most promising methods for solving complex factored MDPs with (cid:2)nite state spaces. In this work we show that ALP solutions are not limited only to MDPs with (cid:2)nite state spaces, but that they can also be applied successfully to factored continuous-state MDPs (CMDPs). We show how one can build an ALP-based approximation for such a model and contrast it to existing solution methods. We argue that this approach offers a robust alternative for solving high dimensional continuous-state space problems. The point is supported by experiments on three CMDP problems with 24-25 continuous state factors.
Perception of the Structure of the Physical World Using Unknown Multimodal Sensors and Effectors
Authors: D. Philipona, J.k. O'regan, J.-p. Nadal, Olivier Coenen
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Is there a way for an algorithm linked to an unknown body to infer by itself information about this body and the world it is in? Taking the case of space for example, is there a way for this algorithm to realize that its body is in a three dimensional world? Is it possible for this algorithm to discover how to move in a straight line? And more basically: do these questions make any sense at all given that the algorithm only has access to the very high-dimensional data consisting of its sensory inputs and motor outputs? We demonstrate in this article how these questions can be given a positive answer. We show that it is possible to make an algorithm that, by ana- lyzing the law that links its motor outputs to its sensory inputs, discovers information about the structure of the world regardless of the devices constituting the body it is linked to. We present results from simulations demonstrating a way to issue motor orders resulting in “fundamental” movements of the body as regards the structure of the physical world.
Log-Linear Models for Label Ranking
Authors: Ofer Dekel, Yoram Singer, Christopher D. Manning
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Label ranking is the task of inferring a total order over a predeﬁned set of labels for each given instance. We present a general framework for batch learning of label ranking functions from supervised data. We assume that each instance in the training data is associated with a list of preferences over the label-set, however we do not assume that this list is either com- plete or consistent. This enables us to accommodate a variety of ranking problems. In contrast to the general form of the supervision, our goal is to learn a ranking function that induces a total order over the entire set of labels. Special cases of our setting are multilabel categorization and hierarchical classiﬁcation. We present a general boosting-based learning algorithm for the label ranking problem and prove a lower bound on the progress of each boosting iteration. The applicability of our approach is demonstrated with a set of experiments on a large-scale text corpus.
Learning a Rare Event Detection Cascade by Direct Feature Selection
Authors: Jianxin Wu, James M. Rehg, Matthew D. Mullin
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Face detection is a canonical example of a rare event detection prob- lem, in which target patterns occur with much lower frequency than non- targets. Out of millions of face-sized windows in an input image, for ex- ample, only a few will typically contain a face. Viola and Jones recently proposed a cascade architecture for face detection which successfully ad- dresses the rare event nature of the task. A central part of their method is a feature selection algorithm based on AdaBoost. We present a novel cascade learning algorithm based on forward feature selection which is two orders of magnitude faster than the Viola-Jones approach and yields classiﬁers of equivalent quality. This faster method could be used for more demanding classiﬁcation tasks, such as on-line learning.
Non-linear CCA and PCA by Alignment of Local Models
Authors: Jakob J. Verbeek, Sam T. Roweis, Nikos Vlassis
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We propose a non-linear Canonical Correlation Analysis (CCA) method which works by coordinating or aligning mixtures of linear models. In the same way that CCA extends the idea of PCA, our work extends re- cent methods for non-linear dimensionality reduction to the case where multiple embeddings of the same underlying low dimensional coordi- nates are observed, each lying on a different high dimensional manifold. We also show that a special case of our method, when applied to only a single manifold, reduces to the Laplacian Eigenmaps algorithm. As with previous alignment schemes, once the mixture models have been estimated, all of the parameters of our model can be estimated in closed form without local optima in the learning. Experimental results illustrate the viability of the approach as a non-linear extension of CCA.
Unsupervised Context Sensitive Language Acquisition from a Large Corpus
Authors: Zach Solan, David Horn, Eytan Ruppin, Shimon Edelman
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We describe a pattern acquisition algorithm that learns, in an unsuper- vised fashion, a streamlined representation of linguistic structures from a plain natural-language corpus. This paper addresses the issues of learn- ing structured knowledge from a large-scale natural language data set, and of generalization to unseen text. The implemented algorithm repre- sents sentences as paths on a graph whose vertices are words (or parts of words). Signiﬁcant patterns, determined by recursive context-sensitive statistical inference, form new vertices. Linguistic constructions are rep- resented by trees composed of signiﬁcant patterns and their associated equivalence classes. An input module allows the algorithm to be sub- jected to a standard test of English as a Second Language (ESL) proﬁ- ciency. The results are encouraging: the model attains a level of per- formance considered to be “intermediate” for 9th-grade students, de- spite having been trained on a corpus (CHILDES) containing transcribed speech of parents directed to small children.
Bias-Corrected Bootstrap and Model Uncertainty
Authors: Harald Steck, Tommi S. Jaakkola
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The bootstrap has become a popular method for exploring model (structure) uncertainty. Our experiments with artiﬁcial and real- world data demonstrate that the graphs learned from bootstrap samples can be severely biased towards too complex graphical mod- els. Accounting for this bias is hence essential, e.g., when explor- ing model uncertainty. We ﬁnd that this bias is intimately tied to (well-known) spurious dependences induced by the bootstrap. The leading-order bias-correction equals one half of Akaike’s penalty for model complexity. We demonstrate the eﬀect of this simple bias-correction in our experiments. We also relate this bias to the bias of the plug-in estimator for entropy, as well as to the diﬀer- ence between the expected test and training errors of a graphical model, which asymptotically equals Akaike’s penalty (rather than one half).
Nonlinear Processing in LGN Neurons
Authors: Vincent Bonin, Valerio Mante, Matteo Carandini
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: According  to  a  widely  held  view,  neurons  in  lateral  geniculate  nucleus (LGN) operate on visual stimuli in a linear fashion. There  is  ample  evidence,  however,  that  LGN  responses  are  not  entirely  linear.  To  account  for  nonlinearities  we  propose  a  model  that  synthesizes  more  than  30  years  of  research  in  the  field.  Model  neurons  have  a  linear  receptive  field,  and  a  nonlinear,  divisive  suppressive field. The suppressive field computes local root-mean- square  contrast.  To  test  this  model  we  recorded  responses  from  LGN of anesthetized paralyzed cats. We estimate model parameters  from  a  basic  set  of  measurements  and  show  that  the  model  can  accurately  predict  responses  to  novel  stimuli.  The  model  might  serve  as  the  new  standard  model  of  LGN  responses.  It  specifies  how  visual  processing  in  LGN  involves  both  linear  filtering  and  divisive gain control.
Ranking on Data Manifolds
Authors: Dengyong Zhou, Jason Weston, Arthur Gretton, Olivier Bousquet, Bernhard Schölkopf
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The Google search engine has enjoyed huge success with its web page ranking algorithm, which exploits global, rather than local, hyperlink structure of the web using random walks. Here we propose a simple universal ranking algorithm for data lying in the Euclidean space, such as text or image data. The core idea of our method is to rank the data with respect to the intrinsic manifold structure collectively revealed by a great amount of data. Encouraging experimental results from synthetic, image, and text data illustrate the validity of our method.
Approximate Analytical Bootstrap Averages for Support Vector Classifiers
Authors: Dörthe Malzahn, Manfred Opper
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We compute approximate analytical bootstrap averages for support vec- tor classiﬁcation using a combination of the replica method of statistical physics and the TAP approach for approximate inference. We test our method on a few datasets and compare it with exact averages obtained by extensive Monte-Carlo sampling.
A Neuromorphic Multi-chip Model of a Disparity Selective Complex Cell
Authors: Bertram E. Shi, Eric K. Tsang
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The relative depth of objects causes small shifts in the left and right ret- inal positions of these objects, called binocular disparity. Here, we describe a neuromorphic implementation of a disparity selective com- plex cell using the binocular energy model, which has been proposed to model the response of disparity selective cells in the visual cortex. Our system consists of two silicon chips containing spiking neurons with monocular Gabor-type spatial receptive fields (RF) and circuits that combine the spike outputs to compute a disparity selective complex cell response. The disparity selectivity of the cell can be adjusted by both position and phase shifts between the monocular RF profiles, which are both used in biology. Our neuromorphic system performs better with phase encoding, because the relative responses of neurons tuned to dif- ferent disparities by phase shifts are better matched than the responses of neurons tuned by position shifts.
Robustness in Markov Decision Problems with Uncertain Transition Matrices
Authors: Arnab Nilim, Laurent El Ghaoui
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Optimal solutions to Markov Decision Problems (MDPs) are very sen- sitive with respect to the state transition probabilities. In many practi- cal problems, the estimation of those probabilities is far from accurate. Hence, estimation errors are limiting factors in applying MDPs to real- world problems. We propose an algorithm for solving ﬁnite-state and ﬁnite-action MDPs, where the solution is guaranteed to be robust with respect to estimation errors on the state transition probabilities. Our al- gorithm involves a statistically accurate yet numerically efﬁcient repre- sentation of uncertainty, via Kullback-Leibler divergence bounds. The worst-case complexity of the robust algorithm is the same as the origi- nal Bellman recursion. Hence, robustness can be added at practically no extra computing cost.
Parameterized Novelty Detectors for Environmental Sensor Monitoring
Authors: Cynthia Archer, Todd K. Leen, António M. Baptista
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: As part of an environmental observation and forecasting system, sensors deployed in the Columbia RIver Estuary (CORIE) gather information on physical dynamics and changes in estuary habi- tat. Of these, salinity sensors are particularly susceptible to bio- fouling, which gradually degrades sensor response and corrupts crit- ical data. Automatic fault detectors have the capability to identify bio-fouling early and minimize data loss. Complicating the devel- opment of discriminatory classi(cid:12)ers is the scarcity of bio-fouling onset examples and the variability of the bio-fouling signature. To solve these problems, we take a novelty detection approach that incorporates a parameterized bio-fouling model. These detectors identify the occurrence of bio-fouling, and its onset time as reliably as human experts. Real-time detectors installed during the sum- mer of 2001 produced no false alarms, yet detected all episodes of sensor degradation before the (cid:12)eld sta(cid:11) scheduled these sensors for cleaning. From this initial deployment through February 2003, our bio-fouling detectors have essentially doubled the amount of useful data coming from the CORIE sensors.
Nonstationary Covariance Functions for Gaussian Process Regression
Authors: Christopher J. Paciorek, Mark J. Schervish
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We introduce a class of nonstationary covariance functions for Gaussian process (GP) regression. Nonstationary covariance functions allow the model to adapt to functions whose smoothness varies with the inputs. The class includes a nonstationary version of the Matérn stationary co- variance, in which the differentiability of the regression function is con- trolled by a parameter, freeing one from ﬁxing the differentiability in advance. In experiments, the nonstationary GP regression model per- forms well when the input space is two or three dimensions, outperform- ing a neural network model and Bayesian free-knot spline models, and competitive with a Bayesian neural network, but is outperformed in one dimension by a state-of-the-art Bayesian free-knot spline model. The model readily generalizes to non-Gaussian data. Use of computational methods for speeding GP ﬁtting may allow for implementation of the method on larger datasets.
Algorithms for Interdependent Security Games
Authors: Michael Kearns, Luis E. Ortiz
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: nspired by events ranging from 9/11 to the collapse of the accounting ﬁrm Arthur Ander-
sen, economists Kunreuther and Heal [5] recently introduced an interesting game-theoretic
model for problems of interdependent security (IDS), in which a large number of players
must make individual investment decisions related to security — whether physical, ﬁnan-
cial, medical, or some other type — but in which the ultimate safety of each participant
may depend in a complex way on the actions of the entire population. A simple example is
the choice of whether to install a ﬁre sprinkler system in an individual condominium in a
large building. While such a system might greatly reduce the chances of the owner’s prop-
erty being destroyed by a ﬁre originating within their own unit, it might do little or nothing
to reduce the chances of damage caused by ﬁres originating in other units (since sprinklers
can usually only douse small ﬁres early). If “enough” other unit owners have not made the
investment in sprinklers, it may be not cost-effective for any individual to do so.
How to Combine Expert (and Novice) Advice when Actions Impact the Environment?
Authors: Daniela Pucci de Farias, Nimrod Megiddo
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The so-called “experts algorithms” constitute a methodology for choos- ing actions repeatedly, when the rewards depend both on the choice of action and on the unknown current state of the environment. An experts algorithm has access to a set of strategies (“experts”), each of which may recommend which action to choose. The algorithm learns how to com- bine the recommendations of individual experts so that, in the long run, for any ﬁxed sequence of states of the environment, it does as well as the best expert would have done relative to the same sequence. This method- ology may not be suitable for situations where the evolution of states of the environment depends on past chosen actions, as is usually the case, for example, in a repeated non-zero-sum game. A new experts algorithm is presented and analyzed in the context of re- peated games. It is shown that asymptotically, under certain conditions, it performs as well as the best available expert. This algorithm is quite different from previously proposed experts algorithms. It represents a shift from the paradigms of regret minimization and myopic optimiza- tion to consideration of the long-term effect of a player’s actions on the opponent’s actions or the environment. The importance of this shift is demonstrated by the fact that this algorithm is capable of inducing co- operation in the repeated Prisoner’s Dilemma game, whereas previous experts algorithms converge to the suboptimal non-cooperative play.
Reasoning about Time and Knowledge in Neural Symbolic Learning Systems
Authors: Artur Garcez, Luis C. Lamb
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We  show  that  temporal logic  and  combinations of temporal logics  and modal logics of knowledge  can be effectively represented in ar(cid:173) tificial  neural  networks.  We  present  a  Translation  Algorithm from  temporal  rules  to  neural  networks,  and  show  that  the  networks  compute  a  fixed-point  semantics  of the  rules.  We  also  apply  the  translation to the muddy children puzzle, which has been used as a  testbed for distributed multi-agent systems.  We provide a complete  solution to the puzzle with the use of simple neural networks, capa(cid:173) ble of reasoning  about  time  and of knowledge  acquisition through  inductive learning.
Policy Search by Dynamic Programming
Authors: J. A. Bagnell, Sham M. Kakade, Jeff G. Schneider, Andrew Y. Ng
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We consider the policy search approach to reinforcement learning. We show that if a “baseline distribution” is given (indicating roughly how often we expect a good policy to visit each state), then we can derive a policy search algorithm that terminates in a ﬁnite number of steps, and for which we can provide non-trivial performance guarantees. We also demonstrate this algorithm on several grid-world POMDPs, a planar biped walking robot, and a double-pole balancing problem.
A Holistic Approach to Compositional Semantics: a connectionist model and robot experiments
Authors: Yuuya Sugita, Jun Tani
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We present a novel connectionist model for acquiring the semantics of a simple language through the behavioral experiences of a real robot. We focus on the “compositionality” of semantics, a fundamental character- istic of human language, which is the ability to understand the meaning of a sentence as a combination of the meanings of words. We also pay much attention to the “embodiment” of a robot, which means that the robot should acquire semantics which matches its body, or sensory-motor system. The essential claim is that an embodied compositional semantic representation can be self-organized from generalized correspondences between sentences and behavioral patterns. This claim is examined and conﬁrmed through simple experiments in which a robot generates corre- sponding behaviors from unlearned sentences by analogy with the corre- spondences between learned sentences and behaviors.
Semidefinite Relaxations for Approximate Inference on Graphs with Cycles
Authors: Michael I. Jordan, Martin J. Wainwright
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We present a new method for calculating approximate marginals for probability distributions deﬁned by graphs with cycles, based on a Gaus- sian entropy bound combined with a semideﬁnite outer bound on the marginal polytope. This combination leads to a log-determinant max- imization problem that can be solved by efﬁcient interior point meth- ods [8]. As with the Bethe approximation and its generalizations [12], the optimizing arguments of this problem can be taken as approximations to the exact marginals. In contrast to Bethe/Kikuchi approaches, our vari- ational problem is strictly convex and so has a unique global optimum. An additional desirable feature is that the value of the optimal solution is guaranteed to provide an upper bound on the log partition function. In experimental trials, the performance of the log-determinant relaxation is comparable to or better than the sum-product algorithm, and by a sub- stantial margin for certain problem classes. Finally, the zero-temperature limit of our log-determinant relaxation recovers a class of well-known semideﬁnite relaxations for integer programming [e.g., 3].
Discriminating Deformable Shape Classes
Authors: Salvador Ruiz-correa, Linda G. Shapiro, Marina Meila, Gabriel Berson
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We present and empirically test a novel approach for categorizing 3-D free form ob- ject shapes represented by range data . In contrast to traditional surface-signature based systems that use alignment to match speciﬁc objects, we adapted the newly introduced symbolic-signature representation to classify deformable shapes [10]. Our approach con- structs an abstract description of shape classes using an ensemble of classiﬁers that learn object class parts and their corresponding geometrical relationships from a set of numeric and symbolic descriptors. We used our classiﬁcation engine in a series of large scale dis- crimination experiments on two well-deﬁned classes that share many common distinctive features. The experimental results suggest that our method outperforms traditional numeric signature-based methodologies. 1
Limiting Form of the Sample Covariance Eigenspectrum in PCA and Kernel PCA
Authors: David Hoyle, Magnus Rattray
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We derive the limiting form of the eigenvalue spectrum for sample co- variance matrices produced from non-isotropic data. For the analysis of standard PCA we study the case where the data has increased variance along a small number of symmetry-breaking directions. The spectrum depends on the strength of the symmetry-breaking signals and on a pa- rameter (cid:11) which is the ratio of sample size to data dimension. Results are derived in the limit of large data dimension while keeping (cid:11) ﬁxed. As (cid:11) increases there are transitions in which delta functions emerge from the upper end of the bulk spectrum, corresponding to the symmetry-breaking directions in the data, and we calculate the bias in the corresponding eigenvalues. For kernel PCA the covariance matrix in feature space may contain symmetry-breaking structure even when the data components are independently distributed with equal variance. We show examples of phase-transition behaviour analogous to the PCA results in this case.
Auction Mechanism Design for Multi-Robot Coordination
Authors: Curt Bererton, Geoffrey J. Gordon, Sebastian Thrun
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The design of cooperative multi-robot systems is a highly active research area in robotics. Two lines of research in particular have generated inter- est: the solution of large, weakly coupled MDPs, and the design and im- plementation of market architectures. We propose a new algorithm which joins together these two lines of research. For a class of coupled MDPs, our algorithm automatically designs a market architecture which causes a decentralized multi-robot system to converge to a consistent policy. We can show that this policy is the same as the one which would be produced by a particular centralized planning algorithm. We demonstrate the new algorithm on three simulation examples: multi-robot towing, multi-robot path planning with a limited fuel resource, and coordinating behaviors in a game of paint ball.
Geometric Analysis of Constrained Curves
Authors: Anuj Srivastava, Washington Mio, Xiuwen Liu, Eric Klassen
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We present a geometric approach to statistical shape analysis of closed curves in images. The basic idea is to specify a space of closed curves satisfying given constraints, and exploit the differential geometry of this space to solve optimization and inference problems. We demonstrate this approach by: (i) deﬁning and computing statistics of observed shapes, (ii) deﬁning and learning a parametric probability model on shape space, and (iii) designing a binary hypothesis test on this space.
An Improved Scheme for Detection and Labelling in Johansson Displays
Authors: Claudio Fanti, Marzia Polito, Pietro Perona
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Consider a number of moving points, where each point is attached to a joint of the human body and projected onto an image plane. Johannson showed that humans can eﬀortlessly detect and recog- nize the presence of other humans from such displays. This is true even when some of the body points are missing (e.g. because of occlusion) and unrelated clutter points are added to the display. We are interested in replicating this ability in a machine. To this end, we present a labelling and detection scheme in a probabilistic framework. Our method is based on representing the joint prob- ability density of positions and velocities of body points with a graphical model, and using Loopy Belief Propagation to calculate a likely interpretation of the scene. Furthermore, we introduce a global variable representing the body’s centroid. Experiments on one motion-captured sequence suggest that our scheme improves on the accuracy of a previous approach based on triangulated graph- ical models, especially when very few parts are visible. The im- provement is due both to the more general graph structure we use and, more signiﬁcantly, to the introduction of the centroid variable.
1-norm Support Vector Machines
Authors: Ji Zhu, Saharon Rosset, Robert Tibshirani, Trevor J. Hastie
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The standard 2-norm SVM is known for its good performance in two- In this paper, we consider the 1-norm SVM. We class classi£cation. argue that the 1-norm SVM may have some advantage over the standard 2-norm SVM, especially when there are redundant noise features. We also propose an ef£cient algorithm that computes the whole solution path of the 1-norm SVM, hence facilitates adaptive selection of the tuning parameter for the 1-norm SVM.
Envelope-based Planning in Relational MDPs
Authors: Natalia H. Gardiol, Leslie P. Kaelbling
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: A mobile robot acting in the world is faced with a large amount of sen- sory data and uncertainty in its action outcomes. Indeed, almost all in- teresting sequential decision-making domains involve large state spaces and large, stochastic action sets. We investigate a way to act intelli- gently as quickly as possible in domains where ﬁnding a complete policy would take a hopelessly long time. This approach, Relational Envelope- based Planning (REBP) tackles large, noisy problems along two axes. First, describing a domain as a relational MDP (instead of as an atomic or propositionally-factored MDP) allows problem structure and dynam- ics to be captured compactly with a small set of probabilistic, relational rules. Second, an envelope-based approach to planning lets an agent be- gin acting quickly within a restricted part of the full state space and to judiciously expand its envelope as resources permit.
Necessary Intransitive Likelihood-Ratio Classifiers
Authors: Gang Ji, Jeff A. Bilmes
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: In pattern classiﬁcation tasks, errors are introduced because of differ- ences between the true model and the one obtained via model estimation. Using likelihood-ratio based classiﬁcation, it is possible to correct for this discrepancy by ﬁnding class-pair speciﬁc terms to adjust the likelihood ratio directly, and that can make class-pair preference relationships in- transitive. In this work, we introduce new methodology that makes nec- essary corrections to the likelihood ratio, speciﬁcally those that are nec- essary to achieve perfect classiﬁcation (but not perfect likelihood-ratio correction which can be overkill). The new corrections, while weaker than previously reported such adjustments, are analytically challenging since they involve discontinuous functions, therefore requiring several approximations. We test a number of these new schemes on an isolated- word speech recognition task as well as on the UCI machine learning data sets. Results show that by using the bias terms calculated in this new way, classiﬁcation accuracy can substantially improve over both the baseline and over our previous results.
Simplicial Mixtures of Markov Chains: Distributed Modelling of Dynamic User Profiles
Authors: Mark Girolami, Ata Kabán
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: To provide a compact generative representation of the sequential activ- ity of a number of individuals within a group there is a tradeoff between the deﬁnition of individual speciﬁc and global models. This paper pro- poses a linear-time distributed model for ﬁnite state symbolic sequences representing traces of individual user activity by making the assump- tion that heterogeneous user behavior may be ‘explained’ by a relatively small number of common structurally simple behavioral patterns which may interleave randomly in a user-speciﬁc proportion. The results of an empirical study on three different sources of user traces indicates that this modelling approach provides an efﬁcient representation scheme, re- ﬂected by improved prediction performance as well as providing low- complexity and intuitively interpretable representations.
Bounded Finite State Controllers
Authors: Pascal Poupart, Craig Boutilier
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We describe a new approximation algorithm for solving partially observ- able MDPs. Our bounded policy iteration approach searches through the space of bounded-size, stochastic ﬁnite state controllers, combining sev- eral advantages of gradient ascent (efﬁciency, search through restricted controller space) and policy iteration (less vulnerability to local optima).
Towards Social Robots: Automatic Evaluation of Human-Robot Interaction by Facial Expression Classification
Authors: G.C. Littlewort, M.S. Bartlett, I.R. Fasel, J. Chenu, T. Kanda, H. Ishiguro, J.R. Movellan
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Computer animated agents and robots bring a social dimension to hu- man computer interaction and force us to think in new ways about how computers could be used in daily life. Face to face communication is a real-time process operating at a time scale of less than a second. In this paper we present progress on a perceptual primitive to automatically detect frontal faces in the video stream and code them with respect to 7 dimensions in real time: neutral, anger, disgust, fear, joy, sadness, sur- prise. The face ﬁnder employs a cascade of feature detectors trained with boosting techniques [13, 2]. The expression recognizer employs a novel combination of Adaboost and SVM’s. The generalization performance to new subjects for a 7-way forced choice was 93.3% and 97% correct on two publicly available datasets. The outputs of the classiﬁer change smoothly as a function of time, providing a potentially valuable repre- sentation to code facial expression dynamics in a fully automatic and unobtrusive manner. The system was deployed and evaluated for mea- suring spontaneous facial expressions in the ﬁeld in an application for automatic assessment of human-robot interaction.
Entrainment of Silicon Central Pattern Generators for Legged Locomotory Control
Authors: Francesco Tenore, Ralph Etienne-Cummings, M. A. Lewis
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

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

Abstract: We present a uniﬁed view for online classiﬁcation, regression, and uni- class problems. This view leads to a single algorithmic framework for the three problems. We prove worst case loss bounds for various algorithms for both the realizable case and the non-realizable case. A conversion of our main online algorithm to the setting of batch learning is also dis- cussed. The end result is new algorithms and accompanying loss bounds for the hinge-loss.