Niger Little-Poole

Right now what I have is really only useful for binary variables in the Dimension tables of a Star schema model. However, I’m brainstorming ideas on how to handle Fact tables. One method I’m playing around with is creating an abstraction on top of a transaction table that is equivalent to a Bloom Filter. I read this paper on Bloom Filters and Differential Privacy and it seems its possible to offer similar guarantees to Random Response. 

The challenge is implementing this while maintaining the following:

Key Integrity & Iindexing

Normalization

For the sake of this example, I’m going to deploy the go-whenami microservice that I open sourced a while back. The AWS Team has created some amazing cloud formation templates that allow you to deploy this stuff without writing a line of code. Simply head over to this github repo and checkout out the README. 

At the bottom of the page there are preconfigured launch forms for the different cloud formation scripts. Just use the one I’ve highlighted. My Timezone microservice does not have an RDS database so I will use the one without DB checked. However if your service has a DB, use that form. It will allow you to configure an RDS instance to be e spun up with your service and will pass credentials as environment variables to your Docker container. The following form choices are important, everything else can probably be left default in most cases:

Environment: picking prod makes it available in multiple regions

EC2 Pair: This is the ssh key you’ll use to login to the bastion host

Health Check Path: This is the endpoint of your health check. Mine is defaulted to the root endpoint so I won’t make a change. This endpoint should return 200 when your service is fine and 500 when its facing problems so that AWS can attempt to spin up another instance and replace the unhealthy container with a healthy one.

Hosted Zone: This is usually the same as your domain name. ie “whenami.io”. If you don’t have a hosted zone setup in AWS Route 53, this will create it for you.

Domain: This is the subdomain you want the service to live on. I would choose something like “api.whenami.io” for this. However you could make it the same as the hosted zone if you want it on the root.

Github (Repo/User/Branch/Token): These settings are how Fargate will find your code and deploy it. Just follow the links on the form if you don’t have a Github token. For simplicity choose master, but if you are using Github flow it could make sense to deploy another Fargate cluster after that looks at develop. This would be your QA instance.

Anything Else: Configure to your liking. This might be CPU or max number of concurrent instances. These options really come down to the performance and cost constraints you have for your service.

Okay so once you’ve done all that, just hit create, kick back, and wait for your service to spin up. Its possible you will get failures if hit soft limits on things like VPCs or Elastic IPs. So make sure you don’t have extra resources running. Depending on the traffic AWS is experiencing, it will take 15 minute to an hour to spin up. Once its setup you will have the following:

Service Running on the domain you specified

Load Balancing and Elastic Scaling. Meaning when there is high volume, Fargate will spin up parallel instances of your container and split the load amonsgt them, scaling it back down when traffic decreases.

Continuous Deployment! Go to your repo, run git commit --allow-empty -m "Trigger build" to make an empty commit. Push that to master (or whatever branch you configured) and Fargate will notice the change and redeploy your service with the changes. no more manual deploys!

CloudWatch Logging & Alerting. All of your services logs are captured by CloudWatch and you can setup alerts so that if your production systems are experiencing lots of issues, you know about it.

Extra Security via a Bastion Host. As a part of this deploy, a server called a Bastion Host was deployed as well. Your main service is only visible to the load balancer and to the Bastion Host. But the bastion host is visible to the public internet. You can use the keys you setup earlier to ssh into this instance, and from that instance interact with your service. This reduces the surface area for attack and AWS provisions special resources to monitor the host in case of attack. Even better, you can always stop the instance when you aren’t using it so others can’t try to penetrate and you don’t have to pay.

The way we actually solved the problem was by modifying both python’s tzgeo and an equivalent Scala package so that we could use them in a distributed manor via Spark. There was nothing out of the box that worked and there were a lot of services offering to do it for a fee per API call. I realized working on this that this is a fairly simple problem. Paying for it just doesn’t make sense.

At the end of the day, all that happens at runtime is a query against geospatial data to see if the coordinate is within a given timezone (represented as a polygon). There are only 24 timezones, so this is actually quite trivial to accomplish. Rather than running a full hosted geospatial database, we can leverage Spatialite. Spatialite is an open source, geospatial extension for SQLite. Its essentially what PostGIS is to Postgres but for SQLite. Spatialite, like SQLite, is a file based embedded DB. This is a perfect use case as there are no writes in our pacakge, only concurrent reads, which is the ideal scenario for a file based database.

Assumptions

Having studied Operations Research, I'm a big fan of Monte Carlo Simulation. One of my professors at Columbia bragged about how much more flexible a simulation based solution can be versus a closed form solution. First, I want to address the assumptions made by Mr. Miller. He makes 3 big assumptions

Followers arrive according to a single poisson process at rate once per hour

Whenever a follower arrives on Twitter, they will always see the tweet we are modeling.

Each follower, and their followers, has the same probability(p) of retweeting the tweet

All of these assumptions are definitely innacurate. First, followers cannot be coming at a constant rate for every user, especially not in a system where every user of twitter is refereshing once per hour. In Miller's example A with a 1000 followers, that means that all 1000 followers will check Twitter within 1 hour. On top of that, his model assumes that the rate at which Followers appear will be the same, regardless of the number of followers one has.

