A layered perturbation method for the protection of tabular outputs
Section 3. The Layered Perturbation Method (LPM)

• Previous
• Next

3.1 Description

The LPM is a perturbative method for totals that focuses on disclosure from differencing. When used in tables of magnitude it allows cell suppression to be restricted to sensitive cells. Three basic ideas underlie the LPM. The first two are similar to the TCM approach.

The first basic idea is the attachment of pseudo-random hash numbers (PRNs) to units to produce consistent perturbation outcomes when needed. This discourages the use of repeated queries to improve the estimation of unperturbed totals. The EZS method is used to multiply the value of a unit $i$ by a weight $w_i=1+{\epsilon }_i,$ with ${\epsilon }_i~\left(0,{\sigma }_{\epsilon }^2\right)$ as above. To obtain consistent results ${\epsilon }_i$ are generated from a unit-specific PRN that is uniformly distributed over $\left[0,1\right).$ For example, use $h_i/\text{1000},$ where $h_i$ are generated from the Social Insurance Number (e.g., $h_i=Mod\left(SI{N}_i·P,\text{1000}\right)$ for $P$ a large prime). Using $h_i$ will always perturb unit $i$ the same way. To perturb unit $i$ the same way only when it appears in the same cell total, generate cell-unit level noise ${w^{}}_i=1+{{\epsilon }^{}}_i$ from ${h^{}}_i=Mod\left(h_i+h_{tot},\text{1000}\right)/\text{1000},$ where $h_{tot}={\displaystyle {\sum }_{i\in cell}{h}_i}.$ Primes are used to designate cell-unit specific noises and perturbations. All noise values are derived from $h_i$ or ${h^{}}_i.$

The second idea is the application of perturbation to units in each cell by layers. The largest four units are perturbed in a random but consistent manner using perturbation weights $w_i$ generated from $h_i.$ The next largest units, say units 5 to 9, are perturbed in a semi-consistent manner. Their perturbation is a mixture of unit specific weights $w_i$ and unit-cell specific weights ${w^{}}_i.$ Smallest units are not perturbed. Their values are protected from differencing by the unit-cell perturbations of units 5 to 9 since adding or removing a unit in a cell, no matter how small, will affect the ${w^{}}_i$ for those units. The number of units per layer is flexible, we have found that four and five, respectively gave satisfactory results.

A third set of measures mostly targets the issue of differencing. The direction of noise for even-ranked units is reversed $(w_i$ are set from ${(-1)}^{i+1}{\epsilon }_i)$ to increase variances of differences when a top-ranked unit is changed. For units 5 to 9 a random mixture of $w_i$ and ${w^{}}_i$ is applied to lessen the risk when a small unit is added or removed. Finally, the noise for the top three units is amplified in nonsensitive cells with greater dominance. This allows lower levels of noise to be used generally, reducing the overall impact of the perturbation on data quality.

A suggested application of the LPM would consist of suppressing all sensitive and small cells (e.g., $n<10)$ and perturbing remaining cells. Because of the protection offered by perturbation, cells that are slightly sensitive may also be publishable. For other cells with cell total $X={\displaystyle {\sum }_{i\in cell}{x}_i},$ set perturbed value $Z$ as

$$\text{ Z}=X+K{\epsilon }_1{x}_1-L{\epsilon }_2{x}_2+M{\epsilon }_3{x}_3-{\epsilon }_4{x}_4-{\displaystyle {\sum }_{i=5}^9\left\{{\left(-1\right)}^i{\alpha }_i{\epsilon }_i-\left(1-{\alpha }_i\right){{\epsilon }^{}}_i\right\}{x}_i}.$$

$K,L$  and $M$  are set to increase the noise of $Z,$ when needed (set $K,L$  and $M\ge 1).$  The ${\alpha }_i$ are random variables that are independent of ${\epsilon }_i,$ e.g., ${\alpha }_i~\text{Uniform(}0,1\text{)}$ or ${\alpha }_i=\text{Mod}\left(h_i,8\right)/7.$

3.2 Some results

Let ${\epsilon }_i,{{\epsilon }^{}}_i~\left(0,{\sigma }_{\epsilon }^2\right),$ ${\alpha }_i~\text{Uniform(}0,1\text{)},$ i.i.d. and let $K,L$  and $M$ be fixed (for now). It follows that:

$$E\left(Z\right)=X\text{and}V\left(Z\right)=\left\{K^2{x}_1^2+L^2{x}_2^2+M^2{x}_3^2+x_4^2+\frac{2}{3}{\displaystyle {\sum }_{i=5}^9{x}_i^2}\right\}{\sigma }_{\epsilon }^2.$$

Let $X_{-1},X_{-2},X_{-3}$ and $Z_{-1},Z_{-2},Z_{-3}$ equal $X$ and $Z$ for the cell after removing units 1, 2 and 3, respectively. Keeping subscripts from the original cell (i.e., subscript 2 refers to the unit that was second in $X)$ we have:

$$\begin{array}{ll}{Z}_{-1}\hfill & =X_{-1}+K{\epsilon }_2{x}_2-L{\epsilon }_3{x}_3+M{\epsilon }_4{x}_4-{\epsilon }_5{x}_5-{\displaystyle {\sum }_{i=6}^{10}\left\{{\left(-1\right)}^i{\alpha }_i{\epsilon }_i-\left(1-{\alpha }_i\right){{\epsilon }^{}}_i\right\}{x}_i},\hfill \\ Z_{-2}\hfill & =X_{-2}+K{\epsilon }_1{x}_1-L{\epsilon }_3{x}_3+M{\epsilon }_4{x}_4-{\epsilon }_5{x}_5-{\displaystyle {\sum }_{i=6}^{10}\left\{{\left(-1\right)}^i{\alpha }_i{\epsilon }_i-\left(1-{\alpha }_i\right){{\epsilon }^{}}_i\right\}{x}_i},\text{and}\hfill \\ Z_{-3}\hfill & =X_{-3}+K{\epsilon }_1{x}_1-L{\epsilon }_2{x}_2+M{\epsilon }_4{x}_4-{\epsilon }_5{x}_5-{\displaystyle {\sum }_{i=6}^{10}\left\{{\left(-1\right)}^i{\alpha }_i{\epsilon }_i-\left(1-{\alpha }_i\right){{\epsilon }^{}}_i\right\}{x}_i}.\hfill \end{array}$$

We can obtain $Z_{-i}$ for other units similarly. If we estimate the dropped units as ${\widehat{x}}_i=Z-Z_{-i}$ it can be shown that, with $G=2\frac{2}{3}{x}_5^2+2{\displaystyle {\sum }_{i=6}^9{x}_i^2+\frac{2}{3}{x}_{10}^2},$

$$\begin{array}{ll}E\left({\widehat{x}}_i\right)\hfill & =x_i,\hfill \\ V\left({\widehat{x}}_1\right)\hfill & =\left\{K^2{x}_1^2+{\left(K+L\right)}^2{x}_2^2+{\left(L+M\right)}^2{x}_3^2+{\left(M+1\right)}^2{x}_4^2+G\right\}{\sigma }_{\epsilon }^2,\hfill \\ V\left({\widehat{x}}_2\right)\hfill & =\left\{L^2{x}_2^2+{\left(L+M\right)}^2{x}_3^2+{\left(M+1\right)}^2{x}_4^2+G\right\}{\sigma }_{\epsilon }^2,\hfill \\ V\left({\widehat{x}}_3\right)\hfill & =\left\{M^2{x}_3^2+{\left(M+1\right)}^2{x}_4^2+G\right\}{\sigma }_{\epsilon }^2,\hfill \\ V\left({\widehat{x}}_4\right)\hfill & =\left\{x_4^2+G\right\}{\sigma }_{\epsilon }^2,\hfill \\ V\left({\widehat{x}}_5\right)\hfill & =\left\{\frac{2}{3}{x}_5^2+2x_6^2+2x_7^2+2x_8^2+2x_9^2+\frac{2}{3}{x}_{10}^2\right\}{\sigma }_{\epsilon }^2,\hfill \\ V\left({\widehat{x}}_6\right)\hfill & =\left\{\frac{2}{3}{x}_5^2+\frac{2}{3}{x}_6^2+2x_7^2+2x_8^2+2x_9^2+\frac{2}{3}{x}_{10}^2\right\}{\sigma }_{\epsilon }^2,\hfill \\ V\left({\widehat{x}}_7\right)\hfill & =\left\{\frac{2}{3}{x}_5^2+\frac{2}{3}{x}_6^2+\frac{2}{3}{x}_7^2+2x_8^2+2x_9^2+\frac{2}{3}{x}_{10}^2\right\}{\sigma }_{\epsilon }^2,\hfill \\ V\left({\widehat{x}}_8\right)\hfill & =\left\{\frac{2}{3}{x}_5^2+\frac{2}{3}{x}_6^2+\frac{2}{3}{x}_7^2+\frac{2}{3}{x}_8^2+2x_9^2+\frac{2}{3}{x}_{10}^2\right\}{\sigma }_{\epsilon }^2,\hfill \\ V\left({\widehat{x}}_9\right)\hfill & =\frac{2}{3}\left\{x_5^2+x_6^2+x_7^2+x_8^2+x_9^2+x_{10}^2\right\}{\sigma }_{\epsilon }^2,\text{and}\hfill \\ V\left({\widehat{x}}_i\right)\hfill & =\frac{2}{3}\left\{x_5^2+x_6^2+x_7^2+x_8^2+x_9^2\right\}{\sigma }_{\epsilon }^2,\text{for}i>9.\hfill \end{array}$$

