Pattern recognition

Introduction to Pattern Recognition: Example 1

10 Patients

6 Patients Cancer type A
4 Patients Cancer tupe B

4 Genes

a,b,c,d

What is the role of each gene in the cancer type?

Data

Note the missing values…

Data

Note that r(a) and r(c) are both negatively co-regulated…

Data and Goals

Could we guess the most involved genes in the Cancer process differentiation?
Given a readout with the expression values for a,b,c,d genes, can we predict whether a new patient has tumor A or B?

Pattern recognition

Classification: predict a categorical label from labelled examples.
Regression: predict a numerical response.
Clustering: group observations without using known class labels.

The representation, target, and evaluation method depend on the scientific question.

Pattern Recognition Scheme in classification (1/3)

Pattern Recognition Scheme in classification (2/3)

Pattern Recognition Scheme in classification (3/3)

The curse of Dimensionality (1/2)

Term coined by Bellman (1961)
Describes a problem related with the relationship of multivariate data and number of samples

Consider a 3-class pattern recognition

One feature or variable.

The curse of Dimensionality (2/2)

The Easiest classifier: three bins / three samples per bin, then, vote
Can we improve the classification performance adding a second feature?

Adapted from Gutierrez-Osuna

Curse of Dimensionality

We shall maintain the density of examples we used on the 1D case?

Curse of Dimensionality

Bins are now 9 -> we will need 27 samples to maintain density.
on 3d, 27bins, 81 samples…

Adapted from Gutierrez-Osuna

The Curse of Dimensionality

Houston! We…

How could we avoid the curse of dimensionality?

Using prior knowledge.
Smoothing the target function.
Reducing the dimensionality.

Feature Selection vs Feature Extraction

Feature Selection

From a set of input N variables, select those which contain the most informative to the problem

Feature Selection vs Feature Extraction

Feature Extraction

From a set of input N variables, could we define a set of functions or transformations that contains relevant information for our problem?

Feature Selection vs Feature Extraction

Feature Selection

Aim

Choose a subset of input variables by eliminating features through a given criteria (e.g. with little or no predictive information).
Feature selection can significantly improve the comprehensibility of the resulting classifier models and often build a model that generalizes better to unseen points.

Types

Supervised: Using a class/target label. Main goal is to find a feature subset that produces higher classification/regression accuracy (e.g. linear filtering with gene expression data).
Unsupervised: Without using class/target label (e.g. Variability filtering analysis in gene expression data).

Feature ranking

For samples (x_k,y_k), assign each feature i a score using its observed values and the target:

S_i=f(\{x_{k,i},y_k\}_{k=1}^{m}).

Rank features by a score appropriate to the question. Estimate supervised rankings inside each training fold to avoid leaking test information.

Pearson Correlation Criteria

Pearson Correlation Coefficient

R(i) = \frac{cov(Xi,Y)}{\sqrt{var(X_i)var(Y)}}

Estimate of R(i)

\mathfrak{R}(i) = \frac{ \sum_{k=1}^{m} (x_{k,i}- \bar x_i) (y_k - \bar y)}{\sqrt{ \sum_{k=1}^{m} (x_{k,i} -\bar x_i )^2 \sum_{k=1}^{m} (y_k - \bar y)^2 }}

.. eq. to a goodness of linear fit of individual variables.

Pearson

Information Theoretic Ranking Criteria

Mutual Information

I(i)= MI(x_i,y) =\int_{x_i} \int_y p(x_i,y) \log \frac{p(x_i,y) }{p(x_i)p(y)} \mathrm{d} x \mathrm{d} y

, where p(x_i) and p(y) are the probability densities of x_i and y, and p(x_i,y)) is the joint density.

\mathfrak{I}(i) = \sum_{x_i} \sum_y P(X=x_i, Y=y) \log \frac{P(X=x_i, Y=y)}{P(X=x_i) P(Y=y)}

Sequential Selection Algorithms (1/3)

