Generalizando o "truque mediano" para dimensões mais altas?

Para algoritmos aleatórios usando valores reais, o "truque mediano" é uma maneira simples de reduzir a probabilidade de falha a qualquer limite , ao custo de apenas uma multiplicativa sobrecarga. Ou seja, se a saída de cair em um "bom intervalo" com probabilidade (pelo menos) , executando cópias independentes e tomando a mediana de suas saídas resultará em um valor caindo em com probabilidade pelo menos pelos limites de Chernoff / Hoeffding. δ > 0 t = O ( log $\mathcal{A}$$\delta > 0$UmI=[a,b]2/3A1,...,Atum1,...,umtI1-$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$

Existe alguma generalização desse "truque" para dimensões mais altas, digamos , em que o bom intervalo agora é um conjunto convexo (ou uma bola ou qualquer conjunto suficientemente agradável e estruturado)? Ou seja, dado um algoritmo aleatório gera valores em , e um "conjunto bom" tal que para todos , como se pode aumentar a probabilidade de sucesso para com apenas um custo logarítmico em ?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$

(Formulado de forma diferente: dado fixo, arbitrário com a garantia de que pelo menos dos pertencem a , existe um procedimento saída de um valor de ? Em caso afirmativo, existe um valor eficiente?)2 $a_1,\dots, a_t\in \mathbb{R}^d$ aiS$\frac{2t}{3}$$a_i$$S$$S$

E qual é o conjunto mínimo de suposições necessárias em para que o acima seja possível?$S$

Desculpe se isso é trivial - não foi possível encontrar uma referência sobre esta pergunta ...

O que você está procurando é quase o mesmo, uma tendência central robusta : uma maneira de reduzir uma nuvem de pontos de dados para um único ponto, de modo que, se muitos deles estiverem próximos de alguma "verdade básica", mas o restante deles arbitrariamente distantes, sua saída também estará próxima da verdade básica. O "ponto de ruptura" desse método é a fração de valores discrepantes arbitrariamente ruins que ele pode tolerar. A diferença é que, no seu caso, você deseja substituir "próximo a" por "dentro do casco convexo de".

Uma maneira de capturar isso é com a noção de profundidade de Tukey. Um ponto tem profundidade de Tukey (em relação a um determinado conjunto de pontos de dados) se cada espaço no meio que contenha o ponto especificado também contiver pelo menos pontos de dados. Se houver um bom subespaço convexo no qual você deseja estar, um ponto com profundidade de Tukey estará dentro dele, desde que haja pelo menos dos pontos de dados dentro dele. Portanto, o ponto de detalhamento desse método é o maior valor de que você pode atingir.n p n p ( 1 - p ) n $p$$n$$pn$$p$$(1-p)n$$p$

Infelizmente, esse ponto de ruptura é , não próximo a 1/2, tanto para a profundidade de Tukey quanto para o seu problema. Eis o porquê: se seus dados estão agrupados perto dos vértices de um simplex, desde que menos de fração deles sejam outliers (mas você não sabe quais), então qualquer ponto o simplex é seguro de escolher, pois sempre estará dentro do casco convexo dos não-discrepantes. Mas se mais de dos pontos puderem ser discrepantes, não há lugar seguro para escolher: qualquer que seja o ponto simples que você escolher, os discrepantes poderão ser todos os pontos do vértice simplex mais próximo e você estaria fora do casco dos não-discrepantes.d + 1 1 / ( d + 1 ) 1 / ( d + 1 $1/(d+1)$$d+1$$1/(d+1)$$1/(d+1)$

Se você está disposto a tolerar um ponto de ruptura pior, mais parecido com , existe um método aleatório para encontrar um ponto profundo polinomial em e : veja meu artigon $O(1/d^2)$$n$$d$

Pontos centrais aproximados com pontos iterados de Radon, K. Clarkson, D. Eppstein, GL Miller, C. Sturtivant e S.-H. Teng, 9º Symp de ACM. Comp. Geom. , San Diego, 1993, pp. 91–98, Int. J. Comp. Geom. & Appl. 6 (3): 357–377, 1996, http://kenclarkson.org/center/p.pdf

Essa é uma pergunta interessante e eu já pensei nisso antes. Aqui está o que descobrimos:

Você executar o seu algoritmo de vezes para obter saídas x 1 , ⋯ , x n ∈ R d e você sabe o que com grande probabilidade de uma grande fração de x i queda s em um bom conjunto G . Você não sabe o que é G , apenas que é convexo. A boa notícia é que existe uma maneira de obter um ponto em G sem mais informações. Chame esse ponto de 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)$

Teorema. Para todos os números naturais e d , existe uma função f : ( R d ) n → R d, de modo que o seguinte seja válido. Seja x 1 . . . x n ∈ R d e deixar L ⊂ R d seja um conjunto convexo satisfazendo $n$$d$$f : (\mathbb{R}^d)^n \to \mathbb{R}^d$$x_1 ... x_n \in \mathbb{R}^d$$G \subset \mathbb{R}^d$Em seguida,f(x1,...,Xn)∈L. Além disso,fé computável no tempo polinomial emnd. $$\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$

Observe que, para , podemos definir f como a mediana. Portanto, isso mostra como generalizar a mediana para d > 1 .$d=1$$f$$d>1$

Antes de provar esse resultado, observe que ele é estanque: Seja e x 1 , ⋯ , x d sejam os elementos base padrão ex x d + 1 = 0 . Qualquer subconjunto de d dos pontos está contido em um espaço afim G da dimensão d - 1 (que é definida exclusivamente por esses pontos). Mas nenhum ponto está contido em todos esses espaços afins. Portanto, existe algum G convexo que contém n ⋅ d / ( d $n=d+1$$x_1, \cdots, x_d$$x_{d+1}=0$$d$$G$$d-1$$G$ pontos, mas não contém f ( x 1 , ⋯ , x n ) , qualquer que seja o valor que leva.$n\cdot d/(d+1)=d$$f(x_1, \cdots, x_n)$

Prova. Usamos o seguinte resultado.

Teorema de Helly. Seja sejam subconjuntos convexos de R d . Suponha que a interseção de qualquer d + 1 K i s não seja vazia. Em seguida, a intersecção de todos K i s é não vazio.$K_1 ... K_m$$\mathbb{R}^d$$d+1$ $K_i$$K_i$

Clique aqui para obter uma prova do Teorema de Helly.

Agora, para provar nosso teorema:

Deixe que ser um limite superior para o número de pontos não em G . Considere todos os meios-espaços fechados K 1 . . . K m ⊂ R d contendo pelo menos n - k pontos com seus limites contendo um conjunto de pontos de classificação máxima (este é um número finito de meiosespaços, pois cada K i é definido por d + 1 pontos em seu limite).$k<n/(d+1)$$G$$K_1 ... K_m \subset \mathbb{R}^d$$n-k$$K_i$$d+1$

O complemento de cada contém no máximo k pontos. Por um limite de união, a interseção que qualquer d + 1 K i s contém pelo menos n - k ( d + 1 ) > 0 pontos. Pelo teorema de Helly (desde halfspaces são convexas), há um ponto na intersecção de toda a K i s . Seja f uma função que calcule um ponto arbitrário na interseção dos K i s.$K_i$$k$$d+1$ $K_i$$n-k(d+1)$$K_is$$f$$K_i$

Tudo o que resta é o de mostrar que a intersecção entre o s está contido na L .$K_i$$G$

Sem perda de generalidade, é o casco convexo de um subconjunto dos pontos com classificação completa. Ou seja, podemos substituir G pelo casco convexo dos pontos que ele contém. Se isso não tiver uma classificação completa, podemos simplesmente aplicar nosso teorema na dimensão inferior.$G$$G$

Cada face de define um meio espaço, onde G é a interseção desses meios espaços. Cada um desses semi-espaços contém G e, portanto, contém pelo menos n - k pontos. O limite de um desses semi-espaços contém uma face de G e, portanto, contém um conjunto de pontos de classificação máxima. Assim, cada um desses semi-espaços é um K i . Assim, o cruzamento de todos K i s está contido em L , como exigido.$G$$G$$G$$n-k$$G$$K_i$$K_i$$G$

Para calcular , configure um programa linear em que as restrições lineares correspondam a K i se uma solução viável corresponda a um ponto na interseção de todos os k i . QED$f$$K_i$$K_i$

Infelizmente, esse resultado não é muito prático no cenário de alta dimensão. Uma boa pergunta é se podemos calcular mais eficiência:$f$

Problema em aberto. Prove o teorema acima com a conclusão adicional de que pode ser calculado no polinômio do tempo em n e d . $f$$n$$d$

Além disso: também podemos mudar o problema para obter uma solução eficiente: se têm a propriedade que estritamente mais da metade deles está na bola B ( y , ε ) , então podemos encontrar um ponto z que se encontra em B ( y , 3 ε ) no polinômio do tempo em n e d . Em particular, podemos definir z = x i para um i arbitrário de modo que estritamente mais da metade dos pontos esteja em $x_1, \cdots, x_n$$B(y,\varepsilon)$$z$$B(y,3\varepsilon)$$n$$d$$z=x_i$$i$ .$B(z,2\varepsilon)$

Existe uma noção da mediana de um conjunto de pontos em altas dimensões e normas gerais que é conhecida sob vários nomes. É apenas o ponto que minimiza a soma das distâncias para todos os pontos do conjunto. Sabe-se que possui uma propriedade de amplificação de confiança semelhante à mediana usual com um pequeno aumento multiplicativo na distância. Você pode encontrar os detalhes no Teorema 3.1 deste artigo: http://arxiv.org/pdf/1308.1334.pdf

Uma coisa interessante que este artigo mostra é que o fator pelo qual a distância aumenta pode ser constante> 1 se você puder amplificar a partir de uma confiança arbitrariamente alta (mas constante <1).

Edit: existe outro artigo recente sobre o tema por Hsu e Sabato http://arxiv.org/pdf/1307.1827v6.pdf Ele analisa e aplica principalmente o procedimento no qual o ponto do conjunto com a menor distância mediana para o resto dos pontos é usado. Este procedimento pode ser usado com qualquer métrica, mas fornece apenas um fator de aproximação de 3.