Maximum Margin Semi-Supervised Learning for Structured Variables
Published 5 December 2005
Yasemin Altün, David McAllester, Mikhail Belkin
Citations99
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper presents a discriminative approach that utilizes the intrinsic geometry of input patterns revealed by unlabeled data points and derives a maximum-margin formulation of semi-supervised learning for structured variables.
Abstract
Abstract Many real-world classification problems involve the prediction ofmultiple inter-dependent variables forming some structural dependency. Recent progress in machine learning has mainly focused onsupervised classification of such structured variables. In this paper, we investigate structured classification in a semi-supervised setting.We present a discriminative approach that utilizes the intrinsic geometry of input patterns revealed by unlabeled data points and wederive a maximum-margin formulation of semi-supervised learning for structured variables. Unlike transductive algorithms, our for-mulation naturally extends to new test points.
Keywords
Computer Science
Combining labeled and unlabeled data with co-training
5,604 Citations1998Avrim Blum, Tom M. Mitchell
Manifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples
3,266 Citations2006Mikhail Belkin, Partha Niyogi +1 more
A semi-supervised framework that incorporates labeled and unlabeled data in a general-purpose learner is proposed and properties of reproducing kernel Hilbert spaces are used to prove new Representer theorems that provide theoretical basis for the algorithms.
Transductive Inference for Text Classification using Support Vector Machines
2,717 Citations1999Thorsten Joachims
An analysis of why TSVMs are well suited for text classi(cid:12)cation is presented, and an algorithm for training TSVMs e(cid:14)-ciently, handling 10,000 examples and more is proposed.
Support vector machine learning for interdependent and structured output spaces
1,260 Citations2004Ioannis Tsochantaridis, Thomas Hofmann +2 more
This paper proposes to generalize multiclass Support Vector Machine learning in a formulation that involves features extracted jointly from inputs and outputs, and demonstrates the versatility and effectiveness of the method on problems ranging from supervised grammar learning and named-entity recognition, to taxonomic text classification and sequence alignment.
Max-Margin Markov Networks
1,251 Citations2003Ben Taskar, Carlos Guestrin +1 more
Maximum margin Markov (M3) networks incorporate both kernels, which efficiently deal with high-dimensional features, and the ability to capture correlations in structured data, and a new theoretical bound for generalization in structured domains is provided.
The MIT Press eBooksConvolution Kernels for Natural Language
812 Citations2002Michael J. Collins, Nigel Duffy
It is shown how a kernel over trees can be applied to parsing using the voted perceptron algorithm, and experimental results on the ATIS corpus of parse trees are given.
Hidden Markov support vector machines
469 Citations2003Yasemin Altün, Ioannis Tsochantaridis +1 more
This paper presents a novel discriminative learning technique for label sequences based on a combination of the two most successful learning algorithms, Support Vector Machines and Hidden Markov Models which it is called HM-SVMs and handles dependencies between neighboring labels using Viterbi decoding.
Cluster Kernels for Semi-Supervised Learning
461 Citations2002Olivier Chapelle, Jason Weston +1 more
A framework to incorporate unlabeled data in kernel classifier, based on the idea that two points in the same cluster are more likely to have the same label is proposed by modifying the eigenspectrum of the kernel matrix.
Beyond the point cloud
443 Citations2005Vikas Sindhwani, Partha Niyogi +1 more
This paper constructs a family of data-dependent norms on Reproducing Kernel Hilbert Spaces (RKHS) that allow the structure of the RKHS to reflect the underlying geometry of the data.
Learning to classify text from labeled and unlabeled documents
330 Citations1998Kamal Nigam, Andrew McCallum +2 more
It is shown that the accuracy of text classifiers trained with a small number of labeled documents can be improved by augmenting this small training set with a large pool of unlabeled documents, and an algorithm is introduced based on the combination of Expectation-Maximization with a naive Bayes classifier.
Kernel methods for missing variables
254 Citations2005Alexander J. Smola, S. V. N. Vishwanathan +1 more
An optimization scheme is proposed which extends the Concave Convex Procedure (CCP) of Yuille and Rangarajan and it is shown how the algorithm can be specialized to various cases in order to efficiently solve the optimization problems that arise.
Érudit documents and data repository (Érudit Consortium, University of Montreal)Efficient Non-Parametric Function Induction in Semi-Supervised Learning
173 Citations2004Yoshua Bengio, Olivier Delalleau +1 more
Experiments show that the proposed non-parametric algorithms which provide an estimated continuous label for the given unlabeled examples are extended to function induction algorithms that correspond to the minimization of a regularization criterion applied to an out-of-sample example, and happens to have the form of a Parzen windows regressor.
Kernel conditional random fields
124 Citations2004John Lafferty, Xiaojin Zhu +1 more
Kernel conditional random fields are introduced as a framework for discriminative modeling of graph-structured data and a procedure for greedily selecting cliques in the dual representation is proposed, which allows sparse representations.
Gaussian process classification for segmenting and annotating sequences
53 Citations2004Yasemin Altün, Thomas Hofmann +1 more
Gaussian Process classification is generalized to predict multiple labels by taking dependencies between neighboring labels into account, motivated by the desire to retain rigorous probabilistic semantics, while overcoming limitations of parametric methods like Conditional Random Fields.
Uncertainty in Artificial IntelligenceCase-factor diagrams for structured probabilistic modeling
53 Citations2004David McAllester, Michael Collins +1 more
Lecture notes in computer scienceMulti-view Discriminative Sequential Learning
47 Citations2005Ulf Brefeld, Christoph Büscher +1 more
The multi-view approach is based on the principle of maximizing the consensus among multiple independent hypotheses and develops this principle into a semi-supervised hidden Markov perceptron, and the resulting procedures utilize unlabeled data effectively and discriminate more accurately than their purely supervised counterparts.
Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)Kernel conditional random fields : representation, clique selection, and semi-supervised learning
10 Citations2018John Lafferty, Yan Liu +1 more
A representer theorem for conditional graphical models is given which shows how kernel conditional random fields arise from risk minimization procedures defined using Mercer kernels on labeled graphs, and a procedure for greedily selecting cliques in the dual representation is proposed, which allows sparse representations.