Archive for the ‘Science’ Category

Two Draft Books

September 13, 2007

If you’re interested in learning about statistical mechanics, graphical models, information theory, error-correcting codes, belief propagation, constraint satisfaction problems, or the connections between all those subjects, you should know about a couple of books that should be out soon, but for which you can already download extensive draft versions.

The first is Information, Physics, and Computation by Marc Mézard and Andrea Montanari.

The second is Modern Coding Theory by Tom Richardson and Ruediger Urbanke.

I also recommend the tutorial on Modern Coding Theory: the Statistical Mechanics and Computer Science Points of View, by Montanari and Urbanke, from the lectures they gave at the 2006 Les Houches summer school.

The Hubbard Model: a Tutorial

September 9, 2007

Today, I will introduce a new kind of post at Nerd Wisdom, that I hope to do more of in the future: the tutorial. These posts will be a little more technical than ordinary posts, and will probably run a little longer as well. They are designed to give the intelligent and well-educated scientist an entry into a field for which he or she is not already a specialist.

When working with graduate-student interns, I find myself presenting these types of tutorials constantly. Unfortunately, this type of material is very hard to find in the literature, because it covers material that is too well-known to the specialist, while sometimes being beyond what is available in textbooks. Thus, there tends to be an artificial barrier to entry into new fields.

My first tutorial will cover the Hubbard Model. To keep this post to a reasonable length, I will just include the first part of the tutorial here.

 

I previously discussed high-temperature superconductivity in cuprates, and mentioned that the detailed mechanism is still controversial. However, what is widely agreed is that, as originally proposed by P.W. Anderson, a good model for these materials is the Hubbard Model (see this paper by Anderson for an entertaining and readable argument in favor of this point). And even if one doesn’t agree with that statement, the Hubbard Model is of enormous intrinsic interest, as perhaps the simplest model of interacting electrons on a lattice.

Despite its simplicity, physicists have not been able to solve for the behavior of the two or three-dimensional Hubbard model in the “thermodynamic limit” (for lattices with a very large number of sites and electrons). Coming up with a reliable approach to solving the Hubbard model has become a kind of holy grail of condensed matter theory.

Note that this is very different from the situation for the classical ferromagnetic Ising model, for which Onsager solved the two-dimensional version exactly in 1944 but where we do not have an exact solution in three dimensions. For the three-dimensional Ising model, we may not have an exact solution, but we understand extremely well the qualitative behavior, and can compute quantitative results to practically arbitrary accuracy. For the Hubbard model, we do not even have know what the qualitative behavior is for two or three dimensional lattices.

I will first describe the model in words, and then show you how to solve for the quantum statistical mechanics of the simplest non-trivial version of the model: the Hubbard model on a lattice with just two sites. I strongly believe that whenever you want to learn about a new algorithm or theory, you should start by solving, and understanding in detail, the smallest non-trivial version that you can construct.

The Full Tutorial

High-Temperature Superconductivity

September 7, 2007

In 1986, a new class of materials, called “cuprate superconductors,” was discovered by Karl Muller and Johannes Bednorz, which displayed superconductivity (the flow of electricity at zero resistance) at much higher temperatures than had ever previously been found. The discovery raised the possibility of materials that could super-conduct at ordinary room temperatures, which would clearly have great technological implications. Muller and Bednorz were awarded the Nobel Prize in Physics in 1987, which stands as the shortest period ever between a discovery and a Nobel prize.

I was a graduate student at Princeton when the news of high-temperature superconductivity broke, and my Ph.D. advisor was Philip W. Anderson, the 1977 Nobel Laureate in physics who at the time was already probably the most famous and respected condensed matter theorist in the world. (One recent study claimed to show that Anderson is the “most creative physicist in the world;” I found the method of the study highly dubious, but the conclusion is not unreasonable.) Anderson nearly immediately proposed a version of his “Resonating-Valence-Bond” theory for the superconductors, and trying to develop a complete theory has been his primary preoccupation ever since.

