Математика: как померить линейность функции заданной на кольце

>Да, до чего средства телепатии дошли.. Или телепаты вышли из отпуска. Чудеса да и только! :-)

Хорошо, пусть это будет мой вопрос (без ссылки на телепатию)

> Хорошо, пусть это будет мой вопрос (без ссылки на телепатию)
Почему? Я вовсе не против ;-)

2unDEFER:

>> Фабрика выпускает карандаши длиной 10, 20 и 30 сантиметра. Причем, 99% карандашей, выпущенных фабрикой, имеют длину 10 см, и по 0.5% процента -- остальные.

>Ну, типа это уже не функция :-)

Значит, я вообще ничего не понял...

Длина карандаша -- случайная функция, принимающая значения 10, 20 и 30. Матожидание вычисляем, как толстый доктор прописал, 99/100*10cm + 0.5/100*20cm + 0.5/100*30cm = 10.15cm

> Хм.. цитата получена не методом copy-paste... Я такого не писал! Там написано: "мат.ожиданием этого _случайного_ процесса" ;-)

Да, тут я подзапутался маленько... Но это ж надо было постараться так ключевое слово спрятать! Райкин вспоминается: "Я забрасываю снасть в воду, и этот динамит взрывается!"

Сравниваем с: "Возьмём эргодический стационарный дискретный процесс (т.е. последовательность), и его реализацию f(n). Тогда мат.ожиданием этого случайного процесса будет среднее арифметическое всех значений f(n)".

>> 2. Что такое "все значения f(n)"? (см. пример выше).

> А чтобы пример выше не работал сказано, что случайный процесс -- эргодический.

Как эргодичность связана с допустимым множеством исходов?

> ...я бы очень хотел узнать что мне надо бы ещё переформулировать чтобы получить этот ответ..

Сформулировать вопрос по-человечески! Мне сильно сдается, что в процессе формулировки ответ сам собой получится... Как я понял, проблема в том, что после нелинейного преобразования линейная функция перестает быть линейной (кто б мог подумать! :)) Видимо, надо соответствующие операции перевести из полярных координат в декартовы, а потом результат -- обратно (если понадобится дальше с ним возиться). Впрочем, я особо не вникал. Как-то неохота гаданием заниматься :)

> Как эргодичность связана с допустимым множеством исходов?
Она связана с тем что там не будет "99% карандашей". Т.е. будут, но для эргодического процесса берётся интеграл типа 1/T \int_0^T f(t) dt -- т.е. плотности распределения или вероятности уже не учитываются. Потому, как там в этой реализации уже как надо распределено...

> Сформулировать вопрос по-человечески!
А что насчёт формулировки ival'а?

> Как я понял, проблема в том, что после нелинейного преобразования линейная функция перестает быть линейной (кто б мог подумать! :))

Это было бы смешно, если б не было так грустно. Если для фазы значение \phi от \phi+n*2*pi не различимы, но функцию a*x всё ещё хочется считать линейной..

2unDEFER:

>> Как эргодичность связана с допустимым множеством исходов?

> Она связана с тем что там не будет "99% карандашей". Т.е. будут, но для эргодического процесса берётся интеграл типа 1/T \int_0^T f(t) dt -- т.е. плотности распределения или вероятности уже не учитываются. Потому, как там в этой реализации уже как надо распределено...

Ниасилил ...

Уверяю, описанный мною процесс совершенно эргодичен. И плотности с верояностями в эргодических процессах совершенно учитываются. И матожидание вычислено верно.

Эргодичность означает, что среднее по выборке совпадает со средним по ансамблю. В терминах графов состояний дискретных Марковских процессов это означает, что

1. Граф связан, т. е. нет нескольких несвязанных компонент.

2. Длины замкнутых циклов взаимно просты, т. е. отсутствует периодичность в компонентах.

Выюорка карандашей вообще не коррелирована, т. ч. процесс заведомо эргодичен.

>> Сформулировать вопрос по-человечески!

> А что насчёт формулировки ival'а?

Чуть понятнее, но все равно ниасилил. Наверное, туп, извиняюсь...

