I'll give you some study material that I dont' understand. Please explain it to me step by step, in very simple terms, as if I was 14 years old. Explain formulas in clear terms. ###LOGISTIC REGRESSION Method differences
 Again
 We distinguish two large classes of classifier models:
 ▶ Generative models
 ▶ Theyinfer rules to replicate the process which has generated the observations
 → emission probabilities
 ▶ Theymake strong hypotheses about the distributions of observations and states
 → Markovchains, memory loss, independence...
 ▶ Discriminative models
 ▶ Theyuse apriori defined features to discriminate observations based on relations between
 them and states
 → conditional probabilities (with respect to observations)
 ▶ Theydoasfewaspossible hypotheses about distribution
 → research of smallest loss (e.g.maximum entropy)
 All these methods presuppose a previous linguistic annotation
 323
 →supervised methods
Mathematically
 The main step for hidden Markov models (see“Markov”deck,sl.48) is
 arg max
 S∈Sm 
p(B|S)p(S)
 where p(B|S) generates an observation given a sequence of states.
 Conversely, discriminative methods directly tackle
 p(S|B)
 by using some knowledge about B.
 324
325
 Towards maximum entropy
Discrimination
 The basic case is binary, with two states
 that is, either the observation is in a class, or it is not.
 ⇒aBernoullian distribution
 The discriminative method is thus concerned with the complementary probabilities
 p(1|β) = 1−p(0|β)
 326
 S ={1,0}
Recipe
 A discriminative method is based on:
 ▶ features to express an observation in a vector space
 ▶ awaytoweigh features
 ▶ aclassification function to express the weighing as a probability
 ▶ anobjective (inthesenseof ‘goal’) function to measure how well discrimination works
 ▶ amethod to optimise the parameters of the objective function
 327
 The classification learns its parameters and is then tested (on different data sets)
Feature functions
 The observations β1,...,βm are associated to more or less arbitrarily chosen features.
 328
 Features are real-valued functions:
 where V is our vocabulary of types.
 f : V −→R
 A qualitative feature (e.g.‘being a deadjectival noun’) can always be assigned a binary
 indicator function
 f (βi) = 1 ifthe feature is satisfied
 0 else
Feature vectors
 We consider a set of features
 F ={f1,f2,...,fk}
 through which every observation β can be represented as a vector
 ⃗
 β =(f1(β),f2(β),...,fk(β)) ∈ Rk
 Not every feature has the same importance for every observation and state!
 329
 Each feature is associated a weight wi, so that we have a
 ⃗
 w =(w1,w2,...,wk) ∈ Rk
 vector of weights.
 ▶ apositive weight means that the feature counts towards p(1|β)
 ▶ anull weight means that the feature is not relevant
 ▶ anegative weight means that the feature counts towards p(0|β)
Classifying
 We want to gauge each observation: we assign it a real number
 330
 Features and weights are linearly combined to obtain a value z ∈ R:
 z(β) := w1f1(β) + w2f2(β) + ... +wkfk(β) + c
 k
 =
 wifi(β) + c
 i=1
 = ⃗w · ⃗ β +c
 with c a constant, called “bias”.
 This defines a linear real-valued function
 which can range from −∞ to +∞.
 z : V →R
 ⇒zis not a probability!
Linearity
 A (real-valued) linear function is one that can be expressed as a first-degree polynomial
 331
 Given generically n arguments x1,x2,...,xn, a first-degree polynomial is of the form
 n
 a1x1 +a2x2 +... +anxn +a0 =
 with a1,a2,...,an and a0 constant coefficients.
 i=1
 aixi + a0
 ⇒Thearguments of a polynomial of degree d can only have powers between 0 and d
 Both coefficients and arguments can be represented by vectors in Rn, and the polynomial as
 ⃗
 a ·⃗x + a0 :=⃗a · (⃗x,1)
 using the dot product.
 Polynomials are very simple functions with good properties
Linear spaces
 The roots of a polynomial p(⃗x) are all⃗r ∈ Rn such that
 p(⃗r) = 0
 332
 Geometrically, the points corresponding to the roots of a polynomial define a subspace of Rn
 For example, on R2 the generic polynomial is
 ax +by +c
 and solving for its roots we obtain
 ax +by +c =0
 y =−a
 bx− c
 b
 ⇒infinite solutions with one co-ordinate varying in function of the other
