Memahami Laplacian: Dari Kalkulus hingga ML

Laplacian muncul dalam algoritma berbasis graf, pipeline pemrosesan citra, dan spectral clustering. Jadi jika Anda membangun model yang bekerja dengan graf, citra, atau data berdimensi tinggi, Laplacian bukan sekadar matematika latar belakang opsional. Inilah komponen yang benar-benar bekerja di balik layar.

Dalam artikel ini, saya akan membahas Laplacian dari dasar: matematika di baliknya, intuisi geometrisnya, graph Laplacian dan bentuk matriksnya, serta bagaimana ia digunakan dalam aplikasi machine learning nyata.

Butuh pengantar praktis tentang persamaan diferensial? Baca artikel terbaru kami untuk beralih dari dasar ke aplikasi machine learning praktis.

Apa itu Laplacian?

Laplacian adalah operator diferensial orde kedua. Ia memberi tahu bagaimana sebuah fungsi melengkung di titik tertentu.

Kadang ia dijelaskan sebagai divergensi dari gradien.

Dan itulah kunci untuk memahami apa yang sebenarnya dilakukan operator ini:

• Gradien memberi tahu arah di mana fungsi meningkat paling cepat
• Divergensi mengukur apakah aliran itu menyebar atau berkumpul.

Saat digabungkan, Laplacian memberi tahu apakah suatu titik merupakan puncak lokal, lembah lokal, atau datar di antaranya.

Secara sederhana, Laplacian mengukur seberapa besar nilai fungsi di suatu titik berbeda dari nilai rata-rata tetangganya. Jika Laplacian nol, fungsi tersebut "seimbang" secara lokal. Positif berarti titik berada di bawah sekelilingnya. Negatif berarti berada di atasnya.

Rumusnya

Dalam 2D, untuk fungsi f(x, y):

Rumus Laplacian 2D

Dalam 3D, untuk fungsi f(x, y, z):

Rumus Laplacian 3D

Pola ini berlaku dalam sejumlah dimensi berapa pun - Anda menjumlahkan turunan parsial kedua sepanjang tiap sumbu. Hal ini membuat Laplacian sangat cocok untuk data berdimensi tinggi, itulah sebabnya ia sering muncul dalam machine learning.

Rumus Laplacian dalam Kalkulus Multivariabel

Rumus Laplacian lebih singkat dari yang Anda kira untuk sesuatu yang muncul di begitu banyak aspek machine learning.

Dalam 3D, untuk fungsi f(x, y, z), tampilannya seperti ini:

Rumus Laplacian 3D

Itu saja. Anda menjumlahkan turunan parsial kedua di sepanjang tiap dimensi.

Setiap suku menanyakan hal yang sama di sepanjang sumbunya: apakah fungsi melengkung ke atas, melengkung ke bawah, atau datar? Ketika Anda menjumlahkan jawabannya, Anda memperoleh satu angka yang menggambarkan kelengkungan keseluruhan di titik itu.

Dari 3D ke n dimensi

Rumus ini digeneralisasi ke n dimensi. Ini adalah rumus umum untuk fungsi dengan n dimensi masukan:

Generalisasi rumus Laplacian

Inilah sebabnya Laplacian bekerja baik dalam machine learning, di mana data Anda sering berada pada ratusan atau ribuan dimensi. Operator ini sekadar menjumlahkan kelengkungan di sepanjang tiap dimensi.

Keterkaitan dengan optimisasi

Jika Anda pernah bekerja dengan gradient descent, Anda sudah memikirkan turunan pertama - arah mana yang menurun? Laplacian membawa Anda selangkah lebih jauh.

Turunan kedua memberi tahu bentuk bukit tersebut.

Laplacian yang sangat positif di suatu titik berarti fungsi melengkung tajam ke atas ke segala arah - Anda dekat dengan minimum. Nilai negatif besar berarti Anda dekat dengan maksimum. Mendekati nol berarti permukaannya datar secara lokal.

Informasi kelengkungan ini penting dalam metode optimisasi orde kedua, yang menggunakannya untuk mengambil langkah yang lebih cerdas daripada gradient descent murni. Laplacian adalah salah satu cara untuk meringkas kelengkungan itu dalam satu nilai skalar.

Intuisi Geometris: Apa yang Diukur Laplacian

Tanda Laplacian pada suatu titik memberi tahu bentuk fungsi di sekitarnya.

