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.

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 ${\displaystyle \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.

Soit ${\displaystyle E}$ un ensemble, et ${\displaystyle d}$ une distance sur cet ensemble. Soit ${\displaystyle {\mathcal {P}}}$ un sous-ensemble de ${\displaystyle E}$, qu'on appelle propriété. Un testeur de propriété^[2] pour ${\displaystyle {\mathcal {P}}}$ est un algorithme qui prend en entrée un élément ${\displaystyle x\in E}$ et un paramètre de distance ${\displaystyle \epsilon }$, effectue certains types de requêtes (queries) sur ${\displaystyle x}$, et détermine certaines caractéristiques (par exemple, le ${\displaystyle i}$-ème bit ${\displaystyle x_{i}}$ de ${\displaystyle x}$, ou bien la valeur ${\displaystyle f(x)}$ d'une certaine fonction ${\displaystyle 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.

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

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

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

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.

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 ${\displaystyle 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 ${\displaystyle max(n,m)}$.

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.

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.

Nous choisissons comme ensemble ${\displaystyle {\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 ${\displaystyle G}$ et un paramètre de distance ${\displaystyle \epsilon }$. De plus, la distance choisie est telle que si le graphe ${\displaystyle G}$ possède ${\displaystyle n}$ sommets, il sera à une distance ${\displaystyle \epsilon }$ de ${\displaystyle {\mathcal {P}}}$ s'il faut lui enlever ${\displaystyle \epsilon n^{2}}$ arêtes pour qu'il soit dans ${\displaystyle {\mathcal {P}}}$.

L'algorithme sélectionne aléatoirement ${\displaystyle 108\ln(k)/\epsilon ^{2}}$ sommets du graphe ${\displaystyle 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.

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

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é ${\displaystyle D}$ sur un ensemble ${\displaystyle {\mathcal {X}}}$, et le but est de déterminer, ayant accès à des observations indépendantes de ${\displaystyle 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].

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

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.

• 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)

• Portail de l'informatique théorique