2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Gaussian fit
Сообщение03.08.2018, 23:57 


10/05/09
71
Здравствуйте!

Есть такая задача: дан массив. Нужно аппроксимировать его с помошью гауссиан. Известно количество гауссиан и положение их центров.
Изображение

Пример результата:
Изображение

Как следует подходить к решению такой задачи? Готовые решения в виде программных пакетов не подходят, нужно знать алгоритмический подход чтобы я мог хотя бы переписать готовое решение под себя.

Для данного примера я вижу что следует минимизировать функционал зависящий от 6 параметров:
$y (A_1, \sigma_1, A_2, \sigma_2, A_3, \sigma_3 ) = A_1 e^{ {-}\frac{(x - \mu_1)^2}{(2 \sigma_1)^2} } + A_2 e^{ {-} \frac{(x - \mu_2)^2}{(2 \sigma_2)^2} } +
A_3 e^{ {-} \frac{(x - \mu_3)^2}{(2 \sigma_3)^2} }$

Наивный вариант: задать сетку значений всех 6 параметров, и найти минимум для всех вариантов параметров. Но встает вопрос как выбирать оптимальный шаг на сетке параметров и какая будет вычислительная сложность. Стоит ли так делать?

 Профиль  
                  
 
 Re: Gaussian fit
Сообщение04.08.2018, 00:14 
Супермодератор
Аватара пользователя


09/05/12
15382
Кронштадт
Вы минусы в показателях экспонент потеряли. :-)

А так... метод Левенберга-Марквардта не годится?

 Профиль  
                  
 
 Re: Gaussian fit
Сообщение04.08.2018, 00:17 


10/05/09
71
Pphantom в сообщении #1330473 писал(а):
Вы минусы в показателях экспонент потеряли. :-)

А так... метод Левенберга-Марквардта не годится?

оупс, конечно.

Надо подумать...

 Профиль  
                  
 
 Re: Gaussian fit
Сообщение04.08.2018, 08:50 
Заслуженный участник


05/08/14
1416
В функционале должна быть сумма по всем наблюдениям. Сумма $A_i$ должна равняться единице, и они должны быть положительными, иначе это не будет плотность. Т.е. оптимизация условная. Далее любой солвер-оптимизатор найдет максимум правдоподобия. Функционал надо максимизировать. Чтобы был «честный» максимум правдоподобия, экспоненты надо разделить на сигмы и корень из два пи.

 Профиль  
                  
 
 Re: Gaussian fit
Сообщение04.08.2018, 17:41 


10/05/09
71
dsge в сообщении #1330500 писал(а):
В функционале должна быть сумма по всем наблюдениям. Сумма $A_i$ должна равняться единице, и они должны быть положительными, иначе это не будет плотность. Т.е. оптимизация условная. Далее любой солвер-оптимизатор найдет максимум правдоподобия. Функционал надо максимизировать. Чтобы был «честный» максимум правдоподобия, экспоненты надо разделить на сигмы и корень из два пи.

В моем случае гауссианы не нормализованы на единицу.

 Профиль  
                  
 
 Re: Gaussian fit
Сообщение04.08.2018, 17:47 
Заслуженный участник


05/08/14
1416
Надо не плотность подогнать, а данные? Тогда, да.

 Профиль  
                  
 
 Re: Gaussian fit
Сообщение04.08.2018, 18:07 


10/05/09
71
dsge в сообщении #1330584 писал(а):
Надо не плотность подогнать, а данные? Тогда, да.

Плотность вообще никак не фигурирует.

 Профиль  
                  
 
 Re: Gaussian fit
Сообщение09.08.2018, 21:25 
Экс-модератор
Аватара пользователя


23/12/05
10530
Гуглите GMM algorithm и обрящете искомое. (GMM = Gaussian Mixture Model). У вас, правда, задача попроще - количество и центры уже известны, но упрощать - не усложнять.

 Профиль  
                  
 
 Re: Gaussian fit
Сообщение12.08.2018, 13:38 
Аватара пользователя


26/05/12
759
приходит весна?
Adventor в сообщении #1330471 писал(а):
Для данного примера я вижу что следует минимизировать функционал зависящий от 6 параметров:
$$y (A_1, \sigma_1, A_2, \sigma_2, A_3, \sigma_3 ) = A_1 e^{ {-}\frac{(x - \mu_1)^2}{(2 \sigma_1)^2} } + A_2 e^{ {-} \frac{(x - \mu_2)^2}{(2 \sigma_2)^2} } +
A_3 e^{ {-} \frac{(x - \mu_3)^2}{(2 \sigma_3)^2} }$$

По параметрам $A_i$ оптимизацию можно сделать сразу аналитически. То есть численная оптимизация будет проходить только по трём параметрам: $\sigma_i$.

Если вас интересует простой надёжный алгоритм, не использующий производные, то рекомендую алгоритм Нелдера-Мида. Именно он используется в стандартной функции fminsearch программы МАТЛАБ. Его простоту гарантирую, так как сам его реализовывал на си.

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

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

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

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

Модераторы: Karan, PAV, Toucan, maxal, Супермодераторы



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

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


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

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