TASK 1 (Ranking and evaluation)
bla 1 1 2 2 3 bli 1 0 1 2 2 blu 0 1 1 0 1
1.1 AP for query "bla bli"
The vector for "bla blu" is simply (1, 0, 1) Dot product similarities for D1, ..., D5: 1, 2, 3, 2, 4 Documents ordered by these similarities: D5, D3, D2 and D4, D1 (D2 and D4 have the same score) Bit array of relevances: 1, 0, 0, 0, 1 Precisions: P@1 = 100%, P@5 = 40% (the others are not needed to compute the AP) Average precision (AP): 70%
1.2 Function compute_ap
def compute_ap(relevances):
prec_sum = 0
num_rel = 0
for i in range(len(relevances)):
if relevances[i] == 1:
num_rel += 1
prec = num_rel / (i + 1)
prec_sum += prec
return prec_sum / num_rel
1.3 Prove that AP = 100% if and only if all 1s at the front
If all 1s at the front, then each prec in the code above is 100%, and so will be the average.
If AP = 100%, then the last prec must be 100%, which can only happen if there is no 0 before the last 1.
=== 1.4
1 1 2 2 3 1 1 1 0 1 2 2 = 1 0 * 1 0 1 2 2 0 1 1 0 1 0 1 0 1 1 0 1
This shows that each column of A can be written as a linear combination of the two columns of the 3 x 2 matrix on the right hand side. This proves that rank(A) <= 2.