So I'm altering that slightly for my simulation. Instead I'll make an assumption, that the rate of arrival of my followers is the number of seconds in a day over the number of followers. This essentially assumes that all my followers, will on average, show up once in a day.It also assumes that time of day is not a factor. This is also not true, but you have to make some assumptions for the simplicity of the model. I'm also going to keep the latter two assumptions (seeing a tweet and constant probability(p)). I will explain at the end how this simulation provides the foundation to start to replace these constants with better interactions.

Simulation

var _giphy_tv_tag="typing"; var g = document.createElement('script'); g.type = 'text/javascript'; g.async = true; g.src = ('https:' == document.location.protocol ? 'https://' : 'http://') + 'giphy.com/static/js/widgets/tv.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(g, s);

So I whipped up an iPython Notebook with a Discrete Event Monte Carlo simulation of this scenario. It was actually quite trivial and only amounted to about 50 lines of code. I won't overly explain the simulation here, view the code if you want to see how it works. But in a nutshell for a fixed probability of retweet p, I simulate a poison process of followers arriving and then retweeting with the given probability. Miller's closed form solution relied on limiting the retweet chain to 2 in order to reduce the complexityof the algebra. My simulation does not have this same constraint. In order to optimize runtime, I did limit the length of retweet chain to 6. However, this limit was based on research conducted by Twitter.

A Test Problem

Miller's test case is two tweets, A and B.

Tweet A was posted by a user with 1000 followers and received 25 retweets in an hour

Tweet B was posted by a user with 2000 followers and received 25 retweets in 30 minutes

Ideally these should be quite similar. This is asking what the tradeoff is between the time the tweet had to be seen and the number of followers the user has. Without any kinds of decays these should be relatively equal tradeoffs. i.e. showing the tweet longer to more followers should yield similar results to showing it to more people for a shorter amount of time.

Which tweet had a high retweet percentage?

via GIPHY

My iPython Notebook also incldues the answer to this. According to my simulation, A most likely had a retweet percentage of 8.2% while B had a retweet percentage of 8.21%. At the moment I haven't been able to figure out a good signifigance test for this. But for now, I'll assume its close enough to demonstrate equivilance. If you have any ideas, reach out I'd be quite interested. However, I think this answer is far more satisfying than Miller's original answer of around 2% for each.

Miller's model, with each person averaging a reload per hour, will see both tweet A and B having 1000 people expected to view the tweet. He then assumes that each of those people will retweet with a 2.1% probability and that their ~90 followers will do the same. One thing to note, all 90 followers for each person who retweeted, won't see the tweet. Only those who manage to arrive in the time remaining between the time the retweeter actually retweeted and the end of duration have the opportunity to retweet further in the chain. In the first order, the direct followers, 20ish people should retweet and then in the remaining time only 5 of those second order followers will retweet.

My model yields a quite different answer. By allowing higher order retweeting and not assuming that all of a users followers will appear within the hour, the model assumes a far higher percent of fewer incoming viewers need to retweet. To make it simple, if only 1/24 of my followers are expected to show up within an hour, then a lot higher of a percent of them need to retweet. Even then, my impression rate is a bit too high for reality, market sentiment says that the average tweet only has around a 2% impression rate.

How to get a better model?

via GIPHY

via GIPHY

Miller's model has so many assumptions and constraints that it doesn't realy accurately model the system. My simulation is also too limited in its current form. However the magic of simulation is that we can introduce more complex elements to the model quite easily. Miller's work is essentially a manipulation of a poisson process and a binomial distribution. While not trivial, finding a closed form solution is certainly doable. But if we wanted to take into account time of day, or decay the retweet probability as it gets further from the source, it will become ridiculously complicated to find a closed form solution.

So what would I do to get a better model?

Add a decay factor to the retweet rate the higher the order ( distance from the original poster) the tweet is

Introduce a decay factor due to time. This should capture the fact that the older a tweet is, the less likely arriving users are to even see it

Make the arrival process a mixture of poisson processes based on the time of day or switch distributions entirely to something that weights more heavily toward more active times

Randomly generate the number of followers each retweeter has according to the researched power law, rather than using the expected value. Should help to give better information on the variance

Optimizing your generator is just a matter of attempting to get the models probability distribution to match as closely as possible to that of the training data. Or at least enough so that the competing model’s classification accuracy falls to 50% meaning the generator is optimal. Goodfellow, in his original paper,  was able to demonstrate that his cost function to get to that distribution was really equivalent to a Jenson-Shannon (JS) divergence. JS divergence is really just a mixture function of Kullback-Leibler (KL) divergence. KL divergence is just an entropy based measure of the difference of two distributions.

Goodfellow’s method had a number of weaknesses that he attempted to address in a follow up paper in 2016. Specifically issues around convergence of the loss function and actually generating things, in this case images, that were not only from the same distribution, but actually were intelligible to humans

The Wasserstein Gan paper attempts to solve a lot of these problems by introducing a new cost function. This cost function is based on Wasserstein Distance, also known as Earth Mover distance. Wasserstein distance is actually a measure of the amount of change a distribution would have to go through to become another one. It has the convenient properties of being able to converge on everything that KL and JS divergence can and it can also converge on a number of additional cases. Specially cases where KL and JS resolve to infinity which will through off gradient descent methods. 

Wasserstein Gan also addresses a big problem with the orignal Gan methodology. Specifically that the Discriminator model was never fully converged because of concerns about saturation. The Wasserstein based cost function has properties that prevent these scenarios and so its possible to converge the Discriminator. A more competitive discriminator leads to a better generator.