Archive for the ‘Books’ Category

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.

Combinatorial Game Theory

August 29, 2007

Combinatorial Game Theory (CGT) is a mathematical discipline that studies two-player, zero-sum games, where the players play sequentially, and there is perfect information and no chance. The aim of CGT is to build mathematical theories that will help players win such games! In practice, the ideas from CGT are of minimal help to the serious player in more complicated games like Chess or Go, but the theories are extremely helpful for simpler but still non-trivial games like Dots-and-Boxes.

9781568811307.jpg

The CGT bible is Winning Ways for Your Mathematical Plays, a four-volume set of books (for the 2nd edition from the early 2000’s; the first edition from 1982 was in two volumes), by the eminent mathematicians Elwyn Berlekamp, John Horton Conway, and Richard Guy.

The basic idea of CGT is to develop a calculus, which lets you assign a value to a position in the game. One normally considers games with the condition that a player who cannot move loses. If both players are without a move in a position (whoever moves loses), the position is assigned a value of 0. If the player on the right can make one move that transforms the position to one of value 0, and the player on the left cannot move at all, the position is assigned a value of 1 (if the roles are reversed, the position has value -1).

Now what happens if the player on the left has a move to a position of value 0, and the player on the right has a move to a position of value 1? What is the value of that position? It turns out to be worth 1/2, as can be seen by considering the position obtained by adding such two such positions together with a position of value -1, when one gets back to a position of value 0 where whoever moves loses (I’ll let you work out the details).

There are more different kinds of values than just fractions. Berlekamp, Conway, and Guy consider a multitude of different interesting games, which give rise to ever deeper mathematics, and game positions with strange values along with complex rules for combining those values.

The writing is informal, with constant punning, but the mathematics is serious. Still, one charm of the field is that there is no pre-requisite mathematical material needed to understand these books–bright high school students can launch right in.

After finishing “Winning Ways,” the ambitious student can move on to the two volumes “Games of No Chance” and “More Games of No Chance” (note that nearly all the papers in these books are available online), and then move onto the rest of the papers collected at David Eppstein‘s CGT page.

Also, take a look at Aaron Siegel‘s Combinatorial Game Suite software to help you do CGT computations.

There’s still much more to say, but I’ll leave that for other posts.

Mitochondria

August 22, 2007

As I mentioned in my previous post about Lenny Guerente’s book “Ageless Quest,” aging research has, within the last 15 years, gone from being a scientific backwater to a mainstream field of scientific research, with new discoveries now regularly featured on the cover of Nature or Science (as in the Nature issue from June 2007 below.)

cover_nature.jpg

Although we now are capable of manipulating the aging process, including significantly extending the lifespan of many laboratory animals, it is still a frustrating fact that there is no consensus about the ultimate cause or causes of aging.

One viewpoint, which is probably only held by a significant minority of scientists in the field, is that the aging process is strongly connected to mitochondria, which are the power plants or batteries of our cell, converting nutrients into useful packets of energy in the form of ATP. We’re used to the idea that electronic equipment fails when the batteries go dead, so it’s not such a stretch to take a close look at the mitochondria.

What’s more, mitochondria produce much of the “pollution” in the cell in the form of the free radicals that are a by-product of the oxidative phosphorylation process (the process that turns nutrients into energy). Those free-radicals can damage proteins or DNA, particularly the mitochondrial DNA (this is special DNA, inherited from the mother, that resides in the mitochondria rather than the nucleus) that codes for a few essential mitochondrial proteins.

So one theory says that there is a kind of vicious circle, whereby old mitochondria start emitting more free radicals, which further damages the mitochondria, until the mitochondria are so damaged that they don’t produce sufficient energy and start damaging the rest of the cell. Right now, the consensus view on whether the experimental facts really fit that theory is “Maybe.”

images2.jpg

If you want to learn more about mitochondria, I highly recommend “Power, Sex, Suicide: Mitochondria and the Meaning of Life (you’ve just got to love that title), by Nick Lane. Lane’s book is popular science, but it’s a very deep book, and actually proposes theories, including theories of aging, that you won’t see elsewhere in the literature. It’s not an easy book to read, but it’s very worthwhile.

