机器学习基础理论与算法实践

需积分: 33 117 浏览量更新于2024-07-20 收藏 3.39MB PDF 举报

"《机器学习经典制作》是一本面向学生和研究人员的机器学习入门书籍，涵盖了现代机器学习的基础理论和概念工具，同时介绍了算法的应用关键方面。书中对一些先进的结果给出了简洁的证明，并讨论了机器学习中的一些复杂主题和开放研究问题。全书包括多类分类、排名和回归等单独章节，但未涉及图形模型和神经网络。本书适合研究生和高年级本科生作为教材，也可作为研究研讨会的参考文本。前3章奠定了后续内容的理论基础，其他章节大部分自成一体，第5章引入的概念在后续章节中广泛应用。每章末尾配有练习题，答案在附录中提供。读者需要具备线性代数、概率论和算法分析的基础知识，书中还提供了线性代数和概率回顾以及凸优化的简短介绍。" 在《机器学习的基础》一书中，作者Mehryar Mohri、Afshin Rostamizadeh和Ameet Talwalkar通过MIT Press出版，为读者构建了全面的机器学习知识框架。该书是“适应性计算与机器学习”系列的一部分，旨在为学习者提供深入理解机器学习算法所需的理论基础。作者们强调了理论工具和概念的重要性，即使对于相对高级的结果，也力求简洁明了。书中涵盖了广泛的主题，包括但不限于： 1. **机器学习基础**：这部分介绍了机器学习的基本概念，如监督学习、无监督学习和强化学习，以及学习理论的基础知识。 2. **线性代数和概率**：这些是机器学习中的核心数学工具，包括向量空间、矩阵运算、概率分布和条件概率等。 3. **算法分析**：讨论了评估和比较机器学习算法性能的方法，如错误率、偏差和方差分析。 4. **模型选择与评估**：涉及交叉验证、正则化和学习曲线等技术，用于选择最佳模型和避免过拟合。 5. **多类分类**：专门的章节探讨了处理多于两种类别的问题，如one-vs-all、one-vs-one策略和多类SVM。 6. **排名和回归**：排名问题在信息检索和推荐系统中有重要意义，而回归则是预测连续变量的关键方法。 7. **凸优化**：介绍了求解机器学习优化问题的基本算法，如梯度下降法和牛顿法。 8. **开发现状与未来挑战**：讨论了当前研究领域中的开放问题，暗示了机器学习领域的未来发展方向。 9. **练习与解决方案**：书中的习题设计有助于巩固学习，附录中提供的完整解答有助于自我评估和深化理解。此外，书中还包含了对概率界限的有用工具集合，这对于理解和应用概率不等式至关重要。《机器学习经典制作》是一本全面且深入的教程，对于希望在机器学习领域深化知识的学习者来说，是一份宝贵的资源。

1.2 Deﬁnitions and terminology 3

Figure 1.1 The zig-zag line on the left panel is consistent over the blue and red

training sample, but it is a complex separation surface that is not likely to generalize

well to unseen data. In contrast, the decision surface on the right panel is simpler

and might generalize better in spite of its misclassiﬁcation of a few points of the

training sample.

Which concept families can actually be learned, and under what conditions? How

well can these concepts be learned computationally?

1.2 Deﬁnitions and terminology

We will use the canonical problem of spam detection as a running example to

illustrate some basic deﬁnitions and to describe the use and evaluation of machine

learning algorithms in practice. Spam detection is the problem of learning to

automatically classify email messages as either spam or non-spam.

Examples: Items or instances of data used for learning or evaluation. In our spam

problem, these examples correspond to the collection of email messages we will use

for learning and testing.

Features : The set of attributes, often represented as a vector, associated to an

example. In the case of email messages, some relevant features may include the

length of the message, the name of the sender, various characteristics of the header,

the presence of certain keywords in the body of the message, and so on.

Labels : Values or categories assigned to examples. In classiﬁcation problems,

examples are assigned speciﬁc categories, for instance, the spam and non-spam

categories in our binary classiﬁcation problem. In regression, items are assigned

real-valued labels.

Training sample: Examples used to train a learning algorithm. In our spam

problem, the training sample consists of a set of email examples along with their

associated labels. The training sample varies for diﬀerent learning scenarios, as

described in section 1.4.

Validation sample: Examples used to tune the parameters of a learning algorithm

4 Introduction

when working with labeled data. Learning algorithms typically have one or more

free parameters, and the validation sample is used to select appropriate values for

these model parameters.

Test sample: Examples used to evaluate the performance of a learning algorithm.

The test sample is separate from the training and validation data and is not made

