Norme și distanțe — lecție practică de AI Engineering

Funcția de distanță definește ce înseamnă „similar”. Dacă o alegeți greșit, tot ce depinde de ea va funcționa greșit.

Tip: Construire Limbaj: Python Cerințe preliminare: Faza 1, lecțiile 01 (Intuiție pentru algebra liniară), 02 (Vectori, matrice și operații) Durată: ~90 de minute

Obiective de învățare

Implementarea de la zero a funcțiilor pentru distanțele L1, L2, cosinus, Mahalanobis, Jaccard și de editare
Alegerea metricii de distanță potrivite pentru o anumită sarcină de învățare automată și explicarea motivului pentru care alternativele eșuează
Stabilirea legăturii dintre normele L1 și L2, regularizările LASSO și Ridge și regiunile lor geometrice de constrângere
Demonstrarea modului în care același set de date produce vecini diferiți sub metrici diferite

Problema

Aveți doi vectori. Poate sunt reprezentări vectoriale ale unor cuvinte, profiluri de utilizatori sau tablouri de pixeli. Trebuie să aflați cât de apropiați sunt.

Răspunsul depinde în întregime de funcția de distanță aleasă. Două puncte de date pot fi cei mai apropiați vecini conform unei metrici și se pot afla la mare distanță conform alteia. Clasificatorul KNN, motorul de recomandare, baza de date vectorială, algoritmul de clusterizare și funcția de pierdere depind toate de această alegere. Dacă greșiți, modelul va optimiza un obiectiv nepotrivit.

Nu există o distanță universal optimă. L2 este potrivită pentru date spațiale. Similaritatea cosinus domină în NLP. Jaccard tratează mulțimi. Distanța de editare tratează șiruri. Mahalanobis ține cont de corelații. Wasserstein transportă masa de probabilitate. Fiecare codifică o altă ipoteză despre semnificația noțiunii de „similar”.

Această lecție construiește de la zero toate funcțiile importante de distanță, arată când este potrivită fiecare și demonstrează că aceleași date produc vecini complet diferiți în funcție de metrica folosită.

Conceptul

Norme: măsurarea mărimii unui vector

O normă măsoară „mărimea” unui vector. Orice funcție de distanță dintre doi vectori poate fi scrisă ca norma diferenței lor: d(a, b) = ||a - b||. Prin urmare, înțelegerea normelor înseamnă înțelegerea distanțelor.

Notă tehnică a traducerii: Afirmația precedentă din original este valabilă numai pentru distanțele induse de norme. Nu orice distanță are forma ||a-b||; distanța cosinus, distanța Jaccard, distanța de editare și distanța Wasserstein sunt contraexemple.

Norma L1 (distanța Manhattan)

Norma L1 însumează valorile absolute ale tuturor componentelor.

||x||_1 = |x_1| + |x_2| + ... + |x_n|

Se numește distanță Manhattan deoarece măsoară cât parcurgeți pe grila stradală a unui oraș în care vă puteți deplasa numai de-a lungul axelor, nu și pe diagonală.

Punctul A = (1, 1)
Punctul B = (4, 5)

Distanța L1 = |4-1| + |5-1| = 3 + 4 = 7

Pe o grilă, parcurgeți 3 blocuri spre est și 4 blocuri spre nord.

Când să folosiți L1:

Date rare și cu multe dimensiuni, precum caracteristici textuale și codificări one-hot
Când doriți o sensibilitate mai mică la valori aberante decât în cazul penalizărilor pătratice: contribuția fiecărei diferențe crește liniar, deși o diferență foarte mare poate domina în continuare suma
Probleme de selectare a caracteristicilor: regularizarea L1 favorizează raritatea

Legătura cu regularizarea L1 (LASSO): adăugarea termenului ||w||_1 la funcția de pierdere penalizează suma valorilor absolute ale ponderilor. Astfel, ponderile mici sunt împinse exact la zero și se realizează automat selectarea caracteristicilor. Penalizarea L1 creează regiuni de constrângere în formă de romb în spațiul ponderilor, iar colțurile romburilor se află pe axele unde unele ponderi sunt zero.

Legătura cu funcțiile de pierdere: eroarea absolută medie (Mean Absolute Error, MAE) este distanța L1 medie dintre predicții și ținte. Penalizează liniar toate erorile, ceea ce o face mai robustă la valori aberante decât MSE.

Norma L2 (distanța euclidiană)

