mtybilly/Instruct2DS huggingface dataset:
Colored Maximum Variance Unfolding
Authors: Le Song, Arthur Gretton, Karsten Borgwardt, Alex J. Smola
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Maximum variance unfolding (MVU) is an effective heuristic for dimensionality reduction. It produces a low-dimensional representation of the data by maximiz- ing the variance of their embeddings while preserving the local distances of the original data. We show that MVU also optimizes a statistical dependence measure which aims to retain the identity of individual observations under the distance- preserving constraints. This general view allows us to design “colored” variants of MVU, which produce low-dimensional representations for a given task, e.g. subject to class labels or other side information.
Adaptive Embedded Subgraph Algorithms using Walk-Sum Analysis
Authors: Venkat Chandrasekaran, Alan S. Willsky, Jason K. Johnson
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We consider the estimation problem in Gaussian graphical models with arbitrary structure. We analyze the Embedded Trees algorithm, which solves a sequence of problems on tractable subgraphs thereby leading to the solution of the estimation problem on an intractable graph. Our analysis is based on the recently developed walk-sum interpretation of Gaussian estimation. We show that non-stationary iterations of the Embedded Trees algorithm using any sequence of subgraphs converge in walk-summable models. Based on walk-sum calculations, we develop adaptive methods that optimize the choice of subgraphs used at each iteration with a view to achieving maximum reduction in error. These adaptive procedures provide a significant speedup in convergence over stationary iterative methods, and also appear to converge in a larger class of models.
Ultrafast Monte Carlo for Statistical Summations
Authors: Charles L. Isbell, Michael P. Holmes, Alexander G. Gray
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Machine learning contains many computational bottlenecks in the form of nested summations over datasets. Kernel estimators and other methods are burdened by these expensive computations. Exact evaluation is typically O(n2 ) or higher, which severely limits application to large datasets. We present a multi-stage stratified Monte Carlo method for approximating such summations with probabilistic relative error control. The essential idea is fast approximation by sampling in trees. This method differs from many previous scalability techniques (such as standard multi-tree methods) in that its error is stochastic, but we derive conditions for error control and demonstrate that they work. Further, we give a theoretical sample complexity for the method that is independent of dataset size, and show that this appears to hold in experiments, where speedups reach as high as 1014 , many orders of magnitude beyond the previous state of the art.
Inferring Neural Firing Rates from Spike Trains Using Gaussian Processes
Authors: John P. Cunningham, Byron M. Yu, Krishna V. Shenoy, Maneesh Sahani
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Neural spike trains present challenges to analytical efforts due to their noisy, spiking nature. Many studies of neuroscienti(cid:2)c and neural prosthetic importance rely on a smoothed, denoised estimate of the spike train’s underlying (cid:2)ring rate. Current techniques to (cid:2)nd time-varying (cid:2)ring rates require ad hoc choices of parameters, offer no con(cid:2)dence intervals on their estimates, and can obscure potentially important single trial variability. We present a new method, based on a Gaussian Process prior, for inferring probabilistically optimal estimates of (cid:2)ring rate functions underlying single or multiple neural spike trains. We test the performance of the method on simulated data and experimentally gathered neural spike trains, and we demonstrate improvements over conventional estimators.
People Tracking with the Laplacian Eigenmaps Latent Variable Model
Authors: Zhengdong Lu, Cristian Sminchisescu, Miguel Á. Carreira-Perpiñán
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Reliably recovering 3D human pose from monocular video requires constraints that bias the estimates towards typical human poses and motions. We define priors for people tracking using a Laplacian Eigenmaps Latent Variable Model (LELVM). LELVM is a probabilistic dimensionality reduction model that naturally combines the advantages of latent variable models---definining a multimodal probability density for latent and observed variables, and globally differentiable nonlinear mappings for reconstruction and dimensionality reduction---with those of spectral manifold learning methods---no local optima, ability to unfold highly nonlinear manifolds, and good practical scaling to latent spaces of high dimension. LELVM is computationally efficient, simple to learn from sparse training data, and compatible with standard probabilistic trackers such as particle filters. We analyze the performance of a LELVM-based probabilistic sigma point mixture tracker in several real and synthetic human motion sequences and demonstrate that LELVM provides sufficient constraints for robust operation in the presence of missing, noisy and ambiguous image measurements.
The Distribution Family of Similarity Distances
Authors: Gertjan Burghouts, Arnold Smeulders, Jan-mark Geusebroek
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Assessing similarity between features is a key step in object recognition and scene categorization tasks. We argue that knowledge on the distribution of distances generated by similarity functions is crucial in deciding whether features are similar or not. Intuitively one would expect that similarities between features could arise from any distribution. In this paper, we will derive the contrary, and report the theoretical result that $L_p$-norms --a class of commonly applied distance metrics-- from one feature vector to other vectors are Weibull-distributed if the feature values are correlated and non-identically distributed. Besides these assumptions being realistic for images, we experimentally show them to hold for various popular feature extraction algorithms, for a diverse range of images. This fundamental insight opens new directions in the assessment of feature similarity, with projected improvements in object and scene recognition algorithms.

