МНК

[svv]

rlsp в сообщении #995508 писал(а):

$f(x)$ - это аппроксимирующая функция, к примеру линейная $kx+b$ или, как в моём случае такая - $\mathbf{B}(t) = (1-t)^3\mathbf{P}_0 + 3t(1-t)^2\mathbf{P}_1 + 3t^2(1-t)\mathbf{P}_2 + t^3\mathbf{P}_3, \quad t \in [0,1]$

У Вас во втором примере векторы. Давайте сначала разберем скалярный случай.
В обоих случаях, $kx+b$ и $B(t)$, я вижу сумму $m$ заданных функций с переменными (неизвестными) коэффициентами.
Давайте унифицируем обозначения. Пусть индекс $k$ обозначает номер заданной функции (и он же — номер коэффициента при ней). Он меняется от $1$ до $m$.
Заданные функции давайте обозначать $g_k(x)$ (соглашусь и на Ваши обозначения).
Коэффициенты при них пусть будут $c_k$.

Тогда $kx+b$ можно записать как $c_1 g_1(x)+c_2 g_2(x)$, где
$c_1=k, \quad g_1(x)=x,
$c_2=b, \quad g_2(x)=1$.
Напишите то же для Вашего примера с кривыми Безье (искусственно придав ему скалярную форму).

[rlsp]

$g_1(t)c_1 + g_2(t)c_2 + g_3(t)c_3 + g_4(t)c_4$

$g_1(t) = (1-t)^3$
$c_1=P_0$

$g_2(t)=t(1-t)^2$
$c_2=3P_1$

$g_3(t)=t^2(1-t)$
$c_3=3P_2$

$g_4(t)=t^3$
$c_4=P_4$

чувствую что-то неправильно?

[svv]

Нет, всё правильно. Очень хорошо.
Для краткости (и общности) введем знак суммы.
Итак, вот к чему мы пришли:
$f(x)=\sum\limits_{k=1}^m c_k g_k(x)$
Согласны? Понятно?

Теперь я хочу понять, чему равна $f(x)$ в $i$-й точке, то есть $f(x_i)$.
Да, это просто вместо $x$ подставить $x_i$.
Но я ещё прошу использовать в записи обозначение $a_{ik}$ для значения $k$-й функции в $i$-й точке:
$a_{ik}=g_k(x_i)$

[rlsp]

svv в сообщении #995555 писал(а):

Нет, всё правильно. Очень хорошо.
Для краткости (и общности) введем знак суммы.
Итак, вот к чему мы пришли:
$f(x)=\sum\limits_{k=1}^m c_k g_k(x)$
Согласны? Понятно?

Теперь я хочу понять, чему равна $f(x)$ в $i$-й точке, то есть $f(x_i)$.
Да, это просто вместо $x$ подставить $x_i$.
Но я ещё прошу использовать в записи обозначение $a_{ik}$ для значения $k$-й функции в $i$-й точке:
$a_{ik}=g_k(x_i)$

Не очень понятно зачем использовать x, ведь это выглядит неоднозначно - как координата. Но ок, сейчас мы имеем $f(x_i)=\sum\limits_{k=1}^m c_k a_{ik}$ что дальше?

[svv]

Просто в формуле $\sum\limits_{}^{}(y-f(x))^2$, которую Вы сначала привели, было $x$.
Конечно, необязательно использовать это обозначение. В Вашем примере с кривой Безье независимая переменная (параметр) была $t$. А теперь, когда ввели обозначение $a_{ik}$, можно и вовсе забыть, как там это обозначалось.

Теперь подставим то, что Вы получили, в формулу для минимизируемого выражения $\sum\limits_{i=1}^{n}(y_i-f(x_i))^2$. Давайте его, кстати, обозначим $F$. Получим
$F=\sum\limits_{i=1}^{n}\left(y_i-\sum\limits_{k=1}^m c_k a_{ik}\right)^2=\sum\limits_{i=1}^{n}\left(\sum\limits_{k=1}^m a_{ik}c_k-y_i\right)^2$

Обратите внимание, что к началу решения задачи $a_{ik}$ либо известны, либо легко вычисляются — это значения заданных функций $g_k$ в известных точках $x_i$. Также известны $y_i$. Все эти значения можно считать константами. А вот $c_k$ переменные, и их надо выбрать так, чтобы $F$ достигала минимума. Таким образом, рассматриваем $F$ как функцию коэффициентов $c_k$:
$F(c_1, ..., c_m)=\sum\limits_{i=1}^{n}\left(\sum\limits_{k=1}^m a_{ik}c_k-y_i\right)^2$
Понятно?

Вы там что-то говорили про производные?

[rlsp]

да, пока понятно. Производные по каждому $c_k$ надо брать? Но пока что это просто огромная сумма.

