06: Non-linear Models

90-Minute Main Lesson: When Does Nonlinearity Earn Its Cost?

  • Objectives： Compare piecewise, QDA, and kernel models; calculate a QDA score including prior and determinant terms; inspect a Gram matrix; distinguish a final test comparison from training-period validation used to choose model complexity.

  • learning path:

    • prerequisite and linear failure 15 min → QDA 25 min → kernel trick 20 min → Fuyao Glass main case 20 min → held-out-check boundary check 10 min.

    • KPCA/KSVM derivations are extensions.

  • Answer first： If class means are equal but covariances differ, which method can use the difference, LDA or QDA?

  • Feedback： QDA, because it estimates \(\Sigma_k\) for each class; the price is more parameters and higher variance.

The Core Question of This Chapter

What should we do when the real world isn’t linear?

Most of our studies so far have focused on linear models, which are the cornerstones of econometrics and machine learning.

However, economic and financial relationships in the real world are often complex and non-linear.

The Limitations of Linear Models: An Intuitive Example

Suppose we use linear regression to fit a dataset that clearly has a curved relationship.

Limitation of Linear Models A scatter plot of points following a parabolic curve, with a poorly fitting straight line from a linear regression model drawn through them. The errors are highlighted. Linear Model vs. Non-linear Data X Y Underestimated at ends Overestimated in middle

Observation: The model systematically underestimates at both ends and overestimates in the middle. The Mean Squared Error (MSE) is high.

Non-linear Relationships in the Real World

  • Credit Default Risk:

    • The relationship between income and default rate may not be linear.

    • Both very low and very high-income individuals might have low risk, while middle-income groups could have higher risk due to over-leveraging.

  • Asset Returns: An asset’s relationship with market factors (its Beta) might change with market volatility, exhibiting non-linearity.
  • Consumer Behavior: The effect of price discounts on sales volume diminishes over time, following a saturation curve rather than a straight line.

Our Journey of Discovery: Three Non-linear Paths

In this chapter, we will systematically learn three powerful classes of non-linear models to overcome the limitations of linear ones.

Roadmap for Exploring Non-linear Models A roadmap showing three learning paths for non-linear models: Piecewise Linear, Quadratic Discriminant Analysis (QDA), and Kernel Methods. Start Linear Models 1. Piecewise Linear Approximatewith lines 2. QDA Directly fit a curve 3. Kernel Trick Lift dimension;linear separator

Part 1: Piecewise Linear Discriminant

Piecewise Linear Discriminant: The ‘Brute Force’ Approach

Core Idea

If one straight line doesn’t work, let’s use multiple straight lines to piece together an approximation.

. . .

This strategy typically involves two steps:

  1. Subclass Partitioning: Further divide one of the original classes (e.g., the blue dots) into multiple subclasses, such that each subclass is linearly separable from the other classes.
  2. Class Merging: When making the final prediction, merge the results from all subclasses that belong to the same original parent class.

Geometric Intuition (1/3): The Initial Problem

First, we have a dataset that cannot be separated by a single straight line.

Initial Non-linear Classification Problem A typical dataset that cannot be perfectly separated by a linear model, where purple and blue dots are arranged in a moon shape. Customer Metric 1 Customer Metric 2 At Risk (0) Good Credit (1)

Geometric Intuition (2/3): Partition and Conquer

We imagine the ‘Good Credit’ (blue) customer group as two potential subgroups. Then we use two different lines to separate them.

  • Line 1: Separates the purple group and the blue ‘bottom-left’ subgroup.
  • Line 2: Separates the purple group and the blue ‘top-right’ subgroup.
Piecewise Linear Discriminant Idea The purple and blue point sets are separated by two independent red and orange dashed lines. Line 1 Line 2

Geometric Intuition (3/3): The Final Boundary

The final decision boundary is a ‘V’ shape, formed by combining parts of these two lines.

The Final Piecewise Linear Boundary Parts of two straight lines form a V-shape that separates the data points. Final Boundary

Pros and Cons of Piecewise Linear Discriminant

Pros Cons
Simple idea, easy to understand How to partition subclasses is a key challenge
Can leverage existing linear model algorithms Number of subclasses is a hyperparameter
Can fit any complex shape with enough segments Prone to overfitting
Conceptually similar to models like decision trees Lacks ‘holistic’ model elegance

Conclusion: Piecewise linear discriminant is an effective ‘heuristic’ method, but in practice, we often seek more systematic and elegant solutions.

Part 2: Quadratic Discriminant Analysis (QDA)

QDA: Directly Fitting the Curve

Quadratic Discriminant Analysis (QDA) doesn’t piece together lines; it directly constructs a quadratic decision boundary.

For our moon-shaped data, an elegant parabola can perform the classification task very well.

QDA's Quadratic Boundary A red parabola elegantly separates the purple and blue data points. Quadratic Decision Boundary

The Form of the QDA Discriminant Function

The QDA discriminant function \(f(\mathbf{x}_n)\) is a quadratic function of the input vector \(\mathbf{x}_n\):

\[ \large{ f(\mathbf{x}_n, \mathbf{W}, \mathbf{w}, b) = \mathbf{x}_n^T \mathbf{W} \mathbf{x}_n + \mathbf{w}^T \mathbf{x}_n + b } \]

  • \(\mathbf{x}_n \in \mathbb{R}^d\): a d-dimensional feature vector.
  • \(\mathbf{W} \in \mathbb{R}^{d \times d}\): The quadratic term coefficient matrix, which ‘bends’ the decision boundary.
  • \(\mathbf{w} \in \mathbb{R}^d\): The linear term coefficient vector, which ‘shifts’ the decision boundary.
  • \(b \in \mathbb{R}\): The bias term.

The Core of QDA: The Quadratic Term Matrix \(\mathbf{W}\)

In the discriminant function, the term that gives QDA its non-linear power is the quadratic term \(\mathbf{x}_n^T \mathbf{W} \mathbf{x}_n\).

  • If \(\mathbf{W} = \mathbf{0}\), QDA degenerates into the familiar Linear Discriminant Analysis (LDA). The decision boundary is linear.
  • If \(\mathbf{W} \neq \mathbf{0}\), the decision boundary \(f(\mathbf{x}_n) = 0\) is a quadratic surface (in 2D space, this is a conic section like an ellipse, parabola, or hyperbola).

The Geometric Meaning of \(\mathbf{W}\): It Shapes the Boundary

Different \(\mathbf{W}\) matrices can generate various shapes of quadratic surface boundaries.

