优化方法在机器学习中的应用

需积分: 10 182 浏览量更新于2024-07-19 收藏 2.98MB PDF 举报

"S. J. Wright Optimization for machine learning.pdf" 是一本关于机器学习优化的书籍，收录在 Neural Information Processing Series 中，该系列由 Michael I. Jordan 和 Thomas Dietterich 编辑。这本书探讨了在神经计算和信息处理领域中的最新发展，通过工作坊的形式汇集了不同背景的科学家，共同研究和开发新颖的计算和统计策略。在机器学习中，优化是核心问题之一，它涉及到如何寻找模型参数的最佳设置，以最大化模型的性能或最小化预测误差。S. J. Wright 的著作可能详细讨论了各种优化算法和技术，这些技术对于训练高效和准确的机器学习模型至关重要。这可能包括梯度下降法、随机梯度下降、牛顿法、拟牛顿法（如 L-BFGS）以及近年来受到广泛关注的深度学习优化方法，如动量法、Adam 优化器等。 Neural Information Processing Systems (NIPS) 工作坊是一个每年举办的会议，旨在促进跨学科的研究合作，推动信息处理和大脑认知机制的理解。这些工作坊提供了展示和讨论未完成工作的平台，从而推动新思想的形成和发展。书中的内容可能涵盖了各种优化方法的应用，如在支持向量机（SVMs）、深度神经网络（DNNs）和其他复杂模型中的应用。例如，"Advances in Large Margin Classifiers" 可能详细讨论了最大间隔分类器的优化策略，而 "Advances in Minimum Description Length: Theory and Applications" 可能涉及了在模型选择和压缩信息表示中的优化问题。此外，"Nearest-Neighbor Methods in Learning and Vision: Theory and Practice" 可能探讨了最近邻方法在学习和视觉任务中的优化问题，而 "Predicting Structured Data" 可能介绍了如何优化模型来处理结构化数据的挑战。优化在机器学习中的重要性不仅在于找到最佳模型参数，还在于处理大规模数据集时的计算效率和收敛速度。因此，S. J. Wright 的书籍可能会深入讨论如何在实际应用中平衡模型的复杂性和性能，以及如何有效地利用并行计算和分布式系统进行优化。总而言之，"S. J. Wright Optimization for machine learning.pdf" 是一本关于机器学习优化的权威资源，它涵盖了从理论到实践的广泛内容，对理解和改进机器学习模型的性能具有极大的价值。通过阅读这本书，读者可以深入了解优化在神经信息处理和机器学习中的关键作用，并学习到最新的优化技术和策略。

1 Introduction: Optimization and Machine

Learning

Suvrit Sra suvrit.sra@tuebingen.mpg.de

Max Planck Insitute for Biological Cybernetics

T¨ubingen, Germany

Sebastian Nowozin Sebastian.Nowozin@Microsoft.com

Microsoft Research

Cambridge, United Kingdom

Stephen J. Wright swright@cs.wisc.edu

University of Wisconsin

Madison, Wisconsin, USA

Since its earliest days as a discipline, machine learning has made use of

optimization formulations and algorithms. Likewise, machine learning has

contributed to optimization, driving the development of new optimization

approaches that address the signiﬁcant challenges presented by machine

learning applications. This cross-fertilization continues to deepen, producing

a growing literature at the intersection of the two ﬁelds while attracting

leading researchers to the eﬀort.

Optimization approaches have enjoyed prominence in machine learning be-

cause of their wide applicability and attractive theoretical properties. While

techniques proposed twenty years and more ago continue to be reﬁned, the

increased complexity, size, and variety of today’s machine learning models

demand a principled reassessment of existing assumptions and techniques.

This book makes a start toward such a reassessment. Besides describing

the resurgence in novel contexts of established frameworks such as ﬁrst-

order methods, stochastic approximations, convex relaxations, interior-point

methods, and proximal methods, the book devotes signiﬁcant attention to

newer themes such as regularized optimization, robust optimization, a vari-

ety of gradient and subgradient methods, and the use of splitting techniques

and second-order information. We aim to provide an up-to-date account of

2 Introduction

the optimization techniques useful to machine learning — those that are

established and prevalent, as well as those that are rising in importance.

To illustrate our aim more concretely, we review in Section 1.1 and 1.2

two major paradigms that provide focus to research at the conﬂuence of

machine learning and optimization: support vector machines (SVMs) and

regularized optimization. Our brief review charts the importance of these

problems and discusses how both connect to the later chapters of this book.

We then discuss other themes — applications, formulations, and algorithms

— that recur throughout the book, outlining the contents of the various

chapters and the relationship between them.

Audience. This book is targeted to a broad audience of researchers and

