trentmkelly/LessWrong-43k huggingface dataset:
Conditional Independence, and Naive Bayes
by Eliezer Yudkowsky — 2008-03-01T01:59:35.000Z

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.

The joint system (X,Y,Z) only has 16 possible states - since Z is just the question "Are X & Y even or odd?" - so H(X,Y,Z) = 4 bits.

But if you calculate the formula just given, you get

(3 + 2 + 1 - 1 - 1 - 1)bits = 3 bits = WRONG!

Why? Because if you have the mutual information between X and Z, and the mutual information between Z and Y, that may include some of the same mutual information that we'll calculate exists between X and Y. In this case, for example, knowing that X is even tells us that Z is even, and knowing that Z is ev...
Searching for Bayes-Structure
by Eliezer Yudkowsky — 2008-02-28T22:01:36.000Z

"Gnomish helms
should not function. Their very construction seems to defy the nature
of thaumaturgical law. In fact, they are impossible. Like most
products of gnomish minds, they include a large number of bells and
whistles, and very little substance. Those that work usually have a minor helm contained within, always hidden away, disguised to appear innocuous and inessential."
-- Spelljammer campaign set

We have seen that knowledge implies mutual information between a mind and its environment, and we have seen that this mutual information is negentropy
in a very physical sense: If you know where molecules are and how fast
they're moving, you can turn heat into work via a Maxwell's Demon /
Szilard engine.

We have seen that forming true beliefs without evidence
is the same sort of improbability as a hot glass of water spontaneously
reorganizing into ice cubes and electricity. Rationality takes "work"
in a thermodynamic sense, not just the sense of mental effort; minds
have to radiate heat if they are not perfectly efficient. This
cognitive work is governed by probability theory, of which
thermodynamics is a special case. (Statistical mechanics is a special
case of statistics.)

If you saw a machine continually spinning a wheel, apparently
without being plugged into a wall outlet or any other source of power,
then you would look for a hidden battery, or a nearby broadcast power
source - something to explain the work being done, without violating
the laws of physics.

So if a mind is arriving at true beliefs, and we assume that the second law of thermodynamics has not been violated, that mind must be doing something at least vaguely Bayesian - at least one process with a sort-of Bayesian structure somewhere - or it couldn't possibly work.

In the beginning, at time T=0, a mind has no mutual information with
a subsystem S in its environment. At time T=1,the mind has 10 bits of
mutual information with S. Somewhere in between, the mind must have
encountered evidence - under the Bayesian definition of evidence,
because all Bayesian evidence is mutual information and all mutual
information is Bayesian evidence, they are just different ways of
looking at it - and processed at least some of that evidence, however
inefficiently, in the r...
Perpetual Motion Beliefs
by Eliezer Yudkowsky — 2008-02-27T20:22:06.000Z

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?

It may help to think of it this way - if you still have some lingering intuition that uncertain beliefs are not authoritative:

In
reality, there may be a very small chance that the egg spontaneously
reforms. But you cannot expect it to reform. You must expect it to smash. Your mandatory belief is that the egg's probability of spontaneous reformation is ~0. Probabilities are not certainties, but the laws of probability are theorems.

If you doubt this, try dropping an egg on the floor
a few decillion times, ign...
The Second Law of Thermodynamics, and Engines of Cognition
by Eliezer Yudkowsky — 2008-02-27T00:48:30.000Z

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...
Leave a Line of Retreat
by Eliezer Yudkowsky — 2008-02-25T23:57:58.000Z

When you surround the enemy

Always allow them an escape route.

They must see that there is

An alternative to death.

—Sun Tzu, The Art of War

Don’t raise the pressure, lower the wall.

—Lois McMaster Bujold, Komarr

I recently happened into a conversation with a nonrationalist who had somehow wandered into a local rationalists’ gathering. She had just declared (a) her belief in souls and (b) that she didn’t believe in cryonics because she believed the soul wouldn’t stay with the frozen body. I asked, “But how do you know that?”

From the confusion that flashed on her face, it was pretty clear that this question had never occurred to her. I don’t say this in a bad way—she seemed like a nice person without any applied rationality training, just like most of the rest of the human species.

Most of the ensuing conversation was on items already covered on Overcoming Bias—if you’re really curious about something, you probably can figure out a good way to test it, try to attain accurate beliefs first and then let your emotions flow from that, that sort of thing. But the conversation reminded me of one notion I haven’t covered here yet:

“Make sure,” I suggested to her, “that you visualize what the world would be like if there are no souls, and what you would do about that. Don’t think about all the reasons that it can’t be that way; just accept it as a premise and then visualize the consequences. So that you’ll think, ‘Well, if there are no souls, I can just sign up for cryonics,’ or ‘If there is no God, I can just go on being moral anyway,’ rather than it being too horrifying to face. As a matter of self-respect, you should try to believe the truth no matter how uncomfortable it is, like I said before; but as a matter of human nature, it helps to make a belief less uncomfortable, before you try to evaluate the evidence for it.”

The principle behind the technique is simple: as Sun Tzu advises you to do with your enemies, you must do with yourself—leave yourself a line of retreat, so that you will have less trouble retreating. The prospect of losing your job, for example, may seem a lot more scary when you can’t even bear to think about it than after you have calculated exactly how long your savings will last, and checked the job market in your area, and otherwise planned out exactly what to do next. Only then will you be ready to fairly assess the probability of keeping your job in...
Superexponential Conceptspace, and Simple Words
by Eliezer Yudkowsky — 2008-02-24T23:59:28.000Z

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?

A machine learner might represent one concept that fits this data as follows:

Sky: ?; AirTemp: Warm; Humidity: High; Wind: ?

In this format, to determine whether this concept accepts or rejects an example, we compare element-by-element: ? accepts anything, but a specific value accepts only that specific value.

So the concept above will accept only Days with AirTemp=Warm and Humidity=High, but the Sky and the Wind can take on any value.&n...
Mutual Information, and Density in Thingspace
by Eliezer Yudkowsky — 2008-02-23T19:14:34.000Z

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 23 = 8 and 22 = 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?

In particular, let's suppose that X and Y are either both odd, or both even.

Now if we receive a 3-bit message (ask 3 questions) and learn that X is in state 5, we know that Y is in state 1 or state 3, but not state 2 or state 4. So the single additional question "Is Y in state 3?", answered "No", tells us the entire state of (X,Y): X=X5, Y=Y1. And we learned this with a total of 4 questions.

Conversely, if we learn that Y is in state 4 using two questions, it will take us only an additional two questions to learn whether X is in state 2, 4, 6, or 8. Again, four questions to learn the state of the joint system.

The mutual information of two variables is defined as the difference between the entropy of the joint system and the entropy of the independent systems: I(X;Y) = H(X) + H(Y) - H(X,Y).

Here there is one bit of mutual information between the two systems: Learning X tells us one bit of information about Y (cuts down the space of possibilities from 4 to 2, a factor-of-2 decrease in the volume) and learning Y tells us one bit of information about X (cuts down the possibility space from 8 to 4).

What about w...
Entropy, and Short Codes
by Eliezer Yudkowsky — 2008-02-23T03:16:50.000Z

Suppose you have a system X that's equally likely to be in any of 8 possible states:

{X1, X2, X3, X4, X5, X6, X7, X8.}

There's an extraordinarily ubiquitous quantity—in physics, mathematics, and even biology—called entropy; and the entropy of X is 3 bits. This means that, on average, we'll have to ask 3 yes-or-no questions to find out X's value. For example, someone could tell us X's value using this code:

X1: 001
X2: 010
X3: 011
X4: 100

X5: 101
X6: 110
X7: 111
X8: 000

So if I asked "Is the first symbol 1?" and heard "yes", then asked "Is the second symbol 1?" and heard "no", then asked "Is the third symbol 1?" and heard "no", I would know that X was in state 4.

Now suppose that the system Y has four possible states with the following probabilities:

Y1: 1/2 (50%)
Y2: 1/4 (25%)
Y3: 1/8 (12.5%)
Y4: 1/8 (12.5%)

Then the entropy of Y would be 1.75 bits, meaning that we can find out its value by asking 1.75 yes-or-no questions.

What does it mean to talk about asking one and three-fourths of a question? Imagine that we designate the states of Y using the following code:

Y1: 1
Y2: 01
Y3: 001
Y4: 000

First you ask, "Is the first symbol 1?" If the answer is "yes", you're done: Y is in state 1. This happens half the time, so 50% of the time, it takes 1 yes-or-no question to find out Y's state.

Suppose that instead the answer is "No". Then you ask, "Is the second symbol 1?" If the answer is "yes", you're done: Y is in state 2. Y is in state 2 with probability 1/4, and each time Y is in state 2 we discover this fact using two yes-or-no questions, so 25% of the time it takes 2 questions to discover Y's state.

