on sorting algorithms

Saturday Morning Breakfast Cereal:

(this is how mergesort really works)

Markets in everything, personal services edition

(Straight from Marginal Revolution) Markets in everything, personal services edition:

A number of people have been hiring “virtual” assistants in lower-wage countries to do all the tasks in their life that don’t require a personal presence. ...

[One man] has his assistant seducing women for him. His assistant, who is female and lives in India, logs onto his account on a popular dating site, browses profiles and (pretending to be him) makes connections with women on the site. She has e-mail conversations and arranges first dates. Then her employer reads the e-mail conversation and goes to the date.

"Gee you're nothing like I imagined you from your emails!"

Doing away with formal peer review

The New York Times considers some efforts to do away with peer review and marshall the connectedness of the web.

The most pressing intellectual issue in the next decade is this tension between the insular, specialized world of expert scholarship and the open and free-wheeling exchange of information on the Web. “And academia ... is caught in the middle.”

I think making work publicly available online is Very Good (I do some of that myself). But doing away with peer review is a Bad Idea.

Peer review is a barrier to entry -- and that's a good thing. It's a sort of curated, walled garden of approved content. When I am working firmly within my area of expertise, I am comfortable evaluating the quality and representativeness of the papers I read. But sometimes -- more often than I would like -- I find myself well outside my area of expertise, and without a good sense of the lay of the land. Essay reviews and general resources like the Stanford Encyclopedia of Philosophy are helpful, but peer reviewed journals are key. Someone with expertise has okayed that content. Peer review is a proxy for knowing I'm not wasting my time.

If peer review is to be done away with, something else must replace it. If curation can be crowdsourced on the internet, I'm for it -- I'm certainly not fond of waiting for referee reports. But moderated internet comments like these ones simply won't do.

predictions

via Marginal Revolution 

Robert Sloss predicted the iPhone in 1910

Well, more or less.  Or is it an iPad?  In 1910 Stoss published an essay called "The Wireless Century," intending to predict the world of 2010.  In this world everyone carries around a "wireless telegraph" which:

1. Serves as a telephone, the whole world over.

2. Either rings or vibrates in your pocket.

3. Can transmit any musical recording or performance with perfect clarity.

4. Can allow people to send each other photographs, across the entire world.

5. Can allow people to see the images of paintings, museums, etc. in distant locales.

6. No one will ever be alone again. 

7. Can serve as a means of payment, connecting people to their bank accounts and enabling payments (Japan is ahead of us here).

8. Can connect people to all newspapers, although Sloss predicted that people would prefer that the device read the paper aloud to them (not so much the case).

9. Can transmit documents to "thin tubes of ink," which will then print those documents in distant locales.

10. People will have a better sense of the poor, and of suffering, because they will have witnessed it through their device (not obviously true, at least not yet).

11. People will vote using their devices and this will empower democracy (nope).

12. Judicial testimonies will be performed over such devices, often from great distances.

13. People will order perfectly-fitting fashions from Paris; this guy should be in the Apps business.

14. Married couples will be much closer, and distance relationships will be closer and better.

15. Military targeting and military orders will become extremely precise.

The essay is reprinted in the Arthur Brehmer book Die Welt in 100 Jahren.  The book is interesting throughout; a bunch of the other writers thought in 2010 we would be fighting wars with large zeppelins.

I'm not even going to try predicting what will be the case for 2110.

8 signs a P≠NP proof is wrong

Here.