The W Matrix Determines the Boundary Shape Three subplots showing decision boundaries in the shapes of an ellipse, a parabola, and a hyperbola. Possible Boundary Shapes from QDA Ellipse Parabola Hyperbola

The ‘Cost’ of QDA: An Explosion in Parameters

This flexibility comes at a cost. Let’s count the number of parameters in the model:

  • Matrix \(\mathbf{W}\): Since \(\mathbf{W}\) can be assumed to be symmetric, it has \(d(d+1)/2\) independent parameters.
  • Vector \(\mathbf{w}\): Has \(d\) parameters.
  • Scalar \(b\): Has \(1\) parameter.

The total number of parameters is \(\frac{d(d+1)}{2} + d + 1\), which is on the order of \(O(d^2)\).

Consequences of Parameter Explosion

Feature Dimension (d) QDA Parameter Count (approx. d²/2)
2 6
10 66
50 1,326
100 5,151
1000 ~500,000

This leads to two serious practical problems:

  1. Huge Computational Load: Solving a model with \(d^2\)-level parameters is very time-consuming.
  2. Large Sample Size Requirement: To robustly estimate so many parameters, a very large sample size is needed, otherwise, the model is highly prone to overfitting.

Understanding QDA from a Probabilistic View: A More Practical Path

In practice, we don’t directly fit that massive \(\mathbf{W}\) matrix. Instead, we derive QDA through the lens of a probabilistic generative model.

Core Assumption: We assume that the data for each class \(k\) follows a Multivariate Gaussian Distribution.

\[ \large{ p(\mathbf{x} | y=k) = \mathcal{N}(\mathbf{x} | \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k) } \]

  • \(\boldsymbol{\mu}_k\): The mean vector for class \(k\) (the center of the distribution).
  • \(\boldsymbol{\Sigma}_k\): The covariance matrix for class \(k\) (the shape and orientation of the distribution).

The Key Difference Between QDA and LDA: The Covariance Matrix

Both QDA and LDA assume the data follows a Gaussian distribution, but they differ in their assumptions about the covariance matrix.

  • LDA (Linear Discriminant Analysis): Assumes that the covariance matrices for all classes are the same. \(\boldsymbol{\Sigma}_1 = \boldsymbol{\Sigma}_2 = \dots = \boldsymbol{\Sigma}_K = \boldsymbol{\Sigma}\) This strong assumption leads to a linear decision boundary.

  • QDA (Quadratic Discriminant Analysis): Allows each class to have its own distinct covariance matrix. \(\boldsymbol{\Sigma}_i \neq \boldsymbol{\Sigma}_j\) for \(i \neq j\) This more flexible assumption is precisely the source of the quadratic decision boundary.

Visual Comparison: Assumptions of LDA vs. QDA

LDA vs. QDA Assumptions A side-by-side comparison. LDA shows two parallel ellipses with a linear boundary. QDA shows two differently shaped ellipses with a curved boundary. LDA Shared covariance Σ₁ = Σ₂ Shared shape → linear QDA Separate covariances Σ₁ ≠ Σ₂ Different shapes → quadratic

Derivation of the QDA Discriminant Function

  • Using Bayes’ theorem, the posterior probability is \(P(y=k|\mathbf{x}) \propto p(\mathbf{x}|y=k) P(y=k)\).

  • By taking the logarithm and expanding the PDF of the Gaussian distribution, we get the discriminant function (ignoring constant terms):

\[ \large{ \delta_k(\mathbf{x}) = -\frac{1}{2} \log |\boldsymbol{\Sigma}_k| - \frac{1}{2} (\mathbf{x} - \boldsymbol{\mu}_k)^T \boldsymbol{\Sigma}_k^{-1} (\mathbf{x} - \boldsymbol{\mu}_k) + \log \pi_k } \]

This is a quadratic function of \(\mathbf{x}\)! The quadratic term comes from \(\mathbf{x}^T \boldsymbol{\Sigma}_k^{-1} \mathbf{x}\).

What is Mahalanobis Distance?

The core of the QDA discriminant function is the squared Mahalanobis distance:

\[ \large{ D_M^2(\mathbf{x}, \boldsymbol{\mu}_k) = (\mathbf{x} - \boldsymbol{\mu}_k)^T \boldsymbol{\Sigma}_k^{-1} (\mathbf{x} - \boldsymbol{\mu}_k) } \]

  • Intuitive Understanding: It measures the ‘statistical distance’ from a point \(\mathbf{x}\) to the center of a distribution \(\boldsymbol{\mu}_k\).
  • It takes into account the covariance structure \(\boldsymbol{\Sigma}_k\) of the data itself. If the data varies greatly in a certain direction (high variance), distances in that direction are ‘shrunk’.
  • QDA does not compare Mahalanobis distance alone; it also includes the class-volume penalty \(-\tfrac12\log|\Sigma_k|\) and prior term \(\log\pi_k\).

Euclidean vs. Mahalanobis Distance

Intuition vs. Form: Understanding Mahalanobis Distance A diagram comparing Euclidean and Mahalanobis distance. It shows two points A and B that are equidistant from the mean in Euclidean terms, but B is a statistical outlier according to Mahalanobis distance which considers the data's covariance. Euclidean vs. Mahalanobis Distance A and B tie in Euclidean distance 1σ2σ3σ μ A B Euclidean · raw scale Mahalanobis · scaled

Conclusion: Point A lies along the ‘major axis’ of the data distribution. Although its Euclidean distance is large, it is statistically ‘closer’.

QDA Decision Rule

For a two-class problem (classes \(\omega_1, \omega_2\)), we can define a discriminant function \(f_i(\mathbf{x})\):

\[ \large{ f_i(\mathbf{x}) = \log\pi_i - \frac{1}{2}\log|\boldsymbol{\Sigma}_i| - \frac{1}{2}(\mathbf{x} - \boldsymbol{\mu}_i)^T \boldsymbol{\Sigma}_i^{-1} (\mathbf{x} - \boldsymbol{\mu}_i) } \]

Decision Rule:

  • If \(f_1(\mathbf{x}) \geq f_2(\mathbf{x})\), predict class \(\omega_1\).
  • Otherwise, predict class \(\omega_2\).

Since each class’s \(f_i(\mathbf{x})\) has its own covariance matrix \(\boldsymbol{\Sigma}_i\), the decision boundary \(f_1(\mathbf{x}) = f_2(\mathbf{x})\) is a quadratic function.

