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).

• \(\mathcal{P}\) problem (states, transitions, etc.)
• \(N\) visit counts
• \(Q\) a q-table: action-value estimates
• \(d\) depth (how many next states to look into)—more is more accurate but slower
• \(U\) value function estimate; usually a Rollout Policy, estimate at some depth \(d\)
• \(c\) exploration constant

After \(n\) simulation s from the starting state; we find the best action for our current state from our q-table.

Subroutine: simulate(state, depth_remaining)

• If depth_remaining=0, simply return the utility from the value function estimate
• For some s, Actions that we just got, if we haven’t seen it, we just return the value function estimate + initialize the N and Q tables
• select an action via the monte-carlo exploration formula
• sample a next state and current reward based on the action you gotten via a generative model
• value = reward + discount*simulate(next_state, depth_remaining-1)
• add to the N(state, action) count
• update the q table at (state, action): Q[s,a] + = (value-Q[s,a])/N[s,a] (“how much better is taking this action?” — with later times taking this action more heavily discounted)

monte-carlo exploration

\begin{equation} \max_{a} Q(s,a) + c \sqrt{ \frac{\log \sum_{a}N(s,a)}{N(s,a)}} \end{equation}