Построение деревьев навыков

Построение деревьев навыков (CST) — это иерархический алгоритм обучения с подкреплением , который может строить деревья навыков на основе набора образцов траекторий решения, полученных в результате демонстрации. CST использует пошаговый алгоритм обнаружения точек изменения MAP ( максимум апостериорный ), чтобы сегментировать каждую демонстрационную траекторию на навыки и интегрировать результаты в дерево навыков. CST был представлен Джорджем Конидарисом , Скоттом Куиндерсмой , Эндрю Барто и Родериком Групеном в 2010 году. ^[1]

Алгоритм

CST состоит в основном из трех частей: обнаружение точки изменения, выравнивание и слияние. Основное внимание CST уделяется онлайн-обнаружению точек изменения. Алгоритм обнаружения точек изменения используется для сегментации данных по навыкам и использует сумму дисконтированного вознаграждения. $R_{t}$ в качестве целевой переменной регрессии. Каждому навыку присвоена соответствующая абстракция. Фильтр частиц используется для управления вычислительной сложностью CST.

Алгоритм обнаружения точки изменения реализован следующим образом. Данные за раз $t\in T$ и модели $Q$ с предыдущим $p(q\in Q)$ даны. Предполагается, что алгоритм может соответствовать сегменту по времени. $j+1$ до $t$ с использованием модели $q$ с вероятностью соответствия $P(j,t,q)_{}^{}$ . Для расчета используется модель линейной регрессии с гауссовским шумом. $P(j,t,q)$ . Априорный гауссов шум имеет нулевое среднее значение и следующую за ним дисперсию. $\mathrm {InverseGamma} \left({\frac {v}{2}},{\frac {u}{2}}\right)$ . Далее следует априор для каждого веса. $\mathrm {Normal} (0,\sigma ^{2}\delta )$ .

Вероятность соответствия $P(j,t,q)$ вычисляется по следующему уравнению.

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}})}}

Затем CST вычисляет вероятность точки изменения в момент времени $j$ с моделью $q$ , $P_{t}(j,q)$ и $P_{j}^{\text{MAP}}$ с использованием алгоритма Витерби .

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

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

Описания параметров и переменных следующие:

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

\Phi (x_{i})

: вектор из m базисных функций, оцениваемых в состоянии

x_{i}

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

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

R_{i}=\sum _{j=i}^{T}\gamma ^{j-i}r_{j}

𝛾: Гамма-функция

n=t-j

m

: количество базисных функций q.

D

: матрица размером m на m с

\delta ^{-1}

на диагонали и нули в других местах

длина навыка $l$ Предполагается, что $подчиняется геометрическому распределению с параметром p$

g_{}^{}(l)=(1-p)^{l-1}p

G_{}^{}(l)=(1-(1-p)^{l})

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

k

: Ожидаемая длина навыка

Используя описанный выше метод, CST может сегментировать данные в цепочку навыков. Временная сложность обнаружения точки изменения равна $O(NL)$ и размер хранилища $O(Nc)$ , где $N$ — количество частиц, $L$ — время вычисления $P(j,t,q)$ , и есть $O(c)$ поменять точки.

Следующий шаг – выравнивание. CST необходимо согласовать компоненты навыков, поскольку точки изменения не происходят в одних и тех же местах. Таким образом, при сегментировании второй траектории после сегментирования первой траектории имеется смещение относительно местоположения точки изменения на второй траектории. Это смещение следует за смесью гауссиан.

Последний шаг – слияние. CST объединяет цепочки навыков в дерево навыков. CST объединяет пару сегментов траектории, назначая один и тот же навык. Все траектории имеют одну и ту же цель и объединяют две цепочки, начиная с их последних сегментов. Если два сегмента статистически похожи, они объединяются. Эта процедура повторяется до тех пор, пока не удастся объединить пару сегментов навыков. $P(j,t,q)$ используются для определения того, лучше моделируется пара траекторий как один навык или как два разных навыка.

Псевдокод

Следующий псевдокод описывает алгоритм обнаружения точки изменения:

particles := [];
Process each incoming data point
for t = 1:T do
    //Compute fit probabilities for all particles      
    for p ∈ particles do
        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))
    end
    // Filter if necessary
    if the number of particles ≥ N then
        particles := particle_filter(p.MAP, M)
    end
    // Determine the Viterbi path
    for t = 1 do
        max_path := []
        max_MAP := 1/|Q|
    else
        max_particle := maxp p.MAP
        max_path := max_particle.path ∪ max_particle
        max_MAP := max_particle.MAP
    end
    // Create new particles for a changepoint at time t
    for q ∈ Q do
        new_p := create_particle(model=q, pos=t, prev_MAP=max_MAP, path=max_path)
        p := p ∪ new_p
    end
    // Update all particles
    for p ∈ P do
        particles := update_particle(current_state, current_reward, p)      
    end
end
// Return the most likely path to the final point
return max_path

function update_particle(current_state, current_reward, particle) is
    p := particle
    r_t := current_reward
    // Initialization
    if t = 0 then
        p.A := zero matrix(p.m, p.m)
        p.b := zero vector(p.m)
        p.z := zero vector(p.m)
        p.sum r := 0
        p.tr1 := 0
        p.tr2 := 0
    end if
    // Compute the basis function vector for the current state
    Φ_t := p.Φ (current state)
    // Update sufficient statistics
    p.A := p.A + Φ_tΦ^T
_t
    p.z := 𝛾p.z + Φ_t
    p.b := p.b + r_t p.z
    p.tr1 := 1 + 𝛾² p.tr1
    p.sum r := sum p.r + r²
_t p.tr1 + 2𝛾r_t p.tr2
    p.tr2 := 𝛾p.tr2 + r_t p.tr1
    p.fit_prob := compute_fit_prob(p, v, u, delta, 𝛾)

Предположения

CTS предполагает, что продемонстрированные навыки образуют дерево, функция вознаграждения предметной области известна и лучшей моделью для объединения пары навыков является модель, выбранная для представления обоих по отдельности.

Преимущества

CST — гораздо более быстрый алгоритм обучения, чем цепочка навыков . CST можно применять для изучения политик более высокого уровня. Даже неудачный эпизод может улучшить навыки. Навыки, приобретенные с помощью агентно-ориентированных функций, можно использовать для решения других задач.

Использование

CST использовался для приобретения навыков в ходе демонстрации на людях в области PinBall . Его также использовали для приобретения навыков в результате демонстрации человеком на мобильном манипуляторе.

См. также

Ссылки

^ Дживанандам, Ниваш (13 сентября 2021 г.). «Недооцененные, но увлекательные концепции машинного обучения №5 — CST, PBWM, SARSA и картографирование Sammon» . Журнал Analytics India . Проверено 5 декабря 2021 г.

Конидарис, Джордж; Скотт Куиндерсма; Эндрю Барто ; Родерик Групен (2010). «Построение деревьев навыков для агентов обучения с подкреплением на основе демонстрационных траекторий». Достижения в области нейронных систем обработки информации 23 .

Конидарис, Джордж; Эндрю Барто (2009). «Открытие навыков в областях непрерывного обучения с подкреплением с использованием цепочки навыков». Достижения в области нейронных систем обработки информации 22 .

Фернхед, Пол ; Чжэнь Лю (2007). «Онлайн-вывод по множественным точкам изменения». Журнал Королевского статистического общества .

[1] Дживанандам, Ниваш (13 сентября 2021 г.). «Недооцененные, но увлекательные концепции машинного обучения №5 — CST, PBWM, SARSA и картографирование Sammon» . Журнал Analytics India . Проверено 5 декабря 2021 г.

[1]