mtybilly/Instruct2DS huggingface dataset:
Neuron-MOS Temporal Winner Search Hardware for Fully-Parallel Data Processing
Authors: Tsutomu Nakai, Tatsuo Morimoto, Ryu Kaihara, Takeo Yamashita, Tadahiro Ohmi Tadashi Shibata
Published in: Advances in Neural Information Processing Systems 8  (NIPS 1995) (Main Conference Track), 1995

Abstract: A  unique  architecture  of  winner  search  hardware  has  been  de(cid:173) veloped  using  a  novel  neuron-like  high  functionality  device  called  Neuron  MOS  transistor  (or  vMOS  in  short)  [1,2]  as  a  key  circuit  element.  The circuits developed  in  this work  can find  the location  of the  maximum  (or  minimum)  signal  among  a  number  of input  data on  the  continuous-time  basis,  thus enabling real-time  winner  tracking as well as fully-parallel sorting of multiple input data.  We  have  developed  two  circuit  schemes.  One  is  an  ensemble  of self(cid:173) loop-selecting v M OS ring oscillators finding the winner as an oscil(cid:173) lating node.  The other is  an ensemble of vMOS variable threshold  inverters receiving a common ramp-voltage for  competitive excita(cid:173) tion  where  data sorting  is  conducted  through  consecutive  winner  search actions.  Test circuits were fabricated by a double-polysilicon  CMOS  process  and  their  operation  has  been  experimentally veri(cid:173) fied.
Human Reading and the Curse of Dimensionality
Authors: Gale Martin
Published in: Advances in Neural Information Processing Systems 8  (NIPS 1995) (Main Conference Track), 1995

Abstract: Whereas optical character recognition (OCR) systems learn to clas(cid:173) sify single characters;  people learn to classify long character strings  in  parallel,  within  a  single  fixation .  This  difference  is  surprising  because  high  dimensionality is  associated  with  poor  classification  learning.  This  paper  suggests  that  the  human  reading  system  avoids  these  problems  because  the  number  of to-be-classified  im(cid:173) ages  is  reduced  by  consistent  and  optimal eye  fixation  positions,  and  by  character sequence  regularities. 
An interesting difference exists between human reading and optical character recog(cid:173) nition (OCR) systems.  The input/output dimensionality of character  classification  in  human reading is much greater than that for  OCR systems (see  Figure  1) .  OCR  systems  classify  one  character  at  time;  while  the  human  reading  system  classifies  as  many  as  8-13  characters  per  eye  fixation  (Rayner,  1979)  and  within  a  fixation,  character  category  and  sequence  information is  extracted  in  parallel  (Blanchard,  McConkie,  Zola,  and  Wolverton,  1984;  Reicher,  1969). 
OCR  (Low  Dbnensionality)  I Dorothy  lived In the  .... I  [Q]  ... _ ....................................  "D"  ~ ................................. ..  "0"  o
Unsupervised Pixel-prediction
Authors: William R. Softky
Published in: Advances in Neural Information Processing Systems 8  (NIPS 1995) (Main Conference Track), 1995

Abstract: When a sensory system constructs a model of the environment  from its input, it might need to verify the model's accuracy. One  method of verification is multivariate time-series prediction: a good  model could predict the near-future activity of its inputs, much  as a good scientific theory predicts future data. Such a predict(cid:173) ing model would require copious top-down connections to compare  the predictions with the input. That feedback could improve the  model's performance in two ways: by biasing internal activity to(cid:173) ward expected patterns, and by generating specific error signals if  the predictions fail. A proof-of-concept model-an event-driven,  computationally efficient layered network, incorporating "cortical"  features like all-excitatory synapses and local inhibition- was con(cid:173) structed to make near-future predictions of a simple, moving stim(cid:173) ulus. After unsupervised learning, the network contained units not  only tuned to obvious features of the stimulus like contour orienta(cid:173) tion and motion, but also to contour discontinuity ("end-stopping")  and illusory contours.
Quadratic-Type Lyapunov Functions for Competitive Neural Networks with Different Time-Scales
Authors: Anke Meyer-Bäse
Published in: Advances in Neural Information Processing Systems 8  (NIPS 1995) (Main Conference Track), 1995

Abstract: The dynamics of complex neural networks modelling the self(cid:173) organization process in cortical maps must include the aspects of  long and short-term memory. The behaviour of the network is such  characterized by an equation of neural activity as a fast phenom(cid:173) enon and an equation of synaptic modification as a slow part of the  neural system. We present a quadratic-type Lyapunov function for  the flow of a competitive neural system with fast and slow dynamic  variables. We also show the consequences of the stability analysis  on the neural net parameters.
Learning long-term dependencies is not as difficult with NARX networks
Authors: Bill G. Horne, Peter Tiño, C. Lee Giles Tsungnan Lin
Published in: Advances in Neural Information Processing Systems 8  (NIPS 1995) (Main Conference Track), 1995

