Linear classifiers, discriminants, and logistic models

Let $d\ge 1$ and $K\ge 2$ be finite integers, with ordered labels $1<2<\cdots <K$. A finite linear-score classifier on ${\mathbb{R}}^d$ is specified by vectors $a_k\in {\mathbb{R}}^d$ and constants $b_k\in \mathbb{R}$, one pair for each label, and assigns score $s_k(x)=a_k^{T}x+b_k$ to $x\in {\mathbb{R}}^d$. Its predicted label is the smallest index attaining ${\max }_{1\le j\le K}{s}_j(x)$. This rule is single-valued, including when two or more scores tie.

Hastie, Tibshirani, and Friedman, ESL, §4.2, equations (4.3)–(4.6)

Stanford CS229 Spring 2022 lecture notes, §§2.1–2.2

Let $n,q\ge 1$ and $K\ge 2$ be finite integers. For a fixed design matrix $X\in {\mathbb{R}}^{n\times q}$ and labels $y_i\in \{1,\dots ,K\}$, form the indicator response matrix $Y\in {\mathbb{R}}^{n\times K}$ by $Y_{ik}=1$ when $y_i=k$ and $Y_{ik}=0$ otherwise. For a coefficient matrix $B\in {\mathbb{R}}^{q\times K}$, set $L(B)=(2n{)}^{-1}\mathrm{\parallel }Y-XB{\mathrm{\parallel }}_F^2$, where $\mathrm{\parallel }A{\mathrm{\parallel }}_F^2$ is the sum of squares of all entries of $A$. Let $B_{\ast }$ be the least-squares minimizer with smallest Frobenius norm. For a new row vector $x^T\in {\mathbb{R}}^{1\times q}$, the indicator-response classifier assigns scores $(x^T{B}_{\ast }{)}_k$ and predicts the smallest class index attaining their maximum. An intercept, if used, is one of the columns of $X$; no rank assumption is imposed on $X$.

Finite linear-score classifiers with a deterministic tie rule

The minimum-norm indicator-response least-squares fit exists uniquely ↗

Hastie, Tibshirani, and Friedman, ESL, §4.2, equations (4.3)–(4.6)

Stanford CS229 Spring 2022 lecture notes, §§1.2 and 2.1

Let $n,q\ge 1$ and $K\ge 2$ be finite, let $X\in {\mathbb{R}}^{n\times q}$, and let $Y\in {\mathbb{R}}^{n\times K}$ be an indicator response matrix. Among all minimizers of $\mathrm{\parallel }Y-XB{\mathrm{\parallel }}_F^2$ over $B\in {\mathbb{R}}^{q\times K}$ there is a unique one of smallest Frobenius norm. If $X=U_r{D}_r{V}_r^T$ is a thin singular-value decomposition with rank $r>0$, orthonormal columns in $U_r,V_r$, and positive diagonal entries in $D_r$, then this minimizer is $B_{\ast }=V_r{D}_r^{-1}{U}_r^{T}Y$. If $r=0$, then $X=0$ and $B_{\ast }=0$. In either case the full minimizer set is $\{B_{\ast }+N:XN=0\}$.

Indicator-response least-squares classification

For a linear map $T:V\to W$ between finite-dimensional inner-product spaces, $x$ minimises $\parallel Tx-b\parallel$ if and only if $T^{\ast }(Tx-b)=0$, equivalently $T^{\ast }Tx=T^{\ast }b$; minimisers exist and any two differ by an element of $\ker T$

Every linear map between finite-dimensional real or complex inner product spaces admits a singular value decomposition

Hastie, Tibshirani, and Friedman, ESL, §4.2, equations (4.3)–(4.6)

Stanford CS229 Spring 2022 lecture notes, §§1.2 and 2.1

Assume the Axiom of Choice. Let $d\ge 1$ and $K\ge 2$ be finite integers, let the class label be $Y\in \{1,\dots ,K\}$, and let $X\in {\mathbb{R}}^d$. Choose class priors ${\pi }_k>0$ with ${\sum }_{k=1}^K{\pi }_k=1$, means ${\mu }_k\in {\mathbb{R}}^d$, and real symmetric positive-definite covariance matrices ${\mathrm{\Sigma }}_k\in {\mathbb{R}}^{d\times d}$. The Gaussian generative model has $\mathrm{Pr}(Y=k)={\pi }_k$ and conditional laws $X\mid Y=k\sim N_d({\mu }_k,{\mathrm{\Sigma }}_k)$. The LDA subfamily imposes one common covariance matrix, ${\mathrm{\Sigma }}_k=\mathrm{\Sigma }$ for every $k$; the QDA subfamily permits the covariance matrices to differ by class.

Multivariate normal law, including singular covariance

The Axiom of Choice

Hastie, Tibshirani, and Friedman, ESL, §4.3, equations (4.7)–(4.12)

Stanford CS229 Spring 2022 lecture notes, §4.1