(N.B. I scheduled the next few posts to self-publish over the weekend while I was traveling. They didn't. Sorry for the then-dearth and present-glut.)

juxtaposition

Is Google making us stupid? Or smart?

Nicholas Carr for The Atlantic:

Over the past few years I’ve had an uncomfortable sense that someone, or something, has been tinkering with my brain, remapping the neural circuitry, reprogramming the memory. My mind isn’t going—so far as I can tell—but it’s changing. I’m not thinking the way I used to think. I can feel it most strongly when I’m reading. Immersing myself in a book or a lengthy article used to be easy. My mind would get caught up in the narrative or the turns of the argument, and I’d spend hours strolling through long stretches of prose. That’s rarely the case anymore. Now my concentration often starts to drift after two or three pages. I get fidgety, lose the thread, begin looking for something else to do.

He thinks looking at stuff really fast on the internet has rotted his brain. It's a familiar story.

Sometime in 1882, Friedrich Nietzsche bought a typewriter—a Malling-Hansen Writing Ball, to be precise. His vision was failing, and keeping his eyes focused on a page had become exhausting and painful, often bringing on crushing headaches. He had been forced to curtail his writing, and he feared that he would soon have to give it up. The typewriter rescued him, at least for a time. Once he had mastered touch-typing, he was able to write with his eyes closed, using only the tips of his fingers. Words could once again flow from his mind to the page.

But the machine had a subtler effect on his work. One of Nietzsche’s friends, a composer, noticed a change in the style of his writing. His already terse prose had become even tighter, more telegraphic.... Nietzsche’s prose “changed from arguments to aphorisms, from thoughts to puns, from rhetoric to telegram style.”

I empathize. A year ago, I was reading in preparation for area exams. From all appearances, at some point during the last stretch, when the details of dozens of readings were in my head, I sprained my brain. And I have since been hobbled in my attempts to focus. This blog--and the short, mostly non-academic readings I have done in keeping it up--have been my rehabilitation. It is anyone's guess whether it has worked--or if reading blogs has instead reinforced the bad habits Carr describes.

Or are they bad habits?

The Internet is a machine designed for the efficient and automated collection, transmission, and manipulation of information, and its legions of programmers are intent on finding the “one best method”—the perfect algorithm—to carry out every mental movement of what we’ve come to describe as “knowledge work.”

Of course, algorithms don't require people. Eureka! Science News, so I am told, has no human editor;

it is powered by the Eureka! news engine, a fully automated artificial intelligence.

Its sole purpose is to ensure that you have access to the very latest and popular science breakthroughs. To achieve this, it constantly surfs the web to gather, regroup, categorize, tag and rank science news from all major science news sources.

It computes relationships between science articles and news found on the web using a vector space model and hierarchical clustering. It then automatically determines in which category each news item belongs using a Naive Bayes classifier. Finally, it examines multiple parameters (such as timeliness, rate of appearance on the web, number of sources reporting the news, etc) for each news group. The result is an e! score which represents the relative importance of a news item.

Even if one accepts the breathless-techie claim that a modified naive Bayes classifier is an "artificial intelligence," one might argue that this service is parasitic on the work of human editors (such as those at each of the thirty-seven sources for e!), even if none are involved directly in this enterprise--which, by the way, does not write the news, it just ranks, formats, and displays the news.

If this is also what reading the internet is training my brain to do, it is likely not a good portent for my dissertation.

political climate versus climate science

edge has a nice interview with Stephen Schneider, a climatologist at Stanford. It's worth reading, but here are a few highlights and reactions:

One of the challenges for scientists such as Schneider is balancing good science with policy advocacy. Good science means

don't be too arrogant about the belief in your models; what you do is make projections, and then you crank a knob to try to avoid the more catastrophic outcomes or the outcomes that don't match your values, but we better be reflexive. That means we had better have what in the language of the systems guys is a "complex adaptive system". We need to always build in knobs so that as we get new information that changes our understanding of the structural bases of models, we can in turn crank up or down our degrees of policy control. But we rationalists, we systems analysts, think that's a great model of reality.

Most politicians think it's also the right way to do public policy. But changing public policy often entails

a five-year knock-down political debate—with the auto industry that wants to make big fat polluting cars, and the mining industry that wants to get the coal and uranium at lowest cost—and when all is said and done, they will reach some political compromise that satisfies nobody. But at least it's progress—and the last thing anybody wants to do is go back in five years and revisit that ugly debate and rekindle, among all these already not very satisfied stake-holders, more reasons for them to be angry.

That is why when we intellectuals say, hey, set up a complex-adaptive system, adjust the management knobs as we learn more; politicians say, oh no, we solved it, don't reopen festering compromises. Problem's over. Don't take me back there anytime soon.

The more scientists are aware of the difficulties of the political climate, the better able they will be to work with politicians to "build a rational management system that recognizes that very wide tails on uncertainty distribution mean that you have to be able to crank up or down as you learn more; that you can't claim that the problem's solved and never revisit an issue once legislation is passed."

Schneider also discusses the three roles he takes on as a scientist: education (helping people gain a nuanced view of climate science), understanding the science (how will the climate change in response to CO2, and how will agriculture change in response to climate change), and asking what to do about it. I think all three of these roles are appropriate for scientists, but I find it fascinating that their own education explicitly prepares them only for understanding the science. It's worth asking why this is so.

[When contemplating a policy recommendation, Schneider asks] what will it do to a poor person? It might affect the quality of protein on their family's table. It's a dilemma. On the one hand you have a moral principle: the polluter pays. On the other hand, the relative fraction of my disposable income that that would represent is much less than that of a poor person in a hot country, or even a poor person in the United States. Energy costs are in that sense a regressive tax.

The same goes for many proposed taxes, including the gasoline tax. It will encourage public transit, innovation, and fuel efficiency, but it will also aggressively target the rural poor (who do not have access to public transit and cannot afford new vehicles). The carbon tax, the panacea of the season, has many of the same difficulties.

How do you make deals where the over-consumers (us) work out a deal with the over-populated and the not yet fully consuming group (developing countries), so that they don't just repeat the Victorian Industrial Revolution with the sweatshops, dirty coal burning, internal combustion engine, etc.? The answer is that these economies in transition need to leapfrog right over it to high technology. Exhibit C: cell-phone.

In central China, Schneider explains, there are no traditional telephone lines, but there are millions of cellular phones. Our collective efforts, therefore, should be put to convincing China to invest in infrastructures that support cleaner utilities. [more]

you can die from that -- UPDATE UPDATE

Blogging as the new sweatshop? Methinks the NYT is a little shrill. Yes, two bloggers have died of heart attacks, presumably brought on by stress, unhealthy eating, and the extreme sedentary behavior that comes with blogging for a living (when you work from home, it's always there, and as a result, so are you).

Fortunately for you, dear reader, I don't get paid for my blog, so there's no stress, and I just came back from a run, so I don't think I'll be one of the statistics. I just hope my health insurance premiums don't go up as a result of my dangerous pastimes (oh wait, that's right... I live in Canada now).

For the record, tech bloggers sometimes earn $30-70k/year, and even the 'self-employed' can sometimes pull in $1000/month. But science bloggers aren't quite as popular as tech bloggers. I'd wager philosophy of science blogs are less popular still. That doesn't mean I'm not jealous.

(hat tip Pure Pedantry)

See my previous posts on death and dying.

the link between video games and violence

Would you ban a video game where the objective is to find and kill Saddam Hussein? How about one where the objective is to recruit a suicide bomber to attack the President of the United States? Wafaa Bilal of Rensselaer Institute of Technology (Troy, NY) turned the former into the latter, a move that has--unsurprisingly--raised a few eyebrows.

(Let me point out, the picture on the left is a buddy of mine who talked to Bilal. NOT Bilal. So if you have a problem with Bilal, the man pictured is NOT him.)

At a Sanctuary for Independent Media event in Troy, Bilal defended the move as a political statement meant "to “hold up a mirror” to an American society which believes that such a game is perfectly fine when it is an American killing Iraqis, but which finds itself outside of its comfort zone when it’s the other way around."

Zac Miner, a sociologist friend of mine, was there:

During his speech, Bilal said that the idea for the game started with Quest for Saddam… in which the object is to find and kill Saddam Hussein. Apparently someone in Al Qaeda obtained a copy of the game, changed the skins of the soldiers and Saddam so that now the player is an Iraqi killing Americans and hunting George Bush [the so-called Night of Bush Capturing game].

[Bilal changed] the game from the Al Qaeda version so that instead of the player himself killing Bush, he now has to recruit someone else - in this case, a character skinned to look like Bilal himself… to become a suicide bomber and attack Bush. Bilial said that the point of this is to show the vulnerabilty of Iraqi citizens to recruitment for such purposes.

Unlike most of the event attendees, Zac played a demonstration version of the game in question. He concludes, "As a game, it wasn’t that good - the controls had some problems, the enemy AI wasn’t that great."

pushing tin

The delightful thing about geeks is that, when they become annoyed, they become obsessed with solving a problem. Julianne at Cosmic Variance points out an example: Jason Steffen's computer modeling of an ideal passenger loading scheme for airlines (available on arXiv).

Steffen's first insight is that the commonplace notion of loading from back to front rather than front to back or randomly doesn't address the main bottleneck of passenger-loading: waiting for people to stow their baggage. Indeed, in his model, back-to-front is the second worst loading method examined--only marginally better than the front-to-back worst-case scenario. The key observation is that in each case, only one passenger is able to stow baggage at a time. The first passenger in line begins stowing baggage immediately, but the second person in line has to wait for her to finish before he can begin stowing his bags--and as a result he blocks the third passenger from stowing her bags. Even random orders performed better--by half--because several passengers were able to stow bags at once.

The ideal depends on aircraft layout, but in the case of rows of 6 passengers, the best scenario is to board in six stages, each ordered back to front: 1) even rows of wing seats, 2) odd row wings, 3) even center, 4) odd center, 5) even aisle, and 6) odd aisle. This can result in a six-fold decrease in loading time.