Abstract: It  has  recently  been  shown  that  gradient  descent  learning  algo(cid:173) rithms for  recurrent  neural  networks can  perform poorly  on  tasks  that  involve  long-term  dependencies.  In  this  paper  we  explore  this  problem  for  a  class  of architectures  called  NARX  networks,  which  have  powerful  representational capabilities.  Previous  work  reported that gradient descent learning is  more effective in NARX  networks  than  in  recurrent  networks  with  "hidden  states".  We  show  that although  NARX  networks  do  not  circumvent the  prob(cid:173) lem  of long-term dependencies,  they  can  greatly  improve  perfor(cid:173) mance  on  such  problems.  We  present  some  experimental 'results  that  show  that  NARX  networks  can  often  retain  information  for  two to three times as long as conventional recurrent  networks.
Learning the Structure of Similarity
Authors: Joshua B. Tenenbaum
Published in: Advances in Neural Information Processing Systems 8  (NIPS 1995) (Main Conference Track), 1995

Abstract: The  additive  clustering (ADCL US)  model (Shepard &  Arabie,  1979)  treats  the  similarity of two  stimuli  as  a  weighted  additive  measure  of their  common features.  Inspired  by  recent  work  in  unsupervised  learning with  multiple cause  models,  we  propose  anew, statistically  well-motivated  algorithm  for  discovering  the  structure  of  natural  stimulus classes  using the ADCLUS model, which promises substan(cid:173) tial gains  in  conceptual  simplicity,  practical  efficiency,  and  solution  quality over earlier efforts.  We  also present  preliminary results  with  artificial data and two classic similarity data sets.
Investment Learning with Hierarchical PSOMs
Authors: Helge Ritter Jörg A. Walter
Published in: Advances in Neural Information Processing Systems 8  (NIPS 1995) (Main Conference Track), 1995

Abstract: We propose a hierarchical scheme for rapid learning of context dependent  "skills"  that  is  based  on  the  recently  introduced  "Parameterized  Self(cid:173) Organizing Map" ("PSOM"). The underlying idea is to first invest some  learning effort to  specialize the  system  into  a  rapid learner for  a  more  restricted range of contexts. 
The specialization is carried out by a prior "investment learning stage",  during which the system acquires a set of basis mappings or "skills" for  a  set of prototypical contexts.  Adaptation  of a "skill" to a new context  can then be achieved by interpolating in the space of the basis mappings  and thus can be extremely rapid. 
We demonstrate the potential of this approach for the task of a 3D visuo(cid:173) motor map for  a  Puma robot and  two  cameras.  This  includes  the for(cid:173) ward and backward robot kinematics in  3D end effector coordinates, the  2D+2D retina coordinates and also the 6D joint angles.  After the invest(cid:173) ment phase  the transformation can  be learned for  a new camera set-up  with a single observation.
How Perception Guides Production in Birdsong Learning
Authors: Christopher L. Fry
Published in: Advances in Neural Information Processing Systems 8  (NIPS 1995) (Main Conference Track), 1995

Abstract: A  c.:omputational  model  of  song  learning  in  the  song  sparrow  (M elospiza  melodia)  learns  to  categorize  the  different  syllables  of  a  song  sparrow  song  and  uses  this  categorization to  train  itself to  reproduce  song.  The model fills  a crucial gap in the computational  explanation  of birdsong  learning  by  exploring  the  organization of  perception  in  songbirds.  It shows  how  competitive  learning  may  lead  to  the  organization  of  a  specific  nucleus  in  the  bird  brain,  replicates  the  song  production  results  of a  previous  model  (Doya  and  Sejnowski,  1995),  and  demonstrates  how  perceptual  learning  can  guide production through  reinforcement  learning.
Stable Fitted Reinforcement Learning
Authors: Geoffrey J. Gordon
Published in: Advances in Neural Information Processing Systems 8  (NIPS 1995) (Main Conference Track), 1995

