Surprising preference for simplicity found in common model

March 12, 2018 by Lisa Zyga, Phys.org feature
Examples of simplicity bias in RNA sequences, circadian rhythms, and financial models. The higher the complexity of an output, the lower the probability that the output will be generated. Credit: Dingle, et al. Published in Nature Communications

Researchers have discovered that input-output maps, which are widely used throughout science and engineering to model systems ranging from physics to finance, are strongly biased toward producing simple outputs. The results are surprising, as naïvely there is no reason to suspect that one output should be more likely than any other.

The researchers, Kamaludin Dingle, Chico Q. Camargo, and Ard A. Louis, at the University of Oxford and at the Gulf University for Science and Technology, have published a paper on their results in a recent issue of Nature Communications.

"The greatest significance of our work is our prediction that simplicity bias—that simple outputs are exponentially more likely to be generated than complex outputs are—holds for a wide variety of systems in science and engineering," Louis told Phys.org. "The simplicity bias implies that, for a made of many different interacting parts—say, a circuit with many components, a network with many chemical reactions, etc.—most combinations of parameters and inputs should result in simple behavior."

The work draws from the field of algorithmic information theory (AIT), which deals with the connections between computer science and information theory. One important result of AIT is the . According to this theorem, when a universal Turing machine (an abstract computing device that can compute any function) is given a random input, simple outputs have an exponentially higher probability of being generated than complex outputs. As the researchers explain, this result is completely at odds with the naïve expectation that all outputs are equally likely.

Despite these intriguing findings, so far the coding theorem has rarely been applied to any real-world systems. This is because the theorem has only been formulated in a very abstract way, and one of its key components—a complexity measure called the Kolmogorov complexity—is uncomputable.

"The coding theorem of Solomonoff and Levin is a remarkable result that should really be much more widely known," Louis said. "It predicts that low-complexity outputs are exponentially more likely to be generated by a universal Turing machine (UTM) than high-complexity outputs are. Since anything that is computable can be computed on a UTM, that is a pretty amazing prediction!

"However, the coding theorem has remained obscure because UTMs are rather abstract, because it can only be proven to hold in the asymptotic limit of large complexities, and because the Kolmogorov measure used to determine complexity is fundamentally uncomputable. Our work circumvents these problems using a slightly weaker version of the coding theorem that is much easier to apply."

In the new, weaker version of the coding theorem, the researchers replaced the Kolmogorov complexity with an approximation complexity, which is computable, while still preserving the exponential preference for simplicity. The weaker coding theorem can be readily applied to make predictions regarding practical systems.

"We use the language of input-output maps, which may sound rather abstract," Louis said. "However, many systems studied in science and engineering convert some kind of input to some kind of output through an algorithm. For example, the information encoded in the DNA of an organism (its genotype) could be seen as input, while the organism's characteristics and behavior (its phenotype) could be seen as the output. In a set of differential equations, the input is the parameters of the equations, and the output is the solution of those equations, given some boundary conditions.

"We argue that if you randomly chose input parameters, then such systems are exponentially more likely to produce simple outputs over complex outputs. Since this prediction holds for a wide range of maps, we are making a broad claim. But that's one of its strengths. Our derivation does not require knowing much about how the map (or the algorithm) in question actually works.

"So the main significance of our work is that our weaker version of the coding theorem approximately maintains the exponential bias towards simplicity of the original coding theorem, but is much easier to apply in practice."

One consequence of the results is that it's possible to predict the probability of any particular outcome based on its complexity. Although a simple output is exponentially more likely to appear than a complex output, the researchers note that this does not necessarily mean that simple outputs are more likely to appear than complex outputs in general, since there may be many more complex outputs than simple ones overall.

To illustrate a few applications, the researchers used the modified coding theorem to analyze systems of RNA sequences, circadian rhythms, and financial markets, and showed that all of these systems exhibit the simplicity bias. In the future, they also plan to apply the results to computer algorithms, biological evolution, and chaotic systems. However, for a more intuitive explanation of what simplicity bias means, the researchers describe a scenario involving our primate relatives:

"Consider the well-known problem of monkeys typing on a typewriter," Louis said. "If the monkeys type in a truly random way, and the typewriter has N keys, then the probability of getting a particular sequence of length k is just 1/Nk, since there is a 1/N chance of getting the right keystroke at each of the k steps. Thus every sequence of length k is equally likely or unlikely.

"Now consider the case where the monkeys are typing into a computer program. They may then by accident type a short program that generates a long output. For example, there is a 133-character code in the programming language C that correctly generates the first 15,000 digits of π. So instead of 1/N15,000, which is the probability for monkeys getting this right on a typewriter, the odds are much lower, only 1/N133, that the monkeys generate π on the computer.

