SamEisenstat(Sam Eisenstat)

• SamEisenstat 22 Jul 2020 2:06 UTC

  LW: 10 AF: 5

  AF

  on: Align­ment pro­pos­als and com­plex­ity classes

  Theorem. Weak HCH (and similar proposals) contain EXP.

  Proof sketch: I give a strategy that H can follow to determine whether some machine that runs in $O\left(2^{c{n}^k}\right)$ time accepts. Basically, we need to answer questions of the form “Does cell $x$ have value $y$ at time $t$.” and “Was the head in position $x$ at time $t$?”, where $x$ and $t$ are bounded by some function in $O\left(2^{c{n}^k}\right)$. Using place-system representations of $x$ and $t$, these questions have length in $O\left(n^k\right)$, so they can be asked. Further, each question is a simple function of a constant number of other such questions about earlier times as long as $t>0$, and can be answered directly in the base case $t=0$.

• SamEisenstat 21 Apr 2020 7:03 UTC

  4 points

  in reply to: jpulgarin’s comment on: The Car­toon Guide to Löb’s Theorem

  *I* think that there’s a flaw in the argument.

  I could elaborate, but maybe you want to think about this more, so for now I’ll just address your remark about $\neg \square C\to C$, where $C$ is refutable. If we assume that $\neg \square C\to C$, then, since $C$ is false, $\neg \square C$ must be false, so $\square C$ must be true. That is, you have proven that PA proves $\square C$, that is, since $C$ is contradictory, PA proves its own inconsistency. You’re right that this is compatible with PA being consistent—PA may be consistent but prove its own inconsistency—but this should still be worrying.

