Gradientlaskumine

Gradientlaskumine on üks olulisemaid algoritme, mida kasutatakse masinõppe mudelite treenimiseks, võrrandisüsteemide lahendamiseks ja paljuks muuks. Ma ei kirjutaks sellest, kui ma saaksin päris hästi aru, kuidas gradientlaskumine toimib. Seega üritan siin postituses väheke selgust luua, kuidas antud iteratiivne meetod töötab.

Mis see gradient siis on? Natuke matemaatikat gradient vektori kohta.

Gradiendi märk on see kolmnurk e. delta ja antud mitme muutujaga funktsiooni puhul on ta lihtsalt vastavate osatuletiste summa. Kolmas valem on skalaarkorrutis gradiendi ja vektori u vahel, mis annab tuletise u suunas.

Teoreem:

Suunaga tuletise maksimum väärtus on |Grad[f[x]]| ja see esineb kohal, kus u-l on sama suund, mis Grad[f[x]]-il .

Seega gradient on vektor ja tal on pikkus ning suund. Tema suund näitab maksimumi suunas antud punktis.

Et mugavam oleks töötada vektoritega, kasutatakse maatrikseid. Jacobi maatriks on funktsiooni kõigi osatuletiste maatriks kujul:

Kui mitme muutujaga funktsioon f[x] on differentseeruv punkti a läheduses, siis ta väheneb kõige kiiremini negatiivse gradiendi suunas. Seda on näha antud joonisel, kus mööda negatiivset gradienti liikudes liigume nagu mäest alla.

Joonis 1
Joonis 2

Siit ka traditsiooniline gradientlaskumise valem.

, kus n on sammu pikkkus ( tavaliselt tähistatakse Kreeka eta tähega, mis meenutab ka n-i ). Siit hüppan edasi järgmise teema juurde, mis on üks võimalus rakendada gradientlaskumist.

Olgu antud mõned punktid x ja y koordinaatidega ja me tahame sobitada neist läbi joone, mis minimeeriks ruutjääkide summat. Ruutjääkide summa on üks võimalikest funktsioonidest, mida minimeerida. Olgu antud A(0.5, 1.4), B(2.3, 1.9), C(2.9, 3.2) . Joone võrrand on teadagi ax + b, a-ks võtame etteantud väärtuse 0.64. Hiljem lahendame ka 2D versiooni sellest ülesandest, kus on vaja leida nii a kui b. b-d hakkame leidma ja võtame kõigepealt b-ks 0-i. b on teadagi koht, kus joon läbib y telge. Seega tuleb prognoositav y väärtus sellise joone võrrandiga kohal x=0.5

0 + 0.64 * 0.5 = 0.32

Jääk on ( vaadeldav y – prognoositav y ). Vaadeldav y on antud joonisel kohal x=0.5 prognoositavast üleval pool ( 1.4 vs 0.32 ) Jäägiks sellel kohal tuleb siis 1.4 – 0.32 = 1.1 Järgmise punkti B juures tuleb jäägiks 0.4 jne. RJS (ruutjääkide summa) = 1.1^2 + 0.4^2 + 1.3^2 Siit ka nimi RJS. RJS näitab kui palju antud mudel prognoosides eksib.

Esialgne mudel

Nüüd tuleb oluline samm, kus esitame RJS-i funktsioonina RJS[b], ehk siis määrame x teljel b väärtused ja y teljel RJS-i väärtused kohal b.

RJS[b] = (1.4 – ( b + 0.64 * 0.5) )^2 + ( 1.9 – ( b + 0.64 * 2.3 ) )^2 + ( 3.2 – ( b + 0.64 * 2.9 ) )^2

Selle funktsiooni graafik on parabool:

Nüüd me tahame leida funktsiooni RJS[b] absoluutset minimumi, mis teadagi on kohal, kus RJS[b] tuletis võrdub nulliga. Siin tuleb liitfunktsiooni puhul kasutada ahelreeglit.

See tuletis tuleb midagi sellist:

d/db = -2 * ( t1 – ( ax1 + b) ) -2 * ( t2 – ( ax2 + b) ) -2 * ( t3 – ( ax3 + b) )

Või numbritena:

-2 *( 1.4 – (b + 0.64 * 0.5) ) -2*(1.9 – (b + 0.64 * 2.3 ) ) -2*( 3.2 – ( b + 0.64 * 2.9 ) )

, kus kõik peale b on konstandid. Pannes nulli b asemele, nagu me esialgse prognoosi puhul tegime, saame vastuseks -5.7 Korrutame selle õppimise kiirust iseloomustava koefitsiendiga 0.1 ja saame -0.57, mis on selle iteratiivse meetodi nö. sammu pikkus. Uus b väärtus on vana – sammupikkus

0 – (-0.57) = 0.57

Seega tehes esimese sammu liikusime optimaalsele b-le tunduvalt lähemale.

b = 0.57 vs b = 0

Kui b = 0, siis parabooli puutuja tõus on -5.7 Mida lähemale me b optimaalsele väärtusele jõuame, seda lähemale jõuab puutuja tõus nullile. Gradientlaskumist kasutatakse tavaliselt juhul kui derivaati ei ole võimalik otseselt arvutada.

Edasi võtame selle tuletise d/db = -2 *( 1.4 – (b + 0.64 * 0.5) ) -2*(1.9 – (b + 0.64 * 2.3 ) ) -2*( 3.2 – ( b + 0.64 * 2.9 ) ) ja paneme uue b, mis on 0.57 vana b asemele, see annab parabooli puutuja tõusuks uue väärtuse -2.3. Korrutame seda jälle 0.1-ga ja saame sammu pikkuseks -0.23 Nüüd võrdub uus b vana b miinus sammupikkus, mis teeb 0.57 – – 0.23 = 0.8 Nii iteratiivselt edasi toimides jõuame lõpuks punkti, kus sammu pikkus on väga väike ( 0.0001) ja võime töö lõpetada. Samuti peatume kui sammude arv on suurem kui mingi ette antud väärtus.

