Машинное обучение

Машинное обучение

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

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

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

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

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

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

Герберт Симон (Herbert Simon) определил обучение следующим образом.

"Обучение - это любое изменение в системе, приводящее к улучшению решения задачи при ее повторном предъявлении или к решению другой задачи на основе тех же данных". [Simon, 1983]

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

Обучение приводит к изменениям в обучаемой системе. Это несомненно. Однако точная природа этих изменений и наилучший способ их представления далеко не так очевидны. Поэтому выделяют три основных подхода к обучению:

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

2. Нейронные сети (neural network), или сети связей (connectionist network), обучаются не на основе символьного языка. Подобно мозгу живых организмов, состоящему из огромного количества нервных клеток, нейронные сети - это системы взаимосвязанных искусственных нейронов. Знания программы неявно представлены в общей организации и взаимодействии этих нейронов. Такие системы не строят явную модель мира, они сами принимают его форму. Нейронные сети обучаются не за счет добавления новой информации в свою базу знаний, а за счет модификации своей общей структуры в ответ на получаемую извне информацию.

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

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

Основные методы решения задачи обучения:

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

2. Обучение без учителя (unsupervised learning), предполагающее извлечение полезной информации интеллектуальным агентом при отсутствии корректно классифицированных обучающих данных. Основной проблемой обучения без учителя является формирование категорий (category formation), или концептуальная кластеризация (conceptual clustering). Как интеллектуальный агент должен разделить объекты на полезные категории? Как вообще определить, полезна ли эта категория? Два алгоритма формирования категорий - CLUSTER/2 и СОВ-WEB.

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

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

Символьное обучение

В данном направлении разрабатываются в основном группы методов: обучением с учителем и обучение без учителя.

Параметры обучения:

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

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

Характеристикой алгоритма обучения также является его цель (target). Цель многих алгоритмов - понятие (concept), или общее описание класса объектов, при котором на основе примеров некоторого понятия выводится его определение, позволяющее в будущем корректно распознавать экземпляры такого понятия, как "кот", "детские заболевания" или "удачное вложение акций". Алгоритмы обучения также могут использовать планы, эвристики решения проблемы или другие формы процедурного знания.

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

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

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

size(obj1, small) , color(obj, red) , shape(obj1, round)

size(obj2, large) , color(obj2, white) , shape{obj2, round)

Общее понятие "мяч" можно описать так.

size(X, Y) , color(X, Z) , shape(X, round)

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

Этот подход изучения понятий на положительных и отрицательных примерах описан в работе Патрика Винстона [Winston, 1975a]. Его программа строит общие определения таких структурных понятий, как арка, описывая их составные части. Обучающие данные - это последовательность положительных и отрицательных примеров понятия. Поскольку программа не отслеживает маршрут поиска, ее производительность существенно зависит от порядка предъявления обучающих примеров. Неудачный порядок может завести программу в тупик пространства поиска. Обучающие примеры необходимо предъявлять программе в порядке, способствующем изучению данного понятия, подобно тому как преподаватель организует свои занятия со студентами. Являясь одной из первых реализаций принципа индуктивного обучения, программа Винстона иллюстрирует свойства и проблемы большинства подходов к машинному обучению. Они используют операции обобщения и специализации, чтобы определить пространство возможных понятий. Поиск в этом пространстве осуществляется на основе данных, и все эти алгоритмы обучения зависят от качества обучающих данных.

Получение эвристик в виде правил вывода демонстрируют методы Data mining.

Деревья решения являются одним из наиболее популярных подходов к решению задач Data Mining. Они создают иерархическую структуру классифицирующих правил типа "ЕСЛИ... ТО...", имеющую вид дерева (это похоже на определитель видов из ботаники или зоологии). Для того чтобы решить, к какому классу отнести некоторый объект или ситуацию, требуется ответить на вопросы, стоящие в узлах этого дерева, начиная с его корня. Вопросы имеют вид "значение параметра A больше x?". Если ответ положительный, осуществляется переход к правому узлу следующего уровня, если отрицательный — то к левому узлу; затем снова следует вопрос, связанный с соответствующим узлом.

