Une question d'apprentissage paritaire

Définissons une classe de fonctions sur un ensemble de bits. Fixons deux distributions p , q qui sont "raisonnablement" différentes l'une de l'autre (si vous le souhaitez, leur distance variationnelle est au moins $n$$p, q$$\epsilon$ , ou quelque chose de similaire).

Maintenant, chaque fonction de cette classe est définie par une collection de k indices S , et est évaluée comme suit: Si la parité des bits sélectionnés est 0, retourne un échantillon aléatoire de p , sinon retourne un échantillon aléatoire de $f$$k$$S$$p$$q$ .

Problème : Supposons que l'on me donne un accès Oracle à certains de cette classe, et bien que je connaisse ϵ (ou une autre mesure de distance), je ne connais pas p et q .$f$$\epsilon$$p$$q$

Y a-t-il des limites sur le nombre d'appels que je dois faire pour PAC-learn ? Vraisemblablement, ma réponse sera en termes de n , k et ϵ .$f$$n, k$$\epsilon$

Remarque : je n'ai pas spécifié le domaine de sortie. Encore une fois, je suis flexible, mais pour l'instant, disons que et q sont définis sur un domaine fini [ 1 .. M ] . En général, je serais également intéressé par le cas où ils sont définis sur R (par exemple, s'ils sont gaussiens)$p$$q$$[1..M]$${\mathbb R}$

La discussion dans les commentaires ci-dessous indique que j'ai mal compris la question. Ma réponse est basée sur le fait que l'Oracle ne prend aucune entrée et retourne $(x, f(x))$ où ou $x \sim p$ ,fonction f ∈ F . Ce n'est apparemment pas ce qui est demandé.$x \sim q$$f \in F$

Étant donné que la distribution cible est fixe pour chaque cible , la limite supérieure de l'échantillon PAC s'applique (cela découle du fait que la distribution cible pour cette limite peut même dépendre complètement de f ∗ ). Par conséquent, m ≤ ˜ O ( $f^* \in F$$f^*$ exemples ϵ (VC(F)+log(1/δ)))devraient suffire pour trouver une hypothèse d'erreur≤ϵwp≥1-δ. Remarque - après avoir vu ces exemples, il faut trouver une hypothèse cohérente à partir deF, et cela peut ne pas être traitable.

D'un autre côté, on peut obtenir une borne inférieure presque identique même pour le cas de , la distribution uniforme, où m ≥ $p=q=U$$m \ge \Omega(\mathrm{VC}(F))$ exemples sont encore nécessaires (cela peut être légèrement amélioré) .

La distance variationnelle entre et$p$ , ainsi que k peut jouer un rôle dans le petit écart entre ces bornes, mais j'en doute.$q$$k$