5.8. ПРОЦЕДУРЫ МИНИМИЗАЦИИ КВАДРАТИЧНОЙ ОШИБКИ

5.8.1. МИНИМАЛЬНАЯ КВАДРАТИЧНАЯ ОШИБКА И ПСЕВДООБРАЩЕНИЕ

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

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

Вид системы линейных уравнений упрощается, если ввести матричные обозначения. Пусть — матрица размера строка которой является вектором и пусть b — вектор-столбец

Тогда наша задача сводится к определению весового вектора а, удовлетворяющего уравнению

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

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

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

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

и задача решения уравнения сводится к задаче решения уравнения . Большим достоинством этого замечательного уравнения является то, что матрица размера квадратная и часто невырожденная. Если данная матрица невырождена, вектор а может быть определен однозначно:

где матрица размера

называется псевдообращением матрицы У. Заметим, что если матрица У квадратная и невырожденная, псевдообращение совпадаете обычным обращением. Следует также отметить, что но обычно . Если матрица УУ вырождена, решение уравнения (32) не будет единственным. Однако решение, обеспечивающее минимальную квадратичную ошибку, существует всегда. В частности, при определении в более общем виде:

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

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

5.8.2. СВЯЗЬ С ЛИНЕЙНЫМ ДИСКРИМИНАНТОМ ФИШЕРА

В данном пункте будет показано, что при соответствующем выборе вектора b разделяющая функция найденная по методу минимальной квадратичной ошибки, непосредственно связана с линейным дискриминантом Фишера. Для того чтобы показать это, следует вернуться к необобщенным линейным разделяющим функциям. Предположим, что имеется множество -мерных выборок причем из них принадлежат подмножеству помеченному — подмножеству S помеченному Далее положим, что выборка образуется из путем прибавления порогового компонента, равного единице, и умножением полученного вектора на —1 в случае выборки, помеченной . Не нарушая общности, можно положить, что первые выборок помечены а последующие помечены Тогда матрицу X можно представить в следующем виде:

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

и

Можно показать, что при определенном выборе b обнаруживается связь между решением по методу наименьшей квадратичной ошибки и линейным дискриминантом Фишера.

Доказательство начнем, записав соотношение (32) для а с использованием разложенных матриц:

Определяя выборочное среднее и матрицу суммарного выборочного разброса

можно в результате перемножения матриц, входящих в (36), получить следующее выражение:

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

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

Поскольку направление вектора при любом w совпадает с направлением вектора то можно записать

следующее выражение:

где a — некоторая скалярная величина. В этом случае соотношение (40) дает

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

5.8.3. АСИМПТОТИЧЕСКОЕ ПРИБЛИЖЕНИЕ К ОПТИМАЛЬНОМУ ДИСКРИМИНАНТУ

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

Чтобы продемонстрировать данное утверждение, следует предположить, что выборки взяты независимо в соответствии с вероятностным законом

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

то нашей задачей будет показать, что величина минимизируется посредством решения

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

Таким образом, в соответствии с законом больших чисел при стремлении к бесконечности приближается с вероятностью 1 к

функции J (а), имеющей вид

где

и

Теперь, если мы из соотношения (42) определим

то получим

Второй член данной суммы не зависит от весового вектора а. Отсюда следует, что а, которое минимизирует , также минимизирует и — среднеквадратичную ошибку между .

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