Machine Learning: Ensemble Methods

Ensemble Method is a popular approach in Machine Learning based on the idea of combining multiple models. For example, by mixing different machine learning algorithms (e.g. SVM, Logistic regression, Bayesian network), ensemble method can automatically pick the best algorithmic model that fits the data the best. On the other hand, by mixing different parameter set of the same algorithmic model (e.g. Random forest, Boosting tree), it can pick the best set of parameters of the same algorithmic model.

Bagging
Bagging is based on the idea of learning multiple models using different sets of sample data, basically by random sampling (with replacement) from the same training set. After the models are learned, we use a voting scheme to predict future data. In case of the classification problem, we use the majority class voted by all models. In case of the regression problem, we take the average value of estimated output from all models.

The model doesn't have to be equally weighted. We can use a weighted average of individual models to come up with the final model. m = w1.m1 + w2.m2 + w3.m3 + ...

To obtain the weights w1, w2 ... we can use machine learning to figure out. In the case, we first use the training data set to train individual models. After that, we use the validation data set to train the weights. Concretely, we feed each data point from the validation set to each model to come up with the final prediction. Based on how the ensembled prediction deviates from the actual outcome, we can learn the optimal set of weights.

Boosting
Boosting extend the idea of bagging by putting more emphasis on the training data that is wrongly predicted. In boosting, weight sampling is used. Initially each training data is equally weighted but as each iteration goes, the data that is wrongly classified will have its weight increased. On the other hand, the model also has its weighted according to how good this model is predicting the data in its round.

1. Each training data carry a sample weight (initially are the same)
2. For each iteration, take sample (with replacement) based on weights
3. Compute the error rate e
4. For each sample that is wrongly predicted, adjust its sample weight by e/(1-e)
5. Weight the trained model according to its error. For example, log(e/(1-e))
6. Stop when e is small enough
7. Ensemble the overall model according to model weight.

Gradient Boosting Method is one of the most powerful and popular boosting methods. It is based on incrementally add a function that fits the residuals.

Found function F to fit y ~ F(x) using a gradient descent approach.

Start with some random guessing function F. Compute the loss based on the residual.
loss = L(y - F(x)) where L is some loss function

Partial differentiate loss w.r.t. function F, and compute the value at every data point. Use another machine learning model to learn another function g(x) that predicts the partial differentiation value. Then update F(x) <- F(x) + a.g(x) where a is the learning rate.

Other ways of Sampling
Instead of sampling the training data, we can also sample on the attributes (e.g. we can randomly pick a subset of the input variables) Random Forest is an example of this approach.

Sliding window
Machine Learning is based on an important assumption that the future is repeating the same pattern as the history. As we all know, as time goes by, this assumption becomes more and more invalid. In other words, we should put more weight in recent history than long term history.

Ensemble method also gives us an elegant way to decay the weight of old data. In this case, we maintain a sliding window of models (say the last 7 days). We learn a model daily and expire the oldest model we compute 7 days ago.

M = M1 + M2.a + M3.a^2 + ... + M7.a^6
M = M / (1 + a + a^2 + ... + a^6)