De Rerum Natura

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.

Questions in an exam are detectors of student competency. Students are detectors of the correct answers in a test. What is the variation in the student’s model of the correct exam? The precision error equations can be used to construct a covariance matrix for the students instead of the questions. What makes the difference is what is being averaged. When you want to use a test to tell you something about the questions, you average over the students. The covariance matrix is then indexed by the questions. When you want the test to tell you about the students, you average over the questions. The covariance matrix is indexed by students.

All of this suggests that it would be possible to build a completely parameter-less approach to detecting latent groups in students. This would be a different approach from that involved in topic models which use a specific probability distribution — the Dirichlet distribution. In this approach, you would assume a number of groups and arbitrarily assign students to these groups in a probabilistic fashion (60% group 1, 30% group 2, etc.). One can then see how well this group distribution predicts the observed covariance matrix by use of non-commutative harmonic analysis. Group assignment is thereby completely determined by the data — no parameters are needed.

I’ve been sick all week but today has been the worst. In between my sleeping hallucinations I have been thinking a lot about a proposal I’m currently writing on the use of non-commutative harmonic analysis to study mapping error patterns. It has become clear that the approach we are advocating at the AIRS lab is applicable to other areas of machine learning. Before I describe in additional detail what I mean by this let me present a graphic that abstractly represents the scientific enterprise:
The work I am describing here lies at the bottom of the picture. It is an algorithmic prescription for understanding the precision of our models given a dataset used to construct those models. I present this diagram to make clear the limitations of our work. It is not a description or explanation of errors in general. It is a technique for probing the error patterns in your system. The hard work is still left to you on how to apply it for a specific system that constructs models from data, and its usefulness is not guaranteed. The technique may tell you nothing interesting about your system.

We can view model creation as a black box. It takes data inputs and produces a model. The crucial point is that in some machine learning situations the number of models we can build is very large. Data is model-redundant.The redundancy is sometimes continuous, for example, the initial position of a camera or the weight of a Lagrangian term. But it can also be discrete — a finite set of documents or photographs. Changing the data inputs can then be used to probe the variation of a system’s model predictions. These variations will not be completely random (i.e. patternless). Some documents are more informative, some photographs give us a better view. Therefore we can use the symmetry groups associated with our data inputs to Fourier analyze the model variation. This model variation or model precision is informative about the quality of the data and can be used to reject bad data or discount lower quality inputs.

In a previous post I mentioned a way of Fourier analyzing the geometric precision error of DEMs. Today I realized that the scheme I proposed can only account for part of the error signal. The approach I proposed is correct but it can only capture one particular aspect of the total error. The simplest way of seeing this is to consider the $S_2$ symmetry group. This would be the one to use for $p=2$ photographs. From two photographs I can produce two DEMs: $A\to B$ and $B\to A$. The covariance matrix for these two DEMS would be a 2×2 covariance matrix of the form:
$$\left(\begin{array}{c}ab\\ bc\end{array}\right).$$
But the representation induced by $S_2$ on these two DEMs generates the matrices:
$$\left(\begin{array}{c}10\\ 01\end{array}\right)\text{and}\left(\begin{array}{c}01\\ 10\end{array}\right)$$
These two matrices cannot capture the three independent degrees of freedom in the 2×2 covariance matrix. Therefore, the induced representation cannot capture all of the possible errors that are observed when two photograps are used to produce two maps. But the representation would allow you to project out that component of the error that is explained by permutations of the images.

You would need at least $p=7$ photograps to have enough members in $S_p$ to completely model the variation in the DEMs observed when you use two photographs to produce a map. To understand the error that cannot be explained by the permutation group you would need to use three photographs to create a DEM. For $p$ photographs this would create $p*(p-1)*(p-2)$ DEMs. Since we can produce as much or even more than $p!$ DEMs from $p$ photographs, at some point we will always overwhelm the representational power of the symmetry group of $p$ objects (in this case, $p$ photographs). What error remains after we project out the component that can be modelled by $S_n$? I hypothesize that it would be error that can be further Fourier analyzed by using the symmetry group associated with the orientation and positions of the cameras. These parameters are themselves error prone and would, by virtue of their geometry, only induce certain error patterns.

