الگوریتم کاهش ابعاد t-sne

t-sne یک روش یادگیری خودران (خودسازمانده) غیر خطی است که برای اکتشاف و بصری‌سازی داده‌ها مورد استفاده قرار می‌گیرد. به بیان ساده‌تر، t-SNE به کاربر درکی از اینکه داده‌ها چگونه در فضای ابعاد بالا سازمان‌دهی شده‌اند ارائه می‌کند که این کار را با دادن موقعیت مکانی به هر نقطه داده در یک نقشه دو یا سه بعدی است به بیانی دیگر، هر شی با ابعاد بالا را با یک نقطه دو یا سه بعدی مدل می کند، به گونه‌ای که اجسام مشابه توسط نقاط نزدیک و اجسام غیر مشابه با نقاط دور با احتمال زیاد مدل می شوند.

تفاوت روش کاهش ابعاد t-SNE و PCA

حفظ فاصله کوچک با t-SNE (خط توپر) در مقایسه با PCA بیشینه‌سازی واریانس

تحلیل مؤلفه‌های اصلی یک روش کاهش ابعاد خطی است که در تلاش برای بیشینه کردن واریانس و حفظ فاصله‌های زیاد دوتایی‌ها از یکدیگر است. به عبارت دیگر، چیزهایی که با یکدیگر متفاوت هستند به صورت دور از هم به پایان می‌رسند. این امر می‌تواند منجر به این شود که در هنگام کار با ساختارهای غیرخطی خمینه شود. ساختار خمینه می‌تواند به صورت یک شکل جغرافیایی مثلا استوانه، کره، منحنی و دیگر موارد باشد.

نظر به اینکه تحلیل مؤلفه‌های اصلی به حفظ فاصله‌های دوتایی‌های بزرگ برای بیشینه کردن واریانس می‌پردازد، t-SNE با حفظ فاصله‌های کوچک دوتایی‌ها یا شباهت محلی از تحلیل مؤلفه‌های اصلی متمایز می‌شود.

نحوه کار الگوریتم t-SNE

الگوریتم t-sne شامل دو مرحله به شرح زیر است: مرحله اول بدین صورت است که، یک توزیع احتمال بر روی نقاط در ابعاد بالاتر ایجاد می‌کند به طوری که به اشیاء مشابه احتمال بالاتر و اشیا غیر مشابه احتمال کمتر اختصاص داده می شود.

مرحله دوم بدین صورت است که، همان توزیع احتمال را در ابعاد پایین‌تر به طور مکرر تکرار می‌کند تا زمانی که واگرایی کولبک-لیبلر به حداقل برسد. به بیانی دیگر، واگرایی کولبک-لیبلر معیاری برای اندازه‌گیری تفاوت بین توزیع‌های احتمال مرحله اول و دوم است.

پیاده‌سازی الگوریتم t-sne

یک مجموعه n عضوی اشیا با ابعاد بالا به صورت $\mathbf {x} _{1},\dots ,\mathbf {x} _{N}$ در نظر بگیریم ابتدا احتمال $p_{ij}$ که بیانگر اشیا $\mathbf {x} _{i}$ و $\mathbf {x} _{j}$ است به صورت زیر محاسبه می‌کنیم:

برای $i\neq j$ داریم

$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 را تشکیل می دهیم:

$P=(p_{ij})_{i,j=1}^{n},p_{ij}={\frac {p_{j\mid i}+p_{i\mid j}}{2N}}$

همانطور که در بخش قبل گفته شد هدف t-SNE این است که نقاط با ابعاد d به صورت $\mathbf {y} _{1},\dots ,\mathbf {y} _{N}$ که تبدیل یافته از ابعاد بالا به پایین است را یاد بگیرد. مانند قبل برای توزیع Q داریم:

$Q=(q_{ij})_{i,j=1}^{n},q_{ij}={\frac {(1+|y_{i}-y_{j}|^{2})^{-1}}{\sum _{k\neq j}(1+|y_{k}-y_{l}|^{2})^{-1}}}$

در اینجا، "رابطه-همسایگی" را با توزیع تی-استودنت مدل می‌کنیم. این جایی است که t در t-SNE از آنجا می‌آید.

حال هدف ما یافتن $y_{i}$ هایی از طریق بهینه سازی است به طوری که P و Q تا حد امکان به هم نزدیک باشند، بنابراین از واگرایی کولبک-لیبلر استفاده می‌کنیم و درایم:

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

حال با از واگرایی کولبک-لیبلر نسبت به $y_{i}$ گرادیان می‌گیریم تا به بهینه ترین جواب برسیم، بنابراین داریم:

${\frac {\partial KL(P|Q)}{\partial y_{i}}}=4\sum _{j=1}^{n}(p_{ij}-q_{ij})(y_{i}-y_{j})(1+|y_{i}-y_{j}|^{2})^{-1}$

شبه کد

algorithm t-SNE is
    input: Data: X = [x1, ..., xN], xi in Rn, 
           Objective params: p (perplexity), 
           Optimization params: T(num of iterations), η (learning rate), α(momentum)
    output: Y = [y1, ..., yN], yi in Rm, m << n
    {pij} =pairwiseAffinites 0, p, X
    initialize Y = [y1, ..., yN] from N(0, 10-4 I)
    for i = 1 to T do
        compute low dimensional affinities qij
        compute ∂C / ∂yi
        yit = yit-1 + η (∂C / ∂yi)+ α(t)(yit-1 - yit-2)

کاربردهای t-SNE

کاربردهای t-SNE در زمینه‌هایی به شرح زیر است:

• پژوهش‌های اقلیمی
• امنیت رایانه‌ای
• بیوانفورماتیک
• پژوهش‌های سرطان
• یادگیری یا ارزیابی خوشه‌بندی، این کاربرد بدین گونه است که اغلب اوقات تعداد خوشه‌ها مقدم بر مدل‌سازی انتخاب یا پس از نتایج تکرار می‌شوند. t-SNE اغلب اوقات می‌تواند جداسازی شفافی در داده‌ها ارائه دهد. از این امر می‌توان مقدم بر استفاده از مدل خوشه‌بندی به منظور انتخاب تعداد خوشه‌ها یا بعدا برای ارزیابی اینکه خوشه ها به درستی داده‌ها را نگه می‌دارند یا خیر بهره برد. t-SNE یک رویکرد خوشه‌بندی نیست زیرا ورودی‌ها را مانند تحلیل مؤلفه‌های اصلی حفظ نمی‌کند و ممکن است مقادیر بین اجراها تغییر کنند، بنابراین از این روش صرفا برای اکتشاف استفاده می‌شود.