Giải thích Laplacian: Từ Giải tích đến ML

Laplacian xuất hiện trong các thuật toán dựa trên đồ thị, quy trình xử lý ảnh và phân cụm phổ. Vì vậy, nếu bạn đang xây dựng các mô hình làm việc với đồ thị, hình ảnh hoặc dữ liệu nhiều chiều, Laplacian không phải là phần toán học nền tảng có cũng được. Chính nó là thứ đang thực sự vận hành bên dưới.

Trong bài viết này, tôi sẽ trình bày Laplacian từ gốc rễ: phần toán phía sau, trực giác hình học, Laplacian trên đồ thị và dạng ma trận của nó, cùng cách nó được dùng trong các ứng dụng học máy thực tế.

Bạn cần một phần mở đầu thực tiễn về phương trình vi phân? Hãy đọc bài viết gần đây của chúng tôi để đi từ nền tảng đến các ứng dụng học máy thực tiễn.

Laplacian là gì?

Laplacian là một toán tử vi phân bậc hai. Nó cho bạn biết một hàm cong như thế nào tại mỗi điểm.

Đôi khi bạn sẽ thấy nó được mô tả là phân kỳ của gradient.

Và đó là chìa khóa để hiểu toán tử này thực sự làm gì:

• Gradient cho bạn biết hướng mà hàm tăng nhanh nhất
• Phân kỳ đo xem dòng chảy đó lan ra hay hội tụ lại.

Khi kết hợp, Laplacian cho bạn biết một điểm là đỉnh cục bộ, đáy cục bộ, hay vùng phẳng ở giữa.

Nói đơn giản, Laplacian đo lường mức độ mà giá trị của hàm tại một điểm khác với giá trị trung bình của các điểm lân cận. Nếu Laplacian bằng 0, hàm ở trạng thái "cân bằng" cục bộ. Dương nghĩa là điểm nằm thấp hơn xung quanh. Âm nghĩa là điểm nằm cao hơn chúng.

Công thức

Trong 2D, với hàm f(x, y):

Công thức Laplacian 2D

Trong 3D, với hàm f(x, y, z):

Công thức Laplacian 3D

Mẫu thức này giữ đúng trong mọi số chiều - bạn cộng các đạo hàm riêng bậc hai theo từng trục. Điều này khiến Laplacian rất phù hợp với dữ liệu nhiều chiều, cũng chính là lý do nó xuất hiện thường xuyên trong học máy.

Công thức Laplacian trong Giải tích Nhiều biến

Công thức Laplacian ngắn gọn hơn bạn kỳ vọng đối với một thứ xuất hiện khắp nơi trong học máy.

Trong 3D, với hàm f(x, y, z), nó trông như sau:

Công thức Laplacian 3D

Hết. Bạn đang cộng các đạo hàm riêng bậc hai theo từng chiều.

Mỗi hạng tử hỏi cùng một câu theo trục của nó: hàm đang cong lên, cong xuống, hay phẳng? Khi bạn cộng các câu trả lời đó, bạn nhận được một con số mô tả độ cong tổng thể tại điểm đó.

Từ 3D đến n chiều

Công thức khái quát hóa lên n chiều. Đây là công thức tổng quát cho một hàm với n chiều đầu vào:

Khái quát công thức Laplacian

Đó là lý do Laplacian hoạt động tốt trong học máy, nơi dữ liệu của bạn thường nằm trong hàng trăm hoặc hàng nghìn chiều. Toán tử chỉ việc cộng độ cong theo từng chiều.

Kết nối với tối ưu hóa

Nếu bạn đã làm việc với gradient descent, bạn vốn đã nghĩ về đạo hàm bậc nhất - hướng nào là xuống dốc? Laplacian đưa bạn đi thêm một bước.

Đạo hàm bậc hai cho bạn biết hình dạng của ngọn đồi đó.

Một Laplacian dương lớn tại một điểm nghĩa là hàm cong mạnh lên theo mọi hướng - bạn ở gần một điểm cực tiểu. Giá trị âm lớn nghĩa là bạn ở gần điểm cực đại. Gần 0 nghĩa là bề mặt phẳng cục bộ.

