Статьи

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

0 261

Существенный класс моделей в анализе данных составляют т.н. регрессионные модели. В результате выборки из набора данных или последовательных измерений мы получаем значения целевой величины в зависимости от некоторого набора входных параметров. Регрессионная модель представляет собой аналитическую зависимость целевой величины от входных параметров, максимально «хорошо» описывающая полученную выборку. Эта выборка еще называется обучающей, а процесс получения конкретного вида модели — обучением с учителем. Метод наименьших квадратов (далее — МНК) является, пожалуй, самым распространенным способом решения регрессионной задачи. В данном посте рассмотрим предпосылки и основные принципы этого метода.

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

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

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

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

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

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

Обычно под линейной регрессией понимают зависимость вида:

\begin{equation}\label{eq:lin_regr}
y(\mathbf{x}, \mathbf{w})=w_0+w_1 x_1+\ldots+w_{M-1} x_{M-1}
\end{equation}

Линейная зависимость от вектора x входных параметров накладывает серьезные ограничения на условия задачи, поэтому линейная регрессионная модель рассматривается в более общем виде:
\begin{equation}\label{eq:lin_regr_comm}
y(\mathbf{x}, \mathbf{w})=w_0+\sum\limits_{i=1}^{M-1}w_i \phi_i(\mathbf{x})
\end{equation}

Функции $\phi_i (x)$ называются базисными. Конкретный их вид нас пока не интересует. Можно отметить, что в качестве базисных функций часто используют ф-ю Гаусса, но выбор обычно диктуется спецификой задачи.

Для удобства записи можно ввести фиктивную ф-ю $\phi_0=1$, и тогда \eqref{eq:lin_regr_comm} можно записать в виде одной суммы:

\begin{equation}\label{eq:lin_regr_comm_ext}
y(\mathbf{x},\mathbf{w})=\sum\limits_{i=0}^{M-1}w_i \phi_i(x)
\end{equation}

Количество параметров модели, как видим, равно M. Параметры модели образуют вектор $w=[w_0, w_1,\ldots,w_{M-1}]^T$ ($T$ в качестве верхнего индексаобозначает транспонирование). Модель называется линейной, потому что искомая зависимость является линейной относительно параметров $w_i$. При этом, зависимость от $\mathbf{x}$, как правило, уже не будет линейной.

Представим, что задача уже решена и нам известна зависимость $y(\mathbf{x}, \mathbf{w})$. Целевую величину $t$ можно тогда представить в виде:
\begin{equation}
t=y(\mathbf{x}, \mathbf{w})+\epsilon
\end{equation}

где $\epsilon$ это некоторое случайное отклонение целевой величины от модели. Предположим, что плотность распределения вероятности отклонения $\epsilon$ дается гауссовым распределением с нулевым средним и дисперсией $\sigma$:

\begin{equation}
p(\epsilon)=\frac1{\sqrt{2\pi\sigma}} \exp\left(-\frac{\epsilon^2}{\sigma^2}\right)
\end{equation}

Для плотности распределения вероятности величины $t$ мы тогда можем записать:

\begin{equation}\label{eq:otkl_distr}
p(t|\mathbf{x},\mathbf{w},\sigma) = \frac1{\sqrt{2\pi\sigma}}\exp\lbrace -\frac{(t-y(\mathbf{x},\mathbf{w}))^2}{\sigma^2} \rbrace
\end{equation}

Это означает, что целевая величина распределена по нормальному закону с мат. ожиданием $y(\mathbf{x},\mathbf{w})$ и дисперсией $\sigma$.

Рассмотрим теперь набор данных из N элементов, такой что $\mathbf{X}=\{\mathbf{x_1},\mathbf{x_2},\ldots,\mathbf{x_N}\}$ – входные параметры, $\mathbf{t}=\{\mathbf{t_1},\mathbf{t_2},\ldots,\mathbf{t_N}\}$ – соответствующие им значения целевой величины. Тогда плотность распределения вероятности того, что мы получим набор значений t при параметрах модели w, будет:
\begin{equation}\label{eq:likelihood}
p(\mathbf{t}|\mathbf{X},\mathbf{w},\sigma)=\prod_{n=1}^N p(t_n|\mathbf{X},\mathbf{w},\sigma)=\prod_{n=1}^N\frac1{\sqrt{2\pi\sigma}}\exp\lbrace -\frac{(t-y(\mathbf{x},\mathbf{w}))^2}{\sigma^2} \rbrace
\end{equation}

