Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
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'} или, в более конкретном примере, {IF 'красный' AND 'восьмиугольник' THEN 'стоп-сигнал'} ). Критическая концепция как в 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 является наиболее распространенным подходом. Эволюционные алгоритмы, такие как GA, используют стохастический поиск, что делает LCS стохастическим алгоритмом. LCS стремится грамотно исследовать пространство поиска, но не выполняет исчерпывающий поиск комбинаций правил и не гарантирует схождения к оптимальному решению.

Удаление [ править ]

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

Обучение [ править ]

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

Сжатие правил [ править ]

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

Прогноз [ править ]

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

Интерпретация [ править ]

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

История [ править ]

Ранние годы [ править ]

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

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

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

Внешние ссылки [ править ]

Видеоурок [ править ]

  • Изучение систем классификаторов в двух словах - (2016). Изучите базовый алгоритм LCS, чтобы изучить их компоненты и то, как они работают.

Веб-страницы [ править ]

  • LCS и GBML Central
  • Исследовательская группа обучающих классификаторов UWE
  • Прогнозирование динамики