Fundamental Experimental Research in Machine Learning [Romanian]

Cercetare fundamentală experimentală în învăţare de mașină

Thomas G. Dietterich 

Catedra de Informatică

Universitatea de Stat din Oregon

Corvallis, Oregon 97331

Proiect de 24 iunie 1997.

Cercetarea fundamentală în învăţare de mașină este în mod inerent empirică, deoarece performanţa de algoritmi de învațare a maşinii este determinată de cât de bine ipotezele care stau la baza lor se potrivesc cu structura lumii. Prin urmare, nici o cantitate de analiză matematică nu poate determina dacă un algoritm de învăţare de mașină va funcţiona bine. Astfel, sunt necesare studiile experimentale.

Pentru a înţelege această idee, să luăm în considerare problema bine studiată de învăţare supravegheată din exemple. Această problemă este, de obicei, declarată, după cum urmează. Un exemplu exp_research-rom-01 este un n-tuplu trasat de la un set X stabilit în conformitate cu o distribuţie fixă, de probabilitate necunoscută D. O funcție f necunoscută se aplică pentru fiecare exemplu, pentru a produce o etichetă exp_research-rom-02. Etichete pot fi evaluate fie ca cantităţile reale (caz în care problema este menţionată ca o problemă de regresie) sau simboluri discrete (caz în care problema este menţionată ca fiind o problemă de clasificare).

Scopul algoritmilor de învăţare de mașină este de a construi o aproximație h la functia f necunoscută, astfel încât cu mare probabilitate, un nou exemplu exp_research-rom-03 întocmit în conformitate cu D va fi etichetat corect: h (x) = f (x).

De exemplu, să luăm în considerare problema de diagnosticare a bolilor de inimă. Exemplele constau în caracteristici ce descriu pacientul, cum ar fi vârsta, sexul, daca pacientul fumează, tensiune arterială, diferite rezultatele testelor de laborator, şi aşa mai departe. Eticheta indică dacă pacientul a fost diagnosticat cu boli de inimă. Sarcina a algoritmului de învăţare este de a învăţa o procedură de luare a deciziilor, care va face diagnostice corecte pentru pacienţii viitori.

Algoritmi de învăţarea lucrează prin căutarea unor spaţii de ipoteze, H, pentru ipoteza h care este într-un sens cea mai ”bună”. Două întrebări fundamentale a cercetărilor învăţării de mașină sunt (a) ce spații de ipoteze bune se găsesc și (b) ce definiţiile de”cele mai bune'' ar trebui fi folosite? De exemplu, un spaţiu de ipoteză foarte popular H este spaţiul de arbori de decizie, precum şi definirea de ”cel mai bun'' este ipoteza care minimizează estimarea de aşa-numita eroare pesimistică [Qui93].

Acesta poate fi dovedit prin ceea că, dacă toate funcţiile f necunoscute sunt la fel de probabile, atunci toate algoritmi de invățare vor avea performanţe identice, indiferent de spaţiu pe care ipoteza H caută şi care definiţia de ”cel mai bun” o folosește [Wol96, Sch94].  Aceste aşa-numite teoreme de ”nici un prânz gratuit'' rezultă din simpla observare că singurele informaţii pe care are algoritm de învăţare sunt exemple de instruire. Şi exemple de antrenare nu oferă nici o informaţie cu privire la etichetele de puncte noi x, care sunt diferite de exemple. Prin urmare, fără nici o altă sursă de informaţii, nu există nici o bază matematică pentru a face predictii despre f (x).

Prin urmare, eficienţa algoritmilor de învăţare de maşină, în practică, depinde de ceea dacă spațiul ipotezei H este suficient de mic şi conţine aproximări bune la funcţia necunoscută f. (Spaţiul ipotezei trebuie să fie mic pentru a fi căutat într-o cantitate de timp fezabil, în scopul de a sprijini hotărâri statistice de calitate a ipotezei bazate pe cantităţi realiste de date de instruire).

Cercetarea fundamentală în procesul de învăţare a maşinii, prin urmare, implică propunerea diverselor spaţiilor de ipoteze H şi a criteriilor de optimizare, de punere în aplicare a acestor propuneri de programe, precum şi testarea performanţei lor pe o mare colecţie de seturi de date din lumea reala. O colecție mare şi în creştere de probleme de învăţare este menţinută la Universitatea din California de la Irvine [MM96], şi a fost folosită ca baza pentru sute de studii experimentale.

Figura 1 prezintă un rezumat de un astfel de studiu. În acest studiu, unde a fost utilizat pe scară largă copac de algoritm de decizie C4.5 a fost comparat cu un nou algoritm, numit ADABOOST, dezvoltat de Freund şi Schapire [FS96]. Ambele algoritmi au fost aplicate la 27 de diferite probleme de invățare. Pentru fiecare problemă de învăţare, există o sumă fixă ​​de date disponibile în colecţia Irvine. Pentru a evalua un algoritm de învăţare, este folosită una dintre cele două metode. În metoda simplă de refuz, este reţinut un subset aleator selectat din datele disponibile, algoritmul de învăţare este ”instruit” cu privire la datele rămase pentru a produce o ipoteză, h, şi precizia h apoi este măsurată pe datele reţinute. În metoda de cross-validare de 10 ori, datele sunt împărţite aleator în 10 dimensiuni de subseturi egale. Algoritmul de învăţare este executat de 10 ori – de fiecare dată, este instruit pe toate, dar una din cele 10 subseturi e apoi evaluat pe subset rămas. Rezultatele din aceste 10 executări sunt ponderate pentru a estima rata de eroare a algoritmului.

