Векторы вкуса
Сервис рекомендаций хранит таблицу: n читателей, m книг, а в клетке — оценка, если читатель её поставил. Известна малая часть клеток. Чтобы угадывать остальные, каждому читателю i и каждой книге j сопоставляют по r чисел — векторы pi и qj, — и оценку предсказывают их скалярным произведением. Найдите векторы, при которых
Σизвестные (i, j) (aij − pi·qj)² + λ·(Σ|pi|² + Σ|qj|²)
как можно меньше. Ответ засчитывается, если это значение не больше чем на 5 % выше, чем у решения жюри.
Вход
В первой строке — n, m, r и λ (1 ≤ n, m ≤ 200, 1 ≤ r ≤ 4, 0 < λ ≤ 100). Во второй — K, число известных клеток (1 ≤ K ≤ 8000). Дальше K строк: i j aij — номер читателя (от 0), номер книги (от 0) и оценка, вещественное число. Клетки не повторяются.
Выход
В первой строке — значение, которое у вас получилось (проверяющая программа пересчитывает его сама). Дальше n строк по r чисел — векторы читателей, потом m строк по r чисел — векторы книг.
Примеры
Пример 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
Пример 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
Ограничения
- Время · Python
- 20000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если векторы книг известны, задача распадается на n независимых маленьких задач: для каждого читателя — наименьшие квадраты с r неизвестными по его известным клеткам. И наоборот.
2Подсказка 2
Чередуйте: при фиксированных q найдите лучшие p, при фиксированных p — лучшие q. Каждый такой шаг не увеличивает сумму. Но остановиться метод может не в лучшей точке.
3Идея
Чередующиеся наименьшие квадраты (ALS). Для читателя i при фиксированных q сумма — квадратичная функция от pi, и её минимум — решение системы (Σ qjqjT + λE)·pi = Σ aijqj по известным клеткам строки. Матрица положительно определена благодаря λ, поэтому решение единственно даже у читателя с одной оценкой.
4Разбор
Векторы — случайные небольшие числа. Раунд: обновить все p, потом все q, посчитать сумму; остановиться, когда она перестала заметно уменьшаться (на 10−7 от себя). Задача не выпуклая, и ALS может остановиться в плохой точке — первый пример это показывает: с одного старта сумма застревает около 3,64, хотя бывает 0,89. Поэтому запусков несколько, с разных случайных векторов, и берётся лучший.
4+Решение
5Сложность
Раунд — O(K·r² + (n + m)·r³): собрать системы и решить их методом Гаусса. Раундов на тестах — от семи до трёхсот: на плотных таблицах сумма перестаёт падать за десяток раундов, а на разреженной (5 % клеток) убывает медленно, и решение жюри упирается в ограничение 300 раундов.
6Типичные ошибки
- Мало раундов. Это
wrong.py: два раунда с одного старта — сумма ещё далека от минимума. - Без штрафа в системе. Если забыть λ на диагонали, у читателя с одной-двумя оценками система вырождена, а векторы улетают в огромные числа.
- Один старт. Скалярное произведение не меняется, если поменять знак у p и q одновременно, но если знаки «разошлись» на разных книгах, чередование не всегда их согласует.
- Пропуски как нули. Неизвестная клетка — не оценка 0; если вписать нули и разложить всю таблицу, векторы будут предсказывать нули.