mtybilly/Instruct2DS huggingface dataset:
Passport-aware Normalization for Deep Model Protection
Authors: Dongdong Chen, Jing Liao, Weiming Zhang, Gang Hua, Nenghai Yu Jie Zhang
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: Despite tremendous success in many application scenarios, deep learning faces serious intellectual property (IP) infringement threats. Considering the cost of designing and training a good model, infringements will significantly infringe the interests of the original model owner. Recently, many impressive works have emerged for deep model IP protection. However, they either are vulnerable to ambiguity attacks, or require changes in the target network structure by replacing its original normalization layers and hence cause significant performance drops. To this end, we propose a new passport-aware normalization formulation, which is generally applicable to most existing normalization layers and only needs to add another passport-aware branch for IP protection. This new branch is jointly trained with the target model but discarded in the inference stage. Therefore it causes no structure change in the target model. Only when the model IP is suspected to be stolen by someone, the private passport-aware branch is added back for ownership verification. Through extensive experiments, we verify its effectiveness in both image and 3D point recognition models. It is demonstrated to be robust not only to common attack techniques like fine-tuning and model compression, but also to ambiguity attacks. By further combining it with trigger-set based methods, both black-box and white-box verification can be achieved for enhanced security of deep learning models deployed in real systems.
Sampling-Decomposable Generative Adversarial Recommender
Authors: Defu Lian, Zheng Liu, Qi Liu, Jianhui Ma, Xing Xie, Enhong Chen Binbin Jin
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: Recommendation techniques are important approaches for alleviating information overload. Being often trained on implicit user feedback, many recommenders suffer from the sparsity challenge due to the lack of explicitly negative samples. The GAN-style recommenders (i.e., IRGAN) addresses the challenge by learning a generator and a discriminator adversarially, such that the generator produces increasingly difficult samples for the discriminator to accelerate optimizing the discrimination objective. However, producing samples from the generator is very time-consuming, and our empirical study shows that the discriminator performs poor in top-k item recommendation. To this end, a theoretical analysis is made for the GAN-style algorithms, showing that the generator of limit capacity is diverged from the optimal generator. This may interpret the limitation of discriminator's performance. Based on these findings, we propose a Sampling-Decomposable Generative Adversarial Recommender (SD-GAR). In the framework, the divergence between some generator and the optimum is compensated by self-normalized importance sampling; the efficiency of sample generation is improved with a sampling-decomposable generator, such that each sample can be generated in O(1) with the Vose-Alias method. Interestingly, due to decomposability of sampling, the generator can be optimized with the closed-form solutions in an alternating manner, being different from policy gradient in the GAN-style algorithms. We extensively evaluate the proposed algorithm with five real-world recommendation datasets. The results show that SD-GAR outperforms IRGAN by 12.4% and the SOTA recommender by 10% on average. Moreover, discriminator training can be 20x faster on the dataset with more than 120K items.
Limits to Depth Efficiencies of Self-Attention
Authors: Noam Wies, Or Sharir, Hofit Bata, Amnon Shashua Yoav Levine
Published in: Advances in Neural Information Processing Systems 33  (NeurIPS 2020) (Main Conference Track), 2020

