Semi-监督学习入门

需积分: 9 30 浏览量更新于2024-07-23 收藏 1.22MB PDF 举报

"Introduction to Semi-Supervised Learning" 是一本关于人工智能和机器学习的综合讲座系列书籍，由Xiaojin Zhu和Andrew B. Goldberg撰写，版权属于Morgan & Claypool。在机器学习领域，半监督学习（Semi-Supervised Learning, SSL）是一种介于无监督学习和监督学习之间的方法。传统的监督学习需要大量带有标签的数据进行训练，而无监督学习则仅使用未标记的数据来发现数据的内在结构。半监督学习则在有限的标记数据和大量的未标记数据之间寻找平衡，以提高模型的泛化能力。在本书中，作者Xiaojin Zhu和Andrew B. Goldberg将探讨以下关键知识点： 1. **半监督学习的基本概念**：介绍半监督学习的核心思想，即如何利用未标记数据来辅助有标签数据的训练过程，以提高模型的性能。 2. **半监督学习的动机**：解释在现实世界中，获取大量带标签数据的困难性，以及为什么需要半监督学习来解决这个问题。 3. **半监督学习的策略**：讨论各种半监督学习方法，如一致性正则化、生成模型（如拉普拉斯推断）、图半监督学习、迁移学习、伪标签等，并解释它们的工作原理。 4. **拉普拉斯推断**：介绍如何通过构建数据的图模型，利用马尔可夫随机场（Markov Random Field, MRF）或条件随机场（Conditional Random Field, CRF）来捕获数据的局部和全局结构。 5. **生成模型与判别模型**：对比生成模型（如隐马尔可夫模型、贝叶斯网络）和判别模型（如支持向量机、神经网络），并阐述它们在半监督学习中的应用。 6. **伪标签法**：讲述如何利用未标记数据生成假设的标签，然后用这些标签进一步训练模型，以迭代地改进模型性能。 7. **半监督聚类**：讨论如何结合聚类算法与半监督学习，以更好地对未标记数据进行分类。 8. **评估与比较**：介绍半监督学习模型的评估标准和实验设计，以及如何比较不同方法的效果。 9. **应用案例**：通过具体的应用场景，如文本分类、图像识别、社交网络分析等，展示半监督学习的实际应用和效果。 10. **未来趋势与挑战**：探讨半监督学习领域的研究前沿，包括深度学习在半监督学习中的作用，以及如何处理大规模未标记数据的挑战。该书作为Synthesis Lectures on Artificial Intelligence and Machine Learning系列的一部分，旨在为读者提供一个深入理解半监督学习理论和技术的平台，适合对机器学习有一定基础的学者和从业者阅读。

2 CHAPTER 1. INTRODUCTION TO STATISTICAL MACHINE LEARNING

1.1 THE DATA

Deﬁnition 1.2. Instance.Aninstance x represents a speciﬁc object. The instance is often repre-

sented by a D-dimensional feature vector x = (x

,...,x

) ∈ R

, where each dimension is called a

feature. The length D of the feature vector is known as the dimensionality of the feature vector.

The feature representation is an abstraction of the objects. It essentially ignores all other infor-

mation not represented by the features. For example, two little green men with the same weight and

height, but with different names, will be regarded as indistinguishable by our feature representation.

Note we use boldface x to denote the whole instance, and x

to denote the d-th feature of x. In our

example, an instance is a speciﬁc little green man; the feature vector consists of D = 2 features: x

is the weight, and x

is the height. Features can also take discrete values. When there are multiple

instances, we will use x

to denote the i-th instance’s d-th feature.

Deﬁnition 1.3. Training Sample.Atraining sample is a collection of instances {x

}

i=1

,...,x

}, which acts as the input to the learning process. We assume these instances are sampled

independently from an underlying distribution P(x), which is unknown to us. We denote this by

}

i=1

i.i.d.

∼ P(x), where i.i.d. stands for independent and identically distributed.

In our example, the training sample consists of n = 100 instances x

,...,x

100

. A training

sample is the “experience” given to a learning algorithm. What the algorithm can learn from it,

however, varies. In this chapter, we introduce two basic learning paradigms: unsupervised learning

and supervised learning.

1.2 UNSUPERVISED LEARNING

Deﬁnition 1.4. Unsupervised learning. Unsupervised learning algorithms work on a training

sample with n instances {x

}

i=1

. There is no teacher providing supervision as to how individual

instances should be handled—this is the deﬁning property of unsupervised learning. Common

unsupervised learning tasks include:

• clustering, where the goal is to separate the n instances into groups;

• novelty detection, which identiﬁes the few instances that are very different from the majority;

• dimensionality reduction, which aims to represent each instance with a lower dimensional

feature vector while maintaining key characteristics of the training sample.

Among the unsupervised learning tasks, the one most relevant to this book is clustering, which

we discuss in more detail.

