Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 33
Текст из файла (страница 33)
В гл. 3 мы исходилн из того, что любое множество, содержащее число выборок, меньшее, чем 22, вероятно, будет линейно разделяемым. Таким образом, несколькими способами используя большое число конструктивных выборок, чтобы переопределить классификатор, мы бы гарантировали хорошее соответствие его работы на конструктивных и проверочных данных.
К сожалению, достаточно большое конструктивное множество почти наверняка не будет линейно разделяемым. Поэтому важно знать, как себя ведут процедуры коррекции ошибок в случае неразделяемых выборок. Поскольку в условиях неразделяемых множеств невозможно посредством весового вектора правильно классифицировать каждую выборку, очевидно, что процесс коррекции ошибок может никогда не прекратиться. Каждый алгоритм образует бесконечную последовательность весовых векторов, где любой член может как давать, так и не давать нужного решения. Точное поведение указанных процедур прн наличии неразделяемых множеств было строго исследовано только в нескольких специальных случаях.
Известно;. например, что длина весовых векторов, образованных с помощью правила постоянного приращения, ограничена. Правила, определяющие окончание процедуры коррекции, полученные эмпирическим путем, часто основываются на тенденции длины весовых векто- Ге. й. Линейные йаедееяееяие функции ров колебаться около некоторого предельного значения. С теоретической точки зрения при целочисленных компонентах выборок процедура, основанная на использовании правила постоянного приращения, приводит к конечному процессу. Если процесс коррекций заканчивается в некоторой произвольной точке, вектор веса может находиться, а может и не находиться в надлем:ащем положении. Усредняя весовые векторы, образованные в результате применения правила коррекций, можно уменьшить риск получения плохого решения из-за случайно неудачно выбранного момента окончания процесса коррекций.
Выл предложен н изучен на практике ряд подобных эвристических модификаций для правил коррекции ошибок. Цель этих модификаций состоит в получении приемлемых характеристик для задач с неразделяемымн множествами при сохранении возможности определения разделяющего вектора для задач с разделяемыми множествами. В качестве общего подхода может быть предложено использование переменного приращения рю которое стремится к нулю при А-сии. Скорость, с которой р, приближается к нулю, является весьма важным фактором.
Если скорость слишком мала, результаты будут оставаться зависящими от тех выборок, которые делают множество неразделяемым. Если скорость слишком велика, то вектор веса может сходиться слишком быстро, и процесс закончится до того, как будут достигнуты оптимальные результаты.
Один из способов выбора ри состоит в представлении его в виде функции нового показателя качества, убывающей по мере улучшения данного показателя. Другой путь выбора ри — это задание его в виде р» — — р,/й. Когда мы будем изучать методы стохастической аппроксимации, то увидим, что последний способ выбора ри представляет собой теоретическое решение аналогичной задачи. Однако прежде, чем обратиться к данной теме, рассмотрим подход, при котором жертвуют ~, возможностью получения разделяющего вектора, с целью достижения нужного компромисса между обеими задачами— как с разделяемыми, так и с неразделяемыми множествами.
5.8. ПРОЦЕДУРЫ МИНИМИЗАЦИИ КВАДРАТИЧНОЕ ОШИБКИ 5,8Л. МИНИМАЛЬНАЯ КВАДРАТИЧНАЯ ОШИБКА И ПСЕВДООБРАЩЕНИЕ В случае ранее рассмотренных функций критерия внимание в основном было сфокусировано на выборках, классифицируемых с ошибкой. Теперь будет рассмотрена функция критерия, включающая все выборки. Там-, где прежде осуществлялся предварительный поиск весового вектора а, приводящего к положительным значениям все скалярные произведения а'уы теперь попытаемся получить а'у~=ЬЬ где Ь| являются произвольно заданными положительными д.а.
Процедуры мииимиоации иоадрао!ичиой ыиибии 169 константами. Таким образом, задача нахождения решения системы линейных неравенств заменяется более строгой, но более понятной задачей определения решения системы-линейных уравнений. Вид системы линейных уравнений упрощается, если ввести матричные обозначения. Пусть У вЂ” матрица размера пхе(, е-я строка которой является вектором у,', и пусть Ь вЂ” вектор-столбец Ь=(Ь„...
..., Ь„)!. Тогда наша задача сводится к определению весового вектора а, удовлетворяющего уравнению Уа=Ь. (29) Если бы матрица У была невырожденной, то можно было бы записать равенство а=У 'Ь и сразу же получить формальное решение. Однако У является прямоугольной матрицей, у которой число строк обычно превышает число столбцов. Когда уравнений больше, чем неизвестных, вектор а определен избыточно, и обычно точного решения не существует. Однако можно искать весовой вектор а, минимизирующий некоторую функцию разности между Уа и Ь. Если определить вектор ошибки е как е= Уа — Ь, (30) то данный подход будет состоять в минимизации квадрата длины вектора ошибки. Данная операция эквивалентна задаче минимизации функции критерия, выражаемой суммой квадратичных ошибок: и .е, (а) = 9 Уа — Ь! ( е = ~ (аеу! — Ь;)'.
(31) ! 1 Задача минимизации суммы квадратичных ошибок является классической. Как будет показано в п. 5.8.4, она может быть решена методом градиентного анализа. Простое решение в замкнутой форме можно также получить, образуя градиент л 7,1е = Д 2 (а'у! — Ь!) у! = 2У' (Уа — Ь) е= ! и полагая его равным нулю. Отсюда получается необходимое условие УеУа = У'Ь, (32) н задача решения уравнения Уа=-Ь сводится к задаче решения уравнения У'Уа=УеЬ. Большим достоинством этого замечательного уравнения является то, что матрица У'У размера е( хе( квадратная и часто невырожденная. Если данная матрица невырождена, вектор а может быть определен однозначно: а=(У'У) 'У'Ь=У'Ь, (33) где матрица размера е(хи Уг=(УеУ) еУ! (34) Гл.
д. Линейные разделяющие функции 170 называется псеедообращением матрицы У. Заметим, что если матрица У квадратная и невырожденная, псевдообращение совпадает с обычным обращением. Следует также отметить, что Уе У=), но обычно УУе+!. Если матрица УвУ вырождена, решение уравнения (32) не будет единственным. Однако решение, обеспечивающее мин имальную квадратичную ошибку, существует всегда. В частности, при определении УУ в более общем виде: У~= !пп (У'У+е7) 'У' (35) в- О можно показать, что данный предел всегда существует, и а=У! Ь является решением уравнения Уа=Ь, обеспечивающим наименьшую квадратичную ошибку.
Указанные и другие интересные свойства псевдообращения подробно изложены в литературе. Решение с наименьшей квадратичной ошибкой зависит от век- тора допуска Ь, и будет показано, что различные способы выбора Ь приводят к различным свойствам получаемого решения. Если вектор Ь задан произвольно, то нет оснований считать, что в случае линейно разделяемых множеств решение с наименьшей квадратичной ошибкой даст разделяющий вектор. Однако можно надеяться, что в случае кан разделяемых, тан и неразделяемых множеств в результате минимизации функции критерия квадратичной ошибки может быть получена нужная разделяющая функция.
Теперь перейдем к исследованию двух свойств решения, подтверждающих данное утверждение. 5.8.2. СВЯЗЬ С ЛИНЕЙНЫМ ДИСКРИМИНАНТОМ ФИШЕРА В данном пункте будет показано, что при соответствующем выборе вектора Ь разделяющая функция а'у, найденная по методу минимальной квадратичной ошибки, непосредственно связана с линейным дискримииантом Фишера. Для того чтобы показать это, следует вернуться к необобщенным линейным разделяющим функциям. Предположим, что имеется множество п е(-мерных выборок х„..., х„, причем и, нз них принадлежат подмножеству Х„, помеченному взз„а пв — подмножеству Х„помеченному вал.
Далее положим, что выборка ув образуется из х, путем прибавления порогового компонента, равного единице, и умножением полученного вектора на — ! в случае выборки, помеченной ва,. Не нарушая общности, можно положить, что первые н, выборок помечены ва„а последующие пв помечены вав. Тогда матрицу У можно представить в сле- дующем виде: б,д. Процедуры минимизации кеадратииноя ошибки !7! где н! является вектор-столбцом нз и, компонент, а Х, — матрицей размера пе~е(, строками которой являются выборки, помеченные иьо Соответствующим образом разло1ким а н Ь: $:.1 ь-( (36) Определяя выборочное среднее т! и матрицу суммарного выбороч- ного разброса 522.
ч-ь гп! —,2, х, 1=1, 2, ' ко,й'! 2 5!о = ~; ~ (х — гп!) (х — пй)е, е= ! х е я'ь. (37) (38) можно в результате перемножения матриц, входящих в (36), полу- чить следующее выражение: (п,ш, + поше)' Зьи+ пьт,ть'+ пететД (не ~ ~п (т, — иь,,) | п (п,ть+ пот,) Полученное выражение может рассматриваться как пара уравнений, причем из первого можно выразить ше через ту: ьое = Ш™ь (39) где т является средним по всем выборкам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
