Sunday, May 8, 2011

Current Probability Ideas

Follow-up to this post (and the series preceding it). I think that while my distinction between subjective and objective probability makes sense, it's not the right direction for answering the questions I'm asking-- it overcomplicates the issues. That change of view is based on a few papers, which I still need to read in more detail. (IE, this post does not summarise insights from those papers, it summarises my reaction from discovering their existence.)

Aside: my previous post, this one, and perhaps the next one or two do not represent me "thinking aloud" as my posts usually do... instead, I'm summarising thoughts that I had over the semester, but felt too busy to blog about.


So. How well can we do with just a single layer of probability, over a standard logic? How can we achieve something similar to Solomonoff induction?

One idea is to imagine that the universe we are observing was constructed by randomly writing down sentences in logic to determine each fact, only taking care not to ever write something which contradicts what we've already written. For example, we can  use a length-based prior to choose a sentence at random from first-order logic.  This prior obviously contains the Solomonoff prior ("is dominant over" as they say), but it's not clear to me whether the relationship goes the other way ("is dominated by") so that they are roughly equivalent. I'm thinking the prior I'm specifying is "even more uncomputable," since we have to check for consistency of theories.

This prior lends itself to an interesting approximation scheme, though.

  • Each sentence has at least log-probability inversely proportional to its length
  • To this, we can add some probability mass for each consistent sequence of sentences which we find that implies the sentence. (To test for "consistent" we just try to find a contradiction for some reasonable amount of time, perhaps trying harder later if it's important.)
  • Normalise this probability by dividing by (1 - probability we encounter an inconsistent sequence drawing randomly), which is estimated based on the cumulative probability of the inconsistent sequences we've identified so far.
  • This gives a rough lower bound for the probability. To get an upper bound, we apply the same technique to the negation of the sentence.
  • If A implies B, then B is at least as probable as A (ie, it can inherit A's lower bound). Likewise, A is at most as probable as B (inheriting B's upper bound). In other words, we can use existing ideas about propagating probability intervals to work with these estimates if we like.
  • To update on evidence, we use compatibility with that evidence as an extra criteria for consistency of sequences of statements. Intuitively, this will throw out a bunch of possibilities (and increase the amount of normalisation by doing that, which increases the probability of the remaining possibilities).

Unfortunately, these bounds would tend to be very wide, I think. The system would have to do a lot of thinking to narrow them down. More generous approximations might find one model and stick to it until it's disproved or a better model is found, say. This would at least give the system something to work with.

Now that we have a little bit of foundation in place, I think we can more usefully consider what to do if we want higher-order probabilities. Just as we can randomly choose sentences of first-order logic, we can randomly choose sentences of any system of probabilistic models we like (such as BLP, BLog, etc). This allows us to use the inference algorithms, et cetera from our favourite formalism. As long as first-order logic is a special case of the formalism, it will be just as universal.

For example, we could perfectly well use a prior based on random theories stated with the (objective-)probability-theoretic quantification which I was discussing in the previous posts. If we do this, we basically solve the puzzles I was running up against there: the inference from objective probabilities over classes to subjective probabilities over individuals is justified by the regularity assumption in the prior, IE, by the idea that the objective probability might be an "essential feature" of the class... something that was written down in the book of rules for the universe before the individual cases were decided.

Saturday, May 7, 2011

Impredicativity

Lukasz Stafiniak sent me this about impredicativity. I had seen the concern before, but never seen why it was worth any worry. Impredicative comprehension principles are a big convenience for normal mathematics, and don't lead to any paradoxes that we know of.

However, looking at it again, I realised that the basic complaint could be read as "impredicative comprehension is not valid in Kripke's theory of truth." This is more concerning to me. In fact, the concern can be stated just in terms of the Tarski hierarchy: 2nd-order logic does not exist at any stage in the Tarski hierarchy. I was foolishly thinking that there was a direct correspondence between stages in the hierarchy and orders of logic. There is, if we use predicative comprehension! But, impredicative comprehension is "too powerful" to exist at any stage of any recursive hierarchy.

This causes trouble for me, because impredicative comprehension is necessary to my understanding of the natural numbers (and other important things).

Fortunately, the article suggests a solution: impredicative quantifications should be understood at the level of provability. IE, we aren't stating that all instances are true; we are stating something stronger, that they are all provable. (But we use infinitary logic, so that this is not as much of a restriction.) This is a very intuitionistic suggestion.

Unfortunately, we can see that this really just introduces another metalanguage (the language of provability). Hence, comprehension interpreted this way does not include all possible predicates after all (even if we extend the provability interpretation to the point where it covers all cases of 2nd-order comprehension): it skips the predicates which can be defined in terms of provability.

Building a self-referential theory of logical implication which follows the rules we want is hard. The obvious way of doing it just leads directly to Curry's paradox. I still have not finished reading Hartry Field's "Saving Truth from Paradox", but it includes an account of implication which may be helpful. These posts also contain some notes which may be helpful.

I should have known for about a year now that the immediate challenge is to built up to 2nd-order logic, not to build up to set theory. However, this made it hit home: I can't rely on 2nd order logic to be there for me when I need it. I don't yet know what 2nd-order logic is, or where it comes from.

Still, the fact remains that 2nd-order logic is a fairly natural, very useful, and almost certainly consistent set of axioms. It seems probable that aliens would stumble upon it, etc. It does not just poof out of existence. Even just as a syntactic entity rather than one with a semantics, it's still important!

Friday, February 4, 2011

Probabilities over Subjective Worlds

This is the promised follow-up to this post.

What sense can we make of the standard treatment of subjective higher-order probabilities? Beyond the formalism, how are we to visualise this stuff?


I wanted a possible-worlds type semantics, but I decided to construct my own rather than looking at existing ones.

In normal possible-world semantics, we've got a bunch of worlds which hold complete valuations-- assignments of every statement to true or false. Then, we often talk about an "accessibility" relation between worlds: world A is only accessible from world B under certain conditions. The accessibility relation controls our notion of "possible" and "necessary": from our perspective at a world W, something is considered "possible" if it is true in some world accessible from W, and "necessary" if it is true in all accessible worlds.

Examples of useful accessibility relations include ones based on knowledge (ie, the accessible worlds are the ones consistent with what I know about the world I'm in) and based on time (ie, the accessible worlds are potential futures).

One way of getting probabilities out of this is to make the accessibility relation continuous-valued; rather than a world being accessible or not, a world has a degree of accessibility.

So, we start with just non-probabilistic facts in each world; then 1st-order probabilistic facts get values based on the immediately accessible worlds. Then 2nd-order facts, 3rd-order, et cetera. (This can go up to infinite orders if the language is expressive enough to mention them.)

To get coherent probabilities, we need to have some restrictions on the weights of the accessibility relations; I won't go into detail here.

Unfortunately, this really only gets us a 1st-order distribution: since all our facts are completely determined in each world, all our 1st-order probabilities will be completely determined in the first propagation step, so all higher-order probabilities will be 1 or 0.

To get an interesting higher-order distribution, we can give up the idea that possible worlds always hold complete valuations. Instead, a possible world contains just a partial picture: an assignment of a few facts to true or false. This allows the probabilities to be only partially determined, allowing nontrivial probabilities at each stage.

This goes along with an idea called "situation theory" which I know only a little about. As I understand it, the idea is that when talking about possibility, we talk about "situations" rather than worlds: partial assignments to true/false rather than complete ones.

It's probably better to think of these as "possible states of knowledge" rather than possible worlds or even possible situations, given the probabilistic interpretation. We move between worlds when we gain knowledge. Some of the worlds *will* be fully specified, and one of these will correspond to the "actual world"; however, we will never get there in terms of our state of knowledge.

Now, since this construction gives us a self-referential probability predicate, it is interesting to think of it as a sort of generalised theory of self-referential truth. P(S)=1 plays the role of True(S), but does so imperfectly: it is possible for the probability of a statement to be 1 but for the statement to later turn out to be false. For example, if we have an even distribution over the possible probabilities of some statement A, then P(P(A)=r)=0 for all real numbers r. This means P(P(A) not equal r)=1 for all r. Yet, we may eventually transition into a world in which r takes on a specific value-- so we can't think of all statements "P(A) not equal r" as being true. This makes our theory of (pseudo-)truth one in which the inference A => True(A) is justified, but not the inference True(A) => A.

The propagation method gives us a "least-fixed-point" type probability distribution. However, there might also be other useful fixed points. For example, we may want some self-referential sentences to come out with probability values.

In any fixed point, there will be probabilistic statements which do not get any truth value. First off, any statement which has a (non-integer) probabilistic belief associated with it can't also have a truth value. There will also be statements, though, which can't be consistently assigned any level of belief.

Overall, this probably doesn't offer an especially appealing theory of truth. It would be interesting to know more about precisely how much it can give us, though.

Friday, January 28, 2011

Some Consequences of Incompleteness

I wrote an essay about some issues in logic a little while ago.

Friday, January 21, 2011

Subjective Probability

The system I described in the previous post doesn't directly lend itself to "subjective" higher-order probabilities. Specifically, we can't just have a degree of belief in an arbitrary statement. We need to choose a variable randomly in order to have a probability-- a completely specific statement (with no variables) can't have a probability other than 1 or 0. Probabilities are reduced to a sort of counting -- specifically, what's known as a "measure" -- rather than being a way of representing uncertainty.

There are some ways we can try to interpret subjective probabilities as measures. We can introduce "possible worlds" (or "possible situations"), which we treat as being chosen randomly-- so if we're uncertain about whether it will rain or snow tomorrow, it's because in some possible worlds it rains, and in some it snows. The probability of each is obtained by counting the possibilities. However, prompted by Lukasz's comment on my previous post, I took a much closer look at how higher-order subjective probability measures should be represented. I found myself re-inventing the standard higher-order probability theory which I complained about in the first place. This can be represented within my framework, but it isn't clear that it should be. Each theory can stand on its own, and is more convenient for different purposes.

One problem with my proposed system is that it does not directly endorse the idea of generalizing from examples. Having knowledge of more examples will give us more knowledge of the probability involved, but only because the probability is defined by literally counting examples. If we have 100 buttons (each measured equally) and we know only that each button is either red or blue, seeing 98 of those buttons will tell us the probability to within a range of .02, but that tells us nothing about the last two buttons! 98 blue buttons are no indication that the last two are blue, unless we add a possible-world framework so that we can measure probabilities of the last two colors as a function of randomly chosen worlds.

Frequentism is a bit better here: probabilities are not just arbitrary measures, but rather, are limiting frequencies. What this means is that the probability of an event is defined as the ratio one would get after an infinite number of experiments. It seems more justifiable to use a limiting frequency as a generalization; if we have a limiting frequency, then we know that if we run experiments long enough, we'll get close to that ratio. This in-the-long-run statement is potentially quite weak with respect the the immediate future, but at least it tells us something about the future!

There are some problems with limiting frequencies, however. One problem  is that there is no mathematical guarantee that limiting frequencies exist! Mathematically speaking, the limiting frequency will typically depend on such things as the order in which we perform the experiments; some orderings will have different limits, and some will have none at all (ie, the ratio varies up and down infinitely). We have to assume that the actual order in which we perform experiments will have a limit. Another problem is how we might get knowledge of limiting frequencies. A limiting frequency is not something we can directly use as a degree of belief concerning another limiting frequency-- limiting frequencies require something called a reference class (meaning that a probability for a specific event is only defined when we think of that event in the context of a specific sequence of random experiments). Furthermore, a ratio from a finite series of experiments does not necessarily tell us anything about the ratio after an infinite number of experiments; we need additional assumptions to try and make this connection.

This brings in the idea that we have to start with some probabilities in order to get more (effectively, we need a Bayesian prior). Taken to its extreme, we get the theory of subjective Bayesian probabilities; all probabilities are interpreted as personal degrees of belief. New information provides evidence for hypotheses by Bayes' Law, so that we can generalize from examples by performing bayesian updates on our probabilistic models of the world.

Really, all three of these options are valid applications of probability theory. One does not have to be a purist-- the different types of probability can be mixed. In particular, it seems useful to take Bayesian-style degrees of belief as a way of estimating the two other kinds of probabilities.

However, that sort of inclusiveness does not settle the issue of how probabilities should be used for particular applications. For my curiosities about higher-order probabilities, the system I presented in the previous post offers a somewhat nice, tight connection between higher-order probabilities and first-order logic (probabilities being a generalization of universal quantifiers). This may be appealing for certain probabilistic logic issues. On the other hand, the Bayesian theory of higher order probabilities has a nicer way of allowing a degree of belief for any statement... (though, higher-order belief distributions require us to just use expected probabilities when making bets, as I complained in the previous post).

I'll end this here... next time, I hope to talk a bit about the structure of possible-world semantics for purely subjective probabilities, and what it provides in the way of a theory of truth and foundation for mathematics.

Sunday, December 19, 2010

Foundations of Higher-Order Probability

I think the foundations of higher-order probability theory may be in a bit of a mess.

Whereas first-order probabilities express uncertainty about the world, a higher-order probability expresses uncertainty about what value a first-order probability has. Or, if you ask a Frequentist instead of a Bayesian: first-order probabilities give limiting frequencies of results from experiments, whereas higher-order probabilities give limiting frequencies of getting certain limiting frequencies.

Uncertainty about uncertainty could be argued to defeat the whole point of having a plausible degree of belief... why can't it be collapsed into a straight degree of belief?

This paper tries to base higher-order probability on the idea that there is some "ideal expert" who knows the "true probability" which we are uncertain about. However, the paper puts it up to the agent to decide what constitutes a "fully informed ideal expert." If the ideal expert knows which events actually happen or not, then the first-order probabilities will all be 0 or 1, so the higher-order probabilities take on the role that 1st-order probabilities usually take on. In the opposite extreme, the "ideal expert" is just the agent itself, so that the higher-order probabilities are all 1 or 0 and the first-order probabilities are known. (All this is specifically laid out by the author.) This seems to put higher-order probability on a very shaky footing; at least to my ear.

Consider the following situation concerning an event A:

P(P(A)=1/3)=1/2
P(P(A)=2/3)=1/2

In English, we do not know if the probability of A is 1/3 or 2/3-- we assign 50% probability to each.

Now, two plausible principles of higher-order reasoning are as follows.

  • Expectation principle: We can find our first-order belief in event A by a weighted averaging over the possibilities; ie, P(A)=E(P(A)), where E is the expectation operator (which takes the average value, weighted by probability). This is necessary to convert higher-order distributions into numbers we can use to place bets, etc.
  • Lifting principal: If we know X, we know P(X)=1. This paper argues for a related rule: P(X)=p if and only if P(P(X)=p)=1. Either rule is sufficient for the argument that follows; specifically, I only need that P(X)=p implies P(P(X)=p)=1. (This is a special case of my "lifting" by instantiation of X to P(X)=p, and a weakening of their coherence-based principle since it takes just one direction of the "if and only if".) [It is interesting to note the similarity of these rules to proposed rules for the truth predicate, and in fact that is what started my investigation of this; however, I won't give significant space to that now.]
Granting both of these rules,  it is not hard to see that any non-trivial higher-order distribution will be contradictory. Returning to the example at hand, we apply the two rules in succession:

P(P(A)=1/3)=1/2
P(P(A)=2/3)=1/2
->
P(A)=1/2 via expectation,
->
P(P(A)=1/2)=1 via lifting.

But this contradicts the original distribution; we have

P(P(A)=1/3)=1/2
P(P(A)=2/3)=1/2
P(P(A)=1/2)=1,

which sums to 3/2, violating the laws of probability.

For higher-order probability to be non-trivial, then, it seems we  must reject one or both of my given principles. If this is granted, I think the best view is that the expectation principle should be abandoned; after all, that paper I cited gives a pretty good argument for a form of lifting principle. One way of looking at the expectation principle is that it flattens the higher-order distribution to a first-order one, trivialising it.

However, I want to preserve both principles. Both seem totally reasonable to me, and I've found a solution for keeping a form of each without any problem. I will argue that the problem here is one of equivocation; the notation being used is not specific enough. (The argument I use comes from my brother.)

For concreteness, suppose the event 'A' I mentioned is flipping a coin and getting heads. One scenario which fits with the probabilities I gave is as follows. We have two unfair coins in a bag; one gives heads 2/3 of the time, and the other gives heads 1/3 of the time. If we want a fair chance of heads, we can just draw at random and flip; half the time we will get the coin bias towards heads, but half the time we will get the one bias against. Since the bias is equal in each direction, we will get heads 50% of the time. This illustrates the expectation principle in action, yet it does not trivialise the higher-order characterisation of the situation: if we draw one coin out of the bag and keep it out, we can try and determine whether it is the 1/3 coin or the 2/3 coin through experimentation. This involves a Bayesian update on the higher-order distribution I gave.

The intuition, then, is that the "flattened" probability (1/2) and the "non-flat" probabilities (1/3 and 2/3) are the limiting frequencies of very different experiments. There is no contradiction in the two distributions because they are talking about different things. 1/2 is the limiting frequency of drawing, flipping, and re-drawing; 1/3 or 2/3 is what we get if we draw a coin and don't re-draw as we continue to flip (and we will find that we get each of those 1/2 of the time).

So, how do we formalise that? One way, which I particularly like, is to let the probability operator bind variables.

I'll use the notation P[x](A)=e to represent P binding variable x (where A is some statement with x as a free variable). Intuitively, the meaning is that if we choose x randomly, the statement A has probability e of being true. In addition, we can talk about choosing multiple variables simultaneously; this will be given notation like P[x,y,z](A)=e.

In this notation, the two principles become the following:

  • Expectation principle: If we have a higher-order distribution represented by a collection of statements P[x](P[y](A)=a)=b, P[x](P[y](A)=c)=d, et cetera, then we can form the first-order distribution P[x,y](A)=E[x](P[y](A)), where E[x](P[y](A)) is the expected value of P[y](A), choosing x randomly.
  • Lifting principle: If we know some statement A (possibly with free variables), we can conclude P[x](A)=1, for any variable. (Together with the expectation principle, this implies the related if-and-only-if statement from the paper I cited.)
With these rules, the argument from earlier has a different conclusion:


P[x](P[y](A)=1/3)=1/2
P[x](P[y](A)=2/3)=1/2
->
P[x,y](A)=1/2 via expectation,
->
P[z](P[x,y](A)=1/2)=1 via lifting.

This makes my earlier point about equivocation clear: the concluding probability is not about P[y](A) at all, but rather, is about P[x,y](A).

There are many details to fill out here; we'd like convenient notation for probability densities,  a proper analysis of what subjective probabilities are like in this system, and several other things. However, I feel these are better left to a paper rather than a blog post. :)

PS-- if anyone has references on similar systems, that'd be great!
PPS-- This paper talks about similar issues. :D

Sunday, December 5, 2010

Three Dreams

(1) I wish I had time to build self-education software. This is a wish carried over from my brother, who came up with the idea; a system which hands you exactly the practice problem you need at the moment, to challenge you, keep your interest, but not give you something you can't do. Ideally, the problem sets would be created and shared in a wiki-lije online community (which is the main difference from current high-end education software!) The broadness enabled by this could revolutionise education, job training, and certification. (Since the program estimates your skill level to determine what problem to give you, sitting potential employees down for a session on the machine would give valuable information about their abilities.)

(2) I would also like to have the time to build a powerful "open work" software in the spirit of mechanical turk, love machine, rentacoder, and others. The hope would be to emphasise love machine's social aspect, but mechanical turk's "all are welcome" aspect. Ideally, the environment would also feel like stack overflow-- you can build reputation by answering questions for free, so that you are more likely to get paid in the future. There are a lot of issues to be dealt with here! The nature of contracts, the details of any "reputation" system... it's complicated. However, it would be great for the efficiency of the intellectual labour market!

(3) I want to build a Bayesian reasoning system capable of acting as mankind's store of knowledge, so that all arguments for and against certain points can be kept track of and weighed properly against the evidence. This is the least realistic of the three dreams, but if it could replace/augment Wikipedia, it would help to end debates like global warming (or, rather, force the debate to proceed entirely from empirical evidence and in a logically correct manner). There are lots of big problems with this one, including the problem of verifying sources of empirical data.