ทำความเข้าใจลาปลาซเชียน: จากแคลคูลัสสู่ ML

ลาปลาซเชียนปรากฏอยู่ในอัลกอริทึมแบบกราฟ สายการประมวลผลภาพ และสเปกทรัลคลัสเตอริง ดังนั้นหากกำลังสร้างโมเดลที่ทำงานกับกราฟ ภาพ หรือข้อมูลมิติสูง ลาปลาซเชียนไม่ใช่คณิตศาสตร์พื้นหลังที่เลือกจะรู้หรือไม่ก็ได้ แต่มันคือสิ่งที่ลงมือทำงานอยู่เบื้องหลังจริงๆ

บทความนี้จะอธิบายลาปลาซเชียนตั้งแต่พื้นฐาน: คณิตศาสตร์ที่อยู่เบื้องหลัง สัญชาตญาณเชิงเรขาคณิต ลาปลาซเชียนบนกราฟและรูปแบบเมทริกซ์ ตลอดจนการใช้งานจริงในงานแมชชีนเลิร์นนิง

ต้องการบทนำเชิงปฏิบัติเรื่องสมการเชิงอนุพันธ์หรือไม่? อ่านบทความล่าสุดของเราเพื่อก้าวจากพื้นฐานสู่งานประยุกต์ในแมชชีนเลิร์นนิง

ลาปลาซเชียนคืออะไร?

ลาปลาซเชียนเป็นตัวดำเนินการเชิงอนุพันธ์อันดับสอง ใช้บอกว่าฟังก์ชันโค้งงออย่างไร ณ จุดใดๆ

บางครั้งจะอธิบายว่าเป็นไดเวอร์เจนซ์ของเกรเดียนต์

และนั่นคือกุญแจสำคัญในการเข้าใจว่าตัวดำเนินการนี้ทำอะไรจริง:

• เกรเดียนต์บอกทิศทางที่ฟังก์ชันเพิ่มขึ้นเร็วที่สุด
• ไดเวอร์เจนซ์วัดว่าการไหลนั้นกระจายออกหรือดึงเข้าหากัน

เมื่อรวมกัน ลาปลาซเชียนจะบอกได้ว่าจุดนั้นเป็นยอดเขาในท้องถิ่น ก้นหุบเขาในท้องถิ่น หรือแบนราบระหว่างกลาง

หากพูดแบบเข้าใจง่าย ลาปลาซเชียนวัดว่าค่าของฟังก์ชัน ณ จุดหนึ่งต่างจากค่าเฉลี่ยของเพื่อนบ้านมากน้อยเพียงใด หากลาปลาซเชียนเป็นศูนย์ ฟังก์ชันจะ “สมดุล” ในเชิงเฉพาะที่ ค่าเป็นบวกหมายถึงจุดนั้นอยู่ต่ำกว่าบริเวณรอบๆ ค่าเป็นลบหมายถึงอยู่สูงกว่า

สูตร

ใน 2 มิติ สำหรับฟังก์ชัน f(x, y):

สูตรลาปลาซเชียน 2 มิติ

ใน 3 มิติ สำหรับฟังก์ชัน f(x, y, z):

สูตรลาปลาซเชียน 3 มิติ

รูปแบบนี้ใช้ได้ในจำนวนมิติเท่าใดก็ได้ — เพียงบวกอนุพันธ์ย่อยอันดับสองตามแต่ละแกน ทำให้ลาปลาซเชียนเหมาะกับข้อมูลมิติสูง ซึ่งเป็นเหตุผลที่พบได้บ่อยในแมชชีนเลิร์นนิง

สูตรลาปลาซเชียนในแคลคูลัสหลายตัวแปร

สูตรลาปลาซเชียนนั้นสั้นกว่าที่คาดไว้สำหรับสิ่งที่ปรากฏกว้างขวางในแมชชีนเลิร์นนิง

ใน 3 มิติ สำหรับฟังก์ชัน f(x, y, z) จะมีหน้าตาแบบนี้:

สูตรลาปลาซเชียน 3 มิติ

เท่านี้เอง เพียงบวกอนุพันธ์ย่อยอันดับสองตามแต่ละมิติ

แต่ละพจน์ถามคำถามเดียวกันตามแกนของมัน: ฟังก์ชันกำลังโค้งขึ้น โค้งลง หรือแบน? เมื่อรวมคำตอบเหล่านั้นเข้าด้วยกัน จะได้ตัวเลขเดียวที่อธิบายความโค้งโดยรวม ณ จุดนั้น

จาก 3 มิติสู่น มิติ

สูตรนี้ทั่วไปได้เป็น n มิติ นี่คือสูตรทั่วไปสำหรับฟังก์ชันที่มีมิติอินพุต n:

การทำให้สูตรลาปลาซเชียนเป็นกรณีทั่วไป

นี่คือเหตุผลที่ลาปลาซเชียนทำงานได้ดีในแมชชีนเลิร์นนิง ซึ่งข้อมูลมักอาศัยอยู่ในหลายร้อยหรือหลายพันมิติ ตัวดำเนินการเพียงสรุปความโค้งตามแต่ละมิติ

ความเชื่อมโยงกับการหาค่าเหมาะที่สุด

หากเคยทำงานกับเกรเดียนต์ดิเซนต์ ก็ได้คิดถึงอนุพันธ์อันดับหนึ่งแล้ว — ทางไหนคือทางลงเขา? ลาปลาซเชียนพาไปอีกขั้น

อนุพันธ์อันดับสองบอกเกี่ยวกับรูปร่างของเนินนั้น

