Least squares
"Хотя это может показаться парадоксальным, вся наука подчинена идее аппроксимации" - эти слова, принадлежащие Бертрану Расселу, отнюдь не кажутся странными, так как задачи, связанные с необходимостью заменить один объект другим, близким в том или ином смысле к первому, но более простым для изучения, возникают очень часто.
В данном разделе мы рассмотрим один из наиболее универсальных инструментов описания данных - метод наименьших квадратов. МНК оказал громадное влияние на методы описания, восстановления и прогнозирования данных самой различной природы. Здесь мы коснемся чуть-чуть нескольких сфер использования МНК. Так, самую малость.

Метод наименьших квадратов (МНК) был придуман в самом начале XIX века почти одновременно тремя учеными, два из которых – это известные математики А. М. Лежандр (1752–1833) и К. Ф. Гаусс (1777–1855), а третим был мало известный математик из Америки, Р.А. Эдрейн (1775–1843), который опубликовал свой вывод нормального закона распределения вероятностей ошибок измерений и применил его «к установлению принципа наименьших квадратов».

А теперь, по сути.

Пусть дана система точек

\(t_i\)\(t_0\)\(t_1\)...\(t_N\)
\(x_i\)\(x_0\)\(x_1\)...\(x_N\)

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

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

Рассматриваемая задача состоит в следующем - нужно выбрать параметры \(\theta^*\) модели, которые объясняют исходные данные как можно лучше.
Чтобы формализовать это, нужно подумать о следующих проблемах: Данная постановка позволяет реализовать переход от наблюдаемого поведения данных к исследованию параметров, которые непосредственно не наблюдаются, но отражают суть процесса. И сделать это можно сделать по-разному. Вот некоторые варианты: Выбор инструмента решения каждый раз зависит от решаемой задачи. Универсальных методов нет, но, тем не менее, есть наиболее часто используемый метод, и это метод наименьших квадратов. И чем это обусловлено? Прежде всего тем, что ключевым моментом всех перечисленных подходов является поиск минимального значения неких параметров. Как помним из курса математического анализа, эта задача разбивается на две - нахождение необходимого и достаточного условий. Если необходимое условие находится достаточно просто - ищем производные функции цели по всем параметрам, приравниваем их нулю, получаем систему уравнений, и - "вуаля!" Значения параметров, которые, возможно, реализуют нашу задачу найдены! То с достаточными условиями все намного, намного сложнее. Во многих случаях нахождение достаточных условий экстремума, вообще, весьма проблематичны. С другой стороны, если функция цели выпукла, то необходимые условия экстремума совпадают с достаточными. Примером выпуклой функции цели является параболоид, то есть, линейная функция, возведенная в квадрат.

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

Перейдем к изложению метода наименьших квадратов.
Поставим в соответствие исходным данным, заданным в виде таблицы, функцию вида \begin{equation} \label{eq1.1} f\left( {\left\{ {a_i } \right\}_{i = 0}^n ,t} \right) = \sum\limits_{i =0}^n {a_i \varphi _i (t) = } a_0 \varphi _0 (t) + a_1 \varphi _1 (t) + ... +a_n \varphi _n (t), \end{equation} где \(\varphi_i (t), i = 0,\ldots ,n \)- базисные функции, а \(a_i -\) неизвестные коэффициенты, подлежащие определению. В частности, если в качестве базисных функций использовать степенные маномы \(\varphi_i (t) =t^i,\) задача сводится к поиску полинома \[ f\left( {\left\{ {a_i } \right\}_{i = 0}^n ,t} \right) = \sum\limits_{i = 0}^n {a_i t^i = } a_0 + a_1 t + ... + a_n t^n \] степени \(n\), приближающего исходную таблицу.
Для определения коэффициентов \(a_i\) будем искать функцию \(f\left( {\left\{{a_i } \right\}_{i = 0}^n ,t} \right)\), отклонение значений которой от заданных таблицей значений \(x_i\) минимально в некотором средне интегральном смысле.


Иллюстрация МНК.

