## Thursday, December 18, 2008

### Back by popular demand

My anxious readership has been flooding me with emails, demanding to know if I'm still alive and why I quit blogging. (Just kidding. Is anyone still reading this thing?)

A good chunk of my time has been occupied by administrative activity (job search), as well as personal matters (both good and bad).

I regularly attend two courses: one by Gideon Schechtman and one by Itai Benjamini.

Here is a nice "paradox" from Gideon's first lecture. Consider the 2x2 square = [-1,1]^2. In each quadrant, inscribe a unit circle. Let S_2 be the largest circle about the origin not intersecting any of the inscribed unit circles. Let R_2 be its radius; compute R_2 (it's easy!).

Now repeat the same in n dimensions: divide [-1,1]^n into 2^n orthants, inscribe a unit ball in each one, and let R_n be the radius of the maximal ball about the origin that does not intersect any of the inscribed balls. It shouldn't take you more than 2 minutes to come up with a formula for R_n -- the basic 2-dimensional intuition carries over to higher dimensions.

However, to anyone not familiar with high-dimensional geometric phenomena, something very surprising should happen. I won't give it a away here, but feel free to discuss in the comments. This sort of "paradox" probably has a name -- anyone know what it is?

## Saturday, October 25, 2008

### CS/politics -- dispelling the myth

I know that the blog's subtitle is "A math/computer science research blog", and that I haven't had a research post in months. I also know that this is the last place you want to turn to for politics.

The point of this post isn't really to weigh in on the upcoming US election -- I have nothing original to say about politics (it's hard enough to find original things to say in math/cs). My goal here is to dispel a false impression you might have gotten if you peruse math/cs blogs. You might naturally come to the conclusion that every mathematician/computer scientist is left-leaning and favors Obama.

You'd be wrong, though. One brave soul -- namely, Lev at Yale -- is willing to go against the current and argue in favor of McCain. Read his piece here. You owe it to yourself to step out of the echo chamber and hear a refreshing dissenting voice.

## Friday, October 3, 2008

### My exchange with Derbyshire

which he has kindly allowed me to post, is below. I'll address the comments in the previous post after Sabbath.

NRO diary
7 messages
Aryeh Kontorovich Fri, Oct 3, 2008 at 1:54 AM
To: gxnmvw7e
 Dear Mr. Derbyshire,your recent NRO diary has prompted me to write a blog post:http://absolutely-regular.blogspot.com/2008/10/non-apologia.htmlI assure you this is not hate-mail from an offended Christian!All the best,-Aryeh

John Derbyshire <> Fri, Oct 3, 2008 at 2:13 AM
To: Aryeh Kontorovich <>
 Thank you, Aryeh. I really didn't get any of that, though.>>there is absolutely no logical reason to prefer materialism over a belief in a higher powerBut there is: it's called "Occam's Razor"And why is there anything mysterious about humans caring for theirchildren? All the higher animals care for their children. It's calledn-a-t-u-r-e.Best,JD[Quoted text hidden]--John Derbyshire[Old website] http:\\www.olimu.com[New website] http:\\www.johnderbyshire.com

Aryeh Kontorovich <> Fri, Oct 3, 2008 at 2:26 AM
To: John Derbyshire <>
 Thank you for the prompt reply! I think the readers would be rather interested to see your reply -- may I post it in the comments?Re: Occam's Razor. This is perfectly fine and good for understanding and predicting natural phenomena (and indeed, is a perfectly natural hypothesis selection criterion in science, with some rigorous mathematical justification). For morality and ethics, the scientific method is woefully inadequate.Re: n-a-t-u-r-e. Not so fast. Natural human instincts (such as for food and sex) are easily subverted by modern technology to serve pure hedonism (cf. junk food, contraception, pornography). Why doesn't every atheist spend his life on a womanizing drug binge?Cheers,-Aryeh[Quoted text hidden]

John Derbyshire <> Fri, Oct 3, 2008 at 2:34 AM
To: Aryeh Kontorovich
 Sure. Use as you like. Just spell my name right.On Thu, Oct 2, 2008 at 8:26 PM, Aryeh Kontorovichwrote:> Thank you for the prompt reply! I think the readers would be rather> interested to see your reply -- may I post it in the comments?>> Re: Occam's Razor. This is perfectly fine and good for understanding and> predicting natural phenomena (and indeed, is a perfectly natural hypothesis> selection criterion in science, with some rigorous mathematical> justification). For morality and ethics, the scientific method is woefully> inadequate.Sez who? Seems perfectly adequate to me.>> Re: n-a-t-u-r-e. Not so fast. Natural human instincts (such as for food and> sex) are easily subverted by modern technology to serve pure hedonism (cf.> junk food, contraception, pornography). Why doesn't every atheist spend his> life on a womanizing drug binge?It's an empirical fact that they don't. Perhaps they are just betterin touch with their nature than you believers.The empirical fact is, in fact, even worse for your case than that.The less religion, the more morality. Religious nations (India,Nigeria, Mexico) have worse stats om crime, dysfunction, HIV, etc.that irreligious ones (Norway, Japan, New Zealand). The mostreligious subgroup of the US population is Af-Ams; the leasstreligious, E-Asian Americans. Guess which way the crime/HIV/etc.stats go?If it's morality you want, hang out with unbelievers!JD[Quoted text hidden]

