Cum se ajunge la partea de sus pe kaggle, sau matriksnet la domiciliu, savepearlharbor

Am împărți povestea în următoarele secțiuni:
1. Condiții de concurență;
2. Crearea de noi caracteristici;
3. O regresie logistică - nuri de gradient adaptiv;
4. Matriksnet - reconstrucția completă a algoritmului;
5. Accelerarea învățării mașinii în Python.

1. Condiții de concurență

Datele în sine poate fi descărcat de aici.

- Probabilitatea de eroare negativă (NLL Negativ Probabilitatea Pierdere) a fost declarat ca fiind un criteriu de evaluare

În cazul în care N - este numărul de înregistrări, y - este valoarea de clic, p - probabilitatea ca evenimentul a fost un clic ( „1“).

O proprietate importantă a acestei funcții, eroarea este că dacă p se bazează pe funcția sigmoid, derivata parțială (în continuare, gradient) la (p-y).

2. Crearea de noi caracteristici

Pentru a începe, să ia o privire la datele brute cu care putem lucra:

Aceasta a crea noi:

EXEMPLU id utilizator Formarea

De asemenea, face o mică transformare de conversie / date, vizează în primul rând eliminarea de informații repetitive:

• ora - ora culminant, aruncam o zi;
• C1 - Cred că ceea ce se află în spatele acestei zone de timp, așa că după 2 ore de contopește cu coloana;
• C15 și C16 - se combină, ca în spatele lor ușor de ghicit lățimea și înălțimea a banner-ului, nu are sens să părăsească caracteristicile suplimentare;
• Site-ul * si app * - transformat în plasament *, așa cum este clar că banner-ul este afișat fie pe site-ul sau în aplicația, precum și celelalte valori - doar criptat un NULL, care este în plus. Informațiile nu pot avea loc;
• Eliminăm toate valorile care nu sunt îndeplinite în datele de testare. Acest lucru ajută la reducerea re-formare.

Toate modificările sunt testate utilizând regresia logistică: acestea fie îmbunătățite sau algoritm dau accelerată și nu afectează rezultatele.

3. O regresie logistică (Logistic Regression) - nuri gradientului adaptive

regresie logistică - un algoritm popular pentru clasificare. Există 2 motive principale pentru aceasta popularitate:
1. Ușor de înțeles și de a crea un algoritm;

2. Viteza și adaptabilitatea predicție a datelor mari datorită coborârii de gradient stohastic (gradient de stochastoc coborâre, SGD).

Pe exemplul datelor Avazu arata ca, din cauza gradientului stocastic, noi nu întotdeauna „du-te“, tocmai la un nivel minim:

3.1. gradientul adaptiv

Astfel, vom obține proprietățile benefice ale algoritmului:

• coborâre mai buna, la un nivel minim (rata de învățare scade cu timpul);
• Alpha pentru fiecare caracteristică se calculează individual (ceea ce este foarte important pentru date rare, în cazul în care cele mai multe dintre caracteristicile sunt foarte rare);
• Calculul ia în considerare alfa, cât de mult schimbat parametrul (w) caracteristici: mai mult am folosit, cu atât mai puțin schimbarea în viitor.

gradientului adaptiv începe să fie instruiți în același mod ca și o regresie logistică obișnuită, dar apoi vine la un minim mai mic:

De fapt, dacă convențional gradient de coborâre stocastic repetat de mai multe ori pe aceleași date, acesta poate fi aproape de AdaGrad. Cu toate acestea, va dura mai multe iterații. În modelul său, am folosit o combinație a acestor tehnici: 5 iterații cu algoritmul convențional, și apoi cea cu AdaGrad. Aici sunt rezultatele:

3.2. Transformarea datelor pentru regresie logistică

Pentru algoritmul de regresie logistică poate lucra cu datele (așa cum apar ele în text valori de format), acestea trebuie să fie convertite la o valoare scalară. Am folosit codarea one hot: conversie caracteristici de text într-o matrice de valori co n x „0“ și „1“, unde N - este numărul de înregistrări, și M - numărul de valori unice în această caracteristică. Principalele motive - pentru a păstra cât mai multe informații facilitate tocare vă permite să lucrați rapid cu spațiile cu milioane de caracteristici în cadrul regresiei logistice.

