Siempre encuentro este término cuando leo sobre el aprendizaje por refuerzo, por ejemplo en esta oración:
Si el problema se modela con cuidado, algunos algoritmos de aprendizaje por refuerzo pueden converger al óptimo global
http://reinforcementlearning.ai-depot.com/
o aquí:
Para cualquier política fija Pi, se ha demostrado que el algoritmo TD descrito anteriormente converge a VPi
http://webdocs.cs.ualberta.ca/~sutton/book/ebook/node62.html
Mi comprensión de la palabra converger es que significa que varias cosas se unen en el mismo punto, pero ¿cómo puede hacer eso una sola cosa (el algoritmo)?
algorithms
machine-learning
estrella de mar
fuente
fuente
Respuestas:
Se dice que un algoritmo iterativo converge cuando, a medida que avanzan las iteraciones, la salida se acerca cada vez más a algún valor específico. Más precisamente, no importa cuán pequeño sea el rango de error que elija, si continúa lo suficiente, la función eventualmente se mantendrá dentro de ese rango de error alrededor del valor final.
En algunas circunstancias, un algoritmo no convergerá, teniendo una salida que siempre varía en cierta cantidad. Incluso podría divergir, donde su producción experimentará cambios de valor cada vez mayores, sin acercarse nunca a un resultado útil. Más precisamente, no importa cuánto tiempo continúe, el valor de la función nunca se establecerá dentro de un rango de cualquier valor "final".
La frase "converger a un óptimo global" en su primera oración es una referencia a algoritmos que pueden converger, pero no al valor "óptimo" (por ejemplo, un algoritmo de escalada que, dependiendo de la función y las condiciones iniciales, puede converger a un máximo local, que nunca alcanza el máximo global).
fuente
¿Qué es la convergencia, en general?
El concepto de convergencia es un término matemático bien definido. Esencialmente significa que "eventualmente" una secuencia de elementos se acerca cada vez más a un solo valor. Llamamos a este valor único el "límite".
La definición formal es algo así:
Dada la secuencia (infinita) de números reales
X0, X1, X2, ... Xn ..., decimos queXn converges to a given number Lsi por cada error positivo que usted piensa, existe unXmelemento tal que cada elementoXnque viene despuésXmdifiereLen menos de ese error.Ejemplo:
Imagine una secuencia como tal:
¿Xn converge a cero? ¡Si! ¿Por qué?
Piense en un error E (por ejemplo,
E = 0.0025). ¿Hay un elemento en la secuencia que después de eso cada elemento esté debajo0.025? ¡Si! Ese elemento esX3 = 0.001. Después de X2, todoXNestá debajo0.0025. ¿Se puede hacer esto para cada E> 0? Si. Por cada error positivo que elijamos, podemos ver cuántos ceros tiene antes de su primer punto decimal y la secuencia será menor que a partir del elemento que tiene el mismo número de ceros.Esto significa que
Xn = 1/(10^5) converges to 0. Como en "puede acercarse más y más a cero" todo lo que queramos.¿Qué significa que un algoritmo converja?
"Técnicamente" lo que converge no es el algoritmo, sino un valor que el algoritmo está manipulando o iterando. Por ejemplo, supongamos que estamos escribiendo un algoritmo que imprime todos los dígitos de PI.
El algoritmo comienza a imprimir números como:
Podríamos preguntarnos: ¿el algoritmo imprime números cada vez más cerca de PI? En otras palabras, ¿la secuencia
X0, X1, ... XN ...que imprime nuestro algoritmo converge a PI?Si es así, decimos que nuestro algoritmo converge a PI.
Por lo general, estamos interesados en probar la exactitud de un algoritmo.
Por lo general, cuando escribimos un algoritmo, nos interesa saber si la solución que proporciona el algoritmo es la correcta para el problema que resuelve. Esto a veces puede venir en forma de una convergencia.
En general, los algoritmos tienen lo que llamamos métricas . Una métrica es un número que le damos a un resultado dado que produce el algoritmo. Por ejemplo, en los algoritmos iterativos AI / Machine Learning es muy común que hagamos un seguimiento del "error" que genera el algoritmo en función de la entrada. Este error es una métrica.
En esos algoritmos iterativos, cada paso genera un error diferente. Y lo que el algoritmo intenta hacer es minimizar ese error para que cada vez sea más pequeño. Decimos que el algoritmo converge si converge la secuencia de errores.
En esos casos,
global optimumgeneralmente se define como la configuración que tiene el error más bajo posible. En ese caso, el "algoritmo converge al óptimo global" significa que "el algoritmo genera errores en una secuencia que converge al error más bajo posible".Si el "óptimo global" es nuestra "solución correcta", afirmar que nuestro algoritmo converge es lo mismo que afirmar que nuestro algoritmo es correcto.
Además, tenga en cuenta que afirmar que un algoritmo converge requiere una prueba (como lo hicimos para nuestro ejemplo 0.001, 0.0001, ...).
Como ejemplo, un clasificador
Un ejemplo de esto podría ser en el caso de un clasificador. Supongamos que queremos clasificar si los números son impares o pares usando un algoritmo de aprendizaje automático, y que tenemos el siguiente conjunto de datos:
Nuestro algoritmo para cada conjunto de números se escupe para cada uno de ellos si son pares o impares. Para eso, podemos definir un error métrico como el número de veces que se equivocó dividido por el número total de elementos que se dieron.
Entonces, si nuestro algoritmo escupe lo siguiente:
Nuestra métrica de error sería
3/5 = 0.6. Ahora digamos que ejecutamos el algoritmo nuevamente y ahora escupe:Nuestra métrica de error sería
1/5 = 0.2.Digamos que se ejecuta más y más veces, y nuestra secuencia de errores se parece a esto:
0.6, 0.2, 0.1, 0.01, 0.000456, 0.00000543, 0.000000000444 ....Entonces, la gran pregunta es: ¿será nuestro algoritmo alguna vez cero? ¿Alguna vez convergerá a cero? ¿Nuestro algoritmo convergerá? ¿Podemos demostrar que eventualmente lo hará bien (o lo más cerca posible de la derecha)?
Espero que sí :)
fuente