mtybilly/Instruct2DS huggingface dataset:
Synchrony Detection by Analogue VLSI Neurons with Bimodal STDP Synapses
Authors: Alan F. Murray Adria Bofill-i-petit
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: Dengyong Zhou, André Elisseeff, William S. Noble, Christina S. Leslie Jason Weston
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: Victoria Stodden David Donoho
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.
A Biologically Plausible Algorithm for Reinforcement-shaped Representational Learning
Authors: Maneesh Sahani
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Signiﬁcant plasticity in sensory cortical representations can be driven in mature animals either by behavioural tasks that pair sensory stimuli with reinforcement, or by electrophysiological experiments that pair sensory input with direct stimulation of neuromodulatory nuclei, but usually not by sensory stimuli presented alone. Biologically motivated theories of representational learning, however, have tended to focus on unsupervised mechanisms, which may play a signiﬁcant role on evolutionary or devel- opmental timescales, but which neglect this essential role of reinforce- ment in adult plasticity. By contrast, theoretical reinforcement learning has generally dealt with the acquisition of optimal policies for action in an uncertain world, rather than with the concurrent shaping of sensory representations. This paper develops a framework for representational learning which builds on the relative success of unsupervised generative- modelling accounts of cortical encodings to incorporate the effects of reinforcement in a biologically plausible way.
Pairwise Clustering and Graphical Models
Authors: Assaf Zomet, Tomer Hertz, Yair Weiss Noam Shental
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: Ming-fai Wong, Pieter Abbeel, Daphne Koller Ben Taskar
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: Daniel Kersten, Paul R. Schrater, Alan L. Yuille Fang Fang
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: Branislav Kveton Milos Hauskrecht
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: J.k. O'regan, J.-p. Nadal, Olivier Coenen D. Philipona
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: Yoram Singer, Christopher D. Manning Ofer Dekel
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: James M. Rehg, Matthew D. Mullin Jianxin Wu
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: Sam T. Roweis, Nikos Vlassis Jakob J. Verbeek
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: David Horn, Eytan Ruppin, Shimon Edelman Zach Solan
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.
Modeling User Rating Profiles For Collaborative Filtering
Authors: Benjamin M. Marlin
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: In this paper we present a generative latent variable model for rating-based collaborative (cid:12)ltering called the User Rating Pro(cid:12)le model (URP). The generative process which underlies URP is de- signed to produce complete user rating pro(cid:12)les, an assignment of one rating to each item for each user. Our model represents each user as a mixture of user attitudes, and the mixing proportions are distributed according to a Dirichlet random variable. The rating for each item is generated by selecting a user attitude for the item, and then selecting a rating according to the preference pattern associ- ated with that attitude. URP is related to several models including a multinomial mixture model, the aspect model [7], and LDA [1], but has clear advantages over each.
Learning a World Model and Planning with a Self-Organizing, Dynamic Neural System
Authors: Marc Toussaint
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We present a connectionist architecture that can learn a model of the relations between perceptions and actions and use this model for be- havior planning. State representations are learned with a growing self- organizing layer which is directly coupled to a perception and a motor layer. Knowledge about possible state transitions is encoded in the lat- eral connectivity. Motor signals modulate this lateral connectivity and a dynamic ﬁeld on the layer organizes a planning process. All mecha- nisms are local and adaptation is based on Hebbian ideas. The model is continuous in the action, perception, and time domain.
Bias-Corrected Bootstrap and Model Uncertainty
Authors: Tommi S. Jaakkola Harald Steck
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: Valerio Mante, Matteo Carandini Vincent Bonin
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: Jason Weston, Arthur Gretton, Olivier Bousquet, Bernhard Schölkopf Dengyong Zhou
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: Manfred Opper Dörthe Malzahn
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.
An Infinity-sample Theory for Multi-category Large Margin Classification
Authors: Tong Zhang
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The purpose of this paper is to investigate inﬁnity-sample properties of risk minimization based multi-category classiﬁcation methods. These methods can be considered as natural extensions to binary large margin classiﬁcation. We establish conditions that guarantee the inﬁnity-sample consistency of classiﬁers obtained in the risk minimization framework. Examples are provided for two speciﬁc forms of the general formulation, which extend a number of known methods. Using these examples, we show that some risk minimization formulations can also be used to ob- tain conditional probability estimates for the underlying problem. Such conditional probability information will be useful for statistical inferenc- ing tasks beyond classiﬁcation.
1 Motivation Consider a binary classiﬁcation problem where we want to predict label y ∈ {±1} based on observation x. One of the most signiﬁcant achievements for binary classiﬁcation in machine learning is the invention of large margin methods, which include support vector machines and boosting algorithms. Based on a set of observations (X1, Y1), . . . , (Xn, Yn), a large margin classiﬁcation algorithm produces a decision function ˆfn by empirically min- imizing a loss function that is often a convex upper bound of the binary classiﬁcation error function. Given ˆfn, the binary decision rule is to predict y = 1 if ˆfn(x) ≥ 0, and to predict y = −1 otherwise (the decision rule at ˆfn(x) = 0 is not important). In the literature, the following form of large margin binary classiﬁcation is often encountered: we minimize the empirical risk associated with a convex function φ in a pre-chosen function class Cn:
ˆfn = arg min f∈Cn
A Neuromorphic Multi-chip Model of a Disparity Selective Complex Cell
Authors: Eric K. Tsang Bertram E. Shi
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: Laurent El Ghaoui Arnab Nilim
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: Todd K. Leen, António M. Baptista Cynthia Archer
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.
Sensory Modality Segregation
Authors: Virginia Sa
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Why are sensory modalities segregated the way they are? In this paper we show that sensory modalities are well designed for self-supervised cross-modal learning. Using the Minimizing-Disagreement algorithm on an unsupervised speech categorization task with visual (moving lips) and auditory (sound signal) inputs, we show that very informative auditory dimensions actually harm performance when moved to the visual side of the network. It is better to throw them away than to consider them part of the “visual input”. We explain this ﬁnding in terms of the statistical structure in sensory inputs.
Nonstationary Covariance Functions for Gaussian Process Regression
Authors: Mark J. Schervish Christopher J. Paciorek
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: Luis E. Ortiz Michael Kearns
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: Nimrod Megiddo Daniela Pucci de Farias
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: Luis C. Lamb Artur Garcez
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: Sham M. Kakade, Jeff G. Schneider, Andrew Y. Ng J. A. Bagnell
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: Jun Tani Yuuya Sugita
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: Martin J. Wainwright Michael I. Jordan
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: Linda G. Shapiro, Marina Meila, Gabriel Berson Salvador Ruiz-correa
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: Magnus Rattray David Hoyle
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: Geoffrey J. Gordon, Sebastian Thrun Curt Bererton
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: Washington Mio, Xiuwen Liu, Eric Klassen Anuj Srivastava
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.
A Low-Power Analog VLSI Visual Collision Detector
Authors: Reid R. Harrison
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We have designed and tested a single-chip analog VLSI sensor that  detects  imminent  collisions  by  measuring  radially  expansive  optic  flow.    The  design  of  the  chip  is  based  on  a  model  proposed  to  explain  leg-extension behavior in flies during  landing  approaches.   A new elementary motion detector (EMD) circuit was developed to  measure optic flow.  This EMD circuit models the bandpass nature  of  large  monopolar  cells  (LMCs)  immediately  postsynaptic  to  photoreceptors  in  the  fly  visual  system.    A  16  ×  16  array  of  2-D  motion detectors was fabricated on a 2.24 mm × 2.24 mm die in a  standard  0.5-µm  CMOS  process.    The  chip  consumes  140  µW  of  power from a 5 V supply.  With the addition of wide-angle optics,  the sensor is able to detect collisions around 500 ms before impact  in complex, real-world scenes.
An Improved Scheme for Detection and Labelling in Johansson Displays
Authors: Marzia Polito, Pietro Perona Claudio Fanti
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: Saharon Rosset, Robert Tibshirani, Trevor J. Hastie Ji Zhu
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: Leslie P. Kaelbling Natalia H. Gardiol
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: Jeff A. Bilmes Gang Ji
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: Ata Kabán Mark Girolami
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: Craig Boutilier Pascal Poupart
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).
Sparseness of Support Vector Machines---Some Asymptotically Sharp Bounds
Authors: Ingo Steinwart
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The decision functions constructed by support vector machines (SVM’s) usually depend only on a subset of the training set—the so-called support vectors. We derive asymptotically sharp lower and upper bounds on the number of support vectors for several standard types of SVM’s. In par- ticular, we show for the Gaussian RBF kernel that the fraction of support vectors tends to twice the Bayes risk for the L1-SVM, to the probability of noise for the L2-SVM, and to 1 for the LS-SVM.
Towards Social Robots: Automatic Evaluation of Human-Robot Interaction by Facial Expression Classification
Authors: M.S. Bartlett, I.R. Fasel, J. Chenu, T. Kanda, H. Ishiguro, J.R. Movellan G.C. Littlewort
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.