Чё, корреляция в полярных координатах не жывёт чтоли?

> Уверяю, описанный мною процесс совершенно эргодичен.

Верю, но если взять одну единственную его реализацию, то там уже будет всё как
надо распределено, там уже будет 99% карандешей нужной длины, и в формуле
"среднего по выборке", плотность распределения не участвует:
   T
  /
1 [
- I  f(t) dt
T ]
  /
   0

Тут есть только сама реализация.

> Чуть понятнее, но все равно ниасилил.
Жаль..
А меня между тем формулировка ival всё же натолкнула на мысль:
надо попробовать определять a и b так как я это сейчас делаю (я всего лишь
складываю несколько разниц углов функции двигаясь по оси X и делю её на
подобную разницу функции f(x)=x -- так получается a), а корреляцию считать
уже с функцией ax+by...

Живёт, но не так как нам нужно :-)

>> А что насчёт формулировки ival'а?

>Чуть понятнее, но все равно ниасилил. Наверное, туп, извиняюсь...

Что за издевка.

Дано:

таблица значений функции

h(k1,k2) = exp (-2*pi*sqrt(-1)*(k1*u/N+k2*v/M)

k1,k2 - натуральные числа 0<=k1<N 0<=k2<M

N,M - известные числа

Найти: u,v

>> Чуть понятнее, но все равно ниасилил. Наверное, туп, извиняюсь...
> Что за издевка.

Я думаю Die-Hard просто не заинтересован.

Странно, а как вам нужно? Корреляция есмь грубо говоря сумма расстояние в от каждой из множества точек до заданной линии, кривой или прямой. Если совокупность точек дана и линия определена, всё остальное должно быть как два бита абассать.

>Странно, а как вам нужно? Корреляция есмь грубо говоря сумма расстояние в от каждой из множества точек до заданной линии, кривой или прямой. Если совокупность точек дана и линия определена, всё остальное должно быть как два бита абассать.

Там фишка в том, что у него отображения (Z/NZ)x(Z/MZ)->U(1)

Я сначала хотел взять евклидовое расстояние на U(1) с плоскости, сказать, чтобы параметры бегали по тору и забацать метод минимальных квадратов. Только там уравнение получилось сложное, я его ниасилил.

На мой делитанский вгляд намного проще за расстояния между функцими взять супремум модуля разности значений функции по всей группе. В этом случае FFT будет равномерно непрерырным (как линейное отображение в конечномерном векторном пространстве). И оценивать будет просто:

Норма от FFT(f) не больше чем норма f умноженной на константу (супремум норм характеров)

> Корреляция есмь грубо говоря сумма расстояние в от каждой из множества точек до заданной линии, кривой или прямой.

Что-то вы тут совсем напустали: "сумма расстояние", "в от"...

А проблема в том, что если функция a*x линейна, то она коррелирует с функцией x на множестве вещественных чисел.

Но когда функция a*x -- это функция угла, и угол изменяется от -pi до pi, то функция a*x превращается в "пилу" с периодом скажем T, а функция x -- в "пилу" с периодом a*T. Но эти "пилы" не коррелируют!

Может быть имеет смысл поискать какую-нить меру периодичности...

Ну почему Вы не пользуетесь услугами телепатов?

если есть функция угла r (phi) то она задана в полярных координатах. Если ты хош произвести корреляцию с например прямой y = ax+b, те нужно поместить их обеих в одинаковые координаты, а прямая задана на декартовых. Если они обе не будут заданы в одних и тех же, расстояние вычислять безсмысленно. Переводи либо прямую в полярные координаты, либо полярную функцию в декартовое. Если первое - уравнение прямой в полярных будет r=b/(sin(phi) - a*cos (phi)) а квадрат расстояние между (r1, phi1), (r2, phi2): r^2 = r1^2 + r2^2 - 2*r1*r2*(sin(phi1)*sin(phi2) + cos(phi1)*cos(phi2)) , может можно как-то упростить, я нестал заморачиваться. Если те нужно просто проверить, что зависимоть r от угла линейна, т.е. имеет вид r=a*phi+b и найти коэффициенты, тогда вообще не заморачиаешся, просто ограничиваеш облась корреляции промежутком (-pi, pi).

телепаты ещё не все отпускные истратили.

Когда я начал писать то сообщение, вашего ещё не было.

> Если те нужно просто проверить, что зависимоть r от угла линейна, т.е. имеет вид r=a*phi+b и найти коэффициенты, тогда вообще не заморачиаешся, просто ограничиваеш облась корреляции промежутком (-pi, pi).

У меня не зависимость r от phi и не наоборот -- у меня зависимость phi от (x,y).
Т.е. функция phi(x,y) -- она сама угол.
И нужно каким-то образом измерить её линейность, т.е. соответствие формуле
phi(x,y) = a*x + b*y.

Проблема в том, что линейность для такой функции теряется из-за ограниченности (верней закольцованности, зацикленности) области_значений, а не области определения.

Аха, теперь и до мя дошло... Попробуй производить корреляцию не с самой ax+by а брать от этой модуль по pi : (defun mod-pi (x) (if (< (abs x) PI) x (mod-pi (- x (* PI (signum x))))))

> Попробуй производить корреляцию не с самой ax+by а брать от этой модуль по pi

Да в том то и дело, что корреляцию надо бы брать с x+y..
И фигня в том, что две "пилы" с разной частотой коррелируют очень слабо.

> Да в том то и дело, что корреляцию надо бы брать с x+y..

Почему так? В лучшем случае это возможно если только один зубец пилы взять.

> И фигня в том, что две "пилы" с разной частотой коррелируют очень слабо.

Ещё бы! Они и должны. Предложенное в предыдущем моём посту, функция будет иметь вид пилы тоже, её частота зависит от коэффициентов а и b. Совпадение частот и будет означать что двои данные кореллируют с функцией с этими коэффициентами, т.е. частота и угл наклона совпадают только одновременно. Ещё, может быть потребен третий, f=ax*by+c.

2unDEFER:

>> Уверяю, описанный мною процесс совершенно эргодичен.

> Верю, но если взять одну единственную его реализацию, то там уже будет сё как надо распределено, там уже будет 99% карандешей нужной длины, и в формуле "среднего по выборке", плотность распределения не участвует:

Вообще ни слова не понял!

Наверное, мы, все же, на разных языках говорим...

Извиняюсь, но за 20 лет активной научной деятельности я ни разу не сталкивался с подобными проблемами.

Попробуйте понять меня правильно.

Я слышу некие термины, каждый из которых мне понятен. Но уже рамдонное сочетание меня слегка вводит в ступор... А в ответ на вопросы я слышу ИМЕННО стохастику...

Попытки намекнуть на то, что определения должны быть ХОТЯ БЫ строгими, вызывает недоумение...

Ну, извините...

Вам есть о чем поговорить, так что ж -- общайтесь! Я сюда больше не захожу (в смысле, как оппонент. Если правила нарушать начнете -- удалю, как модеротор)...

Cheers, D.-H.

> Вообще ни слова не понял!
:-) :-/ :-{

Я ж говорю, вы скорее просто не заинтересованы.
Вот, ival заинтересовался и потому проявляет чудеса телепатии ;-)

