Existe una gran literatura sobre "pruebas de propiedad": el problema de realizar una pequeña cantidad de consultas de recuadro negro a una función para distinguir entre dos casos:
es miembro de alguna clase de funciones C
es ε -lejos de cada función en la clase C .
El rango de la función es a veces booleano: R = { 0 , 1 } , pero no siempre.
Aquí, -lejos se toma generalmente para significar Hamming distancia: la fracción de puntos de f que tendrían que ser cambiado con el fin de lugar f en la clase C . Esta es una métrica natural si f tiene un rango booleano, pero parece menos natural si el rango tiene un valor real.
Mi pregunta: ¿existe un hilo de la literatura de pruebas de propiedad que prueba la cercanía a alguna clase con respecto a otras métricas?
Por lo general, no se llama prueba de propiedad (y realmente no lo es), pero hay una gran cantidad de trabajo para decidir las propiedades de una matriz al observar un pequeño inducido menor. Esto es muy similar al objetivo en las pruebas de propiedad. Ver, por ejemplo, el artículo de Rudelson y Vershynin:
http://portal.acm.org/citation.cfm?id=1255449
Hay documentos anteriores de Frieze-Kannan. El punto es que, por lo general, la métrica que usan es alguna norma de matriz, como la norma espectral, la norma frobenius o la norma de corte. Si lo desea, puede pensar en algunos de estos resultados como algoritmos de prueba de propiedades en una métrica que no sea la distancia de Hamming.
fuente
fuente