pfh's blog

~ 1% inspiration, 99% perseveration ~

4 May 2008, 0:17 UTCInsane prisoner's dilemma
Two perfectly rational human prisoners, let us call them Alice and Bob, have been caught and are about to be interrogated. In the meantime they are both being kept in the one cell.

The outcome will be as per normal prisoner's dilemma. If neither confesses, they both win. If one confesses and the other does not, the first one wins a lot and the second loses. If they both confess, they both lose. They will never meet again.

If this were normal prisoner's dilemma, the outcome game theory predicts is that they both confess. It doesn't matter how much they confer before hand, the game is set up so that this is the rational thing to do.

However, being human, we shall suppose they have a novel ability and a novel option while they are in the cell:

They can tell what motivates the other player, which will be some linear combination of both of the players outcomes. Of course initially both prisoners only care about their own outcome.

They can choose to go insane, modifying their own motivation to be a new linear combination of their own outcome and the other player's. From then on their actions will be guided by that new motivation (possibly to their detriment!). Note that their actions will only be irrational from the perspective of their initial motivation. From the perspective of their new motivation, their actions from then on will be perfectly rational.

If we only allow a limited set of linear combinations, working out the player's actions becomes fairly easy to solve.

What will happen is this: One of the players, say Alice, goes insane to the extent that, to her, the game becomes a coordination game. She will then not confess if she knows that Bob will not confess. Bob, seeing this, will also go insane to the same extent. The problem is now a coordination problem, and they have common knowledge that they both do not want to confess. So they don't confess, and both win.

[permalink]

25 April 2008, 13:53 UTCIntelligent design for the evangelical atheist
Continuing on from "Why go insane?".

Jared Diamond has written up a fascinating set of stories about revenge. What I hope is striking is that people can hold completely alien moral codes, and that in primitive societies these are actually pretty dysfunctional.

A couple more examples of alien moral codes. The Chinese attitude to pets is somewhat different. Disgusted? Good. Now think about how a vegan views you. And of course our own culture is not free from change.

So perhaps your own moral code, despite being obviously correct, is actually a result of taking the conclusion your culture requires and backfilling an argument. Sure, it seems to hang together, but at some point there's a little note that definitely does not say "then a miracle occurs". Maybe it's that people can somehow transcend their evolved natures now they have brains. Maybe it's that there's been some kind of weird evolutionary accident that left us all jolly nice people. Maybe there's some kind of moral zeitgeist, whatever that means. Maybe it is that contrary to all reason group selection is actually a strong effect. Maybe being able to understand the motivations of other creatures will make us love them, rather than just letting us exploit them more efficiently. Maybe it's super-rationality a la Hofstadter.

People are nice, therefore <my pet theory> is true. This is progess over "people are nice because God"? Please stop, it's embarassing.

Your moral code has no more foundation than any other, but that is fine, flying is actually pretty straightforward. The proper test of a moral code is whether it results in a society that is to the benefit of its members. It is perfectly valid to pull a whole belief system from your posterior, if it passes this test.

In fact this is business as usual. The 10 commandments are awfully useful. They were probably designed by committee. Same goes for most religious constructs. People choose to believe in them because they work.

You're not going to arrive at the one true moral code by pure reason. You're not going to find it by introspection. Science is silent on the subject. It's not going to be handed to you on a silver platter. You're going to have to damn well design it yourself.

Or wait for some more practical brand of insanity to wipe you from the face of the Earth.

So, um, that's the general outline of the whole "insanity" thing. Obviously it needs a bit more fleshing out. I'm confident that all the various forms of "then a miracle occurs" are indefensible, but each of them is topic unto itself. The idea that other people can have radically different moral codes, and consider them just as natural as one's own, seems to be a common blindspot [1]. I need more examples of these, and more depth to the examples -- how they differ at a fundamental level, and why they still work.

[1] Two defenses employed here: 1. Labeling beliefs "memes" allow different beliefs to be dismissed as hostile infections. 2. Conspiracy theories allow people's actions to be blamed on coercion and disinformation.

[permalink]

13 April 2008, 10:39 UTCRobust topological sorting and Tarjan's algorithm in Python
The Strongly Connected Components of a directed graph are subsets of nodes such that each node within a subset can be reached from each other node. Tarjan's algorithm can identify these components efficiently (thanks njh for finding this algorithm).

By identifying strongly connected components ahead of time we can create a topological sorting algorithm that does the best it can in the presence of cycles.

Here is an implementation in Python:

sort.py

Here are some things you might use this for:

Install packages with circular dependencies in the best order you can.

Work out in which order a set of equations must be solved, and which must be solved simultaneously.

In a revision control system align as well as possible many versions of a file. (This is basically what I am using this for, but with DNA.)

[permalink]

