mtybilly/Instruct2DS huggingface dataset:
Gradient and Hamiltonian Dynamics Applied to Learning in Neural Networks
Authors: James W. Howse, Chaouki T. Abdallah, Gregory L. Heileman
Published in: Advances in Neural Information Processing Systems 8  (NIPS 1995) (Main Conference Track), 1995

Abstract: The  process  of machine  learning  can  be  considered  in  two  stages:  model  selection  and parameter estimation.  In this  paper a  technique  is  presented  for constructing dynamical systems with desired qualitative properties.  The  approach  is  based  on the fact  that  an n-dimensional  nonlinear  dynamical  system can be decomposed into one gradient and  (n - 1)  Hamiltonian sys(cid:173) tems.  Thus, the model  selection stage consists of choosing the gradient and  Hamiltonian portions appropriately so that a certain behavior is obtainable.  To estimate the parameters, a stably convergent learning rule  is  presented.  This algorithm has been proven to converge to the desired system trajectory  for  all  initial  conditions  and system inputs.  This technique can be used to  design  neural network models  which  are guaranteed to solve the trajectory  learning problem.
A New Learning Algorithm for Blind Signal Separation
Authors: Shun-ichi Amari, Andrzej Cichocki, Howard Hua Yang
Published in: Advances in Neural Information Processing Systems 8  (NIPS 1995) (Main Conference Track), 1995

Abstract: A new on-line learning algorithm which minimizes a  statistical de(cid:173) pendency among outputs is  derived for  blind separation  of mixed  signals.  The  dependency  is  measured  by  the  average  mutual  in(cid:173) formation  (MI)  of the outputs.  The source signals and the mixing  matrix  are  unknown  except  for  the  number  of  the  sources.  The  Gram-Charlier  expansion  instead  of the  Edgeworth  expansion  is  used  in  evaluating  the  MI.  The  natural gradient  approach is  used  to minimize the MI. A novel activation function is proposed for the  on-line learning algorithm  which  has  an equivariant property and  is easily implemented on a  neural network like model.  The validity  of the new learning algorithm are verified by computer simulations.
Adaptive Back-Propagation in On-Line Learning of Multilayer Networks
Authors: Ansgar H. L. West, David Saad
Published in: Advances in Neural Information Processing Systems 8  (NIPS 1995) (Main Conference Track), 1995

