mtybilly/Instruct2DS huggingface dataset:
Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms
Authors: Roni Khardon, Dan Roth, Rocco A. Servedio
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We study online learning in Boolean domains using kernels which cap- ture feature expansions equivalent to using conjunctions over basic fea- tures. We demonstrate a tradeoff between the computational efﬁciency with which these kernels can be computed and the generalization abil- ity of the resulting classiﬁer. We ﬁrst describe several kernel functions which capture either limited forms of conjunctions or all conjunctions. We show that these kernels can be used to efﬁciently run the Percep- tron algorithm over an exponential number of conjunctions; however we also prove that using such kernels the Perceptron algorithm can make an exponential number of mistakes even when learning simple func- tions. We also consider an analogous use of kernel functions to run the multiplicative-update Winnow algorithm over an expanded feature space of exponentially many conjunctions. While known upper bounds imply that Winnow can learn DNF formulae with a polynomial mistake bound in this setting, we prove that it is computationally hard to simulate Win- now’s behavior for learning DNF over such a feature set, and thus that such kernel functions for Winnow are not efﬁciently computable.
Prodding the ROC Curve: Constrained Optimization of Classifier Performance
Authors: Michael Mozer, Robert Dodier, Michael D. Colagrosso, Cesar Guerra-Salcedo, Richard Wolniewicz
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: When designing a two-alternative classiﬁer, one ordinarily aims to maximize the classiﬁer’s ability to discriminate between members of the two classes. We describe a situation in a real-world business application of machine-learning prediction in which an additional constraint is placed on the nature of the solu- tion: that the classiﬁer achieve a speciﬁed correct acceptance or correct rejection rate (i.e., that it achieve a ﬁxed accuracy on members of one class or the other). Our domain is predicting churn in the telecommunications industry. Churn refers to customers who switch from one service provider to another. We pro- pose four algorithms for training a classiﬁer subject to this domain constraint, and present results showing that each algorithm yields a reliable improvement in performance. Although the improvement is modest in magnitude, it is nonethe- less impressive given the difﬁculty of the problem and the ﬁnancial return that it achieves to the service provider.
When designing a classiﬁer, one must specify an objective measure by which the classi- ﬁer’s performance is to be evaluated. One simple objective measure is to minimize the number of misclassiﬁcations. If the cost of a classiﬁcation error depends on the target and/ or response class, one might utilize a risk-minimization framework to reduce the expected loss. A more general approach is to maximize the classiﬁer’s ability to discriminate one class from another class (e.g., Chang & Lippmann, 1994).
An ROC curve (Green & Swets, 1966) can be used to visualize the discriminative performance of a two-alternative classiﬁer that outputs class posteriors. To explain the ROC curve, a classiﬁer can be thought of as making a positive/negative judgement as to whether an input is a member of some class. Two different accuracy measures can be obtained from the classiﬁer: the accuracy of correctly identifying an input as a member of the class (a correct acceptance or CA), and the accuracy of correctly identifying an input as a nonmember of the class (a correct rejection or CR). To evaluate the CA and CR rates, it is necessary to pick a threshold above which the classiﬁer’s probability estimate is inter- preted as an “accept,” and below which is interpreted as a “reject”—call this the criterion. The ROC curve plots CA against CR rates for various criteria (Figure 1a). Note that as the threshold is lowered, the CA rate increases and the CR rate decreases. For a criterion of 1, the CA rate approaches 0 and the CR rate 1; for a criterion of 0, the CA rate approaches 1
Natural Language Grammar Induction Using a Constituent-Context Model
Authors: Dan Klein, Christopher D. Manning
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: This paper presents a novel approach to the unsupervised learning of syn- tactic analyses of natural language text. Most previous work has focused on maximizing likelihood according to generative PCFG models. In con- trast, we employ a simpler probabilistic model over trees based directly on constituent identity and linear context, and use an EM-like iterative procedure to induce structure. This method produces much higher qual- ity analyses, giving the best published results on the ATIS dataset. 1 Overview
To enable a wide range of subsequent tasks, human language sentences are standardly given tree-structure analyses, wherein the nodes in a tree dominate contiguous spans of words called constituents, as in figure 1(a). Constituents are the linguistically coherent units in the sentence, and are usually labeled with a constituent category, such as noun phrase (NP) or verb phrase (VP). An aim of grammar induction systems is to figure out, given just the sentences in a corpus S, what tree structures correspond to them. In this sense, the grammar induction problem is an incomplete data problem, where the complete data is the corpus of trees T , but we only observe their yields S. This paper presents a new approach to this problem, which gains leverage by directly making use of constituent contexts. It is an open problem whether entirely unsupervised methods can produce linguistically accurate parses of sentences. Due to the difficulty of this task, the vast majority of statis- tical parsing work has focused on supervised learning approaches to parsing, where one uses a treebank of fully parsed sentences to induce a model which parses unseen sentences [7, 3]. But there are compelling motivations for unsupervised grammar induction. Building supervised training data requires considerable resources, including time and linguistic ex- pertise. Investigating unsupervised methods can shed light on linguistic phenomena which are implicit within a supervised parser's supervisory information (e.g., unsupervised sys- tems often have difficulty correctly attaching subjects to verbs above objects, whereas for a supervised parser, this ordering is implicit in the supervisory information). Finally, while the presented system makes no claims to modeling human language acquisition, results on whether there is enough information in sentences to recover their structure are important data for linguistic theory, where it has standardly been assumed that the information in the data is deficient, and strong innate knowledge is required for language acquisition [4].
Estimating Car Insurance Premia: a Case Study in High-Dimensional Data Inference
Authors: Nicolas Chapados, Yoshua Bengio, Pascal Vincent, Joumana Ghosn, Charles Dugas, Ichiro Takeuchi, Linyan Meng
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Estimating insurance premia from data is a difficult regression problem for several reasons: the large number of variables, many of which are .discrete, and the very peculiar shape of the noise distri(cid:173) bution, asymmetric with fat tails, with a large majority zeros and a few unreliable and very large values. We compare several machine learning methods for estimating insurance premia, and test them on a large data base of car insurance policies. We find that func(cid:173) tion approximation methods that do not optimize a squared loss, like Support Vector Machines regression, do not work well in this context. Compared methods include decision trees and generalized linear models. The best results are obtained with a mixture of experts, which better identifies the least and most risky contracts, and allows to reduce the median premium by charging more to the most risky customers.
Classifying Single Trial EEG: Towards Brain Computer Interfacing
Authors: Benjamin Blankertz, Gabriel Curio, Klaus-Robert Müller
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Driven by the progress in the ﬁeld of single-trial analysis of EEG, there is a growing interest in brain computer interfaces (BCIs), i.e., systems that enable human subjects to control a computer only by means of their brain signals. In a pseudo-online simulation our BCI detects upcoming ﬁnger movements in a natural keyboard typing condition and predicts their lat- erality. This can be done on average 100–230 ms before the respective key is actually pressed, i.e., long before the onset of EMG. Our approach is appealing for its short response time and high classiﬁcation accuracy (>96%) in a binary decision where no human training is involved. We compare discriminative classiﬁers like Support Vector Machines (SVMs) and different variants of Fisher Discriminant that possess favorable reg- ularization properties for dealing with high noise cases (inter-trial vari- ablity).
Kernel Logistic Regression and the Import Vector Machine
Authors: Ji Zhu, Trevor Hastie
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: The support vector machine (SVM) is known for its good performance in binary classiﬁcation, but its extension to multi-class classiﬁcation is still an on-going research issue. In this paper, we propose a new approach for classiﬁcation, called the import vector machine (IVM), which is built on kernel logistic regression (KLR). We show that the IVM not only per- forms as well as the SVM in binary classiﬁcation, but also can naturally be generalized to the multi-class case. Furthermore, the IVM provides an estimate of the underlying probability. Similar to the “support points” of the SVM, the IVM model uses only a fraction of the training data to index kernel basis functions, typically a much smaller fraction than the SVM. This gives the IVM a computational advantage over the SVM, especially when the size of the training data set is large.
is qualitative and assumes values in a ﬁnite set 
  , where the output  from 