Realities such as families traveling together, recalcitrant passengers, and psychological effects (front-to-back or back-to-front are more psychologically satisfying than random loading because despite their real disadvantages, it seems) are, of course, all ignored.

slutty turing test

via Slashdot:

a chatbot is making the rounds that successfully emulates an easily-laid woman. As such, it dupes lonely Russian males into divulging personal and financial details at a rate of one every three minutes. All jokes aside — and a lot of them come quickly to mind — that sure sounds like the Turing Test to me

I'm not sure this is quite what Turing had in mind, but close enough.

the way we think

The tools we use to gather, store, and analyze information inevitably exert a strong influence over the way we think.

Now that the internet is our go-to tool,

What I wonder, as a long-ago philosophy instructor, is whether today's students, who are used to this "horizontal grazing" style of research, can any longer appreciate the long, complex logical structures that were traditionally regarded as serious thought.

Or do they just snag a few quotables from other blogs an post them without further analysis?

signaling behaviour

Social networking sites are a fascinating phenomenon. Users create an online persona, including pictures, likes and dislikes, relationship status, and activities. Sometime users tend to provide enough information for their friends to identify them--something like a highschool yearbook entry. Most of us want facebook to be much more--a different model of interpersonal interaction.

Much of what goes on on a site like facebook can be considered, by the cynical among us, signaling behavior--that is, because we have such freedom of choice as to what we include or elide, virtually everything on facebook counts as a personal advertisement. Most native English-speakers have read "Hamlet" once or twice in our lives, but not all of us would include it as a favourite book. For those who do, it serves as a signal, an affiliation, or an invitation. Thanks to attentions from the more quantitatively inclined, "Hamlet" also signals an SAT score in the 1000 range. The idea is to mine the apparently harmless public data facebook collects for various affiliations, like "the 10 favorite books at the University of Toronto," and presume a correlation with other known characteristics of that affiliation, in this case the published average SAT levels. Finally, we can look at our own facebook friends to see if any of them lists "Hamlet" as a favourite book. If they do, then by the improper logic that accompanies all signaling behaviour, their SAT scores must be in the 1000 range. Lolita, One Hundred Years of Solitude, and Crime and Punishment are smarty-pants signals (1300+ SATs), though I imagine that the release of a film for One Hundred Years will be a near-term spoiler.

