I'll give you some study material about neural networks: ### Limitsofa perceptron
Computational neuron
 A mathematical neuron is a computational unit
 358
 x1
 x2
 x...
 x4
 w1
 w2
 . . .
 wn
 +c ⇝σ⇝
 ▶ ⃗x =(x1,x2,...,xn) ∈ Rn a vector of inputs
 z
 ▶ ⃗w =(w1,w2,...,wn) ∈ Rn a vector of weights to treat the inputs
 ▶ creal (∈ R) constant, the “bias”
 ▶ σnon-linear R → R “activation” function
 ▶ zreal (∈ R) output
More compactly
 A computational neuron is thus a function
 f : Rn −→R
 defined as
 f (⃗x) := σ(⃗w ·⃗x + α)
 which arises from the application of a non-linear function to a linear combination of values
 ! The non-linear function is not necessarily a sigmoid
 359
Non-linear functions
 A non-linear function is one that cannot be represented as a first-degree polynomial
 360
 ! If it has a curve, it is not linear
 Some examples:
 ▶ powers and exponentials: x−1, ex, ...
 ▶ trigonometric functions: sin(x), tan(x), ...
 ▶ curves of higher degrees: parables x2, cubics 2x3 − 1
 2x2 + 5x + 4, ...
Nonlinearisms
 Sigmoid
 1
 y
 0.8
 0.6
 0.4
 0.2
 −4
 −2
 σ(x) = 1
 361
 x
 2
 4
 1 +e−x
Nonlinearisms
 Hyperbolic tangent
 1
 y
 0.5
 −4
 −2
 −0.5
 −1
 σ(x) = tanh(x) = sinh(x)
 cosh(x) = e2x −1
 362
 2
 x
 4
 e2x +1
Nonlinearisms
 Rectifier, or positive part
 5
 y
 4
 3
 2
 1
 −4
 −2
 363
 x
 2
 4
 σ(x) = max(0,x)
The basic neuron
 The first computational neuron has been the perceptron
 364
 Its activation function is the unit step:
 1
 y
 0.8
 0.6
 0.4
 0.2
 −3 −2 −1
 1
 σ(x) = 0 ifx≤0
 1 ifx >0
 x
 2
 3
A relation between sigmoid and unit step
 Weird observations
 For curiousity, we can note a mildly interesting relation between the sigmoid and the unit
 step function, that is: the sigmoid can be seen as a sort of limit of the sigmoid!
 365
 1
 y
 0.8
 0.6
 0.4
 0.2
 −4
 −2
 In blue σk for k = 2 and k = 2000
 If we consider a scaled sigmoid, for k ∈ R+
 σk(x) =
 1
 1 +e−kx
 we observe that for k −→ +∞ it converges to
 
 
 
 σ∞(x) =
 x
 
 
 1 ifx >0
 1
 2 ifx =0
 0 ifx <0
 If we diminish the discontinuity in 0 by putting
 σ(0) = 0, we obtain the unit step!
 2
 4
 ⇒the perceptron is an extreme, “black-or-white”
 version of a neuron using a sigmoid
Perceptron
 The perceptron thus emits a binary value:
 f (⃗x) = 0 if ⃗w ·⃗x +c ≤ 0
 This is equivalent to performing a linear separation
 366
 1 if ⃗w ·⃗x +c > 0
 (cf. Logistic regression at sl.12)
Inseparables
 ! Not all distributions of points in space are linearly separable!
 Let’s consider the truth tables for the logical AND, OR and XOR:
 0 1
 0 0 0
 1 0 1
 Таблица: *
 AND
 0 1
 0 0 1
 1 1 1
 Таблица: *
 OR
 0 1
 0 0 1
 1 1 0
 Таблица: *
 XOR
 They all represent functions over the set {0,1} × {0,1} with values in {0,1}
 367
 The set {0,1} with the logical operations is called a Boolean algebra
Either one
 368
 OR function
 We can find a line which separates the truth
 values, e.g. for
 ⃗
 w =(1,1) c=−2
 ▶ above the line points get 1 = True
 ▶ below the line points get 0 = False