• Jika ∇²f > 0 di suatu titik, fungsi melengkung ke atas ke segala arah. Titik tersebut lebih rendah dari sekelilingnya. Itulah kekonveksan.

• Jika ∇²f < 0, fungsi melengkung ke bawah. Titik tersebut lebih tinggi dari sekelilingnya. Itulah kekonkavan.

• Jika ∇²f = 0, fungsinya datar secara lokal. Tidak ada kelengkungan bersih ke arah mana pun.

Ini adalah versi multivariabel dari uji turunan kedua yang sudah Anda kenal. Dalam 1D, turunan kedua positif berarti minimum lokal dan yang negatif berarti maksimum lokal. Laplacian memperluas gagasan yang sama ke jumlah dimensi berapa pun dengan menjumlahkan kelengkungan di semua sumbu.

Keterkaitan dengan Hessian

Matriks Hessian menangkap gambaran kelengkungan secara penuh. Ini adalah matriks semua turunan parsial kedua, dan setiap entri menjelaskan bagaimana fungsi melengkung sepanjang sepasang sumbu.

Laplacian adalah jejak (trace) dari Hessian - jumlah entri diagonalnya. Jika Hessian memberi Anda rincian kelengkungan lengkap, Laplacian mereduksinya menjadi satu angka.

Pertukaran ini penting dalam machine learning. Hessian penuh mahal dihitung untuk model berdimensi tinggi - model dengan n parameter memiliki Hessian berukuran n × n. Laplacian memberi ringkasan kelengkungan skalar yang murah dan cepat digunakan.

Mengapa ini penting untuk machine learning

Saat Anda melatih model, Anda menavigasi permukaan loss. Daerah datar berarti pembelajaran lambat. Area konveks berarti optimizer dapat melampaui sasaran. Laplacian memberi Anda pembacaan cepat tentang situasi mana yang sedang Anda hadapi.

Metode berbasis graf menggunakan Laplacian untuk mengukur seberapa mulus nilai berubah di seluruh node graf. Ini adalah perpanjangan langsung dari intuisi kelengkungan yang sama dari fungsi kontinu ke struktur diskret.

Laplacian dan Optimisasi dalam Machine Learning

Gradient descent hanya menggunakan turunan pertama.

Gradien memberi tahu arah langkah. Ia tidak memberi tahu seberapa besar langkah itu. Gradien curam dalam lembah lebar yang datar memerlukan langkah besar. Gradien curam yang sama di dekat tepi tebing tajam memerlukan langkah kecil. Turunan pertama saja tidak dapat membedakannya.

Di situlah turunan kedua berperan.

Kelengkungan dan ukuran langkah

Kelengkungan menggambarkan seberapa cepat gradien itu sendiri berubah. Kelengkungan tinggi berarti permukaan loss berbelok tajam - langkah kecil di ruang parameter menghasilkan perubahan besar pada gradien. Kelengkungan rendah berarti permukaannya datar dan gradien berubah lambat.

Jika Anda mengabaikan kelengkungan dan menggunakan laju pembelajaran tetap, Anda menebak-nebak. Terlalu besar, Anda melampaui sasaran di wilayah berkelenkungan tinggi. Terlalu kecil, Anda merayap di wilayah datar.

Metode optimisasi orde kedua seperti metode Newton menggunakan kelengkungan untuk mengatur ukuran langkah secara otomatis. Mereka membagi gradien dengan kelengkungan, mengambil langkah lebih besar ketika permukaan datar dan lebih kecil ketika tajam.

Di mana Laplacian cocok

Laplacian adalah jejak dari Hessian - satu skalar yang merangkum kelengkungan total di suatu titik. Ia tidak menangkap gambaran lengkap seperti Hessian, tetapi murah dihitung dan berguna sebagai sinyal.

Berikut penjelasan sederhana yang perlu Anda ingat:

• Laplacian loss yang positif besar di suatu titik berarti Anda dekat minimum lokal - loss melengkung ke atas ke segala arah
• Nilai negatif berarti Anda dekat maksimum
• Mendekati nol berarti Anda berada di wilayah datar atau pelana, yang persis tempat gradient descent cenderung macet

Stabilitas dan regularisasi

Kelengkungan juga terkait dengan stabilitas pelatihan. Minimum yang tajam - wilayah dengan kelengkungan tinggi - cenderung melakukan generalisasi lebih buruk daripada yang datar. Model yang konvergen ke minimum tajam sensitif terhadap perubahan kecil pada input.

