Feeds:
Posts
Comments

Archive for 2010

This question appears very trivial and might just be meaningless, so I put it up at the risk of embarrassing myself. However, since it is a genuine question. I still put it up. All thoughts are welcome.

Question: When trying to quantify the performance of a classifier. What advantages does RMSE offer over the Area under the Curve under the ROC metric? And what does the AUC offer that the RMSE does not? I find AUC very intuitive and prefer using it for classification tasks. But can I give a theoretical reason for using it above RMSE and the vice versa? Review committees have different preferences, some journals prefer reporting the RMSE while some prefer the AUC, some ask for both. Another example being – The 2010 KDD Cup used RMSE while the 2010 UCSD data mining competition used AUC.

Or is this a bad question to ask?

To paraphrase my question – What can be instances in which a classifier is deemed as “good” by the AUC measure and “not so good” by the RMSE measure. What would be the exact reason for such a different “opinion”? And in what situations should I use AUC and in what situations should I use RMSE?

Some Background : If they are equivalent, then you would expect a strong linear relationship (with a negative correlation). That means that for a perfect classifier RMSE would be zero and the AUC 1.

I always use both for all purposes. Here is a sample graph.

RMSE versus AUC for a classifier on some Intelligent Tutoring Data

This is actually a very typical graph, and there are no surprises with it. If you leave out some “bad examples” such as those at (0.4, 0.65) and (0.38, 0.7), the graph has a good negative correlation (as measured by the line fit).

So, the question remains for me. What are the advantages and disadvantages of both?

Recommendations :

1. ROC Graphs : Notes and Practical Considerations for Researchers – Tom Fawcett

Read Full Post »

Benoit Mandelbrot Dies

Benoit Mandelbrot (20 November 1924 – 14 October 2010)

Cesaro as quoted by Benoit Mandelbrot on limits in Koch Curves and fractals:

The will is infinite
and the execution confined
The desire is boundless
and the act a slave to limit.

From Mandelbrot’s seminal book on fractal geometry “The Fractal Geometry of Nature” (1982). This book has more digressions and quotations than any other book I think.

Mandelbrot was not like Feynman for me, not the kinds I could call a childhood hero, but the kind of person I liked more and more as I grew up. I was extremely saddened by the news of his demise today morning.

RIP!

As a tribute to Mandelbrot and his immense contribution. I would highly recommend this extremely wonderful PBS documentary.

[Click on the Image to Play]

If for some reason the above does not work – check the documentary out on googlevideo.

______________

Links:

New York Times Obituary

______________

Onionesque Reality Home >>

Read Full Post »

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

Read Full Post »

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 »

I am late with my echo statement on this.

Over the past few days, the internet is abuzz with news of Craig Venter and his team for creating the first fully functional cell, controlled by synthetic DNA and discussions on what might be the ethical consequences of future work in this area.

The fact that this has happened is not surprising at all. Dr Venter has been very open about his work and has been promoting it for some years now.  For instance, a couple of years ago there was a wonderful TED talk in which Venter talks about his team being close to creating synthetic life. The latest news is ofcourse not of synthetic life, but a step closer to that grand aim.

Another Instance : Two years there was a brainstorming session whose transcript was converted by EDGE into a book available for free download too.

Dimitar Sasselov, Max Brockman, Seth Lloyd, George Church, J. Craig Venter, Freeman Dyson, Image Courtesy - EDGE

The BOOK can be downloaded from here.

So from such updates, it did not surprise me much when Venter made the announcement.

____________

Ethics : There have been frenzied debates on what this might lead us to on the internet, on television and elsewhere. These discussions on ethics appear to me to be inevitable and I find it most appropriate to quote the legendary Freeman Dyson on it.

“Two Hundred years ago, William Blake engraved The Gates of Paradise, a little book of drawings and verses. One of the drawings, with the title “Aged Ignorance”, shows an old man wearing professional eyeglasses and holding a large pair of scissors. In front of him, a winged child running naked in the light from a rising sun. The old man sits with his back to the sun. With a self satisfied smile he opens his scissors and chips the child’s wings. With the picture goes a little poem :

“In Time’s Ocean falled drown’d,
In aged ignorance profound,
Holy and cold, I clip’d the Wings
Of all Sublunary Things.”