> Ещё бы! Они и должны. Предложенное в предыдущем моём посту, функция будет иметь вид пилы тоже, её частота зависит от коэффициентов а и b. Совпадение частот и будет означать что двои данные кореллируют с функцией с этими коэффициентами, т.е. частота и угл наклона совпадают только одновременно.

То-то и оно что нужно независимо от частоты/наклона считать такую функцию "линейной" (или псевдо-линейной не знаю как это назвать, но главное что любая такая "пила" получается из функции a*x + b*y взятой по модулю pi) и получать коэффициент корреляции 1.
А вот, если там уже какие-то нелинейные отклонения от этой пилы есть, то корреляция д.б. <1.

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

Прошу прощения, крайне неудачно выразился:

> Вам есть о чем поговорить, так что ж -- общайтесь! Я сюда больше не захожу (в смысле, как оппонент. Если правила нарушать начнете -- удалю, как модеротор)...

Если кто обиделся -- я извиняюсь.

Я просто имел в виду, что я не отлыниваю от обязанностей... :)

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

Модеротор это сильно! А кто будет модестатор?

> Впрочем, все оставшиеся активными, думается, поняли меня правильно.
Да, да ;-)

> Ну всё правильно, если в точности одинакова пиле, максимум будет 1,

Правильно, но не так как нужно!
Нужно для _любой_ "пилы" иметь этот максимум 1!
А если эта пила отличается не только периодом то только тогда меньше.

