event thumbnail image
Machine Learning Summer School 2006 - Taipei
Pascal

Triple jump acceleration for the EM algorithm and its extrapolation-based variants

author: Han-Shen Huang, Institute of Information Science, Academia Sinica

Description

The Aitken's acceleration is one of the most commonly used method to speed up the fixed-point iteration computation, including the EM algorithm. However, it requires to compute or approximate the Jacobian of the EM mapping matrix, which can be intractable for complex models. We will present our current research topic, the triple-jump acceleration, to accelerate the EM and some of its extrapolation-based variants by approximating their Jacobians. One advantage of the triple jump framework is that we can directly use the EM and its extrapolation-based variants as black boxes and achieve acceleration easily. We can update parameter vectors globally with the same approximated Jacobian, or locally based on each decomposable component with different Jacobians. Experimental results show that the triple jump methods consistently accelerate EM, parameterized EM (pEM) and adaptive EM (aEM) for a variety of probabilistic models.

You might be experiencing some problems with Your Video player.
Slides
0:00 Triple Jump Acceleration for the EM Algorithm and Its Extrapolation-based Variants
0:32 Motivation
1:29 Brief Summary of Our Work
2:18 Parameter Estimation Problem
2:54 The EM Algorithm
3:53 Taylor Expansion of M
5:09 Eigenvaluesof J
5:47 Convergence Rate of EM
6:24 Parameterized EM (pEM)
7:18 Convergence Rate of pEM(1)
8:18 Convergence Rate of pEM(2)
8:51 Adaptive OverrelaxedEM (aEM)
9:33 Aitken’sAcceleration for EM (1)
10:52 Aitken’sAcceleration for EM (2)
11:55 Our Solution to Accelerate EM
12:20 Triple Jump Framework (1)
13:00 Triple Jump Framework (2)
14:01 Triple Jump Framework (3)
14:34 Triple Jump Framework (4)
14:52 Advantages of TJ Framework
16:09 TJEM Extrapolation (1)
16:59 TJEM Extrapolation (2)
17:20 TJEM Algorithm
17:36 TJpEMExtrapolation
18:15 TJpEMAlgorithm
18:29 Convergence Properties of TJpEM Algorithm
19:59 Convergence Rates of TJEM and TJpEM
20:12 Convergence Rates of TJpEM with Different Learning Rates
21:48 TJ2pEM Extrapolation
22:26 Comparison of TJ2pEM & TJpEM
23:07 TJ2pEM Algorithm
23:10 Convergence Rate of TJ2pEM
23:48 Convergence Rates of TJ2pEM with Different Learning Rates
24:41 TJ2aEM Algorithm
25:07 Why Dynamic Learning Rates
25:45 Proof Sketch
26:24 Data sets
26:53 TJEM Faster than EM (HMM)
27:35 TJEM Faster than EM (Alarm)
27:40 TJEM Faster than EM (GMM)
27:42 TJEM Faster than EM (Bayesian Classifier)
27:43 TJpEM with Proper Learning Rate Faster than TJEM
28:16 TJpEM with Large Learning Rates Slower than TJEM
28:32 TJ2pEM Overcomes the Impact of Large Learning Rates
28:43 aEMFaster than pEM
29:54 TJ2aEM Faster than aEM(HMM)
30:35 TJ2aEM Faster than aEM(Alarm)
30:54 TJ2aEM Faster than aEM(GMM)
30:58 TJ2aEM Faster than aEM (Bayesian Classifier)
31:01 ComponentwiseTJEM
32:18 Case Study: Bayesian Classifier
32:58 Missing Rate = 50%
33:20 Missing Rate = 90%
33:45 Summary
34:31 Thank You

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.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment: