0 , a costa de solo un multiplicativo t=O(log1δ)t=O(log⁡1δ)t=O(\log\frac{1}{\delta})sobrecarga. A saber, si..."/>

¿Generalizando el "truco mediano" a dimensiones superiores?

22

Para los algoritmos aleatorios A toman valores reales, el "truco mediano" es una forma simple de reducir la probabilidad de falla a cualquier umbral δ>0 , a costa de solo un multiplicativo t=O(log1δ)sobrecarga. A saber, si elAsalida 's cae en un "buen rango"I=[a,b]con una probabilidad de (al menos)2/3, a continuación, ejecutar copias independientesA1,,Aty tomando la mediana de sus salidasa1,,atdará como resultado un valor que cae enIcon una probabilidad de al menos1δpor los límites de Chernoff / Hoeffding.

¿Hay alguna generalización de este "truco" en dimensiones superiores, digamos Rd , 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 A la salida de valores en Rd , y un "buen conjunto" SRd tal que Pr{A(x,r)S}2/3 para todos x , ¿cómo se puede impulso la probabilidad de éxito a 1δcon solo un costo logarítmico en 1/δ ?

(Dicho de otra manera: dado fijo, arbirary a1,,atRd con la garantía de que al menos 2t3 de losaipertenecen aS, ¿hay algún procedimiento que genere un valor desdeS? Si es así, ¿hay uno eficiente?)

¿Y cuál es el conjunto mínimo de supuestos que uno necesita en S para que se pueda lograr lo anterior?

Lo siento si esto resulta trivial: no pude encontrar una referencia sobre esta pregunta ...

Clemente C.
fuente
3
En el caso especial de que sea ​​un cuboide, ¿funciona si usas el truco mediano en cada dimensión individualmente? Entonces muestree un montón de puntos, luego tome la mediana de sus coordenadas en la dimensión 1, 2, ..., d, y luego obtenga un punto en R d . ¿Tal vez necesitará muestras de O ( log ( d / ϵ ) ) con esta estrategia? SRdO(log(d/ϵ))
Robin Kothari
1
En el caso unidimensional, generalmente conoce pero no el intervalo exacto (aunque incluso si no conoce b - a, el truco mediano todavía funciona). ¿Debemos suponer que sabemos S pero solo hasta la traducción? ¿Hasta traducción y escalado? babaS
Sasho Nikolov
@SashoNikolov Creo que esta sería la "generalización más general" (por ejemplo, solo sabemos que es una "buena bola de diámetro ε "). Sε
Clemente C.
1
Bueno, lo que Thomas escribió en su respuesta es aún más general: supone que ( G en su respuesta) es un conjunto convexo desconocido. SG
Sasho Nikolov

Respuestas:

17

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

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

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

David Eppstein
fuente
Sí. Además, mencionaría que uno puede usar aproximaciones eps de redes eps y sus diversos amigos como una forma de obtener una pequeña muestra que se aproxime bien a esas medidas de profundidad. No obtienes un solo punto, pero obtienes mucha más información.
Sariel Har-Peled
Con la terminología de su trabajo, ¿existe una forma eficiente conocida de verificar un centro reclamado para números racionales βββ?
Si por "eficiente" te refieres a polinomio en la dimensión, entonces no sé de tal resultado. Mi artículo solo encuentra un punto, no le da más información sobre la distribución espacial de la profundidad (como Sariel alude anteriormente).
David Eppstein
¡Gracias! Dejando de lado las consideraciones de eficiencia (por ahora), esto parece decir que para el caso general de conjuntos convexos arbitrarios, ¿no hay forma de aumentar la probabilidad constante a la probabilidad arbitraria? (ya que la fracción de puntos buenos debe ser mayor que ? (o me perdí algo; si lo recuerdo, parece que la segunda formulación que tengo no capta la idea de "repeticiones independientes", en las que tendríamos a manovariosconjuntos de puntos, cada uno de los cuales tiene al menos un2/3fracción de buenos puntos).11d+12/3
Clemente C.
1
Un punto, varios puntos o no, si todo lo que sabe es que existe un conjunto convexo pero no dónde está, y desea poder aumentar la probabilidad de estar en el conjunto correcto mejor que d / (d + 1), entonces la fracción de puntos buenos debe ser al menos d / (d + 1) para sortear el ejemplo simplex. De lo contrario, un adversario podría proporcionarle datos en forma de símplex y elegir aleatoriamente una vecindad épsilon de una cara del símplex como conjunto convexo; incluso si adivina un punto cerca de un vértice del simplex al azar, tendrá al menos 1 / (d + 1) probabilidad de elegir incorrectamente.
David Eppstein
14

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 nR d y sabes con alta probabilidad una gran fracción de x inx1,,xnRdxi 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 ) .GGGf(x1,,xn)

