Сравнение двух кривых (функций). Поиск меры сравнения

[Алексей К.]

artful7 в сообщении #155714 писал(а):

Поделитесь соображениями.

Да простейшие. Например, насколько моя (рациональная) аппроксимация спирали Корню отличается от истинной спирали? Ну, оценивал глазками, этого хватало.
Практическая задача --- насколько аппроксимация окружности с помощью кубической кривой Безье отличается от окружности? (PostScript в известной мне реализации разбивает полную окружность на 4 кривые Безье). Решается легко.

Добавлено спустя 5 минут 57 секунд:

STilda писал(а):

дальше берем нашу кривую зависящую от параметров,

Да что за кривую, "зависящую от параметров", все здесь берут? Логарифмическую спиральку? Пеану? Безью? Пендикатрису фигоиды?

[artful7]

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

Да что за кривую, "зависящую от параметров", все здесь берут? Логарифмическую спиральку? Пеану? Безью? Пендикатрису фигоиды?

Сплайны второй и третьей степени, имещие различное количество сегментов.

[artful7]

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


Мне тут подумалось, что на вопрос сравнения двух кривых можно посмотреть с другой стороны: давайте пока отложим в сторону понятие "гибкости" двух кривых и сравним две кривые с точки зрения теории информации, а конкретно - в качестве меры их сравнения возьмем энтропию.
Я тут дернул определение энтропии (ru.science.wikia.com):
В теории информации, энтропия Шеннона, или информационная энтропия — мера неопределённости, связанной со случайной величиной (с.в.); определяет количество информации, содержавшейся в сообщении (обычно в битах или битах на символ); минимальная длина сообщения, необходимая для передачи информации; также абсолютный предел наиболее возможного сжатия без потерь любого сообщения: при представлении сообщения рядом символов, кратчайшее представление, необходимое для передачи сообщения — это энтропия Шеннона в битах на символ, умноженная на число символов в исходном сообщении.

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

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

[worm2]

Что-то у меня не вырисовывается.
Возьмём 3 кривые: $y=0$, $y=3$, $y=\pi$.
С точки зрения теории информации, видимо, у первой кривой энтропия меньше всех, у второй — средняя, у третьей — гораздо больше, т.к. чтобы определить число 0 нужно меньше действий, чем чтобы определить 3, а чтобы определить $\pi$, нужно гораздо больше действий (это всё, разумеется, неформально, по уму здесь какую-нибудь машину Тьюринга нужно определять, но, думаю, что для рассуждения сойдёт).
В этом смысле вторая кривая гораздо ближе к первой, чем к третьей, несмотря на то, что геометрически гораздо ближе к третьей. И какой тогда смысл сравнивать энтропии?
Кстати, может получиться и так, что у двух совершенно разных кривых энтропии одинаковы.

[artful7]

worm2 в сообщении #337898 писал(а):

С точки зрения теории информации ...

А как Вы подсчитали их энтропию?



-- Чт июл 08, 2010 11:55:18 --

worm2 в сообщении #337898 писал(а):

Возьмём 3 кривые: $y=0$, $y=3$, $y=\pi$.

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

[worm2]

artful7 писал(а):

А как Вы подсчитали их энтропию?

Я прикидывал сложность по Колмогорову. Минимальная программа для Машины Тьюринга (МТ), вычисляющая число 2, будет короче (не длиннее), чем минимальная программа для МТ, вычисляющая число (МПМТВЧ) 3. А МПМТВЧ $\pi$ (ну, вообще, стандартная МТ работает с целыми числами, но пусть это будет 2 программы для вычисления числителя и знаменателя, потребуем для $\pi$ точности 0.1%) будет явно длиннее. Поэтому энтропия числя $\pi$ в каком-то смысле больше, чем энтропия числа 3.

Но Вы можете по-своему оценивать энтропию.

artful7 писал(а):

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

Пусть будет так, энтропия у этих функций одинакова. Считать ли их на этом основании "равными"? А такие функции, как, скажем, $x^2$ и $x^3$ — тоже считать "равными" ?

[artful7]

worm2 в сообщении #337918 писал(а):

Минимальная программа для Машины Тьюринга (МТ), вычисляющая число 2, будет короче (не длиннее), чем минимальная программа для МТ, вычисляющая число (МПМТВЧ) 3. А МПМТВЧ $\pi$ (ну, вообще, стандартная МТ работает с целыми числами, но пусть это будет 2 программы для вычисления числителя и знаменателя, потребуем для $\pi$ точности 0.1%) будет явно длиннее. Поэтому энтропия числя $\pi$ в каком-то смысле больше, чем энтропия числа 3.

Информация, по Шеннону, — это лишь одна из характеристик того, как устроен объект (или сообщение, если быть точным), а вовсе не его смыслового содержания объекта, функции (или того, «о чем» повествует сообщение).

worm2 в сообщении #337918 писал(а):

Считать ли их на этом основании "равными"?

Да, с точки зрения сложности своей структуры (а не сложности процесса ее получения) -одинаковы, ибо константы.

