Библиотека    Новые поступления    Словарь    Карта сайтов    Ссылки





назад содержание далее

Часть 12.

В этом соотношении sn представляет состояние, выбранное в момент времени п, а sn+1 - состояние, выбранное в момент п+1. Это уравнение - пример правила обучения на основе временных разностей (temporal difference learning rule), поскольку изменение состояния вычисляется как функция от разности значений ценности V(sn+l)-V(sn) для двух последовательных моментов времени n+1 и п. Такие правила обучения будут обсуждаться ниже в этой главе.

Для игры в "крестики-нолики" правило временных разностей достаточно эффективно. Со временем целесообразно уменьшить шаговый множитель с, поскольку для более обученной системы значения ценности должны изменяться меньше. Тогда можно гарантировать сходимость функции ценности для каждого состояния к значению вероятности победы при игре с данным соперником. Интересно отметить, что неизменность шагового множителя приведет к тому, что такая политика никогда не сойдется и будет постоянно изменяться, отражая изменение (улучшение) стиля игры противника.

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

428

Часть IV. Машинное обучение

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

В рассмотренном примере для обучения не нужны никакие базовые знания, кроме правил игры. (Просто все состояния, кроме конечных, инициализируются значением 0,5.) Однако такая "уравниловка" вовсе не обязательна- при обучении с подкреплением можно учесть и любую реальную информацию о начальных состояниях. Кроме того, при наличии данных о ситуации для значений состояний можно использовать и сведения из этой модели. Важно помнить, что обучение с подкреплением применимо в любом случае, даже при отсутствии модели, однако при наличии модельной информации ее тоже можно учесть.

В примере игры "крестики-нолики" вознаграждение амортизируется с каждым следующим шагом. Здесь используется "близорукий" агент, максимизирующий только сиюминутное вознаграждение. На самом деле, при более пристальном изучении обучения с подкреплением необходимо учитывать "обесценивание" вознаграждения со временем. Пусть коэффициент представляет текущее значение будущего вознаграждения. При получении вознаграждения на ? шагов позже его стоимость снижается в ?k-1 раз. Такая мера "обесценивания" важна для реализации обучения с подкреплением на базе принципа динамического программирования. Этот подход будет описан в следующем разделе.

"Крестики-нолики" - это пример игры с участием двух соперников. Обучение с подкреплением можно также применять при отсутствии противника, учитывая только обратную связь с окружающей средой. Рассмотренный пример характеризуется конечным (к тому же очень маленьким) пространством состояний. Обучение с подкреплением можно также применять для очень больших и бесконечных пространств. В последнем случае ценность состояния определяется только при достижении этого состояния и его участии в решении. Например, в работе [Tesauro, 1995] упомянутое выше правило временных разностей встроено в нейронную сеть для обучения игре в нарды. Несмотря на то что пространство состояний игры в нарды содержит 1020 значений, разработанная программа играет на уровне лучших специалистов.

9.7.3. Алгоритмы вывода и их применение к обучению с подкреплением

В работе [Sutton и Barto, 1998] выделены три семейства алгоритмов обучения с подкреплением на основе вывода: обучение по правилу временных разностей, метод динамического программирования и метод Монте-Карло. К этим типам сводятся все современные подходы к обучению с подкреплением. Методы временных разностей основаны на использовании известных траекторий и пересчете значений ценности состояния на основе ценности последующего состояния. Пример правила обучения игре в "крестики-нолики" на основе временных разностей рассмотрен в предыдущем разделе.

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

Глава 9. Машинное обучение, основанное на символьном представлении... 429

основано на том, что для любой политики п и любого состояния s выполняется следующее рекурсивное уравнение