woodstock01_thumb.jpg

To give you an idea of the excitement in 1987, take a look at this article, looking back at the March 1987 meeting of the American Physical Society in New York City, characterized as the “Woodstock of Physics.”

I was at that meeting, and as one of Anderson’s students, I was definitely at the epicenter of the excitement, but I was actually rather turned off by the whole atmosphere, and I avoided working on the subject too seriously, focusing instead on neural networks and spin glass theory. (As I mentioned in this post, Anderson also made seminal contributions to those fields, and he let me work on whatever I was interested in.) Nevertheless, it was impossible to avoid being influenced, and I did eventually work on a few papers related to the theory of high-temperature superconductivity.

Sadly, the hopes for room temperature cuprate super-conductivity faded with time, and no cuprates have been discovered which super-conduct above 138 degrees Kelvin. And although our understanding of the materials has improved with time, there is still also considerable controversy about the mechanism causing the superconductivity.

See this post for more information about the Hubbard Model, which underlies the physics of the cuprates.

Using Illusions to Understand Vision

September 6, 2007


checkershrunk001.jpg

MIT professor Edward Adelson uses remarkable visual illusions to help explain the workings of the human visual system. One such illusion is shown above. Believe it or not, the square marked A is the same shade of gray on your computer screen as the square marked B.

checkerproofshrunk002.jpg

Here’s a “proof,” provided by Adelson. Two strips of constant grayness are aligned on top of the picture. You can see that the A square is the same shade as the strips near it and the B square is the same shade as the strips near it. Perhaps you still don’t believe that the strips are of constant grayness. In that case, put some paper up next to your computer screen to block off everything except for the strips; you’ll see it’s true.

Adelson explains the illusion here. The point is that our visual system is not meant to be used as a light meter; instead it is trying to solve the much more important problem (for our survival) of determining the true shade (that is, the color of the attached “paint”) of the objects it is looking at.

You can find more interesting illusions and demos from Adelson and other members of the perceptual science group at MIT, but don’t fail to also take a look at the illusions collected by the lab of Dale Purves at Duke. I particularly recommend the cube color contrast demo, where you can see that gray can be made to look yellow or blue.

Purves, together with R. Beau Lotto, wrote the book “Why We See What We Do: An Empirical Theory of Vision,” which collects these remarkable illusions and also expounds on a theory explaining them. The theory, to summarize it very briefly, says that what humans actually see is a “reflexive manifestation of the past rather than a logical analysis of the present.” I found myself quite uncomfortable with the theory for much the same reasons as given in Alan Gilchrist‘s review.

I also would prefer a more mathematical theory than Purves and Lotto give. It seems to me that we should in general try to explain illusions in terms of a Bayesian analysis of the most probable scene given the evidence provided by the light. My collaborators Bill Freeman and Yair Weiss (both former students of Adelson’s) have long worked along these lines; see for example Yair’s excellent Ph.D. thesis from 1998, explaining motion illusions.

In fact, I would like to go beyond a mathematical explanation of illusions to an algorithmic one. I would argue that a good computer vision system should “suffer” from the same illusions as a human, even though it has neither the same evolutionary history nor the same life history. To take an example of what I have in mind, the famous Necker cube illusion presumably arises naturally from the fact that the two interpretations are both local optima, with respect to probability, so a good artificial system should use an algorithm that settles into one interpretation, but then still be able to spontaneously switch to the other.

Consistent Quantum Theory

September 4, 2007

Quantum mechanics is a notoriously confusing and difficult subject, which is terribly unfortunate given its status as a fundamental theory of how the world works. When I was an undergraduate and graduate student of physics in the 1980’s, I was always unsatisfied with the way the subject was presented. We basically learned how to calculate solutions to certain problems, and there was an understanding that you were better off just avoiding the philosophical issues or the paradoxes surrounding the subject. After all, everybody knew that all the challenges raised by physicists as eminent as Einstein had ultimately been resolved experimentally in favor of the “Copenhagen interpretation.”