В частности, в дискретном методе наименьших квадратов строится функционал цели \begin{equation}\label{eq1.2} S\left( {a_0 ,a_1 ,...,a_n } \right) = \sum\limits_{i = 0}^N {\left( {f\left( {a_0 ,a_1 ,...,a_n ,t_i } \right) - x_i } \right)^2\rho _i^2 } = \end{equation} \[=\sum\limits_{i = 0}^N {\left( {a_0 \varphi _0 (t_i ) + a_1 \varphi _1 (t_i ) + ... + a_n \varphi _n (t_i ) - x_i } \right)^2\rho _i^2 } , \] где \(\rho_i\) - некоторые неотрицательные числа (весовые коэффициенты). Если все значения равноправны, то весовые коэффициенты берутся равными единице.
Геометрически функционал (\ref{eq1.2}) представляет собой сумму квадратов отклонений с весом \(\rho_i\) экспериментальных данных \(x_i\) от значений аппроксимирующей функции \(f\left( {a_0 ,a_1 ,...,a_n ,t} \right)\) в точках \(t_i (i = 0,\ldots ,N).\)
Необходимым (а в данном случае, в силу выпуклости функционала цели, и достаточным) условием минимума функции многих переменных \[ S\left( {a_0 ,a_1 ,...,a_n } \right) \to \mathop {\min }\limits_{a_0 ,a_1 ,\ldots,a_n } \] является равенство нулю ее частных производных первого порядка по независимым переменным. \begin{equation}\label{eq1.3} \left\{ {{\begin{array}{*{20}c} {\frac{\partial S}{\partial a_0 } = 2\sum\limits_{i = 0}^N {\left( {f\left( {a_0 ,a_1 ,...,a_n ,t_i } \right) - x_i } \right)\varphi _0 \left( {t_i } \right)\rho _i^2 = 0,} } \hfill \\ {\frac{\partial S}{\partial a_1 } = 2\sum\limits_{i = 0}^N {\left( {f\left( {a_0 ,a_1 ,...,a_n ,t_i } \right) - x_i } \right)\varphi _1 \left( {t_i } \right)\rho _i^2 = 0,} } \hfill \\ {........................................................} \hfill \\ {\frac{\partial S}{\partial a_n } = 2\sum\limits_{i = 0}^N {\left( {f\left( {a_0 ,a_1 ,...,a_n ,t_i } \right) - x_i } \right)\varphi _n \left( {t_i } \right)\rho _i^2 = 0.} } \hfill \\ \end{array} }} \right. \end{equation} Полученная система представляет собой систему линейных алгебраических уравнений порядка \(n + 1\) относительно неизвестных \(a_0 ,a_1 ,...,a_n.\) Система разрешима при условии \(n \le N\). Ее матрица является симметрической и положительно определенной. Решения \(a_0 ,a_1 ,...,a_n\) доставляют минимум функционалу (\ref{eq1.2}).
Решение данной системы может быть осуществлено любым из известных методов (например, методом Гаусса, Крамера и др.). Подставляя найденные в результате решения системы (\ref{eq1.3}) значения \(a_0 ,a_1 ,...,a_n \) в (\ref{eq1.1}), получаем функцию \(f(t),\) наилучшим образом приближающую исходные данные в среднеквадратическом смысле. Качество такого приближения может быть оценено величиной среднеквадратичного отклонения \[ \sigma = \sqrt {\frac{1}{N + 1}\sum\limits_{i = 0}^N {\left( {x_i - f\left({t_i } \right)} \right)^2\rho _i^2 } .} \] Достаточно часто естественным условием является требование описания исходных данных прямой или параболой. В этом случае говорят, что используется линейная или квадратичная регрессия.
Рассмотрим случай описания априорных данных прямой, то есть используем метод линейной регрессии. Опишем исходные данные \(\left( {t_i ,x_i } \right),i = 0,1,...,N\) прямой \(x = at + b.\) В этом случае функция цели (\ref{eq1.2}) примет вид \[ S\left( {a,b} \right) = \sum\limits_{i = 0}^N {\left( {at_i + b - x_i } \right)^2} \to \mathop {\min }\limits_{a,b} . \] Необходимое (и, в данном случае, достаточное) условие экстремума имеет вид \[ \left\{ {{\begin{array}{*{20}c} {\frac{\partial }{\partial a}S\left( {a,b} \right) = 2\sum\limits_{i = 0}^N {t_i \left( {at_i + b - x_i } \right)} = 0,} \hfill \\ {\frac{\partial }{\partial b}S\left( {a,b} \right) = 2\sum\limits_{i = 0}^N {\left( {at_i + b - x_i } \right)} = 0,} \hfill \\ \end{array} }} \right. \] или, что то же, \[ \left\{\begin{array}{*{20}c} {a\sum\limits_{i = 0}^N {t_i^2 } + b\sum\limits_{i = 0}^N {t_i } = \sum\limits_{i = 0}^N {x_i t_i } ,} \hfill \\ {a\sum\limits_{i = 0}^N {t_i} + b(N + 1) = \sum\limits_{i = 0}^N {x_i } .} \hfill\\ \end{array} \right. \] Отсюда, применяя метод Крамера решения систем линейных уравнений, сразу получаем коэффициенты прямой (линейной регрессии) \[ a = \frac{(N + 1)\sum\limits_{i = 0}^N {x_i t_i } - \sum\limits_{i = 0}^N {t_i } \sum\limits_{i = 0}^N {x_i } }{(N + 1)\sum\limits_{i = 0}^N {t_i^2 } - \left( {\sum\limits_{i = 0}^N {t_i } } \right)^2},b = \frac{\sum\limits_{i = 0}^N {t_i^2 } \sum\limits_{i = 0}^N {x_i } - \sum\limits_{i = 0}^N {t_i } \sum\limits_{i = 0}^N {x_i t_i } }{(N + 1)\sum\limits_{i = 0}^N {t_i^2 } - \left( {\sum\limits_{i = 0}^N {t_i } } \right)^2}. \]

Оценка точности уравнения регрессии.

Для оценки точности уравнения регрессии используется дисперсионный анализ. Представим общую сумму квадратов отклонений \(x\) от среднего значения \(\bar{x}=\frac{1}{N+1}\sum_{i=0}^Nx_i\): \[ Q=\sum_{i=0}^N(x_i-\bar{x})^2, \] в виде суммы, одна из которых определена влиянием фактора \(t\), другая - неучтенными факторами \begin{equation}\label{e:2} Q=\sum_{i=0}^N(x_i-\bar{x})^2=\sum_{i=0}^N(\tilde{x}_i-\bar{x})^2+\sum_{i=0}^N(x_i-\tilde{x}_i)^2, \end{equation} где \(\tilde{x}_i=at_i+b\).
Здесь \(Q_R=\sum_{i=0}^N(\tilde{x}_i-\bar{x})^2\)- факторная сумма, которую можно объяснить используемой регрессией (влиянием фактора \(t\)) и \(Q_e=\sum_{i=0}^N(x_i-\tilde{x}_i)^2=\sum_{i=0}^Ne_i^2\) - остаточная часть (объяснить нельзя, так как является влиянием неучтенных факторов).


Иллюстрация ошибки линейной регрессии.

Если фактор \(t\) не оказывает влияния на переменную \(x\), то \(Q_R=0\) и \(Q=Q_e\). Если \(Q_R>Q_e\), то влияние \(t\) существенно. Поэтому для повышения эффективности оценки качества данного уравнения регрессии используется коэффициент детерминации \(R^2\) \[ R^2=\frac{Q_R}{Q}=\frac{\sum_{i=0}^N(\tilde{x}_i-\bar{x})^2}{\sum_{i=0}^N(x_i-\bar{x})^2}= 1-\frac{Q_e}{Q}=1-\frac{\sum_{i=0}^Ne_i^2}{\sum_{i=0}^N(x_i-\bar{x})^2}. \] Ясно, что \(R^2\in [0,1]\) и чем ближе \(R^2\) к единице, тем выше качество полученной регрессионной модели.
Другим критерием оценки качества полученной регрессии является средняя относительная ошибка аппроксимации: \[ \bar{\varepsilon}=\frac{1}{N+1}\sum_{i=0}^N\left|\frac{x_i-\tilde{x}_i}{x_i}\right|\times 100\%= \frac{1}{N+1}\sum_{i=0}^N\left|\frac{e_i}{x_i}\right|\times 100\%. \] Если \(\bar{\varepsilon}\lt 10\%\), то полученная модель высокого качества.

Оценка значимости уравнения регрессии в целом.

Из различных уравнений регрессии наилучшим в смысле МНК считают то, которое обеспечивает минимум дисперсии фактических (полученных экспериментально) значений отклика относительно линии регрессии. Эту дисперсию называют остаточной или дисперсией относительно регрессии: \[ S^2_e=\frac{1}{N+1-k}\sum_{i=0}^N(x_i-\tilde{x}_i)^2, \] где \(k\)- число коэффициентов регрессии в уравнении (в нашем случае \(k=2\)).
Для оценки точности аппроксимации исследуемой зависимости выбранным уравнением регрессии сравнивают дисперсию относительно линии регрессии ( \(S_e^2\) ) с оценкой дисперсии значений \(x_i\) относительно выборочного среднего фактических значений отклика \(\bar{x}\): \[ S^2_E=\frac{1}{k-1}\sum_{i=0}^N(x_i-\bar{x})^2. \] Величина \(S^2_E\) характеризует рассеяние \(x_i\), обусловленное зависимостью отклика от факторов, и поэтому называется объясненной дисперсией. Остаточная дисперсия \(S_e^2\) характеризует рассеяние \(x_i\) , вызванное случайными воздействиями (возмущениями). Очевидно, что связь между откликом и факторами в виде данного уравнения регрессии существует, если объясненная дисперсия существенно больше остаточной.
Чтобы выяснить, можно ли считать отличие рассматриваемых дисперсий существенным, выдвигают нулевую гипотезу об их равенстве \(H_0:S^2_E=S^2_e\) и проверяют ее с использованием значений распределения Фишера: \[ F=\frac{S^2_E}{S^2_e}. \] Гипотеза считается справедливой, если рассчитанное число Фишера не превышает табличного значения \(F[\alpha,\nu_1,\nu_2]\) для заданного уровня значимости \(\alpha\). При выборе табличного значения важно помнить, что в данном случае \(\nu_1=\nu_E=k-1\) и \(\nu_2=\nu_e=N+1-k\).
Справедливость гипотезы о равенстве остаточной и объясненной дисперсий означает, что выбранное уравнение регрессии нельзя принимать в качестве модели связи между откликом и фактором.
Если же \(F\gt F [\alpha, k -1, N+1-k] \), то объясненная дисперсия существенно больше остаточной. А это означает, что между откликом и факторами существует взаимосвязь, которую с вероятностью \(\alpha\) допустимо аппроксимировать рассматриваемым уравнением регрессии.
Из нескольких допустимых аппроксимаций наиболее точной,очевидно, будет та, для которой значение \(S_e^2\) является наименьшим. Отсюда следует, что для наиболее точной модели различие расчетного и табличного чисел Фишера будет максимальным.
На практике для вычисления статистики F используют формулу, связывающую ее с коэффициентом детерминации \[ F=\frac{R^2}{1-R^2}(N+1-k). \]

Множественная линейная регрессия.

Рассмотрим простую задачу построения линейной регрессии для случая многих переменных, то есть, когда на модель оказывает влияние не один, а несколько факторов. В этом случае для наблюдений \[ (t_{i,1},t_{i,2},...,t_{i,n},x_i),i=0,...,N \] строим линейную модель множественной регрессии: \begin{equation}\label{m:1} f\left( {\left\{ {a_i } \right\}_{i = 0}^n ,t} \right) = a_0+\sum\limits_{i =1}^n {a_i t_i}= a_0 + a_1 t_1 + ... +a_n t_n, \end{equation} и задача поиска методом наименьших квадратов параметров данной модели будет иметь вид \[ \textbf{S}=\|\textbf{T}\textbf{A}-\textbf{X}\|^2=\sum_{i=0}^N\left(\sum_{j=1}^na_jt_{i,j}+a_0-x_i\right)^2\to\min_{a_j}, \] где \[ \textbf{T}=\left( \begin{array}{ccccc} 1 & t_{0,1} & t_{0,2} & ... & t_{0,n} \\ 1 & t_{1,1} & t_{1,2} & ... & t_{1,n} \\ 1& t_{2,1} & t_{2,2} & ... & t_{2,n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & t_{N,1} & t_{N,2} & ... & t_{N,n} \\ \end{array} \right), \textbf{A}=\left( \begin{array}{ccccc} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_n \\ \end{array} \right), \textbf{X}=\left( \begin{array}{ccccc} x_0 \\ x_1 \\ x_2 \\ \vdots \\ x_N \\ \end{array} \right). \] Для решения этой задачи найдем производные целевой функции \[ \frac{\partial \textbf{S}}{\partial a_k}=2\sum_{i=0}^N t_{i,k}\left(\sum_{j=1}^na_jt_{i,j}+a_0-x_i\right)= 2\left(\textbf{T}^T(\textbf{T}\textbf{A}-\textbf{X})\right)_k \] и вычислим градиент \[ \nabla \textbf{S}=\left(\frac{\partial \textbf{S}}{\partial a_0},\frac{\partial \textbf{S}}{\partial a_1}, ...,\frac{\partial \textbf{S}}{\partial a_n} \right)=2\left(\textbf{T}^T(\textbf{T}\textbf{A}-\textbf{X})\right). \] Нахождения оптимальных параметров методом МНК сводится к решению матричного уравнения \[ \nabla \textbf{S}=2\left(\textbf{T}^T(\textbf{T}\textbf{A}-\textbf{X})\right)=0. \] Отсюда получаем \[ (\textbf{T}^T\textbf{T})\textbf{A}=\textbf{T}^T\textbf{X} \] и искомое решение равно \[ \textbf{A}=(\textbf{T}^T\textbf{T})^{-1}\textbf{T}^T\textbf{X}. \] В принципе, задача решена, проблема только в вычислительной сложности полученного решения. Для того, чтобы получить более простой (в вычислительном смысле) алгоритм, можно использовать QR-факторизацию, то есть, представление \(\textbf{T}=\textbf{Q}\textbf{R}\), где первая из матриц ортогональная \(\textbf{Q}^T\textbf{Q}=\textbf{I}\), а вторая треугольная, тогда \[ \textbf{A}=(\textbf{T}^T\textbf{T})^{-1}\textbf{T}^T\textbf{X}=((\textbf{Q}\textbf{R})^T(\textbf{Q}\textbf{R}))^{-1} (\textbf{Q}\textbf{R})^T\textbf{X}= (\textbf{R}^T\textbf{Q}^T\textbf{Q}\textbf{R})^{-1}\textbf{R}^T\textbf{Q}^T\textbf{X}= \textbf{R}^{-1}\textbf{R}^{-T}\textbf{R}^T\textbf{Q}^{T}\textbf{X}= \textbf{R}^{-1}\textbf{Q}^{T}\textbf{X}. \] Ну и несколько слов о том, как получить эту факторизацию. Для этого можно использовать ортогонализацию (процесс) Грама-Шмидта.
Пусть дана матрица \[ \textbf{B}=\left[\textbf{b}_1|\textbf{b}_2|...|\textbf{b}_n\right]. \] Тогда \[ \textbf{u}_1=\textbf{b}_1,\textbf{e}_1=\frac{\textbf{u}_1}{\|\textbf{u}_1\|}, \] \[ \textbf{u}_2=\textbf{b}_2-(\textbf{b}_2,\textbf{e}_1)\textbf{e}_1,\textbf{e}_2=\frac{\textbf{u}_2}{\|\textbf{u}_2\|}, \] \[ \textbf{u}_{k+1}=\textbf{b}_{k+1}-(\textbf{b}_{k+1},\textbf{e}_1)\textbf{e}_1-...-(\textbf{b}_{k+1},\textbf{e}_k)\textbf{e}_k, \textbf{e}_{k+1}=\frac{\textbf{u}_{k+1}}{\|\textbf{u}_{k+1}\|}. \] Тогда результат QR-факторизации можно записать в виде \[ \textbf{B}=\left[\textbf{b}_1|\textbf{b}_2|...|\textbf{b}_n\right]= \left[\textbf{e}_1|\textbf{e}_2|...|\textbf{e}_n\right] \left[ \begin{array}{cccc} \textbf{b}_1\textbf{e}_1 & \textbf{b}_2\textbf{e}_1 & ... & \textbf{b}_n\textbf{e}_1 \\ 0 & \textbf{b}_2\textbf{e}_2 & ... & \textbf{b}_n\textbf{e}_2 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & ... & \textbf{b}_n\textbf{e}_n \\ \end{array} \right] \] Пример. \[ \textbf{B}=\left[\textbf{b}_1|\textbf{b}_2|\textbf{b}_n\right]= \left[ \begin{array}{ccc} 1 &1 & 0 \\ 1 & 0& 1 \\ 0 &1 & 1 \\ \end{array} \right], \] то есть \(\textbf{b}_1=(1,1,0)^T,\textbf{b}_2=(1,0,1)^T,\textbf{b}_3=(0,1,1)^T.\)
Тогда \[ \textbf{u}_1=\textbf{b}_1=(1,1,0), \textbf{e}_1=\frac{\textbf{u}_1}{\|\textbf{u}_1\|}= \frac{1}{\sqrt{2}}(1,1,0)=\left(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}},0\right), \] \[ \textbf{u}_2=\textbf{b}_2-(\textbf{b}_2,\textbf{e}_1)\textbf{e}_1=(1,0,1)-\frac{1}{\sqrt{2}}\left(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}},0\right)= \left(\frac{1}{2},-\frac{1}{2},1\right), \textbf{e}_2=\frac{\textbf{u}_2}{\|\textbf{u}_2\|}= \frac{\sqrt{2}}{\sqrt{3}}\left(\frac{1}{2},-\frac{1}{2},1\right)=\left(\frac{1}{\sqrt{6}},-\frac{1}{\sqrt{6}},\frac{2}{\sqrt{6}}\right), \] \[ \textbf{u}_3=\textbf{b}_3-(\textbf{b}_3,\textbf{e}_1)\textbf{e}_1-(\textbf{b}_3,\textbf{e}_2)\textbf{e}_2 =(0,1,1)-\frac{1}{\sqrt{2}}\left(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}},0\right) -\frac{1}{\sqrt{6}}\left(\frac{1}{\sqrt{6}},-\frac{1}{\sqrt{6}},\frac{2}{\sqrt{6}}\right)= \left(-\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}}\right), \textbf{e}_3=\frac{\textbf{u}_3}{\|\textbf{u}_3\|}= \left(-\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}}\right). \] Остается только выписать ответ \[ \textbf{Q}=\left[\textbf{e}_1|\textbf{e}_2|\textbf{e}_n\right]= \left[ \begin{array}{ccc} \frac{1}{\sqrt{2}} &\frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{3}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{6}}& \frac{1}{\sqrt{3}} \\ 0 &\frac{2}{\sqrt{6}} & \frac{1}{\sqrt{3}} \\ \end{array} \right], \textbf{R}= \left[ \begin{array}{ccc} \textbf{b}_1\textbf{e}_1&\textbf{b}_2\textbf{e}_1 & \textbf{b}_3\textbf{e}_1 \\ 0 & \textbf{b}_2\textbf{e}_2& \textbf{b}_3\textbf{e}_2 \\ 0 &0 & \textbf{b}_3\textbf{e}_3 \\ \end{array} \right]= \left[ \begin{array}{ccc} \frac{2}{\sqrt{2}} &\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ 0 & \frac{3}{\sqrt{6}}& \frac{1}{\sqrt{6}} \\ 0 &0 & \frac{2}{\sqrt{3}} \\ \end{array} \right]. \]