12 April 2008, 0:28 UTCA Nokia phone has crashed
I recently bought a mobile phone from a company called Nokia. This company has a good reputation for making mobile phones, and has been doing some great work getting Linux onto some of their phones as well. So it is with some small sadness, but also with firmness of resolve in doing what is right, that I must now report the following:

That the phone that I purchased crashed.

The crash was apparently due to a software fault, and occurred while receiving an SMS.

What must happen now is by the laws of natural justice inevitable. In their hubris they allowed their standards to slip so far as to ship a product with a software defect, and now they must pay the price. It is time for Nokia to get out of the mobile phone business.

[permalink]

7 April 2008, 6:27 UTCAMOS message reader/writer module for Python
(of interest to bioinformaticians, and few others)

AMOS (A Modular Open-Source Assembler) defines a standard message format for describing DNA sequence assemblies. It has a Perl module for reading these assemblies, but no Python module.

Shock! This must be rectified, forthwith!

amos.py

I am currently using this module to import Newbler assemblies of 454 data into AMOS. The quality data is thoroughly b0rked. If anyone has any experience with this, please contact me.

[permalink]

26 February 2008, 22:30 UTCModern anti-depressants such as Prozac are ineffective

Initial Severity and Antidepressant Benefits: A Meta-Analysis of Data Submitted to the Food and Drug Administration Kirsch I, Deacon BJ, Huedo-Medina TB, Scoboria A, Moore TJ, et al. PLoS Medicine Vol. 5, No. 2, e45 doi:10.1371/journal.pmed.0050045

Drug-placebo differences in antidepressant efficacy increase as a function of baseline severity, but are relatively small even for severely depressed patients. The relationship between initial severity and antidepressant efficacy is attributable to decreased responsiveness to placebo among very severely depressed patients, rather than to increased responsiveness to medication.

Now who thinks this will actually stop doctors from fucking over many of my friends and colleagues?

Give your doctor a notepad to write on. Give them a pen. Given them a fluffy toy and a mousepad. Give them some patient data tracking software that doesn't display ads [1]. Doctors are so poor, they have to sell their patients to drug companies just to have these necessary things.

And give them a copy of this paper.

[1] Not joking. At least at Monash University, the GPs use patient data tracking software that displays drug ads.

[permalink]

23 February 2008, 10:51 UTCIntroducing Myrialign - align short reads to a reference genome
Monash has just bought a short read genome sequencer which is about to start throwing great gobs of data in my general direction. To deal with this looming deluge, I've started writing some bits and pieces of (mostly) Python code. These are going into a Savannah project called Myrialign.

The major component at this stage is a utility to align short reads to a reference genome, a common first step when analysing short read data. An alignment can contain any number of SNPs, insertions and deletions, up to a user specified cutoff.

One cute thing I'm doing with this is some extreme bit-parallelism. A single alignment can be writen as a logical expression. Either two things align, or they don't (if they do you go back and work out how, but this is infrequent and is therefore allowed to be slow). We could perform each of the operations required to evaluate this logical expression for each pair of sequences we want to align, but it is possible to do much better. Instead, we can pack 32 (or 64 or 128, depending on architecture) independent alignments into a machine word, and perform the operations on this. Bingo, 32x parallelism!

We may be able to do better still with vector operations. Even with bit-parallelism, we can still get pipeline stalls waiting for operations to complete. It may actually be better to work with many words worth of alignements at once. Performing a vector logical operation isn't going to stall the pipeline. When performing vector operations, the CPU will be able to easily predict what data it will need to load ahead of time. Any housekeeping gets amortized across more alignments. It will at the least be no worse to do this.

This assumes we are able to pump data in and out of memory as fast as we can operate on it. From what I have read on the memory hierachy (someone please correct me if I am wrong), while latency gets progressively worse the further down the cache hierachy one goes, throughput only starts to suffer once you hit main memory. And with vector operations, it's throughput we're interested in here. When your vectors are large enough, latency doesn't matter.

Suddenly, Python and Numpy become a competitive option.

The other cute thing: It really screams on a PlayStation 3. I'm trying to convince my department that it needs a cluster of them.

[permalink]

27 January 2008, 21:34 UTCWhy go insane? Some preliminary notes
The ability to go insane is certainly something that could evolve, if it had some utility. For a rational agent with a certain utility function, the act of going insane would entail some combination of:

1. Modifying its own beliefs.

2. Modifying its own utility function.

One might suppose that an agent having such an ability would simply decide to believe "whatever happens, I win". However, this is not something that should evolve. A rational agent should only decide to go insane if it believes that doing so is in its best interests from the point of view of its current beliefs and utility function.

Still, on the face of it, both of these are incredibly stupid things to do. If you believe something that is not true, you might act on the basis of that belief and do something that harms your interests. Modifying your utility function is even worse, you are unlikely to maximize your initial "true" utility function by maximizing some different utility function.

