bagging/slides.html

<!DOCTYPE html>
<html>
  <head>
    <title>Bagging</title>
    <meta charset="utf-8">
    <link rel="stylesheet" href="https://unpkg.com/purecss@1.0.1/build/pure-min.css" integrity="sha384-oAOxQR6DkCoMliIh8yFnu25d7Eq/PHS21PClpwjOTeU2jRSq11vu66rf90/cZr47" crossorigin="anonymous">    <style>
      @import url(https://fonts.googleapis.com/css?family=Yanone+Kaffeesatz);
      @import url(https://fonts.googleapis.com/css?family=Droid+Serif:400,700,400italic);
      @import url(https://fonts.googleapis.com/css?family=Ubuntu+Mono:400,700,400italic);

      body { font-family: 'Droid Serif'; }
      h1, h2, h3 {
        font-family: 'Yanone Kaffeesatz';
        font-weight: normal;
      }
      .remark-code, .remark-inline-code { font-family: 'Ubuntu Mono'; }
      .reference{
      	font-size: 10px;
      }
      .smaller-font { font-size:14px } 
      @page {
        size: 908px 681px;
        margin: 0;
      }

      @media print {
        .remark-slide-scaler {
          width: 100% !important;
          height: 100% !important;
          transform: scale(1) !important;
          top: 0 !important;
          left: 0 !important;
        }
      }

      .figure img{
        height: 550px;
      }

      .figure-200 img{
        height: 200px;
      }

      .figure-250 img{
        height: 250px;
      }

      .figure-300 img{
        height: 300px;
      }

      .figure-500 img{
        height: 500px;
      }

      .figure-w500 img{
        width: 500px;
      }

      .figure-w600 img{
        width: 600px;
      }
    </style>
  </head>
  <body>
    <textarea id="source">

class: center, middle

# Bagging

CS534 - Machine Learning

Yubin Park, PhD

---

class: middle, center

Recall the bias-variance decomposition

for Squared Loss

$$ \text{E}[(y-f)^2] = \text{Bias}[f]^2 + \text{Var}[f] + \sigma^2 $$

---

class: middle, center

This time, we will decompose a bit differently:

$$ \text{E}[(y-f)^2] = \text{E}[((y - \text{E}[f]) + (\text{E}[f] - f))^2]$$

$$ = \text{E}[(y - \text{E}[f])^2] + \text{E}[(\text{E}[f] - f)^2]$$

$$ \ge \text{E}[(y - \text{E}[f])^2] $$

---

class: middle, center

Maybe too obvious.

If we can make `\(f\)` close to `\(\text{E}[f]\)`

the expected loss will be less.

But, how?

---

## Bagging (1)

Imagine that we know the "real" distribution for the samples: `\((\mathbf{x}_i, y_i)\)`

To estimate `\(\text{E}[f]\)`, we would repeat:

1. draw a set of samples
1. estimate `\(f\)`
1. repeat the above as many as possible
1. then aggregate all estimated `\(f\)`

The only caveat is that we do not know the "real" distribution.

Perhaps, we can "simulate" the real distribution with the samples we have?

BTW, What's the difference between 1) sampling from the distribution and 2) sampling from the samples?


---

## Bagging (2)

Bagging (Bootstrap Aggregation) works as follows:

1. draw random samples from the data with "replacement"
1. estimate `\(f\)`
1. repeat `\(B\)` number of times

then get the final model by averaging as follows:

$$ f\_\text{bagged} = \frac{1}{B} \sum\_{b=1}^B f_b$$

---

class: middle, center

.figure-500[![bt](img/bagged_trees.png)]

.reference[Chapter 8 of [ESLII](https://web.stanford.edu/~hastie/ElemStatLearn/)]

---

class: middle, center

.figure-500[![bt](img/bagged_tree_perf.png)]

.reference[Chapter 8 of [ESLII](https://web.stanford.edu/~hastie/ElemStatLearn/)]

---

## Model Averaging and Stacking

One step beyond the simple averaging models:

$$ \text{E}[(y - \sum\_{b=1}^B w\_b f\_b)^2] \le \text{E}[(y - \frac{1}{B} \sum\_{b=1}^B f_b)^2] $$

If `\(w_b = \frac{1}{B}\)`, then the both sides are equal.

How do we estimate the weights, `\(w_b\)`?

We will divide the training set into two parts:

- **Training I** for fitting `\(f\_b\)`
- **Training II** for estimating `\(w_b\)`

This can be viewed as stacking two layers of models, thus Model Stacking.

---

class: center, middle

## Questions?

</textarea>
    <script src="https://remarkjs.com/downloads/remark-latest.min.js">
    </script>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-AMS_HTML&delayStartupUntil=configured" type="text/javascript">
    </script>
    <script type="text/javascript">
      var hljs = remark.highlighter.engine;
      /*
        Language: terminal console
        Author: Josh Bode <joshbode@gmail.com>
      */
      hljs.registerLanguage('terminal', function() {
        return {
          contains: [
            {
              className: 'string',
              begin: '^([\\w.]+)@([\\w.]+)'
            },
            {
              className: 'constant',
              begin: ' (.*) \\$ '
            },
            {
              className: 'ansi',
              begin: '<span style\\="([^"]+)">',
              end: '<\\/span>'
            }
          ]
        }
      });
      var slideshow = remark.create({
        highlightStyle: 'monokai'
      });

      // extract the embedded styling from ansi spans
      var highlighted = document.querySelectorAll("code.terminal span.hljs-ansi");
      Array.prototype.forEach.call(highlighted, function(next) {
        next.insertAdjacentHTML("beforebegin", next.textContent);
        next.parentNode.removeChild(next);
      });

      // Setup MathJax
      MathJax.Hub.Config({
          tex2jax: {
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
          }
      });

      MathJax.Hub.Configured();
    </script>
  </body>
</html>