Beberapa teknik regularisasi secara langsung memberi penalti pada kelengkungan untuk mendorong optimisasi menuju wilayah yang lebih datar pada permukaan loss. Laplacian juga muncul di sini, sebagai cara untuk mengukur dan membatasi seberapa tajam prediksi model berubah di seluruh ruang input.

Memahami kelengkungan membantu Anda memahami mengapa optimizer Anda macet, mengapa laju pembelajaran sangat penting, dan mengapa beberapa minimum melakukan generalisasi lebih baik daripada yang lain.

Graph Laplacian dan Matriks Laplacian

Sejauh ini, Laplacian berada di dunia fungsi kontinu. Namun apa yang terjadi ketika data Anda bukan permukaan mulus, melainkan graf?

Di sinilah graph Laplacian berperan. Ia mengambil gagasan inti yang sama - mengukur bagaimana nilai di satu titik berbeda dari tetangganya - dan menerapkannya pada node dan edge.

Rumusnya

Graph Laplacian L didefinisikan sebagai:

Rumus Graph Laplacian (disederhanakan)

Dua matriks. Itu saja. Mari kita uraikan artinya masing-masing.

Matriks ketetanggaan (adjacency)

Matriks ketetanggaan A mengodekan node mana yang terhubung. Untuk graf dengan n node, A adalah matriks n × n di mana A_ij = 1 jika ada edge antara node i dan node j, dan 0 jika tidak.

Untuk graf tak berarah sederhana dengan 3 node di mana node 1 terhubung ke node 2 dan 3, tetapi 2 dan 3 tidak saling terhubung:

Matriks ketetanggaan

Matriks derajat (degree)

Matriks derajat D adalah matriks diagonal. Setiap entri diagonal D_ii adalah derajat node i - jumlah edge yang terhubung dengannya. Semua entri di luar diagonal adalah nol.

Berikut rumus untuk graf yang sama:

Matriks derajat

Node 1 memiliki derajat 2 (terhubung ke dua node). Node 2 dan 3 masing-masing memiliki derajat 1.

Menggabungkannya

Kurangkan A dari D dan Anda mendapatkan L:

Mengurangkan matriks ketetanggaan dari matriks derajat

Setiap entri diagonal memberi tahu Anda berapa banyak koneksi yang dimiliki sebuah node. Setiap entri di luar diagonal L_ij bernilai -1 jika node i dan j terhubung, dan 0 jika tidak.

Jika Anda mengalikan L dengan sebuah vektor nilai yang ditetapkan ke setiap node, hasilnya mengukur seberapa besar nilai tiap node berbeda dari nilai tetangganya. Itulah versi diskret dari intuisi kelengkungan yang sama seperti sebelumnya - hanya saja diterapkan pada graf alih-alih permukaan kontinu.

Apa yang dikatakan nilai eigen tentang sebuah graf

Kekuatan sebenarnya dari L berasal dari nilai eigen dan vektor eigennya:

• Nilai eigen terkecil dari L selalu 0. Vektor eigen yang bersesuaian adalah vektor konstan - setiap node mendapatkan nilai yang sama. Ini masuk akal: fungsi konstan memiliki "variasi" nol di seluruh graf.

• Jumlah nilai eigen nol sama dengan jumlah komponen terhubung dalam graf. Jika graf Anda memiliki tiga klaster yang tak saling terhubung, L memiliki tiga nilai eigen nol. Ini adalah cara langsung untuk membaca keterhubungan graf dari sebuah matriks.

• Nilai eigen kecil yang bukan nol berkaitan dengan vektor eigen yang berubah secara lambat di seluruh graf - node yang berdekatan memperoleh nilai yang mirip. Nilai eigen besar berkaitan dengan vektor eigen yang berosilasi cepat antar node yang terhubung.

Fakta menarik: Spektrum nilai eigen inilah yang memberi nama pada metode spektral.

Spectral clustering dan deteksi komunitas

Spectral clustering menggunakan vektor eigen dari L untuk menemukan klaster pada data berstruktur graf. Gagasannya adalah vektor eigen yang terkait dengan nilai eigen kecil memberikan nilai yang mirip pada node yang terhubung rapat dan nilai berbeda pada yang terhubung longgar.

