4 A short theory of edit failures

Sander Scholtus

Previous | Next

4.1  Numerical data

Having formulated a new error localisation problem, we will now show how this problem may be solved by an adapted version of the branch-and-bound algorithm of De Waal and Quere (2003). To do this, we first need to extend the fundamental property mentioned at the end of Section 2.3 to the case that some of the edits may be failed. For convenience, we shall first examine the case of purely numerical data. The next subsection examines the case of purely categorical and mixed data.

In the case of purely numerical data, all edits take the form (2.4) or (2.5). Moreover, the implied edit (2.7) is reduced to its numerical part. The fundamental property given at the end of Section 2.3 implies in particular the following: if a given set of values for $x_1,\dots ,x_{g-1},x_{g+1},\dots ,x_p$ does not satisfy the implied edit (2.7), then it is impossible to find a value for $x_g$ that satisfies ${\psi }^s$ and ${\psi }^t$ simultaneously. However, it is still possible in this case to find a value for $x_g$ that satisfies one of the edits ${\psi }^s$ or ${\psi }^t.$ This observation, which is more or less trivial, forms the basis for the proof of Theorem 1 below.

Suppose that, at some point during an execution of the branch-and-bound algorithm of De Waal and Quere (2003), $q$ numerical variables have been treated (i.e., either eliminated or fixed). We denote the current set of edits by ${\Psi }_q,$ and the edits in this set by ${\psi }_q^k.$ By definition, ${\Psi }_0\equiv \Psi ,$ the original set of edits. It is possible to associate with each current edit ${\psi }_q^k$ an index set $B_q^k,$ which contains the indices of all the original edits that have been used, directly or indirectly, to derive this edit. In fact, $B_q^k$ can be defined recursively as follows:

• For an original edit ${\psi }_0^k,$ we define $B_0^k:=\{k\}.$
• For an edit ${\psi }_q^k$ which is derived from one other edit ${\psi }_{q-1}^l,$ either by fixing a variable to its original value or by simply copying the edit, we define $B_q^k:=B_{q-1}^l.$
• For an edit ${\psi }_q^k$ which is derived by eliminating a variable from a set of edits ${\psi }_{q-1}^t$ $(t\in T),$ we define $B_q^k:={\displaystyle {\cup }_{t\in T}{B}_{q-1}^t}.$

Note that, for numerical data, the set $T$ in the last item always contains exactly two edits. Larger edit sets may be encountered in the categorical case considered below.

A set $B$ is called a representing set of a collection of sets $B_q^{k_1},\dots ,B_q^{k_r}$ if it contains at least one element from each of $B_q^{k_1},\dots ,B_q^{k_r};$ see, for instance, Mirsky (1971, page 25). It should be noted that, in our case, a representing set $B$ identifies a subset of ${\Psi }_0,$ the set of original edits. We can now formulate the following theorem.

Theorem 1. Suppose that $q$ numerical variables have been treated and that the current set of numerical edits can be partitioned as ${\Psi }_q={\Psi }_q^{(1)}\cup {\Psi }_q^{(2)},$ where the edits in ${\Psi }_q^{(1)}$ are satisfied by the original values of the $p-q$ remaining variables, and the edits in ${\Psi }_q^{(2)}$ are failed. Let $B$ be a representing set of the index sets $B_q^k$ for all ${\psi }_q^k\in {\Psi }_q^{(2)}.$ Then there exist values for the eliminated variables that, together with the original values of the other variables, satisfy all original edits except those in $B.$

Proof. The proof of this theorem is given in Appendix A.1.

Example: Suppose that there are three numerical variables $(x_1,x_2,x_3)$ that should satisfy the following eight edits:

$\begin{array}{cc}{\psi }_0^1:& x_1+x_2+x_3=20\\ {\psi }_0^2:& x_1-x_2\ge 3\\ {\psi }_0^3:& -x_1+x_2\ge -6\\ {\psi }_0^4:& -x_1+x_3\ge 5\\ {\psi }_0^5:& x_1-x_3\ge -10\\ {\psi }_0^6:& x_1\ge 0\\ {\psi }_0^7:& x_2\ge 0\\ {\psi }_0^8:& x_3\ge 0.\end{array}$

The record $(x_1^0,x_2^0,x_3^0)=(10,1,-3)$ is inconsistent with respect to these edits. Upon eliminating $x_1$ from the original set of edits, we find the following updated set of edits:

$\begin{array}{ccc}{\psi }_1^1:& -2x_2-x_3\ge -17& (B_1^1=\{1,2\})\\ {\psi }_1^2:& 2x_2+x_3\ge 14& (B_1^2=\{1,3\})\\ {\psi }_1^3:& x_2+2x_3\ge 25& (B_1^3=\{1,4\})\\ {\psi }_1^4:& -x_2-2x_3\ge -30& (B_1^4=\{1,5\})\\ {\psi }_1^5:& -x_2-x_3\ge -20& (B_1^5=\{1,6\})\\ {\psi }_1^6:& x_2\ge 0& (B_1^6=\{7\})\\ {\psi }_1^7:& x_3\ge 0& (B_1^7=\{8\})\\ {\psi }_1^8:& 0\ge -3& (B_1^8=\{2,3\})\\ {\psi }_1^9:& -x_2+x_3\ge 8& (B_1^9=\{2,4\})\\ {\psi }_1^{10}:& x_2-x_3\ge -16& (B_1^{10}=\{3,5\})\\ {\psi }_1^{11}:& 0\ge -5& (B_1^{11}=\{4,5\})\\ {\psi }_1^{12}:& x_2\ge -6& (B_1^{12}=\{3,6\})\\ {\psi }_1^{13}:& x_3\ge 5& (B_1^{13}=\{4,6\}).\end{array}$

The index set $B_1^k$ is displayed in brackets next to each edit.

By substituting the original values of $x_2$ and $x_3$ in the current set of edits, we see that ${\psi }_1^2,{\psi }_1^3,{\psi }_1^7,{\psi }_1^9,$ and ${\psi }_1^{13}$ are failed. The set $B=\{1,4,8\}$ is a representing set for the associated index sets $B_1^k.$ According to Theorem 1, there exists a value for $x_1$ which, together with the original values of $x_2$ and $x_3,$ satisfies the original edits apart from ${\psi }_0^1,{\psi }_0^4,$ and ${\psi }_0^8.$ That this assertion is correct can be seen by substituting $x_2^0=1$ and $x_3^0=-3$ into the original set of edits; in fact, any value $x_1\in [4,7]$ will do.

The importance of Theorem 1 is that it enables one to evaluate, at each node of the branch-and-bound algorithm, which combinations of the original edits could be satisfied by imputing the variables that have been eliminated so far, and also which edits would remain failed. In particular, if we distinguish between hard and soft original edits, then this result makes it possible to use the branch-and-bound algorithm to find all feasible solutions to the new error localisation problem from Section 3, and also to evaluate, for each feasible solution, which of the soft edits remain failed, and hence to evaluate the value of $D_{\text{soft}}.$ This idea will be elaborated in Section 5.

4.2  Categorical and mixed data

We shall now derive a similar result to Theorem 1 for the case of purely categorical data. At the end of this section, we shall combine the two results so that they may also be applied to mixed data.

In the case of purely categorical data, all edits take the form (2.3). Let us consider the elimination method for categorical variables described in Section 2.3. If a given set of values for $v_1,\dots ,v_{g-1},v_{g+1},\dots ,v_m$ does not satisfy the implied edit (2.10), then it is not possible to find a value for $v_g$ that, together with the other values, satisfy all edits ${\psi }^k$ with $k\in T$ simultaneously. This is true because, by property (2.9), $F_j^{\ast }(T)\subseteq F_j^k$ for all $j\ne g$ and all $k\in T.$ Hence, if (2.10) is failed by $v_1,\dots ,v_{g-1},v_{g+1},\dots ,v_m,$ then plugging these values into an original edit with $k\in T$ produces a non-degenerate univariate edit for $v_g.$ Moreover, every possible value of $v_g$ fails at least one of these univariate edits, because of property (2.8). Interestingly, it is still always possible in this case to find a value for $v_g$ that satisfies all edits in $T$ but one. This follows from property (2.8) and the fact that $T$ is a minimal set having this property: for each $k\in T,F_g^k$ must contain at least one value from $D_g$ that is not covered by any other $F_g^l$ with $l\in T.$

We now present the analogue of Theorem 1 for categorical data, using the same notation as for numerical data. In particular, the recursive definition of $B_q^k$ is exactly the same as in Section 4.1.

Theorem 2. Suppose that $q$ categorical variables have been treated and that the current set of categorical edits can be partitioned as ${\Psi }_q={\Psi }_q^{(1)}\cup {\Psi }_q^{(2)},$ where the edits in ${\Psi }_q^{(1)}$ are satisfied by the original values of the $m-q$ remaining variables, and the edits in ${\Psi }_q^{(2)}$ are failed. Let $B$ be a representing set of the index sets $B_q^k$ for all ${\psi }_q^k\in {\Psi }_q^{(2)}.$ Then there exist values for the eliminated variables that, together with the original values of the other variables, satisfy all original edits except those in $B.$

Proof. The proof of this theorem is given in Appendix A.2.

For an example that illustrates the use of this theorem, see Scholtus (2011).

Finally, we remark that Theorem 1 and Theorem 2 can be used together when the data is a mix of categorical and numerical variables. This follows from the structure of the branch-and-bound algorithm of De Waal and Quere (2003), where categorical variables are only treated once all numerical variables have been eliminated or fixed. Hence, the two results may be applied consecutively. There is a slight difference in the procedure for eliminating numerical variables, namely that implied edits are only generated from pairs of edits having an overlapping IF-condition; see Section 2.3. However, this does not affect the correctness of Theorem 1.

Previous | Next