где 7t(a|s) - вероятность действия а для данного состояния s при использовании стохастической политики ?, ?(s?s'|а) - вероятность перехода из состояния s в s' под действием а. Это выражение называется "уравнением Беллмана для V?". Оно выражает соотношение между стоимостью состояния и рекурсивно вычисляемыми значениями стоимости его последующих состояний. На рис. 9.24, а показан первый этап вычислений, где для состояния s рассматриваются три возможных последующих состояния. При использовании политики я вероятность воздействия а составляет n(a\s). Для каждого из этих трех состояний в результате воздействия окружающей среды может осуществиться переход в одно из нескольких состояний, скажем, s' с вознаграждением г. В уравнении Беллмана эти возможности усредняются с учетом вероятности реализации каждой из них. Согласно этому уравнению стоимость начального состояния s пропорциональна стоимости всех последующих состояний с коэффициентом у и вознаграждению, полученному вдоль всего пути.

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

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

430 Часть IV. Машинное обучение

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

Итак, метод Монте-Карло решает задачу обучения с подкреплением за счет усредне­ния результатов экспериментов. Для обеспечения хорошей обусловленности результатов метод Монте-Карло работает только с полными экспериментами, т.е. все тесты должны в итоге завершаться. Более того, оценки стоимости и политики изменяются только по за­вершении каждого теста. Следовательно, метод Монте-Карло является инкрементальным в смысле последовательности экспериментов, а не шагов. Термин Монте-Карло зачас­тую употребляется в более широком значении для обозначения любого метода оценива­ния, в котором важную роль играет случайный компонент. Здесь он используется для методов, основанных на усреднении результатов экспериментов.

В обучении с подкреплением используются и другие методы, среди которых наиболее из­вестным является Q-обучение [Watkins, 1989], представляющее собой вариант подхода на ос­нове временных разностей. Название метода продиктовано следующими соображениям. О - это функция, отображающая пары состояние-действие в изученные значения стоимости

О: (состояние x воздействие) -> стоимость Для одного шага Q-обучения выполняется соотношение

где с?1 и g?1, а rt+1 - вознаграждение для состояния st+1. Метод Q-обучения проиллю­стрирован на рис. 9.24, б. Если на рис. 9.24, а начальный узел представляет состояние, для ко­торого показаны возможные управляющие воздействия, то в рамках Q-обучения обратный проход выполняется для пар состояние-управление, поэтому на рис. 9.24,6 корневым узлом является управляющее воздействие вместе с породившим его состоянием.

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

Интерактивное Q-обучение предполагает прямой проход в пространстве возможных дей­ствий и не требует построения полной модели мира. Его также можно выполнять в пакетном режиме. Легко видеть, что Q-обучение- это разновидность метода временных разностей. Более подробное описание этого метода приводится в [Watkins, 1989] и [Sutton и Barto, 1998].

С помощью обучения с подкреплением решено большое количество важных задач, вклю­чая обучение игре в нарды [Tesauro, 1994,1995]. В [Sutton и Barto, 1998] с точки зрения обу­чения с подкреплением проанализирована программа игры в шашки, описанная в разделе 4.3. Там же рассмотрены вопросы обучения с подкреплением для управления лифтом, динамиче­ского выделения каналов, составления расписаний и других проблем.

9.8. Резюме и ссылки

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

Глава 9. Машинное обучение, основанное на символьном представлении... 431

ведения. В этой научной области возникает множество вопросов, связанных с представлением знаний, поиском и даже базовыми положениями самого искусственного интел­лекта. Можно выделить три обзора, посвященных вопросам машинного обучения. Это работы [Langley, 1995]; [Mitchell, 1997]; [Martin, 1997].

Стоит отметить также более ранние обзоры [Kondratoff и Michalski, 1990]; [Michalski и др., 1983], [Michalski и др., 1986], а также сборник статей [Shavlik и Dietterich, 1990], включающий работы, опубликованные, начиная с 1958 года. Поместив все эти результаты в одну книгу, редакторы сделали очень важное дело как для специалистов в области искусственного интеллекта, так и для новичков, желающих познакомиться с этой областью знаний. В [Klahr, 1987] тоже собраны статьи по машинному обучению, включая ра­боты, относящиеся к более когнитивному подходу.

Работа [Weiss и Kulikowski, 1991] - это вводный обзор по всей области, включая стохастические, нейросетевые методы и алгоритмы машинного обучения. Читатели, заинтересован­ные в получении более глубоких знаний в области рассуждений по аналогии, могут обратить­ся к работам [Carbonell, 1983,1986]; [Holyoak, 1985]; [Kedar-Cabelli, 1988]; [Thagard, 1988]. Материал по вопросам создания новых знаний и формирования теорий содержится в [Langley и др., 1987] и [Shrager и Langley, 1990]. В [Fisher и др., 1991] собраны статьи по кластериза­ции, формированию понятий и другим формам обучения без учителя.

В рамках машинного обучения много работ посвящено алгоритму ID3 и его модификациям. В [Feigenbaum и Feldman, 1963] описан алгоритм запоминания ЕРАМ, в котором исполь­зуется специальный вид дерева решений, получивший название дискриминантной сети (discrimination net) и позволяющий строить последовательности бессмысленных слогов. Квинлану (Quinlan) впервые удалось использовать теорию информации для генерирования дочерних узлов дерева решений. В [Quinlan, 1993] и других работах описаны модификации алгоритма ШЗ и решены вопросы обработки зашумленных данных и атрибутов, принимаю­щих значения из непрерывного интервала [Quinlan, 1996]; [Auer и др., 1995]. В [Stubblefield и Luger, 1996] алгоритм ШЗ применяется для улучшения процесса восстановления источника в задаче рассуждения по аналогии.

Первые примеры обучения с подкреплением приводятся в [Michie, 1961]; [Samuel, 1959]. Большая часть материала этой главы почерпнута из [Sutton и Barto, 1998]. Метод Q-обучения более подробно описан в диссертации [Watkins, 1989]. Вопросы обучения на основе временных разностей освещены в [Sutton, 1998], а все алгоритмы обучения с подкреплением описаны в [Bertsekas и Tsitsiklis, 1996].

Вопросам машинного обучения посвящен журнал "Machine learning". Новые результаты в этой области ежегодно докладываются на конференциях "International Conference on Machine Learning", "European Conference on Machine Learning", "American Association of Artificial Intelligence Conference" и "International Joint Conference on Artificial Intelligence".

Вопросы обучения на основе связей освещены в главе 10, а социальное обучение и другие методы - в главе 11. Роль индуктивных порогов и обобщения в обучении описывается в разделе 16.2.

9.9. Упражнения

1. Вспомните программу изучения понятий Винстона и рассмотрите задачу изучения понятия "ступенька". Ступенька состоит из расположенных рядом маленького и

432 Часть IV. Машинное обучение

большого блоков (рис. 9.25). Создайте семантическую сеть для представления трех или четырех положительных и "почти удовлетворительных" примеров и покажите это понятие в развитии.

Рис. 9.25. Ступенька

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

Реализуйте алгоритм поиска в пространстве версий на языке PROLOG или на любом

другом языке программирования. Если вы выбрали PROLOG, воспользуйтесь рекомендациями из подраздела 14.14.1.

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

С помощью формулы Шеннона докажите, что информативность сообщения о результатах вращения рулетки выше, чем информативность сообщения о результате подбрасывания монеты. Что можно сказать о сообщении "не 00"?

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

Реализуйте алгоритм ID3 на любом языке программирования и протестируйте эту

программу на данных по кредитной истории, приведенных в этой главе. При реализации на языке LISP воспользуйтесь алгоритмами и структурами данных, приведен­ными в разделе 15.13.

Подумайте, какие проблемы возникают при использовании атрибутов, принимающих

значения из непрерывного интервала, например, из множества вещественных чисел.

Предложите свои методы решения этих проблем.

Еще одной проблемой для алгоритма ID3 являются некачественные или неполные данные. Данные считаются некачественными, если для одного и того же набора атрибутов возможны несколько различных результатов. Данные называются неполными, если часть значений атрибутов отсутствует, возможно, из-за слишком высокой стоимости их полу­чения. Как решить эти проблемы за счет модификации алгоритма IDЗ?

Познакомьтесь с алгоритмом построения дерева решений С4.5 из [Quinlan, 1993] и

протестируйте его на одном из наборов данных. В этой работе приводится полный

текст программы и тестовые наборы данных.

Подберите теоретические сведения для обучения на основе объяснения в некоторой

предметной области. Проследите за поведением системы в процессе обучения.

Разработайте алгоритм обучения на основе объяснения на любом языке программирования. Если вы выбрали PROLOG, воспользуйтесь алгоритмом из подраздела 14.14.3.

Глава 9. Машинное обучение, основанное на символьном представлении... 433

Вспомните пример игры в "крестики-нолики" из подраздела 9.7.2. Реализуйте алгоритм обучения на основе временных разностей на любом языке программирования.

Как изменится алгоритм, если принять во внимание симметричность задачи?

Что произойдет, если алгоритм на основе временных разностей из задачи 13 будут

использовать оба игрока?

Проанализируйте задачу игры в шашки с точки зрения обучения с подкреплением.

Воспользуйтесь при этом результатами анализа из [Sutton и Barto, 1998].

Можно ли решить проблему перевернутого маятника, рассмотренную в подразделе 8.2.2

(см. рис. 8.8), с помощью обучения с подкреплением? Разработайте простую функцию

вознаграждения и воспользуйтесь алгоритмом на основе временных разностей.

Еще одной тестовой задачей для обучения с подкреплением является так называемая

проблема решетки. На рис. 9.26 показана решетка размером 4x4. Две заштрихованные ячейки по углам решетки - это целевые конечные состояния агента. Из любой другой ячейки агент может двигаться вверх, вниз, влево или вправо. Он не может выйти за пределы решетки: при такой попытке состояние не изменяется. Вознаграж­дение для всех ходов, за исключением перехода в конечное состояние, составляет -1.

Постройте решение на основе алгоритма временных разностей, описанного в подразделе 9.7.2.

434 Часть IV. Машинное обучение

Машинное обучение на основе связей

Кошка, которая однажды села на горячую печь, никогда больше не сядет ни на горячую, ни на холодную...

- Марк Твен (Mark Twain)

Все неизвестное остается неясным до тех пор, пока не пытаешься его уточнить...

- Бертран Рассел (Bertrand Russell)

...как будто волшебный фонарик освещает изнутри образы на экране... - Т. С. Элиот (T.S. Eliot), Песнь любви Альфреда Прафрока

10.0. Введение

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

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

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

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

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

Алгоритмы и архитектуры, реализующие этот подход, не предполагают явного программирования. Они просто выбираются для обучения сети. В этом и состоит основное преимущество такого подхода: инвариантные свойства входной информации выявляются за счет выбора соответствующей архитектуры и метода обучения. При этом могут появляться "странные" аттракторы. Но явное программирование здесь не требуется. Именно таким системам посвящена данная глава.

Сети связей лучше всего подходят для решения следующих задач.

Классификация - определение категории или группы, к которой принадлежат

входные значения.

Распознавание образов - идентификация структуры или шаблона данных.

Реализация памяти, в том числе задача контекстной адресации памяти.

Прогнозирование, например, диагностика болезни по ее симптомам, определение

следствий на основе известных причин.

Оптимизация - поиск наилучшей структуры ограничений.

Фильтрация - выделение полезного сигнала из фонового шума, отбрасывание

несущественных компонентов сигнала.

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

В разделе 10.1 рассматривается история развития нейроподобных моделей. Здесь представлены основные компоненты, необходимые для обучения нейронной сети, включая "механический" нейрон, а также описаны некоторые исторически значимые ранние результаты в этой области, в том числе нейрон Мак-Каллока-Питтса (McCulloch-Pitts), разработанный в 1943 году. Развитие этих нейросетевых парадигм в течение последних 40 лет во многом обусловило современное состояние проблемы машинного обучения.

В разделе 10.2 в историческом контексте представлено правило обучения персептрона (perception), или дельта-правило (delta rule). Рассматривается пример, в котором персептрон выступает в роли классификатора. В разделе 10.3 вводятся сети со скрытыми слоями и освещается алгоритм обучения на основе обратного распространения ошибки (backpropagation). Такие архитектуры позволили преодолеть проблему линейной разделимости, присущую ранним нейросетевым моделям. Алгоритм обратного распространения состоит в компенсации ошибки на тех узлах многослойной сети с непрерывными пороговыми функциями, которые дают некорректный результат.

В разделе 10.4 представлены модели Кохонена [Kohonen, 1984] и Хехта-Нильсена [Hecht-Nielsen, 1987] и конкурентные методы (competitive learning) их обучения. В этих моделях векторы весовых коэффициентов используются для представления самих образов, а не мощности связей. Алгоритм обучения "победитель забирает все" (winner-takes-all) выбирает узел, образ которого (вектор весовых коэффициентов) наиболее точно соответствует входному вектору, и настраивает эти коэффициенты для обеспечения еще более точного соответствия. Это алгоритм обучения без учителя, поскольку нейрон-

436 Часть IV. Машинное обучение

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

В разделе 10.5 представлена модель обучения с подкреплением Хебба [Hebb, 1949]. Хебб высказал предположение о том, что при каждом возбуждении нейрона вследствие передачи ему импульса от другого нейрона сила связи между этими нейронами возрастает. Алгоритм обучения Хебба- это простой алгоритм настройки весов связей. Будут представлены версии этого алгоритма для обучения с учителем и без учителя, а также линейная ассоциативная память (linear associator), основанная на модели Хебба.

В разделе 10.6 вводится очень важный тип нейроподобных моделей, получивших название аттракторных сетей (attractor network). В этих сетях для циклической передачи сигналов используются обратные связи. Выходом сети является ее состояние в положении равновесия. В процессе настройки весов связей формируется множество аттракторов. При подаче на вход сети образов, относящихся к зоне притяжения аттрактора, сеть сходится к состоянию равновесия, соответствующему данному аттрактору. Следовательно, аттракторы можно использовать для хранения образов в памяти. Тогда, имея входной образ, можно получить либо ближайший из сохраненных образов либо ассоциированный с ним. Первый тип сети называется автоассоциативной (autoassociative memory), а второй - гетероассоциативной памятью (heteroassociative memory). В 1982 году физик-теоретик Джон Хопфилд (John Hopfield) разработал класс аттракторных сетей, доказательство сходимости которых сводится к минимизации функции энергии. Сети Хопфилда можно использовать для решения задач оптимизации при наличии ограничений, в частности задачи коммивояжера. При этом критерий оптимизации записывается как функция энергии системы (подраздел 10.6.4).

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

10.1. Основы теории сетей связей

10.1.1. Ранняя история

Зачастую теорию нейронных сетей считают очень современной наукой, однако ее истоки относятся к периоду ранних работ в области компьютерных наук, психологии и философии. Например, еще Джон фон Нейман пришел в восторг от теории клеточных автоматов и нейроподобного подхода к вычислениям. Первые работы в области нейросетевого обучения выполнялись под влиянием психологической теории обучения животных [Hebb, 1949]. В этом разделе будут описаны основные компоненты нейронных сетей и методы их обучения, а также представлены исторически важные ранние работы в этой области.

Основой нейронных сетей является искусственный нейрон, схема которого показана на рис. 10.1. Искусственный нейрон имеет следующую структуру.

• Входные сигналы хi. Это данные, поступающие из окружающей среды или от других активных нейронов. Диапазон входных значений для различных моделей может отличаться. Обычно входные значения являются дискретными (бинарными)

Глава 10. Машинное обучение на основе связей 437

и определяются множествами {0,1} или {-1,1} либо принимают любые вещественные значения.

Набор вещественных весовых коэффициентов w(. Весовые коэффициенты определяют силу связи между нейронами.

Уровень активации нейрона ?WiXi, который определяется взвешенной суммой

его входных сигналов.

Пороговая функция f, предназначенная для вычисления выходного значения

нейрона путем сравнения уровня активации с некоторым порогом. Пороговая

функция определяет активное или неактивное состояние нейрона.

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

Топология сети (network topology) - это шаблон, определяющий наличие связей

между отдельными нейронами. Топология является главным источником индуктивного порога.

Используемый алгоритм обучения (learning algorithm). В этой главе представлены различные алгоритмы обучения.

Схема кодирования (encoding scheme), определяющая интерпретацию данных в

сети и результатов их обработки.

Первым примером нейросетевой модели является нейрон Мак-Каллока-Питтса [McCulloch и Pitts, 1943]. На вход нейрона подаются биполярные сигналы (равные +1 или -1). Активационная функция - это пороговая зависимость, результат которой вычисляется следующим образом. Если взвешенная сумма входов не меньше нуля, выход нейрона принимается равным 1, в противном случае - -1. В своей работе Мак-Каллок и Питтс показали, как на основе таких нейронов можно построить любую логическую функцию. Следовательно, система из таких нейронов обеспечивает полную вычислительную модель.

На рис. 10.2 показан пример вычисления логических функций И и ИЛИ с помощью нейронов Мак-Каллока-Питтса. Каждый из этих нейронов имеет три входа, первые два из которых задают аргументы функции х и у, а третий, иногда называемый пороговым (bias), всегда равен 1. Весовые коэффициенты связей для входных нейронов составляют соответственно +1, +1 и - 2. Тогда для любых входных значений х и y нейрон вычисляет значение х+у-2. Если это значение меньше 0, выходным значением нейрона является

438 Часть IV. Машинное обучение

-1, в противном случае - 1. Из табл. 10.1 видно, что такой нейрон, по существу, вычисляет значение функции х¬у. Аналогично можно удостовериться в том, что второй нейрон на рис. 10.2 вычисляет значение логической функции ИЛИ.

Таблица 10.1. Модель Мак-Каллока-Питтса для вычисления функции логического И

Несмотря на то что Мак-Каллок и Питтс продемонстрировали возможности нейросетевых вычислений, реальный интерес к этой области проявился только после разработки применимых на практике алгоритмов обучения. Первые модели обучения во многом связаны с работами специалиста по психологии Д. О. Хебба (D. О. Hebb), который в 1949 году предположил, что обучение биологических существ связано с модификацией синапсов в мозгу. Он показал, что многократное возбуждение синапса приводит к повышению его чувствительности и вероятности его возбуждения в будущем. Если некоторый стимул многократно приводит к активизации группы клеток, то между этими клетками возникает сильная ассоциативная связь. Поэтому в будущем подобный стимул приведет к возбуждению тех же связей между нейронами, что в свою очередь обеспечит распознавание стимула (более точно утверждение Хебба приводится в подразделе 10.5.1). Модель обучения Хебба основана только на идее подкрепления и не учитывает забывчивость, штрафы за ошибки или износ. Современные психологи пытались реализовать модель Хебба, но не смогли получить достаточно общих результатов без добавления механизма забывчивости [Rochester и др., 1988], [Quinlan, 1991]. Модель обучения Хебба более подробно будет рассмотрена в разделе 10.5.

В следующем разделе модель нейрона Мак-Каллока-Хебба расширена за счет формирования слоев взаимосвязанных нейронов и добавления алгоритмов их взаимодействия. Первая версия такой нейроподобной структуры получила название nepcenmpona (perceptron).

10.2. Обучение персептрона

10.2.1. Алгоритм обучения персептрона

Фрэнк Розенблатт [Rosenblatt, 1958] предложил алгоритм обучения для одного типа однослойной нейронной сети, получившей название персептрона (perseptron). По способу распространения сигналов персептрон аналогичен нейрону Мак-Каллока-Хебба, пример

Глава 10. Машинное обучение на основе связей 439

которого будет описан в подразделе 10.2.2. Входные значения персептрона являются биполярными (равны -1 или 1), а вес - вещественным числом. Уровень активации персептрона вычисляется как взвешенная сумма его входов, ?xiwi-. Выходное значение персептрона вычисляется с помощью строгой пороговой функции: если уровень активации превышает или равен пороговому значению, выход персептрона принимается равным 1,

в противном случае - -1. Таким образом, выходное значение персептрона вычисляется

на основе его входных значений xi весовых коэффициентов wi, и порога t следующим образом.

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

Здесь sign(?x,w,) - выходное значение персептрона, равное +1 или -1. Разность между желаемым и реальным выходными значениями может быть равна 0, 2 или -2. Следовательно, для каждого компонента входного вектора выполняются такие действия.

Если значения желаемого и реального выхода совпадают, ничего не происходит.

Если реальное выходное значение равно -1, а желаемое - 1, то весовой коэффициент для i-го входа увеличивается на 2 cxi.

Если реальное выходное значение равно -1, а желаемое - 1, то весовой коэффициент для i-го входа уменьшается на 2сxi.

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

Первоначально появление персептрона было встречено с большим энтузиазмом. Однако в 1965 году Нильс Нильсон (Nils Nilsson) и другие исследователи выявили ограниченность модели персептрона. Они показали, что персептрон не решает целого класса достаточно сложных задач, в которых данные не являются линейно разделимыми. И хотя впоследствии появились различные усовершенствования модели персептрона, в том числе многослойные персептроны, Минский и Пейперт в своей книге "Perceptrons" доказали, что с помощью персептрона нельзя решить проблему линейной разделимости [Minsky и Papert, 1969].

Классическим примером задачи классификации, данные которой не обладают свойством линейной разделимости, является проблема "исключающего ИЛИ" (табл. 10.2). Функцию "исключающего ИЛИ" можно представить с помощью следующей таблицы истинности.

440 Часть IV. Машинное обучение

Таблица 10.2. Таблица истинности для функции "исключающее ИЛИ"

Рассмотрим персептрон с двумя входами x1 и x2 , двумя весовыми коэффициентами w1 и w2 и пороговым значением t. Для реализации этой функции сеть должна настроить весовые коэффициенты таким образом, чтобы выполнялись следующие неравенства (рис. 10.3).

w1*1+w2*1 f (из второй строки таблицы истинности), 0+w2*1 > t (из первой строки таблицы истинности), 0+0 < f (т.е. положительный порог, из последней строки таблицы истинности).

Эта система неравенств для w1 и w2 и t не имеет решения. Тем самым подтверждается, что персептрон не может решить проблему "исключающего ИЛИ". Несмотря на то что существуют многослойные сети, способные решить эту проблему (см. подраздел 10.3.3), алгоритм обучения персептрона предназначен только для обучения однослойных сетей.

Невозможность решения задачи "исключающего ИЛИ" для персептрона объясняется тем, что два класса, которые должна различать сеть, не являются линейно разделимыми (рис. 10.3). В двухмерном пространстве невозможно провести прямую, разделяющую множества точек с координатами {(0,0), (1,1)} и {(1,0), (0,1)}.

Можно считать, что входные данные сети определяют пространство. Каждый компонент входного вектора определяет направление, а каждое входное значение задает точку в этом пространстве. В задаче "исключающего ИЛИ" четыре входных вектора с координатами x1 и х2 определяют точки, показанные на рис. 10.3. Задача обучения классификации сводится к разделе-

Рис. 10.3. Задача "исключающего ИЛИ". В двухмерном пространстве нельзя провести прямую, разделяющую пары точек {(0,1), (1,0)} и {(0,0), (1,1)}

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

В результате выявления проблемы линейной разделимости направление исследований сместилось в сторону архитектур, основанных на символьном представлении, а прогресс в области нейросетевой методологии значительно замедлился. Однако дальнейшие исследования в 1970-х и 1980-х годах показали, что эта проблема является разрешимой.

В разделе 10.3 будет описан метод обучения по правилу обратного распространения, который является обобщением алгоритма обучения персептрона для многослойных сетей. Однако прежде чем переходить к изучению этого метода, рассмотрим пример сети персептронного типа, выполняющей классификацию образов. В завершение раздела 10.2 будет изложено обобщенное дельта-правило (generalized delta-rule) - обобщение алгоритма

Глава 10. Машинное обучение на основе связей 441

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

10.2.2. Пример: использование персептронной сети для классификации образов

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

Для рассматриваемого примера в блоке преобразователя и извлечения признаков на рис. 10.4 данные из предметной области задачи трансформируются в двухмерные векторы декартова пространства. На рис. 10.5 показаны результаты анализа информации, приведенной в табл. 10.3, с помощью персептрона с двумя входами. В первых двух столбцах таблицы содержатся векторы данных, используемые для обучения сети. В третьем столбце представлены ожидаемые результаты классификации, + 1 или -1, используемые для обучения сети. На рис. 10.5 показаны обучающие данные и линия разделения классов данных, полученных после предъявления обученной сети каждого входного образа.

Рис. 10.4. Полная система классификации

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

gi(х)>gj(х) для всех j, 1

В простом примере из табл. 10.3 двухмерные входные векторы делятся на два класса, первому из которых соответствует значение 1, а второму- -1.

442 Часть IV. Машинное обучение

Рис. 10.5. Данные из табл. 10.3 в двухмерном пространстве. Персептрон, описанный в подразделе 10.2.1, обеспечивает линейное разделение этого набора данных

Таблица 10.3. Набор обучающих данных для классификации с помощью персептрона

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

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

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

Глава 10. Машинное обучение на основе связей 443

назад содержание далее



ПОИСК:




© FILOSOF.HISTORIC.RU 2001–2023
Все права на тексты книг принадлежат их авторам!

При копировании страниц проекта обязательно ставить ссылку:
'Электронная библиотека по философии - http://filosof.historic.ru'