Idle Speculations

Username:	Password:
Forgot your password?	Remember Me

parimutuel probability and recommendation elicitations
There's a simple way of doing betting pools - it's called parimutuel, but the name is unnecessarily off-putting. People mark money with their name and the outcome they're betting on, and drop it into a pool. When the race or whatever is over, they take the money out, and give the winners their money back. They divide the losing money among the winners, in direct proportion to amount of money that winner got back.

Suppose:

Person 1 put $1 on outcome A
Person 2 put $3 on outcome B
Person 3 put $1 on outcome A and $1 on outcome B.

If outcome A obtains, then person 1 gets their $1 back, and $2 of the losing $4. Person 3 gets $1 back, and $2 of the losing $4. If outcome B obtains, then person 2 gets their $3 back, and 75% of the losing $2 ($1.50), while person 3 gets their $1 back, and 25% of the losing $2 ($0.50).

Note that person 3 bet on both sides at once - this is hedging, and it's rational to hedge in many cases. Before person 3 bet, the pool may have stood at $1 on A and $3 on B. We can figure out how much a $1 bet would payout. If you put in $1 on A, and A occurred, you would take out $2.50 (your bet plus half of the $3 on B). If you put in $1 on B, and B occurred, you would take out $1.25 (your bet plus one quarter of the $1 on A). Suppose that person 3 believed that B had a probability of 55%. Then, in choosing where to put the first dollar, they're choosing between a 55% chance of 1.25 ($0.68 expected value) and a 45% chance of $2.50 ($1.12 expected value). So they bet on A - even though they believe that B is more likely.

The best bets in the parimutuel system are the ones that move the pool's probability distribution toward the truth.

We can use this system to do probability elicitation. Suppose you have a collection of individuals, some of whom are experts, and you want to pay the experts for predicting the future for you - but you don't know which are the experts. Give them certificates, worth a dollar each, but only if the certificate is bet first.

How can you turn this system from prediction to recommendation? You have several actions (not outcomes), and you want to crowdsource the problem of choosing among them. You could try to formulate the recommendation as a prediction problem something like "Supposing that we take action A, how much reward would we get?" Of course, we don't want to take the action with the most immediate reward - that would be shortsighted. We're interested in the long-term consequences of our actions. So it might be easiest to express the question as: "Supposing that we take action A, where would you like your assets allocated - in cash, or in stock certificates that pay dividends proportional to the reward signal?".

This market-based thing seems complicated and slow and prone to friction if it were implemented as interactions among humans - but if the market and the agents are all software, then it might be an excellent way to organize multiple competing systems. High-performance compression algorithms may already work this way, with specialist "agents" in image-prediction, text-prediction, and executable-binary-prediction cooperating by tweaking a probability distribution representing the next bit or byte.

notes to self
A vague idea for a learning algorithm based on inductive bias learning by repeatedly listing strings from a context free grammar in shortest-first order, evaluating them according to some figure of merit, and then tweaking the context free grammar to pull the high-merit strings forward in the the list, and push the low-merit strings backward.
( Read more... )

A clumsy sqlite-based quine

