Cuttlepress

Blogging about Hacker School?

Project Writeup: Infinite Monkey Trainer

The Infinite Monkey Trainer is a project I’ve been backburnering on and off for years. The concept is a machine that will act as an operant conditioner for the infinite monkeys, to speed their production of Hamlet: when a participant enters text into the machine, the machine judges the text’s similarity to Hamlet and rewards bananas accordingly. In its final form, this will ideally be a physical installation, with an actual typewriter and a dispenser of banana candies, but I’ve been primarily concerned with the software up to this point.

An earlier iteration simply compared an incoming string, stripped of spaces and punctuation, to a string consisting of the entirety of Hamlet, similarly stripped. It was my first and only JS project before Hacker School, and an okay prototype. But the scoring was entirely binary, with no room for plausible phrases or misspellings.

Misspellings seemed important to me. After all, we’re talking about Shakespeare: it’s not like spelling was standardized. Earlier in Hacker School, I made a stab at working on the misspellings issue, by implemementing Metaphone. By Metaphoning the input string and the original text, I could ignore nonstandard spellings (or at least, nonstandard spellings that Metaphone to the same thing).

Last week, we had Alex Rudnick in residence, and he helped me progress much further. His suggestion was to implement a language model trained on Hamlet, and use that to check the “probability” of the incoming string’s existence in that text. This turned out to be less complicated than I’d thought. Once the bigrams and unigrams have been pulled out from the text (I’m storing them in JSON), I can simply do some dictionary lookups to grab the probabilities of individual bigrams and multiply them for the whole string. On Alex’s advice, I’m using “Stupid Backoff” when I fall back to an (n-1)gram, because it’s Good Enough. Here’s the lookup in total:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// Check the probability of an phrase, as an array of words.
function checkProbability(text, bigrams, unigrams) {
  var prev = text[0];
  var value = 0;
  // if we have at least two words, we can check the bigrams
  if (text.length > 1){
      for (var i = 1; i<text.length; i++) {
          current = text[i];
          if(prev in bigrams && current in bigrams[prev]) {
              value += bigrams[prev][current];
          }
          else if (current in unigrams) {
              value += unigrams[current]+0.91629;
              // "stupid backoff" (Brants et al 2010) is we multiply the (n-1)grams value by 0.4
              // aka add the neglog of 0.4, which is 0.91629
          }
          else {
              value += unigrams["LEAST_COMMON_PROB"]+0.91629;
              // and if it doesn't exist there, call it as common as the least comnon thing
          }        
          prev = current;
      }    
  }
  // otherwise, we can only check the word as a unigram
  else if (text.length > 0) {
      if (prev in unigrams) {
          value += unigrams[prev]+0.91629;
          // "stupid backoff" again
      }
      else {
          value += unigrams["LEAST_COMMON_PROB"]+2*0.91629;
          // and if it doesn't exist there, stupid backoff to it being as common as the least comnon thing
      }
  }
  // otherwise, the value stays at 0, but then so does the text.length
  return value;
}

One next step I’d like to take is reintegrate the spelling forgiveness. An easy thing to do would be to check both the original string against the original language model and the Metaphoned string against a Metaphoned language model. I’d also like to be more forgiving of common typos, such as adjacent keyboard keys; I suspect there are well-known best practices there.

Another work in progress is the function that converts the between the language model-based probability of a string and its worth in bananas. Currently, I’m using the scoring function I posted last week. I’m comfortable putting off betatesting until after Hacker School.

For presentability, I’ve wrapped the whole thing in an interactive webthing. For obfuscation, the similarity-to-Hamlet calculation is done server-side. The client and server communicate via Socket.io with code almost entirely ripped from my earlier picture chat project. There’s a bit of Sass-based CSS and an image of some bananas, as well. Here’s a screenshot: Monkey trainer.

The code is on github. “Play” online at http://infinitemonkeytrainer.herokuapp.com/

Day 38

A short day and a long one: I left the job fair after midnight, but the coding part of the day only ran until 3:30 to squeeze in Thursday presentations before the job fair. In the morning, I attended Alex’s livehacking Markov chains demo; we basically reimplemented the work I did yesterday, but in Python, and faster. The rest of the day, I worked on my goofy generative Inform 7 project. The results were trained on Emily Short’s Bronze and they are of course mostly not valid Inform, but some are evocatively close:

To decide whether melancholy or enslaved the player:
    if the player
    begin;
        say "yourself";
        rule succeeds;
    end if;

Solving is a thing is scenery.

The stone bench is not unsolved.

Understand "bite [something enterable]" as attacking.

Understand "get [things preferably held] down" as dropping.

Carry out looking toward:
    say "You can't enter [the noun]."

Instead of answering it is easier to you do this world to lit room is a long time: try dropping rule when novice mode on" as hunting.

Understand "solve [something]" as wearing.

Understand "search" as attacking.

The inkpot is that the gate.

I also tried a few approaches to separating out the Inform code from the game text and running the generators separately. More on this after a full night’s sleep.

Day 37

For the first part of the day, I made the writeup post for the Twitter project.

I paired with Stephen on his Zulip bot, which generates text based on a given set of Zulip streams. We worked on cleaning the input of blocks of code, unencoding the HTML entities in the output, and making the input case-insensitive.

For my Hamlet project, I finished writing how to generate bigrams, added the function to tabulate the probability of the input string, and modularized my Metaphone code. I also put some thought into the question of how scoring works: players that type convincing phrases need to be rewarded accordingly. Scoring clearly needs to take the length of the text into account, because otherwise a single word from the corpus is going to score best. While this is the sort of thing that is best done with playtesting, here’s a first attempt at mapping a phrase’s probability value to a score (remember that the probabilities are as negative logarithms; that is, a lower number is a better score):

1
2
3
4
5
6
7
8
9
10
11
12
function calculateScore(text, value) {
  var score;
  if (text.length < 1) {
      score = 0;
  }
  // longer strings with smaller "values" are worth more points
  else {
      var avgValue = value/text.length //going to be somewhere between 0 and 11.2
      score = Math.round(10*(11.5 - avgValue)*text.length);     
  }
  return score;
}

I ran this on several input phrases, with and without Metaphoning everything. Output below the fold.

Project Writeup: Curated Twitter

Curated Dannel” is a project I’ve been joking about implementing for at least a year. While I would love to follow Dannel on Twitter, his tweeting frequency is a bit higher than what I can keep up with. I needed some way of curating his tweets. Luckily, Twitter has a couple of ways to vouch for the attention-worthiness of tweets: favorites and retweets. So, in theory, it’s easy to crowdsource.

I decided to use Node again for this project, and using ntwitter allowed me to interface with the Twitter API without dealing with any of the details of authenticating via OAuth. The API provides access to individual entities (such as existing tweets or users) through queries, and separately, access to realtime events (such as incoming tweets or favorites) through streams. Information is not necessarily consistent across the two, so a hybrid approach seems to be recommended. (One convoluted behavior I dealt with did turn out to be a bug, not a design decision, at least.)

After trying out many different approaches, I ended up with this method: I open an authenticated User Stream as Dannel, which allows me to see his incoming “favorite” and “retweet” events. If the event is on a tweet written by Dannel (his stream also sees events on other relevant tweets, such as further retweets of tweets he previously retweeted), I then check the current total number of favorites and retweets on the included tweet, via the Search API. I store the text, tweet ID, favorite count, and retweet count in a database at MongoHQ, using mongodb. If I haven’t previously retweeted that tweet, I check its eligibility, potentially retweeting it and marking it in the database as retweeted.

Determining a tweet’s eligibility for retweeting is simple:

1
2
3
function tweetQualifiesForRetweet(tweet) {
  return tweet.retweet_count*2 + tweet.favorite_count >= 2;
}

I figure that a retweet should count for more than a favorite, because it’s a more public way of vouching for a tweet’s attention-worthiness. This cutoff seems to provide about as many tweets per day as I’d like; in an optimal universe, the code would adjust its metrics to provide tweets at an approximate quantity over time instead, but in this less-than-optimal universe, I am very ready to move on from this project.

I grabbed a public domain image to make the user icon of the account. (I also used a gratuitous Photoshop “art” filter, which made me inordinately happy.) Another possible extension of this project would be to automatically update its content based on Dannel’s current icon, since he changes them monthly.

