Подскажите алгоритм
От: Khimik  
Дата: 06.10.19 14:30
Оценка:
Я уже выкладывал на форуме свою программу для обработки данных коммерческих рыболовных эхолотов:

http://rsdn.org/forum/shareware/7483435.all
Автор: Khimik
Дата: 01.07.19


  Скрытый текст


Моя программа строит карту глубин. В данном случае карта – это двумерный массив точек. Алгоритм заключается в том, что сводится к минимуму некий функционал – сумма двух слагаемых, домноженных на выбранные коэффициенты. Первое слагаемое – средняя разница между «экспериментальными” точками (полученными на эхолоте) и точками модели (точнее, средний квадрат разницы). Чем меньше это число, тем лучше совпадает модель с замерами эхолотов (в местах где проводились замеры, само собой). Второе слагаемое – средний квадрат разности между каждыми соседними точками модели, можно сказать что это интеграл от квадрата первой производной на модели. Чем меньше это число – тем более «гладкая” выходит модель.
Коэффициент, на которых домножается второе слагаемое, характеризует значимость первого и второго слагаемого. Если первое слишком значимо (этот коэффициент мал), модель будет слишком подстраиваться под ошибки измерений; если второе слишком значимо, модель будет слишком гладкая и некорректно описывать замеры (в предельном случае это будет одна горизонтальная плоскость, единое число для всех точек модели).
Мой алгоритм минимизирует функционал методом градиентного спуска. К сожалению, такой подход жутко медленный – модель считается раз в тысячу медленнее, чем у других программ такого рода.
Я знаю что можно ускорить расчёт, если заменить градиентный спуск на построение системы линейных уравнений. Для одномерно варианта задачи у меня это довольно легко вышло, но в двумерном варианте получается что-то ужасно сложное. Система линейных уравнений двумерна, но её можно в данном случае назвать четырёхмерной, поскольку число строк и столбцов в ней – это общее число точек в модели, т.е. произведение длины модели на ширину.
В текущем варианте моя программа годится только для малых водоёмов (для средних расчёт модели длится слишком долго), но я слышал что для них рыбаки эхолотами не пользуются.
Может кто-нибудь подсказать более простой алгоритм для моей задачи? Это может быть либо другой способ минимизации описанного функционала, либо замена его на какие-нибудь сплайны или лагранжевы функции.
Мне кажется, должен существовать алгоритм итерационный, но «менее итерационный” чем градиентный спуск и соответственно более быстрый. Я не знаю как это называется, я бы описал это словом «самосогласованное схождение к минимуму”.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Re: Подскажите алгоритм
От: kov_serg Россия  
Дата: 07.10.19 07:37
Оценка:
Здравствуйте, Khimik, Вы писали:

K> Может кто-нибудь подсказать более простой алгоритм для моей задачи? Это может быть либо другой способ минимизации описанного функционала, либо замена его на какие-нибудь сплайны или лагранжевы функции.

K> Мне кажется, должен существовать алгоритм итерационный, но «менее итерационный” чем градиентный спуск и соответственно более быстрый. Я не знаю как это называется, я бы описал это словом «самосогласованное схождение к минимуму”.
А что если просто построить усреднение по ближайшим точкам к данной (например в радиусе r)
Типа такой функции:
  est(x0,y0, x,y,z,dz)
#include <math.h>
#include <stdio.h>

double est(double x0,double y0,int n,double *x,double *y,double *z,double *dz,double *w) {
    int i, im=0; double wm=0,s0=0,s1=0;
    if (dz) {
        for(i=0;i<n;i++) {
            w[i]=hypot(x[i]-x0,y[i]-y0)*fabs(dz[i]);
            if (i==0 || wm>w[i]) {
                im=i; wm=w[i]; if (wm==0) return z[i];
            }
        }
    } else {
        for(i=0;i<n;i++) {
            w[i]=hypot(x[i]-x0,y[i]-y0);
            if (i==0 || wm>w[i]) {
                im=i; wm=w[i]; if (wm==0) return z[i];
            }
        }
    }
    for(i=0;i<n;i++) {
        if (i==im) { s0+=1; s1+=z[i]; }
        else { s0+=wm/w[i]; s1+=z[i]*wm/w[i]; }
    }
    return s1/s0;
}

