randomCanary

This is a blog on computer science and engineering stuff, with some economics thrown in, mostly because I'm not qualified to write on anything else. I'm an engineer with two-and-a-half publications, and occasionally call myself a computer scientist because that impresses my niece. One day I hope to publish here. My Githubs[ 1 , 2] and my Google Scholar page, if you're into that sort of thing.

[preetjotsingh]

WhatsApp Easy to Hack

WhatsApp is easy to hack, it has been claimed, by Bass Bosschert, a Dutch security expert from Holland. Bosschert decided to investigate if it was possible to read and upload WhatsApp chat from one...

How is it possible Android's sandboxing is this bad? Is having a new user/id for each app that much extra overhead?

[preetjotsingh]

In episode 11 of Arrow's first season, Felicity Smoak is asked by Olliver to break an encrypted security key. I was interested to see what they used to represent "military-grade encryption" (Is it really that hard to show a screenful of arbitrary hex strings? Lost Easter Egg opportunity.), so I paused the screen and checked out the code. (at 0:51 in the video). 

It's obviously C++ and seems to be handling cmdline arguments which was enough to find it  here.

Here's the description of lunar/jevent.cpp: 

"It computes the date/times of "classical" Jovian satellite events

(transits,  shadows,  occultations,  eclipses) over a given time

span,  and sorts them out to produce the sort of event list one

sees in _Sky and Telescope_ and similar publications.  It can

also store them in a binary form that is used within Guide,  so

that that program can show Galilean events without having to

do all the math itself."

Oh, Hollywood. I'm just glad you're showing C++. 

[preetjotsingh]

The Coin problem

Exponential runtime algorithms get a bad rap. They're not really terrible, but they scale terribly, which means for a lot of problems and a large number of reasonable inputs, they work perfectly well. Usually you need to show some artificially high input to bring out the brute-force solution's ugly super-long runtime-side. That's why I like the Coin problem (also called the Change problem): It's a great example of a problem with an (almost) unrunnable brute-force solution, even for perfectly reasonable inputs. 

The Coin problem:

Given a list of coin-denominations, how many ways can you combine coins them to form some target amount? Here's an example: Your list of coin-denominations are [3,2,1] with  a target amount of 7. 

Here's a solution that totals up to 7: (1, 2, 0). That is, 1 three-coin, and 2 two-coins for a total of 7. You could also just have 7 one-coins. Or three 2-coins with one 1-coin and so on (the total number of ways is 8, by the way).

Here's a better real-world example: In the United Kingdom, they have eight coin-denominations (in pence), ranging from a penny to two pounds: [1, 2, 5, 10, 20, 50, 100, 200]. How many ways you can combine them to get two pounds (200 pence)?

This isn't an artificial example - the coin denominations are real. And the target amount isn't insanely high. Yet a brute-force solution took me seventy-five minutes to run on a i7 laptop.  

Solution I: Brute Force

All solutions are essentially a vector over the list of coins - like the (1,2,0) example above. You could have 0 of the first coin, or maybe 1 or more, depending on the value of (target/coin). For instance, we can use 0, 1 or 2 of the three-coin above. Similarly, the number of two-coins used for a solution could range between 0-3 and 0-7 for the one-coin. 

We could get all possible ways by three for-loops, one for each coin, ranging between 0 and (target/coin). This is exactly equivalent to a cartesian product, which is excellent news because python's itertools lib has a cartesian-product-generating function 1. 

So we now simply generate all possible vectors and then check each one to see if they total up to the target. Here's the code:

If you look at the runtime, you can see this scales terribly: We have two elements for the runtime: One's the gap or ratio between the target and the smallest-denom coin (a penny), which is at most 200 in our example, (this forms the base) and two, the number of coins (eight in our example) which dictates the number of for-loops (and thus forms the exponent). So the outer loop has an upper bound of 2008 with the inner section taking O(n).

