Intent Media Engineering Blog

intentmedia.com

[intentmediaengineering]

Bayesian Inference for A/B tests when metrics have categorical distributions

Most A/B testing happens within the classical statistical framework that involves p-values, statistical significance and confidence intervals. More recently though there has been much interest in using Bayesian inference techniques in setting up and interpreting A/B tests. Terms such "Bayesian A/B tests" and "Bayesian bandits" have been used to describe these techniques. I will not reinvent the wheel here and as an introduction to the topic refer you to other sources [1][2]. In particular, I would recommend Sergey's post as a minimum prerequisite to follow the rest of this post.

The most common example discussed in the context of Bayesian A/B tests is that of binary metrics such as click through rate (CTR) and conversion rate, which is natural given how ubiquitous these metrics are. The case where ads are either clicked or not, or when users either convert or don’t can be modelled as independent bernoulli trials and the likelihood of data under this model follows a binomial distribution. The beta distribution comes in handy as a conjugate prior and story is soon wrapped up as demonstrated in Sergey’s post.

Metrics however do not exist in a vacuum and must be tailored to the way the user interacts with the product in question. As a result, one often ends up with many standardized metrics that everyone understands such as conversion rate, ROI, etc and a few custom metrics that are unique to the product.

In the rest of this post, I introduce one of the keys metrics here at Intent Media - Clicks per page view (CPPV) - which does not have a bernoulli distribution. I show how the Bayesian A/B testing framework can adapted to this metric.

Our Metric: Clicks per page view (CPPV)

A typical Intent Media page view in response to user’s search for a flight might look like this.

Each page view has "impressions" from multiple advertisers and a user is encouraged to comparison shop between any combination of advertisers. So a given page view could result in anything from 0 up to N clicks, where N is the number of ads in each page view (typically N ranges from 3 to 5). Since the advertiser pays for each click received, the number of clicks per page view (CPPV) is one of our key metrics.

Clearly CPPV does not follow a bernoulli distribution. One can certainly derive a transformation that has a bernoulli distribution. For instance, if we instead measured whether a page view receive at least 1 click, that would have a bernoulli distribution. While useful, this metric fails to capture the number of clicks received conditional on receiving at least 1 click and is therefore inadequate. So we are back to working with CPPV. But is having to work with CPPV really that bad? Well, not really.

CPPV as the categorical distribution

Consider the die roll. Receiving up to N clicks can actually be thought of as a roll of a loaded die. Given K rolls (page views) each of which can result in one of 6 faces (N clicks), the distribution of outcomes follows the well-known and widely studied multinomial distribution. This means that the likelihood function i.e. Prob(Data | model parameters) can be modeled as coming from a multinomial distribution. Note that for this to work we must make the (very reasonable) assumption that only one click per ad in a page view is considered valid.

As I mentioned in passing earlier, working with bernoulli distributed metrics is convenient since the resulting likelihood function - a binomial distribution - has a conjugate prior in the beta distribution. The resulting posterior, also a beta distribution is analytically tractable and easy to sample from. Fortunately, the picture doesn't change much with a multinomial likelihood distribution.

Enter the dirichlet distribution. Much like the beta prior is a conjugate prior for the bernoulli distribution, the dirichlet distribution is the conjugate prior for the multinomial distribution. And this is not at all incidental since the dirichlet itself is a multivariate generalization of the beta distribution.

Bayesian inference for CPPV