ค่าลาปลาซเชียนเป็นบวกขนาดใหญ่ ณ จุดหนึ่ง หมายถึงฟังก์ชันโค้งขึ้นอย่างชันทุกทิศทาง — อยู่ใกล้ค่าต่ำสุดเฉพาะที่ ค่าเป็นลบขนาดใหญ่หมายถึงอยู่ใกล้ค่าสูงสุด ใกล้ศูนย์หมายถึงพื้นผิวแบนในเชิงเฉพาะที่

ข้อมูลความโค้งนี้สำคัญในวิธีหาค่าเหมาะที่สุดอันดับสอง ซึ่งใช้เพื่อก้าวให้ชาญฉลาดกว่าเกรเดียนต์ดิเซนต์ธรรมดา ลาปลาซเชียนเป็นหนึ่งในวิธีสรุปความโค้งเป็นสเกลาร์เพียงค่าเดียว

สัญชาตญาณเชิงเรขาคณิต: ลาปลาซเชียนวัดอะไร

เครื่องหมายของลาปลาซเชียน ณ จุดหนึ่งบอกถึงรูปร่างของฟังก์ชันรอบๆ จุดนั้น

• ถ้า ∇²f > 0 ฟังก์ชันโค้งขึ้นทุกทิศทาง จุดนั้นต่ำกว่าบริเวณรอบๆ นั่นคือความนูน (convexity)

• ถ้า ∇²f < 0 ฟังก์ชันโค้งลง จุดนั้นสูงกว่าบริเวณรอบๆ นั่นคือความเว้า (concavity)

• ถ้า ∇²f = 0 ฟังก์ชันแบนในเชิงเฉพาะที่ ไม่มีความโค้งสุทธิในทิศทางใด

นี่คือเวอร์ชันหลายมิติของการทดสอบอนุพันธ์อันดับสองที่คุ้นเคย ใน 1 มิติ อนุพันธ์อันดับสองเป็นบวกหมายถึงค่าต่ำสุดเฉพาะที่ และเป็นลบหมายถึงค่าสูงสุดเฉพาะที่ ลาปลาซเชียนขยายแนวคิดเดียวกันนี้ไปยังจำนวนมิติเท่าใดก็ได้ด้วยการรวมความโค้งตามทุกแกน

ความสัมพันธ์กับเฮสเซียน

เมทริกซ์เฮสเซียนจับภาพความโค้งทั้งหมด เป็นเมทริกซ์ของอนุพันธ์ย่อยอันดับสองทั้งหมด แต่ละสมาชิกอธิบายว่าฟังก์ชันโค้งตามคู่แกนอย่างไร

ลาปลาซเชียนคือทรซของเฮสเซียน — ผลรวมของสมาชิกบนแนวทแยง เฮสเซียนให้ภาพความโค้งครบถ้วน ส่วนลาปลาซเชียนยุบให้เหลือตัวเลขเดียว

ข้อแลกเปลี่ยนนี้สำคัญในแมชชีนเลิร์นนิง เฮสเซียนเต็มมีต้นทุนคำนวณสูงสำหรับโมเดลมิติสูง — โมเดลที่มีพารามิเตอร์ n จะมีเฮสเซียนขนาด n × n ลาปลาซเชียนให้สรุปเชิงสเกลาร์ของความโค้งที่คำนวณได้รวดเร็ว

เหตุใดจึงสำคัญต่อแมชชีนเลิร์นนิง

เมื่อฝึกโมเดล กำลังเดินบนพื้นผิวของ loss พื้นที่แบนหมายถึงการเรียนรู้ช้า พื้นที่นูนหมายถึงตัวหาค่าเหมาะที่สุดอาจก้าวเกิน ลาปลาซเชียนช่วยอ่านอย่างรวดเร็วว่าอยู่ในสถานการณ์ใด

วิธีการบนกราฟใช้ลาปลาซเชียนเพื่อวัดว่าค่าเปลี่ยนแปลงอย่างราบรื่นเพียงใดข้ามโหนดของกราฟ นี่คือการขยายสัญชาตญาณเรื่องความโค้งจากฟังก์ชันต่อเนื่องสู่โครงสร้างเชิงไม่ต่อเนื่องโดยตรง

ลาปลาซเชียนและการหาค่าเหมาะที่สุดในแมชชีนเลิร์นนิง

เกรเดียนต์ดิเซนต์ใช้เพียงอนุพันธ์อันดับหนึ่ง

เกรเดียนต์บอกทิศทางที่จะก้าว แต่ไม่บอกว่าควรก้าวใหญ่เพียงใด เกรเดียนต์ชันในหุบเขากว้างและแบนควรก้าวใหญ่ เกรเดียนต์ชันเท่าเดิมใกล้หน้าผาชันควรก้าวเล็ก อนุพันธ์อันดับหนึ่งลำพังบอกความต่างนี้ไม่ได้

นั่นคือจุดที่อนุพันธ์อันดับสองเข้ามา

ความโค้งและขนาดก้าว

ความโค้งอธิบายว่าเกรเดียนต์เองเปลี่ยนเร็วแค่ไหน ความโค้งสูงหมายถึงพื้นผิวของ loss โค้งงออย่างชัน — ก้าวเล็กในปริภูมิพารามิเตอร์ทำให้เกรเดียนต์เปลี่ยนมาก ความโค้งต่ำหมายถึงพื้นผิวแบนและเกรเดียนต์เปลี่ยนช้า

ถ้ามองข้ามความโค้งและใช้ค่าเรียนรู้คงที่ ก็เท่ากับเดาสุ่ม ใหญ่เกินไปจะก้าวเกินในบริเวณความโค้งสูง เล็กเกินไปจะคลานช้าในบริเวณแบน

วิธีหาค่าเหมาะที่สุดอันดับสอง เช่น วิธีของนิวตัน ใช้ความโค้งเพื่อตั้งขนาดก้าวโดยอัตโนมัติ โดยหารเกรเดียนต์ด้วยความโค้ง ก้าวใหญ่ในบริเวณแบนและก้าวเล็กในบริเวณชัน