So O(bn)*n is an upper bound (probably non-strict, but it'll do). The point is, it scales terribly. 

To see if my laptop could handle it, I did a quick back-of-the-envelope calculation for number of cycles:

The outer loop consists of:

itertools.product(range(200+1), range(100+1), range(40+1), range(20+1), range(10+1), range(4+1), range(2+1), range(1+1))

which is 5.76 billion iterations * inner loop=8  yields roughly 46 billion iterations. Multiplied by 3 or 4 constant-time ops inside the inner loop (there's a break, remember?), we get roughly 140 to 180 billion operations. To find out how long my laptop takes for each common op (in Python), I ran a simple loop containing 1 mult/add/if op. In one second my laptop runs 17 million mult ops / 25 million add ops / 30 million if ops. At that rate, my algorithm should take roughly 6000 seconds to run. Actually, it took  me 4531 seconds - 75 minutes. So we should really be looking for a better solution. 

Solution II : Dynamic programming

Let's have a closer look how we solve coin problems using human computation: Let's sort coins in ascending order and then take the first coin - a penny. How many ways can we represent 2 pounds with pennies? Exactly one way - with 200 coins. In fact, for an target amount x, we can represent it exactly one way with pennies - using x pennies. How many ways can we represent say, 10 pence with pennies and tuppence - coins (1,2)? Well, we know it'll include all the ways we can represent it with pennies (which we know is 1). That is, it'll include all the ways we can represent 10 with some pennies and no (0) tuppence. Then we check if it can be represented with some pennies (possibly 0) and 1 tuppence, with 2 tuppence and so on. We can think of this recursively: If we represent 10 pence with (some combination including) 1 tuppence, we need to know something else : How many ways can we represent the target amount minus the 1 tuppence (8 pence) with (1,2)?

Like most dynprog solutions, I actually needed to spend nontrivial time working out the recurrence relation from several small examples by hand. So here's our new solution: We make a matrix with rows as target amounts from 0 to our (final) target (200 in our example) and the coins (sorted, ascending) are the columns. We populate the first row (target=0) with all 1s since for any set of coin-denominations, there's exactly one way to represent that:  0 of the first coin, 0 of the second coin, etc. We populate the first column (denom = one penny) with all 1s, since for any target x, there's exactly one way to represent it with pennies (with x pennies, to be precise). Then exactly like we mentioned above, for any cell, let's say the 200th row X 2nd column ("How many ways can we represent 200 pence with all coins less than or equal to tuppence?") , our value is equal to:

(1) How many ways can we represent 200 with just pennies (matrix[200,1])  +

(2) How many ways can we represent (200- (1*tuppence)=198) with pennies and tuppence (matrix[198,2]).

 We have our recurrence relation. Now we just loop over and populate our matrix using this relation. The answer is in matrix[200, 200] ("How many ways can we represent 200 pence with coins less than equal to two pounds?"). 

Here's the code:

The algorithm may have taken a while to work out, but the speedup was huge - this took just over a thousandth of a second to get the result.That's a speedup of four-and-a-half billion times.

Solution III : Recursive

There's more than one way to skin a cat - another human-computation approach is to consider the coins in descending order:

Considering the 2-pound-coin, we can represent 200 pence with 1 * 2-pound coin (and nothing else, in that solution). Considering the 1-pound coin, we could represent 200 pence with 2 * 1-pound-coins, or 1 * 1-pound coin and 2 * 50-pence coins. Or 1 * 1-pound coins, 1 * 50-pence coin and 2 * 25-pence coins. Or 1 * 1-pound coins, 1 * 50-pence coins, 1 * 25-pence coins,...and so on. You get the idea - We get a new subproblem after taking away the value of a coin from the target amount (much like the dynprog approach). How many ways can you represent 200 pence with at least one 1-pound coin?  We need to calculate how many ways to represent 200 -100 =100 with coins of 50 pence or lower, and this further reduces to another subproblem with a smaller target amount (and eventually smaller coin denominations) and so on. 

And here's the code for that solution: 

This takes 1.75 seconds to find the solution.

1. Writing three for-loops would limit our program to working only with three or less coin-denominations. But using the lib allows our function to work for a variable number of coins. 

[preetjotsingh]

Quick-and-dirty ML Algorithms II: Decision trees Contd.

In the last post we saw what Shannon entropy was - simply a way of ranking features by how likely they are to yield labels. Or to put it another way, given some feature, say beakType for a bird-labeling situation, Shannon entropy of beakType measures with how much certainty you can name the bird, given just that feature and no other. 

Of course, if beakType can tell us the name of the bird with 100% certainty, then we're done - we don't need any other feature. That's pretty unlikely in any realistic model1. Which is why we need Shannon entropy.

Calculation of Shannon entropy

Let's have another look at our birds dataset -

We already saw Colour was a much more certain indicator of any bird's name than Wingspan. Formally, that can be calculated as the feature's (Shannon) entropy - I'll show an example of the calculation below and explain it.

We calculate the Shannon entropy of Wingspan as follows:

The set of Wingspan values are 10, 5 and 3 across 4 data points.

There's only 1 data point for 10, and so it corresponds to just one label - (-1)*1* log 1 (common log bases are 2, e and 10 according to Wikipedia - I'm going to assume 2) is it's individual calculation - which is 0. 

Same for the Wingspan value 3. 

There are 2 data points for value 5, each corresponding to a different label (Greater Flamingo and Blue Heron). It's calculation is (-1)(1/2)log(1/2) + (-1)(1/2)log(1/2) = 0.5 + 0.5 = 1. 

The entropy calculation for the Wingspan then is (1/4)0 + (1/4)0 + (2/4)1 = 0.5 .

The basic calculation of Shannon entropy is <frequency ratio> * log<frequency ratio> . I like to think of feature-values having a frequency vector over the labels. The frequency ratio of Wingspan value 3 corresponding to label Peregrine Falcon, so it's freq. ratio is 1/1. 3's freq. vector over the set of labels would look like this:

(0,0,1/1,0) -- corresponding to (Wandering Albatross, Greater Flamingo, Peregrine Falcon, Blue Heron). 

Similarly, 10's freq. vector is (1/1, 0, 0, 0) and 5's is (0,1/2,0,1/2)

Your basic entropy calculation for each feature-val is simply:

feature-val_entropy = 0

For:every number in freq. ratio

           feature-val_entropy += number * log(number)    

Which is what we did above for 10, 3 and 5. The last step is merely adding all these, weighted by their frequency in the dataset: So values 10 and 3 occur once each in a dataset of size 4, hence the (1/4). Value 5 occurs twice, hence the (2/4). 

Now we know how to calculate Shannon entropy, yay for us. What does it mean? Entropy means disorder. The greater the value for entropy, the more the uncertainty. A value of 0 indicates maximum possible certainty. A value of 1 indicates maximum possible uncertainty. 

So Wingspan has a value of 0.5 - is that good or bad? The question to ask is, is it the feature with the least entropy? A quick calculation for Colour  gives us 0+0+0+0=0 which is certainly less than 0.5 . And actually with zero entropy you don't need any other feature. 

This is of course, a much-too-simple example. What we'd actually get is a bunch of entropy calculations for all features, and then we choose the the feature with the lowest entropy to split the dataset on / construct our tree with. 

Algorithms such as ID3 simply get the best feature (the one with the lowest Shannon entropy), refine the existing dataset to remove data points for which that feature is decisive or certain, and recurse on the new, culled, dataset, until until you find a subset with all the same labels or until all the features are finished 2.  

The code:

1. Labeling outliers can often be done with just one feature, because they're, well, outliers. You can label a bird just by the wingspan if the wingspan >=11 ft - then it's a Flying Albatross. For labeling the vast majority of birds, though, just the wingspan isn't enough.   

2. In the latter case you might not be able to label your unknown data point X with absolute certainty. Refinements that solve this could include some concept of distance (perhaps borrowing from another ML algorithm, k-nearest-neighbours).

[preetjotsingh]

I've been looking for a lightweight tablet you can write (well) on ever since tablets (as we now know them - not tablet PCs of yore) first came out. The technology was there (ref. Tablet PCs again): It's a question of squeezing it into a smaller and better form factor. And OS. The Surface Pro was a contender until I saw it's lame five-hour battery life, so I'm excited to see how the SP2 (which should have a much-improved battery life thanks to Haswell chips) turns out. 

This review stinks though. There's plenty to bash MS on, specific to the Surface. I'm not sure these objections hold water though. 

Limited Channel program : I haven't researched this, but from personal experience and anecdotally, the distribution seems to be widespread enough : I checked out Surfaces at a Microsoft booth in a downtown Chicago mall, and in a separate section at a California BestBuy. I didn't see if Fry's (or any local popular retail outlet) stocked it, but if it didn't, that would be a valid objection. Which you could mention in this article. But haven't. The article mentions both the MS booths and BestBuy as retail outlets but asks "Why not let the smaller guys sell the tablets too?" The smaller guys have names, right? How about mentioning them? 

Lack of Windows Store apps : Youtube and any non-IE browser are given as examples. Isn't this a full-fledged laptop? You don't use apps to access youtube in a laptop - you enter in the URL in a browser. Ditto for downloading Chrome or Firefox. Did you have problems accessing youtube? Did you try installing non-IE browsers and faced problems? That would be information actually useful to readers. 

Size and price: If you're criticizing a product on price, I'd expect you to mention the price of competing products. The same for dimensions. For the record, all the competing products I've seen (the Sony Duo, Samsung ATIV and a few Fujitsu models) are priced and sized similarly. 

I'm not saying these couldn't be valid objections, but this article reeks of lazy reporting. Would it kill you to put in a little research? It's ten minutes on Google these days, if that. #reportingfail. 

[preetjotsingh]

Quick-and-dirty ML Algorithms I: Decision trees I

Decision-trees are ridiculously simple to understand, except for the Shannon-entropy concept. I'm going to explain D-trees very quickly, and then explain why Shannon entropy is required, and how it works. 

Basics: A dataset is composed of data points which have attributes or properties, which I will call features. This dataset is usually provided to you, or observed. As an example, here's a dataset of a bunch of birds: 

Given this dataset, can we identify the 5th bird? 

Sure. We see the 2nd bird (data point) looks exactly the same as the 5th.  It matches our 5th data point in all (well, we have only two) features. So if we take that to be correct, our 5th bird must be a Greater Flamingo as well. 

The ML problems we approach in D-trees (and probably most of ML) are structured this way: Given a bunch of data points, can we classify some unlabeled data point X? The label for classification, also known as a target label or a class-label, is simply a feature for which we don't know X's value. By convention it's usually the last column. When I refer to the set of features, I usually won't count the class-label in them. 

And that's all D-trees are. You look for a data point that matches X exactly (that is, have the same values as X for all features - well, except for the missing one) , and assign its label to X. 

We can see a few problems with D-Trees from this example:

(1) We need a data point that matches X (our 5th data point) exactly. That's pretty unlikely to happen, and you can see why:

For that you'd need a dataset where all combinations of features are represented. If we have just 30 features, each having just 2 values (say, Yes / No), we would require a ridiculous 1 billion-plus data points (2^30=1.073 billion), just to represent every combination. 

(2) To understand the second problem, let's examine what we actually did to label X with "Greater Flamingo" above: For every data point we checked all features to see if they match X's. This is horribly inefficient if the number of data points is much, much larger than the number of features. And that's usually be the case for all datasets you'll encounter.

It's easier to take each feature (let's start with the first one: Wingspan) and check which value matches X's (It's 5). We'll then consider just that subset of data points (we have two data points that match). We then repeat with other features until the subset becomes smaller and smaller till, hopefully, we have a subset with just one label. In our example, after considering Wingspan we have a subset of 2 data points: Then we check if either of those have Colour=Pink. In this case we have one, and we can assign X it's label of Greater Flamingo. 