exp_research-rom-04

Figura 1: performanţa comparativă a algoritmului de învăţare C4.5 cu algoritmul ADABOOST aplicat la C4.5.

Figura 1 este un grafic de puncte împrăștiate, în care fiecare punct corespunde unei probleme de învăţare diferite. Coordonata x de fiecare punct este rata de eroare lui ADABOOST privind această problemă, şi coordonata y este rata de eroare lui C4.5. Subliniați faptul că se tot ce se află deasupra liniei y = x are o rată de eroare mai mică pentru ADABOOST. Modelul de puncte arată că, în general, ADABOOST au o performanță mai bună decât C4.5 cu privire la aceste probleme de referinţă.

În plus la comparaţii referitoare la performanţa de bază, de asemenea, studii experimentale au fost efectuate pentru a înţelege şi explica diferenţele dintre algoritmi de învățare. Strategia de bază este de a lua doi algoritmi şi de a înțelege efectele de modificări ale acestor algoritmi care o să sporească sau să elimine diferenţele între algoritmi. De exemplu, într-o comparaţie a C4.5 şi algoritmului de propagare inversă pentru reţele neuronale de formare, Dietterich, Hild, & Bakiri [DHB95] a fost observat că reţelele neuronale au lucrat mai bine decît C4.5 cu privire la problema de cartografiere a cuvintelor în limba engleză în şiruri de foneme (pentru sinteză de vorbire). Ei au identificat trei ipoteze pentru a explica această diferenţă şi au testat aceste ipoteze, prin explorarea efectelor modificărilor la C4.5 şi propagare inversă. De exemplu, o modificare de C4.5 şi propagare inversă pentru a capta anumite forme de informaţii statistice au eliminat cea mai mare parte diferenţelor dintre cele două algoritmi. Ei au făcut acest lucru prin îmbunătăţirea preciziei de C4.5 lăsând în acelaşi timp acurateţea propagării inverse neschimbat. Prin urmare, acesta oferă o explicaţie plauzibilă pentru ce propagare inversă a lucrat mai bine – şi anume, că a propagare inversă deja a capturat aceste informaţii statistice, dar C4.5 – nu.

O altă strategie experimentală implică lăsarea algoritmilor nemodificați, dar modificarea exemplelor de instruire pentru a introduce sau a elimina factorii considerate de a fi importante. De exemplu, pentru a testa toleranța de zgomot de algoritmi diferite, zgomot artificial poate fi introdus în date de instruire. Mulţi algoritmi fac ipoteze cu privire la natura interacţiunilor dintre caracteristici diferite ale exemplelor de intrare. Experimentele care manipulează sistematic cu aceste interacţiuni au demonstrat că unele dintre aceste ipoteze nu sunt la fel de puternice cum a fost asumat. De exemplu, algoritmul “ naiv'' lui Bayes pentru clasificare presupune că fiecare caracteristică a exemplelor de instruire este generat independent de celălalt, având în vedere eticheta f (x). Această independenţă puternică este rareori observată în practică, dar studii experimentale au demonstrat că naivul lui Bayes este foarte robust la încălcări ale acestei presupuneri [DP96].

Având în vedere rolul esenţial a cercetării empirice în procesul de învăţare a maşinii, s-ar putea presupune că metodele matematice au oferit prea puţin. Cu toate acestea, a existat o interacţiune puternică între cercetări teoretice şi experimentale în procesul de învăţare a maşinii. Algoritmul ADABOOST este un astfel de caz. Algoritmul a fost dezvoltat iniţial bazat pe un model teoretic cunoscut sub numele de model de învăţare slab. Acest model presupune că există algoritmi de învăţare ”slabi'' care pot face ceva mai bine decât ghicitul aleator pentru un anumit set de ipoteze H, indiferent de suport de distribuţie a probabilităţii D, care sunt generatoare de exemple. ADABOOST arată cum de a ”stimula'' aceste algoritmi de învăţare slabi pentru a atinge precizie arbitrară mare. În timp ce succesul experimental lui ADABOOST este necontestată, explicaţia teoretică pentru succesul său în termeni de model de învăţare slab este controversat. Leo Breiman [Bre96] a efectuat o serie de experimente de apelare a explicaţiilor de învăţare slabe şi care furnizează o explicaţie alternativă bazată pe o prelungire a descompunerii bine-cunoscute de eroare de părtinire / variaţie în statistici. Schapire, Freund, Bartlett şi Lee [SFBL97] au contestat explicaţia lui Breiman cu un cont teoretic mai rafinat (şi experimente asociate) bazat pe modelul de marjă maximă dezvoltat pentru prima dată de către Cortes şi Vapnik [CV95]. Breiman [Bre97] recent a răspuns cu un nou set de experimente şi o explicaţie nouă, bazată pe un model nou, pe care el numeşte ”stimularea de margine”. Această interacţiune plină de viaţă între teorie şi experiment este producerea de îmbunătăţiri rapide în înţelegerea noastră a acestor algoritmi şi este creată pentru a ne ajuta să ne concentrăm pe analiza matematică a celor mai importante întrebări fundamentale, precum şi să sugerăm noi algoritmi de importanţă practică.

