Алгоритм МНК

[mserg]

На вскидку, тут может быть применен интервальный анализ.
Из Open Source вроде как может решить эту задачу COUENNE.
Если выложите данные - смогу сказать точнее.

[Truedoday]

iifat в сообщении #1002316 писал(а):

Гугл по строке «метод Левенберга — Марквардта» даёт примерно 3490. Неужели среди них нет понятного описания?

Разумеется я искал и парочка описаний есть, но они не сильно помогли. Либо они слишком краткие, либо я плохо читаю математические тексты (скорее и то и другое).

-- 10.04.2015, 19:29 --

mserg в сообщении #1002362 писал(а):

На вскидку, тут может быть применен интервальный анализ.
Из Open Source вроде как может решить эту задачу COUENNE.
Если выложите данные - смогу сказать точнее.

Буду очень признателен. Данные прикрепил. Аппроксимирующая функция для них $f(x)=A \cdot \sin(\omega \cdot x + \varphi)\cdot e^{-b \cdot x}\cdot x^2$.

Если есть исходники - было бы неплохо. Хотя разобраться в них все равно придется, так как требуется аппроксимировать не только этой, но и еще одной функцией другие данные.

[mserg]

COUENNE не очень быстро, но, в принципе, решает задачу - см. столбец z.

Исходные тексты, тоже не проблема:
http://www.coin-or.org/projects/Couenne.xml

Проблема в том, чтобы откомпилировать. Даже не совсем так - есть откомпилированное
http://www.coin-or.org/download/binary/Couenne/

Для Standalone-решателя требуется записать все это в хитро-сделанном формате Ampl (расширение .nl).
Если подключать в виде библиотеки, если мне не изменяет память, нужно указать не только целевую функцию, но еще и первые/вторые производные по переменным. Там, конечно, есть библиотеки для автоматического дифференцирования, но все это может отнять массу времени.

Чтобы избежать потери времени, нужен некоторый инструмент моделирования, которое сделает черновую работу для COUENNE сам. Возможно, есть бесплатная версия AMPL на малое число переменных.

Сам я решал задачу в системе Quick NP - система сама делает все необходимое и вызывает COUENNE.exe.

Есть еще вариант с интервальными библиотеками типа PROFIL/BIAS ... По-моему, там есть примеры, которые можно адаптировать под вашу задачу. Если не будет других идей - имеет смысл попробовать.

[Truedoday]

mserg в сообщении #1002433 писал(а):

COUENNE не очень быстро, но, в принципе, решает задачу - см. столбец z.

Отличный результат. Я правильно понимаю, что столбец z получен по аналитической формуле с подставленными коэффициентами $A, \omega, \varphi, b$?

Учитывая, что алгоритм нужен только под одну функцию, производные я сам могу вычислить.

Мне вообще нужен алгоритм, чтоб я его мог понять и руками переписать в другой среде. Подскажите, если можно, где искать в исходниках?

[mserg]

Да, результат получен "подбором" четырех параметров с помощью решения оптимизационной задачи, т.е решением МНК.

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

Поэтому, если нужно иметь строго свой код, то имеет смысл попробовать PROFIL/BIAS (или что-то другое, но я не знаю).

Нужно будет аккуратно прикинут диапазон значений для каждого из параметров.

Насколько я помню, в примерах PROFIL/BIAS реализован поиск с ветвлением переменных, оценками и локальном поиске оптимума в узлах ветвления методом Нелдера-Мида. Вам нужно будет вставить туда свою функцию. Если все получится, можно убрать все "лишнее".

[mserg]

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

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

Во-вторых, если огибающая хорошо видна, то можно найти аргумент абсолюта максимума экспериментальных данных. Потом посмотреть, где огибающая аппроксимирующей функции достигает максимума. Для этого нужно отбросить A, синус и исследовать на экстремум остаток функции (он завит только от b). Т.е. можно оценить b.

В-третьих, можно оценить A по МНК, использовав уже оцененные остальные параметры.

В-четвертых, можно уточнить все параметры с помощью МНК каким-нибудь локальным методом оптимизации, используя полученные ранее оценки.

[Truedoday]

Я порылся в исходниках, думал над информацией, полученной в ответах и смог написать алгоритм. Спасибо всем за помощь Остался еще вопрос, но если его сам не решу, то задам в другой теме - не подходит под Computer Science.

[Xey]

Truedoday в сообщении #1002152 писал(а):

P.S. Или может есть какой-то другой метод, способный дать подобные результаты?

Одни считают , что есть , другие утверждают, что это по сути тоже самое.

Maslov в сообщении #257678 писал(а):

Xey в сообщении #257651 писал(а):

Сейчас сети применяют там, где обычно обходились МНК, и говорят, что это лучше.

Классическое обучение многослойного персептрона - это и есть МНК; его суть в минимизации среднеквадратичной ошибки обучения в пространстве весов. Так что противопоставлять эти два подхода вряд ли корректно.

[Xey]

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

Алексей К. в сообщении #74190 писал(а):

Не надо фитировать сумму квадратов расстояний от точки до окружности.
Достаточно минимизировать

$$\sum [(x_i^2+y_i^2)-2Bx_i-2Cy_i+Q]^2$$

