Градієнтний спуск

Оновлено на September 03, 2024 3 хвилини читають

Вступ

Уявіть, що у нас є функція $f(x)$ і ми хочемо знайти її мінімум. Що б ти зробив ?

Просто так? Нам потрібно лише розв’язати таке рівняння:

$$f’(x) = 0$$

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

Давайте розвинемо інтуїцію

Припустимо, що у нас є функція f з відповідним графіком:

Почнемо з випадкової точки $x_{0}$. Мета полягає в тому, щоб перемістити цю точку та наблизити її до $x*$ так, щоб $f’($x*$) = 0$. Тому проблему можна розділити на дві частини:

• У якому напрямку потрібно перемістити точку $x$ ? Вліво чи вправо?

• На скільки ми повинні його перемістити?

Напрямок

Давайте розвинемо трохи інтуїції, щоб відповісти на перше запитання. Зверніть увагу на наступний пункт:

Зауважте, що:

• коли точка $x_{0}$ знаходиться праворуч від оптимальної точки $x*$, її дотична лінія йде вгору.

• коли точка $x_{0}$ знаходиться праворуч від оптимальної точки $x*$, її дотична лінія йде вниз.

Напрям прямої визначається знаком її нахилу:

• Лінія йде вгору $\implies$ нахил $a$ позитивний.

• Лінія йде вниз $\implies$ нахил $a$ негативний.

Зверніть увагу, що: \

Нахил дотичної до функції в певній точці $x_{0}$ не більше ніж похідна в цій точці $f’(x_{0})$:

$$ tangent(x*{0}): g(x) = f’(x*{0}).(x-x*{0}) + f(x*{0}) $$

Отже, як відповідь на запитання “Куди нам перемістити $x_{0}$?”:

• $f’(x_{0}) < 0$ $\implies$ $x_{0}$ праворуч від $x*$ $\implies$ Нам потрібно перемістити $x_{0}$ ліворуч.

• $f’(x_{0}) > 0$ $\implies$ $x_{0}$ ліворуч від $x*$ $\implies$ Нам потрібно перемістити $x_{0}$ праворуч.

Кроки

А тепер друге запитання: Скільки ми повинні перемістити $x_{0}$?

Подивіться на наступні приклади:

Ми можемо зробити висновок, що:

• $x_{0}$ близьке до $x*$ => Нахил дотичної невеликий => $f’(x{0})$ невеликий.

• $x_{0}$ віддалений від $x*$ => Нахил дотичної великий => $f’(x_{0})$ великий.

Відповівши на обидва запитання, ми дійшли висновку, що лише знання похідної в точці $x_{0}$ може дати нам багато розуміння напрямку та відстані оптимальної точки $x_{0}$.

Градієнтний спуск

Градієнтний спуск - це формулювання відповідей на попередні два запитання. Це ітераційний алгоритм оптимізації, який апроксимує мінімум $x*$ функції, починаючи з випадкової початкової точки $x_{0}$. Алгоритм викладено таким чином:

$$ x*{n+1} = x*{n} - lr \times \frac{\mathrm{d} f}{\mathrm{d} x_{n}} $$

де:

• $ \frac{\mathrm{d} f}{\mathrm{d} x*{n}} $ не більше ніж похідна від $f$ у точці $x*{n}$.

• $lr$ — додатна константа, яка визначає, наскільки великими будуть кроки.

Зауважте, що:

• $x_{n}$ знаходиться праворуч від $x*$ => $\frac{\mathrm{d} f}{\mathrm{d} x_{n}} > 0 $ => $ x_{n+ 1} = x_{n} - позитивний $ => $x_{n}$ рухається вліво.

• $x_{n}$ знаходиться ліворуч від $x*$ => $\frac{\mathrm{d} f}{\mathrm{d} x_{n}} < 0$ => $ x*{n +1} = x*{n} + плюс $ => $x_{n}$ рухається вправо.

• $x_{n}$ близько до $x*$ => $\frac{\mathrm{d} f}{\mathrm{d} x_{n}}$ близько до $0$ => Невелике оновлення до $x_{ n}$.

Вікторина

• Коли градієнтний спуск припиняє ітерацію:

• Коли $x_{n}$ достатньо малий.

• Коли $x_{n}$ близьке до $x_{0}$.

• Коли $\frac{\mathrm{d} f}{\mathrm{d} x_{n}} = 0 $. XXX

• Як ми вибираємо $x_{0}$:

• Ми вибираємо випадково. XXX

• Ми беремо його в районі $x{n}$.

— Це залежить від проблеми.

• Навіщо нам градієнтний спуск:

– Тому що комп’ютери недостатньо потужні, щоб обчислювати похідні.

– Тому що надзвичайно важко знайти формули похідних моделей глибокого навчання. XXX

• Оскільки функції мають більше одного локального мінімуму.