Популярность подхода связана с наглядностью и понятностью. Довольно много систем используют этот метод. Самыми распространенными являются See5/С5.0 (RuleQuest, Австралия), Clementine (Integral Solutions, Великобритания), SIPINA (University of Lyon, Франция), IDIS (Information Discovery, США

Концептуальная кластеризация

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

Числовая таксономия (numeric taxonomy) - один из первых подходов к решению задач кластеризации. Числовые методы основываются на представлении объектов с помощью набора свойств, каждое из которых может принимать некоторое числовое значение. При наличии корректной метрики подобия каждый объект (вектор из п значений признаков) можно рассматривать как точку в л-мерном пространстве. Мерой сходства двух объектов можно считать расстояние между ними в этом пространстве.

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

Проверяются все пары объектов, выбирается пара с максимальной степенью подобия, которая и становится кластером.

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

Можно сказать, что многие алгоритмы обучения без учителя оценивают плотность по методу максимального правдоподобия (maximum likelihood density estimation). Это означает построение распределения, которому с наибольшей вероятностью подчиняются исходные данные. Примером реализации такого подхода является интерпретация набора фонем в приложении обработки естественного языка.

Результатом работы такого алгоритма является бинарное дерево, листья которого соответствуют экземплярам, а внутренние узлы - кластерам более общего вида.

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

objecf1={small, red, rubber, ball},

object2={small, blue, rubber, ball},

object3={large, black, wooden, ball},

то можно ввести метрику подобия

similarity(object1, object2) = 3/4.

similarity(object1, objects) = similarity(object2, object3) = 1/4

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

Человеческие категории также отличаются от большинства формальных иерархий наследования тем, что не все уровни человеческой таксономии одинаково важны. Психологам удалось продемонстрировать существование категорий базового уровня (base-level category) [Rosch, 1978]. Базовая категория - это классификация, которая чаще всего используется для описания объектов в терминах, изученных с раннего детства, на уровне, в некотором смысле охватывающем наиболее фундаментальные свойства объекта. Например, категория "стул" является более базовой, чем любое ее обобщение, в частности, "мебель", или любая ее специализация, например, "офисный стул". "Машина" - это более базовая категория, чем "седан" или "транспортное средство".

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

Эти проблемы учтены в системе COB-WEB [Fisher, 1987]. Не претендуя на звание модели человеческого познания, эта система учитывает категории базового уровня и степень принадлежности элемента соответствующей категории. Кроме того, в программе COBWEB реализован инкрементальный алгоритм обучения, не требующий представления всех обучающих примеров до начала обучения. Во многих приложениях обучаемая система получает данные со временем. В этом случае она должна строить полезные определения понятий на основе исходных данных и обновлять эти описания с появлением новой информации. В системе COBWEB также решена проблема определения корректного числа кластеров. В программе CLUSTER/2 формируется изначально заданное число категорий. Пользователь может изменять это число, однако такой подход нельзя назвать гибким. В системе COBWEB для определения количества кластеров, глубины иерархии и принадлежности категории новых экземпляров используется глобальная метрика качества: вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, p(fi=Vij|ck) - это условная вероятность, с которой свойство f, принимает значение Vij, если объект относится к категории ск.

Критерий полезности категории был определен при исследовании человеческой категоризации. Он учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

∑ ∑ ∑ p(fi=Vij) p(fi=Vij|ck) p(ck|fi=Vij)

k i j

Значения суммируются по всем категориям ск, всем свойствам fi и всем значениям свойств Vij. Значение p(fi=vij|ck) называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство fi - принимает значение Vij, относится к категории ск. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина p(ck|fi=vij) называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории ск свойство fi принимает значение Vij. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение p(fi=vij) - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.