fiesta.sequential_halving

Sequential Halving is the adaptive FB approach which does not spend the budget fairly across the \(N\) models but rather spends the budget more on promising/better models.

It breaks the problem down into rounds of \(\log_2N\), where in each round half of the worse performing models are removed from the canditae models \(S\) until only the best performing model is left (At the start the number of candiate models \(S\) = \(N\)). In each round each model is evaluated \(\lfloor\frac{T}{|S|\lceil\log_2N\rceil}\rfloor\). The models performance each round is based on the models evaluations across all of the rounds. In the last round of 2 models each model is evaluated \(2^{\lceil\log_2N\rceil}-1\) times.

Example:

\(T=16\), \(N=4\):

Round

Candidate Models

#Evaluations

1

S = {m1, m2, m3, m4}

2

2

S = {m2, m4}

4

output

S = {m2}
Caveat

The metric the evaluations produce must be bounded which is typical for a lot of the metrics in NLP e.g. \([0,1]\) for accuracy, recall, precision, and F1. This caveat is to ensure strong theoretical guarantees of choosing the best model (Karnin et al. 2013).

Note

This approach has been shown to outperform the standard non-adpative FB approach as shown in this paper associated to this code base and the following notebook tutorial from this code based. Outperform here means that given the same budget \(T\) we are more likely to find the best model.

fiesta.fiesta.sequential_halving(data, model_functions, split_function, budget, logit_transform=False)[source]
Parameters

  • data (List[Dict[str, Any]]) – A list of dictionaries, that as a whole represents the entire dataset. Each dictionary within the list represents one sample from the dataset.

  • model_functions (List[Callable[[List[Dict[str, Any]], List[Dict[str, Any]]], float]]) – A list of functions that represent different models e.g. pytorch model. Which take a train and test dataset as input and returns a metric score e.g. Accuracy. The model functions should not have random seeds set else it defeats the point of finding the best model independent of the random seed and data split.

  • split_function (Callable[[List[Dict[str, Any]]], Tuple[List[Dict[str, Any]], List[Dict[str, Any]]]]) – A function that can be used to split the data into train and test splits. This should produce random splits each time it is called. If you would like to use a fixed split each time, you can hard code this function to produce a fixed split each time.

  • budget (int) – The total number of evaluations

  • logit_transform (bool) – Whether to transform the model function’s returned metric score by the logit function.

Return type

Tuple[int, List[float], List[List[float]]]

Returns

Tuple containing 3 values:

  1. The best performing model function index given the budget

  2. The number of times each model was evaluated as a proportion of the total number of evaluations

  3. The scores that each model generated when evaluated.

NOTE

That if the logit transform is True then the last item in the tuple would be scores that have been transformed by the logit function.

Raises

ValueError – Given budget \(T\) and the models \(N\) this will be raised if: \(T < (|N| * \log_2|N|)\)