human computation for novel generation algorithms

[anandkulkarni]

Human Computation for Novel Generation Algorithms

I'm thrilled to be doing NaNoGenMo this time through.

What's this all about?

Human computation (a la Mechanical Turk) is a classic way to get books written (see: http://toc.oreilly.com/2008/08/the-crowdsourced-cat-book.html). You pay a hundred people to each contribute 500 words, then end up with a finished book. You can run this over and over again, and provided that you're wiling to use a pricey computational resource (humans), you get books consistently each time you run the program. There's no state retained here from one execution to another; each time you run the program, you get a new book.

Here's a small proof of concept book-writing algorithm using Björn Hartmann's algorithm.

book = []
request = 'Write at least one paragraph about a funny, unbelievable or otherwise memorable incident involving your cat'
for x in range(1:500):
     chapter = post(request)
     book.append(chapter)
print book

You'll see that there are multiple design choices that can be encoded in our algorithm. For example, if we ask for chapters in parallel, we'll create a compilation-of-short-stories book. If we ask for chapters serially and pass in the previous text, we'll create a conventional community-written story.

book = ''
request = 'please write at least 100 words more in this story'
for x in range(1:500):
     chapter = post(request, book)
     book = book + chapter
print book

There are more advanced algorithms possible.

Let's try something more interesting.

I'm trying something different, here, at one layer higher of abstraction – human meta-computation. I'm going to see if we can get humans to iteratively improve the book-writing program I provide until we end up with a finished high-quality generation algorithm.

This means we're constructing two programs in parallel. First, we have the book generation program itself (bot.py), which prints/generates the book. This is the object of improvement.

Then we have the book-generator-improver (improve.py), which requests improvements to the book generator itself. (There's a rabbit hole you can go down, doing algorithms to improve improve.py itself... but we won't go there)

There are structured and unstructured approaches to this – I can ask for open-ended improvements, or I can ask for improvements that take us closer to a goal in some specific way (improving complexity, improving readability). There are also formal approaches like gradient descent.

In competition, there's another idea I'd like to try. We've seen new results recently around deep learning for text generating plausible-looking text based on corpuses. Can we structure these somehow? Maybe using sequence-to-sequence learning for dialogue generation or straight novel generation?

A hybrid approach where people select the best story blocks proposed by an algorithm is also an interesting idea.

Results

Preview of current state of novel, featuring 0 human improvements (Nov 1, 4:01 PM PST): full.pdf

[anandkulkarni]

The stub bot is up, following the recommended "meow" example. https://github.com/anandkulkarni/nanogenmo2016/blob/9e91d6411e91b0e66450c2b6e263fdceeeda7d1b/bot.py

A quick to-do is to get this thing to convert into LaTeX for nice rendering.

[anandkulkarni]

Now, to request iterations and improvements, we need two things: 1) an interface to ask humans to improve our code. is it faster to post tasks to turk, to upwork, or to twitter? 2) a scoring function – did we get better or worse? (the problem is that we need to break out of local optima by getting worse, at times... structured randomness, or search for an optimal policy via MDP?)

[anandkulkarni]

The LaTeX module complicates things here, even though we now have beautiful books being generated. Someone looking at our code won't see the simple text; they'll see the formatting. We're in a local minima already.

https://github.com/anandkulkarni/nanogenmo2016/blob/d9a3337f4c4849e0220f295dd7d2890b0a80eb7a/bot.py

[anandkulkarni]

I thought we can use Fleisch-Kinckaid reading scores to measure quality, but what gives? The meow book is far too readable.

[anandkulkarni]

I should add something to timestamp outputs or I'm going to have some challenges a little later.

[anandkulkarni]

I took a little break to survey alternative approaches. I see grammars (not interesting), story compilers (interesting!) and some stuff with char-rnn (very interesting). These will be cool to look at, either as tools to suggest to people doing posts, or as a comparison case for the study (with an alternate story).

Up next: let's write improve.py, a program to to post requests for improvement. We can use Twitter, Upwork, or a code bounty system.