Norma L2 este distanța în linie dreaptă: rădăcina pătrată a sumei pătratelor componentelor.

||x||_2 = sqrt(x_1^2 + x_2^2 + ... + x_n^2)

Este distanța învățată la geometrie: teorema lui Pitagora în n dimensiuni.

Punctul A = (1, 1)
Punctul B = (4, 5)

Distanța L2 = sqrt((4-1)^2 + (5-1)^2) = sqrt(9 + 16) = sqrt(25) = 5.0

Linia dreaptă traversează grila pe diagonală.

Când să folosiți L2:

Date continue cu un număr mic sau mediu de dimensiuni
Când scările caracteristicilor sunt comparabile
Distanțe fizice, precum date spațiale și citiri ale senzorilor
Similaritatea imaginilor la nivelul pixelilor

Legătura cu regularizarea L2 (Ridge): adăugarea termenului ||w||_2^2 la funcția de pierdere penalizează ponderile mari. Spre deosebire de L1, nu împinge ponderile la zero, ci le micșorează proporțional pe toate spre zero. Penalizarea L2 creează regiuni de constrângere circulare, fără colțuri pe axe. Ponderile devin mici, dar rareori ajung exact la zero.

Legătura cu funcțiile de pierdere: pentru un vector de reziduuri cu d componente, eroarea pătratică medie (Mean Squared Error, MSE) este ||y - y_hat||_2^2 / d. Ridicarea la pătrat penalizează erorile mari mai puternic decât pe cele mici.

Notă tehnică a traducerii: Originalul numește MSE „media pătratelor distanțelor L2”. Pentru un singur vector de reziduuri, relația exactă include împărțirea pătratului normei L2 la numărul componentelor.

MAE (pierderea L1): |y - y_hat|       Penalizare liniară. Robustă la valori aberante.
MSE (pierderea L2): (y - y_hat)^2     Penalizare pătratică. Sensibilă la valori aberante.

Normele Lp: familia generală

L1 și L2 sunt cazuri particulare ale normei Lp:

||x||_p = (|x_1|^p + |x_2|^p + ... + |x_n|^p)^(1/p)

Pentru p >= 1, valorile diferite ale lui p produc „bile unitate” cu forme diferite, adică mulțimi ale punctelor aflate la o distanță cel mult egală cu 1 față de origine:

Notă tehnică a traducerii: Originalul definește aici incorect bila unitate drept mulțimea punctelor cu norma exact 1. Bila unitate este mulțimea ||x|| <= 1; mulțimea ||x|| = 1 este sfera unitate, adică frontiera bilei.

p=1:    Formă de romb       (colțuri pe axe)
p=2:    Cerc/sferă          (forma rotundă obișnuită)
p=3:    Superelipsă         (pătrat cu colțuri rotunjite)
p=inf:  Pătrat/hipercub     (laturi plate de-a lungul axelor)

Norma L-infinit (distanța Cebîșev)

Când p tinde la infinit, norma Lp converge către valoarea absolută maximă a componentelor.

||x||_inf = max(|x_1|, |x_2|, ..., |x_n|)

Distanța dintre două puncte este determinată de singura dimensiune pe care diferența este maximă. Toate celelalte dimensiuni sunt ignorate.

Punctul A = (1, 1)
Punctul B = (4, 5)

Distanța L-inf = max(|4-1|, |5-1|) = max(3, 4) = 4

Când să folosiți L-infinit:

Când contează cea mai nefavorabilă abatere pe oricare dintre dimensiuni
Table de joc: regele din șah se deplasează conform distanței L-infinit, deoarece un pas în orice direcție are costul 1
Toleranțe de fabricație: fiecare dimensiune trebuie să respecte specificațiile

Similaritatea cosinus și distanța cosinus

Similaritatea cosinus măsoară unghiul dintre doi vectori, ignorând mărimile lor.

cos_sim(a, b) = (a . b) / (||a||_2 * ||b||_2)

Valoarea sa variază între -1 pentru direcții opuse și +1 pentru aceeași direcție. Vectorii perpendiculari au similaritatea cosinus 0.

Disimilaritatea numită uzual „distanță cosinus” este cosine_distance = 1 - cosine_similarity. Pentru vectori nenuli, valoarea sa variază de la 0 pentru direcții identice la 2 pentru direcții opuse. În general, această funcție nu este o metrică, deoarece poate încălca inegalitatea triunghiului; pentru un vector nul, similaritatea cosinus nu este definită.