And the rest as they (never) say is just works by analogy to the beta-bernoulli case. Here is some python code that demonstrates this. Imagine we have 2 variants A and B. The goal of inference is to estimate the probability of A being better than B i.e. P( A > B ). One can often derive an analytical closed form solution [3] from first principles - if A and B have known functional forms and P(A > B) is the area under the curve in the region where A > B. More often than not analytical solutions are not available (no functional form or messy integrals) and sampling methods save the day. So I instead sample from A and B, pair them and empirically count the fraction of pairs where A > B. (it doesn't exactly matter how you pair them since samples are independent)

The code is setup as follows.

I track the performance of A and B through N-dimensional vectors (1 per variant) that contains the number of page views with 0 up to N-1 clicks.

To start with the page view counts for A and B are the same and as one would expect, doing inference gives us 0.5 i.e. A and B are evenly placed.

To illustrate how P(A > B) changes, I keep A constant and incrementally make B worse. At each increment, I estimate P(A > B) and notice that this quantity converges to 1, which means once B is 'different enough' from A, we are certain beyond any doubt that A is better.

  This post dealt with how to do inference on data from an A/B test when the metric is not the standard bernoulli. In a future post, I will outline how we can use the estimate of P(A > B) in a real-world experimental setup.

  [1] - http://engineering.richrelevance.com/bayesian-ab-tests/

[2] - http://developers.lyst.com/data/2014/05/10/bayesian-ab-testing/

[3] - http://www.evanmiller.org/bayesian-ab-testing.html

Sharath Rao is a data scientist at Intent Media. His interests are in using machine learning to help people be better people and machines be better machines. You can find tweeting and blogging life and work.

[intentmediaengineering]

Engineering Your Own Education: Part 2

In the previous post, I went through a few of the ways that an engineer can develop the skills that help get that great job in tech.  Mostly, I talked about things that you can do outside of your working life to get better.  In this post, I’m going to get into how learning can be part of your job.

I think that most smart engineers have an appreciation for the material in the previous post. Most promising candidates I meet understand that they need to be as best prepared as they can be to snag a fun, challenging tech job. The point I see many miss though, is that their tech job is the beginning of the next phase of education, not the end of their education.

One of the most important things a professor ever said to me was the following.

Everything that I’m going to teach you in this class was invented after I left school.

The professor was Dennis Kroll, and the topic of the course was Java development (that thing I now do for a living). His point was about the duration of our educational journey as engineers. If we wanted to stay useful and relevant as engineers, we were going to have continually find ways to learn more, throughout our professional careers.

If that sounds unreasonably challenging, I have good news for you: we have the tools to make this easy. Working in an exciting technology startup involves all sorts of learning as an embedded part of the work.

For example, at Intent Media, within the past year we’ve had study groups of various sorts around TDD, management, QA, and functional programming. If you’re a student getting bored and exhausted with tedious homework, this might sound like a negative to you, studying more once you already have a job. It’s actually a huge benefit. These sorts of opportunities give you a chance to continue to get getter at the things you do and the things you want to do in the future, guided and supported by the people who know your work the best, your coworkers.

Beyond simple things like study groups, startups can be places where people experiment with and rapidly adopt new techniques that are going to allow you to develop and grow as an engineer more effectively. I’m thinking of things like agile squads (which we just adopted at IM) to organize the teams and lean coffee to run meetings. These are techniques which will have an explicit impact on how well you are supported and guided to become a better engineer.

Another great technique that a company can use is pair programming. If you’ve never tried it, pair programming might sound scary and invasive. It’s not. In fact, pair programming is one of the best tools that an organization can use to ensure that all of its engineers are growing and learning. When you pair program, you are directly in the code learning from another engineer how they write good code. The examples could not be less abstract; you learn from implementing your actual work. This is miles away from the frustrating artificiality of school homework.

But pair programming at its best is not just a one way street. It’s a great way for everyone to learn from everyone else. Even if the code that you know that I don’t is just the 10 lines of Java you wrote yesterday, that’s still 10 line of code that I know nothing about.  If I’m on your team, I want to learn what you know about that block of code.

As a cultural practice, pair programming promotes a more egalitarian environment where it’s explicitly recognized that all engineers have knowledge to share and deserve the opportunity to learn from each other. On the data engineering squad that I work on, we’ve formalized this with this saying:

We are all teachers and students.

By which we mean that we should all be humble enough to learn from each other.  This also means that we should be thinking about teaching as a core component of our jobs.

As I talked about in this post and my recent talk at CITCON, data engineering teams need to ensure that all team members have a shared understanding of the problem, the application, the techniques, the failure modes, etc. One of the obvious first steps for a team looking to build reliable machine learning software is to ensure that everyone has some basic level of education in what machine learning is and how it works.  Ideally, those team members with the most amount of knowledge in this area should be working on sharing that knowledge with the other members of the team.

When I worked for AI pioneer Ben Goertzel, he never hesitated to teach new hires concepts as basic as the difference between precision and accuracy. If he has the time to teach new members of his team, then I think that all senior engineers or data scientists should have the time to ensure that their team members know what they need to know to be able to make valuable contributions. Training team members so that they understand the problem domain should be a given.

And, of course, teaching a topic is also one of the best ways to learn a topic. So, as an engineer learns over their career, they may find themselves switching formal roles from student to teacher, but they should still be learning through teaching.

Learning how to choose

I hope all of the above material is useful to the engineer looking to understand how they develop the skills to get a good tech job. I understand that it can be hard. Despite the enormous shortage of software engineers, it can still be quite difficult to find the right job when you’re just starting out.

The well prepared software engineer is likely to have a wealth of choices, though.

Even in that situation, it can still be hard to understand the basis for which you should choose Company A over Company B. Given how important learning and growth are to your future as an engineer, I’d strongly encourage you to think about how you’re going to grow before and after you get that first exciting tech job. It’s been my experience that startups offer great environments to learn and grow as an engineer. If you asked me to recommend just one company, I think it’s clear whom I would recommend.

But regardless of if you come to work with me, I think that you should work at some place that values your lifelong development into a better technical professional. My best advice on how to get into such a place is to start thinking and acting in terms of that scale: your entire working life as an engineer (even if you wind up in management someday).

You owe it yourself and everyone who helped you get this far to never stop learning. The journey of becoming a better engineer is never ending but never disappointing, either.

Jeff Smith is a data engineer at Intent Media working on large scale machine learning systems.  He has a background in AI and bioinformatics.  Intent Media is the fifth startup he’s worked at, and it’s easily the most fun one.  You can find him tweeting, blogging, doing more blogging, and drawing comics all over the internet.

[intentmediaengineering]

Engineering Your Own Education: Part 1

One of the fun parts of being on a rocket ship of a startup is that I get to spend some of my time recruiting. I know that not every engineer enjoys recruiting, but personally, I really love it. When I recruit for Intent Media, I’m helping to introduce some smart motivated people to awesome jobs where they will have every chance to succeed in their professional goals and have a great time along the way. It’s sort of like being Santa Claus for good engineers.

One of the most salient aspects of recruiting for me is the difference between people working in data science and engineering and those looking to get started in the field. I got my first job in a data science group back in 2008, before there was a lot of clarity around this emerging profession.  Now, when I talk to mathematically inclined people who can write some code, they all want to talk about data science. Recent grads with degrees in things like electrical engineering, physics, and biomedical engineering are all rushing to brand themselves as data scientists.

I understand the technical person’s desire to align themselves with a hot field, overflowing with good paying jobs.  As a strategy it makes sense, but engineers can fail to appreciate the negatives such an approach has.

What I want to know most when I meet a less experienced engineer is not what they know;

it’s what they’ll learn in the first year that I work with them.

So when a twenty-two year old physics grad tells me that he has a strong background in data science, I get quite concerned about where he sits on the Dunning-Kruger curve. It’s okay to know that you know nothing. If I’m considering working with you, I’d prefer that you know that you know you know nothing. It’s cool. I know that I also know nothing, but working effectively together, we should be able to find a way to implement the next feature story in our backlog. We just need to make sure that a little thing like hubris doesn’t get in the way of learning the things we need to know to solve the real world problems in front of us.

Learning how to learn

I enjoy it when someone asks what they should learn to get a job in data science and engineering. It shows that they appreciate that there is more to be learned. But I would love to be asked how they should learn those things.

Even though no one asked, I’m going to tell you anyway. This is not another post on, “What does a data scientist do?” Those resources are out there. I’m going to assume you can Google as well as me.

Instead, I want to focus on the lifelong process of becoming a better engineer. Because I work on fun big data stuff, that certainly influences my perspective and what people want to talk to me about. But I think these tools and techniques apply equally to all kinds of engineers, including those oh, so sexy data scientists. They’re engineers too.

The Old (and New) School

You can’t talk about learning and software qualifications without wading into the contentious territory of whether or not programmers need a CS degree. This is a complicated issue that some people have very strong opinions on.

To summarize my views on formal CS education, I’d say that it’s great preparation if you can get it. Personally, I worked for a fair bit in software without having a degree in CS, so I don’t think that it’s mandatory to have the qualification. But it should be mandatory to have the knowledge, at least some of it. When I worked in software without a formal qualification, I was useful because I had still learned all sorts of things about software.

How did I learn those things? In my case, I learned mostly from books and practice. When I did finally decide to get a CS degree, it was in large part to signal to employers that I had in fact read those books and practiced the material in them.

ProTip: If you can’t get a degree in CS, at least read the textbooks and do the work.

That will give you most of the benefit of formal CS education.

Of course, the 2014 version of this advice has to acknowledge that if you can do that, then you can probably do a bunch of MOOCs. Coursera, Udacity, edX, and all the other MOOC providers offer world class education for little to no money at any pace (I prefer to watch lectures at 2X, personally). There’s nothing stopping you from getting just as good at programming and statistics as the best and brightest from Stanford and MIT.

I started taking MOOCs during that first experimental session taught by Thrun, Norvig, Ng, and Widom at Stanford. While I was traveling across Indonesia for a month, I was also traveling through the inner depths of databases, guided by Jennifer Widom.

For various reasons, it was one of the best courses that I’ve ever taken in any topic. If you haven’t taken it, you should, especially if you’re interested in data science or engineering. Much of what data engineers do is to solve the old problems of databases at a new scale. Having a solid foundation in databases ends up being useful nearly every day of your working life.

More generally, if you’re an ambitious engineer, who wants to do great things in tech, you should definitely be taking advantage of world-class resources like MOOCs. Lots of us come from modest backgrounds that didn’t necessarily give us much of a chance to go to a place like Stanford. But now that Stanford is just giving away their education, you need to step up to the plate, if you have big data dreams.

Learning on the clock

Figuring out how to build solid engineering skills is a big topic, and I have even more suggestions on how to learn and grow as a professional.  In the concluding post in this series, I’ll change focus from things you do outside of work to things you can do as part of your day to day work as an engineer.

Jeff Smith is a data engineer at Intent Media working on large scale machine learning systems.  He has a background in AI and bioinformatics.  Intent Media is the fifth startup he’s worked at, and it’s easily the most fun one.  You can find him tweeting, blogging, doing more blogging, and drawing comics all over the internet.

[intentmediaengineering]

Testing a Dropwizard application with Cucumber-JVM and jUnit

Dropwizard has quickly become the framework of choice for implementing new web services at Intent Media.

Because we take testing seriously, one of the first things we do when developing a new Dropwizard application is write some integration tests to make sure it will interact with its ecosystem in the way we expect.

Suppose you want to write some integration tests for a Dropwizard server application using Cucumber-JVM, the Java implementation of the popular BDD test framework.

How do you start your application and make it available within Cucumber's test context? Dropwizard provides easy support for unit testing with jUnit, and fortunately Cucumber-JVM works with jUnit as well. Add a DropwizardAppRule with an @ClassRule annotation to your test runner class like so:

package your.dropwizard.app; import cucumber.api.junit.Cucumber; import io.dropwizard.testing.junit.DropwizardAppRule; import org.junit.ClassRule; import org.junit.runner.RunWith; @RunWith(Cucumber.class) public class RunCukesTest { @ClassRule public static final DropwizardAppRule RULE = new DropwizardAppRule(YourApplication.class, "path/to/config/file"); }

Run the test, and you'll see your Dropwizard app starting up before your feature steps execute. It will then shut down automatically after the tests are finished. Here's a good tutorial if you need help getting your step definitions wired up to your feature tests.

So far, so good. But there's a drawback to this solution. One of the key benefits of DropwizardAppRule is that it conveniently brings your application's configuration and environment into test scope via the RULE object. However, because Cucumber test steps are defined in a separate class, we aren't able to refer to RULE where we need it.

The workaround our team settled on was to write a DropwizardHolder class exposing getters and setters for the application properties we needed in our step definitions. A basic implementation might look something like this:

package your.dropwizard.app; import io.dropwizard.testing.junit.DropwizardAppRule; public class DropwizardHolder { private static DropwizardAppRule rule; public static void setRule(DropwizardAppRule rule) { DropwizardHolder.rule = rule; } public static DropwizardAppRule getRule() { return rule; } }

Now add a @BeforeClassmethod to your test runner class to set the rule:

package your.dropwizard.app; import ... import static your.dropwizard.app.DropwizardHolder.setRule; @RunWith(Cucumber.class) public class RunCukesTest { @ClassRule public static final DropwizardAppRule RULE = ... @BeforeClass public static void buildDropwizardHolder() { setRule(RULE); } }

Now you can import the DropwizardHolder in your step definitions class, and access any of the properties exposed by the rule object.

With this framework in place, you can write new integration tests just as fast as you can implement new features.

Happy testing!

Amasa Amos is a Quality Assurance Engineer at Intent Media, where he builds tools to drive cross-platform integration testing. When not breaking things, he enjoys board games, hiking, and ashtanga yoga. You can sometimes find him on Twitter or on Github.

[intentmediaengineering]

Upgrading Dropwizard 0.6 to 0.7

At Intent Media we started using Dropwizard last year when creating an external API. Dropwizard is a great lightweight Java framework (they really exist!) for building RESTful web services, tying together Jetty, Jersey, Jackson, JDBI and a powerful metrics library.   

Everything was working great with the API in production until a few months ago, when we needed to run our application on both http and https to process SSL requests. Unfortunately, with Dropwizard 0.6 this wasn't possible so we decided to upgrade to the next version, 0.7. Dropwizard 0.7 isn’t a drop-in replacement for 0.6 and we couldn’t find a decent resource online, so we decided to write this guide based on our upgrade experience.

The changes we had to make to upgrade to 0.7 were the result of two changes to Dropwizard.  First, the resources moved to new packages.  Second, core Dropwizard objects were renamed.  Third, the way that the application is configured through code has changed.  

Structural Changes 

Class packages have all changed

Our previous ivy.xml file was quite sparse, but in 0.7 there are more distinct dependences.  More importantly, the package names changed from com.yammer.dropwizard and com.codahale.metrics to io.dropwizard and io.dropwizard.metrics

0.6 <dependency org="com.yammer.dropwizard" name="dropwizard-client" rev="0.6.2"/> <dependency org="com.yammer.dropwizard" name="dropwizard-core" rev="0.6.2"/> <dependency org="com.codahale.metrics" name="metrics-core" rev="3.0.1"/> <dependency org="com.codahale.metrics" name="metrics-jvm" rev="3.0.1"/> <dependency org="com.codahale.metrics" name="metrics-jersey" rev="3.0.1"/> <dependency org="com.yammer.dropwizard" name="dropwizard-jdbi" rev="0.6.2"/> <dependency org="com.yammer.dropwizard" name="dropwizard-testing" rev="0.6.2"/>

0.7 <dependency org="io.dropwizard" name="dropwizard-client" rev="0.7.1"/> <dependency org="io.dropwizard" name="dropwizard-core" rev="0.7.1"/> <dependency org="io.dropwizard" name="dropwizard-configuration" rev="0.7.1"/> <dependency org="io.dropwizard" name="dropwizard-jersey" rev="0.7.1"/> <dependency org="io.dropwizard" name="dropwizard-jetty" rev="0.7.1"/> <dependency org="io.dropwizard" name="dropwizard-jackson" rev="0.7.1"/> <dependency org="io.dropwizard" name="dropwizard-validation" rev="0.7.1"/> <dependency org="io.dropwizard" name="dropwizard-util" rev="0.7.1"/> <dependency org="io.dropwizard.metrics" name="metrics-core" rev="3.1.0"/> <dependency org="io.dropwizard.metrics" name="metrics-jvm" rev="3.1.0"/> <dependency org="io.dropwizard.metrics" name="metrics-jersey" rev="3.1.0"/> <dependency org="io.dropwizard" name="dropwizard-jdbi" rev="0.7.1"/> <dependency org="io.dropwizard" name="dropwizard-testing" rev="0.7.1"/>

Services are now applications

What was previously referred to as a service is now an application

0.6: public class ApiService extends Service<ApiServiceConfiguration>{} 0.7: public class ApiApplication extends Application<ApiApplicationConfiguration>{}

New configuration file structure

Previously, the configuration had http as a top level configuration item, but now it’s handled under server with the applicationConnectors: configuration. Additionally, logging changed such that the appenders are separate and not limited to console and file logging.

0.6 http: port: 8281 adminPort: 8282 requestLog: console: enabled: false file: enabled: true currentLogFilename: ./log/requests.log archivedLogFilenamePattern: ./log/requests.%d.log.gz logging: level: INFO loggers: "com.intentmedia": DEBUG console: enabled: true file: enabled: true logFormat: "[%d{yyyy-MM-dd HH:mm:ss.SSS}] [%thread] %msg%n%throwable" currentLogFilename: ./log/api.log archivedLogFilenamePattern: ./log/api.%d.log.gz archivedFileCount: 50

server: applicationConnectors: - type: http port: 8281 requestLog: appenders: - type: file currentLogFilename: ./log/requests.log archivedLogFilenamePattern: ./log/requests.%d.log.gz archivedFileCount: 50 logging: level: INFO loggers: "com.intentmedia": DEBUG appenders: - type: file logFormat: "[%d{yyyy-MM-dd HH:mm:ss.SSS}] [%thread] %msg%n%throwable" currentLogFilename: ./log/api.log archivedLogFilenamePattern: ./log/api.%d.log.gz - type: console threshold: ALL target: stdout logFormat: "[%d{yyyy-MM-dd HH:mm:ss.SSS}] [%thread] %msg%n%throwable"

Code wise, after resolving the new package paths, the main change was in our ApiApplication where the application is setup. Before, resources and health checks were added directly to the environment.   Now, they’re handled by Jersey and the HealthCheckRegistry.  These changes are in the ApiApplication.run() method:

0.6 environment.addProvider(new InstrumentedResourceMethodDispatchAdapter(metricRegistryFactory.create("ResourceStatistics", configuration.getMetrics().getInterval()))); environment.addResource(new UserResource(configuration, httpClient)); environment.addHealthCheck(new HealthyHealthCheck());

0.7 environment.jersey().register(new InstrumentedResourceMethodDispatchAdapter(metricRegistryFactory.create("ResourceStatistics", configuration.getMetrics().getInterval()))); environment.jersey().register(new UserResource(configuration, httpClient)); environment.healthChecks().register("healthy", new TemplateHealthCheck());

Gotchas 

As with any large version change there were also a number of gotchas that took us some time to resolve:

‘metrics’ is now a reserved configuration word. If you have a top level configuration value of ‘metrics’, you’ll need to change it.

HttpClientBuilder has new requirements: environment and user agent (the argument to .build()) are required.

jdbi isn’t as tolerant of repeated connection opening and closing. In an integration junit test, we previously ran jdbi.open() in the @Before method and jdbi.close() in the @After method.  In 0.7 this caused the dreaded “too many open connections” error after enough unit tests ran. The solution is to use jdbi.onDemand(Dao.class).  Additionally, if you are doing any jdbi.execute() calls, an easy way to do this is:

jdbi.withHandle(new HandleCallback() { @Override public Void withHandle(Handle handle) throws Exception { List tableNames = testDataFixture.findAllTables(); for (String tableName : tableNames) { handle.execute(String.format("TRUNCATE TABLE %s", tableName)); } return null; } });

Bonus

SSL with Dropwizard

This whole upgrade process was required so that we could run http and https at the same time, so I would feel bad leaving out the details on how to run Dropwizard with https. Instructions on how to generate a keystore can be found here, with the important command being

keytool -genkey -alias mydomain -keyalg RSA -keystore keystore.jks -keysize 2048

Here is the relevant section of the configuration file for SSL:

server: applicationConnectors: - type: http port: 8281 - type: https port: 8284 keyStorePath: ./bin/api.keystore keyStorePassword: <password> certAlias: api validateCerts: false adminConnectors: - type: http port: 8282

Wrap Up

At Intent Media we love using Dropwizard and are enjoying the benefits of having upgraded to 0.7.  Upgrading to 0.7 will make future upgrades to 0.8 and beyond easier and will allow us to continue enjoying the ability to rapidly create great REST-ful web services.  Keep up to date on Dropwizard developments at the discussion forum on Google groups, and if you find this all interesting come work with us, and help us write more awesome code.

Tom Allen is a Software Engineer at Intent Media, where he writes a lot of Java and some Ruby.  When not upgrading frameworks he can be found running, cooking and learning to dive.  Infrequently attended to online presences include Twitter and Github.

[intentmediaengineering]

The Purginator: Dynamically throttled writes to DynamoDB

https://github.com/intentmedia/purginator

The purginator was designed to enable dynamically throttled write operations against a local or remote DynamoDB database. It also has the ability to generate test data in a local database to validate the correctness of a planned operation.

Our initial use case was to purge several hundred thousand records from a database that was in production use, without exceeding the provisioned write capacity. DynamoDB can be an incredible tool, and we have found some great uses for it. Ensuring that your DynamoDB usage doesn’t exceed your provisioned capacity can be a challenge, especially when multiple applications share the same database. In this case, the operation to purge the records needed to not impact normal application activity, since we didn’t want our production application’s database access to be throttled or interrupted.

The purginator was developed in Clojure, using open source libraries including Faraday and Commons Math. Today, we’re open sourcing it, and we welcome comments, questions, bug reports, and pull requests.

John Chapin is a Data Engineer at Intent Media, where he is building the next generation of predictive analysis tools alongside a world-class team. When he’s not hacking on a functional programming project, he can be found running along the Hudson River or planning his next trip abroad. John has a bachelor’s degree in computer science from James Madison University.

[intentmediaengineering]

Modeling Madly: Machine learning at hackathons

I recently wrapped up another hackathon here at Intent Media. You can see my summary of one of our previous hackathons here. These past two hackathons I’ve taken on some slightly different challenges than people usually go after in a hackathon: developing new machine learning (ML) models.

I‘ve been working on data science and machine learning systems for a while, but I’ve found that doing so under extreme constraints can be a distinctly different experience. A good data hacker can easily find themselves with a great idea at a hackathon but with little to nothing to demo at the end. Accepting that my personal experience is just my own, let me offer three tips for building new models at a hackathon.

Time is not on your side.

At a hackathon you can almost run out of time and still come up with something pretty good as long as you get that last bug fixed before the demo when you’re building something like a web app. This characteristic of hack day is great to build into the plan for your web app hack, but it does not apply to a machine learning hack.

Think about what happens when you do find that last bug in a machine learning project. You might still need to:

Reprocess your raw data.

Regenerate your signals.

Retrain your model.

Evaluate your new model on sample data.

Calculate performance statistics.

Draw your conclusions.

You can’t just hit refresh. Even with a well-oiled workflow, some of those tasks can take all of the time scheduled in your average one-day hackathon. Take #3 for example. Training a production grade model using, say, Hadoop, can take a lot of time, even if you have the cash to spin up a fair-sized cluster of EC2 instances.

What that means for your hack can vary, but you’re just asking for trouble if you don’t start with latency considerations taken into account in the scope and goals of your project. A solid project design is crucial if you’re going to hope to take all of the little steps involved in getting your model ready to demo.

Which leads me to my next point…

Bite off less than you can chew.

One of the best things about working in data science is all of the really smart people. But, of course, the corollary is that one of the worst things about working in data science is all of the really smart people. Sharp engineers and data scientists can take the nugget of an idea and envision a useful, powerful suite of products that would take years to build. This obviously is not so useful when you only have a day or two.

Mature dataists know just how much ambition is too much and plan accordingly. I happen to be lucky enough to work with some very smart and very mature data scientists and engineers, so this has not been a problem for either of my last few hacks. But, I’m just lucky that way. You might not be so lucky.

Unrealistic ambitions are a constant danger in a machine learning hack. These ambitions run along the edge of all activities like a precipice beckoning you to dive off and see where you land. If you take one thing away from this post, let it be this: don’t dive off the cliff. Just don’t do it. You won’t like where you land. You’ll wind up with more questions than answers and you’ll have nothing to show come demo time. Moreover, your fellow developers who worked on apps and not ML models will simply not understand what you spent your time on.

What does a precipice look like? It could be a novel distance metric. It could be a fundamental improvement to a widely used technique like support vector regression (SVR). Or it could just be something really benign sounding like a longer training set. I would say that even choosing to pose the problem as a regression one instead of a classification one could qualify.  Having something like a confusion matrix instead of mean squared error (MSE) as your guide could give you a lot of focus for some quick iterations on your model. That’s true even if your problem feels might be better posed as a regression problem…given more time.

The danger of ambition originates in the intrinsic tension between the rigorous and exploratory mode of academic data science/machine learning education and the pedal-to-the-metal pace mandated by a hackathon. They are different modes of working, and you will have to  suspend some of your good habits for a day or so, if you want to have something to demo.

Use lightweight tools.

This last point can be the trickiest to put in practice, but I think it can totally be the difference between a project that feels like a hack and one that feels like just getting warmed up on a weeklong story. If you’ve figured out how to scope your project appropriately and designed something that you can build in a day or two, you can still actually fail to build it. I think it can the difference can easily come down to technology choices.

For example, I currently work mostly in Cascalog, Clojure, and Java on top of Hadoop to process files stored in S3. I know these tools well enough to pay my rent, but I would definitely think carefully about trying to use any of them in a tight-paced context. I have spent weeks trying to understand a single Cascalog bug. Seriously.  

Much of this is down to the inherent difficulty of MapReduce and distributed systems, but it’s dangerously hairy territory any way you look at it.  Clojure could be an incredibly good prototyping tool in this context, but the difficulty is going to stem a lot from the available libraries.  With a young JVM language, it’s pretty common to find yourself reaching for a library that only exists in Java. This forces you to get into interop, which is a tricky enough topic on its own.  

As for using Java, I think it’s a reasonable choice, but much of what Java and its ecosystem are trying to do for you with things like static type, class hierarchies, etc. is focused on building software that can last.  Remember, you’ll probably trash your result in mere hours.

If you know the language, Python offers an unbeatable value proposition for this use case. scikit-learn has nearly everything you could imagine needing. pandas, NumPy, and SciPy are all sitting there to be brought in when appropriate. And don’t forget how awesome it can be to prototype in a purpose-built exploratory development environment like IPython.

But this is machine learning, and sometimes our data is just big. Maybe even web scale. Some people hate these phrases, but they serve a purpose. We don’t all use Hadoop out of a love for complex Java applications.

Data Science is statistics on a Mac.

— Big Data Borat (@BigDataBorat)

August 27, 2013

@BigDataBorat is big data stats on a Mac Pro?

— Duncan Foster (@GoneCaving)

January 3, 2014

Big data is not just statistics on a Mac Pro, although it can often look like that. Scale can be a real necessity even in a hackathon.

When it is, there are no easy answers. If you’re lucky, maybe you can actually work with multiple hour model learning times. If you’re really lucky, you might be using Spark and not Hadoop, in which case it might not take hours to learn your model.

My point is that, insofar as you have a choice, choose the leaner, meaner tool, the one that will let you do more with less input required from you. Don’t use that C++ library that promises awesome runtime but with Python bindings that you’ve never tried. You’ll never figure out its quirks in time. Write as little data cleanup code as you can manage. Commands like dropna can save you precious minutes to hours.

And if you can get your data from a database or an API instead of files, then, for the love of Cthulhu, do it. Hell, even if you have to load your data from files to a database first, it might be worth your time. SQL is one of the highest-productivity rapid-prototyping tools I know.

And while Hadoop is tough to use as a rapid prototyping tool, there are even ways of making that elephant run a bit faster. Depending on what you’re doing Elastic Map Reduce or PredictionIO can get you to the point of being productive much faster.

I could have danced all night.

I love hackathons and their variations. They remind me of the fun old days in grad school, furiously hacking away to come up with something interesting to say about definitionally uncertain stuff.

The furious pace and the pragmatic compromises are part of the fun. Compared to things like pitch events, hackathons have way less problems (even if they have their issues as well). At their best they’re about the love of unconstrained creation. I’ve tried to do machine learning hacks because it’s just so damn cool to go from zero to having a program that makes decisions. It amazes me every time it works, and doubly so when I can manage to get something working on a deadline.

Taking on a challenge like building a new model in a hackathon is also a great learning experience, especially if you get to work as part of a strong team. Machine learning in the real world is an even larger topic than its academic cousin, and there’s always interesting things to learn. Hackathons can be great places to rapidly iterate through approaches and learn from your teammates how to build things better and faster. That’s pretty likely to come in handy sometime.

Jeff Smith is a data engineer at Intent Media working on large scale machine learning systems.  He has a background in AI and bioinformatics.  Intent Media is the fifth startup he’s worked at, and it’s easily the most fun one.  Jeff has a master’s degree in computer science from the University Hong Kong.  You can find him on Twitter, Medium, and his own blog.

[intentmediaengineering]

Acceptance Testing Data Collection: Asserting On Outbound Resource Requests Using CasperJS and PhantomJS

At Intent Media, we run ad networks, which means that on the data science team, we don't just science data, we also collect it.

One way in which we accomplish this collection is through the use of beacons on our partners' sites. And because we are nearly as excited about software testing as we are about statistical modeling and Hadoop-ing, we also want to do proper acceptance testing of our beacons.

Acceptance testing for us means that we need a way to assert that a browser, upon executing our javascript, will make a request to our beacon url. It turns out that our pal PhantomJS has a handy method for handling this kind of thing, and our favorite PhantomJS wrapper CasperJS emits an event on resource requests to help us out.

Setting Up An Event Listener For Resource Requests

Armed with these tools, we can set up a listener on the 'resource.requested' event and do something useful when it happens:

casper.onResourceRequestFor = function(requestRegexp, callback) { var resourceListener = function(request) { if (request.url.match(requestRegexp)) { callback(); } }; this.on('resource.requested', resourceListener); };

Now we can require our little library in our test, which we'll write in CoffeeScript:

require('./casper.intentmedia.js')

And we can make some assertions about requested resources:

test_page = 'http://localhost/test_page.html' beacon_url = /http:\/\/localhost\/beacon\.html.*/ casper.test.begin "Page fires a beacon request", 1, (test) -> casper.start 'http://localhost', -> casper.open test_page casper.then -> casper.onResourceRequestFor beacon_url, -> test.assert(true, 'Matching request made') casper.run -> test.done()

Note that because we rely here on CasperJS's tester module, we must invoke our test using the test subcommand: casperjs test beacon_test.coffee.

Fixing a Race Condition

That test is almost useful, but if you're following along carefully you'll have noticed a problem. This test is flaky -- like croissant flaky.

The open method waits for the page load to finish, so we won't call the next navigation step on the stack (provided as a callback to then()) until after page load has finished.

Thus, when we make the assertion above, the browser may or may not have already executed the javascript that makes our beacon request.

We really need to set up our listener before the navigation step causing the event to fire.

casper.assertResourceRequestAfterStep = function(urlRegexp, step) { this.onResourceRequestFor(urlRegexp) { this.test.assert(true, 'matching request made'); } step(); };

And then we reflect this change in our test script:

casper.assertResourceRequestAfterStep beacon_url, -> casper.open test_page

Building Out Our Custom Assertion

Relying on a step timeout to fail this test means that we aren't providing super-useful feedback upon test failure. We'll add an explicit wait (using waitFor, documented here), and we'll add better failure and success messages.

casper.assertResourceRequestAfterStep = function(urlRegexp, step) { var testStatus = 'fail'; var passTest = function() { casper.test.assert(true, "Request made for #{urlRegexp}."); }; var failTest = function() { casper.test.assert(false, "No request made for #{urlRegexp}."); }; this.onResourceRequestFor(urlRegexp) { test_status = 'pass'; } step(); this.waitFor(function() { return testStatus == 'pass' }, passTest, failTest); };

Running our test now produces more helpful logging:

Test file: beacon_test.coffee # Page fires a beacon request PASS Request made for /http:\/\/localhost\/beacon\.html.*/ PASS 1 test executed in 0.225s, 1 passed, 0 failed, 0 dubious, 0 skipped.

Tidy Up: Removing Event Listeners

We need to do one other bit of housekeeping. If we don't explicitly remove the event listener we set up, it will persist through the suite. That might cause the suite to behave unpredictably, which in turn might cause us to owe our colleagues beers.

In this case, we're happy to remove the listener once we have seen a matching request:

casper.onResourceRequestFor = function(requestRegexp, callback) { var removeResourceListener = function () { casper.removeListener('resource.requested', resourceListener); }; var resourceListener = function(request) { if (request.url.match(requestRegexp)) { removeResourceListener(); callback(); } }; this.on('resource.requested', resourceListener); };

Wrapping Up

Here's what our custom assertion library looks like now:

casper.onResourceRequestFor = function(requestRegexp, callback) { var removeResourceListener = function () { casper.removeListener('resource.requested', resourceListener); }; var resourceListener = function(request) { if (request.url.match(requestRegexp)) { removeResourceListener(); callback(); } }; this.on('resource.requested', resourceListener); }; casper.assertResourceRequestAfterStep = function(urlRegexp, step) { var testStatus = 'fail'; var passTest = function() { casper.test.assert(true, "Request made for " + urlRegexp); }; var failTest = function() { casper.test.assert(false, "No request made for " + urlRegexp); }; this.onResourceRequestFor(urlRegexp, function() { testStatus = 'pass'; }); step(); casper.waitFor(function() { return testStatus == 'pass'; }, passTest, failTest); };

And our test script:

require('./casper.intentmedia.js') test_page = 'http://localhost/test_page.html' beacon_url = /http:\/\/localhost\/beacon\.html.*/ casper.test.begin "Page fires a beacon request", 1, (test) -> casper.start 'http://localhost', -> casper.assertResourceRequestAfterStep beacon_url, -> casper.open test_page casper.run -> test.done()

Now that's a flake-free and readable acceptance test.

PhantomJS here provides the ability to inspect the outgoing requests that represent the basic acceptance criterion for our beacon tag. And CasperJS’s event system makes the asynchronous nature of these requests manageable.

Anybody out there with a more elegant solution? Other handy uses for CasperJS? If so let us know, or better yet come work here!

Wesley Harris tests software with the data science team at Intent Media. He codes as @whharris and tweets (rarely) as @whharris. You can find him IRL rolling four deep (+ spouse, dog, baby) through the wilds of Prospect Park in beautiful Brooklyn, New York.

[intentmediaengineering]

Cross Browser User Bridging with DynamoDB

Rationale & Background

As the web evolves, user identification has become key when it comes to research, privacy, product customization and engineering. Companies are always balancing the need to respect users’ data collection wishes with the product and economic benefits of providing a customized user experience. The days of relying on third party cookies are gone. Web companies continue to need more effective, trustworthy ways of identifying visitors as previously seen customers or households.

Anonymous user shopping patterns form the core of our ecommerce predictive decisioning platform. We have several classification and regression models that predict the probability of conversion and expected purchase price. We also model a visitor’s expected CTR (Click Through Rate) to perform customized ad selection. To accomplish all this, site page visit history is saved in a “user profile” which represents the best view we have of a site visitor.

When we see a new user, we generate a new UUID and store that in a first party cookie on a partner’s site. That becomes a partner-specific identifier for a that user’s browser.

While first-party visitor cookies are more effective than typical third-party advertising cookies at maintaining a persistent ID for a user, they suffer from a number of drawbacks.

Users still tend to delete their cookies from time to time.

Users buy new computers, discarding machines with the old visitor cookies.

Users switch browsers. If a visitor searches on Chrome and moves to Safari, they get a new visitor cookie and appear like a new user.

Users switch among multiple desktop and mobile devices. A visit from each device generates its own visitor ID cookie.

When you delete cookies, switch browsers or devices, a new visit looks like it is from a previously unseen visitor. This creates low-quality data and degrades the quality of our predictive models.

There are a number of sophisticated methods for probabilistic user identification from a variety of vendors that have built businesses around this difficult problem. In the interest of delivering a backwards-compatible system that could improve our performance in the presence of these issues, we decided to build a way to identify site visitors by their anonymous member ID in addition to the cookie-based visitor ID. This is a unique string that has a one-to-one mapping with usernames, but contains absolutely no personal information. The member ID provides limited coverage since only a small percentage of visitors log in while browsing on e-commerce sites.  It still is effective given people tend to have just a single account across devices. This information retrieves and appends otherwise lost user history to a new visitor ID.

Current Architecture

From an engineering perspective, we use a lot of Amazon Web Services (AWS) for our infrastructure ranging from EC2 for servers to S3 for long-term data storage. We use Amazon DynamoDB for storing user profiles for its simplicity and speed.

DynamoDB is a key/value store. While the actual specification is more complex, it takes a String for a key, which maps to an object that has a value with any number of attributes of various types, like Integers and Strings. For our key we use a GUID stored in a first-party cookie, that is, in the domain of the publisher sites that use our products.

We serve ads within 200 milliseconds. That is enough time for processing, but we cannot waste milliseconds. On an ad call, we send a request to DynamoDB and receive a record with the user’s history, which we use in our decisioning model. After the ad request, we put an update request on a queue for backend processing that then updates Dynamo with any new events we collected from the user.

Implementation

If our data were small enough to fit in a traditional relational database, this would not be a difficult solution. We would only need to add a new index on a second column for whichever field we wanted to look up on, and then modify our request to look at both attributes with an OR in the where clause.

In the world of distributed key value stores, this is a bit trickier to implement without degrading performance. Records can only be retrieved by key. We could make secondary queries based on the results of previous queries pulled back. This however requires a sequence of requests to the database which adds significant time to process each ad request.

Options Considered

Local Secondary Indices

DynamoDB supports local secondary indices. We considered these, but found that in general they are for downsizing a multiple-row result set towards an intended record rather than expanding the result set from a single record into a larger view of a user’s history.

Global Secondary Indices (GSIs)

As we were developing, Dynamo released a feature called Global Secondary Indices. This allows multiple fields to serve as hashes for a record. GSIs may have been effective for a single additional field, but it is difficult to arbitrarily define new lookup fields and query them all in a single request. From the start we wanted the flexibility to expand to add new indices quickly. An example would be to extend this bridging across our third-party visitor ID and other future identifiers. GSIs must be defined at table creation and added to existing tables by completely rehashing. Since they did not lend themselves to our iterative development process, we looked to other options.

Solution

The solution was to develop a second table, which we call our lookups table, in addition to our main profiles table.

Lookups Table

Alternate ID (String, Hash Key) | ID Type (Enum) | Mapped Visitor ID (String)

Profiles Table 

Visitor ID (String, Hash Key) | Alternate ID 1 | Alternate ID 2 | Other profile data

When we first see a visitor with an alternate ID, such as a member ID, we write a lookup record with a reverse index, thus mapping the member ID to the visitor ID. Now suppose that user opens a new browser. As soon as they log in, we pull the new profile for the new visitor ID, and we realize we have an existing profile mapped under an old visitor ID through the member ID. We can then pull down that old profile and merge in the historical data to populate the new one. The lookup record is then rewritten to map to the new, merged profile record.

Thus, the lookups table contains a mapping of alternate IDs to the visitor ID of the last browser seen so far of a given individual. Each profile record contains the best knowledge available for a given individual from the last time we have seen that browser. The resting state of the system at any point trades off some duplication of data for query-optimized profiles for a visit from any browser.

Sample Flow

+----------------------+-----------+----------------------+ | User Actions | Lookups | Profiles | +----------------------+-----------+----------------------+ | User Visits Site |[empty] | abc-> {1 page} | | Gets Cookie “abc” | | | +----------------------+-----------+----------------------+ | User Logs In | 123-> abc | abc-> {2 pages} | +----------------------+-----------+----------------------+ | User Purchases | 123-> abc | abc-> {2 pages, 1 $} | +----------------------+-----------+----------------------+ | User Switches Devices| 123-> abc | abc-> {2 pages, 1 $} | | Gets cookie "def" | | def-> {1 pages} | +----------------------+-----------+----------------------+ | User logs in | 123-> def | abc-> {2 pages, 1 $} | | | | def-> {4 pages, 1 $} | +----------------------+-----------+----------------------+ 

Key Benefits

The performance hit for a secondary lookup is only taken once, on the first request where we see an alternate ID. Subsequent lookups are a guaranteed hit on the primary store. Once we realize we have an existing historical profile for a user, we pull all that data and merge it into the newest profile.

This scales to support an arbitrary number of alternate ID types. Since DynamoDB supports batch requests, we do a batch request for all the alternate IDs, gather the unique visitor IDs that this retrieves, and then do a batch request for the historical profiles of the returned visitor IDs. This limits us to a maximum of two sequential requests, slashing latency.

Merging is nondestructive. We retain the profiles mapped from the old visitor ID, so if the user alternates between devices multiple times, we can retrieve accurate data quickly.

We can track how many devices we have merged together for a given user, and feed that as a signal into our model. Do users who use multiple browsers, tablets, and smartphones shop differently than users who only shop from their desktop? Our model knows.

Conclusion

We have demonstrated how with simple tools we have built a sophisticated cross-browser user profile. Intent Media’s data team does a lot of work to optimize ad performance for publishers and advertisers as well as the overall experience for users. User profile histories are one of many tools we use. This is just one small enhancement we’ve added to our platform as we continue to iterate and innovate.

  Chet Mancini is a Data Engineer at Intent Media, Inc, where he works on the data science team to store and process terabytes of web travel data to build predictive models of shopper behavior. He enjoys functional programming, downhill skiing, and cycling to coffee shops around Brooklyn. Chet has a master’s degree in computer science from Cornell University.

Twitter: @chetmancini

Github: @chetmancini

[intentmediaengineering]

Clojure NYC: Vert.x Intro

Vert.x is a lightweight, high performance application platform for the JVM. It enables polyglot modules to communicate asynchronously across a shared event bus in a distributed environment. In this talk at the Clojure NYC Meetup, John Chapin gives an overview of Vert.x concepts, practical usage, and Clojure support. He also presents a live demonstration of several key Vert.x concepts in the context of an example client/server chat application.

The slides for the presentation can be found here and the code can be found here.

John Chapin is a Data Engineer at Intent Media, where he is building the next generation of predictive analysis tools alongside a world-class team. When he’s not hacking on a functional programming project, he can be found running along the Hudson River or planning his next trip abroad. John has a bachelor’s degree in computer science from James Madison University.

[intentmediaengineering]

Summer @ Intent Media

I am a graduate student at Columbia University studying Operations Research (OR). I came to Intent Media (IM) as a data scientist intern this summer with excitement as well as a bit of nervousness. I have great interest in data science, and I wanted to see what it would be like to work in the area, however I was anxious about whether I would be able to contribute well. Also, I had never worked at a startup before, so I was unsure as to what lay ahead of me. Plus, I am a little scared of dogs, so it did not help that I saw Ben as soon as I walked in to the office.

  I was given a Macintosh laptop, something I had never used before (I mean c’mon, Apple is a fruit!), and was asked to set up everything myself. It is with a bit of abashedness that I admit that I have never been good at figuring out where wires must go. Yes, I have an engineering background, but I only learned how to efficiently fix bugs I created myself, when I was a software engineer. Also, the enormous amount of technical jargon that was flying around got me very worried. However, I am pleased to say, paraphrasing Linkin Park who informed us at 1000 decibels and 600 words per minute, in the end, it didn’t matter.

I had a great summer at IM. My favourite part of IM were the buttered muffins that were always available. Second to that, I liked that IM has retained its startup flavour despite being reasonably well-sized. The processes are lean and the environment, in general, is very vibrant. Having said that, IM also has the steadiness of a well-established company. A very organized tech stack and strong technical infrastructure are its strengths. There is a very open culture that allows people to express themselves and also be heard. It is really inspiring to meet and work with people who are very passionate about what they build together.

During my internship, I worked on the problem of budget smoothing for active advertisers in the online travel space. Let me give you a bit of context before I tell you more about the problem. The web has become a major market for advertisements. Online advertisements drive the revenue of big search giants such as Google, Yahoo, Bing etc. For every word/query that is looked up on a search engine, a finite set of advertisements are displayed. Where do these ads come from? There are a set of advertisers who wish to advertise their products. They begin by registering their products and providing their assessment about what categories each product belongs to. In this model, the people who display these advertisements are called publishers. Advertisers hope that publishers will display their ads whenever the publishers display content in the categories that the advertisers believes are relevant to their ads. Also, there are auctioneers who act as intermediaries in connecting advertisers and publishers for queries. Advertisers bid a price they are willing to pay when a web user clicks on their advertisement. Here is video by Google’s chief economist that explains auction pricing if you’re keen to find out more.

Each advertiser runs several campaigns in order to maximize their presence on the web. Each campaign constitutes a set of queries that the advertiser wants to bid on. All advertisers set a budget cap on the amount of money they want to spend on each campaign. Some advertisers can afford to spend a lot of money on online marketing, therefore, they sustain their online presence throughout the day. There are few other advertisers who have limited budgets and tend to exhaust their budget before the end of day. The natural question that arises here is - how can they spend their budget wisely throughout the day?

To put you out of the stage 4 sleep I just put you in, let me state this problem in simpler terms. If you had $100 to spend in a day, and you kept getting limited time (say < 5 min) offers, how would you know which offers to spend it on? One way to do this would be to keep spending on all the available opportunity until you exhaust your budget. In algorithmic parlance, we call this a ‘greedy’ approach and greedy approaches are seldom optimal. Clearly, why not wait until a better opportunity comes along. However, if you waited too long, you might find that you lost the best opportunities from earlier in the day. How then do you solve this problem in a holistic and principled manner?

I worked under the ‘super’vision of Sharath Rao, a Data Scientist at Intent Media. Based on the problem statement, few of the questions that I started with were:

What is the best strategy to spend budgets?

Is a greedy approach optimal?

Spend in proportion to traffic/size of opportunity or in proportion to campaign performance?

Is there a way to smooth the budget to ensure participation in auctions throughout the day?

Is it possible to solve this problem in a dynamic environment with game theoretic constraints? If yes, is it practically feasible?

Something may maximize auctioneer revenue but would that be fair to advertisers?

I began by reading a few research papers about this topic. A lot of research in this field has been undertaken by software giants, and other DSP/Real Time Bid (RTB) platforms. A few papers that I explored as part of my research were by Google, Microsoft, Turn, Yahoo. My job involved understanding the models presented in the paper. I had to devise ad-hoc experiments to test the feasibility of such approaches. Specifically, the questions that I attempted to answer during my internship were:

Do these models work well in our context?

How efficient is this model? Does it scale well?

Do we need to make any changes to the model?

What will IM have to do to be able to provide the necessary data for a model like this? Specifically, what kind of data collection infrastructure is required for this?

Would the model actually help budget constrained advertisers? Clearly there is a conflict of interest between the advertisers and the auctioneers (discussed well in the Yahoo paper) that needs to handled.

Is there a best strategy that would benefit everyone?

On the whole, my internship was a very fulfilling experience. I got a lot of exposure to work that involves big data and predictive modelling. I came here with a genuine curiosity and an eagerness to learn how the industry employs principled mathematical analysis to drive business growth in dynamic environments such as the internet. I take back to school a lot of insights and learning from this experience. To me, the phrase “mathematical methods in decision making” perfectly sums up the field of Operations Research (OR). While the description is quite broad, it draws our attention to an important fact that, as opposed to qualitative analysis, OR deals with quantitative methods that are used in business and policy decisions. Data science/analysis, of the kind that I did at IM, clearly falls under this definition. It was apparent to me that concepts such as parameter and density estimation, linear and quadratic optimization, stochastic modeling and Bayes' theorem have found applicability in the real world only because of the vastness of data available to us and that data is a very potent resource for any kind of decision making. I also enjoyed being able to place academic knowledge in context. There is a very specific process with regard to how academic research permeates engineering practice. I was very lucky to have witnessed this.

I would like to take this opportunity to encourage everyone out there (YES! EVERYONE!) to be bold and pursue whatever interests you the most. Life is too short to spend on things that allow you to afford seat warmers in your car, but actually don’t interest you. At graduate school, I have noticed that many of my female peers, who want to pursue careers in technology, are intimidated to dive into fields with gender imbalance. Gender imbalance won’t be righted until women stop believing that they can’t. There are only too many women who are extraordinarily accomplished professionals in highly technical fields. Case in point, my co-worker  Betsy transitioned from ‘Business Analyst’ to ‘QA engineer’ and is now heading to dev boot camp and coming back as a software developer!

I am continuing to work at IM over the Fall exploring data analytics and learning lots more. Also, my fear for dogs has reduced greatly. I can now pet Ben without flinching :)

