From Eros to Gaia

I had been re-reading “From Eros to Gaia” by Freeman Dyson after some years. I have a bad habit of never reading prefaces to books, however I am glad I read it this time around because of this sobering passage that appears in it:

My mother used to say that life begins at forty. That was her age when she had her first baby. I say, on the contrary, that life begins at fifty-five, the age when I published my first book. So long as you have courage and a sense of humour, it is never too late to start life afresh. A book is in many ways like a baby. While you are writing, it is curled up in your belly. You cannot get a clear view of it. As soon as it is born, it goes out into the world and develops a character of its own. Like a daughter coming home from school, it surprises you with unexpected flashes of wisdom. The same thing happens with scientific theories. You sit quietly gestating them, for nine months or whatever the required time may be, and then one day they are out on their own, not belonging to you anymore but to the whole community of scientists. Whatever it is that you produce– a baby, a book, or a theory– it is a piece of the magic of creation. You are producing something that you do not fully understand. As you watch it grow, it becomes part of a larger world, and fits itself into a larger design than you imagined. You belong to the company of those medieval craftsmen who added a carved stone here or a piece of scaffolding there, and together built Chartres Cathedral.

Advertisement

Read Full Post »

Implementation and Abstraction in Mathematics

I recently noticed on arXiv that the following manuscript “Implementation and Abstraction in Mathematics” by David McAllester. A couple of years ago, I had taken a graduate course taught by David that had a similar flavour (the material in the manuscript is more advanced, in particular the main results, not to mention it is better organized and the presentation more polished), presenting a type theoretic foundation of mathematics. Although I can’t say I did very well in the course, I certainly enjoyed the ideas in it very much, and thus the above manuscript might be worth a look. Perhaps it might be a good idea to audit that course again, just to make sure I understand the main ideas better this time. :)

Read Full Post »

Some Proofs of the Cauchy-Schwarz Inequality

Over the past 4-5 months whenever there is some time to spare, I have been working through The Cauchy-Schwarz Master Class by J. Michael Steele. And, although I am still left with the last two chapters, I have been reflecting on the material already covered in order to get a better perspective on what I have been slowly learning over the months. This blog post is a small exercise in this direction.

Ofcourse, there is nothing mysterious about proving the Cauchy-Schwarz inequality; it is fairly obvious and basic. But I thought it still might be instructive (mostly to myself) to reproduce some proofs that I know out of memory (following a maxim of my supervisor on a white/blackboard blogpost). Although, why Cauchy-Schwarz keeps appearing all the time and what makes it so useful and fundamental is indeed quite interesting and non-obvious. And like Gil Kalai notes, it is also unclear why is it that it is Cauchy-Schwarz which is mainly useful. I feel that Steele’s book has made me appreciate this importance somewhat more (compared to 4-5 months ago) by drawing to many concepts that link back to Cauchy-Schwarz.

Before getting to the post, a word on the book: This book is perhaps amongst the best mathematics book that I have seen in many years. True to its name, it is indeed a Master Class and also truly addictive. I could not put aside the book completely once I had picked it up and eventually decided to go all the way. Like most great books, the way it is organized makes it “very natural” to rediscover many susbtantial results (some of them named) appearing much later by yourself, provided you happen to just ask the right questions. The emphasis on problem solving makes sure you make very good friends with some of the most interesting inequalities. The number of inequalities featured is also extensive. It starts off with the inequalities dealing with “natural” notions such as monotonicity and positivity and later moves onto somewhat less natural notions such as convexity. I can’t recommend this book enough!

Now getting to the proofs: Some of these proofs appear in Steele’s book, mostly as either challenge problems or as exercises. All of them were solvable after some hints.

________________

Proof 1: A Self-Generalizing proof

This proof is essentially due to Titu Andreescu and Bogdan Enescu and has now grown to be my favourite Cauchy-Schwarz proof.

We start with the trivial identity (for ):

Identity 1:

Expanding we have

Rearranging this we get:

Further: ;

Rearranging this we get the following trivial Lemma:

Lemma 1: 

Notice that this Lemma is self generalizing in the following sense. Suppose we replace with and with , then we have:

But we can apply Lemma 1 to the second term of the right hand side one more time. So we would get the following inequality:

Using the same principle times we get the following:

Now substitute and to get:

This is just the Cauchy-Schwarz Inequality, thus completing the proof.

________________

Proof 2: By Induction

Again, the Cauchy-Schwarz Inequality is the following: for

For proof of the inequality by induction, the most important thing is starting with the right base case. Clearly is trivially true, suggesting that it is perhaps not of much import. So we consider the case for . Which is:

To prove the base case, we simply expand the expressions. To get:

Which is just:

Or:

Which proves the base case.

Moving ahead, we assume the following inequality to be true:

To establish Cauchy-Schwarz, we have to demonstrate, assuming the above, that

So, we start from :

we further have,

Now, we can apply the case for . Recall that:

Thus, using this in the R. H. S of , we would now have:

Or,

This proves the case on assuming . Thus also proving the Cauchy-Schwarz inequality by the principle of mathematical induction.

________________

Proof 3: For Infinite Sequences using the Normalization Trick:

We start with the following question.

Problem: For If and then is ?

Note that this is easy to establish. We simply start with the trivial identity which in turn gives us

Next, take and on summing up to infinity on both sides, we get the following:

From this it immediately follows that

Now let

and

; substituting in , we get:

or,

Which simply gives back Cauchy’s inequality for infinite sequences thus completing the proof:

________________

Proof 4: Using Lagrange’s Identity

We first start with a polynomial which we denote by :

The question to now ask, is ? To answer this question, we start of by re-writing in a “better” form.

Next, as J. Michael Steele puts, we pursue symmetry and rewrite the above so as to make it apparent.

Thus, we now have:

This makes it clear that can be written as a sum of squares and hence is always postive. Let us write out the above completely:

Now, reversing the step we took at the onset to write the L.H.S better, we simply have:

This is called Lagrange’s Identity. Now since the R.H.S. is always greater than or equal to zero. We get the following inequality as a corrollary:

This is just the Cauchy-Schwarz inequality, completing the proof.

________________

Proof 5: Gram-Schmidt Process gives an automatic proof of Cauchy-Schwarz

First we quickly review the Gram-Schmidt Process: Given a set of linearly independent elements of a real or complex inner product space , . We can get an orthonormal set of elemets by the simple recursion (after setting ).

and then

for .

Keeping the above in mind, assume that . Now let . Thus, we have:

Giving: . Rearranging we have:

or

or

where are constants.

Now note that: and

. The following bound is trivial:

. But note that this is simply

Which is just the Cauchy-Schwarz inequality when .

________________

Proof 6: Proof of the Continuous version for d =2; Schwarz’s Proof

For this case, the inequality may be stated as:

Suppose we have and that and . Then consider the double integrals:

, and . These double integrals must satisfy the following inequality:

.

The proof given by Schwarz as is reported in Steele’s book (and indeed in standard textbooks) is based on the following observation:

The real polynomial below is always non-negative:

unless and are proportional. Thus from the binomial formula we have that , moreover the inequality is strict unless and are proportional.

________________

Proof 7: Proof using the Projection formula

Problem: Consider any point in . Now consider the line that passes through this point and origin. Let us call this line . Find the point on the line closest to any point .

If is the point on the line that is closest to , then it is given by the projection formula:

This is fairly elementary to establish. To find the value of , such that distance is minimized, we can simply consider the squared distance since it is easier to work with. Which by definition is:

which is simply:

So, the value of for which the above is minimized is . Note that this simply reproduces the projection formula.

Therefore, the minimum squared distance is given by the expression below:

Note that the L. H. S is always positive. Therefore we have:

Rearranging, we have:

Which is just Cauchy-Schwarz, thus proving the inequality.

________________

Proof 8: Proof using an identity

A variant of this proof is amongst the most common Cauchy-Schwarz proofs that are given in textbooks. Also, this is related to proof (6) above. However, it still has some value in its own right. While also giving an useful expression for the “defect” for Cauchy-Schwarz like the Lagrange Identity above.

We start with the following polynomial:

. Clearly .

To find the minimum of this polynomial we find its derivative w.r.t and setting to zero:

giving:

Clearly we have . We consider:

, substituting we have:

Just rearrangine and simplifying:

This proves Cauchy-Schwarz inequality.

Now suppose we are interested in an expression for the defect in Cauchy-Schwarz i.e. the difference . For this we can just consider the L.H.S of equation since it is just .

i.e. Defect =

Which is just:

This defect term is much in the spirit of the defect term that we saw in Lagrange’s identity above, and it is instructive to compare them.

________________

Proof 9: Proof using the AM-GM inequality

Let us first recall the AM-GM inequality:

For non-negative reals we have the following basic inequality:

.

Now let us define and

Now consider the trivial bound (which gives us the AM-GM): , which is just . Note that AM-GM as stated above for is immediate when we consider and

Using the above, we have:

Summing over , we have:

But note that the L.H.S equals 1, therefore:

or 

Writing out and as defined above, we have:

.

Thus proving the Cauchy-Schwarz inequality.

________________

Proof 10: Using Jensen’s Inequality

We begin by recalling Jensen’s Inequality:

Suppose that is a convex function. Also suppose that there are non-negative numbers such that . Then for all for one has:

.

Now we know that is convex. Applying Jensen’s Inequality, we have:

Now, for for all , let and let .

Which gives:

Rearranging this just gives the familiar form of Cauchy-Schwarz at once:

________________

Proof 11: Pictorial Proof for d = 2

Here (page 4) is an attractive pictorial proof by means of tilings for the case by Roger Nelson.

________________

Read Full Post »

Book Review: “Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World” by Leslie Valiant

Darwinian Evolution is a form of Computational Learning

The punchline of this book is perhaps: “Changing or increasing functionality of circuits in biological evolution is a form of computational learning“; although it also speaks of topics other than evolution, the underlying framework is of the Probably Approximately Correct model [1] from the theory of Machine Learning, from which the book gets its name.

“Probably Approximately Correct” by Leslie Valiant

[Clicking on the image above will direct you to the amazon page for the book]

I had first heard of this explicit connection between Machine Learning and Evolution in 2010 and have been quite fascinated by it since. It must be noted, however, that similar ideas have appeared in the past. It won’t be incorrect to say that usually they have been in the form of metaphor. It is another matter that this metaphor has generally been avoided for reasons I underline towards the end of this review. When I first heard about the idea it immediately made sense and like all great ideas, in hindsight looks completely obvious. Ergo, I was quite excited to see this book and preordered it months in advance.

This book is basically a popular science version and expansion of the ideas on the matter that appeared in a J-ACM article titled “Evolvability” in 2007 [2]. I have to say that I was expecting a bit more from the book than what it already had, in this sense I was somewhat disappointed. But at the same time, it can perhaps be a useful ‘starting’ book for those interested in the broad idea but without much background. We all have examples of books like this. Here’s one from me: about a couple of years ago I read a book on Knots by Alexei Sossinsky, the book got bad reviews from many serious mathematicians for not really being about mathematics, besides having many mistakes. But for a complete beginner, I thought it was an absolutely wonderful book, introducing the reader to the basic ideas very informally besides sharing his infectious enthusiasm for problems in Knot Theory. Coming back, in short if you have enough background of the basic notions of PAC Learning then the book might feel quite redundant in some chapters, but depending on how you read, it might still turn out to be a good read any way. Judging from some other (rude) reviews: If you are a professional nitpicker then this book is probably not worth your time since this book deals with ideas and not with a formal treatment of them. Given what it is aiming at, I think it is a good book.

Before attempting to sketch a skiagram of the main content of the book: One of the main subthemes of the book, constantly emphasized is to look at computer science as a kind of an enabling tool to study natural science. This is oft ignored, perhaps because of the reason that CS curricula are rarely designed with any natural science component in them and hence there is no impetus for aspiring computer scientists to view them from the computational lens. On the other hand,  the relation of computer science with mathematics has become quite well established. As a technology the impact of Computer Science has been tremendous. All this is quite remarkable given the fact that just about a century ago the notion of a computation was not even well defined. Unrelated to the book: More recently people have started taking the idea of digital physics (i.e. physics from a solely computable/digital perspective) seriously. But in the other natural sciences its usage is still woeful. Valiant draws upon the example of Alan Turing as a natural scientist and not just as a computer scientist to make this point. Alan Turing was more interested in natural phenomenon (intelligence, limits of mechanical calculation, pattern formation etc) and used tools from Computer Science to study them, a fact that is evident from his publications. That Turing was trying to understand natural phenomenon was remarked in his obituary by Max Neumann by summarizing the body of his work as: “the extent and the limitations of mechanistic explanations of nature”.

________________

The book begins with a delightful and quite famous quote by John von Neumann (through this paragraph I also discovered the context to the quote). This paragraph also adequately summarizes the motivation for the book very well:

“In 1947 John von Neumann, the famously gifted mathematician, was keynote speaker at the first annual meeting of the Association for Computng Machinery. In his address he said that future computers would get along with just a dozen instruction types, a number known to be adequate for expressing all of mathematics. He went on to say that one need not be surprised at this small number, since 1000 words were known to be adequate for most situations in real life, and mathematics was only a small part of life, and a very simple part at that. The audience responded with hilarity. This provoked von Neumann to respond: “If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is”

Though counterintuitive, von Neumann’s quip contains an obvious truth. Einstein’s theory of general relativity is simple in the sense that one can write the essential content on one line as a single equation. Understanding its meaning, derivation, and consequences requires more extensive study and effort. However, this formal simplicity is striking and powerful. The power comes from the implied generality, that knowledge of one equation alone will allow one to make accurate predictions about a host of situations not even connected when the equation was first written down.

Most aspects of life are not so simple. If you want to succeed in a job interview, or in making an investment, or in choosing a life partner, you can be quite sure that there is no equation that will guarantee you success. In these endeavors it will not be possible to limit the pieces of knowledge that might be relevant to any one definable source. And even if you had all the relevant knowledge, there may be no surefire way of combining it to yield the best decision.

This book is predicated on taking this distinction seriously […]”

In a way, aspects of life as mentioned above appear theoryless, in the sense that there seems to be no mathematical or scientific theory like relativity for them. Something which is quantitative, definitive and short. Note that these are generally not “theoryless” in the sense that there exists no theory at all since obviously people can do all the tasks mentioned in a complex world quite effectively. A specific example is of how organisms adapt and species evolve without having a theory of the environment as such. How can such coping mechanisms come into being in the first place is the main question asked in the book.

Let’s stick to the specific example of biological evolution. Clearly, it is one of the central ideas in biology and perhaps one of the most important theories in science that changed the way we look at the world. But inspite of its importance, Valiant claims (and correctly in my opinion) that evolution is not understood well in a quantitative sense. Evidence that convinces us of its correctness is of the following sort: Biologists usually show a sequence of evolving objects; stages, where the one coming later is more complex than the previous. Since this is studied mostly via the fossil record there is always a lookout for missing links between successive stages (As a side note: Animal eyes is an extremely fascinating and very readable book that delves with this question but specifically dealing with the evolution of the eye. This is particularly interesting given that due to the very nature of the eye, there can be no fossil records for them). Darwin had remarked that numerous successive paths are necessary – that is, if it was not possible to trace a path from an earlier form to a more complicated form then it was hard to explain how it came about. But again, as Valiant stresses, this is not really an explanation of evolution. It is more of an “existence proof” and not a quantitative explanation. That is, even if there is evidence for the existence of a path, one can’t really say that a certain path is likely to be followed just because it exists. As another side note: Watch this video on evolution by Carl Sagan from the beautiful COSMOS

Related to this, one of the first questions that one might ask, and indeed was asked by Darwin himself: Why has evolution taken as much time as it has? How much time would have sufficed for all the complexity that we see around us to evolve? This question infact bothered Darwin a lot in his day. In On the Origins of Species he originally gave an estimate of the Earth’s age to be at least 300 million years, implying indirectly, that there was enough time. This estimate was immediately thrashed by Lord Kelvin, one of the pre-eminent British physicists of the time, who estimated the age of the Earth to be only about 24 million years. This caused Darwin to withdraw the estimate from his book. However, this estimate greatly worried Darwin as he thought 24 million years just wasn’t enough time. To motivate on the same theme Valiant writes the following:

“[…] William Paley, in a highly influential book, Natural Theology (1802) , argued that life, as complex as it is, could not have come into being without the help of a designer. Numerous lines of evidence have become available in the two centuries since, through genetics and the fossil record, that persuade professional biologists that existing life forms on Earth are indeed related and have indeed evolved. This evidence contradicts Paley’s conclusion, but it does not directly address his argument. A convincing direct counterargument to Paley’s would need a specific evolution mechanism to be demonstrated capable of giving rise to the quantity and quality of the complexity now found in biology, within the time and resources believed to have been available. […]”

A specific, albeit more limited version of this question might be: Consider the human genome, which has about 3 billion base pairs. Now, if evolution is a search problem, as it naturally appears to be, then why did the evolution of this genome not take exponential time? If it would have taken exponential time then clearly such evolution could not have happened in any time scale since the origin of the earth. Thus, a more pointed question to ask would be: What circuits could evolve in sub-exponential time (and on a related note, what circuits are evolvable only in exponential time?). Given the context, the idea of thinking about this in circuits might seem a little foreign. But on some more thought it is quite clear that the idea of a circuit is natural when it comes to modeling such systems (at least in principle). For example: One might think of the genome as a circuit, just as how one might think of the complex protein interaction networks and networks of neurons in the brain as circuits that update themselves in response to the environment.