Teorema. Para todos los números naturales y d , existe una función f : ( R d ) nR d tal que se cumple lo siguiente. Let x 1ndf:(Rd)nRd y dejar que G R d sea ​​un conjunto convexo satisfactorio 1x1...xnRdGRdEntoncesf(
1n|{i[n]:xiG}|>dd+1.
. Además, f es computable en el tiempo polinomial en n d . f(x1,...,xn)Gfnd

Tenga en cuenta que, para , podemos establecer f para ser la mediana. Entonces, esto muestra cómo generalizar la mediana para d > 1 .d=1fd>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+1x1,,xdxd+1=0dGd1G puntos pero no contiene f ( x 1 , , x n ) , independientemente del valor que tome.nd/(d+1)=df(x1,,xn)

Prueba. Usamos el siguiente resultado.

El teorema de Helly. Deje ser subconjuntos convexos de R d . Suponga que la intersección de cualquier d + 1 K i s no está vacía. Entonces la intersección de todos los K i s no está vacía.K1...KmRdd+1 KiKi

Haga clic aquí para obtener una prueba del teorema de Helly.

Ahora para probar nuestro teorema:

Deje que ser un límite superior en el número de puntos no en G . Considere todos los medios espacios cerrados K 1 . . . K mR d que contiene al menos n - k puntos con su límite que contiene un conjunto de puntos de rango máximo (este es un número finito de medios espacios ya que cada K i está definido por d + 1 puntos en su límite).k<n/(d+1)GK1...KmRdnkKid+1

El complemento de cada contiene como máximo k puntos. Por un límite de unión, la intersección de cualquier d + 1 K i s contiene al menos n - k ( d + 1 ) > 0 puntos. Según el teorema de Helly (dado que los medios espacios son convexos), hay un punto en la intersección de todos los K i s . Dejamos que f sea ​​una función que calcule un punto arbitrario en la intersección de los K i s.Kikd+1 Kink(d+1)KisfKi

Todos los restos que se va a mostrar que la intersección de la s está contenido en G .KiG

Sin pérdida de generalidad, es el casco convexo de un subconjunto de los puntos con rango completo. Es decir, podemos reemplazar G con el casco convexo de los puntos que contiene. Si esto no tiene rango completo, simplemente podemos aplicar nuestro teorema en una dimensión inferior.GG

Cada cara de define un medio espacio, donde G es la intersección de estos medios espacios. Cada uno de estos medios espacios contiene G y, por lo tanto, contiene al menos n - k puntos. El límite de uno de estos medios espacios contiene una cara deGGGnk y, por lo tanto, contiene un conjunto de puntos de rango máximo. Por lo tanto, cada uno de estos medios espacios es un K i . Por lo tanto, la intersección de todos los K i s está contenida en G , según se requiera.GKiKiG

Para calcular , configure un programa lineal donde las restricciones lineales correspondan a K i sy una solución factible corresponda a un punto en la intersección de todos los K i s. QEDfKiKi

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

Problema abierto Demuestre el teorema anterior con la conclusión adicional de que puede calcularse en un polinomio temporal en n y d . fnd

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

Thomas apoya a Mónica
fuente
Creo que básicamente reinventó la profundidad de Tukey como David Eppstein describe a continuación :)
Suresh Venkat
7

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.

Vitalia
fuente
Gracias, esto se ve bien! Solo lo hojeé hasta ahora, pero (a menos que me equivoque o me salte demasiado rápido), se trata del caso específico de que sea ​​una bola p ; ¿Es eso correcto? Sp
Clemente C.
1
Realmente no. El resultado se indica para todos los espacios de Banach. Para cualquier cuerpo que esté centrado en el origen y simétrico alrededor de su centro, existe una norma correspondiente en la que este cuerpo es la bola unitaria. Dado que, a los fines de su pregunta, podemos suponer sin pérdida de generalidad que el cuerpo convexo está centrado en el origen, obtenemos el resultado para cada cuerpo convexo centralmente simétrico. Quizás con un leve esfuerzo, el resultado puede extenderse a cuerpos convexos generales.
Vitaly
1
Sin embargo, debe conocer la norma para calcular el minimizador para esa norma; si solo sabe que hay una norma pero no cuál es, no tiene suerte.
David Eppstein
1
Tienes razón, David. Necesitas saber la norma. (Esto se traduce en conocer el cuerpo convexo hasta el centro y escalar).
Vitaly
Estaba pensando en este enfoque, pero luego pensé en este contraejemplo para conjuntos convexos arbitrarios. ¿Cómo juega con estos resultados? Deje distribuido en el plano de la siguiente manera: con probabilidad 0.9 , uniforme en ( - 1 , 0 ) y ( + 1 , 0 ) , con probabilidad 0.1 , igual a ( 0 , 0.0001 ) . El conjunto "bueno" convexo es la línea de ( - 1 , 0 ) a ( 1 , 0 )X0.9(1,0)(+1,0)0.1(0,0.0001)(1,0)(1,0). Pero si tomamos muchas muestras, la mediana generalizada será uno de los puntos muestreados ubicados en . Generalice esto fácilmente a dimensiones más altas utilizando un hiperplano y un punto ligeramente desplazado. (0,0.0001)
usul