One or the other, but not both
 Exclusive OR
 369
 XOR function
 We cannot find any line which separates the
 truth values!
 ⇒we will always have “spurious” points on
 one side or the other!
 ! It is not possible to reproduce a XOR function
 with any single linear classifier
370
 Strengthin
 numbers
One helps the other
 If a single computational unit is not able to replicate some functions,
 let’s use two!
 371
 Let’s consider the following layout of neurons:
 x1
 x2
 s1
 t
 s2
 z1
Layerings
 We set the “components” as:
 weights ⃗ s1 = ⃗ s2 = (1,1) and⃗t = (1,−2)
 biases cs1 
= 0, cs2 
= −1 and ct = 0
 activation through the linear rectifier f(x) = max(0,x) in the first layer, none in the
 second one
 372
 x1
 x2
 s1
 t
 s2
 z1
Blocks of weights
 Since we have more weight vectors in series, we can represent them as matrices:
 Ws = ⃗ s1
 ⃗
 s2
 = 1 1
 1 1 γs= cs1
 cs2
 = 0
 −1
 And so we write the simultaneous operations in the first layer (s1 & s2) as
 s(⃗x) = σ(Ws ·⃗xT + γs) = max(⃗ 0,Ws ·⃗xT + γs)
 373
 where⃗ 0 = (0,0) is the vector whose components are all 0s, the activation function is applied
 componentwise and so we have that
 s : R2 −→R2
Computing through the layers
 Example of computation for⃗x = (0,1)T:
 s((0, 1)) = max(⃗ 0, 1 1
 =max(⃗ 0, 1
 1 + 0
 −1 )
 =max(⃗ 0, 1
 0 )
 = max(0,1)
 max(0,0)
 = 1
 0
 The function s is a mapping of R2 into itself:
 every point is shifted into another (notneccessarily different) point
 374
 1 1 · 0
 1 + 0
 −1 )
A new space
 Going back to the four Boolean points (seesl.367), we compare...
 B =(0,1) C =(1,1)
 A =(0,0)
 D =(1,0)
 s(A) = (0,0)
 s(B) = s(D) = (1,0)
 The output of the first layer is separable configuration of points!
 375
 s(C) = (2,1)
 ⇒afirst application of computational units has created a
 new representation that can be separated by another
 ! The network in sl.372 ultimately outputs z = 0 for A and C and z = 1 for B and D
It functions
 In our example, we have replicated the function
 XOR : B ×B −→B
 where B = {0,1} is the Boolean algebra14 by means of a network of computational units
 representing a function
 ρ : R2 −→R
 which is ultimately expressed as15
 ρ(⃗x) = σ(σ(Ws ·⃗xT + γs) ·⃗tT + ct)
 =max(⃗ 0,Ws ·⃗xT + γs) ·⃗tT + ct
 14Which we can embed in R2 as the four points on sl.368 and onwards.
 15Note that it is not necessarily interpretable as a probability as for logistic regression.
 376
It functions
 In the end we observe that
 even if they are defined very differently!
 In computational linguistics we are interested in functions such as:
 ▶ tagging: we associate a linguistic unit to a particular label
 → parts of speech, polarities, lemmas, ...
 ▶ language models: predict which linguistic unit will follow another
 → generation of text, ...
 ⇒wecanmodel them as probability distributions over given vocabularies
 377
 XOR ≡ ρ
 Are we able to replicate them by means of neural networks?
Approximately
 Universal approximation theorem
 378
 Neural networks can approximate any continuous function.
 Approximate: a neural network will not necessarily exactly replicate a function, but we are
 granted to come as close as possible to it
 → theerror can be made arbitrarily small
 Non-continuity: even if linguistic phenomena are discrete, we can generalise to continuity
 ⇒Thekey: the computational neurons need non-linear activation functions
 Then, starting from just one layer a neural network can approximate any function!
