Исследователи представили первый точный алгоритм Data Shapley для взвешенной регрессии k-NN
Data Shapley — стандартный подход для оценки ценности точек данных в обучении моделей машинного обучения. Его специализация для метода k-ближайших соседей (k-NN) широко применяется на практике. Однако до сих пор точные алгоритмы существовали только для невзвешенного k-NN и взвешенной классификации. Для взвешенной регрессии и предсказания мягких меток единственным точным методом оставался полный перебор с экспоненциальной сложностью O(N^K).
Исследователи из научной группы представили работу, закрывающую этот пробел. Они предложили первый точный алгоритм для вычисления Data Shapley во взвешенной k-NN регрессии, работающий за псевдополиномиальное время. Метод основан на динамическом программировании с подсчётом состояний суммы весов и суммы взвешенных целей. Алгоритм проверен на 12 716 тестовых примерах, и ошибок не обнаружено.
Кроме того, авторы разработали сертифицированную FPTAS-схему для непрерывных весов и целей, которая предоставляет проверяемую оценку погрешности. Схема прошла 86 400 проверок без нарушений. Также в работе описан ландшафт вычислительной сложности, включающий нижние границы размера выхода и результаты сложности в рамках модели доступа.
Для многоклассового случая представлено расширение на взвешенные мягкие метки. Авторы выпустили открытую библиотеку, работающую только на CPU, и первый точный эталон для взвешенной регрессии Data Shapley.
В эксперименте по обнаружению ошибочных меток точные значения оказались статистически эквивалентны приближению методом Монте-Карло (тест TOST, n=8, p<10^-4). Однако главное преимущество точности — детерминизм, гарантированная погрешность и эталон для аудита. Метод Монте-Карло не смог воспроизвести точный рейтинг топ-10% точек ни при одном бюджете, вплоть до 3000 перестановок.
