GraphLint: Creating a Domain Specific Language for Graph Validation

Posted on by
2

Kenny Yu is currently a sophomore at Harvard College where he is studying computer science. In the summer of 2011, he interned at Knewton as a software engineer. During his internship, he built a new source review and release process and created a graph validation engine based on configuration schemas. He interned at Knewton again in January 2012 and rebuilt the graph validator by creating a domain specific language. The following blog post is a summary of this project and the process he used to design the language and the new validation engine.

The Question

At the core of the Knewton Adaptive Learning Platform is the course structure that brings all the lessons, concepts, and content into one connected graph. This graph is so large that checking it by hand is infeasible. Thus, Knewton’s graph datastore needed a validation system to check the structure of its graphs.

The validator idea is simple: given a graph, how can we tell if it is “well-formed”? How can we create a set of rules to express what edge and node types are acceptable in a given graph? My mentors, Jordan Lewis and Trevor Smith, decided that I should build a domain specific language (DSL) for writing the ontology schemas to solve this problem.

Developing the Language: “Onto”

Before creating the DSL, I had to understand the use case of the language I was building. After speaking with developers and content creators at Knewton, I composed this list of considerations that would drive my planning process:

  1. Expressiveness of the language – Above all, the language must be capable of encoding complex relationships between nodes and edges.
  2. Simplicity and ease of writing the language – The language must be easy to write and so easy to understand that non-developers can think and write in it.
  3. Ease of implementing the language – It should be easy to take the language and parse it into a form that can be used for graph validation.
  4. Graph validation run-time – Once the ontology had been parsed from the DSL into usable form, how quickly can we validate a graph using the provided ontology?

The graphs I worked with are directed multigraphs, where edges and nodes may have associated data with them. In Knewton’s case, both nodes and edges have types (e.g. “Concept”, “Module” and “Contains”, “Represents”). Using these types, we want to assert relationships like:

For all nodes m of type Module, there exists exactly 1 node c of type Concept such that the directed edge (c,Contains,m) exists in the graph.

We also want to express logical combinations like the following:

For all nodes c of type Concept:

there exists exactly 1 node m of type Module such that the directed edge (c,Contains,m) OR (c,Represents,m) exists in the graph

AND

there exists exactly 0 or 1 nodes m of type Module such that the the directed edge (c,Contains,m) exists in the graph.

I used statements like these as inspiration to create the DSL. The DSL consists of these statements:

  1. Universal quantifier statement: for all <variable> in <node type> <statement>
  2. Existential quantifier statement: there exists <number rule> <variable> in <nodetype> such that <statement>
  3. Edge rule assertion statement: (<variable>,<edge type>,<variable>)
  4. And statement: <statement> and <statement>
  5. Or statement: <statement> or <statement>
  6. Xor (Exclusive or) statement: <statement> xor <statement>
  7. Not statement: not <statement>

Thus, the above two statements, written in the DSL, look like this

and the second one:

Lacking creativity, I decided to give ontology file names the “.onto” extension, and thus the Onto language was born.

Language Implementation Choice

It was difficult to determine which language I would use to implement this project. Having recently taken a compilers class in OCaml and knowing the benefits of OCaml’s strongly typed system and functional programming language features (and my personal preference for coding in OCaml), I thought that OCaml seemed like the natural choice for this kind of project. However, after I considered the reusability of this project with other systems in the company, I realized that OCaml would not be the best choice. The company recently decided to move towards Java and possibly other JVM-based languages. I had researched Java-OCaml bindings and discovered that existing options couldn’t meet this project’s need. As a result, I chose to implement this project in Java to make it more compatible with other systems at Knewton.

Having only used ocamllex and ocamlyacc to create parser generators, I needed to research other parser generators for Java. My mentors suggested ANTLR. I found ANTLR to be a high quality project that was incredibly easy to use.

Validation Algorithm

Now that I could successfully parse ontology files into memory, how would I validate a graph? I decided to implement the algorithm in a functional way: traverse the abstract syntax tree (AST) generated by the parser and for each statement node, create a closure that, when provided an environment–a mapping from variable names to actual nodes in the graph–and called, would return “true” or “false” (and thus represent whether the graph passed validation on that statement). After traversing the entire AST, one closure would be produced and would represent the validate function. A list of errors would be generated if the graph failed validation.

For example, I did the following for the Universal quantifier statement:

for all <variable> in <node type> <statement>

  1. Generate the closure by traversing the AST in <statement>
  2. Iterate over all nodes with type <node type> in the provided graph, and for each node:
  1. extend the current environment by mapping: <variable> to current node
  2. call the closure on this new environment, and ensure the closure returns true