This picture is an image of the human condition in the era that is now beginning. The rising sun is biological science, throwing light of every increasing intensity onto the processes by which we live and feel and think. The winged child is human life, becoming for the first time aware of itself and its potentialities in the light of science. The old man is our existing human society, shaped by ages of past ignorance. Our laws, our loyalities, our fears and hatreds, our economic and social injustices, all grew slowly and are deeply rooted in the past. Inevitably the advance of biological knowledge will bring clashes between the old institutions and new desires for human improvement. Old institutions will clip the wings of human desire. Up to a point, caution is justified and social constraints are necessary. The new technologies will be dangerous as well as liberating. But in the long run, social constraints must bend to new realities. Humanity can not live forever with clipped wings. The vision of self-improvement which William Blake and Samuel Gompers in their different ways proclaimed, will not vanish from the Earth.”

(The above is an excerpt from a lecture given by Freeman Dyson at the Hebrew University of Jerusalem in 1995. The lecture was pulished by the New York Review of Books in 1997 and later as a chapter in Scientist as Rebel. )

Artificial Life Beyond the Wet Medium :

Life is a process which can be abstracted away from any particular mediumJohn Von Neumann

Wet Artificial-Life is what is basically synthetic life (in synthetic life you don’t really abstract the life process into another medium, but you digitize it and recreate it instead as per your requirement).

I do believe abstracting and digitizing life from a “wet chemical medium” to a computer is not very far off either i.e. a software that not only would imitate “life” but also synthesize it. And coupled with something like Koza’s Genetic Programming scheme embedded in it, develop something that possesses some intelligence other than producing more useful programs.

Coded Messages :

This is the fun part from the news about Venter and his team’s groundbreaking work. The synthetic DNA of the bacteria has a few messages coded into it.

1. “To live, to err, to fall, to triumph, to create life out of life.” – from James Joyce’s A Portrait of the Artist as a Young Man.

James Joyce is one of my favourite writers*, so I was glad that this was encoded too. But I find it funny that what this quote says can also be the undoing of synthetic life or rather a difficult problem to solve. The biggest enemy of synthetic life is evolution (creating life out of life :), evolution would ensure that control of the synthetic bacteria is lost soon enough. I believe that countering this would be the single biggest challenge in synthetic biology.

*When I tried reading Ulysses, I kept giving up. But had this compulsive need to finish it anyway. I had to join an Orkut community called “Who is afraid of James Joyce” and after some motivation could read it! ;-)

2. What I can not build, I can not understand – Richard P. Feynman

This is what Dr Venter announced, isn’t “What I can not create, I do not understand” the correct version?

Feynman's Blackboard at the time of his death: Copyright - Caltech

3. “See things not as they are, but as they might be” – J. Robert Oppenheimer from American Prometheus

____________

Recommendations :

1. What is Life – Erwin Schrodinger (PDF)

2. Life – What A Concept! – EDGE (PDF)

3. A Life Decoded : My Genome, My Life – C. J. Venter (Google Books)

____________

Onionesque Reality Home >>

Read Full Post »

N is a Number : A Portrait of Paul Erdős is one of the most delightful, endearing and probably one of the best documentaries I have seen on an individual. I have always regarded Paul  Erdős as one of my personal heroes and hence It seems weird that I had not seen this rather old documentary earlier. Especially given it’s extremely high quality, appeal and not to mention the character it is based on.  However, it is never late to discover something so good.

There is an extremely good wikipedia entry on Paul Erdős. However I would still write a few words on him before linking to the videos.

A Mathematician is a machine for turning coffee into theorems.

— An extremely famous quote attributed to Alfréd Rényi. It was originally intended for Hungarian mathematicians and the mathematical-circles culture that flourished there giving the world so many mathematical giants.

__________

Erdős was an extremely prolific and famously eccentric mathematician, producing more papers and collaborating with more people than anybody in history. His eccentricity made him an extremely lovable character, and he made a fair share in contributing to human comedy.

He had no home and no full time job, he traveled around the world for half a century. Surviving on living with collaborators, fees from lectures and other appearances. His dis-interest in anything carnal or materialistic was almost Zen like I would dare say. Just having two pairs of half empty suitcases as his only belongings as he moved along from one location onto another.

It is often said (and quite correctly) that if you finish all bees in the world, the world would not survive for long. We could use that as an allegory for the sciences /mathematics as well. Erdős was essentially a bee. Brilliant in many areas of mathematics, he traveled from place to place using one idea from one area into another, cross-pollinating them, generating interest with his lovable anecdotes and enriching Mathematics as a consequence. A welcome departure from the so called purists.