[svv]

Да. Но внутри сумм индекс $k$ уже используется и пробегает там все значения. Поэтому то конкретное значение индекса, который имеет $c$, по которому берется производная, я бы обозначил $j$.

Подвожу итог: задача нахождения коэффициентов $c$, при которых $F$ достигает минимума, сводится к решению системы уравнений:
$\frac{\partial}{\partial c_j}F(c_1, ..., c_m)=0$, или
$\frac{\partial}{\partial c_j}\sum\limits_{i=1}^{n}\left(\sum\limits_{k=1}^m a_{ik}c_k-y_i\right)^2=0$,
где $j=1,...,m$.
Продолжим после ужина.

[svv]

Но ход Ваш. Попробуйте продифференцировать.

[rlsp]

svv в сообщении #995681 писал(а):

Но ход Ваш. Попробуйте продифференцировать.

$\frac{\partial}{\partial c_1}\sum\limits_{i=1}^{n}\left(\sum\limits_{k=1}^m a_{ik}c_k-y_i\right)^2=$ $\sum\limits_{i=1}^n(R_i^2)'_{c_1}=$ $\sum\limits_{i=1}^n(2R_i(R_i)'_{c_1})=$ $\sum\limits_{i=1}^n(2a_{i1}(\sum\limits_{k=1}^ma_{ik}c_k-y_i))$
Если такой вывод правильный, то для остальных получается то же самое только с $a_{i2} ... a_{ik}$

[svv]

Правильно. Это мы дифференцировали по $c_1$, а если по $c_j$, вместо $a_{i1}$ будет $a_{ij}$. Сокращаем на $2$.
$\sum\limits_{i=1}^n \left(a_{ij}(\sum\limits_{k=1}^m a_{ik}c_k-y_i)\right)=0$

Перенесем слагаемое с $y$ в правую часть:
$\sum\limits_{i=1}^n \left(a_{ij}\sum\limits_{k=1}^m a_{ik}c_k\right)=\sum\limits_{i=1}^n a_{ij}y_i $

Изменим порядок суммирования в левой части:
$\sum\limits_{k=1}^m \left(\left(\sum\limits_{i=1}^n a_{ij} a_{ik}\right)c_k\right)=\sum\limits_{i=1}^n a_{ij}y_i $

Если ввести обозначения
$p_{jk}=\sum\limits_{i=1}^n a_{ij} a_{ik}$,
$q_j=\sum\limits_{i=1}^n a_{ij}y_i$
(это всё известные величины), получим окончательную систему уравнений
$\sum\limits_{k=1}^m p_{jk}c_k=q_j $,
где и $j$ и $k$ пробегают значения от $1$ до $m$.

Всё понятно?

[rlsp]

поздно уже, голова не варит, давайте завтра продолжим

[Евгений Машеров]

(Оффтоп)

Это частная драка, или я могу присоединиться?

Я бы начал с того, why МНК.
Построили мы красивую модель, объясняющую интересную для нас величину y через какие-то известные х-ы. Модель задана с точностью до набора параметров a, который мы желаем оценить по доступным нам данным.
$y=f(X,a)$
Но вот беда - ни при каких a точные значения y не получаются. Мы догадываемся, что дело в погрешностях - измерения ли значений y, влияния неучтённых факторов (из коих одни вовсе не наблюдаемы, а другие, пусть и могут быть наблюдены, но малозначительны, и их влияние существенно потому лишь, что их очень много), или неточности спецификации самой модели. Поэтому модель дополняется поправками, с учётом которых наблюдения согласуются с данными
$y=f(X,a,\varepsilon)$
Если это именно ошибки измерения y, то можно несколько упростить
$y=f(X,a)+\varepsilon$
избавившись от возможно нелинейного влияния $\varepsilon$, причём упрощение столь существенно, что так поступают даже если невязки $\varepsilon$ связаны не только и не столько с ошибками измерения y.

(Оффтоп)

Ищем под фонарём, поскольку не под фонарём ничего не видно.

