Généraliser le «tour médian» aux dimensions supérieures?

Pour les algorithmes randomisés prenant des valeurs réelles, le "tour médian" est un moyen simple de réduire la probabilité d'échec à n'importe quel seuil , au prix d'un multiplicatif seulement frais généraux. A savoir, si la sortie de tombe dans une "bonne plage" avec probabilité (au moins) , puis exécuter des copies indépendantes A 1 , … , A t et prendre la médiane de leurs sorties a 1 , … , a t se traduira par une valeur tombant dans I δ > 0 t = O ( log $\mathcal{A}$$\delta > 0$AI=[a,b]2/$t=O(\log\frac{1}{\delta})$$\mathcal{A}$$I=[a,b]$$2/3$$\mathcal{A}_1,\dots,\mathcal{A}_t$$a_1,\dots,a_t$$I$avec une probabilité d'au moins $1-\delta$ par les bornes de Chernoff / Hoeffding.

Y a-t-il une généralisation de ce "truc" à des dimensions plus élevées, disons $\mathbb{R}^d$ , où la bonne plage est maintenant un ensemble convexe (ou une balle, ou tout ensemble suffisamment agréable et structuré)? Autrement dit, étant donné un algorithme aléatoire $\mathcal{A}$ délivrer en sortie les valeurs de $\mathbb{R}^d$ , et un "bon jeu" $S\subseteq \mathbb{R}^d$ de telle sorte que $\mathbb{P}_r\{ \mathcal{A}(x,r) \in S \} \geq 2/3$ pour tout $x$ , comment une impulsion la probabilité de réussite à $1-\delta$avec seulement un coût logarithmique en $1/\delta$ ?

