Chapter 3- Linear Models

Question 1

what is a decision stump

Answer 1

single feature

threshold required to switch decision from 0 to 1 is parameter t

Question 2

what is the decision boundary in a decision stump

Answer 2

the point at which the decision switches,

the threshold, t

Question 3

what is the learning algorithm for a decision stump

Answer 3

for t varied between min(x) and max(x):
count errors
if errors is less than minErr, set as minErr and t

Question 4

what does linearly separable mean?

Answer 4

we can fit a linear model (i.e. draw a linear decision boundary) and perfectly separate the classes

Question 5

what is the limitation of a decision stump?

Answer 5

it works only on a single feature

Question 6

what is the discriminant function f(x)=?

Answer 6

(sum for all features: wjxj) - t
or in matrix notation:
wTx - t

Question 7

what does the discriminant function describe, geometrically?

Answer 7

the equation of a plane

Question 8

what is the gradient and y intercept of the decision boundary from the discriminant function in two dimensions?

Answer 8

set equal to zero
m = -(w1/w2)
c = t/w2

Question 9

what is the perceptron decision rule?

Answer 9

if f(x) > 0 then yhat=1 else 0

Question 10

what is the perceptron parameter update rule, with sigmoid error?

Answer 10

wj = wj - (lrate)(yhat - y)(xj)

Question 11

what is the perceptron learning algorithm?

Answer 11

for each training sample:
update weight: wj = wj - (lrate)(yhat - y)(xj)
t = t + lrate(yhat-y)
until changes to parameters are zero

Question 12

what is learning rate?

Answer 12

the step size of the update

Question 13

what is the limitation of the perceptron algorithm?

Answer 13

can only solve linearly separable problems

Question 14

if …. the perceptron algorithm is guaranteed to solve the problem

Answer 14

the data is linearly separable

Question 15

what is the perceptron convergence theorem?

Answer 15

If a dataset is linearly separable, the perceptron learning algorithm will converge to a perfect classification within a finite number of training steps

Question 16

a logistic regression model has the output f(x) = ?

Answer 16

1 / 1+e^-z

where z is wT - t

Question 17

what is the name of the function that logistic regression uses?

Answer 17

sigmoid

Question 18

what is the decision rule for logistic regression?

Answer 18

if f(x) >0.5 then 1 else 0

Question 19

what is loss?

Answer 19

the cost incurred by a model for a prediction it makes

Question 20

what loss function does logistic regression use?

Answer 20

log loss, or cross-entropy

Question 21

what is the equation for log loss (cross entropy), L(f(x),y) = ?

Answer 21

L(f(x),y) = -{ylogf(x) + (1-y)log(1-f(x))}

Question 22

what is an error function?

Answer 22

when the loss function is summed or averaged over all data points

Question 23

what is the error function (summed log loss) for logistic regression E=?

Answer 23

• (sum for each i) {yilog(f(xi)) + (1-yi)log(1-f(xi))}

Question 24

what are the names the error function for logistic regression is known by?

Answer 24

cross entropy error

negative log likelihood

Question 25

what is the rule of gradient descent, in words?

Answer 25

in order to decrease error, we should update parameters in the direction of the negative gradient

Question 26

what is the partial derivative of the cross entropy error function with the logistic regression model, with respect to parameter wj, dE / dwj = ?

Answer 26

dE/df(x) x df(x)/dz x dz/dwj

= sum of i: (f(xi) - yi)xij

Question 27

what is the algorithm for gradient descent?

Answer 27

repeat:
for each parameter j do
wj = wj - lrate x dE/dwj
until termination criteria met

Question 28

what is stochastic gradient descent?

Answer 28

compute the gradient for each example one by one and modify the parameters for each

Question 29

why is stochastic gradient descent often applied?

Answer 29

it works well more effectively in very large datasets

Question 30

what is the algorithm for logistic regression?

Answer 30

t = random
w = random vector
set max epochs
lrate = 0.1

for each epoch:
    for each training example x:
        for each parameter j
            wj = wj - lrate(f(x)-y)(xj)
    t = t + lrate(f(x)-y)

Question 31

what loss function does the perceptron use?

Answer 31

hinge loss

Question 32

give the equation for hinge loss

Answer 32

sum: -y(wx + b)
= sum: -y(yhat)
sum all the negative values for ONLY the misclassified samples

Question 33

stochastic gradient descent is also known as

Answer 33

mini batch

Question 34

gradient based optimisation is possible when the loss function is

Answer 34

differentiable

Question 35

what are the 4 steps of gradient based minimisation?

Answer 35

1. test for convergence
2. compute search direction
3. compute step length
4. update the variables

Question 36

when we perform minibatch sgd, what do we times sum:dL/dW by to scale it

Answer 36

n / |S|

n samples / batch size

Question 37

modern machine learning has given rise to what kind of programming

Answer 37

differentiable programming

Question 38

what is differentiable programming

Answer 38

If the performance of a computer program can be represented by a loss function, we could seek to optimise that program via its parameters using a gradient based approach

Question 39

the perceptron algorithm is a … … classification algorithm

Answer 39

deterministic

binary

Question 40

what is a generative process

Answer 40

describes the way in which data is generated

Question 41

what is the perceptron weight update, with hinge loss?

Answer 41

wj = wj - (lrate)( - yhat x y)(xj)
or if just for the misclassified
wj = wj - (lrate)( -y)(xj)
= wj + (lrate)(y)(xj)

Question 42

we make the iid assumption for logistic regression, this is that

Answer 42

our data are independent and identically distributed (iid).

Question 43

the iid assumption means that the outputs …

Answer 43

The outputs do not depend on multiple inputs nor on other outputs.

Question 44

the iid assumption we make for logistic regression means

Answer 44

we can perform maximum likelihood estimation

i.e. we can work out the best parameters from the data by maximising
p( W | D) = multiply:p(y | x, w)

Question 45

what is the loss function (negative log-likelihood) for SGD for logistic regression

Answer 45

• 1/n sumi->n:[yi log f(xi) + (1-yi) log (1-f(xi))]

same but with 1/n to rescale based on sample size

Question 46

we can use logistic regression to work out p(y=1 | x, w) =

Answer 46

f(x) = 1 / (1 + e^-z)

Question 47

the decision boundary for logistic regression is given by

Answer 47

d = 1 / (1+e^-z)

wx + b = log(d / 1-d)

Question 48

what are the 3 data properties that will cause practical challenges for a logistic regression model

Answer 48

imbalanced data - anything using MLE will try to fit the dominant class

multicollinearity - two or more predictor variables are highly linearly related.

completely separated training data

Question 49

what step can we take to minimise the impact of multicollinearity in logistic regression

Answer 49

feature selection

Question 50

benefits of logistic regression (5)

Answer 50

• Efficient and straightforward,
  
  • Doesn’t require large computation,
  • Easy to implement, easily interpretable
  • Used widely by data analyst and scientist.
  • Provides a probability for predictions and observations.

Question 51

limitations of logistic regression (2 general, 3 data properties)

Answer 51

• Linear decision boundaries
• Inability to handle complex inputs (e.g. an image)
• Multicollinearity (correlated inputs)
• Sparseness (lots of zero or identical inputs)
• Complete separation (it is not a probabilistic problem!)

Question 52

limitations of perceptron (4)

Answer 52

Challenges with high dimensional multiple correlated input features

linear

Convergence can be tricky depending on the variant of perceptron used

deterministic

Question 53

which algorithm: perceptron or logistic regression, doesnt converge

Answer 53

logistic regression

Question 54

why does logistic regression never converge

Answer 54

we can never reach the true decision boundary. We are trying to fit an s form to a straight boundary. Eventually we get w1=inf. This is the closest we will get.

Question 55

what property of logarithm means we can take the log of the likelihood

Answer 55

logarithm is a monotonically increasing function.

It doesnt affect where out max/min is

Question 56

what is a monotonically increasing function, what does it mean?

Answer 56

if the value on the x-axis increases, the value on the y-axis also increases