The last line is essentially the key idea of adaptation, that entities interact with the environment and update themselves (hopefully to cope better) in response. But the catch is that the world/environment is far too complex for simple entities (relatively speaking), with limited computational power, to have a theory for. Hence, somehow the entity will have to cope without really “understanding” the environment (it can only be partially modeled) and improve their functionality. The key thing to pay attention here is the interaction or the interface between the limited computational entity in question and the environment. The central idea in Valiant’s thesis is to think of and model this interaction as a form of computational learning. The entity will absorb information about the world and “learn” so that in the future it “can do better”. A lot of Biology can be thought of as the above: Complex behaviours in environments. Wherein by complex behaviours we mean that in different circumstances, we (or alternately our limited computational entity) might behave completely differently. Complicated in the sense that there can’t possibly be a look up table for modeling such complex interactions. Such interactions-responses can just be thought of as complicated functions e.g. how would a deer react could be seen as a function of some sensory inputs. Or for another example: Protein circuits. The human body has about 25000 proteins. How much of a certain protein is expressed is a function depending on the quantities of other proteins in the body.  This function is quite complicated, certainly not something like a simple linear regression. Thus there are two main questions to be asked: One, how did these circuits come into being without there being a designer to actually design them? Two, How do such circuits maintain themselves? That is, each “node” in protein circuits is a function and as circumstances change it might be best to change the way they work. How could have such a thing evolved?

Given the above, one might ask another question: At what rate can functionality increase or adapt under the Darwinian process? Valiant (like many others, such as Chaitin. See this older blog post for a short discussion) comes to the conclusion that the Darwinian evolution is a very elegant computational process. And since it is so, with the change in the environment there has to be a quantitative way of saying how much rate of change can be kept up with and what environments are unevolvable for the entity. It is not hard to see that this is essentially a question in computer science and no other discipline has the tools to deal with it.

In so far that (biological) interactions-responses might be thought of as complicated functions and that the limited computational entity that is trying to cope has to do better in the future, this is just machine learning! This idea, that changing or increasing functionality of circuits in biological evoution is a form of computational learning, is perhaps very obvious in hindsight. This (changing functionality) is done in Machine Learning in the following sense: We want to acquire complicated functions without explicitly programming for them, from examples and labels (or “correct” answers). This looks at exactly at the question at how complex mechanisms can evolve without someone designing it (consider a simple perceptron learning algorithm for a toy example to illustrate this). In short: We generate a hypothesis and if it doesn’t match our expectations (in performance) then we update the hypothesis by a computational procedure. Just based on a single example one might be able to change the hypothesis. One could draw an analogy to evolution where “examples” could be experiences, and the genome is the circuit that is modified over a period of time. But note that this is not how it looks like in evolution because the above (especially drawing to the perceptron example) sounds more Lamarckian. What the Darwinian process says is that we don’t change the genome directly based on experiences. What instead happens is that we make a lot of copies of the genome which are then tested in the environment with the better one having a higher fitness. Supervised Machine Learning as drawn above is very lamarckian and not exactly Darwinian.

Thus, there is something unsatisfying in the analogy to supervised learning. There is a clear notion of a target in the same. Then one might ask, what is the target of evolution? Evolution is thought of as an undirected process. Without a goal. This is true in a very important sense however this is incorrect. Evolution does not have a goal in the sense that it wants to evolve humans or elephants etc. But it certainly does have a target. This target is “good behaviour” (where behaviour is used very loosely) that would aid in the survival of the entity in an environment. Thus, this target is the “ideal” function (which might be quite complicated) that tells us how to behave in what situation. This is already incorporated in the study of evolution by notions such as fitness that encode that various functions are more beneficial. Thus evolution can be framed as a kind of machine learning problem based on the notion of Darwinian feedback. That is, make many copies of the “current genome” and let the one with good performance in the real world win. More specifically, this is a limited kind of PAC Learning.  If you call your current hypothesis your genome, then your genome does not depend on your experiences. Variants to this genome are generated by a polynomial time randomized Turing Machine. To illuminate the difference with supervised learning, we come back to a point made earlier that PAC Learning is essentially Lamarckian i.e. we have a hidden function that we want to learn. One however has examples and labels corresponding to this hidden function, these could be considered “queries” to this function. We then process these example/label pairs and learn a “good estimate” of this hidden function in polynomial time. It is slightly different in Evolvability. Again, we have a hidden “ideal” function f(x). The examples are genomes. However, how we can find out more about the target is very limited, since one can empirically only observe the aggregate goodness of the genome (a performance function). The task then is to mutate the genome so that it’s functionality improves. So the main difference with the usual supervised learning is that one could query the hidden function in a very limited way: That is we can’t act on a single example and have to take aggregate statistics into account.

Then one might ask what can one prove using this model? Valiant demonstrates some examples. For example, Parity functions are not evolvable for uniform distribution while monotone disjunctions are actually evolvable. This function is ofcourse very non biological but it does illustrate the main idea: That the ideal function together with the real world distribution imposes a fitness landscape and that in some settings we can show that some functions can evolve and some can not. This in turn illustrates that evolution is a computational process independent of substrate.

In the same sense as above it can be shown that Boolean Conjunctions are not evolvable for all distributions. There has also been similar work on real valued functions off late which is not reported in detail in the book. Another recent work that is only mentioned in passing towards the end is the study of multidimensional space of actions that deal with sets of functions (not just one function) that might be evolvable together. This is an interesting line of work as it is pretty clear that biological evolution deals with the evolution of a set of functions together and not functions in isolation.

________________

Overall I think the book is quite good. Although I would rate it 3/5. Let me explain. Clearly this book is aimed at the non expert. But this might be disappointing to those who bought the book because of the fact that this recent area of work, of studying evolution through the lens of computational learning, is very exciting and intellectually interesting. The book is also aimed at biologists, and considering this, the learning sections of the book are quite dumbed down. But at the same time, I think the book might fail to impress most of them any way. I think this is because generally biologists (barring a small subset) have a very different way of thinking (say as compared to the mathematicians or computer scientists) especially through the computational lens. I have had some arguments about the main ideas in the book over the past couple of years with some biologist friends who take the usage of “learning” to mean that what is implied is that evolution is a directed process. It would have been great if the book would have spent more time on this particular aspect. Also, the book explicitly states that it is about quantitative aspects of evolution and has nothing to do with speciation, population dynamics and other rich areas of study. However, I have already seen some criticism of the book by biologists on this premise.

As far as I am concerned, as an admirer of Prof. Leslie Valiant’s range and quality of contributions, I would have preferred if the book went into more depth. Just to have a semi-formal monograph on the study of evolution using the tools of PAC Learning right from the person who initiated this area of study. However this is just a selfish consideration.

________________

References:

[1] A Theory of the Learnable, Leslie Valiant, Communications of the ACM, 1984 (PDF).

[2] Evolvability, Leslie Valiant, Journal of the ACM, 2007 (PDF).

________________

Read Full Post »

von Neumann’s Self Reproducing Automata and the discovery of DNA Structure

Long Blurb: In the past year, I read three books by Gregory Chaitin: His magnum opus – MetaMath! (which had been on my reading stack since 2007), a little new book – Proving Darwin and most of Algorithmic Information Theory (available as a PDF as well). Before this I had only read articles and essays by him. I have been sitting on multiple blog post drafts based on these readings but somehow I never got to finishing them up, perhaps it is time to publish them as is! Chaitin is an engaging and provocative writer (and speaker! see this fantastic lecture for instance) who really makes me think. It has come to my notice that a lot of people find his writing style uncomfortable (for apparently lacking humility and having copious hyperbole). While there might be some merits to this view, if one is able to look beyond these minor misgivings he always has a lot of interesting ideas. The apparent hyperbole is best viewed as effusive enthusiasm to get the most out of his writings (since there is indeed a lot to be mined). I might talk about this when I actually write about his books and the ideas therein. For now, this post was in part inspired by something I read in the second book: Proving Darwin.

I thought this was a thought provoking book, but perhaps was not suited to be a book, yet. It builds on the idea of DNA as software and tries to think of Evolution as a random walk in software space. The idea of DNA as software is not new. If one considers DNA to be software and the other biological processes to also be digital, then one is essentially sweeping out all that might not be digital. This view of biological processes might thus be at best an imprecise metaphor. But as Chaitin quotes Picasso ‘art is a lie that helps us see the truth‘ and explains that this is just a model and the point is to see if anything mathematically interesting can be extracted from such a model.

He eloquently points out that once DNA has been thought of as a giant codebase, then we begin to see that a human DNA is just a major software patchwork, having ancient subroutines common with fish, sponges, amphibians etc. As is the case with large software projects, the old code can never be thrown away and has to be reused – patched and made to work and grows by the principle of least effort (thus when someone catches ill and complains of a certain body part being badly designed it is just a case of bad software engineering!). The “growth by accretion” of this codebase perhaps explains Enrst Haeckel‘s slogan “ontogeny recapitulates phylogeny” which roughly means that the growth of a human embryo resembles the successive stages of evolution (thus biology is just a kind of Software Archeology).

