¿Las muestras de entrenamiento extraídas aleatoriamente para el entrenamiento de mini-lotes de redes neuronales deben ser extraídas sin reemplazo?

Question

Definimos una época como el hecho de haber pasado por la totalidad de las muestras de entrenamiento disponibles, y el tamaño del mini lote como el número de muestras sobre las que se hace la media para encontrar las actualizaciones de pesos/bases necesarias para descender el gradiente.

Mi pregunta es si debemos extraer sin reemplazo del conjunto de ejemplos de entrenamiento para generar cada minilote dentro de una época. Creo que deberíamos evitar el reemplazo para asegurarnos de que realmente "extraemos todas las muestras" para cumplir con el requisito de final de época, pero estoy teniendo problemas para encontrar una respuesta definitiva de una manera u otra.

He intentado buscar en Google y leer el capítulo 1 del libro de Nielsen Redes neuronales y aprendizaje profundo pero no he encontrado una respuesta clara. En ese texto Nielsen no especifica que el muestreo aleatorio se haga sin reemplazo, pero parece dar a entender que sí.

Si lo desea, puede encontrar aquí una formalización más clara de la formación en épocas - https://stats.stackexchange.com/a/141265/131630

Editar: esta pregunta me parecía similar pero no estaba claro cómo aplicar el hecho de que la linealidad de la expectativa es indiferente a la independencia a esta situación - El muestreo debe realizarse con o sin sustitución

Answer 1

Se puede encontrar un buen análisis teórico de los esquemas con y sin reemplazo en el contexto de los algoritmos iterativos basados en sorteos aleatorios (que es como se entrenan muchas redes neuronales profundas (DNN) discriminativas) aquí

En resumen, resulta que el muestreo sin reemplazo, conduce a una convergencia más rápida que el muestreo con de reemplazo.

Aquí haré un breve análisis basado en el ejemplo del juguete que proporcionan: Digamos que queremos optimizar la siguiente función objetivo:

$$ x_{\text{opt}} = \underset{x}{\arg\min} \frac{1}{2} \sum_{i=1}^{N}(x - y_i)^2 $$

donde el objetivo $y_i \sim \mathcal{N}(\mu, \sigma^2)$ . En este ejemplo, estamos tratando de resolver el óptimo $x$ , dado $N$ etiquetas de $y_i$ obviamente.

Bien, entonces si resolviéramos el óptimo $x$ en lo anterior directamente, entonces tomaríamos la derivada de la función de pérdida aquí, la pondríamos a 0, y resolveríamos para $x$ . Así que para nuestro ejemplo anterior, la pérdida es

$$L = \frac{1}{2} \sum_{i=1}^{N}(x - y_i)^2$$

y su primera derivada sería:

$$ \frac{\delta L}{\delta x} = \sum_{i=1}^{N}(x - y_i)$$

Configurar $ \frac{\delta L}{\delta x}$ a 0 y resolviendo para $x$ , rinde:

$$ x_{\text{opt}} = \frac{1}{N} \sum_{i=1}^{N} y_i $$

En otras palabras, la solución óptima no es más que la media muestral de todas las $N$ muestras de $y$ .

Ahora bien, si no pudiéramos realizar el cálculo anterior de una sola vez, tendríamos que hacerlo recursivamente, a través de la ecuación de actualización del descenso de gradiente que aparece a continuación:

$$ x_i = x_{i-1} - \lambda_i \nabla(f(x_{i-1})) $$

y simplemente insertando nuestros términos aquí se obtiene:

$$ x_{i} = x_{i-1} - \lambda_i (x_{i-1} - y_{i}) $$

Si ejecutamos lo anterior para todos los $i \in {1, 2, ... N}$ entonces estamos realizando efectivamente esta actualización sin de reemplazo. La pregunta entonces es, ¿podemos obtener también el valor óptimo de $x$ de esta manera? (Recuerde que el valor óptimo de $x$ no es más que la media muestral de $y$ ). La respuesta es sí, si se deja $\lambda_i = 1/i$ . A ver, esto lo ampliamos:

$$ x_{i} = x_{i-1} - \lambda_i (x_{i-1} - y_{i}) \\\ x_{i} = x_{i-1} - \frac{1}{i} (x_{i-1} - y_{i}) \\\ x_{i} = \frac{i x_{i-1} - (x_{i-1} - y_{i})}{i} \\\ x_{i} = \frac{(i - 1)x_{i-1} + y_{i}}{i} \\\ i x_{i} = (i - 1)x_{i-1} + y_{i} \\\ $$