Hyperplanes in the hyperspace
 y
 (−3,1)
 (2, 3)
 (0, 1
 3)
 O
 (1
 2 , 0)
 x
 A hyperplane in R2 is a line, such as
 ℓ(x, y) := 2x +3y −1 = 0
 In other dimensions:
 R1 apoint x1 = c (froma1x1 +a0 = 0
 simplifying with c = −a0
 a1 
)
 333
 R3 aplane
 a1x1 +a2x2 +a3x3 +a0 = 0
 Rn ageneric hyperplane⃗a ·⃗x = 0
 We notice that:
 ℓ(2, 3)
 =
 2 · 2+3·3−1 = 6 ≥ 0
 ℓ(−3,1) = 2·−3+3·1−1 = −4 ≤ 0
 The space is divided into two regions by sign
Orthogonality of the coefficient vector
 A quick way to ascertain the hyperplane determined by ⃗w
 and c is to notice that
 334
 y
 ⃗
 w =(2,3)
 O
 x
 2x +3y −1
 The vector ⃗w is perpendicular to
 the hyperplane it determines
 In the exampleR2,ifaline hasintersections with the axes
 x I1 =(−c
 a ,0)
 y I2 =(0,−c
 b)
 a vector representing its direction is
 −→
 I2I1 = ( c
 a ,−c
 b) = c(1
 a ,−1
 b)
 whence we can compute
 −→
 I2I1 · ⃗w = c(1
 a ,−1
 b) · ⃗w
 =c(1
 a · a − 1
 b ·b)
 =c(1−1) = c·0 =0
 . . . quod demonstrandum erat!
Squashing values
 1
 0.8
 0.6
 y
 0.4
 0.2
 0
 −4
 −2
 335
 The sigmoid function
 σ(x) = 1
 1 +e−x
 is used as a normalising function.
 We notice:
 ▶ σisdefined on all of R
 ▶ σ(x) ∈ (0,1)
 ▶ σ(0) = 1
 2
 ▶ 1−σ(x)=σ(−x)(∼symmetry)
 ▶ σ(x) is always increasing
 0
 2
 4
 ▶ σ(x) is smooth
 x
Probabilising
 Having computed z from β, the features and the weights, we put
 p(1|β) := σ(z(β)) =
 and conversely
 1
 1 +e−(⃗w·⃗ β+c)
 p(0|β) := 1 −p(1|β) = 1−σ(z(β)) = σ(−z(β)) =
 The two probabilities are complementary
 336
 1
 1 +e⃗w·⃗ β+c
 To choose which state to assign β, we define a threshold θ ∈ (0,1) (usually θ = 1
 2) such that
 δθ(β) = 1 ifp(1|β) > θ
 0 else
 ⇒δθ is our classificator function!
More observations
 We might want to classify more than one observation at the same time
 337
 If we consider B = β1,β2,...,βm, we will have m vectors
 ⃗
 β1, ⃗ β2, . . . , ⃗ βm
 when applying the features to each of them.
 We can consider them all at once as a matrix:
 
 
 ⃗
 β1
 ⃗
 B =
 
 
 
 β2
 .
 .
 .
 ⃗
 βm
 
 
 
 
 
 The matrix B has dimension m×k.
 Now, defining a ‘constant’ vector⃗c = (c,c,...,c) ∈ Rk, we compute
 ⃗
 p =B·⃗wT +⃗cT
More observations
 The entries of the vector8
 are of the type
 i. e. they are the probabilities p(1|βi) for each observation!
 Matrix computations are compact and computationally efficient
 338
 ⃗
 p =B·⃗wT +⃗cT
 pi = ⃗ βi · ⃗w + c
 8If we write⃗x = (x1,x2,...,xn) ∈ Rn, the notation⃗xT is the same vector written vertically, i.e.of dimension
 n ×1instead of 1 ×n. This needs to be formalised for matrix products.
More states
 339
 To deal with state vocabularies S such that |S| > 2 (i.e. non-binary), we deal with probability
 vectors of the form
 ⃗
 p = p(s1|β),p(s2|β),...,p(st|β)
 if |S| = t.
 For ⃗p to be a probability distribution over the states, we require
 pi ∈ [0,1] ∀i ∈ {1,2,...,t}
 t
 pi = 1
 i=1
 If we know that β is assigned the state sj, we will represent this as
 ⃗
 p =(0,0,...,0,1,0,...,0)
 i. e. a vector with only a non zero value in position j.
Squashing vectors
 The generalisation of the sigmoid to vectors is a normalised exponential function (softmax)
 340
 Given ⃗x ∈ Rn, it is a function σ : Rn −→ Rn defined as
 σ(⃗x) := 
ex1
 n
 i=1 exi 
