Googleren sekretua, matematiken bidez azaldua
Pablo Fernandez Gallardo matematikariaren hitzaldi interesgarri batean izan nintzen atzo Bilbon, Bidebarrieta kaleko liburutegian. Hitzaldi sorta izan da, Matematika eguneroko bizitzan, eta atzokoa zen azkena: Googleren sekretua. Neurri batean, sekretu matematikoa da hori, atzo Fernandez Gallardok azaldu zigunez.
Gaur egun Interneteko erabiltzaile kopuru handiak, gure artean behintzat, Google erabiltzen du bere bilaketak egiteko.
Zergatik da Google jaun eta jabe? Bi arrazoi nagusigatik: azkarra delako (trufaz diosku zenbat milisegundo kostatu zaion) eta nahi duguna lehenengo emaitzetan ematen digulako. Portzentaia handi batean, behintzat. Gutxitan pasatzen da bilatzen duguna lehenengo orrialdean ez dagoela. Horrez gain, "baietz lehenengoan!" botoia dauka. Batzuetan Bilbokoa dirudi...
Arrakasta honen ardura galdera batean baino ez dago oinarritua:
- Zein ordenetan erakutsi behar ditut bilaketaren emaitzak?
Eta galdera hau galdera matematikoa baino ez da...
Hau erantzuteko antolakuntzarako irizpidea behar dugu. Web orriak P1, P2... Pn badira, bakoitzari bere garrantzia eman behar diogu. Demagun 0 eta 1 arteko baloreak direla.
Demagun Interneteko errolda eginten dugula, orri bakoitzari bere garrantzia emanez. Behin kontsulta bat eginda, garrantziaren ordenean emango genituzke emaitzak. Erreza ezta? Garrantzi hori baino ez dugu kalkulatu behar. Goazen ba.
(OHARRA: beste kriterioak ere garrantzitsuak dira, hau da, bi hitz bilatzen baditugu ez da berdina elkarrekin egotea ala urruti, edo izenburuan egotea, edo orriaren azkenengo partean... Suposatuko dugu arazo hau konponduta daukagula)
Azken finean Internet grafo bat bezala deskriba dezakegu. Web orrialde bakoitza erpin bat da, eta ertz bakoitza norabidedun esteka bat. Buruan irudia eginda daukazue, ezta? Matematikoki egoera hau matrize bat bezala jarri dezakegu. Zutabe eta lerro bakoitza Pn bezala etiketatuko dugu, ta matrizearen kontenua honela: Pi-tik Pj-ra esteka badago 1 jarriko dugu, bestela 0 bat. Pj zutabea zenbatuko bagenu, Pj-tik irteten diren esteka guztien kopurua edukiko genuke. Eta lerro bakoitzeko baloreak bilatuz, zenbat esteka dauden gure webgunera apuntatzen.
Lehenengo hurbilketa batean esan dezakegu zenbat eta esteka gehiago gure webgunera, orduan eta inportanteagoak garela. Ez dago gaizki, baina ez da berdina Amazonek nire webgunera esteka edukitzea, edo Zerobatek edukitzea.
Beraz, bigarren hurbilketa batean esango dugu gure garrantzia kalkulatzen dela webgune batean sartzen diren esteka guztien garrantzia gehituz. The washington post-i baino ez diogu ziria sartu behar.
Hau idatz daiteke ekuazio matematiko baten eran, eta azken finean, era matrizialean.
x garrantzien bektorea da, M garrantzien bektorea. Beraz garrantzien konponbidea ekuazio honen emaitza izango da: Mx = Lx
L proportzionalitate konstante bat izanda. Beraz arazo hau autobektore eta autobalioen arazoa da.
Bestalde, demagun surflari aleatorio bat daukagula grafo horretan surf egiten, eta ertz bat edo beste hartuko du aleatorioki. Internet osotik pasa dezan, gaitasun magiko bat ere emango diogu, batazbesteko nahi dugun ehunekoan teletrasportatu daiteke (isolatutako Internet aldetan ere sar dadin).
Surflari honi esker, Mx=Lx-i esker eta Perron - Frobenius teoremari esker edukiko dugu gure emaitza. Azken finean, Ordenagailu bati eman behar dizkiogu
- matrize handi bat (milioika lerro eta zutabekin)
- nahi dugun bektore aleatorioa (beste hainbeste lerrokin),
Eta hamar aldiz!!!!! biderketa bat eginez edukiko dugu gure emaitza. Gure Linux instalatuta daukan etxeko PlayStation 3arekin ezin izango dugu egin, baina zerbitzari piloarekin eta ordu batzurtan edukiko genuke gure garrantziaren kalkulua.
Arazo konplexu, itzel, hartu ezina, azkenean ordu batzuetako arazo matematikoan bihurtu dugu. Eta nitaz fidatzen ez bazarete (ez bainaiz matematikaria), hemen daukazue dokumentu originala (PDF formatuan).
Beste faktoreak ere badaude, ez pentsa, PageRank hori aldatzeko, baina arazoaren alderik handiena konponduta dago honela, gero afinatu baino ez da egin behar.
Ni ere hitzaldi horretan egon nintzen eta oso interesgarria iruditu zitzaidan. Hala ere, Pablok onartu didan bezala, PageRank delakoa matematikoki nola kalkulatu daitekeen azaltzen saiatu zen batez ere eta Google-ek erabiltzen dituen beste irizpide batzuk ia aipatu ere ez zituen egin. Horrek, gero jendeak egin zituen galdera batzuk sortarazi zituen, berak azaldutako eskema horretan ondo sartzen ez ziren adibideekin.
Hizlariak zioenez, PageRank-a behin kalkulatu eta gero bilatutako hitzaren edo hitzen arabera, zerrenda horretan zeuden orriak aukeratzen ziren, ORDENA BERDINEAN erakutsiz. Eta hori ez da horrela. PageRank altuak dituztenak, orokorrean lehen emaitzetan agertzen dira, hori egia da, baina ia aipatu ere ez zituen beste irizpideek, pisu handia dute eta emaitza asko aldatzen dute. Horren arrazoia matematikoki ikustarria ez bada ere (horregatik Pablok ez zien inolako garrantzirik eman), partaideetako batek galdetu zuen bezala, Google-ek erantzun egokienak nola aurkitzen dituen ulertzeko ezinbestekoak dira.
Beraz, matematikoki hitzaldia oso ondo egon zen, nire ustez Brin eta Pagek bete-betean asmatu bait zuten Perron eta Frobeniusen teoremak bilatzailea sortzeko erabili zituztenean, baina Google-ek erabiltzen dituen beste irizpideei ezin zaie garrantzirik kendu (azaltzen ez badira ere, gutxienez beraien garrantzia argi utzi behar da), Google-en sekretuaren zati handi bat bait dira.
Portzierto, orain Bilboko hitzaldian erabili zuen aurkezpena eskuragai dago.