Баєсова оптимізація

Баєсова оптимізація — це стратегія оптимізації гіперпараметрів для довільних функцій. Використовується у випадку, якщо обчислення функції з заданими гіперпараметрами є дуже ресурсоємкою операцією.

Кілька кроків баєсової оптимізації — вгорі сама функція, максимум якої шукається, три графіка нижче: очікуване покращення, верхня границя довірчого інтервалу, ймовірність покращення.

Задача

Нехай існує функція $f(x)\in \mathbb {R}$, де $x\in \mathbb {R} ^{p}$, де $p$ — невелике число (зазвичай менше 20). В такому випадку $x$ можна інтерпретувати як набір гіперпараметрів деякої моделі, яку виражає функція $f$. Метод не накладає обмежень на функцію, за якою обчислюється результат, тому часто кажуть про модель чорного ящика. Множина можливих значень $x$ є обмеженою, найчастіше або гіперпрямокутником (кожен з параметрів має верхню і нижню межу), або гіперсімплексом (сума параметрів менша за деяке число).

Задача полягає у тому, щоб знайти такий набір гіперпараметрів, при якому результат буде максимальний. При цьому, обчислення функції $f(x)$ може займати багато часу (хвилини або години), або є фінансово обтяжливим (вимагає придбання лабораторних інгредієнтів або плати за хмарні обчислення), або бути обмеженим через якісь інші причини, тому необхідно провести його якомога меншу кількість разів. Також, важливо підкреслити що метою є пошук глобального, а не локального мінімуму.

При обчисленні $f(x)$ ми отримуємо лише самі значення функції, але не значення її похідної, тому неможливо використовувати такі методи як алгоритм Ньютона.

У базовому варіанті алгоритму вважається, що $f(x)$ вимірюються без шуму, втім, існують варіанти Баєсової оптимізації, які можуть бути використані і коли ця умова не виконується.

Базовий алгоритм

Алгоритм баєсівської оптимізації складається з наступних етапів:

1. Ініціалізація
   • Обирається апріорний розподіл для моделі
   • Значення $f(x)$ обраховується для деякої кількості точок, зазвичай обраних випадково з усієї області визначення
2. Використовуючи наявні виміряні значення функції, уточнюємо апріорний розподіл ймовірностей, отримуючи апостеріорний розподіл (регресія гаусівського процесу)
3. Знаходимо максимум функції вибору на всій області визначення, обчислюємо $f(x)$ у цій точці
4. Постанні два кроки повторюємо задану заздалегідь кількість разів, або ж доки максимум функції вибору не буде меншим за деякий встановлений поріг

Загалом, баєсівська оптимізація побудована на дилемі "розвідка або розробка" (англ. exploring vs. exploiting) — функція вибору побудована таким чином, що її значення збільшується при віддаленні від відомих точок, а також при наближенні до відомого максимуму (нижче ми опишемо цей процес більш докладно). Тобто, максимальне значення зазвичай знаходиться або десь посеред великої ділянки що не містить спостережень, або ж неподалік від максимального відомого значення функції.

Регресія гаусівського процесу

Кілька траєкторій Гауссівського процесу, вибраних з апріорного розподілу

