Weighted Majority algorithm used in online learning

experiment.sh

#/bin/sh
#compare the results under different various beta values

betas=(0.01 0.1 0.5 0.9 0.99)

for i in "${betas[@]}"
do
    python main.py $i
done

main.py

"""
Usage:
python main.py :beta-value

Example:
python main.py 0.1

"""
import numpy as np
import sys
from wm import weighted_majority


np.random.seed (1234)


T = 250
n = 10
v = 0.2
beta = float(sys.argv[1])

xs = np.where (np.random.rand (T, n) >= 0.5, 1, -1)

x1s = xs[:, 0]
ys = np.where(np.random.rand (1, T) >= v, x1s, -x1s).T

#create a inner scope so that the value of i will be preserved, refer to this http://stackoverflow.com/questions/2295290/what-do-lambda-function-closures-capture-in-python
hypothesis = [(lambda i: lambda x: x[i])(i) for i in xrange (n)]

weights, cum_loss, cum_loss_nonnoise = weighted_majority(xs, ys, hypothesis, beta)

#ploting the results
import matplotlib.pyplot as plt

rown, coln = 3,4
ts = [5, 10, 12, 15, 20, 28, 40, 60, 100, 140, 190, 250, 310]

for i, t in zip(xrange (rown * coln), ts):
    #the normalized weight
    normalized_weight = weights[t, :] / np.sum (weights[t, :])
    print normalized_weight

    plt.subplot (rown, coln, i+1)

    plt.bar (np.arange (n), normalized_weight)

    plt.title ('t = %s' %t)

plt.savefig ('img/weights-beta=%.2f.png' %beta)

#plotting the cumulative loss function
plt.clf ()

plt.plot (cum_loss)
plt.title ('cumulative loss function when beta = %.2f' %beta)

plt.savefig ('img/cum-loss-beta=%.2f.png' %beta)

#plotting the cumulative loss function considering only the non-noise case
plt.clf ()
plt.plot (cum_loss_nonnoise)
plt.title ('cumulative loss(non-noise) function when beta = %.2f' %beta)
plt.savefig ('img/cum-loss-nonnoise-beta=%.2f.png' %beta)

Weighted-majority-experiment.readme

Three files are included:

1. `weighted_majority.py`: the weighted majority algorithm 
2. `main.py`: the main program which takes a specific beta value and make a list of plots
3. `experiment.sh`: bash script that experiments on a list of beta values. This is a good entry of this gist.

weighted_majority.py

import numpy as np

def weighted_majority (xs, ys, hypothesis, beta):
    #initialize the weights,
    weights = np.ones ((len (xs) + 1, len (hypothesis)))

    cum_loss = np.zeros (len (xs))

    predictions = np.ones (len(hypothesis))

    for i, x, y in zip(xrange (len(xs)), xs, ys):

        for j, h in enumerate(hypothesis):
            predictions[j] = h (x)

            #updating weight
            if predictions[j] == y:
                weights[i+1, j] = weights[i, j]
            else:
                weights[i+1, j] = weights[i, j] * beta

        #voting process
        pos_ind, neg_ind = (predictions  == 1), (predictions  == -1)

        pos_sum, neg_sum = np.sum (weights[i, pos_ind]), np.sum (weights[i, neg_ind])

        output = (1 if pos_sum > neg_sum else -1)

        if y == output: #correct prediction
            cum_loss[i] = (0 if i == 0 else cum_loss[i-1])
        else:#incorrect prediction
            cum_loss[i] = (1 if i == 0 else cum_loss[i-1] + 1)
            
    return weights, cum_loss