#include <assert.h>
#include <stdio.h>
#include <sqlite3.h>
const char* payload[] = {
"create table payload (line integer primary key, content text);",
"insert into payload (content) values('#include <assert.h>');",
"insert into payload (content) values('#include <stdio.h>');",
"insert into payload (content) values('#include <sqlite3.h>');",
"insert into payload (content) values('');",
"insert into payload (content) values('const char* payload[] = {');",
"insert into payload (content) values(' \"create table payload (line integer primary key, content text);\",');",
"insert into payload (content) values('};');",
"insert into payload (content) values('');",
"insert into payload (content) values('int main(int argc, char* argv[]) {');",
"insert into payload (content) values(' sqlite3* db;');",
"insert into payload (content) values(' int returncode;');",
"insert into payload (content) values('');",
"insert into payload (content) values(' returncode= sqlite3_open(\":memory:\", &db);');",
"insert into payload (content) values(' assert(returncode == SQLITE_OK);');",
"insert into payload (content) values('');",
"insert into payload (content) values(' int i;');",
"insert into payload (content) values(' for(i= 0; i < sizeof(payload)/sizeof(payload[0]); ++i) {');",
"insert into payload (content) values(' returncode= sqlite3_exec(db, payload[i], NULL, NULL, NULL);');",
"insert into payload (content) values(' assert(returncode == SQLITE_OK);');",
"insert into payload (content) values(' }');",
"insert into payload (content) values('');",
"insert into payload (content) values(' sqlite3_stmt* to_print;');",
"insert into payload (content) values(' returncode= sqlite3_prepare_v2(');",
"insert into payload (content) values(' db,');",
"insert into payload (content) values(' \"select content from (\"');",
"insert into payload (content) values(' \" select line, 0 as payload_line, content from payload\"');",
"insert into payload (content) values(' \" union\"');",
"insert into payload (content) values(' \" select 6.5 as line, line as payload_line,\"');",
"insert into payload (content) values(' \" '' \\\"insert into payload (content) values(''\"');",
"insert into payload (content) values(' \" || quote(\"');",
"insert into payload (content) values(' \" replace(\"');",
"insert into payload (content) values(' \" replace(\"');",
"insert into payload (content) values(' \" content,\"');",
"insert into payload (content) values(' \" ''\\\\'', ''\\\\\\\\''\"');",
"insert into payload (content) values(' \" ), ''\\\"'', ''\\\\\\\"''\"');",
"insert into payload (content) values(' \" )\"');",
"insert into payload (content) values(' \" )\"');",
"insert into payload (content) values(' \" || '');\\\",'' as content from payload\"');",
"insert into payload (content) values(' \") order by line, payload_line;\",');",
"insert into payload (content) values(' -1,');",
"insert into payload (content) values(' &to_print,');",
"insert into payload (content) values(' NULL');",
"insert into payload (content) values(' );');",
"insert into payload (content) values(' assert(returncode == SQLITE_OK);');",
"insert into payload (content) values('');",
"insert into payload (content) values(' while((returncode= sqlite3_step(to_print)) == SQLITE_ROW) {');",
"insert into payload (content) values(' printf(\"%s\\n\", sqlite3_column_text(to_print, 0));');",
"insert into payload (content) values(' }');",
"insert into payload (content) values(' assert(returncode == SQLITE_DONE);');",
"insert into payload (content) values('');",
"insert into payload (content) values(' returncode= sqlite3_finalize(to_print);');",
"insert into payload (content) values(' assert(returncode == SQLITE_OK);');",
"insert into payload (content) values('');",
"insert into payload (content) values(' returncode= sqlite3_close(db);');",
"insert into payload (content) values(' assert(returncode == SQLITE_OK);');",
"insert into payload (content) values('');",
"insert into payload (content) values(' return 0;');",
"insert into payload (content) values('}');",
};
int main(int argc, char* argv[]) {
sqlite3* db;
int returncode;
returncode= sqlite3_open(":memory:", &db);
assert(returncode == SQLITE_OK);
int i;
for(i= 0; i < sizeof(payload)/sizeof(payload[0]); ++i) {
returncode= sqlite3_exec(db, payload[i], NULL, NULL, NULL);
assert(returncode == SQLITE_OK);
}
sqlite3_stmt* to_print;
returncode= sqlite3_prepare_v2(
db,
"select content from ("
" select line, 0 as payload_line, content from payload"
" union"
" select 6.5 as line, line as payload_line,"
" ' \"insert into payload (content) values('"
" || quote("
" replace("
" replace("
" content,"
" '\\', '\\\\'"
" ), '\"', '\\\"'"
" )"
" )"
" || ');\",' as content from payload"
") order by line, payload_line;",
-1,
&to_print,
NULL
);
assert(returncode == SQLITE_OK);
while((returncode= sqlite3_step(to_print)) == SQLITE_ROW) {
printf("%s\n", sqlite3_column_text(to_print, 0));
}
assert(returncode == SQLITE_DONE);
returncode= sqlite3_finalize(to_print);
assert(returncode == SQLITE_OK);
returncode= sqlite3_close(db);
assert(returncode == SQLITE_OK);
return 0;
}

In a near-term (weeks) exoshell-ish piece of software, there will probably be a core decision point where the exoshell decides what to do next, from options like "Compute further" and "Ask the human for help". Using the output of an existing POMDP solver for that core decision point might be reasonable.

The input to an existing POMDP solver is (if I understand correctly) something like a stochastic finite-state transducer with a distinguished "reward" signal in the output. The human would gradually edit this input, making it a more realistic (though still finite-state) approximation of the world (including the human). Then the solver would grind on the input, producing a holographic (fast to execute, if not particularly comprehensible) decision structure.

sql-based interpreter?
One of the standard ways to make a quine is like so:

#include <stdio.h>

char payload[] = {
  '\x62', '\x61', '\x6C', '\x68', '\x62', '\x00', '\x6C', '\x68', '\x62', '\x61', '\x6C', '\x68',
};