Deﬁnition 1.5. Clustering. Clustering splits {x

}

i=1

into k clusters, such that instances in the

same cluster are similar, and instances in different clusters are dissimilar. The number of clusters k

may be speciﬁed by the user, or may be inferred from the training sample itself.

1.3. SUPERVISED LEARNING 3

How many clusters do you ﬁnd in the little green men data in Figure 1.1? Perhaps k = 2,

k = 4, or more. Without further assumptions, either one is acceptable. Unlike in supervised learning

(introduced in the next section), there is no teacher that tells us which instances should be in each

cluster.

There are many clustering algorithms. We introduce a particularly simple one, hierarchical

agglomerative clustering, to make unsupervised learning concrete.

Algorithm 1.6. Hierarchical Agglomerative Clustering.

Input: a training sample {x

}

i=1

; a distance function d().

1. Initially, place each instance in its own cluster (called a singleton cluster).

2. while (number of clusters > 1) do:

3. Find the closest cluster pair A, B, i.e., they minimize d(A,B).

4. Merge A, B to form a new cluster.

Output: a binary tree showing how clusters are gradually merged from singletons

to a root cluster, which contains the whole t raining sample.

This clustering algorithm is simple. The only thing unspeciﬁed is the distance function d().

If x

, x

are two singleton clusters, one way to deﬁne d(x

, x

) is the Euclidean distance between

them:

d(x

, x

) =x

− x

=









s=1

− x

)

. (1.1)

We also need to deﬁne the distance between two non-singleton clusters A, B. There are multiple

possibilities: one can deﬁne it to be the distance between the closest pair of points in A and B,

the distance between the farthest pair, or some average distance. For simplicity, we will use the ﬁrst

option, also known as single linkage:

d(A,B) = min

x∈A,x



∈B

d(x, x



). (1.2)

It is not necessary to fully grow the tree until only one cluster remains: the clustering algorithm

can be stopped at any point if d() exceeds some threshold, or the number of clusters reaches a

predetermined number k.

Figure 1.2 illustrates the results of hierarchical agglomerative clustering for k = 2, 3, 4,re-

spectively.The clusters certainly look ﬁne. But because there is no information on how each instance

should be clustered, it can be difﬁcult to objectively evaluate the result of clustering algorithms.

1.3 SUPERVISED LEARNING

Suppose you realize that your alien hosts have a gender: female or male (so they should not all be

called little green men after all). You may now be interested in predicting the gender of a particular

4 CHAPTER 1. INTRODUCTION TO STATISTICAL MACHINE LEARNING

80 90 100 110

weight (lbs.)

height (in.)

80 90 100 110

weight (lbs.)

height (in.)

80 90 100 110

weight (lbs.)

height (in.)

Figure 1.2: Hierarchical agglomerative clustering results for k = 2, 3, 4 on the 100 little green men data.

alien from his or her weight and height. Alternatively, you may want to predict whether an alien is a

juvenile or an adult using weight and height. To explain how to approach these tasks, we need more

deﬁnitions.

Deﬁnition 1.7. Label. A label y is the desired prediction on an instance x.

Labels may come from a ﬁnite set of values, e.g., {female, male}. These distinct values are

called classes. The classes are usually encoded by integer numbers, e.g., female =−1, male = 1, and

thus y ∈{−1, 1}. This particular encoding is often used for binary (two-class) labels, and the two

classes are generically called the negative class and the positive class, respectively. For problems with

more than two classes, a traditional encoding is y ∈{1,...,C}, where C is the number of classes. In

general, such encoding does not imply structure in the classes.That is to say, the two classes encoded

by y = 1 and y = 2 are not necessarily closer than the two classes y = 1 and y = 3. Labels may also

take continuous values in R. For example, one may attempt to predict the blood pressure of little

green aliens based on their height and weight.

In supervised learning, the training sample consists of pairs, each containing an instance x and

a label y: {(x

)}

i=1

. One can think of y as the label on x provided by a teacher, hence the name

supervised learning. Such (instance, label) pairs are called labeled data, while instances alone without

labels (as in unsupervised learning) are called unlabeled data . We are now ready to deﬁne supervised

learning.

Deﬁnition 1.8. Supervised learning. Let the domain of instances be X , and the domain of labels

Y.LetP(x,y) be an (unknown) joint probability distribution on instances and labels X × Y.

Given a training sample {(x

)}

i=1

i.i.d.

∼ P(x,y), supervised learning trains a function f : X → Y

in some function family F, with the goal that f(x) predicts the true label y on future data x, where

(x,y)

i.i.d.

∼ P(x,y)as well.

1.3. SUPERVISED LEARNING 5

Depending on the domain of label y, supervised learning problems are further divided into

classiﬁcation and regression:

Deﬁnition 1.9. Classiﬁcation. Classiﬁcation is the supervised learning problem with discrete

classes

Y. The function f is called a classiﬁer.