available in the learning stage. In the spam problem, the test sample consists of a

collection of email examples for which the learning algorithm must predict labels

based on features. These predictions are then compared with the labels of the test

sample to measure the performance of the algorithm.

Loss function : A function that measures the diﬀerence, or loss, between a pre-

dicted label and a true label. Denoting the set of all labels as Y and the set of

possible predictions as Y



, a loss function L is a mapping L: Y×Y



→ R

. In most

cases, Y



= Y and the loss function is bounded, but these conditions do not always

hold. Common examples of loss functions include the zero-one (or misclassiﬁcation)

loss deﬁned over {−1, +1}×{−1, +1} by L(y, y



)=1



=y

and the squared loss

deﬁned over I × I by L(y, y



)=(y



− y)

,whereI ⊆ R is typically a bounded

interval.

Hypothesis set: A set of functions mapping features (feature vectors) to the set of

labels Y. In our example, these may be a set of functions mapping email features

to Y = {spam, non-spam}. More generally, hypotheses may be functions mapping

features to a diﬀerent set Y



. They could be linear functions mapping email feature

vectors to real numbers interpreted as scores (Y



= R), with higher score values

more indicative of spam than lower ones.

We now deﬁne the learning stages of our spam problem. We start with a given

collection of labeled examples. We ﬁrst randomly partition the data into a training

sample, a validation sample, and a test sample. The size of each of these samples

depends on a number of diﬀerent considerations. For example, the amount of data

reserved for validation depends on the number of free parameters of the algorithm.

Also, when the labeled sample is relatively small, the amount of training data is

often chosen to be larger than that of test data since the learning performance

directly depends on the training sample.

Next, we associate relevant features to the examples. This is a critical step in

the design of machine learning solutions. Useful features can eﬀectively guide the

learning algorithm, while poor or uninformative ones can be misleading. Although

it is critical, to a large extent, the choice of the features is left to the user. This

choice reﬂects the user’s prior knowledge about the learning task which in practice

can have a dramatic eﬀect on the performance results.

Now, we use the features selected to train our learning algorithm by ﬁxing diﬀerent

values of its free parameters. For each value of these parameters, the algorithm

1.3 Cross-validation 5

selects a diﬀerent hypothesis out of the hypothesis set. We choose among them

the hypothesis resulting in the best performance on the validation sample. Finally,

using that hypothesis, we predict the labels of the examples in the test sample. The

performance of the algorithm is evaluated by using the loss function associated to

the task, e.g., the zero-one loss in our spam detection task, to compare the predicted

and true labels.

Thus, the performance of an algorithm is of course evaluated based on its test error

and not its error on the training sample. A learning algorithm may be consistent,

that is it may commit no error on the examples of the training data, and yet

have a poor performance on the test data. This occurs for consistent learners

deﬁned by very complex decision surfaces, as illustrated in ﬁgure 1.1, which tend

to memorize a relatively small training sample instead of seeking to generalize well.

This highlights the key distinction between memorization and generalization, which

is the fundamental property sought for an accurate learning algorithm. Theoretical

guarantees for consistent learners will be discussed with great detail in chapter 2.

1.3 Cross-validation

In practice, the amount of labeled data available is often too small to set aside

a validation sample since that would leave an insuﬃcient amount of training data.

Instead, a widely adopted method known as n-fold cross-validation is used to exploit

the labeled data both for model selection (selection of the free parameters of the

algorithm) and for training.

Let θ denote the vector of free parameters of the algorithm. For a ﬁxed value

of θ, the method consists of ﬁrst randomly partitioning a given sample S of

m labeled examples into n subsamples, or folds. The ith fold is thus a labeled

sample ((x

),...,(x

)) of size m

. Then, for any i ∈ [1,n], the learning

algorithm is trained on all but the ith fold to generate a hypothesis h

,andthe

performance of h

is tested on the ith fold, as illustrated in ﬁgure 1.2a. The

parameter value θ is evaluated based on the average error of the hypotheses h

which is called the cross-validation error .Thisquantityisdenotedby



(θ)and

deﬁned by



(θ)=



i=1



j=1

L(h

),y

)



 

error of h

on the ith fold

The folds are generally chosen to have equal size, that is m

= m/n for all i ∈ [1,n].

How should n be chosen? The appropriate choice is subject to a trade-oﬀ and the

topic of much learning theory research that we cannot address in this introductory

6 Introduction

test train train train train

testtrain train train train

testtrain train traintrain

error

(a) (b)

Figure 1.2 n-fold cross validation. (a) Illustration of the partitioning of the

training data into

5 folds. (b) Typical plot of a classiﬁer’s prediction error as a

