การฝังเพื่อนบ้านแบบเฟ้นสุ่มแจกแจง t

การใช้ t-SNE สำหรับการฝังคำ เพื่อให้เห็นภาพการแจกแจงของคำ

ชุดข้อมูล MNIST ที่ทำการฝังให้อยู่ในสองมิติโดยใช้ t-SNE

การฝังเพื่อนบ้านแบบเฟ้นสุ่มแจกแจง t (t-distributed stochastic neighbor embedding, t-SNE) เป็นวิธีการทางสถิติสำหรับการแสดงข้อมูลมิติสูงด้วยการกำหนดตำแหน่งข้อมูลแต่ละจุดในแผนที่สองมิติหรือสามมิติ โดยมีพื้นฐานจากขั้นตอนวิธีการฝังเพื่อนบ้านแบบเฟ้นสุ่มที่พัฒนาขึ้นครั้งแรกโดยเจฟฟรีย์ ฮินตัน และ แซม โรไวส์ (Sam Roweis) แล้วได้รับการเสนอรูปแบบการแจกแจงที โดย เลาเรินส์ ฟัน แดร์ มาเติน (Laurens van der Maaten) และฮินตัน วิธีนี้เป็นการลดมิติแบบไม่เชิงเส้น ซึ่งเหมาะสำหรับการฝังข้อมูลมิติสูงลงในพื้นที่มิติต่ำ (2 มิติ หรือ 3 มิติ) สำหรับการแสดงให้เห็นเป็นภาพ โดยเฉพาะอย่างยิ่ง เมื่อจัดเรียงชุดข้อมูลมิติสูงใน 2 หรือ 3 มิติ ชุดที่คล้ายกันจะสัมพันธ์กับความน่าจะเป็นสูงในบริเวณใกล้เคียง และชุดที่แตกต่างกันจะสัมพันธ์กันในบริเวณที่ห่างไกล

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

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

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

รายละเอียด

สมมุติว่ามีชุดข้อมูล $N$ ตัวที่แสดงค่าหลายมิติ ${𝐱}_1,\dots ,{𝐱}_N$ วัตถุประสงค์ของเราคือแสดงชุดข้อมูลนี้ในรูปของ ${𝐲}_1,\dots ,{𝐲}_N$ ที่มีจำนวนมิติต่ำกว่าที่สามารถสะท้อนให้เห็นถึงลักษณะความคล้ายคลึงกันของชุดข้อมูลมิติสูง

พารามิเตอร์สำหรับ t-SNE ได้แก่ ค่าความงุนงง (perplexity) ของพารามิเตอร์ฟังก์ชันการสูญเสียและจำนวนการคำนวณวนซ้ำ $T$ ของพารามิเตอร์การปรับให้เหมาะสม, อัตราการเรียนรู้ $\eta$, โมเมนตัม $\alpha (t)$ ฟัน แดร์ มาเติน ได้อธิบายไว้ว่าสมรรถนะของ t-SNE ไม่ค่อยขึ้นกับค่าความงุนงง โดยค่าความงุนงงที่เหมาะสมที่สุดนั้นต่างกันไปขึ้นอยู่กับข้อมูลที่ใช้ แต่โดยทั่วไปจะอยู่ระหว่าง 5 ถึง 50

ขั้นแรก เราคำนวณความคล้ายคลึงกันของแต่ละคู่สำหรับชุดข้อมูลมิติสูง ฟัน แดร์ มาเติน และ ฮินตัน ได้อธิบายว่า "ถ้าเลือกจุดข้อมูล $x_j$ โดยอิงตาม $x_i$ ให้เป็นสัดส่วนกับการแจกแจงความหนาแน่นความน่าจะเป็นแบบปรกติที่มีใจกลางอยู่ที่ $x_i$ แล้ว ความคล้ายคลึงกันระหว่าง $x_j$ กับ $x_i$ จะแสดงได้เป็นความน่าจะเป็นมีเงื่อนไข $p_{j|i}$"

$p_{j\mid i}=\frac{\exp (-\Vert {𝐱}_i-{𝐱}_j{\Vert }^2/2{\sigma }_i^2)}{\sum _{k\ne i}\exp (-\Vert {𝐱}_i-{𝐱}_k{\Vert }^2/2{\sigma }_i^2)},$

โดยสำหรับจุดเดียวกันจะได้ว่า $p_{i\mid i}=0$

${\sigma }_i$ คือค่าเบี่ยงเบนของการแจกแจงปรกติ ซึ่งอาจหาได้โดยวิธีแบ่งครึ่ง เป็นไปตามความสัมพันธ์ความงุนงงดังต่อไปนี้