Notă tehnică a traducerii: Originalul prezintă 1 - cosine_similarity drept distanță fără să precizeze că nu este o metrică matematică în general și că formula cosinus nu este definită pentru vectorul nul.

a = (1, 0)    b = (1, 1)

cos_sim = (1*1 + 0*1) / (1 * sqrt(2)) = 1/sqrt(2) = 0.707
cos_dist = 1 - 0.707 = 0.293

De ce similaritatea cosinus domină în NLP și în lucrul cu reprezentări vectoriale: în texte, lungimea documentului nu trebuie să influențeze similaritatea. Un document despre pisici de două ori mai lung decât un alt document despre pisici trebuie considerat în continuare „similar”. Similaritatea cosinus ignoră mărimea, adică lungimea, și ține cont numai de direcție. Două documente cu aceeași distribuție a cuvintelor, dar cu lungimi diferite, indică aceeași direcție și obțin similaritatea cosinus 1.0.

Când să folosiți similaritatea cosinus:

Similaritatea textelor: vectori TF-IDF, reprezentări vectoriale ale cuvintelor sau propozițiilor
Orice domeniu în care mărimea este zgomot, iar direcția reprezintă semnalul
Sisteme de recomandare: vectori de preferințe ale utilizatorilor
Căutare în spațiul reprezentărilor vectoriale: bazele de date vectoriale folosesc aproape întotdeauna similaritatea cosinus sau produsul scalar

Similaritatea prin produs scalar și similaritatea cosinus

Produsul scalar al doi vectori este:

a . b = a_1*b_1 + a_2*b_2 + ... + a_n*b_n
      = ||a|| * ||b|| * cos(unghi)

Similaritatea cosinus este produsul scalar normalizat prin mărimile ambilor vectori. Când ambii vectori sunt deja normalizați la normă unitară, adică au mărimea 1, produsul scalar și similaritatea cosinus coincid.

Dacă ||a|| = 1 și ||b|| = 1:
    a . b = cos(unghiul dintre a și b)

Diferența apare deoarece produsul scalar include informația despre mărime. Un vector cu o mărime mai mare obține un scor mai mare al produsului scalar. Acest lucru contează în unele sisteme de regăsire în care doriți ca elementele „populare” să fie clasate mai sus. Mărimea are rolul unui semnal implicit de calitate sau importanță.

a = (3, 0)    b = (1, 0)    c = (0, 1)

produs_scalar(a, b) = 3     produs_scalar(a, c) = 0
cos(a, b) = 1.0   cos(a, c) = 0.0

Ambele coincid în privința direcției, dar produsul scalar reflectă și mărimea.

În practică:

Folosiți similaritatea cosinus dacă doriți numai similaritatea direcțională
Folosiți produsul scalar când mărimile conțin informație relevantă
Numeroase baze de date vectoriale, precum Pinecone, Weaviate și Qdrant, vă permit să alegeți între ele
Dacă reprezentările vectoriale sunt normalizate L2, alegerea nu contează

Distanța Mahalanobis

Distanța euclidiană tratează toate dimensiunile în mod egal. Însă, dacă unele caracteristici sunt corelate sau au scări diferite, L2 produce rezultate înșelătoare.

Distanța Mahalanobis ține cont de structura de covarianță a datelor.

d_M(x, y) = sqrt((x - y)^T * S^(-1) * (x - y))

unde S este matricea de covarianță a datelor. Formula cu S^(-1) presupune că S este inversabilă și pozitiv definită. Dacă matricea este singulară sau slab condiționată, folosiți o estimare regularizată a covarianței ori o pseudoinversă, în funcție de problemă.

Notă tehnică a traducerii: Originalul nu menționează condiția de inversabilitate a matricei de covarianță. Aceasta poate eșua frecvent când numărul caracteristicilor este mare în raport cu numărul observațiilor sau când există dependențe liniare.

Intuitiv, distanța Mahalanobis decorelează și normalizează mai întâi datele, prin procedeul de albire (whitening), apoi calculează distanța L2 în spațiul transformat. Dacă S este matricea unitate, adică caracteristicile sunt necorelate și au varianță unitară, distanța Mahalanobis se reduce la distanța euclidiană.

Exemplu: înălțimea și greutatea sunt corelate.
O persoană cu înălțimea 6'2" și greutatea 180 lb nu este neobișnuită.
O persoană cu înălțimea 5'0" și greutatea 180 lb este neobișnuită.

