mtybilly/Instruct2DS huggingface dataset:
A Probabilistic Interpretation of SVMs with an Application to Unbalanced Classification
Authors: Johnny Mariethoz, Samy Bengio Yves Grandvalet
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: In this paper, we show that the hinge loss can be interpreted as the neg-log-likelihood of a semi-parametric model of posterior probabilities. From this point of view, SVMs represent the parametric component of a semi-parametric model ﬁtted by a maximum a posteriori estimation pro- cedure. This connection enables to derive a mapping from SVM scores to estimated posterior probabilities. Unlike previous proposals, the sug- gested mapping is interval-valued, providing a set of posterior probabil- ities compatible with each SVM score. This framework offers a new way to adapt the SVM optimization problem to unbalanced classiﬁca- tion, when decisions result in unequal (asymmetric) losses. Experiments show improvements over state-of-the-art procedures.
Nonparametric inference of prior probabilities from Bayes-optimal behavior
Authors: Liam Paninski
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We discuss a method for obtaining a subject’s a priori beliefs from his/her behavior in a psychophysics context, under the assumption that the behavior is (nearly) optimal from a Bayesian perspective. The method is nonparametric in the sense that we do not assume that the prior belongs to any ﬁxed class of distributions (e.g., Gaussian). Despite this increased generality, the method is relatively simple to implement, being based in the simplest case on a linear programming algorithm, and more generally on a straightforward maximum likelihood or maximum a posteriori formulation, which turns out to be a convex optimization problem (with no non-global local maxima) in many important cases. In addition, we develop methods for analyzing the uncertainty of these esti- mates. We demonstrate the accuracy of the method in a simple simulated coin-ﬂipping setting; in particular, the method is able to precisely track the evolution of the subject’s posterior distribution as more and more data are observed. We close by brieﬂy discussing an interesting connection to recent models of neural population coding.
Oblivious Equilibrium: A Mean Field Approximation for Large-Scale Dynamic Games
Authors: Lanier Benkard, Benjamin Van Roy Gabriel Y. Weintraub
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We propose a mean-ﬁeld approximation that dramatically reduces the computational complexity of solving stochastic dynamic games. We pro- vide conditions that guarantee our method approximates an equilibrium as the number of agents grow. We then derive a performance bound to assess how well the approximation performs for any given number of agents. We apply our method to an important class of problems in ap- plied microeconomics. We show with numerical experiments that we are able to greatly expand the set of economic problems that can be analyzed computationally.
Dynamical Synapses Give Rise to a Power-Law Distribution of Neuronal Avalanches
Authors: Michael Herrmann Anna Levina
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: There is experimental evidence that cortical neurons show avalanche activity with the intensity of firing events being distributed as a power-law. We present a biologically plausible extension of a neural network which exhibits a power-law avalanche distribution for a wide range of connectivity parameters.
From Weighted Classification to Policy Search
Authors: Alfred O. Hero Doron Blatt
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: This paper proposes an algorithm to convert a T -stage stochastic decision problem with a continuous state space to a sequence of supervised learning problems. The optimization problem associated with the trajectory tree and random trajectory methods of Kearns, Mansour, and Ng, 2000, is solved using the Gauss-Seidel method. The algorithm breaks a multistage reinforcement learning problem into a sequence of single-stage reinforcement learning subproblems, each of which is solved via an exact reduction to a weighted-classification problem that can be solved using off-the-self methods. Thus the algorithm converts a reinforcement learning problem into simpler supervised learning subproblems. It is shown that the method converges in a finite number of steps to a solution that cannot be further improved by componentwise optimization. The implication of the proposed algorithm is that a plethora of classification methods can be applied to find policies in the reinforcement learning problem.
Off-Road Obstacle Avoidance through End-to-End Learning
Authors: Jan Ben, Eric Cosatto, Beat Flepp, Yann L. Cun Urs Muller
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We describe a vision-based obstacle avoidance system for off-road mobile robots. The system is trained from end to end to map raw in put images to steering angles. It is trained in supervised mode to predict the steering angles provided by a human driver during training r uns collected in a wide variety of terrains, weather conditions, lighting conditions, and obstacle types. The robot is a 50cm off-road truck, with two f orwardpointing wireless color cameras. A remote computer process es the video and controls the robot via radio. The learning system is a lar ge 6-layer convolutional network whose input is a single left/right pair of unprocessed low-resolution images. The robot exhibits an excellent ability to detect obstacles and navigate around them in real time at speeds of 2 m/s.
PAC-Bayes Learning of Conjunctions and Classification of Gene-Expression Data
Authors: Mohak Shah Mario Marchand
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We propose a “soft greedy” learning algorithm for building small conjunctions of simple threshold functions, called rays, deﬁned on single real-valued attributes. We also propose a PAC-Bayes risk bound which is minimized for classiﬁers achieving a non-trivial tradeoﬀ between sparsity (the number of rays used) and the mag- nitude of the separating margin of each ray. Finally, we test the soft greedy algorithm on four DNA micro-array data sets.
A Second Order Cone programming Formulation for Classifying Missing Data
Authors: Pannagadatta K. Shivaswamy, Alex J. Smola Chiranjib Bhattacharyya
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We propose a convex optimization based strategy to deal with uncertainty          in the observations of a classification problem. We assume that instead          of a sample (xi, yi) a distribution over (xi, yi) is specified. In particu-          lar, we derive a robust formulation when the distribution is given by a          normal distribution. It leads to Second Order Cone Programming formu-          lation. Our method is applied to the problem of missing data, where it          outperforms direct imputation.
Learning first-order Markov models for control
Authors: Andrew Y. Ng Pieter Abbeel
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: First-order Markov models have been successfully applied to many prob- lems, for example in modeling sequential data using Markov chains, and modeling control problems using the Markov decision processes (MDP) formalism. If a ﬁrst-order Markov model’s parameters are estimated from data, the standard maximum likelihood estimator considers only the ﬁrst-order (single-step) transitions. But for many problems, the ﬁrst- order conditional independence assumptions are not satisﬁed, and as a re- sult the higher order transition probabilities may be poorly approximated. Motivated by the problem of learning an MDP’s parameters for control, we propose an algorithm for learning a ﬁrst-order Markov model that ex- plicitly takes into account higher order interactions during training. Our algorithm uses an optimization criterion different from maximum likeli- hood, and allows us to learn models that capture longer range effects, but without giving up the beneﬁts of using ﬁrst-order Markov models. Our experimental results also show the new algorithm outperforming conven- tional maximum likelihood estimation in a number of control problems where the MDP’s parameters are estimated from data.
Who's In the Picture
Authors: Alexander C. Berg, Jaety Edwards, David A. Forsyth Tamara L. Berg
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: The context in which a name appears in a caption provides powerful cues           as to who is depicted in the associated image. We obtain 44,773 face im-           ages, using a face detector, from approximately half a million captioned           news images and automatically link names, obtained using a named en-           tity recognizer, with these faces. A simple clustering method can pro-           duce fair results. We improve these results significantly by combining           the clustering process with a model of the probability that an individual           is depicted given its context. Once the labeling procedure is over, we           have an accurately labeled set of faces, an appearance model for each           individual depicted, and a natural language model that can produce ac-           curate results on captions in isolation.
Optimal Aggregation of Classifiers and Boosting Maps in Functional Magnetic Resonance Imaging
Authors: Manel Martínez-ramón, Stefan Posse Vladimir Koltchinskii
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We study a method of optimal data-driven aggregation of classifiers in a           convex combination and establish tight upper bounds on its excess risk           with respect to a convex loss function under the assumption that the so-           lution of optimal aggregation problem is sparse. We use a boosting type           algorithm of optimal aggregation to develop aggregate classifiers of ac-           tivation patterns in fMRI based on locally trained SVM classifiers. The           aggregation coefficients are then used to design a "boosting map" of the           brain needed to identify the regions with most significant impact on clas-           sification.
Binet-Cauchy Kernels
Authors: S.v.n. Vishwanathan Alex J. Smola
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We propose a family of kernels based on the Binet-Cauchy theorem and its ex- tension to Fredholm operators. This includes as special cases all currently known kernels derived from the behavioral framework, diffusion processes, marginalized kernels, kernels on graphs, and the kernels on sets arising from the subspace angle approach. Many of these kernels can be seen as the extrema of a new continuum of kernel functions, which leads to numerous new special cases. As an application, we apply the new class of kernels to the problem of clustering of video sequences with encouraging results.
The power of feature clustering: An application to object detection
Authors: Moshe Butman Shai Avidan
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We give a fast rejection scheme that is based on image segments and          demonstrate it on the canonical example of face detection. However, in-          stead of focusing on the detection step we focus on the rejection step and          show that our method is simple and fast to be learned, thus making it          an excellent pre-processing step to accelerate standard machine learning          classifiers, such as neural-networks, Bayes classifiers or SVM. We de-          compose a collection of face images into regions of pixels with similar          behavior over the image set. The relationships between the mean and          variance of image segments are used to form a cascade of rejectors that          can reject over 99.8% of image patches, thus only a small fraction of the          image patches must be passed to a full-scale classifier. Moreover, the          training time for our method is much less than an hour, on a standard PC.          The shape of the features (i.e. image segments) we use is data-driven,          they are very cheap to compute and they form a very low dimensional          feature space in which exhaustive search for the best features is tractable.
Synergies between Intrinsic and Synaptic Plasticity in Individual Model Neurons
Authors: Jochen Triesch
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: This paper explores the computational consequences of simultaneous in-          trinsic and synaptic plasticity in individual model neurons. It proposes          a new intrinsic plasticity mechanism for a continuous activation model          neuron based on low order moments of the neuron's firing rate distribu-          tion. The goal of the intrinsic plasticity mechanism is to enforce a sparse          distribution of the neuron's activity level. In conjunction with Hebbian          learning at the neuron's synapses, the neuron is shown to discover sparse          directions in the input.
A Probabilistic Model for Online Document Clustering with Application to Novelty Detection
Authors: Zoubin Ghahramani, Yiming Yang Jian Zhang
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: In this paper we propose a probabilistic model for online document clus-          tering. We use non-parametric Dirichlet process prior to model the grow-          ing number of clusters, and use a prior of general English language          model as the base distribution to handle the generation of novel clusters.          Furthermore, cluster uncertainty is modeled with a Bayesian Dirichlet-          multinomial distribution. We use empirical Bayes method to estimate          hyperparameters based on a historical dataset. Our probabilistic model          is applied to the novelty detection task in Topic Detection and Tracking          (TDT) and compared with existing approaches in the literature.
Non-Local Manifold Tangent Learning
Authors: Martin Monperrus Yoshua Bengio
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We claim and present arguments to the effect that a large class of man-          ifold learning algorithms that are essentially local and can be framed as          kernel learning algorithms will suffer from the curse of dimensionality,          at the dimension of the true underlying manifold. This observation sug-          gests to explore non-local manifold learning algorithms which attempt to          discover shared structure in the tangent planes at different positions. A          criterion for such an algorithm is proposed and experiments estimating a          tangent plane prediction function are presented, showing its advantages          with respect to local manifold learning algorithms: it is able to general-          ize very far from training data (on learning handwritten character image          rotations), where a local non-parametric method fails.
Maximal Margin Labeling for Multi-Topic Text Categorization
Authors: Tomonori Izumitani, Hirotoshi Taira, Eisaku Maeda Hideto Kazawa
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: In this paper, we address the problem of statistical learning for multi- topic text categorization (MTC), whose goal is to choose all relevant top- ics (a label) from a given set of topics. The proposed algorithm, Max- imal Margin Labeling (MML), treats all possible labels as independent classes and learns a multi-class classiﬁer on the induced multi-class cate- gorization problem. To cope with the data sparseness caused by the huge number of possible labels, MML combines some prior knowledge about label prototypes and a maximal margin criterion in a novel way. Experi- ments with multi-topic Web pages show that MML outperforms existing learning algorithms including Support Vector Machines.
1 Multi-topic Text Categorization (MTC)
This paper addresses the problem of learning for multi-topic text categorization (MTC), whose goal is to select all topics relevant to a text from a given set of topics. In MTC, multiple topics may be relevant to a single text. We thus call a set of topics label, and say that a text is assigned a label, not a topic.
In almost all previous text categorization studies (e.g. [1, 2]), the label is predicted by judging each topic’s relevance to the text. In this decomposition approach, the features speciﬁc to a topic, not a label, are regarded as important features. However, the approach may result in inefﬁcient learning as we will explain in the following example.
Imagine an MTC problem of scientiﬁc papers where quantum computing papers are as- signed multi-topic label “quantum physics (QP) & computer science (CS)”. (QP and CS are topics in this example.) Since there are some words speciﬁc to quantum computing such as “qbit1”, one can say that efﬁcient MTC learners should use such words to assign label QP & CS. However, the decomposition approach is likely to ignore these words since they are only speciﬁc to a small portion of the whole QP or CS papers (there are many more QP and CS papers than quantum computing papers), and therefore are not discriminative features for either topic QP or CS.
1Qbit is a unit of quantum information, and frequently appears in real quantum computing litera-
tures, but rarely seen in other literatures.
Symbol x(∈ Rd) t1, t2, . . . , tl T L, λ(⊂ T ) L[j] Λ(= 2T ) {(xi, Li)}m
i=1
Meaning A document vector Topics The set of all topics A label The binary representation of L. 1 if tj ∈ L and 0 otherwise. The set of all possible labels Training samples
Conditional Random Fields for Object Recognition
Authors: Michael Collins, Trevor Darrell Ariadna Quattoni
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We present a discriminative part-based approach for the recognition of          object classes from unsegmented cluttered scenes. Objects are modeled          as flexible constellations of parts conditioned on local observations found          by an interest operator. For each object class the probability of a given          assignment of parts to local features is modeled by a Conditional Ran-          dom Field (CRF). We propose an extension of the CRF framework that          incorporates hidden variables and combines class conditional CRFs into          a unified framework for part-based object recognition. The parameters of          the CRF are estimated in a maximum likelihood framework and recogni-          tion proceeds by finding the most likely class under our model. The main          advantage of the proposed CRF framework is that it allows us to relax the          assumption of conditional independence of the observed data (i.e. local          features) often used in generative approaches, an assumption that might          be too restrictive for a considerable number of object classes.
Inference, Attention, and Decision in a Bayesian Neural Architecture
Authors: Peter Dayan Angela J. Yu
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We study the synthesis of neural coding, selective attention and percep-          tual decision making. A hierarchical neural architecture is proposed,          which implements Bayesian integration of noisy sensory input and top-          down attentional priors, leading to sound perceptual discrimination. The          model offers an explicit explanation for the experimentally observed          modulation that prior information in one stimulus feature (location) can          have on an independent feature (orientation). The network's intermediate          levels of representation instantiate known physiological properties of vi-          sual cortical neurons. The model also illustrates a possible reconciliation          of cortical and neuromodulatory representations of uncertainty.
Exponential Family Harmoniums with an Application to Information Retrieval
Authors: Michal Rosen-zvi, Geoffrey E. Hinton Max Welling
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Directed graphical models with one layer of observed random variables and one or more layers of hidden random variables have been the dom- inant modelling paradigm in many research ﬁelds. Although this ap- proach has met with considerable success, the causal semantics of these models can make it difﬁcult to infer the posterior distribution over the hidden variables. In this paper we propose an alternative two-layer model based on exponential family distributions and the semantics of undi- rected models. Inference in these “exponential family harmoniums” is fast while learning is performed by minimizing contrastive divergence. A member of this family is then studied as an alternative probabilistic model for latent semantic indexing. In experiments it is shown that they perform well on document retrieval tasks and provide an elegant solution to searching with keywords.
An Investigation of Practical Approximate Nearest Neighbor Algorithms
Authors: Andrew W. Moore, Ke Yang, Alexander G. Gray Ting Liu
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: This paper concerns approximate nearest neighbor searching algorithms,          which have become increasingly important, especially in high dimen-          sional perception areas such as computer vision, with dozens of publica-          tions in recent years. Much of this enthusiasm is due to a successful new          approximate nearest neighbor approach called Locality Sensitive Hash-          ing (LSH). In this paper we ask the question: can earlier spatial data          structure approaches to exact nearest neighbor, such as metric trees, be          altered to provide approximate answers to proximity queries and if so,          how? We introduce a new kind of metric tree that allows overlap: certain          datapoints may appear in both the children of a parent. We also intro-          duce new approximate k-NN search algorithms on this structure. We          show why these structures should be able to exploit the same random-          projection-based approximations that LSH enjoys, but with a simpler al-          gorithm and perhaps with greater efficiency. We then provide a detailed          empirical evaluation on five large, high dimensional datasets which show          up to 31-fold accelerations over LSH. This result holds true throughout          the spectrum of approximation levels.
Multiple Relational Embedding
Authors: Geoffrey E. Hinton Roland Memisevic
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We describe a way of using multiple different types of similarity rela-          tionship to learn a low-dimensional embedding of a dataset. Our method          chooses different, possibly overlapping representations of similarity by          individually reweighting the dimensions of a common underlying latent          space. When applied to a single similarity relation that is based on Eu-          clidean distances between the input data points, the method reduces to          simple dimensionality reduction. If additional information is available          about the dataset or about subsets of it, we can use this information to          clean up or otherwise improve the embedding. We demonstrate the po-          tential usefulness of this form of semi-supervised dimensionality reduc-          tion on some simple examples.
Conditional Models of Identity Uncertainty with Application to Noun Coreference
Authors: Ben Wellner Andrew McCallum
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Coreference analysis, also known as record linkage or identity uncer-          tainty, is a difficult and important problem in natural language process-          ing, databases, citation matching and many other tasks. This paper intro-          duces several discriminative, conditional-probability models for coref-          erence analysis, all examples of undirected graphical models. Unlike          many historical approaches to coreference, the models presented here          are relational--they do not assume that pairwise coreference decisions          should be made independently from each other. Unlike other relational          models of coreference that are generative, the conditional model here can          incorporate a great variety of features of the input without having to be          concerned about their dependencies--paralleling the advantages of con-          ditional random fields over hidden Markov models. We present positive          results on noun phrase coreference in two standard text data sets.
Generative Affine Localisation and Tracking
Authors: Andrew Blake John Winn
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We present an extension to the Jojic and Frey (2001) layered sprite model          which allows for layers to undergo affine transformations. This extension          allows for affine object pose to be inferred whilst simultaneously learn-          ing the object shape and appearance. Learning is carried out by applying          an augmented variational inference algorithm which includes a global          search over a discretised transform space followed by a local optimisa-          tion. To aid correct convergence, we use bottom-up cues to restrict the          space of possible affine transformations. We present results on a number          of video sequences and show how the model can be extended to track an          object whose appearance changes throughout the sequence.
Schema Learning: Experience-Based Construction of Predictive Action Models
Authors: Charles Jr. Michael P. Holmes
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Schema learning is a way to discover probabilistic, constructivist, pre- dictive action models (schemas) from experience. It includes meth- ods for ﬁnding and using hidden state to make predictions more accu- rate. We extend the original schema mechanism [1] to handle arbitrary discrete-valued sensors, improve the original learning criteria to handle POMDP domains, and better maintain hidden state by using schema pre- dictions. These extensions show large improvement over the original schema mechanism in several rewardless POMDPs, and achieve very low prediction error in a difﬁcult speech modeling task. Further, we compare extended schema learning to the recently introduced predictive state rep- resentations [2], and ﬁnd their predictions of next-step action effects to be approximately equal in accuracy. This work lays the foundation for a schema-based system of integrated learning and planning.
Machine Learning Applied to Perception: Decision Images for Gender Classification
Authors: Arnulf B. Graf, Heinrich H. Bülthoff, Eero P. Simoncelli, Bernhard Schölkopf Felix A. Wichmann
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We study gender discrimination of human faces using a combination of psychophysical classiﬁcation and discrimination experiments together with methods from machine learning. We reduce the dimensionality of a set of face images using principal component analysis, and then train a set of linear classiﬁers on this reduced representation (linear support vec- tor machines (SVMs), relevance vector machines (RVMs), Fisher linear discriminant (FLD), and prototype (prot) classiﬁers) using human clas- siﬁcation data. Because we combine a linear preprocessor with linear classiﬁers, the entire system acts as a linear classiﬁer, allowing us to visu- alise the decision-image corresponding to the normal vector of the separ- ating hyperplanes (SH) of each classiﬁer. We predict that the female-to- maleness transition along the normal vector for classiﬁers closely mim- icking human classiﬁcation (SVM and RVM [1]) should be faster than the transition along any other direction. A psychophysical discrimina- tion experiment using the decision images as stimuli is consistent with this prediction.
An Information Maximization Model of Eye Movements
Authors: James M. Coughlan, Preeti Verghese, Jitendra Malik Laura W. Renninger
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We propose a sequential information maximization model as a  general strategy for programming eye movements. The model  reconstructs high-resolution visual information from a sequence of  fixations, taking into account the fall-off in resolution from the  fovea to the periphery. From this framework we get a simple rule  for predicting fixation sequences: after each fixation, fixate next at  the location that minimizes uncertainty (maximizes information)  about the stimulus. By comparing our model performance to human  eye movement data and to predictions from a saliency and random  model, we demonstrate that our model is best at predicting fixation  locations. Modeling additional biological constraints will improve  the prediction of fixation sequences. Our results suggest that  information maximization is a useful principle for programming  eye movements.
Learning Hyper-Features for Visual Identification
Authors: Erik G. Learned-miller, Jitendra Malik Andras D. Ferencz
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We address the problem of identifying specific instances of a class (cars)           from a set of images all belonging to that class. Although we cannot build           a model for any particular instance (as we may be provided with only one           "training" example of it), we can use information extracted from observ-           ing other members of the class. We pose this task as a learning problem,           in which the learner is given image pairs, labeled as matching or not, and           must discover which image features are most consistent for matching in-           stances and discriminative for mismatches. We explore a patch based           representation, where we model the distributions of similarity measure-           ments defined on the patches. Finally, we describe an algorithm that           selects the most salient patches based on a mutual information criterion.           This algorithm performs identification well for our challenging dataset           of car images, after matching only a few, well chosen patches.
Parametric Embedding for Class Visualization
Authors: Kazumi Saito, Naonori Ueda, Sean Stromsten, Thomas L. Griffiths, Joshua B. Tenenbaum Tomoharu Iwata
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: In this paper, we propose a new method, Parametric Embedding (PE), for visualizing the posteriors estimated over a mixture model. PE simultane- ously embeds both objects and their classes in a low-dimensional space. PE takes as input a set of class posterior vectors for given data points, and tries to preserve the posterior structure in an embedding space by minimizing a sum of Kullback-Leibler divergences, under the assump- tion that samples are generated by a Gaussian mixture with equal covari- ances in the embedding space. PE has many potential uses depending on the source of the input data, providing insight into the classiﬁer’s be- havior in supervised, semi-supervised and unsupervised settings. The PE algorithm has a computational advantage over conventional embedding methods based on pairwise object relations since its complexity scales with the product of the number of objects and the number of classes. We demonstrate PE by visualizing supervised categorization of web pages, semi-supervised categorization of digits, and the relations of words and latent topics found by an unsupervised algorithm, Latent Dirichlet Allo- cation.
A Topographic Support Vector Machine: Classification Using Local Label Configurations
Authors: Klaus Obermayer Johannes Mohr
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: The standard approach to the classification of objects is to consider the          examples as independent and identically distributed (iid). In many real          world settings, however, this assumption is not valid, because a topo-          graphical relationship exists between the objects. In this contribution we          consider the special case of image segmentation, where the objects are          pixels and where the underlying topography is a 2D regular rectangular          grid. We introduce a classification method which not only uses measured          vectorial feature information but also the label configuration within a to-          pographic neighborhood. Due to the resulting dependence between the          labels of neighboring pixels, a collective classification of a set of pixels          becomes necessary. We propose a new method called 'Topographic Sup-          port Vector Machine' (TSVM), which is based on a topographic kernel          and a self-consistent solution to the label assignment shown to be equiv-          alent to a recurrent neural network. The performance of the algorithm is          compared to a conventional SVM on a cell image segmentation task.
New Criteria and a New Algorithm for Learning in Multi-Agent Systems
Authors: Yoav Shoham Rob Powers
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We propose a new set of criteria for learning algorithms in multi-agent          systems, one that is more stringent and (we argue) better justified than          previous proposed criteria. Our criteria, which apply most straightfor-          wardly in repeated games with average rewards, consist of three require-          ments: (a) against a specified class of opponents (this class is a parameter          of the criterion) the algorithm yield a payoff that approaches the payoff          of the best response, (b) against other opponents the algorithm's payoff          at least approach (and possibly exceed) the security level payoff (or max-          imin value), and (c) subject to these requirements, the algorithm achieve          a close to optimal payoff in self-play. We furthermore require that these          average payoffs be achieved quickly. We then present a novel algorithm,          and show that it meets these new criteria for a particular parameter class,          the class of stationary opponents. Finally, we show that the algorithm          is effective not only in theory, but also empirically. Using a recently          introduced comprehensive game theoretic test suite, we show that the          algorithm almost universally outperforms previous learning algorithms.
The Cerebellum Chip: an Analog VLSI Implementation of a Cerebellar Model of Classical Conditioning
Authors: Manuel Gil, Kynan Eng, Giacomo Indiveri, Matti Mintz, Jörg Kramer, Paul F. Verschure Constanze Hofstoetter
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We  present  a  biophysically  constrained  cerebellar  model  of                classical  conditioning,  implemented  using  a  neuromorphic  analog                VLSI (aVLSI) chip.  Like its biological counterpart, our cerebellar                model  is  able  to  control  adaptive  behavior  by  predicting  the                precise timing of events.  Here we describe the functionality of the                chip  and  present  its  learning  performance,  as  evaluated  in                simulated  conditioning  experiments  at  the  circuit  level  and  in                behavioral  experiments  using  a  mobile  robot.    We  show  that  this                aVLSI model supports the acquisition and extinction of adaptively                timed  conditioned  responses  under  real-world  conditions  with                ultra-low power consumption.
Pictorial Structures for Molecular Modeling: Interpreting Density Maps
Authors: George Phillips, Jude W. Shavlik Frank Dimaio
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: X-ray crystallography is currently the most common way protein  structures are elucidated. One of the most time-consuming steps in  the crystallographic process is interpretation of the electron density  map, a task that involves finding patterns in a three-dimensional  picture of a protein. This paper describes DEFT (DEFormable  Template), an algorithm using pictorial structures to build a  flexible protein model from the protein's amino-acid sequence.  Matching this pictorial structure into the density map is a way of  automating density-map interpretation. Also described are several  extensions to the pictorial structure matching algorithm necessary  for this automated interpretation. DEFT is tested on a set of  density maps ranging from 2 to 4Å resolution, producing root- mean-squared errors ranging from 1.38 to 1.84Å.
Support Vector Classification with Input Data Uncertainty
Authors: Tong Zhang Jinbo Bi
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: This paper investigates a new learning model in which the input data is corrupted with noise. We present a general statistical framework to tackle this problem. Based on the statistical reasoning, we propose a novel formulation of support vector classiﬁcation, which allows uncer- tainty in input data. We derive an intuitive geometric interpretation of the proposed formulation, and develop algorithms to efﬁciently solve it. Empirical results are included to show that the newly formed method is superior to the standard SVM for problems with noisy input.
Expectation Consistent Free Energies for Approximate Inference
Authors: Ole Winther Manfred Opper
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We propose a novel a framework for deriving approximations for in-          tractable probabilistic models. This framework is based on a free energy          (negative log marginal likelihood) and can be seen as a generalization          of adaptive TAP [1, 2, 3] and expectation propagation (EP) [4, 5]. The          free energy is constructed from two approximating distributions which          encode different aspects of the intractable model such a single node con-          straints and couplings and are by construction consistent on a chosen set          of moments. We test the framework on a difficult benchmark problem          with binary variables on fully connected graphs and 2D grid graphs. We          find good performance using sets of moments which either specify fac-          torized nodes or a spanning tree on the nodes (structured approximation).          Surprisingly, the Bethe approximation gives very inferior results even on          grids.
Using Machine Learning to Break Visual Human Interaction Proofs (HIPs)
Authors: Patrice Y. Simard Kumar Chellapilla
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Machine learning is often used to automatically solve human tasks. 
          In this paper, we look for tasks where machine learning algorithms 
          are not as good as humans with the hope of gaining insight into 
          their current limitations. We studied various Human Interactive 
          Proofs (HIPs) on the market, because they are systems designed to 
          tell computers and humans apart by posing challenges presumably 
          too hard for computers. We found that most HIPs are pure 
          recognition tasks which can easily be broken using machine 
          learning. The harder HIPs use a combination of segmentation and 
          recognition tasks. From this observation, we found that building 
          segmentation tasks is the most effective way to confuse machine 
          learning algorithms. This has enabled us to build effective HIPs 
          (which we deployed in MSN Passport), as well as design 
          challenging segmentation tasks for machine learning algorithms.
