Triple jump acceleration for the EM algorithm and its extrapolation-based variants
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.
| 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.
Related content
SEE ALSO:
Link this page
Would you like to put a link to this lecture on your homepage?Go ahead! Copy the HTML snippet !




