selector.generators.surrogates.cppl_surrogate

This module contains functions for the CPPL surrogate.

Classes

CPPL(scenario, seed, features[, pool_size, ...])

Surrogate from CPPL.

class selector.generators.surrogates.cppl_surrogate.CPPL(scenario, seed, features, pool_size=192, alpha=1, gamma=0.1, w=0.1, random_prob=0.2, mutation_prob=0.8, pca_dimension_configurations=8, pca_dimension_instances=8, model_update='Batch', v_hat_norm=None, theta_norm='zero_one', feature_normaliser='max', ensemble=True)

Bases: object

Surrogate from CPPL.

Note

Implementation based on the paper: “Pool-based realtime algorithm configuration: A preselection bandit approach”

Parameters:

• s (selector.scenario.Scenario) – AC scenario.

• seed (int) – Random seed.

• features (ndarray) – Problem instance features.

• pool_size (int) – Number of Configurations to keep in CPPL pool.

• alpha (int) – CPPL hyperparameter alpha, see paper for details.

• gamma (float) – CPPL hyperparameter gamma, see paper for details.

• w (float) – CPPL hyperparameter w, see paper for details.

• random_prob (float) – Probability for a random Configuration being generated.

• mutation_prob (float) – Probability for mutation in crossover mechanism.

• pca_dimension_configurations (int) – PCA dimension for configuration values.

• pca_dimension_instances (int) – PCA dimension for instance feature values.

• model_update (str) – Update mode for model [“SGD”, “Batch”].

• v_hat_norm (str) – Norm to use on v_hat [None, “max”, “zero_one”], see paper for details.

• theta_norm (str) – Norm to use on theta [None, “max”, “zero_one”], see paper for details.

• feature_normaliser (str) – Which normalization to use on instance feature values [“max”, “zero_one”].

• ensemble (bool) – True, if accounting for same configuration with different IDs needs to be made.

add_to_pool(past_instances)

Add the most promising newly created configurations to the pool

Parameters:

past_instances (list of str) – Instance set of the prior tournament.

calibrate_pca()

Calibarte the PCA and Scalers for the featuremap

compute_a(theta, tried_conf_ids, instance_id)

Compute numerator for gradient and hessian computation.

Parameters:

• theta (ndarray) – Parameter vector theta_bar, based on winner feedback.

• tried_conf_ids (list of uuid.UUID) – IDs of configurations that participated in the tournament.

• instance_id (str) – Name of instance the feedback was generated on.

Returns:

Numerator for further compuations.

Return type:

ndarray

compute_b(theta, tried_conf_ids, instance_id)

Compute denominator for gradient and hessian computation.

Parameters:

• theta (ndarray) – Parameter vector theta_bar, based on winner feedback.

• tried_conf_ids (list of uuid.UUID) – IDs of configurations that participated in the tournament.

• instance_id (str) – Name of instance the feedback was generated on.

Returns:

Denominator for further compuations.

Return type:

ndarray

compute_c(theta, tried_conf_ids, instance_id)

Compute second numerator for hessian computation.

Parameters:

• theta (ndarray) – Parameter vector theta_bar, based on winner feedback.

• tried_conf_ids (list of uuid.UUID) – IDs of configurations that participated in the tournament.

• instance_id (str) – Name of instance the feedback was generated on.

Returns:

Second numerator for further compuations.

Return type:

ndarray

compute_confidence(theta, instance_id, conf)

Compute the confidence for an instance/conf combination.

Parameters:

• theta (ndarray) – Parameter vector theta_bar, based on winner feedback.

• instance_id (str) – Name of an instance.

• conf (uuid.UUID) – ID of a configuration.

Returns:

Confidence.

Return type:

float

compute_feature_map(conf, instance_features)

For a configuration/instance pair, compute the quadratic feature map and scale.

Parameters:

• conf (selector.pool.Configuration) – Configuration.

• instance_features (ndarray) – Numpy array of instance features.

Returns:

Scaled quadratic problem instance features.

Return type:

ndarray

compute_gradient(theta, winner_id, tried_confs, instance_id)

Compute the gradient for a given feedback.

Parameters:

• theta (ndarray) – Parameter vector theta_bar, based on winner feedback.

• winner_id (uuid.UUID) – ID of the configuration winning the tournament.

• tried_conf_ids (list of uuid.UUID) – IDs of configurations that participated in the tournament.

• instance_id (str) – Name of instance the feedback was generated on.

Returns:

Gradient for further compuations.

Return type:

ndarray

compute_hessian(theta, winner_id, tried_confs, instance_id)

Compute the hessian for a given feedback.

Parameters:

• theta (ndarray) – Parameter vector theta_bar, based on winner feedback.

• winner_id (uuid.UUID) – ID of the configuration winning the tournament.

• tried_conf_ids (list of uuid.UUID) – IDs of configurations that participated in the tournament.

• instance_id (str) – Name of instance the feedback was generated on.

Returns:

Hessian for further compuations.

Return type:

ndarray

create_new_conf(parent_one, parent_two)

Create new configurations based on a genetic procedure described.

Parameters:

• parent_one (selector.pool.Configuration) – First configuration for the crossover.

• parent_two (selector.pool.Configuration) – Second configuration for the crossover.

Returns:

Resulting configuration.

Return type:

selector.pool.Configuration

delete_from_pool(instance_set)

