Machine Learning

John Samuel
CPE Lyon

Year: 2018-2019
Email: john(dot)samuel(at)cpe(dot)fr

Goals

Goals

1. Machine Learning
2. Deep Learning
3. Artificial Intelligence

Classification

Formal definition

• Let X be the input feature space
• Let Y be the output feature space (of labels)
• The goal of classification algorithm (or classifier) is to find {(x₁, y₁),...,(x_l, y_k)}, i.e., assigning a known label to every input feature vector, where
  • x_i ∈ X
  • y_i ∈ Y
  • |X | = l
  • |Y | = k
  • l >= k

Classification

Classifiers

• Classifying Algorithm
• Two types of classifiers:
  • Binary classifiers assigning an object to any of two classes
  • Multiclass classifiers assigning an object to one of several classes

Binary classification

Classification

Linear Classifiers

• A linear function assigning a score to each possible category by combining the feature vector of an instance with a vector of weights, using a dot product.
• Formalization:
  • Let X be the input feature space and x_i ∈ X
  • Let β_k be vector of weights for category k
  • score(x_i, k) = x_i.β_k, score for assigning category k to instance x_i. The category that gives the highest score is assigned as the category of the instance.

Classification

Classification

Classification

Let

• tp: number of true postives
• fp: number of false postives
• fn: number of false negatives

Then

• Precision p = tp / (tp + fp)
• Recall r = tp / (tp + fn)
• F1-score f1 = 2 * ((p * r) / (p + r))
• F1-score: best value at 1 (perfect precision and recall) and worst at 0.

Multiclass classification

Classification

Multiclass classification

• Transformation to binary
  • One-vs.-rest (One-vs.-all)
  • One-vs.-one
• Extension from binary
  • Neural networks
  • k-nearest neighbours

Multiclass classification

One-vs.-rest (One-vs.-all) strategy

One-vs.-one strategy

Artificial neural networks

Perceptron

• Algorithm for supervised learning of binary classifiers
• Binary classifier is a classifier which decides whether a given input belongs to a particular class or not
• Invented in 1958 by Frank Rosenblatt

Perceptron

Perceptron: Formal definition

• Let y = f(z) be output of perceptron for an input vector z
• Let N be the number of training examples
• Let X be the input feature space
• Let {(x₁, d₁),...,(x_N, d_N)} be the N training examples, where
  • x_i is the feature vector of i^th training example.
  • d_i is the desired output value.
  • x_j,i be the i^th feature of j^th training example.
  • x_j,0 = 1

Perceptron: Formal definition

• Weights are represented in the following manner:
  • w_i is the i^th value of weight vector.
  • w_i(t) is the i^th value of weight vector at a given time t.

Perceptron: Steps

1. Initialize weights and threshold
2. For each example (x_j, d_j) in training set
   • Calculate the weight: y_j(t)=f[w(t).x_j]
   • Update the weights: w_i(t + 1) = w_i(t) + r. (d_j-y_j(t))x_j,i
3. Repeat step 2 until the iteration error 1/s (Σ |d_j - y_j(t)|) is less than user-specified threshold.
4. s is the sample size and r is the learning rate.

Activation function

Identity

Activation function

Binary step

Activation function

TanH

Activation function

Rectified linear unit (ReLU)

Activation function

Gaussian

Feedforward neural network

• Connections between the nodes do not form a cycle
• Information moves from the input nodes, through the hidden nodes (if any) and to the output nodes.
• Information moves in only one direction, forward

Feedforward neural network

Single-layer perceptron

Feedforward neural network

Multilayer perceptron

Feedforward neural network

Backpropagation

• computes the gradient of the loss function with respect to the weights of the network for a single input-output example.
• works by computing the gradient of the loss function with respect to each weight by the chain rule

Deep Learning

• uses multiple layers to progressively extract higher level features from the raw input.

Recurrent neural network

Recurrent neural network

Long short-term memory (LSTM) network

Convolutional Neural Networks

Convolutional Neural Networks

• Analysis of images
• Makes use of mathematical linear operation, convolution
• One input and one output layer
• Multiple hidden layers, consisting of convolutional layers

Web

• https://en.wikipedia.org/wiki/Perceptron
• https://en.wikipedia.org/wiki/Multiclass_classification
• http://scikit-learn.org/stable/
• https://en.wikipedia.org/wiki/Multilayer_perceptron
• https://en.wikipedia.org/wiki/Feedforward_neural_network
• https://en.wikipedia.org/wiki/Recurrent_neural_network
• https://en.wikipedia.org/wiki/Long_short-term_memory
• https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.Perceptron.html
• https://en.wikipedia.org/wiki/Activation_function

Colors

• Color Tool - Material Design

Images

• Wikimedia Commons