পাঠ ০৫ · ৪০-এর মধ্যে · মডিউল ১

Home / AI Courses / ডিপ লার্নিং / Universal approximation

Universal Approximation Theorem

Why one hidden layer is theoretically enough

৬ মিনিট পড়া মাঝারি · Intermediate গণিত-ভারী

এই পাঠে যা শিখবেন

UAT-এর সঠিক formal statement
Geometric intuition — কেন stack of "step bumps" যেকোনো function বানাতে পারে
Theorem-এর সীমাবদ্ধতা — কেন এটি practical guarantee না
Modern deep network-এ UAT-এর তাৎপর্য

১ · Theorem-এর Statement

Cybenko (১৯৮৯): ধরা যাক $\sigma$ একটি sigmoidal function (continuous, $-\infty$-এ $0$, $+\infty$-এ $1$)। যেকোনো continuous function $f: [0,1]^n \to \mathbb{R}$ এবং $\epsilon > 0$-এর জন্য — এমন একটি single hidden layer network বিদ্যমান:

$$F(\mathbf{x}) = \sum_{i=1}^{N} \alpha_i \sigma(\mathbf{w}_i^T \mathbf{x} + b_i)$$

যা $|F(\mathbf{x}) - f(\mathbf{x})| < \epsilon$ — সব $\mathbf{x} \in [0,1]^n$-এর জন্য।

সরল ভাষায়

যত complex continuous function-ই হোক — sigmoid neuron যথেষ্ট পরিমাণ নিয়ে — তা arbitrary precision-এ approximate করা যায়।

Hornik (১৯৯১)-এর extension: শুধু sigmoid নয় — যেকোনো non-polynomial continuous activation কাজ করে। ReLU-ও।

২ · Geometric Intuition — Step bump

একটি sigmoid neuron — soft step। দু'টি sigmoid বিয়োগ করলে — একটি "bump" বানানো যায়। অনেক bump একসাথে — যেকোনো curve।

একটি bump construction:

$$\text{bump}(x) = \sigma(s(x - a)) - \sigma(s(x - b))$$

যেখানে $s$ বড় (sharp transition) ও $a < b$। এই bump $[a, b]$ interval-এ ~১, বাইরে ~০।

যেকোনো function approximation:

x-axis-কে অনেক ছোট interval-এ ভাগ করুন।
প্রতিটি interval-এ — function-এর height অনুসারে একটি bump।
যত interval, তত accurate approximation।

Universal approximation-এর intuition: যেকোনো function-কে অনেক ছোট "bump" বা step দিয়ে approximate। যত neuron, তত precision।

৩ · Proof Sketch (গাণিতিক স্কেচ)

Cybenko-র মূল proof Hahn-Banach theorem ও Riesz representation-এর উপর। আমরা সরল idea দেখি:

একটি sigmoid neuron — soft step বানায়: $\sigma(s(x - a))$, যেখানে $s$ বড়, একটি sharp step at $x = a$।
দু'টি step বিয়োগ — bump: $\sigma(s(x - a)) - \sigma(s(x - b))$ — interval $[a,b]$-এ ১।
অনেক bump-এর যোগ — staircase: $\sum_i h_i \cdot \text{bump}_i(x)$।
Staircase function — যেকোনো continuous function-কে approximate: Riemann integral-এর মতো — যত bin ছোট, তত accurate।
Multi-dimensional extension: tensor product দিয়ে।

৪ · Theorem-এর সীমাবদ্ধতা

"Existence" only: network-এর existence প্রমাণিত — কীভাবে train করবেন তা বলে না।
Width exponential হতে পারে: "যথেষ্ট neuron" — অনেক ক্ষেত্রে $O(2^n)$ — গণনাগতভাবে অসম্ভব।
Generalization-এর কোনো guarantee নাই: training data-তে fit, test data-তে?
Optimization-এর কোনো guarantee নাই: SGD/Adam সেই network খুঁজে পাবে কিনা — separate question।
Continuous function only: discontinuous (যেমন XOR-এর exact step) — limit-এ approximation।

UAT — মন্ত্রের মতো অপব্যবহার হয়। "Neural network যেকোনো function শেখে" — partially true, কিন্তু অনেক caveat-সহ। "Existence" ≠ "trainable" ≠ "efficient"।

৫ · Modern Extension

Depth UAT (২০১৭-পরে):

