Вот придумалась такая задачка:
Есть набор одномерных измерений Xi, взятых через равные интервалы времени.
Требуется разделить временной отрезок на M частей и аппроксимировать данные Xi на каждой из частей полиномом степени не выше K, таким образом, чтобы минимизировать отклонения этой кусочно-полиномиальной аппроксимации от Xi по какой-нибудь разумной норме.
Вопрос 1: решается ли эта задача аналитически хотя бы для каких-нибудь степеней и норм? Поделитесь ссылочками по теме.
Далее. Понятно, что с ростом M минимальные отклонения будут убывать. Причем вначале быстро, а потом все медленнее и медленнее.
К примеру, если данные состоят из 5 квазиполиномиальных участков с разными параметрами, то M=5 будет в каком-то смысле оптимальным, дальше пойдет уточнение на участках.
Вопрос 2: Какие могут быть критерии определения этого оптимума?
Интерес пока что чисто академический, хотя понятно, что приложений у такой теории должно быть достаточно. Например, сегментация сильно нестационарных сигналов (скажем, речь) на квазистационарные участки (в случае речи — фонемы или их части).
Здравствуйте, kfmn, Вы писали:
K>Всем привет!
K>Вот придумалась такая задачка: K>Есть набор одномерных измерений Xi, взятых через равные интервалы времени. K>Требуется разделить временной отрезок на M частей и аппроксимировать данные Xi на каждой из частей полиномом степени не выше K, таким образом, чтобы минимизировать отклонения этой кусочно-полиномиальной аппроксимации от Xi по какой-нибудь разумной норме.
K>Вопрос 1: решается ли эта задача аналитически хотя бы для каких-нибудь степеней и норм? Поделитесь ссылочками по теме.
Что значит апроксимировать аналитичиски? Непонятно что именно Вы имеете ввиду.
Если целевая функция есть прямая, то имея два замера, точно знаем, что К=1 с отклонением ноль? K>Далее. Понятно, что с ростом M минимальные отклонения будут убывать. Причем вначале быстро, а потом все медленнее и медленнее.
На практике такие знания силно не помогут. Отклонение(ошибку) на заданной выборке можно всегда свести к нулю, и это задача интерполяции, что совсем не означает, что что найдена оптимальная опроксимация, при этом общее среднее отклонение может сильно разойтись.
Конечно ошибка модели зависит от кол-ва интервалов(частей), но еще зависит от презентативности самой выборки замеров на инревале и выборке самих интервалов. Делать замеры с постоянным временным интервалом можно только для монотонных функций(на практике их очень мало) или в случае, когда нет никаких предположений о характере функции. В свою очередь задача о выборе инревалов, тоже требует информации о характере целевой функции. Что касается полинмов, на практике не используются полиномы порядка больше К=8, т.к. они очень осцилируют на концах. Чаще всего используются полиномы первого, второго и третего порядка, а также их линейные комбинации(смеси), опять же, в зависимости от характера опроксимируемой функции.
Если характер целевой функции не известн, может стоит отказаться от интервелов и полиномов, и посмотреть в сторону нейринных сетей или генетических алгоритнаов. Есть так же множество статистических методов, но большенство из них линеные и предполагают нормальность выборки. K>Вопрос 2: Какие могут быть критерии определения этого оптимума?
Оптимум деления, есть оптимум модели интерполяции.
Самый реаспространееный, так называемый, кросс- валидационный метод.
Замеры(выборка) делятся на два множества: тестовое и, так называмое, обучающее. Модель опроксимации настраевается таким образом, что при уменьшении среднего отклонения на обучающем множестве, среднее отклонение на тестовом множесве тоже должно уменьшаться (в идеале с той же скоростю). Конечное средне отклонение на тестовом множестве можно принять за реальную ошибку модели. Наименьшая ошибка модели, будет оптимум деления,
Если на обучающем нмножестве среднее отклонение уменьшается, а на тестовом расходится, остатется неизменным, или сходится очень медленно, это говорит о том, что модель начала инерполировать.
Но, кажется, Вы хотели наоборот, найти оптимум деления для оптимума опроксимации, а такого критерия нет.
Здравствуйте, kfmn, Вы писали:
K>Всем привет!
K>Вот придумалась такая задачка: K>Есть набор одномерных измерений Xi, взятых через равные интервалы времени. K>Требуется разделить временной отрезок на M частей и аппроксимировать данные Xi на каждой из частей полиномом степени не выше K, таким образом, чтобы минимизировать отклонения этой кусочно-полиномиальной аппроксимации от Xi по какой-нибудь разумной норме.
K>Вопрос 1: решается ли эта задача аналитически хотя бы для каких-нибудь степеней и норм? Поделитесь ссылочками по теме.
K>Далее. Понятно, что с ростом M минимальные отклонения будут убывать. Причем вначале быстро, а потом все медленнее и медленнее. K>К примеру, если данные состоят из 5 квазиполиномиальных участков с разными параметрами, то M=5 будет в каком-то смысле оптимальным, дальше пойдет уточнение на участках.
K>Вопрос 2: Какие могут быть критерии определения этого оптимума?
K>Интерес пока что чисто академический, хотя понятно, что приложений у такой теории должно быть достаточно. Например, сегментация сильно нестационарных сигналов (скажем, речь) на квазистационарные участки (в случае речи — фонемы или их части).
аналитически есть ответ, если я правильно понимаю, только если точки X_i вы можете выбирать самостоятельно (чебышевские сетки). Да и то, степень нужно будет выбирать заранее. а вообще это огромная тема, много где описанная. Почитать можно например здесь: www.inm.ras.ru/library/Tyrtyshnikov/mna.pdf (кстати, это единственный хороший современный курс на русском языке который я видел, очень рекомендуб)
M>аналитически есть ответ, если я правильно понимаю, только если точки X_i вы можете выбирать самостоятельно (чебышевские сетки). Да и то, степень нужно будет выбирать заранее. а вообще это огромная тема, много где описанная. Почитать можно например здесь: www.inm.ras.ru/library/Tyrtyshnikov/mna.pdf (кстати, это единственный хороший современный курс на русском языке который я видел, очень рекомендуб)
Спасибо за ссылку, почитаю.
Но все-таки у меня сложилось впечатление, что меня не совсем верно поняли. Чтобы было понятнее — несколько частных формулировок.
Есть 100 измерений через 1 секунду, всего 100 секунд. Надо разбить этот отрезок на 5 частей таким образом, чтобы кусочно-постоянная аппроксимация, состоящая из 5 кусков, наименее отклонялась от измерений, т.е. чтобы максимальное отклонение было наименьшим. Вопрос — как выбирать 4 точки для разбиения.
Или задача та же, но частей должно быть 10, аппроксимация кусочно-квадратичная из 10 кусков, и мера приближения — максимальное из средних отклонений на всех 10 участках. И вопрос — как выбрать 9 точек.
Т.е. степень — фиксирована, число участков — фиксировано, мера приближения — тоже фиксирована. Мера приближения выражается, как функция от границ участков и оптимизируется по ним. И под возможностью аналитического значения я понимаю возможность точной аналитической оптимизации этой функции.