Distanța euclidiană le poate considera la aceeași distanță de medie.
Distanța Mahalanobis identifică în mod corect a doua persoană drept un punct atipic,
deoarece ține cont de corelația dintre înălțime și greutate.

Când să folosiți distanța Mahalanobis:

Detectarea punctelor atipice: punctele aflate la o distanță Mahalanobis mare față de medie sunt atipice
Clasificare în cazul caracteristicilor cu scări și corelații diferite
Când aveți suficiente date pentru a estima o matrice de covarianță fiabilă
Controlul calității în fabricație: monitorizarea multivariată a proceselor

Similaritatea Jaccard (pentru mulțimi)

Similaritatea Jaccard măsoară suprapunerea dintre două mulțimi.

J(A, B) = |A intersecție B| / |A reuniune B|

Valoarea variază de la 0 pentru mulțimi fără elemente comune la 1 pentru mulțimi identice. Distanța Jaccard = 1 - similaritatea Jaccard.

A = {pisică, câine, pește}
B = {pisică, pasăre, pește, șarpe}

Intersecție = {pisică, pește}               mărime = 2
Reuniune = {pisică, câine, pește, pasăre, șarpe}  mărime = 5

Similaritatea Jaccard = 2/5 = 0.4
Distanța Jaccard = 0.6

Când să folosiți Jaccard:

Compararea mulțimilor de etichete, categorii sau caracteristici
Similaritatea documentelor pe baza prezenței cuvintelor, nu a frecvenței lor
Detectarea duplicatelor aproximative prin aproximarea Jaccard cu MinHash
Compararea vectorilor de caracteristici binare, care reprezintă prezența sau absența
Evaluarea modelelor de segmentare: Intersection over Union este indicele Jaccard

Distanța de editare (distanța Levenshtein)

Distanța de editare reprezintă numărul minim de operații asupra unui singur caracter necesare pentru transformarea unui șir în altul. Operațiile sunt inserarea, ștergerea și substituirea.

„kitten” -> „sitting”

kitten -> sitten  (substituiți k cu s)
sitten -> sittin  (substituiți e cu i)
sittin -> sitting (inserați g)

Distanța de editare = 3

Se calculează prin programare dinamică. Completați o matrice în care elementul (i, j) este distanța de editare dintre primele i caractere ale șirului A și primele j caractere ale șirului B.

        ""  s  i  t  t  i  n  g
    ""   0  1  2  3  4  5  6  7
    k    1  1  2  3  4  5  6  7
    i    2  2  1  2  3  4  5  6
    t    3  3  2  1  2  3  4  5
    t    4  4  3  2  1  2  3  4
    e    5  5  4  3  2  2  3  4
    n    6  6  5  4  3  3  2  3

Când să folosiți distanța de editare:

Verificarea și corectarea ortografică
Alinierea secvențelor de ADN, cu operații ponderate
Potrivirea aproximativă a șirurilor
Deduplicarea datelor textuale neuniforme

Divergența KL (nu este o distanță, dar este folosită ca atare)

Divergența KL măsoară diferența dintre două distribuții de probabilitate. A fost prezentată în lecția 09, dar este inclusă aici deoarece oamenii o folosesc drept „distanță”, deși nu este una.

D_KL(P || Q) = sum(p(x) * log(p(x) / q(x)))

Proprietate esențială: divergența KL NU este simetrică.

D_KL(P || Q) != D_KL(Q || P)

Prin urmare, nu îndeplinește cerința de bază a unei metrici de distanță. De asemenea, nu respectă inegalitatea triunghiului. Este o divergență, nu o distanță.

În anumite probleme de aproximare, minimizarea divergenței KL directe D_KL(P || Q) tinde să penalizeze sever regiunile în care P are masă, iar Q nu, ceea ce poate favoriza acoperirea mai multor moduri. Minimizarea divergenței inverse D_KL(Q || P) poate favoriza concentrarea pe un singur mod. Aceste descrieri sunt euristice și depind de familia lui Q, de suporturi și de argumentul optimizat.

Notă tehnică a traducerii: Originalul prezintă etichetele „mean-seeking” și „mode-seeking” drept proprietăți necondiționate ale celor două orientări KL. Comportamentul apare în contexte de aproximare specifice și nu constituie o regulă universală.

