-
Notifications
You must be signed in to change notification settings - Fork 9
/
hyperband.py
326 lines (270 loc) · 13.4 KB
/
hyperband.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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
"""
We implement additional hyperparameter optimization methods not present in
https://scikit-optimize.github.io/.
Gist: https://gist.github.com/Deepblue129/2c5fae9daf0529ed589018c6353c9f7b
"""
import math
import logging
import random
import sys
from tqdm import tqdm
logger = logging.getLogger(__name__)
def _random_points(dimensions, n_points, random_seed=None):
""" Generate a random sample of points from dimensions """
# NOTE: We supply as `randint` to `random_state`; otherwise, dimensions with the same distribution would
# recive the same sequence of random numbers.
# We seed `random` so the random seeds generated are deterministic.
random.seed(random_seed)
points = {
d.name: d.rvs(n_samples=n_points, random_state=random.randint(0, 2**32))
for d in dimensions
}
points = [{k: points[k][i] for k in points} for i in range(n_points)]
return points
def successive_halving(
objective,
dimensions,
max_resources_per_model=81,
downsample=3, # Test random downsamples work and check boundaries
initial_resources=3,
n_models=45,
random_seed=None,
progress_bar=True):
"""
Adaptation of the Successive Halving algorithm.
tl;dr keep the best models every iteration of the `initial_models` downsampling each time
Adaptation: Instead of running for N / 2 models for 2T, we run N / 2 models for T**downsample.
This adaptation is the same adaptation of Successive Halving in hyperband.
Reference: http://proceedings.mlr.press/v51/jamieson16.pdf
Reference: http://www.argmin.net/2016/06/23/hyperband/
TODO: Splitting in half is a fairly random number. We could possibly look for a better split
point. For example, we could use the large margin to split points. Or predict the performance
of hyperparameters would do well in the future.
Args:
objective (callable): objective function to minimize
Named Args:
resources (int): number of resources (e.g. epochs) to use while training model
checkpoint (any): saved data from past run
**hyperparameters (any): hyperparameters to run
Returns:
score (float): score to minimize
checkpoint (any): saved data from run
dimensions (list of skopt.Dimensions): list of dimensions to minimize under
max_resources_per_model: Max number of resources (e.g. epochs) to use per model
downsample: Downsampling of models (e.g. halving is a downsampling of 2)
initial_resources: Number of resources (e.g. epochs) to use initially to evaluate first
round.
n_models (int): Number of models to evaluate
random_seed (int, optional): Random seed for generating hyperparameters
progress_bar (boolean or tqdm): Iff to use or update a progress bar.
Returns:
scores (list of floats): Scores of the top objective executions
hyperparameters (list of lists of dict): Hyperparameters with a one to one correspondence
to scores.
"""
if downsample <= 1:
raise ValueError('Downsample must be > 1; otherwise, the number of resources allocated' +
'does not grow')
round_n_models = lambda n: max(round(n), 1)
total_resources_per_model = 0
hyperparameters = _random_points(dimensions, round_n_models(n_models), random_seed)
checkpoints = [None for _ in range(round_n_models(n_models))]
scores = [math.inf for _ in range(round_n_models(n_models))]
# Create a new progress bar
remember_to_close = False
if not isinstance(progress_bar, tqdm) and progress_bar:
remember_to_close = True
# TODO: Compute the tqdm total
progress_bar = tqdm()
# Keep tabs on a set of stats
setattr(progress_bar, 'stats', {'min_score': math.inf, 'models_evaluated': 0})
while total_resources_per_model < max_resources_per_model:
# Compute number of resources to continue running each model with
if total_resources_per_model == 0:
update_n_resources = initial_resources
else:
update_n_resources = min(
total_resources_per_model * downsample - total_resources_per_model,
max_resources_per_model - total_resources_per_model)
results = []
for score, checkpoint, params in zip(scores, checkpoints, hyperparameters):
new_score, new_checkpoint = objective(
resources=update_n_resources, checkpoint=checkpoint, **params)
new_score = min(score, new_score)
results.append(tuple([new_score, new_checkpoint]))
if isinstance(progress_bar, tqdm):
progress_bar.update(update_n_resources)
if progress_bar.stats['min_score'] > new_score:
progress_bar.stats['min_score'] = new_score
progress_bar.set_postfix(progress_bar.stats)
total_resources_per_model += update_n_resources
# NOTE: If this is not the last
is_last_iteration = total_resources_per_model >= max_resources_per_model
if not is_last_iteration:
# Sort by minimum score `k[0][0]`
results = sorted(zip(results, hyperparameters), key=lambda k: k[0][0])
models_evaluated = len(results) - round_n_models(n_models / downsample)
results = results[:round_n_models(n_models / downsample)]
# Update `hyperparameters` lists
results, hyperparameters = zip(*results)
n_models = n_models / downsample
else:
models_evaluated = len(results)
# Update `scores` and `checkpoints` lists
scores, checkpoints = zip(*results)
if isinstance(progress_bar, tqdm):
progress_bar.stats['models_evaluated'] += models_evaluated
progress_bar.set_postfix(progress_bar.stats)
if remember_to_close:
progress_bar.close()
return scores, hyperparameters
def hyperband(objective,
dimensions,
max_resources_per_model=81,
downsample=3,
total_resources=None,
random_seed=None,
progress_bar=True):
"""
Adaptation of the Hyperband algorithm
tl;dr search over the space of successive halving hyperparameters
Adaptation: Originally Hyperband was implemented with the assumption that we cannot reuse
models. We redid the math allowing for reusing models. This is particularly helpful in speeding
up 1 GPU hyperparameter optimization. Just to clarify, by reusing models, we mean that
given hyperparameters `x` and epochs `y`, we can use one model to evaluate all `y` integers
with hyperparameters `x`.
Reference: https://arxiv.org/pdf/1603.06560.pdf
Reference: http://www.argmin.net/2016/06/23/hyperband/
TODO: Implement extension to hyperband proporting an increase of x4:
https://arxiv.org/pdf/1705.10823.pdf
http://www.ijcai.org/Proceedings/15/Papers/487.pdf
Args:
objective (callable): objective function to minimize
Named Args:
resources (int): number of resources (e.g. epochs) to use while training model
checkpoint (any): saved data from past run
**hyperparameters (any): hyperparameters to run
Returns:
score (float): score to minimize
checkpoint (any): saved data from run
dimensions (list of skopt.Dimensions): list of dimensions to minimize under
max_resources_per_model (float): Max number of resources (e.g. epochs) to use per model
downsample (int): Downsampling of models (e.g. halving is a downsampling of 2)
total_resources (optional): Max number of resources hyperband is allowed to use over the
entirety of the algorithm.
random_seed (int, optional): Random seed for generating hyperparameters
progress_bar (boolean, optional): Boolean for displaying tqdm
Returns:
scores (list of floats): Scores of the top objective executions
hyperparameters (list of lists of dict): Hyperparameters with a one to one correspondence
to scores.
"""
if downsample <= 1:
raise ValueError('Downsample must be > 1; otherwise, the number of resources allocated' +
'does not grow')
all_scores = []
all_hyperparameters = []
# Number of times to run hyperband
# Ex. `max_resources_per_model = 81 and downsample = 3`
# Then => initial_resources = [1, 3, 9, 27, 81]
# And => `hyperband_rounds = 5`
# And => `successive_halving_rounds = [5, 4, 3, 2, 1]`
n_hyperband_rounds = math.floor(math.log(max_resources_per_model, downsample)) + 1
if total_resources is None:
# TODO: Multiply by the number of dimensions so it scales the number of models
# given the large space
total_resources_per_round = max_resources_per_model * n_hyperband_rounds
else:
total_resources_per_round = total_resources / n_hyperband_rounds
total_models_evaluated = 0
if progress_bar:
progress_bar = tqdm(total=total_resources_per_round * n_hyperband_rounds)
setattr(progress_bar, 'stats', {'min_score': math.inf, 'models_evaluated': 0})
for i in reversed(range(n_hyperband_rounds)):
n_successive_halving_rounds = i + 1
# NOTE: Attained by running the below code on https://sandbox.open.wolframcloud.com:
# Reduce[Power[d, j - 1] * (x / Power[d, j]) +
# Sum[(Power[d, i] - Power[d, i - 1]) * (x / Power[d, i]), {i, j, k}] == e
# && k >=j>=1 && k>=1 && d>=1, {x}]
# `e` is `total_resources_per_round`
# `x` is `n_models`
# `k - j` is `i`
# `d` is downsample
# The summation is similar to the successive halving rounds loop. It computes the number
# of resources with reuse run in total. This is different from hyperband that assumes
# no reuse.
n_models = downsample * total_resources_per_round
n_models /= downsample * (1 + i) - i
n_models /= downsample**(-i + n_hyperband_rounds - 1)
total_models_evaluated += n_models
scores, hyperparameters = successive_halving(
objective=objective,
dimensions=dimensions,
max_resources_per_model=max_resources_per_model,
downsample=downsample,
initial_resources=max_resources_per_model / downsample**i,
n_models=n_models,
random_seed=random_seed,
progress_bar=progress_bar)
logger.info('Finished hyperband round: %d of %d', n_hyperband_rounds - i - 1,
n_hyperband_rounds - 1)
all_scores.extend(scores)
all_hyperparameters.extend(hyperparameters)
if isinstance(progress_bar, tqdm):
progress_bar.close()
logger.info('Total models evaluated: %f', total_models_evaluated)
logger.info('Total resources used: %f', total_resources_per_round * n_hyperband_rounds)
logger.info('Total resources used per model on average: %f',
total_models_evaluated / total_resources_per_round * n_hyperband_rounds)
return all_scores, all_hyperparameters
### TEST ###
import unittest
import random
from skopt.space import Real, Integer
def config_logging():
""" Configure the root logger with basic settings.
"""
logging.basicConfig(
format='[%(asctime)s][%(processName)s][%(name)s][%(levelname)s] %(message)s',
level=logging.INFO,
stream=sys.stdout)
config_logging()
mock_dimensions = [Integer(1, 100, name='integer')]
def mock(resources, integer=0, checkpoint=None):
# `integer` is a hyperparameter set the first batch
if checkpoint is not None:
return checkpoint, checkpoint
return integer, integer
class TestHyperparameterOptimization(unittest.TestCase):
def test_hyperband_simple(self):
# Basic check on hyperband
scores, hyperparameters = hyperband(objective=mock, dimensions=mock_dimensions)
for score, hyperparameter in zip(scores, hyperparameters):
self.assertEqual(score, hyperparameter['integer'])
def test_successive_halving_simple(self):
# Basic check on successive halving
scores, hyperparameters = successive_halving(objective=mock, dimensions=mock_dimensions)
for score, hyperparameter in zip(scores, hyperparameters):
self.assertEqual(score, hyperparameter['integer'])
def test_hyperband_no_progress_bar(self):
# Basic check on hyperband
scores, hyperparameters = hyperband(
objective=mock, dimensions=mock_dimensions, progress_bar=False)
for score, hyperparameter in zip(scores, hyperparameters):
self.assertEqual(score, hyperparameter['integer'])
def test_successive_halving_no_progress_bar(self):
# Basic check on successive halving
scores, hyperparameters = successive_halving(
objective=mock, dimensions=mock_dimensions, progress_bar=False)
for score, hyperparameter in zip(scores, hyperparameters):
self.assertEqual(score, hyperparameter['integer'])
def test_successive_halving_downsample(self):
with self.assertRaises(ValueError):
successive_halving(
objective=mock,
dimensions=mock_dimensions,
progress_bar=False,
downsample=1,
n_models=45)
if __name__ == '__main__':
unittest.main()