QDA Summary: When Should You Use It?

  • When to Use:

    • QDA is a great choice when you believe that data from different classes have different covariance structures.

    • It offers a good balance between LDA and more complex non-parametric methods (like K-Nearest Neighbors).

  • Advantages: The model form is explicit, and it’s less computationally expensive than many non-linear methods (like kernel SVM).
  • Disadvantages: It relies on a strong assumption of Gaussian distribution. When the feature dimension \(d\) is high, the number of parameters becomes very large, requiring substantial data to avoid overfitting and increasing computational cost.

Part 3: The Kernel Trick

The Kernel Method: A ‘Game-Changing’ Idea

While QDA is effective, it is limited to quadratic functions. What if we want to fit more complex boundaries?

The Kernel Method provides an extremely elegant and powerful idea:

Instead of learning a complex non-linear model in the original low-dimensional space, we map the data via a non-linear function \(\phi(\mathbf{x})\) to a higher-dimensional ‘feature space’ and then learn a simple linear model in that high-dimensional space.

This idea, often called the ‘Kernel Trick’, is a cornerstone of modern machine learning.

Core Intuition: Lifting the Dimension (1/3)

Imagine some data points in a one-dimensional space that cannot be separated by a single ‘point’ (a 0-dimensional hyperplane).

One-dimensional Linearly Inseparable Data A line with two colors of dots distributed on it, which cannot be separated by a single point. x Problem: Cannot separate blue and purple with a single point.

Core Intuition: Lifting the Dimension (2/3)

We define a simple non-linear mapping \(\phi(x) = (x, x^2)\), which maps the one-dimensional data point \(x\) into a two-dimensional space.

Mapping from 1D to 2D Shows the process of mapping x to (x, x^2), lifting the points onto a parabola. x² x Map: φ(x) = (x, x²)

Core Intuition: Lifting the Dimension (3/3)

A miracle happens! In this new 2D space, the data points become separable by a straight line.

Linear Separability in 2D Space The previously inseparable points become separable by a red line after being mapped to 2D. x² x Now, the data is linearly separable!

Complete Flowchart of the Kernel Method

The Kernel Trick Flowchart A diagram illustrating how non-linearly separable data in an input space becomes linearly separable in a higher-dimensional feature space via a mapping function phi(x). The Kernel Method (Kernel Trick) 1. Input Space Non-linearly Separable φ(x) 2. Feature Space Linearly Separable

The New Home After Mapping: Hilbert Space

  • The high-dimensional space where the mapping \(\phi(\mathbf{x})\) leads is mathematically known as a feature space.

  • For our mathematical tools (like distance, angle) to work properly, we require this space to be a Hilbert Space.

For economics students, you don’t need to delve into its rigorous mathematical definition. You can understand it intuitively as:

A Hilbert space is a well-behaved, possibly infinite-dimensional generalization of Euclidean space.

Here, we can confidently compute lengths, distances, and angles, just as in ordinary space.

Key Property of Hilbert Space: The Inner Product

The most important property of a Hilbert space is that it defines an Inner Product, denoted as \(\langle \cdot, \cdot \rangle_{\mathcal{H}}\).

The inner product is a generalization of the familiar dot product:

\[ \begin{aligned} \langle \mathbf{x}_1, \mathbf{x}_2 \rangle &= \mathbf{x}_1^T \mathbf{x}_2 \\ &= \sum_{i=1}^d x_{1,i}x_{2,i}. \end{aligned} \]

With an inner product, we can define Norm (length) and Distance, just as in Euclidean space. The inner product also contains information about the angle between vectors, allowing us to measure similarity.

\[ \langle \mathbf{x}_1, \mathbf{x}_2 \rangle = \lVert\mathbf{x}_1\rVert\,\lVert\mathbf{x}_2\rVert\cos\theta \]

The ‘Magic’ of the Kernel Trick

Recall that the final computations of many linear algorithms (like SVM, PCA, linear regression) can be expressed solely in terms of the inner products of sample points, \(\langle \mathbf{x}_i, \mathbf{x}_j \rangle\).

  • After mapping: compute similarity in feature space rather than input space.

\[ \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j) \rangle_{\mathcal{H}} \]

The Problem:

  1. The mapping function \(\phi(\mathbf{x})\) can be very complex, and we might not even know its explicit form.
  2. The high-dimensional space could have a very high, or even infinite, dimension, making a direct computation of the inner product impossible.

The Kernel Function: A Shortcut to High Dimensions

The Kernel Function \(K(\mathbf{x}_i, \mathbf{x}_j)\) is defined to solve this very problem:

A function \(K(\mathbf{x}_i, \mathbf{x}_j)\) is a kernel function if it can be written as the inner product of some mapping \(\phi\) in a high-dimensional space, i.e., \(K(\mathbf{x}_i, \mathbf{x}_j) = \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j) \rangle_{\mathcal{H}}\).

The essence of the kernel trick

  • We can compute \(K(\mathbf{x}_i, \mathbf{x}_j)\) directly without explicitly constructing the high-dimensional coordinates \(\phi(\mathbf{x})\).

  • This avoids the computational and storage cost of an explicit feature map; it does not remove statistical dimensionality, sample-complexity, or overfitting problems.

Example: A Simple Quadratic Kernel

Suppose our original data is two-dimensional: \(\mathbf{x} = (x_1, x_2)\). Consider a simple kernel function: \(K(\mathbf{x}_i, \mathbf{x}_j) = (\mathbf{x}_i^T \mathbf{x}_j)^2\).

Let’s expand it:

\[ \begin{aligned} \large{ K(\mathbf{x}_i, \mathbf{x}_j) } &= \large{ (x_{i1}x_{j1} + x_{i2}x_{j2})^2 } \\ &= \large{ x_{i1}^2x_{j1}^2 + x_{i2}^2x_{j2}^2 + 2x_{i1}x_{j1}x_{i2}x_{j2} } \\ &= \large{ \langle (x_{i1}^2, x_{i2}^2, \sqrt{2}x_{i1}x_{i2}), (x_{j1}^2, x_{j2}^2, \sqrt{2}x_{j1}x_{j2}) \rangle } \end{aligned} \]

This shows that this simple kernel implicitly corresponds to a mapping from 2D to 3D: \(\phi(\mathbf{x}) = (x_1^2, x_2^2, \sqrt{2}x_1x_2)\).

  • Direct evaluation requires two component-wise multiplications, one addition, and one square.

  • The kernel trick avoids explicitly constructing the three-dimensional feature vectors and then taking their dot product; it does not reduce this two-dimensional kernel evaluation to one multiplication.

How to Identify a Valid Kernel Function?

What conditions must a function \(K(\mathbf{x}_i, \mathbf{x}_j)\) satisfy to guarantee that there is always an underlying Hilbert space and a mapping \(\phi\)?

