সমাধান — অধ্যায় ৬.৮ · Nonlinear Dimensionality Reduction & Manifold Learning¶

অধ্যায় ফাইল: part-6-statistical-ml/06-08-nonlinear-dimensionality-reduction.md (§৭ অনুশীলনী)। চলমান dataset — seed-সূচক random_state=20260619: make_swiss_roll(n_samples=1000, noise=0.05); X shape $(1000,3)$, color = manifold-বরাবর প্রকৃত ১D অবস্থান (যা embedding-এ পুনরুদ্ধার করতে চাই)। unsupervised — পুরো data fit হয়, train/test split প্রয়োজন নেই। মূল notation: $x_i\in\mathbb R^D$ ($D=3$), embedding $y_i\in\mathbb R^d$ ($d=2$); centering matrix $H=I-\tfrac1n\mathbf 1\mathbf 1^\top$; centered kernel $\tilde K=HKH$; double-centering $B=-\tfrac12 H\Delta H$ ($\Delta_{ij}=d_{ij}^2$); geodesic দূরত্ব $d_G$; t-SNE high-D affinity $p_{ij}$, low-D affinity $q_{ij}$, খরচ $\mathrm{KL}(P\Vert Q)=\sum_{i\ne j}p_{ij}\log\frac{p_{ij}}{q_{ij}}$; trustworthiness $T$। canonical সংখ্যা — প্রতিটি method-এর trustworthiness $T$ / embedding-প্রথম-অক্ষ বনাম color-এর $\lvert\text{corr}\rvert$: PCA $0.968/0.165$ (global ব্যর্থ), Isomap $1.000/1.000$, LLE $0.996/0.998$, t-SNE $0.999/0.857$, KernelPCA(rbf) $0.898/0.228$। §ঘ-এর runnable script (seed-সূচক random_state=20260619) উপরের সংখ্যাগুলো পুনরুৎপাদন করে (sklearn-সংস্করণ/optimizer-ভেদে, বিশেষত t-SNE ও KernelPCA-তে, শেষ অঙ্কে সামান্য হেরফের সম্ভব; গল্প অপরিবর্তিত)। গাণিতিক প্রশ্নের (৯–১৩) সংখ্যা স্বয়ংসম্পূর্ণ — অধ্যায়-dataset থেকে স্বাধীন।

ক · ধারণাগত (conceptual)¶

সমাধান ১ (★)¶

(ক) manifold hypothesis। দাবি: বাস্তব উচ্চ-মাত্রিক ($D$) data পূর্ণ $\mathbb R^D$ জুড়ে এলোমেলোভাবে ছড়ানো নয়, বরং একটা অনেক-কম-মাত্রিক ($d\ll D$) মসৃণ manifold-এর উপরে বা কাছাকাছি কেন্দ্রীভূত। অর্থাৎ data-র intrinsic dimension $d$ তার ambient dimension $D$-র চেয়ে অনেক ছোট — গুরুত্বপূর্ণ তথ্য এই নিম্ন-মাত্রিক চাদরের গায়েই থাকে।

(খ) swiss roll-এ $D$ ও $d$। ambient dimension $D=3$ (প্রতিটি বিন্দু ৩D স্থানাঙ্ক $(x,y,z)$)। intrinsic dimension $d=2$ — "কাগজটা" আসলে একটা ২D চাদর (দৈর্ঘ্য ও প্রস্থ), যা ৩D-তে পেঁচানো। "intrinsic" মানে: manifold-এর উপরিতলে স্থানীয়ভাবে চলতে যত স্বাধীন স্থানাঙ্ক/দিক লাগে — এখানে চাদর বরাবর দুটো (একটা পেঁচ-বরাবর "মেলে ধরা দৈর্ঘ্য" = color, একটা প্রস্থ-বরাবর)। ৩D হলেও স্বাধীনতা মাত্র ২।

(গ) লক্ষ্য। dimensionality reduction-এর লক্ষ্য একটা map $\mathbb R^D\to\mathbb R^d$ খোঁজা যা manifold-এর প্রতিবেশ-সম্পর্ক/দূরত্ব যথাসম্ভব রক্ষা করে — অর্থাৎ পেঁচানো roll-কে $d=2$-তে এমনভাবে "মেলে ধরা" যেন কাছের বিন্দু কাছে, manifold-বরাবর ক্রম অটুট থাকে।

সমাধান ২ (★)¶

(ক) সমতলে চাপলে কী হারায়। PCA শুধু একটা সমতল (flat subspace)-এ প্রক্ষেপ করে। swiss roll পেঁচানো বলে দুটো বিন্দু ৩D-তে কাছাকাছি হলেও চাদর-বরাবর (geodesic) বহু দূরে হতে পারে (প্রতিবেশী দুই পাক)। roll-কে variance-সর্বোচ্চ সমতলে চাপলে এই পেঁচ "ভাঁজ হয়ে" মিশে যায় — দূরের পাকের বিন্দুরা একে অপরের উপর পড়ে (overlap), ফলে manifold-বরাবর global ক্রম/গঠন হারিয়ে যায়। PCA Euclidean variance দেখে, geodesic গঠন নয়।

