Laplacianul explicat: de la calcul diferențial la ML

Laplacianul apare în algoritmi bazați pe grafuri, fluxuri de procesare a imaginilor și clusterizare spectrală. Așadar, dacă dezvoltați modele care lucrează cu grafuri, imagini sau date de dimensiune mare, Laplacianul nu este doar „matematică de fundal” opțională. Este componenta care face cu adevărat treaba în culise.

În acest articol, voi acoperi Laplacianul de la bază: matematica din spatele lui, intuiția geometrică, Laplacianul pe graf și forma sa matricială, precum și modul în care este folosit în aplicații reale de machine learning.

Aveți nevoie de o introducere practică în ecuațiile diferențiale? Citiți articolul nostru recent pentru a parcurge drumul de la elemente de bază la aplicații practice în machine learning.

Ce este Laplacianul?

Laplacianul este un operator diferențial de ordinul al doilea. Vă spune cum se curbează o funcție într-un punct dat.

Îl veți vedea uneori descris ca divergența gradientului.

Și acesta este cheia pentru a înțelege ce face efectiv operatorul:

• Gradientul vă indică direcția în care o funcție crește cel mai rapid
• Divergența măsoară dacă acel flux se împrăștie sau se adună.

Combinate, Laplacianul vă spune dacă un punct este un vârf local, o vale locală sau o zonă plată între ele.

Pe scurt, Laplacianul măsoară cât de mult diferă valoarea unei funcții într-un punct față de media valorilor vecinilor. Dacă Laplacianul este zero, funcția este „echilibrată” local. Valoare pozitivă înseamnă că punctul este sub împrejurimi. Valoare negativă înseamnă că este deasupra lor.

Formula

În 2D, pentru o funcție f(x, y):

Formula Laplacianului în 2D

În 3D, pentru o funcție f(x, y, z):

Formula Laplacianului în 3D

Modelul se păstrează în orice număr de dimensiuni – sumați derivatele parțiale de ordinul al doilea pe fiecare axă. Acest lucru face ca Laplacianul să fie o potrivire excelentă pentru date de înaltă dimensionalitate, motiv pentru care apare atât de des în machine learning.

Formula Laplacianului în calculul multivariat

Formula Laplacianului este mai scurtă decât v-ați aștepta pentru ceva ce apare în atâtea zone ale machine learningului.

În 3D, pentru o funcție f(x, y, z), arată astfel:

Formula Laplacianului în 3D

Atât. Sumați derivatele parțiale de ordinul al doilea pe fiecare dimensiune.

Fiecare termen pune aceeași întrebare de-a lungul axei sale: funcția se curbează în sus, în jos sau e plată? Când adunați aceste răspunsuri, obțineți un singur număr care descrie curbura totală în acel punct.

De la 3D la n dimensiuni

Formula se generalizează la n dimensiuni. Aceasta este formula generică pentru o funcție cu n dimensiuni de intrare:

Generalizarea formulei Laplacianului

De aceea Laplacianul funcționează bine în machine learning, unde datele trăiesc adesea în sute sau mii de dimensiuni. Operatorul doar însumează curbura pe fiecare dimensiune.

Conexiunea cu optimizarea

Dacă ați lucrat cu gradient descent, vă gândiți deja la derivate de ordinul întâi – în ce direcție e panta descendentă? Laplacianul vă duce cu un pas mai departe.

Derivatele de ordinul al doilea vă vorbesc despre forma acelui deal.

Un Laplacian mare și pozitiv într-un punct înseamnă că funcția se curbează accentuat în sus în toate direcțiile – sunteți aproape de un minim. O valoare mare negativă înseamnă că sunteți aproape de un maxim. Aproape de zero înseamnă că suprafața este local plată.

Această informație despre curbură contează în metodele de optimizare de ordinul al doilea, care o folosesc pentru a face pași mai inteligenți decât gradient descent simplu. Laplacianul este o modalitate de a rezuma această curbură într-o singură valoare scalară.

Intuiție geometrică: ce măsoară Laplacianul

