Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 279
Текст из файла (страница 279)
Это означает, что наиболее важным аспектом функциональной аппроксимации является не то, что она требует меньше пространства, а то, что она обеспечивает индуктивное обобщение по входным состояниям. Чтобы дать читателю представление о возможностях 4 Известно, что такая точная функция полезности может быть представлена в зиле одной-двух страниц кода на языке В(зр, 1ауа нли С++. Это означает, что она может быть представлена с помощью программы, которая находит точное решение лля игры после каждого ее вызова. Но нас интересуют только аппроксиматоры функций, которые позволяют обойтись приемлемым объемом вычислений.
В действительности может оказаться, что лучше найти с помощью обучения очень простой аппроксиматор функции и применять его в сочетании с некоторым объемом опережающего поиска. Но связанные с этим компромиссы в настоящее время еще недостаточно хорошо изучены. 1029 Глава 21. Обучение с подкреплением Ув(х,у) = 80 + 01 х + 01 у (21. 9) Таким образом, если (0„0,, О,) = (О.
5, О. 2, О. 1), то Тт,(1, 1) =О. 8. По результатам некоторой совокупности попыток будет получено множество выборочных значений Уа (х, у), после чего можно найти соответствие, наилучшее с точки зрения минимизации квадратичных ошибок, с помощью стандартной линейной регрессии (см. главу 20).
Применительно к обучению с подкреплением больше смысла имеет использование алгоритма оперативного обучения, который обновляет параметры после каждой попытки. Предположим, что осуществляется некоторая попытка, и суммарное вознаграждение, полученное начиная с квадрата (1, 1), составляет О. 4. Такой результат наводит на мысль, что значение (гв (1, 1), составляющее в настоящее время О.
8, слишком велико и должно быть уменьшено. Как следует откорректировать параметры, чтобы добиться такого уменьшения? Как и в случае с обучением нейронной сети, запишем функцию ошибки и вычислим ее градиент по отношению к параметрам. Если и, (э) — наблюдаемое суммарное вознаграждение, полученное от состояния з и дальше, вплоть до )-й попытки, то ошибка определяется как (половина) квадратов разностей прогнозируемой общей суммы и фактической общей суммы: Я) (э) = ( Ув(э) -и„.(э) ) '!2.
Скорость изменения ошибки по отношению к каждому параметру О, равна дЕ) удб„поэтому, чтобы изменить значение параметра в направлении уменьшения ошибки, необходимо вычислить следующее выражение: дд (в) дУе(э) Е, ~ — О, — а 88 — = 8, + о(,(з) — ц„(з)) до (21. 10) Это выражение называется ек правилом Видроу — Хоффа, или Ъ. дельта-правилом для оперативного вычисления по методу наименьших квадратов.
Применительно клинейному аппроксиматору функции (га(э) в уравнении 21.9 получаем три простых правила обновления: этого подхода, укажем, что путем исследования только одного состояния из каждой группы по 104' возможных состояний в игре в нарды можно определить с помощью обучения функцию полезности, позволяю|цую программе играть не хуже любого игрока-человека [1499). Оборотной стороной этого подхода, безусловно, является то, что с ним связана такая проблема: невозможность найти в выбранном пространстве гипотез какую-либо функцию, аппроксимируюгцую истинную функцию полезности достаточно хорошо. Как и во всем научном направлении индуктивного обучения, необходимо найти компромисс между размером пространства гипотез н потребностью во времени для определения с помощью обучения требуемой функции.
С увеличением пространства гипотез растет вероятность того, что может быть найдена хорошая аппроксимация, но это означает, что сходимость также, скорее всего, будет достигаться более медленно. Начнем с простейшего случая, в котором предусматривается непосредственная оценка полезности (см. раздел 21.2). При использовании функциональной аппроксимации определение такой оценки представляет собой пример контролируемого обучения.
Например, предположим, что полезности для мира 4хЗ представлены с использованием простой линейной функции. Характеристиками квадратов являются их координаты х и у, поэтому получим следующее соотношение: Часть Ч]. Обучение ]ОЗО Ое е- Ое з- а(и, (а) пв(а) ) О, — О, + ц(оз(а) — и (а))х О, е — 9, + а(о,(а) — це(а) )~ Эти правила можно применить к примеру, в котором ре(1,1) равно 0.8, а ц, (1, 1) равно О.
4. Все значения О,, О, и О, уменьшаются на коэффициент О. 4а, который уменьшает ошибку, относящуюся к квадрату (1, 1) . Обратите внимание на то, что изменение значений О, приводит также к изменению значений рв для всех прочих состояний! Именно это подразумевалось в приведенном выше утверждении, что функциональная аппроксимация позволяет агенту, проводящему обучение с подкреплением, обобщать свой опыт. Мы рассчитываем на то, что агент будет проводить обучение быстрее, если он использует какой-то аппроксиматор функции, при условии, что пространство гипотез не слишком велико, но включает некоторые функции, характеризующиеся достаточно приемлемым соответствием истинной функции полезности. В упр. 2].7 предлагается оценить производительность метода непосредственной оценки полезности, как с функциональной аппроксимацией, так и без нее.
В мире 4хЗ действительно достигается заметное, однако не столь существенное увеличение производительности, прежде всего потому, что это пространство состояний очень мало. Достигнутое увеличение производительности становится намного более значительным в мире 10х10 с вознаграждением +1 в квадрате (10, 10) . Этот мир хорошо приспособлен для линейной функции полезности, поскольку истинная функция полезности является гладкой и почти линейной (см. упр. 21.10). А если вознаграждение +1 будет помещено в квадрат (5, 5), то истинная функция полезности будет больше напоминать по своей форме пирамиду, и попытка применения аппроксиматора функции, приведенного в уравнении 21.9, окончится крахом.
Но не все потеряно! Напомним, что для линейной функциональной аппроксимации важно, чтобы функция линейно зависела от параметров. А сами характеристики могут представлять собой произвольные нелинейные функции от переменных состояния. Поэтому можно включить е р, «е, = ~Т: .Т'т~-~р, ° .р ° в е ° ю Эти идеи можно применить столь же успешно к агентам, осуществляющим обучение по методу временной разности. Для этого достаточно откорректировать параметры, чтобы попытаться уменьшить временную разность между последовательными состояниями.
Новые версии уравнений для метода ТР и метода ()-обучения (2) .3 и 21.8) приведены ниже. Уравнение для полезностей является следующим: дВе(я) О е — 9 + (х[Я(а) + Упе(Я') — пе(Я) ) (21.11) А для Р-значений используется следующее уравнение: аа,(, ) О, + — О, + ц (д(я) + улзахОе(а',а' ) — Оо(а а) ) (21. 12) а' Можно показать, что эти правила обновления сходятся к ближайшей возможной' аппроксимации истинной функции, если аппроксиматор функции линейно зависит ' Это определение расстояния между функциями полезности является довольно формальным; см. (1515].
1031 Глава 21. Обучение с подкреплением функции, задаваемые с помощью нейронных сетей) больше ничего нельзя гарантировать. Параметры могут увеличиваться до бесконечности и в некоторых очень простых случаях, даже несмотря на то, что в пространстве гипотез существуют приемлемые решения. Разработаны более сложные алгоритмы, позволяющие избежать этих проблем, но в настоящее время вся область обучения с подкреплением на основе общих аппроксиматоров функций продолжает оставаться тонким искусством. Функциональная аппроксимация может также оказаться очень полезной при определении с помощью обучения модели среды.
Напомним, что задача определения с помощью обучения модели для наблюдаемой среды представляет собой задачу контролируемого обучения, поскольку каждый следующий результат восприятия предоставляет информацию о результирующем состоянии. При этом может использоваться любой из методов контролируемого обучения, описанный в главе 18, с соответствующими поправками с учетом того факта, что необходимо определить с помощью прогноза полное описание состояния, а не просто булеву классификацию или единственное реальное значение. Например, если состояние определяется с помощью п булевых переменных, то необходимо найти с помощью обучения и булевых функций для прогнозирования всех переменных. А в случае частично наблюдаемой среды задача обучения становится гораздо более сложной.
Если известно, каковы скрытые переменные и какими причинными отношениями они связаны друг с другом и с наблюдаемыми переменными, то можно зафиксировать структуру динамической байесовской сети и воспользоваться алгоритмом ЕМ для определения с помощью обучения ее параметров, как было описано в главе 20. А задачи выявления скрытых переменных и определения структуры модели с помощью обучения все еше остаются открытыми. Теперь обратимся к примерам крупномасштабных приложений обучения с подкреплением.
На основании этих примеров будет показано, что в случае использования функции полезности (следовательно, некоторой модели) модель обычно считается заданной. Например, при определении с помощью обучения функции оценки для нард обычно предполагается, что допустимые ходы и их результаты известны заранее. Приложения методов обучения к ведению игр Первое реальное приложение метода обучения с подкреплением оказалось также первой практически применимой программой из всех возможных типов таких программ; речь идет о программе игры в шашки, написанной Артуром Самюэлом (1349), [1350).
Самюэл впервые использовал для оценки позиций взвешенную линейную функцию, в которой одновременно применялось до 16 термов. В его программе обновление весов осуществлялось на основе некоторой версии уравнения 21.11. Тем не менее методы, применяемые в его программе, имели определенные существенные отличия от современных методов. Первое отличие состояло в том, что для обновления весов использовалась разность между значениями для текущего состояния и зарезервированным значением, сформированным путем полного опережающего просмотра в дереве поиска.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