Mercer’s Theorem provides the answer:

For any finite set of data points \(\{\mathbf{x}_1, \dots, \mathbf{x}_N\}\), if the Gram matrix \(\mathbf{K}\) computed from the kernel function is always positive semi-definite, then \(K\) is a valid kernel function.

What is a Gram Matrix?

The Gram matrix \(\mathbf{K}\) is an \(N \times N\) symmetric matrix where each element \(K_{ij}\) is the value computed by the kernel function on the \(i\)-th and \(j\)-th data points:

\[ \large{ \mathbf{K} = \begin{pmatrix} K(\mathbf{x}_1, \mathbf{x}_1) & K(\mathbf{x}_1, \mathbf{x}_2) & \dots & K(\mathbf{x}_1, \mathbf{x}_N) \\ K(\mathbf{x}_2, \mathbf{x}_1) & K(\mathbf{x}_2, \mathbf{x}_2) & \dots & K(\mathbf{x}_2, \mathbf{x}_N) \\ \vdots & \vdots & \ddots & \vdots \\ K(\mathbf{x}_N, \mathbf{x}_1) & K(\mathbf{x}_N, \mathbf{x}_2) & \dots & K(\mathbf{x}_N, \mathbf{x}_N) \end{pmatrix} } \]

Intuitive Understanding

The Gram matrix is a pairwise similarity matrix that describes the relationships between all sample points in the dataset. The positive semi-definite property ensures that this ‘similarity’ is geometrically consistent (not self-contradictory).

Common Kernel Functions: Your ‘Arsenal’

Fortunately, we don’t need to verify Mercer’s theorem ourselves every time. There are many ready-to-use, proven kernel functions available.

Principle for choosing a kernel

  • first require a symmetric positive-semidefinite Gram matrix, then choose the kernel and its hyperparameters from task meaning, scaling, and leakage-free validation.

  • Interpret kernel values within the chosen kernel:

    • RBF similarity decreases with standardized Euclidean distance.

    • An unnormalized linear kernel does not obey that universal monotonic rule.

Next, we will introduce some of the most commonly used kernel functions.

Common Kernel 1: Linear Kernel

\[ \large{ K(\mathbf{x}_i, \mathbf{x}_j) = \mathbf{x}_i^T \mathbf{x}_j } \]

  • Essence: It’s simply the dot product in the original space.
  • Corresponding Map: \(\phi(\mathbf{x}) = \mathbf{x}\), meaning no mapping is performed.
  • Application: When the data is already linearly separable, an SVM with a linear kernel is the standard linear SVM. This is the simplest and fastest baseline.

Common Kernel 2: Polynomial Kernel

\[ \large{ K(\mathbf{x}_i, \mathbf{x}_j) = (\gamma \mathbf{x}_i^T \mathbf{x}_j + r)^d } \]

  • Parameters:

    • \(d\): The degree of the polynomial.

    • \(\gamma\): A scaling coefficient.

  • \(r\): A nonnegative offset; the standard valid kernel uses \(d\in\mathbb N\), \(\gamma>0\), and \(r\ge0\).
  • Essence: With \(r=0\) the kernel is homogeneous and contains only total degree \(d\); lower-degree terms appear when \(r>0\).
  • Application:

    • Very effective for problems where interactions between features are important.

    • For instance, in financial risk control, \(x_1 \times x_2\) (product of income and debt ratio) might be a stronger predictor than \(x_1\) or \(x_2\) alone.

Common Kernel 3: Gaussian (RBF) Kernel

The Radial Basis Function (RBF) kernel, also called the Gaussian kernel, is a common candidate with universal-approximation properties, but it is not a task-independent “most powerful” choice.

\[ \large{ K(\mathbf{x}_i, \mathbf{x}_j) = \exp \left( -\frac{||\mathbf{x}_i - \mathbf{x}_j||^2}{2\sigma^2} \right) = \exp(-\gamma ||\mathbf{x}_i - \mathbf{x}_j||^2) } \]

  • Parameter:
    • \(\sigma\) (or \(\gamma = 1/(2\sigma^2)\)): Controls the ‘width’ of the kernel.
  • Essence: Similarity is determined entirely by the Euclidean distance between two points. The closer two points are, the closer the kernel value is to 1; the farther apart, the closer to 0.
  • Corresponding Map: This is a very powerful kernel because it corresponds to an infinite-dimensional feature space.

Intuitive Understanding of the RBF Kernel

RBF Kernel: How Gamma Determines 'Influence Radius' A diagram showing that a large gamma leads to a narrow influence and a complex boundary, while a small gamma leads to a wide influence and a smooth boundary. RBF influence radius K(x, x′) = exp(−γd²) · larger γ means faster decay Large γ · narrow influence sharp · fast decay Small γ · wide influence broad · slow decay

Reading the RBF Gamma Diagram

  • Small \(\gamma\) (Large \(\sigma\)): The kernel has a large radius, giving it a wide range of influence. The decision boundary is very smooth.
  • Large \(\gamma\) (Small \(\sigma\)): The kernel has a small radius, limiting the influence of each data point. The decision boundary becomes very complex and wiggly, and is prone to overfitting.

Conclusion

RBF is a reasonable candidate when smooth distance-based similarity is plausible; choose it only after leakage-free validation against simpler baselines.

Common Kernel 4: Sigmoid Kernel

\[ \large{ K(\mathbf{x}_i, \mathbf{x}_j) = \tanh(\alpha \mathbf{x}_i^T \mathbf{x}_j + \beta) } \]

  • Parameters: \(\alpha\) and \(\beta\).
  • Origin: Its form is inspired by the activation functions used in neural networks.
  • Caution: The Sigmoid kernel only satisfies Mercer’s condition for certain parameter values, making it less commonly used in practice than RBF and polynomial kernels.

Main lesson: KPCA/KSVM applications are Extension; after kernel and Gram checks, continue directly to the Fuyao Glass main case.

Application: Kernelized Learning Algorithms

Applying the Kernel Method: ‘Kernelization’ of Algorithms

  • The beauty of the kernel trick lies in its universality.

  • Any algorithm whose computations can be expressed entirely in terms of inner products between data points can be ‘kernelized’ by replacing the inner product with a kernel function \(K(\mathbf{x}_i, \mathbf{x}_j)\).

\[ \large{ \langle \mathbf{x}_i, \mathbf{x}_j \rangle \quad \xrightarrow{\text{Kernelize}} \quad K(\mathbf{x}_i, \mathbf{x}_j) = \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j) \rangle_{\mathcal{H}} } \]