The last step was to ensure that, ideally, I never have to think about keeping the code running. It’s hosted on a small Amazon Web Services instance, and theoretically it should happily run for a pretty long time, but I wanted to not have to deal with crashes or server reboots. I used supervisord to restart the code after any crashes, and a startup script to start supervisord after any reboots.

So! @curateddemarko is live. The code is all on github. Now we just need to monetize it:

Day 36

Busy day! I finally got my Twitter project fully working, with the final piece being that I want to set-it-and-forget-it on my AWS server, so I was determined to find some way of automatically restarting the process if it broke or if the server was restarted. Moshe helped with get supervisord set up, though we had a lot of trouble with getting the “program” part of the conf file working. Tom helped us determine that the solution was to use absolute paths for both Node itself and my .js file, like so:

[supervisord]

[program:curateddannel]
command= /usr/local/bin/node /home/ubuntu/twitter.js
autostart=true
autorestart=true
stdout_logfile=/home/ubuntu/supervisorlogs.log

I also followed this tutorial to make sure the supervisord process runs on machine startup. I’ll do a real announcement/linking to the project tomorrow, once I’m more sure that it’s stable.

I attended Lindsey’s talk on LVars and parallel computing, and I really enjoyed it. The talk and many of the questions lead to a lot of “oh so that’s what that means” moments for me, and like all of the best presentations, it made me interested in a thing I’d never even thought about before.

I had an ofice hour with Alex, which was also really great. We determined that a good approach to my “how do we define ‘similar to Hamlet?’” question would be to generate a language model of Hamlet and check incoming phrases against the probabilities contained therein. He walked me through the basics of how I could construct such a model (build up a dictionary of bigrams, along with their probabilities), along with some implementation tips (for example, store probabilities as a negative logprob). It was lot of very comprehensible information in a fairly short time, and it really felt like learning/progress were occurring. I wrote up the code for grabbing the unigram probabilities from Hamlet and got most of the way through the bigrams (with some debug help from Rishi). Here’s unigrams, where choppedtext is an array of all the words in the text:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function makeUnigrams(choppedtext) {
  var dict = {};
  var highestscore = 0;
  // count the occurences of each word
  for (var i = 0; i<choppedtext.length; i++) {
      if (choppedtext[i] in dict){
          dict[choppedtext[i]] += 1;
      }
      else {
          dict[choppedtext[i]] = 1;
      }
  }
  // then use that count to calculate the probability of each word
  for (var word in dict) {
      var count = dict[word];
      var unlikeliness = (-1)*(Math.log(count/choppedtext.length));
      // storing the numbers as "negative logarithmic probabilities" helps by 
      // 1) ensuring no numbers too small for floats, and 
      // 2) allowing us to add them instead of multiplying
      dict[word] = unlikeliness;
      if (unlikeliness > highestscore) {
          dict["LEAST_COMMON_PROB"] = unlikeliness;
      }
      // dict also stores the highest unlikeliness, 
      // which can be assigned to words that aren't recognized at all
  }
  // and write it to the external file
  fs.writeFile(unigramsfile, JSON.stringify(dict, null, 4), function(err) {
      if(err) {
          console.log(err);
      }
      else {
          console.log("Unigrams saved to "+unigramsfile);
      }
  });
}

Day 35

Over the weekend, I discovered that it is possible to get streamed “favorite” events from the Twitter API… as long as you’re logged in as that user. Luckily my friends seem to trust me (?), so I am now authenticating both as my own application and the account that I want to watch.

I figured out how to watch for favorite events (if (data.event == "favorite")) and retweet events (if(data.retweeted_status)), and how to update documents in a MongoDB using the Node mongodb wrapper (a convenient findAndModify with {"upsert":"true"}).