Alternatively, you might enjoy this video of Douglas Wallace lecturing on the role of mitochondria in diseases and aging. Wallace, a professor from UC Irvine, delivers highly entertaining and persuasive lectures.

“On Intelligence” and Numenta

August 21, 2007


book.png

“On Intelligence,” written by Jeff Hawkins with Sandra Blakeslee, is a great read, full of provocative ideas about how our brains work.

Hawkins founded Palm Computing and Handspring, but he says that his true lifelong passion has been trying to understand our brains. In 2002, he founded the Redwood Neuroscience Institute (now the Redwood Center for Theoretical Neuroscience at Berkeley).

At Redwood, he developed a theory of the brain, that he expounds in this book. The book is a popular science book; you will not find any equations or explicit algorithms. It reads very smoothly, undoubtably due to the fact that Hawkins was helped in writing the book by Sandra Blakeslee, a science writer for the New York Times.

Hawkins argues that the cortex consists of modules that are all performing the same algorithm. The purpose of that algorithm is to learn to complete and predict the spatio-temporal patterns coming into a module from “lower” modules in the brain’s hierarchy, using feedback from “higher” modules.

I find this hypothesis for how the brain works extremely attractive, and “On Intelligence” argues for the hypothesis almost too well, in that the difficulties of converting the hypothesis into a concrete and useful algorithm will slip by the reader, as if by sleight of hand. The problem, of course, is that it is easy to use words to talk about how a brain might work; the hard part is making a machine do the same thing.

Peter Dayan, a leading computational neuroscientist, has written a much more detailed review. And for a 2006 lecture by Hawkins about his theory, you can watch this video.

After reading the book, I actually spent a few weeks trying to make the hypothesis into a concrete algorithm, without much success. But Hawkins is certainly putting his money where his mouth is: he has founded a company, called Numenta, and Numenta has released software (the “Numenta Platform for Intelligent Computing” or “NuPIC”) that implements part of his theory. NuPIC appears to be based on software originally written by Numenta co-founder and Stanford graduate student Dileep George, but transformed by a team of software developers into a professional-quality product.

However, it is very disappointing that the NUPIC software does not include feedback in its hierarchies, nor does it let you learn and infer temporal patterns (only spatial ones). To be honest, I am not so surprised, because it was these elements (that are obviously central in Hawkins’ theory) that I found it so difficult to integrate into a real algorithm.

Numenta promises that future versions of NuPIC will fill these gaps. I sincerely wish them the best of luck! I should say that I think it is wonderful that an impatient guy like Hawkins pushes the field, using a different approach than the standard academic one.

So in summary, you should definitely read Hawkins’ book, and if you’re intrigued, you should by all means check out the free Numenta software. Whether this line of research will lead to anything significant though, I’m not really sure…

Structure and Interpretation of Computer Programs: Videos and Textbook

August 17, 2007


gjspicture.jpg

This set of videos, of Gerald Jay Sussman and Hal Abelson teaching their course on the “Structure and Interpretation of Computer Programs” in July 1986 for Hewlett-Packard employees, is one of the treasures of the internet. The clothes are out of style, but the material presented is still completely relevant.

The SICP web-site has lots of useful additional information, including the complete text of the 2nd edition of their classic textbook.

I am not going to try to write a better review of the Abelon’s and Sussman’s textbook than the Amazon review written by Peter Norvig. Norvig is the head of Research at Google, and a co-author of Artificial Intelligence: a Modern Approach, the leading AI textbook.

But I will add one comment: what I love most about these lectures is the point (see the picture above of Sussman in his wizard hat) that a computer programmer is like a wizard–he creates something real out of ideas. Computers let us be wizards; and I believe we have only scratched the surface of the possible “spells” that we can learn to cast.

If you want a nice implementation of Scheme, the beautiful dialect of Lisp that was invented by Sussman with his student Guy Steele, and used in this textbook, I highly recommend DrScheme.

A Simple but Challenging Game: Part II

August 15, 2007

Here’s Part I again:

My 15-year-old son Adam likes game theory. He invented the following simple game, and asked me about it when I got on the phone with him while I was away at a conference last month (I’ve simplified and formalized the set-up slightly):

