Надзвичайно швидка перевірка доказів штучного інтелекту: що означає новий математичний результат для перевірки гігантських обсягів даних
Дослідники знайшли спосіб перевірити наближені факти про величезні набори даних, використовуючи лише невелику часточку даних, двічі. Ось чому це важливо.
Ключові моменти
- Apple ML Research опублікувала дослідження про новий клас математичних систем доказів, називаються дво-сублінійні інтерактивні докази близькості.
- Метод дозволяє доказувачу, стороні, яка робить твердження, прочитати лише невелику частину величезного набору даних для створення доказу.
- Перевіряючому, стороні, яка перевіряє твердження, потрібно прочитати ще меншу частину, щоб підтвердити, чи є доказ, ймовірно, правильним.
- Цей метод застосовується до наближеної перевірки, тобто він виявляє явно неправильні дані без необхідності перевіряти кожний байт.
- Відповідно до дослідження, жодна існуюча техніка не може змусити перевіряючого прийняти хибне твердження.
Уявіть, що ви управляєте складом з мільйона коробок, і хтось говорить вам, що приблизно 95 відсотків з них позначені правильно. У вас немає часу відкривати кожну коробку. Що якщо ви могли б вибірково перевірити лише кілька сотень і все одно бути впевненими, що твердження справедливо? Це інтуїція, яка стоїть за цим дослідженням.
Учені з Apple ML Research опублікували дослідження про те, що вони називають дво-сублінійними інтерактивними доказами близькості, або dsIPPs. Інтерактивний доказ близькості — це протокол, формальний обмін між двома сторонами, який дозволяє одній стороні переконати іншу, що величезний набір даних задовольняє якусь властивість, без того щоб будь-яка сторона повинна була прочитати все це. «Сублінійний» просто означає, що обсяг роботи зростає набагато повільніше за розмір даних, тому перевірка мільярда записів може вимагати прочитання лише кількох тисяч.
«Дво» — це нова тонкість. Як сторона, що генерує доказ, так і сторона, що його перевіряє, працюють у сублінійному часі. Раніше системи доказів такого типу вимагали, щоб доказувач прочитав усе введення. Тут доказувач читає невелику частину. Перевіряючий читає ще меншу частину.
Що означає «наближена» тут? Система не гарантує досконалість. Вона гарантує, що якщо введення справді належить до властивості, яка тестується, чесний доказувач завжди зможе змусити перевіряючого прийняти його. І якщо введення далеко від цієї властивості, ніякий нечесний доказувач не зможе змусити перевіряючого сказати «так». Думайте про це як про детектор диму: він не пропустить справжню пожежу, а машина з димом його не обманеш.
Чому звичайні люди мають піклуватися?
Ви, ймовірно, не взаємодіятимете з цим дослідженням безпосередньо роками, якщо взагалі. Але проблеми, які воно вирішує, лежать в основі технологій, які люди використовують щодня. Потокові сервіси перевіряють, чи величезні бібліотеки файлів відповідають стандартам якості. Банки аудитують записи операцій на предмет закономірностей шахрайства. Системи охорони здоров'я сканують мільйони записів на предмет помилок звітування. Будь-яка ситуація, де перевірка всього надто повільна або надто дорога, — це саме те, де цей вид системи доказів зрештою стає корисним.
Дослідження носить теоретичний характер на даний момент, тобто воно закладає математичну основу, а не поставляє продукт. Практичні інструменти, побудовані на основі цих ідей, могли б дозволити програмним системам перевіряти масштабні твердження набагато швидше, ніж дозволяють нинішні методи, без шкоди для надійності.
Повна стаття доступна для дослідників, які хочуть детальніше ознайомитися з формальними доказами та межами складності.