Thông tin về độ cong quan trọng trong các phương pháp tối ưu hóa bậc hai, vốn dùng nó để bước đi thông minh hơn so với gradient descent thuần túy. Laplacian là một cách để tóm tắt độ cong đó thành một giá trị vô hướng duy nhất.

Trực giác hình học: Laplacian đo gì

Dấu của Laplacian tại một điểm cho bạn biết hình dạng của hàm xung quanh điểm đó.

• Nếu ∇²f > 0 tại một điểm, hàm cong lên theo mọi hướng. Điểm thấp hơn so với xung quanh. Đó là tính lồi.

• Nếu ∇²f < 0, hàm cong xuống. Điểm cao hơn so với xung quanh. Đó là tính lõm.

• Nếu ∇²f = 0, hàm phẳng cục bộ. Không có độ cong thuần theo bất kỳ hướng nào.

Đây là phiên bản nhiều biến của kiểm định đạo hàm bậc hai mà bạn đã biết. Trong 1D, đạo hàm bậc hai dương nghĩa là cực tiểu cục bộ và âm nghĩa là cực đại cục bộ. Laplacian mở rộng cùng ý tưởng đó cho bất kỳ số chiều nào bằng cách cộng độ cong trên tất cả các trục.

Mối quan hệ với Hessian

Ma trận Hessian nắm bắt bức tranh độ cong đầy đủ. Đó là ma trận tất cả các đạo hàm riêng bậc hai, và mỗi phần tử mô tả hàm cong như thế nào theo một cặp trục.

Laplacian là vết của Hessian - tổng các phần tử trên đường chéo chính. Nếu Hessian cho bạn phân rã độ cong đầy đủ, Laplacian nén nó xuống một con số duy nhất.

Sự đánh đổi đó quan trọng trong học máy. Hessian đầy đủ tốn kém để tính cho các mô hình nhiều chiều - một mô hình với n tham số sẽ có Hessian n × n. Laplacian cho bạn một tóm tắt vô hướng rẻ về độ cong, xử lý nhanh.

Vì sao điều này quan trọng với học máy

Khi bạn huấn luyện một mô hình, bạn đang dò dẫm trên một bề mặt hàm mất mát. Vùng phẳng khiến học chậm. Vùng lồi khiến bộ tối ưu hóa dễ vượt quá. Laplacian cho bạn một chỉ báo nhanh về tình huống bạn đang ở đâu.

Các phương pháp dựa trên đồ thị dùng Laplacian để đo mức độ mượt mà khi giá trị thay đổi qua các nút của đồ thị. Đó là sự mở rộng trực tiếp của trực giác về độ cong từ hàm liên tục sang cấu trúc rời rạc.

Laplacian và Tối ưu hóa trong Học máy

Gradient descent chỉ dùng đạo hàm bậc nhất.

Gradient cho bạn biết hướng để bước. Nó không cho bạn biết nên bước to cỡ nào. Một gradient dốc trong một thung lũng phẳng, rộng đòi hỏi bước lớn. Cùng gradient dốc đó gần mép vực sắc lại đòi hỏi bước nhỏ. Chỉ với đạo hàm bậc nhất thì không phân biệt được.

Đó là lúc đạo hàm bậc hai xuất hiện.

Độ cong và kích thước bước

Độ cong mô tả tốc độ mà chính gradient đang thay đổi. Độ cong cao nghĩa là bề mặt mất mát uốn mạnh - các bước nhỏ trong không gian tham số tạo ra thay đổi lớn ở gradient. Độ cong thấp nghĩa là bề mặt phẳng và gradient thay đổi chậm.

Nếu bạn bỏ qua độ cong và dùng tốc độ học cố định, bạn đang đoán mò. Quá lớn, bạn sẽ vượt quá ở vùng có độ cong cao. Quá nhỏ, bạn sẽ bò qua vùng phẳng.