Здесь мы использовали определение \eqref{eq:lin_regr_comm} и ввели вектор $\phi(\mathbf(x)_n)=\lbrack \phi_1(\mathbf{x}_n),\phi_2 (\mathbf{x}_n),\ldots,\phi_{M-1}(\mathbf{x}_n)\rbrack^T$
При обучении с учителем, нас интересует не величина \eqref{eq:otkl_distr}, вероятность встретить определенный набор параметров, т.е. $p(\mathbf{w}│\mathbf{X},\mathbf{t},σ)$. Чтобы получить эту вероятность, воспользуемся теоремой Байеса:
\begin{equation}\label{eq:bayes_th}
p(\mathbf{w}│\mathbf{X},\mathbf{t}, \sigma)=\frac{p(\mathbf{t}│\mathbf{X},\mathbf{w},\sigma)p(\mathbf{w}|a,b))}{(p(\mathbf{t}|\mathbf{X},\sigma)}
\end{equation}

Формула \eqref{eq:bayes_th} дает апостериорную вероятность получить набор параметров w после получения набора значений целевой величины. Параметры a,b называются гиперпараметрами и отвечают за конкретный вид плотности распределения по $\mathbf{w}$. Знаменатель правой части \eqref{eq:bayes_th} служит коэффициентом нормализации, так чтобы результат интегрирования по по $\mathbf{w}$ был равен единице.

Величина $p(\mathbf{t}│\mathbf{X},\mathbf{w},\sigma)$ в литературе по статистике имеет специальное название – likelihood. Она дает степень вероятности встретить набор $\mathbf{t}$ при параметрах $\mathbf{w}$. Поскольку эта величина единственная, которая влияет на p(\mathbf{t}│\mathbf{X},\mathbf{w},\sigma), то, найдя ее максимум по $\mathbf{w}$, мы найдем и значение $\mathbf{w}_{max}$,при котором $p(\mathbf{t}│\mathbf{X},\mathbf{w},\sigma)$ имеет максимальное значение.

Для удобства, вместо максимума $p(\mathbf{t}│\mathbf{X},\mathbf{w},\sigma)$ будем искать максимум ее логарифма, т.е. решать уравнение:
\begin{equation}\label{eq:extr_ml}
\frac{d\quad ln\quad p(t│X,w,σ)}{dw}=0
\end{equation}

Подставим \eqref{eq:otkl_distr} в \eqref{eq:extr_ml}, получаем:

\begin{equation}\label{eq:extr_ml2}
\frac{d}{dw}\left(-\frac{N}{2} ln\sigma — \frac{N}{2}ln2\pi + \sigma E(\mathbf{w})\right)=0
\end{equation}

где ф-я ошибок E определяется следующим образом:
\begin{equation}\label{eq:error_fun}
E(\mathbf{w})=\frac1{2} \sum_{n=1}^N(t_n-\mathbf{w}^T \mathbf{\phi}(\mathbf{x}_n))^2
\end{equation}

Итак, решая \eqref{eq:extr_ml}, получаем:
\begin{equation}\label{eq:error_fun_exp}
E(\mathbf{w})=\sum_{n=1}^N t_n \phi(\mathbf{x}_n)^T-\mathbf{w}^T \left(\sum_{n=1}^N \mathbf{\phi}(\mathbf{x}_n) \mathbf{\phi}(\mathbf{x}_n)^T \right)
\end{equation}

откуда:
\begin{equation}\label{eq:w_max}
\mathbf{w}_{max}=(\mathbf{\Phi}^T \mathbf{\Phi})^{-1} \mathbf{\Phi}^T \mathbf{t}
\end{equation}

Здесь введено обозначение:
\begin{equation}\label{eq:mat_phi}
\mathbf{\Phi}=\begin{pmatrix}
\phi_0(\mathbf{x}_1) & \ldots & \phi_{M-1}(\mathbf{x}_1) \\
\vdots & \ddots & \vdots \\
\phi_0(\mathbf{x}_N) & \ldots & \phi_{M-1}(\mathbf{x}_N)
\end{pmatrix}
\end{equation}

Строки матрицы \eqref{eq:mat_phi} являются векторами с компонентами из базисных ф-й модели \eqref{eq:lin_regr_comm_ext}.

Решение \eqref{eq:mat_phi} и есть решение по методу наименьших квадратов. Матрица
\begin{equation}\label{eq:moor_penf}
\mathbf{\Phi}^{\dagger}=(\mathbf{\Phi}^T \mathbf{\Phi})^{-1} \mathbf{\Phi}^T
\end{equation}

называется псевдообратной матрицей (или матрица Мура-Пенроуза). Легко проверить, что если Φ квадратная и обратимая, то псевдообратная совпадает с обратной матрицей.
Заметьте, что мы пришли к решению \eqref{eq:w_max} из предположения нормально распределенного случайного отклонения измеренной величины от целевой ф-ии. Само решение опиралось на теорему Байеса \eqref{eq:bayes_th} и на нахождение значения параметров $\mathbf{w}_{max}$ , при которых ф-я правдоподобия \eqref{eq:likelihood} имеет максимальное значение. Такой путь решения (максимальное правдоподобие) имеет широкое применение в приложениях анализа данных.

Решение \eqref{eq:w_max} также может быть получено из чисто геометрических соображений и, по сути, представляет собой проектирование вектора целевых значений t на подпространство, образуемое векторами, из которых состоят столбцы матрицы $\mathbf{\Phi}$, но об этом в одном из следующих постов.

Если появились вопросы, то их можно задать в комментариях.

About the author / 

admin