ลาปลาซเชียนอยู่ตรงไหน

ลาปลาซเชียนเป็นทรซของเฮสเซียน — สเกลาร์เดียวที่สรุปความโค้งรวม ณ จุดหนึ่ง มันไม่ได้จับภาพทั้งหมดแบบเฮสเซียน แต่คำนวณถูกและใช้เป็นสัญญาณได้ดี

นี่คือคำอธิบายแบบภาษาคนที่ควรจำไว้:

• ค่าลาปลาซเชียนของ loss เป็นบวกขนาดใหญ่ ณ จุดหนึ่ง หมายถึงอยู่ใกล้ค่าต่ำสุดเฉพาะที่ — loss โค้งขึ้นทุกทิศทาง
• ค่าเป็นลบหมายถึงอยู่ใกล้ค่าสูงสุด
• ใกล้ศูนย์หมายถึงอยู่ในบริเวณแบนหรืออานม้า ซึ่งเป็นจุดที่เกรเดียนต์ดิเซนต์มักจะติด

เสถียรภาพและรีกูลไรเซชัน

ความโค้งเชื่อมโยงกับเสถียรภาพในการฝึกด้วย ค่าต่ำสุดที่แหลม — พื้นที่ที่มีความโค้งสูง — มักทั่วไป (generalize) ได้แย่กว่าค่าต่ำสุดที่แบน โมเดลที่ลู่เข้าสู่ค่าต่ำสุดแหลมไวต่อการเปลี่ยนแปลงเล็กน้อยของอินพุต

เทคนิครีกูลไรเซชันบางอย่างลงโทษความโค้งโดยตรงเพื่อผลักการหาค่าเหมาะที่สุดไปยังบริเวณที่แบนกว่าของพื้นผิว loss ลาปลาซเชียนก็ปรากฏที่นี่เช่นกัน ในฐานะตัววัดและจำกัดว่าคำทำนายของโมเดลเปลี่ยนแปลงอย่างชันเพียงใดข้ามปริภูมิอินพุต

ความเข้าใจเรื่องความโค้งช่วยให้เข้าใจว่าทำไมตัวหาค่าเหมาะที่สุดถึงหยุดชะงัก ทำไมค่าเรียนรู้จึงสำคัญมาก และทำไมค่าต่ำสุดบางแบบจึงทั่วไปได้ดีกว่า

ลาปลาซเชียนบนกราฟและเมทริกซ์ลาปลาซเชียน

จนถึงตอนนี้ ลาปลาซเชียนอยู่ในโลกของฟังก์ชันต่อเนื่อง แต่ถ้าข้อมูลไม่ใช่พื้นผิวเรียบ หากเป็นกราฟล่ะ?

ตรงนี้เองที่ลาปลาซเชียนบนกราฟเข้ามา ใช้แนวคิดเดียวกัน — วัดว่าค่าที่จุดหนึ่งต่างจากเพื่อนบ้านมากน้อยเพียงใด — แล้วนำไปใช้กับโหนดและขอบ

สูตร

ลาปลาซเชียนบนกราฟ L นิยามดังนี้:

สูตรลาปลาซเชียนบนกราฟ (อย่างย่อ)

มีแค่สองเมทริกซ์เท่านั้น มาดูความหมายของแต่ละตัวกัน

เมทริกซ์เพื่อนบ้าน (adjacency)

เมทริกซ์เพื่อนบ้าน A เข้ารหัสว่าโหนดใดเชื่อมกับโหนดใด สำหรับกราฟที่มีโหนด n ตัว A เป็นเมทริกซ์ขนาด n × n โดย A_ij = 1 หากมีขอบระหว่างโหนด i และโหนด j และเป็น 0 ในกรณีอื่น

สำหรับกราฟไม่กำกับแบบง่ายที่มี 3 โหนด โดยโหนด 1 เชื่อมกับโหนด 2 และ 3 แต่โหนด 2 และ 3 ไม่เชื่อมกันเอง:

เมทริกซ์เพื่อนบ้าน

เมทริกซ์ดีกรี

เมทริกซ์ดีกรี D เป็นเมทริกซ์ทแยงมุม ค่าบนแนวทแยงแต่ละตัว D_ii คือดีกรีของโหนด i — จำนวนขอบที่เชื่อมกับมัน ค่านอกแนวทแยงทั้งหมดเป็นศูนย์

นี่คือสูตรสำหรับกราฟเดียวกัน:

เมทริกซ์ดีกรี

โหนด 1 มีดีกรี 2 (เชื่อมกับสองโหนด) ส่วนโหนด 2 และ 3 มีดีกรีอย่างละ 1

เมื่อนำมารวมกัน

ลบ A ออกจาก D จะได้ L:

ลบเมทริกซ์เพื่อนบ้านออกจากเมทริกซ์ดีกรี

ค่าสมาชิกบนแนวทแยงบอกจำนวนการเชื่อมต่อของแต่ละโหนด ค่านอกแนวทแยง L_ij เป็น -1 ถ้าโหนด i และ j เชื่อมกัน และเป็น 0 หากไม่เชื่อม

ถ้านำ L คูณเวกเตอร์ของค่าที่กำหนดให้แต่ละโหนด ผลลัพธ์จะวัดว่าค่าของแต่ละโหนดต่างจากค่าเพื่อนบ้านมากน้อยเพียงใด นี่คือเวอร์ชันไม่ต่อเนื่องของสัญชาตญาณเรื่องความโค้งแบบเดิม — เพียงแต่นำไปใช้กับกราฟแทนพื้นผิวต่อเนื่อง

อีเจนแวลูบอกอะไรเกี่ยวกับกราฟ

พลังที่แท้จริงของ L มาจากอีเจนแวลูและอีเจนเวกเตอร์ของมัน:

• อีเจนแวลูที่เล็กที่สุดของ L เป็น 0 เสมอ อีเจนเวกเตอร์ที่สอดคล้องกันเป็นเวกเตอร์ค่าคงที่ — ทุกโหนดได้ค่าเดียวกัน ซึ่งสมเหตุสมผล: ฟังก์ชันค่าคงที่ไม่มี “ความแปรผัน” บนกราฟ

• จำนวนอีเจนแวลูศูนย์เท่ากับจำนวนคอมโพเนนต์ที่เชื่อมต่อกันในกราฟ หากกราฟมีสามคลัสเตอร์ที่ไม่เชื่อมกัน L จะมีอีเจนแวลูศูนย์สามค่า นี่คือวิธีอ่านความเชื่อมต่อของกราฟจากเมทริกซ์โดยตรง

• อีเจนแวลูบวกขนาดเล็กสอดคล้องกับอีเจนเวกเตอร์ที่เปลี่ยนช้าๆ บนกราฟ — โหนดที่อยู่ใกล้กันได้ค่าคล้ายกัน อีเจนแวลูขนาดใหญ่สอดคล้องกับอีเจนเวกเตอร์ที่สลับค่าอย่างรวดเร็วระหว่างโหนดที่เชื่อมกัน

เกร็ดน่ารู้: สเปกตรัมของอีเจนแวลูนี่เองที่ทำให้วิธีการเชิงสเปกตรัลได้ชื่อนี้

สเปกทรัลคลัสเตอริงและการค้นหาชุมชน

สเปกทรัลคลัสเตอริงใช้อีเจนเวกเตอร์ของ L เพื่อหาคลัสเตอร์ในข้อมูลที่มีโครงสร้างเป็นกราฟ แนวคิดคืออีเจนเวกเตอร์ที่สอดคล้องกับอีเจนแวลูเล็กจะกำหนดค่าใกล้เคียงกันให้โหนดที่เชื่อมกันหนาแน่น และกำหนดค่าต่างกันให้โหนดที่เชื่อมกันหลวมๆ

เพื่อหาคลัสเตอร์ k ให้เลือกอีเจนเวกเตอร์ k ตัวที่สอดคล้องกับอีเจนแวลูที่ไม่เป็นศูนย์ที่เล็กที่สุด k ของ L จากนั้นนำมาต่อเป็นเมทริกซ์คอลัมน์ และรัน k-means บนแถว แต่ละแถวแทนโหนดหนึ่งตัว และตำแหน่งในปริภูมิมิติต่ำนี้สะท้อนเพื่อนบ้านบนกราฟของมัน

วิธีนี้ใช้ได้กับการค้นหาชุมชนในโซเชียลเน็ตเวิร์ก การจัดกลุ่มเอกสาร การแบ่งส่วนภาพ และทุกที่ที่ข้อมูลมีโครงสร้างกราฟตามธรรมชาติ โหนดสองตัวที่เชื่อมกันแน่นจะอยู่ใกล้กันในปริภูมิอีเจนเวกเตอร์ โหนดจากชุมชนต่างกันจะอยู่ห่างกัน

ลาปลาซเชียนบนกราฟทำให้ปัญหาคอมบิเนโทเรียลที่ยาก — หาคลัสเตอร์ในกราฟนี้ — กลายเป็นปัญหาเชิงพีชคณิตเชิงเส้นที่แก้ได้ง่าย

ลาปลาซเชียนในสเปกทรัลคลัสเตอริง

สเปกทรัลคลัสเตอริงคือจุดที่ลาปลาซเชียนบนกราฟก้าวจากคณิตศาสตร์ที่น่าสนใจสู่เครื่องมือ ML ที่ใช้งานได้จริง

แนวคิดหลักคือแทนที่จะจัดกลุ่มจุดข้อมูลดิบโดยตรง ให้จัดกลุ่มในปริภูมิที่นิยามโดยอีเจนเวกเตอร์ของ L ปริภูมินั้นจับโครงสร้างกราฟ จึงเห็นได้ว่าโหนดใดเชื่อมกันแน่น โหนดใดเชื่อมกันหลวม และโหนดใดอยู่คนละชุมชน

อีเจนเวกเตอร์กำหนดคลัสเตอร์อย่างไร

เลือกอีเจนเวกเตอร์ k ตัวที่สอดคล้องกับอีเจนแวลูที่ไม่เป็นศูนย์ที่เล็กที่สุด k ของ L ต่อเป็นเมทริกซ์คอลัมน์ แถวแต่ละแถวของเมทริกซ์นี้คือโหนดหนึ่งตัว ซึ่งขณะนี้แทนเป็นจุดในปริภูมิ k มิติ

อีเจนเวกเตอร์ที่สอดคล้องกับอีเจนแวลูเล็กจะเปลี่ยนแปลงอย่างช้าๆ บนกราฟ โหนดที่เชื่อมกันหนาแน่นจะได้ค่าคล้ายกันในอีเจนเวกเตอร์เหล่านี้ — ค่าคล้ายกันแปลว่าแถวคล้ายกัน — และแถวคล้ายกันแปลว่าตกใกล้กันในปริภูมิใหม่นี้

ลาปลาซเชียนแบบไม่ทำให้อยู่ในสเกลเดียวกันเทียบกับแบบทำให้อยู่ในสเกลเดียวกัน

ลาปลาซเชียนบนกราฟที่ใช้จริงมีสองแบบ

แบบไม่ทำให้อยู่ในสเกลเดียวกันคือสูตรตรงไปตรงมา L = D - A เหมาะเมื่อโหนดมีดีกรีใกล้เคียงกัน — กล่าวคือ โหนดส่วนใหญ่มีจำนวนการเชื่อมต่อพอๆ กัน