Các phương pháp tối ưu hóa bậc hai như phương pháp Newton dùng độ cong để tự động đặt kích thước bước. Chúng chia gradient cho độ cong, bước lớn hơn nơi bề mặt phẳng và nhỏ hơn nơi bề mặt sắc.

Vị trí của Laplacian

Laplacian là vết của Hessian - một vô hướng tóm tắt tổng độ cong tại một điểm. Nó không nắm bắt toàn bộ bức tranh như Hessian, nhưng rẻ để tính và hữu ích như một tín hiệu.

Đây là lời giải thích dễ hiểu cần ghi nhớ:

• Laplacian dương lớn của hàm mất mát tại một điểm nghĩa là bạn ở gần cực tiểu cục bộ - mất mát cong lên theo mọi hướng
• Giá trị âm nghĩa là bạn ở gần cực đại
• Gần 0 nghĩa là bạn ở vùng phẳng hoặc yên ngựa, chính là nơi gradient descent hay bị chững

Ổn định và regularization

Độ cong cũng liên quan đến độ ổn định huấn luyện. Cực tiểu sắc - vùng có độ cong cao - có xu hướng khái quát kém hơn so với vùng phẳng. Một mô hình hội tụ vào cực tiểu sắc nhạy cảm với thay đổi nhỏ ở đầu vào.

Một số kỹ thuật regularization phạt trực tiếp độ cong để đẩy quá trình tối ưu hóa về phía các vùng phẳng hơn của bề mặt mất mát. Laplacian cũng xuất hiện ở đây, như một cách đo và ràng buộc mức độ mà dự đoán của mô hình thay đổi gắt qua không gian đầu vào.

Hiểu về độ cong giúp bạn hiểu vì sao bộ tối ưu của bạn bị chững, vì sao tốc độ học quan trọng đến vậy, và vì sao một số cực tiểu khái quát tốt hơn những cái khác.

Laplacian trên Đồ thị và Ma trận Laplacian

Cho đến giờ, Laplacian sống trong thế giới các hàm liên tục. Nhưng điều gì xảy ra khi dữ liệu của bạn không phải bề mặt trơn tru, mà là một đồ thị?

Đó là lúc Laplacian trên đồ thị xuất hiện. Nó lấy cùng ý tưởng cốt lõi - đo xem giá trị tại một điểm khác thế nào so với hàng xóm - và áp dụng cho các nút và cạnh.

Công thức

Ma trận Laplacian của đồ thị L được định nghĩa là:

Công thức Laplacian trên đồ thị (đơn giản)

Hai ma trận. Hết. Hãy cùng phân tích ý nghĩa của từng ma trận.

Ma trận kề

Ma trận kề A mã hóa các nút nào được nối với nhau. Với một đồ thị có n nút, A là ma trận n × n với A_ij = 1 nếu có cạnh giữa nút i và nút j, và 0 nếu không.

Với một đồ thị vô hướng đơn giản có 3 nút, trong đó nút 1 nối với nút 2 và 3, còn 2 và 3 không nối với nhau:

Ma trận kề

Ma trận bậc

Ma trận bậc D là ma trận đường chéo. Mỗi phần tử đường chéo D_ii là bậc của nút i - số cạnh nối với nó. Mọi phần tử ngoài đường chéo đều bằng 0.

Đây là công thức cho cùng đồ thị đó:

Ma trận bậc

Nút 1 có bậc 2 (nối với hai nút). Nút 2 và 3 mỗi nút có bậc 1.

Ghép lại với nhau

Lấy A trừ khỏi D là được L:

Lấy ma trận kề trừ khỏi ma trận bậc

Mỗi phần tử đường chéo cho bạn biết một nút có bao nhiêu kết nối. Mỗi phần tử ngoài đường chéo L_ij là -1 nếu hai nút i và j được nối, và 0 nếu không.

Nếu bạn nhân L với một vector các giá trị gán cho mỗi nút, kết quả đo xem giá trị của mỗi nút khác với giá trị các nút lân cận của nó bao nhiêu. Đó là phiên bản rời rạc của cùng trực giác về độ cong trước đó - chỉ là áp dụng cho đồ thị thay vì bề mặt liên tục.

