Proposed Manuscript Chronology

[Jorge_Stolfi]

The authors of that paper DID recover a gradient from that horseshoe that matches up almost perfectly with established indexes of liberalism vs conservatism. How do you explain that if it contains no sequential ordering?

How are those "indexes of liberalism vs conservatism" computed? Perhaps from ... the way those representatves vote?

Sure, for any data set and any axis, the data points "contain" a sequential ordering along that axis.  See again the book example: if you measure the height and width, the books will have a sequential ordering along the height axis, and also a sequential ordering along the width axis.  And one may observe that the two variables are strongly correlated, and that would be a significant observation.  But the ordering along either axis will say nothing except the banal observation that any set of numbers "contains" a sequential ordering.

Have you noticed the following comment in a previous post of mine?

Let c[1], c[2],... c[m] be any m data points of R^d, and p[1], p[2], ... p[m] be any m points of the plane R^2, in any order.  If d >= m, there is an affine  projection of R^d to R^2 that projects each c[k] to p[k].

Can you see what this fact implies about the "Guttman Horseshoe" and the page analysis?

In particular, if you have 240 pages of any book, and for each page you compute any 256 independent statistics, that fact implies that there is a projection of that data onto the plane that will produce the following plot:
   
In fact, for any of the 240! possible assignments of the 240 pages to the 240 dots in that plot, there is a projection that takes each page 256-vector to its assigned dot.

Another way of looking at this fact is that doing "agnostic" multivariate data analysis is likely to produce meaningless results if the number of data coordinates is greater than (or even close to) the number of data points.  Like fitting a polynomial of degree 10 on 12 noisy data points.   

Moreover, the idea of extracting some "intrinsic sequential ordering" for a set of data points is equivalent to identifying some "principal" axis of variation.  It has the problem that the result cannot be invariant with respect to linear transformations of the data vectors.  A simple change of scale along some axis can radically change the direction of such a "principal axis" (like that given by PCA) -- and consequently the "intrinsic sequential ordering" of those points.

Consider again that four-cloud example that I just posted.  Since the centroids are the vertices of a regular tetrahedron in R^4, any ordering of the four clouds is equivalent to any other.  But  for any of the 4! = 6 possible orders of the centroids there is a  linear transformation of R^4 -- a modest stretching in the proper direction -- that causes the "principal axis" of the data set to be such that, along that axis, the clouds are clearly sorted along that axis
   

Thus the concept of "principal axis" is useful only when the Euclidean metric is meaningful for the data space.  Like, when the data points are points of physical 3-space, where the Euclidean distance has a special meaning.  Then only linear transformations of the data that preserve that metric allowed; and then one can define "princpal direction" in a way that commutes with those transformations.  

In contrast, when the Euclidean metric is not meaningful for the data space, the concept of "principal direction" is meaningless too.  That is the case, in particular, when the coordinates of the data vectors are measured in different arbitrary units, like (length,mass,temperature),.  A mere change of unit on any axis can completely change the direction of the "principal direction" determined by PCA, SVD, or any other method.

And this is almost certainly the case for those 256  page statistics that you said you are using.  If they are frequencies of specific words, characters, or digraphs, each statistic has a different amount of noise, hence a change in its value is not equivalent to the same change in the value of some other statistic.

A more meaningful concept, because it is invariant under linear transformations of the data, is the concept of "linear separator" of two sets X, Y of points of R^d.  It is an oriented hyperplane in R^d that maximizes some measure of how accurately it separates the two sets, like the number of X points on the positive side plus the number of Y points on the negative side.  This measure can be taken as the "linear separability" of the two sets.  It is invariant under any linear transformations of the data space, not just isometries.

And, for page statistics typically used in the VMS page order analysis, the clouds of any two major sections have high linear separability.  Even sections that appear consecutive in that "Guttman Horseshoe" plots.  There is a hyperplane in the data space that separates the two clouds with only a small number of pages on the "wrong" side.

Moreover, if one projects the data points of those two sections on the axis orthogonal to that hyperplane, and builds histograms of those projections, one will get two well separated Gaussian-like humps, with a low valley between them.  Meaning that the two sections are not a slice of a single continuous "smoke trail", but two independent clouds, that may overlap to some extent.

Another important point is that most popular methods of determining "principal direction", like PCA or SVG, will not reliably identify the direction S of linear separation (the axis othogonal to the linear separator).  That is because those method are designed under the assumption that the Euclidean metric of the data space is meaningful.  The linear axis S also not the direction of the line between the two centroids.  To find S one must use algorithm that will specifically look for it.

Here are two clouds of points on the plane R^2 that are almost completely separated by an hyperplane (the green line), with a clear band of low density along that separator. 
   
Note that the principal direction determined by PCA (the largest eigenvector of the covariance matrix) and the centroid-to-centroid direction CCD are useless, because they are almost perpendicular to the direction SEP along which the clouds are seen to be separated.

All the best, --stolfi