This allows us to seamlessly upgrade linear algorithms, endowing them with powerful non-linear processing capabilities.

Classic Applications

We will introduce two classic applications:

  1. Kernel Principal Component Analysis (Kernel PCA)
  2. Kernel Support Vector Machine (Kernel SVM)

Application 1: Kernel Principal Component Analysis (KPCA)

Optional topic: after the kernel-trick and Gram-matrix checks, Core goes directly to the Fuyao Glass main case. Return to KPCA/KSVM derivations after Core.

Limitations of PCA

Review of PCA:

  1. Compute the covariance matrix of the data: \(\mathbf{\Sigma} = \frac{1}{N} \sum_{n=1}^N \mathbf{x}_n \mathbf{x}_n^T\) (assuming data is centered).
  2. Perform eigenvalue decomposition on \(\mathbf{\Sigma}\) to find the principal eigenvectors (principal components).

Problem: PCA can only discover linear structures in the data. For non-linear structures, PCA fails.

The Idea Behind KPCA

The idea of KPCA:

  1. Map and center the features: \(\tilde\phi(\mathbf{x}_n)=\phi(\mathbf{x}_n)-N^{-1}\sum_m\phi(\mathbf{x}_m)\).
  2. Compute the feature-space covariance: \(\mathbf{\Sigma}_\phi=N^{-1}\sum_n\tilde\phi(\mathbf{x}_n)\tilde\phi(\mathbf{x}_n)^T\).
  3. Perform eigenvalue decomposition on \(\mathbf{\Sigma}_\phi\).

The Computational Trick of KPCA

Directly computing \(\mathbf{\Sigma}_\phi\) is infeasible, as it could be an infinite-dimensional matrix.

  • Representer form: every required feature-space eigenvector lies in the span of the mapped observations.

  • Finite coefficients: write \(\mathbf{v}=\sum_{n=1}^N\alpha_n\phi(\mathbf{x}_n)\) and solve for the \(N\) coefficients rather than explicit feature coordinates.

Let \(H=I-N^{-1}\mathbf1\mathbf1^T\) and center the raw Gram matrix as \(K_c=HKH\). The eigenproblem is:

\[ \large{ K_c\boldsymbol{\alpha}=N\lambda\boldsymbol{\alpha},\qquad \boldsymbol{\alpha}^{T}K_c\boldsymbol{\alpha}=1 } \]

Here \(K_{ij}=K(\mathbf{x}_i,\mathbf{x}_j)\), while \(K_c\) represents centered mapped features. Kernel PCA avoids explicit \(\phi\) but cannot omit feature-space centering.

Application 2: Kernel Support Vector Machine (KSVM)

Review of Linear SVM

  • Objective: Find a hyperplane that separates two classes of data with the maximum margin.
  • Mathematically, this is equivalent to solving a constrained quadratic optimization problem.

The Dual Problem

  • Through Lagrangian duality, the SVM optimization problem can be converted into its ‘dual form’.
  • Magically, in the dual form, both the optimization objective and the decision function depend only on the inner products of the data points, \(\mathbf{x}_i^T \mathbf{x}_j\).

Soft-Margin SVM Dual: Objective and Feasible Set

For a soft-margin linear SVM with penalty \(C\), the dual must include both its objective and feasible set:

\[ \begin{aligned} \max_{\boldsymbol{\lambda}}\quad &\sum_{n=1}^{N}\lambda_n- \frac12\sum_{n=1}^{N}\sum_{m=1}^{N} \lambda_n\lambda_m y_ny_m\,\mathbf{x}_n^{\mathsf T}\mathbf{x}_m,\\ \text{s.t.}\quad &0\le \lambda_n\le C\quad(n=1,\ldots,N),\\ &\sum_{n=1}^{N}\lambda_n y_n=0. \end{aligned} \]

Here \(\lambda_n\) is a Lagrange multiplier and \(y_n\in\{-1,+1\}\). The hard-margin case removes the upper bound \(C\) but retains \(\lambda_n\ge0\) and the equality constraint.

From SVM to KSVM: Replace Only Inner Products

Kernelization replaces inner products in the objective and decision function; it does not remove the feasible set:

\[ \large{ \mathbf{x}_m^T \mathbf{x}_n \quad \longrightarrow \quad K(\mathbf{x}_m, \mathbf{x}_n) } \]

The complete kernel-SVM dual is:

\[ \begin{aligned} \max_{\boldsymbol{\lambda}}\quad &\sum_{n=1}^{N}\lambda_n- \frac12\sum_{n=1}^{N}\sum_{m=1}^{N} \lambda_n\lambda_m y_ny_m K(\mathbf{x}_n,\mathbf{x}_m),\\ \text{s.t.}\quad &0\le \lambda_n\le C,\qquad \sum_{n=1}^{N}\lambda_n y_n=0. \end{aligned} \]

  • When \(K\) is a valid positive-semidefinite kernel, this is equivalent to finding a maximum-margin hyperplane in its feature space and can yield a nonlinear boundary in the original space;

  • then continue to the final summary.

Objective Retrieval Before the Main Case

Retrieve the opening objectives: explain piecewise boundaries, compute QDA scores with prior/determinant terms, inspect a kernel Gram matrix, and explain why a held-out descriptive test comparison cannot retrospectively select complexity.

Retrieval prompt: If two classes have equal means but different covariance, which can use that difference, LDA or QDA?

Answer

QDA. LDA shares covariance; QDA estimates \(\Sigma_k\) per class and obtains quadratic terms, at the cost of more parameters and variance.

Formative Check 1: The Complete QDA Score

Two classes have equal Mahalanobis distance to a sample, but \(|\Sigma_1|=1\), \(|\Sigma_2|=4\), and equal priors. Which score is larger?

Answer

Class 1. After distance terms cancel, \(-\tfrac12\log|\Sigma_1|=0\) while class 2 has \(-\tfrac12\log4<0\). “Choose the nearest Mahalanobis distance” is incomplete QDA.

Main Case: Fuyao Glass QDA Decline Classification

  • Data used in this example： data/stock/stock_price_pre_adjusted.h5; key=data; Fuyao Glass 600660.XSHG; 2018–2024; predict next-day decline from day/five-day returns and 5/20-day volatility; chronological 80/20 split.

  • Evaluation plan:

    • before looking at test labels, choose LDA and QDA with reg_param=0.1 as the two models to compare.

    • Their shared test period describes final performance; it must not be used to choose a winner and then add complexity.

    • Method source: scikit-learn LDA/QDA guide.

Code 
from pathlib import Path  # Locate the downloaded data file