(খ) corr $0.165$-র অর্থ। PCA-র প্রথম অক্ষ বনাম প্রকৃত manifold-অবস্থান color-এর $\lvert\text{corr}\rvert=0.165\approx0$ — কার্যত সম্পর্কহীন। অর্থাৎ PCA-র variance-সর্বোচ্চ সরলদিক manifold-বরাবর প্রকৃত ১D অবস্থানের সাথে মেলে না; roll-কে মেলে ধরতে ব্যর্থ (সরলরৈখিক অক্ষ ≠ বাঁকা manifold-দিক)।

(গ) কেন nonlinear দরকার। বাঁকা manifold-এর global গঠন ধরতে দূরত্ব/প্রতিবেশকে অরৈখিকভাবে সম্মান করা চাই (geodesic, kernel, বা neighbor-distribution) — যা সরল সমতল-projection পারে না; তাই kernel PCA, Isomap, LLE, t-SNE-র মতো nonlinear পদ্ধতি অপরিহার্য।

সমাধান ৩ (★)¶

(ক) kernel PCA কীসের eigen-decomposition; centering কেন। সাধারণ PCA covariance $C=\tfrac1n X^\top X$-এর eigen-decomposition করে। kernel PCA পরিবর্তে centered kernel matrix $\tilde K=HKH$ ($n\times n$, $K_{ij}=k(x_i,x_j)$, $H=I-\tfrac1n\mathbf 1\mathbf 1^\top$)-এর eigen-decomposition করে — কারণ feature-map $\phi$ সরাসরি না জানায় covariance বানানো যায় না, কিন্তু kernel দিয়েই eigen-গঠন বের করা যায় (kernel trick, ৬.৪)। centering আবশ্যক কারণ PCA covariance-এর জন্য feature-space-এ data মূলবিন্দু-কেন্দ্রিক ($\sum_i\phi(x_i)=0$) হওয়া চাই; $\phi$ সরাসরি না থাকায় এই centering kernel-পর্যায়ে $\tilde K=HKH$ সূত্রে করা হয়।