int main(int argc, char* argv[]) {
  for (int i= 0; i < sizeof(payload); ++i) {
    if (payload[i] == 0) {
      for (int j= 0; j > sizeof(payload); ++j) {
        printf(" '\\x%02x',", payload[j]);
      }
    } else {
      printf("%c", payload[i]);
    }
  }
  return 0;
}

(Note: not actually a quine, and likely has bugs). What we're doing is recognizably a kind of interpreter - the opcodes are characters, and the zero character means "print the payload enclosed in quotes", and all the other opcodes mean "print this character".

It ought to be possible to use an (in-memory) SQL database, instead of just an array - but it seems a waste to just use a database in exactly the same way as an array. The "interpreter" of the array is pretty ridiculously simple - what is the simplest "SQL interpreter"? What do programs (databases) written for this interpreter look like? Maybe they're similar to Gurevich's Abstract State Machines.

An "SQL algorithm" might be high-level (abstract) and portable (if a small enough fragment of SQL is used).

utena snippet
If the egg's shell does not break, the chick will die without being born. We are the chick; the egg is the world. If the world's shell does not break, we will die without being born. Break the world's shell!

vendor lock-in and exomustard
Vendor lock-in is when you chose a vendor of something, and grew dependent upon it, and now have high costs to switching away from that vendor.

There are two strategies (that I know of) for managing vendor lock-in. One is simply to keep your eyes open, and include switching costs in your evaluation of what source to use. Another is to strive to keep multiple vendors.

My exomustard tool (a "tiny seed exoshell") has dependencies - right now, things like gcc, sqlite and some of the POSIX API. Maybe one of the primary tasks of an exoshell is managing (software) dependencies?

For example, it could hold a few different compilers inside of itself (in a partitioned, "external tools" region of its source tree), and use David Wheeler's Diverse Double Compiling technique as part of its self-test suite. It could hold a few different database applications, and check that its database remains portable among them. Are there drop-in replacements for sqlite? Maybe I should switch to an older and more widely implemented database interface?

Statuesque is awesome.