Making Latin Manuscripts Searchable using gHMM's
Authors: Yee W. Teh, Roger Bock, Michael Maire, Grace Vesom, David A. Forsyth Jaety Edwards
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We describe a method that can make a scanned, handwritten mediaeval          latin manuscript accessible to full text search. A generalized HMM is          fitted, using transcribed latin to obtain a transition model and one exam-          ple each of 22 letters to obtain an emission model. We show results for          unigram, bigram and trigram models. Our method transcribes 25 pages          of a manuscript of Terence with fair accuracy (75% of letters correctly          transcribed). Search results are very strong; we use examples of vari-          ant spellings to demonstrate that the search respects the ink of the doc-          ument. Furthermore, our model produces fair searches on a document          from which we obtained no training data.
Nonparametric Transforms of Graph Kernels for Semi-Supervised Learning
Authors: Jaz Kandola, Zoubin Ghahramani, John D. Lafferty Xiaojin Zhu
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We present an algorithm based on convex optimization for constructing kernels for semi-supervised learning. The kernel matrices are derived from the spectral decomposition of graph Laplacians, and combine la- beled and unlabeled data in a systematic fashion. Unlike previous work using diffusion kernels and Gaussian random ﬁeld kernels, a nonpara- metric kernel approach is presented that incorporates order constraints during optimization. This results in ﬂexible kernels and avoids the need to choose among different parametric forms. Our approach relies on a quadratically constrained quadratic program (QCQP), and is compu- tationally feasible for large datasets. We evaluate the kernels on real datasets using support vector machines, with encouraging results.
Sparse Coding of Natural Images Using an Overcomplete Set of Limited Capacity Units
Authors: Michael S. Lewicki Eizaburo Doi
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: It has been suggested that the primary goal of the sensory system is to            represent input in such a way as to reduce the high degree of redun-            dancy. Given a noisy neural representation, however, solely reducing            redundancy is not desirable, since redundancy is the only clue to reduce            the effects of noise. Here we propose a model that best balances redun-            dancy reduction and redundant representation. Like previous models, our            model accounts for the localized and oriented structure of simple cells,            but it also predicts a different organization for the population. With noisy,            limited-capacity units, the optimal representation becomes an overcom-            plete, multi-scale representation, which, compared to previous models,            is in closer agreement with physiological data. These results offer a new            perspective on the expansion of the number of neurons from retina to V1            and provide a theoretical model of incorporating useful redundancy into            efficient neural representations.
1     Introduction
Efficient coding theory posits that one of the primary goals of sensory coding is to eliminate redundancy from raw sensory signals, ideally representing the input by a set of statistically independent features [1]. Models for learning efficient codes, such as sparse coding [2] or ICA [3], predict the localized, oriented, and band-pass characteristics of simple cells. In this framework, units are assumed to be non-redundant and so the number of units should be identical to the dimensionality of the data.
Redundancy, however, can be beneficial if it is used to compensate for inherent noise in the system [4]. The models above assume that the system noise is low and negligible so that redundancy in the representation is not necessary. This is equivalent to assuming that the representational capacity of individual units is unlimited. Real neurons, however, have limited capacity [5], and this should place constraints on how a neural population can best encode a sensory signal. In fact, there are important characteristics of simple cells, such as the multi-scale representation, that cannot be explained by efficient coding theory.
The aim of this study is to evaluate how the optimal representation changes when the system
is constrained by limited capacity units. We propose a model that best balances redundancy reduction and redundant representation given the limited capacity units. In contrast to the efficient coding models, it is possible to have a larger number of units than the intrinsic dimensionality of the data. This further allows to introduce redundancy in the population, enabling precise reconstruction using the imprecise representation of a single unit.
Density Level Detection is Classification
Authors: Don Hush, Clint Scovel Ingo Steinwart
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: We show that anomaly detection can be interpreted as a binary classifi-          cation problem. Using this interpretation we propose a support vector          machine (SVM) for anomaly detection. We then present some theoret-          ical results which include consistency and learning rates. Finally, we          experimentally compare our SVM with the standard one-class SVM.
Learning Syntactic Patterns for Automatic Hypernym Discovery
Authors: Daniel Jurafsky, Andrew Y. Ng Rion Snow
Published in: Advances in Neural Information Processing Systems 17  (NIPS 2004) (Main Conference Track), 2004

Abstract: Semantic taxonomies such as WordNet provide a rich source of knowl-
         edge for natural language processing applications, but are expensive to
         build, maintain, and extend. Motivated by the problem of automatically
         constructing and extending such taxonomies, in this paper we present a
         new algorithm for automatically learning hypernym (is-a) relations from
         text. Our method generalizes earlier work that had relied on using small
         numbers of hand-crafted regular expression patterns to identify hyper-
         nym pairs. Using "dependency path" features extracted from parse trees,
         we introduce a general-purpose formalization and generalization of these
         patterns. Given a training set of text containing known hypernym pairs,
         our algorithm automatically extracts useful dependency paths and applies
         them to new corpora to identify novel pairs. On our evaluation task (de-
         termining whether two nouns in a news article participate in a hypernym
         relationship), our automatically extracted database of hypernyms attains
         both higher precision and higher recall than WordNet.