Dimensão VC dos cilindros dentro de um cilindro

8

Desejo conhecer a dimensão VC de um espaço de intervalo construído da seguinte maneira:(X,R)

  1. X é o cilindro {(x,y,z)R3|x2+y21}
  2. Os intervalos em R são formados pela união de discos circulares, de modo que:
    • o plano que contém o disco é ortogonal ao eixo z ("empilhamos" os discos na direção z)
    • um disco é tangente ao limite do cilindro no ponto (1,0,z)
    • um disco tem diâmetro f(z)+1 , onde f(z) é delimitado (estritamente) por 1<f(z)<1 e aumentando estritamente monotonicamente, estritamente monotonicamente diminuindo ou constante.
  3. Qualquer conjunto construído girando uma dessas faixas em torno do eixo z por um ângulo arbitrário também é uma faixa.

Intuitivamente, imagine pegar um conjunto de moedas (circular, é claro) e classificá-las por diâmetro, diminuindo ou aumentando. Em seguida, solte-os cuidadosamente em um tubo (o cilindro principal) nessa ordem, para que cada um fique no último. Agora incline o tubo levemente para que todos descanse na lateral do cilindro. Se nossas moedas tivessem espessura zero e tivéssemos uma para cada número real, esse seria o nosso alcance.

Estou mais interessado no caso de f(z) ser sigmóide, como a função de erro ou tanh . Especificamente, estou interessado nos intervalos cilíndricos formados pela família de funções tanh(α(zβ)) , onde α,βR .

Eu sei que esse espaço de alcance tem pelo menos VC-dim 4 (eu posso construir um conjunto de quatro pontos que ele quebra), mas estou interessado em colocar um limite superior nele e entender o porquê. Eu sei disso:

  1. Os discos circulares em R2 possuem VC-dim 3
  2. Os subconjuntos da faixa que são delimitados acima ou abaixo por têm pelo menos VC-dim 3, provavelmente igual a 3, porque a parte da inclinação da função atua como uma linha tanh ( α ( z - β ) ) tanh{1y1}R2tanh(α(zβ))tanh

Existe alguma maneira de combinar esses fatos para obter um limite superior na dimensão VC ? Há algo a dizer sobre que atenda aos critérios de (2)?f(z)

Josephine Moeller
fonte
Eu pareço estar entendendo mal alguma coisa. Se a função for fixa, cada faixa será determinada exclusivamente pelo ângulo de rotação em torno do eixo . Você acaba basicamente tentando quebrar intervalos circulares com pontos. O que estou perdendo? A função ser diferente para diferentes faixas? z ffzf
James King
1
Boa pergunta. Sim, pode ser diferente. Conforme observado na resposta abaixo, você deve ter cuidado com , mas pode pertencer a uma família de funções. Como no exemplo acima, pode pertencer à família de funções . f f f tanh ( α ( z - β ) )fffftanh(α(zβ))
Josephine Moeller

Respostas:

4

Você precisa da restrição sigmóide em para que a dimensão VC seja finita. Caso contrário, você pode deixar comportar como uma escada, com arbitrariamente muitos passos. Então essas escadas podem ter arbitrariamente muitos cruzamentos. Isso permite que intervalos admitam subconjuntos diferentes. f n 2 nffn2n

Se for um polinômio, você poderá vincular a dimensão VC usando o grau do polinômio (combinado com o grau do polinômio (2) que descreve o disco). Mas não sei como aplicar esse tipo de resultado para .tanhf(z)tanh

Jeff Phillips
fonte
Direita. Se você possui um polinômio pode usar o limite descrito em Matousek. Mas um transcendental coloca problemas a esse respeito. f ( t )f(t)f(t)
Josephine Moeller
1
Há algum trabalho sobre estruturas / teoria o-minimal que tenta lidar com essas coisas. en.wikipedia.org/wiki/O-minimal_theory#Examples
Sariel Har-Peled
@Sariel: Você está dizendo que isso seria uma maneira, por exemplo, de definir algum tipo de elevação para um espaço construído a partir de funções transcendentais das coordenadas, em vez de polinomiais? Porque as funções hiperbólicas são pfaffianas?
Josephine Moeller
Bem. É uma extensão da complexidade algébrica constante. Pode ser remotamente relevante - eu sinceramente não sei.
Sariel Har-Peled