-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathAdaBoost_binary.py
174 lines (140 loc) · 5 KB
/
AdaBoost_binary.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
# Author: Mehdi Abbassi <[email protected]>
#
# License: GNU/GPL 3
import numpy as np
class DecisionStump:
"""
Base Classifier
"""
def __init__(self, *, gamma, complexity):
"""
setting attributes
"""
self.feature = None
self.threshold = None
self.alpha = None
self.gamma = gamma
self.complexity = complexity
def fit(self, X, y, weights, n_samples, thresholds_set):
"""
constructs a weak base classifier
"""
# non-greedy search to find useful threshold and feature
for feature in thresholds_set.keys():
self.complexity += 1 # add one to the number of calculations
X_column = X[:, feature]
thresholds = thresholds_set[feature]
threshold = np.random.choice(thresholds)
y_predict = np.ones(n_samples)
y_predict[X_column < threshold] = -1
incorrect = y_predict != y
# error fraction
error = np.mean(
np.average(
incorrect,
weights=weights,
axis=0
)
)
# Stop if classification is better than random guessing
# In the case of binary classification, a weak hypothesis
# `h_t` with error significantly larger than 1/2 is of
# equal value to one with error significantly less than
# 1/2 since `h_t` can be replaced by its negation `−h_t`
# (an effect that happens “automatically” in AdaBoost,
# which chooses αt < 0 in such a case). (p. 305)
if np.abs(error - 0.5) > self.gamma:
# Calculate alpha
epsilon = 1e-10 # using epsilon to avoid dividion by zero
self.alpha = 0.5 * np.log(
(1 - error) / (error + epsilon)
)
self.feature, self.threshold = feature, threshold
return self
return self
def predict(self, X):
"""
predicts with a simple rule
"""
n_samples = X.shape[0]
X_column = X[:, self.feature]
predictions = np.ones(n_samples)
predictions[X_column < self.threshold] = -1
return predictions
class AdaBoost:
"""
AdaBoost meta-algorithm
"""
def __init__(self, n_classifiers=200, gamma=12, beta=0.5, random_state=0):
"""
setting attributes
"""
self.n_classifiers = n_classifiers
self.classifiers = []
self.gamma = gamma
self.beta = beta
self.complexity = None
np.random.seed(seed=random_state)
def fit(self, X, y):
"""
calling base learner to construct base classifiers
"""
self.complexity = 0 # to know the number of calculations
n_samples, n_features = X.shape
thresholds = {
feature: np.sort(np.unique(X[:, feature]))[1:]
for feature in range(n_features)
}
# suggested by Schapire >> YouTube: L6BlpGnCYVg 28:25
gamma = self.gamma / np.sqrt(n_samples)
# initialize weights as a uniform distribution
weights = np.full(n_samples, (1/n_samples))
self.classifiers = set()
# iterate through classifiers
gamma_ = gamma
n = 0
while n < self.n_classifiers:
print(f'calling base classifier: {n = }, {gamma_ = }, {self.complexity = }')
base_classifier = DecisionStump(
gamma=gamma_,
complexity=self.complexity
)
base_classifier = base_classifier.fit(
X,
y,
weights,
n_samples,
thresholds
)
self.complexity = base_classifier.complexity
# check if `weak learner` succeds in learning
if base_classifier.feature is None:
gamma_ *= self.beta
print(f'ACHTUNG! {gamma_ = }')
continue
n += 1
print(f'{n = }')
# Calculate predictions and update weights
y_predict = base_classifier.predict(X)
"""
On each round, the weights of incorrectly
classified examples are increased so that,
effectively, hard examples get successively
higher weight, forcing the base learner to
focus its attention on them.
"""
weights *= np.exp(
-1 * base_classifier.alpha * y * y_predict
)
weights /= np.sum(weights)
# Save classifiers
gamma_ = gamma
self.classifiers.add(base_classifier)
def predict(self, X):
"""
predict for multiclass classification
"""
return np.sum(
base_classifier.alpha * base_classifier.predict(X)
for base_classifier in self.classifiers
)