A generalized Fellegi-Holt paradigm for automatic error localization 2. Background and related workA generalized Fellegi-Holt paradigm for automatic error localization 2. Background and related work

• Previous
• Next

Let $x=\left(x_1, \dots , x_p\right)\prime \in {ℝ}^p$  be a record of $p$  numerical variables. Suppose that this record has to satisfy $k$  edit rules, in the form of the following system of linear (in)equalities:

$$Ax+b\odot 0,(2.1)$$

where $A=\left(a_{rj}\right)$ is a $k\times p-$ matrix of coefficients and $b=\left(b_1, \dots , b_k\right)\prime$ is a vector of constants. Here and elsewhere, $0$ represents a vector of zeros of appropriate length; similarly, $\odot$ represents a symbolic vector of operators from the set $\left\{\ge ,\le ,=\right\}.$

For a given record $x$ that does not satisfy all edits in (2.1), the Fellegi-Holt-based error localization problem amounts to finding the minimum of

$${\displaystyle \sum _{j=1}^p{w}_j{\delta }_j},(2.2)$$

with $w_j>0$ the confidence weight of variable $x_j$ and ${\delta }_j\in \left\{0,1\right\},$ under the condition that the original record can be made consistent with the edits by imputing only those $x_j$ with ${\delta }_j=1$ (de Waal et al. 2011, page 66).

Fellegi and Holt (1976) also proposed a method for solving the above error localization problem, based on the generation of a sufficient set of so-called implied edits (see below). Unfortunately, the number of implied edits needed by this method is often extremely large in practice. Over the past decades, various dedicated algorithms for the error localization problem have been developed by, among others, Schaffer (1987), Garfinkel, Kunnathur and Liepins (1988), Kovar and Whitridge (1990), Ragsdale and McKeown (1996), de Waal (2003), de Waal and Quere (2003), Riera-Ledesma and Salazar-González (2003, 2007), Bruni (2004), and de Jonge and van der Loo (2014). Early algorithms mostly focused on strengthening the original method of Fellegi and Holt (1976) by reducing the number of required implied edits. More recent algorithms rely on the fact that the error localization problem can be written as a mixed-integer programming problem, which makes it possible to apply standard optimization techniques. See also de Waal and Coutinho (2005) or de Waal et al. (2011) for an overview and comparison of various error localization algorithms.

Implied edits are constraints that follow logically from the original edits (2.1). In the present context (numerical data, linear edits), all relevant implied edits may be generated by a technique called Fourier-Motzkin elimination (FM elimination; cf. Williams 1986). FM elimination transforms a system of linear constraints having $p$ variables into a system of implied linear constraints having at most $p-1$ variables; thus, at least one of the original variables is eliminated. For mathematical details, see the appendix.

FM elimination has the following fundamental property: the system of implied constraints is satisfied by the values of the non-eliminated variables if, and only if, there exists a value for the eliminated variable that, together with the other values, satisfies the original system of constraints. In error localization under the Fellegi-Holt paradigm, by repeatedly applying this fundamental property, one may verify whether any particular combination of variables can be imputed to obtain a consistent record, given the original values of the other variables. A clear illustration of this use of FM elimination is provided by the error localization algorithm of de Waal and Quere (2003).

To conclude this section, it is interesting to look briefly at the statistical interpretation of the error localization problem. In fact, in motivating their paradigm for automatic error localization, Fellegi and Holt (1976) did not provide any formal statistical argument. Their reasoning was more intuitive:

• “The data in each record should be made to satisfy all edits by changing the fewest possible items of data (fields). This we believe to be in agreement with the idea of keeping the maximum amount of original data unchanged, subject to the constraints of the edits, and so manufacturing as little data as possible. At the same time, if errors are comparatively rare, it seems more likely that we will identify the truly erroneous fields.” (Fellegi and Holt 1976, page 18).

A statistical argument for minimizing the weighted number of imputed variables was provided by Liepins (1980) and Liepins, Garfinkel and Kunnathur (1982), elaborating on earlier results of Naus, Johnson and Montalvo (1972). Suppose that errors occur according to a stochastic process, with each variable $x_j$ being observed in error with a probability $p_j$ that does not depend on its true value and with errors being independent across variables. Suppose furthermore that the confidence weights are defined as follows:

$$w_j=-\log \left(\frac{p_j}{1-p_j}\right).(2.3)$$

Then it can be shown that minimizing expression (2.2) is approximately equivalent to maximizing the likelihood of the unobserved error-free record. Note that these authors tacitly assume that an error always affects one variable at a time.

Alternative error localization procedures that are based more directly on statistical models have been proposed by, e.g., Little and Smith (1987) and Ghosh-Dastidar and Schafer (2006). These procedures use outlier detection techniques and require an explicit model for the true data. Unfortunately, they cannot handle edit rules such as (2.1) in a straightforward manner.

• Previous
• Next