Statistical Learning, Linear Models, and Non-Linear Decision Theory

Terminology and Notation in Statistical Learning

  • Supervised Learning Fundamentals:

    • Supervised learning is a paradigm where a predictive model is trained using observed inputs and desired outputs. The central objective is to use input variables XX to predict target output variables YY.

    • Inputs: Also referred to as features, predictors, or independent variables.

    • Outputs: Also referred to as responses or dependent variables.

    • Variable Types:

    • In most practical statistical learning scenarios, inputs are quantitative (i.e., continuous or real-valued numbers x∈Rp\boldsymbol{x} \in \mathbb{R}^p).

    • Outputs can be quantitative (e.g., in regression problems where Y∈RY \in \mathbb{R}) or qualitative/categorical (e.g., in classification problems where output G∈GG \in \mathcal{G}).

    • Target Encoding:

    • Qualitative output variables are typically encoded into numeric representations for computational convenience. For example, binary outcomes such as "success" versus "failure" are mapped to 11 and 00, respectively.

    • Numeric code values representing categories are formally termed targets or labels.

  • Comprehensive Mathematical Notation Guide:

    • XX: The generic input variable representing a vector of features.

    • XjX_j: The jj-th component variable or feature of XX

    • xix_i: The ii-th observed instance of XX, structured as a pp-vector.

    • xijx_{ij}: The specific value of feature jj within the ii-th observed sample vector xix_i

    • YY: Quantitative output variable (Y∈RY \in \mathbb{R}).

    • GG: Qualitative or categorical output variable (G∈GG \in \mathcal{G}).

    • X\mathbf{X}: An N×pN \times p feature matrix containing NN observed sample vectors xix_i for i=1,…,Ni = 1, \dots, N

    • xj\mathbf{x}_j: An NN-vector column within matrix X\mathbf{X} comprising all NN observed measurements for feature variable XjX_j

    • xiTx_i^T: The ii-th row of matrix X\mathbf{X} (written as a row vector, since all standalone vectors default to column vectors).

    • Y^\hat{Y}: The model's predicted quantitative output value (Y^∈R\hat{Y} \in \mathbb{R}).

    • G^\hat{G}: The model's predicted categorical class label (G^∈G\hat{G} \in \mathcal{G}).

  • Indexing and Boldface Conventions:

    • Index ii is strictly used for rows (sample observations ranging from 11 to NN).

    • Index jj is strictly used for columns (input features ranging from 11 to pp).

    • Boldface Rule: Bold typography is reserved exclusively for matrices (e.g., X\mathbf{X}) and NN-vectors representing entire feature columns (e.g., xj\mathbf{x}_j). Boldface is not applied to individual observation pp-vectors (such as xix_i).

    • Training Set Representation: A dataset comprising NN observations used for training is expressed as T={(xi,yi)}i=1N\mathcal{T} = \{(x_i, y_i)\}_{i=1}^N

Matrix structure diagram illustrating data matrix X, feature vector x_j, sample row x_i, and target vector Y

Linear Regression Models

  • Formulation of the Linear Model:

    • Linear regression models form a foundational baseline for statistical learning.

