In my previous post, I talked about the exploration/exploitation dilemma in optimization, and then defined an algorithm that seeks to resolve it. The algorithm described in that post was a variation of neighborhood search and hill climbing methods. The amount of time it spends looking for improvements in the “neighborhood” of a given solution is a direct function of the magnitude of improvement that a current best solution demonstrates over the previous best.

Large improvements cause the algorithm to remain in the current best solution’s neighborhood for significant lengths of time. While this is a good thing if the neighborhood is rich in potential improvements, it presents a problem if the neighborhood turns out to be sparse in improving solutions.

To counter this, I outline another, far more exploratory, numerical optimization algorithm. This algorithm symetrically interleaves its exploration and exploitation steps, dividing its time equally betweem searching the neighborhood of the current global best, and searching the global solution space in a purely random pattern.

After initially evaluating a solution at random and setting its score as the global best, the algorithm evaluates another solution in the global best’s neighborhood. If this solution’s score is better than that of the global best, it becomes the new global best, otherwise the optimizer tries a protential solution chosen at random from the entire search space. If this solution is better than global best, it becomes the global best and the search resumes from its neighborhood, otherwise the search returns to the current global best’s neighborhood to try another solution at random.

In this way, on every other step, the algorithm bounces between searching the whole space randomly and a much more focussed search in the global best’s neighborhood.

The algorithm was designed to optimize machine learning model parameters, but it can be applied to any numerical optimization problem.

Below is an outline of the algorithm, and below that is a Python implementation of the algorithm tuning the parameters of a LightGBM prediction model.

Interleaved Neighborhood Algorithm


 evaluate random solution rs

 set var global_best to rs score 
 set var best_parameters to rs parameters
 set var horizon to "local"

 while true do
      
       if horizon = "local"
        
          neighborhood solution ns = gaussian distr(mean = best_parameters, deviation = random(0.1...1.0))
        
          if ns better than global_best
           
             set var global_best to ns score 
             set var best_parameters to ns parameters
             continue
        
          else
            
             set var horizon to "global"
             coninue
        
       else
      
           evaluate global random solution gs
          
           if gs score better than global_best
             
              set var global_best to gs score 
              set var best_parameters to gs parameters
              set var horizon to "local"
              continue
          
           else:
               
              set var horizon to "local"
              continue
             

   

Optimizing A LightGBM Machine Learning Model

The Python code below uses the Interleaved Neighborhood Algorithm to search through the space of parameters of a LightGBM machine learning model. The model is trained on, and used to make predictions about, the Kaggle Iowa housing dataset.

LightGBM is a gradient boosting framework with a large number of parameters, each of which can take a huge range of values. This makes parameter optimization a nontrivial problem. For simplicity, the demonstration below uses only a few of the dozens of model parameters available for tuning.

