Web Roundup: Links for April

by

Anki Tips: What I Learned Making 10,000 Flashcards

by

anki-cover Edit: Hey guys! This has proved to be one of the most popular articles on the site, so I’ve created a supplemental download on the 5 biggest Anki mistakes people make and how to avoid them. Enter your email below (or on any of the forms scattered around the site), and I’ll send it to you, along with ~2 emails per week on research backed techniques for achieving anything.

Here’s the form:


 

anki

If you don’t know what Anki or spaced repetition is, start by reading gwern’s excellent introduction.

This month, I created my ten thousandth virtual flashcard. When I started using Anki, I worried that I’d do the wrong thing, but decided that the only way to acquire Anki expertise was to make a lot of mistakes.

Here’s how my Anki usage has evolved.

Why questions

Cards that answer the question “Why?” are more valuable than factual cards. (See also this post.) It’s easy to memorize that QuickSort has a lower bound of O(n lg n), but better to know why it has such a lower bound, and even better still to understand why comparison-based sorts can’t be faster than O(n lg n).

Of course, it’s best to know all of these.

My emerging perspective here is that it’s important to understand all the context of an idea to really know it. How it emerged, how to invent it, what it’s for, and so on.

Images

My original Anki decks were all words. Now, I lean on images as heavily as possible. I find, at least for my sort of mind, that most of understanding something is learning to visualize and manipulate it mentally. Google image search is one of my first stops. In a pinch, I also make crude drawings of my own. As long as it captures the main idea, it’ll do:

crude-ankiAs an unintended consequence, my thought itself has shifted towards more imagery. The repetition makes an image representation of a concept more available mentally than its equivalent in words.

Connections

The biggest problem with Anki is the tendency for cards to become disconnected, so that a lot of knowledge is only available with the right cue and, even then, it’s a sort of impoverished thing.

I’m not aware of any silver bullet for this problem, but I now construct more cards that enforce links between knowledge. I might ask, “How is this concept different from that concept?” Or how a concept explains something from my personal life, or what an idea is reminiscent of.

The main limitation here is the general unavailability of a piece of information. With the right cue, I can recall it, but it’s not as if I can just sit down and brain dump every single one of my memories.

Mnemonics, at least the method of loci, are a bit better in this regard, as I can think myself to a place if I need to retrieve something.

Single deck

Currently, I have decks organized by topic and subtopic. However, I now think this is backwards. Given Hebbian learning — neurons that fire together wire together — I’m convinced that mixing everything is superior.

Take the production of insight, for instance. I find that insight often arises when two ideas that have been recently activated in memory collide and I think, “Oh, wait, that’s related to that.”

If everything is carefully partitioned, you limit opportunities for this serendipity. Topic organization says “ideas about computer science don’t belong with those about economics,” except applying ideas across disciplines is precisely where the insights are likely to be most fertile.

Two-way connections

Here’s a mistake I’ve made a couple of times. You’ll be reading a text and it’ll define something, like the Martin-Löf-Chaitin thesis, and you’ll create a card saying, “What’s the Martin-Löf-Chaitin thesis?”

Then, sometime in your life, you’ll be sitting and thinking, “Hey, what’s that mathematical theory of randomness called?” and you won’t know, because you didn’t make a card like that, and your mind only learned the connection one way.

This has also happened with cuckoo hashing and I’m sure other things too, so now I make more of an effort to learn something forwards and backwards, like “What’s cuckoo hashing?” and “What’s the name of that probabilistic version of hashing?”

In general, poor models of how memory and mind work hinder Anki effectiveness. You might think, hey, knowing something is all there is to knowing. Wrong. A lot of knowing is creating different cues and representations of that knowledge so that you can recall it when needed.

A great deal of an effective knowledge base is engineering it so that it’ll be useful in the sort of situations where you expect to apply it.

Adding whatever

My philosophy when I started using Anki was to add whatever, to just adopt a trifling barrier to entry. I didn’t worry about whether a fact is useful or not or anything like that. If something appealed to me, I’d add it.

This core is remains. The main change this philosophy has undergone is to shift away from setting a specific study time and making cards during that study time. Instead, I add anything interesting, regardless of when it happens, and random connections and insight that occur to me throughout the day.

For example, each morning I go through my RSS reader and check the news for the day. Whenever I come across something interesting or insightful, I add it.

Or here’s a common hangup people have, and that I had, when starting with spaced repetition. It’s the question, “What ought I memorize?” and people think, well, maybe the presidents or something, because that’s what they’ve associated memorization with.

It’s the wrong question. Ask “What’s interesting?” and start ankifying that.

People also really like it when you can recall minutia about them, too, which is sort of fun. If someone mentions their favorite type of cheese, or a pet’s name, make it into an Anki card. It’s like free social points. Memorizing birthdays works.

Thoughts on the value of Anki

I remain, more than a year later, enthusiastic about Anki. The honeymoon period is over and I still think it’s awesome.

Anki-powered studying has become my new normal. Whenever I regress to trying to memorize something spontaneously, without software assistance, like command line flags or some bit of HTML, it’s frustrating. It feels like something is wrong, like it ought to be so much easier, because with Anki it is.

