Winnow algorithm

""" (1) Receive yes/no predictions, (2) predict on your own, (3) learn the correct answer """ def winnow(sample): sample_len = len(sample) sample_positive = (sum(sample) / sample_len) >= 0.5 weights = [1] * sample_len while True: s = sum(w*x for w, x in zip(weights, sample)) correctly_predicted = 1 if s >= sample_len else 0 if correctly_predicted == sample_positive: break if not correctly_predicted and sample_positive: for i, item in enumerate(sample): if item: weights[i] *= 2.0 if correctly_predicted and not sample_positive: for i, item in enumerate(sample): if item: weights[i] *= 0.5 return weights, correctly_predicted samples = [ [0,1,0,1,0,1,1,1,0,1], [1,0,0,1,0,0,0,1,0,0], [0,0,1,1,1,0,0,1,0,1], [1,1,0,1,1,0,0,0,0,0], [1,1,1,1,1,0,0,0,0,0] ] for sample in samples: weights, prediction = winnow(sample) print('Sample: {0} Weights: {1} Prediction: {2}'.format(sample, weights, prediction)) """ Sample: [0, 1, 0, 1, 0, 1, 1, 1, 0, 1] Weights: [1, 2.0, 1, 2.0, 1, 2.0, 2.0, 2.0, 1, 2.0] Prediction: 1 Sample: [1, 0, 0, 1, 0, 0, 0, 1, 0, 0] Weights: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] Prediction: 0 Sample: [0, 0, 1, 1, 1, 0, 0, 1, 0, 1] Weights: [1, 1, 2.0, 2.0, 2.0, 1, 1, 2.0, 1, 2.0] Prediction: 1 Sample: [1, 1, 0, 1, 1, 0, 0, 0, 0, 0] Weights: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] Prediction: 0 Sample: [1, 1, 1, 1, 1, 0, 0, 0, 0, 0] Weights: [2.0, 2.0, 2.0, 2.0, 2.0, 1, 1, 1, 1, 1] Prediction: 1 """