แบบทำให้อยู่ในสเกลเดียวกันปรับสำหรับความไม่สมดุลของดีกรี มีหลายรูปแบบ แต่ที่พบบ่อยที่สุดคือ:

สูตรลาปลาซเชียนแบบทำให้อยู่ในสเกลเดียวกัน

สูตรนี้ปรับสเกลส่วนร่วมของแต่ละโหนดด้วยดีกรีของมัน ในกราฟโลกจริง — โซเชียลเน็ตเวิร์ก เว็บ กราฟการอ้างอิง — บางโหนดมีการเชื่อมต่อหลายร้อยครั้ง ขณะที่บางโหนดมีแค่หนึ่งหรือสอง หากไม่ทำ normalization โหนดที่มีดีกรีสูงจะครอบงำอีเจนเวกเตอร์และผลการจัดกลุ่มจะถดถอย

โดยปกติให้ใช้ลาปลาซเชียนแบบทำให้อยู่ในสเกลเดียวกัน เว้นแต่จะรู้ว่ากราฟมีการกระจายดีกรีสม่ำเสมอ

การใช้งานจริง

สเปกทรัลคลัสเตอริงด้วยลาปลาซเชียนบนกราฟปรากฏในงานแมชชีนเลิร์นนิงหลากหลาย นี่คือตัวอย่างบางส่วน:

• การแบ่งส่วนภาพ — พิกเซลกลายเป็นโหนด น้ำหนักขอบเข้ารหัสความคล้าย และคลัสเตอร์แมปเป็นบริเวณของภาพ
• การจัดกลุ่มเอกสาร — เอกสารเป็นโหนด ขอบเข้ารหัสคำที่ใช้ร่วมกันหรือการอ้างอิง
• การวิเคราะห์โซเชียลเน็ตเวิร์ก — ผู้ใช้เป็นโหนด ขอบเข้ารหัสการเชื่อมต่อ และคลัสเตอร์เผยชุมชน
• ระบบแนะนำ — ไอเทมหรือผู้ใช้สร้างกราฟ และวิธีเชิงสเปกตรัลหากลุ่มพฤติกรรมคล้ายกัน

เมื่อใดก็ตามที่ข้อมูลมีโครงสร้างกราฟตามธรรมชาติ หรือสร้างได้จากความคล้ายเป็นคู่ สเปกทรัลคลัสเตอริงจะให้หนทางเชิงหลักการในการหากลุ่มที่วิธีอิงระยะทางล้วนๆ มองไม่เห็น

ลาปลาซเชียนในการประมวลผลภาพและคอมพิวเตอร์วิทัศน์

ลาปลาซเชียนเป็นหนึ่งในเครื่องมือที่เก่าแก่ที่สุดในคอมพิวเตอร์วิทัศน์ และยังถูกใช้งานอยู่จนถึงปัจจุบัน

ในการประมวลผลภาพ ความเข้มของพิกเซลคือฟังก์ชัน ลาปลาซเชียนวัดว่าความเข้มของพิกเซลหนึ่งต่างจากเพื่อนบ้านเพียงใด เมื่อความเข้มเปลี่ยนช้า ลาปลาซเชียนจะใกล้ศูนย์ เมื่อเปลี่ยนอย่างฉับพลัน — บริเวณขอบ — ลาปลาซเชียนจะตอบสนองแรง

นี่คือพื้นฐานทั้งหมดของการตรวจจับขอบด้วยลาปลาซเชียน

ทำไมอนุพันธ์อันดับสองจึงหารอยขอบได้

อนุพันธ์อันดับหนึ่งหาจุดที่ความเข้มกำลังเปลี่ยน อนุพันธ์อันดับสองหาจุดที่ “การเปลี่ยนนั้นเอง” กำลังเปลี่ยน — กล่าวอีกนัยหนึ่ง จุดที่อัตราการเปลี่ยนสูงสุดแล้วลดลง

ที่ขอบ ความเข้มจะไต่ขึ้นแล้วทรงตัว อนุพันธ์อันดับหนึ่งพุ่งสูงที่ช่วงไต่ อนุพันธ์อันดับสอง — ลาปลาซเชียน — ตัดผ่านศูนย์ตรงจุดสูงสุดของยอดนั้น การตัดผ่านศูนย์เหล่านี้บอกตำแหน่งขอบอย่างแม่นยำ ทำให้ลาปลาซเชียนระบุตำแหน่งขอบแม่นกว่าวิธีอนุพันธ์อันดับหนึ่งอย่างตัวกรองโซเบล

เคอร์เนลลาปลาซเชียนแบบไม่ต่อเนื่อง

ในทางปฏิบัติ ภาพคือกริดของพิกเซล ไม่ใช่ฟังก์ชันต่อเนื่อง ลาปลาซเชียนแบบต่อเนื่องจึงถูกประมาณด้วยเคอร์เนลคอนโวลูชัน — เมทริกซ์ขนาดเล็กที่เลื่อนไปบนภาพ

เคอร์เนลลาปลาซเชียนแบบ 3×3 มาตรฐานมีหน้าตาแบบนี้:

เคอร์เนลลาปลาซเชียนแบบ 3x3

ค่าน้ำหนักตรงกลางเป็น -4 และเพื่อนบ้านที่ติดกันสี่ทิศได้ค่า +1 เมื่อใช้เคอร์เนลนี้กับพิกเซลหนึ่งตัว เท่ากับคำนวณความต่างระหว่างความเข้มของพิกเซลนั้นกับค่าเฉลี่ยของเพื่อนบ้านสี่ทิศ — เวอร์ชันไม่ต่อเนื่องของคำถาม “จุดนี้เปรียบเทียบกับบริเวณรอบๆ อย่างไร” แบบเดิม

ข้อควรคำนึงในทางปฏิบัติ