Sin embargo, la última ecuación no es más que la fórmula de la media móvil. Así, al recorrer el conjunto de $i=1$ , $i=2$ etc., hasta llegar a $i=N$ habríamos realizado nuestras actualizaciones sin de reemplazo, y nuestra fórmula de actualización nos da la solución óptima de $x$ que es la media de la muestra.

$$ N x_{N} = (N - 1)x_{N-1} + y_{N} ==> x_N = \frac{1}{N}\sum_{i=1}^{N} y_i = \mu $$

Sin embargo, si realmente dibujamos con sustitución, entonces mientras nuestros sorteos serían realmente independientes, el valor optimizado $x_N$ sería diferente de la media (óptima) $\mu$ y el error al cuadrado vendría dado por:

$$ \mathop{E}\{(x_N - \mu)^2\} $$

que va a ser un valor positivo, y este sencillo ejemplo de juguete se puede extender a dimensiones más altas. Esto tiene como consecuencia que queramos realizar un muestreo sin reemplazo como solución más óptima.

Espero que esto lo aclare un poco más.

Answer 2

Según el código del repositorio de Nielsen, los minilotes se dibujan sin reemplazo:

    def SGD(self, training_data, epochs, mini_batch_size, eta, test_data=None):
    n = len(training_data)
    for j in range(epochs):
            random.shuffle(training_data)
            mini_batches = [
                training_data[k:k+mini_batch_size]
                for k in range(0, n, mini_batch_size)
            ]
            for mini_batch in mini_batches:
                self.update_mini_batch(mini_batch, eta)

Podemos ver que no hay sustitución de muestras de entrenamiento dentro de una época. Curiosamente, también podemos ver que Nielsen opta por no preocuparse de ajustar eta (la tasa de aprendizaje) para el último tamaño del mini lote, que puede no tener tantas muestras de entrenamiento como los mini lotes anteriores. Es de suponer que esta es una modificación avanzada que deja para capítulos posteriores.**

** EDIT: En realidad, este escalamiento se produce en el def update_mini_batch función. Por ejemplo, con los pesos:

self.weights = [w-(eta/len(mini_batch))*nw for w, nw in zip(self.weights, nabla_w)]     

Esto es necesario porque el último minilote puede ser más pequeño que los minilotes anteriores si el número de muestras de entrenamiento por minilote no se divide uniformemente en el número total de muestras de entrenamiento disponibles.

mylist = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
n = len(mylist)
mini_batch_size = 2
mini_batches = [
    mylist[k:k+mini_batch_size]
    for k in range(0, n, mini_batch_size)
    ]
for mini_batch in mini_batches:
    print(mini_batch)

La salida:

['1', '2']
['3', '4']
['5', '6']
['7', '8']
['9', '10']

Cambiar mini_batch_size a 3 que no se divide uniformemente en nuestras 10 muestras de entrenamiento. Para la salida obtenemos:

['1', '2', '3']
['4', '5', '6']
['7', '8', '9']
['10']

Cuando se evalúa un rango sobre índices de lista (algo de la forma [x:y] donde x y y son algunos índices de la lista), si nuestro valor a la derecha excede la longitud de la lista, python simplemente devuelve los elementos de la lista hasta que el valor salga del rango del índice.

Por lo tanto, el último minilote puede ser más pequeño que los minilotes anteriores, pero si se pondera por el mismo eta entonces esas muestras de entrenamiento contribuirán más al aprendizaje que las muestras de los otros mini lotes más grandes. Dado que se trata sólo del último minilote, probablemente no merezca la pena preocuparse demasiado, pero puede resolverse fácilmente escalando eta a la longitud del mini lote.

Answer 3

Me ha encantado tu pregunta porque he encontrado exactamente el mismo problema. Nadie indica explícitamente si es con o sin reemplazo. Basándome en mi propia lógica, tiene que ser con reemplazo ya que una época debería contener todas las muestras de entrenamiento (por definición) y la siguiente expresión queda al entrenar una NN (por ejemplo en Keras):

$$ i = \lceil s / b \rceil$$

donde:

$i$ : Número de iteraciones por época

$s$ : Número de muestras en el conjunto de datos

$b$ (mini) Tamaño del lote

En caso contrario, habría que cambiar la definición de época por una más genérica.