I followed a similar procedure for the rest of the node types in an ontology.

Unfortunately, closures are not directly accessible in Java. Instead, I had to generate wrapper classes that wrapped methods representing the closure. In addition, because of the lack of match statements in Java, I used the visitor pattern to traverse the AST.

Testing and Profiling

After unit testing the validation engine on small graphs and simple ontologies, I moved on to a real life error-riddled data set. The graph in the data set had 53,377 nodes and 53,960 edges. When I initially tried to validate this graph, the JVM exploded. Even with 2GB of memory, the JVM still did not have enough heap space to validate this graph in half an hour. After profiling, I discovered that over a hundred million Strings were being generated by error messages for failed validation. As a result, I made several changes to make the validator more memory efficient: I used the flyweight pattern when allocating space for environment variables, node and edge types, and I lazily generated the error messages, only creating them when necessary.

This solved the memory problem. However, the run-time of the validation algorithm was still horrible. Each nesting level of a for all and exists statement added a factor of V to the asymptotic run-time (where V is the number of vertices). For example, if an ontology had three nested for all statements, the run-time would be O(V^3). Fortunately, since edges could only connect two vertices (unlike in a hypergraph), I could optimize the exists statement to only check in the neighboring set of the current node. With this optimization, exists statements no longer multiplied the computational complexity. As a result of these memory and time optimizations, the run-time for the 50,000+ node data set went from 30+ minutes to less than 4 seconds. Changing the run-time from V^2 to V makes such a big difference!

Looking Back, and Next Steps

It’s a rare opportunity to go back and rebuild old projects from scratch. It’s an even rarer opportunity to get complete freedom (as an intern) to design a central component of the company’s system. At Knewton, I was fortunate to have both opportunities. Knewton tasked me with rebuilding the graph validation engine, and I had complete freedom to design the project however I wished. Even more remarkable–this project allowed me to to work at a scale (50,000+ nodes!) that I would rarely ever touch at school.

There are several things that in retrospect I would have done differently. The lack of functional language features in Java made it difficult to implement the validation algorithm. As a result, if I were to redo the project, I would probably implement it in Scala. Using Scala’s interoperability with Java and its functional language features (especially the ability to create closures and use case classes) would have made the implementation easier to write and more concise. Furthermore, there are many optimizations I could have implemented to make the validation engine faster: I could have used properties of second-order logic to transform quantifier and logic statements into equivalent statements with a faster run-time, and I could have parallelized the algorithm to make use of concurrency. But this is pretty good for working just two and a half weeks!

Simplifying Cross-Browser Javascript Unit Testing

Posted on by
Reply

By Daniel Straus and Eric Garside

Javascript unit testing is complicated and expensive; unlike server-side logic, code that seems to work fine may execute differently on different browser/OS combinations, which means that in order to get adequate test coverage, all supported platforms need to be tested thoroughly. In order to allow our codebase to be testable as it grows in size we came up with a way to make our testing process easy and scalable.

To write our tests we used ScrewUnit, a behavior-driven testing framework which provides an extensible cross-browser utility for developing tests. Each test suite is just a web page; running it is only as difficult as pointing a browser at it. Let take a look at an example:

This test passes in a Webkit browser, but not in Internet Explorer (IE can’t process the date format). As you can imagine, it would be quite time consuming to have to run tests like this on multiple browsers manually on every check-in.

To make the use of ScrewUnit manageable and efficient we turned to Selenium-WebDriver (a browser automation tool). We can write Selenium routines to open a project’s ScrewUnit test and analyze its results. With a single line of code, we can check if ScrewUnit detects failures:

This is improved over the previous method. But to make this process optimal we wanted to run these routines in parallel. To accomplish this (run across multiple browser/OS combinations) we used Sauce Labs. Sauce Labs allows us kick off tests from a single machine quickly and doesn’t require a large testing hardware infrastructure on our end (everything runs in the Sauce Labs’ cloud). Below is an example of how this all comes together:

By combining ScrewUnit, Selenium and Sauce Labs, we removed the complexity of running Javascript unit tests across multiple browsers. We’ve put together a demo of our tests as they run on our own project.

Knerdlings: Improving Courses through Simulation

Posted on by
Reply

N choose K’s inaugural post is brought to you by the Knewton Adaptive Learning Team (Ashley Miller, Christopher Tang, David Kuntz,  George Davis, Jesse St. Charles, John Davies, Sidharth Gupta)

No two students are identical—they learn and forget at different rates, come from different educational backgrounds, and have different intellectual capabilities, attention spans, and modes of learning. As a result, designing a real-time recommendation engine that is sensitive to the idiosyncrasies of each student is an immensely complex task.