It turns out that most numbers don't have short programs that generate them, so the best the monkeys on the computer can do for these numbers is to type out a program like 'print number,' which is close the probability that they would get it right on a typewriter anyhow. But for simple outputs, the probability is much higher than for the typewriter. By definition, simple outputs are defined as those which have short programs describing them, and complex outputs are those that can only be described by long programs. So π is, by definition, a number with a low complexity, and therefore it is much more likely to be generated by monkeys typing into a computer program than many other numbers which are not simple.

"What the coding theorem does is to make this intuitive story quantitative. Short programs are more likely to be typed in at random, and since probabilities for length k programs also scale as 1/Nk, simple outputs are exponentially much more likely to appear than complex ones. Our contribution is to demonstrate how to easily calculate the exponential relationship between probability and complexity for many practical systems. What is nice is that you don't need to know much about the map (or equivalently the algorithm) to work out whether an output is likely to appear or not. To a good first approximation, the more compressible an output is, the more likely it is to appear upon random inputs."

Explore further: Coding theorem defines decoding error capacity for general scenarios

More information: Kamaludin Dingle, Chico Q. Camargo, and Ard A. Louis. "Input-output maps are strongly biased towards simple outputs." Nature Communications. DOI: 10.1038/s41467-018-03101-6

Related Stories

Classical problem becomes undecidable in a quantum setting

July 9, 2012

(Phys.org) -- As a testament to how differently things work in the quantum and classical regimes, physicists have found that a problem that is easily solved in a classical context cannot be solved at all in a quantum context. ...

How random is your randomness, and why does it matter?

September 19, 2016

Randomness is powerful. Think about a presidential poll: A random sample of just 400 people in the United States can accurately estimate Clinton's and Trump's support to within 5 percent (with 95 percent certainty), despite ...

As simple as random can be

September 19, 2016

A few weeks ago I was having a discussion about mathematical models for the prediction of the movements of the stock market. The question was whether there was any use to developing complex algorithms trying to predict these ...

Recommended for you

New study explores cell mechanics at work

June 19, 2018

It's a remarkable choreography. In each of our bodies, more than 37 trillion cells tightly coordinate with other cells to organize into the numerous tissues and organs that make us tick.

The secret to measuring the energy of an antineutrino

June 18, 2018

Scientists study tiny particles called neutrinos to learn about how our universe evolved. These particles, well-known for being tough to detect, could tell the story of how matter won out over antimatter a fraction of a second ...

18 comments

Adjust slider to filter visible comments by rank

Display comments: newest first

Eikka
4 / 5 (2) Mar 12, 2018
The probability of the monkeys typing in any program longer than "while(1){}" is essentially zero, because the computer locks into an infinite loop.

Using assembly code, the probability is even lower because you only have to make one jump command that refers to itself. In fact any longer program that doesn't contain an infinite loop is exceedingly improbable if you just keep hammering random binary symbols into a processor.

zorro6204
2 / 5 (1) Mar 12, 2018
Normally we strive to describe the universe in terms of objects and energy, but here's an example of another form of the structure of reality, the way it behaves. We've had experience with such laws before, for example the "invisible hand" of commerce, but perhaps this is a field that deserves more resources, as opposed to telescopes for example. To some extent what fills the universe is just a detail, the underlying laws are what matter.
forumid001
not rated yet Mar 12, 2018
Sounds surprising indeed, but is this simply because for all these systems studied the simple solutions (outputs) overwhelmingly outnumber the complex solutions?
Spaced out Engineer
not rated yet Mar 12, 2018
The probability of the monkeys typing in any program longer than "while(1){}" is essentially zero, because the computer locks into an infinite loop.

Using assembly code, the probability is even lower because you only have to make one jump command that refers to itself. In fact any longer program that doesn't contain an infinite loop is exceedingly improbable if you just keep hammering random binary symbols into a processor.


But the vehicle that executes such code by mechanism is then assumed to have no entropy, unless otherwise instructed. There seems to be a problem in the concrete account, where reality has noise innately, our computer model does not always. In other words, deterministic computation can not create Shannon information, though it can conserve(reversible) or destroy it (reduced in irreversible accounts).

So if we are running enough stuff, perhaps our clock can fill in, where our monkey cannot. Or at the least, get close enough :)
Eikka
not rated yet Mar 13, 2018
In other words, deterministic computation can not create Shannon information


That's the point. An actual computer is likely to lock up when given complex unfiltered inputs - rather than doing anything interesting, it just crashes and refuses any further IO. A monkey bashing away in a debugger isn't likely to develop -any- program, rather than just drive the machine into an inoperable state.

Meanwhile, a system like RNA/DNA, or the neurons in our brains have to deal with the onslaught of reality as it is. There's no filters that would drop off sequences that do the equivalent of "rm -rf" because having filters against everything that could "crash" you is much more complex than having a brain that just doesn't crash.