All this sounds like a good analogy. But is there any way to formalize this vaguiesh notion of evolution as a random walk in software space and prove theorems about it? In other words, does a theory as elegant as Darwinian Evolution have a purely mathematical core? it must says Chaitin and since the core of Biology is basically information, he reckons that tools from Algorithmic Information Theory might give some answers. Since natural software are too messy, Chaitin considers artificial software in parallel to natural software and considers a contrived toy setting. He then claims in this setting one sees a mathematical proof that such a software evolves. I’ve read some criticisms of this by biologists on the blogosphere, however most criticise it on the premises that Chaitin explicitly states that his book is not about. There are however, some good critiques, I will write about these when I post my draft on the book.

________________

Now coming to the title of the post. The following are some excerpts from the book:

“But we could not realize that the natural world is full of software, we could not see this, until we invented human computer programming languages […] Nobel Laureate Sydney Brenner shared an office with Francis Crick of Watson and Crick. Most Molecular Biologists of this generation credit Schrödinger’s book What is Life? (Cambridge University Press, 1944) for inspiring them. In his autobiography My Life in Science Brenner instead credits von Neumann’s work on self-reproducing automata.

[…] we present a revisionist history of the discovery of software and of the early days of molecular biology from the vantage point of Metabiology […] As Jorge Luis Borges points out, one creates one’s predecessors! […] infact the past is not only occasionally rewritten, it has to be rewritten in order to remain comprehensible to the present. […]

And now for von Neumann’s self reproducing automata. von Neumann, 1951, takes from Gödel the idea of having a description of the organism within the organism = instructions for constructing the organism = hereditary information = digital software = DNA. First you follow the instructions in the DNA to build a new copy of the organism, then you copy the DNA and insert it in the new organism, then you start the new organism running. No infinite regress, no homunculus in the sperm! […]

You see, after Watson and Crick discovered the molecular structure of DNA, the 4-base alphabet A, C, G, T, it still was not clear what was written in this 4-symbol alphabet, it wasn’t clear how DNA worked. But Crick, following Brenner and von Neumann, somewhere in the back of his mind had the idea of DNA as instructions, as software”

I did find this quite interesting, even if it sounds revisionist. That is because the power of a paradigm-shift conceptual leap is often understated, especially after more time has passed. The more time passes, the more “obvious” it becomes and hence the more “diffused” its impact. Consider the idea of a “computation”. A century ago there was no trace of any such idea, but once it was born born and diffused throughout we basically take it for granted. In fact, thinking of a lot of things (anything?) precisely is nearly impossible without the notion of a computation in my opinion. von Neumann often remarked that Turing’s 1936 paper contained in it both the idea of software and hardware and the actual computer was just an implementation of that idea. In the same spirit von Neumann’s ideas on Self-Reproducing automata have had a similar impact on the way people started thinking about natural software and replication and even artificial life (recall the famous von Neumann quote: Life is a process that can be abstracted away from any particular medium).

While I found this proposition quite interesting, I left this at that. Chaitin cited Brenner’s autobiography which I could not obtain since I hadn’t planned on reading it, google-books previews did not suffice either.  So i didn’t pursue looking on what Brenner actually said.

However, this changed recently, I exchanged some emails with Maarten Fornerod, who happened to point out an interview of Sydney Brenner that actually talks about this.

The relevant four parts of this very interesting 1984 interview can be found here, here, here and here. The text is reproduced below.

“45: John von Neumann and the history of DNA and self-replication:

What influenced me the most was the articles of von Neumann. Now, I had become interested in von Neumann not through the coding issues but through his interest in the nervous system and computers and of course, that’s what Seymour was interested in because what we wanted to do is find out how the brain worked; that was what… you know, like a hobby on the side, you know. After… after dinner we’d work on central problems of the brain, you see, but it was trying to find out how this worked. And so I got this symposium, the Hixon Symposium, which I had got to read. I was, at that time, very fascinated by a rather strange complexion of psychology things by a man called Wolfgang Köhler who was a gestalt psychologist and another man called Lewin, who was what was called a topological psychologist and of course they were talking at a very different level, but in this book there is an article by Köhler and of course in that book there’s this very famous paper which no one has ever read of von Neumann. Now of course later I discovered that those ideas were much older than the dating of this and that people had taken notes of them and they had circulated. But what is the brilliant part of this paper is in fact his description of what it takes to make a self-reproducing machine. And in fact if you look at what he says and what Schrödinger says, you can see what I have come to call Schrödinger’s fundamental error, and in fact we can… I can find you the passage in that. But it’s an amazing passage, because what von Neumann shows is that you have to have a mechanism not only of copying the machine but of copying the information that specifies the machine, right, so that he then divided the machine – the… the automaton as he called it – into three components: the functional part of the automaton; a… a decoding section of this which is part of that, which actually takes the tape, reads the instructions and builds the automaton; and a device that takes a copy of this tape and inserts it into the new automaton, right, which is the essential… essential, fundamental… and when von Neumann said that is the logical basis of self-reproduction, then you can see where Schrödinger made his mistake and this can be summarised in one sentence. Schrödinger says the chromosomes contain the information to specify the future organism and the means to execute it and that’s not true. The chromosomes contain the information to specify the future organisation and a description of the means to implement, but not the means themselves, and that logical difference is made so crystal clear by von Neumann and that to me, was in fact… The first time now of course, I wasn’t smart enough to really see that this is what DNA is all about, and of course it is one of the ironies of this entire field that were you to write a history of ideas in the whole of DNA, simply from the documented information as it exists in the literature, that is a kind of Hegelian history of ideas, you would certainly say that Watson and Crick depended on von Neumann, because von Neumann essentially tells you how it’s done and then you just… DNA is just one of the implementations of this. But of course, none knew anything about the other, and so it’s a… it’s a great paradox to me that in fact this connection was not seen. Linus Pauling is present at that meeting because he gives this False Theory of Antibodies there. That means he heard von Neumann, must have known von Neumann, but he couldn’t put that together with DNA and of course… well, neither could Linus Pauling put his own paper together with his future work because he and Delbrück wrote a paper on self… on self-complementation – two pieces of information – in about 1949 and had forgotten it by the time he did DNA, so that of course leads to a really distrust about what all the historians of science say, especially those of the history of ideas. But I think that that in a way is part of our kind of revolution in thinking, namely the whole of the theory of computation, which I think biologists have yet to assimilate and yet is there and it’s a… it’s an amazingly paradoxical field. You know, most fields start by struggling through from, from experimental confusion through early theoretical, you know, self-delusion, finally to the great generality and this field starts the other way round. It starts with a total abstract generality, namely it starts with, with Gödel’s hypothesis or the Turing machine, and then it takes, you know, 50 years to descend into… into banality, you see. So it’s the field that goes the other way and that is again remarkable, you know, and they cross each other at about 1953, you know: von Neumann on the way down, Watson and Crick on the way up. It was never put together.

[Q] But… but you didn’t put it together either?

I didn’t put it together, but I did put together a little bit later that, because the moment I saw the DNA molecule, then I knew it. And you connected the two at once? I knew this.

46: Schrodinger Wrong, von Neumann right:

I think he made a fundamental error, and the fundamental error can be seen in his idea of what the chromosome contained. He says… in describing what he calls the code script, he says, ‘The chromosome structures are at the same time instrumental in bringing about the development they foreshadow. They are law code and executive power, or to use another simile, they are the architect’s plan and the builder’s craft in one.’ And in our modern parlance, we would say, ‘They not only contain the program but the means to execute the program’. And that is wrong, because they don’t contain the means; they only contain a description of the means to execute it. Now the person that got it right and got it right before DNA is von Neumann in developing the logic of self-reproducing automata which was based of course on Turing’s previous idea of automaton and he gives this description of this automaton which has one part that is the machine; this machine is built under the instructions of a code script, that is a program and of course there’s another part to the machine that actually has to copy the program and insert a copy in the new machine. So he very clearly distinguishes between the things that read the program and the program itself. In other words, the program has to build the machinery to execute the program and in fact he says it’s… when he tries to talk about the biological significance of this abstract theory, he says: ‘This automaton E has some further attractive sides, which I shall not go into at this time at any length’.

47: Schrodinger’s belief in calculating an organism from chromosomes:

One of the central things in the Schrödinger’s little book What Is Life is what he has to say about the chromosomes containing the program or the code, and he says here… on page 20, he says: ‘In calling the structure of the chromosome fibres a code script, we mean that the all penetrating mind once conceived by Laplace, to which every cause or connection lay immediately open, could tell from their structure whether the egg would develop under suitable conditions, into a black cock, or into a speckled hen, into a fly, or a maize plant, a rhododendron, a beetle, a mouse or a woman’. Now, apart from the list of organisms he has given, which falls short of a serious classification of the living world, what he is saying here is that if you could look at the chromosomes, you could compute the… you could calculate the organism, but he’s saying something more. He’s saying that you could actually implement the organism because he goes on to add: ‘But the term code script is of course too narrow. The chromosome structures are at the same time instrumental in bringing about the development they foreshadow. They are law code and executive power, or to use another simile they are architect’s plan and builder’s craft in one.’ What he is saying here is that the chromosomes not only contain a description of the future organism but the means to implement that description or program as we might call it. That’s wrong, because they don’t contain the means to implement it, they only contain a description of the means to implement it and that distinction was made absolutely crystal clear by this remarkable paper of von Neumann, in which he develops and in fact provides a proof of what a self-reproducing automaton – or machine – would have to… would have to contain in order to satisfy the requirements of self-reproduction. He develops this concept of course from the earlier concept of Turing, who had developed ideas of automata that operated on tapes and which of course gave a mechanical example of how you might implement some computation. And if you like, this is the beginning of the theory of computation and what von Neumann has to say about this is made very clear in this essay. And he says that you’ve got to have several components, and I’ll just summarise them. He said you first start with an automaton A, ‘which, when furnished this description of any other automaton in terms of the appropriate functions, will construct that entity’. It’s like a Turing machine, you see. So automaton A has to be given a tape and then it’ll make another automaton A, all right. Now what you have, you’ve got to have… add to this automaton B. ‘Automaton B can make a copy of any instruction I that is furnished to it’, so if you give it a program, it’ll copy the program. And then you have… you combine A and B with each other and you give a control mechanism C, that you have to add as well, which does the following. It says, ‘Let A be furnished with the instruction I’. So you give… you give the tape to A, A copies it under the control of C, okay, by every description, so it makes another copy of A, then you… and of course B is part of A. Then you… C then tells B, ‘copy this tape I’, gives B the copying part of it, this copies it and then C will then take the tape I, and put it into the new machine, okay, and turns it loose as he says here, ‘as an independent entity’.

48: Automata akin to Living Cells:

What von Neumann says is that you need several components in order to provide this self-reproducing automaton. One component, which he calls automaton A, will make another automaton A when furnished with a description of itself. Then you need an automaton C… you need an automaton B, which has the property of copying the instruction tape I, and then you need a control mechanism which will actually control the switching. And so this automaton, or machine, can reproduce itself in the following way. The entity A is provided with a copy of… with the tape I, it now makes another A. The control mechanism then takes the tape I and gives it to B and says make a copy of this tape. It makes a copy of the tape and the control mechanism then inserts the new copy of the tape into the new automaton and effects the separation of the two. Now, he shows that the entire complex is clearly self-reproductive, there is no vicious circle and he goes on to say, in a very modest way I think, the following. He says, ‘The description of this automaton has some further attractive sides into which I shall not go at this time into any length. For instance, it is quite clear that the instruction I is roughly effecting the functions of a gene. It is also clear that the copying mechanism B performs the fundamental act of reproduction, the duplication of the genetic material which is also clearly the fundamental operation in the multiplication of living cells. It is also clear to see how arbitrary alterations of the system E, and in particular of the tape I, can exhibit certain traits which appear in connection with mutation, which is lethality as a rule, but with a possibility of continuing reproduction with a modification of traits.’ So, I mean, this is… this we know from later work that these ideas were first put forward by him in the late ’40s. This is the… a published form which I read in early 1952; the book was published a year earlier and so I think that it’s a remarkable fact that he had got it right, but I think that because of the cultural difference – distinction between what most biologists were, what most physicists and mathematicians were – it absolutely had no impact at all.”

________________

References and Also See:

1. Proving Darwin: Making Biology Mathematical, Gregory Chatin (Amazon).

2. Theory of Self-Reproducing Automata, John von Neumann. (PDF).

3. 1966 film on John von Neumann.

Read Full Post »

Abstractions

I thought I understood Spectral Clustering well enough till I came across these two paragraphs:

Graph Laplacians are interesting linear operators attached to graphs. They are the discrete analogues of the Laplace-Beltrami operators that appear in the Hodge theory of Riemannian manifolds, whose null spaces provide particularly nice representative forms for de Rham cohomology. In particular, their eigenfunctions produce functions on the vertex set of the graph. They can be used, for example, to produce cluster decompositions of data sets when the graph is the 1-skeleton of a Vietoris-Rips complex. We find that these eigenfunctions (again applied to the 1-skeleton of the Vietoris-Rips complex of a point cloud) also can produce useful filters in the Mapper analysis of data sets

– From Prof. Gunnar Carlsson’s survey Topology and Data. (More on this survey as a manifesto for “Topology and Data” in a later post). That aside, I do like how the image on the wiki entry for Vietoris-Rips complex looks like:

A little less intimidating ( now this almost borders on “ofcourse that’s how it is”. I am interested in the same reaction for the paragraph above some months later):

A related application [of the graph laplacian] is “Spectral Clustering”, which is based on the observation that nodal domains of the first eigenvectors of the graph laplacian can be used as indicators for suitably size-balanced minimum cuts.

– From Laplacian Eigenvectors of Graphs linked in the previous post. While this isn’t really as compressed as the lines above, they made me think since I did not know about Courant’s Nodal domain theorem. Like I did in the previous blog post, I would highly recommend this (about 120 page) book. It soon covers the Nodal Domain theorem and things make sense (even in context of links between PCA and k-means and Non-Negative Matrix Factorization and Spectral Clustering, at least in an abstract sense).

_________________________

Onionesque Reality Home >>

Read Full Post »

Summer Readings

Not a technical post. Though certainly an apparition of one.

Here are a few books that I have read/am currently reading/plan to read over this summer with a short blurb (a review would take too long) about each of them. I decided to share as I thought some of them might be of more general interest.

_______________________________________________________________________________________________

1. The Minimum Description Length Principle – Peter Grünwald (Currently Reading – About 40% completed)

Plurality should not be posited without necessity

So goes the principle of parsimony of William of Occam, more commonly called the Occam’s Razor. Friar Occam’s maxim is certainly an observation and not a law, however its universality is unquestioned. The most striking examples being the quest by mathematicians for the most elegant and simple proofs and by physicists for aesthetics and simplicity in theories of nature given multiple competing possibilities.

Looked at more deeply, Occam’s Razor is perhaps the cornerstone of an intricate relationship between Machine Learning and Information Theory, which are essentially two sides of the same coin. At first this is a little difficult to understand. However a closer look at the maxim makes things clearer. What it states essentially is: Given a set of hypothesis that explain some “data” equally well, pick up the hypothesis that has the smallest description (is the simplest). In other words, pick up the hypothesis that achieves maximum compression of the data.

Inductive inference is essentially the task of learning patterns (think formulating laws about your observations) given some observed data and then using what has been learned to make predictions about the future (or unseen data). The more patterns we are able to find in some observations, the more we are able to compress it. And thus the more we are able to compress the data, the more we have learned about it.

The Minimum Description Length principle is a formalization of the Occam’s Razor and is one of the most beautiful and powerful methods for inductive inference. I have written a little about this in a previous post on Ray Solomonoff (the section on the universal distribution). Solomonoff introduced the idea of Kolmogorov Complexity that essentially is this notion.

The Minimum Description Length Principle. (Click on Image to view on Amazon)

Half way into it, I can say that Prof. Grünwald’s book is perhaps the best treatise on the topic. It starts off with a gentle introduction to the idea of MDL and then takes a lot of space to describe preliminaries from Information Theory and Probability. The book becomes a slower read as one moves farther into it which is understandable. It actually is one of the best books that I have come across that takes the basics and builds very powerful theorems from them without appearing like doing black magic. One must commend Dr. Grünwald on this feat.

I have not been completely alien to the idea of a MDL and even the introductory chapters had a lot to give to me. The book covers in depth the idea of crude MDL, Kolmogorov Complexity, refined MDL and using these ideas in inference with a special focus on model selection.

Objective: A couple of months ago, one of my papers got rejected at a top data-mining conference. The reviews however were pretty encouraging, with one of the reviewers stating that the technique so discussed had the potential to be influential amongst the data mining community at large. However, it seems that the paper lost out due a lack of theoretical justification for why and when it worked, and when it wouldn’t. The experimental evidence was substantial but was clearly not enough to convince the reviewers otherwise. 

I have been trying to outline the contours for a proof over the past month though that is not officially what I am doing. I conceive that the proof would need a use of the Minimum Description Length principle. This comes as an opportunity as I had always wanted to know more of the MDL principle ever since I got introduced to Machine Learning.

_______________________________________________________________________________________________

2. Spectra of Graphs — Andries E. Brouwer, Willem H. Haemers (Expecting to finish the required sections soon)

Download (PDF)

My present work seems to have settled around trying to know more about Incrementral Spectral Clustering [2] (and more efficient mapping of new test points to existing clusters). It is noteworthy that most spectral clustering methods are offline methods and addition of new points is rather difficult. Some weeks ago I was trying to understand the use of the Nyström method for this problem.

I will write a post on spectral clustering in the future. But perhaps there is some merit in discussing it a little.

