AI to make smart word associations

Let’s start with a couple of problems
Problem a) I read a lot of news articles and find that a number of words appear close to each other — New next to York, New next to Delhi; However, if I am reading book about history of India — it is unlikely that New will come next to Delhi; in this case Delhi will stand alone. In other words, I am smart enough to understand the context and the relationship between these words. Question is — can my machine learning program make this relationship based on the data that is presented with.
Problem b) My grammar teacher has done a good job of instilling rules in my head — female of a donkey is a jenny (did you know that?). I can determine Jenny is a donkey while reading a text about donkeys but can my machine learning algorithm make that association?
The larger class of problem is how do you understand some class of text — perhaps all novels by Isaac Asimov or the entire wikipedia database and make predictions based on that dataset.
The machine learning algorithm that makes these smart associations is called “Word2Vec”. Word2Vec is the model used to create word embeddings. The model takes each word and maps it to another word in the word space that the model is learning from; eventually a cluster of related words settle down close to each other.
The larger class of problems is called “Word Embeddings”. These are two dimensional neural networks that are used when there a huge number of classes. The NN is able to make semantic relationship between words and produce richer relationships.
Intuition
Word2Vec works with a large data set. Let’s take the example of feeding the entire data set of scientific articles on donkeys to the algorithm. Assume, that this a vocabulary of 10k words. Each of these words, will be represented as input (one-hot encoded) to the Word2Vec algorithm. The training data set will produce a set of weights that determine this relationship. The output is a probability distribution of each of the 10k words. Thus, fed in “jack” (male of a donkey), the output distribution will likely be heavily weighted towards “jenny”.
Chris Mccormick has a great overview of the Skip-gram model for Word2Vec.

Is that horse running? bringing memory to AI with RNNs.

3DayInIceland-8.jpg

The human brain does two functions very well – the first is that it can recognise images very well. The second is that it can detect patterns based on time and make predictions based on those patterns.

The last few months I played around with the first function- — around building image recognition neural networks (CNN)– the ones that help you determine whether a picture is of a dog or human (source code) or another example is detecting faces in a picture (article) or recognising handwritten numbers (article).

For example, we can write a CNN that determines that the above picture is of a horse.

But, if you ask a CNN to tell us if this horse is running or not — it would have a hard time. If you ask a human —  the answer is dependent on a number of things and most on time. If you saw this picture as a series of pictures where the horse was loitering around, you could make the determination that it is likely that the horse is standing around. In that case, we used human memory to solve the problem of determining what the horse is doing.

Recently, I started to dig into the second function of the human brain and see how you can mimic the human brain. To answer a question — how do you introduce an element of time in AI.

The canonical example is that I would like to predict the prices of a stock. Another example is Google Assistant, it needs to understand the context to service a request.

Recurrent Neural Networks (RNNs) and Long Short Term Memory (LSTMs) help you solve problems that have dependencies on time. I have blogged (here and here) about LSTMs previously so lets take RNNs in this blog.

The following picture is called an unfolded model of a RNN.

Recurrent Neural Network

Let’s break this picture down.

Each circle is a feedforward NN (ffnn) which means it is taking input (i), does some calculation and puts out a value (o). The weights calculated by the ffnn are Wi and Wo on the input and output respectively.  NN’s typically take anywhere between 1 to thousands of inputs, thus, i can be in thousands. NNs typically output 1..n outputs as well, thus, o can have that range as well.

So far so good.

Let’s now bring in the notion of time.

RNN’s keep an internal state around (s) and Ws are the weights that are generated for that state. Think of s as the memory component of the RNN.

The way you bring in the memory element along is that you feed the memory from time t as the input to time t+1 and so on. This, is how RNNs are different than standard feed forward networks. The input increases from i to i+s.

Mathematically

s_t = some_function (Wi*i + s_t-1*Ws)

The picture is that of a simple NN repeating itself over time starting with t upto t+2 but really going on to infinity.

The next level of complexity is to stack an RNN on top of another and create a 2 layer RNN. Two layers is the beginning because you can stack an arbitrary number of them.

RNNs-2