Semnul Laplacianului într-un punct vă spune forma funcției în jurul lui.

• Dacă ∇²f > 0 într-un punct, funcția se curbează în sus în toate direcțiile. Punctul este mai jos decât împrejurimile. Aceasta este convexitate.

• Dacă ∇²f < 0, funcția se curbează în jos. Punctul este mai sus decât împrejurimile. Aceasta este concavitate.

• Dacă ∇²f = 0, funcția este local plată. Fără curbură netă în nicio direcție.

Aceasta este versiunea multivariată a testului derivatelor de ordinul al doilea, pe care îl știți deja. În 1D, o a doua derivată pozitivă înseamnă un minim local, iar una negativă înseamnă un maxim local. Laplacianul extinde aceeași idee la orice număr de dimensiuni, însumând curbura pe toate axele.

Relația cu Hessianul

Matricea Hessiană surprinde imaginea completă a curburii. Este o matrice a tuturor derivatelor parțiale de ordinul al doilea, iar fiecare element descrie cum se curbează funcția de-a lungul unei perechi de axe.

Laplacianul este urma Hessianului – suma elementelor sale diagonale. În timp ce Hessianul vă oferă defalcarea completă a curburii, Laplacianul o comprimă într-un singur număr.

Acest compromis este important în machine learning. Hessianul complet este costisitor de calculat pentru modele de dimensionalitate mare – un model cu n parametri are un Hessian n × n. Laplacianul vă oferă un rezumat scalar ieftin al curburii, ușor de folosit.

De ce contează asta pentru machine learning

Când antrenați un model, navigați pe o suprafață de pierdere. Regiunile plate înseamnă învățare lentă. Zonele convexe pot duce la „overshoot” al optimizatorului. Laplacianul vă oferă rapid indicii despre care situație este în joc.

Metodele bazate pe grafuri folosesc Laplacianul pentru a măsura cât de lin se schimbă valorile pe nodurile unui graf. Este o extensie directă a aceleiași intuiții despre curbură din funcțiile continue aplicată structurilor discrete.

Laplacianul și optimizarea în machine learning

Gradient descent folosește doar derivate de ordinul întâi.

Gradientul vă spune în ce direcție să pășiți. Nu vă spune cât de mare ar trebui să fie pasul. Un gradient abrupt într-o vale lată și plată cere un pas mare. Același gradient abrupt lângă o muchie ascuțită cere un pas mic. Doar derivatele de ordinul întâi nu pot face diferența.

Aici intervin derivatele de ordinul al doilea.

Curbură și mărimea pasului

Curbura descrie cât de repede se schimbă chiar gradientul. Curbura mare înseamnă că suprafața pierderii se curbează accentuat – pași mici în spațiul parametrilor produc schimbări mari ale gradientului. Curbura mică înseamnă că suprafața e plată și gradientul se schimbă lent.

Dacă ignorați curbura și folosiți o rată de învățare fixă, ghiciți. Prea mare, și depășiți în regiunile cu curbură mare. Prea mică, și înaintați foarte lent în cele plate.

Metodele de optimizare de ordinul al doilea precum metoda lui Newton folosesc curbura pentru a seta automat mărimea pașilor. Ele împart gradientul la curbură, făcând pași mai mari unde suprafața e plată și mai mici unde e ascuțită.

Locul Laplacianului

Laplacianul este urma Hessianului – un scalar care rezumă curbura totală într-un punct. Nu surprinde imaginea completă așa cum o face Hessianul, dar este ieftin de calculat și util ca semnal.

Iată o explicație pe înțelesul tuturor a ceea ce trebuie să rețineți:

• Un Laplacian mare și pozitiv al pierderii într-un punct înseamnă că sunteți aproape de un minim local – pierderea se curbează în sus în toate direcțiile
• O valoare negativă înseamnă că sunteți aproape de un maxim
• Aproape de zero înseamnă o regiune plată sau de șa, unde gradient descent tinde exact să se blocheze

Stabilitate și regularizare

