TASK 1 (Inverted Index)
1.1 Inverted lists with tf-scores, gap-encoded
bla: 1 tf2, 2 tf2, 4 tf2 -> +1 tf2, +1 tf2, +2 tf2 bli: 2 tf1, 5 tf1 -> +2 tf1, +3 tf1 blu: 3 tf2, 4 tf1, 5 tf2 -> +3 tf2, +1 tf1, +1 tf2
1.3 With entropy-optimal encoding
+1 -> 0 +2 -> 10 +3 -> 11 tf1 -> 0 tf2 -> 1 bla: 01 01 101 bli: 100 110 blu: 111 00 01
TASK 2 (List Intersection)
2.1 Code for intersecting two lists represented as bit vectors:
Array<bool> intersect(Array<bool> list1, Array<bool> list2) {
assert(list1.size() = list2.size());
Array<bool> result;
for (int i = 0; i < list1.size()) { result.push(list1[i] & list2[i]); }
return result;
}CORRECTION NOTE: It can be assumed that they have the same length; if someone does special magic for different lengths that is also fine, but it's not necessary.
2.2 Comparison with gap-encoded representation.
The entropy of the given probability distribution is H(X) = sum_i i / 2^i = 2. Hence, for an entropy-optimal code, we need 2m bits for a list of length m. The bit vector is hence better if and only if m > n/2.
TASK 3 (List Intersection)
3.1 2-gram index and lower bound
W1: #bla# W2: #bli# W3: #blu# #b: W1, W2, W3 bl: W1, W2, W3 la: W1 li: W2 lu: W3 a#: W1 i#: W2 u#: W3 ED(x, y) <= 1 => #common 2-grams of x' and y' must be >= comm := max(|x|, |y|) - 1
3.2 Find all words with ED <= 1 to blaa
x = blaa x' = #blaa# #b: W1, W2, W3 bl: W1, W2, W3 la: W1 aa: a#: W1 2-grams in common with blaa: W1: 4 W2: 2 W3: 2 comm >= 3, so only need to compute edit distance to W1, which is 1, hence fine!
TASK 4 (Latent Semantic Indexing)
4.1 Rank + decomposition
For example, the first three column vectors are linearly independent -> rank 3.
CORRECTION NOTE: no need to prove the linear independence (but the vectors selected should indeed be linear independent). Easy proof for linear independence: compute the determinant, e.g. of the first three column vectors. If it is non-zero, they are linearly independent.
Obtain A' by changing the entry at row 2, column 2 from 0 to 1.
[1 0] [1 1 0 1 0.5]
A' = [1 1] * [0 0 1 1 0.5]
[0 1]
4.2 Ranking for query Q = (1, 1, 0), |Q| = sqrt(2).
Scores with division by |Q|: 1, 1, 1/2, sqrt(3)/2, sqrt(3)/2. Scores without division by |Q|: sqrt(2), sqrt(2), sqrt(1/2), sqrt(3/2), sqrt(3/2).
The ranking is hence D#1, D#2, D#4, D#5, D#3.
TASK 5 (k-means)
5.1 Clustering of 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 with 1 and 2 as initial centroids.
Step 1: 1 | 2 3 4 5 6 7 8 9 10, centroids 1 6 Step 2: 1 2 3 | 4 5 6 7 8 9 10, centroids 2 7 Step 3: 1 2 3 4 | 5 6 7 8 9 10, centroids 2.5 7.5 Step 4: 1 2 3 4 5 | 6 7 8 9 10, centroids 3 8 No more change!
5.2 Same clustering for any choice of initial centroids.
Observation 1: Clustering is always in two contiguous parts. Assume not yet half-half. Then the left-most element of the right part will be assigned to left cluster (or vice versa).
TASK 6 (Naive Bayes)
6.1 Computing the priors and classifying xy and xxxy
Pr(x|X) = 2/3, Pr(y|X) = 1/3, Pr(x|Y) = 2/3, Pr(y|Y) = 1/3, Pr(X) = 2/3, Pr(Y) = 1/3 Pr(X|xy) / Pr(Y|xy) = Pr(X) / Pr(Y) = 2, and the same for Pr(X|xxy) / Pr(Y|xxxy).
Hence both xy and xxxy are classified as X
6.2 Generalization + draw points and band of SVM corresponding classifier.
For any w = (nx, ny): Pr(X|w) = Pr(X) * Pr(x|X)^nx * Pr(y|X)^ny = 2/3 * (2/3)^nx * (1/3)^ny Pr(Y|w) = Pr(Y) * Pr(x|Y)^nx * Pr(y|Y)^ny = 1/3 * (2/3)^nx * (1/3)^ny Hence always Pr(X|w) / Pr(Y|w) = 2 => any w will be classified as X.
2 ---X--------X-------X-------X---
1 ---Y--------Y-------------------
0 1 2 3 4 5 6 7The SVM margin is just two horizontal lines (marked
).