Information Processing

Just another weblog

Archive for June 2006

Googleplexus, Nexus

with 2 comments

A quick report on my Google visit. The place didn’t disappoint — it’s like the 90’s tech bubble never ended there! The cafeteria was great, the buildings are full of bean bag chairs, pool tables, espresso stations, mini scooters, you name it. The employees are surprisingly young and unsurprisingly very geeky. It felt like I was back on the Caltech campus. There was one guy in pajamas in the cafeteria, and lots of people with their dogs. At Caltech one often sees students who look like they just rolled out of bed at midday, staggering across campus in flip flops, gym shorts and t-shirts to hand in a problem set. Google had that feel to me. Interestingly, the ethnic mix is about the same as at Caltech or MIT — at least a third of employees are south- or east-Asians.

The place has tremendous energy. You can tell people are very engaged in their work, and that Google is straining to keep up with the operational load of delivering search services to the entire planet. I noticed a lot of smaller satellite buildings scattered a few blocks from the main campus. They have a terrible space crunch — many developers are sitting four to a small office. CEO Eric Schmidt’s office is tiny and even celebrity technologists like Kai Fu Lee are sharing offices with several other people. (I suppose Lee might spend most of his time in China.) At one point we walked by what appeared to be an inflatable white tent in one of the open areas in building 43. Joking, I asked if those were temporary offices. My host replied (deadpan, peering into the tent) “No, I think that’s a conference room, and it’s not temporary…”

Written by infoproc

June 28, 2006 at 2:24 pm

Posted in globalization, startups


leave a comment »

Next week I’m headed down to the valley on another Robot Genius business trip. Among the meetings with engineers, bankers and VCs is a visit to the Googleplex in Mountain View. I’ll let you know how the wasabi seared ahi is, and whether I managed to get a free massage 😉

Seriously though, I’m one of Google’s biggest fans, and fascinated by the technical aspects of what they’re doing. This extends well beyond search, to things like AI and natural language (they are in a good position to use statistical methods with the large corpus of text they have on hand), massive scaling of computing systems (they have over 500k servers deployed) and even how they hire and manage highly talented technologists. I would consider taking my next sabbatical there! (OK, also in the running are the Santa Fe Institute and possibly KITP Beijing.)

Here’s an interesting example of the kind of problem Google has to deal with in its core search business. A Russian hacker managed to create billions of fake Web pages using scraped content. He registered numerous domains and hosted the pages on servers in Russia. Through clever linking he managed to get Google to index his fake pages and made of order $100k in AdSense revenue before being discovered. This type of search engine manipulation is an ongoing problem, which, along with click fraud, threaten Google’s core business.

Below is a hint about something we’re working on in the Robot Genius labs. Why shouldn’t search engines characterize the executables found on Web sites, not just the text or images?

We’re also crawling the web in order to find distributors of spyware, and can automatically identify packages installed by bad guys as soon as they are created on the system.

Written by infoproc

June 24, 2006 at 7:46 pm

Posted in globalization, startups


with 8 comments

There’s an amusing back and forth (complete with little fables) going on between physicist Dave Bacon and computer scientist Scott Aaronson on their respective blogs. Both work on quantum information theory, and the argument appears to be an old one about physicists’ intuition versus mathematical rigor. (“By the time you can prove it, the result will have been obvious to us for a generation” vs. “You guys are just guessing! Real men prove theorems”.)

I’d like to add my opinion in the form of the following two quotes from Feynman (whom Schwinger remembered in an epitaph as “the outstanding intuitionist of our age”):

“We know a lot more than we can prove.”

“Mathematics is to physics as masturbation is to sex.”

I really only agree with the first quote, which, if you think about it, says something quite deep.

For our proof-obsessed brethren, I recommend the book Proofs and Refutations by Lakatos. How is it, exactly, that we “know” things? Can we ever be entirely sure that a given proof is error free? If not, how is it different from having only a probabilistic (e.g., confidence level) sense of truth?

It is their attempts to deal with unwanted and unexpected refutations – to preserve a valuable theory in the face of imperfect axioms and proof methods – that teach mathematicians the true depths of their conceptions and to point the way to new and deeper ones.

