Le nombre d'empaquetage P(ε,S,ρ) est la cardinalité maximale d'un sous-ensemble de S dont les éléments sont mutuellement à distance strictement supérieure à 2ε (équivalemment, le nombre maximal de boules fermées de rayon ε disjointes qu'on peut placer dans S) ; il mesure combien de points bien séparés S peut contenir à l'échelle ε.

Principe

Quantifier la capacité par la séparation maximale : compter le plus grand ensemble de points de S mutuellement ε-séparés de sorte que les boules ε correspondantes ne se chevauchent pas, capturant la diversité interne à cette échelle.

Démonstration

Dans la boule unité de R^d, on peut placer d'ordre (1/ε)^d boules disjointes de rayon ε ; par exemple, un empilement en réseau fournit une borne inférieure sur P(ε) illustrant la dépendance à la dimension et au rayon.

Mauvaise application

Supposer que les nombres d'empaquetage et de recouvrement sont identiques ; ou utiliser les décomptes d'empaquetage pour déduire le recouvrement sans tenir compte de la relation facteur-de-deux sur le rayon et de la géométrie propre à la métrique.

Conséquence

Un grand nombre d'empaquetage pour petit ε indique une capacité et une séparabilité élevées, ce qui se traduit par des minorations de la complexité d'échantillonnage et implique de nombreuses hypothèses distinguables à cette échelle.

Inversion

Considérer le nombre de recouvrement comme la notion complémentaire : alors que l'empaquetage mesure combien de boules disjointes tiennent dans S, le recouvrement mesure combien de boules sont nécessaires pour recouvrir S ; des inégalités relient les deux (par ex. packing(2ε) ≤ covering(ε) ≤ packing(ε)).

Limite

Dépend de la métrique, de la forme des boules et de l'espace ambiant ; l'empaquetage suppose la disjonction des boules, donc il est indéfini ou trivial si S est trop petit par rapport à ε, et il ne prend pas en compte le quasi-chevauchement ou les tolérances probabilistes de chevauchement.

Tension sémantique

Conflit avec le nombre de recouvrement et avec des notions continues de capacité (entropie, dimension) ; des ensembles peuvent présenter des nombres d'empaquetage similaires mais se comporter différemment en termes de recouvrement ou d'aptitude à l'approximation par des modèles structurés.

Synthèse

Le nombre d'empaquetage capture le nombre maximal de points ε-séparés dans un ensemble : c'est un décompte dépendant de l'échelle de la séparabilité interne qui complète les mesures de compacité basées sur le recouvrement.