Universal Correlation measure — ranking correlations - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T19:27:58Z http://mathoverflow.net/feeds/question/105651 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/105651/universal-correlation-measure-ranking-correlations Universal Correlation measure — ranking correlations Jagra 2012-08-27T19:02:56Z 2012-08-27T19:02:56Z <p>I have time series data of experimental observations for two related processes. I want to measure correlation for use in further analysis.</p> <p>Correlation of the series changes over time and across different length sliding windows on the data. To clarify, I might want to look at correlation over 10, 20, 30, 40, ..., n periods, each of these essentially sliding windows across the data. Kind of analogous to looking at widows of different length simple moving averages.</p> <p>Historically and over future observations, one of these correlation windows will prove a better representation of the data than the rest. But the random nature of the underlying processes (whose distribution one may not know) makes settling on one window by evaluating the data historically an unsound approach.</p> <p><strong>Universal - A possible approach?</strong></p> <p>Information theory applied to the areas of data compression and portfolio allocation has produced what often gets referred to as a “Universal” approach to attacking a similar problem.</p> <p>The late <a href="http://en.wikipedia.org/wiki/Thomas_M._Cover" rel="nofollow">Thomas Cover</a>, a principle advocate for the idea, saw the universal approach as a general method for multi-variate optimization of random processes even where one had no idea of the underlying distribution.</p> <p>Cover's book, <a href="http://www.elementsofinformationtheory.com/" rel="nofollow">Elements of Information Theory</a>, looks at a couple of examples of this idea. Cover seeing this as an optimization technique led me to ask this question here rather than say a dedicated statistics site.</p> <p><strong>Example - Universal data compression</strong></p> <p>In Universal Data Compression, one can see that an internet router can’t know the optimal data compression algorithm to use prior to its actually reading the packet of information or stream of data. Universal Data Compression addresses the problem with the following steps:</p> <ul> <li><p>Ranks each of its available compression algorithms as to their effectiveness after each stream of data has passed through the router.</p></li> <li><p>Calculates the cumulative ranking for each of the compression algorithms</p></li> <li><p>Identifies the mean cumulative rank weighted compression algorithm.</p></li> <li><p>Uses this mean cumulative rank weighted algorithm on the next stream of data it receives.</p></li> </ul> <p>Note that the approach does not use a follow the leader strategy.</p> <p>Over time this method will asymptopically approach the effectiveness of the best single algorithm that one could have picked at the beginning. A Darwin quote captures the key idea behind a Universal approach:</p> <blockquote> <p>It is not the strongest of the species that survive, nor the most intelligent, but the one most responsive to change.</p> </blockquote> <p>Universal approaches keep one in a pretty good place most of the time, which does very well over time.</p> <p><strong>Universal Correlation</strong></p> <p>So it occurred to me that I might develop a related method, as kind of Universal Correlation</p> <p>with the following steps:</p> <ul> <li><p>Rank each correlation window’s effectiveness (more about this below) at each time step.</p></li> <li><p>Calculate the cumulative ranking for each of the correlation windows</p></li> <li><p>Identify the mean cumulative rank weighted correlation window (or the one nearest the mean).</p></li> </ul> <p>I'll then use this in another stage of analysis.</p> <p>Now my question</p> <p>This above seems straightforward and in keeping with other universal approaches, except I've become completely stumped by this key question: </p> <p><em>What measure can I use to rank each correlation window’s effectiveness at each time step?</em></p> <p>This may help clarify: At a given point in time, I have calculated correlation for some number of windows on the data up until that point in time (going back, 10 periods, 20 periods, 30, periods, ...).</p> <p>Now I need a measure to rank the effectiveness or accuracy of each of the time periods correlation relative to each other.</p> <p>Put yet another way: <em>What do I rank the measures of correlation against?</em></p> <p>...</p> <p>Some additional relevant work from information theory might include: universality with respect to piecewise constant compressors (or portfolios) to capture non-stationarity and universality with respect to all context trees up to some maximum depth to capture universality with respect to dependence on different history extents (the extents may be dependent on past data). The latter can be attained in some sense by using a state dependent universal compressor (or universal portfolio) for the maximum history. (See Ordentlich, Weinberger, &amp; Wu paper which explores some of this at: <a href="http://www.hpl.hp.com/techreports/2012/HPL-2012-114.pdf" rel="nofollow">Piecewise Constant Prediction</a>)</p>