Hyperopt: Exhaustive search

[jaberg]

It would be nice to provide an exhaustive search option, similar to grid search, that

1. quantizes all real-valued parameters to some user-specified number of options, and then
2. enumerates every single joint assignment of configurations, while respecting the conditional structure established by choice nodes.

For simple spaces, we could use this as a scientifically interesting baseline.

For complex spaces, we can use this to understand and estimate the "size" of a configuration space.

[sbrodeur]

For simple spaces containing only categorical parameters, exhaustive search is possible using a custom search algorithm and limiting the maximum number of evaluations to the exact size of the full search space.

import itertools
import numpy as np

from hyperopt import hp, fmin, Trials
from hyperopt.base import miscs_update_idxs_vals
from hyperopt.pyll.base import Apply


def recursiveFindNodes(root, node_type='switch'):
    nodes = []
    if isinstance(root, (list, tuple)):
        for node in root:
            nodes.extend(recursiveFindNodes(node, node_type))
    elif isinstance(root, dict):
        for node in root.values():
            nodes.extend(recursiveFindNodes(node, node_type))
    elif isinstance(root, (Apply)):
        if root.name == node_type:
            nodes.append(root)

        for node in root.pos_args:
            if node.name == node_type:
                nodes.append(node)
        for _, node in root.named_args:
            if node.name == node_type:
                nodes.append(node)
    return nodes


def parameters(space):
    # Analyze the domain instance to find parameters
    parameters = {}
    if isinstance(space, dict):
        space = list(space.values())
    for node in recursiveFindNodes(space, 'switch'):

        # Find the name of this parameter
        paramNode = node.pos_args[0]
        assert paramNode.name == 'hyperopt_param'
        paramName = paramNode.pos_args[0].obj

        # Find all possible choices for this parameter
        values = [literal.obj for literal in node.pos_args[1:]]
        parameters[paramName] = np.array(range(len(values)))
    return parameters


def spacesize(space):
    # Compute the number of possible combinations
    params = parameters(space)
    return np.prod([len(values) for values in params.values()])


def suggest(new_ids, domain, trials, seed):

    # Analyze the domain instance to find parameters
    params = parameters(domain.expr)

    # Compute all possible combinations
    s = [[(name, value) for value in values] for name, values in params.items()]
    values = list(itertools.product(*s))

    rval = []
    for _, new_id in enumerate(new_ids):
        # -- sample new specs, idxs, vals
        idxs = {name: np.array([new_id]) for name in params.keys()}
        vals = {name: np.array([value]) for name, value in values[new_id]}

        new_result = domain.new_result()
        new_misc = dict(tid=new_id, cmd=domain.cmd, workdir=domain.workdir)
        miscs_update_idxs_vals([new_misc], idxs, vals)
        rval.extend(trials.new_trial_docs([new_id],
                                          [None], [new_result], [new_misc]))
    return rval


# define an objective function
def objective(args):
    print(args)
    return 0


space = {
    'a': hp.choice('a', ['x', 'y', 'z']),
    'b': hp.choice('b', [1, 2]),
}

trials = Trials()
best = fmin(fn=objective,
            space=space,
            trials=trials,
            algo=suggest,
            max_evals=spacesize(space),
            show_progressbar=False)

Which results in the following output:

{'a': 'x', 'b': 1}
{'a': 'x', 'b': 2}
{'a': 'y', 'b': 1}
{'a': 'y', 'b': 2}
{'a': 'z', 'b': 1}
{'a': 'z', 'b': 2}

I haven't tried yet with nested spaces.

[michaelmior]