Erratum: The authors of paper have declared that they have become convinced that the reasoning in the reference is too simple as a proof of their claims. As a consequence, they withdraw their theorems.
Congruence between model and human attention reveals unique signatures of critical visual events
Authors: Robert Peters, Laurent Itti
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Current computational models of bottom-up and top-down components of atten- tion are predictive of eye movements across a range of stimuli and of simple, ﬁxed visual tasks (such as visual search for a target among distractors). How- ever, to date there exists no computational framework which can reliably mimic human gaze behavior in more complex environments and tasks, such as driving a vehicle through traﬃc. Here, we develop a hybrid computational/behavioral framework, combining simple models for bottom-up salience and top-down rel- evance, and looking for changes in the predictive power of these components at diﬀerent critical event times during 4.7 hours (500,000 video frames) of observers playing car racing and ﬂight combat video games. This approach is motivated by our observation that the predictive strengths of the salience and relevance mod- els exhibit reliable temporal signatures during critical event windows in the task sequence—for example, when the game player directly engages an enemy plane in a ﬂight combat game, the predictive strength of the salience model increases signiﬁcantly, while that of the relevance model decreases signiﬁcantly. Our new framework combines these temporal signatures to implement several event detec- tors. Critically, we ﬁnd that an event detector based on fused behavioral and stim- ulus information (in the form of the model’s predictive strength) is much stronger than detectors based on behavioral information alone (eye position) or image in- formation alone (model prediction maps). This approach to event detection, based on eye tracking combined with computational models applied to the visual input, may have useful applications as a less-invasive alternative to other event detection approaches based on neural signatures derived from EEG or fMRI recordings.
Multi-task Gaussian Process Prediction
Authors: Edwin V. Bonilla, Kian M. Chai, Christopher Williams
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: In this paper we investigate multi-task learning in the context of Gaussian Pro- cesses (GP). We propose a model that learns a shared covariance function on input-dependent features and a “free-form” covariance matrix over tasks. This al- lows for good ﬂexibility when modelling inter-task dependencies while avoiding the need for large amounts of data for training. We show that under the assump- tion of noise-free observations and a block design, predictions for a given task only depend on its target values and therefore a cancellation of inter-task trans- fer occurs. We evaluate the beneﬁts of our model on two practical applications: a compiler performance prediction problem and an exam score prediction task. Additionally, we make use of GP approximations and properties of our model in order to provide scalability to large data sets.
Multi-Task Learning via Conic Programming
Authors: Tsuyoshi Kato, Hisashi Kashima, Masashi Sugiyama, Kiyoshi Asai
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: When we have several related tasks, solving them simultaneously is shown to be more effective than solving them individually. This approach is called multi-task learning (MTL) and has been studied extensively. Existing approaches to MTL often treat all the tasks as \emph{uniformly related to each other and the relatedness of the tasks is controlled globally. For this reason, the existing methods can lead to undesired solutions when some tasks are not highly related to each other, and some pairs of related tasks can have significantly different solutions. In this paper, we propose a novel MTL algorithm that can overcome these problems. Our method makes use of a task network, which describes the relation structure among tasks. This allows us to deal with intricate relation structures in a systematic way. Furthermore, we control the relatedness of the tasks locally, so all pairs of related tasks are guaranteed to have similar solutions. We apply the above idea to support vector machines (SVMs) and show that the optimization problem can be cast as a second order cone program, which is convex and can be solved efficiently. The usefulness of our approach is demonstrated through simulations with protein super-family classification and ordinal regression problems.
Incremental Natural Actor-Critic Algorithms
Authors: Shalabh Bhatnagar, Mohammad Ghavamzadeh, Mark Lee, Richard S. Sutton
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We present four new reinforcement learning algorithms based on actor-critic and natural-gradient ideas, and provide their convergence proofs. Actor-critic rein- forcement learning methods are online approximations to policy iteration in which the value-function parameters are estimated using temporal difference learning and the policy parameters are updated by stochastic gradient descent. Methods based on policy gradients in this way are of special interest because of their com- patibility with function approximation methods, which are needed to handle large or in(cid:2)nite state spaces. The use of temporal difference learning in this way is of interest because in many applications it dramatically reduces the variance of the gradient estimates. The use of the natural gradient is of interest because it can produce better conditioned parameterizations and has been shown to further re- duce variance in some cases. Our results extend prior two-timescale convergence results for actor-critic methods by Konda and Tsitsiklis by using temporal differ- ence learning in the actor and by incorporating natural gradients, and they extend prior empirical studies of natural actor-critic methods by Peters, Vijayakumar and Schaal by providing the (cid:2)rst convergence proofs and the (cid:2)rst fully incremental algorithms.
Collective Inference on Markov Models for Modeling Bird Migration
Authors: M.a. S. Elmohamed, Dexter Kozen, Daniel R. Sheldon
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We investigate a family of inference problems on Markov models, where many sample paths are drawn from a Markov chain and partial information is revealed to an observer who attempts to reconstruct the sample paths. We present algo- rithms and hardness results for several variants of this problem which arise by re- vealing different information to the observer and imposing different requirements for the reconstruction of sample paths. Our algorithms are analogous to the clas- sical Viterbi algorithm for Hidden Markov Models, which ﬁnds the single most probable sample path given a sequence of observations. Our work is motivated by an important application in ecology: inferring bird migration paths from a large database of observations.
EEG-Based Brain-Computer Interaction: Improved Accuracy by Automatic Single-Trial Error Detection
Authors: Pierre Ferrez, José Millán
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Brain-computer interfaces (BCIs), as any other interaction modality based on physiological signals and body channels (e.g., muscular activity, speech and gestures), are prone to errors in the recognition of subject's intent. An elegant approach to improve the accuracy of BCIs consists in a verification procedure directly based on the presence of error-related potentials (ErrP) in the EEG recorded right after the occurrence of an error. Six healthy volunteer subjects with no prior BCI experience participated in a new human-robot interaction experiment where they were asked to mentally move a cursor towards a target that can be reached within a few steps using motor imagination. This experiment confirms the previously reported presence of a new kind of ErrP. These Interaction ErrP" exhibit a first sharp negative peak followed by a positive peak and a second broader negative peak (~290, ~350 and ~470 ms after the feedback, respectively). But in order to exploit these ErrP we need to detect them in each single trial using a short window following the feedback associated to the response of the classifier embedded in the BCI. We have achieved an average recognition rate of correct and erroneous single trials of 81.8% and 76.2%, respectively. Furthermore, we have achieved an average recognition rate of the subject's intent while trying to mentally drive the cursor of 73.1%. These results show that it's possible to simultaneously extract useful information for mental control to operate a brain-actuated device as well as cognitive states such as error potentials to improve the quality of the brain-computer interaction. Finally, using a well-known inverse model (sLORETA), we show that the main focus of activity at the occurrence of the ErrP are, as expected, in the pre-supplementary motor area and in the anterior cingulate cortex."
Invariant Common Spatial Patterns: Alleviating Nonstationarities in Brain-Computer Interfacing
Authors: Benjamin Blankertz, Motoaki Kawanabe, Ryota Tomioka, Friederike Hohlefeld, Klaus-Robert Müller, Vadim V. Nikulin
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Brain-Computer Interfaces can suffer from a large variance of the subject condi- tions within and across sessions. For example vigilance ﬂuctuations in the indi- vidual, variable task involvement, workload etc. alter the characteristics of EEG signals and thus challenge a stable BCI operation. In the present work we aim to deﬁne features based on a variant of the common spatial patterns (CSP) algorithm that are constructed invariant with respect to such nonstationarities. We enforce invariance properties by adding terms to the denominator of a Rayleigh coefﬁcient representation of CSP such as disturbance covariance matrices from ﬂuctuations in visual processing. In this manner physiological prior knowledge can be used to shape the classiﬁcation engine for BCI. As a proof of concept we present a BCI classiﬁer that is robust to changes in the level of parietal a -activity. In other words, the EEG decoding still works when there are lapses in vigilance.
A Unified Near-Optimal Estimator For Dimension Reduction in $l_\alpha$ ($0<\alpha\leq 2$) Using Stable Random Projections
Authors: Ping Li, Trevor J. Hastie
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Many tasks (e.g., clustering) in machine learning only require the lα distances in- stead of the original data. For dimension reductions in the lα norm (0 < α ≤ 2), the method of stable random projections can efﬁciently compute the lα distances in massive datasets (e.g., the Web or massive data streams) in one pass of the data. The estimation task for stable random projections has been an interesting topic. We propose a simple estimator based on the fractional power of the samples (pro- jected data), which is surprisingly near-optimal in terms of the asymptotic vari- ance. In fact, it achieves the Cram´er-Rao bound when α = 2 and α = 0+. This new result will be useful when applying stable random projections to distance- based clustering, classiﬁcations, kernels, massive data streams etc.
Continuous Time Particle Filtering for fMRI
Authors: Lawrence Murray, Amos J. Storkey
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We construct a biologically motivated stochastic differential model of the neural and hemodynamic activity underlying the observed Blood Oxygen Level Dependent (BOLD) signal in Functional Magnetic Resonance Imaging (fMRI). The model poses a difficult parameter estimation problem, both theoretically due to the nonlinearity and divergence of the differential system, and computationally due to its time and space complexity. We adapt a particle filter and smoother to the task, and discuss some of the practical approaches used to tackle the difficulties, including use of sparse matrices and parallelisation. Results demonstrate the tractability of the approach in its application to an effective connectivity study.
Computing Robust Counter-Strategies
Authors: Michael Johanson, Martin Zinkevich, Michael Bowling
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Adaptation to other initially unknown agents often requires computing an effective counter-strategy. In the Bayesian paradigm, one must find a good counter-strategy to the inferred posterior of the other agents' behavior. In the experts paradigm, one may want to choose experts that are good counter-strategies to the other agents' expected behavior. In this paper we introduce a technique for computing robust counter-strategies for adaptation in multiagent scenarios under a variety of paradigms. The strategies can take advantage of a suspected tendency in the decisions of the other agents, while bounding the worst-case performance when the tendency is not observed. The technique involves solving a modified game, and therefore can make use of recently developed algorithms for solving very large extensive games. We demonstrate the effectiveness of the technique in two-player Texas Hold'em. We show that the computed poker strategies are substantially more robust than best response counter-strategies, while still exploiting a suspected tendency. We also compose the generated strategies in an experts algorithm showing a dramatic improvement in performance over using simple best responses.
Random Sampling of States in Dynamic Programming
Authors: Chris Atkeson, Benjamin Stephens
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We combine two threads of research on approximate dynamic programming: random sampling of states and using local trajectory optimizers to globally optimize a policy and associated value function. This combination allows us to replace a dense multidimensional grid with a much sparser adaptive sampling of states. Our focus is on finding steady state policies for the deterministic time invariant discrete time control problems with continuous states and actions often found in robotics. In this paper we show that we can now solve problems we couldn't solve previously with regular grid-based approaches.
Predicting human gaze using low-level saliency combined with face detection
Authors: Moran Cerf, Jonathan Harel, Wolfgang Einhaeuser, Christof Koch
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Under natural viewing conditions, human observers shift their gaze to allocate processing resources to subsets of the visual input. Many computational models have aimed at predicting such voluntary attentional shifts. Although the importance of high level stimulus properties (higher order statistics, semantics) stands undisputed, most models are based on low-level features of the input alone. In this study we recorded eye-movements of human observers while they viewed photographs of natural scenes. About two thirds of the stimuli contained at least one person. We demonstrate that a combined model of face detection and low-level saliency clearly outperforms a low-level model in predicting locations humans fixate. This is reflected in our finding fact that observes, even when not instructed to look for anything particular, fixate on a face with a probability of over 80% within their first two fixations (500ms). Remarkably, the model's predictive performance in images that do not contain faces is not impaired by spurious face detector responses, which is suggestive of a bottom-up mechanism for face detection. In summary, we provide a novel computational approach which combines high level object knowledge (in our case: face locations) with low-level features to successfully predict the allocation of attentional resources.
Local Algorithms for Approximate Inference in Minor-Excluded Graphs
Authors: Kyomin Jung, Devavrat Shah
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We present a new local approximation algorithm for computing MAP and log-partition function for arbitrary exponential family distribution represented by a finite-valued pair-wise Markov random field (MRF), say G. Our algorithm is based on decomposing G into appropriately chosen small components; computing estimates locally in each of these components and then producing a good global solution. We prove that the algorithm can provide approximate solution within arbitrary accuracy when $G$ excludes some finite sized graph as its minor and G has bounded degree: all Planar graphs with bounded degree are examples of such graphs. The running time of the algorithm is $\Theta(n)$ (n is the number of nodes in G), with constant dependent on accuracy, degree of graph and size of the graph that is excluded as a minor (constant for Planar graphs). Our algorithm for minor-excluded graphs uses the decomposition scheme of Klein, Plotkin and Rao (1993). In general, our algorithm works with any decomposition scheme and provides quantifiable approximation guarantee that depends on the decomposition scheme.
Estimating divergence functionals and the likelihood ratio by penalized convex risk minimization
Authors: Xuanlong Nguyen, Martin J. Wainwright, Michael I. Jordan
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We develop and analyze an algorithm for nonparametric estimation of divergence functionals and the density ratio of two probability distributions. Our method is based on a variational characterization of f-divergences, which turns the estima- tion into a penalized convex risk minimization problem. We present a derivation of our kernel-based estimation algorithm and an analysis of convergence rates for the estimator. Our simulation results demonstrate the convergence behavior of the method, which compares favorably with existing methods in the literature.
Variational inference for Markov jump processes
Authors: Manfred Opper, Guido Sanguinetti
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Markov jump processes play an important role in a large number of application domains. However, realistic systems are analytically intractable and they have traditionally been analysed using simulation based techniques, which do not provide a framework for statistical inference. We propose a mean field approximation to perform posterior inference and parameter estimation. The approximation allows a practical solution to the inference problem, {while still retaining a good degree of accuracy.} We illustrate our approach on two biologically motivated systems.
Expectation Maximization and Posterior Constraints
Authors: Kuzman Ganchev, Ben Taskar, João Gama
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: The expectation maximization (EM) algorithm is a widely used maximum likelihood estimation procedure for statistical models when the values of some of the variables in the model are not observed. Very often, however, our aim is primarily to find a model that assigns values to the latent variables that have intended meaning for our data and maximizing expected likelihood only sometimes accomplishes this. Unfortunately, it is typically difficult to add even simple a-priori information about latent variables in graphical models without making the models overly complex or intractable. In this paper, we present an efficient, principled way to inject rich constraints on the posteriors of latent variables into the EM algorithm. Our method can be used to learn tractable graphical models that satisfy additional, otherwise intractable constraints. Focusing on clustering and the alignment problem for statistical machine translation, we show that simple, intuitive posterior constraints can greatly improve the performance over standard baselines and be competitive with more complex, intractable models.
Anytime Induction of Cost-sensitive Trees
Authors: Saher Esmeir, Shaul Markovitch
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Machine learning techniques are increasingly being used to produce a wide-range of classiﬁers for complex real-world applications that involve nonuniform testing costs and misclassiﬁcation costs. As the complexity of these applications grows, the management of resources during the learning and classiﬁcation processes be- comes a challenging task. In this work we introduce ACT (Anytime Cost-sensitive Trees), a novel framework for operating in such environments. ACT is an anytime algorithm that allows trading computation time for lower classiﬁcation costs. It builds a tree top-down and exploits additional time resources to obtain better esti- mations for the utility of the different candidate splits. Using sampling techniques ACT approximates for each candidate split the cost of the subtree under it and fa- vors the one with a minimal cost. Due to its stochastic nature ACT is expected to be able to escape local minima, into which greedy methods may be trapped. Ex- periments with a variety of datasets were conducted to compare the performance of ACT to that of the state of the art cost-sensitive tree learners. The results show that for most domains ACT produces trees of signiﬁcantly lower costs. ACT is also shown to exhibit good anytime behavior with diminishing returns.
Optimal ROC Curve for a Combination of Classifiers
Authors: Marco Barreno, Alvaro Cardenas, J. D. Tygar
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We present a new analysis for the combination of binary classifiers. We propose a theoretical framework based on the Neyman-Pearson lemma to analyze combinations of classifiers. In particular, we give a method for finding the optimal decision rule for a combination of classifiers and prove that it has the optimal ROC curve. We also show how our method generalizes and improves on previous work on combining classifiers and generating ROC curves.
On Sparsity and Overcompleteness in Image Models
Authors: Pietro Berkes, Richard Turner, Maneesh Sahani
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Computational models of visual cortex, and in particular those based on sparse coding, have enjoyed much recent attention. Despite this currency, the question of how sparse or how over-complete a sparse representation should be, has gone without principled answer. Here, we use Bayesian model-selection methods to address these questions for a sparse-coding model based on a Student-t prior. Having validated our methods on toy data, we find that natural images are indeed best modelled by extremely sparse distributions; although for the Student-t prior, the associated optimal basis size is only modestly overcomplete.
A Probabilistic Approach to Language Change
Authors: Alexandre Bouchard-côté, Percy Liang, Dan Klein, Thomas L. Griffiths
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We present a probabilistic approach to language change in which word forms are represented by phoneme sequences that undergo stochastic edits along the branches of a phylogenetic tree. Our framework combines the advantages of the classical comparative method with the robustness of corpus-based probabilistic models. We use this framework to explore the consequences of two different schemes for defining probabilistic models of phonological change, evaluating these schemes using the reconstruction of ancient word forms in Romance languages. The result is an efficient inference procedure for automatically inferring ancient word forms from modern languages, which can be generalized to support inferences about linguistic phylogenies.
Learning the 2-D Topology of Images
Authors: Nicolas L. Roux, Yoshua Bengio, Pascal Lamblin, Marc Joliveau, Balázs Kégl
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We study the following question: is the two-dimensional structure of images a very strong prior or is it something that can be learned with a few examples of natural images? If someone gave us a learning task involving images for which the two-dimensional topology of pixels was not known, could we discover it automatically and exploit it? For example suppose that the pixels had been permuted in a fixed but unknown way, could we recover the relative two-dimensional location of pixels on images? The surprising result presented here is that not only the answer is yes but that about as few as a thousand images are enough to approximately recover the relative locations of about a thousand pixels. This is achieved using a manifold learning algorithm applied to pixels associated with a measure of distributional similarity between pixel intensities. We compare different topology-extraction approaches and show how having the two-dimensional topology can be exploited.
A Bayesian LDA-based model for semi-supervised part-of-speech tagging
Authors: Kristina Toutanova, Mark Johnson
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We present a novel Bayesian model for semi-supervised part-of-speech tagging. Our model extends the Latent Dirichlet Allocation model and incorporates the intuition that words’ distributions over tags, p(t|w), are sparse. In addition we in- troduce a model for determining the set of possible tags of a word which captures important dependencies in the ambiguity classes of words. Our model outper- forms the best previously proposed model for this task on a standard dataset.
Cluster Stability for Finite Samples
Authors: Ohad Shamir, Naftali Tishby
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Over the past few years, the notion of stability in data clustering has received growing attention as a cluster validation criterion in a sample-based framework. However, recent work has shown that as the sample size increases, any clustering model will usually become asymptotically stable. This led to the conclusion that stability is lacking as a theoretical and practical tool. The discrepancy between this conclusion and the success of stability in practice has remained an open ques- tion, which we attempt to address. Our theoretical approach is that stability, as used by cluster validation algorithms, is similar in certain respects to measures of generalization in a model-selection framework. In such cases, the model cho- sen governs the convergence rate of generalization bounds. By arguing that these rates are more important than the sample size, we are led to the prediction that stability-based cluster validation algorithms should not degrade with increasing sample size, despite the asymptotic universal stability. This prediction is substan- tiated by a theoretical analysis as well as some empirical results. We conclude that stability remains a meaningful cluster validation criterion over ﬁnite samples.
Variational Inference for Diffusion Processes
Authors: Cédric Archambeau, Manfred Opper, Yuan Shen, Dan Cornford, John S. Shawe-taylor
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Diffusion processes are a family of continuous-time continuous-state stochastic processes that are in general only partially observed. The joint estimation of the forcing parameters and the system noise (volatility) in these dynamical systems is a crucial, but non-trivial task, especially when the system is nonlinear and multi-modal. We propose a variational treatment of diffusion processes, which allows us to estimate these parameters by simple gradient techniques and which is computationally less demanding than most MCMC approaches. Furthermore, our parameter inference scheme does not break down when the time step gets smaller, unlike most current approaches. Finally, we show how a cheap estimate of the posterior over the parameters can be constructed based on the variational free energy.
Augmented Functional Time Series Representation and Forecasting with Gaussian Processes
Authors: Nicolas Chapados, Yoshua Bengio
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We introduce a functional representation of time series which allows forecasts to be performed over an unspeciﬁed horizon with progressively-revealed informa- tion sets. By virtue of using Gaussian processes, a complete covariance matrix between forecasts at several time-steps is available. This information is put to use in an application to actively trade price spreads between commodity futures con- tracts. The approach delivers impressive out-of-sample risk-adjusted returns after transaction costs on a portfolio of 30 spreads.
Sparse Overcomplete Latent Variable Decomposition of Counts Data
Authors: Madhusudana Shashanka, Bhiksha Raj, Paris Smaragdis
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: An important problem in many fields is the analysis of counts data to extract meaningful latent components. Methods like Probabilistic Latent Semantic Analysis (PLSA) and Latent Dirichlet Allocation (LDA) have been proposed for this purpose. However, they are limited in the number of components they can extract and also do not have a provision to control the expressiveness" of the extracted components. In this paper, we present a learning formulation to address these limitations by employing the notion of sparsity. We start with the PLSA framework and use an entropic prior in a maximum a posteriori formulation to enforce sparsity. We show that this allows the extraction of overcomplete sets of latent components which better characterize the data. We present experimental evidence of the utility of such representations."
Modelling motion primitives and their timing in biologically executed movements
Authors: Ben Williams, Marc Toussaint, Amos J. Storkey
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Biological movement is built up of sub-blocks or motion primitives. Such primitives provide a compact representation of movement which is also desirable in robotic control applications. We analyse handwriting data to gain a better understanding of use of primitives and their timings in biological movements. Inference of the shape and the timing of primitives can be done using a factorial HMM based model, allowing the handwriting to be represented in primitive timing space. This representation provides a distribution of spikes corresponding to the primitive activations, which can also be modelled using HMM architectures. We show how the coupling of the low level primitive model, and the higher level timing model during inference can produce good reconstructions of handwriting, with shared primitives for all characters modelled. This coupled model also captures the variance profile of the dataset which is accounted for by spike timing jitter. The timing code provides a compact representation of the movement while generating a movement without an explicit timing model produces a scribbling style of output.
Subspace-Based Face Recognition in Analog VLSI
Authors: Gonzalo Carvajal, Waldo Valenzuela, Miguel Figueroa
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We describe an analog-VLSI neural network for face recognition based on subspace methods. The system uses a dimensionality-reduction network whose coeﬃcients can be either programmed or learned on-chip to per- form PCA, or programmed to perform LDA. A second network with user- programmed coeﬃcients performs classiﬁcation with Manhattan distances. The system uses on-chip compensation techniques to reduce the eﬀects of device mismatch. Using the ORL database with 12x12-pixel images, our circuit achieves up to 85% classiﬁcation performance (98% of an equivalent software implementation).
Efficient multiple hyperparameter learning for log-linear models
Authors: Chuan-sheng Foo, Chuong B. Do, Andrew Y. Ng
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Using multiple regularization hyperparameters is an effective method for managing model complexity in problems where input features have varying amounts of noise. While algorithms for choosing multiple hyperparameters are often used in neural networks and support vector machines, they are not common in structured prediction tasks, such as sequence labeling or parsing. In this paper, we consider the problem of learning regularization hyperparameters for log-linear models, a class of probabilistic models for structured prediction tasks which includes conditional random fields (CRFs). Using an implicit differentiation trick, we derive an efficient gradient-based method for learning Gaussian regularization priors with multiple hyperparameters. In both simulations and the real-world task of computational RNA secondary structure prediction, we find that multiple hyperparameter learning provides a significant boost in accuracy compared to models learned using only a single regularization hyperparameter.
Discovering Weakly-Interacting Factors in a Complex Stochastic Process
Authors: Charlie Frogner, Avi Pfeffer
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Dynamic Bayesian networks are structured representations of stochastic pro- cesses. Despite their structure, exact inference in DBNs is generally intractable. One approach to approximate inference involves grouping the variables in the process into smaller factors and keeping independent beliefs over these factors. In this paper we present several techniques for decomposing a dynamic Bayesian network automatically to enable factored inference. We examine a number of fea- tures of a DBN that capture different types of dependencies that will cause error in factored inference. An empirical comparison shows that the most useful of these is a heuristic that estimates the mutual information introduced between factors by one step of belief propagation. In addition to features computed over entire factors, for efﬁciency we explored scores computed over pairs of variables. We present search methods that use these features, pairwise and not, to ﬁnd a factor- ization, and we compare their results on several datasets. Automatic factorization extends the applicability of factored inference to large, complex models that are undesirable to factor by hand. Moreover, tests on real DBNs show that automatic factorization can achieve signiﬁcantly lower error in some cases.
Stability Bounds for Non-i.i.d. Processes
Authors: Mehryar Mohri, Afshin Rostamizadeh
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: The notion of algorithmic stability has been used effectively in the past to derive tight generalization bounds. A key advantage of these bounds is that they are de- signed for specific learning algorithms, exploiting their particular properties. But, as in much of learning theory, existing stability analyses and bounds apply only in the scenario where the samples are independently and identically distributed (i.i.d.). In many machine learning applications, however, this assumption does not hold. The observations received by the learning algorithm often have some inherent temporal dependence, which is clear in system diagnosis or time series prediction problems. This paper studies the scenario where the observations are drawn from a station- ary beta-mixing sequence, which implies a dependence between observations that weaken over time. It proves novel stability-based generalization bounds that hold even with this more general setting. These bounds strictly generalize the bounds given in the i.i.d. case. We also illustrate their application in the case of several general classes of learning algorithms, including Support Vector Regression and Kernel Ridge Regression.
Evaluating Search Engines by Modeling the Relationship Between Relevance and Clicks
Authors: Ben Carterette, Rosie Jones
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We propose a model that leverages the millions of clicks received by web search engines, to predict document relevance. This allows the comparison of ranking functions when clicks are available but complete relevance judgments are not. After an initial training phase using a set of relevance judgments paired with click data, we show that our model can predict the relevance score of documents that have not been judged. These predictions can be used to evaluate the performance of a search engine, using our novel formalization of the confidence of the standard evaluation metric discounted cumulative gain (DCG), so comparisons can be made across time and datasets. This contrasts with previous methods which can provide only pair-wise relevance judgements between results shown for the same query. When no relevance judgments are available, we can identify the better of two ranked lists up to 82% of the time, and with only two relevance judgments for each query, we can identify the better ranking up to 94% of the time. While our experiments are on sponsored search results, which is the financial backbone of web search, our method is general enough to be applicable to algorithmic web search results as well. Furthermore, we give an algorithm to guide the selection of additional documents to judge to improve confidence.
Efficient Bayesian Inference for Dynamically Changing Graphs
Authors: Ozgur Sumer, Umut Acar, Alexander T. Ihler, Ramgopal R. Mettu
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Motivated by stochastic systems in which observed evidence and conditional de- pendencies between states of the network change over time, and certain quantities of interest (marginal distributions, likelihood estimates etc.) must be updated, we study the problem of adaptive inference in tree-structured Bayesian networks. We describe an algorithm for adaptive inference that handles a broad range of changes to the network and is able to maintain marginal distributions, MAP estimates, and data likelihoods in all expected logarithmic time. We give an implementation of our algorithm and provide experiments that show that the algorithm can yield up to two orders of magnitude speedups on answering queries and responding to dy- namic changes over the sum-product algorithm.
Markov Chain Monte Carlo with People
Authors: Adam Sanborn, Thomas L. Griffiths
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Many formal models of cognition implicitly use subjective probability distributions to capture the assumptions of human learners. Most applications of these models determine these distributions indirectly. We propose a method for directly determining the assumptions of human learners by sampling from subjective probability distributions. Using a correspondence between a model of human choice and Markov chain Monte Carlo (MCMC), we describe a method for sampling from the distributions over objects that people associate with different categories. In our task, subjects choose whether to accept or reject a proposed change to an object. The task is constructed so that these decisions follow an MCMC acceptance rule, defining a Markov chain for which the stationary distribution is the category distribution. We test this procedure for both artificial categories acquired in the laboratory, and natural categories acquired from experience.