Разбор задачи о покрытии множеств на примере игры Contexto. Узнайте, как жадный алгоритм ищет лучшие стартовые слова. Читайте и применяйте!
Вы когда-нибудь замечали, что топ-N списков часто бесполезны? Я столкнулся с такой проблемой при анализе игры Contexto. Наивный подход — ранжировать слова по частоте попадания в топ-100 — дал удивительно плохой результат: все лучшие слова были похожи друг на друга. Оказалось, что это не задача ранжирования, а задача о покрытии множеств. В этой статье я покажу, как жадный алгоритм решает её и почему это меняет подход к выбору стратегии.
Contexto — ежедневная игра, где нужно угадать скрытое слово по семантической близости. Игроки хотят знать хорошие стартовые слова. Я проанализировал 1421 головоломку и ранжировал слова по частоте попадания в топ-100. Результат: картофель, помидор, лук и их соседи. Все эти слова — еда, и они срабатывают в одни и те же дни, а в другие — молчат.
Проблема в том, что метрика оценивала каждое слово отдельно. Но игроку нужен набор слов, которые покрывают разные головоломки. Это не ранжирование, а задача о покрытии множеств.
Рассмотрим каждую головоломку как элемент, а каждое слово как множество головоломок, где оно попадает в топ-100. Жадный алгоритм: на каждом шаге выбираем слово, покрывающее максимум непокрытых головоломок. При равенстве — по алфавиту для детерминизма.
Результат для первых 10 слов:
Эти 10 слов покрывают 60.5% головоломок. Разнообразие (глагол, еда, место, цвет, часть тела, контейнер, животное) — не дизайн, а результат алгоритма: после выбора salad остальные слова-еда почти ничего не добавляют.
Это стандартная жадная аппроксимация NP-трудной задачи, поэтому не гарантирует оптимум, но детерминирована и воспроизводима.
Contexto публикует топ-500. Слово вне топ-500 не имеет наблюдаемого ранга. Это не пропущенные данные, а цензурирование справа: истинное значение существует, но известно, что оно хуже 500.
Это различие решает всё. Если усреднять только наблюдаемые ранги, слово, попавшее на 3-е место два дня из 1421, обойдёт слово, которое на 200-м месте тысячу раз. Первое — шум, второе — то, что нужно. Поэтому в результатах нет среднего ранга. Используются частоты покрытия и медианы по головоломкам, где слово появилось, с указанием частоты появления.
Объединение данных за 4 года предполагает, что модель не менялась. Если эмбеддинги переобучались, ранние и поздние головоломки несравнимы.
Проверка: внутри года разбиваем головоломки на две половины (по чётности id) и сравниваем 50 слов с наибольшим покрытием по коэффициенту Жаккара. Это базовый уровень. Затем сравниваем половины соседних лет. Внутригодовой базовый уровень — медиана 0.754. Минимальное межгодовое сравнение — 0.493, что выше порога. Проверка пройдена, но она показывает стабильность множества слов, а не точных рангов.
Популярный гайд рекомендует начинать с person, place, thing, idea, concept, затем food, occupation, animal, event, затем city, nature, home, work, technology. Проверим тем же методом:
Гайд прав в идее: разнообразие категорий лучше одного слова. Но конкретные слова — абстрактные категории, которые находятся на среднем расстоянии от всего, редко попадают в топ. Например, occupation в топ-500 всего в 0.8% головоломок.
Когда топ-N список кажется неудовлетворительным, проверьте, независимы ли элементы. Если выбор второго лучшего почти не добавляет ценности, вы решаете задачу ранжирования, когда нужно покрытие. Исправление — другой алгоритм, а не лучшая метрика.
Прямо сейчас: возьмите свои данные и проверьте, не дублируют ли лучшие элементы друг друга. Если да — используйте жадное покрытие множеств. Это просто и эффективно.
Хочешь закрепить знания на практике?
Решай задачи на Algolit — интерактивная платформа для обучения
Начать бесплатно →