Curbura se leagă și de stabilitatea antrenării. Minimelor ascuțite – regiuni cu curbură mare – tind să generalizeze mai slab decât cele plate. Un model care converge într-un minim ascuțit este sensibil la schimbări mici ale intrării.

Unele tehnici de regularizare penalizează direct curbura pentru a împinge optimizarea spre regiuni mai plate ale suprafeței pierderii. Laplacianul apare și aici, ca o modalitate de a măsura și constrânge cât de brusc se schimbă predicțiile modelului în spațiul de intrare.

Înțelegerea curburii vă ajută să înțelegeți de ce optimizatorul se blochează, de ce rata de învățare contează atât de mult și de ce unele minime generalizează mai bine decât altele.

Laplacianul pe grafuri și matricea Laplaciană

Până acum, Laplacianul a trăit în lumea funcțiilor continue. Dar ce se întâmplă când datele nu sunt o suprafață netedă, ci un graf?

Aici intervine Laplacianul pe graf. Ia aceeași idee de bază – măsurarea diferenței dintre valoarea într-un punct și valorile vecinilor – și o aplică pe noduri și muchii.

Formula

Laplacianul pe graf L este definit ca:

Formula Laplacianului pe graf (simplificată)

Două matrici. Atât. Iată ce înseamnă fiecare.

Matricea de adiacență

Matricea de adiacență A codifică ce noduri sunt conectate. Pentru un graf cu n noduri, A este o matrice n × n în care A_ij = 1 dacă există o muchie între nodul i și nodul j, și 0 în caz contrar.

Pentru un graf simplu neorientat cu 3 noduri, unde nodul 1 se conectează la nodurile 2 și 3, dar 2 și 3 nu sunt conectate între ele:

Matricea de adiacență

Matricea gradelor

Matricea gradelor D este o matrice diagonală. Fiecare element diagonal D_ii este gradul nodului i – numărul de muchii conectate la el. Toate elementele extradiagonale sunt zero.

Aceasta este formula pentru același graf:

Matricea gradelor

Nodul 1 are gradul 2 (conectat la două noduri). Nodurile 2 și 3 au fiecare gradul 1.

Împreună

Scădeți A din D și obțineți L:

Scăderea matricii de adiacență din matricea gradelor

Fiecare element diagonal vă spune câte conexiuni are un nod. Fiecare element extradiagonal L_ij este -1 dacă nodurile i și j sunt conectate și 0 dacă nu sunt.

Dacă înmulțiți L cu un vector de valori atribuite fiecărui nod, rezultatul măsoară cât de mult diferă valoarea fiecărui nod de valorile vecinilor săi. Aceasta este versiunea discretă a aceleiași intuiții despre curbură de mai devreme – doar că aplicată pe un graf în loc de o suprafață continuă.

Ce vă spun valorile proprii despre un graf

Adevărata putere a lui L vine din valorile și vectorii proprii:

• Cea mai mică valoare proprie a lui L este întotdeauna 0. Vectorul propriu corespunzător este un vector constant – fiecare nod primește aceeași valoare. Are sens: o funcție constantă are „variație” zero pe graf.

• Numărul de valori proprii zero este egal cu numărul de componente conexe din graf. Dacă graful are trei clustere deconectate, L are trei valori proprii zero. Aceasta este o modalitate directă de a citi conectivitatea grafului dintr-o matrice.

• Valorile proprii mici, nenule, corespund vectorilor proprii care se schimbă lent pe graf – nodurile apropiate primesc valori similare. Valorile proprii mari corespund vectorilor proprii care oscilează rapid între noduri conectate.

Curiozitate: acest spectru de valori proprii dă numele metodelor spectrale.

Clusterizare spectrală și detecția comunităților

Clusterizarea spectrală folosește vectorii proprii ai lui L pentru a găsi clustere în date structurate ca graf. Ideea este că vectorii proprii asociați cu valori proprii mici atribuie valori similare nodurilor dens conectate și valori diferite celor slab conectate.

Pentru a găsi k clustere, luați k vectori proprii corespunzători celor mai mici k valori proprii nenule ale lui L, îi stivuiți într-o matrice și rulați k-means pe rânduri. Fiecare rând este un nod, iar poziția sa în acest spațiu de dimensiune mică reflectă vecinătatea sa în graf.

