En informática , un algoritmo de aprendizaje incremental o incremental es un algoritmo de aprendizaje que tiene la particularidad de estar en línea , es decir que aprende de los datos recibidos según el tiempo. En cada incremento que recibe datos de entrada y un resultado, el algoritmo luego calcula una mejora en el cálculo realizado para predecir el resultado a partir de los datos de entrada.
Dado que no conoce todos los datos, un algoritmo de aprendizaje incremental se ve obligado a tomar decisiones que, en última instancia, pueden resultar no óptimas; Por tanto, el estudio de los algoritmos de aprendizaje incremental se ha centrado en la calidad de las posibles elecciones en dicha configuración. El análisis competitivo formaliza esta idea comparando el rendimiento sobre los mismos datos, el aprendizaje automático en línea y el equivalente con la integridad de los datos disponibles. Para conocer otras opiniones sobre algoritmos donde los datos están disponibles con el tiempo, consulte los artículos algoritmo de minería de flujo de datos (centrado en la cantidad de memoria necesaria para representar los datos recibidos en el pasado), algoritmo dinámico (centrado en la complejidad del tiempo para manipular soluciones a problemas con entradas en línea ).
Un problema que ilustra el concepto de un algoritmo de aprendizaje incremental es el del vendedor ambulante canadiense . El objetivo de este problema es minimizar el costo de alcanzar un vértice en un gráfico ponderado donde algunos de los bordes no son confiables porque pueden eliminarse del gráfico en cualquier momento. Sin embargo, si un borde se vuelve inutilizable, esto solo se le revela al "viajero" cuando alcanza uno de los vértices de ese borde. El peor caso de este problema ocurre cuando todos los bordes no confiables resultan inutilizables y el problema se reduce al problema de la ruta más corta . Se puede realizar un análisis alternativo del problema utilizando un análisis competitivo. Para este método de análisis, el algoritmo fuera de línea conoce de antemano los bordes que serán inutilizables y el objetivo es minimizar la relación entre el rendimiento del algoritmo en línea y el del algoritmo fuera de línea. Este problema está completo en PSPACE .
Aquí hay algunos nombres de algoritmos en línea: servidor K , Balance2, Balance-Slack, Double Coverage, Equipoise, Handicap, Armónico, Random-Slack, Tight Span Algorithm, Tree Algorithm, Work Function Algorithm.