Test de propriété

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Testeur de propriété)
Aller à : navigation, rechercher

En informatique théorique, un test de propriété (property testing en anglais) est un test probabiliste qui a pour objectif de déterminer si un objet donné (un graphe ou une fonction par exemple) possède une propriété fixée ou bien si il est "loin" de l'avoir. Ces algorithmes ont l'avantage d'être très rapides.

Les testeurs de propriété sont notamment utiles pour tester que des grands graphes ont certaines propriétés et les preuves PCP.

Définition formelle[modifier | modifier le code]

Soit E un ensemble, et d une distance sur cet ensemble. Soit \mathcal{P} un sous-ensemble de E, qu'on appelle propriété. Un testeur de propriété[1] pour \mathcal{P} est un algorithme qui, prenant entrée un élément x\in E et un paramètre de distance \epsilon, et a la possibilité d'effectuer certains types de requêtes (queries) sur x afin d'en déterminer certaines caractéristiques (par exemple, le i-ème bit x_i de x, ou bien la valeur f(x) d'une certaine fonction f fixée a priori).

L'algorithme :

  • accepte x avec une probabilité p\geq 2/3 si x\in\mathcal{P};
  • rejette x avec une probabilité p^\prime\geq 2/3 si d(x,\mathcal{P})\geq \epsilon;
  • peut renvoyer n'importe quel résultat avec une probabilité quelconque si 0<d(x,F)<\epsilon.

Si p ou p^\prime vaut 1, l'algorithme est dit à erreur unilatérale. Sinon, il est dit à erreur bilatérale (bien qu'il n'y ait pas de termes officiels français. En anglais, on parle d'algorithme with a "one-sided" or "two-sided" error .)

Précisions et propriétés[modifier | modifier le code]

Les testeurs de propriété sont interessants lorsqu'ils satisfont des contraintes fortes, par exemple un nombre de requêtes constant (dans le cadre de la complexité en requêtes), ou un temps de calcul sous-linéaire. Dans cette optique on s'interesse à des algoritmes probabilistes et non déterministes, pour avoir des résultats non-triviaux.

Selon les versions, l'algorithme choisit les requêtes ou bien elles sont tirées selon une certaine distribution.

La distance choisie sur l'ensemble E est particulièrement importante. Les résultats obtenus avec une distance donnée ne sont pas valables si on la change. Par exemple, dans le cas des graphes, on peut obtenir des résultats complètement différents selon que l'on se limite aux graphes denses, aux graphes peu denses, ou que l'on étudie les graphes en général[2].

Exemples des propriétés de graphes[modifier | modifier le code]

Un cadre classique est celui du test de propriété de graphe. Dans ce contexte l'entrée est pas exemple la matrice d'adjacence ou la liste d'adjacence du graphe.

Graphe 3-coloriable[modifier | modifier le code]

Nous choisissons comme ensemble \mathcal{P} l'ensemble des graphes colorables avec 3 couleurs. Le problème de la 3-coloration est connu NP-complet, donc aucun algorithme à complexité polynomiale n'est connu à ce jour pour le résoudre. Cependant, Alon et Krielevich ont proposé un testeur de propriété fonctionnant en temps constant pour le résoudre[3].

L'algorithme en lui-même est un exemple très générique de testeur de propriété. Il reçoit en entrée un graphe G et un paramètre de distance \epsilon. De plus, la distance choisie est telle que si le graphe G possède n sommets, il sera à une distance \epsilon de \mathcal{P} s'il faut lui enlever \epsilon n^2 arêtes pour qu'il soit dans \mathcal{P}.

L'algorithme sélectionne aléatoirement 108\ln(k)/\epsilon^2 sommets du graphe G, et reconstitue le sous-graphe induit par ces sommets. Il vérifie alors de manière exacte si ce sous-graphe est 3-colorable, et il retourne pour le graphe global la même réponse que pour le sous-graphe.