Funcționează pentru detecția comunităților în rețele sociale, clusterizarea documentelor, segmentarea imaginilor și oriunde datele au o structură naturală de graf. Două noduri strâns conectate ajung aproape unul de altul în spațiul vectorilor proprii. Două noduri din comunități diferite ajung departe unul de altul.

Laplacianul pe graf transformă o problemă combinatorică dificilă – găsiți clusterele din acest graf – într-o problemă de algebră liniară ușor de rezolvat.

Laplacianul în clusterizarea spectrală

Clusterizarea spectrală este locul în care Laplacianul pe graf trece de la matematică interesantă la un instrument ML practic.

Ideea de bază este că, în loc să grupați direct punctele brute de date, le grupați într-un spațiu definit de vectorii proprii ai lui L. Acel spațiu surprinde structura grafului, astfel încât puteți vedea care noduri sunt strâns conectate, care sunt slab conectate și care aparțin unor comunități separate.

Cum definesc vectorii proprii clusterele

Luați k vectori proprii corespunzători celor mai mici k valori proprii nenule ale lui L. Îi stivuiți ca și coloane într-o matrice. Fiecare rând al acelei matrici este un nod, acum reprezentat ca un punct într-un spațiu de dimensiune k.

Vectorii proprii asociați cu valori proprii mici se schimbă lent pe graf. Nodurile dens conectate ajung să aibă valori similare în acești vectori proprii – iar valori similare înseamnă rânduri similare – iar rândurile similare înseamnă că ajung aproape unele de altele în noul spațiu.

Laplacian ne-normalizat versus normalizat

În practică veți vedea două versiuni ale Laplacianului pe graf.

Laplacianul ne-normalizat este formula directă L = D - A. Funcționează bine când nodurile au grade aproximativ similare – adică majoritatea nodurilor au un număr similar de conexiuni

Laplacianul normalizat ajustează dezechilibrul de grad. Există câteva variante, dar cea mai comună este:

Formula Laplacianului normalizat

Aceasta rescalează contribuția fiecărui nod după gradul său. În grafurile din lumea reală – rețele sociale, grafuri web, rețele de citări – unele noduri au sute de conexiuni, iar altele doar una sau două. Fără normalizare, nodurile cu grad mare domină vectorii proprii și rezultatele clusterizării au de suferit.

Folosiți Laplacianul normalizat în mod implicit, cu excepția cazului în care știți că graful are o distribuție uniformă a gradelor.

Aplicații practice

Clusterizarea spectrală cu Laplacianul pe graf apare într-o gamă largă de sarcini de machine learning. Iată câteva:

• Segmentarea imaginilor – pixelii devin noduri, ponderile muchiilor codifică similaritatea, iar clusterele corespund regiunilor imaginii
• Clusterizarea documentelor – documentele devin noduri, muchiile codifică termeni comuni sau citări
• Analiza rețelelor sociale – utilizatorii devin noduri, muchiile codifică conexiuni, iar clusterele dezvăluie comunități
• Sisteme de recomandare – elementele sau utilizatorii formează un graf, iar metodele spectrale găsesc grupuri cu comportament similar

Ori de câte ori datele au o structură naturală de graf, sau puteți construi una din similarități pereche, clusterizarea spectrală oferă o modalitate riguroasă de a găsi grupuri pe care metodele bazate strict pe distanță le ratează.

Laplacianul în procesarea imaginilor și viziune computerizată

Laplacianul este unul dintre cele mai vechi instrumente în viziunea computerizată și este încă folosit activ astăzi.

În procesarea imaginilor, intensitatea pixelului este funcția. Laplacianul măsoară cât de mult diferă intensitatea unui pixel de cea a vecinilor. Unde intensitatea se schimbă lent, Laplacianul este aproape de zero. Unde se schimbă brusc – la o muchie – Laplacianul produce un răspuns puternic.

Aceasta este întreaga bază pentru detecția muchiilor cu Laplacianul.

