mtybilly/Instruct2DS huggingface dataset:
Distributed Dual Averaging In Networks
Authors: Alekh Agarwal, Martin J. Wainwright, John C. Duchi
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: The goal of decentralized optimization over a network is to optimize a global objective formed by a sum of local (possibly nonsmooth) convex functions using only local computation and communication. We develop and analyze distributed algorithms based on dual averaging of subgradients, and we provide sharp bounds on their convergence rates as a function of the network size and topology. Our analysis clearly separates the convergence of the optimization algorithm itself from the effects of communication constraints arising from the network structure. We show that the number of iterations required by our algorithm scales inversely in the spectral gap of the network. The sharpness of this prediction is confirmed both by theoretical lower bounds and simulations for various networks.
Probabilistic Inference and Differential Privacy
Authors: Oliver Williams, Frank Mcsherry
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We identify and investigate a strong connection between probabilistic inference and differential privacy, the latter being a recent privacy definition that permits only indirect observation of data through noisy measurement. Previous research on differential privacy has focused on designing measurement processes whose output is likely to be useful on its own. We consider the potential of applying probabilistic inference to the measurements and measurement process to derive posterior distributions over the data sets and model parameters thereof. We find that probabilistic inference can improve accuracy, integrate multiple observations, measure uncertainty, and even provide posterior distributions over quantities that were not directly measured.
Copula Processes
Authors: Andrew G Wilson, Zoubin Ghahramani
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We define a copula process which describes the dependencies between arbitrarily many random variables independently of their marginal distributions. As an example, we develop a stochastic volatility model, Gaussian Copula Process Volatility (GCPV), to predict the latent standard deviations of a sequence of random variables. To make predictions we use Bayesian inference, with the Laplace approximation, and with Markov chain Monte Carlo as an alternative. We find our model can outperform GARCH on simulated and financial data. And unlike GARCH, GCPV can easily handle missing data, incorporate covariates other than time, and model a rich class of covariance structures.
Learning invariant features using the Transformed Indian Buffet Process
Authors: Joseph L. Austerweil, Thomas L. Griffiths
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Identifying the features of objects becomes a challenge when those features can change in their appearance. We introduce the Transformed Indian Buffet Process (tIBP), and use it to define a nonparametric Bayesian model that infers features that can transform across instantiations. We show that this model can identify features that are location invariant by modeling a previous experiment on human feature learning. However, allowing features to transform adds new kinds of ambiguity: Are two parts of an object the same feature with different transformations or two unique features? What transformations can features undergo? We present two new experiments in which we explore how people resolve these questions, showing that the tIBP model demonstrates a similar sensitivity to context to that shown by human learners when determining the invariant aspects of features.
An Inverse Power Method for Nonlinear Eigenproblems with Applications in 1-Spectral Clustering and Sparse PCA
Authors: Matthias Hein, Thomas Bühler
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Many problems in machine learning and statistics can be formulated as (generalized) eigenproblems. In terms of the associated optimization problem, computing linear eigenvectors amounts to finding critical points of a quadratic function subject to quadratic constraints. In this paper we show that a certain class of constrained optimization problems with nonquadratic objective and constraints can be understood as nonlinear eigenproblems. We derive a generalization of the inverse power method which is guaranteed to converge to a nonlinear eigenvector. We apply the inverse power method to 1-spectral clustering and sparse PCA which can naturally be formulated as nonlinear eigenproblems. In both applications we achieve state-of-the-art results in terms of solution quality and runtime. Moving beyond the standard eigenproblem should be useful also in many other applications and our inverse power method can be easily adapted to new problems.
Fast detection of multiple change-points shared by many signals using group LARS
Authors: Jean-philippe Vert, Kevin Bleakley
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We present a fast algorithm for the detection of multiple change-points when each is frequently shared by members of a set of co-occurring one-dimensional signals. We give conditions on consistency of the method when the number of signals increases, and provide empirical evidence to support the consistency results.
Learning To Count Objects in Images
Authors: Victor Lempitsky, Andrew Zisserman
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We propose a new supervised learning framework for visual object counting tasks, such as estimating the number of cells in a microscopic image or the number of humans in surveillance video frames. We focus on the practically-attractive case when the training images are annotated with dots (one dot per object).   Our goal is to accurately estimate the count. However, we evade the hard task of learning to detect and localize individual object instances. Instead, we cast the problem as that of estimating an image density whose integral over any image region gives the count of objects within that region. Learning to infer such density can be formulated as a minimization of a regularized risk quadratic cost function. We introduce a new loss function, which is well-suited for such learning, and at the same time can be computed efficiently via a maximum subarray algorithm. The learning can then be posed as a convex quadratic program solvable with cutting-plane optimization.  The proposed framework is very flexible as it can accept any domain-specific visual features. Once trained, our system provides accurate object counts and requires a very small time overhead over the feature extraction step, making it a good candidate for applications involving real-time processing or dealing with huge amount of visual data.
Robust PCA via Outlier Pursuit
Authors: Huan Xu, Constantine Caramanis, Sujay Sanghavi
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Singular Value Decomposition (and Principal Component Analysis)  is one of the most widely used techniques for dimensionality reduction: successful and efficiently computable, it is nevertheless plagued by a well-known, well-documented sensitivity to outliers. Recent work has considered the setting where each point has a few arbitrarily corrupted components. Yet, in applications of SVD or PCA such as robust collaborative filtering or bioinformatics, malicious agents, defective genes, or simply corrupted or contaminated experiments may effectively yield entire points that are completely corrupted.  We present an efficient convex optimization-based  algorithm we call Outlier Pursuit, that under some mild assumptions on the uncorrupted points (satisfied, e.g., by the standard generative assumption in PCA problems) recovers the exact optimal low-dimensional subspace, and identifies the corrupted points. Such identification of corrupted points that do not conform to the low-dimensional approximation, is of paramount interest in bioinformatics and financial applications, and beyond. Our techniques involve matrix decomposition using nuclear norm minimization, however, our results, setup, and approach, necessarily differ considerably from the existing line of work in matrix completion and matrix decomposition, since we develop an approach to recover the correct column space of the uncorrupted matrix, rather than the exact matrix itself.
Multi-label Multiple Kernel Learning by Stochastic Approximation: Application to Visual Object Recognition
Authors: Serhat Bucak, Rong Jin, Anil K. Jain
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: Recent studies have shown that multiple kernel learning is very effective for object recognition, leading to the popularity  of kernel learning in computer vision problems. In this work, we develop an efficient algorithm for multi-label multiple kernel learning (ML-MKL). We assume that all the classes under  consideration  share the same combination of kernel functions, and the objective is to find the optimal kernel combination that benefits all the classes. Although several algorithms have been developed for ML-MKL, their computational cost is linear in the number of classes, making them unscalable when the number of classes is large, a challenge  frequently  encountered in visual object recognition. We address this computational challenge by developing a framework for ML-MKL that combines the worst-case analysis with stochastic approximation. Our analysis shows that the complexity of our algorithm is $O(m^{1/3}\sqrt{ln m})$, where $m$ is the number of classes. Empirical studies with object recognition show that while achieving similar classification accuracy, the proposed method is significantly more efficient than the state-of-the-art algorithms for ML-MKL.
Learning sparse dynamic linear systems using stable spline kernels and exponential hyperpriors
Authors: Alessandro Chiuso, Gianluigi Pillonetto
Published in: Advances in Neural Information Processing Systems 23  (NIPS 2010) (Main Conference Track), 2010