Deﬁnition 1.10. Regression. Regression is the supervised learning problem with continuous Y.

The function f is called a regression function.

What exactly is a good f ? The best f is by deﬁnition

∗

= argmin

f ∈F

(x,y)∼P

[

c(x,y,f(x))

]

, (1.3)

where argmin means “ﬁnding the f that minimizes the following quantity”. E

(x,y)∼P

[

]

is the

expectation over random test data drawn from P . Readers not familiar with this notation may wish

to consult Appendix A. c(·) is a loss function that determines the cost or impact of making a prediction

f(x) that is different from the true label y. Some typical loss functions will be discussed shortly. Note

we limit our attention to some function family

F, mostly for computational reasons. If we remove

this limitation and consider all possible functions, the resulting f

∗

is the Bayes optimal predictor, the

best one can hope for on average. For the distribution P , this function will incur the lowest possible

loss when making predictions. The quantity E

(x,y)∼P

[c(x,y,f

∗

(x))] is known as the Bayes error.

However, the Bayes optimal predictor may not be in

F in general. Our goal is to ﬁnd the f ∈ F

that is as close to the Bayes optimal predictor as possible.

It is worth noting that the underlying distribution P(x,y)is unknown to us.Therefore,it is not

possible to directly ﬁnd f

∗

, or even to measure any predictor f ’s performance, for that matter. Here

lies the fundamental difﬁculty of statistical machine learning: one has to generalize the prediction

from a ﬁnite training sample to any unseen test data. This is known as induction.

To proceed, a seemingly reasonable approximation is to gauge f ’s performance using training

sample error. That is, to replace the unknown expectation by the average over the training sample:

Deﬁnition 1.11. Training sample error. Given a training sample {(x

)}

i=1

,the training sample

error is



i=1

c(x

,f(x

)). (1.4)

For classiﬁcation, one commonly used loss function is the 0-1 loss c(x,y,f(x)) ≡ (f (x

) =



i=1

(f (x

) = y

), (1.5)

基本困难：从有限

训练集推广到任意

的测试集！

6 CHAPTER 1. INTRODUCTION TO STATISTICAL MACHINE LEARNING

where f(x) = y is1iff predicts a different class than y on x, and 0 otherwise. For regression, one

commonly used loss function is the squared loss c(x,y,f(x)) ≡ (f (x

) − y

)



i=1

(f (x

) − y

)

. (1.6)

Other loss functions will be discussed as we encounter them later in the book.

It might be tempting to seek the f that minimizes training sample error. However, this

strategy is ﬂawed: such an f will tend to overﬁt the particular training sample. That is, it will likely

ﬁt itself to the statistical noise in the particular training sample. It will learn more than just the

true relationship between

X and Y. Such an overﬁtted predictor will have small training sample

error, but is likely to perform less well on future test data. A sub-area within machine learning called

computational learning theory studies the issue of overﬁtting. It establishes rigorous connections

between the training sample error and the true error, using a formal notion of complexity such as

the Vapnik-Chervonenkis dimension or Rademacher complexity. We provide a concise discussion

in Section 8.1. Informed by computational learning theory, one reasonable training strategy is to

seek an f that “almost” minimizes the training sample error, while regularizing f so that it is not too

complex in a certain sense. Interested readers can ﬁnd the references in the bibliographical notes.

To estimate f ’s future performance, one can use a separate sample of labeled instances, called

the test sample: {(x

)}

n+m

j=n+1

i.i.d.

∼ P(x,y). A test sample is not used during training, and therefore

provides a faithful (unbiased) estimation of future performance.

Deﬁnition 1.12. Test sample error. The corresponding test sample error for classiﬁcation with

0-1 loss is

n+m



j=n+1

(f (x

) = y

), (1.7)

and for regression with squared loss is

n+m



j=n+1

(f (x

) − y

)

. (1.8)

In the remainder of the book, we focus on classiﬁcation due to its prevalence in semi-supervised

learning research. Most ideas discussed also apply to regression, though.

As a concrete example of a supervised learning method, we now introduce a simple classiﬁ-

cation algorithm: k-nearest-neighbor (kNN).

Algorithm 1.13. k-nearest-neighbor classiﬁer.

Input: Training data (x

),...,(x

); distance function d();

number of neighbors k; test instance x

∗

tempting！

over-fit

剩余129页未读，继续阅读

jiangdmdr

粉丝: 58
资源: 765

Semi-监督学习入门

semi-supervised learning

semi-supervised learning

Introduction to Semi-Supervised Learning - Xiaojin Zhu, Andrew B. Goldberg（2009）

机器学习 -- Semi-supervised Learning

active learning surey

Machine.Learning.for.Adaptive.Many-Core.Machines.331

Mastering Machine Learning Algorithms 2018

Machine Learning Algorithms 2017.8

Bishop Pattern Recognition and Machine Learning

深度解析：概率图模型经典第二版-机器学习基石

最新资源