Machine Learning - Linear Classifier

linear classifier

A method using a linear combination of features
for the characterization or the separation of
two or more classes of objects or events.
The resulting combination may be used as a linear
classifier, or, more commonly, for dimensionality
reduction before later classification.

$\qquad\quad y= f(\mathbf{w}\cdot\mathbf{x}-b), \qquad\quad \mathbf{w}\cdot\mathbf{x}=\sum_{j=0}^{d-1} w_j x_j $

feature vector: $\ \ \mathbf{x}=(x_0,\,..,\,x_{d-1})$
weight vector: $\ \ \mathbf{w}=(w_0,\,..,\,w_{d-1})$
offset (threshold): $\ \ b$
(non-linear) transfer function: $\ \ f(z)$

hyperplane

$$ \mathbf{x}\qquad \mathrm{such\ that} \qquad \fbox{$\phantom{\big|}\mathbf{w}\cdot\mathbf{x}=b\phantom{\big|}$} $$

a $(d-1)$ dimensional hyperplane divides a $d$ dimensional space into two halves

$$ \begin{array}{rcl} \mathrm{right-side} &:& \mathbf{w}\cdot\mathbf{x}> b \\ \mathrm{left-side} &:& \mathbf{w}\cdot\mathbf{x}< b \end{array} $$

use transfer function $\ \ f(z)=y(z) \ \ $ to map to feature class

$$ y(z<0)\ \to\ -1,\quad\qquad y(z>0)\ \to\ 1,\quad\qquad z=\mathbf{w}\cdot\mathbf{x}-b $$

also called 'perceptron' $\ \ \to \ \ $ neural networks

task

determine "optimal"
weights $\ \ \mathbf{w}$
offset $\ \ b$

training / testing sets

supervised learning

labeled data: $\ \ N=N_1+N_2$

$ \qquad \begin{array}{rcl} \mathrm{first\ feature} &:& \{\mathbf{x}_\alpha\}, \qquad \alpha\in[1,N_1] \\ \mathrm{second\ feature} &:& \{\mathbf{x}_\beta\}, \qquad \beta\in[N_1+1,N] \end{array} $

divide randomly into training / test data
: typically 70/30, 80/20, ...
non-optimized model parameters (hyper parameters)
may be fine tuned using a validation data set, if needed

center of mass of individual classes

$$ \mathbf{m}_1 = \frac{1}{N_1}\sum_\alpha \mathbf{x}_\alpha, \quad\qquad \mathbf{m}_2 = \frac{1}{N_2}\sum_\beta \mathbf{x}_\beta $$

implicit: sum is over training set
intuition: $\ \ \mathbf{w}\ \propto \ \mathbf{m}_1-\mathbf{m}_2$
: only true for uniformly distributed data

covariance matrix

probability distribution

$\qquad\quad p(\mathbf{x})\ge0, \qquad\qquad \int p(\mathbf{x})\,d\mathbf{x}=1 $

generating the data

$ p(\mathbf{x}) \quad\longrightarrow \quad \mathbf{x}_\alpha, $
with mean (generic)

$ \mathbf{m} = \frac{1}{N}\sum_\alpha \mathbf{x}_\alpha = \int \mathbf{x}\,p(\mathbf{x})\,d\mathbf{x} = \langle \mathbf{x}\rangle $
Cartesian components $$ \mathbf{x}=\left(\begin{array}{c} x_0\\ \vdots \\ x_{d-1}\end{array}\right),\qquad\quad \mathbf{m}=\left(\begin{array}{c} m_0\\ \vdots \\ m_{d-1}\end{array}\right),\qquad\quad \mathbf{x}^T=(x_0,\,\dots,x_{d-1}) $$ note: distinguish here between and vector $\ \ \mathbf{x}\ \ $ and transposed vector $\ \ \mathbf{x}^T\ \ $

covariance matrix

$$ S_{ij} = \big\langle (x_i-m_i)(x_j-m_j)\big\rangle $$

symmetric
: eigenvalues are real
: they correspond to half-width of covariance ellipse
matrix notation

$$ \hat S = \big\langle (\mathbf{x}-\mathbf{m})\,(\mathbf{x}-\mathbf{m})^T\big\rangle, \qquad\quad S_{ij} = (\hat{S})_{ij}, \qquad\quad \mathbf{x}=\left(\begin{array}{c} x_0\\ \vdots \\ x_{d-1} \end{array}\right) $$