Unde întâlniți divergența KL:

VAE-uri: termenul KL din ELBO împinge distribuția latentă spre o distribuție a priori
Distilarea cunoștințelor: modelul elev încearcă să reproducă distribuția modelului profesor
RLHF: penalizarea KL menține modelul ajustat fin aproape de modelul de bază
Metode bazate pe gradientul politicii: constrângerea actualizărilor politicii

Distanța Wasserstein (distanța transportului de masă)

Distanța Wasserstein măsoară „efortul” minim necesar pentru transformarea unei distribuții de probabilitate în alta. Imaginați-vă că o distribuție este o grămadă de pământ, iar cealaltă este o groapă: cât pământ trebuie să mutați și pe ce distanță?

W(P, Q) = infimumul valorii E[d(x, y)] pentru toate planurile de transport gamma

Pentru distribuții unidimensionale, formula se simplifică la integrala diferenței absolute dintre funcțiile de repartiție:

W_1(P, Q) = integrala |CDF_P(x) - CDF_Q(x)| dx

De ce contează distanța Wasserstein:

Este o metrică propriu-zisă: este simetrică și respectă inegalitatea triunghiului
Rămâne finită pentru numeroase distribuții fără suprapunere și poate oferi un obiectiv cu o geometrie mai utilă; existența unui gradient util față de parametrii modelului depinde însă de parametrizare și de regularitate
Această proprietate a făcut-o esențială pentru rețelele Wasserstein GAN (WGAN), care au rezolvat instabilitatea antrenării GAN-urilor originale

Notă tehnică a traducerii: Formularea „au rezolvat instabilitatea” din original este prea categorică. Obiectivul Wasserstein și variantele precum WGAN-GP pot ameliora stabilitatea antrenării, dar nu garantează eliminarea tuturor instabilităților.

Notă tehnică a traducerii: Originalul afirmă necondiționat că distanța Wasserstein „oferă gradienți” pentru distribuții fără suprapunere. Faptul că distanța rămâne informativă la nivelul distribuțiilor nu garantează automat un gradient nenul și util prin orice parametrizare a generatorului.

Distribuții fără suprapunere:

P: [1, 0, 0, 0, 0]    Q: [0, 0, 0, 0, 1]

Divergența KL: infinit (logaritm din zero)
Wasserstein: 4 (transportați întreaga masă peste 4 intervale)

Wasserstein oferă aici o valoare finită și informativă. Divergența KL este infinită.

Când să folosiți Wasserstein:

Antrenarea GAN-urilor: WGAN, WGAN-GP
Compararea distribuțiilor care s-ar putea să nu se suprapună
Probleme de transport optim
Regăsirea imaginilor prin compararea histogramelor de culori

De ce sarcinile diferite necesită distanțe diferite

Sarcină	Distanța optimă	Motiv
Similaritatea textelor	Cosinus	Mărimea este zgomot, direcția exprimă sensul
Compararea pixelilor imaginilor	L2	Relațiile spațiale contează, iar caracteristicile au scări comparabile
Caracteristici rare cu multe dimensiuni	L1	Este robustă și nu amplifică diferențele mari rare
Suprapunerea mulțimilor (etichete, categorii)	Jaccard	Datele sunt în mod natural mulțimi, nu vectori
Potrivirea șirurilor	Distanță de editare	Operațiile corespund intuiției umane despre editare
Detectarea punctelor atipice	Mahalanobis	Ține cont de corelațiile și scările caracteristicilor
Compararea distribuțiilor	Divergență KL	Măsoară informația pierdută prin folosirea lui Q în locul lui P
Antrenarea GAN-urilor	Wasserstein	Oferă gradienți chiar dacă distribuțiile nu se suprapun
Reprezentări vectoriale (baze de date vectoriale)	Cosinus sau produs scalar	Reprezentările sunt antrenate să codifice sensul în direcție
Recomandări	Produs scalar	Mărimea poate codifica popularitatea sau gradul de încredere
Secvențe ADN	Distanță de editare ponderată	Costul substituției variază în funcție de perechea de nucleotide
Controlul calității în fabricație	L-infinit	Contează cea mai nefavorabilă abatere pe oricare dimensiune

Notă tehnică a traducerii: În tabelul original, motivarea distanței L2 pentru pixeli prin faptul că „relațiile spațiale contează” este imprecisă. Distanța L2 la nivel de pixeli compară poziții corespunzătoare și este utilă mai ales pentru imagini aliniate; nu modelează singură similaritatea spațială sau perceptuală.

