Linear classification

Question 1

Data-set

Answer 1

x vector of d attributes
x=[x1,x2,…,xd]
y=f(x)
data set {(x1,y1),…,(xN,yN)}

Question 2

Hypothesis set

Answer 2

Perceptron:
h(x) = sign(sum(i=1,d) wi*xi + b)
linear combination of the attributes, plus a bias b

• > h(x) = sign(sum(i=0,d) wi*xi)
  where w0 = b and x0 = 1
  unknowns: w=[w0,w1,…,wd]’

Question 3

Learning algorithm

Answer 3

Perceptron Learning algorithm PLA

Main assumption: there exist a separating hyperplane (data must be linearly separable)

Idea:

• start from a misclassified point
• update w such that the point is correctly classified
• > update rule: w(i+1) = w(i) + y(i)*x(i)

Question 4

Convergence of the PLA

Answer 4

PLA converges to a perfect classification in a finite number of iterations
- > Ein(h) = 0

Question 5

Generalization of PLA

Answer 5

Eout(h) = P[h(x) != f(x)] = Ein(h) + O( sqrt(d/N*ln(N) )

Question 6

Confusion matrix

Answer 6

[ a b
c d ]

a: true positive
b: false positive

c: false negative
d: true negative

Question 7

Precision

Answer 7

Precision or positive predicted value

PPV = a/(a+b)

Question 8

Recall

Answer 8

Recall or true positive rate

TPR = a/(a+c)

Question 9

F1-score

Answer 9

F1 = 2* PPV*TPR/(PPV+TPR)

Question 10

Performance indexes

Answer 10

• Precision or positive predicted value
• Recall or true positive rate
• F1-score