OpenRaiser/Intern-Atlas huggingface dataset:
Predictive state representations with options
Authors: Britton Wolfe, Satinder Singh 0001
Venue: ICML
Year: 2006

Recent work on predictive state representation (PSR) models has focused on using predictions of the outcomes of open-loop action sequences as state. These predictions answer questions of the form “What is the probability of seeing observation sequence o1, o2,..., oN if the agent takes action sequence a1, a2,..., aN from some given history?” We would like to ask more expressive questions in our representation of state, such as “If I behave according to some policy until I terminate, what will be my last observation?” We extend the linear PSR framework to answer questions like these about options – temporally extended, closed-loop courses of action – bounding the size of the linear PSR needed to model questions about a certain class of options. We introduce a hierarchical PSR (HPSR) that can make predictions about both options and primitive action sequences and show empirical results from learning HPSRs in simple domains. Existing work with predictive state representations (PSRs) focuses on using predictions about open-loop action sequences as state. These predictions answer questions of the form “What is the probability of seeing observation sequence o1, o2,..., oN if the agent takes action sequence a1, a2,..., aN in some given history?” Littman et al. (2002) showed that predictions of this form are sufficient in that they can perfectly capture state and can be used to make any prediction, i.e., answer any question, about the system. In general, the number of predictions in the state vector grows linearly with the number of underlying or hidden system states and this can be too large for practical purposes. Of course, if one truly wants a
Bayesian multi-population haplotype inference via a hierarchical dirichlet process mixture
Authors: Eric P. Xing, Kyung-Ah Sohn, Michael I. Jordan, Yee Whye Teh
Venue: ICML
Year: 2006

Uncovering the haplotypes of single nucleotide polymorphisms and their population demography is essential for many biological and medical applications. Methods for haplotype inference developed thus far---including methods based on coalescence, finite and infinite mixtures, and maximal parsimony---ignore the underlying population structure in the genotype data. As noted by Pritchard (2001), different populations can share certain portion of their genetic ancestors, as well as have their own genetic components through migration and diversification. In this paper, we address the problem of multi-population haplotype inference. We capture cross-population structure using a nonparametric Bayesian prior known as the hierarchical Dirichlet process (HDP) (Teh et al., 2006), conjoining this prior with a recently developed Bayesian methodology for haplotype phasing known as DP-Haplotyper (Xing et al., 2004). We also develop an efficient sampling algorithm for the HDP based on a two-level nested Pólya urn scheme. We show that our model outperforms extant algorithms on both simulated and real biological data.
Semi-supervised nonlinear dimensionality reduction
Authors: Xin Yang, Haoying Fu, Hongyuan Zha, Jesse L. Barlow
Venue: ICML
Year: 2006

The problem of nonlinear dimensionality reduction is considered. We focus on problems where prior information is available, namely, semi-supervised dimensionality reduction. It is shown that basic nonlinear dimensionality reduction algorithms, such as Locally Linear Embedding (LLE), Isometric feature mapping (ISOMAP), and Local Tangent Space Alignment (LTSA), can be modified by taking into account prior information on exact mapping of certain data points. The sensitivity analysis of our algorithms shows that prior information will improve stability of the solution. We also give some insight on what kind of prior information best improves the solution. We demonstrate the usefulness of our algorithm by synthetic and real life examples. 1.
Null space versus orthogonal linear discriminant analysis
Authors: Jieping Ye, Tao Xiong
Venue: ICML
Year: 2006

