Парадигма обучения на основе правил: Системы классификаторов

Введение

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

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

Методология

Архитектура и компоненты данной системы классификаторов обучения могут быть весьма разнообразными. Удобно рассматривать LCS как машину, состоящую из нескольких взаимодействующих компонентов. Компоненты могут добавляться или удаляться, а существующие компоненты могут быть модифицированы или заменены для соответствия требованиям конкретной проблемной области (как алгоритмические строительные блоки) или для обеспечения достаточной гибкости алгоритма для функционирования в различных проблемных областях. В результате парадигма LCS может гибко применяться ко многим задачам, требующим машинного обучения. Основные различия между реализациями LCS заключаются в следующем: (1) архитектура мичиганского типа против архитектуры питтсбургского типа, (2) обучение с подкреплением против обучения с учителем, (3) инкрементное обучение против пакетного обучения, (4) онлайн-обучение против офлайн-обучения, (5) фитнес, основанный на силе, против фитнеса, основанного на точности, и (6) полное отображение действий против отображения наилучшего действия. Эти разделения не обязательно являются взаимоисключающими. Например, XCS, в 1975 году, и его формализация теоремы схемы Голланда. В 1976 году Голланд концептуализировал расширение концепции ГА до того, что он назвал «когнитивной системой», и предоставил первое подробное описание того, что стало известно как первая система классификаторов обучения в статье «Когнитивные системы, основанные на адаптивных алгоритмах». Эта первая система, названная Когнитивная система один (CS 1), была задумана как инструмент моделирования, предназначенный для моделирования реальной системы (т.е. среды) с неизвестной внутренней динамикой, используя популяцию человекочитаемых правил. Целью было создание набора правил для выполнения онлайн-машинного обучения, чтобы адаптироваться к среде на основе редкой обратной связи/вознаграждения (т.е. обучения с подкреплением) и применять эти правила для генерации поведения, соответствующего реальной системе. Эта ранняя, амбициозная реализация позже была признана чрезмерно сложной и дающей противоречивые результаты. Начиная с 1980 года, Кеннет де Йонг и его ученик Стивен Смит использовали другой подход к машинному обучению на основе правил (LS 1), где обучение рассматривалось как процесс офлайн-оптимизации, а не как процесс онлайн-адаптации. Этот новый подход был более похож на стандартный генетический алгоритм, но развивал независимые наборы правил. С тех пор методы LCS, вдохновленные онлайн-обучением, представленным Голландом в Мичиганском университете, стали называться LCS мичиганского типа, а те, которые вдохновили Смит и Де Йонг в Питтсбургском университете, стали называться LCS питтсбургского типа. Другие важные концепции, появившиеся на ранних этапах исследований LCS, включали (1) формализацию алгоритма «кошевой бригады» (BBA) для распределения кредита/обучения, (2) выбор родительских правил из общей «экологической ниши» (т.е. множества соответствий [M]) вместо выбора из всей популяции [P], (3) покрытие, впервые представленное как оператор создания, (4) формализацию множества действий [A] и введение корректного множества [C], (8) фитнес, основанный на точности, (9) сочетание нечеткой логики с LCS (что впоследствии породило ряд алгоритмов нечеткого LCS), (10) поощрение длинных цепочек действий и иерархий по умолчанию для повышения производительности в многошаговых задачах, (11) изучение латентного обучения (что впоследствии вдохновило новое направление предвосхищающих систем классификаторов (ACS)) и (12) введение первой техники распределения кредита, подобной Q-обучению. Хотя не все эти концепции применяются в современных алгоритмах LCS, каждая из них стала вехой в развитии парадигмы LCS.

