Un motor eficient de căutare în e-commerce

2. Istoric și motivație

2.1 Istoric al căutării informației

Primele colecții de documente au fost înregistrate pe pereții pictați ai peșterilor. Apoi, până la invenția hârtiei, anticii romani și greci au înregistrat informația pe role de papirus. Unele artefacte de papirus aveau mici etichete atașate rolelor, care ajutau la găsirea informației. Cuprinsul unei lucrări au început să apară în rolele din Grecia în secolul 2 î.Hr. Ulterior, s-a scris pe pergament, straturi subțiri de piele de animale. Pentru perioada aceasta, cele mai relevante metode de informație erau cele pe cale orală. (Langville și Meyer, 2006)

Inventarea hârtiei, cel mai bun suport de stocare a informației, a crescut viteza înregistrării documentelor și au început să apară colecții tematice. Acest lucru a fost accelerat puternic prin inventarea presei tipografice de către Johann Gutenberg în 1450. În anii 1700 au apărut în America biblioteci publice, la inițiativa lui Benjamin Franklin. Astfel, a crescut dorința de a ierarhiza informațiile. (Langville și Meyer, 2006)

Primul sistem de organizare a informației a fost atribuit autorului roman Valerius Maxiums, care l-a folosit în anul 3 d.Hr. pentru a organiza informația unei cărți ale lui. Ulterior, au apărut sisteme ca sistemul decimal Dewey (1872), cataloagele de cărți (începutul anilor 1900), microfilmul (anii 1930), sistemul MARC (MAchine Readable Cataloging – catalog citibil de către mașini) în anii 1960. În ceea ce privește căutările în baze de date pentru cărți au început cu un sistem SMART (inteligent) al Cornell în anii 1960. (Langville și Meyer, 2006)

În anul 1989 stocarea, accesare și căutarea colecțiilor de documente a fost revoluționată de o invenție numită World Wide Web (rețeaua pentru lumea întreagă) de către fondatorul său, Tim Berners-Lee. Aceasta a devenit semnalul final al dominației Erei Informației și moartea Erei Industriale. Cu toate acestea, volumul mare de informație făcea căutările inițiale foarte greoaie. (Langville și Meyer, 2006)

Primele motoare de căutare aveau dificultăți în ierarhizarea informației. Lucrurile s-au schimbat radical odată cu apariția Google. Într-un document datat 29 ianuarie 1998, "The PageRank Citation Ranking: Bringing Order to the Web" (ierarhizarea bazată pe citări PageRank: aducând ordine în Internet), autorii, dintre care primii doi au fondat Google (Lawrence Page, Sergey Brin, Rajeev Motwani și Terry Winograd), prezentau PageRank, un algoritm care dădea o importanță resurselor găsite în căutări, pe măsura volumului linkurilor către o anumită resursă (cu precizarea că o resursă putea acorda o valoare mai mare dacă, la rândul ei, avea multe linkuri). Autorii concluzionau că "folosind PageRank, putem ordona căutările, în așa fel încât paginile cele mai importante au poziții preferențiale. În experimentele făcute, asta a dus la rezultate de calitate ridicată pentru utilizatori". (Page et al., 2018)

Documentul era o continuare a documentului „The Anatomy of a Large-Scale Hypertextual Web Search Engine” (anatomia unui motor de căutare pe Internet pe scală largă, și hipertextual), în care Sergey Brin și Lawrence Page prezentau motorul de căutare în detaliu, inclusiv formula de calculare a PageRank-ului:

„Presupunem că pagina A are linkuri de la paginile T1 ... Tn (aceste pagini o citează. Parametrul d este un factor de amortizare, care poate fi setat între 0 și 1. În general, îl stabilim la valoarea 0,85. De asemenea, C(A) este definit ca numărul de linkuri care pornesc dinspre pagina A spre alte pagini. PageRank-ul paginii A este definit astfel:

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

De notat că PageRank-ul formează o distribuție probabilistică peste toate paginile de Internet, așa că suma tuturor PageRank-urilor va fi 1. PageRank-ul pentru 26 de milioane de pagini web poate fi calculat în câteva ore pe o stație de lucru medie.” (Brin și Page, 1998)

Într-o lucrare apărută în 2006 (Langville și Meyer, 2006), formula este prezentată ca mai jos, o ecuație simplă a sumelor, rădăcina cărei derivă din cercetările bibliometrice, analiza structurii citațiilor între lucrările academice. PageRank-ul paginii P_i, numită r(P_i), este suma tuturor PageRank-urilor paginii care direcționează către P_i.

unde B_Pi este setul paginiilor care au trimitere către P_i (trimit backlink către P_i în cuvintele autorilor Sergey Brin și Lawrence Page), și |P_j| este numărul de linkuri externe (către alte entități) trimise din pagina P_j. De observat că PageRank-ul paginilor care trimit linkuri către entitate curentă r(P_j) din ecuația anterior menționată este temperat de numărul de recomandări făcute de P_j, notat |P_j|. Problema cu ecuația respectivă este că valorile r(P_j), PageRank-ul paginilor care trimit către pagina P_i, sunt necunoscute. Pentru a trece peste această problemă, autorii ecuației au folosit o procedură iterativă. Astfel, ei au presupus că, la început, toate paginile au un PageRank egal una cu cealaltă (să zicem, 1/n, unde n este numărul de pagini din indexul web al lui Google). Acum regula în ecuația prezentată este urmată pentru a calcula r(P_i) pentru fiecare pagină P_i din index. Regula dinecuație este aplicată în mod succesiv, înlocuind valorile iterației anterioare în r(P_j). Introducem și alte notații pentru a defini această procedură iterativă. Fie r_k+1(P_i) PageRank-ul paginii P_i pentru iterația k + 1. Atunci,

(Langville și Meyer, 2006)

Procesul este inițiat cu r₀(P_i) = 1/n pentru toate paginile P_i și este repetat, în speranța că scorurile Page Rank vor converge în final către niște valori stabile. Aplicând ecuația de mai sus rețelei din figura de mai jos dă următoarele valori pentru PageRank, după câteva iterații:

1. 
   2
   

3

6 5

4

Figura 2.1.1 Graf direcționat, reprezentând o serie de șase pagini

(Langville și Meyer, 2006)

Iterația 0	Iterația 1	Iterația 2	Rank la iterația 2
R0(P1) = 1/6	R1(P1) = 1/18	R2(P1) = 1/36	5
R0(P2) = 1/6	R1(P2) = 5/36	R2(P2) = 1/18	4
R0(P3) = 1/6	R1(P3) = 1/12	R2(P3) = 1/36	5
R0(P4) = 1/6	R1(P4) = 1/4	R2(P4) = 17/72	1
R0(P5) = 1/6	R1(P5) = 5/36	R2(P5) = 11/72	3
R0(P6) = 1/6	R1(P6) = 1/6	R2(P6) = 14/72	2

Tabel 2.1.1 Primele câteva iterații ale ecuației anterior prezentate asupra grafului (Langville și Meyer, 2006)

Un alt algoritm al motoarelor de căutare este și HITS. Un acronim pentru „Hypertext Induced Topic Search” (căutare de subiecte induse prin hipertext), acesta a fost un algoritm aflat la baza Teoma, un motor de căutare lansat în 2001 și achiziționat în același an de un alt motor de căutare, Ask Jeeves Inc. (The Globe și Mail, 2001)

HITS, algoritm inventat de Jon Kleinberg în 1998 (aproximativ în aceeași perioadă în care Sergey Brin și Lawrence Page lucrau la algoritmul PageRank), asemenea PageRank, folosește structura de URL-uri pentru a crea scoruri de popularitate asociate cu paginile web. Totuși, HITS are anumite diferențe (detalii preluate din Langville și Meyer, 2006):

• 
  Dacă metoda PageRank produce un singur scor de popularitate pentru fiecare pagină, HITS produce două.
  
• 
  În timp ce PageRank-ul este independent de căutare, HITS depinde de căutarea făcută.
  
• 
  HITS privește paginile ca autorități și huburi. O autoritate este o pagină cu numeroase linkuri către ea, și un hub este o pagină cu multe linkuri dinspre ea spre alte pagini. Paginile de autoritate și huburile merită să fie numite „bune” atunci când următoarea afirmație circulară este validă: „Autoritățile bune au linkuri către ele din partea unor huburi bune și huburile bune trimit către autorități bune”. Așadar, fiecare pagină este o măsură a autorității și o măsură a unui hub.
  

Cum funcționează algoritmul? (Langville și Meyer, 2006) Fiecare pagină i are un scor de autoritate x_i și un scor de hub y_i. Fie E setul tuturor marginilor direcționate în graful de Internet și fie e_ij marginea direcționată de la nodul i către nodul j. Dat fiind faptul că fiecărei pagini i-a fost atribuită inițial un scor de autoritate inițială x_i și un scor de hub y_i, HITS rafinează în mod succesiv aceste scoruri calculând:

, unde k = 1, 2, 3, ...

Aceste ecuații, care au fost ecuațiile originale ale inventatorului lor, Jon Kleinberg, pot fi scrise într-o formă matriceală cu ajutorul matricei de adiacență L a grafului de URL-uri direcționate. (Langville și Meyer, 2006)

P₁ P₂ P₃ P₄

P₁ 0 1 1 0

L = P₂ 1 0 1 0

P₃ 0 1 0 1

P₄ 0 1 0 0

1 2

3 4

Figura 2.1.2 Graf pentru o rețea de 4 elemente (Langville și Meyer, 2006)

În notarea matricială, ecuațiile precizate iau forma:

x^(k) = L^Ty^(k-1) și y^(k) = Lx^(k),

unde x^(k) și y^(k) sunt n x 1 vectori care păstrează autoritatea aproximativă și scorurile fiecărui hub la fiecare iterație. (Langville și Meyer, 2006)

Algoritmul original HITS: (Langville și Meyer, 2006)

1. 
   Se inițializează y⁽⁰⁾ = e, unde e este vectorul coloană al tuturor valorile de 1. Pot fi folosiți și alți vectori de început pozitivi.
   
2. 
   Până la convergență, execută:
   

x^(k) = L^Ty^(k-1)

y^(k) = Lx^(k)

k = k + 1

Se normalizează x^(k) și y^(k).

Lucrurile au evoluat, pe măsură ce anii au trecut. Algoritmii s-au tot schimbat, la un moment dat Google afirma că au 200 de factori. Întrebat despre asta, în 2010, CEO-ul Google, Eric Schmidt, a afirmat că nu îi poate menționa, pentru că sunt într-o continuă schimbare, și, de asemenea, pentru că sunt un secret comercial al companiei. (Sullivan, 2010)

Potrivit informațiilor celor de la SearchEngineLand, un site important în lumea motoarelor de căutare, „RankBrain” este numele dat de către Google unui sistem de inteligență artificială bazat pe învățare automată (machine-learning artificial intelligence system) care este folosit pentru a genera rezultatelor căutărilor. Prin machine learning, un calculator poate să se învețe pe sine însuși cum să facă o sarcină, mai degrabă decât să urmeze o procedură predefinită. La data apariției articolului, algoritmul ocupa locul 3 în cele mai importante criterii după care un site era afișat în rezultatele căutărilor. Scopul lui? Interpretarea rezultatelor care nu conțin cuvintele căutate în mod exact, ci cuvinte ce ar putea fi similare. Nevoia de a exista a algoritmului venit din faptul că Google procesa în 2016 3 miliarde de căutări zilnic, iar în 2007 a afirmat undeva între 20-25% din acele căutări nu au fost observate până atunci (nu fuseseră probabil căutate niciodată până atunci). În 2016 e posibil să fi ajuns la 15% din căutări, în continuare o valoare mare de căutări pentru care algoritmul își justifică existența. Sunt căutări în special formate din mulți termeni („long-tail”, căutări foarte specifice, dar, totuși, numeroase). (Sullivan, 2016)

Luna	Google	Bing	Yahoo!	Baidu	Yandex Ru	Yandex	Alții
2017-02	92,35	2,91	2,17	1,01	0,42	0,35	0,79
2017-03	92,31	2,96	2,2	1,05	0,38	0,35	0,77
2017-04	92,48	2,89	2,01	1,11	0,36	0,35	0,79
2017-05	92,06	2,92	2,07	1,39	0,35	0,34	0,87
2017-06	91,88	2,88	2,18	1,45	0,38	0,38	0,86
2017-07	92,01	2,55	2,23	1,44	0,4	0,49	0,87
2017-08	91,64	2,52	2,32	1,53	0,36	0,5	1,13
2017-09	91,84	2,59	2,33	1,42	0,39	0,41	1,02
2017-10	91,47	2,75	2,25	1,8	0,42	0,41	0,9
2017-11	92,06	2,76	1,73	1,64	0,5	0,36	0,94
2017-12	91,79	2,75	1,61	1,66	0,57	0,39	1,24
2018-01	91,74	2,76	1,83	1,39	0,58	0,36	1,33
2018-02	91,63	2,71	1,94	1,29	0,63	0,33	1,49

Tabel 2.1.2 Cota de piață la nivel mondial, motoare de căutare (StatCounter Global Stats, 2018)

Vă puteți întreba unde au loc căutările în 2018, nu doar cele din motoare de căutare, ci, la modul general, pe toate platformele unde pot avea loc căutări. Date din februarie 2018 pentru piața din SUA arată dominația Google, care deține motorul de căutare, Google Imagini și YouTube (cu un procent mult mai mic, și Google Hărți). De remarcat că Amazon, cel mai mare magazin online, are o cotă un pic mai mare decât Bing, al doilea motor de căutare generalist, după Google. (Fishkin, 2018)

Figura 2.1.3 Cota de piață a căutărilor web, februarie 2018, pentru piața din SUA (date din partea companiei Jumpshot)

Câte motoare de căutare (generale, pentru tot Internetul) există? Poate, din diferite surse, ați aflat că există „sute de motoare de căutare”. Majoritatea dintre acestea sunt însă fie variații ale site-urilor principale (de exemplu, Google.fr pentru Franța sau Google.co.uk pentru Marea Britanie), fie sunt meta motoare de căutare, care folosesc rezultatele oferite de alte motoare de căutare (Dogpile, Mamma.com, Metacrawler). Da, există unele motoare de căutare tematice (Wolfram|Alpha, IMDb), dar motoarele cele mai vizitate au un procent apropiat de 95% din piața motoarelor de căutare. (Grappone și Couzin, 2011)

Există și alte tipuri de algoritmi care pot susține un motor de căutare. Platforma de clipuri video YouTube este al doilea motor de căutare, ce-i drept, specializat, după Google, cu aproximativ 3 miliarde de căutări pe lună, un volum de căutare mai mare decât cel al Bing, Yahoo!, AOL și Ask.com combinate. (Wagner, 2017) Lucrurile la care se uită cei 1,5 miliarde de utilizatori înregistrați ai platformei YouTube sunt influențate de o listă de clipuri asemănătoare. De fiecare dată când un internaut privește un clip YouTube, i se prezintă într-o bară laterală o listă de clipuri asemănătoare. Acea listă e considerată cel mai important factor în creșterea cotei de piață a YouTube. În una din puținele explicații publice despre cum funcționează formula, o lucrare academică care prezintă rețelele neuronale ale algoritmului, inginerii YouTube o descriu drept una din "cele mai mari și sofisticate sisteme de recomandare la scală industrială existente în lume". (Lewis, 2018)

Faptul că Facebook, cea mai folosită rețea socială la nivel mondial – 2,2 miliarde de utilizatori activi pe lună, în al 4-lea trimestru al lui 2017 (Statista, 2018) –, cu un potențial enorm în a ajuta utilizatorii în căutarea de produse și servicii pe plan local, cu un ecosistem format din milioane de pagini de afaceri, date despre locație ale utilizatorilor, date de comportament, informații demografice, rată de angajament, nu a reușit în anii recenți să fie un concurent serios pentru Google în căutările de afaceri locale poate fi un argument că a fi relevant în căutări e o sarcină mai grea decât pare la o analiză superficială.