Dimensionality reduction is an important pre-processing step for many applications. Linear Discriminant Analysis (LDA) is one of the well known methods for supervised dimensionality reduction. However, the classical LDA formulation requires the nonsingularity of scatter matrices involved. For undersampled problems, where the data dimension is much larger than the sample size, all scatter matrices are singular and classical LDA fails. Many extensions, including null space based LDA (NLDA), orthogonal LDA (OLDA), etc, have been proposed in the past to overcome this problem. In this paper, we present a computational and theoretical analysis of NLDA and OLDA. Our main result shows that under a mild condition which holds in many applications involving high-dimensional data, NLDA is equivalent to OLDA. We have performed extensive experiments on various types of data and results are consistent with our theoretical analysis. The presented analysis and experimental results provide further insight into several LDA based algorithms.
Active learning via transductive experimental design
Authors: Kai Yu 0001, Jinbo Bi, Volker Tresp
Venue: ICML
Year: 2006

This paper considers the problem of selecting the most informative experiments x to get measurements y for learning a regression model y = f(x). We propose a novel and simple concept for active learning, transductive experimental design, that explores available unmeasured experiments (i.e., unlabeled data) and has a better scalability in comparison with classic experimental design methods. Our in-depth analysis shows that the new method tends to favor experiments that are on the one side hard-to-predict and on the other side representative for the rest of the experiments. Efficient optimization of the new design problem is achieved through alternating optimization and sequential greedy search. Extensive experimental results on synthetic problems and three real-world tasks, including questionnaire design for preference learning, active learning for text categorization, and spatial sensor placement, highlight the advantages of the proposed approaches.
Statistical debugging: simultaneous identification of multiple bugs
Authors: Alice X. Zheng, Michael I. Jordan, Ben Liblit, Mayur Naik, Alex Aiken
Venue: ICML
Year: 2006

We describe a statistical approach to software debugging in the presence of multiple bugs. Due to sparse sampling issues and complex interaction between program predicates, many generic off-the-shelf algorithms fail to select useful bug predictors. Taking inspiration from bi-clustering algorithms, we propose an iterative collective voting scheme for the program runs and predicates. We demonstrate successful debugging results on several real world programs and a large debugging benchmark suite.
Efficient lazy elimination for averaged one-dependence estimators
Authors: Fei Zheng 0001, Geoffrey I. Webb
Venue: ICML
Year: 2006

Semi-naive Bayesian classifiers seek to retain the numerous strengths of naive Bayes while reducing error by relaxing the attribute independence assumption. Backwards Sequential Elimination (BSE) is a wrapper technique for attribute elimination that has proved effective at this task. We explore a new technique, Lazy Elimination (LE), which eliminates highly related attribute-values at classification time without the computational overheads inherent in wrapper techniques. We analyze the effect of LE and BSE on a state-of-the-art semi-naive Bayesian algorithm Averaged One-Dependence Estimators (AODE). Our experiments show that LE significantly reduces bias and error without undue computation, while BSE significantly reduces bias but not error, with high training time complexity. In the context of AODE, LE has a significant advantage over BSE in both computational efficiency and error. 1.
Quantum clustering algorithms
Authors: Esma Aïmeur, Gilles Brassard, Sébastien Gambs
Venue: ICML
Year: 2007

By the term "quantization", we refer to the process of using quantum mechanics in order to improve a classical algorithm, usually by making it go faster. In this paper, we initiate the idea of quantizing clustering algorithms by using variations on a celebrated quantum algorithm due to Grover. After having introduced this novel approach to unsupervised learning, we illustrate it with a quantized version of three standard algorithms: divisive clustering, k-medians and an algorithm for the construction of a neighbourhood graph. We obtain a significant speedup compared to the classical approach.
Focused crawling with scalable ordinal regression solvers
Authors: Rashmin Babaria, J. Saketha Nath, S. Krishnan, K. R. Sivaramakrishnan, Chiranjib Bhattacharyya, M. Narasimha Murty
Venue: ICML
Year: 2007