The architecture and components of a given learning classifier system can be quite variable. It is useful to think of an LCS as a machine consisting of several interacting components. Components may be added or removed, or existing components modified/exchanged to suit the demands of a given problem domain (like algorithmic building blocks) or to make the algorithm flexible enough to function in many different problem domains. As a result, the LCS paradigm can be flexibly applied to many problem domains that call for machine learning. The major divisions among LCS implementations are as follows: (1) Michigan style architecture vs. Pittsburgh style architecture, (2) reinforcement learning vs. supervised learning, (3) incremental learning vs. batch learning, (4) online learning vs. offline learning, (5) strength based fitness vs. accuracy based fitness, and (6) complete action mapping vs best action mapping. These divisions are not necessarily mutually exclusive. For example, XCS, in 1975 and his formalization of Holland's schema theorem. In 1976, Holland conceptualized an extension of the GA concept to what he called a "cognitive system", and provided the first detailed description of what would become known as the first learning classifier system in the paper "Cognitive Systems based on Adaptive Algorithms". This first system, named Cognitive System One (CS 1) was conceived as a modeling tool, designed to model a real system (i. e. environment) with unknown underlying dynamics using a population of human readable rules. The goal was for a set of rules to perform online machine learning to adapt to the environment based on infrequent payoff/reward (i. e. reinforcement learning) and apply these rules to generate a behavior that matched the real system. This early, ambitious implementation was later regarded as overly complex, yielding inconsistent results. Beginning in 1980, Kenneth de Jong and his student Stephen Smith took a different approach to rule based machine learning with (LS 1), where learning was viewed as an offline optimization process rather than an online adaptation process. This new approach was more similar to a standard genetic algorithm but evolved independent sets of rules. Since that time LCS methods inspired by the online learning framework introduced by Holland at the University of Michigan have been referred to as Michigan style LCS, and those inspired by Smith and De Jong at the University of Pittsburgh have been referred to as Pittsburgh style LCS. Other important concepts that emerged in the early days of LCS research included (1) the formalization of a bucket brigade algorithm (BBA) for credit assignment/learning, (2) selection of parent rules from a common 'environmental niche' (i. e. the match set [M]) rather than from the whole population [P], (3) covering, first introduced as a create operator, (4) the formalization of an action set [A], and the introduction of the correct set [C], (8) accuracy based fitness (9) the combination of fuzzy logic with LCS (which later spawned a lineage of fuzzy LCS algorithms), (10) encouraging long action chains and default hierarchies for improving performance on multi step problems, (11) examining latent learning (which later inspired a new branch of anticipatory classifier systems (ACS)), and (12) the introduction of the first Q learning like credit assignment technique. While not all of these concepts are applied in modern LCS algorithms, each were landmarks in the development of the LCS paradigm.

Революция

Интерес к системам классификаторов обучения возродился в середине 1990-х годов главным образом благодаря двум событиям: разработке алгоритма Q-обучения для обучения с подкреплением и представлению значительно упрощенных архитектур LCS мичиганского типа Стюартом Уилсоном. Система классификаторов нулевого уровня Уилсона (ZCS). Обучение с подкреплением обычно направлено на изучение функции ценности, которая отображает полное представление пространства состояний/действий. Аналогично, конструкция XCS заставляет её формировать всеобъемлющее и точное представление проблемного пространства (то есть полную карту), а не сосредотачиваться на высокодоходных нишах в среде (как это было в случае с LCS, основанными на силе). Концептуально, полные карты отражают не только то, что следует делать, или что правильно, но и то, чего делать не следует, или что неправильно. В отличие от этого, большинство LCS, основанных на силе, или исключительно на обучении с учителем, стремятся к набору правил эффективных обобщений в форме карты наилучших действий (или частичной карты). С тех пор сравнения между пригодностью, основанной на силе, и пригодностью, основанной на точности, а также полными и картами наилучших действий, были изучены более подробно.

Вслед за XCS

XCS вдохновил на разработку целого нового поколения алгоритмов и приложений LCS. В 1995 году Конгдон первым применил LCS к реальным эпидемиологическим исследованиям заболеваний – EpiCS, а позже – EpiXCS для эпидемиологической классификации. Эти ранние работы стимулировали дальнейший интерес к применению алгоритмов LCS к сложным и масштабным задачам интеллектуального анализа данных, особенно ярко проявившийся в биоинформатических приложениях. В 1998 году Столцманн представил системы предвосхищающих классификаторов (ACS), включающие правила в форме «условие – действие – эффект», а не классическое представление «условие – действие». В 2002 году Уилсон представил XCSF, добавив вычисляемое действие для выполнения аппроксимации функций. В 2003 году Бернардо Мансилья представил систему контролируемого классификатора (UCS), специализирующую алгоритм XCS для задач контролируемого обучения, задач с одним шагом и формирования наилучшего набора действий. UCS отказался от стратегии обучения с подкреплением в пользу простого соответствия правил точности, а также фаз исследования/эксплуатации, характерных для многих алгоритмов обучения с подкреплением. Булл представил простую LCS (YCS), основанную на точности, и простую систему минимального классификатора LCS (MCS), основанную на силе, чтобы добиться лучшего теоретического понимания структуры LCS. Bacardit представил GAssist и BioHEL – LCS в стиле Питтсбурга, предназначенные для интеллектуального анализа данных и масштабируемости при работе с большими наборами данных в биоинформатике. В 2008 году Другович опубликовал книгу под названием «Проектирование и анализ обучающих систем классификаторов», включающую некоторые теоретические исследования алгоритмов LCS. Бутц представил первую визуализацию онлайн-обучения правилам в графическом интерфейсе для XCSF. ExSTraCS интегрировал (1) экспертные знания для управления покрытием и генетическим алгоритмом в направлении важных признаков данных, (2) форму долговременной памяти, называемую отслеживанием атрибутов, обеспечивающую более эффективное обучение и характеризацию гетерогенных шаблонов данных, и (3) гибкое представление правил, аналогичное представлению смешанного дискретно-непрерывного списка атрибутов Bacardit. Bacardit и Urbanowicz исследовали статистические и визуализационные стратегии для интерпретации правил LCS и выполнения обнаружения знаний для интеллектуального анализа данных. Браун и Икбал исследовали концепцию повторного использования строительных блоков в виде фрагментов кода и первыми решили задачу мультиплексора на 135 бит, сначала изучив полезные строительные блоки из более простых задач мультиплексирования. ExSTraCS 2.0 был позже представлен для улучшения масштабируемости LCS в стиле Мичигана, успешно решив задачу мультиплексора на 135 бит напрямую впервые. Также использовались для обозначения того, что более точно можно определить как обучающую систему классификаторов. В силу их сходства с генетическими алгоритмами, системы классификаторов обучения в стиле Питтсбурга иногда обобщенно называют «генетическими алгоритмами». Кроме того, некоторые алгоритмы LCS или тесно связанные с ними методы называются «когнитивными системами». Такое разнообразие терминологии вносит некоторую путаницу в эту область. До 2000-х годов почти все методы обучающих систем классификаторов разрабатывались с учетом задач обучения с подкреплением. В результате термин «обучающая система классификаторов» обычно определялся как сочетание обучения с подкреплением методом «проб и ошибок» с глобальным поиском генетического алгоритма. Интерес к приложениям контролируемого обучения и даже неконтролируемого обучения с тех пор расширил использование и определение этого термина.