Lakatos shows this by an account of the historical development of the concept of proof in mathematics and by showing in historical detail how certain valuable ‘proofs’ were preserved in the face of refutation. To this point Lakatos shows that the ‘proofs’ of the truth of Euler’s number are no proofs at all. The great mathematician Euler noticed that for any regular polyhedron the formula V-E+F=2 holds where V is the number of vertices, E is the number of edges and F is the number of faces. Euler’s and his successors’ proofs fall before any number of counterexamples. Does this prove that the theorem is ‘incorrect?’ Or does it mean… that their concept of what constituted a regular polyhedron was deficient. Lakatos shows how these conceptions were modified over a couple of hundred years as counterexample after counterexample were faced.

Written by infoproc

June 20, 2006 at 8:24 pm

Posted in Uncategorized

Kamikazes and terrorists

with 4 comments

Freeman Dyson reflects on kamikaze pilots and Islamic terrorists in the New York Review of Books. (See the very end of the article, which is mostly a review of Daniel Dennett’s book on religion and natural science.) I have heard it said many times that men die in battle for friends in their unit, rather than for flag and country.

The best source of information about modern Islamic terrorists that I know of is a book, Understanding Terror Networks, by Marc Sageman.[1] Sageman is a former United States foreign service officer who worked with the Mujahideen in Afghanistan and Pakistan. In chapter 5 of his book, he describes in detail the network that planned and carried out the September 2001 attacks on the United States. He finds that the bonds holding the group together, during its formative years in Hamburg, were more personal than political. He concludes: “Despite the popular accounts of the 9/11 perpetrators in the press, in-group love rather than out-group hate seems a better explanation for their behavior.”

To end this review, I would like to introduc another recently published book, Kamikaze Diaries: Reflections of Japanese Student Soldiers, by Emiko Ohnuki-Tierney.[2] This contains extensive extracts from diaries written by seven of the young men who died in suicidal missions or as kamikaze pilots in the closing months of World War II. The diaries give us firsthand testimony of the thoughts and feelings of these young soldiers who knew that they were fated to die. Their thoughts and feelings are astonishingly lucid and free from illusions. Some of them expressed their feelings in poetry. All of them were highly educated and familiar with Western literature in several languages, having spent most of their brief lives in reading and writing. Only one of them, Hayashi Ichizo, was religious, having grown up in a Japanese Christian family. His Christian faith did not make self-sacrifice easier for him than for the others. He had read Kierkegaard’s Sickness unto Deathand carried it with him on his final mission together with his Bible.

All of the young men, including Hayashi, had a profoundly tragic view of life, mitigated only by happy memories of childhood with family and friends. They were as far as it was possible to be from the brainwashed zombies that contemporary Americans imagined to be piloting the kamikaze planes. They were thoughtful and sensitive young men, neither religious nor nationalistic fanatics.

Here I have space to mention only one of them, Nakao Takanori, who must speak for the rest. Nakao left a poem beginning, “How lonely is the sound of the clock in the darkness of the night.” In his last letter to his parents, a week before his death, he wrote,

At the farewell party, people gave me encouragement. I did my best to encourage myself. My co-pilot is Uno Shigeru, a handsome boy, aged nineteen, a naval petty officer second class. His home is in Hyogo Prefecture. He thinks of me as his elder brother, and I think of him as my younger brother. Working as one heart, we will plunge into an enemy vessel. Although I did not do much in my life, I am content that I fulfilled my wish to live a pure life, leaving nothing ugly behind me.

We have no firsthand testimony from the young men who carried out the September 11 attacks. They were not as highly educated and as thoughtful as the kamikaze pilots, and they were more influenced by religion. But there is strong evidence that they were not brainwashed zombies. They were soldiers enlisted in a secret brotherhood that gave meaning and purpose to their lives, working together in a brilliantly executed operation against the strongest power in the world. According to Sageman, they were motivated like the kamikaze pilots, more by loyalty to their comrades than by hatred of the enemy. Once the operation had been conceived and ordered, it would have been unthinkable and shameful not to carry it out.