In this paper we propose a novel, scalable, clustering based Ordinal Regression formulation, which is an instance of a Second Order Cone Program (SOCP) with one Second Order Cone (SOC) constraint. The main contribution of the paper is a fast algorithm, CB-OR, which solves the proposed formulation more eficiently than general purpose solvers. Another main contribution of the paper is to pose the problem of focused crawling as a large scale Ordinal Regression problem and solve using the proposed CB-OR. Focused crawling is an efficient mechanism for discovering resources of interest on the web. Posing the problem of focused crawling as an Ordinal Regression problem avoids the need for a negative class and topic hierarchy, which are the main drawbacks of the existing focused crawling methods. Experiments on large synthetic and benchmark datasets show the scalability of CB-OR. Experiments also show that the proposed focused crawler outperforms the state-of-the-art.
Structural alignment based kernels for protein structure classification
Authors: Sourangshu Bhattacharya, Chiranjib Bhattacharyya, Nagasuma R. Chandra
Venue: ICML
Year: 2007

Structural alignments are the most widely used tools for comparing proteins with low sequence similarity. The main contribution of this paper is to derive various kernels on proteins from structural alignments, which do not use sequence information. Central to the kernels is a novel alignment algorithm which matches substructures of fixed size using spectral graph matching techniques. We derive positive semi-definite kernels which capture the notion of similarity between substructures. Using these as base more sophisticated kernels on protein structures are proposed. To empirically evaluate the kernels we used a 40% sequence non-redundant structures from 15 different SCOP superfamilies. The kernels when used with SVMs show competitive performance with CE, a state of the art structure comparison program.
Efficiently computing minimax expected-size confidence regions
Authors: Brent Bryan, H. Brendan McMahan, Chad M. Schafer, Jeff G. Schneider
Venue: ICML
Year: 2007

Given observed data and a collection of parameterized candidate models, a 1 -- α confidence region in parameter space provides useful insight as to those models which are a good fit to the data, all while keeping the probability of incorrect exclusion below α. With complex models, optimally precise procedures (those with small expected size) are, in practice, difficult to derive; one solution is the Minimax Expected-Size (MES) confidence procedure. The key computational problem of MES is computing a minimax equilibria to a certain zero-sum game. We show that this game is convex with bilinear payoffs, allowing us to apply any convex game solver, including linear programming. Exploiting the sparsity of the matrix, along with using fast linear programming software, allows us to compute approximate minimax expected-size confidence regions orders of magnitude faster than previously published methods. We test these approaches by estimating parameters for a cosmological model.
Multiple instance learning for sparse positive bags
Authors: Razvan C. Bunescu, Raymond J. Mooney
Venue: ICML
Year: 2007

We present a new approach to multiple instance learning (MIL) that is particularly effective when the positive bags are sparse (i.e. contain few positive instances). Unlike other SVM-based MIL methods, our approach more directly enforces the desired constraint that at least one of the instances in a positive bag is positive. Using both artificial and real-world data, we experimentally demonstrate that our approach achieves greater accuracy than state-of-the-art MIL methods when positive bags are sparse, and performs competitively when they are not. In particular, our approach is the best performing method for image region classification. 1.
Learning to rank: from pairwise approach to listwise approach
Authors: Zhe Cao, Tao Qin 0001, Tie-Yan Liu, Ming-Feng Tsai, Hang Li 0001
Venue: ICML
Year: 2007

The paper is concerned with learning to rank, which is to construct a model or a function for ranking objects. Learning to rank is useful for document retrieval, collaborative filtering, and many other applications. Several methods for learning to rank have been proposed, which take object pairs as 'instances' in learning. We refer to them as the pairwise approach in this paper. Although the pairwise approach offers advantages, it ignores the fact that ranking is a prediction task on list of objects. The paper postulates that learning to rank should adopt the listwise approach in which lists of objects are used as 'instances' in learning. The paper proposes a new probabilistic method for the approach. Specifically it introduces two probability models, respectively referred to as permutation probability and top k probability, to define a listwise loss function for learning. Neural Network and Gradient Descent are then employed as model and algorithm in the learning method. Experimental results on information retrieval show that the proposed listwise approach performs better than the pairwise approach.
Feature selection in a kernel space
Authors: Bin Cao 0001, Dou Shen, Jian-Tao Sun, Qiang Yang 0001, Zheng Chen 0001
Venue: ICML
Year: 2007

