The Elements of Statistical Learning Note

Preliminaries

Matrix Algebra

Orthonormal Matrix

Definition

${\mathbf{Q}}^{⊺}\mathbf{Q}=\mathbf{Q}{\mathbf{Q}}^{⊺}=\mathbf{I}\text{and}{\mathbf{Q}}^{⊺}={\mathbf{Q}}^{-1}$ The matrix whose column and rows are orthonormal vectors.

Examples

• Rotation Matrix
• Permutation Matrix

Facts

Every orthonormal matrix is Unitary Matrix.

For a vector $\mathbf{y}=x_1{\mathbf{q}}_1+x_2{\mathbf{q}}_2+\cdots +x_n{\mathbf{q}}_n$, which can be expressed as a linear combination of column vectors of the orthonormal matrix $\mathbf{Q}$, we can easily find the coefficients $x_i={\mathbf{q}}_i^{⊺}\mathbf{y}$ of the linear combination using the Inner product. $\mathbf{y}=\mathbf{Qx}\to {\mathbf{Q}}^{⊺}\mathbf{y}=\underset{\mathbf{I}}{\underbrace{{\mathbf{Q}}^{⊺}\mathbf{Q}}}\mathbf{x}\to {\mathbf{Q}}^{⊺}\mathbf{y}=\mathbf{x}$

Link to original

Eigendecomposition

Definition

$\mathbf{Av}=\lambda \mathbf{v}$ where $\mathbf{A}$ is a $n\times n$ matrix and $\mathbf{v}\ne 0$

If $\mathbf{Av}$ is a scalar multiple of non-zero vector $\mathbf{v}$, then $\lambda$ is the eigenvalue and $\mathbf{v}$ is the eigenvector.

Characteristic Polynomial

$|\mathbf{A}-\lambda \mathbf{I}|=0$ The values ${\lambda }_i$ satisfying the characteristic polynomial, are the eigenvalues of the matrix $\mathbf{A}$

Eigenspace

$E=\{\mathbf{v}:(\mathbf{A}-\lambda \mathbf{I})\mathbf{v}=0\}$

The set of all eigenvectors of $A$ corresponding to the same eigenvalue, together with the zero vector.

The Kernel of the matrix $(\mathbf{A}-\lambda \mathbf{I})$

Eigenvector: non-zero vector in the eigenspace

Algebraic Multiplicity

${\mu }_A({\lambda }_i)$

Let ${\lambda }_i$ be an eigenvalue of an $n\times n$ matrix $A$. The algebraic multiplicity ${\mu }_A({\lambda }_i)$ of the eigenvalue is its multiplicity as a root of a Characteristic Polynomial, that is, the largest k such that $(\lambda -{\lambda }_i{)}^k$

Geometric Multiplicity

${\gamma }_A({\lambda }_i)$ Let ${\lambda }_i$ be an eigenvalue of an $n\times n$ matrix $A$. The geometric multiplicity ${\gamma }_A({\lambda }_i)$ of the eigenvalue is the dimension of the Eigenspace associated with the eigenvalue.

Computation

1. Find the solution^[eigenvalues] of the Characteristic Polynomial.
2. Find the solution^[eigenvectors] of the Under-Constrained System $(\mathbf{A}-{\lambda }_i\mathbf{I}){\mathbf{v}}_i=0$ using the found eigenvalue.

Facts

There exists at least one eigenvector corresponding to the eigenvalue $\lambda$

Eigenvectors corresponding to different eigenvalues are always linearly independent.

When $\mathbf{A}$ is a normal or real Symmetric Matrix, the eigendecomposition is called Spectral Decomposition

$\mathrm{tr}(\mathbf{A})={\sum }_{i=1}^n{\lambda }_i$ The Trace of the matrix is equal to the sum of the eigenvalues of the matrix.

Proof Since the matrix $\mathbf{A}-\lambda \mathbf{I}$ only has $\lambda$ term on diagonal, and the calculation of cofactor deletes a row and a column, the coefficient of ${\lambda }^{n-1}$ of $\text{det}(\mathbf{A}-\lambda \mathbf{I})$ is always $-(a_{11}+a_{22}+\cdots +a_{nn})$. Also, since ${\lambda }_i$ are the solution of the Characteristic Polynomial, the expression is factorized as $\text{det}(\mathbf{A}-\lambda \mathbf{I})=(\lambda -{\lambda }_1)(\lambda -{\lambda }_2)\dots (\lambda -{\lambda }_n)$ and the coefficient of ${\lambda }^{n-1}$ become a $-({\lambda }_1+{\lambda }_2+\cdots +{\lambda }_n)$ Therefore, $-(a_{11}+a_{22}+\cdots +a_{nn})=-({\lambda }_1+{\lambda }_2+\cdots +{\lambda }_n)$ and $\text{Trace}(\mathbf{A})={\sum }_{i=1}^n{\lambda }_i$.

$|\mathbf{A}|={\prod }_{i=1}^n{\lambda }_i$ The Determinant of the matrix is equal to the product of the eigenvalues of the matrix.

Not all matrices have $n$ linearly independent eigenvectors.

When $\mathbf{Av}=\lambda \mathbf{v}$ holds,

• the eigenvalues of ${\mathbf{A}}^{-1}$ are $\frac{1}{\lambda }$ and the eigenvectors of the matrix ${\mathbf{A}}^{-1}$ are the same as $\mathbf{A}$.
• the eigenvalues of $A^k$ is ${\lambda }^k$
• the eigenvalues of $c\mathbf{A}$ is $c\lambda$
• the eigenvalues of $\mathbf{A}+c\mathbf{I}$ is $\lambda +c$
• the eigenvalues of $(\mathbf{A}+c\mathbf{I}{)}^{-1}$ is $1/(\lambda +c)$

$1\le {\gamma }_A({\lambda }_i)\le {\mu }_A({\lambda }_i)\le n$

An eigenvalue’s Geometric Multiplicity cannot exceed its Algebraic Multiplicity

$\exists P\text{ s.t. }A=PD{P}^{-1}\iff \forall {\lambda }_i:{\gamma }_A({\lambda }_i)={\mu }_A({\lambda }_i)$

the matrix is diagonalizable $\iff$ the Geometric Multiplicity is equal to the Algebraic Multiplicity for all eigenvalues

Let $A$ be a symmetric matrix. Then, $A$ has $r$ eigenvalues equal to $1$ and the rest zero $\iff A^2=A,\mathrm{rank}(A)=r$.

Link to original

The non-zero eigenvalues of $AB$ are the same as those of $BA$.

Link to original

Projection Matrix

Definition

$P=A(A^{⊺}A{)}^{-1}{A}^{⊺}$

For some vector $\mathbf{b}$, $P\mathbf{b}$ is the projection of $\mathbf{b}$ onto $A$

Facts

The projection matrix $P$ is symmetric Idempotent Matrix

Consider a Symmetric Matrix $P$, then $P$ is idempotent with rank $r$ if and only if $r$ eigenvalues are $1$ and $n-r$ eigenvalues are $0$.

$\mathrm{tr}(P)=\mathrm{rank}(P)$

The projection matrix is Positive Semi-Definite Matrix

If $P_1$ and $P_2$ are projection matrices, and $P_1-P_2$ is Positive Semi-Definite Matrix, then

• $P_1{P}_2=P_2{P}_1=P_2$
• $P_1-P_2$ is a projection matrix.

Link to original

QR Decomposition

Definition

$\mathbf{A}=\mathbf{QR}$ Decomposition of matrix $\mathbf{A}$ into a product $\mathbf{A}=\mathbf{QR}$ of an orthonormal matrix $\mathbf{Q}$ and an upper triangular matrix $\mathbf{R}$.

Computation

Using the Gram Schmidt Orthonormalization

QR decomposition can be computed by Gram Schmidt Orthonormalization. Where $Q=[q_1,\dots ,q_n]$ is the matrix of orthonormal column vectors obtained by the orthonormalization and $\mathbf{R}=\left[\begin{array}{ccccc}{\mathbf{q}}_1^{⊺}{\mathbf{a}}_1& {\mathbf{q}}_1^{⊺}{\mathbf{a}}_2& {\mathbf{q}}_1^{⊺}{\mathbf{a}}_3& \cdots & {\mathbf{q}}_1^{⊺}{\mathbf{a}}_n\\ 0& {\mathbf{q}}_2^{⊺}{\mathbf{a}}_2& {\mathbf{q}}_2^{⊺}{\mathbf{a}}_3& \cdots & {\mathbf{q}}_2^{⊺}{\mathbf{a}}_n\\ 0& 0& {\mathbf{q}}_3^{⊺}{\mathbf{a}}_3& \cdots & {\mathbf{q}}_3^{⊺}{\mathbf{a}}_n\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & {\mathbf{q}}_n^{⊺}{\mathbf{a}}_n\end{array}\right]$

Link to original

Cholesky Decomposition

Definition

$A=L{L}^{†}$

Decomposition of a Positive-Definite Matrix into the product of lower triangular matrix and its Conjugate Transpose.

Computation

Let $\mathbf{A}=\left[\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{22}& a_{33}\end{array}\right]$ be Positive-Definite Matrix. Then, $\mathbf{A}=\mathbf{L}{\mathbf{L}}^{⊺}=\left[\begin{array}{ccc}{L}_{11}& 0& 0\\ L_{21}& L_{22}& 0\\ L_{31}& L_{32}& L_{33}\end{array}\right]\left[\begin{array}{ccc}{L}_{11}& L_{21}& L_{31}\\ 0& L_{22}& L_{32}\\ 0& 0& L_{33}\end{array}\right]=\left[\begin{array}{ccc}{L}_{11}^2& & \text{(symmetric)}\\ & & \\ L_{21}{L}_{11}& L_{21}^2+L_{22}^2& \\ & & \\ L_{31}{L}_{11}& L_{31}{L}_{21}+L_{32}{L}_{22}& L_{31}^2+L_{32}^2+L_{33}^2\end{array}\right]$ By setting the first-row first-column entry $L_{11}=\sqrt{a_{11}}$, can find other entries using substitution. $L_{21}=a_{21}/L_{11},L_{31}=a_{31}/L_{11},L_{22}=\sqrt{a_{22}-L_{21}^2},L_{32}=(a_{32}=L_{31}{L}_{21})/L_{22},L_{33}=\sqrt{a_{33}-L_{31}^2-L_{32}^2}$ By summarizing, $L_{ii}=\sqrt{a_{ii}-{\sum }_{k=1}^{i-1}{L}_{ik}^2}$, $L_{ij}=\frac{1}{L_{jj}}(a_{ij}-{\sum }_{k=1}^{j-1}{L}_{ik}{L}_{jk})$

Link to original

Spectral Theorem

Definition