Which is not to say that Anki is a panacea. Just as it’s a good idea to diversify your stock portfolio, it’s a good idea to diversify learning methods.

Further Reading

Creativity, Fan Fiction, and Compression

by

I’ve written before about the relationship between creativity and compressibility. To recap, a creative work is one that violates expectations, while a compressible statement is one that’s expected.

For instance, consider two sentences:

  • Where there’s a will, there’s a way.
  • Where there’s a will, there’s a family fighting over it.

I suspect you find the second more creative.

Three more examples of creative sentences:

  • When I was a kid, my parents moved a lot. But I always found them.
  • Dad always said laughter is the best medicine, which is why several of us died of tuberculosis.
  • A girl phoned me the other day and said, “Come on over, there’s nobody home.” I went over. Nobody was home.

Given that less predictable sentences are more creative, and less predictable sentences are less compressible, creative works ought to be less compressible than non-creative ones. And, indeed, I found some evidence for this in a previous experiment.

But that was not too compelling as it compared technical, repetitive works to novels. This time, I decided to compare very creative writing to normal creative writing.

Methods

The idea then is to compare the compressibility of amateur creative writing with that of experts. To accomplish this, I took 95 of the top 100 most downloaded works from Project Gutenberg. I figure that these count as very creative works given that they’re still popular now, ~100 years later. For amateur writing, I downloaded 107 fanfiction novels listed as “extraordinary” from fanfiction.net.

I then selected the strongest open source text compression algorithm, as ranked by Matt Mahoney’s compression benchmark — paq8pxd. I ran each work through the strongest level of compression, and then compared the ratio of compressed to uncompressed space for each work.

Analysis and Results

I plotted the data and examined the outliers, which turned out to be compressed files that my script incorrectly grabbed from Project Gutenberg. I removed these from the analysis, and produced this:

fanfic-graph1

Here the red dots are fanfiction novels, while the blue-ish ones are classic works of literature. If the hypothesis were true, we’d expect them to fall into distinct clusters. They don’t.

Comparing compressibility alone produces this:

fanfic-graph2

Again, no clear grouping.

Finally, I applied a Student’s t test to the data, which should tell us if the two data sets are distinguishable mathematically. Based on the graphs, intuition says it won’t, and indeed it doesn’t:

The p-value here is 0.1755, which is not statistical significance. The code and data necessary to reproduce this are available on GitHub.

Discussion

I must admit a certain amount of disappointment that we weren’t able to distinguish between literature and fanfiction by compressiblity. That would have been pretty neat.

So, what does this failure mean? There at least six hypothesis that get a boost based on this evidence:

  • Creativity and compression are unrelated.
  • A view of humans as compressors is wrong.
  • Human compression algorithms (the mind) and machine compression algorithms are distinct to the point where one cannot act as a proxy for the other.
  • Compression algorithms are still too crude to detect subtle differences.
  • Fanfiction is as creative as literature.

And so on and, of course, it’s possible that I messed up the analysis somewhere.

Of all of these, my preferred explanation is that compression technology (and hardware) are not yet good enough. Consider, again, the difference between a creative and a not-creative sentence:

  • Honesty is the best policy.
  • I want to die peacefully in my sleep, like my grandfather… not screaming and
    yelling like the passengers in his car.

The first is boring, right? Why? Because we’ve heard it before. It’s compressible — but how’s a compression algorithm supposed to know that? Well, maybe if we trained it on a corpus of the English language, gave it the sort of experience that we have, then it might be able to identify a cliche.

But that’s not how compression works right now. I mean, sure, some have certain models of language, but nothing approaching the memory that a human has, which is where “human as computer compression algorithm” breaks down. Even with the right algorithm — maybe we already know it — the hardware isn’t there.

Scientific American estimates that the brain has a storage capacity of about 2.5 petabytes, which is sort of hand-wavy and I’d bet on the high side, but every estimate I’ve seen puts the brain at more than 4 gigabytes, by at least a couple orders of magnitude. I don’t know of any compressors that use memory anywhere near that, and certainly none that use anything like 2.5 petabytes. At the very least, we’re limited by hardware here.

But don’t just listen to me. Make up your own mind.

Further Reading

  • The idea that kicked off this whole line of inquiry is Jürgen Schmidhuber’s theory of creativity, whichI’ve written up. If you prefer, here’s the man himself giving a talk on the subject.
  • To reproduce what I’ve done here, everything is on GitHub. That repository is also a good place to download the top 100 Gutenberg novels in text form, as rate-limiting makes scraping them a multi-day affair.
  • I similarly compared technical writing and creative writing in this post and did find that technical writing was more compressible.
  • For an introduction to data compression algorithms, try this video.
  • Check out the Hutter Prize, which emphasizes the connection between progress in compression and artificial intelligence.
  • For a ranking of compressors, try Matt Mahoney’s large text compression benchmark. He’s also written a data compression tutorial.

You Could Have Discovered Quantum Mechanics

by

