Monthly Archives: February 2008

< ?xml version="1.0" standalone="yes"?> < !DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">

Followup to:  Searching for Bayes-Structure

Previously I spoke of mutual information between X and Y, I(X;Y), which is the difference between the entropy of the joint probability distribution, H(X,Y) and the entropies of the marginal distributions, H(X) + H(Y).

I gave the example of a variable X, having eight states 1..8 which are all equally probable if we have not yet encountered any evidence; and a variable Y, with states 1..4, which are all equally probable if we have not yet encountered any evidence.  Then if we calculate the marginal entropies H(X) and H(Y), we will find that X has 3 bits of entropy, and Y has 2 bits.

However, we also know that X and Y are both even or both odd; and this is all we know about the relation between them.  So for the joint distribution (X,Y) there are only 16 possible states, all equally probable, for a joint entropy of 4 bits.  This is a 1-bit entropy defect, compared to 5 bits of entropy if X and Y were independent.  This entropy defect is the mutual information – the information that X tells us about Y, or vice versa, so that we are not as uncertain about one after having learned the other.

Suppose, however, that there exists a third variable Z.  Z has two states, “even” and “odd”, perfectly correlated to the evenness or oddness of (X,Y).  In fact, we’ll suppose that Z is just the question “Are X and Y even or odd?”

If we have no evidence about X and Y, then Z itself necessarily has 1 bit of entropy on the information given.  There is 1 bit of mutual information between Z and X, and 1 bit of mutual information between Z and Y.  And, as previously noted, 1 bit of mutual information between X and Y.  So how much entropy for the whole system (X,Y,Z)?  You might naively expect that

H(X,Y,Z) = H(X) + H(Y) + H(Z) – I(X;Z) – I(Z;Y) – I(X;Y)

but this turns out not to be the case.

Continue reading "Conditional Independence, and Naive Bayes" »

Followup to:  The Second Law of Thermodynamics, and Engines of Cognition

Yesterday’s post concluded:

To form accurate beliefs about something, you really do have to observe it. It’s a very physical, very real process: any rational mind does "work" in the thermodynamic sense, not just the sense of mental effort…  So unless you can tell me which specific step in your argument violates the laws of physics by giving you true knowledge of the unseen, don’t expect me to believe that a big, elaborate clever argument can do it either.

One of the chief morals of the mathematical analogy between thermodynamics and cognition is that the constraints of probability are inescapable; probability may be a "subjective state of belief", but the laws of probability are harder than steel.

People learn under the traditional school regimen that the teacher tells you certain things, and you must believe them and recite them back; but if a mere student suggests a belief, you do not have to obey it.  They map the domain of belief onto the domain of authority, and think that a certain belief is like an order that must be obeyed, but a probabilistic belief is like a mere suggestion.

They look at a lottery ticket, and say, "But you can’t prove I won’t win, right?"  Meaning:  "You may have calculated a low probability of winning, but since it is a probability, it’s just a suggestion, and I am allowed to believe what I want."

Here’s a little experiment:  Smash an egg on the floor.  The rule that says that the egg won’t spontaneously reform and leap back into your hand is merely probabilistic.  A suggestion, if you will.  The laws of thermodynamics are probabilistic, so they can’t really be laws, the way that "Thou shalt not murder" is a law… right?

So why not just ignore the suggestion?  Then the egg will unscramble itself… right?

Continue reading "Perpetual Motion Beliefs" »

Followup to:  Superexponential Conceptspace, and Simple Words

The first law of thermodynamics, better known as Conservation of Energy, says that you can’t create energy from nothing: it prohibits perpetual motion machines of the first type, which run and run indefinitely without consuming fuel or any other resource.  According to our modern view of physics, energy is conserved in each individual interaction of particles.  By mathematical induction, we see that no matter how large an assemblage of particles may be, it cannot produce energy from nothing – not without violating what we presently believe to be the laws of physics.

This is why the US Patent Office will summarily reject your amazingly clever proposal for an assemblage of wheels and gears that cause one spring to wind up another as the first runs down, and so continue to do work forever, according to your calculations.  There’s a fully general proof that at least one wheel must violate (our standard model of) the laws of physics for this to happen.  So unless you can explain how one wheel violates the laws of physics, the assembly of wheels can’t do it either.

