mtybilly/Instruct2DS huggingface dataset:
Fully Dynamic Consistent Facility Location
Authors: Vincent Cohen-Addad, Niklas Oskar D Hjuler, Nikos Parotsidis, David Saulpic, Chris Schwiegelshohn
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We consider classic clustering problems in fully dynamic data streams, where data elements can be both inserted and deleted. In this context, several parameters are of importance: (1) the quality of the solution after each insertion or deletion, (2) the time it takes to update the solution, and (3) how different consecutive solutions are. The question of obtaining efficient algorithms in this context for facility location, $k$-median and $k$-means has been raised in a recent paper by Hubert-Chan et al. [WWW'18] and also appears as a natural follow-up on the online model with recourse studied by Lattanzi and Vassilvitskii [ICML'17] (i.e.: in insertion-only streams).

In this paper, we focus on general metric spaces and mainly on the facility location problem. We give an arguably simple algorithm that maintains a constant factor approximation, with $O(n\log n)$ update time, and total recourse $O(n)$. This improves over the naive algorithm which consists in recomputing a solution at each time step and that can take up to $O(n^2)$ update time, and $O(n^2)$ total recourse. These bounds are nearly optimal: in general metric space, inserting a point take $O(n)$ times to describe the distances to other points, and we give a simple lower bound of $O(n)$ for the recourse. Moreover, we generalize this result for the $k$-medians and $k$-means problems: our algorithm maintains a constant factor approximation in time $\widetilde{O}(n+k^2)$.