Quantum mechanics is what you would inevitably come up with if you started from probability theory, and then said, let’s try to generalize it so that the numbers we used to call “probabilities” can be negative numbers. As such, the theory could have been invented by mathematicians in the nineteenth century without any input from experiment. It wasn’t, but it could have been… And yet, with all the structures mathematicians studied, none of them came up with quantum mechanics until experiment forced it on them. And that’s a perfect illustration of why experiments are relevant in the first place! More often than not, the only reason we need experiments is that we’re not smart enough.
—Quantum Computing Since Democritus

The chapter itself goes into more details. You should buy a copy. The author blogs.

The Creative Process Demystified

by

Jack Kerouac is a liar.

Okay, let me rewind. I don’t know how much experience you’ve had with creative writing types — pale, imaginative creatures — but let me tell you how they talk about Jack Kerouac. They say his name in sort of hushed, reverent tones, and whisper things like, “Can you believe that he wrote On the Road in one sitting?” Like great authors are some sort of gods. We, you and me, on this blog, we know better. There are no gods and his name is Richard Feynman.

Except Kerouac didn’t even write On the Road in one sitting. He spent three years writing pieces of it and, eventually, spent three weeks writing a first draft from that material. He then spent a couple of years revising that draft, which became On the Road. But this doesn’t make as good of a story, so instead Jack told everyone that he wrote it all at once because, as we’ve established, he was a liar.

Now, what’s the significance of this story? The answer is incrementalism: Great works are the result of a process of incremental growth and improvement.

Consider the Christian creation native. In the beginning, God created the heavens and the earth. Now, God is an omnipotent, all powerful dude, so presumably the heavens and earth are less impressive than he. The implicit assumption is that you need something complicated to create something else complicated.

We were more or less speculating in the dark with this narrative until Charles Darwin and Alfred Russel Wallace came along with evolution. It turns out that something as complex as the human mind is not a miracle from on high, but the result of millions of years of selective pressure.

Or, to put it another way, simple things grow into complicated things if you expend enough energy on them.1

Creating something is more like evolution than like God creating the heavens and the earth. It’s not a process of flipping a switch, or letting it all fall out of your mind. You have to grow a book or a blog post. Write a rough draft and filter it into something better. Hill-climb until the quality is twice what it was before.

No magic

There is nothing magical behind the creative process. Sure, authors and poets will sometimes wax romantic about writing and play up the mystery, but this is misdirection.

Look, I can do it, too:

Writing is, in its essence, the soul’s interpretation of the signs that are revealed to it. The ability to write well, the gift of a soul, is something innate. One must be born into it. Just as not all men possess the capacity for reading tea leaves or interpreting the whims of the spirit realm, few are born with that devil’s touch that brands one writer.

Except, you know, that’s all bullshit. There’s no magic. You get an idea. You think about the idea. Maybe write an outline. Write a rough draft. Delete a lot. Write another draft. Repeat until good. With a liberal sprinkling of self-loathing and lots of doubt, that’s creativity.

Indeed, to create something good:

  1. Come up with an idea.
  2. Create a rough version.
  3. Refine it until it’s good.

That’s it. That’s how books are written. I mean, sure, there are some specifics, like how to keep everything organized and whatever, but this is the gist of it. Create a prototype and then refine it over and over. That’s incrementalism. That’s what I mean when I say that great works are grown. It’s not magical. It’s algorithmic. Follow these instructions and you’re golden.

Most of the difficulty in creating something worthwhile is not because of the complexity of the process, but rather the difficulty in maintaining effort over time. We get bored and frustrated and quit. The trick to writing or creating something great is figuring out how to tame those tendencies and continue exerting yourself in pursuit of that goal.


1. Evolution, however, is not a race towards greater complexity. Single-celled organisms rule the world.

Web Roundup: More Links for March

by

Creativity, Literature, and Compression

by

But first, a joke:

I was at a bar last weekend, chatting with this woman. She was decent looking. There was a lull in the conversation, so I say to her, “Hey, I’ve got this talent. I can tell when a woman was born after feeling her breasts.” She doesn’t believe me at first, but after a minute or so, she comes around. “Go on, then,” she says to me. I feel her up a bit before she gets impatient. “Well, when I was born?” she asks. So I tell her — “Yesterday.”

Dissecting and killing the joke

What’s funny about that joke? The surprise. First, there’s the set up. It’s titillating, and listeners start anticipating: this is going somewhere. And then — punchline! Outta nowhere, or at least that’s what it feels like. Cue laughter. This shock, this violation of expectation, is what comedy’s all about.

Here’s another one: “I’m not a member of any organized religion. I’m a Jew.” If the sentence had instead been, “I’m not a member of any organized religion. I’m an atheist,” there would be nothing at all funny about it. George Carlin’s, “If you can’t beat them, arrange to have them beaten,” follows the same pattern.

Brains are sort of anticipation engines and, when you violate those expectations, well, that’s comedy. It’s the difference between something original and something not. If Carlin had said, “If you can’t beat them, join them,” I wouldn’t be talking about him. It’s boring, cliched. It’s not creative.

Creativity is about violating expectations.

Anticipation is compression