The basic idea of clustering is the following:

Suppose you have a set of distributions , and that each distribution has an associated weight such that .  Then any dataset could be assumed to have been generated by sampling these distributions, each with a probability equal to their associated weight. The task of clustering is then to identify these distributions. Methods such as Expectation Maximization work with trying to estimate a mixture model. k-means clustering further simplifies the case by assuming that these distributions are simply a mixture of spherical Gaussians.

Trying to model such explicit models of the data is the cause of failure of these methods on many real world datasets that might not have been generated by such distributions (which is most likely the case). Spectral Clustering on the other hand is a metric modification method (essentially a manifold method) that changes the data representation and on this new representation finding natural clusters is much easier.

To do so, the data points are connected as a graph, and we work with the spectra (Eigenvectors) of the graph Laplacian matrix (the laplacian measures the “flow” thus giving a deeper understanding of the data). This is a very beautiful idea (more on a detailed post). Why spectral clustering has become so popular in a short time is not just because it works well, but also because there is a solid theoretical basis for it.

Objective: The above lines sums up the need to read this book. This book is more on Spectral Graph Theory and has a small section on clustering. However it covers many basics that are necessary if one is to aspire to make a contribution to the area. Such as: While working with the Nystrom Method I found myself at a loss to understand the basis for using the Frobenius Norm amongst many others and had to take them on faith. Many other aspects that appeared like black magic earlier just seem like beautiful ideas after reading the book.

The book covers the basics of Graphs to some extent and also of the needed algebra. It then describes the various ideas associated with the spectra of graphs and some applications (such as Google’s PageRank). The second half of the book is beyond my scope at the moment, but it is certainly something that would be of great interest to the more advanced reader.

_______________________________________________________________________________________________

3. The Symmetries of Things – John Conway (Finished Reading)

Rating

The Symmetries of Things - John Conway, Heidi Burgiel, Chaim Goodman-Strauss. (Click on the Image to see the book on Amazon)

I must confess that I was initially disappointed with this book. I had picked this up after weighing it with Prof. David Mumford’s book — Indra’s Pearls: The Vision of Felix Klein . The disappointment perhaps was more given that this book was expensive ($57) and was written by John Conway! Luckily (I suppose) a two day flight delay facilitated a second reading of the book and I changed my mind. And now think this is a brilliant book (not to mention very beautiful with the hardcover and over 1000 illustrations in color).

Given the number of ideas in the book, I will write about this it (and some of the ideas) in a different blog article (which has been in the drafts for over two weeks already!).

_______________________________________________________________________________________________

4. The Beginning of Infinity- David Deutsch (To Read)

The Beginning of Infinity is Quantum Computing pioneer David Deutsch’s most recent book. Highly recommended to me by many researchers I have a lot of respect for, I am yet to begin reading it. Here is the official product description for the book:

The Beginning of Infinity - David Deutsch (Click on Image to view on Amazon)

“This is a bold and all-embracing exploration of the nature and progress of knowledge from one of today’s great thinkers. Throughout history, mankind has struggled to understand life’s mysteries, from the mundane to the seemingly miraculous. In this important new book, David Deutsch, an award-winning pioneer in the field of quantum computation, argues that explanations have a fundamental place in the universe. They have unlimited scope and power to cause change, and the quest to improve them is the basic regulating principle not only of science but of all successful human endeavor. This stream of ever improving explanations has infinite reach, according to Deutsch: we are subject only to the laws of physics, and they impose no upper boundary to what we can eventually understand, control, and achieve. In his previous book, “The Fabric of Reality”, Deutsch describes the four deepest strands of existing knowledge – the theories of evolution, quantum physics, knowledge, and computation-arguing jointly they reveal a unified fabric of reality. In this new book, he applies that worldview to a wide range of issues and unsolved problems, from creativity and free will to the origin and future of the human species. Filled with startling new conclusions about human choice, optimism, scientific explanation, and the evolution of culture, “The Beginning of Infinity” is a groundbreaking book that will become a classic of its kind.”

Here are some reviews of the book.

_______________________________________________________________________________________________

5. The Original of Laura – Vladimir Nabokov (Finished Reading)

Rating

The Original of Laura - Nabokov (Click on the image to view it on Amazon)

“Oh you must! said Winny. It is of course fictionalized and all that, but you’ll come face to face with yourself at every corner. And there’s your wonderful death. Let me show you your wonderful death”

This piece is not for you if you are not already Nabokovian. For this novel is truly unfinished. Being a perfectionist, Nabokov had requested it to be destroyed had he not been able to finish it. And on reading a few cards, one realizes immediately why. It is quite unlike many of his other works, unpolished and raw. The broad contours of the storyline are certainly discernible, however reading it is like wandering inside a mobius labyrinth . I had been waiting with bated breath to get the time to read his final work and would confess I was mildly disappointed. I wondered if his son did the right thing by going against his father’s will by getting it published. The package (hardcover, print, cards of the novel in Nabokov’s writing) is exquisite and is definitely a collectors item. However there is nothing more to it. If you’ve never read anything by Nabokov and want to, then I’d point you to Pale Fire. However, if you ARE Nabokovian, and are willing to spend a little, then this book should certainly find a place in your book shelf.

_______________________________________________________________________________________________

6. Immortality – Milan Kundera (Finished Reading)

Rating

Immortality - Milan Kundera (Click on image to see on Amazon)

There is a certain part of all of us that lives outside of time. Perhaps we become aware of our age only at exceptional moments and most of the time we are ageless.

I have always thought the the true age of an individual was a mental thing and that the actual age did not matter. I have had the good fortune to meet an Indian mathematician who had the chance to work with Israel Gelfand. It is quite well known that some of the deepest contributions in mathematics and science have been made by young men and women. After a certain age the accumulated prejudices make them too conservative to make a revolutionary contribution. Quoting Freeman Dyson:

    … the history of mathematics is a history of horrendously difficult problems being solved by young people too ignorant to know that they were impossible. — Freeman Dyson, “Birds and Frogs”

Israel Gelfand was a prime example of showing us otherwise. He kept making significant contributions till a ripe old age. In that sense Gelfand was ageless. Ofcourse I am not even trying to talk about the name of Gelfand that has already become immortal.

Milan Kundera’s Immortality further refined my thinking of what was meant by Immortal. It starts off with the narrator describing an old woman learning how to swim. A gesture sprung up by the woman after the lesson was more that of a young girl and takes him by surprise. “At the time, that gesture aroused in me immense, inexplicable nostalgia, and this nostalgia gave birth to the woman I call Agnes.” However the author reasons rather paradoxically that the reason might be something else. “there are fewer gestures in the world than there are individuals,” therefore “a gesture is more individual than an individual.” Hence when Agnes dies it does not disturb the author greatly. This reminded me of the last lines from the critically acclaimed Hindi Movie Saaransh about the continuity of life. In any case, from the observation in the start, Kundera weaves out a number of stories and explores a number of themes very beautifully.

This novel is quite unlike The Unbearable Lightness of Being that I had the chance to read a few years ago. That novel explored the life of intellectuals and artists after the Prague spring (and the consequent soviet invasion) of 1968. It had a definite plot and explored a definite notion: The notion of Eternal Recurrence of Nietzsche. There is no definiteness to Immortality however, and it almost redefines what is a novel, almost bordering on being avant-garde towards the end. This is the book I would suggest at the moment to anyone if I were asked. Five stars!

_______________________________________________________________________________________________

7. The Unfolding of Language: An Evolutionary Tour of Mankind’s Greatest Invention — Guy Deutscher (To Read)

The Unfolding of Language - Guy Deutscher (Click on the Image for viewing it on Amazon)

Again a book that I have been meaning to read for a while but get distracted to other books. Click on the image above to learn more about the book!

_______________________________________________________________________________________________

Wish List:

Here a couple of technical books that I want to attempt reading after the summer.

1. Pattern Theory by David Mumford and Agnès Desolneux.

2. Algebraic Geometry and Statistical Learning Theory by Sumio Watanabe.

_______________________________________________________________________________________________

References:

1. Occam’s Razor – Blumer, Ehrenfeucht, Haussler, Warmuth, Information Processing Letters 24 (1987) 377-380.

2. A Tutorial on Spectral Clustering – Ulrike von Luxberg, Statistics and Computing, 17 (4) 2007.

_______________________________________________________________

Onionesque Reality Home >>

Read Full Post »

A Logical Journey: From Gödel to Philosophy

I had an occasion to read this fantastic book over the last couple of months. This book is a compilation by Hao Wang, a confidante of Kurt Gödel. Compiled over ten years it contains Gödel’s views on a wide array of areas. Some of these insights are little known, some are very interesting and some just show that Gödel was just as human in making errors.

This is an unadulterated chronicle of a brilliant mind. I don’t know what else to say to suggest this book. It is a must read for anyone with a remote interest in Mathematical Logic, Philosophy and Kurt Godel.