Lu et al. ২০১৭ — width-bounded UAT। ReLU network-এ width $\geq n+1$ যথেষ্ট, কিন্তু depth dependent।
Montufar et al. ২০১৪ — deep ReLU networks-এর "linear region" exponentially বেশি depth-এ।
Gain — sample efficiency, parameter efficiency।

Bengio's hierarchy argument:

কিছু function $f$-এর জন্য — shallow approximation-এ $O(2^n)$ neuron লাগে, deep-এ $O(n)$।
"Exponential separation" — depth fundamentally efficient কিছু problem-এ।

৬ · কোডে — UAT-এর demonstration

একটি sin curve fit করি — single hidden layer MLP দিয়ে।

Python · PyTorch

import torch
import torch.nn as nn

# Target: f(x) = sin(2πx)
x = torch.linspace(0, 1, 100).unsqueeze(1)
y = torch.sin(2 * torch.pi * x)

# Single hidden layer MLP
def make_model(hidden):
    return nn.Sequential(
        nn.Linear(1, hidden),
        nn.Tanh(),
        nn.Linear(hidden, 1)
    )

for h in [2, 8, 32]:
    model = make_model(h)
    optim = torch.optim.Adam(model.parameters(), lr=0.01)
    for epoch in range(2000):
        pred = model(x)
        loss = ((pred - y) ** 2).mean()
        optim.zero_grad()
        loss.backward()
        optim.step()
    print(f"hidden={h:2d}: final MSE = {loss.item():.6f}")

২ neuron-এ approximation মোটামুটি, ৮-এ ভাল, ৩২-এ প্রায় perfect। UAT বাস্তবে দেখা যায় — যত capacity, তত accuracy।

৭ · UAT-এর তাৎপর্য

Theoretical foundation: DL-এর "কেন কাজ করে" প্রশ্নের আংশিক উত্তর।
Architecture choice freedom: যেকোনো sufficient architecture work করে — design-এ flexibility।
Limitation awareness: existence ≠ practicality। Engineering সমস্যা theory-র চেয়ে বড়।
Deep learning-এর justification: "depth" UAT-এর efficient version।

UAT — beautiful theorem, কিন্তু practitioner-দের জন্য সর্তকতা। "আমার model UAT-এর কারণে যেকোনো কিছু শিখবে" — naive ভাবনা। Practical DL-এ data, optimization, generalization — সবই matter।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ UAT যদি বলে এক hidden layer-ই যথেষ্ট — তাহলে DL-এর "deep" শব্দ কেন? Depth বনাম width-এর গাণিতিক পার্থক্য কী?

এই প্রশ্নের গভীর উত্তর — DL theory-র কেন্দ্রে।

UAT-এর "যথেষ্ট" — কিন্তু কতটা?

UAT existence proof — neuron সংখ্যা bound দেয় না।
কিছু simple function-এ — $O(n)$ neuron।
কিছু complex function-এ — $O(2^n)$ — exponential blow-up।
Practical-এ infeasible।

Depth-এর exponential efficiency:

Telgarsky ২০১৬: এমন function $f$ আছে যা depth-$d$ network-এ $O(d)$ neuron-এ approximate, কিন্তু shallow network-এ $\Omega(2^d)$ neuron লাগে।
Eldan & Shamir ২০১৬: ৩-layer ও ২-layer-এর মধ্যে exponential gap।
Implication: depth = compositional complexity-র এক "currency"।

Hierarchical structure:

বাস্তব ডেটার natural hierarchy — image-এ pixel→edge→shape→object।
Shallow network — সব hierarchy একসাথে শিখতে চাপের।
Deep network — প্রতিটি স্তর একটি abstraction level।
Compositional learning — efficient।

Empirical evidence:

ImageNet-এ — VGG-19 (১৯ স্তর) > VGG-11 > AlexNet (৮ স্তর)।
NLP-এ — BERT-large (২৪ স্তর) > BERT-base (১২ স্তর)।
LLM-এ — GPT-3 (৯৬) > GPT-2 (৪৮) — capability scaling।

Depth-এর সীমা:

Vanishing gradient (পূর্বে আলোচিত)।
Compute & memory cost।
Overfitting risk small data-তে।

Width-এর সীমা:

Parameter explosion।
Memory bottleneck (especially for FC)।
Less hierarchical learning।

Sweet spot:

Modern transformer — moderate depth (২৪-৯৬), large width (৪০৯৬-১৬৩৮৪)।
CNN — moderate width, larger depth (ResNet 152)।
Domain-specific tradeoff।

মূল উপলব্ধি: UAT — possibility theorem। DL = efficiency theory। দু'টোই important — কিন্তু DL-এর "deep" শব্দটা empirical reality, theoretical guarantee নয়।

প্র ০২ "Continuous function" — UAT-এর শর্ত। কিন্তু বাস্তব ডেটায় (যেমন বিড়াল-কুকুর classification) discrete decision। UAT কীভাবে তবু কাজ করে?

UAT-এর nuance — যা অনেক tutorial skip করে।

Theorem-এর সঠিক statement:

$f$ continuous function on compact set।
$|F(\mathbf{x}) - f(\mathbf{x})| < \epsilon$ — uniform approximation।
Discrete decisions theorem-এর scope বাইরে।

Classification-এর case:

Output continuous — softmax probability (০ থেকে ১)।
Decision boundary "soft" — argmax-এ discrete হয়।
Network যা শেখে — continuous probability function।

Boundary issue:

Decision boundary-তে — function discontinuity attempt করে।
Approximation কখনো perfect না — ছোট error remains।
Training-এ — boundary-তে high gradient, careful regularization।

Discontinuous function-এর UAT extension:

Almost-everywhere continuous functions — approximation possible।
$L^p$-norm-এ approximation (instead of uniform)।
Discontinuity-গুলো arbitrary close-এ approximate, exactly নয়।

Practical implications:

Hard boundary — adversarial example easy। Network confidence-এ unstable।
Soft probability — label smoothing, calibration helpful।
Noise injection — boundary smoother, robust।

Real-world data:

"Bilai vs. Kukur" — image space-এ ambiguous example প্রায় নেই।
Manifold hypothesis — real images low-D manifold-এ। Boundary far from data।
Function "effectively continuous" data-এ।

Edge cases:

Adversarial example — manifold-এর বাইরে। Network-এর continuous extension misbehaves।
OOD detection — যখন test data train distribution-এর বাইরে।
Calibration — confidence-এর meaningfulness।

মূল উপলব্ধি: UAT-এর "continuous" requirement আসলে quite permissive — practical ML data সাধারণত মেনে চলে। কিন্তু boundary-তে ও OOD-তে — network-এর behavior carefully test করতে হয়।

প্র ০৩ UAT existence-এর কথা বলে — but optimization (SGD) সেই network-এ কীভাবে পৌঁছায়, এটি separate প্রশ্ন। SGD-র global optimum কি UAT-এর network খুঁজে পায়?

DL theory-র সবচেয়ে fundamental open problem। উত্তর — partially।

UAT vs Optimization — disconnect:

UAT — function space-এ existence।
SGD — parameter space-এ search।
দু'টো পৃথক space — convergence guarantee আলাদা।

Loss landscape — DL-এর mystery:

Non-convex — অনেক local minimum।
Saddle point — high dimension-এ অসংখ্য।
Theoretical worry — SGD bad local minimum-এ stuck হবে।

Empirical observation (২০১৪-পরে):

SGD প্রায় সবসময় good local minimum পায়।
Different initialization-এ পৌঁছানো local minima — comparable performance।
Saddle point-গুলো-ই বড় চ্যালেঞ্জ, local minimum না।

Theoretical progress:

Choromanska et al. ২০১৫: spin-glass model — most local minima similar quality।
NTK theory (Jacot ২০১৮): infinitely wide network — gradient flow analytically tractable।
Mean-field theory: wide network-এর SGD behavior PDE-এ describe।
Lottery Ticket Hypothesis (Frankle ২০১৯): sparse subnetwork already exists — SGD শুধু আবিষ্কার করে।

Implicit regularization:

SGD-এর noise — generalize-prone solution-এ pull করে।
Flat minima > sharp minima (better generalization)।
Adam, AdamW — different bias।

Failure modes:

Bad initialization — vanishing/exploding gradient।
Wrong learning rate — divergence বা stuck।
Insufficient data — SGD overfits, generalize ব্যর্থ।
Architecture-task mismatch।

Modern training tricks:

Warmup + cosine decay LR schedule।
Batch size scheduling।
Weight decay (L2 regularization)।
Gradient clipping।
Mixed precision।

Open questions:

কেন overparameterized network generalize করে?
SGD-এর implicit regularization — exact characterization?
Loss landscape-এর geometry — high-D-এ?

মূল উপলব্ধি: UAT existence prove করে, SGD reach করে — দু'টোই separate miracle। DL-এর কাজ "existence + reachability"-এর fortuitous coincidence-এ। Theory পুরোপুরি catch up করতে পারেনি।

প্র ০৪ UAT continuous function-এ। কিন্তু LLM (GPT-4) discrete token predict করে — natural language tasks। UAT কি LLM-এর success ব্যাখ্যা করে, না অন্য theory দরকার?

Modern AI-এর সবচেয়ে hot theoretical question।

LLM = continuous function?

Internal computation — continuous (matrix multiplication, softmax)।
Output layer — vocabulary-এর উপর probability distribution (continuous)।
Sampling — discrete token (argmax বা random)।
"Function" বলতে — text → next-token-distribution।

UAT applicability:

Token-level — UAT applies (continuous function approximation)।
Sequence-level — Transformer = function of variable-length sequence। UAT-এর extension prove হয়েছে।
Reasoning, in-context learning — UAT explain করে না সম্পূর্ণ।

Beyond UAT — other theories:

Scaling laws (Kaplan ২০২০, Chinchilla ২০২২): empirical power-law relation between model/data/compute and loss।
Phase transitions: certain capabilities suddenly emerge at specific scale।
In-context learning theory: model implicitly performs gradient descent inside forward pass।
Mesa-optimization: learned algorithm inside learned model।

LLM unique properties:

Few-shot learning: example দিলে শেখে — UAT-এর scope বাইরে।
Chain-of-thought reasoning: intermediate computation।
Tool use, agent behavior: emergent।
Compositional generalization: training data-এ unseen combination।

Theoretical frontiers:

Mechanistic interpretability: circuit-level understanding (Anthropic)।
Information theory of LLMs: Solomonoff induction approximation?
Algorithmic computation: transformer = differentiable computer।
Statistical physics analogies: phase transition, entropy।

UAT relevance:

Necessary condition — যদি UAT না হতো, expressiveness অভাব।
Sufficient না — capacity ছাড়াও data quality, optimization, architecture।
"Skeleton" theory — DL-এর সব behavior explain করে না।

Future of theory:

UAT — DL-এর Newton mechanics (basic but limited)।
Modern theory — DL-এর quantum mechanics খোঁজা।
Practitioner-দের জন্য — empirical scaling laws-ই বেশি useful।

মূল উপলব্ধি: UAT — DL-এর foundation, কিন্তু পুরো গল্প না। LLM-এর behavior — emergence, scaling, in-context — separate theoretical frameworks দরকার। Active research এখনো উন্মুক্ত।

অনুশীলন

Construct: Two sigmoid দিয়ে একটি bump $[2, 5]$ interval-এ — formula লিখুন (steep transition $s=10$)।
$\text{bump}(x) = \sigma(10(x - 2)) - \sigma(10(x - 5))$
- $x < 2$: প্রথমটি ~০, দ্বিতীয়টি ~০ → ০।
- $2 < x < 5$: প্রথমটি ~১, দ্বিতীয়টি ~০ → ১।
- $x > 5$: প্রথমটি ~১, দ্বিতীয়টি ~১ → ০।
Code: উপরের sin-fit কোডে $h = 1$ ব্যবহার করলে কী হবে? কেন?

$h = 1$ — মাত্র একটি hidden neuron। নেট: $y = w_2 \tanh(w_1 x + b_1) + b_2$। শুধু একটি single tanh shape — sin-এর full oscillation কখনোই capture করতে পারে না। Loss high থাকবে।
Reflect: "Universal" শব্দটা UAT-এ overpromise করে কি? কোন সাধারণ ভুল ধারণা মানুষ করে?
সাধারণ ভুল ধারণা:
- "Network যেকোনো কিছু শিখতে পারবে" — না, যথেষ্ট data ও সঠিক optimization লাগে।
- "একটি স্তর-ই যথেষ্ট" — practical-এ width exponential হতে পারে।
- "UAT ⟹ DL কাজ করবে" — existence ≠ trainability।
- "Network যেকোনো input-এ generalize করবে" — UAT training distribution-এ, OOD-তে guarantee নাই।
"Universal" actually narrow — continuous functions on compact sets-এ existence। Practical ML-এর জন্য needed অনেক বেশি।