13
$\begingroup$

While casually reading some mass market works on chaos theory over the last few years I began to wonder how various aspects of it could be applied to data mining and related fields, like neural nets, pattern recognition, uncertainty management, etc. To date, I've run into so few examples of such applications in the published research that I wonder if a) they've actually been put into practice in known, published experiments and projects and b) if not, why are they used so little in these interrelated fields?

Most of the discussions of chaos theory I've seen to date revolve around scientific applications that are entirely useful, but have little to do with data mining and related fields like pattern recognition; one of the archetypical examples is the Three-Body Problem from physics. I want to forego discussion of ordinary scientific applications of this kind and restrict the question solely to those applications which are obviously relevant to data mining and related fields, which seem to be few and far between in the literature. The list of potential applications below can be used as a starting point of a search for published research, but I'm only interested in those applications that have actually been put into practice, if any. What I'm looking for are known implementations of chaos theory to data mining, in contradistinction to the list of potential applications, which is much broader. Here's a small sampling of off-the-cuff ideas for data mining applications that occurred to me while reading; perhaps none of them are pragmatic, perhaps some are being put to practical use as we speak, but go by terms that I'm not yet familiar with:

  1. Identifying self-similar structures in pattern recognition, as Mandelbrot did in a practical way in the case of error bursts in analog telephone lines a few decades ago.
  2. Encountering Feigenbaum's Constant in mining results (perhaps in a manner similar to how string theorists were startled to see Maxwell's Equations pop up in unexpected places in the course of their research).
  3. Identifying the optimal bit depth for neural net weights and various mining tests. I wondered about this one because of the vanishingly small numerical scales at which sensitivity to initial conditions comes into play, which are partially responsible for the unpredictability of chaos-related functions.
  4. Using the notion of fractional dimensions in other ways not necessarily related to fascinating fractal curiosities, like Menger Sponges, Koch Curves or Sierpinski Carpets are. Perhaps the concept can be applied to the dimensions of mining models in some beneficial way, by treating them as fractional?
  5. Deriving power laws like the ones that come into play in fractals.
  6. Since the functions encountered in fractals are nonlinear, I wonder if there's some practical application to nonlinear regression.
  7. Chaos theory has some tangential (and sometimes overstated) relationships to entropy, so I wonder if there's some way to calculate Shannon's Entropy (or limits upon it and its relatives) from the functions used in chaos theory, or vice versa.
  8. Identifying period-doubling behavior in data.
  9. Identifying the optimal structure for a neural net by intelligently selecting ones that are most likely to "self-organize" in a useful way.
  10. Chaos and fractals etc. are also tangentially related to computational complexity, so I wonder if complexity could be used to identify chaotic structures, or vice-versa.
  11. I first heard of the Lyapunov exponent in terms of chaos theory and have noticed it a few times since then in recipes for specific neural nets and discussions of entropy.

There are probably dozens of other relationships I haven't listed here; all of this came off the top of my head. I'm not narrowly interested in specific answers to these particular speculations, but am just throwing them out there as examples of the type of applications that might exist in the wild. I'd like to see replies that have examples of current research and existing implementations of ideas like this, as long the applications are specifically applicable to data mining.

There are probably other extant implementations I’m not aware of, even in areas I'm more familiar with (like information theory, fuzzy sets and neural nets) and others I those I have even less competence in, like regression, so more input is welcome. My practical purpose here is to determine whether or not to invest more in learning about particular aspects of chaos theory, which I'll put on the back burner if I can't find some obvious utility.

I did a search of CrossValidated but didn't see any topics that directly address the utilitarian applications of chaos theory to data mining etc. The closest I could come was the thread Chaos theory, equation-free modeling and non-parametric statistics, which deals with a specific subset.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – whuber Jan 15 at 23:37
6
+50
$\begingroup$

Data mining (DM) as a practical approach appears to be almost complementary to mathematical modeling (MM) approaches, and even contradictory to a chaos theory (CT). I'll first talk about DM and general MM, then focus on CT.

Mathematical modeling

In economic modeling DM until very recently was considered almost a taboo, a hack to fish for correlations instead of learning about causation and relationships, see this post in SAS blog. The attitude is changing, but there are many pitfalls related to spurious relationships, data dredging, p-hacking etc.

In some cases, DM appears to be a legitimate approach even in fields with established MM practices. For instance, DM can be used to search for particle interactions in physical experiments that generate a lot of data, think of particle smashers. In this case physicists may have an idea how the particles look like, and search for the patterns in the datasets.

Chaos Theory