• SamEisenstat 25 Mar 2020 6:01 UTC

  7 points

  on: Ad­ding Up To Normality

  This reminds me of the Discourse on Method.

  [T]here is seldom so much perfection in works composed of many separate parts, upon which different hands had been employed, as in those completed by a single master. Thus it is observable that the buildings which a single architect has planned and executed, are generally more elegant and commodious than those which several have attempted to improve, by making old walls serve for purposes for which they were not originally built. Thus also, those ancient cities which, from being at first only villages, have become, in course of time, large towns, are usually but ill laid out compared with the regularity constructed towns which a professional architect has freely planned on an open plain; so that although the several buildings of the former may often equal or surpass in beauty those of the latter, yet when one observes their indiscriminate juxtaposition, there a large one and here a small, and the consequent crookedness and irregularity of the streets, one is disposed to allege that chance rather than any human will guided by reason must have led to such an arrangement. And if we consider that nevertheless there have been at all times certain officers whose duty it was to see that private buildings contributed to public ornament, the difficulty of reaching high perfection with but the materials of others to operate on, will be readily acknowledged. In the same way I fancied that those nations which, starting from a semi-barbarous state and advancing to civilization by slow degrees, have had their laws successively determined, and, as it were, forced upon them simply by experience of the hurtfulness of particular crimes and disputes, would by this process come to be possessed of less perfect institutions than those which, from the commencement of their association as communities, have followed the appointments of some wise legislator. It is thus quite certain that the constitution of the true religion, the ordinances of which are derived from God, must be incomparably superior to that of every other. And, to speak of human affairs, I believe that the pre-eminence of Sparta was due not to the goodness of each of its laws in particular, for many of these were very strange, and even opposed to good morals, but to the circumstance that, originated by a single individual, they all tended to a single end. In the same way I thought that the sciences contained in books (such of them at least as are made up of probable reasonings, without demonstrations), composed as they are of the opinions of many different individuals massed together, are farther removed from truth than the simple inferences which a man of good sense using his natural and unprejudiced judgment draws respecting the matters of his experience. And because we have all to pass through a state of infancy to manhood, and have been of necessity, for a length of time, governed by our desires and preceptors (whose dictates were frequently conflicting, while neither perhaps always counseled us for the best), I farther concluded that it is almost impossible that our judgments can be so correct or solid as they would have been, had our reason been mature from the moment of our birth, and had we always been guided by it alone.

  It is true, however, that it is not customary to pull down all the houses of a town with the single design of rebuilding them differently, and thereby rendering the streets more handsome; but it often happens that a private individual takes down his own with the view of erecting it anew, and that people are even sometimes constrained to this when their houses are in danger of falling from age, or when the foundations are insecure. With this before me by way of example, I was persuaded that it would indeed be preposterous for a private individual to think of reforming a state by fundamentally changing it throughout, and overturning it in order to set it up amended; and the same I thought was true of any similar project for reforming the body of the sciences, or the order of teaching them established in the schools: but as for the opinions which up to that time I had embraced, I thought that I could not do better than resolve at once to sweep them wholly away, that I might afterwards be in a position to admit either others more correct, or even perhaps the same when they had undergone the scrutiny of reason. I firmly believed that in this way I should much better succeed in the conduct of my life, than if I built only upon old foundations, and leaned upon principles which, in my youth, I had taken upon trust. For although I recognized various difficulties in this undertaking, these were not, however, without remedy, nor once to be compared with such as attend the slightest reformation in public affairs. Large bodies, if once overthrown, are with great difficulty set up again, or even kept erect when once seriously shaken, and the fall of such is always disastrous. Then if there are any imperfections in the constitutions of states (and that many such exist the diversity of constitutions is alone sufficient to assure us), custom has without doubt materially smoothed their inconveniences, and has even managed to steer altogether clear of, or insensibly corrected a number which sagacity could not have provided against with equal effect; and, in fine, the defects are almost always more tolerable than the change necessary for their removal; in the same manner that highways which wind among mountains, by being much frequented, become gradually so smooth and commodious, that it is much better to follow them than to seek a straighter path by climbing over the tops of rocks and descending to the bottoms of precipices.

  ...

  And finally, as it is not enough, before commencing to rebuild the house in which we live, that it be pulled down, and materials and builders provided, or that we engage in the work ourselves, according to a plan which we have beforehand carefully drawn out, but as it is likewise necessary that we be furnished with some other house in which we may live commodiously during the operations, so that I might not remain irresolute in my actions, while my reason compelled me to suspend my judgement, and that I might not be prevented from living thenceforward in the greatest possible felicity, I formed a provisory code of morals, composed of three or four maxims, with which I am desirous to make you acquainted.

  The first was to obey the laws and customs of my country, adhering firmly to the faith in which, by the grace of God, I had been educated from my childhood and regulating my conduct in every other matter according to the most moderate opinions, and the farthest removed from extremes, which should happen to be adopted in practice with general consent of the most judicious of those among whom I might be living. For as I had from that time begun to hold my own opinions for nought because I wished to subject them all to examination, I was convinced that I could not do better than follow in the meantime the opinions of the most judicious; and although there are some perhaps among the Persians and Chinese as judicious as among ourselves, expediency seemed to dictate that I should regulate my practice conformably to the opinions of those with whom I should have to live; and it appeared to me that, in order to ascertain the real opinions of such, I ought rather to take cognizance of what they practised than of what they said, not only because, in the corruption of our manners, there are few disposed to speak exactly as they believe, but also because very many are not aware of what it is that they really believe; for, as the act of mind by which a thing is believed is different from that by which we know that we believe it, the one act is often found without the other. Also, amid many opinions held in equal repute, I chose always the most moderate, as much for the reason that these are always the most convenient for practice, and probably the best (for all excess is generally vicious), as that, in the event of my falling into error, I might be at less distance from the truth than if, having chosen one of the extremes, it should turn out to be the other which I ought to have adopted. And I placed in the class of extremes especially all promises by which somewhat of our freedom is abridged; not that I disapproved of the laws which, to provide against the instability of men of feeble resolution, when what is sought to be accomplished is some good, permit engagements by vows and contracts binding the parties to persevere in it, or even, for the security of commerce, sanction similar engagements where the purpose sought to be realized is indifferent: but because I did not find anything on earth which was wholly superior to change, and because, for myself in particular, I hoped gradually to perfect my judgments, and not to suffer them to deteriorate, I would have deemed it a grave sin against good sense, if, for the reason that I approved of something at a particular time, I therefore bound myself to hold it for good at a subsequent time, when perhaps it had ceased to be so, or I had ceased to esteem it such.

  My second maxim was to be as firm and resolute in my actions as I was able, and not to adhere less steadfastly to the most doubtful opinions, when once adopted, than if they had been highly certain; imitating in this the example of travelers who, when they have lost their way in a forest, ought not to wander from side to side, far less remain in one place, but proceed constantly towards the same side in as straight a line as possible, without changing their direction for slight reasons, although perhaps it might be chance alone which at first determined the selection; for in this way, if they do not exactly reach the point they desire, they will come at least in the end to some place that will probably be preferable to the middle of a forest. In the same way, since in action it frequently happens that no delay is permissible, it is very certain that, when it is not in our power to determine what is true, we ought to act according to what is most probable; and even although we should not remark a greater probability in one opinion than in another, we ought notwithstanding to choose one or the other, and afterwards consider it, in so far as it relates to practice, as no longer dubious, but manifestly true and certain, since the reason by which our choice has been determined is itself possessed of these qualities. This principle was sufficient thenceforward to rid me of all those repentings and pangs of remorse that usually disturb the consciences of such feeble and uncertain minds as, destitute of any clear and determinate principle of choice, allow themselves one day to adopt a course of action as the best, which they abandon the next, as the opposite.

  (This is probably 5% of the text. There is more interesting stuff there, but it’s less relevant to this post.)