Декілька апостеріорних траєкторій, що проходять через дві відомі точки (початок координат і (1, 1). Різні параметри гаусівського ядра породжують траєкторії різної звивистості. Функція середнього в усіх випадках є нульовою

Нехай є гауссівський процес тобто, такий випадковий процес $\{X_{t};t\in T\}$, що для будь-якого набору значень ${t_{1},t_{2},t_{3},...,t_{k}}$ випадковий вектор $(X_{t_{1}},\ldots ,X_{t_{n}})^{\top }$ має багатовимірний нормальний розподіл (зверніть увагу, це не означає, що функція задана лише в дискретних точках — вона задана по всьому простору, і будь які довільно вибрані точки будуть пов'язані таким чином). Тоді конкретна реалізація цього процесу буде деякою функцією $f(x)$.

Різним процесам відповідають різні розподіли функцій. Загалом, Гаусівський процес описується двома параметрами: функцією середнього, яка повертає вектор середніх значень для заданого набору точок (кожна окрема точка $x_{i}$ є вектором у просторі $\mathbb {R} ^{p}$)

$\mu _{0}(x_{1:n})=[\mu _{0}(x_{1}),\mu _{0}(x_{2}),...,\mu _{0}(x_{n})]$

і функцією, що породжує матрицю коваріації для цих точок

$\Sigma _{0}(x_{1:n},x_{1:n})=[\Sigma _{0}(x_{1},x_{1}),...,\Sigma _{0}(x_{1},x_{n});...;\Sigma _{0}(x_{n},x_{1}),...,\Sigma _{0}(x_{n},x_{n})]$

Тоді, якщо нам відома деяка кількість значень функції $f(x_{1:n})$, можна використати цю інформацію для того щоб уточнити апріорний розподіл наступним чином:

$\mu _{n}(x)=\Sigma _{0}(x,x_{1:n})\Sigma _{0}(x_{1:n},x_{1:n})^{-1}(f(x_{1:n})-\mu _{0}(x_{1:n}))+\mu _{0}(x)$

$\sigma _{n}^{2}(x)=\Sigma _{0}(x,x)-\Sigma _{0}(x,x_{1:n})\Sigma _{0}(x_{1:n},x_{1:n})^{-1}\Sigma _{0}(x_{1:n},x)$

Розподіл, заданий цими параметрами, визначає ймовірності значень невідомого, $n+1$-го значення функції по всій області визначення.

Функція середнього

Апріорна функція середнього для задач баєсівської оптимізації обирається достатньо простою. У найпопулярнішому випадку константи, її значення може обиратися рівним нулю, або середньому значень в усіх точках (але не обмежено цими варіантами). Іноді, якщо є причини вважати, що значення $f(x)$ прямо чи обернено пропорційне якомусь з параметрів, можуть використовуватися поліноми невисокого ступеню. Також, можуть застосовуватися більш складні методи визначення — функція середнього може сама будуватися на за допомогою непараметричних моделей (РБФ, Random forest, тощо).

Ядерна функція коваріації

Апріорна функція для матриці коваріації обирається серед ядерних функцій. Ядерні функції мають дві важливі якості в контексті задачі регресії гаусівського процесу: вони є симетричними, і породжена ними матриця є позитивно визначеною (обидві умови є обов'язковими для будь-якої матриці коваріації). Ядро визначає коваріацію між будь-якими двома точками, в залежності від відстані між ними (або дисперсію значень у точці, якщо відстань є нульовою). Чим швидше функція ядра спадає з відстанню, тим швидше функція може змінюватися при зміні аргументів. Зазвичай, ядра мають параметри, що визначають швидкість цього спадання.

Популярними варіантами для баєсівської оптимізації

• гаусівське ядро, також відоме як квадратично-експоненціальне ядро (англ. squared-exponential)

$K(x,x')=\sigma e^{-{\frac {(x-x')^{2}}{2l^{2}}}}=\sigma e^{-{\frac {r^{2}}{2l^{2}}}}$,

де $r$ — відстань між точками. Параметрами ядра є $\sigma$ і $l$.

• ядро Матерна (або сімейство ядер, що залежить від $\nu$)

$K(r)={\frac {2^{1-\nu }}{\Gamma _{\nu }}}\left({\frac {{\sqrt {2\nu }}r}{l}}\right)^{/nu}K_{\nu }\left({\frac {{\sqrt {2\nu }}r}{l}}\right)$,

де $K_{\nu }$ — модифікована функція Бесселя. Параметрами ядра є $\nu$ і $l$. Типові значення для $\nu$ — 3/2, 5/2.

• γ-експоненційне ядро

$K(r)=e^{-\left({\frac {r}{l}}\right)^{\gamma }}$

