Une généralisation du paradigme de Fellegi-Holt pour la localisation automatique des erreurs 4. Un problème généralisé de localisation des erreursUne généralisation du paradigme de Fellegi-Holt pour la localisation automatique des erreurs 4. Un problème généralisé de localisation des erreurs

• Précédent
• Suivant

Soit $\mathcal{G}$ un ensemble fini d’opérations de vérification autorisées pour une application donnée de vérification automatique. De façon informelle, il est proposé ici de généraliser le problème de localisation des erreurs de Fellegi et Holt (1976) en remplaçant l’énoncé « le plus petit sous-ensemble de variables qui peuvent être imputées pour assurer la cohérence de l’enregistrement » par « la plus courte séquence d’opérations de vérification autorisées qui peut être appliquée pour assurer la cohérence de l’enregistrement ». Pour donner une définition formelle de ce problème généralisé de localisation des erreurs, il faut introduire de nouveaux éléments de notation et quelques concepts.

Supposons une séquence de points $x=x_0,x_1,\dots ,x_t=y$ appartenant à ${ℝ}^p.$ Un chemin allant de $x$ à $y$ s’entend d’une séquence d’opérations de vérification distinctes $g_1,\dots ,g_t\in \mathcal{G}$ de sorte que $x_n=g_n\left(x_{n-1}\right)$ pour tout $n\in \left\{1,\dots ,t\right\}.$ (Remarque : Si $g_n$ contient des paramètres libres, il faut interpréter cette égalité comme « il existe des valeurs des paramètres réalisables faisant en sorte que $g_n$ établisse une correspondance entre $x_{n-1}$ et $x_n$  ».) Un chemin est désigné par $P=\left[g_1,\dots ,g_t\right].$ L’ensemble de tous les chemins possibles allant de $x$ à $y$ est désigné par $\mathcal{P}\left(x,y\right).$ Cet ensemble peut être vide. Plus loin, on utilise $\mathcal{P}\left(x;G\right)$ pour désigner, pour un sous-ensemble donné $G\subseteq \mathcal{G},$ l’ensemble de tous les chemins partant de $x$ et correspondant aux opérations de vérification de $G$ dans un certain ordre (sans spécifier les paramètres libres); si $G$ contient $t$ éléments, $\mathcal{P}\left(x;G\right)$ contient $t!$ chemins.

Pour chaque opération de vérification $g\in \mathcal{G},$ on peut associer un poids $w_g>0$ représentant le coût de l’application de l’opération de vérification $g.$ Plus particulièrement, le poids d’une opération FH doit être égal au poids de confiance de la variable qu’elle impute. La longueur d’un chemin $P=\left[g_1,\dots ,g_t\right]$ peut donc être définie comme la somme des poids des opérations de vérification qui la constitue : $\ell \left(P\right)={\displaystyle {\sum }_{n=1}^t{w}_{g_n}},$ où, par convention, le chemin vide a une longueur de zéro. La distance de $x$ à $y$ s’entend de la longueur du chemin le plus court reliant $x$ à $y:$

