Cuando aumentamos la cantidad de datos de entrenamiento en el algoritmo KNN, ¿por qué se reduce la tasa de error?

Analicemos esto desde un marco teórico probabilístico.

Supongamos que X representa la entrada e Y representa su salida correspondiente. Supongamos que hay una distribución de probabilidad subyacente P ( X , Y ) que genera nuestra entrada y salida.

Nuestro objetivo en la inclinación de la máquina es aprender una transformación que toma una entrada y la asigna a una predicción Y * . En general, esperamos que Y * esté tan cerca de Y (el verdadero valor que queremos obtener) como sea posible con respecto a alguna función de pérdida. Si consideramos que nuestra función de pérdida es un error cuadrático medio (una función de pérdida muy popular y útil en el aprendizaje automático), podemos derivar la elección óptima de Y * para que sea E [Y | X] . Esta opción de predicción minimiza nuestra pérdida en promedio. Esto tiene sentido intuitivamente: dada una entrada X , tomamos el promedio de la salida. En un gran número de entradas, minimizamos nuestro error / pérdida en promedio.

Ahora podría estar pensando: ¿cómo sabemos qué es P ( X , Y )? En general, no tendrá esta información y, por lo tanto, no podrá calcular directamente E [Y | X] . Aunque los resultados anteriores ofrecen ideas interesantes, especialmente con respecto a KNN. Podemos ver que KNN se aproxima al Y * óptimo = E [Y | X]. ¿Cómo es eso? Pensemos en cómo funciona KNN. Dada una entrada X , tomamos los K vecinos más similares en nuestro conjunto de entrenamiento y tomamos el promedio (o tomamos un voto mayoritario) de sus resultados para obtener Y * . Ver la correspondencia? Ahora pensemos en tu pregunta original. A medida que aumentamos los datos de entrenamiento, la tasa de error parece disminuir en general. Bien, adivine qué, con más datos obtenemos una mejor aproximación de E [Y | X] para una entrada dada X. Esto corresponde a una disminución en el error en general porque de nuestra discusión teórica esta elección óptima minimiza nuestra pérdida en promedio. Con más datos, obtenemos predicciones más precisas.

* Nota: Trevor Hastie, Robert Tibshirani y Jerome Friedman discuten en detalle el Capítulo 2 de Los elementos del aprendizaje estadístico .

Primero, veamos el principio básico de KNN:

Dos observaciones con una entrada similar tendrán una salida similar.

Para aprovechar eso, cuando vemos una nueva observación, encontramos el ejemplo de entrenamiento más cercano y utilizamos la salida correcta para ese punto de datos como la salida para este.

Si tiene más datos de entrenamiento, el “vecino más cercano” probablemente esté más cerca (lo que significa que la entrada es aún más similar). Una entrada más similar significa, en teoría, una salida más similar.

Para un ejemplo extremo, imagine usar solo 5 ejemplos de entrenamiento. Puedes ver por qué eso no será muy bueno incluso para un problema bastante simple. Ahora imagina que tienes 5000 ejemplos …

Esto es cierto no solo para KNN, sino para todos los algoritmos de aprendizaje automático. Se cree que el algoritmo que tiene más datos gana. En pocas palabras, cuando proporciona más datos, la granularidad del espacio muestral se vuelve más fina. Esas son las distancias que Euclidean, la Norma L1 o Manhattan se hacen en una escala mucho más baja que evita errores.

Por ejemplo, supongamos que tenemos dos muestras etiquetadas con A y B. La distancia entre ellas es de 10 unidades. Sin embargo, cuando proporcionamos más muestras, obtenemos A, B, C y D con distancias de 0.5 unidades. Esto es mucho más preciso. ¿No es así?

Valores atípicos:

Si contempla un poco las palabras atípicas, descubrirá por qué se necesitan más muestras para la capacitación. Un valor atípico es una muestra que está muy lejos en un sistema de coordenadas cartesianas de cualquier otra muestra.

Si agrega más muestras, es más probable que llene el vacío y reduzca la aparición de valores atípicos.

Sobreajuste:

Sin embargo, debe tener cuidado de no caer en la trampa de ajuste excesivo que puede ocurrir al obtener una precisión del 100% para el entrenamiento.

Validación cruzada:

La validación cruzada y el plegado en k son la técnica más común para manejar este dilema.

Lo diré un poco diferente, usando regresión lineal. Imagine que las muestras de entrenamiento se muestrean a partir de una función continua:

[matemáticas] y = f (x) [/ matemáticas]

El objetivo es aproximar esa función a partir de ejemplos de capacitación porque en realidad, para problemas complejos, no tendrá acceso a [matemáticas] f (x) [/ matemáticas] sino a los ejemplos. Entonces, KNN tiene un conjunto de ejemplos de entrenamiento que contienen los puntos de datos que consisten en pares de entrada / salida.

[matemáticas] S_ {tren} = [(x_1, y_1), (x_2, y_2),…, (x_n, y_n)] [/ matemáticas]

Por lo tanto, se aproxima a [math] f () [/ math] con [math] g () [/ math] como

[matemáticas] g (x) = \ sum_ {i} ^ {K} \ alpha_ {i} y_ {i} [/ matemáticas]

donde las y están emparejadas con los K vecinos más cercanos a la entrada de consulta [math] x [/ math]. Y el [math] \ alpha [/ math] representa los coeficientes de ponderación inversamente proporcionales a las distancias respectivas desde el punto de consulta.

Por lo tanto, la precisión de [math] g () [/ math] es mayor cuanto más puntos de datos existan. Si visualiza [math] f () [/ math] y [math] g () [/ math] como superficies, entonces [math] g () [/ math] es una versión de muestra de [math] f () [/ matemáticas] . Para mejorar la suavidad de [math] g () [/ math] necesitamos aumentar la frecuencia de muestreo, que es análoga a aumentar los puntos de datos en el ejemplo de entrenamiento.

El muestreo del curso, correspondiente a un conjunto pequeño [matemática] S_ {tren} [/ matemática] puede causar alias (baja precisión) al igual que en el muestreo de imágenes con baja frecuencia.

Espero que esto ayude.

KNN realmente solo está implementando una función de los datos de entrenamiento. La etapa de “aprendizaje” en realidad no es realmente aprender. Produce y mirando a los vecinos x en el conjunto de datos. Entonces, cuántos vecinos puede ver es realmente lo que importa …

KNN es un algoritmo de aproximación local, y cuantos más datos de entrenamiento tenemos, más se caracteriza nuestra aproximación local.

Si piensa en cómo funciona KNN, puede comprender fácilmente por qué. Considere el caso donde K = 1, entonces KNN clasifica un nuevo punto asumiendo que puntos similares (es decir, cerca uno del otro) tienen la misma clase y, por lo tanto, asigna al nuevo punto la misma clase que el punto más cercano en el conjunto de entrenamiento. Pero, ¿qué sucede si no tiene puntos en el conjunto de entrenamiento que estén cerca del que desea clasificar? Bueno, entonces el más cercano podría estar lejos, y la aproximación local se debilita. Cuantos más puntos de entrenamiento tenga, es menos probable que esto suceda

Encontré estas imágenes en línea que podrían ayudar a visualizar el problema.