Metode Kernel

METODE KERNEL

În ultimele decenii, evoluția exponențială a colectării datelor în baze de date macroeconomice în format digital a determinat o creștere uriașă a acestora ca volum. Ca o consecință, organizarea automată și clasificarea datelor macroeconomice indicatoriale prezintă o importanță practică deosebită. Diversele tehnici de categorizare a datelor sunt folosite pentru a clasifica numeroasele date macroeconomice în funcție de clasele cărora acestea le aparțin.

Deoarece construcția manuală a unor clasificatori este dificilă și consumatoare de timp, se preferă clasificatori ce învață din exemple de antrenare, proces care alcătuiește clasificarea de tip supervizat.

O variantă de rezolvare a problemei clasificării datelor este aceea prin care se utilizează metodele de tip kernel. Aceste metode reprezintă o clasă de algoritmi folosiți în analiza și clasificarea automată a informațiilor. Majoritatea algoritmilor din această categorie se axează pe soluționarea unor probleme de optimizare convexă și calculul de valori proprii. Aceștia sunt eficienți din punctul de vedere al timpului de calcul și sunt foarte stabili din punct de vedere statistic.

Cel mai cunoscut și cel mai folosit algoritm din această categorie este clasificatorul SVM (support vector machine). SVM-urile sunt clasificatori care au cel mai înalt grad de dezvoltare având rezultate excelente atât la nivel teoretic, cât și la nivel empiric.

În acest context, clasificarea definește o procedură algoritmică care atribuie unui obiect primit drept valoare de intrare (input), o categorie dintr-un set de categorii date. Un exemplu este apartenența unei țări la una dintre cele două clase cărora le poate aparține pe baza datelor indicatoriale macroeconomice ce o caracterizează: “țară prosperă“ – “țară non-prosperă” sau determinarea deciziei economice optime pe baza caracteristicilor observate la nivel indicatorial macroeconomic.

Un algoritm care implementează o problemă de clasificare poartă denumirea de clasificator. De asemenea, clasificator este o noțiune folosită pentru a denumi o funcție matematică implementată de un algoritm de clasificare, ce transformă/mapează datele de intrare (inputs) într-o anumită clasă. Mulțimea datelor de intrare este alcătuit din instanțe/obiecte care sunt grupate în categorii/clase. O instanță este descrisă printr-un vector de caracteristici ale instanței/obiectului. De cele mai multe ori se întâmplă ca datele ordinale și nominale să fie grupate împreună; la fel și în cazul valorilor întregi și reale. Mai mult, există algoritmi care funcționează cu date nominale și necesită discretizarea valorilor întregi sau reale în grupuri (ex: valori10). Clasificarea se referă în mod uzual la o procedură supervizată (o procedură care clasifică noi instanțe, învățând dintr-un set de antrenare cu instanțe ce au fost corect categorizate.

Procedura corespondentă nesupervizată se numește clusterizare (clustering) și constă în gruparea datelor în clase folosind o măsură de similaritate, de cele mai multe ori folosindu-se calculul de distanțe între instanțe/obiecte, acestea din urmă fiind reprezentate sub formă de vectori într-un spațiu vectorial multidimensional.

Au fost efectuate diverse teste empirice pentru a compara clasificatorii între ei, cu scopul de a determina un clasificator optim pentru o anumită problemă, însă rămâne încă în stadiul în care alegerea îi revine utilizatorului, fiind deocamdată o alegere subiectivă.

Categorizarea/clasificarea datelor macroeconomice reprezintă acțiunea automată de a asigna date indicatoriale macroeconomice, unor clase predefinite. Acest mecanism poate oferi o viziune conceptuală asupra colecțiilor de date macroeconomice și are importante aplicații în lumea reală.

Cerința de clasificare a datelor indicatoriale macroeconomice poate fi: 1) clasificare supervizată în cadrul căreia sunt informații cu privire la clasificarea corectă a acestora și la clasele cărora le aparțin și 2) clasificare nesupervizată (clusterizare) în cadrul căreia clasificarea se efectuează doar pe baza similarităților descoperite.

În ultimul timp, numărul datelor ce caracterizează indicatorii macroeconomici a crescut extrem de mult ca volum și continuă să crească pe măsură ce specialiștii din domeniul macroeconomic au nevoie să ia în considerare din ce în ce mai mulți factori reprezentați de indicatorii economici. Astfel că, organizarea automată și clasificarea datelor care alcătuiesc bazele de date indicatoriale macroeconomice prezintă o importanță practică majoră.

Date fiind atât costul ridicat al resurselor umane și/sau materiale pe care îl implică organizarea manuală a datelor macroeconomice indicatoriale sau determinarea claselor cărora acestea aparțin, cât și faptul că anumite clasificări de date macroeconomice sunt efectiv imposibil de realizat într-un anumit interval de timp, se explică interesul crescând asupra găsirii unor metode din ce în ce mai eficiente de aplicat în domeniul clasificării datelor macroeconomice.

Teoria învățării automate utilizează caracteristicile unui proces inductiv care construiește un clasificator de date automat prin învățarea dintr-un set de date clasificate apriori. Avantajele pe care le comportă această abordare sunt acuratețea, reducerea considerabilă a efortului prin prisma faptului că nu este necesară nici o intervenție din exterior sau din partea specialiștilor din domeniu, nici pentru construcția clasificatorului și nici pentru adaptarea acestuia.

Introducere privind metodele kernel

Învățarea automată (Machine Learning) este subdomeniul inteligenței artificiale. Inteligența artificială dorește să modeleze și să controleze în mare măsură cele mai importante activități ce se pot efectua cu ajutorul creierului uman respectiv, clasificarea și predicția. Acele activități prin care se execută clasificarea sunt mașinile automate instruibile.

În ultimele decenii, a fost efectuată o diferențiere din ce în ce mai profundă a componentelor inteligenței artificiale, iar tehnologiile utilizate au devenit absolut indispensabile prin faptul că au reușit să depășească limitele umane.

Două dintre cele mai importante subdomenii ale învățării automate sunt învățarea supervizată și cea nesupervizată. Se știe că, în cazul învățării supervizate există un set de exemple ce conțin etichetele corespunzătoare claselor cărora acestea aparțin, iar în cazul învățării nesupervizate, nu există aceste apartenențe cunoscute apriori, ci acestea se calculează pe baza unor măsuri de similaritate între obiectele mulțimii date.

Algoritmul regresiei ridge a fost publicat de Hoerl and Kennard [9], forma duală a regresiei ridge a fost studiată de Saunders et al. [10], combinația dintre regresia ridge și kernel a fost studiată în literatura de specialitate atât a proceselor gaussiene, cât și a regularizării rețelelor, analiza discriminantă liniară și utilizarea ei alături de funcții kernel a fost de asemenea studiată în literatura de specialitate, iar algoritmul perceptron a fost și el kernelizat. În consecință, literatura de specialitate oferă nenumărate cazuri în care au fost introduse și utilizate cu succes funcțiile de tip kernel.

Funcțiile kernel pe care le putem apela pentru a efectua o clasificare a datelor returnează similaritățile existente între obiecte. Metodele kernel se bazează pe lucrul cu o matrice, matricea kernel, ce conține similaritățile existente între obiectele mulțimii de date considerate. Prin urmare, metodele kernel nu operează cu datele în mod direct.

Funcțiile kernel sunt utilizate pentru extensia neliniară a metodelor liniare, acest lucru realizându-se în cazul în care dacă un algoritm este scris în termenii produselor scalare, atunci se poate schimba matricea de produse scalare cu o funcție sau cu o matrice arbitrară pozitiv semidefinită, iar această funcție sau matrice să conțină produsele scalare ale datelor în spațiul determinat de caracteristicile datelor (feature space). Ca urmare, va fi obținută o extensie neliniară a algoritmului.

Metodele kernel au ca obiectiv învățarea din date, iar acest tip de metode au următoarele avantaje:

se bazează pe un fundament teoretico-matematic extrem de riguros atât prin definirea funcțiilor kernel, cât și a spațiului kernel, folosind teoreme de caracterizare a funcțiilor kernel și teoreme privind gradul de păstrare a proprietăților statistice a metodelor;

sunt un instrument care poate fi folosit în domenii variate, iar această versatilitate se datorează capacității de a învăța datele care sunt reprezentate fie vectorial, fie în alt mod decât vectorial;

poate soluționa eficient problemele de clasificare a datelor utilizate în domenii variate precum bioinformatica, clasificarea documentelor, informatica macroeconomică, regăsirea informației și procesarea imaginilor;

au o trăsătură comună, o particularitate ce definește toate metodele de acest tip și anume, analiza tiparelor neliniare din cadrul unei mulțimi de date (Shawe-Taylor, Cristianini, 2004).

Conform Shawe-Taylor, Cristianini (2004) și Hofmann et al. (2008) se pot reda atât definițiile metodelor kernel, cât și principalele caracteristici ale metodelor de clasificare a datelor bazate pe funcții kernel după cum urmează:

Metodele kernel sunt definite pe baza a două componente: a) o funcție φ care scufundă spațiul de intrare χ într-un spațiu care poate fi de dimensiune mai mare și care împreună cu produsul scalar notat cu F, denumit spațiul caracteristicilor și b) un algoritm de clasificare sau de regresie utilizat pentru detectarea în spațiul caracteristicilor F a funcțiilor șablon liniare ce sunt reprezentate sub formă de produse scalare între punctele spațiului caracteristicilor.

Funcția kernel k este funcția care, satisface relația

k(x,z) = ‹φ(x),φ(z)›, oricare ar fi x și z ∈ χ, (1)

iar φ este o funcție definită pe spațiul χ cu valori în spațiul caracteristicilor F, cu produs scalar:

φ : χ → φ(x) ∈ F. (2)

Pentru ca o funcție kernel să devină un candidat potrivit pentru rezolvarea unei probleme de clasificare, ea trebuie să satisfacă două proprietăți de bază (Shawe-Taylor, Cristianini, 2004):

• funcția kernel trebuie să fie o măsură de similaritate potrivită problemei și domeniului în care se dorește rezolvarea acesteia;

• evaluarea funcției kernel trebuie să conțină un timp computațional semnificativ mai scăzut decât timpul aferent calculului explicit al produselor scalare dintre vectorii de caracteristici definiți de φ.

