Система обучающих классификаторов - Learning classifier system - Wikipedia

2D-визуализация обучения правилам LCS для аппроксимации 3D-функции. Каждый синий эллипс представляет собой отдельное правило, охватывающее часть пространства решений. (Адаптировано из изображений, взятых из XCSF[1] с разрешения Мартина Бутца)

Системы обучающих классификаторов, или же LCS, являются парадигмой машинное обучение на основе правил методы, которые объединяют компонент обнаружения (например, обычно генетический алгоритм ) с обучающим компонентом (выполняющим либо контролируемое обучение, обучение с подкреплением, или же обучение без учителя ).[2] Системы обучающихся классификаторов стремятся идентифицировать набор контекстно-зависимых правил, которые коллективно хранят и применяют знания в кусочно способ делать прогнозы (например, моделирование поведения,[3] классификация,[4][5] сбор данных,[5][6][7] регресс,[8] аппроксимация функции,[9] или же стратегия игры ). Такой подход позволяет комплексно пространства решений быть разбитым на более мелкие и простые части.

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

Методология

Архитектура и компоненты данной системы обучающих классификаторов могут быть весьма разнообразными. Полезно думать о LCS как о машине, состоящей из нескольких взаимодействующих компонентов. Компоненты могут быть добавлены или удалены, или существующие компоненты могут быть изменены / заменены в соответствии с требованиями данной проблемной области (например, алгоритмические строительные блоки) или для того, чтобы алгоритм был достаточно гибким для работы во многих различных проблемных областях. В результате парадигма LCS может гибко применяться ко многим проблемным областям, которые требуют машинное обучение. Основные различия между реализациями LCS следующие: (1) архитектура в стиле Мичиган и архитектура в стиле Питтсбурга,[10] (2) обучение с подкреплением против. контролируемое обучение, (3) инкрементное обучение против пакетного обучения, (4) онлайн обучение против. автономное обучение, (5) приспособленность, основанная на силе, и приспособленность, основанная на точности, и (6) полное отображение действий против отображения лучших действий. Эти подразделения не обязательно являются взаимоисключающими. Например, XCS,[11] самый известный и наиболее изученный алгоритм LCS в стиле Мичиган, был разработан для обучения с подкреплением, но также может выполнять обучение с учителем, применяет инкрементное обучение, которое может быть как онлайн, так и офлайн, применяет фитнес на основе точности и стремится генерировать законченное действие отображение.

Элементы общего алгоритма LCS

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

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

Среда

Окружающая среда - это источник данных, на которых обучается LCS. Это может быть офлайн, конечный набор обучающих данных (характеристика сбор данных, классификация, или проблема регрессии), или последовательный онлайн-поток живых обучающих экземпляров. Предполагается, что каждый обучающий экземпляр включает некоторое количество Особенности (также называемый атрибуты, или же независимые переменные ) и одиночный конечная точка представляющий интерес (также называемый учебный класс, действие, фенотип, прогноз, или же зависимая переменная ). Часть обучения LCS может включать выбор функции, поэтому не все функции обучающих данных должны быть информативными. Набор значений характеристик экземпляра обычно называют государственный. Для простоты возьмем пример проблемной области с Булево /двоичный особенности и Булево /двоичный учебный класс. Для систем в стиле Мичиган один экземпляр из среды обучается в каждом цикле обучения (т.е. инкрементное обучение). Системы в стиле Питтсбурга выполняют пакетное обучение, при котором наборы правил оцениваются на каждой итерации по большей части или по всем обучающим данным.

Правило / классификатор / популяция

Правило - это контекстно-зависимая связь между значениями состояния и некоторым прогнозом. Правила обычно имеют форму выражения {IF: THEN} (например, {IF 'condition' THEN 'action'}, или, как более конкретный пример, {ЕСЛИ "красный" И "восьмиугольник" ТО "стоп-сигнал"}). Критическая концепция как в LCS, так и в машинном обучении на основе правил заключается в том, что отдельное правило само по себе не является моделью, поскольку правило применимо только тогда, когда его условие выполнено. Думайте о правиле как о «локальной модели» пространства решений.

