Понимание алгоритма TPE Hyperopt

Я иллюстрирую алгоритм TPE Hyperopt для своего основного проекта и, похоже, не могу заставить алгоритм сходиться. Насколько я понимаю из оригинала, paper и лекция на YouTube, в которой работает алгоритм TPE следующие шаги:

(далее x = гиперпараметры и y = потери)

  1. Начните с создания истории поиска [x, y], скажем, 10 баллов.
  2. Отсортируйте гиперпараметры в соответствии с их потерями и разделите их на два набора, используя некоторый квантиль (= 0,5 означает, что наборы будут одинакового размера)
  3. Сделайте оценку плотности ядра как для плохой группы гиперпараметров (g (x)), так и для хорошей группы гиперпараметров (l (x))
  4. Хорошие оценки будут иметь низкую вероятность в g (x) и высокую вероятность в l (x), поэтому мы предлагаем оценивать функцию при argmin (g (x) / l (x))
  5. Оцените пару (x, y) в предложенной точке и повторите шаги 2–5.

Я реализовал это в python для целевой функции f (x) = x ^ 2, но алгоритм не может сойтись к минимуму.

import numpy as np
import scipy as sp
from matplotlib import pyplot as plt
from scipy.stats import gaussian_kde


def objective_func(x):
    return x**2

def measure(x):
    noise = np.random.randn(len(x))*0
    return x**2+noise

def split_meassures(x_obs,y_obs,gamma=1/2):
    #split x and y observations into two sets and return a seperation threshold (y_star)
    size = int(len(x_obs)//(1/gamma))
    l = {'x':x_obs[:size],'y':y_obs[:size]}
    g = {'x':x_obs[size:],'y':y_obs[size:]}
    y_star = (l['y'][-1]+g['y'][0])/2
    return l,g,y_star

#sample objective function values for ilustration
x_obj = np.linspace(-5,5,10000)
y_obj = objective_func(x_obj)

#start by sampling a parameter search history
x_obs = np.linspace(-5,5,10)
y_obs = measure(x_obs)

nr_iterations = 100
for i in range(nr_iterations):

    #sort observations according to loss
    sort_idx = y_obs.argsort()
    x_obs,y_obs = x_obs[sort_idx],y_obs[sort_idx]

    #split sorted observations in two groups (l and g)
    l,g,y_star = split_meassures(x_obs,y_obs)

    #aproximate distributions for both groups using kernel density estimation
    kde_l = gaussian_kde(l['x']).evaluate(x_obj)
    kde_g = gaussian_kde(g['x']).evaluate(x_obj)

    #define our evaluation measure for sampling a new point
    eval_measure = kde_g/kde_l

    if i%10==0:
        plt.figure()
        plt.subplot(2,2,1)
        plt.plot(x_obj,y_obj,label='Objective')
        plt.plot(x_obs,y_obs,'*',label='Observations')
        plt.plot([-5,5],[y_star,y_star],'k')
        plt.subplot(2,2,2)
        plt.plot(x_obj,kde_l)
        plt.subplot(2,2,3)
        plt.plot(x_obj,kde_g)
        plt.subplot(2,2,4)
        plt.semilogy(x_obj,eval_measure)
        plt.draw()

    #find point to evaluate and add the new observation
    best_search = x_obj[np.argmin(eval_measure)]
    x_obs = np.append(x_obs,[best_search])
    y_obs = np.append(y_obs,[measure(np.asarray([best_search]))])

plt.show()

Я подозреваю, что это происходит из-за того, что мы продолжаем выборку там, где мы наиболее уверены, тем самым сужая l (x) вокруг этой точки, что никак не меняет место выборки. Так где же мне не хватает понимания?


person Søren Jensen    schedule 26.05.2019    source источник


Ответы (1)


Итак, я все еще изучаю TPE. Но вот две проблемы в этом коде:

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

  2. Потому что этот код просто добавляет новые наблюдения в список x и y. Он добавляет много дубликатов. Дубликаты приводят к искаженному набору наблюдений, что приводит к очень странному разделению, и вы легко можете увидеть это на более поздних графиках. eval_measure начинается как нечто похожее на целевую функцию, но позже расходится.

Если вы удалите дубликаты в x_obs и y_obs, вы сможете устранить проблему №. 2. Однако первая проблема может быть устранена только путем добавления некоторого способа исследования пространства поиска.

person mbbce    schedule 13.10.2019
comment
Спасибо за комментарий. Я понял, что было не так, и это действительно было то, на что вы указали; вместо поиска наиболее определенной точки (ведущей к дублированию) новая точка поиска берется из приблизительного распределения. Эта страница действительно помогла мне понять алгоритм TPE в конце (если вы все еще учитесь) dkopczyk. quantee.co.uk/hyperparameter-optimization. - person Søren Jensen; 22.11.2019