EXEMPLU codare one-hot

4. Matriksnet - asamblare la domiciliu

Să mergem în ordine a ceea ce constituie Maktriksnet:

1. Element de bază - Clasificare și Regresie Arbore (TARC);
2. Algoritmul de bază - Gradient Stimularea mașinii (GBM)
3. Actualizați algoritmul de bază - Stochastic Gradient Stimularea mașină (SGBM).

4.1. Clasificare și Regresie Arbore (TARC)

Acesta este unul dintre clasic algoritmi de arbori de decizie. care a fost deja scris pe Habre (de exemplu, aici și aici). Așa că nu voi intra în detalii, dar permiteți-mi amintesc termenii de principiu și de bază.

Astfel, arborele de decizie are următorii parametri care definesc algoritmul:

• Termeni împărțite în foi (x_1≥0.5)
• „Înălțime“ a arborelui (numărul de straturi cu condițiile din exemplul 2 de mai sus le)
• regula de predicție P® (în exemplul de mai sus utilizat așteptare)

4.1.1. Cum pentru a determina răspunsul la condițiile despicate

La fiecare nivel, avem nevoie pentru a determina caracteristicile condițiilor de pe părți, care se va împărți planul în așa fel încât vom face previziuni mai exacte.

Astfel, toate caracteristicile de trecere și este posibil divizat și selectați acele puncte în care vom avea o valoare de NLL mai mică după divizare (în exemplul de mai sus, desigur, x2). Pentru a determina separarea folosesc de obicei alte funcții - informații câștig și Gini impuritate. dar în cazul nostru vom selecta NLL, așa cum ne cere să reducă la minimum a sarcinii (a se vedea. fișa postului în secțiunea №1).

4.1.2. Regularizarea COȘ

În cazul CART necesită în mod tipic de regularizare, astfel încât să nu facă predicții prea siguri de unde suntem într-adevăr nu sunt sigur. Yandex ofera pentru a corecta formula de predicție, după cum urmează:

În cazul în care N - numărul de valori din listă, și lambda - un parametru de regularizare (experți Maktriksneta recomanda 100, dar ar trebui să fie testate pentru fiecare sarcină separat). Astfel, cu atât mai puțin avem valori în foaia, mai puțin algoritmul nostru este valoarea predictivă încrezător.

4.1.3. copaci uituci (Oblivious copaci)

În Matriksnete în loc de abordarea clasică, atunci când, după scindare x1 următorul nivel al arborelui nu pot partaja date cu privire la această caracteristică, utilizat așa-numitul copaci care sunt uituci în câteva nivele de divizare valori ale aceleiași caracteristici (cum ar fi „uitând“ că divizat a fost deja făcut).

Folosind acest tip de copac, în opinia mea, justificată în primul rând în cazurile în care datele are caracteristici 1-2, splitarea mai înguste, care dau rezultate mai bune decât split-urile de pe mai multe caracteristici neutilizate.

4.2. Masina Stimularea Gradient

Gradient mașină Stimularea (GBM) - este utilizarea pădurii de copaci scurte, în cazul în care fiecare ulterioară nu încearcă să ghicească valoarea-țintă, și încearcă să îmbunătățească prognosticul arborilor anteriori. Să considerăm un exemplu simplu de regresie și a arborilor cu o înălțime de 1 (se poate face doar 1 sciziune în cadrul fiecărui copac).

De fapt, fiecare copac ajută la optimizarea funcției de eroare la pătrat:

Principalul avantaj al GBM în comparație TARC - este mai puțin probabil să se recalifice ca vom da previziuni pe baza foii cu un număr mare de valori CMV. În Matriksnete în GBM «înălțimea“ a arborelui depinde de iterația curentă începe cu 1, la fiecare 10 iterații crește un alt 1, dar nu mai mult de 6. Această abordare poate accelera în mod semnificativ algoritmul, nu rezultate mult mai rau in prima iterație. Am testat această versiune, dar sa oprit pe o variantă, atunci când are loc trecerea la nivelul următor, după epuizarea posibilităților în anul precedent.