Правила могут быть представлены разными способами для обработки различных типов данных (например, двоичные, дискретные, порядковые, непрерывные). Для заданных двоичных данных LCS традиционно применяет троичное представление правил (т.е. правила могут включать 0, 1 или '#' для каждой функции в данных). Символ «безразлично» (например, «#») служит подстановочным знаком в условии правила, разрешающем правила и систему в целом для обобщения взаимосвязей между функциями и целевой конечной точкой, которые должны быть предсказаны. Рассмотрим следующее правило (# 1 ### 0 ~ 1) (т.е. условие ~ действие). Это правило можно интерпретировать так: ЕСЛИ вторая характеристика = 1 И шестая характеристика = 0, ТО предсказание класса = 1. Мы бы сказали, что вторая и шестая характеристики были указаны в этом правиле, а остальные были обобщены. Это правило и соответствующее прогнозирование применимы только к экземпляру, когда экземпляр правила удовлетворяет его условиям. Это чаще называют соответствием. В LCS в стиле Мичиган каждое правило имеет свою пригодность, а также ряд других связанных с ним параметров правила, которые могут описывать количество существующих копий этого правила (т. Е. многочисленность), возраст правила, его точность или точность прогнозов вознаграждения, а также другую описательную или экспериментальную статистику. Правило вместе с его параметрами часто называют классификатор. В системах в стиле Мичиган классификаторы содержатся в численность населения [P], для которого установлено максимальное количество классификаторов. В отличие от большинства стохастический алгоритмы поиска (например, эволюционные алгоритмы ), Популяции LCS начинаются пустыми (т.е. нет необходимости случайным образом инициализировать популяцию правил). Вместо этого классификаторы будут первоначально представлены населению с закрывающим механизмом.

В любом LCS обученная модель представляет собой набор правил / классификаторов, а не какое-либо отдельное правило / классификатор. В LCS в стиле Мичиган вся обученная (и, необязательно, уплотненная) совокупность классификаторов формирует модель прогнозирования.

Соответствие

Одним из наиболее важных и часто трудоемких элементов LCS является процесс согласования. Первый шаг в цикле обучения LCS берет один обучающий экземпляр из среды и передает его в [P], где происходит сопоставление. На втором шаге каждое правило в [P] теперь сравнивается с обучающим экземпляром, чтобы увидеть, какие правила соответствуют (т. Е. Контекстуально релевантны текущему экземпляру). На третьем шаге все правила соответствия перемещаются в набор совпадений [M]. Правило соответствует обучающему экземпляру, если все значения функций, указанные в условии правила, эквивалентны соответствующему значению функции в обучающем экземпляре. Например, предполагая, что обучающий экземпляр - (001001 ~ 0), эти правила будут соответствовать: (### 0 ## ~ 0), (00 ### 1 ~ 0), (# 01001 ~ 1), но эти правила не будет (1 ##### ~ 0), (000 ## 1 ~ 0), (# 0 # 1 # 0 ~ 1). Обратите внимание, что при сопоставлении конечная точка / действие, указанное правилом, не принимается во внимание. В результате набор соответствий может содержать классификаторы, предлагающие конфликтующие действия. На четвертом шаге, поскольку мы выполняем контролируемое обучение, [M] делится на правильный набор [C] и неправильный набор [I]. Правило сопоставления попадает в правильный набор, если оно предлагает правильное действие (на основе известного действия обучающего экземпляра), в противном случае оно попадает в [I]. В LCS с обучением с подкреплением вместо этого будет сформирован набор действий [A], поскольку правильное действие неизвестно.

Покрытие

На этом этапе цикла обучения, если ни один из классификаторов не попал ни в [M], ни в [C] (как это было бы в случае, когда совокупность начинается пустой), применяется механизм покрытия (пятый шаг). Покрытие - это форма инициализация умного населения онлайн. Покрытие случайным образом генерирует правило, которое соответствует текущему обучающему экземпляру (а в случае контролируемого обучения это правило также генерируется с правильным действием. Предполагая, что обучающий экземпляр равен (001001 ~ 0), покрытие может генерировать любое из следующих правил: (# 0 # 0 ## ~ 0), (001001 ~ 0), (# 010 ## ~ 0). Покрытие не только гарантирует, что в каждом цикле обучения есть хотя бы одно правильное правило соответствия в [C], но и что любое правило, инициализированное в совокупности, будет соответствовать по крайней мере одному обучающему экземпляру.Это не позволяет LCS исследовать пространство поиска правил, которые не соответствуют ни одному обучающему экземпляру.

Обновление параметров / присвоение кредитов / обучение

На шестом шаге параметры правила любого правила в [M] обновляются, чтобы отразить новый опыт, полученный в текущем обучающем экземпляре. В зависимости от алгоритма LCS на этом этапе может произойти ряд обновлений. Для обучения с учителем мы можем просто обновить точность / ошибку правила. Точность / ошибка правила отличается от точности / ошибки модели, поскольку она рассчитывается не для всех обучающих данных, а только для всех совпадающих экземпляров. Точность правила вычисляется путем деления количества раз, когда правило было в правильном наборе [C], на количество раз, когда оно было в наборе совпадений [M]. Точность правил можно рассматривать как «локальную точность». Здесь также обновляется соответствие правилу и обычно рассчитывается как функция точности правила. Понятие фитнеса взято прямо из классических генетические алгоритмы. Имейте в виду, что существует множество вариантов того, как LCS обновляет параметры для выполнения присвоения кредитов и обучения.

Потребление

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

Открытие правил / генетический алгоритм

На восьмом этапе LCS принимает высокоэлитного генетический алгоритм (GA), который выберет два родительских классификатора на основе приспособленности (выживаемость наиболее приспособленных). Родители выбираются из [C], как правило, с использованием выбор турнира. Некоторые системы применили выбор колеса рулетки или детерминированный отбор, и имеют по-разному выбранные родительские правила либо из [P] - панмиктический выбор, либо из [M]). Кроссовер и мутация теперь применяются операторы для генерации двух новых правил потомков. В этот момент правила для родителей и потомков возвращаются в [P]. LCS генетический алгоритм является очень элитарным, поскольку на каждой итерации обучения сохраняется подавляющее большинство населения. В качестве альтернативы обнаружение правил может быть выполнено каким-либо другим методом, например оценка алгоритма распределения, но ГА - безусловно, наиболее распространенный подход. Эволюционные алгоритмы, такие как GA, используют стохастический поиск, что делает LCS стохастическим алгоритмом. LCS стремится грамотно исследовать пространство поиска, но не выполняет исчерпывающий поиск комбинаций правил и не гарантирует схождения к оптимальному решению.

Удаление

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

Обучение персонала

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

Правило уплотнения

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

Прогноз

Независимо от того, применялось ли уплотнение правил или нет, выходом алгоритма LCS является совокупность классификаторов, которые могут применяться для прогнозирования ранее невидимых экземпляров. Механизм прогнозирования не является частью самого контролируемого цикла обучения LCS, однако он будет играть важную роль в цикле обучения LCS с обучением с подкреплением. А пока мы рассмотрим, как можно применить механизм прогнозирования для прогнозирования тестовых данных. При прогнозировании компоненты обучения LCS отключаются, чтобы совокупность не продолжала учиться на входящих данных тестирования. Экземпляр теста передается в [P], где набор соответствий [M] формируется как обычно. На этом этапе набор совпадений по-другому передается в массив прогнозов. Правила в наборе совпадений могут предсказывать различные действия, поэтому применяется схема голосования. В простой схеме голосования побеждает действие с наиболее сильными поддерживающими «голосами» из правил сопоставления и становится выбранным прогнозом. Не все правила имеют равное право голоса. Скорее сила голоса за одно правило обычно пропорциональна его количеству и пригодности. Эта схема голосования и характер того, как хранятся знания LCS, предполагают, что алгоритмы LCS неявно учащиеся ансамбля.

Интерпретация

Индивидуальные правила LCS обычно являются удобочитаемым выражением IF: THEN. Правила, составляющие модель прогнозирования LCS, могут быть ранжированы по различным параметрам правил и проверены вручную. Также были предложены глобальные стратегии для управления открытием знаний с использованием статистических и графических данных.[12][13] Что касается других передовых подходов к машинному обучению, таких как искусственные нейронные сети, случайные леса, или же генетическое программирование, обучающие системы классификаторов особенно хорошо подходят для задач, требующих интерпретируемых решений.

История

Ранние годы

Джон Генри Холланд был наиболее известен своей работой по популяризации генетические алгоритмы (GA), через его новаторскую книгу «Адаптация в естественных и искусственных системах»[14] в 1975 году и его формализация Теорема схемы Холланда. В 1976 году Холланд концептуализировал расширение концепции ГА до того, что он назвал «когнитивной системой»,[15] и предоставил первое подробное описание того, что станет известно как первая система обучающихся классификаторов, в статье «Когнитивные системы, основанные на адаптивных алгоритмах».[16] Эта первая система, названная Когнитивная система один (CS-1) был задуман как инструмент моделирования, предназначенный для моделирования реальной системы (т.е. среда) с неизвестной базовой динамикой с использованием набора понятных человеку правил. Цель заключалась в том, чтобы набор правил выполнял онлайн-машинное обучение адаптироваться к среде на основе нечастых выплат / вознаграждений (например, обучение с подкреплением) и применять эти правила для создания поведения, соответствующего реальной системе. Эта ранняя амбициозная реализация позже была сочтена слишком сложной и дала противоречивые результаты.[2][17]

Начиная с 1980 г. Кеннет де Йонг и его ученик Стивен Смит применили другой подход к машинному обучению на основе правил. (LS-1), где обучение рассматривалось как автономный процесс оптимизации, а не как процесс онлайн-адаптации.[18][19][20] Этот новый подход был больше похож на стандартный генетический алгоритм, но развил независимые наборы правил. С тех пор методы LCS, вдохновленные структурой онлайн-обучения, представленной Голландией в Мичиганском университете, стали называть LCS в мичиганском стиле, а те, кого вдохновляли Смит и Де Йонг из Университета Питтсбурга, назывались LCS в Питтсбургском стиле.[2][17] В 1986 году Голландия разработала то, что на следующее десятилетие будет считаться стандартной системой LCS в мичиганском стиле.[21]

Другие важные концепции, которые возникли на заре исследований LCS, включали (1) формализацию алгоритм бригады ведра (BBA) для присвоения кредита / обучения,[22] (2) выбор родительских правил из общей «экологической ниши» (т.е. набор совпадений [M]), а не от всего численность населения [П],[23] (3) покрытие, впервые представленный как Создайте оператор[24] (4) формализация набор действий [A],[24] (5) упрощенная архитектура алгоритма,[24] (6) силовой фитнес,[21] (7) рассмотрение одноэтапных или контролируемых задач обучения[25] и введение правильный набор [C],[26] (8) фитнес на основе точности[27] (9) комбинация нечеткой логики с LCS[28] (который позже породил родословную нечеткие алгоритмы LCS), (10) обнадеживающие цепи с длинным действием и иерархии по умолчанию для повышения производительности на многоэтапных задачах,[29][30][31] (11) изучение скрытое обучение (который позже вдохновил новую ветвь системы упреждающих классификаторов (ACS)[32]), (12) введение первого Q-обучение -подобная техника присвоения кредитов.[33] Хотя не все эти концепции применяются в современных алгоритмах LCS, каждая из них была вехой в развитии парадигмы LCS.

Революция

Интерес к обучающим системам классификаторов возродился в середине 1990-х годов во многом благодаря двум событиям; развитие Q-Learning алгоритм[34] за обучение с подкреплением и введение Стюартом Уилсоном значительно упрощенных архитектур LCS в стиле Мичиган.[11][35] Уилсона Система классификаторов нулевого уровня (ZCS)[35] сфокусирован на повышении алгоритмической понятности на основе стандартной реализации LCS Hollands.[21] Частично это было сделано путем удаления правил назначения ставок и внутреннего списка сообщений, необходимых для первоначального присвоения кредита BBA, и замены его гибридным BBA /Q-Learning стратегия. ZCS продемонстрировала, что гораздо более простая архитектура LCS может работать так же хорошо, как и оригинальные, более сложные реализации. Тем не менее, ZCS по-прежнему страдает недостатками производительности, в том числе быстрым распространением универсальных классификаторов.

В 1995 году Уилсон опубликовал свою знаменательную статью «Пригодность классификатора на основе точности», в которой он представил систему классификатора. XCS.[11] XCS взяла упрощенную архитектуру ZCS и добавила основанную на точности приспособленность, нишевый GA (действующий в наборе действий [A]), явный механизм обобщения, называемый подчинение, и адаптация Q-Learning переуступка кредита. XCS был популяризирован своей способностью достигать оптимальной производительности при разработке точных и максимально общих классификаторов, а также своей впечатляющей гибкостью задач (способной выполнять оба обучение с подкреплением и контролируемое обучение ). Позднее XCS стал самым известным и наиболее изученным алгоритмом LCS и определил новое семейство LCS на основе точности. ZCS альтернативно стал синонимом LCS на основе прочности. XCS также важен, потому что он успешно преодолел разрыв между LCS и областью обучение с подкреплением. После успеха XCS, LCS позже были описаны как системы обучения с подкреплением, наделенные способностью к обобщению.[36] Обучение с подкреплением обычно стремится изучить функцию значения, которая отображает полное представление пространства состояния / действия. Точно так же дизайн XCS заставляет его формировать всеобъемлющее и точное представление о проблемном пространстве (т.е. полная карта) вместо того, чтобы сосредоточиться на нишах с высокой отдачей в окружающей среде (как это было в случае LCS, основанного на силе). Концептуально полные карты отражают не только то, что вам следует делать или что правильно, но также и то, что вам не следует делать или что неправильно. Иными словами, большинство LCS, основанных на силе, или LCS с исключительно контролируемым обучением ищут набор правил эффективных обобщений в форме карта лучших действий (или частичная карта). С тех пор сравнения между физической подготовкой на основе силы и точности и картами полных и лучших действий были изучены более подробно.[37][38]

По следам XCS

XCS вдохновил на разработку целого нового поколения алгоритмов и приложений LCS. В 1995 году Конгдон первым применил LCS в реальных условиях. эпидемиологический исследования болезни [39] за которым следовал Холмс, который разработал БУЛ ++,[40] EpiCS,[41] и позже EpiXCS[42] за эпидемиологический классификация. Эти ранние работы вдохновили более поздний интерес к применению алгоритмов LCS для сложных и крупномасштабных сбор данных задачи воплощены биоинформатика Приложения. В 1998 году Штольцманн представил системы упреждающих классификаторов (САУ) который включал правила в форме «условие-действие-эффект», а не классическое представление «условие-действие».[32] ACS была разработана для прогнозирования последствий для восприятия действия во всех возможных ситуациях в окружающей среде. Другими словами, система развивает модель, которая не только определяет, что делать в данной ситуации, но также предоставляет информацию о том, что произойдет после того, как будет выполнено определенное действие. Это семейство алгоритмов LCS лучше всего подходит для многоэтапных задач, планирования, ускорения обучения или устранения неоднозначности перцептивного псевдонима (т.е. когда одно и то же наблюдение получается в разных состояниях, но требует разных действий). Позднее Бутц продолжил это предвосхищающее семейство LCS, разработав ряд улучшений исходного метода.[43] В 2002 году Уилсон представил XCSF, добавление вычисляемого действия для выполнения аппроксимации функции.[44] В 2003 году Bernado-Mansilla представила Система контролируемых классификаторов (UCS), который специализировал алгоритм XCS для задачи контролируемое обучение, пошаговые задачи и формирование набора лучших действий. UCS удалила обучение с подкреплением Стратегия в пользу простого, основанного на точности правила пригодности, а также фаз изучения / использования, характерных для многих учащихся с подкреплением. Компания Bull представила простой LCS, основанный на точности (YCS)[45] и простой силовой LCS Система минимального классификатора (MCS)[46] для лучшего теоретического понимания структуры LCS. Представлен Bacardit GAssist[47] и BioHEL,[48] LCS в стиле Питтсбурга, предназначенные для сбор данных и масштабируемость к большим наборам данных в биоинформатика Приложения. В 2008 году Другович опубликовал книгу под названием «Проектирование и анализ обучаемых систем классификаторов», включающую некоторые теоретические исследования алгоритмов LCS.[49] Бутц представил первое правило визуализации онлайн-обучения в GUI для XCSF[1] (см. изображение вверху этой страницы). Урбанович расширил структуру UCS и представил ExSTraCS, специально разработан для контролируемое обучение в шумных проблемных областях (например, эпидемиология и биоинформатика).[50] ExSTraCS интегрировал (1) экспертные знания для управления охватом и генетическим алгоритмом в отношении важных характеристик данных,[51] (2) форма долговременной памяти, называемая отслеживанием атрибутов,[52] позволяя более эффективно изучать и характеризовать разнородные шаблоны данных, и (3) гибкое представление правил, подобное смешанному дискретно-непрерывному представлению списка атрибутов Bacardit.[53] И Бакардит, и Урбанович исследовали стратегии статистики и визуализации для интерпретации правил LCS и выполнения поиска знаний для интеллектуального анализа данных.[12][13] Браун и Икбал исследовали концепцию повторного использования строительных блоков в виде фрагментов кода и первыми решили проблему эталонного теста 135-битного мультиплексора, впервые изучив полезные строительные блоки из более простых задач мультиплексора.[54] ExSTraCS 2.0 позже был представлен для улучшения масштабируемости LCS в стиле Мичиган, впервые успешно решив проблему эталонного теста 135-битного мультиплексора.[5] N-битный мультиплексор проблема очень эпистатический и неоднородный, что делает его очень сложным машинное обучение задача.

Варианты

Система классификаторов обучения в стиле Мичиган

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

Система классификаторов в стиле Питтсбурга

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

Гибридные системы

Также были предложены системы, которые стремятся объединить ключевые сильные стороны обеих систем.

Преимущества

  • Адаптивный: они могут адаптироваться к меняющейся среде в случае онлайн-обучения.
  • Без модели: они делают ограниченные предположения об окружающей среде или шаблонах ассоциаций в данных.
    • Они могут моделировать сложные, эпистатические, гетерогенные или распределенные основные паттерны, не полагаясь на предварительные знания.
    • Они не делают никаких предположений о количестве прогностических и непредсказуемых функций в данных.
  • Ensemble Learner: к конкретному экземпляру не применяется единственная модель, которая универсально дает прогноз. Вместо этого релевантный и часто противоречивый набор правил вносит свой вклад в «голосование», которое можно интерпретировать как нечеткое предсказание.
  • Стохастический обучающийся: недетерминированное обучение выгодно в крупномасштабных задачах или задачах высокой сложности, когда детерминированное или исчерпывающее обучение становится трудноразрешимым.
  • Неявно многоцелевой: правила развиваются в сторону точности с неявным и явным давлением, поощряющим максимальную общность / простоту. Это неявное обобщающее давление уникально для LCS. Фактически, более общие правила будут чаще появляться в наборах соответствий. В свою очередь, у них есть более частая возможность быть избранными в качестве родителей и передать свои более общие (геномы) правилам потомства.
  • Интерпретируемый: в интересах интеллектуального анализа данных и обнаружения знаний отдельные правила LCS логичны, и их можно сделать интерпретируемыми операторами IF: THEN. Также были введены эффективные стратегии, позволяющие открывать глобальные знания, идентифицирующие важные особенности и закономерности ассоциации из совокупности правил в целом.[12]
  • Гибкое приложение
    • Одно- или многоэтапные задачи
    • Обучение с учителем, с подкреплением или без учителя
    • Бинарный класс и мультиклассовая классификация
    • Регресс
    • Дискретные или непрерывные элементы (или некоторое сочетание обоих типов)
    • Чистые или шумные проблемные домены
    • Сбалансированные или несбалансированные наборы данных.
    • Учитывает отсутствующие данные (т.е. отсутствующие значения функций в обучающих примерах)

Недостатки

  • Ограниченная доступность программного обеспечения: существует ограниченное количество доступных реализаций LCS с открытым исходным кодом, и еще меньше разработано, чтобы быть удобными для пользователя или доступными для практиков машинного обучения.
  • Интерпретация: хотя алгоритмы LCS, безусловно, более интерпретируемы, чем некоторые продвинутые изучающие машины, пользователи должны интерпретировать набор правил (иногда большие наборы правил для понимания модели LCS). Методы уплотнения правил и стратегии интерпретации остаются областью активных исследований.
  • Теория / Доказательства сходимости: за алгоритмами LCS стоит относительно небольшой объем теоретической работы. Вероятно, это связано с их относительной алгоритмической сложностью (с применением ряда взаимодействующих компонентов), а также их стохастической природой.
  • Переоснащение: как и любой машинный обучающийся, LCS может страдать от переоснащение несмотря на неявное и явное давление обобщения.
  • Параметры запуска: LCS часто имеют множество параметров запуска, которые необходимо учитывать / оптимизировать. Как правило, большинство параметров можно оставить на усмотрение сообщества по умолчанию, за исключением двух критических параметров: максимального размера популяции правил и максимального количества итераций обучения. Оптимизация этих параметров, вероятно, будет очень проблемной.
  • Известность: несмотря на свой возраст, алгоритмы LCS до сих пор не получили широкой известности даже в сообществах машинного обучения. В результате алгоритмы LCS редко рассматриваются по сравнению с другими общепринятыми подходами к машинному обучению. Вероятно, это связано со следующими факторами: (1) LCS - относительно сложный алгоритмический подход, (2) LCS, моделирование на основе правил - это парадигма моделирования, отличная от почти всех других подходов к машинному обучению. (3) Программные реализации LCS встречаются не так часто.
  • В вычислительном отношении дорого: хотя алгоритмы LCS, безусловно, более осуществимы, чем некоторые исчерпывающие подходы, они могут быть дорогими в вычислительном отношении. Для простых линейных задач обучения нет необходимости применять LCS. Алгоритмы LCS лучше всего подходят для сложных проблемных пространств или проблемных пространств, в которых мало предварительных знаний.

Проблемные домены

  • Адаптивное управление
  • Сбор данных
  • Инженерный дизайн
  • Выбор функции
  • Аппроксимация функций
  • Game-Play
  • Классификация изображений
  • Обработка знаний
  • Медицинский диагноз
  • Моделирование
  • Навигация
  • Оптимизация
  • Прогноз
  • Запрос
  • Робототехника
  • Маршрутизация
  • Правило-индукция
  • Планирование
  • Стратегия

Терминология

Название "Learning Classifier System (LCS)" немного вводит в заблуждение, поскольку существует множество машинное обучение алгоритмы, которые «учатся классифицировать» (например, деревья решений, искусственные нейронные сети ), но не являются LCS. Термин 'машинное обучение на основе правил (RBML ) 'полезен, поскольку он более четко отражает существенный компонент этих систем, основанный на правилах, но он также распространяется на методы, которые не считаются LCS (например, изучение правил ассоциации, или же искусственная иммунная система ). Более общие термины, такие как «машинное обучение на основе генетики» и даже «генетический алгоритм».[39] также использовались для обозначения того, что было бы более характерно определено как система обучающихся классификаторов. Из-за их сходства с генетические алгоритмы Системы обучающихся классификаторов Питтсбургского стиля иногда в общем называют «генетическими алгоритмами». Помимо этого, некоторые алгоритмы LCS или тесно связанные методы называются «когнитивными системами»,[16] 'адаптивные агенты', 'производственные системы ', или в общем как «система классификаторов».[55][56] Такое изменение терминологии вносит некоторую путаницу в поле зрения.

Вплоть до 2000-х годов почти все методы системы обучающих классификаторов разрабатывались с учетом задач обучения с подкреплением. В результате термин «обучающая система классификаторов» обычно определялся как комбинация обучения с подкреплением «методом проб и ошибок» с глобальным поиском генетического алгоритма. Интерес к приложениям для обучения с учителем и даже к обучению без учителя с тех пор расширили использование и определение этого термина.

Смотрите также

Рекомендации

  1. ^ а б Стальф, Патрик О .; Бутц, Мартин В. (01.02.2010). «JavaXCSF: Система обучающих классификаторов XCSF на Java». SIGEVOlution. 4 (3): 16–19. Дои:10.1145/1731888.1731890. ISSN  1931-8499. S2CID  16861908.
  2. ^ а б c Урбанович, Райан Дж .; Мур, Джейсон Х. (22 сентября 2009 г.). «Обучающие системы классификаторов: полное введение, обзор и план действий». Журнал искусственной эволюции и приложений. 2009: 1–25. Дои:10.1155/2009/736398. ISSN  1687-6229.
  3. ^ Дориго, Марко (1995). «Alecsys и AutonoMouse: обучение управлению настоящим роботом с помощью распределенных систем классификаторов». Машинное обучение. 19 (3): 209–240. Дои:10.1007 / BF00996270. ISSN  0885-6125.
  4. ^ Бернадо-Мансилла, Эстер; Гаррелл-Гуиу, Хосеп М. (01.09.2003). «Системы классификаторов обучения на основе точности: модели, анализ и приложения к задачам классификации». Эволюционные вычисления. 11 (3): 209–238. Дои:10.1162/106365603322365289. ISSN  1063-6560. PMID  14558911. S2CID  9086149.
  5. ^ а б c Урбанович, Райан Дж .; Мур, Джейсон Х. (2015-04-03). «ExSTraCS 2.0: описание и оценка масштабируемой системы классификаторов обучения». Эволюционный интеллект. 8 (2–3): 89–116. Дои:10.1007 / s12065-015-0128-8. ISSN  1864-5909. ЧВК  4583133. PMID  26417393.
  6. ^ Бернадо, Эстер; Ллора, Ксавьер; Гаррелл, Хосеп М. (07.07.2001). Ланци, Пьер Лука; Штольцманн, Вольфганг; Уилсон, Стюарт В. (ред.). Достижения в системах обучающих классификаторов. Конспект лекций по информатике. Springer Berlin Heidelberg. стр.115 –132. Дои:10.1007/3-540-48104-4_8. ISBN  9783540437932.
  7. ^ Бакардит, Жауме; Бутц, Мартин В. (2007-01-01). Ковач, Тим; Ллора, Ксавьер; Такадама, Кейки; Ланци, Пьер Лука; Штольцманн, Вольфганг; Уилсон, Стюарт В. (ред.). Системы обучающих классификаторов. Конспект лекций по информатике. Springer Berlin Heidelberg. стр.282 –290. CiteSeerX  10.1.1.553.4679. Дои:10.1007/978-3-540-71231-2_19. ISBN  9783540712305.
  8. ^ Урбанович, Райан; Рамананд, Ниранджан; Мур, Джейсон (01.01.2015). Непрерывный анализ данных конечных точек с помощью ExSTraCS: контролируемая обучающая классификаторная система. Труды сопутствующей публикации Ежегодной конференции по генетическим и эволюционным вычислениям 2015 г.. GECCO Companion '15. Нью-Йорк, Нью-Йорк, США: ACM. С. 1029–1036. Дои:10.1145/2739482.2768453. ISBN  9781450334884. S2CID  11908241.
  9. ^ Butz, M. V .; Lanzi, P. L .; Уилсон, С. В. (1 июня 2008 г.). «Аппроксимация функций с помощью XCS: гиперэллипсоидальные условия, рекурсивные методы наименьших квадратов и сжатие». IEEE Transactions по эволюционным вычислениям. 12 (3): 355–376. Дои:10.1109 / TEVC.2007.903551. ISSN  1089-778X. S2CID  8861046.
  10. ^ Введение в машинное обучение на основе правил: практическое руководство, Райан Дж. Урбанович и Уилл Браун, см. Стр. 72-73, где сравнивается архитектура в стиле Мичиган и архитектура в стиле Питтсбурга.
  11. ^ а б c Уилсон, Стюарт В. (1995-06-01). «Фитнес классификатора по точности». Evol. Вычислить. 3 (2): 149–175. CiteSeerX  10.1.1.363.2210. Дои:10.1162 / evco.1995.3.2.149. ISSN  1063-6560. S2CID  18341635.
  12. ^ а б c Urbanowicz, R.J .; Granizo-Mackenzie, A .; Мур, Дж. Х. (01.11.2012). «Конвейер анализа со статистическими и визуализационными открытиями знаний для систем классификаторов обучения в стиле Мичиган». Журнал IEEE Computational Intelligence Magazine. 7 (4): 35–45. Дои:10.1109 / MCI.2012.2215124. ISSN  1556-603X. ЧВК  4244006. PMID  25431544.
  13. ^ а б Бакардит, Жауме; Ллора, Ксавьер (2013). «Крупномасштабный интеллектуальный анализ данных с использованием машинного обучения на основе генетики». Междисциплинарные обзоры Wiley: интеллектуальный анализ данных и открытие знаний. 3 (1): 37–61. Дои:10.1002 / widm.1078. S2CID  43062613.
  14. ^ Холланд, Джон (1975). Адаптация в естественных и искусственных системах: вводный анализ с приложениями к биологии, контролю и искусственному интеллекту. Мичиган Пресс. ISBN  9780262581110.
  15. ^ Холланд JH (1976) Адаптация. В: Rosen R, Snell F (eds) Progress in теоретической биологии, том 4. Academic Press, New York, стр. 263–293.
  16. ^ а б Холланд Дж. Х., Райтман Дж. С. (1978) Когнитивные системы, основанные на адаптивных алгоритмах Перепечатано в: Эволюционные вычисления. Летопись окаменелостей. В: Дэвид Б.Ф. (редактор) IEEE Press, Нью-Йорк, 1998. ISBN  0-7803-3481-7
  17. ^ а б Ланци, Пьер Лука (2008-02-08). «Обучающие системы классификаторов: тогда и сейчас». Эволюционный интеллект. 1 (1): 63–82. Дои:10.1007 / s12065-007-0003-3. ISSN  1864-5909. S2CID  27153843.
  18. ^ Смит С. (1980) Система обучения, основанная на генетических адаптивных алгоритмах. Кандидат наук. диссертация, факультет компьютерных наук, университет Питтсбурга
  19. ^ Смит С (1983) Гибкое обучение эвристике решения проблем с помощью адаптивного поиска. В кн .: Восьмая международная совместная конференция по искусственному интеллекту. Морган Кауфманн, Los Altos, стр. 421–425.
  20. ^ Де Йонг К.А. (1988) Обучение с помощью генетических алгоритмов: обзор. Mach Learn 3: 121–138
  21. ^ а б c Холланд, Джон Х. «Избегая нестабильности: возможности универсальных алгоритмов обучения применительно к параллельной системе, основанной на правилах». Машинное обучение(1986): 593-623.
  22. ^ Холланд, Джон Х. (1 января 1985 г.). Характеристики ковшовой бригады. Труды 1-й Международной конференции по генетическим алгоритмам. Хиллсдейл, Нью-Джерси, США: L. Erlbaum Associates Inc., стр. 1–7. ISBN  978-0805804263.
  23. ^ Букер, Л. (1 января 1982 г.). Интеллектуальное поведение как адаптация к рабочей среде (Тезис). Университет Мичигана.
  24. ^ а б c Уилсон, С. В. "Рост знаний в искусственном животном. Труды Первой Международной конференции по генетическим алгоритмам и их приложениям »(1985).
  25. ^ Уилсон, Стюарт В. (1987). «Системы классификаторов и проблема аниматов». Машинное обучение. 2 (3): 199–228. Дои:10.1007 / BF00058679. ISSN  0885-6125.
  26. ^ Бонелли, Пьер; Пароди, Александр; Сен, Сандип; Уилсон, Стюарт (01.01.1990). NEWBOOLE: быстрая система GBML. Труды Седьмой Международной конференции (1990 г.) по машинному обучению. Сан-Франциско, Калифорния, США: Morgan Kaufmann Publishers Inc., стр.153–159. ISBN  978-1558601413.
  27. ^ Фрей, Питер В .; Сланец, Дэвид Дж. (1991). «Распознавание букв с помощью адаптивных классификаторов голландского типа». Машинное обучение. 6 (2): 161–182. Дои:10.1007 / BF00114162. ISSN  0885-6125.
  28. ^ Валенсуэла-Рендон, Мануэль. "Система нечетких классификаторов: система классификаторов для непрерывно изменяющихся переменных." В ICGA, стр. 346-353. 1991 г.
  29. ^ Риоло, Рик Л. (1988-01-01). Эмпирические исследования иерархий по умолчанию и последовательностей правил в обучающих системах классификаторов (Тезис). Анн-Арбор, Мичиган, США: Мичиганский университет.
  30. ^ Р.Л., Риоло (1 января 1987 г.). «Ковшовая бригада. I. Длинные последовательности классификаторов». Генетические алгоритмы и их приложения: материалы второй международной конференции по генетическим алгоритмам: 28–31 июля 1987 г., Массачусетский технологический институт, Кембридж, Массачусетс..
  31. ^ Р.Л., Риоло (1 января 1987 г.). «Производительность бригады ведра. II. Иерархия по умолчанию». Генетические алгоритмы и их приложения: материалы второй международной конференции по генетическим алгоритмам: 28–31 июля 1987 г., Массачусетский технологический институт, Кембридж, Массачусетс..
  32. ^ а б W. Stolzmann, "Системы упреждающих классификаторов", в Proceedings of the 3 Annual Genetic Programming Conference, pp.658–664, 1998.
  33. ^ Риоло, Рик Л. (01.01.1990). Предварительное планирование и скрытое обучение в системе классификаторов. Труды Первой Международной конференции по моделированию адаптивного поведения от животных к аниматам. Кембридж, Массачусетс, США: MIT Press. С. 316–326. ISBN  978-0262631389.
  34. ^ Уоткинс, Кристофер Джон Корниш Хеллаби. «Учимся на отсроченных наградах». Кандидат наук, Кембриджский университет, 1989.
  35. ^ а б Уилсон, Стюарт В. (1994-03-01). «ZCS: система классификаторов нулевого уровня». Эволюционные вычисления. 2 (1): 1–18. CiteSeerX  10.1.1.363.798. Дои:10.1162 / evco.1994.2.1.1. ISSN  1063-6560. S2CID  17680778.
  36. ^ Ланци, П. Л. (2002). «Изучение систем классификаторов с точки зрения обучения с подкреплением». Мягкие вычисления. 6 (3–4): 162–170. Дои:10.1007 / с005000100113. ISSN  1432-7643. S2CID  39103390.
  37. ^ Ковач, Тимоти Майкл Дуглас. Сравнение физической подготовки на основе силы и точности в системах обучения и классификатора. 2002.
  38. ^ Ковач, Тим. «Два взгляда на системы классификаторов». В Международный семинар по системам обучающих классификаторовС. 74-87. Springer Berlin Heidelberg, 2001 г.
  39. ^ а б Конгдон, Клэр Бейтс. «Сравнение генетических алгоритмов и других систем машинного обучения по сложной классификационной задаче из общих исследований болезней». Доктор философии, Мичиганский университет, 1995.
  40. ^ Холмс, Джон Х. (1996-01-01). "Основанный на генетике подход к обнаружению знаний в клинических данных с помощью машинного обучения". Материалы ежегодного осеннего симпозиума AMIA: 883. ISSN  1091-8280. ЧВК  2233061.
  41. ^ Холмс, Джон Х. "Выявление риска заболевания с помощью обучающей системы классификаторов." В ICGAС. 426-433. 1997 г.
  42. ^ Холмс, Джон Х. и Дженнифер А. Сагер. "Открытие правил в данных эпидемиологического надзора с использованием EpiXCS: эволюционный вычислительный подход." ВКонференция по искусственному интеллекту в медицине в ЕвропеС. 444-452. Springer Berlin Heidelberg, 2005 г.
  43. ^ Бутц, Мартин В. "Смещение исследования в системе классификатора упреждающего обучения." В Международный семинар по системам обучающих классификаторов, стр. 3-22. Springer Berlin Heidelberg, 2001.
  44. ^ Уилсон, Стюарт В. (2002). «Классификаторы, приближающие функции». Естественные вычисления. 1 (2–3): 211–234. Дои:10.1023 / А: 1016535925043. ISSN  1567-7818. S2CID  23032802.
  45. ^ Бык, Ларри. "Простая система классификаторов, основанная на точности обучения." Технический отчет группы обучающих классификаторов UWELCSG03-005, Университет Западной Англии, Бристоль, Великобритания (2003).
  46. ^ Бык, Ларри. "Простая система классификаторов на основе результатов обучения." ВМеждународная конференция по параллельному решению проблем с натуры, стр. 1032-1041. Springer Berlin Heidelberg, 2004 г.
  47. ^ Пеньярройя, Жауме Бакардит. «Питтсбургское генетическое машинное обучение в эпоху интеллектуального анализа данных: представления, обобщение и время выполнения». PhD, Universitat Ramon Llull, 2004.
  48. ^ Бакардит, Жауме; Берк, Эдмунд К .; Красногор, Наталио (12 декабря 2008 г.). «Повышение масштабируемости эволюционного обучения на основе правил». Меметические вычисления. 1 (1): 55–67. Дои:10.1007 / s12293-008-0005-4. ISSN  1865-9284. S2CID  775199.
  49. ^ Другович, янв (2008). Дизайн и анализ обучающих систем классификаторов - Springer. Исследования в области вычислительного интеллекта. 139. Дои:10.1007/978-3-540-79866-8. ISBN  978-3-540-79865-1.
  50. ^ Урбанович, Райан Дж., Гедиминас Бертасиус и Джейсон Х. Мур. "Расширенная система обучающих классификаторов в стиле Мичиган для гибкого контролируемого обучения, классификации и интеллектуального анализа данных." В Международная конференция по параллельному решению проблем с натурыС. 211-221. Издательство Springer International, 2014.
  51. ^ Урбанович, Райан Дж., Делани Гранизо-Маккензи и Джейсон Х. Мур. "Использование экспертных знаний для определения покрытий и мутаций в системе классификаторов в стиле Мичиган для обнаружения эпистаза и неоднородности." ВМеждународная конференция по параллельному решению проблем с натуры, стр. 266-275. Springer Berlin Heidelberg, 2012 г.
  52. ^ Урбанович, Райан; Гранизо-Маккензи, Амвросий; Мур, Джейсон (01.01.2012). Связанное с экземпляром отслеживание атрибутов и обратная связь для систем классификаторов контролируемого обучения в стиле Мичиган. Труды 14-й ежегодной конференции по генетическим и эволюционным вычислениям. GECCO '12. Нью-Йорк, Нью-Йорк, США: ACM. С. 927–934. Дои:10.1145/2330163.2330291. ISBN  9781450311779. S2CID  142534.
  53. ^ Бакардит, Жауме; Красногор, Наталио (01.01.2009). Смешанное дискретно-непрерывное представление списка атрибутов для крупномасштабных классификационных доменов. Труды 11-й ежегодной конференции по генетическим и эволюционным вычислениям. GECCO '09. Нью-Йорк, Нью-Йорк, США: ACM. С. 1155–1162. CiteSeerX  10.1.1.158.7314. Дои:10.1145/1569901.1570057. ISBN  9781605583259. S2CID  10906515.
  54. ^ Икбал, Мухаммад; Браун, Уилл Н .; Чжан, Мэнцзе (01.08.2014). «Повторное использование строительных блоков извлеченных знаний для решения сложных крупномасштабных булевых задач». IEEE Transactions по эволюционным вычислениям. 18 (4): 465–480. Дои:10.1109 / tevc.2013.2281537. S2CID  525358.
  55. ^ Букер, Л. Б .; Голдберг, Д. Э .; Холланд, Дж. Х. (1989-09-01). «Системы классификаторов и генетические алгоритмы» (PDF). Искусственный интеллект. 40 (1): 235–282. Дои:10.1016/0004-3702(89)90050-7. HDL:2027.42/27777.
  56. ^ Уилсон, Стюарт В. и Дэвид Э. Голдберг. «Критический обзор систем классификаторов». В Материалы третьей международной конференции по генетическим алгоритмам., стр. 244-255. Издательство Morgan Kaufmann Publishers Inc., 1989 г.

внешняя ссылка

Видеоурок

Веб-страница