mtybilly/Instruct2DS huggingface dataset:
Temporally Dependent Plasticity: An Information Theoretic Account
Authors: Gal Chechik, Naftali Tishby
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: The paradigm of Hebbian learning has recently received a novel in(cid:173) terpretation with the discovery of synaptic plasticity that depends  on the relative timing of pre and post  synaptic spikes.  This paper  derives a temporally dependent learning rule from the basic princi(cid:173) ple of mutual information maximization and studies its relation to  the experimentally observed  plasticity.  We  find  that  a  supervised  spike-dependent learning rule sharing similar structure with the ex(cid:173) perimentally observed plasticity increases mutual information to a  stable near  optimal  level.  Moreover,  the  analysis  reveals  how  the  temporal structure of time-dependent learning rules is  determined  by the temporal filter  applied by neurons over their inputs.  These  results suggest experimental prediction as to the dependency of the  learning rule on neuronal biophysical parameters
A Variational Mean-Field Theory for Sigmoidal Belief Networks
Authors: Chiranjib Bhattacharyya, S. Sathiya Keerthi
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: A variational derivation of Plefka's mean-field theory is  presented.  This  theory  is  then  applied  to  sigmoidal  belief networks  with  the  aid of further approximations.  Empirical evaluation on small scale  networks  show  that  the  proposed  approximations  are  quite  com(cid:173) petitive.
Robust Reinforcement Learning
Authors: Jun Morimoto, Kenji Doya
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: This paper proposes a  new  reinforcement  learning  (RL)  paradigm  that explicitly takes into account input disturbance as well as mod(cid:173) eling errors.  The use of environmental models  in  RL  is  quite pop(cid:173) ular  for  both  off-line  learning  by  simulations  and  for  on-line  ac(cid:173) tion planning.  However, the difference between the model and the  real environment can lead to unpredictable, often unwanted results.  Based on the theory of H oocontrol, we consider a  differential game  in  which  a  'disturbing'  agent  (disturber)  tries  to  make  the  worst  possible  disturbance  while  a  'control'  agent  (actor)  tries  to  make  the best control input.  The problem is formulated as finding a min(cid:173) max solution of a  value function that takes into account the norm  of the output deviation and the norm of the disturbance.  We derive  on-line  learning  algorithms  for  estimating  the  value  function  and  for  calculating the worst disturbance and the best  control in refer(cid:173) ence to the value function.  We  tested the paradigm, which we call  "Robust  Reinforcement  Learning  (RRL),"  in  the task  of inverted  pendulum.  In  the  linear  domain,  the  policy  and  the  value  func(cid:173) tion learned by the on-line algorithms coincided with those derived  analytically  by the linear  H ootheory.  For a  fully  nonlinear  swing(cid:173) up task, the control by RRL  achieved  robust  performance against  changes in the pendulum weight  and friction  while a  standard RL  control could not  deal with such environmental changes.
Explaining Away in Weight Space
Authors: Peter Dayan, Sham Kakade
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Explaining  away  has  mostly  been  considered  in  terms  of inference  of  states  in  belief networks.  We  show  how  it can  also  arise in a Bayesian  context in  inference about  the  weights  governing relationships  such  as  those  between stimuli  and reinforcers in  conditioning experiments such  as  bacA,'Ward blocking.  We  show how  explaining away  in  weight  space  can be accounted for using an  extension of a Kalman filter model; pro(cid:173) vide a new  approximate way  of looking at the Kalman gain  matrix as  a  whitener for  the correlation  matrix  of the  observation process;  suggest  a network implementation of this  whitener using an  architecture due to  Goodall; and show that the resulting model exhibits backward blocking.
Improved Output Coding for Classification Using Continuous Relaxation
Authors: Koby Crammer, Yoram Singer
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Output coding is  a general  method for  solving  multiclass  problems  by  reducing them to  multiple binary classification problems.  Previous re(cid:173) search on output coding has employed, almost solely, predefined discrete  codes. We describe an algorithm that improves the performance of output  codes by relaxing them  to  continuous codes.  The relaxation procedure  is  cast  as  an  optimization  problem and  is  reminiscent of the  quadratic  program for support vector machines.  We describe experiments with the  proposed algorithm, comparing it to  standard discrete output codes.  The  experimental results indicate that continuous relaxations of output codes  often improve the generalization performance, especially for short codes.
Learning Curves for Gaussian Processes Regression: A Framework for Good Approximations
Authors: Dörthe Malzahn, Manfred Opper
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Based  on  a  statistical mechanics  approach,  we  develop  a  method  for approximately computing average case learning curves for Gaus(cid:173) sian  process  regression  models.  The  approximation  works  well  in  the large  sample size  limit  and for  arbitrary dimensionality  of the  input space.  We explain how the approximation can be systemati(cid:173) cally improved and argue that similar techniques can be applied to  general likelihood models.
Sequentially Fitting ``Inclusive'' Trees for Inference in Noisy-OR Networks
Authors: Brendan J. Frey, Relu Patrascu, Tommi Jaakkola, Jodi Moran
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: An  important  class  of problems  can  be  cast  as inference  in noisy(cid:173) OR Bayesian networks,  where  the binary state of each variable is  a  logical  OR of noisy  versions  of the  states of the  variable's  par(cid:173) ents.  For example, in medical diagnosis, the presence of a symptom  can be expressed as a noisy-OR of the diseases that may cause the  symptom  - on  some  occasions,  a  disease  may fail  to  activate  the  symptom.  Inference  in  richly-connected noisy-OR networks is  in(cid:173) tractable,  but  approximate methods  (e .g.,  variational techniques)  are  showing  increasing  promise  as  practical  solutions.  One  prob(cid:173) lem  with  most  approximations  is  that  they  tend  to  concentrate  on  a  relatively  small  number  of  modes  in  the  true  posterior,  ig(cid:173) noring  other plausible  configurations of the  hidden  variables.  We  introduce a  new  sequential variational method for  bipartite noisy(cid:173) OR networks, that favors  including  all modes of the true posterior  and models the  posterior distribution  as  a  tree.  We  compare this  method with other approximations using an ensemble of networks  with network statistics that are comparable to the QMR-DT med(cid:173) ical diagnostic network. 
Inclusive variational approximations 
1  Approximate algorithms for probabilistic inference are gaining in popularity and are  now even being incorporated into VLSI hardware (T. Richardson, personal commu(cid:173) nication).  Approximate  methods include  variational techniques  (Ghahramani  and  Jordan 1997; Saul et al.  1996; Frey and Hinton 1999; Jordan et al.  1999), local prob(cid:173) ability propagation (Gallager 1963; Pearl 1988; Frey 1998; MacKay 1999a; Freeman  and Weiss 2001) and Markov chain Monte Carlo (Neal 1993; MacKay 1999b).  Many  algorithms have been proposed in each of these classes. 
One  problem that  most  of the  above  algorithms  suffer  from  is  a  tendency to  con(cid:173) centrate on a  relatively  small  number of modes  of the  target  distribution  (the  dis(cid:173) tribution  being  approximated).  In  the  case  of medical  diagnosis,  different  modes  correspond to different  explanations of the symptoms.  Markov  chain  Monte  Carlo  methods are usually guaranteed to eventually sample from  all  the modes,  but this  may take an extremely long time, even when tempered transitions  (Neal  1996)  are 
(a)
Periodic Component Analysis: An Eigenvalue Method for Representing Periodic Structure in Speech
Authors: Lawrence K. Saul, Jont B. Allen
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: An  eigenvalue  method  is  developed  for  analyzing  periodic  structure in  speech.  Signals are analyzed by  a matrix diagonalization reminiscent of  methods  for principal component analysis  (PCA)  and  independent com(cid:173) ponent analysis (ICA).  Our method-called periodic component analysis  (1l"CA)-uses  constructive interference to  enhance periodic  components  of the frequency  spectrum and  destructive interference  to  cancel  noise.  The front end emulates important aspects of auditory processing, such as  cochlear filtering, nonlinear compression, and insensitivity to phase, with  the  aim  of approaching the robustness of human  listeners.  The  method  avoids the inefficiencies of autocorrelation at the pitch period:  it does not  require  long  delay  lines,  and  it correlates  signals  at  a clock rate  on  the  order  of the  actual pitch,  as  opposed  to  the  original  sampling rate.  We  derive its cost function and present some experimental results.
Partially Observable SDE Models for Image Sequence Recognition Tasks
Authors: Javier R. Movellan, Paul Mineiro, Ruth J. Williams
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: This paper explores a framework for recognition of image sequences  using partially observable stochastic differential equation (SDE)  models. Monte-Carlo importance sampling techniques are used for  efficient estimation of sequence likelihoods and sequence likelihood  gradients. Once the network dynamics are learned, we apply the  SDE models to sequence recognition tasks in a manner similar to  the way Hidden Markov models (HMMs) are commonly applied.  The potential advantage of SDEs over HMMS is the use of contin(cid:173) uous state dynamics. We present encouraging results for a video  sequence recognition task in which SDE models provided excellent  performance when compared to hidden Markov models.
Combining ICA and Top-Down Attention for Robust Speech Recognition
Authors: Un-Min Bae, Soo-Young Lee
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  present  an  algorithm  which  compensates  for  the  mismatches  between characteristics of real-world problems and assumptions of  independent  component analysis algorithm.  To  provide additional  information  to  the  ICA  network,  we  incorporate top-down  selec(cid:173) tive  attention.  An  MLP  classifier is  added to the separated signal  channel  and  the  error  of  the  classifier  is  backpropagated  to  the  ICA  network.  This backpropagation process results  in  estimation  of expected ICA  output  signal for  the top-down  attention.  Then,  the unmixing matrix is  retrained according to a  new  cost function  representing the backpropagated error as well  as independence.  It  modifies the density of recovered signals to the density appropriate  for  classification.  For noisy speech  signal recorded in real environ(cid:173) ments,  the  algorithm  improved  the  recognition  performance  and  showed robustness against parametric changes.
A Comparison of Image Processing Techniques for Visual Speech Recognition Applications
Authors: Michael S. Gray, Terrence J. Sejnowski, Javier R. Movellan
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  examine  eight  different  techniques  for  developing  visual  rep(cid:173) resentations  in  machine  vision  tasks.  In  particular  we  compare  different  versions  of  principal  component  and  independent  com(cid:173) ponent  analysis  in  combination  with  stepwise  regression  methods  for  variable selection.  We  found  that local methods,  based on the  statistics of image patches, consistently outperformed global meth(cid:173) ods based on the statistics of entire images.  This result is consistent  with  previous  work  on  emotion  and facial  expression  recognition.  In  addition, the use of a stepwise regression technique for  selecting  variables and regions of interest substantially boosted performance.
The Missing Link - A Probabilistic Model of Document Content and Hypertext Connectivity
Authors: David A. Cohn, Thomas Hofmann
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  describe  a joint probabilistic  model  for  modeling  the  contents  and  inter-connectivity  of document collections such  as  sets of web pages  or  research  paper archives.  The  model  is  based  on  a  probabilistic  factor  decomposition  and  allows  identifying  principal  topics  of the  collection  as well as  authoritative documents within those topics.  Furthermore, the  relationships between topics is mapped out in order to build a predictive  model of link content.  Among the many applications of this approach are  information retrieval and search, topic identification, query disambigua(cid:173) tion, focused web crawling, web authoring, and bibliometric analysis.
The Use of Classifiers in Sequential Inference
Authors: Vasin Punyakanok, Dan Roth
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We  study  the  problem  of combining  the  outcomes  of several  different  classifiers in a way that provides a coherent inference that satisfies some  constraints.  In particular, we develop two general approaches for an im(cid:173) portant subproblem - identifying phrase structure.  The first is  a Marko(cid:173) vian approach that extends standard HMMs to allow the use of a rich ob(cid:173) servation  structure  and  of general  classifiers  to  model  state-observation  dependencies.  The second is  an extension of constraint satisfaction for(cid:173) malisms.  We  develop efficient combination algorithms under both mod(cid:173) els and study them experimentally in the context of shallow parsing.
Finding the Key to a Synapse
Authors: Thomas Natschläger, Wolfgang Maass
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Experimental data have shown that synapses are heterogeneous: different  synapses respond with different sequences of amplitudes of postsynaptic  responses to the same spike train.  Neither the role of synaptic dynamics  itself nor the  role  of the  heterogeneity of synaptic  dynamics  for  com(cid:173) putations in neural circuits is  well  understood.  We present in this article  methods that make it feasible to compute for a given synapse with known  synaptic parameters the spike train that is optimally fitted  to the synapse,  for example in the  sense that it produces the largest sum of postsynap(cid:173) tic responses.  To  our surprise we find  that most of these optimally fitted  spike  trains  match  common firing  patterns  of specific  types  of neurons  that are discussed in the literature.
The Unscented Particle Filter
Authors: Rudolph van der Merwe, Arnaud Doucet, Nando de Freitas, Eric A. Wan
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: In this paper, we  propose a  new  particle filter  based on sequential  importance sampling.  The algorithm uses  a  bank of unscented fil(cid:173) ters to obtain the importance proposal distribution.  This proposal  has  two  very  "nice"  properties.  Firstly,  it  makes  efficient  use  of  the  latest  available  information  and,  secondly,  it  can  have  heavy  tails.  As  a  result,  we  find  that  the  algorithm  outperforms  stan(cid:173) dard  particle filtering  and  other  nonlinear  filtering  methods  very  substantially.  This  experimental finding  is  in  agreement  with the  theoretical  convergence  proof for  the  algorithm.  The  algorithm  also includes resampling and (possibly) Markov chain Monte Carlo  (MCMC)  steps.
Algorithms for Non-negative Matrix Factorization
Authors: Daniel D. Lee, H. Sebastian Seung
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Non-negative matrix factorization (NMF) has previously been shown to 
be a useful decomposition for multivariate data. Two different multi- 
plicative algorithms for NMF are analyzed. They differ only slightly in 
the multiplicative factor used in the update rules. One algorithm can be 
shown to minimize the conventional least squares error while the other 
minimizes the generalized Kullback-Leibler divergence. The monotonic 
convergence of both algorithms can be proven using an auxiliary func- 
tion analogous to that used for proving convergence of the Expectation- 
Maximization algorithm. The algorithms can also be interpreted as diag- 
onally rescaled gradient descent, where the rescaling factor is optimally 
chosen to ensure convergence.
Divisive and Subtractive Mask Effects: Linking Psychophysics and Biophysics
Authors: Barbara Zenger, Christof Koch
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: We describe an analogy between psychophysically measured effects  in  contrast  masking,  and  the  behavior  of a  simple  integrate-and(cid:173) fire  neuron  that  receives  time-modulated  inhibition.  In  the  psy(cid:173) chophysical experiments, we tested observers ability to discriminate  contrasts of peripheral  Gabor patches  in  the  presence  of collinear  Gabor flankers.  The data reveal a complex interaction pattern that  we  account  for  by  assuming  that  flankers  provide  divisive  inhibi(cid:173) tion  to  the  target  unit  for  low  target  contrasts,  but  provide  sub(cid:173) tractive  inhibition  to  the  target  unit  for  higher  target  contrasts.  A similar switch from divisive to subtractive inhibition is  observed  in  an integrate-and-fire unit that receives  inhibition  modulated in  time such that the cell spends part of the time in  a high-inhibition  state  and  part  of  the  time  in  a  low-inhibition  state.  The  simi(cid:173) larity  between  the effects  suggests  that  one  may  cause  the  other.  The biophysical model makes testable predictions for  physiological  single-cell  recordings.
Noise Suppression Based on Neurophysiologically-motivated SNR Estimation for Robust Speech Recognition
Authors: Jürgen Tchorz, Michael Kleinschmidt, Birger Kollmeier
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: A  novel  noise  suppression  scheme  for  speech  signals  is  proposed  which  is  based  on  a  neurophysiologically-motivated estimation  of  the  local  signal-to-noise  ratio  (SNR)  in  different  frequency  chan(cid:173) nels.  For  SNR-estimation,  the  input  signal  is  transformed  into  so-called  Amplitude Modulation Spectrograms  (AMS),  which rep(cid:173) resent both spectral and temporal characteristics of the respective  analysis  frame,  and  which  imitate  the  representation  of modula(cid:173) tion  frequencies  in  higher  stages  of the  mammalian  auditory sys(cid:173) tem.  A neural network is  used to analyse AMS  patterns generated  from  noisy  speech  and  estimates  the  local  SNR.  Noise  suppres(cid:173) sion  is  achieved  by  attenuating  frequency  channels  according  to  their SNR. The noise suppression algorithm is evaluated in speaker(cid:173) independent  digit  recognition  experiments  and  compared to noise  suppression by Spectral Subtraction.
Dendritic Compartmentalization Could Underlie Competition and Attentional Biasing of Simultaneous Visual Stimuli
Authors: Kevin A. Archie, Bartlett W. Mel
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: Neurons in area V4 have relatively large receptive fields  (RFs), so multi(cid:173) ple visual features  are simultaneously "seen" by these cells.  Recordings  from  single  V 4  neurons  suggest  that  simultaneously  presented  stimuli  compete  to  set  the  output  firing  rate,  and  that  attention  acts  to  isolate  individual  features  by  biasing  the  competition in  favor  of the  attended  object.  We propose that both stimulus competition and attentional bias(cid:173) ing arise from the spatial segregation of afferent synapses onto different  regions of the excitable dendritic tree of V 4 neurons. The pattern of feed(cid:173) forward, stimulus-driven inputs follows from  a Hebbian rule:  excitatory  afferents  with  similar RFs  tend  to  group  together on  the  dendritic  tree,  avoiding randomly located inhibitory inputs with similar RFs.  The same  principle  guides  the  formation  of inputs  that  mediate  attentional  mod(cid:173) ulation.  Using  both  biophysically  detailed  compartmental  models  and  simplified models of computation in single neurons, we demonstrate that  such an architecture could account for the response properties and atten(cid:173) tional modulation of V 4 neurons.  Our results  suggest an important role  for nonlinear dendritic conductances in extrastriate cortical processing.
Smart Vision Chip Fabricated Using Three Dimensional Integration Technology
Authors: Hiroyuki Kurino, M. Nakagawa, Kang Wook Lee, Tomonori Nakamura, Yuusuke Yamada, Ki Tae Park, Mitsumasa Koyanagi
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: The  smart  VISIOn  chip  has  a  large  potential  for  application  in  general  purpose  high  speed  image  processing  systems.  In  order  to  fabricate  smart  vision  chips  including  photo  detector  compactly,  we  have  proposed  the  application  of  three  dimensional  LSI  technology  for  smart  vision  chips.  Three  dimensional  technology  has  great  potential  to  realize  new  neuromorphic  systems  inspired  by not only  the biological function but also  the  biological structure.  In this paper, we describe our three dimensional LSI technology for  neuromorphic circuits and the design of smart vision chips .
An Analysis of Convex Relaxations for MAP Estimation
Authors: Pawan Mudigonda, Vladimir Kolmogorov, Philip Torr
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: The problem of obtaining the maximum a posteriori estimate of a general discrete random field (i.e. a random field defined using a finite and discrete set of labels) is known to be N P-hard. However, due to its central importance in many applications, several approximate algorithms have been proposed in the literature. In this paper, we present an analysis of three such algorithms based on convex relaxations: (i) L P - S: the linear programming (L P) relaxation proposed by Schlesinger [20] for a special case and independently in [4, 12, 23] for the general case; (ii) Q P - R L: the quadratic programming (Q P) relaxation by Ravikumar and Lafferty [18]; and (iii) S O C P - M S: the second order cone programming (S O C P) relaxation first proposed by Muramatsu and Suzuki [16] for two label problems and later extended in [14] for a general label set. We show that the S O C P - M S and the Q P - R L relaxations are equivalent. Furthermore, we prove that despite the flexibility in the form of the constraints/objective function offered by Q P and S O C P, the L P - S relaxation strictly dominates (i.e. provides a better approximation than) Q P - R L and S O C P - M S. We generalize these results by defining a large class of S O C P (and equivalent Q P) relaxations which is dominated by the L P - S relaxation. Based on these results we propose some novel S O C P relaxations which strictly dominate the previous approaches.
Random Features for Large-Scale Kernel Machines
Authors: Ali Rahimi, Benjamin Recht
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: To accelerate the training of kernel machines, we propose to map the input data to a randomized low-dimensional feature space and then apply existing fast linear methods. The features are designed so that the inner products of the transformed data are approximately equal to those in the feature space of a user speciﬁed shift- invariant kernel. We explore two sets of random features, provide convergence bounds on their ability to approximate various radial basis kernels, and show that in large-scale classiﬁcation and regression tasks linear machine learning al- gorithms applied to these features outperform state-of-the-art large-scale kernel machines.
Compressed Regression
Authors: Shuheng Zhou, Larry Wasserman, John D. Lafferty
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Recent research has studied the role of sparsity in high dimensional regression and signal reconstruction, establishing theoretical limits for recovering sparse models from sparse data. In this paper we study a variant of this problem where the original $n$ input variables are compressed by a random linear transformation to $m \ll n$ examples in $p$ dimensions, and establish conditions under which a sparse linear model can be successfully recovered from the compressed data. A primary motivation for this compression procedure is to anonymize the data and preserve privacy by revealing little information about the original data. We characterize the number of random projections that are required for $\ell_1$-regularized compressed regression to identify the nonzero coefficients in the true model with probability approaching one, a property called ``sparsistence.'' In addition, we show that $\ell_1$-regularized compressed regression asymptotically predicts as well as an oracle linear model, a property called ``persistence.'' Finally, we characterize the privacy properties of the compression procedure in information-theoretic terms, establishing upper bounds on the rate of information communicated between the compressed and uncompressed data that decay to zero.
Predictive Matrix-Variate t Models
Authors: Shenghuo Zhu, Kai Yu, Yihong Gong
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: It is becoming increasingly important to learn from a partially-observed random matrix and predict its missing elements. We assume that the entire matrix is a single sample drawn from a matrix-variate t distribution and suggest a matrix-variate t model (MVTM) to predict those missing elements. We show that MVTM generalizes a range of known probabilistic models, and automatically performs model selection to encourage sparse predictive models. Due to the non-conjugacy of its prior, it is difficult to make predictions by computing the mode or mean of the posterior distribution. We suggest an optimization method that sequentially minimizes a convex upper-bound of the log-likelihood, which is very efficient and scalable. The experiments on a toy data and EachMovie dataset show a good predictive accuracy of the model.
Loop Series and Bethe Variational Bounds in Attractive Graphical Models
Authors: Alan S. Willsky, Erik B. Sudderth, Martin J. Wainwright
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Variational methods are frequently used to approximate or bound the partition or likelihood function of a Markov random field. Methods based on mean field theory are guaranteed to provide lower bounds, whereas certain types of convex relaxations provide upper bounds. In general, loopy belief propagation (BP) provides (often accurate) approximations, but not bounds. We prove that for a class of attractive binary models, the value specified by any fixed point of loopy BP always provides a lower bound on the true likelihood. Empirically, this bound is much better than the naive mean field bound, and requires no further work than running BP. We establish these lower bounds using a loop series expansion due to Chertkov and Chernyak, which we show can be derived as a consequence of the tree reparameterization characterization of BP fixed points.
Stable Dual Dynamic Programming
Authors: Tao Wang, Michael Bowling, Dale Schuurmans, Daniel J. Lizotte
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Recently, we have introduced a novel approach to dynamic programming and re- inforcement learning that is based on maintaining explicit representations of sta- tionary distributions instead of value functions. In this paper, we investigate the convergence properties of these dual algorithms both theoretically and empirically, and show how they can be scaled up by incorporating function approximation.
FilterBoost: Regression and Classification on Large Datasets
Authors: Joseph K. Bradley, Robert E. Schapire
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We study boosting in the ﬁltering setting, where the booster draws examples from an oracle instead of using a ﬁxed training set and so may train efﬁciently on very large datasets. Our algorithm, which is based on a logistic regression technique proposed by Collins, Schapire, & Singer, requires fewer assumptions to achieve bounds equivalent to or better than previous work. Moreover, we give the ﬁrst proof that the algorithm of Collins et al. is a strong PAC learner, albeit within the ﬁltering setting. Our proofs demonstrate the algorithm’s strong theoretical proper- ties for both classiﬁcation and conditional probability estimation, and we validate these results through extensive experiments. Empirically, our algorithm proves more robust to noise and overﬁtting than batch boosters in conditional probability estimation and proves competitive in classiﬁcation.
Unsupervised Feature Selection for Accurate Recommendation of High-Dimensional Image Data
Authors: Sabri Boutemedjet, Djemel Ziou, Nizar Bouguila
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Content-based image suggestion (CBIS) targets the recommendation of products based on user preferences on the visual content of images. In this paper, we mo- tivate both feature selection and model order identiﬁcation as two key issues for a successful CBIS. We propose a generative model in which the visual features and users are clustered into separate classes. We identify the number of both user and image classes with the simultaneous selection of relevant visual features us- ing the message length approach. The goal is to ensure an accurate prediction of ratings for multidimensional non-Gaussian and continuous image descriptors. Experiments on a collected data have demonstrated the merits of our approach.
Efficient Principled Learning of Thin Junction Trees
Authors: Anton Chechetka, Carlos Guestrin
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We present the first truly polynomial algorithm for learning the structure of bounded-treewidth junction trees -- an attractive subclass of probabilistic graphical models that permits both the compact representation of probability distributions and efficient exact inference. For a constant treewidth, our algorithm has polynomial time and sample complexity, and provides strong theoretical guarantees in terms of $KL$ divergence from the true distribution. We also present a lazy extension of our approach that leads to very significant speed ups in practice, and demonstrate the viability of our method empirically, on several real world datasets. One of our key new theoretical insights is a method for bounding the conditional mutual information of arbitrarily large sets of random variables with only a polynomial number of mutual information computations on fixed-size subsets of variables, when the underlying distribution can be approximated by a bounded treewidth junction tree.
Regret Minimization in Games with Incomplete Information
Authors: Martin Zinkevich, Michael Johanson, Michael Bowling, Carmelo Piccione
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Extensive games are a powerful model of multiagent decision-making scenarios with incomplete information. Finding a Nash equilibrium for very large instances of these games has received a great deal of recent attention. In this paper, we describe a new technique for solving large games based on regret minimization. In particular, we introduce the notion of counterfactual regret, which exploits the degree of incomplete information in an extensive game. We show how minimizing counterfactual regret minimizes overall regret, and therefore in self-play can be used to compute a Nash equilibrium. We demonstrate this technique in the domain of poker, showing we can solve abstractions of limit Texas Hold’em with as many as 1012 states, two orders of magnitude larger than previous methods.
A Bayesian Model of Conditioned Perception
Authors: Alan Stocker, Eero P. Simoncelli
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We propose an extended probabilistic model for human perception. We argue that in many circumstances, human observers simultaneously evaluate sensory evidence under different hypotheses regarding the underlying physical process that might have generated the sensory information. Within this context, inference can be optimal if the observer weighs each hypothesis according to the correct belief in that hypothesis. But if the observer commits to a particular hypothesis, the belief in that hypothesis is converted into subjective certainty, and subsequent perceptual behavior is suboptimal, conditioned only on the chosen hypothesis. We demonstrate that this framework can explain psychophysical data of a recently reported decision-estimation experiment. The model well accounts for the data, predicting the same estimation bias as a consequence of the preceding decision step. The power of the framework is that it has no free parameters except the degree of the observer's uncertainty about its internal sensory representation. All other parameters are defined by the particular experiment which allows us to make quantitative predictions of human perception to two modifications of the original experiment.
Scan Strategies for Meteorological Radars
Authors: Victoria Manfredi, Jim Kurose
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We address the problem of adaptive sensor control in dynamic resource-constrained sensor networks. We focus on a meteorological sensing network comprising radars that can perform sector scanning rather than always scanning 360 degrees. We compare three sector scanning strategies. The sit-and-spin strategy always scans 360 degrees. The limited lookahead strategy additionally uses the expected environmental state K decision epochs in the future, as predicted from Kalman filters, in its decision-making. The full lookahead strategy uses all expected future states by casting the problem as a Markov decision process and using reinforcement learning to estimate the optimal scan strategy. We show that the main benefits of using a lookahead strategy are when there are multiple meteorological phenomena in the environment, and when the maximum radius of any phenomenon is sufficiently smaller than the radius of the radars. We also show that there is a trade-off between the average quality with which a phenomenon is scanned and the number of decision epochs before which a phenomenon is rescanned.
The Tradeoffs of Large Scale Learning
Authors: Léon Bottou, Olivier Bousquet
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: This contribution develops a theoretical framework that takes into account the effect of approximate optimization on learning algorithms. The analysis shows distinct tradeoffs for the case of small-scale and large-scale learning problems. Small-scale learning problems are subject to the usual approximation--estimation tradeoff. Large-scale learning problems are subject to a qualitatively different tradeoff involving the computational complexity of the underlying optimization algorithms in non-trivial ways.
Inferring Elapsed Time from Stochastic Neural Processes
Authors: Misha Ahrens, Maneesh Sahani
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Many perceptual processes and neural computations, such as speech recognition, motor control and learning, depend on the ability to measure and mark the passage of time. However, the processes that make such temporal judgements possible are unknown. A number of different hypothetical mechanisms have been advanced, all of which depend on the known, temporally predictable evolution of a neural or psychological state, possibly through oscillations or the gradual decay of a memory trace. Alternatively, judgements of elapsed time might be based on observations of temporally structured, but stochastic processes. Such processes need not be specific to the sense of time; typical neural and sensory processes contain at least some statistical structure across a range of time scales. Here, we investigate the statistical properties of an estimator of elapsed time which is based on a simple family of stochastic process.
A learning framework for nearest neighbor search
Authors: Lawrence Cayton, Sanjoy Dasgupta
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Can we leverage learning techniques to build a fast nearest-neighbor (NN) retrieval data structure? We present a general learning framework for the NN problem in which sample queries are used to learn the parameters of a data structure that minimize the retrieval time and/or the miss rate. We explore the potential of this novel framework through two popular NN data structures: KD-trees and the rectilinear structures employed by locality sensitive hashing. We derive a generalization theory for these data structure classes and present simple learning algorithms for both. Experimental results reveal that learning often improves on the already strong performance of these data structures.
Reinforcement Learning in Continuous Action Spaces through Sequential Monte Carlo Methods
Authors: Alessandro Lazaric, Marcello Restelli, Andrea Bonarini
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Learning in real-world domains often requires to deal with continuous state and action spaces. Although many solutions have been proposed to apply Reinforce- ment Learning algorithms to continuous state problems, the same techniques can be hardly extended to continuous action spaces, where, besides the computation of a good approximation of the value function, a fast method for the identiﬁcation of the highest-valued action is needed. In this paper, we propose a novel actor-critic approach in which the policy of the actor is estimated through sequential Monte Carlo methods. The importance sampling step is performed on the basis of the values learned by the critic, while the resampling step modiﬁes the actor’s policy. The proposed approach has been empirically compared to other learning algo- rithms into several domains; in this paper, we report results obtained in a control problem consisting of steering a boat across a river.
Ensemble Clustering using Semidefinite Programming
Authors: Vikas Singh, Lopamudra Mukherjee, Jiming Peng, Jinhui Xu
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We consider the ensemble clustering problem where the task is to ‘aggregate’ multiple clustering solutions into a single consolidated clustering that maximizes the shared information among given clustering solutions. We obtain several new results for this problem. First, we note that the notion of agreement under such circumstances can be better captured using an agreement measure based on a 2D string encoding rather than voting strategy based methods proposed in literature. Using this generalization, we ﬁrst derive a nonlinear optimization model to max- imize the new agreement measure. We then show that our optimization problem can be transformed into a strict 0-1 Semideﬁnite Program (SDP) via novel con- vexiﬁcation techniques which can subsequently be relaxed to a polynomial time solvable SDP. Our experiments indicate improvements not only in terms of the proposed agreement measure but also the existing agreement measures based on voting strategies. We discuss evaluations on clustering and image segmentation databases.
Theoretical Analysis of Heuristic Search Methods for Online POMDPs
Authors: Stephane Ross, Joelle Pineau, Brahim Chaib-draa
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Planning in partially observable environments remains a challenging problem, despite significant recent advances in offline approximation techniques. A few online methods have also been proposed recently, and proven to be remarkably scalable, but without the theoretical guarantees of their offline counterparts. Thus it seems natural to try to unify offline and online techniques, preserving the theoretical properties of the former, and exploiting the scalability of the latter. In this paper, we provide theoretical guarantees on an anytime algorithm for POMDPs which aims to reduce the error made by approximate offline value iteration algorithms through the use of an efficient online searching procedure. The algorithm uses search heuristics based on an error analysis of lookahead search, to guide the online search towards reachable beliefs with the most potential to reduce error. We provide a general theorem showing that these search heuristics are admissible, and lead to complete and epsilon-optimal algorithms. This is, to the best of our knowledge, the strongest theoretical result available for online POMDP solution methods. We also provide empirical evidence showing that our approach is also practical, and can find (provably) near-optimal solutions in reasonable time.
A Constraint Generation Approach to Learning Stable Linear Dynamical Systems
Authors: Byron Boots, Geoffrey J. Gordon, Sajid M. Siddiqi
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Stability is a desirable characteristic for linear dynamical systems, but it is often ignored by algorithms that learn these systems from data. We propose a novel method for learning stable linear dynamical systems: we formulate an approxima- tion of the problem as a convex program, start with a solution to a relaxed version of the program, and incrementally add constraints to improve stability. Rather than continuing to generate constraints until we reach a feasible solution, we test stability at each step; because the convex program is only an approximation of the desired problem, this early stopping rule can yield a higher-quality solution. We apply our algorithm to the task of learning dynamic textures from image sequences as well as to modeling biosurveillance drug-sales data. The constraint generation approach leads to noticeable improvement in the quality of simulated sequences. We compare our method to those of Lacy and Bernstein [1, 2], with positive results in terms of accuracy, quality of simulated sequences, and efﬁciency.
An online Hebbian learning rule that performs Independent Component Analysis
Authors: Claudia Clopath, André Longtin, Wulfram Gerstner
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Independent component analysis (ICA) is a powerful method to decouple signals. Most of the algorithms performing ICA do not consider the temporal correlations of the signal, but only higher moments of its amplitude distribution. Moreover, they require some preprocessing of the data (whitening) so as to remove second order correlations. In this paper, we are interested in understanding the neural mechanism responsible for solving ICA. We present an online learning rule that exploits delayed correlations in the input. This rule performs ICA by detecting joint variations in the firing rates of pre- and postsynaptic neurons, similar to a local rate-based Hebbian learning rule.
Modeling Natural Sounds with Modulation Cascade Processes
Authors: Richard Turner, Maneesh Sahani
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Natural sounds are structured on many time-scales. A typical segment of speech, for example, contains features that span four orders of magnitude: Sentences (~1s); phonemes (~0.1s); glottal pulses (~0.01s); and formants (<0.001s). The auditory system uses information from each of these time-scales to solve complicated tasks such as auditory scene analysis. One route toward understanding how auditory processing accomplishes this analysis is to build neuroscience-inspired algorithms which solve similar tasks and to compare the properties of these algorithms with properties of auditory processing. There is however a discord: Current machine-audition algorithms largely concentrate on the shorter time-scale structures in sounds, and the longer structures are ignored. The reason for this is two-fold. Firstly, it is a difficult technical problem to construct an algorithm that utilises both sorts of information. Secondly, it is computationally demanding to simultaneously process data both at high resolution (to extract short temporal information) and for long duration (to extract long temporal information). The contribution of this work is to develop a new statistical model for natural sounds that captures structure across a wide range of time-scales, and to provide efficient learning and inference algorithms. We demonstrate the success of this approach on a missing data task.