Доказана оптимальность последовательной фильтрации: порядок этапов влияет на затраты

Учёные опубликовали на arXiv препринт, в котором формально доказали оптимальное правило упорядочивания этапов в последовательных фильтрах. Такие системы широко применяются в ранжировании, каскадном машинном обучении и выявлении мошенничества: каждый этап проверяет множество объектов и часть отбраковывает, тратя ресурсы.

Авторы рассмотрели модель, где стоимость каждого этапа и вероятность отбраковки не зависят от других. Для такой постановки доказано, что минимальные ожидаемые общие затраты достигаются при сортировке фильтров по возрастанию отношения стоимости к вероятности отбраковки (cost-to-rejection ratio).

С помощью обширного Monte Carlo моделирования было показано, что оптимальный порядок строго доминирует над распространёнными эвристиками во всех прогонах — как по средним значениям, так и по полному распределению результатов.

Результат имеет практическое значение для проектирования высоконагруженных систем, где важно снизить вычислительные расходы без потери качества отбора. Например, в системах рекомендаций или поточного обнаружения аномалий оптимальная настройка последовательности фильтров может дать существенную экономию ресурсов.

Работа опирается на строгий математический аппарат и не требует дополнительных предположений, кроме независимости моделей стоимости и селективности. Авторы отмечают, что найденное правило просто в применении и не уступает более сложным методам.