Wanted: nonlinearity
 Activation
 If we suppose that an activation function
 σ : R−→R
 is linear, this means that we can just write it as
 σ(x) = αx +β
 for some α,β ∈ R and for all x ∈ R.
 So if e.g.in the example of sl.373 we consider the matrix As = αs1 
0
 βs = (βs1
 ,βs1
 )T we can substitute as
 s(⃗x) = σ(Ws ·⃗xT + γs)
 =As ·(Ws ·⃗xT +γs)+βs
 =(As ·Ws)·⃗xT +(As · γs +βs)
 379
 0 αs2
 and
 which is a linear combination using weights16 As · Ws ∈ M(2,R) and biases As · γs + βs ∈ R2.
 16The following notation stays for “all quadratic (2 × 2) matrices with elements in R”.
Wanted: nonlinearity
 More layers
 If we consider a neural network with more than one layer, we are considering the two
 successively applied functions
 s1(⃗x) = W1 ·⃗x + γ1 Rn −→ Rm
 s2(⃗y) = W2 ·⃗y + γ2 Rm −→ Rk
 with n, m and k not necessarily coinciding.
 If we substitute and make the expression explicit we will obtain
 s2(s1(⃗x)) = W2 · s1(⃗x) + γ2
 =W2·(W1 ·⃗x +γ1)+γ2
 =(W2 ·W1)·⃗x +(W2 ·γ1 +γ2)
 . . . and so in the end we are just considering another linear combination with total weights
 W2 ·W1 ∈ M(k,n,R) and biases W2 ·γ1 +γ2 ∈ Rk!
 380
 Any number of linear layers collapses into just one layer
381
 Feedforward networks
Neuron after neuron
 382
In the net
 A neural network is a k-partite directed graph where nodes are computational neurons
 383
 x1
 x2
 It expresses a (non-linear) function
 z1
 z2
 z3
 ρ : Rn −→Rm
 ⇒Anacyclic neural network is also called a feedforward neural network
Layers
 Different kinds of layers are distinguished:
 ▶ thefirst (0) layer is the input layer
 → itcorresponds to the input vector
 ▶ thelast layer is the output layer
 384
 → itcorresponds to the output vector, usually a probability distribution through normalisation
 ▶ all intervening layers are hidden layers
 → theyare made of computational units
 ⋆ each represents a transformation of the input space (cf.375)
 ! Usually, the layers are fully connected, i.e.every computational unit
 is connected to every unit of the successive level
 Each layer sk is a function Rnk −→ Rnk+1 represented as
 sk(⃗x) = σk(Wk ·⃗xk + γk)
 with Wk ∈ M(nk,nk+1,R) and γk ∈ Rnk+1, and σ any non-linear activation function.
Multiregression
 We are learning a multinomial regression for each layer
 385
 ! In the hidden layers the “feature” vector is a result of many transformations
 ⇒Theinitial representation becomes in a sense less important
 with respect to the subsequent processing
Toy networks
 Let’s try some neural networking at
 http://playground.tensorflow.org/
 386
Neural training
 The network has to learn weights Wk and biases γk for each layer
 387
 The objective functions are the same as for a usual logistic regression, using cross-entropy:
 ∆(ˆ π, ˜ π) = −(1 − ˆ p)log2(1 − ˜ p) − ˆ plog2(˜ p)
 and in the multinomial (with |S| > 2) case we can similarly compute
 |S|
 ∆(ˆ π, ˜ π) = −
 i=1
 ˆ
 ⃗
 pi log ˜ ⃗pi
 where⃗p represents the probability distribution over all the states (see Logisticregression sl.18).
 Given the known classification, they collapse on one single member, e.g.
 ∆(ˆ π, ˜ π) = −log˜ ⃗p⋆
 if ⋆ is the index of the “true’’ state.
Very partial derivatives
 We again apply the gradient descent
 388
 ! In the case of deep networks, bazillions of weights and biases are nested into each other
 ⇒partial derivatives have to be computed recursively
 ⇒the objective function is also in general not convex
 This is where most of the computational complexity of neural networks lies
###