Linear regression line fitted through scatter plot observations
  • Two-Feature Model Formulation:

    • Given an input dataset with p=2p = 2 features X=(X1,X2)X = (X_1, X_2), the model estimates scalar coefficients β^=(β^0,β^1,β^2)\hat{\beta} = (\hat{\beta}_0, \hat{\beta}_1, \hat{\beta}_2) to predict values:       y^i=β^0+β^1xi1+β^2xi2,where β^j,xij,y^i∈R\hat{y}_i = \hat{\beta}_0 + \hat{\beta}_1 x_{i1} + \hat{\beta}_2 x_{i2}, \quad \text{where } \hat{\beta}_j, x_{ij}, \hat{y}_i \in \mathbb{R}

  • Generalization to pp Features:

    • For an arbitrary number of features pp, the prediction formula for observation ii is:       y^i=β^0+∑j=1pβ^jxij,for i=1,…,N\hat{y}_i = \hat{\beta}_0 + \sum_{j=1}^p \hat{\beta}_j x_{ij}, \quad \text{for } i = 1, \dots, N

  • Generic Variable Form:

    • Dropping the specific observation index ii yields the generic equation over continuous input spaces:       Y^=β^0+∑j=1pXjβ^j,where β^j,Xj,Y^∈R\hat{Y} = \hat{\beta}_0 + \sum_{j=1}^p X_j \hat{\beta}_j, \quad \text{where } \hat{\beta}_j, X_j, \hat{Y} \in \mathbb{R}

    • Vectorized Representation and Bias Vector Augmentation:

  • Using explicit vector inner products, the equation simplifies to:     Y^=XTβ^+β^0,where X,β^∈Rp, and β^0,Y^∈R\hat{Y} = X^T \hat{\beta} + \hat{\beta}_0, \quad \text{where } X, \hat{\beta} \in \mathbb{R}^p, \text{ and } \hat{\beta}_0, \hat{Y} \in \mathbb{R}

  • Constant Augmentation Trick:

    • By appending a constant term 11 to the feature vector XX (making X∈Rp+1X \in \mathbb{R}^{p+1}), the intercept β^0\hat{\beta}_0 is seamlessly folded into the coefficient vector β^\hat{\beta}:       Y^=XTβ^\hat{Y} = X^T \hat{\beta}

    • This compact vector form simplifies underlying mathematics and mirrors exact computational implementations.

Matrix shape diagram for standard inner product plus scalar biasMatrix shape diagram showing parameter vector augmented with intercept bias
  • Python Computational Implementation:

    • Numerical linear algebra packages execute matrix operations efficiently via matrix multiplication operators or dot products:

import numpy as np

# X: shape (p,), beta_hat: shape (p,)
Y_hat = X.T @ beta_hat  # returns scalar
import numpy as np

# X: shape (p,), beta_hat: shape (p,)
Y_hat = np.dot(X.T, beta_hat)  # returns scalar
  • Extension to Multiple Outputs (KK-Vector Response):

    • When predicting KK distinct targets simultaneously (Y^∈RK\hat{Y} \in \mathbb{R}^K), the model expands to:     Y^=XTβ^,where β^∈Rp×K,X∈Rp,Y^∈RK\hat{Y} = X^T \hat{\beta}, \quad \text{where } \hat{\beta} \in \mathbb{R}^{p \times K}, X \in \mathbb{R}^p, \hat{Y} \in \mathbb{R}^K

    • Each individual output variable within Y^\hat{Y} requires its own dedicated set of pp parameter coefficients. Otherwise, identical predictions would be generated across all KK outputs.

Matrix dimensions for multivariate output model

Geometric Interpretation and Fitting of Linear Models

  • Geometric Interpretations:

    • One Feature (p=1p=1, Y^∈R\hat{Y} \in \mathbb{R}):

    • The system XTβ^=[x1][b^b^0]T=Y^X^T \hat{\beta} = [x \quad 1] [\hat{b} \quad \hat{b}_0]^T = \hat{Y} defines a straight line in two-dimensional space (X1,Y)(X_1, Y).

    • Two Features (p=2p=2, Y^∈R\hat{Y} \in \mathbb{R}):

    • The system forms a flat plane residing in three-dimensional space (X1,X2,Y)(X_1, X_2, Y).

    • General Case (pp Features, Y^∈R\hat{Y} \in \mathbb{R}):

    • The model produces a pp-dimensional hyperplane embedded within a (p+1)(p+1)-dimensional coordinate space.

    • Multiple Target Outputs (Y^∈RK\hat{Y} \in \mathbb{R}^K):

    • The overall space remains (p+1)(p+1)-dimensional, containing KK distinct hyperplanes. Each input instance xix_i maps to KK independent values across these planes.

  • Least Squares Fitting on Training Data:

    • Given a design matrix X∈RN×p\mathbf{X} \in \mathbb{R}^{N \times p} representing NN training observations, the prediction vector across all training instances is Y^=Xβ^\mathbf{\hat{Y}} = \mathbf{X} \hat{\beta}.