This viewpoint of the errors would therefore view the observed error as one that can be captured by a succesive series of symmetry groups. One component would be that related to the finite group of $S_p$. Another component would be that one induced by translations and rotations of the camera positions and orientations. Like any real theory of errors, this approach would only peel away layers of error — always remaining would be a nugget of error that would require more and more complex models to decompose. The second law of thermodynamics is not violated!

The metaphor to x-raying in the title of this post comes from using Fourier analysis to study X-ray diffraction photographs by crystals. Crystals induce a certain periodicity on the scattered X-rays even when the sample is crushed into a powder. In other words, the randomly scattered blocks of crystal in the powder individually send a perfect difraction pattern. But the X-ray photograph records the mismash of the signals — the picture is blurry. Nonetheless, the bluriness has a symmetry component that comes from the periodic structure of the crystals and therefore Fourier analysis is able to pick the symmetry in the x-ray caused by the crystal periodicity. The Fourier decompositions for geometric errors are doing the same thing. There are many sources of errors in DEMs from aerial photographs. Some come from the fact that you used individual photographs to create the maps. This component of the error can therefore be accounted by studying representations of the symmetry group of p objects. Others come from uncertainty in the position or orientation of the camera when it took the photograph. These are explained by induced representations of non-abelian Lie groups like 3-D rotations in the space of covariance matrices.

I’ve finished the experiments with different reconstruction matrices for the DEM precision error and I get a rock solid result independent of which reconstruction matrix I use. So my hypothesis that randomness may be used to increase the precision error was wrong. In the process, however, I have finally understood how to use the symmetry group $S_n$ to Fourier analyze the covariance matrix. This has lead me to consider generalizations of our current approach that rely on the asymmetry of stereo matching algorithms.

The covariance matrix for our current procedure for creating maps is made up of photographic pairs. From two images, A and B, we create DEMs $A\to B$ and $B\to A$. So $n$ photographs lead to $n*(n-1)$ DEMs. The resulting covariance matrix can be Fourier analyzed by considering the representation induced by the symmetry group for $n$ objects (in our case the photographs) on the $n*(n-1)$ space. That is, for each element of the group, call it $\pi$, we define $M_{A\to B,C\to D}=1$ if $\pi (A)\to \pi (B)=C\to D$. This matrix representation can then be decomposed into its irreducible components to carry out the Fourier transform.

The above construction can then, in turn, be generalized by using the asymmetry of stereo matching algorithms. One constructs DEMs of the form $A\to B\to C$. This will not, in general, produce the same DEM as $A\to C\to B$ and so on. There will be $n*(n-1)*(n-2)$ ways of constructing these DEMs. A representation of the group can then be induced by generalizing the rule in the previous paragraph. Bringing in more photographs into the chain will induce higher and higher dimensional representations of the symmetry group. But note that all these representations are, by construction, smaller or equal to the $n!$ dimensionality of the symmetry group itself. Higher dimensional representations could be constructed because an arbitrary DEM like $A\to B\to A\to C$ will not be equivalent to the $A\to C$ DEM, for example. The matching process being imperfect will not return to the same pixel when the matching chain is of the form $A\to B\to A$.

None of these more complicated DEM production processes will lead to anything interesting if there were no errors in the matching process. If creating a 3-D model from photographs was perfect, all the DEMs would be error free and the covariance matrix would be proportional to the identity matrix. In other words, the Fourier decomposition of the covariance matrix is interesting because there is a symmetry to the errors. I’ll keep readers updated on the results of this line of inquiry as I obtain concrete results.

This week I am at the annual Neural Information Processing Systems Conference a fascinating conference that combines many of my scientific interests on machine learning, computer vision, statistics, and natural language processing. Last night I visited the poster by Jonathan Huang on efficient inference for distributions on permutations.

The paper considers the problem of how to reason probabilistically in a tracking task where you have sporadic tracking information of objects. Juang and co-authors end up using concepts like irreducible representations and Clebsch-Gordan coefficients. This may be unfamiliar concepts to the reader but to me they sound like a distant echo of all my physics training since these concepts are all over quantum mechanics and quantum field theory. What a cool paper! I’ll definitely be studying this paper since I have been interested in the issue of permutations with my work on recognizing answer patterns in multiple-choice exams.