XCS inspired the development of a whole new generation of LCS algorithms and applications. In 1995, Congdon was the first to apply LCS to real world epidemiological investigations of disease EpiCS, and later EpiXCS for epidemiological classification. These early works inspired later interest in applying LCS algorithms to complex and large scale data mining tasks epitomized by bioinformatics applications. In 1998, Stolzmann introduced anticipatory classifier systems (ACS) which included rules in the form of 'condition action effect, rather than the classic 'condition action' representation. In 2002, Wilson introduced XCSF, adding a computed action in order to perform function approximation. In 2003, Bernado Mansilla introduced a sUpervised Classifier System (UCS), which specialized the XCS algorithm to the task of supervised learning, single step problems, and forming a best action set. UCS removed the reinforcement learning strategy in favor of a simple, accuracy based rule fitness as well as the explore/exploit learning phases, characteristic of many reinforcement learners. Bull introduced a simple accuracy based LCS (YCS) and a simple strength based LCS Minimal Classifier System (MCS) in order to develop a better theoretical understanding of the LCS framework. Bacardit introduced GAssist and BioHEL, Pittsburgh style LCSs designed for data mining and scalability to large datasets in bioinformatics applications. In 2008, Drugowitsch published the book titled "Design and Analysis of Learning Classifier Systems" including some theoretical examination of LCS algorithms. Butz introduced the first rule online learning visualization within a GUI for XCSF ExSTraCS integrated (1) expert knowledge to drive covering and genetic algorithm towards important features in the data, (2) a form of long term memory referred to as attribute tracking, allowing for more efficient learning and the characterization of heterogeneous data patterns, and (3) a flexible rule representation similar to Bacardit's mixed discrete continuous attribute list representation. Both Bacardit and Urbanowicz explored statistical and visualization strategies to interpret LCS rules and perform knowledge discovery for data mining. Browne and Iqbal explored the concept of reusing building blocks in the form of code fragments and were the first to solve the 135 bit multiplexer benchmark problem by first learning useful building blocks from simpler multiplexer problems. ExSTraCS 2.0 was later introduced to improve Michigan style LCS scalability, successfully solving the 135 bit multiplexer benchmark problem for the first time directly. have also been applied to refer to what would be more characteristically defined as a learning classifier system. Due to their similarity to genetic algorithms, Pittsburgh style learning classifier systems are sometimes generically referred to as 'genetic algorithms'. Beyond this, some LCS algorithms, or closely related methods, have been referred to as 'cognitive systems', This variation in terminology contributes to some confusion in the field. Up until the 2000s nearly all learning classifier system methods were developed with reinforcement learning problems in mind. As a result, the term ‘learning classifier system’ was commonly defined as the combination of ‘trial and error’ reinforcement learning with the global search of a genetic algorithm. Interest in supervised learning applications, and even unsupervised learning have since broadened the use and definition of this term.

Видео-учебник

Системы классификаторов обучения вкратце (2016) Изучите базовый алгоритм LCS, чтобы понять его компоненты и принципы работы.