Aryeh Kontorovich Fri, Oct 3, 2008 at 2:48 AM
To: John Derbyshire <>
 Sure. Use as you like. Just spell my name right.did I misspell your name in the post or correspondence? My sincere apologies (though I haven't been able to locate an error after several cursory glances). > Re: Occam's Razor. This is perfectly fine and good for understanding and> predicting natural phenomena (and indeed, is a perfectly natural hypothesis> selection criterion in science, with some rigorous mathematical> justification). For morality and ethics, the scientific method is woefully> inadequate.Sez who? Seems perfectly adequate to me.Well, the Nazis had used the scientific method to determine that a human ceases to live outside a certain temperature and pressure range. Scientifically, those were sound experiments. Science tells us what we can do. Morality tells us what we should do.It's an empirical fact that they don't. Perhaps they are just betterin touch with their nature than you believers.Actually, if you look at the demographics in America and Europe, you'll see that the believers make much better breeders than the non-believers. Say what you will about Muslims, but they certainly seem to be beating the rational, logical westerners at this game. The empirical fact is, in fact, even worse for your case than that.The less religion, the more morality. Religious nations (India,Nigeria, Mexico) have worse stats om crime, dysfunction, HIV, etc.that irreligious ones (Norway, Japan, New Zealand). The mostreligious subgroup of the US population is Af-Ams; the leasstreligious, E-Asian Americans. Guess which way the crime/HIV/etc.stats go?If it's morality you want, hang out with unbelievers!I certainly wasn't defending all religions as morally virtuous (I was merely defending religious faith from the conflation with superstition). As far as moral superiority, I am only prepared to defend Judaism.-AK

John Derbyshire <> Fri, Oct 3, 2008 at 1:08 PM
To: Aryeh Kontorovich <>
 On Thu, Oct 2, 2008 at 8:48 PM, Aryeh Kontorovich>> > Re: Occam's Razor. This is perfectly fine and good for understanding and>> > predicting natural phenomena (and indeed, is a perfectly natural>> > hypothesis>> > selection criterion in science, with some rigorous mathematical>> > justification). For morality and ethics, the scientific method is>> > woefully>> > inadequate.>>>> Sez who? Seems perfectly adequate to me.>>> Well, the Nazis had used the scientific method to determine that a human> ceases to live outside a certain temperature and pressure range.> Scientifically, those were sound experiments. Science tells us what we can> do. Morality tells us what we should do.You lose a point there for being the first to say "Nazi". Don't youknow the damn rules?>> It's an empirical fact that they don't. Perhaps they are just better>> in touch with their nature than you believers.>> Actually, if you look at the demographics in America and Europe, you'll see> that the believers make much better breeders than the non-believers. Say> what you will about Muslims, but they certainly seem to be beating the> rational, logical westerners at this game.Yes. Religious belief contributes to fitness (in the technicalbiological sense -- increases your genome's chances of passing on itsmaterial).And this proves ... what? That evolution is a haphazard business,that sooner or later heads in a wrong direction. Which any biologistcould have told you. Biologist's joke: "To a first approximation, allspecies are extinct." It's actually about 99.9 percent.>>> The empirical fact is, in fact, even worse for your case than that.>> The less religion, the more morality. Religious nations (India,>> Nigeria, Mexico) have worse stats om crime, dysfunction, HIV, etc.>> that irreligious ones (Norway, Japan, New Zealand). The most>> religious subgroup of the US population is Af-Ams; the leasst>> religious, E-Asian Americans. Guess which way the crime/HIV/etc.>> stats go?>>>> If it's morality you want, hang out with unbelievers!>>> I certainly wasn't defending all religions as morally virtuous (I was merely> defending religious faith from the conflation with superstition). As far as> moral superiority, I am only prepared to defend Judaism.That old thing? I'll give it another 3,000 yrs, then -- pfffft!--[Quoted text hidden]

## Thursday, October 2, 2008

### Non-apologia