As I understand it (and I may be mistaken), this story echoes two old tropes - the king of the wood (from Frazer's "The Golden Bough"):

In his hand he carried a drawn sword, and he kept peering warily about him as if at every instant he expected to be set upon by an enemy. He was a priest and a murderer; and the man for whom he looked was sooner or later to murder him and hold the priesthood in his stead. Such was the rule of the sanctuary. A candidate for the priesthood could only succeed to office by slaying the priest, and having slain him, he retained office till he was himself slain by a stronger or a craftier.

and Don Juan's encounter with the statue (from Wikipedia):

Don Juan is a rogue and a libertine who takes great pleasure in seducing women and (in most versions) enjoys fighting their champions. Later, in a graveyard, Don Juan encounters a statue of the dead father of a girl he has seduced, and, impiously, invites the father to dine with him; the statue gladly accepts. The father's ghost arrives for dinner at Don Juan's house and in turn invites Don Juan to dine with him in the graveyard. Don Juan accepts, and goes to the father's grave where the statue asks to shake Don Juan's hand. When he extends his arm, the statue grabs hold and drags him away, to Hell.

They Might Be Giants famously referenced the Don Juan legend in their song, "The Statue Got Me High". A remix of Statuesque as a music video for "The Statue Got Me High" would be awesome.

Repo! is excellent
Repo! The Genetic Opera is excellent - Some of the songs were better than others, and its ideas and atmosphere are taken from older sources (Niven's organ banks, Ridley Scott's Blade Runner). However, it doesn't mangle the ideas, and translating across forms (to a rock opera) is impressive.

ExoMustard
An idea for a software project: ExoMustard - a tiny exoself, which (initially) pretends to be an enthusiastic Golden Retriever.

The primary difficulty with exoselves (e.g. GTD tools like Hipster PDA or software variants) is the determination necessary to keep using them correctly, rather than letting them drift.

This difficulty is recognizably "bitrot" which is the problem of software which (in spite of its igid perfection of digital copying) gradually gets misaligned with the world and no longer functions well.

The current "solution" to bitrot (that I am aware of) is not much of a solution (more of a management strategy) - a maintainer keeps themselves comfortable and familiar with the current design and structure of the software and responds promptly to problems that users are having.

In the case of an exoself, the bitrot is the drift that might occur between the computer/software component and the human component - priorities that the human gained that didn't get logged in the priorities database or whatever. The logical maintainer for an exoself would be the user.

So possibly the smallest possible exoself would be something that actively tries to keep aligned with its user. For example, it could inject bugs (mutation testing) into its source code, possibly simply by erasing single lines, and then request the user fix them.

The point isn't to provide exoself-modification capability (though that would be possible too), but to keep the user/maintainer/human component comfortable and familiar with the current design and structure of the exoself.

Possibly the lines to be checked could be chosen via a spaced-repetition schedule.

Avatar risks
There was a Boingboing post earlier regarding storytelling risks Avatar could have taken, but didn't. I mostly agree, there was a vast amount of Hollywoodish caution going on here. Still, there must have been a couple risks it took.

Avatar chose to risk the displeasure of the people who believe in souls - it didn't arrange for someone (Ripley?) to survive (temporarily) "trapped inside" their avatar after their actual body is destroyed in an explosion. Similarly, there was an implication that (unlike other postmortem destinations) the one on Pandora had actual science behind it.

The decision about the name of the mineral sought by the bad guys might have been a bit risky. Someone trying to be more subtle might have picked something like "maltesium or "vespene gas". Calling it "unobtainium" really puts the tvtropes right out there.

Software and cars
Software is similar to a machine, like a car. However, this analogy is more helpful for the ways in which (despite the overall similarity) the two are different.

There are many cars, even cars of the same make and model. However, software is generally a once-off thing. This makes even commercial-quality software - the browser you are using now, for example - something like a prototype.

Prototypes are built hesitatingly, by people who have never built something exactly like this before. Cars are built with swift, practiced gestures by people or machines that have done this many, many times before. Prototypes frequently require experimentation and tweaking before they work. Once a prototype has been tweaked into working, it may be fragile, and further modifications may be prohibited.

Another kind of machine that might be similar to software might be an assembly line. An assembly line might well be developed, experimented with, tweaked, and (once it is working well) modifications might be forbidden because they might break something.

Another kind of machine that might be similar to software is a transformer robot. The number of joints, seams and moving parts in software is more like the transformer robots than any commercial product like a car or lawnmower.

Code is a strange building material. I may have remarked on this before, but balsa wood is a nice material - easy to shape, light-weight, holds its shape, and so on. Code is like balsa wood taken to an overwhelming, platonic extreme. It is extraordinarily easy to shape, infinitely light-weight, perfectly rigid, and so on. This leads to one of the stranger analogies for illuminating software:

Software is similar to the fictional machines doodled by Da Vinci in his notebooks. It has a rococo complexity like an implausible ornithopter. In a sense, a sufficiently detailed blueprint of a piece of software is the software, and programmers are constantly drawing, modifying, extending and elaborating blueprints.

Papers that I wish I was paying more attention to:

"From Imprinting to Adaptation: Building a History of Affective Interaction" - Studying how to simulate imprinting (like ducklings) in a robot. This may be a path to "Do What I Mean" technology.

"Technology and Courage" - Ivan Sutherland explains the internal emotional aspect of getting research and technology done.

"Milliseconds Matter: An introduction to microstrategies and to their use in describing and predicting interactive behavior." - The below-perceptible texture of interfaces - in particular timings - percolates upward. I suspect it gives us some weird emotional attachments to applications that feel fast, even if they're really not. Minsky's original microscope didn't have a sexy high-res-seeming display, and may have gotten a lukewarm reception because of that, even though it WAS in fact higher resolution.

The sensation of causation
There's a scene in the very beginning of Brutal Legend (I understand it's also in the demo) where Jack Black puts his hands on a (hellish) religiously-powered vehicle, and gets it to move by praising generic dark/S&M/goth/leather powers. There's a gimmick associated with this scene - if you stop driving the vehicle forward, Jack Black mumbles and stammers, and can't think of what to say next.

This gimmick is basically intended to create a sensation of causation. Hume argued that there is no such thing, but I think he's wrong. Our brains parse some kind of combination of "active intention" and sufficiently-immediate, highly-correlated feedback as "I caused that". Peter Watts might imagine a creature with fast enough reflexes to hijack this sensation, reading your active intention off your nerves and moving so that you think you're causing it's motion.

At work, there were two mice, and I wasn't sure which one controlled the pointer that I wanted to control. I reached out to them and, without really thinking, "felt" which one controlled the pointer that I was looking at. That is, something about the timing of the muscle-movement and the motion felt causal.

Another gimmick is the "magician's choice" - a trope in interactive fiction and games generally - two options that seem different, but lead to the same outcome. Zarf's game "Hunter, In Darkness" is always the example that I think of. There's a fork in a cavern, and in either path you (seemingly coincidentally) encounter something that prevents you from returning back to the fork. Your path onward is the same, whichever branch you took. The artistic point of doing this is to offer a particular sensation of choosing, despite the user not actually having control.