Giá trị riêng cho bạn biết gì về một đồ thị

Sức mạnh thực sự của L đến từ các trị riêng và vectơ riêng của nó:

• Trị riêng nhỏ nhất của L luôn là 0. Vectơ riêng tương ứng là một vectơ hằng - mọi nút nhận cùng giá trị. Điều này hợp lý: một hàm hằng có "độ biến thiên" bằng không trên đồ thị.

• Số lượng trị riêng bằng 0 bằng với số thành phần liên thông trong đồ thị. Nếu đồ thị của bạn có ba cụm tách rời, L có ba trị riêng bằng 0. Đây là cách trực tiếp để đọc tính liên thông của đồ thị từ một ma trận.

• Các trị riêng nhỏ khác 0 tương ứng với các vectơ riêng thay đổi chậm trên đồ thị - các nút gần nhau nhận các giá trị tương tự. Các trị riêng lớn tương ứng với các vectơ riêng dao động nhanh giữa các nút kề nhau.

Một điều thú vị: Phổ các trị riêng này chính là thứ mang lại tên gọi cho các phương pháp phổ.

Phân cụm phổ và phát hiện cộng đồng

Phân cụm phổ sử dụng các vectơ riêng của L để tìm cụm trong dữ liệu có cấu trúc đồ thị. Ý tưởng là các vectơ riêng gắn với trị riêng nhỏ gán giá trị tương tự cho các nút được kết nối dày đặc và giá trị khác nhau cho các nút kết nối lỏng lẻo.

Để tìm k cụm, bạn lấy k vectơ riêng tương ứng với k trị riêng nhỏ nhất khác 0 của L, xếp chúng thành một ma trận và chạy k-means trên các hàng. Mỗi hàng là một nút, và vị trí của nó trong không gian chiều thấp này phản ánh lân cận đồ thị của nó.

Cách làm này hiệu quả cho phát hiện cộng đồng trong mạng xã hội, phân cụm tài liệu, phân đoạn ảnh, và bất kỳ nơi nào dữ liệu của bạn có cấu trúc đồ thị tự nhiên. Hai nút kết nối chặt chẽ sẽ nằm gần nhau trong không gian vectơ riêng. Hai nút từ các cộng đồng khác nhau sẽ cách xa nhau.

Laplacian trên đồ thị biến một bài toán tổ hợp khó - tìm các cụm trong đồ thị này - thành một bài toán đại số tuyến tính dễ giải.

Laplacian trong Phân cụm Phổ

Phân cụm phổ là nơi Laplacian trên đồ thị đi từ toán thú vị đến công cụ ML thực dụng.

Ý tưởng cốt lõi là thay vì phân cụm trực tiếp các điểm dữ liệu thô, bạn phân cụm chúng trong một không gian được xác định bởi các vectơ riêng của L. Không gian đó nắm bắt cấu trúc đồ thị, nên bạn có thể thấy nút nào kết nối chặt, nút nào kết nối lỏng, và nút nào thuộc các cộng đồng riêng biệt.

Cách vectơ riêng xác định cụm

Lấy các vectơ riêng k tương ứng với k trị riêng nhỏ nhất khác 0 của L. Xếp chúng thành các cột trong một ma trận. Mỗi hàng của ma trận đó là một nút, nay được biểu diễn như một điểm trong không gian k chiều.

Các vectơ riêng gắn với trị riêng nhỏ thay đổi chậm trên đồ thị. Các nút kết nối dày đặc sẽ có giá trị tương tự trong các vectơ riêng này - và giá trị tương tự nghĩa là hàng tương tự - và hàng tương tự nghĩa là chúng nằm gần nhau trong không gian mới.

Laplacian chưa chuẩn hóa và đã chuẩn hóa

Có hai phiên bản Laplacian trên đồ thị mà bạn sẽ gặp trong thực tế.

Laplacian chưa chuẩn hóa là L = D - A đơn giản. Nó hoạt động tốt khi các nút có bậc xấp xỉ nhau - tức là khi hầu hết các nút có số kết nối tương tự