Still, there was a lot of weird stuff in the Copenhagen interpretation like the “collapse of the wave-function” caused by a measurement, or apparently non-local effects. What I wished existed was a clearly-defined and sensible set of “rules of the game” for using quantum mechanics. The need for such a set of rules has only increased with time with the advent of the field of quantum computing.

cover.gif

In his book, “Consistent Quantum Theory,” (the first 12 out of 27 chapters are available online) noted mathematical physicist Robert Griffiths provides the textbook I wished I had as a student. With contributions from Murray Gell-Mann, Roland Omnes, and James Hartle, Griffiths originated the “consistent history” approach to quantum mechanics which is explained in this book, .

The best summary of the approach can be obtained from the comparison Griffiths makes between quantum mechanics and the previous classical mechanics. Quantum mechanics differs from classical mechanics in the following ways:

1. Physical objects never posses a completely precise position or momentum.
2. The fundamental dynamical laws of physics are stochastic and not deterministic, so from the present state of the world one cannot infer a unique future (or past) course of events.
3. The principle of unicity does not hold: there is not a unique exhaustive description of a physical system or a physical process. Instead reality is such that it can be described in various alternative, incompatible ways, using descriptions which cannot be combined or compared.

It is the 3rd point which is the heart of the approach. In quantum mechanics, you are permitted to describe systems using one “consistent framework” or another, but you may not mix incompatible frameworks (basically frameworks using operators that don’t commute) together.

Griffiths uses toy models to illustrate the approach throughout the book, and provides resolutions for a large number of quantum paradoxes. He stresses that measurement plays no fundamental role in quantum mechanics, that wave function collapse is not a physical process, that quantum mechanics is a strictly local theory, and that reality exists independent of any observers. All of these points might seem philosphically natural and unremarkable, except for the fact that they contradict the standard Copenhagen interpretation.

This is a book that will take some commitment from the reader to understand, but it is the best explanation of quantum mechanics that I know of.

Duke and Pawn Endgames

September 3, 2007

Note: to understand this post, you don’t need to know anything about chess; I’ll explain everything necessary right here.

One of the best ways for a chess beginner to improve is to study king and pawn endgames, and one of the best ways to do that is to play a game with only kings and pawns. Just remove all the rest of the pieces, and have at it.

Unfortunately, while Chess with just kings and pawns is not trivial, as you improve you will eventually outgrow it, because between two good chess players, the game is very likely to end in a draw.

As I mentioned in an earlier post, my son Adam likes to design games, and he designed this very clever variant of the King and Pawn endgame that eliminates the possibility of a draw.

duke001.jpg

Rules:

Set up the pieces as above, with four pawns plus a King for both White and Black.

The players alternate moves, starting with White.

The pawns move as in chess: one square forward, or optionally two squares forward if they haven’t moved yet, and they capture a piece one square ahead of them diagonally.

Pawns may still capture en passant as in Chess, which means the following. If an enemy pawn moves two squares forward, and one of your pawns could have captured it if it had only moved one square forward, you may capture that pawn as if it had only moved one square forward, but only if you do so with your pawn on the turn immediately after the enemy pawn moves.

The Kings can only move one square up or down, or left or right; they cannot move diagonally. (Such limited versions of Kings are sometimes called “Dukes;” hence the title of this post.)

You win the game immediately if you capture the opponent’s King, or if one of your pawns reaches the other side of the board.

You must always move; if you cannot make a legal move, you lose the game. (This is different from Chess, where stalemate is a draw.)

You may not make a move which recreates a position that has previously occurred during the game. (This is also different from Chess, but such a rule exists in Shogi, the Japanese version of Chess.)

That’s all the rules. In this game, draws are impossible, even if only two Kings remain on the board. For example, imagine that the White King is on a1, and the Black King is on b2. If White is to move, he loses, because he must move to a2 or b1, when Black can capture his King. But if Black is to move, he must retreat to the north-east, when White will follow him, until Black eventually reaches h8 and has no more retreat.