Alon et Krielevich ont montré qu'avec une probabilité de 2/3, cette réponse était juste.

Autres exemples[modifier | modifier le code]

Le test de propriété peut aussi être utilisé pour estimer les propriétés de fonctions (monotonie, linéarité...), ou d'ensembles divers  : est-ce qu'un ensemble de points est recouvrable par un nombre donné de boules, en quelle langue est écrit un texte... On parle en particulier de tests de propriétés algébrique, lorsque les objets considérés sont des structures algébriques comme des groupes ou des espaces vectoriels[4].

Une variante a également émergé, dans laquelle l'objet étudié est une distribution de probabilité D sur un ensemble \mathcal{X}, et le but est de déterminer, ayant accès à des observations indépendantes de D, si cette dernière satisfait une certaine propriété (telle qu'être uniforme, avoir une faible entropie, ou bien avoir une densité de probabilité décroissante ...)[5].

Applications[modifier | modifier le code]

Les applications sont par exemple les graphes de très grandes tailles comme le graphe du web (en). Le test de propriété est aussi relié à l'apprentissage automatique (notamment l'apprentissage PAC)[6], à la théorie des codes et au théorème PCP[7].

Historique[modifier | modifier le code]

Le concept de test de propriété a été défini dans les années 90. Bien qu'il soit relié à d'autres formes d'approximation, notamment les PCPs, on considère que le test de propriété pour des fonctions a été formulé explicitement pour la première fois par Rubinfeld et Sudan[8] dans le cadre du test de fonctions. Dans le cadre du test de propriété pour des graphes, le premier article à explicitement définir ces notions a été publié par Goldreich et Ron[9].

Depuis, de nombreux articles ont été publiés. Notamment, Alon et al.[10] ont complètement caractérisé l'ensemble des propriétés de graphes testables efficacement (i.e en temps constant).

Bibliographie[modifier | modifier le code]

  • Oded Goldreich, « A brief introduction to property testing », dans Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, Springer,‎ 2011 (lire en ligne), p. 465-469Document utilisé pour la rédaction de l’article
  • Nicolas Dalsass, Test de propriété pour l'homomorphisme de graphes et d'hypergraphes,‎ 2011 (lire en ligne)

Notes et références[modifier | modifier le code]

  1. Une source pour la traduction de property testing est (Dalsass 2011)
  2. (en) Kaufman, Krielevich et Ron, « Tight bounds for testing bipartiteness in general graphs », SIAM journal on computing, vol. 33, no 6,‎ 2004, p. 1441-1483 (ISSN 0097-5397)
  3. (en) Noga Alon et Michael Krivelevich, « Testing k-colorability », SIAM Journal on Discrete Mathematics, vol. 15, no 2,‎ février 2002 (lire en ligne)
  4. (Goldreich 2011)
  5. (fr) Ronitt Rubinfeld, « Dompter les Distributions de Probabilité Géantes » (Traduction par C. Canonne de « Taming Big Probability Distributions » de Ronitt Rubinfeld, XRDS: Crossroads - Volume 19 Issue 1, Automne 2012, Pages 24-28 [texte intégral])
  6. Voir Oded Goldreich, Shafi Goldwasser et Dana Ron, « Property Testing and its Connection to Learning and Approximation », Journal of the ACM, vol. 45,‎ 1998, p. 339-348 (lire en ligne)
  7. (Goldreich 2011)
  8. (en) Ronitt Rubinfeld et Madhu Sudan, « Robust characterization of polynomials with applications to program testing », SIAM Journal on Computing, vol. 25, no 2,‎ février 1996, p. 252-271
  9. (en) Goldreich et Ron, « Property testing and its connection to learning and approximation », JACM,‎ 1998
  10. (en) Noga Alon, Fischer, Newman et Shapira, « A combinatorial characterization of the testable graph properties: it's all about regularity », SIAM Journal on Computing, vol. 39, no 1,‎ 2009, p. 251-260 (lire en ligne)