Written by infoproc

June 18, 2006 at 4:23 am

Posted in Uncategorized

Brains, genes, backlash

with 5 comments

We posted before about Bruce Lahn’s research. Lahn showed that two variants of a gene suspected to be related to brain function exhibit very different distributions in different ethnic groups, and show signs of having been subject to strong selection fairly recently in human history. Today the WSJ ran a front page article on Lahn and the backlash against his research (excerpts below). See also this interview with Lahn from Science.

Last September, Bruce Lahn, a professor of human genetics at the University of Chicago, stood before a packed lecture hall and reported the results of a new DNA analysis: He had found signs of recent evolution in the brains of some people, but not of others.

It was a triumphant moment for the young scientist. He was up for tenure and his research was being featured in back-to-back articles in the country’s most prestigious science journal. Yet today, Dr. Lahn says he is moving away from the research. “It’s getting too controversial,” he says.

Dr. Lahn had touched a raw nerve in science: race and intelligence.

What Dr. Lahn told his audience was that genetic changes over the past several thousand years might be linked to brain size and intelligence. He flashed maps that showed the changes had taken hold and spread widely in Europe, Asia and the Americas, but weren’t common in sub-Saharan Africa.

Web sites and magazines promoting white “racialism” quickly seized on Dr. Lahn’s suggestive scientific snapshot. One magazine that blames black and Hispanic people for social ills hailed his discovery as “the moment the antiracists and egalitarians have dreaded.”

Dr. Lahn has drawn sharp fire from other leading genetics researchers. They say the genetic differences he found may not signify any recent evolution — and even if they do, it is too big a leap to suggest any link to intelligence. “This is not the place you want to report a weak association that might or might not stand up,” says Francis Collins, director of the genome program at the National Institutes of Health.

Several scientific groups have set out to disprove or challenge Dr. Lahn’s discoveries. His own university now says it is abandoning a patent application it filed to cover a DNA-based intelligence test that drew on his work.

As scientific tools for probing genes become increasingly powerful, research into human differences has exploded. Most of the time, scientists are looking for clues about the causes of disease. But some research is raising tensions as scientists such as Dr. Lahn venture into studies of genetic differences in behavior or intelligence.

Pilar Ossorio, a professor of law and medical ethics at the University of Wisconsin, criticizes Dr. Lahn for implying a conclusion similar to “The Bell Curve,” a controversial 1994 bestseller by Richard J. Herrnstein and Charles Murray. The book argued that the lower average performance by African-Americans on IQ tests had a genetic component and wasn’t solely the result of social factors. Referring to Dr. Lahn and his co-authors, Prof. Ossorio says: “It’s exactly what they were getting at. There was a lot of hallway talk. People said he’s doing damage to the whole field of genetics.”

The 37-year-old Dr. Lahn says his research papers, published in Science last September, offered no view on race and intelligence. He personally believes it is possible that some populations will have more advantageous intelligence genes than others. And he thinks that “society will have to grapple with some very difficult facts” as scientific data accumulate. Yet Dr. Lahn, who left China after participating in prodemocracy protests, says intellectual “police” in the U.S. make such questions difficult to pursue.

Scientists believe that a small group of anatomically modern humans struck out from Africa probably less than 100,000 years ago. After arriving on the Eurasian land mass, they continued to split up and eventually humans populated nearly every corner of the globe. One use of genetic research is to probe how each group evolved differently after becoming isolated from the others. Recently created genetic maps of people of African, Asian and European ancestry make that research easier.

For instance, researchers have found that most Europeans have a genetic variant that lets them fully digest milk as adults. The variant is much less common in Africa and Asia, where lactose intolerance is widespread. Scientists theorize that it spread quickly among Europeans because drinking milk from domesticated dairy animals conferred a nutritional advantage. Similar evolutionary reasoning may explain why many people in malaria-prone parts of Africa carry gene variants linked to malaria resistance.

