แผนที่การแพร่กระจาย (Diffusion maps)เป็น อัลกอริทึม การลดมิติหรือการสกัดคุณลักษณะที่Coifmanและ Lafon ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]} นำเสนอ ซึ่งคำนวณตระกูลของการฝังชุดข้อมูลลงในพื้นที่ยูคลิด (มักมีมิติต่ำ) โดยพิกัดสามารถคำนวณได้จากเวกเตอร์ลักษณะเฉพาะและค่าลักษณะเฉพาะของตัวดำเนินการการแพร่กระจายบนข้อมูลระยะทางยูคลิดระหว่างจุดในพื้นที่ฝังตัวจะเท่ากับ "ระยะทางการแพร่กระจาย" ระหว่างการกระจายความน่าจะเป็นที่อยู่ตรงกลางจุดเหล่านั้น แตกต่างจากวิธีการลดมิติเชิงเส้น เช่นการวิเคราะห์ส่วนประกอบหลัก (PCA) แผนที่การแพร่กระจายเป็นส่วนหนึ่งของตระกูล วิธี การลดมิติแบบไม่เชิงเส้น ซึ่งมุ่งเน้นไปที่การค้นหา แมนิโฟลด์พื้นฐานที่ข้อมูลได้รับการสุ่มตัวอย่างมา ด้วยการบูรณาการความคล้ายคลึงกันในระดับท้องถิ่นที่แตกต่างกัน แผนที่การแพร่กระจายให้คำอธิบายโดยรวมของชุดข้อมูล เมื่อเปรียบเทียบกับวิธีการอื่น ๆ อัลกอริทึมแผนที่การแพร่กระจายมีความทนทานต่อการรบกวนจากสัญญาณรบกวนและมีต้นทุนการคำนวณต่ำ

ตาม^{[ 3 ]}และ^{[ 5 ]}แผนที่การแพร่กระจายสามารถกำหนดได้ในสี่ขั้นตอน

แผนที่การแพร่กระจายใช้ประโยชน์จากความสัมพันธ์ระหว่างการแพร่กระจายความร้อนและลูกโซ่ Markov แบบสุ่ม ข้อสังเกตพื้นฐานคือ หากเราเดินแบบสุ่มบนข้อมูล การเดินไปยังจุดข้อมูลที่อยู่ใกล้เคียงจะมีโอกาสมากกว่าการเดินไปยังจุดข้อมูลที่อยู่ไกลออกไป ให้เป็นปริภูมิการวัดโดยที่คือเซตของข้อมูล และแทนการกระจายของจุดบน ${\displaystyle (X,{\mathcal {A}},\mu )}$${\displaystyle X}$${\displaystyle \mu }$${\displaystyle X}$

จากหลักการนี้ การเชื่อมต่อระหว่างจุดข้อมูลสองจุดและสามารถกำหนดได้ว่าเป็นความน่าจะเป็นของการเดินจาก ไปยังในหนึ่งก้าวของการเดินแบบสุ่ม โดยปกติแล้ว ความน่าจะเป็นนี้จะระบุในรูปของฟังก์ชันเคอร์เนลของจุดทั้งสอง: ตัวอย่างเช่น เคอร์เนลแบบเกาส์เซียนที่นิยมใช้: ${\displaystyle k}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle k:X\times X\rightarrow \mathbb {R} }$

${\displaystyle k(x,y)=\exp \left(-{\frac {||xy||^{2}}{\epsilon }}\right)}$

โดยทั่วไปแล้ว ฟังก์ชัน เคอร์เนลมีคุณสมบัติดังต่อไปนี้

${\displaystyle k(x,y)=k(y,x)}$

( สมมาตร) ${\displaystyle k}$

${\displaystyle k(x,y)\geq 0\,\,\forall x,y}$

( เป็นการรักษาความเป็นบวก) ${\displaystyle k}$

เคอร์เนลเป็นตัวกำหนดเบื้องต้นของ รูปทรงเรขาคณิต เฉพาะที่ของชุดข้อมูล เนื่องจากเคอร์เนลแต่ละตัวจะจับคุณลักษณะเฉพาะของชุดข้อมูล ดังนั้นการเลือกเคอร์เนลจึงควรขึ้นอยู่กับแอปพลิเคชันที่ต้องการใช้งาน นี่คือความแตกต่างที่สำคัญกับวิธีการต่างๆ เช่นการวิเคราะห์องค์ประกอบหลัก (Principal Component Analysis ) ซึ่งพิจารณาความสัมพันธ์ระหว่างจุดข้อมูลทั้งหมดพร้อมกัน

