2014 dxdy logo

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

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


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


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Проекционный алгоритм
Сообщение26.05.2017, 22:00 


26/05/17
24
Занимаюсь решением задачи диагностики работы устройства. В компьютер поступает информация от датчиков и обрабатывается путем решения уравнений в онлайне.

Скачал класс (C++) с проекционным решающим алгоритмом, закомпилировал. Все работает хорошо. Возникла новая задача: все то же, но с сильным шумом. Стал копать алгоритм, пришел по ссылкам с сайта класса сюда, смотри рис. 4.

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

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

 Профиль  
                  
 
 Re: Проекционный алгоритм
Сообщение27.05.2017, 11:22 
Заслуженный участник


05/08/14
1564
Базисные функции, теория приближений, теория аппроксимаций. Книги по численным методам, прикладному функциональному анализу.

 Профиль  
                  
 
 Re: Проекционный алгоритм
Сообщение13.02.2018, 13:44 


26/05/17
24
У меня снова возникло желание вернуться к вопросу.

Может быть, кто-нибудь подскажет конкретную литературу, отталкиваясь от которой можно "расшифровать" данную блок-схему?

 Профиль  
                  
 
 Re: Проекционный алгоритм
Сообщение14.02.2018, 00:55 
Заслуженный участник


26/05/14
981
Кажется, блок схема работает с понятиями из линейной алгебры - матрицами и векторами.
Читать блок схемы, я надеюсь, вы умеете. Если так, то осталось только разобраться с выражениями внутри блоков. Какой блок вам не ясен?

 Профиль  
                  
 
 Re: Проекционный алгоритм
Сообщение14.02.2018, 09:51 


26/05/17
24
slavav в сообщении #1292365 писал(а):
Кажется, блок схема работает с понятиями из линейной алгебры - матрицами и векторами.
Читать блок схемы, я надеюсь, вы умеете. Если так, то осталось только разобраться с выражениями внутри блоков. Какой блок вам не ясен?



Так с блок-схемой проблем нет, все формулы глазами вижу. Вопрос - не в том, чтобы все это запрограммировать (тем более, что все уже запрограммировано и работает).

Вопрос - в том, чтобы понять, на основе какой (конкретно) теории создан этот алгоритм. В какой статье или книге встречаются подобные формулы? Вот это мне пока не понятно, а хочется понять.

 Профиль  
                  
 
 Re: Проекционный алгоритм
Сообщение14.02.2018, 11:29 
Заслуженный участник
Аватара пользователя


11/03/08
9492
Москва
0. В статье (хотя тут претензия не столько к её авторам, сколько к "Известным специалистам Бейкеру и Грейвс-Моррису") несколько превратно показано преимущество аппроксимации Паде над многочленами. Разложение в ряд Тейлора делается не с целью получить наилучшую аппроксимацию значений функции на отрезке, а чтобы в данной точке аппроксимировать функцию и все её производные. Поэтому на отдалении от этой точки приближение рядом Тейлора всё более и более отстоит от значений функции, однако если, скажем, приближать многочленами Чебышева, точность будет хороша на всём отрезке, и такого эффекта, как на иллюстрирующей преимущество Паде над многочленами картинке, не будет. Аппроксимация отношением полиномов может быть лучше, скажем, тем, что может отражать поведение функции за пределами отрезка аппроксимации (полиномы любят, даже если хорошо подогнаны к данным на отрезке, "гулять" за его пределами, уходя в бесконечность).
1. Используемый метод подгонки сводится к тому, что от выражения $y=\frac {f(x)}{g(x)}$, где f, g - полиномы, переходят к $y g(x)=f(x)$, при этом коэффициенты числителя и знаменателя можно одновременно умножить на одно и то же число, так что можно выбрать их так, чтобы константа в многочлене g(x) была бы равна 1. Тогда $y g(x)=f(x)$ можно записать в виде $y(1+g(x)-1)=f(x)$ или $y=f(x)+y(1-g(x))$, которое является линейным по параметрам и может быть легко оценено. Однако тут может крыться ловушка.
Обычно данные отягощены погрешностью, как ошибкой измерения, так и ошибкой спецификации модели.
$y=\frac {f(x)}{g(x)}+\varepsilon$
и тогда при умножении на g(x) спецификация ошибки изменится: там, где знаменатель велик, погрешности будут приближаться тщательнее, чем там, где мал (а если g(x) в некоторых точках обращается в ноль - соответствующие значения будут вовсе пренебрежены). Такой подход работает, если $g(x)\approx 1$, в противном случае надо использовать общие методы нелинейной регрессии, потеряв лёгкость вычислений.
2. Перейдя в линейную (по параметрам, сами слагаемые модели будут одночленами разных степеней и их произведениями на y, в этом смысле модель нелинейна, но линейно зависит от коэффициентов при слагаемых) модель $y(1+g(x)-1)=f(x)$, можем её оценивать обычным МНК. Это потребует обращения матрицы, что представляло крайне трудоёмкую часть работы в докомпьютерную эру, и даже в раннекомпьютерную, и способствовало развитию итеративных методов, менее расходных по вычислительной мощности (в них вместо обращения, задачи кубической сложности по отношению к размерности матрицы, использовалось многократное умножение матрицы на вектор и сложение матриц, обе квадратичны по сложности). Это преимущество ныне востребовано для очень больших разреженных матриц; для таких размерностей, как у Вас, лично я бы использовал обычное выражение для регрессии
$a=(X^TX)^{-1}X^Ty$. Есть ещё два основания предпочесть итеративные методы обращению матрицы, но одно из них здесь, полагаю, "не играет", а второе скорее ложно и способствует самообману. Итеративный алгоритм использует выражение для коррекции обратной матрицы при прибавлении к ней матрицы ранга 1, соответствующей добавлению новых строк в матрицу данных. Его можно дополнить коэффициентом, дающим "гиперкоррекцию" в том смысле, что вновь поступившие данные имеют больший вес, чем прежние. Это полезно, если модель в действительности не постоянна, а меняется во времени, так что слишком старые данные стоит забыть, опираясь на более свежие. Так, именно этим образом, по всей вероятности, рассчитывается линейная аппроксимация Вашей речи в Вашем сотовом телефоне, как часть процедуры сжатия сигнала. Поскольку положение губ, языка и другие характеристики речевого аппарата меняются во времени - бессмысленно использовать слишком давние отсчёты звукового сигнала. Однако, если я правильно понял, у Вас для всех наблюдений используется одна и та же модель, и подобное преимущество менее уместно, чем горб верблюда в зоопарке - он хотя бы "приколен". Второе преимущество состоит в том, что такой алгоритм даст Вам ответ, даже если матрица неполного ранга и необратима. Но этот ответ может быть в таком случае попросту бессмысленен, и об этом грустном факте лучше знать, а не довольствоваться тем, что "что-то посчитало".

 Профиль  
                  
 
 Re: Проекционный алгоритм