Here at Knewton we are addressing this challenge head-on, using educational path planning technologies and advanced models of student ability. These technologies and models ensure that, no matter how different students are when they enter our system, each of them progresses through the course material in a way that maximizes his or her individual rate of learning. In our ongoing research and experimentation to improve these student models, our latest and most diabolical step has been to create our very own army of virtual abecedarians (Knerdlings), who assist in the testing of our recommendation engine.

Testing Our Recommendation Engine

One good way to evaluate the courses that make use of our recommendation engine is of course to collect and analyze real data generated by real students. These analyses are critical to maintaining and improving the quality of our courses for future students, but real students take real time to complete a course. So, to enable ourselves to research and develop in the interim, we needed a flexible and automated way of generating student data. With this goal in mind, we engineered a virtual student named “Isaak” and used him as the prototype for a whole army of Knerdlings.

In addition to meeting the goal of generating usable data, there are numerous advantages that this strategy offers us. First, it gives us an efficient way to simulate taking our course over and over (and over and over) again. Second, we gain fine-grained control over the many possible kinds of students who could use our course in the future. Next, we can induce particular behaviors in students, and simulate a broad range of student abilities and learning styles. Last but not least, we can be as realistic as we need to be, and nuanced in the exact ways we expect a real-world student would actually be. With these thoughts in mind, we designed the inner workings of Isaak’s mind.

Modeling Student Behavior

The core of Isaak’s mind is a graphical (that’s “graph-based,” not “made of pretty pictures”) model that keeps track of the current state of Isaak’s latent abilities—like his proficiency in “Solving 30-60-90 triangle problems,” or in “Understanding trigonometry”. If Isaak were a real student in a Knewton-powered course, he would be exposed to instructional content and take assessments, and his performance on these assessments would play a role in determining his path through the course. Each student’s latent abilities determine how well the student performs on any assessment of a given topic or concept—in technical parlance, latent ability contributes to a “generative model of performance”. To model student behavior more accurately, Isaak’s latent ability levels also need to improve over time as he is “exposed” to more material, and to degrade without proper reinforcement.

In short, Isaak needs to be able to learn, and (regrettably) needs to be able to forget.  Inspired by research that started with Hermann Ebbinghaus’s work on memory retention and learning curves, we model the changes in Isaak’s latent ability, while learning and forgetting, using exponential growth and decay curves. Isaak doesn’t actually do any learning (or forgetting), of course—he just receives a “bump” in his virtual ability level for a topic each time we expose him to content associated with that topic. (The precise nature of that “bump” depends on the functional form of the learning curve.) Likewise, if Isaak is not exposed to some other topic, he might forget that topic over time. The forgetting curve itself that governs Isaak’s rate of retention is roughly described by the following formula:

,  where R is memory retention, S is the relative strength of memory, and t is time.

By integrating this process into the simulation, we can capture the way in which a student’s knowledge waxes and wanes, depending on how and when they are exposed to various content. The resulting simulation isn’t a perfect recreation of real student behavior, but, in addition to being really cool, the corps of Knerdlings generated in the simulation lets us test the algorithms that govern a student’s flow through the course quite stringently, while maintaining enough simplicity for us to understand the results.

Visualizing the Data

Once we were ready to set our army of Knerdlings loose in our courses, we needed to make sense of the copious amount of data they were about to generate. We did this by summarizing the results in a visualization that lets us understand the behavior of our virtual students graphically (this time, that’s “graph-based” and “in a pretty picture”). The visualization lets us watch latent ability levels change over time, as individual Knerdlings interact with a Knewton course, in a way that’s much easier to grasp than, say, a spreadsheet containing the exact values of a student’s ability on every concept for each hour that they were enrolled. We have nothing against spreadsheets here at Knewton—they have their place—but problems and strange behavior jump out much more clearly to us visually.

Creating Better Algorithms

The visualization tool will also have applications outside of Knewton HQ. In the hands of an instructor, for example, it could help track the progress of students, and allow the instructor to adjust her course plan to account for her students’ likely learning states. Say that a student has passed a sizable number of the units in the course, at a point well into the semester. The student has most likely forgotten some of the topics that were covered earlier in the semester and not revisited since. Using this visualization, along with the Ebbinghaus-based model of learning and forgetting, the instructor now can see at a glance what parts of the course the student is most likely to have forgotten—even what parts the student is likely to forget in the future—so that she can remediate her student appropriately.

So far, this graphical tool and its associated models are only operational internally, but those models are already helping us create better algorithms, which in turn are going to start moving students through Knewton-powered courses more efficiently than ever before, during this next academic year.