This is the reason why e.g. a completely deterministic algorithm, a computer program, cannot produce intelligence but merely the semblance of intelligence. The purely computational AI is a misnomer.
Spaced out Engineer
not rated yet Mar 13, 2018
This is the reason why e.g. a completely deterministic...
..... The purely computational AI is a misnomer.

Without knowledge of whether reality is deterministic, with more probable informal systems to emerging , I won't say.
Brains do crash, though I would not say psychosis is a form. Illusionism and perspectivism can be argued with as little as the Necker Cube. Seizures/strokes, I would consider a crash (assumption). It is difficult to dicotomize a chemical imbalance as exploratory, in having hath left the social construct, or bring something to it.

Error correcting codes exist in computation. Redundancy and additional space, or hamming distance permits handling a monkey. Are we using the VM in windows with training wheels or on the hunt in a Unix system? The length of time the monkey is permitted to code as is in question. Like the drunken stumbler, all finite codes will be generated, given enough time.
"rm -rf" does show the difference in tabular rasa
Eikka
5 / 5 (1) Mar 13, 2018
Without knowledge of whether reality is deterministic


If reality is deterministic, the question of intelligence in the first place becomes moot and it becomes irrelevant to discuss whether an AI is intelligent.

Any intelligence in a purely deterministic reality isn't a property of any individual part of it, but of the whole system, because everything is perfectly causally related. I.e. you're not smart - the universe is.

Brains do crash


Brains are robust against that, except brains that have flaws, like epilepsy, which is more alike the halting problem I'm describing where the computer stops because it runs into a looping state, or the instruction does something harmful like shutting down the program you're using to input data.
Error correcting codes exist in computation.

Any error correction would necessitate you to pre-define what is an error and what is data. That pulls the intelligence out of the AI and replaces it with yours.
Eikka
5 / 5 (1) Mar 13, 2018
What I think it's pointing out is that intelligence in general if any is to be discovered, can not be described as a turing machine. Brains can certainly operate as turing machines, and they can run into the same issues like getting stuck on logical paradoxes, but they don't have the same halting problem that causes a turing machine to stop in its tracks.

As far as evolution is concerned, it is first easier to come up with a rule based system that operates like a computer - but as the complexity of dealing with the real world increases such "expert systems" become increasingly fragile and increasingly cumbersome to maintain. So, the next level up is ditching the program and coming up with an actually intelligent system that is not based on simple IF-THEN reflexes, however complex they may be. In this way, intelligence supercedes the algorithm.

This difference is readily apparent in some animals, like how you can "hypnotize" a chicken to make it catatonic.
434a
not rated yet Mar 13, 2018
The prevalence of mental illness has always indicated to me that the brain is extremely susceptible to error. Inability to act as a functioning member of one's society could easily be classified as an uncorrected error.

And the causes are as diverse as the symptoms. Not only do we find genetic errors that cause mental ill health, we also have disease vectors, chemicals both external (nominally called drugs and toxins) and internal (hormones and neurotransmitters) and we can effectively teach mental illness through behavioural modification e.g. violence, abuse, poor role modelling etc.
There is no end of ways to make someone mentally ill.

The reality appears to be that the brain is born defenceless against socially engineered malfeasance, because it is that very plasticity that is the foundation for our ability to learn.

Evolution gave us the gift of intelligence, but evolution says nothing about the perfectness of the solution just that it is better than what came before.
Eikka
5 / 5 (1) Mar 13, 2018
The prevalence of mental illness has always indicated to me that the brain is extremely susceptible to error.

Compared to what?

Compared to just about anything we know of, human beings are remarkably robust in function. We don't bump our heads into streetlights like moths do, thinking it's the moon.

Inability to act as a functioning member of one's society could easily be classified as an uncorrected error


There's a multitude of deeper assumptions there.

For example, a society is a non-real entity that is subject to interpretation - who you count in, who you count out, or whether there exists overlappin societies etc... Likewise the rules of society depend on who you ask, and furthermore, any way you define society there will be those who "fail" to operate in it.

In a sense, there's no wrong way to think. Just ways that get you eaten by a lion, and ways that don't.
434a
not rated yet Mar 13, 2018
Compared to what?


Where did I suggest I was making a comparison? There are mental illnesses and mentally ill people. They form a significant portion of society. Accept that or have an F22 classifiable disorder, it's your choice or perhaps it isn't...we shouldn't judge.

Inability to act as a functioning member of one's society could easily be classified as an uncorrected error


There's a multitude of deeper assumptions there.


Yes, you have made many, this is merely an extension of them in the narrative of the brain you have presented.


In a sense, there's no wrong way to think. Just ways that get you eaten by a lion, and ways that don't.


