Test de propriété

En informatique théorique, un test de propriété (ou property testing en anglais) est un test probabiliste qui a pour objectif de déterminer si un objet donné, par exemple un graphe ou une fonction, possède une propriété fixée ou bien s'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.

Exemple introductif[modifier | modifier le code]

Considérons l'exemple simpliste suivant^[1] : on cherche à savoir si un graphe est vide ou relativement loin de l'être. Plus précisément on cherche à savoir si le graphe donné en entrée (dont le nombre de nœud est noté n) n'a aucune arêtes ou bien a au moins $\epsilon n^{2}$ arêtes. Le type de requêtes est le suivant : on choisit k sommets et on reçoit le sous-graphe induit par ces k sommets. L'algorithme est simple : choisir au hasard uniformément k sommets, si le sous-graphe induit est vide renvoyé vide sinon renvoyer non vide. Dans le cas de la sortie non vide, l'algorithme ne se trompe pas, alors que dans le cas de vide, il est possible que le graphe soit en fait loin d'être vide. Cependant la probabilité d'erreur est petite pour n allant vers l'infini.

Définition plus 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é^[2] pour ${\mathcal {P}}$ est un algorithme qui prend en entrée un élément $x\in E$ et un paramètre de distance $\epsilon$ , effectue certains types de requêtes (queries) sur $x$ , et détermine 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).

Les testeurs de propriété sont intéressants 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'intéresse à des algorithmes probabilistes et non déterministes, afin d'obtenir des résultats non-triviaux.

Acceptation probabiliste[modifier | modifier le code]

L'algorithme a les propriétés suivantes :

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,{\mathcal {P}})<\epsilon$ .

Comme pour un algorithme de Monte-Carlo classique, si $p$ ou $p^{\prime }$ vaut 1, l'algorithme est dit à erreur unilatérale. Sinon, il est dit à erreur bilatérale^[3].

Les différents modèles[modifier | modifier le code]

Il existe plusieurs modèles de test. En particulier, on peut définir plusieurs distances et type de requêtes selon la densité des graphes en entrées : des graphes denses, des graphes creux ou des graphes généraux.

Distances[modifier | modifier le code]

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^[4].

La distance pour les graphes denses entre deux graphes est souvent le nombre d'arêtes à changer divisé par $n^{2}$ . La distance pour les graphes creux ou généraux entre deux graphes est souvent le nombre d'arêtes à changer divisé par $max(n,m)$ .

Requêtes[modifier | modifier le code]

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

Pour les graphes denses, les requêtes sont de la forme : "est-ce que (u,v) est une arête du graphe ?", alors que pour les graphes creux, elles sont du type "quel est le degré du nœud u ?" ou "quel est le i-ème voisin du nœud u ?".

Une autre différence importante entre les modèles est que certains modèles sont non-adaptatifs, c'est-à-dire que toutes les requêtes sont choisies à l'avance, alors que certains sont adaptatifs, c'est-à-dire que la réponse à une requête peut être utilisée pour les requêtes suivantes.

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

Un cadre classique est celui du test de propriété de graphe. Dans ce contexte l'entrée est par 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^[5].

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 de propriétés de graphes[modifier | modifier le code]

Deux autres problèmes importants consiste à savoir si le graphe d'entrée est sans graphe sans triangle^[6] et s'il est biparti^[7].

Exemples sur des fonctions ou des distributions[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ébriques, lorsque les objets considérés sont des structures algébriques comme des groupes ou des espaces vectoriels^[8].

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 ...)^[9].

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)^[10], à la théorie des codes et au théorème PCP^[8].

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^[11] 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^[12].

Depuis, de nombreux articles ont été publiés. Notamment, Alon et al.^[13] ont complètement caractérisé l'ensemble des propriétés de graphes testables 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-469
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]

↑ Cet exemple est issu de Terence Tao, « On the property testing of hereditary graph and hypergraph properties », sur What’s new, 31 octobre 2007.
↑ Une source pour la traduction de property testing est (Dalsass 2011)
↑ 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 .
↑ (en) Kaufman, Krielevich et Ron, « Tight bounds for testing bipartiteness in general graphs », SIAM journal on computing, vol. 33, n^o 6,‎ 2004, p. 1441-1483 (ISSN 0097-5397)
↑ (en) Noga Alon et Michael Krivelevich, « Testing k-colorability », SIAM Journal on Discrete Mathematics, vol. 15, n^o 2,‎ février 2002 (lire en ligne)
↑ Noga Alon, Tali Kaufman, Michael Krivelevich et Dana Ron, « Testing Triangle-Freeness in General Graphs », SIAM J. Discrete Math., vol. 22, n^o 2,‎ 2008, p. 786-819 (DOI 10.1137/07067917X)
↑ Oded Goldreich et Dana Ron, « A Sublinear Bipartiteness Tester for Bounded Degree Graphs », Combinatorica, vol. 19, n^o 3,‎ 1999, p. 335-373 (DOI 10.1007/s004930050060)
↑ ^{a et b} (Goldreich 2011)
↑ (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])
↑ 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)
↑ (en) Ronitt Rubinfeld et Madhu Sudan, « Robust characterization of polynomials with applications to program testing », SIAM Journal on Computing, vol. 25, n^o 2,‎ février 1996, p. 252-271
↑ (en) Goldreich et Ron, « Property testing and its connection to learning and approximation », JACM,‎ 1998
↑ (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, n^o 1,‎ 2009, p. 251-260 (lire en ligne)

Portail de l'informatique théorique

[1] Cet exemple est issu de Terence Tao, « On the property testing of hereditary graph and hypergraph properties », sur What’s new, 31 octobre 2007.

[2] Une source pour la traduction de property testing est (Dalsass 2011)

[3] 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 .

[4] (en) Kaufman, Krielevich et Ron, « Tight bounds for testing bipartiteness in general graphs », SIAM journal on computing, vol. 33, n^o 6,‎ 2004, p. 1441-1483 (ISSN 0097-5397)

[5] (en) Noga Alon et Michael Krivelevich, « Testing k-colorability », SIAM Journal on Discrete Mathematics, vol. 15, n^o 2,‎ février 2002 (lire en ligne)

[6] Noga Alon, Tali Kaufman, Michael Krivelevich et Dana Ron, « Testing Triangle-Freeness in General Graphs », SIAM J. Discrete Math., vol. 22, n^o 2,‎ 2008, p. 786-819 (DOI 10.1137/07067917X)

[7] Oded Goldreich et Dana Ron, « A Sublinear Bipartiteness Tester for Bounded Degree Graphs », Combinatorica, vol. 19, n^o 3,‎ 1999, p. 335-373 (DOI 10.1007/s004930050060)

[Goldreich_2011-8] {a et b} (Goldreich 2011)

[9] (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])

[10] 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)

[11] (en) Ronitt Rubinfeld et Madhu Sudan, « Robust characterization of polynomials with applications to program testing », SIAM Journal on Computing, vol. 25, n^o 2,‎ février 1996, p. 252-271

[12] (en) Goldreich et Ron, « Property testing and its connection to learning and approximation », JACM,‎ 1998

[13] (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, n^o 1,‎ 2009, p. 251-260 (lire en ligne)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]