Построение древа навыков - Constructing skill trees

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

Алгоритм

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

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

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

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

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

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

${ Displaystyle P_ {j} ^ {MAP} = max _ {i, q} { frac {P_ {j} (i, q) g (ji)} {1-G (ji-1)}}, forall j$

Ниже приведены описания параметров и переменных;

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

${ displaystyle Phi (x_ {i}) _ {} ^ {}}$ : вектор из m базисных функций, вычисленных в состоянии ${ 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_ {я} = сумма _ {j = i} ^ {T} gamma ^ {j-i} r_ {j}}$

${ displaystyle Gamma _ {} ^ {}}$ : Гамма-функция

${ Displaystyle п _ {} ^ {} = т-к}$

${ displaystyle m _ {} ^ {}}$ : Количество базисных функций q.

${ displaystyle D _ {} ^ {}}$ : матрица m на m с ${ displaystyle delta ^ {- 1}}$ по диагонали и нули еще где

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

${ displaystyle g _ {} ^ {} (l) = (1-p) ^ {l-1} p}$

${ Displaystyle G _ {} ^ {} (l) = (1- (1-p) ^ {l})}$

${ displaystyle p _ {} ^ {} = { frac {1} {k}}}$

${ displaystyle k _ {} ^ {}:}$ Ожидаемая длина навыка

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

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

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

Псевдокод

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

частицы: = []; Обработка каждой входящей точки данныхза t = 1: Т делать    // Вычислить вероятности соответствия для всех частиц за  ${ displaystyle p in частицы}$  делать        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 - Г (т - п.пос - 1)) конец    // При необходимости фильтруем    если количество частиц ≥ N тогда        частицы: = фильтр_частиц (p.MAP, M) конец    // Определяем путь Витерби    за t = 1 делать        max_path: = [] max_MAP: = 1 / | Q | еще        max_particle: =  ${ displaystyle max _ {p}}$ p.MAP max_path: = max_particle.path  ${ Displaystyle чашка}$  max_particle max_MAP: = max_particle.MAP конец    // Создаем новые частицы для точки изменения в момент времени t    за  ${ displaystyle q in Q}$  делать        new_p: = create_particle (модель = q, pos = t, prev_MAP = max_MAP, path = max_path) p: = p  ${ Displaystyle чашка}$  new_p конец    // Обновляем все частицы    за  ${ displaystyle p in P}$  делать        частицы: = update_particle (current_state, current_reward, p) конецконец// Возвращаем наиболее вероятный путь к конечной точкевозвращаться max_path

функция update_particle (текущее_состояние, текущее_назначение, частица) является    p: = частица r_t: = current_reward // Инициализация    если t = 0 тогда        p.A: = нулевая матрица (p.m, p.m) p.b: = нулевой вектор (p.m) p.z: = нулевой вектор (p.m) p.sum r: = 0 p.tr1: = 0 p.tr2: = 0 конец, если    // Вычислить вектор базисной функции для текущего состояния     ${ displaystyle Phi _ {t}}$  : = стр. ${ displaystyle Phi}$ (Текущее состояние) // Обновляем достаточную статистику    p.A: = p.A + ${ displaystyle Phi _ {t} Phi _ {t} ^ {T}}$     p.z: =  ${ displaystyle gamma}$ p.z + ${ displaystyle Phi _ {t}}$     p.b: = p.b + ${ displaystyle r_ {t}}$  p.z p.tr1: = 1+  ${ displaystyle gamma ^ {2}}$  p.tr1 p.sum r: = сумма p.r +  ${ displaystyle r_ {t} ^ {2}}$  p.tr1 + 2 ${ displaystyle gamma r_ {t}}$  p.tr2 p.tr2: =  ${ displaystyle gamma}$ p.tr2 + ${ displaystyle r_ {t}}$  p.tr1 p.fit_prob: = compute_fit_prob (p, v, u, delta,  ${ displaystyle gamma}$ )

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

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

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

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

Использует

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