So arranging that your opponent is to move if the two Kings are placed on squares of the same color (if there are no pawn moves) is the key to victory. This concept, known as the “opposition,” is also very important in ordinary Chess King and pawn endgames, which is why skill at chess will translate into skill in this variant, and why improving your play at this variant will improve your Chess. Of course, the pawns are there, and they complicate things enormously!

Naturally, one can consider other starting positions, with different numbers of pawns.

This game can be analyzed using the methods of Combinatorial Game Theory (CGT). Noam Elkies, the Harvard mathematician, has written a superb article on the application of CGT to ordinary chess endgames, but it required great cleverness for him to find positions for which CGT could be applied; with this variant, the application of CGT should be much easier.

The Life of the Lab Biologist

September 1, 2007

As I mentioned in a previous post, I was lucky to be able to attend, as a student, the 2006 Molecular Biology of Aging summer course at the Woods Hole Marine Biology Laboratory. This three week course was intensive; part the time was spent in lectures, where many of the world’s leading experts on aging explained their research in detail (and the students were able to ask lots of questions), and the rest was spent in the lab. There was also often time to attend some of the many other stimulating talks in molecular biology or neuroscience being held elsewhere at Woods Hole. Because the subject was so far from my normal research, I took vacation time to attend; I suppose it doesn’t seem like much of a vacation, but in fact Woods Hole is incredibly stimulating, and it was one of the most memorable and refreshing vacations I’ve ever had.

We performed real experiments in the lab, as the other students were all biology post-docs and grad students who were there to learn cutting edge techniques. I was also assigned to a group, led by Dr. Meng Wang, a post-doc in Gary Ruvkun’s lab, and we learned how to perform RNA interference (RNAi) screens on the nematode worm C. Elegans.

The RNAi technique lets you suppress the transcription of any single gene in the worm’s genome. An “RNAi screen” means that you divide the population of worms that into groups organized so that each group has a different gene suppressed, and you make sure that you have a group for each gene in the genome. For each group of worms, you check whether it has some phenotype that you’re interested in (in our case it was the ability to breed at a later age than usual). That way, you can quickly find genes that are involved in the phenotype.

216878320_502fcdb4c2.jpg

The picture above is from the lab at Woods Hole. From left to right are Michael Morissette, Andrew Midzak, Serkalem Tadesse, myself, and John Cumbers. The others have finished their work, but I was slower than everybody else, so I’m guessing that I was still counting worms or something.

Biologists work incredibly long hours at the lab, often doing work that is exciting in terms of its implications, but sometimes pretty dull and repetitive in the doing; biologists are dedicated people! On the other hand, lab life seems much more social compared to the life of a computer scientist or physicist. (Although there is much more social interaction in those fields than in fields like history, as I know by observing my historian wife. I always find it ironic that humanists, who tend to be outgoing people, usually find themselves working in a much more solitary way than scientists.)

One thing I learned was that lab biology is largely a matter of learning and using “protocols,” which are basically like scientific recipes. Take a look at this amusing video, which features the highly talented John Cumbers (who was one of my lab-mates) and produced by the Brown iGEM team:

Another protocol was for “picking” worms (moving them from one petri dish to another). An adult C. Elegans is only about 1 millimeter long, so picking them up is not easy. You do it under a microscope with a special thin wire (a “picker”). You sort of try to scoop them up, but the worms run away! It’s like a video game, except not nearly as fun, really. Here’s a video showing the technique in action.

You should notice by the way that the picked worm is glowing. That’s because the worm is a mutant: a gene for a fluorescent protein has been spliced into its genome attached to another gene (daf-12) of interest. That way you can know where daf-12 is expressed in its body. (This video was submitted by user a99xel to YouTube).

Richard Feynman

August 31, 2007

Richard Feynman has been one of my heroes, ever since the end of my freshman year at Harvard. After my last final exam, but before I headed home for the summer, I was able to sit in the beautiful Lowell House library, without any obligations, and just read chapters from his wonderful Lectures on Physics. After that there wasn’t much doubt in my mind about what I wanted to do with my life.

