МНК

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

А чтобы не "вертеть в голове индексы", советовал бы разобраться с матричной записью. Затраты труда, чтобы освоить её, окупятся очень быстро. Вплоть до того, что некоторые вещи, долго выписываемые в индексной записи, получаются в одну строчку.

[rlsp]

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

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

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

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

Если честно, то абстракция на абстракции, вот смотрю я на $a_{ij}$ и приходится листать выше по тексту чтобы раскрыть эти обозначения до исходной $g_j(x_i)$ и придать какой-то смысл этому. Но если не требуется в голове всё это держать, то в целом вся цепочка мне пока понятна.

[ИСН]

Вся математика - это абстракция на абстракции.

[rlsp]

ИСН в сообщении #995910 писал(а):

Вся математика - это абстракция на абстракции.

ну в программировании тоже самое, за исключением того, что абстракциям дают понятные обозначения - типа "threshold-set" или "wtf-collection"

[svv]

rlsp
Сейчас я повторю конец того сообщения, где была получена система, но добавлю к каждой формуле матричную запись. Проиллюстрирую то, что сказал Евгений Машеров.
$\bullet$ Пожалуйста, не читайте это сообщение, пока не проработаете предыдущие.
$\bullet$ Понимание матричной записи и того, как она получается из индексной, сейчас не требуется.

Изменим порядок суммирования в левой части:
$\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 \quad\quad A^\top Ac=A^\top y$
Если ввести обозначения
$p_{jk}=\sum\limits_{i=1}^n a_{ij} a_{ik}\quad\quad P=A^\top A$
$q_j=\sum\limits_{i=1}^n a_{ij}y_i\quad\quad q=A^\top y$
(это всё известные величины), получим окончательную систему уравнений
$\sum\limits_{k=1}^m p_{jk}c_k=q_j\quad\quad Pc=q$

Далее в матричных обозначениях:
$c=P^{-1}q$
$c=(A^\top A)^{-1}A^\top y$

[ewert]

Ну здесь-то как раз никаких абстракций и нет, честно выписываем сумму квадратов и тупо её дифференцируем, всё чиста канкретна. Другое дело, что это несколько занудно и, кроме того, не годится для комплекснозначных функций (а они вполне бывают нужны). Если же не хочется возиться с техническими деталями, то нужно как раз абстрактнее к этому делу и подойти. Нужно интерпретировать задачу как поиск псевдорешения переопределённой системы линейных уравнений: $\sum\limits_kg_k(x_i)c_k=y_i\ (\forall i)\ \Leftrightarrow\ A\vec c=\vec y$, т.е. поиск столбца $\vec c$, минимизирующего квадрат нормы $\|A\vec c-\vec y\|^2$. Столбец с номером $k$ матрицы $A$ -- это набор $\vec g_k$ значений базисной функции $g_k$ во всех узлах $x_i$. Согласно некоторой линейноалгебраической теореме (довольно простой), такая минимизация эквивалентна решению системы $P\vec c=\vec b$, где $P$ -- это матрица Грама для столбцов матрицы $A$, т.е. составлена из всевозможных скалярных произведений этих столбцов: $p_{kl}=(\vec g_l,\vec g_k)$; соответственно, $b_k=(\vec y,\vec g_k)\ (\forall k)$. Остаётся лишь расшифровать скалярные произведения, вот и всё.

[rlsp]

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

rlsp
Сейчас я повторю конец того сообщения, где была получена система, но добавлю к каждой формуле матричную запись. Проиллюстрирую то, что сказал Евгений Машеров.
$\bullet$ Пожалуйста, не читайте это сообщение, пока не проработаете предыдущие.
$\bullet$ Понимание матричной записи и того, как она получается из индексной, сейчас не требуется.

Изменим порядок суммирования в левой части:
$\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 \quad\quad A^\top Ac=A^\top y$
Если ввести обозначения
$p_{jk}=\sum\limits_{i=1}^n a_{ij} a_{ik}\quad\quad P=A^\top A$
$q_j=\sum\limits_{i=1}^n a_{ij}y_i\quad\quad q=A^\top y$
(это всё известные величины), получим окончательную систему уравнений
$\sum\limits_{k=1}^m p_{jk}c_k=q_j\quad\quad Pc=q$

Далее в матричных обозначениях:
$c=P^{-1}q$
$c=(A^\top A)^{-1}A^\top y$

Цитата:

Понимание матричной записи и того, как она получается из индексной, сейчас не требуется.

Тогда мне не понятна та часть Вашего сообщения, где используются матрицы.

-- 26.03.2015, 15:33 --

ewert в сообщении #995917 писал(а):

вот и всё.

если бы я попросил меня запутать, я бы не мог надеяться на более удачную попытку

[svv]

Это сообщение, в которое добавлена матричная запись, — на будущее.
(Подобно тому как словарь покупают перед изучением нового языка.)

[ewert]

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

если бы я попросил меня запутать, я бы не мог надеяться на более удачную попытку

Я в некотором смысле именно это и пытался сделать. Т.е. я хотел показать, что для сознательного отношения к задаче нужно знать линейную алгебру, тогда всё очень просто. Если же знать лень, то ничего не поделаешь -- придётся возиться с индексами.

[rlsp]

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