Why not just avoid specifying max_evals entirely? (Serious question, but it seems like hyperopt should stop on it's own when no new values are produced.)

[sbrodeur]

Indeed - a very Pythonic way to do this is with the suggestion algorithm implemented as a iterator / generator and throwing a StopIteration exception once finished. It only requires the fmin function to catch this and abort the optimization.

[sbrodeur]

After carefully reading the source code of the FMinIter class, the suggestion algorithm only needs to return an empty list to stop the optimization loop!

Here is an updated code for exhaustive search over complex discrete spaces:

import numpy as np

from functools import partial
from hyperopt import hp, fmin, Trials, pyll
from hyperopt.base import miscs_update_idxs_vals
from hyperopt.pyll.base import dfs, as_apply
from hyperopt.pyll.stochastic import implicit_stochastic_symbols


class ExhaustiveSearchError(Exception):
    pass


def validate_space_exhaustive_search(space):
    supported_stochastic_symbols = ['randint', 'quniform', 'qloguniform', 'qnormal', 'qlognormal', 'categorical']
    for node in dfs(as_apply(space)):
        if node.name in implicit_stochastic_symbols:
            if node.name not in supported_stochastic_symbols:
                raise ExhaustiveSearchError('Exhaustive search is only possible with the following stochastic symbols: ' + ', '.join(supported_stochastic_symbols))


def suggest(new_ids, domain, trials, seed, nbMaxSucessiveFailures=1000):

    # Build a hash set for previous trials
    hashset = set([hash(frozenset([(key, value[0]) if len(value) > 0 else ((key, None))
                                   for key, value in trial['misc']['vals'].items()])) for trial in trials.trials])

    rng = np.random.RandomState(seed)
    rval = []
    for _, new_id in enumerate(new_ids):
        newSample = False
        nbSucessiveFailures = 0
        while not newSample:
            # -- sample new specs, idxs, vals
            idxs, vals = pyll.rec_eval(
                domain.s_idxs_vals,
                memo={
                    domain.s_new_ids: [new_id],
                    domain.s_rng: rng,
                })
            new_result = domain.new_result()
            new_misc = dict(tid=new_id, cmd=domain.cmd, workdir=domain.workdir)
            miscs_update_idxs_vals([new_misc], idxs, vals)

            # Compare with previous hashes
            h = hash(frozenset([(key, value[0]) if len(value) > 0 else (
                (key, None)) for key, value in vals.items()]))
            if h not in hashset:
                newSample = True
            else:
                # Duplicated sample, ignore
                nbSucessiveFailures += 1

            if nbSucessiveFailures > nbMaxSucessiveFailures:
                # No more samples to produce
                return []

        rval.extend(trials.new_trial_docs([new_id],
                                          [None], [new_result], [new_misc]))
    return rval


# Define an objective function
def objective(args):
    print(args)
    return 0


space = hp.choice('a', [{'a': 'x'},
                        {'a': 'y', 'b': hp.choice('c', [1, 2, 3])},
                        {'a': 'z', 'b': hp.choice('e', [hp.choice('f', [0.0, 1.0]),
                                                        hp.quniform('g', 10.0, 100.0, 10)])}
                        ])

validate_space_exhaustive_search(space)

trials = Trials()
best = fmin(fn=objective,
            space=space,
            trials=trials,
            algo=partial(suggest, nbMaxSucessiveFailures=1000),
            max_evals=np.inf,
            show_progressbar=False)

Which returns all the 16 possible configurations:

{'a': 'x'}
{'a': 'y', 'b': 1}
{'a': 'z', 'b': 1.0}
{'a': 'z', 'b': 0.0}
{'a': 'z', 'b': 100.0}
{'a': 'z', 'b': 90.0}
{'a': 'y', 'b': 3}
{'a': 'z', 'b': 50.0}
{'a': 'y', 'b': 2}
{'a': 'z', 'b': 20.0}
{'a': 'z', 'b': 40.0}
{'a': 'z', 'b': 60.0}
{'a': 'z', 'b': 80.0}
{'a': 'z', 'b': 30.0}
{'a': 'z', 'b': 70.0}
{'a': 'z', 'b': 10.0}

The exhaustive search is based on random sampling of the space and avoiding any duplicated sample evaluation. It supports the usage of 'randint', 'quniform', 'qloguniform', 'qnormal', 'qlognormal' and 'categorical' within complex, conditional spaces.

[paalvibe]

@sbrodeur Thanks for your excellent code. However, in a search space of 1152 variations, it sometimes misses approximately 1-10 variations. I managed to fix it in a hacky manner by adding a semaphore to the code. Should be improved, but it works at least:

import threading
pool_sema = threading.Semaphore()
def grid_search_suggest(new_ids, domain, trials, seed, nbMaxSucessiveFailures=1000):
    """Not efficient to have shared semaphore pool_sema for all invocations of this function
    but let's accept it for now.

    Without the semaphore, the grid_search wil sometimes miss about 0-10 combinations per 1000."""
    global pool_sema
    pool_sema.acquire()
    # Build a hash set for previous trials
    hashset = set([hash(frozenset([(key, value[0]) if len(value) > 0 else ((key, None))
                                   for key, value in trial['misc']['vals'].items()])) for trial in trials.trials])

    rng = np.random.RandomState(seed)
    rval = []
    for _, new_id in enumerate(new_ids):
        newSample = False
        nbSucessiveFailures = 0
        while not newSample:
            # -- sample new specs, idxs, vals
            idxs, vals = pyll.rec_eval(
                domain.s_idxs_vals,
                memo={
                    domain.s_new_ids: [new_id],
                    domain.s_rng: rng,
                })
            new_result = domain.new_result()
            new_misc = dict(tid=new_id, cmd=domain.cmd, workdir=domain.workdir)
            miscs_update_idxs_vals([new_misc], idxs, vals)

            # Compare with previous hashes
            h = hash(frozenset([(key, value[0]) if len(value) > 0 else (
                (key, None)) for key, value in vals.items()]))
            if h not in hashset:
                newSample = True
            else:
                # Duplicated sample, ignore
                nbSucessiveFailures += 1

            if nbSucessiveFailures > nbMaxSucessiveFailures:
                # No more samples to produce
                pool_sema.release()
                return []

        rval.extend(trials.new_trial_docs([new_id],
                                          [None], [new_result], [new_misc]))
    pool_sema.release()
    return rval