---
title: "Let's build Image classifiers-II"
author: 'Philippe Fullsack+others'
output:
  html_document:
    toc: yes
  pdf_document: null
  pdf_presentation: null
  slidy_presentation:
    css: slidy.css
    widescreen: yes
  word_document: null
---

# Theme of activity

   + (a) Image classification problems in R

   + (b) Review and compare models

   + (c) MNIST digit prediction
   
   + (d) Alternative (shallow) learning models  

## Alternative classification models


### Decision trees

+(Pro): Works directly from table data
+(Pro): Easiest to understand
+(Pro): Relevant features are extracted automatically by Random Forests
+(Pro): Results are human-readable and easy to interpret
+(Con): CART trees are prone to overfitting and not robust to outliers
+(Con): Random forests loose the ease of interpretation of CART trees
+(Con): Models take a lot of memory for large number of classes and features

### Support vector machines (SVM)

SVM is a <b>discriminative</b> classifier.

It works by finding hyperplanes that separate two classes by the largest possible margin.

Data does not need to be perfectly linearly  separable, i.e. the method also minimizes the number of misclassified points on each side of the hyperplane.

SVM was originally applied to binary data in euclidean space (linear-SVM), but admits extensions to non-linear data (via the so-called kernel trick) and to multi-class classification.

<a href="https://towardsdatascience.com/support-vector-machines-for-classification-fc7c1565e3"><img width=500 src="https://miro.medium.com/max/544/1*6U9NrruycDBsPOyivpn8UQ.png">
</a>

+(Pro): Relatively straightforward to understand
+(Pro): Results are human-readable and easy to interpret
+(Con): No unique method for non-binary classification
+(Con): Not very flexible
+(Con): Requires the construction of an appropriate kernel
+(Con): Computationally intensive


### K-Nearest Neighbours

K-Nearest Neighbours classifiers work by inspecting local neighborhood of the point to predict and voting for the most frequent class expressed near the point.

The basic difference between K-NN classifier and Naive Bayes classifier is that, the former is a discriminative classifier but the latter is a generative classifier. ... Naive Bayes is an eager learning classifier and it is much faster than K-NN. Thus, it could be used for prediction in real time.

K-NN is a <b>discriminative</b> classifier.

<a href="">
<img width=500 src="https://res.cloudinary.com/dyd911kmh/image/upload/f_auto,q_auto:best/v1531424125/KNN_final_a1mrv9.png"></a>

Naive Bayes is a 'linear classifier' while K-NN is not;

K-NN is NOT a probabilistic method although you can pretend it is and
estimate probabilities of classes through a naive estimator in the neighbourhood of a point that needs prediction. The empirical probability of a class $y$ is calculated as:


$$P(y|x) = # labels y in NN(x) / # size of NN(x) $$

where NN(x) is the set of nearest neighbours of point $x$ for some choice of metrics.

In this sense, K-NN is equivalent to a non-parametric estimation method.

+(Pro): Works directly from table data
+(Pro): Medium hard to understand
+(Pro): Results are human-readable and easy to interpret
+(Con): Requires the choice of a metric
+(Con): Requires some embedding in euclidean or metric space.
+(Con): Requires tuning of optimal neighborhood size

### Naive Bayes
https://stackoverflow.com/questions/36969740/difference-between-probabilistic-knn-and-naive-bayes


Naive Bayes is a <b>generative</b> classifier.

+An example with a naive probability distribution:

<a href="https://towardsdatascience.com/introduction-to-na%C3%AFve-bayes-classifier-fa59e3e24aaf">
</a>
<a href="https://www.globalsoftwaresupport.com/naive-bayes-classifier-explained-step-step/">
<img src="naivebayes.png"></a>


+An example with explicit generative distribution (gaussian):

<a href="">
<img width=500 src="https://i.ytimg.com/vi/TcAQKPgymLE/maxresdefault.jpg"></a>

+Naive bayes assumes that each class is distributed according to a simple distribution, independent on feature basis. 