Ты чёто сильно путаеш ИМХО. Суть корреляции в том, что для набора данных ты предлагаеш параметризованную модель, например пилу, параметризованную a и b. 1 ты получиш только если существуют такие параметры a и b, при которых твои данные в точности соответствуют модели. Если нет, 1 ты не получиш. В данной задаче при ограничении по модулю pi, ты получиш 1 если период совпадёт, т.к. при этом должен совпасть обязательно и наклон, они взаимосвязаты. Можно причинить преобразование, при котором пила с другим наклоном будет иметь одинаковый период или соответственно наоборот, но тогда заведомо не получиш 1, т.к. зависимось наклона пилы от периода будет иная чем предполагаемая для данных. Если чёто идёт не так - подумай о соответствии предполагаемой модели.

> Суть корреляции в том, что для набора данных ты предлагаеш параметризованную модель, например пилу, параметризованную a и b.

Суть корреляции в том, что для функции f(x) полностью коррелированной с ней будет признана лишь функция вида g(x)=a*f(x);
Если при этом f(x,y)=x+y то коррелированной с ней будут лишь функции вида a*x+b*y. Таким образом мы можем использовать корреляцию (с функцией x+y) как меру линейности, но лишь в области вещесвенных чисел.

Только из-за того, что значения функции g(x,y) берутся по модулю pi, я не могу воспользовать корреляцией как мерой её линейности.
Вопрос заключается именно в том, какой бы ещё такой хитрый коэффициент посчитать, чтобы я мог даже для функции g(x,y) со значениями взятыми по модулю pi померить её соответсвие форме a*x+b*y (также взятой по модулю pi).

> Суть корреляции в том, что для функции f(x) полностью коррелированной с ней будет признана лишь функция вида g(x)=a*f(x); Если при этом f(x,y)=x+y то коррелированной с ней будут лишь функции вида a*x+b*y.

не, не так. Для набора данных (x, y)_i предлагаеш модельную функцию y=f(x,p), где р - набор параметров. Корреляция проверяет, насколько твой набор данных соответствует модели при данном наборе параметров р. Например, есть набор значений (0, 1), (1, 0.6), (2, -0.1). Ты предполагаеш что он соответствует линейной вида y=ax+b, и соответствующим методом ищещ такие a и b при которых твои данные наиболее близко к этой прямой. По коэффициенту видиш, насколько плох наилучший результат, т.е. насколько далеко точки есть от полученной прямой.

> Только из-за того, что значения функции g(x,y) берутся по модулю pi, я не могу воспользовать корреляцией как мерой её линейности.

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

> Вопрос заключается именно в том, какой бы ещё такой хитрый коэффициент посчитать, чтобы я мог даже для функции g(x,y) со значениями взятыми по модулю pi померить её соответсвие форме a*x+b*y (также взятой по модулю pi).

Корреляция - общий метод, лишние коэффициенты бесполезно. Убедись, что существует такие a и b, при которых твои данные полностью ложатся на функцию. Если нету - значит выбрал неладную модель, ищи другое функцию.

Да, вдруг кажется понял что ошибался насчёт корреляции (x+y) и (a*x+b*y). Коррелированы лишь (x+y) и a*(x+y)..
Тогда, да. В общем тогда я так сейчас и делаю -- сначала подбираю a и b, а затем считаю корреляцию. Всё хорошо в общем..

>Вопрос заключается именно в том, какой бы ещё такой хитрый коэффициент посчитать, чтобы я мог даже для функции g(x,y) со значениями взятыми по модулю pi померить её соответсвие форме a*x+b*y (также взятой по модулю pi).