Функція має параметри $\gamma$ і $l$, при чому параметр $\gamma$ може набувати значень від 0 до 2. При $\gamma =2$ переходить в квадратично-експоненційне

• Раціонально-квадратичне ядро англ. Rational Quadratic

$K(r)=\left(1+{\frac {r^{2}}{2\alpha l^{2}}}\right)^{-\alpha }$

з параметрами $\alpha ,l>0$

Також, у всіх цих функціях замість масштабування всього вектора (наприклад, параметр l у гаусівському ядрі), кожна компонента вектора $x$ може масштабуватися окремо — у цьому випадку замість одного параметру використовується $p$ параметрів, де $p$ — розмірність вектора $x$.

Загалом, відомо, що клас функцій, які можна апроксимувати використовуючи прості (і навіть константні) функції середнього і довільні ядра коваріації є досить широким, і як мінімум включає в себе всі ліпшицеві функції.

Визначення гіперпараметрів

Параметри функції ядра і середнього (вектор, що містить всі параметри позначається як $\eta$) визначаються виходячи з відомих значень функції. Існує кілька підходів до такого визначення:

• Оцінка максимальної правдоподібності (англ. MLE): для заданого набору точок обчислюється правдоподібність такого результату в залежності від значень гіперпараметрів, $P(f(x_{1:n})|\eta )$, і обирається те значення, для якого правдоподібність максимальна

• Оцінка максимальної апостеріорної ймовірності (англ. MAP): у цьому методі припускається, що самі гіперпараметри мають деякий розподіл $P(\eta )$. Тоді оцінка максимальної правдоподібності змінюється, і функція, максимум якої ми шукаємо виглядає так:

$P(\eta |f(x_{1:n}))=P(f(x_{1:n})|\eta )P(\eta )$

Фактично, MLE є окремим випадком MAP, якщо ми припускаємо що $\eta$ має рівномірний розподіл. MAP є більш корисною, якщо ми можемо зробити якісь припущення щодо можливих значень гіперпараметрів (наприклад, якісь їх комбінації є дуже малоймовірними). Популярними варіантами для розподілів є рівномірний, нормальний або логнормальний.

• Повністю баєсівська оцінка (англ. fully Bayesian): у цьому методі ми не обираємо єдине значення гіперпараметрів, а обчислюємо апостеріорний розподіл як:

$P(f(x)=y|x_{1:n})=\int P(f(x)=y|f(x1:n),\eta )P(\eta |f(x1:n))d\eta$

зазвичай, такий інтеграл неможливо взяти, тому обчислюють його наближене значення за допомогою суми

$P(f(x)=y|x_{1:n})=\Sigma _{J}P(f(x)=y|f(x1:n),\eta ={\hat {\eta }}_{J})$

де ${\hat {\eta }}_{J}$ — деяка кількість наборів гіперпараметрів, що отримана з загального розподілу гіперпараметрів будь-яким методом МКМЛ.

Функція оцінки

Загалом, функція оцінки (або функція вибору, англ. Acquisition Functions) дозволяє зрозуміти потенційну вигоду від випробовування в даній точці. Найбільш типовою функцією оцінки є очікуване покращення (англ. Expected Improvement):

$EI(x)=\mathbb {E} [[f(x)-f_{n}^{*}]^{+}]$

