icml-tutorial

Description

Support Vector and Kernel MachinesNello CristianiniBIOwulf [e-mail]://www.support-vector.net/tutorial.htmlICML 2001A Little Historyz SVMs introduced in COLT-92 by Boser, Guyon, Vapnik. Greatly developed ever since.z Initially popularized in the NIPS community, now an important and active field of all Machine Learning research. z Special issues of Machine Learning Journal, and Journal of Machine Learning Research.z Kernel Machines: large class of learning algorithms, SVMs a particular instance.www.support-vector.netA Little Historyz Annual workshop at NIPSz Centralized website: www.kernel-machines.orgz Textbook (2000): see www.support-vector.netz Now: a large and diverse community: from machine learning, optimization, statistics, neural networks, functional analysis, etc. etcz Successful applications in many fields (bioinformatics, text, handwriting recognition, etc)z Fast expanding field, EVERYBODY WELCOME ! -www.support-vector.netPreliminariesz Task of this class of algorithms: detect and exploit complex patterns in data (eg: by clustering, classifying, ranking, cleaning, etc. the data)z Typical problems: how to represent complex patterns; and how to exclude spurious (unstable) patterns (= overfitting)z The first is a computational problem; the second a statistical problem.www.support-vector.netVery Informal Reasoningz The class of kernel methods implicitly defines the class of possible patterns ...

Informations

• Publié par: Phawying
• Nombre de lectures: 14
• Langue: English

Extrait

Support Vector and Kernel Machines

Nello Cristianini BIOwulf Technologies [e-mail] http://mtlotirlah.wpoup.swwotcev-trut/ten.r

ICML 2001

A Little History

z

z

z

z

SVMs introduced in COLT-92 by Boser, Guyon, Vapnik. Greatly developed ever since. Initially popularized in the NIPS community, now an important and active field of all Machine Learning research. Special issues of Machine Learning Journal, and Journal of Machine Learning Research. Kernel Machines: large class of learning algorithms, SVMs a particular instance.

www.support-vector.net

A Little History

z

z

z

z

z

z

Annual workshop at NIPS Centralized website: www.kernel-machines.org Textbook (2000): see www.support-vector.net Now: a large and diverse community: from machine learning, optimization, statistics, neural networks, functional analysis, etc. etc Successful applications in many fields (bioinformatics, text, handwriting recognition, etc) Fast expanding field, EVERYBODY WELCOME ! -

www.support-vector.net

Preliminaries

z Task of this class of algorithms: detect and exploit complex patterns in data (eg: by clustering, classifying, ranking, cleaning, etc. the data) z Typical problems: how to represent complex patterns; and how to exclude spurious (unstable) patterns (= overfitting) z The first is a computational problem; the second a statistical problem.

www.support-vector.net

Very Informal Reasoning

z The class of kernel methods implicitly defines the class of possible patterns by introducing a notion of similarity between data z Example: similarity between documents z By length z By topic z By language … z Choice of similarity Î Choice of relevant features

www.support-vector.net

More formal reasoning

z

z

z

z

Kernel methods exploit information about the inner products between data items Many standard algorithms can be rewritten so that they only require inner products between data (inputs) Kernel functions = inner products in some feature space (potentially very complex) If kernel given, no need to specify what features of the data are being used

www.support-vector.net

Just in case …

z Inner product between vectors x,z1 å x i z i z Hyperplane: i x w,#b10 x x w x

o

b

o

www.support-vector.net

o

x

o

o

x

x

x o

Overview of the Tutorial

z Introduce basic concepts with extended example of Kernel Perceptron z Derive Support Vector Machines z Other kernel based algorithms z Properties and Limitations of Kernels z On Kernel Alignment z On Optimizing Kernel Alignment

www.support-vector.net

Parts I and II: overview

z Linear Learning Machines (LLM) z Kernel Induced Feature Spaces z Generalization Theory z Optimization Theory z Support Vector Machines (SVM)

www.support-vector.net

Modularity

z

z

z

z

IMPORTANT CONCEPT

Any kernel-based learning algorithm composed of two modules: – A general purpose learning machine – A problem specific kernel function Any K-B algorithm can be fitted with any kernel Kernels themselves can be constructed in a modular way Great for software engineering (and for analysis)

www.support-vector.net

1-Linear Learning Machines

z Simplest case: classification. Decision function is a hyperplane in input space z The Perceptron Algorithm (Rosenblatt, 57)

z Useful to analyze the Perceptron algorithm, before looking at SVMs and Kernel Methods in general

www.support-vector.net