If you enjoyed my post, you know what to do - Come work for Intent Media

  I am a graduate student at Columbia University studying Operations Research. I worked as a software engineer at Oracle before I began my soul searching sojourn! I dabbled in a lot of things before I fell in love with data science. I interned at Intent Media over the summer of ‘14  and and am continuing to intern during fall of 2014. You can connect with me on Linkedin.

[intentmediaengineering]

Random Assumptions will make an A-- Part 2

Overview

In our previous post, Random Assumptions can make an A— Part 1, we discussed a solution that we built to build sticky random numbers. In this blogpost we’ll examined in detail the bug that we introduced, and our efforts and final solution to the problem.

The Initial (not so good) solution

We wanted to generate several sticky random numbers for a user based off a user_id for our multivariate tests. We used a combination of the user_id, the multivariate test attribute id, and some salt to generate a seed for the Random generator. Our solution looked something like this:

int seed = String.format("%s some salt", userId).hashCode(); double diceRoll = Random(seed).nextDouble();

Having implemented this we patted ourselves on the back and went for a beer.

A few weeks later we found out that our solution was buggy. During an analysis of some data, we found a high amount of covariance with our tests. What is covariance, you might ask? A formal definition is available at Wikipedia of course, but we can demonstrate the problem using our original example.

We have a test with two designs Design Awesome and Design Sweet with a 50-50 split and with two ad copies “Look at me!” and “I am a sweet ad copy”. Given this test we would expect to see the follow distribution of users:

| Design | Ad Copy | Expected % of Users | ----------------------------------------------------------------- | Design Awesome | "Look at me!" | 25 | | Design Awesome | "I am a sweet ad copy" | 25 | | Design Sweet | "Look at me!" | 25 | | Design Sweet | "I am a sweet ad copy" | 25 |

We won’t get exactly 25% in each bucket but it should be reasonably within range. Well when we looked at the numbers we were way off:

| Design | Ad Copy | Expected % of Users | Actual % of Users | ----------------------------------------------------------------- | Awesome | "Look..." | 25 | 36 | | Awesome | "I am..." | 25 | 12 | | Sweet | "Look..." | 25 | 15 | | Sweet | "I am..." | 25 | 37 |

These numbers are way off. And when we looked at our tests with more attributes they were even more skewed. We obviously had a new problem.

Random Number Basics

Remember that the Random library provided by Java is actually a Pseudorandom Generator. It takes a seed number, and every successive call to it returns a “random” number. This number is actually generated by applying a math function to the seed and the number of successive calls. There is a lot of math involved but check out Wikipedia’s article Random Number Generation if you are interested in learning more

One of the most important features of Random is that it has a ‘normal’ distribution. A ‘normal’ distribution means that the dice rolls are close to evenly divided. For example, if you flipped a coin 100 times you would expect it to come up heads about 50 times (45 times would be perfectly acceptable). Similarly if you called `Random.nextInt(2)` 100 times you would expect it come up as `0` about 50 times. And it does.