If the answer is "No" twice in a row, you ask "Is the third symbol 1?" If "yes", you're done and Y is in state 3; if "no", you're done and Y is in state 4. The 1/8 of the time that Y is in state 3, it takes three questions; and the 1/8 of the time that Y is in state 4, it takes three questions.

(1/2 * 1) + (1/4 * 2) + (1/8 * 3) + (1/8 * 3)
= 0.5 + 0.5 + 0.375 + 0.375
= 1.75.

The general formula for the entropy of a system S is the sum, over all Si, of -p(Si)*log2(p(Si)).

For example, the log (base 2) o...
Where to Draw the Boundary?
by Eliezer Yudkowsky — 2008-02-21T19:14:17.000Z

The one comes to you and says:

Long have I pondered the meaning of the word "Art", and at last I've found what seems to me a satisfactory definition: "Art is that which is designed for the purpose of creating a reaction in an audience."

Just because there's a word "art" doesn't mean that it has a meaning, floating out there in the void, which you can discover by finding the right definition.

It feels that way, but it is not so.

Wondering how to define a word means you're looking at the problem the wrong way—searching for the mysterious essence of what is, in fact, a communication signal.

Now, there is a real challenge which a rationalist may legitimately attack, but the challenge is not to find a satisfactory definition of a word. The real challenge can be played as a single-player game, without speaking aloud. The challenge is figuring out which things are similar to each other—which things are clustered together—and sometimes, which things have a common cause.

If you define "eluctromugnetism" to include lightning, include compasses, exclude light, and include Mesmer's "animal magnetism" (what we now call hypnosis), then you will have some trouble asking "How does electromugnetism work?" You have lumped together things which do not belong together, and excluded others that would be needed to complete a set. (This example is historically plausible; Mesmer came before Faraday.)

We could say that electromugnetism is a wrong word, a boundary in thingspace that loops around and swerves through the clusters, a cut that fails to carve reality along its natural joints.

Figuring where to cut reality in order to carve along the joints—this is the problem worthy of a rationalist. It is what people should be trying to do, when they set out in search of the floating essence of a word.

And make no mistake: it is a scientific challenge to realize that you need a single word to describe breathing and fire. So do not think to consult the dictionary editors, for that is not their job.

What is "art"? But there is no essence of the word, floating in the void.

Perhaps you come to me with a long list of the things that you call "art" and "not art":

The Little Fugue in G Minor: Art.
A punch in the nose: Not art.
Escher's Relativity: Art.
A flower: Not art.
The Python programming language: Art.
A

...
Arguing "By Definition"
by Eliezer Yudkowsky — 2008-02-20T23:37:56.000Z

"This plucked chicken has two legs and no feathers—therefore, by definition, it is a human!"

When people argue definitions, they usually start with some visible, known, or at least widely believed set of characteristics; then pull out a dictionary, and point out that these characteristics fit the dictionary definition; and so conclude, "Therefore, by definition, atheism is a religion!"

But visible, known, widely believed characteristics are rarely the real point of a dispute. Just the fact that someone thinks Socrates's two legs are evident enough to make a good premise for the argument, "Therefore, by definition, Socrates is human!" indicates that bipedalism probably isn't really what's at stake—or the listener would reply, "Whaddaya mean Socrates is bipedal? That's what we're arguing about in the first place!"

Now there is an important sense in which we can legitimately move from evident characteristics to not-so-evident ones. You can, legitimately, see that Socrates is human-shaped, and predict his vulnerability to hemlock. But this probabilistic inference does not rely on dictionary definitions or common usage; it relies on the universe containing empirical clusters of similar things.

This cluster structure is not going to change depending on how you define your words. Even if you look up the dictionary definition of "human" and it says "all featherless bipeds except Socrates", that isn't going to change the actual degree to which Socrates is similar to the rest of us featherless bipeds.

When you are arguing correctly from cluster structure, you'll say something like, "Socrates has two arms, two feet, a nose and tongue, speaks fluent Greek, uses tools, and in every aspect I've been able to observe him, seems to have every major and minor property that characterizes Homo sapiens; so I'm going to guess that he has human DNA, human biochemistry, and is vulnerable to hemlock just like all other Homo sapiens in whom hemlock has been clinically tested for lethality."

And suppose I reply, "But I saw Socrates out in the fields with some herbologists; I think they were trying to prepare an antidote. Therefore I don't expect Socrates to keel over after he drinks the hemlock—he will be an exception to the general behavior of objects in his cluster: they did not take an antidote, and he did."

Now there's not much point ...