, . . . ,
 = 1
 n
 exn
 n
 i=1 exi
 i=1 exi 
· (ex1,...,exn)
 = e⃗x
 ⃗
 1n · e⃗x
 ⇒the vector σ(⃗x) satisfies our requisites of representing a probability distribution!
Imagining the softmax
 y
 (0, 1)
 σ(R2)
 O
 (1, 0)
 The image of the softmax
 σ(Rn) ⊂ Rn
 341
 in the example of R2 is the subset of the plane
 {(x,y) | x,y ∈ (0,1), x +y = 1}
 x
 so we can visualise it as the segment of the
 line x + y − 1 = 0 between the extremes
 (0, 1) and (1,0) (not included).
 ⇒In more dimensions, it will be a section of
 the corresponding hyperplane.
 All points in R2 get “squeezed” there, and
 those already there get shifted towards the
 segment’s middle point.
More states
 The probabilities p(sj|β) in this model are thus computed as
 p(sj|β) := σ(⃗ β · ⃗wj + cj)
 with ⃗wj and cj the weights specific for a state.
 The features stay the same, but they have not the same importance for every state!
 342
 We again use a matricial representation
 ⃗
 p =σ(W · ⃗ βT +⃗cT)
 with⃗c = (c1,c2,...,ct) ∈ Rt, W of dimensions t ×k, and the function applied componentwise.
Decisions with more states
 In a multinomial setting, (i.e.more than two states) we can define the decision function as
 δθ(β) = argmax
 i∈{1,...,S}
 that is, we take the state with maximum probability.
 ⃗
 p
 NB: the maximum possible value in the normalised vector can be 1
 NB2: a large value in one dimension will constrain the others to notably smaller values
 343
What it is all about
 Given the observations, we want to find the weights which better estimate them
 344
 If we choose a β, have defined the features and know the state β is associated with in the
 training, we notice
 δθ(β,F, ⃗w) = δθ(⃗w)
 where we intend c included in the weights.
 ⇒the classifier is a function of the weights
 We are defining an infinite family of functions varying with the weights!
 ⇒the objective becomes to determine some weights which output the better estimates
Estimates
 Given our state set S = {1,0}, we have
 ▶ aknown, “true” probability distribution ˆ π = {ˆ p,1 − ˆ p} over S
 −→ since we know the annotated state for each β
 ▶ anestimated probability distribution ˜ π over S determined by ˜ p = σ(z(⃗w))
 −→ this distribution is a function of the weight vector ⃗w
 We want to define a
 ∆: ˆ π × ˜ π −→ R
 which measures the similarity/distance between knowledge and prediction.
 ⇒error/loss function
 345
Mind the gap
 Goal
 346
 To measure how much information (∼bits) we need to describe the
 underlying “true” distribution by means of another, approximated distribution
 ⇒Cross-entropy of ˜ π and ˆ π
 We define cross-entropy9 for the two random variables ξ and ψ sharing the same sample
 space Ω as10
 H(ξ||ψ) = −
 p(ξ = ω)log2p(ψ = ω)
 ω∈Ω
 This is in a sense the expected value of ψ’s distribution from the perspective of ξ’s!
 9Which is equivalently expressed as H(ξ) + D(ξ||ψ), where the term D(ξ||ψ) is usually called the Kullback-Leibler distance or
 relative entropy; see Cover & Thomas (1991), Elements of Information Theory, §2.3.
 10Here the notation H(ξ||ψ) is used, as a cross-reference to the Kullback-Leibler distance, instead of the more common H(ξ,ψ),
 which might be confused with the joint entropy.
Mind the weights
 In the binary classification framework with S = {0,1} we compute:
 H(ˆ π||˜
 π) = −
 p(ˆ π = ω)log2 p(˜ π = ω)
 s∈S
 =−p(ˆ π =0)log2p(˜ π = 0)+p(ˆ π = 1)log2p(˜ π = 1)
 =− (1−ˆ p)log2(1−˜ p)+ˆ plog2(˜ p)
 347
 ! We notice that H(ˆ π||˜ π) takes values in [0,+∞) and we have H(ˆ π||˜ π) = 0 if and only if ˆ π ≡ ˜ π
 The perfect classifier has no doubts: it assigns probability
 ▶ ˆ p =1for the desired match ...
 ▶ ...and consequently 1 − ˆ p = 0 for the other one
Perfection vs.imperfection
 1
 If we assume to have a perfect classifier and substitute ˆ p = 1 in cross-entropy we obtain
 ∆(ˆ π, ˜ π) := −log2 ˜ p = −log2 σ(⃗w · ⃗ β + c)
 ! We can put 0·log0 = 0 even if logx −→
 x→0 