His mathematical output was so prolific that a tribute is the famous Erdős number that gives the collaborative distance of a mathematician with him. The reason for such astounding output was not just his love for only mathematics but a brilliant memory. Colleagues have remarked that he could remember problems discussed years ago and exactly what the details that were talked about. If a mathematical problem was left half way, he could still remember where was the point they stopped, even if revisited after years. Not just that, he had this knack of knowing the mind of other mathematicians in where their interests lay. So he knew who would like to work on what kind of problems.

Though Mathematics was his only love, his knowledge was extremely wide and he could talk with most people about most things they might be interested in. Almost educated in the classical European style, with interests spreading across other basic sciences, politics, history. literature etc.

His work was not rich just in quantity. He displayed an extremely good taste in choosing and posing problems. The solutions to some of which have resulted in entirely new areas of Mathematics. Paul Erdős had been a towering figure even while he was alive, but as more time passes by, he only grows taller.

__________

N is a Number : A Portrait of Paul Erdős – Videos

Total Runtime : 57 Minutes

[View Here]

– Based on the book “The man who only loves numbers” by Paul Hoffman.

– Made by George Paul Csicsery 1993

– Narrated by James Locker

– Music by Mark Adler (I have to mention the music as I thought it was pretty beautiful, especially towards the end)

__________

Hat Tip : To Dr Vitorino Ramos’ ever thoughtful blog

__________

Onionesque Reality Home >>

Read Full Post »

I have been involved in a major project on contrast enhancement of Magnetic Resonance Images by using Independent Component Analysis (ICA) and Support Vector Machines (SVM) for the past couple of  months. It is an extremely exciting project and also something new for me, as I have worked on bio-medical images just once before. In the past, I have used ICA and SVM in face recognition/authentication, however this application is quite novel.

This post intends to introduce the problem, discuss a motivating example, some methods, expected work and some problems.

__________

A Simple Introduction and Motivating Example:

The simplest motivating example for this problem is the famous cocktail party problem:

You are at a cocktail party, and there are about 12 people present with each talking simultaneously. Add to that a music source. So that makes it 13.

Suppose you want to follow what each person was saying later and for doing so you place a number of tape recorders at different locations in the room (let’s not worry about the number of recorders right now). When you hear them later, the sounds would hardly be understandable as they would be mixed up.

Now you define an engineering problem : that using these recordings (which are basically mixtures), separate out the different sources with as little distortion as possible. In a real time cocktail party, the brain shows[1][2][3] a remarkable ability to follow one conversation. However such a problem has proved to be quite difficult in signal processing. Let’s just illustrate the cocktail party problem in a cartoon below :

 

The Cocktail Party Problem

Please listen to a demo of the cocktail party problem at the HUT ICA project page.

__________

The Logic Behind Constructing MR Images in Simple Terms:

Now, keeping the previous brief discussion in mind. Let’s introduce in simple words how MRI works. This is just a simplification to make the idea clearer, and not really how MRI works.  Discussing MRI in detail would divert the focus of the post. To look at how MRI works follow these highly recommended tutorials[4][5][6]:

Suppose your body is placed in a Magnetic Field (let’s not worry about specifics yet). Consider two contiguous tissues in your body – X and Y. When subject to a magnetic field, the particles (protons) in the tissues would get aligned according to the field. The amount of magnetization would depend on the tissue type. Now suppose we want to measure how much a tissue gets magnetized. One way to think about it is like this : First apply the magnetic field, after the application the particles would get excited. Once the field is removed, these particles would tend to relax to their ground state. By being able to measure the time it takes for the particles to return, we would get some measure of the magnetization of the tissue(s). This is because, the greater the time for relaxation, greater the magnetization.

An image is basically a measure of the energy distribution. Now suppose we have the measurements for tissues X and Y, and since they were of a different nature (composition, density of protons etc), their response to the field would have been different. Thus we would get some contrast between them and thus would get an image.

In very simplistic terms, this is how MRI scans are obtained. Though as mentioned above, please follow [4][5][6] for detailed tutorials on MRI.

__________

MRI scans of the Brain and the Cocktail Party Problem :

Now consider the above discussion in context of taking a MRI scan of the brain. The brain has a number of constituents. Some being : Gray Matter, White Matter, Cerebrospinal Fluid (CSF) Fat, Muscle/Skin, Glial Matter etc. Now since each is unique, they would exhibit unique characteristics under a magnetic field. However, while taking a scan, we get one MRI image of the entire brain.

These scans can be considered as an equivalent to the mixtures of the cocktail party example. If we apply blind source separation to these, we should be able to separate out the various constituents such as gray matter, white matter, CSF etc. These images of the independent sources can be used for better diagnosis. This would be something like this :

