Часть 10.

Таблица 9.1. Данные о кредитной истории

Рис. 9.13. Дерево решений для оценки кредитного риска

В целом, размер дерева, необходимого для классификации конкретного набора примеров, варьируется в зависимости от проверяемых свойств. На рис. 9.14 показано дерево, которое гораздо проще предыдущего, но позволяет корректно классифицировать примеры из табл. 9.1.

Глава 9. Машинное обучение, основанное на символьном представлении...

393

Рис. 9.14. Упрощенное дерево решений для оценки кредитного риска

Имея набор обучающих примеров и несколько деревьев решений, позволяющих корректно классифицировать эти примеры, следует выбрать дерево, которое с наибольшей вероятностью позволит корректно классифицировать неизвестные экземпляры. По алгоритму ШЗ таким деревом считается простейшее дерево решений, покрывающее все обучающие примеры. В основу такого предположения положена проверенная временем эвристика, согласно которой предпочтение отдается простоте без дополнительных ограничений. Этот принцип впервые был сформулирован в 1324 году философом-схоластом Вильямом из Оккама (William of Occam) и получил название "бритвы Оккама" (Occam's Razor).

"Глупо прилагать больше усилий, чем нужно для достижения цели... Не стоит приумножать сущности сверх необходимого."

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

Хотя принцип "бритвы Оккама" хорошо зарекомендовал себя в качестве общей эвристики для всех видов интеллектуальной деятельности, его использование в данном алгоритме имеет более точное обоснование. Если предположить, что существующих примеров достаточно для построения корректного обобщения, то проблема сводится к выделению необходимых свойств из дополнительных примеров. Простейшее дерево решений, покрывающее все примеры, вероятнее всего, не будет содержать излишних ограничений. И хотя эта идея основывается на интуитивных рассуждениях, ее можно проверить на практике. Некоторые из таких эмпирических результатов представлены в подразделе 9.3.3. Однако, прежде чем переходить к их изучению, рассмотрим алгоритм ID3, позволяющий строить деревья решений на основе примеров.

9.3.1. Построение дерева решений сверху вниз

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

394

Часть IV. Машинное обучение

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

Например, рассмотрим процесс построения дерева, представленного на рис. 9.14, на основе данных из табл. 9.1. Имея полную таблицу примеров, алгоритм ID3 выбирает в качестве корневого свойства значение дохода на основе функции выбора, описанной в подразделе 9.3.2. При этом множество примеров делится на три части, как показано на рис. 9.15. Элементы каждой части представлены порядковыми номерами примеров в таблице.

Рис. 9.16. Еще один фрагмент дерева решений

Алгоритм индукции начинает свою работу с отбора корректно классифицированных элементов целевых категорий. Алгоритм ID3 строит дерево решений следующим образом.

function induce_tree (example_set, Properties)

Begin

если все элементы набора примеров example_set принадлежат к

одному и тому же классу,

то вернуть конечный узел, отнеся его к этому классу, иначе, если множество Properties пусто,

то вернуть конечный узел, именем которого является

Глава 9. Машинное обучение, основанное на символьном представлении...

395

объединение всех имен классов в example_set иначе Begin

выбрать свойство Р и назначить его корнем

текущего дерева;

удалить свойство Р из множества Properties для каждого значения V свойства Р Begin

создать ветвь дерева с меткой V; к разделу partitionv отнести

элементы множества example_set, для которых свойство Р принимает значение V; вызвать функцию induce_tree {partitionv, Properties) , добавить результаты к ветви V End End End

Согласно алгоритму ID3 функция induce_tree рекурсивно вызывается для каждого раздела. Например, пусть к разделу {1,4,7, 11} относятся клиенты с высоким риском; алгоритм ID3 создаст соответствующий конечный узел. Затем в качестве корневого узла поддерева раздела {2, 3, 12, 14} выбирается свойство "кредитная история". На рис. 9.14 элементы этого раздела в свою очередь разбиваются на три группы: {2, 3}, {14} и {12}. Таким образом, строится дерево, представленное на рис. 9.14. Оставшуюся часть дерева читателям предлагается построить самостоятельно. Реализация этого алгоритма на языке LISP описана в разделе 15.13.

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

9.3.2. Выбор свойств на основе теории информации

Каждое свойство можно рассматривать с точки зрения его вклада в процесс классификации. Например, если необходимо определить виды животных, то одним из признаков классификации является откладывание яиц. Алгоритм ID3 при выборе корня текущего поддерева оценивает удельный вес информации, добавляемой каждым свойством. Затем он выбирает свойство, имеющее наибольшую информативность.

Теория информации [Shannon, 1948] обеспечивает математическую основу для измерения информативности сообщения. Каждое сообщение можно рассматривать как экземпляр в пространстве возможных сообщений. Передача сообщения соответствует выбору одного из возможных сообщений. С этой точки зрения целесообразно определить информационную емкость сообщения в зависимости от размера пространства и частоты использования каждого возможного сообщения.

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

396 Часть IV. Машинное обучение

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

Роль вероятности передачи каждого сообщения видна из следующего примера. Предположим, что существует монета, при подбрасывании которой в трех из четырех случаев выпадает решка. Если знать, что вероятность выпадения решки составляет 3/4, то в 3/4 случаев можно правильно угадать результат игры.

Шеннон формализовал эти наблюдения, определив количество информации в сообщении как функцию от вероятности р передачи каждого возможного сообщения, а именно -log2p. Имея пространство сообщений М={т1, т2, ... , mп} и зная вероятности р(mi) для каждого сообщения, информативность этих сообщений можно вычислить следующим образом.

Количество информации в сообщении измеряется в битах. Например, информативность сообщения в результате подбрасывания обычной монеты составляет

Если же монета такова, что вероятность выпадения решки составляет 75%, то информативность сообщения равна

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

Дерево решений можно рассматривать с точки зрения информации о примерах. Информативность дерева вычисляется на основе вероятностей различных типов классификации. Например, если предположить, что все примеры в табл. 9.1 появляются с одинаковой вероятностью, то

Следовательно, информативность распределения D9.1, описанного в табл. 9.1, а значит, и любого дерева, покрывающего эти примеры, составляет

Количество информации, обеспечиваемое при выборе данного свойства в качестве корня текущего дерева, равно разности общего количества информации в дереве и

Глава 9. Машинное обучение, основанное на символьном представлении... 397

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

Предположим, что существует набор обучающих примеров С. Если корнем текущего дерева является свойство Р, которое может принимать л значений, то множество С будет ,разделено на подмножества {C1,C2, ... , Cn}. Информация, необходимая для завершения построения дерева при выборе свойства Р, составляет

Выигрыш от использования свойства Р вычисляется как разность общей информативности дерева и объема информации, необходимого для завершения построения дерева.

Возвращаясь к примеру из табл. 9.1, при выборе в качестве корня дерева свойства "доход" примеры будут разделены на три группы: С1={1, 4, 7, 11},С2={2, 3, 12, 14} и Сз={5, 6, 8, 9, 10, 13). Информация, необходимая для завершения построения дерева, составляет

Информационный выигрыш от такого разбиения данных табл. 9.1. составляет

Аналогично можно показать, что

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

9.3.3. Анализ алгоритма ID3

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

Например, в работе [Quinlan, 1983) исследована производительность алгоритма ID3 на примере задачи классификации эндшпилей при игре в шахматы. В примерах эндшпилей участвовали белые король и ладья и черные король и конь. Задачей алгоритма было научиться распознавать позиции, приводящие к поражению черных за три хода.

398 Часть IV. Машинное обучение

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

С учетом симметрии область определения задачи включает 1,4 миллиона различных позиций, среди которых 474 тысячи приводят к поражению черных за три хода. Алгоритм ГОЗ строил дерево на случайно выбранном обучающем множестве и тестировался на 10000 различных комбинаций, которые тоже выбирались случайным образом. Результаты тестирования приведены в табл. 9.2. Более подробный анализ результатов тестирования приводится в работе [Quinlan, 1983].

Эти результаты подтверждаются и другими тестами и конкретными приложениями. Существуют варианты алгоритма ID3, позволяющие решать задачи в условиях зашумленных данных и очень больших обучающих множеств. Более подробная информация приводится в работе [Quinlan, 1986a, б].

9.3.4. Вопросы обработки данных для построения дерева решений

В работе [Quinlan, 1983] впервые предлагается использовать теорию информации для построения поддеревьев дерева решений. Именно эта работа положена в основу приведенного выше обоснования алгоритма. Рассмотренные примеры были достаточно понятны и просты. Однако в них не затрагивалось множество проблем, которые зачастую возникают при работе с большими массивами данных.

Первая проблема - плохие данные. Это означает, что несколько наборов данных с

идентичными свойствами приводят к различному результату. Что делать при отсутствии априорной информации о достоверности данных?

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

ввести новое значение "неизвестен"? Как обойти эту проблему?

Некоторые признаки могут принимать значения из непрерывного интервала. Такие

данные подлежат дискретизации и последующей группировке. Можно ли приду

мать более эффективный подход?

Набор данных может быть слишком большим для алгоритма обучения. Что делать

в этой ситуации?

Решение этих проблем привело к созданию нового поколения алгоритмов обучения, основанных на построении дерева решений. Наиболее известным из них является алгоритм С4.5 [Quinlan, 1996]. Для решения этих проблем также используются такие приемы,

Глава 9. Машинное обучение, основанное на символьном представлении... 399

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

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

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

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

9.4. Индуктивный порог и возможности обучения

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

9.4.1. Индуктивный порог

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

400 Часть IV. Машинное обучение

возможных комбинаций составляет 2n. Поэтому число вариантов классификации всех битовых строк длины п составляет 2 в степени 2n. Для n=50 это число превышает количество молекул во вселенной. Поэтому без некоторых эвристических ограничений невозможно организовать эффективный поиск в таких пространствах.

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

"Вы говорите, что одно предложение вытекает из другого. Однако необходимо признать, что это умозаключение не интуитивно и не демонстративно. Тогда какова же его природа? Можно сказать, что оно проверяется экспериментально, но это слабое утешение. Все умозаключения, основанные на опыте, предполагают, что будущее аналогично прошедшему, и что сходные причины приведут к подобным результатам". [Hume, 1748].

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

В индуктивном обучении обучающие данные - это лишь подмножество всех экземпляров области определения. Следовательно, для любой обучающей выборки возможны различные обобщения. Вернемся к примеру с классификацией битовых строк. Предположим, что в качестве положительных примеров некоторого класса строк системе были предъявлены строки {1100, 1010}. Для этого примера допустимо много различных обобщений: все строки, начинающиеся с "1" и заканчивающиеся "0"; множество строк, начинающихся с "1"; множество четных строк или любое другое подмножество, включающее рассмотренный пример {1100, 1010}. На основе чего система может сделать обобщение? Одних данных для этого недостаточно, поскольку все приведенные примеры обобщений согласуются с этими данными. Обучаемая система должна сделать дополнительные предположения о "вероятных понятиях".

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

Такая эвристика позволяет алгоритму ID3 выполнять эффективный поиск в пространстве деревьев решений и решить проблему выбора приемлемого обобщения на основе ограниченного объема данных. В алгоритме ID3 предполагается, что минимальное дерево, корректно классифицирующее все обучающие примеры, вероятнее всего, будет корректно классифицировать и последующие обучающие примеры. Это предположение основано на том, что маленькие деревья, скорее всего, будут соответствовать имеющимся данным. Если же обучающее множество достаточно велико, то такие деревья должны включать все существенные признаки для определения принадлежности классу. Как описано в подразделе 9.3.3, это предположение обосновывается решением практических задач. Подобное предпочтение простых определений понятий используется в таких алгоритмах обучения, как CLUSTER/2 из подраздела 9.6.2.

Глава 9. Машинное обучение, основанное на символьном представлении... 401

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

Примером синтаксического порога, который может оказаться эффективным при классификации битовых строк, является ограничение описания примеров шаблонами, состоящими из символов {0, 1, #}. Каждый шаблон определяет класс всех соответствующих ему строк, при этом соответствие задается следующими правилами.

Если в некоторой позиции шаблона строки содержится "О", значит, и целевая строка должна содержать "О" в этой позиции.

Если в некоторой позиции шаблона строки содержится "1", значит, и целевая строка должна содержать "1" в этой позиции.

Символ "#" в некоторой позиции соответствует либо "1" либо "О".

Например, шаблон "1 ##0" определяет набор строк {1110, 1100, 1010, 1000}.

Использование классов, соответствующих таким шаблонам, значительно уменьшает размер пространства понятий. Для строк длины п можно определить 3n различных шаблонов. Это значительно меньше, чем 2 в степени 2" возможных понятий в неограниченном пространстве. Порог также позволяет упростить реализацию поиска в пространстве версий, поскольку в этом случае обобщение означает замену символов "1" или "0" в шаблоне символом "#". Однако наличие этого порога приводит к невозможности представления (а следовательно, и изучения) некоторых понятий. Например, с помощью такого шаблона нельзя представить все строки, содержащие четное число нулей и единиц.

Противоречие между выразительностью и эффективностью - типичная проблема обучения. Например, в программе LEX четные и нечетные целые не различаются. Следовательно, она не может обучиться эвристике, основанной на этом различии. И хотя в некоторых программах порог изменяется в соответствии с данными [Utgoff, 1986], большинство обучаемых программ основываются на фиксированном пороге срабатывания.

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

Конъюнктивные пороги (conjunctive bias) ограничивают возможности обучения конъюнкцией литералов. Это достаточно типичный подход, поскольку использование дизъюнкции в определениях понятий вызывает проблемы при обобщении. Например, предположим, что в представлении понятий в рамках алгоритма исключения кандидата можно свободно использовать операцию дизъюнкции. Поскольку максимально конкретным обобщением набора положительных примеров является простая дизъюнкция этих примеров, то обучаемая система вообще не сможет выполнить обобщение. Такая система будет просто добавлять новые операнды [Mitchell, 1980].

Ограничения на количество дизъюнктов (limitation on the number of disjuncts). Чисто конъюнктивные пороги являются слишком жесткими для многих приложений. Повысить выразительность представления можно, разрешив использовать небольшое ограниченное число дизъюнктов.

402 Часть IV. Машинное обучение

' Векторы признаков (feature vector) - это представления, описывающие объекты через наборы свойств, значения которых различны для разных объектов. В табл. 9.1 объекты представлены именно наборами признаков.

Деревья решений (decision tree) - это представления понятий, эффективность которых подтверждается алгоритмом ID3.

Хорновские выражения (Horn clauses) налагают ограничения на форму вывода, используемую при автоматическом доказательстве. Хорновские выражения детально описаны в разделе 12.2.

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

9.4.2. Теория изучаемости

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

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

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

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

Глава 9. Машинное обучение, основанное на символьном представлении... 403

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

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

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

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

В 1984 году эти рассуждения были формализованы в теории приближенно корректного с высокой вероятностью РАС-обучения (probably approximately correct learning) [Valiant, 1984].

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

Формально понятие РАС-изучаемости определяется следующим образом. Пусть С - это множество понятий с, а X - множество экземпляров. В качестве понятий могут выступать алгоритмы, шаблоны или другие средства деления множества X на положительные и отрицательные примеры. Множество С является РАС-изучаемым, если существует алгоритм, обладающий следующими свойствами.

404 Часть IV. Машинное обучение

1. Если для ошибки понятия 6 и вероятности ненахождения понятия 5 существует алгоритм, который за полиномиальное время 1 /е и 1 /5 в случайной выборке приме

ров размера п = \Х\ находит такое понятие с, являющееся элементом множества

С, при котором вероятность ошибки обобщения, превышающая е, меньше, чем S.

Следовательно, для элемента у, подчиняющегося тому же распределению, что и

элементы множества X, выполняется соотношение

Р[Р[у неверно классифицируется с помощью понятия

2. Время работы алгоритма для л примеров является полиномиальным и составляет

Это определение РАС-изучаемости позволило доказать эффективность нескольких индуктивных порогов. Например, в работе [Valiant, 1984] показано, что класс выражений k-CNF является изучаемым. Выражения k-CNF- это предложения в конъюнктивной нормальной форме с ограничением на количество дизъюнктов. Выражения формируются из операторов конъюнкции С1^С2^...Cn, где сi- дизъюнктивное выражение, состоящее не более чем из к литералов. Этот теоретический результат обосновывает общепринятое описание понятий в конъюнктивной форме, используемое во многих алгоритмах обучения. Мы не будем приводить доказательство этого утверждения, а отошлем читателя к исходной статье, где обосновывается этот результат, а также свойство изучаемости при использовании других порогов. Результаты исследования изучаемости понятий и индуктивных порогов приводятся в работах [Haussler, 1988] и [Martin, 1997].

9.5. Знания и обучение

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

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

Глава 9. Машинное обучение, основанное на символьном представлении... 405

9.5.1. Алгоритм Meta-DENDRAL

Алгоритм Meta-DENDRAL [Buchanan, Mitchell, 1978] - это один из первых и лучших примеров применения знаний в индуктивном обучении. Алгоритм Meta-DENDRAL формирует правила, используемые программой DENDRAL для масс-спектрографического анализа данных. Эта программа восстанавливает структуру органических молекул на основе химических формул и данных масс-спектрографических экспериментов.

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

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

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

Двойные и тройные связи не разрываются.

В экспериментальных данных можно наблюдать лишь фрагменты, размер

которых превышает 2 атома углерода.

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

Эти пояснения составляют набор положительных примеров для программы формирования правил. Ограничения в левой части правил строятся на основе поиска от общего к частному. Работа алгоритма начинается с рассмотрения наиболее общего описания расщепления X1*X2. Этот шаблон означает, что расщепление, обозначенное символом "*", может произойти между любыми двумя атомами. Этот шаблон уточняется таким образом:

добавление атомов: X1 *Х2 ?Х3-Х, *Х2, где оператор "-" означает химическую связь, или

инстанцирование атомов и атрибутов атомов: X, *Х2 ? С*Х2.

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

Преимущество алгоритма Meta-DENDRAL состоит в использовании знаний об области определения для преобразования одномерных данных в более удобную форму. Это

406 Часть IV. Машинное обучение

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

9.5.2. Обучение на основе объяснения

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

Существует несколько различных реализаций этой идеи. Например, она оказала значительное влияние на представление общих операторов планирования (см. раздел 5.4 и 9.5) в программе STRIPS [Fikes и др., 1972]. В алгоритме Meta-DENDRAL тоже использованы преимущества теоретической интерпретации обучающих примеров. В последние годы многие авторы предложили альтернативные формулировки этой идеи [DeJong и Моопеу, 1986; Minton, 1988]. Типичным примером является алгоритм обобщения на основе объяснения, разработанный Митчеллом и его коллегами в 1986 году. В этом разделе будет рассмотрен вариант алгоритма обучения на основе объяснения EBL (explanation-based learning), разработанный Дейонгом и Муни (DeJong и Моопеу] в 1986 году.

Исходными данными для алгоритма EBL являются следующие.

Целевое понятие. Задача обучаемой системы- выработать эффективное определение этого понятия. В зависимости от типа приложения целевым понятием может быть система классификации, доказанная теорема, план достижения цели или эвристика для решения задачи.

Обучающий пример. Это пример цели.

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

Критерий функциональности. Средства описания формы, которую может принимать определение понятия.

Для иллюстрации алгоритма EBL рассмотрим пример изучения понятия "чашка". Эта задача была описана Винстоном (Winston) в 1983 году и адаптирована к обучению на основе объяснения Митчеллом и его коллегами в 1986 году. Целевым понятием в этой задаче является правило, которое можно использовать для выяснения, является ли объект чашкой.

где premise - это конъюнктивное выражение, содержащее переменную X.

Допустим, теоретические сведения о чашках представлены в виде следующих правил.

Глава 9. Машинное обучение, основанное на символьном представлении... 407

Обучающий пример - это экземпляр целевого понятия, который в данном случае имеет такой вид:

cup(obj1)

small(obj1)

part(obj1, handle)

owns(bob, obj1)

part(obj1, bottom)

part(obj1, bowl)

points_up(bowl)

concave(bowl)

color(obj1, red).

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

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

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

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

Обобщенное дерево доказательства можно построить на основе обучающего примера различными способами. В работе Митчелла сначала строится дерево доказательства для конкретного примера, которое затем обобщается с помощью процесса, получившего название регрессии цели (goal regression). В процессе регрессии цели обобщенная цель (в нашем примере сир(Х)) приравнивается к корню дерева доказательства, при этом конкретные значения заменяются переменными. Такие подстановки выполняются рекурсивно по всему дереву до тех пор, пока не будут заменены все соответствующие константы. Этот процесс более подробно описан в работе [Mitchell и др., 1986].

408 Часть IV. Машинное обучение

В [DeJong и Моопеу, 1986] предложен альтернативный подход, позволяющий строить обобщенные и частные деревья одновременно. Это достигается благодаря особому варианту дерева доказательства, содержащему правила выявления отличий цели от понятия, сформированного за счет подстановки переменных в реальное доказательство. Это дерево называется структурой объяснения (explanation structure) (рис. 9.18) и представляет абстрактную структуру доказательства. Обучаемая система поддерживает два различных списка подстановок для структуры объяснения: список конкретных подстановок, необходимый для объяснения обучающего примера, и список общих подстановок для обоснования обобщенной цели. Эти списки подстановок строятся в процессе создания структуры объяснения.

Списки общих и частных подстановок формируются следующим образом. Пусть ss и sg - списки частных и общих подстановок соответственно. Для всех соответствующих выражений e1 и е2 в структуре объяснения ss и sg обновляются по следующему правилу.

if e1. находится в левой части правила, а е2 - в его заключении, then begin

Ts = наиболее общий унификатор из e1ss и e2ss %объединить е1 и е2

Глава 9. Машинное обучение, основанное на символьном представлении...

409

при условии ss

Ss =SsTs %обновить значение Ss, скомпоновав его с Тs

Тg = наиболее общий унификатор из e1sg и e2sg %объединить е1 и е2 при условии sg

sg =sgTg %оСновить значение sg, скомпоновав его с Тg

end if e1 находится в левой части правила, а е2 - это факт из обучающего

примера then begin

Ts = наиболее общий унификатор из e1Ss и e2ss %объединить e1 и е2

%при условии Ss

ss =SSTs %обновить значение ss, скомпоновав его с Тs

end

Рис. 9.18. Структура объяснения для примера с чашкой

В примере на рис. 9.18

ss = {obj1/X, obj1/Y, obj1/A, obj1/Z, bowl/W)

sg = {X/Y,Y/A,X/Z}.

Применяя эти подстановки к структуре объяснения, показанной на рис. 9.18, получим частное и общее деревья доказательства, показанные на рис. 9.17.

Преимущества обучения на основе объяснения сводятся к следующему.

Обучающие примеры зачастую содержат несущественную информацию, наподобие

цвета чашки в предыдущем примере. Теоретические сведения об области определения

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

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

Используя знания об области определения, алгоритм EBL обеспечивает обучение

на основе одного обучающего примера.

1. 410

Часть IV. Машинное обучение

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

Алгоритм EBL применялся для решения многочисленных задач обучения. Например, в работе [Mitchell и др., 1983] обсуждается вопрос добавления EBL к алгоритму LEX. Допустим, первый положительный пример использования операции ОР1 встретился при вычислении интеграла ?хг dx. Согласно алгоритму LEX этот пример станет элементом множества S, содержащего наиболее конкретные обобщения. Однако человек сразу же определит, что используемый при решении этой задачи прием не зависит от значений коэффициента и показателя степени и может применяться для любых вещественных значений этих переменных (за исключением показателя степени -1). Поэтому можно обобщить этот пример и сделать вывод о том, что операцию ОР1 необходимо применять для вычисления любых интегралов вида ?r1x(r2?1)dx , где r1 и r2 - любые вещественные числа. Для такого обобщения алгоритм LEX был модифицирован на базе знаний алгебры и обучения на основе объяснения. Реализация алгоритма обучения на основе объяснения на языке PROLOG приводится в подразделе 14.8.3.

9.5.3. Алгоритм EBL и обучение на уровне знаний

Алгоритм EBL элегантно демонстрирует роль знаний в обучении, однако при его изучении возникает много важных вопросов. Один из самых очевидных сводится к следующему: чему на самом деле учится система на основе объяснения? Чистый алгоритм EBL позволяет лишь выучить правила в рамках дедуктивного замыкания (deductive closure) существующих теоретических сведений. Это означает, что изученные правила можно сформулировать лишь на основе базы знаний без использования обучающих примеров вообще. Основная роль обучающего примера сводится к фокусированию внимания обучаемой системы на существенных аспектах области определения задачи. Следовательно, алгоритм EBL зачастую рассматривают как одну из форм ускорения обучения или реструктуризации базы знаний. Он ускоряет процесс обучения, поскольку не требует построения дерева доказательства, лежащего в основе нового правила. Однако он не позволяет изучить никакой новой информации. Это отличительное свойство алгоритма было сформулировано Дитрихом (Dietterich) при обсуждении обучения на уровне знаний в 1986 году.

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

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

Глава 9. Машинное обучение, основанное на символьном представлении... 411