• Statistical Machine Learning
  • Bayesian decision theory
  • linear regression
    • regularization in lasso
  • K-nearest neighbors (KNN)
  • support vector machine (SVM)
    • hard-margin binary SVM
    • soft-margin binary SVM
    • kernel SVM
      • positive-definite kernel
  • dimensionality reduction by principal component analysis (PCA)
  • Monte Carlo sampling method
    • transformation method
    • rejection sampling
    • importance sampling
    • sampling-importance-resampling
    • simulated annealing
  • Markov chain
    • detailed balance
  • Markov chain Monte Carlo (MCMC)
    • metropolis hasting algorithm (MH algorithm)
    • Gibbs sampling
  • entropy
    • surprise
    • decision tree based on entropy
  • statistical learning theory
    • consistence wrt $\mathcal{F}$ & $P$
      • generalization bound
    • shattering coefficient $\mathcal{N}(\mathcal{F},n)$
  • (Vapnik-Chervonenkis dimension) VC dimension
    • Rademacher complexity
    • structural risk minimization (SRM)

Statistical Machine Learning

SGD > GD for online learning

SGD problem: mini batch too big

gated recurrent unit (GRU): a RNN

principal component analysis (PCA): autoencoder, dimensionality reduction

Bayesian decision theory

loss ${\lambda }_{ik}$: take action ${\alpha }_i$ when sample belong to $C_k$

goal: minimize risk

$$R({\alpha }_i|X)=\sum _{k=1}^K{\lambda }_{ik}P(C_k|X)$$

for 0-1 loss, $R({\alpha }_i|X)=1-P(C_i|X)$

reject class: a $K+1$th class w/ fixed loss $\lambda \in (0,1)$

• $\Rightarrow R(a_{K+1}|X)\equiv \lambda$
• reject when ${\min }_{i=1\dots K}R({\alpha }_i|X)>\lambda$

or, maximize discriminant function $g_i(x),i=1\dots K$

maximum likelihood estimator (MLE)

parametric (distribution based on known parameters) vs non-parametric

linear regression

$$\begin{gathered} X\in {\mathbb{R}}^{N\times P} \\ Y\in {\mathbb{R}}^{N\times 1} \\ L(W)=\Vert W^{T}X-Y{\Vert }^2=W^T{X}^{T}XW-2W^T{X}^{T}Y+Y^{T}Y \\ \underset{W}{\mathrm{argmin}}L(W)\Rightarrow \frac{\partial L(W)}{\partial W}=0 \\ \Rightarrow 2X^{T}XW-2X^{T}Y=0 \\ \Rightarrow \hat{W}=(X^{T}X{)}^{-1}{X}^{T}Y \end{gathered}$$

regularization in lasso

$$\underset{W}{\mathrm{argmin}}\left[L(W)+\lambda P(W)\right]\Rightarrow \hat{W}=(X^{T}X+\lambda I{)}^{-1}{X}^{T}Y$$

assuming $P(W)=\Vert W{\Vert }_2$

$X^{T}X+\lambda I$ invertible, proof by positive definite

K-nearest neighbors (KNN)

need to try different $K$

support vector machine (SVM)

hard-margin binary SVM

$y=-1,1$

objective, maximize minimum margin:

$$\begin{gathered} \underset{W,b}{\mathrm{argmax}}\underset{i=1\dots N}{\min }\frac{1}{\Vert W\Vert }|W^T{X}_i+b|\text{ s.t. }{y}_i(W^T{X}_i+b)>0 \\ \Rightarrow \underset{W,b}{\mathrm{argmax}}\frac{1}{\Vert W\Vert }\cdot 1\text{ s.t. }{y}_i(W^T{X}_i+b)\ge 1 \\ \Rightarrow \underset{W,b}{\mathrm{argmin}}\frac{1}{2}\Vert W{\Vert }^2\text{ s.t. }{y}_i(W^T{X}_i+b)\ge 1 \end{gathered}$$

by