There are two players, each of whom is given a real number which is chosen randomly from a uniform distribution between 0.0 and 1.0. The players know their own number but not their opponent’s. One player moves first and has the choice of passing or challenging. If he challenges, both players reveal their number, and the player with the higher number receives a payoff of 1, while the other player receives a payoff of 0. If the first player passes, the second player has a choice of challenging or passing. If he challenges, again both players reveal their numbers and the player with the higher number receives a payoff of 1, while the other player receives a payoff of 0. If the second player also passes, both players receive a payoff of 1/2. They play the game one time, and are interested in maximizing their expected payoff.

What is the right strategy? For example, if you received the number 0.17, would you pass or challenge if you were the first player? What about if you were the second player? What would you do if the number you received was 0.0017?

I’ll tell you more in a later post, but for now why don’t you think about it….

Here’s the promised followup:

It is clear that if any player has the advantage, it’s the second player, because he gets some information from the first player, and can use it to make his decision. Nevertheless, the first player can adopt the strategy of always challenging, and thereby guarantee that he wins half the time. So apparently he should always challenge. This is the answer that was given by “Optionalstopping” in the comments. The same answer was given to me by the evolutionary game theorist Arne Traulsen (who has recently worked on a ground-breaking theory for the emergence of punishment), after I asked him about the game at a lunch conversation.

There is another way to arrive at the same answer. Assume that each player chooses a strategy parameterized by a single value; if he receives a number above that value, he challenges, while if he receives a number below that value he passes. If you work out the Nash equilibrium (basically, that means that both you and your opponent pick the strategy that gives you the best payoff assuming that the opponent is maximizing their payoff), you’ll find (I won’t bore you with the math) that the value for both players is zero–they should always challenge. My son Adam gave an intuitive version of this argument, without the math. Of course it’s true that probabilistic strategies are also possible. I haven’t proven it, but I strongly doubt that introducing probabilistic strategies will change the result that the Nash equilibrium is to always challenge for both players.

So at first I thought the matter was settled. But still, there is something very weird about this result. Would you really challenge if you were the first player and you received a .001? Would you really?

And what if you were the second player, and the first player passed, and you had a .000001? You know that the first player is not “following the rules” of Nash equilibrium. Are you really going to challenge because Nash tells you to? It’s obviously a crazy result! There must be a hole in the arguments.

So what’s wrong with the above arguments?

First let’s start with the Nash equilbrium arguments. By the way, many authors use the term “rational” for players that use strategies dictated by Nash equilibrium arguments, but I think “rational” and “irrational” are excessively loaded terms, so I prefer to instead say that a player that follows a strategy dictated by Nash equilibrium arguments is a “Nashist.”

If you are the second player, and the first player has passed, you can deduce that the first player is not a Nashist. So in order to make a correct play (maximize your expected winnings) you need to choose some probability distribution for what the first player’s strategy is, and then compute whether you will win more or less depending on whether you challenge. There doesn’t seem to be any obvious way to choose the probability distribution for the first player’s strategy, but you can definitely say that he is not certainly a Nashist! A Nashist is stuck (by definition of being a Nashist) believing that all other players are always Nashists, even in the face of clear evidence that they are not (you see why I don’t like to call Nashists “rational”) and would choose the strategy that followed from that obviously wrong belief; he would always challenge as the second player.

A non-Nashist, on the other hand, can come up with a reasonable probability distribution for the first player’s strategy, and come to the conclusion that he should pass if he is the second player and he has a .000001.

OK, so we can see why the second player might want to pass if he receives a .000001. What about the first player: is it wrong to be a Nashist? Should you pass or challenge if you get a .001, or a .000001, or a .000000001? A Nashist would be compelled, by the force of his “idealogy,” to challenge in each case. But you can make a good argument that that’s wrong. Instead, let’s say I am the first player and I have a .000001. I know that if I pass, the second player will be able to deduce that I’m not a Nashist, and will go through the argument given above for the second player. Now “all” I have to do is form my probability distribution for what his probability distribution of my strategy will be, and compute whether I will have more chance of winning depending whether I challenge or not. Again there’s no obvious way to choose these probability distributions, but it seems pretty clear to me to that reasonable probability distributions will give a result that says don’t challenge if you are the first player and you have a sufficiently low number.

