Социальные и эмерджентные модели обучения. Эволюционное алгоритмы.

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

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

 

Системы классификации и эволюционное программирование.

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

Воздействие системы классификации с внешней средой:

Сверху вниз – вход, выход, обратная связь.

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

Эволюционное программирование – см предыдущий вопрос.

 

Деревья решений

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

Область применения достаточно широка. Задачи которые они решают:

1. Описание данных.

2. Классификация.

3. Регрессия – поиск зависимостей.

 

Построение дерева решений.

Пусть задано обучающее множество Т, оно содержит объекты, каждые из которых характеризуются неким набором атрибутов m, причем один из этих атрибутов указывает на принадлежность объекта к определенному классу. Обозначим все классы и тогда возможны три ситуации:

1. Множество Т содержит 1 или более примеров, относящихся к одному из классов. В этом случае дерево решений – лист, определяющий класс решений .

2. Т не содержит ни одного примера. В этом случае дерево решений – это пустой лист и класс, к которому его нужно отнести, будет выбираться из связного с ним множества.

3. В множестве есть примеры относящиеся к разным классам, тогда множество можно разбить на ряд множеств и для этого выбрать признак и по нему произвести разделение множества Т.

 

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

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

 

 

Как разбивать на подмножества:

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

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

 

Преимущества деревьев решений.

1. Быстрый процесс обучения.

2. Генерация правил в областях, где эксперту трудно формализовать свои знания.

3. Извлечение правил на естественном языке.

4. Понятная классификационная модель.

Недостатки:

1. Размер дерева – найти «золотую середину» между ветвистостью и компактностью достаточно трудно.