outer product $$ \mathbf{x}\,\mathbf{x}^T= \mathbf{x}\otimes\mathbf{x}, \qquad\quad \big(\mathbf{x}\,\mathbf{x}^T\big)_{ij}=x_ix_j $$ note $$ \mathbf{x}^T\mathbf{x} = \mathbf{x}\cdot\mathbf{x} = \sum_i x_i x_i $$

covariance ellipse

parametric ellipse

$$ \frac{x^2}{a^2}+\frac{y^2}{b^2} = 1, \quad\qquad \left\{\begin{array}{rcl} x(t) &=& \sqrt{\lambda_1}\cos\Theta\cos t -\sqrt{\lambda_2}\sin\Theta\sin t \\[0.1ex] y(t) &=& \sqrt{\lambda_1}\sin\Theta\cos t +\sqrt{\lambda_2}\cos\Theta\sin t \end{array}\right. $$

angle with x-axis: $\ \Theta$
eigenvalues $\ \lambda_i$

$$ \mathbf{x} = \hat{V} \cdot \hat{\Lambda} \cdot \mathbf{T}, \quad\qquad \mathbf{x} = {x\choose y}, \quad\qquad \mathbf{T} = {\cos t\choose \sin t}, $$

eigen-vector matrix $\ \hat{V}$

$$ \hat{V}=\left(\begin{array}{cc} \cos\Theta & -\sin\Theta \\ \sin\Theta & \cos\Theta \end{array}\right) \quad\qquad \hat{\Lambda}=\left(\begin{array}{cc} \sqrt{\lambda_1} & 0 \\ 0 & \sqrt{\lambda_2}, \end{array}\right) $$

plotting a covariance ellipse

if (__name__ == "__main__"):
not executed when imported as a module
allows to include testing
$A=\sum_i\lambda_i |\lambda_i\rangle\langle\lambda_i|$
matrix decomposition in terms of eigensystem
projection operators $|\lambda\rangle\langle\lambda|$ are outer products
np.random.multivariate_normal(mean, coVar, N)
draws N samples from a
multi-variate Gaussian with covariance matrix coVar
two covariance matrices:
for data generation and measured

#!/usr/bin/env python3
import math                      # math
import numpy as np               # numerics
import matplotlib.pyplot as plt  # plotting
from numpy import linalg as LA   # linear algebra

# flip to True to print intermediate values
DEBUG = False                    

# ***
# *** covariance matrix from data
# ***

def covarianceMatrix(data):
  '''Normalized (divide-by-N, population) 
     covariance matrix of input data.
     Alternatives to manual loop:
     np.mean(data, axis=0) and 
     np.cov(data.T, bias=True).'''
  nRow = len(data)                     # number of data points
  nCol = len(data[0])                  # dimension
  mean = np.zeros(nCol)                # empty array
  for thisRow in data:                 # loop over data points
    mean += thisRow*1.0/nRow           # vector-mean
#
  coVar = np.zeros((nCol,nCol))        # empty matrix
  for thisRow in data:
    dataPoint = thisRow - mean         # shifted data point
    coVar += np.outer(dataPoint,dataPoint)/nRow  # outer product
#
  if DEBUG:
    print("\ninput data\n", data)
    print("nRow, nCol\n", nRow, nCol)
    print("mean\n", mean)
  print("\n covariance matrix: measured \n",coVar)
#
  return mean, coVar                   # returning both

# ***
# *** generate data for plotting an ellipse
# ***

def plotEllipseData(data):
  """generates ellipse from symmetric 2x2 slice 
   of the input matrix"""
#
# slice (copy: don't mutate caller's matrix)
  slice22 = data[:2, :2].copy() 
# eigh: for symmetric matrices
  eigenValues, eigenVectors = LA.eigh(slice22)  
#
  if (eigenValues[0]<0.0) or (eigenValues[1]<0.0):
    print("# plotEllipseData: only positive eigenvalues (variance)")
    return
#
  if DEBUG:
    print("\n# slice22     ", slice22)
    print("\n# eigenValues ", eigenValues)
    print("\n# eigenVectors\n",eigenVectors)
#
  a = math.sqrt(eigenValues[0])
  b = math.sqrt(eigenValues[1])
# first eigenvector = eigenVectors[:, 0]
  cTheta = eigenVectors[0, 0]  
  sTheta = eigenVectors[1, 0]
  x = []
  y = []
  for i in range(nPoints:=101):          # walrus assignment
    tt = i*2.0*math.pi/(nPoints-1)       # full loop
    cc = math.cos(tt)
    ss = math.sin(tt)
    xx = a*cTheta*cc - b*sTheta*ss
    yy = a*sTheta*cc + b*cTheta*ss
    x.append(xx)
    y.append(yy)
#   print(xx,yy)
  return x, y

# ***
# *** generate 2D test data
# ***

def testData(angle, var1, var2, nData, startMean=(0.0,0.0)):
  r"2D Gaussian for a given angle and main variances.\
   A = \sum_i \lambda_i |lambda_i><lambda_i|"
#
  eigen1 = [math.cos(angle),-math.sin(angle)]
  eigen2 = [math.sin(angle), math.cos(angle)]
  startCoVar  = var1*np.outer(eigen1,eigen1)
  startCoVar += var2*np.outer(eigen2,eigen2)
  print("\n covariance matrix: data generation \n",startCoVar)
  return np.random.multivariate_normal(startMean, startCoVar, nData)

# ***
# *** main (with a block)
# ***

if (__name__ == "__main__"):    # blocking out-of-use access
#
  np.random.seed(0)             # reproducible test data

  dataMatrix = testData(0.3*math.pi, 1.0, 9.0, 100)
  mean, coVar = covarianceMatrix(dataMatrix)

  if DEBUG:
    print("\n#main: data\n", dataMatrix)
    print("#main: mean\n", mean)
    print("\n#main: coVar matrix \n",coVar)

  xEllipse, yEllipse = plotEllipseData(coVar)  # coVar-ellipse

  xData = [thisRow[0] for thisRow in dataMatrix]
  yData = [thisRow[1] for thisRow in dataMatrix]

  Z_90 = math.sqrt(4.605)       # 90% confidence (chi2, 2 dof)
  Z_95 = math.sqrt(5.991)       # 95% confidence
  Z_99 = math.sqrt(9.210)       # 99% confidence
#
  xE_90 = [Z_90*xx + mean[0] for xx in xEllipse]
  yE_90 = [Z_90*yy + mean[1] for yy in yEllipse]
  xE_95 = [Z_95*xx + mean[0] for xx in xEllipse]
  yE_95 = [Z_95*yy + mean[1] for yy in yEllipse]
  xE_99 = [Z_99*xx + mean[0] for xx in xEllipse]
  yE_99 = [Z_99*yy + mean[1] for yy in yEllipse]
#
  plt.plot(xE_90, yE_90, label="90%")
  plt.plot(xE_95, yE_95, label="95%")
  plt.plot(xE_99, yE_99, label="99%")
  plt.plot(xData, yData, "ob", markersize=5)
#
  plt.legend(loc="upper left")
  plt.axis('square')                           # square plot
  plt.title("Confidence ellipses from sample covariance")
  plt.xlabel("x")
  plt.ylabel("y")
  plt.savefig('foo.svg')                       # export figure
  plt.show()

#!/usr/bin/env python3
import math                      # math
import numpy as np               # numerics
import matplotlib.pyplot as plt  # plotting
from numpy import linalg as LA   # linear algebra

# flip to True to print intermediate values
DEBUG = False

# ***
# *** covariance matrix from data
# ***

def covarianceMatrix(data):
  '''Normalized (divide-by-N, population) 
     covariance matrix of input data.
     Alternatives to manual loop:
     np.mean(data, axis=0) and 
     np.cov(data.T, bias=True).'''
  nRow = len(data)                     # number of data points
  nCol = len(data[0])                  # dimension
  mean = np.zeros(nCol)                # empty array
  for thisRow in data:                 # loop over data points
    mean += thisRow*1.0/nRow           # vector-mean
#
  coVar = np.zeros((nCol,nCol))        # empty matrix
  for thisRow in data:
    dataPoint = thisRow - mean         # shifted data point
    coVar += np.outer(dataPoint,dataPoint)/nRow  # outer product
#
  if DEBUG:
    print("\ninput data\n", data)
    print("nRow, nCol\n", nRow, nCol)
    print("mean\n", mean)
  print("\n covariance matrix: measured \n",coVar)
#
  return mean, coVar                   # returning both

# ***
# *** generate data for plotting an ellipse
# ***

def plotEllipseData(data):
  """generates ellipse from symmetric 2x2 slice 
   of the input matrix"""
#
# slice (copy: don't mutate caller's matrix)
  slice22 = data[:2, :2].copy() 
# eigh: for symmetric matrices
  eigenValues, eigenVectors = LA.eigh(slice22)  
#
  if (eigenValues[0]<0.0) or (eigenValues[1]<0.0):
    print("# plotEllipseData: only positive eigenvalues (variance)")
    return
#
  if DEBUG:
    print("\n# slice22     ", slice22)
    print("\n# eigenValues ", eigenValues)
    print("\n# eigenVectors\n",eigenVectors)
#
  a = math.sqrt(eigenValues[0])
  b = math.sqrt(eigenValues[1])
# first eigenvector = eigenVectors[:, 0]
  cTheta = eigenVectors[0, 0]  
  sTheta = eigenVectors[1, 0]
  x = []
  y = []
  for i in range(nPoints:=101):          # walrus assignment
    tt = i*2.0*math.pi/(nPoints-1)       # full loop
    cc = math.cos(tt)
    ss = math.sin(tt)
    xx = a*cTheta*cc - b*sTheta*ss
    yy = a*sTheta*cc + b*cTheta*ss
    x.append(xx)
    y.append(yy)
#   print(xx,yy)
  return x, y

# ***
# *** generate 2D test data
# ***

def testData(angle, var1, var2, nData, startMean=(0.0,0.0)):
  r"2D Gaussian for a given angle and main variances.\
   A = \sum_i \lambda_i |lambda_i><lambda_i|"
#
  eigen1 = [math.cos(angle),-math.sin(angle)]
  eigen2 = [math.sin(angle), math.cos(angle)]
  startCoVar  = var1*np.outer(eigen1,eigen1)
  startCoVar += var2*np.outer(eigen2,eigen2)
  print("\n covariance matrix: data generation \n",startCoVar)
  return np.random.multivariate_normal(startMean, startCoVar, nData)

# ***
# *** main (with a block)
# ***

if (__name__ == "__main__"):    # blocking out-of-use access
#
  np.random.seed(0)             # reproducible test data

dataMatrix = testData(0.3*math.pi, 1.0, 9.0, 100)
  mean, coVar = covarianceMatrix(dataMatrix)

if DEBUG:
    print("\n#main: data\n", dataMatrix)
    print("#main: mean\n", mean)
    print("\n#main: coVar matrix \n",coVar)

xEllipse, yEllipse = plotEllipseData(coVar)  # coVar-ellipse

xData = [thisRow[0] for thisRow in dataMatrix]
  yData = [thisRow[1] for thisRow in dataMatrix]

Z_90 = math.sqrt(4.605)       # 90% confidence (chi2, 2 dof)
  Z_95 = math.sqrt(5.991)       # 95% confidence
  Z_99 = math.sqrt(9.210)       # 99% confidence
#
  xE_90 = [Z_90*xx + mean[0] for xx in xEllipse]
  yE_90 = [Z_90*yy + mean[1] for yy in yEllipse]
  xE_95 = [Z_95*xx + mean[0] for xx in xEllipse]
  yE_95 = [Z_95*yy + mean[1] for yy in yEllipse]
  xE_99 = [Z_99*xx + mean[0] for xx in xEllipse]
  yE_99 = [Z_99*yy + mean[1] for yy in yEllipse]
#
  plt.plot(xE_90, yE_90, label="90%")
  plt.plot(xE_95, yE_95, label="95%")
  plt.plot(xE_99, yE_99, label="99%")
  plt.plot(xData, yData, "ob", markersize=5)
#
  plt.legend(loc="upper left")
  plt.axis('square')                           # square plot
  plt.title("Confidence ellipses from sample covariance")
  plt.xlabel("x")
  plt.ylabel("y")
  plt.savefig('foo.svg')                       # export figure
  plt.show()

python intermezzo

loading a privat module
:: plotting the covariance ellipse
__pycache__
:: directory created when importing private files
:: stores pre-compiled bytecode
imports are not transferred

#!/usr/bin/env python3

import math                        # math
import matplotlib.pyplot as plt    # plotting
import ML_covarianceMatrix as CM   # loading user-defined module


dataMatrix  = CM.testData(0.3*math.pi, 1.0, 9.0, 100)
mean, coVar = CM.covarianceMatrix(dataMatrix)

xEllipse, yEllipse = CM.plotEllipseData(coVar)  # coVar-ellipse

xData = [thisRow[0] for thisRow in dataMatrix]
yData = [thisRow[1] for thisRow in dataMatrix]

Z_90 = math.sqrt(4.601)                      # 90% confidence
Z_95 = math.sqrt(5.991)                      # 95% confidence
Z_99 = math.sqrt(9.210)                      # 99% confidence

xE_90 = [Z_90*xx + mean[0] for xx in xEllipse]
yE_90 = [Z_90*yy + mean[1] for yy in yEllipse]
xE_99 = [Z_99*xx + mean[0] for xx in xEllipse]
yE_99 = [Z_99*yy + mean[1] for yy in yEllipse]

plt.plot(xE_90, yE_90, label="90%")
plt.plot(xE_99, yE_99, label="99%")
plt.plot(xData, yData, "ob", markersize=5)

plt.legend(loc="upper left")
plt.axis('square')                           # square plot
plt.savefig('foo.svg')                       # export figure
plt.show()

#!/usr/bin/env python3

import math                        # math
import matplotlib.pyplot as plt    # plotting
import ML_covarianceMatrix as CM   # loading user-defined module

dataMatrix  = CM.testData(0.3*math.pi, 1.0, 9.0, 100)
mean, coVar = CM.covarianceMatrix(dataMatrix)

xEllipse, yEllipse = CM.plotEllipseData(coVar)  # coVar-ellipse

xData = [thisRow[0] for thisRow in dataMatrix]
yData = [thisRow[1] for thisRow in dataMatrix]

Z_90 = math.sqrt(4.601)                      # 90% confidence
Z_95 = math.sqrt(5.991)                      # 95% confidence
Z_99 = math.sqrt(9.210)                      # 99% confidence

xE_90 = [Z_90*xx + mean[0] for xx in xEllipse]
yE_90 = [Z_90*yy + mean[1] for yy in yEllipse]
xE_99 = [Z_99*xx + mean[0] for xx in xEllipse]
yE_99 = [Z_99*yy + mean[1] for yy in yEllipse]

plt.plot(xE_90, yE_90, label="90%")
plt.plot(xE_99, yE_99, label="99%")
plt.plot(xData, yData, "ob", markersize=5)

plt.legend(loc="upper left")
plt.axis('square')                           # square plot
plt.savefig('foo.svg')                       # export figure
plt.show()

multivariate Gaussians

uni/multi-variate : one/multi-dimenional
one-dimensional Gaussian $$ N(x) = \frac{1}{\sqrt{2\pi\sigma^2}}e^{-(x-\mu)^2/(2\sigma^2)} $$
multivariate $$ N(\mathbf{x}) = \frac{1}{\sqrt{(2\pi)^d|\hat{S}|}} \exp\left(\frac{-1}{2}({\mathbf x}-{\mathbf m})^T{\hat{S}}^{-1} ({\mathbf x}-{\mathbf m})\right) $$

diagonal case

$$ \hat{S}=\left(\begin{array}{ccc} \sigma_0^2 & \dots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \dots & \sigma_{d-1}^2 \end{array}\right), \qquad\quad \sigma_k^2 = \big\langle (x_k-m_k)^2\big\rangle $$

if $\ \ \big\langle (x_i-m_i)(x_j-m_j)\big\rangle=0\quad \mbox{for}\quad i\ne j$
$i\ne j\ \ $ uncorrelated

$$ |\hat{S}| = \prod_k \sigma_k^2, \qquad\quad \hat{S}^{-1}=\left(\begin{array}{ccc} 1/\sigma_0^2 & \dots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \dots & 1/\sigma_{d-1}^2 \end{array}\right) $$

multivariate Gaussian factorizes

$$ N(\mathbf{x}) = \prod_k \frac{\exp(-(x_k-m_k)^2/(2\sigma_k^2))}{\sqrt{2\pi\sigma_k^2}} $$