mtybilly/Instruct2DS huggingface dataset:
Large scale networks fingerprinting and visualization using the k-core decomposition
Authors: J. I. Alvarez-hamelin, Luca Dall'asta, Alain Barrat, Alessandro Vespignani
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We use the k-core decomposition to develop algorithms for the analysis of large scale complex networks. This decomposition, based on a re- cursive pruning of the least connected vertices, allows to disentangle the hierarchical structure of networks by progressively focusing on their cen- tral cores. By using this strategy we develop a general visualization algo- rithm that can be used to compare the structural properties of various net- works and highlight their hierarchical structure. The low computational complexity of the algorithm, O(n + e), where n is the size of the net- work, and e is the number of edges, makes it suitable for the visualization of very large sparse networks. We show how the proposed visualization tool allows to ﬁnd speciﬁc structural ﬁngerprints of networks.
Norepinephrine and Neural Interrupts
Authors: Peter Dayan, Angela J. Yu
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Angela J. Yu
Center for Brain, Mind & Behavior Green Hall, Princeton University
Princeton, NJ 08540, USA ajyu@princeton.edu
Experimental data indicate that norepinephrine is critically involved in aspects of vigilance and attention. Previously, we considered the func- tion of this neuromodulatory system on a time scale of minutes and longer, and suggested that it signals global uncertainty arising from gross changes in environmental contingencies. However, norepinephrine is also known to be activated phasically by familiar stimuli in well- learned tasks. Here, we extend our uncertainty-based treatment of nore- pinephrine to this phasic mode, proposing that it is involved in the de- tection and reaction to state uncertainty within a task. This role of nore- pinephrine can be understood through the metaphor of neural interrupts.
Consensus Propagation
Authors: Benjamin V. Roy, Ciamac C. Moallemi
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We propose consensus propagation, an asynchronous distributed protocol for averaging numbers across a network. We establish convergence, characterize the convergence rate for regular graphs, and demonstrate that the protocol exhibits better scaling properties than pairwise averaging, an alternative that has received much recent attention. Consensus propagation can be viewed as a special case of belief propagation, and our results contribute to the belief propagation literature. In particular, beyond singly-connected graphs, there are very few classes of relevant problems for which belief propagation is known to converge.
CMOL CrossNets: Possible Neuromorphic Nanoelectronic Circuits
Authors: Jung Hoon Lee, Xiaolong Ma, Konstantin K. Likharev
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Hybrid  “CMOL”  integrated  circuits,  combining  CMOS  subsystem  with  nanowire  crossbars  and  simple  two-terminal  nanodevices,  promise  to  extend  the  exponential  Moore-Law  development  of  microelectronics  into  the  sub-10-nm  range.  We  are  developing  neuromorphic  network  (“CrossNet”)  architectures  for  this  future  technology, in which neural cell bodies are implemented in CMOS,  nanowires  are  used  as  axons  and  dendrites,  while  nanodevices  (bistable  latching  switches)  are  used  as  elementary  synapses.  We  have  shown  how  CrossNets  may  be  trained  to  perform  pattern  recovery  and  classification  despite  the  limitations  imposed  by  the  CMOL  hardware.    Preliminary  estimates  have  shown  that  CMOL  CrossNets may be extremely dense (~107 cells per cm2) and operate  approximately a million times faster than biological neural networks,  at  manageable  power  consumption.  In  Conclusion,  we  discuss  in  brief possible short-term and long-term applications of the emerging  technology. 
1  Introduction: CMOL Circuits 
Recent  results  [1,  2]  indicate  that  the  current  VLSI  paradigm  based  on  CMOS  technology  can  be  hardly  extended  beyond  the  10-nm  frontier:  in  this  range  the  sensitivity  of  parameters  (most  importantly,  the  gate  voltage  threshold)  of  silicon  field-effect  transistors  to  inevitable  fabrication  spreads  grows  exponentially.  This  sensitivity will probably send the fabrication facilities costs skyrocketing, and may  lead to the end of Moore’s Law some time during the next decade.   There  is  a  growing  consensus  that  the  impending  Moore’s  Law  crisis  may  be  preempted by a radical paradigm shift from the purely CMOS technology to hybrid  CMOS/nanodevice circuits, e.g., those of “CMOL” variety (Fig. 1). Such circuits (see,  e.g., Ref. 3 for their recent review) would combine a level of advanced CMOS devices  fabricated by the lithographic patterning, and two-layer nanowire crossbar formed,  e.g.,  by  nanoimprint,  with  nanowires  connected  by  simple,  similar,  two-terminal  nanodevices at each crosspoint. For such devices, molecular single-electron latching  switches [4] are presently the leading candidates, in particular because they may be  fabricated using the self-assembled monolayer (SAM) technique which already gave  reproducible results for simpler molecular devices [5].
A General and Efficient Multiple Kernel Learning Algorithm
Authors: Sören Sonnenburg, Gunnar Rätsch, Christin Schäfer
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: While classical kernel-based learning algorithms are based on a single kernel, in practice it is often desirable to use multiple kernels. Lankriet et al. (2004) considered conic combinations of kernel matrices for classi- ﬁcation, leading to a convex quadratically constraint quadratic program. We show that it can be rewritten as a semi-inﬁnite linear program that can be efﬁciently solved by recycling the standard SVM implementa- tions. Moreover, we generalize the formulation and our method to a larger class of problems, including regression and one-class classiﬁca- tion. Experimental results show that the proposed algorithm helps for automatic model selection, improving the interpretability of the learn- ing result and works for hundred thousands of examples or hundreds of kernels to be combined.
f (x) = sign N Xi=1
αiyik(xi, x) + b! ,
Stimulus Evoked Independent Factor Analysis of MEG Data with Large Background Activity
Authors: Kenneth Hild, Kensuke Sekihara, Hagai T. Attias, Srikantan S. Nagarajan
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: This paper presents a novel technique for analyzing electromagnetic imaging data obtained using the stimulus evoked experimental paradigm. The technique is based on a probabilistic graphical model, which describes the data in terms of underlying evoked and interference sources, and explicitly models the stimulus evoked paradigm. A variational Bayesian EM algorithm infers the model from data, suppresses interference sources, and reconstructs the activity of separated individual brain sources. The new algorithm outperforms existing techniques on two real datasets, as well as on simulated data.
Laplacian Score for Feature Selection
Authors: Xiaofei He, Deng Cai, Partha Niyogi
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: In supervised learning scenarios, feature selection has been studied widely in the literature. Selecting features in unsupervised learning scenarios is a much harder problem, due to the absence of class labels that would guide the search for relevant information. And, almost all of previous unsupervised feature selection methods are "wrapper" techniques that require a learning algorithm to evaluate the candidate feature subsets. In this paper, we propose a "filter" method for feature selection which is independent of any learning algorithm. Our method can be performed in either supervised or unsupervised fashion. The proposed method is based on the observation that, in many real world classification problems, data from the same class are often close to each other. The importance of a feature is evaluated by its power of locality preserving, or, Laplacian Score. We compare our method with data variance (unsupervised) and Fisher score (supervised) on two data sets. Experimental results demonstrate the effectiveness and efficiency of our algorithm.
Variational Bayesian Stochastic Complexity of Mixture Models
Authors: Kazuho Watanabe, Sumio Watanabe
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: The Variational Bayesian framework has been widely used to approximate the Bayesian learning. In various applications, it has provided computational tractability and good generalization performance. In this paper, we discuss the Variational Bayesian learning of the mixture of exponential families and provide some additional theoretical support by deriving the asymptotic form of the stochastic complexity. The stochastic complexity, which corresponds to the minimum free energy and a lower bound of the marginal likelihood, is a key quantity for model selection. It also enables us to discuss the effect of hyperparameters and the accuracy of the Variational Bayesian approach as an approximation of the true Bayesian learning.
Hierarchical Linear/Constant Time SLAM Using Particle Filters for Dense Maps
Authors: Austin I. Eliazar, Ronald Parr
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We present an improvement to the DP-SLAM algorithm for simultane- ous localization and mapping (SLAM) that maintains multiple hypothe- ses about densely populated maps (one full map per particle in a par- ticle ﬁlter) in time that is linear in all signiﬁcant algorithm parameters and takes constant (amortized) time per iteration. This means that the asymptotic complexity of the algorithm is no greater than that of a pure localization algorithm using a single map and the same number of parti- cles. We also present a hierarchical extension of DP-SLAM that uses a two level particle ﬁlter which models drift in the particle ﬁltering process itself. The hierarchical approach enables recovery from the inevitable drift that results from using a ﬁnite number of particles in a particle ﬁlter and permits the use of DP-SLAM in more challenging domains, while maintaining linear time asymptotic complexity.
An exploration-exploitation model based on norepinepherine and dopamine activity
Authors: Samuel M. McClure, Mark S. Gilzenrat, Jonathan D. Cohen
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We propose a model by which dopamine (DA) and norepinepherine  (NE) combine to alternate behavior between relatively exploratory  and  exploitative  modes.  The  model  is  developed  for  a  target  detection  task  for  which  there  is  extant  single  neuron  recording  data  available  from  locus  coeruleus  (LC)  NE  neurons.  An  exploration-exploitation trade-off is elicited by regularly switching  which  of  the  two  stimuli  are  rewarded.  DA  functions  within  the  model  to  change  synaptic  weights  according  to  a  reinforcement  learning  algorithm.  Exploration  is  mediated  by  the  state  of  LC  firing,  with  higher  tonic  and  lower  phasic  activity  producing  greater  response  variability.  The  opposite  state  of  LC  function,  with lower baseline firing rate and greater phasic responses, favors  exploitative  behavior.  Changes  in  LC  firing  mode  result  from  combined  measures  of  response  conflict  and  reward  rate,  where  response  conflict  is  monitored  using  models  of  anterior  cingulate  cortex (ACC). Increased long-term response conflict and decreased  reward  rate,  which  occurs  following  reward  contingency  switch,  favors  the  higher  tonic  state  of  LC  function  and  NE  release.  This  increases exploration, and facilitates discovery of the new target.
Kernels for gene regulatory regions
Authors: Jean-philippe Vert, Robert Thurman, William S. Noble
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We describe a hierarchy of motif-based kernels for multiple alignments of biological sequences, particularly suitable to process regulatory regions of genes. The kernels incorporate progressively more information, with the most complex kernel accounting for a multiple alignment of orthologous regions, the phylogenetic tree relating the species, and the prior knowledge that relevant sequence patterns occur in conserved motif blocks. These kernels can be used in the presence of a library of known transcription factor binding sites, or de novo by iterating over all k -mers of a given length. In the latter mode, a discriminative classifier built from such a kernel not only recognizes a given class of promoter regions, but as a side effect simultaneously identifies a collection of relevant, discriminative sequence motifs. We demonstrate the utility of the motif-based multiple alignment kernels by using a collection of aligned promoter regions from five yeast species to recognize classes of cell-cycle regulated genes. Supplementary data is available at http://noble.gs.washington.edu/proj/pkernel.
Transfer learning for text classification
Authors: Chuong B. Do, Andrew Y. Ng
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Linear text classiﬁcation algorithms work by computing an inner prod- uct between a test document vector and a parameter vector. In many such algorithms, including naive Bayes and most TFIDF variants, the parame- ters are determined by some simple, closed-form, function of training set statistics; we call this mapping mapping from statistics to parameters, the parameter function. Much research in text classiﬁcation over the last few decades has consisted of manual efforts to identify better parameter func- tions. In this paper, we propose an algorithm for automatically learning this function from related classiﬁcation problems. The parameter func- tion found by our algorithm then deﬁnes a new learning algorithm for text classiﬁcation, which we can apply to novel classiﬁcation tasks. We ﬁnd that our learned classiﬁer outperforms existing methods on a variety of multiclass text classiﬁcation tasks.
arg maxk2f1;:::;KgPn
The Forgetron: A Kernel-Based Perceptron on a Fixed Budget
Authors: Ofer Dekel, Shai Shalev-shwartz, Yoram Singer
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: The Perceptron algorithm, despite its simplicity, often performs well on online classification tasks. The Perceptron becomes especially effective when it is used in conjunction with kernels. However, a common difficulty encountered when implementing kernel-based online algorithms is the amount of memory required to store the online hypothesis, which may grow unboundedly. In this paper we present and analyze the Forgetron algorithm for kernel-based online learning on a fixed memory budget. To our knowledge, this is the first online learning algorithm which, on one hand, maintains a strict limit on the number of examples it stores while, on the other hand, entertains a relative mistake bound. In addition to the formal results, we also present experiments with real datasets which underscore the merits of our approach.
Online Discovery and Learning of Predictive State Representations
Authors: Peter Mccracken, Michael Bowling
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Predictive state representations (PSRs) are a method of modeling dynamical systems using only observable data, such as actions and observations, to describe their model. PSRs use predictions about the outcome of future tests to summarize the system state. The best existing techniques for discovery and learning of PSRs use a Monte Carlo approach to explicitly estimate these outcome probabilities. In this paper, we present a new algorithm for discovery and learning of PSRs that uses a gradient descent approach to compute the predictions for the current state. The algorithm takes advantage of the large amount of structure inherent in a valid prediction matrix to constrain its predictions. Furthermore, the algorithm can be used online by an agent to constantly improve its prediction quality; something that current state of the art discovery and learning algorithms are unable to do. We give empirical results to show that our constrained gradient algorithm is able to discover core tests using very small amounts of data, and with larger amounts of data can compute accurate predictions of the system dynamics.
Hyperparameter and Kernel Learning for Graph Based Semi-Supervised Classification
Authors: Ashish Kapoor, Hyungil Ahn, Yuan Qi, Rosalind W. Picard
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: There have been many graph-based approaches for semi-supervised clas- siﬁcation. One problem is that of hyperparameter learning: performance depends greatly on the hyperparameters of the similarity graph, trans- formation of the graph Laplacian and the noise model. We present a Bayesian framework for learning hyperparameters for graph-based semi- supervised classiﬁcation. Given some labeled data, which can contain inaccurate labels, we pose the semi-supervised classiﬁcation as an in- ference problem over the unknown labels. Expectation Propagation is used for approximate inference and the mean of the posterior is used for classiﬁcation. The hyperparameters are learned using EM for evidence maximization. We also show that the posterior mean can be written in terms of the kernel matrix, providing a Bayesian classiﬁer to classify new points. Tests on synthetic and real datasets show cases where there are signiﬁcant improvements in performance over the existing approaches.
Fusion of Similarity Data in Clustering
Authors: Tilman Lange, Joachim M. Buhmann
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Fusing multiple information sources can yield signiﬁcant beneﬁts to suc- cessfully accomplish learning tasks. Many studies have focussed on fus- ing information in supervised learning contexts. We present an approach to utilize multiple information sources in the form of similarity data for unsupervised learning. Based on similarity information, the clustering task is phrased as a non-negative matrix factorization problem of a mix- ture of similarity measurements. The tradeoff between the informative- ness of data sources and the sparseness of their mixture is controlled by an entropy-based weighting mechanism. For the purpose of model se- lection, a stability-based approach is employed to ensure the selection of the most self-consistent hypothesis. The experiments demonstrate the performance of the method on toy as well as real world data sets.
Sensory Adaptation within a Bayesian Framework for Perception
Authors: Alan Stocker, Eero P. Simoncelli
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We extend a previously developed Bayesian framework for perception to account for sensory adaptation. We ﬁrst note that the perceptual ef- fects of adaptation seems inconsistent with an adjustment of the inter- nally represented prior distribution. Instead, we postulate that adaptation increases the signal-to-noise ratio of the measurements by adapting the operational range of the measurement stage to the input range. We show that this changes the likelihood function in such a way that the Bayesian estimator model can account for reported perceptual behavior. In particu- lar, we compare the model’s predictions to human motion discrimination data and demonstrate that the model accounts for the commonly observed perceptual adaptation effects of repulsion and enhanced discriminability.
Radial Basis Function Network for Multi-task Learning
Authors: Xuejun Liao, Lawrence Carin
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We extend radial basis function (RBF) networks to the scenario in which multiple correlated tasks are learned simultaneously, and present the cor- responding learning algorithms. We develop the algorithms for learn- ing the network structure, in either a supervised or unsupervised manner. Training data may also be actively selected to improve the network’s gen- eralization to test data. Experimental results based on real data demon- strate the advantage of the proposed algorithms and support our conclu- sions.
Gaussian Process Dynamical Models
Authors: Jack Wang, Aaron Hertzmann, David J Fleet
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: This paper introduces Gaussian Process Dynamical Models (GPDM) for nonlinear time series analysis. A GPDM comprises a low-dimensional latent space with associated dynamics, and a map from the latent space to an observation space. We marginalize out the model parameters in closed-form, using Gaussian Process (GP) priors for both the dynamics and the observation mappings. This results in a nonparametric model for dynamical systems that accounts for uncertainty in the model. We demonstrate the approach on human motion capture data in which each pose is 62-dimensional. Despite the use of small data sets, the GPDM learns an effective representation of the nonlinear dynamics in these spaces. Webpage: http://www.dgp.toronto.edu/
Rodeo: Sparse Nonparametric Regression in High Dimensions
Authors: Larry Wasserman, John D. Lafferty
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We present a method for nonparametric regression that performs bandwidth selection and variable selection simultaneously. The approach is based on the technique of incrementally decreasing the bandwidth in directions where the gradient of the estimator with respect to bandwidth is large. When the unknown function satisfies a sparsity condition, our approach avoids the curse of dimensionality, achieving the optimal minimax rate of convergence, up to logarithmic factors, as if the relevant variables were known in advance. The method--called rodeo (regularization of derivative expectation operator)--conducts a sequence of hypothesis tests, and is easy to implement. A modified version that replaces hard with soft thresholding effectively solves a sequence of lasso problems.
Pattern Recognition from One Example by Chopping
Authors: Francois Fleuret, Gilles Blanchard
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We investigate the learning of the appearance of an object from a single image of it. Instead of using a large number of pictures of the object to recognize, we use a labeled reference database of pictures of other ob- jects to learn invariance to noise and variations in pose and illumination. This acquired knowledge is then used to predict if two pictures of new objects, which do not appear on the training pictures, actually display the same object. We propose a generic scheme called chopping to address this task. It relies on hundreds of random binary splits of the training set chosen to keep together the images of any given object. Those splits are extended to the complete image space with a simple learning algorithm. Given two images, the responses of the split predictors are combined with a Bayesian rule into a posterior probability of similarity. Experiments with the COIL-100 database and with a database of 150 de- graded LATEX symbols compare our method to a classical learning with several examples of the positive class and to a direct learning of the sim- ilarity.
Hot Coupling: A Particle Approach to Inference and Normalization on Pairwise Undirected Graphs
Authors: Firas Hamze, Nando de Freitas
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: This paper presents a new sampling algorithm for approximating func- tions of variables representable as undirected graphical models of arbi- trary connectivity with pairwise potentials, as well as for estimating the notoriously dif(cid:2)cult partition function of the graph. The algorithm (cid:2)ts into the framework of sequential Monte Carlo methods rather than the more widely used MCMC, and relies on constructing a sequence of in- termediate distributions which get closer to the desired one. While the idea of using (cid:147)tempered(cid:148) proposals is known, we construct a novel se- quence of target distributions where, rather than dropping a global tem- perature parameter, we sequentially couple individual pairs of variables that are, initially, sampled exactly from a spanning tree of the variables. We present experimental results on inference and estimation of the parti- tion function for sparse and densely-connected graphs.
Separation of Music Signals by Harmonic Structure Modeling
Authors: Yun-gang Zhang, Chang-shui Zhang
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Separation of music signals is an interesting but difficult problem. It is helpful for many other music researches such as audio content analysis. In this paper, a new music signal separation method is proposed, which is based on harmonic structure modeling. The main idea of harmonic structure modeling is that the harmonic structure of a music signal is stable, so a music signal can be represented by a harmonic structure model. Accordingly, a corresponding separation algorithm is proposed. The main idea is to learn a harmonic structure model for each music signal in the mixture, and then separate signals by using these models to distinguish harmonic structures of different signals. Experimental results show that the algorithm can separate signals and obtain not only a very high Signalto-Noise Ratio (SNR) but also a rather good subjective audio quality.
Learning Minimum Volume Sets
Authors: Clayton Scott, Robert Nowak
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Given a probability measure P and a reference measure µ, one is often interested in the minimum µ-measure set with P -measure at least α. Minimum volume sets of this type summarize the regions of greatest probability mass of P , and are useful for detecting anoma- lies and constructing conﬁdence regions. This paper addresses the problem of estimating minimum volume sets based on independent samples distributed according to P . Other than these samples, no other information is available regarding P , but the reference mea- sure µ is assumed to be known. We introduce rules for estimating minimum volume sets that parallel the empirical risk minimization and structural risk minimization principles in classiﬁcation. As in classiﬁcation, we show that the performances of our estimators are controlled by the rate of uniform convergence of empirical to true probabilities over the class from which the estimator is drawn. Thus we obtain ﬁnite sample size performance bounds in terms of VC dimension and related quantities. We also demonstrate strong universal consistency and an oracle inequality. Estimators based on histograms and dyadic partitions illustrate the proposed rules.
Spectral Bounds for Sparse PCA: Exact and Greedy Algorithms
Authors: Baback Moghaddam, Yair Weiss, Shai Avidan
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Sparse PCA seeks approximate sparse "eigenvectors" whose projections capture the maximal variance of data. As a cardinality-constrained and non-convex optimization problem, it is NP-hard and is encountered in a wide range of applied fields, from bio-informatics to finance. Recent progress has focused mainly on continuous approximation and convex relaxation of the hard cardinality constraint. In contrast, we consider an alternative discrete spectral formulation based on variational eigenvalue bounds and provide an effective greedy strategy as well as provably optimal solutions using branch-and-bound search. Moreover, the exact methodology used reveals a simple renormalization step that improves approximate solutions obtained by any continuous method. The resulting performance gain of discrete algorithms is demonstrated on real-world benchmark data and in extensive Monte Carlo evaluation trials.
A Domain Decomposition Method for Fast Manifold Learning
Authors: Zhenyue Zhang, Hongyuan Zha
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We propose a fast manifold learning algorithm based on the methodology of domain decomposition. Starting with the set of sample points partitioned into two subdomains, we develop the solution of the interface problem that can glue the embeddings on the two subdomains into an embedding on the whole domain. We provide a detailed analysis to assess the errors produced by the gluing process using matrix perturbation theory. Numerical examples are given to illustrate the efficiency and effectiveness of the proposed methods.
Generalized Nonnegative Matrix Approximations with Bregman Divergences
Authors: Suvrit Sra, Inderjit S. Dhillon
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Nonnegative matrix approximation (NNMA) is a recent technique for dimensionality reduction and data analysis that yields a parts based, sparse nonnegative representation for nonnegative input data. NNMA has found a wide variety of applications, including text analysis, document clustering, face/image recognition, language modeling, speech processing and many others. Despite these numerous applications, the algorithmic development for computing the NNMA factors has been relatively deficient. This paper makes algorithmic progress by modeling and solving (using multiplicative updates) new generalized NNMA problems that minimize Bregman divergences between the input matrix and its lowrank approximation. The multiplicative update formulae in the pioneering work by Lee and Seung [11] arise as a special case of our algorithms. In addition, the paper shows how to use penalty functions for incorporating constraints other than nonnegativity into the problem. Further, some interesting extensions to the use of "link" functions for modeling nonlinear relationships are also discussed.
Predicting EMG Data from M1 Neurons with Variational Bayesian Least Squares
Authors: Jo-anne Ting, Aaron D'souza, Kenji Yamamoto, Toshinori Yoshioka, Donna Hoffman, Shinji Kakei, Lauren Sergio, John Kalaska, Mitsuo Kawato
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: An increasing number of projects in neuroscience requires the sta- tistical analysis of high dimensional data sets, as, for instance, in predicting behavior from neural ﬁring or in operating artiﬁcial de- vices from brain recordings in brain-machine interfaces. Linear analysis techniques remain prevalent in such cases, but classical linear regression approaches are often numerically too fragile in high dimensions. In this paper, we address the question of whether EMG data collected from arm movements of monkeys can be faith- fully reconstructed with linear approaches from neural activity in primary motor cortex (M1). To achieve robust data analysis, we develop a full Bayesian approach to linear regression that auto- matically detects and excludes irrelevant features in the data, reg- ularizing against overﬁtting. In comparison with ordinary least squares, stepwise regression, partial least squares, LASSO regres- sion and a brute force combinatorial search for the most predictive input features in the data, we demonstrate that the new Bayesian method oﬀers a superior mixture of characteristics in terms of reg- ularization against overﬁtting, computational eﬃciency and ease of use, demonstrating its potential as a drop-in replacement for other linear regression techniques. As neuroscientiﬁc results, our anal- yses demonstrate that EMG data can be well predicted from M1 neurons, further opening the path for possible real-time interfaces between brains and machines.
Comparing the Effects of Different Weight Distributions on Finding Sparse Representations
Authors: Bhaskar D. Rao, David P. Wipf
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Given a redundant dictionary of basis vectors (or atoms), our goal is to ﬁnd maximally sparse representations of signals. Previously, we have argued that a sparse Bayesian learning (SBL) framework is particularly well-suited for this task, showing that it has far fewer local minima than other Bayesian-inspired strategies. In this paper, we provide further evi- dence for this claim by proving a restricted equivalence condition, based on the distribution of the nonzero generating model weights, whereby the SBL solution will equal the maximally sparse representation. We also prove that if these nonzero weights are drawn from an approximate Jef- freys prior, then with probability approaching one, our equivalence con- dition is satisﬁed. Finally, we motivate the worst-case scenario for SBL and demonstrate that it is still better than the most widely used sparse rep- resentation algorithms. These include Basis Pursuit (BP), which is based on a convex relaxation of the ℓ0 (quasi)-norm, and Orthogonal Match- ing Pursuit (OMP), a simple greedy strategy that iteratively selects basis vectors most aligned with the current residual.
Goal-Based Imitation as Probabilistic Inference over Graphical Models
Authors: Deepak Verma, Rajesh P. Rao
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Humans are extremely adept at learning new skills by imitating the actions of others. A progression of imitative abilities has been observed in children, ranging from imitation of simple body movements to goalbased imitation based on inferring intent. In this paper, we show that the problem of goal-based imitation can be formulated as one of inferring goals and selecting actions using a learned probabilistic graphical model of the environment. We first describe algorithms for planning actions to achieve a goal state using probabilistic inference. We then describe how planning can be used to bootstrap the learning of goal-dependent policies by utilizing feedback from the environment. The resulting graphical model is then shown to be powerful enough to allow goal-based imitation. Using a simple maze navigation task, we illustrate how an agent can infer the goals of an observed teacher and imitate the teacher even when the goals are uncertain and the demonstration is incomplete.
Message passing for task redistribution on sparse graphs
Authors: K. Y. Michael Wong, David Saad, Zhuo Gao
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: The problem of resource allocation in sparse graphs with real variables is studied using methods of statistical physics. An efﬁcient distributed algorithm is devised on the basis of insight gained from the analysis and is examined using numerical simulations, showing excellent performance and full agreement with the theoretical results.
Neuronal Fiber Delineation in Area of Edema from Diffusion Weighted MRI
Authors: Ofer Pasternak, Nathan Intrator, Nir Sochen, Yaniv Assaf
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Diffusion Tensor Magnetic Resonance Imaging (DT-MRI) is a non inva- sive method for brain neuronal ﬁbers delineation. Here we show a mod- iﬁcation for DT-MRI that allows delineation of neuronal ﬁbers which are inﬁltrated by edema. We use the Muliple Tensor Variational (MTV) framework which replaces the diffusion model of DT-MRI with a mul- tiple component model and ﬁts it to the signal attenuation with a vari- ational regularization mechanism. In order to reduce free water con- tamination we estimate the free water compartment volume fraction in each voxel, remove it, and then calculate the anisotropy of the remaining compartment. The variational framework was applied on data collected with conventional clinical parameters, containing only six diffusion di- rections. By using the variational framework we were able to overcome the highly ill posed ﬁtting. The results show that we were able to ﬁnd ﬁbers that were not found by DT-MRI.
A Computational Model of Eye Movements during Object Class Detection
Authors: Wei Zhang, Hyejin Yang, Dimitris Samaras, Gregory J. Zelinsky
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We present a computational model of human eye movements in an ob- ject class detection task. The model combines state-of-the-art computer vision object class detection methods (SIFT features trained using Ad- aBoost) with a biologically plausible model of human eye movement to produce a sequence of simulated ﬁxations, culminating with the acqui- sition of a target. We validated the model by comparing its behavior to the behavior of human observers performing the identical object class detection task (looking for a teddy bear among visually complex non- target objects). We found considerable agreement between the model and human data in multiple eye movement measures, including number of ﬁxations, cumulative probability of ﬁxating the target, and scanpath distance.
Efficient Unsupervised Learning for Localization and Detection in Object Categories
Authors: Nicolas Loeff, Himanshu Arora, Alexander Sorokin, David Forsyth
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We describe a novel method for learning templates for recognition and localization of objects drawn from categories. A generative model repre- sents the conﬁguration of multiple object parts with respect to an object coordinate system; these parts in turn generate image features. The com- plexity of the model in the number of features is low, meaning our model is much more efﬁcient to train than comparative methods. Moreover, a variational approximation is introduced that allows learning to be or- ders of magnitude faster than previous approaches while incorporating many more features. This results in both accuracy and localization im- provements. Our model has been carefully tested on standard datasets; we compare with a number of recent template models. In particular, we demonstrate state-of-the-art results for detection and localization.
Beyond Gaussian Processes: On the Distributions of Infinite Networks
Authors: Ricky Der, Daniel D. Lee
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: A general analysis of the limiting distribution of neural network functions is performed, with emphasis on non-Gaussian limits. We show that with i.i.d. symmetric stable output weights, and more generally with weights distributed from the normal domain of attraction of a stable variable, that the neural functions converge in distribution to stable processes. Conditions are also investigated under which Gaussian limits do occur when the weights are independent but not identically distributed. Some particularly tractable classes of stable distributions are examined, and the possibility of learning with such processes.
Preconditioner Approximations for Probabilistic Graphical Models
Authors: John D. Lafferty, Pradeep K. Ravikumar
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We present a family of approximation techniques for probabilistic graphical models, based on the use of graphical preconditioners developed in the scientific computing literature. Our framework yields rigorous upper and lower bounds on event probabilities and the log partition function of undirected graphical models, using non-iterative procedures that have low time complexity. As in mean field approaches, the approximations are built upon tractable subgraphs; however, we recast the problem of optimizing the tractable distribution parameters and approximate inference in terms of the well-studied linear systems problem of obtaining a good matrix preconditioner. Experiments are presented that compare the new approximation schemes to variational methods.
Structured Prediction via the Extragradient Method
Authors: Ben Taskar, Simon Lacoste-Julien, Michael I. Jordan
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We present a simple and scalable algorithm for large-margin estima- tion of structured models, including an important class of Markov net- works and combinatorial models. We formulate the estimation problem as a convex-concave saddle-point problem and apply the extragradient method, yielding an algorithm with linear convergence using simple gra- dient and projection calculations. The projection step can be solved us- ing combinatorial algorithms for min-cost quadratic ﬂow. This makes the approach an efﬁcient alternative to formulations based on reductions to a quadratic program (QP). We present experiments on two very different structured prediction tasks: 3D image segmentation and word alignment, illustrating the favorable scaling properties of our algorithm.
Noise and the two-thirds power Law
Authors: Uri Maoz, Elon Portugaly, Tamar Flash, Yair Weiss
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: The two-thirds power law, an empirical law stating an inverse non-linear relationship between the tangential hand speed and the curvature of its trajectory during curved motion, is widely acknowledged to be an invariant of upper-limb movement. It has also been shown to exist in eyemotion, locomotion and was even demonstrated in motion perception and prediction. This ubiquity has fostered various attempts to uncover the origins of this empirical relationship. In these it was generally attributed either to smoothness in hand- or joint-space or to the result of mechanisms that damp noise inherent in the motor system to produce the smooth trajectories evident in healthy human motion. We show here that white Gaussian noise also obeys this power-law. Analysis of signal and noise combinations shows that trajectories that were synthetically created not to comply with the power-law are transformed to power-law compliant ones after combination with low levels of noise. Furthermore, there exist colored noise types that drive non-power-law trajectories to power-law compliance and are not affected by smoothing. These results suggest caution when running experiments aimed at verifying the power-law or assuming its underlying existence without proper analysis of the noise. Our results could also suggest that the power-law might be derived not from smoothness or smoothness-inducing mechanisms operating on the noise inherent in our motor system but rather from the correlated noise which is inherent in this motor system.
From Lasso regression to Feature vector machine
Authors: Fan Li, Yiming Yang, Eric P. Xing
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Lasso regression tends to assign zero weights to most irrelevant or redundant features, and hence is a promising technique for feature selection. Its limitation, however, is that it only offers solutions to linear models. Kernel machines with feature scaling techniques have been studied for feature selection with non-linear models. However, such approaches require to solve hard non-convex optimization problems. This paper proposes a new approach named the Feature Vector Machine (FVM). It reformulates the standard Lasso regression into a form isomorphic to SVM, and this form can be easily extended for feature selection with non-linear models by introducing kernels defined on feature vectors. FVM generates sparse solutions in the nonlinear feature space and it is much more tractable compared to feature scaling kernel machines. Our experiments with FVM on simulated data show encouraging results in identifying the small number of dominating features that are non-linearly correlated to the response, a task the standard Lasso fails to complete.
Maximum Margin Semi-Supervised Learning for Structured Variables
Authors: Y. Altun, D. McAllester, M. Belkin
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Many real-world classiﬁcation problems involve the prediction of multiple inter-dependent variables forming some structural depen- dency. Recent progress in machine learning has mainly focused on supervised classiﬁcation of such structured variables. In this paper, we investigate structured classiﬁcation in a semi-supervised setting. We present a discriminative approach that utilizes the intrinsic ge- ometry of input patterns revealed by unlabeled data points and we derive a maximum-margin formulation of semi-supervised learning for structured variables. Unlike transductive algorithms, our for- mulation naturally extends to new test points.
Generalization in Clustering with Unobserved Features
Authors: Eyal Krupka, Naftali Tishby
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We argue that when objects are characterized by many attributes, clustering them on the basis of a relatively small random subset of these attributes can capture information on the unobserved attributes as well. Moreover, we show that under mild technical conditions, clustering the objects on the basis of such a random subset performs almost as well as clustering with the full attribute set. We prove a finite sample generalization theorems for this novel learning scheme that extends analogous results from the supervised learning setting. The scheme is demonstrated for collaborative filtering of users with movies rating as attributes.
Variable KD-Tree Algorithms for Spatial Pattern Search and Discovery
Authors: Jeremy Kubica, Joseph Masiero, Robert Jedicke, Andrew Connolly, Andrew W. Moore
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: In this paper we consider the problem of finding sets of points that conform to a given underlying model from within a dense, noisy set of observations. This problem is motivated by the task of efficiently linking faint asteroid detections, but is applicable to a range of spatial queries. We survey current tree-based approaches, showing a trade-off exists between single tree and multiple tree algorithms. To this end, we present a new type of multiple tree algorithm that uses a variable number of trees to exploit the advantages of both approaches. We empirically show that this algorithm performs well using both simulated and astronomical data.