Abstract: We  describe  the  reinforcement  learning  problem,  motivate  algo(cid:173) rithms which seek an approximation to the Q function, and present  new  convergence results for  two such algorithms. 
1 
INTRODUCTION AND BACKGROUND 
Imagine an agent acting in some environment.  At time t, the environment is in some  state Xt  chosen from  a finite set of states.  The agent perceives Xt,  and is  allowed to  choose an action at from  some finite  set of actions.  The environment then changes  state,  so  that  at  time  (t + 1)  it  is  in  a  new  state  Xt+1  chosen  from  a  probability  distribution which depends only on  Xt  and at.  Meanwhile,  the agent experiences a  real-valued cost  Ct,  chosen  from  a  distribution  which  also  depends  only  on  Xt  and  at  and which  has finite  mean and variance. 
Such  an environment is  called  a  Markov  decision  process,  or MDP.  The reinforce(cid:173) ment learning problem is  to control an MDP  to minimize the expected discounted  cost  Lt ,tCt  for  some  discount  factor,  E  [0,1].  Define  the  function  Q  so  that  Q(x, a)  is  the cost for  being in state x  at time  0,  choosing action a,  and behaving  optimally from  then on.  If we  can discover Q,  we  have solved the problem:  at each  step,  we  may simply choose at  to minimize Q(xt, at).  For more information about  MDPs, see  (Watkins,  1989, Bertsekas and Tsitsiklis,  1989).  We  may distinguish two classes of problems, online and offline.  In  the offline  prob(cid:173) lem,  we have a full  model of the MDP: given a state and an action, we  can describe  the  distributions  of the  cost  and  the  next  state.  We  will  be  concerned  with  the  online problem, in which our knowledge of the MDP is  limited to what we  can dis(cid:173) cover by  interacting with it.  To solve an online problem,  we  may approximate the  transition  and  cost functions,  then  proceed  as for  an offline  problem  (the indirect  approach);  or  we  may  try  to  learn  the Q  function  without  the  intermediate  step  (the direct approach).  Either approach may work better for  any given problem:  the 
Stable Fitted Reinforcement  Learning
Discriminant Adaptive Nearest Neighbor Classification and Regression
Authors: Robert Tibshirani Trevor Hastie
Published in: Advances in Neural Information Processing Systems 8  (NIPS 1995) (Main Conference Track), 1995

Abstract: Nearest  neighbor  classification expects  the  class  conditional  prob(cid:173) abilities  to  be  locally  constant,  and  suffers  from  bias  in  high  di(cid:173) mensions  We  propose  a  locally  adaptive form  of nearest  neighbor  classification  to try  to finesse  this curse  of dimensionality.  We  use  a  local  linear  discriminant  analysis  to  estimate  an  effective  met(cid:173) ric  for  computing neighborhoods.  We  determine the local decision  boundaries  from  centroid  information,  and  then  shrink  neighbor(cid:173) hoods  in  directions  orthogonal to  these  local  decision  boundaries,  and  elongate  them  parallel  to  the  boundaries.  Thereafter,  any  neighborhood-based  classifier  can be employed, using the  modified  neighborhoods.  We  also  propose  a  method  for  global  dimension  reduction, that combines local dimension information. We  indicate  how  these  techniques  can be  extended  to the  regression  problem.
A Predictive Switching Model of Cerebellar Movement Control
Authors: James C. Houk Andrew G. Barto
Published in: Advances in Neural Information Processing Systems 8  (NIPS 1995) (Main Conference Track), 1995

Abstract: We present a hypothesis about how the cerebellum could partici(cid:173) pate in regulating movement in the presence of significant feedback  delays without resorting to a forward model of the motor plant. We  show how a simplified cerebellar model can learn to control end(cid:173) point positioning of a nonlinear spring-mass system with realistic  delays in both afferent and efferent pathways. The model's opera(cid:173) tion involves prediction, but instead of predicting sensory input, it  directly regulates movement by reacting in an anticipatory fashion  to input patterns that include delayed sensory feedback.
Recurrent Neural Networks for Missing or Asynchronous Data
Authors: Francois Gingras Yoshua Bengio
Published in: Advances in Neural Information Processing Systems 8  (NIPS 1995) (Main Conference Track), 1995