(খ) linear kernel। $k(x,x')=x^\top x'$ নিলে feature-map = identity ($\phi(x)=x$), তাই kernel PCA হুবহু সাধারণ (linear) PCA (৫.৯)-তে পরিণত হয় (সমাধান ১৩-এ প্রমাণ)।

(গ) RBF কেন swiss roll-এ দুর্বল। RBF kernel-pca একটা স্থির nonlinear feature-space-এ variance-সর্বোচ্চ দিক খোঁজে, কিন্তু swiss roll-এর প্রকৃত geodesic/unrolling গঠন স্পষ্টভাবে ধরে না (উপযুক্ত $\gamma$ ছাড়া roll মেলে না) — তাই canonical corr মাত্র $0.228$, যেখানে geodesic সরাসরি ব্যবহারকারী Isomap পায় $1.000$।

সমাধান ৪ (★)¶

(ক) কোথায় Euclidean ও geodesic ভিন্ন। swiss roll-এ দুই প্রতিবেশী পাকের মধ্যে Euclidean দূরত্ব ছোট (৩D-তে পাশাপাশি, "শর্টকাট"), কিন্তু geodesic বিশাল (চাদর-বরাবর হাঁটতে পুরো পাক ঘুরে যেতে হয়) — এখানেই Euclidean ভয়ানক বিভ্রান্ত করে। একই পাকের ভেতরে দুটো বিন্দুর Euclidean ও geodesic প্রায় সমান (চাদর সেখানে প্রায়-সমতল)।

(খ) geodesic কৌশল ও MDS। প্রতিটি বিন্দুর kNN দিয়ে একটা neighbor graph বানিয়ে edge-ওজন = local Euclidean দূরত্ব; তারপর graph-shortest-path (Dijkstra/Floyd–Warshall) = geodesic-আনুমান $d_G$। এই $d_G$-matrix manifold-বরাবর প্রকৃত দূরত্ব ধরে, তাই দূরত্ব-রক্ষাকারী MDS (double-centering + eigen) এতে চালালে roll সঠিকভাবে মেলে যায়। বিপরীতে কাঁচা Euclidean দূরত্ব "শর্টকাট"-এ প্রতিবেশী-পাককে কাছে দেখায়, তাই Euclidean-MDS roll ভাঁজ করে রাখে (PCA-র মতোই ব্যর্থ)।

(গ) নিখুঁত $1.000$-র অর্থ। Isomap-এ $T=1.000$ এবং $\lvert\text{corr}\rvert=1.000$ ⇒ embedding-এর প্রথম অক্ষ manifold-বরাবর প্রকৃত ১D অবস্থান color-এর সাথে প্রায়-নিখুঁত রৈখিক মিল, এবং কোনো মিথ্যা-প্রতিবেশী নেই — অর্থাৎ geodesic-MDS roll-কে সম্পূর্ণ ও সঠিকভাবে মেলে ধরেছে, local ও global দুই-ই রক্ষিত।

সমাধান ৫ (★★)¶

(ক) weight কী ধরছে। $w_{ij}$ হলো $x_i$-কে তার প্রতিবেশীদের affine/convex (উত্তল)-যোগ হিসেবে লেখার সহগ — একটা স্থানীয় barycentric স্থানাঙ্ক: প্রতিবেশ-patch-এর ভেতরে বিন্দুটি কোথায় বসে (প্রতিবেশীদের সাপেক্ষে আপেক্ষিক অবস্থান)। ছোট patch-এ manifold প্রায়-সমতল, তাই এই রৈখিক পুনর্গঠন ভালো কাজ করে।

(খ) $\sum_j w_{ij}=1$ শর্ত ও invariance। affine constraint $\sum_j w_{ij}=1$ reconstruction-কে input-এর translation-এ অপরিবর্তিত রাখে: $x_i+c-\sum_j w_{ij}(x_j+c)=x_i-\sum_j w_{ij}x_j+(1-\sum_j w_{ij})c=x_i-\sum_j w_{ij}x_j$ (যেহেতু $\sum_j w_{ij}=1$, $c$-পদ মোছে)। সাথে weight rotation-এও invariant (rotation linear, reconstruction-error norm অপরিবর্তিত) এবং scale-এ সামঞ্জস্যপূর্ণ। ফলে $w_{ij}$ কেবল প্রতিবেশীদের আপেক্ষিক geometry ধরে, পরম স্থানাঙ্ক নয় — তাই এই geometry নিম্ন-মাত্রায় হুবহু বহন করা যায় (ধাপ ii)।

(গ) কেন "local"। LLE local — প্রতিটি বিন্দুর কেবল ছোট প্রতিবেশের রৈখিক geometry ($w_{ij}$) সংরক্ষণ করে এবং এই স্থানীয় টুকরোগুলো একটা global sparse-eigen সমস্যায় জুড়ে দেয়; Isomap-এর মতো বিন্দু-জোড়ার global geodesic দূরত্ব ব্যবহার করে না। তবু swiss roll-এ local-linear patch যথেষ্ট তথ্যপূর্ণ, তাই canonical corr $0.998$ (প্রায়-নিখুঁত)।

সমাধান ৬ (★★)¶

(ক) $p_{ij},q_{ij}$ ও match। $p_{ij}$ = high-D-তে বিন্দু $i,j$ "প্রতিবেশী" হওয়ার সম্ভাবনা (Gaussian affinity, প্রতিটি বিন্দুর bandwidth perplexity দিয়ে স্কেল); $q_{ij}$ = একই জোড়ার low-D affinity (Student-$t$)। দুটোই একটা প্রতিবেশ-সম্ভাবনা বণ্টন। t-SNE চায় low-D $q_{ij}$ যেন high-D $p_{ij}$-র যত কাছাকাছি সম্ভব — অর্থাৎ high-D-র প্রতিবেশ-গঠন low-D-তে প্রতিফলিত করা; এজন্য $\mathrm{KL}(P\Vert Q)$ minimize করে।

(খ) অপ্রতিসম KL-র পক্ষপাত। $\mathrm{KL}(P\Vert Q)=\sum p_{ij}\log\frac{p_{ij}}{q_{ij}}$-এ penalty $p_{ij}$ দিয়ে ওজনিত: যেখানে $p_{ij}$ বড় (high-D-তে কাছের জোড়া) কিন্তু $q_{ij}$ ছোট (low-D-তে দূরে ফেলা), সেখানে $\log\frac{p_{ij}}{q_{ij}}$ বড় ⇒ বিশাল penalty। উল্টোদিকে $p_{ij}\approx0$ (high-D-তে দূরের জোড়া) হলে যত-ই $q_{ij}$ ভুল হোক penalty নগণ্য। তাই t-SNE সবচেয়ে যত্ন নেয় high-D-তে কাছের জোড়াকে low-D-তেও কাছে রাখতে (local সংরক্ষণে পক্ষপাতী), দূরের জোড়ার সঠিক ব্যবধানে নয়।

(গ) তাই local-strong, global-weak। এই local-পক্ষপাত বলে cluster/প্রতিবেশ-গঠন চমৎকার ধরা পড়ে (canonical $T=0.999$), কিন্তু cluster-গুলোর মধ্যেকার global দূরত্ব ও manifold-বরাবর ক্রম নির্ভরযোগ্যভাবে রক্ষিত হয় না ⇒ canonical $\lvert\text{corr}\rvert=0.857$ (Isomap-এর $1.000$-র চেয়ে কম)। তাই t-SNE-মানচিত্রে cluster-দের পারস্পরিক দূরত্ব/অবস্থান অতিরিক্ত-ব্যাখ্যা করা ভুল।

সমাধান ৭ (★★)¶

(ক) crowding problem। উচ্চ-মাত্রায় একটা বিন্দুর "মাঝারি-দূরত্বের" প্রতিবেশী অনেক থাকতে পারে (উচ্চ-মাত্রার আয়তন বড়), কিন্তু $2$D-র সীমিত জায়গায় সেগুলো সব একই মাঝারি-দূরত্বে রাখার মতো জায়গা নেই — তাই তারা কেন্দ্রের দিকে চেপে (crowd) যায়, আলাদা cluster গুলিয়ে যায়। এটাই crowding problem।

(খ) ভারী-লেজ Student-$t$ কেন দূরে ঠেলে। low-D-তে Gaussian affinity দূরত্ব বাড়লে দ্রুত (exponentially) পড়ে; কিন্তু Student-$t$ ($q_{ij}\propto(1+\lVert y_i-y_j\rVert^2)^{-1}$) ভারী-লেজ — বড় দূরত্বেও $q$ খুব ছোট হয় না (বহুপদীয়ভাবে পড়ে)। তাই একটা নির্দিষ্ট মাঝারি $p_{ij}$ match করতে low-D-তে বিন্দুদের আরও দূরে বসাতে হয় (Gaussian হলে দ্রুত-পতনের কারণে কাছে চেপে যেত একই $q$ পেতে) — মাঝারি-দূরত্বের প্রতিবেশীদের জন্য বেশি low-D জায়গা তৈরি হয়।

(গ) তাই crowding উপশম। Student-$t$ লেজ মাঝারি/দূরের বিন্দুদের low-D-তে স্বাচ্ছন্দ্যে ছড়িয়ে বসতে দেয়, ফলে আলাদা cluster-গুলো চাপাচাপি না করে স্পষ্ট ও পৃথক থাকে — crowding কমে, visualization-এ cluster পরিষ্কার (এটাই t-SNE-র উঁচু $T=0.999$-র মূল কারণ)।

সমাধান ৮ (★★)¶

(ক) PCA-র উঁচু $T$, নিচু corr একসাথে। $T=0.968$ উঁচু ⇒ PCA মোটামুটি local প্রতিবেশ ঠিক রাখে (low-D-তে যাদের কাছের দেখাচ্ছে তারা high-D-তেও অনেকাংশে কাছের ছিল — কম মিথ্যা-প্রতিবেশী)। কিন্তু $\lvert\text{corr}\rvert=0.165\approx0$ ⇒ global manifold-ক্রম পুনরুদ্ধারে ব্যর্থ। দুই মিলে: PCA ছোট-পরিসরে (local) মোটামুটি ঠিক, কিন্তু বড়-পরিসরে roll ভাঁজ-করে দূরের অংশ মিশিয়ে ফেলেছে (global ভুল)।

(খ) কেন শুধু $T$ বিপজ্জনক। trustworthiness কেবল স্থানীয় প্রতিবেশ-সংরক্ষণ মাপে, global geometry নয়। তাই roll-কে চ্যাপ্টা করে দূরের পাক overlap করিয়েও উঁচু $T$ পাওয়া যায় — প্রতিটি ছোট patch-এ প্রতিবেশ ঠিক, কিন্তু patch-গুলোর পারস্পরিক বিন্যাস সম্পূর্ণ ভুল। তাই একটা পদ্ধতি high $T$ পেয়েও manifold-কে "ভুল" মেলে ধরতে পারে; $T$-র পাশে একটা global মাপ (এখানে manifold-অবস্থানের সাথে corr) দেখা অপরিহার্য।

(গ) Isomap-এ দুই-ই উঁচু কেন শক্তিশালী। Isomap-এ $T=1.000$ এবং corr $=1.000$ — local প্রতিবেশ ও global ১D ক্রম দুই-ই রক্ষিত। এটাই সত্যিকারের সঠিক unrolling-এর প্রমাণ: শুধু-local-ঠিক (PCA-র মতো) নয়, বরং বড়-পরিসরেও manifold-বরাবর ক্রম পুনরুদ্ধার। তাই দুই-পরিমাপ একসাথে উঁচু হওয়া একক $T$-র চেয়ে অনেক বিশ্বাসযোগ্য সাক্ষ্য।

খ · গণনামূলক (computational)¶

সমাধান ৯ (★★) — MDS double-centering¶

$\Delta=\begin{pmatrix}0&1&4\\1&0&1\\4&1&0\end{pmatrix}$ (তিন বিন্দু $0,1,2$-তে, squared-দূরত্ব)।

(ক) সারি/কলাম/grand গড়। - সারি-গড়: সারি$1=(0+1+4)/3=5/3\approx1.667$; সারি$2=(1+0+1)/3=2/3\approx0.667$; সারি$3=(4+1+0)/3=5/3$। - $\Delta$ symmetric, তাই কলাম-গড়ও $\bar\Delta_{\cdot j}=(5/3,\,2/3,\,5/3)$। - grand-গড়: $\bar\Delta_{\cdot\cdot}=\frac{1}{9}\sum_{ij}\Delta_{ij}=\frac{0+1+4+1+0+1+4+1+0}{9}=\frac{12}{9}=\frac{4}{3}\approx1.333$।

(খ) $B=-\tfrac12 H\Delta H$, উপাদান-সূত্র $B_{ij}=-\tfrac12(\Delta_{ij}-\bar\Delta_{i\cdot}-\bar\Delta_{\cdot j}+\bar\Delta_{\cdot\cdot})$। $$ B_{11}=-\tfrac12\big(0-\tfrac53-\tfrac53+\tfrac43\big)=-\tfrac12\big(-\tfrac{6}{3}\big)=-\tfrac12(-2)=1, $$ $$ B_{12}=-\tfrac12\big(1-\tfrac53-\tfrac23+\tfrac43\big)=-\tfrac12\big(1-\tfrac{3}{3}\big)=-\tfrac12(1-1)=0, $$ $$ B_{13}=-\tfrac12\big(4-\tfrac53-\tfrac53+\tfrac43\big)=-\tfrac12\big(4-2\big)=-1, $$ $$ B_{22}=-\tfrac12\big(0-\tfrac23-\tfrac23+\tfrac43\big)=-\tfrac12(0)=0, $$ $$ B_{23}=-\tfrac12\big(1-\tfrac23-\tfrac53+\tfrac43\big)=-\tfrac12\big(1-1\big)=0,\qquad B_{33}=B_{11}=1. $$ তাই $$ B=\begin{pmatrix}1&0&-1\0&0&0\-1&0&1\end{pmatrix}. $$

(গ) যাচাই। - symmetric: $B=B^\top$ ✓। - সারি-যোগফল $0$: সারি$1=1+0-1=0$, সারি$2=0$, সারি$3=-1+0+1=0$ ✓ (double-centering-এর স্বাক্ষর — $B\mathbf 1=0$)। - $B_{ii}=\lVert x_i-\bar x\rVert^2$: বিন্দু $0,1,2$, centroid $\bar x=1$; squared-দূরত্ব $(0-1)^2,(1-1)^2,(2-1)^2=1,0,1$ = কর্ণ $(1,0,1)$ ✓।

অর্থাৎ $B$ ঠিক inner-product (centered Gram) matrix। এর শীর্ষ-eigenvector: eigenvalue $2$ (eigenvector $\propto(1,0,-1)$), যা স্কেল করে ১D স্থানাঙ্ক $(-1,0,1)$ ফেরায় — মূল বিন্দু $0,1,2$-র centered রূপ। এটাই MDS-এর মূল কাজ: squared-দূরত্ব → double-center → eigen → স্থানাঙ্ক পুনরুদ্ধার।

সমাধান ১০ (★★) — Isomap geodesic / shortest path¶

edge: $A\!-\!B{:}1,\ B\!-\!C{:}1,\ C\!-\!D{:}1,\ D\!-\!E{:}1,\ A\!-\!E{:}1.2$।

(ক) $d_G(A,E)$ — দুই পথ তুলনা। - পথ $A\!-\!B\!-\!C\!-\!D\!-\!E=1+1+1+1=4$ (চাদর-বরাবর, প্রকৃত geodesic)। - সরাসরি edge $A\!-\!E=1.2$ ("শর্টকাট")। - graph-shortest-path $=\min(4,\,1.2)=\mathbf{1.2}$।

কিন্তু লক্ষণীয়: এই $1.2$ হলো graph-shortest-path যদি $A\!-\!E$ edge রাখা হয় — যা এখানে ভুল geodesic। প্রকৃত manifold-geodesic $=4$; $A\!-\!E$ একটা মিথ্যা শর্টকাট-edge (নিচে খ/গ)। তাই Isomap সফল হতে হলে kNN graph-এ $A\!-\!E$ edge থাকা উচিত নয় (যথাযথ ছোট $k$-তে নিকটতম-প্রতিবেশী হিসেবে এটা বাদ পড়বে), তখন $d_G(A,E)=4$ সঠিকভাবে পাওয়া যাবে।

(খ) swiss roll-এর প্রতিবেশী-পাক প্রতিচ্ছবি। swiss roll-এ পাশাপাশি দুই পাক ৩D Euclidean-এ কাছে ($A,E$-র $1.2$-র মতো) কিন্তু চাদর-বরাবর geodesic বহু দূর ($A,E$-র $4$-র মতো) — হুবহু একই পরিস্থিতি। kNN graph-এ এমন একটা শর্টকাট-edge ভুলভাবে দুই দূর-পাককে সংযুক্ত করলে geodesic ছোট হয়ে যায়, manifold "মুড়ে" যায়। এটাই Euclidean-বনাম-geodesic পার্থক্যের মূল শিক্ষা।

(গ) ভুল edge রাখলে বিকৃতি। যদি Isomap ভুল করে $A\!-\!E$ শর্টকাট রাখে, $d_G(A,E)=1.2$ হয়ে যায় ⇒ MDS embedding-এ পথের দুই দূর-প্রান্ত $A,E$ কাছে এসে পড়ে, roll "ছিঁড়ে/মুড়ে" বিকৃত হয় (দুই প্রান্ত মিলে গিয়ে গঠন নষ্ট)। তাই Isomap-এ $k$ যথাযথ ছোট রাখা জরুরি — যথেষ্ট বড় যেন graph সংযুক্ত থাকে, কিন্তু এত বড় নয় যেন প্রতিবেশী-পাকে শর্টকাট-edge ঢোকে।

সমাধান ১১ (★★) — t-SNE low-D affinity¶

$y_1=(0,0),\ y_2=(1,0),\ y_3=(3,0)$; $w_{ij}=(1+\lVert y_i-y_j\rVert^2)^{-1}$।

(ক) squared-দূরত্ব ও $w_{ij}$। $$ \lVert y_1-y_2\rVert^2=1,\quad \lVert y_1-y_3\rVert^2=9,\quad \lVert y_2-y_3\rVert^2=4. $$ $$ w_{12}=\frac{1}{1+1}=0.5,\qquad w_{13}=\frac{1}{1+9}=0.1,\qquad w_{23}=\frac{1}{1+4}=0.2. $$ (চাইলে normalize: $\sum=0.5+0.1+0.2=0.8$ (একপাশের জোড়া), দ্বিমুখী গুনে $q_{12}=0.5/1.6=0.3125$, ইত্যাদি — তুলনার জন্য unnormalized $w$-ই যথেষ্ট।)

(খ) Student-$t$ বনাম Gaussian, জোড়া $(1,3)$। - Student-$t$: $w_{13}=0.1$। - Gaussian: $\exp(-\lVert y_1-y_3\rVert^2)=\exp(-9)\approx0.0001234$।

অনুপাত $0.1/0.0001234\approx810$ — Student-$t$ এই দূরের জোড়াকে প্রায় $800\times$ বেশি "ওজন" দেয়। ভারী-লেজই এর কারণ।

(গ) তাই crowding-উপশম। ভারী-লেজ বলে দূরত্ব বাড়লেও $w$ ধীরে (বহুপদীয়ভাবে) পড়ে — দূরের/মাঝারি বিন্দু low-D-তে সম্পূর্ণ "শূন্য" হয়ে মুছে যায় না (Gaussian-এ $\exp(-9)$ কার্যত শূন্য)। ফলে মাঝারি-দূরত্বের প্রতিবেশীদের জন্য low-D-তে জায়গা থাকে, তারা চাপাচাপি না করে আলাদা বসে — crowding কমে।

গ · প্রমাণভিত্তিক (proof-based)¶

সমাধান ১২ (★★★) — double-centering প্রমাণ¶

centered $\{z_i\}$ ($\sum_i z_i=0$), $\Delta_{ij}=\lVert z_i-z_j\rVert^2$, লক্ষ্য $B_{ij}=z_i^\top z_j$।

(ক) $\Delta_{ij}$ বিস্তার। $$ \Delta_{ij}=\lVert z_i-z_j\rVert^2=(z_i-z_j)^\top(z_i-z_j)=\lVert z_i\rVert^2-2z_i^\top z_j+\lVert z_j\rVert^2. $$

(খ) সারি-গড় ও grand-গড় (cross-term মোছে)। $s:=\tfrac1n\sum_l\lVert z_l\rVert^2$ লিখি। $$ \bar\Delta_{i\cdot}=\tfrac1n\sum_j\Delta_{ij}=\tfrac1n\sum_j\big(\lVert z_i\rVert^2+\lVert z_j\rVert^2-2z_i^\top z_j\big)=\lVert z_i\rVert^2+s-\tfrac2n z_i^\top\underbrace{\sum_j z_j}{=0}=\lVert z_i\rVert^2+s. $$ শেষ পদ শূন্য কারণ $\sum_j z_j=0$ (data centered) — এখানেই centering গুরুত্বপূর্ণ, এটাই cross-term মুছে দেয়। symmetry-তে কলাম-গড় $\bar\Delta_{\cdot j}=\lVert z_j\rVert^2+s$। grand-গড়: $$ \bar\Delta=\tfrac1n\sum_i(\lVert z_i\rVert^2+s)=s+s=2s. $$}=\tfrac1n\sum_i\bar\Delta_{i\cdot

(গ) double-centered রাশি বসিয়ে। $$ \Delta_{ij}-\bar\Delta_{i\cdot}-\bar\Delta_{\cdot j}+\bar\Delta_{\cdot\cdot} =\big(\lVert z_i\rVert^2+\lVert z_j\rVert^2-2z_i^\top z_j\big)-\big(\lVert z_i\rVert^2+s\big)-\big(\lVert z_j\rVert^2+s\big)+2s. $$ $\lVert z_i\rVert^2,\ \lVert z_j\rVert^2$ এবং $s$-পদগুলো পুরো বাতিল হয়ে অবশিষ্ট থাকে $-2z_i^\top z_j$। তাই $$ -\tfrac12\big(\Delta_{ij}-\bar\Delta_{i\cdot}-\bar\Delta_{\cdot j}+\bar\Delta_{\cdot\cdot}\big)=-\tfrac12(-2z_i^\top z_j)=z_i^\top z_j=B_{ij}.\qquad\blacksquare $$ matrix-রূপে $B=-\tfrac12 H\Delta H$ ($H=I-\tfrac1n\mathbf 1\mathbf 1^\top$, ঠিক সারি+কলাম গড় বাদ দেওয়ার অপারেটর)। অর্থাৎ double-centering শুধু squared-দূরত্ব থেকে centered inner-product (Gram) পুনরুদ্ধার করে; এর eigen-decomposition $B=V\Lambda V^\top$ থেকে $Z=V\Lambda^{1/2}$ মূল (centered) স্থানাঙ্ক দেয় — এটাই classical MDS।

সমাধান ১৩ (★★★) — kernel PCA = PCA (linear kernel)¶

centered data ($\sum_i x_i=0$, $X\in\mathbb R^{n\times D}$ সারি = বিন্দু, তাই $HX=X$)। linear kernel $k(x,x')=x^\top x'$।

(ক) $\tilde K=XX^\top$। linear kernel-এ $K_{ij}=x_i^\top x_j\Rightarrow K=XX^\top$ ($n\times n$ Gram)। centered বলে $HX=X$ এবং $X^\top H=(HX)^\top=X^\top$, তাই $$ \tilde K=HKH=H(XX^\top)H=(HX)(HX)^\top=XX^\top=K. $$ (data আগে থেকে centered বলে kernel-centering কিছু বদলায় না।)

(খ) Gram ও covariance-এর eigen একই। covariance $C=\tfrac1n X^\top X$ ($D\times D$), Gram $G=XX^\top$ ($n\times n$)। ধরুন $X^\top X v=\lambda v$ (অর্থাৎ $C$-র eigenvector $v$, eigenvalue $\lambda/n$)। দুই পাশে বাঁ থেকে $X$ গুণ: $$ X(X^\top X)v=\lambda Xv\;\Longrightarrow\;(XX^\top)(Xv)=\lambda(Xv). $$ তাই $u:=Xv$ হলো Gram $G=XX^\top$-র eigenvector, eigenvalue অভিন্ন $\lambda$ (অশূন্য $\lambda$-র জন্য $u\ne0$, কারণ $\lVert u\rVert^2=v^\top X^\top X v=\lambda\lVert v\rVert^2>0$)। অর্থাৎ $X^\top X$ ও $XX^\top$-র অশূন্য eigenvalue হুবহু এক, eigenvector $X$-গুণনে সম্পর্কিত।

(গ) উপসংহার। kernel PCA-র projection আসে Gram $\tilde K=XX^\top$-র শীর্ষ-eigenvector থেকে, আর সাধারণ PCA-র projection আসে covariance $C\propto X^\top X$-র শীর্ষ-eigenvector থেকে — (খ) অনুযায়ী এরা একই eigenvalue ও সম্পর্কিত eigenvector ভাগ করে, তাই একই $d$-মাত্রিক principal subspace ও একই projection দেয়। সুতরাং linear-kernel PCA $\equiv$ ৫.৯-এর PCA — kernel PCA হলো PCA-র অরৈখিক সাধারণীকরণ যার linear-kernel বিশেষক্ষেত্র সাধারণ PCA। nonlinear kernel-এ $\phi$ অরৈখিক বলে তখন PCA একটা বাঁকা feature-space-এ ঘটে (যা swiss roll-এর মতো অরৈখিক গঠন আংশিক ধরতে পারে)।

ঘ · কোডিং (Python)¶

সমাধান ১৪ (★★★) — PCA বনাম Isomap বনাম t-SNE (+KernelPCA, LLE), trustworthiness ও corr¶

# 06-08 — Nonlinear dimensionality reduction on the swiss roll:
# PCA vs Isomap vs LLE vs t-SNE vs KernelPCA(rbf), with trustworthiness + |corr| to true manifold coord.
# seed-সূচক random_state=20260619 — make_swiss_roll(n=1000, noise=0.05); color = true 1D position.
import numpy as np
from sklearn.datasets import make_swiss_roll
from sklearn.decomposition import PCA, KernelPCA
from sklearn.manifold import Isomap, LocallyLinearEmbedding, TSNE, trustworthiness
from scipy.stats import pearsonr

SEED = 20260619

# ----- canonical dataset -----
X, color = make_swiss_roll(n_samples=1000, noise=0.05, random_state=SEED)
# X: (1000, 3) ambient;  color: (1000,) প্রকৃত manifold-বরাবর ১D অবস্থান

def evaluate(name, Y):
    """trustworthiness (n_neighbors=10) ও embedding প্রথম-অক্ষ বনাম color-এর |corr|."""
    T = trustworthiness(X, Y, n_neighbors=10)
    c = abs(pearsonr(Y[:, 0], color)[0])
    print(f"{name:14s}: trustworthiness = {T:.3f}   |corr| = {c:.3f}")
    return T, c

results = {}

# ----- 1. PCA (linear) -----
Y = PCA(n_components=2, random_state=SEED).fit_transform(X)
results["PCA"] = evaluate("PCA", Y)               # canonical 0.968 / 0.165 (fails)

# ----- 2. Isomap (geodesic MDS) -----
Y = Isomap(n_neighbors=10, n_components=2).fit_transform(X)
results["Isomap"] = evaluate("Isomap", Y)         # canonical 1.000 / 1.000

# ----- 3. LLE (local linear) -----
Y = LocallyLinearEmbedding(n_neighbors=10, n_components=2,
                           random_state=SEED).fit_transform(X)
results["LLE"] = evaluate("LLE", Y)               # canonical 0.996 / 0.998

# ----- 4. t-SNE (neighbor-distribution KL) -----
Y = TSNE(n_components=2, random_state=SEED).fit_transform(X)
results["t-SNE"] = evaluate("t-SNE", Y)           # canonical 0.999 / 0.857

# ----- 5. KernelPCA (rbf) -----
Y = KernelPCA(n_components=2, kernel="rbf").fit_transform(X)
results["KernelPCA"] = evaluate("KernelPCA", Y)   # canonical 0.898 / 0.228

# ----- সিদ্ধান্ত: কোন method-এর min(T, |corr|) সর্বোচ্চ (local ও global দুই-ই ভালো) -----
best = max(results, key=lambda k: min(results[k]))
print(f"\n=> উভয় T ও |corr|-এ সেরা: {best} "
      f"(T={results[best][0]:.3f}, |corr|={results[best][1]:.3f})")

প্রত্যাশিত আউটপুট (canonical):

PCA           : trustworthiness = 0.968   |corr| = 0.165
Isomap        : trustworthiness = 1.000   |corr| = 1.000
LLE           : trustworthiness = 0.996   |corr| = 0.998
t-SNE         : trustworthiness = 0.999   |corr| = 0.857
KernelPCA     : trustworthiness = 0.898   |corr| = 0.228

=> উভয় T ও |corr|-এ সেরা: Isomap (T=1.000, |corr|=1.000)

পাঠ। 1. PCA fails (global). $T=0.968$ উঁচু (local মোটামুটি), কিন্তু $\lvert\text{corr}\rvert=0.165\approx0$ — সরলরৈখিক projection swiss roll-কে চ্যাপ্টা করে দূরের পাক overlap করায়, manifold-বরাবর global ক্রম হারায়। উঁচু $T$ একাই বিভ্রান্তিকর — global মাপ (corr) ফাঁস করে দেয়। 2. Isomap perfect. $T=1.000$, $\lvert\text{corr}\rvert=1.000$ — geodesic (kNN-graph shortest path) + MDS roll-কে নিখুঁত মেলে ধরে; local ও global দুই-ই রক্ষিত। এই manifold-এর সেরা। 3. LLE প্রায়-perfect. $T=0.996$, $\lvert\text{corr}\rvert=0.998$ — শুধু local-linear geometry সংরক্ষণ করেও swiss roll-এ চমৎকার (global geodesic ছাড়াই)। 4. t-SNE: local-strong, global-weak. $T=0.999$ (সর্বোচ্চ local — cluster/প্রতিবেশ অনবদ্য), কিন্তু $\lvert\text{corr}\rvert=0.857$ (Isomap-এর চেয়ে কম) — অপ্রতিসম KL কাছের জোড়ায় পক্ষপাতী, তাই global ক্রম আংশিক। visualization-এ দারুণ, কিন্তু cluster-দূরত্ব/অক্ষ-অর্থ অতিরিক্ত-ব্যাখ্যা করা ভুল। 5. KernelPCA(rbf) দুর্বল. $T=0.898$, $\lvert\text{corr}\rvert=0.228$ — RBF feature-space-এর variance swiss roll-এর geodesic/unrolling গঠন ধরে না (linear kernel হলে এটা হুবহু PCA হতো — §গ প্রমাণ)।

মূল শিক্ষা: একটা মাত্র সংখ্যায় (যেমন $T$) আস্থা না রেখে local (trustworthiness) ও global (manifold-অবস্থানের সাথে corr) দুই-ই যাচাই করা — তবেই Isomap-এর সত্যিকার সঠিক unrolling বনাম PCA-র শুধু-local-ঠিক ব্যর্থতা স্পষ্ট হয়।

(দ্রষ্টব্য: sklearn-সংস্করণ/optimizer-ভেদে, বিশেষত t-SNE ও KernelPCA*-তে, শেষ অঙ্কে সামান্য হেরফের সম্ভব; কিন্তু গল্প — PCA-র low corr ($\approx0.165$) বনাম Isomap/LLE-র high corr ($\approx1.0$), এবং t-SNE-র উঁচু $T$ কিন্তু মাঝারি corr — অপরিবর্তি