Abstract: An  adaptive back-propagation algorithm is  studied  and compared  with  gradient  descent  (standard  back-propagation)  for  on-line  learning  in  two-layer  neural  networks  with  an  arbitrary  number  of hidden  units.  Within  a  statistical  mechanics  framework ,  both  numerical  studies  and  a  rigorous  analysis show  that  the  adaptive  back-propagation method results in faster  training by breaking the  symmetry between  hidden  units  more efficiently  and by  providing  faster  convergence to optimal generalization than gradient descent.
Neuron-MOS Temporal Winner Search Hardware for Fully-Parallel Data Processing
Authors: Tadashi Shibata, Tsutomu Nakai, Tatsuo Morimoto, Ryu Kaihara, Takeo Yamashita, Tadahiro Ohmi
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.
Learning long-term dependencies is not as difficult with NARX networks
Authors: Tsungnan Lin, Bill G. Horne, Peter Tiño, C. Lee Giles
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.
Investment Learning with Hierarchical PSOMs
Authors: Jörg A. Walter, Helge Ritter
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.
Discriminant Adaptive Nearest Neighbor Classification and Regression
Authors: Trevor Hastie, Robert Tibshirani
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: Andrew G. Barto, James C. Houk
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: Yoshua Bengio, Francois Gingras
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: Alina Beygelzimer, Daniel J. Hsu, John Langford, Tong Zhang
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: Ali Jalali, Sujay Sanghavi, Chao Ruan, Pradeep K. Ravikumar
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: Yung-kyun Noh, Byoung-tak Zhang, Daniel D. Lee
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: Min Yang, Linli Xu, Martha White, Dale Schuurmans, Yao-liang Yu
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: Adrien Wohrer, Ranulfo Romo, Christian K. Machens
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: Andrew Gelfand, Yutian Chen, Laurens Maaten, Max Welling
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: Jiquan Ngiam, Zhenghao Chen, Daniel Chia, Pang W. Koh, Quoc V. Le, Andrew Y. Ng
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: Ronny Luss, Saharon Rosset, Moni Shahar
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: Kun Gai, Guangyun Chen, Chang-shui Zhang
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: Samy Bengio, Jason Weston, David Grangier
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: Yuanqing Lin, Tong Zhang, Shenghuo Zhu, Kai Yu
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: Andrew Goldberg, Ben Recht, Junming Xu, Robert Nowak, Xiaojin Zhu
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: Rina Foygel, Mathias Drton
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: Abhinav Gupta, Martial Hebert, Takeo Kanade, David M. Blei
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: Alan Fern, Prasad Tadepalli
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: Shibin Parameswaran, Kilian Q. Weinberger
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: Haefner Ralf, Matthias Bethge
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: Prateek Jain, Raghu Meka, Inderjit S. Dhillon
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.
Efficient and Robust Feature Selection via Joint ℓ2,1-Norms Minimization
Authors: Feiping Nie, Heng Huang, Xiao Cai, Chris H. Ding
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: Jacob D. Abernethy, Manfred K. Warmuth
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: Ken Takiyama, Masato Okada
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: Luke Maurits, Dan Navarro, Amy Perfors
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: Ulrike V. Luxburg, Agnes Radl, Matthias Hein
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: Manas Pathak, Shantanu Rane, Bhiksha Raj
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: Fuxin Li, Cristian Sminchisescu
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: Surya Ganguli, Haim Sompolinsky
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."
The Multidimensional Wisdom of Crowds
Authors: Peter Welinder, Steve Branson, Pietro Perona, Serge J. Belongie
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Distributing labeling tasks among hundreds or thousands of annotators is an increasingly important method for annotating large datasets. We present a method for estimating the underlying value (e.g. the class) of each image from (noisy) annotations provided by multiple annotators. Our method is based on a model of the image formation and annotation process. Each image has different characteristics that are represented in an abstract Euclidean space. Each annotator is modeled as a multidimensional entity with variables representing competence, expertise and bias. This allows the model to discover and represent groups of annotators that have different sets of skills and knowledge, as well as groups of images that differ qualitatively. We find that our model predicts ground truth labels on both synthetic and real data more accurately than state of the art methods. Experiments also show that our model, starting from a set of binary labels, may discover rich information, such as different "schools of thought" amongst the annotators, and can group together images belonging to separate categories.
Boosting Classifier Cascades
Authors: Nuno Vasconcelos, Mohammad J. Saberian
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: The problem of optimal and automatic design of a detector cascade is considered. A novel mathematical model is introduced for a cascaded detector. This model is analytically tractable, leads to recursive computation, and accounts for both classification and complexity. A boosting algorithm, FCBoost, is proposed for fully automated cascade design. It exploits the new cascade model, minimizes a Lagrangian cost that accounts for both classification risk and complexity. It searches the space of cascade configurations to automatically determine the optimal number of stages and their predictors, and is compatible with bootstrapping of negative examples and cost sensitive learning. Experiments show that the resulting cascades have state-of-the-art performance in various computer vision problems.
Implicitly Constrained Gaussian Process Regression for Monocular Non-Rigid Pose Estimation
Authors: Mathieu Salzmann, Raquel Urtasun
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Estimating 3D pose from monocular images is a highly ambiguous problem. Physical constraints can be exploited to restrict the space of feasible configurations. In this paper we propose an approach to constraining the prediction of a discriminative predictor. We first show that the mean prediction of a Gaussian process implicitly satisfies linear constraints if those constraints are satisfied by the training examples. We then show how, by performing a change of variables, a GP can be forced to satisfy quadratic constraints. As evidenced by the experiments, our method outperforms state-of-the-art approaches on the tasks of rigid and non-rigid pose estimation.
Effects of Synaptic Weight Diffusion on Learning in Decision Making Networks
Authors: Kentaro Katahira, Kazuo Okanoya, Masato Okada
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: When animals repeatedly choose actions from multiple alternatives, they can allocate their choices stochastically depending on past actions and outcomes. It is commonly assumed that this ability is achieved by modifications in synaptic weights related to decision making. Choice behavior has been empirically found to follow Herrnstein’s matching law. Loewenstein & Seung (2006) demonstrated that matching behavior is a steady state of learning in neural networks if the synaptic weights change proportionally to the covariance between reward and neural activities. However, their proof did not take into account the change in entire synaptic distributions. In this study, we show that matching behavior is not necessarily a steady state of the covariance-based learning rule when the synaptic strength is sufficiently strong so that the fluctuations in input from individual sensory neurons influence the net input to output neurons. This is caused by the increasing variance in the input potential due to the diffusion of synaptic weights. This effect causes an undermatching phenomenon, which has been observed in many behavioral experiments. We suggest that the synaptic diffusion effects provide a robust neural mechanism for stochastic choice behavior.
Interval Estimation for Reinforcement-Learning Algorithms in Continuous-State Domains
Authors: Martha White, Adam White
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: The reinforcement learning community has explored many approaches to obtain- ing value estimates and models to guide decision making; these approaches, how- ever, do not usually provide a measure of confidence in the estimate. Accurate estimates of an agent’s confidence are useful for many applications, such as bi- asing exploration and automatically adjusting parameters to reduce dependence on parameter-tuning. Computing confidence intervals on reinforcement learning value estimates, however, is challenging because data generated by the agent- environment interaction rarely satisfies traditional assumptions. Samples of value- estimates are dependent, likely non-normally distributed and often limited, partic- ularly in early learning when confidence estimates are pivotal. In this work, we investigate how to compute robust confidences for value estimates in continuous Markov decision processes. We illustrate how to use bootstrapping to compute confidence intervals online under a changing policy (previously not possible) and prove validity under a few reasonable assumptions. We demonstrate the applica- bility of our confidence estimation algorithms with experiments on exploration, parameter estimation and tracking.