Sistem de clasificare a învățării - Learning classifier system

Image
Vizualizarea 2D a regulilor LCS învățând să aproximeze o funcție 3D. Fiecare elipsă albastră reprezintă o regulă individuală care acoperă o parte din spațiul soluției. (Adaptat din imagini preluate de la XCSF cu permisiunea lui Martin Butz)

Sistemele de clasificare a învățării , sau LCS , sunt o paradigmă a metodelor de învățare automată bazate pe reguli care combină o componentă de descoperire (de exemplu, un algoritm genetic ) cu o componentă de învățare (efectuând fie învățare supravegheată , învățare de întărire sau învățare nesupravegheată ). Sistemele de clasificare a învățării urmăresc să identifice un set de reguli dependente de context care stochează și aplică în mod colectiv cunoștințele într-o manieră parțială pentru a face predicții (de exemplu , modelarea comportamentului , clasificarea , extragerea datelor , regresia , aproximarea funcției sau strategia jocului ). Această abordare permite separarea spațiilor de soluții complexe în părți mai mici și mai simple.

Conceptele fondatoare din spatele sistemelor de clasificare a învățării au venit din încercările de modelare a sistemelor adaptive complexe , folosind agenți bazați pe reguli pentru a forma un sistem cognitiv artificial (adică inteligența artificială ).

Metodologie

Arhitectura și componentele unui anumit sistem de clasificare a învățării pot fi destul de variabile. Este util să ne gândim la un LCS ca la o mașină formată din mai multe componente care interacționează. Componentele pot fi adăugate sau eliminate, sau componentele existente modificate / schimbate pentru a se potrivi cerințelor unui anumit domeniu de problemă (cum ar fi blocurile de construcție algoritmice) sau pentru a face algoritmul suficient de flexibil pentru a funcționa în multe domenii de probleme diferite. Ca rezultat, paradigma LCS poate fi aplicată flexibil multor domenii cu probleme care necesită învățare automată . Diviziunile majore dintre implementările LCS sunt după cum urmează: (1) arhitectură în stil Michigan vs. arhitectură în stil Pittsburgh, (2) învățare de consolidare vs. învățare supravegheată , (3) învățare incrementală vs. învățare în serie, (4) învățare online vs. . învățare offline , (5) fitness bazat pe forță față de fitness bazat pe precizie și (6) mapare completă a acțiunii vs cea mai bună acțiune. Aceste divizii nu se exclud neapărat reciproc. De exemplu, XCS, cel mai cunoscut și cel mai bine studiat algoritm LCS, este în stil Michigan, a fost conceput pentru învățarea prin întărire, dar poate efectua și învățare supravegheată, aplică învățare incrementală care poate fi online sau offline, aplică condiții de fitness bazate pe precizie și caută pentru a genera o mapare completă a acțiunilor.

Elemente ale unui algoritm LCS generic

Image
O schemă etapizată care ilustrează un ciclu de învățare generic în sistem Michigan clasificator de învățare care efectuează învățare supravegheată.

Ținând cont de faptul că LCS este o paradigmă pentru învățarea automată bazată pe genetică, mai degrabă decât o metodă specifică, următoarele prezintă elementele cheie ale unui algoritm LCS generic, modern (adică post-XCS). Pentru simplitate, permiteți-ne să ne concentrăm pe arhitectura în stil Michigan cu învățare supravegheată. Vedeți ilustrațiile din dreapta prezentând pașii secvențiali implicați în acest tip de LCS generic.

Mediu inconjurator

Mediul este sursa de date despre care învață un LCS. Poate fi un set de date de antrenament finit și offline (caracteristic unei probleme de extragere a datelor , clasificare sau regresie) sau un flux online secvențial de instanțe de antrenament live. Se presupune că fiecare instanță de antrenament include un anumit număr de caracteristici (denumite și atribute sau variabile independente ) și un singur punct final de interes (denumit și clasă , acțiune , fenotip , predicție sau variabilă dependentă ). O parte din învățarea LCS poate implica selectarea caracteristicilor , prin urmare nu toate caracteristicile din datele de instruire trebuie să fie informative. Setul de valori ale caracteristicilor unei instanțe este denumit în mod obișnuit stat . Pentru simplitate, să presupunem un exemplu de domeniu problemă cu caracteristici booleene / binare și o clasă booleană / binară . Pentru sistemele în stil Michigan, o instanță din mediu este instruită pe fiecare ciclu de învățare (adică învățare incrementală). Sistemele în stil Pittsburgh efectuează învățarea în serie, unde seturile de reguli sunt evaluate fiecare iterație pe o mare parte sau pe toate datele de instruire.

