Использование обучения с подкреплением для построения когнитивной модели иерархических открытий

Человеческое планирование иерархично. Планируете ли вы что-то простое, например, приготовление обеда, или что-то сложное, например, поездку за границу, мы обычно начинаем с грубого мысленного наброска целей, которых хотим достичь («поехать в Индию, а затем вернуться домой»). Затем этот набросок постепенно дорабатывается до подробной последовательности подцелей («забронировать билет на самолет», «упаковать багаж»), подцелей и т. Д., Вплоть до фактической последовательности движений тела, что намного сложнее. чем исходный план.

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

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

На рисунке выше показан пример иерархического планирования, а именно, как кто-то может планировать выйти из своего офиса в Кембридже, чтобы купить свадебное платье своей мечты в Патне, Индия. Круги представляют состояния, а стрелки представляют действия, которые переходят между состояниями. Каждое состояние представляет собой группу состояний нижнего уровня. Более толстые стрелки указывают на переходы между состояниями более высокого уровня, которые часто приходят на ум первыми.

Байесовская перспектива

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

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

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

Теоретические основы

Ключевой областью, в которой сочетаются психология и нейробиология, является формальное понимание человеческого поведения по отношению к назначенным действиям. Мы просим:

Каковы методы планирования и методы, используемые агентами-людьми при выполнении какой-либо задачи? Как люди открывают для себя полезные абстракции?

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

Разбивка

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

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

Иерархическое обучение с подкреплением

Вопрос о том, как агенты должны принимать полезные решения, является предметом обучения с подкреплением. Иерархическое обучение с подкреплением (HRL) стало преобладающей структурой для представления иерархического обучения и планирования. В рамках исследования моделирования HRL было представлено несколько идей относительно потенциальных методов построения модели.

Мы сосредотачиваемся на идее, что люди спонтанно организуют свою среду в кластеры состояний, которые ограничивают планирование. Такое иерархическое планирование более эффективно с точки зрения времени и памяти, чем наивное или плоское планирование, которое включает в себя действия низкого уровня и согласуется с ограниченным объемом рабочей памяти людей [3].

На диаграмме ниже толстые узлы и ребра указывают на то, что все они должны рассматриваться и поддерживаться в краткосрочной памяти для вычисления плана, а серые стрелки указывают на принадлежность к кластеру. Мы наблюдаем, что планирование перехода от состояния s к состоянию g на низкоуровневом графе G требует как минимум столько же шагов, сколько и фактическое выполнение план (вверху), введение высокоуровневого графа H решает эту проблему, снижает вычислительные затраты (в центре), а рекурсивное расширение иерархии дополнительно сокращает время и память, затрачиваемые на планирование (внизу).

Solway et al. дают формальное определение оптимальной иерархии, но не уточняют, как мозг может ее обнаружить [2]. Мы предполагаем, что оптимальная иерархия зависит от структуры среды, включая как структуру графа, так и распределение наблюдаемых характеристик среды, в частности, вознаграждений.

Модель

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

Состав

Мы представляем наблюдаемую среду как граф G = (V, E), а скрытую иерархию как H. И G, и H - невзвешенные неориентированные графики. H состоит из кластеров, где каждый низкоуровневый узел в G принадлежит ровно одному кластеру, и мостов, или ребра высокого уровня, которые соединяют эти кластеры. Мосты могут существовать между кластерами k и k ', только если есть ребро между некоторыми v, v' ∈ V такой, что v ∈ k и v ' ∈ k', т. е. каждому краю верхнего уровня в H соответствует край нижнего уровня в G.

На рисунке ниже цвета обозначают назначения кластеров. Черные края учитываются при планировании, а серые края игнорируются планировщиком. Толстые края соответствуют переходам через кластеры. Переход между кластерами w и z осуществляется через мост.

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

  • Маленькие кластеры
  • Плотная связь внутри кластеров
  • Редкая связь между кластерами

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

Мы используем стохастический процесс китайского ресторана с дискретным временем (CRP) как априор для кластеров. Открытие иерархий может быть выполнено путем инвертирования генеративной модели для получения апостериорной вероятности иерархии H. Генеративная модель, формально представленная в [6], порождает такие иерархии.

Награды