Legătura cu funcțiile de pierdere

Unele funcții de pierdere provin din norme, distanțe sau divergențe aplicate predicțiilor și țintelor, dar nu toate sunt distanțe matematice.

Notă tehnică a traducerii: Afirmația originalului este o simplificare intuitivă, nu o definiție matematică. Unele funcții de pierdere provin din norme sau distanțe, dar entropia încrucișată și divergența KL nu sunt metrici, iar hinge loss este o funcție surogat bazată pe marjă.

Funcție de pierdere   Construcție uzuală                 Comportament
MSE                   Eroare L2 la pătrat                Penalizează puternic erorile mari
MAE                   Eroare L1                          Penalizează liniar erorile
Pierderea Huber       L1 pentru erori mari,              Combină avantajele: robustețe la valori aberante,
                      L2 pentru erori mici               gradient neted în apropierea lui zero
Entropie încrucișată  Log-verosimilitate / divergență KL Măsoară nepotrivirea distribuțiilor
Pierdere hinge        max(0, 1 - y*f(x))                 Penalizează încălcarea marjei în clasificarea binară
Pierdere triplet      Distanțe L2 (de obicei)            Apropie exemplele pozitive și îndepărtează
                                                           exemplele negative
Pierdere contrastivă  Distanțe L2                        Apropie perechile similare și menține perechile
                                                           diferite dincolo de marjă

Legătura cu regularizarea

Regularizarea adaugă la funcția de pierdere o penalizare bazată pe norma ponderilor.

Regularizare L1 (LASSO):   pierdere + lambda * ||w||_1
  -> Ponderi rare. Unele ponderi devin exact zero.
  -> Selectare automată a caracteristicilor.
  -> Soluția are colțuri (nu este derivabilă în zero).

Regularizare L2 (Ridge):   pierdere + lambda * ||w||_2^2
  -> Ponderi mici. Toate ponderile se micșorează spre zero.
  -> Fără selectarea caracteristicilor (nimic nu ajunge exact la zero).
  -> Soluție netedă peste tot.

Elastic Net:               pierdere + lambda_1 * ||w||_1 + lambda_2 * ||w||_2^2
  -> Combină raritatea L1 cu stabilitatea L2.
  -> Grupurile de caracteristici corelate sunt păstrate sau eliminate împreună.

Notă tehnică a traducerii: Efectul de grupare al Elastic Net este o tendință favorizată de penalizare, nu o garanție că toate caracteristicile corelate vor fi întotdeauna păstrate sau eliminate împreună; rezultatul depinde de date și de hiperparametri.

De ce L1 produce raritate, dar L2 nu: imaginați-vă regiunea de constrângere în spațiul bidimensional al ponderilor. L1 este un romb, iar L2 este un cerc. Pentru o funcție de pierdere cuadratică cu contururi eliptice, primul contact cu rombul apare frecvent într-un colț, unde una dintre ponderi este zero. Contactul cu cercul apare de obicei într-un punct neted, unde ambele ponderi sunt nenule.

Notă tehnică a traducerii: Originalul afirmă generic că toate contururile funcției de pierdere sunt elipse. Această geometrie este o ilustrare pentru obiective cuadratice; alte funcții de pierdere pot avea contururi diferite, deși mecanismul colțurilor penalizării L1 rămâne relevant.

Căutarea celor mai apropiați vecini

Fiecare funcție de distanță implică o problemă de căutare a celor mai apropiați vecini: pentru un punct de interogare, găsiți cele mai apropiate puncte dintr-un set de date.

Căutarea exactă a celui mai apropiat vecin are complexitatea O(n * d) pentru fiecare interogare într-un set cu n puncte și d dimensiuni. Pentru seturile de date mari, este prea lentă.

Algoritmii de căutare aproximativă a celor mai apropiați vecini (Approximate Nearest Neighbor, ANN) sacrifică puțin din acuratețe pentru creșteri foarte mari de viteză:

Algoritm          Abordare                         Folosit de
Arbori KD         Partiționarea spațiului          scikit-learn (puține dim.)
                  aliniată cu axele
Arbori ball       Hipersfere imbricate             scikit-learn (număr mediu de dim.)
LSH               Proiecții hash aleatorii         Detectarea duplicatelor aproximative
HNSW              Graf ierarhic navigabil          FAISS, Qdrant, Weaviate
                  de tip „lume mică”