Де $\mathbb {E}$ — математичне очікування, $f_{n}^{*}$ — максимальне значення функції з вже відомих, а ${}^{+}$ означає, що ми беремо лише позитивні значення (від'ємні замінюються нулем).

Як можна зрозуміти з механіки гаусівського процесу, значення функції $f(x)$ у точці $x_{n}$, що знаходиться поблизу відомої точки є, ймовірно, близьким до значення цієї точки, а при віддаленні від них, розкид можливий значень росте. Таким чином, у точках близьких до максимуму ймовірність того, що нове значення буде вищим ніж максимум є порівняно високою, але значення цього перевищення є невеликим (велике середнє, мала девіація). Тоді як у далеких від максимуму широких проміжках що не містять жодного значення, ймовірність того що значення перевищить максимум є малою, проте саме це перевищення може бути значним (маленьке середнє, велика девіація). При обчисленні нової точки, девіація навколо неї, зазвичай, падає — тому алгоритм змушує весь час переходити від дослідженням незаповнених, віддалених від відомих точок зон, до уточнення значень навколо актуального максимуму. Це коливання називають дилемою exploring vs. exploiting.

Функція очікуваного покращення може бути виражена у замкненому вигляді, й легко обчислюється, на відміну від функції $f(x)$.

Значення $x$ при якому очікуване покращення досягає максимуму є значенням, у якому береться наступна точка.

Іншими варіантами функції оцінки є:

• Градієнт знання (англ. Knowledge Gradient)
• Ентропійний пошук (англ. Entropy Search)
• Ентропійний пошук з передбаченням (англ. Predictive Entropy Search)

Ці функції є більш популярними для екзотичних варіантів баєсівської оптимізації.

Для ілюстрації часто використовується графік апостеріорного середнього, і значення деякого довірчого інтервалу (наприклад, 95%). Максимальне значення довірчого інтервалу (англ. Upper Confidence Bound) може використовуватися і як функція оцінки.

Екзотичні варіанти алгоритму

У випадку наявності шуму, функція середнього не буде обов'язково проходити через всі наявні точки

Екзотичною баєсівською оптимізацією називають алгоритми, що вирішують задачу, умови якої відрізняються від базової у деяких важливих деталях.

Найважливішим з них є зашумлені оцінки — якщо значення функції $f(x)$ не є точним, а саме вимірюється з деяким шумом. У такому випадку, до матриці коваріації додаються діагональні члени, що не залежать від відстані, і позначають власне похибку вимірювання. Описані вище функції оцінки можуть бути застосовані і в цьому випадку, хоча існують спеціалізовані варіанти цих функцій, що є більш доречними для цієї задачі.

Іншим варіантом є модифікація алгоритму для паралельних обчислень, при якій визначається не одна, а одразу кілька точок для наступного випробування (оскільки значення функції у цих точках можуть бути визначені незалежно для пришвидшення процесу). Описані вище функції також можуть бути природно розширенні для такої задачі.

Історія

Вперше подібний алгоритм був запропоновий у 1964 році Гарольдом Кушнером. У методі Кушнера, втім, функція апроксимувалася випадковим блуканням (математичним аналогом броунівського руху) зі змінним середнім і дисперсією. Метод був покращений А.Г. Жилінскасом і Йонасом Моцкусом в 1970х, у припущенні, що на кожному етапі процесу шукається лише одна точка, якою випробовують наступною (one-stage Bayesian method), проте вони також вважали процес, що описує функцію, вінерівським. У 1975 Моцкус запропонував використовувати максимум функції очікуваного покращення (EI) як наступну точку(пошук максимуму цієї функції був досліджений ще у 1961 році Чарльзом Кларком, при роботі над зовсім іншою задачею). Загалом, метод важко узагальнювався на більш ніж одновимірний випадок (тобто, випадок коли функція залежала від більш ніж одного аргументу). Також, з 1960х років у геології з'явився кригінг подібний метод, що використовувався для побудови карт.

Значний поштовх у розвитку, метод отримав у 1998 році, після роботи Дональда Джонса, Матіаса Шонлау і Вільяма Велча, в якій вони описали метод, більш подібний на сучасний — де брався до уваги зв'язок між близькими точками (проте, автори використовували матрицю кореляції замість матриці коваріації). У їх роботі була використана функція, подібна до γ-експоненційного ядра. Описаний ними метод отримав назву Efficient Global Optimization (EGO).

Література

• Rasmussen C.E., Williams C.K.I. Gaussian Processes for Machine Learning. — Cambridge, Massachusetts : MIT Press, 2006. — 248 с. — ISBN 026218253X.
• R. Garnett. Bayesian Optimization. — Cambridge University Press, 2023. — 358 с. — ISBN 9781108425780.