Uogólniając „sztuczkę środkową” do wyższych wymiarów?

W przypadku algorytmów losowych przyjmujących rzeczywiste wartości „sztuczka medianowa” jest prostym sposobem zmniejszenia prawdopodobieństwa niepowodzenia do dowolnego progu , kosztem tylko wielokrotności narzut. Mianowicie, jeśli wyjście mieści się w „dobrym zakresie” z prawdopodobieństwem (co najmniej) , to uruchamianie niezależnych kopii i przyjmując medianę swoich wyników spowoduje, że wartość spadnie do z prawdopodobieństwem co najmniej granicach Chernoffa / Hoeffdinga.$\mathcal{A}$$\delta > 0$$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$

Czy istnieje jakieś uogólnienie tej „sztuczki” do wyższych wymiarów, powiedzmy , gdzie dobrym zasięgiem jest teraz zestaw wypukły (lub kula lub jakikolwiek wystarczająco ładny i uporządkowany zestaw)? To znaczy, biorąc pod uwagę zrandomizowany algorytm wyprowadzający wartości w oraz „dobry zestaw” taki, że dla wszystkich , w jaki sposób można zwiększyć prawdopodobieństwo sukcesu do przy koszcie logarytmicznym tylko w ?$\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$

(Odmiennie sformułowane: biorąc pod uwagę ustalone, arbirary z gwarancją, że co najmniej z należy do , czy istnieje procedura wyprowadzanie wartości z ? Jeśli tak, to czy istnieje efektywna?)2 $a_1,\dots, a_t\in \mathbb{R}^d$ aiS$\frac{2t}{3}$$a_i$$S$$S$

A jaki jest minimalny zestaw założeń, których potrzebuje aby powyższe było możliwe do osiągnięcia?$S$

Przepraszam, jeśli okaże się to trywialne - nie mogłem znaleźć odniesienia do tego pytania ...

To, czego szukasz, to prawie ta sama silna tendencja centralna : sposób zredukowania chmury punktów danych do jednego punktu, tak że jeśli wiele punktów danych jest zbliżonych do jakiejś „podstawowej prawdy”, ale reszta z nich są dowolnie daleko, wtedy twój wynik będzie również bliski prawdzie podstawowej. „Punktem podziału” takiej metody jest ułamek arbitralnie złych wartości odstających, które może tolerować. Różnica polega na tym, że w twoim przypadku chcesz zastąpić „blisko” przez „w wypukłym kadłubie”.

Jednym ze sposobów na uchwycenie tego jest pojęcie głębokości Tukey. Punkt ma głębokość Tukeya (w odniesieniu do danego zestawu punktów danych), jeśli każda półprzestrzeń zawierająca dany punkt zawiera również co najmniej punktów danych. Jeśli istnieje dobra wypukła podprzestrzeń, w której chcesz się znaleźć, to punkt o głębokości Tukeya będzie w niej, dopóki będzie w niej co najmniej punktów danych. Zatem punktem podziału tej metody jest największa wartość , jaką można uzyskać.n p n p ( 1 - p ) n $p$$n$$pn$$p$$(1-p)n$$p$

