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

21

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 1Aδ>0UmI=[a,b]2/3A1,...,Atum1,...,umtI1-δt=O(log1δ)AI=[a,b]2/3A1,,Ata1,,atI1δ

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 / δRdARdSRdPr{A(x,r)S}2/3x1δ1/δ

(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 ta1,,atRd aiSS2t3aiSS

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 ...

Clemente C.
fonte
3
No caso especial de que é um cubóide, funciona se você usar o truque mediano em cada dimensão individualmente? Portanto, experimente vários pontos, depois pegue a mediana de suas coordenadas nas dimensões 1, 2, ..., d e então você obtém um ponto em . Talvez você precise de amostras de com esta estratégia? R d O ( log ( d / ε ) )SRdO(log(d/ϵ))
Robin Kothari
11
No caso unidimensional, geralmente você sabe mas não o intervalo exato (embora, mesmo que você não saiba o truque mediano ainda funcione). Devemos assumir que conhecemos mas apenas até a tradução? Até tradução e redimensionamento? b - a SbabaS
Sasho Nikolov
@ShohoNikolov Acho que essa seria a "generalização geral" mais verdadeira (por exemplo, sabemos apenas que é uma "boa bola de diâmetro "). εSε
Clement c
11
Bem, o que Thomas escreveu em sua resposta é ainda mais geral: ele assume que ( em sua resposta) é um conjunto convexo desconhecido. GSG
Sasho Nikolov

Respostas:

17

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 ppnpnp(1p)np

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+11/(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 dO(1/d2)nd

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

David Eppstein
fonte
Sim. Além disso, eu mencionaria que é possível usar as redes eps aproximações eps e seus vários amigos como uma maneira de obter uma pequena amostra que se aproxime bem de tais medidas de profundidade. Você não entende nada, mas obtém muito mais informações.
Sariel Har-Peled
Com a terminologia do seu artigo, existe uma maneira eficiente conhecida de verificar um reivindicado -center para números racionais ? βββ
Se por "eficiente" você quer dizer polinômio na dimensão, não conheço esse resultado. Meu artigo encontra apenas um ponto, não fornece mais informações sobre a distribuição espacial da profundidade (como Sariel menciona acima).
David Eppstein
Obrigado! Pondo de lado as considerações de eficiência (por enquanto), isso parece dizer que, para o caso geral de conjuntos convexos arbitrários, não há como aumentar a probabilidade constante para a probabilidade arbitrária? (como a fração de pontos positivos precisa ser maior que ? (ou eu perdi alguma coisa - olhando para trás, parece que a segunda formulação que eu não capto) idéia de "repetições independentes", onde teríamos em mãos vários conjuntos de pontos, cada um dos quais com pelo menos uma fração de pontos positivos.) 2/311d+12/3
Clement C. C.
11
Um ponto, vários pontos, ou não, se tudo o que você sabe é que existe um conjunto convexo, mas não onde está, e você deseja aumentar a probabilidade de estar no conjunto correto para melhor do que d / (d + 1), então a fração de pontos positivos precisa ser pelo menos d / (d + 1) para contornar o exemplo simplex. Caso contrário, um adversário poderá fornecer dados na forma de um simplex e escolher aleatoriamente um bairro épsilon de uma face do simplex como o conjunto convexo; mesmo se você adivinhar um ponto próximo a um vértice do simplex aleatoriamente, terá pelo menos 1 / (d + 1) de probabilidade de escolher incorretamente.
David Eppstein
14

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 nR 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 ) .nx1,,xnRdxiGGGf(x1,,xn)

Teorema. Para todos os números naturais e d , existe uma função f : ( R d ) nR d, de modo que o seguinte seja válido. Seja x 1 . . . x nR d e deixar L R d seja um conjunto convexo satisfazendo 1ndf:(Rd)nRdx1...xnRdGRdEm seguida,f(x1,...,Xn)L. Além disso,fé computável no tempo polinomial emnd.
1n|{i[n]:xiG}|>dd+1.
f(x1,...,xn)Gfnd

Observe que, para , podemos definir f como a mediana. Portanto, isso mostra como generalizar a mediana para d > 1 .d=1fd>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+1x1,,xdxd+1=0dGd1G pontos, mas não contém f ( x 1 , , x n ) , qualquer que seja o valor que leva.nd/(d+1)=df(x1,,xn)

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.K1...KmRdd+1 KiKi

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 mR 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)GK1...KmRdnkKid+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.Kikd+1 Kink(d+1)KisfKi

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

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.GG

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.GGGnkGKiKiG

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 . QEDfKiKi

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 . fnd

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 Bx1,,xnB(y,ε)zB(y,3ε)ndz=xii .B(z,2ε)

Thomas apoia Monica
fonte
Eu acho que você basicamente reinventou Tukey profundidade como David Eppstein descreve abaixo :)
Suresh Venkat
7

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.

Vitaly
fonte
Obrigado, isso parece bom! Eu apenas o deslizei até agora, mas (a menos que eu esteja enganado ou pule rápido demais), ele lida com o caso específico de ser uma bola p ; isso está correto? Sp
Clement c
11
Na verdade não. O resultado é indicado para todos os espaços de Banach. Para qualquer corpo centrado na origem e simétrico em torno do centro, existe uma norma correspondente na qual esse corpo é a bola unitária. Como para os fins da sua pergunta, podemos assumir, sem perda de generalidade, que o corpo convexo é centrado na origem, obtemos o resultado válido para todo corpo convexo centralmente simétrico. Talvez com algum esforço leve o resultado possa ser estendido a corpos convexos em geral.
Vitaly
11
Você precisa conhecer a norma para calcular o minimizador para essa norma - se você sabe apenas que existe uma norma, mas não o que é, você está sem sorte.
David Eppstein
11
Você está certo, David. Você precisa conhecer a norma. (Isso significa conhecer o corpo convexo até o centro e a escala).
Vitaly
Eu estava pensando nessa abordagem, mas depois pensei nesse contra-exemplo para conjuntos convexos arbitrários. Como ele se encaixa nesses resultados? Seja distribuído no plano da seguinte forma: com probabilidade 0,9 , uniforme em ( - 1 , 0 ) e ( + 1 , 0 ) , com probabilidade 0,1 , igual a ( 0 , 0,0001 ) . O conjunto "bom" convexo é a linha de ( - 1 , 0 ) a ( 1 , 0 )X0.9(1,0)(+1,0)0.1(0,0.0001)(1,0)(1,0). Porém, se coletarmos muitas amostras, a mediana generalizada será um dos pontos amostrados localizados em . Generalize isso facilmente para dimensões mais altas usando um hiperplano e um ponto ligeiramente deslocado. (0,0.0001)
usul