Deep Learning: Perceptrons © Fabian M. Suchanek
Overview 2 Perceptrons    Training a perceptron    Extending a perceptron    Activation Functions    Structured Perceptrons ->Deep-learning
A perceptron is a linear classifier perceptron  is a function   that is computed as         perceptron( ) =  It is thus a binary classifier (in a supervised scenario). x x x x x x x perceptron( )=1 perceptron( )=0 x 3 >details
A perceptron is a linear classifier x' x' x' x' x' x' x' perceptron( )=1 perceptron( )=0 x'            ° °    perceptron( )=0  (with a simple binary function) 4 perceptron  is a function   that is computed as         perceptron( ) =  >details
Eliminating the bias x x 5 The bias   can be eliminated by adding a new dimension to all input vectors (whose value is always 1) and adding the weight  .             perceptron(  is vector concatenation.
Eliminating the bias x' x' vector concatenation 6 The bias   can be eliminated by adding a new dimension to all input vectors (whose value is always 1) and adding the weight  .             perceptron(
Eliminating the bias x' 7 x' The bias   can be eliminated by adding a new dimension to all input vectors (whose value is always 1) and adding the weight  .             perceptron(
Eliminating the bias x' 8 x' The bias   can be eliminated by adding a new dimension to all input vectors (whose value is always 1) and adding the weight  .             perceptron(
Overview 9 Perceptrons    Training a perceptron    Extending a perceptron    Activation Functions    Structured Perceptrons ->Deep-learning
Def: Training a perceptron Eliminate the bias  . Choose a learning rate  . While there exists a misclassified example  , add   to   if   is positive, otherwise subtract   from  . x x x x x x 10
Training a perceptron Eliminate the bias  . Choose a learning rate  . While there exists a misclassified example  , add   to   if   is positive, otherwise subtract   from  . x x x x x x 11
Training a perceptron Eliminate the bias  . Choose a learning rate  . While there exists a misclassified example  , add   to   if   is positive, otherwise subtract   from  . x x x x x x 12
Training a perceptron Eliminate the bias  . Choose a learning rate  . While there exists a misclassified example  , add   to   if   is positive, otherwise subtract   from  . x x x x x x Intuition: The sum of two vectors is closer to each of them. Theorem: If the examples can be linearly separated at all, they will eventually be. 13 >SVMs&dim
Overview 14 >SVM Perceptrons    Training a perceptron    Extending a perceptron    Activation Functions    Structured Perceptrons ->Deep-learning
A different view on perceptrons The perceptron formula        perceptron( ) can be written as                      perceptron( ) where   is the   misclassified example, and   its class. x x x x a b x ? 15 perceptron( )   “Which similarity is bigger: to   or to   ?” a : neg. training example b : pos. training example
Perceptrons & SVMs x x x x a b 16 A support vector machine (SVM) works in this way, but chooses the examples that separate the training data best. x The perceptron formula        perceptron( ) can be written as                      perceptron( ) where   is the   misclassified example, and   its class.
Problems with Perceptrons x x x x ? The perceptron can learn only linearly separable models. In particular, it cannot learn XOR. 17 If the training data is not linearly separable, the perceptron will find an arbitrarily bad solution.
Mapping to another space x If we map the examples to another space, e.g.,  ... x x x 18
x x x x below the  plane below the  plane If we map the examples to another space, e.g.,  then many datasets become linearly separable — among them XOR. Mapping to another space 19 >kernels
      perceptron Mapping to another space If we map the examples to another space,e.g.  then the perceptron function (in alternative form) becomes 20 small trick Since   only ever appears in the form  , we do not need  at all! What we need is only the “kernel”
Kernels 21 A perceptron with a kernel simulates a mapping of the training data to a higher‐dimensional space, without incurring the inefficiency of actually mapping the data. Cover’s theorem  says: given a set of training data that is not linearly separable, one can with high probability transform it into a training set that is linearly separable by projecting it in a higher-dimensional space. kernel  for a function   is a function  such that  . Support vector machines (SVMs) also use kernels.
Overview 22 Perceptrons    Training a perceptron    Extending a perceptron    Activation Functions    Structured Perceptrons ->Deep-learning
Def: Activation functions 23 •  Step function    + simple to compute    - not differentiable •  Rectified Linear Unit (ReLU)    + easy to compute    - not differentiable •  Sigmoid function    + differentiable    - not centered •  Tanh    + differentiable    + centered ?
ReLU 24 It can be made differentiable by choosing   and setting the derivative at   to   :         ? The  Rectified Linear Unit  (ReLU) is the following activation function: ReLU has shown superior performance in some tasks, and is hence often the activation function of choice. >strucPerc
Overview 25 Perceptrons    Training a perceptron    Extending a perceptron    Activation Functions    Structured Perceptrons ->end ->Deep-learning
Reminder: CRFs 26 conditional random field   (CRF) with identical potentials is a probability distribution of the form     ... which has the same max as a HMM, if  . Let us consider feature functions  . Each has a weight . We define  . If the weights form a vector  , and the functions form a vector  :       To find  , we maximize: ->prob-conditional-random-fields ->named-entity-recognition-and-classification ->pos-tagging
The Structured Perceptron 27 The  Structured Perceptron  is an algorithm that, like a CRF, is given an input  and feature functions   with weights  , and it computes                          Input:  I, run, fast Output space:  Features:  Weights:  N,ADV,N   N,V,V PR,V,ADV  PR,V,ADV  is closest to  => it is the output
Features of the Structured Perceptron 28 In practice, each feature function is a sum over the positions in  :                         ...which means that the structured perceptron maximizes:                                                                        ... which is exactly what a CRF computes. Interesting: Since every factor depends only on its predecessor, this quantity can be maximized by the Viterbi Algorithm, running in  , where   is the length of  , and   is the number of different values that each component of   can take. [ Michael Collins: “Lecture 4, COMS E6998-3: The Structured Perceptron” ]
Features of the Structured Perceptron 29 The structured perceptron maximizes:                         If we choose   and  , we can simulate an HMM tagging: Input  I, run, fast . Output space of possible  :  N,ADV,N  N,V,V PR,V,ADV   N,ADV,N  N,V,V  PR,V,ADV  N,ADV,N  N,V,V  PR,V,ADV PR,V,ADV  is always closest to  => it is the output
Features of the Structured Perceptron 30 The structured perceptron maximizes:                         The features can be HMM features, but they can also be other features: •  a capitalized word is more likely to be a proper name •  a number can be tagged as a number right away •  etc.  N,ADV,N  N,V,V  PR,V,ADV
Training the Structured Perceptron 31 The structured perceptron differs from a CRF mainly in its learning algorithm to find     Given       •  a number    of iterations       •  training examples        •  a vector of feature functions     Iterate for  , for