Abstract: We introduce a new Bayesian nonparametric approach to identification of sparse dynamic linear systems. The impulse responses are modeled as Gaussian processes whose autocovariances encode the BIBO stability constraint, as defined by the recently introduced “Stable Spline kernel”. Sparse solutions are obtained by placing exponential hyperpriors on the scale factors of such kernels. Numerical experiments regarding estimation of ARMAX models show that this technique provides a definite advantage over a group LAR algorithm and state-of-the-art parametric identification techniques based on prediction error minimization.
On Local Rewards and Scaling Distributed Reinforcement Learning
Authors: Drew Bagnell, Andrew Y. Ng
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We consider the scaling of the number of examples necessary to achieve good performance in distributed, cooperative, multi-agent reinforcement learning, as a function of the the number of agents n. We prove a worstcase lower bound showing that algorithms that rely solely on a global reward signal to learn policies confront a fundamental limit: They require a number of real-world examples that scales roughly linearly in the number of agents. For settings of interest with a very large number of agents, this is impractical. We demonstrate, however, that there is a class of algorithms that, by taking advantage of local reward signals in large distributed Markov Decision Processes, are able to ensure good performance with a number of samples that scales as O(log n). This makes them applicable even in settings with a very large number of agents n.
Learning Shared Latent Structure for Image Synthesis and Robotic Imitation
Authors: Aaron Shon, Keith Grochow, Aaron Hertzmann, Rajesh P. Rao
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We propose an algorithm that uses Gaussian process regression to learn common hidden structure shared between corresponding sets of heterogenous observations. The observation spaces are linked via a single, reduced-dimensionality latent variable space. We present results from two datasets demonstrating the algorithms's ability to synthesize novel data from learned correspondences. We first show that the method can learn the nonlinear mapping between corresponding views of objects, filling in missing data as needed to synthesize novel views. We then show that the method can learn a mapping between human degrees of freedom and robotic degrees of freedom for a humanoid robot, allowing robotic imitation of human poses from motion capture data.
Recovery of Jointly Sparse Signals from Few Random Projections
Authors: Michael B. Wakin, Marco F. Duarte, Shriram Sarvotham, Dror Baron, Richard G. Baraniuk
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Compressed sensing is an emerging ﬁeld based on the revelation that a small group of linear projections of a sparse signal contains enough information for reconstruc- tion. In this paper we introduce a new theory for distributed compressed sensing (DCS) that enables new distributed coding algorithms for multi-signal ensembles that exploit both intra- and inter-signal correlation structures. The DCS theory rests on a new concept that we term the joint sparsity of a signal ensemble. We study three simple models for jointly sparse signals, propose algorithms for joint recov- ery of multiple signals from incoherent projections, and characterize theoretically and empirically the number of measurements per sensor required for accurate re- construction. In some sense DCS is a framework for distributed compression of sources with memory, which has remained a challenging problem in information theory for some time. DCS is immediately applicable to a range of problems in sensor networks and arrays.
Saliency Based on Information Maximization
Authors: Neil Bruce, John Tsotsos
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: A model of bottom-up overt attention is proposed based on the principle  of maximizing information sampled from  a scene.  The proposed opera(cid:173) tion  is  based on  Shannon's self-information  measure and is  achieved in  a neural circuit, which is demonstrated as having close ties with  the cir(cid:173) cuitry existent in  the primate visual cortex.  It is  further shown  that the  proposed saliency measure may  be extended  to  address  issues that cur(cid:173) rently elude explanation in the domain of saliency based models.  Results  on  natural  images are compared with experimental eye tracking data re(cid:173) vealing  the  efficacy of the  model  in  predicting  the  deployment of overt  attention as compared with existing efforts.
Learning vehicular dynamics, with application to modeling helicopters
Authors: Pieter Abbeel, Varun Ganapathi, Andrew Y. Ng
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We consider the problem of modeling a helicopter's dynamics based on state-action trajectories collected from it. The contribution of this paper is two-fold. First, we consider the linear models such as learned by C I F E R (the industry standard in helicopter identification), and show that the linear parameterization makes certain properties of dynamical systems, such as inertia, fundamentally difficult to capture. We propose an alternative, acceleration based, parameterization that does not suffer from this deficiency, and that can be learned as efficiently from data. Second, a Markov decision process model of a helicopter's dynamics would explicitly model only the one-step transitions, but we are often interested in a model's predictive performance over longer timescales. In this paper, we present an efficient algorithm for (approximately) minimizing the prediction error over long time scales. We present empirical results on two different helicopters. Although this work was motivated by the problem of modeling helicopters, the ideas presented here are general, and can be applied to modeling large classes of vehicular dynamics.
Identifying Distributed Object Representations in Human Extrastriate Visual Cortex
Authors: Rory Sayres, David Ress, Kalanit Grill-spector
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: The category of visual stimuli has been reliably decoded from patterns of neural activity in extrastriate visual cortex [1]. It has yet to be seen whether object identity can be inferred from this activity. We present fMRI data measuring responses in human extrastriate cortex to a set of 12 distinct object images. We use a simple winner-take-all classifier, using half the data from each recording session as a training set, to evaluate encoding of object identity across fMRI voxels. Since this approach is sensitive to the inclusion of noisy voxels, we describe two methods for identifying subsets of voxels in the data which optimally distinguish object identity. One method characterizes the reliability of each voxel within subsets of the data, while another estimates the mutual information of each voxel with the stimulus set. We find that both metrics can identify subsets of the data which reliably encode object identity, even when noisy measurements are artificially added to the data. The mutual information metric is less efficient at this task, likely due to constraints in fMRI data.
Convex Neural Networks
Authors: Yoshua Bengio, Nicolas L. Roux, Pascal Vincent, Olivier Delalleau, Patrice Marcotte
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Convexity has recently received a lot of attention in the machine learning community, and the lack of convexity has been seen as a major disadvantage of many learning algorithms, such as multi-layer artificial neural networks. We show that training multi-layer neural networks in which the number of hidden units is learned can be viewed as a convex optimization problem. This problem involves an infinite number of variables, but can be solved by incrementally inserting a hidden unit at a time, each time finding a linear classifier that minimizes a weighted sum of errors.
Robust Fisher Discriminant Analysis
Authors: Seung-jean Kim, Alessandro Magnani, Stephen Boyd
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Fisher linear discriminant analysis (LDA) can be sensitive to the problem data. Robust Fisher LDA can systematically alleviate the sensitivity problem by explicitly incorporating a model of data uncertainty in a classification problem and optimizing for the worst-case scenario under this model. The main contribution of this paper is show that with general convex uncertainty models on the problem data, robust Fisher LDA can be carried out using convex optimization. For a certain type of product form uncertainty model, robust Fisher LDA can be carried out at a cost comparable to standard Fisher LDA. The method is demonstrated with some numerical examples. Finally, we show how to extend these results to robust kernel Fisher discriminant analysis, i.e., robust Fisher LDA in a high dimensional feature space.
Computing the Solution Path for the Regularized Support Vector Regression
Authors: Lacey Gunter, Ji Zhu
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: In this paper we derive an algorithm that computes the entire solu- tion path of the support vector regression, with essentially the same computational cost as ﬁtting one SVR model. We also propose an unbiased estimate for the degrees of freedom of the SVR model, which allows convenient selection of the regularization parameter.
Soft Clustering on Graphs
Authors: Kai Yu, Shipeng Yu, Volker Tresp
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We propose a simple clustering framework on graphs encoding pairwise data similarities. Unlike usual similarity-based methods, the approach softly assigns data to clusters in a probabilistic way. More importantly, a hierarchical clustering is naturally derived in this framework to gradually merge lower-level clusters into higher-level ones. A random walk analysis indicates that the algorithm exposes clustering structures in various resolutions, i.e., a higher level statistically models a longer-term diffusion on graphs and thus discovers a more global clustering structure. Finally we provide very encouraging experimental results.
Efficient estimation of hidden state dynamics from spike trains
Authors: Marton G. Danoczy, Richard H. R. Hahnloser
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Neurons can have rapidly changing spike train statistics dictated by the underlying network excitability or behavioural state of an animal. To estimate the time course of such state dynamics from single- or multi- ple neuron recordings, we have developed an algorithm that maximizes the likelihood of observed spike trains by optimizing the state lifetimes and the state-conditional interspike-interval (ISI) distributions. Our non- parametric algorithm is free of time-binning and spike-counting prob- lems and has the computational complexity of a Mixed-state Markov Model operating on a state sequence of length equal to the total num- ber of recorded spikes. As an example, we ﬁt a two-state model to paired recordings of premotor neurons in the sleeping songbird. We ﬁnd that the two state-conditional ISI functions are highly similar to the ones mea- sured during waking and singing, respectively.
From Batch to Transductive Online Learning
Authors: Sham Kakade, Adam Tauman Kalai
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: It is well-known that everything that is learnable in the difﬁcult online setting, where an arbitrary sequences of examples must be labeled one at a time, is also learnable in the batch setting, where examples are drawn independently from a distribution. We show a result in the opposite di- rection. We give an efﬁcient conversion algorithm from batch to online that is transductive: it uses future unlabeled data. This demonstrates the equivalence between what is properly and efﬁciently learnable in a batch model and a transductive online model.
Learning Depth from Single Monocular Images
Authors: Ashutosh Saxena, Sung H. Chung, Andrew Y. Ng
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: We consider the task of depth estimation from a single monocular image. We take a supervised learning approach to this problem, in which we begin by collecting a training set of monocular images (of unstructured outdoor environments which include forests, trees, buildings, etc.) and their corresponding ground-truth depthmaps. Then, we apply supervised learning to predict the depthmap as a function of the image. Depth estimation is a challenging problem, since local features alone are insufficient to estimate depth at a point, and one needs to consider the global context of the image. Our model uses a discriminatively-trained Markov Random Field (MRF) that incorporates multiscale local- and global-image features, and models both depths at individual points as well as the relation between depths at different points. We show that, even on unstructured scenes, our algorithm is frequently able to recover fairly accurate depthmaps.
Non-Local Manifold Parzen Windows
Authors: Yoshua Bengio, Hugo Larochelle, Pascal Vincent
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: To escape from the curse of dimensionality, we claim that one can learn non-local functions, in the sense that the value and shape of the learned function at x must be inferred using examples that may be far from x. With this objective, we present a non-local non-parametric density esti- mator. It builds upon previously proposed Gaussian mixture models with regularized covariance matrices to take into account the local shape of the manifold. It also builds upon recent work on non-local estimators of the tangent plane of a manifold, which are able to generalize in places with little training data, unlike traditional, local, non-parametric models.
Bayesian Sets
Authors: Zoubin Ghahramani, Katherine A. Heller
Published in: Advances in Neural Information Processing Systems 18  (NIPS 2005) (Main Conference Track), 2005

