De Rerum Natura

noisy-map

ground-truth

All the experiments we have been carrying out with precision error have, so far, been with real data. Because of this, we do not have “ground truth” to determine if the reconstruction is correct. That changed today.

Synthetic experiments are a well-known device for studying models or algorithms. By artificially creating data where one knows exactly what is going on, one can then see if the algorithm one is testing is able to reproduce the artificially created “ground truth”.

I did that today by creating an artificial landscape as shown in the left figure at the top. A single example from the ten noisy versions of this landscape is shown in the figure on the right.

The advantage of using precision error is shown in the figures at the bottom. The figure on the left shows what happens after weighting the maps with the discovered precision error covariance matrix. The picture on the right is the result of simple averaging. The difference is clear. The weighted average is better, and precision error estimation was the way to obtain the weights.

weighted-average

simple-average

Decay of precision error estimate variance

Just to show that not all questions behave as nicely as question 9 in the previous post, here is the plot for question 6 in the same exam.The fit is not as good as for question 9. This is expected, there is no reason why the precision error should decay with a perfect exponential behavior. Nonetheless, it still shows a similar decay constant — about six questions. Remember to click on the image to get the larger image in a zoom pane.

To show off the installation of FancyZoom (a trick I learned while visiting the excellent Language Log), I present a graph of the percentage variation in the mean square precision error as a function of the number of questions used to compute it. The image looks small but you can now click on it to obtain a zoomed in version. Try it!

Question 9 precision error estimate variance

Note how good the fit is to a shifted exponential function of the form:
$$a+b*\exp (-c(n_q-3)).$$
The measurements are the small dots at $n_q=\{\mathrm{4,6,7,10,12}\}$. The fitted values are $a=0.06$, $b=0.2$, and $c=0.43$. The variable $c$ is the decay constant for the variability in the estimate. In particular, if you calculate its inverse $1/c$ you get the number of questions beyond three that will give you less than 33% variability in the estimate. This turns out to be about 2 questions. So ten or twelve questions should be enough for this group of students.

Once again, this suggests that teachers are asking too many questions in their multiple choice exams.

Our technical report on how to recover precision error estimates with ${\ell }_1$-minimization has been accepted by the 2008 International Conference on Machine Learning.

The paper originally got three anonymous reviews. Two were positive, one strongly negative. In our response to the reviews, we agreed with the general criticism by the reviewers that one experimental demonstration is not enough. In our precision error papers so far, we have only been using one dataset — aerial photographs from the Twenty-Nine Palms region in California. So we are going to include some results from North Carolina forest data to show that our technique works for all sorts of images.

Readers of previous posts may note that besides maps, the precision error has been recovered for questions in a multiple-choice-quesiton (MCQ) exam. It would be nice to include this in our ICML paper, but the title of the paper is “Autonomous geometric precision error estimation in low-level computer vision tasks” so it seems incongruous to do so.

The paper was submitted in early January. Afterwards, we realized that our precision error technique for elevation errors in maps applies to any set of models that make scalar predictions about multiple entities. We are now working on a draft for a Science magazine article that will combine the examples from maps and exams to illustrate the wide applicability of our technique.

The precision error equations require that “ground truth” cancel out. It is easy to see what that means for elevations in a map. What does it mean for parse trees in a natural language processing task like sentence parsing?

One way to define distance between trees is to consider the total number of reverse operations that bring them back to a common ancestor. Is that number equal to the number one would get by comparing everything to the “true” parsing? That is, the observed parse prediction’s distance is equal to the true parse distance plus the distance created by the error-transformations.

Substraction makes sense to me in the context of trees: you take everything after the common ancestor. What is addition of parse trees? The union of all edges and vertices. Parse trees are graphs after all.

This addition and subtraction of graphs means that we can use the precisione error equations. Parse trees are added and substracted. In the end, a score is assigned to the difference by counting the number of operations it would take to collapse the resulting graph to disconnected single ancestors.

How do I get a bunch of parsing models to test this idea out?

An interesting baseline for thinking about precision error is to consider the case of uniformly random answers. The student may be completely ignorant: you gave a college level test to kindergarten kids. Your questions were so hard or so incomprehensible (think Chris Kattan’s mumbling character giving a “uupp-uizzz” (pop-quiz) to this students) that students are just guessing.

Fig. 1: Precision error for random guessers

Fig. 2: Actual student answers

Note how the answer look uniformly gray. There really is no pattern in the students response. This is a uniform group answering this exam — the random answering makes everyone belong to the same group.

This second figure is actual student answers in a test. The grayness of the diagonal squares is varying. Some questions have a precision error lower than random! Others, just as high. The noisy (imprecise questions) are the ones that gave students the most trouble.

Back in December, Howard Schultz and I wrote a paper for the IEEE Computer Vision and Pattern Recognition 2008 conference. The paper, by the way, was rejected by the reviewers (this should form an interesting article at some future time). In the paper we calculate the horizontal decorrelation length for a collection of maps using a variogram technique.

The plots were not coming out right and Howard pointed out that I had not de-meaned the data. In particular, I had not de-meaned the average precision error. That is, the precision error for a model has a mean.

For some reason, I had thought that this mean error could be exactly solved with the precision error equations. It cannot. Given $m$ models, the precision error equations give you $m-1$ equations. So the mean value also has to be recovered with ${\ell }_1$-minimization.

How should one interpret this mean precision error? In the case of exams, the mean precision error for a question could be interpreted as the hardness or ease for the question. Hard questions will get answered correctly by few people, easy ones will be answered correctly by everyone.

This is what I observe in the introductory Physics class exam I have been analyzing. The hardest questions have the smallest mean error. The easiest ones have the largest mean error.

The correct way of defining the covariance matrix involves substracting this mean. That is, the entries should be of the form $⟨{\delta }_i{\delta }_j⟩-⟨{\delta }_i⟩⟨{\delta }_j⟩$ and not just plain $⟨{\delta }_i{\delta }_j⟩$ as I have been writing in previous posts.

Version 2.5 of WordPress has introduced a ‘’shortcode” API that allows you to write things like

[caption]My caption[/caption]

and have WordPress post-process this with functions that have been registered to handle the caption block. Is this the way to integrate MathML and Latex into WordPress?

As the number of models increase, the observed pattern in prediction discrepancies allows one to decide what is causing it assuming uniform uncertainty among all possible scenarios. The observed error pattern will be consistent with many different scenarios. In some scenarios, the noisy model predictions are due to the model being correct and the other models being incorrect. In other scenarios, the model is incorrect and the other models are correct. The hypothesis I want to prove is that the “mass” (the number of states) that corresponds to assuming the model is incorrect becomes larger than the one assuming it is correct.

Precision error is a measure of the variation in the predictions of a collection of models. If there are no variations — all the models agree. There is no precision error. One is perfectly in focus as far as one can tell. But, of course, scientific models disagree. So who is to blame? Is it the data or is it the algorithms used to process the data (the models). Having enough models allows you to do decide who is to blame.

Consider the case of a piece of data used to train one of the models that always lead to a disagreement, no matter what algorithm is used to process it. Who is to blame in this case? The optimal choice seems to me to be to decide that the data is bad.

Now consider an algorithm that always disagrees with all the other models no matter what set of predictions are compared. This seems to suggest that the model is wrong, not the data.

In both these cases, the availability of a large number of models is what allows one to distinguish the two cases. Real data will not be as stark as the examples above. Here is where Fourier analysis and probability theory come in. As the number of models increases one is able to disentangle the two. For small number of models, blaming the data or the model would explain the observed variation equally well. As the number of models increase, assigning blame becomes asymmetric!

This is sort of like the “Is it me or is him/her?” question. Comparing ourselves to only one other person does not allow us to decide who is the crazy one. But the more people we interact with, the sooner we realize who is to blame.

I’ll try to come up with a simple example with a few models to illustrate the point mathematically in a later post.