Сообщение14.02.2018, 12:34 
Заслуженный участник
Аватара пользователя


11/03/08
9492
Москва
Что касается объяснения идеи метода - её надо искать в книгах либо по эконометрике, либо по электросвязи. И там, и там возникает задача оценивания модели, параметры которой могут меняться во времени. Помнится, я что-то такое видел в Прокисе, "Цифровая связь", впрочем, во многих книгах по цифровой обработке сигналов это можно найти, там и другое преимущество этого метода играет - сигнальные процессоры имеют обычно не рекордную производительность и весьма скромную память, так что алгоритм быстрый и с минимальными требованиями к памяти ценен. Экономисты время на расчёты имеют, для них важнее "современность" алгоритма, то, что свежие данные входят с большим весом.
Вот ссылка на заметку в Вики, где метод назван "рекурсивным МНК". При всей краткости и даже поверхностности описания идею можно понять.
https://ru.wikipedia.org/wiki/%D0%A0%D0 ... 0%9D%D0%9A
Ещё замечу, что для коррекции обратной матрицы при добавлении очередной строки данных опираются на тождество
$(\mathbf {A} -\mathbf {BD} ^{-1}\mathbf {C} )^{-1}=\mathbf {A} ^{-1}+\mathbf {A} ^{-1}\mathbf {B} (\mathbf {D} -\mathbf {CA} ^{-1}\mathbf {B} )^{-1}\mathbf {CA} ^{-1}$
в котором в качестве B и C используются добавляемые к данным строки (и та же строка, но транспонированная, соответственно), а D - единичная матрица

 Профиль  
                  
 
 Re: Проекционный алгоритм
Сообщение14.02.2018, 14:45 


26/05/17
24
Евгений,

Сначала - про Ваши пункты 0. - 1. - 2.

0. Да, похоже, что "преимущество аппроксимации Паде" там "натянуто" с помощью удобного примера. Ну и шут с ними, с этими аппроксимациями, я их не использую.

1. Сам метод (сведения дроби к линейному уравнению), кстати, довольно изящный. Но опять же, я его не собираюсь использовать.

2.
Цитата:
Это полезно, если модель в действительности не постоянна, а меняется во времени, так что слишком старые данные стоит забыть, опираясь на более свежие. Так, именно этим образом, по всей вероятности, рассчитывается линейная аппроксимация Вашей речи в Вашем сотовом телефоне, как часть процедуры сжатия сигнала. Поскольку положение губ, языка и другие характеристики речевого аппарата меняются во времени - бессмысленно использовать слишком давние отсчёты звукового сигнала. Однако, если я правильно понял, у Вас для всех наблюдений используется одна и та же модель