A similar argument applies to a "reactionless drive", a propulsion system that violates Conservation of Momentum.  In standard physics, momentum is conserved for all individual particles and their interactions; by mathematical induction, momentum is conserved for physical systems whatever their size.  If you can visualize two particles knocking into each other and always coming out with the same total momentum that they started with, then you can see how scaling it up from particles to a gigantic complicated collection of gears won’t change anything.  Even if there’s a trillion quadrillion atoms involved, 0 + 0 + … + 0 = 0.

But Conservation of Energy, as such, cannot prohibit converting heat into work.  You can, in fact, build a sealed box that converts ice cubes and stored electricity into warm water.  It isn’t even difficult.  Energy cannot be created or destroyed:  The net change in energy, from transforming (ice cubes + electricity) to (warm water), must be 0.  So it couldn’t violate Conservation of Energy, as such, if you did it the other way around…

Perpetual motion machines of the second type, which convert warm water into electrical current and ice cubes, are prohibited by the Second Law of Thermodynamics.

The Second Law is a bit harder to understand, as it is essentially Bayesian in nature.

Yes, really.

Continue reading "The Second Law of Thermodynamics, and Engines of Cognition" »

Followup to:  Mutual Information, and Density in Thingspace

Thingspace, you might think, is a rather huge space.  Much larger than reality, for where reality only contains things that actually exist, Thingspace contains everything that could exist.

Actually, the way I "defined" Thingspace to have dimensions for every possible attribute – including correlated attributes like density and volume and mass – Thingspace may be too poorly defined to have anything you could call a size.  But it’s important to be able to visualize Thingspace anyway.  Surely, no one can really understand a flock of sparrows if all they see is a cloud of flapping cawing things, rather than a cluster of points in Thingspace.

But as vast as Thingspace may be, it doesn’t hold a candle to the size of Conceptspace.

"Concept", in machine learning, means a rule that includes or excludes examples.  If you see the data 2:+, 3:-, 14:+, 23:-, 8:+, 9:- then you might guess that the concept was "even numbers".  There is a rather large literature (as one might expect) on how to learn concepts from data… given random examples, given chosen examples… given possible errors in classification… and most importantly, given different spaces of possible rules.

Suppose, for example, that we want to learn the concept "good days on which to play tennis".  The possible attributes of Days are:

Sky:      {Sunny, Cloudy, Rainy}
AirTemp:  {Warm, Cold}
Humidity: {Normal, High}
Wind:     {Strong, Weak}

We’re then presented with the following data, where + indicates a positive example of the concept, and – indicates a negative classification:

+   Sky: Sunny;  AirTemp: Warm;  Humidity: High;  Wind: Strong.
-   Sky: Rainy;  AirTemp: Cold;  Humidity: High;  Wind: Strong.
+   Sky: Sunny;  AirTemp: Warm;  Humidity: High;  Wind: Weak.

What should an algorithm infer from this?

Continue reading "Superexponential Conceptspace, and Simple Words" »

Continuation of:  Entropy, and Short Codes

Suppose you have a system X that can be in any of 8 states, which are all equally probable (relative to your current state of knowledge), and a system Y that can be in any of 4 states, all equally probable.

The entropy of X, as defined yesterday, is 3 bits; we’ll need to ask 3 yes-or-no questions to find out X’s exact state.  The entropy of Y, as defined yesterday, is 2 bits; we have to ask 2 yes-or-no questions to find out Y’s exact state.  This may seem obvious since 2³ = 8 and 2² = 4, so 3 questions can distinguish 8 possibilities and 2 questions can distinguish 4 possibilities; but remember that if the possibilities were not all equally likely, we could use a more clever code to discover Y’s state using e.g. 1.75 questions on average.  In this case, though, X’s probability mass is evenly distributed over all its possible states, and likewise Y, so we can’t use any clever codes.

What is the entropy of the combined system (X,Y)?

You might be tempted to answer, "It takes 3 questions to find out X, and then 2 questions to find out Y, so it takes 5 questions total to find out the state of X and Y."

But what if the two variables are entangled, so that learning the state of Y tells us something about the state of X?

Continue reading "Mutual Information, and Density in Thingspace" »