Assume the Axiom of Choice. Let $d\ge 1$ and $K\ge 2$ be finite, let ${\pi }_k>0$ with ${\sum }_{k=1}^K{\pi }_k=1$, let ${\mu }_k\in {\mathbb{R}}^d$, and let each real symmetric matrix ${\mathrm{\Sigma }}_k\in {\mathbb{R}}^{d\times d}$ be positive definite, meaning $v^T{\mathrm{\Sigma }}_{k}v>0$ for every nonzero $v$. Define

For LDA, assume ${\mathrm{\Sigma }}_k=\mathrm{\Sigma }$ for all $k$; then $\log p_k(x)$ differs by a term independent of $k$ from the affine score

For QDA, allow the ${\mathrm{\Sigma }}_k$ to vary with $k$; then $\log p_k(x)$ differs by a term independent of $k$ from the quadratic score

Thus maximizing the posterior probabilities uses affine scores in LDA and scores of degree at most two in QDA; ties are resolved by the smallest class index.

Gaussian LDA and QDA model contracts

Finite linear-score classifiers with a deterministic tie rule

A positive-definite multivariate normal law has its Gaussian density

The Axiom of Choice

Hastie, Tibshirani, and Friedman, ESL, §4.3, equations (4.7)–(4.12)

Stanford CS229 Spring 2022 lecture notes, §4.1

For $d\ge 1$, define the sigmoid $\sigma (t)=(1+e^{-t}{)}^{-1}$. A binary logistic conditional model on $x\in {\mathbb{R}}^d$ has finite coefficients ${\beta }_0\in \mathbb{R}$, $\beta \in {\mathbb{R}}^d$ and specifies $\mathrm{Pr}(Y=1\mid x)=\sigma ({\beta }_0+x^T\beta )$ and $\mathrm{Pr}(Y=0\mid x)=1-\sigma ({\beta }_0+x^T\beta )$ for $Y\in \{0,1\}$. Its classifier predicts $1$ when ${\beta }_0+x^T\beta >0$ and predicts $0$ when ${\beta }_0+x^T\beta \le 0$. A multiclass softmax conditional model has finite ordered labels $1,\dots ,K$ with $K\ge 2$, affine logits ${\eta }_k(x)=a_k+x^T{w}_k$ for $a_k\in \mathbb{R}$ and $w_k\in {\mathbb{R}}^d$, and probabilities $\mathrm{Pr}(Y=k\mid x)=e^{{\eta }_k(x)}\mathrm{/}{\sum }_{j=1}^K{e}^{{\eta }_j(x)}$; its classifier chooses the smallest index attaining the largest logit. These models specify conditional label probabilities and impose no distributional assumption on the feature vector $X$, in particular no Gaussian feature law.

Finite linear-score classifiers with a deterministic tie rule

Hastie, Tibshirani, and Friedman, ESL, §§4.4 and 4.4.5

Stanford CS229 Spring 2022 lecture notes, §§2.1 and 3.2.3

Fix a finite design with rows $x_i^T\in {\mathbb{R}}^q$, $1\le i\le n$, where $n\ge 1$ and $q\ge 1$. Use either an intercept design, in which the first coordinate of every row is $1$ and $\beta =({\beta }_0,\theta )\in \mathbb{R}\times {\mathbb{R}}^{q-1}$, or a no-intercept design, in which no coordinate is reserved as an intercept, the intercept coefficient is fixed at zero, and $\beta \in {\mathbb{R}}^q$. Let $y_i\in \{0,1\}$ and assume the responses are conditionally independent given the design, with binary logistic probabilities $p_i=\sigma (x_i^T\beta )$ for finite coefficients. In either design convention, the log-likelihood is

For $\lambda >0$, the L1 objective to minimize in the intercept design is $-\mathrm{\ell }(\beta )+\lambda \mathrm{\parallel }\theta {\mathrm{\parallel }}_1$, so the intercept is unpenalized; in the no-intercept design it is $-\mathrm{\ell }(\beta )+\lambda \mathrm{\parallel }\beta {\mathrm{\parallel }}_1$, so every coefficient is penalized. Here $\mathrm{\parallel }\theta {\mathrm{\parallel }}_1={\sum }_{j=1}^{q-1}\mathrm{\mid }{\theta }_j\mathrm{\mid }$ and $\mathrm{\parallel }\beta {\mathrm{\parallel }}_1={\sum }_{j=1}^q\mathrm{\mid }{\beta }_j\mathrm{\mid }$, with an empty sum equal to zero. These are objective definitions and assert no optimizer existence.

Binary logistic and multiclass softmax conditional models

Hastie, Tibshirani, and Friedman, ESL, §§4.4.1 and 4.4.4, equations (4.20) and (4.31)

Stanford CS229 Spring 2022 lecture notes, §2.1

Let $n,q\ge 1$ be finite, let $X\in {\mathbb{R}}^{n\times q}$ be a fixed design matrix whose first column is the intercept column of ones, and let $y\in \{0,1{\}}^n$. For finite $\beta \in {\mathbb{R}}^q$, put $\eta =X\beta$, $p_i=\sigma ({\eta }_i)$, $W=\mathrm{diag}(p_i(1-p_i))$, and $\mathrm{\ell }(\beta )={\sum }_i[y_i{\eta }_i-\log (1+e^{{\eta }_i})]$. Then