$Perp(P_i)=2^{H(P_i)}$

$H(P_i)=-\sum _j{p}_{j\mid i}{\log }_2{p}_{j\mid i}$

ในที่นี้ $H(P_i)$ คือเอนโทรปีของข้อมูล หากกระจุกกันอยู่อย่างหนาแน่นในพื้นที่แคบแล้ว ${\sigma }_i$ จะเป็นค่าที่มีขนาดเล็ก

จากนั้น[ความน่าจะเป็นร่วม]] $p_{ij}$ คำนวณได้โดยใช้สูตรต่อไปนี้

$p_{ij}=\frac{p_{j\mid i}+p_{i\mid j}}{2N}$

โดยในกรณี $i=j$ จะกลายเป็น 0 (นั่นคือ $p_{ii}=0$)

ให้ผลเฉลยตั้งต้น $Y^{(0)}$ ได้จากการสุ่มตัวอย่างของการแจกแจงแบบเกาส์เซียนที่มีค่าเฉลี่ยเป็น 0

สุดท้าย ให้ทำซ้ำ T ครั้ง หาผลเฉลย $Y^{(T)}$ ในขั้นตอนต่อไปตั้งแต่ขั้น t=1 ถึง t=T

คำนวณความคล้ายคลึงมิติต่ำสำหรับ $Y^{(t-1)}$ ซึ่งเป็ผลเฉลยที่ t-1

ความน่าจะเป็นร่วมโดยใช้การแจกแจงที (การแจกแจงโคชี) โดยมีองศาเสรีเป็น 1

$q_{ij}=\frac{(1+\Vert {𝐲}_i-{𝐲}_j{\Vert }^2{)}^{-1}}{\sum _{k\ne l}(1+\Vert {𝐲}_k-{𝐲}_l{\Vert }^2{)}^{-1}}$

อย่างไรก็ตาม จะให้ค่าเป็น 0 สำหรับคู่ที่มีจุดเดียวกัน $q_{ii}=0$

ให้ไดเวอร์เจนซ์คัลแบ็ก–ไลบ์เลอร์สำหรับการแจกแจง P ของ $p_{ij}$ และการแจกแจง Q ของ $q_{ij}$ เป็นฟังก์ชันเป้าหมาย แล้วหาผลเฉลย $Y^{(t)}$ ที่ทำให้มีค่าต่ำที่สุด

$KL(P||Q)=\sum _{i\ne j}{p}_{ij}\log \frac{p_{ij}}{q_{ij}}$

คำนวณความชันของฟังก์ชันเป้าหมายสำหรับแต่ละ i

$\frac{\delta C}{\delta y_i}=4\sum _j(p_{ij}-q_{ij})(y_i-y_j)(1+\Vert y_i-y_j{\Vert }^2{)}^{-1}$

ความชันของฟังก์ชันเป้าหมายและคำนวณหาผลเฉลย $Y^{(t)}$ ลำดับที่ t จากคำตอบก่อนหน้า

$Y^{(t)}=Y^{(t-1)}+\eta \frac{\delta C}{\delta Y}+\alpha (t)(Y^{(t-1)}-Y^{(t-2)})$

การแสดงผลเฉลย $Y^{(T)}$ ด้วยภาพทำให้สามารถเข้าใจกลุ่มของชุดข้อมูลที่มีมิติสูงได้

ข้อเสีย

• ยังไม่ชัดเจนว่าจะดำเนินการลดมิติทั่วไปอย่างไร
• มีสมบัติที่ค่อนข้างเป็นเฉพาะที่ทำให้มีความอ่อนไหวต่อคำสาปของมิติข้อมูลโดยธรรมชาติ
  • ฟังก์ชันเกาส์เซียนใช้ระยะทางแบบยุคลิด $\Vert x_i-x_j\Vert$ จึงได้รับผลจากคำสาปของมิติ และสูญเสียความสามารถในการแยกแยะข้อมูลตามระยะทางสำหรับมิติสูง $p_{ij}$ จะกลายเป็นมีค่าเกือบเท่ากัน เพื่อบรรเทาปัญหานี้ จึงได้มีการเสนอวิธีการที่ระยะห่างจะถูกปรับโดยการแปลงกำลังตามขนาดเฉพาะของแต่ละจุด
• ไม่รับประกันว่าฟังก์ชันเป้าหมาย t จะลู่เข้าที่ค่าต่ำสุดวงกว้าง
  • แม้ว่าจะมีพารามิเตอร์และขั้นตอนวิธีเหมือนกัน ก็อาจได้ผลเฉลยที่แตกต่างกัน