De ce derivatele de ordinul al doilea găsesc muchii

O derivată de ordinul întâi găsește unde se schimbă intensitatea. O derivată de ordinul al doilea găsește unde se schimbă chiar această schimbare – cu alte cuvinte, unde rata de schimbare atinge un vârf și apoi scade.

La o muchie, intensitatea crește și apoi se stabilizează. Derivata de ordinul întâi are un vârf la rampă. Derivata de ordinul al doilea – Laplacianul – trece prin zero chiar în vârful acelui spike. Aceste treceri prin zero marchează poziția exactă a unei muchii, ceea ce face Laplacianul mai precis pentru localizarea muchiilor decât metodele bazate pe derivata întâi, precum filtrul Sobel.

Nucleul discret al Laplacianului

În practică, imaginile sunt grile de pixeli, nu funcții continue. Laplacianul continuu este aproximat folosind un nucleu de convoluție – o matrice mică pe care o glisați peste imagine.

Nucleul discret standard 3×3 al Laplacianului arată astfel:

Nucleu discret 3x3 al Laplacianului

Greutatea centrală este -4, iar cei patru vecini direcți primesc câte +1. Când aplicați acest nucleu pe un pixel, calculați diferența dintre intensitatea acelui pixel și media celor patru vecini – versiunea discretă a aceleiași întrebări „cum se compară acest punct cu împrejurimile lui” de mai devreme.

Considerații practice

Filtrarea brută cu Laplacianul este sensibilă la zgomot. Un singur pixel zgomotos produce un vârf de intensitate, iar Laplacianul îl va marca drept muchie.

Remediul standard este să neteziți mai întâi imaginea cu un blur Gaussian, apoi să aplicați Laplacianul. Această combinație se numește Laplacian of Gaussian (LoG). Gaussianul suprimă zgomotul, iar Laplacianul găsește muchiile reale.

În deep learning, rețelele neuronale convoluționale învață propriile filtre de detecție a muchiilor din date – dar acele filtre învățate adesea seamănă cu nucleul Laplacian. Deci, într-un fel, matematica ce a făcut Laplacianul util în viziunea computerizată clasică este aceeași pe care rețelele neuronale o redescoperă singure.

Laplacian discret vs. continuu

Laplacianul este trei idei înrudite care apar în contexte diferite.

Înțelegerea versiunii cu care lucrați vă scutește de multă confuzie când treceți între manuale de calcul, cod numeric și lucrări de ML pe grafuri.

Laplacianul continuu

Laplacianul continuu este cel din calcul. Pentru o funcție netedă f definită pe un spațiu continuu, este suma derivatelor parțiale de ordinul al doilea:

Laplacianul continuu

Această versiune presupune că funcția este netedă și derivabilă peste tot. Este fundamentul teoretic – dar datele reale nu sunt niciodată continue. Nu puteți calcula derivate exacte pe o grilă de pixeli sau pe un tabel de măsurători.

Laplacianul discret

Când treceți de la funcții continue la date eșantionate, derivatele sunt înlocuite cu diferențe finite – aproximații calculate din valorile vecine.

Pentru o funcție 1D eșantionată la puncte echidistante, derivata a doua discretă în punctul i este:

Laplacianul discret

Comparați valoarea din i cu cele două vecine. Aceeași idee se extinde la grile 2D (imagini), volume 3D și mai departe. Nucleele de convoluție din secțiunea de procesare a imaginilor sunt exact asta – aproximații prin diferențe finite ale Laplacianului continuu, aplicate pe o grilă de pixeli.

Această discretizare face Laplacianul calculabil în metode numerice și fluxuri ML. De fiecare dată când aplicați un filtru Laplacian în cod, rulați o aproximație prin diferențe finite, nu operatorul exact din calcul.

Laplacianul pe graf

Laplacianul pe graf duce discretizarea cu un pas mai departe. În loc de o grilă regulată cu spațiere uniformă, aveți un set arbitrar de noduri conectate prin muchii cu ponderi variabile.