A Logical Journey - From Godel to Philosophy

[Click on the image to buy this book or click here]

____________

Here is an introduction to the book and the author.

Hao Wang (1921-1995) was one of the few confidantes of the great mathematician and logician Kurt Gödel. A Logical Journey is a continuation of Wang’s Reflections on Kurt Gödel and also elaborates on discussions contained in From Mathematics to Philosophy. A decade in preparation, it contains some important and unfamiliar insights into Gödel’s views on a wide range of issues, from Platonism and the nature of logic, to minds and machines, the existence of god, and positivism and phenomenology.

The impact of Gödel’s theorem on twentieth century thought is on a par with that of Einstein’s theory of relativity, Heisenberg’s uncertainty principle or Keynesian economics. These previously unpublished intimate and informal conversations, however, bring to light and amplify Gödel’s other major contributions to logic and philosophy. They reveal that there is much more in Gödel’s philosophy of mathematics than is commonly realized, and more in his philosophy than just a philosophy of mathematics.

Wang writes that “it is even possible that his quite informal and loosely structured conversations with me, which I am freely using in this book, will turn out to be the fullest existing expression of the diverse components of his inadequately articulated general philosophy”

I will leave you with some quotes from the book. Unless mentioned, they are by Kurt Gödel.

1. To develop the skill of correct thinking is in the first place to learn what you have to disregard. In order to go on, you have to know what to leave out: this is the essence  of effective thinking. (1972, from chapter 1 – Gödel’s life)

2. I would not say that one cannot polemicize against Nietzsche. But it should of course also be a writer [Dichter] or a person of the same type to do that. (17.2.48)

3. What you say about sadness is right : if there were a completely hopeless sadness, there would be nothing beautiful in it. But I believe there can rationally be no such thing. Since we understand neither why this world exists, nor why it is constituted exactly as it is, nor why we are in it, nor why we were born into exactly these and no other external relations: why then should we presume to know exactly this to be all  at there is no other world and that we shall never be in yet another one? (27.2.50)

4. One. cannot really say that complete ignorance is sufficient ground for hopelessness . If e.g. someone will land on an island completely unknown to him, it is just as likely that it is inhabited by harmless people as that it is by cannibals, and his ignorance gives no reason for hopelessness , but rather for hope. Your aversion against occult phenomena is of course well justified to the extent that we are here facing a hard-to-disentangle mixture of deception, credulousness and stupidity, with genuine phenomena. But the result (and the meaning) of the deception is, in my opinion, not to fake genuine phenomena but to conceal them. (3.4.50)

5. Is the book about Einstein really so hard to understand? I think that prejudice against and fear of every “abstraction” may also be involved here, and if you would attempt to read it like a novel (without wanting to understand right away everything at the 6rst reading), perhaps it would not seem so incomprehensible to you. (8.1.51)

6. As you know, I am indeed also thoroughly anti nationalistic, but one cannot, I believe, decide hastily against the possibility that people like Bismarck have the honorable intention to do something good. (7.11.56)

7. About the relation of art and kitsch we have, I believe, already discussed many times before. It is similar to that between light and heavy music. One could, however, hardly assert that all good music must be tragic? (23.3.57)

8. It is always enjoyable to see that there are still people who value a certain measure of idealism. (12.11.61)

9. Of all that we experience, there eventually of course remains only a memory, but just in this way all lasting things retain some of their actuality. (24.3.63)

10. She was not a beauty, but she was an extraordinarily intelligent person and had an extremely important role [in his life], because she was actually what one calls the life-line. She connected him to the earth. Without her, he could not exist at all.

A complicated marriage, but neither could exist without the other. And the idea that she should die before him was unthinkable for him. It is fortunate that he died before her. He was absolutely despondent when she was sick. He said, “Please come to visit my wife.”

She once told me, ‘I have to hold him like a baby.”  (1.4.2-3-4,  Alice Von Kahler on Adele and Kurt Godel)

Einstein and Godel at IAS, Princeton

11.The one man who was, during the last years, certainly by far Einstein‘s best friend, and in some ways strangely resembled him most was Kurt Godel,  the great logician. They were very different in almost every personal way- Einstein gregarious, happy, full of laughter and common sense, and Godel extremely solemn,very serious, quite solitary, and distrustful of common sense as a means of arriving at the truth. But they shared a fundamental quality: both went directly and wholeheartedly to the questions at the very center of things (in Holton and Elkena, Straus 1982:422).

12. Einstein has often told me that in the late years of his life he has continually sought Godel’s company in order to have discussions with him. Once he said to me that his own work no longer meant much, that he came to the Institute merely to have the privilege to walk home with Godel. [“The late years” probably began in 1951 , when Einstein stopped working on the unified theory. 1.6.2 Oskar Morgenstern]

13. The philosophers have only interpreted the world, in various ways, the point, however , is to change it. (Karl Marx, Theses on Feverbach 1845, Chapter 3)

14. The place which philosophy has occupied in Chinese civilization has been comparable to that of religion in other civilizations. In the world of the future, man will have philosophy in the place of religion. This is consistent with the Chinese tradition. It is not necessary that man should be religious, but it is necessary that he should be philosophical. When he is philosophical he has the very best of the blessings of religion. (Fung1 948:1, 6).

15. Engaging in philosophy is salutary in any case, even when no positive results emerge from it (and I remain perplexed). It has the effect  [Wirkung] that “the color [is] brighter,” that is, that reality appears more clearly as such. This observation reveals that , according to Godel’s conception , the study of philosophy helps us to see reality more distinctly , even though it may happen that no (communicable ) positive results come out of it to help others.

16. In presenting these conversations, you should pay attention to three principles: (1) deal only with certain points; (2) separate out the important and the new; and (3) pay attention to connections. Godel, 5 February 1976

17. The notion of existence is one of the primitive concepts with which we must begin as given. It is the clearest concept we have. Even “all”, as studied in predicate logic, is less clear, since we don’t have an overview of the whole world. We are here thinking of the weakest and the broadest sense of existence. For example, things which act are different from things which don’t. They all have existence proper to them. (4.4.12)

18. Existence: we know all about it, there is nothing concealed. The concept of existence helps us to form a good picture of reality. It is important for supporting a strong philosophical view and for being open-minded in reaching it. (4.4.13)

19. Power is a quality that enables one to reach one’s goals. Generalities contain the laws which enable you to reach your goals. Yet a preoccupation with power distracts us from paying attention to what is at the foundation of the world, and it fights against the basis of rationality. (4.4.14)

20. The world tends to deteriorate: the principle of entropy. Good things appear from time to time in single persons and events. But the general development tends to be negative. New extraordinary characters emerge to prevent the downward movement. Christianity was best at the beginning. Saints slow down the downward movement. In science, you may say, it is different. But progress occurs not in the sense of understanding the world, only in the sense of dominating the world, for which the means remains, once it is there. Also general knowledge though not in the deeper sense of first principles, has moved upwards. Specifically, philosophy tends to go down. (4.4.15)

21. The view that existence is useful but not true is widely held; not only in mathematics but also in physics, where it takes the form of regarding only the directly observable [by sense perception] as what exists. This is a prejudice of the time. The psychology behind it is not the implicit association of existence with time, action, and so on. Rather the association is with the phenomenon that consistent but wrong assumptions are useful sometimes. Falsity is in itself something evil but often serves as a tool for finding truth. Unlike objectivism, however, the false assumptions are useful only temporarily and intermediately. (4.4.16)

22. Einstein’s religion is more abstract, like that of Spinoza and Indian philosophy. My own religion is more similar to the religion of the churches. Spinoza’s God is less than a person. Mine is more than a person, because God can’t be less than a person. He can play the role of a person. There are spirits which have no body but can communicate with and influence the world. They keep [themselves] in the background today and are not known. It was different in antiquity and in the Middle Ages, when there were miracles. Think about deja vu and thought transference. The nuclear processes, unlike the chemical , are irrelevant to the brain.

23. The possible worldviews [can be divided] into two groups [conceptions]: skepticism, materialism and positivism stand on one [the left] side; spiritualism, idealism and theology on the other [the right]. The truth lies in the middle,or consists in a combination of these two conceptions. (Chapter 5)

24. Some reductionism is right: reduce to concepts and truths, but not to sense perceptions. Really it should be the other way around: Platonic ideas [what Husserl calls “essences ” and Godel calls “concepts”] are what things are to be reduced to. Phenomenology makes them [the ideas] clear. (5.3.15)

25. Introspection is an important component of thinking; today it has a bad reputation. Introspective psychology is completely overlooked today. Epoche concerns how introspection should be used, for example, to detach oneself from influences of external stimuli (such as the fashions of the day). Even the scientists (fashions of the day). Even the scientists [sometimes] do not agree because they are not [detached true] subjects [ in this sense].

