Квадратичную ошибку приближения

Среднеквадратичное приближение функций

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

Теория

Пусть значения приближаемой функции f(x) заданы в N+1 узлах f(x₀), …, f(x_N). Аппроксимирующую функцию будем выбирать из некоторого параметрического семейства F(x, c), где c = (c₀, …, c_n)^T — вектор параметров, N > n.

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

В этом случае задача аппроксимации ставится как задача поиска такого вектора параметров c = (c₀, …, c_n)^T, при котором значения аппроксимирующей функции как можно меньше отклонялись бы от значений аппроксимируемой функции  F(x, c) в совокупности всех узлов.

Графически задачу можно представить так

Запишем критерий среднеквадратичного приближения для метода наименьших квадратов:
J( c) = √ (Σ_i=0^N[f(x_i) — F(x, c) ]²) →min

Подкоренное выражение представляет собой квадратичную функцию относительно коэффициентов аппроксимирующего многочлена. Она непрерывна и дифференцируема по c₀, …, c_n. Очевидно, что ее минимум находится в точке, где все частные производные равны нулю. Приравнивая к нулю частные производные, получим систему линейных алгебраических уравнений относительно неизвестных (искомых) коэффициентов многочлена наилучшего приближения.

Метод наименьших квадратов может быть применен для различных параметрических функций, но часто в инженерной практике в качестве аппроксимирующей функции используются многочлены по какому-либо линейно независимому базису {φ_k(x), k=0,…,n}:
F(x, c)  = Σ_k=0ⁿ[c_kφ_k(x)].

В этом случае система линейных алгебраических уравнений для определения коэффициентов будет иметь вполне определенный вид:
a₀₀c₀ + a₀₁c₁ +… + a_0nc_n = b₀
a₁₀c₀ + a₁₁c₁ +… + a_1nc_n = b₁
…
a_n0c₀ + a_n1c₁ +… + a_nnc_n = b_n

a_kj =  Σ_i=0^N    [φ_k(x_i)φ_j(x_i) ], b_j =  Σ_i=0^N[f(x_i)φ_j(x_i) ]

Чтобы эта система имела единственное решение необходимо и достаточно, чтобы определитель матрицы А (определитель Грама) был отличен от нуля. Для того, чтобы система имела единственное решение необходимо и достаточно чтобы система базисных функций φ_k(x), k=0,…,n была линейно независимой на множестве узлов аппроксимации.

В этой статье рассматривается среднеквадратичное приближение многочленами по степенному базису  {φ_k(x) = x^k, k=0,…,n}.

Пример

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

Примем в качестве аппроксимирующей функцию
y = F(x) = c₀ + c₁x + c₂x², то есть, n=2, N=4

Система уравнений для определения коэффициентов:
a₀₀c₀ + a₀₁c₁ +… + a_0nc_n = b₀
a₁₀c₀ + a₁₁c₁ +… + a_1nc_n = b₁
…
a_n0c₀ + a_n1c₁ +… + a_nnc_n = b_n

a_kj =  Σ_i=0^N[φ_k(x_i)φ_j(x_i) ], b_j =  Σ_i=0^N[f(x_i)φ_j(x_i) ]

Коэффициенты вычисляются по формулам:
a₀₀ = N + 1 = 5, a₀₁ = Σ_i=0^Nx_i = 11,25,  a₀₂ = Σ_i=0^Nx_i² = 30,94
a₁₀ = Σ_i=0^Nx_i = 11,25,  a₁₁ = Σ_i=0^Nx_i² = 30,94,  a₁₂ = Σ_i=0^Nx_i³ = 94,92
a₂₀ = Σ_i=0^Nx_i² = 30,94,  a₂₁ = Σ_i=0^Nx_i³ = 94,92,  a₂₂ = Σ_i=0^Nx_i⁴ = 303,76
b₀ = Σ_i=0^Ny_i = 11,25,  b₁ = Σ_i=0^Nx_iy_i = 29,  b₂ = Σ_i=0^Nx_i²y_i = 90,21

Решаем систему уравнений и получаем такие значения коэффициентов:
c₀ = 4,822, c₁ = -3,882, c₂ = 0,999

