Когда проверка AI-моделей сложнее, чем кажется: почему свойства функций не равны свойствам распределений
Исследователи Apple показали, что тестирование и верификация свойств функций работают принципиально по-разному. Хотя для тестирования location-invariant свойств функций и соответствующих распределений сложность схожа, при верификации через интерактивные доказательства близости (IPPs) эта связь разрушается. Работа важна для понимания пределов эффективной проверки моделей машинного обучения.
Это фундаментальное исследование показывает, где проходит граница возможностей эффективной верификации AI-систем. Понимание этих пределов критично для разработки надёжных методов аудита моделей машинного обучения — особенно когда полный пересчёт слишком дорог, а доверять заявлениям вендоров нельзя.
Когда интуиция подводит: тестирование ≠ верификация
Команда Apple Machine Learning Research опубликовала работу, которая переворачивает устоявшиеся представления о проверке свойств функций. Речь о location-invariant свойствах — характеристиках функций, которые зависят только от частот появления значений, а не от их расположения.
Ранее считалось: если сложность тестирования таких свойств функций близка к сложности тестирования соответствующих распределений, то эта симметрия сохранится и при верификации. Новое исследование показывает: это не так.
Что нашли исследователи
Авторы построили doubly-sublinear IPPs (интерактивные доказательства близости с двойной сублинейностью) для нескольких естественных location-invariant свойств:
-
Равномерное распределение значений: для функций из [m] в [n], где каждое значение встречается ровно m/n раз, сложность верификатора — O(n^{0.5−α}), а честного прувера — e^{O(n^{0.5+α}/ε²)}.
-
K-частотное распределение: для функций, где каждое значение встречается либо m/k раз, либо совсем не встречается, сложность верификатора — poly(1/ε)·k^{(2/3)−2α}.
Критический момент: для соответствующих свойств распределений doubly-efficient IPP не существует (доказано Herman и Rothblum, 2025). Более того, для проверки равномерности распределения над [n] верификатору нужно минимум n^{1/2} сэмплов — никакие интерактивные протоколы не помогут.
Почему это важно
Разрыв между тестированием и верификацией означает: нельзя автоматически переносить результаты о сложности проверки из одной области в другую. Для ML-систем это критично — эффективно протестировать модель может быть намного проще, чем верифицировать заявления о её свойствах через интерактивный протокол.
Работа продолжает линию исследований о том, как эффективно проверять корректность статистического анализа без полного его повторения — всё более актуальная задача в эпоху масштабных AI-вычислений.
Ключевые выводы
- Сложность тестирования и верификации location-invariant свойств функций принципиально различается, хотя для тестирования связь с распределениями была известна
- Построены doubly-sublinear IPPs для равномерных и k-частотных функций, где сложность верификатора и прувера сублинейна относительно наивных подходов
- Для соответствующих свойств распределений (например, равномерности) doubly-efficient IPP не существует, что доказывает фундамальный разрыв
- Результаты показывают пределы эффективной верификации статистических утверждений через интерактивные доказательства
- Работа критична для понимания границ проверяемости ML-моделей без полного повторения вычислений
Автор: Сергей Ефимов · Источник: machinelearning.apple.com
Это одна из тех работ, что выглядят как сухая математика, но на деле решают очень прикладной вопрос: можно ли верить AI-системе на слово, если она говорит «я проверила данные и вот свойства»? Apple показали, что для определённого класса свойств (location-invariant) ответ неожиданный: проверить функцию можно эффективно, а вот проверить распределение — нет, даже с интерактивными доказательствами.
Практический смысл простой: когда вы аудируете чужую ML-модель, нельзя рассчитывать на «быструю верификацию» заявлений о статистических свойствах. Либо пересчитывайте сами, либо принимайте риски. Особенно актуально для регуляторов и компаний, проверяющих AI-поставщиков — красивая история «мы дадим вам доказательство без раскрытия данных» работает не всегда. Математика расставила границы доверия.
Комментарии