Distance Edit/Levenstein avec horodatage - différents chemins avec un coût similaire (minimal)

Question

J'utilise le Distance Edit/Levenstein pour mesurer la similarité entre les mots. Contrairement à l'implémentation la plus simple, mes lettres ont des horodatages, disons des nombres d'échantillons N=0,1,2,...

Le problème auquel je suis confronté est que je peux obtenir différents chemins le long de la matrice des coûts qui aboutissent au même coût (minimal), et ces différents chemins sont associés à différentes chaînes cibles. Par exemple, si je mesure la distance entre la chaîne source aa et la chaîne cible bab et je suppose que la chaîne source commence à l'horodatage N=0, alors j'ai deux chemins avec le même coût de 2 (une addition et une substitution) :

1. Ajouter b à N=-1, laissez le 1er a tel qu'il est, et remplacer le 2ème a avec un b .
2. Remplacer le 1er a avec un b Laissez le 2ème a tel qu'il est, et ajouter b à N=2.

Alignés sur la ligne du temps, ces 2 résultats sont différents :

Time:    ... -1 0 1 2 3 ...
Source:         a a
Target1:      b a b
Target2:        b a b

Je dois savoir quand cela se produit, afin de pouvoir choisir entre les deux cibles possibles en fonction de certains critères. Existe-t-il un autre moyen que de tracer le chemin en cours de route et de garder la trace de tous les chemins possibles qui mènent au coût minimal ?

J'ai envisagé d'utiliser Distorsion temporelle dynamique Mais il semble que, puisque la matrice des coûts est initialisée à l'infini (sauf pour l'entrée [0,0]), la première étape consistera toujours à faire correspondre la première image de la cible à la première image de la source, ce qui fait que la cible commence au même moment que la source. De toute façon, en utilisant DTW, je dois toujours tracer tous les chemins menant au même coût minimal.

Toute aide et tout commentaire sont les bienvenus.

Answer 1

En réfléchissant un peu plus à votre problème, il semble qu'il y ait une mauvaise compréhension de DTW ou de Levensthein. Les deux algorithmes essaient de comprimer et d'étendre les séquences pour les faire correspondre les unes aux autres. Ainsi, dans le cas de DTW, votre exemple aurait les solutions suivantes :

Solution1:
  a a
 /| |
b a b

Solution2:
a a
| |\
b a b

Solution3:
a a
|\|\
b a b

Si vous examinez ces solutions, vous remarquerez qu'elles ont toutes un coût de 2, c'est-à-dire que dans tous les cas, 2 b sont attribués à des comme. Ce que ces exemples signifient, c'est que dans la première séquence, un horodatage est écrasé par rapport à la deuxième séquence. Par exemple, dans la première solution, les deux premiers horodatages de b a sont écrasés pour former un seul pas de temps correspondant au premier a de la deuxième séquence (la deuxième séquence est simplement inversée, la troisième solution est plus complexe). Le DTW est destiné à traiter les séquences qui sont jouées à une vitesse différente à certains moments, d'où l'analogie avec le "time-warping".

Si vos pas de temps sont vraiment fixes et que vous n'avez besoin que de les aligner, sans tenir compte de la déformation réelle, vous pourriez simplement essayer tous les alignements et calculer les coûts.

Quelque chose comme ceci (en supposant que str2 soit la plus courte) :

for i = 0 to length( str1 ) - length( str2 ) do
  shift str2 by i to the left
  calculate number of different position between shifted str2 and str1
done
return i with lowest difference

En supposant que vous ayez besoin à la fois d'un décalage et d'un gauchissement (quelque chose peut avoir été ajouté au début et les pas de temps peuvent ne pas correspondre), envisagez le DTW de sous-séquence. Pour cela, il suffit de relâcher les conditions aux limites.

En supposant que vous indexez votre chaîne à un au lieu de zéro, vous pouvez écrire DTW comme ceci :

diff( x, y ) = 1 if str1 at x != str2 at x 
               0 otherwise

cost( 0, 0 ) = 0;
cost( 0, * ) = infinity;
cost( *, 0 ) = infinity;
cost( x, y ) = min( cost( x-1, y-1 ), cost( x-1, y ), cost( y, y-1) ) + diff( x, y )

DTW-Cost est alors cost( length( str1 ), length( str2 ) ) et votre chemin peut être tracé à partir de là. Pour les DTW ultérieurs, il suffit de changer ceci :

diff( x, y ) = 1 if str1 at x != str2 at x 
               0 otherwise

cost( 0, 0 ) = 0;
cost( 0, * ) = 0;
cost( *, 0 ) = infinity; // yes this is correct and needed
cost( x, y ) = min( cost( x-1, y-1 ), cost( x-1, y ), cost( y, y-1) ) + diff( x, y )

Ensuite, vous choisissez votre coût DTW comme min( cost( x, length( str2 ) ) et remonter jusqu'à argmin( cost( x, length( str2 ) ) . Cela suppose que vous savez qu'une chaîne est la sous-chaîne de l'autre. Si vous ne le savez pas et que les deux chaînes n'ont qu'un milieu commun déformé, vous devrez faire une correspondance partielle, ce qui, pour autant que je sache, est encore un sujet de recherche ouvert, car il faut choisir une notion d'"optimalité" qui ne peut pas être clairement définie.