Well what about the other argument, that says that the first player should always challenge, since he is at a disadvantage and if he always challenges, he’ll win half the time? It seems paradoxical to think that there is a strategy that can do better than winning half the time for the first player.

Of course, all Nashists will always win exactly half the time, whether they play first or second. If you are playing against someone who you know is a Nashist, it actually doesn’t matter what you do! But suppose instead that you are playing against an ordinary human. You should play forming the best possible probability distribution of what they will do. Many humans will challenge if they have a number above .5 and pass otherwise, whether or not they play first (a very bad strategy by the way). It is perfectly possible, indeed likely, that playing against a population of ordinary humans, there exists a strategy that wins more than half the time for the first player. I can’t prove that strategy exists by arguing in this way (one would need to run experiments to determine the probability distributions of strategies, and then it would be easy to compute), but I’m actually pretty confident that it does exist, and I’m also pretty confident that the strategy involves passing when you are given a .000001 as the first player.

So I don’t believe either argument for always challenging holds up, which is comforting, because always challenging does seem intuitively wrong. Unfortunately, I can’t tell you exactly what the optimal strategy is either, at least until you tell me what the true probability distribution is for player strategies.

images1.jpg

By the way, Arne recommended that I pick up Game Theory Evolving, by Herbert Gintis, for my son. It’s a wonderful book, full of interesting games and solved problems in game theory. Adam and I both love it. Gintis gives other examples showing that Nashists (he calls them “self-regarding agents”) can choose bizarre strategies, including “Rosenthal’s Centipede Game:”

The players, Mutt and Jeff, start out with $2 each, and they alternate rounds. On the first round, Mutt can defect by stealing $2 from Jeff, and the game is over. Otherwise, Mutt cooperates by not stealing, and Nature gives Mutt $1. Then Jeff can defect and steal $2 from Mutt, and the game is over, or he can cooperate and Nature gives Jeff $1. This continues until one or the other defects, or each player has $100.

In this game, the Nash equilibrium, obtained by induction by working backwards from the end of the game, when it is clearly “correct” to defect, is that Mutt should immediately defect on his first turn. So that’s what a Nashist would do, but fortunately humans are much more “rational” than Nashists!

Algorithms for Physics

August 14, 2007


smac_cover.jpg

Much of my own work is at the intersection of statistical mechanics and algorithms, in particular understanding and developing new algorithms using ideas originating in statistical mechanics. Werner Krauth also works at the intersection of the two fields, but coming from a very different angle: he is a leading expert on the development and application of algorithms to compute and understand the properties of physical systems.

In his recently published book, “Statistical Mechanics: Algorithms and Computations,” targeted at advanced undergraduates or graduate students, he covers a very wide range of interesting algorithms. To give you an idea of the coverage, I’ll just list the chapters: “Monte Carlo methods,” “Hard disks and spheres,” “Density matrices and path integrals,” “Bosons,” “Order and disorder in spin systems, “Entropic forces,”and “Dynamic Monte Carlo methods.”

Krauth’s presentation is leavened by his humor, and he often uses the results obtained using his algorithms to make surprising points about physics that would otherwise be hard to convey.

I am often asked by computer science or electrical engineering scientists and researchers for good introductions to physics, and particularly statistical mechanics, and I’m now happy to be able to recommend this book.

images.jpg

Specifying physics explicitly in terms of algorithms, as Krauth does, gives a very concrete basis for understanding concepts that can otherwise seem terribly abstract. Gerald Sussman and Jack Wisdom make this point in the preface of their already classic book (which is available online) “Structure and Interpretation of Classical Mechanics”:

“Computational algorithms are used to communicate precisely some of the methods used in the analysis of dynamical phenomena. Expressing the methods of variational mechanics in a computer language forces them to be unambiguous and computationally effective. Computation requires us to be precise about the representation of mechanical and geometric notions as computational objects and permits us to represent explicitly the algorithms for manipulating these objects. Also, once formalized as a procedure, a mathematical idea becomes a tool that can be used directly to compute results.”

