Feeds:
Posts

## “Darwinian Evolution is a form of PAC (Machine) Learning”

Changing or increasing functionality of circuits in biological evolution is a form of computational learning. – Leslie Valiant

The title of this post comes from Prof. Leslie Valiant‘s The ACM Alan M. Turing award lecture titled “The Extent and Limitations of Mechanistic Explanations of Nature”.

Prof. Leslie G. Valiant

Click on the image above to watch the lecture

[Image Source: CACM “Beauty and Elegance”]

Short blurb: Though the lecture came out sometime in June-July 2011, and I have shared it (and a paper that it quotes) on every online social network I have presence on, I have no idea why I never blogged about it.

The fact that I have zero training (and epsilon knowledge of) in biology that has not stopped me from being completely fascinated by the contents of the talk and a few papers that he cites in it. I have tried to see the lecture a few times and have also started to read and understand some of the papers he mentions. Infact, the talk has inspired me enough to know more about PAC Learning than the usual Machine Learning graduate course might cover. Knowing more about it is now my “full time side-project” and it is a very exciting side-project to say the least!

_________________________

It is widely accepted that Darwinian Evolution has been the driving force for the immense complexity observed in life or how life evolved. In this beautiful 10 minute video Carl Sagan sums up the timeline and the progression:

There is however one problem: While evolution is considered the driving force for such complexity, there isn’t a satisfactory explanation of how 13.75 billion years of it could have been enough. Many have often complained that this reduces it to a little more than an intuitive explanation. Can we understand the underlying mechanism of Evolution (that can in turn give reasonable time bounds)? Valiant makes the case that this underlying mechanism is of computational learning.

There have been a number of computational models that have been based on the general intuitive idea of Darwinian Evolution. Some of these include: Genetic Algorithms/Programming etc. However, people like Valiant amongst others find such methods useful in an engineering sense but unsatisfying w.r.t the question.

In the talk Valiant mentions that this question was asked in Darwin’s day as well. To which Darwin proposed a bound of 300 million years for such evolution to occur. This immediately fell into a problem as Lord Kelvin, one of the leading physicists of the time put the figure of the age of Earth to be 24 million years. Now obviously this was a problem as evolution could not have happened for more than 24 million years according to Kelvin’s estimate. The estimate of the age of the Earth is now much higher. ;-)

The question can be rehashed as: How much time is enough? Can biological circuits evolve in sub-exponential time?

For more I would point out to his paper:

Evolvability: Leslie Valiant (Journal of the ACM – PDF)

Towards the end of the talk he shows a Venn diagram of the type usually seen in complexity theory text books for classes P, NP, BQP etc but with one major difference: These subsets are fact and not unproven:

$Fact: Evolvability \subseteq SQ Learnable \subseteq PAC Learnable$

*SQ or Statistical Query Learning is due to Michael Kearns (1993)

Coda: Valiant claims that the problem of evolution is no more mysterious than the problem of learning. The mechanism that underlies biological evolution is “evolvable target pursuit”, which in turn is the same as “learnable target pursuit”.

_________________________

Onionesque Reality Home >>

## Probably the Most Tragic Images of the Year

I picked up these images at Wired two days ago and just could not fit in the time to put them up earlier.

There is a remarkable quote by Einstein

“Two things are infinite: the universe and human stupidity; and I’m not sure about the the universe.”

It isn’t definite to me if I liked this quotation earlier. But I am NOW wholly convinced that I love it. And this new found unequivocalness for it is due to the following:

As a kid, I used to have a large collection of encyclopedias. I remember reading about the Aral Sea in the picture atlas, and that it mentioned that there was increasing salination of the sea water and that it would disappear in some decades.

Over the years that time, we were fed with doomsday scenarios all the while. Like all the coastal cities would be soon under sea due to rising ocean levels, and that the Himalayas would soon be ice free etc etc. Over a period of time you get fed up with such idle talk and since you don’t see anyone giving convincing answers, you tend to believe that nothing like that is true. Secondly, the eternal optimist that I am, I just probably wished that what that encyclopedia said about the Aral was some “minor” problem.

