mtybilly/Instruct2DS huggingface dataset:
Can We Learn to Beat the Best Stock
Authors: Allan Borodin, Ran El-Yaniv, Vincent Gogan
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: A novel algorithm for actively trading stocks is presented. While tradi- tional universal algorithms (and technical trading heuristics) attempt to predict winners or trends, our approach relies on predictable statistical relations between all pairs of stocks in the market. Our empirical results on historical markets provide strong evidence that this type of techni- cal trading can “beat the market” and moreover, can beat the best stock in the market. In doing so we utilize a new idea for smoothing critical parameters in the context of expert learning.
1 Introduction: The Portfolio Selection Problem
The portfolio selection (PS) problem is a challenging problem for machine learning, online algorithms and, of course, computational ﬁnance. As is well known (e.g. see Lugosi [1]) sequence prediction under the log loss measure can be viewed as a special case of portfo- lio selection, and perhaps more surprisingly, from a certain worst case minimax criterion, portfolio selection is not essentially any harder (than prediction) as shown in [2] (see also [1], Thm. 20 & 21). But there seems to be a qualitative difference between the practical utility of “universal” sequence prediction and universal portfolio selection. Simply stated, universal sequence prediction algorithms under various probabilistic and worst-case mod- els work very well in practice whereas the known universal portfolio selection algorithms do not seem to provide any substantial beneﬁt over a naive investment strategy (see Sec. 4).
A major pragmatic question is whether or not a computer program can consistently out- perform the market. A closer inspection of the interesting ideas developed in information theory and online learning suggests that a promising approach is to exploit the natural volatility in the market and in particular to beneﬁt from simple and rather persistent statis- tical relations between stocks rather than to try to predict stock prices or “winners”. We present a non-universal portfolio selection algorithm1, which does not try to predict win- ners. The motivation behind our algorithm is the rationale behind constant rebalancing algorithms and the worst case study of universal trading introduced by Cover [3]. Not only does our proposed algorithm substantially “beat the market” on historical markets, it also beats the best stock. So why are we presenting this algorithm and not just simply making money? There are, of course some caveats and obstacles to utilizing the algorithm. But for large investors the possibility of a goose laying silver (if not golden) eggs is not impossible.
1Any PS algorithm can be modiﬁed to be universal by investing any ﬁxed fraction of the initial
wealth in a universal algorithm.
An MCMC-Based Method of Comparing Connectionist Models in Cognitive Science
Authors: Woojae Kim, Daniel J. Navarro, Mark A. Pitt, In J. Myung
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Despite the popularity of connectionist models in cognitive science, their performance can often be diﬃcult to evaluate. Inspired by the geometric approach to statistical model selection, we introduce a conceptually similar method to examine the global behavior of a connectionist model, by counting the number and types of response patterns it can simulate. The Markov Chain Monte Carlo-based algorithm that we constructed (cid:222)nds these patterns eﬃciently. We demonstrate the approach using two localist network models of speech perception.
Dynamical Modeling with Kernels for Nonlinear Time Series Prediction
Authors: Liva Ralaivola, Florence d'Alché-Buc
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We consider the question of predicting nonlinear time series. Kernel Dy- namical Modeling (KDM), a new method based on kernels, is proposed as an extension to linear dynamical models. The kernel trick is used twice: ﬁrst, to learn the parameters of the model, and second, to compute preimages of the time series predicted in the feature space by means of Support Vector Regression. Our model shows strong connection with the classic Kalman Filter model, with the kernel feature space as hidden state space. Kernel Dynamical Modeling is tested against two benchmark time series and achieves high quality predictions.
Learning Non-Rigid 3D Shape from 2D Motion
Authors: Lorenzo Torresani, Aaron Hertzmann, Christoph Bregler
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: This paper presents an algorithm for learning the time-varying shape of a non-rigid 3D object from uncalibrated 2D tracking data. We model shape motion as a rigid component (rotation and translation) combined with a non-rigid deformation. Reconstruction is ill-posed if arbitrary deforma- tions are allowed. We constrain the problem by assuming that the object shape at each time instant is drawn from a Gaussian distribution. Based on this assumption, the algorithm simultaneously estimates 3D shape and motion for each time frame, learns the parameters of the Gaussian, and robustly ﬁlls-in missing data points. We then extend the algorithm to model temporal smoothness in object shape, thus allowing it to handle severe cases of missing data.
Discriminative Fields for Modeling Spatial Dependencies in Natural Images
Authors: Sanjiv Kumar, Martial Hebert
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: In this paper we present Discriminative Random Fields (DRF), a discrim- inative framework for the classiﬁcation of natural image regions by incor- porating neighborhood spatial dependencies in the labels as well as the observed data. The proposed model exploits local discriminative models and allows to relax the assumption of conditional independence of the observed data given the labels, commonly used in the Markov Random Field (MRF) framework. The parameters of the DRF model are learned using penalized maximum pseudo-likelihood method. Furthermore, the form of the DRF model allows the MAP inference for binary classiﬁca- tion problems using the graph min-cut algorithms. The performance of the model was veriﬁed on the synthetic as well as the real-world images. The DRF model outperforms the MRF model in the experiments.
Fast Algorithms for Large-State-Space HMMs with Applications to Web Usage Analysis
Authors: Pedro F. Felzenszwalb, Daniel P. Huttenlocher, Jon M. Kleinberg
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: In applying Hidden Markov Models to the analysis of massive data streams, it is often necessary to use an arti(cid:12)cially reduced set of states; this is due in large part to the fact that the basic HMM estimation algorithms have a quadratic dependence on the size of the state set. We present algorithms that reduce this computational bottleneck to linear or near-linear time, when the states can be embedded in an underlying grid of parameters. This type of state representation arises in many domains; in particular, we show an application to tra(cid:14)c analysis at a high-volume Web site.
A Probabilistic Model of Auditory Space Representation in the Barn Owl
Authors: Brian J. Fischer, Charles H. Anderson
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The barn owl is a nocturnal hunter, capable of capturing prey using au- ditory information alone [1]. The neural basis for this localization be- havior is the existence of auditory neurons with spatial receptive ﬁelds [2]. We provide a mathematical description of the operations performed on auditory input signals by the barn owl that facilitate the creation of a representation of auditory space. To develop our model, we ﬁrst formu- late the sound localization problem solved by the barn owl as a statistical estimation problem. The implementation of the solution is constrained by the known neurobiology.
Tree-structured Approximations by Expectation Propagation
Authors: Yuan Qi, Tom Minka
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Approximation structure plays an important role in inference on loopy graphs. As a tractable structure, tree approximations have been utilized in the variational method of Ghahramani & Jordan (1997) and the se- quential projection method of Frey et al. (2000). However, belief propa- gation represents each factor of the graph with a product of single-node messages. In this paper, belief propagation is extended to represent fac- tors with tree approximations, by way of the expectation propagation framework. That is, each factor sends a “message” to all pairs of nodes in a tree structure. The result is more accurate inferences and more fre- quent convergence than ordinary belief propagation, at a lower cost than variational trees or double-loop algorithms.
Boosting versus Covering
Authors: Kohei Hatano, Manfred K. Warmuth
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We investigate improvements of AdaBoost that can exploit the fact that the weak hypotheses are one-sided, i.e. either all its positive (or negative) predictions are correct. In particular, for any set of m labeled examples consistent with a disjunction of k literals (which are one-sided in this case), AdaBoost constructs a consistent hypothesis by using O(k2 log m) iterations. On the other hand, a greedy set covering algorithm ﬁnds a consistent hypothesis of size O(k log m). Our primary question is whether there is a simple boosting algorithm that performs as well as the greedy set covering. We ﬁrst show that InfoBoost, a modiﬁcation of AdaBoost pro- posed by Aslam for a diﬀerent purpose, does perform as well as the greedy set covering algorithm. We then show that AdaBoost requires Ω(k2 log m) iterations for learning k-literal disjunctions. We achieve this with an adversary construction and as well as in simple experiments based on artiﬁcial data. Further we give a vari- ant called SemiBoost that can handle the degenerate case when the given examples all have the same label. We conclude by showing that SemiBoost can be used to produce small conjunctions as well.
Learning Near-Pareto-Optimal Conventions in Polynomial Time
Authors: Xiaofeng Wang, Tuomas Sandholm
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We study how to learn to play a Pareto-optimal strict Nash equilibrium when there exist multiple equilibria and agents may have different pref- erences among the equilibria. We focus on repeated coordination games of non-identical interest where agents do not know the game structure up front and receive noisy payoffs. We design efﬁcient near-optimal al- gorithms for both the perfect monitoring and the imperfect monitoring setting(where the agents only observe their own payoffs and the joint actions).
Using the Forest to See the Trees: A Graphical Model Relating Features, Objects, and Scenes
Authors: Kevin P. Murphy, Antonio Torralba, William T. Freeman
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Standard approaches to object detection focus on local patches of the image, and try to classify them as background or not. We propose to use the scene context (image as a whole) as an extra source of (global) information, to help resolve local ambiguities. We present a conditional random ﬁeld for jointly solving the tasks of object detection and scene classiﬁcation.
Approximability of Probability Distributions
Authors: Alina Beygelzimer, Irina Rish
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We consider the question of how well a given distribution can be approx- imated with probabilistic graphical models. We introduce a new param- eter, effective treewidth, that captures the degree of approximability as a tradeoff between the accuracy and the complexity of approximation. We present a simple approach to analyzing achievable tradeoffs that ex- ploits the threshold behavior of monotone graph properties, and provide experimental results that support the approach.
Gene Expression Clustering with Functional Mixture Models
Authors: Darya Chudova, Christopher Hart, Eric Mjolsness, Padhraic Smyth
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We propose a functional mixture model for simultaneous clustering and alignment of sets of curves measured on a discrete time grid. The model is speciﬁcally tailored to gene expression time course data. Each func- tional cluster center is a nonlinear combination of solutions of a simple linear differential equation that describes the change of individual mRNA levels when the synthesis and decay rates are constant. The mixture of continuous time parametric functional forms allows one to (a) account for the heterogeneity in the observed proﬁles, (b) align the proﬁles in time by estimating real-valued time shifts, (c) capture the synthesis and decay of mRNA in the course of an experiment, and (d) regularize noisy proﬁles by enforcing smoothness in the mean curves. We derive an EM algo- rithm for estimating the parameters of the model, and apply the proposed approach to the set of cycling genes in yeast. The experiments show consistent improvement in predictive power and within cluster variance compared to regular Gaussian mixtures.
Large Scale Online Learning
Authors: Léon Bottou, Yann L. Cun
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We consider situations where training data is abundant and computing resources are comparatively scarce. We argue that suitably designed on- line learning algorithms asymptotically outperform any batch learning algorithm. Both theoretical and experimental evidences are presented.
Plasticity Kernels and Temporal Statistics
Authors: Peter Dayan, Michael Häusser, Michael London
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Computational  mysteries  surround  the  kernels  relating  the  magnitude  and  sign  of  changes  in  efficacy  as  a  function  of  the time difference between pre- and post-synaptic  activity at  a synapse.  One important idea34  is that kernels result from fil(cid:173) tering, ie an attempt by synapses to eliminate noise corrupting  learning.  This idea has hitherto been applied to trace learning  rules; we apply it to experimentally-defined kernels, using it to  reverse-engineer assumed signal statistics. We also extend it to  consider the additional goal for  filtering of weighting learning  according  to  statistical  surprise,  as  in the  Z-score  transform.  This provides a fresh view of observed kernels and can lead to  different, and more natural, signal statistics.
Phonetic Speaker Recognition with Support Vector Machines
Authors: William M. Campbell, Joseph P. Campbell, Douglas A. Reynolds, Douglas A. Jones, Timothy R. Leek
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: A recent area of signiﬁcant progress in speaker recognition is the use of high level features—idiolect, phonetic relations, prosody, discourse structure, etc. A speaker not only has a distinctive acoustic sound but uses language in a characteristic manner. Large corpora of speech data available in recent years allow experimentation with long term statistics of phone patterns, word patterns, etc. of an individual. We propose the use of support vector machines and term frequency analysis of phone se- quences to model a given speaker. To this end, we explore techniques for text categorization applied to the problem. We derive a new kernel based upon a linearization of likelihood ratio scoring. We introduce a new phone-based SVM speaker recognition approach that halves the er- ror rate of conventional phone-based approaches.
Information Maximization in Noisy Channels : A Variational Approach
Authors: David Barber, Felix V. Agakov
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The maximisation of information transmission over noisy channels is a common, albeit generally computationally diﬃcult problem. We approach the diﬃculty of computing the mutual information for noisy channels by using a variational approximation. The re- sulting IM algorithm is analagous to the EM algorithm, yet max- imises mutual information, as opposed to likelihood. We apply the method to several practical examples, including linear compression, population encoding and CDMA.
Variational Linear Response
Authors: Manfred Opper, Ole Winther
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: A general linear response method for deriving improved estimates of cor- relations in the variational Bayes framework is presented. Three applica- tions are given and it is discussed how to use linear response as a general principle for improving mean ﬁeld approximations.
Circuit Optimization Predicts Dynamic Networks for Chemosensory Orientation in Nematode C. elegans
Authors: Nathan A. Dunn, John S. Conery, Shawn R. Lockery
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The connectivity of the nervous system of the nematode Caenorhabdi- tis elegans has been described completely, but the analysis of the neu- ronal basis of behavior in this system is just beginning. Here, we used an optimization algorithm to search for patterns of connectivity sufﬁ- cient to compute the sensorimotor transformation underlying C. elegans chemotaxis, a simple form of spatial orientation behavior in which turn- ing probability is modulated by the rate of change of chemical concen- tration. Optimization produced differentiator networks with inhibitory feedback among all neurons. Further analysis showed that feedback reg- ulates the latency between sensory input and behavior. Common patterns of connectivity between the model and biological networks suggest new functions for previously identiﬁed connections in the C. elegans nervous system.
Learning to Find Pre-Images
Authors: Jason Weston, Bernhard Schölkopf, Gökhan H. Bakir
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We consider the problem of reconstructing patterns from a feature map. Learning algorithms using kernels to operate in a reproducing kernel Hilbert space (RKHS) express their solutions in terms of input points mapped into the RKHS. We introduce a technique based on kernel princi- pal component analysis and regression to reconstruct corresponding pat- terns in the input space (aka pre-images) and review its performance in several applications requiring the construction of pre-images. The intro- duced technique avoids difﬁcult and/or unstable numerical optimization, is easy to implement and, unlike previous methods, permits the compu- tation of pre-images in discrete input spaces.
Sparse Representation and Its Applications in Blind Source Separation
Authors: Yuanqing Li, Shun-ichi Amari, Sergei Shishkin, Jianting Cao, Fanji Gu, Andrzej S. Cichocki
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: In this paper, sparse representation (factorization) of a data matrix is ﬁrst discussed. An overcomplete basis matrix is estimated by using the K(cid:0)means method. We have proved that for the estimated overcom- plete basis matrix, the sparse solution (coefﬁcient matrix) with minimum l1(cid:0)norm is unique with probability of one, which can be obtained using a linear programming algorithm. The comparisons of the l1(cid:0)norm so- lution and the l0(cid:0)norm solution are also presented, which can be used in recoverability analysis of blind source separation (BSS). Next, we ap- ply the sparse matrix factorization approach to BSS in the overcomplete case. Generally, if the sources are not sufﬁciently sparse, we perform blind separation in the time-frequency domain after preprocessing the observed data using the wavelet packets transformation. Third, an EEG experimental data analysis example is presented to illustrate the useful- ness of the proposed approach and demonstrate its performance. Two almost independent components obtained by the sparse representation method are selected for phase synchronization analysis, and their peri- ods of signiﬁcant phase synchronization are found which are related to tasks. Finally, concluding remarks review the approach and state areas that require further study.
Probabilistic Inference in Human Sensorimotor Processing
Authors: Konrad P. Körding, Daniel M. Wolpert
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: When we learn a new motor skill, we have to contend with both the vari- ability inherent in our sensors and the task. The sensory uncertainty can be reduced by using information about the distribution of previously ex- perienced tasks. Here we impose a distribution on a novel sensorimotor task and manipulate the variability of the sensory feedback. We show that subjects internally represent both the distribution of the task as well as their sensory uncertainty. Moreover, they combine these two sources of information in a way that is qualitatively predicted by optimal Bayesian processing. We further analyze if the subjects can represent multimodal distributions such as mixtures of Gaussians. The results show that the CNS employs probabilistic models during sensorimotor learning even when the priors are multimodal.
From Algorithmic to Subjective Randomness
Authors: Thomas L. Griffiths, Joshua B. Tenenbaum
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We explore the phenomena of subjective randomness as a case study in understanding how people discover structure embedded in noise. We present a rational account of randomness perception based on the statis- tical problem of model selection: given a stimulus, inferring whether the process that generated it was random or regular. Inspired by the mathe- matical definition of randomness given by Kolmogorov complexity, we characterize regularity in terms of a hierarchy of automata that augment a finite controller with different forms of memory. We find that the reg- ularities detected in binary sequences depend upon presentation format, and that the kinds of automata that can identify these regularities are in- formative about the cognitive processes engaged by different formats.
Eye Micro-movements Improve Stimulus Detection Beyond the Nyquist Limit in the Peripheral Retina
Authors: Matthias H. Hennig, Florentin Wörgötter
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Even under perfect ﬁxation the human eye is under steady motion (tremor, microsaccades, slow drift). The “dynamic” theory of vi- sion [1, 2] states that eye-movements can improve hyperacuity. Accord- ing to this theory, eye movements are thought to create variable spatial excitation patterns on the photoreceptor grid, which will allow for better spatiotemporal summation at later stages. We reexamine this theory us- ing a realistic model of the vertebrate retina by comparing responses of a resting and a moving eye. The performance of simulated ganglion cells in a hyperacuity task is evaluated by ideal observer analysis. We ﬁnd that in the central retina eye-micromovements have no effect on the perfor- mance. Here optical blurring limits vernier acuity. In the retinal periph- ery however, eye-micromovements clearly improve performance. Based on ROC analysis, our predictions are quantitatively testable in electro- physiological and psychophysical experiments.
Mechanism of Neural Interference by Transcranial Magnetic Stimulation: Network or Single Neuron?
Authors: Yoichi Miyawaki, Masato Okada
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: This paper proposes neural mechanisms of transcranial magnetic stim- ulation (TMS). TMS can stimulate the brain non-invasively through a brief magnetic pulse delivered by a coil placed on the scalp, interfering with speciﬁc cortical functions with a high temporal resolution. Due to these advantages, TMS has been a popular experimental tool in various neuroscience ﬁelds. However, the neural mechanisms underlying TMS- induced interference are still unknown; a theoretical basis for TMS has not been developed. This paper provides computational evidence that in- hibitory interactions in a neural population, not an isolated single neuron, play a critical role in yielding the neural interference induced by TMS.
Efficient Multiscale Sampling from Products of Gaussian Mixtures
Authors: Alexander T. Ihler, Erik B. Sudderth, William T. Freeman, Alan S. Willsky
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The problem of approximating the product of several Gaussian mixture distributions arises in a number of contexts, including the nonparametric belief propagation (NBP) inference algorithm and the training of prod- uct of experts models. This paper develops two multiscale algorithms for sampling from a product of Gaussian mixtures, and compares their performance to existing methods. The ﬁrst is a multiscale variant of pre- viously proposed Monte Carlo techniques, with comparable theoretical guarantees but improved empirical convergence rates. The second makes use of approximate kernel density evaluation methods to construct a fast approximate sampler, which is guaranteed to sample points to within a tunable parameter (cid:15) of their true probability. We compare both multi- scale samplers on a set of computational examples motivated by NBP, demonstrating signiﬁcant improvements over existing methods.
Markov Models for Automated ECG Interval Analysis
Authors: Nicholas P. Hughes, Lionel Tarassenko, Stephen J. Roberts
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We examine the use of hidden Markov and hidden semi-Markov mod- els for automatically segmenting an electrocardiogram waveform into its constituent waveform features. An undecimated wavelet transform is used to generate an overcomplete representation of the signal that is more appropriate for subsequent modelling. We show that the state dura- tions implicit in a standard hidden Markov model are ill-suited to those of real ECG features, and we investigate the use of hidden semi-Markov models for improved state duration modelling.
A Mixed-Signal VLSI for Real-Time Generation of Edge-Based Image Vectors
Authors: Masakazu Yagi, Hideo Yamasaki, Tadashi Shibata
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: A mixed-signal image filtering VLSI has been developed aiming at  real-time generation of edge-based image vectors for robust image  recognition. A four-stage asynchronous median detection architec- ture  based  on  analog  digital  mixed-signal  circuits  has  been  intro- duced  to  determine  the  threshold  value  of  edge  detection,  the  key  processing  parameter  in  vector  generation.  As  a  result,  a  fully  seamless pipeline processing from threshold detection to edge fea- ture  map  generation  has  been  established.  A  prototype  chip  was  designed in a 0.35-µm double-polysilicon three-metal-layer CMOS  technology and the concept was verified by the fabricated chip. The  chip  generates  a  64-dimension  feature  vector  from  a  64x64-pixel  gray scale image every 80µsec. This is about 104 times faster than the  software computation, making a real-time image recognition system  feasible.
Autonomous Helicopter Flight via Reinforcement Learning
Authors: H. J. Kim, Michael I. Jordan, Shankar Sastry, Andrew Y. Ng
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Autonomous helicopter ﬂight represents a challenging control problem, with complex, noisy, dynamics. In this paper, we describe a successful application of reinforcement learning to autonomous helicopter ﬂight. We ﬁrst ﬁt a stochastic, nonlinear model of the helicopter dynamics. We then use the model to learn to hover in place, and to ﬂy a number of maneuvers taken from an RC helicopter competition.
Insights from Machine Learning Applied to Human Visual Classification
Authors: Felix A. Wichmann, Arnulf B. Graf
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We attempt to understand visual classiﬁcation in humans using both psy- chophysical and machine learning techniques. Frontal views of human faces were used for a gender classiﬁcation task. Human subjects classi- ﬁed the faces and their gender judgment, reaction time and conﬁdence rating were recorded. Several hyperplane learning algorithms were used on the same classiﬁcation task using the Principal Components of the texture and shape representation of the faces. The classiﬁcation perfor- mance of the learning algorithms was estimated using the face database with the true gender of the faces as labels, and also with the gender es- timated by the subjects. We then correlated the human responses to the distance of the stimuli to the separating hyperplane of the learning algo- rithms. Our results suggest that human classiﬁcation can be modeled by some hyperplane algorithms in the feature space we used. For classiﬁca- tion, the brain needs more processing for stimuli close to that hyperplane than for those further away.
Classification with Hybrid Generative/Discriminative Models
Authors: Rajat Raina, Yirong Shen, Andrew McCallum, Andrew Y. Ng
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Although discriminatively trained classiﬁers are usually more accurate when labeled training data is abundant, previous work has shown that when training data is limited, generative classiﬁers can out-perform them. This paper describes a hybrid model in which a high-dimensional subset of the parameters are trained to maximize generative likelihood, and another, small, subset of parameters are discriminatively trained to maximize conditional likelihood. We give a sample complexity bound showing that in order to ﬁt the discriminative parameters well, the num- ber of training examples required depends only on the logarithm of the number of feature occurrences and feature set size. Experimental results show that hybrid models can provide lower test error and can produce better accuracy/coverage curves than either their purely generative or purely discriminative counterparts. We also discuss several advantages of hybrid models, and advocate further work in this area.
Feature Selection in Clustering Problems
Authors: Volker Roth, Tilman Lange
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: A novel approach to combining clustering and feature selection is pre- sented. It implements a wrapper strategy for feature selection, in the sense that the features are directly selected by optimizing the discrimina- tive power of the used partitioning algorithm. On the technical side, we present an efﬁcient optimization algorithm with guaranteed local con- vergence property. The only free parameter of this method is selected by a resampling-based stability analysis. Experiments with real-world datasets demonstrate that our method is able to infer both meaningful partitions and meaningful subsets of features.
Invariant Pattern Recognition by Semi-Definite Programming Machines
Authors: Thore Graepel, Ralf Herbrich
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: invariances with respect to given pattern Knowledge about local transformations can greatly improve the accuracy of classiﬁcation. Previous approaches are either based on regularisation or on the gen- eration of virtual (transformed) examples. We develop a new frame- work for learning linear classiﬁers under known transformations based on semideﬁnite programming. We present a new learning algorithm— the Semideﬁnite Programming Machine (SDPM)—which is able to ﬁnd a maximum margin hyperplane when the training examples are polynomial trajectories instead of single points. The solution is found to be sparse in dual variables and allows to identify those points on the trajectory with minimal real-valued output as virtual support vec- tors. Extensions to segments of trajectories, to more than one trans- formation parameter, and to learning with kernels are discussed. In experiments we use a Taylor expansion to locally approximate rota- tional invariance in pixel images from USPS and ﬁnd improvements over known methods.
Impact of an Energy Normalization Transform on the Performance of the LF-ASD Brain Computer Interface
Authors: Yu Zhou, Steven G. Mason, Gary E. Birch
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: This  paper  presents  an  energy  normalization  transform  as  a  method to reduce system errors in the LF-ASD brain-computer  interface.  The energy normalization transform has two major  benefits to the system performance. First, it can increase class  separation  between  the  active  and  idle  EEG  data.    Second,  it  can  desensitize  the  system  to  the  signal  amplitude  variability.  For  four  subjects  in  the  study,  the  benefits  resulted  in  the  performance  improvement  of  the  LF-ASD  in  the  range  from  7.7% to 18.9%, while for the fifth subject, who had the highest  non-normalized  accuracy  of  90.5%,  the  performance  did  not  change notably with normalization.
Subject-Independent Magnetoencephalographic Source Localization by a Multilayer Perceptron
Authors: Sung C. Jun, Barak A. Pearlmutter
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We describe a system that localizes a single dipole to reasonable accu- racy from noisy magnetoencephalographic (MEG) measurements in real time. At its core is a multilayer perceptron (MLP) trained to map sen- sor signals and head position to dipole location. Including head position overcomes the previous need to retrain the MLP for each subject and ses- sion. The training dataset was generated by mapping randomly chosen dipoles and head positions through an analytic model and adding noise from real MEG recordings. After training, a localization took 0.7 ms with an average error of 0.90 cm. A few iterations of a Levenberg-Marquardt routine using the MLP’s output as its initial guess took 15 ms and im- proved the accuracy to 0.53 cm, only slightly above the statistical limits on accuracy imposed by the noise. We applied these methods to localize single dipole sources from MEG components isolated by blind source separation and compared the estimated locations to those generated by standard manually-assisted commercial software.
Image Reconstruction by Linear Programming
Authors: Koji Tsuda, Gunnar Rätsch
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: A common way of image denoising is to project a noisy image to the sub- space of admissible images made for instance by PCA. However, a major drawback of this method is that all pixels are updated by the projection, even when only a few pixels are corrupted by noise or occlusion. We pro- pose a new method to identify the noisy pixels by (cid:1) 1-norm penalization and update the identiﬁed pixels only. The identiﬁcation and updating of noisy pixels are formulated as one linear program which can be solved efﬁciently. Especially, one can apply the ν-trick to directly specify the fraction of pixels to be reconstructed. Moreover, we extend the linear program to be able to exploit prior knowledge that occlusions often ap- pear in contiguous blocks (e.g. sunglasses on faces). The basic idea is to penalize boundary points and interior points of the occluded area dif- ferently. We are able to show the ν-property also for this extended LP leading a method which is easy to use. Experimental results impressively demonstrate the power of our approach.
Extreme Components Analysis
Authors: Max Welling, Christopher Williams, Felix V. Agakov
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Principal components analysis (PCA) is one of the most widely used techniques in machine learning and data mining. Minor components analysis (MCA) is less well known, but can also play an important role in the presence of constraints on the data distribution. In this paper we present a probabilistic model for “extreme components analysis” (XCA) which at the maximum likelihood solution extracts an optimal combina- tion of principal and minor components. For a given number of compo- nents, the log-likelihood of the XCA model is guaranteed to be larger or equal than that of the probabilistic models for PCA and MCA. We de- scribe an efﬁcient algorithm to solve for the globally optimal solution. For log-convex spectra we prove that the solution consists of principal components only, while for log-concave spectra the solution consists of minor components. In general, the solution admits a combination of both. In experiments we explore the properties of XCA on some synthetic and real-world datasets.
Bayesian Color Constancy with Non-Gaussian Models
Authors: Charles Rosenberg, Alok Ladsariya, Tom Minka
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We present a Bayesian approach to color constancy which utilizes a non- Gaussian probabilistic model of the image formation process. The pa- rameters of this model are estimated directly from an uncalibrated image set and a small number of additional algorithmic parameters are chosen using cross validation. The algorithm is empirically shown to exhibit RMS error lower than other color constancy algorithms based on the Lambertian surface reﬂectance model when estimating the illuminants of a set of test images. This is demonstrated via a direct performance comparison utilizing a publicly available set of real world test images and code base.
All learning is Local: Multi-agent Learning in Global Reward Games
Authors: Yu-han Chang, Tracey Ho, Leslie P. Kaelbling
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: In large multiagent games, partial observability, coordination, and credit assignment persistently plague attempts to design good learning algo- rithms. We provide a simple and efﬁcient algorithm that in part uses a linear system to model the world from a single agent’s limited per- spective, and takes advantage of Kalman ﬁltering to allow an agent to construct a good training signal and learn an effective policy.
Automatic Annotation of Everyday Movements
Authors: Deva Ramanan, David A. Forsyth
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: This paper describes a system that can annotate a video sequence with: a description of the appearance of each actor; when the actor is in view; and a representation of the actor’s activity while in view. The system does not require a ﬁxed background, and is automatic. The system works by (1) tracking people in 2D and then, using an annotated motion capture dataset, (2) synthesizing an annotated 3D motion sequence matching the 2D tracks. The 3D motion capture data is manually annotated off-line using a class structure that describes everyday motions and allows mo- tion annotations to be composed — one may jump while running, for example. Descriptions computed from video of real motions show that the method is accurate.
A Classification-based Cocktail-party Processor
Authors: Nicoleta Roman, Deliang Wang, Guy J. Brown
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Guy J. Brown 
Department of Computer Science 
University of Sheffield  211 Portobello Street  Sheffield, S1 4DP, UK  g.brown@dcs.shef.ac.uk
Linear Dependent Dimensionality Reduction
Authors: Nathan Srebro, Tommi S. Jaakkola
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: We formulate linear dimensionality reduction as a semi-parametric esti- mation problem, enabling us to study its asymptotic behavior. We gen- eralize the problem beyond additive Gaussian noise to (unknown) non- Gaussian additive noise, and to unbiased non-additive models.
Clustering with the Connectivity Kernel
Authors: Bernd Fischer, Volker Roth, Joachim M. Buhmann
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Clustering aims at extracting hidden structure in dataset. While the prob- lem of ﬁnding compact clusters has been widely studied in the litera- ture, extracting arbitrarily formed elongated structures is considered a much harder problem. In this paper we present a novel clustering algo- rithm which tackles the problem by a two step procedure: ﬁrst the data are transformed in such a way that elongated structures become compact ones. In a second step, these new objects are clustered by optimizing a compactness-based criterion. The advantages of the method over related approaches are threefold: (i) robustness properties of compactness-based criteria naturally transfer to the problem of extracting elongated struc- tures, leading to a model which is highly robust against outlier objects; (ii) the transformed distances induce a Mercer kernel which allows us to formulate a polynomial approximation scheme to the generally NP- hard clustering problem; (iii) the new method does not contain free kernel parameters in contrast to methods like spectral clustering or mean-shift clustering.
Attractive People: Assembling Loose-Limbed Models using Non-parametric Belief Propagation
Authors: Leonid Sigal, Michael Isard, Benjamin H. Sigelman, Michael J. Black
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: The detection and pose estimation of people in images and video is made challenging by the variability of human appearance, the complexity of natural scenes, and the high dimensionality of articulated body mod- els. To cope with these problems we represent the 3D human body as a graphical model in which the relationships between the body parts are represented by conditional probability distributions. We formulate the pose estimation problem as one of probabilistic inference over a graphi- cal model where the random variables correspond to the individual limb parameters (position and orientation). Because the limbs are described by 6-dimensional vectors encoding pose in 3-space, discretization is im- practical and the random variables in our model must be continuous- valued. To approximate belief propagation in such a graph we exploit a recently introduced generalization of the particle ﬁlter. This framework facilitates the automatic initialization of the body-model from low level cues and is robust to occlusion of body parts and scene clutter.
Out-of-Sample Extensions for LLE, Isomap, MDS, Eigenmaps, and Spectral Clustering
Authors: Yoshua Bengio, Jean-françcois Paiement, Pascal Vincent, Olivier Delalleau, Nicolas L. Roux, Marie Ouimet
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Several unsupervised learning algorithms based on an eigendecompo- sition provide either an embedding or a clustering only for given train- ing points, with no straightforward extension for out-of-sample examples short of recomputing eigenvectors. This paper provides a uniﬁed frame- work for extending Local Linear Embedding (LLE), Isomap, Laplacian Eigenmaps, Multi-Dimensional Scaling (for dimensionality reduction) as well as for Spectral Clustering. This framework is based on seeing these algorithms as learning eigenfunctions of a data-dependent kernel. Numerical experiments show that the generalizations performed have a level of error comparable to the variability of the embedding algorithms due to the choice of training data.
Learning Spectral Clustering
Authors: Francis R. Bach, Michael I. Jordan
Published in: Advances in Neural Information Processing Systems 16  (NIPS 2003) (Main Conference Track), 2003

Abstract: Spectral clustering refers to a class of techniques which rely on the eigen- structure of a similarity matrix to partition points into disjoint clusters with points in the same cluster having high similarity and points in dif- ferent clusters having low similarity. In this paper, we derive a new cost function for spectral clustering based on a measure of error between a given partition and a solution of the spectral relaxation of a minimum normalized cut problem. Minimizing this cost function with respect to the partition leads to a new spectral clustering algorithm. Minimizing with respect to the similarity matrix leads to an algorithm for learning the similarity matrix. We develop a tractable approximation of our cost function that is based on the power method of computing eigenvectors.