Anticipation and prediction are the same thing. When I drop a ball, I anticipate and predict that it will fall to the ground.

Now, let us imagine a program that can take in a few facts about you and then predict with certainty what it is that you’re going to say. In such a case, the machine wouldn’t need to remember anything about you except those few facts. If it needs to know your opinion on something in the future, it can take those facts, run them through its internal predictor, and regenerate your opinions.

You, as a human, sort of already do this. For instance, if I tell you how I lean politically, you might not need to know my stance on anything — you might be able to anticipate it. So instead of storing, “The author’s opinion on Serious Political Topic X,” in long term memory, you could just remember, “The author is a Blue.”

This difference between remembering everything and remembering just a few details is compression. It follows, then, that when you can predict something, you can compress it.

Given then, that:

  1. Creativity is about violating expectations.
  2. That which can be expected can be compressed.

I would expect that creative things are less compressible than non-creative things. Do creative books compress less than non-creative ones?

That’s what I want to find out.

Methods

The idea, then, is to take works that are creative and non-creative, compress both, and observe whether the non-creative books are more compressible. Given the theory fleshed out above, I expect the non-creative works to be more compressible.

Sorting books into creative and non-creative buckets is, by its nature, a subjective task. I attempted to grab from the most obviously creative and non-creative works. In practice, this tended to blur the line between non-creative and boring. The most mind-numbing works, I figure, are the least creative.

Creative works:

  • Alice in Wonderland
  • Godel, Escher, Bach: an Eternal Golden Braid
  • Through the Looking Glass
  • Flatland
  • Beyond Good and Evil
  • Emerson, First Essays
  • A few other popular novels on Project Gutenberg.

Non-creative works:

  • The Berne Convention
  • RFC 4880
  • IRS Publication 557: Tax exempt status for your organization
  • ITunes User Agreement
  • Patent 8,322,614, “System for processing financial transactions in a self-service library terminal”
  • The Affordable Care Act

I took each of these works, ran them through the xz compressor — the strongest general purpose compressor in wide circulation, as far as I know — and then compared the “compressibility” (ratio of uncompressed to compressed data) of the two classes of files. The comparison was done with R.

Analysis and Results

Before anything else, I plotted the compressibility of the data using a dotplot, and colored each by work as creative or not. The results are visually striking:

compressed-literature-dotplot

You will notice that the works fall into two distinct clusters. Creative works (black) are less compressible than non-creative works (red), which is what I would suspect given that my hypothesis is true.

My statistics-fu is weak, but I think the Student’s t-test is the right tool for the job here. This calculates the p-value that the two groups are different, which comes out to 0.00001488 or, if the computer could speak, “I’m near certain that the non-creative group is more compressible than the creative group.” (That level of certainty is almost certainly inappropriate, though. In a trial of 10,000 analyses like these, I screw up more than one of them.)

Limitations

Let’s dig in a little deeper to the creative works:

This is sorted from most compressible to least, implying that Jekyll and Hyde is the most creative novel of those tested, while Godel, Escher, Bach is the least. I find this unlikely.

Indeed, if I plug in Moby Dick, I get a ratio of .3353, or less compressible than Alice in Wonderland, Breakfast of Champions, and others. Now, I’ve read Moby Dick and it’s a terrible, boring affair. I much prefer Godel, Escher, Bach or Alice in Wonderland. And internet reviewers largely do, too.

So it seems that compressibility can classify novels from technical works, but it’s not — at least using xz — possible to separate very creative works from just creative works.

Discussion

So, the theory predicted that non-creative works would be more compressible than creative ones, and that panned out. This is far from confirmation of the model, but it’s still evidence, and I’m pretty confident that the average novel is less compressible than the average piece of technical work.

It would be much more impressive if this could distinguish more specific degrees of creativity. If I compared some of the novels produced by first time authors (or bad fan-fiction) to those on the Modern Library’s top picks and it found that the Modern Library picks were more creative, well, that’d be neat. (Maybe I will try this out in a future post.) We can imagine such a technique becoming more and more powerful — to the point where it can distinguish between the relative merit of different works by the same author.

The limiting factor here, of course, is the power (or intelligence) of the compression technology. The compression algorithms that we all use are not that complicated. I can feed them sensory input and they won’t compress it down to the laws of physics. Instead, they’re relatively crude-but-effective attempts at deduplication, which means that they’re an imperfect measuring sticks for how creative something seems to a human.

For instance, if I feed a compressor a cliche or a clever play on that cliche, the compressor doesn’t have the intellectual context necessary to ding the cliche. If I could, instead, train an algorithm on a huge corpus of English text, of the sort that Google possesses, I’d be able to better construct a compressor that’d evaluate originality.

Even then, there are theoretical limits on this. I could feed a compressor random input, which cannot be compressed, but that doesn’t mean that there’s anything of interest to humans. And we can wonder: how much can word alone, surface level characteristics of text, be representative of creativity? At some point, a sufficiently intelligent compressor must understand the content, too.

In that final sense, humans are the ultimate compressors — at least for now.

Further Reading

Mike Tyson and Steroids