เมื่อกำหนดแล้ว เราสามารถสร้างห่วงโซ่มาร์คอฟแบบย้อนกลับได้ในเวลาไม่ต่อเนื่องบน(กระบวนการที่เรียกว่าการสร้างลาปลาเซียนกราฟแบบนอร์มาไลซ์): ${\displaystyle (X,k)}$${\displaystyle X}$

${\displaystyle d(x)=\int _{X}k(x,y)d\mu (y)}$

และกำหนด:

${\displaystyle p(x,y)={\frac {k(x,y)}{d(x)}}}$

แม้ว่าเคอร์เนลที่ปรับให้เป็นมาตรฐานใหม่จะไม่สืบทอดคุณสมบัติสมมาตร แต่ก็สืบทอดคุณสมบัติการรักษาความเป็นบวกและได้รับคุณสมบัติการอนุรักษ์:

${\displaystyle \int _{X}p(x,y)d\mu (y)=1}$

จากนั้นเราสามารถสร้างเมทริกซ์การเปลี่ยนสถานะของห่วงโซ่มาร์คอฟ ( ) บน ได้กล่าวอีกนัยหนึ่งแสดงถึงความน่าจะเป็นการเปลี่ยนสถานะหนึ่งขั้นจากไปยังและให้เมทริกซ์การเปลี่ยนสถานะ t ขั้น ${\displaystyle p(x,y)}$${\displaystyle M}$${\displaystyle X}$${\displaystyle p(x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle M^{t}}$

เรากำหนดเมทริกซ์การแพร่กระจาย(ซึ่งเป็นรูปแบบหนึ่งของเมทริกซ์ลาปลาเซียนของ กราฟ ) ${\displaystyle L}$

${\displaystyle L_{i,j}=k(x_{i},x_{j})\,}$

จากนั้นเราจึงกำหนดเคอร์เนลใหม่

${\displaystyle L_{i,j}^{(\alpha )}=k^{(\alpha )}(x_{i},x_{j})={\frac {L_{i,j}}{(d(x_{i})d(x_{j}))^{\alpha }}}\,}$

หรือเทียบเท่า

${\displaystyle L^{(\alpha )}=D^{-\alpha }LD^{-\alpha }\,}$

โดยที่ D เป็นเมทริกซ์แนวทแยงและ${\displaystyle D_{i,i}=\sum _{j}L_{i,j}.}$

เราใช้การทำให้เป็นมาตรฐานแบบลาปลาเซียนของกราฟกับเคอร์เนลใหม่นี้:

${\displaystyle M=({D}^{(\alpha )})^{-1}L^{(\alpha )},\,}$

โดยที่เป็นเมทริกซ์แนวทแยง และ${\displaystyle D^{(\alpha )}}$${\displaystyle {D}_{i,i}^{(\alpha )}=\sum _{j}L_{i,j}^{(\alpha )}.}$

${\displaystyle p(x_{j},t|x_{i})=M_{i,j}^{t}\,}$

หนึ่งในแนวคิดหลักของกรอบงานการแพร่กระจายคือ การดำเนินห่วงโซ่ไปข้างหน้าตามเวลา (โดยใช้กำลังที่มากขึ้นเรื่อยๆ ของ t ) จะเผยให้เห็นโครงสร้างทางเรขาคณิตของ t ในระดับที่ใหญ่ขึ้นเรื่อยๆ (กระบวนการแพร่กระจาย) โดยเฉพาะอย่างยิ่ง แนวคิดของกลุ่มในชุดข้อมูลจะถูกวัดเป็นบริเวณที่ความน่าจะเป็นที่จะหลุดออกจากบริเวณนี้ต่ำ (ภายในเวลา t ที่กำหนด) ดังนั้น t จึงไม่เพียงแต่ทำหน้าที่เป็นพารามิเตอร์เวลาเท่านั้น แต่ยังมีบทบาทคู่เป็นพารามิเตอร์ขนาดด้วย ${\displaystyle M}$${\displaystyle X}$

การแยกส่วนประกอบค่าลักษณะเฉพาะของเมทริกซ์ให้ผลลัพธ์ ดังนี้${\displaystyle M^{t}}$

${\displaystyle M_{i,j}^{t}=\sum _{l}\lambda _{l}^{t}\psi _{l}(x_{i})\phi _{l}(x_{j})\,}$

โดยที่คือลำดับของค่าลักษณะเฉพาะของและและคือเวกเตอร์ลักษณะเฉพาะซ้ายและขวาแบบไบออร์โทกอนอลตามลำดับ เนื่องจากสเปกตรัมของค่าลักษณะเฉพาะลดลง จึงจำเป็นต้องใช้เพียงไม่กี่พจน์เพื่อให้ได้ความแม่นยำสัมพัทธ์ที่กำหนดในผลรวมนี้ ${\displaystyle \{\แลมบ์ดา _{l}\}}$${\displaystyle M}$${\displaystyle \{\psi _{l}\}}$${\displaystyle \{\phi _{l}\}}$

เหตุผลที่ต้องนำขั้นตอนการทำให้เป็นมาตรฐานมาใช้ก็เพื่อปรับอิทธิพลของความหนาแน่นของจุดข้อมูลต่อ การเปลี่ยนแปลง เล็กน้อยของการแพร่กระจาย ในบางแอปพลิเคชัน การสุ่มตัวอย่างข้อมูลโดยทั่วไปไม่เกี่ยวข้องกับเรขาคณิตของแมนิโฟลด์ที่เราสนใจที่จะอธิบาย ในกรณีนี้ เราสามารถกำหนดและตัวดำเนินการแพร่กระจายจะประมาณตัวดำเนินการ Laplace–Beltrami ได้ จากนั้นเราจะได้เรขาคณิตแบบ Riemannianของชุดข้อมูลกลับคืนมาโดยไม่คำนึงถึงการกระจายของจุด เพื่ออธิบายพฤติกรรมระยะยาวของการกระจายจุดของระบบสมการเชิงอนุพันธ์สุ่ม เราสามารถใช้และห่วงโซ่ Markov ที่ได้จะประมาณการแพร่กระจายของ Fokker–Planckได้ ด้วยมันจะลดลงเหลือการทำให้เป็นมาตรฐานแบบกราฟ Laplacian แบบคลาสสิก ${\displaystyle \alpha }$${\displaystyle \alpha =1}$${\displaystyle \alpha =0.5}$${\displaystyle \alpha =0}$

ระยะการแพร่กระจาย ณ เวลาหนึ่งระหว่างสองจุด สามารถวัดได้จากความคล้ายคลึงกันของสองจุดในพื้นที่สังเกตการณ์ โดยพิจารณาจากการเชื่อมต่อระหว่างกัน ซึ่งกำหนดโดยสูตร ${\displaystyle t}$

${\displaystyle D_{t}(x_{i},x_{j})^{2}=\sum _{y}{\frac {(p(y,t|x_{i})-p(y,t|x_{j}))^{2}}{\phi _{0}(y)}}}$

โดยที่คือการกระจายสถานะคงที่ของห่วงโซ่มาร์คอฟ ซึ่งกำหนดโดยเวกเตอร์ลักษณะเฉพาะด้านซ้ายตัวแรกของ กล่าวคือ: ${\displaystyle \phi _{0}(y)}$${\displaystyle M}$

${\displaystyle \phi _{0}(y)={\frac {d(y)}{\sum _{z\in X}d(z)}}}$

โดยสัญชาตญาณแล้ว ค่าจะมีขนาดเล็กหากมีเส้นทางสั้นๆ จำนวนมากเชื่อมต่อระหว่างและมีคุณสมบัติที่น่าสนใจหลายประการที่เกี่ยวข้องกับระยะการแพร่กระจาย โดยอิงจากการอภิปรายก่อนหน้านี้ของเรา ซึ่งทำหน้าที่เป็นพารามิเตอร์มาตราส่วนด้วย: ${\displaystyle D_{t}(x_{i},x_{j})}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle t}$