Таким образом
y = 4,8 — 3,9x + x²

График получившейся функции

Релизация на C#

А теперь перейдем к тому, как написать код, который бы строил такую матрицу. А тут, оказывается, все совсем просто:

private double[,] MakeSystem(double[,] xyTable, int basis)
{
  double[,] matrix = new double[basis, basis + 1];
  for (int i = 0; i < basis; i++)
  {
    for (int j = 0; j < basis; j++)
    {
      matrix[i, j] = 0;
    }
  }
  for (int i = 0; i < basis; i++)
  {
    for (int j = 0; j < basis; j++)
    {
      double sumA = 0, sumB = 0;
      for (int k = 0; k < xyTable.Length / 2; k++)
      {
        sumA += Math.Pow(xyTable[0, k], i) * Math.Pow(xyTable[0, k], j);
        sumB += xyTable[1, k] * Math.Pow(xyTable[0, k], i);
      }
      matrix[i, j] = sumA;
      matrix[i, basis] = sumB;
    }
  }
  return matrix;
}

На входе функция получает таблицу значений функций — матрицу, в первом столбце которой содержатся значения x, во втором, соответственно, y, а также значение степенного базиса.

Сначала выделяется память под матрицу, в которую будут записаны коэффициенты для решения системы линейных уравнений. Затем, собственно, составляем матрицу — в sumA записываются значения коэффициентов aij, в sumB — bi, все по формуле, указанной выше в теоретической части.

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

Скриншот работы программы на примере, решенном выше:

Используемые источники:
Сулимова В.В. Методические указания по курсу «Вычислительный практикум» — Тула, ТулГУ, 2009 — 65 с.

Лабораторная
работа № 18.

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

Общие сведения

Пусть
в результате наблюдений получена таблица
совместно наблюдаемых значений:

Таблица 1

x					
y					

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

(1)

Подставив
в формулу (1) эмпирическое значение
переменной x=
x_i
, получим
теоретическое значение величины y=y_i^т
, вычисленное
по формуле

(2)

Разности

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

Есть разные способы
оценки суммарной ошибки аппроксимации,
Чаще всего оценивают суммарную
квадратичную ошибку, равную сумме
квадратов отклонений эмпирических
значений функции от теоретических:

(3)

Параметры a₁,
a₂,
… , a_m
должны быть определены из условия
минимума суммарной квадратичной ошибки.
Запишем необходимое условие экстремума
функции многих переменных S(a₁,
a₂,
… , a_m):

(4)

Формулы
(4) представляют собой систему m
уравнений с m
неизвестными для определения наилучших
значений параметров. Если функция (1)
линейна относительно параметров a₁,
a₂,
… , a_m,
то система
(4) представляет собой систему линейных
уравнений.

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

Задаваясь конкретным
видом зависимости (1), а именно

1. линейной функцией

y=a₁+a₂x.

(5)

1. квадратичной
   функцией

y=a₁+a₂x+a₃x².
(6)

1. экспоненциальной
   функцией:

.

(7)

1. логарифмической
   функцией

,

(8

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

Достоверность
аппроксимации

Квадратичная
ошибка (погрешность) аппроксимации
функции в соответствии с формулой (3)
равна

.

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

(9)

(10)

(11)

Величина

(12)

называется
коэффициентом детерминированности и
характеризует меру точности аппроксимации
табличных данных функцией любого вида.
Если К²
= 1, то ошибка
аппроксимации равна 0 и теоретические
значения функции совпадают с эмпирическими
значениями.

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

Задание 1

Построить
график зависимости зарплаты от текущего
месяца, если рассматривался период
относительно устойчивого роста зарплаты
в течение четырнадцати месяцев. Данные
представлены в таблице 2. Построить
графики аппроксимирующих функций (линии
тренда)с помощью встроенных средств MS
Excel

Таблица 2

Рис.1.

Решение

1. Открыть
   MS
   Excel

2. Набрать
   таблицу данных и оформить ее по образцу

3. Сохранить
   файл в личной папке

4. Построить
   график данной функции, заданной таблично
   с применением Мастера диаграмм. При
   этом выбрать Тип диаграммы – Точечный,
   Вид диаграммы – соответствующей
   отдельным точкам графика

5. Далее
   построить график линейной аппроксимирующей
   функции – линию тренда, заданную
   линейным уравнением. Для этого выполним
   следующие действия

а) выделим щелчком
мыши график функции;

