La competiţia NeurIPS Traffic4cast 2022, doi developeri de la Bolt, Andrei Ilie şi Martin Lumiste, au ocupat locul al doilea. Provocarea ediţiei din decembrie a competiției a fost utilizarea informaţiilor de tip sparse traffic counter pentru a prezice nivelul traficului, pentru un oraş întreg, cu 15 minute în avans.
Despre această provocare, algoritmul celor doi care foloseşte machine learning și modul în care oraşele pot folosi acest algoritm am discutat cu cei doi developeri.
Club IT&C: Ce a stat în spatele deciziei de a participa la această ediţie a competiţiei NeurIPS?
Andrei Ilie: NeurIPS este una dintre cele mai cunoscute conferințe la nivel mondial, din domeniul inteligenței artificiale și nu numai, la care participă mari universități, companii sau institute de cercetare. Anual, în cadrul ei, au loc şi o serie de competiții interesante, la care pasionații pot participa.
Un exemplu de competiție propusă la NeurIPS este Reconaissance Blind Chess. Concurenţii creează agenți inteligenți care participă la partide de șah, în care pot observa doar stări parțiale ale tablei de joc. La fiecare mutare, agenții aleg să observe un pătrat 3×3, iar apoi iau decizia de mutare doar pe baza informației parțiale deduse până la acel moment al jocului.
Bineînţeles, un alt exemplu este competiția la care noi am ocupat locul al doilea acest an: Traffic4cast. Aici, autorii pun la dispoziția participanților seturi mari de date reprezentând stadiul traficului în câteva orașe, iar obiectivul lor este de a prezice cât mai precis nivelul de trafic pentru următoarele 15 minute.
Am fost surprinşi să aflăm că NeurIPS organizează o competiție atât de similară cu temele noastre de lucru și cercetare de la Bolt. Acuratețea traficului pe care noi îl estimăm și, implicit, a celebrelor ETA-uri (Estimated Time of Arrival) este de mare importanță pentru business-ul nostru. Accesul la ETA-uri precise ajută atât pentru o bună experiență a clienților cu produsele noastre, cât și în procesul de optimizare a alocării șoferilor de ride-hailing sau a curierilor pentru livrările de mâncare.
Martin a găsit aceasta competiție și m-a convins și pe mine să particip. La vremea respectivă mă aflam în concediu de paternitate şi am fost reticent la început. Însă, odată ce am alocat timp pentru a explora datele competiției și am reușit să trimitem o primă soluţie comună pe serverul de evaluare, am realizat cât de aliniată este problema respectivă cu pasiunile și cercetările noastre curente. De acolo, a mai fost doar puțin până la a lucra împreună zi de zi, consecvent și organizat, pentru a formula soluții din ce în ce mai bune.
Club IT&C: Ne puteţi descrie, pe scurt, rolul pe care îl are fiecare dintre voi la Bolt?
Andrei Ilie: Lucrez de aproximativ trei ani la Bolt. La început, rolul meu a fost de Senior Data Scientist și m-am ocupat, în principal, de modelele de machine learning pe care Bolt le folosește pentru a produce ETA-uri cu acuratețe. În general, rolul de Data Science la Bolt presupune colaborarea strânsă cu divizia de Product și înţelegerea modelului de business. La acestea se adaugă prototiparea și cercetarea soluțiilor data-driven, care pot ajuta la rezolvarea unor probleme concrete, urmate de implementarea și monitorizarea acestor soluții în mediul de producție.
În prezent, ocup rolul de Engineering Manager și coordonez un grup de trei echipe de Data Science, care se ocupă de harți (Geo), de business-ul de livrare de mâncare (Bolt Food) și de business-ul de închiriere a trotinetelor electrice și car-sharing (Bolt Drive).
Martin Lumiste: Lucrez de 4 ani la Bolt și ocup poziția de Staff Data Scientist și, de curând, cea de Group Tech Lead al echipe de Data Science. În trecut, am construit algoritmii care stabilesc prețul dinamic al curselor Bolt, cu obiectivul de a balansa cererea și oferta din platforma noastră. De asemenea, am lucrat în zona de harți, construind și îmbunătățind modele de machine learning pentru predicția de ETA-uri și rute pe care șoferii le vor urma. În prezent, ocup rolul de Group Tech Lead în organizația de Data Science, unde mă ocup de cercetarea și construirea unor metode de care toți colegii din Data Science să beneficieze.
Club IT&C: Soluţia propusă de voi în cadrul NeurIPS Traffic4cast foloseşte un algoritm care generează predicţii de trafic pe baza extrapolării informaţiilor provenite de la instrumentele de măsurare a traficului din intersecţii. Ne puteţi explica mai pe larg cum funcţionează?
Obiectivul competiției a fost utilizarea datelor live provenite de la traffic counters, care măsoară câte mașini trec prin anumite intersecții, pentru a prezice traficul la nivelul fiecărei străzi dintr-un oraş întreg. Motivația este că multe orașe dispun de aceste mecanisme (traffic counters), fiind destul de ieftine și ușor de montat. Însă, dificultatea problemei constă în raritatea acestor senzori, aceştia fiind disponibili – de obicei – doar în intersecțiile principale, pe când predicțiile trebuie să acopere majoritatea străzilor dintr-un oraş.
Soluția noastră a exploatat tipare statistice între configurația măsurătorilor senzorilor la momente istorice și vitezele înregistrate de mașini pe toate străzile din oraș (acestea fiind datele de antrenament). În general, metoda propusă de noi a fost una standard, care foloseşte un model numit gradient boosted tree (LightGBM). Partea inovatoare a soluției constă în modul în care am folosit măsurătorile de traffic counters. Deși relativ rare, instrumentele de măsurare a traficului erau în număr de aproximativ 4000, ceea ce făcea nefezabil ca toate să fie utilizate ca date de intrare ale modelului pe care voiam să îl antrenăm. Aşadar, am folosit o tehnică clasică de reducere a dimensionalităţii, Principal Component Analysis, care ne-a ajutat să reducem cele 4000 de măsurători la aproximativ 10 numere reprezentative, pentru fiecare interval orar din setul de date.
Au fost multe alte idei pe care le-am exploatat în obținerea soluției finale, în majoritatea cazurilor refolosind lecţii pe care le-am învăţat în anii de cercetare pentru îmbunătățirea ETA-urilor. Toate acestea sunt documentate într-un articol deschis, care se afla la următorul link: https://arxiv.org/abs/2211.00157. De asemenea, toată implementarea soluției noastre este open-source: https://github.com/skandium/t4c22.
Club IT&C: Aşadar, acest algoritm necesită puţină putere de procesare şi este foarte rapid. Practic, pe bază de machine learning, acesta poate fi „antrenat” pe un laptop sau computer personal? De asemenea, puteţi explica în termeni simpli ce este Gradient Boosted Trees (GBT)?
În general, modelele deep de tip Graph Neural Networks (GNNs) se potrivesc perfect în estimarea proprietăților muchiilor unui graf, acesta fiind şi cazul uzual în problemele de estimare a traficului. Totuși, antrenamentul unor astfel de modele necesită acces la resurse de procesare grafică (GPU), este costisitor și poate dura mult.
Metoda noastră s-a inspirat din tot ceea ce am învăţat în ultimii ani de lucru la Bolt: de multe ori, transpunerea datelor structurate (cum ar fi cele din grafuri) în forma tabulară și utilizarea metodelor simple, precum Gradient Boosted Trees (GBTs) peste acest format de date poate da rezultate surprinzător de bune.
Folosirea modelelor deep peste GNNs permite identificarea atributelor cheie în mod automat, exploatând structura existentă în grafuri. Pot identifica tipare arbitrar de complexe într-un mod automat, relevante pentru problemele în care sunt folosite. În mod opus, folosirea unor modele ca GBTs necesită identificarea tiparelor în mod manual și transpunerea lor în forma tabulară. Experiența noastră din domeniu ne-a ajutat să înțelegem care sunt atributele pe care trebuie să le capturăm într-o formă tabulară, iar apoi să folosim GBTs – care sunt mult mai rapizi și eficienți – fiind totodată şi foarte preciși. Tipul de modele pe care le-am folosit este atât de simplu computațional, încât poate fi antrenat și pe un laptop personal (ceea ce am și făcut pentru o parte a concursului), singura limitare impusă fiind de memorie RAM. Antrenamentul este foarte rapid (maxim câteva ore pentru cele mai mari orașe), permițând o iterare eficientă peste idei.
Modelele de tip GBT există de mult timp. În esenţă, o formă similară metodelor de acum a fost publicată pentru prima oară 1999, iar multe alte metode similare au fost publicate anterior. Problemele de bază pe care le pot rezolva sunt cele de regresie (de exemplu, să estimeze prețul unui apartament în funcţie de suprafața lui, anul construcției etc.) sau clasificare (de exemplu, să estimeze dacă un bloc are risc seismic ridicat, pe baza anului în care a fost construit, a materialelor folosite etc). Pentru ambele probleme, modalitatea modelelor GBT de funcționare este foarte similară. Acestea învață iterativ arbori de decizie – fiecare arbore de decizie fiind un model simplu individual, care încearcă să corecteze eroarea arborilor creați înaintea lui. Fiecare arbore pornește de la suma estimărilor arborilor creați înaintea lui și încearcă să creeze un model mai precis. Arborele supune datele de intrare unui traseu de operatori logici, iar la final – în ceea ce literatura numește „frunze” – se află o componentă parțială a ceea ce vrem să prezicem (de exemplu, apartamentul mai vechi de 50 de ani -> suprafață mai mare de 60m, dar mai mică de 70 m -> preț 100.000 unități).
Club IT&C: Cum vedeţi voi soluţia aceasta aplicată în oraşe şi care sunt beneficiile ei?
Multe orașe dispun deja de traffic counters, iar soluția noastră poate fi aplicată ușor peste astfel de măsurători. Avantajul metodei propuse de noi este că se poate antrena foarte rapid, produce estimări într-un timp foarte scurt și nu necesită putere de calcul mare pentru niciuna dintre etapele ei.
Estimările precise ale timpilor de mișcare în oraș sunt esențiale pentru planificarea călătoriilor, pentru logistica firmelor de transport sau curierat și nu numai. În general, estimările de trafic ajută la buna funcționare a orașelor, fiind o sursă esențială pentru o bună organizare a mobilității urbane.
Club IT&C: Din cunoştinţele voastre, cum stă România la acest capitol, la instrumentele de măsurare a nivelului de trafic?
Din păcate, nu cunoaștem în detaliu stadiul tehnologizării României din acest punct de vedere. Cu siguranță, există senzori și camere de trafic în marile orașe din România, dar nu putem comenta asupra modului în care astfel de fluxuri de date sunt folosite sau nu în prezent. Suntem convinşi că există o plajă largă de îmbunătățiri aduse traficului din marile orașe pe baza metodelor data-driven: prin folosirea estimărilor de trafic pentru planificarea mobilității în general, dar, mai ales, prin eficientizarea traficului existent, folosind metode smart. Aici pot intra semafoarele smart, sensurile reversibile, crearea unor noi bretele/șosele în urma identificării tiparelor de mobilitate din orașe și a „bottleneck”-urilor acestora etc. De asemenea, aceste tehnologii ne ajută şi pe noi, la Bolt, să aducem îmbunătăţiri la nivelul managementului mobilităţii din oraşe, prin transformarea mediului urban dintr-unul orientat pe vehicule, în unul care prioritizează locuitorii şi bunăstarea lor generală.