If suppose the Simulated MR scans (from the McGill Simulated brain Database) were as follows:

 

Simulated MR Scans

 

 

The “ground truth” images for these scans would be as follows :

 

Ground Truth Images of Different Brain Tissue Substances

__________

Restatement of the Broad Research Problem and Use of ICA and SVM:

Magnetic Resonance Imaging is superior to Computerised Tomography for brain imaging at least, for the reason that it can give much better soft tissue contrast (because even small changes in the proton density and composition in the tissue are well represented).

Like for most techniques, improvements to scans obtained by MRI are much desired to improve diagnosis. Blind source separation has been used to separate physiologically different components from EEG[7]/MEG[8] data (similar to the cocktail party problem), financial data[9] and even in fMRI[10][11]. But it has not received much attention for MRI. Nakai et al[12] used Independent Component Analysis for the purpose of separating physiologically independent components from MRI scans. They took MR images of 10 normal subjects, 3 subjects with brain tumour and 1 subject with multiple sclerosis and performed ICA on the data. They reported success in improving contrast for gray and white matter, which was beneficial for the diagnosis of brain tumour. The demylination in Multiple sclerosis cases was also enhanced in the images. They suggested that ICA could potentially separate out all the tissues which had different relaxation characteristics (different sources of the cocktail party example). This approach thus shows much promise.

In more technical terms : Consider a set of MR frames as a single multispectral image. Where each band is taken during a particular pulse sequence (will be discussed below). Then use ICA on the data to separate out the physiologically independent components. A classifier such as the SVM can improve the contrast further of the separated independent components.

However, using ICA for MRI has been tricky, something I would discuss towards the end of this post and also in future posts.

Before doing so, I intend to touch up on the basics for the sake of completeness.

__________

Magnetic Resonance Imaging:

I had been thinking of writing a detailed tutorial on MRI, mostly because it requires some basic physics. However I don’t think it is required. I would recommend [4][5][6] for a study of the same in sufficient depth. I have recently taken tutorials on MRI, and would be willing to write for the blog if there are requests.

__________

An Introduction to Independent Component Analysis:

Independent Component Analysis was developed initially to solve problems such as the cocktail party problem discussed above.

Let’s formalize a problem like the cocktail party example. For simplicity let us assume that there are only two sources and two mixtures (obtained by keeping two recorders at different locations in the party).

Let’s represent these two mixtures as x_1 and x_2, and let s_1 and s_2 be the two sources that were mixed. Since we are assuming that the two microphones were kept at different locations, the mixtures x_1 and x_2 would be different.

We could write this as:

x_1 = a_{11}s_1 + a_{12}s_2 \quad \cdots \quad (1)

x_2 = a_{21}s_1 + a_{22}s_2 \quad \cdots \quad (2)

The coefficients a_{11}, a_{12}, a_{21}, a_{22} are basically some parameters that depend on the distance of the respective source from the microphones.

Let’s define our problem as : Using only the mixtures x_i estimate the signal sources s_i. It is notable that you do not have any knowledge of the parameters a_{ij}.

This could be illustrated by this :

Consider three signals:

Suppose we have five mixtures obtained from these three signals.

Signals obtained by mixing source signals

If you only have the mixed signals available. And do not know how they were mixed (parameters a_{ij} not known). And from these mixed signals (x_{i}) you have to estimate the source signals (s_{i}). This problem is of considerable difficulty.

One approach would be : Use the statistical properties of the signals (s_i) to estimate the parameters (a_{ij}). It is surprising that it is enough to assume that s_1 and s_2 are statistically independent. This assumption might not be valid in many scenarios. But works well in most situations.

We could write the above system of linear equations in matrix form as :

x=As

where, A represents the mixing matrix, x and s represent the mixtures and the sources respectively.

The problem is to estimate s from x without knowing A. The assumption made is that the sources s are statistically independent.

How we go about solving this problem is exciting and an area of active research.  ICA was originally developed for solving such problems. Please follow [12][13][14] for discussions on mutual information, measures of non-gaussianity such as Kurtosis and Negentropy and the fastICA algorithm.

__________

Why can ICA be used in MRI?

One limitation that ICA faces is that it can not work if more than one signal sources have a  Gaussian distribution. This can be illustrated as follows:

Again consider our equation for just two sources :

\displaystyle \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix} \begin{bmatrix} s_1 \\ s_2 \end{bmatrix}

