5
$\begingroup$

I'm erring on the side of conservatism asking here rather than MO, as it is possible this is a complex question.

"Big Data" is the Silicon Valley term for the issues surrounding the huge amounts of data being produced by the global IT structure. Advanced mathematics is starting to pay attention to this, with very early thoughts on topological approaches. For example, see the Wiki here.

But one obvious way to think about patterns in Big Data is as polychromatic colored complete graphs: let the vertices be your data, let the edges represent relations between data, and let the colors be specific relations (which are the objective of Big Data visualization), with some neutral color representing no relation.

By the very definition of Big Data and Ramsey Theory, this virtually guarantees the existence of monochromatic complete subgraphs which may be nothing but spurious relations that must exist because of Ramsey Theory.

I am NOT a graph theorist in any way. So what I am asking specifically is this:

Are there other techniques that can be overlayed on to a graph theoretical approach that add information that the monochromatic subgraphs are real "signal" and not Ramsey noise? Or, am I misunderstanding, and the Ramsey structures are not actually noise?

$\endgroup$
6
  • 1
    $\begingroup$ The Ramsey subgraphs are mostly pretty small compared to the full graph. I imagine if you get a sizable monochrome subgraph, you can be confident it's not noise. $\endgroup$
    – Gerry Myerson
    Oct 20, 2013 at 0:15
  • $\begingroup$ @GerryMyerson: That seems reasonable, but is there some rigor around your conjecture? Again, I'm not a graph theorist, so are you suggesting there are known bounds, perhaps probablistic, that say how large Ramsey subgraphs are expected to be? This would be a good test for signal vs. noise should it exist. $\endgroup$
    – user452
    Oct 20, 2013 at 0:19
  • 1
    $\begingroup$ Computing Ramsey numbers is notoriously difficult, even in the 2-color case, and the known upper and lower bounds for them are generally far apart. But there are known upper and lower bounds, and I think even the worst bounds would say a graph has to be enormous to guarantee, say, a monochrome $K_{100}$. But my expertise on the question only runs to vague impressions; best do some study on your own of what the known bounds are, and what they imply for your question. $\endgroup$
    – Gerry Myerson
    Oct 20, 2013 at 0:47
  • $\begingroup$ @GerryMyerson: Thanks, that's a good next step. But it seems like good and bad news. The good news is that there may be usable bounds. But the bad news might be that Big Data is enormous enough to produce sizable Ramsey graphs. Unless enormous is really enormous; i.e. not reachable by computable processes. $\endgroup$
    – user452
    Oct 20, 2013 at 0:54
  • $\begingroup$ I want to answer but am afraid that you (OP) already know what I want to say and am actually talking about something else, so I will put this as a comment. Yes, you are right that there will inevitably be patterns in large data sets. Some people even use "Data Mining" as a perjorative term meaning exactly finding these spurious patterns by accident. One of our main defences against this is to split the data randomly into pieces (in many different ways) and then see how well a model or rule learned from one piece generalises to the other pieces. This idea is called cross-validation. $\endgroup$
    – Flounderer
    Oct 20, 2013 at 1:07

3 Answers 3

Reset to default
8
$\begingroup$

As requested, I'll post the comment above as an answer:

The OP is right that there are inevitably patterns in large data sets, and in fact often ones of the sort that we want to find. Here are a couple of very common examples.

In statistics, traditionally you do "hypothesis testing" where you try to find evidence for or against the hypothesis that a parameter has a particular value, for example that the mean height of American males is 5'11''. You do this by measuring the mean height of a sample and then seeing if it is "significantly" different from 5'11''. The problem is, if your sample is big enough, it is always "significantly different", because significance, whatever that is, increases with the size of the sample.

Another example is finance, where people called technical analysts look for support and resistance patterns, which is where a price keeps declining after reaching a certain value (say \$20), and then bouncing back up again. This is evidence that people are selling when the price reaches \$20 and taking their profits. However, such patterns also very commonly appear in random walks, so it is often not clear whether they represnt anything real about the financial situation.

It is said that "If you torture the data for long enough, it will confess." Some people use the term Data Mining in a perjorative sense to refer to finding patterns which aren't really there, in a sense that all sufficiently large data sets should contain such patterns just by chance.

One of our main defences against this problem is to split the data randomly into subsets and look for patterns in one subset, then see whether they generalize to the other subsets. In machine learning, people say "training" instead of "fitting a statistical model" or "looking for patterns" and then talk about "validation". The idea is that the validation should show you how your model is likely to perform on unseen data. If your model learns a spurious pattern, then you hope that this will show up as a poor performance on the validation data. Such a model is said to be over-fitted.

