Para los algoritmos aleatorios toman valores reales, el "truco mediano" es una forma simple de reducir la probabilidad de falla a cualquier umbral , a costa de solo un multiplicativo sobrecarga. A saber, si elsalida 's cae en un "buen rango"con una probabilidad de (al menos), a continuación, ejecutar copias independientesy tomando la mediana de sus salidasdará como resultado un valor que cae encon una probabilidad de al menospor los límites de Chernoff / Hoeffding.
¿Hay alguna generalización de este "truco" en dimensiones superiores, digamos , donde el buen rango es ahora un conjunto convexo (o una bola, o cualquier conjunto suficientemente agradable y estructurado)? Es decir, dado un algoritmo aleatorio la salida de valores en , y un "buen conjunto" tal que para todos , ¿cómo se puede impulso la probabilidad de éxito a con solo un costo logarítmico en ?
(Dicho de otra manera: dado fijo, arbirary con la garantía de que al menos de lospertenecen a, ¿hay algún procedimiento que genere un valor desde? Si es así, ¿hay uno eficiente?)
¿Y cuál es el conjunto mínimo de supuestos que uno necesita en para que se pueda lograr lo anterior?
Lo siento si esto resulta trivial: no pude encontrar una referencia sobre esta pregunta ...
fuente
Respuestas:
Lo que está buscando es casi la misma tendencia central robusta : una forma de reducir una nube de puntos de datos a un solo punto, de modo que si muchos de los puntos de datos están cerca de alguna "verdad básica", pero el resto de ellos están arbitrariamente lejos, entonces su salida también estará cerca de la verdad básica. El "punto de ruptura" de dicho método es la fracción de valores atípicos arbitrariamente malos que puede tolerar. La diferencia es que en su caso desea reemplazar "cerca de" por "dentro del casco convexo de".
Una forma de capturar esto es con la noción de profundidad de Tukey. Un punto tiene la profundidad de Tukey (con respecto a un conjunto dado de n puntos de datos) si cada medio espacio que contiene el punto dado también contiene al menos p n puntos de datos. Si hay un buen subespacio convexo en el que desea estar dentro, entonces un punto con la profundidad de Tukey p estará dentro, siempre que haya al menos ( 1 - p ) n de los puntos de datos dentro de él. Entonces, el punto de ruptura de este método es el mayor valor de p que puede alcanzar.p n pn p (1−p)n p
Desafortunadamente, este punto de ruptura es , no cercano a 1/2, tanto para la profundidad de Tukey como para su problema. He aquí por qué: si sus datos se agrupan cerca de los vértices d + 1 de un símplex, siempre que menos de 1 / ( d + 1 ) fracción de ellos sean valores atípicos (pero no sabe cuáles), entonces cualquier punto en el simplex es seguro de elegir, ya que siempre estará dentro del casco convexo de los no atípicos. Pero si más de 1 / ( d + 1 )1/(d+1) d+1 1/(d+1) 1/(d+1) de los puntos pueden ser valores atípicos, no hay ningún lugar seguro para elegir: cualquiera que sea el punto en el simplex que elija, los valores atípicos podrían ser todos los puntos del vértice simplex más cercano, y estaría fuera del casco del no valores atípicos
Si está dispuesto a tolerar un punto de ruptura peor, más parecido a , hay un método aleatorio para encontrar un punto profundo que sea polinómico tanto en n como en d : vea mi artículoO(1/d2) n d
Aproximación de puntos centrales con puntos de radón iterados, K. Clarkson, D. Eppstein, GL Miller, C. Sturtivant y S.-H. Teng, 9º ACM Symp. Comp. Geom , San Diego, 1993, págs. 91–98, Int. J. Comp. Geom & Appl. 6 (3): 357–377, 1996, http://kenclarkson.org/center/p.pdf
fuente
Esta es una buena pregunta y lo he pensado antes. Esto es lo que se nos ocurrió:
Ejecutas tu algoritmo veces para obtener salidas x 1 , ⋯ , x n ∈ R d y sabes con alta probabilidad una gran fracción de x in x1,⋯,xn∈Rd xi caída s en algún bien establecido . No sabes qué es G , solo que es convexo. La buena noticia es que hay una manera de obtener un punto en G sin más información al respecto. Llame a este punto f ( x 1 , ⋯ , x n ) .G G G f(x1,⋯,xn)
Tenga en cuenta que, para , podemos establecer f para ser la mediana. Entonces, esto muestra cómo generalizar la mediana para d > 1 .d=1 f d>1
Antes de probar este resultado, tenga en cuenta que es ajustado: Sea y sea x 1 , ⋯ , x d los elementos básicos estándar yx d + 1 = 0 . Cualquier subconjunto de d de los puntos está contenido en un espacio afín G de dimensión d - 1 (que se define de manera única por esos puntos). Pero ningún punto está contenido en todos esos espacios afines. Por lo tanto, hay algo de G convexo que contiene n ⋅ d / ( d +n=d+1 x1,⋯,xd xd+1=0 d G d−1 G puntos pero no contiene f ( x 1 , ⋯ , x n ) , independientemente del valor que tome.n⋅d/(d+1)=d f(x1,⋯,xn)
Desafortunadamente, este resultado no es muy práctico en el entorno de alta dimensión. Una buena pregunta es si podemos calcular más eficiente:f
Aparte: también podemos cambiar el problema para obtener una solución eficiente: si tienen la propiedad de que estrictamente más de la mitad se encuentran en una bola B ( y , ε ) , entonces podemos encontrar un punto z que yace en B ( y , 3 ε ) en polinomio tiempo en n yx1,⋯,xn B(y,ε) z B(y,3ε) n . En particular, podemos establecer z = x i para un i arbitrario demodo que estrictamente más de la mitad de los puntos estén en Bd z=xi i .B(z,2ε)
fuente
Existe una noción de la mediana de un conjunto de puntos en grandes dimensiones y normas generales que se conoce con varios nombres. Es solo el punto que minimiza la suma de distancias a todos los puntos del conjunto. Se sabe que tiene una propiedad de amplificación de confianza similar a la mediana habitual con un pequeño aumento multiplicativo en la distancia. Puede encontrar los detalles en el Teorema 3.1 de este documento: http://arxiv.org/pdf/1308.1334.pdf
Una cosa buena que muestra este artículo es que el factor por el cual la distancia aumenta puede hacerse constante> 1 si puede amplificar desde una confianza arbitrariamente alta (pero constante <1).
Editar: hay otro artículo reciente sobre el tema de Hsu y Sabato http://arxiv.org/pdf/1307.1827v6.pdf Principalmente analiza y aplica el procedimiento en el que el punto en el conjunto con la distancia media más pequeña al resto de los puntos se usa. Este procedimiento se puede usar con cualquier métrica, pero solo da un factor de aproximación de 3.
fuente