Reflec­tive or­a­cles as a solu­tion to the con­verse Law­vere problem

Iter­a­tion Fixed Point Exercises

Di­ag­o­nal­iza­tion Fixed Point Exercises

Topolog­i­cal Fixed Point Exercises

• SamEisenstat 12 Jun 2018 8:47 UTC

  LW: 1 AF: 1

  AF

  on: A Loop­hole for Self-Ap­plica­tive Soundness

  As you say, this isn’t a proof, but it wouldn’t be too surprising if this were consistent. There is some $k\in N$ such that ${\square }_n\varphi \to \varphi$ has a proof of length $n^k$ by a result of Pavel Pudlák (On the length of proofs of finitistic consistency statements in first order theories). Here I’m making the dependence on $n$ explicit, but not the dependence on $\varphi$. I haven’t looked at it closely, but the proof strategy in Theorems 5.4 and 5.5 suggests that $k$ will not depend on $\varphi$, as long as we only ask for the weaker property that ${\square }_n\varphi \to \varphi$ will only be provable in length $n^k$ for sentences $\varphi$ of length at most $k$.

• SamEisenstat 5 Jun 2018 20:46 UTC

  0 points

  AF

  in reply to: Diffractor’s comment on: A Loop­hole for Self-Ap­plica­tive Soundness

  I misunderstood your proposal, but you don’t need to do this work to get what you want. You can just take each sentence ${\square }_n\varphi \to \varphi$ as an axiom, but declare that this axiom takes $n$ symbols to invoke. This could be done by changing the notion of length of a proof, or by taking axioms ${\psi }_{\varphi ,n}\to ({\square }_n\varphi \to \varphi )$ and ${\psi }_{\varphi ,n}$ with ${\psi }_{\varphi ,n}$ very long.

• SamEisenstat 9 May 2018 1:52 UTC

  1 point

  in reply to: interstice’s comment on: Open ques­tion: are min­i­mal cir­cuits dae­mon-free?

  Yeah, I had something along the lines of what Paul said in mind. I wanted not to require that the circuit implement exactly a given function, so that we could see if daemons show up in the output. It seems easier to define daemons if we can just look at input-output behaviour.

