2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: МНК
Сообщение26.03.2015, 13:33 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: МНК
Сообщение26.03.2015, 13:38 


20/01/15
27
svv в сообщении #995902 писал(а):

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

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


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


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

 Профиль  
                  
 
 Re: МНК
Сообщение26.03.2015, 13:40 
Заслуженный участник
Аватара пользователя


18/05/06
13284
с Территории
Вся математика - это абстракция на абстракции.

 Профиль  
                  
 
 Re: МНК
Сообщение26.03.2015, 13:45 


20/01/15
27
ИСН в сообщении #995910 писал(а):
Вся математика - это абстракция на абстракции.

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

 Профиль  
                  
 
 Re: МНК
Сообщение26.03.2015, 13:58 
Заслуженный участник


23/07/08
7870
Харьков
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$

 Профиль  
                  
 
 Re: МНК
Сообщение26.03.2015, 14:16 
Заслуженный участник


11/05/08
31867
Ну здесь-то как раз никаких абстракций и нет, честно выписываем сумму квадратов и тупо её дифференцируем, всё чиста канкретна. Другое дело, что это несколько занудно и, кроме того, не годится для комплекснозначных функций (а они вполне бывают нужны). Если же не хочется возиться с техническими деталями, то нужно как раз абстрактнее к этому делу и подойти. Нужно интерпретировать задачу как поиск псевдорешения переопределённой системы линейных уравнений: $\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)$. Остаётся лишь расшифровать скалярные произведения, вот и всё.

 Профиль  
                  
 
 Re: МНК
Сообщение26.03.2015, 14:30 


20/01/15
27
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 писал(а):
вот и всё.

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

 Профиль  
                  
 
 Re: МНК
Сообщение26.03.2015, 14:33 
Заслуженный участник


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

 Профиль  
                  
 
 Re: МНК
Сообщение26.03.2015, 14:41 
Заслуженный участник


11/05/08
31867
rlsp в сообщении #995924 писал(а):
если бы я попросил меня запутать, я бы не мог надеяться на более удачную попытку :P

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

 Профиль  
                  
 
 Re: МНК
Сообщение26.03.2015, 14:48 


20/01/15
27
svv в сообщении #995926 писал(а):
Это сообщение, в которое добавлена матричная запись, — на будущее.
(Подобно тому как словарь покупают перед изучением нового языка.)

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

-- 26.03.2015, 15:54 --

ewert в сообщении #995930 писал(а):
rlsp в сообщении #995924 писал(а):
если бы я попросил меня запутать, я бы не мог надеяться на более удачную попытку :P

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

Да блин, неужели не понятно - одно делать умножать матрицы, двигать столбцы и другое понимать зачем это делается. Ну вот дали Вам формулу $$\beta^* = (X^T X)^{-1}X^Ty$$ и что дальше, откуда понимание процесса возникнет? Откуда транспонированная матрица взялась? Сейчас, благодаря svv, я пришёл к системе уравнений. И вот на данном этапе переход к матрицам уже понятен - для решения системы.

 Профиль  
                  
 
 Re: МНК
Сообщение26.03.2015, 15:18 
Заслуженный участник
Аватара пользователя


11/03/08
6737
Москва
Ну, давайте с самого начала запишем задачу, используя матрицы.
$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$

 Профиль  
                  
 
 Re: МНК
Сообщение26.03.2015, 15:32 
Заслуженный участник


11/05/08
31867
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^*$.

 Профиль  
                  
 
 Re: МНК
Сообщение26.03.2015, 15:35 
Заслуженный участник
Аватара пользователя


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

(Оффтоп)

Далее он пояснял, что кухарка управлять государством не может, хотя такую глупость враги большевикам и приписывают, управлять должны специалисты, и надо учить молодых рабочих, как те выучатся, так и управлять смогут; потом пропагандисты из этого сделали "Каждая кухарка может управлять государством", впрочем, с "В здоровом теле здоровый дух" и "Истина в вине" те же приключения...
)
И для оценки введём обозначение, чтобы отличать от точного значения, "шапочку" пририсуем $\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$, оказавшаяся в пространстве столбцов Х - искажает нашу оценку, делает её не равной истинному значению.

 Профиль  
                  
 
 Re: МНК
Сообщение26.03.2015, 15:42 
Заслуженный участник


11/05/08
31867

(Оффтоп)

Евгений Машеров в сообщении #995956 писал(а):
потом пропагандисты из этого сделали "Каждая кухарка может управлять государством",

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

 Профиль  
                  
 
 Re: МНК
Сообщение26.03.2015, 16:00 
Заслуженный участник
Аватара пользователя


11/03/08
6737
Москва

(Оффтоп)

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 56 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group