2014 dxdy logo

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

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




 
 Разложить матрицу (МНК)
Сообщение08.12.2007, 12:49 
Пусть есть матрица довольно больших размеров, 500х500 к примеру, структура матрицы - ленточная, ширина ленты около 100. Внутри ленты - положительные числа, выражающие результат эксперимента, вне ленты - нули, которые означают, что эксперимент не производился. Предполагается, что числа внутри ленты "в целом" подчиняются следующему закону: $$A_{ij}  = S_i  \cdot R_j  \cdot X_{\left| {i - j} \right|}  + N_{ij} $$, то есть числа внутри ленты мультипликативно зависят от трех функций - функции номера столбца, номера строки, и "расстояния" между ними, плюс некая "шумовая" часть, не вписывающаяся в мультипликативную модель. Известно, что функции S и R ведут себя непредсказуемо, а X - быстро убывающая с увеличением расстояния.
Нужно найти законы S, R, X. Подскажите, к какому классу задач относится эта, и как ее решать.

Первый шаг сделан такой - зануляем шумовую часть, и, логарифмируя, переходим от произведений к суммам. А дальше?

 
 
 
 
Сообщение09.12.2007, 03:41 
Аватара пользователя
Метод наименьших квадратов. 8-) Должно работать с молодецким посвистом.

 
 
 
 
Сообщение09.12.2007, 09:32 
нг писал(а):
Метод наименьших квадратов. 8-) Должно работать с молодецким посвистом.


не понял. что к чему приближать методом НК? то есть, минимизировать разность между чем и чем? я пока даже не представляю, как начальные приближения для S, R, X получить.

 
 
 
 
Сообщение09.12.2007, 23:54 
Аватара пользователя
Мы имеем семейство $A_{i,j}$, которые мы хотим приравнять к произведению. То есть, минимизировапть $\sum_{i,j}(\ln S_i + \ln R_j + \ln X_{|i-j|} - \ln A_{i, j})^2$. В качестве искомых переменных выступают $\ln S_i$, $\ln R_j$ и $\ln X_{|i-j|}$, каждой по $n$ штук. Размерность, конечно, большая, но матрица имеет удобную структуру.

 
 
 
 
Сообщение10.12.2007, 06:58 
так как мне нужно нечто более, чем уравнение плоскости, приближенно проходящей через все точки, то стало быть МНК у меня выходит нелинейный. в этом я не очень силен. кто-нибудь может на пальцах объяснить, что будет первыми шагами в решении этой задачи минимизации?

 
 
 
 
Сообщение10.12.2007, 09:38 
Аватара пользователя
Логарифмируя обе части, получается линейный МНК. Посмотрите внимательно на формулу, которую привел нг.

 
 
 
 
Сообщение10.12.2007, 19:47 
Аватара пользователя
:evil:
Очевидно, что такое разложение не однозначно, поскольку мы можем всегда умножить все S (или R) на константу, поделив при этом X на константу. То есть, если в лоб, получим сингулярную систему. Поэтому полезно положить $\sum S_i = \sum R_j = 0$. Или $S_1 = R_1 = 1$.

 
 
 
 
Сообщение11.12.2007, 14:57 
так, допустим, мы прологарифмировали входящие в произведение члены. получили сумму логарифмов. теперь минимизируем сумму квадратов разностей. вопрос - как? при минимизации (как я это делаю в экселе) для "наклона" и "засечки" существуют явные формулы. а здесь-то как быть?

да, разложение неоднозначное, по крайней мере с точностью до константы. пусть тогда X(0)=1.

 
 
 
 
Сообщение11.12.2007, 19:33 
Аватара пользователя
похоже, надо разбираться с МНК. Перемещаю в «Помогите…»

 
 
 
 
Сообщение11.12.2007, 22:36 
Аватара пользователя
:evil:
mbaitoff писал(а):
да, разложение неоднозначное, по крайней мере с точностью до константы. пусть тогда X(0)=1.

Это хорошо, но мало. У Вас две лишних степени свободы, Вы зафиксировали пока одну. И я не уверен, что Вы выбрали лучший способ. Мне кажется (с вычислительной точки зрения), суммы удобнее.

mbaitoff писал(а):
вопрос - как?

Как обычно. Берёте производную по переменной и приравниваете её нулю. Ваши переменные — $s_i = \ln S_i$ и т.п. Вот по $s_i$ и дифференцируете.

Почитайте что-нибудь. Гугл в помощь Ваш случай прост до предела — все коэффициенты либо равны 0, либо 1.