IVF               Index inversat cu                FAISS (miliarde de elemente)
                  căutare bazată pe clustere
Cuantizare de     Comprimă vectorii și caută       FAISS (memorie limitată)
produs            în spațiul comprimat

HNSW (Hierarchical Navigable Small World) este unul dintre algoritmii folosiți frecvent în bazele de date vectoriale moderne. Construiește un graf cu mai multe niveluri, în care fiecare nod este conectat la vecinii săi aproximativi. Căutarea începe la nivelul superior, rar și cu salturi lungi, apoi coboară la nivelul inferior, dens și cu salturi scurte.

Notă tehnică a traducerii: Originalul numește HNSW „algoritmul dominant”. Aceasta este o caracterizare dependentă de moment și de produs; traducerea păstrează afirmația mai verificabilă că HNSW este utilizat pe scară largă.

norm-unit-balls

Construirea implementării

Pasul 1: toate funcțiile de normă și distanță

Consultați code/distances.py pentru implementarea completă. Fiecare funcție este construită de la zero folosind numai operații matematice Python de bază.

Pasul 2: aceleași date, distanțe și vecini diferiți

Demonstrația din distances.py creează un set de date, alege un punct de interogare și arată cum se schimbă cel mai apropiat vecin în funcție de metrica de distanță. Punctul „cel mai apropiat” conform L1 poate să nu fie cel mai apropiat conform L2 sau similarității cosinus.

Pasul 3: căutarea după similaritatea reprezentărilor vectoriale

Codul include o simulare a căutării după similaritatea reprezentărilor vectoriale, care găsește „documentele” cele mai asemănătoare unei interogări prin similaritatea cosinus și distanța L2, arătând că ierarhiile pot fi diferite.

Utilizarea implementării

Cea mai frecventă utilizare practică este găsirea elementelor similare într-o bază de date vectorială.

import numpy as np

def cosine_similarity_matrix(X):
    norms = np.linalg.norm(X, axis=1, keepdims=True)
    norms = np.where(norms == 0, 1, norms)
    X_normalized = X / norms
    return X_normalized @ X_normalized.T

embeddings = np.random.randn(1000, 768)

sim_matrix = cosine_similarity_matrix(embeddings)

query_idx = 0
similarities = sim_matrix[query_idx]
top_k = np.argsort(similarities)[::-1][1:6]
print(f"Top 5 most similar to item 0: {top_k}")
print(f"Similarities: {similarities[top_k]}")

Când apelați model.encode(text) și apoi căutați într-o bază de date vectorială, în interior se petrece acest proces. Modelul de reprezentare transformă textul în vectori. Baza de date vectorială caută vectorii stocați cu similaritate cosinus sau produs scalar maximă față de vectorul interogării și folosește algoritmi ANN pentru a evita verificarea tuturor elementelor.

Exerciții

Calculați distanțele L1, L2 și L-infinit dintre (1, 2, 3) și (4, 0, 6). Verificați dacă relația L-inf <= L2 <= L1 se respectă întotdeauna pentru orice pereche de puncte. Demonstrați de ce această ordine este garantată.
Creați doi vectori pentru care similaritatea cosinus este ridicată (> 0.9), dar distanța L2 este mare (> 10). Explicați geometric ce se întâmplă. Apoi creați doi vectori pentru care similaritatea cosinus este scăzută (< 0.3), dar distanța L2 este mică (< 0.5).
Implementați o funcție care primește un set de date și un punct de interogare și returnează cel mai apropiat vecin conform distanțelor L1, L2, cosinus și Mahalanobis. Găsiți un set de date pentru care toate cele patru metrici indică puncte diferite drept cel mai apropiat vecin.
Calculați manual, prin metoda CDF, distanța Wasserstein dintre [0.5, 0.5, 0, 0] și [0, 0, 0.5, 0.5]. Apoi calculați-o între [0.25, 0.25, 0.25, 0.25] și [0, 0, 0.5, 0.5]. Care valoare este mai mare și de ce?
Implementați MinHash pentru aproximarea similarității Jaccard. Generați 100 de mulțimi aleatorii, calculați valoarea Jaccard exactă pentru toate perechile și comparați-o cu aproximarea MinHash bazată pe 50, 100 și 200 de funcții hash. Reprezentați grafic eroarea de aproximare.

Termeni-cheie

