Polynomial regression

The Core Idea

WHY does this work? Because we're still doing linear regression! The "linear" in linear regression means linear in parameters $\theta_i$, not in features. If we define new features $x_1 = x$, $x_2 = x^2$, $x_3 = x^3$, then our model becomes: $h_\theta(\mathbf{x}) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \theta_3 x_3$

This is linear in $\theta$! So we can use the same normal equation or gradient descent we already know.

Deriving the Model from First Principles

Step 1: Feature Transformation

Start with training data $(x^{(i)}, y^{(i)})$ where $i = 1, \ldots, m$.

Original feature vector: $\mathbf{x}^{(i)} = [x^{(i)}]$ (just one feature)

Transformed feature vector: $\phi(\mathbf{x}^{(i)}) = [1, x^{(i)}, (x^{(i)})^2, (x^{(i)})^3, \ldots, (x^{(i)})^d]$

Why? We create $d$ new features from the original $x$. This is called feature engineering. The hypothesis becomes: $h_\theta(x) = \theta^T \phi(x)$

Step 2: Apply Linear Regression

Build the design matrix $\Phi$ where each row is $\phi(\mathbf{x}^{(i)})$:

1 & x^{(1)} & (x^{(1)})^2 & \cdots & (x^{(1)})^d \\ 1 & x^{(2)} & (x^{(2)})^2 & \cdots & (x^{(2)})^d \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x^{(m)} & (x^{(m)})^2 & \cdots & (x^{(m)})^d \end{bmatrix}$$ **WHY this shape?** Each row represents one training example with all its polynomial features. We have $m$ rows (examples) and $d+1$ columns (features including intercept). The cost function is the same as linear regression: $$J(\theta) = \frac{1}{2m} \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})^2$$ > [!formula] Normal Equation for Polynomial Regression > $$\theta = (\Phi^T \Phi)^{-1} \Phi^T \mathbf{y}$$ > **Derivation:** Identical to linear regression. We minimize $J(\theta)$ by setting $\nabla_\theta J = 0$: > $$\frac{\partial J}{\partial \theta} = \frac{1}{m}\Phi^T(\Phi\theta - \mathbf{y}) = 0$$ > $$\Phi^T\Phi\theta = \Phi^T\mathbf{y}$$ > $$\theta = (\Phi^T\Phi)^{-1}\Phi^T\mathbf{y}$$ > > **WHY does this work?** We're solving the least-squares problem in the transformed feature space. The algebra is identical; only the matrix $\Phi$ changed. ## Worked Examples > [!example] Example 1: Fitting a Quadratic > **Data:** $(1, 3), (2, 7), (3, 13), (4, 21)$ > **Goal:** Fit $h_\theta(x) = \theta_0 + \theta_1 x + \theta_2 x^2$ > > **Step 1: Build $\Phi$** > $$\Phi = \begin{bmatrix} > 1 & 1 & 1 \\ > 1 & 2 & 4 \\ > 1 & 3 & 9 \\ > 1 & 4 & 16 > \end{bmatrix}, \quad \mathbf{y} = \begin{bmatrix} 3 \\ 7 \\ 13 \\ 21 \end{bmatrix}$$ > > **WHY these numbers?** Each row is $[1, x^{(i)}, (x^{(i)})^2]$. For example, row 1: $[1, 1, 1^2] = [1, 1, 1]$; row 2: $[1, 2, 2^2] = [1, 2, 4]$. > > **Step 2: Compute $\Phi^T \Phi$** > $$\Phi^T\Phi = \begin{bmatrix} > 4 & 10 & 30 \\ > 10 & 30 & 100 \\ > 30 & 100 & 354 > \end{bmatrix}$$ > > **WHY?** Matrix multiplication: element $(i,j)$ is the dot product of column $i$ of $\Phi^T$ with column $j$ of $\Phi$. For example, the top-left entry is $\sum_i 1 \cdot 1 = 4$ (four rows). > > **Step 3: Compute $\Phi^T \mathbf{y}$** > $$\Phi^T\mathbf{y} = \begin{bmatrix} 44 \\ 140 \\ 484 \end{bmatrix}$$ > > **WHY these numbers?** First entry: $\sum_i 1 \cdot y^{(i)} = 3+7+13+21 = 44$. Second: $\sum_i x^{(i)} y^{(i)} = 1\cdot3 + 2\cdot7 + 3\cdot13 + 4\cdot21 = 3+14+39+84 = 140$. Third: $\sum_i (x^{(i)})^2 y^{(i)} = 1\cdot3 + 4\cdot7 + 9\cdot13 + 16\cdot21 = 3+28+117+336 = 484$. > > **Step 4: Solve for $\theta$** > $$\theta = (\Phi^T\Phi)^{-1}\Phi^T\mathbf{y} = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$$ > > **Result:** $h_\theta(x) = 1 + x + x^2$ > > **Verification:** $h(1) = 1+1+1 = 3$ ✓, $h(2) = 1+2+4 = 7$ ✓, $h(3) = 1+3+9 = 13$ ✓, $h(4) = 1+4+16 = 21$ ✓. > > All four points lie **exactly** on $y = x^2 + x + 1$! With 3 parameters and 4 collinear-in-pattern points, the least-squares fit passes through them perfectly (zero training error). This is a rare exact fit; usually real data has noise and the fit is only approximate. > [!example] Example 2: Choosing Polynomial Degree > **Data:** Temperature (°C) vs Ice Cream Sales (units): $(10, 20), (15, 40), (20, 80), (25, 120), (30, 150)$ > > **Try degree 1 (linear):** $h(x) = \theta_0 + \theta_1 x$ > - Underfits: Can't capture the accelerating growth > - High training error > > **Try degree 2 (quadratic):** $h(x) = \theta_0 + \theta_1 x + \theta_2 x^2$ > - Good fit: Captures the curve > - Low training error, generalizes well > > **Try degree 4:** $h(x) = \sum_{i=0}^{4} \theta_i x^i$ > - Overfits: With 5 parameters and 5 data points, it wiggles through every point > - Zero training error, but terrible on new data > > **WHY does high degree overfit?** With degree 4 we have 5 parameters ($\theta_0, \ldots, \theta_4$) and only 5 data points. The model has just enough freedom to pass exactly through every point, so it memorizes noise instead of learning the pattern. This is the ==bias-variance tradeoff==. ## Feature Scaling is Critical > [!formula] Why Scale Polynomial Features? > If $x \in [1, 100]$, then $x^2 \in [1, 10000]$ and $x^3 \in [1, 1000000]$. > > **Problem:** Features have wildly different scales → gradient descent converges slowly, normal equation becomes numerically unstable. > **Solution:** Apply ==feature scaling== after transformation: > $$x_j^{(i)} \leftarrow \frac{x_j^{(i)} - \mu_j}{\sigma_j}$$ > where $\mu_j$ is mean and $\sigma_j$ is standard deviation of feature $j$. > > **WHY?** This makes all features have mean 0 and standard deviation 1, putting them on equal footing. ## Multiple Features For multiple input features $x_1, x_2, \ldots, x_n$, we can include: - **Pure powers:** $x_1^2, x_1^3, x_2^2, x_2^3, \ldots$ - **Interaction terms:** $x_1 x_2, x_1 x_2^2, x_1^2 x_2, \ldots$ Example with two features, degree 2: $$h_\theta(x_1, x_2) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \theta_3 x_1^2 + \theta_4 x_2^2 + \theta_5 x_1 x_2$$ **WHY interaction terms?** They capture how features work together. For example, predicting crop yield might depend on both rainfall AND temperature interacting (too much rain + too much heat = bad). > [!mistake] Common Error: Forgetting to Scale > **Wrong intuition:** "Feature scaling is optional, it just speeds up convergence." > > **Why it feels right:** For linear regression with similar-scale features, scaling isn't critical. > > **Why it's wrong:** With polynomial features, $x^2$ and $x^3$ can differ by orders of magnitude. Without scaling: > - Normal equation: $(\Phi^T\Phi)^{-1}$ becomes ill-conditioned (near-singular) > - Gradient descent: Takes forever or diverges > > **The fix:** Always scale features after polynomial transformation, before training. > [!mistake] Common Error: Using Too High Degree > **Wrong intuition:** "Higher degree = more flexible = better model." > > **Why it feels right:** Higher-degree polynomials fit training data better (lower $J_{\text{train}}$). > > **Why it's wrong:** They overfit! With degree $d$ you have $d+1$ parameters. When $d+1$ approaches or exceeds the number of training examples $m$, the model has enough freedom to fit every point exactly—including noise. In our 5-point example, degree 4 gives 5 parameters for 5 points, so training error hits zero but the fit wiggles wildly between points. > > **Steel-man:** Yes, higher degree reduces bias (model complexity). But it explodes variance (sensitivity to training data). The test error increases. > > **The fix:** Use ==cross-validation== to choose degree. Plot training and validation error vs. degree; pick the degree where validation error is lowest. > [!recall]- Explain to a 12-Year-Old > Imagine you're trying to draw a line through some dots on a graph. If the dots make a curve (like a smile 😊), a straight line won't work well—it'll miss most of the dots! > > Polynomial regression is like saying: "Instead of just drawing straight lines, let me also try drawing curves—like parabolas (U-shapes) or even wigglier curves." > > Here's the trick: We take our data (like the x-position of dots) and create new "super-features"—we square it ($x^2$), cube it ($x^3$), and so on. Then we use our old straight-line method (linear regression) on these new features! > > It's like we're telling the computer: "Hey, I know you can only draw straight lines, but what if I give you $x$, $x^2$, and $x^3$ as separate features? Then your 'straight line' in this new space will look like a curve in the original space!" > > But be careful! If you make the curve TOO wiggly (too high degree), it'll snake through every single dot perfectly—but that's called "memorizing" not "learning." It's like memorizing answers to practice problems instead of understanding the concept. When you get a new problem (new data), you'll fail! > [!mnemonic] Remembering When to Use Polynomial Regression > **"Curves Need Curves"** > - If your data **Curves**, you **Need** polynomial features (not a straight line) > - But remember: **C**hoose degree with **C**ross-validation > > **Degree selection:** Start with 1, 2, 3... "Low, Squared, Cubed" > - **1** = Low (linear) > - **2** = Squared (quadratic, parabola) > - **3** = Cubed (cubic, S-curves) > > **"Scale Before You Sail"** — Always feature scale before training! ## Connections - [[2.2.01-Linear-regression-fundamentals]] — Polynomial regression uses the same cost function and normal equation - [[2.2.05-Feature-scaling]] — Critical for polynomial features due to vastly different magnitudes - [[2.3.02-Overfitting-and-regularization]] — High-degree polynomials are prone to overfitting; regularization helps - [[2.4.01-Train-validation-test-split]] — Use validation set to select optimal polynomial degree - [[3.1.03-Bias-variance-tradeoff]] — Degree choice directly affects bias (underfitting) vs variance (overfitting) - [[2.2.03-Gradient-descent-variants]] — Can use gradient descent instead of normal equation for large feature sets #flashcards/ai-ml What is polynomial regression? ::: A regression technique that fits curved relationships by transforming input features into polynomial terms (x, x², x³, ...) and applying linear regression to these transformed features. Why does polynomial regression still count as "linear" regression? ::: Because it's linear in the parameters θ, not the features. h(x) = θ₀ + θ₁x + θ₂x² is linear in θ even though it's nonlinear in x. How do you create the design matrix Φ for polynomial regression of degree d? ::: Each row i contains [1, x⁽ⁱ⁾, (x⁽ⁱ⁾)², ..., (x⁽ⁱ⁾)ᵈ]. The matrix has m rows (examples) and d+1 columns (features including intercept). What is the normal equation for polynomial regression? ::: θ = (ΦᵀΦ)⁻¹Φᵀy, where Φ is the design matrix with polynomial features. It's identical to linear regression but uses transformed features. Why is feature scaling critical for polynomial regression? ::: Because polynomial features have vastly different magnitudes (x² and x³ can differ by orders of magnitude), causing numerical instability in the normal equation and slow convergence in gradient descent. What are interaction terms in polynomial regression? ::: Products of different features like x₁x₂ or x₁²x₂, which capture how features work together rather than just their individual effects. What happens if you use too high a polynomial degree? ::: Overfitting—the model has too many parameters relative to training examples, so it memorizes noise instead of learning patterns. Training error drops but test error increases. How do you choose the optimal polynomial degree? ::: Use cross-validation: train models with different degrees, plot training and validation error vs degree, and pick the degree where validation error is lowest. What is the transformation function φ(x) for degree-2 polynomial? ::: φ(x) = [1, x, x²], transforming a single feature x into three features (including intercept term). Why might polynomial regression underfit with degree 1? ::: A degree-1 polynomial is just a straight line, which cannot capture curved relationships in the data, leading to high bias and high training error. ## 🖼️ Concept Map ```mermaid flowchart TD LR[Linear regression] CURVE[Curved data] PR[Polynomial regression] LINP[Linear in parameters] FT[Feature transformation phi x] DM[Design matrix Phi] COST[Cost function J theta] NE[Normal equation] THETA[Parameters theta] GD[Gradient descent] CURVE -->|motivates| PR LR -->|extended by| PR PR -->|relies on| LINP LINP -->|allows reuse of| LR PR -->|starts with| FT FT -->|builds| DM DM -->|minimizes| COST COST -->|solved by| NE COST -->|solved by| GD NE -->|yields| THETA GD -->|yields| THETA ``` ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > Polynomial regression ka matlab hai ki agar apka data straight line ke bajaye curve follow karta hai, toh ap usko seedha line se fit nahi kar sakte. Jaise agar aap cricket ball ko hawa mein fekte ho, toh uski height parabola (U-shape) banati hai, straight line nahi. Toh yahan pe trick ye hai ki hum apne original feature x ko transform karke nayi features banate hain—x², x³, vagera—aur phir normal linear regression use karte hain in nayi features pe! > > Samajhne wali baat ye hai ki "linear" regression ka matlab "linear in parameters" hota hai, na ki "linear in features". Matlab h(x) = θ₀ + θ₁x + θ₂x² equation θ₀, θ₁, θ₂ ke liye linear hai, chahe x² non-linear ho. Isliye hum same normal equation ya gradient descent use kar sakte hain jo pehle seekha tha. > > Lekin ek badi dikat ye hai ki agar aap degree bohot zyada rakh doge (jaise degree 4 par sirf 5 ![[audio/2.2.06-Polynomial-regression.mp3]]