Untuk menemukan k klaster, Anda mengambil k vektor eigen yang bersesuaian dengan k nilai eigen terkecil yang bukan nol dari L, menyusunnya menjadi sebuah matriks, dan menjalankan k-means pada baris-barisnya. Setiap baris adalah node, dan posisinya di ruang berdimensi rendah ini mencerminkan lingkungan grafnya.

Ini bekerja untuk deteksi komunitas dalam jejaring sosial, pengelompokan dokumen, segmentasi citra, dan di mana pun data Anda memiliki struktur graf yang alami. Dua node yang terhubung erat akan berakhir berdekatan dalam ruang vektor eigen. Dua node dari komunitas berbeda akan berakhir berjauhan.

Graph Laplacian mengubah masalah kombinatorial yang sulit - temukan klaster dalam graf ini - menjadi masalah aljabar linear yang mudah diselesaikan.

Laplacian dalam Spectral Clustering

Spectral clustering adalah tempat graph Laplacian beralih dari matematika yang menarik menjadi alat ML yang praktis.

Gagasan intinya adalah alih-alih mengelompokkan titik data mentah secara langsung, Anda mengelompokkannya dalam ruang yang didefinisikan oleh vektor eigen dari L. Ruang itu menangkap struktur graf, sehingga Anda dapat melihat node mana yang terhubung erat, yang terhubung longgar, dan yang termasuk ke komunitas terpisah.

Bagaimana vektor eigen mendefinisikan klaster

Ambil k vektor eigen yang bersesuaian dengan k nilai eigen terkecil yang bukan nol dari L. Susun mereka sebagai kolom ke dalam sebuah matriks. Setiap baris matriks itu adalah sebuah node, kini direpresentasikan sebagai titik dalam ruang berdimensi k.

Vektor eigen yang terkait dengan nilai eigen kecil berubah perlahan di seluruh graf. Node yang terhubung rapat berakhir dengan nilai yang mirip dalam vektor-vektor eigen ini - dan nilai yang mirip berarti baris yang mirip - dan baris yang mirip berarti mereka mendarat berdekatan dalam ruang baru.

Laplacian tidak ternormalisasi versus ternormalisasi

Ada dua versi graph Laplacian yang akan Anda temui dalam praktik.

Laplacian tidak ternormalisasi adalah L = D - A yang lugas. Ia bekerja baik ketika node memiliki derajat yang kira-kira serupa - yaitu, ketika sebagian besar node memiliki jumlah koneksi yang mirip

Laplacian ternormalisasi menyesuaikan ketidakseimbangan derajat. Ada beberapa varian, tetapi yang paling umum adalah:

Rumus Laplacian ternormalisasi

Ini mereskalakan kontribusi setiap node berdasarkan derajatnya. Dalam graf dunia nyata - jejaring sosial, graf web, jaringan sitasi - beberapa node memiliki ratusan koneksi dan yang lain hanya satu atau dua. Tanpa normalisasi, node berderajat tinggi mendominasi vektor eigen dan hasil pengelompokan akan buruk.

Gunakan Laplacian ternormalisasi secara default kecuali Anda tahu graf Anda memiliki distribusi derajat yang seragam.

Aplikasi praktis

Spectral clustering dengan graph Laplacian muncul di berbagai tugas machine learning. Berikut beberapa di antaranya:

• Segmentasi citra - piksel menjadi node, bobot edge mengodekan kemiripan, dan klaster memetakan ke wilayah citra
• Pengelompokan dokumen - dokumen menjadi node, edge mengodekan istilah bersama atau sitasi
• Analisis jejaring sosial - pengguna menjadi node, edge mengodekan koneksi, dan klaster mengungkap komunitas
• Sistem rekomendasi - item atau pengguna membentuk graf, dan metode spektral menemukan kelompok dengan perilaku serupa

Kapan pun data Anda memiliki struktur graf alami, atau Anda dapat membangunnya dari kemiripan berpasangan, spectral clustering memberi cara berprinsip untuk menemukan kelompok yang luput dari metode berbasis jarak murni.

Laplacian dalam Pemrosesan Citra dan Penglihatan Komputer

Laplacian adalah salah satu alat tertua dalam penglihatan komputer, dan masih aktif digunakan hingga kini.

