mtybilly/Instruct2DS huggingface dataset:
Transfer Learning using Kolmogorov Complexity: Basic Theory and Empirical Evaluations
Authors: M. M. Mahmud, Sylvian Ray
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: Ping Li, Qiang Wu, Christopher J. Burges
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: Krishnan Kumar, Chiru Bhattacharya, Ramesh Hariharan
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.
Direct Importance Estimation with Model Selection and Its Application to Covariate Shift Adaptation
Authors: Masashi Sugiyama, Shinichi Nakajima, Hisashi Kashima, Paul V. Buenau, Motoaki Kawanabe
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: When training and test samples follow different input distributions (i.e., the situation called \emph{covariate shift}), the maximum likelihood estimator is known to lose its consistency. For regaining consistency, the log-likelihood terms need to be weighted according to the \emph{importance} (i.e., the ratio of test and training input densities). Thus, accurately estimating the importance is one of the key tasks in covariate shift adaptation. A naive approach is to first estimate training and test input densities and then estimate the importance by the ratio of the density estimates. However, since density estimation is a hard problem, this approach tends to perform poorly especially in high dimensional cases. In this paper, we propose a direct importance estimation method that does not require the input density estimates. Our method is equipped with a natural model selection procedure so tuning parameters such as the kernel width can be objectively optimized. This is an advantage over a recently developed method of direct importance estimation. Simulations illustrate the usefulness of our approach.
The Price of Bandit Information for Online Optimization
Authors: Varsha Dani, Sham M. Kakade, Thomas P. Hayes
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: In the online linear optimization problem, a learner must choose, in each round, a decision from a set D ⊂ Rn in order to minimize an (unknown and chang- ing) linear cost function. We present sharp rates of convergence (with respect to additive regret) for both the full information setting (where the cost function is revealed at the end of each round) and the bandit setting (where only the scalar cost incurred is revealed). In particular, this paper is concerned with the price of bandit information, by which we mean the ratio of the best achievable regret √ in the bandit setting to that in the full-information setting. For the full informa- tion case, the upper bound on the regret is O∗( nT ), where n is the ambient √ dimension and T is the time horizon. For the bandit case, we present an algorithm which achieves O∗(n3/2 T ) regret — all previous (nontrivial) bounds here were O(poly(n)T 2/3) or worse. It is striking that the convergence rate for the bandit setting is only a factor of n worse than in the full information case — in stark √ contrast to the K-arm bandit setting, where the gap in the dependence on K is T log K). We also present lower bounds showing that exponential ( this gap is at least n, which we conjecture to be the correct order. The bandit algorithm we present can be implemented efﬁciently in special cases of particular interest, such as path planning and Markov Decision Problems.
Iterative Non-linear Dimensionality Reduction with Manifold Sculpting
Authors: Michael Gashler, Dan Ventura, Tony Martinez
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Many algorithms have been recently developed for reducing dimensionality by projecting data onto an intrinsic non-linear manifold. Unfortunately, existing algo- rithms often lose signiﬁcant precision in this transformation. Manifold Sculpting is a new algorithm that iteratively reduces dimensionality by simulating surface tension in local neighborhoods. We present several experiments that show Man- ifold Sculpting yields more accurate results than existing algorithms with both generated and natural data-sets. Manifold Sculpting is also able to beneﬁt from both prior dimensionality reduction efforts.
Support Vector Machine Classification with Indefinite Kernels
Authors: Ronny Luss, Alexandre D'aspremont
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: In this paper, we propose a method for support vector machine classification using indefinite kernels. Instead of directly minimizing or stabilizing a nonconvex loss function, our method simultaneously finds the support vectors and a proxy kernel matrix used in computing the loss. This can be interpreted as a robust classification problem where the indefinite kernel matrix is treated as a noisy observation of the true positive semidefinite kernel. Our formulation keeps the problem convex and relatively large problems can be solved efficiently using the analytic center cutting plane method. We compare the performance of our technique with other methods on several data sets.
Learning with Transformation Invariant Kernels
Authors: Christian Walder, Olivier Chapelle
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: This paper considers kernels invariant to translation, rotation and dilation. We show that no non-trivial positive deﬁnite (p.d.) kernels exist which are radial and dilation invariant, only conditionally positive deﬁnite (c.p.d.) ones. Accordingly, we discuss the c.p.d. case and provide some novel analysis, including an elemen- tary derivation of a c.p.d. representer theorem. On the practical side, we give a support vector machine (s.v.m.) algorithm for arbitrary c.p.d. kernels. For the thin- plate kernel this leads to a classiﬁer with only one parameter (the amount of regu- larisation), which we demonstrate to be as effective as an s.v.m. with the Gaussian kernel, even though the Gaussian involves a second parameter (the length scale).
A probabilistic model for generating realistic lip movements from speech
Authors: Gwenn Englebienne, Tim Cootes, Magnus Rattray
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: The present work aims to model the correspondence between facial motion and speech. The face and sound are modelled separately, with phonemes being the link between both. We propose a sequential model and evaluate its suitability for the generation of the facial animation from a sequence of phonemes, which we obtain from speech. We evaluate the results both by computing the error between generated sequences and real video, as well as with a rigorous double-blind test with human subjects. Experiments show that our model compares favourably to other existing methods and that the sequences generated are comparable to real video sequences.
Automatic Generation of Social Tags for Music Recommendation
Authors: Douglas Eck, Paul Lamere, Thierry Bertin-mahieux, Stephen Green
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Social tags are user-generated keywords associated with some resource on the Web. In the case of music, social tags have become an important component of Web2.0" recommender systems, allowing users to generate playlists based on use-dependent terms such as "chill" or "jogging" that have been applied to particular songs. In this paper, we propose a method for predicting these social tags directly from MP3 files. Using a set of boosted classifiers, we map audio features onto social tags collected from the Web. The resulting automatic tags (or "autotags") furnish information about music that is otherwise untagged or poorly tagged, allowing for insertion of previously unheard music into a social recommender. This avoids the ''cold-start problem'' common in such systems. Autotags can also be used to smooth the tag space from which similarities and recommendations are made by providing a set of comparable baseline tags for all tracks in a recommender system."
Learning to classify complex patterns using a VLSI network of spiking neurons
Authors: Srinjoy Mitra, Giacomo Indiveri, Stefano Fusi
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We propose a compact, low power VLSI network of spiking neurons which can learn to classify complex patterns of mean ﬁring rates on–line and in real–time. The network of integrate-and-ﬁre neurons is connected by bistable synapses that can change their weight using a local spike–based plasticity mechanism. Learning is supervised by a teacher which provides an extra input to the output neurons during training. The synaptic weights are updated only if the current generated by the plastic synapses does not match the output desired by the teacher (as in the perceptron learning rule). We present experimental results that demonstrate how this VLSI network is able to robustly classify uncorrelated linearly separable spatial patterns of mean ﬁring rates.
Efficient Convex Relaxation for Transductive Support Vector Machine
Authors: Zenglin Xu, Rong Jin, Jianke Zhu, Irwin King, Michael Lyu
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We consider the problem of Support Vector Machine transduction, which involves a combinatorial problem with exponential computational complexity in the number of unlabeled examples. Although several studies are devoted to Transductive SVM, they suffer either from the high computation complexity or from the solutions of local optimum. To address this problem, we propose solving Transductive SVM via a convex relaxation, which converts the NP-hard problem to a semi-definite programming. Compared with the other SDP relaxation for Transductive SVM, the proposed algorithm is computationally more efficient with the number of free parameters reduced from O(n2) to O(n) where n is the number of examples. Empirical study with several benchmark data sets shows the promising performance of the proposed algorithm in comparison with other state-of-the-art implementations of Transductive SVM.
Message Passing for Max-weight Independent Set
Authors: Sujay Sanghavi, Devavrat Shah, Alan S. Willsky
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We investigate the use of message-passing algorithms for the problem of ﬁnding the max-weight independent set (MWIS) in a graph. First, we study the perfor- mance of loopy max-product belief propagation. We show that, if it converges, the quality of the estimate is closely related to the tightness of an LP relaxation of the MWIS problem. We use this relationship to obtain sufﬁcient conditions for correctness of the estimate. We then develop a modiﬁcation of max-product – one that converges to an optimal solution of the dual of the MWIS problem. We also develop a simple iterative algorithm for estimating the max-weight independent set from this dual solution. We show that the MWIS estimate obtained using these two algorithms in conjunction is correct when the graph is bipartite and the MWIS is unique. Finally, we show that any problem of MAP estimation for probability distributions over ﬁnite domains can be reduced to an MWIS problem. We believe this reduction will yield new insights and algorithms for MAP estimation.
Boosting the Area under the ROC Curve
Authors: Phil Long, Rocco Servedio
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We show that any weak ranker that can achieve an area under the ROC curve slightly better than 1/2 (which can be achieved by random guessing) can be efﬁ- ciently boosted to achieve an area under the ROC curve arbitrarily close to 1. We further show that this boosting can be performed even in the presence of indepen- dent misclassiﬁcation noise, given access to a noise-tolerant weak ranker.
Sparse Feature Learning for Deep Belief Networks
Authors: Marc'aurelio Ranzato, Y-lan Boureau, Yann L. Cun
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Unsupervised learning algorithms aim to discover the structure hidden in the data, and to learn representations that are more suitable as input to a supervised machine than the raw input. Many unsupervised methods are based on reconstructing the input from the representation, while constraining the representation to have certain desirable properties (e.g. low dimension, sparsity, etc). Others are based on approximating density by stochastically reconstructing the input from the representation. We describe a novel and efficient algorithm to learn sparse representations, and compare it theoretically and experimentally with a similar machines trained probabilistically, namely a Restricted Boltzmann Machine. We propose a simple criterion to compare and select different unsupervised machines based on the trade-off between the reconstruction error and the information content of the representation. We demonstrate this method by extracting features from a dataset of handwritten numerals, and from a dataset of natural image patches. We show that by stacking multiple levels of such machines and by training sequentially, high-order dependencies between the input variables can be captured.
Receding Horizon Differential Dynamic Programming
Authors: Yuval Tassa, Tom Erez, William D. Smart
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: The control of high-dimensional, continuous, non-linear systems is a key problem in reinforcement learning and control. Local, trajectory-based methods, using techniques such as Differential Dynamic Programming (DDP) are not directly subject to the curse of dimensionality, but generate only local controllers. In this paper, we introduce Receding Horizon DDP (RH-DDP), an extension to the classic DDP algorithm, which allows us to construct stable and robust controllers based on a library of local-control trajectories. We demonstrate the effectiveness of our approach on a series of high-dimensional control problems using a simulated multi-link swimming robot. These experiments show that our approach effectively circumvents dimensionality issues, and is capable of dealing effectively with problems with (at least) 34 state and 14 action dimensions.
A Risk Minimization Principle for a Class of Parzen Estimators
Authors: Kristiaan Pelckmans, Johan Suykens, Bart D. Moor
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: This paper explores the use of a Maximal Average Margin (MAM) optimality principle for the design of learning algorithms. It is shown that the application of this risk minimization principle results in a class of (computationally) simple learning machines similar to the classical Parzen window classifier. A direct relation with the Rademacher complexities is established, as such facilitating analysis and providing a notion of certainty of prediction. This analysis is related to Support Vector Machines by means of a margin transformation. The power of the MAM principle is illustrated further by application to ordinal regression tasks, resulting in an $O(n)$ algorithm able to process large datasets in reasonable time.
Managing Power Consumption and Performance of Computing Systems Using Reinforcement Learning
Authors: Gerald Tesauro, Rajarshi Das, Hoi Chan, Jeffrey Kephart, David Levine, Freeman Rawson, Charles Lefurgy
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Electrical power management in large-scale IT systems such as commercial data- centers is an application area of rapidly growing interest from both an economic and ecological perspective, with billions of dollars and millions of metric tons of CO2 emissions at stake annually. Businesses want to save power without sac- riﬁcing performance. This paper presents a reinforcement learning approach to simultaneous online management of both performance and power consumption. We apply RL in a realistic laboratory testbed using a Blade cluster and dynam- ically varying HTTP workload running on a commercial web applications mid- dleware platform. We embed a CPU frequency controller in the Blade servers’ ﬁrmware, and we train policies for this controller using a multi-criteria reward signal depending on both application performance and CPU power consumption. Our testbed scenario posed a number of challenges to successful use of RL, in- cluding multiple disparate reward functions, limited decision sampling rates, and pathologies arising when using multiple sensor readings as state variables. We describe innovative practical solutions to these challenges, and demonstrate clear performance improvements over both hand-designed policies as well as obvious “cookbook” RL implementations.
A Game-Theoretic Approach to Apprenticeship Learning
Authors: Umar Syed, Robert E. Schapire
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We study the problem of an apprentice learning to behave in an environment with an unknown reward function by observing the behavior of an expert. We follow on the work of Abbeel and Ng [1] who considered a framework in which the true reward function is assumed to be a linear combination of a set of known and observable features. We give a new algorithm that, like theirs, is guaranteed to learn a policy that is nearly as good as the expert's, given enough examples. However, unlike their algorithm, we show that ours may produce a policy that is substantially better than the expert's. Moreover, our algorithm is computationally faster, is easier to implement, and can be applied even in the absence of an expert. The method is based on a game-theoretic view of the problem, which leads naturally to a direct application of the multiplicative-weights algorithm of Freund and Schapire [2] for playing repeated matrix games. In addition to our formal presentation and analysis of the new algorithm, we sketch how the method can be applied when the transition function itself is unknown, and we provide an experimental demonstration of the algorithm on a toy video-game environment.
Scene Segmentation with CRFs Learned from Partially Labeled Images
Authors: Bill Triggs, Jakob J. Verbeek
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Conditional Random Fields (CRFs) are an effective tool for a variety of different data segmentation and labeling tasks including visual scene interpretation, which seeks to partition images into their constituent semantic-level regions and assign appropriate class labels to each region. For accurate labeling it is important to capture the global context of the image as well as local information. We in- troduce a CRF based scene labeling model that incorporates both local features and features aggregated over the whole image or large sections of it. Secondly, traditional CRF learning requires fully labeled datasets which can be costly and troublesome to produce. We introduce a method for learning CRFs from datasets with many unlabeled nodes by marginalizing out the unknown labels so that the log-likelihood of the known ones can be maximized by gradient ascent. Loopy Belief Propagation is used to approximate the marginals needed for the gradi- ent and log-likelihood calculations and the Bethe free-energy approximation to the log-likelihood is monitored to control the step size. Our experimental results show that effective models can be learned from fragmentary labelings and that incorporating top-down aggregate features signiﬁcantly improves the segmenta- tions. The resulting segmentations are compared to the state-of-the-art on three different image datasets.
Measuring Neural Synchrony by Message Passing
Authors: Justin Dauwels, François Vialatte, Tomasz Rutkowski, Andrzej S. Cichocki
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: A novel approach to measure the interdependence of two time series is proposed, referred to as “stochastic event synchrony” (SES); it quantiﬁes the alignment of two point processes by means of the following parameters: time delay, variance of the timing jitter, fraction of “spurious” events, and average similarity of events. SES may be applied to generic one-dimensional and multi-dimensional point pro- cesses, however, the paper mainly focusses on point processes in time-frequency domain. The average event similarity is in that case described by two parameters: the average frequency offset between events in the time-frequency plane, and the variance of the frequency offset (“frequency jitter”); SES then consists of ﬁve pa- rameters in total. Those parameters quantify the synchrony of oscillatory events, and hence, they provide an alternative to existing synchrony measures that quan- tify amplitude or phase synchrony. The pairwise alignment of point processes is cast as a statistical inference problem, which is solved by applying the max- product algorithm on a graphical model. The SES parameters are determined from the resulting pairwise alignment by maximum a posteriori (MAP) estimation. The proposed interdependence measure is applied to the problem of detecting anoma- lies in EEG synchrony of Mild Cognitive Impairment (MCI) patients; the results indicate that SES signiﬁcantly improves the sensitivity of EEG in detecting MCI.
Discriminative Batch Mode Active Learning
Authors: Yuhong Guo, Dale Schuurmans
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Active learning sequentially selects unlabeled instances to label with the goal of reducing the effort needed to learn a good classifier. Most previous studies in active learning have focused on selecting one unlabeled instance at one time while retraining in each iteration. However, single instance selection systems are unable to exploit a parallelized labeler when one is available. Recently a few batch mode active learning approaches have been proposed that select a set of most informative unlabeled instances in each iteration, guided by some heuristic scores. In this paper, we propose a discriminative batch mode active learning approach that formulates the instance selection task as a continuous optimization problem over auxiliary instance selection variables. The optimization is formuated to maximize the discriminative classification performance of the target classifier, while also taking the unlabeled data into account. Although the objective is not convex, we can manipulate a quasi-Newton method to obtain a good local solution. Our empirical studies on UCI datasets show that the proposed active learning is more effective than current state-of-the art batch mode active learning algorithms.
What makes some POMDP problems easy to approximate?
Authors: Wee S. Lee, Nan Rong, David Hsu
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Point-based algorithms have been surprisingly successful in computing approx- imately optimal solutions for partially observable Markov decision processes (POMDPs) in high dimensional belief spaces. In this work, we seek to understand the belief-space properties that allow some POMDP problems to be approximated efﬁciently and thus help to explain the point-based algorithms’ success often ob- served in the experiments. We show that an approximately optimal POMDP so- lution can be computed in time polynomial in the covering number of a reachable belief space, which is the subset of the belief space reachable from a given belief point. We also show that under the weaker condition of having a small covering number for an optimal reachable space, which is the subset of the belief space reachable under an optimal policy, computing an approximately optimal solution is NP-hard. However, given a suitable set of points that “cover” an optimal reach- able space well, an approximate solution can be computed in polynomial time. The covering number highlights several interesting properties that reduce the com- plexity of POMDP planning in practice, e.g., fully observed state variables, beliefs with sparse support, smooth beliefs, and circulant state-transition matrices.
Boosting Algorithms for Maximizing the Soft Margin
Authors: Gunnar Rätsch, Manfred K. Warmuth, Karen A. Glocer
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Gunnar R¨atsch
Friedrich Miescher Laboratory
Max Planck Society T¨ubingen, Germany
We present a novel boosting algorithm, called SoftBoost, designed for sets of bi- nary labeled examples that are not necessarily separable by convex combinations of base hypotheses. Our algorithm achieves robustness by capping the distribu- tions on the examples. Our update of the distribution is motivated by minimizing a relative entropy subject to the capping constraints and constraints on the edges of the obtained base hypotheses. The capping constraints imply a soft margin in the dual optimization problem. Our algorithm produces a convex combination of hypotheses whose soft margin is within δ of its maximum. We employ relative en- tropy projection methods to prove an O( ln N δ2 ) iteration bound for our algorithm, where N is number of examples. We compare our algorithm with other approaches including LPBoost, Brown- Boost, and SmoothBoost. We show that there exist cases where the number of iter- ations required by LPBoost grows linearly in N instead of the logarithmic growth for SoftBoost. In simulation studies we show that our algorithm converges about as fast as LPBoost, faster than BrownBoost, and much faster than SmoothBoost. In a benchmark comparison we illustrate the competitiveness of our approach.
Gaussian Process Models for Link Analysis and Transfer Learning
Authors: Kai Yu, Wei Chu
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: In this paper we develop a Gaussian process (GP) framework to model a collection of reciprocal random variables defined on the \emph{edges} of a network. We show how to construct GP priors, i.e.,~covariance functions, on the edges of directed, undirected, and bipartite graphs. The model suggests an intimate connection between \emph{link prediction} and \emph{transfer learning}, which were traditionally considered two separate research topics. Though a straightforward GP inference has a very high complexity, we develop an efficient learning algorithm that can handle a large number of observations. The experimental results on several real-world data sets verify superior learning capacity.
Near-Maximum Entropy Models for Binary Neural Representations of Natural Images
Authors: Matthias Bethge, Philipp Berens
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Maximum entropy analysis of binary variables provides an elegant way for study- ing the role of pairwise correlations in neural populations. Unfortunately, these approaches suffer from their poor scalability to high dimensions. In sensory cod- ing, however, high-dimensional data is ubiquitous. Here, we introduce a new approach using a near-maximum entropy model, that makes this type of analy- sis feasible for very high-dimensional data—the model parameters can be derived in closed form and sampling is easy. Therefore, our NearMaxEnt approach can serve as a tool for testing predictions from a pairwise maximum entropy model not only for low-dimensional marginals, but also for high dimensional measurements of more than thousand units. We demonstrate its usefulness by studying natural images with dichotomized pixel intensities. Our results indicate that the statistics of such higher-dimensional measurements exhibit additional structure that are not predicted by pairwise correlations, despite the fact that pairwise correlations ex- plain the lower-dimensional marginal statistics surprisingly well up to the limit of dimensionality where estimation of the full joint distribution is feasible.
Privacy-Preserving Belief Propagation and Sampling
Authors: Michael Kearns, Jinsong Tan, Jennifer Wortman
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We provide provably privacy-preserving versions of belief propagation, Gibbs sampling, and other local algorithms — distributed multiparty protocols in which each party or vertex learns only its ﬁnal local value, and absolutely nothing else.
Bayesian Co-Training
Authors: Shipeng Yu, Balaji Krishnapuram, Harald Steck, R. B. Rao, Rómer Rosales
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We propose a Bayesian undirected graphical model for co-training, or more generally for semi-supervised multi-view learning. This makes explicit the previously unstated assumptions of a large class of co-training type algorithms, and also clarifies the circumstances under which these assumptions fail. Building upon new insights from this model, we propose an improved method for co-training, which is a novel co-training kernel for Gaussian process classifiers. The resulting approach is convex and avoids local-maxima problems, unlike some previous multi-view learning methods. Furthermore, it can automatically estimate how much each view should be trusted, and thus accommodate noisy or unreliable views. Experiments on toy data and real world data sets illustrate the benefits of this approach.
Supervised Topic Models
Authors: Jon D. Mcauliffe, David M. Blei
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We introduce supervised latent Dirichlet allocation (sLDA), a statistical model of labelled documents. The model accommodates a variety of response types. We derive a maximum-likelihood procedure for parameter estimation, which relies on variational approximations to handle intractable posterior expectations. Prediction problems motivate this research: we use the fitted model to predict response values for new documents. We test sLDA on two real-world problems: movie ratings predicted from reviews, and web page popularity predicted from text descriptions. We illustrate the benefits of sLDA versus modern regularized regression, as well as versus an unsupervised LDA analysis followed by a separate regression.
A Kernel Statistical Test of Independence
Authors: Arthur Gretton, Kenji Fukumizu, Choon H. Teo, Le Song, Bernhard Schölkopf, Alex J. Smola
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Although kernel measures of independence have been widely applied in machine learning (notably in kernel ICA), there is as yet no method to determine whether they have detected statistically signiﬁcant dependence. We provide a novel test of the independence hypothesis for one particular kernel independence measure, the Hilbert-Schmidt independence criterion (HSIC). The resulting test costs O(m2), where m is the sample size. We demonstrate that this test outperforms established contingency table and functional correlation-based tests, and that this advantage is greater for multivariate data. Finally, we show the HSIC test also applies to text (and to structured data more generally), for which no other independence test presently exists.
Discriminative Keyword Selection Using Support Vector Machines
Authors: Fred Richardson, William M. Campbell
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Many tasks in speech processing involve classification of long term characteristics of a speech segment such as language, speaker, dialect, or topic. A natural technique for determining these characteristics is to first convert the input speech into a sequence of tokens such as words, phones, etc. From these tokens, we can then look for distinctive phrases, keywords, that characterize the speech. In many applications, a set of distinctive keywords may not be known a priori. In this case, an automatic method of building up keywords from short context units such as phones is desirable. We propose a method for construction of keywords based upon Support Vector Machines. We cast the problem of keyword selection as a feature selection problem for n-grams of phones. We propose an alternating filter-wrapper method that builds successively longer keywords. Application of this method on a language recognition task shows that the technique produces interesting and significant qualitative and quantitative results.
Probabilistic Matrix Factorization
Authors: Andriy Mnih, Ruslan Salakhutdinov
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Many existing approaches to collaborative ﬁltering can neither handle very large datasets nor easily deal with users who have very few ratings. In this paper we present the Probabilistic Matrix Factorization (PMF) model which scales linearly with the number of observations and, more importantly, performs well on the large, sparse, and very imbalanced Netﬂix dataset. We further extend the PMF model to include an adaptive prior on the model parameters and show how the model capacity can be controlled automatically. Finally, we introduce a con- strained version of the PMF model that is based on the assumption that users who have rated similar sets of movies are likely to have similar preferences. The result- ing model is able to generalize considerably better for users with very few ratings. When the predictions of multiple PMF models are linearly combined with the predictions of Restricted Boltzmann Machines models, we achieve an error rate of 0.8861, that is nearly 7% better than the score of Netﬂix’s own system.
Density Estimation under Independent Similarly Distributed Sampling Assumptions
Authors: Tony Jebara, Yingbo Song, Kapil Thadani
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: A method is proposed for semiparametric estimation where parametric and non- parametric criteria are exploited in density estimation and unsupervised learning. This is accomplished by making sampling assumptions on a dataset that smoothly interpolate between the extreme of independently distributed (or id) sample data (as in nonparametric kernel density estimators) to the extreme of independent identically distributed (or iid) sample data. This article makes independent simi- larly distributed (or isd) sampling assumptions and interpolates between these two using a scalar parameter. The parameter controls a Bhattacharyya afﬁnity penalty between pairs of distributions on samples. Surprisingly, the isd method maintains certain consistency and unimodality properties akin to maximum likelihood esti- mation. The proposed isd scheme is an alternative for handling nonstationarity in data without making drastic hidden variable assumptions which often make esti- mation difﬁcult and laden with local optima. Experiments in density estimation on a variety of datasets conﬁrm the value of isd over iid estimation, id estimation and mixture modeling.
Efficient Inference for Distributions on Permutations
Authors: Jonathan Huang, Carlos Guestrin, Leonidas Guibas
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Permutations are ubiquitous in many real world problems, such as voting, rankings and data association. Representing uncertainty over permutations is challenging, since there are n! possibilities, and typical compact representations such as graphical models cannot efﬁciently capture the mutual exclusivity con- straints associated with permutations. In this paper, we use the “low-frequency” terms of a Fourier decomposition to represent such distributions compactly. We present Kronecker conditioning, a general and efﬁcient approach for maintaining these distributions directly in the Fourier domain. Low order Fourier-based approximations can lead to functions that do not correspond to valid distributions. To address this problem, we present an efﬁcient quadratic program deﬁned directly in the Fourier domain to project the approximation onto a relaxed form of the marginal polytope. We demonstrate the effectiveness of our approach on a real camera-based multi-people tracking setting.
Fitted Q-iteration in continuous action-space MDPs
Authors: András Antos, Csaba Szepesvári, Rémi Munos
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We consider continuous state, continuous action batch reinforcement learning where the goal is to learn a good policy from a sufficiently rich trajectory generated by another policy. We study a variant of fitted Q-iteration, where the greedy action selection is replaced by searching for a policy in a restricted set of candidate policies by maximizing the average action values. We provide a rigorous theoretical analysis of this algorithm, proving what we believe is the first finite-time bounds for value-function based algorithms for continuous state- and action-space problems.
Blind channel identification for speech dereverberation using l1-norm sparse learning
Authors: Yuanqing Lin, Jingdong Chen, Youngmoo Kim, Daniel D. Lee
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Speech dereverberation remains an open problem after more than three decades of research. The most challenging step in speech dereverberation is blind chan- nel identiﬁcation (BCI). Although many BCI approaches have been developed, their performance is still far from satisfactory for practical applications. The main difﬁculty in BCI lies in ﬁnding an appropriate acoustic model, which not only can effectively resolve solution degeneracies due to the lack of knowledge of the source, but also robustly models real acoustic environments. This paper proposes a sparse acoustic room impulse response (RIR) model for BCI, that is, an acous- tic RIR can be modeled by a sparse FIR ﬁlter. Under this model, we show how to formulate the BCI of a single-input multiple-output (SIMO) system into a l1- norm regularized least squares (LS) problem, which is convex and can be solved efﬁciently with guaranteed global convergence. The sparseness of solutions is controlled by l1-norm regularization parameters. We propose a sparse learning scheme that infers the optimal l1-norm regularization parameters directly from microphone observations under a Bayesian framework. Our results show that the proposed approach is effective and robust, and it yields source estimates in real acoustic environments with high ﬁdelity to anechoic chamber measurements.
Predicting Brain States from fMRI Data: Incremental Functional Principal Component Regression
Authors: Sennay Ghebreab, Arnold Smeulders, Pieter Adriaans
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We propose a method for reconstruction of human brain states directly from functional neuroimaging data. The method extends the traditional multivariate regression analysis of discretized fMRI data to the domain of stochastic functional measurements, facilitating evaluation of brain responses to naturalistic stimuli and boosting the power of functional imaging. The method searches for sets of voxel timecourses that optimize a multivariate functional linear model in terms of Rsquare-statistic. Population based incremental learning is used to search for spatially distributed voxel clusters, taking into account the variation in Haemodynamic lag across brain areas and among subjects by voxel-wise non-linear registration of stimuli to fMRI data. The method captures spatially distributed brain responses to naturalistic stimuli without attempting to localize function. Application of the method for prediction of naturalistic stimuli from new and unknown fMRI data shows that the approach is capable of identifying distributed clusters of brain locations that are highly predictive of a specific stimuli.
Agreement-Based Learning
Authors: Percy Liang, Dan Klein, Michael I. Jordan
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: The learning of probabilistic models with many hidden variables and non- decomposable dependencies is an important and challenging problem. In contrast to traditional approaches based on approximate inference in a single intractable model, our approach is to train a set of tractable submodels by encouraging them to agree on the hidden variables. This allows us to capture non-decomposable aspects of the data while still maintaining tractability. We propose an objective function for our approach, derive EM-style algorithms for parameter estimation, and demonstrate their effectiveness on three challenging real-world learning tasks.
Extending position/phase-shift tuning to motion energy neurons improves velocity discrimination
Authors: Yiu M. Lam, Bertram E. Shi
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We extend position and phase-shift tuning, concepts already well established in the disparity energy neuron literature, to motion energy neurons. We show that Reichardt-like detectors can be considered examples of position tuning, and that motion energy filters whose complex valued spatio-temporal receptive fields are space-time separable can be considered examples of phase tuning. By combining these two types of detectors, we obtain an architecture for constructing motion energy neurons whose center frequencies can be adjusted by both phase and posi- tion shifts. Similar to recently described neurons in the primary visual cortex, these new motion energy neurons exhibit tuning that is between purely space- time separable and purely speed tuned. We propose a functional role for this intermediate level of tuning by demonstrating that comparisons between pairs of these motion energy neurons can reliably discriminate between inputs whose velocities lie above or below a given reference velocity.
Parallelizing Support Vector Machines on Distributed Computers
Authors: Kaihua Zhu, Hao Wang, Hongjie Bai, Jian Li, Zhihuan Qiu, Hang Cui, Edward Y. Chang
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Support Vector Machines (SVMs) suffer from a widely recognized scalability problem in both memory use and computational time. To improve scalability, we have developed a parallel SVM algorithm (PSVM), which reduces memory use through performing a row-based, approximate matrix factorization, and which loads only essential data to each machine to perform parallel computation. Let $n$ denote the number of training instances, $p$ the reduced matrix dimension after factorization ($p$ is significantly smaller than $n$), and $m$ the number of machines. PSVM reduces the memory requirement from $\MO$($n^2$) to $\MO$($np/m$), and improves computation time to $\MO$($np^2/m$). Empirical studies on up to $500$ computers shows PSVM to be effective.
Object Recognition by Scene Alignment
Authors: Bryan Russell, Antonio Torralba, Ce Liu, Rob Fergus, William T. Freeman
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Current object recognition systems can only recognize a limited number of object categories; scaling up to many categories is the next challenge. We seek to build a system to recognize and localize many different object categories in complex scenes. We achieve this through a simple approach: by matching the input im- age, in an appropriate representation, to images in a large training set of labeled images. Due to regularities in object identities across similar scenes, the retrieved matches provide hypotheses for object identities and locations. We build a prob- abilistic model to transfer the labels from the retrieval set to the input image. We demonstrate the effectiveness of this approach and study algorithm component contributions using held-out test sets from the LabelMe database.