Quadratic discriminant analysis

Overview

Each class is modelled as a normal distribution with its own mean and covariance. The decision rule compares a score that is quadratic in the input 2012.14331 §3.1. When the two covariances differ, the quadratic terms do not cancel, so the boundary is curved. The paper calls this the optimal boundary and does not use the name QDA.

The invariant is that deciding class a when the score is positive maximises the expected value gain, given the priors and value matrix 2012.14331 §3.1. With the error-minimising values, it minimises the overall error 2012.14331 §3.1. The card names this as the Bayes-optimal rule in §3.1.

Variants

Bayes quadratic boundary for two normals

The score is \beta(\bm{x}) = \bm{x}'\mathbf{Q}_2\bm{x} + \bm{q}_1'\bm{x} + q_0, with the coefficients given in eq. 3. The quadratic term is \mathbf{Q}_2 = \tfrac{1}{2}(\bm{\Sigma}_b^{-1} - \bm{\Sigma}_a^{-1}). It vanishes when the covariances are equal, so the boundary is then linear 2012.14331 eq. 3. Card: Methods to integrate multinormals and compute classification measures.

Boundary fitted from samples

With samples, the paper uses the maximum-likelihood estimates: sample means, sample covariances and relative class counts. The optimal boundary then follows from these estimates 2012.14331 §3.2. The card does not state whether the covariances divide by n or n-1. The code uses the n-1 form, which is a code choice and not a paper statement 2012.14331 §3.2 classify_normals.m.

Sample-optimal boundary

The paper also describes a sample-based refinement. It starts from the quadratic \beta and adjusts its (k+1)(k+2)/2 free parameters to maximise the outcome value of the samples. The paper says this stays in the quadratic family and limits overfitting 2012.14331 §3.2. The card's code does not follow this by default; it fits an SVM boundary instead 2012.14331 §3.2 optimize_samp_bd.m. See Pitfalls.

When to use which

Implementation sketch

Language-agnostic pseudocode of the Bayes quadratic rule for two normals, with the value terms set to the error-minimising case. The formula is from 2012.14331 §3.1 eq. 3.

# Quadratic decision rule for two normal classes  [arxiv:2012.14331 §3.1] [eq. 3]
# Input:  x (k,); mu_a, mu_b (k,); cov_a, cov_b (k, k); p_a, p_b priors
# Output: label "a" or "b"

def qda_decide(x, mu_a, cov_a, mu_b, cov_b, p_a, p_b):
    inv_a = inverse(cov_a)
    inv_b = inverse(cov_b)
    # Quadratic, linear and constant terms of the score  [eq. 3]
    q2 = 0.5 * (inv_b - inv_a)
    q1 = inv_a @ mu_a - inv_b @ mu_b
    # Value terms assumed equal, so only the priors remain  [§3.1]
    q0 = 0.5 * (mu_b @ inv_b @ mu_b - mu_a @ inv_a @ mu_a
                + log(det(cov_b) / det(cov_a))) + log(p_a / p_b)
    beta = x @ q2 @ x + q1 @ x + q0
    # Decide a when the score is positive  [§3.1]
    return "a" if beta > 0 else "b"

Pitfalls

• Value matrix notation. The card defines v_a = v_{aa} - v_{ab} and says "with \mathbf{V} = \mathbf{1}" minimises the overall error 2012.14331 §3.1. Read literally, an all-ones matrix gives v_a = 0, and the logarithm in eq. 3 is then undefined. The card does not say which matrix it means. The sketch above assumes equal values, which is the error-minimising case.
• Fitted versus optimised boundary. The paper's sample-optimal boundary starts from \beta and optimises the outcome value 2012.14331 §3.2. The card's code uses an SVM by default and warns that this boundary can do worse than \beta classify_normals.m. Choose the method deliberately.
• Speed claims. The card's summary says the \tilde{\chi} method is the fastest for the quadratic benchmark 2012.14331 §5. Its table gives 0.7 s for \tilde{\chi} and 0.1 s for the ray method on the two-normal case fig. 8b. Check the figure before you pick a method on speed.
• Dependencies. The generalized chi-square path needs an external toolbox that is not in the card's repository int_norm_quad_gx2.m.

Contradictions

None known among the cited papers. Only one card covers this concept so far.

Papers

• Methods to integrate multinormals and compute classification measures: gives the quadratic Bayes boundary for two normals with unequal covariances, its fit from samples, and the integrals that compute its error.