But while Sussman and Wisdom’s book focuses in great detail on classical mechanics, Krauth’s book covers more broadly subjects in classical mechanics, statistical mechanics, quantum mechanics, and even quantum statistical mechanics. Another difference is that Sussman and Wisdom specify their algorithms in executable Scheme code, while Krauth uses pseudo-code. Of course, both choices have their advantages, just as both of these books are worth your time.

Gateway High School, 1981

August 13, 2007


paulgraham_1960_3304843.gif

Paul Graham has a great web-site full of thought-provoking essays. Some of them were collected into his fascinating book “Hackers and Painters.”

One of those essays, “Gateway High School, 1981” talks about our high school, which I in fact graduated from in 1981. The picture above is from that essay; it’s the Chess Club picture from the 1981 Gateway High School yearbook. I’m the one at the bottom left seated at the chess board; Paul is standing at the top left.

If you read Paul’s description, or read his famous essay about “Why Nerds are Unpopular,” my high school sounds very grim, but I really didn’t experience it the same way. I honestly had a pretty good time in high school; maybe that’s why I’m the one who’s smiling in the picture above. I even loved rooting for the football teams (both the Steelers and the Gators), and trace my football fanaticism to those years, when the Pittsburgh Steelers were a dynasty.

When I arrived at Harvard in 1981, I was at first a little intimidated by some of the other students who went to better high schools, but I soon realized that I was easily well-enough prepared. And I was hungry to learn.

Nowadays, I’m most concerned that high school students are so driven to perform in order to be accepted into the elite universities, and that many high school teachers drive the students so hard with homework, that by the time they get to college, the students can have had the natural desire to learn drummed out of them.

Version Control Using Subversion

August 5, 2007

I’ve worked with some twenty-odd interns over the last few years at MERL, all of them graduate students at top electrical engineering and computer science departments from around the world. I’ve also interviewed many more job candidates for our research lab. One fact that has continually amazed me is what a tiny fraction of them have had any previous experience using version control (also called “source code management”) systems.

Version control lets you save each version of a software project as you build it up. Because you know that you can always back up to a previous working version, you are much more confident in writing new code. All professional software developers use version control on every project they work on; working without it is sometimes compared to trying to write a novel with a word-processor that doesn’t have a delete key.

If you’re getting started with version control, I recommend that you use Subversion, (also known as “svn”) which has several fundamental improvements over the older CVS system. A free book explaining the system comes with it, but I also recommend “Pragmatic Version Control Using Subversion”, by Mike Mason.

If you’re a budding programmer or a graduate student in an EECS department, think of it this way–not only will using version control help you write better software, but it will help you get a job if you ever want to go into industry. I doubt we’re the only ones who routinely ask candidates whether they’ve used version control to help assess their software development skills. [And if it crossed your mind, you can’t fake your way through this; if you say that you’ve used it, you’ll get follow-ups.]

“Ageless Quest” by Lenny Guarente

August 5, 2007


519qsvhv4wl_sl210_.jpg

MIT professor Lenny Guarente is a pioneer and leader in the study of the molecular biology of aging. This book is a popularized account of some of the early research that he and his students and post-docs conducted; research that helped move the study of aging from being a kind of slightly disreputable scientific backwater to one of the most dynamic and exciting fields of modern molecular biology. Guarente’s research focused on sirtuins, which are proteins that are now understood to retard aging in a wide variety of organisms, with mechanisms that vary depending on the organism.”

Ageless Quest” is an easy read and a great introduction to the field. It had a surprising amount of impact on me; after reading this book I decided that I wanted to learn more about what was happening in this very important field, so I audited an MIT reading course on the molecular biology of aging taught by Angeiszka Czopik and Danica Chen, two post-docs in Prof. Guarente’s lab, and then I attended the 2006 Summer School Course on the molecular biology of aging at Woods Hole’s famous Marine Biological Laboratory, organized by Gary Ruvkun and Steve Austad.

This book probably won’t have that big an impact on you! It’s a pretty light book weighing in at only 154 pages; but you can learn a lot whether or not you have a background in biology.