Message Oriented Object Design and Machine Learning in Javascript

This article will show how to use Message Oriented Object Design (not unlike Message Oriented Programming aka MOP or Actor Model) to model your user interface as an actor and handle some more complex processing while updating the user interface. Specifically, the sample code implements a simple machine learning exercise wherein you enter any character on your keyboard and the program attempts to guess what you chose (without cheating ;).
 
First what is Message Oriented Object Design (henceforth referred to as MOOD)? Message Oriented Object Design is an object oriented design philosophy wherein we view objects as sending immutable messages/publishing events on channels. MOOD systems also rely on the configuration of object networks to enable collaboration between them. A core tenet is the lack of inter-object getters (be it method or property calls). Since I wrote this example in Javascript and it has no inherent support for this concept all of the ideals of MOOD will need to be enforced by convention. Message Oriented Object Design is a term I made up. I'm not sure that it's sufficiently different from Message Oriented Programming or Message Based Programming to warrant existence but I also don't want to sully those terms with my own ideas if there are important subtleties I'm missing.
 
I'm in the process of writing a very in depth article on Message Oriented Object Design so if you want to know more just let me know and I'll contact you when it's available. For now, suffice it to say that the words object and actor are interchangeable as are the words message, method, or event.
 
The problem we're going to solve is this: Given a text box where a user can enter in any character literal we will create a system that will use that information to predict what the user's next entry to be and also update the web page with our stats on how we're doing. Because we're using the MOOD philosophy, there will be no getters between objects (using them on private methods is perfectly acceptable though).
 
To get started I wrote the following very simple javascript object to represent the user interface:
 
 
One of the key ideas that makes MOOD so powerful is that it views your user interface as just another MOOD object (basically an as an actor). This means that all of the UI eventing that can be so troublesome finds a home here. The idea of asynchronous actions will be built into all of our objects so even as we switch contexts to work on the machine learning portion of the system, the overall object design will look very familiar.
 
Here you can also see the concept of a channel in my objects. In MOOD (and Message Oriented Programming) we always assume that we're using a channel which well pass along our message to the correct object. So while we will end up passing an object reference as the channel, this assumption forces us to view our code as though it is an isolated object unaware of how its method calls will affect others. This will enable us to ensure an extremely clean separation of concerns (SRP) and it will make it easier on us to verify when we violate SRP. How? Look at the semantic meaning of the code in the object. Does any of it seem out of place for an object that's managing the type of UI we are? Why isn't there any knowledge of the learning that this program will be doing? Think about this as we continue.
 
Once I had this code written, I wrote some quick test code just to make sure it was outputting the correct values to the correct spots in the HTML. I'll leave writing that code as an exercise to the reader as it is fairly trivial.
 
Next up, I iterated on the actor that managed the learning task. While the latest code is utilizing a markov chain to learn the users' patterns, I started it incrementally by just having it guess "yesterday's weather" (ie. use the current input as our prediction of the next input). This is the completed implementation:
 
 
As a refresher, the Markov Chain as I've implemented it tells us which value is most likely to be entered next given the previous value. I won't go into the implementation details but the code is fairly concise and is hopefully legible enough to be decrypted. 
 
The learning actor has just a couple of main parts to it.
  • The next(value) message that is passed the value that the user entered.
  • The _learn_from_new_information(previous_value, current_value) method that trains our markov chain.
  • The _make_best_guess(value) method that utilizes our trained markov chain to make an educated guess about the user's next entry.
  • Last but not least, a simple set_guess_channel_to(channel) message that we can use to publish what we guessed and what the right guess actually was.
Initially, I had actually written the code that is now in the scoreboard actor as a part of the learning actor. Here's that code:
 
 
You can see it's fairly simple and likewise I was hesitant to move it to a new class. As you get started with this style, you will feel this quite often. I recommend fighting through the pain until you come upon the first "major" refactoring you need to do. The ease in which you'll be able to make that change I guarantee will astound you and you'll be hooked. Another reason I hesitated to move this out of my learning actor is that I assumed I would be duplicating the concept of "the previous value must equal the last". Since MOOD doesn't allow for getters I knew that the only way I could have shared that logic would be copy 'n' paste reuse (read: ewww). Look at the algorithm left over in the learning actor though. It never cares whether or not we guessed right. It only tracks the guesses and makes a hypothesis regarding them. So if guess checking wasn't a concern of the learning algorithm why did I have it there to begin with? I simply wanted to display a scoreboard. Hence the creation of my scoreboard actor.
 