Понятно, что если мы ничем не ограничены в выборе этих невязок, то можем подогнать всё, что угодно под любую модель. Но так как нам нужна не любая, а реальная зависимость, то мы пытаемся обойтись по возможности меньшими поправками. То есть ищем такие параметры a, чтобы вектор невязок $\varepsilon$ был бы как можно меньше. Однако "меньше" и "больше" применимо к числу, и мы "свёртываем" вектор к одному числу, часто (но не обязательно) норме этого вектора. Выбирая способ "свёртывания" $g=G(\varepsilon)$, можно руководствоваться простыми принципами:
1. Если невязки нулевые - это наилучший возможный результат, то есть $G(0)=0$
2. $G(\varepsilon)$ - монотонная функция от абсолютных величин отдельных элементов вектора невязок.
Даже и при этих условиях (и некоторых дополнительных, скажем, чтобы отрицательные и положительные значения невязок влияли бы одинаково - "ошибки в плюс и в минус равно вредны") остаётся выбор - можно брать максимум абсолютных величин элементов вектора, можно сумму абсолютных значений, можно сумму квадратов. Наиболее часто именно сумма квадратов, оттого и называется МНК. Выбор именно квадратов не всегда наилучший. Скажем, если в данных ожидаются грубые ошибки, то сумма абсолютных величин надёжнее. Оптимальны квадраты, если распределение ошибок нормальное, но главная причина популярности МНК скорее в том, что вычисления упрощаются радикально.
Находя минимум через приравненные к нулю производные по $a_j$ суммы квадратов невязок $\Sigma(y_i-f(X_i,a))^2$, получаем выражение для производных $\Sigma 2(y_i-f(X_i,a)) \frac {\partial f(X_i,a)}{\partial a_j}=0$
А если ещё и $f(X,a)$ есть линейная функция, то нахождение искомых коэффициентов a сводится к решению системы линейных уравнений. Что не только упрощение вычислительной работы, но ещё и гарантия единственности оптимума, в общем случае можем, даже найдя оптимум, оказаться в локальном вместо глобального.
Линейность здесь имеется в виду "по коэффициентам", то есть сами иксы могут быть нелинейными функциями чего-то, это несущественно, важно, чтобы в выражение для y они входили линейно. Модели "истинно линейные" встречаются далеко не всегда, но, с одной стороны, в интересующей нас области может вполне работать линейная аппроксимация, с другой стороны, можно определёнными преобразованиями привести к линейному виду. Так, популярная у экономистов производственная функция Кобба-Дугласа $P=aL^{\alpha}K^{\beta}$, (использование произведения в ней отражает тот факт, что при отсутствии как рабочей силы L, так и капитальных затрат K производство P будет нулевым, даже если второй фактор производства в наличии) после логарифмирования оказывается линейной по параметрам "логарифм от L" и "логарифм от K". Линейная аппроксимация используется также и при оценивании существенно нелинейных моделей, например, методом Левенберга-Марквардта.

[rlsp]

svv в сообщении #995737 писал(а):

Правильно. Это мы дифференцировали по $c_1$, а если по $c_j$, вместо $a_{i1}$ будет $a_{ij}$. Сокращаем на $2$.
$\sum\limits_{i=1}^n \left(a_{ij}(\sum\limits_{k=1}^m a_{ik}c_k-y_i)\right)=0$

Перенесем слагаемое с $y$ в правую часть:
$\sum\limits_{i=1}^n \left(a_{ij}\sum\limits_{k=1}^m a_{ik}c_k\right)=\sum\limits_{i=1}^n a_{ij}y_i $

Изменим порядок суммирования в левой части:
$\sum\limits_{k=1}^m \left(\left(\sum\limits_{i=1}^n a_{ij} a_{ik}\right)c_k\right)=\sum\limits_{i=1}^n a_{ij}y_i $

Если ввести обозначения
$p_{jk}=\sum\limits_{i=1}^n a_{ij} a_{ik}$,
$q_j=\sum\limits_{i=1}^n a_{ij}y_i$
(это всё известные величины), получим окончательную систему уравнений
$\sum\limits_{k=1}^m p_{jk}c_k=q_j $,
где и $j$ и $k$ пробегают значения от $1$ до $m$.

Всё понятно?

Тяжеловато в голове вертеть индексы, поэтому уточню - k - участвует в каждой производной как индекс функции, являющейся частью аппроксимирующей функции. А j - индекс функции, по которой берётся частная производная. То есть, если убрать j и записать непосредственно с числами, то у нас будет система из j уравнений, в каждом из которых k будет пробегать от 1 до m?
$\sum\limits_{k=1}^m p_{jk}c_k=q_j $,
$\left\{ \begin{array}{rcl} \sum\limits_{k=1}^m p_{1k}c_k=q_1 \\ \sum\limits_{k=1}^m p_{2k}c_k=q_2 \\ \sum\limits_{k=1}^m p_{3k}c_k=q_3 \\ \sum\limits_{k=1}^m p_{4k}c_k=q_4 \\ \end{array} \right.$

[svv]

(Евгений Машеров)

Любой участник всегда может присоединиться. Так же, как и я сам это сделал.
Имхо, не должно быть иначе.

rlsp
Да, именно так.
Я подожду, пока Вы ещё раз (или два) всё это просмотрите, привыкнете и скажете, что Вы всё поняли.
Самое трудное позади.

[rlsp]

Да, спасибо за экскурс, теперь я хочу научиться пользоваться этим методом сам, зачем он мне я отлично знаю)