mtybilly/Instruct2DS huggingface dataset:
Active Learning for Anomaly and Rare-Category Detection
Authors: Dan Pelleg, Andrew W. Moore
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We introduce a novel active-learning scenario in which a user wants to          work with a learning algorithm to identify useful anomalies. These are          distinguished from the traditional statistical definition of anomalies as          outliers or merely ill-modeled points. Our distinction is that the useful-          ness of anomalies is categorized subjectively by the user. We make two          additional assumptions. First, there exist extremely few useful anoma-          lies to be hunted down within a massive dataset. Second, both useful          and useless anomalies may sometimes exist within tiny classes of similar          anomalies. The challenge is thus to identify "rare category" records in an          unlabeled noisy set with help (in the form of class labels) from a human          expert who has a small budget of datapoints that they are prepared to cat-          egorize. We propose a technique to meet this challenge, which assumes          a mixture model fit to the data, but otherwise makes no assumptions on          the particular form of the mixture components. This property promises          wide applicability in real-life scenarios and for various statistical mod-          els. We give an overview of several alternative methods, highlighting          their strengths and weaknesses, and conclude with a detailed empirical          analysis. We show that our method can quickly zoom in on an anomaly          set containing a few tens of points in a dataset of hundreds of thousands.
A Feature Selection Algorithm Based on the Global Minimization of a Generalization Error Bound
Authors: Dori Peleg, Ron Meir
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: A novel linear feature selection algorithm is presented based on the          global minimization of a data-dependent generalization error bound.          Feature selection and scaling algorithms often lead to non-convex opti-          mization problems, which in many previous approaches were addressed          through gradient descent procedures that can only guarantee convergence          to a local minimum. We propose an alternative approach, whereby the          global solution of the non-convex optimization problem is derived via          an equivalent optimization problem. Moreover, the convex optimization          task is reduced to a conic quadratic programming problem for which effi-          cient solvers are available. Highly competitive numerical results on both          artificial and real-world data sets are reported.
Semi-supervised Learning with Penalized Probabilistic Clustering
Authors: Zhengdong Lu, Todd K. Leen
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: While clustering is usually an unsupervised operation, there are circum-          stances in which we believe (with varying degrees of certainty) that items          A and B should be assigned to the same cluster, while items A and C          should not. We would like such pairwise relations to influence cluster          assignments of out-of-sample data in a manner consistent with the prior          knowledge expressed in the training set. Our starting point is proba-          bilistic clustering based on Gaussian mixture models (GMM) of the data          distribution. We express clustering preferences in the prior distribution          over assignments of data points to clusters. This prior penalizes cluster          assignments according to the degree with which they violate the prefer-          ences. We fit the model parameters with EM. Experiments on a variety          of data sets show that PPC can consistently improve clustering results.
A Direct Formulation for Sparse PCA Using Semidefinite Programming
Authors: Alexandre D'aspremont, Laurent E. Ghaoui, Michael I. Jordan, Gert R. Lanckriet
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We examine the problem of approximating, in the Frobenius-norm sense,          a positive, semidefinite symmetric matrix by a rank-one matrix, with an          upper bound on the cardinality of its eigenvector. The problem arises          in the decomposition of a covariance matrix into sparse factors, and has          wide applications ranging from biology to finance. We use a modifica-          tion of the classical variational representation of the largest eigenvalue          of a symmetric matrix, where cardinality is constrained, and derive a          semidefinite programming based relaxation for our problem.
Stable adaptive control with online learning
Authors: H. J. Kim, Andrew Y. Ng
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Learning algorithms have enjoyed numerous successes in robotic control          tasks. In problems with time-varying dynamics, online learning methods          have also proved to be a powerful tool for automatically tracking and/or          adapting to the changing circumstances. However, for safety-critical ap-          plications such as airplane flight, the adoption of these algorithms has          been significantly hampered by their lack of safety, such as "stability,"          guarantees. Rather than trying to show difficult, a priori, stability guar-          antees for specific learning methods, in this paper we propose a method          for "monitoring" the controllers suggested by the learning algorithm on-          line, and rejecting controllers leading to instability. We prove that even if          an arbitrary online learning method is used with our algorithm to control          a linear dynamical system, the resulting system is stable.
An Auditory Paradigm for Brain-Computer Interfaces
Authors: N. J. Hill, Thomas N. Lal, Karin Bierig, Niels Birbaumer, Bernhard Schölkopf
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: Nicolò Cesa-bianchi, Claudio Gentile, Luca Zaniboni
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: Omid Madani, David M. Pennock, Gary W. Flake
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: Alexander T. Ihler, John W. Fisher, Alan S. Willsky
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: Thomas N. Lal, Thilo Hinterberger, Guido Widman, Michael Schröder, N. J. Hill, Wolfgang Rosenstiel, Christian E. Elger, Niels Birbaumer, Bernhard Schölkopf
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: Le Lu, Gregory D. Hager, Laurent Younes
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.
Supervised Graph Inference
Authors: Jean-philippe Vert, Yoshihiro Yamanishi
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: Corinna Cortes, Mehryar Mohri
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: Anthony J. Bell, Lucas C. Parra
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: Kosuke Hamaguchi, Masato Okada, Kazuyuki Aihara
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: Dengyong Zhou, Thomas Hofmann, Bernhard Schölkopf
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.
ℓ₀-norm Minimization for Basis Selection
Authors: David P. Wipf, Bhaskar D. Rao
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: Ofer Dekel, Shai Shalev-shwartz, Yoram Singer
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: Moray Allan, Christopher Williams
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: Philip M. Long, Xinyu Wu
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: Rasmus K. Olsson, Lars K. Hansen
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: Francis R. Bach, Michael I. Jordan
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: Guy Shani, Ronen I. Brafman
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: Charles A. Micchelli, Massimiliano Pontil
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.
Online Bounds for Bayesian Algorithms
Authors: Sham M. Kakade, Andrew Y. Ng
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.
Computing regularization paths for learning multiple kernels
Authors: Francis R. Bach, Romain Thibaux, Michael I. Jordan
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: R. J. Vogelstein, Udayan Mallik, Eugenio Culurciello, Gert Cauwenberghs, Ralph Etienne-Cummings
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: Françcois Rivest, Yoshua Bengio, John Kalaska
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: Neil D. Lawrence, Michael I. Jordan
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: Hans P. Graf, Eric Cosatto, Léon Bottou, Igor Dourdanovic, Vladimir Vapnik
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: Rob Fergus, Andrew Zisserman, Pietro Perona
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: Ulrike V. Luxburg, Olivier Bousquet, Mikhail Belkin
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: Wojtek Kowalczyk, Nikos Vlassis
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: Pradeep Shenoy, Rajesh P. Rao
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: Felix Schürmann, Karlheinz Meier, Johannes Schemmel
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: Léon Bottou, Jason Weston, Gökhan H. Bakir
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: Richard S. Zemel, Miguel Á. Carreira-Perpiñán
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: Ingo Steinwart, Clint Scovel
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: Dashan Gao, Nuno Vasconcelos
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: Yuanqing Lin, Daniel D. Lee
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: Nathan Srebro, Jason Rennie, Tommi S. Jaakkola
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: Fei Sha, Lawrence K. Saul
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: Massimiliano Pavan, Marcello Pelillo
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.