DEV Community: Nikitha Srikanth

A Dash of LIME

Nikitha Srikanth — Mon, 14 Sep 2020 14:35:10 +0000

If you were put inside a completely black box, what would it feel like? Well, for one thing, it would be completely dark. You would have no way of looking outside the box, and most importantly, no one would be able to see you from outside.

Now assume there is one such random box. Let's say this box can predict the future. So based on that, it gives you suggestions like whether you should buy that car you've always wanted, or whether learning Spanish will help you in the future. You have no idea what information the box uses to come up with the prediction. So should you trust it? If you believe in tarot cards and magic 8-balls, this isn't probably that different. But you would be better off knowing why the model came up with these suggestions in the first place since you're trusting it with making decisions about your life.

Magic 8-ball: Always ask again to be sure
 
Let's look at another scenario where 100 people use one random black box each to navigate in the dark. 99 of these people safely reach their destination with the black box shouting out directions in which they should move. But one person falls off the edge of a cliff. Is this a trustworthy box? It did do its job perfectly 99% of the time. But ideally, you would like to know why the box made a mistake and fix it. But you can't see what is inside a black box remember? Well, the next obvious question is, why would we use a shady black box then?
 
In scientific terms, a black box is anything that takes in some input and gives out a result, with no explanation whatsoever as to how it arrived at it.
 

 
This is also how most machine learning models work, especially neural networks, and we are using these shady black boxes everywhere. You give these models lots of data using which models learn some underlying patterns and give you some output. With deep neural networks, there are way too many neurons and layers to fully understand what is happening inside. Maybe you get extremely high accuracies in a classification task. But you never know what it has learnt to perform this classification. Good accuracy can come out of learning the wrong patterns and from overfitting as well.
 
A great example is a model that identified whether an image had a dog or a wolf. It would get it right most of the time, giving a false sense of accuracy that it had learnt the right things. But with tools that help understand what the black box model does, it was seen that the model was classifying based on the background and not the animal. The model noticed that most images of wolves had snow in the background. So what it was actually classifying was “snow" and "no snow”.
 

Left: Dogs, Right: Wolves (There is snow in the background for wolves and no snow for dogs, which is what the model caught on)

It is better to have a model that performs badly due to genuine confusion. This could look like a model wrongly classifying a human in a dog costume as a dog (This is understandable because some humans can pull off some great impersonations).

Left: Person dressed as a dog, Right: Dog (Can be confusing sometimes)

The point here is that the model is classifying wrongly, but for the right reasons. It is better to have a model you can trust even if it gets things wrong sometimes, because you know what it is learning, and you can make changes accordingly to learn better.
 
It is important now more than ever for humans to be able to interpret these models. We need to move towards making these boxes transparent because
 

AI is being used to make important decisions like diagnosing deadly diseases, pick who gets hired, who gets a loan, who gets parole, where you should invest. We can't afford to learn the wrong things and must be able to trust the model.
Wrong decisions could perpetuate and reinforce stereotypes because the model may learn patterns that exist due to biases in society.

So blindly trusting a model is a bad idea. Now, what can we do if we can't look in the box?
In fact, you can do a bunch of things. I want to talk about one thing in particular (That was a lot of unnecessary examples to get to the point).
 
This is where we add a dash of LIME to our lives. In the paper “Why Should I Trust You? Explaining the Predictions of Any Classifier", the authors propose a tool called LIME - Local Interpretable Model-Agnostic Explanations. This helps us explain the actions of a model to a certain extent by building a model over a model.
LIME exploits the fact that it is easier to explain a simple surrogate model than to explain the actual complex model.
 
With a black box model at hand, if you want to explain the model's predictions for a particular observation, we make some changes to this observation. In an image, this would look like greying out some parts.

Left: Original Image, Right: Image with different regions that can be greyed out. Sources: Marco Tulio Ribeiro

So a new set of samples similar to the observation are generated with some parts removed in each. The model's predictions are then seen for this generated set of samples. Using these predictions, the different portions of the image are weighted. So if an image of a tree frog is classified correctly when the portion of its head is present but wrongly when most of the head is greyed out, it means that the head portion must be weighted more.