But my retweeter, which is supposed to retweet when an incoming favorite/retweet event directs its attention to a tweet with more than a certain number of retweets/favorites, was never firing. It turns out that the “favorite_count” I was seeing was incorrect. My best guess is that, unlike the identically-named field of a naked tweet object, the “favorite_count” value of a tweet delivered via a streamed “favorite” event is relative to the authenticated user, meaning, “how many times has this user favorited the tweet?” Which is almost useless, since a user can’t favorite or retweet more than once; if you’re seeing the message at all, the answer is “once.” (Except that it’s the value right before the event was sent, so the value is actually “0.”) So you have to do a search query on the returned tweet ID, which counts against your rate limit. I’m going to run it tonight and see if I get rate limited. If I do, I’ll just do all the counting in my own database, and hope my stream doesn’t cut out.

I also went to lunch with Lindsey, who is at Hacker School as a resident! And I attended Daphne’s concise and demystifying Makefile workshop.

Day 34

More working on Twitter: I sent tweets and retweets from Node (after re-discovering that it is important to use the string version of a tweet’s id because there are so many tweets). I also did the necessary work to deploy to Heroku — Procfile and package.json and such — and set up another of Heroku’s MongoHQ databases before realizing that Heroku probably wasn’t actually the right thing for this project. I wanted to have a single, long-running process (that opens a stream and acts on incoming data, forever or something like it), but Heroku’s web processes go to sleep after an hour of inactivity. There are hacky ways to work around it, such as sending pings to keep the process awake, or having only a background worker instead of a web process, but they seemed inelegant. After asking around, I decided that the best way to proceed would be to use AWS, so I made a new MongoHQ database and started to set up my AWS [micro]instance.

Day 33

Today started early with Tom’s workshop on deploying to Amazon EC2, where we all learned how to use a tiny subset of the dizzying array of AWServices. In the afternoon, I attended Mary’s refactoring/testing workshop; we learned about testing in general and a bit about testing on asynchronous systems. I paired with Ashton on refactoring a very small server and writing some tests for it. For the other snippets of the day, I continued to read about the Twitter API and the many possible Node modules for interacting with it. Right before it was time to leave for the Monday talk, I finally got a filter stream working with ntwitter and help from Paul. Here’s the relevent code, which is deceptively short, for opening a stream of a particular user, and attaching a handler to incoming data:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var twit = new twitter({
  consumer_key: keys.consumer_key,
  consumer_secret: keys.consumer_secret,
  access_token_key: keys.access_token_key,
  access_token_secret: keys.access_token_secret
});

var tofollow = //whoever you want to follow, as a user id (not screenname)

twit.stream('statuses/filter', {follow:tofollow}, function(stream){
  console.log("making a stream");
  stream.on('data', function (data){
      if (data.text){
          console.log(pluck(data, ["text"]));
      }    
  });
});

The Monday lecture was an entertaining overview by Zane Lackey of some of the principles behind how he and his team handle security at Etsy.

Day 32

I paired briefly with Sumana on some basic CSS, but fixing the lag problem on my picture chat project consumed most of my day. Kate had suggested that I try using a spritesheet to speed load time; I was skeptical that it would make that big of a difference (there aren’t that many icons yet), but I figured I’d give it a shot. But I still wanted to automate the creation of the spritesheet, since I intend to add more icons as I have the inclination to draw them. So I spent the morning and part of the afternoon running in small, frustrating circles around a small handful of poorly documented imagemagick Node modules, trying to get anything working.

At some point I finally realized that I was in fact getting an error message at load time — I hadn’t noticed it because it was buried in the logs by all the socket-connecting. I asked on Zulip and Anton pointed out that I’d probably forgotten to enable the Websocket ability on Heroku. Which, of course, I had. Fixing it removed the lag and any remaining resolve I had to get spriting working.

So picture chat was up in time to present at Thursday presentations, despite some tricky business with closures right before the deadline (thanks, Mary and Kate!). Here’s a link to a frozen copy of the transcript from a couple of minutes of my batchmates sending messages, and here’s a composite of several of my favorite phrases:

Like a fish needs a bicycle.

The arrow icon was Rishi’s idea, and a very good one.

Day 31

Spent some time doing tweaks to my picture chat app, including better support for mobile:

The future.

(After hours, I also spent a bit of time drawing some new icons.)

And I deployed it to Heroku! But I think it’s not quite ready for a link here yet.

In the afternoon, I paired with Mary on learning about the Twitter API. I can now grab tweets using the REST API; tomorrow I’d like to mess with streaming.