Splitting up the whole data set into $k$ subsets and validating a model fitted to one of the subsets on the rest of the data, and doing this $k$ times, once for each subset, is called $k$--fold cross-validation and is a common way of estimating how your model will perform on new data. This is why the Stackexchange statistics site is called Cross Validated.

The motivation for this procedure is that we really want to see how our patterns generlize to unseen data. If they are real patterns, they should show up in unseen data as well. But if we don't have any unseen data yet, we just pretend that some of the data we have got is unseen, and use it to validate the model. And it makes perfect sense, because usually our reason for wanting to fit models/find patterns/learn is to make predictions about new data that we haven't seen yet.

$\endgroup$
2
  • $\begingroup$ It could also happen that you happen to observe a real pattern,but it looks like an accident because the data is also evolving. $\endgroup$
    – Baby Dragon
    Oct 20, 2013 at 2:40
  • $\begingroup$ Thanks--I was aware of cross-validation, and now I'm understanding that the sets predicted by Ramsey theory are pretty small. So this is not as big a deal as I thought it could be, but I do enjoy the education. $\endgroup$
    – user452
    Dec 10, 2013 at 1:31
2
$\begingroup$

I don't know if "Big Data" has a Ramsey subgraph problem, but many, many big data practitioners have an "applied Ramsey Theory" problem.

The fundamental theorem of applied Ramsey Theory is:

Theorem: For any algorithm, if you look hard enough, and define terms loosely enough, you can find data that the algorithm fits perfectly.

This, of course, has a well-known corollary.

Corollary: For any algorithm for which you seek funding, there exists a data set that can be declared interesting enough to fill a proposal.

This phenomenon is particularly noticeable in many big data applications; semantic search is a wonderful example. Often, you find researchers that see an interesting problem but don't have the sophistication to tackle it (because the sophistication may not even yet exist). So they create frameworks, and then create problems on those frameworks, while eliding any discussion of the degree to which the framework matches reality.

Of course, they're very good at creating problems within frameworks and then solving them, but it is not yet clear that they've actually manifest progress towards any true mathematical understanding.

That said, a foundation of mathematics is understanding simpler cases to the ones that are interesting, so it may be that what's being done in the "big data" world is indeed very interesting. But I haven't seen any wonderful breakthroughs yet, despite seeing many wonderful solutions to problems that don't actually exist.

$\endgroup$
1
$\begingroup$

Ramsey's theorem has nothing to say about real data sets, which contain much bigger structures and anti-structures than the theorem predicts, and it only predicts that at least one must exist.

Giant monochromatic anti-structures (such as tens of millions of people on earth none of whom are friends with each other) are there because the structure is sparse. Monochromatic structures far larger than what might have been forced by Ramsey theorem (had there not been anti-structure) are there because of the small world phenomenon, where people related to you are likely to be related to each other.

$\endgroup$
7
  • $\begingroup$ Do you have a source for the "sparse" comment on anti-structures? This sounds interesting, but might also be a Big Data impediment unless there are ways to tell anti-structures apart (which I do realize is the whole point of this!) $\endgroup$
    – user452
    Dec 10, 2013 at 1:27
  • 1
    $\begingroup$ Take the population of the Earth, and friends/nonfriends to be the structure and nonstructure. The number of friends (even social network "friends") for most people is a tiny fraction of the population, so the density of edges in the graph is small. You can trivially construct a huge clique of antifriends by taking the least popular person, removing them and their friends from the population, then take person remaining with the smallest number of friends, etc. If the typical number of friends is under 1000 you have found at least some millions of people who are all anti-friends. $\endgroup$
    – zyx
    Dec 10, 2013 at 1:32
  • 1
    $\begingroup$ Whereas Ramsey theorem predicts that if there is no group of $k$ mutual friends, for $k$ in the range of 15 to 20, then we have $k$ mutual anti-friends. But the algorithm I described would give you millions. $\endgroup$
    – zyx
    Dec 10, 2013 at 1:36
  • $\begingroup$ I could be wrong but this example may not be addressing my concern. Often times, we do not know the pattern we are looking for, and in that case I wondered because of Ramsey whether that made task of finding a "real" harder. I'm now convinced it does not owing to the size issue you raised. But in your example, we know what we are looking for. In this latter case, would that change your answer? $\endgroup$
    – user452
    Dec 10, 2013 at 1:42
  • 1
    $\begingroup$ If you first find the pattern (or pick the nicest of several similar patterns) and then try to determine its significance, that can certainly be a problem. But the impressive-looking patterns that turn out to be impostors will not be from Ramsey theory, for the reasons already discussed, and also because RT is about what is absolutely true in the worst case, while falsity of patterns is about what is usually true in the typical case. $\endgroup$
    – zyx
    Dec 10, 2013 at 21:16

You must log in to answer this question.