How LIME generates explanations for the model's predictions with greying out different parts of the image and seeing how prediction varies. Sources: Marco Tulio Ribeiro
 

A simple linear model is learned with these weights, and this approximates well in the vicinity of the observation in consideration. The parts of the observation that are weighted more are displayed, and hence with human intuition, we can see if this makes sense.
 
Maybe you see with LIME that a classifier for emails of atheist groups and Christian groups is learning that the word god is an important factor for classification. But you also see that it is the word god in atheist emails that is causing the classification. This is because these emails talk about god in the context that god doesnt exist. But all the model is learning is the presence of the word god in the email, and not in the context. It is learning If(god is present): classify atheist, which we as humans can immediately identify as the wrong basis for classification. We can then make our training samples more diverse and make the necessary changes so our model picks up on the right things.
 
To summarise, let’s break apart LIME - “Local Interpretable Model-Agnostic Explanations”
from the bottom.
Explanations refer to the fact that we can explain the actions of our model.
 
Model-Agnostic means that LIME looks at every model as a black box and is indifferent to what kind of model you use.
 
Interpretable means that the explanations provided are simple for anyone to understand.
Local refers to LIME’s explanation of the prediction of a model in the vicinity or locality of a particular sample with the help of a simple model in that region.
 
Seems perfect, but there is still a lot of work to be done. It is useful when you're working with patterns that align with human intuition in texts and images. When you're looking at things like protein sequences, it is not very easy to understand the explanations. But this is still a great step towards model transparency and interpretability. LIME for me seems to be one of the greatest resources out there and I would recommend it to everyone.

The Avengers and the Knapsack Problem

Nikitha Srikanth — Wed, 26 Aug 2020 17:16:49 +0000

The Knapsack Problem is a general optimisation problem. The solution to this problem has something in it for everyone. Before we see how it can be useful, let's break apart the word 'knapsack'.

This word comes from German 'knap', which means 'bite', and 'sack', meaning 'bag'.
The word 'knapper' means 'to eat', and therefore knapsacks are generally eating bags. While a monstrous bag that bites comes to mind, this was merely a name given to a bag used by soldiers to store food. But this slowly evolved to refer to an everyday carrier for ordinary things. But it wasn't soon before the word began to be replaced by the likes of 'backpacks', and one of the only places it stuck, was the knapsack problem.

So what is the knapsack problem? It is a problem where one has to try and fit as many things of value into a knapsack without overloading it. This is generally expressed as a set of objects, each having a particular value and a weight. Objects must be chosen from this set, such that the total value of chosen objects is maximum. But there is a limit on the total weight of the objects. The knapsack problem thus refers to any problem that applies a constraint to you maximising the value of objects. Since I did mention that there's something in it for everyone, let's look at a few ways it can be used:

You’re an art thief. You need to break into a museum. Now you can use one sack to carry all the valuable pieces you've stolen, because you can't really carry more than one while dodging security systems and booby traps, and then jumping over roofs, trying to escape. So you need to figure out how to pick as many valuable items as possible but also making sure you only take as much as your 'knapsack' can carry. Before you carry out the heist, you can sit at home, carefully run the knapsack algorithm on the various pieces of art in the museum, and you'll be guaranteed that you'd choose the most valuable loot among all other criminals who attempt to rob the same museum, with similar sacks. Clearly, this is a bad example, so let's just move on to the next.

You are now a student writing a test. You have 20 questions out of which you choose which ones to answer while making sure that you've attempted for a total of 100 marks. So you now assign a value depending on how easy a question is for you. The weight becomes the maximum marks for that question. Now using these as the parameters for solving the knapsack problem, you can come up with a set of questions that will be the easiest for you, while also making it highly probable that you'll score a complete 100. This could be extremely useful if there are too many questions to choose from with a marks scheme that's equally diverse. But most tests aren't going to be testing you for your knapsack problem-solving skills. If only our tests were this 'meta'. Moving on to slightly better examples.

