@inproceedings{BenDavid:EtAl:08, title = {Does unlabeled data provably help? Worst-case analysis of the sample complexity of semi-supervised learning}, address = {Helsinki, Finland}, author = {Shai Ben-David and Tyler Lu and Dávid Pál}, booktitle = {Proceedings of the The 21st Annual Conference on Learning Theory (COLT-08)}, year = 2008, url = {http://www.cs.uwaterloo.ca/~dpal/papers/ssl/ssl.pdf}, biburl = {http://www.bibsonomy.org/bibtex/28da77eaeb242315faa2e0c589bd4e1a1/seandalai}, keywords = {2008 semi-supervised colt} } @incollection{Weston:EtAl:06, title = {Semi-supervised protein classification using cluster kernels}, address = {Cambridge, MA}, author = {Jason Weston and Christina Leslie and Eugene Ie and William Stafford Noble}, booktitle = {Semi-Supervised Learning}, editor = {Olivier Chapelle and Bernhard Schölkopf and Alexander Zien}, publisher = {MIT Press}, year = 2006, biburl = {http://www.bibsonomy.org/bibtex/2f8333651e27bea485ecc95db9c215978/seandalai}, keywords = {semi-supervised 2006 kernels string} } @article{Basu:EtAl:04, title = {Active Semi-Supervision for Pairwise Constrained Clustering}, address = {Lake Buena Vista, FL}, author = {Sugato Basu and Arindam Banerjee and Raymond J. Mooney}, booktitle = {Proceedings of the SIAM International Conference on Data Mining}, month = {April}, pages = {333--344}, year = 2004, url = {http://www.cs.utexas.edu/users/ml/papers/semi-sdm-04.pdf}, abstract = {Semi-supervised clustering uses a small amount of supervised data to aid unsupervised learning. One typical approach specifies a limited number of must-link and cannot-link constraints between pairs of examples. This paper presents a pairwise constrained clustering framework and a new method for actively selecting informative pairwise constraints to get improved clustering performance. The clustering and active learning methods are both easily scalable to large datasets, and can handle very high dimensional data. Experimental and theoretical results confirm that this active querying of pairwise constraints significantly improves the accuracy of clustering when given a relatively small amount of supervision.}, biburl = {http://www.bibsonomy.org/bibtex/2c3a38d2081aba3ce847f23eb50512b0b/seandalai}, keywords = {semi-supervised 2004 active clustering} } @inproceedings{Wang:EtAl:03, title = {Bootstrapping SVM active learning by incorporating unlabelled images for image retrieval}, author = {Lei Wang and Kap Luk Chan and Zhihua Zhang}, booktitle = {IEEE Computer Society Conference on Computer Vision and Pattern Recognition}, year = 2003, url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1211412}, abstract = {The performance of image retrieval with SVM active learning is known to be poor when started with few labeled images only. In this paper, the problem is solved by incorporating the unlabelled images into the bootstrapping of the learning process. In this work, the initial SVM classifier is trained with the few labeled images and the unlabelled images randomly selected from the image database. Both theoretical analysis and experimental results show that by incorporating unlabelled images in the bootstrapping, the efficiency of SVM active learning can be improved, and thus improves the overall retrieval performance.}, biburl = {http://www.bibsonomy.org/bibtex/249793b7f5d767cc9b5df7b557b3d6781/seandalai}, keywords = {semi-supervised 2003 image active svm} } @inproceedings{Zhang:Oles:00, title = {A probability analysis on the value of unlabeled data for classification problems}, author = {Tong Zhang and Frank J. Oles}, booktitle = {17th International Conference on Machine Learning}, year = 2000, url = {http://www-cs-students.stanford.edu/~tzhang/papers/icml00-unlabeled.pdf}, biburl = {http://www.bibsonomy.org/bibtex/2d901550751a48f3ba780d73f676805b6/seandalai}, keywords = {semi-supervised icml 2000} } @inproceedings{Su:EtAl:04, title = {Semi-supervised training of a Kernel PCA-Based Model for Word Sense Disambiguation }, address = {Geneva, Switzerland}, author = {Weifeng Su and Marine Carpuat and Dekai Wu}, booktitle = {20th International Conference on Computational Linguistics}, year = 2004, url = {http://acl.ldc.upenn.edu/C/C04/C04-1190.pdf}, description = {Main point is that a bigger kernel matrix can be built with unlabelled data}, abstract = {In this paper, we introduce a new semi-supervised learning model for word sense disambiguation based on Kernel Principal Component Analysis (KPCA), with experiments showing that it can further improve accuracy over supervised KPCA models that have achieved WSD accuracy superior to the best published individual models. Although empirical results with supervised KPCA models demonstrate significantly better accuracy compared to the state-of-the-art achieved by either naive Bayes or maximum entropy models on Senseval-2 data, we identify specific sparse data conditions under which supervised KPCA models deteriorate to essentially a most-frequent-sense predictor. We discuss the potential of KPCA for leveraging unannotated data for partially-unsupervised training to address these issues, leading to a composite model that combines both the supervised and semi-supervised models.}, biburl = {http://www.bibsonomy.org/bibtex/27717dfb69eb2f87a5fdaab8eb0119138/seandalai}, keywords = {coling semi-supervised 2004 dimensionality wsd} } @inproceedings{Ham:EtAl:05, title = {Semisupervised alignment of manifolds}, author = {Jihun Ham and Daniel Lee and Lawrence Saul}, booktitle = {10th International Workshop on Artificial Intelligence and Statistics}, editor = {Robert G. Cowell and Zoubin Ghahramani}, pages = {120--127}, year = 2005, url = {http://www.seas.upenn.edu/~jhham/papers/AISTATS05.pdf}, abstract = {In this paper, we study a family of semisupervised learning algorithms for ``aligning'' different data sets that are characterized by the same underlying manifold. The optimizations of these algorithms are based on graphs that provide a discretized approximation to the manifold. Partial alignments of the data sets - obtained from prior knowledge of their manifold structure or from pairwise correspondences of subsets of labeled examples - are completed by integrating supervised signals with unsupervised frameworks for manifold learning. As an illustration of this semisupervised setting, we show how to learn mappings between different data sets of images that are parameterized by the same underlying modes of variability (e.g., pose and viewing angle). The curse of dimensionality in these problems is overcome by exploiting the low dimensional structure of image manifolds. }, biburl = {http://www.bibsonomy.org/bibtex/2fba9508e6a35574d84b336d204fb3b34/seandalai}, keywords = {semi-supervised 2005 manifold dimensionality aistats} } @inproceedings{Sindhwani:Keerthi:06, title = {Large scale semi-supervised linear SVMs}, address = {New York, NY, USA}, author = {Vikas Sindhwani and S. Sathiya Keerthi}, booktitle = {29th annual international ACM SIGIR Conference on Research and development in information retrieval}, pages = {477--484}, publisher = {ACM Press}, year = 2006, url = {http://portal.acm.org/citation.cfm?id=1148170.1148253}, location = {Seattle, Washington, USA}, isbn = {1-59593-369-7}, doi = {http://doi.acm.org/10.1145/1148170.1148253}, description = {Large scale semi-supervised linear SVMs}, abstract = {Large scale learning is often realistic only in a semi-supervised setting where a small set of labeled examples is available together with a large collection of unlabeled data. In many information retrieval and data mining applications, linear classifiers are strongly preferred because of their ease of implementation, interpretability and empirical performance. In this work, we present a family of semi-supervised linear support vector classifiers that are designed to handle partially-labeled sparse datasets with possibly very large number of examples and features. At their core, our algorithms employ recently developed modified finite Newton techniques. Our contributions in this paper are as follows: (a) We provide an implementation of Transductive SVM (TSVM) that is significantly more efficient and scalable than currently used dual techniques, for linear classification problems involving large, sparse datasets. (b) We propose a variant of TSVM that involves multiple switching of labels. Experimental results show that this variant provides an order of magnitude further improvement in training efficiency. (c) We present a new algorithm for semi-supervised learning based on a Deterministic Annealing (DA) approach. This algorithm alleviates the problem of local minimum in the TSVM optimization procedure while also being computationally attractive. We conduct an empirical study on several document classification tasks which confirms the value of our methods in large scale semi-supervised settings.}, biburl = {http://www.bibsonomy.org/bibtex/2e14377cf02ec95a0f04da79f4b653644/seandalai}, keywords = {semi-supervised 2006 sigir svm} } @inproceedings{Bennett:Demiriz:98, title = {Semi-Supervised Support Vector Machines}, address = {Cambridge, MA}, author = {Kristin P. Bennett and Ayhan Demiriz}, booktitle = {Advances in Neural Information Processing Systems 11}, editor = {Michael S. Kearns and Sara A. Solla and David A. Cohn}, publisher = {MIT Press}, year = 1998, url = {http://books.nips.cc/papers/files/nips11/0368.pdf}, abstract = {We introduce a semi-supervised support vector machine (S3VM) method. Given a training set of labeled data and a working set of unlabeled data, S3VM constructs a support vector machine using both the training and working sets. We use S3VM to solve the transduction problem using overall risk minimization (ORM) posed by Vapnik. The transduction problem is to estimate the value of a classication function at the given points in the working set. This contrasts with the standard inductive learning problem of estimating the classication function at all possible values and then using the xed function to deduce the classes of the working set data. We propose a general S3VM model that minimizes both the misclassication error and the function capacity based on all the available data. We show how the S3VM model for 1-norm linear support vector machines can be converted to a mixed-integer program and then solved exactly using integer programming. Results of S3VM and the standard 1-norm support vector machine approach are compared on eleven data sets. Our computational results support the statistical learning theory results showing that incorporating working data improves generalization when insufficient training information is available. In every case, S3VM either improved or showed no signicant dierence in generalization compared to the traditional approach.}, biburl = {http://www.bibsonomy.org/bibtex/22e18de878646cdc4c2542f9e2a82fe6f/seandalai}, keywords = {semi-supervised 1998 svm nips} } @inproceedings{Yang:EtAl:06, title = {Semi-supervised nonlinear dimensionality reduction}, address = {New York, NY, USA}, author = {Xin Yang and Haoying Fu and Hongyuan Zha and Jesse Barlow}, booktitle = {23rd International Conference on Machine learning}, pages = {1065--1072}, publisher = {ACM Press}, year = 2006, url = {http://www.icml2006.org/icml_documents/camera-ready/134_Semi_Supervised_Nonl.pdf}, location = {Pittsburgh, Pennsylvania}, isbn = {1-59593-383-2}, doi = {http://doi.acm.org/10.1145/1143844.1143978}, abstract = {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. }, biburl = {http://www.bibsonomy.org/bibtex/2893c4e62cc73106e3b717e34a6169573/seandalai}, keywords = {semi-supervised 2006 icml dimensionality} } @inproceedings{Kulis:EtAl:05, title = {Semi-supervised Graph Clustering: A Kernel Approach}, author = {Brian Kulis and Sugato Basu and Inderjit Dhillon and Raymond Mooney}, booktitle = {22nd International Conference on Machine Learning}, year = 2005, url = {http://www.cs.utexas.edu/users/ml/papers/kernel-kdd-05.pdf}, abstract = {Semi-supervised clustering algorithms aim to improve clustering results using limited supervision. The supervision is generally given as pairwise constraints; such constraints are natural for graphs, yet most semisupervised clustering algorithms are designed for data represented as vectors. In this paper, we unify vector-based and graph-based approaches. We show that a recently-proposed objective function for semi-supervised clustering based on Hidden Markov Random Fields, with squared Euclidean distance and a certain class of constraint penalty functions, can be expressed as a special case of the weighted kernel k-means objective. A recent theoretical connection between kernel kmeans and several graph clustering objectives enables us to perform semi-supervised clustering of data given either as vectors or as a graph. For vector data, the kernel approach also enables us to find clusters with nonlinear boundaries in the input data space. Furthermore, we show that recent work on spectral learning (Kamvar et al., 2003) may be viewed as a special case of our formulation. We empirically show that our algorithm is able to outperform current state-of-the-art semi-supervised algorithms on both vector-based and graph-based data sets.}, biburl = {http://www.bibsonomy.org/bibtex/2bcedccdcff8179a1d10f0ec37747644b/seandalai}, keywords = {semi-supervised 2005 icml graphs clustering} } @incollection{NIPS2006_357, title = {Branch and Bound for Semi-Supervised Support Vector Machines}, address = {Cambridge, MA}, author = {Olivier Chapelle and Vikas Sindhwani and Sathiya Keerthi}, booktitle = {Advances in Neural Information Processing Systems 19}, editor = {B. Sch\"{o}lkopf and J. Platt and T. Hoffman}, publisher = {MIT Press}, year = 2007, url = {http://books.nips.cc/papers/files/nips19/NIPS2006_0357.pdf}, biburl = {http://www.bibsonomy.org/bibtex/2c96df1e21c4242ecc8580475f1de9ece/seandalai}, keywords = {semi-supervised 2006 svm nips} }