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 bla is the only word with ED <= 1.

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 1 0 1 0.5]     [1 0]     [1 1 0 1 0.5]
[1 1 1 2  1 ]  =  [1 1]  *  [0 0 1 1 0.5]
[1 1 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   7

The SVM band is just the two horizontal lines.