A generalized Fellegi-Holt paradigm for automatic error localization 5. Implied edits for general edit operationsA generalized Fellegi-Holt paradigm for automatic error localization 5. Implied edits for general edit operations

• Previous
• Next

In this section, a result will be derived that establishes whether a given path of edit operations of the form (3.1) can be used to make a given record consistent with a given system of edit rules (i.e., is a feasible solution to the error localization problem). This result uses the FM elimination technique discussed in Section 2.

Let $x$ be a given record and let $y_t$ be any record that can be obtained by applying, in sequence, the edit operations $g_1,\dots ,g_t$ to $x:$

$$y_t=g_t\circ g_{t-1}\circ \cdots \circ g_1\left(x\right).(5.1)$$

Write $g_n\left(x\right)=T_{n}x+S_n{\alpha }_n+c_n,$ for $n\in \left\{1,\dots ,t\right\}.$ From (5.1) it follows by induction that

$$\begin{array}{ll}{y}_1\hfill & =T_{1}x+S_1{\alpha }_1+c_1,\hfill \\ y_2\hfill & =T_2{T}_{1}x+S_2{\alpha }_2+c_2+T_2\left(S_1{\alpha }_1+c_1\right),\hfill \end{array}$$

and, in general,

$$y_t=T_t\cdots T_{1}x+S_t{\alpha }_t+c_t+{\displaystyle \sum _{n=2}^t{T}_t\cdots T_n}\left(S_{n-1}{\alpha }_{n-1}+c_{n-1}\right),(5.2)$$

where the sum over $n$ is defined to be zero when $t=1.$ Moreover, all terms involving $S_n{\alpha }_n$ vanish in these expressions when $g_n$ does not contain any free parameters.

The path of edit operations $P=\left[g_1,\dots ,g_t\right]$ can be applied to $x$ to obtain a record that is consistent with the edits (2.1) if, and only if, there exists a $y_t$ of the form (5.2) that satisfies $A{y}_t+b\odot 0$ and all relevant additional restrictions of the form (3.2) on ${\alpha }_1,\dots ,{\alpha }_t.$ Using (5.2), $A{y}_t+b\odot 0$ can be written as:

$$\left(A{T}_t\cdots T_1\right)x+\left(A{S}_t\right){\alpha }_t+{\displaystyle \sum }_{n=2}^t\left(A{T}_t\cdots T_n{S}_{n-1}\right){\alpha }_{n-1}+b_t\odot 0,(5.3)$$

with $b_t=b+A{c}_t+{\displaystyle {\sum }_{n=2}^{t}A{T}_t\cdots T_n{c}_{n-1}}$ a vector of constants.

Interestingly, (5.3) and the possible additional restrictions of the form (3.2) constitute a linear system of the form (2.1) on the extended record ${\left(x^{\prime },{{\alpha }^{\prime }}_1,\dots ,{{\alpha }^{\prime }}_t\right)}^{\prime }.$ Therefore, FM elimination may be used to remove all free parameters from this system. This yields a system of implied restrictions for $x.$ Moreover, a repeated application of the fundamental property of FM elimination establishes that $x$ satisfies this system of implied edits if, and only if, there exist parameter values for ${\alpha }_1,\dots ,{\alpha }_t$ that, together with $x,$ satisfy (5.3) and (3.2). Hence, it follows that the path of edit operations $P=\left[g_1,\dots ,g_t\right]$ can lead to a consistent record for $x$ if, and only if, $x$ satisfies the system of implied edits obtained by eliminating ${\alpha }_1,\dots ,{\alpha }_t$ from (5.3) and (if relevant) additional restrictions of the form (3.2).

Example. Consider the following edits in $x_1$ and $x_2:$

$$x_1\ge 0,(5.4)$$

$$x_2\ge 0,(5.5)$$

$$x_1+x_2\le 5.(5.6)$$

Let $g$ be the edit operation that transfers an amount of at most four units between $x_1$ and $x_2,$ in either direction: $g\left(\left(x_1,x_2\right)\prime \right)=\left(x_1+\alpha ,x_2-\alpha \right)\prime$ with $-4\le \alpha \le 4.$ For this single edit operation, the system of transformed edits (5.3) is:

$$x_1+\alpha \ge 0,(5.7)$$

$$x_2-\alpha \ge 0,(5.8)$$

$$x_1+x_2\le 5.(5.9)$$

I also add the following restrictions of the form (3.2) on $\alpha :$

$$\alpha \ge -4,(5.10)$$

$$\alpha \le 4.(5.11)$$

This yields five linear constraints (5.7) $-$ (5.11) on $x_1,$ $x_2,$ and $\alpha ,$ from which $\alpha$ may be removed by FM elimination to obtain:

$$x_1\ge -4,(5.12)$$

$$x_2\ge -4,(5.13)$$

$$x_1+x_2\ge 0,(5.14)$$

$$x_1+x_2\le 5.(5.15)$$

According to the theory, any record $\left(x_1,x_2\right)\prime$ that satisfies (5.12) $-$ (5.15) can be made consistent with the original edits (5.4) $-$ (5.6) by transferring a certain amount $-4\le \alpha \le 4$ between $x_1$ and $x_2.$ The example record $\left(x_1,x_2\right)\prime =\left(-2,3\right)\prime$ is inconsistent with the original edit rules (5.4) $-$ (5.6) but satisfies (5.12) $-$ (5.15). This implies that the record can be made consistent with the original edits by applying $g.$ It is easy to see that this is true; any choice $2\le \alpha \le 3$ will do.

It is interesting to note that, for the special case that $P$ consists of the single FH operation that imputes $x_j,$ the transformed system of edits (5.3) is obtained by replacing every occurrence of $x_j$ in the original edits by an unrestricted parameter $\alpha .$ Eliminating $\alpha$ from (5.3) is equivalent in this case to eliminating $x_j$ directly from the original edits. In this sense, the above result generalizes the fundamental property of FM elimination for FH operations to all edit operations of the form (3.1).

In general, the set of records defined by expression (5.2) depends on the way the edit operations are ordered. Thus, two paths consisting of the same set of edit operations in a different order need not yield the same solution to the error localization problem. In this respect, general edit operations differ from FH operations (Scholtus 2014).

• Previous
• Next