Feeds:
Posts

## Proof that 2^(1/n) is irrational

After an interesting conversation with somebody recently I was looking around and aggregating simple mathematical facts that have somewhat crazy proofs. Like for all such questions, I found a great MathOverflow thread and decided to share this gem from there:

Fact: $\sqrt[n] {2}$ is irrational for any integer $n \geq 3$.

Proof: Suppose it is not. Then $\displaystyle \sqrt[n] {2} = \frac{p}{q}$, then $2 q^n = p^n$, or $p^n = q^n + q^n$ contradicting Fermat’s Last Theorem.

Although a commenter there mentions that the argument is essentially circular (which I find fascinating), but other than that it made me laugh, what I find interesting about this answer and an accompanying comment by Greg Kuperberg is that it made me realize that Fermat’s Last Theorem is not strong enough to imply the irrationality of $\sqrt{2}$.

## “Not Even Wrong”

Not only is it not right, it’s not even wrong! – Wolfgang Pauli

I just found a delightful joke concerning Pauli while rummaging through my email, thought it was worthy of sharing!

The phrase “Not Even Wrong” ofcourse was famously coined by Wolfgang Pauli, who was known to be particularly acerbic to sloppy thinking. The wiki entry for the phrase has the following story on how it originated. Rudolf Peierls writes that “a friend showed Pauli the paper of a young physicist which he suspected was not of great value but on which he wanted Pauli’s views. Pauli remarked sadly,”Not only is it not right, it’s not even wrong!”

Coming to the email which centers around being “Not even wrong”:

Wolfgang Pauli

Exactly, Pauli could be pretty scathing in his reviews. Visiting physicists delivering a presentation would dread seeing him in the audience. Pauli would sit and listen and scowl, arms crossed, and shake his head. The faster he shook his head, the more he disagreed with you.

The joke goes that when Pauli died he asked God why the fine structure constant has the value 1/(137.0) … God went to a blackboard and began scribbling equations. Pauli soon started shaking his head violently…

Note: I didn’t write this but apparently I read it somewhere a few years ago and mailed it to somebody. I googled for parts of it, but couldn’t locate the source. If you happen to know, then please link me up!

________________

Onionesque Reality Home >>

## An Overcoming

A Random Post on silence.

The Silence that lives in Houses, Matisse (1947)

One should speak only when one may not remain silent; and then speak only of that which one has overcome—everything else is chatter, “literature,” lack of breeding. My writings speak only of my overcomings: “I” am in them, together with everything that was hostile to me, ego ipsissimus, indeed, even if a yet prouder expression be permitted, ego ipsissimum.

Nietzsche – Maxims & Opinions (1886)

________________

The solution of the problem of life is seen in the vanishing of the problem. (Is not this the reason why those who have found after a long period of doubt that the meaning of life became clear to them have been unable to say what constituted that sense?) (6.521)

Whereof one can not speak, one must pass over in silence (7)

Wittgenstein – Tractatus Logico Philosophicus (1922)

________________

You need not leave your room. Remain sitting at your table and listen. You need not even listen, simply wait, just learn to become quiet, and still, and solitary. The world will freely offer itself to you to be unmasked. It has no choice; it will roll in ecstasy at your feet.

Kafka – Aphorisms (1918)

________________

Onionesque Reality Home >>

## 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 ﬁnd that these eigenfunctions (again applied to the 1-skeleton of the Vietoris-Rips complex of a point cloud) also can produce useful ﬁlters 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 >>

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)

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 $K$ distributions $\displaystyle \mathcal D = \{ D_1, D_2 \dots D_K \}$, and that each distribution has an associated weight $\{w_1, w_2 \dots w_K \}$ such that $\displaystyle \sum_i w_i = 1$.  Then any dataset could be assumed to have been generated by sampling these $K$ distributions, each with a probability equal to their associated weight. The task of clustering is then to identify these $K$ 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.

_______________________________________________________________________________________________

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 >>

## First Blog Post Citation

This is a first for this blog, and hence worth mentioning.

I came across a paper that is to appear in the proceedings of the IEEE Conference on Computer Systems and Applications 2010. Find the paper here.

This paper cites an old post on this blog, one of the first few infact. This is reference number [2] on the paper. It was good to know, and more importantly, a boost to blog to discuss small ideas that are otherwise improper for a formal presentation.

___________

Since it is lame to write just the above lines, I leave you with a couple of talks that I watched over the friday night and I would highly recommend.

There was a talk by Machine Learning pioneer Geoffrey Hinton some years ago at Google Tech Talks that became quite a hit. This talk was titled The Next Generation of Neural Networks that discusses Restricted Boltzmann Machines, and how this generative approach can lead to learning complex and deep dependencies in the data.

There was a follow up talk recently, that I had long bookmarked, but just got around to seeing yesterday. This like the previous is a fantastic talk that has completed my conversion to begin exploring deep learning methods. :)

Here is the talk –

Another great talk that I had been looking at last night was a talk by Prof Yann LeCun

