Una pregunta de aprendizaje de paridad

10

Definamos una clase de funciones sobre un conjunto de bits. Arregle dos distribuciones p , q que sean "razonablemente" diferentes entre sí (si lo desea, su distancia de variación es al menos ϵ , o algo similar).np,qϵ

Ahora cada función en esta clase se define mediante una colección de k índices S , y se evalúa de la siguiente manera: si la paridad de los bits seleccionados es 0, devuelve una muestra aleatoria de p , de lo contrario devuelve una muestra aleatoria de q .fkSpq

Problema : Supongamos que soy dado acceso a algún oráculo de esta clase, y aunque sé que ε (o alguna otra medida de distancia), no sé p y q .fϵpq

¿Hay algún límite en la cantidad de llamadas que debo hacer a PAC-learn ? Presumiblemente mi respuesta será en términos de n , k y ϵ .fn,kϵ

Nota : no especifiqué el dominio de salida. Una vez más, soy flexible, pero por ahora vamos a decir que y q se definen sobre un dominio finito [ 1 .. M ] . En general, también me interesaría el caso cuando se definen sobre R (por ejemplo, si son gaussianos)pq[1..M]R

Suresh Venkat
fuente
No estoy seguro de entender el modelo. ¿Qué especificas en una llamada de oráculo? ¿Los ejemplos siempre se extraen de la distribución especificada por el objetivo?
Lev Reyzin
1
En una llamada al oráculo, invocas f () y devuelve un valor.
Suresh Venkat
Entonces, dependiendo de la función objetivo , ¿ p o q siempre se usa para generar ejemplos? (Supongo que estás aprendiendo pac clase F. )fFpqF
Lev Reyzin
Si, eso es correcto. el problema es aprender cuál (o aprender el bit de paridad que se usa)
Suresh Venkat
2
No estoy seguro de cómo adaptar el modelo PAC a este modelo. Pero parece que es suficiente para poder distinguir de q con probabilidad 1 - 1 / ( 2 k ) y luego puede obtener los valores f ( x ) para k linealmente independiente x y usar la eliminación gaussiana para encontrar f (ya que f es lineal). distinguir dos gaussianos bien separados será fácil, por ejemplo. pq11/(2k)f(x)kxff
Sasho Nikolov

Respuestas:

6

La discusión en los comentarios a continuación indica que he entendido mal la pregunta. Mi respuesta se basa en la Oracle tomar ninguna entrada y devolver , donde x ~ p o x ~ q , en función de f F . Aparentemente, esto no es lo que se pregunta.(x,f(x))xpxqfF


Debido a que la distribución objetivo es fija para cada objetivo , se aplica el límite superior de la muestra PAC (esto se deduce del hecho de que la distribución objetivo para este límite puede incluso depender completamente de f ). Por lo tanto, m ˜ O ( 1fFf ejemplos ϵ (VC(F)+log(1/δ)))deberían ser suficientes para encontrar una hipótesis de errorϵwp1-δ. Nota: después de ver estos ejemplos, uno necesita encontrar una hipótesis consistente deF, y esto puede no ser manejable.

mO~(1ϵ(VC(F)+log(1/δ)))
ϵ1δF

Por otro lado, se puede obtener un límite inferior casi coincidente incluso para el caso de , la distribución uniforme, donde aún se requieren ejemplos de m Ω ( V C ( F ) ) (esto se puede mejorar ligeramente) .p=q=UmΩ(VC(F))

La distancia variacional entre y q , así como k puede jugar un papel en la pequeña brecha entre estos límites, pero lo dudo.pqk

Lev Reyzin
fuente
El entorno típico de aprendizaje PAC tiene un oráculo que extrae una muestra x de la distribución D y devuelve ( x , f ( x ) ) . Esta no es la configuración descrita en la pregunta de Suresh o en la publicación del blog que la inspiró:bit.ly/YtwdST. En ambos, el oráculoesla función f , y el alumno es libre de enviar cualquier elemento del conjunto de instancias (cadenas de bits de longitud n(f,D)xD(x,f(x))fn) Lev, ¿tu respuesta supone un oráculo del primer tipo o del segundo tipo? Si es el segundo tipo, ¿seguimos hablando de aprendizaje PAC?
Keki Burjorjee
1
Veo. En PAC, el "oráculo" por lo general se considera como un botón que devuelve , donde x ~ D . El Oracle que usted describe se llama "consulta de membresía" para f . Mi respuesta solo se aplica a la primera. Si solo realiza consultas de membresía, ¿cómo puede encontrar información sobre(x,f(x))xDf o q utilizando el marco de Suresh? Digamos p = q por simplicidad. pqp=q
Lev Reyzin
Gracias por esa aclaración. Entonces, en el caso que describió Suresh, el oráculo de "consulta de membresía" funciona de la siguiente manera (supongo que ha puesto esta entidad entre comillas porque el oráculo puede devolver un valor real, no solo un booleano es-un-miembro / no-a- respuesta del miembro): si la paridad de los atributos efectivos es 1, el resultado devuelto se extrae de la distribución . De lo contrario, el resultado se extrae de la distribución q . Hay una arruga adicional. El oráculo recuerda todas sus respuestas anteriores y las devuelve si se consulta con la misma entrada. En otras palabras, es determinista. pq
Keki Burjorjee
1
No entiendo. Si el oráculo es simplemente una función y lo consulta dándole x , ¿no devuelve simplemente f ( x )FXF(X) ? ¿Cómo entra en juego o q si el alumno genera x él mismo? Creo que no he entendido este punto básico todo el tiempo ...pagqX
Lev Reyzin
Para y q =p=N(+0.25,1)q=N(0.25,1)def fitness() ...random_number_generator.set_seed(x)