Kernel Methods & RBF Networks: Kernels, RBF, SVM, and Approximation

TAKEAWAYS:

• Kernel methods map input data into higher-dimensional spaces to enable linear separation of non-linear problems using kernel functions (e.g., Gaussian, polynomial).
• RBF networks use radial kernels to approximate complex functions via localized basis functions, trained via least-squares or gradient descent.
• SVM and RBF networks both rely on kernel tricks but differ in optimization objectives (margin maximization vs. function approximation).
• Kernel methods excel in high-dimensional data (e.g., text, images) but suffer from computational costs for large datasets.
• RBF networks are widely used in time-series prediction, robotics, and financial modeling due to their universal approximation capability.
• The choice between kernel methods depends on data structure, interpretability needs, and computational constraints.

---

1. Kernel Methods: The Core Idea

Kernel methods transform input data into a higher-dimensional space where linear separation becomes possible. Instead of explicitly computing the transformation (which can be computationally expensive), we use kernel functions to compute inner products in the transformed space.

1.1 Why Kernels?

• Non-linear problems: Many real-world datasets (e.g., XOR, spiral data) are not linearly separable in their original space.
• Curse of dimensionality: Directly computing transformations (e.g., $\varphi (x)$) is often infeasible for high-dimensional data.
• Kernel trick: Compute $K(x_i,x_j)=\varphi (x_i{)}^T\varphi (x_j)$ without explicitly knowing $\varphi$.

1.2 Common Kernel Functions

1.3 Worked Example: Kernelized Linear Regression

Problem: Predict house prices (target $y$) based on features $x$ (e.g., size, location). Assume a non-linear relationship exists. Solution: Use a Gaussian kernel to transform features into a higher-dimensional space.

1. Kernel matrix $K$ for training data $X=[x_1,x_2,x_3]$: $$K_{ij}=\exp (-\gamma \Vert x_i-x_j{\Vert }^2)$$ For $\gamma =0.5$ and $x_1=1,x_2=2,x_3=3$: $$K=\left[\begin{array}{ccc}1& \exp (-0.5\cdot 1)& \exp (-0.5\cdot 4)\\ \exp (-0.5\cdot 1)& 1& \exp (-0.5\cdot 1)\\ \exp (-0.5\cdot 4)& \exp (-0.5\cdot 1)& 1\end{array}\right]\approx \left[\begin{array}{ccc}1.00& 0.61& 0.14\\ 0.61& 1.00& 0.61\\ 0.14& 0.61& 1.00\end{array}\right]$$

2. Kernel ridge regression: $$\hat{y}=K(X,x^{\ast })\alpha$$ where $\alpha =(K+\lambda I{)}^{-1}y$.

Real-world tie-in:

• eSewa’s fraud detection: Uses kernel SVM to classify transactions as fraudulent/legitimate by mapping raw features (amount, time, location) into a space where fraud patterns become linearly separable.
• NEPSE stock prediction: Gaussian kernels help model non-linear trends in stock prices by capturing complex relationships between historical data points.

---

2. Radial-Basis Function (RBF) Networks

RBF networks are universal approximators that model non-linear functions using localized basis functions. They consist of:

1. Input layer: Raw features.
2. Hidden layer: RBF units (each computes a radial kernel).
3. Output layer: Linear combination of hidden activations.

2.1 Structure of an RBF Network

2.2 RBF Units: The Building Blocks

Each hidden unit computes: $${\varphi }_j(x)=\exp \left(-\frac{\Vert x-{\mu }_j{\Vert }^2}{2{\sigma }_j^2}\right)$$

• ${\mu }_j$: Center of the $j$-th RBF unit (learned or fixed via clustering).
• ${\sigma }_j$: Width of the RBF (controls locality).
• Visualization: A 2D RBF unit with ${\mu }_j=(1,1)$ and ${\sigma }_j=0.5$:

2.3 Training an RBF Network

1. Step 1: Determine centers (e.g., via $k$-means clustering on input data).
2. Step 2: Compute widths (e.g., average distance to nearest neighbors).
3. Step 3: Train output weights using least-squares: $$W=({\Phi }^T\Phi {)}^{-1}{\Phi }^{T}y$$ where $\Phi$ is the matrix of RBF activations.

Worked Example: Predicting Traffic Congestion Problem: Predict traffic delay (minutes) at a Kathmandu intersection based on time of day ($x_1$) and weather ($x_2$). Data:

1. Cluster centers (2 units):
   • ${\mu }_1=(10,1)$, ${\mu }_2=(15,3)$.
2. Compute RBF activations for $\sigma =2$: For $x=(8,0)$: $${\varphi }_1=\exp \left(-\frac{(8-10{)}^2+(0-1{)}^2}{8}\right)=0.56$$ $${\varphi }_2=\exp \left(-\frac{(8-15{)}^2+(0-3{)}^2}{8}\right)=0.01$$
3. Train weights: Solve $W={\Phi }^{T}y$ for all data points.

Real-world tie-in:

• Pathao’s route optimization: Uses RBF networks to predict congestion delays by learning localized patterns in driver data (time, location, weather).
• NTC’s network planning: RBF networks model non-linear demand patterns to optimize tower placements.

---

3. Kernel Methods vs. RBF Networks vs. SVM

---

4. Advantages and Limitations

Advantages of Kernel Methods/RBF Networks

• Non-linearity: Handle complex patterns without manual feature engineering.
• Universal approximation: RBF networks can approximate any continuous function (given enough units).
• Flexibility: Kernels adapt to data structure (e.g., Gaussian for smooth data, polynomial for structured data).

Limitations

• Computational cost: Kernel matrices scale as $O(n^2)$ in memory.
• Hyperparameter sensitivity: Choice of $\gamma$ (RBF width) or $C$ (SVM regularization) critically affects performance.
• Interpretability: Black-box nature limits debugging.

Exam Pitfall:

• Overfitting: RBF networks with too many centers or narrow widths will overfit. Always validate with a holdout set.
• Kernel selection: Polynomial kernels may fail for highly non-linear data; Gaussian kernels are safer but slower.

---

5. Applications in Nepal and Globally

In Nepal

1. Khalti’s transaction risk scoring:

   • Uses RBF networks to model non-linear relationships between transaction features (amount, time, device) and fraud risk.
   • Why RBF? Localized basis functions capture rare but critical fraud patterns (e.g., small transactions at odd hours).

2. NTC’s signal strength prediction:

   • Kernel ridge regression predicts signal attenuation in hilly terrain by mapping raw features (elevation, distance) into a space where terrain effects become linear.

3. NEPSE’s volatility modeling:

   • Gaussian kernel SVM classifies high/low volatility days by transforming raw price data into a space where volatility clusters are separable.

Globally

1. YouTube’s recommendation system:

   • Uses kernel methods to compute similarities between user preferences and video features (e.g., cosine similarity in a transformed space).

2. Autonomous vehicles (e.g., Tesla):

   • RBF networks model sensor inputs (LiDAR, camera) to predict object trajectories in real-time.

3. Drug discovery (e.g., DeepMind/AlphaFold):

   • Kernel methods compare molecular structures by embedding them into high-dimensional spaces where chemical similarity is linear.

---

6. Implementation Steps (Pseudocode)

# RBF Network Training (Scikit-learn style)
from sklearn.cluster import KMeans
from sklearn.linear_model import LinearRegression

def train_rbf(X, y, n_centers=5, sigma='auto'):
    # Step 1: Cluster centers
    kmeans = KMeans(n_clusters=n_centers).fit(X)
    centers = kmeans.cluster_centers_

    # Step 2: Compute RBF activations
    if sigma == 'auto':
        sigma = np.mean([np.linalg.norm(x - c) for x in X for c in centers]) / np.sqrt(2 * n_centers)
    Phi = np.exp(-np.sum((X[:, np.newaxis] - centers)**2, axis=2) / (2 * sigma**2))

    # Step 3: Train linear output
    model = LinearRegression().fit(Phi, y)
    return model, centers, sigma

Exam Tip:

• Derive the kernel matrix for small datasets (e.g., 3 points) in the exam.
• Compare RBF and SVM: RBF networks approximate functions; SVM classifies with margins. Both use kernels but optimize different objectives.
• Hyperparameters: Always mention $\gamma$ (RBF width), $C$ (SVM regularization), and $n_{\text{centers}}$ (RBF units) in discussions.

---

## Exam Tip

1. For theoretical questions:

   • Define kernel methods as "techniques that operate in a high-dimensional space via implicit transformations using kernel functions."
   • For RBF networks, emphasize their two-stage training (centers first, then weights).
   • Derive the kernel matrix for 2–3 data points to show understanding.

2. For numerical problems:

   • Always show steps: Compute $K(x_i,x_j)$ explicitly for Gaussian/polynomial kernels.
   • Assume $\gamma =1$ if not given for RBF kernels to simplify calculations.
   • Plot the kernel function for a given $\gamma$ (e.g., Gaussian kernel for $x\in [-2,2]$).

3. For comparisons:

   • Use a table to contrast RBF networks (approximation), SVM (classification), and kernel PCA (dimensionality reduction).
   • Highlight that all three use kernels but solve different problems.

4. Common exam traps:

   • Confusing $\gamma$ and $\sigma$: $\gamma =1/(2{\sigma }^2)$ in Gaussian kernels.
   • Overfitting: RBF networks with too many centers or narrow $\sigma$ will memorize training data.
   • Kernel selection: Polynomial kernels are rare in practice; focus on Gaussian/RBF.

5. Visuals to include in answers:

   • Draw a kernelized decision boundary (e.g., XOR problem solved with RBF kernel).
   • Sketch an RBF network architecture with 3 input features, 4 RBF units, and 1 output.
   • Plot a Gaussian kernel for $\gamma =0.5$ and $\gamma =2$ to show width effects.