I last read about the problem many years ago and after that never came across anything on it. And just a couple of days back was shocked by these images. I have only one word for them : Tragic!

The images are from 1973, 1987, 1999, 2006 and 2009. The two recent images were released by the European Space Agency, the earlier ones were taken by the United States Geological Survey.

Aral Sea - 1973

Aral Sea - 1987

Aral Sea - 1999

Aral Sea - 2006

Aral Sea - 2009

[Image(s) Source : Wired Science]

The South Aral Sea, the remnant of the original lake that you can see to your left on the above image is also expected to vanish by 2020, thankfully the North Aral sea (the part on the right) has been saved due to a world bank funded dam project.

The Aral sea, once the world’s fourth largest lake at roughly around 68,000 sq kms is now just about one-tenth that size. The trouble started when it was decided by the Soviets in 1918 that the two rivers that drained into the Aral – The Amu Darya and Syr Darya would be largely diverted to the deserts to develop them into cotton growing lands. The Soviet plan worked and cotton became one of the most important exports from that area. By the 1960s massive amount of water was being diverted and the sea began to shrink steadily. And how that happened is spoken out loud by the pictures.

The death of the Aral is extremely sad. It’s death has left it’s once thriving fishing industry destroyed, the diverting of the rivers has mostly reduced the two rivers to a shadow of their former selves. The Aral served as a climate moderator in the largely arid lands there, it’s death might herald major environmental catastrophe in the region.

This is a prime example of what human stupidity could lead to and leaves me short of words to describe my anguish at the same.

It has a number of things to say:

Ignoring warnings which have clear proof is just plain stupidity. There is ample proof for example of climate change and its bad impact. For example, I have been visiting the Himalayas once every few years since 1991. And the change there is apparent, as compared to the 80s the glaciers that make up the Ganges have shrunk by several kilometers. I don’t know what the solutions are, nor am I comparing the Aral problem with it. I understand that the Aral was a different kind of a problem. Different because it was known to the Soviets that the lake would dry up from the start. Climate change can not be compared to it as we do not yet fully understand a number of things about it, so how effective the correctives would be is debatable. It would be for our good if that debate is settled soon with good and incisive scientific evidence.

It also is a comment on how totalitarian regimes can be dangerous. In such regimes, since a decision taken can not be opposed, such a decision could either lead to major dividends/progress as it would be implemented very rapidly or major catastrophe as was in the above case.  Soviet officials were aware that the Aral would sooner or later evaporate. In 1964 Aleksandr Asarin noted that :

“It was part of the five-year plans, approved by the council of ministers and the Politburo. Nobody on a lower level would dare to say a word contradicting those plans, even if it was the fate of the Aral Sea.”

Ofcourse he was right, there is rarely any way to convince or reason with or oppose supercilious totalitarian regimes even if their decisions are clearly suicidal. I am tempted to make a political comment on two present day countries (one a totalitarian state and one a liberal democracy) here, but would avoid the temptation.

Anyhow, the images above disturbed me enough to lose sleep.

_____

Onionesque Reality Home >>

## Giant’s Causeway Problem Solved

I came across a report on the new year eve of an old problem concerning the fantastic pattern formation and columnar jointing in nature  resolved. This particular problem  has been close to my heart as I elaborate in the paragraph below hence it was fun to read about it.

A Childhood Story: When I was in grade 2, my pappa got me a set of Childcraft Worldbook. It had some very interesting pictures. I was too young to understand the text completely but I used to love looking at the pictures. There was a very nice picture and a short accompanying article on the Giant’s Causeway in Volume 6 – Our World, on page 31 . However, I enjoyed reading this particular article as it had a story of the kind that kids are attracted to. It said that a lot of people before the turn of the century thought it was made by a giant, Fionn Mac Cumhail, to travel from Ireland to Scotland, and that this explained why the mostly regular hexagonal blocks that made up the Giant’s Causeway were so huge. I was fascinated by the story, but there was a short note at the end – It is believed that these columns were made by volcanic activity. I think fascination is fundamental to most science and art, when talking of science it has to be coupled with its seemingly opposite characteristic – skepticism. I think the line on volcanic activity making the structure did just that. Over the years whenever I saw a picture of the Causeway, I used to wonder how it (specifically the shapes) might have formed. And a PhD student has answered that question now!