by

tyson-at-13This is a picture of Mike Tyson at age 13. Or at least that’s what the Daily Mail says. I’m skeptical because I sure as hell have never seen a 13 year old that looks like that.

Here’s Mike at 14. Still big, but maybe a little more reasonable:
tyson-at-14By that point, he’d already been boxing for two years. At the age of 12, he was able to bench more than 200 pounds:

At 12, Tyson was arrested for purse snatching and sent to the Tryon School for Boys. He soon met Bobby Stewart, a counselor and former boxer who saw in Tyson a pugnacious kid who had grown to 200 pounds and could bench press more than his weight.

The most popular “explanation” is that Mike Tyson is some sort of genetic freak. He just had a lot of natural potential and that’s why he looks like that. In general, though, the phrase “because genetics” sounds a lot like “because magic.”

What’s more likely: Tyson was a kid with a one-in-a-million natural muscular physique, or that he was on the juice? I would give someone 10 to 1 odds that Mike used steroids at least some point in his professional career, and maybe as young as the age of 13.

This is even less surprising if we consider the rates at which teenagers are abusing sex hormones. From the Palo Alto Medical Foundation:

Five to 12 percent of male high school students and 1 percent of female students have used anabolic steroids by the time they are seniors. But, you know, still. Steroids at 13? Ah, but you forget Mike’s background:

Tyson, now 47 and retired, described his ferocious appetite for drink and drugs that dated back to trying cocaine at the age of 11 and first being given alcohol as a baby in New York.

So, even at age 11, Mike wasn’t a stranger to hard drugs. I’m willing to concede, though, that Mike might not have abused steroids in his early teens. Perhaps the two pictures above are taken at a flattering angle, dated incorrectly, or something else.

That said, I’m still confident that Mike was on the juice at some point in his professional career. From Wikipedia:

By 1990, Tyson seemed to have lost direction, and his personal life was in disarray amidst reports of less vigorous training prior to the Douglas match… Contrary to reports that Tyson was out of shape, sources noted his pronounced muscles, absence of body fat and weight of 220 and 1/2 pounds, only two pounds more than he had weighed when he beat Michael Spinks 20 months earlier.

So, I’m supposed to believe that he was 220 pounds of lean muscle at a mere 5’10”? Give me a break. These stats are not attainable without performance enhancing drugs. (Although, certainly, one might argue that Iron Mike was not that lean.)

Oh, and don’t get me started on drug testing:

Confessing he had taken “blow” and “pot” before the bout, he said: “I had to use my whizzer, which was a fake penis where you put in someone’s clean urine to pass your drug test.”

Or get this. Here’s what Mike had to say when asked, “What would you do differently if you could start training all over again?”

Growth hormones. I would’ve used the growth hormones like the rest of the athletes.

Here he is in another interview:

No, no. All the fighters are on it, the ones that can afford it are on it. That’s my opinion only, I haven’t seen nobody do it but it’s common knowledge.

Steroid usage in the large

Now, I want to step back for a moment. My goal here is not to pick on Mike Tyson, who possesses a certain je ne sais quoi, but:

  • To pick on those (most of the public) who are too ready to believe that most muscleheads are genetic miracles and not a walking meat billboard for steroid use.
  • To point out the prevalence of steroid use at the elite level.

In pursuit of my second point, consider that the livelihoods of star athletes are dependent on their ability not only to perform, but their ability to perform better than everyone else. Albert Pujols 10-year contract, for instance, is worth $240 million dollars. Alex Rodriguez was the highest paid player in the MLB last season, earning $28 million. The median salary for a MLB player, in contrast, is around a million. We’re talking a $27 million dollar incentive to find some sort of undetectable super drug that transforms a median player into the best player.

And that’s just baseball. Forbes’ list of the top paid athletes has about 25 players in golf, tennis, football, even cricket, earning more.

How powerful are performance enhancing drugs?

Of course, it’s not at all obvious that steroids can transform someone from a pretty good baseball player into one of the best. Perhaps, you might think, steroids are not all that effective. The New York Department of Health would have us believe that “[S]teroids cannot improve an athlete’s agility or skill.”

Here’s how an HIV positive man describes testosterone replacement:

At that point I weighed around 165 pounds. I now weigh 185 pounds. My collar size went from a 15 to a 17 1/2 in a few months; my chest went from 40 to 44. My appetite in every sense of that word expanded beyond measure. Going from napping two hours a day, I now rarely sleep in the daytime and have enough energy for daily workouts and a hefty work schedule. I can squat more than 400 pounds. Depression, once a regular feature of my life, is now a distant memory. An HIV patient like the essayist above would probably inject between 150 to 200mg every two weeks. The higher end of that range would bring someone to the top of the typical male level. A first steroid cycle for an athlete might be around 1000mg ever two weeks — more than four times as much.

But what does that translate to, you know, physically? A common myth spread by gearheads who really out to know better says:

Gear [steroids] is not a magical pill. It makes hard work more rewarding, it doesn’t give results for doing nothing. But how about some evidence? Okay!

