Key Sequence

Notation

New Concepts

• graph
• depth first search

Important Results / Claims

• solving topological sort with depth first search

Questions

Interesting Factoids

1. initialize weights \(\alpha_{i} = \frac{1}{N}\)
2. for \(t \in 1 … T\)
   • learn this-round classifier \(f_{t}\qty(x)\) on data weights \(\alpha_{i}\)
   • recompute classifier coefficient \(\hat{w}_{t}\)
   • recompute weights \(\alpha_{i}\)
   • normalize weights \(\alpha_{i} = \frac{\alpha_{i}}{\sum_{j=1}^{N} \alpha_{j}}\)
3. final model predicts via \(\hat{y} = \text{sign}\qty(\sum_{t=1}^{T} \hat{w}_{t}f_{t}\qty(x))\) for classifier with \(T\) rounds

After some iterations. This algorithm only works on binary classification and eventually gets exponential loss / 0/1 loss. gradient boosting will eventually allow a more general form.

boosting allows combining very simple models to boost results. One good algoritm is AdaBoost.

additional information

example

for instance, we can ensemble four decision trees together. You can weight the prediction of each of the trees, and then add them up, and then run some decision boundary over them (i.e. for instance if the output is boolean, you can multiply the boolean as \(\pm 1\) multiplied by a weight)

high level ideas

1. add more features (i.e. extract more, increase model complexity)
2. add more weak learners together

hash table are a randomized data structure that allows fast insert / delete / search.

• insert: stick it into the data structure based on key
• delete: delete from data structure
• search: get a pointer into the data structure, or null

\(O\qty(1)\) time insert, delete, and search

constituents

• \(U\) is a universe, where \(|U| = M\)
• \(K \subseteq U\) keys are going to show up, \(|K| = n\)
• \(M \gg n\)
• \(h: U \to \qty {1 \dots n}\) is a function that maps elements of \(U\) to buckets

slight abuse of notation: there will be \(n\) buckets, and \(n\) elements that come in. They should be similar OOM but can be not equal (since you can stick multiple into a bucket and run a constant-time search).