An Untrollable Mathematician Illustrated

[Qiaochu_Yuan]

This is great. I con­sis­tently keep want­ing to read the ti­tle as “Un­con­trol­lable Math­e­mat­i­cian,” which I’m ex­cited about as a band name.

[ryan_b]

Per­haps if we spec­ify a differ­ent rule that only solves the prob­lem of up­dat­ing on nega­tive in­for­ma­tion, you could have an “Un-Con-Trol­lable Math­e­mat­i­cian.”

[Hazard]

This was in­cred­ibly en­joy­able to read! I think you did a very good job of mak­ing it easy to read with­out dumb­ing it down. Though I’m not well versed in the core math of this post, I still feel like I man­aged to get some use­ful gist from it, and I also don’t feel like I’ve been tricked into think­ing I un­der­stand more than I do.

[Benito]

(this is so awe­some and it helps give me in­tu­itions about Gödel’s the­o­rem and how math­e­mat­ics hap­pens and stuff)

I didn’t parse the fi­nal sen­tence?

​Log­i­cal in­duc­tion (which is un­trol­lable but not ex­actly a Bayesian prob­a­bil­ity dis­tri­bu­tion) is still the gold stan­dard for log­i­cal un­cer­tainty, but per­haps the num­ber of de­sir­able prop­er­ties we can get by spec­i­fy­ing sim­ple sam­pling pro­cesses.

It feels like it should say ‘but per­haps the num­ber of de­sir­able prop­er­ties we can get by spec­i­fy­ing sim­ple sam­pling pro­cesses is X’ but is miss­ing the fi­nal clause, or some­thing.

Edit: This has been fixed now :-)

[abramdemski]

Right, whoops.

It should have said “… by spec­i­fy­ing sim­ple sam­pling pro­cesses will in­crease as we push fur­ther in the di­rec­tion Sam has opened up.”

[DanielFilan]

Fur­ther bug: I can now see both the old fi­nal image and the new fi­nal image.

[abramdemski]

Wow, that’s weird, I **don’t** see both when I try to edit the draft. Only in the non-edit­ing view.

[habryka]

Sorry for that, fixed it!

[Benito]

Wow. Oli’s on it.

[Benito]

I cu­rated this post be­cause:

• The ex­pla­na­tion it­self was very clear—a se­ri­ous effort had been made to ex­plain this work and re­lated ideas.

• In the course of ex­plain­ing a sin­gle re­sult, it helps give strong in­tu­itions about a wide va­ri­ety of re­lated ar­eas in math and logic, which are very im­por­tant for al­ign­ment re­search.

• It was re­ally fun to read; the draw­ings are very beau­tiful.

Biggest hes­i­ta­tions I had with cu­rat­ing:

• It wasn’t clear to me that the main ar­gu­ment the post makes re­gard­ing the un­trol­lable math­e­mat­i­ci­ans is it­self a huge re­sult in agent foun­da­tions re­search.

This wasn’t a big fac­tor for me though, as just mak­ing trans­par­ent all of the men­tal moves in achiev­ing this re­sult helps the reader with see­ing /​ learn­ing the men­tal mod­els used through­out this re­search area.

[rk]

I want to echo the other com­ments thank­ing you for mak­ing this lay-ap­proach­able and for the fun for­mat!

I do find my­self con­fused by some of the state­ments though. It may be that I have a root mi­s­un­der­stand­ing or that I am mis­read­ing some of the more quickly stated sen­tences.

For ex­am­ple, when you talk about the trees of truth & false­hood and the gap in the mid­dle: am I right in think­ing of these trees as prov­abil­ity and non-prov­abil­ity? Rather than per­haps truth & falsehood

Also, in the ex­is­tence proof for Bs such that $P\left(B|A\right)>\frac{1}{2}$ and we can prove $A\to B$ , you say that if B is a log­i­cal truth, A → B must be prov­able, be­cause any­thing im­plies a log­i­cal truth. It seems right to me that any­thing log­i­cally im­plies a log­i­cal truth. But surely we can’t prove all log­i­cal truths from any­thing—what if it’s a truth in the grey area such that it can’t be proved at all?

If some­one can put me right, that would be great

[Dacyn]