б) вызовем
контекстное меню щелчком правой кнопки

в) выполним команду
Добавить линию тренда, которая вызовет
диалоговое окно этой команды;

г) в диалоговом
окне команды Линия тренда зададим Тип
аппроксимации — линейная на вкладке
Тип;

д) перейдем на
вкладку окна Параметра, где установим
опции:

показывать на
диаграмме уравнение;

поместить
на диаграмму величину достоверности
аппроксимации R^2;

е) подтвердить
выбор нажатием клавиши OK

Результат построения
представлен на рис.

1. Построить
   график квадратичной аппроксимации –
   квадратичную линию тренда и найти
   уравнение квадратичной аппроксимации.
   Для решения этой задачи нужно повторить
   все действия пунктов 4, 5, но при
   построении линии тренда выбрать Тип
   аппроксимации -Полиномиальная степени
   2. Если вторая линия тренда строится
   на той же диаграмме что и первая, то
   нужно выполнить только п.5

2. Построить
   график экспоненциальной аппроксимации.
   Решение очевидно

Результаты решения
задачи 1 показаны на рис.1-3.

Рис. 2.

Рис. 3.

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

Задание
2

Построить
график зависимости загрязнения воздуха
сернистым газом от расстояния до
источника загрязнения (высокой трубы)
и определить, в каком диапазоне расстояний
концентрация превосходят предельно
допустимую. Предельно допустимая
концентрация равна С=0,:6 мг/и³.
Наблюдения проводились на различных
расстояниях от источника загрязнения
период наименьшей интенсивности.

Данные получены
в утренние часы при наименьших выбросах
промышленного объекта. В дневное и
вечернее время загрязненность выше

Решение:

1. Предварительно
   выполним сортировку данных. Для этого
   выделим ряды данных по R
   и C вместе с заголовками
   и выполним команду Данные|Сортировка.
   В диалоговом окне укажем Сортировку
   по возрастанию и по ряду R.

2.

Таблица 2

Рис.
4.

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

Рис. 5.

0

Соседние файлы в папке prepod

• #
• #
• #
• #
• #
• #

From Wikipedia, the free encyclopedia

In statistics, the mean squared error (MSE)^[1] or mean squared deviation (MSD) of an estimator (of a procedure for estimating an unobserved quantity) measures the average of the squares of the errors—that is, the average squared difference between the estimated values and the actual value. MSE is a risk function, corresponding to the expected value of the squared error loss.^[2] The fact that MSE is almost always strictly positive (and not zero) is because of randomness or because the estimator does not account for information that could produce a more accurate estimate.^[3] In machine learning, specifically empirical risk minimization, MSE may refer to the empirical risk (the average loss on an observed data set), as an estimate of the true MSE (the true risk: the average loss on the actual population distribution).

The MSE is a measure of the quality of an estimator. As it is derived from the square of Euclidean distance, it is always a positive value that decreases as the error approaches zero.

The MSE is the second moment (about the origin) of the error, and thus incorporates both the variance of the estimator (how widely spread the estimates are from one data sample to another) and its bias (how far off the average estimated value is from the true value).^{[citation needed]} For an unbiased estimator, the MSE is the variance of the estimator. Like the variance, MSE has the same units of measurement as the square of the quantity being estimated. In an analogy to standard deviation, taking the square root of MSE yields the root-mean-square error or root-mean-square deviation (RMSE or RMSD), which has the same units as the quantity being estimated; for an unbiased estimator, the RMSE is the square root of the variance, known as the standard error.

Definition and basic properties[edit]

The MSE either assesses the quality of a predictor (i.e., a function mapping arbitrary inputs to a sample of values of some random variable), or of an estimator (i.e., a mathematical function mapping a sample of data to an estimate of a parameter of the population from which the data is sampled). The definition of an MSE differs according to whether one is describing a predictor or an estimator.

