Решетчатый и случайный поиск

Привет, Хабр!

Среди разнообразных подходов оптимизации, сегодня мы поговорим про методы решетчатого (grid search) и случайного (random search) поиска. Они были созданы для нахождения оптимальных решений в больших пространствах параметров.

Решетчатый поиск - это метод, при котором пространство возможных параметров систематически исследуется путем оценки и сравнения результатов на равномерно распределенных точках. Его юзают, когда необходимо исследовать каждую комбинацию параметров, хотя он может быть ресурсоемким при большом количестве параметров.

Случайный поиск в свою очередь предлагает раскапывать пространство параметров путем случайного выбора точек. Этот метод используют когда пространство параметров слишком велико для полного перебора, или когда только некоторые параметры оказывают значительное влияние на результат.

Решетчатый поиск

Решетчатый поиск предполагает, как мы ранее говорили – систематическое переборное исследование определенного пространства параметров с целью нахождения наилучшего набора значений, максимизирующих или минимизирующих заданную функцию оценки (например, точность модели).

Принцип работы алгоритма

Первый шаг - это определение пространства параметров, которое будет исследоваться. Это включает в себя выбор гиперпараметров для настройки и диапазонов их значений. Например, при настройке модели мл это могут быть гиперпараметры, такие как скорость обучения, количество слоев, количество деревьев в случайном лесу и т.п

Далее создается 'решетка' - сетка возможных комбинаций значений гиперпараметров. Это делается путем определения списка значений для каждого гиперпараметра. Например, если у нас есть два параметра A и B, где A может принимать значения [1, 2, 3], а B - [4, 5], то решетка будет состоять из всех пар (A, B): [(1,4), (1,5), (2,4), (2,5), (3,4), (3,5)]:

Алгоритм последовательно перебирает каждую комбинацию параметров в решетке и вычисляет функцию оценки для каждой комбинации. Это может быть, например, точность классификации модели на валидационном наборе данных.

После оценки всех комбинаций алгоритм выбирает комбинацию параметров, которая дает наилучший результат по функции оценки.

В математическое виде допустим, у нас есть функция оценки F , которую мы хотим максимизировать (или минимизировать), и набор гиперпараметров θ={θ1​,θ2​,...,θn​}. Каждый гиперпараметр θi​ пимеет заданный диапазон значений. Тогда решетчатый поиск осуществляется следующим образом:

1. Для каждого θi создается множество возможных значений Si​.

2. Формируется декартово произведение всех множеств Si, что дает нам полное пространство поиска S=S1​×S2​×...×Sn​.

3. Для каждой комбинации параметров c∈S, вычисляется F(c).

4. Выбирается комбинация c∗, для которой F(c∗) является максимальным (или минимальным, в зависимости от задачи).

Рассмотрим примеры реализации на питоне:

Решетчатый поиск для оптимизации гиперпараметров с помощью гридсерча#:

from sklearn.model_selection import GridSearchCV
from sklearn.svm import SVC
from sklearn.datasets import load_iris

iris = load_iris()
X, y = iris.data, iris.target

model = SVC()
parameters = {'kernel':('linear', 'rbf'), 'C':[1, 10]}

clf = GridSearchCV(model, parameters)
clf.fit(X, y)
print(clf.best_params_)

{'C': 1, 'kernel': 'linear'}

Реализуем решетчатый поиск на чистом питоне:

def grid_search(f, param_grid):
    best_score = float('inf')
    best_params = None
    for p in param_grid:
        score = f(**p)
        if score < best_score:
            best_score = score
            best_params = p
    return best_params

def test_function(x, y):
    return (x - 2) ** 2 + (y - 5) ** 2

param_grid = [{'x': x, 'y': y} for x in range(-10, 11) for y in range(-10, 11)]
best_params = grid_search(test_function, param_grid)
print(best_params)

{'x': 2, 'y': 5}

Случайный поиск (Random Search)

Случайный поиск (Random Search) - это метод, который выбирает случайные комбинации параметров из заданного пространства параметров и оценивает их, чтобы найти наиболее оптимальное решение.

Первый шаг в случайном поиске начинается с определения пространства параметров, которое нужно исследовать. Это включает в себя установление диапазонов для каждого из гиперпараметров. Например, если регулируемыми параметрами являются скорость обучения и количество нейронов в слое, для каждого из них устанавливается диапазон возможных значений.

В отличие от решетчатого поиска, который систематически перебирает все комбинации, случайный поиск выбирает комбинации случайно. Это делается путем выбора случайного значения для каждого параметра из его диапазона. Например, если скорость обучения может быть от 0.01 до 0.1, а количество нейронов - от 10 до 100, алгоритм случайно выберет число в каждом из этих диапазонов.

Каждая случайно выбранная комбинация параметров оценивается для определения ее эффективности. К примеру это может быть оценка точности, F1-меры или других метрик производительности модели на валидационном наборе данных.

Процесс выбора и оценки повторяется заданное количество раз или до достижения определенного критерия останова. После завершения всех итераций выбирается лучший набор параметров.

Допустим, у нас есть функция оценки F , и набор гиперпараметров Θ={θ1​,θ2​,...,θn​}, где каждый параметр θi имеет определенный диапазон значений или распределение. Алгоритм случайного поиска можно представить следующим образом:

Инициализация: задается число итераций T.

Для каждой итерации t=1,2,...,T:

1. Генерируется случайный набор параметров θt, где каждый θit выбирается случайно из его распределения или диапазона. Вычисляется значение функции оценки F(θt).

2. Выбирается набор параметров θ∗, который дает наилучшее значение F.

Случайный поиск (Random Search) часто используется для оптимизации гиперпараметров:

Случайный поиск с испольованием RandomizedSearchCV из scikit-learn для классификатора SVM

from sklearn.model_selection import RandomizedSearchCV
from sklearn.svm import SVC
from sklearn.datasets import load_iris
import scipy.stats as stats

# Загрузка данных
iris = load_iris()
X, y = iris.data, iris.target

# Определение модели и параметров
model = SVC()
param_distributions = {
    'C': stats.uniform(0.1, 10),
    'gamma': stats.uniform(0.001, 0.1)
}

# Случайный поиск
random_search = RandomizedSearchCV(model, param_distributions, n_iter=100, random_state=42)
random_search.fit(X, y)
print(random_search.best_params_)

{'C': 3.845401188473625, 'gamma': 0.09607143064099162}

Случайный поиск для настройки гиперпараметров нейр.сети с Keras

from keras.models import Sequential
from keras.layers import Dense
import numpy as np

# Функция для создания модели
def create_model(optimizer='adam'):
    model = Sequential()
    model.add(Dense(12, input_dim=8, activation='relu'))
    model.add(Dense(1, activation='sigmoid'))
    model.compile(loss='binary_crossentropy', optimizer=optimizer, metrics=['accuracy'])
    return model

# Случайно выбираем гиперпараметры
optimizers = ['rmsprop', 'adam']
batch_size = np.random.choice([16, 32, 64], 1)[0]
epochs = np.random.choice([10, 50, 100], 1)[0]

# Создаем и тренируем модель
model = create_model(optimizer=np.random.choice(optimizers))
model.fit(X, y, epochs=epochs, batch_size=batch_size)

Случайный поиск для оптимизации гиперпараметров регрессии

from sklearn.linear_model import Ridge
import numpy as np

# Генерация случайных гиперпараметров
alpha_values = np.random.uniform(0.1, 2, 100)

best_score = 0
best_alpha = None

# Поиск лучшего значения alpha
for alpha in alpha_values:
    model = Ridge(alpha=alpha)
    model.fit(X_train, y_train)
    score = model.score(X_val, y_val)
    if score > best_score:
        best_score = score
        best_alpha = alpha

print("Лучшее значение alpha:", best_alpha)

Вставьте любой свой набор данных подходящий для этих операций

Сравнение решетчатого поиска и случайного поиска

Решетчатый поиск лучше работает, когда пространство гиперпараметров относительно маленькое и есть необходимость в тщательном и систематическом исследовании каждой возможной комбинации.

Случайный поиск более предпочтителен в сценариях с большим пространством гиперпараметров, где нецелесообразно проверять каждую возможную комбинацию, а также в случаях, когда исследование должно быть выполнено быстро или когда требуется нахождение нестандартных решений.

Больше про методы поиска и другие практические инструменты вы можете узнать в рамках онлайн-курсов от экспертов индустрии. Переходите в каталог и выбирайте интересующее вас направление.