However, we can make this even more efficient. If we considered the feature Colour first, we'd get a subset that has only one label (well, the subset has only one data point) and we'd be done. With just one iteration. 

Saving on iterations could be a big deal if we have a ton of features. And most useful data sets do.

So where are the trees? You can make trees explicitly by splitting the dataset by each feature, with a branch for each value of that feature. That's exactly what we described above.

How do you choose features efficiently? That's where Shannon entropy comes in. First, let's see why choosing Colour worked so well: Colour has  a 1-to-1 mapping with Name. That is, for each branch (value) of Colour, we have only one value in Name. That clearly isn't the case with branches or values of Wingspan - the value 5 corresponds to both Greater Flamingo (2nd data point) and Blue Heron (4th data point). If you were trying to decide some unknown bird's label solely by Wingspan, you'd have to flip a coin if it had a 5-foot wingspan. 

So you can see this as a deterministic vs a probabilistic function for the 2 features. Exactly! I probably should explain what I mean by that. Deterministic here means that for every branch or value, the feature Colour is able to map to a single label with 100% certainty. In Wingspan's case, that's not so for value 5 - that maps to 2 labels, with an equal number of data points (well, 1) for each label. 

So if Wingspan=5 had say, 9 data points that have a label of Greater Flamingo, and just 1 data point with a label of Blue Heron...We could say that (solely by) Wingspan=5, there's a 90% chance the bird is a Greater Flamingo. 