Nu există noțiunea de „pixel vecin” aici – doar noduri și conexiunile dintre ele. Laplacianul pe graf L = D - A înlocuiește structura diferențelor finite cu structura de adiacență. Întrebarea de bază rămâne: cum se compară valoarea unui nod cu a vecinilor săi? Dar „vecinii” sunt acum definiți de graf, nu de proximitatea spațială.

De ce contează asta în ML

Majoritatea datelor ML nu trăiesc pe o grilă regulată. Moleculele, rețelele sociale, grafurile de cunoștințe și norii de puncte 3D au structură neregulată. Nu puteți aplica un Laplacian standard cu diferențe finite pe ele.

Laplacianul pe graf rezolvă asta făcând explicită structura de vecinătate prin matricea de adiacență. De aceea rețelele neuronale pe grafuri și metodele spectrale pot aplica operații bazate pe Laplacian pe date fără un sistem natural de coordonate.

Exemplu rezolvat: calculul unui Laplacian

Să facem totul concret cu două exemple – unul continuu, unul pe graf.

Exemplul 1: Laplacianul continuu al f(x, y) = x² + y²

Luați funcția f(x, y) = x² + y². Este un paraboloid simplu – o formă de bol care se curbează în sus în fiecare direcție.

Pentru a calcula Laplacianul, aveți nevoie de derivata parțială de ordinul al doilea față de fiecare variabilă.

Mai întâi, față de x:

Calculul Laplacianului continuu (1)

Apoi față de y:

Calculul Laplacianului continuu (2)

Iar acum doar le adunați:

Calculul Laplacianului continuu (3)

Laplacianul este o constantă 4 peste tot. Are sens, deoarece un paraboloid are aceeași curbură în fiecare punct. Valoarea pozitivă vă spune că funcția se curbează în sus în toate direcțiile, în acord cu forma de bol.

Exemplul 2: Laplacianul pe graf pentru un graf mic

Luați un graf cu 4 noduri și următoarele muchii:

• Nodul 1 se conectează la nodurile 2 și 3
• Nodul 2 se conectează la nodurile 1 și 4
• Nodul 3 se conectează la nodul 1
• Nodul 4 se conectează la nodul 2

Matricea de adiacență A codifică conexiunile:

Calculul Laplacianului pe graf (1)

Matricea gradelor D pune numărul de conexiuni al fiecărui nod pe diagonală:

Calculul Laplacianului pe graf (2)

Nodurile 1 și 2 au câte 2 conexiuni. Nodurile 3 și 4 au câte 1.

În final, scădeți pentru a obține L = D - A:

Calculul Laplacianului pe graf (3)

Cum citiți această matrice: Rândul 1 spune: nodul 1 are gradul 2 și este conectat la nodurile 2 și 3 (intrările -1). Rândul 3 spune: nodul 3 are gradul 1, conectat doar la nodul 1. Zerourile vă spun care perechi de noduri nu împart nicio muchie.

Îl puteți calcula și în Python pentru verificare:

import numpy as np

A = np.array([
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 0],
    [0, 1, 0, 0]
])

D = np.diag(A.sum(axis=1))
L = D - A

print(L)

Calculul Laplacianului pe graf în Python

Confuzii frecvente

Laplacianul este asemănător cu câteva alte concepte, iar diferențele nu sunt întotdeauna evidente doar din denumiri. În această secțiune, voi încerca să elimin toate punctele de confuzie.

Laplacian vs. gradient

Gradientul ∇f este un vector. Indică direcția de creștere maximă, iar magnitudinea sa vă spune cât de repede crește funcția. Folosește derivate de ordinul întâi.

Laplacianul ∇²f este un scalar. Nu vă spune în ce direcție să vă mișcați – vă spune despre forma funcției într-un punct. Este construit din derivate de ordinul al doilea.

Laplacian vs. Hessian

Aceasta îi încurcă pe mulți cel mai des.

Hessianul H este o matrice a tuturor derivatelor parțiale de ordinul al doilea. Pentru o funcție cu n intrări, este o matrice n × n care surprinde cum se schimbă gradientul pe fiecare pereche de axe. Vă oferă imaginea completă a curburii.

