Machine Learning Summer School (MLSS), Chicago 2009

On Surrogate Loss Functions, f-Divergences and Decentralized Detection

author: Michael I. Jordan, Department of Electrical Engineering and Computer Sciences, UC Berkeley
published: July 30, 2009, recorded: June 2009, views: 665

Slides

Slides
0:00	f-Divergences and Surrogate Loss Functions
2:08	Motivating Example: Decentralized Detection
4:13	Decentralized Detection
5:29	Decentralized Detection (cont.)
7:13	Perspectives
10:28	f-divergences (Ali-Silvey Distances)
11:32	Why the f-divergence?
11:34	f-divergences (Ali-Silvey Distances)
11:58	Why the f-divergence?
13:48	Machine Learning Perspective
14:47	Margin-Based Surrogate Loss Functions
15:21	Estimation Based on a Convex Surrogate Loss
15:38	Some Theory for Surrogate Loss Functions
17:18	Outline
17:58	Setup
19:14	Profiling
21:08	Some Examples
21:50	Link between -losses and f-divergences
22:12	Conjugate Duality
23:36	Link between -losses and f-divergences
24:46	The Easy Direction: → f
26:17	The f → Direction Has a Constructive Consequence
27:53	Example – Hellinger distance
29:14	Example – Variational distance
29:41	Example – Kullback-Leibler divergence
30:08	Bayes Consistency for Choice of (Q, )
32:36	Setup (1)
34:13	Setup (2)
34:51	Bayes Consistency for Choice of (Q, )
35:57	Universal Equivalence of Loss Functions
37:23	An Equivalence Theorem
40:13	Estimation of Divergences
40:15	An Equivalence Theorem
43:58	Universal Equivalence of Loss Functions
46:57	Estimation of Divergences
48:28	Existing Work
48:41	Estimation of Divergences
49:08	Existing Work
49:11	Main Idea
50:35	Kullback-Leibler Divergence
50:54	M-Estimation Procedure
51:16	Convex Empirical Risk with Penalty
51:41	Convergence Rates
51:56	Results (1)
52:42	Results (2)
52:47	Conclusions

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Lecture popularity: You need to login to cast your vote.

Description

In 1951, David Blackwell published a seminal paper - widely cited in economics - in which a link was established between the risk based on 0-1 loss and a class of functionals known as f-divergences. The latter functionals have since come to play an important role in several areas of signal processing and information theory, including decentralized detection. Yet their role in these fields has largely been heuristic. We show that an extension of Blackwell´s programme provides a solid foundation for the use of f-divergences in decentralized detection, as well as in more general problems of experimental design. Our extension is based on a connection between f-divergences and the class of so-called surrogate loss funcions - computationally-inspired upper bounds on 0-1 loss that have become central in the machine learning literature on classification. (Joint work with XuanLong Nguyen and Martin Wainwright.)