Existe uma grande literatura sobre "teste de propriedade" - o problema de fazer um pequeno número de consultas de caixa preta em uma função para distinguir entre dois casos:
é membro de alguma classe de funções
é de todas as funções da classe .C
O intervalo da função às vezes é booleano: , mas nem sempre.
Aqui, é geralmente considerado como distância de Hamming: a fração dos pontos de que precisariam ser alterados para colocar na classe . Essa é uma métrica natural se tiver um intervalo booleano, mas parecerá menos natural se o intervalo for de valor real.f f C f
Minha pergunta: existe um fio da literatura de teste de propriedades que testa a proximidade de alguma classe com relação a outras métricas?
Geralmente não é chamado de teste de propriedade (e realmente não é), mas há um grande trabalho sobre a decisão de propriedades de uma matriz observando um menor menor induzido. Isso é muito semelhante ao objetivo no teste de propriedades. Veja, por exemplo, o artigo de Rudelson e Vershynin:
http://portal.acm.org/citation.cfm?id=1255449
Existem artigos anteriores de Frieze-Kannan. O ponto é que geralmente a métrica que eles usam é alguma norma matricial, como norma espectral, norma de frobenius ou norma de corte. Se desejar, você pode pensar em alguns desses resultados como algoritmos de teste de propriedades em uma métrica diferente da distância de Hamming.
fonte
O trabalho de Berman, Raskhodnikova e Yaroslavtsev [1] introduz o teste das funções com relação às distâncias , para . Destina-se a capturar situações em que a magnitude do ruído é o que importa (em vez da distância mais frágil de Hamming). (Alguns resultados referentes às distâncias também podem ser encontrados em [2]).L p p ≥ 1 L pf:[n]d→R Lp p≥1 Lp
Veja, por exemplo, o Capítulo 12 (Seção 12.4) da Introdução aos testes de propriedades de Goldreich para uma discussão sobre os testes em relação à edição e distância .Lp
(Observe que o teste não é o mesmo que o teste de distribuição (normalmente em relação a / variação total), pois (i) o teste do objeto não é o mesmo (funciona com distribuições de probabilidade), (ii) o tipo de acesso é diferente ( consulta versus amostra, geralmente) e (iii) a distância conforme definida em [1] é normalizada (por ) para problemas de dimensionamento e não está em teste de distribuição (como a massa é sempre por definição) .L 1 L 1 n 1L1 L1 L1 n 1
[1] Teste . Berman, Raskhodnikova e Yaroslavtsev, STOC'14.Lp
[2] Testando monotonicidadek . Canonne, Grigorescu, Guo, Kumar e Wimmer, ITCS'17.
fonte