Chronological Path Stability/Uncertainty Analysis

[Jorge_Stolfi]

ok, several questions here

Thanks for these answers!

P(h|g)= C(g,h) / sum_j C(g,j) I then combine the JS divergences between these conditional distributions. A row contributes only if it has at least 3 transitions in each profile. Excluded weights are not redistributed to the remaining rows.

Here "row" means a left character g, correct? So you consider only digraphs of characters g that occur at least three times on the page? 

Let G(p) be the set of g characters that qualify for a page p.  Then for any page p and any g in G(p) you have a distribution H(p,g), a vector of M probabilities P(h|g), where M is the size of the alphabet you are using.  Check?  

How do you combine those vectors into the vectors of 256 numbers that you feed to MDS?

Then to measure the distance of two pages p,q you compute

• NP33dist(p,q) sum{ Jdiv(H(p,g),H(q,g)) : g in G(p)∩G(q) } / |G(p)∩G(q)|
  

Is that right?  

In my model, pair dependent weights and row exclusions mean it is not ordinary JS on one fixed probability vector. It is probably better described as weighted JS dissimilarity, I do not claim all the guarantees of ordinary JS distance.

OK.

Near the center [of the prob simplex], small JS distances are approximately a constant multiple of Euclidean distances.

Yeah, I should have guessed that from symmetry. 

If i am trying to get to the heart of what you are asking with this line of inquiry, my guess would be something like: does the horseshoe and disputed ordering persist when sampling zeros/sparse rows/probability estimation is handled differently?

I did not have a specific aim, but yes, generally I worry about the impact of the measurement method on the results -- including clustering, alignment, and ordering of the data points.

The factor 1/p makes changes involving rare categories more influential. ... JS is finite but it is sensitive near zero probabilities.

This is why I asked about how the probabilities are estimated.  

Any way you estimate the probabilities P(h|g), the result will have an uncertainty that depends on how many times g occurs in the page.  If on two pages p,q there are 10 occurrences of "g" but 3 and 4 of "gh", respectively, intuitively those two pages are more similar on that particular digraph than if they had 1000 "g" and 300 and 400 "gh".  But the JS divergences and distances use the probabilities P(h|g) which are 0.30 and 0.40 in both cases.  

This obliviousness to the counts is already a problem for interpretations.  But the sensitivity of JS metric to small probability values makes the problem worse.  That might justify using the Bayesian estimates of P(h|g) instead of the simple frequencies, since it would ensure that all probabilities are nonzero.

In particular, if g does not occur on a page at all, the Bayesian P(h|g) will be 1/M for all h (not 0/0).  Then you should not have to exclude any rows. But ideally one should also keep track of the uncertainties, and use them to compute weights for MDS, curve fitting, etc.  But that looks like a huge complication... 

When mapped back to probabilities, the geodesics are generally curved.

This may have a bearing on the question of how close to alignment three or more sections are.  

If the sections are mapped to points of R^256 and measured with the Euclidean metric,  alignment would mean the obvious thing -- they lay near some straight line of R^256.  But we could also compare their prob vectors with JS distance and check how much Jdist(A,B) + Jdist(B,C) is equal to Jdist(A,C).  This alignment criterion could disagree with the Euclidean one.  Which one would be right?

Can JS distance be represented as Euclidean DIstance? Yes, in Hlibert space, but not generally in R^D or R^D-1.

If this mapping existed, then we could apply it and work with Euclidean metric -- which we understand better.  Or less poorly...

you still have not gotten back to me on the last test you suggested that I ran.

Sorry, which one was that?  You did several...

All the best, --stolfi