Dalam pemrosesan citra, intensitas piksel adalah fungsinya. Laplacian mengukur bagaimana intensitas suatu piksel berbeda dari tetangganya. Di mana intensitas berubah perlahan, Laplacian mendekati nol. Di mana berubah tajam - pada tepi - Laplacian menghasilkan respons kuat.

Itulah keseluruhan dasar dari deteksi tepi Laplacian.

Mengapa turunan kedua menemukan tepi

Turunan pertama menemukan di mana intensitas berubah. Turunan kedua menemukan di mana perubahan itu sendiri berubah - dengan kata lain, di mana laju perubahan memuncak lalu menurun.

Pada tepi, intensitas meningkat lalu merata. Turunan pertama memuncak pada kenaikan itu. Turunan kedua - Laplacian - melintasi nol tepat di puncak lonjakan itu. Persilangan nol ini menandai lokasi tepi secara tepat, yang membuat Laplacian lebih presisi untuk pelokalan tepi daripada metode turunan pertama seperti filter Sobel.

Kernel Laplacian diskret

Dalam praktiknya, citra adalah kisi piksel, bukan fungsi kontinu. Laplacian kontinu didekati menggunakan sebuah kernel konvolusi - matriks kecil yang Anda geser melintasi citra.

Kernel Laplacian diskret 3×3 standar terlihat seperti ini:

Kernel Laplacian diskret 3x3

Bobot tengah adalah -4 dan empat tetangga langsung masing-masing mendapat +1. Saat Anda menerapkan kernel ini ke sebuah piksel, Anda menghitung selisih antara intensitas piksel tersebut dan rata-rata empat tetangganya - versi diskret dari pertanyaan "bagaimana titik ini dibandingkan dengan sekelilingnya" yang sama seperti sebelumnya.

Pertimbangan praktis

Penyaringan Laplacian mentah sensitif terhadap derau. Satu piksel berderau menghasilkan lonjakan intensitas tajam, dan Laplacian akan menandainya sebagai tepi.

Perbaikan standarnya adalah menghaluskan citra terlebih dahulu dengan blur Gaussian, lalu menerapkan Laplacian. Kombinasi ini disebut Laplacian of Gaussian (LoG). Gaussian menekan derau, dan Laplacian menemukan tepi yang sebenarnya.

Dalam deep learning, convolutional neural network mempelajari filter deteksi tepi mereka sendiri dari data - tetapi filter yang dipelajari itu sering menyerupai kernel Laplacian. Jadi dalam arti tertentu, matematika yang membuat Laplacian berguna dalam visi komputer klasik adalah matematika yang sama yang "ditemukan kembali" oleh jaringan saraf.

Laplacian Diskret vs. Kontinu

Laplacian adalah tiga gagasan terkait yang muncul dalam konteks berbeda.

Memahami versi mana yang Anda gunakan menghemat banyak kebingungan saat Anda berpindah antara buku teks kalkulus, kode numerik, dan makalah graph ML.

Laplacian kontinu

Laplacian kontinu adalah yang berasal dari kalkulus. Untuk fungsi mulus f yang didefinisikan pada ruang kontinu, ia merupakan jumlah turunan parsial kedua:

Laplacian kontinu

Versi ini mengasumsikan fungsi Anda mulus dan terdiferensialkan di mana-mana. Ini adalah landasan teoretis - tetapi data nyata tidak pernah kontinu. Anda tidak dapat menghitung turunan eksak pada kisi piksel atau tabel pengukuran.

Laplacian diskret

Saat Anda berpindah dari fungsi kontinu ke data tersampel, turunan digantikan oleh beda hingga - pendekatan yang dihitung dari nilai tetangga.

Untuk fungsi 1D yang disampel pada titik-titik berjarak seragam, turunan kedua diskret di titik i adalah:

Laplacian diskret

Anda membandingkan nilai di i dengan dua tetangganya. Gagasan yang sama diperluas ke kisi 2D (citra), volume 3D, dan seterusnya. Kernel konvolusi dari bagian pemrosesan citra persis ini - pendekatan beda hingga dari Laplacian kontinu, diterapkan pada kisi piksel.

Diskretisasi ini membuat Laplacian dapat dihitung dalam metode numerik dan pipeline ML. Setiap kali Anda menerapkan filter Laplacian dalam kode, Anda menjalankan pendekatan beda hingga, bukan operator kalkulus yang eksak.

Graph Laplacian