And...that's Shannon entropy. 

Shannon entropy simply calculates how likely or certain is a feature on its own, to map to labels. Yielding a label with 90% probability (for a given feature-value) is pretty great. Yielding a label with absolute certainty for every single feature-value's downright perfect. You don't need any other feature at that point. Colour's like that in our example. The other end of the spectrum's a feature that yields an equal chance of any possible label for every of it's values - this is the least certain. In between we have features that may yield label with differing certainty for each of it's values.  Shannon entropy of a feature is simply a metric for this overall certainty - certainty averaged across all it's values. 

Now you know why we need Shannon entropy and what it is. In my next post I'll show how to calculate Shannon entropy, and an algorithm to select the best feature - which, it turns out, is exactly what we've described above. 

[preetjotsingh]

Quick-and-Dirty Machine Learning Algorithms 0: Intro

This is a quick-and-dirty tutorial on ML algorithms: It's aim is to provide a programmer with a very quick, but still somewhat in-depth look at ML with coding (hence the dirty). This isn't meant to substitute a full-fledged ML course. For that I've been told to check out Andrew Ng's Machine Learning course. 

Audience & disclaimers: My typical audience is someone with basic CS knowledge and half-decent programming skills. These posts mainly serve as online notes for ML algorithms after I've learnt them and as a reference for my friends. If it's useful to you, great. Leave a comment in any case.  If I've got something wrong, let me know.

