Dimensión VC de los cilindros dentro de un cilindro

8

Deseo saber la dimensión VC de un espacio de rango construido de la siguiente manera:(X,R)

  1. X es el cilindro {(x,y,z)R3|x2+y21}
  2. Los rangos en R se forman tomando la unión de discos circulares de manera que:
    • el plano que contiene el disco es ortogonal al eje z ("apilamos" los discos en la dirección z)
    • un disco es tangente al límite del cilindro en el punto (1,0,z)
    • un disco tiene un diámetro f(z)+1 , donde f(z) está limitado (estrictamente) por 1<f(z)<1 , y aumenta estrictamente monotónicamente, disminuye estrictamente monotónicamente o es constante.
  3. Cualquier conjunto construido girando uno de estos rangos sobre el eje z en un ángulo arbitrario también es un rango.

Intuitivamente, imagina tomar un conjunto de monedas (circulares, por supuesto) y clasificarlas por diámetro, ya sea disminuyendo o aumentando. Luego colóquelos cuidadosamente en un tubo (el cilindro principal) en ese orden, de modo que cada uno descanse sobre el último. Ahora incline el tubo ligeramente para que todos descansen contra el costado del cilindro. Si nuestras monedas tuvieran un grosor cero y tuviéramos una para cada número real, este sería nuestro rango.

Estoy principalmente interesado en el caso de que f(z) sea ​​sigmoide, como la función de error o tanh . Específicamente, estoy interesado en los rangos cilíndricos formados por la familia de funciones tanh(α(zβ)) , donde α,βR .

Sé que este espacio de rango tiene al menos VC-dim 4 (puedo construir un conjunto de cuatro puntos que rompe), pero estoy interesado en ponerle un límite superior y entender por qué. Yo sé eso:

  1. Los discos circulares en R2 tienen VC-dim 3
  2. Los subconjuntos de la tira que están delimitados arriba o abajo por tienen al menos VC-dim 3, probablemente igual a 3, porque la parte de la pendiente de la función actúa como una línea{1y1}R2tanh(α(zβ))tanh

¿Hay alguna forma de combinar estos hechos para obtener un límite superior en la dimensión VC ? ¿Hay algo que decir sobre que cumpla con los criterios en (2)?f(z)

Josephine Moeller
fuente
Parece que estoy malentendido algo. Si la función es fija, entonces cada rango está determinado únicamente por el ángulo de rotación sobre el eje . Luego terminas esencialmente tratando de romper intervalos circulares con puntos. ¿Qué es lo que me estoy perdiendo? ¿Puede la función ser diferente para diferentes rangos? fzf
James King
1
Buena pregunta. Sí, puede ser diferente. Como se señala en la respuesta a continuación, debe tener cuidado con , pero puede pertenecer a una familia de funciones. Como en el ejemplo anterior, puede pertenecer a la familia de funciones . fffftanh(α(zβ))
Josephine Moeller

Respuestas:

4

Necesita la restricción sigmoidea en para que la dimensión VC sea finita. De lo contrario, puede dejar que comporte como una escalera, con arbitrariamente muchos pasos. Entonces estas escaleras pueden tener arbitrariamente muchas intersecciones. Esto permite que rangos admitan subconjuntos diferentes. ffn2n

Si es un polinomio, puede vincular la dimensión VC utilizando el grado del polinomio (combinado con el grado del polinomio (2) que describe el disco). Pero no estoy seguro de cómo aplicar este tipo de resultado para .f(z)tanh

Jeff Phillips
fuente
Derecha. Si tiene un polinomio , puede usar el límite descrito en Matousek. Pero una trascendental plantea problemas a este respecto. f(t)f(t)
Josephine Moeller
1
Hay algo de trabajo en estructuras / teoría o-minimal que trata de manejar tales cosas. en.wikipedia.org/wiki/O-minimal_theory#Examples
Sariel Har-Peled
@Sariel: ¿Estás diciendo que esta sería una forma, por ejemplo, de definir algún tipo de elevación a un espacio construido a partir de funciones trascendentales de las coordenadas, en lugar de las polinomiales? ¿Porque las funciones hiperbólicas son Pfaffian?
Josephine Moeller
Bien. Es una extensión de la complejidad algebraica constante. Puede ser remotamente relevante, francamente no lo sé.
Sariel Har-Peled