În concluzie, învăţare de mașină este un domeniu de cercetare empirică în mod inerent. Întrebări fundamentale în acest domeniu necesită un studiu empiric, prin articularea unor ipoteze noi şi cercetarea lor experimentală. Aceste experimente fac uz de seturi de date culese din lumea reala a aplicaţiilor de mașină de învăţare, şi nu există, prin urmare, o relaţie importantă între cercetarea fundamentală şi aplicată. Cu toate acestea, cercetare experimentală de învăţare a maşinii nu se aplică – se încearcă e răspuns la întrebări fundamentale, mai degrabă decât pentru a produce aplicaţii profitabile. Succesul sau eşecul unui efort de aplicații particulare nu oferă o perspectivă asupra întrebărilor fundamentale – succesul sau eşecul, de obicei nu au legătură cu calitatea sau adecvare a algoritmilor de învățare a mașinii. Mai degrabă, aceasta este de obicei determinată de aspectele manageriale şi financiare ale proiectului. În plus, proiectele de cerere sunt proiectate astfel ca să nu răspundă la întrebările fundamentale, ci să le eludeze. Progresele în cercetarea fundamentală necesită o proiectare atentă, execuție, şi interpretare de experimente. Studenții necesită o pregătire în statistici pentru proiectarea experimentului şi analiză, precum şi cunoştinţe solide de modele matematice dezvoltate în teorie de învațare computațională.

Înţelegerea noastră de întrebări fundamentale în învăţarea de maşină avansează rapid (împreună cu calitatea de algoritmi deînvațare care rezultă). Mare parte din acest progres poate fi urmărit în fuzionarea de cercetare experimentală (condusă de crearea şi extinderea depozitului de la Irvine) şi de cercetare teoretică (iniţiată de munca de pionierat lui Vapnik [VC71] şi Valiant [Val84]), împreună cu progresele realizate în hardware-ul computerului care permit experimentarea pe scară largă. Cu toate acestea, un cont de calcul a puterii de oameni pentru învăţarea abilităţilor foarte complexe, cum ar fi viziune şi procesarea limbajului, se află încă la o oarecare distanţă în viitor. Există multe provocări importante pentru cercetarea fundamentală a învăţării de maşinăîn deceniile următoare, şi cercetarea experimentală va fi esenţială pentru îndeplinirea acestor probleme.

Referințe

Bre96

Leo Breiman. Bias, variance, and arcing classifiers. Technical Report 460, Department of Statistics, University of California, Berkeley, CA, 1996.

Bre97

Leo Breiman. Arcing the edge. Technical report, Department of Statistics, University of California, Berkeley, CA, 1997.

CV95

Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine Learning, 20:273-297, 1995.

DHB95

T. G. Dietterich, H. Hild, and G. Bakiri. A comparison of ID3 and backpropagation for English text-to-speech mapping. Machine Learning, 18:51-80, 1995.

DP96

Pedro Domingos and Michael Pazzani. Beyond independence: Conditions for the optimality of the simple Bayesian classifier. In Lorenza Saitta, editor, Proceedings of the Thirteenth International Conference on Machine Learning, pages 105-112, San Francisco, CA, 1996. Morgan Kaufmann.

FS96

Yoav Freund and Robert E. Schapire. Experiments with a new boosting algorithm. In L. Saitta, editor, Proceedings of the Thirteenth International Conference on Machine Learning, pages 148-156, San Francisco, CA, 1996. Morgan Kaufmann.

MM96

Christopher J. Merz and Patrick M. Murphy. UCI repository of machine learning databases. http://www.ics.uci.edu/~mlearn/MLRepository.html, 1996.

Qui93

J. R. Quinlan. C4.5: Programs for Empirical Learning. Morgan Kaufmann, San Francisco, CA, 1993.

Sch94

Cullen Schaffer. A conservation law for generalization performance. In William Cohen and Haym Hirsh, editors, Proceedings of the Eleventh International Conference on Machine Learning, pages 259-265, San Francisco, CA, 1994. Morgan Kaufmann.

SFBL97

Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee. Boosting the margin: A new explanation for the effectiveness of voting methods. In Doug Fisher, editor, Machine Learning: Proceedings of the Fourteenth International Conference. Morgan Kaufmann, 1997.

Val84

L. G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134-1142, November 1984.

VC71

V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probab. and its Applications, 16(2):264-280, 1971.

Wol96

David H. Wolpert. The lack of a priori distinctions between learning algorithms. Neural Computation, 8(7):1341-1390, 1996.


Tom Dietterich, Tue Jun 24 17:00:06 PDT 1997

You can find original post in English here