1. จุดต่างๆ จะอยู่ใกล้กันมากขึ้นในระดับมาตราส่วนที่กำหนด (ตามที่ระบุโดย) หากจุดเหล่านั้นมีการเชื่อมต่อกันอย่างมากในกราฟ ซึ่งเป็นการเน้นย้ำแนวคิดเรื่องคลัสเตอร์${\displaystyle D_{t}(x_{i},x_{j})}$
2. ระยะทางนี้มีความเสถียรต่อสัญญาณรบกวน เนื่องจากระยะทางระหว่างจุดสองจุดขึ้นอยู่กับเส้นทางที่เป็นไปได้ทั้งหมดที่มีความยาวระหว่างจุดทั้งสอง${\displaystyle t}$
3. จากมุมมองของการเรียนรู้ของเครื่อง ระยะทางจะคำนึงถึงหลักฐานทั้งหมดที่เชื่อมโยงกับทำให้เราสรุปได้ว่าระยะทางนี้เหมาะสมสำหรับการออกแบบอัลกอริธึมการอนุมานโดยอาศัยความน่าจะเป็นส่วนใหญ่^{[ 3 ]}${\displaystyle x_{i}}$${\displaystyle x_{j}}$

สามารถคำนวณระยะการแพร่กระจายได้โดยใช้เวกเตอร์ลักษณะเฉพาะโดย

