最新《机器学习最优化》课程笔记

需积分: 40 128 浏览量更新于2023-05-30 评论收藏 8.57MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

Course notes on

Optimization for Machine Learning

Gabriel Peyr´e

CNRS & DMA

Ecole Normale Sup´erieure

gabriel.peyre@ens.fr

https://mathematical-tours.github.io

www.numerical-tours.com

May 9, 2020

Abstract

This document presents ﬁrst order optimization methods and their applications to machine learning.

This is not a course on machine learning (in particular it does not cover modeling and statistical consid-

erations) and it is focussed on the use and analysis of cheap methods that can scale to large datasets and

models with lots of parameters. These methods are variations around the notion of “gradient descent”,

so that the computation of gradients plays a major role. This course covers basic theoretical properties

of optimization problems (in particular convex analysis and ﬁrst order diﬀerential calculus), the gradient

descent method, the stochastic gradient method, automatic diﬀerentiation, shallow and deep networks.

Contents

1 Motivation in Machine Learning 1

1.1 Unconstraint optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Classiﬁcation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Basics of Convex Analysis 2

2.1 Existence of Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.2 Convexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.3 Convex Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Derivative and gradient 5

3.1 Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3.2 First Order Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3.3 Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.4 Link with PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.5 Classiﬁcation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3.6 Chain Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4 Gradient Descent Algorithm 9

4.1 Steepest Descent Direction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4.2 Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

5 Convergence Analysis 11

5.1 Quadratic Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

5.2 General Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

6 Regularization 17

6.1 Penalized Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

6.2 Ridge Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

6.3 Lasso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

6.4 Iterative Soft Thresholding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

7 Stochastic Optimization 21

7.1 Minimizing Sums and Expectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

7.2 Batch Gradient Descent (BGD) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

7.3 Stochastic Gradient Descent (SGD) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

7.4 Stochastic Gradient Descent with Averaging (SGA) . . . . . . . . . . . . . . . . . . . . . . . . 25

7.5 Stochastic Averaged Gradient Descent (SAG) . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

8 Multi-Layers Perceptron 26

8.1 MLP and its derivative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

8.2 MLP and Gradient Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

8.3 Universality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

9 Automatic Diﬀerentiation 30

9.1 Computational Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

9.2 Forward Mode of Automatic Diﬀerentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

9.3 Reverse Mode of Automatic Diﬀerentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

9.4 Feed-forward Compositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

9.5 Feed-forward Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

9.6 Recurrent Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

1 Motivation in Machine Learning

1.1 Unconstraint optimization

In most part of this Chapter, we consider unconstrained convex optimization problems of the form

inf

x∈R

f(x), (1)

and try to devise “cheap” algorithms with a low computational cost per iteration to approximate a minimizer

when it exists. The class of algorithms considered are ﬁrst order, i.e. they make use of gradient information.

In the following, we denote

argmin

f(x)

def.

= {x ∈ R

; f(x) = inf f},

to indicate the set of points (it is not necessarily a singleton since the minimizer might be non-unique) that

achieve the minimum of the function f. One might have argmin f = ∅ (this situation is discussed below),

but in case a minimizer exists, we denote the optimization problem as

min

x∈R

f(x). (2)

In typical learning scenario, f(x) is the empirical risk for regression or classiﬁcation, and p is the number

of parameter. For instance, in the simplest case of linear models, we denote (a

, y

)

i=1

where a

∈ R

are

the features. In the following, we denote A ∈ R

n×p

the matrix whose rows are the a

Figure 3: Coercivity condition for least squares.

Figure 4: Convex vs. non-convex functions ; Strictly convex vs. non strictly convex functions.

x → +∞. Such a function is called coercive. In this case, one can choose any x

∈ R

and consider its

associated lower-level set

Ω = {x ∈ R

; f(x) 6 f(x

)}

which is bounded because of coercivity, and closed because f is continuous. One can actually show that for

convex function, having a bounded set of minimizer is equivalent to the function being coercive (this is not

the case for non-convex function, for instance f(x) = min(1, x

) has a single minimum but is not coercive).

Example 1 (Least squares). For instance, for the quadratic loss function f(x) =

||Ax −y||

, coercivity holds

if and only if ker(A) = {0} (this corresponds to the overdetermined setting). Indeed, if ker(A) 6= {0} if x

is a solution, then x

+ u is also solution for any u ∈ ker(A), so that the set of minimizer is unbounded. On

contrary, if ker(A) = {0}, we will show later that the set of minimizer is unique, see Fig. 3. If ` is strictly

convex, the same conclusion holds in the case of classiﬁcation.

2.2 Convexity

Convex functions deﬁne the main class of functions which are somehow “simple” to optimize, in the sense

that all minimizers are global minimizers, and that there are often eﬃcient methods to ﬁnd these minimizers

(at least for smooth convex functions). A convex function is such that for any pair of point (x, y) ∈ (R

)

∀t ∈ [0, 1], f((1 − t)x + ty) 6 (1 −t)f(x) + tf(y) (5)

which means that the function is bellow its secant (and actually also above its tangent when this is well

deﬁned), see Fig. 4. If x

is a local minimizer of a convex f, then x

is a global minimizer, i.e. x

∈ argmin f.

Convex function are very convenient because they are stable under lots of transformation. In particular,

if f, g are convex and a, b are positive, af + bg is convex (the set of convex function is itself an inﬁnite

dimensional convex cone!) and so is max(f, g). If g : R

→ R is convex and B ∈ R

q×p

, b ∈ R

then

f(x) = g(Bx + b) is convex. This shows immediately that the square loss appearing in (3) is convex, since

|| · ||

/2 is convex (as a sum of squares). Also, similarly, if ` and hence L is convex, then the classiﬁcation

loss function (4) is itself convex.

剩余37页未读，继续阅读

syp_net

粉丝: 147
资源: 1197

会员权益专享

最新《机器学习最优化》课程笔记

评论0

会员权益专享

最新资源

最新《机器学习最优化》课程笔记

评论0

台湾大学机器学习基石手写笔记

斯坦福大学机器学习课程个人笔记完整版

张志华《机器学习导论》笔记和补充材料

机器学习个人笔记完整版v5.4.docx

斯坦福大学吴恩达Coursera机器学习公开课中文笔记

《机器学习导论》干货笔记

如何学习机器学习相关的技术

机器学习简答题笔记.docx

机器学习笔记 Bishop版PAML

如何开始学习机器学习

matlab ga优化机器学习

北邮+机器学习+自动化+yhh+机器学习实验+作业+kmeans算法1

怎么学习深度学习和机器学习

-车载测试的报文换算例子

数据库.sql

光纤激光打标机培训资料全.doc

在unity 中使用XML的小样

基于android的高校校园跑腿系统的设计app（android毕业设计，包括源码、数据库）.zip

会员权益专享

最新资源