Niestety ten punkt podziału wynosi , nie jest blisko 1/2, zarówno dla głębokości Tukey, jak i dla twojego problemu. Oto dlaczego: jeśli twoje dane są skupione w pobliżu wierzchołków jednostronnych, to tak długo, jak mniej niż część jest wartościami odstającymi (ale nie wiesz, które), to dowolny punkt w simplex jest bezpieczny do wybrania, ponieważ zawsze znajdzie się w wypukłym kadłubie elementów odstających. Ale jeśli więcej niż punktów może być wartościami odstającymi, to nie ma bezpiecznego miejsca do wybrania: niezależnie od tego, który punkt w elemencie wybranym wybierzesz, wartościami odstającymi mogą być wszystkie punkty z najbliższego wierzchołka liczby pojedynczej i byłbyś poza kadłubem nietypowych.d + 1 1 / ( d + 1 ) 1 / ( d + 1 $1/(d+1)$$d+1$$1/(d+1)$$1/(d+1)$

Jeśli jesteś gotów tolerować gorszy punkt przebicia, bardziej jak , jest to metoda na znalezienie randomizowane głęboki punkt, który jest wielomian zarówno i : patrz mój papiern $O(1/d^2)$$n$$d$

Przybliżenie punktów środkowych za pomocą iterowanych punktów Radona, K. Clarkson, D. Eppstein, GL Miller, C. Sturtivant i S.-H. Teng, 9. ACM Symp. Komp. Geom. , San Diego, 1993, ss. 91–98, Int. J. Comp. Geom. I Appl. 6 (3): 357–377, 1996, http://kenclarkson.org/center/p.pdf

To miłe pytanie i już o tym myślałem. Oto, co wymyśliliśmy:

Uruchomieniu algorytmu razy, aby dostać wyjścia i wiesz, co z dużym prawdopodobieństwem duża część s upadku na jakiegoś dobrego zestawu . Nie wiesz, co to jest , tylko to, że jest wypukłe. Dobrą wiadomością jest to, że istnieje sposób na uzyskanie punktu w bez dalszych informacji na ten temat. Nazwij ten punkt .$n$$x_1, \cdots, x_n \in \mathbb{R}^d$$x_i$$G$$G$$G$$f(x_1, \cdots, x_n)$

Twierdzenie. Dla wszystkich liczb naturalnych i istnieje funkcja taka, że ​​zachowane są następujące elementy. Niech i niech będzie wypukłym zestawem spełniającymNastępnie . Ponadto jest obliczalne w czasie wielomianu w . $n$$d$$f : (\mathbb{R}^d)^n \to \mathbb{R}^d$$x_1 ... x_n \in \mathbb{R}^d$$G \subset \mathbb{R}^d$ $$\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$

Zauważ, że dla możemy ustawić na medianę. To pokazuje, jak uogólnić medianę dla .$d=1$$f$$d>1$

Przed udowodnieniem tego wyniku, zwróć uwagę, że jest ciasny: Niech i niech będą standardowymi elementami podstawowymi, a . Każdy podzbiór punktów jest zawarty w afinicznej przestrzeni o wymiarze (który jest jednoznacznie określony przez te punkty). Ale nie ma sensu we wszystkich tych afinicznych przestrzeniach. Stąd jest wypukły który zawiera punktów, ale nie zawiera , bez względu na jaką wartość.$n=d+1$$x_1, \cdots, x_d$$x_{d+1}=0$$d$$G$$d-1$$G$$n\cdot d/(d+1)=d$$f(x_1, \cdots, x_n)$

Dowód. Używamy następującego wyniku.

Twierdzenie Helly. Niech będą wypukłymi podzbiorami . Załóżmy, że przecięcie dowolnego s jest niepuste. Zatem przecięcie wszystkich jest niepuste.$K_1 ... K_m$$\mathbb{R}^d$$d+1$ $K_i$$K_i$

Kliknij tutaj, aby uzyskać dowód twierdzenia Helly.

Teraz, aby udowodnić nasze twierdzenie:

Niech za górną granicę liczby punktów nie w . Rozważ wszystkie zamknięte półprzestrzenie zawierający co najmniej punktów, a ich granica zawiera zestaw punktów o maksymalnej wartości (jest to skończona liczba półprzestrzeni, ponieważ każde jest zdefiniowane przez punktów na granicy).$k<n/(d+1)$$G$$K_1 ... K_m \subset \mathbb{R}^d$$n-k$$K_i$$d+1$

Uzupełnienie każdego zawiera najwyżej punktów. Przez granicę związkową przecięcie dowolnych zawiera co najmniej > 0 punktów. Zgodnie z twierdzeniem Helly (ponieważ półprzestrzenie jest wypukłe) istnieje punkt na przecięciu wszystkich . Pozwalamy być funkcją, która oblicza dowolny punkt na przecięciu .$K_i$$k$$d+1$ $K_i$$n-k(d+1)$$K_is$$f$$K_i$

Pozostaje to, aby pokazać, że przecięcie się y zawarty jest w .$K_i$$G$

Bez utraty ogólności jest wypukłym kadłubem podzbioru punktów o pełnej randze. Oznacza to, że możemy zastąpić wypukłym kadłubem punktów w nim zawartych. Jeśli to nie ma pełnej rangi, możemy po prostu zastosować nasze twierdzenie w niższym wymiarze.$G$$G$

Każda ściana definiuje półprzestrzeń, gdzie jest przecięciem tych półprzestrzeni. Każda z tych półprzestrzeni zawiera a zatem zawiera co najmniej punktów. Granica jednego z tych półprzestrzeni zawiera twarz a zatem zawiera zestaw punktów o maksymalnej wartości. Zatem każda z tych półprzestrzeni jest . Zatem przecięcie wszystkich jest zawarte w , zgodnie z wymaganiami.$G$$G$$G$$n-k$$G$$K_i$$K_i$$G$

Aby obliczyć , skonfiguruj program liniowy, w którym ograniczenia liniowe odpowiadają s, a wykonalne rozwiązanie odpowiada punktowi przecięcia wszystkich s. CO BYŁO DO OKAZANIA$f$$K_i$$K_i$

Niestety, ten wynik nie jest zbyt praktyczny w ustawieniach wysokowymiarowych. Dobrym pytaniem jest, czy możemy obliczać bardziej wydajnie:$f$

Otwarty problem. Udowodnić wyżej twierdzenia z dodatkowym wniosku, że może być obliczony czas wielomian i . $f$$n$$d$

Poza tym: Możemy również zmienić problem, aby uzyskać wydajne rozwiązanie: jeśli mają właściwość, że ściśle ponad połowa z nich leży w kulce , możemy znaleźć punkt który znajduje się w w czasie wielomian i . W szczególności możemy ustawić dla dowolnego tak że dokładnie więcej niż połowa punktów znajduje się w .$x_1, \cdots, x_n$$B(y,\varepsilon)$$z$$B(y,3\varepsilon)$$n$$d$$z=x_i$$i$$B(z,2\varepsilon)$

Istnieje pojęcie mediany zbioru punktów w wysokich wymiarach i ogólnych normach, które jest znane pod różnymi nazwami. To tylko punkt, który minimalizuje sumę odległości do wszystkich punktów w zestawie. Wiadomo, że ma podobną właściwość wzmocnienia ufności jak zwykła mediana z niewielkim multiplikatywnym wzrostem odległości. Szczegóły znajdują się w Twierdzeniu 3.1 tego dokumentu: http://arxiv.org/pdf/1308.1334.pdf

Jedną fajną rzeczą, którą pokazuje ten artykuł, jest to, że czynnikiem, dzięki któremu zwiększa się odległość, można ustawić dowolną stałą> 1, jeśli można zwiększyć z arbitralnie wysokiej (ale stałej <1) pewności.

Edycja: istnieje inny niedawny artykuł na ten temat autorstwa Hsu i Sabato http://arxiv.org/pdf/1307.1827v6.pdf Przeważnie analizuje i stosuje procedurę, w której punkt w zestawie o najmniejszej medianie odległości do reszty punktów jest używany. Tę procedurę można zastosować z dowolną miarą, ale daje ona jedynie współczynnik przybliżenia 3.