However, suppose that this agent is interacting with other agents that have some ability to read its mind. I'm not supposing telepathy, just the ability to infer internal thought processes from the agent's actions. To make this easier, they might first take the agent down to the pub and get it drunk. Humans do seem to have some ability to do this.

This creates the possibility, the agent will know, of others responding not only to its actions but to its beliefs and goals.

One nice thing about the ability to go insane is that it provides the start of an explanation of where utility functions come from. When making an AI, one has to specify a utility function, and it is hard to consider an AI with a fixed utility function as being truly intelligent or conscious, even if that utility function has been artificially evolved. However an AI that can change its goals maybe is in with a chance.

In a society of such agents, is there a fixed point for the utility function? Will any society of agents with this ability tend to some specific utility function? This would seem to be our society's inescapable fate, so let's hope it is a nice one. I am cautiously optimistic.

By the way, there are a number of basic misconceptions that need to be addressed before having a sensible discussion about this topic:

A group of selfish rational agents does not itself act in a selfish rational way. This can be shown by inventing some (non-zero-sum) games and determining the actions rational players will make -- their actions will usually not maximize overall utility. This is a straightforward consequence of game theory, and should not be surprising. What is surprising, and should be a cause of hope, is that humans sometimes do not behave as game theory predicts.
- The genetic corollary: A population of identical genes that have undergone natural selection will not act in the common interest of that population except by accident. Instead, such a population is best thought of as the environment in which further evolution may occur. A mutant gene may arise that exploits the existing population, making many copies of itself in a way that happens to be to the detriment of the original population of genes.

As group rationality and individual rationality are different things, our modern gas-guzzling McDonald's eating flamboyantly wasteful consumer society may be represent a return to (individual) rationality, rather than a departure from it.

Group selection is nonsense, there is only kin selection, and kin selection is quite a weak effect in humans. See the "Selfish Gene" by Dawkins. Kin selection is a strong effect in social insects due to the way they breed (all genes in the hive are only ever passed on via the queen and a small number of fertile males), this should not be taken as evidence of true altruism in nature.

There is no Gaia. Nature exists in a state of equilibreum, but not of overall optimality. Where apparent altruism exists in nature, it is usually either a kin selection effect or reciprocal altruism. Humans have done a lot of damage, but only by being successful. Any similarly successful species would do a similar amount of damage, there is no natural mechanism to prevent this. Humanity is no more "sinful" than any other species would be given the opportunity.

Genes that cause behaviors are not memes. Memes replicate by means other than sexual reproduction. When I talk about evolved abilities and goals, this is plain old Darwinian evolution of DNA.

Finally, there is sometimes a notion that once a human level of intelligence is achieved, we can somehow transcend these mechanistic game theoretic models of behavior. Peter Singer is one person I've seen play with this opinion. I'm not sure if Dawkins goes that far too. Christians are pretty keen on it. Free will.

A non-mechanistic theory is (I think) necessarily not a comprehensible one, nor one that can be conveyed by language. I can't prove that there is not something like this at work, I'm not even sure how to go about asking the right question about it. What I am hoping to show is that it is not a necessary thing to suppose. We can form an argument that some kind of motivation higher than pure selfishness will bootstrap itself into existance without the help of a by-definition-incomprehensible influence.

[permalink]

15 January 2008, 7:39 UTCRandom color scheme generator

Based on my previous post, I have written a javascript random color scheme generator. It uses CIELAB color space to accurately model opponent-process color perception. For each of the opposing pairs (dark/light, red/green, yellow/blue), one color will be extreme, and one will be middling. I've allowed all possible permutations of these assignments.

Inspire me!

Using the parameters I've chosen, the following color combinations are possible:

red/green/purple/cyan + colorless
Colors extreme in both color dimensions must be matched against a colorless shade.

blue/yellow + aqua/magenta
A color extreme in one dimension must be matched against a color extreme in the other dimension.

Additionally, there will be a contrast of dark or light against middling brightness.

Update: After discussing some of these schemes with ctwardy, I've added a further rule: for the red/green/purple/cyan+colorless schemes, the body of the text must be the colorless one.

Appendix: Rarely used color terms

A bluish cyan and a light blue:

We tend not to distinguish between cyan and light blue, which is a pity because light blue is an awesome color.

Magenta, another rarely used color term:

Don't confuse dark magenta (aka Tyrian purple) with dark red or purple.

Both Tyrian purple and what we now call purple have been associated with richness and royalty, but Tyrian purple would be contrasted with gold, whereas our modern purple would be contrasted with white.

[permalink]

11 December 2007, 8:31 UTCA rest from opponent process
See next blog post for a more fully developed theory >>

Opponent process theory holds that the brain processes color by contrasting black and white, red and green, and yellow and blue.

I propose that a good color scheme is one that gives the eye a refuge from each of these oppositions.