Chaotic system are probably particularly resistant to analysis with DM techniques. Consider a familiar linear congruental method (LCG) used in common psudo-random number generators. It is essentially a chaotic system. That is why it's used to "fake" random numbers. A good generator will be indistinguishable from a random number sequence. This means that you will not be able to determine whether it's random or not by using statistical methods. I'll include data mining here too. Try to find a pattern in the RAND() generated sequence with data mining! Yet, again it's a completely deterministic sequence as you know, and its equations are also extremely simple.

Chaos theory is not about randomly looking for similarity patterns. Chaos theory involves learning about processes and dynamic relationships such that small disturbances amplify in the system creating unstable behaviors, while somehow in this chaos the stable patterns emerge. All this cool stuff happens due to properties of equations themselves. The researchers then study these equations and their systems. This is very different from the mind set of applied data mining.

For instance, you can talk about self-similarity patterns while studying chaotic systems, and notice that data miners talk about search for patterns too. However, these handles "pattern" concept very differently. Chaotic system would be generating these patterns from the equations. They may try to come up with their set of equations by observing actual systems etc., but they always deal with equations at some point. Data miners would come from the other side, and not knowing or guessing much about the internal structure of the system, would try to look for patterns. I don't think that these two groups ever look at the same actual systems or data sets.

Another example is the simplest logistic map that Feigenbaum worked with to create his famous period doubling bifurcation.

enter image description here

The equation is ridiculously simple: $$x_{n+1} = r x_n (1 - x_n)$$ Yet, I don't see how would one discover it with data mining techniques.

$\endgroup$
  • $\begingroup$ (+1). I'll add that when you can pinpoint the equation that determines a chaotic system's behaviour, you can predict that behaviour completely, or close to it. We seldom can obtain an R-squared even >.5 in data mining / predictive modeling. $\endgroup$ – rolando2 Jan 24 at 19:30
  • $\begingroup$ +1 this is definitely complementary to the reply I've been readying for awhile now, which I'll post in a few hours. $\endgroup$ – SQLServerSteve Jan 24 at 21:36
4
$\begingroup$

The strangest thing I uncovered when reading up on chaos theory in order to answer this question was an astonishing dearth of published research in which data mining and its relatives leverage chaos theory. This was despite a concerted effort to find them, by consulting such sources as A.B. Ҫambel’s Applied Chaos Theory: A Paradigm for Complexity and Alligood, et al.'s Chaos: An Introduction to Dynamical Systems (the latter is incredibly useful as a sourcebook for this topic) and raiding their bibliographies. After all that, I was only to come up with a single study that might qualify and I had to stretch the bounds of “data mining” just to include this edge case: a team at the University of Texas performing research on Belousov-Zhabotinsky (BZ) reactions (which were already known to be prone to aperiodicity) accidentally discovered discrepancies in the malonic acid used in their experiments due to chaotic patterns, prompting them to seek a new supplier.[1] There are probably others - I am not a specialist in chaos theory and can hardly give an exhaustive evaluation of the literature – but the stark disproportion with ordinary scientific uses like the Three-Body Problem from physics would not change much if we enumerated them all. In fact, in the interim when this question was closed, I considered rewriting it under the title “Why are there so Few Implementations of Chaos Theory in Data Mining and Related Fields?” This is incongruent with the ill-defined yet widespread sentiment that there ought to be a multitude of applications in data mining and related fields, like neural nets, pattern recognition, uncertainty management, fuzzy sets, etc.; after all, chaos theory is also a cutting edge topic with many useful applications. I had to think long and hard about exactly where the boundaries between these fields lay in order to understand why my search was fruitless and my impression wrong.

The ;tldr Answer

The short explanation for this stark imbalance in the number of studies and deviation from expectations can be ascribed to the fact that chaos theory and data mining etc. answer two neatly separated classes of questions; the sharp dichotomy between them is obvious once pointed out, yet so fundamental as to go unnoticed, much like looking at one’s own nose. There might be some justification for the belief that the relative newness of chaos theory and fields like data mining explains some of the dearth of implementations, but we can expect the relative imbalance to persist even as these fields mature because they simply address distinctly different sides of the same coin. Almost all of the implementations to date have been in studies of known functions with well-defined outputs that happened to exhibit a few puzzling chaotic aberrations, whereas data mining and individual techniques like neural nets and decision trees all involve the determination of an unknown or poorly defined function. Related fields like pattern recognition and fuzzy sets likewise can be viewed as the organization of the results of functions that are also often unknown or poorly defined, when the means of that organization aren’t readily apparent either. This creates a practically insurmountable chasm that can only be crossed in certain rare circumstances – but even these can be grouped together under the rubric of a single use case: preventing aperiodic interference with data mining algorithms.

Incompatibility with the Chaos Science Workflow