Laplacian đã chuẩn hóa điều chỉnh mất cân bằng bậc. Có vài biến thể, nhưng phổ biến nhất là:

Công thức Laplacian đã chuẩn hóa

Cách này tái tỷ lệ đóng góp của mỗi nút theo bậc của nó. Trong các đồ thị thế giới thực - mạng xã hội, web, trích dẫn - có nút có hàng trăm kết nối, có nút chỉ một hai. Nếu không chuẩn hóa, các nút bậc cao sẽ lấn át các vectơ riêng và kết quả phân cụm sẽ kém đi.

Hãy dùng Laplacian đã chuẩn hóa theo mặc định trừ khi bạn biết đồ thị của mình có phân bố bậc đồng đều.

Ứng dụng thực tiễn

Phân cụm phổ với Laplacian trên đồ thị xuất hiện trong nhiều tác vụ học máy. Dưới đây là vài ví dụ:

• Phân đoạn ảnh - điểm ảnh thành nút, trọng số cạnh mã hóa độ tương đồng, và các cụm ánh xạ thành vùng ảnh
• Phân cụm tài liệu - tài liệu thành nút, cạnh mã hóa từ khóa chung hoặc trích dẫn
• Phân tích mạng xã hội - người dùng thành nút, cạnh mã hóa kết nối, và các cụm hé lộ cộng đồng
• Hệ thống gợi ý - mục hoặc người dùng tạo thành đồ thị, và phương pháp phổ tìm các nhóm có hành vi tương tự

Bất cứ khi nào dữ liệu của bạn có cấu trúc đồ thị tự nhiên, hoặc bạn có thể xây dựng nó từ độ tương đồng cặp đôi, phân cụm phổ cho bạn một cách có cơ sở để tìm các nhóm mà các phương pháp thuần khoảng cách bỏ lỡ.

Laplacian trong Xử lý Ảnh và Thị giác Máy tính

Laplacian là một trong những công cụ lâu đời nhất trong thị giác máy tính, và đến nay vẫn được dùng tích cực.

Trong xử lý ảnh, cường độ điểm ảnh là hàm số. Laplacian đo xem cường độ của một điểm ảnh khác với lân cận của nó thế nào. Nơi cường độ thay đổi chậm, Laplacian gần 0. Nơi thay đổi gắt - tại cạnh - Laplacian cho phản hồi mạnh.

Đó là toàn bộ nền tảng của phát hiện cạnh bằng Laplacian.

Vì sao đạo hàm bậc hai tìm ra cạnh

Đạo hàm bậc nhất tìm nơi cường độ đang thay đổi. Đạo hàm bậc hai tìm nơi mà chính sự thay đổi đó đang thay đổi - nói cách khác, nơi tốc độ thay đổi đạt đỉnh rồi giảm.

Tại một cạnh, cường độ tăng rồi bằng phẳng. Đạo hàm bậc nhất nhô lên tại đoạn dốc. Đạo hàm bậc hai - Laplacian - đổi dấu tại đúng đỉnh của đợt nhô đó. Các điểm đổi dấu này đánh dấu chính xác vị trí của cạnh, khiến Laplacian xác định vị trí cạnh chính xác hơn các phương pháp bậc nhất như bộ lọc Sobel.

Kernel Laplacian rời rạc

Trong thực tế, ảnh là lưới điểm ảnh, không phải hàm liên tục. Laplacian liên tục được xấp xỉ bằng một kernel tích chập - một ma trận nhỏ trượt qua ảnh.

Kernel Laplacian rời rạc chuẩn 3×3 trông như sau:

Kernel Laplacian rời rạc 3x3

Trọng số ở giữa là -4 và bốn hàng xóm trực tiếp mỗi ô nhận +1. Khi bạn áp dụng kernel này lên một điểm ảnh, bạn đang tính hiệu giữa cường độ điểm ảnh đó và trung bình của bốn hàng xóm - phiên bản rời rạc của câu hỏi "điểm này so với xung quanh thế nào" như trước.

Lưu ý thực hành