Based on the feedback delete poorly performing configurations from the pool.

Parameters:

instance_set (list of str) – Instance set the feedback was generated on.

expected_improvement(suggestions, next_instance_set)

Compute expected improvement via CPPL model.

Parameters:

• suggestions (list of selector.pool.Configuration) – Suggested configurations.

• next_instance_set (list of str) – List of next instances to be run.

Returns:

ei: Expected improvements.

Return type:

ndarray

from_log_space()

Not implemented.

get_suggestions(scenario, n_to_select, d, r, next_instance_set, instance_features=None)

Suggest configurations to run next based on the next instance set to run on.

Parameters:

• scenario (selector.scenario.Scenario) – AC scenario.

• n_to_select (int) – Number of configurations to return.

• d (list of selector.pool.Tournament) – Tournament history.

• r (dict) – Performances of the configuration on the instance set of the tournament.

• next_instance_set (list of str) – Instance set to run on in the next tournament.

• instance_features (ndarray) – Problem instance features.

Returns:

• list of selector.pool.Configuration, Suggested configurations.

• list of list of float, Utility and confidence pairs according to selected configurations.

Return type:

tuple

predict(suggestions, next_instance_set)

Predict performance/quality of configurations with CPPL.

Parameters:

• suggestions (list of selector.pool.Configuration) – Suggested configurations.

• next_instance_set – List of next instances to run the tournament on.

Returns:

• v: ndarray, Mean of predicted performance/quality.

• c: ndarray, Variance of predicted performance/quality.

Return type:

tuple

probability_improvement(suggestions, results, next_instance_set)

Compute probability of improvement.

Parameters:

• suggestions (list of selector.pool.Configuration) – Suggested configurations.

• next_instance_set – List of next instances to be run.

• results (dict) – Performances of the configuration on the instance set of the tournament.

• next_instance_set – List of next instances to run the tournament on.

Returns:

pi_output: Probabilities of improvement.

Return type:

ndarray

process_parameter()

Figure out the parameter types and get values/calibrate encoding and scaling

scale_conf(configuration)

Scale and encode a configuration. Continuous/integer parameters are scaled between 0 and 1. Categorical parameters are one-hot encoded.

Parameters:

configuration (selector.pool.Configuration) – Configuration.

Returns:

Scaled and encoded configuration values.

Return type:

ndarray

select_from_set(conf_set, instance_set, n_to_select)

For a set of configurations and instances select the most promising configurations

Parameters:

• conf_set (list of selector.pool.Configuration) – Set of configurations to select from.

• instance_set (list of str) – Instance set the next tournament will be run on.

• n_to_select (int) – Number of configurations to select from the set.

Returns:

• list of selector.pool.Configuration, Selected configurations.

• list of list of float, Utility and confidence pairs according to selected configurations.

Return type:

tuple

suggest_from_outside_pool(conf_set, n_to_select, next_instance_set, instance_features=None)

Suggest configurations to run next that are not in the CPPL pool.

Parameters:

• conf_set (list of selector.pool.Configuration) –

• n_to_select (int) – Number of configurations to return.

• next_instance_set (list of str) – Instance set to run on in the next tournament.

• instance_features (ndarray) – Problem instance features.

Returns:

• suggest: list of selector.pool.Configuration, Suggested configurations.

• ranking: list of list of float, Utility and confidence pairs according to selected configurations.

Return type:

tuple

to_log_space()

Not implemented.

update(previous_tournament, c, results, terminations, instance_features=None, ac_runtime=None)

Update the model with given feedback.

Parameters:

• results (dict) – Feedback for the configuration-instance pairs in the previous tournament.

• previous_tournament (selector.pool.Tournament) – Tournament.

• c (list of selector.pool.Configuration) – Configurations participating in the previous tournament.

• results – Performances of the configuration on the instance set of the tournament.

• terminations (dict) – Configurations that were terminated on instances.

• instance_features (ndarray) – Problem instance features.

• ac_runtime (int) – The total runtime of Selector in seconds so far.

update_feature_store(conf, instance)

For a configuration/instance pair, compute the features and store them in a feature store for later use.

Parameters:

• conf (selector.pool.Configuration) – Configuration.

• instance (str) – Instance name.

update_model_mini_batch(winner_ids, tried_confs, instance_ids)

Update the thetas of the model for feedback over multiple instances.

Parameters:

• winner_id (uuid.UUID) – ID of the configuration winning the tournament.

• tried_conf_ids (list of uuid.UUID) – IDs of configurations that participated in the tournament.

• instance_id (str) – Name of instance the feedback was generated on.

update_model_single_observation(winner_id, tried_confs, instance_id)

Update the thetas of the model for a single instance feedback.

Parameters:

• winner_id (uuid.UUID) – ID of the configuration winning the tournament.

• tried_conf_ids (list of uuid.UUID) – IDs of configurations that participated in the tournament.

• instance_id (str) – Name of instance the feedback was generated on.

update_running_sums(theta, winner_id, tried_confs, instance_id)

Update the rolling sums of gradients and hessian for a feedback.

Parameters:

• theta (ndarray) – Parameter vector theta_bar, based on winner feedback.

• winner_id (uuid.UUID) – ID of the configuration winning the tournament.

• tried_conf_ids (list of uuid.UUID) – IDs of configurations that participated in the tournament.

• instance_id (str) – Name of instance the feedback was generated on.