Вероятностное обоснование метода наименьших квадратов.

Как уже говорилось ранее, если при построении аппроксимации нет возможности точно и четко выбрать критерий качества, то следует использовать метод наименьших квадратов. Рассмотрим еще одно обоснование использования МНК, опирающееся на вероятностный подход.
Как и ранее, пусть \[ \textbf{X}=\textbf{T}\textbf{A}+\textbf{E} \] где \[ \textbf{T}=\left( \begin{array}{ccccc} 1 & t_{0,1} & t_{0,2} & ... & t_{0,n} \\ 1 & t_{1,1} & t_{1,2} & ... & t_{1,n} \\ 1& t_{2,1} & t_{2,2} & ... & t_{2,n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & t_{N,1} & t_{N,2} & ... & t_{N,n} \\ \end{array} \right)= \left( \begin{array}{c} \textbf{T}_0 \\ \textbf{T}_1 \\ \textbf{T}_2 \\ \vdots \\ \textbf{T}_N \\ \end{array} \right), \textbf{A}=\left( \begin{array}{c} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_n \\ \end{array} \right), \textbf{X}=\left( \begin{array}{c} x_0 \\ x_1 \\ x_2 \\ \vdots \\ x_N \\ \end{array} \right) , \textbf{E}=\left( \begin{array}{c} \varepsilon_0 \\ \varepsilon_1 \\ \varepsilon_2 \\ \vdots \\ \varepsilon_N \\ \end{array} \right). \] Здесь \( \varepsilon_i\) - ошибка восстановления \(i-\)го изменения. Значение \( \varepsilon_i\) отражает влияние неучтенных факторов, среди которых случайный шум. Предположим далее, что \( \varepsilon_i\) распределены в соответствии с распределением Гаусса (так называемое нормальное распределение) со средним значением равным нулю и дисперсией \(\sigma^2\), тогда плотность распределения ошибки будет \[ p\left( \varepsilon_i\right)=\frac{1}{\sigma\sqrt{2\pi}}\exp\left(-\frac{ \varepsilon_i^2}{2\sigma^2}\right). \] и, соответственно, \[ p\left(x_i|\textbf{T}_i;\textbf{A}\right)=\frac{1}{\sigma\sqrt{2\pi}}\exp\left(-\frac{ (x_i-\textbf{T}_i\textbf{A})^2}{2\sigma^2}\right). \] Здесь \(p\left(x_i|\textbf{T}_i;\textbf{A}\right)\) функция вероятности случайной величины \(\textbf{T}\) при наблюдении \(\textbf{T}_i\), параметризованная по \(\textbf{A}\). Заметим, что так как \(\textbf{A}\) не является случайной величиной, то правильнее распределение \(x_i\) записать так \(x_i|\textbf{T}_i: \textbf{A}\sim \mathcal{N}(\textbf{T}_i\textbf{A},\sigma^2).\)
Если использование вероятности позволяет предсказывать неизвестные результаты, основанные на известных параметрах, то функция правдоподобия позволяет оценивать неизвестные параметры, основанные на известных результатах. Выпишем функцию правдоподобия \[ \mathcal{L}(\textbf{A})=\mathcal{N}(\textbf{A};\textbf{T},\textbf{X})=p(\textbf{X}|\textbf{T};\textbf{A}) \] и полагая, что \( \varepsilon_i\) независимы, получаем \[ \mathcal{L}(\textbf{A})=\prod_{i=0}^Np(x_i|\textbf{T}_i;\textbf{A})=\prod_{i=0}^N\frac{1}{\sigma\sqrt{2\pi}}\exp\left(-\frac{ (x_i-\textbf{T}_i\textbf{A})^2}{2\sigma^2}\right). \] Теперь, учитывая вероятностную модель, связывающую \(x_i\) и \(\textbf{T}_i\), требуется так выбрать параметры \(\textbf{A}\), чтобы результат, полученный при использовании аппроксимационной модели, был наиболее близким к результатам наблюдений, то есть сделать результаты аппроксимации максимально возможными.
Принцип максимального правдоподобия говорит, что следует выбрать \(\textbf{A}\) так, чтобы максимизировать \(\mathcal{L}(\textbf{A})\). Вместо максимизации \(\mathcal{L}(\textbf{A})\) можно максимизировать любую строго возрастающую функцию от \(\mathcal{L}(\textbf{A})\), в частности, все будет проще, если использует натуральный логарифм функции правдоподобия \[ \ell(\textbf{A})=\ln \mathcal{L}(\textbf{A})=\ln \prod_{i=0}^Np(x_i|\textbf{T}_i;\textbf{A})=\ln\prod_{i=0}^N\frac{1}{\sigma\sqrt{2\pi}}\exp\left(-\frac{ (x_i-\textbf{T}_i\textbf{A})^2}{2\sigma^2}\right) =\prod_{i=0}^N\ln\frac{1}{\sigma\sqrt{2\pi}}\exp\left(-\frac{ (x_i-\textbf{T}_i\textbf{A})^2}{2\sigma^2}\right) =(N+1)\ln \frac{1}{\sigma\sqrt{2\pi}}- \frac{1}{\sigma^2}\cdot \frac{1}{2}\sum_{i=0}^N (x_i-\textbf{T}_i\textbf{A})^2. \] Таким образом, задача максимизации \(\ell(\textbf{A})\) сводится к минимизации \[ \sum_{i=0}^N (x_i-\textbf{T}_i\textbf{A})^2, \] то есть, приходим к методу наименьших квадратов.

Линеаризация при методе наименьших квадратов.

Приведенная методология определения аппроксимирующих функций методом наименьших квадратов годится лишь для функций, у которых неопределенные коэффициенты заданы линейно. Если же это условие не выполняется, то прямое использование метода наименьших квадратов невозможно.
Как же быть в этом случае? Возможно ли вообще использовать в таких случаях метод наименьших квадратов? Да. Возможно. Но тогда нужно проводить некоторые дополнительные построения, линеаризующие (по коэффициентам) приближающую функцию.
Проиллюстрируем это на нескольких примерах.
  1. Пусть приближающая функция имеет вид \(x = \frac{1}{\alpha t + \beta }\).
    Тогда для \(x_i \)ошибка будет равна \begin{equation}\label{eq1.4} \delta _i = x_i - \frac{1}{\alpha t_i + \beta }. \end{equation} Прямое использование метода наименьших квадратов приводит к минимизации величины \begin{equation} \label{eq1.5} S(\alpha ,\beta ) = \sum\limits_{i = 1}^n {\delta _i ^2} = \sum\limits_{i = 1}^n {\left( {x_i - \frac{1}{\alpha t_i + \beta }} \right)^2} . \end{equation} Взяв частные производные по \(\alpha \)и \(\beta \), и приравняв их нулю, получим систему из двух нелинейных уравнений, \[ \left\{ {{\begin{array}{*{20}c} {\frac{\partial S(\alpha ,\beta )}{\partial \alpha } = 2\sum\limits_{i = 1}^n {\left( {x_i - \frac{1}{\alpha t_i + \beta }} \right)\frac{t_i }{(\alpha t_i + \beta )^2} = 0,} } \hfill \\ {\frac{\partial S(\alpha ,\beta )}{\partial \alpha } = 2\sum\limits_{i = 1}^n {\left( {x_i - \frac{1}{\alpha t_i + \beta }} \right)\frac{1}{(\alpha t_i + \beta )^2} = 0,} } \hfill \\ \end{array} }} \right. \] которая не подлежит точному решению. В связи с этим, проведем некоторые построения.
    Рассмотрим величины \[ \Delta _i = x_i \left( {\alpha t_i + \beta } \right) - 1,(i = 1,2,...,n). \] Установим зависимость между \(\Delta _i \) и \(\delta _i \). Из (\ref{eq1.4}) получаем \[ \alpha t_i + \beta = \frac{1}{x_i - \delta _i }. \] Тогда \[ \Delta _i = \frac{x_i }{x_i - \delta _i } - 1 = \frac{\delta _i }{x_i - \delta _i },(i = 1,2,...,n), \] и, следовательно, при малых \(\Delta _i \) \[ \delta _i = \frac{x_i \Delta _i }{\Delta _i + 1} \approx x_i \Delta_i. \] Тогда задача (\ref{eq1.5}) сводится к задаче определения коэффициентов \(\alpha \) и \(\beta \)так, чтобы величина \[ \sum\limits_{i = 1}^n {\left( {x_i \Delta _i } \right)^2} = \sum\limits_{i = 1}^n {\left( {1 - \alpha t_i x_i - \beta x_i } \right)^2x_i^2 .} \] была минимальной.
    Таким образом, мы пришли к задаче (\ref{eq1.2}) при условии, что приближаемая функция тождественно равна единице и \(\varphi _0 (t) = tx(t),\varphi _1 (t) = x(t)\) с весом \(\rho _i = x_i .\)
    Погрешность приближения имеет вид \[ \sigma = \sqrt {\frac{1}{n}\sum\limits_{i = 1}^n {\left( {x_i - \frac{1}{\alpha t_i + \beta }} \right)^2} } . \]
  2. Рассмотрим другой пример. Пусть приближающая функция имеет вид \[ x = \frac{t}{\alpha t + \beta }. \] Для \(x_i \) ошибка будет равна \begin{equation} \label{eq1.6} \delta _i = x_i - \frac{t_i }{\alpha t_i + \beta } \end{equation} и \[ \Delta _i = x_i \left( {\alpha t_i + \beta } \right) - t_i ,(i = 1,2,...,n). \] Установим связь между \(\Delta _i \)и \(\delta _i \). Из (\ref{eq1.6}) имеем \[ \alpha t_i + \beta = \frac{t_i }{x_i - \delta _i }. \] Тогда \[ \Delta_i = \frac{t_i x_i }{x_i - \delta _i } - t_i = \frac{t_i \delta_i }{x_i - \delta _i },(i = 1,2,...,n), \] Отсюда при малых \(\Delta _i \) \[ \delta _i = \frac{x_i \Delta _i }{\Delta _i + t_i } \approx \frac{x_i }{t_i }\Delta _i . \] Для малых \(\delta _i \) \[ \sum\limits_{i = 1}^n {\delta _i ^2} \approx \sum\limits_{i = 1}^n {\left({\frac{x_i }{t_i }\Delta _i } \right)^2} \] и \[ \sum\limits_{i = 1}^n {\left( {\frac{x_i }{t_i }\Delta _i } \right)^2} = \sum\limits_{i = 1}^n {\left( {t_i - \alpha t_i x_i - \beta x_i } \right)^2\left( {\frac{x_i }{t_i }} \right)^2} . \] Таким образом, мы пришли к задаче (\ref{eq1.2}) при условии, что приближаемая функция тождественно равна \(t\)и \(\varphi _0 (t) = tx(t),\varphi _1 (t) =x(t)\) и \(\rho _i = x_i /t_i.\)
    Погрешность приближения имеет вид \[ \sigma = \sqrt {\frac{1}{n}\sum\limits_{i = 1}^n {\left( {x_i - \frac{t_i}{\alpha t_i + \beta }} \right)^2} } . \]
  3. Наконец, пусть приближающая функция имеет вид \[ x = \frac{\alpha t + \beta }{\gamma t + 1}. \] Задача состоит в нахождении коэффициентов \(\alpha \), \(\beta\), \(\gamma\), при которых величина \[ \sum\limits_{i = 1}^n {\delta _i^2 = } \sum\limits_{i = 1}^n {\left( {x_i - \frac{\alpha t_i + \beta }{\gamma t_i + 1}} \right)^2} \] будет минимальной. Линеаризуем эту задачу.
    Пусть \[ \Delta _i = \gamma t_i x_i + x_i - \alpha t_i - \beta ,(i = 1,2,...,n). \] Установим связь между \(\Delta _i \)и \(\delta _i \). Из предыдущего получаем \[ \frac{\Delta _i }{\gamma t_i + 1} = x_i - \frac{\alpha t_i + \beta }{\gamma t_i + 1}. \] Таким образом, имеем \[ \frac{\Delta _i }{\gamma t_i + 1} = \delta _i . \] Для малых \(\delta _{i}\) получаем задачу, эквивалентную искомой \[ \sum\limits_{i = 1}^n {\left( {\frac{\Delta _i }{\gamma t_i + 1}} \right)^2} = \sum\limits_{i = 1}^n {\left( {x_i - \alpha t_i - \beta + \gamma t_i x_i } \right)^2\left( {\frac{1}{\gamma t_i + 1}} \right)^2 \to \min } . \] Использовать метод наименьших квадратов не представляется возможным, так как в "вес" входит неизвестный параметр \(\gamma {\rm u}\)Поэтому рассмотрим итерационный метод пошагового уточнения весовых коэффициентов.
    Для задачи (\ref{eq1.2}) положим \(\varphi _0 (t) = t,\varphi _1 (t) = 1,\varphi _2 (t) = - tx(t)\)и \(\rho _i = 1.\) Решая эту задачу, получаем первое приближение \(\alpha_1, \beta_1, \gamma_1 \).
    Полагая теперь \(\varphi _0 (t) = t,\varphi _1 (t) = 1,\varphi _2 (t) = -tx(t), \quad \rho _i = \frac{1}{\gamma _1 t_i + 1}.\)и снова решая эту задачу, получаем \(\alpha _2 ,\beta _2 ,\gamma _2 \). Продолжая этот процесс при \(\varphi _0 (t) = t,\varphi _1 (t) = 1,\varphi _2 (t) = - tx(t), \quad \rho _i = \frac{1}{\gamma _2 t_i + 1},\) получим следующее приближение значений \(\alpha ,\beta ,\gamma \).
    Итерацию будем продолжать до тех пор пока не будут выполняться соотношения \[ \left\{ {{\begin{array}{*{20}c} {\left| {\alpha _k - \alpha _{k - 1} } \right| \lt \varepsilon ,} \hfill \\ {\left| {\beta _k - \beta _{k - 1} } \right| \lt \varepsilon ,} \hfill \\ {\left| {\gamma _k - \gamma _{k - 1} } \right| \lt \varepsilon ,} \hfill \\ \end{array} }} \right. \] где \(\varepsilon \)- заданная погрешность. Естественно, все множество используемых регрессионных моделей не исчерпывается дробно-линейными функциями, достаточно часто используются степенные и показательные функции.
  4. Будем искать приближающую функцию в виде \(x = \alpha t^\beta \). Для всех \(i = 1,2,\ldots ,n\) положим \(\delta _i = x_i - \alpha t_i^\beta \)и \[ \Delta _i = \ln x_i - \ln \alpha - \beta \ln t_i = \ln \frac{x_i }{\alpha t_i^\beta }. \] Далее, установим связь между этими величинами. Из первого равенства найдем \(\alpha t_i^\beta = x_i - \delta _i \)и подставим во второе \[ \Delta _i = \ln \frac{x_i }{x_i - \delta _i }. \] Отсюда \(x_i - \delta _i = x_i \exp \left( { - \Delta _i } \right)\)при малых \(\Delta _i \)можем записать \(\delta _i = x_i \left( {1 - \exp \left( { -\Delta _i } \right)} \right) \approx x_i \Delta _i .\)Таким образом, задачу минимизации величины \(\sum\limits_{i = 1}^n {\delta _i ^2} \) можно заменить задачей минимизации величины \[ \sum\limits_{i = 1}^n {\left( {x_i \Delta _i } \right)^2 = } \sum\limits_{i= 1}^n {\left( {\ln x_i - \ln \alpha - \beta \ln t_i } \right)^2} x_i^2 , \] которая является задачей (\ref{eq1.2}).
    Погрешность приближения имеет вид \[ \sigma = \sqrt {\frac{1}{n}\sum\limits_{i = 1}^n {\left( {x_i - \alpha t_i^\beta } \right)^2} } . \]
  5. Пусть приближающая функция задана в виде \(x = \alpha \beta ^t\). Для всех \(i = 1,2,\ldots ,n\) положим \[\delta _i = x_i - \alpha \beta ^{t_i }\] и \[\Delta _i = \ln x_i - \ln \alpha - t_i \ln \beta = \ln \frac{x_i }{\alpha \beta ^{t_i }}.\] Найдем связь между этими величинами.
    Выражая из первого равенства \(\alpha \beta ^{t_i } = x_i - \delta _i \) и подставляя во второе, получаем \[ \Delta _i = \ln \frac{x_i }{x_i - \delta _i }. \] Следовательно, \(\delta _i = x_i \left( {1 - \exp \left( { - \Delta _i }\right)} \right) \approx x_i \Delta _i .\)Таким образом, по аналогии, задачу минимизации величины \(\sum\limits_{i = 1}^n {\delta _i ^2} \) можно заменить задачей минимизации величины \[ \sum\limits_{i = 1}^n {\left( {x_i \Delta _i } \right)^2 = } \sum\limits_{i = 1}^n {\left( {\ln x_i - \ln \alpha - t_i \ln \beta } \right)^2} x_i^2 , \] которая является задачей (\ref{eq1.2}).
    Погрешность приближения будет иметь вид \[ \sigma = \sqrt {\frac{1}{N}\sum\limits_{i = 1}^N {\left( {x_i - \alpha \beta ^{t_i }} \right)^2} } . \]

Пример построения функции регрессии

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

Полиномиальная регрессия


Нелинейная регрессия


График

Данные

Сплайн-регрессионные модели.

Линейная фильтрация сигналов.

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


Оригинальный сигнал + помехи = исходные данные.

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

Фильтр Колмогорова-Винера.

Использование оптимальной фильтрации для обработки изображений.

Логистическая регрессия и задача классификации.

Теперь поговорим о проблеме классификации с точки зрения МНК. В отличие от задачи регрессии, задача классификации сводится к тому, что прогнозируемая величина принимает значения из заданного конечного множества. Рассмотрим случай бинарной классификации, то есть, величина \(x_i\) может принимать только два значения: 0 и 1.
Это не так и плохо, бинарная классификация, достаточно распространенный случай - "любит - не любит", "плюнет - поцелует", в конце концов, "true-false".
Итак, пусть регрессионная модель имеет вид \[ f\left( \textbf{A} ,\textbf{t} \right)=g\left( \textbf{A}^T \textbf{t} \right)= \frac{1}{1+\exp\left(-\textbf{A}^T \textbf{t}\right)}, \textbf{A}=\left( \begin{array}{c} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_n \\ \end{array} \right), \textbf{t}=\left( \begin{array}{c} 1\\ t_1 \\ t_2 \\ \vdots \\ t_n \\ \end{array} \right) \] и \begin{equation}\label{sigmoid} g(z)=\frac{1}{1+e^{-z}}. \end{equation} Данная модель называется логистической, а функция (\ref{sigmoid}) называется сигмоидом.
Ясно, что при \(z\to -\infty\) будет \(g(z)\to 0 \) и при \(z\to \infty\) будет \(g(z)\to 1 \).
Будем считать, что наблюдаемые значения могут быть принимать только два значения \(x_i=\{0,1\}\).


Графики логистической регрессии по множеству красных точек, синих точек и общая (черным цветом).

Выпишем производную сигмоида, это нам понадобится в дальнейшем. \[ g'(z)=\frac{d}{dz}\frac{1}{1+e^{-z}}=\frac{1}{(1+e^{-z})^2}e^{-z}=\frac{1}{(1+e^{-z})^2}\left(1-\frac{1}{1+e^{-z}}\right)= g(z)(1-g(z)). \] Рассматривая линейную регрессию как вероятностную модель, мы пришли к задаче максимального правдоподобия. Применим эту же идею к логистической регрессии.
Пусть \[ P(x=1|\textbf{T},\textbf{A})=f\left( \textbf{A} ,\textbf{T} \right), \] \[ P(x=0|\textbf{T},\textbf{A})=1-f\left( \textbf{A} ,\textbf{T} \right). \] Тогда \[ p(x|\textbf{T},\textbf{A})=\left(f\left( \textbf{A} ,\textbf{T} \right)\right)^x\left(1-f\left( \textbf{A} ,\textbf{T} \right)\right)^{1-x}. \] Полагая, что все наблюдения независимы, получаем функцию правдоподобия \[ \mathcal{L}(\textbf{A})=p(\textbf{X}|\textbf{T},\textbf{A})=\prod_{i=0}^Np(x_i|\textbf{T}_i,\textbf{A})= \prod_{i=0}^N\left(f\left( \textbf{A} ,\textbf{T}_i \right)\right)^{x_i}\left(1-f\left( \textbf{A} ,\textbf{T}_i \right)\right)^{1-x_i}. \] В силу монотонности, для поиска максимума вместо функции правдоподобия можно рассмотреть ее логарифм \[ \ell(\textbf{A})=\ln\mathcal{L}(\textbf{A})=\sum_{i=0}^N\left(x_i\ln f\left( \textbf{A} ,\textbf{T}_i \right)\right)+ (1-x_i)\left(1-f\left( \textbf{A} ,\textbf{T}_i \right)\right)= \sum_{i=0}^N\left(x_i\ln f\left( \textbf{A} ,\textbf{T}_i \right)\right)+ (1-x_i)\ln\left(1-f\left( \textbf{A} ,\textbf{T}_i \right)\right). \] Остается найти производную, приравнять нулю и найти решение полученной задачи \[ \frac{\partial}{\partial a_j}\ell(\textbf{A})= \left( x\frac{1}{g\left( \textbf{A}^T \textbf{T} \right)}-(1-x)\frac{1}{1-g\left( \textbf{A}^T \textbf{T} \right)}\right) \frac{\partial}{\partial a_j}g\left( \textbf{A}^T \textbf{T} \right)= g\left( \textbf{A}^T \textbf{T} \right)\left(1-g\left( \textbf{A}^T \textbf{T} \right)\right) \frac{\partial}{\partial a_j}\textbf{A}^T \textbf{T}= \] \[ =\left( x\left(1-g\left( \textbf{A}^T \textbf{T} \right)\right)-(1-x)g\left( \textbf{A}^T \textbf{T} \right)\right)\textbf{T}_j =\left( x-g\left( \textbf{A}^T \textbf{T} \right)\right)\textbf{T}_j. \] Замечая, что \(g'(z)=g(z)(1-g(z))\), приходим к задаче стохастического градиентного спуска \(a:=a+\alpha\nabla_a\ell(\textbf{A})\), и при этом, \[ a_j:=a_j+\alpha\left( x-g\left( \textbf{A}^T \textbf{T} \right)\right)\textbf{T}_j \] и \[ \nabla_a\ell(\textbf{A})=\sum_{i=0}^N\left( x_i-g\left( \textbf{A}^T \textbf{T}_{i} \right)\right)\textbf{T}_{i}. \]

Вернемся к определению логистической регрессии с вероятностной точки зрения.

Логистическая регрессия, как и линейная регрессия, относится к обобщенным линейным моделям (generalized linear models), что может быть записано в виде \[ x_i|\textbf{T}_i: \textbf{A}\sim \mathcal{N}(\textbf{T}_i\textbf{A},\sigma^2). \] или, что то же самое, \[ \textbf{T}_i: \textbf{A}\sim \mathcal{N}(a_0+a_1t_{i,1}+...a_nt_{i,n},\sigma^2). \] Отсюда имеем \[ \textbf{X}= a_0\textbf{T}^T_{0}+a_1\textbf{T}^T_{1}+...a_n\textbf{T}^T_{n}+\textbf{E}, \textbf{E}\sim \mathcal{N}(0,\sigma^2), \textbf{T}^T_0=\left( \begin{array}{c} 1 \\ 1 \\ 1 \\ \vdots \\ 1 \\ \end{array} \right), \textbf{T}^T_1=\left( \begin{array}{c} t_{0,1} \\ t_{1,1} \\ t_{2,1} \\ \vdots \\ t_{N,1} \\ \end{array} \right), ..., \textbf{T}^T_n=\left( \begin{array}{c} t_{0,n} \\ t_{1,n} \\ t_{2,n} \\ \vdots \\ t_{N,n} \\ \end{array} \right). \] Логистическую регрессию определим следующим образом \[ \ln\left(\frac{p(\textbf{t})}{1-p(\textbf{t})}\right)=a_0\textbf{T}^T_{0}+a_1\textbf{T}^T_{1}+...a_n\textbf{T}^T_{n}. \] В случае использования двух исходов - положительного \(x_i=1\) и отрицательного \(x_i=0\) \[ \frac{p(\textbf{t})}{1-p(\textbf{t})}= \frac{P[\textbf{X}=1|\textbf{T}=\textbf{t}]}{1-P[\textbf{X}=0|\textbf{T}=\textbf{t}]}. \] Логистическая регрессия гарантирует вычисление значения между 0 и 1: \[ p(\textbf{T}^T_{i})=[x_i=1|\textbf{T}_i=\textbf{t}_i]=\frac{\exp\left(a_0\textbf{T}^T_{0}+a_1\textbf{T}^T_{1}+...a_n\textbf{T}^T_{n}\right)} {1+\exp\left(a_0\textbf{T}^T_{0}+a_1\textbf{T}^T_{1}+...a_n\textbf{T}^T_{n}\right)}. \] Приведем сравнение линейной и логистической регрессии
Линейная регрессия Логистическая регрессия
Закон распределения \(\textbf{Y}|\textbf{X}=\textbf{x}\) \(\mathcal{N}(\mu(\textbf{x}),\sigma^2)\) \(\textbf{Bern}(p(\textbf{x}))\)
Название закона распределения НормальныйБернулли (биномиальный)
\(E[\textbf{Y}|\textbf{X}=\textbf{x}]\) \(\mu(\textbf{x})\) \(p(\textbf{x})\)
Принимаемые значение \((-\infty,\infty)\) \(0,1\)
Использование Числовые данные Бинарные данные (класс: Да/Нет)
Связь \(\eta(\textbf{x})=\mu(\textbf{x})\) \(\eta(\textbf{x})=\ln\left(\frac{p(\textbf{x})}{1-p(\textbf{x})}\right)\)
Значение \(\mu(\textbf{x})=\eta(\textbf{x})\) \(p(\textbf{x})=\frac{\exp\left(\eta(\textbf{x})\right)}{1+\exp\left(\eta(\textbf{x})\right)}= \frac{1}{1+\exp\left(-\eta(\textbf{x})\right)}\)

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

Таким образом, качество классификатора существенно зависит от выбора порога. Далее поговорим о том как выбирать порог.

ROC-кривые и их анализ.

Эта часть написана по данным мотивам.
ROC означает Receiver Operating Characteristic (от Signal Detection Theory)-рабочая (эксплуатационная) характеристика приемника.
Кривые ROC часто используются для графического отображения связи / компромисса между клинической чувствительностью и специфичностью для каждого возможного отсечения для теста или комбинации тестов.
Площадь под ROC-кривой является мерой полезности классификатора в целом, при этом большая площадь означает более эффективный классификатор, поэтому области под ROC-кривыми используются для сравнения качества классификаторов.
ROC-кривые впервые были применены после японского нападения на Перл-Харбор в 1941 году, с целью изучения качества систем распознавания радиосигналов при наличии шума. Первоначальное исследование было мотивировано желанием определить, как американские операторы радиолокационных станций пропустили японские самолеты. Первоначально ROC-кривые использовались для отделения сигнала от шума, чем и обусловлено их использование как двоичных классификаторов.
ROC-кривые строятся путем использования доли принадлежности к одному и другому классам - True Positives и False Positives.


Отложим на оси абсцисс значение FPR, а по оси ординат TPR. Ясно, что диагональ, идущая от начала координат соответствует классификатору со случайным выбором класса.


ROC-кривая для случайного классификатора, с предсказанием попадания
в класс 0 (с точностью 100%), в класс 1 (с точностью 100%) и в класс 1 (с точностью 80%).

Пусть имеется пять наблюдений классификатора \(C_i, i=1,..,5.\)


Построение ROC-кривой для наблюдений классификатора \(C_i, i=1,..,5\).


Выпуклая оболочка наблюдений классификатора \(C_i, i=1,..,5\) и тривиальных набюлюдений (вершины квадрата).

Точки, лежащие ниже выпуклой оболочки (внутри ее подграфа) являются субоптимальными, то есть, соответствуют заведомо худшим классификаторам. В данном случае это \(C_3\).
Существует достаточно простая связь между введенными ранее характеристиками классификатора. \[ TPR=\frac{ACC-neg}{pos}+\frac{neg}{pos}FPR, \] где \(neg=\frac{NEG}{N}\), \(pos=\frac{POS}{N}\), здесь \(NEG\) количество отрицательных результатов, \(POS\) количество положительных результатов и \(N\)- общее количество наблюдений.
Это соотношение получается из цепочки равенств \[ ACC=\frac{TP+TN}{N}=\frac{TP}{N}+\frac{TN}{N}=\frac{TP}{POS}\frac{POS}{N}+\frac{NEG-FP}{N}= \frac{TP}{POS}\frac{POS}{N}+\frac{TP}{POS}\frac{POS}{N}+\frac{NEG-TN}{N}=\frac{TP}{POS}\frac{POS}{N}+\frac{NEG}{N}-\frac{FP}{NEG}\frac{NEG}{N}= TRP\cdot pos+neg\cdot FPR. \]
Замечая, что \(TPR\) это ось \(0y\), а \(FPR\) ось \(0x\), получаем \[ y=ax+b, y=TPR, x=FPR, a=\frac{neg}{pos}, b=\frac{ACC-neg}{pos}. \] Отношение neg / pos - это наклон линии, меняя это соотношение и меняя точность, можем получить много параллельных линий с одинаковым наклоном. Более высокие линии соответствуют лучшей точности классификатора. Ясно, что соотношение neg / pos представляет собой приемлимое отношение неправильно и правильно классифицированных наблюдений. Точность классификации определяется пересечением соответствующей линии и второй диагональю (на картинке - это линия синего цвета).
neg/pos=1neg/pos=0.5
Приведем иллюстрацию нахождения оптимального классификатора для рассмотренного примера при разных отношениях neg / pos.
neg/pos=1/1neg/pos=1/4neg/pos=4/1
Наилучший классификатор \(C_2\)Наилучший классификатор \(C_4\)Наилучший классификатор \(C_1\)
Точность \(\approx 81\%\)Точность \(\approx 83\%\)Точность \(\approx 82\%\)

Пример.


Построение ROC-кривой.


Использование ROC-кривой для нахождения лучшего классификатора для отношения neg/pos=1/1.


Площадь подграфика ROC-кривой.
Чем больше площаль, тем лучше метод классикации.


Примеры ROC-кривых для разных классификаторов.

Задачи для самостоятельной работы.

Полезная литература. Книги.

  1. Bjorck A. Numerical Methods For Least Squares Problems / A.Bjorck .— Philadelphia: SIAM, 1996 .— 427 p.
  2. Cheung K.W. Least Squares Algorithms for Time-of-Arrival-Based Mobile Location / K.W.Cheung, H.So, Y.Chan // IEEE Transactions on Signal Processing .— 2004 .— №4(52) .— P.1121-1128.
  3. Hosmer D.W. Applied Logistic Regression / D.W. Hosmer, S. Lemeshow. — Hoboken: John Wiley & Sons, Inc, 2000. — 397 p.
  4. Rawlings J. Applied regression analysis: a research tool. — 2nd ed. / John O. Rawlings, Sastry G. Pentula, David A. Dickey: Springer, 1998 .— 659 с.
  5. Schleicher C. Kolmogorov-Wiener Filters for Finite Time-Series / Christoph Schleicher. — 2003. — 48 p.
  6. Vaseghi S. Advanced Digital Signal Processing and Noise Reduction / Saeed V. Vaseghi. — Chichester: John Wiley & Sons, Inc., 2006. — 480 p.
  7. Weisberg S. Applied Linear Regression / S. Weisberg. — Hoboken, New Jersey: John Wiley & Sons, Inc., 2005. — 325 p.
  8. Вапник В.Н. Восстановление зависимостей по эмпирическим данным / В.Н.Вапник .— М: Наука, 1979 .— 448 с.
  9. Воронцов К.В. Математические методы обучения по прецедентам (теория обучения машин).— 141 с.
  10. Губанов В.С. Обобщенный метод наименьших квадратов. Теория и применение в астрометрии / В.С.Губанов .— СПб: Наука, 1997 .— 318 с.
  11. Дрейпер Н. Прикладной регрессионный анализ / Н.Дрейпер, Г.Смит; Книга 1 .— М.: Финансы и статистика, 1986 .— 369 с.
  12. Дрейпер Н. Прикладной регрессионный анализ / Н.Дрейпер, Г.Смит; Книга 2 .— М.: Финансы и статистика, 1986 .— 369 с.
  13. Колос М.В. Методы оптимальной фильтрации / М.В.Колос, И.В.Колос .— М: Изд-во МГУ, 2000 .— 102 с.
  14. Методы цифровой обработки сигналов для решения прикладных задач. / Под ред. В.И.Марчука .— М.: Радиотехника, 2012 .— 128 с.
  15. Лигун А.А. Асимптотические методы восстановления кривых / А.А.Лигун, А.А.Шумейко .— К.: Изд. Института математики НАН Украины, 1997 .— 358 с.
  16. Линник Ю.В. Метод наименьших квадратов и основы математико-статистической теории обработки наблюдений / Ю.В.Линник .— М: Наука, 1962 .— 349 с.
  17. Лоусон Ч. Численное решение задач метода наименьших квадратов / Ч.Лоусон, Р.Хенсон .— М: Наука, 1986 .— 232 с.
  18. Любимцев О.В. Линейные регрессионные модели в эконометрике / О.В.Любимцев, О.Л.Любимцева; Учебное пособие .— Нижний Новгород: ННГАСУ, 2016 .— 45 с.
  19. Мазмишвили А.И. Теория ошибок и метод наименьших квадратов / А.И.Мазмишвили .— М.: Недра, 1978 .— 311 с.
  20. Носко В.П. Эконометрика. Введение в регрессионный анализ временных рядов. / В.П.Носко .— М, 2002 .— 254 с.
  21. Себер Д. Линейный регрессионный анализ / Д. Себер. — М: Мир, 1980. — 456 с.
  22. Стрижов В.В. Методы выбора регрессионных моделей / В.В.Стрижов, Е.А.Крымова .— М: Вычислительный центр РАН, 2010 .— 60 с.
  23. Ферстер Э. Методы корреляционного и регрессионного анализа / Э.Ферстер, Б.Ренц .— М.: Статистика и финансы, 1983 .— 302 с.
  24. Шашков В.Б. Прикладной регрессионный анализ. Многофакторная регрессия. / В.Б.Шашков; Учебное пособие .— Оренбург: ГОУ ВПО ОГУ, 2003 .— 363 с.
  25. Шумейко А.А., Сотник С.Л. Интеллектуальный анализ данных (Введение в Data Mining).-Днепропетровск:Белая Е.А., 2012.- 212 с.

Полезная литература. Статьи.

  1. Angrist J. Two-Stage Least Squares Estimation of Average Causal Effects in Models With Variable Treatment Intensity./ Joshua D. Angrist, Guido W. Imbens // Journalofthe American Statistical Association. — 1995. — №430(90). — P.431–442.
  2. Cantrell C. A. Technical Note: Review of methods for linear least-squares fitting of data and application to atmospheric chemistry problems./ C. A. Cantrell // Atmos. Chem. Phys. — 2008. — №8. — P.5477–5487.
  3. Golub G.H. Numerical methods for solving linear least squares problems. / G.H.Golub // Aplikace matematiky. — 1965. — Vol. 10, No. 3. — P.213-216.
  4. Fawcett T. An introduction to ROC analysis. / Tom Fawcett // Pattern Recognition Letters. — 2006. — № 27. — P.861-874.
  5. Smyth G. Nonlinear regression / G.Smyth // Encyclopedia of Environmetrics: John Wiley & Sons, Ltd, Chichester .— 2002 .— Vol.3 .— P.1405–1411.
  6. Sorenson H.W. Least-squares estimation: from Gauss to Kalman. / H. W. Sorenson // IEEE spectrum. — 1970. — july. — P.63-68.
  7. Yuan J. Numerical methods for generalized least squares problems./ Jin Yun Yuan // Journal of Computational and Applied Mathematics. — 1996. — 66. — P.571-584.
  8. Андреев В.А. Универсальные многофакторные регрессионные модели коммерческой результативности инноваций в России./ В.А.Андреев, Д.А.Чупикин // Труды ИСА РАН. — 2011. — №1, Том 61. — С.66-76
  9. Кисин Ю.К. О применении алгоритмов на основе метода наименьших квадратов и конечных формул в задачах траекторных измерений / Ю.К.Кисин // Вестник Концерна ВКО "Алмаз-Антей" .— 2016 .— №3 .— C.74-80.
  10. Лапин А.П. Применение взвешенного метода наименьших квадратов при исследовании функции преобразования вихреакустических расходомеров / А.П.Лапин, А.Дружков // Вестник ЮУрГУ. Серия «Компьютерные технологии, управление, радиоэлектроника» .— 2013 .— №3(13) .— C.109-113.
  11. Логистическая регрессия и ROC-анализ — математический аппарат.
  12. Мазуров Б.Т. Метод наименьших квадратов (статика, динамика, модели с уточняемой структурой) / Б.Т.Мазуров, В.А.Падве // Вестник СГУГиТ .— 2017 .— №2(22) .— C.22-35.
  13. Шумейко А.А. О построении асимптотически оптимальной кусочно-линейной регрессии. / А.А. Шумейко, Е.А. Шумейко // Інформатика та математичні методи в моделюванні. — 2011. — № 2 (1). — C.99-106.

Вопрос-ответ.

Задать вопрос: