De Rerum Natura

I am reading Cucker and Zhou’s “Learning Theory: An Approximation Theory Viewpoint”. I am trying to understand the accuracy versus precision separation in Digital Elevation Models (DEMs) by looking at how the bias/variance decomposition is done. Are these two different ways of decomposing error isomorphic? Is accuracy the same as bias, precision variance? I don’t think so. The accuracy error in a DEM could be defined by considering translations and other operations such as rotations and shearing. These operations being global could be used to define what one wants to call the accuracy of a model. What remains after these global operations would then be the precision error. This view of error decomposition means that it is not possible to look at something like the average error over a DEM and blindly state that it can also be decomposable into an accuracy and precision part. This is only possible for height estimates that have no uncertainty in their x,y locations. This is the case for the autonomous difference equations we described in the 8th Optical 3D conference. They are invariant under arbitrary rotations and rotations about axes that are parallel to the z-axis.

Getting back to Cucker and Zhou’s book. I found the following comment about “probably approximately correct” PAC learning interesting: “Extensions of PAC learning allowing for labeling mistakes with small probability exist.” Thus the “probably” part of PAC error estimates assumes that you have perfect training data. This is just another example of how little we know about error and how to properly take it into account in our estimation algorithms.

In the case of the DEM models, the autonomous difference equations can only detect an error that is invariant under the abelian operations of translations and rotations about a single axis. If I tried to decompose the height error taking into account x,y uncertainty — I would find that the average error is not decomposable into separable parts. Somehow, one must be able to express this non-separability as being technically due to the non-abelian character of 3D rotations.

The “Swiss paper” that I discussed in an earlier post solved the problem of vertical precision error estimation. I used a set of difference equations that range over $\{l,m\}$ where $l$ and $m$ are integers from 1 to the number of observations. The equations look like the difference of simple averages. My purpose in using them is that I would be able to cancel out the true value and be left with the error in each measurement. Surprisingly, the set of independent equations you get from considering all possible equations of this type can be turned into a well-determined linear algebra problem for the entries in a particular sparse covariance matrix. This allowed me to measure the vertical uncertainty in a composite Digital Elevation Model (DEM) without knowing ground truth. I currently interpret this as meaning that I have an estimate of how good my DEM model is. I could still be off by a scale, rotation, and translation.

But vertical uncertainty is only the first of two important numbers for the quality of a map. Another important one is the horizontal resolution. How fine grained are the readings in the map? Another way to capture this resolution is to ask what is the horizontal correlation length — how far apart do two measurements have to be so that they are de-correlated with each other. A way to study this is with the variogram. I had never heard of a ‘variogram’ until a couple of years ago. It essentially measures the spatial correlation of data by taking the average of the spatial difference of a function:
$$E[(f(x)-f(x+L){)}^2]$$
One typical behavior of this variogram function is that it starts at zero and rises to a plateau in an exponential fashion:
$$r*(1-\exp (-L/\lambda ))$$
The horizontal correlation length is defined to be where the variogram reaches 67% of its final value. In the exponential rise curve this happens when $L=\lambda$.

I have had to put off the calculation of the correlation length until today. I was astounded to get almost text-book like exponential rise curves. The autonomous difference equations work for horizontal correlation lengths also! I found a four postings correlation length for our Twenty-Nine Palms dataset. Howard says this is very good resolution. What surprises me is that this could even be done.