+In the case of continuous features (predicting variables), a commonly used model is the Radial-Basis-function (RBF), which implies that each class is normally distributed. The predicted class is the one that maximizes the gaussian density.


+(Pro): Flexible: can choose from many parametric distributions

+(Pro): Connection with maximum likelihood methods

+(Pro): Model takes less memory than other alternatives (e.g. Random Forests)

+(Con): Not always the most accurate method


### Ridge regression

<a href="https://web.stanford.edu/~hastie/glmnet/glmnet_alpha.html">See the Glmnet vignette at Stanford</a>


## Useful links

+<a href="https://www.datasciencecentral.com/profiles/blogs/comparing-classifiers-decision-trees-knn-naive-bayes">Comparing Classifiers: Decision Trees, K-NN & Naive Bayes</a>

+<a href="https://lazyprogrammer.me/bayes-classifier-and-naive-bayes-tutorial-using/">Mnist classification with Naive Bayes</a>

+<a href="https://en.wikipedia.org/wiki/Naive_Bayes_classifier">Wikipedia article on Naive Bayes methods</a>


## Suggested project: TEXT classification

+Download the following dataset:
http://www.marcovanetti.com/pages/wmsnsec/wmsnsec1.xml

(src:http://www.marcovanetti.com/)

+Apply all methods described here to engineer the best classification model.
+Discuss the potential limitations of this dataset
+How is classification affected by automatic translations?
+Find an analog nbut much larger dataset
+Write an essay on the dangers of Social media


<a href="https://www.ijarse.com/images/fullpdf/1470802548_135ijarse.pdf"></a>

# Application to MNIST data classification

## Run classification models in R

+Load the data:

```{r}
set.seed(1)
train <- read.csv("../Data/mnist_train.psv", sep="|", as.is=TRUE, header=FALSE)
test <- read.csv("../Data/mnist_test.psv", sep="|", as.is=TRUE, header=FALSE)
```

+Separate the predictors from the response:

```{r}
Xtrain <- as.matrix(train[,-1])
Xtest <- as.matrix(test[,-1])
ytrain <- train[,1]
ytest <- test[,1]
```

We are ready to build prediction models.

### Regression: Ridge regression 

For ridge regression, I'll directly use the multinomial loss
function and let the R function do cross validation for me.
The **glmnet** package is my preferred package for doing
ridge regressions, just remember to set *alpha* to 0.


+Principle (a) : general linear model. Use of a 'link function'.

$$  y = ax + b $$

is replaced by linear regression through a link:

$$ g(y) = ax + b $$

For binary classification (2 classes)

+Principle (b) : In ridge regression models, a term of regularization $\| \Gamma x \|^2$ is added to robustify the usual method of least-squares.

$$  \|Ax-b \|^2 + \| \Gamma x \|^2  $$

In R, you can use Glmnet for ridge regression.

Glmnet is a package that fits a generalized linear model via penalized maximum likelihood.
The regularization path is computed for the lasso or elasticnet penalty at a grid of values for the regularization parameter lambda. 
The algorithm is extremely fast, and can exploit sparsity in the input matrix x .

```{r}
library(glmnet)
outLm <- cv.glmnet(Xtrain, ytrain, alpha=0, nfolds=3, family="multinomial")
predLm <- apply(predict(outLm, Xtest, s=outLm$lambda.min,
                  type="response"), 1, which.max) - 1L
```

In MNIST the class labels are 0,1,2 etc.

As predicted classes are indexed starting at 1 by Glmnet, we need to subtract
one off of the Glmnet results to get the correct class labels.

### Boosting: Gradient boosted trees

Gradient boosted trees belongs to the family of boosting algorithms. They can be applied directly to data with more than 2 claases.

We will see a very short introduction on boosting on Wednesday.

One can tune several hyperparameters: interaction depth, number of trees or learning rate.

You will have to experiment with these. I am not going to discuss this in detail here.

```{r}
library(gbm)
outGbm <- gbm.fit(Xtrain,  factor(ytrain), distribution="multinomial",
                  n.trees=500, interaction.depth=2)
predGbm <- apply(predict(outGbm, Xtest, n.trees=outGbm$n.trees),1,which.max) - 1L
```

### Hyperplane separators:  Support vector machines

Support Vector Machines work by searching for hyperplanes that separate two classes by the maximum margin.

Hence these methods are based on maximizing the discrimination of  distinct classes.

For non-binary data, a method must be found to reduce the problem to one of binary data.

Usually we either compare each class to all others, or each class to each other class.

We need to experiment with a kernel choice in the case of non-linearly separable data. A commonly used kernel is the radial basis function kernel.

To fit SVMs, we can import the e1071 library.


```{r}
library(e1071)
outSvm <- svm(Xtrain,  factor(ytrain), kernel="radial", cost=1)
predSvm <- predict(outSvm, Xtest)
```

## Prediction Performance and Comparison

### Misclassification rates

We see that the methods differ substantially in how predictive they are
on the test dataset:

```{r}
mean(predLm != ytest)
mean(predGbm != ytest)
mean(predSvm != ytest)
```

k-NN > SVM > tree-methods

### Mis-classification rates by class

Where do ridge regression and support vector machines make errors?

```{r}
tapply(predLm != ytest, ytest, mean)
tapply(predSvm != ytest, ytest, mean)
```

+ What are the digits that are the most difficult to predict

+ Which digit is the easiest to predict?


### Confusion matrix

Although the digit is like half of the digit 8 in shape, the difficulty of predictions of both '3' and '8' cannot be explained
by a confusion between 3 and 8:

```{r}
table(predLm,ytest)
table(predSvm,ytest)
```

We also see that the points where these two models make mistakes do not
have too great of an overlap.

```{r}
table(predSvm != ytest, predLm != ytest)
```

This gives evidence that stacking could be beneficial.

### Mis-classified digits

We can pick out a large sample of images that are 3's
and see if these are particularly difficult to detect.

```{r, fig.width=7, fig.height=6}
iset <- sample(which(train[,1] == 3),5*7)
par(mar=c(0,0,0,0))
par(mfrow=c(5,7))
for (j in iset) {
  y <- matrix(as.matrix(train[j,-1]),16,16,byrow=TRUE)
  y <- 1 - (y + 1)*0.5

  plot(0,0,xlab="",ylab="",axes=FALSE)
  rasterImage(y,-1,-1,1,1)
  box()
  text(-0.8,-0.7, train[j,1], cex=3, col="red")
}
```

For the most part though, these do not seem difficult for
a human to classify.

What if we look at the actual mis-classified points. Here
are the ones from the support vector machine:

```{r, fig.width=7, fig.height=7}
iset <- sample(which(predSvm != ytest),7*7)
par(mar=c(0,0,0,0))
par(mfrow=c(7,7))
for (j in iset) {
  y <- matrix(as.matrix(test[j,-1]),16,16,byrow=TRUE)
  y <- 1 - (y + 1)*0.5

  plot(0,0,xlab="",ylab="",axes=FALSE)
  rasterImage(y,-1,-1,1,1)
  box()
  text(-0.8,-0.7, test[j,1], cex=3, col="red")
  text(0.8,-0.7, predSvm[j], cex=3, col="blue")
}
```

And the ridge regression:

```{r, fig.width=7, fig.height=7}
iset <- sample(which(predLm != ytest),7*7)
par(mar=c(0,0,0,0))
par(mfrow=c(7,7))
for (j in iset) {
  y <- matrix(as.matrix(test[j,-1]),16,16,byrow=TRUE)
  y <- 1 - (y + 1)*0.5

  plot(0,0,xlab="",ylab="",axes=FALSE)
  rasterImage(y,-1,-1,1,1)
  box()
  text(-0.8,-0.7, test[j,1], cex=3, col="red")
  text(0.8,-0.7, predLm[j], cex=3, col="blue")
}
```


# Summary

+ We have learned how use alternative to tree-based models to classify images in R

+ We have learned how to analyze the reasons for misclassification

+ Next steps for improvement are deep learning methods (not seen in this course)