$$\begin{gathered} |W^T{X}_i+b|=y_i(W^T{X}_i+b) \\ \underset{i=1\dots N}{\min }|W^T{X}_i+b|:=1 \end{gathered}$$

apply Lagrange multiplier:

$$\begin{gathered} L(W,b,\lambda )=\frac{1}{2}\Vert W{\Vert }^2+\sum _{i=1}^N{\lambda }_i(1-y_i(W^T{X}_i+b)) \\ \Rightarrow \underset{W,b}{\min }\underset{{\lambda }_i\ge 0}{\max }L(W,b,\lambda ) \\ \Rightarrow \underset{{\lambda }_i\ge 0}{\max }\underset{W,b}{\min }L(W,b,\lambda ) \end{gathered}$$

$$\begin{gathered} \frac{\partial L}{\partial W}=\frac{\partial L}{\partial b}=0 \\ \Rightarrow \hat{W}=\sum _{i=1}^N{\lambda }_i{y}_i{X}_i,\sum _{i=1}^N{\lambda }_i{y}_i=0 \\ \Rightarrow \hat{L}=-\frac{1}{2}\Vert \hat{W}{\Vert }^2+\sum _{i=1}^N{\lambda }_i=-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\lambda }_i{\lambda }_j{y}_i{y}_j{X}_i^T{X}_j+\sum _{i=1}^N{\lambda }_i \end{gathered}$$

final objective:

$$\underset{{\lambda }_i\ge 0}{\mathrm{argmin}}(-\hat{L})=\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\lambda }_i{\lambda }_j{y}_i{y}_j{X}_i^T{X}_j-\sum _{i=1}^N{\lambda }_i$$

solution: sequential minimal optimization (SMO)

• fix all but 2 ${\lambda }_i$, and iterate
• 2 variable because ${\sum }_{i=1}^N{\lambda }_i{y}_i=0$

soft-margin binary SVM

hinge loss

kernel SVM

solve non-linear problem w/ linear classifier

kernel, but w/o $\phi$ restriction

objective:

$$\underset{{\lambda }_i\ge 0}{\mathrm{argmin}}(-\hat{L})=\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\lambda }_i{\lambda }_j{y}_i{y}_{j}K(X_i,X_j)-\sum _{i=1}^N{\lambda }_i$$

positive-definite kernel

positive-definite kernel output positive-definite matrix

• positive-definite matrix: pivots > 0 or eigenvalues ${\lambda }_i>0$ or subdeterminant > 0
• Hilbert space: symmetric, positive-definite, linear

alternative definition of kernel:

• symmetric
• positive-definite: Gram matrix $G$ semi-positive definite $$G:=\left[\begin{array}{ccc}K(X_1,X_1)& \cdots & K(X_1,X_N)\\ ⋮& \ddots & ⋮\\ K(X_N,X_1)& \cdots & K(X_N,X_N)\end{array}\right]$$

dimensionality reduction by principal component analysis (PCA)

lossy transformation from $p$ to $q$ dimension

• mean: $\frac{1}{N}{X}^T\vec{1}$
• covariance: $\frac{1}{N}{X}^{T}HX$
  • centering matrix: $H:=I-\frac{1}{N}\vec{1}{\vec{1}}^T$
    • $H^T=H,H^2=H$
  • proof: $$S=\frac{1}{N}\sum _{i=1}^N\Vert X_i-\bar{X}{\Vert }^2=\frac{1}{N}\Vert \left[\begin{array}{ccc}{X}_1-\bar{X}& \cdots & X_N-\bar{X}\end{array}\right]{\Vert }^2$$

maximize variance

$$\begin{gathered} \underset{\vec{u}}{\mathrm{argmax}}{\vec{u}}^{T}S\vec{u}\text{ s.t. }{\vec{u}}^T\vec{u}=1 \\ \Rightarrow \underset{\lambda }{\mathrm{argmax}}L(\vec{u},\lambda )={\vec{u}}^{T}S\vec{u}+\lambda (1-{\vec{u}}^T\vec{u}) \\ \Rightarrow S\vec{u}=\lambda \vec{u} \end{gathered}$$