Дело в том, что на вход приходят реальные сигналы от реальных датчиков; в каждый момент времени эти сигналы не очень-то соответствуют подгоняемой модели (дифференциальному уравнению). И не только из-за ошибки округления, а в основном потому, что механизм сложный и проявляется куча локальных эффектов, которые можно "пережевать", только "переварив" всю запись испытания.
Кстати, всего у нас получается такая система:
строк: 3600сек. * 10Гц = 36000 (это минимум, лучше брать гораздо большую частоту дискретизации),
столбцов: точно не менее 10 - это к-ты перед членами уравнения (разные измеряемые параметры, их производные и прочие комбинации).

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

P.S. Кстати, класс, о котором я тут говорю и в котором запрограммирована данная блок-схема - вот он.

-- 14.02.2018, 15:52 --

Евгений Машеров в сообщении #1292419 писал(а):
Что касается объяснения идеи метода - её надо искать в книгах либо по эконометрике, либо по электросвязи. И там, и там возникает задача оценивания модели, параметры которой могут меняться во времени. Помнится, я что-то такое видел в Прокисе, "Цифровая связь", впрочем, во многих книгах по цифровой обработке сигналов это можно найти, там и другое преимущество этого метода играет - сигнальные процессоры имеют обычно не рекордную производительность и весьма скромную память, так что алгоритм быстрый и с минимальными требованиями к памяти ценен. Экономисты время на расчёты имеют, для них важнее "современность" алгоритма, то, что свежие данные входят с большим весом.
Вот ссылка на заметку в Вики, где метод назван "рекурсивным МНК". При всей краткости и даже поверхностности описания идею можно понять.
https://ru.wikipedia.org/wiki/%D0%A0%D0 ... 0%9D%D0%9A
Ещё замечу, что для коррекции обратной матрицы при добавлении очередной строки данных опираются на тождество
$(\mathbf {A} -\mathbf {BD} ^{-1}\mathbf {C} )^{-1}=\mathbf {A} ^{-1}+\mathbf {A} ^{-1}\mathbf {B} (\mathbf {D} -\mathbf {CA} ^{-1}\mathbf {B} )^{-1}\mathbf {CA} ^{-1}$
в котором в качестве B и C используются добавляемые к данным строки (и та же строка, но транспонированная, соответственно), а D - единичная матрица


Спасибо, в закладки. Только вот чего нет в этом методе - а нет тут коэффициентов для его настройки. Потому что, как показывает практика, такие к-ты сильно влияют на качество/скорость получения решения.

Цитата:
её надо искать в книгах либо по эконометрике, либо по электросвязи


Вот и не могу никак найти. А надо, потому что нужно для составления документации. Ну и для общего развития тоже...

 Профиль  
                  
 
 Re: Проекционный алгоритм
Сообщение14.02.2018, 16:20 
Заслуженный участник
Аватара пользователя


11/03/08
9492
Москва
Ну, собственно, тут один настроечный параметр, задающий "скорость забывания". И, боюсь, его лишь эмпирически можно подобрать, он сильно зависит от задачи. Чем быстрее изменяется состояние - тем скорее забывать надо. В качестве одного из вариантов подбора - провести на некоей выборке расчёт с разными значениями этого параметра, а в качестве критерия - ошибка прогноза по модели.

 Профиль  
                  
 
 Re: Проекционный алгоритм
Сообщение14.02.2018, 16:38 


26/05/17
24
Евгений Машеров в сообщении #1292450 писал(а):
Ну, собственно, тут один настроечный параметр, задающий "скорость забывания". И, боюсь, его лишь эмпирически можно подобрать, он сильно зависит от задачи. Чем быстрее изменяется состояние - тем скорее забывать надо. В качестве одного из вариантов подбора - провести на некоей выборке расчёт с разными значениями этого параметра, а в качестве критерия - ошибка прогноза по модели.


А вот и нет :D

Там еще есть параметры Smax и Z2F.

Причем параметр "забывания" относится к тамошнему рекурсивному МНК. То есть для учета забывания проекционный алгоритм как бы и не нужен, можно каждую МНК-систему можно решать хоть по Гауссу, да хоть по Крамеру, то есть целиком. И итерировать себе дальше.

А там МНК-системы решаются (уточняется решение) непрерывно, с шагом в 1 строку, по мере поступления строк, то есть наблюдений за процессом. В этом ("проекционном") алгоритме и участвуют Smax и Z2F. Их цель - откатывать старое решение, если новое "ушло" куда-то не туда.

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

P.S. На всякий случай извиняюсь за въедливость.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

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



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

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


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

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