Graph Laplacian membawa diskretisasi selangkah lebih jauh. Alih-alih kisi reguler dengan jarak seragam, Anda memiliki sekumpulan node arbitrer yang dihubungkan oleh edge dengan bobot bervariasi.

Tidak ada konsep "piksel tetangga" di sini - hanya node dan koneksinya. Graph Laplacian L = D - A menggantikan struktur beda hingga dengan struktur ketetanggaan. Pertanyaan inti yang sama tetap ada: bagaimana nilai sebuah node dibandingkan dengan tetangganya? Namun "tetangga" kini didefinisikan oleh graf, bukan kedekatan spasial.

Mengapa ini penting dalam ML

Sebagian besar data ML tidak berada pada kisi reguler. Molekul, jejaring sosial, knowledge graph, dan point cloud 3D semuanya memiliki struktur tak beraturan. Anda tidak dapat menerapkan Laplacian beda hingga standar pada data tersebut.

Graph Laplacian mengatasinya dengan membuat struktur ketetanggaan eksplisit melalui matriks ketetanggaan. Itulah mengapa graph neural network dan metode spektral dapat menerapkan operasi berbasis Laplacian pada data yang tidak memiliki sistem koordinat alami.

Contoh Terbimbing: Menghitung Laplacian

Mari kita buat ini konkret dengan dua contoh - satu kontinu, satu berbasis graf.

Contoh 1: Laplacian kontinu dari f(x, y) = x² + y²

Ambil fungsi f(x, y) = x² + y². Ini adalah paraboloid sederhana - bentuk mangkuk yang melengkung ke atas ke segala arah.

Untuk menghitung Laplacian, Anda memerlukan turunan parsial kedua terhadap setiap variabel.

Pertama, terhadap x:

Perhitungan Laplacian kontinu (1)

Lalu terhadap y:

Perhitungan Laplacian kontinu (2)

Dan sekarang tinggal jumlahkan:

Perhitungan Laplacian kontinu (3)

Laplacian bernilai konstan 4 di mana-mana. Itu masuk akal karena paraboloid memiliki kelengkungan yang sama di setiap titik. Nilai positif memberi tahu Anda bahwa fungsi melengkung ke atas ke segala arah, konsisten dengan bentuk mangkuk.

Contoh 2: Graph Laplacian untuk graf kecil

Ambil graf dengan 4 node dan edge berikut:

• Node 1 terhubung ke node 2 dan 3
• Node 2 terhubung ke node 1 dan 4
• Node 3 terhubung ke node 1
• Node 4 terhubung ke node 2

Matriks ketetanggaan A mengodekan koneksi:

Perhitungan Graph Laplacian (1)

Matriks derajat D menempatkan jumlah koneksi tiap node pada diagonal:

Perhitungan Graph Laplacian (2)

Node 1 dan 2 masing-masing memiliki 2 koneksi. Node 3 dan 4 masing-masing memiliki 1.

Terakhir, kurangkan untuk memperoleh L = D - A:

Perhitungan Graph Laplacian (3)

Begini cara membaca matriks ini: Baris 1 menyatakan: node 1 memiliki derajat 2, dan terhubung ke node 2 dan 3 (entri -1). Baris 3 menyatakan: node 3 memiliki derajat 1, hanya terhubung ke node 1. Nol menunjukkan pasangan node yang tidak berbagi edge.

Anda juga dapat menghitungnya di Python untuk memverifikasi:

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)

Perhitungan Graph Laplacian di Python

Kebingungan Umum

Laplacian mirip dengan beberapa konsep lain, dan perbedaannya tidak selalu jelas dari namanya saja. Di bagian ini, saya akan mencoba menghilangkan semua titik kebingungan.

Laplacian vs. gradien

Gradien ∇f adalah vektor. Ia menunjuk ke arah kenaikan paling curam dan besarannya memberi tahu seberapa cepat fungsi meningkat. Ia menggunakan turunan pertama.

Laplacian ∇²f adalah skalar. Ia tidak memberi tahu arah mana yang harus ditempuh - ia memberi tahu bentuk fungsi di suatu titik. Ia dibangun dari turunan kedua.

Laplacian vs. Hessian

Yang ini paling sering menyesatkan orang.

Hessian H adalah matriks semua turunan parsial kedua. Untuk fungsi dengan n masukan, ini adalah matriks n × n yang menangkap bagaimana gradien berubah di sepanjang setiap pasangan sumbu. Ia memberi gambaran kelengkungan yang lengkap.