O trăsătură comună a metodelor kernel este capacitatea de analiză a datelor într-un spațiu al caracteristicilor definit de o funcție kernel de complexitate mai ridicată, comparativ cu spațiul inițial al datelor, pornind numai de la informații legate de produsele scalare efectuate între datele inițiale, furnizate prin matricea kernel.

Metodele kernel au fost reintroduse în anii 1990 împreună cu SVM-urile și sunt funcții liniare, iar în spațiile multidimensionale sunt echivalente cu funcțiile neliniare din spațiul intrărilor. Referitor la aceste metode, analiza statistică arată că marginea extinsă poate rezolva problema dimensionalității datelor, ceea ce a dus la utilizarea metodelor kernel în multe alte domenii, iar algoritmii sunt implementați astfel încât se efectuează calculul produselor scalare dintre vectori (Shawe-Taylor, 2014).

Metodele kernel oferă un cadru stabil din punct de vedere statistic și unitar pentru a descoperi algoritmi care pot acționa pe tipuri generale de date (de exemplu, șiruri, vectori sau text) și caută tipuri generale de relații (de exemplu, clasamente, clasificări, regresie, clustere). Domeniile în care au aplicabilitate aceste metode variază de la rețele neuronale și recunoașterea formelor la învățarea automată și data mining (Shawe-Taylor, Cristianini, 2004).

Prin folosirea funcțiilor kernel se asigură modul de a fi descoperite conexiunile neliniare pe baza unor algoritmi liniari aplicați într-un spațiu al caracteristicilor convenabil ales.

Acest tip de abordare face ca proiectarea algoritmului să nu mai depindă de proprietățile spațiului caracteristicilor, iar acest lucru produce o creștere a flexibilității metodei și este corespunzătoare atât unor algoritmi de învățare automată, cât și proiectării funcțiilor kernel mult mai adaptabili în cadrul analizei datelor. Rezultă că, indiferent de algoritmul utilizat, proprietățile teoretice ale unei funcții kernel date, rămân aceleași.

În aserțiunile ce urmează sunt introduse atât proprietățile ce caracterizează familia funcțiilor kernel, cât și proprietățile ce derivă din acestea și metodele de proiectare a lor. De asemenea, este discutată demonstrarea faptului că nu este posibilă o mașină universală, iar funcțiile kernel trebuie alese în funcție de problemă și de exemplele existente pentru fiecare caz în parte. Este precizat un cadru utilizat pentru cuantificarea compatibilității existente dintre o funcție kernel și o sarcină de învățare (Shawe-Taylor, Cristianini, 2004).

Dacă se dau o funcție kernel și un set de învățare, atunci se poate determina matricea care conține evaluarea efectuată prin funcția dată asupra tuturor perechilor de obiecte ale mulțimii considerate, iar o astfel de matrice funcționează ca un recipient colector de informații despre algoritmul kernel, despre repartiția datelor, despre model sau despre zgomot și de aceea joacă un rol foarte important.

Teorema de caracterizare a funcțiilor kernel

Teorema de caracterizare a funcțiilor kernel: O funcție care este continuă sau are domeniul de definiție o mulțime finită, poate fi descompusă într-o transformare de caracteristici sub forma în cadrul unui spațiu Hilbert, F, aplicată ambelor argumente, urmată de evaluarea produsului scalar din F dacă și numai dacă această transformare satisface proprietatea de a fi semi-definită pozitiv finită (Shawe-Taylor, Cristianini, 2004).

Funcțiile kernel de bază și tipurile de funcții kernel

O funcție kernel trebuie să îndeplinească două proprietăți esențiale pentru o aplicație: 1) trebuie să conțină măsura adecvată a similarității calculată în domeniul respectiv al aplicației și 2) evaluarea ei ar trebui să necesite un timp computațional semnificativ mai scurt decât cel necesar într-o evaluare a transformării a caracteristicilor.

Funcțiile kernel nu sunt restricționate în ceea ce privește valorile intrare de tip vectorial. Astfel că, funcțiile pot fi proiectate pentru structuri și/sau obiecte foarte variate cum ar fi: șirurile de caractere, grafice, documente text, mulțimi și noduri ale grafurilor etc. Ca o consecință a acestei modularități de care dispun funcțiile kernel, având la dispoziție metode de evaluare variate și o diversitate de tipuri de date asupra cărora se pot defini funcțiile de acest tip, reiese imediat că acest tip de abordare a modelării și clasificării datelor permite customizarea necesară a funcției , adaptându-se problemei și domeniului în care este dată aceasta.

Cercetările incipiente ce vizau metodele de tip kernel utilizau doar funcțiile cu formă închisă (closed-form). Introducerea de funcții kernel ANOVA reprezintă primul exemplu de kernel definit printr-o relație recursivă ceea ce face ca evaluarea să fie mai eficientă prin programare dinamică (Shawe-Taylor, Cristianini, 2004). Prin urmare, și celelalte funcții kernel pot fi definite în termenii unor relații recursive sau în termenii unor proceduri foarte generale din punct de vedere computațional.

Metoda de tip kernel poate fi combinată cu o funcție de tip kernel facând astfel posibilă implementarea și reutilizarea algoritmului într-un spațiu multidimensional prin intermediul proprietății de modularitate.

Modularitatea reprezintă posibilitatea de a se lucra cu orice funcție de tip kernel, ceea ce rezultă în aplicabilitatea unui algoritm pentru orice tip de date din orice domeniu, inclusiv din domeniul macroeconomic.

Abordarea de tip kernel a problemei de clasificare a datelor conduce la posibilitatea de a combina module diferite pentru a obține în final sisteme complexe de clasificare a datelor.

Proprietățile computaționale ale metodelor kernel

1) Se pot aplica în spațiile multidimensionale ale caracteristicilor având un cost scăzut în ceea ce privește timpul și spațiul.

2) Algoritmii care folosesc metodele kernel rezolvă problemele de optimizare convexă.

Fig. 4. Etapele aplicării metodelor kernel

Datele sunt procesate utilizând o matrice kernel, care la rândul ei este procesată de un algoritm pentru a produce o funcție model/șablon ce va fi folosită pentru învățarea noilor exemple/puncte/date.

Studiu asupra metodelor kernel

În literatura de specialitate au fost identificate de către Shawe-Taylor, J. și Cristianini, N., trei proprietăți pe care trebuie să le aibă un algoritm pentru a fi aplicabil în domeniul clasificării datelor:

eficiența computațională;

invariabilitate și robustețe la diferitele tipuri de date;

stabilitate din punct de vedere statistic.

De asemenea, au fost efectuate studii și s-a constatat că recodificarea datelor poate duce la creșterea facilitării determinării șablonului sau modelului de date, fiind astfel necesară abordarea de tipul metodelor kernel.

Abordarea de tipul metodelor kernel pentru identificarea șablonului/șabloanelor care există în datele economice corespunde următoarei proceduri:

Se determină spațiul caracteristicilor corespunzător pe baza datelor utilizate;

Se utilizează algoritmi elaborați pe baza algebrei liniare, geometriei și statisticii.

Pentru orice soluție a uneia dintre metodele de tip kernel există două părți componente:

prima este compusă dintr-un modul care execută maparea datelor în spațiul caracteristicilor;

cea de-a doua parte este reprezentată de un algoritm proiectat să determine șabloane/modele liniare existente în respectivul spațiu.

În literatura de specialitate a statisticii și a învățării automate, reprezentând o consecință a studierii și cercetărilor continue în domeniul identificării relațiilor de tip liniar ce există în cadrul datelor, precum și ca urmare a elaborării unor algoritmi robuști, în cadrul metodei kernel se utilizează o funcție kernel, această funcție oferind o formulă computațională simplificată prin care se eficientizează reprezentarea modelelor liniare în spații multidimensionale. În acest fel, se asigură un grad ridicat de reprezentabilitate a datelor.

Shawe-Taylor, J. și Cristianini, N. au demostrat că acest tip de abordare în domeniul clasificării datelor este robustă și eficientă în ceea ce privește detectarea modelelor stabile existente într-o mulțime finită de date. În acest sens, se va efectua modular încorporarea datelor într-un spațiu în care se pot determina anumite relații liniare. Două componente diferite efectuează cele două acțiuni și anume:

1) componenta mapării inițiale sub forma unei funcții kernel ce depinde de tipul datelor și de domeniul de cunoștințe pe care acestea îl caracterizează și se așteaptă anumite modele/șabloane caracteristice domeniului respectiv;

2) componenta ce conține algoritmul caracterizat atât de generalitate, robustețe, din punct de vedere statistic, cât și de eficiență computațională. Această eficiență se exprimă în termeni polinomiali atunci când dimensiunea spațiului crește exponențial.

Cu scopul de a introduce metodele de tip kernel, Shawe-Taylor, J. și Cristianini, N. au utilizat un exemplu de regresie liniară cu ajutorul metodei celor mai mici pătrate și cu toate că acest exemplu este limitat la regresia supervizată, au fost evidențiate anumite aspecte extrem de importante, respectiv:

– datele formează un spațiu vectorial denumit spațiul caracteristicilor;

– modelele liniare existente se caută printre proiecțiile datelor în cadrul spațiului caracteristicilor;

– cu ajutorul produsului scalar calculat pentru perechile de date din spațiul caracteristicilor sunt implementați algoritmii, coordonatele punctelor nemaifiind necesare;

– produsele scalare determinate pentru perechile de date se calculează direct și eficient prin utilizarea unei funcții kernel.

Prin urmare, chiar dacă exemplul oferit de Shawe-Taylor, J. și Cristianini, N. este unul în care algoritmii utilizați optimizează funcții liniare, abordarea prin metode kernel permite descoperirea relațiilor neliniare existente în datele vizate prin folosirea mapărilor de tip neliniar.

Fig. 1. Funcția Φ determină formarea unui spațiu al caracteristicilor datelor în care

modelul/șablonul neliniar devine liniar.

Această funcție kernel calculează produsele scalare direct din datele de intrare (inputs)

(Sursa: Kernel Methods for Pattern Analysis, Shawe-Taylor, Cristianini, 2004)

Se definește un model liniar ca fiind o funcție model ce aparține unei mulțimi de modele bazate pe o clasă de funcții liniare (Shawe-Taylor, Cristianini, 2004).

Regresia liniară într-un spațiu al caracteristicilor cuprinde a) regresia liniară primală, b) regresia ridge primală și duală, precum și c) mapările caracteristicilor neliniare definite kernel.

a) Regresia liniară primală

Fie problema în care se caută o funcție liniară omogenă definită pe mulțimea numerelor reale de tipul

(3), unde x reprezintă vectorii input n-dimensionali x=(x1 ,x2, …,xn), w este un vector n-dimensional, iar reprezintă transpusa vectorului w.

Funcția din relația (3) are gradul de interpolare cel mai ridicat pentru un set de antrenare dat format din punctele xi și etichetele corespunzătoare yi și anume.

Se poate spune că funcția liniară g, definită pe setul caracteristicilor cu valori în mulțimea etichetelor corespunzătoare, prin crearea unei funcții model/șablon având o valoare aproximativ nulă,

(4)

este cea mai simplă relație existentă în produsul cartezian al mulțimilor punctelor și etichetelor corespunzătoare. Acest tip de relație este cunoscută sub denumirea de interpolare liniară, iar din punct de vedere geometric relația corespunde determinării unui hiperplan prin punctele n-dimensionale date în mulțimea considerată. În fig. 2 este dat cazul n=1.

Fig. 2. Problema regresiei liniare pentru cazul unidimensional

(Sursa: Kernel Methods for Pattern Analysis, Shawe-Taylor, Cristianini, 2004)

În cazul în care datele au fost generate sub forma perechilor de tipul (x, g(x)), unde g(x) reprezintă produsul scalar dintre w și x și sunt puncte liniar independente, există posibilitatea de a determina parametrii în urma rezolvării sitemului liniar de ecuații de forma

Xw , (5)

Unde X reprezintă matricea care are liniile date de vectorii linie obținuți prin transpunerea vectorilor coloană ce caracterizează punctele setului considerat, iar y reprezintă vectorul

Se poate observa că input-urile sunt vectori coloană, însă în cadrul matricei X se află sub formă de vectori linie.

I. Dacă numărul punctelor <numărul dimensiunilor

Există și posibilitatea apariției cazului în care numărul punctelor este mai mic decât dimensiunile, iar în acest caz sunt mai multe soluții pentru parametrii w decât sunt oferite de date în mod exact. Situația aceasta impune alegerea vectorului w a cărui normă este minimă, criteriul fiind unul adecvat.

II. Dacă numărul punctelor >numărul dimensiunilor

Există situația în care numărul punctelor este mai mare decât dimensiunile și dacă în plus, există și zgomot în timpul procesului de generare, atunci nu va fi un model/șablon exact și este necesară aplicarea unui criteriu de aproximare. Astfel că, se va alege modelul/șablonul care are eroarea minimă. În general, în cazul mulțimilor mici de date care conțin zgomot, se aplică o procedură care conține un criteriu compus din cele două condiții: un vector w care are mici valorile normei și erorii.

Distanța reprezintă eroarea funcției liniare în cazul mulțimii considerate și se calculează după formula:

(6),

iar această valoare reprezintă valoarea funcției model căutată

(7).

Pentru a avea un caracter generalizat de aplicabilitate, se dorește găsirea unei funcții pentru care să fie mică suma tuturor erorilor rezultate din setul de antrenare. În acest scop, se măsoară diferența dintre datele din setul de antrenare și o anumită funcție după măsura sumei pătratelor erorilor:

, (8),

notând cu pătratul erorii lui asupra exemplului , iar cu notăm pierderea totală a funcției asupra întregului set de antrenare.

În consecință, problema învățării se reduce la alegerea vectorului care minimizează pierderea sau eroarea totală, iar această problemă are ca soluție aproximarea celor mai mici pătrate.

Vectorul care va conține valorile ce reprezintă diferențele poate fi scris sub forma:

(9),

și atunci funcția de pierdere sau eroare poate avea următoarea formă:

Xw Xw (10).

Optimul lui se găsește printre rădăcinile derivatelor parțiale ale funcției pierdere sau eroare în funcție de parametrii

și prin setarea vectorului acestor parametri la vectorul nul se obțin ecuațiile normale

(12)

Dacă există inversa matricei rezultante , atunci soluția problemei celor mai mici pătrate se exprimă sub forma expresiei (13), iar pentru a minimiza pătratul erorii trebuie să fie cât mai mulți parametri sub formă de dimensiuni

(13)

Pentru rezolvarea unui sistem liniar de ecuații de dimensiune este necesar un anumit număr de operații algebrice limitate prin

, constantă,

operații care corespund unei complexități exprimate sub forma unei funcții polinomiale cubice în , adică

Calculul valorii predictibile pentru un punct se poate efectua pe baza unei funcții de predicție

(14).

Observații:

1) Dacă matricea este nesingulară, atunci poate fi exprimat în următorul mod

(15),

de unde rezultă scrierea punctelor de antrenament sub formă de combinații liniare ,

2) Dacă matricea este singulară, atunci poate fi folosită pseudo-inversa care va determina dacă satisface ecuația (12) cu norma minimă.

În cazul în care datele nu conțin suficiente informații pentru a determina exact o soluție, sunt necesare restricții în vederea alegerii funcției, o astfel de restricție fiind definită sub numele de regularizare. Ca urmare, cea mai simplă alegere a funcției ar fi o funcție care are norme mici ca valori, iar în cazul regresiei celor mai mici pătrate rezultă criteriul de optimizare din cadrul regresiei ridge.

Regresia ridge implică rezolvarea următoarei funcții de optimizare:

(16)

și definește relația dintre normă și pierdere, controlând astfelgradul de regularizare. În consecință, problema de învățare se reduce la rezolvarea unei probleme de optimizare în spațiul

Problema primală și duală a regresiei ridge

După derivarea funcției de cost în funcție de parametri se obțin ecuațiile din relația (17):

(17)

Prin urmare, dacă atunci matricea este inversabilă, iar soluția va fi dată de relația (18):

(18)

Soluția ecuației din relația (18) implică rezolvarea unui sistem de n ecuații liniare cu n necunoscute. Complexitatea este . Soluția obținută astfel prin calcularea explicită a vectorului ponderilor se numește soluție primală. Funcția de predicție rezultată este dată de relația (19):

(19)

Rescriind ecuația (17) în funcție de se va obține următoarea relație:

(20)

În relația (20) se poate observa încă o dată că poate fi scris sub formă de combinație liniară între punctele de antrenament, cu

Prin urmare, va rezulta

(21)

În relația (21) se poate scrie sub formă matriceală sau sub forma produsului scalar .

Pentru a afla este rezolvat un sistem cu ecuații liniare și necunoscute ceea ce implică o complexitate . Soluția obținută în urma acestui calcul reprezintă o combinație liniară între exemplele de antrenament considerate și se numește soluție duală, iar parametrii se numesc variabile duale. Funcția de predicție este dată de relația (22) în care am notat cu produsul scalar dintre respectiv :

(22)

Observații

1) Problema de optimizare (16) se poate rezolva prin două metode diferite (Shawe-Taylor, Cristianini, 2004), o soluție fiind rezolvarea ecuației (18), iar cealaltă rezultă din rezolvarea ecuației (21). Soluția duală fiind dată de produsele scalare dintre perechile de puncte de antrenament, analog se va întâmpla în cazul unui nou punct – se calculează produsul scalar dintre punctele de antrenament si noul exemplu.

2) Alegerea uneia dintre cele două metode depinde de dimensiunea n a spațiului caracteristicilor și de numărul al exemplelor de antrenament. Dacă n > atunci calculul soluției duale este mai eficient decât al soluției primale.

3) Evaluarea funcției de predicție în cazul soluției primale are o complexitate , iar în cazul soluției duale complexitatea este

4) Rezolvarea algoritmului regresiei ridge se poate rezolva doar prin calculul produsului scalar dintre datele considerate.

5) Metoda regresiei ridge reprezintă soluția problemei identificării relațiilor funcționale liniare existente între o variabilă selectată și restul caracteristicilor, iar funcția predictivă rezultată poate estima valoarea variabilei selectate prin intermediul valorilor celorlalte caracteristici.

Mapări ale caracteristicilor neliniare definite kernel

Deoarece în general, relațiile căutate sunt neliniare și variabila selectată poate fi estimată adecvat ca o funcție neliniară care depinde de restul caracteristicilor, procedura propusă de Shawe-Taylor și Cristianini (2004) prevede maparea caracteristicilor datelor într-un nou spațiu astfel încât relațiile căutate pot fi reprezentate într-o formă liniară și detectarea acestor relații cu ajutorul regresiei ridge.

Fie maparea

.

Alegerea acestei funcții de mapare are ca obiectiv conversia relațiilor neliniare în relații liniare. Aplicarea funcției presupune transformarea mulțimii de date în mulțimea . O relație de tipul celei căutate are forma:

(23)

Dacă va fi folosită metoda primală, atunci vor exista probleme în cazul în care N este foarte mare deoarece soluția sistemului de ecuații presupune un cost ridicat.

Dacă va fi utilizată metoda duală, atunci este necesar calculul produsului scalar dintre perechile de puncte din spațiul caracteristicilor, .

În particular, pentru calculul funcției predictive se utilizează matricea care are elementele

(24)

liniile lui având ca elemente vectorii caracteristicilor, , iar vectorul are ca elemente valorile

(25).

Observație: Deoarece numărul de operații necesare determină o complexitate mai mare trebuie luate în calcul și alte posibilități de a eficientiza algoritmul/metoda. Există cazuri în care produsele scalare necesare metodei soluției duale se pot calcula într-o manieră mai eficientă sub forma unei funcții directe de caracteristici, o funcție kernel, fără a calcula în mod explicit maparea , ceea ce înseamnă că pasul în care se efectuează reprezentarea vectorială poate fi eliminat din cadrul algoritmului.

Cazul particular n=2

Fie un spațiu bidimensional și o mapare a caracteristicilor

:

Atunci , spațiul de funcții liniare considerat, va fi

Maparea caracteristicilor preia datele dintr-un spațiu bidimensional și le transformă într-un spațiu tridimensional astfel încât relațiile liniare din spațiul caracteristicilor corespund relațiilor cuadratice din spațiul intrărilor. Elementele obținute prin maparea caracteristicilor se evaluează pe baza calculelor produsului scalar astfel:

În consecință, funcția este o funcție kernel și este spațiul corespunzător caracteristicilor. Rezultă că se pot efectua calculele legate de produsul scalar între proiecțiile pe spațiul caracteristicilor a două puncte fără a evalua în mod explicit coordonatele lor.

Observații:

1) Aceeași funcție kernel calculează produsul scalar corespunzător mapării pentru spațiul având 4 dimesiuni

:

2) Spațiul caracteristicilor nu este unic determinat de funcția kernel.

Generalizare

Fie un spațiu -dimensional , atunci funcția este o funcție kernel corespunzătoare mapării caracteristicilor

Acest lucru are loc deoarece avem

Analizând complexitatea operațiilor efectuate, se poate observa că în cazul formei duale a algoritmului de regresie ridge aceasta este pentru calculul vectorului , față de o predicție a complexității de , demonstrând astfel că funcțiile kernel îmbunătățesc complexitatea operațiilor în cazul calculului produsului scalar în spațiul caracteristicilor, iar aceasta conduce atât la eficientizarea algoritmilor în spațiile multidimensionale, cât și la utilizarea ambelor forme, primală și duală, a algoritmului.

Proprietatea de modularitate

Este de remarcat faptul că algoritmul nu depinde de funcția kernel și nici funcția kernel nu depinde de algoritmul aplicat. Această proprietate de modularitate permite schimbarea algoritmului sau modificarea funcției kernel fără a fi necesare alte schimbări/modificări adiacente, separând astfel proiectarea și analiza algoritmului de proiectarea și analiza funcției kernel.

Observații:

1) Metodele kernel implementează regresia neliniară utilizând un spațiu al caracteristicilor definit kernel.

2) Metodele kernel se pot utiliza în rezolvarea a nenumărate probleme existente în clasificarea datelor macroeconomice.

Relația dintre metodele kernel și alte metode de clasificare a datelor

Clasificarea

Se consideră metoda de clasificare supervizată a datelor. Se dă setul de puncte din mulțimea , cu etichetele din mulțimea ,

.

Se cere determinarea unei funcții de predicție astfel încât eroarea să fie mică. Știm că Pentru ca pierderea să fie discretă și valoarea așteptată să fie probabilitatea ca un exemplu aleator să fie greșit clasificat de funcția a fost inclusă valoarea 0,5.

Fig. 3. Crearea unui hiperplan printr-o funcție liniară pentru clasificare

(Sursa: Kernel Methods for Pattern Analysis, Shawe-Taylor, Cristianini, 2004)

În fig. 3 hiperplanul este reprezentat de linia îngroșată, regiunea pozitivă fiind deasupra, iar cea negativă dedesubt; vectorul definește o direcție ortogonală pe hiperplan, iar valorile lui translatează hiperplanul, determinând și alte poziții paralele cu hiperplanul considerat inițial.

Prin urmare, o reprezentare ce are parametri liberi poate descrie toate posibilele hiperplane în spațiul

Specialiștii din domeniul statisticii și rețelelor neuronale denumesc acest tip de clasificatori discriminanți liniari, respectiv perceptroni.

Fie vectorul pondere. Pentru selectarea acestui vector există diferiți algoritmi, majoritatea putând fi aplicați în forma lor duală.

Algoritmul perceptron pentru clasificare

Algoritmul perceptron de clasificare utilizează date care aparțin unui spațiu n-dimensional și caută un vector, w, cu proprietatea că w separă liniar în mod absolut două mulțimi conținute în același set de date astfel încât toți vectorii din mulțimea P să se afle în semispațiul pozitiv, iar toți vectorii din mulțimea N să se regăsească în semispațiul negativ.

Pasul 1: Input o mulțime de date de antrenament care reprezintă reuniunea a două mulțimi, P și N. Se inițializează ponderile și numărul iterațiilor.

Pasul 2: Se introduce un vector ca input și se calculează output-ul.

Pasul 3: Se actualizează ponderile după o formulă care conține informații despre numărul iterației și output-ul așteptat pentru a determina mulțimea ponderilor optime.

Pasul 4: Se repetă pașii 2 și 3 până când este îndeplinită una din următoarele două condiții: eroarea rezultată din iterație este mai mică decât eroarea specificată de utilizator sau un număr specificat de iterații a fost completat.

Observație: Pentru a determina mulțimea optimă de ponderi este necesar să se calculeze performanța rețelei neuronale prin folosirea unor formule de calcul al erorii (funcția de cost).

Algoritmii SVM pentru clasificare

SVM-urile fac parte din tehnicile de tip kernel și reprezintă un grup de metode de clasificare supervizată care sunt o extensie a modelelor neliniare.

Algoritmul SVM general

Pasul 1:Input S. S fiind o mulțime de puncte de antrenament etichetate

Pasul 2: Se caută un hiperplan care să clasifice datele astfel încât acesta să se afle cât mai departe de punctele date, distanța dintre puncte și hiperplan să fie optim minimizată, algoritmul SVM găsește hiperplanul care are distanța minimă cea mai mare față de punctele considerate.

Pasul 3: Output H. H este un hiperplan optim care clasifică noile date.

Teoremă

Fie , ales arbitrar. Presupunem că un exemplu de antrenament

este extras conform unei repartiții și este separabil liniar în spațiul caracteristicilor definit implicit de funcția kernel și având parametrii de ieșire și funcția . Atunci funcția determină marginea dură a SVM în spațiul caracteristicilor definit de cu marginea geometrică În plus, eroarea de generalizare a clasificatorului rezultat este limitată de

având probabilitatea , iar este matricea kernel corespunzătoare.

Analiza componentelor principale

Deoarece relațiile caracteristicilor unui set de date sunt importante pentru a reduce dimensionalitatea există tehnici prin care se pot obține mai multe informații din date prin utilizarea unui număr mai mic de coordonate. Pentru a obține un set mai mic de variabile se aplică funcții ale caracteristicilor inițiale astfel încât datele să poată fi redate pe baza noilor coordonate.

În situația în care se folosesc funcții liniare problema se reduce la proiectarea datelor pe un spațiu de dimensiuni mai mici astfel încât distanța dintre un vector și proiecția sa să fie cât mai mică pentru a păstra cât mai multe din informațiile originale.

Problema minimizării distanța medie pătratică dintre vectori și proiecțiile lor se poate rezolva printr-o tehnică ce presupune proiectarea datelor dintr-o mulțime pe spațiul determinat de primii k vectori proprii ai matricei , cu și astfel coordonatele unui nou vector din noul spațiu pot fi obținute pe baza proiecției sale pe vectorii proprii . Tehnica se numește analiza componentelor principale.

Datele pot fi incluse într-o primă etapă într-un spațiu al caracteristicilor și apoi să se efectueze proiecția acestora în acel spațiu în cazul neliniar. În această situație funcțiile de tip kernel pot defini spațiul caracteristicilor de vreme ce algoritmul necesită doar produsele scalare dintre datele introduse. Astfel, se pot determina relații neliniare între variabilele din date prin introducerea acestor date într-un spațiu indus de o funcție de tip kernel și în acest mod relațiile liniare pot fi determinate prin aplicarea tehnicii kernel de analiză a componentelor principale.

Clusterizarea (clasificarea nesupervizată)

Clusterele de puncte existente într-o mulțime cu date dintr-o mulțime se pot determina prin identificarea unui anumit număr de centre cărora le sunt atribuite punctele pe baza distanței minime dintre punct și centru.

În cazul în care numărul de centre este fixat procedura se numește -means și este necesară măsurarea distanței dintre două puncte, iar această distanță poate fi calculată folosind doar prin produsul scalar, conform formulei de mai jos:

De asemenea, dacă această distanță se alătură unei reprezentări duale a mediei unei mulțimi de puncte date atunci procedura -means poate fi implementată într-un spațiu definit kernel. Dezavantajul unei astfel de aplicații îl reprezintă eficiența foarte scăzută.

Crearea unei noi funcții de tip kernel prin normalizare

Pentru a fi utilizate la scară generalizată, funcțiile de tip kernel trebuie să se poată construi conform domeniului datelor în care vor fi aplicate. Dacă elementele input sunt sub forma unui spațiu vectorial de tipul există produsul scalar denumit spațiu liniar kernel. Se știe că o funcție polinomială kernel poate transforma un kernel liniar dintr-un spațiu al caracteristicilor într-un produs scalar, doar prin utilizarea câtorva operații, astfel nefiind afectată complexitatea algoritmului aplicat.

Fie o funcție kernel care corespunde unei mapări a caracteristicilor, . Atunci prin normalizare corespunde unei mapări a caracteristicilor

iar va fi o funcție de scris astfel:

Pentru a putea utiliza diferite tipuri de date, este necesar să fie dezvoltate funcții kernel corespunzătoare mapării inputurilor și acestea să nu fie vectori ai spațiului caracteristicilor.

În acest sens se consideră spațiul intrărilor ce constă din mulțimea tuturor submulțimilor unei mulțimi alese arbitrar și funcția kernel a două submulțimi, și , definită ca numărul de submulțimi comune prin

Această funcție kernel corespunde unei mapări a caracteristicilor din spațiul vectorial de dimensiune , reprezintă reuniunea tuturor submulțimilor, iar imaginea unei mulțimi este vectorul cu proprietatea că

Validitatea/validarea unei funcții de tip kernel este exprimată/efectuată prin existența corespondenței cu un produs scalar din spațiul caracteristicilor.

De altfel, dacă o funcție poate fi evaluată eficient și corespunde calculului produsului scalar, atunci acea funcție constituie o potențială funcție kernel ce poate fi utilizată.

Selectarea funcției kernel optime se efectuează în urma evaluării relației dintre informațiile inițiale conținute în datele considerate și tipurile de modele/șabloane pe care le dorim să fie identificate ca output-uri. Evaluarea acestei relații se va face prin examinarea modului de a fi derivate funcțiile kernel din modele probabilistice ale procesului de generare a datelor.

Construcția de funcții complexe de tip kernel se poate efectua pe baza caracteristicilor explicite, pe baza măsurilor de similaritate sau pe baza oricăror alte tipuri de informații extrase din datele inițiale. Prin folosirea unor componente pentru a crea funcții de tip kernel este dovedită proprietatea de modularitate.

Noțiuni și proprietăți ale produsului scalar

Ținând cont de faptul că datele pot fi incluse într-un spațiu multidimensional în care se poate efectua analiza liniară a formelor pe baza analizei neliniare din spațiul intrărilor și știind că această tehnică poate fi aplicată fără a suferi modificări la nivel computațional datorită metodelor kernel, atunci se poate spune că algoritmii analizei formelor pot fi aplicați asupra imaginii datelor de antrenament din spațiul caracteristicilor prin evaluarea indirectă a produselor scalare. Știm deja că o funcție kernel este o funcție care returnează produsul scalar dintre imaginile perechilor de intrări (inputs) dintr-un spațiu al caracteristicilor.