Regula / clasificatorul / populația

O regulă este o relație dependentă de context între valorile stării și o anumită predicție. Regulile iau de obicei forma unei expresii {IF: THEN}, (de exemplu, { IF 'condition' THEN 'action'}, sau ca un exemplu mai specific, {IF 'roșu' ȘI 'octagon' THEN 'stop-sign'} ). Un concept critic atât în ​​LCS, cât și în învățarea automată bazată pe reguli, este acela că o regulă individuală nu este în sine un model, deoarece regula este aplicabilă numai atunci când condiția sa este îndeplinită. Gândiți-vă la o regulă ca la un „model local” al spațiului soluției.

Regulile pot fi reprezentate în mai multe moduri diferite pentru a gestiona diferite tipuri de date (de exemplu, binare, discrete, ordinale, continue). Datele binare date LCS aplică în mod tradițional o reprezentare a regulilor ternare (adică regulile pot include fie 0, 1, fie „#” pentru fiecare caracteristică din date). Simbolul „nu-mi pasă” (adică „#”) servește ca un wild card în condițiile unei reguli care permite regulilor, iar sistemul în ansamblu să generalizeze relațiile dintre caracteristici și obiectivul final țintă pentru a fi prezis. Luați în considerare următoarea regulă (# 1 ### 0 ~ 1) (adică condiție ~ acțiune). Această regulă poate fi interpretată ca: DACĂ a doua caracteristică = 1 ȘI a șasea caracteristică = 0 APOI predicția clasei = 1. Am spune că a doua și a șasea caracteristică au fost specificate în această regulă, în timp ce celelalte au fost generalizate. Această regulă și predicția corespunzătoare se aplică numai unei instanțe atunci când condiția regulii este îndeplinită de instanță. Aceasta este denumită mai frecvent ca potrivire. În LCS în stil Michigan, fiecare regulă are propria sa formă, precum și o serie de alți parametri de regulă asociați cu aceasta care pot descrie numărul de copii ale acelei reguli care există (adică numerozitatea ), vârsta regulii, acuratețea sau precizia predicțiilor recompensei și alte statistici descriptive sau experiențiale. O regulă împreună cu parametrii săi este adesea denumită clasificator . În sistemele în stil Michigan, clasificatorii sunt cuprinși într-o populație [P] care are un număr maxim definit de utilizator de clasificatori. Spre deosebire de majoritatea algoritmilor de căutare stocastică (de exemplu, algoritmi evolutivi ), populațiile LCS încep goale (adică nu este nevoie să inițializați aleatoriu o populație de reguli). În schimb, clasificatorii vor fi introduși inițial populației cu un mecanism de acoperire.

În orice LCS, modelul instruit este un set de reguli / clasificatori, mai degrabă decât orice regulă / clasificator unic. În LCS în stil Michigan, întreaga populație clasificatoare instruită (și opțional compactată) formează modelul de predicție.

Potrivire

Unul dintre cele mai critice și adesea consumatoare de timp elemente ale unui LCS este procesul de potrivire. Primul pas într-un ciclu de învățare LCS ia o singură instanță de formare din mediul înconjurător și o trece la [P] unde are loc potrivirea. La pasul doi, fiecare regulă din [P] este acum comparată cu instanța de antrenament pentru a vedea care reguli se potrivesc (adică sunt relevante contextual pentru instanța actuală). La pasul trei, orice regulă de potrivire este mutată într-un set de potrivire [M]. O regulă se potrivește cu o instanță de antrenament dacă toate valorile caracteristicilor specificate în condiția regulii sunt echivalente cu valoarea caracteristicii corespunzătoare din instanța de antrenament. De exemplu, presupunând că instanța de antrenament este (001001 ~ 0), aceste reguli ar corespunde: (### 0 ## ~ 0), (00 ### 1 ~ 0), (# 01001 ~ 1), dar aceste reguli nu ar fi (1 ##### ~ 0), (000 ## 1 ~ 0), (# 0 # 1 # 0 ~ 1). Observați că la potrivire, punctul final / acțiunea specificată de regulă nu este luată în considerare. Ca rezultat, setul de potrivire poate conține clasificatori care propun acțiuni conflictuale. În al patrulea pas, întrucât efectuăm învățarea supravegheată, [M] este împărțit într-un set corect [C] și un set incorect [I]. O regulă de potrivire intră în setul corect dacă propune acțiunea corectă (pe baza acțiunii cunoscute a instanței de antrenament), altfel intră în [I]. În învățarea de consolidare LCS, aici ar fi format un set de acțiuni [A], deoarece acțiunea corectă nu este cunoscută.

Acoperire

În acest moment al ciclului de învățare, dacă niciun clasificator nu a făcut nici [M], nici [C] (așa cum ar fi cazul când populația începe goală), se aplică mecanismul de acoperire (al cincilea pas). Acoperirea este o formă de inițializare inteligentă a populației online . Acoperirea în mod aleatoriu generează o regulă care se potrivește instanței actuale de antrenament (și în cazul învățării supravegheate, acea regulă este generată și cu acțiunea corectă. Presupunând că instanța de antrenament este (001001 ~ 0), acoperirea poate genera oricare dintre următoarele reguli: (# 0 # 0 ## ~ 0), (001001 ~ 0), (# 010 ## ~ 0). Acoperirea nu numai că asigură faptul că fiecare ciclu de învățare există cel puțin o regulă de potrivire corectă în [C], dar că orice regulă inițiată în populație se va potrivi cu cel puțin o instanță de antrenament. Acest lucru împiedică LCS să exploreze spațiul de căutare a regulilor care nu se potrivesc cu nici o instanță de antrenament.

Actualizări de parametri / atribuire de credit / învățare

În al șaselea pas, parametrii regulilor oricărei reguli din [M] sunt actualizați pentru a reflecta noua experiență câștigată din instanța de instruire actuală. În funcție de algoritmul LCS, la acest pas pot avea loc o serie de actualizări. Pentru învățarea supravegheată, putem actualiza pur și simplu acuratețea / eroarea unei reguli. Acuratețea / eroarea regulii este diferită de acuratețea / eroarea modelului, deoarece nu este calculată pe toate datele de antrenament, ci doar pe toate cazurile pe care le-a corespuns. Precizia regulii este calculată prin împărțirea numărului de ori în care regula a fost într-un set corect [C] la numărul de ori a fost într-un set de potrivire [M]. Precizia regulilor poate fi considerată ca o „precizie locală”. Ajustarea regulilor este, de asemenea, actualizată aici și este calculată în mod obișnuit în funcție de precizia regulilor. Conceptul de fitness este preluat direct din algoritmii genetici clasici . Rețineți că există multe variații cu privire la modul în care LCS actualizează parametrii pentru a efectua atribuirea și învățarea creditului.

Subsumare

În al șaptelea pas, se aplică de obicei un mecanism de subsumare . Subsumarea este un mecanism explicit de generalizare care combină clasificatorii care acoperă părți redundante ale spațiului problematic. Clasificatorul subsumant absoarbe efectiv clasificatorul subsumat (și are numărul său crescut). Acest lucru se poate întâmpla numai atunci când clasificatorul subsumant este mai general, la fel de precis și acoperă tot spațiul problematic al clasificatorului pe care îl subsumează.

Descoperirea regulilor / algoritmul genetic

În etapa a opta, LCS adoptă un algoritm genetic extrem de elitist (GA) care va selecta doi clasificatori părinți pe baza fitnessului (supraviețuirea celui mai potrivit). Părinții sunt selectați din [C] folosind de obicei selecția turneului . Unele sisteme au aplicat selecția roții de ruletă sau selecția deterministă și au selectat reguli părinte diferite fie din [P] - selecția panmictică, fie din [M]). Operatorii de încrucișare și mutație sunt acum aplicați pentru a genera două noi reguli de descendenți. În acest moment, atât regulile părinte, cât și descendenții sunt returnate la [P]. Algoritmul genetic LCS este foarte elitist, deoarece fiecare iterație de învățare, marea majoritate a populației este păstrată. Descoperirea regulilor poate fi efectuată alternativ prin altă metodă, cum ar fi o estimare a algoritmului de distribuție , dar o GA este de departe cea mai comună abordare. Algoritmii evolutivi precum GA utilizează o căutare stocastică, ceea ce face din LCS un algoritm stocastic. LCS caută să exploreze inteligent spațiul de căutare, dar nu efectuează o căutare exhaustivă a combinațiilor de reguli și nu este garantat că va converge către o soluție optimă.

Ștergere

Ultimul pas într-un ciclu de învățare LCS generic este menținerea dimensiunii maxime a populației. Mecanismul de ștergere va selecta clasificatorii pentru ștergere (de obicei folosind selecția roții de ruletă). Probabilitatea ca un clasificator să fie selectat pentru ștergere este invers proporțională cu capacitatea sa. Când este selectat un clasificator pentru ștergere, parametrul său de numerozitate este redus cu unul. Când numerozitatea unui clasificator este redusă la zero, aceasta este eliminată în totalitate din populație.

Instruire

LCS va parcurge în mod repetat acești pași pentru un anumit număr de iterații de instruire definite de utilizator sau până când sunt îndeplinite anumite criterii de terminare definite de utilizator. Pentru învățarea online, LCS va obține o instanță de instruire complet nouă, fiecare iterație din mediu. Pentru învățarea offline, LCS va itera printr-un set de date de antrenament finit. Odată ce a ajuns la ultima instanță din setul de date, va reveni la prima instanță și va reveni prin setul de date.

Compactarea regulilor

Odată ce instruirea este completă, populația de reguli va conține în mod inevitabil niște reguli sărace, redundante și fără experiență. Este comun să se aplice o regulă de compactare sau euristică de condensare ca etapă de post-procesare. Această populație de regulă compactată rezultată este gata să fie aplicată ca model de predicție (de exemplu, faceți predicții pe instanțe de testare) și / sau să fie interpretată pentru descoperirea cunoștințelor .

Predicție

Indiferent dacă s-a aplicat sau nu compactarea regulilor, rezultatul unui algoritm LCS este o populație de clasificatori care poate fi aplicată pentru a face predicții în instanțe nevăzute anterior. Mecanismul de predicție nu face parte din ciclul de învățare LCS supravegheat în sine, însă ar juca un rol important într-un ciclu de învățare LCS de învățare de consolidare. Deocamdată luăm în considerare modul în care mecanismul de predicție poate fi aplicat pentru a face predicții pentru a testa datele. Când se fac predicții, componentele de învățare LCS sunt dezactivate, astfel încât populația să nu continue să învețe din datele de testare primite. O instanță de testare este transmisă la [P] unde se formează un set de potrivire [M] ca de obicei. În acest moment, setul de potrivire este trecut diferit la o matrice de predicție. Regulile din setul de meci pot prezice diferite acțiuni, prin urmare se aplică o schemă de vot. Într-o schemă simplă de vot, acțiunea cu cele mai puternice „voturi” de susținere din regulile de potrivire câștigă și devine predicția selectată. Toate regulile nu primesc un vot egal. Mai degrabă, forța votului pentru o singură regulă este de obicei proporțională cu numerozitatea și capacitatea sa. Această schemă de vot și natura modului în care cunoștințele magazinului LCS sugerează că algoritmii LCS sunt implicit cursanți de ansamblu .

Interpretare

Regulile LCS individuale sunt în mod obișnuit expresie citită de om IF: THEN. Regulile care constituie modelul de predicție LCS pot fi clasificate după diferiți parametri de regulă și inspectate manual. Au fost, de asemenea, propuse strategii globale pentru a ghida descoperirea cunoștințelor folosind statistici și grafice. În ceea ce privește alte abordări avansate de învățare automată, cum ar fi rețelele neuronale artificiale , pădurile aleatorii sau programarea genetică , sistemele de clasificare a învățării sunt deosebit de potrivite pentru problemele care necesită soluții interpretabile.

Istorie

Primii ani

John Henry Holland a fost cel mai bine cunoscut pentru munca sa de popularizare a algoritmilor genetici (GA), prin cartea sa inovatoare „Adaptare în sisteme naturale și artificiale” în 1975 și formalizarea teoremei schemei lui Holland . În 1976, Holland a conceptualizat o extensie a conceptului GA la ceea ce el a numit „sistem cognitiv” și a furnizat prima descriere detaliată a ceea ce va deveni cunoscut ca primul sistem de clasificare a învățării în lucrarea „Sisteme cognitive bazate pe algoritmi adaptivi”. Acest prim sistem, denumit Cognitive System One (CS-1) a fost conceput ca un instrument de modelare, conceput pentru a modela un sistem real (adică mediu ) cu dinamici subiacente necunoscute utilizând o populație de reguli lizibile de om. Scopul a fost ca un set de reguli să efectueze învățarea online a mașinilor pentru a se adapta la mediu pe baza recompenselor / recompenselor rare (adică învățării prin întărire) și a aplica aceste reguli pentru a genera un comportament care să se potrivească cu sistemul real. Această implementare timpurie și ambițioasă a fost considerată ulterior ca fiind prea complexă, oferind rezultate inconsistente.

Începând din 1980, Kenneth de Jong și elevul său Stephen Smith au adoptat o abordare diferită a învățării automate bazate pe reguli cu (LS-1) , unde învățarea a fost privită mai degrabă ca un proces de optimizare offline decât ca un proces de adaptare online. Această nouă abordare a fost mai asemănătoare cu un algoritm genetic standard, dar a dezvoltat seturi independente de reguli. De atunci metodele LCS inspirate de cadrul de învățare online introdus de Olanda la Universitatea din Michigan au fost denumite LCS în stil Michigan , iar cele inspirate de Smith și De Jong de la Universitatea din Pittsburgh au fost denumite stilul Pittsburgh LCS . În 1986, Olanda a dezvoltat ceea ce ar fi considerat LCS standard în stil Michigan pentru următorul deceniu.

Alte concepte importante care au apărut în primele zile ale cercetării LCS includeau (1) formalizarea unui algoritm de brigadă de bucket (BBA) pentru atribuirea / învățarea creditelor, (2) selectarea regulilor părinților dintr-o „nișă de mediu” comună (adică potrivirea set [M]), mai degrabă decât din întreaga populație [P], (3) acoperind , introdus mai întâi ca operator de creare , (4) formalizarea unui set de acțiuni [A], (5) o arhitectură simplificată de algoritm, (6 ) fitness bazat pe forță , (7) luarea în considerare a problemelor de învățare cu un singur pas sau supravegheate și introducerea setului corect [C], (8) fitness bazat pe precizie (9) combinația logicii fuzzy cu LCS (care mai târziu a generat o linie de algoritmi LCS fuzzy ), (10) încurajând lanțuri lungi de acțiune și ierarhii implicite pentru îmbunătățirea performanței la problemele cu mai mulți pași, (11) examinând învățarea latentă (care a inspirat ulterior o nouă ramură a sistemelor de clasificare anticipativă (ACS)), și (12) introducerea primului atribuitor de credit de tip Q-learning tehnica ent. Deși nu toate aceste concepte sunt aplicate în algoritmii LCS moderni, fiecare a reprezentat repere în dezvoltarea paradigmei LCS.

Revoluția

Interesul pentru învățarea sistemelor de clasificare a fost revigorat la mijlocul anilor 1990, în mare parte datorită a două evenimente; dezvoltarea algoritmului Q-Learning pentru învățarea prin întărire și introducerea unor arhitecturi LCS în stil Michigan simplificate semnificativ de către Stewart Wilson. Sistemul de clasificare a nivelului Zeroth al lui Wilson (ZCS) s-a axat pe creșterea înțelegerii algoritmice pe baza implementării LCS standard Hollands. Acest lucru a fost realizat, parțial, prin eliminarea licitării de reguli și a listei de mesaje interne, esențiale pentru atribuirea de credit BBA inițială, și înlocuirea acesteia cu o strategie hibridă BBA / Q-Learning . ZCS a demonstrat că o arhitectură LCS mult mai simplă ar putea funcționa la fel ca implementările originale și mai complexe. Cu toate acestea, ZCS suferea încă de dezavantaje ale performanței, inclusiv proliferarea clasificatorilor excesivi.

În 1995, Wilson a publicat lucrarea sa de referință, „Clasificatorul de fitness bazat pe precizie”, în care a introdus sistemul de clasificare XCS . XCS a luat arhitectura simplificată a ZCS și a adăugat o condiție fizică bazată pe precizie, o nișă GA (care acționează în setul de acțiuni [A]), un mecanism explicit de generalizare numit subsum și o adaptare a atribuirii creditului Q-Learning . XCS a fost popularizat prin capacitatea sa de a atinge performanțe optime în timp ce a evoluat clasificatori exacți și maxim generali, precum și prin flexibilitatea sa impresionantă a problemelor (capabilă să efectueze atât învățarea de consolidare, cât și învățarea supravegheată ). XCS a devenit ulterior cel mai cunoscut și mai studiat algoritm LCS și a definit o nouă familie de LCS bazată pe precizie . ZCS a devenit alternativ sinonim cu LCS bazat pe rezistență . XCS este, de asemenea, important, deoarece a eliminat cu succes decalajul dintre LCS și domeniul învățării prin întărire . După succesul XCS, LCS a fost ulterior descris ca sisteme de învățare de întărire dotate cu o capacitate de generalizare. Învățarea prin întărire caută de obicei să învețe o funcție de valoare care să traseze o reprezentare completă a spațiului de stare / acțiune. În mod similar, designul XCS îl determină să formeze o reprezentare completă și precisă a spațiului problematic (adică o hartă completă ), mai degrabă decât să se concentreze pe nișe de plată ridicate în mediu (așa cum a fost cazul LCS bazat pe forță). Conceptual, hărțile complete nu captează doar ceea ce ar trebui să faci sau ce este corect, ci și ce nu ar trebui să faci sau ce este incorect. În mod diferit, majoritatea LCS-urilor bazate pe forță sau LCS-urilor de învățare exclusiv supravegheate caută un set de reguli de generalizări eficiente sub forma unei hărți de acțiune mai bune (sau a unei hărți parțiale ). Comparațiile dintre puterea vs. fitnessul bazat pe precizie și hărțile complete față de cele mai bune acțiuni au fost examinate mai detaliat.

În urma XCS

XCS a inspirat dezvoltarea unei noi generații de algoritmi și aplicații LCS. În 1995, Congdon a fost primul care a aplicat LCS la investigațiile epidemiologice reale ale bolii, urmat îndeaproape de Holmes, care a dezvoltat BOOLE ++ , EpiCS și ulterior EpiXCS pentru clasificarea epidemiologică . Aceste lucrări timpurii au inspirat interesul ulterior în aplicarea algoritmilor LCS la sarcini complexe și pe scară largă de extragere a datelor , reprezentate de aplicațiile bioinformatice . În 1998, Stolzmann a introdus sisteme de clasificare anticipativă (ACS) care includeau reguli sub forma „condiție-acțiune-efect”, mai degrabă decât reprezentarea clasică „acțiune-condiție”. ACS a fost conceput pentru a prezice consecințele perceptive ale unei acțiuni în toate situațiile posibile dintr-un mediu. Cu alte cuvinte, sistemul dezvoltă un model care specifică nu numai ce trebuie făcut într-o anumită situație, ci oferă și informații despre ceea ce se va întâmpla după ce o acțiune specifică va fi executată. Această familie de algoritmi LCS este cea mai potrivită pentru probleme în mai mulți pași, planificarea, accelerarea învățării sau dezambiguizarea aliasării perceptive (adică în cazul în care aceeași observație este obținută în stări distincte, dar necesită acțiuni diferite). Butz a urmărit ulterior această anticipativă familie de LCS dezvoltând o serie de îmbunătățiri ale metodei originale. În 2002, Wilson a introdus XCSF , adăugând o acțiune calculată pentru a efectua aproximarea funcției. În 2003, Bernado-Mansilla a introdus un sistem de clasificare supravegheat (UCS) , care a specializat algoritmul XCS în sarcina învățării supravegheate , a problemelor cu un singur pas și a forma un set de acțiune optim. UCS a eliminat strategia de învățare a consolidării în favoarea unei reguli de fitness simple, bazate pe acuratețe, precum și a fazelor de învățare explorare / exploatare, caracteristice multor cursanți de consolidare. Bull a introdus un simplu LCS bazat pe precizie (YCS) și un simplu sistem bazat pe rezistență LCS Minimal Classifier System (MCS) pentru a dezvolta o mai bună înțelegere teoretică a cadrului LCS. Bacardit a introdus GAssist și BioHEL , LCS -uri în stil Pittsburgh, proiectate pentru extragerea datelor și scalabilitate la seturi de date mari în aplicații de bioinformatică . În 2008, Drugowitsch a publicat cartea intitulată „Proiectarea și analiza sistemelor de clasificare a învățării”, inclusiv o examinare teoretică a algoritmilor LCS. Butz a introdus prima vizualizare a învățării online în cadrul unei GUI pentru XCSF (vezi imaginea din partea de sus a acestei pagini). Urbanowicz a extins cadrul UCS și a introdus ExSTraCS, conceput în mod explicit pentru învățarea supravegheată în domenii cu probleme zgomotoase (de exemplu, epidemiologie și bioinformatică). ExSTraCS a integrat (1) cunoștințe expert pentru a conduce acoperirea și algoritmul genetic către caracteristici importante ale datelor, (2) o formă de memorie pe termen lung denumită urmărirea atributelor, permițând o învățare mai eficientă și caracterizarea tiparelor de date eterogene și (3) o reprezentare de regulă flexibilă similară cu reprezentarea mixtă a listei de atribute discrete-continue a lui Bacardit. Atât Bacardit, cât și Urbanowicz au explorat strategii statistice și de vizualizare pentru a interpreta regulile LCS și a efectua descoperirea cunoștințelor pentru extragerea datelor. Browne și Iqbal au explorat conceptul de reutilizare a blocurilor de construcție sub formă de fragmente de cod și au fost primii care au rezolvat problema de referință a multiplexorului de 135 de biți învățând mai întâi blocuri de construcție utile din probleme mai simple de multiplexor. ExSTraCS 2.0 a fost introdus ulterior pentru a îmbunătăți scalabilitatea LCS în stil Michigan, rezolvând cu succes problema de referință a multiplexorului de 135 de biți pentru prima dată direct. Problema multiplexorului pe n-biți este extrem de epistatică și eterogenă , ceea ce îl face o sarcină foarte dificilă de învățare automată .

Variante

Sistemul de clasificare a învățării în stil Michigan

LCS-urile în stil Michigan sunt caracterizate de o populație de reguli în care algoritmul genetic funcționează la nivelul regulilor individuale și soluția este reprezentată de întreaga populație de reguli. Sistemele în stil Michigan învață, de asemenea, în mod incremental, ceea ce le permite să efectueze atât învățarea de consolidare, cât și învățarea supravegheată, precum și învățarea online și offline. Sistemele în stil Michigan au avantajul de a fi aplicabile unui număr mai mare de domenii cu probleme și beneficiile unice ale învățării incrementale.

Sistem de clasificare a învățării în stil Pittsburgh

LCS-urile în stil Pittsburgh sunt caracterizate de o populație de seturi de reguli cu lungime variabilă, unde fiecare set de reguli este o soluție potențială. Algoritmul genetic funcționează de obicei la nivelul unui întreg set de reguli. Sistemele în stil Pittsburgh pot, de asemenea, să evolueze în mod unic liste ordonate de reguli, precum și să utilizeze o regulă implicită. Aceste sisteme au avantajul natural de a identifica seturi de reguli mai mici, făcând aceste sisteme mai interpretabile în ceea ce privește inspecția manuală a regulilor.

Sisteme hibride

Au fost, de asemenea, propuse sisteme care urmăresc să combine punctele forte ale ambelor sisteme.

Avantaje

  • Adaptive: Se pot adapta la un mediu în schimbare în cazul învățării online.
  • Model gratuit: fac presupuneri limitate despre mediu sau modelele de asociere din cadrul datelor.
    • Ele pot modela modele subiacente complexe, epistatice, eterogene sau distribuite fără a se baza pe cunoștințe anterioare.
    • Nu fac presupuneri cu privire la numărul de caracteristici predictive față de non-predictive din date.
  • Ensemble Learner: Niciun model unic nu este aplicat unei instanțe date care oferă universal o predicție. În schimb, un set de reguli relevante și adesea conflictuale contribuie la un „vot” care poate fi interpretat ca o predicție neclară.
  • Studenți stochastici: învățarea nedeterministă este avantajoasă în problemele de scară largă sau complexitate ridicată, unde învățarea deterministă sau exhaustivă devine intratabilă.
  • Implicit multi-obiectiv: regulile evoluează către precizie cu presiuni implicite și explicite care încurajează generalitatea / simplitatea maximă. Această presiune de generalizare implicită este unică LCS. Efectiv, reguli mai generale, vor apărea mai des în seturile de meciuri. La rândul lor, aceștia au o ocazie mai frecventă de a fi selectați ca părinți și de a transmite regulile lor mai generale (genomii) către descendenți.
  • Interpretabile: În interesul exploatării datelor și al descoperirii cunoștințelor, regulile LCS individuale sunt logice și pot fi făcute ca instrucțiuni interpretabile umane IF: THEN. Au fost introduse, de asemenea, strategii eficiente pentru a permite descoperirea cunoștințelor globale, identificând trăsături semnificative și modele de asociere din populația de regulă în ansamblu.
  • Aplicatie flexibila
    • Probleme cu un singur pas sau cu mai mulți pași
    • Învățare supravegheată, consolidată sau fără supraveghere
    • Clasa binară și clasificarea multi-clasă
    • Regresie
    • Caracteristici discrete sau continue (sau un amestec de ambele tipuri)
    • Domenii cu probleme curate sau zgomotoase
    • Seturi de date echilibrate sau dezechilibrate.
    • Acceptă datele lipsă (adică valorile caracteristicilor lipsă în instanțele de antrenament)

Dezavantaje

  • Disponibilitate limitată a software-ului: există un număr limitat de implementări LCS open source, accesibile și chiar mai puține care sunt concepute pentru a fi ușor de utilizat sau accesibile pentru practicienii de învățare automată.
  • Interpretare: În timp ce algoritmii LCS sunt cu siguranță mai interpretabili decât unii învățători avansați de mașini, utilizatorii trebuie să interpreteze un set de reguli (uneori seturi mari de reguli pentru a înțelege modelul LCS). Metodele de compactare a regulilor și strategiile de interpretare rămân o zonă de cercetare activă.
  • Dovezi de teorie / convergență: există un corp relativ mic de lucrări teoretice în spatele algoritmilor LCS. Acest lucru se datorează probabil complexității lor algoritmice relative (aplicarea unui număr de componente care interacționează), precum și naturii lor stocastice.
  • Overfitting: Ca orice elev care învață mașina, LCS poate suferi de overfitting în ciuda presiunilor de generalizare implicite și explicite.
  • Parametrii de rulare: LCS-urile au adesea mulți parametri de rulare de luat în considerare / optimizare. De obicei, majoritatea parametrilor pot fi lăsați la dispoziția comunității implicit, cu excepția a doi parametri critici: dimensiunea maximă a populației de reguli și numărul maxim de iterații de învățare. Optimizarea acestor parametri este foarte probabil dependentă de probleme.
  • Notorietate: în ciuda vârstei lor, algoritmii LCS nu sunt încă cunoscuți pe scară largă nici măcar în comunitățile de învățare automată. Ca urmare, algoritmii LCS sunt rareori luați în considerare în comparație cu alte abordări de învățare automată stabilite. Acest lucru se datorează probabil următorilor factori: (1) LCS este o abordare algoritmică relativ complicată, (2) LCS, modelarea bazată pe reguli este o paradigmă diferită de modelare decât aproape toate celelalte abordări de învățare automată. (3) Implementările de software LCS nu sunt la fel de obișnuite.
  • Scump din punct de vedere al calculației: deși este cu siguranță mai fezabil decât unele abordări exhaustive, algoritmii LCS pot fi scump din punct de vedere al calculației. Pentru probleme simple, liniare de învățare, nu este necesar să se aplice un LCS. Algoritmii LCS se potrivesc cel mai bine spațiilor problematice complexe sau spațiilor problematice în care există puține cunoștințe anterioare.

Domenii cu probleme

  • Control adaptiv
  • Exploatarea datelor
  • Proiectare inginerie
  • Selectarea caracteristicii
  • Aproximarea funcției
  • Joc-joc
  • Clasificarea imaginilor
  • Gestionarea cunoștințelor
  • Diagnostic medical
  • Modelare
  • Navigare
  • Optimizare
  • Predicție
  • Interogare
  • Robotica
  • Rutare
  • Inducerea regulii
  • Programare
  • Strategie

Terminologie

Numele, „Sistemul de clasificare a învățării (LCS)”, este un pic înșelător, deoarece există mulți algoritmi de învățare automată care „învață să clasifice” (de exemplu , arbori de decizie , rețele neuronale artificiale ), dar nu sunt LCS. Termenul „învățare automată bazată pe reguli ( RBML )” este util, deoarece surprinde mai clar componenta esențială „bazată pe reguli” a acestor sisteme, dar se generalizează și la metode care nu sunt considerate LCS (de exemplu , învățarea regulilor de asociere) , sau sisteme imune artificiale ). Termeni mai generali precum „învățarea automată bazată pe genetică” și chiar „algoritm genetic” au fost de asemenea aplicați pentru a se referi la ceea ce ar fi definit mai caracteristic ca un sistem de clasificare a învățării. Datorită similitudinii lor cu algoritmii genetici , sistemele de clasificare a învățării în stil Pittsburgh sunt uneori denumite generic „algoritmi genetici”. Dincolo de aceasta, unii algoritmi LCS, sau metode strâns legate, au fost denumiți „sisteme cognitive”, „agenți adaptivi”, „ sisteme de producție ” sau generic ca „sistem clasificator”. Această variație a terminologiei contribuie la o anumită confuzie în domeniu.

Până în anii 2000, aproape toate metodele sistemului de clasificare a învățării au fost dezvoltate având în vedere problemele de învățare de consolidare. Ca rezultat, termenul „sistem de clasificare a învățării” a fost definit în mod obișnuit ca fiind combinația învățării de consolidare „încercare-eroare” cu căutarea globală a unui algoritm genetic. Interesul pentru aplicațiile de învățare supravegheate și chiar învățarea nesupravegheată au extins de atunci utilizarea și definiția acestui termen.

Vezi si

Referințe

linkuri externe

Tutorial video

Pagini web