В контексте графа G награды можно интерпретировать как наблюдаемые особенности вершин. Поскольку люди часто группируются на основе наблюдаемых характеристик, разумно моделировать кластеры, вызванные вознаграждением [5]. Кроме того, мы предполагаем, что каждое состояние обеспечивает случайно определенное вознаграждение и что цель агента - максимизировать общее вознаграждение [8].

Поскольку мы предполагаем, что кластеры вызывают вознаграждение, мы моделируем каждый кластер как имеющий среднее вознаграждение. Каждый узел в этом кластере получает среднее вознаграждение, полученное из распределения, сосредоточенного вокруг среднего вознаграждения кластера. Наконец, каждое наблюдаемое вознаграждение извлекается из распределения, сосредоточенного вокруг среднего вознаграждения этого узла. Формальное обсуждение приведено в [1].

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

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

Кластеры приносят вознаграждение

Цель первого эксперимента заключалась в том, чтобы понять, как вознаграждения обобщаются в кластерах состояний. Мы проверили, влияет ли структура графа на формирование кластеров и обобщают ли люди вознаграждение, наблюдаемое на одном узле, на кластер, к которому этот узел принадлежит.

Настраивать

Эксперимент проводился с просьбой к 32 людям выбрать узел для следующего посещения, как указано в следующем сценарии. Участникам случайным образом был представлен график ниже или его перевернутая версия, чтобы гарантировать отсутствие предвзятости руки или структуры графика. Мы предсказали, что участники выберут узел, соседний с помеченным узлом, который был расположен в более крупном кластере, то есть серый узел слева от синего в первом случае и серый узел справа от синего в кластере. второй случай.

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

Вы работаете на большом золотом руднике, состоящем из нескольких отдельных шахт и туннелей. Расположение мин показано на схеме ниже (каждый кружок представляет шахту, а каждая линия представляет собой туннель). Вам платят ежедневно, и вам платят 10 долларов за грамм золота, которое вы нашли в тот день. Вы копаете ровно одну шахту в день и записываете количество золота (в граммах), которое было добыто в этот день. За последние несколько месяцев вы обнаружили, что в среднем каждая шахта дает около 15 граммов золота в день. Вчера вы выкопали синюю шахту на диаграмме ниже и получили 30 граммов золота. В какой из двух заштрихованных шахт вы будете копать сегодня? Обведите выбранный вами рудник.

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

Вывод

Мы аппроксимировали байесовский вывод над H, используя выборку Metropolis-within-Gibbs [4], которая обновляет каждый компонент H путем выборки из его апостериорной части, обусловливая все другие компоненты в одиночная ступенька Метрополис-Гастингс. Мы использовали гауссовское случайное блуждание в качестве распределения предложений для непрерывных компонентов и условное предварительное задание CRP в качестве распределения предложений для кластерных назначений [7]. Подход можно интерпретировать как стохастическое восхождение на холм по отношению к функции полезности, определяемой апостериорной зависимостью.

Полученные результаты

В каждой из групп людей и симуляции было по 32 участника. Три верхних кластеризации, выведенные моделью, показаны ниже (левая панель). Все три лучших результата были одинаковыми, что свидетельствует о том, что модель с высокой степенью достоверности определила цветные группы. Результаты для участников, а также результаты для статической модели вознаграждений визуализированы на гистограмме ниже (правая панель), отображающей долю людей и имитируемых субъектов, которые решили посетить узел 2 следующим. Сплошная черная линия указывает среднее значение, а пунктирные черные линии указывают 2,5-й и 97,5-й процентили.

Перечисленные p -значения в таблице ниже были вычислены с помощью биномиального теста с правым хвостом, где нуль предполагалось как биномиальное распределение при выборе левого или правого серого узла. Уровень значимости был принят равным 0,05, и результаты экспериментов на людях и результаты моделирования были статистически значимыми.

Награды побуждают кластеры

Во втором эксперименте цель состояла в том, чтобы определить, вызывают ли вознаграждения кластеры. Мы предсказали, что узлы с одинаковым вознаграждением, расположенные рядом друг с другом, будут сгруппированы вместе, даже если структура графа сама по себе не будет вызывать кластеры.