Spații Hilbert

Definiție 1. Fie spațiul vectorial cu valori reale și o funcție definită pe acest spațiu, . Această funcție este liniară dacă sunt îndeplinite simultan următoarele condiții:

1. ;

2. pentru orice x, z și

Definiție 2. Un spațiu vectorial cu valori reale este un spațiu al produsului scalar (spațiul liniar euclidian) dacă există o formă biliniară (liniară în fiecare argument), simetrică și pozitivă cu valori reale astfel încât Această mapare se numește produs scalar.

Observație: Dacă atunci produsul scalar se numește produs scalar strict.

Definiție 3. O normă se poate defini pe spațiul bidimensional al unui produs scalar strict prin formula , iar distanța dintre doi vectori asociată acestei norme va fi .

Definiție 4. Pentru spațiul vectorial produsul scalar este definit prin formula:

Observație: Dacă produsul scalar nu este strict, punctele pentru care determină un subspațiu liniar astfel încât și dacă atunci pentru orice rezultă că Prin urmare, întotdeauna se poate transforma un produs scalar într-un produs scalar strict.

Definiție 5. Un spațiu vectorial pe care a fost definită o distanță se numește spațiu metric astfel încât spațiul produsului scalar este și el tot un spațiu metric.

Definiție 6. Un spațiu Hilbert este un spațiu al produsului scalar care este separabil ( o mulțime finită de elemente din astfel încât are loc ) și complet (pentru fiecare șir Cauchy de elemente din converge către , iar un șir Cauchy este un șir cu proprietatea că , cu m>n și n).

Definiție 7. Fie mulțimea tuturor șirurilor de numere reale astfel încât

și produsul scalar al două șiruri este dat de

Acest spațiu astfel definit se numește

Observație: Un spațiu Hilbert complet și separabil este izomorf cu cu finit sau este izomorf cu spațiul .

Metodele kernel necesită ca spațiul caracteristicilor să fie un spațiu complet și separabil. Folosirea formei duale de reprezentare nu implică și construirea vectorilor de caracteristici, chiar dacă antrenăm o funcție liniară reprezentată sub forma unui vector al ponderilor. Acest vector al ponderilor este o combinație liniară de vectori ai caracteristicilor punctelor de antrenament.

Elementele unui spațiu Hilbert sunt funcții liniare prin produsele scalare; pentru un punct , funcția corespunzătoare este dată de

Prin urmare, determinarea vectorului ponderilor este echivalentă cu identificarea elementului corespunzător din spațiul caracteristicilor.

În lucrarea lui Shawe-Taylor și Cristianini din 2004 sunt date următoarele două exemple de spații ale produsului scalar:

Exemplul 1: Fie . De asemenea, fie fixate numere pozitive, este o matrice pătratică având ca elemente . Un produs scalar definit pe spațiul este dat de:

Exemplul 2: Fie spațiul vectorial al funcțiilor pătratice integrabile pe o mulțime compactă din împreună cu proprietățile de aditivitate și înmulțire cu scalar

Atunci pentru , se definește produsul scalar prin

Observație: Într-un spațiu al produsului scalar are loc inegalitatea Cauchy-Schwarz:

.

Definiție 8: Unghiul dintre doi vectori ai unui produs scalar este dat de formula

cos .

Definiție 9: O submulțime de vectori din mulțimea notată se numește ortonormală dacă , unde are valoarea 1 pentru și are valoarea pentru .

Pentru o mulțime ortonormală și un vector , expresia

se numește serie Fourier pentru . Dacă seriile Fourier pentru sunt egale cu pentru orice , atunci mulțimea este și ea bază. Cum un spațiu Hilbert este echivalent cu sau cu , atunci se poate găsi o bază ortonormală, iar această bază poate fi utilizată pentru a defini izomorfismul dintre spațiul Hilbert considerat și sau dintre spațiul Hilbert dat și

Rangul unei matrice de dimensiune este egal cu dimensiunea spațiului determinat de coloanele matricei. Astfel că, rangul lui este cel mai mic pentru care, având o matrice de dimensiune ale cărei coloane liniar independente formează o bază pentru spațiul lui , iar este o matrice de dimensiune ale cărei coloane reprezintă coloanele lui în acea bază, se poate scrie expresia:

pentru care se observă că .

Deoarece este de dimensiune , rangul lui rangul lui . Prin simetrie cele două ranguri sunt egale, ceea ce implică faptul că dimensiunea spațiului determinat de liniile lui este de asemenea egal cu rangul lui

Observații:

1) Dacă o matrice de dimensiune are rangul egal cu min atunci matricea are rangul maxim.

2) În domeniul învățării automate, funcțiile kernel pot fi reprezentate sub formă de matrici Gram.

Matricea Gram

Fiind dată o mulțime de vectori, , matricea Gram este definită ca fiind matricea de dimensiune ce are ca elemente . Dacă utilizăm o funcție kernel pentru a evalua produsele scalare dintr-un spațiu al caracteristicilor cu o mapare a caracteristicilor, atunci matricea Gram asociată se numește matrice kernel și are elementele

.

Observații:

1) Matricea Gram are un rol important în forma duală a unor algoritmi de învățare.

2) Matricea Gram este simetrică deoarece , cee ce implică faptul că G.

3) Matricea Gram conține toate informațiile necesare pentru a calcula perechile de distanțe dintre date.

4) Prin comparația între informațiile din vectorii mulțimii originale și informațiile conținute de matricea Gram se constată că există o anumită pierdere. Această pierdere de informații de referă la orientarea mulțimii originale de date față de origine datorată faptului că matricea produselor scalare este invariantă la rotații în raport cu originea.

5) În plus, reprezentarea sub formă de matrice Gram pierde informațiile legate de aliniamentul dintre puncte și axe, iar acest lucru provine din faptul că matricea Gram este invariantă la rotații astfel încât orice rotație a sistemului de coordonate nu va produce schimbări asupra matricei produselor scalare.

6) Pentru forma duală a algoritmului de regresie ridge (regresia ridge fiind recomandată în vederea atenuării sau eliminării multicoliniarității) se observă că singurele informații legate de setul de antrenament, informații primite de algoritm, sunt cele din matricea Gram sau din matricea kernel și valorile output asociate. Cu alte cuvinte, în matricea kernel sunt conținute toate informațiile pe care le pot extrage algoritmii de analiză a formelor din datele de antrenament și din spațiul caracteristicilor ales, precum și informațiile legate de etichetele datelor.

7) Matricea kernel este tipul de date central pentru toți algoritmii de tip kernel. Matricea poate fi văzută ca un furnizor de informații, în sensul că aceasta trebuie să pună la dispoziția algoritmilor suficiente informații despre date pentru ca aceștia să poată fi aplicați.

Așadar, în literatura de specialitate este foarte important să fie studiate proprietățile acestor matrice, modul în care acestea sunt create, modalitățile lor de adaptare, felul în care aceste matrice se potrivesc problemelor ce trebuie rezolvate.

Matrice singulare și valori proprii

O matrice A se numește singulară dacă există o combinație neliniară coloanele lui A egală cu vectorul nul. Fie un vector nenul care conține coeficienții combinației considerate, aceștia fiind notați cu astfel încât A 0.

Dacă o matrice A este pătratică cu dimensiunea este nesingulară atunci coloanele sunt liniar independente și spațiul are dimensiunea . Prin urmare, se pot determina vectorii astfel încât, pentru vectorii unitate , să aibă loc relația

Matriceal, relația de mai sus poate fi scrisă astfel:

, de unde rezultă că , inversa matricei .

Fiind dată o matrice pentru care este adevărată relația Ax , atunci numărul real se numește valoare proprie, iar x se numește vectorul propriu corespunzător.

Urmează că, numărul 0 este o valoare proprie a unei matrice dacă și numai dacă matricea este singulară.

Pentru o pereche formată dintr-un vector propriu și o valoare proprie și pentru matricea A pătratică ce are elemente numere complexe cu proprietatea că este egală cu conjugata transpusei acesteia, atunci are loc

.

Acest coeficient se numește coeficient Rayleigh și reprezintă un instrument utilizat pentru dezvoltarea algoritmilor din domeniul învățării automate.

Fie problema de optimizare

.

Deoarece soluția este invariantă la rescalare, se poate impune restricția ca și se poate rezolva utilizând un multiplicator Lagrange. Se obține pentru o matrice simetrică optimizarea pentru care soluțiile derivatelor parțiale în raport cu v ne dau relația Av Presupunând că un vector propriu este normalizat, atunci vectorul propriu al celei mai mari valori proprii este soluția optimizării max, iar valoarea proprie corespunzătoare reprezintă valoarea maximului.

O soluție este garantată deoarece se caută maximul pentru o mulțime compactă. Analog, pentru a găsi minimul valorii proprii.

Norma spectrală a unei matrice A se definește prin

.

Definiție: O matrice pătratică se numește simetrică dacă , ceea ce înseamnă că un element este egal cu elementul , pentru orice , .

Definiție: O matrice este diagonală dacă dacă toate toate elementele care nu aparțin diagonalei principale sunt nule. O matrice pătratică este triunghiulară superior/inferior dacă toate elementele de deasupra/de dedesubtul diagonalei principale sunt nule.

Pentru matricele simetrice vectorii proprii corespunzători unor valori proprii distincte sunt ortogonali. Fie o a doua valoare proprie cu și vectorul corespunzător, se observă că:

de unde rezultă că .

În consecință, dacă A este o matrice simetrică de dimensiune , atunci poate avea cel mult valori proprii distincte. Fie o pereche formată dintr-un vector propriu și o valoare proprie corespunzătoare a matricei , atunci transformarea

se numește deflație, iar ca urmare a faptului că este normalizat rezultă că

astfel încât deflația reduce valoarea proprie la valoarea nulă.

Deoarece vectorii proprii corespunzători valorilor proprii distincte sunt ortogonali, valorile proprii ale lui A rămân nemodificate. Prin aplicarea repetată a algoritmului pentru a determina vectorul propriu corespunzător valorii proprii maxime pozitive/minime negative și apoi aplicând deflația, rezultă o mulțime ortonormală de vectori proprii. Acești vectori proprii corespunzători unei valori proprii nule sunt adăugați unei baze ortonormale prin extinderea mulțimii de vectori proprii obținuți prin deflație. Dacă se formează o matrice care are drept coloane vectorii proprii și o matrice diagonală cu elementele , valorile proprii corespunzătoare, atunci se va obține

