Verifica ultra-rapida di prove con IA: cosa significa un nuovo risultato matematico per validare dati enormi

Punti chiave

• Apple ML Research ha pubblicato uno studio su una nuova classe di sistemi di prove matematiche chiamati interactive proofs of proximity doppiamente sub-lineari.
• Il metodo consente a un provatore, la parte che formula un'affermazione, di leggere solo una piccola frazione di un dataset massiccio per generare una prova.
• Un verificatore, la parte che controlla l'affermazione, ha bisogno di leggere una frazione ancora più piccola per confermare se la prova è probabilmente corretta.
• La tecnica si applica alla verifica approssimativa, il che significa che rileva input chiaramente sbagliati senza necessità di ispezionare ogni byte.
• Secondo la ricerca, nessuna tecnica esistente può ingannare il verificatore e fargli accettare un'affermazione falsa.

Immagina di gestire un magazzino con un milione di scatole e qualcuno ti dice che approssimativamente il 95 percento di esse è etichettato correttamente. Non hai tempo di aprire ogni scatola. E se potessi controllare casualmente solo poche centinaia e comunque essere sicuro che l'affermazione regge? Questo è il principio dietro questa ricerca.

Gli scienziati di Apple ML Research hanno pubblicato uno studio su quello che chiamano interactive proofs of proximity doppiamente sub-lineari, o dsIPP. Un interactive proof of proximity è un protocollo, uno scambio formale tra due parti, che consente a un lato di convincere l'altro che un dataset enorme soddisfa una certa proprietà, senza che nessuna delle due parti debba leggere tutto. "Sub-lineare" semplicemente significa che il lavoro cresce molto più lentamente rispetto alla dimensione dei dati, quindi verificare un miliardo di record potrebbe richiedere la lettura di solo poche migliaia.

La parte "doppiamente" è la novità. Sia la parte che genera la prova che la parte che la controlla lavorano in tempo sub-lineare. In precedenza, i sistemi di prove di questo tipo richiedevano al provatore di leggere l'intero input. Qui, il provatore legge una piccola porzione. Il verificatore legge una porzione ancora più piccola.

Cosa significa "approssimativo" in questo contesto? Il sistema non garantisce la perfezione. Garantisce che se un input appartiene genuinamente alla proprietà sottoposta a test, un provatore onesto può sempre convincere il verificatore ad accettare. E se un input è lontano da quella proprietà, nessun provatore disonesto può ingannare il verificatore facendogli dire sì. Pensala come un rilevatore di fumo: non perderà un incendio reale e una macchina del fumo non lo inganna.

Perché dovrebbe importare alle persone comuni?

Probabilmente non interagirai direttamente con questa ricerca per anni, se mai. Ma i problemi che affronta stanno alla base di tecnologie che le persone usano ogni giorno. I servizi di streaming verificano se enormi librerie di file soddisfano gli standard di qualità. Le banche controllano i record di transazioni per modelli di frode. I sistemi sanitari scansionano milioni di record per errori di segnalazione. Qualsiasi situazione in cui verificare tutto è troppo lento o troppo costoso è esattamente il luogo in cui questo tipo di sistema di prove alla fine diventa utile.

La ricerca è teorica per ora, il che significa che pone le basi matematiche piuttosto che lanciare un prodotto. Gli strumenti pratici costruiti su queste idee potrebbero consentire ai sistemi software di verificare affermazioni su larga scala molto più velocemente di quanto i metodi attuali consentono, senza compromettere l'affidabilità.

L'articolo completo è disponibile per i ricercatori che vogliono approfondire le prove formali e i limiti di complessità.