${\displaystyle D_{t}(x_{i},x_{j})^{2}=\sum _{l}\lambda _{l}^{2t}(\psi _{l}(x_{i})-\psi _{l}(x_{j}))^{2}\,}$

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

${\displaystyle \Psi _{t}(x)=(\lambda _{1}^{t}\psi _{1}(x),\lambda _{2}^{t}\psi _{2}(x),\ldots ,\lambda _{k}^{t}\psi _{k}(x))}$

เนื่องจากการลดทอนของสเปกตรัม จึงเพียงพอที่จะใช้ เวกเตอร์และค่าลักษณะเฉพาะ k ตัวแรกเท่านั้น ดังนั้นเราจึงได้แผนที่การแพร่กระจายจากข้อมูลดั้งเดิมไปยัง ปริภูมิ kมิติ ซึ่งฝังอยู่ในปริภูมิเดิม

ใน^{[ 6 ]}พิสูจน์ได้ว่า

${\displaystyle D_{t}(x_{i},x_{j})^{2}\approx ||\Psi _{t}(x_{i})-\Psi _{t}(x_{j})||^{2}\,}$

ดังนั้นระยะทางแบบยุคลิดในพิกัดการแพร่กระจายจึงเป็นการประมาณระยะทางการแพร่กระจาย

กรอบอัลกอริทึมพื้นฐานของแผนที่การแพร่กระจายมีดังนี้:

ขั้นตอนที่ 1. กำหนดเมทริกซ์ความคล้ายคลึงL มา ให้

ขั้นตอนที่ 2. ปรับค่าเมทริกซ์ให้เป็นมาตรฐานตามพารามิเตอร์: . ${\displaystyle \alpha }$${\displaystyle L^{(\alpha )}=D^{-\alpha }LD^{-\alpha }}$

ขั้นตอนที่ 3. สร้างเมทริกซ์มาตรฐาน ${\displaystyle M=({D}^{(\alpha )})^{-1}L^{(\alpha )}}$

ขั้นตอนที่ 4. คำนวณ ค่าลักษณะเฉพาะที่ใหญ่ที่สุด kค่าของเมทริกซ์ และเวกเตอร์ลักษณะเฉพาะที่สอดคล้องกัน ${\displaystyle M^{t}}$

ขั้นตอนที่ 5. ใช้แผนที่การแพร่กระจาย (diffusion map) เพื่อรับค่าฝังตัว (embedding ) ${\displaystyle \Psi _{t}}$

ในเอกสาร^{[ 6 ]} Nadler และคณะได้แสดงวิธีการออกแบบเคอร์เนลที่สร้างการแพร่กระจายที่เกิดจากสมการ Fokker–Planckพวกเขายังอธิบายด้วยว่า เมื่อข้อมูลประมาณแมนิโฟลด์ เราสามารถกู้คืนเรขาคณิตของแมนิโฟลด์นี้ได้โดยการคำนวณค่าประมาณของตัวดำเนินการ Laplace–Beltramiการคำนวณนี้ไม่ไวต่อการกระจายของจุดโดยสิ้นเชิง ดังนั้นจึงให้การแยกสถิติและเรขาคณิตของข้อมูล เนื่องจากแผนที่การแพร่กระจายให้คำอธิบายโดยรวมของชุดข้อมูล จึงสามารถวัดระยะห่างระหว่างคู่ของจุดตัวอย่างในแมนิโฟลด์ที่ข้อมูลฝังอยู่ได้ แอปพลิเคชันที่ใช้แผนที่การแพร่กระจาย ได้แก่การจดจำใบหน้า [ ^{7 ]}การจัดกลุ่มสเปกตรัมการแสดงภาพในมิติที่ต่ำ^การ แบ่งส่วนภาพ^{[ 8 ]}การแบ่งส่วนโมเดล 3 มิติ^{[ 9 ]}การตรวจสอบและระบุตัวตน ผู้พูด ^{[ 10 ] [ 11 ]}การสุ่มตัวอย่างบนแมนิโฟลด์การตรวจจับความผิดปกติ^{[ 12 ] [ 13 ]}การเติมภาพ^{[ 14 ]}การเปิดเผยโครงสร้างเครือข่ายสถานะพักของสมอง^{[ 15 ]} และอื่นๆ