Это сообщение, в которое добавлена матричная запись, — на будущее.
(Подобно тому как словарь покупают перед изучением нового языка.)

сейчас то что делать

-- 26.03.2015, 15:54 --

ewert в сообщении #995930 писал(а):

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

если бы я попросил меня запутать, я бы не мог надеяться на более удачную попытку

Я в некотором смысле именно это и пытался сделать. Т.е. я хотел показать, что для сознательного отношения к задаче нужно знать линейную алгебру, тогда всё очень просто. Если же знать лень, то ничего не поделаешь -- придётся возиться с индексами.

Да блин, неужели не понятно - одно делать умножать матрицы, двигать столбцы и другое понимать зачем это делается. Ну вот дали Вам формулу

$$\beta^* = (X^T X)^{-1}X^Ty$$

и что дальше, откуда понимание процесса возникнет? Откуда транспонированная матрица взялась? Сейчас, благодаря svv, я пришёл к системе уравнений. И вот на данном этапе переход к матрицам уже понятен - для решения системы.

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

Ну, давайте с самого начала запишем задачу, используя матрицы.
$y=Xa+\varepsilon$
Это даёт небольшую экономию букв, но требуется тоже небольшое напряжение, чтобы вспомнить, как матрицы умножаются (и что столбец можно считать матрицей nх1)
Теперь выразим вектор невязок
$\varepsilon=y-Xa$
Опять вспоминаем, как умножаются матрицы, и догадываемся, что при умножении столбца на себя же, но транспонированного, получим сумму квадратов его элементов (Ой! А не это ли мы ищем?)
$S=\varepsilon^T\varepsilon=(y-Xa)^T(y-Xa)$
Оказывается, что по матричной переменной можно дифференцировать так же, как по обычной числовой (соблюдая правила, в частности, помня, что матрицы некоммутативны, вообще говоря).
Дифференцируя по очень похожим на привычные правилам и приравнивая производные нулю, получим:
$X^T(y-Xa)=0$
$X^TXa=X^Ty$
$a=(X^TX)^{-1}X^Ty$

[ewert]

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

Откуда транспонированная матрица взялась?

Ниоткуда, если не знать линейной алгебры. А если знать, то возьмётся практически вынужденно. Требование $\|A\vec c-\vec y\|=\min$ по теореме о проекции означает, что $A\vec c$ -- это ортогональная проекция вектора $\vec y$ на образ матрицы $A$, т.е. $A\vec c-\vec y\perp A\vec u\ (\forall\vec u)$, т.е. $(A\vec c-\vec y,A\vec u)=0\ (\forall\vec u)$, т.е. $(A^T(A\vec c-\vec y),\vec u)=0\ (\forall\vec u)$, т.е. $A^T(A\vec c-\vec y)=\vec0$, т.е. $A^TA\vec c=A^T\vec y$. Причём в комплексном случае -- ровно так же, только $A^T$ надо, естественно, заменить на $A^*$.

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

Теперь самое время вспомнить, что мы ищем оценку, а не точное значение (ну то есть нам нужно точное значение, но, как говаривал по аналогичному поводу Ленин - "Мы не утописты"

(Оффтоп)

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

)
И для оценки введём обозначение, чтобы отличать от точного значения, "шапочку" пририсуем $\hat{a}$
То есть на самом деле
$\hat{a}=(X^TX)^{-1}X^Ty=(X^TX)^{-1}X^T(Xa+\varepsilon)=(X^TX)^{-1}X^TXa+(X^TX)^{-1}\varepsilon=a+(X^TX)^{-1}\varepsilon$
И вот тут уже мы получили, почти даром, не только оценку, но и её свойства.
Скажем, эпсилон обычно принимают случайной величиной с нулевым матожиданием. Если так - то матожидание оценки коэффициентов равно истинному значению, т.е. наша оценка несмещённая. И дисперсию оценки получить оказывается очень просто. И с распределением понятно, если известно распределение эпсилонов (нормальное? Ну так их комбинация будет также нормально распределена). И ясно, когда у нас ничего не получится - если матрица $X^TX$ не обращаема, определитель у нея нулевой, или, скажем иначе, есть собственные значения нулевые. И даже можно получить оценку вычислительных погрешностей, а они иногда играют тут неожиданно резко.
И становится ясно, как влияет вектор $\varepsilon$. Собственно, страшные слова "пространство столбцов матрицы Х" становятся ясны, это просто все мыслимые линейные комбинации столбцов. У нас вектор $\varepsilon$ лежит, вообще говоря, вне этого пространства, и его можно представить суммой вектора в этом пространстве и вектора, ортогонального этому пространству. Часть, которая ортогональна - на оценку не влияет, мы от неё избавились. Часть вектора $\varepsilon$, оказавшаяся в пространстве столбцов Х - искажает нашу оценку, делает её не равной истинному значению.

[ewert]

(Оффтоп)

Евгений Машеров в сообщении #995956 писал(а):

потом пропагандисты из этого сделали "Каждая кухарка может управлять государством",

это уже в конце 80-х, причём совсем другие пропагандисты. До тех времён пропагандисты были довольно-таки аккуратными.

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

(Оффтоп)

Да пожалуй, что те же пропагандисты, только иначе мотивированные. "Настоящий знаменосец не отвлекается при смене цвета знамени!"