Nüüd vaatame, kuidas leida nii a kui ka b.

RJS[a,b] = (1.4 – ( b + a * 0.5) )^2 + ( 1.9 – ( b + a * 2.3 ) )^2 + ( 3.2 – ( b + a * 2.9 ) )^2

RJS[a,b]

Me otsime jälle a ja b väärtusi, mis annavad miinimum ruutjääkide summa. Leiame kõigepealt jälle tuletise d/db suhtes.

d/db = -2 *( 1.4 – (b + a * 0.5) ) -2*(1.9 – (b + a * 2.3 ) ) -2*( 3.2 – ( b + a * 2.9 ) )

d/da = -2 * 0.5 ( 1.4 – ( b + a * 0.5)) – 2 * 2.3 ( 1.9 – ( b + a * 2.3) – 2 * 2.9 ( 3.2 – ( b + a * 2.9

Nüüd valime suvaliselt b = 0 ja a = 1

d/db tuleb sel juhul -1.6 ja d/da tuleb -0.8

Edasi määrame sammu pikkuse b suhtes 0.01 ( – 1.6) = -0.016 ja sammu pikkuse a suhtes 0.01 (-0.8) = -0.008 Kasutame väiksemat koefitsienti seekord ( 0.01 ). Uus b = vana b – sammu pikkus b suhtes, b = 0 – -0.016 = 0.016 ja a= 1 – -0.008 = 1.008

Edasi paneme jälle uued a ja b sinna osatuletiste valemitesse ja kõik kordub kuni mingi lõpetamise kriteerium aktiveerub, nagu ennem mainitud.

Nüüd ma hüppan jälle uue alateema juurde. Kirjutaks midagi c# keeles, mis kiirendaks lahendamist. Kood on järgmine:

public class Point
    {
        public Point(double x, double y)
        {
            this.x = x;
            this.y = y;
        }
        public double x = 0;
        public double y = 0;
    }

class Program
    {
        static void Main(string[] args)
        {
            //A(0.5, 1.4), B(2.3, 1.9), C(2.9, 3.2)
            Point[] points = new Point[3];
            points[0] = new Point(0.5, 1.4);
            points[1] = new Point(2.3, 1.9);
            points[2] = new Point(2.9, 3.2);
            GradientFit(points, 1000, 0.01);
            Console.Read();
        }
        static void GradientFit(Point[] points, int maxIterations, double learningRate)
        {
            double a = 0;
            double b = 0;
            Random r = new Random();
            a = r.NextDouble();
            b = r.NextDouble();
            double stepb = 0;
            double stepa = 0;
            for(int i = 0; i < maxIterations; i++)
            {
                double dda = DDA(points, a, b);
                double ddb = DDB(points, a, b);
                stepb = learningRate * ddb;
                stepa = learningRate * dda;
                b = b - stepb;
                a = a - stepa;
            }
            Console.WriteLine("a = " + a + " b = " + b + " \n") ;
        }
        static double DDB(Point[] points, double a, double b)
        {
            double result = 0;
            for(int i = 0; i < points.Length; i++)
            {
                result += -2 * ( points[i].y - (b + a * points[i].x));
            }
            return result;
        }
        static double DDA(Point[] points, double a, double b)
        {
            double result = 0;
            for (int i = 0; i < points.Length; i++)
            {
                result += -2 * points[i].x * (points[i].y - (b + a * points[i].x));
            }
            return result;
        }

    }

Selle funktsiooniga mängides saab kiiresti selgeks, et ta on päris tundlik õppimise kiiruse koefitsiendi suhtes ( learning rate ).

Gradientlaskumise kiirendamiseks suurte andmehulkade korral kasutatakse stohhastilist gradientlaskumist. Stohhastiline gradientlaskumine võtab antud näite põhjal suvaliselt ühe punkti ja uuendab selle järgi a ja b väärtusi, siis võtab suvaliselt jälle ühe punkti ja uuendab uuesti jne. Antud näite järgi võtab stohhastiline gradientlaskumine kolme asemel ühe punkti neist kolmest ja uuendab selle järgi a ja b väärtusi. Kui on antud näiteks kolme punkti asemel 100000 punkti ja valitakse ainult üks neist, siis see kiirendab andmetöötlust tunduvalt. Seda on näha koodis, kus on näiteks 1000 iteratsiooniga vaja arvutada 1000 * punktide arv tehet. Seda koodi on lihtne muuta stohhastiliseks, jätan selle lugejale ülesandeks.

Stohhastilise gradientlaskumise üks eelis on, et ta on nö. online. See tähendab, et uute andmete saabudes, on võimalik jätkata sealt, kus pooleli jäi.

Veel kasutatakse miniplokk gradientlaskumist, mis on põhimõtteliselt stohhastiline gradientlaskumine, kus võetakse suvaliselt ühe punkti asemel mingi kindla suurusega hulk punkte.

Kokkuvõttes on gradientlaskumine võimas optimeerimise algoritm, mida on piisavalt lihtne kasutada. Öeldakse, et raskem on formuleerida optimeerimise probleem, kui kasutada olemasolevaid optimeerimise algoritme. Selle näite põhjal pole ka kohe ilmne, kuidas a ja b leidmist optimeerimise probleemina formuleerida.

Advertisements