Lọc Laplacian thô rất nhạy với nhiễu. Một điểm ảnh nhiễu đơn lẻ tạo ra đỉnh cường độ sắc, và Laplacian sẽ gắn cờ nó như một cạnh.

Cách khắc phục tiêu chuẩn là làm mờ ảnh trước bằng Gaussian, sau đó áp dụng Laplacian. Sự kết hợp này gọi là Laplacian of Gaussian (LoG). Gaussian triệt nhiễu, và Laplacian tìm cạnh thực.

Trong học sâu, mạng nơ-ron tích chập tự học các bộ lọc phát hiện cạnh từ dữ liệu - nhưng các bộ lọc học được đó thường giống kernel Laplacian. Vì vậy, theo một cách nào đó, toán học khiến Laplacian hữu dụng trong thị giác máy tính cổ điển cũng là toán học mà mạng nơ-ron tự khám phá lại.

Laplacian Rời rạc so với Liên tục

Laplacian là ba ý tưởng liên quan xuất hiện trong các ngữ cảnh khác nhau.

Hiểu bạn đang làm việc với phiên bản nào sẽ giúp tránh nhiều nhầm lẫn khi bạn di chuyển giữa giáo trình giải tích, mã số học và các bài báo ML về đồ thị.

Laplacian liên tục

Laplacian liên tục là cái đến từ giải tích. Với một hàm trơn f xác định trên một không gian liên tục, nó là tổng các đạo hàm riêng bậc hai:

Laplacian liên tục

Phiên bản này giả định hàm của bạn trơn và khả vi mọi nơi. Nó là nền tảng lý thuyết - nhưng dữ liệu thực không bao giờ liên tục. Bạn không thể tính đạo hàm chính xác trên một lưới điểm ảnh hay một bảng đo đạc.

Laplacian rời rạc

Khi bạn chuyển từ hàm liên tục sang dữ liệu được lấy mẫu, đạo hàm được thay bằng sai phân hữu hạn - các xấp xỉ tính từ giá trị lân cận.

Với một hàm 1D được lấy mẫu tại các điểm cách đều, đạo hàm bậc hai rời rạc tại điểm i là:

Laplacian rời rạc

Bạn đang so sánh giá trị tại i với hai hàng xóm. Cùng ý tưởng mở rộng lên lưới 2D (ảnh), khối 3D, và hơn thế. Các kernel tích chập trong phần xử lý ảnh chính là thứ này - xấp xỉ sai phân hữu hạn của Laplacian liên tục, áp dụng trên lưới điểm ảnh.

Sự rời rạc hóa này khiến Laplacian có thể tính được trong các phương pháp số và pipeline ML. Bất cứ khi nào bạn áp dụng bộ lọc Laplacian trong mã, bạn đang chạy một xấp xỉ sai phân hữu hạn, không phải toán tử giải tích chính xác.

Laplacian trên đồ thị

Laplacian trên đồ thị đưa việc rời rạc hóa đi xa hơn một bước. Thay vì một lưới đều với khoảng cách đồng nhất, bạn có một tập nút bất kỳ được nối bằng các cạnh có trọng số khác nhau.

Không có khái niệm "điểm ảnh lân cận" ở đây - chỉ có các nút và các kết nối giữa chúng. Laplacian trên đồ thị L = D - A thay thế cấu trúc sai phân hữu hạn bằng cấu trúc kề. Câu hỏi cốt lõi vẫn vậy: giá trị của một nút so với các hàng xóm như thế nào? Nhưng "hàng xóm" giờ được định nghĩa bởi đồ thị, không phải bởi gần không gian.

Vì sao điều này quan trọng trong ML

Hầu hết dữ liệu ML không sống trên một lưới đều. Phân tử, mạng xã hội, đồ thị tri thức và đám mây điểm 3D đều có cấu trúc bất quy tắc. Bạn không thể áp dụng Laplacian sai phân hữu hạn tiêu chuẩn cho chúng.