students in the machine learning and optimization communities; but the

material covered is widely applicable and should be valuable to researchers

in other related areas too. Some chapters have a didactic ﬂavor, covering

recent advances at a level accessible to anyone having a passing acquaintance

with tools and techniques in linear algebra, real analysis, and probability.

Other chapters are more specialized, containing cutting-edge material. We

hope that from the wide range of work presented in the book, researchers

will gain a broader perspective of the ﬁeld, and that new connections will

be made and new ideas sparked.

For background relevant to the many topics discussed in this book, we refer

to the many good textbooks in optimization, machine learning, and related

subjects. We mention in particular Bertsekas (1999) and Nocedal and Wright

(2006) for optimization over continuous variables, and Ben-Tal et al. (2009)

for robust optimization. In machine learning, we refer for background to

Vapnik (1999), Sch¨olkopf and Smola (2002), Christianini and Shawe-Taylor

(2000), and Hastie et al. (2009). Some fundamentals of graphical models

and the use of optimization therein can be found in Wainwright and Jordan

(2008) and Koller and Friedman (2009).

1.1 Support Vector Machines

The support vector machine (SVM) is the ﬁrst contact that many optimiza-

tion researchers had with machine learning, due to its classical formulation

as a convex quadratic program — simple in form, though with a complicat-

ing constraint. It continues to be a fundamental paradigm today, with new

algorithms being proposed for diﬃcult variants, especially large-scale and

nonlinear variants. Thus, SVMs oﬀer excellent common ground on which to

demonstrate the interplay of optimization and machine learning.

1.1 Support Vector Machines 3

1.1.1 Background

The problem is one of learning a classiﬁcation function from a set of labeled

training examples. We denote these examples by {(x

),i=1,...,m},

where x

∈ R

are feature vectors and y

∈{−1, +1} are the labels. In the

simplest case, the classiﬁcation function is the signum of a linear function of

the feature vector. That is, we seek a weight vector w ∈

and an intercept

b ∈

R such that the predicted label of an example with feature vector x is

f(x)=sgn(w

x + b). The pair (w,b) is chosen to minimize a weighted sum

of: (a) a measure of the classiﬁcation error on the training examples; and

(b) w

, for reasons that will be explained in a moment. The formulation

is thus

minimize

w,b,ξ

w + C



i=1

subject to y

+ b) ≥ 1 − ξ

,ξ

≥ 0, 1 ≤ i ≤ m.

(1.1)

Note that the summation term in the objective contains a penalty contribu-

tion from term i if y

= 1 and w

+ b<1, or y

= −1andw

+ b>−1.

If the data are separable, it is possible to ﬁnd a (w,b) pair for which this

penalty is zero. Indeed, it is possible to construct two parallel hyperplanes in

, both of them orthogonal to w but with diﬀerent intercepts, that contain

no training points between them. Among all such pairs of planes, the pair

for which w

is minimal is the one for which the separation is greatest.

Hence, this w gives a robust separation between the two labeled sets, and is

therefore, in some sense, most desirable. This observation accounts for the

presence of the ﬁrst term in the objective of (1.1).

Problem (1.1) is a convex quadratic program with a simple diagonal

Hessian but general constraints. Some algorithms tackle it directly, but for

many years it has been more common to work with its dual, which is

minimize

XY α −α

subject to



=0, 0 ≤ α

≤ C,

(1.2)

where Y =Diag(y

,...,y

)andX =[x

,...,x

] ∈ R

n×m

. This dual is

also a quadratic program. It has a positive semideﬁnite Hessian and simple

bounds, plus a single linear constraint.

More powerful classiﬁers allow the inputs to come from an arbitrary set

X, by ﬁrst mapping the inputs into a space H via a nonlinear (feature)

mapping φ

X → H, and then solving the classiﬁcation problem to ﬁnd

(w,b)withw ∈

H. The classiﬁer is deﬁned as f(x)

= sgn(w,φ(x) + b),

and it can be found by modifying the Hessian from YX

XY to YKY,

4 Introduction

where K

= φ(x

),φ(x

) is the kernel matrix. The optimal weight vector

can be recovered from the dual solution by setting w =



i=1

φ(x

), so

that the classiﬁer is f(x)=sgn[



i=1

φ(x

),φ(x) + b].

In fact, it is not even necessary to choose the mapping φ explicitly.

We need only deﬁne a kernel mapping k

X × X → R and deﬁne the

matrix K directly from this function by setting K

= k(x

, x

). The

classiﬁer can be written purely in terms of the kernel mapping k as follows:

f(x)=sgn[



i=1

k(x

, x)+b].

1.1.2 Classical Approaches

There has been extensive research on algorithms for SVMs since at least the