____

The Giant’s Causeway: On the coast of northern Ireland, there is an area of about 40,000 interlocking basalt columns extending into the sea. Most of the columns are hexagonal and fit very neatly, the neatness of this structure inspired a number of legends of an “intelligent designer”.

[A view of the Giant’s Causeway on the northern Irish Coast : Image Source]

Click to Enlarge

[A view of the Basalt Columns on the Causeway: Image Source -BBC]

A structure similar somewhat to the Giant’s Causeway is the Devil’s Postpile in California.

What is known is that in the Paleogene period, there was intense volcanic activity in the region (Antrim), and that it is what formed the structures. However, what was not known was how was it that such specific forms, shapes were formed.

____

Research: PhD student Lucas Goehring and his adviser Dr Stephen Morris of the department of Physics  of the University of Toronto have been working on the problem above. They found out that the size of the columns that varies from one site to another varies as according to the speed of cooling of the lava from an eruption/flow. Using a combination (as required for such a task) of solid mathematical theory provided by Harvard Prof L Mahadevan, good experimentation and field work at the actual sites the researchers solved the problem of what determines the size of the columns.The field work involved making measurements in-situ i.e on the columns to determine at what rate had the lava cooled to form them.

The key to understanding and confirming their ideas was reproducing the phenomenon in the lab, that they did using simple materials. The idea was to use water and corn- starch, which cracks when dried and forms very similar columns as the ones talked about. Controlling the drying rate, a relationship between the size of the columns and the cooling rate was worked out.

[Image Source – Reference 1]

The above is the experimental setup for the one just described above. According to Goehring : “The columns are formed as a sharp front of cooling moves into the lava flow, assisted by the boiling of groundwater, As the front advances, it leaves behind a crack network which evolves into an almost hexagonal arrangement. This network carves out the columns.”. They found out that the slower the cooling the much larger the columns.

____

For more detailed information on the research carried out in this regard, I’d direct you to pages from Goehring’s website.

>> Models

He in the above pages gives a quite accessible picture of their findings and their work. Perfect, especially for somebody like me who is not trained in the field in which this research has been carried out, but are very interested in how it was done.

The findings of this work appeared in the December issue of the proceedings of the national academy of sciences.

____

____

Onionesque Reality Home >>

While searching for some methods for face representation in connection with my recent project, I lost the way clicking on some stray links and landed up on some beautiful art work involving Voronoi diagrams. I was aware of art work based on Voronoi diagrams (it kind of follows naturally that Voronoi diagrams can lead to very elegant designs, isn’t it?) but a couple of images on them were enough to re-ignite interest. It was also interesting to see an alternate solution to my problem based on Voronoi diagrams as well. However I intend to share some of the art work I came across.

———-

Before I get to the actual art-work I suppose it would be handy to give a very basic introduction to Voronoi Diagrams with a couple of handy applications.

Introduction: Voronoi diagrams are named after Georgy Voronoy (1868-1908), an eminent Russian/Ukrainian mathematician. A number of mathematicians before Voronoy such as Descartes and Dirichlet have been known to have used them, Voronoy extended the idea to $\mathcal{N}$ dimensions. The Voronoi diagram is a tessellation, or a tiling. A tiling of a plane is simply a collection of plane figures that fills the plane with no overlaps and no gaps in between. This idea can ofcourse be extended to $\mathcal{N}$ dimensions, but for simplicity let us stick with 2 dimensions.

[A pavement Tessellation/Tiling]

Definition: A Voronoi diagram is a special kind of a decomposition of a metric space which is determined by a discrete set of points.

Generally speaking for a 2-D case:

>> Let us designate a set of $n$ distinct points that we call sites as $\mathcal{P}$. i.e $\mathcal{P}=\{P_1, P_2\ldots, P_n\}$

