Сверхбыстрая проверка математических доказательств: что новый результат означает для верификации огромных объёмов данных
Исследователи нашли способ проверить приблизительные утверждения об огромных наборах данных, используя лишь крошечную часть данных, причём дважды. Вот почему это важно.
Ключевые моменты
- Apple ML Research опубликовала исследование о новом классе математических систем доказательств под названием двойные субполиномиальные интерактивные доказательства близости.
- Метод позволяет доказывающей стороне прочитать только небольую часть массивного набора данных для создания доказательства.
- Проверяющей стороне нужно прочитать ещё меньшую часть, чтобы убедиться в вероятной корректности доказательства.
- Техника применяется к приблизительной верификации, то есть она выявляет явно ошибочные входные данные без необходимости проверки каждого байта.
- Согласно исследованию, никакая существующая техника не может обмануть проверяющую сторону и заставить её принять ложное утверждение.
Представьте, что вы управляете складом с миллионом коробок, и кто-то утверждает, что примерно 95 процентов из них помечены правильно. У вас нет времени открывать каждую коробку. Что если вы сможете выборочно проверить лишь несколько сотен и при этом быть уверенными в справедливости утверждения? В этом суть данного исследования.
Учёные из Apple ML Research опубликовали исследование о том, что они называют двойными субполиномиальными интерактивными доказательствами близости, или dsIPP. Интерактивное доказательство близости — это протокол, формальный обмен информацией между двумя сторонами, который позволяет одной стороне убедить другую в том, что огромный набор данных обладает некоторым свойством, без необходимости для любой из сторон прочитать весь набор. «Субполиномиальный» просто означает, что объём работы растёт намного медленнее, чем размер данных, так что проверка миллиарда записей может потребовать чтения всего нескольких тысяч.
«Двойной» — это новое усовершенствование. Обе стороны — как создающая доказательство, так и проверяющая его — работают в субполиномиальное время. Ранее системы доказательств такого типа требовали от доказывающей стороны прочитать весь вход. Здесь доказывающая сторона читает небольшую часть. Проверяющая сторона читает ещё меньшую часть.
Что здесь означает «приблизительный»? Система не гарантирует совершенство. Она гарантирует, что если вход действительно обладает тестируемым свойством, честная доказывающая сторона всегда сможет убедить проверяющую сторону принять утверждение. И если вход далеко отстоит от этого свойства, никакая нечестная доказывающая сторона не сможет обмануть проверяющую сторону и заставить её согласиться. Думайте об этом как о дымовом датчике: он не пропустит настоящий пожар, и дымовая машина не сможет его обмануть.
Почему это должно волновать обычных людей?
Вы, вероятно, не будете взаимодействовать с этим исследованием напрямую в течение многих лет, если вообще будете. Но проблемы, которые оно решает, лежат в основе технологий, которыми люди пользуются каждый день. Потоковые сервисы проверяют, соответствуют ли огромные библиотеки файлов стандартам качества. Банки проверяют записи транзакций на предмет шаблонов мошенничества. Системы здравоохранения сканируют миллионы записей на предмет ошибок отчётности. Любая ситуация, где проверка всего происходит слишком медленно или стоит слишком дорого, — это ровно то, где система доказательств такого типа в конечном итоге становится полезной.
Пока что исследование носит теоретический характер, то есть оно закладывает математическую основу, а не поставляет готовый продукт. Практические инструменты, построенные на основе этих идей, могли бы позволить программным системам проверять крупномасштабные утверждения намного быстрее, чем позволяют текущие методы, без ущерба для надёжности.
Полный документ доступен для исследователей, которые хотят глубже разобраться в формальных доказательствах и границах сложности.
