In this paper, we study the problem of semi-supervised structured output prediction, which aims to learn predictors for structured outputs, such as sequences, tree nodes, vectors, etc., from a set of data points of both inputoutput pairs and single inputs without outputs. The traditional methods to solve this problem usually learns one single predictor for all the data points, and ignores the variety of the different data points. Different parts of the data set may have different local distributions, and requires different optimal local predictors. To overcome this disadvantage of existing methods, we propose to learn different local predictors for neighborhoods of different data points, and the missing structured outputs simultaneously. In the neighborhood of each data point, we proposed to learn a linear predictor by minimizing both the complexity of the predictor and the upper bound of the structured prediction loss. The minimization is conducted by gradient descent algorithms. Experiments over four benchmark data sets, including DDSM mammography medical images, SUN natural image data set, Cora research paper data set, and Spanish news wire article sentence data set, show the advantages of the proposed method.
@cite_15 proposed the problem of semi-supervised learning with structured outputs. Moreover, a novel discriminative approach was also proposed to use the manifold of input features of both labeled and unlabeled data points. This approach is based on the semi-supervised maximum-margin formulation. It is an inductive algorithm, and it can be easily extended to new-coming test data points.
@cite_15
2140045824 1792316426 2095758845 2145494108
Semi-supervised learning, which uses unlabeled data to help learn a discriminative model, is especially important for structured output problems, as considerably more effort is needed to label its multi-dimensional outputs versus standard single output problems. We propose a new max-margin framework for semi-supervised structured output learning, that allows the use of powerful discrete optimization algorithms and high order regularizers defined directly on model predictions for the unlabeled examples. We show that our framework is closely related to Posterior Regularization, and the two frameworks optimize special cases of the same objective. The new framework is instantiated on two image segmentation tasks, using both a graph regularizer and a cardinality regularizer. Experiments also demonstrate that this framework can utilize unlabeled data from a different source than the labeled data to significantly improve performance while saving labeling effort. Promising approaches to structured learning problems have recently been developed in the maximum margin framework. Unfortunately, algorithms that are computationally and memory efficient enough to solve large scale problems have lagged behind. We propose using simple subgradient-based techniques for optimizing a regularized risk formulation of these problems in both online and batch settings, and analyze the theoretical convergence, generalization, and robustness properties of the resulting techniques. These algorithms are are simple, memory efficient, fast to converge, and have small regret in the online setting. We also investigate a novel convex regression formulation of structured learning. Finally, we demonstrate the benefits of the subgradient approach on three structured prediction problems. Many real-world classification problems involve the prediction of multiple inter-dependent variables forming some structural dependency. Recent progress in machine learning has mainly focused on supervised 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 we derive a maximum-margin formulation of semi-supervised learning for structured variables. Unlike transductive algorithms, our formulation naturally extends to new test points. We consider the semi-supervised learning problem, where a decision rule is to be learned from labeled and unlabeled data. In this framework, we motivate minimum entropy regularization, which enables to incorporate unlabeled data in the standard supervised learning. Our approach includes other approaches to the semi-supervised problem as particular or limiting cases. A series of experiments illustrates that the proposed solution benefits from unlabeled data. The method challenges mixture models when the data are sampled from the distribution class spanned by the generative model. The performances are definitely in favor of minimum entropy regularization when generative models are misspecified, and the weighting of unlabeled data provides robustness to the violation of the "cluster assumption". Finally, we also illustrate that the method can also be far superior to manifold learning in high dimension spaces.