Abstract: Self-attention architectures, which are rapidly pushing the frontier in natural language processing, demonstrate a surprising depth-inefficient behavior: Empirical signals indicate that increasing the internal representation (network width) is just as useful as increasing the number of self-attention layers (network depth). In this paper, we theoretically study the interplay between depth and width in self-attention. We shed light on the root of the above phenomenon, and establish two distinct parameter regimes of depth efficiency and inefficiency in self-attention. We invalidate the seemingly plausible hypothesis by which widening is as effective as deepening for self-attention, and show that in fact stacking self-attention layers is so effective that it quickly saturates a capacity of the network width. Specifically, we pinpoint a ``depth threshold" that is logarithmic in the network width: for networks of depth that is below the threshold, we establish a double-exponential depth-efficiency of the self-attention operation, while for depths over the threshold we show that depth-inefficiency kicks in. Our predictions accord with existing empirical ablations, and we further demonstrate the two depth-(in)efficiency regimes experimentally for common network depths of 6, 12, and 24. By identifying network width as a limiting factor, our analysis indicates that solutions for dramatically increasing the width can facilitate the next leap in self-attention expressivity.
Reinforcement Learning with Function Approximation Converges to a Region
Authors: Geoffrey J. Gordon
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Many  algorithms  for  approximate reinforcement  learning  are  not  known  to  converge.  In  fact,  there  are  counterexamples  showing  that the adjustable weights in some algorithms may oscillate within  a region rather than converging to a point.  This paper shows that,  for  two  popular algorithms,  such  oscillation  is  the  worst  that  can  happen:  the  weights  cannot  diverge,  but  instead  must  converge  to a  bounded region.  The algorithms are SARSA(O)  and V(O);  the  latter algorithm was used in the well-known TD-Gammon program.
Redundancy and Dimensionality Reduction in Sparse-Distributed Representations of Natural Objects in Terms of Their Local Features
Authors: Penio S. Penev
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Low-dimensional representations are key to solving problems in high(cid:173) level vision, such as face compression and recognition. Factorial coding  strategies for reducing the redundancy present in natural images on the  basis of their second-order statistics have been successful in account(cid:173) ing for both psychophysical and neurophysiological properties of early  vision. Class-specific representations are presumably formed later, at  the higher-level stages of cortical processing. Here we show that when  retinotopic factorial codes are derived for ensembles of natural objects,  such as human faces, not only redundancy, but also dimensionality is re(cid:173) duced. We also show that objects are built from parts in a non-Gaussian  fashion which allows these local-feature codes to have dimensionalities  that are substantially lower than the respective Nyquist sampling rates.
Who Does What? A Novel Algorithm to Determine Function Localization
Authors: Isaac Meilijson, Eytan Ruppin Ranit Aharonov-Barki
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  introduce  a  novel  algorithm,  termed  PPA  (Performance  Prediction  Algorithm),  that  quantitatively  measures  the  contributions  of elements  of a neural system to  the tasks it performs.  The algorithm identifies the  neurons or areas which participate in a cognitive or behavioral task, given  data about performance decrease in a small set of lesions.  It also allows  the  accurate  prediction  of performances  due  to  multi-element  lesions.  The effectiveness  of the  new  algorithm is  demonstrated  in  two  models  of recurrent neural  networks with  complex interactions among  the ele(cid:173) ments.  The algorithm is  scalable and applicable to  the  analysis of large  neural  networks.  Given  the  recent advances  in  reversible  inactivation  techniques,  it has  the  potential  to  significantly  contribute  to  the  under(cid:173) standing of the  organization of biological nervous systems, and to  shed  light on  the  long-lasting debate about local  versus distributed computa(cid:173) tion in the brain.
Overfitting in Neural Nets: Backpropagation, Conjugate Gradient, and Early Stopping
Authors: Steve Lawrence, C. Lee Giles Rich Caruana
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: The conventional wisdom is that backprop nets with excess hidden units  generalize  poorly.  We  show  that  nets  with  excess  capacity  generalize  well when  trained with backprop and early  stopping.  Experiments  sug(cid:173) gest two reasons for this:  1) Overfitting can vary significantly in different  regions of the model.  Excess capacity allows better fit to regions of high  non-linearity,  and  backprop often  avoids  overfitting  the  regions  of low  non-linearity.  2)  Regardless  of size,  nets  learn  task  subcomponents  in  similar sequence.  Big nets pass  through stages  similar to those learned  by  smaller nets.  Early  stopping can  stop training the large net  when  it  generalizes  comparably  to  a  smaller net.  We  also  show  that conjugate  gradient can yield worse generalization because it overfits regions of low  non-linearity when learning to fit regions of high non-linearity.
Learning Segmentation by Random Walks
Authors: Jianbo Shi Marina Meila
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We present a new view of image segmentation by pairwise simi(cid:173) larities. We interpret the similarities as edge flows in a Markov  random walk and study the eigenvalues and eigenvectors of the  walk's transition matrix. This interpretation shows that spectral  methods for clustering and segmentation have a probabilistic foun(cid:173) dation. In particular, we prove that the Normalized Cut method  arises naturally from our framework. Finally, the framework pro(cid:173) vides a principled method for learning the similarity function as a  combination of features.
A PAC-Bayesian Margin Bound for Linear Classifiers: Why SVMs work
Authors: Thore Graepel Ralf Herbrich
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  present a  bound on the generalisation error of linear classifiers  in  terms  of  a  refined  margin  quantity  on  the  training  set.  The  result  is  obtained  in  a  PAC- Bayesian framework  and  is  based  on  geometrical  arguments  in  the space of linear  classifiers.  The  new  bound constitutes an exponential improvement of the so far tightest  margin bound by Shawe-Taylor et al.  [8]  and scales logarithmically  in  the inverse margin.  Even  in  the case  of less  training  examples  than input dimensions sufficiently large margins lead to non-trivial  bound values and - plexity  term.  Furthermore,  the  classical  margin  is  too  coarse  a  measure for  the  essential  quantity  that controls the generalisation  error:  the  volume  ratio  between  the  whole  hypothesis  space  and  the subset of consistent hypotheses.  The practical relevance of the  result  lies  in the fact  that the well-known support vector machine  is optimal w.r.t. the new bound only if the feature vectors are all of  the same length.  As a consequence we recommend to use SVMs on  normalised feature  vectors only - a  recommendation that is  well  supported  by our  numerical experiments on two  benchmark  data  sets. 
for maximum margins -
to a  vanishing com(cid:173)
Active Learning for Parameter Estimation in Bayesian Networks
Authors: Daphne Koller Simon Tong
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Bayesian  networks  are  graphical  representations  of probability  distributions.  In  virtually  all  of the  work  on  learning  these  networks,  the  assumption  is  that  we  are  presented  with  a data  set consisting  of randomly  generated instances  from  the  underlying  distribution.  In  many  situations, however, we  also  have  the  option  of active  learning, where  we  have  the  possibility of guiding the  sampling process by  querying  for certain types  of samples.  This  paper addresses the problem of estimating the parameters of Bayesian networks in  an  active  learning  setting.  We  provide  a  theoretical  framework  for  this  problem,  and  an  algorithm  that chooses  which  active  learning  queries  to  generate  based  on  the  model  learned  so  far.  We present experimental results showing that our active learning algorithm can significantly  reduce the need for training data in  many situations.
A Tighter Bound for Graphical Models
Authors: Hilbert J. Kappen Martijn A. R. Leisink
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  present  a  method to bound  the  partition function  of a  Boltz(cid:173) mann machine neural network with any odd order polynomial. This  is  a  direct  extension  of the mean field  bound,  which  is  first  order.  We  show  that  the  third  order  bound  is  strictly  better  than  mean  field.  Additionally  we  show  the  rough  outline  how  this  bound  is  applicable  to  sigmoid belief networks.  Numerical  experiments  in(cid:173) dicate  that  an error  reduction  of a  factor  two  is  easily  reached  in  the region  where  expansion based  approximations are  useful.
Occam's Razor
Authors: Zoubin Ghahramani Carl Edward Rasmussen
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: The Bayesian paradigm apparently only sometimes gives rise to Occam's  Razor;  at  other times  very  large models perform well.  We  give  simple  examples of both kinds of behaviour. The two views are reconciled when  measuring complexity of functions, rather than of the machinery used to  implement them.  We analyze the complexity of functions for some linear  in the parameter models that are  equivalent to  Gaussian Processes, and  always find Occam's Razor at work.
Exact Solutions to Time-Dependent MDPs
Authors: Michael L. Littman Justin A. Boyan
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  describe an extension of the Markov decision process model in  which  a  continuous time  dimension  is  included in  the state space.  This  allows  for  the  representation  and  exact  solution  of  a  wide  range of problems in  which  transitions or rewards  vary over time.  We  examine  problems based on  route planning with  public trans(cid:173) portation and telescope observation scheduling.
An Information Maximization Approach to Overcomplete and Recurrent Representations
Authors: Haim Sompolinsky, Daniel D. Lee Oren Shriki
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: The principle of maximizing mutual  information is  applied to  learning  overcomplete and recurrent representations.  The underlying model con(cid:173) sists  of a network of input units driving a larger number of output units  with recurrent interactions.  In the limit of zero noise, the network is de(cid:173) terministic  and  the mutual information can be related  to  the  entropy  of  the output units.  Maximizing this entropy with respect to  both the feed(cid:173) forward connections as well as the recurrent interactions results in simple  learning rules for both sets of parameters.  The conventional independent  components (ICA) learning algorithm can be recovered as a special case  where  there  is  an  equal  number of output  units  and  no  recurrent  con(cid:173) nections.  The application of these new  learning rules is  illustrated on a  simple two-dimensional input example.
A Linear Programming Approach to Novelty Detection
Authors: Kristin P. Bennett Colin Campbell
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Novelty detection involves modeling the normal behaviour of a sys(cid:173) tem hence  enabling detection of any divergence from normality.  It  has  potential applications in  many areas  such  as  detection  of ma(cid:173) chine  damage  or  highlighting  abnormal features  in  medical data.  One  approach  is  to  build  a  hypothesis  estimating  the  support  of  the normal data i.e. constructing a function which is positive in the  region  where  the  data is  located  and  negative elsewhere.  Recently  kernel  methods  have  been  proposed  for  estimating the  support  of  a  distribution  and  they  have  performed well  in  practice - training  involves solution of a  quadratic programming problem.  In this pa(cid:173) per we propose a simpler kernel method for  estimating the support  based  on  linear  programming.  The  method  is  easy  to  implement  and  can learn large  datasets rapidly.  We  demonstrate the method  on medical and fault detection datasets. 
1
Programmable Reinforcement Learning Agents
Authors: Stuart J. Russell David Andre
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We present an expressive agent design language for reinforcement learn(cid:173) ing that allows the user to constrain the policies considered by the learn(cid:173) ing process.The language includes standard features  such as  parameter(cid:173) ized subroutines, temporary interrupts, aborts, and memory variables, but  also  allows  for  unspecified choices  in  the  agent program.  For learning  that which isn't specified, we present provably convergent learning algo(cid:173) rithms.  We  demonstrate by  example that agent programs written in the  language are concise as well as modular.  This facilitates state abstraction  and the transferability of learned skills.
Learning Joint Statistical Models for Audio-Visual Fusion and Segregation
Authors: Trevor Darrell, William T. Freeman, Paul A. Viola John W. Fisher III
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: People can  understand complex auditory  and  visual  information,  often  using one to disambiguate the other.  Automated analysis, even at a low(cid:173) level,  faces  severe challenges, including  the  lack of accurate  statistical  models  for  the  signals,  and  their high-dimensionality  and  varied  sam(cid:173) pling rates.  Previous approaches  [6]  assumed simple parametric models  for the joint distribution which, while tractable, cannot capture the com(cid:173) plex signal relationships. We learn the joint distribution of the visual and  auditory  signals using a non-parametric approach.  First,  we project the  data into  a maximally  informative,  low-dimensional subspace,  suitable  for density estimation.  We  then  model the  complicated stochastic rela(cid:173) tionships between the  signals  using  a nonparametric density  estimator.  These  learned densities  allow  processing across  signal  modalities.  We  demonstrate,  on  synthetic and  real  signals,  localization  in  video  of the  face that is  speaking in  audio, and,  conversely, audio enhancement of a  particular speaker selected from the video.
Convergence of Large Margin Separable Linear Classification
Authors: Tong Zhang
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Large  margin  linear classification  methods  have  been  successfully  ap(cid:173) plied to many applications.  For a linearly separable problem, it is known  that under appropriate assumptions, the expected misclassification error  of the computed "optimal hyperplane" approaches zero at a rate propor(cid:173) tional  to  the  inverse  training  sample  size.  This  rate  is  usually charac(cid:173) terized  by the margin and the maximum norm of the input data.  In  this  paper,  we  argue  that another quantity,  namely  the robustness of the  in(cid:173) put data distribution,  also  plays  an  important role  in characterizing  the  convergence behavior of expected misclassification error.  Based on  this  concept of robustness,  we  show that for a large margin  separable linear  classification problem, the expected misclassification error may converge  exponentially in the number of training sample size.
Emergence of Movement Sensitive Neurons' Properties by Learning a Sparse Code for Natural Moving Images
Authors: Malcolm W. Brown, Christophe G. Giraud-Carrier Rafal Bogacz
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Olshausen  &  Field  demonstrated  that  a  learning  algorithm  that  attempts  to  generate  a  sparse  code  for  natural  scenes  develops  a  complete  family  of localised,  oriented,  bandpass  receptive  fields,  similar  to  those  of  'simple  cells'  in  VI.  This  paper  describes  an  algorithm  which  finds  a  sparse  code  for  sequences  of images  that  preserves information  about the  input.  This  algorithm when  trained  on  natural  video  sequences  develops  bases  representing  the  movement in particular directions  with  particular speeds,  similar to  the  receptive  fields  of  the  movement-sensitive  cells  observed  in  cortical  visual  areas.  Furthermore,  to  previous  approaches  to  learning direction  selectivity,  the  timing  of neuronal  activity  encodes  the  phase  of the  movement,  so  the  precise  timing  of spikes is crucially important to  the information encoding.
High-temperature Expansions for Learning Models of Nonnegative Data
Authors: Oliver B. Downs
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Recent  work  has  exploited  boundedness  of data  in  the  unsupervised  learning of new types of generative model.  For nonnegative data it was  recently  shown  that the  maximum-entropy generative  model  is  a  Non(cid:173) negative Boltzmann Distribution  not  a  Gaussian  distribution,  when  the  model is  constrained to match the  first and second order statistics of the  data.  Learning for practical sized problems is made difficult by the need  to  compute  expectations  under  the  model  distribution.  The  computa(cid:173) tional  cost of Markov  chain Monte  Carlo  methods  and  low  fidelity  of  naive  mean  field  techniques has  led  to  increasing interest in  advanced  mean  field  theories  and  variational  methods.  Here I  present a  second(cid:173) order mean-field approximation for the Nonnegative Boltzmann Machine  model,  obtained  using  a  "high-temperature" expansion.  The  theory  is  tested  on  learning  a bimodal 2-dimensional model,  a high-dimensional  translationally  invariant distribution,  and  a generative  model for hand(cid:173) written digits.
A Support Vector Method for Clustering
Authors: David Horn, Hava T. Siegelmann, Vladimir Vapnik Asa Ben-Hur
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  present a novel  method for clustering using the support vector ma(cid:173) chine approach.  Data points are  mapped to  a high  dimensional  feature  space, where support vectors are used to define a sphere enclosing them.  The boundary of the sphere forms in data space a set of closed contours  containing the data.  Data points enclosed by each contour are defined as a  cluster. As the width parameter of the Gaussian kernel is decreased, these  contours fit  the data more tightly and  splitting of contours occurs.  The  algorithm  works  by  separating clusters  according  to  valleys  in  the un(cid:173) derlying probability distribution,  and  thus clusters can take on  arbitrary  geometrical shapes.  As in other SV algorithms, outliers can be dealt with  by introducing a soft margin constant leading to smoother cluster bound(cid:173) aries.  The  structure of the data is  explored by  varying the two parame(cid:173) ters.  We  investigate the dependence of our method on  these parameters  and apply it to several data sets.
Incremental and Decremental Support Vector Machine Learning
Authors: Tomaso Poggio Gert Cauwenberghs
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: An on-line recursive algorithm for training support vector machines, one  vector  at  a  time,  is  presented.  Adiabatic  increments  retain  the  Kuhn(cid:173) Tucker  conditions  on  all  previously  seen  training  data,  in  a  number  of steps  each computed analytically.  The  incremental procedure is  re(cid:173) versible, and decremental "unlearning" offers an  efficient method to ex(cid:173) actly  evaluate  leave-one-out generalization performance.  Interpretation  of decremental unlearning in feature space sheds light on the relationship  between generalization and geometry of the data.
Active Inference in Concept Learning
Authors: Javier R. Movellan Jonathan D. Nelson
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: People  are  active  experimenters,  not  just  passive  observers,  constantly  seeking  new  information  relevant  to  their  goals.  A  reasonable  approach  to  active  information  gathering  is  to  ask  questions  and  conduct  experiments  that  maximize  the  expected  information  gain,  given  current  beliefs  (Fedorov  1972,  MacKay  1992,  Oaksford  &  Chater  1994).  In  this  paper  we  present  results  on  an  exploratory  experiment  designed  to  study  people's  active  information  gathering  behavior  on  a  concept  task  (Tenenbaum  2000).  The  results  of the  experiment are  analyzed  in  terms  of the  expected  information  gain  of the  questions  asked  by  subjects.
Sex with Support Vector Machines
Authors: Ming-Hsuan Yang Baback Moghaddam
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Nonlinear  Support  Vector  Machines  (SVMs)  are  investigated  for  visual sex classification with low resolution  "thumbnail"  faces  (21- by-12  pixels)  processed  from  1,755  images  from  the  FE RET face  database.  The  performance  of SVMs  is  shown  to  be  superior  to  traditional pattern classifiers (Linear, Quadratic, Fisher Linear Dis(cid:173) criminant,  Nearest-Neighbor)  as  well  as  more  modern  techniques  such as Radial Basis Function (RBF) classifiers and large ensemble(cid:173) RBF  networks.  Furthermore, the  SVM  performance  (3.4%  error)  is  currently the best result reported in the open literature.
Recognizing Hand-written Digits Using Hierarchical Products of Experts
Authors: Geoffrey E. Hinton Guy Mayraz
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: The  product  of  experts  learning  procedure  [1]  can  discover  a  set  of  stochastic binary features that constitute a non-linear generative model of  handwritten images of digits.  The quality of generative models learned  in this way can be assessed by learning a separate model for each class of  digit and  then comparing the unnormalized probabilities of test images  under the  10 different class-specific models.  To  improve discriminative  performance, it is helpful to learn a hierarchy of separate models for each  digit class.  Each model in the hierarchy has one layer of hidden units and  the nth level model is trained on data that consists of the activities of the  hidden  units  in  the  already  trained  (n  - l)th  level  model.  After train(cid:173) ing, each level produces a separate, unnormalized log probabilty score.  With a three-level hierarchy for each of the 10 digit classes, a test image  produces 30 scores  which  can  be used  as  inputs to  a supervised,  logis(cid:173) tic classification network that is trained on separate data.  On the MNIST  database, our system is comparable with current state-of-the-art discrimi(cid:173) native methods, demonstrating that the product of experts learning proce(cid:173) dure can produce effective generative models of high-dimensional data. 
1  Learning products of stochastic binary experts 
Hinton [1] describes a learning algorithm for probabilistic generative models that are com(cid:173) posed  of a  number of experts.  Each  expert specifies  a probability  distribution  over  the  visible variables and the experts are combined by  multiplying these distributions together  and renormalizing. 
(1) 
where d  is  a data vector in a discrete space, Om  is  all  the parameters of individual model  m, Pm(dIOm) is  the probability of d under model m, and  c  is  an  index over all  possible  vectors in  the data space. 
A Restricted Boltzmann machine [2,  3]  is  a special case of a product of experts in  which  each expert is  a single,  binary  stochastic  hidden unit that has  symmetrical connections to  a  set of visible units,  and connections between the hidden units are  forbidden.  Inference  in an RBM is  much easier than in a general Boltzmann machine and it is also much easier 
than in a causal belief net because there is  no explaining away.  There is  therefore no need  to  perform any iteration to determine the activities of the hidden units.  The hidden states,  Sj ,  are conditionally independent given the visible states,  Si,  and the distribution of Sj  is  given by the standard logistic function :
APRICODD: Approximate Policy Construction Using Decision Diagrams
Authors: Jesse Hoey, Craig Boutilier Robert St-Aubin
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We propose a method of approximate dynamic programming for Markov  decision processes (MDPs) using algebraic decision diagrams  (ADDs).  We produce near-optimal value functions and policies with much lower  time  and  space  requirements  than  exact  dynamic  programming.  Our  method reduces  the  sizes  of the  intermediate value functions  generated  during value iteration by replacing the values at the terminals of the ADD  with  ranges  of values.  Our method is  demonstrated on  a class  of large  MDPs (with up to 34 billion states), and we compare the results with the  optimal value functions.
Four-legged Walking Gait Control Using a Neuromorphic Chip Interfaced to a Support Vector Learning Algorithm
Authors: Bernhard Schölkopf, Klaus Hepp, Rodney J. Douglas Susanne Still
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: To  control  the  walking gaits  of a four-legged robot we  present a novel  neuromorphic  VLSI  chip  that  coordinates  the  relative  phasing  of the  robot's legs similar to how spinal Central Pattern Generators are believed  to  control  vertebrate  locomotion  [3].  The  chip  controls  the  leg  move(cid:173) ments by  driving motors  with time varying voltages which are  the  out(cid:173) puts of a small network of coupled oscillators.  The characteristics of the  chip's  output voltages  depend  on  a  set  of input parameters.  The rela(cid:173) tionship between input parameters and output voltages can be computed  analytically for an idealized system.  In  practice, however,  this  ideal  re(cid:173) lationship is only approximately true due to transistor mismatch and off(cid:173) sets.  Fine tuning of the chip's input parameters is done automatically by  the robotic system, using an unsupervised Support Vector (SV) learning  algorithm introduced  recently  [7].  The learning  requires  only  that  the  description of the desired output is  given.  The machine learns from (un(cid:173) labeled) examples how to set the parameters to the chip in order to obtain  a desired motor behavior.
A Mathematical Programming Approach to the Kernel Fisher Algorithm
Authors: Gunnar Rätsch, Klaus-Robert Müller Sebastian Mika
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We investigate a new kernel-based classifier:  the Kernel Fisher Discrim(cid:173) inant (KFD). A mathematical programming formulation based on the ob(cid:173) servation that KFD maximizes the average margin permits an interesting  modification of the original KFD algorithm yielding the sparse KFD. We  find  that  both,  KFD  and  the  proposed sparse  KFD,  can  be  understood  in an unifying probabilistic context.  Furthermore, we  show connections  to Support Vector Machines and Relevance Vector Machines.  From this  understanding,  we  are  able  to  outline  an  interesting  kernel-regression  technique based upon the KFD  algorithm.  Simulations support the  use(cid:173) fulness  of our approach.
Using Free Energies to Represent Q-values in a Multiagent Reinforcement Learning Task
Authors: Geoffrey E. Hinton Brian Sallans
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: The problem of reinforcement learning in large factored Markov decision  processes is explored. The Q-value of a state-action pair is approximated  by the free energy of a product of experts network.  Network parameters  are learned on-line using a modified SARSA algorithm which minimizes  the inconsistency of the Q-values of consecutive state-action pairs.  Ac(cid:173) tions are chosen based on the current value estimates by fixing the current  state and sampling actions from the network using Gibbs sampling. The  algorithm is  tested  on  a co-operative multi-agent task.  The product of  experts model is found to perform comparably to table-based Q-Iearning  for small instances of the task,  and  continues to perform well  when the  problem becomes too large for a table-based representation.
Dopamine Bonuses
Authors: Peter Dayan Sham Kakade
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Substantial data support a temporal difference (TO) model of  dopamine (OA) neuron activity in which the cells provide a global  error signal for reinforcement learning. However, in certain cir(cid:173) cumstances, OA activity seems anomalous under the TO model,  responding to non-rewarding stimuli. We address these anoma(cid:173) lies by suggesting that OA cells multiplex information about re(cid:173) ward bonuses, including Sutton's exploration bonuses and Ng et  al's non-distorting shaping bonuses. We interpret this additional  role for OA in terms of the unconditional attentional and psy(cid:173) chomotor effects of dopamine, having the computational role of  guiding exploration.
Sparse Greedy Gaussian Process Regression
Authors: Peter L. Bartlett Alex J. Smola
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  present  a  simple  sparse  greedy  technique  to  approximate  the  maximum a  posteriori estimate of Gaussian Processes  with much  improved  scaling  behaviour  in  the  sample  size  m.  In  particular,  computational  requirements  are  O(n2m),  storage  is  O(nm),  the  cost  for  prediction  is  0 ( n)  and  the  cost  to  compute  confidence  bounds  is  O(nm),  where  n  «:  m.  We  show  how  to  compute  a  stopping  criterion,  give  bounds  on  the  approximation  error,  and  show applications to large scale problems.
Large Scale Bayes Point Machines
Authors: Thore Graepel Ralf Herbrich
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: also known as the Bayes point -
The concept of averaging over classifiers is fundamental to the  Bayesian analysis of learning. Based on this viewpoint, it has re(cid:173) cently been demonstrated for linear classifiers that the centre of  mass of version space (the set of all classifiers consistent with the  training set) - exhibits excel(cid:173) lent generalisation abilities. However, the billiard algorithm as pre(cid:173) sented in [4] is restricted to small sample size because it requires  o (m 2 ) of memory and 0 (N . m2 ) computational steps where m  is the number of training patterns and N is the number of random  draws from the posterior distribution. In this paper we present a  method based on the simple perceptron learning algorithm which  allows to overcome this algorithmic drawback. The method is al(cid:173) gorithmically simple and is easily extended to the multi-class case.  We present experimental results on the MNIST data set of hand(cid:173) written digits which show that Bayes point machines (BPMs) are  competitive with the current world champion, the support vector  machine. In addition, the computational complexity of BPMs can  be tuned by varying the number of samples from the posterior.  Finally, rejecting test points on the basis of their (approximative)  posterior probability leads to a rapid decrease in generalisation er(cid:173) ror, e.g. 0.1% generalisation error for a given rejection rate of 10%.
Efficient Learning of Linear Perceptrons
Authors: Hans-Ulrich Simon Shai Ben-David
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  consider  the  existence  of efficient  algorithms for  learning the  class of half-spaces in ~n in the agnostic learning model (Le.,  mak(cid:173) ing no prior assumptions on the example-generating distribution).  The resulting combinatorial problem - finding  the best  agreement  half-space  over  an  input  sample - is  NP  hard  to  approximate to  within some constant factor.  We  suggest  a  way to circumvent this  theoretical bound by introducing a new measure of success for  such  algorithms.  An  algorithm is  IL-margin  successful  if the agreement  ratio of the half-space it outputs is as good as that of any half-space  once training points that are inside the IL-margins of its separating  hyper-plane are  disregarded.  We  prove  crisp  computational com(cid:173) plexity results with respect  to this success measure:  On one hand,  for  every positive IL,  there exist efficient  (poly-time) IL-margin suc(cid:173) cessful  learning  algorithms.  On  the  other  hand,  we  prove  that  unless  P=NP, there is  no  algorithm that runs  in time polynomial  in  the  sample  size  and  in  1/ IL  that  is  IL-margin  successful  for  all  IL> O.
Gaussianization
Authors: Ramesh A. Gopinath Scott Saobing Chen
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: High dimensional data modeling is difficult mainly because the so-called  "curse of dimensionality". We propose a technique called "Gaussianiza(cid:173) tion" for high dimensional density estimation, which alleviates the curse  of dimensionality by exploiting the independence structures in  the data.  Gaussianization is  motivated from  recent developments in  the statistics  literature:  projection pursuit, independent component analysis and Gaus(cid:173) sian  mixture  models  with  semi-tied  covariances.  We  propose  an  iter(cid:173) ative  Gaussianization  procedure  which  converges  weakly:  at  each  it(cid:173) eration,  the  data is  first  transformed  to  the  least dependent coordinates  and then each coordinate is  marginally Gaussianized by univariate tech(cid:173) niques.  Gaussianization offers density estimation sharper than traditional  kernel  methods and radial  basis function  methods.  Gaussianization can  be viewed as efficient solution of nonlinear independent component anal(cid:173) ysis and high dimensional projection pursuit.
Error-correcting Codes on a Bethe-like Lattice
Authors: David Saad, Yoshiyuki Kabashima Renato Vicente
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  analyze Gallager codes by employing a simple mean-field approxi(cid:173) mation that distorts the model geometry and preserves important interac(cid:173) tions between sites.  The method naturally recovers the probability prop(cid:173) agation decoding algorithm as  an extremization of a proper free-energy.  We  find  a thermodynamic phase transition that coincides with informa(cid:173) tion theoretical upper-bounds and explain the practical code performance  in terms of the free-energy landscape.
Homeostasis in a Silicon Integrate and Fire Neuron
Authors: Bradley A. Minch Shih-Chii Liu
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: In this work, we explore homeostasis in a silicon integrate-and-fire neu(cid:173) ron.  The neuron adapts its firing rate over long time periods on the order  of seconds or minutes so that it returns to its spontaneous firing rate after  a  lasting  perturbation.  Homeostasis  is  implemented  via  two  schemes.  One  scheme  looks  at  the  presynaptic  activity  and  adapts  the  synaptic  weight depending  on  the  presynaptic  spiking rate.  The  second scheme  adapts the synaptic "threshold" depending on the neuron's activity.  The  threshold is  lowered if the  neuron's activity  decreases over a long  time  and  is  increased  for  prolonged  increase  in  postsynaptic  activity.  Both  these  mechanisms  for  adaptation use  floating-gate  technology.  The re(cid:173) sults shown here are measured from  a chip fabricated in  a 2-J.lm  CMOS  process.
Incorporating Second-Order Functional Knowledge for Better Option Pricing
Authors: Yoshua Bengio, François Bélisle, Claude Nadeau, René Garcia Charles Dugas
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Incorporating prior knowledge of a particular task into the  architecture  of a learning algorithm can greatly improve generalization performance.  We  study  here  a case where we  know  that the  function  to be learned is  non-decreasing in two of its  arguments and convex in  one of them.  For  this purpose we propose a class of functions similar to multi-layer neural  networks but (1) that has those properties, (2) is a universal approximator  of continuous functions  with  these  and  other properties.  We  apply  this  new class  of functions  to  the task of modeling the price of call  options.  Experiments show improvements on regressing the price of call options  using the new types of function classes that incorporate the a priori con(cid:173) straints.
Spike-Timing-Dependent Learning for Oscillatory Networks
Authors: Zhaoping Li, John A. Hertz Silvia Scarpetta
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  apply to oscillatory networks a  class of learning rules in which  synaptic weights change proportional to pre- and post-synaptic ac(cid:173) tivity,  with  a  kernel  A(r) measuring the effect  for  a  postsynaptic  spike a time r  after the presynaptic one.  The resulting synaptic ma(cid:173) trices have an outer-product form in which the oscillating patterns  are  represented  as  complex  vectors.  In  a  simple  model,  the even  part of A(r) enhances the resonant response to learned stimulus by  reducing the effective  damping, while the odd part determines the  frequency of oscillation.  We relate our model to the olfactory cortex  and hippocampus and their presumed roles  in forming  associative  memories and input representations.
On Reversing Jensen's Inequality
Authors: Alex Pentland Tony Jebara
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Jensen's inequality is a powerful mathematical tool and one of the  workhorses in statistical learning. Its applications therein include the EM  algorithm, Bayesian estimation and Bayesian inference. Jensen com(cid:173) putes simple lower bounds on otherwise intractable quantities such as  products of sums and latent log-likelihoods. This simplification then per(cid:173) mits operations like integration and maximization. Quite often (i.e. in  discriminative learning) upper bounds are needed as well. We derive and  prove an efficient analytic inequality that provides such variational upper  bounds. This inequality holds for latent variable mixtures of exponential  family distributions and thus spans a wide range of contemporary statis(cid:173) tical models. We also discuss applications of the upper bounds including  maximum conditional likelihood, large margin discriminative models and  conditional Bayesian inference. Convergence, efficiency and prediction  results are shown. 1
From Mixtures of Mixtures to Adaptive Transform Coding
Authors: Todd K. Leen Cynthia Archer
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We establish a principled framework for adaptive transform cod(cid:173) ing. Transform coders are often constructed by concatenating an ad  hoc choice of transform with suboptimal bit allocation and quan(cid:173) tizer design. Instead, we start from a probabilistic latent variable  model in the form of a mixture of constrained Gaussian mixtures.  From this model we derive a transform coding algorithm, which is  a constrained version of the generalized Lloyd algorithm for vector  quantizer design. A byproduct of our derivation is the introduc(cid:173) tion of a new transform basis, which unlike other transforms (PCA,  DCT, etc.) is explicitly optimized for coding. Image compression  experiments show adaptive transform coders designed with our al(cid:173) gorithm improve compressed image signal-to-noise ratio up to 3 dB  compared to global transform coding and 0.5 to 2 dB compared to  other adaptive transform coders.
Algorithmic Stability and Generalization Performance
Authors: André Elisseeff Olivier Bousquet
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  present a novel way of obtaining PAC-style bounds on the gen(cid:173) eralization error of learning algorithms, explicitly using their stabil(cid:173) ity properties.  A stable learner is one for which the learned solution  does  not  change much with small  changes in the training set.  The  bounds we  obtain do not depend on any measure of the complexity  of the hypothesis space  (e.g.  VC  dimension)  but rather depend on  how  the  learning  algorithm  searches  this  space,  and  can  thus  be  applied  even when the VC  dimension is  infinite.  We  demonstrate  that regularization networks possess the required stability property  and apply our method to obtain new bounds on their generalization  performance.
The Kernel Trick for Distances
Authors: Bernhard Schölkopf
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: A method is described which, like the kernel trick in  support vector ma(cid:173) chines  (SVMs),  lets  us  generalize distance-based  algorithms to  operate  in  feature  spaces,  usually  nonlinearly  related  to  the  input  space.  This  is  done  by  identifying  a  class  of kernels  which  can  be  represented  as  norm-based distances in Hilbert spaces.  It turns out that common kernel  algorithms,  such as  SVMs and kernel PCA,  are actually really distance  based algorithms and can be run with that class of kernels, too.  As  well  as  providing  a  useful  new  insight  into  how  these  algorithms  work, the present work can form the basis for conceiving new algorithms.