T-SNE

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

t-distributed stochastic neighbor embedding) t-SNE) הוא אלגוריתם בלמידה חישובית להורדת ממדים, שפותח על ידי לורנס ואן דר מאטן וג'פרי הינטון.

זאת שיטה לא-ליניארית להורדת ממדים שמתאימה במיוחד להורדת מימד של מרחבים ממימד גבוה למרחבים מממד 2 או 3 (מפות). האלגוריתם ממדל כל אובייקט מהמרחב הרב-ממדי בעזרת נקודה דו ממדית או תלת ממדית כך שאובייקטים דומים ימודלו לנקודות קרובות זו לזו, ואובייקטים רחוקים ימודלו לנקודות רחוקות זו מזו.

אלגוריתם ה-t-SNE כולל שני שלבים עיקריים. בהתחלה האלגוריתם בונה התפלגות עבור כל זוג אובייקטים ממימד גבוה כך שלאובייקטים דומים יש הסתברות גבוהה להיבחר, בעוד שלאובייקטים לא דומים יש הסתברות נמוכה מאוד (אינפיניטסימלית) להיבחר. שנית, האלגוריתם מגדיר התפלגות באופן דומה עבור כל זוג נקודות במפה ממימד נמוך. לאחר מכן האלגוריתם מנסה להביא למינימום את דיברגנץ קולבק-ליבלר (Kullback–Leibler divergence) בין שתי ההתפלגויות, ביחס למיקומים של הנקודות על המפה. האלגוריתם המקורי משתמש במרחק אוקלידי כדי למצוא מרחק בין שני אובייקטים, אך ניתן להשתמש במטריקות אחרות לחישוב המרחק.

אלגוריתם t-SNE שימושי במגוון רחב של תחומים, כגון אבטחת מחשב אישי ברשת, ניתוח מוזיקלי, חקר הסרטן וביואינפורמטיקה.

פרטי האלגוריתם

בהינתן סט של N אובייקטים ממימד גבוה, 𝐱1,,𝐱N, האלגוריתם מחשב קודם את ההסתברויות pij שהן פרופורציוניות לדמיון בין האובייקטים 𝐱i ו 𝐱j, באופן הבא:

pj|i=exp(𝐱i𝐱j2/2σi2)kiexp(𝐱i𝐱k2/2σi2),

pij=pj|i+pi|j2N

כאשר σi נקבע כך שה-perplexity (מידת השוואה להתפלגויות) של ההתפלגויות שהוגדרו (Q,P) יהיה שווה ל-perplexity מסוים שנקבע מראש על ידי חיפוש בינארי.

מטרת ה-t-SNE היא ללמוד מפה d-ממדית 𝐲1,,𝐲N ( עם 𝐲id), שמשקפת את pij בצורה כמה שיותר טובה. בשביל מטרה זו היא מודדת את qij, הדמיון בין 2 נקודות במפה,𝐲i ו 𝐲j, בצורה דומה לחישוב pij:

qij=(1+𝐲i𝐲j2)1kl(1+𝐲k𝐲l2)1

האלגוריתם משתמש בהתפלגות t כדי למדוד דמיון בין נקודות על המפה.

מיקום הנקודות 𝐲i במפה נקבעות על ידי מינימיזציה של דיברגנץ קולבק-ליבלר של ההתפלגות Q מההתפלגות P, כלומר הבאה למינימום של: KL(P||Q)=ijpijlogpijqij

המינימיזציה של Kullback–Leibler divergence ביחס לנקודות 𝐲i מתבצע באמצעות אופטימיזציית gradient descent.

התוצאה של האופטימיזציה היא מפה שמשקפת בצורה טובה את הדמיון בין קלטי המרחב הרב ממדי.

קישורים חיצוניים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

T-SNE28888661