Laplacian adalah jejak dari Hessian - jumlah entri diagonalnya. Anda kehilangan informasi kelengkungan di luar diagonal, tetapi memperoleh satu angka yang cepat dihitung.

Gunakan Hessian ketika Anda membutuhkan rincian kelengkungan lengkap. Gunakan Laplacian ketika ringkasan skalar sudah cukup.

Graph Laplacian vs. operator diferensial

Keduanya berbagi nama dan intuisi inti yang sama, tetapi beroperasi pada objek yang sepenuhnya berbeda.

Laplacian diferensial bekerja pada fungsi halus dan kontinu. Ia memerlukan turunan, yang berarti mengasumsikan fungsi Anda terdiferensialkan di mana-mana.

Graph Laplacian L = D - A bekerja pada graf - struktur diskret dengan node dan edge. Tidak ada turunan yang terlibat. Ia mengukur bagaimana nilai pada setiap node berbeda dari tetangganya menggunakan operasi matriks.

Koneksinya bersifat konseptual, bukan komputasional. Keduanya mengukur deviasi lokal dari rata-rata lingkungan, tetapi sepenuhnya berbeda.

Konvensi tanda

Beberapa bidang mendefinisikan Laplacian dengan tanda negatif: -∇²f. Anda akan melihat ini dalam fisika dan beberapa makalah ML tentang graph neural network. Laplacian negatif −L adalah positif semidefinit, yang memiliki sifat lebih baik untuk masalah optimisasi tertentu dan membuat analisis nilai eigen lebih rapi.

Ketika Anda membaca makalah dan nilai eigen Laplacian semuanya tidak negatif, periksa apakah mereka menggunakan L atau -L. Secara matematis setara, tetapi mencampuradukkan konvensi dapat menyesatkan Anda.

Mengapa Laplacian Penting dalam Data Science

Pada titik ini, Anda telah melihat Laplacian muncul di kalkulus, teori graf, pemrosesan citra, dan optimisasi. Operator yang sama memecahkan masalah fundamental yang sama dalam konteks berbeda: mengukur bagaimana nilai di satu titik berhubungan dengan sekelilingnya.

Berikut tempat kemunculannya dalam data science:

• ML berbasis graf: Graph Laplacian L = D - A adalah fondasi metode spektral. Kapan pun data Anda memiliki struktur graf alami, Laplacian memberi Anda matriks yang mengodekan pola konektivitas penuh dalam bentuk yang dapat diproses dengan aljabar linear

• Clustering: Spectral clustering menggunakan vektor eigen dari L untuk menemukan kelompok yang luput dari metode berbasis jarak murni. Ia bekerja baik ketika klaster tidak konveks atau tidak dapat dipisahkan secara linear

• Pembelajaran semi-terawasi: Banyak metode semi-terawasi menggunakan graph Laplacian untuk menyebarkan label dari node berlabel ke yang tidak berlabel. Asumsinya adalah node yang terhubung kemungkinan berbagi label yang sama, dan Laplacian mengkuantifikasi seberapa mulus label seharusnya bervariasi di seluruh graf

• Manifold learning: Algoritma seperti Laplacian Eigenmaps menggunakan graph Laplacian untuk menemukan representasi berdimensi rendah dari data berdimensi tinggi. Vektor eigen dari L memetakan titik yang berdekatan di ruang asli ke titik yang berdekatan di ruang tereduksi

• Ekstraksi fitur citra: Laplacian diskret mendeteksi tepi dan wilayah dengan perubahan intensitas cepat. Fitur-fitur tersebut langsung masuk ke pipeline visi komputer klasik maupun sebagai prior dalam arsitektur deep learning

Singkatnya, Laplacian adalah salah satu dari sedikit alat matematika yang skalanya naik dari satu persamaan kalkulus hingga ke graph neural network berskala besar.

Penutup

Laplacian bermula sebagai operator kalkulus, cara untuk mengukur kelengkungan dalam fungsi kontinu. Saat Anda sampai ke ML berbasis graf, ia menjadi matriks yang mengodekan struktur seluruh jaringan. Gagasan intinya persis sama, hanya bentuknya yang berbeda.

Daftarkan diri Anda pada kursus Linear Algebra for Data Science in R untuk memperoleh pengalaman langsung dengan banyak konsep dan topik yang dibahas dalam artikel ini.