One study placed men into four groups: exercise with testosterone, exercise with placebo, no exercise with testosterone, and no exercise with placebo. The findings? Men who injected testosterone gained strength and lean muscle mass even without exercise:

Among the men in the no-exercise groups, those given testosterone had greater increases than those given placebo in muscle size in their arms (mean [±SE] change in triceps area, 424±104 vs. -81±109 mm2) and legs (change in quadriceps area, 607±123 vs. -131±111 mm2) and greater increases in strength in the bench-press (9±4 vs. -1±1 kg) and squatting exercises (16±4 vs. 3±1 kg).

Dudes not exercising added 20 pounds to their bench press, while those that exercised and juiced added 50 pounds.

Here’s another study:

Increase in one-repetition maximum leg press strength averaged 17.2% with testosterone alone, 17.4% with resistance training alone, and 26.8% with testosterone + resistance training. To put it another way, sitting around and doing nothing while on testosterone will make you as strong as people who actually train with weights. (These subjects were dosed with 1000mg weekly.)

And that’s just vanilla testosterone. We aren’t even talking about the fun steroids, like trenbolone, which is used to fatten up livestock but much loved by bodybuilders everywhere. It’s literally a steroid intended for bulls — you know, giant muscly cows with horns and shit.

Lest you think I’m citing too much from non-athlete populations, from a review of the use in athletes:

Strength gains of about 5–20% of the initial strength and increments of 2–5kg bodyweight, that may be attributed to an increase of the lean body mass, have been observed.

Rademacher et al. reported one study not reporting strength improvements are that in male canoeists, 6 weeks of Oral-Turinabol administration improved strength and performance measured by canoe ergometry with 6% and 9%, respectively. At the 2012 men’s 1000m kayak single, 6% performance more than separates a last from first place finish, and kayaking is not even a strength sport.

I should point out, too, that one additional benefit of steroid use is that they reduce recovery time and thus training time. Ignoring the performance benefits, an Olympian would still take steroids, as it would allow them to train maybe twice as often as an opponent not on them.

The prevalence of performance enhancing drugs among elite athletes

So, we’ve established that:

  • Athletes face millions of dollars worth of incentives to juice.
  • Performance enhancing drugs are very effective at, well, enhancing performance, even among trained athletes.
    But while all this is suggestive, maybe elite athletes do play by the rules — either out of moral goodness or fear that they’ll get caught. Maybe the testing infrastructure is good enough.

So what does the actual rate of steroid use among the athletic population look like?

From one anonymous survey: > From the athletes questioned, a number of 64 (85.33%) accepted that they did take doping pharmacological substances.

From an evaluation of doping among Italian athletes: > Over 10% of athletes indicated a frequent use of amphetamines or anabolic steroids at national or international level, fewer athletes mentioning blood doping (7%) and beta-blockers (2%) or other classes of drugs.

Another anonymous response found that 7% of athletes admitted to doping, in contrast to the .81% caught by testing:

Official doping tests only reveal 0.81% (n = 25,437; 95% CI: 0.70–0.92%) of positive test results, while according to RRT 6.8% (n = 480; 95% CI: 2.7–10.9%) of our athletes confessed to having practiced doping (z = 2.91, p = 0.004).

From a confidential survey of former NFL players:

The high-water mark for steroid use occurred in the 1980s, when about one in every five players, 20.3 percent, said they had tried the drugs. Use declined in the 1990s and beyond to 12.7 percent of players, the researchers reported.

I’m a bit skeptical that the 10% figure is useful as anything other than a lower bound. If you just ask people at the gym about their steroid use, for instance, you get much higher rates: > 160 responses were received, a 53.3% response rate. Of the 160, 62 admitted having taken steroids (38.8%).

The Tour de France, for instance, has abuse rates much higher than 10%:

Scientists estimated at least 80 percent of riders in the grand tours of France, Spain and Italy were manipulating their blood. It became as routine as “saying we have to have air in our tires or water in our bottles,” Armstrong told interviewer Oprah Winfrey this January, when he finally confessed, after years of lawyer-backed denials, that he doped for all seven of his Tour wins from 1999-2005.

The NY Times reports that more than a third of top finishers have been caught. The actual abuse rates must be higher.

Since 1998, more than a third of the top finishers of the Tour de France have admitted to using performance-enhancing drugs in their careers or have been officially linked to doping.

What’s a man to believe?

So, what are the actual abuse rates among elite athletes? My subjective feeling is more than 10 percent and probably less than 70. I suspect that most athletes have tried them at least once, but chronic use is probably less — maybe around 30 percent, but I’m uncertain. Given that those at the top experience both more pressure and enhanced performance, I suspect that the best players make up a disproportionate portion of abusers.

If you enjoyed this, check out the movie Pumping Iron!

The Stable Marriage Problem Explained

by

You are out in a thunderstorm. You look up, at the rolling thunderheads painting the sky, and wonder, “Why am I here? What’s the point of all of this? What difference can I make in a world of 7 billion?”

Your weekly scheduled existential angst is interrupted by a flash. It’s lightning, six-ish bolts. The yellow branches cross and, for a moment, spell out your name. “What are the odds?” you wonder.