worm2 в сообщении #337918 писал(а):

А такие функции, как, скажем, $x^2$ и $x^3$ — тоже считать "равными" ?

Как раз - и нет! Поскольку сложность их структуры - различна (квадратическая и кубическая функции).


Кстати, во всем этом что-то общее есть с колмогоровской сложностью.

[worm2]

artful7 писал(а):

worm2 писал(а):

А такие функции, как, скажем, $x^2$ и $x^3$ — тоже считать "равными" ?

Как раз - и нет! Поскольку сложность их структуры - различна (квадратическая и кубическая функции).

Ну хорошо! Но уж $x^3+x$ и $x^3-x$ — одинаковые?

-- Чт июл 08, 2010 22:45:48 --

Может, вы интересуетесь классификацией кривых? Тогда кое-что уже классифицировано. Есть алгебраические кривые $n$-го порядка и остальные Среди остальных про такую же стройную классификацию не знаю, но есть всякие мелкие.

[artful7]

worm2 в сообщении #338026 писал(а):

Но уж $x^3+x$ и $x^3-x$ — одинаковые?

Выходит, у вас - два мужа?
Выходит, ... два... © Из известного фильма :)

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


Здесь вот какое дело.
Пусть у нас имеются две кривые, графически точно сопоставленные друг с другом: парабола и кривая Безье 2-й степени (составная, если необходимо для более точного сопоставления). Если мы сравним кратчайшую программу, которая вычисляет значения функции $x^2$ и кратчайшую программу, вычисляющую значения квадратического сплайна, то очевидно, что вторая программа - будет длиннее.
С другой стороны, график параболы можно точно провести через три точки, т.е. интерполировать параболой три точки. А вот с составной кривой Безье (второго порядка) уже можно интерполировать большее количество точек. Хотя порядок выражений параболы и составной кривой Безье - остается одинаковым ($n=2$).

Теперь, если сравнить между собой две составные кривые Безье одинаковой степени, но с различным количеством составных сегментов, то при одинаковом порядке их выражений ($n=2$), их характеристические кривые обязательно будут отличаться своими интерполяционными способностями. Иными словами, если прохождение кривой через точку с заданными координатами связать с формализацией (представлением) нескольких бит информации, то "информационная емкость" второй составной кривой будет выше, чем первой. Значит, энтропия этих двух кривых тоже будет разной (у второй кривой мера неопределенности будет меньшей за счет бОльшего количества информации, представленной или "запомненной" посредством изменения внутренней структуры её аналитического выражения).

Вопрос мой в том, как вычислить эту информационную емкость?

[artful7]

Цитата:

Вопрос мой в том, как вычислить эту информационную емкость?

Проще говоря, сколько бит информации можно запомнить (формализовать, закодировать) при помощи составной кривой, проходящей через $n$ точек.

-- Пт июл 09, 2010 13:43:07 --

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

-- Пт июл 09, 2010 13:50:48 --

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

[worm2]

За безнадёжное дело, имхо, Вы взялись.
Во-первых, поскольку множество целых чисел бесконечно, существует бесконечное количество кривых $y=a$, где $a\in\mathbb{Z}$, а значит, каждая такая кривая содержит бесконечное количество бит информации (это если считать, что любые 2 такие кривые несут одинаковое количество информации; иначе придётся сказать, что информации больше несут те кривые, у которых $|a|$ больше, но зато каждая конкретная кривая $y=a$ будет нести конечное число бит).
Во-вторых, то, что кривая проходит через $n$ точек и вследствие этого может нести какую-то информацию, является свойством не кривой, а класса, к которой эта кривая принадлежит. Например, можно сказать, что кривая $y=x^2$ проходит через одну заданную точку, а можно сказать, что через сто (если сто точек заданы таким образом, что лежат на этой параболе), или через бесконечное число. А вот класс кривых $\{y=ax^3+bx^2+cx+d\}$ (все коэффициенты вещественны) уже обладает формализуемым свойством: для любых 4 точек с разными абсциссами найдётся единственная кривая из этого класса, проходящая через них. Кривую $y=x^2$ можно рассматривать как элемент этого класса, но можно рассматривать и как элемент другого класса $\{y=ax^2+bx+c\}$, так что однозначно приписать кривой количество информации на этом пути не получается. Рассматривая функцию вне классов, можно определить для неё количество информации по Колмогорову или как-нибудь ещё, но тут уже не приходится говорить о "числе точек, через которые она проходит" (кривые $y=x^2$ и $y=\pi x^2$, насколько я могу вообразить разные смыслы, придаваемые этому утверждению, "проходят через одно и то же число точек").

artful7 писал(а):

сколько бит информации можно запомнить (формализовать, закодировать) при помощи составной кривой, проходящей через $n$ точек.

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

[artful7]

Да, задачка...

[artful7]

Обсуждение перенесено в раздел "Computer Science": http://dxdy.ru/topic35148.html.

[PAV]

Тема закрыта в связи с переездом вопроса в другой раздел