−∞if we consider it as a limit11
 We observe:
 ▶ ∆(ˆ π,˜ π) −→ 0 when ˜ p also tends towards 1
 −→ there is no difference between the two distributions
 ▶ ∆(ˆ π,˜ π) −→ +∞ when ˜ p instead tends towards 0
 −→ thetotal opposition is valued with the greatest (infinite) error/loss
 11This happens for example in the formula for H(ˆ π||˜ π) if ˆ p = 0 and ˜ p → 0 (it can never be exactly 0 since the
 sigmoid takes values in the open interval (0,1)).
 348
Perfection vs.imperfection
 0
 Assume again that the observation β is assigned the state 1, so ˆ p = 1.
 ∆(ˆ π, ˜ π) := −log2(1 − ˜ p) = −log2 σ(−⃗w · ⃗ β − c)
 We observe:
 ▶ ∆(ˆ π,˜ π) −→ 0 when ˜ p also tends towards 0
 −→ there is no difference between the two distributions
 ▶ ∆(ˆ π,˜ π) −→ +∞ when ˜ p instead tends towards 1
 −→ thetotal opposition is valued with the greatest (infinite) error/loss
 349
Total loss
 We define the average error/loss over all observations B = β1,β2,...,βm as the arithmetic
 mean
 ¯
 ∆= 1
 m 
m
 i=1 
∆(ˆ pi,˜ pi(⃗w))
 where
 ▶ theknown probabilities⃗ˆ p ∈ [0,1]m are fixed and
 ▶ thepredicted probabilities ⃗˜ p ∈ (0,1)m are in function of the weights ⃗w
 and so we want to look for a set of weights12 ⃗w⋆ such that
 ⃗
 w⋆ =argmin
 ⃗
 w∈Rk
 ¯
 ∆(⃗w)
 ! We are granted to find one and exactly one, as the function ¯ ∆(⃗w) is convex
 350
 12For ease of notation, the constant term c is considered as included in the weights.
Convexity
 Convexity
 12
 351
 x) = x2 +3
 10
 2 
4 
6 
8
 −3 −2 −1
 y f(
 1
 2
 A set in Rn where all segments between
 any two points of the set entirely lie inside
 the set
 ⇒the opposite is a concave region
 A real-valued function f(x) : S −→ R is
 said to be convex if for every two points
 x1, x2 ∈ S the segment between them has
 values greater than or equal to those of the
 function over the corresponding points.
 x
 More precisely, if
 3
 f (x1)+t(f(x2)−f(x1)) ≥ f(x1+t(x2−x1))∀t ∈ [0,1]
Convex functions
 1
 0.5
 −0.5
 −1
 y
 0.5
 1
 352
 f (x) = log(x)
 1.5
 2
 2.5
 x
 The logarithm is a concave function, but the
 region under its curve is convex.
 ⇒the opposite function f(x) = −log(x) is
 convex!
 3
 That is the reason why we are granted the
 loss function (cf.sl.347) to be convex
Growth
 f (x) = x2 +3
 10
 2 
4 
6 
8
 −3 −2 −1
 The derivative of a function represents the
 pointwise rate and direction of change in a
 function.
 353
 12
 y
 For example, for f(x) = x2 + 3 we have
 f ′(x) = 2x
 so that
 ▶ f′(2) = 4
 → (strongly) increasing
 ▶ f′(0) = 0
 → stationary, so an extreme (here: the
 minimum at (0,3))
 x
 1
 2
 3
 ▶ f′(−1) = −2
 → (moderately) decreasing
 A convex function has a unique minimum
Multiple dimensions
 In more dimensions we speak of gradient
 354
 ⇒For afunction f : Rn → R change takes place in all n dimensions
 The arguments of our loss function are ⃗w ∈ Rk and c, so we have k +1 dimensions of change,
 computed for a single observation as13
 ∂∆(⃗w,c)
 ∂wi
 ∂∆(⃗w,c)
 ∂c
 =(˜ p −ˆ p)βi
 =˜ p −ˆ p
 NB: we reach the minimum with stationary gradient ⃗ 0 if and only if the approximated
 probability ˜ p coincides with the known probability ˆ p!
 13The ∂ symbol represents a partial derivative taken with respect to only one of the arguments, if there is more
 than one.
Going down the curve
 12
 f (x) = x2 +3
 10
 y
 2 
4 
6 
8
 −3 −2 −1
 Gradient descent
 355
 ###