Напомним, что Solway et. Аль показал, что люди предпочитают пути, которые пересекают наименьшее количество границ иерархии [2]. Следовательно, между двумя идентичными путями единственная причина предпочесть один другому - это то, что он пересекает меньшее количество границ иерархии. Одним из возможных контраргументов является то, что люди выбирают путь с более высокими наградами. Однако в нашей настройке, подробно описанной ниже, награды выдаются только в состоянии цели, а не в совокупности по пройденному пути. Кроме того, размер вознаграждения варьировался между испытаниями. Следовательно, маловероятно, что люди предпочтут путь, потому что узлы на этом пути имеют более высокое вознаграждение.

Настраивать

Этот эксперимент проводился в Интернете с помощью Amazon Mechanical Turk (MTurk). Участникам был дан следующий контекст о задаче:

Представьте, что вы шахтер, работающий в сети золотых приисков, соединенных туннелями. Каждый рудник ежедневно дает определенное количество золота (очков). Каждый день ваша задача - переходить от стартовой шахты к целевой шахте и собирать очки с целевой шахты. В некоторые дни вы сможете выбрать любую шахту, которая вам нравится. В такие дни вы должны попытаться выбрать шахту, которая приносит больше всего очков. В остальные дни будет доступна только одна шахта. Точки этой шахты будут выделены зеленым цветом, а остальные - серым. В эти дни вам следует перейти к доступной шахте. На нем будут написаны баллы каждой шахты. Текущая шахта будет выделена толстой рамкой. Вы можете перемещаться между минами с помощью клавиш со стрелками (вверх, вниз, влево, вправо). Как только вы достигнете целевой шахты, нажмите клавишу пробела, чтобы набрать очки и начать следующий день. В эксперименте будет 100 дней (пробных).

График ниже (левая панель) был представлен участникам. Как и в предыдущем эксперименте, участникам случайным образом давали либо конфигурацию, показанную на том же графике, либо перевернутую по горизонтали версию того же графика, чтобы контролировать потенциальную лево-правую асимметрию. Также изображены ожидаемые индуцированные кластеры с нумерацией узлов для справки (правая панель).

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

В каждом испытании значения вознаграждения менялись с вероятностью 0,2. Новые награды разыгрывались равномерно случайным образом из интервала [0, 300]. Однако группировка вознаграждений оставалась неизменной для испытаний: узлы 1, 2 и 3 всегда имели одно значение вознаграждения, узлы 4, 5 и 6 имели другое значение вознаграждения, а узлы 7, 8, 9 и 10 имели одно значение вознаграждения. третье значение награды.

Первые 99 испытаний позволили участнику разработать иерархию кластеров. В последнем испытании, которое действовало как испытательное испытание, участникам предлагалось перейти от узла 6 к узлу 1. Предполагая, что вознаграждения вызвали кластеры, показанные выше, мы предсказали, что больше участников пойдут по пути через узел 5, который пересекает только один кластер. граница, через один через узел 7, который пересекает две границы кластера.

Вывод

Мы смоделировали случай с фиксированным выбором, исходя из предположения, что задачи во всех 100 испытаниях были такими же, как и в 100-м испытании, представленном участникам, испытательном испытании. Во-первых, мы предполагали статические награды, при этом награды оставались неизменными во всех испытаниях. Затем мы предположили динамические награды, где награды менялись для каждого испытания.

В отличие от предыдущего эксперимента, где участник выбирает один узел, модель предсказывает этот узел, этот эксперимент касается второго узла полного пути, который участник выбрал пройти от начального узла до целевого узла. Поэтому, чтобы сравнить модель с человеческими данными, мы использовали вариант поиска в ширину, в дальнейшем называемый иерархической BFS, для прогнозирования пути от начального узла (узел 6) к цели (узел 1).

Статические награды. Для каждого объекта мы взяли апостериорную выборку с использованием выборки Метрополис внутри Гиббса и выбрали наиболее вероятную иерархию, то есть иерархию с наивысшей апостериорной вероятностью. Затем мы использовали иерархическую BFS, чтобы сначала найти путь между кластерами, а затем между узлами внутри кластеров.