We address the problem of feature selection in a kernel space to select the most discriminative and informative features for classification and data analysis. This is a difficult problem because the dimension of a kernel space may be infinite. In the past, little work has been done on feature selection in a kernel space. To solve this problem, we derive a basis set in the kernel space as a first step for feature selection. Using the basis set, we then extend the margin-based feature selection algorithms that are proven effective even when many features are dependent. The selected features form a subspace of the kernel space, in which different state-of-the-art classification algorithms can be applied for classification. We conduct extensive experiments over real and simulated data to compare our proposed method with four baseline algorithms. Both theoretical analysis and experimental results validate the effectiveness of our proposed method.
Local similarity discriminant analysis
Authors: Luca Cazzanti, Maya R. Gupta
Venue: ICML
Year: 2007

We propose a local, generative model for similarity-based classification. The method is applicable to the case that only pairwise similarities between samples are available. The classifier models the local class-conditional distribution using a maximum entropy estimate and empirical moment constraints. The resulting exponential class conditional-distributions are combined with class prior probabilities and misclassification costs to form the local similarity discriminant analysis (local SDA) classifier. We compare the performance of local SDA to a non-local version, to the local nearest centroid classifier, the nearest centroid classifier, k-NN, and to the recently-developed potential support vector machine (PSVM). Results show that local SDA is competitive with k-NN and the computationally-demanding PSVM while offering the advantages of a generative classifier.
Minimum reference set based feature selection for small sample classifications
Authors: Xue-wen Chen 0001, Jong Cheol Jeong
Venue: ICML
Year: 2007

We address feature selection problems for classification of small samples and high dimensionality. A practical example is microarray-based cancer classification problems, where sample size is typically less than 100 and number of features is several thousands or higher. One of the commonly used methods in addressing this problem is recursive feature elimination (RFE) method, which utilizes the generalization capability embedded in support vector machines and is thus suitable for small samples problems. We propose a novel method using minimum reference set (MRS) generated by the nearest neighbor rule. MRS is the set of minimum number of samples that correctly classify all the training samples. It is related to structural risk minimization principle and thus leads to good generalization. The proposed MRS based method is compared to RFE method with several real datasets, and experimental results show that the MRS method produces better classification performance.
Kernel selection forl semi-supervised kernel machines
Authors: Guang Dai, Dit-Yan Yeung
Venue: ICML
Year: 2007

Existing semi-supervised learning methods are mostly based on either the cluster assumption or the manifold assumption. In this paper, we propose an integrated regularization framework for semi-supervised kernel machines by incorporating both the cluster assumption and the manifold assumption. Moreover, it supports kernel learning in the form of kernel selection. The optimization problem involves joint optimization over all the labeled and unlabeled data points, a convex set of basic kernels, and a discrete space of unknown labels for the unlabeled data. When the manifold assumption is incorporated, graph Laplacian kernels are used as the basic kernels for learning an optimal convex combination of graph Laplacian kernels. Comparison with related methods on the USPS data set shows very promising results.
Boosting for transfer learning
Authors: Wenyuan Dai, Qiang Yang 0001, Gui-Rong Xue, Yong Yu 0001
Venue: ICML
Year: 2007

Traditional machine learning makes a basic assumption: the training and test data should be under the same distribution. However, in many cases, this identical-distribution assumption does not hold. The assumption might be violated when a task from one new domain comes, while there are only labeled data from a similar old domain. Labeling the new data can be costly and it would also be a waste to throw away all the old data. In this paper, we present a novel transfer learning framework called TrAdaBoost, which extends boosting-based learning algorithms (Freund & Schapire, 1997). TrAdaBoost allows users to utilize a small amount of newly labeled data to leverage the old data to construct a high-quality classification model for the new data. We show that this method can allow us to learn an accurate model using only a tiny amount of new data and a large amount of old data, even when the new data are not sufficient to train a model alone. We show that TrAdaBoost allows knowledge to be effectively transferred from the old data to the new. The effectiveness of our algorithm is analyzed theoretically and empirically to show that our iterative algorithm can converge well to an accurate model.
An integrated approach to feature invention and model construction for drug activity prediction
Authors: Jesse Davis, Vítor Santos Costa, Soumya Ray, David Page
Venue: ICML
Year: 2007