Here is the talk –

This talk is started by the late Sam Roweis. It feels good at one level to see his work preserved on the internet. I have quite enjoyed talks by him at summer schools in the past.

___________

Onionesque Reality Home >>

## Taught Bio-Informatics (UG)

I am in the process of winding up taking a basic course on Bio-Informatics, it is offered as an elective subject for final year under-graduate Information Technology students.  I preferred taking this course as a visiting faculty on weekends as managing time in the week is hard (though i did take some classes on weekdays).

______

[Gene Clustering : (a) shows clusters (b) uses hierarchical clustering (c) uses k-means (d)  SOM finds clusters which are arranged in grids. Source : Nature Biotechnology 23, 1499 – 1501 (2005) by Patrick D’haeseleer]

Why Bio-Informatics?

The course (out of the ones offered in Fall) I would have preferred taking the most would have been a course on AI. There is no course on Machine Learning or Pattern Recognition at the UG level here, and the course on AI comes closest as it has sufficient weight given to Neural Nets and Bayesian Learning.

The only subject that comes nearest to my choice as AI was not available, was Bio-Informatics as about 60 percent of the syllabus was Machine Learning, Data Mining and Pattern Recognition. And it being a basic course gave me the liberty to take these parts in much more detail as compared to the other parts. And that’s exactly why taking up Bio-Informatics even though it’s not directly my area was not a bad bargain!

______

The Joys of Teaching:

This is the first time that I have formally taken a complete course, I have taken work-shops and given talks quite a few times before. But never taken a complete course.

I have always enjoyed teaching. When I say I enjoy teaching, I don’t necessarily mean something academic. I like discussing ideas in general

If I try to put down why I enjoy teaching, there might be some reasons:

• There is an obvious inherent joy in teaching that few activities have for me. When i say teaching here, like I said before I don’t just mean to talk about formal teaching, but rather the more general meaning of the term.
• It’s said that there is no better way to learn than to teach. Actually that was the single largest motivation that prompted me to take that offer.
• Teaching gives me a high! The time I get to discuss what I like (and teach), I forget things that might be pressing me at other times of the day. I tend to become a space-cadet when into teaching. It’s such a wonderful experience!
• One more reason that i think i like teaching is this : I have a wide range of reading (or atleast am interested in) and I have noticed that the best way it gets connected and in most unexpected ways is in discussions. You don’t get people who would be interested in involved discussions very often, also being an introvert means the problem is further compounded. Teaching gives me a platform to engage in such discussions. Some of the best ideas that I have got, borrowing from a number of almost unrelated areas is while discussing/teaching. And this course gave me a number of ideas that I would do something about if I get the chance and the resources.
• Teaching also gives you the limits of your own reading and can inspire you to plug the deficiencies in your knowledge.
• Other than that, I take teaching or explaining things as a challenge. I enjoy it when I find out that I can explain pion exchanges to friends who have not seen a science book after grade 10. Teaching is a challenge well worth taking for a number of reasons!

From this specific course the most rewarding moment was when a couple of groups approached me after the conclusion of classes to help them a little with their projects. Since their projects are of moderate difficulty and from pattern recognition, I did take that up as a compliment for sure! Though I can not say I can “help” them,  I don’t like using that word, it sounds pretentious, I would definitely like to work with them on their projects and hopefully would learn something new about the area.

______

Course:

I wouldn’t be putting up my notes for the course, but the topics I covered included:

1. Introduction to Bio-Informatics, Historical Overview, Applications, Major Databases, Data Management, Analysis and Molecular Biology.

2. Sequence Visualization, structure visualization, user interface, animation verses simulation, general purpose technologies, statistical concepts, microarrays, imperfect data, quantitative randomness, data analysis, tool selection, statistics of alignment, clustering and classification, regression analysis.

3. Data Mining Methods & Technology overview, infrastructure, pattern recognition & discovery, machine learning methods, text mining & tools, dot matrix analysis, substitution metrics, dynamic programming, word methods, Bayesian methods, multiple sequence alignment, tools for pattern matching.

4. Introduction, working with FASTA, working with BLAST, filtering and capped BLAST, FASTA & BLAST algorithms & comparison.

Like I said earlier, my focus was on dynamic programming, clustering, regression (linear, locally weighted), Logistic regression, support vector machines, Neural Nets, an overview of Bayesian Learning. And then introduced all the other aspects as applications subsequently and covered the necessary theory then!

______

Resources:

All my notes for the course were hand-made and not on $\LaTeX$, so it would be impossible to put them up now (they were basically made from a number of books and the MIT-OCW).

H0wever I would update this space soon enough linking to all the resources I would recommend.

______

I am looking forward to taking a course on Digital Image Processing and Labs the next semester, which begins December onwards (again as a visiting instructor)! Since Image Processing is closer to the area I am interested in deeply (Applied Machine Learning – Computer Vision), I am already very excited about the possibility!

______

Onionesque Reality Home >>