Happy Birthday, VICTOR & 2015!

It occurred to me that 5 years ago today (okay, technically ~5.01 years ago today) my sister and I built a cool little AI construct known as VICTOR. I use ‘cool’, ‘AI’, and ‘construct’ loosely. Really, VICTOR is a deceptively simple little program that has consistently seemed to capture the hearts and minds of academic advisors, potential employees, friends, and family. VICTOR’s been defunct for several years (he doesn’t crawl news sources any more; nor does he post on Twitter), but he always seems to find a place in my heart (and on my resume).

A typical conversation about my projects goes something like so:

Me: Yep, I do startups. To keep my skills honed I often do all kinds of fun little projects!
Me: For example, Jumpino, or skrch, or VICTOR, or this new project I’ve been working on: Jssembly. It’s really cool. It lets you run native Assembly in Java.
—: I see. VICTOR looks amazing. Tell me more about him.
Me: … well, it’s not really technically challenging or anything. And the math isn’t hard. It’s just a silly little toy. Why don’t we look at skrch instead? It’s a sketch-based OCR search-engine! How cool is that?
—: Yeah, it’s pretty cool I guess, but can you tell me how VICTOR works?

Everybody loves VICTOR

D’oh! Well I don’t know why people love you so much, VICTOR, but I’ll dedicate this post to you. So how does he work? It’s very simple, actually. Before we dive in the nitty-gritty, here are some facts about VICTOR:

  • VICTOR is 1832 days old!
  • VICTOR is written in PHP and Prototype. Back then, jQuery wasn’t cool and Angular wasn’t around.
  • VICTOR’s emotional spectrum is based on a schema devised by Dr. Klaus Sherer and his colleagues at the University of Geneva.
  • VICTOR’s design is (perhaps unsurprisingly) inspired by WALL-E’s EVE.
  • VICTOR has a Twitter account with over 4000 tweets. Unfortunately, it’s no longer active.

First, let’s observe VICTOR’s behavior. Why so many people may like him is because his emotional response is (at times) eerily accurate. Consider a few examples. These are 10 random non-cherry-picked samples and were taken simply by refreshing VICTOR’s page and pasting them here.

Emotion Headline Accuracy?
Worried Britney Spears’ Conservatorship is Ending. For Real This Time. (Maybe.) Pretty accurate, especially for a Britney fan, although the headline may be in jest.
Confident Obama denies crisis with Israel I can see that. “Denies” is a confidence-inspiring word.
Curious Ahmadinejad aide says Iran not ready to talk nuclear Curiosity is a neutral emotion. I’d say this is more miss than hit.
Serious Bears get next chance to upend red-hot Tom Brady, Patriots Don’t really see this one. The headline is about sports, not something particularly serious.
Excited Google’s Shopping Spree Explained In 10 Bullet Points (GOOG) A shopping spree is always exciting. This makes sense.
Impressed O’Gara returns for Italy opener Maybe VICTOR knows something about O’Gara that I don’t. This one is a miss, I’m afraid.
Convinced Wage gap shrinks between men and women Confirmation bias at work? If anything, the emotional reponse is funny.
Excited Better Get Ready Europe, TechCrunch Partybus is Heading Your Way Pretty head-on. Everything about the headline screams “exciting”.
Impressed Kurt Warner mindful of the end as Cardinals seek Super return Nope.
Curious Motorola Ming A1680, MT810, and XT806 begin their Android mercy mission in China Curious generally means there’s not enough data to move on the emotional spectrum.

Emotional baggage

That was fun. But how do VICTOR’s emotions work? We’ve already seen some variety in his behavior. Is there a systematic way to “graph” emotion? There might be. Based on research done by Dr. Klaus Sherer (see Toward emotion-sensitive multimodal interfaces: the challenge of the European Network of Excellence HUMAINE), let’s begin by drawing a cartesian coordinate system and labeling some axes. According to the model, we end up with this:

Emotional Spectrum

Given this model, emotions have two dimensions: excitatory power (passive/active), and valence (negative/positive). So, e.g., happiness would probably fall somewhere in the second quadrant, whereas apathy might be in the fourth. The hard part, as you may have guessed, is plotting a nontrivial amount of emotions on this spectrum. Eventually, and using a separate tool to assist in plotting new emotions, we came up with the following (populated) spectrum:

Emotion Plot

The algorithm

Step 1 — Tabula rasa: VICTOR doesn’t know anything. Suppose he reads the following headline:

David is awesome!

As he encounters new words (e.g. “David”, “is”, “awesome”), VICTOR puts them into a database and gives them the emotional charge of curiosity. The database, for example, would look like this:

word eX ey
david 0 0.333
is 0 0.333
awesome 0 0.333


Step 2 — Training
: I see the same headline on VICTOR’s dashboard (“David is awesome”) and I mark it as maximally exciting (coordinates: (-0.707, 0.707)). VICTOR amends the database, so that all words in the headline are closer to (-0.707, 0.707). The database now looks like the following; using the midpoint equation, we have:

word eX ey
david -0.3535 0.52
is -0.3535 0.52
awesome -0.3535 0.52

Step 3 — How do you feel? It’s trivial to see now that any headline with a word like “awesome” (accurate) or “David” (inaccurate) will make VICTOR more excited! This is where the training comes in. With enough data, neutral words like “is” or “David” will slowly migrate towards the center, whereas charged words like “awesome” will accurately model emotional states that VICTOR should feel when reading various headlines.

Wrapping it all up

If my intuitive explanation failed to satisfy some of the more technically-inclined, here’s how I originally explained his inner workings: VICTOR reads 20 headlines every hour. He looks at every word carefully and if he understands the word, he is affected emotionally by it accordingly; if he doesn’t understand the word, he becomes more curious. The emotional central tendency of any word w based on a [0,n] training set is defined by:

As VICTOR reads, he traverses the emotional spectrum via a simple recursive mid-point equation. His final emotion E after reading a headline and traversing over an arbitrary number of words is given by:

Well that’s it for me. Happy new year! And, of course, a warm “happy birthday” goes out to VICTOR.

(To see him in action, click here.)

Cracking the Coding Interview Problem 2.2

I don’t blog often. And I haven’t blogged about coding for a while; but I think I should. So here goes.

Having recently graduated from UCLA, I’m now trying to get a solid job at a solid company making some solid money. My skills primarily consist of writing code and running startups so that’s my target. Apart from the obvious choices (Google, Facebook, Microsoft, and so on), I’m also applying to a slew of startups around LA and the Bay Area. If you’re not familiar with the interview processes for tech companies, they go something like so: HR interview, phone tech interview 1, phone tech interview 2 … phone tech interview n, campus tech interview 1, campus tech interview 2 … campus tech interview n, offer or no offer.

Now I’m all up for hiring smart people that know how to get things done, but I really really loathe the technical interview. To explain why, let me cite an example from Cracking the Code Interview — the de facto bible of tech interviews.

2.2 Implement an algorithm to find the nth to last element of a singly linked list.

Easy, right? Well, not so fast, skipper. Here is the proposed solution (by an apparent Googler):

public static LinkedListNode nthToLast(LinkedListNode head, int n) {
	LinkedListNode p1 = head;
	LinkedListNode p2 = head;

	if (n <= 0) return null;

	// Move p2 n nodes into the list. Keep n1 in the same position.
	for (int i = 0; i < n - 1; i++) {
		if (p2 == null) {
			return null; // Error: list is too small.
		}
		p2 = p2.next;
	}
	if (p2 == null) { // Another error check.
		return null;
	}

	// Move them at the same pace. When p2 hits the end,
	// p1 will be at the right element.
	while (p2.next != null) {
		p1 = p1.next;
		p2 = p2.next;
	}
	return p1;
}

Feel free to scratch your head and go “what the hell” because I know I am. The above is considered a solution to Problem 2.2. First, let me mention what’s wrong with it:

  • Using two pointers is dumb.
  • It’s difficult to read. I needed 10 minutes to get my head around it when the function should be doing something trivial
  • It’s simply bad design. More on this in a few.

Now let’s solve the problem like real software engineers, not hipster programmers that thrive on esoteric nonsense:

// this is how normal people find the length of a linked list
public int getLength(Node head) {
	int length = 0;
	Node n = head;
		
	// iterate through the list
	while (n != null) {
		// yay more length
		++length;

		// go forward!
		n = n.next;
	}
	return length;
}
	
// this is how normal people find the nth to last node of a linked list
public Node getnthFromLast(Node head, int nth) {
	int length = getLength(head);
	Node n = head;
	int location = 0;
		
	// if list is empty or we want to go too far back or we want zeroth to last, return null
	if (length == 0 || nth > length || nth <= 0) return null;
		
	// 1st to last = last
	// 2nd to last = penultimate (length-1)
	// 3rd to last = length - 2
	// .. and so on
	while (n != null) {

		// right location?
		if (location == length - nth) return n;
			
		// next spot
		++location;
			
		// next node
		n = n.next;
	}
}

Simple, concise, readable. What irks me most is that not only will interviewers think code like the one from the book is good, but so will interviewees. Oh well, c’est la vie.

Back in black

After a Dreamhost blunder that left thousands with their websites hanging by a thread (or by a noose), my blog was also deemed infected with some sort of virus. I have no idea what kind of vulnerability DH was trying to fix, but I couldn’t find anything that was compromised. Even so, my WordPress installation wouldn’t start up. So I had to re-install the whole thing, find a new theme, mess around with it a bit and re-launch.

I’m back in black. And to all of my imaginary fans: I love you!

Resolutions

I’m not very goal oriented. Maybe I should be. So here are some resolutions for 2012.

  • Continue getting straight A’s
  • Launch E-Sports Rankings and make it successful
  • Gain 10-20lb of muscle mass
  • Read at least 12 books
  • Do some stand-up
  • Release a game on the Android market
  • Update this blog daily
  • Moar?

Here’s hoping I’ll at least get through half of those!