import pandas as pd  # Read local quotes into a table
from sklearn.pipeline import make_pipeline  # Apply scaling and QDA together within each training period
from sklearn.preprocessing import StandardScaler  # Unifying the return and volatility feature scales
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis, QuadraticDiscriminantAnalysis
from sklearn.metrics import balanced_accuracy_score, roc_auc_score  # Evaluate classification and probability ranking
# Public download: https://assets.qiufei.site/data/stock/stock_price_pre_adjusted.h5
# After downloading, change the next line to the file's actual location on your device.
# Course-relative option: Path("data/stock/stock_price_pre_adjusted.h5")
# Windows: Path(r"C:\qiufei\data\stock\stock_price_pre_adjusted.h5")
# macOS: Path("/Users/your_name/data/stock/stock_price_pre_adjusted.h5")
# Linux: Path("/home/your_name/data/stock/stock_price_pre_adjusted.h5")
price_path = Path("/home/ubuntu/r2_data_mount/data/stock/stock_price_pre_adjusted.h5")
price_rows = pd.read_hdf(price_path, key='data', where=['order_book_id=="600660.XSHG"', 'date>=Timestamp("2018-01-01")', 'date<=Timestamp("2024-12-31")'], columns=['close'])  # Only Load Target Companies and Periods
qda_frame = price_rows.reset_index().sort_values('date')  # Build Forecast Order by Trading Day
qda_frame['return_t'] = qda_frame['close'].pct_change()  # Compute one-day returns
qda_frame['return_5d_t'] = qda_frame['close'].pct_change(5)  # Compute cumulative five-day returns
qda_frame['volatility_5d_t'] = qda_frame['return_t'].rolling(5).std()  # Construct Short-Term Historical Volatility
qda_frame['volatility_20d_t'] = qda_frame['return_t'].rolling(20).std()  # Construct Monthly Historical Volatility
qda_frame['future_return_t1'] = qda_frame['return_t'].shift(-1)  # Retain continuous future returns before label construction to identify an unknown terminal label
qda_frame['target_date_t1'] = qda_frame['date'].shift(-1)  # Preserve the label-realization date for boundary purging
qda_frame = qda_frame.dropna()  # Drop rows with rolling-window missing values or unknown future returns before label construction
Code 
qda_frame['down_t1'] = (qda_frame['future_return_t1'] < 0).astype(int)  # Create classes only for observed future returns
assert qda_frame['future_return_t1'].notna().all() and qda_frame['date'].max() < price_rows.reset_index()['date'].max()  # Verify that the last feature date is earlier than the last label realization date
split_row = int(len(qda_frame) * 0.8)  # Fixed First Eighty Percent as Training Period
test_start_date = qda_frame.iloc[split_row]['date']
train_rows = qda_frame[(qda_frame['date'] < test_start_date) & (qda_frame['target_date_t1'] < test_start_date)]  # Purge training labels realized in test
test_rows = qda_frame[qda_frame['date'] >= test_start_date]
assert train_rows['target_date_t1'].max() < test_rows['date'].min()  # Verify the label-realization boundary
feature_names = ['return_t', 'return_5d_t', 'volatility_5d_t', 'volatility_20d_t']  # Define the model actual field
lda_model = make_pipeline(StandardScaler(), LinearDiscriminantAnalysis()).fit(train_rows[feature_names], train_rows['down_t1'])  # Fit the LDA model selected before viewing test results
qda_model = make_pipeline(StandardScaler(), QuadraticDiscriminantAnalysis(reg_param=0.1)).fit(train_rows[feature_names], train_rows['down_t1'])  # Fit the QDA model selected before viewing test results
lda_probability = lda_model.predict_proba(test_rows[feature_names])[:, 1]  # Produce LDA probabilities in the common held-out check
down_probability = qda_model.predict_proba(test_rows[feature_names])[:, 1]  # Produce QDA probabilities in the same held-out check
descriptive_comparison = pd.DataFrame([{'model': 'LDA', 'roc_auc': roc_auc_score(test_rows['down_t1'], lda_probability), 'balanced_accuracy': balanced_accuracy_score(test_rows['down_t1'], lda_probability >= 0.5)}, {'model': 'QDA', 'roc_auc': roc_auc_score(test_rows['down_t1'], down_probability), 'balanced_accuracy': balanced_accuracy_score(test_rows['down_t1'], down_probability >= 0.5)}])  # Save one descriptive check of both fixed models
display(descriptive_comparison)  # Show common test evidence without selecting a model
model roc_auc balanced_accuracy
0 LDA 0.539681 0.513192
1 QDA 0.458896 0.495022

Formative Check 2: Is the Kernel Valid?

If a candidate kernel’s Gram matrix has a clearly negative eigenvalue, can it directly serve a standard kernel SVM?

Answer

Generally no. Mercer’s condition requires positive semidefiniteness; a clear negative eigenvalue means no valid inner product and removes the standard convexity guarantee.

Step-by-Step Exercise: Interpret the LDA/QDA Comparison

  • Task： Interpret test AUC, balanced accuracy, and calibration for the LDA and QDA models evaluated together. Explain why these final results cannot be used to choose a winner and then change the model.
  • Complete solution:

    • Report both fixed models’ metrics and five-bin probability tables.

    • If QDA does not win, the pattern is consistent with variance risk from extra covariance parameters, but the opened test cannot be used to reselect the model.

    • Any complexity choice must be completed inside training-period time validation.

Code 
comparison_rows = descriptive_comparison.copy()  # Reuse the completed common check rather than reopening test
display(comparison_rows)  # Present the descriptive contrast while preserving the no-selection boundary
Table 1
model roc_auc balanced_accuracy
0 LDA 0.539681 0.513192
1 QDA 0.458896 0.495022

Scaffolded Complete Solution: Five-Bin Calibration

Code 
calibration_parts = []  # Collect Five Groups of Calibration Results for LDA and QDA
for model_name, model_probability in [('LDA', lda_probability), ('QDA', down_probability)]:  # Evaluate Two Probability Sets for the Same Test Label
    model_calibration = pd.DataFrame({'observed': test_rows['down_t1'].to_numpy(), 'probability': model_probability})  # Aligning Predictive Probability and Real Categories
    model_calibration['probability_bin'] = pd.cut(model_calibration['probability'], bins=[0, .2, .4, .6, .8, 1], include_lowest=True)  # Use five pre-declared probability intervals
    model_table = model_calibration.groupby('probability_bin', observed=False).agg(n=('observed', 'size'), mean_probability=('probability', 'mean'), observed_rate=('observed', 'mean')).reset_index()  # Calculate mean predicted probability and observed frequency for Each Group
    model_table.insert(0, 'model', model_name)  # Mark the model to which the calibration sheet belongs
    calibration_parts.append(model_table)  # Save Five Groups of Results for Current Model