• SamEisenstat 8 May 2018 20:01 UTC

  LW: 10 AF: 7

  AF

  on: Open ques­tion: are min­i­mal cir­cuits dae­mon-free?

  I’m having trouble thinking about what it would mean for a circuit to contain daemons such that we could hope for a proof. It would be nice if we could find a simple such definition, but it seems hard to make this intuition precise.

  For example, we might say that a circuit contains daemons if it displays more optimization that necessary to solve a problem. Minimal circuits could have daemons under this definition though. Suppose that some function $f$ describes the behaviour of some powerful agent, a function $\tilde{f}$ is like $f$ with noise added, and our problem is to predict sufficiently well the function $\tilde{f}$. Then, the simplest circuit that does well won’t bother to memorize a bunch of noise, so it will pursue the goals of the agent described by $f$ more efficiently than $\tilde{f}$, and thus more efficiently than necessary.

• SamEisenstat 14 Apr 2018 1:39 UTC

  LW: 1 AF: 1

  AF

  on: No Con­stant Distri­bu­tion Can be a Log­i­cal Inductor

  Two minor comments. First, the bitstrings that you use do not all correspond to worlds, since, for example, $Con(PA+Con(PA\left)\right)$ implies $Con\left(PA\right)$, as $PA$ is a subtheory of $PA+Con\left(PA\right)$. This can be fixed by instead using a tree of sentences that all diagonalize against themselves. Tsvi and I used a construction in this spirit in A limit-computable, self-reflective distribution, for example.

  Second, I believe that weakening #2 in this post also cannot be satisfied by any constant distribution. To sketch my reasoning, a trader can try to buy a sequence of sentences ${\varphi }_1,{\varphi }_1\wedge {\varphi }_2,\dots$, spending $$2^{-n}$ on the \(n\)th sentence \(\phi_1 \wedge \dots \wedge \phi_n\). It should choose the sequence of sentences so that \(\phi_1 \wedge \dots \wedge \phi_n\) has probability at most \(2^{-n}\), and then it will make an infinite amount of money if the sentences are simultaneously true.

  The way to do this is to choose each ${\varphi }_n$ from a list of all sentences. If at any point you notice that ${\varphi }_1\wedge \cdots \wedge {\varphi }_n$ has too high a probability, then pick a new sentence for ${\varphi }_n$. We can sell all the conjunctions ${\varphi }_1\wedge \cdots \wedge {\varphi }_k$ for $k\ge n$ and get back the original amount payed by hypothesis. Then, if we can keep using sharper continuous tests of the probabilities of the sentences ${\varphi }_1\wedge \cdots \wedge {\varphi }_n$ over time, we will settle down to a sequence with the desired property.

  In order to turn this sketch into a proof, we need to be more careful about how these things are to be made continuous, but it seems routine.

• SamEisenstat 24 Jan 2018 3:04 UTC

  LW: 2 AF: 1

  AF

  on: An Un­trol­lable Mathematician

  I at first didn’t understand your argument for claim (2), so I wrote an alternate proof that’s a bit more obvious/​careful. I now see why it works, but I’ll give my version below for anyone interested. In any case, what you really mean is the probability of deciding a sentence outside of $\Phi$ by having it announced by nature; there may be a high probability of sentences being decided indirectly via sentences in $\Phi$.

  Instead of choosing $\Phi$ as you describe, pick $\Phi$ so that the probability $\mu \left(\Phi \right)$ of sampling something in $\Phi$ is greater than $1-\mu \left(\psi \right)\cdot \epsilon /2$. Then, the probability of sampling something in $\Phi -\left\{\psi \right\}$ is at least $1-\mu \left(\psi \right)\cdot (1+\epsilon /2)$. Hence, no matter what sentences have been decided already, the probability that repeatedly sampling from $\mu$ selects $\psi$ before it selects any sentence outside of $\Phi$ is at least

  $$\begin{array}{cc}\sum _{k=0}^{\infty }(1-\mu (\psi )\cdot (1+\epsilon /2){)}^k\cdot \mu (\psi )& =\frac{\mu \left(\psi \right)}{\mu \left(\psi \right)\cdot (1+\epsilon /2)}\\ & >1-\epsilon /2\end{array}$$

  as desired.

  Furthermore, this argument makes it clear that the probability distribution we converge to depends only on the set of sentences which the environment will eventually assert, not on their ordering!

  Oh, I didn’t notice that aspect of things. That’s pretty cool.