One of my favorite commentators, John Derbyshire, is an unabashed atheist. Though his salvos are mostly aimed at his former faith of Christianity, I suspect that he is an equal-opportunity kafir. I admire Mr. Derbyshire for his razor-sharp wit and unwavering intellectual honesty, and so it is with great caution that I venture to point out a lapse in his reasoning. Namely, he seems to conflate religion with "rank superstition". (Again, technically the statement applies only to Christianity, but I doubt Mr. Derbyshire's judgement of, say, Jewish ritual observance would be any more flattering.)

As an observant Jew, I believe with perfect faith that the world was created by an infinitely wise and all-powerful Creator, who endowed men with souls and free will and who demands that we choose to behave in accordance with His laws, as revealed to us on Mount Sinai (the requirements are a great deal less exacting for non-Jews). But the point of this note is not to defend my beliefs or to try to gain converts. Rather, it is to attempt to understand the distinction between "superstition" and other -- "valid", "legitimate", "rational" -- beliefs. Merriam-Webster's definition of superstition is a good start: "a belief [...] resulting from ignorance [...] trust in magic or chance [...] a false conception of causation [...] a notion maintained despite evidence to the contrary". That certainly doesn't sound very attractive. So what's the antidote to superstition? Mr. Derbyshire doesn't really propose one, but if I might put words into his mouth for a moment, I would hazard positivism or materialism.

But of course, as any philosopher of epistemology will tell you, there is absolutely no logical reason to prefer materialism over a belief in a higher power. Recently, a very intelligent friend of mine (let's call him W) demanded a logical justification for my adherence to Judaism. I told him that every man must answer for himself the fundamental question along the lines of, "Is there meaning to life? Did a Creator create us for a purpose?"

In my experience, most atheists avoid a logically consistent and intellectually honest answer. Many of them go through life doing all the "right" things -- work, marriage, children -- yet if pressed, have a hard time justifying their actions. Childrearing is a major burden, which certainly cannot be justified on the basis of short-term pleasure. Yet I suspect many people have children out of some vague sense that they're "supposed to" -- without the conscious realization that they are fulfilling some greater purpose. Indeed, there are millions of atheists whose answer to the meaning-of-life question would be an emphatic NO. Yet examining the way many of these so-called atheists choose to live their lives, one can't help but wonder if they're actually scrupulously following some sacred text. How many of them have children? How many justify it solely based on Darwinian genetics?

I claim that such people are being less than intellectually honest. They have some vague sense of purpose in life, but are unwilling to admit that, as it would undermine their "atheist" credentials.

Who can blame them? A positive answer to the meaning-of-life question opens some intimidating doors. If we are created with a purpose, we must seek to discover this purpose and strive to fulfil it. That could entail hard work and major sacrifices!

"But isn't God just a story you're telling yourself for comfort?" my friend W asked. "No," I told him. "To me, this has the feel of compelling, undeniable reality."

How does any of know that we are not, in reality, just a brain in a vat? The short answer is that we have absolutely no way of knowing. One could just as well claim that positivist reality is a story we tell ourselves for comfort. And as long as we're choosing which stories to tell ourselves -- without any objective logical basis for any of them! -- we have to judge these stories by some other criterion than the scientific method. Indeed, there are lots of "stories" out there, and why I picked the "Judaism" one is a long story in itself. But let's dispense once and for all with the fallacious notion that religious belief is somehow illogical or irrational.

## Wednesday, July 9, 2008

Consider the standard PAC learning model. We have a concept class C over an instance space X, as well as a probability distrubution P on X. After observing a labeled sample of size m, and finding an f in C consistent with this sample, we will know that with high probability the generalization error of f is bounded by something like

(*) sqrt(d / m) + confidence term,

where d is the VC-dimension of the concept class C [the confidence term isn't the interesting part here -- it appears in all generalization bounds of this type, and goes to zero as 1/sqrt(m)]. Intuitively, this bound says that if we managed to explain the observations by picking a model from a "simple" class, we can be confident that our predictions will be good. Explanations by more complex models are less informative. In the trivial case, C= 2^X and VC-dim(C)=|X|
-- so achieving zero sample error tells us nothing about generalization error.

However, one might reason as follows. Suppose I receive a labeled sample and find a classifier f in C that achieves zero sample error. Now what's stopping me from re-defining my concept class? I'll define a new concept class C' = {f} that contains a single concept -- f! Its VC-dimension is trivially zero. As far as my prediction is concerned, it doesn't matter whether I learned using C or C' -- in either case, I'll pick the classifier f. But the VC-dimension of C might be large, giving me a poor generalization guarantee (*), while VC-dim(C') = 0, which is as good as things can be!

What's wrong with this reasoning?

## Monday, February 4, 2008

### Cheating on tests

Various youngsters share their favorite test-cheating techniques here. What struck me was the high overhead and low information content of their devices. All of their tricks have the capacity to hold a few words of text, or maybe a paragraph at best. Is this what exams in schools have become -- the rote regurgitation of a set number of words? Wouldn't it be easier to just memorize the darn words?