Abstract: Inspired by “Google™ Sets”, we consider the problem of retrieving items from a concept or cluster, given a query consisting of a few items from that cluster. We formulate this as a Bayesian inference problem and de- scribe a very simple algorithm for solving it. Our algorithm uses a model- based concept of a cluster and ranks items using a score which evaluates the marginal probability that each item belongs to a cluster containing the query items. For exponential family models with conjugate priors this marginal probability is a simple function of sufﬁcient statistics. We focus on sparse binary data and show that our score can be evaluated ex- actly using a single sparse matrix multiplication, making it possible to apply our algorithm to very large datasets. We evaluate our algorithm on three datasets: retrieving movies from EachMovie, ﬁnding completions of author sets from the NIPS dataset, and ﬁnding completions of sets of words appearing in the Grolier encyclopedia. We compare to Google™ Sets and show that Bayesian Sets gives very reasonable set completions.
Modeling Neuronal Interactivity using Dynamic Bayesian Networks
Authors: Lei Zhang, Dimitris Samaras, Nelly Alia-klein, Nora Volkow, Rita Goldstein
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: Eizaburo Doi, Doru C. Balcan, Michael S. Lewicki
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: Rong Jin, Feng Kang, Chris H. Ding
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: Jian Zhang, Zoubin Ghahramani, Yiming Yang
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: Daichi Mochihashi, Yuji Matsumoto
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: Sathiya Keerthi, Wei Chu
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: Le Song, Evian Gordon, Elly Gysels
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: O. P. Kreidl, Alan S. Willsky
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: Jason Palmer, Kenneth Kreutz-Delgado, Bhaskar D. Rao, David P. Wipf
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: Brigham S. Anderson, Andrew W. Moore
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: Sridhar Mahadevan, Mauro Maggioni
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: Daniel B. Neill, Andrew W. Moore, Gregory F. Cooper
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: Boaz Nadler, Stephane Lafon, Ioannis Kevrekidis, Ronald R. Coifman
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: Tai-sing Lee, Brian R. Potetz
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: Laurent Zwald, Gilles Blanchard
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: Antoni B. Chan, Nuno Vasconcelos
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: Raymond J. Mooney, Razvan C. Bunescu
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: Vidhya Navalpakkam, Laurent Itti
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: Zoubin Ghahramani, Thomas L. Griffiths
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: Gilles Blanchard, Masashi Sugiyama, Motoaki Kawanabe, Vladimir Spokoiny, Klaus-Robert Müller
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: Xuanlong Nguyen, Martin J. Wainwright, Michael I. Jordan
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.