tsne

import%20marimo%0A%0A__generated_with%20%3D%20%220.11.20%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20from%20PIL%20import%20Image%0A%20%20%20%20import%20os%0A%20%20%20%20import%20base64%0A%20%20%20%20from%20IPython.display%20import%20HTML%0A%20%20%20%20from%20sklearn.datasets%20import%20fetch_openml%0A%20%20%20%20from%20sklearn.decomposition%20import%20PCA%0A%20%20%20%20import%20pandas%20as%20pd%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20warnings%0A%20%20%20%20from%20matplotlib%20import%20animation%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20os.chdir(%22assets%2Farticles%2Fnotebooks%22)%0A%20%20%20%20except%3A%0A%20%20%20%20%20%20%20%20pass%0A%0A%20%20%20%20np.seterr(divide%3D%22ignore%22%2C%20invalid%3D%22ignore%22)%0A%20%20%20%20warnings.simplefilter(%22ignore%22%2C%20RuntimeWarning)%0A%20%20%20%20warnings.filterwarnings(%22ignore%22)%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20HTML%2C%0A%20%20%20%20%20%20%20%20Image%2C%0A%20%20%20%20%20%20%20%20PCA%2C%0A%20%20%20%20%20%20%20%20animation%2C%0A%20%20%20%20%20%20%20%20base64%2C%0A%20%20%20%20%20%20%20%20fetch_openml%2C%0A%20%20%20%20%20%20%20%20mo%2C%0A%20%20%20%20%20%20%20%20np%2C%0A%20%20%20%20%20%20%20%20os%2C%0A%20%20%20%20%20%20%20%20pd%2C%0A%20%20%20%20%20%20%20%20plt%2C%0A%20%20%20%20%20%20%20%20warnings%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%20t-SNE%20from%20Scratch%20(ft.%20NumPy)%3A%20%0A%20%20%20%20%20%20%20%20%3Ccenter%3E%20**Acquire%20a%20deep%20understanding%20of%20the%20inner%20workings%20of%20t-SNE%20via%20implementation%20from%20scratch%20in%20python**%20%3C%2Fcenter%3E%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Introduction%0A%0A%20%20%20%20%20%20%20%20I%20have%20found%20that%20one%20of%20the%20best%20ways%20to%20truly%20understanding%20any%20statistical%20algorithm%20or%20methodology%20is%20to%20manually%20implement%20it%20yourself.%20On%20the%20flip%20side%2C%20coding%20these%20algorithms%20can%20sometimes%20be%20time%20consuming%20and%20a%20real%20pain%2C%20and%20when%20somebody%20else%20has%20already%20done%20it%2C%20why%20would%20I%20want%20to%20spend%20my%20time%20doing%20it%20%E2%80%94%20seems%20inefficient%2C%20no%3F%20Both%20are%20fair%20points%2C%20and%20I%20am%20not%20here%20to%20make%20an%20argument%20for%20one%20over%20the%20other.%0A%0A%20%20%20%20%20%20%20%20This%20article%20is%20designed%20for%20readers%20who%20are%20interested%20in%20understanding%20t-SNE%20via%20translation%20of%20the%20mathematics%20in%20the%20%5Boriginal%20paper%5D(https%3A%2F%2Fjmlr.org%2Fpapers%2Fvolume9%2Fvandermaaten08a%2Fvandermaaten08a.pdf)%20%E2%80%94%20by%20Laurens%20van%20der%20Maaten%20%26%20Geoffrey%20Hinton%20%E2%80%94%20into%20python%20code%20implementation.%5B1%5D%20I%20find%20these%20sort%20of%20exercises%20to%20be%20quite%20illuminating%20into%20the%20inner%20workings%20of%20statistical%20algorithms%2Fmodels%20and%20really%20test%20your%20underlying%20understanding%20and%20assumptions%20regarding%20these%20algorithms%2Fmodels.%20You%20are%20almost%20guaranteed%20to%20walk%20away%20with%20a%20better%20understanding%20then%20you%20had%20before.%20At%20the%20very%20minimum%2C%20successful%20implementation%20is%20always%20very%20satisfying!%0A%0A%20%20%20%20%20%20%20%20This%20article%20will%20be%20accessible%20to%20individuals%20with%20any%20level%20of%20exposure%20of%20t-SNE.%20However%2C%20note%20a%20few%20things%20this%20post%20definitely%20is%20**not**%3A%0A%0A%20%20%20%20%20%20%20%201.%20A%20_strictly_%20conceptual%20introduction%20and%20exploration%20of%20t-SNE%2C%20as%20there%20are%20plenty%20of%20other%20great%20resources%20out%20there%20that%20do%20this%3B%20nevertheless%2C%20I%20will%20be%20doing%20my%20best%20to%20connect%20the%20mathematical%20equations%20to%20their%20intuitive%2Fconceptual%20counterparts%20at%20each%20stage%20of%20implementation.%0A%0A%20%20%20%20%20%20%20%202.%20A%20_comprehensive_%20discussion%20into%20the%20applications%20%26%20pros%2Fcons%20of%20t-SNE%2C%20as%20well%20as%20direct%20comparisons%20of%20t-SNE%20to%20other%20dimensionality%20reduction%20techniques.%20I%20will%2C%20however%2C%20briefly%20touch%20on%20these%20topics%20throughout%20this%20article%2C%20but%20will%20by%20no%20means%20cover%20this%20in-depth.%0A%0A%20%20%20%20%20%20%20%20Without%20further%20ado%2C%20let%E2%80%99s%20start%20with%20a%20_brief_%20introduction%20into%20t-SNE.%0A%0A%20%20%20%20%20%20%20%20%23%23%20A%20Brief%20Introduction%20to%20t-SNE%0A%0A%20%20%20%20%20%20%20%20_t-distributed%20stochastic%20neighbor%20embedding_%20(t-SNE)%20is%20a%20dimensionality%20reduction%20tool%20that%20is%20primarily%20used%20in%20datasets%20with%20a%20large%20dimensional%20feature%20space%20and%20enables%20one%20to%20visualize%20the%20data%20down%2C%20or%20project%20it%2C%20into%20a%20lower%20dimensional%20space%20(usually%202-D).%20It%20is%20especially%20useful%20for%20visualizing%20non-linearly%20separable%20data%20wherein%20linear%20methods%20such%20as%20%5BPrincipal%20Component%20Analysis%5D(https%3A%2F%2Fen.m.wikipedia.org%2Fwiki%2FPrincipal_component_analysis)%20(PCA)%20would%20fail.%20Generalizing%20linear%20frameworks%20of%20dimensionality%20reduction%20(such%20as%20PCA)%20into%20non-linear%20approaches%20(such%20as%20t-SNE)%20is%20also%20known%20as%20%5BManifold%20Learning%5D(https%3A%2F%2Fen.m.wikipedia.org%2Fwiki%2FNonlinear_dimensionality_reduction).%20These%20methods%20can%20be%20extremely%20useful%20for%20visualizing%20and%20understanding%20the%20underlying%20structure%20of%20a%20high%20dimensional%2C%20non-linear%20data%20set%2C%20and%20can%20be%20great%20for%20disentangling%20and%20grouping%20together%20observations%20that%20are%20similar%20in%20the%20high-dimensional%20space.%20For%20more%20information%20on%20t-SNE%20and%20other%20manifold%20learning%20techniques%2C%20the%20%5Bscikit-learn%20documentation%5D(https%3A%2F%2Fscikit-learn.org%2Fstable%2Fmodules%2Fmanifold.html)%20is%20a%20great%20resource.%20Additionally%2C%20to%20read%20about%20some%20cool%20areas%20t-SNE%20has%20seen%20applications%2C%20the%20%5BWikipedia%20page%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FT-distributed_stochastic_neighbor_embedding%23cite_note-3)%20highlights%20some%20of%20these%20areas%20with%20references%20to%20the%20work.%0A%0A%20%20%20%20%20%20%20%20Let%E2%80%99s%20start%20with%20breaking%20down%20the%20name%20_t-distributed%20stochastic%20neighbor%20embedding_%20into%20its%20components.%20t-SNE%20is%20an%20extension%20on%20stochastic%20neighbor%20embedding%20(SNE)%20presented%206%20years%20earlier%20in%20this%20%5Bpaper%5D(https%3A%2F%2Fcs.nyu.edu%2F~roweis%2Fpapers%2Fsne_final.pdf)%20by%20Geoffrey%20Hinton%20%26%20Sam%20Roweis.%20So%20let%E2%80%99s%20start%20there.%20The%20_stochastic_%20part%20of%20the%20name%20comes%20from%20the%20fact%20that%20the%20objective%20function%20is%20not%20convex%20and%20thus%20different%20results%20can%20arise%20from%20different%20initializations.%20The%20_neighbor%20embedding_%20highlights%20the%20nature%20of%20the%20algorithm%20%E2%80%94%20optimally%20mapping%20the%20points%20in%20the%20original%20high-dimensional%20space%20into%20the%20corresponding%20low-dimensional%20space%20while%20best%20preserving%20the%20%E2%80%9Cneighborhood%E2%80%9D%20structure%20of%20the%20points.%20SNE%20is%20comprised%20of%20the%20following%20(simplified)%20steps%3A%0A%0A%20%20%20%20%20%20%20%201.%20_Obtain%20the%20Similarity%20Matrix%20between%20Points%20in%20the%20Original%20Space_%3A%20Compute%20the%20conditional%20probabilities%20for%20each%20datapoint%20%24j%24%20relative%20to%20each%20datapoint%20%24i%24.%20These%20conditional%20probabilities%20are%20calculated%20in%20the%20original%20high-dimensional%20space%20using%20a%20Gaussian%20centered%20at%20%24i%24%20and%20take%20on%20the%20following%20interpretation%3A%20the%20probability%20that%20i%20would%20pick%20%24j%24%20as%20its%20neighbor%20in%20the%20original%20space.%20This%20creates%20a%20matrix%20that%20represents%20similarities%20between%20the%20points.%0A%0A%20%20%20%20%20%20%20%202.%20_Initialization_%3A%20Choose%20random%20starting%20points%20in%20the%20lower-dimensional%20space%20(say%2C%202-D)%20for%20each%20datapoint%20in%20the%20original%20space%20and%20compute%20new%20conditional%20probabilities%20similarly%20as%20above%20in%20this%20new%20space.%0A%0A%20%20%20%20%20%20%20%203.%20_Mapping_%3A%20Iteratively%20improve%20upon%20the%20points%20in%20the%20lower-dimensional%20space%20until%20the%20%5BKullback-Leibler%20divergences%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FKullback%25E2%2580%2593Leibler_divergence)%20between%20all%20the%20conditional%20probabilities%20is%20minimized.%20Essentially%20we%20are%20minimizing%20the%20differences%20in%20the%20probabilities%20between%20the%20similarity%20matrices%20of%20the%20two%20spaces%20so%20as%20to%20ensure%20the%20similarities%20are%20best%20preserved%20in%20the%20mapping%20of%20the%20original%20high-dimensional%20dataset%20to%20the%20low-dimensional%20dataset.%0A%0A%20%20%20%20%20%20%20%20t-SNE%20improves%20upon%20SNE%20in%20two%20primary%20ways%3A%0A%0A%20%20%20%20%20%20%20%201.%20It%20minimizes%20the%20Kullback-Leibler%20divergences%20between%20the%20joint%20probabilities%20rather%20than%20the%20conditional%20probabilities.%20The%20authors%20refer%20to%20this%20as%20%E2%80%9Csymmetric%20SNE%E2%80%9D%20b%2Fc%20their%20approach%20ensures%20that%20the%20joint%20probabilities%20%24p_ij%24%20%3D%20%24p_ji%24.%20**This%20results%20in%20a%20much%20better%20behaved%20cost%20function%20that%20is%20easier%20to%20optimize.**%0A%0A%20%20%20%20%20%20%20%202.%20It%20computes%20the%20similarities%20between%20points%20using%20a%20%5Bstudent's%20t-distribution%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FStudent%2527s_t-distribution)%20w%2F%20one%20degree%20of%20freedom%20(also%20a%20%5BCauchy%20Distribution%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FCauchy_distribution))%20rather%20than%20a%20Gaussian%20in%20the%20low-dimensional%20space%20(step%202%20above).%20Here%20we%20can%20see%20where%20the%20%E2%80%9Ct%E2%80%9D%20in%20t-SNE%20is%20coming%20from.%20**This%20improvement%20helps%20to%20alleviate%20the%20%E2%80%9Ccrowding%20problem%E2%80%9D%20highlighted%20by%20the%20authors%20and%20to%20further%20improve%20the%20optimization%20problem.**%20This%20%E2%80%9Ccrowding%20problem%E2%80%9D%20can%20be%20envisioned%20as%20such%3A%20Imagine%20we%20have%20a%2010-D%20space%2C%20the%20amount%20of%20space%20available%20in%202-D%20will%20not%20be%20sufficient%20to%20accurately%20capture%20those%20moderately%20dissimilar%20points%20compared%20to%20the%20amount%20of%20space%20for%20nearby%20points%20relative%20to%20the%20amount%20of%20space%20available%20in%20a%2010-D%20space.%20More%20simply%2C%20just%20envision%20taking%20a%203-D%20space%20and%20projecting%20it%20down%20to%202-D%2C%20the%203-D%20space%20will%20have%20much%20more%20overall%20space%20to%20model%20the%20similarities%20relative%20to%20the%20projection%20down%20into%202-D.%20The%20Student-t%20distribution%20helps%20alleviate%20this%20problem%20by%20having%20heavier%20tails%20than%20the%20normal%20distribution.%20See%20the%20%5Boriginal%20paper%5D(https%3A%2F%2Fjmlr.org%2Fpapers%2Fvolume9%2Fvandermaaten08a%2Fvandermaaten08a.pdf)%20for%20a%20much%20more%20in-depth%20treatment%20of%20this%20problem.%0A%0A%20%20%20%20%20%20%20%20If%20this%20did%20not%20all%20track%20immediately%2C%20that%20is%20okay!%20I%20am%20hoping%20when%20we%20implement%20this%20in%20code%2C%20the%20pieces%20will%20all%20fall%20in%20to%20place.%20The%20main%20takeaway%20is%20this%3A%20**t-SNE%20models%20similarities%20between%20datapoints%20in%20the%20high-dimensional%20space%20using%20joint%20probabilities%20of%20%E2%80%9Cdatapoints%20choosing%20others%20as%20its%20neighbor%E2%80%9D%2C%20and%20then%20tries%20to%20find%20the%20best%20mapping%20of%20these%20points%20down%20into%20the%20low-dimensional%20space%2C%20while%20best%20preserving%20the%20original%20high-dimensional%20similarities.**%0A%0A%20%20%20%20%20%20%20%20%23%23%20Implementation%20from%20Scratch%0A%0A%20%20%20%20%20%20%20%20Let%E2%80%99s%20now%20move%20on%20to%20understanding%20t-SNE%20via%20implementing%20the%20original%20version%20of%20the%20algorithm%20as%20presented%20in%20the%20%5Bpaper%5D(https%3A%2F%2Fjmlr.org%2Fpapers%2Fvolume9%2Fvandermaaten08a%2Fvandermaaten08a.pdf)%20by%20Laurens%20van%20der%20Maaten%20%26%20Geoffrey%20Hinton.%20We%20will%20first%20start%20with%20implementing%20algorithm%201%20below%20step-by-step%2C%20which%20will%20cover%2095%25%20of%20the%20main%20algorithm.%20There%20are%20two%20additional%20enhancements%20the%20authors%20note%3A%201)%20Early%20Exaggeration%20%26%202)%20Adaptive%20Learning%20Rates.%20We%20will%20only%20discuss%20adding%20in%20the%20early%20exaggeration%20as%20that%20is%20most%20conducive%20in%20aiding%20the%20interpretation%20of%20the%20actual%20algorithms%20inner%20workings%2C%20as%20the%20adaptive%20learning%20rate%20is%20focused%20on%20improving%20the%20rates%20of%20convergence.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.image(%22data%2Falgorithm.webp%22).center()%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%201.%20Inputs%0A%0A%20%20%20%20%20%20%20%20Following%20the%20original%20paper%2C%20we%20will%20be%20using%20the%20publicly%20available%20%5BMNIST%20dataset%5D(https%3A%2F%2Fwww.openml.org%2Fsearch%3Ftype%3Ddata%26status%3Dactive%26id%3D554%26sort%3Druns)%20from%20OpenML%20with%20images%20of%20handwritten%20digits%20from%200%E2%80%939.%5B2%5D%20We%20will%20also%20randomly%20sample%201000%20images%20from%20the%20dataset%20%26%20reduce%20the%20dimensionality%20of%20the%20dataset%20using%20Principal%20Component%20Analysis%20(PCA)%20and%20keep%2030%20components.%20These%20are%20both%20to%20improve%20computational%20time%20of%20the%20algorithm%2C%20as%20the%20code%20here%20is%20not%20optimized%20for%20speed%2C%20but%20rather%20for%20interpretability%20%26%20learning.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(PCA%2C%20fetch_openml%2C%20np%2C%20pd)%3A%0A%20%20%20%20%23%20Fetch%20MNIST%20data%0A%20%20%20%20mnist%20%3D%20fetch_openml(%22mnist_784%22%2C%20version%3D1%2C%20as_frame%3DFalse)%0A%20%20%20%20mnist.target%20%3D%20mnist.target.astype(np.uint8)%0A%0A%20%20%20%20X_total%20%3D%20pd.DataFrame(mnist%5B%22data%22%5D)%0A%20%20%20%20y_total%20%3D%20pd.DataFrame(mnist%5B%22target%22%5D)%0A%0A%20%20%20%20X_reduced%20%3D%20X_total.sample(n%3D1000)%0A%20%20%20%20y_reduced%20%3D%20y_total.loc%5BX_reduced.index%5D%0A%0A%20%20%20%20%23%20PCA%20to%20keep%2030%20components%0A%20%20%20%20X%20%3D%20PCA(n_components%3D30).fit_transform(X_reduced)%0A%20%20%20%20return%20X%2C%20X_reduced%2C%20X_total%2C%20mnist%2C%20y_reduced%2C%20y_total%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22This%20will%20be%20our%20X%20dataset%20with%20each%20row%20being%20an%20image%20and%20each%20column%20being%20a%20feature%2C%20or%20principal%20component%20in%20this%20case%20(i.e.%20linear%20combinations%20of%20the%20original%20pixels)%3A%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(X%2C%20pd)%3A%0A%20%20%20%20%23%20To%20make%20it%20look%20pretty%20in%20marimo%0A%20%20%20%20df_X%20%3D%20pd.DataFrame(X)%0A%20%20%20%20df_X.columns%20%3D%20df_X.columns.astype(str)%0A%20%20%20%20df_X%0A%20%20%20%20return%20(df_X%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20We%20also%20will%20need%20to%20specify%20the%20cost%20function%20parameters%20%E2%80%94%20perplexity%20%E2%80%94%20and%20the%20optimization%20parameters%20%E2%80%94%20iterations%2C%20learning%20rate%2C%20%26%20momentum.%20We%20will%20hold%20off%20on%20these%20for%20now%20and%20address%20them%20as%20they%20appear%20at%20each%20stage.%0A%0A%20%20%20%20%20%20%20%20In%20terms%20of%20output%2C%20recall%20that%20we%20seek%20a%20the%20low-dimensional%20mapping%20of%20the%20original%20dataset%20X.%20We%20will%20be%20mapping%20the%20original%20space%20into%20a%202%20dimensional%20space%20throughout%20this%20example.%20Thus%2C%20our%20new%20output%20will%20be%20the%201000%20images%20now%20represented%20in%20a%202%20dimensional%20space%20rather%20than%20the%20original%2030%20dimensional%20space%2C%20with%20a%20shape%20of%20%5B1000%2C%202%5D.%0A%0A%20%20%20%20%20%20%20%20%23%23%23%202.%20Compute%20Affinities%2FSimilarities%20of%20X%20in%20the%20Original%20Space%0A%0A%20%20%20%20%20%20%20%20Now%20that%20we%20have%20our%20inputs%2C%20the%20first%20step%20is%20to%20compute%20the%20pairwise%20similarities%20in%20the%20original%20high%20dimensional%20space.%20That%20is%2C%20for%20each%20image%20%24i%24%20we%20compute%20the%20probability%20that%20%24i%24%20would%20pick%20image%20%24j%24%20as%20its%20neighbor%20in%20the%20original%20space%20for%20each%20%24j%24.%20These%20probabilities%20are%20calculated%20via%20a%20normal%20distribution%20centered%20around%20each%20point%20and%20then%20are%20normalized%20to%20sum%20up%20to%201.%20Mathematically%2C%20we%20have%3A%0A%0A%20%20%20%20%20%20%20%20%24%24%0A%20%20%20%20%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%20%20%20%20p_%7Bj%7Ci%7D%3D%5Cfrac%7B%5Cexp%7B(-%5C%7Cx_i-x_j%5C%7C%5E2%2F2%5Csigma_i%5E2)%7D%7D%7B%5Csum_%7Bk%5Cne%20i%7D%5Cexp%7B(-%5C%7Cx_i-x_j%5C%7C%5E2%2F2%5Csigma_i%5E2)%7D%7D%0A%20%20%20%20%20%20%20%20%5Ctag%7B1%7D%0A%20%20%20%20%20%20%20%20%5Cend%7Bequation%7D%0A%20%20%20%20%20%20%20%20%24%24%0A%0A%20%20%20%20%20%20%20%20Note%20that%2C%20in%20our%20case%20with%20n%20%3D%201000%2C%20these%20computations%20will%20result%20in%20a%201000%20x%201000%20matrix%20of%20similarity%20scores.%20Note%20we%20set%20%24p%24%20%3D%200%20whenever%20%24i%24%20%3D%20%24j%24%20b%2Fc%20we%20are%20modeling%20pairwise%20similarities.%20However%2C%20you%20may%20notice%20that%20we%20have%20not%20mentioned%20how%20%24%5Csigma%24%20is%20determined.%20This%20value%20is%20determined%20for%20each%20observation%20%24i%24%20via%20a%20grid%20search%20based%20on%20the%20user-specified%20desired%20%5Bperplexity%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FPerplexity)%20of%20the%20distributions.%20We%20will%20talk%20about%20this%20immediately%20below%2C%20but%20let%E2%80%99s%20first%20look%20at%20how%20we%20would%20code%20eq.%20(1)%20above%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(grid_search%2C%20np)%3A%0A%20%20%20%20def%20get_original_pairwise_affinities(%0A%20%20%20%20%20%20%20%20X%3A%20np.ndarray%2C%20perplexity%3A%20int%20%3D%2010%0A%20%20%20%20)%20-%3E%20np.ndarray%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20Function%20to%20obtain%20affinities%20matrix.%0A%0A%20%20%20%20%20%20%20%20Parameters%0A%20%20%20%20%20%20%20%20----------%0A%20%20%20%20%20%20%20%20X%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20input%20data%20array.%0A%20%20%20%20%20%20%20%20perplexity%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20perplexity%20value%20for%20the%20grid%20search.%0A%0A%20%20%20%20%20%20%20%20Returns%0A%20%20%20%20%20%20%20%20------%0A%20%20%20%20%20%20%20%20np.ndarray%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20pairwise%20affinities%20matrix.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%0A%20%20%20%20%20%20%20%20n%20%3D%20len(X)%0A%0A%20%20%20%20%20%20%20%20print(%22Computing%20Pairwise%20Affinities....%22)%0A%0A%20%20%20%20%20%20%20%20p_ij%20%3D%20np.zeros(shape%3D(n%2C%20n))%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(0%2C%20n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Equation%201%20numerator%0A%20%20%20%20%20%20%20%20%20%20%20%20diff%20%3D%20X%5Bi%5D%20-%20X%0A%20%20%20%20%20%20%20%20%20%20%20%20%CF%83_i%20%3D%20grid_search(diff%2C%20i%2C%20perplexity)%20%20%23%20Grid%20Search%20for%20%CF%83_i%0A%20%20%20%20%20%20%20%20%20%20%20%20norm%20%3D%20np.linalg.norm(diff%2C%20axis%3D1)%0A%20%20%20%20%20%20%20%20%20%20%20%20p_ij%5Bi%2C%20%3A%5D%20%3D%20np.exp(-(norm**2)%20%2F%20(2%20*%20%CF%83_i**2))%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Set%20p%20%3D%200%20when%20j%20%3D%20i%0A%20%20%20%20%20%20%20%20%20%20%20%20np.fill_diagonal(p_ij%2C%200)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Equation%201%0A%20%20%20%20%20%20%20%20%20%20%20%20p_ij%5Bi%2C%20%3A%5D%20%3D%20p_ij%5Bi%2C%20%3A%5D%20%2F%20np.sum(p_ij%5Bi%2C%20%3A%5D)%0A%0A%20%20%20%20%20%20%20%20%23%20Set%200%20values%20to%20minimum%20numpy%20value%20(%CE%B5%20approx.%20%3D%200)%0A%20%20%20%20%20%20%20%20%CE%B5%20%3D%20np.nextafter(0%2C%201)%0A%20%20%20%20%20%20%20%20p_ij%20%3D%20np.maximum(p_ij%2C%20%CE%B5)%0A%0A%20%20%20%20%20%20%20%20print(%22Completed%20Pairwise%20Affinities%20Matrix.%20%5Cn%22)%0A%0A%20%20%20%20%20%20%20%20return%20p_ij%0A%20%20%20%20return%20(get_original_pairwise_affinities%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20Now%20before%20we%20look%20at%20the%20results%20of%20this%20code%2C%20let%E2%80%99s%20discuss%20how%20we%20determine%20the%20values%20of%20%24%5Csigma%24%20via%20the%20grid_search()%20function.%20Given%20a%20specified%20value%20of%20perplexity%20(which%20in%20this%20context%20can%20be%20loosely%20thought%20about%20as%20the%20number%20of%20nearest%20neighbors%20for%20each%20point)%2C%20we%20do%20a%20grid%20search%20over%20a%20range%20of%20values%20of%20%24%5Csigma%24%20such%20that%20the%20following%20equation%20is%20as%20close%20to%20equality%20as%20possible%20for%20each%20%24i%24%3A%0A%0A%20%20%20%20%20%20%20%20%24%24%0A%20%20%20%20%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%20%20%20%20Perp(P_i)%3D2%5E%7BH(P_i)%7D%0A%20%20%20%20%20%20%20%20%5Ctag%7B2%7D%0A%20%20%20%20%20%20%20%20%5Cend%7Bequation%7D%0A%20%20%20%20%20%20%20%20%24%24%0A%0A%20%20%20%20%20%20%20%20where%20%24H(P_i)%24%20is%20the%20Shannon%20entropy%20of%20%24P%24%3A%0A%0A%20%20%20%20%20%20%20%20%24%24%0A%20%20%20%20%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%20%20%20%20H(P_i)%20%3D%20-%20%5Csum_jp_%7Bj%7Ci%7D%5Clog_2p_%7Bj%7Ci%7D%0A%20%20%20%20%20%20%20%20%5Ctag%7B2%7D%0A%20%20%20%20%20%20%20%20%5Cend%7Bequation%7D%0A%20%20%20%20%20%20%20%20%24%24%0A%0A%20%20%20%20%20%20%20%20In%20our%20case%2C%20we%20will%20set%20perplexity%20%3D%2010%20and%20set%20the%20search%20space%20to%20be%20defined%20by%20%5B0.01%20*%20standard%20deviation%20of%20the%20norms%20for%20the%20difference%20between%20images%20%24i%24%20and%20%24j%24%2C%205%20*%20standard%20deviation%20of%20the%20norms%20for%20the%20difference%20between%20images%20%24i%24%20and%20%24j%24%5D%20divided%20into%20200%20equal%20steps.%20Knowing%20this%2C%20we%20can%20define%20our%20grid_search()%20function%20as%20follows%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20def%20grid_search(diff_i%3A%20np.ndarray%2C%20i%3A%20int%2C%20perplexity%3A%20int)%20-%3E%20float%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20Helper%20function%20to%20obtain%20%CF%83's%20based%20on%20user-specified%20perplexity.%0A%0A%20%20%20%20%20%20%20%20Parameters%0A%20%20%20%20%20%20%20%20-----------%0A%20%20%20%20%20%20%20%20diff_i%0A%20%20%20%20%20%20%20%20%20%20%20%20Array%20containing%20the%20pairwise%20differences%20between%20data%20points.%0A%20%20%20%20%20%20%20%20i%0A%20%20%20%20%20%20%20%20%20%20%20%20Index%20of%20the%20current%20data%20point.%0A%20%20%20%20%20%20%20%20perplexity%0A%20%20%20%20%20%20%20%20%20%20%20%20User-specified%20perplexity%20value.%0A%0A%20%20%20%20%20%20%20%20Returns%0A%20%20%20%20%20%20%20%20-------%0A%20%20%20%20%20%20%20%20float%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20value%20of%20%CF%83%20that%20satisfies%20the%20perplexity%20condition.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%0A%20%20%20%20%20%20%20%20result%20%3D%20np.inf%20%20%23%20Set%20first%20result%20to%20be%20infinity%0A%0A%20%20%20%20%20%20%20%20norm%20%3D%20np.linalg.norm(diff_i%2C%20axis%3D1)%0A%20%20%20%20%20%20%20%20std_norm%20%3D%20np.std(%0A%20%20%20%20%20%20%20%20%20%20%20%20norm%0A%20%20%20%20%20%20%20%20)%20%20%23%20Use%20standard%20deviation%20of%20norms%20to%20define%20search%20space%0A%0A%20%20%20%20%20%20%20%20for%20%CF%83_search%20in%20np.linspace(0.01%20*%20std_norm%2C%205%20*%20std_norm%2C%20200)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Equation%201%20Numerator%0A%20%20%20%20%20%20%20%20%20%20%20%20p%20%3D%20np.exp(-(norm**2)%20%2F%20(2%20*%20%CF%83_search**2))%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Set%20p%20%3D%200%20when%20i%20%3D%20j%0A%20%20%20%20%20%20%20%20%20%20%20%20p%5Bi%5D%20%3D%200%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Equation%201%20(%CE%B5%20-%3E%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20%CE%B5%20%3D%20np.nextafter(0%2C%201)%0A%20%20%20%20%20%20%20%20%20%20%20%20p_new%20%3D%20np.maximum(p%20%2F%20np.sum(p)%2C%20%CE%B5)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Shannon%20Entropy%0A%20%20%20%20%20%20%20%20%20%20%20%20H%20%3D%20-np.sum(p_new%20*%20np.log2(p_new))%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Get%20log(perplexity%20equation)%20as%20close%20to%20equality%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20np.abs(np.log(perplexity)%20-%20H%20*%20np.log(2))%20%3C%20np.abs(result)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20result%20%3D%20np.log(perplexity)%20-%20H%20*%20np.log(2)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%CF%83%20%3D%20%CF%83_search%0A%0A%20%20%20%20%20%20%20%20return%20%CF%83%0A%20%20%20%20return%20(grid_search%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22Given%20these%20functions%2C%20we%20can%20compute%20the%20affinity%20matrix%20via%3A%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(X%2C%20get_original_pairwise_affinities)%3A%0A%20%20%20%20p_ij%20%3D%20get_original_pairwise_affinities(X)%0A%20%20%20%20return%20(p_ij%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(p_ij%2C%20pd)%3A%0A%20%20%20%20%23%20To%20make%20it%20look%20pretty%20in%20marimo%0A%20%20%20%20df_p_ij%20%3D%20pd.DataFrame(p_ij)%0A%20%20%20%20df_p_ij.columns%20%3D%20df_p_ij.columns.astype(%22str%22)%0A%20%20%20%20df_p_ij%0A%20%20%20%20return%20(df_p_ij%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20Note%2C%20the%20diagonal%20elements%20are%20set%20to%20%24%5Cepsilon%20%5Capprox%200%24%20by%20construction%20(whenever%20%24i%24%20%3D%20%24j%24).%20Recall%20that%20a%20key%20extension%20of%20the%20t-SNE%20algorithm%20is%20to%20compute%20the%20joint%20probabilities%20rather%20than%20the%20conditional%20probabilities.%20This%20is%20computed%20simply%20as%20follow%3A%0A%0A%20%20%20%20%20%20%20%20%24%24%0A%20%20%20%20%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%20%20%20%20p_%7Bij%7D%3D%5Cfrac%7Bp_%7Bj%7Ci%7D%2Bp_%7Bi%7Cj%7D%7D%7B2n%7D%0A%20%20%20%20%20%20%20%20%5Ctag%7B3%7D%0A%20%20%20%20%20%20%20%20%5Cend%7Bequation%7D%0A%20%20%20%20%20%20%20%20%24%24%0A%0A%20%20%20%20%20%20%20%20Thus%2C%20we%20can%20define%20a%20new%20function%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20def%20get_symmetric_p_ij(p_ij%3A%20np.ndarray)%20-%3E%20np.ndarray%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20Function%20to%20obtain%20symmetric%20affinities%20matrix%20utilized%20in%20t-SNE.%0A%0A%20%20%20%20%20%20%20%20Parameters%0A%20%20%20%20%20%20%20%20----------%0A%20%20%20%20%20%20%20%20p_ij%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20input%20affinity%20matrix.%0A%0A%20%20%20%20%20%20%20%20Returns%0A%20%20%20%20%20%20%20%20np.ndarray%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20symmetric%20affinities%20matrix.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20print(%22Computing%20Symmetric%20p_ij%20matrix....%22)%0A%0A%20%20%20%20%20%20%20%20n%20%3D%20len(p_ij)%0A%20%20%20%20%20%20%20%20p_ij_symmetric%20%3D%20np.zeros(shape%3D(n%2C%20n))%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(0%2C%20n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20j%20in%20range(0%2C%20n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20p_ij_symmetric%5Bi%2C%20j%5D%20%3D%20(p_ij%5Bi%2C%20j%5D%20%2B%20p_ij%5Bj%2C%20i%5D)%20%2F%20(2%20*%20n)%0A%0A%20%20%20%20%20%20%20%20%23%20Set%200%20values%20to%20minimum%20numpy%20value%20(%CE%B5%20approx.%20%3D%200)%0A%20%20%20%20%20%20%20%20%CE%B5%20%3D%20np.nextafter(0%2C%201)%0A%20%20%20%20%20%20%20%20p_ij_symmetric%20%3D%20np.maximum(p_ij_symmetric%2C%20%CE%B5)%0A%0A%20%20%20%20%20%20%20%20print(%22Completed%20Symmetric%20p_ij%20Matrix.%20%5Cn%22)%0A%0A%20%20%20%20%20%20%20%20return%20p_ij_symmetric%0A%20%20%20%20return%20(get_symmetric_p_ij%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22Feeding%20in%20%60p_ij%60%20from%20above%2C%20we%20obtain%20the%20following%20symmetric%20affinities%20matrix%3A%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(get_symmetric_p_ij%2C%20p_ij)%3A%0A%20%20%20%20p_ij_symmetric%20%3D%20get_symmetric_p_ij(p_ij)%0A%20%20%20%20return%20(p_ij_symmetric%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(p_ij_symmetric%2C%20pd)%3A%0A%20%20%20%20%23%20To%20make%20it%20look%20pretty%20in%20marimo%0A%20%20%20%20df_p_ij_symmetric%20%3D%20pd.DataFrame(p_ij_symmetric)%0A%20%20%20%20df_p_ij_symmetric.columns%20%3D%20df_p_ij_symmetric.columns.astype(%22str%22)%0A%20%20%20%20df_p_ij_symmetric%0A%20%20%20%20return%20(df_p_ij_symmetric%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20Now%20we%20have%20completed%20the%20first%20main%20step%20in%20t-SNE!%20We%20computed%20the%20symmetric%20affinity%20matrix%20in%20the%20original%20high-dimensional%20space.%20Before%20we%20dive%20right%20into%20the%20optimization%20stage%2C%20we%20will%20discuss%20the%20main%20components%20of%20the%20optimization%20problem%20in%20the%20next%20two%20steps%20and%20then%20combine%20them%20into%20our%20for%20loop.%0A%0A%20%20%20%20%20%20%20%20%23%23%23%203.%20Sample%20Initial%20Solution%20%26%20Compute%20Low%20Dimensional%20Affinity%20Matrix%0A%0A%20%20%20%20%20%20%20%20Now%20we%20want%20to%20sample%20a%20random%20initial%20solution%20in%20the%20lower%20dimensional%20space%20as%20follows%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20def%20initialization(%0A%20%20%20%20%20%20%20%20X%3A%20np.ndarray%2C%20n_dimensions%3A%20int%20%3D%202%2C%20initialization%3A%20str%20%3D%20%22random%22%0A%20%20%20%20)%20-%3E%20np.ndarray%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20Obtain%20initial%20solution%20for%20t-SNE%20either%20randomly%20or%20using%20PCA.%0A%0A%20%20%20%20%20%20%20%20Parameters%0A%20%20%20%20%20%20%20%20----------%0A%20%20%20%20%20%20%20%20X%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20input%20data%20array.%0A%20%20%20%20%20%20%20%20n_dimensions%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20number%20of%20dimensions%20for%20the%20output%20solution.%20Default%20is%202.%0A%20%20%20%20%20%20%20%20initialization%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20initialization%20method.%20Can%20be%20'random'%20or%20'PCA'.%20Default%20is%20'random'.%0A%0A%20%20%20%20%20%20%20%20Returns%0A%20%20%20%20%20%20%20%20-------%0A%20%20%20%20%20%20%20%20np.ndarray%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20initial%20solution%20for%20t-SNE.%0A%0A%20%20%20%20%20%20%20%20Raises%0A%20%20%20%20%20%20%20%20-------%0A%20%20%20%20%20%20%20%20ValueError%0A%20%20%20%20%20%20%20%20%20%20%20%20If%20the%20initialization%20method%20is%20neither%20'random'%20nor%20'PCA'.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%0A%20%20%20%20%20%20%20%20%23%20Sample%20Initial%20Solution%0A%20%20%20%20%20%20%20%20if%20initialization%20%3D%3D%20%22random%22%20or%20initialization%20!%3D%20%22PCA%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20y0%20%3D%20np.random.normal(loc%3D0%2C%20scale%3D1e-4%2C%20size%3D(len(X)%2C%20n_dimensions))%0A%20%20%20%20%20%20%20%20elif%20initialization%20%3D%3D%20%22PCA%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20X_centered%20%3D%20X%20-%20X.mean(axis%3D0)%0A%20%20%20%20%20%20%20%20%20%20%20%20_%2C%20_%2C%20Vt%20%3D%20np.linalg.svd(X_centered)%0A%20%20%20%20%20%20%20%20%20%20%20%20y0%20%3D%20X_centered%20%40%20Vt.T%5B%3A%2C%20%3An_dimensions%5D%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20raise%20ValueError(%22Initialization%20must%20be%20'random'%20or%20'PCA'%22)%0A%0A%20%20%20%20%20%20%20%20return%20y0%0A%20%20%20%20return%20(initialization%2C)%0A%0A%0A%40app.cell%0Adef%20_(X%2C%20initialization)%3A%0A%20%20%20%20y0%20%3D%20initialization(X)%0A%20%20%20%20return%20(y0%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(pd%2C%20y0)%3A%0A%20%20%20%20df_y0%20%3D%20pd.DataFrame(y0)%0A%20%20%20%20df_y0.columns%20%3D%20df_y0.columns.astype(%22str%22)%0A%20%20%20%20df_y0%0A%20%20%20%20return%20(df_y0%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20Now%2C%20we%20want%20to%20compute%20the%20affinity%20matrix%20in%20this%20lower%20dimensional%20space.%20However%2C%20recall%20that%20we%20do%20this%20utilizing%20a%20student's%20t-distribution%20w%2F%201%20degree%20of%20freedom%3A%0A%0A%20%20%20%20%20%20%20%20%24%24%0A%20%20%20%20%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%20%20%20%20q_%7Bij%7D%3D%5Cfrac%7B(1%2B%5C%7Cy_i-y_j%5C%7C%5E2)%5E%7B-1%7D%7D%7B%5Csum_%7Bk%20%5Cne%20l%7D%20(1%2B%5C%7Cy_i-y_j%5C%7C%5E2)%5E%7B-1%7D%7D%0A%20%20%20%20%20%20%20%20%5Ctag%7B4%7D%0A%20%20%20%20%20%20%20%20%5Cend%7Bequation%7D%0A%20%20%20%20%20%20%20%20%24%24%0A%0A%20%20%20%20%20%20%20%20Again%2C%20we%20set%20%24q%3D0%24%20whenever%20%24i%20%3D%20j%24.%20Note%20this%20equation%20differs%20from%20eq.%20(1)%20in%20that%20the%20denominator%20is%20over%20all%20%24i%24%20and%20thus%20symmetric%20by%20construction.%20Putting%20this%20into%20code%2C%20we%20obtain%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20def%20get_low_dimensional_affinities(Y%3A%20np.ndarray)%20-%3E%20np.ndarray%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20Obtain%20low-dimensional%20affinities.%0A%0A%20%20%20%20%20%20%20%20Parameters%0A%20%20%20%20%20%20%20%20-----------%0A%20%20%20%20%20%20%20%20Y%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20low-dimensional%20representation%20of%20the%20data%20points.%0A%0A%20%20%20%20%20%20%20%20Returns%0A%20%20%20%20%20%20%20%20-------%0A%20%20%20%20%20%20%20%20np.ndarray%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20low-dimensional%20affinities%20matrix.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%0A%20%20%20%20%20%20%20%20n%20%3D%20len(Y)%0A%20%20%20%20%20%20%20%20q_ij%20%3D%20np.zeros(shape%3D(n%2C%20n))%0A%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(0%2C%20n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Equation%204%20Numerator%0A%20%20%20%20%20%20%20%20%20%20%20%20diff%20%3D%20Y%5Bi%5D%20-%20Y%0A%20%20%20%20%20%20%20%20%20%20%20%20norm%20%3D%20np.linalg.norm(diff%2C%20axis%3D1)%0A%20%20%20%20%20%20%20%20%20%20%20%20q_ij%5Bi%2C%20%3A%5D%20%3D%20(1%20%2B%20norm**2)%20**%20(-1)%0A%0A%20%20%20%20%20%20%20%20%23%20Set%20p%20%3D%200%20when%20j%20%3D%20i%0A%20%20%20%20%20%20%20%20np.fill_diagonal(q_ij%2C%200)%0A%0A%20%20%20%20%20%20%20%20%23%20Equation%204%0A%20%20%20%20%20%20%20%20q_ij%20%3D%20q_ij%20%2F%20q_ij.sum()%0A%0A%20%20%20%20%20%20%20%20%23%20Set%200%20values%20to%20minimum%20numpy%20value%20(%CE%B5%20approx.%20%3D%200)%0A%20%20%20%20%20%20%20%20%CE%B5%20%3D%20np.nextafter(0%2C%201)%0A%20%20%20%20%20%20%20%20q_ij%20%3D%20np.maximum(q_ij%2C%20%CE%B5)%0A%0A%20%20%20%20%20%20%20%20return%20q_ij%0A%20%20%20%20return%20(get_low_dimensional_affinities%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22Here%20we%20are%20seeking%20a%201000%20x%201000%20affinity%20matrix%20but%20now%20in%20the%20lower%20dimensional%20space%3A%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(get_low_dimensional_affinities%2C%20y0)%3A%0A%20%20%20%20q_ij%20%3D%20get_low_dimensional_affinities(y0)%0A%20%20%20%20return%20(q_ij%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(pd%2C%20q_ij)%3A%0A%20%20%20%20%23%20To%20make%20it%20look%20pretty%20in%20marimo%0A%20%20%20%20df_q_ij%20%3D%20pd.DataFrame(q_ij)%0A%20%20%20%20df_q_ij.columns%20%3D%20df_q_ij.columns.astype(%22str%22)%0A%20%20%20%20df_q_ij%0A%20%20%20%20return%20(df_q_ij%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%204.%20Compute%20Gradient%20of%20the%20Cost%20Function%0A%0A%20%20%20%20%20%20%20%20Recall%2C%20our%20cost%20function%20is%20the%20Kullback-Leibler%20divergence%20between%20joint%20probability%20distributions%20in%20the%20high%20dimensional%20space%20and%20low%20dimensional%20space%3A%0A%0A%20%20%20%20%20%20%20%20%24%24%0A%20%20%20%20%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%20%20%20%20C%3D%5Ctext%7BKL%7D(P%5C%7CQ)%3D%5Csum_i%20%5Csum_j%20p_%7Bij%7D%20%5Clog%20%5Cfrac%7Bp_%7Bij%7D%7D%7Bq_%7Bij%7D%7D%0A%20%20%20%20%20%20%20%20%5Ctag%7B5%7D%0A%20%20%20%20%20%20%20%20%5Cend%7Bequation%7D%0A%20%20%20%20%20%20%20%20%24%24%0A%0A%20%20%20%20%20%20%20%20Intuitively%2C%20we%20want%20to%20minimize%20the%20difference%20in%20the%20affinity%20matrices%20%24p_%7Bij%7D%24%20and%20%24q_%7Bij%7D%24%20thereby%20best%20preserving%20the%20%E2%80%9Cneighborhood%E2%80%9D%20structure%20of%20the%20original%20space.%20The%20optimization%20problem%20is%20solved%20using%20gradient%20descent%2C%20but%20first%20let%E2%80%99s%20look%20at%20computing%20the%20gradient%20for%20the%20cost%20function%20above.%20The%20authors%20derive%20(see%20appendix%20A%20of%20the%20paper)%20the%20gradient%20of%20the%20cost%20function%20as%20follows%3A%0A%0A%20%20%20%20%20%20%20%20%24%24%0A%20%20%20%20%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%20%20%20%20%5Cfrac%7B%5Cpartial%20C%7D%7B%5Cpartial%20y_i%7D%20%3D%204%20%5Csum_j(p_%7Bij%7D-q_%7Bij%7D)(1%2B%5C%7Cy_i-y_j%5C%7C%5E2)%5E%7B-1%7D(y_i-y_j)%0A%20%20%20%20%20%20%20%20%5Ctag%7B6%7D%0A%20%20%20%20%20%20%20%20%5Cend%7Bequation%7D%0A%20%20%20%20%20%20%20%20%24%24%0A%0A%20%20%20%20%20%20%20%20In%20python%2C%20we%20have%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20def%20get_gradient(p_ij%3A%20np.ndarray%2C%20q_ij%3A%20np.ndarray%2C%20Y%3A%20np.ndarray)%20-%3E%20np.ndarray%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20Obtain%20gradient%20of%20cost%20function%20at%20current%20point%20Y.%0A%0A%20%20%20%20%20%20%20%20Parameters%0A%20%20%20%20%20%20%20%20----------%0A%20%20%20%20%20%20%20%20p_ij%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20joint%20probability%20distribution%20matrix.%0A%20%20%20%20%20%20%20%20q_ij%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20Student's%20t-distribution%20matrix.%0A%20%20%20%20%20%20%20%20Y%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20current%20point%20in%20the%20low-dimensional%20space.%0A%0A%20%20%20%20%20%20%20%20Returns%0A%20%20%20%20%20%20%20%20------%0A%20%20%20%20%20%20%20%20np.ndarray%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20gradient%20of%20the%20cost%20function%20at%20the%20current%20point%20Y.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%0A%20%20%20%20%20%20%20%20n%20%3D%20len(p_ij)%0A%0A%20%20%20%20%20%20%20%20%23%20Compute%20gradient%0A%20%20%20%20%20%20%20%20gradient%20%3D%20np.zeros(shape%3D(n%2C%20Y.shape%5B1%5D))%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(0%2C%20n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Equation%205%0A%20%20%20%20%20%20%20%20%20%20%20%20diff%20%3D%20Y%5Bi%5D%20-%20Y%0A%20%20%20%20%20%20%20%20%20%20%20%20A%20%3D%20np.array(%5B(p_ij%5Bi%2C%20%3A%5D%20-%20q_ij%5Bi%2C%20%3A%5D)%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20B%20%3D%20np.array(%5B(1%20%2B%20np.linalg.norm(diff%2C%20axis%3D1)%20**%202)%20**%20(-1)%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20C%20%3D%20diff%0A%20%20%20%20%20%20%20%20%20%20%20%20gradient%5Bi%5D%20%3D%204%20*%20np.sum((A%20*%20B).T%20*%20C%2C%20axis%3D0)%0A%0A%20%20%20%20%20%20%20%20return%20gradient%0A%20%20%20%20return%20(get_gradient%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22Feeding%20in%20the%20relevant%20arguments%2C%20we%20obtain%20the%20gradient%20as%20follows%3A%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(get_gradient%2C%20p_ij_symmetric%2C%20q_ij%2C%20y0)%3A%0A%20%20%20%20gradient%20%3D%20get_gradient(p_ij_symmetric%2C%20q_ij%2C%20y0)%0A%20%20%20%20return%20(gradient%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(gradient%2C%20pd)%3A%0A%20%20%20%20%23%20Make%20pretty%20in%20marimo%0A%20%20%20%20df_gradient%20%3D%20pd.DataFrame(gradient)%0A%20%20%20%20df_gradient.columns%20%3D%20df_gradient.columns.astype(%22str%22)%0A%20%20%20%20df_gradient%0A%20%20%20%20return%20(df_gradient%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20Now%2C%20we%20have%20all%20the%20pieces%20in%20order%20to%20solve%20the%20optimization%20problem!%0A%0A%20%20%20%20%20%20%20%20%23%23%23%205.%20Iterate%20%26%20Optimize%20the%20Low-Dimensional%20Mapping%0A%0A%20%20%20%20%20%20%20%20In%20order%20to%20update%20our%20low-dimensional%20mapping%2C%20we%20use%20%5Bgradient%20descent%20with%20momentum%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FGradient_descent)%20as%20outlined%20by%20the%20authors%3A%0A%0A%20%20%20%20%20%20%20%20%24%24%0A%20%20%20%20%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%20%20%20%20%5Cmathcal%7BY%7D%5E%7B(t)%7D%3D%5Cmathcal%7BY%7D%5E%7B(t-1)%7D%2B%5Ceta%5Cfrac%7B%5Cpartial%20C%7D%7B%5Cpartial%20%5Cmathcal%7BY%7D%7D%20%2B%20%5Calpha(t)(%5Cmathcal%7BY%7D%5E%7B(t-1)%7D-%5Cmathcal%7BY%7D%5E%7B(t-2)%7D)%0A%20%20%20%20%20%20%20%20%5Ctag%7B7%7D%0A%20%20%20%20%20%20%20%20%5Cend%7Bequation%7D%0A%20%20%20%20%20%20%20%20%24%24%0A%0A%20%20%20%20%20%20%20%20where%20%24%5Ceta%24%20is%20our%20%5Blearning%20rate%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FLearning_rate)%20and%20%24%5Calpha(t)%24%20is%20our%20momentum%20term%20as%20a%20function%20of%20time.%20The%20learning%20rate%20controls%20the%20step%20size%20at%20each%20iteration%20and%20the%20momentum%20term%20allows%20the%20optimization%20algorithm%20to%20gain%20inertia%20in%20the%20smooth%20direction%20of%20the%20search%20space%2C%20while%20not%20being%20bogged%20down%20by%20the%20noisy%20parts%20of%20the%20gradient.%20We%20will%20set%20%24%5Ceta%3D200%24%20for%20our%20example%20and%20will%20fix%20%24%5Calpha(t)%3D0.5%24%20if%20%24t%20%3C%20250%24%20and%20%24%5Calpha(t)%3D0.8%24%20otherwise.%20We%20have%20all%20the%20components%20necessary%20above%20to%20compute%20to%20the%20update%20rule%2C%20thus%20we%20can%20now%20run%20our%20optimization%20over%20a%20set%20number%20of%20iterations%20%24T%24%20(we%20will%20set%20%24T%3D1000%24).%0A%0A%20%20%20%20%20%20%20%20Before%20we%20set%20up%20for%20iteration%20scheme%2C%20let%E2%80%99s%20first%20introduce%20the%20enhancement%20the%20authors%20refer%20to%20as%20%E2%80%9Cearly%20exaggeration%E2%80%9D.%20This%20term%20is%20a%20constant%20that%20scales%20the%20original%20matrix%20of%20affinities%20%24p_%7Bij%7D%24.%20What%20this%20does%20is%20it%20places%20more%20emphasis%20on%20modeling%20the%20very%20similar%20points%20(high%20values%20in%20%24p_%7Bij%7D%24%20from%20the%20original%20space)%20in%20the%20new%20space%20early%20on%20and%20thus%20forming%20%E2%80%9Cclusters%E2%80%9D%20of%20highly%20similar%20points.%20The%20early%20exaggeration%20is%20placed%20on%20at%20the%20beginning%20of%20the%20iteration%20scheme%20(%24T%3C250%24)%20and%20then%20turned%20off%20otherwise.%20Early%20exaggeration%20will%20be%20set%20to%204%20in%20our%20case.%20We%20will%20see%20this%20in%20action%20in%20our%20visual%20below%20following%20implementation.%0A%0A%20%20%20%20%20%20%20%20Now%2C%20putting%20all%20of%20the%20pieces%20together%20for%20the%20algorithm%2C%20we%20have%20the%20following%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20get_gradient%2C%0A%20%20%20%20get_low_dimensional_affinities%2C%0A%20%20%20%20get_original_pairwise_affinities%2C%0A%20%20%20%20get_symmetric_p_ij%2C%0A%20%20%20%20initialization%2C%0A%20%20%20%20np%2C%0A)%3A%0A%20%20%20%20def%20tsne(%0A%20%20%20%20%20%20%20%20X%3A%20np.ndarray%2C%0A%20%20%20%20%20%20%20%20perplexity%3A%20int%20%3D%2010%2C%0A%20%20%20%20%20%20%20%20T%3A%20int%20%3D%201000%2C%0A%20%20%20%20%20%20%20%20%CE%B7%3A%20int%20%3D%20200%2C%0A%20%20%20%20%20%20%20%20early_exaggeration%3A%20int%20%3D%204%2C%0A%20%20%20%20%20%20%20%20n_dimensions%3A%20int%20%3D%202%2C%0A%20%20%20%20)%20-%3E%20list%5Bnp.ndarray%2C%20np.ndarray%5D%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20t-SNE%20(t-Distributed%20Stochastic%20Neighbor%20Embedding)%20algorithm%20implementation.%0A%0A%20%20%20%20%20%20%20%20Parameters%0A%20%20%20%20%20%20%20%20----------%0A%20%20%20%20%20%20%20%20X%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20input%20data%20matrix%20of%20shape%20(n_samples%2C%20n_features).%0A%20%20%20%20%20%20%20%20perplexity%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20perplexity%20parameter.%20Default%20is%2010.%0A%20%20%20%20%20%20%20%20T%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20number%20of%20iterations%20for%20optimization.%20Default%20is%201000.%0A%20%20%20%20%20%20%20%20%CE%B7%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20learning%20rate%20for%20updating%20the%20low-dimensional%20embeddings.%20Default%20is%20200.%0A%20%20%20%20%20%20%20%20early_exaggeration%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20factor%20by%20which%20the%20pairwise%20affinities%20are%20exaggerated%20during%20the%20early%20iterations%20of%20optimization.%0A%20%20%20%20%20%20%20%20%20%20%20%20Default%20is%204.%0A%20%20%20%20%20%20%20%20n_dimensions%0A%20%20%20%20%20%20%20%20%20%20%20%20The%20number%20of%20dimensions%20of%20the%20low-dimensional%20embeddings.%0A%20%20%20%20%20%20%20%20%20%20%20%20Default%20is%202.%0A%0A%20%20%20%20%20%20%20%20Returns%0A%20%20%20%20%20%20%20%20-------%0A%20%20%20%20%20%20%20%20list%5Bnp.ndarray%2C%20np.ndarray%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20A%20list%20containing%20the%20final%20low-dimensional%20embeddings%20and%20the%20history%20of%20embeddings%20at%20each%20iteration.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20n%20%3D%20len(X)%0A%0A%20%20%20%20%20%20%20%20%23%20Get%20original%20affinities%20matrix%0A%20%20%20%20%20%20%20%20p_ij%20%3D%20get_original_pairwise_affinities(X%2C%20perplexity)%0A%20%20%20%20%20%20%20%20p_ij_symmetric%20%3D%20get_symmetric_p_ij(p_ij)%0A%0A%20%20%20%20%20%20%20%20%23%20Initialization%0A%20%20%20%20%20%20%20%20Y%20%3D%20np.zeros(shape%3D(T%2C%20n%2C%20n_dimensions))%0A%20%20%20%20%20%20%20%20Y_minus1%20%3D%20np.zeros(shape%3D(n%2C%20n_dimensions))%0A%20%20%20%20%20%20%20%20Y%5B0%5D%20%3D%20Y_minus1%0A%20%20%20%20%20%20%20%20Y1%20%3D%20initialization(X%2C%20n_dimensions)%0A%20%20%20%20%20%20%20%20Y%5B1%5D%20%3D%20np.array(Y1)%0A%0A%20%20%20%20%20%20%20%20print(%22Optimizing%20Low%20Dimensional%20Embedding....%22)%0A%20%20%20%20%20%20%20%20%23%20Optimization%0A%20%20%20%20%20%20%20%20for%20t%20in%20range(1%2C%20T%20-%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Momentum%20%26%20Early%20Exaggeration%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20t%20%3C%20250%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%CE%B1%20%3D%200.5%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20early_exaggeration%20%3D%20early_exaggeration%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%CE%B1%20%3D%200.8%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20early_exaggeration%20%3D%201%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Get%20Low%20Dimensional%20Affinities%0A%20%20%20%20%20%20%20%20%20%20%20%20q_ij%20%3D%20get_low_dimensional_affinities(Y%5Bt%5D)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Get%20Gradient%20of%20Cost%20Function%0A%20%20%20%20%20%20%20%20%20%20%20%20gradient%20%3D%20get_gradient(early_exaggeration%20*%20p_ij_symmetric%2C%20q_ij%2C%20Y%5Bt%5D)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Update%20Rule%0A%20%20%20%20%20%20%20%20%20%20%20%20Y%5Bt%20%2B%201%5D%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Y%5Bt%5D%20-%20%CE%B7%20*%20gradient%20%2B%20%CE%B1%20*%20(Y%5Bt%5D%20-%20Y%5Bt%20-%201%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20)%20%20%23%20Use%20negative%20gradient%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Compute%20current%20value%20of%20cost%20function%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20t%20%25%2050%20%3D%3D%200%20or%20t%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cost%20%3D%20np.sum(p_ij_symmetric%20*%20np.log(p_ij_symmetric%20%2F%20q_ij))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print(f%22Iteration%20%7Bt%7D%3A%20Value%20of%20Cost%20Function%20is%20%7Bcost%7D%22)%0A%0A%20%20%20%20%20%20%20%20print(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22Completed%20Low%20Dimensional%20Embedding%3A%20Final%20Value%20of%20Cost%20Function%20is%20%7Bnp.sum(p_ij_symmetric%20*%20np.log(p_ij_symmetric%20%2F%20q_ij))%7D%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20solution%20%3D%20Y%5B-1%5D%0A%0A%20%20%20%20%20%20%20%20return%20solution%2C%20Y%0A%20%20%20%20return%20(tsne%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22Now%20calling%20the%20code%3A%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(X%2C%20tsne)%3A%0A%20%20%20%20solution%2C%20Y%20%3D%20tsne(X)%0A%20%20%20%20return%20Y%2C%20solution%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(pd%2C%20solution)%3A%0A%20%20%20%20%23%20To%20make%20pretty%20for%20marimo%0A%20%20%20%20df_solution%20%3D%20pd.DataFrame(solution)%0A%20%20%20%20df_solution.columns%20%3D%20df_solution.columns.astype(%22str%22)%0A%20%20%20%20df_solution%0A%20%20%20%20return%20(df_solution%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22where%20%60solution%60%20is%20the%20final%202-D%20mapping%20and%20%60Y%60%20is%20our%20mapped%202-D%20values%20at%20each%20step%20of%20the%20iteration.%20Plotting%20the%20evolution%20of%20%60Y%60%20where%20%60Y%5B-1%5D%60%20is%20our%20final%202-D%20mapping%2C%20we%20obtain%20(note%20how%20the%20algorithm%20behaves%20with%20early%20exaggeration%20on%20and%20off)%3A%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(Y%2C%20animation%2C%20mo%2C%20np%2C%20plt%2C%20y_reduced)%3A%0A%20%20%20%20def%20tsne_evolution_fig()%3A%0A%20%20%20%20%20%20%20%20fig%2C%20ax%20%3D%20plt.subplots()%0A%20%20%20%20%20%20%20%20ax.axis(%22off%22)%0A%20%20%20%20%20%20%20%20ax.set_title(%22MNIST%20t-SNE%22)%0A%20%20%20%20%20%20%20%20scat%20%3D%20ax.scatter(Y%5B1%5D%5B%3A%2C%200%5D%2C%20Y%5B1%5D%5B%3A%2C%201%5D%2C%20c%3Dy_reduced%2C%20cmap%3D%22tab10%22)%0A%20%20%20%20%20%20%20%20plt.colorbar(scat%2C%20ax%3Dax)%0A%0A%20%20%20%20%20%20%20%20%23%20t-SNE%20Descent%20Animation%0A%20%20%20%20%20%20%20%20ys%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20prelims%20%3D%20list(range(0%2C%2050%2C%205))%0A%20%20%20%20%20%20%20%20early_range%20%3D%20list(range(50%2C%20250%2C%2010))%0A%20%20%20%20%20%20%20%20mid_range_1%20%3D%20list(range(250%2C%20300%2C%205))%0A%20%20%20%20%20%20%20%20mid_range_2%20%3D%20list(range(300%2C%20400%2C%2010))%0A%20%20%20%20%20%20%20%20end_range%20%3D%20list(range(400%2C%201000%2C%2050))%0A%0A%20%20%20%20%20%20%20%20visual_range%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20prelims%0A%20%20%20%20%20%20%20%20%20%20%20%20%2B%20early_range%0A%20%20%20%20%20%20%20%20%20%20%20%20%2B%20mid_range_1%0A%20%20%20%20%20%20%20%20%20%20%20%20%2B%20mid_range_2%0A%20%20%20%20%20%20%20%20%20%20%20%20%2B%20end_range%0A%20%20%20%20%20%20%20%20%20%20%20%20%2B%20%5B999%2C%20999%2C%20999%2C%20999%2C%20999%2C%20999%2C%20999%5D%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20for%20i%20in%20visual_range%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20ys.append(Y%5Bi%5D)%0A%0A%20%20%20%20%20%20%20%20def%20strike(text)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20result%20%3D%20%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20c%20in%20text%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20result%20%3D%20result%20%2B%20c%20%2B%20%22%5Cu0336%22%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20result%0A%0A%20%20%20%20%20%20%20%20def%20animate(iterations)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20scat.set_offsets(ys%5Biterations%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20iterations%20%3C%2031%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ax.text(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%200.05%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Early%20Exaggeration%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20horizontalalignment%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20verticalalignment%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20transform%3Dax.transAxes%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ax.text(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%200.05%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20strike(%22%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20horizontalalignment%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20verticalalignment%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20transform%3Dax.transAxes%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.set_xlim(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%201.25%20*%20np.min(ys%5Biterations%5D%5B%3A%2C%200%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%201.25%20*%20np.max(ys%5Biterations%5D%5B%3A%2C%200%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.set_ylim(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%201.25%20*%20np.min(ys%5Biterations%5D%5B%3A%2C%201%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%201.25%20*%20np.max(ys%5Biterations%5D%5B%3A%2C%201%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20rot_animation%20%3D%20animation.FuncAnimation(%0A%20%20%20%20%20%20%20%20%20%20%20%20fig%2C%20animate%2C%20frames%3Dlen(ys)%20-%201%2C%20interval%3D350%2C%20blit%3DFalse%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20rot_animation.save(%22data%2FMNIST.gif%22%2C%20dpi%3D300)%0A%0A%20%20%20%20tsne_evolution_fig()%0A%20%20%20%20mo.image(%22data%2FMNIST.gif%22%2C%20height%3D500).center()%0A%20%20%20%20return%20(tsne_evolution_fig%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20I%20recommend%20playing%20around%20with%20different%20values%20of%20the%20parameters%20(i.e.%2C%20perplexity%2C%20learning%20rate%2C%20early%20exaggeration%2C%20etc.)%20to%20see%20how%20the%20solution%20differs%20(See%20the%20original%20paper%20and%20the%20scikit-learn%20documentation%20for%20guides%20on%20using%20these%20parameters).%0A%0A%20%20%20%20%20%20%20%20%23%23%20Conclusion%0A%0A%20%20%20%20%20%20%20%20And%20there%20you%20have%20it%2C%20we%20have%20coded%20t-SNE%20from%20scratch!%20I%20hope%20you%20have%20found%20this%20exercise%20to%20be%20illuminating%20into%20the%20inner%20workings%20of%20t-SNE%20and%2C%20at%20the%20very%20minimum%2C%20satisfying.%20Note%20that%20this%20implementation%20is%20not%20intended%20to%20be%20optimized%20for%20speed%2C%20but%20rather%20for%20understanding.%20Additions%20to%20the%20t-SNE%20algorithm%20have%20been%20implemented%20to%20improve%20computational%20speed%20and%20performance%2C%20such%20as%20variants%20of%20the%20%5BBarnes-Hut%20algorithm%5D(https%3A%2F%2Flvdmaaten.github.io%2Fpublications%2Fpapers%2FJMLR_2014.pdf)%20(tree-based%20approaches)%2C%20using%20PCA%20as%20the%20initialization%20of%20the%20embedding%2C%20or%20using%20additional%20gradient%20descent%20extensions%20such%20as%20adaptive%20learning%20rates.%20The%20implementation%20in%20scikit-learn%20makes%20use%20of%20many%20of%20these%20enhancements.%0A%0A%20%20%20%20%20%20%20%20As%20always%2C%20I%20hope%20you%20have%20enjoyed%20reading%20this%20as%20much%20as%20I%20enjoyed%20writing%20it.%0A%0A%20%20%20%20%20%20%20%20%23%23%20References%0A%0A%20%20%20%20%20%20%20%20%5B1%5D%20van%20der%20Maaten%2C%20L.J.P.%3B%20Hinton%2C%20G.E.%20Visualizing%20High-Dimensional%20Data%20Using%20t-SNE.%20Journal%20of%20Machine%20Learning%20Research%209%3A2579%E2%80%932605%2C%202008.%0A%0A%20%20%20%20%20%20%20%20%5B2%5D%20LeCun%20et%20al.%20(1999)%3A%20The%20MNIST%20Dataset%20Of%20Handwritten%20Digits%20(Images)%20License%3A%20CC%20BY-SA%203.0%0A%0A%20%20%20%20%20%20%20%20%3Cdiv%20style%3D%22text-align%3A%20center%3B%20font-size%3A%2024px%3B%22%3E%E2%9D%96%E2%9D%96%E2%9D%96%3C%2Fdiv%3E%0A%0A%20%20%20%20%20%20%20%20%3Ccenter%3E%0A%20%20%20%20%20%20%20%20Access%20all%20the%20code%20via%20this%20Marimo%20Notebook%20or%20my%20%5BGitHub%20Repo%5D(https%3A%2F%2Fgithub.com%2Fjakepenzak%2Fblog-posts)%0A%0A%20%20%20%20%20%20%20%20I%20appreciate%20you%20reading%20my%20post!%20My%20posts%20primarily%20explore%20real-world%20and%20theoretical%20applications%20of%20econometric%20and%20statistical%2Fmachine%20learning%20techniques%2C%20but%20also%20whatever%20I%20am%20currently%20interested%20in%20or%20learning%20%F0%9F%98%81.%20At%20the%20end%20of%20the%20day%2C%20I%20write%20to%20learn!%20I%20hope%20to%20make%20complex%20topics%20slightly%20more%20accessible%20to%20all.%0A%20%20%20%20%20%20%20%20%3C%2Fcenter%3E%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A