If we assume that $K,L$ and $M$ are fixed we can set them based on some requirement for $\text{V}\left({\widehat{x}}_i\right).$ For example, we may want to have $\text{V}\left({\widehat{x}}_i\right)=x_i^2/30$ since, for $z~\text{N}(0,1),\mathrm{Pr}\left(\left|z\right|>\text{0}\text{.44}\right)=\text{0}\text{.66}$ which for ${\widehat{x}}_i~\text{N}\left(x_i,x_i^2/30\right)$ gives $\mathrm{Pr}\left\{\left|{\widehat{x}}_i-x_i\right|\ge 8\%x_i\right\}=66\%.$

To obtain $\text{V}\left({\widehat{x}}_i\right)=x_i^2/NN$ we can solve (fixed) $K,L$ and $M$ in reverse order. This gives

$$\begin{array}{ll}M\hfill & =\frac{\sqrt{\left(x_3^2+x_4^2\right)\left(x_3^2/NN{\sigma }_{\epsilon }^2-G\right)-x_3^2{x}_4^2}-x_4^2}{x_3^2+x_4^2}\hfill \\ L\hfill & =\frac{\sqrt{\left(x_2^2+x_3^2\right)\left(x_2^2/NN{\sigma }_{\epsilon }^2-G-x_4^2\left(M+1\right)²\right)-M²x_2^2{x}_3^2}-M{x}_3^2}{x_2^2+x_3^2}\hfill \\ K\hfill & =\frac{\sqrt{\left(x_1^2+x_2^2\right)\left(x_1^2/NN{\sigma }_{\epsilon }^2-G-x_3^2\left(L+M\right)²-x_4^2\left(M+1\right)²\right)-L²x_1^2{x}_2^2}-L{x}_2^2}{x_1^2+x_2^2}\hfill \end{array}$$

In practice, $L$ and $M$ are bounded below at 1 and above at some threshold value less than 2, and $K$ is bounded below at 1 and can taper off above the threshold. Also, the target values of $K,L$ and $M$ depend on the situation in each cell. Here, for simplicity of illustration, they were assumed not to change when we removed observations from the cell.

Using the same noise and changing its direction for even-ranked units means that we take advantage of the correlation between the $Z$ and $Z_{-i}$ to increase the variance of ${\widehat{x}}_i=Z-Z_{-i}.$ For example, the contribution to $V\left({\widehat{x}}_1\right)$ from unit 2 is ${\left(K+L\right)}^2{x}_2^2{\sigma }_{\epsilon }^2.$ If we had used independent (or unit-cell specific) noises ${{\epsilon }^{}}_i$ instead of ${\epsilon }_i$ for units 1 to 4 the contribution from unit 2 would have been only $\left(K^2+L^2\right)x_2^2{\sigma }_{\epsilon }^2.$

3.3 Comparison with the EZS and TCM approaches

