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

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

[thumb|ชุดข้อมูล [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 ตัวที่แสดงค่าหลายมิติ \mathbf{x}_1, \dots, \mathbf{x}_N วัตถุประสงค์ของเราคือแสดงชุดข้อมูลนี้ในรูปของ \mathbf{y}_1, \dots, \mathbf{y}_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(-\lVert\mathbf{x}_i - \mathbf{x}_j\rVert^2 / 2\sigma_i^2)}{\sum_{k \neq i} \exp(-\lVert\mathbf{x}_i - \mathbf{x}_k\rVert^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 + \lVert \mathbf{y}_i - \mathbf{y}_j\rVert^2)^{-1}}{\sum_{k \neq l} (1 + \lVert \mathbf{y}_k - \mathbf{y}_l\rVert^2)^{-1}}

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

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

: KL(P||Q) = \sum_{i \neq 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+\lVert y_i - y_j \rVert^2 )^{-1} 

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

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

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

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

## อ้างอิง

หมวดหมู่:การวิเคราะห์ข้อมูล
หมวดหมู่:การเรียนรู้ของเครื่อง
หมวดหมู่:การลดมิติ