Matrix dimensions for batch sample prediction
  • The objective is finding optimal parameters β^\hat{\beta} making predicted outputs Y^\mathbf{\hat{Y}} as close to observed targets Y\mathbf{Y} as possible.

  • Residual Sum of Squares (RSS):     RSS(β)=∑i=1N(yi−xiTβ)2RSS(\beta) = \sum_{i=1}^N (y_i - x_i^T \beta)^2

  • The estimation process minimizing RSS is termed the method of least squares.

    • Analytical Derivation of the Least Squares Parameter Vector:

  • Express RSS in matrix-vector notation:      RSS(β)=∑i=1N(yi−xiTβ)2=∑i=1N(yi−y^i)2=(y−y^)T(y−y^)=(y−Xβ)T(y−Xβ)RSS(\beta) = \sum_{i=1}^N (y_i - x_i^T \beta)^2 = \sum_{i=1}^N (y_i - \hat{y}_i)^2 = (\mathbf{y} - \mathbf{\hat{y}})^T (\mathbf{y} - \mathbf{\hat{y}}) = (\mathbf{y} - \mathbf{X}\beta)^T (\mathbf{y} - \mathbf{X}\beta)

  • Differentiate RSS(β)RSS(\beta) with respect to vector β\beta and set derivative equal to zero:      dRSSdβ=XT(y−Xβ)=0\frac{dRSS}{d\beta} = \mathbf{X}^T (\mathbf{y} - \mathbf{X}\beta) = 0

  • Solve for β^\hat{\beta}:      XTy−XTXβ=0  ⟹  XTXβ=XTy  ⟹  β^=(XTX)−1XTy\mathbf{X}^T \mathbf{y} - \mathbf{X}^T \mathbf{X} \beta = 0 \implies \mathbf{X}^T \mathbf{X} \beta = \mathbf{X}^T \mathbf{y} \implies \hat{\beta} = (\mathbf{X}^T \mathbf{X})^{-1} \mathbf{X}^T \mathbf{y}

    • Classification via Linear Regression Thresholding:

  • Consider a dataset of 100 sample points with two feature dimensions X=(X1,X2)X = (X_1, X_2) and a binary qualitative outcome G∈{Blue,Orange}G \in \{\text{Blue}, \text{Orange}\}, encoded numerically as Blue = 0 and Orange = 1.

  • Fitting a linear regression model yields continuous estimates Y^\hat{Y}, which are transformed into categorical predictions G^\hat{G} using a threshold decision rule at 0.50.5:     G^={Orangeif Y^>0.5Blueif Y^≤0.5\hat{G} = \begin{cases} \text{Orange} & \text{if } \hat{Y} > 0.5 \\ \text{Blue} & \text{if } \hat{Y} \le 0.5 \end{cases}

  • The resulting decision boundary in feature space is linear, defined precisely by the line xTβ^=0.5x^T \hat{\beta} = 0.5

Linear regression classification boundary splitting blue and orange classes

Non-Linear Models: kk-Nearest Neighbor (kNNk\text{NN}) Methods

  • Core Principles:

    • Nearest-neighbor methods estimate output Y^\hat{Y} at target point xx by averaging response values of training observations located closest to xx in input feature space.

    • Formal Definition of kNNk\text{NN}:     Y^(x)=1k∑xi∈Nk(x)yi\hat{Y}(x) = \frac{1}{k} \sum_{x_i \in N_k(x)} y_i     where Nk(x)N_k(x) specifies the neighborhood surrounding point xx, defined by the kk nearest training instances xix_i

  • Classification Decision Rule:

    • Given threshold θ\theta (typically θ=0.5\theta = 0.5 for binary 0/10/1 outcomes):     g^(x)={Orangeif y^(x)>θBlueif y^(x)≤θ\hat{g}(x) = \begin{cases} \text{Orange} & \text{if } \hat{y}(x) > \theta \\ \text{Blue} & \text{if } \hat{y}(x) \le \theta \end{cases}

  • Distance Metric:

    • Closeness is evaluated using Euclidean distance standard metric:     EuD⁡(x1,x2)=∥x1−x2∥2=(∑j=1p(x1j−x2j)2)1/2\operatorname{EuD}(x_1, x_2) = \|x_1 - x_2\|_2 = \left( \sum_{j=1}^p (x_{1j} - x_{2j})^2 \right)^{1/2}

  • Behavior Under Different Values of kk:

    • 15-NN15\text{-NN} Classifier:

    • Determines class membership via majority vote across the 15 nearest neighboring points.

    • Generates a smooth, non-linear decision boundary.

Decision boundary formed by 15-nearest neighbor classification
  • 1-NN1\text{-NN} Classifier:

    • Sets prediction Y^\hat{Y} equal to the exact label yℓy_\ell of the single nearest point xℓx_\ell to xx

    • Creates a highly complex, non-linear decision boundary containing enclosed decision islands.

    • Training Error Rate: Exactly 0%0\% misclassifications on training data. Because every training sample instance xix_i is its own closest neighbor (xi∈N1(xi)x_i \in N_1(x_i)), the model evaluates y^(xi)=yi\hat{y}(x_i) = y_i, yielding zero prediction errors during training.

Extremely complex non-linear decision boundary formed by 1-nearest neighbor classification

Comparison: Linear vs. Non-Linear (kNNk\text{NN}) Models

  • Model Flexibility, Complexity, and Trade-offs:

    • Linear Model Properties:

    • Makes higher misclassifications on non-linearly structured training data.

    • Highly rigid parameterization. Represented compactly by only p+1p+1 scalar values (parameters β∈Rp+1\beta \in \mathbb{R}^{p+1}).

    • Low model complexity yields strong stability and low variance when evaluating unseen test data.

    • 1-NN1\text{-NN} Model Properties:

    • Perfectly classifies training data ($0\% error rate).\n - Controlled by a single global hyperparameter k \in \mathbb{N},butstructurallyreliesoncalculatinglocalneighborhoodaveragesacross, but structurally relies on calculating local neighborhood averages across\frac{N}{k} local regions.\n - Extremely fragile and highly sensitive to training data noise (high variance), leading to severe overfitting on new data points.\n\n- **Synthetic Data Benchmark Setup**:\n - Synthetic simulation demonstrating non-linear cluster overlap:\n - Total sample size: 200 observations (100 Blue, 100 Orange).\n - Blue class centers: 10 mean vectors m_kgeneratedfrombivariateGaussiandistributiongenerated from bivariate Gaussian distribution\mathcal{N}\left( (1,0)^T, \mathbf{I} \right).\n - Orange class centers: 10 mean vectors m_k generated from bivariate Gaussian distribution $ NORTH \mathcal{N}\left( (0,1)^T, \mathbf{I} \right).

    • Individual sample generation: Select cluster mean mkm_k uniformly at random with probability 0.10.1, then sample data point from N(mk,I5)\mathcal{N}\left( m_k, \frac{\mathbf{I}}{5} \right).

    • This generative process produces overlapping multi-modal clusters that linear decision boundaries cannot separate cleanly.

Statistical Decision Theory Framework

  • Theoretical Framework Principles:

    • Let X∈RpX \in \mathbb{R}^p denote a real-valued random input vector, and Y∈RY \in \mathbb{R} represent a real-valued target random variable, governed by joint probability distribution Pr⁡(X,Y)\operatorname{Pr}(X, Y).

    • The goal is finding a prediction function f(X)f(X) mapping inputs to predicted targets YY

    • Loss Function:

    • Quantifies penalization incurred by prediction errors. Using squared error loss:       L(Y,f(X))=(Y−f(X))2L(Y, f(X)) = (Y - f(X))^2

  • Mathematical Foundations of Expectation:

    • Expectation of continuous variable XX: E(X)=∫xxPr⁡(x)dx=∫xxPr⁡(dx)E(X) = \int_x x \operatorname{Pr}(x) dx = \int_x x \operatorname{Pr}(dx)

    • Expectation of function g(X,Y)g(X, Y):

    • Discrete: E(g(X,Y))=∑x∑yg(x,y)Pr⁡(x,y)E(g(X, Y)) = \sum_x \sum_y g(x, y) \operatorname{Pr}(x, y)

    • Continuous: E(g(X,Y))=∫x∫yg(x,y)Pr⁡(x,y)dxdyE(g(X, Y)) = \int_x \int_y g(x, y) \operatorname{Pr}(x, y) dx dy

    • In decision theory, the evaluated function is squared loss g(X,Y)=(Y−f(X))2g(X, Y) = (Y - f(X))^2

  • Expected Prediction Error (EPE):

    • Objective criterion for selecting optimal function ff:     EPE(f)=E[(Y−f(X))2]=∫x∫y(y−f(x))2Pr⁡(x,y)dxdy=∫(y−f(x))2Pr⁡(dx,dy)EPE(f) = E\left[ (Y - f(X))^2 \right] = \int_x \int_y (y - f(x))^2 \operatorname{Pr}(x, y) dx dy = \int (y - f(x))^2 \operatorname{Pr}(dx, dy)

    • Applying conditional probability factorization Pr⁡(X,Y)=Pr⁡(Y∣X)Pr⁡(X)\operatorname{Pr}(X, Y) = \operatorname{Pr}(Y|X) \operatorname{Pr}(X), EPE rewrites as:     EPE(f)=EXEY∣X[(Y−f(X))2∣X]EPE(f) = E_X E_{Y|X} \left[ (Y - f(X))^2 \mid X \right]

    • The inner expectation EY∣XE_{Y|X} calculates expected squared error over all outcomes conditional on a specific input XX. The outer expectation EXE_X averages these errors across input space Rp\mathbb{R}^p

  • Pointwise Minimization and the Regression Function:

    • To minimize total EPE(f)EPE(f), it suffices to minimize expected error conditional on every individual input value X=xX = x:     f(x)=argmin⁡cEY∣X[(Y−c)2∣X=x]f(x) = \operatorname{argmin}_c E_{Y|X} \left[ (Y - c)^2 \mid X = x \right]     where cc represents a fixed predicted scalar value.

    • The condition X=xX = x does not isolate a single training instance; rather, it refers to all possible population instances sharing feature values xx. For a given xx, target YY remains a random variable.

    • The theoretical minimizer cc of expected squared error E(Y−c)2E(Y - c)^2 is the conditional expectation c=E(Y)c = E(Y). Thus, the optimal theoretical target solution is:     f(x)=EY∣X(Y∣X=x)f(x) = E_{Y|X}(Y \mid X = x)     which is formally termed the regression function.

3D density distribution visualization illustrating conditional expected squared error minimization
  • Conceptual Application (Real Estate Evaluation):

    • Consider predicting home values YY using features X1X_1 (bedroom count), X2X_2 (square footage), and X3X_3 (neighborhood quality rating).

    • The regression function f(x)=EY∣X(Y∣X=x)f(x) = E_{Y|X}(Y \mid X = x) does not represent the average price of a single home, nor does it mean average price across the full housing market.

    • It equals the population average price across all homes possessing identical features x=(x1,x2,x3)x = (x_1, x_2, x_3).

  • Theoretical Target vs. Empirical Reality:

    • In practical applications, the true joint probability distribution Pr⁡(X,Y)\operatorname{Pr}(X, Y) is unknown.

    • Continuous input features mean exact feature matches X=xX = x appear at most once in finite datasets. Evaluating empirical expectations over a single observation yields no smoothing capability.

    • Parametric and non-parametric models represent practical computational attempts to estimate f^(x)≈E(Y∣X=x)\hat{f}(x) \approx E(Y \mid X = x) using finite data.

  • Model Alignment with Decision Theory:

    • Linear Regression: Assumes f(x)f(x) is approximated by a global linear structure f(x)≈xTβf(x) \approx x^T \beta. Solves β\beta by substituting this structure into the theoretical EPE equation.

    • k-Nearest Neighborsk\text{-Nearest Neighbors}: Relaxes conditioning at an exact point X=xX = x to conditioning over a localized neighborhood region Nk(x)N_k(x), replacing theoretical population expectations with sample arithmetic averages:     f^(x)=Ave⁡(yi∣xi∈Nk(x))\hat{f}(x) = \operatorname{Ave}\left( y_i \mid x_i \in N_k(x) \right)     Assumes f(x)f(x) is approximated locally by a constant function.

  • Asymptotic Convergence of kNNk\text{NN}:

    • As sample size N→∞N \to \infty and neighborhood size k→∞k \to \infty such that kN→0\frac{k}{N} \to 0:     f^(x)→convrgE(Y∣X=x)\hat{f}(x) \xrightarrow{\text{convrg}} E(Y \mid X = x)

    • Under asymptotic infinite sample conditions, kNNk\text{NN} operates as a universal function approximator.

Decision Theory for Categorical Outputs (Classification & Bayes Classifier)

  • Decision Theory Formulation for Classification:

    • Let target class labels belong to finite categorical set G={G1,G2,…,GK}\mathcal{G} = \{G_1, G_2, \dots, G_K\} with set size ∣G∣=K|\mathcal{G}| = K. Prediction model G^(X)\hat{G}(X) outputs labels in G\mathcal{G}.

    • Loss Matrix L\mathbf{L}:

    • Costs are specified by a K×KK \times K matrix L∈R≥0K×K\mathbf{L} \in \mathbb{R}_{\ge 0}^{K \times K}, where entry L(k,ℓ)L(k, \ell) defines the loss incurred by classifying an observation belonging to true class GkG_k as predicted class GℓG_\ell

    • Correct classifications along the matrix diagonal incur zero cost (L(k,k)=0L(k, k) = 0).

Loss function matrix structure mapping actual class rows against predicted class columns
  • 0-1 Loss Function:

    • The standard classification loss penalizes every misclassification with a unit cost of 1:     L[Gk,G^(X)]={1if Gk≠G^(X)0if Gk=G^(X)L[G_k, \hat{G}(X)] = \begin{cases} 1 & \text{if } G_k \neq \hat{G}(X) \\ 0 & \text{if } G_k = \hat{G}(X) \end{cases}

  • Categorical Expected Prediction Error:

    • Integrating misclassification loss over joint distribution Pr⁡(G,X)\operatorname{Pr}(G, X) yields:     EPE=E[L(G,G^(X))]=EX∑k=1KL[Gk,G^(X)]Pr⁡(Gk∣X)EPE = E\left[ L(G, \hat{G}(X)) \right] = E_X \sum_{k=1}^K L\left[ G_k, \hat{G}(X) \right] \operatorname{Pr}(G_k \mid X)

    • Pointwise minimization at specific feature vector X=xX = x requires:     G^(x)=argmin⁡g∈G∑k=1KL[Gk,g]Pr⁡(Gk∣X=x)\hat{G}(x) = \operatorname{argmin}_{g \in \mathcal{G}} \sum_{k=1}^K L[G_k, g] \operatorname{Pr}(G_k \mid X = x)

  • Derivation of the Bayes Classifier Under 0-1 Loss:

    1. Substituting 0-1 loss simplifies the summation:      ∑k=1KL[Gk,g]Pr⁡(Gk∣X=x)=∑k≠gPr⁡(Gk∣X=x)=1−Pr⁡(g∣X=x)\sum_{k=1}^K L[G_k, g] \operatorname{Pr}(G_k \mid X = x) = \sum_{k \neq g} \operatorname{Pr}(G_k \mid X = x) = 1 - \operatorname{Pr}(g \mid X = x)

    2. Minimizing misclassification cost simplifies directly to maximizing class probability:      \hat{G}(x) = \operatorname{argmin}_{g \in \mathcal{G}} \left[ 1 - \operatorname{Pr}(g \mid X = x) \right] = \operatorname{argmax}_{g \in \mathcal{G}} \operatorname{Pr}(g \n\mid X = x)

    • Bayes Optimal Decision Rule:     G^(x)=Gkif Pr⁡(Gk∣X=x)=max⁡g∈GPr⁡(g∣X=x)\hat{G}(x) = G_k \quad \text{if } \operatorname{Pr}(G_k \mid X = x) = \max_{g \in \mathcal{G}} \operatorname{Pr}(g \mid X = x)

    • The strategy assigning observations to the most probable class conditional on X=xX = x is termed the Bayes classifier. The minimal error rate achieved by this optimal boundary is the Bayes rate.

    • kNNk\text{NN} classification directly approximates the Bayes classifier by replacing exact conditional class probabilities Pr⁡(Gk∣X=x)\operatorname{Pr}(G_k \mid X = x) with empirical training class frequencies inside local neighborhood Nk(x)N_k(x).

Bayes optimal decision boundary separating overlapping class distributions

The Curse of Dimensionality in Local Methods

  • Breakdown of Local Methods in High Dimensions:

    • Although asymptotic convergence f^(x)→E(Y∣X=x)\hat{f}(x) \to E(Y \mid X = x) holds theoretically as N,k→∞N, k \to \infty, high feature dimensionality (p≫1p \gg 1) degrades performance drastically. This phenomenon is known as the curse of dimensionality.

  • Geometric Distortion 1: Loss of Neighborhood Locality:

    • Assume pp input variables are uniformly distributed within a unit hypercube [0,1]p[0, 1]^p.

    • Consider a sub-cube neighborhood capturing a fractional proportion rr of total sample volume. The required edge length ep(r)e_p(r) of this sub-cube is:     ep(r)=r1/pe_p(r) = r^{1/p}

    • Evaluating required edge lengths to capture a small 10%10\% volume fraction (r=0.1r = 0.1) across dimensions:

    • p=1  ⟹  e1(0.1)=0.10p = 1 \implies e_1(0.1) = 0.10 ($10\% of feature range)\n - p = 2 \implies e_2(0.1) = 0.32\n - p = 3 \implies e_3(0.1) = 0.46 ($46\% of feature range)

    • p=4  ⟹  e4(0.1)=0.56p = 4 \implies e_4(0.1) = 0.56

    • p=5  ⟹  e5(0.1)=0.63p = 5 \implies e_5(0.1) = 0.63

    • p=6  ⟹  e6(0.1)=0.68p = 6 \implies e_6(0.1) = 0.68

    • p=10  ⟹  e10(0.1)=0.80p = 10 \implies e_{10}(0.1) = 0.80 ($80\% of feature range)\n - **Implication**: To collect even 10\%ofdatainstancesin10−dimensionalspace,theneighborhoodmustspanof data instances in 10-dimensional space, the neighborhood must span80\% of the full coordinate range along every input dimension. Consequently, neighborhoods cease being local, invalidating local constant assumptions.\n\n![Unit hypercube sub-volume neighborhood visualization](https://assets.knowt.com/pdf-flow-prod/898d163c-213f-43b9-bd24-1380f7e40474-figures/18.png)\n\n![Edge length growth curves required to capture fixed sample fractions across increasing dimensions](https://assets.knowt.com/pdf-flow-prod/898d163c-213f-43b9-bd24-1380f7e40474-figures/19.png)\n\n- **Geometric Distortion 2: Vanishing Inscribed Spherical Volume**:\n - Consider a hypersphere S_pinscribedwithinaunithypercubeinscribed within a unit hypercubeC_pacrossacrossp dimensions.\n - The ratio of hypersphere volume to hypercube volume approaches zero rapidly as dimension increases:\n    \lim_{p \to \infty} \frac{\text{Vol}(S_p)}{\text{Vol}(C_p)} = 0\n - **Implication**: As feature dimensions grow, uniformly distributed sample mass concentrates almost entirely in the corners of the bounding hypercube. Data points become sparse and isolated near domain boundaries. Nearest neighbor estimation converts from local interpolation to unreliable boundary extrapolation.\n\n![Volume ratio curve showing exponential decay of inscribed hypersphere volume relative to hypercube volume](https://assets.knowt.com/pdf-flow-prod/898d163c-213f-43b9-bd24-1380f7e40474-figures/20.png)\n\n# Supervised Learning as Function Approximation\n\n- **Additive Error Statistical Models**:\n - Quantitative response data are modeled assuming an underlying statistical structure:\n    Y = f(X) + \varepsilon\n    where systematic function f(X) = E(Y \mid X)isperturbedbyrandomstochasticerroris perturbed by random stochastic error\varepsilonsatisfyingsatisfyingE(\varepsilon) = 0\n - Unexplained variance \varepsilon reflects unobserved input features or inherent stochastic system variability.\n - Non-deterministic systems allow multiple distinct target outputs Ytooccurforanidenticalfeatureinstanceto occur for an identical feature instanceX = x\n\n- **Categorical Response Surface Modeling**:\n - Additive error formulations cannot represent qualitative targets (e.g., adding numerical noise to categorical text labels is undefined).\n - Instead, categorical responses are modeled by approximating conditional class probability distributions p(x) = \operatorname{Pr}(G \mid X = x).\n - For binary outcome coding (0/1),conditionalprobabilitiesmapbacktoexpectedconditionaltargetvalues), conditional probabilities map back to expected conditional target valuesp(x) = E(Y \mid X = x).\n\n![Probabilistic density distributions separated across binary class values](https://assets.knowt.com/pdf-flow-prod/898d163c-213f-43b9-bd24-1380f7e40474-figures/21.png)\n\n- **Supervised Function Approximation Framework**:\n - Learning algorithm parameterize approximators f_\theta(x)usingparametervectorusing parameter vector\theta.\n - **Linear Basis Expansion Models**:\n - A flexible class of approximators expands functions as weighted sums of basis functions h_k(x):\n      f_\theta(x) = \sum_{k=1}^K h_k(x) \theta_k\n - Basis choice dictates model architecture:\n - h_k(x) = x_k \implies Standard Linear Model\n - h_k(x) = x_k^m \implies Polynomial Surface Model\n - h_k(x) = \operatorname{ReLU}(w_k^T x + b_k) \implies Rectified Linear Neural Network\n - h_k(x) = \frac{1}{1 + \exp(-x^T \beta_k)} \implies Sigmoidal Neural Network\n\n![Surface fitting visualization approximating sample points in three-dimensional space](https://assets.knowt.com/pdf-flow-prod/898d163c-213f-43b9-bd24-1380f7e40474-figures/22.png)\n\n- **Maximum Likelihood Estimation (MLE)**:\n - Parameters \thetaareestimatedbymaximizinglog−likelihoodoverare estimated by maximizing log-likelihood overN independent samples:\n    L(\theta) = \sum_{i=1}^N \log \operatorname{Pr}\theta(y_i)\n - Log-probabilities \log \operatorname{Pr}\theta(y_i)lieonlie on(-\infty, 0].Maximizing. MaximizingL(\theta) selects parameters under which observed training data exhibits maximum occurrence probability.\n\n![Logarithm density curve illustrating log-likelihood values](https://assets.knowt.com/pdf-flow-prod/898d163c-213f-43b9-bd24-1380f7e40474-figures/23.png)\n\n- **Equivalence of Least Squares and Maximum Likelihood**:\n - Assume additive error follows independent Gaussian noise \varepsilon \sim \mathcal{N}(0, \sigma^2), giving conditional likelihood:\n    \operatorname{Pr}(Y \mid X, \theta) = \mathcal{N}\left( f_\theta(X), \sigma^2 \right)\n - The conditional log-likelihood equation expands as:\n    L(\theta) = C - \frac{1}{2\sigma^2} \sum_{i=1}^N \left( y_i - f_\theta(x_i) \right)^2\n - Maximizing log-likelihood L(\theta)withrespecttowith respect to\thetaismathematicallyequivalenttominimizingResidualSumofSquaresis mathematically equivalent to minimizing Residual Sum of SquaresRSS(\theta) = \sum_{i=1}^N (y_i - f_\theta(x_i))^2$$