Neural Networks Deep Learning for Information Extraction © Fabian M. Suchanek
Neural Network A Neural Network is a classification algorithm that has been developed in the 1960’s. It is inspired by the human brain. 2 Neurons, by  Ivan Atanassov 
Deep Learning Neural Networks have recently achieved impressive performance (and  almost mystical popularity) under the name “Deep Learning”, because 1. Standard classification datasets emerged         thus allowing a more objective comparisons of methods. 2. Hardware (in particular GPUs) became more powerful         lending their strength to machine learning algorithms 3. More data became available         allowing better training 4. New neural network algorithms and architectures were devised 3
Overview 4 Perceptrons    Training a perceptron    Extending a perceptron    Structured Perceptrons Neural networks    Word2vec    Training a neural network Convolutional neural networks Recurrent neural networks Encoder‐decoders
Def: Perceptron perceptron  is a function   that is computed as         perceptron( ) =  where •     is the input vector of   real values •     is a weight vector of   real values •     is the dot product, mapping two vectors to a single real number •     is the bias value •     is an activation function, e.g.,  ? ... 5 (In a later generalization, activation functions can also go from   to  .)
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 6 >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) 7 perceptron  is a function   that is computed as         perceptron( ) =  >details
Eliminating the bias x x 8 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' x' vector concatenation 9 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' 10 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' 11 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 12 Perceptrons    Training a perceptron    Extending a perceptron    Structured Perceptrons Neural networks    Word2vec    Training a neural network Convolutional neural networks Recurrent neural networks Encoder‐decoders
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 13
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 14
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 15
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. 16
Overview 17 Perceptrons    Training a perceptron    Extending a perceptron    Structured Perceptrons Neural networks    Word2vec    Training a neural network Convolutional neural networks Recurrent neural networks Encoder‐decoders
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 i ? 18 perceptron( )   “Which similarity is bigger: to   or to   ?”
Perceptrons & SVMs x x x x a b 19 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. 20 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 21
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 22
      perceptron Mapping to another space If we map the examples to another space,e.g.  then the perceptron function (in alternative form) becomes 23 small trick Since   only ever appears in the form  , we do not need  at all! What we need is only the “kernel”
Kernels 24 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