minimize distance between full projection ($p$-dimensional) and principal component analysis (PCA, $q$-dimensional):

• centering: ${\tilde{X}}_i=X_i-\bar{X}$
• lossless transformation with ${\vec{u}}_k$: $X_i^{\prime }={\sum }_{k=1}^p({\tilde{X}}_i^T{\vec{u}}_k){\vec{u}}_k$
• PCA transformation: ${\hat{X}}_i={\sum }_{k=1}^q({\tilde{X}}_i^T{\vec{u}}_k){\vec{u}}_k$

objective:

$$\underset{{\vec{u}}_k}{\mathrm{argmin}}\frac{1}{N}\sum _{i=1}^N\Vert {\hat{X}}_i-X_i^{\prime }{\Vert }^2=\frac{1}{N}\sum _{i=1}^N\Vert \sum _{k=q+1}^p(\stackrel{iTuk)uk2=N1i=1\sum Nk=q+1\sum p(XiTuk)2\Rightarrow ukargmink=q+1\sum pukTSuk s.t. ukTuk=1\Rightarrow Suk=\lambda uk}{X}$$

Monte Carlo sampling method

• sampling
  • purpose: determine parameter when doing sum/integral
  • good: from area of high probability & independent
• Monte Carlo drawback
  • does not work in high dimension
  • assume sample independence

transformation method

1. assume $z\sim p(z_0)$
2. get sample $x$
3. assume CDF $h(z_0=x)$
4. solve $z_1=h^{-1}(x)$
5. get another sample and repeat

rejection sampling

1. define distribution $q(z)$ s.t. $\exists k,\forall z,kq(z)\ge p(z)$
2. get sample $z_i\sim q(z)$
3. rate $\alpha :=\frac{p(z_i)}{kq(z_i)}\in (0,1]$
4. select random variable $x\sim U(0,1)\in (0,1]$
5. if $\alpha \ge x$, accept sample $z_i$; else reject

• reject most sample when $k$ large
• $k$ hard to determine
• waste iteration

importance sampling

for value $f$ following distribution with PDF $p$, do not know CDF, want expectation

define distribution $q(z)$ with known CDF

weight (importance) ${\omega }_i:=\frac{p(z_i)}{q(z_i)}$

$$E(f):=\int f(z)p(z)dz=\int f(z)\frac{p(z)}{q(z)}q(z)dz\approx \int {\omega }_{i}f(z)q(z)dz\approx \frac{1}{L}\sum _{i=1}^L{\omega }_{i}f(z_i)$$

sampling-importance-resampling

1. get $L$ sample $z_i$ from $q(z)$ with known CDF
2. ${\omega }_i:=\frac{p(z_i)}{q(z_i)}$
3. normalize ${\tilde{\omega }}_i:=\frac{{\omega }_i}{{\sum }_i{w}_i}$
4. treat ${\tilde{\omega }}_i$ as probability for $z_i$ and resample

simulated annealing

• to avoid trapped in local minimum
• still need to try multiple time

when seeking minimum, accept increase in $f$ with probability

$$e^{-\frac{\Delta f}{T}}<1$$

where temperature $T\in (0,1),T\leftarrow T\gamma ,\gamma =0.99\in (0,1)$

Markov chain

• transition matrix $Q$
  • stochastic matrix, because each row sum to 1
    • $\{Q^n\}$ converge, stationary $\Leftarrow$
      • all eigenvalue $|\lambda |\le 1$
      • $Q=A\Lambda A^{-1}\Rightarrow Q^n=A{\Lambda }^n{A}^{-1}$ where ${\Lambda }^n$ is diagonal with entries ${\lambda }_i^n$
• ${\vec{\pi }}_t$ probability be at state $x=1\dots N$ at time $t$
  • stationary distribution: ${\pi }_{m+1}={\pi }_m$ when $m$ large
  • ${\pi }_{t+1}={\pi }_{t}Q$
• sampling method: given PDF $p(z)$, set $Q$ s.t. $\pi (z)=p(z)$

