¿Modelos discriminativos overfit más modelos generativos?

Question

En una entrevista, el entrevistador dijo que discriminativo modelos tienden a overfit más de los modelos generativos, ya que resolver más de un problema complejo y, por tanto, consumen más recursos (o parámetros) de hacerlo. Para las definiciones de discriminación y modelos generativos, puede ess este post Generativo vs discriminativo

Pensé que era más parámetros llevaría a sobreajuste pero aquí la lógica se invierte. Alguna idea?

Answer 1

Este es un divertido pregunta ya que proporciona una buena contexto de por qué la utiliza a menudo heurística que más parámetros de $\implies$ más de riesgo de sobreajuste es sólo eso, una heurística. Para conectar a tierra la discusión, vamos a considerar lo que es, en cierto sentido, la más simple problema de clasificación binaria. Como ejemplo vamos a tomar el canónica generativo-discriminativo par de naive Bayes y de regresión logística, respectivamente. Es importante que nos fijamos en pares correspondientes de esta manera. De lo contrario, lo que hemos de decir es que va a ser inútil. Ciertamente podríamos llegar con extraordinariamente flexible modelos generativos (imagine que sustituye el factor condicional $p(x|y)$ en naive Bayes con algo como funciones delta), que en esencia siempre overfit.

Primero debemos definir lo que entendemos por el sobreajuste. Una definición útil de sobreajuste implica derivados apretado probabilística de los límites en la generalización de error basado en el conjunto de entrenamiento de error y el tipo de clasificadores que estamos usando. En este caso un parámetro relevante es la VC de la dimensión de la hipótesis de clase $H$ (el conjunto de los clasificadores utilizados). Simplemente ponga la VC de la dimensión de una hipótesis de clase está dado por el mayor conjunto de ejemplos tales que para cualquier posible etiquetado de ese conjunto, existe una $h \in H$ el cual puede etiquetar en exactamente de esa manera. Así que, dado que $m$ ejemplos de una clasificación binaria de configuración hay $2^m$ maneras a la etiqueta. Si existe algún conjunto de $m$ ejemplo, y para cada una de las $2^m$ posibles formas de etiquetado hay algunos $h \in H$ que las etiquetas correctamente, podemos concluir $\text{VCdim}(H) \ge m$. Además podemos decir que el conjunto de $m$ puntos es destrozado por $H$.

En resulta que Bayes naive de regresión logística y ambos tienen la misma dimensión VC, ya que ambos clasificar ejemplos en $n$ dimensiones utilizando un $n$ dimensiones hyperplane. La VC de la dimensión de una $n$ dimensiones hyperplane es $n+1$. Usted puede mostrar esta por la parte superior-la delimitación de la VC dimensión mediante Randon del Teorema y, a continuación, dar un ejemplo de un conjunto de $n+1$ puntos que se rompió. Además, en este caso a nuestra intuición de baja dimensionalidad ejemplos generaliza a dimensiones superiores y podemos hacer fotos bonitas.

En este sentido, ambos son igualmente probables overfit porque nosotros en general obtendrá similar límites en la generalización. Esto también explica por qué 1 vecino más cercano es el rey de sobreajuste, ha infinito VC dimensión debido a que se rompe cada conjunto de ejemplos. Este no es el final de la historia, aunque.

Otra forma útil para definir formalmente el sobreajuste se basa en la obtención de la generalización de los límites en términos de la mejor predictor en la hipótesis de clase, es decir, la hipótesis de que todos estamos de acuerdo que es mejor si tuviéramos un número infinito de ejemplos. Aquí, las cosas se ven diferentes para el naive Bayes/regresión logística comparación. La primera cosa a tener en cuenta es que debido a la forma naive Bayes es parametrizada (que necesitan para especificar válido condicionales, suma a 1, etc), no se nos garantiza la convergencia en la óptima clasificador lineal, incluso teniendo en cuenta un número infinito de ejemplos. Por otro lado, la regresión logística se. Así que podemos concluir que, de hecho, el conjunto de todos los Bayes naive de los clasificadores es un subconjunto de todos los de regresión logística de los clasificadores. Esto proporciona cierta evidencia de que, efectivamente, Bayes naive de los clasificadores pueden ser menos propensos a overfit en este sentido, simplemente porque son menos poderosos/más limitadas. De hecho, este es el caso. En definitiva, si estamos realizando la clasificación en $n$ dimensiones del espacio, naive Bayes requiere en el orden de $O(\log n)$ muestras a converger whp a la mejor clasificador naive Bayes. La regresión logística requiere en el orden de $O(n)$. Para una referencia para este resultado ver En Discriminativo vs Generativo de los clasificadores por Ng y Jordania.

Answer 2

Un modelo generativo es típicamente de sobreajuste menos porque permite que el usuario ponga en más de lado la información en el formulario de clase de las oraciones condicionales.

Considere la posibilidad de un modelo generativo $p(c|x) = p(c)p(x|c)$. Si la clase condicionales son mulitvariate normales compartida de covarianza, esto tendrá un lineal de la decisión de la frontera. Así, el modelo por sí mismo es tan potente como un SVM lineal o regresión logística.

Sin embargo, una discriminativo clasificador es mucho más libre en la elección de decisión, función: sólo tiene que encontrar un adecuado hyperplane. El generativa clasificador sin embargo se necesita mucho menos muestras de encontrar buenos parámetros si los supuestos son válidos.

Lo siento, es más bien handwavy y no hay ningún disco duro de matemáticas detrás de él. Pero es una intuición.