. We , to it. Usually it is assumed that the training data are an independently and identically distributed sample from an unknown probability distribution
A Model of the Phonological Loop: Generalization and Binding
Authors: Randall C. O'Reilly, R. Soto
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We present a  neural network model that shows how the prefrontal  cortex, interacting with the basal ganglia, can maintain a sequence  of  phonological  information  in  activation-based  working  memory  (i.e.,  the  phonological  loop).  The  primary function  of this  phono(cid:173) logical  loop  may  be  to  transiently  encode  arbitrary  bindings  of  information  necessary  for  tasks  - the  combinatorial  expressive  power  of language  enables  very  flexible  binding  of essentially  ar(cid:173) bitrary  pieces  of information.  Our  model  takes  advantage  of the  closed-class nature of phonemes, which allows  different  neural rep(cid:173) resentations of all possible phonemes at each sequential position to  be encoded.  To  make this work,  we  suggest that the basal ganglia  provide a  region-specific update signal that allocates phonemes to  the appropriate sequential coding slot.  To  demonstrate that flexi(cid:173) ble,  arbitrary binding of novel  sequences can be supported by this  mechanism,  we  show  that  the  model  can  generalize  to  novel  se(cid:173) quences after  moderate amounts of training.
Thin Junction Trees
Authors: Francis R. Bach, Michael I. Jordan
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We present an algorithm that induces a class of models with thin junction trees—models that are characterized by an upper bound on the size of the maximal cliques of their triangulated graph. By ensuring that the junction tree is thin, inference in our models remains tractable throughout the learning process. This allows both an efﬁcient implementation of an iterative scaling parameter estimation algorithm and also ensures that inference can be performed efﬁciently with the ﬁnal model. We illustrate the approach with applications in handwritten digit recognition and DNA splice site detection.
A Parallel Mixture of SVMs for Very Large Scale Problems
Authors: Ronan Collobert, Samy Bengio, Yoshua Bengio
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Support Vector Machines  (SVMs)  are currently the state-of-the-art models for  many classification problems but they suffer from the complexity of their train(cid:173) ing algorithm which is at least quadratic with respect to the number of examples.  Hence,  it is  hopeless  to try to solve  real-life  problems  having more than a  few  hundreds  of  thousands  examples  with  SVMs.  The  present  paper  proposes  a  new  mixture  of SVMs  that  can  be  easily  implemented  in  parallel  and  where  each SVM is  trained on a  small  subset of the whole  dataset.  Experiments on a  large benchmark dataset  (Forest)  as well  as  a  difficult  speech database, yielded  significant  time  improvement  (time  complexity  appears  empirically  to  locally  grow linearly with the number of examples) .  In addition, and that is a surprise,  a  significant improvement in  generalization was  observed on Forest.
Multi Dimensional ICA to Separate Correlated Sources
Authors: Roland Vollgraf, Klaus Obermayer
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We present a new method for the blind separation of sources, which  do not fulfill the independence assumption.  In contrast to standard  methods  we  consider  groups  of  neighboring  samples  ("patches")  within the observed mixtures.  First  we  extract independent  features  from  the  observed  patches.  It turns out that the average dependencies  between these features  in  different  sources  is  in  general  lower  than  the  dependencies  be(cid:173) tween  the  amplitudes  of different  sources.  We  show  that it  might  be  the  case  that  most  of  the  dependencies  is  carried  by  only  a  small  number  of features.  Is  this  case  - provided  these  features  can  be  identified  by  some  heuristic  - we  project  all  patches  into  the subspace  which  is  orthogonal to  the subspace  spanned by  the  "correlated"  features.  Standard ICA is then performed on the elements of the transformed  patches  (for  which  the  independence  assumption  holds)  and  ro(cid:173) bustly yields a  good estimate of the mixing matrix.
Effective Size of Receptive Fields of Inferior Temporal Visual Cortex Neurons in Natural Scenes
Authors: Thomas P. Trappenberg, Edmund T. Rolls, Simon M. Stringer
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Inferior temporal cortex (IT) neurons have large receptive ﬁelds when a single effective object stimulus is shown against a blank background, but have much smaller receptive ﬁelds when the object is placed in a natural scene. Thus, translation invariant object recognition is reduced in natural scenes, and this may help object selection. We describe a model which accounts for this by competition within an attractor in which the neurons are tuned to different objects in the scene, and the fovea has a higher cortical magniﬁcation factor than the peripheral visual ﬁeld. Further- more, we show that top-down object bias can increase the receptive ﬁeld size, facilitating object search in complex visual scenes, and providing a model of object-based attention. The model leads to the prediction that introduction of a second object into a scene with blank background will reduce the receptive ﬁeld size to values that depend on the closeness of the second object to the target stimulus. We suggest that mechanisms of this type enable the output of IT to be primarily about one object, so that the areas that receive from IT can select the object as a potential target for action.
A kernel method for multi-labelled classification
Authors: André Elisseeff, Jason Weston
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: This article presents a Support Vector Machine (SVM) like learning sys- tem to handle multi-label problems. Such problems are usually decom- posed into many two-class problems but the expressive power of such a system can be weak [5, 7]. We explore a new direct approach. It is based on a large margin ranking system that shares a lot of common proper- ties with SVMs. We tested it on a Yeast gene functional classiﬁcation problem with positive results.
Very loopy belief propagation for unwrapping phase images
Authors: Brendan J. Frey, Ralf Koetter, Nemanja Petrovic
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Since  the  discovery  that  the  best  error-correcting  decoding  algo(cid:173) rithm can be viewed  as belief propagation in a  cycle-bound graph,  researchers  have  been  trying  to  determine  under  what  circum(cid:173) stances "loopy belief propagation" is effective for probabilistic infer(cid:173) ence.  Despite several theoretical advances in our understanding of  loopy belief propagation, to our knowledge,  the only  problem that  has  been  solved  using  loopy  belief propagation is  error-correcting  decoding on Gaussian channels.  We  propose a  new  representation  for  the two-dimensional  phase unwrapping problem,  and  we  show  that loopy belief propagation produces results that are superior to  existing techniques.  This is  an important result, since  many imag(cid:173) ing techniques, including magnetic resonance imaging and interfer(cid:173) ometric synthetic aperture radar,  produce phase-wrapped images.  Interestingly,  the  graph  that  we  use  has  a  very  large  number  of  very short cycles,  supporting evidence that a  large minimum cycle  length is  not needed for  excellent results  using  belief propagation.
Modularity in the motor system: decomposition of muscle patterns as combinations of time-varying synergies
Authors: A. D'avella, M. C. Tresch
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: The question of whether the nervous system produces movement through the combination of a few discrete elements has long been central to the study of motor control. Muscle synergies, i.e. coordinated patterns of muscle activity, have been proposed as possible building blocks. Here we propose a model based on combinations of muscle synergies with a spe- ciﬁc amplitude and temporal structure. Time-varying synergies provide a realistic basis for the decomposition of the complex patterns observed in natural behaviors. To extract time-varying synergies from simultane- ous recording of EMG activity we developed an algorithm which extends existing non-negative matrix factorization techniques.
The Method of Quantum Clustering
Authors: David Horn, Assaf Gottlieb
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We propose a novel clustering method that is an extension of ideas inher- ent to scale-space clustering and support-vector clustering. Like the lat- ter, it associates every data point with a vector in Hilbert space, and like the former it puts emphasis on their total sum, that is equal to the scale- space probability function. The novelty of our approach is the study of an operator in Hilbert space, represented by the Schr¨odinger equation of which the probability function is a solution. This Schr¨odinger equation contains a potential function that can be derived analytically from the probability function. We associate minima of the potential with cluster centers. The method has one variable parameter, the scale of its Gaussian kernel. We demonstrate its applicability on known data sets. By limiting the evaluation of the Schr¨odinger potential to the locations of data points, we can apply this method to problems in high dimensions.
Generating velocity tuning by asymmetric recurrent connections
Authors: Xiaohui Xie, Martin A. Giese
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Asymmetric lateral connections are one possible mechanism that can ac- count for the direction selectivity of cortical neurons. We present a math- ematical analysis for a class of these models. Contrasting with earlier theoretical work that has relied on methods from linear systems theory, we study the network’s nonlinear dynamic properties that arise when the threshold nonlinearity of the neurons is taken into account. We show that such networks have stimulus-locked traveling pulse solutions that are appropriate for modeling the responses of direction selective cortical neurons. In addition, our analysis shows that outside a certain regime of stimulus speeds the stability of this solutions breaks down giving rise to another class of solutions that are characterized by speciﬁc spatio- temporal periodicity. This predicts that if direction selectivity in the cor- tex is mainly achieved by asymmetric lateral connections lurching activ- ity waves might be observable in ensembles of direction selective cortical neurons within appropriate regimes of the stimulus speed.
Incremental Learning and Selective Sampling via Parametric Optimization Framework for SVM
Authors: Shai Fine, Katya Scheinberg
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We propose a framework based on a parametric quadratic program(cid:173) ming  (QP)  technique  to  solve  the  support vector  machine  (SVM)  training problem.  This framework, can be specialized to obtain two  SVM  optimization  methods.  The first  solves  the  fixed  bias  prob(cid:173) lem,  while  the  second  starts  with  an  optimal  solution  for  a  fixed  bias problem and adjusts the bias until the optimal value is found.  The later method can be applied in conjunction with any other ex(cid:173) isting technique which obtains a fixed  bias solution.  Moreover, the  second  method  can  also  be  used  independently  to  solve  the  com(cid:173) plete SVM training problem.  A combination of these two methods  is  more  flexible  than  each  individual  method  and,  among  other  things,  produces an incremental algorithm which exactly  solve the  1-Norm Soft  Margin  SVM  optimization problem.  Applying  Selec(cid:173) tive  Sampling techniques may further  boost convergence.
Bayesian Predictive Profiles With Applications to Retail Transaction Data
Authors: Igor V. Cadez, Padhraic Smyth
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Massive transaction data sets are recorded in a routine manner in telecommunications, retail commerce, and Web site management. In this paper we address the problem of inferring predictive in- dividual proﬂles from such historical transaction data. We de- scribe a generative mixture model for count data and use an an approximate Bayesian estimation framework that eﬁectively com- bines an individual’s speciﬂc history with more general population patterns. We use a large real-world retail transaction data set to illustrate how these proﬂles consistently outperform non-mixture and non-Bayesian techniques in predicting customer behavior in out-of-sample data.
Spectral Kernel Methods for Clustering
Authors: Nello Cristianini, John Shawe-Taylor, Jaz S. Kandola
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: In this paper we introduce new algorithms for unsupervised learn(cid:173) ing based on the use of a kernel matrix. All the information re(cid:173) quired by such algorithms is contained in the eigenvectors of the  matrix or of closely related matrices. We use two different but re(cid:173) lated cost functions, the Alignment and the 'cut cost'. The first  one is discussed in a companion paper [3], the second one is based  on graph theoretic concepts. Both functions measure the level of  clustering of a labeled dataset, or the correlation between data clus(cid:173) ters and labels. We state the problem of unsupervised learning as  assigning labels so as to optimize these cost functions. We show  how the optimal solution can be approximated by slightly relaxing  the corresponding optimization problem, and how this corresponds  to using eigenvector information. The resulting simple algorithms  are tested on real world data with positive results.
Batch Value Function Approximation via Support Vectors
Authors: Thomas G. Dietterich, Xin Wang
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We present three ways of combining linear programming with the kernel trick to find value function approximations for reinforcement learning. One formulation is based on SVM regression; the second is based on the Bellman equation; and the third seeks only to ensure that good moves have an advantage over bad moves. All formu(cid:173) lations attempt to minimize the number of support vectors while fitting the data. Experiments in a difficult, synthetic maze problem show that all three formulations give excellent performance, but the advantage formulation is much easier to train. Unlike policy gradi(cid:173) ent methods, the kernel methods described here can easily 'adjust the complexity of the function approximator to fit the complexity of the value function.
PAC Generalization Bounds for Co-training
Authors: Sanjoy Dasgupta, Michael L. Littman, David A. McAllester
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: The rule-based bootstrapping introduced by Yarowsky, and its co- training variant by Blum and Mitchell, have met with considerable em- pirical success. Earlier work on the theory of co-training has been only loosely related to empirically useful co-training algorithms. Here we give a new PAC-style bound on generalization error which justiﬁes both the use of conﬁdences — partial rules and partial labeling of the unlabeled data — and the use of an agreement-based objective function as sug- gested by Collins and Singer. Our bounds apply to the multiclass case, i.e., where instances are to be assigned one of
Analog Soft-Pattern-Matching Classifier using Floating-Gate MOS Technology
Authors: Toshihiko Yamasaki, Tadashi Shibata
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: A flexible pattern-matching analog classifier is presented in con- junction with a robust image representation algorithm called Prin- cipal Axes Projection (PAP). In the circuit, the functional form of  matching is configurable in terms of the peak position, the peak height  and the sharpness of the similarity evaluation. The test chip was fabri- cated in a 0.6-m m CMOS technology and successfully applied to  hand-written pattern recognition and medical radiograph analysis using  PAP as a feature extraction pre-processing step for robust image coding.  The separation and classification of overlapping patterns is also ex- perimentally demonstrated.
On the Concentration of Spectral Properties
Authors: John Shawe-Taylor, Nello Cristianini, Jaz S. Kandola
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We  consider  the  problem  of  measuring  the  eigenvalues  of a  ran(cid:173) domly drawn sample of points.  We  show  that these  values  can be  reliably  estimated  as  can the  sum  of the  tail  of eigenvalues.  Fur(cid:173) thermore,  the  residuals  when  data is  projected  into a  subspace  is  shown to be reliably estimated on  a  random sample.  Experiments  are presented that confirm the theoretical results.
Stochastic Mixed-Signal VLSI Architecture for High-Dimensional Kernel Machines
Authors: Roman Genov, Gert Cauwenberghs
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: A mixed-signal paradigm is presented for high-resolution parallel inner- product computation in very high dimensions, suitable for efﬁcient im- plementation of kernels in image processing. At the core of the externally digital architecture is a high-density, low-power analog array performing binary-binary partial matrix-vector multiplication. Full digital resolution is maintained even with low-resolution analog-to-digital conversion, ow- ing to random statistics in the analog summation of binary products. A random modulation scheme produces near-Bernoulli statistics even for highly correlated inputs. The approach is validated with real image data, and with experimental results from a CID/DRAM analog array prototype in 0.5
The Emergence of Multiple Movement Units in the Presence of Noise and Feedback Delay
Authors: Michael Kositsky, Andrew G. Barto
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Tangential hand velocity proﬁles of rapid human arm movements of- ten appear as sequences of several bell-shaped acceleration-deceleration phases called submovements or movement units. This suggests how the nervous system might efﬁciently control a motor plant in the presence of noise and feedback delay. Another critical observation is that stochastic- ity in a motor control problem makes the optimal control policy essen- tially different from the optimal control policy for the deterministic case. We use a simpliﬁed dynamic model of an arm and address rapid aimed arm movements. We use reinforcement learning as a tool to approximate the optimal policy in the presence of noise and feedback delay. Using a simpliﬁed model we show that multiple submovements emerge as an optimal policy in the presence of noise and feedback delay. The optimal policy in this situation is to drive the arm’s end point close to the target by one fast submovement and then apply a few slow submovements to accu- rately drive the arm’s end point into the target region. In our simulations, the controller sometimes generates corrective submovements before the initial fast submovement is completed, much like the predictive correc- tions observed in a number of psychophysical experiments.
Pranking with Ranking
Authors: Koby Crammer, Yoram Singer
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We  discuss  the  problem  of ranking  instances.  In  our  framework  each  instance  is  associated  with  a  rank  or  a  rating,  which  is  an  integer from  1 to k.  Our goal is  to find  a  rank-prediction rule that  assigns  each  instance  a  rank  which  is  as  close  as  possible  to  the  instance's true rank.  We  describe  a  simple  and efficient  online  al(cid:173) gorithm, analyze its performance in the mistake bound model, and  prove  its  correctness.  We  describe  two  sets  of experiments,  with  synthetic  data and  with  the  EachMovie  dataset  for  collaborative  filtering.  In  the experiments we  performed,  our algorithm outper(cid:173) forms  online algorithms for  regression and classification applied to  ranking.
Asymptotic Universality for Learning Curves of Support Vector Machines
Authors: Manfred Opper, Robert Urbanczik
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Using  methods  of  Statistical  Physics,  we  investigate  the  rOle  of  model  complexity  in  learning  with  support  vector  machines  (SVMs).  We  show  the  advantages  of  using  SVMs  with  kernels  of infinite  complexity  on  noisy  target  rules,  which,  in  contrast  to  common  theoretical  beliefs,  are found  to  achieve  optimal  general(cid:173) ization error although the training error  does  not  converge to the  generalization error.  Moreover,  we  find  a  universal  asymptotics of  the  learning curves  which  only  depend  on the target  rule  but not  on the  SVM  kernel.
Active Information Retrieval
Authors: Tommi Jaakkola, Hava T. Siegelmann
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: In classical large information retrieval systems, the system responds  to a  user initiated query with a  list of results ranked by relevance.  The  users  may further  refine  their  query  as  needed.  This  process  may  result  in  a  lengthy  correspondence  without  conclusion.  We  propose  an  alternative  active  learning  approach,  where  the  sys(cid:173) tem responds to the initial user's query by successively probing the  user for  distinctions at multiple levels of abstraction.  The system's  initiated  queries  are  optimized  for  speedy  recovery  and  the  user  is  permitted to respond with multiple selections  or may reject the  query.  The information is in each case unambiguously incorporated  by the system and the subsequent queries are adjusted to minimize  the  need  for  further  exchange.  The system's  initiated  queries  are  subject  to resource  constraints pertaining to the  amount of infor(cid:173) mation that can be presented  to the user  per iteration.
Tempo tracking and rhythm quantization by sequential Monte Carlo
Authors: Ali Taylan Cemgil, Bert Kappen
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We present a probabilistic generative model for timing deviations in expressive music. performance. The structure of the proposed model is equivalent to a switching state space model. We formu(cid:173) late two well known music recognition problems, namely tempo tracking and automatic transcription (rhythm quantization) as fil(cid:173) tering and maximum a posteriori (MAP) state estimation tasks. The inferences are carried out using sequential Monte Carlo in(cid:173) tegration (particle filtering) techniques. For this purpose, we have derived a novel Viterbi algorithm for Rao-Blackwellized particle fil(cid:173) ters, where a subset of the hidden variables is integrated out. The resulting model is suitable for realtime tempo tracking and tran(cid:173) scription and hence useful in a number of music applications such as adaptive automatic accompaniment and score typesetting.
Learning a Gaussian Process Prior for Automatically Generating Music Playlists
Authors: John C. Platt, Christopher J. C. Burges, Steven Swenson, Christopher Weare, Alice Zheng
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: This paper presents AutoDJ: a system for automatically generating mu- sic playlists based on one or more seed songs selected by a user. AutoDJ uses Gaussian Process Regression to learn a user preference function over songs. This function takes music metadata as inputs. This paper further introduces Kernel Meta-Training, which is a method of learning a Gaussian Process kernel from a distribution of functions that generates the learned function. For playlist generation, AutoDJ learns a kernel from a large set of albums. This learned kernel is shown to be more effective at predicting users’ playlists than a reasonable hand-designed kernel.
Geometrical Singularities in the Neuromanifold of Multilayer Perceptrons
Authors: Shun-ichi Amari, Hyeyoung Park, Tomoko Ozeki
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Singularities are ubiquitous  in the parameter space of hierarchical  models such as multilayer perceptrons.  At singularities, the Fisher  information  matrix  degenerates,  and  the  Cramer-Rao  paradigm  does no more hold, implying that the classical model selection the(cid:173) ory  such  as  AIC  and  MDL  cannot  be  applied.  It is  important  to  study the relation between the generalization error and the training  error  at  singularities.  The  present  paper  demonstrates  a  method  of analyzing these errors both for  the maximum likelihood estima(cid:173) tor and the  Bayesian  predictive distribution  in  terms  of Gaussian  random fields,  by using simple models.
Convergence of Optimistic and Incremental Q-Learning
Authors: Eyal Even-dar, Yishay Mansour
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Vie sho,v the convergence of tV/O deterministic variants of Q(cid:173) learning. The first is the widely used optimistic Q-learning, which initializes the Q-values to large initial values and then follows a greedy policy with respect to the Q-values. We show that setting the initial value sufficiently large guarantees the converges to an E(cid:173) optimal policy. The second is a new and novel algorithm incremen(cid:173) tal Q-learning, which gradually promotes the values of actions that are not taken. We show that incremental Q-learning converges, in the limit, to the optimal policy. Our incremental Q-learning algo(cid:173) rithm can be viewed as derandomization of the E-greedy Q-learning.
Boosting and Maximum Likelihood for Exponential Models
Authors: Guy Lebanon, John D. Lafferty
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We derive an equivalence between AdaBoost and the dual of a convex optimization problem, showing that the only difference between mini- mizing the exponential loss used by AdaBoost and maximum likelihood for exponential models is that the latter requires the model to be normal- ized to form a conditional probability distribution over labels. In addi- tion to establishing a simple and easily understood connection between the two methods, this framework enables us to derive new regularization procedures for boosting that directly correspond to penalized maximum likelihood. Experiments on UCI datasets support our theoretical analy- sis and give additional insight into the relationship between boosting and logistic regression.
Iterative Double Clustering for Unsupervised and Semi-Supervised Learning
Authors: Ran El-Yaniv, Oren Souroujon
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We present a powerful meta-clustering technique called Iterative Dou- ble Clustering (IDC). The IDC method is a natural extension of the recent Double Clustering (DC) method of Slonim and Tishby that ex- hibited impressive performance on text categorization tasks [12]. Us- ing synthetically generated data we empirically ﬂnd that whenever the DC procedure is successful in recovering some of the structure hidden in the data, the extended IDC procedure can incrementally compute a signiﬂcantly more accurate classiﬂcation. IDC is especially advan- tageous when the data exhibits high attribute noise. Our simulation results also show the eﬁectiveness of IDC in text categorization prob- lems. Surprisingly, this unsupervised procedure can be competitive with a (supervised) SVM trained with a small training set. Finally, we propose a simple and natural extension of IDC for semi-supervised and transductive learning where we are given both labeled and unla- beled examples.
Multiagent Planning with Factored MDPs
Authors: Carlos Guestrin, Daphne Koller, Ronald Parr
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We present a principled and efﬁcient planning algorithm for cooperative multia- gent dynamic systems. A striking feature of our method is that the coordination and communication between the agents is not imposed, but derived directly from the system dynamics and function approximation architecture. We view the en- tire multiagent system as a single, large Markov decision process (MDP), which we assume can be represented in a factored way using a dynamic Bayesian net- work (DBN). The action space of the resulting MDP is the joint action space of the entire set of agents. Our approach is based on the use of factored linear value functions as an approximation to the joint value function. This factorization of the value function allows the agents to coordinate their actions at runtime using a natural message passing scheme. We provide a simple and efﬁcient method for computing such an approximate value function by solving a single linear pro- gram, whose size is determined by the interaction between the value function structure and the DBN. We thereby avoid the exponential blowup in the state and action space. We show that our approach compares favorably with approaches based on reward sharing. We also show that our algorithm is an efﬁcient alterna- tive to more complicated algorithms even in the single agent case.
ACh, Uncertainty, and Cortical Inference
Authors: Peter Dayan, Angela J. Yu
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Acetylcholine (ACh) has been implicated in a wide variety of tasks involving attentional processes and plasticity. Following extensive animal studies, it has previously been suggested that ACh reports on uncertainty and controls hippocampal, cortical and cortico-amygdalar plasticity. We extend this view and consider its effects on cortical representational inference, arguing that ACh controls the balance between bottom-up inference, in(cid:3)uenced by input stimuli, and top-down inference, in(cid:3)uenced by contextual information. We illustrate our proposal using a hierarchical hid- den Markov model.
On Discriminative vs. Generative Classifiers: A comparison of logistic regression and naive Bayes
Authors: Andrew Y. Ng, Michael I. Jordan
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We  compare discriminative  and  generative learning as  typified  by  logistic regression and naive Bayes.  We show,  contrary to a widely(cid:173) held  belief  that  discriminative  classifiers  are  almost  always  to  be  preferred,  that  there  can  often  be  two  distinct  regimes  of  per(cid:173) formance  as  the  training  set  size  is  increased,  one  in  which  each  algorithm  does  better.  This  stems  from  the  observation- which  is  borne  out  in  repeated  experiments- that  while  discriminative  learning has lower asymptotic error, a generative classifier may also  approach its  (higher)  asymptotic error  much faster.
Risk Sensitive Particle Filters
Authors: Sebastian Thrun, John Langford, Vandi Verma
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: We propose a new particle ﬁlter that incorporates a model of costs when generating particles. The approach is motivated by the observation that the costs of accidentally not tracking hypotheses might be signiﬁcant in some areas of state space, and next to irrelevant in others. By incorporat- ing a cost model into particle ﬁltering, states that are more critical to the system performance are more likely to be tracked. Automatic calculation of the cost model is implemented using an MDP value function calcula- tion that estimates the value of tracking a particular state. Experiments in two mobile robot domains illustrate the appropriateness of the approach.
Characterizing Neural Gain Control using Spike-triggered Covariance
Authors: Odelia Schwartz, E. J. Chichilnisky, Eero P. Simoncelli
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Spike-triggered averaging techniques are effective for linear characterization of neural responses. But neurons exhibit important nonlinear behaviors, such as gain control, that are not captured by such analyses. We describe a spike-triggered covariance method for retrieving suppressive components of the gain control signal in a neuron. We demonstrate the method in simulation and on retinal ganglion cell data. Analysis of physiological data reveals significant suppressive axes and explains neural nonlinearities. This method should be applicable to other sensory areas and modalities.
On Spectral Clustering: Analysis and an algorithm
Authors: Andrew Y. Ng, Michael I. Jordan, Yair Weiss
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: Despite many empirical successes of spectral  clustering  methods(cid:173) algorithms  that  cluster  points  using  eigenvectors  of  matrices  de(cid:173) rived  from  the  data- there  are  several  unresolved  issues.  First,  there  are  a  wide  variety  of  algorithms  that  use  the  eigenvectors  in  slightly  different  ways.  Second,  many of these  algorithms  have  no  proof that  they  will  actually  compute  a  reasonable  clustering.  In  this  paper,  we  present  a  simple  spectral  clustering  algorithm  that can be implemented using a  few  lines  of Matlab.  Using  tools  from  matrix  perturbation  theory,  we  analyze  the  algorithm,  and  give  conditions  under  which  it  can  be  expected  to  do  well.  We  also  show  surprisingly  good  experimental  results  on  a  number  of  challenging clustering problems.
Grouping with Bias
Authors: Stella X. Yu, Jianbo Shi
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: With the optimization of pattern discrimination as a goal, graph partitioning approaches often lack the capability to integrate prior knowledge to guide grouping. In this paper, we consider priors from unitary generative models, partially labeled data and spatial attention. These priors are modelled as constraints in the solution space. By imposing uniformity condition on the constraints, we restrict the feasible space to one of smooth solutions. A subspace projection method is developed to solve this constrained eigenprob(cid:173) lema We demonstrate that simple priors can greatly improve image segmentation results.