Subscribe RSS

Posts Tagged ‘properties’

Transitivité ou inégalité triangulaire ?

June 10th, 2009 by fmn | 6 Comments | Filed in Research

Translate original post with Google Translate

Dans mon billet d’hier, je mentionnais l’inadéquation de la plupart des illustrations censées montrer comment la similarité visuelle ne vérifie pas l’inégalité triangulaire.

En fait, après réflexion et quelques relectures, je pense que les auteurs font une confusion entre l’inégalité triangulaire et la transitivité. L’inégalité triangulaire fait référence à la notion de plus court chemin. Si m(A, B) est une mesure entre l’objet A et l’objet B, alors l’inégalité triangulaire se traduit par :

m(A,B) + m(B, C) \geq m(A,C) .

En géométrie euclidienne, cela indique qu’il est plus court d’aller du point A au point C en ligne droite que de faire un détour par le point B.

La transitivité est une propriété que peut posséder une relation binaire. Une relation binaire R est transitive si lorsque x et y sont en relation et que y et z sont en relation, alors x et z sont également en relation, plus formellement :

x R y \wedge y R z \Rightarrow x R z .

Par exemple si l’amitié était transitive, les amis de mes amis seraient mes amis.

Ainsi les exemples donnés pour montrer que la similarité visuelle ne vérifie pas l’inégalité triangulaire, montrent plutôt que la similarité visuelle n’est pas transitive : le fait que les images A et B soient similaires et que B et C soient similaires n’impliquent pas que les images A et C sont similaires.

La non-transitivité de la similarité visuelle n’implique en rien la non vérification de l’inégalité triangulaire. En formalisant un peu, si l’image A et l’image B sont similaires, on peut imaginer que la mesure de similarité s entre ces deux images est inférieure à une valeur seuil \alpha donnée :

s(A, B) \leq \alpha .

De même, les images B et C sont similaires :

s(B, C) \leq \alpha .

Si l’on fait la somme des ces deux similarités :

s(A, B) + s(B, C) \leq 2 \alpha .

Les exemples indiquent que les images A et C ne sont pas similaires, donc

\alpha < s(A, C) .

Cette dernière inégalité n’est pas suffisante pour conclure que s(A,B) + s(B, C) \leq s(A, C), il faudrait pour cela que s(A, C) > 2 \alpha. Or on a juste s(A, C) \geq \alpha. Les exemples donnés ne sont donc pas suffisant pour conclure à la non vérification de l’inégalité triangulaire.

On pourrait argumenter sur le fait que je considère ici des cas limites et que si s(A, C) > \alpha, il est “probable” que s(A, C) \geq 2 \alpha, ce qui conduit à ne pas vérifier l’inégalité triangulaire. Soit, mais les exemples donnés sont censés illustrer la non vérification de la propriété et non indiquer que “probablement” elle n’est pas vérifiée.

FMN.

Wikio
Wikio

Tags: , , ,

How to find good examples of triangular inequality for visual similarity?

June 8th, 2009 by fmn | 4 Comments | Filed in Research
Amos Tversky works have shown that human similarity judgement is not a metric (in a mathematic sens). In particular the following properties are not always verified:
  1. Minimality : \delta(a,b) \geq \delta(a, a) = 0.
  2. Symmetry : \delta(a, b) = \delta(b, a).
  3. Triangular inequality : \delta(a, b) + \delta(b, c) \geq \delta(a, c).

Computer vision shows more and more interests in Tversky’s results. In their introduction, many publications try to illustrate the non-verification of the previous properties. My point is that the examples of the non-verification of the triangular inequality are not correct (for images).

By example, in a projet report (Graphem – in french) on the visual similarity, the authors propose these images:

b_01
A                               B                               C
According to the authors:
  1. left (A) and right (C) images can be judged quite dissimilars.
  2. But middle image (B) can be judged similar to (A) et à (C).
  3. The distance d(A, C) would thus be greater than the sum d(A,B)+d(B,C), contradicting the triangle inequality.
I don’t see in this example where is the non verification of the triangle inequality:
  1. Ok for the first point, one can imagine an experience reinforcing these facts. The distance d(A, C) is thus obtained “high”. It could be discussed on the precise measure. Or if the measure is d(A, C) or d(C, A). But this can be admitted.
  2. If B is judged similar to A and C, the measures d(B, A) and d(B, C) must be “low”, in  any case smaller than d(A, C).

For the last point, a conclusion on the triangle inequality can only be given from a comparison between d(A, C) and the sum d(B, A) + d(B, C). But the numerical values are unknown, or not given by the authors. It is thus impossible to compute the sum and thus impossible to conclude. More formally, we have:

d(B, A) \leq d(A, C)

and

d(B, C) \leq d(A, C).

The only possible conclusion is d(B, A) + d(B, C) \leq 2 d(A, C), but not d(B, A) + d(B, C) \geq d(A, C).

Other bad examples can be find. Thus in a diaporama from J.M. Jolion (in french) on the similarity between images:
similarite_01-1
According to the author: with respect to a partial registration the triangle inequality is not validated d(a, b) + d(b, c) <= d(a, c). My previous commentaries still apply, i don’t understand how the author produces its conclusion.
In order to be complete, in E. Baudrier PhD thesis (p. 67) (that i supervised), the same kind of examples is reproduced:
scriptthesebaudrier_01-1
Triangular inequality: left and center images are similar, center and right ones also. If the similarity verify the triangular inequality, the left and right images are simular. It is not the case (Baudrier, 2005)
There, the author doesn’t try to compute any sum and its argument is close to Tversky one’s in “Features of Similarity” :
The triangle inequality differs from minimality and symmetry in that it cannot be formulated in ordinal terms. It asserts that one distante must be smaller than the sum of the two others, and hence it cannot be readily refuted with ordinal or even interval data. However, the triangle inequality implies that if A is quite similar to B, and B is quite similar to C, then A and C cannot be very dissimilar from each other.
Here Tversky makes a confusion between transitivity and triangular inequality. Does the former implies the latter ? It is not proved! Elsewhere in its publication, Tversky points out that visual stimulus are different in nature of others stimulus (verbal ones by example). Can visual stimulus lead to a verification of the triangular inequality? I don’t think so but still can’t find indisputable example of this in the case of visual objects.
FMN.
Wikio
Wikio

Tags: , , , ,