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

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

(Различия между версиями)

Версия 15:46, 23 ноября 2008

Содержание

1 Введение
2 Методы восстановления регрессии, минимизирующие невязку ответов
3 Методы, минимизирующие расстояния до объектов
- 3.1 Метод наименьших расстояний
- 3.2 Вычисление расстояния между точкой и прямой
4 Сравнение
- 4.1 МНК
- 4.2 МНР
5 Заключение
6 Список литературы

Введение

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

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

x	x₁	x₂	...	x_i	...	x_n
y	y₁	y₂	...	y_i	...	y_n

Требуется наилучшим образом сгладить экспериментальную зависисмость между переменными $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.$

Заключение

Список литературы

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:NikitaN/%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»

@@ Строка 117: / Строка 117: @@
 [[Изображение:1.jpg|300px]]
 Используя необходимое условие экстремума, <tex>\frac{\partial\Psi}{\partial a_k} = 0, k = 0,1,...,m</tex> получаем так называемую нормальную систему метода наименьших квадратов:
 <tex>\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.</tex>
@@ Строка 127: / Строка 128: @@
 [[Изображение:2.jpg|300px]]
 Также из условия экстремума получаем нормальную систему для данного метода.
 <tex>\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.</tex>