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

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

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

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

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

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

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

รายละเอียด

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

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

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

${\displaystyle 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})}},}$

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

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

${\displaystyle Perp(P_{i})=2^{H(P_{i})}}$

${\displaystyle H(P_{i})=-\sum _{j}p_{j\mid i}\log _{2}p_{j\mid i}}$

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

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

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

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

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

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

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

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

${\displaystyle 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 สำหรับคู่ที่มีจุดเดียวกัน ${\displaystyle q_{ii}=0}$

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

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

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

${\displaystyle {\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}}$

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

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

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

ข้อเสีย

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

อ้างอิง

1. Hinton, Geoffrey; Roweis, Sam (January 2002). Stochastic neighbor embedding (PDF). Neural Information Processing Systems.
2. van der Maaten, L.J.P.; Hinton, G.E. (Nov 2008). "Visualizing Data Using t-SNE" (PDF). Journal of Machine Learning Research. 9: 2579–2605.
3. Gashi, I.; Stankovic, V.; Leita, C.; Thonnard, O. (2009). "An Experimental Study of Diversity with Off-the-shelf AntiVirus Engines". Proceedings of the IEEE International Symposium on Network Computing and Applications: 4–11.
4. Hamel, P.; Eck, D. (2010). "Learning Features from Music Audio with Deep Belief Networks". Proceedings of the International Society for Music Information Retrieval Conference: 339–344.
5. Jamieson, A.R.; Giger, M.L.; Drukker, K.; Lui, H.; Yuan, Y.; Bhooshan, N. (2010). "Exploring Nonlinear Feature Space Dimension Reduction and Data Representation in Breast CADx with Laplacian Eigenmaps and t-SNE". Medical Physics. 37 (1): 339–351. doi:10.1118/1.3267037. PMC 2807447. PMID 20175497.
6. Wallach, I.; Liliean, R. (2009). "The Protein-Small-Molecule Database, A Non-Redundant Structural Resource for the Analysis of Protein-Ligand Binding". Bioinformatics. 25 (5): 615–620. doi:10.1093/bioinformatics/btp035. PMID 19153135.
7. Birjandtalab, J.; Pouyan, M. B.; Nourani, M. (2016-02-01). Nonlinear dimension reduction for EEG-based epileptic seizure detection. 2016 IEEE-EMBS International Conference on Biomedical and Health Informatics (BHI). pp. 595–598. doi:10.1109/BHI.2016.7455968. ISBN .
8. Visualizing Representations: Deep Learning and Human Beings Christopher Olah's blog, 2015
9. "K-means clustering on the output of t-SNE". Cross Validated. สืบค้นเมื่อ 2019-04-06.
10. Pezzotti, Nicola; Lelieveldt, Boudewijn P. F.; Maaten, Laurens van der; Hollt, Thomas; Eisemann, Elmar; Vilanova, Anna (2017-07-01). "Approximated and User Steerable tSNE for Progressive Visual Analytics". IEEE Transactions on Visualization and Computer Graphics (ภาษาอังกฤษแบบอเมริกัน). 23 (7): 1739–1752. doi:10.1109/tvcg.2016.2570755. ISSN 1077-2626. PMID 28113434.
11. Wattenberg, Martin; Viégas, Fernanda; Johnson, Ian (2016-10-13). "How to Use t-SNE Effectively" (ภาษาอังกฤษ). Distill. สืบค้นเมื่อ 2019-04-06.
12. Linderman, George C.; Steinerberger, Stefan (2017-06-08). "Clustering with t-SNE, provably". :1706.02582 [cs.LG].
13. Schubert, Erich; Gertz, Michael (2017-10-04). Intrinsic t-Stochastic Neighbor Embedding for Visualization and Outlier Detection. SISAP 2017 – 10th International Conference on Similarity Search and Applications. pp. 188–203. doi:10.1007/978-3-319-68474-1_13.