Other research is starting to explain variations in human skin color and hair texture. But scientists tense up when it comes to doing the same sort of research on the brain. Sociologist Troy Duster, who studies the use of racial categories by geneticists, worries that scientists will interpret data in ways that fit their prejudices. He cites the sorry history of phrenology, a study of skull shapes popular in the 19th century, and other pseudoscientific techniques used to categorize people as inferior. “Science doesn’t transcend the social milieu,” says Dr. Duster, of New York University.

Dr. Lahn traces his interest in human differences back to his youth in China. Foreigners there used to have a special currency that they could use at stores closed to ordinary Chinese. “I wondered why people were different, and why Chinese were at the bottom,” he says.

By the time violence struck Tiananmen Square in 1989, Dr. Lahn, the son of two physicists, was an undergraduate at Harvard University. He channeled his curiosity into genetics and built his reputation with a groundbreaking study of the Y chromosome. After taking a post at the University of Chicago in 2000, Dr. Lahn won a prestigious fellowship from the Howard Hughes Medical Institute.

The fellowship pays most of his research bills and has allowed him to pursue creative projects, often on attention-grabbing subjects. One study looked at how promiscuity among female chimpanzees, gorillas and humans affected the evolution of a gene that makes sperm sticky. “Bruce is in a hurry to be famous,” says Martin Kreitman, a Chicago colleague who is friendly with him.

Henry Harpending, a University of Utah anthropology professor who recently published a theory for why Ashkenazi Jews tend to have high IQ’s, says Dr. Lahn once suggested they co-author an article for Scientific American about the genetics of behavior, in which they could explain why “Chinese are boring.”

“I think that Bruce doesn’t understand political correctness,” Dr. Harpending says. Dr. Lahn says he only vaguely recalls the conversation but confirms that he wonders whether during China’s imperial times there was “some selection” against rebellious individuals.

In recent years, Dr. Lahn has become interested in why the human brain is so large and complex. Although humans and chimpanzees share about 96% of their DNA, human brains are about four times larger. Even today, researchers can find a correlation, on average, between people’s brain size and their IQ.

Dr. Lahn’s group zeroed in on the role of two genes, called ASPM and microcephalin, that are known to have a role in brain size. Humans with defective copies of either gene are born with brains only about one-third the normal size.

Studying DNA from several species, the Chicago team found that, over millions of years, the genes had undergone more rapid change in monkeys, apes and humans than in other animals. Their next step was to determine if evolution had continued in modern humans. Dr. Lahn’s graduate students began decoding DNA from 1,184 people belonging to 59 groups from around the world, including Bedouins, Pima Indians and French-speaking Basques.

The data showed that evolution had continued in recent millennia. A statistical analysis of DNA patterns suggested that new mutations in each of the two brain-related genes had spread quickly through some human populations. Evidently, these mutations were advantageous among those populations — just as the genetic variant promoting milk digestion was advantageous to early Europeans. Dr. Lahn and his team further observed that the new mutations are found most frequently outside of Africa.

What the data didn’t say was how the mutations were advantageous. Perhaps the genes play a role outside of the brain or affect a brain function that has nothing to do with intelligence.

While acknowledging that the evidence doesn’t permit a firm conclusion, Dr. Lahn favors the idea that the advantage conferred by the mutations was a bigger and smarter brain. He found ways to suggest that in his papers. One mutation, which according to his estimates arose some 40,000 years ago, coincided with the first art found in caves, the paper observed. The other mutation, present mostly in people from the Middle East and Europe, and estimated to be 5,800 years old, coincided with the “development of cities and written language.”

That suggested brain evolution might have occurred in tandem with important cultural changes. Yet because neither variant is common in sub-Saharan Africa, there was another potential implication: Some groups had been left out.

The dean of the University of Chicago’s medical school, James L. Madara, says he approached Dr. Lahn before the papers were published. They discussed whether the report could be taken out of context. “Let the chips lie where they may,” Dr. Madara says he told Dr. Lahn. As long as the ideas and data are clear, “don’t worry about the implications,” the dean said.