pd.concat(calibration_parts, ignore_index=True).query("model == 'LDA'")  # Output five sets of calibration evidence for LDA first
Table 2
model probability_bin n mean_probability observed_rate
0 LDA (-0.001, 0.2] 0 NaN NaN
1 LDA (0.2, 0.4] 0 NaN NaN
2 LDA (0.4, 0.6] 336 0.507943 0.470238
3 LDA (0.6, 0.8] 0 NaN NaN
4 LDA (0.8, 1.0] 0 NaN NaN

Scaffolded Complete Solution: QDA Calibration

Code 
pd.concat(calibration_parts, ignore_index=True).query("model == 'QDA'")  # Output five sets of calibration evidence for QDA first
Table 3
model probability_bin n mean_probability observed_rate
5 QDA (-0.001, 0.2] 0 NaN NaN
6 QDA (0.2, 0.4] 5 0.329425 0.400000
7 QDA (0.4, 0.6] 331 0.526541 0.471299
8 QDA (0.6, 0.8] 0 NaN NaN
9 QDA (0.8, 1.0] 0 NaN NaN

Empty or tiny bins are instability evidence. Compare mean probability with observed frequency alongside n; an accidental match is not proof of good calibration.

Apply It to a New Case

Switch to Hengrui Pharmaceuticals 600276.XSHG; compare QDA probabilities, RBF-SVM decision scores, and the training-period prior-probability baseline. Tune reg_param, \(C\), and \(\gamma\) only with expanding training windows.

Complete-answer reminder

  • use chronological validation, estimate scaling without leakage, compare models and the baseline on the same test period, report AUC and—where probabilities are available—balanced accuracy and calibration, and explain the cost of added complexity.

  • Never interpret an uncalibrated SVM score as a probability.

Complete Solution for the New Case: Data and Time Boundaries

Table 4
Code 
from sklearn.model_selection import GridSearchCV, TimeSeriesSplit  # Extending the window only during the training period
from sklearn.svm import SVC  # Build an RBF classifier that outputs decision scores
from pathlib import Path  # Locate the downloaded data file
# Public download: https://assets.qiufei.site/data/stock/stock_price_pre_adjusted.h5
# After downloading, change the next line to the file's actual location on your device.
# Course-relative option: Path("data/stock/stock_price_pre_adjusted.h5")
# Windows: Path(r"C:\qiufei\data\stock\stock_price_pre_adjusted.h5")
# macOS: Path("/Users/your_name/data/stock/stock_price_pre_adjusted.h5")
# Linux: Path("/home/your_name/data/stock/stock_price_pre_adjusted.h5")
price_path = Path("/home/ubuntu/r2_data_mount/data/stock/stock_price_pre_adjusted.h5")
transfer_rows = pd.read_hdf(price_path, key='data', where=['order_book_id=="600276.XSHG"', 'date>=Timestamp("2018-01-01")', 'date<=Timestamp("2024-12-31")'], columns=['close'])  # Select Hengrui Medicine Close Price
transfer_frame = transfer_rows.reset_index().sort_values('date')  # Sort by trading days in order of forecast availability
transfer_frame['return_t'] = transfer_frame['close'].pct_change()  # Compute one-day returns
transfer_frame['return_5d_t'] = transfer_frame['close'].pct_change(5)  # Compute five-day returns
transfer_frame['volatility_5d_t'] = transfer_frame['return_t'].rolling(5).std()  # Compute rolling five-day volatility
transfer_frame['volatility_20d_t'] = transfer_frame['return_t'].rolling(20).std()  # Constructing Historical Twentieth Day Volatility
transfer_frame['future_return_t1'] = transfer_frame['return_t'].shift(-1)  # Retain continuous future returns before label construction
transfer_frame['target_date_t1'] = transfer_frame['date'].shift(-1)  # Preserve the label-realization date
transfer_frame = transfer_frame.dropna()  # Drop rows with unknown future outcomes or rolling-window missing values before label construction
transfer_frame['down_t1'] = (transfer_frame['future_return_t1'] < 0).astype(int)  # Create labels only for observed future returns
transfer_train = transfer_frame[(transfer_frame['date'] <= '2022-12-31') & (transfer_frame['target_date_t1'] < '2023-01-01')]  # Purge training labels realized in test
transfer_test = transfer_frame[transfer_frame['date'] >= '2023-01-01']
assert transfer_train['target_date_t1'].max() < transfer_test['date'].min()  # Verify the label-realization boundary
transfer_features = ['return_t', 'return_5d_t', 'volatility_5d_t', 'volatility_20d_t']  # Fixed Four T-Points as Available Feature

Complete Solution for the New Case: Selection and fixed Test

Code 
transfer_cv = TimeSeriesSplit(5, gap=1)  # Purge one row for the one-day forecast horizon in every fold
assert all(transfer_train.iloc[fit_idx]['target_date_t1'].max() < transfer_train.iloc[val_idx]['date'].min() for fit_idx, val_idx in transfer_cv.split(transfer_train))  # Verify every fold's label boundary
qda_search = GridSearchCV(make_pipeline(StandardScaler(), QuadraticDiscriminantAnalysis()), {'quadraticdiscriminantanalysis__reg_param': [0, .1, .5]}, cv=transfer_cv, scoring='roc_auc').fit(transfer_train[transfer_features], transfer_train['down_t1'])  # Select QDA shrink only during training
svm_search = GridSearchCV(make_pipeline(StandardScaler(), SVC(kernel='rbf')), {'svc__C': [.1, 1, 10], 'svc__gamma': ['scale', .1, 1]}, cv=transfer_cv, scoring='roc_auc').fit(transfer_train[transfer_features], transfer_train['down_t1'])  # Select kernel parameters without randomized internal probability fitting
transfer_probabilities = {'QDA': qda_search.predict_proba(transfer_test[transfer_features])[:, 1], 'prior baseline': pd.Series(transfer_train['down_t1'].mean(), index=transfer_test.index).to_numpy()}  # Retain only outputs with explicit probability semantics
svm_decision_score = svm_search.decision_function(transfer_test[transfer_features])  # Generate the uncalibrated SVM ranking score
probability_metrics = [{'model': model_name, 'roc_auc': roc_auc_score(transfer_test['down_t1'], probability), 'balanced_accuracy': balanced_accuracy_score(transfer_test['down_t1'], probability >= .5)} for model_name, probability in transfer_probabilities.items()]  # Apply a 0.5 threshold only to probabilities
transfer_metrics = pd.DataFrame(probability_metrics + [{'model': 'RBF-SVM score', 'roc_auc': roc_auc_score(transfer_test['down_t1'], svm_decision_score), 'balanced_accuracy': float('nan')}])  # Report only threshold-free SVM ranking evidence
transfer_calibration = []  # Collect calibration tables for the two probability models
for model_name, probability in transfer_probabilities.items():  # Use the same sub-box rule for each set of probabilities
    calibration_frame = pd.DataFrame({'observed': transfer_test['down_t1'].to_numpy(), 'probability': probability})  # Aligning Probability and Real Labels
    calibration_frame['bin'] = pd.cut(calibration_frame['probability'], [0, .2, .4, .6, .8, 1], include_lowest=True)  # Divide into five fixed probability groups
    model_calibration = calibration_frame.groupby('bin', observed=False).agg(n=('observed', 'size'), mean_probability=('probability', 'mean'), observed_rate=('observed', 'mean')).reset_index()  # Calculate Calibration Evidence
    model_calibration.insert(0, 'model', model_name)  # Indicate the source model for each set
    transfer_calibration.append(model_calibration)  # Save Current Model Results