My research background's mostly in CS Theory, so I'd like to add that if you're in the kind of CS theory that models real-life situations, you've probably caught on that ML's pretty necessary to refine your model and test it out.

What are ML algorithms and why should I know them?

Machine Learning algorithms are one set of techniques for filling in gaps in a data set. Or to put it another way, it's a way to guess an unknown event given a dataset of similar events. 

As an example, consider the case of a student, Lucy: We observe Lucy's schedule for the past three months, and see that 9 out of 12 Thursdays 4-5 pm she's in the library, studying. If we were asked to guess where's Lucy going to be next Thursday at 4:30pm, the library would be a pretty good bet. We could confidently say: “Based on the data, there's a 75% chance Lucy will be in the library at 4:30pm on Thursday.” (If this looks like your stats course, you're right - ML's just statistical inference (well, at least the type I touch upon here). 

Of course this is a fairly crude way of guessing. We don't know why Lucy was studying in the library so we can't tell if she still needs to go there (maybe she was studying for a school exam, and school's off now, so she needn't be at the library). Maybe she went to the library for three months because she hitched a ride with her study-buddy Bob, but Bob now prefers to study at the Starbucks that opened just last week near his house.

These are all important questions to ask when you use ML algorithms within your model: You essentially want to know how relevant the data set is to answering your question. Maybe the dataset you infer from is not Lucy's schedule for the past three months, but the schedules of students at Lucy's school. Or schedules of students in Lucy's age bracket. Or her neighborhood. All which might be relevant to answering questions about Lucy's current schedule to varying degrees. 

ML algorithms then, can be somewhat heuristicky by themselves. And that's why it's important to understand what's happening under the hood, even while there are several emerging APIs and apps that run the algorithms for you (Splunk and BigML come to mind). ML algorithms though, for all their simplicity / crudeness can be surprisingly accurate when applied well, because people are often consistent ; repetitions take place. Patterns are formed. The more sophisticated ML algorithms try to detect such patterns explicitly, and make predictions based on them. In this blog post I intend to take an ML algorithm, explain the theory, and give code examples.

Acknowledgements: Outside a full-fledged course, combining the theory with code's been done super-well in Machine Learning in Action by Peter Harrington, which is a great starting point for programmers seeking an intro to ML. I've also learned from Wikipedia, AI course lectures (Udacity's Intro to AI + AI for Robotics & Coursera's ML course by Andrew Ng have explanations of several core concepts), and numerous course notes, presentations and other web snippets from Google (Michael Crawford's ID3 presentation stands out).

[preetjotsingh]

A 5-year AI program composed solely of MOOCs or their equivalent.  LUKASZ STAFINIAK is incredibly cool for putting this together.

[preetjotsingh]

Conference posters in Latex

Got a poster to prepare for an academic conference but don't know where to start? Here, you can use my code as a template (which was based on Shashank Shalgar's poster, which was based on another template which used the baposter class).

These notes might be useful if you've never used baposter class previously (but I assume you have at least a passing familiarity with latex) - 

Structure: Sections or boxes in the poster are headerboxes. You can name them (name=intro) and then use names for adjusting relative positions (above=references, below=definitions).

I compiled it twice: Once with pdflatex and once with ps2pdf. The latter requires the image files to be .eps and (I believe) the former requires (or at least, happily accepts) .png .

If you're on Ubuntu (and most probably on a Mac) you can convert image files using the convert command (> convert a.png a.eps).

Things I found useful:

The above/below parameters in headerbox were really useful in placement and length of boxes -\headerbox{Control cases}{name=models1,column=2, above=references, below=definitions} is an excellent example. It just extended to cover the available space in the poster once I put in those parameters.

Phantom text (which is exactly what it sounds like - text that takes up space but isn't seen) was extremely useful in getting the spacing just right (\phantom{\tiny{xxxxx}}). My Overview andDefinitions boxes have the same height – but that's because I put phantom text in the latter so they both ended at approximately the same line (if you look carefully, you can see that they almost, but not quite, align exactly). 

Many thanks to Dr. Shalgar, the eminent particle physicist, for his guidance and complimentary nespresso.