• SamEisenstat 22 Jul 2017 12:03 UTC

  0 points

  AF

  on: Some Crit­i­cisms of the Log­i­cal In­duc­tion paper

  A few thoughts:

  I agree that the LI criterion is “pointwise” in the way that you describe, but I think that this is both pretty good and as much as could actually be asked. A single efficiently computable trader can do a lot. It can enforce coherence on a polynomially growing set of sentences, search for proofs using many different proof strategies, enforce a polynomially growing set of statistical patterns, enforce reflection properties on a polynomially large set of sentences, etc. So, eventually the market will not be exploitable on all these things simultaneously, which seems like a pretty good level of accurate beliefs to have.

  On the other side of things, it would be far to strong to ask for a uniform bound of the form “for every $\epsilon >0$, there is some day $t$ such that after step $t$, no trader can multiply its wealth by a factor more than $1+\epsilon$”. This is because a trader can be hardcoded with arbitrarily many hard-to-compute facts. For every $\delta$, there must eventually be a day $t^{\prime }>t$ on which the belief of your logical inductor assign probability less than $\delta$ to some true statement, at which point a trader who has that statement hardcoded can multiply its wealth by $1/\delta$. (I can give a construction of such a sentence using self-reference if you want, but it’s also intuitively natural—just pick many mutually exclusive statements with nothing to break the symmetry.)

  Thus, I wouldn’t think of traders as “mistakes”, as you do in the post. A trader can gain money on the market if the market doesn’t already know all facts that will be listed by the deductive process, but that is a very high bar. Doing well against finitely many traders is already “pretty good”.

  What you can ask for regarding uniformity is for some simple function $f$ such that any trader $T$ can multiply its wealth by at most a factor $f\left(T\right)$. This is basically the idea of the mistake bound model in learning theory; you bound how many mistakes happen rather than when they happen. This would let you say a more than the one-trader properties I mentioned in my first paragraph. In fact, $LIA$ has this propery; $f\left(T\right)$ is just the initial wealth of the trader. You may therefore want to do something like setting traders’ initial wealths according to some measure of complexity. Admittedly this isn’t made explicit in the paper, but there’s not much additional that needs to be done to think in this way; it’s just the combination of the individual proofs in the paper with the explicit bounds you get from the initial wealths of the traders involved.

  ---

  I basically agree completely on your last few points. The traders are a model class, not an ensemble method in any substantive way, and it is just confusing to connect them to the papers on ensemble methods that the LI paper references. Also, while I use the idea of logical induction to do research that I hope will be relevant to practical algorithms, it seems unlikely than any practical algorithm will look much like a LI. For one thing, finding fixed points is really hard without some property stronger than continuity, and you’d need a pretty good reason to put it in the inner loop of anything.

• SamEisenstat 5 Jul 2017 22:20 UTC

  LW: 2 AF: 2

  AF

  on: Two Ques­tions about Solomonoff Induction

  Universal Prediction of Selected Bits solves the related question of what happens if the odd bits are adversarial but the even bits copy the preceding odd bits. Basically, the universal semimeasure learns to do the right thing, but the exact sense in which the result is positive is subtle and has to do with the difference between measures and semimeasures. The methods may also be relevant to the questions here, though I don’t see a proof for either question yet.