With EZS the perturbed cell total is simply $Z=X+{\displaystyle {\sum }_{i\in cell}{\epsilon }_i{x}_i},$ giving $V\left(Z\right)={\displaystyle {\sum }_{i\in cell}{x}_i^2{\sigma }_{\epsilon }^2}.$ For any unit $i$ we have $E\left({\widehat{x}}_i\right)=x_i$ and $V\left({\widehat{x}}_i\right)=x_i^2{\sigma }_{\epsilon }^2,$ which is smaller than the equivalent variance with the LPM for the same level of noise ${\sigma }_{\epsilon }^2$ even when we set $K=L=M=1.$ A possible exception could be unit 5, if subsequent units are relatively quite small. This can be seen by examining $V\left({\widehat{x}}_5\right)$ above.

The TCM applies three multiplicative perturbation factors to the largest, say 4, units in each cell. A magnitude component $M_i$ determines the relative size of the perturbation for the $i^{\text{th}}$ ranked unit. The $M_i$ are fixed; typically $M_1>M_2>M_3>M_4,$ e.g., $\left[\text{0}\text{.6},\text{0}\text{.4},\text{0}\text{.3},\text{0}\text{.2}\right].$ A permanent random factor $d_i=\pm 1$ fixes the direction of the noise for each unit $i.$ A pseudo-random factor $s_i>0$ determines unit-cell specific noises. This gives $Z=X+{\displaystyle {\sum }_{i=1}^4{M}_i{d}_i{s}_i{x}_i}.$ The method can be represented in a form comparable to LPM, with $\left[M_1,M_2,M_3,M_4\right]=\left[K,L,M,1\right],d_i=\text{sign}\left({\epsilon }_i\right)$ and $s_i=\left|{{\epsilon }^{}}_i\right|.$ The way the $d_i$ are fixed is a major difference with the LPM that greatly diminishes the protection offered to ${\widehat{x}}_1.$ To illustrate this, consider two adaptions of these methods that yield identical variances for $Z:$

$$\begin{array}{ll}{Z}_{LPM}\hfill & =X+K{\epsilon }_1{x}_1-L{\epsilon }_2{x}_2+M{\epsilon }_3{x}_3-{\epsilon }_4{x}_4,\text{and}\hfill \\ Z_{TCM}\hfill & =X+Ksign\left({\epsilon }_1\right)\left|{{\epsilon }^{}}_1\right|x_1+Lsign\left({\epsilon }_2\right)\left|{{\epsilon }^{}}_2\right|x_2+Msign\left({\epsilon }_3\right)\left|{{\epsilon }^{}}_3\right|x_3+sign\left({\epsilon }_4\right)\left|{{\epsilon }^{}}_4\right|x_4,\hfill \end{array}$$

where the same notational conventions as before are used, with fixed $K,L,M>0.$ This yields

$$\begin{array}{ll}{V}_{LPM}\left({\widehat{x}}_1\right)\hfill & =\left\{K^2{x}_1^2+{\left(K+L\right)}^2{x}_2^2+{\left(L+M\right)}^2{x}_3^2+{\left(M+1\right)}^2{x}_4^2+x_5^2\right\}{\sigma }_{\epsilon }^2,\text{and}\hfill \\ V_{TCM}\left({\widehat{x}}_1\right)\hfill & =K^2{x}_1^2{\sigma }_{\epsilon }^2+\left\{\left(K^2+L^2\right)x_2^2+\left(L^2+M^2\right)x_3^2+\left(M^2+1\right)x_4^2\right\}{\sigma }_{\left|\epsilon \right|}^2+x_5^2{\sigma }_{\epsilon }^2.\hfill \end{array}$$

Not only are factors such as ${\left(K+L\right)}^2$ larger than $\left(K^2+L^2\right),$ but the variance for the noise, ${\sigma }_{\epsilon }^2,$ is often replaced with that of the absolute noise, ${\sigma }_{\left|\epsilon \right|}^2,$ which is much smaller. For the split triangular distribution it goes from $\left(3a^2+2ab+b^2\right)/6\text{to}{\left(b-a\right)}^2/18.$ When $b=2a$ this means dropping from $11a^2/6\text{to}{a}^2/18.$

This is not a legitimate comparison of the two methods. We are not using the actual LPM, and method parameters need not be identical. But it shows the impact of the different approaches taken for the $d_i.$

• Previous
• Article main page
• Next