This lattice of RNNs then provide the flexibility to process temporal dependent data and make complex predictions.

Inner working of an AI that mimics human memory

In the last blog, I gave an overview of LSTMs (long short term memory) in AI that mimics human memory. I will use this blog to go 2 layers below to draw the building blocks of this technology.

LSTM-1As a reminder, at a 50k level, the building block looks like the image on the left. There is long and short term memory on the left –> some input comes in –> new long and short term memory is output on the right. Plus, an output that determines what the input is.

Let’s open the box called the LSTM NN (neural network). This block is composed of four blocks or gates:

  • The Forget Gate
  • The Learn Gate
  • The Remember Gate
  • The Use Gate

The intuitive understanding of the gates is as follows: When some new input comes in, the system determines what from the long term memory should be forgotten to make space for the new stuff coming in; this is done by the forget gate. Then, the learn gate is used to determine what should be learnt and dropped from the short term memory.

The processed output from these gates is fed to the remember gate which then updates the long term memory; in other words a new long term memory is formed based on the updated short term and the long term memory. Finally, the use gate kicks in and produces a new short term memory and an output.LSTM-2

Going a level deeper:

Learn Gate

The learn gate is broken in two phases: Combine –> Ignore.

  • Combine: In the combine step, the system takes in the short term memory and the input and combines them together. In the example, the output will be Squirrels, Trees and Dog/Wolf (we don’t know yet — see previous blog for context)
  • Ignore: In the second phase, information that isn’t pertinent will be dropped. In the example, the information about trees is dropped because the show was about wild animals.

Forget Gate

The forget gate decides what to keep from the long term memory. In the example, the show is about wild animals but there was input about wild flora, so the forget gate decides it is going to drop information about the flora.

Remember Gate

This gate is very simple. It adds output from the Learn gate and Forget gate to form the new long term memory. In the example, the output will be squirrel, dog/wolf and elephants.

Use Gate

This gate combines the input from the learn gate

Math behind the various gates for mathematically inclined

Learn Gate

Combine phase (output = Nt)

Take the STM from time t-1, take the current event Et and pass them through a tanh function.

Nt = tanh (STM_t-1, Et)

Mathematically Nt = tanh (Wn [STM_t-1, Et] + bn) where Wn and bn are weight and bias vectors.

Then, the output from the combine phase is multiplied by another vectory called i_t that is the ignore factor from the Ignore phase.

Ignore phase (output = i_t)

We create a new neural network that takes the input and STM and apply the sigmoid function on them.

i_t = sigmoid ( Wi [STM_t-1, Et] + bi)

Thus, the output from the Learn gate is:

tanh (Wn [STM_t-1, Et] + bn) * sigmoid ( Wi [STM_t-1, Et] + bi)

Forget Gate

The forget output is calculated by multiplying the long term memory with a forget factor (ft).

The forget factor is calculated using the short term memory and the input.

ft = sigmoid( Wf [STM_t-1, Et] + bf]

Forget output = LTM_t-1 * ft

Remember Gate

The remember gate takes output from the Forget and Learn gates and adds them together.

LTMt = LTM_t-1 * ft + Nt * i_t

Use Gate

The use gate applies a tanh function on the output of the forget gate and multiplies it to a sigmoid of the input and the event.

STMt = tanh (Wu [STM_t-1, Et] + bu) * sigmoid ( Wv [STM_t-1, Et] + bv)

Summary

The four gates mimic a point in time memory system. To truly envision this, think of a lattice of connected cells separated in time. Thus, the memory system will continually evolve and learn over a period of time.

(credit: the math and the example are coming in from the Udacity deep learning coursework)

Mimicking human memory with AI

Memory is a fascinating function of the human brain. Specifically, the interplay of the short term memory and long term memory where both work in conjunction to help humans decide how to respond to the current stimuli is what makes us function in the real world..

Let’s take an example —

I am watching a program on TV and suddenly a picture of a dog/wolf comes up. From the looks of it, I cannot distinguish between the two. What is it – a dog or a wolf?

If the previous image was a squirrel and since squirrels are likely to be in a domestic setting, I could make an assessment that the current image is a dog.