detailed balance

Markov chain in stationary distribution if

$$\pi (x)p_{xy}=\pi (y)p_{yx}$$

Markov chain Monte Carlo (MCMC)

• work in high dimension
• honor probability dependency between sample

metropolis hasting algorithm (MH algorithm)

want to sample target distribution $p$

design Markov chain w/ stationary distribution $\pi =p$:

1. get Markov chain w/ $Q$ s.t. not necessarily $\pi =p$
2. acceptance rate $\alpha (x,x^{\ast }):=\min \left(1,\frac{p(x^{\ast })Q_{x^{\ast },x}}{p(x)Q_{x,x^{\ast }}}\right)$
   • $\Rightarrow p(x)Q_{x,x^{\ast }}\alpha (x,x^{\ast })=p(x^{\ast })Q_{x^{\ast },x}\alpha (x^{\ast },x)$
3. use new Markov chain w/ $Q_{x,x^{\ast }}^{\prime }:=\alpha (x,x^{\ast })Q_{x,x^{\ast }},x^{\ast }\ne x$
   • $Q_{x,x}$ take the rest of probability s.t. ${\sum }_y{Q}_{x,y}=1$

• drawback: do not know when stationary/converge. sample may be dependent

Gibbs sampling

want to sample variable $x_i$ following different distribution

fix $x_{-i}:=\{x_1\dots x_{i-1},x_{i+1}\dots \}$ to previous value when sampling $x_i$: $$Q_{x,x^{\ast }}:=p(x_i^{\ast }|x_{-1})$$

a special case for metropolis hasting method $\Leftarrow$

$$\begin{gathered} p(x_{-i}^{\ast })=p(x_{-i}) \\ \Rightarrow \alpha (x,x^{\ast })=\frac{p(x^{\ast })p(x_i|x_{-i}^{\ast })}{p(x)p(x_i^{\ast }|x_{-i})}=\frac{p(x_i^{\ast }|x_{-i}^{\ast })p(x_{-i}^{\ast })p(x_i|x_{-i}^{\ast })}{p(x_i|x_{-i})p(x_{-i})p(x_i^{\ast }|x_{-i})}=\frac{p(x_i^{\ast }|x_{-i})p(x_{-i})p(x_i|x_{-i})}{p(x_i|x_{-i})p(x_{-i})p(x_i^{\ast }|x_{-i})}=1 \end{gathered}$$

entropy

• randomness, impurity, how easy to determine
• equal to expected surprise $$H=\mathbb{E}(\sup )=\sum _{x}p(x)\sup (x)=-\sum _{x}p(x)\ln p(x)$$
• cross entropy loss

surprise

$$\sup =\ln \frac{1}{p(x)}=-\ln p(x)$$

decision tree based on entropy

• information gain $$\begin{gathered} I(Y|x_i)=H(Y)-H(Y|x_i) \\ \text{where}H(Y|x_i)=\sum _{x}p(x_i=x)H(Y|x_i=x) \end{gathered}$$
• maximize information gain on each split

statistical learning theory

• Bayes classifier $f^{\ast }$: minimize expected risk
• empirical risk minimization (ERM): minimize loss on training data
• estimation error (training error): because $X$ finite, grow w/ $|\mathcal{F}|$
• approximation error (model complexity): because $\mathcal{F}$ finite

consistence wrt $\mathcal{F}$ & $P$

empirical risk $R_n(f)$ close to true risk $R(f)$ $$P\left(|R(f)-R_n(f)|\ge \epsilon \right)\to 0\text{ as }n\to \infty$$

• universally consistent wrt $\mathcal{F}$: $\forall P$
• Bayes-consistent wrt $P$ $$P\left(|R(f^{\ast })-R_n(f)|\ge \epsilon \right)\to 0\text{ as }n\to \infty$$
• $\iff$ uniform convergence $$P(\underset{f\in \mathcal{F}}{\sup }|R_n(f)-R(f)|>\epsilon )\to 0$$
  • sufficiency $$P\left(|R(f)-R_n(f)|\ge \epsilon \right)\le P\left(\underset{f\in \mathcal{F}}{\sup }|R_n(f)-R(f)|\ge \frac{\epsilon }{2}\right)$$
