gradient descent

Angol

Főnév

gradient descent (tsz. gradient descents)

1. (informatika, mesterséges intelligencia, algoritmusok) A Gradient Descent egy numerikus optimalizációs módszer, amelyet széles körben használnak gépi tanulásban, mélytanulásban és általános optimalizációs problémák megoldására. Az algoritmus célja egy adott függvény minimumának (vagy maximumának) megtalálása azáltal, hogy az aktuális pontban kiszámítja a gradiens irányát, és abba az irányba mozog, ahol a függvényérték csökken.

---

Működési elv

1. Kezdőpont kiválasztása:
   • Válassz egy véletlenszerű kezdő ${\textstyle x_{0}}$ pontot a függvény tartományában.
2. Gradiens kiszámítása:
   • Számítsd ki a függvény gradiensét (${\textstyle \nabla f(x)}$) az aktuális pontban.
3. Lépésvégrehajtás:
   • Mozogj a negatív gradiens irányába a következőképpen: $$x_{k+1}=x_{k}-\eta \cdot \nabla f(x_{k})$$ ahol:
     • ${\textstyle \eta }$: Lépésköz (tanulási ráta),
     • ${\textstyle \nabla f(x_{k})}$: A gradiens az ${\textstyle x_{k}}$ pontban.
4. Iterációk ismétlése:
   • Ismételd, amíg el nem érsz egy előre meghatározott kritériumot (pl. a gradiens normája kicsi lesz, vagy a függvényérték változása elhanyagolható).

---

Matematikai alapok

A gradiens egy vektor, amely egy adott pontban a függvény legmeredekebb emelkedésének irányát adja meg. Ezért a gradiens negatív iránya a legmeredekebb csökkenés iránya.

$$\nabla f(x)=\left[{\frac {\partial f}{\partial x_{1}}},{\frac {\partial f}{\partial x_{2}}},\dots ,{\frac {\partial f}{\partial x_{n}}}\right]$$

---

Típusai

1. Batch Gradient Descent:
   • Az összes adatpontot felhasználja minden lépésben.
   • Pontos, de nagy adathalmazok esetén lassú lehet.
2. Stochastic Gradient Descent (SGD):
   • Egyetlen adatpont alapján frissíti a paramétereket.
   • Gyorsabb, de zajosabb konvergenciát eredményez.
3. Mini-Batch Gradient Descent:
   • Az adatokat kisebb csomagokra (batch-ekre) osztja, és ezek alapján frissíti a paramétereket.
   • Az SGD és batch módszer közötti kompromisszum.

---

Paraméterek hatása

1. Lépésköz (${\textstyle \eta }$):
   • Ha ${\textstyle \eta }$ túl kicsi, az algoritmus lassan konvergál.
   • Ha ${\textstyle \eta }$ túl nagy, az algoritmus oszcillálhat vagy divergens lehet.

1. Kezdőpont:
   • Nem konvex függvények esetén a kezdőpont befolyásolhatja, hogy az algoritmus melyik lokális minimumhoz konvergál.

---

Előnyök

1. Egyszerű implementáció.
2. Alkalmas nagyméretű problémákhoz.
3. Rugalmas, különböző variánsokkal testreszabható.

---

Hátrányok

1. Lokális optimumok:
   • Nem konvex függvényeknél elakadhat lokális optimumokban.
2. Lassú konvergencia:
   • Ha a függvény túl lapos, a konvergencia lassú lehet.
3. Tanulási ráta érzékenysége:
   • A helytelen lépésköz problémákhoz vezethet.

---

Példa

Optimalizálandó függvény:

$$f(x)=x^{2}-4x+4$$ Cél: a minimum helyének meghatározása.

---

Python implementáció

def gradient_descent(f_prime, start, learning_rate, iterations):
    x = start
    for i in range(iterations):
        grad = f_prime(x)
        x = x - learning_rate * grad
        print(f"Iteráció {i+1}: x = {x:.4f}, f'(x) = {grad:.4f}")
    return x

# Függvény deriváltja
f_prime = lambda x: 2*x - 4

# Paraméterek
start_point = 0.0
learning_rate = 0.1
max_iterations = 20

# Gradient descent futtatása
optimal_x = gradient_descent(f_prime, start_point, learning_rate, max_iterations)
print(f"Optimális x érték: {optimal_x:.4f}")

Kimenet:

Iteráció 1: x = 0.4000, f'(x) = -4.0000
Iteráció 2: x = 0.7600, f'(x) = -3.2000
Iteráció 3: x = 1.0080, f'(x) = -2.4800
...
Iteráció 20: x = 1.9999, f'(x) = -0.0002
Optimális x érték: 2.0000

---

C++ implementáció

#include <iostream>
#include <cmath>

using namespace std;

double gradient_descent(double (*f_prime)(double), double start, double learning_rate, int iterations) {
    double x = start;
    for (int i = 0; i < iterations; ++i) {
        double grad = f_prime(x);
        x = x - learning_rate * grad;
        cout << "Iteráció " << i + 1 << ": x = " << x << ", f'(x) = " << grad << endl;
    }
    return x;
}

// Függvény deriváltja
double f_prime(double x) {
    return 2 * x - 4;
}

int main() {
    // Paraméterek
    double start_point = 0.0;
    double learning_rate = 0.1;
    int max_iterations = 20;

    // Gradient descent futtatása
    double optimal_x = gradient_descent(f_prime, start_point, learning_rate, max_iterations);
    cout << "Optimális x érték: " << optimal_x << endl;

    return 0;
}

Kimenet:

Iteráció 1: x = 0.4, f'(x) = -4
Iteráció 2: x = 0.76, f'(x) = -3.2
...
Iteráció 20: x = 2, f'(x) = 0
Optimális x érték: 2

---

Alkalmazások

1. Gépi tanulás:
   • Súlyok és paraméterek optimalizálása neurális hálózatokban.
2. Optimalizáció:
   • Matematikai modellek illesztése adatokhoz.
3. Adatelemzés:
   • Függvények minimális hibájának megtalálása.

---

Összegzés

A Gradient Descent egy hatékony és egyszerű optimalizációs algoritmus, amely széles körben alkalmazható különböző területeken. Bár érzékeny a paraméterekre, megfelelő konfigurálás esetén robusztus eredményeket nyújt. Modern alkalmazásokban gyakran kombinálják továbbfejlesztett technikákkal, például adaptív tanulási rátával (Adam, RMSprop).

További információk

• gradient descent - Szótár.net (en-hu)
• gradient descent - Sztaki (en-hu)
• gradient descent - Merriam–Webster
• gradient descent - Cambridge
• gradient descent - WordNet
• gradient descent - Яндекс (en-ru)
• gradient descent - Google (en-hu)
• gradient descent - Wikidata
• gradient descent - Wikipédia (angol)