Я все таки попытаюсь еще раз объяснить что я имел ввиду когда говорил, что кажется понял что Вам нужно:

С вычитами можно обращаться как с комплексными числами, т.е. вычиту \phi соответствует комплексное число

exp(sqrt(-1)*\phi)=cos(\phi)+sqrt(-1)*sin(\phi).

А сложению соответствует комплексное умножение.

Далее будем рассматривать дискретные функции. Т.е. вычеты у нас будут по модулям N и M, а g(x,y) мы будем подганять наборами функций

h(k1,k2)=exp(-2pi*sqrt(-1)*(u*k1/N+v*k2/M)

u,v - тоже вычиты по модулям N,M

Чтобы подобрать (u,v) можно вычислить преобразование фурье.

В самом деле: рассмотрим преобразование фурье от h(k1,k2), эта некоторая функция s, причем ее значение в точке (l1,l2) равно:

s(l1,l2)=\sum_{(k1,k2) \in [1..N]x[1..M] h(k1,k2)*exp(-2*pi*(l1*k1/N+l2*k2/M))

заметим, что

h(k1,k2)*exp(-2*pi*(l1*k1/N+l2*k2/M)) =

exp(2pi*sqrt(-1)*(u+l1)/N*k1)*exp(2pi*sqrt(-1)*(v+l2)*k2)

и сама сумма есть произведение двух сумм:

S1 = sum_{k1 \in [1..N]) exp(-2*pi*(u+l1)/N)^k1

S2 = sum_{k2 \in [1..M]) exp(-2*pi*(v+l2)/M)^k2

Если u+l1 = 0 (mod N), то все слагаемые в сумме S1 равны еденице, а она сама равна N, в противном случае это геометрическая прогрессия, сумма которой равна 0

Аналогично S2 = M если v+l2=0 (mod N) и нулю во всех остальных случаях,

Получаем, что s - эта фуркция равная N*M в точке (-u,-v) и нулю в остальных случаях.

Таким образом чтобы подобрать (u,v) - нужно просто вычислить преобразование фурье от g и найти максимум.

В качестве оценки близости функций можно взять максимальный модуль разности значений по всем (l1,l2). При фурье преобразование если исходные функции были на расстоянии r, то из образы будут на расстояние не более чем С1*r, где С1 - некоторая константа. Аналогичное верно и в другую сторону, но возможно c другой константой C2.

Другими словами за "точноть приближения" можно взять расстояние в описанном выше смысле между образом g и образом h.

> Таким образом чтобы подобрать (u,v) - нужно просто вычислить преобразование фурье от g и найти максимум.

Мм.. Це ж гениально!!!
Оно работает!
Весьма, весело будет получить распознаватель полностью пронизанный преобразованиями Фурье :-)

Фишка вся в том, что я думая о возможном дальнейшем использовании этих результатов пришёл к выводу:
характерный спектр будет иметь не только буквы, но и вся страница целиком (т.е. используя ровно тот же алгоритм можно будет определять наклон страницы), и абзацы, строки и может быть даже отдельные слова.. Надо только правильно обрезать диапазон рассматриваемых частот сверху.

Вообще была идея двигаясь по слову слева направо, рассматривая его через квадратное окошко определённого размера, выполнять преобразование Фурье этого окошка и соответственно распознавать отдельные буквы.
Пока к сожалению попытка взять среднюю часть текста "БАБ" (т.е. чтоб в окошке виднелись части букв Б и А -- полностью) и произвести это преобразование несколько разочаровала -- всё же эти части букв "Б" слишком сильно влияют на спектр этого изображения. Наверное стоит воспользоваться "оконным" преобразованием Фурье..
Так что будем ещё думать..

> Пока к сожалению попытка взять среднюю часть текста "БАБ" (т.е. чтоб в окошке виднелись части букв Б и А -- полностью) и произвести это преобразование несколько разочаровала -- всё же эти части букв "Б" слишком сильно влияют на спектр этого изображения.

Однако, именно определение коэффициентов u, v именно данным способом уже способно правильно определить и масштаб и сдвиг даже в таких условиях.
Всё же вы, ival -- магистр телепатии! :-D