БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ

История философских исследований в области индуктивного обучения описана в главе 1. Уильям из Окхема (1280-1349), наиболее влиятельный философ своей эпохи, внесший в средние века наибольший вклад в развитие эпистемологии, логики и метафизики, заслужил признание потомков за то, что выдвинул важный принцип, называемый "бритвой Оккама", который на латыни выражается словами "Entia поп sunt multiplicanda praeter necessitatem", а в переводе звучит так: "Не следует множить сущности без необходимости". К сожалению, это замечательное изречение не удалось найти в его трудах точно в такой формулировке.
Одной из первых систем, в которой использовались деревья решений (или, как они в ней именовались, различительные сети (discrimination nets)), была система ЕРАМ (Elementary Perceiver And Memorizer) Фейгенбаума [457]. Система ЕРАМ предназначалась для применения в качестве модели имитации познания в процессе обучения человека новым понятиям. В системе CLS [707] для формирования деревьев решений использовался эвристический прогностический метод. В системе ID3
[1256] была дополнительно реализована крайне важная идея о том, что для обеспечения функционирования эвристической функции может применяться информационное содержание. Сама теория информации была разработана Клодом Шенноном для использования в качестве средства исследования процессов связи [1394]. Важный вклад, сделанный Шенноном, состоит также в том, что он разработал первые образцы систем, действующих по принципу машинного обучения, в частности механическую мышь, получившую имя Theseus (Тезей), которая обучалась прохождению через лабиринт по методу проб и ошибок. Метод %2 отсечения ветвей деревьев был описан Куинланом [1257]. Описание пакета С4.5 производственного назначения, который основан на использовании деревьев решений, можно найти в [1259]. В литературе по статистике существует отдельное направление, посвященное исследованиям в области деревьев решений. Одним из основных источников информации по этой теме является книга Classification and Regression Trees [180], известная под названием книги "CART".
Предпринимались также попытки применить многие другие алгоритмические подходы к обучению. Подход, основанный на использовании текущей наилучшей гипотезы, предусматривает сопровождение единственной гипотезы, а также ее уточнение, если обнаруживается, что она слишком широка, и обобщение, если она оказывается слишком узкой. Такой принцип проведения исследований уже давно применяется в философии [1049]. Кроме того, даже ранние работы в области когнитивной психологии показали, что в этом состоит естественная форма изучения концепций людьми [199]. В искусственном интеллекте такой подход наиболее тесно связан с работой Патрика Уинстона, в докторской диссертации которого [1602] рассматривается проблема изучения описаний сложных объектов. В методе пространства версий [1061], [1062] принят другой подход, в котором сопровождается множество всех совместимых гипотез и удаляются оказавшиеся несовместимыми с новыми примерами. Такой подход был реализован в экспертной системе Meta-Dendral, применяемой в химии [202], а затем — системе Митчелла Lex [1066], которая обучалась решению задач исчисления. Третье влиятельное направление возникло под влиянием работы Михальского и его коллег над рядом алгоритмов AQ, применявшихся для изучения множеств логических правил [1038], [1041].
Метод обучения ансамбля деревьев решений все чаще применяется для повышения производительности обучающих алгоритмов. Первый эффективный метод такого типа, называемый созданием мультимножеств [179], предусматривает формирование комбинаций гипотез, изученных на основе многочисленных наборов данных начальной загрузки, каждый из которых формируется путем выборки подмножества из первоначального множества данных. Метод усиления, описанный в данной главе, впервые был изложен в теоретической работе Шейпира [1361]. Алгоритм AdaBoost был разработан Фрейндом и Шейпиром [501], а результаты его теоретического анализа приведены в [1360]. В [505] принципы работы метода усиления описаны с точки зрения специалиста по статистике.
Теоретический анализ обучающих алгоритмов начался с работы Голда [569] по проблеме идентификации в пределе. Стимулом к развитию этого подхода отчасти явились модели научного открытия, разработанные в рамках философии науки [1229], но этот подход в основном применялся к задаче изучения грамматик на примерах предложений [1162].
Подход, основанный на изучении "идентификации в пределе", в основном посвящен достигаемой в конечном итоге сходимости, а исследования колмогоровской сложности, или алгоритмической сложности, проведенные независимо Соломоновым [1445] и Колмогоровым [828], представляют собой попытку дать формальное определение понятия простоты, используемого в принципе бритвы Оккама. Чтобы исключить проблему, связанную с тем, что простота зависит от способа представления информации, было предложено измерять простоту как длину кратчайшей программы для универсальной машины Тьюринга, которая правильно воспроизводит наблюдаемые данные. Хотя существует много возможных универсальных машин Тьюринга и поэтому много возможных "кратчайших" программ, было обнаружено, что эти программы отличаются по длине не больше чем на некоторую константу, независимую от объема данных. Это — великолепное открытие, которое по сути показывает, что любое искажение в первоначальном представлении данных в конечном итоге должно быть преодолено с помощью самих же данных. Его широкому применению препятствует лишь то, что задача вычисления длины кратчайшей программы является неразрешимой. Однако вместо точного значения длины могут применяться такие приближенные критерии, как минимальная длина описания, или MDL (Minimum Description Length) [1291], которые позволяют добиться на практике превосходных результатов. Наилучшим источником сведений по проблеме колмогоровской сложности является книга Ли и Витаньи [927].
Теория вычислительного обучения (т.е. теория РАС-обучения) была выдвинута Лесли Валиантом [1528]. В работе Валианта подчеркивается важность вычислительной и выборочной сложности. Совместно с Майклом Кернсом [783] Валиант показал, что задача РАС-обучения некоторых классов концепций является трудноразрешимой, даже если в примерах присутствует достаточный объем информации. Некоторые положительные результаты были получены для таких классов, как списки решений [1293].
В статистике сложилось независимое направление анализа выборочной сложности, начиная с одной важной работы Вапника и Червоненкиса по теории равномерной сходимости [1538]. Понятие так называемой VC-размерности (VC— сокращение от Vapnik— Chervonenkis) позволяет получить критерий, приблизительно аналогичный, но более общий, чем критерий In | н |, полученный на основе анализа РАС-обучения. В частности, критерий VC-размерности может применяться к непрерывным классам функций, на которые не распространяется стандартный анализ РАС-обучения. Теория РАС-обучения и теория VC-размерности были впервые связаны в единое целое группой ученых, называемых "четырьмя немцами" (хотя ни один из них фактически не является немцем), — Блумером, Эренфойхтом, Хауссле-ром и Вармутом [141]. Дальнейшие исследования в области теории VC-размерности привели к открытию понятия машины поддерживающих векторов, или SVM (Support Vector Machine) [156], [1537], которая будет описана в главе 20.
Большое количество важных статей по машинному обучению было собрано в книге Readings in Machine Learning [1399]. Кроме того, много важных статей, а также огромные библиографические справочники содержатся в двух томах, Machine Learning 1 [1039] и Machine Learning 2 [1040]. В [1565] дано широкое введение в область методов изучения функций, применяемых в машинном обучении, статистике и нейронных сетях. Исследования, намного превосходящие по своей широте все прочие работы в области сравнения производительности обучающих алгоритмов, были проведены в рамках проекта Statlog [1047]. Результаты продуктивных современных исследований по машинному обучению публикуются в ежегодном сборнике трудов конференций International Conference on Machine Learning и Conference on Neural Information Processing Systems, в журналах Machine Learning и Journal of Machine Learning Research, а также в основных журналах по искусственному интеллекту. Кроме того, труды в области теории вычислительного обучения публикуются в материалах ежегодного семинара ACM Workshop on Computational Learning Theory (COLT), а само это направление представлено в книгах [34] и [786].







Материалы

Яндекс.Метрика