Predictor[edit]

If a vector of predictions is generated from a sample of data points on all variables, and is the vector of observed values of the variable being predicted, with being the predicted values (e.g. as from a least-squares fit), then the within-sample MSE of the predictor is computed as

In other words, the MSE is the mean of the squares of the errors . This is an easily computable quantity for a particular sample (and hence is sample-dependent).

In matrix notation,

where is and is the column vector.

The MSE can also be computed on q data points that were not used in estimating the model, either because they were held back for this purpose, or because these data have been newly obtained. Within this process, known as statistical learning, the MSE is often called the test MSE,^[4] and is computed as

Estimator[edit]

The MSE of an estimator with respect to an unknown parameter is defined as^[1]

This definition depends on the unknown parameter, but the MSE is a priori a property of an estimator. The MSE could be a function of unknown parameters, in which case any estimator of the MSE based on estimates of these parameters would be a function of the data (and thus a random variable). If the estimator is derived as a sample statistic and is used to estimate some population parameter, then the expectation is with respect to the sampling distribution of the sample statistic.

The MSE can be written as the sum of the variance of the estimator and the squared bias of the estimator, providing a useful way to calculate the MSE and implying that in the case of unbiased estimators, the MSE and variance are equivalent.^[5]

Proof of variance and bias relationship[edit]

An even shorter proof can be achieved using the well-known formula that for a random variable , . By substituting with, , we have

But in real modeling case, MSE could be described as the addition of model variance, model bias, and irreducible uncertainty (see Bias–variance tradeoff). According to the relationship, the MSE of the estimators could be simply used for the efficiency comparison, which includes the information of estimator variance and bias. This is called MSE criterion.

In regression[edit]

In regression analysis, plotting is a more natural way to view the overall trend of the whole data. The mean of the distance from each point to the predicted regression model can be calculated, and shown as the mean squared error. The squaring is critical to reduce the complexity with negative signs. To minimize MSE, the model could be more accurate, which would mean the model is closer to actual data. One example of a linear regression using this method is the least squares method—which evaluates appropriateness of linear regression model to model bivariate dataset,^[6] but whose limitation is related to known distribution of the data.

The term mean squared error is sometimes used to refer to the unbiased estimate of error variance: the residual sum of squares divided by the number of degrees of freedom. This definition for a known, computed quantity differs from the above definition for the computed MSE of a predictor, in that a different denominator is used. The denominator is the sample size reduced by the number of model parameters estimated from the same data, (n−p) for p regressors or (n−p−1) if an intercept is used (see errors and residuals in statistics for more details).^[7] Although the MSE (as defined in this article) is not an unbiased estimator of the error variance, it is consistent, given the consistency of the predictor.

In regression analysis, «mean squared error», often referred to as mean squared prediction error or «out-of-sample mean squared error», can also refer to the mean value of the squared deviations of the predictions from the true values, over an out-of-sample test space, generated by a model estimated over a particular sample space. This also is a known, computed quantity, and it varies by sample and by out-of-sample test space.

Examples[edit]

Mean[edit]

Suppose we have a random sample of size from a population, . Suppose the sample units were chosen with replacement. That is, the units are selected one at a time, and previously selected units are still eligible for selection for all draws. The usual estimator for the is the sample average

which has an expected value equal to the true mean (so it is unbiased) and a mean squared error of

where is the population variance.

For a Gaussian distribution, this is the best unbiased estimator (i.e., one with the lowest MSE among all unbiased estimators), but not, say, for a uniform distribution.

Variance[edit]

The usual estimator for the variance is the corrected sample variance:

This is unbiased (its expected value is ), hence also called the unbiased sample variance, and its MSE is^[8]

where is the fourth central moment of the distribution or population, and is the excess kurtosis.

However, one can use other estimators for which are proportional to , and an appropriate choice can always give a lower mean squared error. If we define

then we calculate:

This is minimized when

