Precisión y rendimiento de la distancia euclidiana

Question

La fórmula habitual de la distancia euclidiana que todo el mundo utiliza es

$$d(x,y):=\sqrt{\sum (x_i - y_i)^2}$$

Ahora bien, por lo que sé, las sumas de cuadrados suelen venir con algunos problemas en cuanto a la precisión numérica.

Existe una fórmula obviamente equivalente:

$$d(x,y):= c \sqrt{\sum \left(\frac{x_i - y_i}{c}\right)^2}$$

Donde parece ser una práctica común elegir $c = \max_i |x_i - y_i|$ .

Para 2d, esto se simplifica a una fórmula de la forma $d(x,y):= c \sqrt{1 + \frac{b}{c}^2}$

Algunas preguntas aquí:

1. ¿Cuál es la ganancia de precisión al hacer esto, en particular para las altas dimensionalidades?
2. ¿Cuánto incrementa los costes de computación?
3. ¿Es esta elección de $c$ ¿Optima?

4. Para calcular $c$ Esto requiere dos pases sobre los datos. Sin embargo, debería ser posible en una sola pasada, empezando por $c_0=1$ y ajustarlo cuando sea necesario para obtener una precisión óptima.

   Por ejemplo, dejemos $c_0=1$ , $c_i=\max_{j\leq i} |x_i-y_i|$ . Entonces $$S_i:=\sum_{j\leq i} \left(\frac{x_i - y_i}{c_i}\right)^2 = \sum_{j\leq i-1} \left(\frac{x_i - y_i}{c_{i-1}}\right)^2 \cdot \frac{c_{i-1}^2}{c_i^2}+\left(\frac{x_i - y_i}{c_i}\right)^2 = S_{i-1} \cdot \left(\frac{c_{i-1}}{c_i}\right)^2+\left(\frac{x_i - y_i}{c_i}\right)^2$$ Esto debería permitir el cálculo en una sola pasada de esta fórmula, ¿verdad?

¿Algún comentario en particular sobre el coste computacional y las ventajas de precisión de calcular la distancia euclidiana de esta manera? ¿Por qué todo el mundo utiliza la forma ingenua, es la ganancia de precisión demasiado pequeña para la baja dimensionalidad y el coste computacional asociado demasiado alto?

P.D. Al menos a mi entender, la fórmula habitual debería ser precisa hasta el rango de valores de sqrt(Double.MAX_VALUE) a sqrt(Double.MIN_NORMAL) que cubre alrededor de e+-154 como máximo dividido por la dimensionalidad - así que incluso para 1000 dimensiones, eso debería estar bien para la mayoría de los usos de una función de distancia ...

Answer 1

No soy un experto en números, pero la única ventaja que puedes obtener del reescalado es evitar el desbordamiento/desbordamiento aritmético si los valores de entrada son extremos. Si la fórmula directa puede ser evaluada sin desbordamiento o subdesbordamiento, no es menos precisa que tu fórmula embellecida.

En particular, si (a) estás haciendo la aritmética en doble precisión, (b) sabes que el resultado verdadero no puede ser mayor que un googol, y (c) estás dispuesto a que el resultado sea demasiado pequeño cuando el resultado verdadero es menor que un googol, entonces molestarse en reescalar no le reportará ningún beneficio.

Las bibliotecas de propósito general no suelen poder permitirse los dos últimos supuestos, por lo que sí necesitan reescalar. Por otro lado, una situación en la que se garantiza que estas suposiciones son ciertas es si las coordenadas de entrada se dan como solo flotantes de precisión (que no pueden representar ni googol ni googolth).

Si se reescala, asegúrese de elegir un $c$ que sea una potencia de 2; entonces las operaciones de escalado pueden hacerse sin error de redondeo (y posiblemente más rápido, si se implementa con, digamos, ldexp() en C).

Answer 2

Estoy usando la forma ingenua, y he encontrado que la pérdida de precisión es significativa para distancias pequeñas (como entre los puntos (1,8) y (16,3)) por ejemplo. El error es muy significativo, prueba por ti mismo.