We've got all of these objects but what to do with them? The configuration of our objects is referred to as the network configuration. This is essentially just a different flavor of dependency injection. The difference here being that your configuration will be able to be factored away from the rest of your code and isolated if you so choose. Here's the object network configuration for this code:
 
 
The first thing that should stand out to you is that we are making no attempt to make our objects immutable. In MOOD, just like in Actor Model, we are guaranteed that an actor will only ever be used from the context of a single thread throughout its lifetime. This might seem to be a poor constraint here is why it's not: Imagine the learning actor gets some VERY complex logic. That isn't a stretch depending on how accurate you want the guesses to be. So, if you had written this code without using this style and didn't explicitly design for asynchronicity what might happen? The first time that learning actor needs to really think, your UI will freeze up. Because we wrote this using Message Oriented Object Design however, we can throw that logic _anywhere_ and it won't block our UI. What do I mean by anywhere? I mean we could literally host it on a web service and instead of implementing our actor on the HTML we could have an actor that was responsible for interacting with the web service. Someday, if Javascript gets threads we could even throw the extra work onto a thread and create a channel object to manage the threading context on the passed messages. The rest of our code wouldn't change for either case. If you need an actual example leave me a comment to that effect because for now this seems as though it's easy to see especially once someone has pointed it out. In the meantime, if you've been thinking that Message Oriented Object Design is a lot of extra work for pedantic self-indulgent programmers think about whether or not your code could do that.
 
Oh yeah. Also, notice that there is only one VERY thin object in all of that code that has anything to do with the DOM. The rest is trivially unit testable. And not just testable in a small way, but testable as in only the object under test will be exercised. I didn't TDD this code. That's just the way the MOOD pulls me.
 
Also, I apologize in advance for my horrible naming of methods and objects. Hopefully it still gets the point across.
 
That's it! Go ahead and try it, it's pretty neat. Just "randomly" pressing keys on the keyboard the way I do the code was able to guess correctly 40% of the time or so. Not bad at all! Also, regular patterns like "abcabcabc" it will get pretty quick and you'll see the code try to follow you if you do something like "aaaabababaaaababababab". Of course, like all learning agents, the more random the string you enter, the worse the agent will perform.
 
The full HTML source code is here for you to download and try. It does require you to include jquery for it to work. Leave a comment if you have any questions! :)
 

Using Graphs to Build Your Own Ruby Pattern Matcher

There's More Than One Way To Skin a Rat!

A while back I posted an article on using dynamic programming to implement a string matching algorithm I cobbled together. That article is here: http://justinbozonier.posterous.com/string-pattern-matching-welcome-to-dynamic-pr

Tonight, I'm writing about solving that same problem but by using a graph. It was a solution suggested by a few people and then finally a couple of days ago my boss (Kelly Leahy) brought up the problem once more as I was asking for suggestions of CS concepts he thinks I should tackle and we got back on the subject of that pattern matcher. If it was mentioned so much in the past why did I jump on it now? Quite simply, I've been learning Ruby lately at the insistence of James Thigpen. He's been ranting and raving (on top of many others) so I thought this would be a great first project.

Tools and Techniques Used

I tried my best to stick to pure TDD and unit testing with a context/spec naming style and test structure using RSpec. For my IDE I tried using RadRails, RubyMine, and NetBeans. Ultimately I chose NetBeans. For some reason it turned out to be the easiest for me. **shrug**

This is my very first Ruby project ever and I typically do C# development so if you see some ugly .NET-isms... please flame away so I might learn ;D

Stating the Problem

The problem to solve is given a pattern such as "a.c*z" we need a way to determine if a string like "abcdefghijklmnopqrstuvwxyz" matches it (it does) and that a string like "afdgkjbdkfdstg" does not. Our pattern matching grammar will have only three basic elements. A literal element that matches a character in a string exactly (ex. a, b, c, ..., x, y, z, 0-9, etc), a match any element which matches any single character (a period ie. "."), and a match all element (an asterisk "*") which matches zero or more occurences of any character or combination thereof.

