Regression

Regression is a way to predict a continuous value (a number that can take many values, not just categories) using other input features. The key thing is that we need continuous value. It tries to find the relationship between input variables (X) and an output variable (y).

Regression

In simple words: Regression helps answer questions like “If X changes, how does Y change?”

Some examples of Regression:
- Predicting house prices based on size, location, and number of rooms.
- Forecasting stock prices based on past trends.
- Estimating a person’s weight based on height and age.
- Predicting the temperature tomorrow based on today’s weather conditions.

Here, we need to predict the y based on the given input x and the model parameter θ. The θ depends on the dataset, and also depends on the Model we are going to use.

Regression in Machine Learning

Parameters vs Hyperparameters

Parameters = values learned from training data
It defines the model’s internal structure used for predictions
Example:
- Linear Regression: slope (m) and intercept(b)
- Neural Networks: weights, biases
- SVM: This model learns a hyperplane (decision boundary). The coefficients (weights) of the hyperplane and the support vectors are the parameters learned during training.

Hyperparameters = values set before training
It controls how the model learns, but is not learned from the data
Example:
- KNN: number of neighbors (k)
- Neural Networks: learning rate, number of layers
- SVM: C, gamma, kernel type

Parametric vs. Non-Parametric Models

Parametric Models have a fixed number of parameters learned from training. SVM learns coefficients (weights) and support vectors, which define a decision boundary called a hyperplane. Similarly, Linear Regression learns parameters like the slope and intercept of the line. Once trained, predictions depend only on these learned parameters (not directly on the full dataset).

Non-parametric models do not learn fixed parameters. Instead, they rely on the training dataset directly for making a prediction. KNN is called a non-parametric model because it does not learn internal parameters. It simply stores the training data and, during prediction, compares new points to the stored data (neighbors). The model “learns nothing in advance,” but makes predictions by looking at the data each time.

Non-Parametric Regression (KNN)

In KNN, predictions are based on the “neighborhood” of similar data points. Here, we focus on KNN for regression, where the output is a continuous value. However, KNN can also be applied to classification tasks.

k-nearest neighbors(KNN) vs. Kernelized Regression(KR)

If a person lives in a poor neighborhood, their income is likely to be lower, and people around them will have similar income ranges. On the other hand, if someone lives in an expensive neighborhood in California (e.g., Beverly Hills or Palo Alto), their income is likely to be higher compared to someone from a poorer area.

Similarly, if we have a basket with 10 bad apples and if we pick an 11th apple from the same basket, chances are it will also be bad.

The idea is that “your value is influenced by the values of your neighbors”. KNN assumes that if most of the nearby data points (neighbors) have a certain property, the new point will likely share that property.

So, Non-parametric regression (like KNN) doesn’t assume a fixed formula. Instead, it uses the values of nearby data points (neighbors) to estimate the outcome.

Non-Parametric Regression (KNN)

For a new input x*, KNN looks at the k closest points (neighbors) from the training data. Once the k nearest points are found, the prediction is the average of their outputs, that is, y*.

So, we look at the k closest neighbors, take their values (y’s), and average them to get the prediction.

When k = N (total data size), meaning we use all the data points as neighbors. Then, the prediction will just be the average of the entire dataset. This doesn’t give useful local predictions anymore; it just gives one global mean value.

Small k (like 1 or 3): Predictions depend heavily on very close neighbors → more local and sensitive.
Large k (like N = 1000): Prediction is just the global average → more general but loses local detail.
That’s why choosing the right k is crucial in kNN.

KNN with k = 2

KNN with k=2 looks at the two closest points and predicts by averaging their values. But if those neighbors aren’t good representatives, the prediction may be inaccurate.

In KNN, prediction is usually done by taking the average of neighbors, but it can also use other strategies like the median or a weighted average (giving closer neighbors more influence).

Kernelized Regression (KR)

• Also known as Nadaraya-Watson regression
• It is the weighted average

Kernelized regression is a smart way to make predictions by asking: “How similar is this new thing to things I’ve seen before?”

Instead of trying to fit a straight line through data points (like regular regression), kernelized regression:
1. Looks at how “similar” a new point is to each point in our training data
2. Uses the most similar points to make a prediction
3. Gives more weight to very similar points, less weight to dissimilar ones

The Weighted Average Form

The core idea is that the prediction ŷ* is a weighted average of all the known answers (yₙ) from the dataset.

where,
- ŷ* is the new prediction
- yₙ is a known answer from the dataset
- wₙ is the weight (or importance) we assign to that specific yₙ

For any weighted average, all the weights wₙ must add up to 1.

How the Weight (wₙ) is Calculated

The weight wₙ is based on similarity: we give more weight to yₙ if its corresponding input xₙ is “closer” to the new input x*.