For a Gaussian distribution, where , this means that the MSE is minimized when dividing the sum by . The minimum excess kurtosis is ,^[a] which is achieved by a Bernoulli distribution with p = 1/2 (a coin flip), and the MSE is minimized for Hence regardless of the kurtosis, we get a «better» estimate (in the sense of having a lower MSE) by scaling down the unbiased estimator a little bit; this is a simple example of a shrinkage estimator: one «shrinks» the estimator towards zero (scales down the unbiased estimator).

Further, while the corrected sample variance is the best unbiased estimator (minimum mean squared error among unbiased estimators) of variance for Gaussian distributions, if the distribution is not Gaussian, then even among unbiased estimators, the best unbiased estimator of the variance may not be

Gaussian distribution[edit]

The following table gives several estimators of the true parameters of the population, μ and σ², for the Gaussian case.^[9]

True value	Estimator	Mean squared error
	= the unbiased estimator of the population mean,
	= the unbiased estimator of the population variance,
	= the biased estimator of the population variance,
	= the biased estimator of the population variance,

Interpretation[edit]

An MSE of zero, meaning that the estimator predicts observations of the parameter with perfect accuracy, is ideal (but typically not possible).

Values of MSE may be used for comparative purposes. Two or more statistical models may be compared using their MSEs—as a measure of how well they explain a given set of observations: An unbiased estimator (estimated from a statistical model) with the smallest variance among all unbiased estimators is the best unbiased estimator or MVUE (Minimum-Variance Unbiased Estimator).

Both analysis of variance and linear regression techniques estimate the MSE as part of the analysis and use the estimated MSE to determine the statistical significance of the factors or predictors under study. The goal of experimental design is to construct experiments in such a way that when the observations are analyzed, the MSE is close to zero relative to the magnitude of at least one of the estimated treatment effects.

In one-way analysis of variance, MSE can be calculated by the division of the sum of squared errors and the degree of freedom. Also, the f-value is the ratio of the mean squared treatment and the MSE.

MSE is also used in several stepwise regression techniques as part of the determination as to how many predictors from a candidate set to include in a model for a given set of observations.

Applications[edit]

• Minimizing MSE is a key criterion in selecting estimators: see minimum mean-square error. Among unbiased estimators, minimizing the MSE is equivalent to minimizing the variance, and the estimator that does this is the minimum variance unbiased estimator. However, a biased estimator may have lower MSE; see estimator bias.
• In statistical modelling the MSE can represent the difference between the actual observations and the observation values predicted by the model. In this context, it is used to determine the extent to which the model fits the data as well as whether removing some explanatory variables is possible without significantly harming the model’s predictive ability.
• In forecasting and prediction, the Brier score is a measure of forecast skill based on MSE.

Loss function[edit]

Squared error loss is one of the most widely used loss functions in statistics^{[citation needed]}, though its widespread use stems more from mathematical convenience than considerations of actual loss in applications. Carl Friedrich Gauss, who introduced the use of mean squared error, was aware of its arbitrariness and was in agreement with objections to it on these grounds.^[3] The mathematical benefits of mean squared error are particularly evident in its use at analyzing the performance of linear regression, as it allows one to partition the variation in a dataset into variation explained by the model and variation explained by randomness.

Criticism[edit]

The use of mean squared error without question has been criticized by the decision theorist James Berger. Mean squared error is the negative of the expected value of one specific utility function, the quadratic utility function, which may not be the appropriate utility function to use under a given set of circumstances. There are, however, some scenarios where mean squared error can serve as a good approximation to a loss function occurring naturally in an application.^[10]

Like variance, mean squared error has the disadvantage of heavily weighting outliers.^[11] This is a result of the squaring of each term, which effectively weights large errors more heavily than small ones. This property, undesirable in many applications, has led researchers to use alternatives such as the mean absolute error, or those based on the median.

See also[edit]

• Bias–variance tradeoff
• Hodges’ estimator
• James–Stein estimator
• Mean percentage error
• Mean square quantization error
• Mean square weighted deviation
• Mean squared displacement
• Mean squared prediction error
• Minimum mean square error
• Minimum mean squared error estimator
• Overfitting
• Peak signal-to-noise ratio

Notes[edit]

References[edit]