Taste vectors
A recommendation service keeps a table: n readers, m books, and a cell holds a rating if the reader gave one. A small part of the cells is known. To guess the rest, each reader i and each book j get r numbers each, vectors pi and qj, and a rating is predicted by their dot product. Find vectors for which
Σknown (i, j) (aij − pi·qj)² + λ·(Σ|pi|² + Σ|qj|²)
is as small as possible. An answer is accepted if this value is at most 5% above that of the jury’s solution.
Input
The first line holds n, m, r and λ (1 ≤ n, m ≤ 200, 1 ≤ r ≤ 4, 0 < λ ≤ 100). The second holds K, the number of known cells (1 ≤ K ≤ 8000). Then K lines: i j aij, the reader’s number (from 0), the book’s number (from 0) and the rating, a real number. Cells do not repeat.
Output
The first line holds the value you obtained (the checker recomputes it itself). Then n lines of r numbers, the reader vectors, then m lines of r numbers, the book vectors.
Examples
Example 1
2 2 1 0.1 3 0 0 1.00 0 1 2.00 1 0 2.00
0.892475 -1.074745 -1.713704 -1.074023 -1.712637
Example 2
3 3 1 1.0 3 0 0 4.00 1 1 4.00 2 2 4.00
21.000000 -1.732054 1.732034 -1.732102 -1.732049 1.732059 -1.732025
Limits
- Time · Python
- 20000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
If the book vectors are known, the problem splits into n independent small problems: for each reader, least squares with r unknowns over their known cells. And the other way round.
2Hint 2
Alternate: with q fixed, find the best p; with p fixed, the best q. Each such step does not increase the sum. But the method may stop at a point that is not the best.
3The idea
Alternating least squares (ALS). For reader i with q fixed, the sum is a quadratic function of pi, and its minimum is the solution of the system (Σ qjqjT + λE)·pi = Σ aijqj over the known cells of the row. The matrix is positive definite thanks to λ, so the solution is unique even for a reader with one rating.
4Walkthrough
The vectors start as small random numbers. A round: update all p, then all q, compute the sum; stop when it has stopped decreasing noticeably (by 10−7 of itself). The problem is not convex, and ALS may stop at a bad point; the first example shows it: from one start the sum gets stuck at about 3.64, although 0.89 is possible. So there are several runs from different random vectors, and the best is taken.
4+Solution
5Complexity
A round is O(K·r² + (n + m)·r³): assemble the systems and solve them by Gaussian elimination. On the tests the rounds number from seven to three hundred: on dense tables the sum stops falling within a dozen rounds, while on a sparse one (5% of cells) it decreases slowly, and the jury’s solution hits the limit of 300 rounds.
6Common mistakes
- Too few rounds. This is
wrong.py: two rounds from one start, with the sum still far from the minimum. - No penalty in the system. If λ is forgotten on the diagonal, for a reader with one or two ratings the system is degenerate, and the vectors fly off to huge numbers.
- One start. The dot product does not change if the signs of p and q are flipped together, but if the signs have “diverged” across different books, alternation does not always reconcile them.
- Gaps as zeros. An unknown cell is not a rating of 0; if zeros are written in and the whole table is factorized, the vectors will predict zeros.