mtybilly/Instruct2DS huggingface dataset:
A General Boosting Method and its Application to Learning Ranking Functions for Web Search
Authors: Hongyuan Zha, Tong Zhang, Olivier Chapelle, Keke Chen, Gordon Sun Zhaohui Zheng
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We present a general boosting method extending functional gradient boosting to optimize complex loss functions that are encountered in many machine learning problems. Our approach is based on optimization of quadratic upper bounds of the loss functions which allows us to present a rigorous convergence analysis of the algorithm. More importantly, this general framework enables us to use a standard regression base learner such as decision trees for fitting any loss function. We illustrate an application of the proposed method in learning ranking functions for Web search by combining both preference data and labeled data for training. We present experimental results for Web search using data from a commercial search engine that show significant improvements of our proposed methods over some existing methods.
Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations
Authors: Tommi S. Jaakkola Amir Globerson
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We present a novel message passing algorithm for approximating the MAP problem in graphical models. The algorithm is similar in structure to max-product but unlike max-product it always converges, and can be proven to find the exact MAP solution in various settings. The algorithm is derived via block coordinate descent in a dual of the LP relaxation of MAP, but does not require any tunable parameters such as step size or tree weights. We also describe a generalization of the method to cluster based potentials. The new method is tested on synthetic and real-world problems, and compares favorably with previous approaches.
GRIFT: A graphical model for inferring visual classification features from human data
Authors: Andrew Cohen Michael Ross
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: This paper describes a new model for human visual classification that enables the recovery of image features that explain human subjects' performance on different visual classification tasks. Unlike previous methods, this algorithm does not model their performance with a single linear classifier operating on raw image pixels. Instead, it models classification as the combination of multiple feature detectors. This approach extracts more information about human visual classification than has been previously possible with other methods and provides a foundation for further exploration.
A general agnostic active learning algorithm
Authors: Daniel J. Hsu, Claire Monteleoni Sanjoy Dasgupta
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We present an agnostic active learning algorithm for any hypothesis class of bounded VC dimension under arbitrary data distributions. Most previ- ous work on active learning either makes strong distributional assumptions, or else is computationally prohibitive. Our algorithm extends the simple scheme of Cohn, Atlas, and Ladner [1] to the agnostic setting, using re- ductions to supervised learning that harness generalization bounds in a simple but subtle manner. We provide a fall-back guarantee that bounds the algorithm’s label complexity by the agnostic PAC sample complexity. Our analysis yields asymptotic label complexity improvements for certain hypothesis classes and distributions. We also demonstrate improvements experimentally.
Simplified Rules and Theoretical Analysis for Information Bottleneck Optimization and PCA with Spiking Neurons
Authors: Wolfgang Maass Lars Buesing
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We show that under suitable assumptions (primarily linearization) a simple and perspicuous online learning rule for Information Bottleneck optimization with spiking neurons can be derived. This rule performs on common benchmark tasks as well as a rather complex rule that has previously been proposed \cite{KlampflETAL:07b}. Furthermore, the transparency of this new learning rule makes a theoretical analysis of its convergence properties feasible. A variation of this learning rule (with sign changes) provides a theoretically founded method for performing Principal Component Analysis {(PCA)} with spiking neurons. By applying this rule to an ensemble of neurons, different principal components of the input can be extracted. In addition, it is possible to preferentially extract those principal components from incoming signals $X$ that are related or are not related to some additional target signal $Y_T$. In a biological interpretation, this target signal $Y_T$ (also called relevance variable) could represent proprioceptive feedback, input from other sensory modalities, or top-down signals.
Hidden Common Cause Relations in Relational Learning
Authors: Wei Chu, Zoubin Ghahramani Ricardo Silva
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: When predicting class labels for objects within a relational database, it is often helpful to consider a model for relationships: this allows for information between class labels to be shared and to improve prediction performance. However, there are different ways by which objects can be related within a relational database. One traditional way corresponds to a Markov network structure: each existing relation is represented by an undirected edge. This encodes that, conditioned on input features, each object label is independent of other object labels given its neighbors in the graph. However, there is no reason why Markov networks should be the only representation of choice for symmetric dependence structures. Here we discuss the case when relationships are postulated to exist due to hidden com- mon causes. We discuss how the resulting graphical model differs from Markov networks, and how it describes different types of real-world relational processes. A Bayesian nonparametric classiﬁcation model is built upon this graphical repre- sentation and evaluated with several empirical studies.
Modeling image patches with a directed hierarchy of Markov random fields
Authors: Geoffrey E. Hinton Simon Osindero
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We describe an efficient learning procedure for multilayer generative models that combine the best aspects of Markov random fields and deep, directed belief nets. The generative models can be learned one layer at a time and when learning is complete they have a very fast inference procedure for computing a good approximation to the posterior distribution in all of the hidden layers. Each hidden layer has its own MRF whose energy function is modulated by the top-down directed connections from the layer above. To generate from the model, each layer in turn must settle to equilibrium given its top-down input. We show that this type of model is good at capturing the statistics of patches of natural images.
The Generalized FITC Approximation
Authors: Sean Holden Andrew Naish-guzman
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We present an efﬁcient generalization of the sparse pseudo-input Gaussian pro- cess (SPGP) model developed by Snelson and Ghahramani [1], applying it to binary classiﬁcation problems. By taking advantage of the SPGP prior covari- ance structure, we derive a numerically stable algorithm with O(N M 2) training complexity—asymptotically the same as related sparse methods such as the in- formative vector machine [2], but which more faithfully represents the posterior. We present experimental results for several benchmark problems showing that in many cases this allows an exceptional degree of sparsity without compromis- ing accuracy. Following [1], we locate pseudo-inputs by gradient ascent on the marginal likelihood, but exhibit occasions when this is likely to fail, for which we suggest alternative solutions.
Cooled and Relaxed Survey Propagation for MRFs
Authors: Wee S. Lee, Yee W. Teh Hai L. Chieu
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We describe a new algorithm, Relaxed Survey Propagation (RSP), for ﬁnding MAP conﬁgurations in Markov random ﬁelds. We compare its performance with state-of-the-art algorithms including the max-product belief propagation, its se- quential tree-reweighted variant, residual (sum-product) belief propagation, and tree-structured expectation propagation. We show that it outperforms all ap- proaches for Ising models with mixed couplings, as well as on a web person disambiguation task formulated as a supervised clustering problem.
A Spectral Regularization Framework for Multi-Task Structure Learning
Authors: Massimiliano Pontil, Yiming Ying, Charles A. Micchelli Andreas Argyriou
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Learning the common structure shared by a set of supervised tasks is an important practical and theoretical problem. Knowledge of this structure may lead to bet- ter generalization performance on the tasks and may also facilitate learning new tasks. We propose a framework for solving this problem, which is based on reg- ularization with spectral functions of matrices. This class of regularization prob- lems exhibits appealing computational properties and can be optimized ef(cid:2)ciently by an alternating minimization algorithm. In addition, we provide a necessary and suf(cid:2)cient condition for convexity of the regularizer. We analyze concrete ex- amples of the framework, which are equivalent to regularization with Lp matrix norms. Experiments on two real data sets indicate that the algorithm scales well with the number of tasks and improves on state of the art statistical performance.
CPR for CSPs: A Probabilistic Relaxation of Constraint Propagation
Authors: Luis E. Ortiz
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: This paper proposes constraint propagation relaxation (CPR), a probabilistic approach to classical constraint propagation that provides another view on the whole parametric family of survey propagation algorithms SP(ρ), ranging from belief propagation (ρ = 0) to (pure) survey propagation(ρ = 1). More importantly, the approach elucidates the implicit, but fundamental assumptions underlying SP(ρ), thus shedding some light on its effectiveness and leading to applications beyond k-SAT.
Theoretical Analysis of Learning with Reward-Modulated Spike-Timing-Dependent Plasticity
Authors: Wolfgang Maass, Robert A. Legenstein Dejan Pecevski
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Reward-modulated spike-timing-dependent plasticity (STDP) has recently emerged as a candidate for a learning rule that could explain how local learning rules at single synapses support behaviorally relevant adaptive changes in com- plex networks of spiking neurons. However the potential and limitations of this learning rule could so far only be tested through computer simulations. This ar- ticle provides tools for an analytic treatment of reward-modulated STDP, which allow us to predict under which conditions reward-modulated STDP will be able to achieve a desired learning effect. In particular, we can produce in this way a theoretical explanation and a computer model for a fundamental experimental ﬁnding on biofeedback in monkeys (reported in [1]).
A New View of Automatic Relevance Determination
Authors: Srikantan S. Nagarajan David P. Wipf
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Automatic relevance determination (ARD), and the closely-related sparse Bayesian learning (SBL) framework, are effective tools for pruning large numbers of irrelevant features. However, popular update rules used for this process are either prohibitively slow in practice and/or heuristic in nature without proven convergence properties. This paper furnishes an alternative means of optimizing a general ARD cost function using an auxiliary function that can naturally be solved using a series of re-weighted L1 problems. The result is an efficient algorithm that can be implemented using standard convex programming toolboxes and is guaranteed to converge to a stationary point unlike existing methods. The analysis also leads to additional insights into the behavior of previous ARD updates as well as the ARD cost function. For example, the standard fixed-point updates of MacKay (1992) are shown to be iteratively solving a particular min-max problem, although they are not guaranteed to lead to a stationary point. The analysis also reveals that ARD is exactly equivalent to performing MAP estimation using a particular feature- and noise-dependent \textit{non-factorial} weight prior with several desirable properties over conventional priors with respect to feature selection. In particular, it provides a tighter approximation to the L0 quasi-norm sparsity measure than the L1 norm. Overall these results suggests alternative cost functions and update procedures for selecting features and promoting sparse solutions.
Sequential Hypothesis Testing under Stochastic Deadlines
Authors: Angela J. Yu Peter Frazier
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Most models of decision-making in neuroscience assume an inﬁnite horizon, which yields an optimal solution that integrates evidence up to a ﬁxed decision threshold; however, under most experimental as well as naturalistic behavioral settings, the decision has to be made before some ﬁnite deadline, which is often experienced as a stochastic quantity, either due to variable external constraints or internal timing uncertainty. In this work, we formulate this problem as sequential hypothesis testing under a stochastic horizon. We use dynamic programming tools to show that, for a large class of deadline distributions, the Bayes-optimal solution requires integrating evidence up to a threshold that declines monotonically over time. We use numerical simulations to illustrate the optimal policy in the special cases of a ﬁxed deadline and one that is drawn from a gamma distribution.
Discriminative Log-Linear Grammars with Latent Variables
Authors: Dan Klein Slav Petrov
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We demonstrate that log-linear grammars with latent variables can be practically trained using discriminative methods. Central to efﬁcient discriminative training is a hierarchical pruning procedure which allows feature expectations to be efﬁ- ciently approximated in a gradient-based procedure. We compare L1 and L2 reg- ularization and show that L1 regularization is superior, requiring fewer iterations to converge, and yielding sparser solutions. On full-scale treebank parsing exper- iments, the discriminative latent models outperform both the comparable genera- tive latent models as well as the discriminative non-latent baselines.
HM-BiTAM: Bilingual Topic Exploration, Word Alignment, and Translation
Authors: Eric P. Xing Bing Zhao
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We present a novel paradigm for statistical machine translation (SMT), based on joint modeling of word alignment and the topical aspects underlying bilingual document pairs via a hidden Markov Bilingual Topic AdMixture (HM-BiTAM). In this new paradigm, parallel sentence-pairs from a parallel document-pair are coupled via a certain semantic-flow, to ensure coherence of topical context in the alignment of matching words between languages, during likelihood-based training of topic-dependent translational lexicons, as well as topic representations in each language. The resulting trained HM-BiTAM can not only display topic patterns like other methods such as LDA, but now for bilingual corpora; it also offers a principled way of inferring optimal translation in a context-dependent way. Our method integrates the conventional IBM Models based on HMM --- a key component for most of the state-of-the-art SMT systems, with the recently proposed BiTAM model, and we report an extensive empirical analysis (in many way complementary to the description-oriented of our method in three aspects: word alignment, bilingual topic representation, and translation.
Optimistic Linear Programming gives Logarithmic Regret for Irreducible MDPs
Authors: Peter L. Bartlett Ambuj Tewari
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We present an algorithm called Optimistic Linear Programming (OLP) for learning to optimize average reward in an irreducible but otherwise unknown Markov decision process (MDP). OLP uses its experience so far to estimate the MDP. It chooses actions by optimistically maximizing estimated future rewards over a set of next-state transition probabilities that are close to the estimates: a computation that corresponds to solving linear programs. We show that the total expected reward obtained by OLP up to time $T$ is within $C(P)\log T$ of the reward obtained by the optimal policy, where $C(P)$ is an explicit, MDP-dependent constant. OLP is closely related to an algorithm proposed by Burnetas and Katehakis with four key differences: OLP is simpler, it does not require knowledge of the supports of transition probabilities and the proof of the regret bound is simpler, but our regret bound is a constant factor larger than the regret of their algorithm. OLP is also similar in flavor to an algorithm recently proposed by Auer and Ortner. But OLP is simpler and its regret bound has a better dependence on the size of the MDP.
TrueSkill Through Time: Revisiting the History of Chess
Authors: Ralf Herbrich, Tom Minka, Thore Graepel Pierre Dangauthier
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We extend the Bayesian skill rating system TrueSkill to infer entire time series of skills of players by smoothing through time instead of (cid:12)ltering. The skill of each participating player, say, every year is represented by a latent skill variable which is a(cid:11)ected by the relevant game outcomes that year, and coupled with the skill variables of the previous and subsequent year. Inference in the resulting factor graph is carried out by approximate message passing (EP) along the time series of skills. As before the system tracks the uncertainty about player skills, explicitly models draws, can deal with any number of competing entities and can infer individual skills from team results. We extend the system to estimate player-speci(cid:12)c draw mar- gins. Based on these models we present an analysis of the skill curves of important players in the history of chess over the past 150 years. Results include plots of players’ lifetime skill development as well as the ability to compare the skills of di(cid:11)erent players across time. Our results indicate that a) the overall playing strength has increased over the past 150 years, and b) that modelling a player’s ability to force a draw provides signi(cid:12)cantly better predictive power.
Topmoumoute Online Natural Gradient Algorithm
Authors: Pierre-antoine Manzagol, Yoshua Bengio Nicolas L. Roux
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Guided by the goal of obtaining an optimization algorithm that is both fast and yielding good generalization, we study the descent direction maximizing the decrease in generalization error or the probability of not increasing generalization error. The surprising result is that from both the Bayesian and frequentist perspectives this can yield the natural gradient direction. Although that direction can be very expensive to compute we develop an efficient, general, online approximation to the natural gradient descent which is suited to large scale problems. We report experimental results showing much faster convergence in computation time and in number of iterations with TONGA (Topmoumoute Online natural Gradient Algorithm) than with stochastic gradient descent, even on very large datasets.
Learning Monotonic Transformations for Classification
Authors: Tony Jebara Andrew Howard
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: A discriminative method is proposed for learning monotonic transforma- tions of the training data while jointly estimating a large-margin classi(cid:12)er. In many domains such as document classi(cid:12)cation, image histogram classi(cid:12)- cation and gene microarray experiments, (cid:12)xed monotonic transformations can be useful as a preprocessing step. However, most classi(cid:12)ers only explore these transformations through manual trial and error or via prior domain knowledge. The proposed method learns monotonic transformations auto- matically while training a large-margin classi(cid:12)er without any prior knowl- edge of the domain. A monotonic piecewise linear function is learned which transforms data for subsequent processing by a linear hyperplane classi(cid:12)er. Two algorithmic implementations of the method are formalized. The (cid:12)rst solves a convergent alternating sequence of quadratic and linear programs until it obtains a locally optimal solution. An improved algorithm is then derived using a convex semide(cid:12)nite relaxation that overcomes initializa- tion issues in the greedy optimization problem. The e(cid:11)ectiveness of these learned transformations on synthetic problems, text data and image data is demonstrated.
Combined discriminative and generative articulated pose and non-rigid shape estimation
Authors: Alexandru Balan, Michael J. Black Leonid Sigal
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Estimation of three-dimensional articulated human pose and motion from images is a central problem in computer vision. Much of the previous work has been limited by the use of crude generative models of humans represented as articu- lated collections of simple parts such as cylinders. Automatic initialization of such models has proved difﬁcult and most approaches assume that the size and shape of the body parts are known a priori. In this paper we propose a method for automatically recovering a detailed parametric model of non-rigid body shape and pose from monocular imagery. Speciﬁcally, we represent the body using a param- eterized triangulated mesh model that is learned from a database of human range scans. We demonstrate a discriminative method to directly recover the model pa- rameters from monocular images using a conditional mixture of kernel regressors. This predicted pose and shape are used to initialize a generative model for more detailed pose and shape estimation. The resulting approach allows fully automatic pose and shape recovery from monocular and multi-camera imagery. Experimen- tal results show that our method is capable of robustly recovering articulated pose, shape and biometric measurements (e.g. height, weight, etc.) in both calibrated and uncalibrated camera environments.
Multiple-Instance Active Learning
Authors: Mark Craven, Soumya Ray Burr Settles
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: In a multiple instance (MI) learning problem, instances are naturally organized into bags and it is the bags, instead of individual instances, that are labeled for training. MI learners assume that every instance in a bag labeled negative is actually negative, whereas at least one instance in a bag labeled positive is actually positive. We present a framework for active learning in the multiple-instance setting. In particular, we consider the case in which an MI learner is allowed to selectively query unlabeled instances in positive bags. This approach is well motivated in domains in which it is inexpensive to acquire bag labels and possible, but expensive, to acquire instance labels. We describe a method for learning from labels at mixed levels of granularity, and introduce two active query selection strategies motivated by the MI setting. Our experiments show that learning from instance labels can significantly improve performance of a basic MI learning algorithm in two multiple-instance domains: content-based image recognition and text classification.
Semi-Supervised Multitask Learning
Authors: Xuejun Liao, Lawrence Carin Qiuhua Liu
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: A semi-supervised multitask learning (MTL) framework is presented, in which M parameterized semi-supervised classiﬁers, each associated with one of M par- tially labeled data manifolds, are learned jointly under the constraint of a soft- sharing prior imposed over the parameters of the classiﬁers. The unlabeled data are utilized by basing classiﬁer learning on neighborhoods, induced by a Markov random walk over a graph representation of each manifold. Experimental results on real data sets demonstrate that semi-supervised MTL yields signiﬁcant im- provements in generalization performance over either semi-supervised single-task learning (STL) or supervised MTL.
Contraction Properties of VLSI Cooperative Competitive Neural Networks of Spiking Neurons
Authors: Elisabetta Chicca, Giacomo Indiveri, Jean-jeacques Slotine, Rodney J. Douglas Emre Neftci
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: A non–linear dynamic system is called contracting if initial conditions are for- gotten exponentially fast, so that all trajectories converge to a single trajectory. We use contraction theory to derive an upper bound for the strength of recurrent connections that guarantees contraction for complex neural networks. Speciﬁ- cally, we apply this theory to a special class of recurrent networks, often called Cooperative Competitive Networks (CCNs), which are an abstract representation of the cooperative-competitive connectivity observed in cortex. This speciﬁc type of network is believed to play a major role in shaping cortical responses and se- lecting the relevant signal among distractors and noise. In this paper, we analyze contraction of combined CCNs of linear threshold units and verify the results of our analysis in a hybrid analog/digital VLSI CCN comprising spiking neurons and dynamic synapses.
Mining Internet-Scale Software Repositories
Authors: Paul Rigor, Sushil Bajracharya, Cristina Lopes, Pierre F. Baldi Erik Linstead
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Large repositories of source code create new challenges and opportunities for statistical machine learning. Here we first develop an infrastructure for the automated crawling, parsing, and database storage of open source software. The infrastructure allows us to gather Internet-scale source code. For instance, in one experiment, we gather 4,632 java projects from SourceForge and Apache totaling over 38 million lines of code from 9,250 developers. Simple statistical analyses of the data first reveal robust power-law behavior for package, SLOC, and method call distributions. We then develop and apply unsupervised author-topic, probabilistic models to automatically discover the topics embedded in the code and extract topic-word and author-topic distributions. In addition to serving as a convenient summary for program function and developer activities, these and other related distributions provide a statistical and information-theoretic basis for quantifying and analyzing developer similarity and competence, topic scattering, and document tangling, with direct applications to software engineering. Finally, by combining software textual content with structural information captured by our CodeRank approach, we are able to significantly improve software retrieval performance, increasing the AUC metric to 0.86-- roughly 10-30% better than previous approaches based on text alone.
Optimal models of sound localization by barn owls
Authors: Brian J. Fischer
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Sound localization by barn owls is commonly modeled as a matching procedure where localization cues derived from auditory inputs are compared to stored templates. While the matching models can explain properties of neural responses, no model explains how the owl resolves spatial ambiguity in the localization cues to produce accurate localization near the center of gaze. Here, we examine two models for the barn owl's sound localization behavior. First, we consider a maximum likelihood estimator in order to further evaluate the cue matching model. Second, we consider a maximum a posteriori estimator to test if a Bayesian model with a prior that emphasizes directions near the center of gaze can reproduce the owl's localization behavior. We show that the maximum likelihood estimator can not reproduce the owl's behavior, while the maximum a posteriori estimator is able to match the behavior. This result suggests that the standard cue matching model will not be sufficient to explain sound localization behavior in the barn owl. The Bayesian model provides a new framework for analyzing sound localization in the barn owl and leads to predictions about the owl's localization behavior.
Discriminative K-means for Clustering
Authors: Zheng Zhao, Mingrui Wu Jieping Ye
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We present a theoretical study on the discriminative clustering framework, recently proposed for simultaneous subspace selection via linear discriminant analysis (LDA) and clustering. Empirical results have shown its favorable performance in comparison with several other popular clustering algorithms. However, the inherent relationship between subspace selection and clustering in this framework is not well understood, due to the iterative nature of the algorithm. We show in this paper that this iterative subspace selection and clustering is equivalent to kernel K-means with a specific kernel Gram matrix. This provides significant and new insights into the nature of this subspace selection procedure. Based on this equivalence relationship, we propose the Discriminative K-means (DisKmeans) algorithm for simultaneous LDA subspace selection and clustering, as well as an automatic parameter estimation procedure. We also present the nonlinear extension of DisKmeans using kernels. We show that the learning of the kernel matrix over a convex set of pre-specified kernel matrices can be incorporated into the clustering formulation. The connection between DisKmeans and several other clustering algorithms is also analyzed. The presented theories and algorithms are evaluated through experiments on a collection of benchmark data sets.
Heterogeneous Component Analysis
Authors: Motoaki Kawanabe, Klaus-Robert Müller, Shin Ishii Shigeyuki Oba
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: In bioinformatics it is often desirable to combine data from various measurement sources and thus structured feature vectors are to be analyzed that possess different intrinsic blocking characteristics (e.g., different patterns of missing values, obser- vation noise levels, effective intrinsic dimensionalities). We propose a new ma- chine learning tool, heterogeneous component analysis (HCA), for feature extrac- tion in order to better understand the factors that underlie such complex structured heterogeneous data. HCA is a linear block-wise sparse Bayesian PCA based not only on a probabilistic model with block-wise residual variance terms but also on a Bayesian treatment of a block-wise sparse factor-loading matrix. We study vari- ous algorithms that implement our HCA concept extracting sparse heterogeneous structure by obtaining common components for the blocks and speciﬁc compo- nents within each block. Simulations on toy and bioinformatics data underline the usefulness of the proposed structured matrix factorization concept.
An Analysis of Inference with the Universum
Authors: Alekh Agarwal, Fabian H. Sinz, Bernhard Schölkopf Olivier Chapelle
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We study a pattern classiﬁcation algorithm which has recently been proposed by Vapnik and coworkers. It builds on a new inductive principle which assumes that in addition to positive and negative data, a third class of data is available, termed the Universum. We assay the behavior of the algorithm by establishing links with Fisher discriminant analysis and oriented PCA, as well as with an SVM in a pro- jected subspace (or, equivalently, with a data-dependent reduced kernel). We also provide experimental results.
Exponential Family Predictive Representations of State
Authors: Satinder S. Baveja David Wingate
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: In order to represent state in controlled, partially observable, stochastic dynamical systems, some sort of sufﬁcient statistic for history is necessary. Predictive repre- sentations of state (PSRs) capture state as statistics of the future. We introduce a new model of such systems called the “Exponential family PSR,” which deﬁnes as state the time-varying parameters of an exponential family distribution which models n sequential observations in the future. This choice of state representation explicitly connects PSRs to state-of-the-art probabilistic modeling, which allows us to take advantage of current efforts in high-dimensional density estimation, and in particular, graphical models and maximum entropy models. We present a pa- rameter learning algorithm based on maximum likelihood, and we show how a variety of current approximate inference methods apply. We evaluate the qual- ity of our model with reinforcement learning by directly evaluating the control performance of the model.
One-Pass Boosting
Authors: Phil Long, Rocco Servedio Zafer Barutcuoglu
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: This paper studies boosting algorithms that make a single pass over a set of base classi(cid:2)ers. We (cid:2)rst analyze a one-pass algorithm in the setting of boosting with diverse base classi(cid:2)ers. Our guarantee is the same as the best proved for any boosting algo- rithm, but our one-pass algorithm is much faster than previous approaches. We next exhibit a random source of examples for which a (cid:147)picky(cid:148) variant of Ad- aBoost that skips poor base classi(cid:2)ers can outperform the standard AdaBoost al- gorithm, which uses every base classi(cid:2)er, by an exponential factor. Experiments with Reuters and synthetic data show that one-pass boosting can sub- stantially improve on the accuracy of Naive Bayes, and that picky boosting can sometimes lead to a further improvement in accuracy.
The Value of Labeled and Unlabeled Examples when the Model is Imperfect
Authors: Mikhail Belkin Kaushik Sinha
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Semi-supervised learning, i.e. learning from both labeled and unlabeled data has received signi(cid:2)cant attention in the machine learning literature in recent years. Still our understanding of the theoretical foundations of the usefulness of unla- beled data remains somewhat limited. The simplest and the best understood sit- uation is when the data is described by an identi(cid:2)able mixture model, and where each class comes from a pure component. This natural setup and its implications ware analyzed in [11, 5]. One important result was that in certain regimes, labeled data becomes exponentially more valuable than unlabeled data. However, in most realistic situations, one would not expect that the data comes from a parametric mixture distribution with identi(cid:2)able components. There have been recent efforts to analyze the non-parametric situation, for example, (cid:147)cluster(cid:148) and (cid:147)manifold(cid:148) assumptions have been suggested as a basis for analysis. Still, a satisfactory and fairly complete theoretical understanding of the nonparametric problem, similar to that in [11, 5] has not yet been developed. In this paper we investigate an intermediate situation, when the data comes from a probability distribution, which can be modeled, but not perfectly, by an identi(cid:2)able mixture distribution. This seems applicable to many situation, when, for example, a mixture of Gaussians is used to model the data. the contribution of this paper is an analysis of the role of labeled and unlabeled data depending on the amount of imperfection in the model.
On higher-order perceptron algorithms
Authors: Fabio Vitale, Cristian Brotto Claudio Gentile
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: A new algorithm for on-line learning linear-threshold functions is proposed which efficiently combines second-order statistics about the data with the logarithmic behavior" of multiplicative/dual-norm algorithms. An initial theoretical analysis is provided suggesting that our algorithm might be viewed as a standard Perceptron algorithm operating on a transformed sequence of examples with improved margin properties. We also report on experiments carried out on datasets from diverse domains, with the goal of comparing to known Perceptron algorithms (first-order, second-order, additive, multiplicative). Our learning procedure seems to generalize quite well, and converges faster than the corresponding multiplicative baseline algorithms."
Fast Variational Inference for Large-scale Internet Diagnosis
Authors: David Maltz, John C. Platt Emre Kiciman
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Web servers on the Internet need to maintain high reliability, but the cause of intermittent failures of web transactions is non-obvious. We use Bayesian inference to diagnose problems with web services. This diagnosis problem is far larger than any previously attempted: it requires inference of 10^4 possible faults from 10^5 observations. Further, such inference must be performed in less than a second. Inference can be done at this speed by combining a variational approximation, a mean-field approximation, and the use of stochastic gradient descent to optimize a variational cost function. We use this fast inference to diagnose a time series of anomalous HTTP requests taken from a real web service. The inference is fast enough to analyze network logs with billions of entries in a matter of hours.
The Infinite Markov Model
Authors: Eiichiro Sumita Daichi Mochihashi
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We present a nonparametric Bayesian method of estimating variable order Markov processes up to a theoretically inﬁnite order. By extending a stick-breaking prior, which is usually deﬁned on a unit interval, “vertically” to the trees of inﬁnite depth associated with a hierarchical Chinese restaurant process, our model directly infers the hidden orders of Markov dependencies from which each symbol originated. Experiments on character and word sequences in natural language showed that the model has a comparative performance with an exponentially large full-order model, while computationally much efﬁcient in both time and space. We expect that this basic model will also extend to the variable order hierarchical clustering of general data.
Retrieved context and the discovery of semantic structure
Authors: Marc Howard Vinayak Rao
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Semantic memory refers to our knowledge of facts and relationships between con- cepts. A successful semantic memory depends on inferring relationships between items that are not explicitly taught. Recent mathematical modeling of episodic memory argues that episodic recall relies on retrieval of a gradually-changing rep- resentation of temporal context. We show that retrieved context enables the de- velopment of a global memory space that reﬂects relationships between all items that have been previously learned. When newly-learned information is integrated into this structure, it is placed in some relationship to all other items, even if that relationship has not been explicitly learned. We demonstrate this effect for global semantic structures shaped topologically as a ring, and as a two-dimensional sheet. We also examined the utility of this learning algorithm for learning a more realistic semantic space by training it on a large pool of synonym pairs. Retrieved context enabled the model to “infer” relationships between synonym pairs that had not yet been presented.
Active Preference Learning with Discrete Choice Data
Authors: Nando D. Freitas, Abhijeet Ghosh Brochu Eric
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We propose an active learning algorithm that learns a continuous valuation model from discrete preferences. The algorithm automatically decides what items are best presented to an individual in order to find the item that they value highly in as few trials as possible, and exploits quirks of human psychology to minimize time and cognitive burden. To do this, our algorithm maximizes the expected improvement at each query without accurately modelling the entire valuation surface, which would be needlessly expensive. The problem is particularly difficult because the space of choices is infinite. We demonstrate the effectiveness of the new algorithm compared to related active learning methods. We also embed the algorithm within a decision making tool for assisting digital artists in rendering materials. The tool finds the best parameters while minimizing the number of queries.
Bayesian binning beats approximate alternatives: estimating peri-stimulus time histograms
Authors: Mike Oram, Johannes Schindelin, Peter Foldiak Dominik Endres
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: The peristimulus time historgram (PSTH) and its more continuous cousin, the spike density function (SDF) are staples in the analytic toolkit of neurophysiologists. The former is usually obtained by binning spiketrains, whereas the standard method for the latter is smoothing with a Gaussian kernel. Selection of a bin with or a kernel size is often done in an relatively arbitrary fashion, even though there have been recent attempts to remedy this situation \cite{ShimazakiBinningNIPS2006,ShimazakiBinningNECO2007}. We develop an exact Bayesian, generative model approach to estimating PSHTs and demonstate its superiority to competing methods. Further advantages of our scheme include automatic complexity control and error bars on its predictions.
Online Linear Regression and Its Application to Model-Based Reinforcement Learning
Authors: Michael L. Littman Alexander L. Strehl
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We provide a provably efficient algorithm for learning Markov Decision Processes (MDPs) with continuous state and action spaces in the online setting. Specifically, we take a model-based approach and show that a special type of online linear regression allows us to learn MDPs with (possibly kernalized) linearly parameterized dynamics. This result builds on Kearns and Singh's work that provides a provably efficient algorithm for finite state MDPs. Our approach is not restricted to the linear setting, and is applicable to other classes of continuous MDPs.
Transfer Learning using Kolmogorov Complexity: Basic Theory and Empirical Evaluations
Authors: Sylvian Ray M. M. Mahmud
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: In transfer learning we aim to solve new problems using fewer examples using information gained from solving related problems. Transfer learning has been successful in practice, and extensive PAC analysis of these methods has been de- veloped. However it is not yet clear how to deﬁne relatedness between tasks. This is considered as a major problem as it is conceptually troubling and it makes it unclear how much information to transfer and when and how to transfer it. In this paper we propose to measure the amount of information one task contains about another using conditional Kolmogorov complexity between the tasks. We show how existing theory neatly solves the problem of measuring relatedness and transferring the ‘right’ amount of information in sequential transfer learning in a Bayesian setting. The theory also suggests that, in a very formal and precise sense, no other reasonable transfer method can do much better than our Kolmogorov Complexity theoretic transfer method, and that sequential transfer is always justi- ﬁed. We also develop a practical approximation to the method and use it to transfer information between 8 arbitrarily chosen databases from the UCI ML repository.
McRank: Learning to Rank Using Multiple Classification and Gradient Boosting
Authors: Qiang Wu, Christopher J. Burges Ping Li
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We cast the ranking problem as (1) multiple classiﬁcation (“Mc”) (2) multiple or- dinal classiﬁcation, which lead to computationally tractable learning algorithms for relevance ranking in Web search. We consider the DCG criterion (discounted cumulative gain), a standard quality measure in information retrieval. Our ap- proach is motivated by the fact that perfect classiﬁcations result in perfect DCG scores and the DCG errors are bounded by classiﬁcation errors. We propose us- ing the Expected Relevance to convert class probabilities into ranking scores. The class probabilities are learned using a gradient boosting tree algorithm. Evalua- tions on large-scale datasets show that our approach can improve LambdaRank [5] and the regressions-based ranker [6], in terms of the (normalized) DCG scores. An efﬁcient implementation of the boosting tree algorithm is also presented.
A Randomized Algorithm for Large Scale Support Vector Learning
Authors: Chiru Bhattacharya, Ramesh Hariharan Krishnan Kumar
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We propose a randomized algorithm for large scale SVM learning which solves the problem by iterating over random subsets of the data. Crucial to the algorithm for scalability is the size of the subsets chosen. In the context of text classification we show that, by using ideas from random projections, a sample size of O(log n) can be used to obtain a solution which is close to the optimal with a high probability. Experiments done on synthetic and real life data sets demonstrate that the algorithm scales up SVM learners, without loss in accuracy.