(Formulé différemment: étant donné fixe, arbitraire $a_1,\dots, a_t\in \mathbb{R}^d$ avec la garantie qu'au moins des appartiennent à , existe-t-il une procédure produisant une valeur à partir de ? Si oui, existe-t-il un système efficace?) aiS$\frac{2t}{3}$$a_i$$S$$S$

Et quel est l'ensemble minimum d'hypothèses dont on a besoin sur pour que ce qui précède soit réalisable?$S$

Désolé si cela s'avère insignifiant - je n'ai pas pu trouver de référence sur cette question ...

Ce que vous recherchez est à peu près la même une tendance centrale robuste : un moyen de réduire un nuage de points de données à un seul point, de sorte que si beaucoup de points de données sont proches d'une certaine "vérité de fond" mais le reste d'entre eux sont arbitrairement éloignés, alors votre sortie sera également proche de la vérité du terrain. Le «point de rupture» d'une telle méthode est la fraction de valeurs aberrantes arbitrairement mauvaises qu'elle peut tolérer. La différence est que dans votre cas, vous voulez remplacer "près de" par "dans la coque convexe de".

Une façon de saisir cela est avec la notion de profondeur de Tukey. Un point a une profondeur de Tukey (par rapport à un ensemble donné de n points de données) si chaque demi-espace contenant le point donné contient également au moins p n points de données. S'il y a un bon sous-espace convexe dans lequel vous voulez être, alors un point avec la profondeur de Tukey p sera à l'intérieur tant qu'il y aura au moins ( 1 - p ) n des points de données à l'intérieur. Le point de rupture de cette méthode est donc la plus grande valeur de p que vous puissiez atteindre.$p$$n$$pn$$p$$(1-p)n$$p$

Malheureusement, ce point de panne est de , pas proche de 1/2, à la fois pour la profondeur de Tukey et pour votre problème. Voici pourquoi: si vos données sont regroupées près des d + 1 sommets d'un simplexe, tant que moins de 1 / ( d + 1 ) fraction d'entre elles sont aberrantes (mais vous ne savez pas lesquelles), alors n'importe quel point dans le simplex est sûr à prendre car il sera toujours dans la coque convexe des non-aberrants. Mais si plus de 1 / ( d + 1 $1/(d+1)$$d+1$$1/(d+1)$$1/(d+1)$ des points peuvent être des valeurs aberrantes, il n'y a nulle part où il est sûr de choisir: quel que soit le point du simplexe que vous choisissez, les valeurs aberrantes pourraient être tous les points du sommet du simplexe le plus proche, et vous seriez en dehors de la coque du non valeurs aberrantes.

Si vous êtes prêt à tolérer un point de dégradation pire, plus comme , il existe une méthode aléatoire pour trouver un point profond qui est polynomial à la fois en n et en d : voir mon article$O(1/d^2)$$n$$d$

Approximation des points centraux avec des points de radon itérés, K. Clarkson, D. Eppstein, GL Miller, C. Sturtivant et S.-H. Teng, 9e ACM Symp. Comp. Geom. , San Diego, 1993, pp. 91–98, Int. J. Comp. Geom. & Appl. 6 (3): 357–377, 1996, http://kenclarkson.org/center/p.pdf

C'est une bonne question et j'y ai déjà pensé. Voici ce que nous avons trouvé:

Vous exécutez votre algorithme fois pour obtenir des sorties x 1 , ⋯ , x n ∈ R d et vous savez ce avec une forte probabilité d' une fraction importante de x i chute s dans une bonne série G . Vous ne savez pas ce qu'est G , juste qu'il est convexe. La bonne nouvelle est qu'il existe un moyen d'obtenir un point en G sans plus d'informations à ce sujet. Appelons ce point f ( x 1 , ⋯ , x n ) .$n$$x_1, \cdots, x_n \in \mathbb{R}^d$$x_i$$G$$G$$G$$f(x_1, \cdots, x_n)$

Théorème. Pour tous les nombres naturels et d , il existe une fonction f : ( R d ) n → R d telle que la suivante soit vérifiée. Soit x 1 . . . x n ∈ R d et soit G ⊂ R d un ensemble convexe satisfaisant $n$$d$$f : (\mathbb{R}^d)^n \to \mathbb{R}^d$$x_1 ... x_n \in \mathbb{R}^d$$G \subset \mathbb{R}^d$Ensuitef(x1,...,Xn)∈G. De plus,fest calculable en polynôme temporel ennd. $$\frac{1}{n}\left|\left\{ i \in [n] : x_i \in G \right\}\right| > \frac{d}{d+1}.$$ $f(x_1, ..., x_n) \in G$$f$$n^d$

Notez que, pour , nous pouvons définir f pour être la médiane. Cela montre donc comment généraliser la médiane pour d > 1 .$d=1$$f$$d>1$

Avant de prouver ce résultat, notez qu'il est serré: Soit et soit x 1 , ⋯ , x d les éléments de base standard et x d + 1 = 0 . Tout sous-ensemble de d des points est contenu dans un espace affine G de dimension d - 1 (qui est uniquement défini par ces points). Mais aucun point n'est contenu dans tous ces espaces affines. Il existe donc un certain G convexe qui contient n ⋅ d / ( d $n=d+1$$x_1, \cdots, x_d$$x_{d+1}=0$$d$$G$$d-1$$G$ points mais ne contient pas f ( x 1 , ⋯ , x n ) , quelle que soit la valeur qui prend.$n\cdot d/(d+1)=d$$f(x_1, \cdots, x_n)$

Preuve. Nous utilisons le résultat suivant.

Théorème de Helly. Soit être des sous-ensembles convexes de R d . Supposons que l'intersection de tout d + 1 K i s ne soit pas vide. L'intersection de tous les K i est alors non vide.$K_1 ... K_m$$\mathbb{R}^d$$d+1$ $K_i$$K_i$

Cliquez ici pour une preuve du théorème de Helly.

Maintenant pour prouver notre théorème:

Soit est une limite supérieure sur le nombre de points non G . Considérons tous les demi-espaces fermés K 1 . . . K m ⊂ R d contenant au moins n - k points avec leur frontière contenant un ensemble de points de rang maximal (il s'agit d'un nombre fini de demi-espaces car chaque K i est défini par d + 1 points sur sa frontière).$k<n/(d+1)$$G$$K_1 ... K_m \subset \mathbb{R}^d$$n-k$$K_i$$d+1$

Le complément de chaque contient au plus k points. Par une limite d'union, l'intersection tout d + 1 K i s contient au moins n - k ( d + 1 ) > 0 points. Selon le théorème de Helly (puisque les demi-espaces sont convexes), il y a un point à l'intersection de tous les K i s . Soit f une fonction qui calcule un point arbitraire dans l'intersection des K i s.$K_i$$k$$d+1$ $K_i$$n-k(d+1)$$K_is$$f$$K_i$

Tout ce qui reste est de montrer que l'intersection de la s est contenu dans G .$K_i$$G$

Sans perte de généralité, est la coque convexe d'un sous-ensemble de points de rang complet. Autrement dit, nous pouvons remplacer G par la coque convexe des points qu'il contient. Si cela n'a pas un rang complet, nous pouvons simplement appliquer notre théorème en dimension inférieure.$G$$G$

Chaque face de définit un demi-espace, où G est l'intersection de ces demi-espaces. Chacun de ces demi-espaces contient G et contient donc au moins n - k points. La frontière de l'un de ces demi-espaces contient une face de G et contient donc un ensemble de points de rang maximal. Ainsi chacun de ces demi-espaces est un K i . Ainsi, l'intersection de tous les K i est contenue dans G , comme requis.$G$$G$$G$$n-k$$G$$K_i$$K_i$$G$

Pour calculer , mettre en place un programme linéaire où les contraintes linéaires correspondent à K i s et une solution réalisable correspond à un point dans l'intersection de tous les K i s. QED$f$$K_i$$K_i$

Malheureusement, ce résultat n'est pas très pratique dans le cadre de grande dimension. Une bonne question est de savoir si nous pouvons calculer plus efficacement:$f$

Problème ouvert. Démontrer le théorème ci-dessus avec la conclusion supplémentaire que peut être calculé en polynôme temporel en n et d . $f$$n$$d$

A part: On peut aussi changer le problème pour obtenir une solution efficace: si ont la propriété que strictement plus de la moitié d'entre eux se trouvent dans une boule B ( y , ε ) , alors on peut trouver un point z qui se trouve dans B ( y , 3 ε ) dans le polynôme temporel en n et d . En particulier, nous pouvons définir z = x i pour un arbitraire i tel que strictement plus de la moitié des points sont dans $x_1, \cdots, x_n$$B(y,\varepsilon)$$z$$B(y,3\varepsilon)$$n$$d$$z=x_i$$i$ .$B(z,2\varepsilon)$

Il existe une notion de la médiane d'un ensemble de points de grande dimension et de normes générales connue sous différents noms. C'est juste le point qui minimise la somme des distances à tous les points de l'ensemble. Il est connu pour avoir une propriété d'amplification de confiance similaire à la médiane habituelle avec une petite augmentation multiplicative de la distance. Vous pouvez trouver les détails dans le théorème 3.1 de cet article: http://arxiv.org/pdf/1308.1334.pdf

Une bonne chose que cet article montre est que le facteur par lequel la distance augmente peut être rendu constant> 1 si vous pouvez amplifier à partir d'une confiance arbitrairement élevée (mais constante <1).

Edit: il y a un autre article récent sur le sujet par Hsu et Sabato http://arxiv.org/pdf/1307.1827v6.pdf Il analyse et applique principalement la procédure dans laquelle le point dans l'ensemble avec la plus petite distance médiane au reste des points est utilisé. Cette procédure peut être utilisée avec n'importe quelle métrique mais ne donne qu'un facteur d'approximation de 3.