En el aprendizaje computacional, el teorema de la NFL establece que no existe un alumno universal. Para cada algoritmo de aprendizaje, hay una distribución que hace que el alumno emite una hipotesis con un gran error, con alta probabilidad (aunque hay una hipotesis de bajo error). La conclusión es que para aprender, la clase de hipotesis o las distribuciones deben estar restringidas. En su libro "Una teoría probabilística del reconocimiento de patrones", Devroye et al prueban el siguiente teorema para el alumno vecino más cercano a K:
Assume μ has a density. if k→∞ and k/n→0 then for every ϵ>0, there's N, s.t. for all n>N:P(Rn−R∗>ϵ)<2exp(−Cdnϵ2)
DondeR∗ es el error de la regla óptima de bayes, Rn es el verdadero error de la salida K-NN (el la probabilidad es superior al conjunto de entrenamiento de tamañon ),μ es la medida de probabilidad en el espacio de instanciaRd yCdEsta constante depende solo de la dimensión euclidiana. Por lo tanto, podemos acercarnos tanto como queramos a la mejor hipótesis que existe (no la mejor en alguna clase restringida), sin hacer ninguna suposición sobre la distribución. ¿Entonces estoy tratando de entender cómo este resultado no contradice el teorema de la NFL? ¡Gracias!