mtybilly/Instruct2DS huggingface dataset:
The Rescorla-Wagner Algorithm and Maximum Likelihood Estimation of Causal Parameters
Authors: Alan L. Yuille
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: This paper analyzes generalization of the classic Rescorla-Wagner (R-          W) learning algorithm and studies their relationship to Maximum Like-          lihood estimation of causal parameters. We prove that the parameters          of two popular causal models, P and P C, can be learnt by the same          generalized linear Rescorla-Wagner (GLRW) algorithm provided gener-          icity conditions apply. We characterize the fixed points of these GLRW          algorithms and calculate the fluctuations about them, assuming that the          input is a set of i.i.d. samples from a fixed (unknown) distribution. We          describe how to determine convergence conditions and calculate conver-          gence rates for the GLRW algorithms under these conditions.
An Auditory Paradigm for Brain-Computer Interfaces
Authors: Thomas N. Lal, Karin Bierig, Niels Birbaumer, Bernhard Schölkopf N. J. Hill
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Motivated by the particular problems involved in communicating         with "locked-in" paralysed patients, we aim to develop a brain-         computer interface that uses auditory stimuli.            We describe a         paradigm that allows a user to make a binary decision by focusing         attention on one of two concurrent auditory stimulus sequences.         Using Support Vector Machine classification and Recursive Chan-         nel Elimination on the independent components of averaged event-         related potentials, we show that an untrained user's EEG data can         be classified with an encouragingly high level of accuracy. This         suggests that it is possible for users to modulate EEG signals in a         single trial by the conscious direction of attention, well enough to         be useful in BCI.
Worst-Case Analysis of Selective Sampling for Linear-Threshold Algorithms
Authors: Claudio Gentile, Luca Zaniboni Nicolò Cesa-bianchi
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We provide a worst-case analysis of selective sampling algorithms for learning linear threshold functions. The algorithms considered in this paper are Perceptron-like algorithms, i.e., algorithms which can be efﬁ- ciently run in any reproducing kernel Hilbert space. Our algorithms ex- ploit a simple margin-based randomized rule to decide whether to query the current label. We obtain selective sampling algorithms achieving on average the same bounds as those proven for their deterministic coun- terparts, but using much fewer labels. We complement our theoretical ﬁndings with an empirical comparison on two text categorization tasks. The outcome of these experiments is largely predicted by our theoreti- cal results: Our selective sampling algorithms tend to perform as good as the algorithms receiving the true label after each classiﬁcation, while observing in practice substantially fewer labels.
Co-Validation: Using Model Disagreement on Unlabeled Data to Validate Classification Algorithms
Authors: David M. Pennock, Gary W. Flake Omid Madani
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: In the context of binary classification, we define disagreement as a mea-          sure of how often two independently-trained models differ in their clas-          sification of unlabeled data. We explore the use of disagreement for error          estimation and model selection. We call the procedure co-validation,          since the two models effectively (in)validate one another by comparing          results on unlabeled data, which we assume is relatively cheap and plen-          tiful compared to labeled data. We show that per-instance disagreement          is an unbiased estimate of the variance of error for that instance. We also          show that disagreement provides a lower bound on the prediction (gen-          eralization) error, and a tight upper bound on the "variance of prediction          error", or the variance of the average error across instances, where vari-          ance is measured across training sets. We present experimental results on          several data sets exploring co-validation for error estimation and model          selection. The procedure is especially effective in active learning set-          tings, where training sets are not drawn at random and cross validation          overestimates error.
Message Errors in Belief Propagation
Authors: John W. Fisher, Alan S. Willsky Alexander T. Ihler
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Belief propagation (BP) is an increasingly popular method of perform-          ing approximate inference on arbitrary graphical models.          At times,          even further approximations are required, whether from quantization or          other simplified message representations or from stochastic approxima-          tion methods. Introducing such errors into the BP message computations          has the potential to adversely affect the solution obtained. We analyze          this effect with respect to a particular measure of message error, and show          bounds on the accumulation of errors in the system. This leads both to          convergence conditions and error bounds in traditional and approximate          BP message passing.
Methods Towards Invasive Human Brain Computer Interfaces
Authors: Thilo Hinterberger, Guido Widman, Michael Schröder, N. J. Hill, Wolfgang Rosenstiel, Christian E. Elger, Niels Birbaumer, Bernhard Schölkopf Thomas N. Lal
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: During the last ten years there has been growing interest in the develop-          ment of Brain Computer Interfaces (BCIs). The field has mainly been          driven by the needs of completely paralyzed patients to communicate.          With a few exceptions, most human BCIs are based on extracranial elec-          troencephalography (EEG). However, reported bit rates are still low. One          reason for this is the low signal-to-noise ratio of the EEG [16]. We are          currently investigating if BCIs based on electrocorticography (ECoG) are          a viable alternative. In this paper we present the method and examples          of intracranial EEG recordings of three epilepsy patients with electrode          grids placed on the motor cortex. The patients were asked to repeat-          edly imagine movements of two kinds, e.g., tongue or finger movements.          We analyze the classifiability of the data using Support Vector Machines          (SVMs) [18, 21] and Recursive Channel Elimination (RCE) [11].
A Three Tiered Approach for Articulated Object Action Modeling and Recognition
Authors: Gregory D. Hager, Laurent Younes Le Lu
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Visual action recognition is an important problem in computer vision.          In this paper, we propose a new method to probabilistically model and          recognize actions of articulated objects, such as hand or body gestures,          in image sequences. Our method consists of three levels of representa-          tion. At the low level, we first extract a feature vector invariant to scale          and in-plane rotation by using the Fourier transform of a circular spatial          histogram. Then, spectral partitioning [20] is utilized to obtain an initial          clustering; this clustering is then refined using a temporal smoothness          constraint. Gaussian mixture model (GMM) based clustering and density          estimation in the subspace of linear discriminant analysis (LDA) are then          applied to thousands of image feature vectors to obtain an intermediate          level representation. Finally, at the high level we build a temporal multi-          resolution histogram model for each action by aggregating the clustering          weights of sampled images belonging to that action. We discuss how this          high level representation can be extended to achieve temporal scaling in-          variance and to include Bi-gram or Multi-gram transition information.          Both image clustering and action recognition/segmentation results are          given to show the validity of our three tiered representation.
Generalization Error and Algorithmic Convergence of Median Boosting
Authors: Balázs Kégl
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We have recently proposed an extension of ADABOOST to regression           that uses the median of the base regressors as the final regressor. In this           paper we extend theoretical results obtained for ADABOOST to median           boosting and to its localized variant. First, we extend recent results on ef-           ficient margin maximizing to show that the algorithm can converge to the           maximum achievable margin within a preset precision in a finite number           of steps. Then we provide confidence-interval-type bounds on the gener-           alization error.
Supervised Graph Inference
Authors: Yoshihiro Yamanishi Jean-philippe Vert
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We formulate the problem of graph inference where part of the graph is           known as a supervised learning problem, and propose an algorithm to           solve it. The method involves the learning of a mapping of the vertices           to a Euclidean space where the graph is easy to infer, and can be formu-           lated as an optimization problem in a reproducing kernel Hilbert space.           We report encouraging results on the problem of metabolic network re-           construction from genomic data.
Confidence Intervals for the Area Under the ROC Curve
Authors: Mehryar Mohri Corinna Cortes
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: In many applications, good ranking is a highly desirable performance for          a classifier. The criterion commonly used to measure the ranking quality          of a classification algorithm is the area under the ROC curve (AUC). To          report it properly, it is crucial to determine an interval of confidence for          its value. This paper provides confidence intervals for the AUC based          on a statistical and combinatorial analysis using only simple parameters          such as the error rate and the number of positive and negative examples.          The analysis is distribution-independent, it makes no assumption about          the distribution of the scores of negative or positive examples. The results          are of practical use and can be viewed as the equivalent for AUC of the          standard confidence intervals given in the case of the error rate. They          are compared with previous approaches in several standard classification          tasks demonstrating the benefits of our analysis.
Maximising Sensitivity in a Spiking Network
Authors: Lucas C. Parra Anthony J. Bell
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We use unsupervised probabilistic machine learning ideas to try to ex- plain the kinds of learning observed in real neurons, the goal being to connect abstract principles of self-organisation to known biophysi- cal processes. For example, we would like to explain Spike Timing- Dependent Plasticity (see [5,6] and Figure 3A), in terms of information theory. Starting out, we explore the optimisation of a network sensitiv- ity measure related to maximising the mutual information between input spike timings and output spike timings. Our derivations are analogous to those in ICA, except that the sensitivity of output timings to input tim- ings is maximised, rather than the sensitivity of output ‘ﬁring rates’ to inputs. ICA and related approaches have been successful in explaining the learning of many properties of early visual receptive ﬁelds in rate cod- ing models, and we are hoping for similar gains in understanding of spike coding in networks, and how this is supported, in principled probabilistic ways, by cellular biophysical processes. For now, in our initial simula- tions, we show that our derived rule can learn synaptic weights which can unmix, or demultiplex, mixed spike trains. That is, it can recover inde- pendent point processes embedded in distributed correlated input spike trains, using an adaptive single-layer feedforward spiking network.
1 Maximising Sensitivity.
In this section, we will follow the structure of the ICA derivation [4] in developing the spiking theory. We cannot claim, as before, that this gives us an information maximisation algorithm, for reasons that we will delay addressing until Section 3. But for now, to ﬁrst develop our approach, we will explore an interim objective function called sensitivity which we deﬁne as the log Jacobian of how input spike timings affect output spike timings.
1.1 How to maximise the effect of one spike timing on another.
Consider a spike in neuron j at time tl that has an effect on the timing of another spike in neuron i at time tk. The neurons are connected by a weight wij. We use i and j to index neurons, and k and l to index spikes, but sometimes for convenience we will use spike indices in place of neuron indices. For example, wkl, the weight between an input spike l and an output spike k, is naturally understood to be just the corresponding wij.
Theory of localized synfire chain: characteristic propagation speed of stable spike pattern
Authors: Masato Okada, Kazuyuki Aihara Kosuke Hamaguchi
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Repeated spike patterns have often been taken as evidence for the synfire          chain, a phenomenon that a stable spike synchrony propagates through          a feedforward network. Inter-spike intervals which represent a repeated          spike pattern are influenced by the propagation speed of a spike packet.          However, the relation between the propagation speed and network struc-          ture is not well understood. While it is apparent that the propagation          speed depends on the excitatory synapse strength, it might also be related          to spike patterns. We analyze a feedforward network with Mexican-Hat-          type connectivity (FMH) using the Fokker-Planck equation. We show          that both a uniform and a localized spike packet are stable in the FMH          in a certain parameter region. We also demonstrate that the propagation          speed depends on the distinct firing patterns in the same network.
Semi-supervised Learning on Directed Graphs
Authors: Thomas Hofmann, Bernhard Schölkopf Dengyong Zhou
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Given a directed graph in which some of the nodes are labeled, we inves- tigate the question of how to exploit the link structure of the graph to infer the labels of the remaining unlabeled nodes. To that extent we propose a regularization framework for functions de(cid:2)ned over nodes of a directed graph that forces the classi(cid:2)cation function to change slowly on densely linked subgraphs. A powerful, yet computationally simple classi(cid:2)cation algorithm is derived within the proposed framework. The experimental evaluation on real-world Web classi(cid:2)cation problems demonstrates en- couraging results that validate our approach.
Class-size Independent Generalization Analsysis of Some Discriminative Multi-Category Classification
Authors: Tong Zhang
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We consider the problem of deriving class-size independent generaliza-          tion bounds for some regularized discriminative multi-category classi-          fication methods. In particular, we obtain an expected generalization          bound for a standard formulation of multi-category support vector ma-          chines.    Based on the theoretical result, we argue that the formula-          tion over-penalizes misclassification error, which in theory may lead to          poor generalization performance. A remedy, based on a generalization          of multi-category logistic regression (conditional maximum entropy), is          then proposed, and its theoretical properties are examined.
ℓ₀-norm Minimization for Basis Selection
Authors: Bhaskar D. Rao David P. Wipf
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Finding the sparsest, or minimum ℓ0-norm, representation of a signal given an overcomplete dictionary of basis vectors is an important prob- lem in many application domains. Unfortunately, the required optimiza- tion problem is often intractable because there is a combinatorial increase in the number of local minima as the number of candidate basis vectors increases. This deﬁciency has prompted most researchers to instead min- imize surrogate measures, such as the ℓ1-norm, that lead to more tractable computational methods. The downside of this procedure is that we have now introduced a mismatch between our ultimate goal and our objective function. In this paper, we demonstrate a sparse Bayesian learning-based method of minimizing the ℓ0-norm while reducing the number of trou- blesome local minima. Moreover, we derive necessary conditions for local minima to occur via this approach and empirically demonstrate that there are typically many fewer for general problems of interest.
The Power of Selective Memory: Self-Bounded Learning of Prediction Suffix Trees
Authors: Shai Shalev-shwartz, Yoram Singer Ofer Dekel
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Prediction suffix trees (PST) provide a popular and effective tool for tasks          such as compression, classification, and language modeling. In this pa-          per we take a decision theoretic view of PSTs for the task of sequence          prediction. Generalizing the notion of margin to PSTs, we present an on-          line PST learning algorithm and derive a loss bound for it. The depth of          the PST generated by this algorithm scales linearly with the length of the          input. We then describe a self-bounded enhancement of our learning al-          gorithm which automatically grows a bounded-depth PST. We also prove          an analogous mistake-bound for the self-bounded algorithm. The result          is an efficient algorithm that neither relies on a-priori assumptions on the          shape or maximal depth of the target PST nor does it require any param-          eters. To our knowledge, this is the first provably-correct PST learning          algorithm which generates a bounded-depth PST while being competi-          tive with any fixed PST determined in hindsight.
Harmonising Chorales by Probabilistic Inference
Authors: Christopher Williams Moray Allan
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We describe how we used a data set of chorale harmonisations composed          by Johann Sebastian Bach to train Hidden Markov Models. Using a prob-          abilistic framework allows us to create a harmonisation system which          learns from examples, and which can compose new harmonisations. We          make a quantitative comparison of our system's harmonisation perfor-          mance against simpler models, and provide example harmonisations.
Mistake Bounds for Maximum Entropy Discrimination
Authors: Xinyu Wu Philip M. Long
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We establish a mistake bound for an ensemble method for classification          based on maximizing the entropy of voting weights subject to margin          constraints. The bound is the same as a general bound proved for the          Weighted Majority Algorithm, and similar to bounds for other variants          of Winnow. We prove a more refined bound that leads to a nearly opti-          mal algorithm for learning disjunctions, again, based on the maximum          entropy principle. We describe a simplification of the on-line maximum          entropy method in which, after each iteration, the margin constraints are          replaced with a single linear inequality. The simplified algorithm, which          takes a similar form to Winnow, achieves the same mistake bounds.
A Harmonic Excitation State-Space Approach to Blind Separation of Speech
Authors: Lars K. Hansen Rasmus K. Olsson
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We discuss an identiﬁcation framework for noisy speech mixtures. A
block-based generative model is formulated that explicitly incorporates
the time-varying harmonic plus noise (H+N) model for a number of latent
sources observed through noisy convolutive mixtures. All parameters
including the pitches of the source signals, the amplitudes and phases of
the sources, the mixing ﬁlters and the noise statistics are estimated by
maximum likelihood, using an EM-algorithm. Exact averaging over the
hidden sources is obtained using the Kalman smoother. We show that
pitch estimation and source separation can be performed simultaneously.
The pitch estimates are compared to laryngograph (EGG) measurements.
Artiﬁcial and real room mixtures are used to demonstrate the viability
of the approach. Intelligible speech signals are re-synthesized from the
estimated H+N models.
Blind One-microphone Speech Separation: A Spectral Learning Approach
Authors: Michael I. Jordan Francis R. Bach
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We present an algorithm to perform blind, one-microphone speech sep-          aration. Our algorithm separates mixtures of speech without modeling          individual speakers. Instead, we formulate the problem of speech sep-          aration as a problem in segmenting the spectrogram of the signal into          two or more disjoint sets. We build feature sets for our segmenter using          classical cues from speech psychophysics. We then combine these fea-          tures into parameterized affinity matrices. We also take advantage of the          fact that we can generate training examples for segmentation by artifi-          cially superposing separately-recorded signals. Thus the parameters of          the affinity matrices can be tuned using recent work on learning spectral          clustering [1]. This yields an adaptive, speech-specific segmentation al-          gorithm that can successfully separate one-microphone speech mixtures.
Resolving Perceptual Aliasing In The Presence Of Noisy Sensors
Authors: Ronen I. Brafman Guy Shani
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Agents learning to act in a partially observable domain may need to          overcome the problem of perceptual aliasing  i.e., different states that          appear similar but require different responses. This problem is exacer-          bated when the agent's sensors are noisy, i.e., sensors may produce dif-          ferent observations in the same state. We show that many well-known          reinforcement learning methods designed to deal with perceptual alias-          ing, such as Utile Suffix Memory, finite size history windows, eligibility          traces, and memory bits, do not handle noisy sensors well. We suggest          a new algorithm, Noisy Utile Suffix Memory (NUSM), based on USM,          that uses a weighted classification of observed trajectories. We compare          NUSM to the above methods and show it to be more robust to noise.
Kernels for Multi--task Learning
Authors: Massimiliano Pontil Charles A. Micchelli
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: This paper provides a foundation for multitask learning using reproducing ker-          nel Hilbert spaces of vectorvalued functions. In this setting, the kernel is a          matrixvalued function. Some explicit examples will be described which go be-          yond our earlier results in [7]. In particular, we characterize classes of matrix          valued kernels which are linear and are of the dot product or the translation invari-          ant type. We discuss how these kernels can be used to model relations between          the tasks and present linear multitask learning algorithms. Finally, we present a          novel proof of the representer theorem for a minimizer of a regularization func-          tional which is based on the notion of minimal norm interpolation.
Variational Minimax Estimation of Discrete Distributions under KL Loss
Authors: Liam Paninski
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We develop a family of upper and lower bounds on the worst-case ex-          pected KL loss for estimating a discrete distribution on a finite number m          of points, given N i.i.d. samples. Our upper bounds are approximation-          theoretic, similar to recent bounds for estimating discrete entropy; the          lower bounds are Bayesian, based on averages of the KL loss under          Dirichlet distributions. The upper bounds are convex in their parameters          and thus can be minimized by descent methods to provide estimators with          low worst-case error; the lower bounds are indexed by a one-dimensional          parameter and are thus easily maximized. Asymptotic analysis of the          bounds demonstrates the uniform KL-consistency of a wide class of es-          timators as c = N/m   (no matter how slowly), and shows that          no estimator is consistent for c bounded (in contrast to entropy estima-          tion). Moreover, the bounds are asymptotically tight as c  0 or ,          and are shown numerically to be tight within a factor of two for all c.          Finally, in the sparse-data limit c  0, we find that the Dirichlet-Bayes          (add-constant) estimator with parameter scaling like -c log(c) optimizes          both the upper and lower bounds, suggesting an optimal choice of the          "add-constant" parameter in this regime.
Online Bounds for Bayesian Algorithms
Authors: Andrew Y. Ng Sham M. Kakade
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We present a competitive analysis of Bayesian learning algorithms in the online learning setting and show that many simple Bayesian algorithms (such as Gaussian linear regression and Bayesian logistic regression) per- form favorably when compared, in retrospect, to the single best model in the model class. The analysis does not assume that the Bayesian algo- rithms’ modeling assumptions are “correct,” and our bounds hold even if the data is adversarially chosen. For Gaussian linear regression (us- ing logloss), our error bounds are comparable to the best bounds in the online learning literature, and we also provide a lower bound showing that Gaussian linear regression is optimal in a certain worst case sense. We also give bounds for some widely used maximum a posteriori (MAP) estimation algorithms, including regularized logistic regression.
Analysis of a greedy active learning strategy
Authors: Sanjoy Dasgupta
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We abstract out the core search problem of active learning schemes, to          better understand the extent to which adaptive labeling can improve sam-          ple complexity. We give various upper and lower bounds on the number          of labels which need to be queried, and we prove that a popular greedy          active learning rule is approximately as good as any other strategy for          minimizing this number of labels.
Computing regularization paths for learning multiple kernels
Authors: Romain Thibaux, Michael I. Jordan Francis R. Bach
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: The problem of learning a sparse conic combination of kernel functions          or kernel matrices for classification or regression can be achieved via the          regularization by a block 1-norm [1]. In this paper, we present an al-          gorithm that computes the entire regularization path for these problems.          The path is obtained by using numerical continuation techniques, and          involves a running time complexity that is a constant times the complex-          ity of solving the problem for one value of the regularization parameter.          Working in the setting of kernel linear regression and kernel logistic re-          gression, we show empirically that the effect of the block 1-norm reg-          ularization differs notably from the (non-block) 1-norm regularization          commonly used for variable selection, and that the regularization path is          of particular value in the block case.
Saliency-Driven Image Acuity Modulation on a Reconfigurable Array of Spiking Silicon Neurons
Authors: Udayan Mallik, Eugenio Culurciello, Gert Cauwenberghs, Ralph Etienne-Cummings R. J. Vogelstein
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We have constructed a system that uses an array of 9,600 spiking sili- con neurons, a fast microcontroller, and digital memory, to implement a reconﬁgurable network of integrate-and-ﬁre neurons. The system is designed for rapid prototyping of spiking neural networks that require high-throughput communication with external address-event hardware. Arbitrary network topologies can be implemented by selectively rout- ing address-events to speciﬁc internal or external targets according to a memory-based projective ﬁeld mapping. The utility and versatility of the system is demonstrated by conﬁguring it as a three-stage network that accepts input from an address-event imager, detects salient regions of the image, and performs spatial acuity modulation around a high-resolution fovea that is centered on the location of highest salience.
Brain Inspired Reinforcement Learning
Authors: Yoshua Bengio, John Kalaska Françcois Rivest
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Successful application of reinforcement learning algorithms often  involves considerable hand-crafting of the necessary non-linear  features to reduce the complexity of the value functions and hence  to promote convergence of the algorithm. In contrast, the human  brain readily and autonomously finds the complex features when  provided with sufficient training. Recent work in machine learning  and neurophysiology has demonstrated the role of the basal ganglia  and the frontal cortex in mammalian reinforcement learning. This  paper develops and explores new  learning  algorithms  that provides  potential new approaches to the feature construction problem. The  algorithms are compared and evaluated on the Acrobot task. 
inspired by neurological evidence
Semi-supervised Learning via Gaussian Processes
Authors: Michael I. Jordan Neil D. Lawrence
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We present a probabilistic approach to learning a Gaussian Process         classifier in the presence of unlabeled data. Our approach involves         a "null category noise model" (NCNM) inspired by ordered cate-         gorical noise models. The noise model reflects an assumption that         the data density is lower between the class-conditional densities.         We illustrate our approach on a toy problem and present compar-         ative results for the semi-supervised classification of handwritten         digits.
Parallel Support Vector Machines: The Cascade SVM
Authors: Eric Cosatto, Léon Bottou, Igor Dourdanovic, Vladimir Vapnik Hans P. Graf
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We describe an algorithm for support vector machines (SVM) that  can be parallelized efficiently and scales to very large problems with  hundreds of thousands of training vectors. Instead of analyzing the  whole training set in one optimization step, the data are split into  subsets and optimized separately with multiple SVMs. The partial  results are combined and filtered again in a ‘Cascade’ of SVMs, until  the global optimum is reached. The Cascade SVM can be spread over  multiple processors with minimal communication overhead and  requires far less memory, since the kernel matrices are much smaller  than for a regular SVM. Convergence to the global optimum is  guaranteed with multiple passes through the Cascade, but already a  single pass provides good generalization. A single pass is 5x – 10x  faster than a regular SVM for problems of 100,000 vectors when  implemented on a single processor. Parallel implementations on a  cluster of 16 processors were tested with over 1 million vectors  (2-class problems), converging in a day or two, while a regular SVM  never converged in over a week.
Sampling Methods for Unsupervised Learning
Authors: Andrew Zisserman, Pietro Perona Rob Fergus
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We present an algorithm to overcome the local maxima problem in es-
           timating the parameters of mixture models. It combines existing ap-
           proaches from both EM and a robust fitting algorithm, RANSAC, to give
           a data-driven stochastic learning scheme. Minimal subsets of data points,
           sufficient to constrain the parameters of the model, are drawn from pro-
           posal densities to discover new regions of high likelihood. The proposal
           densities are learnt using EM and bias the sampling toward promising
           solutions. The algorithm is computationally efficient, as well as effective
           at escaping from local maxima. We compare it with alternative methods,
           including EM and RANSAC, on both challenging synthetic data and the
           computer vision problem of alpha-matting.