การกรองด้วยลาปลาซเชียนแบบดิบไวต่อสัญญาณรบกวน พิกเซลที่มีสัญญาณรบกวนเดี่ยวๆ ทำให้เกิดยอดความเข้ม และลาปลาซเชียนจะระบุว่าเป็นขอบ

วิธีแก้มาตรฐานคือทำให้ภาพเรียบก่อนด้วย Gaussian blur แล้วค่อยใช้ลาปลาซเชียน ชุดคู่นี้เรียกว่าLaplacian of Gaussian (LoG) Gaussian ช่วยกดสัญญาณรบกวน และลาปลาซเชียนค้นหาขอบจริง

ในดีปเลิร์นนิง โครงข่ายคอนโวลูชันเรียนรู้ฟิลเตอร์ตรวจจับขอบจากข้อมูล — ซึ่งบ่อยครั้งมีลักษณะคล้ายเคอร์เนลลาปลาซเชียน ดังนั้นในแง่หนึ่ง คณิตศาสตร์ที่ทำให้ลาปลาซเชียนมีประโยชน์ในคอมพิวเตอร์วิทัศน์แบบดั้งเดิมก็คือคณิตศาสตร์เดียวกับที่โครงข่ายประสาทค้นพบขึ้นมาเอง

ลาปลาซเชียนแบบไม่ต่อเนื่องกับแบบต่อเนื่อง

ลาปลาซเชียนคือแนวคิดที่เกี่ยวข้องกันสามแบบซึ่งปรากฏในบริบทต่างๆ

การเข้าใจว่ากำลังใช้เวอร์ชันใดจะช่วยลดความสับสนเมื่อย้ายไปมาระหว่างตำราแคลคูลัส โค้ดเชิงตัวเลข และงานกราฟ ML

ลาปลาซเชียนแบบต่อเนื่อง

ลาปลาซเชียนแบบต่อเนื่องมาจากแคลคูลัส สำหรับฟังก์ชันเรียบ f ที่นิยามบนปริภูมิต่อเนื่อง มันคือผลรวมของอนุพันธ์ย่อยอันดับสอง:

ลาปลาซเชียนแบบต่อเนื่อง

เวอร์ชันนี้สมมติว่าฟังก์ชันเรียบและมีอนุพันธ์ได้ทุกที่ เป็นรากฐานเชิงทฤษฎี — แต่ข้อมูลจริงไม่เคยต่อเนื่อง คุณคำนวณอนุพันธ์ที่แน่นอนได้บนกริดของพิกเซลหรือบนตารางข้อมูลไม่ได้

ลาปลาซเชียนแบบไม่ต่อเนื่อง

เมื่อย้ายจากฟังก์ชันต่อเนื่องไปสู่ข้อมูลที่ถูกสุ่มตัวอย่าง อนุพันธ์จะถูกแทนที่ด้วยความต่างเชิงจำกัด — การประมาณจากค่าของเพื่อนบ้าน

สำหรับฟังก์ชัน 1 มิติที่สุ่มตัวอย่างที่จุดห่างเท่ากัน อนุพันธ์อันดับสองแบบไม่ต่อเนื่องที่จุด i คือ:

ลาปลาซเชียนแบบไม่ต่อเนื่อง

กำลังเปรียบเทียบค่าที่ i กับเพื่อนบ้านสองข้าง แนวคิดเดียวกันนี้ขยายสู่กริด 2 มิติ (ภาพ) ปริมาตร 3 มิติ และมากกว่านั้น เคอร์เนลคอนโวลูชันจากส่วนประมวลผลภาพก็คือสิ่งนี้ — การประมาณแบบความต่างเชิงจำกัดของลาปลาซเชียนต่อเนื่อง ที่ใช้กับกริดพิกเซล

การทำให้ไม่ต่อเนื่องนี้ทำให้ลาปลาซเชียนคำนวณได้ในวิธีเชิงตัวเลขและไปป์ไลน์ ML ทุกครั้งที่ใช้ฟิลเตอร์ลาปลาซเชียนในโค้ด กำลังรันการประมาณแบบความต่างเชิงจำกัด ไม่ใช่ตัวดำเนินการแคลคูลัสจริง

ลาปลาซเชียนบนกราฟ

ลาปลาซเชียนบนกราฟทำให้ไม่ต่อเนื่องไปอีกขั้น แทนที่จะเป็นกริดสม่ำเสมอ มีชุดโหนดตามอำเภอใจที่เชื่อมด้วยขอบน้ำหนักต่างกัน

ที่นี่ไม่มีแนวคิดเรื่อง “พิกเซลเพื่อนบ้าน” — มีเพียงโหนดและการเชื่อมต่อระหว่างกัน ลาปลาซเชียนบนกราฟ L = D - A แทนโครงสร้างความต่างเชิงจำกัดด้วยโครงสร้างเพื่อนบ้าน เม็ดสาระยังเหมือนเดิม: ค่าของโหนดเปรียบเทียบกับเพื่อนบ้านอย่างไร แต่ “เพื่อนบ้าน” นิยามโดยกราฟ ไม่ใช่ความใกล้เชิงพื้นที่

ทำไมจึงสำคัญใน ML

ข้อมูล ML ส่วนใหญ่ไม่ได้อยู่บนกริดสม่ำเสมอ โมเลกุล โซเชียลเน็ตเวิร์ก กราฟความรู้ และพอยต์คลาวด์ 3 มิติ ล้วนมีโครงสร้างไม่สม่ำเสมอ คุณจึงใช้ลาปลาซเชียนแบบความต่างเชิงจำกัดมาตรฐานกับสิ่งเหล่านี้ไม่ได้