>> We may then define the Voronoi Diagram of P as a collection $\mathcal{V}=\{V_1,V_2,\ldots, V_n\}$ of subsets of the plane. These subsets are called as Voronoi Regions. Each point in $V_i$ is such that it is closer to $\mathcal{P}_i$ than any other point in $\mathcal{P}$.

To be more precise:

A point $Q$ lies in the Voronoi Region corresponding to a site $P_i \in \mathcal{P}$ if and only if –

$Euclidean\_Distance(Q,P_i) < Euclidean\_Distance(Q,P_j)$ for each $P_i \neq P_j$

However it might be the case that there are some points in the plane that might have more than one site that is the closest to it. These points do not lie in either Voronoi Region, but simply lie on the boundary of two adjacent regions. All such points form a skeleton of lines that is called the Voronoi Skeleton of $\mathcal{P}$.

We can say that $\mathcal{V(P)}$ is the Voronoi Transform, that transforms a set of discrete points (sites) into a Voronoi Diagram.

———-

For more clarity on the above, consider a sample Voronoi Diagram below:

The dots are called the Sites. The Voronoi Regions are simply areas around a site but enclosed by the lines around them. The network of lines is simply the Voronoi Skeleton.

———-

Some Extensions to the above Definition: The above definition which is ofcourse extremely simple can be extended very easily[1] for getting some fun art forms.

Some of these extensions could be as follows [1]:

1. Since each region corresponds to a site, each site can be associated with a color. Hence the Voronoi diagram can be colored accordingly.

2. In the definition the sites were considered to be simply points, we can obtain a variety of figures by allowing the “sites” to be subsets of the plane than just points. We see, that if the sites are defined as simply points, the Voronoi skeleton would always be composed of straight lines. With this change there could be interesting skeletal figures emerging.

3. We could also modify the distance metric from the Euclidean distance to some other to get some very interesting figures.

This just shows the kind of variety of figures that can be generated by just a small change in one aspect of the basic definition.

———-

Constructing a Voronoi Diagram:

Let us forget the extensions that we spoke of for a moment and come back to the basic definition. Looking at the definition it  seems constructing Voronoi diagrams is a simple process. And it is not difficult at all. The steps are as follows:

1. Consider a random set of points.

2. Connect ALL of these points by straight lines.

3. Draw a perpendicular bisector to EACH of these connecting lines.

4. Now select pieces that are formed, such that each site (point) is encapsulated.

Voronoi Diagrams can be very easily made by direct commands in both MATLAB and MATHEMATICA.

———-

Voronoi Diagrams in Nature: It is interesting to see how often Voronoi diagrams occur in nature. Just consider two examples:

[Left: Reticulum Plasmatique (Image Source) Right: Polygons on Giraffes]

———-

Uses of Voronoi Diagrams: There are a wide variety of applications of Voronoi diagrams. They are more important then what one might come to believe. Some of the applications are as follows:

1. Nearest Neighbour Search: This is the most obvious application of Voronoi Diagrams.

2. Facility Location: The example that is often quoted in this case is the example of choosing where to place a new Antenna in case of cellular mobile systems and similarly deciding the location of a new McDonalds given a number of them already exist in the city.

3. Path Planning: Suppose one models the sites as obstacles, then they can be used to determine the best path (a path that stays at a maximum distance from all obstacles or sites).

There are a number of other applications, such as in Geophysics, Metrology, Computer Graphics, Epidemiology and even pattern recognition. A very good example that illustrates how they can be used was the analysis of the Cholera epidemic in London in 1854, in which physician John Snow determined a very strong correlation of deaths with proximity to a particular infected pump (specific example from Wolfram Mathworld).

Let’s consider the specific example of path planning [2]. Consider a robot placed in one corner of a room with stuff dispersed around.

Now the best path from the point where the robot is located to the goal would be the one in which the robot is farthest from the nearest obstacle at any point in time. To find such a path, the Voronoi diagram of the room would be required to be found out. Once it is done, the vertices or the skeleton of the Voronoi Diagram provides the best path. Which path ultimately is to be taken can be found out by comparing the various options (alternative paths) by using search algorithms.

