谁更胜一筹？--随机搜索 V.S. 网格搜索
在进行超参数优化工作时，我不断思考该使用随机搜索还是网格搜索呢？这时候，一个同事给我介绍了一篇由Bergstra和Bengio编写的随机搜索超参数优化论文（链接），文中认为在进行参数优化时随机搜索比网格搜索更有效。
我想通过测试来得到自己的答案，我的实验设置如下。给定空间为（1024,1024）的超参数空间，可由相同形状的矩阵表示。我们为寻找最佳超参数设置的预算是25个实验。因此，这将允许我们进行网格搜索，其中我们设置每个超参数有5个值的组合，或者在该空间中的25个随机搜索。此外，我设置了一个“批量”版本的随机搜索，执行5批次每批次5次随机搜索，优化调整每次批次后的搜索。生成多个这样的随机超参数空间后，计算两种随机搜索优于网格搜索的次数。
生成空间
这一步是生成随机2D超参数空间，例如某种地形。 我使用了Hill地形算法（链接）。 它是一个简单而优雅的算法。 代码如下：
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
from __future__ import division, print_function
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.cm as cm
import operator
%matplotlib inline
SIZE = 1024
NUM_ITERATIONS = 200
terrain = np.zeros((SIZE, SIZE), dtype="float")
mod_iter = NUM_ITERATIONS // 10
for iter in range(NUM_ITERATIONS):
if iter % mod_iter == 0:
print("iteration: {:d}".format(iter))
r = int(np.random.uniform(0, 0.2 * SIZE))
xc, yc = np.random.randint(0, SIZE - 1, 2)
z = 0
xmin, xmax = int(max(xc - r, 0)), int(min(xc + r, SIZE))
ymin, ymax = int(max(yc - r, 0)), int(min(yc + r, SIZE))
for x in range(xmin, xmax):
for y in range(ymin, ymax):
z = (r ** 2) - ((x - xc) ** 2 + (y - yc) ** 2)
if z > 0:
terrain[x, y] += z
print("total iterations: {:d}".format(iter))
# 标准化单元高度
zmin = np.min(terrain)
terrain -= zmin
zmax = np.max(terrain)
terrain /= zmax
# 通过z值平滑地形
terrain = np.power(terrain, 2)
# 乘以255以使地形以灰度表示
terrain = terrain * 255
terrain = terrain.astype("uint8")
从上面代码生成的一个可能的地形如下所示。 我还为它生成了一个等高线图。
1
2
3
4
5
6
7
8
9
plt.title("terrain")
image = plt.imshow(terrain, cmap="gray")
plt.ylim(max(plt.ylim()), min(plt.ylim()))
plt.colorbar(image, shrink=0.8)
plt.title("contours")
contour = plt.contour(terrain, linewidths=2)
plt.ylim(max(plt.ylim()), min(plt.ylim()))
plt.colorbar(contour, shrink=0.8, extend='both')
网格搜索
如您所见，地形只是一个形状矩阵（1024，1024）。 由于我们的预算是25个实验，我们将在这个地形上进行一次5x5的网格搜索。 意即在x和y轴上选择5个等距点，并读取这些（x，y）位置处的地形矩阵值。 执行此操作的代码如下所示。 在轮廓图上的点的最佳值以蓝色标示。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 执行 (5x5)网格搜索
results = []
for x in np.linspace(0, SIZE-1, 5):
for y in np.linspace(0, SIZE-1, 5):
xi, yi = int(x), int(y)
results.append([xi, yi, terrain[xi, yi]])
best_xyz = [r for r in sorted(results, key=operator.itemgetter(2))][0]
grid_best = best_xyz[2]
print(best_xyz)
xvals = [r[0] for r in results]
yvals = [r[1] for r in results]
plt.title("grid search")
contour = plt.contour(terrain, linewidths=2)
plt.ylim(max(plt.ylim()), min(plt.ylim()))
plt.scatter(xvals, yvals, color="b", marker="o")
plt.scatter([best_xyz[0]], [best_xyz[1]], color='b', s=200, facecolors='none', edgecolors='b')
plt.ylim(max(plt.ylim()), min(plt.ylim()))
plt.colorbar(contour)
网格搜索中最优点坐标为（767，767），值为109。
随机搜索
接下来进行实验的是纯随机搜索。由于实验预设为25个，所以这里仅随机生成x值和y值，然后在这些点中搜索地形矩阵值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 进行随机搜索
results = []
xvals, yvals, zvals = [], [], []
for i in range(25):
x = np.random.randint(0, SIZE, 1)[0]
y = np.random.randint(0, SIZE, 1)[0]
results.append((x, y, terrain[x, y]))
best_xyz = sorted(results, key=operator.itemgetter(2))[0]
rand_best = best_xyz[2]
print(best_xyz)
xvals = [r[0] for r in results]
yvals = [r[1] for r in results]
plt.title("random search")
contour = plt.contour(terrain, linewidths=2)
plt.ylim(max(plt.ylim()), min(plt.ylim()))
plt.scatter(xvals, yvals, color="b", marker="o")
plt.scatter([best_xyz[0]], [best_xyz[1]], color='b', s=200, facecolors='none', edgecolors='b')
plt.colorbar(contour)
在该测试中，随机搜索做得更好一些，找到坐标为(663，618)值为103的点。
批量随机搜索
在这种方法中，我决定将我的25个实验预算分成5批，每批5个实验。 查找（x，y）值在每个批次内是随机的。 同时，在每个批次结束时，优胜者会被挑出来进行特殊处理。 采用对象不是在空间中任何地方生成的点，而是在这些点周围绘制一个窗口，并且仅从这些空间进行采样。 在每次迭代时，窗口会进行几何收缩。我试图寻找到目前为止找到的最优点的邻域中的点，希望这个搜索将产生更多的最优点。 同时，我保留剩余的实验探索空间，希望我可能找到另一个最佳点。 其代码如下所示：
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
def cooling_schedule(n, k):
""" 每次运行时减少窗口的大小
n – 批次数目
k – 当前批次的索引号
返回 乘数(0..1) 的大小
"""
return (n - k) / n
results, winners = [], []
for bid in range(5):
print("Batch #: {:d}".format(bid), end="")
# 计算窗口大小
window_size = int(0.25 * cooling_schedule(5, bid) * SIZE)
# 计算出优胜者并把其值加入结果中
# 只保持最优的两点
for x, y, _, _ in winners:
if x < SIZE // 2:
# 中左区
xleft = max(x - window_size // 2, 0)
xright = xleft + window_size
else:
# 中右区
xright = min(x + window_size // 2, SIZE)
xleft = xright - window_size
if y < SIZE // 2:
# 下半区
ybot = max(y - window_size // 2, 0)
ytop = ybot + window_size
else:
# 上半区
ytop = min(y + window_size // 2, 0)
ybot = ytop - window_size
xnew = np.random.randint(xleft, xright, 1)[0]
ynew = np.random.randint(ybot, ytop, 1)[0]
znew = terrain[xnew, ynew]
results.append((xnew, ynew, znew, bid))
# 添加剩余随机点
for i in range(5 - len(winners)):
x = np.random.randint(0, SIZE, 1)[0]
y = np.random.randint(0, SIZE, 1)[0]
z = terrain[x, y]
results.append((x, y, z, 2))
# 找出最优两点
winners = sorted(results, key=operator.itemgetter(2))[0:2]
print(" best: ", winners[0])
best_xyz = sorted(results, key=operator.itemgetter(2))[0]
print(best_xyz)
xvals = [r[0] for r in results]
yvals = [r[1] for r in results]
plt.title("batched random search")
contour = plt.contour(terrain, linewidths=2)
plt.ylim(max(plt.ylim()), min(plt.ylim()))
plt.scatter(xvals, yvals, color="b", marker="o")
plt.scatter([best_xyz[0]], [best_xyz[1]], color='b', s=200, facecolors='none', edgecolors='b')
plt.colorbar(contour)
结束时此空间中的全局最小点坐标（707,682），值为20。
显然，并不是所有的运行都是如此顺利的，也很有可能从上述任何方法发现的点只是一个局部最小值。 此外，没有理由假定网格搜索可能不优于随机搜索，因为随机地形可能在其中一个均匀布置的点下面具有其全局最小点，并且随机搜索可能错过该点。
为了检查这个假设，我对1000个随机地形批量运行上面的代码。 对于每个地形，我为3种方法中的每一种运行25个实验，并为每个方法找到最低（最优）点。我这样做了两次，以确保结果的客观性。代码如下：
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
TERRAIN_SIZE = 1024
NUM_HILLS = 200
NUM_TRIALS = 1000
NUM_SEARCHES_PER_DIM = 5
NUM_WINNERS = 2
nbr_random_wins = 0
nbr_brand_wins = 0
for i in range(NUM_TRIALS):
terrain = build_terrain(TERRAIN_SIZE, NUM_HILLS)
grid_result = best_grid_search(TERRAIN_SIZE, NUM_SEARCHES_PER_DIM)
random_result = best_random_search(TERRAIN_SIZE,
NUM_SEARCHES_PER_DIM**2)
batch_result = best_batch_random_search(TERRAIN_SIZE,
NUM_SEARCHES_PER_DIM,
NUM_SEARCHES_PER_DIM,
NUM_WINNERS)
print(grid_result, random_result, batch_result)
if random_result < grid_result:
nbr_random_wins += 1
if batch_result < grid_result:
nbr_brand_wins += 1
print("# times random search wins: {:d}".format(nbr_random_wins))
print("# times batch random search wins: {:d}".format(nbr_brand_wins))
执行结果如下：
1
2
3
4
5
6
7
8
9
Run-1
------
#-times random search wins: 619 ‘随机搜索优胜次数
#-times batch random search wins: 638 ‘随机批量搜索优胜次数
Run-2
------
#-times random search wins: 640 ‘随机搜索优胜次数
#-times batch random search wins: 621随机批量搜索优胜次数
结果表明随机搜索似乎比网格搜索稍好（因为第一个数字超过500）。 此外，批量版本不一定更好，因为纯随机搜索在第二次运行有更好的结果。
以上是我实验的结果。在这个过程中，我学习了一个有趣的算法来生成地形，也为自己解除了困惑。如果你想亲自尝试，不妨阅读本文核心笔记（链接）以及批处理运行Python版本代码（链接）。
数十款阿里云产品限时折扣中，赶紧点击领劵开始云上实践吧！作者简介：
Sujit Pal是一名程序员，在Healline Networks担任技术管理。喜好研究编程语言Java和Python，喜欢从多角度研究和解决问题。
本文由北邮@爱可可-爱生活 老师推荐，阿里云云栖社区组织翻译。
文章原标题《Random vs Grid Search: Which is Better?》，作者：Sujit Pal ，译者：伍昆