The diagonal entries of $W$ are positive, so $-\mathrm{\ell }$ is convex; if $X$ has full column rank, $X^{T}WX$ is positive definite. In that full-rank case, the exact Newton step for maximizing the unpenalized log-likelihood is

This is the Bernoulli-logit IRLS step with the weighted least-squares convention using weights $p_i(1-p_i)$. The identities describe one update and do not assert convergence of repeated updates.

Binary logistic and multiclass softmax conditional models

Binary logistic log-likelihood and L1-penalized objective

A $C^2$ function is convex exactly when its Hessian is positive semidefinite

For a linear map $T:V\to W$ between finite-dimensional inner-product spaces, $x$ minimises $\parallel Tx-b\parallel$ if and only if $T^{\ast }(Tx-b)=0$, equivalently $T^{\ast }Tx=T^{\ast }b$; minimisers exist and any two differ by an element of $\ker T$

Generalized linear model with explicit conditioning

Explicit exponential-family response contracts

General-link score and Fisher information

One minimum-norm IRLS step

IRLS equals the Fisher-scoring step when information is invertible

Hastie, Tibshirani, and Friedman, ESL, §§4.4.1 and 4.4.4, equations (4.20)–(4.31)

Stanford CS229 Spring 2022 lecture notes, §§2.1 and 3.2.2

Let $n,q\ge 1$ be finite, let $x_i\in {\mathbb{R}}^q$ be a fixed design row with an intercept coordinate when one is used, and let $y_i\in \{0,1\}$. Suppose the unpenalized binary logistic log-likelihood is $\mathrm{\ell }(\beta )={\sum }_i[y_i{x}_i^T\beta -\log (1+e^{x_i^T\beta })]$. If there is a vector $v\in {\mathbb{R}}^q$ such that $(2y_i-1)x_i^{T}v>0$ for every $i$, then ${\sup }_{\beta \in {\mathbb{R}}^q}\mathrm{\ell }(\beta )=0$, and no finite coefficient vector attains this supremum.

Binary logistic and multiclass softmax conditional models

Binary logistic log-likelihood and L1-penalized objective

Hastie, Tibshirani, and Friedman, ESL, §4.4.5 and Exercise 4.5

Input a finite ordered sample $((x_i,y_i){)}_{i=1}^n$ with $n\ge 1$, $x_i\in {\mathbb{R}}^d$, and $y_i\in \{-1,+1\}$. Put ${\tilde{x}}_i=(x_i,1)\in {\mathbb{R}}^{d+1}$ and initialize $w=0$. In each pass, visit $i=1,\dots ,n$ in the fixed order. Whenever $y_i{w}^T{\tilde{x}}_i\le 0$, replace $w$ by $w+y_i{\tilde{x}}_i$ and count one update. After a full pass with no updates, stop and return $w$. The associated classifier returns $+1$ when $w^T(x,1)>0$ and $-1$ when $w^T(x,1)\le 0$, so a score tie is assigned to $-1$. The procedure has no iteration limit; if its stop condition never holds, it continues with further passes.

Hastie, Tibshirani, and Friedman, ESL, §4.5.1, update (4.44)

Stanford CS229 Spring 2022 lecture notes, §2.2

Let $((x_i,y_i){)}_{i=1}^n$ be a finite ordered sample with $n\ge 1$, $x_i\in {\mathbb{R}}^d$, and $y_i\in \{-1,+1\}$. Put ${\tilde{x}}_i=(x_i,1)\in {\mathbb{R}}^{d+1}$, with Euclidean inner product $⟨u,v⟩=u^{T}v$ and norm $\mathrm{\parallel }u{\mathrm{\parallel }}_2=(u^{T}u{)}^{1\mathrm{/}2}$. Suppose $\mathrm{\parallel }{\tilde{x}}_i{\mathrm{\parallel }}_2\le R$ for every $i$ and there is a unit vector $u\in {\mathbb{R}}^{d+1}$ and $\gamma >0$ such that $y_i⟨u,{\tilde{x}}_i⟩\ge \gamma$ for every $i$. The zero-initialized cyclic procedure that visits the sample in the stated order and updates $w\leftarrow w+y_i{\tilde{x}}_i$ whenever $y_i⟨w,{\tilde{x}}_i⟩\le 0$ makes at most $R^2\mathrm{/}{\gamma }^2$ updates and stops after a finite pass with no updates. At each visit, before its update, the procedure predicts $+1$ if $⟨w,{\tilde{x}}_i⟩>0$ and $-1$ otherwise; a prediction mistake is a visit on which this prediction differs from $y_i$. The total number of such mistakes before termination is at most $R^2\mathrm{/}{\gamma }^2$. The returned weight vector has strictly positive signed margin on every sample point.

The cyclic perceptron update procedure

Cauchy–Schwarz: $\mathrm{\mid }⟨u,v⟩\mathrm{\mid }\le \parallel u\parallel \parallel v\parallel$, with equality exactly for linearly dependent vectors

Hastie, Tibshirani, and Friedman, ESL, §4.5.1 and Exercise 4.6

Cornell CS4780 Spring 2018, Lecture 3, “Perceptron Convergence”