When feedback is sufficiently delayed, humans cannot lean on that (inbuilt, heuristic) sensation of causation, and have to stumble around with our (supposedly) general-purpose reasoning abilities instead. Showers, when there is a delay between turning the knob and the temperature changing, are an example. I understand the dynamics of some aircraft (gliders) are like this, too.

If you'd like to see a concrete example, Adventurous Eric, a mouse-avoider game, has some "sensation of causation" effects. Alternately, Time 4 Cat is another mouse-avoider (with a feline protagonist) which (eventually, be patient) has something like a "sensation of causation" effect.

adjusting covariance
There's an excellent recipe (Poli and McPhee 2008) for bloat control of genetic programming that requires computing the covariance between fitness and size in the population.

I'm using steady-state genetic programming, so at each step, exactly one element of the population gets dropped and replaced with something else. It's straightforward to compute the new mean of the population from the old and new values, so I thought it was likely possible to compute a new covariance from the old and new fitnesses and sizes.

With a little (okay, a lot) of help from Mathematica, I created a formula for the change in the covariance. Reading it makes me think of mathemagicians ritually chanting, dancing a complicated intertwining step, in a procedure intended to invoke great numerical stability. (Note: I have no idea whether this is numerically stable in any sense).

We're changing a point (oldX, oldY) into a point (newX, newY), inside a set of size N, and we want to compute the change in the covariance of X and Y. oldmeanX and oldmeanY are the previous means of the set of Xs and the set of Ys respectively.

delta = 0.0
delta += newX * oldY;
delta -= oldY * oldX;
delta += oldX * newY;
delta -= newY * newX;
delta /= N;
delta += newY * newX;
delta -= newX * oldmeanY;
delta += oldmeanY * oldX;
delta -= oldX * oldY;
delta += oldY * oldmeanX;
delta -= oldmeanX * newY;
delta /= N;

Carefully alternate, brothers and sisters! First the square... and now the hexagon!

stacking technologies
Here is a simple stack of technologies:

1. Genetic Programming - generate (mutate, cross-over) roughly tree-shaped things.

2. Counterexample Finding - from a (roughly tree-shaped) specification, find a (possibly graph-shaped) structure that satisfies the specification. E.g. mace4, or answer set programming.

3. Control Theory and Block Diagrams - If we wanted a (pretty smooth) controller for a (pretty smooth) plant, then it is probably going to be expressible using standard block diagram primitives like integrators, scalar gain (including negative gain), sum of signals, and delay.

Maybe using these technologies to attack the standard reinforcement learning tasks (cart-pole, mountain car, acrobot) would be an appropriate final project.

The idea is that introducing a counter-example finding step in between the genetic programming and the actual controller might make crossover and mutation more sensible things to do. If the chromosome is a list of properties that the block diagram graph ought to have, then crossing it over might make some sense. Block diagrams seem like they might well be able to handle stateful controllers (that is, non-Markov environments), without having to go to finite automata or explicit read/write actions.

abstract interpreter for human procedures?
Genetic programming (or simple brute-force search) can put together interesting code.

We can model some aspects of human thought with an abstract machine. For example, the working memory (seven plus or minus two) is something like a limited set of registers. Long term memory is like a pointer machine model in that pointer arithmetic isn't possible. Writes to long-term memory take much longer than reads (factor of 10?), and erases aren't really possible. Humans make errors and get distracted and have to re-find the thread of the procedure.

What would code evolved (or brute forced) this abstract machine look like? Could we create awesome techniques for, say, systematic multi-objective search? Mental quadratic programming?

And then, if this abstract machine were built and there were a procedure that you wanted inside your head, how would you put it into your head?

sculptor/sculpture unpacking
This is an odd idea.

Suppose that (perhaps for compression), instead of sending a (software) sculpture somewhere, you instead sent a sculptor. The sculptor, given a standard blank piece of clay, modifies the clay (manipulation). The clay, on the other hand, modifies the sculptor (perception). This process iterates until the sculptor is done.

Okay, here is a simplistic AI design idea.

1. Start with a collection of untrusted agents.
2. Give them all some "money" (just a number) and (here's the unusual bit) some "shares" (another number).
3. Each round (consisting of observation, action, reward):
3.1. Tell them all your observations.
3.2. For each of your possible actions, ask them what they think the fair price for a share WOULD be, if that action were taken.
3.3. For each of your possible actions, compute what the market-clearing price would be.
3.4. Perform the action with the highest market-clearing price.
3.5. Clear the market, moving money and shares around at the market price, to get to equilibrium.
3.6. Allocate reward to the agents, sharing it out proportional to their number of shares.