și

O astfel de procedură se numește descompunere proprie a matricei , iar mulțimea valorilor proprii, , se numește spectrul. Se presupune că valorile proprii apar în ordine descrescătoare,

O matrice care are proprietatea că I este o matrice ortonormală. Minorii principali ai unei matrici sunt matricele obținute prin selectarea unui determinant din liniile și coloanele matricei inițial considerată.

Dacă matricea simetrică A are valori proprii nenule atunci descompunerea proprie poate si exprimată prin relația:

unde și sunt matricele care conțin cele coloane ale lui și minorul principal al lui corespunzător valorilor proprii nenule. Astfel, rangul maxim al lui A este . Fiind dat un vector în spațiul determinat de coloanele matricei rezultă că

unde este matricea diagonală inversă astfel încât coloanele matricei A determină același spațiu de dimensiune . Acest lucru implică faptul că rangul unei matrice simetrice A este egal cu numărul valorilor ei proprii nenule.

Pentru o matrice care are toate valorile proprii nenule relația se poate scrie sub forma

Pentru matricele simetrice norma spectrală poate fi evaluată simplu pentru că descompunerea proprie a matricei este dată de

Astfel încât spectrul lui este . De asemenea,

Teorema Courant-Fisher: Dacă este o matrice simetrică, atunci pentru , cea de-a k valoare proprie a matricei A, satisface relația:

cu punctul de extrem atins de vectorul propriu corespunzător, iar T este un subspațiu de o dimensiune specificată.

Observație: Teorema Courant‐Fisher caracterizează valorile proprii prin maximizarea sau minimizarea coeficientului Raleigh în subspațiul T și apoi se alege subspațiul pentru minimizarea maximului sau pentru maximizarea minimului. Cea mai mare valoare proprie corespunde cazului în care dimensiunea subspațiului este cea a spațiului și astfel se maximizează coeficientul în întreg spațiul.

Definiție: O matrice simetrică se numește pozitiv semidefinită (pozitiv definită) dacă toate valorile ei proprii sunt nenegative (pozitive). În acest caz, dacă și numai dacă , pentru orice vector , iar valoarea proprie minimă satisface relația

Propoziție Matricele Gram și matricele kernel sunt pozitiv semidefinite.

Propoziție O matrice A este pozitiv semidefinită dacă și numai dacă , pentru matrice cu elemente numere reale.

Observație: Alegerea matricei B nu este unică.

Propoziție: O matrice este pozitiv semidefinită (pozitiv definită) dacă și numai dacă toți minorii principali sunt pozitiv semidefiniți (pozitiv definiți).

Determinantul det(A) al unei matrice pătratice este produsul valorilor sale proprii. Prin urmare, pentru o matrice pozitiv definită determinantul va fi strict pozitiv, iar pentru matricele singulare acesta va fi nul.

Dacă se consideră matricea ca transformare liniară Ax calculează proiecția lui pe vectorii proprii care formează coloanele matricei , înmulțirea cu modifică proiecțiile, iar înmulțirea cu recalculează vectorul rezultat.

Urma tr(A) a unei matrice pătratice A este suma elementelor sale de pe diagonala principală, tr (A)

Deoarece

tr () tr (),

urma matricei rămâne invariantă la transformări de forma pentru că

.

Luând din descompunerea proprie a lui A, urma unei matrice este egală cu suma valorilor sale proprii.

Caracterizarea funcțiilor kernel

Se știe că o funcție kernel calculează produsul scalar al două puncte utilizând o funcție definită pe spațiul mulțimii de puncte considerate

De asemenea, modul de formare a unei matrice de perechi de date de intrare pentru o funcție kernel are ca rezultat o matrice pozitiv semidefinită. O funcție kernel definește implicit un spațiu al caracteristicilor și în majoritatea cazurilor definirea construirii acestui spațiu nu trebuie efectuată explicit, ceea ce conduce la o mai bună eficiență.

Observație: În situația în care structura datelor și cunoștințele asupra unor aplicații specifice sugerează necesitatea unei modalități de comparare a perechilor de date de intrare existente într-o mulțime, funcția care efectuează această comparare poate fi o funcție kernel.

Caracterizare generală a funcțiilor kernel

Un mod de a verifica dacă o funcție este o funcție de tip kernel este acela prin care se construiește un spațiu al caracteristicilor pentru care funcția corespunde, în primă fază, unei mapări a caracteristicilor și, în a doua fază, corespunde calculării produsului scalar. Prin această tehnică s-a demonstrat (Shawe-Taylor, Cristianini, 2004) că funcția polinomială este o funcție kernel.

O alternativă pentru demonstrarea că o funcție este de tip kernel este o modalitate teoretică de a creea noi funcții kernel și de a combina funcții kernel pentru a obține unele noi.

Observație: Relația dintre funcțiile kernel și matricele pozitiv semidefinite reprezintă un element cheie în determinarea alternativei de verificare a unei funcții care poate fi de tip kernel.

Definiție: Fie o funcție . Dacă această funcție este simetrică pentru matricele determinate de constrângerea/restricția ca pentru orice submulțime finită a spațiului sunt pozitiv semidefinite, atunci funcția este finită și pozitiv semidefinită.

Observație: Această definiție nu impune ca mulțimea să fie un spațiu vectorial.

În cele ce urmează se va efectua demonstrația legată de faptul că proprietatea de a fi o funcție finită pozitiv semidefinită este proprietatea caracteristică funcțiilor de tip kernel. Prin construirea explicită a spațiului caracteristicilor se va efectua această demonstrație.

Teorema de caracterizare a funcțiilor kernel: O funcție

care este continuă sau este definită pe o mulțime finită, se poate descompune într-o mapare a caracteristicilor, într-un spațiu Hilbert aplicată ambelor argumente și urmată de evaluarea produsului scalar în

dacă și numai dacă funcția are proprietatea de a fi finită și pozitiv semidefinită.

Fiind dată o funcție și această funcție are preoprietatea de a fi finită și pozitiv semidefinită atunci spațiul ei corespunzător, notat cu , se numește Spațiul Hilbert Kernel Reproducător (Reproducing Kernel Hilbert Space – RKHS) (Shawe-Taylor, Cristianini, 2004). Analog, notația se folosește pentru a desemna produsul scalar corespunzător.

Proprietatea de reproducere Ca urmare a faptului că orice funcție kernel poate fi utilizată pentru a construi un spațiu Hilbert în care există proprietatea de reproducere, atunci dacă o funcție simetrică satisface proprietatea de reproducere într-un spațiu Hilbert de funcții astfel încât , pentru unde este o familie de funcții pentru învățare, atunci satisface proprietatea de a fi finită și pozitiv semidefinită, atât timp cât are loc:

Observație: Pentru a construi un spațiu al caracteristicilor pentru o funcție kernel validă se utilizează teorema lui Mercer. Această teoremă completează caracterizarea unei funcții de tip kernel și definește spațiul caracteristicilor în termenii unui vector al caracteristicilor explicit.

Teorema lui Mercer: Fie o submulțime compactă din . Presupunem că funcția este o funcție simetrică și continuă astfel încât operatorul integral :

este pozitiv

ceea ce rezultă că

pentru orice .

Atunci putem extinde într-o serie uniform convergentă pe în termenii funcțiilor , care îndeplinesc relațiile și .

În plus, seria este convergentă.

Exemplu

Fie o funcție kernel . Oastfel de funcție se numește invariantă la translații atât timp cât produsul scalar a două date rămâne nemodificat în cazul în care perechea de date este translatată de același vector. Se consideră cazul unidimensional în care este definit pe intervalul astfel încât poate fi extins la o funcție reală periodică, simetrică și continuă. Acest tip de funcție poate fi extins către o serie Fourier uniform convergentă .

Prin urmare, poate fi extinsă după cum urmează:

.

Șirul este un șir de elemente pozitive, prin urmare acest lucru arată faptul că este produsul scalar din spațiul caracteristicilor definit de mulțimea caracteristicilor ortogonale deoarece funcțiile 1, și alcătuiesc o mulțime de funcții ortogonale pe intervalul.

În consecință, normalizarea acestora va furniza o mulțime de caracteristici Mercer. Se observă faptul că embedding este definită independent de parametrii , care controlează geometria spațiului caracteristicilor.

Observație: Exemplul anterior arată rolul jucat de alegerea funcției kernel. Parametrii din extinderea sunt coeficienții săi Fourier. Dacă, pentru arbitrar, avem , caracteristicile corespunzătoare sunt eliminate din spațiul caracteristicilor. Analog, valorile mici ale lui reprezintă faptul că acea/acele caracteristică/caracteristici are/au o mai mică pondere și prin urmare va/vor avea o mai mică influență asupra alegerii hiperplanului. Așadar, alegerea funcției kernel poate reprezenta alegerea unui filtru care are o anumită caracteristică spectrală al cărei efect este acela de a controla influența diverselor frecvențe pentru a determina optima separare.

Funcții kernel de covarianță

Conform teoremei lui Mercer o funcție kernel poate fi exprimată ca sumă de produse ale funcțiilor de produse scalare

.

Acest lucru sugerează un nou punct de vedere asupra funcțiilor kernel ca funcții kernel de covarianță determinate de o repartiție de probabilitate peste o clasă de funcții. În general, fiind dată o repartiție peste o clasă de funcții , atunci funcția de covarianță este dată de expresia

se numește funcție kernel de covarianță.

Relația de mai sus este o funcție kernel deoarece există funcția de mapare

și produsul scalar este definit prin

Pentru ca o funcție să fie o funcție kernel de învățare aceasta este redată de relația: în care spațiul conține funcții de forma

.

Pentru funcția kernel , spațiul său corespunzător este unidimensional și conține multiplii lui . Prin urmare, se poate spune că funcția este o combinație de funcții kernel simple pentru toate funcțiile ponderate conform repartiției condiționate anterior, .

În consecință, orice funcție kernel derivată prin această procedură se va constitui într-o funcție kernel validă pentru că se verifică proprietatea de a fi finită și pozitiv semidefinită

Mai mult, în cazul în care clasa de funcții are valorile , atunci funcția kernel va fi normalizată și are loc relația:

Observație: Orice funcție kernel se poate obține sub forma unei funcții kernel de covarianță pentru care reparția are o anumită formă.

Fie o funcție kernel validă repartiția Gaussiană care generează funcții conform relației:

,

unde sunt funcții ortonormale pentru funcția kernel , iar funcțiile sunt generate conform repartiției Gauss – media 0 și abaterea standard 1.

Deoarece ortonormalitatea lui poate restricționa norma sa prin

=

Atunci această funcție va avea probabilitatea 1 în spațiul .

Deoarece norma este o funcție pozitivă, urmează că măsura funcțiilor care nu se află în spațiul este nulă. Funcția nu va aparține clasei de funcții în cazul spațiilor infinit dimensionale. De aceea, repartiția va fi definită pe spațiul . Funcția de covarianță va avea următoarea formă:

.

Matricea kernel

Fie o mulțime de antrenament și funcția kernel , există matricea kernel sau matricea Gram având elementele , pentru

Funcția este o funcție kernel validă care furnizează matrice kernel pozitiv semidefinite pentru orice mulțime de antrenament, adică proprietatea de a fi finită și pozitiv semidefinită. Această proprietate determină manipularea funcțiilor kernel fără a fi necesar spațiul corespunzător al caracteristicilor. Proprietatea menționată asigură validitatea funcției kernel, în sensul că există un spațiu al caracteristicilor pentru care corespunde funcția kernel respectivă.

Modularitatea conținută de mașinile kernel înseamnă că orice funcție kernel poate fi utilizată pentru a determina matrice kernel pozitiv semidefinite și simetrice și orice algoritm kernel este aplicabil atât timp cât acesta acceptă ca date de intrare o astfel de matrice alături de informații necesare pentru etichetare. Ca urmare, matricea kernel are rol de interfață pentru datele de intrare și modulele de învățare.

Matricea kernel și informațiile critice (bottleneck)

Matricea kernel reprezintă componenta principală în teoria metodelor kernel. Această matrice conține toate informațiile disponibile pentru pasul în care se efectuează învățarea, exceptând cazul etichetelor datelor de ieșire pentru învățarea supervizată. Numai prin intermediul matricei kernel algoritmul de învățare obține informații legate de alegerea spațiului caracteristicilor și a datelor de antrenament.

Unele dintre proprietățile acestei matrice pot determina performanța de a generaliza un sistem de învățare. În funcție de problema de învățare pentru care se aplică, proprietățile variază, însă matricea kernel are un rol important și reprezintă structura centrală a datelor.

Reprezentarea datelor poate fi îmbunătățită cu ajutorul proprietății matricei kernel de a fi finită și pozitiv semidefinită și astfel, poate fi îmbunătățită performanța globală a sistemului de învățare.

Exemplu

Adăugarea unei constante la elementele diagonalei principale are efectul introducerii unei margini slabe (soft margin) în clasificare.

Observații

1) În cazul seturilor de date foarte mari este posibil ca matricea kernel să nu poată fi memorată și astfel, să fie necesar să fie recalculată funcția kernel sub forma elementelor matricei. Acest lucru are anumite consecințe asupra alegerii algoritmului.

2) Indiferent de tipul (vectori reali, șiruri de caractere, structuri discrete, imagini, serii de timp ș.a.) datelor de intrare (inputs) caracterizarea funcțiilor kernel valide se face prin intermediul proprietății de a fi finite și pozitiv semidefinite.

3) Matricele kernel corespunzătoare oricărei mulțimi finite de antrenament sunt pozitiv semidefinite, funcția kernel calculează produsul scalar după proiectarea inputurilor pe un spațiu al caracteristicilor.

Fig. 4. Utilizarea funcțiilor kernel pentru aplicarea algoritmilor aupra datelor care nu sunt vectoriale

(Sursa: Kernel Methods for Pattern Analysis, Shawe-Taylor, Cristianini, 2004)

Observații:

1) Funcția kernel conține toate informațiile disponibile pentru mașina de învățare referitoare la pozițiile relative ale inputurilor în spațiul caracteristicilor.

2) În cazul în care trebuie determinată structura din cadrul mulțimii de date, aceasta se va determina prin intermediul matricei kernel.

3) În cadrul metodei kernel se acordă fiecărei perechi de date de intrare aceeași pondere a similarității/disimilarității astfel încât elementele diagonalei secundare a matricei kernel devin foarte mici, iar elementele diagonalei principale sunt aproape unitare. De aceea, metoda kernel poate reprezenta doar conceptul de identitate, ceea ce duce la fenomenul de overfitting.

4) Dacă o mstrice kernel este complet uniformă, atunci orice input este similar cu fiecare dintre inputuri. Fiecărui input mapat îi va corespunde același vector al caracteristicilor, iar acest lucru conduce la fenomenul de underfitting deoarece singurele funcții care pot fi ușor reprezentate sunt cele care mapează toate punctele în aceeași clasă.

5) Funcțiile kernel pot determina similaritatea dintre două puncte. Dacă se utilizează kerneluri normalizate, atunci se pot exprima ca

,

adică probabilitatea a priori a inputurilor de a se afla în aceeași clasă minus probabilitatea a priori de a fi în clase diferite.

6) În cazul unei funcții kernel de covarianță asupra unei clase de funcții de clasificare avem repartiția și are loc:

.

7) Se observă că matricea kernel poate fi descompusă după

unde sunt vectorii proprii, iar sunt valorile proprii corespunzătoare. Vectorii proprii pot determina spațiul caracteristicilor, chiar dacă acesta este determinat de mulțimea datelor de antrenament. Extinzând relația de la funcțiile proprii la operatorul integral, vom avea

,

ceea ce ne oferă construcția spațiului caracteristicilor din teorema lui Mercer. Prin urmare, o funcție kernel poate fi definită peste funcțiile proprii ale operatorului kernel.

8) Pentru învățarea supervizată care are ca rezultat un vector care are ca elemente valorile , se consideră matricea , numită hessiana, definită ca produsul Schur dintre matricea yy’ și K. Dacă este o pereche ce aparține mulțimii atunci ( ) este o pereche ce aparține mulțimii , unde , pentru orice

Selectarea unei funcții kernel

Selectarea unui kernel se face în mod ideal pe baza cunoștințelor domeniului problemei respective deținute anterior și pe baza restricțiilor impuse învățării asupra selectării funcției model/șablon din spațiul caracteristicilor definit de funcția kernel aleasă. Alegerea a priori a funcției kernel nu e întotdeauna cea corectă și este forțată considerarea unei familii de funcții kernel definite astfel încât să reflecte clasele așteptate, dar care să permită alegerea funcției kernel particulare care va fi utilizată.

Ca urmare, trebuie ca în primă fază să se efectueze alegerea unei funcții kernel din familia de funcții considerate și apoi să fie selectată o funcție model/șablon din spațiul caracteristicilor funcției kernel alese.

Conul matricelor kernel

Matricele pozitiv semidefinite formează un con în spațiul vectorial al matricelor pătratice de dimensiune , unde prin con se înțelege o mulțime închisă pe care sunt definite operațiile de adunare și înmulțire cu scalari nenegativi (Shawe-Taylor, Cristianini, 2004).

Acest lucru este important deoarece funcțiile trebuie să fie convexe pentru a asigura existența unor metode eficiente, pentru a efectua optimizarea asupra unor astfel de matrice. Studiul optimizării asupra unor astfel de mulțimi se întâlnește în literatura de specialitate sub denumirea de programare semidefinită (semidefined programming SDP).

O măsură de similaritate între două kerneluri este introdusă cu ajutorul produsului scalar Frobenius dintre perechile de matrice care au dimensiuni identice:

.

Norma matricei corespunzătoare se numește normă Frobenius. Dacă se consideră tr() ca o funcție de , gradientul său este

Pe baza acestui produs scalar se poate defini o măsură simplă de similaritate dintre două matrice kernel, și , în următoarea definiție.

Definiție: Funcția alignment dintre două matrice kernel și este dată de relația:

Observație: Funcția alignment dintre o matrice kernel și este (, yy’), iar yy’ este funcția kernel ideală pentru y. Pentru , (, yy’) va fi

Observație: Funcția alignment poate fi asimilată cosinusului unghiului dintre cele două matrice reprezentate de vectori -dimensionali, it satisfies Definirea funcției alignment nu utilizează faptul că matricele sunt pozitiv semidefinite.

Propoziție: Fie simetrică. Atunci este pozitiv semidefinită dacă și numai dacă pentru orice pozitiv semidefinită.

Observație: Funcția alignment poate fi de asemenea considerată drept coeficient de corelație Pearson între variabilele aleatoare și generate având repartiție uniformă asupra perechilor . În plus, această funcție este legată de distanța dintre matricele kernel normalizate cu norma Frobenius

Construcția funcției kernel

Caracterizarea funcțiilor kernel și a matricelor kernel este utilă pentru a decide dacă o funcție candidat considerată reprezintă o funcție kernel validă și pentru a justifica o serie de reguli pe baza cărora se pot manipula și combina funcțiile kernel simple pentru a obține funcții kernel complexe.

Clasa funcțiilor kernel este o mulțime închisă pe care sunt definite operațiile asupra funcțiilor kernel și operațiile asupra matricelor kernel.

Operațiile asupra funcțiilor kernel

Propoziție: Fie funcțiile kernel definite pe o funcție valoare reală definită pe cu o funcție kernel definită pe , este o matrice pătratică simetrică pozitiv semidefinită de dimensiune . Atunci următoarele funcții sunt funcții kernel:

(i) ;

(ii) ;

(iii) ;

(iv) ;

(v) ;

(vi)

Observație: Combinația de funcții kernel din (iii) este denumită în literatura de specialitate produs Schur. Orice funcție kernel poate fi descompusă ca produs Schur de normalizări și funcția kernel unidimensională cu

Introducerea funcțiilor kernel are ca motivație căutarea unor modele neliniare prin utilizarea de funcții liniare în spațiul caracteristicilor creat prin folosirea uneu mapări nelianiare a caracteristicilor.

Propoziție: Fie o funcție kernel definită pe , și este o funcție polinomială cu coeficienți pozitivi. Atunci următoarele funcții sunt și funcții kernel:

(i) ;

(ii) ;

(iii) .

Observație: Ultima funcție kernel din propoziția anterioară este cunoscută sub denumirea de funcție kernel gaussiană.