26. Positivists decline to acknowledge any apriori knowledge. They wish to reduce everything to sense perceptions. Generally they contradict themselves in that they deny introspection as experience, referring to higher mental phenomena as “judgments”. They use too narrow a notion of experience and introduce an arbitrary bound on what experience is, excluding phenomenological experience. Russell (in his 1940 (Inquiry into Meaning and Truth]) made a more drastic mistake in speaking as if sense experience were the only experience we can find by introspection.

27. For approaching the central part of philosophy, there is good reason to confine one’s attention to reflections on mathematics. Physics is perhaps less well suited for this purpose; Newtonian physics would be better. (Chapter 9)

28. The meaning of the world is the separation of wish and fact. (Chapter 9)

29. Whole and part– partly concrete parts and partly abstract parts- are at the bottom of everything. They are most fmtdamental in our conceptual system. Since there is similarity, there are generalities. Generalities are just a fundamental aspect of the world. It is a fundamental fact of reality that there are two kinds of reality: universals and particulars (or individuals).

30. Zhi zhi wei zhi zhi, bu zhi wei bu zhi, shi zhi ye. (To know that you know when you do know and know that you do not know when you do not know: that is knowledge .) Confucius, Analects, 2: 17. (Epilogue).

____________

Onionesque Reality Home >>

Read Full Post »

American Prometheus

I wrote rather passionately about J. Robert Oppenheimer in one part of a previous post marking an anniversary of the first nuclear bombings. Those interested in Oppenheimer’s life might be interested in reading that part.

I read American Prometheus: The Triumph and Tragedy of J. Robert Oppenheimer (Buy it) by Kai Bird and Martin Sherwin between 14-29 October. And it is amongst the best biographies I have read. It is a very different book, it is not inspiring like some biographies on great men are. It is not philosophical or based on some mad pursuit. I have never seen such a well researched biography before. Sometimes I found the details about Oppenheimer’s personal life nauseating, but that just indicates the amount of surveillance he was under.

This book is not inspiring, it is haunting*.

[American Prometheus- Kai Bird, Martin Sherwin. Image Source ]

A Pulitzer prize winner (2006), this book chronicles the life of physicist, administrator, poet, American patriot and the father of the atomic bomb from his very early days to his last. The authors delve into every aspect of Oppenheimer’s life from his birth, to his time in England and Germany as a student. His leftist days at Berkeley, his love interests, his role in the Manhattan project, his public humiliation in the security hearings of 1954 at the height of the red scare and his quiet life after that, till his death. Twenty five years of research by the authors culminated into a devastatingly sad biography of one of the most famous men of all time.

The prologue in the book quotes George Kennan (1904-2005) the famous American diplomat now known as the father of the containment policy during the red scare as saying the following about him:

“In the dark day of the early fifties, when troubles crowded in upon him from many sides and when he found himself harassed by his position at the center of controversy, I drew his attention to the fact that he would be welcomed in a hundred academic centers abroad and asked him whether he had not thought of taking academic residence outside this country. His answer, given to me with tears in his eyes: ‘Damn it, I happen to love this country’“

The book is divided into 5 parts and 40 chapters, each part covering a stage in his life. I would request all who get the opportunity to read this book, even those who have personal enmity with science and scientists but read once in a while about general things.

Some sections of the book are striking and stunning and represent major turning points in the book and just stand out.

—

While reading I observed that the authors place very clearly facts about the “Apple Incident” in which I was interested ever since I read about it, where in a state of depression and enormous emotional distress in his troubled student days at Cambridge, England in the autumn of 1925 Oppenheimer placed a “poisoned” apple on the desk of his head tutor, Patrick Blackett (few people know that Blackett was an adviser to Jawaharlal Nehru). The authorities learned of the incident and after some talking with his parents he was allowed to stay at Cambridge subject to the condition that he visit the psychiatrist as per a mandated chart. Oppenheimer gradually recovered and thrived in his golden intellectual days at Gottingen, Germany shortly afterwards when he produced some fundamental research and became known as one of the best quantum physicists of the time. The time bracket from this period at gottingen to his days as the Director of the Manhattan Project were his best days. By the end of 1945 Oppenheimer was one of the most famous physicists of the time.

[The above photo of Oppenheimer’s porkpie hat was the cover of Physics Today in May 1948, exemplifying the high regard and respect Oppenheimer commanded at that time. Image Soure]

—

Taking a brief digression, I’d cite two of my favorite quotes from the book:

After the emotional turmoil of his student days in England, Oppenheimer was always trying to be above that. His guiding principles were discipline and work. Quoting him from a letter to his brother.

Discipline is good for the soul is more fundamental than any of the grounds given for its goodness. I believe that through discipline, though not through discipline alone, we can achieve serenity, and a certain small but precious measure of freedom from the accidents of incarnation…I believe that through discipline we learn to preserve what is essential to our happiness in more and more adverse circumstances, and to abandon with simplicity what would else have seemed to us indispensable.

There is another fantastic quote attributed to P.A.M Dirac, the legendary physicist who was known to be eccentrically single minded to his dedication of science. Once Oppenheimer gave him several books as a gift. Dirac politely refused and remarked:

Reading books interfered with thought.

—

The Beast In the Jungle: I mentioned just a paragraph earlier that there were some very strong parts in the book that represented a watershed in his life. Some of them were just stunning. Like this part named “The Beast In the Jungle“. Until this section of the book Oppenheimer had been doing fine even though the number of his enemies were increasing. It was after this chapter that his decline began or rather accelerated.

The authors mention that Oppenheimer had harbored a vague sort of a premonition that something dark was in store for him in the future for a while. In the late 40s he read a novella by Henry James written in 1903 titled “The Beast in the Jungle“. James’ story was one of obsession, tormented egotism and as the authors put it, of existential foreboding. The story is very short, I have placed a link below to read the book from, for those interested. I could finish it under a couple of hours only. The basic plot of this story is as (from wikipedia):

John Marcher, the protagonist, is reacquainted with May Bartram, a woman he knew ten years earlier, who remembers his odd secret: Marcher is seized with the belief that his life is to be defined by some catastrophic or spectacular event, lying in wait for him like a “beast in the jungle.” May decides to buy a house in London with the money she got from her Great-Aunt who passed away, and to spend her days with Marcher curiously awaiting what fate has in store for him. Marcher is a hopeless egoist, who believes that he is precluded from marrying so that he does not subject his wife to his “spectacular fate”.

He takes May to the theatre and invites her to an occasional dinner, but does not allow her to get close to him. As he sits idly by and allows the best years of his life to pass, he takes May down as well, until the denouement where he learns that the great misfortune of his life was to throw it away, and to ignore the love of a good woman, based upon his preposterous sense of foreboding.

Oppenheimer was struck by the charge of the story and asked his friend Herb Marks to read it. After the bombings of Hiroshima and Nagasaki, as the authors write citing evidence Oppenheimer lived with a similar feelings that someday he would be struck by his “beast in the jungle” which would alter his whole life. Oppenheimer knew he was kept track of and that people in the Govt and the intelligence were looking for evidence to destroy him. As it turned out, his beast in the jungle was Lewis Strauss, who destroyed him.

Einstein and Oppenheimer: The parts on Einstein in the book were interesting.

[Einstein and Oppenheimer at IAS: Image source]

The book mentions Einstein in numerous instances throughout. However the ones related to Oppenheimer are the ones that I intend to touch upon.

Einstein could not understand why Oppenheimer was so keen on maintaining access to Washington and the echelons of the government. Einstein by instinct disliked politicians, and figures of authority. I quoted him in one previous post on this:

To punish me for my contempt of authority, fate made me an authority myself.

Einstein was always uncomfortable with attention is a well known fact to all those who admire him. There was this unforgettable quote in the book by him. On Einstein’s 71st birthday, Oppenheimer was walking him to his residence and Einstein said:

You know, when it’s once been given to a man to do something sensible, afterward life is a little strange.

Einstein suggested to Oppenheimer that he resign just taking into account the sheer outrageousness of the attacks on him. Einstein had left Germany when the Nazi nationalist frenzy swept the country and never set his foot on Germany again. He believed that the rise of McCarthyism in America was alarming, and he thought that Oppenheimer would end up humiliating himself.

As the authors note that Einstein’s instincts were right. He confided to a friend:

Oppenheimer is not a gypsy like me, I was born with the skin of an Elephant; there is no one who can hurt me.

and he thought that Oppenheimer was the reverse.

I would once again suggest the book to everyone who can set his/her hands on it. I would also congratulate the authors for the extremely gripping and compelling biography, it is amazing to think that the authors could piece together research spread over 25 years in such a wonderful way and I am already not able to get myself to complete a 60 page report on a project based on Support Vector Machines, in which I don’t even have to “piece together” things.

* This line is in no way borrowed from, or inspired by the newsweek review on this book.

—

Links:

1. American Prometheus: The Triumph and Tragedy of J. Robert Oppenheimer – Kai Bird and Martin Sherwin

2. The Beast in the Jungle – Henry James (Download it from Project Gutenberg)

—

Onionesque Reality Home >>

Read Full Post »