You could be someone who wants to chart a new diet plan for whatever reason. Anyway, let's assume you want to choose the tastiest dishes for your diet plan, while also making sure you're consuming the least calories. Again the knapsack problem is your go-to approach. Or you could visit a dietician.

Now some of the most important applications of this problem would be deciding where to invest, how to maximise profits, how to make the most out of resources while also reducing waste, and also how to select the perfect team. Yes so hypothetically, if you could buy superheroes and build your team like the Avengers, you could use the knapsack problem to maximise strength, while under a budget. I realised I could implement this when Entertainment Weekly released this very controversial post, asking people who they'd pick with a budget of $15.

It's pretty evident that there is a huge problem with the prices. Scarlet Witch cannot possibly cost less than $15 alone because she’s clearly the most powerful Avenger. I’m not the only one who has issues with this categorisation. Here’s a link to see how crazy the internet is going. Anyway, I modified costs wherever I wasn’t satisfied.

So my ‘knapsack’ has a limit of $15, and I have ‘weights’ (costs) of each ‘item’ (avenger).
The values I assigned to each of them, was a number from 1 to 25, representing how valuable and powerful the avenger seems to me (25 being the highest).
So now I have weights and values for all my ‘items’.

How do we go about doing this? This is a classic 0/1 knapsack problem, where 0/1 means you either take an item or drop it. So this is different from a fractional knapsack problem, where I’m allowed to take only, say, Thor’s eye, and not necessarily him as a whole.
Therefore, 0/1 knapsack means I take an avenger, or I don’t, without being allowed to take parts of the avenger (Hmm, I wonder what happened to Thor’s eye).
I used two techniques- The greedy approach and the dynamic programming approach.
First, let’s look at the greedy approach. As its name suggests, it is a method of choosing the best item at every point, and continue till you’ve taken everything. So for example, if you want to choose items to fit in your knapsack, you sort the items available based on what ‘best’ means to you, and put things into the knapsack in the order of decreasing priority, until it is full.
Let’s look at some ways of defining what’s 'best'.
Value - If you think the higher the value, the better the object, you would sort the objects by value. So you would then choose the highest value object from the set, then the next highest value from the remaining, and so on, until you can no longer fit anything in your knapsack. Obviously, it would be dumb to choose the objects of lowest value first.

Weight - If you think that choosing the lightest object is the best choice, you would sort the objects in increasing order of weight. So at every point, your best choice would be the object with the lightest weight. You would thus continue picking objects in this manner until the knapsack is full. Again, if you choose one heavy object and fill the knapsack right in the beginning, it would be a dumb choice. So here, we choose the lightest items first.

Density - This is a way of defining ‘best’ by taking into account both weight and value. Ideally, you would want high value and low weights to fit as much value as you can into the knapsack. You'd sort the objects according to value divided by weight (or density), and pick from highest density to lowest. Since an increase in the numerator and a decrease in the denominator increases the magnitude of density, high value and low weight imply high density. So it would make no sense to pick the lowest density first because then you’d be picking the worst of both worlds (low value and high weight).

Each of these techniques gives you a different total value because each method would end up with you having the best according to that metric. However, the knapsack problem is generally defined as maximising value while subject to a maximum weight constraint. The problem with the greedy technique is also that it chooses local optimums, and will not necessarily give you the maximum value. Assume you’re greedily picking objects by value. We see that Ironman, Captain Marvel, and Scarlet Witch have a value of 10. So picking by value, the greedy algorithm will pick all of them. But since each of them cost $5, we will also use up our budget of $15. Our team has a total value of 30.

However, if we dropped Captain Marvel, we’d be left with $5, and a total value of 20. But, we could spend $1 on Loki and $4 on Doctor strange, adding a 9+8.5 to the total value. So now we have 37.5, which is a greater value than the previously obtained 30.

We need a better approach. This is where dynamic programming comes in.
The name for this technique was randomly chosen by the person who developed it, because he wanted it to sound non-mathematic, and also so that people wouldn’t know what he was talking about. In this approach, we make use of the solutions to sub-problems to develop the overall solution.
Let’s assume we can use only objects 1,2 out of a given set of objects. Let’s also assume that the maximum weight we can use is 6. The weights and values of each of these two objects are shown below.

