Linear classifiers (Jan 24)

Today we delved deeped into linear classifiers and studied the LDA and SVM.
Before the actual content, we discussed the course groupwork. Each group should submit their predictions to Kaggle as described in the assignment text.
Next, we studied a demo of projecting 2D data to 1D with different degrees of separation. The below animation recaps the idea: a good projection makes the classes nicely distinct in the 1D projected space. This is also seen in the Fisher score: bigger score means better separation. Luckily we do not need to try all directions (like in the demo), but can use the LDA formula to find the best direction with one line of code.

The LDA projection vector can be found in two ways: 1) Solve a generalized eigenvalue problem, or, 2) use the simpler formula:

             w = (S₁ + S₂)^-1 (m₁ - m₂),

with S₁ and S₂ the covariance matrices of the two classes and m₁ and m₂ the respective class means.

In the beginning of the second hour, we applied LDA to pixel classification. On the example, the user left-clicks at face areas and right-clicks at non-face areas. This is used as training material for skin detector that gives results like the one below.

This demo (code pasted at the bottom of this page) served as a motivation to look at SVM. The support vector machine is know for kernel trick, which (implicitly) maps the data into a higher dimension before classification. This enables non-linear class boundaries, which will be needed when the background is more variable than in the above simple example.

The essence of SVM is max margin classification, i.e., it attempts to maximize the margin between classes (as shown below). In case the classes are overlapping, we assign a penalty for each sample that is on the wrong side of the margin. The balance between margin width and the number of samples falling on the wrong side is adjusted using the parameter C.

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 24 11:05:43 2017

@author: heikki.huttunen@tut.fi

An example of using the LDA for pixel color classification.
Left mouse button shows examples of foreground, and
right mouse button examples of background.
"""

import numpy as np
import matplotlib.pyplot as plt
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
from mpl_toolkits.mplot3d import Axes3D

def onclick(event):
    """
    Function that is run every time when used clicks the mouse.
    """
    
    ix, iy = event.xdata, event.ydata
    button = event.button
    
    if button == 2:
        # Stop when used clicks middle button (or kills window)
        fig.canvas.mpl_disconnect(cid)
        plt.close("all")
    else:
        # Otherwise add to the coords list.
        global coords
        coords.append([int(ix), int(iy), button])

if __name__ == "__main__":
        
    # Load test image and show it.
    
    img = plt.imread("hh.jpg")
    
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.imshow(img)
    ax.set_title("Left-click: face; right-click: non-face; middle: exit")
    coords = []
    
    # Link mouse click to our function above.
    
    cid = fig.canvas.mpl_connect('button_press_event', onclick)
    plt.show()
    
    X = []
    y = []
    
    for ix, iy, button in coords:
        
        # Collect nearby samples to the user clicked point
    
        w = img[iy-3 : iy+4, ix-3:ix+4, :]
        
        # Unnecessarily complicated line to collect color channels
        # into a matrix (results in 49x3 matrix)
        
        C = np.array([w[...,c].ravel() for c in [0,1,2]]).T
        X.append(C)
        
        # Store class information to y.
        
        if button == 1:
            y.append(np.ones(C.shape[0]))
        else:
            y.append(np.zeros(C.shape[0]))
            
    X = np.concatenate(X, axis = 0)
    y = np.concatenate(y, axis = 0)
    X_test = np.array([img[...,c].ravel() for c in [0,1,2]]).T
    
    # Switch between sklearn and our own implementation.
    # Don't know why these produce slightly different results.
    # Both seem to work though.
    
    use_sklearn = True
    
    if use_sklearn:
        clf = LinearDiscriminantAnalysis()
        clf.fit(X, y)
        y_hat = clf.predict(X_test)
 
    else: # Do it the hard way:
        C0 = np.cov(X[y==0, :], rowvar = False)
        C1 = np.cov(X[y==1, :], rowvar = False)
        m0 = np.mean(X[y==0, :], axis = 0)
        m1 = np.mean(X[y==1, :], axis = 0)
        
        w = np.dot(np.linalg.inv(C0 + C1), (m1 - m0))
        T = 0.5 * (np.dot(w, m1) + np.dot(w, m0))    
 
        y_hat = np.dot(X_test, w) - T

        # Now y_hat is the class score.
        # Let's just threshold that at 0.
        # And cast from bool to integer
        
        y_hat = (y_hat > 0).astype(np.uint8)
    
    # Manipulate the vector form prediction to the original image shape.
    
    class_img = np.reshape(y_hat, img.shape[:2])
    prob_img  = np.reshape(clf.predict_proba(X_test)[:, 1], img.shape[:2])
    
    fig, ax = plt.subplots(1, 3)
    ax[0].imshow(img)
    ax[1].imshow(prob_img)
    img[class_img == 0] = 0
    ax[2].imshow(img)

    plt.show()