This would be reasonably true, if all I had was my short term memory.

At this point, my long term memory kicks in at this point and tells me that I am watching a show about wild animals. Voila, the obvious answer at that point is that the current image is of a wolf.

LSTMs mimic human memory

A specific branch under Deep Learning in AI called LSTMs (long short term memory) are used to solve problems that have temporal (or time based) dependencies. In other words, LSTMs are used to mimic the human memory to predict outcomes. Unlike another branch in Deep Learning called RNNs (recurrent NNs) which only keep the short term memory around, LSTMs bring in long term memory to bring in high fidelity to their predictions.

The Working of LSTMs

LSTM-1
The NN takes in the long term memory (Elephant), the short term memory (Squirrels, Trees) and the input (Dog/Wolf) and makes the following set of determination:

  • What should it forget? Trees in this case because the show is about wild animals and not trees.
  • What should it learn? There is a Dog/Wolf in addition to the squirrels and trees.
  • What should it predict? The Wolf
  • What should it remember long term? Elephant, Squirrel, Wolf
  • What should it remember short term? Squirrel, Wolf

All the above is done for the current time and the new long/short term memory are fed into the next input that comes at time t+1.

Thus, you can think of the above picture as recurring for every time epoch t.

In the next blog, we will deep dive into the LSTM NN and see how each of the bulleted questions are answered.

Pretty interesting, isn’t it?

(disclaimer: the example used is from the Deep Learning course work on Udacity)

Understanding Recurrent Neural Networks (RNNs)

Neural Networks (NNs) that depend on past history are called Recurrent Neural Networks (RNNs). The technical term is networks that depend on temporal dependencies or dependencies that change based on time are called RNNs.

This class of NN’s are distinct than the ones that, for example, do image recognition which do not have dependencies on time. RNN’s have wider applications because most applications have dependencies that depend on time. A key challenge in RNNs is the vanishing gradient problem in which the contribution of information or memory (in the next paragraph) decays geometrically over time.

rnn-cell
Basic Cell in a RNN

The basic idea is that you take a feed forward NN (FFNN) and introduce internal memory state that takes the output from the internal training layer. Thus, our FFNN now remembers what happened before.  For completeness, prediction can be 1..n.

The next step is to chain each of these cells together.

Thus, a RNN is a combination of multiple such cells where multiple inputs are fed into different cells (think prediction of next word is dependent on the last few words), each cell has it’s own memory coming in from its previous iteration and each cell goes ahead and makes its own prediction.

rnns.png
RNNs

The beauty of RNNs is that they can be stacked as lego blocks. To imagine this, think about the above picture as 1 RNN lego block and make the prediction layer feed into another RNN block stacked above it.

Applications

There are some interesting use cases for RNNs:

  • Sentiment analysis
  • Speech recognition
  • Time series prediction
  • Natural language processing
  • Gesture Recognition

Amazon Lex provides a framework to build conversational interfaces using voice and text with .

How do they detect faces in pictures?

 

06 Mar 2018

face-detection

I was fascinated when Facebook launched the feature where it put a box around a human head (and a bit creeped out when it started suggesting the name of the human next to the box). I always wondered how they did it and filed it under machine-learning magic-ery. Now, I know how they do it so let me peel back the curtain.

There are two distinct problem domains in the feature

  • Find the human – we will use this blog lifting the curtain behind the magic.
  • Label the human – this is supervised machine learning and we will ignore this problem in the blog.

The “Find the human” problem is solved through something called “Haar Cascade Classifiers” – detailed article for brilliant humans and the rest follow along in this blog :-).

The underlying building block is a Classifier but lets drop the terminology and use airport security as a metaphor to explain the process.

Think of face detection solution as a airport security problem where a series of security guards each do a specialised task. The guard at the airport entrance is responsible to ensure that there is no suspicious car loitering around the airport. The guard at the security gate is responsible for letting ones with a valid id and a boarding ticket. The person behind the scanner is responsible to weed out any harmful objects in the handbag. The person behind the scanning machine ensures that no person gets in with a gun. The explosives security person uses a specialised explosive detector paper and puts in the machine to find out if hidden explosives are carried by the person under consideration.