So now we see that the maximum total value for the given objects, subject to maximum weight constraint 6, is 10, which is obtained by adding object 1 to the knapsack.

Now assume we now have objects 1,2,3.

The maximum weight is still 6. If the weight of object 3 is greater than 6, we can’t add it to our ‘knapsack’. We see that in this case, the weight of object 3, is lesser than 6. We have two choices. We could use 3 in the knapsack, or we could drop it.

Case 1: We use object 3

If we choose object 3 in the knapsack, the remaining weight is 4 (weight of object 3), subtracted from maximum capacity, which is 6. Thus the remaining capacity of the knapsack is now 2.
Now that we’ve added object 3 already, we have objects 1,2 to choose from and a remaining capacity of 2. So we again find the maximum value that can be obtained using objects 1,2 and a maximum capacity of 2. This is the same as the first case where we had only objects 1 and 2. However, this time, since our maximum capacity is 2, we cannot use object 1. Thus, the maximum value obtained from objects 1 and 2, subject to maximum weight 2, is 8 (value of object 2). We can add object 2 to the knapsack. So 8 + 6 (value of object 3)=14, is the total value in the knapsack.

Case 2: We don't use object 3

If we don’t use 3, the maximum value is the same as the value obtained by choosing from objects 1,2, subject to maximum weight 6. We already did this in the beginning, and the maximum value is 10.
Since we already know the solution for using objects 1,2 only, and we're trying to figure out if adding object 3 can give us a selection of objects with a higher total value, we take the maximum of the above two cases as the solution. Hence, 14 is the maximum value that can be obtained by using objects 1,2,3, with a knapsack of maximum capacity 6.

This might seem like overkill with just 3 objects at hand. However, for a problem that involves larger data sizes, like choosing from 25 superheroes, this approach can be very efficient. We start with solutions for a small set of objects and go on adding objects one by one to it, and obtain the solution at each stage until we build up towards all the objects.

So we can use solutions to subproblems to compute the optimum solution for the original problem. If there is a table from which we can look up solutions to subproblems, we can easily solve the bigger problem by building this table from the bottom up. Let's look at the table for the above set of 3 items.

So this table has solutions for all subproblems, starting from no items and maximum weight 0, to all items, maximum weight 6. Row number i corresponds to having items 1 to i available to us. Column no j corresponds to a maximum weight of j. Thus cell i,j corresponds to the maximum value obtained with objects 1 to i, with weight constraint j. Thus the bottom rightmost cell gives us the final maximum value.

Using this approach, I was able to obtain a maximum value of 51.5 for my team of avengers. To know which heroes were chosen, we backtrack on the table.
For simplicity, let’s look at another table for a few objects, whose weights and values are mentioned on the left side of the table below.

Now we see that the value at (4,7) is 9 and the value at (3,7) is also 9. This means that object 4 was not included, as the value remains the same as when 3 objects are used, even after having 4 objects available to us. Now we see value at (2,7) is not the same as (3,7). This means that object 3 is present in the knapsack, as the maximum value changed when the set of objects available changed from 1,2 to 1,2,3. Since we’ve included object 3 in the knapsack. The remaining capacity of the knapsack is 4(weight of object 3), subtracted from maximum weight 7. So the remaining capacity becomes 3. So we move to (2,3). (2,3) and (1,3) are not the same. Hence item 2 is also in the knapsack. So now the remaining capacity is 3 minus 3 (the weight of object 2) which is 0. Hence the knapsack is full, and we reach column 0.
The elements in the knapsack are object 3 and object 2. The Avengers dynamic programming table contained 26 rows and 16 columns and it is highly impractical to try and explain a large table when you can explain a smaller table the same.

Similarly, I was able to see that my team consisted of Winter Soldier, Hawkeye, Vision, Loki, Gamora, Black Widow, and Ironman. Sounds like a good team.

The code I used is available here. Now I just have to sit and hope these heroes are for sale.