You are currently browsing the monthly archive for October 2012.

Four different snapshots (click to enlarge) from one of my latest books, recently published in Japan: Ajith Abraham, Crina Grosan, Vitorino Ramos (Eds.), “Swarm Intelligence in Data Mining” (群知能と  データマイニング), Tokyo Denki University press [TDU], Tokyo, Japan, July 2012.

Figure – Attractor basins (fig.2 pp.6 on Mária Ercsey-Ravasz and Zoltán Toroczkai, “Optimization hardness as transient chaos in an analog approach to constraint satisfaction“, Nature Physics, vol. 7, p. 966-970, 2011.)

Mária Ercsey-Ravasz and Zoltán Toroczkai have proposed a way of mapping satisfiability problems to differential equations and a deterministic algorithm that solves them in polynomial continuous time at the expense of exponential energy functions (so the discrete approximation of the algorithm does not run in polynomial time, and an analogue system would need exponential resources).

The map assigns a phase space to a problem; the algorithm chooses random initial conditions from within that phase space.  In the graphs above and below, they pick a 2-d subspace of the phase space and for each initial point in that space they illustrate 1) the particular solution the algorithm finds, 2) the corresponding “solution cluster”, an equivalence class of solutions that identifies two solutions if they differ in exactly one variable assignment, and 3) the time it takes to solve the problem.  Each row adds another clause to satisfy.

The especially interesting part of the paper is the notion of an escape rate,  the proportion of the trajectories still searching for a solution after a time t.  In a companion paper, they show that the escape rate for Sudoku combinatorial instances (The Chaos Within Sudoku, Nature, August 2012)  correlates strongly with human judgements of hardness. This escape rate is similar to the Kolmogorov complexity in that it gives a notion of hardness to individual problem instances rather than to classes of problems. Full paper could be retrieved from arXiv: Mária Ercsey-Ravasz and Zoltán Toroczkai, “Optimization hardness as transient chaos in an analog approach to constraint satisfaction“, Nature Physics, vol. 7, p. 966-970, 2011. (at arXiv on August 2012).

Figure – Attractor basins for 3-XORSAT (fig.8 pp.18 on Mária Ercsey-Ravasz and Zoltán Toroczkai, “Optimization hardness as transient chaos in an analog approach to constraint satisfaction“, Nature Physics, vol. 7, p. 966-970, 2011.)

Figure (click to enlarge) – Orders of common functions (via Wikipedia): A list of classes of functions that are commonly encountered when analyzing the running time of an algorithm. In each case, c is a constant and n increases without bound. The slower-growing functions are generally listed first. For each case, several examples are given.

“… words are not numbers, nor even signs. They are animals, alive and with a will of their own. Put together, they are invariably less or more than their sum. Words die in antisepsis. Asked to be neutral, they display allegiances and stubborn propensities. They assume the color of their new surroundings, like chameleons; they perversely develop echoes.” Guy Davenport, “Another Odyssey”, 1967. [above: painting by Mark Rothko – untitled]

Image – Reese Inman, DIVERGENCE II (2008), acrylic on panel 30 x 30 in Remix (Boston, 2008), a solo exhibition of handmade computer art works by Reese Inman, Gallery NAGA in Boston.

Apophenia is the experience of seeing meaningful patterns or connections in random or meaningless data. The term was coined in 1958[1] by Klaus Conrad,[2] who defined it as the “unmotivated seeing of connections” accompanied by a “specific experience of an abnormal meaningfulness”, but it has come to represent the human tendency to seek patterns in random information in general (such as with gambling). In statistics, apophenia is known as a Type I error – the identification of false patterns in data.[7] It may be compared with a so called false positive in other test situations. Two correlated terms are synchronicity and pareidolia (from Wikipedia):

Synchronicity: Carl Jung coined the term synchronicity for the “simultaneous occurrence of two meaningful but not causally connected events” creating a significant realm of philosophical exploration. This attempt at finding patterns within a world where coincidence does not exist possibly involves apophenia if a person’s perspective attributes their own causation to a series of events. “Synchronicity therefore means the simultaneous occurrence of a certain psychic state with one or more external events which appear as meaningful parallels to a momentary subjective state”. (C. Jung, 1960).

Pareidolia: Pareidolia is a type of apophenia involving the perception of images or sounds in random stimuli, for example, hearing a ringing phone while taking a shower. The noise produced by the running water gives a random background from which the patterned sound of a ringing phone might be “produced”. A more common human experience is perceiving faces in inanimate objects; this phenomenon is not surprising in light of how much processing the brain does in order to memorize and recall the faces of hundreds or thousands of different individuals. In one respect, the brain is a facial recognition, storage, and recall machine – and it is very good at it. A by-product of this acumen at recognizing faces is that people see faces even where there is no face: the headlights & grill of an auto-mobile can appear to be “grinning”, individuals around the world can see the “Man in the Moon”, and a drawing consisting of only three circles and a line which even children will identify as a face are everyday examples of this.[15].

[...] People should learn how to play Lego with their minds. Concepts are building bricks [...] V. Ramos, 2002.

@ViRAms on Twitter

Archives

Blog Stats

  • 255,000 hits