Verallgemeinern des „Median-Tricks“ auf höhere Dimensionen?

Für randomisierte Algorithmen die reelle Werte annehmen, ist der "Median-Trick" eine einfache Methode, um die Wahrscheinlichkeit eines Ausfalls auf einen Schwellenwert zu reduzieren , und zwar nur auf Kosten eines multiplikativen Gemeinkosten. Wenn nämlich die Ausgabe von mit einer Wahrscheinlichkeit von (mindestens) in einen "guten Bereich" fällt, werden unabhängige Kopien und unter Berücksichtigung des Medians ihrer Ausgaben ergibt sich ein Wert, der mit einer Wahrscheinlichkeit von mindestens nach Chernoff / Hoeffding-Schranken in fällt . δ > 0 t = O ( log $\mathcal{A}$$\delta > 0$AI=[a,b]2/3A1,...,Ateinen1,...,atI1-$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$$1-\delta$

Gibt es eine Verallgemeinerung dieses "Tricks" zu höheren Dimensionen, sagen wir , wo der gute Bereich jetzt eine konvexe Menge (oder eine Kugel oder eine ausreichend schöne und strukturierte Menge) ist? Das heißt, ein randomisierter Algorithmus Werte in und eine "gute Menge" so dass für alle , wie kann man die Erfolgswahrscheinlichkeit mit nur logarithmischen Kosten in auf erhöhen ?A R d S⊆ R d P r { A (x,r)∈S}≥2 / 3x1-δ1 /$\mathbb{R}^d$$\mathcal{A}$$\mathbb{R}^d$$S\subseteq \mathbb{R}^d$$\mathbb{P}_r\{ \mathcal{A}(x,r) \in S \} \geq 2/3$$x$$1-\delta$$1/\delta$

(Anders ausgedrückt: Bei gegebenem festen, willkürlichen mit der Garantie, dass mindestens der zu gehören , gibt es eine Prozedur einen Wert ausgeben von ? Wenn ja, gibt es einen effizienten?)2 $a_1,\dots, a_t\in \mathbb{R}^d$ aiS$\frac{2t}{3}$$a_i$$S$$S$

Und was ist der minimale Satz von Annahmen, den man für braucht, um das oben Genannte zu erreichen?$S$

Entschuldigung, wenn sich herausstellt, dass dies trivial ist - ich konnte zu dieser Frage keine Referenz finden ...

Was Sie suchen, ist fast dieselbe robuste zentrale Tendenz : eine Möglichkeit, eine Datenpunktwolke auf einen einzigen Punkt zu reduzieren, sodass viele der Datenpunkte einer "Grundwahrheit" nahe kommen, der Rest jedoch beliebig weit weg sind, dann wird dein Output auch nahe an der Bodenwahrheit liegen. Die "Durchbruchstelle" einer solchen Methode ist der Anteil willkürlich schlechter Ausreißer, den sie tolerieren kann. Der Unterschied besteht darin, dass Sie in Ihrem Fall "in der Nähe von" durch "in der konvexen Hülle von" ersetzen möchten.

Eine Möglichkeit, dies einzufangen, ist der Begriff der Tukey-Tiefe. Ein Punkt hat die Tukey-Tiefe (in Bezug auf eine gegebene Menge von n Datenpunkten), wenn jeder Halbraum, der den gegebenen Punkt enthält, auch mindestens p n Datenpunkte enthält . Wenn es einen guten konvexen Unterraum gibt, in dem Sie sich befinden möchten, befindet sich ein Punkt mit der Tukey-Tiefe p darin, solange sich mindestens ( 1 - p ) n der Datenpunkte darin befinden. Der Durchschlagspunkt dieser Methode ist also der größte Wert von p , den Sie erreichen können.$p$$n$$pn$$p$$(1-p)n$$p$

Leider ist dieser Aufschlüsselungspunkt , nicht nahe 1/2, sowohl für die Tukey-Tiefe als auch für Ihr Problem. Hier ist der Grund: Wenn Ihre Daten in der Nähe der d + 1- Eckpunkte eines Simplex gruppiert sind , sind so lange weniger als 1 / ( d + 1 ) Bruchteil davon Ausreißer (aber Sie wissen nicht, welche), irgendwo in Der Simplex kann sicher ausgewählt werden, da er sich immer innerhalb der konvexen Hülle der Nicht-Ausreißer befindet. Aber wenn mehr als 1 / ( d + 1 $1/(d+1)$$d+1$$1/(d+1)$$1/(d+1)$ Bei den Punkten kann es sich um Ausreißer handeln, es gibt jedoch keinen Ort, der sicher ausgewählt werden kann: Unabhängig davon, welchen Punkt im Simplex Sie auswählen, können die Ausreißer alle Punkte des nächsten Simplex-Scheitelpunkts sein, und Sie befinden sich außerhalb des Rumpfs des Nicht-Simplex-Scheitelpunkts. Ausreißer.

Wenn Sie einen schlechteren Durchschlag tolerieren wollen, eher wie , gibt es eine zufällige Methode, um einen tiefen Punkt zu finden, der sowohl in n als auch in d polynomisch ist : siehe meine Arbeit$O(1/d^2)$$n$$d$

Approximation von Mittelpunkten mit iterierten Radonpunkten, K. Clarkson, D. Eppstein, GL Miller, C. Sturtivant und S.-H. Teng, 9. ACM Symp. Comp. Geom. , San Diego, 1993, S. 91–98, Int. J. Comp. Geom. & Appl. 6 (3): 357–377, 1996, http://kenclarkson.org/center/p.pdf

Dies ist eine nette Frage, über die ich schon einmal nachgedacht habe. Folgendes haben wir uns ausgedacht:

Sie führen Ihren Algorithmus mal aus, um die Ausgaben x 1 , ⋯ , x n ∈ R d zu erhalten, und Sie wissen, was mit hoher Wahrscheinlichkeit ein großer Bruchteil von x i s in eine gute Menge G fällt . Sie wissen nicht, was G ist, nur dass es konvex ist. Die gute Nachricht ist, dass es eine Möglichkeit gibt, einen Punkt in G zu bekommen, ohne weitere Informationen darüber. Nenne diesen Punkt 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)$

Satz. Für alle natürlichen Zahlen und D gibt es eine Funktion f : ( R d ) n → R d , so daß folgendes gilt. Sei x 1 . . . x n ∈ R d und lassen G ⊂ R d eine konvexe Menge befriedigend sein $n$$d$$f : (\mathbb{R}^d)^n \to \mathbb{R}^d$$x_1 ... x_n \in \mathbb{R}^d$$G \subset \mathbb{R}^d$Dannf(x1,...,Xn)∈G. Zudemfist inZeitPolynom in berechenbarnd. $$\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$

Beachten Sie, dass wir für f als Median festlegen können . Dies zeigt also, wie der Median für d > 1 verallgemeinert wird .$d=1$$f$$d>1$

Bevor Sie dieses Ergebnis beweisen, stellen Sie fest, dass es eng ist: Sei und sei x 1 , ⋯ , x d das Standardbasiselement und x d + 1 = 0 . Jede Teilmenge von d der Punkte ist in einem affinen Raum G der Dimension d - 1 enthalten (der durch diese Punkte eindeutig definiert ist). Aber in all diesen affinen Räumen ist kein Punkt enthalten. Daher gibt es ein konvexes G , das n ⋅ d / ( d $n=d+1$$x_1, \cdots, x_d$$x_{d+1}=0$$d$$G$$d-1$$G$ Punkte, enthält aber kein f ( x 1 , ⋯ , x n ) , welcher Wert auch immer angenommen wird.$n\cdot d/(d+1)=d$$f(x_1, \cdots, x_n)$

Beweis. Wir verwenden das folgende Ergebnis.

Der Satz von Helly. Sei konvexe Teilmengen von R d sein . Angenommen, der Schnittpunkt von d + 1 K i s ist nicht leer. Dann ist der Schnittpunkt aller K i s nicht leer.$K_1 ... K_m$$\mathbb{R}^d$$d+1$ $K_i$$K_i$

Klicken Sie hier, um einen Beweis für Hellys Theorem zu erhalten.

Nun, um unseren Satz zu beweisen:

$k<n/(d+1)$$G$$K_1 ... K_m \subset \mathbb{R}^d$$n-k$$K_i$$d+1$

$K_i$$k$$d+1$ $K_i$$n-k(d+1)$$K_is$$f$$K_i$

$K_i$$G$

$G$$G$

$G$$G$$G$$n-k$$G$$K_i$$K_i$$G$

$f$$K_i$$K_i$

$f$

$f$$n$$d$

$x_1, \cdots, x_n$$B(y,\varepsilon)$$z$$B(y,3\varepsilon)$$n$$d$$z=x_i$$i$$B(z,2\varepsilon)$

Es gibt einen Begriff des Medians einer Menge von Punkten in hohen Dimensionen und allgemeinen Normen, der unter verschiedenen Namen bekannt ist. Es ist nur der Punkt, der die Summe der Abstände zu allen Punkten in der Menge minimiert. Es ist bekannt, dass es eine ähnliche Konfidenzverstärkungseigenschaft wie der übliche Median mit einer kleinen multiplikativen Zunahme des Abstands aufweist. Sie finden die Details in Satz 3.1 dieses Papiers: http://arxiv.org/pdf/1308.1334.pdf

Eine schöne Sache, die dieser Aufsatz zeigt, ist, dass der Faktor, um den der Abstand zunimmt, zu jeder Konstante> 1 gemacht werden kann, wenn Sie von einem willkürlich hohen (aber konstanten <1) Vertrauen verstärken können.

Edit: es gibt eine andere kürzlich erschienene Arbeit über das Thema von Hsu und Sabato http://arxiv.org/pdf/1307.1827v6.pdf Es analysiert meist und wendet das Verfahren , bei dem der Punkt im Satz mit dem kleinsten mittleren Abstand zum Rest der Punkte wird verwendet. Dieses Verfahren kann mit jeder Metrik angewendet werden, liefert jedoch nur einen Näherungsfaktor von 3.