John Easton, head of media relations at the medical school, says his office was worried the work could be misinterpreted and abused by racist groups. Mr. Easton borrowed a copy of “The Mismeasure of Man,” the famous attack on IQ tests and brain-volume measurements by the late paleontologist Stephen Jay Gould. Mr. Easton helped Dr. Lahn with talking points about his research. “We said, ‘Don’t be shy about telling people what it doesn’t mean,’ ” Mr. Easton recalls.

Mr. Easton says Dr. Lahn “makes us nervous” but “with Bruce we know it’s not driven by personal bias.” That is because Asians “don’t score at the top” in the frequency of the brain-gene mutations, Mr. Easton says.

Dr. Lahn’s paper and talk at his university — in which he also claimed the gene variants were probably linked to higher IQ — provoked a strong reaction both on and off campus. Dr. Collins, head of the federal genome program, obtained advance copies of the papers and circulated them to top population geneticists. He wasn’t persuaded by the statistical evidence for evolution and criticized Dr. Lahn’s work in media interviews.

The papers won wide attention among researchers, and several responded by setting out to test Dr. Lahn’s findings. Scientists at the Broad Institute, a top genetics center in Cambridge, Mass., have been reanalyzing some of the data and say they may challenge Dr. Lahn’s finding that evolution acted on ASPM, one of the genes. Broad’s influential chief, Eric Lander, says scientists probing recent evolution run the risk of “seeing a difference, and saying there is a story to fit it.”

A team at the University of California, Los Angeles, recently tested whether the gene variants actually affect brain size. They studied DNA from 120 people whose brain volumes they had already measured using magnetic-resonance imaging. They didn’t find any difference. “It certainly makes you want to look at other explanations” of what the variations mean, says Roger P. Woods, a UCLA brain-mapping expert who reported the results in May.

Some of Dr. Lahn’s co-authors are also uncomfortable with the work. Sarah Tishkoff, a geneticist at the University of Maryland who provided DNA from remote African groups, says she is bothered how one paper drew a link between the genetic changes and the rise of civilization. She thinks it is too early to reach any conclusions about why the changes spread and says it is “very simplistic” to imagine that a single gene could have a major effect on complex cultural traits.

Several groups of scientists have sent letters to Science criticizing the papers. Dr. Lahn prepared responses, sending one earlier this month, but Dr. Tishkoff wasn’t willing to add her name to them.

“You have to follow the data wherever it leads, but speculating in this field is dangerous,” says Spencer Wells, head of the National Geographic Society’s Genographic Project, a five-year, $40 million effort to collect DNA samples from 100,000 indigenous people. Dr. Wells says the project team might try to find evolutionary reasons for physical differences such as why Danes are taller than pygmies. But Dr. Wells says National Geographic won’t study the brain. “I think there is very little evidence of IQ differences between races,” he says.

The accuracy of Dr. Lahn’s work and his views on race came up in his tenure review last fall, says a person familiar with it. After debate, his department voted unanimously in his favor, according to another faculty member. A more senior committee agreed and awarded Dr. Lahn the post of full professor, although it wasn’t unanimous, this person says.

Dr. Lahn stands by his work but says that because of the controversy he is moving into other projects. Earlier this year, Mr. Easton of the university’s media department forwarded Dr. Lahn a paper by two economists looking at the IQ of infants of different races. Dr. Lahn wasn’t interested. “I’m surprised anyone studies this,” he replied in an email.

Dr. Lahn says he isn’t as eager as he once was to continue studying brain differences. P. Thomas Schoenemann, a professor of anthropology at the University of Michigan-Dearborn, says that at Dr. Lahn’s request he collected DNA from 25 people whose brain sizes he had studied previously. But the two scientists haven’t been in touch recently.

The university’s patent office is also having second thoughts. Its director, Alan Thomas, says his office is dropping a patent application filed last year that would cover using Dr. Lahn’s work as a DNA-based intelligence test. “We really don’t want to end up on the front page…for doing eugenics,” Mr. Thomas says.

More recently, Dr. Lahn says he was moved when a student asked him whether some knowledge might not be worth having. It is a notion to which he has been warming. Dr. Lahn says he once tried testing himself for which version of the brain genes he has. The experiment’s outcome was blurry “but it wasn’t looking good,” he says. He hasn’t tried testing himself again.