ลาปลาซเชียนบนกราฟแก้ปัญหานี้ด้วยการทำให้โครงสร้างเพื่อนบ้านชัดเจนผ่านเมทริกซ์เพื่อนบ้าน นี่คือเหตุผลที่ GNN และวิธีเชิงสเปกตรัลสามารถประยุกต์การดำเนินการแบบลาปลาซเชียนกับข้อมูลที่ไม่มีระบบพิกัดธรรมชาติได้

ตัวอย่างทำจริง: การคำนวณลาปลาซเชียน

มาทำให้รูปธรรมด้วยสองตัวอย่าง — แบบต่อเนื่องหนึ่ง แบบกราฟหนึ่ง

ตัวอย่างที่ 1: ลาปลาซเชียนแบบต่อเนื่องของ f(x, y) = x² + y²

พิจารณาฟังก์ชัน f(x, y) = x² + y² นี่คือพาราบอ ลอยด์อย่างง่าย — รูปชามที่โค้งขึ้นทุกทิศทาง

ในการหาลาปลาซเชียน ต้องใช้อ นุพันธ์ย่อยอันดับสองตามแต่ละตัวแปร

ก่อน ตาม x:

การคำนวณลาปลาซเชียนแบบต่อเนื่อง (1)

จากนั้น ตาม y:

การคำนวณลาปลาซเชียนแบบต่อเนื่อง (2)

แล้วบวกเข้าด้วยกัน:

การคำนวณลาปลาซเชียนแบบต่อเนื่อง (3)

ลาปลาซเชียนเป็นค่าคงที่ 4 ทุกที่ ซึ่งสมเหตุสมผล เพราะพาราบอโลยด์มีความโค้งเท่ากันทุกจุด ค่าเป็นบวกบอกว่าฟังก์ชันโค้งขึ้นทุกทิศทาง สอดคล้องกับรูปชาม

ตัวอย่างที่ 2: ลาปลาซเชียนบนกราฟสำหรับกราฟขนาดเล็ก

พิจารณากราฟที่มี 4 โหนดและขอบดังนี้:

• โหนด 1 เชื่อมกับโหนด 2 และ 3
• โหนด 2 เชื่อมกับโหนด 1 และ 4
• โหนด 3 เชื่อมกับโหนด 1
• โหนด 4 เชื่อมกับโหนด 2

เมทริกซ์เพื่อนบ้าน A เข้ารหัสการเชื่อมต่อ:

การคำนวณลาปลาซเชียนบนกราฟ (1)

เมทริกซ์ดีกรี D ใส่จำนวนการเชื่อมต่อของแต่ละโหนดไว้บนแนวทแยง:

การคำนวณลาปลาซเชียนบนกราฟ (2)

โหนด 1 และ 2 มีการเชื่อมต่ออย่างละ 2 ครั้ง โหนด 3 และ 4 อย่างละ 1 ครั้ง

สุดท้าย ลบเพื่อให้ได้ L = D - A:

การคำนวณลาปลาซเชียนบนกราฟ (3)

วิธีอ่านเมทริกซ์นี้: แถว 1 บอกว่าโหนด 1 มีดีกรี 2 และเชื่อมกับโหนด 2 และ 3 (สมาชิก -1) แถว 3 บอกว่าโหนด 3 มีดีกรี 1 เชื่อมกับโหนด 1 เพียงโหนดเดียว ค่า 0 บอกคู่โหนดที่ไม่มีขอบร่วมกัน

สามารถคำนวณใน Python เพื่อตรวจสอบได้:

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)

การคำนวณลาปลาซเชียนบนกราฟใน Python

ความสับสนที่พบบ่อย

ลาปลาซเชียนคล้ายกับแนวคิดอื่นบางอย่าง และความแตกต่างไม่ได้ชัดจากชื่อเสมอไป ในส่วนนี้จะพยายามขจัดจุดสับสนทั้งหมด

ลาปลาซเชียน vs. เกรเดียนต์

เกรเดียนต์ ∇f เป็นเวกเตอร์ ชี้ทิศทางที่เพิ่มขึ้นชันสุด และขนาดบอกว่าฟังก์ชันเพิ่มเร็วแค่ไหน ใช้อนุพันธ์อันดับหนึ่ง

ลาปลาซเชียน ∇²f เป็นสเกลาร์ ไม่ได้บอกทิศทางที่จะไป — แต่บอกถึงรูปร่างของฟังก์ชัน ณ จุดหนึ่ง สร้างจากอนุพันธ์อันดับสอง

ลาปลาซเชียน vs. เฮสเซียน

ประเด็นนี้มักทำให้หลายคนสับสนที่สุด

เฮสเซียน H เป็นเมทริกซ์ของอนุพันธ์ย่อยอันดับสองทั้งหมด สำหรับฟังก์ชันที่มีอินพุต n มิติ จะเป็นเมทริกซ์ n × n ที่จับว่าค่าเกรเดียนต์เปลี่ยนตามทุกคู่แกนอย่างไร ให้ภาพความโค้งแบบครบถ้วน

ลาปลาซเชียนคือทรซของเฮสเซียน — ผลรวมของสมาชิกบนแนวทแยง สูญเสียข้อมูลความโค้งนอกแนวทแยงไป แต่ได้ตัวเลขเดียวที่คำนวณเร็ว

ใช้เฮสเซียนเมื่อจำเป็นต้องเห็นภาพความโค้งครบถ้วน ใช้ลาปลาซเชียนเมื่อสรุปเป็นสเกลาร์เพียงพอ

ลาปลาซเชียนบนกราฟ vs. ตัวดำเนินการเชิงอนุพันธ์

ทั้งคู่ใช้ชื่อเดียวกันและสัญชาตญาณแกนเดียวกัน แต่ทำงานกับวัตถุคนละแบบโดยสิ้นเชิง