$A=A^{†}\iff A=Q\mathbf{\Lambda }{Q}^{†}$ where $Q$ is a Unitary Matrix, and $\mathbf{\Lambda }=\mathrm{diag}({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n)$

A matrix $A$ is a Hermitian Matrix if and only if $A$ is Unitary Diagonalizable Matrix.

Facts

Every Hermitian Matrix is diagonalizable, and has real-valued Eigenvalues and orthonormal eigenvector matrix.

For the Hermitian Matrix ${\mathbf{A}}^{†}=\mathbf{A}$, the every eigenvalue is real.

Proof For the eigendecomposition $\mathbf{Ax}=\lambda \mathbf{x}$, ${\mathbf{x}}^{†}\mathbf{Ax}={\mathbf{x}}^{†}\lambda \mathbf{x}=\lambda {\mathbf{x}}^{†}\mathbf{x}=\lambda ||\mathbf{x}||\Rightarrow \lambda =\frac{{\mathbf{x}}^{†}\mathbf{Ax}}{||\mathbf{x}||}$. Since $\mathbf{A}$ is hermitian, ${\mathbf{x}}^{†}\mathbf{Ax}\in \mathbb{R}$ and norm is always real. Therefore, every eigenvalue is real.

For the Hermitian Matrix ${\mathbf{A}}^{†}=\mathbf{A}$, the eigenvectors from different eigenvalues are orthogonal.

Proof Let the eigendecomposition $\mathbf{A}{\mathbf{x}}_1={\lambda }_1{\mathbf{x}}_1,\mathbf{A}{\mathbf{x}}_2={\lambda }_2{\mathbf{x}}_2$ where ${\lambda }_1\ne {\lambda }_2,{\mathbf{x}}_1\ne {\mathbf{x}}_2$. By the property of hermitian matrix, $(\mathbf{A}{\mathbf{x}}_1{)}^{†}{\mathbf{x}}_2={\mathbf{x}}_1^{†}{\mathbf{A}}^{†}{\mathbf{x}}_2={\mathbf{x}}_1^{†}{\lambda }_2{\mathbf{x}}_2={\lambda }_2{\mathbf{x}}_1^{†}{\mathbf{x}}_2$ and $(\mathbf{A}{\mathbf{x}}_1{)}^{†}{\mathbf{x}}_2=({\lambda }_1{\mathbf{x}}_1{)}^{†}{\mathbf{x}}_2={\bar{\lambda }}_1{\mathbf{x}}_1^{†}{\mathbf{x}}_2={\lambda }_1{\mathbf{x}}_1^{†}{\mathbf{x}}_2$ So, ${\lambda }_2{\mathbf{x}}_1^{†}{\mathbf{x}}_2={\lambda }_1{\mathbf{x}}_1^{†}{\mathbf{x}}_2\Rightarrow ({\lambda }_1-{\lambda }_2){\mathbf{x}}_1^{†}{\mathbf{x}}_2=0$. Since ${\lambda }_1\ne {\lambda }_2$, ${\mathbf{x}}_1^{†}{\mathbf{x}}_2=0$. Therefore, ${\mathbf{x}}_1^{†},{\mathbf{x}}_2$ are orthogonal.

Link to original

Singular Value Decomposition

Definition

${\mathbf{A}}_{n\times m}={\mathbf{U}}_{n\times n}{\mathbf{D}}_{n\times m}({\mathbf{V}}_{m\times m}{)}^{⊺}={\sum }_{i=1}^{\min (n,m)}{d}_i{U}_i{V}_i^{⊺}$ An arbitrary matrix ${\mathbf{A}}_{n\times m}$ can be decomposed to $\mathbf{UD}{\mathbf{V}}^{⊺}$.

For $n\ge m$ ${\mathbf{A}}_{n\times m}={\mathbf{U}}_{n\times m}{\mathbf{D}}_{m\times m}({\mathbf{V}}_{m\times m}{)}^{⊺}$ where ${\mathbf{U}}^{⊺}\mathbf{U}={\mathbf{I}}_m$ and ${\mathbf{V}}^{⊺}\mathbf{V}=\mathbf{V}{\mathbf{V}}^{⊺}={\mathbf{I}}_m$ and $\mathbf{D}$ is Diagonal Matrix

For $n\le m$ ${\mathbf{A}}_{n\times m}={\mathbf{U}}_{n\times n}{\mathbf{D}}_{n\times n}({\mathbf{V}}_{m\times n}{)}^{⊺}$ where ${\mathbf{U}}^{⊺}\mathbf{U}=\mathbf{U}{\mathbf{U}}^{⊺}={\mathbf{I}}_n$ and ${\mathbf{V}}^{⊺}\mathbf{V}={\mathbf{I}}_n$ and $\mathbf{D}$ is Diagonal Matrix

Calculation

For matrix ${\mathbf{A}}_{m\times n}=\mathbf{UD}{\mathbf{V}}^{⊺}$

${\mathbf{V}}_{n\times n}$ is the matrix of orthonormal eigenvectors of ${\mathbf{A}}^{⊺}\mathbf{A}$ ${\mathbf{U}}_{m\times m}$ is the matrix of orthonormal eigenvectors of $\mathbf{A}{\mathbf{A}}^{⊺}$ ${\mathbf{D}}_{m\times n}$ is the Diagonal Matrix made of the square roots of the non-zero eigenvalues of ${\mathbf{A}}^{⊺}\mathbf{A}$ and $\mathbf{A}{\mathbf{A}}^{⊺}$ sorted in descending order.

If the eigendecomposition is ${\mathbf{A}}^{⊺}\mathbf{Ax}=\lambda \mathbf{x}$, then the eigenvalues $\lambda \ge 0$ and the eigenvectors $\mathbf{x}\in \mathbb{C}({\mathbf{A}}^{⊺})$ are orthonormal by Spectral Theorem. If the $\mathrm{rank}(\mathbf{A})=r\le n$, then ${\lambda }_1⪈{\lambda }_2⪈\cdots \ge {\lambda }_r,{\lambda }_{r+1}=\dots {\lambda }_n=0$. Where ${\sigma }_i=\sqrt{{\lambda }_i}{}_{i=1,2,\dots ,r}$ are called the singular values.

Now, the Orthonormal Matrix $\mathbf{V}=[{\mathbf{V}}_1,{\mathbf{V}}_2]$ is calculated using the singular values. Where $V_1=[{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_r]$ is the Orthonormal Matrix of eigenvectors corresponding to the non-zero eigenvalues and $V_2=[{\mathbf{v}}_{r+1},{\mathbf{v}}_{r+2},\dots ,{\mathbf{v}}_n]$ is the Orthonormal Matrix of eigenvectors corresponding to zero eigenvalues where each ${\mathbf{v}}_r+i\in \mathbf{N}({\mathbf{A}}^{⊺}\mathbf{A})=\mathbf{N}(\mathbf{A})$, and ${\mathbf{D}}_{m\times n}=\mathrm{diag}({\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r,0,\dots ,0)$ is a rectangular Diagonal Matrix.

Since $\mathbf{V}$ is an orthonormal matrix and $\mathbf{D}$ is a Diagonal Matrix, $\mathbf{AV}=\mathbf{UD}\Rightarrow \mathbf{A}[{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n]=[{\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_m]\mathbf{D}\Rightarrow \mathbf{A}{\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i\Rightarrow {\mathbf{u}}_i=\frac{1}{{\sigma }_i}\mathbf{A}{\mathbf{v}}_i$. Now, the Orthonormal Matrix $\mathbf{U}=[{\mathbf{U}}_1,{\mathbf{U}}_2]$ is calculated using the linear system $\frac{1}{{\sigma }_i}\mathbf{A}{\mathbf{v}}_i$ and the null space of $\mathbf{A}$, $\mathbf{N}(\mathbf{A})$ Where ${\mathbf{U}}_1=[{\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_r]$ is the Orthonormal Matrix of the vectors ${\mathbf{u}}_{\{1,2,\dots ,r\}}\in \mathbf{C}(\mathbf{A})$ obtained from the system equation $\frac{1}{{\sigma }_i}\mathbf{A}{\mathbf{v}}_i$ And ${\mathbf{U}}_2=[{\mathbf{u}}_{r+1},{\mathbf{u}}_{r+2},\dots ,{\mathbf{u}}_m]$ is the Orthonormal Matrix of the vectors ${\mathbf{u}}_{\{r+1,r+2,\dots ,m\}}\in \mathbf{N}({\mathbf{A}}^{⊺})$. which is corresponding to zero eigenvalues

The Orthonormal Matrix $\mathbf{U}=[{\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_m]$ can also be formed by the eigenvectors of $\mathbf{A}{\mathbf{A}}^{⊺}$ similarly to calculating of $\mathbf{V}$.

Facts

$\mathbf{U},\mathbf{V}$ are the Unitary Matrix

Let $\mathbf{A}$ be a real symmetric Positive Semi-Definite Matrix Then, the Eigendecomposition(Spectral Decomposition) of $\mathbf{A}$ and the singular value decomposition of $\mathbf{A}$ are equal.

$\mathbf{A}=\mathbf{P\Lambda }{\mathbf{P}}^{⊺}=\mathbf{UD}{\mathbf{V}}^{⊺}$ where $\mathbf{P}=\mathbf{U}=\mathbf{V}$ and $\mathbf{\Lambda }=\mathbf{D}$ are non-negative and the shape of the every matrix is $n\times n$

Visualization

every matrix can be decomposed as a

• ${\mathbf{V}}^{⊺}$: rotation and reflection
• $\mathbf{D}$: scaling
• $\mathbf{U}$: rotation and reflection

Link to original

Non-Negative Matrix Factorization

Definition

${\mathbf{X}}_{n\times p}\approx {\mathbf{W}}_{n\times r}{\mathbf{H}}_{r\times p}$ where $r\le \max (n,p)$

Non-negative matrix factorization (NMF) is an algorithm where a matrix $\mathbf{X}$ is factorized into two matrices $\mathbf{W}$ and $\mathbf{H}$ have no negative elements.

The matrices $\mathbf{W}$ and $\mathbf{H}$ are found by maximizing $\sum _{i=1}^n\sum _{j=1}^p[x_{ij}\log (\mathbf{WH}{)}_{ij}-(\mathbf{WH}{)}_{ij}]$

Link to original

Model Assessment and Selection

Bias-Variance Decomposition

Definition

Assume that $Y=f(X)+ϵ$ where $E(ϵ)=0$ and $\mathrm{Var}(ϵ)={\sigma }_{ϵ}^2$. Then, under squared error loss. $\begin{array}{rl}\mathrm{Err}(x_0)& =E[(Y-\hat{f}(x_0){)}^2|X=x_0]\\ & ={\sigma }_{ϵ}^2+{\mathrm{Bias}}^2(\hat{f}(x_0))+\mathrm{Var}(\hat{f}(x_0))\\ & =\text{Irreducible error}+{\text{Bias}}^2+\text{Variance}\end{array}$

Link to original

Mallow's Cp

Definition

$C_p=\frac{SS{E}_p}{s^2}-(n-2p)=\overline{\text{err}}+\frac{p}{n}{\hat{\sigma }}^2$ where $p-1$ is the number of explanatory variables, $s^2$ is a sample variance under the full model, and $\overline{\text{err}}=\frac{RSS}{n}$

Mallow’s $C_p$ is used to assess the fit of a regression model. A small value of $C_p$ means that the model is relatively precise.

Link to original

Akaike Information Criterion

Definition

$AIC=-\frac{2}{n}\sum _{i=1}^n\ln f(X_i\hat{\mathbf{\theta }})+\frac{2p}{n}$ where $\hat{\mathbf{\theta }}$ is the MLE of the postulated model’s parameter $\mathbf{\theta }$

Link to original

Bayesian Information Criterion

Definition

$BIC=\frac{SS{E}_p}{n{\sigma }^2}+\frac{p\ln n}{n}$

Facts

BIC more penalize than AIC when $p$ is large

Link to original

Vapnik–Chervonenkis Dimension

Definition

Vapnik–Chervonenkis (VC) dimension is measure of the size of a class of sets. The VC dimension of the class $\{f(x,\alpha )\}$ is the largest number of points that can be shattered (can always learn a perpect classifier for any labeling) by members of $\{f(x,\alpha )\}$.

Examples

• The VC dimension of linear indicator functions in the plane is 3.
• $\sin (\alpha x)$ has infinite VC dimension.

Link to original

Cross Validation

Definition

Partition a set of data into $K$ sets $I_j,j=1,2,\dots ,K$ and denote a function $\kappa :\{1,2,\dots ,n\}\to \{1,2,\dots ,K\}$ such that $\kappa (i)=j\iff i\in I_j$. For the dataset $\{({\mathbf{X}}_1,Y_1),({\mathbf{X}}_2,Y_2),\dots ,({\mathbf{X}}_n,Y_n)\}$, let ${\hat{f}}_{-j}$ be the estimator based on observations except $I_j$, then the cross validation estimation for the prediction error is defined as ${\widehat{PE}}_{CV}(\hat{f})=\frac{1}{n}\sum _{i=1}^{n}L(Y_i,{\hat{f}}_{-\kappa (i)}({\mathbf{X}}_i))$ where $L$ is a loss function

Facts

If the data is partitioned into $k$ group with equal size, then it is called a $k$-fold cross validation.

Link to original

Leave-One-Out-Cross-Validation

Definition

$\text{LOOCV}(\hat{f})=\frac{1}{n}\sum _{i=1}^{n}L(Y_i,{\hat{f}}_{-i}({\mathbf{X}}_i))$ Cross Validation with $K=n$

Link to original

Generalized Croos Validation

Convenient approximation to Leave-One-Out-Cross-Validation of a linear model $\hat{\mathbf{y}}=\mathbf{Sy}$, $\mathrm{GCV}(\hat{f})=\frac{1}{n}\sum _{i=1}^n{\left[\frac{y_i-\hat{f}(x_i)}{1-\mathrm{tr}(\mathbf{S})/n}\right]}^2\stackrel{a}{\to }\text{LOOCV}(\hat{f})$

Link to original

Maximum Likelihood Methods

Maximum Likelihood Estimation

Definition

MLE is the method of estimating the parameters of an assumed Distribution

Let $X_1,X_2,\dots ,X_n$ be Random Sample with PDF $f(x|\theta )$, where $\theta \in \Omega$, then the MLE ${\hat{\theta }}_{\text{MLE}}$ of $\theta$ is estimated as ${\hat{\theta }}_{\text{MLE}}=\underset{\theta }{\mathrm{argmax}}L(\theta |\mathbf{x})$

Regularity Conditions

• R0: The pdfs are distinct, i.e. $\theta \ne {\theta }^{\prime }\Rightarrow f(x_i|\theta )\ne f(x_i|{\theta }^{\prime })$
• R1: The pdfs have same supports $\forall \theta$
• R2: The true value ${\theta }_0$ is an interior point in $\Omega$
• R3: The pdf $f(x|\theta )$ is twice differentiable with respect to $\theta \in \Omega$
• R4: $\frac{\partial }{\partial {\theta }^2}\int f(x|\theta )dx=\int \frac{\partial }{\partial {\theta }^2}f(x|\theta )dx$
• R5: The pdf $f(x|\theta )$ is three times differentiable with respect to $\theta \in \Omega$, $\forall \theta \in \Omega ,\left|\frac{{\partial }^3}{\partial {\theta }^3}\ln f(x|\theta )\right|\le M(x)$, and $\exists c\in \mathbb{R},\exists M(x),\forall |\theta -{\theta }_0|<c,\forall$ interior point $x,E_{{\theta }_0}[M(X)]<\infty$

Properties

Functional Invariance

If $\hat{\theta }$ is the MLE for $\theta$, then $g(\hat{\theta })$ is the MLE of $g(\theta )$

Consistency

Under R0 ~ R2 Regularity Conditions, let ${\theta }_0$ be a true parameter, $f(x|\theta )$ is differentiable with respect to $\theta \in \Omega$, then $\frac{\partial }{\partial \theta }L(\theta )=0$ has a solution ${\hat{\theta }}_n$ such that ${\hat{\theta }}_n\stackrel{P}{\to }{\theta }_0$

Asymptotic Normality

Under the R0 ~ R5 Regularity Conditions, let $X_1,X_2,\dots ,X_n$ be Random Sample with PDF $f(x|\theta )$, where $\theta \in \Omega$, ${\hat{\theta }}_n$ be a consistent Sequence of solutions of MLE equation $\frac{\partial l(\theta )}{\partial \theta }=0$, and $0<I({\theta }_0)<\infty$, then $\sqrt{n}({\hat{\theta }}_n-{\theta }_0)\stackrel{D}{\to }N\left(0,\frac{1}{I({\theta }_0)}\right)$ where $I({\theta }_0)$ is the Fisher Information.

By the asymptotic normality, the MLE estimator is asymptotically efficient under R0 ~ R5 Regularity Conditions

Asymptotic Confidence Interval

By the asymptotic normality of MLE, $\sqrt{nI(\hat{\theta })}(\hat{\theta }-\theta )\stackrel{D}{\to }N(0,1)$ Thus, $100(1-\alpha )\%$ confidence interval of for $\theta$ is $\left(\hat{\theta }-z_{\alpha /2}\frac{1}{\sqrt{nI(\hat{\theta })}},\hat{\theta }+z_{\alpha /2}\frac{1}{\sqrt{nI(\hat{\theta })}}\right)$

Delta method for MLE Estimator

Under the R0 ~ R5 Regularity Conditions, let $g(x)$ be a continuous function and $g^{\prime }({\theta }_0)\ne 0$, then $\sqrt{n}(g({\hat{\theta }}_n)-g({\theta }_0))\stackrel{D}{\to }N\left(0,\frac{g^{\prime }({\theta }_0{)}^2}{I({\theta }_0)}\right)$

Facts

Under R0 and R1 regularity conditions, let ${\theta }_0$ be a true parameter, then $\forall \theta \ne {\theta }_0,\underset{n\to \infty }{\lim }{P}_{{\theta }_0}[L({\theta }_0)>L(\theta )]=1$

Link to original

The EM Algorithm

Expectation-Maximization Algorithm

Definition

Let $\mathbf{X}=(X_1,X_2,\dots ,X_n)$ be an observed data, $\mathbf{Z}=(Z_1,Z_2,\dots ,Z_n)$ be an unobserved (latent) variable, $\mathbf{X},\mathbf{Z}$ are independent, $g(\mathbf{X}|\mathbf{\theta })$ be a joint pdf of $\mathbf{X}$, $h(\mathbf{X},\mathbf{Z}|\mathbf{\theta })$ be a joint pdf of $\mathbf{X},\mathbf{Z}$, $k(\mathbf{Z}|\mathbf{X},\mathbf{\theta })$ be a conditional pdf of $\mathbf{Z}$ given $\mathbf{X}$

By the definition of a conditional pdf, we have the identity $k(\mathbf{Z}|\mathbf{X},\mathbf{\theta })=\frac{h(\mathbf{X},\mathbf{Z}|\mathbf{\theta })}{g(\mathbf{X}|\mathbf{\theta })}$

The goal of the EM algorithm is maximizing the observed likelihood $L(\mathbf{\theta }|\mathbf{X})=g(\mathbf{X}|\mathbf{\theta })$ using the complete likelihood $L^c(\mathbf{\theta }|\mathbf{X},\mathbf{Z})=h(\mathbf{X},\mathbf{Z}|\mathbf{\theta })$.

Using the definition conditional pdf, we derive the identity for an arbitrary but fixed ${\mathbf{\theta }}_0\in \Omega$

&= \int \ln[h(\mathbf{X}, \mathbf{Z} | \boldsymbol{\theta})] k(\mathbf{Z} | \mathbf{X}, \boldsymbol{\theta}_{0}) d \mathbf{Z} - \int \ln[k(\mathbf{Z} | \mathbf{X}, \boldsymbol{\theta})]k(\mathbf{Z} | \mathbf{X}, \boldsymbol{\theta}_{0})d\mathbf{Z}\\ &= E_{\boldsymbol{\theta}_{0}}[\ln L^{c}(\boldsymbol{\theta}|\mathbf{X}, \mathbf{Z}) | \boldsymbol{\theta}_{0}, \mathbf{X}] - E_{\boldsymbol{\theta}_{0}}[\ln k(\mathbf{Z} | \mathbf{X}, \boldsymbol{\theta}) | \boldsymbol{\theta}_{0}, \mathbf{X}] \end{aligned}$$ Let the first term of RHS be a quasi-likelihood function $$Q(\boldsymbol{\theta} | \boldsymbol{\theta}_{0}, \mathbf{X}) := E_{\boldsymbol{\theta}_{0}}[\ln L^{c}(\boldsymbol{\theta}|\mathbf{X}, \mathbf{Z}) | \boldsymbol{\theta}_{0}, \mathbf{X}]$$ EM algorithm maximizes $Q(\boldsymbol{\theta} | \boldsymbol{\theta}_{0}, \mathbf{X})$ instead of maximizing $\ln L(\boldsymbol{\theta}|\mathbf{X})$ # Algorithm 1. Expectation Step: Compute $$Q(\boldsymbol{\theta} | \hat{\boldsymbol{\theta}}^{(m)}, \mathbf{X}) := E_{\hat{\boldsymbol{\theta}}^{(m)}}[\ln L^{c}(\boldsymbol{\theta}|\mathbf{X}, \mathbf{Z}) | \hat{\boldsymbol{\theta}}_{m}, \mathbf{X}]$$ where the $m = 0, 1, \dots$, and the expectation is taken under the conditional pdf $k(\mathbf{Z} | \mathbf{X}, \hat{\boldsymbol{\theta}}^{(m)})$ 2. Maximization Step: $$\hat{\boldsymbol{\theta}}^{(m+1)} = \underset{\boldsymbol{\theta}}{\operatorname{arg max}} Q(\boldsymbol{\theta} | \hat{\boldsymbol{\theta}}^{(m)}, \mathbf{X})$$ # Properties ## Convergence The [[Sequence]] of estimates $\hat{\boldsymbol{\theta}}^{(m)}$ satisfies $$L(\hat{\boldsymbol{\theta}}^{(m+1)}|\mathbf{X}) \leq L(\hat{\boldsymbol{\theta}}^{(m)}|\mathbf{X})$$ Therefore the [[Sequence]] of EM estimates converge to (at least local) optimalLink to original

Bayesian Methods

Bayes Risk

Definition

r(\theta, \delta) &= \int_{\Theta} R(\theta, \delta) \pi(\theta) d\theta = E_\theta[R(\theta, \delta)] = E_\theta[E_{x}[L(\theta, \delta(x))]]\\ &= \int_{\Theta} \int_{X} L(\theta, \delta(x))p(x|\theta) \pi(\theta) dx d\theta = \int_{X} \int_{\Theta} L(\theta, \delta(x))p(\theta|x)p(x) d\theta dx\\ &= \int_{X}E_\theta[L(\theta, \delta(x))|X=x]p(x)dx = \int_{X}\rho(x, \pi)p(x)dx \end{aligned}$$ where $L(\theta, \delta)$ is [[Loss Function]], $R(\theta, \delta)$ is [[Risk Function]], and $\rho(x, \pi)$ is a [[Posterior Risk]].Link to original

Posterior Risk

Definition

$\rho (\pi ,\delta )=E_{\theta }[L(\theta ,\delta (x))|X=x]=\int L(\theta ,\delta (x))p(\theta |x)d\theta$

where $L(\theta ,\delta )$ is Loss Function, $R(\theta ,\delta )$ is Risk Function, and $p(\theta |x)$ is a posterior probability

Link to original

Bayes Estimator

Definition

${\hat{\delta }}_{\text{Bayes}}=\underset{\delta }{\mathrm{argmin}}r(\theta ,\delta )=\underset{\delta }{\mathrm{argmin}}\rho (\pi ,\delta )$

Estimator that minimizes the Bayes Risk $r(\theta ,\delta )$ or Posterior Risk $\rho (\pi ,\delta )$

Facts

Under Squared Error Loss, the Bayes estimator is a posterior mean, and a posterior mode under Absolute Error Loss.

Consider a regression model $\mathbf{y}\sim N_n(\mathbf{X}\mathbf{\beta },{\sigma }^2\mathbf{I})$ and the prior distribution for $\mathbf{\beta }$, $\mathbf{\beta }\sim N_p(\mathbf{m},{\sigma }^2\mathbf{V})$. Then, the Bayes estimator under the Squared Error Loss is obtained as ${\hat{\mathbf{\beta }}}_{\text{Bayes}}=({\mathbf{X}}^{⊺}\mathbf{X}+{\mathbf{V}}^{-1}{)}^{-1}({\mathbf{V}}^{-1}\mathbf{m}+{\mathbf{X}}^{⊺}\mathbf{y})$ If $\mathbf{V}={\lambda }^{-1}{\mathbf{I}}_p$ for some $\lambda >0$ and $\mathbf{m}=0$, then the Bayes estimator is the same as ridge estimator ${\hat{\mathbf{\beta }}}_{\text{Bayes}}={\hat{\mathbf{\beta }}}_{\text{ridge}}=({\mathbf{X}}^{⊺}\mathbf{X}+\lambda \mathbf{I}{)}^{-1}{\mathbf{X}}^{⊺}\mathbf{y}$ If $\mathbf{V}={\lambda }^{-1}({\mathbf{X}}^{⊺}\mathbf{X}{)}^{-1}$ and $\mathbf{m}=0$, then the Bayes estimator is the James-Stein regression estimator ${\hat{\mathbf{\beta }}}_{\text{Bayes}}=(1+\lambda {)}^{-1}\hat{\mathbf{\beta }}$

Link to original

Monte Carlo Integration

Definition

${\int }_a^{b}h(x)dx={\int }_a^{b}q(x)f(x)dx=E[q(X)]\approx \frac{1}{n}\sum _{i=1}^{n}q(X_i)$ where $h(x):=q(x)f(x)$ and $f(x)$ is a PDF

Link to original

Gibbs Sampling

Definition

A MCMC algorithm for sampling from a specified Multivariate Distribution when direct sampling from the joint distribution is difficult, but sampling from the Conditional Distribution is more practical.

Algorithm

1. Begin with some initial value $X^{(0)}$
2. For $i=1,\dots k$ generate $X^{(i+1)}$ from $p(X_j^{(i+1)}|X_1^{(i+1)},\dots ,X_{j-1}^{(i+1)},X_{j+1}^{(i+1)},\dots ,X_n^{(i+1)})$
3. Repeat the above step $k$ times.

Examples

Consider a bivariate random variable $(X,Y)$, and suppose we want to obtain samples from the marginals $f(x),f(y)$. Take samples from the conditional distributions $x_i\sim f(x|y=y_{i-1})$ and $y_i\sim f(y|x=x_{i-1})$. As $k\to \infty$, the samples $x_k,y_k$ are eventually samples from $f(x)$ and $f(y)$ respectively.

Facts

It is common to discard some number of samples at the beginning (burn-in period).

Link to original

Regression

Parametric Regression

Simple Linear Regression

Definition

$Y_i={\beta }_0+{\beta }_1{X}_i+{ϵ}_i,i=1,2,\dots ,n$ where ${ϵ}_i$‘s are i.i.d. error terms, with $E({ϵ}_i)=0$ and $\mathrm{Var}({ϵ}_i)={\sigma }^2$

Link to original

Multiple Linear Regression

Definition

$Y_i={\beta }_0+{\beta }_1{X}_{i1}+{\beta }_2{X}_{i2}+\cdots +{\beta }_{p-1}{X}_{i,p-1}+{ϵ}_i,i=1,2,\dots ,n$ where ${ϵ}_i$‘s are i.i.d. error terms, with $E({ϵ}_i)=0$ and $\mathrm{Var}({ϵ}_i)={\sigma }^2$

Matrix Notations

Let $\mathbf{\beta }=({\beta }_0,{\beta }_1,{\beta }_2,\dots ,{\beta }_{p-1}{)}^{⊺}$ and ${\mathbf{x}}_i=(1,X_{i1},X_{i2},\dots ,X_{i,p-1}{)}^{⊺}$, then the regression model can be express the model as $Y_i={\mathbf{x}}_i^{⊺}\mathbf{\beta }+{ϵ}_i,i=1,2,\dots ,n$

Let $\mathbf{y}=[Y_1,Y_2,\dots ,Y_n{]}^{⊺}$, $\mathbf{X}=[{\mathbf{x}}_1^{⊺},{\mathbf{x}}_2^{⊺},\dots ,{\mathbf{x}}_n^{⊺}{]}^{⊺}$, $\mathbf{ϵ}=[{ϵ}_1,{ϵ}_2,\dots ,{ϵ}_n{]}^{⊺}$, then the regression model can be express as $\mathbf{y}=\mathbf{X}\mathbf{\beta }+\mathbf{ϵ}$ where $E[\mathbf{ϵ}]=0$, and $\mathrm{Cov}[\mathbf{ϵ}]={\sigma }^2{I}_n$

Link to original

Ridge Regression

Definition

$\begin{array}{rl}{\hat{\beta }}_{\text{ridge}}& =({\mathbf{X}}^{⊺}\mathbf{X}+\lambda \mathbf{I}{)}^{-1}{\mathbf{X}}^{⊺}\mathbf{y}\\ & =\underset{\beta }{\mathrm{argmin}}(\mathbf{y}-\mathbf{X}\beta {)}^{⊺}(\mathbf{y}-\mathbf{X}\beta )+\lambda {\beta }^{⊺}\beta \\ & =\underset{\beta }{\mathrm{argmin}}(\mathbf{y}-\mathbf{X}\beta {)}^{⊺}(\mathbf{y}-\mathbf{X}\beta ),\text{subject to}{\beta }^{⊺}\beta \le c\end{array}$ where $\lambda \ge 0$ is a complexity parameter that controls the amount of shrinkage.

Ridge regression is particularly useful to mitigate the problem of Multicollinearity in linear regression

Facts

${\hat{\mathbf{y}}}_{\text{ridge}}=\mathbf{X}{\hat{\beta }}_{\text{ridge}}=\mathbf{X}({\mathbf{X}}^{⊺}\mathbf{X}+\lambda \mathbf{I}{)}^{-1}{\mathbf{X}}^{⊺}\mathbf{y}=\sum _{i=1}^p{\mathbf{u}}_j\frac{d_j^2}{d_j^2+\lambda }{\mathbf{u}}_j^{⊺}\mathbf{y}$ where $\mathbf{X}=\mathbf{UD}{\mathbf{V}}^{⊺}$ by Singular Value Decomposition

Link to original

Lasso Regression

Definition

$\begin{array}{rl}{\hat{\beta }}_{\text{lasso}}& =\underset{\beta }{\mathrm{argmin}}(\mathbf{y}-\mathbf{X}\beta {)}^{⊺}(\mathbf{y}-\mathbf{X}\beta )+\lambda ||\beta ||\\ & =\underset{\beta }{\mathrm{argmin}}(\mathbf{y}-\mathbf{X}\beta {)}^{⊺}(\mathbf{y}-\mathbf{X}\beta ),\text{subject to}||\beta ||\le c\end{array}$

Lasso model assume that the coefficients of the model are sparse.

Link to original

Elastic Net Regularization

Definition

$\begin{array}{rl}{\hat{\beta }}_{\text{lasso}}& =\underset{\beta }{\mathrm{argmin}}(\mathbf{y}-\mathbf{X}\beta {)}^{⊺}(\mathbf{y}-\mathbf{X}\beta )+\lambda (\alpha {\beta }^{⊺}\beta +(1-\alpha )||\beta ||)\\ & =\underset{\beta }{\mathrm{argmin}}(\mathbf{y}-\mathbf{X}\beta {)}^{⊺}(\mathbf{y}-\mathbf{X}\beta ),\text{subject to}(\alpha {\beta }^{⊺}\beta +(1-\alpha )||\beta ||)\le c\end{array}$

Elastic net is a regularized regression method that linearly combined the penalties of the lasso and ridge regressions.

Link to original

Principal Component Analysis

Definition

PCA is a linear dimensionality reduction technique. The correlated variables are linearly transformed onto a new coordinate system such that the directions capturing the largest variance in the data.

Population Version

Given a random vector $\mathbf{x}$, we find a $\mathbf{\alpha }$ such that $\mathrm{Var}({\mathbf{\alpha }}^{⊺}\mathbf{x})$ is maximized: $\underset{\mathbf{\alpha }}{\mathrm{argmax}}\mathrm{Var}({\mathbf{\alpha }}^{⊺}\mathbf{x})\text{s.t.}{\mathbf{\alpha }}^{⊺}\mathbf{\alpha }=1$ Equivalently, by the Method of Lagrange Multipliers with ${\mathbf{\alpha }}^{⊺}\mathbf{\alpha }=1$, $\underset{\mathbf{\alpha }}{\mathrm{argmax}}{\mathbf{\alpha }}^{⊺}\Sigma \mathbf{\alpha }-\lambda ({\mathbf{\alpha }}^{⊺}\mathbf{\alpha }-1)$ By differentiation, the $\mathbf{\alpha }$ is given by the eigen value problem $\Sigma \mathbf{\alpha }=\lambda \mathbf{\alpha }$ Thus the $\mathbf{\alpha }$ maximizing the variance of ${\mathbf{\alpha }}^{⊺}\mathbf{x}$ is the eigenvector corresponding to the largest Eigenvalue.

Sample Version

Given a data matrix $\mathbf{X}$, by Singular Value Decomposition, A matrix $\mathbf{X}$ can be factorized as $\mathbf{X}=\mathbf{UD}{\mathbf{V}}^{⊺}$. By algebra, $\mathbf{XV}=\mathbf{UD}=:\mathbf{Z}\Rightarrow \mathbf{X}{\mathbf{v}}_i=d_i{\mathbf{u}}_i=:{\mathbf{z}}_i$, where we call ${\mathbf{z}}_i$ the $i$-th principal component.

Facts

Since $\mathrm{Var}({\mathbf{z}}_i)=\mathrm{Var}(\mathbf{X}{\mathbf{v}}_i)=\frac{d_i^2}{n}$ and $d_1\ge d_2\ge \cdots \ge d_p\ge 0$ $\mathrm{Var}({\mathbf{z}}_1)\ge \mathrm{Var}({\mathbf{z}}_2)\ge \cdots \ge \mathrm{Var}({\mathbf{z}}_p)\ge 0$

Link to original

Partial Least Squares Regression

Definition

${\hat{\phi }}_m=\underset{\alpha }{\mathrm{argmax}}{\mathrm{Corr}}^2(\mathbf{y},\mathbf{X}a)\mathrm{Var}(\mathbf{X}\alpha )\text{subject to}||\alpha ||=1,{\alpha }^{⊺}\mathbf{S}{\hat{\phi }}_l=0,l=1,\dots ,m-1$ where $\mathbf{S}=\frac{1}{n}{\mathbf{X}}^{⊺}\mathbf{X}$ is the sample covariance matrix.

Unlike PCR maximizing $\mathrm{Var}(\mathbf{X}a)$ only, PLS finds directions maximizing both $\mathrm{Var}(\mathbf{X}a)$ and ${\mathrm{Corr}}^2(\mathbf{y},\mathbf{X}a)$

Link to original

Grouped Lasso

${\hat{\beta }}_{\text{grouped lasso}}=\underset{\beta }{\mathrm{argmin}}(\mathbf{y}-\mathbf{X}\beta {)}^{⊺}(\mathbf{y}-\mathbf{X}\beta )+\lambda \sum _{l=1}^L\sqrt{p_l}||{\beta }_l|{|}_2$ where $L$ is the number of groups, $p_l$ is the number of variables within the group $l$, and $||\cdot |{|}_2$ is Euclidean Norm

In grouped lasso, the variables in each group share a regularization parameter.

Link to original

nonparametricNonparametric Regression

Piecewise Polynomials

Definition

Suppose that knots are ${\xi }_j,j=1,\dots ,K$. Then, the basis functions for order-M spline are defined as: $\begin{array}{rl}{h}_j(X)& =X^{j-1},j=1,\dots ,M\\ h_{M+l}(X)& =(X-{\xi }_l{)}_{+}^{M-1},l=1,\dots ,K\end{array}$ where $(x{)}_{+}=\{\begin{array}{ll}x& x\ge 0\\ 0& x<0\end{array}$

Examples

For cubic Polynomials with two knots ${\xi }_1,{\xi }_2$, the basis functions are: $h_1(X)=1,h_2(X)=X,h_3(X)=X^2,h_4(X)=X^3,h_5(X)=(X-{\xi }_1{)}_{+}^3,h_6(X)=(X-{\xi }_2{)}_{+}^3$

Facts

Order of piecewise polynomials

• constant: 1
• linear: 2
• quadratic: 3
• cubic: 4

Link to original

Natural Cubic Splines

Definition

Suppose that knots are ${\xi }_j,j=1,\dots ,K$. Then, the basis functions for natural cubic Spline are defined as: $N_1(X)=1,N_2(X)=X,N_{k+2}(X)=d_k(X)-d_{K-1}(X)$ where $d_k(X)=\frac{(X-{\xi }_k{)}_{+}^3-(X-{\xi }_K{)}_{+}^3}{{\xi }_K-{\xi }_k}$

Link to original

Smoothing Splines

Definition

$RSS(f,\lambda )=\sum _{i=1}^N(y_i-f(x_i){)}^2+\lambda \int f^{\prime \prime }(t{)}^{2}dt$ where $\lambda \ge 0$ is a smoothing parameter. If $\lambda =0$, the smoothing spline is any interpolating spline. If $\lambda =\infty$, the smoothing spline is Least Square line.

Smoothing splines is a Spline basis method that avoids the knot selection problem. Among all functions $f(x)\in C^2$, find one that minimizes the penalized RSS.

Facts

The unique analytic solution of smoothing spline is a Natural Cubic Splines with knots at the unique values of the $x_i$‘s

Link to original

Classification

Introduction

Bayes Classifier

Definition

${\hat{f}}_{\text{Bayes}}(x)=\underset{1\le k\le K}{\mathrm{argmax}}P(Y=k|X=x)=\underset{1\le k\le K}{\mathrm{argmax}}{p}_k(x){\pi }_k$ where $p_k(x)=P(x|Y=k)$ is conditional PDF of $x$ given $Y=k$ and ${\pi }_k=P(Y=k)$ is prior

Properties

Optimality of Bayes Rule

Bayes classifier ${\hat{f}}_{\text{Bayes}}(x)$ minimizes the prediction risk over all classifiers

Facts

For a given $x$, the Bayes classifier ${\hat{f}}_{\text{Bayes}}(x)$ is deterministic, i.e. it does not depend on the training sample. It can not be used in practice since $P(Y=k|X=x)$ is unknown.

Bayes classifier ${\hat{f}}_{\text{Bayes}}(x)$ maximizes the posterior pdf.

Link to original

Parametric Classifier

Linear Discriminant Analysis

Definition

$\underset{1\le k\le K}{\mathrm{argmax}}{\hat{f}}_k(x)=\underset{1\le k\le K}{\mathrm{argmax}}\left[\ln {\hat{\pi }}_k+x^{⊺}{\hat{\Sigma }}^{-1}{\hat{\mu }}_k-\frac{1}{2}{\hat{\mu }}_k^{⊺}{\hat{\Sigma }}^{-1}{\hat{\mu }}_k\right]$ where ${\hat{\pi }}_k=\frac{n_k}{n}$ is the sample ratio, ${\hat{\mu }}_k=\frac{1}{n_k}\sum _{i:Y_i=k}{X}_i$ is the sample mean, and $\hat{\Sigma }=\frac{1}{n-K}\sum _{k=1}^K\sum _{i:Y_i=k}(X_i-{\hat{\mu }}_k)(X_i-{\hat{\mu }}_k{)}^{⊺}$ is the sample variance covariance matrix

LDA is a Bayes Classifier with an assumption that $p_k(x)\sim N_p({\mu }_k,\Sigma )$

Facts

LDA assume homogeneity of variance-covariance among classes. Quadratic Discriminant Analysis may be used when the covariances are not equal.

Link to original

Quadratic Discriminant Analysis

Definition

$\underset{1\le k\le K}{\mathrm{argmax}}{\hat{f}}_k(x)=\underset{1\le k\le K}{\mathrm{argmax}}\left[\ln {\hat{\pi }}_k-\frac{1}{2}\ln |{\hat{\Sigma }}_k|-\frac{1}{2}(x-{\hat{\mu }}_k{)}^{⊺}{\hat{\Sigma }}_k^{-1}(x-{\hat{\mu }}_k)\right]$ where ${\hat{\pi }}_k=\frac{n_k}{n}$ is the sample ratio, ${\hat{\mu }}_k=\frac{1}{n_k}\sum _{i:Y_i=k}{X}_i$ is the sample mean, and ${\hat{\Sigma }}_k=\frac{1}{n_k-1}\sum _{i:Y_i=k}(X_i-{\hat{\mu }}_k)(X_i-{\hat{\mu }}_k{)}^{⊺}$ is the sample variance covariance matrix

Bayes Classifier with an assumption that $p_k(x)\sim N_p({\mu }_k,{\Sigma }_k)$

Link to original

Logistic Regression

Definition

Logistic regression is a Generalized Linear Model with Logit link function. Logistic regression models the log-odds of an event as a linear combination of independent variables. $\mathrm{logit}(\pi )=\ln \left(\frac{\pi }{1-\pi }\right)={\mathbf{x}}^{⊺}\mathbf{\beta }$ The probability is calculated as $\pi (\mathbf{x})=P(Y=1|X=\mathbf{x})=\frac{\exp ({\mathbf{x}}^{⊺}\mathbf{\beta })}{1+\exp ({\mathbf{x}}^{⊺}\mathbf{\beta })}=\frac{1}{1+\exp (-{\mathbf{x}}^{⊺}\mathbf{\beta })}$

Link to original

Nonparametric Classifier

Kernel Density Estimation

Definition

${\hat{f}}_h(x)=\frac{1}{n}\sum _{i=1}^n{K}_h(x-X_i)=\frac{1}{nh}\sum _{i=1}^{n}K\left(\frac{x-X_i}{h}\right)$ where $K\text{s.t.}{\int }_{-\infty }^{\infty }K(t)dt=1,{\int }_{-\infty }^{\infty }{K}^2(t)dt<\infty$ is the kernel, $K_h(x):=\frac{1}{h}K(\frac{x}{h})$ is the scaled kernel, and $h$ is a smoothing parameter (bandwidth, or window width)

KDE is a non-parametric method to estimate PDF of a random variable based on kernel and wrights.

Multidimensional KDE

${\hat{f}}_H(x)=\frac{1}{n}\sum _{i=1}^n{K}_H(\mathbf{x}-{\mathbf{x}}_i)=\frac{1}{n}|H{|}^{-1}\sum _{i=1}^{n}K(H^{-1}(\mathbf{x}-{\mathbf{x}}_i))$ where $K\text{s.t.}{\int }_{-\infty }^{\infty }K(\mathbf{u})d\mathbf{u}=1,K\ge 0$ is the kernel, $K_H(x):=|H{|}^{-1}K(H^{-1}x)$ is the scaled kernel, and $H$ is a positive-definite bandwidth matrix.

Facts

Widely used kernels

Link to original

Kernel Based Classifier

Definition

$\underset{1\le k\le K}{\mathrm{argmax}}{\hat{f}}_k(x)=\underset{1\le k\le K}{\mathrm{argmax}}{\hat{p}}_k(x){\hat{\pi }}_k=\underset{1\le k\le K}{\mathrm{argmax}}\left(\frac{1}{n}|H{|}^{-1}\sum _{i:Y_i=k}K(H^{-1}(\mathbf{x}-{\mathbf{X}}_i))\right)$ where ${\hat{p}}_k(x)=\frac{1}{n_k}|H{|}^{-1}\sum _{i:Y_i=k}K(H^{-1}(\mathbf{x}-{\mathbf{X}}_i))$ and ${\hat{\pi }}_k=\frac{n_k}{n}$

Bayes Classifier with an assumption that $p_k(x)$ is the Kernel Density Estimation.

Link to original

K-Nearest Neighbors Algorithm

Definition

Suppose $d_i(x):=d(x,X_i)$ is the distance between the training sample $X_i$ and the given point $x$. Let $d_{(1)}(x)\le d_{(2)}(x)\le \cdots \le d_{(n)}(x)$ $\underset{1\le k\le K}{\mathrm{argmax}}{\hat{f}}_k=\underset{1\le j\le K}{\mathrm{argmax}}{p}_j(x)=\underset{1\le j\le K}{\mathrm{argmax}}\frac{1}{k}\sum _{i=1}^{n}I(d_i(x)\le d_{(k)}(x))I(Y_i=j)$

The k-NN determines a sample’s class using the $k$-nearest training datum.

Facts

$k$ and $d$ are hyperparameters.

Link to original

Decision Tree

Definition

Decision tree consists of Classification Tree and Regression Tree.

Link to original

Regression Tree

Definition

Decision tree algorithm consists of growing and pruning step. Suppose $R_1(j,s)=\{\mathbf{x}|x_j\le s\},R_2(j,s)=\{\mathbf{x}|x_j>s\}$

1. growing: seek the splitting variable $j$ and split point $s$ that solves ${\min }_{j,s}\left[{\min }_{c_1}\sum _{i:{\mathbf{x}}_i\in R_1(j,s)}(y_i-c_1{)}^2+{\min }_{c_1}\sum _{i:{\mathbf{x}}_i\in R_2(j,s)}(y_i-c_2{)}^2\right]$
2. pruning: Suppose the number of terminal nodes in a tree $T$ is $|T|$ and $R_{ii=1,\dots ,|T|}$ is the split regions corresponding to the terminal node. For a tree $T$, define the cost complexity function. $C_{\alpha }(T)=\sum _{j=1}^{|T|}\sum _{i:{\mathbf{x}}_i\in R_2}(Y_i-{\bar{Y}}_j{)}^2+\alpha |T|$ where $\alpha$ is a tuning parameter regularizing complexity.

Regression function is estimated by $\hat{f}(x)=\sum _{m=1}^M{\hat{C}}_{m}I(x\in R_m)$ A non-parametric regression that partitions explanatory variables into a set of rectangles and takes the average of the response variables in each rectangle as an estimate of the regression function in that region.

Link to original

Classification Tree

Definition

Suppose $Y\in \{1,2,\dots ,K\}$, and $R_1(j,s)=\{\mathbf{x}|x_j\le s\},R_2(j,s)=\{\mathbf{x}|x_j>s\}$ Define a variable ${\hat{p}}_{mk}$ representing the proportion of class $k$ observations in a node $m$ ${\hat{p}}_{mk}=\frac{1}{n_m}\sum _{i:{\mathbf{x}}_i\in R_m}I(Y_i=k),k=1,2,\dots ,K$ We classify the observations in a node $m$ to class $k(m)=\underset{1\le k\le K}{\mathrm{argmax}}{\hat{p}}_{mk}$ Suppose the number of terminal nodes in a tree $T$ is $|T|$ and $R_{ii=1,\dots ,|T|}$ is the split regions corresponding to the terminal node. For a tree $T$, define the cost complexity function. $C_{\alpha }(T)=\sum _{m=1}^{|T|}{n}_m{Q}_m(T)+\alpha |T|$ where $Q_m(T)$ is an impunity function, $\alpha$ is a tuning parameter regularizing complexity.

The tree minimizes $C_{\alpha }$ is the selected as optimal.

Impunity Functions

• Misclassification error: $\frac{1}{n_m}\sum _{i:{\mathbf{x}}_i\in R_m}I(Y_i\ne k(m))=1-{\hat{p}}_{mk}$
• Gini index: $\sum _{k=1}^K{\hat{p}}_{mk}(1-{\hat{p}}_{mk})$
• Cross entropy on deviance: $-\sum _{k=1}^K{\hat{p}}_{m}k\ln ({\hat{p}}_{m}k)$

Link to original

Information Gain

Definition

The information gain of a node $t$ of a decision tree is defined as $IG(t)=Q(t)-\frac{n_L}{n_t}Q(t_L)-\frac{n_R}{n_t}Q(t_R)$ where $Q(t)$ is the impunity of node $t$, $n_t$ is the number of samples used in $t$, $t_L,t_R$ are children nodes of the $t$.

Link to original

Feature Importance

Definition

The feature importance of a feature $x_i$ used for Decision Tree is defined as $\mathcal{I}(x_i)=\frac{\sum _{t\in T(x_i)}IG(t)}{\sum _{j=1}^p\sum _{t\in T(x_j)}IG(t)}$ where $IG(t)$ is the Information Gain of a node $t$, and $T(x_i)$ is a set of nodes using the feature $x_i$

Link to original

Confusion Matrix

Definition

	Predicted Positive (PP)	Predicted Negative (PN)
Actual Positive	True Positive (TP)	False Negative (FN)
Actual Negative	False Positive (FP)	True Negative (TN)

Metrics

Accuracy

Definition

$\frac{\text{TP}+\text{TN}}{\text{TP}+\text{TN}+\text{FP}+\text{FN}}$

Link to original

Recall

Definition

$\frac{\text{TP}}{\text{TP}+\text{FN}}$

Recall, Sensitivity, or True positive rate means that the rate of correctly predicted cases out of all the actual positive cases..

Link to original

Precision

Definition

$\frac{\text{TP}}{\text{TP}+\text{FP}}$

Precision means that the rate of actually positive cases out of cases predicted as positive.

Link to original

Specificity

Definition

$\frac{\text{TN}}{\text{FP}+\text{TN}}$

Specificity means that the rate of correctly predicted cases out of all the actual negative cases.

Link to original

Type 1 Error

Definition

$\frac{\text{FP}}{\text{FP}+\text{TN}}$

Link to original

Type 2 Error

Definition

$\frac{\text{FN}}{\text{TP}+\text{FN}}$

Link to original

F-Score

Definition

F1 Score

$F_1=\frac{2}{{\text{recall}}^{-1}+{\text{precision}}^{-1}}=2\frac{\text{precision}\cdot \text{recall}}{\text{precision}+\text{recall}}$ The harmonic mean of Precision and Recall.

F-beta score

$F_{\beta }=(1+{\beta }^2)\frac{\text{precision}\cdot \text{recall}}{({\beta }^2\cdot \text{precision})+\text{recall}}$ where $\beta >0$

Recall is considered $\beta$ times as important as Precision.

Link to original

Positive Predictive Value

Definition

$\frac{\text{Sensitivity}\times \text{Prevalence}}{(\text{Sensitivity}\times \text{Prevalence})+((1-\text{Specificity})\times (1-\text{Prevalence}))}$ where $\text{Prevalence}=\frac{\text{positive cases}}{\text{total population}}$

Positive predictive value (in medical statistics and epidemiology) means that the rate of actually positive cases out of cases predicted as positive.

Link to original

Link to original

Receiver Operating Characteristic Curve

Definition

A receiver operating characteristic curve (ROC curve) is a plot of the True Positive Rate and False Negative Rate at each threshold setting.

AUC

The area under the ROC curve is called AUC (Area under curve)

Link to original

Support Vector Machines

Hyperplane

Definition

Vector Equation for a hyperplane

$f(\mathbf{x})={\beta }_0+{\mathbf{\beta }}^{⊺}\mathbf{x}=0$

Facts

Suppose the dimension of $\mathbf{x}$ is $p$

• $p=1$: point in $1$-dimensional space.
• $p=2$: line in $2$-dimensional space.
• $p=3$: plane in $3$-dimensional space.
• $p>3$: hyperplane in $p$-dimensional space.

$\forall {\mathbf{x}}_1,{\mathbf{x}}_2\in H,{\mathbf{\beta }}^{⊺}({\mathbf{x}}_1-{\mathbf{x}}_2)=0\Rightarrow \mathbf{\beta }\perp H$

$\mathbf{\beta }$ is perpendicular to the surface $H$

$\forall \mathbf{x}\in {\mathbb{R}}^{p+1},d_s(\mathbf{x},H)={\mathbf{\beta }}^{\ast ⊺}(\mathbf{x}-{\mathbf{x}}_0)=\frac{1}{||\mathbf{\beta }||}({\mathbf{\beta }}^{⊺}\mathbf{x}+{\beta }_0-\underset{=0}{\underbrace{({\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_0)}})=\frac{1}{||\mathbf{\beta }||}({\mathbf{\beta }}^{⊺}\mathbf{x}+{\beta }_0)=\frac{f(\mathbf{x})}{||f^{\prime }(\mathbf{x})||}$ where $d_s(\cdot )$ is a signed distance, ${\mathbf{\beta }}^{\ast }:=\mathbf{\beta }/||\mathbf{\beta }||$, and ${\mathbf{x}}_0\in H$

Link to original

Kernel Function

Definition

$K:{\mathbb{R}}^p\to \mathbb{R},K({\mathbf{x}}_i,{\mathbf{x}}_j)=⟨\varphi ({\mathbf{x}}_i),\varphi ({\mathbf{x}}_j)⟩$ where $\varphi :{\mathbb{R}}^p\to \mathcal{H}$

The kernel function returns the result of Inner product in $\mathcal{H}$ by using only the original input data.

Examples

Some common kernel functions $K({\mathbf{x}}_i,{\mathbf{x}}_j)$ are as follows:

• Linear: $⟨{\mathbf{x}}_i,{\mathbf{x}}_j⟩$
• Polynomial: $(⟨{\mathbf{x}}_i,{\mathbf{x}}_j⟩+c{)}^{d}c\ge 0,n\ge 1$
• Gaussian radial basis function: $\exp (-\gamma ||{\mathbf{x}}_i-{\mathbf{x}}_j|{|}^2),\gamma >0$
• Sigmoid: $\tanh (\kappa ⟨{\mathbf{x}}_i,{\mathbf{x}}_j⟩+c),\kappa >0,c<0$

Link to original

Support Vector Machine

Definition

Hard-Margin Support Vector Machine

Assume that we have a learning set $\mathcal{L}=\{({\mathbf{x}}_i,y_i)|i=1,2,\dots ,n\},{\mathbf{x}}_i\in {\mathbb{R}}^p,y_i\in \{-1,+1\}$ Suppose given two classes of data can separate by a Hyperplane without error. The hyperplane is called a separating hyperplane (SH)

Define $d_{-}:=\underset{i}{\min }\mathrm{dist}(\text{SH},{\mathbf{x}}_i),{\mathbf{x}}_i\in \{{\mathbf{x}}_i|y_i=-1\}$, $d_{+}:=\underset{i}{\min }\mathrm{dist}(\text{SH},{\mathbf{x}}_i),{\mathbf{x}}_i\in \{{\mathbf{x}}_i|y_i=+1\}$, and the margin of SH $d:=d_{-}+d_{+}$ A SH which maximizes its margin ($d$) is called an optimal separating hyperplane (OSH). To find OSH, set linear constraints ${\beta }_0$ and $\mathbf{\beta }$ satisfy $\{\begin{array}{ll}{\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_i\ge +1& y_i=+1\\ {\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_i\le -1& y_i=-1\end{array}\iff y_i({\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_i)\ge +1,i=1,\dots ,n$ where the minimum distance $1$ is arbitrary and may differ.

Let $H_{+}:{\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_i=+1$ and $H_{-}:{\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_i=-1$. Then the points lying either on $H_{+}$ or $H_{-}$ are called support vectors. If ${\mathbf{x}}_{+}\in H_{+}$ and ${\mathbf{x}}_{-}\in H_{-}$, then $d_{+}=d_{-}=\frac{1}{||\mathbf{\beta }||}$ and $d=\frac{2}{||\mathbf{\beta }||}$

Therefore, the OHS can be obtained by a Convex Optimization problem. It can be solved by Method of Lagrange Multipliers $L_P(\mathbf{\beta },{\beta }_0,\mathbf{\alpha })=\frac{1}{2}||\mathbf{\beta }|{|}^2-{\sum }_{i=1}^n{\alpha }_i[y_i({\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_i)-1]$ with $0\le \mathbf{\alpha }$

By Duality of optimization problem, we have the dual optimization problem is defined as ${\max }_{\mathbf{\alpha }}{L}_D(\mathbf{\alpha })\text{subject to}0\le \mathbf{\alpha },{\mathbf{\alpha }}^{⊺}\mathbf{y}=0$ where $\mathbf{H}=(y_i{y}_j{\mathbf{x}}_i^{⊺}{\mathbf{x}}_j)$

And the dual Lagrangian function is defined as $L_D(\mathbf{\alpha })={\sum }_{i=1}^n{\alpha }_i-\frac{1}{2}{\sum }_{i=1}^n{\sum }_{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^{⊺}{\mathbf{x}}_j=1_n^{⊺}\mathbf{\alpha }-\frac{1}{2}{\mathbf{\alpha }}^{⊺}\mathbf{H}\mathbf{\alpha }$

The primal optimization problem is convex and satisfies KKT Conditions. Thus, holds Strong Duality and the solution of the dual problem is the same as the primal problem.

The optimal parameter is obtained as $\hat{\mathbf{\beta }}=\sum _{i\in \text{sv}}{\hat{\alpha }}_i{y}_i{\mathbf{x}}_i,{\hat{\beta }}_0=\frac{1}{|\text{sv}|}\sum _{i\in \text{sv}}\left(\frac{1-y_i{\mathbf{x}}_i^{⊺}\hat{\mathbf{\beta }}}{y_i}\right)$ where $\text{sv}$ is an index set of support vectors

The optimal hyperplane can be written as $\hat{f}(\mathbf{x})={\hat{\beta }}_0+{\hat{\mathbf{\beta }}}^{⊺}\mathbf{x}$ and the classification rule is given by $C(\mathbf{x})=\mathrm{sign}(\hat{f}(\mathbf{x}))$

Soft-Margin Support Vector Machine

$\min \frac{1}{2}||\mathbf{\beta }|{|}^2+C\sum _{i=1}^n{\xi }_i\text{subject to}{y}_i({\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_i)\ge +1-{\xi }_i,{\xi }_i\ge 0,i=1,\dots ,n$ where $C$ is the regularization parameter, and $\mathbf{\xi }$ is called a slack variable. If ${\xi }_i=0$, the point is out of margin. On the other hand, if ${\xi }_i>0$, then the point is within the margin.

The Lagrangian primal function is defined as $L_P(\mathbf{\beta },{\beta }_0,\mathbf{\alpha },\mathbf{\eta })=\frac{1}{2}||\mathbf{\beta }|{|}^2+C\sum _{i=1}^n{\xi }_i-{\sum }_{i=1}^n{\alpha }_i[y_i({\beta }_0+{\mathbf{\beta }}^{⊺}{\mathbf{x}}_i)-(1-{\xi }_i)]-{\sum }_{i=1}^n{\eta }_i{\xi }_i$ with $0\le \mathbf{\alpha }$ and $0\le \mathbf{\eta }$.

And the dual function is defined as $L_D(\alpha )={\sum }_{i=1}^n{\alpha }_i-\frac{1}{2}{\sum }_{i=1}^n{\sum }_{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^{⊺}{\mathbf{x}}_j=1_n^{⊺}\mathbf{\alpha }-\frac{1}{2}{\mathbf{\alpha }}^{⊺}\mathbf{H}\mathbf{\alpha }$ with ${\mathbf{\alpha }}^{⊺}\mathbf{y}=0$ and $0\le \mathbf{\alpha }\le C{1}_n$ where $\mathbf{H}=(y_i{y}_j{\mathbf{x}}_i^{⊺}{\mathbf{x}}_j)$

and the dual optimization problem is defined as ${\max }_{\mathbf{\alpha }}{L}_D(\mathbf{\alpha })\text{subject to}{\mathbf{\alpha }}^{⊺}\mathbf{y}=0,0\le \mathbf{\alpha }\le C{1}_n$ The primal optimization problem is convex and satisfies KKT Conditions. Thus, holds Strong Duality and the solution of the dual problem is the same as the primal problem.

The optimal parameter is obtained as $\hat{\mathbf{\beta }}=\sum _{i\in \text{sv}}{\hat{\alpha }}_i{y}_i{\mathbf{x}}_i,{\hat{\beta }}_0=\frac{1}{|\text{sv}|}\sum _{i\in \text{sv}}\left(\frac{1-y_i{\mathbf{x}}_i^{⊺}\hat{\mathbf{\beta }}}{y_i}\right)$ where $\text{sv}$ is an index set of support vectors.

Non-Linear Support Vector Machine

Non-linear SVM finds an optimal separating Hyperplane in high-dimensional feature space $\mathcal{H}$. It accomplished by the kernel trick. The kernel trick is that instead of computing inner products in $\mathcal{H}$, compute them using a non-linear Kernel Function in input space.

Hard-Margin Non-Linear Support Vector Machine

If the data can be separated in $\mathcal{H}$, then the dual optimization problem is defined as ${\max }_{\mathbf{\alpha }}\left(1_n^{⊺}\mathbf{\alpha }-\frac{1}{2}{\mathbf{\alpha }}^{⊺}\mathbf{H}\mathbf{\alpha }\right)\text{subject to}0\le \mathbf{\alpha },{\mathbf{\alpha }}^{⊺}\mathbf{y}=0$ where $\mathbf{H}=(y_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j))$

The optimal separating Hyperplane in the $\mathcal{H}$ is $\hat{f}(\mathbf{x})={\hat{\beta }}_0+\sum _{i\in \text{sv}}{\hat{\alpha }}_i{y}_{i}K({\mathbf{x}}_i,{\mathbf{x}}_j)$

and the decision rule is defined as $C(\mathbf{x})=\mathrm{sign}(\hat{f}(\mathbf{x}))$

Soft-Margin Non-Linear Support Vector Machine

In the non-separable case, the dual problem is defined as ${\max }_{\mathbf{\alpha }}\left(1_n^{⊺}\mathbf{\alpha }-\frac{1}{2}{\mathbf{\alpha }}^{⊺}\mathbf{H}\mathbf{\alpha }\right)\text{subject to}0\le \mathbf{\alpha }\le C{1}_n,{\mathbf{\alpha }}^{⊺}\mathbf{y}=0$ where $\mathbf{H}=(y_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j))$

The optimal separating Hyperplane in the $\mathcal{H}$ is $\hat{f}(\mathbf{x})={\hat{\beta }}_0+\sum _{i\in \text{sv}}{\hat{\alpha }}_i{y}_{i}K({\mathbf{x}}_i,{\mathbf{x}}_j)$

and the decision rule is defined as $C(\mathbf{x})=\mathrm{sign}(\hat{f}(\mathbf{x}))$

Link to original

Support Vector Regression

Definition

Support vector regression (SVR) depends only on a subset of the training data, because the loss function $L_{ϵ}=(|y-f(\mathbf{x})|-ϵ{)}_{+}$ ignores any training data close to the model prediction, within a band or tube.

The primal optimization problem is defined as

\min &\left( \cfrac{1}{2}||\boldsymbol{\beta}||^{2} + C\sum\limits_{i=1}^{n}(\xi_{i} + \xi'_{i}) \right)\\ \text{subject to}\ &y_{i} - (\beta_{0} + \boldsymbol{\beta}^{\intercal}\mathbf{x}_{i}) \leq \epsilon + \xi'_{i},\\ &(\beta_{0} + \boldsymbol{\beta}^{\intercal}\mathbf{x}_{i}) - y_{i} \leq \epsilon + \xi_{i},\\ &\ \xi'_{i} \geq 0, \ \xi_{i} \geq 0\quad i=1,\dots,n \end{aligned}$$ The term $\cfrac{1}{2}||\boldsymbol{\beta}||^{2}$ in the objective function, which appears with the intention of maximizing the margin of SVM, acts as a regularization parameter in SVR. The Lagrangian primal function is defined as $$ \begin{aligned} L_{P} &= \frac{1}{2}||\boldsymbol{\beta}||^{2} + C\sum_{{i=1}}^{{n}} (\xi_{{i}} + \xi'_{{i}}) \\ &+ \sum_{{i=1}}^{{n}} \alpha'_{{i}} \left( y_{{i}} - (\beta_{0} + \boldsymbol{\beta}^{\intercal} \mathbf{x}_{{i}}) - \epsilon - \xi'_{{i}} \right) + \sum_{{i=1}}^{{n}} \alpha_{{i}} \left( (\beta_{0} + \boldsymbol{\beta}^{\intercal} \mathbf{x}_{{i}}) - y_{{i}} - \epsilon - \xi_{{i}} \right)\\ &- \sum_{{i=1}}^{{n}} \mu'_{{i}} \xi'_{{i}} - \sum_{{i=1}}^{{n}} \mu_{{i}} \xi_{{i}} \end{aligned} $$ with $\mathbb{\alpha}, \mathbb{\alpha}', \boldsymbol{\mu}, \boldsymbol{\mu}' \geq \mathbf{0}$ The dual optimization is defined as $$ \begin{aligned} \max\ &\left( \mathbf{y}^{\intercal} (\mathbf{\alpha} - \mathbf{\alpha'}) - \epsilon \mathbf{1}^{\intercal} (\mathbf{\alpha} + \mathbf{\alpha'}) - \frac{1}{2} (\mathbf{\alpha} - \mathbf{\alpha'})^{\intercal} \mathbf{K} (\mathbf{\alpha} - \mathbf{\alpha'}) \right) \\ \text{subject to}\ &\mathbf{1}_{n}^{\intercal} (\mathbf{\alpha} - \mathbf{\alpha'}) = 0, \mathbf{0} \leq \mathbf{a}, \mathbf{a}' \leq C\mathbf{1}_{n}\quad i=1,\dots,n \end{aligned}$$ And the dual Lagrangian function is defined as $$\begin{aligned} L_{D} = &\ \mathbf{y}^{\intercal} (\mathbf{\alpha} - \mathbf{\alpha'}) - \epsilon \mathbf{1}^{\intercal} (\mathbf{\alpha} + \mathbf{\alpha'}) - \frac{1}{2} (\mathbf{\alpha} - \mathbf{\alpha'})^{\intercal} \mathbf{K} (\mathbf{\alpha} - \mathbf{\alpha'}) \\ &+ \lambda \mathbf{1}_{n}^{\intercal} (\mathbf{\alpha} - \mathbf{\alpha'})\\ &- \boldsymbol{\mu}^{\intercal} \mathbf{\alpha} - \boldsymbol{\mu}'^{\intercal} \mathbf{\alpha'}+ \boldsymbol{\mu}_{C}^{\intercal} (C\mathbf{1}_{n} - \mathbf{\alpha}) + \boldsymbol{\mu}_{C}'^{\intercal} (C\mathbf{1}_{n} - \mathbf{\alpha'}) \end{aligned}$$ with $\boldsymbol{\mu}, \boldsymbol{\mu}', \boldsymbol{\mu}_{C}, \boldsymbol{\mu}_{C}' \geq \mathbf{0}$ where $\mathbf{K}$ is a [[Kernel Function]].Link to original

Ensemble Learning

Bootstrap Aggregating

Definition

Regression Setting

Given a training set $Z=\{(x_i,y_i)|1=1,\dots ,n\}$, draw a bootstrap sample $\{Z^{\ast b}|b=1,\dots ,B\}$ from training data. Bagging estimator of $f$ at $x$ is defined as ${\hat{f}}_{\text{bag}}(x)=\frac{1}{B}\sum _{b=1}^B{\hat{f}}^{\ast b}(x)$ where ${\hat{f}}^{\ast b}(x)$ is the prediction at $x$ based on a new training set $Z^{\ast b}$

Classification Setting

Given a training set $Z=\{(x_i,y_i)|1=1,\dots ,n\}$, draw a bootstrap sample $\{Z^{\ast b}|b=1,\dots ,B\}$ from training data. Bagging estimator of $f$ at $x$ is defined as ${\hat{f}}_{\text{bag}}(x)=\underset{1\le k\le K}{\mathrm{argmax}}\#\{b|{\hat{f}}^{\ast b}(x)=k\}$ where ${\hat{f}}^{\ast b}(x)$ is the prediction at $x$ based on a new training set $Z^{\ast b}$

Facts

Bagging in a classification setting with zero-one loss often fails. Bagging a good classifier can make it better, but bagging a bad classifier can make it worse.

Bagging reduces the variance of an estimated prediction function. It seems to work especially well for high-variance, low-bias procedures, such as trees.

Link to original

Boosting

Definition

Boosting builds a strong learner by combining many weak learners whose accuracies are slightly better than a random guess.

Examples

AdaBoost

Link to original

AdaBoost

Definition

The AdaBoost (Adaptive Boosting) is the weighted sum of weak learners that are robust to outliers and noise.

Algorithm

Consider a 2-class problem with $Y\in \{-1,1\}$

1. Initialize the weights $w_i=\frac{1}{n},i=1,2,\dots ,n$
2. Repeat for $m=1,2,\dots ,M$:
   1. Fit a weak classifier $\delta$ that minimizes the weighted error rate $\text{err}=\sum _{i=1}^n{w}_{i}I(y_i\ne \delta (x_i))$ and call the fitted classifier $f_m$, and its corresponding error rate ${\text{err}}_m$
   2. Compute $c_m=\ln \left(\frac{1-{\text{err}}_m}{{\text{err}}_m}\right)=\mathrm{logit}(1-{\text{err}}_m)$
   3. Update the weights $w_i$ by $w_i=\frac{w_i\exp [c_{m}I(y_i\ne f_m(X_i))]}{\sum _{j=1}^n{w}_j\exp [c_{m}I(y_j\ne f_m(X_j))]}$
3. Output the classifier $f(x)=\mathrm{sgn}\left(\sum _{m=1}^M{c}_m{f}_m(x)\right)$

Facts

AdaBoost is equivalent to Gradient Boosting using the exponential loss $L(y,f(x))=\exp (-yf(x))$

Link to original

Gradient Boosting

Definition

The gradient boosting is a type of Forward Stagewise Additive Modeling that uses gradients to calculate the residuals.

Algorithm

1. Initialize the model $f_0(x)=\underset{\mathbf{\gamma }}{\mathrm{argmin}}\sum _{i=1}^{n}L(y_i,\mathbf{\gamma })$
2. Repeat for $m=1,2,\dots ,M$:
   1. Calculate the residuals for each data point $r_{im}=-{\left[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}\right]}_{f=f_{m-1}}$ where $L$ is a Loss Function
   2. Fit weak learners to the residuals $h_m(x)=\underset{h}{\mathrm{argmin}}\sum _{i=1}^n(r_{im}-h(x_i){)}^2$
   3. Calculate a learning rate ${\gamma }_m=\underset{\gamma }{\mathrm{argmin}}\sum _{i=1}^{n}L(y_i,f_{m-1}(x_i)+\gamma h_m(x_i))$
   4. Update model using the fitted weak learners $f_m(x)=f_{m-1}(x)+\gamma h_m(x)$
3. Output the final model $\hat{f}(x)=f_0(x)+\sum _{i=1}^m{\gamma }_m{h}_m(x)$

Link to original

Forward Stagewise Additive Modeling

Definition

The forward stagewise additive modeling sequentially adds new basis functions to the model of the previous step without adjusting the parameters and coefficients of those that have already been added.

Algorithm

1. Initialize $f_0(x)=0$
2. For $m=1,2,\dots ,M$
   1. Compute $({\beta }_m,{\mathbf{\gamma }}_m)=\underset{\beta ,\mathbf{\gamma }}{\mathrm{argmin}}\sum _{i=1}^{n}L(y_i,f_{m-1}(x_i)+\beta b(x_i;\mathbf{\gamma }))$
   2. Set $f_m(x)=f_{m-1}(x)+{\beta }_{m}b(x;{\mathbf{\gamma }}_m)$ where $b(x;\mathbf{\gamma })$ is a basis function and $L(y,f(x))$ is a Loss Function

Link to original

Random Forest

Definition

Random forest constructs a multitude of de-correlated decision trees at training time and make a prediction through Bagging.

Algorithm

1. For $b=1,\dots ,B$:
   1. Draw a size $n$ bootstrap sample $\{Z^{\ast b}|b=1,\dots ,B\}$ from training data.
   2. Grow a random-forest tree $T_b$ to the bootstrapped data, by recursively repeating the following steps for each terminal node of the tree, until the minimum node size $\text{nmin}$ is reached.
      1. Select $m<<p$ variables at random.
      2. Pick the best variable and split point among the selected variables.
      3. Split the node into two children nodes.
2. Output the ensemble of trees $\{T_b{\}}_1^B$ to make a prediction at a new point $x$
   • Regression: ${\hat{f}}_{\text{rf}}^B(x)=\frac{1}{B}\sum _{b=1}^B{T}_b(x)$
   • Classification: $C_{\text{rf}}^B(x)=\underset{1\le b\le B}{\mathrm{argmax}}\#\{b|{\hat{C}}_b(x)=b\}$ where ${\hat{C}}_b(x)$ is the class prediction of the $b$th random-forest tree.

Facts

Selection of hyperparameter $m$ is recommended as

• For classification: $\min (\lfloor \sqrt{p}\rfloor ,1)$
• For regression: $\min (\lfloor \frac{p}{3}\rfloor ,1)$

Link to original

Neural Networks

Projection Pursuit Regression

Definition

$f(\mathbf{x})={\sum }_{m=1}^M{f}_m({\mathbf{w}}_m^{⊺}\mathbf{x})+\mathbf{ϵ}$ where $f_m$ are unspecified function

Facts

PPR is a single-layered Neural Network where each neuron uses a different activation function and has no bias term.

Link to original

Activation Function

Definition

The activation function of a node in an artificial neural network is a function that calculates the output of the node based on the linear combination of its inputs. It is used to add a non-linearity to the model.

Examples

Logistic Function

Definition

$\sigma (x)=\mathrm{logistic}(x)={\mathrm{logit}}^{-1}(x)=\frac{1}{1+\exp (-x)}$

The logistic function is inverse function of Logit.

Facts

Sigmoid activation function is vulnerable to vanishing gradient problem. $\frac{d}{dx}\sigma (x)=\sigma (x)(1-\sigma (x))$ The image of the derivative of the sigmoid function is $(0,0.25]$. For this reason, after passing node with sigmoid Activation Function, the gradient is decreased

Also, with the sigmoid Activation Function, if all the inputs are positive, then all the gradients also positive.

Link to original

Hyperbolic Tangent Function

Definition

$\tanh (x)=\frac{\sinh x}{\cosh x}=\frac{e^x-e^{-x}}{e^x+e^{-x}}=\frac{e^{2x}-1}{e^{2x}+1}$

Link to original

Rectified Linear Unit Function

Definition

$f(x)=\max (0,x)$

Facts

If an initial value is negative, it is never updated.

Link to original

ReLU6

Definition

$f(x)=\min (\max (0,x),6)$

Link to original

Gaussian-Error Linear Unit

Definition

GELU is a smooth approximation of ReLU.

$f(x)=x\Phi (x)$ where $\Phi$ is the CDF of the standard normal distribution.

Link to original

Parametric ReLU

Definition

$f(x)=\max (\alpha x,x)$ where $\alpha \le 1$ is a hyperparameter

Facts

If $\alpha =0.01$, it is called a Leaky ReLU

Link to original

Exponential Linear Unit

Definition

$f(x)=\{\begin{array}{ll}x& x\ge 0\\ \alpha (e^x-1)& x<0\end{array}$ where $\alpha \ge 0$ is a hyperparameter

Link to original

Swish Function

Definition

$f(x)=x\sigma (\beta x)=\frac{x}{1+e^{-\beta x}}$ where $\sigma$ is Sigmoid Function, and $\beta$ is a hyperparameter

When $\beta =1$, the function is called a sigmoid liniear unit (SiLU).

Link to original

Link to original

Sum of Squared Errors Loss

Definition

Suppose the number of data is $n$, then the sum of squared error loss (SSE) is defined as the sum of Squared Error Loss of all data. $R(\theta )=\sum _{i=1}^n(y_i-f(x_i){)}^2$

Link to original

Cross-Entropy Loss

Definition

Suppose the number of data is $n$ and the number of classes is $K$, then the cross entropy loss is defined as $R(\theta )=-\sum _{i=1}^n\sum _{k=1}^K{y}_{ik}\ln f_k(x_i)$

Link to original

Neural Network

Definition

Neural network can be thought as a non-linear generalization of linear model.

The derived features $Z_m$ are constructed by an Activation Function and linear combinations of the inputs. $Z_m=\sigma ({\alpha }_{0m}+{\alpha }_m^{⊺}X),m=1,\dots ,M$ where $\sigma$ is an Activation Function

Output nodes are the linear combinations of $Z$ $T_k={\beta }_{0k}+{\beta }_k^{⊺}Z,k=1,\dots ,K$ And the output is modeled by a function of a linear combinations of $Z_m$ $f_k(X)=g_k(T),k=1,\dots ,K$ where $g_k(T)$ is called an output function.

Facts

The output function $g_k(T)$ varies by the problem. For regression $g_k$ is Identity Function, and for $k$-class classification Softmax Function $\sigma$ is used as the $g_k$.

For regression problem, Sum of Squared Errors Loss is used as Loss Function. For classification problem, we use Cross-Entropy Loss

With the softmax activation function and the Cross-Entropy Loss, the neural network model is exactly a linear Logistic Regression model in the hidden units.

The parameters of a neural network are estimated by Backpropagation.

Neural network is especially effective in problem with a high signal-to-noise ratio.

Link to original

Dropout

Definition

Dropout is a regularization technique used for Neural Network. Dropout randomly dropping out or omitting units during training process of a Neural Network.

Link to original

Clustering Analysis

K-Means Clustering

Definition

The k-means clustering algorithm solves the following optimization problem $\underset{\mathbf{S}}{\min }\sum _{k=1}^K\sum _{x_i\in S_i}||x_i-m_k|{|}^2$ where $K$ is the number of clusters, a Partition $\mathbf{S}=\{S_k|k=1,\dots ,K\}$ is a set of clusters, and $m_k=\frac{1}{|S_k|}\sum _{x_i\in S_i}{x}_i$ The k-means clustering algorithm aims to partition observations into clusters in which each observation belongs to the cluster with the nearest mean.

Algorithm

1. Initialize $\{m_i^{(1)}|i=1,\dots ,K\}$.

2. Assignment step: Assign each observation to the cluster with the nearest mean

   $S_i^{(t)}=\left\{x_p|\underset{1\le j\le K}{\mathrm{argmin}}||x_p-m_j^{(t)}|{|}^2\right\}$ where each $x_p$ is assigned to exactly one $S_i^{(t)}$

3. Update step: Recalculate means for observations assigned to each cluster. $m_i^{(t+1)}=\frac{1}{|S_i^{(t)}|}\sum _{x_j\in s_i^{(t)}}{x}_j$

4. Iterate step 2 and 3 until the within cluster variation converges.

Facts

The k-means clustering uses spherical metric (Euclidean distance) to group data, so that it is useful only when clusters are convex sets.

Link to original

Self-Organizing Map

Definition

A self-organizing map (SOM) is a clustering method that produces a low-dimensional representation of a higher-dimensional data set while preserving the Topological Manifold structure of the data.

The algorithm fits a grid to high-dimensional data and assigns the data to the fitted nodes (prototypes) of the grid.

Link to original

Spectral Clustering

Definition

Spectral clustering technique make use of spectrum of the similarity matrix of the data to perform dimensionality reduction before clustering.

Algorithms

Apply Laplacian Eigenmap to the given data ${\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_n\in {\mathbb{R}}^l$. ${\mathbf{x}}_i\in {\mathbb{R}}^l\to [{\mathbf{z}}_2,{\mathbf{z}}_3,\dots ,{\mathbf{z}}_m{]}_i\in {\mathbb{R}}^m$

Form an $n\times k$ sub matrix $\mathbf{T}$ using the first $k$-columns of the embedded matrix $\mathbf{Z}$, and normalize each row to norm $1$. $\mathbf{T}=[{\mathbf{z}}_1,{\mathbf{z}}_2,\dots ,{\mathbf{z}}_k]$

Apply clustering algorithm (e.g. K-Means Clustering) to ${\mathbf{t}}_1,{\mathbf{t}}_2,\dots ,{\mathbf{t}}_n$, where ${\mathbf{t}}_i$ is the $i$-th row of $\mathbf{T}$.

Mathematical Background

Consider a cluster assignment vector ${\mathbf{z}}_i$ for each data point. Then, clustering $n$ observations is corresponding to estimating ${\mathbf{z}}_i$‘s The entries $a_{ij}$ of the Adjacency Matrix represents the similarity between points $i$ and $j$.

Under the assumption that the close data points (large $a_{ij}$) have a similar label (${\mathbf{z}}_i\approx {\mathbf{z}}_j$), the optimization problem is set up that minimizing the difference between assignments for similar points. $\underset{\mathbf{Z}}{\mathrm{argmin}}\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{a}_{ij}({\mathbf{z}}_i-{\mathbf{z}}_j{)}^2\text{subject to}{\mathbf{Z}}^{⊺}\mathbf{Z}=I$ where the constraint is imposed to avoid the trivial solution ${\mathbf{z}}_i=0$.

In a matrix notation, the problem is $\underset{\mathbf{Z}}{\mathrm{argmin}}\mathrm{tr}({\mathbf{Z}}^{⊺}\mathbf{LZ})\text{subject to}{\mathbf{Z}}^{⊺}\mathbf{Z}=I$

When ${\mathbf{z}}_i\approx {\mathbf{z}}_j$, $a_{ij}$ is large and when ${\mathbf{z}}_i\ne {\mathbf{z}}_j$, $a_{ij}$ is small. So, $a_{ij}$ works as the weight for each pair in the optimization.

The Lagrangian function is defined as $L_P={\mathbf{Z}}^{⊺}\mathbf{LZ}-\Lambda ({\mathbf{Z}}^{⊺}\mathbf{Z}-1)$ And the solution of the problem is given by an Eigenvalue problem. $\frac{\partial L_p}{\partial \mathbf{Z}}=2\mathbf{LZ}-2\Lambda \mathbf{Z}=0\Rightarrow \mathbf{LZ}=\Lambda \mathbf{Z}\Rightarrow {\mathbf{Z}}^{⊺}\mathbf{LZ}=\Lambda$ The solution $\mathbf{Z}$ is an $n\times n$ matrix of eigenvectors sorted in ascending by their corresponding eigenvalues.

Link to original

Procrustes Analysis

Definition

Procrustes Transformation without Scaling

Consider two $n\times p$ matrices ${\mathbf{X}}_1$ and a target ${\mathbf{X}}_2$. What we want is to find a Procrustes transformation of $X_1$ whose result is closest to $X_2$,

The optimization problem is defined as $\underset{\mu ,\mathbf{R}}{\min }||{\mathbf{X}}_2-({\mathbf{X}}_1\mathbf{R}+1_n\mathbf{\mu })|{|}_F$ where $\mathbf{R}$ is a $p\times p$ Orthonormal Matrix (perform rotation and reflection), ${\mathbf{\mu }}_{1\times p}$ act as location parameter, and $||\cdot |{|}_F$ is a Frobenius Norm.

Let ${\tilde{x}}_1$ and ${\tilde{x}}_2$ be the columnwise mean vectors of the matrices, and ${\tilde{\mathbf{X}}}_1$ and ${\tilde{\mathbf{X}}}_2$ be the demeaned matrices. Consider the SVD ${\tilde{\mathbf{X}}}_1^{⊺}{\tilde{\mathbf{X}}}_2=\mathbf{UD}{\mathbf{V}}^{⊺}$. Then, the solution of the optimization problem is given by $\hat{\mathbf{R}}=\mathbf{U}{\mathbf{V}}^{⊺},\hat{\mu }={\tilde{x}}_2-\hat{\mathbf{R}}{\tilde{x}}_1$ and the minimal distance is referred to as the Procrustes distance.

Procrustes Transformation with Scaling

Consider demeaned matrices ${\mathbf{X}}_1$ and ${\mathbf{X}}_2$. The Procrustes distance with scaling is obtained from more general optimization problem. $\underset{\beta ,\mathbf{R}}{\min }||{\mathbf{X}}_2-\beta {\mathbf{X}}_1\mathbf{R}|{|}_F$ where $\beta >0$ is a positive scalar.

The solution for $\mathbf{R}$ is as before ($\hat{\mathbf{R}}=\mathbf{U}{\mathbf{V}}^{⊺}$), with $\hat{\beta }=\mathrm{tr}(D)/||{\mathbf{X}}_1|{|}_F^2$

Procrustes Average

Consider demeaned and scaled matrices $\{{\mathbf{X}}_l|l=1,2,\dots ,L\}$. Procrustes average problem finds the shape $\mathbf{M}$ closest in average squared Procrustes distance to all the given shapes. $\underset{\{{\mathbf{R}}_l{\}}_1^L,\mathbf{M}}{\min }||{\mathbf{X}}_l{\mathbf{R}}_l-\mathbf{M}|{|}_F^2$ This is solved by a simple algorithm

1. Initialize $\mathbf{M}={\mathbf{X}}_1$
2. Solve the $L$ Procrustes rotation problems with $\mathbf{M}$ fixed, yielding ${\mathbf{X}}_l^{\prime }\leftarrow \mathbf{X}{\hat{\mathbf{R}}}_l$
3. Let $\mathbf{M}\leftarrow \frac{1}{L}\sum _{l=1}^L{\mathbf{X}}_l^{\prime }$
4. Iterate step 1 and 2 until it converges.

Link to original

Kernel Principal Component Analysis

Definition

Consider an $n\times p$ demeaned matrix $\mathbf{X}$ By SVD $\mathbf{X}=\mathbf{UD}{\mathbf{V}}^{⊺}$, where $\mathbf{U},\mathbf{V}$ are orthonormal matrices and $\mathbf{D}$ is a Diagonal Matrix. Then, $\mathbf{X}{\mathbf{X}}^{⊺}=\mathbf{UD}{\mathbf{V}}^{⊺}(\mathbf{UD}{\mathbf{V}}^{⊺}{)}^{⊺}=\mathbf{U}{\mathbf{D}}^2{\mathbf{U}}^{⊺}$ By PCA $\mathbf{Z}:=\mathbf{XV}=\mathbf{UD}$. For a linear kernel $\mathbf{K}=\mathbf{X}{\mathbf{X}}^{⊺}$, $\mathbf{K}=\mathbf{Z}D{\mathbf{U}}^{⊺}\Rightarrow K(D{\mathbf{U}}^{⊺}{)}^{-1}=\mathbf{Z}$. $\because \mathbf{U}$ is an Orthonormal Matrix, $\mathbf{Z}=\mathbf{KU}{\mathbf{D}}^{-1}\iff {\mathbf{z}}_{im}=\sum _{j=1}^n\frac{{\mathbf{u}}_{jm}}{d_m}K({\mathbf{x}}_i,{\mathbf{x}}_j)$ The kernel principal components are given by solution of the optimization problem. $\underset{g_i\in {\mathcal{H}}_K}{\max }\mathrm{Var}{g}_i(\mathbf{X})\text{subject to}||g_i|{|}_{{\mathcal{H}}_K}=1,\forall j<i,⟨g_i,g_j{⟩}_{{\mathcal{H}}_K}=0$ where $g_i(\mathbf{x})=\sum _{j=1}^n\frac{{\mathbf{u}}_{ji}}{d_i}K(\mathbf{x},{\mathbf{x}}_j)$

Link to original