The formula for the weight of a single point n

This fraction is just a clever way to turn “similarity scores” into percentages that sum to 1.

• Numerator: K(x*, xₙ)
  - This is the “raw similarity score” between your new point (x*) and a single training point (xₙ).
  - The kernel K outputs a high number if they are similar and a low number if they are different.
• Denominator: Σₘ K(x*, xₘ)
  - This is the “total similarity score.”
  - It’s the sum of the raw similarity scores between x* and all the training points.

The Final Formula

Replace the wₙ in ŷ* = Σₙ(wₙ).yₙ , we get

Kernelized Regression (KR)

The general form for the y

A kernel function K(x*, xₙ) takes two inputs and gives back one number (scalar). Behind the scenes, it first maps each input into a (possibly hidden) higher-dimensional space and then takes the dot product of those two mapped points. Because a dot product is large when two vectors point in a similar direction, the kernel’s value tells you how alike the two inputs are in that hidden space; not necessarily how close they are in ordinary distance, but how well their hidden features match.

The formula essentially says: “Average all the known outcomes, but weight them by how similar each training point is to the new point you’re predicting.”

This makes kernelized regression very flexible as it can capture complex, non-linear patterns without assuming the data follows a straight line.

Example:
We want to predict the price of a 1100 sq ft house using kernelized regression(KR) with a Gaussian kernel (σ = 300).

Overview of the calculation (Only one feature)
Step 1: Calculate the “similarity score” (kernel value) between the new point (1100 sq ft) and every house in the dataset.

Step 2: Add all those similarity scores together, then divide each individual score by this total sum to get its percentage weight.

Step 3: Multiply the price of each house by its unique percentage weight and add all those final values together for the prediction.

Input Data (Training Dataset)

Step 1: Calculate Kernel Values K(1100, each training house)

Formula: K(x₁, x₂) = exp(-(x₁ - x₂)² / (2σ²)) where σ = 300.
Here we are using a Gaussian (RBF) Kernel.
x₁ this is what we want to predict, which is 1100. (i.e., x₁ = 1100)

For House 1 (1000 sq ft):
K(1100, 1000) = exp(-(1100–1000)² / (2 × 300²))
              = exp(-(100)² / (2 × 90,000))
              = exp(-10,000 / 180,000)
              = exp(-0.0556)
              = 0.945959

For House 2(1200 sq ft):
K(1100, 1200) = exp(-(1100–1200)² / (2 × 30⁰²))
              = exp(-(-100)² / 180,000)
              = exp(-10,000 / 180,000)
              = exp(-0.0556)
              = 0.945959

For House 3(1500 sq ft):
K(1100, 1500) = exp(-(1100–1500)² / (2 × 30⁰²))
              = exp(-(-400)² / 180,000)
              = exp(-160,000 / 180,000)
              = exp(-0.889)
              = 0.411112

For House 4(2000 sq ft):
K(1100, 2000) = exp(-(1100–2000)² / (2 × 30⁰²))
              = exp(-(-900)² / 180,000)
              = exp(-810,000 / 180,000)
              = exp(-4.5)
              = 0.011109

For House 5(2200 sq ft):
K(1100, 2200) = exp(-(1100–2200)² / (2 × 30⁰²))
              = exp(-(-1100)² / 180,000)
              = exp(-1,210,000 / 180,000)
              = exp(-6.72)
              = 0.001204

Step 2: Normalize Weights (so they sum to 1)

Total Kernel Sum = 0.945959 + 0.945959 + 0.411112 + 0.011109 + 0.001204 
                 = 2.315344

Weight₁ = 0.945959 / 2.315344 = 0.408561 (40.9%) 
Weight₂ = 0.945959 / 2.315344 = 0.408561 (40.9%)
Weight₃ = 0.411112 / 2.315344 = 0.177560 (17.8%)
Weight₄ = 0.011109 / 2.315344 = 0.004798 (0.5%)
Weight₅ = 0.001204 / 2.315344 = 0.000520 (0.1%)

Step 3: Apply Weighted Average

Predicted Price = Σ (Weight × Price)
                = (0.408561 × 200,000) + (0.408561 × 250,000) + (0.177560 × 320,000) +(0.004798 × 400,000) + (0.000520 × 450,000)
                = 81,712 + 102,140 + 56,819 + 1,919 + 234
                = 242825

Interpretation:

• Houses at 1000 & 1200 sq ft dominate the prediction (81.6% combined influence)
• The 1500 sq ft house adds some influence (17.8%)
• Larger houses (2000+ sq ft) barely matter (less than 1%)
• Result: The prediction is heavily influenced by the two closest houses, giving us a reasonable price of $242,825k

You can explore this concept interactively with kernelized regression visualization that lets you adjust parameters in real-time.