display(pd.Series({'QDA_best': qda_search.best_params_, 'SVM_best': svm_search.best_params_}))  # Output fixed hyperparameters for training periods
display(transfer_metrics)  # Outputting common test AUC and equilibrium accuracy
Table 5 
QDA_best    {'quadraticdiscriminantanalysis__reg_param': 0.5}
SVM_best                     {'svc__C': 1, 'svc__gamma': 0.1}
dtype: object
model roc_auc balanced_accuracy
0 QDA 0.508321 0.503456
1 prior baseline 0.500000 0.500000
2 RBF-SVM score 0.498711 NaN

  • Executed design: QDA selects reg_param=0.5 with AUC/balanced accuracy 0.508321/0.503456;

  • RBF-SVM selects \(C=1,\gamma=0.1\) and reports only test-period AUC for its uncalibrated score;

  • the prior baseline is 0.500000/0.500000.

  • We avoid probability=True because its randomized inner fit violates the time boundary.

  • Without time-valid calibration, no SVM 0.5 probability threshold or calibration table is reported.

fixed-Test Calibration

Code 
pd.concat(transfer_calibration, ignore_index=True).query("model == 'QDA'")  # Outputting five calibration tables for QDA
Table 6
model bin n mean_probability observed_rate
0 QDA (-0.001, 0.2] 0 NaN NaN
1 QDA (0.2, 0.4] 9 0.314139 0.777778
2 QDA (0.4, 0.6] 470 0.498199 0.523404
3 QDA (0.6, 0.8] 4 0.650944 0.250000
4 QDA (0.8, 1.0] 0 NaN NaN

RBF-SVM: check the Uncalibrated Decision Score

Code 
pd.Series({'score_min': svm_decision_score.min(), 'score_median': pd.Series(svm_decision_score).median(), 'score_max': svm_decision_score.max(), 'test_roc_auc': roc_auc_score(transfer_test['down_t1'], svm_decision_score)})  # Report score range and threshold-free AUC
Table 7 
score_min      -1.209231
score_median   -0.295047
score_max       1.313768
test_roc_auc    0.498711
dtype: float64

fixed-Test Calibration: Prior-Probability Baseline

Code 
pd.concat(transfer_calibration, ignore_index=True).query("model == 'prior baseline'")  # Output the prior-probability baseline calibration table
Table 8
model bin n mean_probability observed_rate
5 prior baseline (-0.001, 0.2] 0 NaN NaN
6 prior baseline (0.2, 0.4] 0 NaN NaN
7 prior baseline (0.4, 0.6] 483 0.48995 0.52588
8 prior baseline (0.6, 0.8] 0 NaN NaN
9 prior baseline (0.8, 1.0] 0 NaN NaN

Formative Check 3: When Not to Use Nonlinearity

A nonlinear model fits training better but fails to beat the linear baseline in every time-validation window. Which should be chosen?

Answer

Prefer the linear baseline. Training fit is not generalization evidence; upgrade only for stable out-of-sample gains large enough to justify complexity.

Sources and Further Reading

  • Hastie, Tibshirani & Friedman, The Elements of Statistical Learning, discriminant analysis and kernels.
  • Schölkopf & Smola, Learning with Kernels.
  • Ledoit & Wolf (2004), covariance shrinkage.
  • Data: local pre-adjusted A-share data; file, key, fields, period, and split are stated above.

Chapter Summary

Optional topic

after Core, optionally enter the KPCA/KSVM derivations, then continue to the final summary without replaying the main case.

Comparison of Three Non-linear Modeling Philosophies

Feature / Method Piecewise Linear Discriminant Quadratic Discriminant Analysis (QDA) Kernel Method (Kernel Trick)
Core Idea Approximate with line segments Directly fit a quadratic curve Lift dimension, turn curve into line
Flexibility High (depends on segment design) Medium (only quadratic forms) High (depends on kernel, tuning, and retained dimensions)
Computational Cost Depends on number of segments Medium (\(O(d^2)\)) High (\(O(N^2)\) to \(O(N^3)\))
Interpretability Medium (like a decision tree) High (quadratic function) Low (high-dim space is not intuitive)
Main Assumption No specific distribution assumption Data follows a Gaussian distribution No specific distribution assumption
Key Parameters Number of subclasses/segments Class priors, covariance estimation, and regularization Kernel type and its parameters (gamma, d)
Use Case Intuitive modeling, tree-like scenarios Different class covariances, low feature dimension Non-linear problems where out-of-sample evidence supports the added complexity

Key Takeaways

  1. Non-linearity: use it when linear failure is demonstrated and validation supports added complexity.
  2. QDA: different class covariances create quadratic boundaries, but the Gaussian assumption remains strong.
  3. Kernel Trick:
    • Core Idea: Lift dimension + Apply a linear model.
    • Computes \(K(\mathbf{x}_i, \mathbf{x}_j)=\langle\phi(\mathbf{x}_i),\phi(\mathbf{x}_j)\rangle\) without explicit coordinates, while regularization and sample complexity remain.
    • Kernelizes inner-product algorithms such as PCA and SVM.
    • RBF is a common candidate, but performance depends on bandwidth, retained dimensions, the downstream model, and out-of-sample evaluation; the one-dimensional KPCA counterexample here shows that it does not guarantee separability.

Thank You!

Q & A