Квази-изометрия из пространства с полуметрикой

[Centimo]

Здравствуйте.
Возник следующий вопрос:
Пусть у нас есть пространство с заданными на нём еквлидовой метрикой и отношением эквивалентности. Возможно ли построить такое отображение элементов этого пространства в другое метрическое пространство (произвольной размерности), чтобы:
1) расстояние между двумя образами в новом пространстве можно было вычислить на основании расстояния между прообразами;
2) по расстоянию между двумя образами можно было бы определить относятся ли они к одному классу эквивалентности.

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

Я предполагаю, что ответ звучит примерно следующим образом: "да, теоретически это возможно, но как это сделать - ищи сам". Собственно, прошу поделиться мыслями, ссылками, литературой, пинками...

[arseniiv]

(А можно поинтересоваться исходной задачей, если она есть? Уж больно похоже на XY problem.)

-- Чт июн 28, 2018 21:04:39 --

И ещё дополнительно: получается, отношение эквивалентности никак-никак не связано с евклидовой метрикой? Или какие-то хитрые связи есть?

[Centimo]

arseniiv в сообщении #1323197 писал(а):

(А можно поинтересоваться исходной задачей, если она есть? Уж больно похоже на XY problem.)

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

arseniiv в сообщении #1323197 писал(а):

И ещё дополнительно: получается, отношение эквивалентности никак-никак не связано с евклидовой метрикой? Или какие-то хитрые связи есть?

Если я правильно понял Ваш посыл, то прямых связей нет. Т. е. связи наверное есть, но они не заданы мной и мне неизвестны.

[arseniiv]

Ясно. Ну, лично у меня идей тогда нет. В общей постановке вообще выходит абстрактная задача классификации, а её решают по-разному в зависимости от природы объектов. И даже для формул стоит знать, как они потом используются, это бы дало сделать какой-то выбор (того представления их точками некоторого $\mathbb E^n$, о котором вы говорите).

-- Пт июн 29, 2018 00:33:39 --

Вообще идея запихивать классифицируемое пространство образов подмногообразием в $\mathbb E^n$ не нова, но я по вашему описанию не сразу понял, что это на самом деле она. Хотя тень оставляет не очень связанное с метрикой отношение эквивалентности — так зачем тогда вообще говорить о метрике, кстати. Если предположить, что всё-таки расстояния между классами обычно больше, чем среди элементов класса, получится обычная задача. Если нет, то я по-прежнему не понимаю, и пусть другие пробуют.

[Centimo]

arseniiv в сообщении #1323235 писал(а):

Ясно. Ну, лично у меня идей тогда нет. В общей постановке вообще выходит абстрактная задача классификации, а её решают по-разному в зависимости от природы объектов. И даже для формул стоит знать, как они потом используются, это бы дало сделать какой-то выбор (того представления их точками некоторого $\mathbb E^n$, о котором вы говорите).

Ну идея как раз о том, как определять эквивалентность произвольных формул, а не каких-то конкретных, связанных с какой-то задачей.

arseniiv в сообщении #1323235 писал(а):

Вообще идея запихивать классифицируемое пространство образов подмногообразием в $\mathbb E^n$ не нова, но я по вашему описанию не сразу понял, что это на самом деле она. Хотя тень оставляет не очень связанное с метрикой отношение эквивалентности — так зачем тогда вообще говорить о метрике, кстати. Если предположить, что всё-таки расстояния между классами обычно больше, чем среди элементов класса, получится обычная задача. Если нет, то я по-прежнему не понимаю, и пусть другие пробуют.

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

[arseniiv]

Да, если нужно бесконечное число классов, это точно ого-го.

Centimo в сообщении #1323236 писал(а):

Ну идея как раз о том, как определять эквивалентность произвольных формул, а не каких-то конкретных, связанных с какой-то задачей.

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

[Centimo]

arseniiv в сообщении #1323237 писал(а):

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

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

[arseniiv]

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

Кстати, а для чего пришлось сравнивать выражения, ещё и с точностью (ещё и таким предполагаемым способом)?

[Centimo]

arseniiv в сообщении #1323379 писал(а):

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

А откуда "неразрешимость"? Есть какие-то теоретические основания, или же потому что "не может быть так хорошо"?

arseniiv в сообщении #1323379 писал(а):

Кстати, а для чего пришлось сравнивать выражения, ещё и с точностью (ещё и таким предполагаемым способом)?

Ни для чего. Это и есть задача, которая пришла в голову пока думал над другим.

[arseniiv]

Centimo в сообщении #1323453 писал(а):

А откуда "неразрешимость"? Есть какие-то теоретические основания, или же потому что "не может быть так хорошо"?

Я знаю как минимум про один набор: арифметические операции, рациональные константы и взятие модуля и переменная (кажется, так — пока не помню где искать надо), и тогда тождественное равенство нулю неразрешимо (а с ним и просто равенство, ибо $f\equiv g\Leftrightarrow f-g\equiv0$). Разумно предполагать, что сколь-нибудь сложный набор (в частности, любой, в котором выразим этот — даже если я ошибся в его точном составе, он примерно такой же простой) будет страдать не меньше.

Centimo в сообщении #1323453 писал(а):

Ни для чего. Это и есть задача, которая пришла в голову пока думал над другим.

Понятно.