• $$P\left(|R(f)-R_n(f)|\ge \epsilon \right)\le 2\exp (-2n{\epsilon }^2)$$

generalization bound

for finite class $\mathcal{F}=\{f_i\},i=1,\dots ,m$ $$P\left(|R(f)-R_n(f)|\ge \epsilon \right)\le 2m\exp (-2n{\epsilon }^2)$$

• proposition: choose $\delta \in (0,1)\Rightarrow$ w/ at least $1-\delta$ probability $$|R(f)-R_n(f)|\le \sqrt{\frac{\ln (2m)-\ln \delta }{2n}}$$
  • by $\delta :=2m\exp (-2n{\epsilon }^2)$

for infinite class $\mathcal{F}$ $$P\left(\underset{f\in \mathcal{F}}{\sup }|R(f)-R_n(f)|>\epsilon \right)\le 2\mathcal{N}(\mathcal{F},2n)\exp \left(\frac{-n{\epsilon }^2}{4}\right)$$

• proof: $$\begin{gathered} P\left(|R(f)-R_n(f)|\ge \epsilon \right)\le P\left(\underset{f\in \mathcal{F}}{\sup }|R(f)-R_n(f)|\ge \frac{\epsilon }{2}\right) \\ \le 2P\left(\underset{f\in \mathcal{F}}{\sup }|R_n(f)-R_n^{\prime }(f)|\ge \frac{\epsilon }{2}\right)\text{by Symmetrization Lemma} \end{gathered}$$ where $R_n^{\prime }(f)$ is empirical risk of another $n$ sample (ghost sample)

  $\Rightarrow \exists c\le \mathcal{N}(\mathcal{F},2n)$ class of $f$ for sample & ghost sample

• problem: hard to compute shattering coefficient

shattering coefficient $\mathcal{N}(\mathcal{F},n)$

maximum number of ${\mathcal{F}}_{X_1,\dots ,X_n}$, function we can get by restricting $\mathcal{F}$ to $X_1,\dots ,X_n$

(Vapnik-Chervonenkis dimension) VC dimension

maximum $n$ s.t. $\exists f\in \mathcal{F},\forall X=\{X_1\dots ,X_n\}$, $f$ classify $X$ completely correctly

• for function class $\mathcal{F}$ w/ VC dimension $d$ $$\mathcal{N}(\mathcal{F},n)\le \sum _{i=0}^d\left(\genfrac{}{}{0ex}{}{n}{d}\right)$$
  • for $n>d$, $\mathcal{N}(\mathcal{F},n)\le {\left(\frac{en}{d}\right)}^d$
• ERM is consistence $\iff$ VC dimension finite

Rademacher complexity

richness of function class $\mathcal{F}$ in sample set $\{X_i\}$

sample label ${\sigma }_i=\pm 1,i=1,\dots ,n$

$$Ra{d}_n(\mathcal{F})=\mathbb{E}\left[\underset{f\in \mathcal{F}}{\sup }\frac{1}{n}\sum _{i=1}^n{\sigma }_{i}f(X_i)\right]$$

solution: for each possible set of ${\sigma }_i$, find the function $f$ to maximize the inner sum, then take weighted average

• generalization bound: with ≥ $1-\delta$ probability, $\forall f\in \mathcal{F}$, $$\begin{gathered} R(f)\le R_n(f)+2Ra{d}_n(\mathcal{F})+\sqrt{\frac{-\ln (\delta )}{2n}} \\ \le R_n(f)+2\sqrt{\frac{d\ln \left(\frac{en}{d}\right)-\ln \delta }{n}} \end{gathered}$$

structural risk minimization (SRM)

to balance training error and model complexity

• e.g. regularization, linear SVM VC $=d+1$, RBF kernel $\Rightarrow \infty$