There’s a lot to say about Feynman, but I will restrict myself for now to a couple rather recent items which give a picture of the character of this remarkable man. First, there is this 1981 BBC Interview, recently released to the web, where you can see him briefly discuss a few of the things that were important to him.

images3.jpg

Secondly, if you haven’t read Perfectly Reasonable Deviations From the Beaten Track, the collection of his letters edited by his daughter Michelle Feynman that was published in 2005, you owe it to yourself to do so. I was skeptical at first that a book of letters, even those of Feynman, could be very interesting, but I wound up reading every word.

Let me just give you one example of a pair of letters from 1964:

Dear Professor Feynman,

Dr Marvin Chester is presently under consideration for promotion to the Associate Professorship in our department. I would be very grateful for a letter from you evaluating his stature as a physicist. May I thank you in advance for your cooperation in this matter.

Sincerely,
D.S Saxon
Chairman
Dick: Sorry to bother you, but we really need this sort of thing.
David S.

Dr. D.S. Saxon, Chairman
Department of Physics
University of California, Los Angeles
Los Angeles, California

Dear David:

This is in answer to your request for a letter evaluating Dr. Marvin Chester’s research contributions and his stature as a physicist.

What’s the matter with you fellows, he has been right there the past few years–can’t you “evaluate” him best yourself? I can’t do much better than the first time you asked me, a few years ago when he was working here, because I haven’t followed his research in detail. At that time, I was very much impressed with his originality, his ablity to carry a theoretical argument to its practical, experimental conclusions, and to design and perform the key experiments. Rarely have I met that combination in such good balance in a student. Was I wrong? How has he been making out?

Sincerely yours,
R.P. Feynman

The above letter stands out in the files of recommendations. After this time, any request for a recommendation by the facility where the scientist was working was refused.

Edit: In the comments below, Shimon Schocken recommends Feynman’s “QED.” I thought of this book after finishing this post. It’s an amazing work. In it, Feynman gives a popular account (you don’t need any physics background to follow it) of his theory of quantum electrodynamics, for which he won the Nobel Prize. But it’s a popular account that makes no compromises in its scientific accuracy. The other books recommended in the comments (“Six Easy Pieces” and “Surely You’re Joking”) are also definitely great books, but “QED” is somehow often overlooked, even though it is the book that Feynman himself recommended to those interested in his work.

Prediction Markets

August 30, 2007

What does it mean to say that “I believe that Hillary Clinton has a 42% chance to win the 2008 U.S. Presidential election?” It used to be that some academics (called “frequentists”) had problems with this statement, because they only wanted to talk about probabilities for experiments that, at least in principle, could be run many times, to permit a reasonable estimate of the frequency of some event. I think hardly anybody is a frequentist anymore.

One good operational definition of the above statement is that if you offer me a choice between $1.00 if Hillary Clinton wins, or $0.42 regardless of whether or not she wins, I am indifferent. If you offer me less than the $0.42, I’ll take the chance on Senator Clinton, if you offer me more, I’ll go with the sure thing.

Nowadays, we can get good estimates of the probabilities of many interesting events from prediction markets like TradeSports for sporting events, or Intrade for political and other events. In these markets, participants buy and sell contracts of the above variety, so that the market provides a consensus probability for a particular event.

closingchart.jpg

I find these markets fascinating. You can find out for example, looking at the chart above, that Senator Obama’s apparent chance of winning the Democratic nomination has fallen from around 39% to around 17% over the last few weeks (presumably because of the fallout over his statements on foreign policy). Or that the New England Patriots off-season acquisitions have increased their chances of winning the next Super Bowl from about 7% to 17%.

There’s some bias towards American sports and politics, but events like the recent French Presidential election are also heavily traded.

I’ve just been an observer, and I intend to stay that way, but if you’re interested, but don’t want to use real money, Intrade recently began letting you play with pretend dollars.