Termen	Formulare uzuală	Ce înseamnă de fapt
Normă	„Mărimea unui vector”	O funcție care asociază unui vector un scalar nenegativ, respectă inegalitatea triunghiului și omogenitatea absolută și este zero numai pentru vectorul nul.
Norma L1	„Distanța Manhattan”	Suma valorilor absolute ale componentelor. Produce raritate în optimizare și este mai puțin sensibilă la valori aberante decât o penalizare pătratică, fără a fi imună la acestea.
Norma L2	„Distanța euclidiană”	Rădăcina pătrată a sumei pătratelor componentelor. Distanța în linie dreaptă din spațiul euclidian.
Norma Lp	„Normă generalizată”	Rădăcina de ordin p a sumei puterilor p ale valorilor absolute ale componentelor. L1 și L2 sunt cazuri particulare.
Norma L-infinit	„Norma maxim” sau „distanța Cebîșev”	Valoarea absolută maximă a componentelor. Limita normei Lp când p tinde la infinit.
Similaritate cosinus	„Unghiul dintre vectori”	Produsul scalar normalizat prin mărimile ambilor vectori. Variază de la -1 la +1 și ignoră lungimea vectorilor.
Distanță cosinus	„1 minus similaritatea cosinus”	Disimilaritate între 0 și 2 pentru vectori nenuli; în general nu este o metrică deoarece poate încălca inegalitatea triunghiului.
Produs scalar	„Cosinus nenormalizat”	Suma produselor componentelor corespunzătoare. Este egal cu similaritatea cosinus înmulțită cu mărimile ambilor vectori.
Distanță Mahalanobis	„Distanță care ține cont de corelații”	Distanța L2 într-un spațiu albit, adică decorelat și normalizat, folosind matricea de covarianță a datelor.
Similaritate Jaccard	„Suprapunerea mulțimilor”	Mărimea intersecției împărțită la mărimea reuniunii. Se aplică mulțimilor, nu vectorilor.
Distanță de editare	„Distanță Levenshtein”	Numărul minim de inserări, ștergeri și substituiri necesare pentru transformarea unui șir în altul.
Divergență KL	„Distanța dintre distribuții”	Nu este o distanță propriu-zisă, deoarece nu este simetrică. Măsoară biții suplimentari necesari când Q este folosită pentru codificarea lui P.
Distanță Wasserstein	„Distanța transportului de masă”	Efortul minim necesar pentru transportarea masei dintr-o distribuție în alta. Este o metrică propriu-zisă.
Cel mai apropiat vecin aproximativ	„Căutare ANN”	Algoritmi precum HNSW, LSH și IVF, care găsesc puncte aproximativ cele mai apropiate mult mai rapid decât căutarea exactă.
HNSW	„Algoritmul bazelor de date vectoriale”	Graf Hierarchical Navigable Small World. Un graf cu mai multe niveluri pentru căutarea rapidă și aproximativă a celor mai apropiați vecini.
Regularizare L1	„LASSO”	Adăugarea normei L1 a ponderilor la funcția de pierdere. Împinge ponderile la zero și produce raritate.
Regularizare L2	„Ridge” sau „degradarea ponderilor” (weight decay)	Adăugarea pătratului normei L2 a ponderilor la funcția de pierdere. Micșorează ponderile spre zero fără a produce raritate.
Elastic Net	„L1 + L2”	Combină regularizarea L1 și L2. Tratează grupurile de caracteristici corelate mai bine decât fiecare metodă separat.

Lecturi suplimentare

FAISS: A Library for Efficient Similarity Search - biblioteca Meta pentru căutări ANN la scara miliardelor de elemente
Wasserstein GAN (Arjovsky et al., 2017) - lucrarea care a introdus distanța transportului de masă în GAN-uri
Locality-Sensitive Hashing (Indyk & Motwani, 1998) - algoritmul fundamental pentru ANN
Efficient Estimation of Word Representations (Mikolov et al., 2013) - Word2Vec, unde similaritatea cosinus a devenit alegerea implicită pentru reprezentările vectoriale
Documentația sklearn.neighbors - ghid practic pentru metricile de distanță și algoritmii de vecinătate din scikit-learn

Sursă: Norms and Distances — original

Navigare: înapoi: 01.13 — Stabilitate numerică · Faza 1 — Fundamente matematice · Catalog complet · în continuare: 01.15 — Statistică pentru învățarea automată.