Automl

Note: this reduction is experimental and is subject to change

Goal:

The primary goal of automl is to provide users with a hands-off method to get an optimal learning configuration without prior experience using VW or an in-depth understanding of their dataset. A "configuration" is a general term which can be extended to any aspect of VW (enabled reduction, # of passes, etc…) but as of now a configuration will specify the set of namespace interactions used in a contextual bandit problem. More specifically, a configuration specifies a set of interactions which will be excluded from the default configuration.

Defining a Configuration, and the Default Configuration (-q ::)

The default configuration for automl will include all quadratic interactions (specified with the -q :: flag in VW). This means that interactions will be generated for all permutation of each feature in all the seen namespaces. All other configurations will be defined by a set of namespace interactions which will be excluded from the default configuration. Thus the default configuration's exclusion set will be empty, whereas other configuration's exclusion sets will contain namespace interactions which will be removed from the full quadratic set.

Namespace Counter

Automl gains an understanding of the dataset it is processing in a streaming fashion. Upon initialization, it has no knowledge of which namespaces are present, and their frequencies. As examples are fed to atuoml, it stores a counter of which namespaces have been seen and how often they occur. This information is essential in determining which interactions exist, and which are more important when generating new configs and deciding how to use them.

Generating New Configs (One-Diff Config Oracle using oracle_type --one_diff)

Automl implements a "one-diff" config oracle by default (can be spcified with --oracle_tpye one_diff) which generates all interaction sets with a difference of one interaction from the current "champion" (this will be described later). Say the set of seen namespaces includes {A, B, C}, then the list of all quadratic interactions includes {AA, AB, AC, BB, BC, CC}. Consider that the champion configuration has the interactions {AA, AB, AC, BB} and exclusions {BC, CC}. The one-diff oracle will then generate all interaction sets with one more interaction than the champ and one less interactions than the champ. Thus it will include these sets with one-diff additions: {AA, AB, AC, BB, BC}, {AA, AB, AC, BB, CC}, and these sets with one-diff removals: {AA, AB, AC}, {AA, AB, BB}, {AA, AC, BB}, {AB, AC, BB}.

Generating New Configs (Random Config Oracle using oracle_type --rand)

Automl implements a random config oracle(can be specified with --oracle_type rand) which generates random configs around the current "champion". The oracle will generate a config which includes one more (random) exclusion than the current champion. Upon initialization, the default configuration (-q ::) will be considered the champion. Automl will process one example (in order to collect some namespace information) before generating new configs. Say the first example includes namespace 'A', 'B', and 'C', then the champion will have interactions {AA, AB, AC, BB, BC, CC} and an exclusion set {}. When the config oracle is called to generate a new config, it will add one interaction from the current champs interaction set to its exclusion set. Thus a new config could be generated with interactions {AA, AC, BB, BC, CC} and exclusion set {AB}. Currently the constant CONFIGS_PER_CHAMP_CHANGE is set to 5, meaning that the config oracle will generate 5 new configs in this fashion whenever invoked.

Generating New Configs (One-Diff-Inclusion Oracle using oracle_type --one_diff_inclusion)

This is equivalent to the standard one-diff oracle, but the champ will start with no interactions. This oracle should be better at gradually finding the best interactions, and only adding interactions when they have a statistically relevant impact on performance.

Live Configs, Champion, Priority Challengers, Regular Challengers

As previously stated, the goal of automl is to find the optimal configuration in a hands-off approach. This is achieved by training multiple configurations in parallel, removing bad configurations, exploring new configurations, and exploiting the best configuration. The number of live configurations at any given time is specified with the "--automl #" flag, and is set to 3 by default. There are 3 types of configs, each of which comes with a unique set of rules. The champion is considered our best current config. While all configs will learn from each example, only the champion will be used to predict. Thus from an external perspective, it will appear as if only the model with the champion config is being used. Priority challengers are configs which are considered good and are given priority to stay live for more examples, as to have the opportunity to overtake the champion. Regular challengers are generally newer configs which are frequently swapped in and out as to explore a wider set of configs.

Set of Configs and Index_queue

When the config oracle generates configs they are stored in a map (from index to config struct). All configs are stored in this map regardless of their priority, whether they are live or inactive, etc. The index_queue is a priority queue which stores indices of this map of inactive configs which can be swapped in to the live slots. When new configs are generated, their indices are added to the index queue, and when a new inactive config is requested, the index_queue will pop the config with the highest priority (separate concept from priority challengers!). By default the priority of every config is the same, but you can use "--priority_type lease_exclusion" to prioritize configs which exclude less (and less frequent) namespaces. Regardless of the priority_type used in the index_queue, it will cycle through all inactive configs before retrying a config which has already been seen. Once the index_queue is empty, it will repopulate itself with all inactive configs and repeat the cycle.

Determining the Strength of a Config

Automl uses the confidence sequence method to determine predictive strength of a config. Each config will have an upper_bound and lower_bound which form a confidence interval around the expected predictive strength of a given model.

Initializing Champion, Priority Challengers, Regular Challengers

Upon initialization the default config (-q ::) is set to be the champion. After processing one example, the oracle will generate new configs and these configs will be used populate the priority and regular challengers. By default half of the challengers will be priority and the other half regular. You can specify an exact number of challengers with the flag "--priority_challengers #".

Lease and General Algorithm for Swapping Regular Challengers

Each config is assigned a staring lease. This lease is set to 10 by default but can set with the flag "--lease #". As each example is processed, the update_count (initialized to 0) of all live configs will be incremented by 1. Once update_count==lease we will consider the config to have used its lease. If this occurs in the champion or in a priority challenger, then the lease for the config is doubled everything continues as normal. If this occurs with a regular challenger then a series of actions are triggered. First the lease is doubled. Next we check if the lower_bound of the regular challenger is higher than the upper_bound of any of the priority challengers. It is important to note that this strongly favors the priority challenger as lower_bound is a much more conservative estimate of predictive power than upper_bound. If this condition is met with any of the priority challengers, then the regular challenger is made priority and the priority challenger is made regular. If not, the regular challenger is made inactive, and is swapped out with some other inactive config which has been generated by the oracle.

General Algorithm for Swapping out the Champion

After processing each example we will check all configs to determine if any of them have a higher lower_bound than the champion's upper_bound. Recall that this this comparison gives priority to the current champion as lower_bound is a more conservative estimate. If any config meets this condition, then it will become the new champion, and the old champion will take on the status of the config that replaced it (either priority or regular challenger). Note that it is also possible for the champion to be overtaken by an inactive config, in which case the champion will kick out the worst live config, and the inactive config will become champion. This case should really not happen in practice. Whenever a champion change occurs, the config oracle is invoked, and new configs are generated around the new champion. Note that this is the only time that new configs are generated other than at the first example. By default, all challenger and inactive configs will be cleared when the champ is changed.

Removing Configs

In the same function which checks if the champion should be swapped out, configs are eligible to be removed permanently. If a config is deemed "strictly worse" than the current champion, then it will get the status Removed and can never become live again. Currently there are no defined criteria for a config to be eligible for removal.

Comparing Estimators on Equivalent Time Frames

Automl has recently been updated to have multiple estimators for the champion, each on an equivalent time-frame of its respective challenger. For instance, if there are 3 challengers which were first initialized 10, 100, and 1000 examples ago respectively, then they will each have a pair of estimators (challenger_estimator, champ_estimator) which were also initialized 10, 100, and 1000 examples ago respectively. The challenger estimators will use each of the challengers models when making predictions on each example, and the champion estimators will use the champion model. This is an important update because it ensures that models are being compared using the same set of examples, ensuring that nonstationary input data does not skew one of the estimators unfairly.