The typical workflow in “chaos science” is to perform a computational analysis of the outputs of a known function, often alongside visual aids of the phase space, like bifurcation diagrams, Hénon maps, Poincaré sections, phase diagrams and phase trajectories. The fact that researchers rely on computational experimentation illustrates just how hard chaotic effects are to find; it’s not something you can ordinarily determine with pen and paper. They also occur exclusively in nonlinear functions. This workflow isn’t feasible unless we have a known function to work with. Data mining might yield regression equations, fuzzy functions and the like, but they all share the same limitation: they’re just general approximations, with a much wider window for error. In contrast, the known functions subject to chaos are relatively rare, as are the ranges of inputs that yield chaotic patterns, so a high degree of specificity is required even to test for chaotic effects. Any strange attractors present in the phase space of unknown functions would certainly shift or vanish altogether as their definitions and inputs changed, greatly complicating the detection procedures outlined by authors like Alligood, et al.

Chaos as a Contaminant in Data Mining Results

In fact, the relationship of data mining and its relatives to chaos theory is practically adversarial. This is literally true if we view cryptanalysis broadly as a specific form of data mining, given that I’ve run across at least one research paper on leveraging chaos in encryption schemes (I can’t find the citation at the moment, but can hunt it down on request). To a data miner, the presence of chaos is normally a bad thing, since the seemingly nonsensical value ranges it outputs can greatly complicate the already arduous process of approximating an unknown function. The most common use for chaos in data mining and related fields is to rule it out, which is no mean feat. If chaotic effects are present but undetected, their effects upon a data mining venture might be difficult to surmount. Just think of how easily an ordinary neural net or decision tree might overfit the seemingly nonsensical outputs of a chaotic attractor, or how sudden spikes in input values could certainly confound regression analysis and might be ascribed to bad samples or other sources of error. The rarity of chaotic effects among all functions and input ranges means investigation into them would be severely deprioritized by experimenters.

Methods of Detecting Chaos in Data Mining Results

Certain measures associated with chaos theory are useful in identifying aperiodic effects, such as the Kolmogorov Entropy and requirement that the phase space exhibit a positive Lyapunov exponent. These are both on the checklist for chaos detection[2] provided in A.B. Ҫambel’s Applied Chaos Theory, but most aren’t useful for approximated functions, such as the Lyapunov exponent, which requires definite functions with known limits. The general procedure he outlines might nonetheless be useful in data mining situations; Ҫambel’s aim is ultimately a program of “chaos control,” i.e. elimination of the interfering aperiodic effects.[3] Other methods like calculating box-counting and correlation dimensions for detecting the fractional dimensions that lead to chaos might be more practical in data mining applications than the Lyapunov and others on his list. Another telltale sign of chaotic effects is the presence of period doubling (or tripling and beyond) patterns in function outputs, which often precedes aperiodic (i.e. “chaotic”) behavior in phase diagrams.

Differentiating Tangential Applications

This primary use case must be differentiated from a separate class of applications that are only tangentially related to chaos theory. On closer inspection, the list of “potential applications” I provided in my question actually consisted almost entirely of ideas for leveraging concepts that chaos theory depends upon, but which can be applied independently in the absence of aperiodic behavior (period doubling excepted). I recently thought of a novel potenital niche use, generating aperiodic behavior to pop neural nets out of local minima, but this too would belong on the list of tangential applications. Many of them were discovered or fleshed out as a result of research into chaos science, but can be applied to other fields. These “tangential applications” have only fuzzy connections to each other yet form a distinct class, separated by a hard boundary from the main use case of chaos theory in data mining; the first leverages certain aspects of chaos theory without the aperiodic patterns, while the latter is devoted solely to ruling out chaos as a complicating factor in data mining results, perhaps with the use of prerequisites like the positivity of the Lyapunov exponent and detection of period doubling. If we differentiate between chaos theory and other concepts it makes use of correctly, it is easy to see that the applications of the former are inherently restricted to known functions in ordinary scientific study. There really is good reason to be excited about the potential applications of these secondary concepts in the absence of chaos, but also reason to worry about the contaminating effects of unexpected aperiodic behavior on data mining endeavors when it is present. Such occasions will be rare, but that rarity is also likely to mean that they will go undetected. Ҫambel’s method might be of use in staving off such problems though.

[1] pp. 143-147, Alligood, Kathleen T.; Sauer, Tim D. and Yorke, James A., 2010, Chaos: An Introduction to Dynamical Systems, Springer: New York. [2] pp. 208-213, Ҫambel, A.B., 1993, Applied Chaos Theory: A Paradigm for Complexity, Academic Press, Inc.: Boston. [3] p. 215, Ҫambel.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.