mid-1990s, and a wide variety of techniques have been proposed. Out-of-

the-box techniques for convex quadratic programming have limited appeal

because usually the problems have large size, and the Hessian in (1.2) can be

dense and ill-conditioned. The proposed methods thus exploit the structure

of the problem and the requirements on its (approximate) solution. We

survey some of the main approaches here.

One theme that recurs across many algorithms is decomposition applied

to the dual (1.2). Rather than computing a step in all components of α

at once, these methods focus on a relatively small subset and ﬁx the other

components. An early approach due to Osuna et al. (1997) works with a

subset B ⊂{1, 2,...,s}, whose size is assumed to exceed the number of

nonzero components of α in the solution of (1.2); their approach replaces

one element of B at each iteration and then re-solves the reduced problem

(formally, a complete reoptimization is assumed, though heuristics are used

in practice). The sequential minimal optimization (SMO) approach of Platt

(1999) works with just two components of α at each iteration, reducing

each QP subproblem to triviality. A heuristic selects the pair of variables

to relax at each iteration. LIBSVM

(see Fan et al., 2005) implements an

SMO approach for (1.2) and a variety of other SVM formulations, with a

particular heuristic based on second-order information for choosing the pair

of variables to relax. This code also uses shrinking and caching techniques

like those discussed below.

SVM

light

(Joachims, 1999) uses a linearization of the objective around the

current point to choose the working set B to be the indices most likely to give

descent, giving a ﬁxed size limitation on B. Shrinking reduces the workload

further by eliminating computation associated with components of α that

1. http://www.csie.ntu.edu.tw/

cjlin/libsvm/

2. http://www.cs.cornell.edu/People/tj/svm_light/

1.1 Support Vector Machines 5

seem to be at their lower or upper bounds. The method nominally requires

computation of |B| columns of the kernel K at each iteration, but columns

can be saved and reused across iterations. Careful implementation of gra-

dient evaluations leads to further computational savings. In early versions

of SVM

light

, the reduced QP subproblem was solved with an interior-point

method (see below), but this was later changed to a coordinate relaxation

procedure due to Hildreth (1957) and D’Esopo (1959). Zanni et al. (2006)

use a similar method to select the working set, but solve the reduced problem

using nonmontone gradient projection, with Barzilai-Borwein step lengths.

One version of the gradient projection procedure is described by Dai and

Fletcher (2006).

Interior-point methods have proved eﬀective on convex quadratic pro-

grams in other domains, and have been applied to (1.2) (see Ferris and

Munson, 2002; Gertz and Wright, 2003). However, the density, size, and

ill-conditioning of the kernel matrix make achieving eﬃciency diﬃcult. To

ameliorate this diﬃculty, Fine and Scheinberg (2001) propose a method that

replaces the Hessian with a low-rank approximation (of the form VV

where V ∈

m×r

for r  m) and solves the resulting modiﬁed dual. This

approach works well on problems of moderate scale, but may be too expen-

sive for larger problems.

In recent years, the usefulness of the primal formulation (1.1) as the basis

of algorithms has been revisited. We can rewrite this formulation as an

unconstrained minimization involving the sum of a quadratic and a convex

piecewise-linear function, as follows:

minimize

w,b

w + CR(w,b), (1.3)

where the penalty term is deﬁned by

R(w,b)



i=1

max(1 −y

+ b), 0). (1.4)

Joachims (2006) describes a cutting-plane approach that builds up a con-

vex piecewise-linear lower bounding function for R(w,b) based on subgra-

dient information accumulated at each iterate. Eﬃcient management of the

inequalities deﬁning the approximation ensures that subproblems can be

solved eﬃciently, and convergence results are proved. Some enhancements

are decribed in Franc and Sonnenburg (2008), and the approach is extended

to nonlinear kernels by Joachims and Yu (2009). Implementations appear in

the code SVM

perf

3. http://www.cs.cornell.edu/People/tj/svm_light/svm_perf.html

剩余508页未读，继续阅读

Armspine

粉丝: 0
资源: 2

优化方法在机器学习中的应用

Machine Learning, Optimization, and Big Data(2017).pdf

MIT+-+Optimization+for+Machine+Learning.2012.pdf

numerical optimization wright pdf

wolfe简约梯度法结合实际案例求解最优，求带上迭代次数的图，且附上参考文献

上述代码结合实际案例求解最优，并附上参考文献

python代码用混合罚函数法实现线性优化问题的具体案例，包括绘制迭代过程图，保证准确，并附上参考文献

数值最优化(第二版)pdf

拟牛顿迭代法matlab程序

信号去噪的算法发展历程，并给出参考资料

请简述信号去噪的算法发展历程，并给出参考资料

最新资源