function of the size of the training sample: the error decreases as a function of the

number of training points.

chapter. For a large n, each training sample used in n-fold cross-validation has size

m−m/n = m(1−1/n) (illustrated by the right vertical red line in ﬁgure 1.2b), which

is close to m, the size of the full sample, but the training samples are quite similar.

Thus, the method tends to have a small bias but a large variance. In contrast,

smaller values of n lead to more diverse training samples but their size (shown by

the left vertical red line in ﬁgure 1.2b) is signiﬁcantly less than m,thusthemethod

tends to have a smaller variance but a larger bias.

In machine learning applications, n is typically chosen to be 5 or 10. n-fold cross

validation is used as follows in model selection. The full labeled data is ﬁrst split

into a training and a test sample. The training sample of size m is then used to

compute the n-fold cross-validation error



(θ) for a small number of possible

values of θ. θ is next set to the value θ

for which



(θ) is smallest and the

algorithm is trained with the parameter setting θ

over the full training sample of

size m.Itsperformanceisevaluatedonthetestsampleasalreadydescribedinthe

previous section.

The special case of n-fold cross validation where n = m is called leave-one-out

cross-validation, since at each iteration exactly one instance is left out of the training

sample. As shown in chapter 4, the average leave-one-out error is an approximately

unbiased estimate of the average error of an algorithm and can be used to derive

simple guarantees for some algorithms. In general, the leave-one-out error is very

costly to compute, since it requires training n times on samples of size m − 1, but

for some algorithms it admits a very eﬃcient computation (see exercise 10.9).

In addition to model selection, n-fold cross validation is also commonly used for

performance evaluation. In that case, for a ﬁxed parameter setting θ, the full labeled

sample is divided into n random folds with no distinction between training and test

samples. The performance reported is the n-fold cross-validation on the full sample

as well as the standard deviation of the errors measured on each fold.

1.4 Learning scenarios 7

1.4 Learning scenarios

We next brieﬂy describe common machine learning scenarios. These scenarios diﬀer

in the types of training data available to the learner, the order and method by which

training data is received and the test data used to evaluate the learning algorithm.

Supervised learning: The learner receives a set of labeled examples as training

data and makes predictions for all unseen points. This is the most common scenario

associated with classiﬁcation, regression, and ranking problems. The spam detection

problem discussed in the previous section is an instance of supervised learning.

Unsupervised learning: The learner exclusively receives unlabeled training data,

and makes predictions for all unseen points. Since in general no labeled exam-

ple is available in that setting, it can be diﬃcult to quantitatively evaluate the

performance of a learner. Clustering and dimensionality reduction are example of

unsupervised learning problems.

Semi-supervised learning: The learner receives a training sample consisting of

both labeled and unlabeled data, and makes predictions for all unseen points. Semi-

supervised learning is common in settings where unlabeled data is easily accessible

but labels are expensive to obtain. Various types of problems arising in applications,

including classiﬁcation, regression, or ranking tasks, can be framed as instances

of semi-supervised learning. The hope is that the distribution of unlabeled data

accessible to the learner can help him achieve a better performance than in the

supervised setting. The analysis of the conditions under which this can indeed

be realized is the topic of much modern theoretical and applied machine learning

research.

Transductive inference: As in the semi-supervised scenario, the learner receives

a labeled training sample along with a set of unlabeled test points. However, the

objective of transductive inference is to predict labels only for these particular test

points. Transductive inference appears to be an easier task and matches the scenario

encountered in a variety of modern applications. However, as in the semi-supervised

setting, the assumptions under which a better performance can be achieved in this

setting are research questions that have not been fully resolved.

On-line learning: In contrast with the previous scenarios, the online scenario

involves multiple rounds and training and testing phases are intermixed. At each

round, the learner receives an unlabeled training point, makes a prediction, receives

the true label, and incurs a loss. The objective in the on-line setting is to minimize

the cumulative loss over all rounds. Unlike the previous settings just discussed, no

distributional assumption is made in on-line learning. In fact, instances and their

labels may be chosen adversarially within this scenario.

剩余426页未读，继续阅读

wuxinxing1981

粉丝: 3
资源: 30

机器学习基础理论与算法实践

机器学习个人笔记完整版

Matlab统计和机器学习工具箱官方英文手册

吴恩达机器学习视频讲座笔记中文版

机器学习经典例题csdn

唐宇迪-机器学习经典案例.zip

机器学习经典算法的实现

matlab 制作机器学习样本集

机器学习与经典程序设计

机器学习经典算法改进研究

大数据平台人工机器学习与自动机器学习的区别

最新资源