Abstract: In this paper we  propose recurrent neural networks with feedback into the input  units for  handling two  types  of data analysis problems.  On the one  hand,  this  scheme can be used for static data when some of the input variables are missing.  On  the  other  hand,  it can also  be  used  for  sequential  data,  when  some of the  input variables are missing or are available at different frequencies.  Unlike in the  case of probabilistic models (e.g.  Gaussian) of the missing variables, the network  does  not  attempt  to  model the  distribution  of the  missmg  variables given  the  observed variables.  Instead it is a  more "discriminant" approach that fills  in the  missing variables for  the sole purpose of minimizing a  learning criterion  (e.g.,  to  minimize an output error).
Agnostic Active Learning Without Constraints
Authors: Daniel J. Hsu, John Langford, Tong Zhang Alina Beygelzimer
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We present and analyze an agnostic active learning algorithm that works without keeping a version space. This is unlike all previous approaches where a restricted set of candidate hypotheses is maintained throughout learning, and only hypotheses from this set are ever returned. By avoiding this version space approach, our algorithm sheds the computational burden and brittleness associated with maintaining version spaces, yet still allows for substantial improvements over supervised learning for classification.
A Dirty Model for Multi-task Learning
Authors: Sujay Sanghavi, Chao Ruan, Pradeep K. Ravikumar Ali Jalali
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We consider the multiple linear regression problem, in a setting where some of the set of relevant features could be shared across the tasks. A lot of recent research has studied the use of $\ell_1/\ell_q$ norm block-regularizations with $q > 1$  for such (possibly) block-structured problems, establishing strong guarantees on recovery even under high-dimensional scaling where the number of features scale with the number of observations. However, these papers also caution that the performance of such block-regularized methods are very dependent on the {\em extent} to which the features are shared across tasks. Indeed they show~\citep{NWJoint} that if the extent of overlap is less than a threshold, or even if parameter {\em values} in the shared features are highly uneven, then block $\ell_1/\ell_q$ regularization could actually perform {\em worse} than simple separate elementwise $\ell_1$ regularization. We are far away from a realistic multi-task setting: not only do the set of relevant features have to be exactly the same across tasks, but their values have to as well.  Here, we ask the question: can we leverage support and parameter overlap when it exists, but not pay a penalty when it does not? Indeed, this falls under a more general question of whether we can model such \emph{dirty data} which may not fall into a single neat structural bracket (all block-sparse, or all low-rank and so on). Here, we take a first step, focusing on developing a dirty model for the multiple regression problem. Our method uses a very simple idea: we decompose  the parameters into two components and {\em regularize these differently.} We show both theoretically and empirically, our method strictly and noticeably outperforms both $\ell_1$ and $\ell_1/\ell_q$ methods, over the entire range of possible overlaps. We also provide theoretical guarantees that the method performs well under high-dimensional scaling.
Generative Local Metric Learning for Nearest Neighbor Classification
Authors: Byoung-tak Zhang, Daniel D. Lee Yung-kyun Noh
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We consider the problem of learning a local metric to enhance the performance of nearest neighbor classification. Conventional metric learning methods attempt to separate data distributions in a purely discriminative manner; here we show how to take advantage of information from parametric generative models. We focus on the bias in the information-theoretic error arising from finite sampling effects, and find an appropriate local metric that maximally reduces the bias based upon knowledge from generative models. As a byproduct, the asymptotic theoretical analysis in this work relates metric learning with dimensionality reduction, which was not understood from previous discriminative approaches. Empirical experiments show that this learned local metric enhances the discriminative nearest neighbor performance on various datasets using simple class conditional generative models.
Relaxed Clipping: A Global Training Method for Robust Regression and Classification
Authors: Linli Xu, Martha White, Dale Schuurmans, Yao-liang Yu Min Yang
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Robust regression and classification are often thought to require non-convex loss functions that prevent scalable, global training. However, such a view neglects the possibility of reformulated training methods that can yield practically solvable alternatives. A natural way to make a loss function more robust to outliers is to truncate loss values that exceed a maximum threshold. We demonstrate that a relaxation of this form of ``loss clipping'' can be made globally solvable and applicable to any standard loss while guaranteeing robustness against outliers. We present a generic procedure that can be applied to standard loss functions and demonstrate improved robustness in regression and classification problems.
Linear readout from a neural population with partial correlation data
Authors: Ranulfo Romo, Christian K. Machens Adrien Wohrer
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: How much information does a neural population convey about a stimulus? Answers to this question are known to strongly depend on the correlation of response variability in neural populations. These noise correlations, however, are essentially immeasurable as the number of parameters in a noise correlation matrix grows quadratically with population size. Here, we suggest to bypass this problem by imposing a parametric model on a noise correlation matrix. Our basic assumption is that noise correlations arise due to common inputs between neurons. On average, noise correlations will therefore reflect signal correlations, which can be measured in neural populations. We suggest an explicit parametric dependency between signal and noise correlations. We show how this dependency can be used to fill the gaps" in noise correlations matrices using an iterative application of the Wishart distribution over positive definitive matrices. We apply our method to data from the primary somatosensory cortex of monkeys performing a two-alternative-forced choice task. We compare the discrimination thresholds read out from the population of recorded neurons with the discrimination threshold of the monkey and show that our method predicts different results than simpler, average schemes of noise correlations."
On Herding and the Perceptron Cycling Theorem
Authors: Yutian Chen, Laurens Maaten, Max Welling Andrew Gelfand
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: The paper develops a connection between traditional perceptron algorithms and recently introduced herding algorithms. It is shown that both algorithms can be viewed as an application of the perceptron cycling theorem. This connection strengthens some herding results and suggests new (supervised) herding algorithms that, like CRFs or discriminative RBMs, make predictions by conditioning on the input attributes. We develop and investigate variants of conditional herding, and show that conditional herding leads to practical algorithms that perform better than or on par with related classifiers such as the voted perceptron and the discriminative RBM.
Tiled convolutional neural networks
Authors: Zhenghao Chen, Daniel Chia, Pang W. Koh, Quoc V. Le, Andrew Y. Ng Jiquan Ngiam
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Convolutional neural networks (CNNs) have been successfully applied to many tasks such as digit and object recognition. Using convolutional (tied) weights signiﬁcantly reduces the number of parameters that have to be learned, and also allows translational invariance to be hard-coded into the architecture. In this paper, we consider the problem of learning invariances, rather than relying on hard-coding. We propose tiled convolution neural networks (Tiled CNNs), which use a regular “tiled” pattern of tied weights that does not require that adjacent hidden units share identical weights, but instead requires only that hidden units k steps away from each other to have tied weights. By pooling over neighboring units, this architecture is able to learn complex invariances (such as scale and rotational invariance) beyond translational invariance. Further, it also enjoys much of CNNs’ advantage of having a relatively small number of learned parameters (such as ease of learning and greater scalability). We provide an efficient learning algorithm for Tiled CNNs based on Topographic ICA, and show that learning complex invariant features allows us to achieve highly competitive results for both the NORB and CIFAR-10 datasets.
Decomposing Isotonic Regression for Efficiently Solving Large Problems
Authors: Saharon Rosset, Moni Shahar Ronny Luss
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: A new algorithm for isotonic regression is presented based on recursively partitioning the solution space. We develop efficient methods for each partitioning subproblem through an equivalent representation as a network flow problem, and prove that this sequence of partitions converges to the global solution. These network flow problems can further be decomposed in order to solve very large problems. Success of isotonic regression in prediction and our algorithm's favorable computational properties are demonstrated through simulated examples as large as 2x10^5 variables and 10^7 constraints.
Learning Kernels with Radiuses of Minimum Enclosing Balls
Authors: Guangyun Chen, Chang-shui Zhang Kun Gai
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: In this paper, we point out that there exist scaling and initialization problems in most existing multiple kernel learning (MKL) approaches, which employ the large margin principle to jointly learn both a kernel and an SVM classifier. The reason is that the margin itself can not well describe how good a kernel is due to the negligence of the scaling. We use the ratio between the margin and the radius of the minimum enclosing ball to measure the goodness of a kernel, and present a new minimization formulation for kernel learning. This formulation is invariant to scalings of learned kernels, and when learning linear combination of basis kernels it is also invariant to scalings of basis kernels and to the types (e.g., L1 or L2) of norm constraints on combination coefficients. We establish the differentiability of our formulation, and propose a gradient projection algorithm for kernel learning. Experiments show that our method significantly outperforms both SVM with the uniform combination of basis kernels and other state-of-art MKL approaches.
Label Embedding Trees for Large Multi-Class Tasks
Authors: Jason Weston, David Grangier Samy Bengio
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Multi-class classification becomes challenging at test time when the number of classes is very large and testing against every possible class can become computationally infeasible. This problem can be alleviated by imposing (or learning) a structure over the set of classes. We propose an algorithm for learning a tree-structure of classifiers which, by optimizing the overall tree loss, provides superior accuracy to existing tree labeling methods. We also propose a method that learns to embed labels in a low dimensional space that is faster than non-embedding approaches and has superior accuracy to existing embedding approaches. Finally we combine the two ideas resulting in the label embedding tree that outperforms alternative methods including One-vs-Rest while being orders of magnitude faster.
Deep Coding Network
Authors: Tong Zhang, Shenghuo Zhu, Kai Yu Yuanqing Lin
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: This paper proposes a principled extension of the traditional single-layer flat sparse coding scheme, where a two-layer coding scheme is derived based on theoretical analysis of nonlinear functional approximation that extends recent results for local coordinate coding. The two-layer approach can be easily generalized to deeper structures in a hierarchical multiple-layer manner. Empirically, it is shown that the deep coding approach yields improved performance in benchmark datasets.
Transduction with Matrix Completion: Three Birds with One Stone
Authors: Ben Recht, Junming Xu, Robert Nowak, Xiaojin Zhu Andrew Goldberg
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We pose transductive classification as a matrix completion problem. By assuming the underlying matrix has a low rank, our formulation is able to handle three problems simultaneously: i) multi-label learning, where each item has more than one label, ii) transduction, where most of these labels are unspecified, and iii) missing data, where a large number of features are missing. We obtained satisfactory results on several real-world tasks, suggesting that the low rank assumption may not be as restrictive as it seems. Our method allows for different loss functions to apply on the feature and label entries of the matrix. The resulting nuclear norm minimization problem is solved with a modified fixed-point continuation method that is guaranteed to find the global optimum.
Extended Bayesian Information Criteria for Gaussian Graphical Models
Authors: Mathias Drton Rina Foygel
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Gaussian graphical models with sparsity in the inverse covariance matrix are of significant interest in many modern applications. For the problem of recovering the graphical structure, information criteria provide useful optimization objectives for algorithms searching through sets of graphs or for selection of tuning parameters of other methods such as the graphical lasso, which is a likelihood penalization technique. In this paper we establish the asymptotic consistency of an extended Bayesian information criterion for Gaussian graphical models in a scenario where both the number of variables p and the sample size n grow. Compared to earlier work on the regression case, our treatment allows for growth in the number of non-zero parameters in the true model, which is necessary in order to cover connected graphs. We demonstrate the performance of this criterion on simulated data when used in conjuction with the graphical lasso, and verify that the criterion indeed performs better than either cross-validation or the ordinary Bayesian information criterion when p and the number of non-zero parameters q both scale with n.
Estimating Spatial Layout of Rooms using Volumetric Reasoning about Objects and Surfaces
Authors: Martial Hebert, Takeo Kanade, David M. Blei Abhinav Gupta
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: There has been a recent push in extraction of 3D spatial layout of scenes. However, none of these approaches model the 3D interaction between objects and the spatial layout. In this paper, we argue for a parametric representation of objects in 3D, which allows us to incorporate volumetric constraints of the physical world. We show that augmenting current structured prediction techniques with volumetric reasoning significantly improves the performance of the state-of-the-art.
A Computational Decision Theory for Interactive Assistants
Authors: Prasad Tadepalli Alan Fern
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We study several classes of interactive assistants from the points of view of decision theory and computational complexity. We first introduce a class of POMDPs called hidden-goal MDPs (HGMDPs), which formalize the problem of interactively assisting an agent whose goal is hidden and whose actions are observable. In spite of its restricted nature, we show that optimal action selection in finite horizon HGMDPs is PSPACE-complete even in domains with deterministic dynamics. We then introduce a more restricted model called helper action MDPs (HAMDPs), where the assistant's action is accepted by the agent when it is helpful, and can be easily ignored by the agent otherwise. We show classes of HAMDPs that are complete for PSPACE and NP along with a polynomial time class. Furthermore, we show that for general HAMDPs a simple myopic policy achieves a regret, compared to an omniscient assistant, that is bounded by the entropy of the initial goal distribution. A variation of this policy is shown to achieve worst-case regret that is logarithmic in the number of goals for any goal distribution.
Large Margin Multi-Task Metric Learning
Authors: Kilian Q. Weinberger Shibin Parameswaran
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Multi-task learning (MTL) improves the prediction performance on multiple, different but related, learning problems through shared parameters or representations. One of the most prominent multi-task learning algorithms is an extension to svms by Evgeniou et al. Although very elegant, multi-task svm is inherently restricted by the fact that support vector machines require each class to be addressed explicitly with its own weight vector which, in a multi-task setting, requires the different learning tasks to share the same set of classes. This paper proposes an alternative formulation for multi-task learning by extending the recently published large margin nearest neighbor (lmnn) algorithm to the MTL paradigm. Instead of relying on separating hyperplanes, its decision function is based on the nearest neighbor rule which inherently extends to many classes and becomes a natural fit for multitask learning. We evaluate the resulting multi-task lmnn on real-world insurance data and speech classification problems and show that it consistently outperforms single-task kNN under several metrics and state-of-the-art MTL classifiers.
Evaluating neuronal codes for inference using Fisher information
Authors: Matthias Bethge Haefner Ralf
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Many studies have explored the impact of response variability on the quality of sensory codes. The source of this variability is almost always assumed to be intrinsic to the brain. However, when inferring a particular stimulus property, variability associated with other stimulus attributes also effectively act as noise. Here we study the impact of such stimulus-induced response variability for the case of binocular disparity inference. We characterize the response distribution for the binocular energy model in response to random dot stereograms and find it to be very different from the Poisson-like noise usually assumed. We then compute the Fisher information with respect to binocular disparity, present in the monocular inputs to the standard model of early binocular processing, and thereby obtain an upper bound on how much information a model could theoretically extract from them. Then we analyze the information loss incurred by the different ways of combining those inputs to produce a scalar single-neuron response. We find that in the case of depth inference, monocular stimulus variability places a greater limit on the extractable information than intrinsic neuronal noise for typical spike counts. Furthermore, the largest loss of information is incurred by the standard model for position disparity neurons (tuned-excitatory), that are the most ubiquitous in monkey primary visual cortex, while more information from the inputs is preserved in phase-disparity neurons (tuned-near or tuned-far) primarily found in higher cortical regions.
Guaranteed Rank Minimization via Singular Value Projection
Authors: Raghu Meka, Inderjit S. Dhillon Prateek Jain
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Minimizing the rank of a matrix subject to affine constraints is a fundamental problem with many important applications in machine learning and statistics. In this paper we propose a simple and fast algorithm SVP (Singular Value Projection) for rank minimization under affine constraints ARMP and show that SVP recovers the minimum rank solution for affine constraints that satisfy a Restricted Isometry Property} (RIP). Our method guarantees geometric convergence rate even in the presence of noise and requires strictly weaker assumptions on the RIP constants than the existing methods. We also introduce a Newton-step for our SVP framework to speed-up the convergence with substantial empirical gains. Next, we address a practically important application of ARMP - the problem of low-rank matrix completion, for which the defining affine constraints do not directly obey RIP, hence the guarantees of SVP do not hold. However, we provide partial progress towards a proof of exact recovery for our algorithm by showing a more restricted isometry property and observe empirically that our algorithm recovers low-rank Incoherent matrices from an almost optimal number of uniformly sampled entries. We also demonstrate empirically that our algorithms outperform existing methods, such as those of \cite{CaiCS2008,LeeB2009b, KeshavanOM2009}, for ARMP and the matrix completion problem by an order of magnitude and are also more robust to noise and sampling schemes. In particular, results show that our SVP-Newton method is significantly robust to noise and performs impressively on a more realistic power-law sampling scheme for the matrix completion problem.
Double Q-learning
Authors: Hado V. Hasselt
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: In some stochastic environments the well-known reinforcement learning algorithm Q-learning performs very poorly. This poor performance is caused by large overestimations of action values. These overestimations result from a positive bias that is introduced because Q-learning uses the maximum action value as an approximation for the maximum expected action value. We introduce an alternative way to approximate the maximum expected value for any set of random variables. The obtained double estimator method is shown to sometimes underestimate rather than overestimate the maximum expected value. We apply the double estimator to Q-learning to construct Double Q-learning, a new off-policy reinforcement learning algorithm. We show the new algorithm converges to the optimal policy and that it performs well in some settings in which Q-learning performs poorly due to its overestimation.
Generalized roof duality and bisubmodular functions
Authors: Vladimir Kolmogorov
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Consider a convex relaxation $\hat f$ of a pseudo-boolean function $f$. We say that the relaxation is {\em totally half-integral} if $\hat f(\bx)$ is a polyhedral function with half-integral extreme points $\bx$, and this property is preserved after adding an arbitrary combination of constraints of the form $x_i=x_j$, $x_i=1-x_j$, and $x_i=\gamma$ where $\gamma\in\{0,1,\frac{1}{2}\}$ is a constant. A well-known example is the {\em roof duality} relaxation for quadratic pseudo-boolean functions $f$. We argue that total half-integrality is a natural requirement for generalizations of roof duality to arbitrary pseudo-boolean functions.  Our contributions are as follows. First, we provide a complete characterization of totally half-integral relaxations $\hat f$ by establishing a one-to-one correspondence with {\em bisubmodular functions}. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally half-integral relaxations and relaxations based on the roof duality.
Efficient and Robust Feature Selection via Joint ℓ2,1-Norms Minimization
Authors: Heng Huang, Xiao Cai, Chris H. Ding Feiping Nie
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Feature selection is an important component of many machine learning applications. Especially in many bioinformatics tasks, efficient and robust feature selection methods are desired to extract meaningful features and eliminate noisy ones. In this paper, we propose a new robust feature selection method with emphasizing joint ℓ2,1-norm minimization on both loss function and regularization. The ℓ2,1-norm based loss function is robust to outliers in data points and the ℓ2,1-norm regularization selects features across all data points with joint sparsity. An efficient algorithm is introduced with proved convergence. Our regression based objective makes the feature selection process more efficient. Our method has been applied into both genomic and proteomic biomarkers discovery. Extensive empirical studies were performed on six data sets to demonstrate the effectiveness of our feature selection method.
Repeated Games against Budgeted Adversaries
Authors: Manfred K. Warmuth Jacob D. Abernethy
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We study repeated zero-sum games against an adversary on a budget. Given that an adversary has some constraint on the sequence of actions that he plays, we consider what ought to be the player's best mixed strategy with knowledge of this budget. We show that, for a general class of normal-form games, the minimax strategy is indeed efficiently computable and relies on a random playout" technique. We give three diverse applications of this algorithmic template: a cost-sensitive "Hedge" setting, a particular problem in Metrical Task Systems, and the design of combinatorial prediction markets."
Switching state space model for simultaneously estimating state transitions and nonstationary firing rates
Authors: Masato Okada Ken Takiyama
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We propose an algorithm for simultaneously estimating state transitions among neural states, the number of neural states, and nonstationary firing rates using a switching state space model (SSSM).  This model enables us to detect state transitions based not only on the discontinuous changes of mean firing rates but also on discontinuous changes in temporal profiles of firing rates, e.g., temporal correlation.  We derive a variational Bayes algorithm for a non-Gaussian SSSM whose non-Gaussian property is caused by binary spike events.  Synthetic data analysis reveals the high performance of our algorithm in estimating state transitions, the number of neural states, and nonstationary firing rates compared to previous methods.  We also analyze neural data recorded from the medial temporal area.  The statistically detected neural states probably coincide with transient and sustained states, which have been detected heuristically. Estimated parameters suggest that our algorithm detects the state transition based on discontinuous change in the temporal correlation of firing rates, which transitions previous methods cannot detect.  This result suggests the advantage of our algorithm in real-data analysis.
Why are some word orders more common than others? A uniform information density account
Authors: Dan Navarro, Amy Perfors Luke Maurits
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Languages vary widely in many ways, including their canonical word order. A basic aspect of the observed variation is the fact that some word orders are much more common than others. Although this regularity has been recognized for some time, it has not been well-explained. In this paper we offer an information-theoretic explanation for the observed word-order distribution across languages, based on the concept of Uniform Information Density (UID). We suggest that object-first languages are particularly disfavored because they are highly non-optimal if the goal is to distribute information content approximately evenly throughout a sentence, and that the rest of the observed word-order distribution is at least partially explainable in terms of UID. We support our theoretical analysis with data from child-directed speech and experimental work.
Getting lost in space: Large sample analysis of the resistance distance
Authors: Agnes Radl, Matthias Hein Ulrike V. Luxburg
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: The commute distance between two vertices in a graph is the expected   time it takes a random walk to travel from the first to the second   vertex and back. We study the behavior of the commute distance as the size of the underlying graph   increases. We prove that the commute distance converges to an   expression that does not take into account the structure of the   graph at all and that is completely meaningless as a distance   function on the graph. Consequently, the use of the raw commute   distance for machine learning purposes is strongly discouraged for   large graphs and in high dimensions. As an alternative we introduce   the amplified commute distance that corrects for   the undesired large sample effects.
Multiparty Differential Privacy via Aggregation of Locally Trained Classifiers
Authors: Shantanu Rane, Bhiksha Raj Manas Pathak
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: As increasing amounts of sensitive personal information finds its way into data repositories, it is important to develop analysis mechanisms that can derive aggregate information from these repositories without revealing information about individual data instances. Though the differential privacy model  provides a framework to analyze such mechanisms for databases belonging to a single party, this framework has not yet been considered in a multi-party setting. In this paper, we propose a privacy-preserving protocol for composing a differentially private aggregate classifier  using classifiers trained locally by separate mutually untrusting parties. The protocol allows these parties to interact with an untrusted curator to construct additive shares of a perturbed aggregate classifier. We also present a detailed theoretical analysis containing a proof of differential privacy  of the perturbed aggregate classifier and a bound on the excess risk introduced by the perturbation. We verify the bound with an experimental evaluation on a real dataset.
Convex Multiple-Instance Learning by Estimating Likelihood Ratio
Authors: Cristian Sminchisescu Fuxin Li
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Multiple-Instance learning has been long known as a hard non-convex problem.
 In this work, we propose an approach that recasts it as a convex likelihood ratio
 estimation problem. Firstly, the constraint in multiple-instance learning is reformulated
 into a convex constraint on the likelihood ratio. Then we show that a joint
 estimation of a likelihood ratio function and the likelihood on training instances
 can be learned convexly. Theoretically, we prove a quantitative relationship between
 the risk estimated under the 0-1 classification loss, and under a loss function
 for likelihood ratio estimation. It is shown that our likelihood ratio estimation is
 generally a good surrogate for the 0-1 loss, and separates positive and negative
 instances well. However with the joint estimation it tends to underestimate the
 likelihood of an example to be positive. We propose to use these likelihood ratio
 estimates as features, and learn a linear combination on them to classify the bags.
 Experiments on synthetic and real datasets show the superiority of the approach.
Short-term memory in neuronal networks through dynamical compressed sensing
Authors: Haim Sompolinsky Surya Ganguli
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Recent proposals suggest that large, generic neuronal networks could store memory traces of past input sequences in their instantaneous state. Such a proposal raises important theoretical questions about the duration of these memory traces and their dependence on network size, connectivity and signal statistics. Prior work, in the case of gaussian input sequences and linear neuronal networks, shows that the duration of memory traces in a network cannot exceed the number of neurons (in units of the neuronal time constant), and that no network can out-perform an equivalent feedforward network. However a more ethologically relevant scenario is that of sparse input sequences. In this scenario, we show how linear neural networks can essentially perform compressed sensing (CS) of past inputs, thereby attaining a memory capacity that {\it exceeds} the number of neurons. This enhanced capacity is achieved by a class of ``orthogonal recurrent networks and not by feedforward networks or generic recurrent networks. We exploit techniques from the statistical physics of disordered systems to analytically compute the decay of memory traces in such networks as a function of network size, signal sparsity and integration time. Alternately, viewed purely from the perspective of CS, this work introduces a new ensemble of measurement matrices derived from dynamical systems, and provides a theoretical analysis of their asymptotic performance."