Machine Learning Summer School 2006 - Taipei

Online Learning and Bregman Divergences

author: Manfred K. Warmuth, Department of Computer Science, University of California

Description

L 1: Introduction to Online Learning (Predicting as good as the best expert, Predicting as good as the best linear combination of experts, Additive versus multiplicative family of updates)
L 2: Bregman divergences and Loss bounds (Introduction to Bregman divergences, Relative loss bounds for the linear case, Nonlinear case & matching losses, Duality and relation to exponential families)
L 3: Extensions, interpretations, applications (Online to Batch Conversions, Prior information on the weight vector, Some applications)

Categories

Top: Computer Science: Machine Learning: On-line Learning
Top: Computer Science: Machine Learning: Computational Learning Theory

You might be experiencing some problems with Your Video player.

*Slides*
0:06	Online Learning and Bregman Divergences
1:01	Bregman Divergences [Br,CL,Cs]
1:42	Exponential Family of Distributions
4:10	Expectation parameter
4:48	Exponential Family of Distributions
4:53	Expectation parameter
5:55	Primal & Dual Parameters
6:50	Gaussian (unit variance)
8:00	Primal & Dual Parameters
8:15	Gaussian (unit variance)
8:39	Bernoulli
10:40	Poisson
12:07	Manfred1_Page_25
15:55	Exponential Family of Distributions
16:05	Expectation parameter
16:26	Bregman Div. as Rel. Ent. between Distributions
17:23	Area unchanged When Slide Flipped
18:55	Area unchanged When Slide Flipped
19:25	Area unchanged When Slide Flipped
19:34	Area unchanged When Slide Flipped
19:56	Dual divergence for Bernoulli
20:55	Area unchanged When Slide Flipped
20:58	Dual divergence for Bernoulli
21:30	Area unchanged When Slide Flipped
21:34	Dual divergence for Bernoulli
22:35	Dual divergence for Poisson
24:02	Dual matching loss for sigmoid transfer func.
27:15	Example: Gaussian density estimation
29:12	Derivation of Updates
29:32	Example: Gaussian density estimation
29:53	Derivation of Updates
31:52	On-line Algorithm [AW]
32:27	Alternate Motivation of Same On-Line Update
34:14	Alternate Motivation of Same On-Line Update
34:46	Shrinkage Towards Initial
34:48	Shrinkage Towards Initial
37:29	Key Lemma [AW]
37:55	Main Theorem
38:15	Bounds for the Forward Algorithm
39:07	Shrinkage Towards Initial
39:43	Bounds for the Forward Algorithm
42:17	Why Bregman divergences?
43:15	General setup of on-line learning
43:52	Minimax Algorithm for T Trials
45:51	Gaussian
47:35	Last-step Minimax
47:39	Minimax Algorithm for T Trials
48:05	Last-step Minimax
49:23	Last-step Minimax: Bernoulli
51:26	Minimax Algorithm for T Trials
52:12	Synopsis of methods
52:59	Minimax Algorithm for T Trials
53:39	Gaussian
54:45	Synopsis of methods
56:47	Content of this tutorial
56:54	Simple conversions
57:00	Expected loss bounds [HW]
60:24	Expected loss bounds [HW]
61:39	Expected loss bounds [HW]
62:20	Expected loss bounds [HW]
63:20	Tail bound [CCG]
64:22	Application: Adaptive Channel Equalization
67:02	Application: Caching [GBW]
67:58	Caching Policies
69:02	Which Policy to Choose?
69:44	Characteristics Vary with Time
71:12	Randomly Permuted Request Stream
71:40	Characteristics Vary with Time
71:48	Randomly Permuted Request Stream
72:27	Want “Adaptive” Policy

Lecture rating

People found this lecture:
Worth seeing
because it is:
Valuable and informative
Well presented
Easily understandable
Acceptably recorded
You need to login to cast your vote.

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.