mtybilly/Instruct2DS huggingface dataset:
Modeling Neuronal Interactivity using Dynamic Bayesian Networks
Authors: Dimitris Samaras, Nelly Alia-klein, Nora Volkow, Rita Goldstein Lei Zhang
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Functional Magnetic Resonance Imaging (fMRI) has enabled scientists to look into the active brain. However, interactivity between functional brain regions, is still little studied. In this paper, we contribute a novel framework for modeling the interactions between multiple active brain regions, using Dynamic Bayesian Networks (DBNs) as generative mod- els for brain activation patterns. This framework is applied to modeling of neuronal circuits associated with reward. The novelty of our frame- work from a Machine Learning perspective lies in the use of DBNs to reveal the brain connectivity and interactivity. Such interactivity mod- els which are derived from fMRI data are then validated through a group classiﬁcation task. We employ and compare four different types of DBNs: Parallel Hidden Markov Models, Coupled Hidden Markov Models, Fully-linked Hidden Markov Models and Dynamically Multi- Linked HMMs (DML-HMM). Moreover, we propose and compare two schemes of learning DML-HMMs. Experimental results show that by using DBNs, group classiﬁcation can be performed even if the DBNs are constructed from as few as 5 brain regions. We also demonstrate that, by using the proposed learning algorithms, different DBN structures charac- terize drug addicted subjects vs. control subjects. This ﬁnding provides an independent test for the effect of psychopathology on brain function. In general, we demonstrate that incorporation of computer science prin- ciples into functional neuroimaging clinical studies provides a novel ap- proach for probing human brain function.
A Theoretical Analysis of Robust Coding over Noisy Overcomplete Channels
Authors: Doru C. Balcan, Michael S. Lewicki Eizaburo Doi
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Biological sensory systems are faced with the problem of encoding a high-fidelity sensory signal with a population of noisy, low-fidelity neurons. This problem can be expressed in information theoretic terms as coding and transmitting a multi-dimensional, analog signal over a set of noisy channels. Previously, we have shown that robust, overcomplete codes can be learned by minimizing the reconstruction error with a constraint on the channel capacity. Here, we present a theoretical analysis that characterizes the optimal linear coder and decoder for one- and twodimensional data. The analysis allows for an arbitrary number of coding units, thus including both under- and over-complete representations, and provides a number of important insights into optimal coding strategies. In particular, we show how the form of the code adapts to the number of coding units and to different data and noise conditions to achieve robustness. We also report numerical solutions for robust coding of highdimensional image data and show that these codes are substantially more robust compared against other image codes such as ICA and wavelets.
A Probabilistic Approach for Optimizing Spectral Clustering
Authors: Feng Kang, Chris H. Ding Rong Jin
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Spectral clustering enjoys its success in both data clustering and semisupervised learning. But, most spectral clustering algorithms cannot handle multi-class clustering problems directly. Additional strategies are needed to extend spectral clustering algorithms to multi-class clustering problems. Furthermore, most spectral clustering algorithms employ hard cluster membership, which is likely to be trapped by the local optimum. In this paper, we present a new spectral clustering algorithm, named "Soft Cut". It improves the normalized cut algorithm by introducing soft membership, and can be efficiently computed using a bound optimization algorithm. Our experiments with a variety of datasets have shown the promising performance of the proposed clustering algorithm.
Learning Multiple Related Tasks using Latent Independent Component Analysis
Authors: Zoubin Ghahramani, Yiming Yang Jian Zhang
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We propose a probabilistic model based on Independent Component Analysis for learning multiple related tasks. In our model the task parameters are assumed to be generated from independent sources which account for the relatedness of the tasks. We use Laplace distributions to model hidden sources which makes it possible to identify the hidden, independent components instead of just modeling correlations. Furthermore, our model enjoys a sparsity property which makes it both parsimonious and robust. We also propose efficient algorithms for both empirical Bayes method and point estimation. Our experimental results on two multi-label text classification data sets show that the proposed approach is promising.
Context as Filtering
Authors: Yuji Matsumoto Daichi Mochihashi
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Long-distance language modeling is important not only in speech recognition and machine translation, but also in high-dimensional discrete sequence modeling in general. However, the problem of context length has almost been neglected so far and a nave bag-of-words history has been i employed in natural language processing. In contrast, in this paper we view topic shifts within a text as a latent stochastic process to give an explicit probabilistic generative model that has partial exchangeability. We propose an online inference algorithm using particle filters to recognize topic shifts to employ the most appropriate length of context automatically. Experiments on the BNC corpus showed consistent improvement over previous methods involving no chronological order.
A matching pursuit approach to sparse Gaussian process regression
Authors: Wei Chu Sathiya Keerthi
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: In this paper we propose a new basis selection criterion for building sparse GP regression models that provides promising gains in accuracy as well as efficiency over previous methods. Our algorithm is much faster than that of Smola and Bartlett, while, in generalization it greatly outperforms the information gain approach proposed by Seeger et al, especially on the quality of predictive distributions.
Phase Synchrony Rate for the Recognition of Motor Imagery in Brain-Computer Interface
Authors: Evian Gordon, Elly Gysels Le Song
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Motor imagery attenuates EEG  and  rhythms over sensorimotor cortices. These amplitude changes are most successfully captured by the method of Common Spatial Patterns (CSP) and widely used in braincomputer interfaces (BCI). BCI methods based on amplitude information, however, have not incoporated the rich phase dynamics in the EEG rhythm. This study reports on a BCI method based on phase synchrony rate (SR). SR, computed from binarized phase locking value, describes the number of discrete synchronization events within a window. Statistical nonparametric tests show that SRs contain significant differences between 2 types of motor imageries. Classifiers trained on SRs consistently demonstrate satisfactory results for all 5 subjects. It is further observed that, for 3 subjects, phase is more discriminative than amplitude in the first 1.5-2.0 s, which suggests that phase has the potential to boost the information transfer rate in BCIs.
Inference with Minimal Communication: a Decision-Theoretic Variational Approach
Authors: Alan S. Willsky O. P. Kreidl
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Given a directed graphical model with binary-valued hidden nodes and real-valued noisy observations, consider deciding upon the maximum a-posteriori (MAP) or the maximum posterior-marginal (MPM) assignment under the restriction that each node broadcasts only to its children exactly one single-bit message. We present a variational formulation, viewing the processing rules local to all nodes as degrees-of-freedom, that minimizes the loss in expected (MAP or MPM) performance subject to such online communication constraints. The approach leads to a novel message-passing algorithm to be executed offline, or before observations are realized, which mitigates the performance loss by iteratively coupling all rules in a manner implicitly driven by global statistics. We also provide (i) illustrative examples, (ii) assumptions that guarantee convergence and efficiency and (iii) connections to active research areas.
Variational EM Algorithms for Non-Gaussian Latent Variable Models
Authors: Kenneth Kreutz-Delgado, Bhaskar D. Rao, David P. Wipf Jason Palmer
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We consider criteria for variational representations of non-Gaussian latent variables, and derive variational EM algorithms in general form. We establish a general equivalence among convex bounding methods, evidence based methods, and ensemble learning/Variational Bayes methods, which has previously been demonstrated only for particular cases.
Fast Information Value for Graphical Models
Authors: Andrew W. Moore Brigham S. Anderson
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Calculations that quantify the dependencies between variables are vital to many operations with graphical models, e.g., active learning and sen- sitivity analysis. Previously, pairwise information gain calculation has involved a cost quadratic in network size. In this work, we show how to perform a similar computation with cost linear in network size. The loss function that allows this is of a form amenable to computation by dynamic programming. The message-passing algorithm that results is described and empirical results demonstrate large speedups without de- crease in accuracy. In the cost-sensitive domains examined, superior ac- curacy is achieved.
Value Function Approximation with Diffusion Wavelets and Laplacian Eigenfunctions
Authors: Mauro Maggioni Sridhar Mahadevan
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We investigate the problem of automatically constructing efﬁcient rep- resentations or basis functions for approximating value functions based on analyzing the structure and topology of the state space. In particu- lar, two novel approaches to value function approximation are explored based on automatically constructing basis functions on state spaces that can be represented as graphs or manifolds: one approach uses the eigen- functions of the Laplacian, in effect performing a global Fourier analysis on the graph; the second approach is based on diffusion wavelets, which generalize classical wavelets to graphs using multiscale dilations induced by powers of a diffusion operator or random walk on the graph. Together, these approaches form the foundation of a new generation of methods for solving large Markov decision processes, in which the underlying repre- sentation and policies are simultaneously learned.
A Bayesian Spatial Scan Statistic
Authors: Andrew W. Moore, Gregory F. Cooper Daniel B. Neill
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We propose a new Bayesian method for spatial cluster detection, the “Bayesian spatial scan statistic,” and compare this method to the standard (frequentist) scan statistic approach. We demonstrate that the Bayesian statistic has several advantages over the frequentist approach, including increased power to detect clusters and (since randomization testing is unnecessary) much faster runtime. We evaluate the Bayesian and fre- quentist methods on the task of prospective disease surveillance: detect- ing spatial clusters of disease cases resulting from emerging disease out- breaks. We demonstrate that our Bayesian methods are successful in rapidly detecting outbreaks while keeping number of false positives low.
Diffusion Maps, Spectral Clustering and Eigenfunctions of Fokker-Planck Operators
Authors: Stephane Lafon, Ioannis Kevrekidis, Ronald R. Coifman Boaz Nadler
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: This paper presents a diffusion based probabilistic interpretation of spectral clustering and dimensionality reduction algorithms that use the eigenvectors of the normalized graph Laplacian. Given the pairwise adjacency matrix of all points, we define a diffusion distance between any two data points and show that the low dimensional representation of the data by the first few eigenvectors of the corresponding Markov matrix is optimal under a certain mean squared error criterion. Furthermore, assuming that data points are random samples from a density p(x) = e-U (x) we identify these eigenvectors as discrete approximations of eigenfunctions of a Fokker-Planck operator in a potential 2U (x) with reflecting boundary conditions. Finally, applying known results regarding the eigenvalues and eigenfunctions of the continuous Fokker-Planck operator, we provide a mathematical justification for the success of spectral clustering and dimensional reduction algorithms based on these first few eigenvectors. This analysis elucidates, in terms of the characteristics of diffusion processes, many empirical findings regarding spectral clustering algorithms. Keywords: Algorithms and architectures, learning theory.
Scaling Laws in Natural Scenes and the Inference of 3D Shape
Authors: Brian R. Potetz Tai-sing Lee
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: This paper explores the statistical relationship between natural images and their underlying range (depth) images. We look at how this relationship changes over scale, and how this information can be used to enhance low resolution range data using a full resolution intensity image. Based on our findings, we propose an extension to an existing technique known as shape recipes [3], and the success of the two methods are compared using images and laser scans of real scenes. Our extension is shown to provide a two-fold improvement over the current method. Furthermore, we demonstrate that ideal linear shape-from-shading filters, when learned from natural scenes, may derive even more strength from shadow cues than from the traditional linear-Lambertian shading cues.
On the Convergence of Eigenspaces in Kernel Principal Component Analysis
Authors: Gilles Blanchard Laurent Zwald
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: This paper presents a non-asymptotic statistical analysis of Kernel-PCA with a focus different from the one proposed in previous work on this topic. Here instead of considering the reconstruction error of KPCA we are interested in approximation error bounds for the eigenspaces themselves. We prove an upper bound depending on the spacing between eigenvalues but not on the dimensionality of the eigenspace. As a consequence this allows to infer stability results for these estimated spaces.
Layered Dynamic Textures
Authors: Nuno Vasconcelos Antoni B. Chan
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: A dynamic texture is a video model that treats a video as a sample from a spatio-temporal stochastic process, speciﬁcally a linear dynamical sys- tem. One problem associated with the dynamic texture is that it cannot model video where there are multiple regions of distinct motion. In this work, we introduce the layered dynamic texture model, which addresses this problem. We also introduce a variant of the model, and present the EM algorithm for learning each of the models. Finally, we demonstrate the efﬁcacy of the proposed model for the tasks of segmentation and syn- thesis of video.
Subsequence Kernels for Relation Extraction
Authors: Razvan C. Bunescu Raymond J. Mooney
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We present a new kernel method for extracting semantic relations between entities in natural language text, based on a generalization of subsequence kernels. This kernel uses three types of subsequence patterns that are typically employed in natural language to assert relationships between two entities. Experiments on extracting protein interactions from biomedical corpora and top-level relations from newspaper corpora demonstrate the advantages of this approach.
Optimal cue selection strategy
Authors: Laurent Itti Vidhya Navalpakkam
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Survival in the natural world demands the selection of relevant visual cues to rapidly and reliably guide attention towards prey an d predators in cluttered environments. We investigate whether our visu al system selects cues that guide search in an optimal manner. We formall y obtain the optimal cue selection strategy by maximizing the signal to noise ratio (S N R) between a search target and surrounding distractors. This optimal strategy successfully accounts for several phenom ena in visual search behavior, including the effect of target-distracto r discriminability, uncertainty in target's features, distractor heterogenei ty, and linear separability. Furthermore, the theory generates a new predict ion, which we verify through psychophysical experiments with human subj ects. Our results provide direct experimental evidence that humans sel ect visual cues so as to maximize S N R between the targets and surrounding clutter.
Infinite latent feature models and the Indian buffet process
Authors: Thomas L. Griffiths Zoubin Ghahramani
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We define a probability distribution over equivalence classes of binary matrices with a finite number of rows and an unbounded number of columns. This distribution is suitable for use as a prior in probabilistic models that represent objects using a potentially infinite array of features. We identify a simple generative process that results in the same distribution over equivalence classes, which we call the Indian buffet process. We illustrate the use of this distribution as a prior in an infinite latent feature model, deriving a Markov chain Monte Carlo algorithm for inference in this model and applying the algorithm to an image dataset.
Non-Gaussian Component Analysis: a Semi-parametric Framework for Linear Dimension Reduction
Authors: Masashi Sugiyama, Motoaki Kawanabe, Vladimir Spokoiny, Klaus-Robert Müller Gilles Blanchard
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We propose a new linear method for dimension reduction to identify nonGaussian components in high dimensional data. Our method, NGCA (non-Gaussian component analysis), uses a very general semi-parametric framework. In contrast to existing projection methods we define what is uninteresting (Gaussian): by projecting out uninterestingness, we can estimate the relevant non-Gaussian subspace. We show that the estimation error of finding the non-Gaussian components tends to zero at a parametric rate. Once NGCA components are identified and extracted, various tasks can be applied in the data analysis process, like data visualization, clustering, denoising or classification. A numerical study demonstrates the usefulness of our method.
Divergences, surrogate loss functions and experimental design
Authors: Martin J. Wainwright, Michael I. Jordan Xuanlong Nguyen
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: In this paper, we provide a general theorem that establishes a correspon- dence between surrogate loss functions in classiﬁcation and the family of f-divergences. Moreover, we provide constructive procedures for determining the f-divergence induced by a given surrogate loss, and conversely for ﬁnding all surrogate loss functions that realize a given f-divergence. Next we introduce the notion of universal equivalence among loss functions and corresponding f-divergences, and provide nec- essary and sufﬁcient conditions for universal equivalence to hold. These ideas have applications to classiﬁcation problems that also involve a com- ponent of experiment design; in particular, we leverage our results to prove consistency of a procedure for learning a classiﬁer under decen- tralization requirements.
Mixture Modeling by Affinity Propagation
Authors: Delbert Dueck Brendan J. Frey
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Clustering is a fundamental problem in machine learning and has been approached in many ways. Two general and quite different approaches include iteratively ﬁtting a mixture model (e.g., using EM) and linking to- gether pairs of training cases that have high afﬁnity (e.g., using spectral methods). Pair-wise clustering algorithms need not compute sufﬁcient statistics and avoid poor solutions by directly placing similar examples in the same cluster. However, many applications require that each cluster of data be accurately described by a prototype or model, so afﬁnity-based clustering – and its beneﬁts – cannot be directly realized. We describe a technique called “afﬁnity propagation”, which combines the advantages of both approaches. The method learns a mixture model of the data by recursively propagating afﬁnity messages. We demonstrate afﬁnity prop- agation on the problems of clustering image patches for image segmen- tation and learning mixtures of gene expression models from microar- ray data. We ﬁnd that afﬁnity propagation obtains better solutions than mixtures of Gaussians, the K-medoids algorithm, spectral clustering and hierarchical clustering, and is both able to ﬁnd a pre-speciﬁed number of clusters and is able to automatically determine the number of clusters. Interestingly, afﬁnity propagation can be viewed as belief propagation in a graphical model that accounts for pairwise training case likelihood functions and the identiﬁcation of cluster centers.
Tensor Subspace Analysis
Authors: Deng Cai, Partha Niyogi Xiaofei He
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Previous work has demonstrated that the image variations of many ob- jects (human faces in particular) under variable lighting can be effec- tively modeled by low dimensional linear spaces. The typical linear sub- space learning algorithms include Principal Component Analysis (PCA), Linear Discriminant Analysis (LDA), and Locality Preserving Projec- tion (LPP). All of these methods consider an n1 × n2 image as a high dimensional vector in Rn1×n2, while an image represented in the plane is intrinsically a matrix. In this paper, we propose a new algorithm called Tensor Subspace Analysis (TSA). TSA considers an image as the sec- ond order tensor in Rn1 ⊗ Rn2, where Rn1 and Rn2 are two vector spaces. The relationship between the column vectors of the image ma- trix and that between the row vectors can be naturally characterized by TSA. TSA detects the intrinsic local geometrical structure of the tensor space by learning a lower dimensional tensor subspace. We compare our proposed approach with PCA, LDA and LPP methods on two standard databases. Experimental results demonstrate that TSA achieves better recognition rate, while being much more efﬁcient.
Query by Committee Made Real
Authors: Amir Navot, Naftali Tishby Ran Gilad-bachrach
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Training a learning algorithm is a costly task. A major goal of active learning is to reduce this cost. In this paper we introduce a new algorithm, KQBC, which is capable of actively learning large scale problems by using selective sampling. The algorithm overcomes the costly sampling step of the well known Query By Committee (QBC) algorithm by projecting onto a low dimensional space. KQBC also enables the use of kernels, providing a simple way of extending QBC to the non-linear scenario. Sampling the low dimension space is done using the hit and run random walk. We demonstrate the success of this novel algorithm by applying it to both artificial and a real world problems.
An Application of Markov Random Fields to Range Sensing
Authors: Sebastian Thrun James Diebel
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: This paper describes a highly successful application of MRFs to the problem of generating high-resolution range images. A new generation of range sensors combines the capture of low-resolution range images with the acquisition of registered high-resolution camera images. The MRF in this paper exploits the fact that discontinuities in range and coloring tend to co-align. This enables it to generate high-resolution, low-noise range images by integrating regular camera images into the range data. We show that by using such an MRF, we can substantially improve over existing range imaging technology.
Analysis of Spectral Kernel Design based Semi-supervised Learning
Authors: Rie Kubota Ando Tong Zhang
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We consider a framework for semi-supervised learning using spectral decomposition based un-supervised kernel design. This approach sub- sumes a class of previously proposed semi-supervised learning methods on data graphs. We examine various theoretical properties of such meth- ods. In particular, we derive a generalization performance bound, and obtain the optimal kernel design by minimizing the bound. Based on the theoretical analysis, we are able to demonstrate why spectral kernel design based methods can often improve the predictive performance. Ex- periments are used to illustrate the main consequences of our analysis.
Representing Part-Whole Relationships in Recurrent Neural Networks
Authors: Valentin Zhigulin, H. S. Seung Viren Jain
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: There is little consensus about the computational function of top-down synaptic connections in the visual system. Here we explore the hypothesis that top-down connections, like bottom-up connections, reflect partwhole relationships. We analyze a recurrent network with bidirectional synaptic interactions between a layer of neurons representing parts and a layer of neurons representing wholes. Within each layer, there is lateral inhibition. When the network detects a whole, it can rigorously enforce part-whole relationships by ignoring parts that do not belong. The network can complete the whole by filling in missing parts. The network can refuse to recognize a whole, if the activated parts do not conform to a stored part-whole relationship. Parameter regimes in which these behaviors happen are identified using the theory of permitted and forbidden sets [3, 4]. The network behaviors are illustrated by recreating Rumelhart and McClelland's "interactive activation" model [7]. In neural network models of visual object recognition [2, 6, 8], patterns of synaptic connectivity often reflect part-whole relationships between the features that are represented by neurons. For example, the connections of Figure 1 reflect the fact that feature B both contains simpler features A1, A2, and A3, and is contained in more complex features C1, C2, and C3. Such connectivity allows neurons to follow the rule that existence of the part is evidence for existence of the whole. By combining synaptic input from multiple sources of evidence for a feature, a neuron can "decide" whether that feature is present. 1 The synapses shown in Figure 1 are purely bottom-up, directed from simple to complex features. However, there are also top-down connections in the visual system, and there is little consensus about their function. One possibility is that top-down connections also reflect part-whole relationships. They allow feature detectors to make decisions using the rule that existence of the whole is evidence for existence of its parts. In this paper, we analyze the dynamics of a recurrent network in which part-whole relationships are stored as bidirectional synaptic interactions, rather than the unidirectional interactions of Figure 1. The network has a number of interesting computational capabilities. When the network detects a whole, it can rigorously enforce part-whole relationships Synaptic connectivity may reflect other relationships besides part-whole. For example, invariances can be implemented by connecting detectors of several instances of the same feature to the same target, which is consequently an invariant detector of the feature. 1
Size Regularized Cut for Data Clustering
Authors: Ya Zhang, Xiang Ji Yixin Chen
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We present a novel spectral clustering method that enables users to incorporate prior knowledge of the size of clusters into the clustering process. The cost function, which is named size regularized cut (SRcut), is defined as the sum of the inter-cluster similarity and a regularization term measuring the relative size of two clusters. Finding a partition of the data set to minimize SRcut is proved to be NP-complete. An approximation algorithm is proposed to solve a relaxed version of the optimization problem as an eigenvalue problem. Evaluations over different data sets demonstrate that the method is not sensitive to outliers and performs better than normalized cut.
How fast to work: Response vigor, motivation and tonic dopamine
Authors: Nathaniel D. Daw, Peter Dayan Yael Niv
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Reinforcement learning models have long promised to unify computa- tional, psychological and neural accounts of appetitively conditioned be- havior. However, the bulk of data on animal conditioning comes from free-operant experiments measuring how fast animals will work for rein- forcement. Existing reinforcement learning (RL) models are silent about these tasks, because they lack any notion of vigor. They thus fail to ad- dress the simple observation that hungrier animals will work harder for food, as well as stranger facts such as their sometimes greater produc- tivity even when working for irrelevant outcomes such as water. Here, we develop an RL framework for free-operant behavior, suggesting that subjects choose how vigorously to perform selected actions by optimally balancing the costs and beneﬁts of quick responding. Motivational states such as hunger shift these factors, skewing the tradeoff. This accounts normatively for the effects of motivation on response rates, as well as many other classic ﬁndings. Finally, we suggest that tonic levels of dopamine may be involved in the computation linking motivational state to optimal responding, thereby explaining the complex vigor-related ef- fects of pharmacological manipulation of dopamine.
Robust design of biological experiments
Authors: Adam Arkin, Michael I. Jordan Patrick Flaherty
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We address the problem of robust, computationally-efficient design of biological experiments. Classical optimal experiment design methods have not been widely adopted in biological practice, in part because the resulting designs can be very brittle if the nominal parameter estimates for the model are poor, and in part because of computational constraints. We present a method for robust experiment design based on a semidefinite programming relaxation. We present an application of this method to the design of experiments for a complex calcium signal transduction pathway, where we have found that the parameter estimates obtained from the robust design are better than those obtained from an "optimal" design.
On the Accuracy of Bounded Rationality: How Far from Optimal Is Fast and Frugal?
Authors: Laura Martignon Michael Schmitt
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Fast and frugal heuristics are well studied models of bounded rationality. Psychological research has proposed the take-the-best heuristic as a successful strategy in decision making with limited resources. Take-thebest searches for a sufficiently good ordering of cues (features) in a task where objects are to be compared lexicographically. We investigate the complexity of the problem of approximating optimal cue permutations for lexicographic strategies. We show that no efficient algorithm can approximate the optimum to within any constant factor, if P = NP. We further consider a greedy approach for building lexicographic strategies and derive tight bounds for the performance ratio of a new and simple algorithm. This algorithm is proven to perform better than take-the-best.
Fast Online Policy Gradient Learning with SMD Gain Vector Adaptation
Authors: Douglas Aberdeen, Nicol N. Schraudolph Jin Yu
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Reinforcement learning by direct policy gradient estimation is attractive in theory but in practice leads to notoriously ill-behaved optimization problems. We improve its robustness and speed of convergence with stochastic meta-descent, a gain vector adaptation method that employs fast Hessian-vector products. In our experiments the resulting algorithms outperform previously employed online stochastic, ofﬂine conjugate, and natural policy gradient methods.
A Bayes Rule for Density Matrices
Authors: Manfred K. Warmuth
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: The classical Bayes rule computes the posterior model probability from the prior probability and the data likelihood. We generalize this rule to the case when the prior is a density matrix (symmetric positive definite and trace one) and the data likelihood a covariance matrix. The classical Bayes rule is retained as the special case when the matrices are diagonal. In the classical setting, the calculation of the probability of the data is an expected likelihood, where the expectation is over the prior distribution. In the generalized setting, this is replaced by an expected variance calculation where the variance is computed along the eigenvectors of the prior density matrix and the expectation is over the eigenvalues of the density matrix (which form a probability vector). The variances along any direction is determined by the covariance matrix. Curiously enough this expected variance calculation is a quantum measurement where the co-variance matrix specifies the instrument and the prior density matrix the mixture state of the particle. We motivate both the classical and the generalized Bayes rule with a minimum relative entropy principle, where the Kullbach-Leibler version gives the classical Bayes rule and Umegaki's quantum relative entropy the new Bayes rule for density matrices.
Combining Graph Laplacians for Semi--Supervised Learning
Authors: Mark Herbster, Massimiliano Pontil Andreas Argyriou
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: A foundational problem in semi-supervised learning is the construction of a graph underlying the data. We propose to use a method which optimally combines a number of differently constructed graphs. For each of these graphs we associate a basic graph kernel. We then compute an optimal combined kernel. This kernel solves an extended regularization problem which requires a joint minimization over both the data and the set of graph kernels. We present encouraging results on different OCR tasks where the optimal combined kernel is computed from graphs constructed with a variety of distances functions and the `k ' in nearest neighbors.
Integrate-and-Fire models with adaptation are good enough
Authors: Alexander Rauch, Hans-rudolf Lüscher, Wulfram Gerstner Renaud Jolivet
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Integrate-and-Fire-type models are usually criticized because of their simplicity. On the other hand, the Integrate-and-Fire model is the basis of most of the theoretical studies on spiking neuron models. Here, we develop a sequential procedure to quantitatively evaluate an equivalent Integrate-and-Fire-type model based on intracellular recordings of cortical pyramidal neurons. We find that the resulting effective model is sufficient to predict the spike train of the real pyramidal neuron with high accuracy. In in vivo-like regimes, predicted and recorded traces are almost indistinguishable and a significant part of the spikes can be predicted at the correct timing. Slow processes like spike-frequency adaptation are shown to be a key feature in this context since they are necessary for the model to connect between different driving regimes.
Large-Scale Multiclass Transduction
Authors: Quoc V. Le, Simon Burton, Alex J. Smola, Vishy Vishwanathan Thomas Gärtner
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We present a method for performing transductive inference on very large datasets. Our algorithm is based on multiclass Gaussian processes and is effective whenever the multiplication of the kernel matrix or its inverse with a vector can be computed sufﬁciently fast. This holds, for instance, for certain graph and string kernels. Transduction is achieved by varia- tional inference over the unlabeled data subject to a balancing constraint.
Sparse Gaussian Processes using Pseudo-inputs
Authors: Zoubin Ghahramani Edward Snelson
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We present a new Gaussian process (GP) regression model whose covariance is parameterized by the the locations of M pseudo-input points, which we learn by a gradient based optimization. We take M N, where N is the number of real data points, and hence obtain a sparse regression method which has O(M 2 N ) training cost and O(M 2 ) prediction cost per test case. We also find hyperparameters of the covariance function in the same joint optimization. The method can be viewed as a Bayesian regression model with particular input dependent noise. The method turns out to be closely related to several other sparse GP approaches, and we discuss the relation in detail. We finally demonstrate its performance on some large data sets, and make a direct comparison to other sparse GP methods. We show that our method can match full GP performance with small M , i.e. very sparse solutions, and it significantly outperforms other approaches in this regime.
Fast biped walking with a reflexive controller and real-time policy searching
Authors: Bernd Porr, Florentin Wörgötter Tao Geng
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: In this paper, we present our design and experiments of a planar biped robot ("RunBot") under pure reflexive neuronal control. The goal of this study is to combine neuronal mechanisms with biomechanics to obtain very fast speed and the on-line learning of circuit parameters. Our controller is built with biologically inspired sensor- and motor-neuron models, including local reflexes and not employing any kind of position or trajectory-tracking control algorithm. Instead, this reflexive controller allows RunBot to exploit its own natural dynamics during critical stages of its walking gait cycle. To our knowledge, this is the first time that dynamic biped walking is achieved using only a pure reflexive controller. In addition, this structure allows using a policy gradient reinforcement learning algorithm to tune the parameters of the reflexive controller in real-time during walking. This way RunBot can reach a relative speed of 3.5 leg-lengths per second after a few minutes of online learning, which is faster than that of any other biped robot, and is also comparable to the fastest relative speed of human walking. In addition, the stability domain of stable walking is quite large supporting this design strategy.
Learning from Data of Variable Quality
Authors: Michael Kearns, Jennifer Wortman Koby Crammer
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We initiate the study of learning from multiple sources of limited data, each of which may be corrupted at a different rate. We develop a com- plete theory of which data sources should be used for two fundamental problems: estimating the bias of a coin, and learning a classiﬁer in the presence of label noise. In both cases, efﬁcient algorithms are provided for computing the optimal subset of data.
Two view learning: SVM-2K, Theory and Practice
Authors: David Hardoon, Hongying Meng, John S. Shawe-taylor, Sándor Szedmák Jason Farquhar
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Kernel methods make it relatively easy to define complex highdimensional feature spaces. This raises the question of how we can identify the relevant subspaces for a particular learning task. When two views of the same phenomenon are available kernel Canonical Correlation Analysis (KCCA) has been shown to be an effective preprocessing step that can improve the performance of classification algorithms such as the Support Vector Machine (SVM). This paper takes this observation to its logical conclusion and proposes a method that combines this two stage learning (KCCA followed by SVM) into a single optimisation termed SVM-2K. We present both experimental and theoretical analysis of the approach showing encouraging results and insights.
Extracting Dynamical Structure Embedded in Neural Activity
Authors: Afsheen Afshar, Gopal Santhanam, Stephen I. Ryu, Krishna V. Shenoy, Maneesh Sahani Byron M. Yu
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Spiking activity from neurophysiological experiments often exhibits dy- namics beyond that driven by external stimulation, presumably reﬂect- ing the extensive recurrence of neural circuitry. Characterizing these dynamics may reveal important features of neural computation, par- ticularly during internally-driven cognitive operations. For example, the activity of premotor cortex (PMd) neurons during an instructed de- lay period separating movement-target speciﬁcation and a movement- initiation cue is believed to be involved in motor planning. We show that the dynamics underlying this activity can be captured by a low- dimensional non-linear dynamical systems model, with underlying re- current structure and stochastic point-process output. We present and validate latent variable methods that simultaneously estimate the system parameters and the trial-by-trial dynamical trajectories. These meth- ods are applied to characterize the dynamics in PMd data recorded from a chronically-implanted 96-electrode array while monkeys perform delayed-reach tasks.
Large-scale biophysical parameter estimation in single neurons via constrained linear regression
Authors: Liam Paninski, Quentin J. Huys Misha Ahrens
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Our understanding of the input-output function of single cells has been substantially advanced by biophysically accurate multi-compartmental models. The large number of parameters needing hand tuning in these models has, however, somewhat hampered their applicability and interpretability. Here we propose a simple and well-founded method for automatic estimation of many of these key parameters: 1) the spatial distribution of channel densities on the cell's membrane; 2) the spatiotemporal pattern of synaptic input; 3) the channels' reversal potentials; 4) the intercompartmental conductances; and 5) the noise level in each compartment. We assume experimental access to: a) the spatiotemporal voltage signal in the dendrite (or some contiguous subpart thereof, e.g. via voltage sensitive imaging techniques), b) an approximate kinetic description of the channels and synapses present in each compartment, and c) the morphology of the part of the neuron under investigation. The key observation is that, given data a)-c), all of the parameters 1)-4) may be simultaneously inferred by a version of constrained linear regression; this regression, in turn, is efficiently solved using standard algorithms, without any "local minima" problems despite the large number of parameters and complex dynamics. The noise level 5) may also be estimated by standard techniques. We demonstrate the method's accuracy on several model datasets, and describe techniques for quantifying the uncertainty in our estimates.
Data-Driven Online to Batch Conversions
Authors: Yoram Singer Ofer Dekel
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Online learning algorithms are typically fast, memory efficient, and simple to implement. However, many common learning problems fit more naturally in the batch learning setting. The power of online learning algorithms can be exploited in batch settings by using online-to-batch conversions techniques which build a new batch algorithm from an existing online algorithm. We first give a unified overview of three existing online-to-batch conversion techniques which do not use training data in the conversion process. We then build upon these data-independent conversions to derive and analyze data-driven conversions. Our conversions find hypotheses with a small risk by explicitly minimizing datadependent generalization bounds. We experimentally demonstrate the usefulness of our approach and in particular show that the data-driven conversions consistently outperform the data-independent conversions.
Learning Rankings via Convex Hull Separation
Authors: Rómer Rosales, Balaji Krishnapuram Glenn Fung
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We propose efﬁcient algorithms for learning ranking functions from or- der constraints between sets—i.e. classes—of training samples. Our al- gorithms may be used for maximizing the generalized Wilcoxon Mann Whitney statistic that accounts for the partial ordering of the classes: spe- cial cases include maximizing the area under the ROC curve for binary classiﬁcation and its generalization for ordinal regression. Experiments on public benchmarks indicate that: (a) the proposed algorithm is at least as accurate as the current state-of-the-art; (b) computationally, it is sev- eral orders of magnitude faster and—unlike current methods—it is easily able to handle even large datasets with over 20,000 samples.