So of course our use should have universal distribution, right…?

The Assumption

So yeah we were wrong, because we were using Random in an unexpected way. Random does have normal distribution for each successive call with a single seed number, but the numbers from seed to seed are NOT normal distribution. This may be a bit confusing to understand at first, so it’s helpful to visualize the problem.

Imagine all the random numbers generated by `Random` in one large table:

| Seed | first call | second call | third call | ... --------------------------------------------------- | 1 | 0.5889789 | 0.78998897 | 0.0029884 | ... | 2 | 0.5889788 | 0.78998898 | 0.0029885 | ... | 3 | 0.5889787 | 0.78998899 | 0.0029886 | ... | 4 | 0.5889786 | 0.78998900 | 0.0029887 | ...

(Note these values aren’t accurate; this is just for illustration purposes)

If you examine a row of values (left to right) you would find the number distribution to appear normal. However if you examine a column of values (top to bottom) you find that the numbers are obviously not normal.

This was our critical assumption that shot us in the foot. Because we were constantly switching the seed number we were using the column of values and not the row. Our seed numbers were also very close together, so it threw our normality right out the window, and caused the covariance that we were seeing.

The solution

Given all of the above, we decided to use our own random function for these purposes:

long attributeIdSha1 = Long.parseLong(DigestUtils.shaHex(attributeId.toString()).substring(0, END_INDEX), RADIX); double longValue = (double) ((Math.abs(randomizedUserIdHash ^ attributeIdSha1) % PARTITION_SIZE))/ PARTITION_SIZE;

