• Machine Learning
  • general problem format
  • machine learning is about building a function
    • simplification using feature vector
  • loss
    • zero-one loss
    • quadratic loss
  • empirical risk
  • three types of machine learning problems
    • classification problem
      • all possible training set
      • signature of machine learning function $\lambda$
      • classifier $h$ define a partition of $X$
    • regression problem
    • clustering problem
  • supervised/ unsupervised machine learning
• polynomial data fitting
  • interpolation in polynomial data fitting
• k-nearest neighbors predictor
  • Voronoi diagram
• gradient descent
  • stochastic gradient descent (SGD)
  • step size
  • subgradient
• logistic-regression classifier
  • score function for linear boundary
  • signed distance to hyperplane
  • logistic function
    • softmax function
  • cross entropy loss for binary classification
    • cross entropy loss for $K$-class case
• support vector machine (SVM)
  • binary support vector machine
    • separating hyperplane for binary support vector machine
    • hinge loss
      • empirical risk of binary support vector machine
  • soft linear support vector machine
    • subgradient of hinge function
  • support vector machine with kernel
    • representer theorem
    • support vector
    • kernel for support vector machine

Machine Learning

general problem format

given input $A$, want output $y\in Y$

$$f:A\to Y,y=f(a)\in Y\text{for }a\in A$$

• traditional approach
  hand-craft the function $f$
• machine learning
  build another function $\lambda$ and use it to generate an approximation $f$

machine learning is about building a function

• training data $L=\{(a_1,y_1),\cdots ,(a_n,y_n)\}$
• class of allowed function $\mathcal{F}$

use a predefined algorithm to compute $f\in \mathcal{F}$ with the goal:

$$y\approx f(x)$$

simplification using feature vector

convert input into a 1d vector, making machine learning generally applicable

• feature vector $\vec{x}\in X\subseteq {\mathbb{R}}^d$
• $\varphi :A\to X$
• training set $T_a=\{({\vec{x}}_1,y_1),\cdots ,({\vec{x}}_n,y_n)\}\subset {\mathbb{R}}^d\times {\mathbb{R}}^e$
• hypothesis space $\mathcal{H}$
• $Y\subseteq {\mathbb{R}}^e$

predefined algorithm produce $h\in \mathcal{H}$ so that

$$f(a)=h(\varphi (a))$$

loss

estimation of the error of $h$

$$\begin{gathered} \ell :Y\times Y\to {\mathbb{R}}^{+} \\ \ell (y_n,h({\vec{x}}_n)) \end{gathered}$$

zero-one loss

