学位论文 > 优秀研究生学位论文题录展示

基于图的半监督机器学习

作　者: 胡崇海
导　师: 刘康生
学　校: 浙江大学
专　业: 运筹学与控制论
关键词: 机器学习监督学习标记点流形正则化分类器核函数对偶问题线性可分学习问题
分类号: TP181
类　型: 博士论文
年　份: 2008年
下　载: 583次
引　用: 3次
阅　读: 论文下载

内容摘要

Over the past few years, semi-supervised learning has gained considerable interest and success in both theory and practice. Traditional supervised machine learning algorithms can only make use of labeled data, and reasonable performance is often achieved only with a large number of labeled data. However, labeled data is often expensive and time consuming to collect, while unlabeled data is usually cheaper and easier to obtain. The strength of semi-supervised learning lies in its ability to utilize a large quantity of unlabeled data to effectively and efficiently improve learning performance.Recently, graph-based semi-supervised learning algorithms are being intensively studied, thanks to its convenient local representation, connection with other models like kernel machines. Graph Laplacian is the central quantity of graph-based semi-supervised learning, which plays a role in exploring the underlying manifold geometry of the data. Using graph Laplacian to form the regularization problem and further employing the kernel techniques is a promising approach of semi-supervised learning.The author first introduce the basic concepts of semi-supervised learning, as well as the utilized tools and theory, such as support vector machines, kernel methods and regularization theory.The main contributions of this thesis are mainly presented in chapter 5 and chapter 6. In chapter 5, the author first investigate a class of graph-based semi-supervised learning methods by spectral transformation. Then the formulation of semi-supervised spectral kernel learning based on maximum margin criterion with spectral decreasing order constraints is formed, and he also maintain that the maximum margin criterion is a more essential goal of semi-supervised kernel learning than kernel target alignment by theoretical analysis. By equivalently transforming the resulted intractable optimization problem into a quadratically constrained quadratic programming, the problem can be efficiently solved. Moreover, the author also propose a method to automatically tune the involved trade-off parameter. Furthermore, the author seek another way to learn the spectral coefficients from a more essential view. Due to the fact that the spectral order constraints are actually not hard requirements but only for the purpose of ensuring the smoothness of the score function, the author leaves out those constraints by directly including the smoothness regularizer into the maximum margin objective, which coincides with the theory of manifold regularization. Its efficient iterative algorithm is also designed next. Experimental results on real-world data sets have demonstrated that both of his proposed spectral learning methods achieve promising results against other approaches.Motivated by the requirements of many practical problems, in chapter 6 the author turns to study the problem of semi-supervised learning with structured outputs, which is a more general topic than the standard semi-supervised learning. By extending the definition of smoothness regularizer to multi-class setting, he next explore the multi-class semi-supervised classification. Although the obtained data dependent kernel similar to that of Sindhwani et al., his multi-class model really extend the theory of theirs. Still next, the author further generalize the multi-class manifold regularization problem to the scenario with structured outputs, and the corresponding dual problems are also obtained. From the dual formulations, we can find that the semi-supervised learning task finally can be achieved by the supervised structural prediction with a newly defined "data dependent joint kernel matrix". This data dependent kernel matrix generalizes that of Sindhwani et al. to structural prediction. Moreover, his proposed inductive approach can naturally predict the unseen data points other than the unlabeled data. Some experiments on text categorization with hierarchies are conducted, and the empirical results show his approaches actually utilize the structural and manifold information of the data simultaneously, and finally help us to improve the prediction performance. As a supplement, the author also proposes the concept of joint Laplacian, which shares the similar properties of standard Laplacian matrix.

全文目录

ABSTRACT  3-5
ACKNOWLEDGEMENTS  5-11
Chapter 1 Introduction(Chinese)  11-31
  1.1 Concepts  11-17
  1.2 SVM,Kernel Methods  17-22
  1.3 Regularization Theory  22-23
  1.4 Graph-based Semi-supervised Learning  23-27
  1.5 Contributions of This Thesis  27-31
    1.5.1 Graph Laplacian Spectral Learning  27-29
    1.5.2 Semi-supervised Learning With Structured Outputs  29-31
Chapter 2 Introduction  31-37
  2.1 Standard SVM  31-32
  2.2 Structural SVM  32-33
  2.3 Semi-supervised Learning  33-35
  2.4 Contribution of This Thesis  35-37
Chapter 3 Kernel,RKHS and Regularization  37-45
  3.1 Binary Classification  37-38
  3.2 Kernels and RKHS  38-39
  3.3 The Kernel Methods  39-41
  3.4 Regularization Theory  41-45
    3.4.1 From Regularization Theory To SVM  42-45
Chapter 4 Preliminaries of Semi-supervised Learning  45-55
  4.1 Concepts  46-48
  4.2 Graph-based Semi-supervised Learning  48-55
    4.2.1 Approximating Manifolds as Graphs  48-50
    4.2.2 Is Manifold(Graph) Useful?  50-51
    4.2.3 Graph Laplacian  51-55
Chapter 5 Spectral Transformation Approaches To Semi-Supervised Learning  55-87
  5.1 Introduction  55-57
  5.2 Background and Related Work  57-60
    5.2.1 Regularization Problems  57-58
    5.2.2 Semi-supervised Spectral Learning  58-60
    5.2.3 KTA-based Spectral Kernel Design  60
  5.3 Marginal-based Semi-supervised Spectral Learning  60-70
    5.3.1 Theoretical Foundation  60-62
    5.3.2 Algorithms  62-70
  5.4 Manifold-Wrapped Kernel Learning Via Spectral Transformation  70-79
    5.4.1 Manifold Regularization Problem  72-74
    5.4.2 Algorithms  74-79
  5.5 Experimental Results  79-83
    5.5.1 Data  79
    5.5.2 Tested Methods  79-80
    5.5.3 Experimental Setup  80-81
    5.5.4 Performance Results  81-83
  5.6 Conclusions  83-87
Chapter 6 Graph-based Semi-supervised Structural Prediction  87-125
  6.1 Symbols  88-89
  6.2 Supervised Classification Models With Multiple Categories  89-97
    6.2.1 Traditional Multi-class Classification  89-90
    6.2.2 Supervised Classification With Structured Output Space  90-93
    6.2.3 Marginal Rescaling Model(SVM_1~(△m))  93-96
    6.2.4 Slack Rescaling Model(SVM_1~(△s))  96-97
  6.3 Semi-supervised Learning With Multiple Categories  97-107
    6.3.1 Multi-class Manifold Regularization  97-101
    6.3.2 ManifoldRegularization Problem Based On SVM_1~(△s)  101-105
    6.3.3 Manifold Regularization Problem Based On SVM_1~(△m)  105-107
  6.4 Inductive Approach  107-109
  6.5 Experiments  109-118
    6.5.1 Compared Methods  109-110
    6.5.2 Data sets  110
    6.5.3 Experimental Protocol  110-113
    6.5.4 Performance Estimation Criteria  113-115
    6.5.5 Results  115-118
  6.6 Discussions  118-124
    6.6.1 Joint Laplacian?!  118-122
    6.6.2 Computational Issue  122-124
  6.7 Conclusions  124-125
Chapter 7 Conclusions And Future Work  125-129
Chapter 8 Appendix  129-133
  8.1 Matrix  129-130
  8.2 Kronecker Product  130
  8.3 The Vec Operator  130-133
Bibliography  133-142

基于图的半监督机器学习

内容摘要

全文目录

相似论文