It's like a REALLY simple regex evaluator.

And I know some people are going to ask, why not just use a regular expression? They're super sexy and simple to use in Ruby. Why reinvent the wheel?

I have this crazy idea that even though frameworks are pretty awesome at abstracting the difficult detais away from our view, living in ignorance of the basic data structures and algorithms that these frameworks are constructed of, that just leaves us using these things not because they save us time, but because we are dependent on them to get the job done. I'm all for frameworks, but I want to use them because I understand why I should use them, not because I can't understand how to live without them.

What Makes Solving This Difficult?

One of the key things that makes this a somewhat difficult problem to solve if you've never encountered it before is probably best shown as an example.

Imagine you have the following test string:
"*a*a*a"

now imagine how you would test that the following string matches it:
"aaaaababaaaaaaaaa"

See the problem is the * matches everything including the a so how do you know whether to treat the a as a part of the asterisk or as a literal? The answer that Kelly helped me to formulate is that you treat it as both. Basically you allow your solution to branch and when you come to the end of the string you're testing, you look to see if any of the branched paths finally completed the pattern.

I designed the program so that every character in the test pattern represents a given transition from one state to another. There are also three different types of states. A starting state where every match algorithm begins life, a terminal state which is where all matches will end life, and a standard state that represents an interim step from character to character.

So given our string pattern above, the program I wrote would generate the following graph:
  • Start State
    • Transitions to itself on any character (the asterisk)
    • Also, transitions to the next standard state via a literal transition edge that matches on the letter "a"
  • Literal Transition State
    • Transitions to itself on any character (the asterisk)
    • Also, transitions to the next standard state via a literal transition edge that matches on the letter "a"
  • Literal Transition State
    • Transitions to itself on any character (the asterisk)
    • Also, transitions to the next standard state via a literal transition edge that matches on the letter "a"
  • Literal Transition State
    • transitions to the terminal state via an always transition edge.
  • Terminal State
Getting Down to Brass Tacks

Let's look at the transitions and states in code to try to make some sense out of what has been a fairly abstract read up until now. First the graph states:

As you can see the states really do nothing aside from managing their transitions. I do a poor job of encapsulating these from the rest of my string matching world (ie. the objects that use this array could technically add to it directly) and that should be marked for refactoring later (whether or not it is is my lil secret! ;)

And then the transitions:

These are even simpler! The only bit of logic to a transition is it's test to determine whether or not the provided character can be transitioned on. 

Hopefully from just seeing this code you can get a pretty good feeling for how these things might fit together.

What gets more complicated is the building of the graph. I like to imagine that specs can help to explain the code they test somewhat so let me share some of those first:

My tests are awkwardly named so I could use some naming help if you care to leave a comment! :)

This is the class they test:

Here's a quick high level explanation:
  • First, create the root of the whole graph. This is ALWAYS a start state.
  • Store that as the state we're currently adding transitions to. (line 9)
  • Next, for each character in the test string we are matching against the string pattern create the appropriate transition.
  • Add the newly created transition to the current state
  • Set the current state to point to the destination of the new state provided by our new transition.
  • Rinse, lather, repeat...
  • Once that's done ALWAYS create a terminal state as the last state.
  • Attach it to our current state by adding a transition always transition to the current state that points at the final state.
Now about this transition always transition. It feels dirty and like needing to know the start and end state should be unecessary. Even in the current state needing to know the start state is probably unecessary, but the final state... I'm not sure how to handle that generically like the other states. Thoughts?

Also, notice the code block on line 11! That was my first sampling of Ruby awesomeness. I should totally have been able to avoid writing my own string reader by using ruby's string.each_char |c| {} code block but I learned about that after wrapping up and I didn't care to do more refactoring at the time. :)

Notice how I lied about the difference between a "." and a "*"? They're both the same transitions but they have different destination states. Here it is again:

The "*" transition acts as more of a loop back into the same state it left. The "." moves us forward to the next state.

Meat and Potatoes Time!!