Observație: S-a demonstrat că noile funcții obținute din funcții simple kernel sunt tot funcții kernel deoarece sunt pozitiv semidefinite. Este necesar să fie clar efectul combinațiilor de funcții kernel asupra structurii spațiului corespunzător al caracteristicilor.

Pentru a efectua adunarea a două funcții kernel vectorul caracteristicilor este concatenarea vectorilor corespunzători

pentru că

=

.

Caracteristicile sunt produsele tuturor perechilor de caracteristici de forma care sunt date de relația pentru și unde este dimensiunea spațiului caracteristicilor corespunzătoare lui Prin urmare, produsul scalar este dat de

=

.

Definiția spațiului caracteristicilor din acest caz depinde de alegerea sistemului de coordonate deoarece folosește o funcție de înglobare. Faptul că noua funcție kernel se poate exprima în termenii unor funcții kernel de bază demostrează că aceasta este invariantă la această alegere a sistemului. Pentru cazul unui exponent al unei singure funcții kernel

se obține prin inducție faptul că spațiul caracteristicilor corespunzător este indexat de toate funcțiile monomiale de grad

,

cu satisfies

Observație: În cadrul acestei înglobări se observă că respectivele caracteristici monomiale nu au aceeași pondere. Acest lucru se datorează fatului că în acest caz există repetiții în prelungirea (extensia) funcției, adică produse ale caracteristicilor individuale care conduc la aceeași funcție . De exemplu, pentru cazul bidimensional produsul scalar poate fi scris

=

Observație: Funcția kernel gaussiană este o funcție kernel polinomială de grad infinit. Astfel că, caracteristicile sale sunt toate monoamele caracteristicilor input fără a avea restricții asupra gradelor acestora. Prelungirea Taylor expansion a funcției exponențiale exp arată că ponderea monoamelor individuale este .

Operații asupra funcțiilor kernel

– transformarea spațiului caracteristicilor prin aplicarea operațiilor asupra matricei kernel, aceasta rămânând pozitiv semidefinită și simetrică; dezavantajul acestei operații este că nu se știe cum se va efectua calculul kernel pentru noile puncte de testare.

– transformarea matricei kernel corespunde unei tranformări calculabile în spațiul caracteristicilor, astfel fiind posibilă calcularea funcției kernel asupra punctelor.

S-a demonstrat că metodele kernel pot oferi un cadru stabil și valid în domeniul metodelor de clasificare a datelor și prin urmare, și a datelor macroeconomice.

Utilizarea funcțiilor kernel în domeniul macroeconomic

Predictorii din domeniul macroeconomic și financiar doresc să fie maximizată acuratețea predicției efectuate și să fie minimizată complexitatea modelului utilizat. Existența unui număr mare de variabile este cauzată de incertitudinea ridicată din aceste domenii economice și determină o dimensionalitate direct proporțională.

În încercarea de a depăși problemele ivite din cauza supradimensionalității spațiului au fost aplicate mai multe tipuri variabile predictor pentru a se obține un număr mai mic de componente principale care sunt ulterior utilizate pentru predicție într-un model de factori dinamici (Stock, Watson, 2006).

Abordările existente în aceeași direcție pentru aplicare în domeniul macroeconomic includ predicții combinate bazate pe modele multiple, fiecare dintre acestea incluzând un număr cât mai mic de variabile (Faust, Wright, 2009; Wright, 2009; Aiolfi, Favero, 2005; Huang, Lee, 2010; Rapach et al., 2010; Exterkate et al. 2012), metoda parțială a celor mai mici pătrate (Groen, Kapetanios, 2008), și regresia Bayesiană (De Mol et al., 2008; Banbura et al., 2010; Carriero et al., 2011). Stock and Watson (2009) au găsit că pentru a efectua predicția unor serii de timp macroeconomice, abordarea modelului factorilor dinamici este preferabilă celorlalte variante enumerate. Au fost realizate cu succes aplicații în domeniul financiar (Ludvigson, Ng, 2007, 2009; Cakmakli, van Dijk, 2010). Au fost efectuate cercetări în direcția predicției pe baza posibilei existențe a relațiilor neliniare între seriile de timp financiare și macroeconomice (Terasvirta, 2006; White, 2006; Kock, Terasvirta, 2011). S-a dovedit că aceste metode sunt potrivite pentru un număr mic de predictori și abilitatea lor de se îmbunătăți este limitată în privința tehnicilor liniare de predicție (Stock and Watson, 1999; Medeiros et al. 2006, Terasvirta et al., 2005).

Giovannetti (2011) a propus o abordare de tip hibrid, estimând un model neliniar prin extragerea componentelor principale dintr-o mulțime mare de predictori.

Exterkate et al. (2012) au introdus o tehnică de predicție care poate să depășească atât dimensionalitatea ridicată, cât și neliniaritatea.

Ideea de bază este aceea de a angaja un set flexibil de funcții de predicție neliniare și pentru a preveni fenomenul de overfitting (învățarea pe de rost) prin penalizare, într-un mod care limitează complexitatea calculului prin regresia ridge kernel, în cadrul căreia setul de predictori este mapat într-un spațiu de dimensiuni mari sau infinit-dimensional determinat de funcțiile neliniare ale predictorilor.

Prin alegerea convenabilă a metodei kernel se pot evita dificultățile unor calcule efectuate într-un spațiu multidimensional și de asemenea, se pot omite dificultățile întâlnite în cazul metodei standard de regresie ridge liniară. În acest caz, numărul de variabile predictor este relativ mare față de numărul observațiilor existente în seriile de timp.

Metodologia de tip kernel s-a dezvoltat în domeniul machine learning, un domeniu care implică lucrul cu volume mari de date. Noțiunea de kernel provine din faptul că tot setul de calcule ce trebuie efectuat se realizează în termenii unei funcții kernel a unui operator integral pozitiv (Vapnik, 1995).

O aplicație tipică a metodelor kernel este clasificarea (Scholkopf et al., 1998). Potențialul utilizării metodelor de tip kernel a fost confirmat într-o aplicație empirică pentru a efectua predicția asupra a 4 indicatori pentru activitatea macroeconomică a S.U.A. pentru 1970-2009. În comparație cu rezultatele slabe ale metodelor tradiționale, rezultatele regresiei ridge kernel sunt îmbunătățite substanțial. De asemenea, această metodă este cel mai puțin afectată de datele existente în perioada crizei economice din 2008-2009, față de metodele tradiționale utilizate (Exterkate et al., 2012).

Bibliografie

Shawe-Taylor, J., Cristianini, N., Kernel Methods for Pattern Analysis, Cambridge University Press, 2004. Disponibilă la http://cs.du.edu/~mitchell/mario_books/Kernel_Methods_for_Pattern_Analysis_-_John_Shawe-Taylor_&_Nello_Christianini.pdf.

Shawe-Taylor, J., Kernel Methods for Pattern Analysis, Machine Learning Tutorial Imperial College, February 2014

Exterkate, P., Groenen, P.J.F., Heij, C., van Dijk, D, Nonlinear Forecasting With Many Predictors Using Kernel Ridge Regression, International Conferences on Computational and Financial Econometrics (Limassol, October 2009, and London, December 2010), 2012.

Stock, J.H., Watson, M.W. Why has U.S. inflation become harder to forecast? Journal of Money, Credit and Banking, 39:3–33, 2007.

Stock, J.H., Watson, M.W. Generalized shrinkage methods for forecasting using many predictors. Manuscript, Harvard University, 2009.

Terasvirta, T. Forecasting economic variables with nonlinear models. In G. Elliot, C.W.J. Granger, and A. Timmermann, editors, Handbook of Economic Forecasting, pages 413–458. Elsevier, Amsterdam, 2006.

Terasvirta, T., van Dijk, D, Medeiros, M.C. Linear models, smooth transition autoregressions, and neural networks for forecasting macroeconomic time series: A re-examination. International Journal of Forecasting, 21:755–774, 2005.

Vapnik, V.N. The Nature of Statistical Learning Theory. Springer, New York, 1995.

Hoerl, A.E., Kennard, R.W. Ridge regression: Biased estimation for nonorthogonal problems. Technometrics, 12(1) (1970): 55–67, 1970.

10.Saunders, C., Gammermann, A., Vovk, V., Ridge regression learning algorithm in dual variables. In J. Shavlik, editor, Machine Learning: Proceedings of the Fifteenth International Conference(ICML ’98). Morgan Kaufmann, 1998.

Bibliografie

Shawe-Taylor, J., Cristianini, N., Kernel Methods for Pattern Analysis, Cambridge University Press, 2004. Disponibilă la http://cs.du.edu/~mitchell/mario_books/Kernel_Methods_for_Pattern_Analysis_-_John_Shawe-Taylor_&_Nello_Christianini.pdf.

Shawe-Taylor, J., Kernel Methods for Pattern Analysis, Machine Learning Tutorial Imperial College, February 2014

Exterkate, P., Groenen, P.J.F., Heij, C., van Dijk, D, Nonlinear Forecasting With Many Predictors Using Kernel Ridge Regression, International Conferences on Computational and Financial Econometrics (Limassol, October 2009, and London, December 2010), 2012.

Stock, J.H., Watson, M.W. Why has U.S. inflation become harder to forecast? Journal of Money, Credit and Banking, 39:3–33, 2007.

Stock, J.H., Watson, M.W. Generalized shrinkage methods for forecasting using many predictors. Manuscript, Harvard University, 2009.

Terasvirta, T. Forecasting economic variables with nonlinear models. In G. Elliot, C.W.J. Granger, and A. Timmermann, editors, Handbook of Economic Forecasting, pages 413–458. Elsevier, Amsterdam, 2006.

Terasvirta, T., van Dijk, D, Medeiros, M.C. Linear models, smooth transition autoregressions, and neural networks for forecasting macroeconomic time series: A re-examination. International Journal of Forecasting, 21:755–774, 2005.

Vapnik, V.N. The Nature of Statistical Learning Theory. Springer, New York, 1995.

Hoerl, A.E., Kennard, R.W. Ridge regression: Biased estimation for nonorthogonal problems. Technometrics, 12(1) (1970): 55–67, 1970.

10.Saunders, C., Gammermann, A., Vovk, V., Ridge regression learning algorithm in dual variables. In J. Shavlik, editor, Machine Learning: Proceedings of the Fifteenth International Conference(ICML ’98). Morgan Kaufmann, 1998.