Yes you are right that the first tree is prov­abil­ity, but I think the sec­ond tree is meant to be dis­prov­abil­ity rather than non-prov­abil­ity. Similarly, when the OP later talks about “log­i­cal truths” and “log­i­cal false­hoods” it seems he re­ally means “prov­able state­ments” and “dis­prov­able state­ments”—this should re­solve the is­sue in your last para­graph, since if B is prov­able then so is A->B.

[rk]

dis­prov­abil­ity rather than non-provability

Yeah, you’re definitely right there. Oops, me.

Similarly, when the OP later talks about “log­i­cal truths” and “log­i­cal false­hoods” it seems he re­ally means “prov­able state­ments” and “dis­prov­able state­ments”—this should re­solve the is­sue in your last para­graph, since if B is prov­able then so is A->B

If that’s the case, then how does Goedel kick in? He then says, noth­ing can sep­a­rate log­i­cal truth from log­i­cal false­hood. But if he means prov­abil­ity and dis­prov­abil­ity, then triv­ially they can be separated

[Dacyn]

Here “sep­a­ra­tion” would mean that there is an al­gorithm which in­puts any state­ment and out­puts ei­ther “yes” or “no”, such that the al­gorithm re­turns “yes” on all in­puts that are prov­able state­ments and “no” on all in­puts that are dis­prov­able state­ments. But the al­gorithm also has to halt on all pos­si­ble in­puts, not just the ones that are prov­able or dis­prov­able. Such a sep­a­ra­tion al­gorithm can­not ex­ist (I am not sure if this fol­lows from Gödel’s the­o­rem or re­quires a sep­a­rate di­ag­o­nal­iza­tion ar­gu­ment). This is the re­sult needed in that step of the ar­gu­ment.

[rk]

Ah, so I was quite wrong when I said “triv­ially they can be sep­a­rated”. Cos we only have semi-de­ci­sion pro­ce­dures for prov­abil­ity and dis­prov­abil­ity!

Thanks for helping me with this

[Connor_Flexman]

I am con­fused as to how the propo­si­tional con­sis­tency and $\text{observe}\left[\right]$ func­tion work to­gether to pre­vent the trol­ling in the fi­nal step. Sup­pose I do try to find pairs of sen­tences such that I can show $(A\Rightarrow B_i)$ and also $\neg B_i$ to drive $A$ down. Does this fail be­cause you are pos­tu­lat­ing non-ad­ver­sar­ial sam­pling, as ESRogs men­tions? Or is there some other rea­son why propo­si­tional con­sis­tency is im­por­tant here?

[Diffractor]

There’s a mis­con­cep­tion, it isn’t about find­ing sen­tences of the form $A\to B_i$ and $\neg B_i$, be­cause if you do that, it im­me­di­ately dis­proves $A$. It’s ac­tu­ally about merely find­ing many in­stances of $A\to B_i$ where $P\left(B_i|A\right)$ has $<\frac{1}{2}$ prob­a­bil­ity, and this low­ers the prob­a­bil­ity of $A$. This is kind of like how find­ing out about the Banach-Tarski para­dox (some­thing you as­sign low prob­a­bil­ity to) may lower your de­gree of be­lief in the ax­iom of choice.

The par­tic­u­lar thing that pre­vents trol­ling is that in this dis­tri­bu­tion, there’s a fixed prob­a­bil­ity of draw­ing $A$ on the next round no mat­ter how many im­pli­ca­tions and $B$’s you’ve found so far. So the way it evades trol­ling is a bit cheaty, in a cer­tain sense, be­cause it be­lieves that the se­quence of truth or falsity of math sen­tences that it sees is drawn from a cer­tain fixed dis­tri­bu­tion, and doesn’t do any­thing like be­liev­ing that it’s more likely to see a cer­tain class of sen­tences come up soon.

[Benito]

(I fixed your LaTex. FYI what­ever your com­ment looks like be­fore you post, is what it will look like af­ter. Use ctrl-4 or cmd-4 for LaTex, de­pend­ing on whether you’re us­ing a PC or a Mac.)

[ESRogs]