ลาปลาซเชียนเชิงอนุพันธ์ทำงานกับฟังก์ชันต่อเนื่องที่เรียบ ต้องการอนุพันธ์ ซึ่งแปลว่าสมมติว่าฟังก์ชันหาอนุพันธ์ได้ทุกที่

ลาปลาซเชียนบนกราฟ L = D - A ทำงานกับกราฟ — โครงสร้างไม่ต่อเนื่องที่มีโหนดและขอบ ไม่มีอนุพันธ์เข้ามาเกี่ยวข้อง มันวัดว่าค่าที่แต่ละโหนดต่างจากเพื่อนบ้านอย่างไรด้วยเมทริกซ์โอเปอเรชัน

ความเชื่อมโยงเป็นเชิงแนวคิด ไม่ใช่การคำนวณ ทั้งคู่วัดการเบี่ยงเบนเฉพาะที่จากค่าเฉลี่ยของเพื่อนบ้าน แต่เป็นคนละสิ่งกันโดยสิ้นเชิง

ธรรมเนียมเครื่องหมาย

บางสาขานิยามลาปลาซเชียนด้วยเครื่องหมายลบ: -∇²f จะพบในฟิสิกส์และในงาน ML บางงานว่าด้วยกราฟนิวรัลเน็ตเวิร์ก ลาปลาซเชียนเชิงลบ −L เป็นบวกกึ่งแน่นอน (positive semi-definite) ซึ่งมีสมบัติที่ดีกว่าสำหรับปัญหาการหาค่าเหมาะที่สุดบางแบบและทำให้การวิเคราะห์อีเจนแวลูสะอาดขึ้น

เมื่ออ่านงานวิจัยแล้วเห็นว่าอีเจนแวลูของลาปลาซเชียนไม่เป็นลบทั้งหมด ให้ตรวจสอบว่ากำลังใช้ L หรือ -L คณิตศาสตร์เทียบเท่ากัน แต่การผสมธรรมเนียมอาจทำให้ได้ผลลัพธ์ผิด

ทำไมลาปลาซเชียนจึงสำคัญในวิทยาการข้อมูล

ถึงตอนนี้ ได้เห็นลาปลาซเชียนในแคลคูลัส ทฤษฎีกราฟ การประมวลผลภาพ และการหาค่าเหมาะที่สุด ตัวดำเนินการเดียวกันนี้แก้ปัญหาพื้นฐานเดียวกันในบริบทต่างๆ: วัดว่าค่าที่จุดหนึ่งสัมพันธ์กับบริบทแวดล้อมอย่างไร

นี่คือจุดที่พบในวิทยาการข้อมูล:

• ML บนกราฟ: ลาปลาซเชียนบนกราฟ L = D - A เป็นรากฐานของวิธีเชิงสเปกตรัล เมื่อข้อมูลมีโครงสร้างกราฟตามธรรมชาติ ลาปลาซเชียนให้เมทริกซ์ที่เข้ารหัสรูปแบบการเชื่อมต่อทั้งหมดในรูปที่ทำพีชคณิตเชิงเส้นต่อได้

• การจัดกลุ่ม: สเปกทรัลคลัสเตอริงใช้อีเจนเวกเตอร์ของ L เพื่อหากลุ่มที่วิธีอิงระยะทางล้วนๆ พลาด เหมาะเมื่อคลัสเตอร์ไม่เป็นนูนหรือไม่แยกเชิงเส้น

• การเรียนรู้แบบกึ่งมีผู้สอน: วิธีหลายอย่างใช้ลาปลาซเชียนบนกราฟเพื่อแพร่ป้ายกำกับจากโหนดที่มีป้ายกำกับไปยังโหนดที่ไม่มี สมมติฐานคือโหนดที่เชื่อมกันมีแนวโน้มแชร์ป้ายกำกับเดียวกัน และลาปลาซเชียนปริมาณว่าป้ายกำกับควรเปลี่ยนอย่างราบรื่นข้ามกราฟเพียงใด

• แมนิโฟลด์เลิร์นนิง: อัลกอริทึมอย่าง Laplacian Eigenmaps ใช้ลาปลาซเชียนบนกราฟเพื่อหาตัวแทนมิติต่ำของข้อมูลมิติสูง อีเจนเวกเตอร์ของ L แม็ปจุดที่อยู่ใกล้กันในปริภูมิดั้งเดิมไปยังจุดที่อยู่ใกล้กันในปริภูมิลดมิติ

• การสกัดคุณลักษณะภาพ: ลาปลาซเชียนแบบไม่ต่อเนื่องตรวจจับขอบและบริเวณที่ความเข้มเปลี่ยนเร็ว คุณลักษณะเหล่านี้ป้อนตรงสู่ไปป์ไลน์วิทัศน์แบบดั้งเดิมและเป็น prior ในสถาปัตยกรรมดีปเลิร์นนิง

สรุปแล้ว ลาปลาซเชียนเป็นหนึ่งในเครื่องมือคณิตศาสตร์ไม่กี่อย่างที่ขยายจากสมการแคลคูลัสเดียวไปจนถึงกราฟนิวรัลเน็ตเวิร์กขนาดใหญ่ได้

สรุป

ลาปลาซเชียนเริ่มต้นเป็นตัวดำเนินการในแคลคูลัส วิธีวัดความโค้งของฟังก์ชันต่อเนื่อง เมื่อมาถึง ML บนกราฟ มันกลายเป็นเมทริกซ์ที่เข้ารหัสโครงสร้างของทั้งเครือข่าย แนวคิดแกนกลางยังเหมือนเดิมทุกประการ เพียงแต่รูปแบบเปลี่ยนไป

ลงทะเบียนเรียนคอร์สLinear Algebra for Data Science in R เพื่อได้ลงมือทำกับแนวคิดและหัวข้อจำนวนมากที่บทความนี้ครอบคลุม