นอกจากนี้ กรอบงานแผนที่การแพร่กระจายยังได้รับการขยายอย่างมีประสิทธิภาพไปยังเครือข่ายที่ซับซ้อน^{[ 16 ]}ซึ่งเผยให้เห็นการจัดระเบียบการทำงานของเครือข่ายที่แตกต่างจากโครงสร้างเชิงโทโพโลยีหรือเชิงโครงสร้างโดยแท้จริง

แนวคิดพื้นฐานของแผนที่การแพร่กระจายสามารถขยายไปยังเวกเตอร์และเทนเซอร์ลำดับสูงกว่าได้โดยการเพิ่มแมนิโฟลด์ข้อมูลด้วยการเชื่อมต่อเชิงเส้นตรงซึ่งอธิบายวิธีการที่เวกเตอร์และเทนเซอร์อื่นๆ แปลงเมื่อเคลื่อนที่จากจุดหนึ่งบนแมนิโฟลด์ไปยังจุดใกล้เคียง ในกรณีของกราฟข้อมูลแบบไม่ต่อเนื่องที่ประมาณแมนิโฟลด์แบบต่อเนื่อง สิ่งนี้เทียบเท่ากับการกำหนดซับสเปซเฉพาะที่ให้กับทุกจุดข้อมูลและเมทริกซ์ตั้งฉากปกติที่แมประหว่างซับสเปซให้กับทุกขอบบนกราฟ วัตถุนี้เรียกว่าชีฟเซลลูลาร์^{[ 17 ]}สามารถค้นหาซับสเปซได้โดยการใช้การวิเคราะห์ส่วนประกอบหลักเฉพาะที่รอบๆ แต่ละจุด ในขณะที่การแมปขอบสามารถค้นหาได้โดยการใช้การวิเคราะห์ความสัมพันธ์แบบแคนอนิกส์ระหว่างซับสเปซเฉพาะที่ จากนั้น ส่วนขยายของกราฟลาปลาเซียนที่อธิบายวิวัฒนาการของเวลาของเวกเตอร์ที่ผ่านการเดินแบบสุ่มสามารถกำหนดได้: กราฟลาปลา เซียน การเชื่อมต่อ :

${\displaystyle L_{ij}={\mathcal {O}}_{ij}}$

${\displaystyle L_{ii}=d\mathbf {I} }$

โดยที่คือดีกรีของโหนดในกราฟ และคือการเชื่อมต่อแบบตั้งฉากปกติระหว่างโหนดที่อยู่ติดกัน นี่คือเมทริกซ์แบบบล็อกสปาร์ส โดยมีหนึ่งบล็อกสำหรับแต่ละขอบของกราฟ ${\displaystyle d}$${\displaystyle i}$${\displaystyle {\mathcal {O}}_{ij}}$${\displaystyle L_{ij}}$

การฝังที่เทียบเท่าที่พบโดยการ ใช้ แผนที่การแพร่กระจายกับ Laplacian การเชื่อมต่อนี้เรียกว่าแผนที่การแพร่กระจายเวกเตอร์^{[ 18 ]}

ลาปลาเซียนการเชื่อมต่อยังสามารถกำหนดสำหรับเทนเซอร์ลำดับสูงกว่าได้ ซึ่งในกรณีนี้แต่ละบล็อกของเมทริกซ์จะเป็นผลคูณโครเนกเกอร์ของเมทริกซ์การเชื่อมต่อ ลาปลาเซียนการเชื่อมต่อกราฟลำดับที่สองเข้ารหัสข้อมูลเกี่ยวกับวิวัฒนาการของเมทริกซ์และปริภูมิย่อยภายใต้การแพร่กระจายการเดินแบบสุ่ม สิ่งนี้มีความเชื่อมโยงอย่างใกล้ชิดกับทฤษฎีโฮโลโนมี และ การแยกส่วนเดอแรม เวก เตอร์ลักษณะเฉพาะของลาปลาเซียนการเชื่อมต่อลำดับที่สองสามารถใช้เพื่อแยก ส่วนแมนิโฟลด์ข้อมูลออกเป็นแมนิโฟล ด์ ย่อย แทนที่จะหาการฝัง นี่คือแนวคิดหลักเบื้องหลังตัวประมาณส่วนประกอบแมนิโฟลด์เชิงเรขาคณิต (GeoManCEr) ^{[ 19 ]}

• การลดมิติแบบไม่เชิงเส้น
• การจัดกลุ่มสเปกตรัม