mtybilly/Instruct2DS huggingface dataset:
Classification on Pairwise Proximity Data
Authors: Ralf Herbrich, Peter Bollmann-Sdorra, Klaus Obermayer Thore Graepel
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: We  investigate the problem of learning a classification task on data  represented in terms of their pairwise proximities.  This representa(cid:173) tion does  not refer  to an explicit feature  representation of the data  items and  is  thus  more  general than the standard approach  of us(cid:173) ing Euclidean feature vectors,  from  which  pairwise proximities can  always  be  calculated.  Our  first  approach  is  based  on  a  combined  linear  embedding  and  classification  procedure  resulting  in  an  ex(cid:173) tension of the Optimal Hyperplane algorithm to pseudo-Euclidean  data.  As  an  alternative  we  present  another  approach  based  on  a  linear threshold model in the proximity values themselves, which is  optimized using Structural Risk Minimization.  We  show that prior  knowledge about the problem can be incorporated by the choice of  distance measures and examine different metrics W.r.t.  their gener(cid:173) alization.  Finally, the algorithms are successfully applied to protein  structure  data  and  to  data from  the  cat's  cerebral  cortex.  They  show  better performance than K-nearest-neighbor classification.
Using Analytic QP and Sparseness to Speed Training of Support Vector Machines
Authors: John C. Platt
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: Training a Support Vector Machine (SVM) requires the solution of a very  large quadratic programming (QP) problem.  This paper proposes an  al(cid:173) gorithm for training SVMs:  Sequential Minimal Optimization,  or SMO.  SMO breaks the large QP problem into a series of smallest possible QP  problems which  are  analytically  solvable.  Thus,  SMO does not require  a numerical QP library.  SMO's computation time is dominated by eval(cid:173) uation  of the  kernel,  hence  kernel  optimizations  substantially  quicken  SMO. For the MNIST database, SMO is  1.7 times as fast as PCG chunk(cid:173) ing;  while for  the  UCI Adult database  and  linear SVMs,  SMO can  be  1500 times faster than the PCG chunking algorithm.
Dynamically Adapting Kernels in Support Vector Machines
Authors: Colin Campbell, John Shawe-Taylor Nello Cristianini
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: The kernel-parameter is one of the few  tunable parameters in  Sup(cid:173) port  Vector  machines,  controlling  the  complexity  of the  resulting  hypothesis.  Its  choice  amounts to model  selection  and  its  value  is  usually  found  by  means  of a  validation  set.  We  present  an  algo(cid:173) rithm which  can automatically perform  model  selection with little  additional computational cost and with no need of a validation set .  In  this  procedure  model  selection  and  learning  are  not  separate,  but  kernels  are  dynamically  adjusted  during  the  learning  process  to find  the kernel parameter which  provides the best possible upper  bound on  the  generalisation error.  Theoretical  results  motivating  the  approach  and  experimental  results  confirming  its  validity  are  presented.
Temporally Asymmetric Hebbian Learning, Spike liming and Neural Response Variability
Authors: Sen Song L. F. Abbott
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: Recent experimental data indicate that the strengthening or weakening of  synaptic connections between neurons depends on  the relative timing of  pre- and postsynaptic action potentials. A Hebbian synaptic modification  rule based on these data leads to a stable state in which the excitatory and  inhibitory inputs to a neuron are balanced, producing an irregular pattern  of firing.  It  has  been  proposed  that  neurons  in  vivo  operate  in  such  a  mode.
Learning Mixture Hierarchies
Authors: Andrew Lippman Nuno Vasconcelos
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: The hierarchical representation of data has various applications in do(cid:173) mains such as data mining, machine vision, or information retrieval. In  this paper we introduce an extension of the Expectation-Maximization  (EM) algorithm that learns mixture hierarchies in a computationally ef(cid:173) ficient manner. Efficiency is achieved by progressing in a bottom-up  fashion, i.e. by clustering the mixture components of a given level in the  hierarchy to obtain those of the level above. This cl ustering requires onl y  knowledge of the mixture parameters, there being no need to resort to  intermediate samples. In addition to practical applications, the algorithm  allows a new interpretation of EM that makes clear the relationship with  non-parametric kernel-based estimation methods, provides explicit con(cid:173) trol over the trade-off between the bias and variance of EM estimates, and  offers new insights about the behavior of deterministic annealing methods  commonly used with EM to escape local minima of the likelihood.
Optimizing Admission Control while Ensuring Quality of Service in Multimedia Networks via Reinforcement Learning
Authors: Hui Tong, Satinder P. Singh Timothy X. Brown
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: This  paper  examines  the  application  of  reinforcement  learning  to  a  telecommunications networking problem . The problem requires that rev(cid:173) enue  be  maximized  while  simultaneously  meeting  a  quality  of service  constraint  that  forbids  entry  into  certain  states.  We  present  a  general  solution  to  this  multi-criteria  problem  that  is  able  to  earn  significantly  higher revenues than alternatives.
Coding Time-Varying Signals Using Sparse, Shift-Invariant Representations
Authors: Terrence J. Sejnowski Michael S. Lewicki
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: A common way to represent a time series is to divide it into short(cid:173) duration blocks,  each of which is  then represented by a set of basis  functions.  A limitation of this approach, however, is  that the tem(cid:173) poral alignment of the basis functions with the underlying structure  in the time series is arbitrary.  We present an algorithm for encoding  a time series that does not require blocking the data.  The algorithm  finds  an efficient  representation by inferring the best temporal po(cid:173) sitions  for  functions  in  a  kernel  basis.  These  can  have  arbitrary  temporal  extent  and  are  not  constrained  to  be  orthogonal.  This  allows the model to capture structure in the signal that may occur  at arbitrary temporal positions and preserves the relative temporal  structure of underlying events.  The model is shown to be equivalent  to a  very sparse and highly over complete basis.  Under this model,  the mapping from  the data to the representation is  nonlinear,  but  can  be  computed  efficiently.  This form  also  allows  the  use  of ex(cid:173) isting methods for  adapting the basis itself to data.  This approach  is  applied to speech data and results in a shift invariant, spike-like  representation that resembles coding in the cochlear nerve.
Evidence for a Forward Dynamics Model in Human Adaptive Motor Control
Authors: Reza Shadmehr Nikhil Bhushan
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: Based  on  computational  principles,  the  concept  of  an  internal  model for  adaptive control has been divided  into a  forward  and an  inverse model.  However, there is as yet little evidence that learning  control by the eNS is through adaptation of one or the other.  Here  we  examine  two  adaptive control  architectures, one  based only on  the inverse model and other based on a combination of forward and  inverse  models.  We  then show that for  reaching movements of the  hand  in  novel  force  fields,  only  the  learning of the  forward  model  results  in  key  characteristics of performance  that match  the  kine(cid:173) matics of human subjects.  In  contrast, the adaptive control system  that relies only on the inverse model fails to produce the kinematic  patterns observed  in  the subjects,  despite the  fact  that it  is  more  stable.  Our results  provide evidence that learning control of novel  dynamics is  via formation of a  forward  model.
Restructuring Sparse High Dimensional Data for Effective Retrieval
Authors: Paul A. Viola Charles Lee Isbell Jr.
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: The task in text retrieval is to find  the subset of a collection of documents relevant  to  a user's  information request,  usually expressed as  a set of words.  Classically,  documents and queries are represented as  vectors of word counts.  In  its  simplest  form, relevance is  defined to be the dot product between a document and  a query  vector-a measure  of the  number of common  terms.  A  central  difficulty  in  text  retrieval  is  that  the  presence or absence  of a  word  is  not sufficient to  determine  relevance to a query. Linear dimensionality reduction has been proposed as a tech(cid:173) nique for extracting underlying structure from  the document collection.  In  some  domains  (such  as  vision)  dimensionality  reduction  reduces  computational com(cid:173) plexity.  In  text retrieval  it is  more often  used  to  improve retrieval  performance.  We  propose  an  alternative  and  novel  technique  that  produces  sparse  represen(cid:173) tations  constructed  from  sets  of highly-related  words.  Documents  and  queries  are  represented  by  their distance  to  these  sets,  and relevance  is  measured by  the  number of common clusters.  This technique significantly improves retrieval  per(cid:173) formance,  is  efficient  to  compute  and  shares  properties  with  the  optimal  linear  projection operator and the independent components of documents.
Approximate Learning of Dynamic Models
Authors: Daphne Koller Xavier Boyen
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: Inference is a key  component in  learning probabilistic models from par(cid:173) tially  observable  data.  When  learning  temporal  models,  each  of the  many  inference phases requires a  traversal  over an  entire long data se(cid:173) quence;  furthermore,  the  data structures manipulated are exponentially  large, making this process computationally expensive.  In [2], we describe  an approximate inference algorithm for monitoring stochastic processes,  and prove bounds on its approximation error.  In this paper, we apply this  algorithm as an approximate forward propagation step in an EM algorithm  for learning temporal Bayesian networks.  We provide a related approxi(cid:173) mation for the backward step, and prove error bounds for the  combined  algorithm.  We  show empirically that,  for a real-life domain,  EM  using  our inference algorithm  is  much  faster  than  EM  using exact inference,  with almost no degradation in quality of the learned model.  We  extend  our analysis  to  the  online learning  task,  showing a  bound  on  the  error  resulting  from  restricting  attention  to  a  small  window  of observations.  We  present an  online EM  learning algorithm for  dynamic systems,  and  show that it learns much faster than standard offline EM.
Independent Component Analysis of Intracellular Calcium Spike Data
Authors: Julia Börger, Alexander von zur Mühlen, Georg Brabant, Christof Schöfl Klaus Prank
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: Calcium (Ca2+)is an ubiquitous intracellular messenger which reg(cid:173) ulates cellular processes, such as secretion, contraction, and cell  proliferation. A number of different cell types respond to hormonal  stimuli with periodic oscillations of the intracellular free calcium  concentration ([Ca2+]i). These Ca2+ signals are often organized  in complex temporal and spatial patterns even under conditions  of sustained stimulation. Here we study the spatio-temporal as(cid:173) pects of intracellular calcium ([Ca 2+]i) oscillations in clonal J3-cells  (hamster insulin secreting cells, HIT) under pharmacological stim(cid:173) ulation (Schofi et al., 1996). We use a novel fast fixed-point al(cid:173) gorithm (Hyvarinen and Oja, 1997) for Independent Component  Analysis (ICA) to blind source separation of the spatio-temporal  dynamics of [Ca2+]i in a HIT-cell. Using this approach we find two  significant independent components out of five differently mixed in(cid:173) put signals: one [Ca2+]i signal with a mean oscillatory period of  68s and a high frequency signal with a broadband power spectrum  with considerable spectral density. This results is in good agree(cid:173) ment with a study on high-frequency [Ca2+]j oscillations (Palus  et al., 1998) Further theoretical and experimental studies have to  be performed to resolve the question on the functional impact of  intracellular signaling of these independent [Ca2+]i signals. 
932
A Model for Associative Multiplication
Authors: Suzanna Becker G. Bjorn Christianson
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: Despite the fact that mental arithmetic is  based on only a few  hun(cid:173) dred basic facts  and  some simple  algorithms, humans have a  diffi(cid:173) cult time  mastering the subject,  and  even  experienced  individuals  make  mistakes.  Associative  multiplication,  the  process  of doing  multiplication  by  memory  without the  use  of rules  or algorithms,  is  especially  problematic.  Humans  exhibit  certain  characteristic  phenomena in  performing associative  multiplications,  both in  the  type of error and  in  the error frequency.  We  propose a  model  for  the  process  of associative  multiplication,  and  compare  its  perfor(cid:173) mance  in  both  these  phenomena  with  data from  normal  humans  and from  the model proposed  by  Anderson  et al (1994).
Batch and On-Line Parameter Estimation of Gaussian Mixtures Based on the Joint Entropy
Authors: Manfred K. Warmuth Yoram Singer
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: We  describe  a  new  iterative method  for parameter estimation of Gaus(cid:173) sian  mixtures.  The new method is based on a framework developed by  Kivinen and Warmuth for supervised on-line learning. In contrast to gra(cid:173) dient descent and EM, which estimate the mixture's covariance matrices,  the proposed method estimates the inverses  of the covariance matrices.  Furthennore, the new parameter estimation procedure can  be applied in  both on-line and  batch settings.  We show experimentally that it is typi(cid:173) cally faster than EM, and usually requires about half as  many  iterations  as EM.
Learning Macro-Actions in Reinforcement Learning
Authors: Jette Randlov
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: We present a method for automatically constructing macro-actions from  scratch from primitive actions during the reinforcement learning process.  The  overall  idea is  to reinforce  the  tendency  to  perform action b after  action a  if such  a  pattern  of actions  has  been rewarded.  We  test  the  method on a bicycle task, the car-on-the-hill task, the race-track task and  some grid-world tasks.  For the  bicycle and race-track tasks  the use  of  macro-actions approximately halves the learning time, while for one of  the grid-world tasks  the learning time is  reduced by a  factor of 5.  The  method did not work for the car-on-the-hill task for reasons we discuss  in the conclusion.
Fast Neural Network Emulation of Dynamical Systems for Computer Animation
Authors: Demetri Terzopoulos, Geoffrey E. Hinton Radek Grzeszczuk
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: Computer animation through the numerical simulation of physics-based  graphics  models offers  unsurpassed realism,  but  it can be computation(cid:173) ally demanding. This paper demonstrates the possibility of replacing the  numerical simulation of nontrivial dynamic  models  with  a dramatically  more  efficient  "NeuroAnimator"  that  exploits  neural  networks.  Neu(cid:173) roAnimators  are  automatically  trained  off-line  to  emulate  physical  dy(cid:173) namics through  the observation  of physics-based models in  action.  De(cid:173) pending on  the model,  its  neural  network emulator can yield physically  realistic  animation  one  or  two  orders  of magnitude faster  than  conven(cid:173) tional  numerical simulation.  We  demonstrate NeuroAnimators for a va(cid:173) riety of physics-based models.
Improved Switching among Temporally Abstract Actions
Authors: Satinder P. Singh, Doina Precup, Balaraman Ravindran Richard S. Sutton
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: In robotics and other control applications it is commonplace to have a pre(cid:173) existing  set  of controllers  for  solving  subtasks,  perhaps  hand-crafted  or  previously learned or planned, and still face  a difficult problem of how to  choose and switch among the controllers to solve an overall task as well as  possible.  In this paper we present a framework based on Markov decision  processes and semi-Markov decision processes for phrasing this problem,  a basic theorem regarding the improvement in performance that can be ob(cid:173) tained by switching flexibly between given controllers, and example appli(cid:173) cations of the theorem.  In particular, we show how an  agent can plan with  these high-level controllers and then use the results of such planning to find  an even better plan, by modifying the existing controllers, with negligible  additional cost and no re-planning. In one of our examples, the complexity  of the problem is  reduced from  24 billion state-action pairs to  less than a  million state-controller pairs. 
In many applications, solutions to parts of a task are known, either because they were hand(cid:173) crafted  by  people  or because  they  were  previously  learned  or  planned.  For  example,  in  robotics applications, there may exist controllers for moving joints to  positions,  picking up  objects, controlling eye movements, or navigating along hallways.  More generally, an intelli(cid:173) gent system may have available to it several temporally extended courses of action to choose  from.  In such cases, a key challenge is  to  take full  advantage of the existing temporally ex(cid:173) tended actions, to choose or switch among them effectively, and to plan at their level rather  than at the level of individual actions. 
Recently, several researchers have begun to address these challenges within the framework of  reinforcement learning and Markov decision processes (e.g., Singh,  1992; Kaelbling,  1993;  Dayan & Hinton,  1993; Thrun and Schwartz,  1995;  Sutton,  1995;  Dietterich,  1998; Parr &  Russell,  1998;  McGovern, Sutton & Fagg,  1997).  Common to much of this recent work is  the  modeling  of a  temporally  extended action  as  a  policy  (controller)  and  a  condition  for  terminating,  which  we  together refer to  as  an  option  (Sutton,  Precup &  Singh,  1998).  In  this paper we consider the problem of effectively combining given  options into  one overall  policy, generalizing prior work by Kaelbling (1993).  Sections  1-3 introduce the framework;  our new results are in Sections 4 and 5. 
Improved Switching among Temporally Abstract Actions
Dynamics of Supervised Learning with Restricted Training Sets
Authors: David Saad Anthony C. C. Coolen
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: We  study  the  dynamics  of supervised  learning  in  layered  neural  net(cid:173) works,  in  the regime where the size p of the training set is  proportional  to the number N  of inputs.  Here the local fields  are no longer described  by  Gaussian  distributions.  We  use  dynamical  replica theory  to  predict  the  evolution  of macroscopic  observables,  including  the  relevant  error  measures, incorporating the old formalism  in the limit piN --t  00.
A Polygonal Line Algorithm for Constructing Principal Curves
Authors: Adam Krzyzak, Tamás Linder, Kenneth Zeger Balázs Kégl
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: Principal curves have  been  defined  as  "self consistent" smooth  curves  which pass through the "middle" of a d-dimensional probability distri(cid:173) bution or data cloud.  Recently, we  [1]  have offered a new approach by  defining principal curves as continuous curves of a  given length which  minimize the expected squared distance between the curve and points of  the space randomly chosen according to  a given distribution.  The new  definition made it possible to carry out a theoretical analysis of learning  principal curves from training data.  In this paper we propose a practical  construction based on the new definition.  Simulation results demonstrate  that the new algorithm compares favorably with previous methods both  in terms of performance and computational complexity.
Neuronal Regulation Implements Efficient Synaptic Pruning
Authors: Isaac Meilijson, Eytan Ruppin Gal Chechik
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: Human and animal studies show  that mammalian brain undergoes  massive synaptic pruning during childhood , removing about half of  the  synapses  until  puberty.  We  have  previously  shown  that main(cid:173) taining network  memory performance  while  synapses  are  deleted,  requires  that  synapses  are  properly  modified  and  pruned,  remov(cid:173) ing the weaker synapses.  We  now show that neuronal regulation , a  mechanism recently  observed  to maintain the average neuronal in(cid:173) put field , results in weight-dependent synaptic modification . Under  the  correct  range  of the  degradation  dimension  and  synaptic  up(cid:173) per  bound,  neuronal  regulation  removes  the  weaker  synapses  and  judiciously  modifies  the  remaining  synapses .  It implements  near  optimal synaptic modification, and  maintains the  memory perfor(cid:173) mance  of a  network  undergoing  massive  synaptic  pruning.  Thus ,  this  paper shows  that  in  addition to the  known effects  of Hebbian  changes,  neuronal  regulation  may  play  an  important  role  in  the  self-organization of brain networks during development.
Finite-Sample Convergence Rates for Q-Learning and Indirect Algorithms
Authors: Satinder P. Singh Michael J. Kearns
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: In  this  paper,  we  address  two  issues  of long-standing  interest  in  the  re(cid:173) inforcement  learning  literature.  First,  what  kinds  of performance  guar(cid:173) antees  can  be  made  for  Q-learning  after  only  a  finite  number  of actions?  Second,  what  quantitative  comparisons  can  be  made  between  Q-learning  and  model-based  (indirect)  approaches,  which  use  experience  to estimate  next-state  distributions  for  off-line  value  iteration?  We  first  show  that  both  Q-learning  and  the  indirect  approach  enjoy  rather  rapid  convergence  to  the  optimal  policy  as  a  function  of the num(cid:173) ber  of  state  transitions  observed.  In  particular,  on  the  order  of  only  (Nlog(1/c)/c2 )(log(N) + loglog(l/c))  transitions  are  sufficient  for  both  algorithms  to  come  within  c  of the  optimal  policy,  in  an  idealized  model  that  assumes  the  observed  transitions  are  "well-mixed"  throughout  an  N-state  MDP.  Thus,  the  two  approaches  have  roughly  the  same  sample  complexity.  Perhaps  surprisingly,  this  sample  complexity  is  far less  than  what is required for the model-based approach to actually construct a good  approximation  to  the  next-state  distribution.  The  result  also  shows  that  the  amount  of memory required  by  the model-based  approach  is  closer  to  N  than  to N 2 •  For  either  approach,  to  remove  the  assumption  that  the  observed  tran(cid:173) sitions  are  well-mixed,  we  consider  a  model  in  which  the  transitions  are  determined by a fixed,  arbitrary exploration policy.  Bounds on the number  of transitions  required  in  order  to  achieve  a  desired  level  of performance  are  then  related  to  the  stationary  distribution  and  mixing  time  of  this  policy.
Global Optimisation of Neural Network Models via Sequential Sampling
Authors: Mahesan Niranjan, Arnaud Doucet, Andrew H. Gee João F. G. de Freitas
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: We  propose a novel strategy for  training neural networks using se(cid:173) quential sampling-importance resampling algorithms.  This global  optimisation strategy allows  us  to learn the  probability distribu(cid:173) tion of the network  weights  in  a  sequential framework.  It is  well  suited to applications involving on-line, nonlinear, non-Gaussian or  non-stationary signal processing.
Linear Hinge Loss and Average Margin
Authors: Manfred K. Warmuth Claudio Gentile
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: We  describe a unifying method for proving relative loss  bounds for on(cid:173) line linear threshold classification algorithms, such as the Perceptron and  the Winnow algorithms.  For classification problems the discrete loss  is  used,  i.e., the total  number of prediction mistakes.  We  introduce a con(cid:173) tinuous loss function, called the "linear hinge loss", that can be employed  to derive the updates of the algorithms.  We  first  prove bounds w.r.t.  the  linear hinge loss  and  then  convert them  to  the  discrete  loss.  We  intro(cid:173) duce a notion of "average margin" of a set of examples .  We  show how  relative loss  bounds based on the  linear hinge  loss can  be converted to  relative loss bounds i.t.o.  the discrete loss using the average margin.
Learning Instance-Independent Value Functions to Enhance Local Search
Authors: Andrew G. Barto, Theodore J. Perkins, Richard S. Sutton Robert Moll
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: Reinforcement learning methods can be used to improve the performance  of local  search  algorithms  for  combinatorial  optimization  by  learning  an  evaluation  function  that  predicts  the  outcome  of search.  The  eval(cid:173) uation  function  is  therefore  able  to  guide  search  to  low-cost  solutions  better than  can  the original  cost function.  We  describe a  reinforcement  learning method for enhancing local search that combines aspects of pre(cid:173) vious work by Zhang and Dietterich (1995) and Boyan and Moore (1997,  Boyan  1998).  In  an  off-line  learning  phase,  a  value function  is  learned  that is  useful for guiding search for multiple problem sizes and instances.  We illustrate our technique by  developing several  such functions for the  Dial-A-Ride Problem.  Our learning-enhanced local  search algorithm ex(cid:173) hibits  an  improvement of more  then  30%  over  a  standard  local  search  algorithm.
Support Vector Machines Applied to Face Recognition
Authors: P. Jonathon Phillips
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: Face recognition is a K  class problem. where K  is the number of known  individuals;  and  support vector machines  (SVMs)  are a binary  classi(cid:173) fication method. By reformulating the face recognition problem and re(cid:173) interpreting the output of the SVM classifier. we developed a SVM -based  face recognition algorithm.  The face recognition problem is formulated  as a problem in difference space.  which models dissimilarities between  two facial images. In difference space we formulate face recognition as a  two class problem.  The classes are:  dissimilarities between faces  of the  same person.  and dissimilarities between faces  of different people.  By  modifying the interpretation of the decision surface generated by SVM.  we generated a similarity metric between faces  that is learned from ex(cid:173) amples of differences between faces.  The SVM-based algorithm is com(cid:173) pared with a principal component analysis (PeA) based algorithm on a  difficult set of images from the FEREf database. Performance was mea(cid:173) sured for both verification and identification scenarios. The identification  performance for SVM is 77-78% versus 54% for PCA. For verification.  the equal error rate is 7% for SVM and 13 % for PCA.
A Theory of Mean Field Approximation
Authors: Toshiyuki Tanaka
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: I present a theory of mean field  approximation based on information ge(cid:173) ometry.  This  theory  includes  in  a  consistent way  the  naive  mean  field  approximation, as well as the TAP approach and the  linear response the(cid:173) orem  in  statistical physics, giving clear information-theoretic interpreta(cid:173) tions to them.
Unsupervised and Supervised Clustering: The Mutual Information between Parameters and Observations
Authors: Jean-Pierre Nadal Didier Herschkowitz
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: Recent  works  in  parameter  estimation  and  neural  coding  have  demonstrated that optimal performance are related to the  mutual  information between parameters and data.  We  consider the mutual  information in  the case where  the dependency in the parameter (a  vector  8)  of  the  conditional  p.d.f.  of each  observation  (a  vector  0, is  through  the  scalar  product  8.~ only.  We  derive  bounds  and  asymptotic behaviour for  the mutual information and compare with  results  obtained on  the same model with the" replica technique" .
Stationarity and Stability of Autoregressive Neural Network Processes
Authors: Adrian Trapletti, Kurt Hornik Friedrich Leisch
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: We  analyze  the  asymptotic behavior of autoregressive  neural  net(cid:173) work  (AR-NN)  processes  using techniques from Markov chains and  non-linear time series  analysis.  It is  shown  that standard AR-NNs  without shortcut connections are  asymptotically stationary.  If lin(cid:173) ear  shortcut  connections  are  allowed,  only  the  shortcut  weights  determine whether the overall system is stationary, hence standard  conditions for  linear AR processes  can be  used.
A Principle for Unsupervised Hierarchical Decomposition of Visual Scenes
Authors: Michael Mozer
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: Structure in  a visual  scene can  be  described at many levels of granular(cid:173)
ity.  At a coarse level,  the  scene is  composed of objects;  at  a finer level, 
each object is made up of parts, and the parts of subparts. In this  work, I 
propose a simple principle by  which  such hierarchical  structure can  be 
extracted from  visual scenes: Regularity in the relations among different 
parts of an  object is  weaker than in  the  internal  structure of a part. This 
principle  can  be  applied  recursively  to  define  part-whole  relationships 
among elements  in  a scene.  The principle does  not make use  of object 
models,  categories,  or  other  sorts  of  higher-level  knowledge;  rather, 
part-whole relationships  can  be  established based  on  the  statistics  of a 
set of sample visual  scenes. I illustrate with a model that performs unsu(cid:173)
pervised  decomposition  of simple  scenes.  The  model  can  account  for 
the  results from  a human  learning experiment on  the  ontogeny  of part(cid:173)
whole relationships.
Gradient Descent for General Reinforcement Learning
Authors: Andrew W. Moore Leemon C. Baird III
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: A  simple  learning  rule  is  derived,  the  VAPS  algorithm,  which  can  be  instantiated  to  generate  a  wide  range  of  new  reinforcement(cid:173) learning  algorithms.  These  algorithms  solve  a  number  of  open  problems, define several new approaches to reinforcement learning,  and  unify  different  approaches  to  reinforcement  learning  under  a  single  theory.  These  algorithms  all  have  guaranteed  convergence,  and  include  modifications  of several  existing  algorithms  that  were  known  to  fail  to  converge  on  simple  MOPs.  These  include  Q(cid:173) In  addition  to  these  learning,  SARSA,  and  advantage  learning.  it  also  generates  pure  policy-search  value-based  algorithms  reinforcement-learning  algorithms,  which  learn  optimal  policies  without  learning  a  value  function.  search  and  value-based  algorithms  to  be  combined,  thus  unifying  two  very  different  approaches  to  reinforcement  learning  into  a  single  Value  and  Policy  Search  (V APS)  algorithm.  And  these  algorithms converge for  POMDPs without requiring a  proper belief  state .  Simulations  results  are  given,  and  several  areas  for  future  research are discussed. 
In  addition,  it  allows  policy(cid:173)
1  CONVERGENCE  OF  GREEDY  EXPLORATION 
Many  reinforcement-learning  algorithms  are  known  that  use  a  parameterized  function  approximator  to  represent  a  value  function,  and  adjust  the  weights  include  Q-learning,  SARSA,  and  incrementally  during  advantage  learning.  There  are  simple  MOPs  where  the  original  form  of  these  algorithms  fails  to  converge,  as  summarized  in  Table  1.  For the  cases  with..J,  the  algorithms  are  guaranteed  to  converge  under  reasonable  assumptions  such  as
Vertex Identification in High Energy Physics Experiments
Authors: Halina Abramowicz, David Horn Gideon Dror
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: In High Energy Physics experiments one has to sort through a high  flux  of events, at a  rate of tens of MHz,  and select  the few  that are  of interest.  One  of the  key  factors  in  making  this  decision  is  the  location of the vertex  where  the  interaction , that led  to the event ,  took  place.  Here  we  present  a  novel  solution  to  the  problem  of  finding  the  location  of the  vertex,  based  on  two  feedforward  neu(cid:173) ral  networks with fixed  architectures, whose parameters are chosen  so  as  to  obtain  a  high  accuracy.  The  system  is  tested  on  simu(cid:173) lated  data sets , and is  shown  to  perform better  than  conventional  algorithms.
Probabilistic Visualisation of High-Dimensional Binary Data
Authors: Michael E. Tipping
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: We  present a  probabilistic latent-variable framework for  data visu(cid:173) alisation,  a  key  feature  of which  is  its  applicability  to  binary and  categorical data types for  which few  established  methods exist.  A  variational approximation to the likelihood is exploited to derive a  fast  algorithm for  determining the model parameters.  Illustrations  of application to real and synthetic binary data sets are given.
Computation of Smooth Optical Flow in a Feedback Connected Analog Network
Authors: Rodney J. Douglas Alan Stocker
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: In  1986, Tanner and Mead [1] implemented an interesting constraint sat(cid:173) isfaction  circuit  for  global  motion  sensing  in  a VLSI.  We  report  here  a  new  and  improved a VLSI implementation that provides smooth optical  flow as well as global motion in a two dimensional visual field.  The com(cid:173) putation of optical flow  is  an ill-posed problem, which expresses itself as  the aperture problem.  However, the optical flow  can be estimated by the  use of regularization methods, in  which additional constraints are intro(cid:173) duced in  terms of a global energy functional that must be minimized . We  show how the algorithmic constraints of Hom and Schunck [2]  on com(cid:173) puting smooth optical flow can be mapped onto the physical constraints  of an equivalent electronic network.
Applications of Multi-Resolution Neural Networks to Mammography
Authors: Paul Sajda Clay Spence
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: We  have  previously  presented  a  coarse-to-fine  hierarchical  pyra(cid:173) mid/neural  network  (HPNN)  architecture  which  combines  multi(cid:173) scale  image  processing  techniques  with  neural  networks.  In  this  paper  we  present  applications  of  this  general  architecture  to  two  problems  in  mammographic  Computer-Aided  Diagnosis  (CAD).  The  first  application  is  the  detection  of  microcalcifications.  The  <:oarse-to-fine  HPNN  was  designed  to learn  large-scale  context  in(cid:173) formation  for  detecting  small objects  like  microcalcifications.  Re(cid:173) ceiver  operating  characteristic  (ROC)  analysis  suggests  that  the  hierarchical  architecture  improves  detection  performance  of a  well  established  CAD  system by  roughly  50 %.  The second  application  is  to detect mammographic masses directly.  Since masses are large,  extended objects,  the coarse-to-fine HPNN architecture is  not suit(cid:173) able for  this  problem.  Instead we  construct  a fine-to-coarse  HPNN  architecture which  is  designed  to  learn  small-scale detail  structure  associated  with  the extended  objects.  Our initial  results  applying  the  fine-to-coarse  HPNN  to  mass  detection  are  encouraging,  with  detection  performance  improvements  of about  36 %.  We  conclude  that the ability of the HPNN architecture to integrate information  across  scales,  both  coarse-to-fine  and  fine-to-coarse,  makes  it  well  suited  for  detecting  objects  which  may  have  contextual  clues  or  detail structure occurring at scales  other than  the  natural scale of  the object.
Robot Docking Using Mixtures of Gaussians
Authors: Roderick Murray-Smith, Volker Hansen Matthew M. Williamson
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: This  paper applies  the  Mixture  of Gaussians  probabilistic model,  com(cid:173) bined  with  Expectation Maximization  optimization  to  the  task  of sum(cid:173) marizing three dimensional range data for a mobile robot.  This provides  a flexible way of dealing with uncertainties in sensor information, and al(cid:173) lows the introduction of prior knowledge into low-level perception mod(cid:173) ules.  Problems with the basic approach were solved in  several ways:  the  mixture of Gaussians was reparameterized to reflect the types of objects  expected  in  the  scene,  and  priors  on  model  parameters  were  included  in  the  optimization  process.  Both approaches force  the  optimization  to  find  'interesting'  objects,  given the  sensor and object characteristics.  A  higher level  classifier  was  used  to  interpret the  results  provided by  the  model, and to reject spurious solutions.
Semi-Supervised Support Vector Machines
Authors: Ayhan Demiriz Kristin P. Bennett
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: We  introduce  a  semi-supervised  support  vector  machine  (S3yM)  method.  Given  a  training  set  of labeled  data  and  a  working  set  of unlabeled  data,  S3YM  constructs  a  support vector  machine us(cid:173) ing  both  the  training  and  working  sets.  We  use  S3 YM  to  solve  the  transduction  problem  using  overall  risk  minimization  (ORM)  posed  by  Yapnik.  The  transduction  problem  is  to  estimate  the  value of a  classification function at the given points in the working  set.  This  contrasts  with  the  standard inductive  learning  problem  of estimating the  classification  function  at  all  possible values  and  then  using  the  fixed  function  to  deduce  the classes  of the working  set  data.  We  propose  a  general  S3YM  model  that minimizes both  the  misclassification  error  and  the  function  capacity  based  on  all  the available data.  We show  how the S3YM  model  for  I-norm lin(cid:173) ear  support  vector  machines  can  be  converted  to  a  mixed-integer  program  and then solved exactly using  integer  programming.  Re(cid:173) sults  of S3YM  and  the  standard  I-norm  support  vector  machine  approach  are  compared  on  ten  data sets.  Our  computational  re(cid:173) sults  support  the statistical  learning  theory  results  showing  that  incorporating  working  data  improves  generalization  when  insuffi(cid:173) cient  training information is  available.  In every case,  S3YM  either  improved or showed no significant difference in generalization com(cid:173) pared to the traditional approach. 
Semi-Supervised Support  Vector Machines
A Phase Space Approach to Minimax Entropy Learning and the Minutemax Approximations
Authors: Alan L. Yuille James M. Coughlan
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: There  has  been  much  recent  work  on  measuring  image  statistics  and  on  learning  probability  distributions  on  images.  We  observe  that  the  mapping  from  images  to  statistics  is  many-to-one  and  show  it  can  be  quantified  by  a  phase  space  factor.  This  phase  space approach throws light on the Minimax Entropy technique for  learning Gibbs distributions on images with potentials derived from  image statistics and elucidates the ambiguities that are inherent to  determining the potentials.  In  addition, it shows that if the phase  factor  can  be  approximated  by  an  analytic  distribution  then  this  approximation  yields  a  swift  "Minutemax"  algorithm  that  vastly  reduces  the  computation  time  for  Minimax entropy  learning.  An  illustration  of this  concept,  using  a  Gaussian  to  approximate  the  phase  factor,  gives  a  good  approximation  to  the  results  of  Zhu  and  Mumford  (1997)  in  just  seconds  of  CPU  time.  The  phase  space  approach  also  gives  insight  into  the  multi-scale  potentials  found  by  Zhu and Mumford  (1997)  and suggests that the forms  of  the potentials are influenced greatly by phase space considerations.  Finally,  we  prove  that probability distributions  learned  in  feature  space  alone  are  equivalent  to  Minimax  Entropy  learning  with  a  multinomial approximation of the phase factor.
Almost Linear VC Dimension Bounds for Piecewise Polynomial Networks
Authors: Vitaly Maiorov, Ron Meir Peter L. Bartlett
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: We  compute  upper  and  lower  bounds  on  the  VC  dimension  of  feedforward  networks  of  units  with  piecewise  polynomial  activa(cid:173) tion functions.  We  show that if the number of layers is  fixed,  then  the  VC  dimension  grows  as  W log W,  where  W  is  the  number of  parameters in the network.  This result stands in opposition to the  case  where  the  number of  layers  is  unbounded,  in  which  case  the  VC  dimension grows as W 2 •
Bayesian Modeling of Facial Similarity
Authors: Tony Jebara, Alex Pentland Baback Moghaddam
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: In  previous work  [6, 9, 10],  we  advanced a  new technique for  direct  visual  matching  of  images  for  the  purposes  of  face  recognition  and  image  retrieval ,  using  a  probabilistic  measure  of  similarity  based  primarily  on  a  Bayesian  (MAP)  analysis  of image  differ(cid:173) ences,  leading  to  a  "dual"  basis  similar  to  eigenfaces  [13].  The  performance  advantage  of  this  probabilistic  matching  technique  over  standard  Euclidean  nearest-neighbor  eigenface  matching was  recently demonstrated using results from DARPA's 1996  "FERET"  face  recognition  competition, in  which  this  probabilistic matching  algorithm  was  found  to  be  the  top  performer.  We  have  further  developed  a  simple  method  of replacing  the  costly  com put ion  of  nonlinear  (online)  Bayesian  similarity  measures  by  the  relatively  inexpensive  computation  of  linear  (offline)  subspace  projections  and simple (online)  Euclidean norms, thus resulting in a significant  computational speed-up for  implementation with very  large image  databases  as typically encountered  in  real-world  applications.
The Bias-Variance Tradeoff and the Randomized GACV
Authors: Xiwu Lin, Fangyu Gao, Dong Xiang, Ronald Klein, Barbara Klein Grace Wahba
Published in: Advances in Neural Information Processing Systems 11  (NIPS 1998) (Main Conference Track), 1998

Abstract: We  propose a new in-sample cross validation based method (randomized  GACV) for choosing smoothing or bandwidth parameters that govern the  bias-variance or fit-complexity tradeoff in  'soft' classification.  Soft clas(cid:173) sification refers to  a  learning procedure which  estimates the probability  that an example with a given attribute vector is  in  class  1 vs  class O.  The  target  for  optimizing  the  the  tradeoff is  the  Kullback-Liebler distance  between  the  estimated  probability  distribution  and  the  'true'  probabil(cid:173) ity  distribution,  representing  knowledge of an  infinite  population.  The  method uses a randomized estimate of the trace of a Hessian and mimics  cross validation at the cost of a single relearning with perturbed outcome  data.