И не вспоминайте про Excel. Он — не Богом данная сущность. Так, убыточное изделие редмондского завода ширпотреба от программирования. И в него вбиты те же формулы, что нужны Вам, только в простом варианте.

 
 
 
 
Сообщение12.12.2007, 09:27 
незваный гость писал(а):
:evil:
mbaitoff писал(а):
да, разложение неоднозначное, по крайней мере с точностью до константы. пусть тогда X(0)=1.

Это хорошо, но мало. У Вас две лишних степени свободы, Вы зафиксировали пока одну. И я не уверен, что Вы выбрали лучший способ. Мне кажется (с вычислительной точки зрения), суммы удобнее.


фиксировать суммы непригодно с точки зрения физического смысла проводимых экспериментов. пусть тогда S(1)=R(1)=1.

Цитата:

mbaitoff писал(а):
вопрос - как?

Как обычно. Берёте производную по переменной и приравниваете её нулю. Ваши переменные — $s_i = \ln S_i$ и т.п. Вот по $s_i$ и дифференцируете.

Почитайте что-нибудь. Гугл в помощь Ваш случай прост до предела — все коэффициенты либо равны 0, либо 1.


не согласен. ведь есть же возможность взять произвольные S(i), R(j), X(.) и при этом обратное разложение полученной матрицы А никак не должно давать нули и единицы. к тому же, как использовать факт того, что X(.) - быстро убывающая?

 
 
 
 
Сообщение12.12.2007, 09:48 
Аватара пользователя
:evil:
mbaitoff писал(а):
фиксировать суммы непригодно с точки зрения физического смысла проводимых экспериментов. пусть тогда S(1)=R(1)=1.

Это абсолютно пофигительно. Что Вы не зафиксируете, все результаты получатся пропорциональны.

mbaitoff писал(а):
не согласен.

Вы бы лучше воспользовались советом и почитали бы что-нибудь про МНК. А то Ваши рассуждения непонятно к чему относятся. (Или Вас смущает, что переменные называются $s_i$, а не $x_i$?)

 
 
 
 
Сообщение12.12.2007, 11:57 
хорошо, начинаю минимизировать функцию \[
U = \sum\limits_{ij} {\left( {s_i  + r_i  + x_{ij}  - a_{ij} } \right)} ^2 
\]
дифференцирую по каждому из \[
s_i 
\], получаю
\[
\frac{{\partial U}}
{{\partial s_i }} = 2Ms_i  + 2\sum\limits_{j = 1}^M {\left( {r_j  + x_{ij}  - a_{ij} } \right)} 
\], дифференцирую по каждому из \[
r_j 
\], получаю \[
\frac{{\partial U}}
{{\partial r_j }} = 2Nr_j  + 2\sum\limits_{i = 1}^N {\left( {s_i  + x_{ij}  - a_{ij} } \right)} 
\], дифференцируя по \[
x_{ij} 
\] получаю \[
\frac{{\partial U}}
{{\partial x_{ij} }} = 2MNx_{ij}  + 2\sum\limits_{ij}^{N,M} {\left( {s_i  + r_j  - a_{ij} } \right)} 
\].
если экстремум достигается, тогда все эти производные равны нулю (или многомерном случае это не так выражается?). допустим, приравняв к нулю, я выразил все s_i, r_j, x_{ij}, но что мне это дает? все они по-прежнему зависят друг от друга.

 
 
 
 
Сообщение12.12.2007, 19:28 
Аватара пользователя
:evil:
Во-первых, у Вас не $x_{i,j}$, а $x_{|i-j|}$. Соответственно, производную по $x$ Вы подсчитали неправильно. (Иначе Вы можете выбрать произвольные $S_i$, $R_j$, и положить $X_{i,j} = \frac{A_{i,j}}{S_iR_j}$.

Во-вторых, Вам не напоминает то, что у Вас получилось, систему линейных уравнений? Если Вы нормализуете на $\sum s_i =0$, $\sum r_j  = 0$, она ещё более упростится: $ \frac{{\partial U}} {{\partial s_i }} = 2Ms_i + 2\sum\limits_{j = 1}^M {\left( {x_{|i-j|} - a_{ij} } \right)} $, $ \frac{{\partial U}} {{\partial r_j }} = 2Nr_j + 2\sum\limits_{i = 1}^N {\left( { x_{|i-j|} - a_{ij} } \right)} $

Добавлено спустя 6 минут 45 секунд:

mbaitoff писал(а):
опустим, приравняв к нулю, я выразил все s_i, r_j, x_{ij}, но что мне это дает? все они по-прежнему зависят друг от друга.

Что значит «я выразил»? Если Вы решили систему уравнений, Вы нашли Ваш ответ.

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group