Новый алгоритм для отбора разнообразных данных: решение NP-трудной задачи за почти линейное время
Задача выбора небольшого, разнообразного и качественного подмножества из огромного пула кандидатов является ключевой в современном машинном обучении. Она возникает при формировании датасетов для обучения больших моделей, отборе примеров для обучения с подкреплением, подборе промптов для in-context обучения и других приложениях.
Точечные процессы определителя (DPP) предлагают математически строгий подход к измерению разнообразия, однако их MAP-задача (выбор подмножества размера k, максимизирующего логарифм определителя) является NP-трудной. Стандартные жадные и семплинговые алгоритмы имеют суперлинейную сложность по размеру исходного набора n, что критично при работе с миллионами и миллиардами примеров.
Авторы новой работы на arXiv (2606.19411) переформулировали DPP-MAP как задачу непрерывной оптимизации на многообразии Штифеля. Они показали, что условия оптимальности первого порядка сводятся к нелинейной задаче на собственные значения (NEPv) ранее не изученного типа.
Для решения этой NEPv предложен итерационный метод самосогласованного поля (SCF) с гарантией локальной сходимости, основанной на спектральной щели. Алгоритм, названный Spectral DPP, требует только умножений матрицы на вектор и выполняется за время O((ndk+nk^2)t) для малого числа итераций t.
Это означает, что сложность алгоритма почти линейна по n, что делает его применимым для гигантских наборов данных. Метод хорошо совместим с низкоранговыми ядрами и ядрами на основе признаков, широко используемыми в ML.
В статье представлен теоретический анализ релаксации, решателя и масштабируемости; полное тестирование на реальных данных запланировано в будущем эмпирическом исследовании. Работа открывает путь к эффективному использованию DPP в сценариях, где разнообразие данных критически важно.