Most uses of facebook are old-fashioned. We use it to pass notes, whisper rumors, send invitations to parties, flirt, and spy on our friends. Sharing photos, notes, and interests isn't novel, but it is a lot easier on facebook--and it allows interested parties to learn as much or as little as they wish. Facebook status messages are new: they can be passive announcements. "Needs a hug" is certain to get a response.

a respite from Amsterdam

From Jason Kottke via Marginal Revolution:

Ben Tesch is about to launch a collaborative weather site called cumul.us. It'll aggregate weather information and harness the wisdom of crowds to see if they can make better weather predictions than the experts.

Tyler Cowan predicts Ben's effort will fail:

how many government agencies already work at predicting the weather?, or in other words the crowd is already in place.

I'm not so sure. If the weather report says, "chance of rain in Toronto," and the crowd in Mississauga is getting wet, I take the umbrella. Moreover, when I'm planning a trip to Vancouver, I look for average temperatures as a means to an end: I want to know what to pack. It's much better to know that everyone is wearing a scarf. The genius of Ben's site is in removing the middleman -- most of us want a weather report that's good enough to keep from looking like a dolt. And as long as we're doing what everyone else is doing, we've done it. If we're all wet, at least we're all wet together.

i in ur hed, wastin ur time

O, HAI!
It's probably too late to mention this in a hip way (if anything having to do with the Internet can ever really count as "hip"), but the LOLcats phenomenon just seems to keep expanding. Already, linguists are studying it; one day, perhaps a thesis will be written about LOLcats... in a LOLcat dialect.