4.2.1. clasificarea GBM

Atunci când se lucrează cu clasificarea fiecărui arbore ulterior ar trebui să îmbunătățească predicția cel precedent, dar ar trebui să se facă astfel încât copacii au lucrat la o singură problemă - clasificarea utilizând funcția sigmoid. În acest caz, este convenabil să prezinte problema de optimizare este aceeași ca și în regresia logistică, și anume:

soluție interesantă Yandex este faptul ca initial p0 prognoza de predicție utilizată de regresie logistică și caracteristicile produsului și greutăți (WTX) - ca una dintre caracteristicile.

4.3. Stochastic GBM

Stocastică GBM GBM diferă de convențional prin aceea că fiecare arbore este considerat un eșantion de date (10-50%). Acest lucru ajută atât pentru a ucide 2 păsări cu o piatră - pentru a accelera algoritmul (. Altfel ar trebui să calculeze rezultatul pentru toate 40400000 de înregistrări de formare), și este, de asemenea, eliminarea în mare măsură problema supraantrenament.
Rezultatul final:

După cum se poate observa, în continuare cel mai mare optimizare face de lucru cu date mai degrabă decât pe propriile lor algoritmi. Deși cu regresia logistică de obicei, ar fi dificil să se ridice mai sus, locul 30-lea în cazul în care contul merge la fiecare zece miime.

5. Încercările de a accelera învățarea mașinii în Python

A fost prima mea realizare a proiectului de algoritmi de învățare pe cont propriu, adică în codul, ceea ce face predicții, nu folosesc soluții gata făcute de la terțe părți, toți algoritmii și manipulări ale datelor sunt efectuate în aer liber, care mi-a permis să înțeleagă mai bine obiectivele și principiile de funcționare a acestor instrumente. Cu toate acestea, m-am bucurat de ore de lucru: regresie logistică într-o mare măsură - Abnisheka cod Kaggle, Matriksnet împrumută o mică parte din codul de Stephen Marshall COȘ la învățare carte mașină: algoritmică perspectivă.

În ceea ce privește punerea în aplicare, am început să experimenteze cu sarcina în R, dar apoi repede a dat-o în sus, pentru că este practic imposibil de a lucra cu date mari. Python a fost aleasă datorită simplității sintaxa și prezența unui mare număr de biblioteci pentru învățare mașină.

Problema principală CPython - este foarte lent (deși mult mai rapid R). Cu toate acestea, există mai multe opțiuni pentru a accelera, ca urmare a utilizării următoarele:

• PyPy - JIT-compilator, care poate accelera din nou x20 CPython Standard, principala problemă - nu există practic nici biblioteci pentru a lucra cu calcule (NumPyPy încă în dezvoltare), tot ce trebuie să scrie fără ele. Perfect pentru punerea în aplicare a de regresie logistică cu gradient de coborâre stocastice, la fel ca în cazul nostru;
• Numba - decoratori JIT permite pre-compila unele dintre caracteristicile (un principiu în PyPy), dar restul de cod poate profita de biblioteci de CPython. Un mare plus - pentru funcțiile predefinite pot fi eliminate GIL (Global Interpret Lock) și de a folosi multiprocesor. Ceea ce am folosit pentru a accelera Matriksneta. Problema Numba este același cu cel al PyPy, - nici un suport pentru orice bibliotecă, principala diferență - în Numba este realizarea unor funcții NumPy.

Înainte de a Cython nu a atins, deoarece au încercat să accelereze sângele minim, dar cred că data viitoare mai ușor pentru a merge direct la GPGPU folosind Theano / Numba.

Dacă găsiți orice inexactități sau erori în articol, sau cod, scrie PM.

Trimiterile la sursele utilizate pentru acest articol, și în timp ce lucrează la algoritmii:

JHF / ftp / trebst.pdf

Stochastic Gradient Stimularea - statweb.stanford.edu/