Santykių modeliavimas siekiant efektyviai išspręsti sudėtingas problemas | MIT naujienos

Vokiečių filosofas Fredrichas Nietzsche kartą pasakė, kad „nematomos gijos yra stipriausi ryšiai“. Galima manyti, kad „nematomos gijos“ yra susijusių objektų, pvz., namų, esančių pristatymo vairuotojo maršrute, susiejimas arba sudėtingesni subjektai, pvz., operacijos finansiniame tinkle arba naudotojai socialiniame tinkle.

Kompiuterių mokslininkas Julianas Shunas tiria tokio tipo daugialypius, bet dažnai nematomus ryšius naudodamas grafikus, kur objektai vaizduojami kaip taškai arba viršūnės, o santykiai tarp jų modeliuojami linijų atkarpomis arba briaunomis.

Shun, naujai eiti pareigas Elektros inžinerijos ir informatikos katedros docentas, kuria grafikų algoritmus, kurie galėtų būti naudojami norint rasti trumpiausią kelią tarp namų pristatymo vairuotojo kelyje arba aptikti apgaulingus sandorius, kuriuos finansų tinkle atliko kenkėjiški veikėjai.

Tačiau didėjant duomenų kiekiui, tokie tinklai išaugo iki milijardų ar net trilijonų objektų ir jungčių. Siekdamas rasti efektyvių sprendimų, Shun kuria didelio našumo algoritmus, kurie pasitelkia lygiagretųjį skaičiavimą, kad būtų galima greitai išanalizuoti net didžiausius grafikus. Kadangi lygiagretus programavimas yra žinomas sudėtingas, jis taip pat kuria patogias programavimo sistemas, kurios palengvina kitiems veiksmingų savo grafikų algoritmų rašymą.

„Jei ko nors ieškote paieškos sistemoje ar socialiniame tinkle, rezultatus norite gauti labai greitai. Jei bandote nustatyti nesąžiningas finansines operacijas banke, norite tai padaryti realiuoju laiku, kad sumažintumėte žalą. Lygiagretūs algoritmai gali paspartinti darbą naudojant daugiau skaičiavimo išteklių“, – aiškina Shun, kuris taip pat yra pagrindinis Kompiuterių mokslo ir dirbtinio intelekto laboratorijos (CSAIL) tyrėjas.

Tokie algoritmai dažnai naudojami internetinėse rekomendacijų sistemose. Ieškokite produkto el. prekybos svetainėje ir tikėtina, kad greitai pamatysite susijusių prekių, kurias taip pat galite įtraukti į krepšelį, sąrašą. Šis sąrašas sugeneruojamas naudojant grafikų algoritmus, kurie išnaudoja lygiagretumą, kad būtų galima greitai rasti susijusius elementus dideliame vartotojų tinkle ir turimus produktus.

Universiteto jungtys

Būdamas paauglys, Shunas vienintelė patirtis su kompiuteriais buvo vidurinės mokyklos klasė kuriant svetaines. Labiau domėjosi matematika ir gamtos mokslais, o ne technologijomis, jis ketino baigti vieną iš šių dalykų, kai įstojo į Kalifornijos universiteto Berklyje bakalauro studijas.

Tačiau pirmaisiais metais draugas jam rekomendavo įvesti į informatikos klasę. Nors jis nežinojo, ko tikėtis, jis nusprendė užsiregistruoti.

„Įsimylėjau programavimą ir algoritmų projektavimą. Perėjau į informatiką ir niekada atgal nežiūrėjau“, – prisimena jis.

Šis pradinis informatikos kursas buvo savarankiškas, todėl Shun daugumą medžiagos išmokė pats. Jam patiko loginiai algoritmų kūrimo aspektai ir trumpa informatikos problemų grįžtamojo ryšio kilpa. Shun galėjo įvesti savo sprendimus į kompiuterį ir iškart pamatyti, ar jis teisus, ar ne. Ir klaidingų sprendimų klaidos nukreiptų jį į teisingą atsakymą.

„Visada maniau, kad buvo smagu kurti daiktus, o programuodami kuriate sprendimus, kurie daro kažką naudingo. Tai mane sužavėjo“, – priduria jis.

Baigęs studijas, Shun kurį laiką praleido pramonėje, tačiau netrukus suprato, kad nori siekti akademinės karjeros. Universitete jis žinojo, kad turės laisvę studijuoti jį dominančias problemas.

Patekimas į grafikus

Jis įstojo kaip magistrantūros studentas Carnegie Mellon universitete, kur daugiausia dėmesio skyrė taikomiesiems algoritmams ir lygiagrečiam skaičiavimui.

