Contact presa:

Descărcare media

datele

* Termeni de utilizare:

Imaginile pentru descărcare de pe site-ul web al biroului de știri MIT sunt puse la dispoziția entităților necomerciale, a presei și a publicului larg sub o licență Creative Commons Attribution Non-Commercial No Derivatives. Nu puteți modifica imaginile furnizate, altele decât să le decupați la dimensiune. La reproducerea imaginilor trebuie utilizată o linie de credit; dacă una nu este furnizată mai jos, creditați imaginile la „MIT”.

Imaginea anterioară Imaginea următoare

Deoarece oricine a folosit vreodată o foaie de calcul poate atesta, este adesea convenabil să organizați datele în tabele. Dar în epoca datelor mari, acele tabele pot fi enorme, cu milioane sau chiar sute de milioane de rânduri.

O modalitate de a face analiza big-data practică din punct de vedere al calculului este de a reduce dimensiunea tabelelor de date - sau a matricilor, de a folosi termenul matematic - lăsând în afară o grămadă de rânduri. Trucul este că rândurile rămase trebuie să fie într-un anumit sens reprezentative pentru cele care au fost omise, pentru ca calculele efectuate pe ele să producă aproximativ rezultatele potrivite.

La Simpozionul ACM pe teoria calculelor din iunie, cercetătorii MIT vor prezenta un nou algoritm care găsește cea mai mică aproximare posibilă a matricei originale care garantează calcule fiabile. Pentru o clasă de probleme importante în inginerie și învățare automată, aceasta este o îmbunătățire semnificativă față de tehnicile anterioare. Și pentru toate clasele de probleme, algoritmul găsește aproximarea cât mai repede posibil.

Pentru a determina cât de bine reprezintă un rând dat al matricei condensate un rând al matricei originale, algoritmul trebuie să măsoare „distanța” dintre ele. Dar există diferite moduri de a defini „distanța”.

Un mod comun este așa-numita „distanță euclidiană”. În distanța euclidiană, diferențele dintre intrările la pozițiile corespunzătoare din cele două rânduri sunt pătrate și adăugate, iar distanța dintre rânduri este rădăcina pătrată a sumei rezultate. Intuiția este cea a teoremei pitagoreice: rădăcina pătrată a sumei pătratelor lungimilor picioarelor unui triunghi dreptunghic dă lungimea hipotenuzei.

O altă măsură a distanței este mai puțin frecventă, dar deosebit de utilă în rezolvarea învățării automate și a altor probleme de optimizare. Se numește „distanța Manhattan” și este pur și simplu suma diferențelor absolute dintre intrările corespunzătoare din cele două rânduri.

În interiorul normei

De fapt, atât distanța Manhattan, cât și distanța euclidiană sunt exemple de ceea ce statisticiștii numesc „norme”. Distanța Manhattan, sau 1-normă, este prima rădăcină a sumei diferențelor ridicate la prima putere, iar distanța euclidiană, sau 2-normă, este rădăcina pătrată a sumei diferențelor ridicate la a doua putere. Norma 3 este rădăcina cubică a sumei diferențelor ridicate la a treia putere și așa mai departe până la infinit.

În lucrarea lor, cercetătorii MIT - Richard Peng, postdoctorat în matematică aplicată, și Michael Cohen, student absolvent în inginerie electrică și informatică - demonstrează că algoritmul lor este optim pentru condensarea matricelor sub orice normă. Însă, potrivit lui Peng, „cea la care ne-a păsat cu adevărat a fost norma 1”.

În condensarea matricei - în conformitate cu orice normă - primul pas este de a atribui fiecărui rând al matricei originale o „greutate”. Greutatea unui rând reprezintă numărul de alte rânduri cu care este similară și determină probabilitatea ca rândul să fie inclus în matricea condensată. Dacă este, valorile sale vor fi înmulțite în funcție de greutatea sa. Deci, de exemplu, dacă 10 rânduri sunt bune stand-ins unul pentru celălalt, dar nu și pentru alte rânduri ale matricei, fiecare va avea 10% șanse să intre în matricea condensată. Dacă una dintre ele o face, intrările sale vor fi înmulțite cu 10, astfel încât să reflecte contribuția celorlalte nouă rânduri în care se află.

Deși distanța din Manhattan este într-un anumit sens mai simplă decât distanța euclidiană, îngreunează calcularea greutăților rândurilor. Anterior, cel mai bun algoritm pentru condensarea matricelor în conformitate cu norma 1 ar produce o matrice al cărei număr de rânduri era proporțional cu numărul de coloane ale matricei originale ridicate la puterea de 2,5. Totuși, cel mai bun algoritm pentru condensarea matricelor în conformitate cu norma 2 ar produce o matrice al cărei număr de rânduri era proporțional cu numărul de coloane ale matricei originale de ori propriul logaritm.

Asta înseamnă că, dacă matricea avea 100 de coloane, sub norma 1, cea mai bună condensare posibilă, înainte de munca lui Peng și Cohen, era o matrice cu sute de mii de rânduri. În conformitate cu norma 2, era o matrice cu câteva sute de rânduri. Această discrepanță crește odată cu creșterea numărului de coloane.

Recursivitatea îmblânzirii

Algoritmul lui Peng și Cohen condensează matricele sub norma 1, precum și sub norma 2; în conformitate cu norma 2, condensează matricile la fel ca și predecesorii săi. Asta pentru că, pentru 2-normă, folosește pur și simplu cel mai bun algoritm existent. Pentru norma 1, folosește același algoritm, dar îl folosește de cinci sau șase ori.

Contribuția reală a lucrării este de a demonstra matematic că algoritmul cu 2 norme va produce rezultate fiabile în conformitate cu 1-norma. După cum explică Peng, o ecuație pentru calcularea greutăților cu 1 normă este cunoscută de ceva timp. Dar „amuzantul cu această definiție este că este recursiv”, spune el. "Deci, setul corect de greutăți apare atât pe partea stângă, cât și pe partea dreaptă." Adică, greutatea pentru un anumit rând matricial - numiți-l w - este setată egală cu o expresie matematică care include ea însăși w.

„Se știa că există această definiție, dar oamenii din statistici nu știau ce să facă cu ea”, spune Peng. „Se uită la el și se gândesc:„ Cum calculez vreodată ceva cu asta? ””

Ce demonstrează Peng și Cohen este că, dacă începeți prin a seta w pe partea dreaptă a ecuației egală cu 1, atunci evaluați expresia și conectați răspunsul înapoi la dreapta w, apoi faceți același lucru din nou și din nou, veți converge rapid pe o bună aproximare a valorii corecte a lui w.

„Este o matematică extrem de elegantă și oferă un avans semnificativ față de rezultatele anterioare”, spune Richard Karp, profesor de informatică la Universitatea din California la Berkeley și câștigător al Medaliei Naționale a Științei și al Premiului Turing, cel mai înalt. onoare în informatică. „Rezumă problema inițială la una foarte ușor de înțeles. Admir dezvoltarea matematică care a intrat în ea. ”