These kitties are getting out of hand--they can code now:

HAI
CAN HAS STDIO?
I HAS A VAR
GIMMEH VAR
IZ VAR BIGGER THAN 10?
YARLY
BTW this is true
VISIBLE "BIG NUMBER!"
NOWAI
BTW this is false
VISIBLE "LITTLE NUMBER!"
KTHX
KTHXBYE

Scary.
KTHXBAI

words

• Postmodernism annoys me. Just one example: the "smirking forceps of quotation marks." "Smirking forceps" is a better descriptor than "scare quotes." If anyone was ever scared off by punctuation, it wasn't a postmodern. Postmoderns are in love with them. After all, there's no better way to indicate sophistication than to smirk.
• Contronyms, words that are their own antonym, amuse me (e.g. "strike" means hit, except in baseball, where it's a miss).
• Technological neologorrhia annoys me. Neologorrhia is my neologism for the flood of new words that seems always to accompany new technology. "Neologorrhia" doesn't count, because (1) I invented it and (2) it's postmodern neologorrhia, not technological neologorrhia. It'd be hypocritical of me to complain about that, after trademarking postculturalism in my last post. Or would that be just appropriately postmodern enough?
  

the future is now

Geoffrey Nunberg wrote in “Farewell to the Information Age” that “nothing betrays the spirit of an age so precisely as the way it represents the future.” Two mistakes futurists make, he continues, are to extend some current innovation to its logical end or to unintentionally naturalize some assumptions about culture. His example is a picture in a 1950 issue of Popular Mechanics. An apron-clad woman sprays down oddly-shaped plastic furniture with a garden hose—in her living room. Plastics, yes, Mr. McGuire’s “one word” to Benjamin in The Graduate, is undoubtedly the former of the futurist mistakes, while the unwitting naturalization of “woman’s work” in the image is the latter. Nunberg hopes to avoid these mistakes in his own futurism. Nunberg writes on the future of “information” in the era electronic. For the most part, Nunberg is masterful—and surprisingly prescient. He wrote in 1995, and many of his predictions have already come to pass.

Nunberg argues that information is dead. Information requires print, because it is through the physical and social institution of print that information came into being. The constrained, valuable column inch of the printed page helped to create the material character of information—that uniform, morselized, quantifiable entity. The social history of its development, and the institutions that grew up to support it contributed to and codified its semantic qualities: objectivity and autonomy. The example Nunberg uses to illustrate his point is, ironically, non-print. Imagine stepping into a rental car for the first time, turning on the radio and hearing that the Red Sox lost to Toronto. “You accept what you hear without interrogating it,” says Nunberg, “in virtue of the form of language that expresses it and the kind of document that presents it.”

In the age of the Internet, Nunberg is certain, these strictures will break down. Nunberg foresees words sprawling across undelimited web pages, no longer tightly constrained in expensive column-inches. He anticipates the growing concern with sources, the changing meaning of what it is to be an author, or journalist, or photographer, or professional. Strikingly, for 1995, he foresees discussion-based forms of collaboration. A linguist, Nunberg wonders at the new, twisted meanings of words when applied in this new context. Would a Derridean speak of the hyperlink as actualizing intertextuality to the point of eradicating all boundaries between texts? If so, would she realize the anachronism inherent in the very idea of intertextuality? In a realm where there can be “intertextuality without transgression,” intertextuality is emptied of its old meaning.

Perhaps because he is so worried about avoiding the two mistakes of the futurist, Nunberg falls into the trap of the presentist—he misidentifies information, that very entity he hopes to define. His example of hearing a score on a radio belies his mistake. For who among us trusts any printed source without interrogation? Perhaps we trust the sports scores and the weather (insofar as we trust any weather report). If so, then information is far more limited than Nunberg makes it out to be. Let me repeat what Nunberg says of the radio: “you accept what you hear without interrogating it... in virtue of the form of language that expresses it and the kind of document that presents it.” True enough—interpretation of sports scores and weather reports is largely about formatting, not about authorship. Besides these, though, what else do we trust?

Are we now so embedded in the interrogative electronic era that we have now altered how we read print sources? Am I simply a jaded academic, cynically picking fights over the supposed “objectivity” of the media? Or is Nunberg just plain wrong?

YouTube + science

YouTube has a 3-minute clip of Lives of a Cell, David Bolinsky's 3-D animation of the interior of a white blood cell (via Wired). Three points worth mentioning:

1. the full version will be featured on PBSs 22nd Century
2. word has it, the Wachowski brothers want to feature some of the animation in a remake of Invasion of the Body Snatchers
   
3. although the cells are abustle with activity, 90-95% of molecules are (visually) left out of the animation

It's unfortunate that journals can't show us animations like this--science might be much more popular.

How many bits is that tree?

Brian Cantwell Smith, rumored inventor of recursion, tells me a colleague at Xerox PARC once wondered, "How many bits is that tree?" The question is striking for being posed at all--it requires an unusual metaphysical commitment, to say the least--but moreover because it was posed seriously, as though it was a meaningful question.

There is a notion being bandied about in virtually every discipline which, in its own way, makes similarly overreaching claims on ontology. That notion is information. It is not clear just what information is. Perhaps St. Augustine would have said, “What is [information]? If no one asks me, I know; but if I wanted to explain it to one who asks me, I plainly do not know.”

But how many bits is that tree? Those of us with a computational bent are likely to think that there might be a minimal description of any given element of the universe (such as a tree), and this minimal description can be measured in bits. Wolfram certainly thinks so, and Greg Chaitin's algorithmic independence seems just suited for drawing lines around objects like trees. Nevertheless, the tree is more than its description. How many bits are in that tree seems a different question than how many bits is that tree.

geekvision: seeing the world as information

I don’t know when it became commonplace to see the world as information. I’m sure the idea predates computers, probably by a few millennia. But I think it has only become popular—wildly popular—recently, maybe as recently as just the past few decades. Seeing the world as information is still not a majority thing, it’s a quirk reserved for the qwerty crowd: the geeks (nerds, not so much. Just the geeks). Back in the early 1800s, there was a vogue of information gathering beyond anything seen before—this was the age of the rise of the actuarial table, the science of statistics and of sociology. The scientist D’Alembert, upon entering a room on a visit abroad would whip out a pocket rule with which to gather measurements of paintings (subject and artist were apparently irrelevant). This is not the sort of “everything is information” I’m talking about, though. I mean that geeks today use the very concept of information as their primary metaphor for describing. I suspect that attempting to describe this concept of information will necessarily fail, and indeed will be misleading, because my description would be necessarily formal (I would cite Shannon, Church, Turing, and Godel), while the idea is purely intuitive and possibly not conscious. Oh, sometimes the concept floats to the surface—the study of heritable traits is about decoding DNA, finding out the information hidden in the genes. Indeed, this aspect of biology is so emphasized that most of us ignore development and morphology. But in general, I think, the information conceptual schema stays in the background.

Nevertheless, it has had a significant impact on our way of life. This is in part because of who geeks are and what they do. Geeks have had a pretty successful couple of decades lately. They’re rich and powerful even if they’re not obvious about it (though they’re getting pretty obvious now that they can replace their model space ships with real ones).