A New Coefficient of Correlation
arxiv.org
arxiv.org
- it's always fun when a new equation or formula is discovered, doubly so when it is very practical
- actually really easy to wrap your head around it
- seems very computationally efficient. Basically boils down to sorts and distance
- not limited to strict numeric fields ( integers and reals). Anything with an ordering defined can act as your Xs/Ys: characters, words, complex/vectors (under magnitude). I think you could even apply it recursively to divide and conquer high dimensional datasets.
- looks useful in both LTI and non stationary signal analysis
- possible use cases: exoplanet search, cosmology in general, ecology, climate, cryptanalysis, medicine, neuroscience, and of course, someone will find a way to win (more likely lose) money on stonks.
Pearson and other correlation coefficients are linear, O(n), sorting would incur logiarithmic multiplier O(NlogN).
Thus, it is not computationally efficient.
To break ties randomly one has to have good random number generator, which is a problem in itself.
Finally, if you want to have differentiable version of this correlation coefficient, you will need to use sorting networks which are O(Nlog^2(N)).
But, it is a cool idea nevertheless, it brings up use of ranking in statistics and there are ties to other areas of the statistical science.
For example, it appears that you can more efficiently prune language models if you use rank metric than probability [1].
That doesn't seem a deal breaker to me. Sure if you're dealing with billions of data entries it will be 9 times slower, but throwing 9 times more computational power to solve a problem is far from something unheard of nowadays.
Closer to 30 times slower, as the logarithm in sorting complexity is a binary rather than decimal one.
Take the B-tree example, with 4KB pages, you can fit 1000 integers in there for a branching factor of 500, and a performance multiplier of just over 3.
We can track the rank of newly sampled pairs in LogN using something like an order statistic tree:
https://en.wikipedia.org/wiki/Order_statistic_tree
But I guess the problem is that with each new pair, O(n) pairs could change their contribution to the correlation coefficient.
There are several discussions here in HN about PRNGs of different kinds and people still want to invent new ones. Why? Because old ones do not satisfy them in full.
Returning to the problem at hand. How many consecutive ties do we expect? This would helps us to define how many bits should we extract from state - for N expected consecutive ties we should extract 2log_2(N) bits or more (birthday paradox). For 64K ties we need 32 bits, which is fair amount of state, 1/8 of typical PRNG discussed here.
Most PRNGs are splittable and this also brings the question "how does splitting affect bits generated?" Will these bits be correlated between splitted generators?
I definitely do not want correlation coefficient computation that produces close results for provably different sets due to correlation between tie-breaked sections filled with random numbers.
Just use a good PRNG to pick one of them :D
Is there some standard sense in which only (sub)linear algorithms are considered "computationally efficient"? O(nlogn) is fine for a very wide variety of practical uses.
Thus, this particular algorithm will not fit into, say, traffic analysis framework.
The point of it is to detect general dependencies, where Pearson only detects linear ones (cases where Y is completely determined by X but their Pearson correlation is 0 are trivial to construct). The "linear" in linear dependency isn't the same as the "linear" in linear complexity here, but it doesn't seem surprising for an algorithm that can detect more general dependencies to have worse than linear performance (and nlogn is pretty much the next best).
In the absence of a known algorithm with the same properties and better complexity, it doesn't seem unreasonable to call it "computationally efficient" when it comes with a complexity sufficient for most uses, rather than say quadratic or exponential.
There are several such algorithms.
Also, there is a comment with a link to paper comparing this correlation coefficient to some other: https://news.ycombinator.com/item?id=29690208
It looks like this "new coefficient of correlation" is not without flaws compared to others.
If you want to compute a correlation coefficient, you are probably happy to get eg 3 significant digits of precision. Thus you can use approximation algorithms and sampling.
> Thus, it is not computationally efficient.
That is not really what I meant. First, I personally consider NlogN the bar for "efficient" as far as algorithms go. Anything polynomial is inefficient, and anything better than NlogN is like, "super efficient" in my mind. Maybe that is a weird opinion, should I update my mental model? My reasoning is a lot of well known algorithms operate in better than polynomial but worse than linear time.
Second, sorting is a solved problem. Regardless of theoretical efficiency, we have so many ways to sort things, there is almost always really fast in practice ways of sorting data.
I didn't know about sorting networks, that is fascinating!
What is efficient and what ain't depends totally on context.
For example, for some domains even proving that a problem is in NP (instead of something worse), means that they consider the problem tractable, because we have good solvers for many NP hard problems in practice.
For other domains, you want O(1) or O(log n) or O(log* n) etc.
In general, P vs NP is such a big deal, because polynomial runtime is generally seen as tractable, and anything worse as intractable.
(Btw, O(n log n) _is_ a polynomial runtime, and so is O(N) or even O(1). Though I can see that as a shorthand of notation you are excluding them.)
I mean yes, technically n^1 is a polynomial, but normally this is just called linear. You hit the nail on the head with the last sentence. Here I'm using polynomial to basically mean "n^k, k>1". From a NP vs P point of view, P is considered tractable. But from a "actually writing libraries" point of view, I think software developers consider O(n^2) "kinda bleh" if it can be at all avoided. Also developers tend to give much more weight to the actual coefficients / parallelism potential / practical runtime. Neural networks have superlinear bounds everywhere, but GPU goes brrr.
Brass tacks, sorting some tuples and diffing the rank then reducing strikes me as likely to be:
- pretty fast even in the naive implementation
- sorting is a well trodden field
- easy to write things like shaders for
- amenable to speculative execution
- amenable to divide and conquer
So that is what I mean by efficient.
The “N” in NP means the solution can be produced by a non-deterministic Turing machine (i.e. a computer that can search the problem space in many dimensions in each step).
NP does not mean “non-polynomial” time to produce a solution, otherwise P != NP by definition. Instead P is a subset of NP.
The open question is if all decision problems with solutions verifiable in polynomial time can also be produced in polynomial time.
I know that the N stands for non-deterministic. Read my comment carefully, it agrees with everything you write here. (Or at least, does not disagree. It's silent on most of the intricacies.)
For many people moving a problem from NP to P means the same as having a tractable solution. See eg Scott Aaronson's writing on the topic.
Please take a spoon of your own medicine and read my comment even more carefully. I never suggested my comments were a contradiction to yours.
I added some information for bystanders that may have read your comment and come to (or reinforced) a wrong conclusion.
Yes, interpreting NP as non-polynomial is a common misunderstanding. Especially because it's 'sort-of almost right'.
By the same reasoning, economy would be a solved problem: you just need to have money.
Computing correlation by sorting a large amount of samples instead of reading them once is a cost difference that can make your data processing practically infeasible despite the efficiency of sorting algorithms.
(1) Rank coefficients can absolutely be updated online.
(2) There aren't many applications where an extra polylogarithmic factor is the difference between a good-enough algorithm and something too slow.
(3) The RNG is an implementation detail I'd probably omit. It's asymptotically equivalent to the deterministic operation of rescaling the sum of all pairwise absolute differences of Y values for each run of identical X values. If in your initial sort of the X values you instead lexicographically sort by X then Y then you can get away with a linear algorithm for computing those pairwise absolute differences.
Could you expand a little bit more on how to differentiate this coefficient? Since it is only based on ranks, it feels very non-differentiable.
Also, I would say that random number generation is a well-solved problem.
It would be great if someone who has Wikipedia edit privileges, can edit the Wikipedia article at [1] to describe/link how the Chatarjee's correlation coefficient solves many of the known limitation of Pearson's correlation coefficient. ;)
[1] https://en.wikipedia.org/wiki/Pearson_correlation_coefficien...
(especially second top-left diagram)
But the part that one would add would not necessarily be the definition of the coefficient ξn, but rather the interesting discussion at the beginning about what makes for a good correlation coefficient.
Regardless, I expect reviews are pretty straight forward for a concept that stands on its own like this one.
Thanks for sharing this. On the other hand the cited paper clearly relates to interdisciplinary peer review.
I am not sure how or if this can be transferred to mathematics.
https://arxiv.org/abs/1910.12327
This follow-up paper presents a related measure of conditional dependence that has a "natural interpretation as a nonlinear generalization of the familiar partial R2 statistic for measuring conditional dependence by regression."
The follow-up paper also provides some additional interpretive insights, I think.
My intuitive impression is that both of these are important developments.
I also have a very vague suspicion, based on the form of the function, that the correlation measure has some interpretation in terms of mutual information involving rank transformations of random variables.
"In statistics, ranking is the data transformation in which numerical or ordinal values are replaced by their rank when the data are sorted. For example, the numerical data 3.4, 5.1, 2.6, 7.3 are observed, the ranks of these data items would be 2, 3, 1 and 4 respectively. For example, the ordinal data hot, cold, warm would be replaced by 3, 1, 2."
https://en.m.wikipedia.org/wiki/Ranking
Also learned that a Spearman coeff is just the Pearson coefficient taken on the rank of the data, instead of on the raw data.
But whereas Pearson/Spearman takes the sum of product of data/mean differences (Σ(x-x̄)(y-ȳ)/σxσy) where x̄ is mean and σ=std. dev., Chatterjee takes sum of rank differences (3Σ(rᵢ₊₁-rᵢ)/n²-1), concerning just the ranks of the Y data after the X,Y pairs have been sorted by X.
But still missing the intuition for why the sum of difference of ranks is so useful or where the magic numbers come from.
I have a math (but not statistics) background, and am sometimes bewildered by the many correlation coefficients that float around when MI describes pretty exactly what one wants ("how much does knowledge of one variable tell you about the other variable"?).
So ... what am I not understanding?
A slightly critical review on the work van be seen here: https://academic.oup.com/biomet/advance-article/doi/10.1093/.... They argue that the older forms of rank correlation, namely D, R, and tau*, are superior. Nonetheless, it seems like a nice contribution to the stats literature, although I doubt the widespread use of correlation is going anywhere.
I try to remind myself that "it is just a model", as a corollary to "all models are wrong, some are useful." You are never dealing with the real world. And you are usually trying to estimate some future as of yet unobserved signal based on existing data. In other words, if your bins are reasonable and reasonably usefully accurate, you can build a working if not perfect system.
Don't try to optimize testing error performance to a value lower than the irreducible error in the system.
Biased samples produce biased results and this OP correlation coefficient might be sensitive to such an issue.
In one of the projects we were assuming gamma distribution (for speech processing) and sampling that is notoriously hard. Trying to use binned MI produced serious errors, as opposed to Minimim MSE one, even Maximum Likelihood did better (if noisy).
Spearman's correlation helps you understand monotonic/rank-order relationships between variables: "Is there a trend where increasing X tends to also increase Y?" (This way we can be just as good at measuring the existence of linear, logarithmic, or exponential relationships, although we can't tell them apart.)
Mutual information helps you understand how similar two collections of data are, in the sort of unstructured way that's useful in building decision trees. You could have high mutual information without any sort of linear or monotonic relationship at all. Thus it's more general while at the same time not telling you anything that would be helpful in building, for instance, a predictive multivariate linear model.
TLDR; More specific coefficients leverage assumptions about the structure of the data (eg linearity), which can help you construct optimal versions of models under those assumptions. Mutual information doesn't make any assumptions about the structure of the data so it won't feed into such a model, but it still has lots of applications!
https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.85...
https://en.wikipedia.org/wiki/Transfer_entropy
It is designed for time series, but can be adopted to a more general case. The advantage over MI is that with MI, you could only see that A and B are related, while TE can show that A dives B, but not the reverse.
With MI (the article claims that) you can have a coefficient of 1 without X being a function of Y.
[1] this means that this coefficient is intentionally not symmetric.
edit: was wrong about sha256
Technically this may not always be the case but it's very hard to construct a convincing counter example.
Example:
x1 = 1, y1 = 2
x2 = 1.1, y2 = 2
Here, y is a function of x, because if we know that x = 1, the we also know that y = 2. However, x is not a function of y, as we don't know what value x has given that y = 2.
I hope that made it more clear. Here, "function" simply means that every time we started with the same x, we also got the same y.
> counterexample = tibble(x = 1:6, y = c(1.1,-1.2,1.3,-1.4,1.5,-1.6))
> counterexample
# A tibble: 6 × 2
x y
<int> <dbl>
1 1 1.1
2 2 -1.2
3 3 1.3
4 4 -1.4
5 5 1.5
6 6 -1.6
> XICOR::calculateXI(xvec = counterexample$x, yvec=counterexample$y)
[1] -0.2857143
> -0.2857143 == 1
[1] FALSE
I think the abstract is a bit strong, it probably means "converges to" for a large repeating sample.
Quote: " On the other hand, it is not very hard to prove that the minimum possible value of ξn(X, Y ) is −1/2 + O(1/n), and the minimum is attained when the top n/2 values of Yi are placed alternately with the bottom n/2 values. This seems to be paradoxical, since Theorem 1.1 says that the limiting value is in [0, 1]. The resolution is that Theorem 1.1 only applies to i.i.d. samples. Therefore a large negative value of ξn has only one possible interpretation: the data does not resemble an i.i.d. sample."
You propose Y = f(X) = (-1)^X*(1+X/10) as your functional relation, which is measurable if X is discrete and indeed if we let x_n=n, then the limiting value of the estimator will be -1/2 not 1.
However, this is just a particular value of the estimator on a particular sample of (x,y). The theorem is an "almost surely statement", which means that it fails for a set of samples with 0 propbability.
Indeed, if we actually picked a random sample of (X, f(X)) with your f, then independent on the distribution on X, since X is discrete, we would expect to see many ties (infinitely many ties as the number of samples goes to infinity). This would mean that |r_{i+1}-r_i| is 0 for all but finitely many i and so the estimator would be 1.
This also covers the case of f being a hash function as mentioned before. Worse yet it only has finitely many different values so once again infinitely many ties.
The way the estimator is defined, it will take care of the (X, f(X)) case fairly easily as for a typical sample you will get x values that cluster and for a measurable function this implies that the resulting values will be close together and so the rank differences will be small.
This discussion probably wasnt included in the abstract since its fairly simple measure theory which most experts readimg tje article will be intimately familiar with
"it is not very hard to prove that the minimum possible value of [the proposed measure] is −1/2 + O(1/n), and the minimum is attained when the top n/2 values of Yi are placed alternately with the bottom n/2 values. ...Theorem 1.1 only applies to i.i.d. samples. Therefore a large negative value of [the measure] has only one possible interpretation: the data does not resemble an i.i.d. sample."
roenxi, I congratulate your example, it shows that you are working to understand the measure. "where does it break" is always a good question.
> doesn't that mean y is a predictable function of x
Sort of: as function of real numbers, sha256 is just some deterministic function. But point is its output "looks like" a uniform random variable for any reasonable input distribution i.e. as a function of random variables the input and output variables should have 0 correlation
This is similar to how, e.g., we generally assume that AES is unbreakable from a computational point of view, but if you want a statistically unbreakable cipher, your only (IINM) option is a one-time pad.
2. The result is an "almost surely" result, i.e. in the collection of all possible infinite samples, the set of samples for which it fails has 0 measure. In non technical terms this means that it works for typical random samples and may not work for handpicked counterexamples.
In our particular case let f=Sha256. Then X must be discrete, i.e. a natural number. Now the particulars depend on the distribution on X, but the general idea is that since we have discrete values, the probability that we get an infinite sample where the values tend to infinity is 0. So we get that in a typical sample theres going to be an infinitude of x ties and furthermore most x values arent too large (in a way you can make precise), so the tie factors l_i dominate since there just arent that many distinct values encountered total. And so we get that the coefficient tends to 1.
Comparing with something people barely know should be nice but people have a limited attention span so I would push to that anexes at best and focus on the more important parts.
"The formula is so simple that it is likely that there are many such coefficients, some of them possibly having better properties than the one presented below."
suggesting that the author is seeking to highlight a basic principle, not tune for a specific application.
For example: Cor(X, Y & Z)
I know you could run them pairwise but it’s possible Cor(X, Y) and Cor(X, Z) are close to zero but Cor(X, Y & Z) is close to 1.
Worth noting the author is a highly regarded professor at Stanford.
1. a mutual relationship or connection between two or more things
2. [Statistics] interdependence of variable quantities.
3. [Statistics] a quantity measuring the extent of the interdependence of variable quantities.
In statistics, correlation or dependence is any statistical
relationship, whether causal or not, between two random variables or bivariate
data. In the broadest sense correlation is any statistical association, though
it actually refers to the degree to which a pair of variables are linearly
related.
Also correlation very definitely means that knowing <x> tells you something about <y>. And vice versa. Like, for example: its value. Or at least a better idea of it than pure guessing without correlation.
Correlation, in general, just means some sort of statistical dependence: knowing x tells you something about y. It's often "operationalized" by computing Pearson's r: it's easy to do and there's lots of associated theory.
However, I would find it absolutely bizarre if someone showed a plot with obvious non-linear dependence and described it as "uncorrelated". In that case, the low r reflects a failure of the measuring tool rather than something being measured.
For example, you might have a radio signal (such as WiFi) that you want to receive. First step is that you have to pick that signal out of whatever signal comes out of your radio receiver: which will be the WiFi signal along with all sorts of noise and interference from other users. Typically the search will be done with the mentioned "Pearson's Correlation", using it to compare the received signal with an expected template: a value of 1.0 meaning the received signal is a perfect match with the template, a value of 0.0 meaning no match at all. If the wanted signal is present, interference, noise and distortion will reduce the result of the correlation to less than 1.0, meaning you might miss the WiFi signal, even though it is present.
This article is about coming up with a measure that gives a more robust result in the face of noise, interference and distortion. It's fundamental stuff, in that it has quite general application.
Skimming it now, this looks wild. Using the variance of the rank of the dataset (for a given point, how many are less than that point) seems... weird, and throwing out some information. The author seems legit tho, so I can't wait to try drop-in implementing this in a few things.
The neat thing about ranks is that, in aggregate, they're very robust. You can make an estimate of the mean arbitrarily bad by tweaking a single data point: just send it towards +/- infinity and the mean will follow. The median, on the other hand, is barely affected by that sort of shenanigans.
I'd like to learn more about the small sample properties. Proofs of asymptotics are necessary but less interesting. But the author's examples on example data sets look like it makes sense.
Let's make this more precise, and use R-squared (which this coefficient appears to be in some shape or form, since it is between 0 and 1, not -1 and 1). You look for relationships of the type y_i = f(x_i) + epsilon_i, where f is in some class of functions. Then this coefficient would be the ratio of the variance of f(x_i) and the variance of y_i. If you allow the class of functions to be arbitrary, there's no residual epsilon. So you need to specify somehow that class. In the case of the Pearson correlation, that class is the class of linear functions. If you want to generalize the Pearson correlation, you need to think of more general ways to specify the class of regression functions.
Assuming a linear relationship, if you know the correlation coefficient, you can predict unobserved values of y based on a known x with good accuracy.
y = ax + b + error
where strong correlation means error is small.
There are inherent flaws/assumptions to this approach which Peter Molenaar has done extensive work to critique (See Todd Rose's book on the subject). For anyone who understands the technique presented in this paper, does it also depend on the mean as a model like when calculating Pearson's r?
Another very useful consequence of being order-based, is that this new coefficient is much more robust to noise/outliers than the canonical correlation coefficient.
side note- it also isn't clear that you can group by diagnosis, see, for example, https://pubmed.ncbi.nlm.nih.gov/29154565/, which shows that even within diagnostic groups there is substantial individual variation.
def corr(x,y):
n = len(x)
an_array = np.stack((x, y), axis=-1)
sorted_array = an_array[np.argsort(an_array[:, 0])]
r = rankdata(sorted_array[:,1])
s = sum(np.abs(np.diff(r)))
return 1.0 - (3.0 \* s/(n\*n -1.0))https://cran.r-project.org/web/packages/XICOR/index.html
Edit: R code from Dr. Chatterjee's Stanford page is here - https://souravchatterjee.su.domains//xi.R
If you have never worked with R, the code seems clunky so I suggest checking out Python implementation on Github here:
https://github.com/czbiohub/xicor
The Python library is not from the original author though. But it's easy to read the code and it works with pandas as well.
Results seem to exactly match the R and Python implementation, so there will be a second pass focusing on performance, stability and support for categorical variables.
Pretty cool that it can also work for e.g. textual data in principle, as someone mentioned.
For instance, what does this mean? > μ is the law of Y μ is usually the mean or average. Is “law” something else?
The notation in this paper is totally standard.
EDIT: \mu there refers to a probability measure. Nothing to do with averages.
In terms of the notation, it seemed like the author actually tried to keep his paper accessible, so my complaint isn’t with the author. My gripe is more with math notation in general.
In my opinion, unless you’ve read the appropriate textbooks or taken the right classes, math notation is hard to learn. The symbols are hard to Google for. Integral symbols, R for real numbers, sigma, delta, the round E that stands for IN are not found on a standard keyboard so it’s challenging for a layman to Google and learn that notation on their own. Math evolved over millennia and the notation wasn’t constructed with SEO in mind, so I understand why things are the way they are, but it’s a stumbling block for the uninitiated trying to learn more advanced math. Maybe there are resources like math.stackexchange out there that I’m unaware of that would help make learning notation more approachable.