Проведение поверхностей наилучшего приближения

Материал из MachineLearning.

Версия от 19:29, 28 февраля 2010; Yury Chekhovich (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Содержание

Введение

На практике мы часто сталкиваемся с задачей о сглаживании экспериментальных зависимостей.

Пусть зависимость между двумя переменными x и y выражается в виде таблицы, полученной опытным путем. Это могут быть результаты опыта или наблюдений, статистической обработки материала и т.п.

x x1 x2 ... xi ... xn
y y1 y2 ... yi ... yn

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

Формулы, служащие для аналитического представления опытных данных, получили название эмпирических формул.

Задача нахождения эмпирических формул разбивается на два этапа. На первом этапе нужно установить вид зависимости y = f(x), т.е. решить, является ли она линейной, квадратичной, логарифмической или какой-либо другой. Второй этап – определение неизвестных параметров этой функции.

Часто вид эмпирической зависимости известен, но числовые параметры неизвестны. Будем считать, что зависимость полиномиальная, а для определения параметров полинома рассмотрим следующие методы.

Методы восстановления регрессии, минимизирующие невязку ответов

Метод наименьших квадратов

Основная статья: Метод наименьших квадратов

Пусть функция y = f(x) задана таблицей своих значений: y_i = f(x_i), i = 0,1,...,n. Требуется найти многочлен фиксированной степени m, для которого среднеквадратичное отклонение (СКО) \sigma = \sqrt{\frac{1}{n + 1}\sum^{n}_{i=0}{(P_m(x_i)-y_i)^2}} минимально.

Так как многочлен P_m(x) = a_0+a_1x+a_2x^2+...+a_mx^m определяется своими коэффициентами, то фактически нужно подобрать набор коэффициентов a_0,a_1,...,a_m, минимизирующий функцию \Psi(a_0,a_1,...,a_m) = \sum^{n}_{i=0}{(P_m(x_i)-y_i)^2} = \sum^{n}_{i=0}({\sum^{m}_{j=0}{a_jx_i^j}-y_i)^2}.

Используя необходимое условие экстремума, \frac{\partial\Psi}{\partial a_k} = 0, k = 0,1,...,m получаем так называемую нормальную систему метода наименьших квадратов: \sum^{m}_{j=0}{(\sum^{n}_{i=0}{x_i^{j+k}})a_j} = \sum^{n}_{i=0}{y_ix_i^k}, k = 0,1,...,m.

Полученная система есть система алгебраических уравнений относительно неизвестных a_0,a_1,...,a_m. Можно показать, что определитель этой системы отличен от нуля, то есть решение существует и единственно. Однако при высоких степенях m система является плохо обусловленной. Поэтому метод наименьших квадратов применяют для нахождения многочленов, степень которых не выше 5. Решение нормальной системы можно найти, например, методом Гаусса.

Запишем нормальную систему наименьших квадратов для двух простых случаев: m = 0 и m = 2. При m = 0 многочлен примет вид: P_0(x) = a_0. Для нахождения неизвестного коэффициента a_0 имеем уравнение: (n+1)a_0 = \sum^{n}_{i=0}{y_i}. Получаем, что коэффициент a_0 есть среднее арифметическое значений функции в заданных точках.

Если же используется многочлен второй степени P_2(x) = a_0+a_1x+a_2x^2, то нормальная система уравнений примет вид:

\left\{\begin{matrix} (n+1)a_0 + (\sum^{n}_{i=0}{x_i})a_1 + (\sum^{n}_{i=0}{x_i^2})a_2 = \sum^{n}_{i=0}{y_i},\\ (\sum^{n}_{i=0}{x_i})a_0 + (\sum^{n}_{i=0}{x_i^2})a_1 + (\sum^{n}_{i=0}{x_i^3})a_2 = \sum^{n}_{i=0}{y_ix_i},\\ (\sum^{n}_{i=0}{x_i^2})a_0 + (\sum^{n}_{i=0}{x_i^3})a_1 + (\sum^{n}_{i=0}{x_i^4})a_2 = \sum^{n}_{i=0}{y_ix_i^2} \end{matrix}\right.

Пример

Пусть функция задана таблицей своих значений:

x -3 -1 0 1 3
y -4 -0.8 1.6 2.3 1.5

Приблизим функцию многочленом 2-ой степени. Для этого вычислим коэффициенты нормальной системы уравнений:

\sum^{4}_{i=0}{x_i}=0 ,\sum^{4}_{i=0}{x_i^2}=20 ,\sum^{4}_{i=0}{x_i^3}=0 ,\sum^{4}_{i=0}{x_i^4}=164

\sum^{4}_{i=0}{y_i}=0.6 ,\sum^{4}_{i=0}{y_ix_i}=19.6 ,\sum^{4}_{i=0}{y_ix_i^2}=-21

Составим нормальную систему наименьших квадратов, которая имеет вид:

\left\{\begin{matrix} 5a_0 + 0a_1 + 20a_2 = 0.6,\\ 0a_0 + 20a_1 + 0a_2 = 19.6,\\ 20a_0 + 0a_1 + 164a_2 = -21 \end{matrix}\right.

Решение системы легко находится:a_0 = 1.234,a_1 = 0.98,a_2 = -0.278..

Таким образом, многочлен 2-ой степени найден: P_2(x) = 1.234 +0.98x -0.278x^2..

Нахождение оптимальной степени многочлена

Предположим, что функцию f можно с высокой точностью аппроксимировать многочленом P_m(x) некоторой степени m. Если эта степень заранее неизвестна, то возникает проблема выбора оптимальной степени аппроксимирующего многочлена в условиях, когда исходные данные y_i содержат случайные ошибки. Для решения этой задачи можно принять следующий алгоритм: для каждого m=0,1,2,... вычисляется величина \sigma_m = \sqrt{\frac{1}{n - m}\sum^{n}_{i=0}{(P_m(x_i)-y_i)^2}}. За оптимальное значение степени многочлена следует принять то значение m, начиная с которого величина \sigma_m стабилизируется или начинает возрастать.

Определение параметров эмпирической зависимости

Часто из физических соображений следует, что зависимость y = f(x) между величинами хорошо описывается моделью вида y = g(x,a_0,a_1,...,a_m), где вид зависимости g известен. Тогда применение критерия наименьших квадратов приводит к задаче определения искомых параметров a_0,a_1,...,a_m из условия минимума функции: \Psi(a_0,a_1,...,a_m) = \sum^{n}_{i=0}{(g(x_i,a_0,a_1,...,a_m)-y_i)^2}.

Если зависимость от параметров a_0,a_1,...,a_m нелинейна, то экстремум функции \Psi(a_0,a_1,...,a_m) = \sum^{n}_{i=0}{(g(x_i,a_0,a_1,...,a_m)-y_i)^2} ищут методами минимизации функций нескольких переменных.

Методы, минимизирующие расстояния до объектов

Метод наименьших расстояний

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

Если в МНК минимизировалось среднее квадратичное отклонение (СКО) \sigma = \sqrt{\frac{1}{n + 1}\sum^{n}_{i=0}{(P_m(x_i)-y_i)^2}},то в методе наименьших расстояний берется наименьшее расстояние от объекта до прямой \sigma = \sqrt{\frac{1}{n + 1}\sum^{n}_{i=0}{\rho^2(M_i,L)}}, где M_i - точка (x_i,y_i), а L - прямая,приближающая данную функцию.

И аналогично МНК производятся все вычисления.

Вычисление расстояния между точкой и прямой

Когда прямая задана формулой f(x,y) = ax+by+c = 0 то для любой точки P=(x,y) расстояние \rho(P,L) может быть получено прямо из уравнения: \rho(P,L)=\frac{ax+by+c}{sqrt(a^2+b^2)}.

Сравнение

Рассмотрим линейную функцию y = ax+b

МНК

В методе наименьших квадратов подбираются коэффициенты, минимизирующие функцию \Psi(a,b) = \sum^{n}_{i=0}{(ax_i+b-y_i)^2}

Используя необходимое условие экстремума, \frac{\partial\Psi}{\partial a_k} = 0, k = 0,1,...,m получаем так называемую нормальную систему метода наименьших квадратов: \left\{\begin{matrix} (\sum^{n}_{i=0}{x_i})a + (n+1)b = \sum^{n}_{i=0}{y_i},\\ (\sum^{n}_{i=0}{x_i^2})a + (\sum^{n}_{i=0}{x_i})b = \sum^{n}_{i=0}{y_ix_i}\end{matrix}\right.


МНР

Метод наименьших расстояний для линейного случая отличается функцией, которую минимизируем. \Psi(a,b) = \sum^{n}_{i=0} \frac{(ax_i+b-y_i)^2}{a^2+1}

Также из условия экстремума получаем нормальную систему для данного метода. \left\{\begin{matrix} (\sum^{n}_{i=0}{x_i})a + (n+1)b = \sum^{n}_{i=0}{y_i},\\ (\sum^{n}_{i=0}{x_i^2-y_i^2})a + (\sum^{n}_{i=0}{x_i})b + (\sum^{n}_{i=0}{y_ix_i})a^2 + 2(\sum^{n}_{i=0}{y_i})ab - ab^2 - (\sum^{n}_{i=0}{x_i}) a^2b= \sum^{n}_{i=0}{y_ix_i}\end{matrix}\right.

Пример

Рассмотрим применение данных методов на реальном примере. Пусть имеются точки, координаты которых представлены в таблице.

x -3 -1 0 1 3
y -4 -0.8 1.6 2.3 1.5

Суммы,необходимые для решения нормальных систем, будут такими:

\sum^{4}_{i=0}{x_i}=0 ,\sum^{4}_{i=0}{x_i^2}=20 ,\sum^{4}_{i=0}{y_i^2}=26.74

\sum^{4}_{i=0}{y_i}=0.6 ,\sum^{4}_{i=0}{y_ix_i}=19.6

МНК

Считаем оптимальные параметры a и b.

\left\{\begin{matrix} 0a + 5b = 0.6,\\ 20a + 0b = 19.6 \end{matrix}\right.

\left\{\begin{matrix} a = 0.98,\\ b = 0.12 \end{matrix}\right.

Прямая будет иметь вид:

y = 0.98x+0.12

МНР

Аналогично считаем методом наименьших расстояний.

\left\{\begin{matrix} 0a + 5b = 0.6,\\ -6.74a + 0b + 19.6a^2 + 1.2ab - ab^2 -0a^2b = 19.6 \end{matrix}\right.

\left\{\begin{matrix} \left\[\begin{matrix}a \approx 1.2 ,\\ a \approx -0.85, \end{matrix}\right.\\ b = 0.12 \end{matrix}\right.

y \approx 1.2x+0.12

y \approx -0.85x+0.12

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

Для наглядности результаты представлены на рисунке.

Пример программы

Заключение

В процессе сравнения метода наименьших квадратов и метода наименьших расстояний можно сделать следующие выводы: оба метода дают результаты, мало отличающиеся друг от друга. МНК и МНР достаточно хорошо справляются с задачей построения поверхностей наилучшего приближения, о чем можно судить по результатам для линейного случая. В пространствах более высокого порядка это может быть не так. И вообще МНК в них предпочтительней только потому, что выписать нормальную систему для МНР является нетривиальной задачей (даже для линейного случая порядок уравнений в МНР у нас 3, а в МНК - 2).

Список источников

Источник — «http://recognition.su/wiki/index.php?title=%D0%9F%D1%80%D0%BE%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE%D0%B2%D0%B5%D1%80%D1%85%D0%BD%D0%BE%D1%81%D1%82%D0%B5%D0%B9_%D0%BD%D0%B0%D0%B8%D0%BB%D1%83%D1%87%D1%88%D0%B5%D0%B3%D0%BE_%D0%BF%D1%80%D0%B8%D0%B1%D0%BB%D0%B8%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F»