Sequential Selection Algorithms (2/3)

Sequential Selection Algorithms (3/3)

Can redundant variables help each other?

(a): The presumably redundant variables, (b) set after a 45 degree rotation
from Guyon 2003

Intra-Class covariance

(a) The class conditional distributions have a high covariance aligned with two class centers. (b) The class conditional distributions have a high covariance in the direction perpendicular to the line of the two class centers.
from Guyon 2003

Is covariance useful?

from Guyon 2003

Feature extraction: subspace methods

Project observations into a lower-dimensional representation that retains information relevant to the task.

Examples include:

Principal component analysis (PCA)
Linear discriminant analysis (LDA)
Independent component analysis (ICA)

Each method uses a different criterion; dimension reduction does not automatically preserve predictive information.

Feature Extraction: subspace methods

Principal Component Analysis

Most popular and commonly used methods. Sometimes included in the “Factor Analysis” methods.

It’s the second most main tool for visualization
- (First is always to plot the signals!)
Main goal of PCA is to capture main directions of variance in input space.
Dimensionality reduction:
- Allows for projecting the dataset onto a low dimensional subspace.
- Form of compression, or data modeling.
- Filtering.

The mean as a least-squares representation

For observations x_1,\ldots,x_n, choose a single representative vector a:

J(a)=\sum_{k=1}^n\lVert x_k-a\rVert^2.

With \bar x=n^{-1}\sum_k x_k,

J(a)=\sum_k\lVert x_k-\bar x\rVert^2 +n\lVert a-\bar x\rVert^2.

The minimum occurs at a=\bar x.

Principal Component Analysis

Projection onto one direction

For a unit vector e, approximate each observation by

\hat x_k=\bar x+a_ke.

The least-squares coefficient is

a_k=e^\top(x_k-\bar x).

This minimises \sum_k\lVert x_k-\bar x-a_ke\rVert^2 for a fixed direction. PCA then chooses the direction with the smallest reconstruction error.

Covariance matrix

For a random vector X\in\mathbb R^p with mean \mu:

\Sigma=\operatorname E[(X-\mu)(X-\mu)^\top].

Its (i,j) entry is \operatorname{Cov}(X_i,X_j). Diagonal entries are variances.

The usual unbiased sample estimate is

\widehat\Sigma=\frac{1}{n-1}\sum_{k=1}^n (x_k-\bar x)(x_k-\bar x)^\top.

Scaling features changes the covariance matrix and can change the principal components.

The first principal component

Let S=\sum_k(x_k-\bar x)(x_k-\bar x)^\top be the scatter matrix.

For a unit vector e, reconstruction error is

J(e)=\sum_k\lVert x_k-\bar x\rVert^2-e^\top S e.

Minimising J means maximising e^\top S e subject to e^\top e=1. The solution is an eigenvector associated with the largest eigenvalue:

Se=\lambda e.

PCA

PCA (1/4)

PCA (2/4)

PCA (3/4)

PCA (4/4)

PCA

Linear Discriminant Analysis (1/3)

LDA looks for the projection

y = w^\top x

So that maximizes the Fisher Criterion

J(W)=\frac{w^\top S_B w}{w^\top S_W w}

Linear Discriminant Analysis (2/3)

where,

S_B: Between Scatter Matrix

S_B=(m_1-m_2)(m_1-m_2)^\top

Linear Discriminant Analysis (3/3)

S_w: Within Scatter Matrix

S_W=S_1+S_2,\text{where } S_i=\sum_{x \in C_i}(x-m_i)(x-m_i)^\top

Linear Discriminant Analysis

LDA minimizes the within scatter matrix while maximizes the between scatter matrix.

It can be extended to Multiple classes (Multiple Discriminant Analysis)

Linear Discriminant Analysis

LDA vs PCA (1/4)

LDA vs PCA (2/4)

LDA vs PCA (3/4)

LDA vs PCA (4/4)

Independent component analysis