Now finally after the background on Voronoi Diagrams let’s look at some cool artwork that i came across. ;-)

———-

Fractals from Voronoi Diagrams:

This I came across on the page of Kim Sherriff[3]. The idea is straightforward to say the least.

It is: To create a fractal, first create a Voronoi diagram from some points, next add more points and then create the Voronoi diagrams inside individual Voronoi Regions. Some sample progression could be like this:

Repeating the above process recursively on the above would give the following Voronoi fractal.

Interestingly, this fractal looks like the structure of a leaf.

The above was repeated in color by Frederik Vanhoutte[4] to get some spectacular results. Also I would highly recommend his blog!

[Voronoi Fractal – Image Source]

I am really going to try this myself, it seems a few hours of work at first sight. Ofcourse I won’t use the code that the author has provided. ;-)

———-

Mosaic Images Using Voronoi Diagrams[5] :

I have not had the time to read this paper. However, I am always attracted by mosaics, and these ones (the ones in the paper) as created using Voronoi Diagrams have an increased coolness quotient for me. Sample this image:

Golan Levin’s[6] experiments in using Voronoi diagrams to obtain aesthetic forms yielded probably even more pleasant results. The ones below give a very delicate look to their subjects.

The tilings that are produced by just mild tweaks to the basic definition of a Voronoi Diagram for a 2-D case that I had talked about earlier can give rise to a variety of tilings. Say like the one below:

Also, today I came across a nice Voronoi Diagram on The Reference Frame:

The diagram is a representation of 17,168 weather stations around the world. Dr Motl illustrates how handy MATHEMATICA is for such things.

Click to Enlarge

———-

References:

[1] Craig Kaplan, Voronoi Diagrams and Ornamental Design.

[2] Introduction to Voronoi Diagrams – Example.

[3] Kim Sherriff, “Fractals from Voronoi Diagrams“.

[4] Frederik Vanhoutte, “Voronoi Fractal“.

[6] Golan Levin, “Segmentation and Symptom

———-

Applets:

2. Bubble Harp.

———-

———-

Onionesque Reality Home >>

## A Fractal with Zero Area and an Infinite Perimeter?

Following a discussion on Reasonable Deviations. I was prompted to write on this.

The above is an illustration on the generation of the Sierpinski Gasket. For simplicity we assume that the area of the initial triangle is 1. We split this triangle into four triangles by joining the mid-points of the sides of the triangle. These smaller triangles as shown in figure 2 have equal areas. We then remove the middle triangle. We adopt the convention that we will only remove the middle triangle and not a triangle at the edge.

In each of the three remaining triangles we repeat the process and remove the middle triangles. This is where self-symmetry comes in. If we pretend to see only one of the three small triangles then we are actually doing the same thing as we did to the original triangle. Albeit on a smaller scale. The above figure shows the third and fourth iterates of the original triangle. This process repeated ad infinitum gives rise to the Sierpinski gasket.

The L-System representation of the process is:

variables : A B

constants : + −

start : A

rules : (A → B−A−B),(B → A+B+A)

angle : 60°

Continuing with our earlier assumption, suppose the initial triangle had an area

A0= 1;

Now in the first iteration we remove one of the four equal areas in that triangle and keeping the other three that remain.

Therefore the total area of the first iterate will be equal to

A1 = (3/4) x 1;

Similarly in the second iteration, we repeat the process as I have already noted above. Thus,

A2 = (3/4)(3/4) x 1;

For n iterations the area will be given by:

An = (3/4)n x 1;

Now if n is arbitrarily large then the area, it would follow will be ZERO.

Now finding out the perimeter is a similar exercise. The length of the boundary of the nth iterate of the original triangle is the total length of the boundaries of all the shaded small triangles in the nth iterate. It can be shown that this gets arbitrarily large as n gets arbitrarily large. Therefore we conclude that a Sierpinski gasket has infinite perimeter!

And that it has zero area inside and infinite perimeter.