Laplacian trên đồ thị giải quyết điều này bằng cách biểu diễn rõ ràng cấu trúc lân cận qua ma trận kề. Đó là lý do mạng nơ-ron đồ thị và các phương pháp phổ có thể áp dụng các phép toán dựa trên Laplacian cho dữ liệu không có hệ tọa độ tự nhiên.

Ví dụ giải bài: Tính một Laplacian

Hãy làm cụ thể với hai ví dụ - một liên tục, một dựa trên đồ thị.

Ví dụ 1: Laplacian liên tục của f(x, y) = x² + y²

Xét hàm f(x, y) = x² + y². Đây là một paraboloid đơn giản - hình cái bát cong lên theo mọi hướng.

Để tính Laplacian, bạn cần đạo hàm riêng bậc hai theo từng biến.

Trước hết, theo x:

Tính Laplacian liên tục (1)

Sau đó theo y:

Tính Laplacian liên tục (2)

Và giờ chỉ việc cộng chúng lại:

Tính Laplacian liên tục (3)

Laplacian là một hằng số 4 ở mọi nơi. Điều đó hợp lý vì một paraboloid có cùng độ cong tại mọi điểm. Giá trị dương cho biết hàm cong lên theo mọi hướng, phù hợp với hình cái bát.

Ví dụ 2: Laplacian trên đồ thị cho một đồ thị nhỏ

Xét một đồ thị có 4 nút và các cạnh sau:

• Nút 1 nối với nút 2 và 3
• Nút 2 nối với nút 1 và 4
• Nút 3 nối với nút 1
• Nút 4 nối với nút 2

Ma trận kề A mã hóa các kết nối:

Tính Laplacian trên đồ thị (1)

Ma trận bậc D đặt số kết nối của mỗi nút lên đường chéo:

Tính Laplacian trên đồ thị (2)

Nút 1 và 2 mỗi nút có 2 kết nối. Nút 3 và 4 mỗi nút có 1.

Cuối cùng, lấy hiệu để có L = D - A:

Tính Laplacian trên đồ thị (3)

Đọc ma trận này như sau: Hàng 1 nói: nút 1 có bậc 2, và nối với nút 2 và 3 (các phần tử -1). Hàng 3 nói: nút 3 có bậc 1, chỉ nối với nút 1. Các số 0 cho biết cặp nút nào không có cạnh chung.

Bạn cũng có thể tính nó trong Python để kiểm chứng:

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)Được hỗ trợ bởi

Tính Laplacian trên đồ thị bằng Python

Những nhầm lẫn thường gặp

Laplacian giống với một vài khái niệm khác, và khác biệt không phải lúc nào cũng rõ ràng qua tên gọi. Trong phần này, tôi sẽ cố loại bỏ mọi điểm gây nhầm lẫn.

Laplacian so với gradient

Gradient ∇f là một vectơ. Nó chỉ hướng tăng nhanh nhất và độ lớn của nó cho bạn biết hàm tăng nhanh ra sao. Nó dùng đạo hàm bậc nhất.

Laplacian ∇²f là một vô hướng. Nó không cho bạn biết nên đi hướng nào - nó cho bạn biết về hình dạng của hàm tại một điểm. Nó được xây dựng từ đạo hàm bậc hai.

Laplacian so với Hessian

Đây là điều khiến nhiều người hay nhầm nhất.

Hessian H là ma trận các đạo hàm riêng bậc hai. Với một hàm có n đầu vào, đó là ma trận n × n nắm bắt cách gradient thay đổi theo mọi cặp trục. Nó cho bạn bức tranh độ cong đầy đủ.

Laplacian là vết của Hessian - tổng các phần tử đường chéo. Bạn mất thông tin độ cong ngoài đường chéo, nhưng có một con số duy nhất tính nhanh.

Dùng Hessian khi bạn cần phân rã độ cong đầy đủ. Dùng Laplacian khi một tóm tắt vô hướng là đủ.

Laplacian đồ thị so với toán tử vi phân

Chúng cùng tên và cùng trực giác cốt lõi, nhưng vận hành trên các đối tượng hoàn toàn khác nhau.