Propo­si­tional con­sis­tency lets us ex­press con­straints be­tween sen­tences (such as ”$A$ and $B$ can­not both be true”) as sen­tences (such as “$\neg \left(A\&B\right)$”) in a way the prior un­der­stands and cor­rectly en­forces.

Any branch con­tra­dict­ing an already-stated con­straint is clipped off the tree of pos­si­ble se­quences of sen­tences.

The prob­a­bil­ity of any sen­tence $S$ which is con­sis­tent with ev­ery­thing seen so far can’t go be­low $\mu \left(S\right)$ or above $1-\mu \left(\neg S\right)$, since $S$ or $\neg S$ can be drawn next. So, no trol­ling.

How do I know whether $S$ is con­sis­tent with ev­ery­thing seen so far. Doesn’t that pre­sup­pose log­i­cal om­ni­science?

Or does con­sis­tency here only mean that it doesn’t vi­o­late any ex­plic­itly stated con­straints (such that I don’t have to know all the im­pli­ca­tions of all the sen­tences I’ve seen so far and whether they con­tra­dict $S$)?

[Diffractor]

There’s a differ­ence be­tween “con­sis­tency” (it is im­pos­si­ble to de­rive X and notX for any sen­tence X, this re­quires a halt­ing or­a­cle to test, be­cause there’s always more proof paths), and “propo­si­tional con­sis­tency”, which merely re­quires that there are no con­tra­dic­tions dis­cov­er­able by boolean alge­bra only. So A^B is propo­si­tion­ally in­con­sis­tent with notA, and propo­si­tion­ally con­sis­tent with A. If there’s some clever way to prove that B im­plies notA, it wouldn’t af­fect the propo­si­tional con­sis­tency of them at all. Propo­si­tional con­sis­tency of a set of sen­tences can be ver­ified in ex­po­nen­tial time.

[Chris_Leong]

Since propo­si­tional con­sis­tency is weaker than con­sis­tency our prior may dis­tribute some prob­a­bil­ity to cases that are con­tra­dic­tory. I guess that’s con­sid­ered ac­cept­able be­cause the aim is to make the prior non-trol­lable, rather than good.

[cousin_it]

Great ex­pla­na­tion! I read your ear­lier post on IAFF where the whole thing was ex­plained in one sen­tence, and it was quite clear, but see­ing it in pic­tures is much more fun. Maybe this is also why the Se­quences were fun to read—they ex­plained sim­ple ideas but in a very fancy cur­sive font :-)

[ESRogs]

Sup­pose na­ture is show­ing you true sen­tences one at a time. Model them as drawn ran­domly from a fixed dis­tri­bu­tion $\mu \left(S\right)$, but en­forc­ing propo­si­tional con­sis­tency.

Does this mean na­ture has to in fact be show­ing me sen­tences sam­pled from this fixed dis­tri­bu­tion, or am I just pre­tend­ing that that’s what it’s do­ing when I up­date my prior?

Does this work when sen­tences are shown to me in an ad­ver­sar­ial or­der?

[Diffractor]

You’re pre­tend­ing that it’s what na­ture is do­ing what you up­date your prior. It works when sen­tences are shown to you in an ad­ver­sar­ial or­der, but there’s the weird as­pect that this prior ex­pects the sen­tences to go back to be­ing drawn from some fixed dis­tri­bu­tion af­ter­wards. It doesn’t do a thing where it goes “ah, I’m see­ing a bunch of blue blocks se­lec­tively re­vealed, even though I think there’s a bunch of red blocks, the next block I’ll have re­vealed will prob­a­bly be blue”. In­stead, it just sticks with its prior on red and blue blocks.

[cata]

Thank you for mak­ing this! The for­mat held my at­ten­tion well, so I un­der­stood a lot whereas I might have zoned out and left if the same ma­te­rial had been pre­sented more tra­di­tion­ally. I’m go­ing to print it out and dis­tribute it at work—peo­ple like zines there.

[nostalgebraist]

This prior isn’t trol­lable in the origi­nal sense, but it is trol­lable in a weaker sense that still strikes me as im­por­tant. Since $\mu$ must sum to 1, only finitely many sen­tences $S$ can have $\mu \left(S\right)>ϵ$ for a given $ϵ>0$. So we can choose some finite set of “im­por­tant sen­tences” and con­trol their os­cilla­tions in a prac­ti­cal sense, but if there’s any $ϵ>0$ such that we think os­cilla­tions across the range $(ϵ,1-ϵ)$ are a bad thing, all but finitely many sen­tences can ex­hibit this bad be­hav­ior.

