mtybilly/Instruct2DS huggingface dataset:
`N-Body' Problems in Statistical Learning
Authors: Alexander G. Gray, Andrew W. Moore
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  present  efficient  algorithms for  all-point-pairs  problems ,  or  'N(cid:173) body '-like problems, which  are  ubiquitous in statistical learning.  We  focus on six examples, including nearest-neighbor classification, kernel  density  estimation,  outlier  detection ,  and  the  two-point  correlation.  These include any problem which abstractly requires  a comparison of  each  of the  N  points  in  a  dataset  with  each  other  point  and  would  naively  be  solved  using  N 2  distance  computations.  In  practice  N  is  often  large  enough  to  make this  infeasible.  We  present  a  suite  of  new  geometric  t echniques  which  are  applicable  in  principle  to  any  'N-body'  computation  including  large-scale  mixtures  of  Gaussians,  RBF neural networks,  and HMM 's.  Our  algorithms exhibit favorable  asymptotic  scaling  and  are  empirically  several  orders  of magnitude  faster  than  the  naive  computation,  even  for  small datasets.  We  are  aware of no exact  algorithms for  these  problems which  are  more effi(cid:173) cient  either  empirically  or  theoretically.  In  addition,  our framework  yields  simple and  elegant  algorithms.  It also  permits two  important  generalizations  beyond  the  standard  all-point-pairs  problems,  which  are  more difficult.  These  are  represented  by  our final  examples,  the  multiple two-point correlation  and the  notorious n-point correlation.
A Silicon Primitive for Competitive Learning
Authors: David Hsu, Miguel Figueroa, Chris Diorio
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Competitive  learning  is  a  technique  for  training  classification  and  clustering  networks.  We  have  designed  and  fabricated  an  11- transistor primitive,  that  we  term  an  automaximizing  bump  circuit,  that  implements  competitive  learning  dynamics.  The  circuit  per(cid:173) forms  a  similarity  computation,  affords  nonvolatile  storage,  and  implements  simultaneous  local  adaptation  and  computation.  We  show  that  our  primitive  is  suitable  for  implementing  competitive  learning  in  VLSI,  and  demonstrate  its  effectiveness  in  a  standard  clustering task.
Propagation Algorithms for Variational Bayesian Learning
Authors: Zoubin Ghahramani, Matthew J. Beal
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Variational  approximations  are  becoming  a  widespread  tool  for  Bayesian learning of graphical models.  We  provide  some theoret(cid:173) ical  results for  the variational updates in a  very  general family  of  conjugate-exponential graphical  models.  We  show  how  the  belief  propagation  and  the junction  tree  algorithms  can  be  used  in  the  inference step of variational Bayesian learning.  Applying these re(cid:173) sults to the Bayesian analysis of linear-Gaussian state-space models  we  obtain a  learning procedure that exploits the Kalman smooth(cid:173) ing propagation, while  integrating over  all  model parameters.  We  demonstrate how  this can be used to infer the hidden state dimen(cid:173) sionality of the state-space model in a variety of synthetic problems  and one  real high-dimensional data set.
An Adaptive Metric Machine for Pattern Classification
Authors: Carlotta Domeniconi, Jing Peng, Dimitrios Gunopulos
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Nearest neighbor  classification assumes locally constant class con(cid:173) ditional  probabilities.  This  assumption  becomes  invalid  in  high  dimensions with finite  samples due to the curse of dimensionality.  Severe  bias  can be  introduced  under these  conditions  when  using  the  nearest  neighbor  rule.  We  propose  a  locally  adaptive  nearest  neighbor  classification  method to try to  minimize  bias.  We  use  a  Chi-squared distance analysis to compute a flexible  metric for pro(cid:173) ducing neighborhoods that are elongated along less relevant feature  dimensions and constricted along most influential ones.  As a result,  the class conditional probabilities tend to be smoother in the mod(cid:173) ified neighborhoods, whereby better classification performance can  be achieved.  The efficacy of our method is validated and compared  against other techniques using a variety of real world data.
On Iterative Krylov-Dogleg Trust-Region Steps for Solving Neural Networks Nonlinear Least Squares Problems
Authors: Eiji Mizutani, James Demmel
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: This  paper  describes  a  method of dogleg  trust-region  steps,  or re(cid:173) stricted  Levenberg-Marquardt  steps,  based  on  a  projection  pro(cid:173) cess  onto the  Krylov subspaces  for  neural  networks  nonlinear least  squares problems.  In particular, the linear conjugate gradient (CG)  method  works  as  the  inner iterative  algorithm for  solving  the  lin(cid:173) earized  Gauss-Newton normal equation, whereas  the  outer nonlin(cid:173) ear algorithm repeatedly  takes so-called  "Krylov-dogleg"  steps, re(cid:173) lying only on matrix-vector multiplication without explicitly form(cid:173) ing the Jacobian matrix or the Gauss-Newton model Hessian.  That  is,  our  iterative  dogleg  algorithm  can  reduce  both  operational  counts  and  memory space  by  a  factor  of O(n)  (the number of pa(cid:173) rameters)  in comparison with a  direct  linear-equation solver.  This  memory-less property is  useful  for  large-scale  problems.
Hierarchical Memory-Based Reinforcement Learning
Authors: Natalia Hernandez-Gardiol, Sridhar Mahadevan
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Sridhar  Mahadevan 
Department of Computer Science 
Michigan State University  East Lansing,  MI  48824  mahadeva@cse.msu.edu 
A  key  challenge  for  reinforcement  learning  is  scaling  up  to  large  partially  observable  domains.  In this paper,  we  show  how  a  hier(cid:173) archy of behaviors can be used to create and select among variable  length short-term memories  appropriate for  a task.  At  higher lev(cid:173) els  in  the  hierarchy,  the  agent  abstracts  over  lower-level  details  and  looks  back  over  a  variable  number  of high-level  decisions  in  time.  We  formalize  this  idea  in  a  framework  called  Hierarchical  Suffix Memory (HSM).  HSM  uses a memory-based SMDP learning  method  to  rapidly  propagate  delayed  reward  across  long  decision  sequences.  We  describe  a  detailed  experimental  study  comparing  memory  vs.  hierarchy  using  the  HSM  framework  on  a  realistic  corridor navigation task.
Second Order Approximations for Probability Models
Authors: Hilbert J. Kappen, Wim Wiegerinck
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: In  this  paper,  we  derive  a  second  order mean  field  theory  for  directed  graphical  probability  models.  By  using  an  information  theoretic  argu(cid:173) ment  it  is  shown  how  this  can  be  done  in  the  absense  of a  partition  function.  This method is  a direct generalisation of the well-known TAP  approximation for  Boltzmann Machines.  In  a numerical  example,  it is  shown  that the  method  greatly  improves  the  first  order mean  field  ap(cid:173) proximation.  For a restricted class of graphical models, so-called single  overlap graphs, the second order method has comparable complexity to  the first order method.  For sigmoid belief networks, the method is shown  to be particularly fast and effective.
Feature Selection for SVMs
Authors: Jason Weston, Sayan Mukherjee, Olivier Chapelle, Massimiliano Pontil, Tomaso Poggio, Vladimir Vapnik
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We introduce a method of feature selection for Support Vector Machines.  The method is based upon finding those features which minimize bounds  on  the leave-one-out error.  This  search can be efficiently performed via  gradient descent.  The resulting  algorithms  are  shown to  be  superior to  some standard feature selection algorithms on both toy data and real-life  problems of face  recognition, pedestrian detection  and  analyzing DNA  micro array data.
Constrained Independent Component Analysis
Authors: Wei Lu, Jagath C. Rajapakse
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: The  paper  presents  a  novel  technique  of constrained  independent  component analysis  (CICA)  to introduce constraints into the clas(cid:173) sical ICA and solve the constrained optimization problem by using  Lagrange  multiplier  methods.  This  paper  shows  that  CICA  can  be used to order the resulted independent components in a specific  manner and normalize the demixing matrix in the signal separation  procedure.  It can systematically eliminate the ICA's indeterminacy  on permutation and dilation.  The experiments demonstrate the use  of CICA  in  ordering of  independent  components  while  providing  normalized demixing processes.  Keywords:  Independent  component  analysis, constrained indepen(cid:173) dent component analysis, constrained optimization, Lagrange mul(cid:173) tiplier methods
The Early Word Catches the Weights
Authors: Mark A. Smith, Garrison W. Cottrell, Karen L. Anderson
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: The strong correlation between the frequency of words and their naming  latency has been well documented.  However, as  early as  1973, the  Age  of Acquisition (AoA) of a word was  alleged to be the actual  variable of  interest, but these studies  seem to  have been ignored in  most of the lit(cid:173) erature.  Recently, there has been a resurgence of interest in AoA. While  some studies have shown that frequency has no effect when AoA is con(cid:173) trolled for,  more recent studies have found independent contributions of  frequency and AoA. Connectionist models have repeatedly shown strong  effects  of frequency,  but  little  attention  has  been  paid  to  whether they  can also  show  AoA effects.  Indeed,  several researchers have explicitly  claimed  that they  cannot  show  AoA  effects.  In  this  work,  we  explore  these claims using a simple feed forward neural network.  We find  a sig(cid:173) nificant  contribution  of AoA  to  naming  latency,  as  well  as  conditions  under which frequency provides an independent contribution.
The Manhattan World Assumption: Regularities in Scene Statistics which Enable Bayesian Inference
Authors: James M. Coughlan, Alan L. Yuille
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Preliminary work by the authors made use of the so-called  "Man(cid:173) hattan  world"  assumption  about  the  scene  statistics  of  city  and  indoor scenes.  This assumption stated that such  scenes were built  on a  cartesian grid which led to regularities in the image edge gra(cid:173) dient  statistics.  In this paper we  explore the general applicability  of this  assumption  and show  that,  surprisingly,  it holds  in a  large  variety of less structured environments including rural scenes.  This  enables us, from  a single image, to determine the orientation of the  viewer relative to the scene structure and also to detect target ob(cid:173) jects  which  are  not  aligned  with  the  grid.  These  inferences  are  performed  using  a  Bayesian  model  with  probability  distributions  (e.g.  on the image gradient statistics)  learnt from  real data.
Processing of Time Series by Neural Circuits with Biologically Realistic Synaptic Dynamics
Authors: Thomas Natschläger, Wolfgang Maass, Eduardo D. Sontag, Anthony M. Zador
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Experimental data show that biological synapses behave quite differently  from the symbolic synapses in common artificial neural network models.  Biological synapses are dynamic, i.e., their "weight" changes on  a short  time  scale  by  several  hundred percent in  dependence of the  past  input  to  the  synapse.  In  this  article  we  explore  the  consequences  that  these  synaptic  dynamics  entail  for  the  computational  power  of feedforward  neural  networks. We  show that gradient descent suffices to  approximate  a given  (quadratic) filter  by  a rather small  neural  system  with  dynamic  synapses.  We  also  compare our network model to  artificial  neural net(cid:173) works  designed  for  time  series  processing.  Our  numerical  results  are  complemented by  theoretical analysis which  show  that even with just a  single hidden layer such networks can approximate a surprisingly large  large  class  of nonlinear filters:  all  filters  that  can  be  characterized  by  Volterra series. This result is robust with regard to various changes in the  model for synaptic dynamics.
Machine Learning for Video-Based Rendering
Authors: Arno Schödl, Irfan A. Essa
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  present  techniques  for  rendering  and  animation  of  realistic  scenes  by  analyzing  and  training  on  short  video  sequences.  This  work extends the new paradigm for computer animation, video  tex(cid:173) tures,  which  uses  recorded video  to generate  novel  animations  by  replaying the  video  samples  in  a  new  order.  Here  we  concentrate  on  video  sprites,  which  are  a  special  type  of  video  texture.  In  video  sprites,  instead of storing whole  images,  the  object  of inter(cid:173) est  is  separated  from  the  background  and  the  video  samples  are  stored as  a sequence of alpha-matted sprites with associated veloc(cid:173) ity information.  They can be  rendered anywhere  on the screen to  create a novel animation of the object.  We present methods to cre(cid:173) ate  such  animations  by  finding  a  sequence  of sprite  samples  that  is  both  visually  smooth  and  follows  a  desired  path.  To  estimate  visual  smoothness,  we  train  a  linear  classifier  to  estimate  visual  similarity  between video  samples.  If the  motion  path is  known in  advance,  we  use  beam search to find  a  good sample sequence.  We  can specify the motion interactively by precomputing the sequence  cost  function  using Q-Iearning.
Discovering Hidden Variables: A Structure-Based Approach
Authors: Gal Elidan, Noam Lotner, Nir Friedman, Daphne Koller
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: A serious problem in learning probabilistic models is the presence of hid(cid:173) den variables. These variables are not observed, yet interact with several  of the observed variables.  As  such,  they induce seemingly complex de(cid:173) pendencies  among  the  latter.  In  recent years,  much  attention  has  been  devoted to  the  development of algorithms for  learning parameters,  and  in  some cases  structure, in  the presence of hidden variables.  In this  pa(cid:173) per,  we  address  the  related  problem of detecting  hidden  variables  that  interact with the observed variables.  This problem is of interest both for  improving our understanding of the domain and as a preliminary step that  guides the learning procedure towards promising models.  A very natural  approach is  to  search for "structural  signatures" of hidden variables - substructures in the learned network that tend to  suggest the presence of  a hidden variable.  We  make this  basic  idea concrete, and  show  how  to  integrate it with structure-search algorithms.  We evaluate this method on  several synthetic and real-life datasets, and show that it performs surpris(cid:173) ingly well.
FaceSync: A Linear Operator for Measuring Synchronization of Video Facial Images and Audio Tracks
Authors: Malcolm Slaney, Michele Covell
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: FaceSync  is  an  optimal  linear  algorithm  that  finds  the  degree  of syn(cid:173) chronization  between  the  audio  and  image  recordings  of  a  human  speaker.  Using canonical correlation,  it finds  the best direction  to com(cid:173) bine  all  the  audio  and  image data,  projecting  them  onto  a  single  axis.  FaceSync uses  Pearson's correlation to  measure the degree of synchro(cid:173) nization between the audio and image data. We derive the optimal linear  transform to combine the audio and visual information and describe an  implementation that avoids  the  numerical problems caused by comput(cid:173) ing the correlation matrices. 
1  Motivation  In many applications, we want to know about the synchronization between an audio signal  and  the corresponding image data.  In a teleconferencing system,  we might want to know  which of the several people imaged by a camera is  heard by the microphones; then, we can  direct the camera to the speaker. In post-production for a film,  clean audio dialog is  often  dubbed over the  video;  we  want to  adjust the  audio  signal  so  that the lip-sync is  perfect.  When analyzing a film,  we want to know when the person talking is in the shot, instead of  off camera. When evaluating the quality of dubbed films,  we can measure of how  well  the  translated words and audio fit  the actor's face. 
This paper describes an algorithm, FaceSync, that measures the degree of synchronization  between the video image of a face and the associated audio signal. We can do this task by  synthesizing the talking face,  using techniques  such  as Video  Rewrite  [1], and then com(cid:173) paring the synthesized video with the test video. That process, however, is expensive. Our  solution finds  a linear operator that, when applied to the audio and video signals, generates  an  audio-video-synchronization-error  signal.  The  linear  operator  gathers  information  from throughout the image and thus allows us to do the computation inexpensively.  Hershey and Movellan  [2]  describe an approach based on measuring the mutual informa(cid:173) tion between the audio signal and individual pixels in the  video. The correlation between  the audio signal, x, and one pixel in the image y,  is  given by Pearson's correlation,  r.  The  mutual information between these two  variables is  given by f(x,y)  = -1/2  log(l-?). They  create movies that show the regions of the video that have high correlation with the audio; 

Currently at IBM Almaden Research, 650 Harry Road, San Jose, CA 95120.  2.  Currently at Yes Video. com, 2192 Fortune Drive, San Jose, CA 95131.
What Can a Single Neuron Compute?
Authors: Blaise Agüera y Arcas, Adrienne L. Fairhall, William Bialek
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: In this  paper  we  formulate  a  description  of the  computation  per(cid:173) formed  by  a  neuron  as  a  combination  of  dimensional  reduction  and nonlinearity.  We  implement this description for  the Hodgkin(cid:173) Huxley model,  identify the most  relevant  dimensions  and find  the  nonlinearity.  A  two  dimensional  description  already  captures  a  significant  fraction  of the information that  spikes  carry about  dy(cid:173) namic inputs.  This description  also shows that computation in the  Hodgkin-Huxley  model  is  more  complex  than  a  simple  integrate(cid:173) and-fire or perceptron model.
Tree-Based Modeling and Estimation of Gaussian Processes on Graphs with Cycles
Authors: Martin J. Wainwright, Erik B. Sudderth, Alan S. Willsky
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  present  the embedded  trees  algorithm,  an  iterative technique  for  estimation  of Gaussian  processes  defined  on  arbitrary  graphs.  By exactly solving a series of modified problems on embedded span(cid:173) ning  trees,  it  computes  the  conditional  means  with  an  efficiency  comparable to or better than other techniques.  Unlike other meth(cid:173) ods,  the  embedded trees  algorithm  also  computes  exact  error  co(cid:173) variances.  The error  covariance  computation  is  most  efficient  for  graphs in  which  removing a  small number of edges  reveals an em(cid:173) bedded  tree.  In  this  context,  we  demonstrate  that  sparse  loopy  graphs  can  provide  a  significant  increase  in  modeling  power  rela(cid:173) tive to trees,  with only a  minor increase in  estimation complexity.
Foundations for a Circuit Complexity Theory of Sensory Processing
Authors: Robert A. Legenstein, Wolfgang Maass
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We introduce total wire length as salient complexity measure for an anal(cid:173) ysis of the circuit complexity of sensory processing in biological neural  systems and neuromorphic engineering. This new complexity measure is  applied to a set of basic computational problems that apparently need to  be solved by circuits for translation- and scale-invariant sensory process(cid:173) ing.  We  exhibit new  circuit design strategies  for these  new  benchmark  functions that can be implemented within realistic complexity bounds, in  particular with linear or almost linear total  wire length.
Bayes Networks on Ice: Robotic Search for Antarctic Meteorites
Authors: Liam Pedersen, Dimitrios Apostolopoulos, William Whittaker
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: A  Bayes  network  based  classifier  for  distinguishing  terrestrial  rocks  from  meteorites  is  implemented  onboard  the  Nomad  robot.  Equipped with a camera,  spectrometer and eddy current sensor, this  robot searched the  ice  sheets of Antarctica and autonomously made  the first robotic identification of a meteorite, in January 2000 at the  Elephant Moraine.  This paper discusses  rock classification from  a  robotic platform, and describes the system onboard Nomad.
Learning and Tracking Cyclic Human Motion
Authors: Dirk Ormoneit, Hedvig Sidenbladh, Michael J. Black, Trevor Hastie
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  present  methods  for  learning  and  tracking  human  motion  in  video.  We  estimate  a  statistical model of typical  activities from  a  large  set  of 3D  periodic  human  motion data  by  segmenting these  data automatically into  "cycles".  Then  the  mean  and  the  princi(cid:173) pal components of the cycles  are  computed using  a  new  algorithm  that  accounts  for  missing  information  and  enforces  smooth  tran(cid:173) sitions  between  cycles.  The  learned  temporal  model  provides  a  prior probability distribution over human motions that can be used  in  a  Bayesian  framework  for  tracking  human subjects  in  complex  monocular video sequences  and recovering  their  3D  motion.
Active Support Vector Machine Classification
Authors: Olvi L. Mangasarian, David R. Musicant
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: An active set strategy is applied to the dual of a simple  reformula(cid:173) tion of the standard quadratic program of a  linear support vector  machine.  This  application  generates  a  fast  new  dual  algorithm  that consists of solving a  finite  number of linear equations,  with a  typically large dimensionality equal to the number of points to  be  classified.  However, by making novel use of the Sherman-Morrison(cid:173) Woodbury formula, a  much smaller matrix of the order of the orig(cid:173) inal  input  space  is  inverted at each step.  Thus,  a  problem  with a  32-dimensional input space and 7 million points required inverting  positive definite symmetric matrices of size 33 x 33 with a total run(cid:173) ning time of 96  minutes  on a  400 MHz  Pentium II.  The algorithm  requires  no  specialized  quadratic or linear  programming code,  but  merely a  linear equation solver which is  publicly  available.
Generalizable Singular Value Decomposition for Ill-posed Datasets
Authors: Ulrik Kjems, Lars Kai Hansen, Stephen C. Strother
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We demonstrate that statistical analysis of ill-posed data sets is  subject to a bias, which can be observed when projecting indepen(cid:173) dent test set examples onto a basis defined by the training exam(cid:173) ples. Because the training examples in an ill-posed data set do not  fully span the signal space the observed training set variances in  each basis vector will be too high compared to the average vari(cid:173) ance of the test set projections onto the same basis vectors. On  basis of this understanding we introduce the Generalizable Singu(cid:173) lar Value Decomposition (GenSVD) as a means to reduce this bias  by re-estimation of the singular values obtained in a conventional  Singular Value Decomposition, allowing for a generalization perfor(cid:173) mance increase of a subsequent statistical model. We demonstrate  that the algorithm succesfully corrects bias in a data set from a  functional PET activation study of the human brain. 
1 
Ill-posed Data Sets 
An ill-posed data set has more dimensions in each example than there are examples.  Such data sets occur in many fields of research typically in connection with image  measurements. The associated statistical problem is that of extracting structure  from the observed high-dimensional vectors in the presence of noise. The statistical  analysis can be done either supervised (Le. modelling with target values: classifi(cid:173) cation, regresssion) or unsupervised (modelling with no target values: clustering,  PCA, ICA). In both types of analysis the ill-posedness may lead to immediate prob(cid:173) lems if one tries to apply conventional statistical methods of analysis, for example  the empirical covariance matrix is prohibitively large and will be rank-deficient. 
A common approach is to use Singular Value Decomposition (SVD) or the analogue  Principal Component Analysis (PCA) to reduce the dimensionality of the data. Let  the N observed i-dimensional samples Xj, j = L .N, collected in the data matrix  X = [Xl ... XN] of size I x N, I> N . The SVD-theorem states that such a matrix  can be decomposed as
Vicinal Risk Minimization
Authors: Olivier Chapelle, Jason Weston, Léon Bottou, Vladimir Vapnik
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: The  Vicinal  Risk  Minimization  principle establishes  a  bridge  between  generative models  and  methods derived from  the  Structural Risk Mini(cid:173) mization Principle such  as  Support Vector Machines  or Statistical  Reg(cid:173) ularization.  We  explain how  VRM  provides  a  framework  which  inte(cid:173) grates a number of existing algorithms, such as Parzen windows, Support  Vector Machines, Ridge Regression, Constrained Logistic Classifiers and  Tangent-Prop.  We  then  show  how  the approach implies new  algorithm(cid:173) s for solving problems usually associated with generative models.  New  algorithms  are  described for  dealing with pattern recognition problems  with very different pattern distributions and dealing with unlabeled data.  Preliminary empirical results are presented.
Rate-coded Restricted Boltzmann Machines for Face Recognition
Authors: Yee Whye Teh, Geoffrey E. Hinton
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  describe  a  neurally-inspired,  unsupervised  learning  algorithm  that  builds  a non-linear generative model for pairs  of face  images from  the  same individual.  Individuals are then recognized by  finding  the highest  relative probability pair among all pairs that consist of a test image and  an image whose identity is known.  Our method compares favorably with  other methods in the literature. The generative model consists of a single  layer of rate-coded, non-linear feature detectors  and  it has  the property  that,  given a data vector,  the  true posterior probability distribution  over  the feature detector activities can be inferred rapidly without iteration or  approximation. The weights of the feature detectors are learned by com(cid:173) paring the correlations of pixel intensities and feature activations in two  phases: When the network is observing real data and when it is observing  reconstructions of real data generated from the feature activations.
Shape Context: A New Descriptor for Shape Matching and Object Recognition
Authors: Serge Belongie, Jitendra Malik, Jan Puzicha
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  develop  an  approach  to  object  recognition  based  on  match(cid:173) ing shapes and using a resulting measure of similarity in a  nearest  neighbor  classifier.  The  key  algorithmic  problem  here  is  that  of  finding  pointwise  correspondences  between  an  image shape  and  a  stored  prototype  shape.  We  introduce  a  new  shape  descriptor,  the  shape  context,  which  makes  this  possible,  using  a  simple  and  robust algorithm.  The shape context at a point captures the distri(cid:173) bution over relative positions of other shape points and thus sum(cid:173) marizes  global  shape in  a  rich,  local  descriptor.  We  demonstrate  that  shape  contexts  greatly  simplify  recovery  of correspondences  between points of two given shapes.  Once shapes are aligned, shape  contexts are used to define a robust score for measuring shape sim(cid:173) ilarity.  We  have  used  this  score  in  a  nearest-neighbor  classifier  for  recognition of hand written  digits  as  well  as  3D  objects,  using  exactly  the  same  distance  function.  On  the  benchmark  MNIST  dataset  of handwritten  digits,  this  yields  an  error  rate  of 0.63%,  outperforming other published techniques.
Position Variance, Recurrence and Perceptual Learning
Authors: Zhaoping Li, Peter Dayan
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Stimulus  arrays  are  inevitably  presented  at  different  positions  on  the  retina in  visual  tasks,  even those that nominally require fixation.  In par(cid:173) ticular, this applies to many perceptual learning tasks.  We show that per(cid:173) ceptual inference or discrimination in the face of positional variance has a  structurally different quality from inference about fixed position stimuli,  involving  a particular,  quadratic,  non-linearity rather than  a purely  lin(cid:173) ear discrimination.  We show the advantage taking this non-linearity into  account has for discrimination, and suggest it as a role for recurrent con(cid:173) nections in area VI, by demonstrating the superior discrimination perfor(cid:173) mance of a recurrent network.  We propose that learning the feedforward  and recurrent neural connections for  these tasks corresponds to  the fast  and slow components of learning observed in perceptual learning tasks.
Learning Switching Linear Models of Human Motion
Authors: Vladimir Pavlovic, James M. Rehg, John MacCormick
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: The human  figure  exhibits  complex and  rich  dynamic  behavior that is  both nonlinear and  time-varying.  Effective models  of human dynamics  can be learned from motion capture data using switching linear dynamic  system  (SLDS)  models.  We  present results  for human  motion  synthe(cid:173) sis, classification, and visual tracking using learned SLDS models.  Since  exact inference in SLDS is intractable, we present three approximate in(cid:173) ference algorithms and compare their performance.  In particular, a new  variational  inference algorithm  is  obtained by  casting the  SLDS  model  as  a Dynamic  Bayesian  Network.  Classification experiments  show  the  superiority of SLDS over conventional HMM's for our problem domain.
Place Cells and Spatial Navigation Based on 2D Visual Feature Extraction, Path Integration, and Reinforcement Learning
Authors: Angelo Arleo, Fabrizio Smeraldi, Stéphane Hug, Wulfram Gerstner
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  model  hippocampal place cells  and head-direction cells by combin(cid:173) ing allothetic  (visual) and idiothetic (proprioceptive) stimuli.  Visual in(cid:173) put, provided by a video camera on a miniature robot, is preprocessed by  a set of Gabor filters on 31 nodes of a log-polar retinotopic graph. Unsu(cid:173) pervised Hebbian learning is employed to  incrementally build a popula(cid:173) tion of localized overlapping place fields.  Place cells serve as basis func(cid:173) tions for reinforcement learning.  Experimental results for goal-oriented  navigation of a mobile robot are presented.
Kernel-Based Reinforcement Learning in Average-Cost Problems: An Application to Optimal Portfolio Choice
Authors: Dirk Ormoneit, Peter W. Glynn
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Many  approaches  to  reinforcement  learning  combine  neural  net(cid:173) works  or other  parametric function  approximators with  a  form  of  temporal-difference  learning  to  estimate  the  value  function  of  a  Markov  Decision  Process.  A  significant disadvantage of those  pro(cid:173) cedures  is that the resulting learning algorithms are frequently un(cid:173) stable.  In  this  work,  we  present  a  new,  kernel-based  approach  to  reinforcement learning which overcomes this difficulty and provably  converges  to a  unique solution.  By contrast to existing algorithms,  our  method  can  also  be  shown  to  be  consistent  in  the  sense  that  its  costs  converge  to  the  optimal costs  asymptotically.  Our  focus  is  on learning in  an average-cost  framework  and on a  practical  ap(cid:173) plication to  the optimal portfolio choice problem.
Ensemble Learning and Linear Response Theory for ICA
Authors: Pedro A. d. F. R. Højen-Sørensen, Ole Winther, Lars Kai Hansen
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  propose a general Bayesian framework for performing independent  component analysis  (leA) which  relies  on  ensemble  learning  and  lin(cid:173) ear response theory  known from  statistical physics.  We  apply it to both  discrete and continuous sources. For the continuous source the underde(cid:173) termined (overcomplete) case is  studied.  The naive mean-field approach  fails in this case whereas linear response theory-which gives an improved  estimate  of covariances-is  very  efficient.  The  examples  given  are  for  sources without temporal correlations. However, this derivation can eas(cid:173) ily  be  extended  to  treat  temporal  correlations.  Finally,  the  framework  offers a simple way  of generating new  leA algorithms without needing  to define the prior distribution of the sources explicitly.
Regularization with Dot-Product Kernels
Authors: Alex J. Smola, Zoltán L. Óvári, Robert C. Williamson
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: In  this  paper  we  give  necessary  and  sufficient  conditions  under  which  kernels  of dot  product  type  k(x, y)  =  k(x . y)  satisfy Mer(cid:173) cer's  condition  and  thus  may  be  used  in  Support  Vector  Ma(cid:173) chines  (SVM),  Regularization  Networks  (RN)  or  Gaussian  Pro(cid:173) cesses  (GP).  In  particular,  we  show  that  if the  kernel  is  analytic  (i.e.  can be expanded in a  Taylor series),  all expansion coefficients  have to be nonnegative.  We  give an explicit functional form for  the  feature map by calculating its eigenfunctions and eigenvalues.
From Margin to Sparsity
Authors: Thore Graepel, Ralf Herbrich, Robert C. Williamson
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  present  an  improvement  of Novikoff's  perceptron convergence  theorem.  Reinterpreting this mistake bound as a margin dependent  sparsity guarantee allows us to give a PAC-style generalisation er(cid:173) ror bound for the classifier learned by the perceptron learning algo(cid:173) rithm.  The bound value crucially depends on the margin a support  vector machine would achieve on the same data set using the same  kernel.  Ironically, the bound yields better guarantees than are cur(cid:173) rently available for  the support vector solution itself.
Interactive Parts Model: An Application to Recognition of On-line Cursive Script
Authors: Predrag Neskovic, Philip C. Davis, Leon N. Cooper
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: In  this  work,  we  introduce  an  Interactive  Parts  (IP)  model as  an  alternative  to  Hidden  Markov  Models  (HMMs).  We  tested  both  models  on  a  database of on-line  cursive  script.  We  show  that  im(cid:173) plementations of HMMs  and the IP model, in which  all letters  are  assumed  to have  the same average width, give  comparable results.  However , in contrast to  HMMs,  the  IP model can handle duration  modeling without  an increase  in  computational complexity.
A New Model of Spatial Representation in Multimodal Brain Areas
Authors: Sophie Denève, Jean-René Duhamel, Alexandre Pouget
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Most  models  of spatial representations in  the cortex  assume  cells  with limited receptive fields that are defined in a particular egocen(cid:173) tric frame  of reference.  However,  cells  outside  of primary sensory  cortex  are  either  gain  modulated  by  postural  input  or  partially  shifting.  We  show  that  solving  classical  spatial  tasks,  like  sen(cid:173) sory prediction, multi-sensory integration, sensory-motor transfor(cid:173) mation and motor control requires more complicated intermediate  representations  that  are  not  invariant  in  one  frame  of  reference.  We  present  an  iterative  basis  function  map  that  performs  these  spatial tasks optimally with gain modulated and partially shifting  units,  and tests it against  neurophysiological and neuropsycholog(cid:173) ical data. 
In  order  to  perform  an  action  directed  toward  an  object,  it  is  necessary  to  have  a  representation  of  its  spatial  location.  The  brain  must  be  able  to  use  spatial  cues coming from  different modalities (e.g.  vision, audition, touch, proprioception),  combine  them  to  infer  the  position  of the  object,  and  compute  the  appropriate  movement. 
These  cues  are  in  different  frames  of reference  corresponding  to  different  sensory  or  motor  modalities.  Visual  inputs  are  primarily  encoded  in  retinotopic  maps,  auditory  inputs  are  encoded  in  head  centered  maps  and  tactile  cues  are  encoded  in  skin-centered maps.  Going from  one frame  of reference to the other might  seem  easy.  For  example,  the  head-centered  position  of an  object  can  be  approximated  by the sum of its retinotopic position and the eye position.  However,  positions are  represented by population codes in the brain, and computing a  head-centered map  from  a  retinotopic map  is  a  more  complex computation than the underlying sum.  Moreover,  as  we  get  closer  to  sensory-motor  areas  it  seems  reasonable  to  assume
Feature Correspondence: A Markov Chain Monte Carlo Approach
Authors: Frank Dellaert, Steven M. Seitz, Sebastian Thrun, Charles E. Thorpe
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: When  trying  to  recover  3D  structure  from  a  set  of  images,  the  most difficult  problem is  establishing  the correspondence  between  the measurements.  Most existing  approaches  assume that features  can be tracked across frames,  whereas methods that exploit rigidity  constraints to facilitate matching do so only under restricted  cam(cid:173) era  motion.  In  this  paper  we  propose  a  Bayesian  approach  that  avoids  the  brittleness  associated  with  singling out  one  "best"  cor(cid:173) respondence,  and instead consider the distribution over all possible  correspondences.  We  treat  both  a  fully  Bayesian  approach  that  yields  a  posterior  distribution,  and  a  MAP  approach  that  makes  use of EM  to maximize this posterior.  We show how  Markov chain  Monte  Carlo methods can  be  used  to implement these  techniques  in practice,  and present  experimental results on real  data.
Stagewise Processing in Error-correcting Codes and Image Restoration
Authors: K. Y. Michael Wong, Hidetoshi Nishimori
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  introduce  stagewise  processing  in  error-correcting  codes  and  image restoration, by extracting information from the former stage  and  using  it  selectively  to  improve  the  performance  of the  latter  one.  Both  mean-field  analysis  using  the  cavity  method  and  sim(cid:173) ulations  show  that  it  has  the  advantage  of  being  robust  against  uncertainties in hyperparameter estimation.
The Kernel Gibbs Sampler
Authors: Thore Graepel, Ralf Herbrich
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  present an algorithm that samples the hypothesis space of ker(cid:173) nel classifiers.  Given a uniform prior over normalised weight vectors  and  a  likelihood  based on  a  model  of label  noise leads to a  piece(cid:173) wise  constant  posterior that  can  be  sampled  by  the  kernel  Gibbs  sampler (KGS).  The KGS is a Markov Chain Monte Carlo method  that  chooses  a  random  direction  in  parameter space  and  samples  from the resulting piecewise constant density along the line chosen.  The KGS  can be used  as  an analytical tool for  the exploration of  Bayesian transduction, Bayes point machines,  active learning, and  evidence-based model selection on small data sets that are contam(cid:173) inated with  label noise.  For a  simple toy example  we  demonstrate  experimentally how  a Bayes point machine based on the KGS  out(cid:173) performs  an  SVM  that  is  incapable  of  taking  into  account  label  noise.
Learning Sparse Image Codes using a Wavelet Pyramid Architecture
Authors: Bruno A. Olshausen, Phil Sallee, Michael S. Lewicki
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  show  how  a  wavelet  basis  may  be  adapted  to  best  represent  natural images  in  terms  of sparse coefficients.  The  wavelet  basis,  which  may  be  either  complete  or  overcomplete,  is  specified  by  a  small number of spatial functions  which  are  repeated across space  and combined in a  recursive fashion  so  as  to be self-similar across  scale.  These functions are adapted to minimize the estimated code  length under a model that assumes images are composed of a linear  superposition of sparse,  independent  components.  When  adapted  to natural images, the wavelet  bases take on  different  orientations  and they evenly tile the orientation domain, in stark contrast to the  standard,  non-oriented  wavelet  bases  used  in  image  compression.  When  the  basis  set  is  allowed  to  be  overcomplete,  it  also  yields  higher coding efficiency than standard wavelet  bases.
Weak Learners and Improved Rates of Convergence in Boosting
Authors: Shie Mannor, Ron Meir
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: The  problem  of  constructing  weak  classifiers  for  boosting  algo(cid:173) rithms is  studied.  We  present an algorithm that produces a  linear  classifier that is guaranteed to achieve an error better than random  guessing for  any distribution on the data.  While this weak  learner  is not useful for  learning in general, we show that under reasonable  conditions on the distribution it yields an effective weak learner for  one-dimensional  problems.  Preliminary  simulations  suggest  that  similar  behavior  can  be  expected  in  higher  dimensions,  a  result  which  is  corroborated by  some  recent  theoretical  bounds.  Addi(cid:173) tionally, we  provide improved convergence rate bounds for the gen(cid:173) eralization error in situations where the empirical error can be made  small,  which  is  exactly the  situation  that  occurs  if weak  learners  with guaranteed performance that is better than random guessing  can be established.
Keeping Flexible Active Contours on Track using Metropolis Updates
Authors: Trausti T. Kristjansson, Brendan J. Frey
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Condensation, a form of likelihood-weighted particle filtering,  has been  successfully used to infer the shapes of highly constrained "active" con(cid:173) tours in video sequences.  However, when the contours are highly flexible  (e.g.  for tracking fingers of a hand), a computationally burdensome num(cid:173) ber of particles is needed to successfully approximate the contour distri(cid:173) bution.  We  show how  the Metropolis algorithm can be used to update a  particle set representing a distribution  over contours  at each  frame in a  video sequence.  We compare this method to condensation using a video  sequence that requires highly  flexible  contours,  and  show  that the  new  algorithm performs dramatically better that the condensation algorithm.  We  discuss  the  incorporation of this  method  into  the  "active  contour"  framework where a shape-subspace is  used constrain shape variation.
Data Clustering by Markovian Relaxation and the Information Bottleneck Method
Authors: Naftali Tishby, Noam Slonim
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We introduce a new,  non-parametric and principled, distance based  clustering  method.  This  method  combines  a  pairwise  based  ap(cid:173) proach  with  a  vector-quantization  method which  provide  a  mean(cid:173) ingful  interpretation  to  the  resulting  clusters.  The  idea  is  based  on  turning  the  distance  matrix  into  a  Markov  process  and  then  examine the decay  of mutual-information during  the relaxation of  this  process.  The  clusters  emerge  as  quasi-stable  structures  dur(cid:173) ing  this  relaxation,  and  then  are  extracted  using  the  information  bottleneck method.  These  clusters  capture  the  information about  the  initial point  of the  relaxation  in  the  most  effective  way.  The  method can cluster data with no geometric or other bias and makes  no  assumption about the underlying distribution.