We present a new machine learning approach for 3D-QSAR, the task of predicting binding affinities of molecules to target proteins based on 3D structure. Our approach predicts binding affinity by using regression on substructures discovered by relational learning. We make two contributions to the state-of-the-art. First, we use multiple-instance (MI) regression, which represents a molecule as a set of 3D conformations, to model activity. Second, the relational learning component employs the "Score As You Use" (SAYU) method to select substructures for their ability to improve the regression model. This is the first application of SAYU to multiple-instance, real-valued prediction. We evaluate our approach on three tasks and demonstrate that (i) SAYU outperforms standard coverage measures when selecting features for regression, (ii) the MI representation improves accuracy over standard single feature-vector encodings and (iii) combining SAYU with MI regression is more accurate for 3D-QSAR than either approach by itself.
Percentile optimization in uncertain Markov decision processes with application to efficient exploration
Authors: Erick Delage, Shie Mannor
Venue: ICML
Year: 2007

Markov decision processes are an effective tool in modeling decision-making in uncertain dynamic environments. Since the parameters of these models are typically estimated from data, learned from experience, or designed by hand, it is not surprising that the actual performance of a chosen strategy often significantly differs from the designer's initial expectations due to unavoidable model uncertainty. In this paper, we present a percentile criterion that captures the trade-off between optimistic and pessimistic points of view on MDP with parameter uncertainty. We describe tractable methods that take parameter uncertainty into account in the process of decision making. Finally, we propose a cost-effective exploration strategy when it is possible to invest (money, time or computation efforts) in actions that will reduce the uncertainty in the parameters.
Non-isometric manifold learning: analysis and an algorithm
Authors: Piotr Dollár, Vincent C. Rabaud, Serge J. Belongie
Venue: ICML
Year: 2007

In this work we take a novel view of nonlinear manifold learning. Usually, manifold learning is formulated in terms of finding an embedding or 'unrolling' of a manifold into a lower dimensional space. Instead, we treat it as the problem of learning a representation of a nonlinear, possibly non-isometric manifold that allows for the manipulation of novel points. Central to this view of manifold learning is the concept of generalization beyond the training data. Drawing on concepts from supervised learning, we establish a framework for studying the problems of model assessment, model complexity, and model selection for manifold learning. We present an extension of a recent algorithm, Locally Smooth Manifold Learning (LSML), and show it has good generalization properties. LSML learns a representation of a manifold or family of related manifolds and can be used for computing geodesic distances, finding the projection of a point onto a manifold, recovering a manifold from points corrupted by noise, generating novel points on a manifold, and more.
Hierarchical maximum entropy density estimation
Authors: Miroslav Dudík, David M. Blei, Robert E. Schapire
Venue: ICML
Year: 2007

We study the problem of simultaneously estimating several densities where the datasets are organized into overlapping groups, such as a hierarchy. For this problem, we propose a maximum entropy formulation, which systematically incorporates the groups and allows us to share the strength of prediction across similar datasets. We derive general performance guarantees, and show how some previous approaches, such as hierarchical shrinkage and hierarchical priors, can be derived as special cases. We demonstrate the proposed technique on synthetic data and in a real-world application to modeling the geographic distributions of species hierarchically grouped in a taxonomy. Specifically, we model the geographic distributions of species in the Australian wet tropics and Northeast New South Wales. In these regions, small numbers of samples per species significantly hinder effective prediction. Substantial benefits are obtained by combining information across taxonomic groups.