Témoins du logiciel mathématique

11

Comme beaucoup de gens, je suis un grand utilisateur de logiciels mathématiques tels que Mathematica et Maple. Cependant, je suis devenu de plus en plus frustré par les nombreux cas où un tel logiciel vous donne simplement la mauvaise réponse sans avertissement. Cela peut se produire lors de l'exécution de toutes sortes d'opérations, des sommes simples à l' optimisation, parmi de nombreux autres exemples.

Je me demandais ce qui pouvait être fait à propos de ce grave problème. Ce qui est nécessaire, c'est un moyen de permettre à l'utilisateur de vérifier l'exactitude d'une réponse donnée afin qu'il ait une certaine confiance dans ce qu'on lui dit. Si vous deviez obtenir une solution d'un collègue en mathématiques, il / elle pourrait simplement s'asseoir et vous montrer son travail. Cependant, cela n'est pas possible pour un ordinateur dans la plupart des cas. L'ordinateur pourrait-il plutôt vous donner un témoin simple et facilement vérifiable de l'exactitude de leur réponse? La vérification peut être effectuée par ordinateur, mais nous espérons que la vérification de l'algorithme de vérification sera beaucoup plus facile que la vérification de l'algorithme pour produire le témoin en premier lieu. Quand serait-ce possible et comment cela pourrait-il être formalisé

Donc, en résumé, ma question est la suivante.

Serait-il possible au moins en théorie pour un logiciel mathématique de fournir une courte preuve vérifiable avec la réponse que vous avez demandée?

Un cas trivial où nous pouvons le faire immédiatement est bien sûr la factorisation des entiers ou de nombreux problèmes classiques NP-complets (par exemple le circuit hamiltonien, etc.).

cc.complexity-theory Communauté
la source
Pouvez-vous donner un exemple où la réponse produite est fausse? Il est bien sûr possible de générer une preuve vérifiable de l'exactitude des calculs, mais une telle preuve n'a pas besoin d'être facile à vérifier à la main, tout simplement parce que le logiciel utilise généralement des algorithmes hautement non triviaux qui sont plus efficaces que les plus intuitifs.
Mahdi Cheraghchi
J'ai donné deux exemples dans la question, mais les couleurs des liens peuvent ne pas être faciles à voir. Cliquez sur "sommes" ou "optimisation".
1
Une sorte de ce que Manuel Blum et Sampath Kannan ont fait dans dl.acm.org/citation.cfm?id=200880 ?
Andrej Bauer
Vous voudrez peut-être jeter un œil aux algorithmes de certification .
Pratik Deoghare du
oui, trop de systèmes logiciels symboliques sont traités comme des "boîtes noires" et c'est aussi une stratégie d'entreprise pour protéger les secrets commerciaux. (1) essayer des alternatives open source (2) considérer la «meilleure pratique» en génie logiciel des «tests unitaires». brièvement, l'idée serait de créer des «tests de santé mentale» des résultats, par exemple en substituant des valeurs connues, d'autres manipulations, des inverses, etc. à des tests bien construits, il est peu probable que la formule et le test échouent d'une manière qui donnerait un "faux positif".
vzn

Réponses:

5

  1. Le concept de «témoins» ou de «preuves vérifiables» n'est pas totalement nouveau: comme mentionné dans les commentaires, recherchez le concept de «certificat». Trois exemples me sont venus à l'esprit, il y en a plus (dans les commentaires et ailleurs):

    • Kurt Mehlhorn a décrit en 1999 un problème similaire dans les algorithmes de géométrie computationnelle (par exemple, des erreurs mineures dans les coordonnées peuvent générer de grosses erreurs dans les résultats de certains algorithmes), résolus de manière similaire dans la bibliothèque Leda , en insistant pour que chaque algorithme produise un "certificat" de sa réponse en plus de la réponse elle-même.

    • Demaine, Lopez-Ortiz et Munro en 2000 ont utilisé les concepts de certificats (ils les appellent "preuves") pour montrer des limites inférieures adaptatives sur le calcul de l'union et de l'intersection (et de la différence, mais celle-ci est triviale) d'ensembles triés. N'excluez pas leur travail car ils n'ont pas utilisé de certificats pour se protéger contre les erreurs de calcul: ils ont montré que même si le certificat peut être linéaire dans la taille de l'instance dans le pire des cas, il est souvent plus court et peut donc être "vérifié" "en temps sublinéaire (accès aléatoire à l'entrée sous forme de tableau trié ou d'arborescence B), et en particulier en moins de temps que nécessaire pour calculer un tel certificat.

    • J'utilise le concept de certificats sur divers autres problèmes depuis que j'ai vu Ian Munro présenter leur implémentation à Alenex 2001 , et en particulier pour les permutations (excuses pour la fiche sans vergogne, une autre arrive), où le certificat est plus court dans le meilleur des cas que dans le pire ou le cas moyen, ce qui donne une structure de données compressée pour les permutations. Là encore, la vérification du certificat (ie la commande) prend au maximum un temps linéaire, moins que le calcul (ie le tri).

  2. Le concept n'est pas toujours utile pour la vérification des erreurs: il y a des problèmes où la vérification du certificat prend autant de temps que sa production (ou simplement la production du résultat). Deux exemples me viennent à l'esprit, un trivial et un compliqué, Blum et Kannan (mentionnés dans les commentaires) en donnent d'autres.

    • nn
    • Le certificat pour la coque convexe en deux et trois dimensions, si les points sont donnés dans un ordre aléatoire, prend autant de bits à encoder que de comparaisons à calculer [FOCS 2009] (autre plug sans vergogne).

La bibliothèque Leda est l'effort le plus général (à ma connaissance) visant à faire des algorithmes déterministes producteurs de certificats la norme dans la pratique. L'article de Blum et Kannan est le meilleur effort que j'ai vu pour en faire la norme en théorie, mais ils montrent les limites de cette approche.

J'espère que ça aide...

Jeremy
la source
Merci c'est très intéressant. En ce qui concerne votre point 2. Je pense que je parle de quelque chose d'un peu différent. Le problème n'est pas les bogues dans le code mais plutôt les algorithmes que nous connaissons peuvent donner la mauvaise réponse. De plus, à un niveau banal, je ne sais même pas à quoi ressemblerait un certificat utile pour de nombreuses fonctions mathématiques. Par exemple pour une somme infinie ou, disons, la minimisation d'une fonction.
Pour être un peu plus clair. Il semble qu'il soit très difficile de concevoir des algorithmes corrects pour de nombreux problèmes mathématiques. Cependant, nous vivons avec des algorithmes qui peuvent faire des erreurs sans nous avertir (et en fait, ils sont prouvés incorrects) pour des raisons pratiques. L'espoir qu'il n'est pas (comme) difficile de concevoir des correcteurs de correction prouvablement corrects pour le même ensemble de problèmes.
Je m'éloigne de mon expertise, mais je pensais que les erreurs de calcul étaient généralement causées par des erreurs d'arrondi avec des résultats intermédiaires (c'était clairement le cas dans les exemples motivant Leda) sur les opérations de base (multiplications, divisions, etc.) plutôt que par des erreurs dans les algorithmes. J'aurais pensé que les systèmes algébriques tels que l'érable et le matlab les évitaient :(
Jeremy
C'est une question intéressante et peut-être que quelqu'un ici sait à coup sûr. Cependant, bon nombre des réponses incorrectes dont je parle ne sont pas des calculs numériques, ce qui implique au moins à première vue que les problèmes sont plus que ce que vous décrivez. Je ne connais pas la complexité des limites de calcul / des sommes infinies, etc. mais je suppose qu'en général elles sont insolubles dans le pire des cas et donc des heuristiques qui donnent parfois la mauvaise réponse sont nécessaires / utiles. mathematic.stackexchange.com/questions/tagged/bugs n'est pas informatif pour avoir une idée des choses qui tournent mal.
CS théorique a le concept d'auto-test, qui s'applique à de nombreux problèmes d'algèbre linéaire. L'une des idées de base est que pour de nombreux problèmes, la solution peut être vérifiée (peut-être avec un peu d'informations supplémentaires) plus facilement qu'elle ne peut être calculée. Voir par exemple https://doi.org/10.1016/0022-0000(93)90044-W .
Neal Young