$$d\left(x,y\right)=\{\begin{array}{ll}\min \left\{\ell \left(P\right)\text{|}P\in \mathcal{P}\left(x,y\right)\right\}\hfill & \text{si }\mathcal{P}\left(x,y\right)\ne \varnothing ,\hfill \\ \infty \hfill & \text{sinon}\text{.}\hfill \end{array}$$

En règle générale, $d\left(x,y\right)$ satisfait aux axiomes types d’un espace métrique, sauf qu’elle ne doit pas nécessairement être symétrique pour $x$ et $y;$ il s’agit plutôt de ce qu’on appelle un espace quasimétrique (Scholtus 2014). En conséquence, $d\left(x,y\right)$ représente « la distance de $x$ à $y$  » plutôt que « la distance entre $x$ et $y$  ».

La distance de $x$ à n’importe quel sous-ensemble fermé non vide $D\subseteq {ℝ}^p$ s’entend de la distance jusqu’au plus proche $y\in D:$ $d\left(x,D\right)=\min \left\{d\left(x,y\right)\text{|}y\in D\right\}.$ Aux fins de la localisation des erreurs, le sous-ensemble fermé non vide de ${ℝ}^p$ présentant un intérêt particulier est l’ensemble $D_0$ de tous les points qui satisfont à (2.1).

On peut maintenant formuler le problème généralisé de localisation des erreurs.

Problème. Supposons un ensemble donné d’enregistrements cohérents $D_0,$ un ensemble donné d’opérations de vérification autorisées $\mathcal{G}$ et un enregistrement donné $x.$ Si $d\left(x,D_0\right)=\infty ,$ alors le problème de localisation des erreurs pour $x$ est irréalisable. Sinon, n’importe quel chemin le plus court menant à un enregistrement $y\in D_0$ de sorte que $d\left(x,y\right)<\infty$ correspond à une solution réalisable au problème de localisation des erreurs pour $x.$ Une solution réalisable est dite optimale si elle produit un enregistrement $x^{*}\in D_0$ faisant en sorte que

$$d\left(x,x^{*}\right)=d\left(x,D_0\right).(4.1)$$

Le problème généralisé de la localisation des erreurs consiste donc officiellement à trouver un chemin optimal d’opérations de vérification.

Remarque n°1. En règle générale, il peut y avoir un très grand nombre d’enregistrements $x^{*}$ dans $D_0$ qui satisfont à (4.1) et qui peuvent être atteints par le même chemin d’opérations de vérification. Pour résoudre le problème de localisation des erreurs, il suffit de trouver un chemin optimal. La construction d’un enregistrement associé $x^{*}\in D_0$ peut donc être considérée comme une généralisation du problème d’imputation cohérente (voir la discussion sur l’imputation à la fin de la section 3).

Remarque n° 2. Le problème de localisation des erreurs ci-dessus est irréalisable pour les enregistrements qui ne peuvent être mis en correspondance dans $D_0$ par aucune combinaison d’opérations de vérification distinctes de $\mathcal{G}.$ Pour éviter cette situation, il faut définir un ensemble $\mathcal{G}$ suffisamment vaste pour que $d\left(x,D_0\right)<\infty$ pour tout $x\in {ℝ}^p.$ Dans ce qui suit, on présume tacitement que $\mathcal{G}$ a cette propriété. Un moyen simple d’y arriver, mais pas nécessairement le seul, est de s’assurer que $\mathcal{G}$ contient au moins toutes les opérations FH. Cela est suffisant parce que deux points quelconques de ${ℝ}^p$ peuvent toujours être reliés par un chemin qui concatène les opérations FH associées aux coordonnées qui les différencient.

Remarque n° 3. Il n’est pas difficile de voir que le problème de localisation des erreurs ci-dessus réduit le problème original de Fellegi et Holt (1976) au cas particulier où $\mathcal{G}$ contient seulement les opérations FH.

Remarque n° 4. Comme pour le problème de localisation des erreurs original fondé sur le paradigme de Fellegi-Holt, on peut montrer que, en vertu de certaines hypothèses, la minimisation de $d\left(x,y\right)$ pour tout $y\in D_0$ pour un enregistrement observé donné $x$ équivaut approximativement à la maximisation de la vraisemblance de l’enregistrement exempt d’erreur non observé associé. L’argument est sensiblement le même que celui de Kruskal (1983, pages 38-39) pour la distance dite de Levenshtein dans le contexte de l’appariement approximatif de chaînes. Pour cela, il faut d’abord que toutes les vérifications (2.1) soient des vérifications avec rejet, c’est-à-dire des vérifications auxquelles seules les valeurs erronées échouent. De plus, il faut présumer que le « processus de génération d’erreurs » stochastique $ℰ$ dont il est question à la section 3 a les propriétés suivantes :

• Il existe une correspondance biunivoque entre l’ensemble des erreurs qui peuvent se produire en vertu de $ℰ$ et l’ensemble des opérations de vérification autorisées $\mathcal{G}$ qui corrigent les erreurs.
• Les erreurs dans $ℰ$ se produisent de façon indépendante les unes des autres.
• L’erreur correspondant à l’opération $g$ se produit selon une probabilité connue $p_g.$

Enfin, comme pour (2.3), les poids $w_g$ doivent être choisis comme suit :

$$w_g=-\log \left(\frac{p_g}{1-p_g}\right).(4.2)$$

En vertu de ces hypothèses, Scholtus (2014) a adapté l’argument de Kruskal (1983) pour montrer que la solution optimale au problème de localisation des erreurs (4.1) peut être justifiée comme un estimateur approximatif du maximum de vraisemblance. [Remarque : Le calcul présenté par Scholtus (2014) suppose en outre que $p_g\ll 1$ pour toutes les valeurs, auquel cas $w_g\approx -\log p_g.$ Cette hypothèse n’est pas nécessaire; voir Liepins (1980).]

• Précédent
• Suivant