,
то есть отклонения от нуля значения левой части неявного уравнения окружности.
Можно показать, что при малых отклонениях это близко к честному МНК.

На сколько обосновано такое упрощение?

[Truedoday]

Xey в сообщении #1002812 писал(а):

Maslov в сообщении #257678 писал(а):

Xey в сообщении #257651 писал(а):

Сейчас сети применяют там, где обычно обходились МНК, и говорят, что это лучше.

Классическое обучение многослойного персептрона - это и есть МНК; его суть в минимизации среднеквадратичной ошибки обучения в пространстве весов. Так что противопоставлять эти два подхода вряд ли корректно.

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

[Алексей К.]

Xey в сообщении #1002939 писал(а):

На сколько обосновано такое упрощение?

Его, когда я этим занимался, удалось легко обосновать тупым анализом. Что-то стандартное, с оценкой малых поправок, именно для окружности. Там уточнено --- "при малых отклонениях". Наверняка это означает, что при отклонениях от круглости порядка $\delta$ получим разницу между честным и нечестным способами определения линейных параметров (центр, радиус) порядка $\delta^2/R$.
Но вряд ли это применимо даже к эллипсу: симметрия окружности работала при доказательстве. И вряд ли это применимо к рассматриваемой задаче.

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

Метод Левенберга-Марквардта для нелинейной регрессии использует линеаризацию задачи, сводя её к серии линейных регрессий. Для этого берётся начальное приближение коэффициентов нелинейной модели и строится линейная регрессия, в которой регрессоры - производные нелинейной функции регрессии по коэффициентам, вычисленные в точках наблюдений, зависимая переменная (регрессанд) равна отклонениям наблюдаемых значений от вычисленных с данным приближением коэффициентов, а оцениваемые параметры линейной регрессии будут равны поправкам к значениям коэффициентов нелинейной модели. При этом возникает вычислительная трудность, связанная с тем, что значения производных (регрессоров вспомогательной модели) могут быть линейно зависимы или близки к линейно зависимым, так что обращение матрицы $Z^TZ$ будет вовсе невозможно или сопровождаться вычислительными ошибками. Особенность метода Левенберга-Марквардта в том, что перед обращением к диагонали прибавляют положительно определённую матрицу, обычно скалярную или же диагональ обращаемой матрицы, умноженную на некоторый коэффициент (конечно, если матрица предварительно нормирована и на диагонали единицы - это одно и то же)
Полученный из $\beta=(Z^TZ+kI)^{-1}Z^T(y-f(X,b))$ вектор поправок коэффициентов нелинейной регрессии прибавляется к коэффициентам нелинейной регрессии $b_{i+1}=b_i+\beta_i$ и расчёт повторяется до сходимости.

-- 17 май 2015, 17:31 --

Truedoday в сообщении #1002366 писал(а):

Данные прикрепил
. Аппроксимирующая функция для них $f(x)=A \cdot \sin(\omega \cdot x + \varphi)\cdot e^{-b \cdot x}\cdot x^2$.

Данные там уже убраны. Просьба выложить повторно (если,конечно,интерес к вопросу остался)

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

А вообще для именно такой функции не лучше ли было оценить частоту и фазу по пересечениям нуля и максимумам-минимумам (интерполируя, чтобы получить точность выше интервала между отсчётами), а потом (по тем же максимумам-минимумам) оценить $\frac {f(x)}{x^2}=Ae^{-bx}$, прологарифмировав и парной линейной регрессией?

[B@R5uk]

Лично я такие же задачи, которые возникают при обработке результатов физического эксперимента, решаю в матлабе с помощью функции fminsearch. Просто задаю функцию модели. Задаю функцию МНК. И оптимизирую её по параметрам модели. Единственная проблема: угадать начальное приближение для этих параметров (хотя, в зависимости от модели этой проблемы может и не быть).

Считается просто шикарно. Алгоритм, использованный в функции fminsearch вполне известный: метод Нелдера-Мида. Он гарантированно находит локальный минимум и достаточно быстро даже на плохих функциях. Кроме того, он очень прост для самостоятельной реализации (и я это сам проверял). Кстати, некоторые параметры модели, по которым модель линейна (например, постоянное смешение, амплитудный множитель каждого из слагаемых модели) не обязательно оптимизировать, их можно посчитать по формуле линеаризированного МНК аналитически, а оптимизацию вести по тем параметрам, по которым модель нелинейна. Это немного усложняет реализацию, но очень сильно увеличивает быстродействие.

И ещё. В численных методах первоочерденая задача -- поиск минимума. Решать диффуры, находить нули системы уравнений лучше делать через неё, а не на оборот.

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

А вообще для именно такой функции не лучше ли было оценить...

Кстати, это очень хороший метод получить оценки параметров модели и использовать их в качестве начального приближения для дальнейшей оптимизации. Однако, непосредственно их нельзя считать окончательным результатом, так как из-за выполненных нелинейных преобразований они не будут удовлетворять тем трём требованиям (что-то там про несмещённость, адекватность и так делее -- не помню точно), что накладывает теорвер на оценки параметров модели. Честно посчитать МНК всегда лучше, особенно, если случайные погрешности в данных имеют Гауссово распределение и не имеют систематической погрешности.