Динамическое вознаграждение. Для динамического вознаграждения мы использовали онлайн-вывод. Для каждого моделируемого участника мы позволили выборке для каждого испытания пройти только 10 шагов. Затем мы сохранили иерархию и добавили информацию об измененных наградах. Затем мы снова разрешили сэмплирование, начиная с сохраненной иерархии. Как и в эксперименте на людях, в начале каждого испытания была 0,2 вероятности того, что вознаграждения будут повторно рандомизированы до новых значений, хотя вознаграждения всегда были равны в пределах кластеров. Этот метод вывода моделировал, как участники-люди могут учиться кумулятивно в ходе многих испытаний. Для целей этого эксперимента мы предположили, что люди всегда имеют в виду только одну иерархию, а не обновляют несколько иерархий параллельно. Мы также изменили лог-апостериор, чтобы наложить штраф на отключенные кластеры, потому что такие кластеры стали гораздо более распространенными при таком типе вывода.

Полученные результаты

Было 95 участников в каждой из людей и двух симулированных группах. Нулевая гипотеза представлена ​​равным числом участников, выбирающих путь через узел 5 и через узел 7, поскольку при отсутствии какой-либо другой информации и при условии, что оба пути имеют одинаковую длину, участник с равной вероятностью выберет любой из них.

Как показано в таблице выше, результаты эксперимента на людях и моделирования статических вознаграждений были статистически значимыми при α = 0,05. Кроме того, как показано ниже, результаты эксперимента на людях находятся в 90-м процентиле нормального распределения с центром около 0,5, ожидаемой пропорции с учетом нулевой гипотезы. На рисунке мы включаем кластеризацию, идентифицированную статической моделью вознаграждения (первая строка), статической моделью вознаграждения с формированием кластера между отключенными компонентами, оштрафованными второй строкой) и динамической моделью вознаграждения (третья строка).

Статические награды. Мы использовали 1000 итераций выборки из Метрополиса в пределах Гиббса для генерации каждой выборки с выдержкой и запаздыванием по 1 каждой. Моделирование со статическим вознаграждением, безусловно, способствует прохождению через узел 5 до статистически значимого уровня. Более того, поскольку его целью является моделирование человеческого поведения, этот результат имеет значение в свете того, что человеческие данные также являются статистически значимыми (0,0321 ‹α = 0,05).

Динамическое вознаграждение. Чтобы имитировать испытания на людях, мы провели 100 испытаний, каждое с 10 итерациями Метрополиса внутри Гиббса для выборки из апостериорной части. Выгорание и задержка снова были установлены на 1. Похоже, что метод онлайн-вывода смоделировал человеческие данные лучше, чем моделирование статических вознаграждений, даже несмотря на то, что группа смоделированных участников при динамическом моделировании вознаграждений дальше от гипотезы, чем группа, смоделированная при статических вознаграждениях. моделирование. 56 участников-людей и 54 смоделированных участника при динамическом моделировании вознаграждений решили пройти через узел 5 (разница 3,4%) по сравнению с 64 смоделированными участниками при статическом моделировании вознаграждений (разница 18,5%).

На гистограмме выше показано соотношение людей и имитируемых субъектов, второй узел выбранного пути которых был узлом 5. Сплошная черная линия указывает ожидаемую пропорцию с учетом нулевой гипотезы, а пунктирные черные линии указывают 10-й и 90-й процентили.

Выводы

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

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

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

использованная литература

[1] А. Кумар и С. Ягати, Обобщение вознаграждений и открытие иерархии вознаграждений для планирования (2018 г.), Массачусетский технологический институт.

[2] А. Солуэй, К. Дюк, Н. Кордова, Д. Йи, А. Барто, Ю. Нив и М. Ботвиник, Оптимальная поведенческая иерархия (2014), PLOS Computational Biology.

[3] Г. Миллер, Магическое число семь плюс-минус два: некоторые ограничения нашей способности обрабатывать информацию (1956), The Psychological Review

[4] Дж. Робертс и Дж. Розенталь, Примеры адаптивного MCMC (2009), Журнал вычислительной и графической статистики.

[5] Дж. Балагер, Х. Спайерс, Д. Хассабис и К. Саммерфилд, Нейронные механизмы иерархического планирования в виртуальной сети метро (2016), Neuron

[6] М. Томов, С. Ягати, А. Кумар, В. Ян и С. Гершман, Открытие иерархических представлений для эффективного планирования (2020), PLOS Computational Biology.

[7] Р. Нил, Методы выборки цепей Маркова для моделей смесей процессов Дирихле (2000), Журнал вычислительной и графической статистики.

[8] Р. Саттон и А. Барто, Обучение с подкреплением: Введение (2018), MIT Press.