This makes intuitive sense: A 1100 sq ft house should be priced between the 1000 sq ft ($200k) and 1200 sq ft ($250k) houses, which is exactly what we got!

Overview of the calculation (More than one features)
With one feature, the distance was simple: (x₁ - x₂)²

With multiple features (e.g., x = [size, bedrooms]), the "distance" becomes the squared Euclidean distance, which is just the sum of the squared differences for each feature.i.e. (size₁ - size₂)² + (bedrooms₁ - bedrooms₂)²

The Gaussian kernel formula K(x₁, x₂) = exp(- Distance² / 2 σ²) stays the same, but we plug in this new multi-feature distance.

The steps (with 2 Features)
Let’s predict the price of a new house x* = [1100 sq ft, 3 beds].
Let's use a training house x₁ = [1000 sq ft, 2 beds].

Problem: A distance of “1 bedroom” is not comparable to “100 sq ft”. Before we do anything, we must normalize the features (e.g., using standardization or min-max scaling) so they are on the same scale. For this example, let’s just assume they are already scaled.
The steps look exactly the same, but Step 1 is now multi-dimensional.

Step 1: Calculate the “similarity score” (kernel value) for each house.
Distance for House 1:
Dist² = (1100 - 1000)² + (3 - 2)²
Dist² = 100² + 1²
Dist² = 10,000 + 1 = 10,001

Kernel Value for House 1: K(x*, x₁) = exp(-10,001 / (2 σ²))
(Repeat this for every house in the dataset)

Step 2: Add all kernel scores together (e.g., K₁ + K₂ + ...) to get a "Total Sum," then divide each individual score by this total to get its percentage weight.
w₁ = K₁ / Total Sum
w₂ = K₂ / Total Sum
…and so on

Step 3: Multiply the price of each house by its unique percentage weight and add all those final values together for the prediction.
ŷ* = (w₁ × Price₁) + (w₂ × Price₂) + ...

KNN vs Kernelized Regression (KR)

Kernel Function

• Kernel methods are a powerful technique that enables linear algorithms to solve non-linear problems by implicitly transforming data into higher-dimensional spaces.
• The fundamental insight is that many datasets that are not linearly separable in their original space become linearly separable when mapped to a higher-dimensional feature space.
• Kernel methods implicitly map data from a lower-dimensional input space to a higher-dimensional feature space where linear algorithms can find solutions.
• The key is that we never actually compute the high-dimensional coordinates. We only work with kernel values. When the linear decision boundary from the high-dimensional space is projected back to the original space, it appears as a non-linear boundary. This is done using a function called the kernel function without explicitly computing the coordinates in that space.

You can explore how we separate data points by mapping them into higher dimensions with an interactive visualization that lets you adjust parameters in real time.

• The reason we project data into a higher-dimensional space is that it becomes easier to find a separation line (or hyperplane) there.
• Points that are close in distance are considered more similar. The kernel method says: “If you give me data points in the lower-dimensional space, it may be hard to calculate their similarities directly. So, I will project them into a higher-dimensional space where computing similarities is easier.”
• Once projected, the similarities calculated in the higher-dimensional space effectively represent the similarities in the original lower-dimensional space.

A kernel function K(x, y) computes the inner product between two vectors after they have been mapped to a higher-dimensional space:
K(x, y) = ⟨φ(x), φ(y)⟩

Get Prajun Trital’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Where:
- K(x, y) = kernel function
- φ(x) = mapping function to higher-dimensional space
- ⟨·,·⟩ = inner dot product

Implicit Mapping

We never explicitly compute φ(x) (the high-dimensional coordinates)

• We only compute K(x, y) directly
• This avoids the computational cost of working in high dimensions
• Known as the “kernel trick”

Why Dot Product in Kernel Methods?

Similarity Measure

• The dot product tells us how similar two vectors are in direction.
• If two vectors point in the same direction, → the dot product is large (high similarity).
• If they are orthogonal (90° apart), → dot product is 0 (no similarity).
• If opposite → dot product is negative.
• This makes it a natural way to measure similarity between data points.

Decision Boundaries in SVM

• SVM decision rules depend on the distance of a point from the hyperplane.
• This distance is computed using dot products (between data points and the weight vector).
• Without dot products, SVM cannot check how “aligned” a point is with the separating hyperplane.

Requirements of Kernel Functions

For a function k(x, y) to be a valid kernel function that can be expressed as an inner product in some higher-dimensional feature space 𝒱, it must satisfy two fundamental conditions:

• Symmetry: k(x, y) = k(y, x)
• Positive Semi-Definiteness

When we map data to higher dimensions, computing dot products becomes very expensive.
For example, if we map 2D data (x₁, x₂) to 6D space:

• Feature mapping: φ(x) = [x₁², x₂², √2x₁x₂, √(2c)x₁, √(2c)x₂, c]
• Computing dot product: φ(x) · φ(y) requires:
  First: Calculate all 6 features for both x and y
  Then: Multiply corresponding features and add them up
  This is slow and uses lots of memory

The Smart Solution — Kernel Trick:
Instead of doing all that work, we use the kernel function:
K(x, y) = (x₁y₁ + x₂y₂ + c)²

No feature computation needed! We never calculate φ(x) or φ(y)
Direct calculation: The kernel gives us the same result as φ(x) · φ(y)
Much faster: Just compute the simple kernel formula
Saves memory: No need to store high-dimensional vectors

Instead of: φ(x) · φ(y) = [expensive calculation in high dimensions]
We use: K(x, y) = [simple calculation in original dimensions]
Result: SAME ANSWER, much less work!

Common Types of Kernels. All of these kernels returns a scalar.

1. Linear Kernel: k(x, y) = xᵀy
   This is the simplest kernel. It is just the regular dot product between two vectors.
   φ(x) = x, φ is the identity map
   The feature mapping is just the identity function; no transformation happens. The data stays in the original space.
   Use this when the data is already linearly separable and complex decision boundaries are not needed.
2. Polynomial Kernel: k(x, y) = (xᵀy + c)ᵈ, for c ≥ 0
   where:
   c: Constant term (usually c ≥ 0 for positive semi-definiteness)
   d: Degree of the polynomial

• Instead of explicitly computing φ(x) and φ(y) for polynomial relationships and then taking their dot product, we can directly use the polynomial kernel function: ⟨φ(x), φ(y)⟩ = k(x, y) = (xᵀy + c)ᵈ
• This kernel function produces the same result as the dot product in the higher-dimensional feature space, but only requires operations in the original input space. As a result, it avoids both the computational cost and the memory requirements of explicitly working with expanded feature vectors.

Example:
Suppose, x = (2, 1), x′ = (1, 3), c = 1, and d = 2
We will compute, k(x, x′) = (xᵀx′ + c)ᵈ
First, compute the inner product: xᵀx′= 2⋅1 + 1⋅3 = 5

What is xᵀx′? When we have two column vectors with a transpose and another with no transpose, then it is a dot product and returns a single scalar (a 1 x 1 value)

Then apply the kernel: k(x, x′) = (xᵀx′+ c)ᵈ = (5 + 1)² = 6² = 36
So the similarity score between x and y in the kernel space is 36.

Where This Comes From (Feature Map Expansion)?

Verify with our Example

This matches our kernel computation.
These can be explained with the following slides:

Kernel Method Illustration

• In the above figure, we have 9 points in a 2D plane, i.e., R². And in 2D, these red and green points cannot be separated by a straight line (linear boundary).
• So, we map them to a higher-dimensional space (R⁶) using a polynomial feature map. The feature map takes (x₁, x₂) to 6 coordinates (because it’s using a polynomial kernel of degree 2).

Original 2D point becomes a point in 6D

In that 6D space, a separating hyperplane can be written as:
w₁ ​+ w₂ ​− 25 = 0 (We get 25 from the radius of a circle in the above graph, which is 5)
Where w₁ = x₁² and w₂ = x₂²

If we substitute back w₁ = x₁² and w₂ = x₂²
w₁ ​+ w₂ ​− 25 = 0 ⟹ x₁² ​+ x₂² ​= 25
This is just the equation of a circle with radius 5 in the original 2D plane.

So:
In R⁶ → the separation looks linear (a flat hyperplane).
In R² → that same separation appears as a non-linear circle boundary.

Visualizing polynomial Kernel

3. Gaussian (RBF) Kernel: k(x, y) = exp(-||x-y||² / 2σ²)
Where:
- x, y are input data points
- ||x-y||² is the squared Euclidean distance between points
- σ² is the bandwidth parameter that controls the kernel width

The Gaussian RBF kernel implicitly corresponds to a mapping into an infinite-dimensional space. Points that are close in the original space have high kernel values (close to 1), while distant points have low kernel values (close to 0).

How the Gaussian Kernel Works in Practice

• The kernel assigns weights to training points based on their similarity to a query point
• Points closer to the query point receive higher weights
• The final prediction is a weighted average of nearby training points
• This creates a smooth, non-linear function that can fit complex patterns

Parameter of Gaussian Curve

The Gaussian kernel is widely used in:
- Support Vector Machines (SVM)
- Kernel Ridge Regression
- Gaussian Processes
- Kernel PCA
- Various other kernel-based machine learning algorithms

🔖 Learn ML by doing: Interactive demos

🔙 Back to all notes
𝕏 Let’s Connect

Backlinks:
Machine Learning