Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 183
Скачиваний: 4
112 ГЛ. V. МИНИМИЗАЦИЯ ЭМПИРИЧЕСКОГО РИСКА
на регулярные процедуры, которые должна реализовать обучающая программа, как было в теории рекуррентных алгоритмов. Здесь исследователю каждый раз приходится изобретать алгоритмы, подчиняющиеся определенным об щим правилам.
Преимущество такой теории — ее общность. Так, при исследовании задачи обучения распознаванию образов не возникает необходимости различать две постановки зада чи — детерминистскую и стохастическую. И если все су ществующие рекуррентные алгоритмы обучения распозна ванию образов, по существу, строят в спрямляющем про странстве разделяющую гиперплоскость, то конструк тивные идеи алгоритмов обучения распознаванию образов, использующих метод минимизации эмпирического риска, значительно богаче. В частности, метод минимизации эмпирического риска может быть применен в классе ку сочно-ломаных функций, логических функций опреде ленного вида и др.
у Все эти преимущества связаны с тем, что метод мини мизации эмпирического риска отвечает на вопрос «что надо делать», оставляя в стороне вопрос о том, «как это сделать». Поэтому для минимизации эмпирического рис ка широко могут быть использованы различные методы, в том числе и эвристические.
Применение эвристических методов в этом случае име ет теоретическое оправдание: если в классе решающих правил, емкость которого невелика, выбрать правило, которое хотя и не минимизирует эмпирический риск, но доставляет ему достаточно малую величину, то в силу рав номерной сходимости выбранное правило будет иметь до статочно высокое качество.
Таким образом, алгоритм заведомо способен обучаться, если:
1 ) емкость класса решающих правил алгоритма неве лика,
2 ) выбирается правило, которое доставляет величине эмпирического риска малое значение.
Конструктивные идеи таких алгоритмов имеют чрез вычайно наглядную геометрическую интерпретацию: в пространстве надо построить гиперповерность, принадле жащую заданному классу гиперповерхностей (характер класса гиперповерхностей существенно определяет осо
§ 12. АЛГОРИТМЫ МЕТОДА ОБОБЩ ЕННОГО ПОРТРЕТА |
И З |
бенность алгоритма), которая по возможности с мень шим количеством ошибок, разделяет векторы обучающей последовательности одного класса от векторов обучающей последовательности второго класса. Методы построения таких разделяющих поверхностей и составляют кон структивную особенность алгоритмов обучения распозна ванию образов. При этом принято различать два класса алгоритмов: алгоритмы, строящие «гладкие» разделяющие гиперповерхности, и алгоритмы, строящие «не глад кие» разделяющие поверхности. Методы построения гладких разделяющих поверхностей основаны на построении разделяющей гиперплоскости в соответ ствующем спрямляющем пространстве. Один из них — метод обобщенного портрета будет подробно рассмотрен в третьей части книги. Методы построения «не гладких» разделяющих гиперповерхностей берут свое начало с работ М. М. Бонгарда и М. Н. Вайнцвайга, предложивших один из наиболее популярных алгоритмов обучения такого типа — алгоритм «Кора» [4, 9].
§ 12. Алгоритмы метода обобщенного портрета
Алгоритмы метода обобщенного портрета реализуют идею минимизации эмпирического риска в классе линей ных и кусочно-линейных функций.
Сам метод обобщенного портрета состоит в специальном способе построения разделяющей гиперплоскости. В слу чае, если обучающая последовательность может быть разделена гиперплоскостью, существует целое семейство разделяющих гиперплоскостей. Особенность метода зак лючается в том, что с его помощью строится оптимальная разделяющая гиперплоскость (т. е. гиперплоскость, ко торая из всех разделяющих гиперплоскостей наиболее далеко отстоит от ближайшего к ней элемента обучающей последовательности). Важной особенностью метода обоб щенного портрета является возможность установить (в случае, если это так), что «безошибочного» разделения элементов обучающей последовательности не существует.
Различные алгоритмы, реализующие метод построения обобщенного портрета, предназначены для построения разделяющей гиперплоскости в условиях, когда безоши бочное разделение векторов невозможно. В этих случаях
114 ГЛ. V. МИНИМИЗАЦИЯ ЭМПИРИЧЕСКОГО РИСКА
используются алгоритмы, минимизирующие эмпиричес кий риск в классе линейных или кусочно-линейных ре шающих правил.
В качестве примера приведем здесь идею двух таких алгоритмов (подробно система алгоритмов метода обоб щенного портрета будет рассмотрена в третьей части книги).
Если обучающая последовательность не может быть безошибочно разделена на два класса, среди векторов обу чающей последовательности определяется тот, который наиболее «препятствует» разделению. Он исключается из обучающей последовательности, а оставшиеся векторы вновь разделяются гиперплоскостью. Если разделение все еще невозможно, то исключается еще один вектор, и так до тех пор, пока множество оставшихся векторов не будет разделено. При этом считается, что число исключенных векторов минимально (или близко к нему). Правило удалений определяется эвристическим понятием «вектора, наиболее препятствующего разделению». Удаленные из обучающей последовательности векторы как раз и со ставляют множество неправильно опознанных векторов. Отношение числа этих векторов к числу всех векторов обучающей последовательности определяет величину эмпирического риска для выбранного решающего пра вила (обобщенного портрета). Величина же истинного риска для найденного правила с вероятностью 1 — ц отли чается от эмпирического риска не более чем на е, где е определяется согласно (5.11).
Если с помощью приведенного алгоритма будет пост роена разделяющая гиперплоскость, которая неправильно классифицирует слишком много векторов обучающей по следовательности, то считается, что в классе линейных решающих правил нет удовлетворительного правила, и делается попытка отыскать такое правило в классе ку сочно-линейных правил. Для этого сначала строится раз деляющая гиперплоскость, минимизирующая число оши бок, а затем к ней «пристраивается» еще одна гиперплос кость, с тем чтобы с помощью гиперповерхности, состав ленной из двух кусков гиперплоскостей, минимизировать число ошибок при разделении обучающей последователь ности. Если ошибок все еще много, то достраивается ещо одна гиперплоскость и т. д.
§13. АЛГОРИТМ КОРА |
115 |
С увеличением числа к кусков гиперплоскостей умень шается количество неправильно опознанных векторов, т. е. уменьшается величина эмпирического риска. Однако величина ек гарантированного уклонения истинного риска от эмпирического растет с ростом числа кусков гипер плоскостей по линейному закону
гк = кг.
Отсюда следует, что желательно разделить обучающую последовательность с помощью минимального числа кус ков гиперплоскостей.
Различные алгоритмы реализуют разные идеи построе ния такого кусочно-линейного правила, которое миними зирует сумму величины эмпирического риска и величины гарантированного уклонения.
§ 13. Алгоритм Кора
Все рассмотренные до сих пор конструктивные идеи алгоритмов обучения распознаванию образов были свя заны с построением в спрямляющем пространстве разде ляющей гиперплоскости. Алгоритм обучения распознава нию образов «Кора» исходит из иных конструктивных идей.
Пусть обучающая последовательность распадается на два множества векторов — множество векторов первого класса {х} и множество векторов второго класса {х}. Задается множество характеристических функций ф (х, т), которые называются признаками. Из множества при знаков алгоритм выделяет так называемые достаточные признаки. Достаточным признаком для векторов первого класса называется признак ф (х, т*), который на всех векторах второго класса принимает значение 0 , а на не которых векторах первого класса 1 .
Аналогично определяются достаточные признаки вто рого класса. Алгоритм выбирает t достаточных признаков первого класса и t достаточных признаков второго клас са, так, чтобы для каждого вектора обучающей после довательности нашлось несколько достаточных призна ков, принимающих на этом векторе значение 1. Иными словами, признаки должны «покрывать» все множество примеров.
116 |
ГЛ. V. МИНИМИЗАЦИЯ ЭМПИРИЧЕСКОГО РИСКА |
Опознание вектора, не участвовавшего в обучении, проводится так: подсчитывается, сколько достаточных признаков первого класса на этом векторе приняли зна чение единица и сколько достаточных признаков второго класса приняли значение единица. Вектор относится к тому классу, для которого число достаточных признаков, принявших значение единица, больше.
Особенность алгоритма «Кора» состоит в том, что рас сматривается бинарное пространство X. В качестве клас са характеристических функций ф (х , т) берутся все воз можные конъюнкции двух-трех переменных.
Для каждого класса отбор конъюнкций (признаков) производится по следующим правилам:
1.Из всех возможных признаков (конъюнкций трех переменных) отбираются достаточные признаки. Доста точные признаки упорядочиваются: считается, что при знак ф (X, тД лучше, чем ф (х , т2), если число векторов обучающей последовательности, обладающих этим при знаком (т. е. векторов, для которых ф (х, тД = 1), больше числа векторов, обладающих признаком ф (х , т2).
2.Из найденного множества достаточных признаков исключаются «подчиненные». Признакф (х, т2) называется «подчиненным» признаку ф (х, тД, если множество векто ров обучающей последовательности {х : ф (х, тД= 1}, обладающих признаком ф (х, тД, включает в себя мно жество векторов {ж:ф(ж, тД = 1}, обладающих при знаком ф (х, тД. Подчиненность признаков легко про
веряется от старшего в упорядоченном ряду признака
кмладшему.
3.Из оставшихся достаточных признаков произво дится окончательный отбор t признаков. Принцип отбора таков, чтобы в окончательный набор вошли признаки, которые «покрывают» все множество примеров, данное на обучение, и чтобы, по возможности, все примеры обладали приблизительно одинаковым количеством признаков
(признаки должны «покрывать» множество примеров «рав номерно»).
Характерной особенностью алгоритма «Кора» являются небольшая емкость класса решающих правил и чрезвы чайно простой метод (хотя и эвристический) поиска пра вила, минимизирующего эмпирический риск.. Заметим, что указать класс функций малой емкости, в котором
§ 13. АЛГОРИТМ КОРА |
117 |
можно найти достаточно хорошее решающее правило, значительно труднее, чем класс функций большой ем кости.
Оценим число возможных решающих правил для алго ритма «Кора». Пусть бинарное пространство X имеет раз мерность п, тогда число возможных троек координат рав
но Сп■На каждой тройке с помощью конъюнкции может быть задано восемь функций алгебры логики. Таким об
разом, всего возможно Т = 8 С® различных признаков. Из возможных признаков должно быть отобрано t доста точных признаков первого класса и t достаточных призна
ков второго класса. Так как существует не более Ст спо собов выбрать t признаков из множества, содержащего Т элементов, то число различных решающих правил N ограничено величиной
N < (8 С1Т) \
Следовательно, N < пъі и, согласно (5.17), в случае,! если величина эмпирического риска близка к нулю, ве-І роятность неправильной классификации с помощью най-' денного правила уклонится от эмпирической оценки не более чем на величину
6t ln п — ln n
е = ------- |
1------ |
L- |
Заметим, что величина уклонения пропорциональна только логарифму размерности пространства. В этом и есть замечательная особенность рассмотренного класса не гладких решающих правил.
Г л а в а VI
М Е Т О Д У П О Р Я Д О Ч Е Н Н О Й М И Н И М И З А Ц И И Р И С К А
§ 1. О критериях оценки качества алгоритмов
До сих пор мы интересовались только тем, каким усло виям должен удовлетворять алгоритм, чтобы обеспечить машине способность обучаться. Были рассмотрены рекур рентные алгоритмы. Оказалось, что они требуют достаточ но большой обучающей последовательности. Поэтому бы ла рассмотрена их модернизация, которая заключалась в запоминании обучающей последовательности и много кратном ее использовании. Суть этой модернизации со стояла в том, что задача решалась методом минимизации эмпирического риска. Были найдены условия, при кото рых алгоритмы минимизации эмпирического риска при водят к успеху, и тем самым получена возможность строить различные алгоритмы, способные обучаться рас познаванию образов. Какой же алгоритм выбрать теперь для решения конкретных задач? Какой из алгоритмов обу чения распознаванию образов будет лучше работать на выборках фиксированной длины Z?
Для того чтобы строить наилучшие алгоритмы на вы борках фиксированной длины (конечно-оптимальные ал горитмы), надо прежде всего договориться о том, как оценивать качество алгоритма (т. е. о том, каков критерий оптимизации).
Качество алгоритма обучения при решении конкрет ной задачи естественно определять как качество решаю щего правила, выбранного им по обучающей последова тельности. Качество же решающего правила F (х , а*) для конкретной задачи, заданной распределением Р (х, со),