Verificação de provas ultra-rápida com IA: o que um novo resultado matemático significa para validar dados massivos

Pontos-chave

• A Apple ML Research publicou um estudo sobre uma nova classe de sistemas de prova matemática chamada provas interativas duplamente sub-lineares de proximidade.
• O método permite a um provador, a parte que faz uma alegação, ler apenas uma pequena fração de um conjunto de dados massivo para gerar uma prova.
• Um verificador, a parte que verifica a alegação, precisa de ler uma fração ainda menor para confirmar se a prova é provavelmente correta.
• A técnica aplica-se a verificação aproximada, o que significa que detecta entradas claramente erradas sem necessidade de inspecionar cada byte.
• Nenhuma técnica existente consegue enganar o verificador para aceitar uma alegação falsa, de acordo com a investigação.

Imagine que dirige um armazém com um milhão de caixas e alguém lhe diz que aproximadamente 95 por cento delas estão correctamente etiquetadas. Não tem tempo para abrir todas as caixas. E se conseguisse verificar apenas algumas centenas e mesmo assim estar confiante de que a alegação é válida? Essa é a intuição por trás desta investigação.

Cientistas na Apple ML Research publicaram um estudo sobre o que chamam provas interativas duplamente sub-lineares de proximidade, ou dsIPPs. Uma prova interativa de proximidade é um protocolo, uma troca formal entre duas partes, que permite a um lado convencer o outro de que um conjunto de dados massivo satisfaz uma determinada propriedade, sem que nenhum dos lados tenha de ler a totalidade. "Sub-linear" simplesmente significa que o trabalho cresce muito mais lentamente do que o tamanho dos dados, por isso verificar um bilião de registos pode exigir apenas ler alguns milhares.

A parte "dupla" é o novo pormenor. Tanto a parte que gera a prova como a parte que a verifica trabalham em tempo sub-linear. Anteriormente, sistemas de prova deste tipo exigiam que o provador lesse a entrada completa. Aqui, o provador lê uma pequena porção. O verificador lê uma porção ainda menor.

O que significa "aproximado" aqui? O sistema não garante perfeição. Garante que se uma entrada genuinamente pertence à propriedade a ser testada, um provador honesto consegue sempre levar o verificador a aceitar. E se uma entrada está longe dessa propriedade, nenhum provador desonesto consegue enganar o verificador a dizer que sim. Pense nisso como um detector de fumo: não vai perder um fogo real, e uma máquina de fumo não o consegue enganar.

Por que é que as pessoas comuns devem importar-se?

Provavelmente não vai interagir directamente com esta investigação durante anos, se é que alguma vez vai. Mas os problemas que ela aborda estão por baixo de tecnologias que as pessoas usam todos os dias. Os serviços de streaming verificam se bibliotecas enormes de ficheiros cumprem os padrões de qualidade. Os bancos auditam registos de transacções para detectar padrões de fraude. Os sistemas de saúde analisam milhões de registos para erros de relatório. Qualquer situação em que verificar tudo é demasiado lento ou demasiado custoso é exactamente o local onde este tipo de sistema de prova eventualmente se torna útil.

A investigação é teórica por enquanto, o que significa que estabelece a base matemática em vez de disponibilizar um produto. Ferramentas práticas construídas com base nessas ideias podem permitir que sistemas de software verifiquem alegações em larga escala muito mais rapidamente do que os métodos actuais permitem, sem sacrificar a fiabilidade.

O artigo completo está disponível para investigadores que queiram aprofundar as provas formais e os limites de complexidade.