We complement our analysis with experiments showing that the cost of the solution maintained by our algorithm at any time $t$ is very close to the cost of a solution obtained by quickly recomputing a solution from scratch at time $t$ while having a much better running time.
Efficient Rematerialization for Deep Networks
Authors: Ravi Kumar, Manish Purohit, Zoya Svitkina, Erik Vee, Joshua Wang
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: When training complex neural networks, memory usage can be an important bottleneck.  The question of when to rematerialize, i.e., to recompute intermediate values rather than retaining them in memory, becomes critical to achieving the best time and space efficiency.  In this work we consider the rematerialization problem and devise efficient algorithms that use structural characterizations of computation graphs---treewidth and pathwidth---to obtain provably efficient rematerialization schedules. Our experiments demonstrate the performance of these algorithms on many common deep learning models.
Flow-based Image-to-Image Translation with Feature Disentanglement
Authors: Ruho Kondo, Keisuke Kawano, Satoshi Koide, Takuro Kutsuna
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Learning non-deterministic dynamics and intrinsic factors from images obtained through physical experiments is at the intersection of machine learning and material science. Disentangling the origins of uncertainties involved in microstructure growth, for example, is of great interest because future states vary due to thermal fluctuation and other environmental factors. To this end we propose a flow-based image-to-image model, called Flow U-Net with Squeeze modules (FUNS), that allows us to disentangle the features while retaining the ability to generate highquality diverse images from condition images. Our model successfully captures probabilistic phenomena by incorporating a U-Net-like architecture into the flowbased model. In addition, our model automatically separates the diversity of target images into condition-dependent/independent parts. We demonstrate that the quality and diversity of the images generated for microstructure growth and CelebA datasets outperform existing variational generative models.
Temporal Coherence, Natural Image Sequences, and the Visual Cortex
Authors: Jarmo Hurri, Aapo Hyvärinen
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We show that two important properties of the primary visual cortex emerge when the principle of temporal coherence is applied to natural image sequences. The properties are simple-cell-like receptive ﬁelds and complex-cell-like pooling of simple cell outputs, which emerge when we apply two different approaches to temporal coherence. In the ﬁrst approach we extract receptive ﬁelds whose outputs are as temporally co- herent as possible. This approach yields simple-cell-like receptive ﬁelds (oriented, localized, multiscale). Thus, temporal coherence is an alterna- tive to sparse coding in modeling the emergence of simple cell receptive ﬁelds. The second approach is based on a two-layer statistical generative model of natural image sequences. In addition to modeling the temporal coherence of individual simple cells, this model includes inter-cell tem- poral dependencies. Estimation of this model from natural data yields both simple-cell-like receptive ﬁelds, and complex-cell-like pooling of simple cell outputs. In this completely unsupervised learning, both lay- ers of the generative model are estimated simultaneously from scratch. This is a signiﬁcant improvement on earlier statistical models of early vision, where only one layer has been learned, and others have been ﬁxed a priori.
Nonparametric Representation of Policies and Value Functions: A Trajectory-Based Approach
Authors: Christopher G. Atkeson, Jun Morimoto
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: A longstanding goal of reinforcement learning is to develop non- parametric representations of policies and value functions that support rapid learning without suffering from interference or the curse of di- mensionality. We have developed a trajectory-based approach, in which policies and value functions are represented nonparametrically along tra- jectories. These trajectories, policies, and value functions are updated as the value function becomes more accurate or as a model of the task is up- dated. We have applied this approach to periodic tasks such as hopping and walking, which required handling discount factors and discontinu- ities in the task dynamics, and using function approximation to represent value functions at discontinuities. We also describe extensions of the ap- proach to make the policies more robust to modeling error and sensor noise.
A Differential Semantics for Jointree Algorithms
Authors: James D. Park, Adnan Darwiche
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: A new approach to inference in belief networks has been recently proposed, which is based on an algebraic representation of belief networks using multi{linear functions. According to this approach, the key computational question is that of representing multi{linear functions compactly, since inference reduces to a simple process of ev aluating and diﬁerentiating such functions. W e show here that mainstream inference algorithms based on jointrees are a special case of this approach in a v ery precise sense. W e use this result to prov e new properties of jointree algorithms, and then discuss some of its practical and theoretical implications.
"Name That Song!" A Probabilistic Approach to Querying on Music and Text
Authors: Brochu Eric, Nando de Freitas
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We present a novel, ﬂexible statistical approach for modelling music and text jointly. The approach is based on multi-modal mixture models and maximum a posteriori estimation using EM. The learned models can be used to browse databases with documents containing music and text, to search for music using queries consisting of music and text (lyrics and other contextual information), to annotate text documents with music, and to automatically recommend or identify similar songs.
Going Metric: Denoising Pairwise Data
Authors: Volker Roth, Julian Laub, Klaus-Robert Müller, Joachim M. Buhmann
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Pairwise  data in  empirical  sciences  typically  violate  metricity,  ei(cid:173) ther  due  to  noise  or  due  to  fallible  estimates,  and  therefore  are  hard  to  analyze  by  conventional  machine  learning  technology.  In  this  paper  we  therefore  study  ways  to  work  around  this  problem.  First,  we  present  an  alternative  embedding  to  multi-dimensional  scaling  (MDS)  that  allows  us  to  apply  a  variety  of classical  ma(cid:173) chine learning and signal processing algorithms.  The class of pair(cid:173) wise grouping algorithms which share the shift-invariance property  is  statistically  invariant  under  this  embedding  procedure,  leading  to  identical assignments  of objects to clusters.  Based on this  new  vectorial  representation,  denoising  methods  are  applied  in  a  sec(cid:173) ond  step.  Both steps  provide a  theoretically  well  controlled setup  to  translate  from  pairwise  data  to  the  respective  denoised  met(cid:173) ric  representation.  We  demonstrate the practical usefulness of our  theoretical  reasoning by  discovering structure in  protein sequence  data bases, visibly improving performance upon existing automatic  methods.
String Kernels, Fisher Kernels and Finite State Automata
Authors: Craig Saunders, Alexei Vinokourov, John S. Shawe-taylor
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: In  this  paper  we  show  how  the  generation  of documents  can  be  thought of as a  k-stage Markov process,  which leads to a  Fisher ker(cid:173) nel from which the n-gram and string kernels can be re-constructed.  The Fisher  kernel  view  gives  a  more flexible  insight into the string  kernel  and  suggests  how  it  can  be  parametrised  in  a  way  that  re(cid:173) flects  the  statistics  of the training corpus.  Furthermore,  the  prob(cid:173) abilistic  modelling  approach  suggests  extending  the  Markov  pro(cid:173) cess  to  consider  sub-sequences  of varying  length,  rather  than  the  standard fixed-length  approach  used  in  the  string kernel.  We give  a  procedure  for  determining  which  sub-sequences  are  informative  features  and  hence  generate  a  Finite State  Machine  model,  which  can  again  be  used  to  obtain  a  Fisher  kernel.  By  adjusting  the  parametrisation we  can also influence the weighting received by the  features .  In this way we  are able to obtain a  logarithmic weighting  in  a  Fisher  kernel.  Finally,  experiments  are  reported  comparing  the  different  kernels  using  the  standard  Bag  of Words  kernel  as  a  baseline.
Extracting Relevant Structures with Side Information
Authors: Gal Chechik, Naftali Tishby
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: The problem of extracting the relevant aspects of data, in face of multiple conﬂicting structures, is inherent to modeling of complex data. Extract- ing structure in one random variable that is relevant for another variable has been principally addressed recently via the information bottleneck method [15]. However, such auxiliary variables often contain more in- formation than is actually required due to structures that are irrelevant for the task. In many other cases it is in fact easier to specify what is irrelevant than what is, for the task at hand. Identifying the relevant structures, however, can thus be considerably improved by also mini- mizing the information about another, irrelevant, variable. In this paper we give a general formulation of this problem and derive its formal, as well as algorithmic, solution. Its operation is demonstrated in a synthetic example and in two real world problems in the context of text categoriza- tion and face images. While the original information bottleneck problem is related to rate distortion theory, with the distortion measure replaced by the relevant information, extracting relevant features while removing irrelevant ones is related to rate distortion with side information.
Classifying Patterns of Visual Motion - a Neuromorphic Approach
Authors: Jakob Heinzle, Alan Stocker
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We report a system that classiﬁes and can learn to classify patterns of visual motion on-line. The complete system is described by the dynam- ics of its physical network architectures. The combination of the fol- lowing properties makes the system novel: Firstly, the front-end of the system consists of an aVLSI optical ﬂow chip that collectively computes 2-D global visual motion in real-time [1]. Secondly, the complexity of the classiﬁcation task is signiﬁcantly reduced by mapping the continu- ous motion trajectories to sequences of ’motion events’. And thirdly, all the network structures are simple and with the exception of the optical ﬂow chip based on a Winner-Take-All (WTA) architecture. We demon- strate the application of the proposed generic system for a contactless man-machine interface that allows to write letters by visual motion. Re- garding the low complexity of the system, its robustness and the already existing front-end, a complete aVLSI system-on-chip implementation is realistic, allowing various applications in mobile electronic devices.
Fast Transformation-Invariant Factor Analysis
Authors: Anitha Kannan, Nebojsa Jojic, Brendan Frey
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Dimensionality reduction techniques such as principal component analy- sis and factor analysis are used to discover a linear mapping between high dimensional data samples and points in a lower dimensional subspace. In [6], Jojic and Frey introduced mixture of transformation-invariant component analyzers (MTCA) that can account for global transforma- tions such as translations and rotations, perform clustering and learn lo- cal appearance deformations by dimensionality reduction. However, due to enormous computational requirements of the EM algorithm for learn- ing the model, O( is the dimensionality of a data sample, MTCA was not practical for most applications. In this paper, we demon- strate how fast Fourier transforms can reduce the computation to the or- . With this speedup, we show the effectiveness of MTCA der of in various applications - tracking, video textures, clustering video se- quences, object recognition, and object detection in images.
Spikernels: Embedding Spiking Neurons in Inner-Product Spaces
Authors: Lavi Shpigelman, Yoram Singer, Rony Paz, Eilon Vaadia
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Inner-product operators, often referred to as kernels in statistical learning, de- ﬁne a mapping from some input space into a feature space. The focus of this paper is the construction of biologically-motivated kernels for cortical ac- tivities. The kernels we derive, termed Spikernels, map spike count sequences into an abstract vector space in which we can perform various prediction tasks. We discuss in detail the derivation of Spikernels and describe an efﬁcient al- gorithm for computing their value on any two sequences of neural population spike counts. We demonstrate the merits of our modeling approach using the Spikernel and various standard kernels for the task of predicting hand move- ment velocities from cortical recordings. In all of our experiments all the ker- nels we tested outperform the standard scalar product used in regression with the Spikernel consistently achieving the best performance.
Graph-Driven Feature Extraction From Microarray Data Using Diffusion Kernels and Kernel CCA
Authors: Jean-philippe Vert, Minoru Kanehisa
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We present an algorithm to extract features from high-dimensional gene expression proﬁles, based on the knowledge of a graph which links to- gether genes known to participate to successive reactions in metabolic pathways. Motivated by the intuition that biologically relevant features are likely to exhibit smoothness with respect to the graph topology, the algorithm involves encoding the graph and the set of expression pro- ﬁles into kernel functions, and performing a generalized form of canoni- cal correlation analysis in the corresponding reproducible kernel Hilbert spaces. Function prediction experiments for the genes of the yeast S. Cerevisiae validate this approach by showing a consistent increase in performance when a state-of-the-art classiﬁer uses the vector of features instead of the original expression proﬁle to predict the functional class of a gene.
Spike Timing-Dependent Plasticity in the Address Domain
Authors: R. J. Vogelstein, Francesco Tenore, Ralf Philipp, Miriam S. Adlerstein, David H. Goldberg, Gert Cauwenberghs
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Address-event representation (AER), originally proposed as a means to communicate sparse neural events between neuromorphic chips, has proven efﬁcient in implementing large-scale networks with arbitrary, conﬁgurable synaptic connectivity. In this work, we further extend the functionality of AER to implement arbitrary, conﬁgurable synaptic plas- ticity in the address domain. As proof of concept, we implement a bi- ologically inspired form of spike timing-dependent plasticity (STDP) based on relative timing of events in an AER framework. Experimen- tal results from an analog VLSI integrate-and-ﬁre network demonstrate address domain learning in a task that requires neurons to group corre- lated inputs.
Efficient Learning Equilibrium
Authors: Ronen I. Brafman, Moshe Tennenholtz
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We introduce efficient learning  equilibrium  (ELE), a normative ap(cid:173) proach to learning in non cooperative settings.  In ELE, the learn(cid:173) ing  algorithms  themselves  are  required  to  be  in  equilibrium.  In  addition,  the  learning  algorithms  arrive  at  a  desired  value  after  polynomial time,  and deviations from a prescribed ELE become ir(cid:173) rational after  polynomial time.  We  prove the existence of an ELE  in  the  perfect  monitoring  setting,  where  the  desired  value  is  the  expected payoff in a  Nash equilibrium.  We  also show that an ELE  does  not  always  exist  in  the  imperfect  monitoring  case.  Yet,  it  exists  in  the  special  case  of common-interest  games.  Finally,  we  extend our results to general stochastic games.
Using Tarjan's Red Rule for Fast Dependency Tree Construction
Authors: Dan Pelleg, Andrew W. Moore
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We focus on the problem of efﬁcient learning of dependency trees. It is well-known that given the pairwise mutual information coefﬁcients, a minimum-weight spanning tree algorithm solves this problem exactly and in polynomial time. However, for large data-sets it is the construc- tion of the correlation matrix that dominates the running time. We have developed a new spanning-tree algorithm which is capable of exploiting partial knowledge about edge weights. The partial knowledge we main- tain is a probabilistic conﬁdence interval on the coefﬁcients, which we derive by examining just a small sample of the data. The algorithm is able to ﬂag the need to shrink an interval, which translates to inspec- tion of more data for the particular attribute pair. Experimental results show running time that is near-constant in the number of records, with- out signiﬁcant loss in accuracy of the generated trees. Interestingly, our spanning-tree algorithm is based solely on Tarjan’s red-edge rule, which is generally considered a guaranteed recipe for bad performance.
Approximate Inference and Protein-Folding
Authors: Chen Yanover, Yair Weiss
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Side-chain prediction is an important subtask in the protein-folding  problem.  We  show  that  finding  a  minimal  energy  side-chain  con(cid:173) figuration  is  equivalent  to  performing  inference  in  an  undirected  graphical model.  The graphical model  is  relatively  sparse yet  has  many cycles.  We used this equivalence to assess the performance of  approximate inference  algorithms  in  a  real-world  setting.  Specifi(cid:173) cally we  compared belief propagation (BP), generalized BP (GBP)  and naive mean field  (MF).  In  cases  where  exact  inference  was  possible,  max-product  BP  al(cid:173) ways found the global minimum of the energy  (except  in few  cases  where it failed  to converge), while other approximation algorithms  of similar  complexity  did  not.  In  the  full  protein  data set,  max(cid:173) product  BP  always  found  a  lower  energy  configuration  than  the  other algorithms, including  a  widely  used  protein-folding software  (SCWRL).
Learning a Forward Model of a Reflex
Authors: Bernd Porr, Florentin Wörgötter
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We develop a systems theoretical treatment of a behavioural system that interacts with its environment in a closed loop situation such that its mo- tor actions inﬂuence its sensor inputs. The simplest form of a feedback is a reﬂex. Reﬂexes occur always “too late”; i.e., only after a (unpleas- ant, painful, dangerous) reﬂex-eliciting sensor event has occurred. This deﬁnes an objective problem which can be solved if another sensor input exists which can predict the primary reﬂex and can generate an earlier reaction. In contrast to previous approaches, our linear learning algo- rithm allows for an analytical proof that this system learns to apply feed- forward control with the result that slow feedback loops are replaced by their equivalent feed-forward controller creating a forward model. In other words, learning turns the reactive system into a pro-active system. By means of a robot implementation we demonstrate the applicability of the theoretical results which can be used in a variety of different areas in physics and engineering.
Information Regularization with Partially Labeled Data
Authors: Martin Szummer, Tommi S. Jaakkola
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Classiﬁcation with partially labeled data requires using a large number of unlabeled examples (or an estimated marginal P (x)), to further con- strain the conditional P (yjx) beyond a few available labeled examples. We formulate a regularization approach to linking the marginal and the conditional in a general way. The regularization penalty measures the information that is implied about the labels over covering regions. No parametric assumptions are required and the approach remains tractable even for continuous marginal densities P (x). We develop algorithms for solving the regularization problem for ﬁnite covers, establish a limiting differential equation, and exemplify the behavior of the new regulariza- tion approach in simple cases.
Mismatch String Kernels for SVM Protein Classification
Authors: Eleazar Eskin, Jason Weston, William S. Noble, Christina S. Leslie
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We introduce a class of string kernels, called mismatch kernels, for use with support vector machines (SVMs) in a discriminative approach to the protein classiﬁcation problem. These kernels measure sequence sim- ilarity based on shared occurrences of  -length subsequences, counted with up to mismatches, and do not rely on any generative model for the positive training sequences. We compute the kernels efﬁciently using a mismatch tree data structure and report experiments on a benchmark SCOP dataset, where we show that the mismatch kernel used with an SVM classiﬁer performs as well as the Fisher kernel, the most success- ful method for remote homology detection, while achieving considerable computational savings.
Adaptive Caching by Refetching
Authors: Robert B. Gramacy, Manfred K. Warmuth, Scott A. Brandt, Ismail Ari
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We are constructing caching policies that have 13-20% lower miss rates than the best of twelve baseline policies over a large variety of request streams. This represents an improvement of 49–63% over Least Recently Used, the most commonly implemented policy. We achieve this not by designing a speciﬁc new policy but by using on-line Machine Learning algorithms to dynamically shift between the standard policies based on their observed miss rates. A thorough experimental evaluation of our techniques is given, as well as a discussion of what makes caching an interesting on-line learning problem.
Timing and Partial Observability in the Dopamine System
Authors: Nathaniel D. Daw, Aaron C. Courville, David S. Touretzky
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: According to a series of inﬂuential models, dopamine (DA) neurons sig- nal reward prediction error using a temporal-difference (TD) algorithm. We address a problem not convincingly solved in these accounts: how to maintain a representation of cues that predict delayed consequences. Our new model uses a TD rule grounded in partially observable semi-Markov processes, a formalism that captures two largely neglected features of DA experiments: hidden state and temporal variability. Previous models pre- dicted rewards using a tapped delay line representation of sensory inputs; we replace this with a more active process of inference about the under- lying state of the world. The DA system can then learn to map these inferred states to reward predictions using TD. The new model can ex- plain previously vexing data on the responses of DA neurons in the face of temporal variability. By combining statistical model-based learning with a physiologically grounded TD theory, it also brings into contact with physiology some insights about behavior that had previously been conﬁned to more abstract psychological models.
Multiple Cause Vector Quantization
Authors: David A. Ross, Richard S. Zemel
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We propose a model that can learn parts-based representations of high- dimensional data. Our key assumption is that the dimensions of the data can be separated into several disjoint subsets, or factors, which take on values independently of each other. We assume each factor has a small number of discrete states, and model it using a vector quantizer. The selected states of each factor represent the multiple causes of the input. Given a set of training examples, our model learns the association of data dimensions with factors, as well as the states of each VQ. Inference and learning are carried out efﬁciently via variational algorithms. We present applications of this model to problems in image decomposition, collaborative ﬁltering, and text classiﬁcation.
Unsupervised Color Constancy
Authors: Kinh Tieu, Erik G. Miller
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: In [1] we introduced a linear statistical model of joint color changes in images due to variation in lighting and certain non-geometric camera pa- rameters. We did this by measuring the mappings of colors in one image of a scene to colors in another image of the same scene under different lighting conditions. Here we increase the ﬂexibility of this color ﬂow model by allowing ﬂow coefﬁcients to vary according to a low order polynomial over the image. This allows us to better ﬁt smoothly vary- ing lighting conditions as well as curved surfaces without endowing our model with too much capacity. We show results on image matching and shadow removal and detection.
Value-Directed Compression of POMDPs
Authors: Pascal Poupart, Craig Boutilier
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We examine the problem of generating state-space compressions of POMDPs in a way that minimally impacts decision quality. We analyze the impact of compres- sions on decision quality, observing that compressions that allow accurate policy evaluation (prediction of expected future reward) will not affect decision qual- ity. We derive a set of sufﬁcient conditions that ensure accurate prediction in this respect, illustrate interesting mathematical properties these confer on lossless lin- ear compressions, and use these to derive an iterative procedure for ﬁnding good linear lossy compressions. We also elaborate on how structured representations of a POMDP can be used to ﬁnd such compressions.
Constraint Classification for Multiclass Classification and Ranking
Authors: Sariel Har-Peled, Dan Roth, Dav Zimak
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: The constraint classiﬁcation framework captures many ﬂavors of mul- ticlass classiﬁcation including winner-take-all multiclass classiﬁcation, multilabel classiﬁcation and ranking. We present a meta-algorithm for learning in this framework that learns via a single linear classiﬁer in high dimension. We discuss distribution independent as well as margin-based generalization bounds and present empirical and theoretical evidence showing that constraint classiﬁcation beneﬁts over existing methods of multiclass classiﬁcation.
Neural Decoding of Cursor Motion Using a Kalman Filter
Authors: W Wu, M. J. Black, Y. Gao, M. Serruya, A. Shaikhouni, J. P. Donoghue, Elie Bienenstock
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: The direct neural control of external devices such as computer displays or prosthetic limbs requires the accurate decoding of neural activity rep- resenting continuous movement. We develop a real-time control system using the spiking activity of approximately 40 neurons recorded with an electrode array implanted in the arm area of primary motor cortex. In contrast to previous work, we develop a control-theoretic approach that explicitly models the motion of the hand and the probabilistic re- lationship between this motion and the mean ﬁring rates of the cells in 70 bins. We focus on a realistic cursor control task in which the sub- ject must move a cursor to “hit” randomly placed targets on a computer monitor. Encoding and decoding of the neural data is achieved with a Kalman ﬁlter which has a number of advantages over previous linear ﬁltering techniques. In particular, the Kalman ﬁlter reconstructions of hand trajectories in off-line experiments are more accurate than previ- ously reported results and the model provides insights into the nature of the neural coding of movement.
   
On the Dirichlet Prior and Bayesian Regularization
Authors: Harald Steck, Tommi S. Jaakkola
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: A  common  objective  in  learning  a  model  from  data is  to  recover  its network structure,  while the model parameters are of minor in(cid:173) terest.  For example,  we  may  wish  to  recover  regulatory  networks  from high-throughput data sources.  In  this paper we  examine how  Bayesian  regularization  using  a  product  of independent  Dirichlet  priors over  the model  parameters affects  the  learned model  struc(cid:173) ture  in  a  domain  with  discrete  variables.  We  show  that  a  small  scale  parameter - often interpreted as  "equivalent sample size"  or  "prior  strength"  - leads  to  a  strong  regularization  of  the  model  structure (sparse graph)  given a  sufficiently large data set.  In  par(cid:173) ticular, the empty graph is obtained in the limit of a vanishing scale  parameter.  This is  diametrically opposite to what one may expect  in  this  limit,  namely  the  complete graph from  an  (unregularized)  maximum likelihood estimate.  Since  the prior affects  the parame(cid:173) ters as  expected, the scale parameter balances a  trade-off  between  regularizing  the  parameters  vs.  the  structure  of  the  model.  We  demonstrate  the  benefits  of optimizing  this  trade-off in  the  sense  of predictive accuracy.
Forward-Decoding Kernel-Based Phone Recognition
Authors: Shantanu Chakrabartty, Gert Cauwenberghs
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Forward decoding kernel machines (FDKM) combine large-margin clas(cid:173) sifiers  with  hidden  Markov  models  (HMM)  for  maximum  a  posteriori  (MAP)  adaptive sequence estimation.  State  transitions  in the  sequence  are conditioned on observed data using a kernel-based probability model  trained with a recursive scheme that deals effectively with noisy and par(cid:173) tially labeled data.  Training over very large data sets is accomplished us(cid:173) ing a sparse probabilistic support vector machine (SVM) model based on  quadratic entropy, and an  on-line stochastic steepest descent algorithm.  For speaker-independent continuous phone recognition,  FDKM trained  over 177 ,080 samples of the TlMIT database achieves 80.6% recognition  accuracy over the full  test set, without use  of a prior phonetic language  model.
Optoelectronic Implementation of a FitzHugh-Nagumo Neural Model
Authors: Alexandre R. Romariz, Kelvin Wagner
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: An optoelectronic implementation of a spiking neuron model based on the FitzHugh-Nagumo equations is presented. A tunable semiconduc- tor laser source and a spectral ﬁlter provide a nonlinear mapping from driver voltage to detected signal. Linear electronic feedback completes the implementation, which allows either electronic or optical input sig- nals. Experimental results for a single system and numeric results of model interaction conﬁrm that important features of spiking neural mod- els can be implemented through this approach.
Margin-Based Algorithms for Information Filtering
Authors: Nicolò Cesa-bianchi, Alex Conconi, Claudio Gentile
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: In this work, we study an information ﬁltering model where the relevance labels associated to a sequence of feature vectors are realizations of an unknown probabilistic linear function. Building on the analysis of a re- stricted version of our model, we derive a general ﬁltering rule based on the margin of a ridge regression estimator. While our rule may observe the label of a vector only by classfying the vector as relevant, experiments on a real-world document ﬁltering problem show that the performance of our rule is close to that of the on-line classiﬁer which is allowed to observe all labels. These empirical results are complemented by a theo- retical analysis where we consider a randomized variant of our rule and prove that its expected number of mistakes is never much larger than that of the optimal ﬁltering rule which knows the hidden linear model.
Half-Lives of EigenFlows for Spectral Clustering
Authors: Chakra Chennubhotla, Allan D. Jepson
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Using a Markov chain perspective of spectral clustering we present an algorithm to automatically ﬁnd the number of stable clusters in a dataset. The Markov chain’s behaviour is characterized by the spectral properties of the matrix of transition probabilities, from which we derive eigenﬂows along with their halﬂives. An eigenﬂow describes the ﬂow of probabil- ity mass due to the Markov chain, and it is characterized by its eigen- value, or equivalently, by the halﬂife of its decay as the Markov chain is iterated. A ideal stable cluster is one with zero eigenﬂow and inﬁ- nite half-life. The key insight in this paper is that bottlenecks between weakly coupled clusters can be identiﬁed by computing the sensitivity of the eigenﬂow’s halﬂife to variations in the edge weights. We propose a novel EIGENCUTS algorithm to perform clustering that removes these identiﬁed bottlenecks in an iterative fashion.
The RA Scanner: Prediction of Rheumatoid Joint Inflammation Based on Laser Imaging
Authors: Anton Schwaighofer, Volker Tresp, Peter Mayer, Alexander K. Scheel, Gerhard A. Müller
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We describe the RA scanner, a novel system for the examination of pa- tients suffering from rheumatoid arthritis. The RA scanner is based on a novel laser-based imaging technique which is sensitive to the optical characteristics of ﬁnger joint tissue. Based on the laser images, ﬁnger joints are classiﬁed according to whether the inﬂammatory status has improved or worsened. To perform the classiﬁcation task, various lin- ear and kernel-based systems were implemented and their performances were compared. Special emphasis was put on measures to reliably per- form parameter tuning and evaluation, since only a very small data set was available. Based on the results presented in this paper, it was con- cluded that the RA scanner permits a reliable classiﬁcation of patholog- ical ﬁnger joints, thus paving the way for a further development from prototype to product stage.
Evidence Optimization Techniques for Estimating Stimulus-Response Functions
Authors: Maneesh Sahani, Jennifer F. Linden
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: An essential step in understanding the function of sensory nervous sys- tems is to characterize as accurately as possible the stimulus-response function (SRF) of the neurons that relay and process sensory informa- tion. One increasingly common experimental approach is to present a rapidly varying complex stimulus to the animal while recording the re- sponses of one or more neurons, and then to directly estimate a func- tional transformation of the input that accounts for the neuronal ﬁring. The estimation techniques usually employed, such as Wiener ﬁltering or other correlation-based estimation of the Wiener or Volterra kernels, are equivalent to maximum likelihood estimation in a Gaussian-output-noise regression model. We explore the use of Bayesian evidence-optimization techniques to condition these estimates. We show that by learning hyper- parameters that control the smoothness and sparsity of the transfer func- tion it is possible to improve dramatically the quality of SRF estimates, as measured by their success in predicting responses to novel input.
Binary Coding in Auditory Cortex
Authors: Michael R. Deweese, Anthony M. Zador
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Cortical neurons have been reported to use both rate and temporal  codes. Here we describe a novel mode in which each neuron  generates exactly 0 or 1 action potentials, but not more, in response  to a stimulus. We used cell-attached recording, which ensured  single-unit isolation, to record responses in rat auditory cortex to  brief tone pips. Surprisingly, the majority of neurons exhibited  binary behavior with few multi-spike responses; several dramatic  examples consisted of exactly one spike on 100% of trials, with no  trial-to-trial variability in spike count. Many neurons were tuned to  stimulus frequency. Since individual trials yielded at most one  spike for most neurons, the information about stimulus frequency  was encoded in the population, and would not have been accessible  to later stages of processing that only had access to the activity of a  single unit. These binary units allow a more efficient population  code than is possible with conventional rate coding units, and are  consistent with a model of cortical processing  in which  synchronous packets of spikes propagate stably from one neuronal  population to the next. 
1 B i n a r y c o d i n g i n a u d i t o r y c o r t e x 
We recorded responses of neurons in the auditory cortex of anesthetized rats to  pure-tone pips of different frequencies [1, 2]. Each pip was presented repeatedly,  allowing us to assess the variability of the neural response to multiple presentations  of each stimulus. We first recorded multi-unit activity with conventional tungsten  electrodes (Fig. 1a). The number of spikes in response to each pip fluctuated  markedly from one trial to the next (Fig. 1e), as though governed by a random  mechanism such as that generating the ticks of a Geiger counter. Highly variable  responses such as these, which are at least as variable as a Poisson process, are the  norm in the cortex [3-7], and have contributed to the widely held view that cortical  spike trains are so noisy that only the average firing rate can be used to encode  stimuli. 
Because we were recording the activity of an unknown number of neurons, we could  not be sure whether the strong trial-to-trial fluctuations reflected the underlying  variability of the single units. We therefore used an alternative technique, cell-
Learning Attractor Landscapes for Learning Motor Primitives
Authors: Auke J. Ijspeert, Jun Nakanishi, Stefan Schaal
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Many control problems take place in continuous state-action spaces, e.g., as in manipulator robotics, where the control objective is of- ten deﬂned as ﬂnding a desired trajectory that reaches a particular goal state. While reinforcement learning oﬁers a theoretical frame- work to learn such control policies from scratch, its applicability to higher dimensional continuous state-action spaces remains rather limited to date. Instead of learning from scratch, in this paper we suggest to learn a desired complex control policy by transforming an existing simple canonical control policy. For this purpose, we represent canonical policies in terms of diﬁerential equations with well-deﬂned attractor properties. By nonlinearly transforming the canonical attractor dynamics using techniques from nonparametric regression, almost arbitrary new nonlinear policies can be gener- ated without losing the stability properties of the canonical sys- tem. We demonstrate our techniques in the context of learning a set of movement skills for a humanoid robot from demonstrations of a human teacher. Policies are acquired rapidly, and, due to the properties of well formulated diﬁerential equations, can be re-used and modiﬂed on-line under dynamic changes of the environment. The linear parameterization of nonparametric regression moreover lends itself to recognize and classify previously learned movement skills. Evaluations in simulations and on an actual 30 degree-of- freedom humanoid robot exemplify the feasibility and robustness of our approach.
Combining Dimensions and Features in Similarity-Based Representations
Authors: Daniel J. Navarro, Michael D. Lee
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: This paper develops a new representational model of similarity data that combines continuous dimensions with discrete features. An al- gorithm capable of learning these representations is described, and a Bayesian model selection approach for choosing the appropriate number of dimensions and features is developed. The approach is demonstrated on a classic data set that considers the similarities between the numbers 0 through 9.
Bayesian Monte Carlo
Authors: Zoubin Ghahramani, Carl E. Rasmussen
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We investigate Bayesian alternatives to classical Monte Carlo methods for evaluating integrals. Bayesian Monte Carlo (BMC) allows the in- corporation of prior knowledge, such as smoothness of the integrand, into the estimation. In a simple problem we show that this outperforms any classical importance sampling method. We also attempt more chal- lenging multidimensional integrals involved in computing marginal like- lihoods of statistical models (a.k.a. partition functions and model evi- dences). We ﬁnd that Bayesian Monte Carlo outperformed Annealed Importance Sampling, although for very high dimensional problems or problems with massive multimodality BMC may be less adequate. One advantage of the Bayesian approach to Monte Carlo is that samples can be drawn from any distribution. This allows for the possibility of active design of sample points so as to maximise information gain.
A Model for Learning Variance Components of Natural Images
Authors: Yan Karklin, Michael S. Lewicki
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We present a hierarchical Bayesian model for learning efﬁcient codes of higher-order structure in natural images. The model, a non-linear gen- eralization of independent component analysis, replaces the standard as- sumption of independence for the joint distribution of coefﬁcients with a distribution that is adapted to the variance structure of the coefﬁcients of an efﬁcient image basis. This offers a novel description of higher- order image structure and provides a way to learn coarse-coded, sparse- distributed representations of abstract image properties such as object location, scale, and texture.
Nash Propagation for Loopy Graphical Games
Authors: Luis E. Ortiz, Michael Kearns
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We introduce NashProp, an iterative and local message-passing algo- rithm for computing Nash equilibria in multi-player games represented by arbitrary undirected graphs. We provide a formal analysis and exper- imental evidence demonstrating that NashProp performs well on large graphical games with many loops, often converging in just a dozen itera- tions on graphs with hundreds of nodes. NashProp generalizes the tree algorithm of (Kearns et al. 2001), and can be viewed as similar in spirit to belief propagation in probabilis- tic inference, and thus complements the recent work of (Vickrey and Koller 2002), who explored a junction tree approach. Thus, as for prob- abilistic inference, we have at least two promising general-purpose ap- proaches to equilibria computation in graphs.