Limits of Spectral Clustering
Authors: Olivier Bousquet, Mikhail Belkin Ulrike V. Luxburg
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: An important aspect of clustering algorithms is whether the partitions          constructed on finite samples converge to a useful clustering of the whole          data space as the sample size increases. This paper investigates this          question for normalized and unnormalized versions of the popular spec-          tral clustering algorithm. Surprisingly, the convergence of unnormalized          spectral clustering is more difficult to handle than the normalized case.          Even though recently some first results on the convergence of normal-          ized spectral clustering have been obtained, for the unnormalized case          we have to develop a completely new approach combining tools from          numerical integration, spectral and perturbation theory, and probability.          It turns out that while in the normalized case, spectral clustering usually          converges to a nice partition of the data space, in the unnormalized case          the same only holds under strong additional assumptions which are not          always satisfied. We conclude that our analysis gives strong evidence for          the superiority of normalized spectral clustering. It also provides a basis          for future exploration of other Laplacian-based methods.
Newscast EM
Authors: Nikos Vlassis Wojtek Kowalczyk
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We propose a gossip-based distributed algorithm for Gaussian mixture learning, Newscast EM. The algorithm operates on network topologies where each node observes a local quantity and can communicate with other nodes in an arbitrary point-to-point fashion. The main difference between Newscast EM and the standard EM algorithm is that the M-step in our case is implemented in a decentralized manner: (random) pairs of nodes repeatedly exchange their local parameter estimates and com- bine them by (weighted) averaging. We provide theoretical evidence and demonstrate experimentally that, under this protocol, nodes converge ex- ponentially fast to the correct estimates in each M-step of the EM algo- rithm.
Dynamic Bayesian Networks for Brain-Computer Interfaces
Authors: Rajesh P. Rao Pradeep Shenoy
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We describe an approach to building brain-computer interfaces (BCI)          based on graphical models for probabilistic inference and learning. We          show how a dynamic Bayesian network (DBN) can be used to infer          probability distributions over brain- and body-states during planning and          execution of actions. The DBN is learned directly from observed data          and allows measured signals such as EEG and EMG to be interpreted in          terms of internal states such as intent to move, preparatory activity, and          movement execution. Unlike traditional classification-based approaches          to BCI, the proposed approach (1) allows continuous tracking and predic-          tion of internal states over time, and (2) generates control signals based          on an entire probability distribution over states rather than binary yes/no          decisions. We present preliminary results of brain- and body-state es-          timation using simultaneous EEG and EMG signals recorded during a          self-paced left/right hand movement task.
Edge of Chaos Computation in Mixed-Mode VLSI - A Hard Liquid
Authors: Karlheinz Meier, Johannes Schemmel Felix Schürmann
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Computation without stable states is a computing paradigm dif-         ferent from Turing's and has been demonstrated for various types         of simulated neural networks. This publication transfers this to a         hardware implemented neural network. Results of a software im-         plementation are reproduced showing that the performance peaks         when the network exhibits dynamics at the edge of chaos. The         liquid computing approach seems well suited for operating analog         computing devices such as the used VLSI neural network.
Breaking SVM Complexity with Cross-Training
Authors: Jason Weston, Gökhan H. Bakir Léon Bottou
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We propose to selectively remove examples from the training set using probabilistic estimates related to editing algorithms (Devijver and Kittler, 1982). This heuristic procedure aims at creating a separable distribution of training examples with minimal impact on the position of the decision boundary. It breaks the linear dependency between the number of SVs and the number of training examples, and sharply reduces the complexity of SVMs during both the training and prediction stages.
Proximity Graphs for Clustering and Manifold Learning
Authors: Miguel Á. Carreira-Perpiñán Richard S. Zemel
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Many machine learning algorithms for clustering or dimensionality re- duction take as input a cloud of points in Euclidean space, and construct a graph with the input data points as vertices. This graph is then parti- tioned (clustering) or used to redeﬁne metric information (dimensional- ity reduction). There has been much recent work on new methods for graph-based clustering and dimensionality reduction, but not much on constructing the graph itself. Graphs typically used include the fully- connected graph, a local ﬁxed-grid graph (for image segmentation) or a nearest-neighbor graph. We suggest that the graph should adapt locally to the structure of the data. This can be achieved by a graph ensemble that combines multiple minimum spanning trees, each ﬁt to a perturbed version of the data set. We show that such a graph ensemble usually pro- duces a better representation of the data manifold than standard methods; and that it provides robustness to a subsequent clustering or dimension- ality reduction algorithm based on the graph.
Fast Rates to Bayes for Kernel Machines
Authors: Clint Scovel Ingo Steinwart
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We establish learning rates to the Bayes risk for support vector machines          (SVMs) with hinge loss. In particular, for SVMs with Gaussian RBF          kernels we propose a geometric condition for distributions which can be          used to determine approximation properties of these kernels. Finally, we          compare our methods with a recent paper of G. Blanchard et al..
Discriminant Saliency for Visual Recognition from Cluttered Scenes
Authors: Nuno Vasconcelos Dashan Gao
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Saliency mechanisms play an important role when visual recognition          must be performed in cluttered scenes. We propose a computational defi-          nition of saliency that deviates from existing models by equating saliency          to discrimination. In particular, the salient attributes of a given visual          class are defined as the features that enable best discrimination between          that class and all other classes of recognition interest. It is shown that          this definition leads to saliency algorithms of low complexity, that are          scalable to large recognition problems, and is compatible with existing          models of early biological vision. Experimental results demonstrating          success in the context of challenging recognition problems are also pre-          sented.
Bayesian Regularization and Nonnegative Deconvolution for Time Delay Estimation
Authors: Daniel D. Lee Yuanqing Lin
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Bayesian Regularization and Nonnegative Deconvolution (BRAND) is          proposed for estimating time delays of acoustic signals in reverberant          environments. Sparsity of the nonnegative filter coefficients is enforced          using an L1-norm regularization. A probabilistic generative model is          used to simultaneously estimate the regularization parameters and filter          coefficients from the signal data. Iterative update rules are derived under          a Bayesian framework using the Expectation-Maximization procedure.          The resulting time delay estimation algorithm is demonstrated on noisy          acoustic data.
Maximum-Margin Matrix Factorization
Authors: Jason Rennie, Tommi S. Jaakkola Nathan Srebro
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We present a novel approach to collaborative prediction, using low-norm instead of low-rank factorizations. The approach is inspired by, and has strong connections to, large-margin linear discrimination. We show how to learn low-norm factorizations by solving a semi-deﬁnite program, and discuss generalization error bounds for them.
Real-Time Pitch Determination of One or More Voices by Nonnegative Matrix Factorization
Authors: Lawrence K. Saul Fei Sha
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: An auditory "scene", composed of overlapping acoustic sources, can be          viewed as a complex object whose constituent parts are the individual          sources. Pitch is known to be an important cue for auditory scene analy-          sis. In this paper, with the goal of building agents that operate in human          environments, we describe a real-time system to identify the presence of          one or more voices and compute their pitch. The signal processing in the          front end is based on instantaneous frequency estimation, a method for          tracking the partials of voiced speech, while the pattern-matching in the          back end is based on nonnegative matrix factorization, an unsupervised          algorithm for learning the parts of complex objects. While supporting a          framework to analyze complicated auditory scenes, our system maintains          real-time operability and state-of-the-art performance in clean speech.
Efficient Out-of-Sample Extension of Dominant-Set Clusters
Authors: Marcello Pelillo Massimiliano Pavan
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Dominant sets are a new graph-theoretic concept that has proven to          be relevant in pairwise data clustering problems, such as image seg-          mentation. They generalize the notion of a maximal clique to edge-          weighted graphs and have intriguing, non-trivial connections to continu-          ous quadratic optimization and spectral-based grouping. We address the          problem of grouping out-of-sample examples after the clustering process          has taken place. This may serve either to drastically reduce the compu-          tational burden associated to the processing of very large data sets, or          to efficiently deal with dynamic situations whereby data sets need to be          updated continually. We show that the very notion of a dominant set of-          fers a simple and efficient way of doing this. Numerical experiments on          various grouping problems show the effectiveness of the approach.
Instance-Specific Bayesian Model Averaging for Classification
Authors: Gregory F. Cooper Shyam Visweswaran
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Classification algorithms typically induce population-wide models  that are trained to perform well on average on expected future  instances. We introduce a Bayesian framework for learning  instance-specific models from data that are optimized to predict  well for a particular instance. Based on this framework, we present  a  that performs  selective model averaging over a restricted class of Bayesian  networks. On experimental evaluation, this algorithm shows  superior performance over model selection. We intend to apply  such instance-specific algorithms to improve the performance of  patient-specific predictive models induced from medical data. 
instance-specific algorithm called ISA