Būdamas bakalauro studijas, Shun lankė teorinių algoritmų pamokas ir praktinio programavimo kursus, tačiau abu pasauliai nesusiejo. Jis norėjo atlikti tyrimus, kuriuose būtų sujungta teorija ir taikymas. Lygiagretūs algoritmai puikiai tiko.

„Paralelinio skaičiavimo metu turite rūpintis praktiniais pritaikymais. Lygiagretaus skaičiavimo tikslas – pagreitinti veiklą realiame gyvenime, taigi, jei jūsų algoritmai praktiškai nėra greiti, vadinasi, jie nėra tokie naudingi“, – sako jis.

Carnegie Mellon jis buvo supažindintas su grafų duomenų rinkiniais, kur tinklo objektai modeliuojami kaip briaunomis sujungtos viršūnės. Jis pajuto, kad jį traukia daugybė tokio tipo duomenų rinkinių pritaikymo būdų ir sudėtinga problema, susijusi su veiksmingų algoritmų kūrimu, kaip juos valdyti.

Baigęs doktorantūros stažuotę Berklyje, Shun ieškojo fakulteto pareigų ir nusprendė prisijungti prie MIT. Jis bendradarbiavo su keliais MIT fakulteto nariais lygiagrečiųjų skaičiavimų tyrimų srityje ir džiaugėsi galėdamas prisijungti prie instituto, turinčio tokią didelę patirtį.

Viename iš pirmųjų projektų po prisijungimo prie MIT Shun sujungė jėgas su Elektros inžinerijos ir informatikos katedros profesoriumi ir kitu CSAIL nariu Samanu Amarasinghe, programavimo kalbų ir kompiliatorių ekspertu, kad sukurtų grafikų apdorojimo programavimo sistemą, žinomą kaip GraphIt. Paprasta naudoti sistema, kuri generuoja efektyvų kodą iš aukšto lygio specifikacijų, veikė maždaug penkis kartus greičiau nei kitas geriausias metodas.

„Tai buvo labai vaisingas bendradarbiavimas. Nebūčiau galėjęs sukurti tokio galingo sprendimo, jei būčiau dirbęs pats“, – sako jis.

Shun taip pat išplėtė savo tyrimų dėmesį įtraukdamas grupavimo algoritmus, kuriais siekiama sugrupuoti susijusius duomenų taškus. Jis ir jo mokiniai kuria lygiagrečius algoritmus ir sistemas, kad greitai išspręstų sudėtingas klasterizacijos problemas, kurios gali būti naudojamos tokioms programoms kaip anomalijų aptikimas ir bendruomenės aptikimas.

Dinaminės problemos

Pastaruoju metu jis ir jo bendradarbiai daugiausia dėmesio skyrė dinaminėms problemoms, kai laikui bėgant keičiasi duomenys grafikų tinkle.

Kai duomenų rinkinyje yra milijardai ar trilijonai duomenų taškų, algoritmo vykdymas nuo nulio, kad būtų atliktas vienas nedidelis pakeitimas, skaičiavimo požiūriu gali būti labai brangu. Jis ir jo mokiniai kuria lygiagrečius algoritmus, kurie vienu metu apdoroja daug atnaujinimų, pagerina efektyvumą ir išsaugo tikslumą.

Tačiau šios dinamiškos problemos taip pat yra vienas didžiausių iššūkių, kuriuos Shunas ir jo komanda turi įveikti. Kadangi nėra daug dinaminių duomenų rinkinių algoritmams tikrinti, komanda dažnai turi generuoti sintetinius duomenis, kurie gali būti nerealūs ir gali trukdyti jų algoritmų veikimui realiame pasaulyje.

Galų gale jo tikslas yra sukurti dinaminius grafų algoritmus, kurie efektyviai veiktų praktikoje ir atitiktų teorines garantijas. Tai užtikrina, kad jie bus taikomi įvairiuose nustatymuose, sako jis.

Shun tikisi, kad dinamiški lygiagretūs algoritmai ateityje skirs dar didesnį dėmesį tyrimams. Duomenų rinkiniams vis didėjant, sudėtingesniems ir sparčiau besikeičiantiems, mokslininkams reikės sukurti efektyvesnius algoritmus, kad neatsiliktų.

Jis taip pat tikisi, kad dėl kompiuterinių technologijų pažangos kils naujų iššūkių, nes mokslininkams reikės sukurti naujus algoritmus, kad būtų panaudotos naujos aparatinės įrangos savybės.

„Štai ir yra tyrimų grožis – galiu pabandyti išspręsti problemas, kurių kiti žmonės anksčiau nesprendė, ir prisidėti kažkuo naudingu visuomenei“, – sako jis.