Laplacian vi phân tác động lên các hàm trơn, liên tục. Nó đòi hỏi đạo hàm, tức giả định hàm của bạn khả vi mọi nơi.

Laplacian trên đồ thị L = D - A tác động lên đồ thị - cấu trúc rời rạc với nút và cạnh. Không có đạo hàm nào tham gia. Nó đo xem giá trị tại mỗi nút khác với hàng xóm của nó bằng các phép toán ma trận.

Mối liên hệ là về mặt khái niệm, không phải tính toán. Cả hai đều đo sai lệch cục bộ so với trung bình lân cận, nhưng hoàn toàn khác nhau.

Quy ước dấu

Một số lĩnh vực định nghĩa Laplacian với dấu âm: -∇²f. Bạn sẽ thấy điều này trong vật lý và trong một số bài báo ML về mạng nơ-ron đồ thị. Laplacian âm −L là nửa xác định dương, điều này có các tính chất đẹp hơn cho một số bài toán tối ưu và làm phân tích trị riêng gọn hơn.

Khi bạn đọc một bài báo và các trị riêng của Laplacian đều không âm, hãy kiểm tra xem họ đang dùng L hay -L. Về mặt toán học là tương đương, nhưng trộn lẫn quy ước có thể dẫn đến kết quả sai.

Vì sao Laplacian quan trọng trong Khoa học Dữ liệu

Đến đây, bạn đã thấy Laplacian xuất hiện trong giải tích, lý thuyết đồ thị, xử lý ảnh và tối ưu hóa. Cùng một toán tử đang giải cùng một vấn đề nền tảng trong các ngữ cảnh khác nhau: đo xem giá trị tại một điểm liên hệ với xung quanh như thế nào.

Dưới đây là nơi điều đó xuất hiện trong khoa học dữ liệu:

• ML dựa trên đồ thị: Laplacian trên đồ thị L = D - A là nền tảng của các phương pháp phổ. Bất cứ khi nào dữ liệu của bạn có cấu trúc đồ thị tự nhiên, Laplacian cho bạn một ma trận mã hóa toàn bộ mẫu kết nối dưới dạng mà bạn có thể làm đại số tuyến tính trên đó

• Phân cụm: Phân cụm phổ dùng các vectơ riêng của L để tìm các nhóm mà các phương pháp thuần khoảng cách bỏ lỡ. Nó hoạt động tốt khi các cụm không lồi hoặc không tách tuyến tính

• Học bán giám sát: Nhiều phương pháp bán giám sát dùng Laplacian trên đồ thị để lan truyền nhãn từ nút có nhãn sang nút chưa có. Giả định là các nút kết nối có khả năng chia sẻ cùng nhãn, và Laplacian định lượng mức độ nhãn nên biến thiên mượt trên đồ thị

• Học đa tạp: Các thuật toán như Laplacian Eigenmaps sử dụng Laplacian trên đồ thị để tìm biểu diễn chiều thấp của dữ liệu nhiều chiều. Các vectơ riêng của L ánh xạ các điểm gần nhau trong không gian gốc thành gần nhau trong không gian giảm chiều

• Trích xuất đặc trưng ảnh: Laplacian rời rạc phát hiện cạnh và vùng thay đổi cường độ nhanh. Những đặc trưng đó đi thẳng vào cả pipeline thị giác máy tính cổ điển lẫn làm prior trong kiến trúc học sâu

Tóm lại, Laplacian là một trong số ít công cụ toán học mở rộng từ một phương trình giải tích đơn lẻ cho đến các mạng nơ-ron đồ thị lớn.

Kết luận

Laplacian khởi đầu là một toán tử giải tích, cách để đo độ cong trong các hàm liên tục. Khi đến học máy dựa trên đồ thị, nó là một ma trận mã hóa cấu trúc của cả một mạng. Ý tưởng cốt lõi vẫn y nguyên, chỉ hình thức là khác.

Đăng ký khóa Đại số tuyến tính cho Khoa học Dữ liệu bằng R của chúng tôi để thực hành nhiều khái niệm và chủ đề được đề cập trong bài viết này.