Konplexutasun konputazionaleko teorialariek deskubritu egin dute problema jakin batzuk zail bihurtzen dituen hori zer den ulertzeko modu berri eta harrigarri bat.
Informatikari teorikoak ideia konplexuez arduratzen dira. Baina ahal duten neurrian, beti nahiago dute ideia sinpleekin lan egitea. Erregulartasunaren lema izeneko 2009ko tresna batek hori egiteko modu bikaina eskaintzen die. Izan ere, problema edo funtzio konputazional jakin bat zati sinpleagoetan banatzea ahalbidetzen die.
Konplexutasun konputazionalaren teorialariek problema ezberdinen zailtasun erlatiboa aztertzen dute, eta sinplifikatzeko gaitasun horrek maneiatzeko zailak diren funtzio matematikoak ulertzen lagundu die denbora luzez. Baina zati konplexuak dituzten problema batzuek erronka planteatzen diote oraindik ere analisiari.
Orain, lan berri batek ulertzeko zailak diren problema horiek aztertzeko modu bat ekarri digu. Eta aurrerapena espero ez zen informatikaren arlo batetik etorri da: ekitate algoritmikoa. Horren bidez, banketxeek eta aseguru etxeek erabiltzen dituztenen moduko algoritmoak aztertzen dira, bermatzeko pertsonak bidezko tratua jasotzen dutela. Emaitza berriek erakutsi dute ekitate tresnek behar bezala mapatu ditzaketela problema zail baten zatiak, bai eta ebaztea zailtzen duten problemaren eremu zehatzak isolatu ere.
“Lan zoragarria da benetan. Eta oso zirraragarria”, adierazi du Michael Kimek, lan berrian berrerabili den ekitate tresnetako bat sortzen lagundu zuen Cornell Unibertsitateko zientzialari informatikariak. «Espazio horietan lan egiten duen teorialari gisa, emaitza bikaina da norbaitek arlo jakin bateko zure lana hartu eta beste arlo batera aplikatzea».
Doitasun pronostikoak
Erakundeak gero eta erosoago sentitzen dira algoritmoak erabilita erabakitzeko nork jasotzen duen banku mailegu bat, adibidez, edo nori eman behar zaion baldintzapeko askatasuna; eta, ondorioz, gero eta garrantzitsuagoa da kalkuluetan giza aurreiritziak sartzen ari ez direla egiaztatzeko modu formal bat izatea. Baina badago bidezkoa zer den neurtzeko modu bat baino gehiago.
Has gaitezen iragarpen baten doitasuna neurtzeko problema orokorrarekin. Plantea dezagun zure hirian euria egingo duen iragartzen duen ordenagailu programa bat bururatzen zaizula, eta haren doitasuna neurtu nahi duzu. Esan dezagun urteko egunen % 40an euria egiten duela, gutxi gorabehera. Multidoitasun izeneko ekitate tresna erabiltzen baduzu, zure algoritmoa doitzat jo liteke % 40aren inguruko batez besteko iragarpena egiten badu. Eta hori lor liteke algoritmoak euri probabilitatearen % 40 iragartzen badu urteko egun guztietan, edo euriaren % 100 iragartzen badu soilik egunen % 40an (izan ere, batezbestekoa berbera litzateke). Hala ere, espezifikoagoa izatea nahi baduzu (euria egingo du asteartean?), – gerta daiteke algoritmo berbera doia ez izatea.
Har dezagun orain mailegu eskatzaileek ordainketa guztiak egitearen probabilitatea iragartzen duen algoritmo bat. Ez da nahikoa tasa orokor zuzena iragartzen duen algoritmo bat izatearekin (hau da, aurreko adibideko euri probabilitatearen % 40a). Populazio talde ezberdinetako norbanako espezifikoen tasa iragarri behar du, modu doi bezain bidezkoan.
Iragarpen doiak, oro har, murriztu egiten dira konplexutasun geruzak gehitzen diren neurrian, hala nola eguraldi pronostikorako egun jakin bat edo mailegu bat eskatzen duen pertsona jakin bat. Benetako bizitzako egoerak berehala bihurtzen dira konplexuegiak doitasun anizkuna horiek neurtzeko modurik onena izateko.
2018an, Kim eta ekitatearen esparruko beste ikertzaile batzuek multikalibrazio izeneko ekitate paradigma berri eta solidoago bat sortu zuten, konplexutasun maila horiek kontuan izaten dituena. Tresna berriak iragarpen “kalibratuak” ematen ditu, hau da, sistemak konplexutasun geruza guztiak kontuan izaten ditu. Multikalibrazioak esan nahi du algoritmo baten iragarpenak doiak direla, egunero begiratuta zein asteartean soilik. Edo pertsona guztientzako mailegu iragarpenak egiten ari bagara zein pertsona mota jakin batentzako soilik. Multikalibrazioak ekitatea bermatu behar luke esparru guztietan.
Baina erabilgarria da ere beste gauza batzuetarako.
Ekitateaz harago
Iaz, informatikari teorilarien talde batek tresna horiek beste esparru batean aplikatzeko aukera aztertu zuen. Frogatu zuten multidoitasuna eta multikalibrazioa grafoen teoriako teoremekiko (matematiken arloko diziplina horrek objektuen arteko harremanak aztertzen ditu) baliokideak zirela. Horren ondorioz, Salil Vadhanek, Harvard Unibertsitateko zientzialari informatikariak, bere buruari galdetu zion zein esparrutan izan zitekeen tresna hori erabilgarria.
«Ikusi genuen emaitzak lortzen ari zirela multikalibrazioa grafoen teorian [erabilita]», azaldu du Vadhanek, 2009ko erregulartasunaren lemaren eta lan berriaren egileetako batek. «Orain, gauza bera egin nahi dugu konplexutasunaren teoriarekin». Horretarako, Harvardeko lankide Cynthia Dworkekin (hura ere grafoen teoriari buruzko artikuluko egileetako bat) eta Sílvia Casacuberta bere graduko ikaslearekin (egun graduondoko ikaslea da Oxfordeko Unibertsitatean) elkartu zen.
Hirukoteak hiztegi moduko bat sortu zuen, ekitate tresnen eta konplexutasunaren teoriaren ideien arteko itzulpenak egiten zituena. Frogatu zuten edozein populazio (izan pronostikoa egiteko egunak izan mailegu eskatzaileak) itzul litekeela problema konputazional baterako sarrera posibleen panorama batean.
Konexioak ezarri ondoren, ikertzaileek frogatu zuten multidoitasuna, ekitate tresnarik ahulena, erregulartasunaren lemaren baliokidea dela: funtzio sinple bat —euriaren batez besteko iragarpena, adibidez— funtzio konplexu batera hurbil daiteke —hala nola benetako batezbestekoa— (benetako eurialdiak kalkulatuta). «Multidoitasunarekiko eta erregulartasunarekiko konexioa terminologia aldaketa bat besterik ez da», adierazi du Vadhanek.
Eta hori frogatu ondoren, ikertzaileek beren buruari galdetu zioten ea multikalibrazioa, ekitate tresna sendoena, ezin ote zen aplikatu gai solidoagoren bat frogatzeko. Eta zuzen zebiltzan: deskubritu zuten ekitate algoritmo batek azpipopulazioen barruan iragarpen doiak mantentzeko gaitasuna aplika litekeela beste lema bat indartzeko; hain zuzen ere, Impagliazzoren oinarrizko lema. Lema horrek laguntzen digu problema zail baten egitura ulertzen, izan ditzakeen sarrera (input) guztiak aztertuta; eta, horietatik, ebazteko zailena zein den galdetu behar diogu gure buruari.
Input jakin batzuekin bakarrik zaila den problema bat imajinatzeko, har dezagun berriro euria. Imajina dezagun urtaro euritsu bat —zeinetan euria egiten duen ia egunero— eta urtaro lehor bat —zeinetan ez duen apenas euririk egiten— dituen eskualde bat. Horri esker, zuzen iragar dezakegu euria egingo duen denboraren % 90ean. Gainerako % 10a (pentsatzekoa denez, bi urtaroen arteko muga egunetan, zeinetan euria egiteko eta zerua oskarbi egoteko probabilitatea berdina den) input zailak dira. Egun horietarako iragarpenak ez dira izango ausazko usteak baino hobeak.
«[Funtzio zail batek deskribatutako] problema konputazional batean, zein input dira errazagoak eta zein zailagoak?»; horixe galdetu zion bere buruari zendutako Luca Trevisanek, Italiako Bocconi Unibertsitateko zientzialari informatikari teorialariak (2009ko erregulartasunaren lemaren egileetako bat ere bazen). Impagliazzok frogatu zuen edozein problema zailetarako algoritmo efiziente guztientzat zailak diren puntu zailen multzo komun bat dagoela beti.
Lan berriaren egileek frogatu dute multikalibrazioaren eskakizun zorrotzak aplikatzeak lema hobetzen duela, hura orokortuz, problema gehiagotara aplikatu ahal izateko. Problema baten input zehatzak identifikatzeko aurreko saiakerek —existitzen zirela soilik frogatzearen ordez—, inplikatzen zuten inputak zati txikiagoetan zatitzea eta funtzionatzen jarraitzen zuen hurbilketa funtzio bat bilatzea. Eta, ondoren, nahikoa zatiketa egin ostean, hurbilketarik jasan ezin zuten inputak identifikatu ahal ziren. Hor dagoen arazoa da zatiketak prozesatu beharreko zatien kopuru esponentzial bat eragiten zuela; eta, beraz, ikuspegi hori ez zen bideragarria. Multikalibrazioa aplikatzean, berriz, ikertzaileek zatiketen guztizko kopurua murriztu ahal izan dute; eta, horrela, funtzio zailaren hurbilketa egiteko ikuspegia sinplifikatzea lortu dute.
«Asko gustatu zait emaitza», esan du Huijia (Rachel) Linek, Washingtoneko Unibertsitateko zientzialari informatikari teorialariak (iazko grafoen teoriari buruzko artikuluaren egileetako bat ere bada). «[Oinarrizko lema] klasikora itzultzean datza, norabide berri bat emateko».
«Polita da ikustea konplexutasunean inspiratutako iragarpen ikuspegi hori badugula, eta horren ondorioz ideia eder berriak sortu direla ekitatean. [Eta] polita da konplexutasunera itzultzen direla ikustea, zirkulua itxita», esan du Kimek. «Badugu beti esperantza horrelako gauzak gertatzeko».
Jatorrizko artikulua:
Lakshmi Chandrasekaran (2024). The Question of What’s Fair Illuminates the Question of What’s Hard, Quanta Magazine, 2024ko ekainaren 24a. Quanta Magazine aldizkariaren baimenarekin berrinprimatua.