Written by infoproc

June 16, 2006 at 10:30 pm

Posted in genetics

More null energy condition

leave a comment »


This is an extension of an earlier paper hep-th/0502203 (see blog post here). We show that in a broad class of models violation of the null energy condition indicates instability. The results are relevant to general relativity and to cosmology.

A paper by Dubovsky et al. (Ref. [6] in the new paper) exhibited a loophole in our earlier results involving superluminal (acausal) excitations. We traced this to an equation in our analysis (Eq. (47) in the new paper) that needs to be solved to find the unstable mode. In models with superluminal excitations this equation is solvable in some frames but not others (this is a sickness of acausality). Correspondingly, in some frames the Hamiltonian has no negative mode. In the appendix of the new paper we show that requiring causality is enough to restore the link between NEC violation and instability.

Coincidentally, the paper posted just before ours, hep-th/0606090 (Creminelli et al.) discusses some effective theories that can violate the NEC and be stable. Our results don’t cover these models as they have four-derivative terms in the Lagrangian. We restrict ourselves to models which have classical equations of motion that are second order PDEs. I don’t know what to make of third and higher order PDEs — who knows what initial conditions are well-posed in those models.

However, the Creminelli et al. paper and the Dubovsky et al. paper are examples of how the creativity of model builders tends to evade the results of theorem-provers. No go theorems are only as good as their assumptions!

The null energy condition and instability

Authors: Roman V. Buniy, Stephen D. H. Hsu, Brian M. Murray

We extend previous work showing that violation of the null energy condition implies instability in a broad class of models, including gauge theories with scalar and fermionic matter as well as any perfect fluid. Simple examples are given to illustrate these results. The role of causality in our results is discussed. Finally, we extend the fluid results to more general systems in thermal equilibrium. When applied to the dark energy, our results imply that w is unlikely to be less than -1.

Written by infoproc

June 13, 2006 at 2:03 am

Posted in physics

The origin of probability in quantum mechanics

with 2 comments


Of related interest, slides of a talk covering the same material. (Check out Gork the robot!)

Title: Discreteness and the origin of probability in quantum mechanics
Authors: R. Buniy, S. Hsu, A. Zee

Attempts to derive the Born rule, either in the Many Worlds or Copenhagen interpretation, are unsatisfactory for systems with only a finite number of degrees of freedom. In the case of Many Worlds this is a serious problem, since its goal is to account for apparent collapse phenomena, including the Born rule for probabilities, assuming only unitary evolution of the wavefunction. For finite number of degrees of freedom, observers on the vast majority of branches would not deduce the Born rule. However, discreteness of the quantum state space, even if extremely tiny, may restore the validity of the usual arguments.

A relevant passage from a recent article by Steve Weinberg:

Einstein’s Mistakes, Physics Today, November 2005

Bohr’s version of quantum mechanics was deeply flawed, but not for the reason Einstein thought. The Copenhagen interpretation describes what happens when an observer makes a measurement, but the observer and the act of measurement are themselves treated classically. This is surely wrong: Physicists and their apparatus must be governed by the same quantum mechanical rules that govern everything else in the universe. But these rules are expressed in terms of a wavefunction (or, more precisely, a state vector) that evolves in a perfectly deterministic way. So where do the probabilistic rules of the Copenhagen interpretation come from?

Considerable progress has been made in recent years toward the resolution of the problem, which I cannot go into here. It is enough to say that neither Bohr nor Einstein had focused on the real problem with quantum mechanics. The Copenhagen rules clearly work, so they have to be accepted. But this leaves the task of explaining them by applying the deterministic equation for the evolution of the wavefunction, the Schrödinger equation, to observers and their apparatus. The difficulty is not that quantum mechanics is probabilistic—that is something we apparently just have to live with. The real difficulty is that it is also deterministic, or more precisely, that it combines a probabilistic interpretation with deterministic dynamics.

Written by infoproc

June 8, 2006 at 4:01 am

Posted in physics