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).
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 .
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 .
¿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 ϵ .
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)
fuente
Respuestas:
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)) x∼p x∼q f∈F
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 ( 1f∗∈F f∗
ejemplos ϵ (VC(F)+log(1/δ)))deberían ser suficientes para encontrar una hipótesis de error≤ϵwp≥1-δ. Nota: después de ver estos ejemplos, uno necesita encontrar una hipótesis consistente deF, y esto puede no ser manejable.
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=U m≥Ω(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.p q k
fuente
def fitness() ...
random_number_generator.set_seed(x)