Our problem was : We have to estimate s from x without any knowledge of A. We would first need to estimate the parameters A from x, assuming statistical independence of s. And then we could find s as :

s = Wx, where W=A^{-1} , or the inverse of the estimated mixing matrix A.

To understand how a solution would become impossible if both the sources had a Gaussian distribution, consider this :

Consider two independent components having the following uniform distributions:

P(s_i) = \begin{cases} \frac{1}{2 \sqrt{3}} & \text{if} \quad |s_i| \leq \sqrt{3} \\ 0 & \text{otherwise} \end{cases}

The joint density of the two sources would then be uniform on a square. This follows from the fact that the joint density would be the product of the two marginal densities.

 

The joint distribution for Si

[ Image Source : Reference [12][13] ]

Now if s_1 and s_2 were mixed by a mixing matrix A

A = \begin{bmatrix} 2 & 3 \\ 2 & 1 \end{bmatrix}

The mixtures obtained are x_1 and x_2. Now since the original sources had a joint distribution on a square, and they were transformed by using a mixing matrix, the joint distribution of the mixtures x_1 and x_2 will be a parallelogram. These mixtures are no longer independent.

 

Joint Distribution of the mixtures

[ Image Source : Reference [12][13] ]

Now consider the problem once again : We have to estimate the mixing matrix A from the mixtures x_i, and using this estimated A we have to estimate the sources s_i.

From the above joint distribution we have a way to estimate A. The edges of the parallelogram are in a direction given by the columns of A. This is an intuitive way of estimating the mixing matrix : obtain the joint distributions of the mixtures, estimate the columns of the mixing matrix by finding the directions of the edges of the parallelogram. This solution gives a good intuitive feel of a in-principle solution of the problem( however, it isn’t practical).

However, now instead of two independent sources having a uniform distribution consider two independent sources having a Gaussian distribution. The joint distribution would be :

 

Joint Distribution when both Independent sources are Gaussian

[ Image Source : Reference [12][13] ]

Now going by the above discussion, because of the nature of the above joint distribution, it is not possible to estimate the mixing matrix from it.

Thus ICA fails when one or more independent components have a a gaussian distribution.

Noise in MRI is non-gaussian[16], therefore ICA is suited for MRI.

__________

Problems in Using ICA for MRI Blind Source Separation:

The application of ICA for MRI faces a number of problems. I would discuss these in later blog posts. I would only discuss one major problem – the problem of Over-Complete ICA.

Over-Complete ICA in MRI:

The problem of over complete ICA occurs when there are lesser sensors (tape recorders from our above discussion) than sources. This problem can be understood by the following discussion. Suppose you have 3 mixtures x_1, x_2 and x_3 (imagine you have collected 3 tape recordings in a cocktail party of 6). Therefore you now have to estimate 6 sources from 3 mixtures.

Now the problem becomes something like this :

x_1 = a_{11}s_1 + a_{12}s_2 + a_{13}s_3 + a_{14}s_4 + a_{15}s_5 + a_{16}s_6

x_2 = a_{21}s_1 + a_{22}s_2 + a_{23}s_3 + a_{24}s_4 + a_{25}s_5 + a_{26}s_6

x_3 = a_{31}s_1 + a_{32}s_2 + a_{33}s_3 + a_{34}s_4 + a_{35}s_5 + a_{36}s_6

Assume for a second we can still estimate a_{ij}, still we can not find all the signal sources. As the number of linear equations is just three, while the number of unknowns is 6. This is a considerably harder problem and has been discussed by many groups such as [19][20][21].

Now dropping our assumption, the estimation of a_{ij} is also harder in such a case.

The Case in MRI:

The problem of over-complete ICA doesn’t arise when it comes to functional-MRI. However it is a problem when it comes to MRI[17].

In MRI, by varying the parameters used for imaging, the three kind of images that can be obtained are T1 weighted, T2 weighted and Proton Density images. Going by our discussion in the section on MRI above. These three can be treated as mixtures.

Therefore, we have 3 mixtures at our disposal.  However, as the ground truth images above show: The number of different tissues in the brain exceeds 9. Thus this becomes a considerably difficult problem : We have to estimate 9-10 independent components from just 3 mixtures.

I would discuss methods that can help do that in later blog posts.

If only three mixtures are used, 3 ICs can be estimated. Since the actual number of ICs exceeds 9. It is obvious that the each of 3 ICs have atleast 2 ICs mixed, which means that a certain tissue type is not enhanced as much as it could have been had there been one IC for it. This can be understood by looking at this example.

 

3 ICs obtained by Applying Fast-ICA on MR scans