It’s not a sign, though. You’re not falling for that one. Your worn copy of Dawkins has earned you that much. The mind, you know, has a tendency of seeing patterns where there are none.

You soon tire of the diversion and go back to fretting about existence. At least until a boom interrupts your reverie. You look up again. The clouds are parting.

You wonder if this is some sort of freak weather system and why, exactly, you thought it would be a good idea to be out in a thunderstorm.

Light filters through as the clouds continue to part. A shy blue sky reveals herself. Trumpets sound. There are winged creatures in the sky. A man in white floats down from the heavens.

You figure it’s a brain tumor — hopefully benign.

The man approaches you and says, “There’s been an administrative mix up.”

Fast forward an hour. It’s explained to you that Nietzsche was almost right. God isn’t dead, not exactly. He’s disappeared. Maybe on vacation or maybe this is part of one of his weird plans. (“Oh, God. I know the one. Luminous fellow. Always coming up with those crazy schemes.”) The angels, in their wisdom, figure that the best way to choose a new God to serve while the real one is out is via a lottery. They assign a number to every living soul and then choose one at random.

The angels, you see, are nihilists — and you are the chosen one.

First act as God

Now you’re God and, boy, if you thought you had responsibilities before, you’ve really got ’em now, and all the angels are waiting. Or, at least, you feel like they ought to be waiting. That’s how people on Earth behave after electing a new president — waiting for him to do something, anything.

But the angels aren’t really like that. They speak in Zen koans. Stuff like, “Do something. Do nothing. Be one hand clapping,” and “A cow is hanging from a tree by its teeth. A river rushes below. Does the cow mu?”

Mostly they just sit around, shrugging at each other. You figure they are sort of like what cats would be like if they were human-shaped and had wings.

Still, you suppose you ought to make some huge gesture to, you know, your people. Maybe not let them outright know that God is back — save a little mystery for further on in the relationship — but something.

So you ponder for a while and think, “Hey, what about that whole divorce epidemic going on? As God, I ought to be able to do something about that. Solve that romance thing.”

Your first act of God, you announce to the angels, will be to solve the Stable Marriage Problem.

The Stable Marriage Problem

Mathematics is a game of the imagination. There is but one rule: you may not contradict yourself — and I’m not even sure about that rule. Maybe there’s a neat looking branch of math waiting to be discovered where sometimes contradictions are allowed.

For every 100 human girls born, 106 boys are born, but the sex ratio for the global population is 101 males for every female — which means that, even if “true love” were a real thing, fated by God, some people would end up alone.

But with mathematics, I get to be the God, and I decide that I’m doing mathematics in a platonic reality where there is a man for every woman and a woman for every man.

Now consider these men and women living in this platonic mathematical universe. The women have some men they would prefer to be with — the Johnny Depps and George Clooneys — and the men have their own preferences — the Scarlett Johanssons and, well, more Scarlett Johanssons.

However, if God matches me with Scarlett Johansson, there is a problem. It’ll end in divorce. A smarter, better looking, more successful, all-around-wonderful guy will come along and, well, I’m out. And our twelve children will be devastated.

No, this will not do at all.

What I’m after is an equilibrium where no individual has a better option, a stable pairing. Like let’s say I’m with Casey Anthony — who is pretty cute but also maybe a murderess — and some other non-possible-murderess comes along who prefers me over her husband. If I prefer this new woman over the constant threat of death-by-angry-wife, then a better option exists.

An ideal couple is one with no options — people who cannot do any better than each other. If you marry someone, you both probably prefer someone else (at least when not blinded by infatuation), like Brad Pitt or Angelina Jolie. But none of those people want you more than their spouse, so you’re stuck together. And that’s true love.

Is there a stable pairing?

But it’s not obvious that there is always a stable pairing. Maybe there is some way to set things up so that there’s an infinite cycle — one where people keep getting divorced and then remarried and then divorced again. I can sort of imagine such a scenario. Look at all the people getting divorced and then remarried today.

Every introduction to this problem that I’ve read papers over this concern. It says, “Well, there is a stable pairing for every set of preferences. Just analyze this algorithm I’m about to give.” This is totally unsatisfying — I don’t want to just know something. I want to know how I could reinvent it.

But alas. I’m not that clever, so you will have to put up with the traditional style of presentation.

A first algorithm

Since you’re God, you can just use the nicest algorithm that you can invent, which would go like this:

  1. Given all men and women, generate all possible matches.
  2. Filter out all the non-stable matches.
  3. Pick your favorite one.

So let’s say you whip this up and you recognize that it has some seriously nasty algorithmic complexity. It grows exponentially and, on a conventional computer will take longer than the age of the universe for inputs larger than ~50.

But that’s fine, right? Now that you’re omnipotent, you’d think that you wouldn’t need to deal with any of this computational complexity nonsense. Except one of those damned angels chimes in and lets you know that even God isn’t allowed to use exponential algorithms for large inputs.

So, if we want to have stable marriages and more than 50 happy souls in our platonic mathematical reality, we’re going to have to come up with something better.

