Construcción de árboles de habilidades

La construcción de árboles de habilidades (CST, por sus siglas en inglés) es un algoritmo de aprendizaje por refuerzo jerárquico que puede construir árboles de habilidades a partir de un conjunto de trayectorias de soluciones de muestra obtenidas mediante demostración. CST utiliza un algoritmo incremental de detección de puntos de cambio MAP ( máxima probabilidad a posteriori ) para segmentar cada trayectoria de demostración en habilidades e integrar los resultados en un árbol de habilidades. CST fue presentado por George Konidaris , Scott Kuindersma , Andrew Barto y Roderic Grupen en 2010. ^{[ 1 ]}

CST consta principalmente de tres partes: detección de puntos de cambio, alineación y fusión. El enfoque principal de CST es la detección de puntos de cambio en línea. El algoritmo de detección de puntos de cambio se utiliza para segmentar los datos en habilidades y utiliza la suma de recompensas descontadas.${\displaystyle R_{t}}$como variable de regresión objetivo. A cada habilidad se le asigna una abstracción apropiada. Se utiliza un filtro de partículas para controlar la complejidad computacional de CST.

El algoritmo de detección de puntos de cambio se implementa de la siguiente manera. Los datos para tiempos${\displaystyle t\in T}$y modelos Q con anterioridad${\displaystyle p(q\in Q)}$se dan. Se supone que el algoritmo puede ajustar un segmento de tiempo${\displaystyle j+1}$a t usando el modelo q con la probabilidad de ajuste${\displaystyle P(j,t,q)_{}^{}}$Se utiliza un modelo de regresión lineal con ruido gaussiano para calcular${\displaystyle P(j,t,q)}$. La distribución a priori del ruido gaussiano tiene media cero y varianza que sigue${\displaystyle \mathrm {Gamma inversa} \left({\frac {v}{2}},{\frac {u}{2}}\right)}$. La distribución a priori para cada peso es la siguiente:${\displaystyle \mathrm {Normal} (0,\sigma ^{2}\delta)}$.

La probabilidad de ajuste${\displaystyle P(j,t,q)}$se calcula mediante la siguiente ecuación.

${\displaystyle P(j,t,q)={\frac {\pi ^{-{\frac {n}{2}}}}{\delta ^{m}}}\left|(A+D)^{-1}\right|^{\frac {1}{2}}{\frac {u^{\frac {v}{2}}}{(y+u)^{\frac {u+v}{2}}}}{\frac {\Gamma ({\frac {n+v}{2}})}{\Gamma ({\frac {v}{2}})}}}$

Luego, CST calcula la probabilidad del punto de cambio en el tiempo j con el modelo q ,${\displaystyle P_{t}(j,q)}$y${\displaystyle P_{j}^{\text{MAPA}}}$utilizando un algoritmo de Viterbi .

${\displaystyle P_{t}(j,q)=(1-G(tj-1))P(j,t,q)p(q)P_{j}^{\text{MAP}}}$

${\displaystyle P_{j}^{\text{MAP}}=\max _{i,q}{\frac {P_{j}(i,q)g(ji)}{1-G(ji-1)}},\forall j<t}$

Las descripciones de los parámetros y variables son las siguientes:

${\displaystyle A=\sum _{i=j}^{t}\Phi (x_{i})\Phi (x_{i})^{T}}$

${\displaystyle \Phi (x_{i})}$: un vector de m funciones base evaluadas en el estado${\displaystyle x_{i}}$

${\displaystyle y=(\sum _{i=j}^{t}R_{i}^{2})-b^{T}(A+D)^{-1}b}$

${\displaystyle b=\sum _{i=j}^{t}R_{i}\Phi (x_{i})}$

${\displaystyle R_{i}=\sum _{j=i}^{T}\gamma ^{ji}r_{j}}$

𝛾 : función gamma

${\displaystyle n=tj}$

m : El número de funciones base que tiene q.

D : una matriz m por m con${\displaystyle \delta ^{-1}}$en la diagonal y ceros en el resto

Se supone que la longitud de la habilidad l sigue una distribución geométrica con parámetro p.

${\displaystyle g_{}^{}(l)=(1-p)^{l-1}p}$

${\displaystyle G_{}^{}(l)=(1-(1-p)^{l})}$

${\displaystyle p_{}^{}={\frac {1}{k}}}$

k : Longitud esperada de la habilidad

Utilizando el método anterior, CST puede segmentar los datos en una cadena de habilidades. La complejidad temporal de la detección del punto de cambio es${\displaystyle O(NL)}$y el tamaño de almacenamiento es${\displaystyle O(Nc)}$donde N es el número de partículas y L es el tiempo de cálculo.${\displaystyle P(j,t,q)}$y hay${\displaystyle O(c)}$puntos de cambio.