[I used FastICA for obtaining these Independent Components ]

To get more ICs, in simple words, we need more mixtures. However we can obtain more mixtures from the existing mixtures itself by a process of Band-Expansion[18].

I would discuss this problem of OC-ICA and it’s possible solutions in later posts.

__________

To Conclude:

A basic idea related to application of ICA to MR scans was discussed. It is clear that even with just three ICs significant tissue contrast enhancement is achieved. Problems related to OC-ICA would be discussed in later posts one by one. I would also discuss quantifying the results obtained using the Tanimoto/Jaccard coefficient of similarity.

__________

References and Resources:

Cocktail Party Problem

[1] “Some Experiments on the Recognition of Speech, with One and with Two Ears“; E. Colin Cherry; The Journal of the Acoustical Society of America; September 1953. (PDF)

[2] “The Attentive Brain“; Stephen Grossberg; Department of Cognitive and Neural Systemss – Boston University; American Scientist, 1995. (PDF)

[3] “The Cocktail Party Problem : A Primer“; Josh H. McDermott; Current Biology Vol 19. No. 22. (PDF)

Magnetic Resonance Imaging

[4] “Magnetic Resonance ImagingTutorial“; H Panepucci and A Tannus; Technical Report; USP, 1994. (PDF)

[5] “10 Video lessons on MRI by Paul Callaghan” (~ an hour in total). (Videos)

[6] “MRI Tutorial for Neuroscience Boot Camp” Melissa Saenz. (PDF)

Sample ICA Applications Similar to The Cocktail Party Problem

[7] “Independent Component Analysis of Electroencephalographic Data“; Makieng, Bell, Jung, Sejnowski; Advances in Neural Information Processing Systems, 1996. (PDF)

[8] “Application of ICA to MEG noise Reduction“; Masaki Kawakatsu; 4th International Symposium on Independent Component Analysis and Blind Source Separation; 2003. (PDF)

[9] “Independent Component Analysis in Financial Data” from the book Computational Finance; Yasser S. Abu-Mostafa; The MIT Press; 2000. (Book Link)

[10] “ICA of functional MRI data : An overview“; Calhoun, Adali, Hansen, Larsen, Pekar; 4th International Symposium on Independent Component Analysis and Blind Source Separation; 2003. (PDF)

[11] “Independent Component Analysis of fMRI Data – Examining the Assumptions“; McKeown, Sejnowski; Human Brain Mapping; 1998. (PDF)

Independent Component Analysis : Tutorials/Books

[12] “Independent Component Analysis : Algorithms and Applications“; Aapo Hyvärinen, Erkki Oja; Neural Networks; 2000. (PDF)

[13] “Independent Component Analysis“; Aapo Hyvärinen, Juha Karhunen, Erkki Oja; John Wiley Publications; 2001. (Book Link)

[14] ICA Tutorial at videolectures.net by Aapo Hyvärinen. (Videos)

Independent Component Analysis for Magnetic Resonance Imaging

[15] “Application of of Independent Component Analysis to Magnetic Resonance Imaging for enhancing the Contrast of Gray and White Matter“; Nakai, Muraki, Bagarinao, Miki, Takehara, Matsuo, Kato, Sakahara, Isoda; NeuroImage; 2004. (Journal Link)

[16] “Noise in MRI“; Albert Macovski; Magnetic Resonance in Medicine; 1996. (PDF)

[17] “Independent Component Analysis in Magnetic Resonance Image Analysis“;  Ouyang, Chen, Chai, Clayton Chen, Poon, Yang, Lee; EURASIP journal on Advances in Signal Processing; 2008 (Journal Link)

[18] “Band Expansion Based Over-Complete Independent Component Analysis for Multispectral Processing of Magnetic Resonance Images “; Ouyang, Chen, Chai, Clayton Chen, Poon, Yang, Lee; IEEE Transactions on Biomedical Imaging; June 2008. (PDF)

Over-Complete ICA:

[19] “Blind Source Separation of More Sources Than Mixtures Using Over Complete Representations“; Lee, Lewicki, Girolami, Sejnowski; IEEE Signal Processing Letters; 1999. (PDF)

[20] “Learning Overcomplete Representations“; Lewicki, Sejnowski. (PDF)

[21] “A Fast Algorithm for estimating over-complete ICA bases for Image Windows “; Hyvarinen, Cristescu, Oja; International Joint Conference on Neural Networks; 1999. (IEEE Xplore link)

__________

Onionesque Reality Home >>

Read Full Post »