Essentially we SHA1 the attribute id for each multivariate test attribute to get 4 bytes and then XOR with the randomizedUserIdHash that we previous assigned to get a new random number. Again its a pseudo random, but in our testing we saw enough of a distribution to feel confident in our solution.

We replayed a large set of ad calls against this new algorithm and found that the covariance disappeared. We had our solution.

Lessons learned

Random number generation is a hard problem. And while it’s great that all these libraries our out there to help us with this stuff, it’s really important to understand how these libraries work so your assumptions don’t catch you off guard.

Orion Delwaterman

[intentmediaengineering]

Machine Learning with Spark MLlib on Elastic MapReduce

Overview

At Intent Media we use Amazon Elastic MapReduce with Spark for some of our data processing and large scale machine learning tasks. Here we share some details and an example of how to set up Spark 1.0.0 MLlib on EMR for machine learning.

There are materials available that explain how to set up Spark 0.8.1 for data processing on EMR. To demonstrate running a machine learning job with MLlib, we created a project that adds a couple of additional elements to those examples:

1. A Scala main class for a simple EMR-based machine learning job. This class follows Spark’s built-in BinaryClassification example closely, with small changes that allow the user to specify the Spark executor memory (something we have found useful on larger datasets, defaults to 512m), and a modified SparkConf setup to work with EMR. 2. Spark 1.0.0 support. Spark’s MLlib module has seen a number of improvements in recent releases, including sparse feature vectors, decision trees, naive bayes classification, and distributed linear algebra routines for SVD and PCA. The 1.0+ jars available on the Spark website unfortunately do not work out of the box on EMR but for previous releases AWS has provided EMR-compatible jars in the s3 bucket at s3://elasticmapreduce/samples/spark. As far as we’re aware these are not yet officially available for the 1.0+ releases of Spark so we rolled our own. For more information on this — for instance, to create jars for running Spark 1.0.1+ on EMR — see our detailed instructions.

Running an Example

This example follows closely a recent post from Snowplow Analytics. It assumes that you have the SBT, the Amazon EMR Ruby client, and s3cmd installed and configured with your AWS access credentials.

From the command line, run the following, assuming {JAR_BUCKET} is the S3 bucket to which you would like to push the jar.

git clone git://github.com/johnnywalleye/spark-example-project.git cd spark-example-project sbt assembly s3cmd put target/scala-2.10/spark-example-project-0.2.0.jar s3://{JAR_BUCKET}/spark-example-project-0.2.0.jar

Running

To invoke the job from the command line, run the following, assuming {OUT_BUCKET} is the S3 bucket to which you would like to send your output:

elastic-mapreduce --create --name "BinaryClassificationJob" --instance-type m3.xlarge --instance-count 3 --bootstrap-action s3://intentmedia-spark/install-spark-shark.sh --jar s3://elasticmapreduce/libs/script-runner/script-runner.jar --step-name "binary classification run" --arg s3://snowplow-hosted-assets/common/spark/run-spark-job-0.1.0.sh --arg s3://{JAR_BUCKET}/spark-example-project-0.2.0.jar --arg com.intentmedia.spark.BinaryClassificationJob --arg s3://intentmedia-spark/sample_binary_classification_data.txt/ --arg s3://{OUT_BUCKET}/results/ --arg --algorithm --arg LR --arg --regType --arg L2 --arg --regParam --arg 0.1 —-arg —-executorMemory —-arg 512m

You’re all set at this point and should be able to see the results of your job at s3://{OUT_BUCKET}/results/

Specifically, the predictions-and-labels output should look like the following, though may differ since the job randomly assigns training/test labels to 80% and 20% of the dataset respectively. Here we have a test set AUC of 1, great! Turns out this particular toy problem was not very difficult:

(0.0,0.0) (0.0,0.0) (1.0,1.0) (0.0,0.0) (1.0,1.0) (1.0,1.0) (1.0,1.0) (0.0,0.0) (0.0,0.0) (0.0,0.0) (0.0,0.0) (0.0,0.0) (0.0,0.0) (1.0,1.0)

This example runs on a small file but the benefit of using Spark is that we can scale to much larger datasets, preprocess our data, and train a variety of statistical models all within the same framework. Spark’s performance on ML tasks is of course best if the entire dataset fits in memory, and AWS’ r3.8xlarge instances offer 244GB of memory for a few dollars per hour on demand or about $0.25 per hour spot, allowing the user to quickly scale to a cluster with a few TB of memory.

We use this setup at Intent Media to power some of the models that we use for serving ads. Given that MLlib is still changing quickly, we have modified it in certain cases, some simple (predicting class probabilities rather than class outcomes in classifiers) and some more complicated (adding a new splitting criterion to MLlib's DecisionTree). Modeling with Spark on a cluster has been useful in allowing us to rapidly iterate over preprocessing and modeling techniques while easily scaling available CPU and memory.

Jon Sondag

Data Scientist

[intentmediaengineering]

TL;DQA

I am a Quality Assurance Engineer here at INTENT MEDIA. Here is a little video about how I became a QA--a unique tale of a cockeyed optimist and her unbridled enthusiasm. Here is IM’s youtube channel which has MANY other gems and you can learn more about me here.

There are a lot of interesting things about being a QA, but my favorite is the necessity to think big picture, so that the dev is free to focus on the task at hand. I like thinking through the branching paths of possibility that a new feature can create for the user to follow, then using logic to pare down those branches so that my test plan is optimally thorough, yet succinct and non-redundant.

In fact this strategy reminds me a lot of the approach I took to studio architecture, which I majored in in college, and math, my minor. That way of thinking exemplifies what I like about QA, architecture, math, Virginia Woolf, Walt Whitman, what I know of Buddhism through Wu Tang, and pretty much my general outlook on the world.

Proof of the System

My philosophy is that there is an underlying system in everything that scales from infinite to eensy, a ruleset which often repeats and references itself fractaliciously. I seek to understand that hidden logic, then trigger its manifestation and point to it, saying, “seeeee! That's what I thought would happen, and I thought so because I understand the dynamics beneath the surface.”

Once I have designed a comprehensive yet efficient test plan, I don’t mind doing the testing, even when it is manual and monotonous. Many people find that shocking; however, I don’t mind because I see it as disclosing an underlying truth that I hypothesized existed back when I asserted said test plan.

Just as Sol LeWitt probably relished executing his concept for Incomplete Open Cubes by iterating on the combinations of edges a deconstructed cube can have, I enjoy a distinct satisfaction from carrying out a complex or repetitive test plan. I am testing and revealing the supposed physics of the coded little world. I have constructed an experiment and when I carry out that experiment, I will have manifested the relevant logic of the system.

While fulfilling the plan, I am driven by the knowledge that if something went awry in the additional code I should have seen a deviation from my conjecture by now. If you knew everything EVER about a particular seed and the place you are going to plant it, you would know everything EVER about the tree it would become, and QA is about mitigating the risks of the unknowns in the semi-closed-ecosystem that you deal with when you push code.

Grains of Sand or the Beach

The study of architecture allowed me to feel this brand of contentment, the pleasure of demonstrating an invisible principle, in each design--whether it be for a building's floor plan or a modular representation of the NYC subway system. In the real practice of architecture, however, architects are often very concerned with formal qualities, which I think should be the last result of unearthing the hidden logic, not the goal.

The abstract sector of math is all about the quest to pin down the sublime, but arithmetic and derived sciences can lead one to focus on grains of sand rather than the beach. (I took to number theory, knot theory and linear algebra like a mermaid to H2O. But don't ask me to calculate a tip because I don't understand the question, and I won't respond to it.)

Everything is Everything

Virginia Woolf picks up what I am layin’ down when I talk about this. In "Mrs. Dalloway," V Dubs shows us that the overarching system that ties a universe together is fully evinced, and thus--via a little extrapolation--contained, in each fleeting moment of each of our lives, even that of a boring housewife.

She uses stream-of-consciousness narration of all the characters’ thoughts to give the reader a picture of this universe in its entirety. Through following the titular wife’s day of mundane errands, zooming in and out on humanity and posing existential questions as she goes, Woolf proves that the fundamental equation of being is contained in anything and everything.

As Michael Cunningham, a major Woolf fan/imitator, put it: “There is war. There is the search for God. These are all very important things. But everything you need to know about human life, about human experience can also be found in two elderly women having tea in a corner of a little shabby tearoom some place, very much the way the recipe for the whole organism is contained in every strand of DNA. If you look hard and close enough, if you look with enough art at anything that happens to any human being, you can find the whole story there.”

Walt Whitman saw this same equation when he “leaned and loafed at his ease, observing” a leaf of grass as an allegory for the natural world and all its earthly delights.

As for the Buddha, he said a lot of great stuff that sums up the universe. I will refer to another wise eastern(-ish) beacon of wisdom: Wu Tang Clan. In ‘The Tao of Wu,’ the RZA’s treatise on both Buddhism and his own personal philosophy, the legendary rapper explains: “To most of us, you can’t say ‘All is void’ one second then ‘Everything has a Buddha nature’ the next. But what Buddha said is true...Everything is everything.” I see this holism daily. In the natural world, the laws expressed in the minute details have one hundred percent overlap and consistency with the laws expressed by infinite scale. The physical (and metaphysical) laws are consistent and coherent and holistic.

The Leaky Biodome

This is not the case when humans are creating the ecosystem. Biosphere 2 is a lesson in writing code and in faulty QA. The underlying perfect order that I am talking about does not necessarily exist in the spheres man creates, yet some other (flawed) underlying system does.

As the attempt at human autonomy unravelled in the public eye, Time wrote of the Biosphere 2 debacle: “Now, the veneer of credibility, already bruised by allegations of tamper-prone data, secret food caches and smuggled supplies, has cracked ... the two-year experiment in self-sufficiency is starting to look less like science and more like a $150 million stunt.”

In the built world, The RZA-Buddha’s “everything is everything” is still true to the extent that everything is dependent on everything. And that's why when you are building that "everything"--the leaky biodome that you build whenever you write code--from scratch, you better test the S*** out of it, for there will be dependencies.

That blade of grass you built weird just became a wonky field upon which you also built a really awesome condo that you will now have to bulldoze because it's on the buggy lawn that you should have thoroughly QAed!

Beatrix “Betsy” Carroll Quality Assurance Engineer

[intentmediaengineering]

Hack Day: March 2014

One of the best things about working in tech at Intent Media is the fun we all have while working. I’m not just talking about the obviously fun stuff like playing foosball or watching the dogs chase their own shadows. We also seem to have an inordinate amount of fun battling with checkstyle and debugging EMR jobs. I think it’s a great sign for our future how much we all seem to enjoy doing the stuff that is, in fact, our real jobs.

All of this goes double for when we’re really trying to have a bit of fun with things during my favorite regular IM event, Hack Day. We have Hack Days about once every quarter. The goal is to work on something outside what we would normally do. Of course, we’ve had lots of great products come out of Hack Days and make into customers hands. We’ve also had a ton of success with other Hack Day projects that focused on improving our office, our kitchen, and just our experience at work. This latest Hack Day was no exception to our long track record of successful Hack Days with tons of awesome projects. Here’s a recap.

Day 0: Pitches Be Crazy On Wednesday night of this Hack “Day”, we kicked off with a pitch/brainstorming session. At first, it started off a bit slow, making it look like there weren’t quite as many ideas in the queue as before, but that quickly changed once we got warmed up. We like to continually broaden our technical horizons, and it definitely came out in the range technologies people wanted to play with. We already use bunch of Clojure and Cascalog, but people were itching to find ways to take that further. Others even wanted to bring in Clojure’s arch frenemy, Scala. The range of interesting ideas in mobile was also really cool to see, given that only a small portion of us are normally developing for mobile on a daily basis. The non-technical proposals were also pretty ambitious, albeit with only one mentioning the explicit goal of world domination.

Although the schedule has people officially starting their hacks on Thursday morning, before the end of Wednesday, Mike managed to basically complete his proposed project, getting app to app deeplinking up and running on a phone in what must have been minutes.

Day 1: On Like Donkey Kong As Thursday morning rolled around, the office quickly filled up with people diving into their hacks. It was pretty clear that a lot of people were very excited about the possibilities of their ideas and wanted to make the most of their time. A random office visitor on Thursday could easily have been confused about the nature of our business, mistaking us for a massively parallel mobile app development studio. Of course, depending on where they wandered, they could have encountered folks trying to hack our engineering hiring process, source brand new pizza boxes, or tune a ukulele. We do value versatility in our team.

As the day turned into night, several teams were still hacking, constructing, and singing away, powered by beer or Red Bull, depending on their preference. My personal favorite snacks were the dates still on the branches, flown in directly from Tunisia.

Day 2: The Demo of Smaug

Even though some folks were up and hacking all the way into the morning, Friday came around anyway, with just hours left for people to polish their hacks (or just get them running). Fueled by doughnuts, coffee, and panic, people spend the final few hours of the morning getting everything ready to demo. One dev who had already been up all night managed to make it to a doctor’s appointment to find that he was going to have a son and still made it in time to show off some awesome fully functional hacks.

Once “keyboards down” was called, we all met up to rest and enjoy a massive Mexican spread and debate just how dangerous the hot sauce was before the demos. Like a lot of events at IM, the demos were started off with the announcement another awesome sales success. It was a great reminder that all of our fun had been fueled by the success of our business and the satisfaction of our customers.

Our first non-technical hack started us off, with the public debut of “For All Intents and Purposes”, our new Intent Media theme song. It was written and recorded in the short span of Hack Day and was obviously a huge hit.

Diving into our technical hacks, Adrian explored some fascinating pricing research that he summed up well with, “As you can see, we Australians always get screwed.” Following him, Marc showed us how he could give our advertisers superpowers, with a sweet Hulk smash. Double D threw down a bit of monitoring judo, using a tiny bit of Python and Collectd to find some performance numbers in need of a takedown. Following that David was another David, sporting a snappy Michigan tie and an immediately useful app for internal idea collection, built on top of Rails and Mongo.

Representing QA, Michelle walked us through two different projects, both of which were plagued with bugs that she found in external tools. Naturally, she filed those bugs on those tools and still managed to show off how monkey testing using gremlins.js could work for us. Tom followed her with another Javascript project focused on taking even better care of our partners and their customers. Frank demoed his browser extension for travel shopping reminders, and more than a few people asked for immediate access for their personal gain.

Ori knocked more than a few socks off with his two projects. The first was a TeamCity utility for OS X that looked better than the stuff from JetBrains. He topped that with what Kurt called, “what looks like another whole company.” Using Ruby, SendGrid, and Heroku he put together an app to help us painlessly share meeting notes. Andrew also started a bit of a frenzy with his dBeaver replacement, dBieber. “Yes, Justin Bieber plays every time you issue a query.” He also teamed up with Pete to show off a great way to take our hotel pricing data to the next level, automatically bubbling up the best deals.

Our other non-technical hack, led by Lynne, was our first private office. After over 5 years of sitting shoulder to shoulder, the team decided that when Damon returned to the office after some travel, he should find his desk lovingly remodeled into a quaint Italian villa, built out of pizza boxes. Castella D’Amon has more amenities than most Manhattan apartments, including its own phone line, A/C, a wine rack, and a disco ball. Look for it on Airbnb, sometime soon.

Another Tom came up with another project, this one designed to ease the pain of dealing with multiple irritating CRMs. Mike and Mike demoed a beautiful and fully functional iOS app with all sorts of neat features like location autocomplete, app to app deeplinking, and persistent search parameters. Geoff skyped in to show off “a semi-wet Mason jar of dirt”, that turned out to not be a bomb, but in fact an exciting way to connect up our office plants to our monitoring tools.

Amasa tried to solve some of the difficulties of remote testing on iOS and demoed a great and super useful solution. John showed off his substantial engineering chops by using Scala and the Play framework to massively improve the performance of some important partner communications processes. One of the Mikes got back up to talk to our internal chatbot, Bender, whom he had recently wired up to Slack, in the hopes of moving our chatting to a better platform. Camila looked to our international future with a slick solution for ad translation. Bravo! Then, I and my dog summarized a data team project on using ensemble methods to make better, more stable segmentation models.

The last project to demo was a fairly large effort by Ivan, Johnathan, Kurt, Adrian, and Brian. Called the Recruiting Tornado, it was focused on making our engineering hiring process better and more transparent. Using an absolute maelstrom of fun tech, it was built on Clojure, Om, Clojurescript, React, and Datomic. Getting awesome engineers into the company is a huge priority for all of us, and it really showed in the amount of work that went into this demo.

Wrap-Up This latest Hack Day was a success by any measure, with tons of useful products being put together in a day-ish. The sheer breadth of the projects was really impressive. Moreover, I think a lot of us were tremendously energized to see how much we could accomplish in so little time. Some of that is due to a solid tech stack to build on top of, but I think most of that was due to us having a bunch of great people who get excited about what they do. It was a great time for everyone, and I look forward to doing it all over again next quarter.

Jeff Smith Data Engineer

[intentmediaengineering]

Deleting Cookies in Safari 6.0 with Selenium WebDriver

One of the many useful features of Selenium WebDriver is that it can act as a wrapper for several different browser drivers. This means (in theory, at least) that if you restrict yourself to calling methods exposed by the WebDriver API, you can reuse the same code to drive automated tests in any of the browsers WebDriver supports.

In practice, however, this is not always the case. There can be subtle differences in how WebDriver's methods are implemented for each browser. In some cases, certain browsers may not support a given method at all.

One example is deleting cookies. In Ruby, we can tell WebDriver to delete all cookies for the current domain via a call to

page.driver.browser.manage.delete_all_cookies

This executes WebDriver's browser-specific implementation of the delete_all_cookies method, which for most browsers works as expected.

For Safari, a message is passed to the SafariDriver telling it to execute its own cookie deletion method. In OSX, SafariDriver does this by deleting the ~/Library/Cookies/Cookies.binarycookies file where the cookie data is stored.

Unfortunately, as of Safari 6.0, cookie data is also stored in active memory by the cookied process. If cookied notices that Cookies.binarycookies is missing, it simply recreates the file from memory -- so deleting it is no longer enough. SafariDriver has not yet been updated to reflect this change.

Fortunately, there is a simple workaround: after deleting the cookie jar, just kill cookied! In Ruby we can accomplish this by calling out to the shell with

%x( rm ~/Library/Cookies/Cookies.binarycookies ) %x( killall cookied )

We don't have to worry about this breaking Safari's cookie management -- if Safari notices that cookied isn't running (whenever it looks for some cookie, for example) it restarts the process.

Happy testing,

Amasa Amos

Quality Assurance Engineer

[intentmediaengineering]

Random Assumptions can make an A-- Part 1

Overview

Sometimes its good to take an in-depth look at the mistakes we make. This is an examination of an issue we were addressing, and how a couple of assumptions we made, introduced a new and devious bug.

It ain't pretty but looking back is how we get better. And hopefully you can read this and learn something without making the same mistake.

We split this into two posts. The first post covers the original problem we encountered and our attempt to solve it. The second post will cover the bug we introduced, and our final resolution.

Background on Multivariate Testing

We here at Intent Media believe in testing and data. We have a whole system dedicated to test the effectiveness of our ads, the Multivariate Test System. This system allows us to test multiple attributes of our ads at the same time. It's used throughout our system and has proven to be a very effective tool to maximize our effectiveness.

For example, let's say we decide to test a new design, Design Awesome, against our current design, Design Sweet with a 50/50 split. We also want to test a new Ad Copy, "Look at me!", vs "I am a sweet ad copy" also at 50/50 split. Our system allows us not only to look at each attribute independently but also in combinations (how did Design Awesome with "Look at me!" vs Design Sweet with "I am a sweet ad copy").

I won't go into too many details about Multivariate Testing but if you want to read more about check out http://en.wikipedia.org/wiki/Multivariate_testing.

The original setup

Our old implementation worked by building a 'splat' table. Using our above test as an example, the splat table would contain four entries:

Design, Ad Copy, Bottom Range, Top Range ------------------------------------------------------ Design Awesome, "Look at me!", 0.0, 0.25  Design Awesome, "I am a sweet ad copy", 0.25, 0.5  Design Sweet, "Look at me!", 0.5, 0.75  Design Sweet, "I am a sweet ad copy", 0.75, 1.0

When a user visits one of our publisher's site we assign them a single random number or 'dice roll'. This number will determine all the values for all the attributes the user will see while looking at our ads.

But the dice must also be sticky. If the random number changes everytime the user visits the site, the ad could potentially change color and design for a page refresh, and that would break the validity of our tests. We don't want to use a cookie to record the random number because that would be third party cookie, which many users and browsers block and we don't want to rely on them.

To do this we use a user_id assigned by the publisher (not personably identifiable), add a salt string to the user_id, and use the hash code to seed the Random class to get a repeatable random number:

int seed = String.format("%s some salt", userId).hashCode(); double diceRoll = Random(seed).nextDouble();

This was quick way to generate a sticky random number, and distribution of the numbers was quite good. This implementation worked well for us for a quite a while. But over time we discovered two bugs with this.

The original bugs

1. The splat table is really slow.

As we started testing more and more attributes ,the splat table started getting really large. In our above example we have only have two attributes each with two possible values which leads to a splat table of 4 rows. For one of our current partners we are testing 13 separate attributes with 2-6 possible values for each attribute. The splat table for this partner would be 7,464,960 rows. Yikes!

While the dice roll to get the attributes is relatively quick, building the table is really really slow. We tried lots of tricks to speed up generation, but it was taking a lot of time and effort. In addition if we made one change to any of those attributes we would have to rebuild the whole table every time (at one point it locked up our whole database for over an hour). So it made updating any of these tests painful.

2. Moving fenceposts

Occasionally we fiddle with the percentages of our tests. This will shift some users from one value to another on the attribute we changed. This is acceptable for us because we are shifting the tests.

But because of the nature of splat tables, it can also shift users on multiple attributes not just one. Consider our original example splat table:

Design, Ad Copy, Bottom Range, Top Range  ------------------------------------------------------ Design Awesome, "Look at me!", 0.0, 0.25  Design Awesome, "I am a sweet ad copy", 0.25, 0.5  Design Sweet, "Look at me!", 0.5, 0.75  Design Sweet, "I am a sweet ad copy", 0.75, 1.0

Now instead of doing a 50/50 spit for the design, let's do a 75/25 split. That would generate the following table:

Design, Ad Copy, Bottom Range, Top Range  ------------------------------------------------------ Design Awesome, "Look at me!", 0.0, 0.125  Design Awesome, "I am a sweet ad copy", 0.125, 0.25  Design Sweet, "Look at me!", 0.25, 0.625  Design Sweet, "I am a sweet ad copy", 0.625, 1.0

Now imagine you are user and your sticky random dice roll is 0.40. In the original table you would get Design Awesome with "I am a sweet ad copy", but now you get Design Sweet with "Look at me!". So even though we only changed the probability for one attribute we shifted some users over multiple attributes. Not good!

Enter the conquering/bumbling heroes...

Given all this we set out to try and solve both issues. There were a number of strategies we could have employed to solve the first problem, but the second problem just seemed intractable. We could just not figure out a way to structure the splat table to get around this moving fence post issue. So we decided to abandon it, and do a 'dice roll' for each attribute.

But this created another problem. How do we do generate 17 different sticky random numbers. Looking at how we used to generate random numbers, we decided to modify our random number generator to include both the user id and the id of the attribute:

int seed = String.format("user %s attribute_id %s", userId, attribute.getId().toString()).hashCode(); double diceRoll = Random(seed).nextDouble();

This would generate a unique repeatable seed for each user and attribute. We tested this with a single attribute and got a good distribution, and surprisingly it was faster than our older implementation. All is well, right?

Next time, the fall

There was actually a very large bug we introduced with this change. We'll detail it in the next blog post, but see if you can guess what mistakes we made in this fix.

Orion Delwaterman Software Engineer