It seems es­pe­cially bad that we can only pre­vent “up-to-$ϵ$ trol­ling” for finite sets of sen­tences, since in PA (or what­ever) there are plenty of countable sets of sen­tences that seem “es­sen­tially the same” (like the ones you get from an in­duc­tion ar­gu­ment), and it feels very un­nat­u­ral to choose finite sub­sets of these and dis­t­in­guish them from the oth­ers, even (or es­pe­cially?) if we pre­tend we have no prior knowl­edge be­yond the ax­ioms.

[hwold]

I don’t un­der­stand where that ¹⁄₂ comes from. Un­less I have made a gross mis­take P(A|A ⇒ B) < P(A) even if P(A&B) > P(A&not(B)). In your first ex­am­ple, if I swap P(AB) and P(A&not(B)) so that P(AB) = .5 and P(A&not(B))=.3 then P(A|A=>B) = .5/​.7 ~ 0.71 < 0.8 = P(A).

[Chris_Leong]

This con­fused me as well. This be­ing true en­sures that the ra­tio P(A):P(not A) dou­bles at each step. But part of this comic seems to im­ply that be­ing less than a half stops the trol­ling, when it should only stop the trol­ling from pro­ceed­ing at such a fast-paced rate.

[Dacyn]

Maybe I am not sure why this math­e­mat­i­cian is con­sid­ered to be un­trol­lable? It seems the same or a similar al­gorithm could drive his prob­a­bil­ities up and down ar­bi­trar­ily within the in­ter­val $\left[\mu \right(S),1-\mu (-S\left)\right]$. If this is true, then his be­liefs at any stage are es­sen­tially ar­bi­trary with re­spect to this re­stric­tion. But isn’t that ba­si­cally the same as say­ing that if the state­ment hasn’t been proven or dis­proven yet, then his be­liefs don’t give any mean­ingful (non-trol­lable) fur­ther in­for­ma­tion as to whether the state­ment is true?

[Diffractor]

The be­liefs aren’t ar­bi­trary, they’re still rea­son­ing ac­cord­ing to a prob­a­bil­ity dis­tri­bu­tion over propo­si­tion­ally con­sis­tent “wor­lds”. Fur­ther­more, the be­liefs con­verge to a sin­gle num­ber in the limit of up­dat­ing on the­o­rems, even if the sen­tence of in­ter­est is un­prov­able. Con­sider some large but finite set S of sen­tences that haven’t been proved yet, such that the prob­a­bil­ity of sam­pling a sen­tence in that set be­fore sam­pling the sen­tence of in­ter­est “x”, is very close to 1. Then pick a time N, that is large enough that by that time, all the log­i­cal re­la­tions be­tween the sen­tences in S will have been found. Then, with prob­a­bil­ity very close to 1, ei­ther “x” or “notx” will be sam­pled with­out go­ing out­side of S.

So, if there’s some cool new the­o­rem that shows up re­lat­ing “x” and some sen­tence out­side of S, like “y->x”, well, you’re al­most cer­tain to hit ei­ther “x” or “notx” be­fore hit­ting “y”, be­cause “y” is out­side S, so this hot new the­o­rem won’t af­fect the prob­a­bil­ities by more than a neg­ligible amount.

Also I figured out how to gen­er­al­ize the prior a bit to take into ac­count ar­bi­trary con­straints other than propo­si­tional con­sis­tency, though there’s still kinks to iron out in that one. Check this.

[romeostevensit]

Has trol­ling peo­ple into pro­vid­ing un­trol­lable mod­els been reused? Seems worth try­ing.

[Elo]

Do the pic­tures load for other peo­ple? Be­cause they don’t load for me.

[Elo]

Oh wait. Just that browser.

[jimrandomh]

Many (though not all) of the images are bro­ken links right now. Could we get them re-up­loaded some­where else?

[Benito]

I just tried to fix that, and also the spac­ing is­sues. Let me know if it’s still bro­ken.