• SamEisenstat 11 Jun 2017 23:21 UTC

  0 points

  AF

  in reply to: abramdemski’s comment on: An Ap­proach to Log­i­cally Up­date­less Decisions

  Yeah, I like tail dependence.

  There’s this question of whether for logical uncertainty we should think of it more as trying to “un-update” from a more logically informed perspective rather than trying to use some logical prior that exists at the beginning of time. Maybe you’ve heard such ideas from Scott? I’m not sure if that’s the right perspective, but it’s what I’m alluding to when I say you’re introducing artificial logical uncertainty.

• SamEisenstat 10 Jun 2017 6:31 UTC

  LW: 1 AF: 1

  AF

  in reply to: cousin_it’s comment on: Two Ma­jor Ob­sta­cles for Log­i­cal In­duc­tor De­ci­sion Theory

  Yeah, the 5 and 10 problem in the post actually can be addressed using provability ideas, in a way that fits in pretty natually with logical induction. The motivation here is to work with decision problems where you can’t prove statements $A=a\to U=u$ for agent $A$, utility function $U$, action $a$, and utility value $u$, at least not with the amount of computing power provided, but you want to use inductive generalizations instead. That isn’t necessary in this example, so it’s more of an illustration.

  To say a bit more, if you make logical inductors propositionally consistent, similarly to what is done in this post, and make them assign things that have been proven already probability 1, then they will work on the 5 and 10 problem in the post.

  It would be interesting if there was more of an analogy to explore between the provability oracle setting and the inductive setting, and more ideas could be carried over from modal UDT, but it seems to me that this is a different kind of problem that will require new ideas.

• SamEisenstat 10 Jun 2017 1:16 UTC

  LW: 3 AF: 1

  AF

  in reply to: William_S’s comment on: Two Ma­jor Ob­sta­cles for Log­i­cal In­duc­tor De­ci­sion Theory

  It’s hard to analyze the dynamics of logical inductors too precisely, so we often have to do things that feel like worst-case analysis, like considering an adversarial trader with sufficient wealth. I think that problems that show up from this sort of analysis can be expected to correspond to real problems in superintelligent agents, but that is a difficult question. The malignancy of the universal prior is part of the reason.

  As to your proposed solution, I don’t see how it would work. Scott is proposing that the trader makes conditional contracts, which are in effect voided if the event that they are conditional on doesn’t happen, so the trader doesn’t actually lose anything is this case. (It isn’t discussed in this post, but conditional contracts can be built out of the usual sort of bets, with payoffs given by the definition of conditional probability.) So, in order to make the trader lose money, the events need to happen sometimes, not just be expect to happen with some nonnegligable probability by the market.

• SamEisenstat 3 Jun 2017 0:24 UTC

  LW: 2 AF: 2

  AF

  on: An Ap­proach to Log­i­cally Up­date­less Decisions

  In counterfactual mugging with a logical coin, AsDT always uses a logical inductor’s best-estimate of the utility it would get right now, so it sees the coin as already determined, and sees no benefit from giving Omega money in the cases where Omega asks for money.

  The way I would think about what’s going on is that if the coin is already known at the time that the expectations are evaluated, then the problem isn’t convergent in the sense of AsDT. The agent that pays up whenever asked has a constant action, but it doesn’t receive a constant expected utility. You can think of the averaging as introducing artificial logical uncertainty to make more things convergent, which is why it’s more updateless. (My understanding is that this is pretty close to how you’re thinking of it already.)

• SamEisenstat 24 Apr 2017 5:08 UTC

  0 points

  AF

  on: Gen­er­al­iz­ing Foun­da­tions of De­ci­sion The­ory II

  This isn’t too related to your main point, but every ordered field can be embedded into a field of Hahn series, which might be simpler to work with than surreals.

  That page discusses the basics of Hahn series, but not the embedding theorem. (Ehrlich, 1995) treats things in detail, but is long and introduces a lot of definitions. The embedding theorem is stated on page 23 (24 in the pdf).