We study the problem of maximum entropy density estimation in the presence of known sample selection bias. We propose three bias correction approaches.The first one takes advantage of unbiased sufficient statistics which can be obtained from biased samples. The second one estimates thebiased distribution and then factors the bias out. The third one approximates the second by only using samples from the sampling distribution. Weprovide guarantees for the first two approaches and evaluate the performance of all three approaches in synthetic experiments and on real data from species habitat modeling, where maxent has been successfully appliedand where sample selection bias is a significant problem.

While classical kernel-based learning algorithms are based on a single kernel, in practice it is often desirable to use multiple kernels. Lankriet et al. (2004) considered conic combinations of kernel matrices for classification, leadingto a convex quadratically constraint quadratic program. We show that it can be rewritten as a semi-infinite linear program that can be efficiently solved by recycling the standard SVM implementations. Moreover,we generalize the formulation and our method to a larger class of problems, including regression and one-class classification. Experimentalresults show that the proposed algorithm helps for automatic model selection, improving the interpretability of the learning resultand works for hundred thousands of examples or hundreds of kernels to be combined.

We show how to learn a Mahanalobis distance metric for k-nearest neighbor (kNN)classification by semidefinite programming. The metric is trained with the goal that the k-nearest neighbors always belong to the same class while examples from different classes are separated by a large margin. On seven data sets of varying size and difficulty, we find that metrics trained in this way lead to significant improvements in kNN classification--for example, achieving a test error rate of 1.3% on the MNIST handwritten digits. As in support vector machines (SVMs), the learning problem reduces to a convex optimization based on the hinge loss. Unlike learning in SVMs, however, our framework requires no modification or extension for problems in multiway (as opposed to binary) classification.

In this paper, we provide a general theorem that establishes a correspondence betweensurrogate loss functions in classification and the family of f-divergences. Moreover, we provide constructive procedures for determining the f-divergence induced by a given surrogate loss, and conversely for finding all surrogate loss functions that realize a given f-divergence. Next we introduce the notion of universal equivalence among loss functions and corresponding f-divergences, and provide necessary andsufficient conditions for universal equivalence to hold. These ideas have applications to classification problems that also involve a component ofexperiment design; in particular, we leverage our results to prove consistency of a procedure for learning a classifier under decentralization requirements.

We present a novel spectral clustering method that enables users to incorporate priorknowledge of the size of clusters into the clustering process. The cost function, which is named size regularized cut (SRcut), is defined as the sum of the inter-cluster similarity and a regularization term measuring therelative size of two clusters. Finding a partition of the data set to minimize SRcut is proved to be NPcomplete. An approximation algorithm isproposed to solve a relaxed version of the optimization problem as an eigenvalue problem. Evaluations over different data sets demonstrate thatthe method is not sensitive to outliers and performs better than normalized cut.

Suppose we have a set of training data (ztcl7 yl), . . .

Linear text classification algorithms work by computing an inner product betweena test document vector and a parameter vector. In many such algorithms, including naive Bayes and most TFIDF variants, the parameters aredetermined by some simple, closed-form, function of training set statistics; we call this mapping mapping from statistics to parameters, the parameter function. Much research in text classification over the last few decades has consisted of manual efforts to identify better parameter functions. Inthis paper, we propose an algorithm for automatically learning this function from related classification problems. The parameter function foundby our algorithm then defines a new learning algorithm for text classification, which we can apply to novel classification tasks. We find that our learned classifier outperforms existing methods on a variety of multiclass text classification tasks.

We show that Queyranne's algorithm for minimizing symmetric submodular functionscan be used for clustering with a variety of different objective functions. Two specific criteria that we consider in this paper are the single linkage and the minimum description length criteria. The first criterion triesto maximize the minimum distance between elements of different clusters,and is inherently "discriminative". It is known that optimal clusterings into k clusters for any given k in polynomial time for this criterion can be computed. The second criterion seeks to minimize the description length of the clusters given a probabilistic generative model. We show that the optimal partitioning into 2 clusters, and approximate partitioning (guaranteed to be within a factor of 2 of the the optimal) for more clusters can be computed. To the best of our knowledge, this is the first time that a tractable algorithm for finding the optimal clustering with respect to the MDL criterion for 2 clusters has been given. Besides the optimality result for the MDL criterion, the chief contribution of this paper is to show that the same algorithm can be used to optimize a broad class of criteria, and hence can be used for many application specific criterion for which efficient algorithm are not known.

Fusing multiple information sources can yield significant benefits to successfully accomplishlearning tasks. Many studies have focussed on fusing information in supervised learning contexts. We present an approach to utilize multiple information sources in the form of similarity data for unsupervised learning. Based on similarity information, the clustering task is phrased as a nonnegative matrix factorization problem of a mixture ofsimilarity measurements. The tradeoff between the informativeness ofdata sources and the sparseness of their mixture is controlled by an entropy-based weighting mechanism. For the purpose of model selection, astability-based approach is employed to ensure the selection of the most self-consistent hypothesis. The experiments demonstrate the performance of the method on toy as well as real world data sets.

This activity often manifests itself as dynamically coordinated sequences of action potentials. Since multiple electrode recordings are now a standard tool in neuroscience research, it is important to have a measure of such network-wide behavioral coordinationand information sharing, applicable to multiple neural spike train data. We propose a new statistic, informational coherence, which measures how much better one unit can be predicted by knowing the dynamical state of another. We argue informational coherence is a measure of association and shared information which is superior to traditional pairwisemeasures of synchronization and correlation. To find the dynamical states, we use a recently-introduced algorithm which reconstructs effectivestate spaces from stochastic time series.