Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 243
Текст из файла (страница 243)
Иными словами, полученная гипотеза будет по всей вероятности приблизительно правильной. Количество требуемых примеров, зависящее от е и 6, называется 'в. выборочной сложностью (зашр1е сошр!ехйу) пространства гипотез. Поэтому создается впечатление, что основной вопрос сводится к определению размера пространства гипотез. Как бьшо показано выше, если н — множество всех булевых функций от п атрибутов, то ~н) =2' . Таким образом, выборочная сложность пространства растет в зависимости от 2".
Поскольку количество возможных примеров также равно 2", на этом основании можно утверждать, что любой обучающий алгоритм для пространства всех булевых функций не может функционировать лучше, чем поисковая таблица, если он просто возврашает гипотезу, совместимую со всеми известными примерами. Еше один способ убедиться в справедливости этого утверждения может быть основан на том наблюдении, что для любого не встречавшегося ранее примера пространство гипотез будет содержать столько же со- 892 Часть Ът.
Обучение вместимых гипотез, которые предсказывают положительный результат, сколько имеется гипотез, предсказывающих отрицательный результат. Поэтому дилемма, с которой мы сталкиваемся, состоит в следующем: если пространство функций, которые могут рассматриваться алгоритмом, останется неограниченным, то алгоритм не будет способен к обучению, но, с другой стороны, ограничение пространства может привести к полному удалению истинной функции. Существуют два способа "разрешения" этой дилеммы. Первый способ состоит в соблюдении требования, чтобы алгоритм возвращал не просто любую совместимую гипотезу, а преимущественно наиболее простую гипотезу (что и предусмотрено в обучении деревьев решений). Теоретический анализ подобных алгоритмов выходит за рамки данной книги, но в тех случаях, когда задача поиска простых совместимых гипотез является легко разрешимой, результаты определения выборочной сложности обычно бывают лучше по сравнению с результатами анализа, основанными только на определении совместимости.
Второй способ разрешения дилеммы, который рассматривается ниже, состоит в том, что нужно сосредоточиться на тех подмножествах всего множества булевых функций, которые доступны для обучения. Идея этого способа состоит в том, что в большинстве случаев не требуется полная выразительная мощь булевых функций и можно ограничиться использованием более простых языков. В следующем разделе один из таких ограниченных языков рассматривается более подробно.
Обучение списков решений ;ъ. Список решений — это логическое выражение с ограниченной формой. Он состоит из ряда проверок, каждая из которых представляет собой коньюнкцню литералов. Если проверка, применяемая к описанию примера, завершается успешно, то список решений задает возвращаемое значение. Если же проверка оканчивается неудачей, то обработка продолжается со следующей проверки в списке'. Списки решений напоминают деревья решений, но их общая структура проще.
С другой стороны, отдельные проверки в них намного сложнее. На рис. 18.10 показан список решений, который представляет следующую гипотезу: )ух )у111)уауе(х) а» Раегопа(х, Боте) и (Раегопа(х, Рп11) л Рг1/Бак(х) ) Если допускается применение проверок с произвольными размерами, то списки решений становятся способными представить любую булеву функцию (упр.
18.15). С другой стороны, если размер каждой проверки ограничен, самое большее, )с литералами, то для обучающего алгоритма появляется возможность успешно создавать обобщения на основе небольшого количества примеров. Мы будем называть такой язык списков решений с )с литералами языком ск )с-РЬ (РЬ вЂ” Рес)гйоп Ь)з)). Пример, приведенный на рис. 18.10, относится к языку 2-01.. Можно легко показать (упр.
18.15), что язык )с-РЬ включает в качестве подмножества язык ок к-кзТ 10Т— Ресйюп Тгее), который представляет собой множество всех деревьев решений с глубиной, не превышающей )с. Важно помнить, что конкретный язык, к которому применяется обозначение )с-РЬ, зависит от атрибутов, используемых для описания примеров. Мы будем использовать запись )с-РЬ(п) для обозначения языка (с-РЬ, в котором применяется п булевых атрибутов.
"Поэт нс список решений васити!ен по своей структуре оператору соко в языке Ьйр. Часть \71. Обучение 894 Листинг 18.3. Алгоритм обучения списков решений Еппоеьоп Рестзвоп-Ьтзс-Ьеагпъпа(ехашр1ев1 геепгпв список решений или индикатор неудачи Еаз1пге аЕ множество ехашр1еа пусто сьеп геспгп тривиальный список решений ВГо С е- проверка, которая согласуется с непуотым подмножеством ехатар1еа, множества ехаюр1еа, таким что все элементы ехашр1еве являются либо положительными, либо отрицательными примерами аЕ такая пооверка С отсутствует Еьею геепгп Еа11иге ЕЕ примеры в подмножестве ехаир1езе являются положительными еьеп о с в уеа езве о е- Лто геспгю список решений с начальной проверкой с, результатом о и оставшимися проверками, определяемыми выражением Рес1зьоп-Ьъзе-Ьеагпьпц(ехашр1еа-ехашр2еае1 В этом алгоритме не определен метод выбора следующей проверки для добавления к списку решений.
Хотя формально приведенные выше результаты не зависят от такого метода выбора, представляется резонным подход, позволяющий отдавать предпочтение небольшим проверкам, которые согласуются с большими множествами однородно классифицируемых примеров, для того чтобы обгций список решений был как можно более компактным. Простейшая стратегия достижения этой цели состоит в том, что нужно отыскивать наименьшую проверку с, которая согласуется с любым однородно классифицируемым подмножеством, независимо от размера этого подмножества.
Как показано на рис. 18.11, даже такой примитивный подход действует вполне успешно. о В О,Я но 07 8 о 05 0,4 0 20 40 60 00 100 Объем обучающего множества утес. 18 11. Кривая обучения по данным о ресспоране при использовании алгори яма Реса втсп -ьз в с-ьеагп зод. Для сравнения показана кривая, соепветсшвуююлш алгоритмуреота1оп-тгее-Ьеагп1по Обсуждение полученных результатов В рамках теории вычислительного обучения был создан новый способ трактовки проблемы обучения.
В начште 1960-х годов разработки в области теории обучения 895 Глава 18. Обучение на основе наблюдений сосредоточивались в основном на проблеме успешной Ж идентификации в пределе. Всоответствии с этим понятием любой алгоритм идентификации должен возвращать гипотезу, которая точно совпадает с истинной функцией. Один из способов решения этой задачи состоит в следующем: вначале упорядочить все гипотезы в множестве и в соответствии с некоторым критерием простоты, затем выбрать простейшую гипотезу, совместимую со всеми полученными до сих пор примерами. По мере получения новых примеров в этом методе предусмотрен отказ от более простой гипотезы, которая стала недействительной, и принятие вместо нее более сложной гипотезы.
Но после того как достигается истинная функция, от нее никогда не происходит отказ. К сожалению, в больших пространствах гипотез количество примеров и продолжительность вычислений, необходимая для достижения истинной функции, становятся колоссальными. Поэтому теория вычислительного обучения не определяет безусловного требования, чтобы обучающийся агент определил "единственный истинный закон", руководящий его средой, а вместо этого допускает, чтобы он нашел гипотезу с определенной степенью прогностической точности.
Кроме того, в теории вычислительного обучения большое внимание уделяется выявлению компромисса между выразительностью языка гипотез и сложностью обучения, поэтому развитие этой теории непосредственно привело к созданию важного класса обучающих алгоритмов, получившего название машин поддермеявающих векторов йшррогг нес1ог тасИпе). Приведенные в данном разделе результаты РАС-обучения представляют собой результаты определения сложности для наихудшего случая и не обязательно отражают выборочную сложность для среднего случая, которая измеряется с помощью приведенных здесь кривых обучения. При анализе среднего случая необходимо также принять предположения о распределении вероятностей примеров и распрелелении вероятностей истинных функций, которые должны быть изучены с помощью данного алгоритма.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