Each of this security guard is a Classifier and classifies a particular threat. When each is put together in a series, we get a Cascade of Classifiers. Each building on the work of the other. Each and everyone of them has to perform their specialised task for a successful outcome. The successful outcome in this case is that a person was allowed into the airport lounge and can board his/her plane. Each of the classifier goes through a great deal of specialised training for it to perform their task. Makes sense?

So lets apply this metaphor to face detection machine-learning algorithm. In ML, each classifier focusses on a special feature within a picture. The basic classifier tells something as simple as “this is a horizontal edge” or “this is a vertical edge” where edge detection is a feature. This classifier feeds into another one that perhaps says “this is a square” and so on so forth. Eventually, you get to a classifier that tells you “this is a bridge of the nose” or “these are eyes”. Each classifier has been fed 100s of thousands of images that are either positive (human in the picture) or negative (no human in the picture) for it to learn to correctly classify the pictures.

So how many such features are there? Turns out a whole lot. For a typical 24×24 pixel, there are 160k+ features. The Haar in the “Haar based classifier” is a mathematical function that optimises this algorithm and reduces the number of features to look out for to about 6k.

Now it turns out that applying this knowledge into our programs is a lot simpler than the entire training process because opencv.org provides a python package called opencv to detect these pictures.

I ran a short function to detect humans in about 100 pictures with humans and ended up with a 100% detection rate – not bad at all. Running it over 100 dog pictures ended up returning a 89% accuracy rate. Thus, 11% of dogs were categorised as humans and if you know me – I think that is fair because some dogs are like humans :-).

My github repo here if you want to see the code, although you can find it on the Haar based Classifier link as well.

Intuitive understanding of a softmax function in a neural network

16 Feb 2018

A softmax function squashes its inputs to be between 0 and 1 and also normalises them so that the sum is equal to 1.

Let’s take a problem where we have to classify between three classes.

Softmax is used to classify for greater than 2 classes for less than 3, use a sigmoid function. So, we need to tell if an animal is a duck, a dog or a cat. Our Neural Network linear function looks a picture of an animal and comes back with say a score 2 (duck), 1(dog) and -1(cat). The next step is to convert the scores into a probabilities whether the picture is a duck, dog or a cat.

This is where Softmax comes in. The softmax function takes independent scores and comes back with probabilities such that the sum of these probabilities is equal to 1. Thus, we can classify a picture against these classes relative to each other.

The formula is

P(duck)=eded+eo+ecP(duck)=eded+eo+ec

where d is duck, o is dOg and c is cat in the formula. Our end result will look something like:

P(duck) = 0.70

P(dog) = 0.26

P(cat) = 0.03

Thus, we have taken a matrix of scores and converted them into probability distributions

[211][21−1]

Apply softmax to produce

⎡⎣⎢⎢0.70.260.03⎤⎦⎥⎥[0.70.260.03]

Thus, to summarise, a softmax function squashes its inputs called logits to be between 0 and 1 and also normalises them so that the sum is equal to 1.

Understanding cross entropy in neural networks

Let’s say that there are a bunch of events and a bunch of probabilities, cross entropy predicts how likely are those events likely to happen based on the probabilities.

A high cross entropy means that an event is unlikely to happen while a low event indicates that the event will happen.

In a neural network (NN), an error function is used to classify data into appropriate classifications. So in well performing NN the goal is to minimise the output of the error function. Another way to look at this minimization is that we should be increasing the probabilities that these points are classified right. Thus, we are aiming to get the probabilities of the events to get higher.

Let’s take an example – where we have 3 doors and if we open the door, we are likely to either find a duck, dog or a cat behind each door. These events are independent to each other, thus all 3 doors can have a dog behind them.

Let’s say the most likely probability is to find the following behind each doors:

Door 1 = P(duck) = 0.70

Door 2 = P(dog) = 0.80

Door 3 = P(cat) = 0.97

Thus, the likely hood of finding a duck, a dog and a cat is

0.70.80.97=0.60.7∗0.8∗0.97=0.6