Laplacianul este urma Hessianului – suma elementelor diagonale. Pierdeți informația de pe extradiagonală, dar obțineți un singur număr rapid de calculat.

Folosiți Hessianul când aveți nevoie de defalcarea completă a curburii. Folosiți Laplacianul când un rezumat scalar este suficient.

Laplacianul pe graf vs. operatorul diferențial

Acestea împart un nume și aceeași intuiție de bază, dar operează pe obiecte complet diferite.

Laplacianul diferențial acționează pe funcții netede, continue. Necesită derivate, ceea ce presupune că funcția este derivabilă peste tot.

Laplacianul pe graf L = D - A acționează pe grafuri – structuri discrete cu noduri și muchii. Nu sunt implicate derivate. Măsoară cât de mult diferă valoarea din fiecare nod de valorile vecinilor săi folosind operații matriciale.

Conexiunea este conceptuală, nu computațională. Ambele măsoară abaterea locală față de media vecinătății, dar sunt în întregime diferite.

Convenții de semn

Unele domenii definesc Laplacianul cu semn negativ: -∇²f. Veți vedea asta în fizică și în unele lucrări de ML despre rețele neuronale pe grafuri. Laplacianul negativ −L este semidefinit pozitiv, ceea ce are proprietăți mai bune pentru anumite probleme de optimizare și face analiza valorilor proprii mai curată.

Când citiți o lucrare și valorile proprii ale Laplacianului sunt toate nenegative, verificați dacă folosesc L sau -L. Matematica este echivalentă, dar amestecarea convențiilor vă poate conduce la rezultate greșite.

De ce contează Laplacianul în data science

Până acum, ați văzut Laplacianul apărând în calcul, teoria grafurilor, procesarea imaginilor și optimizare. Același operator rezolvă aceeași problemă fundamentală în contexte diferite: măsurarea modului în care o valoare într-un punct se raportează la împrejurimi.

Iată unde apare asta în data science:

• ML bazat pe grafuri: Laplacianul pe graf L = D - A este fundația metodelor spectrale. Ori de câte ori datele au o structură naturală de graf, Laplacianul vă oferă o matrice care encodează întregul model de conectivitate într-o formă pe care o puteți supune algebrei liniare

• Clusterizare: Clusterizarea spectrală folosește vectorii proprii ai lui L pentru a găsi grupuri pe care metodele bazate strict pe distanță le ratează. Funcționează bine când clusterele nu sunt convexe sau liniar separabile

• Învățare semi-supervizată: Multe metode semi-supervizate folosesc Laplacianul pe graf pentru a propaga etichete de la nodurile etichetate la cele neetichetate. Presupunerea este că nodurile conectate au probabil aceeași etichetă, iar Laplacianul cuantifică cât de lin ar trebui să varieze etichetele pe graf

• Învățare pe varietăți (manifold learning): Algoritmi precum Laplacian Eigenmaps folosesc Laplacianul pe graf pentru a găsi reprezentări de dimensiune mică ale datelor de înaltă dimensionalitate. Vectorii proprii ai lui L mapează punctele apropiate în spațiul original la puncte apropiate în spațiul redus

• Extragerea de caracteristici din imagini: Laplacianul discret detectează muchii și regiuni cu schimbări rapide de intensitate. Aceste caracteristici intră direct în fluxuri clasice de viziune computerizată și ca priori în arhitecturi de deep learning

Pe scurt, Laplacianul este unul dintre puținele instrumente matematice care scalează de la o singură ecuație de calcul până la rețele neuronale mari pe grafuri.

Concluzie

Laplacianul pornește ca un operator de calcul, o modalitate de a măsura curbură în funcții continue. Până ajungeți la ML bazat pe grafuri, devine o matrice care encodează structura unei întregi rețele. Ideea de bază este exact aceeași, doar forma diferă.

Înscrieți-vă la cursul nostru Linear Algebra for Data Science in R pentru a obține experiență practică cu multe concepte și subiecte acoperite în acest articol.