Материал подготовлен автоматически по первоисточникам: ссылки на них — в конце статьи.
Стоимость диагностического теста или другого признака можно учитывать прямо при выборе следующего измерения, а затем оценить, насколько жадная политика отстаёт от оптимальной. В нерецензированном препринте, где все числа получены автором, Joseph Bingham из Technion проверил полученную оценку на 4 000 задачах с разной стоимостью признаков: ошибка жадного выбора оказалась близка к нулю. Для продуктовой команды это превращает коэффициент штрафа из настройки «на глаз» в управляемую цену данных, хотя на крупных задачах сертификат остаётся диагностикой, а не численной гарантией.
Почему штраф за стоимость — не эвристика
Активный отбор признаков последовательно решает, какие данные запросить перед прогнозом. В медицине это лабораторные тесты, во фроде — дополнительные проверки, в интерактивной анкете — следующий вопрос. Каждое действие раскрывает новый признак, стоит денег или времени и должно укладываться в общий бюджет.
EIG-Cost оценивает доступное действие как ожидаемый прирост информации минус его стоимость, умноженную на коэффициент λ. Алгоритм выбирает действие с наибольшей положительной оценкой и останавливается, если подходящих действий не осталось, бюджет исчерпан или все оценки стали неположительными.
Работа связывает это правило с глобальной целью. Сумма ожидаемых приростов информации по шагам равна информации обо всей траектории: какие признаки выбрали, какие значения увидели и когда остановились. Поэтому сумма оценок EIG-Cost равна информации траектории за вычетом ожидаемой стоимости.
Отсюда появляется лагранжева релаксация. Вместо прямого ограничения бюджета оптимизатор вычитает из результата λ за каждую единицу стоимости. Сам λ играет роль теневой цены: чем он выше, тем больше информации должен принести признак, чтобы алгоритм согласился его купить. При этом EIG-Cost сохраняет жёсткий предел и не выполняет действие, которое превысит остаток бюджета.
Как сертификат отделяет недобор бюджета от ошибки выбора
Жадный шаг ещё не означает, что вся последовательность оптимальна. Сертификат разделяет разрыв между EIG-Cost и лучшей политикой с жёстким бюджетом на две части. Первая отвечает за запас бюджета, который политика не использовала; вторая, обозначенная Δλ, показывает, сколько жадная последовательность теряет относительно оптимума задачи со штрафом.
Такое разделение помогает локализовать проблему. Большой первый член означает, что λ слишком рано заставляет политику остановиться. Большой Δλ означает, что локально привлекательные действия складываются в слабую последовательность и одного изменения цены недостаточно.
Вычислить Δλ можно, только если доступен оптимум задачи со штрафом. На малых задачах с неодинаковой стоимостью признаки перебрали точно, и сертификат ограничил фактический разрыв во всех проверенных случаях. На клиническом масштабе такой перебор непрактичен, поэтому разложение показывает источники ошибки, но не даёт готовой верхней границы.
Классическая гарантия для жадных алгоритмов здесь тоже не переносится автоматически. Она требует свойства убывающей отдачи, которое называют субмодулярностью: каждый следующий признак должен приносить не больше пользы после расширения уже известного набора. В работе приведён гауссовский пример, где два признака усиливают друг друга. Для равной стоимости и неадаптивного выбора остаётся отдельная гарантия, зависящая от близости задачи к субмодулярной, но общий адаптивный алгоритм с разными ценами её не наследует.
Когда работа меняет планы продукта
Подход применим, если система покупает данные по одному и может остановиться: заказывает проверку, задаёт вопрос или запускает измерение. В такой архитектуре EIG-Cost стоит рассматривать как объяснимую базовую политику перед обучением агента с подкреплением. Коэффициент λ позволяет менять компромисс между информацией и расходами без повторного обучения генератора признаков и классификатора.
Эксперименты охватывают синтетические гауссовские задачи, CKD, PhysioNet 2012 и MIMIC-IV. Клиническую проверку провели на 202 971 госпитализации с 21 целевым диагнозом; при бюджете $30 политика использовала 6,6% стоимости полного набора тестов. Её сравнивали с жадным выбором без штрафа, вариантом, который делит пользу на цену, и другими методами активного отбора.
Эти результаты не дают оснований переносить клинические показатели прямо в продукт. Данные MIMIC-IV происходят из одной больницы, а основной эксперимент допускает тесты, записанные за всю госпитализацию, поэтому в признаки может попадать информация из более позднего лечения. Дополнительная проверка с фиксированным временным окном сохраняет преимущество метода, но не заменяет внешнюю валидацию.
Практический вывод уже применим вне медицины. Если оптимум можно посчитать на уменьшенной копии задачи, команда получает проверяемый сертификат и может понять, мешает ли ей цена или жадность. Если задача слишком велика, лагранжева схема всё равно задаёт осмысленный регулятор расходов, но её следует оценивать на собственной границе «качество — стоимость», а не считать доказанно оптимальной.
Источники
Иллюстрация: рисунок из статьи «The Lagrangian Structure of Cost-Penalized Active Feature Acquisition», Joseph Bingham, CC BY 4.0
Похоже на вашу задачу?
Расскажите, что собираете. За полчаса разложим на этапы и назовём сроки — это бесплатно и ни к чему не обязывает.