Since multiplication of various events with numbers less that 1 could be very small, we typically use the logarithm function to add them up and that is the formula for Cross entropy

Crossentropy=log(0.7)log(0.8)log(0.9)Crossentropy=−log(0.7)−log(0.8)−log(0.9)
Crossentropy=(0.35566)(0.2231)(0.1053)Crossentropy=−(−0.35566)−(−0.2231)−(−0.1053)
Crossentropy=0.685Crossentropy=0.685

This low cross entropy number indicates that the likelihood that these events (of a duck, dog, cat ) showing up behind the doors is high. To implement this in tensorflow, you’d do the following:

“`python softmax_data = [0.7, 0.2, 0.1] one_hot_data = [1.0, 0.0, 0.0] softmax = tf.placeholder(tf.float32) one_hot = tf.placeholder(tf.float32) cross_entropy = -tf.reduce_sum(tf.multiply(one_hot, tf.log(softmax))) “`

Understanding neural networks – a dog lovers primer

03 Mar 2017

UntitledLet’s look at a problem: I am a dog lover and I subscribe to Instagram where I get a stream of images of toasters, birds, cats and dogs. While these images are exciting (who doesn’t like toasters :-)), what I want to do, is automatically save images of dogs to an account on the cloud. The question is, what kind of program do I need to write that tags all dog images to feed my cloud database of awesome-dog-images.

A neural network to the rescue!

A neural network is a decision engine. Its job is to look at in-coming data and make a decision about the data. Typically, a neural network uses logistic regression to make these decisions. I covered regressions here – logistic regression classifies data into a yes/no class of answers.

Building a neural network is like training a dog.

  • You train the dog to obey a command
  • Analyse if the dog is behaving right in all field conditions and
  • Provide the appropriate feedback to fix any problems

“Sit boy” – Training the neural network

To get something useful from a neural network – you need to train it. To do this you take the existing set and split into the data you train with and the data you test against.

Training the data

In the data here, I have two regression lines that neatly separates the images. In neural network parlance, each quadrant is a decision node that outputs yes/no if it identifies the data right. Each node is called a perceptron or neuron. Each one looks at input data and decides how to categorise that data. In the example above, the input either passes a threshold for dogs, cats, birds and toasters and each neuron answers a yes or no.
neural-network-dog-classifier

You write a function called an activation function to make the decision. Typically, an activation function uses a heaviside activation function i.e. the function returns false if the number is < 0 and returns true if a number is greater than 0. Each function takes a weight (w) that determines how important the function is. This is really important – the weights determine if a network is going to be successful. For example as I am looking for a dog, the activation function for dogs will have a heavier value than for a cat. If on the other hand, I was looking to classify toasters, the weight for toaster would be greater than that for mammals and birds. The output of these functions will go through an aggregator function that determines the final output. The activation function is the key as it is this function that determines what the answer is going to be.

The network above has only forward propagation as in each neuron makes a decision and pushes the answer forward. Thus, once you have trained the network and the network makes errors, it will continue making the error forever. What makes this picture interesting and useful is if you can find the error between the right value and the error and feed it back to the network. This is called back propagation.

Is the dog doing the right thing: Analysing the output

Did the dog do the right thing? A dog sleeping on the sofa while I gave it a sit command is an epic fail. Isn’t it?

In neural networks, you take your test data and feed it through the network to see the output. The good thing with the test data is that we already know the answer. You compare the result from the network to the test data and determine the delta. The delta tells you how off you are from the right answer. We will get into more details in another blog perhaps.

Provide feedback to the dog to fix issues: Provide feedback to the network

Once you have the delta from the network, you feed it back into the network. This process is called back-propagation. The way to think about back-propagation is that it is a mirror of the neural network, where instead of starting from the inputs you start with the error instead. You start with the derived answer and the actual answer, calculate the delta for the error and start updating the weights on the way back. You do so for each record in the data set. You typically use gradient descent to find the right weights on the way back.

To sum up – weights are what helps determine the right answer but you don’t get the right weights when you only move in one direction, so you find the error and fix the weights back and voila you have a neural network that has learnt.

Congratulations! You have now successfully trained your dog – welcome to a great life ahead.