Voir la source de Test de propriété

En [[informatique théorique]], un '''test de propriété''' (ou '''''property testing''''' en anglais) est un [[algorithme probabiliste|test probabiliste]] qui a pour objectif de déterminer si un objet donné, par exemple un [[Théorie des graphes|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 ==
Considérons l'exemple simpliste suivant<ref>Cet exemple est issu de {{lien web|url=https://terrytao.wordpress.com/2007/10/31/on-the-property-testing-of-hereditary-graph-and-hypergraph-properties/|titre=On the property testing of hereditary graph and hypergraph properties|auteur=[[Terence Tao]]|date=31 octobre 2007|site=What’s new}}.</ref> : 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 <math>\epsilon n^2</math> 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 ==
Soit <math>E</math> un ensemble, et <math>d</math> une distance sur cet ensemble. Soit <math>\mathcal{P}</math> un sous-ensemble de <math>E</math>, qu'on appelle ''propriété''. Un testeur de propriété<ref>Une source pour la traduction de ''{{langue|en|property testing}}'' est {{harv|Dalsass|2011}}</ref> pour <math>\mathcal{P}</math> est un algorithme qui prend en entrée un élément <math>x\in E</math> et un paramètre de distance <math>\epsilon</math>, effectue certains types de requêtes (''{{langue|en|queries}}'') sur  <math>x</math>, et détermine certaines caractéristiques (par exemple, le <math>i</math>-ème bit <math>x_i</math> de <math>x</math>, ou bien la valeur <math>f(x)</math> d'une certaine fonction <math>f</math> 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 ===
L'algorithme a les propriétés suivantes :
* accepte <math>x</math> avec une probabilité <math>p\geq 2/3</math> si <math>x\in\mathcal{P}</math>;
* rejette <math>x</math> avec une probabilité <math>p^\prime\geq 2/3</math> si <math>d(x,\mathcal{P})\geq \epsilon</math>;
* peut renvoyer n'importe quel résultat avec une probabilité quelconque si <math>0<d(x,\mathcal{P})<\epsilon</math>.

Comme pour un [[algorithme de Monte-Carlo]] classique, si <math>p</math> ou <math>p^\prime</math> vaut 1, l'algorithme est dit à erreur unilatérale. Sinon, il est dit à erreur bilatérale<ref>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 ''.</ref>.

=== Les différents modèles ===
Il existe plusieurs modèles de test. En particulier, on peut définir plusieurs distances et type de requêtes selon la [[densité d'un graphe|densité des graphes]] en entrées : des graphes denses, des graphes creux ou des graphes généraux.

=== Distances ===
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<ref>{{article|langue=en|nom1=Kaufman|nom2=Krielevich|nom3=Ron|titre=Tight bounds for testing bipartiteness in general graphs|périodique=SIAM journal on computing|volume=33|numéro=6|pages=1441-1483|issn=0097-5397|année=2004}}</ref>. 

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

=== Requêtes ===
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 ==
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 ===

Nous choisissons comme ensemble <math>\mathcal{P}</math> l'ensemble des graphes colorables avec 3 couleurs. Le problème de la 3-coloration est connu [[Problème NP-complet|NP-complet]], donc aucun algorithme à [[P (complexité)|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<ref>{{article|langue=en|prénom1=Noga|nom1=Alon|prénom2=Michael|nom2=Krivelevich|titre=Testing k-colorability|périodique=SIAM Journal on Discrete Mathematics|volume=15|numéro=2|mois=Février|année=2002|url texte=http://www.tau.ac.il/~nogaa/PDFS/test7.pdf|consulté le=21 janvier 2011}}</ref>.

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

L'algorithme sélectionne aléatoirement <math>108\ln(k)/\epsilon^2</math> sommets du graphe <math>G</math>, 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 ===
Deux autres problèmes importants consiste à savoir si le graphe d'entrée est sans [[graphe sans triangle]]<ref>
{{article
 | auteur1    = [[Noga Alon]] | auteur2    =  Tali Kaufman | auteur3    =   Michael Krivelevich | auteur4 = Dana Ron
 | titre     = Testing Triangle-Freeness in General Graphs
 | périodique   = SIAM J. Discrete Math.
 | volume    = 22 | numéro    = 2 | passage     = 786-819
 |année    = 2008
 | doi       = 10.1137/07067917X
}}
</ref> et s'il est [[graphe biparti|biparti]]<ref>
{{article
 | auteur1    = [[Oded Goldreich]] 
 | auteur2 = Dana Ron
 | titre     = A Sublinear Bipartiteness Tester for Bounded Degree Graphs
 | périodique   = Combinatorica
 | volume    = 19 | numéro    = 3
 | passage     = 335-373
 | année      = 1999
 | doi       = 10.1007/s004930050060
}}</ref>.

=== Exemples sur des fonctions ou des distributions ===
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 [[Structure algébrique|structures algébriques]] comme des [[groupe (mathématiques)|groupes]] ou des [[espace vectoriel|espaces vectoriels]]<ref name="Goldreich 2011">{{harv|Goldreich|2011}}</ref>.

Une variante a également émergé, dans laquelle l'objet étudié est une [[Loi de probabilité|distribution de probabilité]] <math>D</math> sur un ensemble <math>\mathcal{X}</math>, et le but est de déterminer, ayant accès à des observations indépendantes de <math>D</math>, 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 ...)<ref>'''(fr)''' Ronitt Rubinfeld, « [http://www.cs.columbia.edu/~ccanonne/files/misc/tamingbigdistr-fr.pdf 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 [http://dl.acm.org/citation.cfm?id=2331042.2331052 &#91;texte intégral&#93;])</ref>.

== Applications ==

Les applications sont par exemple les graphes de très grandes tailles comme le {{lien|fr=graphe du web|trad=Webgraph|lang=en}}. Le test de propriété est aussi relié à l'[[apprentissage automatique]] (notamment l'[[apprentissage PAC]])<ref>Voir
{{article
 | nom1 = Goldreich |prénom1 = Oded |lien auteur1 = Oded Goldreich
 | nom2 = Goldwasser | prénom2 = Shafi | lien auteur2 = Shafi Goldwasser
 | nom3 =  Ron | prénom3 = Dana
 | titre = Property Testing and its Connection to Learning and Approximation
 | périodique = Journal of the ACM |lien périodique = Journal of the ACM
 | année = 1998
 | volume = 45
 | passage = 339-348
 | lire en ligne = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.9214&rep=rep1&type=pdf
}}
</ref>, à la [[théorie des codes]] et au [[théorème PCP]]<ref name="Goldreich 2011"/>.

== Historique ==
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<ref>{{article|langue=en|prénom1=Ronitt|nom1=Rubinfeld|prénom2 = Madhu|nom2 = Sudan |lien auteur2 = Madhu Sudan |titre=Robust characterization of polynomials with applications to program testing |périodique=SIAM Journal on Computing|volume=25|numéro=2|mois=Février|année=1996|pages=252-271}}</ref> 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<ref>{{article|langue=en|nom1=Goldreich|nom2=Ron|titre=Property testing and its connection to learning and approximation|périodique=JACM|année=1998}}</ref>.

Depuis, de nombreux articles ont été publiés. Notamment, [[Noga Alon|Alon]] {{et al.}}<ref>{{article|langue=en|nom1=Alon| prénom1 = Noga | lien auteur1 = Noga Alon|nom2=Fischer|nom3=Newman|nom4=Shapira|titre=A combinatorial characterization of the testable graph properties: it's all about regularity|périodique=SIAM Journal on Computing|volume=39|numéro=1|année=2009|pages=251-260|url texte=http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=5DE8C56273C3C59CA6762871EB5D81D0?doi=10.1.1.110.5474&rep=rep1&type=pdf|consulté le=24 janvier 2011}}</ref> ont complètement caractérisé l'ensemble des propriétés de graphes testables en temps constant.

== Bibliographie ==
* {{chapitre 
 | titre chapitre = A brief introduction to property testing
 | nom = Goldreich | prénom = Oded | lien auteur = Oded Goldreich
 | titre ouvrage = Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation
 | passage=465-469
 | année=2011
 |éditeur = Springer
 | lire en ligne = http://www.wisdom.weizmann.ac.il/~oded/COL/pt-intro.pdf
}}{{plume}}
* {{ouvrage
 | nom = Dalsass | prénom = Nicolas
 | titre = Test de propriété pour l'homomorphisme de graphes et d'hypergraphes
 | année = 2011
 | lire en ligne = http://hal-lirmm.ccsd.cnrs.fr/docs/00/61/85/88/PDF/Testing_hypergraphs_homomorphisms_2_.pdf
}}

== Notes et références ==
<references/>

{{Portail|informatique théorique}}

[[Catégorie:Informatique théorique]]