temp.py

   1 
   2 
    import numpy as np
   3 
    import pandas as pd
   4 
    from lightgbm import LGBMRegressor
   5 
    from sklearn.metrics import mean_absolute_error
   6 
    from sklearn.model_selection import train_test_split
   7 
    from random import randrange, uniform, gauss
   8 
    import clevercsv
   9 
 
  10 
 
  11 
    #Read datasets into memory
  12 
    complete_train = pd.read_csv(
  13 
        "train.csv",
  14 
        encoding = "UTF-8",
  15 
        index_col = "Id")
  16 
 
  17 
    complete_test = pd.read_csv(
  18 
        "test.csv",
  19 
        encoding = "UTF-8",
  20 
        index_col = "Id")
  21 
 
  22 
 
  23 
    #Seperate predictors from target variable
  24 
    X = complete_train.drop(
  25 
        columns = "SalePrice")
  26 
 
  27 
    y = complete_train[
  28 
        "SalePrice"]
  29 
 
  30 
 
  31 
    #Encode categoricals and impute missing data
  32 
    def encode_impute(*datasets):
  33 
        for dataset in datasets:
  34 
            for column in dataset.columns:
  35 
                dataset[
  36 
                    column].fillna(
  37 
                    -999,
  38 
                    inplace = True)
  39 
                if dataset[
  40 
                    column].dtype ==  "object":
  41 
                    dataset[
  42 
                        column] = dataset[
  43 
                        column].astype("category", copy = False)
  44 
 
  45 
    encode_impute(X)
  46 
 
  47 
 
  48 
    #Create validation set
  49 
    X_train, X_valid, y_train, y_valid = train_test_split(X, y)
  50 
 
  51 
 
  52 
    #Model evaluation
  53 
    def model_check(parameters):
  54 
       
  55 
        local_copy ={
  56 
            key:value for key,value in parameters.items()}
  57 
       
  58 
        model = LGBMRegressor().set_params(**local_copy)
  59 
        model.fit(X_train, y_train)
  60 
        prediction = model.predict(X_valid)
  61 
        error_rate = mean_absolute_error(y_valid, prediction)
  62 
       
  63 
        return {"score": error_rate, "parameters": parameters}
  64 
 
  65 
 
  66 
    #Parameter generation
  67 
    def param_gen():
  68 
       
  69 
        k = randrange(10000)
  70 
       
  71 
        parameters = {
  72 
           "boosting_type": "dart",
  73 
           "n_estimators": k,
  74 
           "num_leaves": randrange(round(k/3 * 2)),
  75 
           "learning_rate": uniform(0.01, 1)}
  76 
       
  77 
        return parameters
  78 
 
  79 
 
  80 
 
  81 
    #square_neighborhood algorithm
  82 
    def interleaved_neighborhood():
  83 
       
  84 
        initialize = model_check(param_gen())
  85 
       
  86 
        global_best = {
  87 
            "score": initialize["score"],
  88 
            "parameters": initialize["parameters"]}
  89 
       
  90 
        with open(
  91 
            "values.csv", "a", encoding = "UTF-8") as valuefile:
  92 
            values = clevercsv.writer(valuefile)
  93 
            values.writerow(
  94 
                [global_best["score"],
  95 
                global_best["parameters"]])
  96 
       
  97 
        horizon = "local"
  98 
       
  99 
       
 100 
        while True:
 101 
           
 102 
            try:
 103 
               
 104 
                if horizon == "local":
 105 
                   
 106 
                    perturb = {
 107 
                        key:abs(gauss(value, uniform(0.1, 2.0)))
 108 
                        if type(value) != str
 109 
                        else value for key,value
 110 
                        in global_best["parameters"].items()}
 111 
                   
 112 
                    rounded = {
 113 
                        key:round(value)
 114 
                        if key in ["n_estimators", "num_leaves"]
 115 
                        else value for key,value in perturb.items()}
 116 
                   
 117 
                    local_solution = model_check(rounded)
 118 
                   
 119 
                    if local_solution["score"] < global_best["score"]:
 120 
                       
 121 
                        with open(
 122 
                            "values.csv", "a", encoding = "UTF-8") as valuefile:
 123 
                            values = clevercsv.writer(valuefile)
 124 
                            values.writerow(
 125 
                                [local_solution["score"],
 126 
                                local_solution["parameters"]])
 127 
                       
 128 
                        global_best["score"] = local_solution["score"]
 129 
                        global_best["parameters"] = local_solution["parameters"]
 130 
                       
 131 
                        continue
 132 
                  
 133 
                   
 134 
                    else:
 135 
                       
 136 
                        horizon = "global"
 137 
                        
 138 
                        continue
 139 
                           
 140 
                           
 141 
                else:
 142 
                   
 143 
                    random_solution = model_check(param_gen())
 144 
                   
 145 
                    if random_solution["score"] < global_best["score"]:
 146 
                       
 147 
                        with open(
 148 
                            "values.csv", "a", encoding = "UTF-8") as valuefile:
 149 
                            values = clevercsv.writer(valuefile)
 150 
                            values.writerow(
 151 
                                [random_solution["score"],
 152 
                                random_solution["parameters"]])
 153 
                       
 154 
                        global_best["score"] = random_solution["score"]
 155 
                        global_best["parameters"] = random_solution["parameters"]
 156 
                       
 157 
                        horizon = "local"
 158 
                       
 159 
                        continue
 160 
                   
 161 
                    else:
 162 
                       
 163 
                        horizon = "local"
 164 
                       
 165 
                        continue
 166 
                       
 167 
           
 168 
           
 169 
            except Exception as error:
 170 
               
 171 
                print(error)
 172 
       
 173 
       
 174 
 
 175 
       
 176 
 
 177 
    interleaved_neighborhood()
 178 
 
 179 
 
 180 
 
 181 
 

   

Full code repo available on Github

   

Related posts:

Square Neighborhood Algorithm: Balancing Exploration And Exploitation In Optimization

Speculative Fiction Bot

EXP-RTL: Exponential Retaliation In Iterated Prisoner’s Dilemma Games

   

About Me