Now all of that was built with the ultimate focus on getting the construction of the actual matcher to be as easy as possible. Here are the tests for how the matcher is ultimately used:

God it's painful showing off code that I'm sure could've been written more elegantly! I always convince myself it's for the best to not go back over it an edit it so that way it gives a more honest view of my coding process and doesn't turn into Justin just trying to look pretty.

So without further ado this is the entire implementation of the code that actually utilizes the graph to match a string against a given pattern:

Here's a general overview of the steps involved so that you can hopefully glean as much from my code as possible:
  • First "compile" the test pattern provided by the user into a graph representation.
  • Next make that graph the first state to be evaluated (a graph is really just represented by a start node that acts as the root.
  • Next we read the next character from the test string provided by the user.
  • We every transition of every state that has been queued for evaluation.
  • For each transition that tests true on its can_do method grab that transition's destination state and place that into our next states list/array.
  • Once we've done that for every state and transition until we've ran out of test string to process there should be at least one state in our next states queue that is ready to transition to the terminal state (assuming there is a match).
  • If there is then return true! We have a winner!
  • Else it's false and these strings don't match according to the given pattern.
Was It Good For You?

I try to share these kinds of learning experiences because so many times in the past I've been so thankful when someone else did. Maybe you're like me and don't have a CS background/degree and are trying to find ways to make data structures and algorithms more practical/applicable. It can be hard to take theory and find a way to apply it. Well anyway, hopefully it helps somebody.

Also, Ruby is a pretty nice language. I might even enjoy it more than Python (I like having an end keyword instead of ambiguous white space ;).

If the mood strikes you, you can find the whole project on my github account here: http://github.com/jcbozonier/DfaStringMatcher

Also, I know I call this a DFA in the github title but it isn't. A deterministic finite automata would have no cycles, whereas my graph does.

So that's that. If this was the least bit helpful let me know by leaving a comment and if you feel like I got something wrong or left something else out entirely leave a comment to that effect as well. Thanks for reading!

String Pattern Matching: Welcome to Dynamic Programming!

The Challenge

So here's the puzzle you're provided: Given a string pattern tell if another given string matches the pattern. The character "." is a wild card that can only match one character and a "*" is a wild card that can match as many characters as possible. Nothing matches a missing character.

For the pattern "a.c*f", for example, "abcdef" would match as would "azcrwgfdjkgfdkjhdfjkfhf" but "bbcdef" would not.

How would you go about solving this problem? When I first set out to solve this problem I got horribly stuck. I tried to use just a for loop and then got totally lost in that the possible permutations branched all over the place. It seemed nigh intractable (for me of course since I knew this was solvable since regex does even more coolness than this).

Side note: That is a great way to tell what computer science challenges deserve your attention most. If you literally can't even come close to tackling a problem understanding how to finally conquer it will make you a better developer by an order of magnitude each problem IMO.

Think about this for a bit cuz up next is the solution.

A Speedy Savior

So first off, one solution would be to create a string for every possible permutation of the pattern (up to the test string's length) and check if one of those patterns matches your test string. There are two issues with this approach: A) It takes up a lot of space and B) it would take a LOT of time.

To prove it would take a lot of time consider that our solution would essentially need to consider every letter in the place of the wild card. That's 26 additional runs PER single wild card... in the case of the asterisk that could be 26^N where N is the number of letters your wild card might take up. In the larger example above, with that technique, there'd be at least 766,467,265,200,361,890,474,622,976 permutations just to the wild card alone.

Thankfully as it turns out there's a better way: Dynamic programming! Ok so what is dynamic programming and why does it apply here? Basically, dynamic programming can be helpful whenever you have a problem that breaks down into individual subproblems that can be combined together to form a complete answer. Once you've solved all of the individual subproblems you start from the finishing line and make your program assume that you found your optimal solution and try to work out what the previous step must've been given that the current step is optimal. 

What some of you might be thinking is... what if my string doesn't match? Assuming correctness seems wrong in that case huh? You definitely don't want to return a false positive but that won't happen. What will happen is that if you're program isn't able to match the strings, then the algorithm will be left incomplete and will never reach the block of code that says to return true. Essentially we only say there is a match if the algorithm starts at our finish line and ends up at the starting line we specify. If that path is broken, then our algorithm will return false.

Another benefit of this method is that the worst case runtime is O(mn) or for you non-computer science types, the number of steps the algorithm will take is approximately equal to the length of the pattern string multiplied by the length of the test string (the string we're matching against). In our large sample above that would be about 115 steps to figure out the solution (at the worst)!

Forming a Recurring Subsequence Problem

This is really the hardest part. You need to think about the problem from several different angles until you can see it as a sum of several smaller problems. Once you see this subsolution though the programming just pops out at you.

In our example with the strings, I had been thinking about how I could break this up for the better of the day in the back of head during idle cycles. Finally when I sat down to draw out some ideas (I'm very visual) I realized that I could create a table with the pattern string forming the columns and the test string forming the rows. Once that was done I marked the cells that matched with a T (for True) and an F if they didn't. I saw that in cases where I expected a match, I could traverse the table from the upper left corner to the lower right by traversing cells diagonally (or vertically in the case of an asterisk or a period).

I know this is hard to visualize so I'm going to *try* to give a visual here... bare with me.  :)

1 is True and 0 is False BTW...

Pattern: ".a*.j*"

Test string: "cadeajmn"

. a * . j *
c 1 0 1 1 0 1
a 1 1 1 1 0 1
d 1 0 1 1 0 1
e 1 0 1 1 0 1
a 1 0 1 1 0 1
j 1 0 1 1 1 1
m 1 0 1 1 0 1
n 1 0 1 1 0 1

That is the test that made me have my "a-ha" moment. So now looking at this primitative visualization let's see how our pattern matching rules show up here. First notice that the asterisks and periods have their entire columns set to true. The reason for this is that they can stand in for any letter so given appropriate positioning they **could** be true in any of those instances. I got a little tripped up here. I thought that this matrix should represent the fact that my period can only represent one letter but that turned out to be unnecessarily complicated during this phase. The 2nd phase, as you'll see, makes that much easier.

From here see if you can start at the finish line though and work your way back to the start. Now while it *is* possible in this table that you could move from cell to cell horizontally, our phase 2 rules won't allow for this. If we did allow this that would mean that two pattern characters could match to one test character and hopefully you can see why that makes no sense in our scenario. Also remember that you can only traverse cells vertically if you're in an asterisk column (since that means that that single pattern character matched multiple test strings and that's the only pattern character capable of doing that by definition).

Note that we know if our traversal was successful because at some point, on some path, we will arrive at cell (0,0). If we miss the starting line and go off the table, then we don't have a match.

These last two paragraphs we've basically listed out the rules for our recursive algorithm. More clearly, they are as follows:

Given a cell (i, j) where i is the column, j is the row

  • if we reach cell (0,0) AND this cell's value is true we have a match
  • if we reach a cell where either i or j are negative we have no match (for this path, regardless of the value)
  • if none of the above but the current cell is true then test cell (i-1,j-1) (the cell to the upper left)
  •   if that doesn't have a complete path and we are in an asterisk column try the row above

Here are those same rules but in code:

private static bool _HasCompletePath(IList<List<bool>> matrix, int patternIndex, int stringIndex, string pattern){    var result = false;     if(patternIndex < 0 || stringIndex < 0)        return false;     if (patternIndex == 0 && stringIndex == 0 && matrix[patternIndex][stringIndex])    {        result = true;    }    else if(matrix[patternIndex][stringIndex])    {        var tempResult = _HasCompletePath(matrix, patternIndex - 1, stringIndex - 1, pattern);        if(!tempResult && _HasCompletePath(matrix, patternIndex, stringIndex-1, pattern) && pattern[patternIndex] == '*')        {            tempResult = true;        }        result |= tempResult;    }     return result;}

Wrapping up

I don't expect this to make perfect sense to someone who has never written a dynamic programming algorithm in their life. My main hope is that by me sharing the insights I gained while I'm still new to this that this will help others to learn this stuff a little easier. If nothing else, it should at least provide a new non-formalized non-mathematical perspective (which is REALLY difficult to find on the web).

Full source code is available here: http://github.com/jcbozonier/Dynamic-Programming-Sample/tree/master