This is against the Koch Snowflake, which is a figure having a finite area inside an infinite perimeter. This goes against the way we think and according to geometric intuition that we have. But it actually is characteristic of many shpaes in nature. For example (i really like this example :D ) if we take all the arteries, veins and capillaries in the human body, then they occupy a relative small fraction of the body. Yet if we were able to lay them out end to end, we would find that the total length would come to over 60000 kilometres. This example i am quoting from an article i had copied years ago.

Related Article:

Lindenmayer systems and Fractals

Onionesque Reality Home >>

This post is following the previous post in which i mentioned about the rules governing the motion of a bird swarm.

The video below is a breathtaking, sublime, amazing recording of thousands of starlings in a flock before roosting. This is from the UK country-side. While it is another awesome demonstration of how the “imagination” of nature can be like, it also gives a perfect example of how the entire swarm is organized and how it moves. Modern researchers are trying to imitate such emergent behavior to use in fields like robotics, data mining, internet mathematics, optimization etc etc.

How do birds exactly do this?

Here is an excerpt from a talk that i had given at a technical event in October ’07.

In a swarm if we say that there are ‘N’ number of agents, then we can say that these autonomous agents are in a way co-operating to achieve a global objective. This global objective can be better foraging, constructing shelter, serving as a defence mechanism among others. This apparent collective intelligence emerges from very simple individual agents. The actions of these agents are governed by local rules and through the interactions of the N agents the swarm achieves a global objective. A kind of “self organization” emerges in these systems. We see that there is no central controller in such cases. Swarm intelligence gives a basis which makes it possible to explore collective (or distributed) problem solving without centralized control or without the provision of a global model. [1]

The individual (but autonomous) agent does not follow directives from a central authority or work according to some global plan. As a common example, a bird in a flock, only adjusts its movements to coordinate with the movements of its flock mates or more precisely the members that are its neighbors. It simply tries to stay close to its neighbors, but avoid collisions with them. Each bird does not take commands from any leader bird since there is no lead bird. Any bird can fly anywhere in the swarm, either in the middle or the front or the back of the swarm. Swarm behavior gives the birds some distinct advantages like protection from predators, and searching for food (effectively in a swarm each bird is exploiting the eyes of every other bird). Scientists are trying to find out how these birds, fish etc move in flocks, schools in a way that appears orchestrated. A school of fish and a flock of birds move as if all the “steps” were pre planned. For one moment they are moving towards the left and in another they are darting towards the right. Among these researchers in 1987, Reynolds created a boidor bird-oid (bird like) model. This is a distributed behavioral model, to simulate the motion of a flock of birds on a computer [2]. Each boid is implemented as an agent which moves according to its own understanding of the dynamic environment. A boid observes the following rules. First, is that a boid must move away from boids that are too close, so as to reduce the chance of collisions. Second, boid must fly in the general direction that the flock is moving. Third, a boid should minimize exposure to the flock’s exterior by moving toward the perceived center of the flock. Flake later [3] added a Fourth rule, a boid should move laterally away from any boid that blocks its view. This boid model seems reasonable if we consider it from another point of view, that of it acting according to attraction and repulsion between neighbors in a flock. The repulsion relationship results in the avoidance of collisions and attraction makes the flock keep shape, i.e., copying movements of neighbors can be seen as a kind of attraction.

This is what i was talking about in the previous post. A certain set of rules is followed that would give a certain shape to the swarm, if the set is altered so will be the shape and maybe functionality as well!

Sounds nice, now how can these simple rules be modeled on a computer? They can be done using NetLogo. Here is a sample model . To get a good idea about the intricacies adjust the population, the turn angles and the vision. For playing around with the model and making your own you are instructed to go through the writeup to this model on the above page.

References:

[1] E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm Intelligence: From Natural to Artifcial Systems. NY: Oxford Univ. Press, 1999.

[2] C. Reynolds, ‘Flocks, herds, and schools: A distributed behavioral model,” Comp. Graph, vol. 21, no. 4, pp. 25{34, 1987.

[3] G. Flake, The Computational Beauty of Nature. Cambridge, MA: MIT Press, 1999.