int main(int argc, char const *argv[]) {
    enum { n=4 }; double w[n],
        x[n]={0,1,1,0},
        y[n]={0,0,1,1},
        z[n]={1,2,2,2}, 
        dz[n]={0.10,0.15,0.05,0.20},
        x0=0.5, y0=0.5,
        z0=est(x0,y0,n,x,y,z,dz,w);
    printf("est=%.3f\n",z0);
    return 0;
}
где x0,y0 точка где хотим прикинуть глубину, x,y,z,dz список точек с координатами, глубиной и прогрешностью (или обр. весами или вообе без).
Re: Подскажите алгоритм
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 07.10.19 08:08
Оценка:
Здравствуйте, Khimik, Вы писали:

K> Может кто-нибудь подсказать более простой алгоритм для моей задачи? Это может быть либо другой способ минимизации описанного функционала, либо замена его на какие-нибудь сплайны или лагранжевы функции.

K> Мне кажется, должен существовать алгоритм итерационный, но «менее итерационный” чем градиентный спуск и соответственно более быстрый. Я не знаю как это называется, я бы описал это словом «самосогласованное схождение к минимуму”.

Такой алгоритм мне не известен. Ты уверен, что нельзя ускорить алгоритм с помощью всяких разных оптимизаций? Например, взять готовую библиотеку для этого. Ceres solver не решает твою проблему?
Re[2]: Подскажите алгоритм
От: Khimik  
Дата: 07.10.19 13:38
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>Здравствуйте, Khimik, Вы писали:


K>> Может кто-нибудь подсказать более простой алгоритм для моей задачи? Это может быть либо другой способ минимизации описанного функционала, либо замена его на какие-нибудь сплайны или лагранжевы функции.

K>> Мне кажется, должен существовать алгоритм итерационный, но «менее итерационный” чем градиентный спуск и соответственно более быстрый. Я не знаю как это называется, я бы описал это словом «самосогласованное схождение к минимуму”.
_>А что если просто построить усреднение по ближайшим точкам к данной (например в радиусе r)

Спасибо за идею, я попробую. Кажется это называется Adjacent averaging. Может получится хорошее начальное приближение, чтобы меньше времени требовалось на градиентный спуск.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Re[2]: Подскажите алгоритм
От: Khimik  
Дата: 07.10.19 13:40
Оценка:
Здравствуйте, Nuzhny, Вы писали:

N>Здравствуйте, Khimik, Вы писали:


K>> Может кто-нибудь подсказать более простой алгоритм для моей задачи? Это может быть либо другой способ минимизации описанного функционала, либо замена его на какие-нибудь сплайны или лагранжевы функции.

K>> Мне кажется, должен существовать алгоритм итерационный, но «менее итерационный” чем градиентный спуск и соответственно более быстрый. Я не знаю как это называется, я бы описал это словом «самосогласованное схождение к минимуму”.

N>Такой алгоритм мне не известен. Ты уверен, что нельзя ускорить алгоритм с помощью всяких разных оптимизаций? Например, взять готовую библиотеку для этого. Ceres solver не решает твою проблему?


Я чайник в таких вещах, не слышал про Ceres solver и вообще не представляю, как какие-то сторонние библиотеки вообще могут ускорить алгоритм. А мне надо ускорить свой раз в тысячу.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Re: Подскажите алгоритм
От: wildwind Россия  
Дата: 08.10.19 05:59
Оценка:
Здравствуйте, Khimik, Вы писали:

Лет десять назад я работал с геологами и экологами, и у них тоже часто возникает эта задача. Только они имеют дело не с глубиной водоемов, а с землей и распределением в ней неких величин, например содержания определенных элементов и веществ. Я узнал тогда, что общеизвестного "хорошего" во всех случаях алгоритма нет, коммерческие программы имеют свои проприетарные и конкурируют в основном именно ими. И лучшие алгоритмы используют знания о предметной области (вводимые экспертом) для сокращения объема вычислений. Сама задача, кажется, называется "регуляризация".

А очевидно напрашивающееся "лобовое" решение для вашего случая — это считать тем, что у вас есть, в облаке, за небольшую денежку.
Re: Подскажите алгоритм
От: kfmn Россия  
Дата: 09.10.19 08:14
Оценка:
Здравствуйте, Khimik, Вы писали:

K> Моя программа строит карту глубин. В данном случае карта – это двумерный массив точек. Алгоритм заключается в том, что сводится к минимуму некий функционал – сумма двух слагаемых, домноженных на выбранные коэффициенты. Первое слагаемое – средняя разница между «экспериментальными” точками (полученными на эхолоте) и точками модели (точнее, средний квадрат разницы). Чем меньше это число, тем лучше совпадает модель с замерами эхолотов (в местах где проводились замеры, само собой). Второе слагаемое – средний квадрат разности между каждыми соседними точками модели, можно сказать что это интеграл от квадрата первой производной на модели. Чем меньше это число – тем более «гладкая” выходит модель.


Если честно, по описанию это выглядит стандартной задачей аппроксимацией функции двух переменных по набору точек с регуляризацией по гладкости... Я бы первым делом посмотрел в сторону простых двумерных сплайнов или метода наименьших квадратов с какими-то простыми гладкими базисными функциями. Есть робастные варианты МНК, которые умеют отстраиваться от выбросов в данных.
Re: Подскажите алгоритм
От: Слава  
Дата: 09.10.19 08:21
Оценка:
Здравствуйте, Khimik, Вы писали:

K>Я уже выкладывал на форуме свою программу для обработки данных коммерческих рыболовных эхолотов:


K>http://rsdn.org/forum/shareware/7483435.all
Автор: Khimik
Дата: 01.07.19


Есть такой ЖЖ golos-dobra, вот можно к нему сходить и аккуратно, вежливо поинтересоваться методом расчёта.
Отредактировано 09.10.2019 8:21 Слава . Предыдущая версия .
Re: Подскажите алгоритм
От: Sharowarsheg  
Дата: 14.11.19 23:42
Оценка:
Здравствуйте, Khimik, Вы писали:

K>Я уже выкладывал на форуме свою программу для обработки данных коммерческих рыболовных эхолотов:


K>http://rsdn.org/forum/shareware/7483435.all
Автор: Khimik
Дата: 01.07.19


K>Моя программа строит карту глубин. В данном случае карта – это двумерный массив точек.


А сколько на сколько размер?

K> Алгоритм заключается в том, что сводится к минимуму некий функционал – сумма двух слагаемых, домноженных на выбранные коэффициенты. Первое слагаемое – средняя разница между «экспериментальными” точками (полученными на эхолоте) и точками модели (точнее, средний квадрат разницы). Чем меньше это число, тем лучше совпадает модель с замерами эхолотов (в местах где проводились замеры, само собой). Второе слагаемое – средний квадрат разности между каждыми соседними точками модели, можно сказать что это интеграл от квадрата первой производной на модели. Чем меньше это число – тем более «гладкая” выходит модель.


А смысл у этой сложной эволюции какой? Почему нельзя, например, взять карту, да так её и использовать?

И сколько неизвестных? Сумма двух слагаемых, домноженных на выбранные коэффициенты — что из этого известно, что неизвестно, и сколько коэффициентов?

От числа размерностей сильно зависит, какие приёмы есть. В смысле, сколько параметров у функции, которую надо минимизировать. Одно дело, когда одна-две-три оси, а другое дело, когда минимизация в стомерном пространстве.

K>Я знаю что можно ускорить расчёт, если заменить градиентный спуск на построение системы линейных уравнений. Для одномерно варианта задачи у меня это довольно легко вышло, но в двумерном варианте получается что-то ужасно сложное. Система линейных уравнений двумерна, но её можно в данном случае назвать четырёхмерной, поскольку число строк и столбцов в ней – это общее число точек в модели, т.е. произведение длины модели на ширину.



Можно, наверное, взять сетку и проредить её или в 9 раз (выкинув две точки из трёх в каждой оси), или в 100 раз (выкинув 9 из 10 в каждой оси), и посчитать параметры для такой облегчённой карты. Насколько они будут совпадать с правильными?

C другой стороны, можно на видеокарте считать, например. Вроде хорошо ложится на параллельность.
Отредактировано 15.11.2019 0:18 Sharowarsheg . Предыдущая версия . Еще …
Отредактировано 15.11.2019 0:17 Sharowarsheg . Предыдущая версия .
Отредактировано 14.11.2019 23:47 Sharowarsheg . Предыдущая версия .
Отредактировано 14.11.2019 23:44 Sharowarsheg . Предыдущая версия .
Отредактировано 14.11.2019 23:43 Sharowarsheg . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.