I agree to a point, the issue is how lions have evolved and proliferated. Things were a lot simpler when the things that could cause you harm were a mere 400lb slab of muscle, teeth and claws, now less so.
Spaced out Engineer
not rated yet Mar 13, 2018

If reality is deterministic, the question of intelligence...
....perfectly causally related. I.e. you're not smart - the universe is.

That is certainly one interpretation of such an image.
Could be non-causally relational. The synchronous emergent.
The universe is the whole. The construct of intelligence is an open question for coupling and decoupling individuated solutions. Of course we are placing precedence on the ontology of Systems or System.

Any error correction would necessitate you to pre-define what is an error and what is data. That pulls the intelligence out of the AI and replaces it with yours

Hard to say. We can have useless error correction, just as extra stuff, in addition to some prior-ed completeness (objectivity). Neither parties would need the entire mathematical universe to be made fools of by some elquilibriationing external reality.
Spaced out Engineer
not rated yet Mar 13, 2018
What I think it's pointing out is that intelligence in general if any is to be discovered, can not be described as a turing machine…
logical paradoxes…..
…. next level up …..

The vehicle of a turning machine is of interest. A soft Turning machine that halts, due to nondeterminism and finiteness, in which we can know independence, is quite fanciful. A hard thesis Turing machine that is determinsistic, but can be partitioned, is also within the realm of gnosticism.

Paradoxes may not exist in a paraconsistent system. Fidelity is a bitch. truth or Truth?

The hierarchy is interesting. On the lowest level bootstrapping Markov processes is genius. On the higher levels, this becomes intractable. The anticipation engine must blossom modality. We do not need the whole to get close enough sometimes, where the simulated inner world is isomorphic to some boundless truth, even if such neuronal deloading takes an energetic expenditure to silence.

Eikka
not rated yet Mar 15, 2018
Where did I suggest I was making a comparison?


When you attach an adjective like "extremely", you're making a juxtaposition to something which is not extreme, and that demands the question: what is it?

Mental illness is a social definition as it depends on whether the individual is harmed by their mental condition - it's not about the contents of the thought but the consequences - and that's why the social environment and context has a lot to do with whether a person is mentally ill or not.

So it cannot be used to establish directly whether brains are prone to error in the same sense as computers are. In other social contexts, the error might not be an error at all. The appearance of "high prevalence of mental illness" is simultaneously a sign that the society does not tolerate deviance in thought and behaviour.

tl;dr: it's too easy to call someone crazy just for disagreeing with you
Eikka
not rated yet Mar 15, 2018
Hard to say.


Not really. An "error" is defined by your objectives, and if -you- don't have objectives, you don't know what error is, therefore you can't error-correct. Hence why, when a programmer makes an AI for a specific task, they define the objective and they define what is error and what is information, not the AI itself.

In other words, whatever fancy neural network or training method they're using, it's still the designer that defines what the behaviour should be and leaves no room for intelligence in the machine. In the end, this is just regular programming in a roundabout way: you come up with some function that takes input A and reliably transforms it into output B, and the function that's supposed to be intelligent has nothing to do with A and B - it's just shifting the bits around.

Eikka
not rated yet Mar 15, 2018
A soft Turning machine that halts, due to nondeterminism and finiteness, in which we can know independence, is quite fanciful.


Even a hypnotized chicken is intelligent enough that it eventually recovers from its stupor and stops staring at the ground.

But that's because it has other things to do than try to solve the intractable problem you set for it. It's a living being that gets hungry, falls asleep, forgets and gets distracted - it has its own purposes and goals in existence that are not set by an intelligent designer, but arise out of the reality of being a chicken. It has a brain that error-corrects to keep itself alive.

The reality of being a computer program is limited to what the programmers input to you, and what they expect out of you, so everything is dependent on their intelligence.
Eikka
not rated yet Mar 15, 2018
In that sense, whatever AI the programmers come up with, it cannot be intelligent because that would be against the point of such systems. The programmers need it to perform a definite task, not go off painting daisies or finding the meaning of life.

And that's a paradox. What we want out of AI is not intelligence, yet we call it intelligence.
antialias_physorg
not rated yet Mar 15, 2018
The prevalence of mental illness has always indicated to me that the brain is extremely susceptible to error

I think it's more of an issue that the brain is constantly active and barely being kept in check. The upshot is that it can react quickly to changing circumstances - the downside is that this means if any of the balancing mechanisms fail (or any of the parameters go into permanent saturation) you have a serious problem.

I sometimes liken this to how keeping muscle tension allows you to react to something quickly - while having your limbs in the same position but muscles relaxed makes does not. In both cases your posture may be identical, but in the latter case you're a pushover (quite literally).
But tension has the downside that if you cramp up or run out of energy you're screwed.

However, like any system, such a pre-stressed one can be gamed.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.