ICA models observations as mixtures of latent sources:

X=AS.

The aim is to recover statistically independent source components.
Non-Gaussianity is central to common ICA identifiability assumptions.
In a square invertible model, the unmixing matrix is W=A^{-1}; more general models need other treatment.
PCA removes correlations. Uncorrelated components need not be independent.

LDA vs PCA vs ICA (1/4)

LDA vs PCA vs ICA (2/4)

LDA vs PCA vs ICA (3/4)

LDA vs PCA vs ICA (4/4)

Nonlinear class boundaries

There are non-linear problems:

Can be linearized?
Can we change the features measured?
Representation change?

If “no”, then there are non-linear alternatives.

$But\u2026$

k-nearest neighbours

Choose a distance measure and a value of k.
Find the k nearest training observations to the new observation.
For classification, combine their labels, commonly by majority vote.
For regression, combine their numerical responses, commonly by averaging.

Scale features appropriately. Select k using training-only validation; prediction cost can be substantial for large datasets.

k-NN (1/4)

k-NN (2/4)

k-NN (3/4)

k-NN (4/4)

Voronoi Tessellation

Classification algorithms in sklearn

Cluster Analysis

Clustering

Partitioning of a data set into subsets (clusters). Individuals in each subset share some common trait according to some defined distance measure The most typical trait is proximity

Data clustering is a common technique for statistical data analysis. There are a number of techniques available

Hierarchical (e.g. agglomerative clustering)
Partitional (e.g. k-means clustering)
Graph base (Spectral)

Clustering (1/5)

Clustering (2/5)

Clustering (3/5)

Clustering (4/5)

Clustering (5/5)

Clustering

Distances and norms

A metric satisfies non-negativity, identity, symmetry, and the triangle inequality:

d(x,y)=0\iff x=y,\qquad d(x,y)=d(y,x),

d(x,y)\le d(x,z)+d(z,y).

For p\ge1, a common norm-induced distance is

d_p(x,y)=\left(\sum_i|x_i-y_i|^p\right)^{1/p}.

p=2 gives Euclidean distance. Not every metric is induced by a norm.

k-means

The most common clustering algorithm, (J. B. MacQueen, 1967)

Ask user how many clusters are desired.
Randomly guess k cluster center locations.
Each pattern is assigned to the closest center.
A New center is assigned as the centroid of the assigned patterns.
Repeat from (3).

kmeans (1/10)

kmeans (2/10)

kmeans (3/10)

kmeans (4/10)

kmeans (5/10)

kmeans (6/10)

kmeans (7/10)

kmeans (8/10)

kmeans (9/10)

kmeans (10/10)

kmeans

Convergence (1/2)

Convergence (2/2)

Number of Clusters

Number of Clusters (1/2)

Number of Clusters (2/2)

Clustering algorithms in sklearn

Validity and Over-Fitting

In multivariable predictive models, over-fitting occurs when a large number of predictor variables is fit to a small N of subjects. A model may “fit” well or perfectly, even if no real relationship. Simon, JNCI 2003

Direct Consequence of Overfitting

Model performance results are not reproducible in a new set of data.

Fermi

over-fitting (1/3)

Fermi

“How many arbitrary parameters did you use for your calculations?”

Dyson

“I thought for a moment about our cut-off procedures and said, -Four.-"

Fermi

“I remember my friend Johnny von Neumann used to say, with four parameters I can fit an elephant, and with five I can make him wiggle his trunk.”

over-fitting (2/3)

+ over-fitting

over-fitting (3/3)

From Dyson, F. A meeting with Enrico Fermi; how one intuitive physicist rescued a team from fruitless research. Nature 2004.

Over-Fitting

Validation Schemes

Ransohoff. Nat Rev Cancer 2004

Validation without leakage

Fit preprocessing, feature selection, and tuning using only the training partition. For tuned models, use nested cross-validation or an untouched test set. Keep samples from the same person together when splitting.

Validation Schemes