$$\ell (y,\hat{y}):=\{\begin{array}{ll}0& y=\hat{y}\\ 1& \text{otherwise}\end{array}$$

quadratic loss

$$\ell (y,\hat{y}):=(y-\hat{y}{)}^2$$

empirical risk

average lost based on the training set

$$L_T(h):=\frac{1}{N}\sum _{n=1}^N\ell (y_n,h({\vec{x}}_n))$$

three types of machine learning problems

classification problem

label given data

• classifier (predictor) $h$: the produced function

all possible training set

$$\mathcal{T}:=2^{X\times Y}$$

signature of machine learning function $\lambda$

$$\lambda :\mathcal{T}\to \mathcal{H}\text{such that}\lambda (T)=h$$

• $\lambda$ learn (or train) classifier $h$ from training set $T$
• inference: apply classifier $h$ on any data
  • testing: apply classifier $h$ on unseen data

classifier $h$ define a partition of $X$

regression problem

given data, return a vector

clustering problem

group given data

supervised/ unsupervised machine learning

supervised learning: classification, regression

unsupervised learning: clustering

polynomial data fitting

not machine learning but similar

$$\begin{gathered} A\vec{c}=\vec{b} \\ A=\left[\begin{array}{cccc}1& x_1& \cdots & x_1^k\\ ⋮& ⋮& & ⋮\\ 1& x_N& \cdots & x_N^k\end{array}\right] \\ \vec{b}=\left[\begin{array}{c}{y}_1\\ ⋮\\ y_N\end{array}\right] \\ \hat{\vec{c}}\in \underset{\vec{c}}{\mathrm{argmin}}\Vert A\vec{c}=\vec{b}{\Vert }^2 \end{gathered}$$

• number of monomial $m(d,k)=\left(\genfrac{}{}{0ex}{}{d+k}{k}\right)$

interpolation in polynomial data fitting

achieve $0$ loss

• $k=N-1\Rightarrow$ always interpolate
• overfitting

k-nearest neighbors predictor

remember the whole training set

$$T=\{({\vec{x}}_i,y_i)|i=1,\cdots ,N\}$$

return average of $y_n$s corresponding to the $k$ closest ${\vec{x}}_n$s to $\vec{x}$

• useful for both classification and regression
• smaller $k$ results in worse overfitting
• good interpolation and poor extrapolation

Voronoi diagram

gradient descent

stochastic gradient descent (SGD)

group training set randomly into mini-batch, use gradient from each mini-batch to descent

• mini-step are in the right direction on average
• epoch: using all data once

step size

• fixed

• decreasing

• momentum

  $${\vec{v}}_{k+1}={\mu }_k{\vec{v}}_k-{\alpha }_k\nabla f({\vec{z}}_k)$$

• line search

subgradient

logistic-regression classifier

• score-based

score function for linear boundary

$$s(\vec{x})=\sigma (a(\vec{x}))=\sigma (c+{\vec{u}}^T\vec{x})$$

signed distance to hyperplane

hyperplane $\chi \in {\mathbb{R}}^d$

$$b+{\vec{w}}^T\vec{x}=0\vec{w}\ne \vec{0}$$

• $\vec{w}$ is perpendicular to $\chi$

• distance of $\chi$ from origin

  $$\beta :=\frac{|b|}{\Vert \vec{w}\Vert }$$

• signed distance of $\vec{x}$ from $\chi$

  $$\Delta (\vec{x}):=\frac{b+{\vec{w}}^T\vec{x}}{\Vert \vec{w}\Vert }$$

logistic function

$$f(\Delta ):=\frac{1}{1+e^{-\Delta }}$$

then the score function is

$$s(\vec{x}):=f(a(\vec{x}))=f(b+{\vec{w}}^T\vec{x})=\frac{1}{1+e^{-b-{\vec{w}}^T\vec{x}}}$$

• activation $a(\vec{x})$ is signed distance scaled

softmax function

softmax function in activation $\vec{a}$

$$\begin{gathered} \vec{s}(\vec{x})=\left[\begin{array}{c}{s}_1(\vec{a})\\ ⋮\\ s_K(\vec{a})\end{array}\right] \\ \vec{a}(\vec{x})=\left[\begin{array}{c}{a}_1(\vec{x})\\ ⋮\\ a_K(\vec{x})\end{array}\right] \\ {s}_k(\vec{x})=f(a_k(\vec{x}))=\frac{e^{a_k}(\vec{x})}{{\sum }_{j=1}^K{e}^{a_j}(\vec{x})} \end{gathered}$$

cross entropy loss for binary classification

cross entropy loss of assigning score $p$ to point whose true label is $y$

$$\begin{gathered} \ell (y,p):=\{\begin{array}{ll}-\log p& y=1\\ -\log (1-p)& y=0\end{array} \\ =-y\log p-(1-y)\log (1-p) \end{gathered}$$

• differentiable so we can do gradient descent
• base of $\log$ does not matter
• resulting risk function is weakly convex

cross entropy loss for $K$-class case

$$\ell (y,\vec{p})=-\log p_y=-\sum _{k=1}^K{q}_k\log p_k$$

• true label $y$
• prediction $\vec{p}$
• one hot encoding $\vec{q}$ of $y$

support vector machine (SVM)

binary support vector machine

separating hyperplane for binary support vector machine

$$\begin{gathered} {\vec{n}}^T\vec{x}+c=0 \\ \vec{n}\in {\mathbb{R}}^d,\Vert \vec{n}\Vert =1,c\in \mathbb{R} \end{gathered}$$

• decision rule

  $$\begin{gathered} h(\vec{x})=\text{sign}({\vec{n}}^T\vec{x}+c) \\ \Rightarrow y({\vec{n}}^T\vec{x}+c)\ge 0 \end{gathered}$$

• margin for $(\vec{x},y)$ with parameter $\vec{v}=(\vec{n},c)$

  $${\mu }_{\vec{v}}(\vec{x},y):=y({\vec{n}}^T\vec{x}+c)$$

  • margin ${\mu }_{\vec{v}}(T)$ of training set

    $${\mu }_{\vec{v}}(T):=\underset{(\vec{x},y)\in T}{\min }{\mu }_{\vec{v}}(\vec{x},y)$$

  • linearly separable if ${\mu }_{\vec{v}}(T)>0$

hinge loss

reference margin ${\mu }^{\ast }>0$

$$\begin{gathered} {\ell }_{\vec{v}}(\vec{x},y):=\frac{1}{\mu \ast }\max \{0,{\mu }^{\ast }-{\mu }_{\vec{v}}(\vec{x},y)\} \\ =\max \{0,1-y({\vec{w}}^T\vec{x}+b)\} \end{gathered}$$

where

$$\vec{w}:=\frac{\vec{n}}{{\mu }^{\ast }},b=\frac{c}{{\mu }^{\ast }}$$

• separating hyperplane ${\vec{w}}^T\vec{x}+b=0$

empirical risk of binary support vector machine

$$L_T(\vec{w},b):=\frac{1}{2}\Vert \vec{w}{\Vert }^2+\frac{C_0}{N}\sum _{n=1}^N{\ell }_{(\vec{w},b)}({\vec{x}}_n,y_n)$$

• bigger $C_0\Rightarrow$ smaller ${\mu }^{\ast }$

soft linear support vector machine

$$({\vec{w}}^{\ast },b^{\ast })={\text{ERM}}_T(\vec{w},b)$$

subgradient of hinge function

$$\begin{gathered} \rho (z)=\max \{0,z\} \\ {\rho }^{\prime }(z)=\{\begin{array}{ll}1& z>0\\ 0& \text{otherwise}\end{array} \end{gathered}$$

support vector machine with kernel

representer theorem

$\forall$ loss function in the form

$$L^T(\vec{w},b)=R(\Vert \vec{w}\Vert )+S({\vec{w}}^T{\vec{x}}_1+b,\cdots ,{\vec{w}}^T{\vec{x}}_N+b)$$

where $R:{\mathbb{R}}_{+}\to \mathbb{R}$ increasing, $S:{\mathbb{R}}^N\to \mathbb{R}$,

$\exists {\beta }_1,\cdots {\beta }_N$ s.t.

$${\vec{w}}^{\ast }=\sum _{n=1}^N{\beta }_n{\vec{x}}_n$$

• proof: by writing

  $${\vec{w}}^{\ast }=\sum _{n=1}^N{\beta }_n{\vec{x}}_n+\vec{u}\text{for some}\vec{u}\in \text{span}\{{\vec{x}}_i\}$$

  and proving $\vec{u}=\vec{0}$ by contradiction

support vector

sample that are misclassified or classified correctly with a margin not larger than ${\mu }^{\ast }$

only support vector contribute to ${\vec{w}}^{\ast },b^{\ast }$

$$\begin{gathered} h(\vec{x})=\text{sign}\left(\sum _{n=1}^N{\beta }_n{\vec{x}}_n^T\vec{x}+b^{\ast }\right) \\ {L}^T(\vec{w},b)=\frac{1}{2}\sum _{n=1}^N{\beta }_m{\beta }_n{\vec{x}}_n^T{\vec{x}}_n+\frac{C_0}{N}\sum _{n=1}^N\rho \left(1-y_n\left(\sum _{n=1}^N{\beta }_m{\vec{x}}_n^T{\vec{x}}_n+b\right)\right) \end{gathered}$$

kernel for support vector machine

$$\begin{gathered} h(\vec{x})=\text{sign}\left(\sum _{n=1}^N{\beta }_{n}K({\vec{x}}_n,\vec{x})+b^{\ast }\right) \\ {L}^T(\vec{w},b)=\frac{1}{2}\sum _{n=1}^N{\beta }_m{\beta }_{n}K({\vec{x}}_n,{\vec{x}}_n)+\frac{C_0}{N}\sum _{n=1}^N\rho \left(1-y_n\left(\sum _{n=1}^N{\beta }_{m}K({\vec{x}}_n,{\vec{x}}_n)+b\right)\right) \end{gathered}$$

where kernel $K$

$$K(\vec{x},\vec{\xi }):=\vec{\phi }(\vec{x})\vec{\phi }(\vec{\xi })$$

for some $\vec{\phi }$

• $K(\vec{x},\vec{\xi })=K(\vec{\xi },\vec{x})$
• $K^2(\vec{x},\vec{\xi })\le K(\vec{x},\vec{x})K(\vec{\xi },\vec{\xi })$

$K$ is a kernel of $\{{\vec{x}}_i\}$

• $\iff C\ge 0$ where $C_{ij}=K({\vec{x}}_i,{\vec{x}}_j)$

• $\iff$ Mercer’s condition: $\forall f:{\mathbb{R}}^d\to \mathbb{R}$ s.t.

  $${\int }_{{\mathbb{R}}^d}f(\vec{x})d\vec{x}$$

  is finite,

  $${\int }_{{\mathbb{R}}^d\times {\mathbb{R}}^d}K(\vec{x},\vec{\xi })f(\vec{x})f(\vec{\xi })d\vec{x}d\vec{\xi }\ge 0$$

• Gaussian kernel

  $$K(\vec{x},\vec{\xi })=e^{-\frac{\Vert \vec{x}-\vec{\xi }{\Vert }^2}{{\sigma }^2}}$$

  • radial basis function (RBF) SVM