A wine competition has d tasters, and each row of rows holds the scores one wine got from them. The organisers suspect the tasters really judge only a couple of hidden qualities, so a few directions should describe most of the variation. Measure it.
Write explained_variance(rows, k, rounds) that returns a list of k floats: the share of the total variance carried by each of the first k principal components, computed exactly like this:
- Centre the data and build the covariance matrix
C(divide byn). The total variance is the sum of the diagonal entries of this originalC. - For each component in turn: start from
v = [1.0, 2.0, 3.0, ..., d](entryiisi + 1), repeatroundstimesw = C·v,v = w / |w|. Its variance isλ = v·(C·v)and its share isλ / total. - Before looking for the next component, remove this one from the matrix (deflation):
C[i][j] ← C[i][j] - λ · v[i] · v[j]for everyi,j.
tasting_panel(n, d, seed) builds the tables the tests use; it is available in your code, so you can try it with Run.
Examples
Input: rows = [[2, 0], [0, 2], [4, 4], [2, 2]], k = 2, rounds = 50
Output: [0.7500000000000001, 0.25000000000000006]
Explanation: C = [[2, 1], [1, 2]] with total variance 4. The first component is the diagonal with
variance 3; after deflation C becomes [[0.5, -0.5], [-0.5, 0.5]], whose component is the other
diagonal with variance 1.
Input: rows = [[59, 52, 62], [50, 50, 68], [71, 66, 66], [46, 42, 69], [64, 60, 55], [55, 49, 72],
[68, 61, 60], [52, 47, 64]], k = 2, rounds = 100
Output: [0.8770187678361232, 0.11042439899280906]
Constraints
2 <= n <= 1000,2 <= d <= 8,1 <= k <= d,1 <= rounds <= 200- the tests make sure that
C·vis never the zero vector - floats are compared with a tolerance of
1e-6
Goals
- Find several principal components one after another by deflating the covariance matrix
- Express each component's variance as a share of the total variance
- See how few directions describe data driven by a few hidden factors