Gale-Shapely algorithm

For inspiration, consider how dating actually works. Bob approaches Alice and says something like, “Let’s hang out sometime.” or “Want to get dinner sometime?” or, for college students, the always popular, “We should watch Netflix together.”

Alice says “yes” if she finds Bob acceptable and “no” otherwise. Then they date until someone better comes along, at which point one of them “falls of out love,” which is really evolution nudging them to go pursue someone else. And the relationship ends. Usually, the woman is the rejecter and the man the rejectee.

So in the real world, the algorithm looks sorta like:

  1. A man asks out a woman he likes.
  2. The woman accepts or rejects the man.
  3. If the woman accepts the man, the woman dates the man until a suitor she
    prefers comes along. At this point, the relationship ends.
  4. The woman dates the new man and the old man asks out a new woman.

Rinse and repeat.

This is basically what the solution to The Stable Marriage Problem — the Gale-Shapely algorithm — looks like.

  1. Each man proposes to his first choice.
  2. Each woman (provisionally) accepts the best man who proposed to her. We could say that they’re engaged.
  3. Each non-engaged man proposes to his next-best choice.
  4. Each woman accepts the best man who proposed to her and rejects the
    rest. This may entail breaking off her current engagement and “trading up.”
  5. Repeat until everyone pairs off.

Looks sorta like dating in real life, huh?

Proving stability

How do we know that this algorithm produces a stable match?

Let’s consider two couples: Fred + Wilma and Barney + Betty. Is it possible that there is a better option? That Barney prefers Wilma over Betty and Wilma prefers Barney over Fred?

No. If Barney preferred Wilma over Betty, he would have proposed to her before Betty, as each man proposes in order of most preferred. In such a case, either Wilma accepted and later kicked him out because she traded up for Fred, or she didn’t accept him because she was already engaged to someone better — Fred or someone worse than Fred. In either case, it’s impossible that Wilma prefers Barney over Fred.

Smashing the Patriarchy

But wait! We’ve discovered a sexist algorithm. All the men are matched with the best possible woman from their point of view, while the women get their worst stable match! It’s stable only because all the men are too happy to agree to swap with any woman.

If we reverse the algorithm so that the women ask the men out, then we get a female optimal algorithm — “proving” that there’s more than one stable match.

How many possible stable matches are there?

Lots. It turns out that the upper bound is something like \(O(n!^{\frac{2}{3}}\)) and a lower bound of \(\Omega(2.28^n)\). Or, you know, lots.

This means that we can probably find a more egalitarian one than the male-optimal version. And indeed we can, except the algorithm is fairly complicated, relying on more knowledge of graph theory than I currently possess.

But as long as you’re omniscient, surely you can figure it out.

Further Reading

What Are Quantum Computers Used For?

by

The literal answer to the question, “What are quantum computers used for?” is well, nothing, since we can’t build them yet — but maybe you want to know the answer to the question, “What will quantum computers be used for?”

That I can answer.

There is a lot of magical thinking around quantum computers. That they’re the next big thing in computing, that they’ll replace classical computers, that they’ll be impossibly fast and small. There’s at least one quantum physicist who doesn’t know any better. Most problems receive no sort of “quantum speedup.”

Here’s what Scott Aaronson, a theoretical computer science guy who works on quantum computing at MIT, has to say:

To be clear, I think it’s entirely possible that I’ll see practical quantum computers in my lifetime (and also possible, of course, that I won’t see them). And if we do get scalable, universal quantum computers, then they’ll almost certainly find real applications (not even counting codebreaking): mostly, I think, for specialized tasks like quantum simulation, but to a lesser extent for solving combinatorial optimization problems.
—Quantum Computing Since Democritus

Sure, quantum computing will be useful, but no, they won’t enable us to replace classical architecture machines with fingernails that — I don’t know — pass the Turing test.

Here’s Aaronson himself in Scientific American with a bit more on quantum computers for simulation:

If quantum computers ever become a reality, the “killer app” for them will most likely not be code breaking but rather something so obvious it is rarely even mentioned: simulating quantum physics. This is a fundamental problem for chemistry, nanotechnology and other fields, important enough that Nobel Prizes have been awarded even for partial progress.

Problems fit for a quantum computer

On what sort of specific problems quantum computers will be used for, well, that’s a complexity class: BQP. A quantum computer — should they prove physically realizable — can outperform a classical computer at problems outside of P (another complexity class) but in BQP.

The main suspected problems in that class are:

  • Integer factorization (important for crypto)
  • Quantum-level simulations of physical stuff.

So, you know, what Aaronson already told us.

So, classical machines are here to stay. Quantum computers are not a silver bullet. Hard problems remain hard, or as Aaronson puts it (again from his Scientific American piece):

I predict that the hardness of NP-complete problems will someday be seen the same way: as a fundamental principle that describes part of the essential nature of our universe. There is no way of telling what theoretical enlightenment or what practical consequences might come from future application of this kind of fundamental principle.

Further Reading

  • Scott has a book, Quantum Computing Since Democritus. It’s excellent. I recommend it. You should buy a copy.