El siguiente paso es la alineación. CST necesita alinear las habilidades componentes porque el punto de cambio no se produce exactamente en los mismos lugares. Por lo tanto, al segmentar la segunda trayectoria después de segmentar la primera, se produce un sesgo en la ubicación del punto de cambio en la segunda trayectoria. Este sesgo sigue una mezcla de gaussianas.

El último paso es la fusión. CST fusiona cadenas de habilidades en un árbol de habilidades. CST fusiona un par de segmentos de trayectoria asignándoles la misma habilidad. Todas las trayectorias tienen el mismo objetivo y fusiona dos cadenas comenzando por sus segmentos finales. Si dos segmentos son estadísticamente similares, los fusiona. Este procedimiento se repite hasta que no se logra fusionar un par de segmentos de habilidad.${\displaystyle P(j,t,q)}$Se utilizan para determinar si un par de trayectorias se modelan mejor como una sola habilidad o como dos habilidades diferentes.

El siguiente pseudocódigo describe el algoritmo de detección de puntos de cambio:

partículas := []; Procesar cada punto de datos entrante para t = 1:T hacer //Calcular las probabilidades de ajuste para todas las partículas para p ∈ partículas hacer p_tjq := (1 − G(t − p.pos − 1)) × p.fit_prob × model_prior(p.model) × p.prev_MAP p.MAP := p_tjq × g(t−p.pos) / (1 − G(t − p.pos − 1)) fin // Filtrar si es necesario si el número de partículas ≥ N entonces partículas := filtro_de_partículas(p.MAP, M) fin // Determinar la trayectoria de Viterbi para t = 1 hacer ruta_máxima := [] max_MAP := 1/|Q| de lo contrario max_particle := max p p.MAP ruta_máxima := ruta_partícula_máxima ∪ partícula_máxima max_MAP := max_particle.MAP fin // Crea nuevas partículas para un punto de cambio en el tiempo t para q ∈ Q hacer new_p := create_particle(model=q, pos=t, prev_MAP=max_MAP, path=max_path) p := p ∪ new_p fin // Actualizar todas las partículas para p ∈ P hacer partículas := actualizar_partícula(estado_actual, recompensa_actual, p) fin fin // Devuelve la ruta más probable al punto final return max_path

La función update_particle(estado_actual, recompensa_actual, partícula) es p := partícula r_t := recompensa_actual // Inicialización si t = 0 entonces pA := matriz cero(pm, pm) pb := vector cero(pm) pz := vector cero(pm) p.sum r := 0 p.tr1 := 0 p.tr2 := 0 fin si // Calcular el vector de función base para el estado actual Φ t := p. Φ (estado actual) // Actualizar estadísticas suficientes pA := pA + Φ t Φ T t pz := 𝛾 p.z + Φ t pb := pb + r t pz p.tr1 := 1 + 𝛾 2 p.tr1 p.sum r := sum pr + r 2 t p.tr1 + 2 𝛾 r t p.tr2 p.tr2 := 𝛾 p.tr2 + r t p.tr1 p.fit_prob := cálculo_fit_prob(p, v, u, delta, 𝛾 )

Los sistemas de tutoría cognitiva (CTS) asumen que las habilidades demostradas forman un árbol, que se conoce la función de recompensa del dominio y que el mejor modelo para fusionar un par de habilidades es el modelo seleccionado para representarlas individualmente.

CST es un algoritmo de aprendizaje mucho más rápido que el encadenamiento de habilidades . CST se puede aplicar al aprendizaje de políticas de dimensiones superiores. Incluso un episodio fallido puede mejorar las habilidades. Las habilidades adquiridas mediante características centradas en el agente se pueden utilizar para otros problemas.

El método CST se ha utilizado para adquirir habilidades mediante demostraciones humanas en el ámbito del pinball . También se ha utilizado para adquirir habilidades mediante demostraciones humanas en un manipulador móvil.

• corteza prefrontal ganglios basales memoria de trabajo
• Estado-acción-recompensa-estado-acción
• Mapeo de Sammon

• Konidaris, George; Scott Kuindersma; Andrew Barto ; Roderic Grupen (2010). "Construcción de árboles de habilidades para agentes de aprendizaje por refuerzo a partir de trayectorias de demostración". Advances in Neural Information Processing Systems 23 .

• Konidaris, George; Andrew Barto (2009). "Descubrimiento de habilidades en dominios de aprendizaje por refuerzo continuo mediante encadenamiento de habilidades". Avances en sistemas de procesamiento de información neuronal 22 .

• Fearnhead, Paul ; Zhen Liu (2007). "Inferencia en línea para múltiples puntos de cambio". Journal of the Royal Statistical Society .