(New page: == Numeric Version of Example Given in Lecture == It's easier for me to follow numerical examples than qualitative, so here is the same example Dr. Boutin gave in lecture of a distance fu...) |
|||
(One intermediate revision by one other user not shown) | |||
Line 1: | Line 1: | ||
+ | =Not all dissimilarity measures satisfy the triangle inequality...= | ||
+ | |||
== Numeric Version of Example Given in Lecture == | == Numeric Version of Example Given in Lecture == | ||
It's easier for me to follow numerical examples than qualitative, | It's easier for me to follow numerical examples than qualitative, | ||
− | so here is the same example Dr. Boutin gave in lecture of a | + | so here is the same example [[User:mboutin|Dr. Boutin]] gave in lecture of a |
distance function for which the triangle inequality fails to | distance function for which the triangle inequality fails to | ||
hold reframed in a numeric context. | hold reframed in a numeric context. | ||
Line 17: | Line 19: | ||
− | Note that the first 3 axioms | + | Note that the first 3 axioms hold. By definition <math>D</math> is |
either 0 or the minimum of the absolute value of non-zero values, hence | either 0 or the minimum of the absolute value of non-zero values, hence | ||
<math>D</math> is non-negative. By symmetry of absolute value, | <math>D</math> is non-negative. By symmetry of absolute value, | ||
Line 38: | Line 40: | ||
--[[User:Jvaught|Jvaught]] 17:29, 25 March 2010 (UTC) | --[[User:Jvaught|Jvaught]] 17:29, 25 March 2010 (UTC) | ||
+ | ---- | ||
+ | [[2010_Spring_ECE_662_mboutin|Back to ECE662 Spring 2010]] |
Latest revision as of 08:29, 2 April 2010
Not all dissimilarity measures satisfy the triangle inequality...
Numeric Version of Example Given in Lecture
It's easier for me to follow numerical examples than qualitative, so here is the same example Dr. Boutin gave in lecture of a distance function for which the triangle inequality fails to hold reframed in a numeric context.
Let a semimetric $ D $ be defined on $ \mathbb{R}^2 $ as $ D:\mathbb{R}^2 \times \mathbb{R}^2 \to \mathbb{R} $ by $ (\vec{x_1}, \vec{x_2}) \mapsto d $ where $ d $ is the minimal magnitude non-zero element of the difference vector $ \vec{x_1} - \vec{x_2} $ if such exists or 0 otherwise.
For example, $ D((1, 7), (-3, 12)) = \min\{|4|, |-5|\} = 4 $.
$ D((1, 7), (1, 12)) = 5 $. $ D((1, 7), (1, 7)) = 0 $.
Note that the first 3 axioms hold. By definition $ D $ is
either 0 or the minimum of the absolute value of non-zero values, hence
$ D $ is non-negative. By symmetry of absolute value,
$ D $ is symmetric. And $ D $ can only be 0 if
the set of non-zero elements of the difference vector is empty,
which implies that the vectors are equal. However, consider the
following counter-example to the triangle inequality (which is the
numerical equivalent of the example given in lecture, where the first
component is the level of detail of the image and the second component
is the subject of the image).
$ \vec{x_1} = (1, 10), \vec{x_2} = (2, 20), \vec{x_3} = (12, 21) $
Then $ D(\vec{x_1}, \vec{x_2}) = 1, D(\vec{x_2}, \vec{x_3}) = 1, D(\vec{x_1}, \vec{x_3}) = 11 $ and $ 1 + 1 < 11 $.
So the triangle inequality doesn't hold and $ D $ is only a semimetric.
--Jvaught 17:29, 25 March 2010 (UTC)