Neural Networks and Deep Learning Algorithms
Open in the Padhaiko app5.1 Neural networks: Structures, activation functions and universal approximation theorem
An Artificial Neural Network (ANN) is a computational graph composed of interconnected processing units (neurons or nodes) organized in layers that learn hierarchical representations from data.
Structure of an Artificial Neuron and Network
A single neuron computes an affine combination of inputs with weights and bias , followed by a nonlinear activation function :
A standard feedforward network has:
- Input layer: receives raw features (no computation).
- Hidden layer(s): extract increasingly abstract nonlinear features; each neuron connects to the previous layer via learnable weights.
- Output layer: produces task predictions (linear for regression, sigmoid for binary classification, softmax for multi-class).
Activation Functions
Without nonlinear activation functions, any stack of linear layers collapses to a single linear map (). Nonlinearity enables learning complex boundaries.
| Activation | Formula | Range | Derivative | Key Advantage / Issue |
|---|---|---|---|---|
| Step (Threshold) | if else | (undefined at ) | Used in classic perceptron; cannot train with gradient descent | |
| Sigmoid (Logistic) | Smooth probability output; saturates and causes vanishing gradients | |||
| Hyperbolic Tangent () | Zero-centered (better than sigmoid); still saturates for large | |||
| ReLU | if else | Fast, avoids saturation for ; can suffer dying ReLU () | ||
| Leaky ReLU | if else | Prevents dying ReLU with small negative slope | ||
| Softmax (output) | , sums to | Coupled Jacobian | Converts raw logits into a valid probability distribution |
Universal Approximation Theorem
Universal Approximation Theorem (Cybenko, Hornik)
A feedforward neural network with a single hidden layer containing a finite number of neurons and a non-constant, bounded, continuous (or non-polynomial, e.g., ReLU/sigmoid) activation function can approximate any continuous function on a compact subset to any desired degree of accuracy , given enough hidden units.
5.2 Perceptron, multilayer perceptron and backpropagation
Single-Layer Perceptron
Introduced by Frank Rosenblatt (1958), a perceptron computes (or ).
- Perceptron learning rule: For training sample and learning rate :
- Perceptron Convergence Theorem: Guaranteed to converge in finite steps if and only if the data is linearly separable.
- XOR limitation (Minsky & Papert, 1969): A single perceptron produces a single hyperplane and cannot solve linearly non-separable problems such as XOR.
Multilayer Perceptron (MLP)
Adding one or more hidden layers with nonlinear activations produces a Multilayer Perceptron (MLP), which combines multiple hyperplanes to represent arbitrary non-convex and non-linearly separable regions (including XOR).
Backpropagation Algorithm
Backpropagation (Rumelhart, Hinton, & Williams, 1986) trains MLPs efficiently by applying the chain rule of calculus backwards from the loss to compute exact gradients in a single backward sweep.
1. Forward pass:
For each layer l = 1 .. L:
z^[l] = W^[l] * a^[l-1] + b^[l]
a^[l] = sigma(z^[l])
2. Compute output loss L(a^[L], y) and output delta:
delta^[L] = dL/dz^[L] (for cross-entropy + softmax: a^[L] - y)
3. Backward pass (for l = L-1 down to 1):
delta^[l] = (W^[l+1]^T * delta^[l+1]) elementwise* sigma'(z^[l])
4. Parameter gradients and update:
dL/dW^[l] = delta^[l] * a^[l-1]^T
dL/db^[l] = delta^[l]
W^[l] <- W^[l] - eta * dL/dW^[l], b^[l] <- b^[l] - eta * dL/db^[l]5.3 Introduction to deep learning
Deep Learning uses neural networks with many hidden layers to learn hierarchical feature representations automatically from raw data (pixels, audio waveforms, text tokens) without manual feature engineering.
Why Deep Learning Works (and Key Challenges)
- Depth advantage: Early layers detect low-level primitives (edges, phonemes); middle layers compose parts (shapes, motifs); deep layers recognize high-level concepts (faces, sentences).
- Challenges & modern solutions:
- Vanishing / exploding gradients: Gradients shrink or blow up across many layers. Solved via ReLU, He/Xavier weight initialization, Batch Normalization / Layer Normalization, Residual (skip) connections (), and gradient clipping.
- Overfitting with millions of parameters: Solved via Dropout, weight decay, data augmentation, and early stopping.
- Optimization speed: Mini-batch SGD with Momentum, RMSprop, and Adam adaptive optimizers on GPUs/TPUs.
Convolutional Neural Networks (CNNs) — Core Deep Architecture for Spatial Data
For grid data like images, a CNN replaces dense matrix multiplies with:
- Convolutional layers: Small learnable filters (kernels) slide across the input via weight sharing and local receptive fields, producing feature maps. For input size , kernel , padding , stride :
- Pooling layers (Max / Average pooling): Downsample feature maps to reduce parameters and add local translation invariance.
- Fully connected head: Maps flattened features to class logits.
5.4 Concepts on recurrent and generative neural networks
Recurrent Neural Networks (RNNs)
Standard feedforward networks assume fixed-size independent inputs. Recurrent Neural Networks (RNNs) handle sequential data (text, speech, time series) by keeping a hidden state that carries memory of previous steps:
- Trained by Backpropagation Through Time (BPTT) across unrolled time steps.
- Limitation of vanilla RNNs: Vanishing gradients over long sequences forget distant context.
- LSTM (Long Short-Term Memory) and GRU: Introduce a cell state and learnable gates (forget, input, output gates in LSTM; update and reset gates in GRU) creating additive gradient highways to remember long-range dependencies.
Generative Neural Networks
Whereas discriminative models learn , generative neural networks learn the data distribution (or ) to synthesize realistic new samples (images, audio, text).
| Architecture | Core Mechanism | Training Objective | Key Strength / Trade-off |
|---|---|---|---|
| Autoencoder (AE) & Variational AE (VAE) | Encoder maps to latent space ; decoder reconstructs | Maximize ELBO: reconstruction log-likelihood minus | Smooth latent space and stable training; outputs can be slightly blurry |
| Generative Adversarial Network (GAN) | Generator creates fake samples; Discriminator distinguishes real from fake | Two-player minimax game: | Very sharp images; prone to mode collapse and unstable training |
| Autoregressive & Transformer LLMs | Predict next token given prefix via self-attention | Maximum likelihood / cross-entropy over tokens | Dominant for text and multimodal generation; sequential sampling cost |
| Diffusion Models | Gradually add Gaussian noise to data, then learn a neural network to denoise step-by-step | Denoising score matching / MSE on predicted noise | State-of-the-art image fidelity and diversity; slow multi-step sampling |
Worked Out Examples
5.1
A single sigmoid neuron has input , weight , bias , and target . Using squared error loss and learning rate , perform one forward pass, compute the gradient , and find the updated weight .
Forward pass:
Backward pass (gradient ):
Gradient descent weight update ():
(Notice increases so moves closer to target .)
, , , and .
5.2
Show that a single perceptron with weights , bias , and step threshold if else implements the 2-input AND gate. Also state why no single perceptron can implement XOR.
Evaluate on all four inputs:
- : .
- : .
- : .
- : .
This matches the AND truth table exactly.
Why XOR fails: In space, and have target on opposite corners of the unit square while and have target on the other diagonal. No single straight line can separate the two classes, so a 2-layer MLP is required.
All four inputs match AND ( only at ). XOR is not linearly separable, so a single line (perceptron) cannot separate its classes.
5.3
An RGB image of size is passed to a convolutional layer with filters of spatial size . Compute the output spatial size when (a) padding , stride , and (b) padding , stride . Also find the total number of learnable parameters (weights + biases) in this layer.
Case (a) :
Case (b) :
Total learnable parameters: Each filter spans all input channels and has bias:
Output sizes: (a) , (b) . Total learnable parameters .
Exercises
Exercise: Neural Networks and Deep Learning
Why are nonlinear activation functions essential in multilayer neural networks? State the Universal Approximation Theorem and explain one practical limitation of a single-hidden-layer network.
Why nonlinearity matters: A composition of linear layers is still a single linear map and cannot learn curved decision boundaries.
Universal Approximation Theorem & limitation: Any continuous function on a compact domain can be approximated arbitrarily closely by a 1-hidden-layer network with non-polynomial activations. However, in practice it may need exponentially many hidden neurons and overfit or fail to optimize easily compared to deep networks.
Without nonlinear activations, deep networks collapse into a single linear transformation. UAT guarantees a 1-hidden-layer network can approximate any continuous function on a compact set, though it may require impractically wide layers.
Given raw output logits for a 3-class classifier, compute the Softmax probabilities .
Exponentiate each logit:
Sum: .
Normalize by :
(summing to ).
A perceptron has weights , bias , learning rate , and step output if else . For training input with target , compute and the updated weights and bias.
Compute weighted sum and prediction:
Apply perceptron update ():
; updated weights .
Explain the vanishing gradient problem in deep networks and recurrent neural networks, and list four techniques used to overcome it.
Cause: During backpropagation, gradients are multiplied across many layers (or time steps in BPTT). When activation derivatives (like sigmoid's max ) or weight eigenvalues are , the product shrinks exponentially toward , stalling updates in early layers/steps.
Four solutions: (1) ReLU/Leaky ReLU activations (derivative for ); (2) Residual/skip connections (); (3) Batch/Layer Normalization and He/Xavier initialization; (4) Gated RNN cells (LSTM / GRU) with additive cell-state highways.
Repeated multiplication of small derivatives shrinks gradients exponentially in deep/recurrent nets. Solutions include ReLU, residual skip connections, normalization + proper initialization, and LSTM/GRU gating.
Compare Variational Autoencoders (VAE) and Generative Adversarial Networks (GAN) in terms of architecture, loss objective, and output quality/stability.
VAE: Uses an encoder–decoder pair mapping inputs to a Gaussian latent space , trained by maximizing the ELBO (reconstruction accuracy minus KL divergence to prior). Training is stable, though generated images can appear slightly blurry.
GAN: Uses a Generator and Discriminator in a minimax adversarial game. Produces very sharp, realistic samples without explicit likelihood, but can suffer from mode collapse and unstable training.
VAEs optimize a stable variational lower bound (reconstruction + KL) with slightly blurrier outputs; GANs play a Generator–Discriminator minimax game producing sharper samples but risking mode collapse and instability.