
Working with Real DataMachine Learning is about inferencing values from data. Studying about machine learning, therefore, comes out best by experimenting with real-world data, not artificial datasets. Fortunately, there are thousands of open datasets to choose from, ranging across all sorts of domains. Here are a few places we can look at:
Approximation Theory
The purpose of studying Approximation Theory is to better understand the Universal Approximation Theorem, which defines the limits (or unbounded potential) of AI and Machine Learning on what Neural Networks can learn to solve real-life problems. Approximation Theory is the foundation of Machine Learning and its usefulness is brought to life by the advancement of contemporary computing power. For example, Approximation Theory says an approximated function exists by Math theorem but does not indicate how to reach that approximation. Artificial Neural Network, trained by Big Data, reaches that optimal function. Approximation theory is the proof of why AI or Machine Learning works.
K-Armed Bandit Problem: Reinforcement Learning as an Example of ApproximationConsider the following learning problem. We are faced repeatedly with a choice among different options, or actions. After each choice we receive a numerical reward chosen from a stationary probability distribution that depends on the action we selected. Our objective is to maximize the expected total reward over some time period, for example, over 1000 action selections, or time steps. This is the original form of the -armed bandit problem
Mathematically, each of the actions has an expected or mean reward given that one action is selected; let us call this the value of that action. We denote the action selected on time step as and the corresponding reward as , The value of an arbitrary action , denoted , is the expected reward given that is selected:
If we know the value of each action, then it would be trivial to solve the -armed bandit problem: we would always select the action with the highest value. We do not know, however, the action values with certainly in reality, although we may have estimates. We denote the estimated value of action at time step as . We would like to be close to .
If we maintain estimates of the action values, then at any time step there is at least one action whose estimated value is greatest. We call these the greedy actions. When we select one of these actions, we say that we are exploiting our current knowledge of the values of the actions. If instead we select one of the non-greedy actions, then we say we are exploring, because this enables us to improve our estimate of the non-greedy action’s value. Exploitation is the right thing to do to maximize the expected reward on the one step, but exploration may produce the greater total reward in the long run.
Given that exploring and exploiting is not possible in any single action, systematic methods are used to balance the exploration and exploitation. This is the basic idea behind reinforcement learning.
Defining Machine Learning
Machine Learning addresses the question of how to build computer programs that improve their performance at some task through experience.
Definition of LearningA computer program is said to learn from experience/data with respect to some class of tasks and performance measure , it its performance at tasks in , as measured by , improves with experience .
The problem of inducing general functions from specific training examples is central to learning.
Machine Learning v.s. Data MiningMachine Learning and Data Mining often employ the same methods and overlap significantly, but while machine learning focuses on prediction, based on known properties learned from the training data, data mining focuses on the discovery of (previously) unknown properties in the data (this is the analysis step of knowledge discovery in databases)
There are so many different types of machine learning systems that it is useful to classify them in broad categories, based on the following criteria:
- How they are supervised during training (supervised, unsupervised, semi-supervised, self-supervised, and others)
- Whether or not they can learn incrementally on the fly (online v.s. batch learning)
- Whether they work by simply comparing new data points to known data points, or instead by detecting patterns in the training data and building a predictive model, much like scientists do ( instance-based v.s. model-based learning)
Supervised, Unsupervised, Semi-Supervised, Self-Supervised, Reinforcement Learning
Machine learning systems can be classified according to the amount and type of supervision they get during training. The main categories are
- Supervised learning: the training set we feed to the algorithm includes the desired solutions, called labels. A typical supervised learning task is classification, such as spam detector in email
- Unsupervised learning: the training data is unlabeled. Clustering and 2D/3D Visualization are examples.
- Semi-supervised learning: when labeling data is time-consuming and we end up having some labeled instances and some unlabeled, simi-supervised learning can deal with this situation.
- Self-supervised learning: generate a fully labeled dataset from a fully unlabeled one
- Reinforcement learning: the learning system, called an agent in this context, can observe the environment, select and perform actions, and get rewards or penalties in return. It must then learn by itself what is the best strategy, called a policy, to get the most reward over time. A policy defines what action the agent should choose when it is in a given situation.
Online v.s. Batch Learning
Batch learning
In batch learning, the system is trained using all the available data. This will generally take a lot of time and computing resources, so it is typically done offline. First the system is trained, and then it is launched into production and runs without learning anymore; it just applies what it has learned. This is called offline learning.
The batch learning can be automated fairly easily when it needs a new round of training with new data:
Practical Batch LearningAutomated batch learning is simple and often works fine, but
- training using the full set of data can take many hours, so we would typically train a new system only every 24 hours or even just weekly. If our system needs to adapt to rapidly changing data (e.g., to predict stock prices), then we need a more reactive solution.
- training on the full set of data requires a lot of computing resources (CPU, memory space, disk space, disk I/O, network I/O, etc.). If we have a lot of data and we automate your system to train from scratch every day, it will end up costing us a lot of money. If the amount of data is huge, it may even be impossible to use a batch learning algorithm.
- if our system needs to be able to learn autonomously and it has limited resources (e.g., a smartphone application or a rover on Mars), then carrying around large amounts of training data and taking up a lot of resources to train for hours every day is a showstopper.
A model’s performance tends to decay slowly over time, simply because the world continues to evolve while the model remains unchanged. This phenomenon is often called model rot or data drift ⚠️. The solution is to regularly retrain the model on up-to-date data. How often we need to do that depends on the use case
Online Learning
In online learning, we train the system incrementally by feeding it data instances sequentially, either individually or in small groups called mini-batches. Each learning step is fast and cheap, so the system can learn about new data on the fly, as it arrives
One important parameter of online learning systems is how fast they should adapt to changing data: this is called the learning rate (not to be confused with learning rate as a hyperparameter). If we set a high learning rate, then our system will rapidly adapt to new data, but it will also tend to quickly forget the old data (for example, a spam filter would then flag only the latest kinds of spam). Conversely, if we set a low learning rate, the system will have more inertia; that is, it will learn more slowly, but it will also be less sensitive to noise in the new data or to sequences of nonrepresentative data points (outliers).
Practical Online LearningA big challenge with online learning is that if bad data is fed to the system, the system’s performance will decline, possibly quickly. To reduce this risk, we need to monitor our system closely and promptly switch learning off (and possibly revert to a previously working state) if we detect a drop in performance. We may also want to monitor the input data and react to abnormal data; for example, using an anomaly detection algorithm
Instance-Based v.s. Model-Based Learning
One more way to categorize machine learning systems is by how they generalize. Most machine learning tasks are about making predictions. This means that given a number of training examples, the system needs to be able to make good predictions for (generalize to) examples it has never seen before. Having a good performance measure on the training data is good, but insufficient; the true goal is to perform well on new instances.
There are 2 main approaches to generalization:
Instance-Based Learning
Possibly the most trivial form of learning is simply to learn by heart. A spam email detection would measure the similarity between two emails. A (very basic) similarity measure between two emails could be to count the number of words they have in common. The system would flag an email as spam if it has many words in common with a known spam email.
This is called instance-based learning: the system learns the examples by heart, then generalizes to new cases by using a similarity measure to compare them to the learned examples (or a subset of them).
Model-Based Learning
Another way to generalize from a set of examples is to build a model of these examples and then use that model to make predictions. This is called model-based learning Explore in Colab Explore in Kaggle
Main Challenges of Machine Learning
Insufficient Quantity of Training Data
It takes a lot of data for most machine learning algorithms to work properly. Even for very simple problems we typically need thousands of examples, and for complex problems such as image or speech recognition we may need millions of examples.
The Unreasonable Effectiveness of DataIn a famous paper published in 2001, Microsoft researchers Michele Banko and Eric Brill showed that very different machine learning algorithms, including fairly simple ones, performed almost identically well on a complex problem of natural language disambiguation once they were given enough data
As the authors put it, “these results suggest that we may want to reconsider the trade-off between spending time and money on algorithm development versus spending it on corpus development”.
The idea that data matters more than algorithms for complex problems was further popularized by Peter Norvig et al. in a paper titled “The Unreasonable Effectiveness of Data”, published in 2009.
Nonrepresentative Training Data
Explore in Colab Explore in Kaggle
In order to generalize well, it is crucial that our training data be representative of the new cases we want to generalize to. This is true whether we use instance-based learning or model-based learning and is often harder than it sounds: if the sample is too small, we will have sampling noise (i.e., non-representative data as a result of chance), but even very large samples can be non-representative if the sampling method is flawed. This is called sampling bias.
Overfitting the Training Data
Explore in Colab Explore in Kaggle
Say we are visiting a foreign country and the taxi driver rips us off. We might be tempted to say that all taxi drivers in that country are thieves. Overgeneralizing is something that we humans do all too often, and unfortunately machines can fall into the same trap if we are not careful. In machine learning this is called overfitting: it means that the model performs well on the training data, but it does not generalize well. See an accompanying Jupyter notebook example that illustrate such phenomenon and its possible solutions
Underfitting the Training Data
Underfitting is the opposite of overfitting: it occurs when our model is too simple to learn the underlying structure of the data. For example, a linear model of life satisfaction is prone to underfit; reality is just more complex than the model, so its predictions are bound to be inaccurate, even on the training examples.
Here are the main options for fixing this problem:
- Select a more powerful model, with more parameters.
- Feed better features to the learning algorithm (Feature Engineering).
- Reduce the constraints on the model
Testing and Validating
The only way to know how well a model will generalize to new cases is to actually try it out on new cases. One way to do that is to split our data into two sets:
- the 1️⃣ training set, and
- the 2️⃣ test set
As these names imply, we train our model using the training set, and we test it using the test set. The error rate on new cases is called the generalization error (or out-of-sample error), and by evaluating the model on the test set, we get an estimate of this error. This value tells us how well the model will perform on instances it has never seen before. If the training error is low but the generalization error is high, it means that the model is overfitting the training data for example.
TIPIt is common to use 80% of the data for training and hold out 20% for testing. However, this depends on the size of the dataset: if it contains 10 million instances, then holding out 1% means the test set will contain 100,000 instances, probably more than enough to get a good estimate of the generalization error.
In another situation, suppose we are hesitating between 2 candidate models. How do we decide between them? One option is to train both and compare how well they generalize using the test set. Suppose further that the linear model generalizes better, but we want to apply some regularization to avoid overfitting. The question is, how do we choose the value of the regularization hyperparameter? One option is to train 100 different models using 100 different values for this hyperparameter. Finally we launch the model with the best hyperparameter value which produces the smallest generalization error of 5% into production, but unfortunately it does not perform as well as expected and produces 15% errors. What just happened?
The problem is that we measured the generalization error multiple times on the test set, and we adapted the model and hyperparameters to produce the best model for that particular set. This means the model is unlikely to perform as well on new data. A common solution to this problem is called holdout validation: simply hold out part of the training set to evaluate several candidate models and select the best one. The new held-out set is called the 3️⃣ validation set (or the development set, or dev set). The steps are:
- train multiple models with various hyperparameters on the reduced training set (i.e., the full training set minus the validation set)
- select the model that performs best on the validation set.
- train the best model on the full training set (including the validation set), which gives us the final model.
- evaluate this final model on the test set to get an estimate of the generalization error
Machine Learning Project Checklist
As a well-organized data scientist, the first thing we should do before any serious business project is to pull out our machine learning project checklist which can guide us through our machine learning projects in 8 main steps:
TIPThere is a complete end-to-end notebook project that demonstrate this process - Explore in Colab Explore in Kaggle
-
Document everything along the way
-
Frame the problem and look at the bit picture
- Define the objective in business terms
- How will the solution be used?
- What are the current solutions/workarounds (if any)?
- How should this problem to framed (i.e. supervised/unsupervised, online/offline, etc.)?
- How should performance be measured
- Is the performance measure aligned with business objective?
- What would be the minimum performance needed to reach the business objective?
- What are comparable problems? Can we reuse experience or tools?
- Is human expertise available?
- How would we solve the problem manually?
- List the assumptions we or others have made so far
- Verify assumptions if possible
-
Get the data
TIP
Automate as much as possible so we can get fresh data easily
-
Explore the data to gain insights
-
Prepare the data to better expose the underlying data patterns to machine learning algorithms
-
Explore many different models and shortlist the best ones
-
Fine-tune our models and combine them into a solution
-
Present solution
- Make sure the big picture is hightlighted first
- Explain why this solution achieves the business objective
- Describe what worked and what didn’t
- List assumptions and system’s limitations
- Ensure keys findings are communicated through beautiful visualizations or easy-to-remember statements
-
Launch, monitor, and maintain the system
Neural Networks
The area of Neural Networks has originally been primarily inspired by the goal of modeling biological neural systems, but has since diverged and become a matter of engineering and achieving good results in Machine Learning tasks. Therefore, the Neural Networks and AI in general is essentially the discipline of Machine Learning
Biological Motivation and Connections
Historically, digital computers such as the von Neumann model operate via the execution of explicit instructions with access to memory by a number of processors. Some neural networks, on the other hand, originated from efforts to model information processing in biological systems through the framework of connectionism. Unlike the von Neumann model, connectionist computing does not separate memory and processing.
Basic Principles of ConnectionismThe central connectionist principle is that mental phenomena can be described by interconnected networks of simple and often uniform units. The form of the connections and the units can vary from model to model. For example, units in the network could represent neurons and the connections could represent synapses, as in the human brain.
Activation function: Internal states of any network change over time due to neurons sending a signal to a succeeding layer of neurons in the case of a feedforward network, or to a previous layer in the case of a recurrent network. The activation function defines under what circumstances will a neuron send a signal outward to other neurons. This can be, for example, a function of probability whose range describes the probability of the neuron firing the signal
Memory and learning: Neural networks follow two basic principles:
- Any mental state can be described as a -dimensional vector of numeric activation values over neural units in a network.
- Memory and learning are created by modifying the ‘weights’ of the connections between neural units, generally represented as an matrix. The weights are adjusted according to some learning rule or algorithm
The basic computational unit of the brain is a neuron. Approximately 86 billion neurons can be found in the human nervous system and they are connected with approximately - synapses. The diagram below shows a cartoon drawing of a biological neuron (left) and a common mathematical model (right).
Each neuron receives input signals from its dendrites and produces output signals along its (single) axon. The axon eventually branches out and connects via synapses to dendrites of other neurons.
In the computational model of a neuron, the signals that travel along the axons (e.g. ) interact multiplicatively (e.g. ) with the dendrites of the other neuron based on the synaptic strength at that synapse (e.g. ). The idea is that the synaptic strengths (the weights ) are learnable and control the strength of influence (and its direction: excitory (positive weight) or inhibitory (negative weight)) of one neuron on another. In the basic model, the dendrites carry the signal to the cell body where they all get summed. If the final sum is above a certain threshold, the neuron can fire, sending a spike along its axon. In the computational model, we assume that the precise timings of the spikes do not matter, and that only the frequency of the firing communicates information. Based on this rate code interpretation, we model the firing rate of the neuron with an activation function , which represents the frequency of the spikes along the axon. Historically, a common choice of activation function is the sigmoid function , since it takes a real-valued input (the signal strength after the sum) and squashes it to range between 0 and 1. An example code for forward-propagating a single neuron might look as follows:
class Neuron(object): # ... def forward(self, inputs): """ assume inputs and weights are 1-D numpy arrays and bias is a number """ cell_body_sum = np.sum(inputs * self.weights) + self.bias firing_rate = 1.0 / (1.0 + math.exp(-cell_body_sum)) # sigmoid activation function return firing_rate
In other words, each neuron performs a dot product with the input and its weights, adds the bias and applies the non-linearity (or activation function), in this case the sigmoid
Coarse modelIt’s important to stress that this model of a biological neuron is very coarse. For example, there are many different types of neurons, each with different properties. The dendrites in biological neurons perform complex nonlinear computations. The synapses are not just a single weight, they are a complex non-linear dynamical system. The exact timing of the output spikes in many systems is known to be important, suggesting that the rate code approximation may not hold. Due to all these and many other simplifications, be prepared to hear groaning sounds from anyone with some neuroscience background if we draw analogies between Neural Networks and real brains. See this review if people are interested.
Neural Networks are modeled as collections of neurons that are connected in an acyclic graph. In other words, the outputs of some neurons can become inputs to other neurons. Cycles are not allowed since that would imply an infinite loop in the forward pass of a network. Instead of an amorphous blobs of connected neurons, Neural Network models are often organized into distinct layers of neurons.
Convolutional Neural Networks (CNNs)
Convolutional Neural Networks (ConvNets or CNNs) are a category of Neural Networks that have proven very effective in areas such as image recognition and classification. ConvNets have been successful in identifying faces, objects and traffic signs apart from powering vision in robots and self-driving cars.
In the figure above, a ConvNet is able to recognize scenes and the system is able to suggest relevant captions (“a soccer player is kicking a soccer ball”) while figure below shows an example of ConvNets being used for recognizing everyday objects, humans and animals. Lately, ConvNets have been effective in several Natural Language Processing tasks (such as sentence classification) as well.
Essentially, every image can be represented as a matrix of pixel values.
Channel is a conventional term used to refer to a certain component of an image. An image from a standard digital camera will have three channels - red, green and blue - we can imagine those as three 2d-matrices stacked over each other (one for each color), each having pixel values in the range 0 to 255. A grayscale image, on the other hand, has just one channel. We will only consider grayscale images, so we will have a single 2d matrix representing an image. The value of each pixel in the matrix will range from 0 to 255 - zero indicating black and 255 indicating white.
Convolution Step
ConvNets derive their name from the “convolution” operator. The primary purpose of convolution in case of a ConvNet is to extract features from the input image. Convolution preserves the spatial relationship between pixels by learning image features using small squares of input data. We will not go into the mathematical details of Convolution here, but will try to understand how it works over images.
As we discussed above, every image can be considered as a matrix of pixel values. Consider a 5 x 5 image whose pixel values are only 0 and 1 (note that for a grayscale image, pixel values range from 0 to 255, the green matrix below is a special case where pixel values are only 0 and 1):
Also, consider another 3 x 3 matrix as shown below:
Then, the Convolution of the 5 x 5 image and the 3 x 3 matrix can be computed as shown in the animation below:
We slide the orange matrix over our original image (green) by 1 pixel (also called stride) and for every position, we compute element wise multiplication (between the two matrices) and add the multiplication outputs to get the final integer which forms a single element of the output matrix (pink). Note that the 3×3 matrix sees only a part of the input image in each stride. In CNN terminology, the 3×3 matrix is called a filter or kernel or feature detector and the matrix formed by sliding the filter over the image and computing the dot product is called the Convolved Feature or Activation Map or the Feature Map. It is important to note that filters acts as feature detectors from the original input image.
In practice, a CNN learns the values of these filters on its own during the training process (although we still need to specify parameters such as number of filters, filter size, architecture of the network etc. before the training process). The more filters we have, the more image features get extracted and the better our network becomes at recognizing patterns in unseen images.
The size of the Feature Map is controlled by 3 parameters that we need to decide before the convolution step is performed:
-
Depth: Depth corresponds to the number of filters we use for the convolution operation. In the network shown below, we are performing convolution of the original boat image using three distinct filters, thus producing three different feature maps as shown. We can think of these three feature maps as stacked 2d matrices
-
Stride: Stride is the number of pixels by which we slide our filter matrix over the input matrix. When the stride is 1 then we move the filters one pixel at a time. When the stride is 2, then the filters jump 2 pixels at a time as we slide them around. Having a larger stride will produce smaller feature maps.
-
Zero-padding: Sometimes, it is convenient to pad the input matrix with zeros around the border, so that we can apply the filter to bordering elements of our input image matrix. A nice feature of zero padding is that it allows us to control the size of the feature maps. Adding zero-padding is also called wide convolution, and not using zero-padding would be a narrow convolution.
Pooling Step
Spatial Pooling (also called subsampling or downsampling) reduces the dimensionality of each feature map but retains the most important information. Spatial Pooling can be of different types: Max, Average, Sum etc.
In case of Max Pooling, we define a spatial neighborhood (for example, a 2×2 window) and take the largest element from the rectified feature map within that window. Instead of taking the largest element we could also take the average (Average Pooling) or sum of all elements in that window. In practice, Max Pooling has been shown to work better.
Pooling
- makes the input representations (feature dimension) smaller and more manageable
- reduces the number of parameters and computations in the network, therefore, controlling overfitting
- makes the network invariant to small transformations, distortions and translations in the input image
- helps us arrive at an almost scale invariant representation of our image. This is very powerful since we can detect objects in an image no matter where they are located
Architecture
A convolutional neural network consists of an input layer, hidden layers and an output layer. In a convolutional neural network, the hidden layers include one or more layers that perform convolutions followed by other layers such as pooling layers and fully connected layers
After several convolutional and max pooling layers, the final classification is done via fully connected layers. Neurons in a fully connected layer have connections to neurons in the previous layer. The input to this fully connected layer is a one-dimensional vector, which is the flattened output of the convolutional/pooling layers.
What does the flattening look like?In a Convolutional Neural Network (CNN), the input to the fully connected network (FCN) is the output of the final convolutional layer or pooling layer. This input is typically a 3-dimensional tensor with height, width, and depth representing the extracted features. The flattening on this 3D tensor is essentially “unfolding” all the dimensions together. The resulting one-dimensional vector will have a size equal to the product of the original dimensions. For example, a tensor has the flattened vector with size of , which is the number of neurons of the FCN input layers.
There are two aspects of this computation worth paying attention to:
- Location Invariance: Let’s say we want to classify whether or not there’s an elephant in an image. Because we are sliding our filters over the whole image we don’t really care where the elephant occurs. In practice, pooling also gives us invariance to translation, rotation and scaling.
- Compositionality: Each filter composes a local patch of lower-level features into higher-level representation. That’s why CNNs are so powerful in Computer Vision. It makes intuitive sense that you build edges from pixels, shapes from edges, and more complex objects from shapes.
Convolutional Neural Networks for NLP
Instead of image pixels, the input to most NLP tasks are sentences or documents represented as a matrix. Each row of the matrix corresponds to one token, typically a word, but it could be a character. That is, each row is vector that represents a word. Typically, these vectors are word embeddings (low-dimensional representations) like word2vec or GloVe, but they could also be one-hot vectors that index the word into a vocabulary. For a 10 word sentence using a 100-dimensional embedding we would have a 10×100 matrix as our input. That’s our “image”.
In vision, our filters slide over local patches of an image, but in NLP we typically use filters that slide over full rows of the matrix (words). Thus, the “width” of our filters is usually the same as the width of the input matrix. The height, or region size, may vary, but sliding windows over 2-5 words at a time is typical. Putting all the above together, a Convolutional Neural Network for NLP may look like this:
In the illustration of this Convolutional Neural Network (CNN) architecture for sentence classification above, we depict three filter region sizes: 2, 3 and 4, each of which has 2 filters. Every filter performs convolution on the sentence matrix and generates (variable-length) feature maps. Then 1-max pooling is performed over each map, i.e., the largest number from each feature map is recorded. Thus a univariate feature vector is generated from all six maps, and these 6 features are concatenated to form a feature vector for the penultimate layer. The final softmax layer then receives this feature vector as input and uses it to classify the sentence; here we assume binary classification and hence depict two possible output states.
What about the nice intuitions we had for Computer Vision? Location Invariance and local Compositionality made intuitive sense for images, but not so much for NLP. We probably do care a lot where in the sentence a word appears (Except for Latin). Pixels close to each other are likely to be semantically related (part of the same object), but the same isn’t always true for words. In many languages, parts of phrases could be separated by several other words. The compositional aspect isn’t obvious either. Clearly, words compose in some ways, like an adjective modifying a noun, but how exactly this works what higher level representations actually “mean” isn’t as obvious as in the Computer Vision case. Given all this, Recurrent Neural Networks make more intuitive sense. They resemble how we process language, or at least how we think we process language: Reading sequentially from left to right.
Recurrent Neural Networks (RNNs)
A glaring limitation of Vanilla Neural Networks (and also Convolutional Networks) is that their API is too constrained. They accept a fixed-sized vector as input (e.g. an image) and produce a fixed-sized vector as output (e.g. probabilities of different classes). In addition, these models perform this mapping using a fixed amount of computational steps (e.g. the number of layers in the model). The core reason that recurrent nets are more exciting is that they allow us to operate over sequences of vectors: Sequences in the input, the output, or in the most general case both. We will illustrate this now
Introduction
We all heard of this buz word “LLM” (Large Language Model). But let’s put that aside for just a second and look at a much simpler one called “character-level language model” where, for example, we input a prefix of a word such as “hell” and the model outputs a complete word “hello”. That is, this language model predicts the next character of a character sequence. This is like a Math function where we have:
where we call inputs like “hell” a sequence.
How do we obtain a function like this? One approach is to have 4 black boxes, each of which takes a single character as input and calculates an output:
But one might have noticed that if the 3rd function (box) produces , then why would the 4th function (box), given the same input, gives a different output of ‘o’? This suggest that we should take the history into account. Instead of having depend on 1 parameter, we now have it take 2 parameters.
- a character;
- a variable that summarizes the previous calculations:
Now it makes much more sense with:
But what if we want to predict a longer or shorter word? For example, how about predicting “cat” by “ca”? That’s simple, we will have 2 black boxes to do the work.
What if the function is not smart enough to produce the correct output everytime? We will simply collect a lot of examples such as “cat” and “hello”, and feed them into the boxes to train them until they can output correct vocabulary like “cat” and “hello”.
This is the idea behind RNN. It’s recurrent because the boxed function gets invoked repeatedly for each element of the sequence. In the case of our character-level language model, element is a character such as “e” and sequence is a string like “hell”
Each function is a network unit containing 2 perceptrons. One perceptron computes the “history” like , , .
One great thing about the RNNs is that they offer a lot of flexibility on how we wire up the neural network architecture. Normally when we are working with neural networks, we are given a fixed sized input vector (red boxes below), then we process it with some hidden layers (green), and we produce a fixed sized output vector (blue). The left-most model in figure below is the Vanilla Neural Networks, which receives a single input and produce one output (The green box in between actually represents layers of neurons). The rest of the models on the right are all Recurrent Neural Networks that allow us to operate over sequences of input, output, or both at the same time:
- An example of one-to-many model is image captioning where we are given a fixed sized image and produce a sequence of words that describe the content of that image through RNN
- An example of many-to-one task is sentiment classification in NLP where we are given a sequence of words of a
- sentence and then classify what sentiment (e.g. positive or negative) that sentence is.
- An example of many-to-many task is machine translation in NLP, where we can have an RNN that takes a sequence of words of a sentence in English, and then this RNN is asked to produce a sequence of words of a sentence in German.
- There is also a variation of many-to-many task as shown in the last model in figure below, where the model generates an output at every timestep. An example of this many-to-many task is video classification on a frame level where the model classifies every single frame of video with some number of classes. We should note that we don’t want this prediction to only be a function of the current timestep (current frame of the video), but also all the timesteps (frames) that have come before this video.
TIPA CNN learns to recognize patterns across space. So a CNN will learn to recognize components of an image (e.g., lines, curves, etc.) and then learn to combine these components to recognize larger structures (e.g., faces, objects, etc.)
A RNN will similarly learn to recognize patterns across time. So a RNN that is trained to translate text might learn that “dog” should be translated differently if preceded by the word “hot”.
The mechanism by which the two kinds of NNs represent these patterns is different, however. In the case of a CNN, we are looking for the same patterns on all the different subfields of the image. In the case of a RNN we are (in the simplest case) feeding the hidden layers from the previous step as an additional input into the next step. While the RNN builds up memory in this process, it is not looking for the same patterns over different slices of time in the same way that a CNN is looking for the same patterns over different regions of space.
It should be noted that “time” and “space” here shouldn’t be taken too literally. We could run a RNN on a single image for image captioning, for instance, and the meaning of “time” would simply be the order in which different parts of the image are processed. So objects initially processed will inform the captioning of later objects processed.
The sequence regime of operation is much more powerful compared to fixed networks that are doomed from the get-go by a fixed number of computational steps. Moreover, as we’ll see in a bit, RNNs combine the input vector with their state vector with a fixed (but learned) function to produce a new state vector. This can in programming terms be interpreted as running a fixed program with certain inputs and some internal variables. Viewed this way, RNNs essentially describe programs. In fact, it is known that RNNs are Turing-Complete in the sense that they can simulate arbitrary programs (with proper weights).
Space → Time v.s. Function → ProgramIf training vanilla neural nets is optimization over functions, training recurrent nets is optimization over programs.
If our data is not in form of sequences, we can still formulate and train powerful models that learn to process it sequentially. We’re learning stateful programs that process our fixed-sized data.
At the core, RNNs accept an input vector x
and give us an output vector y
. This output vector’s contents are
influenced not only by the input we just fed in, but also on the entire history of inputs we’ve fed in from the past.
The RNN’s API consists of a single step function:
rnn = RNN()y = rnn.step(x) # x is an input vector, y is the RNN's output vector
This is where RNN starts to model the notion of “memory”: The RNN class has some internal state that is updated
every time step()
is called. In the simplest case this state consists of a single hidden vector h
:
class RNN: # ... def step(self, x): # update the hidden state self.h = np.tanh(np.dot(self.W_hh, self.h) + np.dot(self.W_xh, x)) # compute the output vector y = np.dot(self.W_hy, self.h) return y
The step function above specifies the forward pass of RNN. There are 3 parameters , , and . The hidden vector, or more generally the hidden state, is defined by
where is the index of the “black boxes” shown earlier. In our example of “hell”, . The hidden state is usually initialized with zero vector (simulating “no memory at all”). There are 2 terms inside the :
- one term based on the previous hidden state , and
- the other term based on the current input
In the program above we use numpy np.dot
which is a matrix multiplication. The 2 terms interact with addition.
We initialize matrices , , and with random numbers and the bulk of work during training goes into
finding the matrices that gives rise to the desirable behavior, as measured with some loss function
that expresses our preferences to what kind of output y
we would like to see in response to our input sequence x
The value is given by
What are and ?They are activation functions which are used to change the linear function in a perceptron to a non-linear function. Please refer to Machine Learning by Mitchell, Tom M. (1997), Paperback (page 96) for why we bump it to non-linear
A typical activation function for is :
which squashes the activations to the range
In practice, is constance, i.e.
We get RNNs as neural networks if we stack up as follows:
y1 = rnn1.step(x)y = rnn2.step(y1)
In other words we have two separate RNNs: One RNN is receiving the input vectors and the second RNN is receiving the output of the first RNN as its input. Except neither of these RNNs know or care - it’s all just vectors coming in and going out, and some gradients flowing through each module during backpropagation.
Forward Propagation Equations for RNN
We now develop the forward propagation equations for the RNN. We assume the hyperbolic tangent activation function, i.e. and that the output is discrete, as if the RNN is used to predict words or characters. A natural way to represent discrete variables is to regard the output as giving the unnormalized log probabilities of each possible value of the discrete variable. We can then apply the softmax (discussed shortly) operation as a post-processing step to obtain a vector of normalized probabilities over the output.
Forward propagation begins with a specification of the initial state . The dimension of the hidden state , in contract to our previous overview, is independent of the dimension of the input or output sequences. In fact, is a 3D array, whose 1st-dimensional size is exactly the number of RNN parameters.
Then, for each time step from to , we apply the following update equations:
where
- is the hidden state vector of size
- is the output produced by the model at step where
- is the normalized probability of at
- is the hidden bias vector of size
- is the output bias vector of size
- the size of is
- the size of is
- the size of is
Note that this recurrent network maps an input sequence to an output sequence of the same length.
Loss Function of RNN
According to the discussion of Machine Learning by Mitchell, Tom M. (1997), the key for training RNN or any neural network is through “specifying a measure for the training error”. We call this measure a loss function.
In RNN, the total loss for a given sequence of input paired with a sequence of expected is the sum of the losses over all the time steps, i.e.
Knowing the exact form of requires our intuitive understanding of cross-entropy
Cross-Entropy
In information theory, the cross-entropy between two probability distributions and over the same underlying set of events measures the average number of bits needed to identify an event drawn from the set if a coding scheme used for the set is optimized for an estimated probability distribution , rather than the true distribution
Confused? Let’s put it in the context of Machine Learning. Machine Learning sees the world based on probability. The “probability distribution” identifies the various tasks to learn. For example, a daily language such as English or Chinese, can be seen as a probability distribution. The probability of “name” followed by “is” is far greater than “are” as in “My name is Jack”. We call such language distribution . The task of RNN (or Machine Learning in general) is to learn an approximated distribution of ; we call this approximation
“The average number of bits needed” is can be seen as the distance between and given an event. In analogy of language, this can be the quantitative measure of the deviation between a real language phrase “My name is Jack” and “My name are Jack”.
At this point, it is easy to imagine that, in the Machine Learning world, the cross entropy indicates the distance between what the model believes the output distribution should be and what the original distribution really is.
Now we have an intuitive understanding of cross entropy, let’s formally define it. The cross-entropy of the discrete probability distribution relative to a distribution over a given set is defined as
Since we assume the softmax probability distribution earlier, the probability distribution of is:
where is the predicted sequence by RNN and is the i-th element of the predicted sequence
Therefore, the total loss for a given sequence of input paired with a sequence of expected is the sum of the losses over all the time steps, i.e.
What is the Mathematical form of in RNN? Why would it become 1?By definition, is the true distribution whose exact functional form is unknown. In the language of Approximation Theory, is the function that RNN is trying to learn or approximate mathematically.
Although the makes the exact form of unknown, computationally is perfectly defined in each training example. Taking our “hello” example:
The 4 probability distributions of is “reflected” in the output layer of this example. They are “reflecting” the probability distribution of because they are only values and have not been transformed to the distribution yet. But in this case, we are 100% sure that the true probability distribution for the 4 outputs are
respectively. That is all we need for calculating the
The softmax function takes as input a vector of real numbers, and normalizes it into a probability distribution consisting of probabilities proportional to the exponentials of the input numbers. That is, prior to applying softmax, some vector components could be negative, or greater than one; and might not sum to 1; but after applying softmax, each component will be in the interval and the components will add up to 1, so that they can be interpreted as probabilities. Furthermore, the larger input components will correspond to larger probabilities.
For a vector of real numbers, the the standard (unit) softmax function , where is defined by
where and
In the context of RNN,
where
- is the length of a sequence feed into the RNN
- is the output by perceptron unit
i
- ,
The softmax function takes an N-dimensional vector of arbitrary real values and produces another N-dimensional vector with real values in the range (0, 1) that add up to 1.0. It maps
This property of softmax function that it outputs a probability distribution makes it suitable for probabilistic interpretation in classification tasks. Neural networks, however, are commonly trained under a log loss (or cross-entropy) regime
We are going to compute the derivative of the softmax function because we will be using it for training our RNN model shortly. But before diving in, it is important to keep in mind that Softmax is fundamentally a vector function. It takes a vector as input and produces a vector as output; in other words, it has multiple inputs and multiple outputs. Therefore, we cannot just ask for “the derivative of softmax”; We should instead specify:
- Which component (output element) of softmax we’re seeking to find the derivative of.
- Since softmax has multiple inputs, with respect to which input element the partial derivative is computed.
What we’re looking for is the partial derivatives of
where is the partial derivative of the i-th output with respect with the k-th input.
We’ll be using the quotient rule of derivatives. For where both and are differentiable and , The quotient rule states that the derivative of is
In our case, we have
The rest of it becomes trivial then. When ,
When :
This concludes the derivative of the softmax function:
Deriving Gradient Descent Weight Update Rule
Training a RNN model of is the same thing as searching for the optimal values for the following parameters of the Forward Progagation Equations:
By the Gradient Descent discussed in Machine Learning by Mitchell, Tom M. (1997), Paperback, we should derive the weight update rule by taking partial derivatives with respect to all of the variables above. Let’s start with
Machine Learning by Mitchell, Tom M. (1997), Paperback has also mentioned gradients and partial derivatives as being important for an optimization algorithm to update, say, the model weights of a neural network to reach an optimal set of weights. The use of partial derivatives permits each weight to be updated independently of the others, by calculating the gradient of the error curve with respect to each weight in turn.
Many of the functions that we usually work with in machine learning are multivariate, vector-valued functions, which means that they map multiple real inputs to multiple real outputs :
In training a neural network, the backpropagation algorithm is responsible for sharing back the error calculated at the output layer among the neurons comprising the different hidden layers of the neural network, until it reaches the input.
If our RNN contains only 1 perceptron unit, the error is propagated back by, using the Chain Rule of :
Note that in the RNN mode, is not a direct function of . Thus its first order derivative cannot be computed unless we connect the to first and then to , because both the first order derivatives of and are defined by the model presented earlier above
It is more often the case that we’d have many connected perceptrons populating the network, each attributed a different weight. Since this is the case for RNN, we can generalise multiple inputs and multiple outputs using the Generalized Chain Rule:
Generalized Chain RuleConsider the case where and ; an inner function, , maps inputs to outputs, while an outer function, , receives inputs to produce an output, . For the generalized chain rule states:
Therefore, the error propagation of Gradient Descent in RNN is
where is the length of a RNN sequence and the index of timestep
OnWe assume the error is the sum of all errors of each timestep, which is why we include the term
Let’s look at first
Since
For the we shall recall from the earlier discussion on softmax derivative that we CANNOT simply have
because we need to
- specify which component (output element) we’re seeking to find the derivative of
- with respect to which input element the partial derivative is computed
Therefore:
where is the number of timesteps (or the length of a sequence such as “hell”)
Applying the chain rule again:
Recall we have already derived that
Observing that
We have at this point derived backpropagating rule for and :
- ✅
- ✅
Now let’s look at :
Recall from Deep Learning, section 6.5.2, p. 207 that the vector notation of is
This gives us a start with:
The equation above leaves us with a term , which we calculate next. Note that the back propagation on has source from both and . It’s gradient, therefore, is given by
Note that the 2nd term is zero at first iteration propagating back because for the last-layer (unrolled) of RNN , there’s no gradient update flow from the next hidden state.
So far we have derived backpropagating rule for
- ✅
- ✅
- ✅
Let’s tackle the remaining and :
This concludes our propagation rules for training RNN:
According to page 91 of Machine Learning by Mitchell, Tom M. (1997), Paperback, the amount of updates in direction is given by
The update rules for training RNN with a learning rate of , therefore, are:
where
NOTEA Python implementation of the RNN discussed in this article can be found at here
Graph Neural Network
Large Language Model (LLM)
RAG & GraphRAG
What Is Retrieval-Augmented Generation (RAG)?
Engaging in a conversation with a company’s AI assistant can be frustrating. Chatbots give themselves away by returning generic responses that often don’t answer the question. This is because Large language models (LLMs), like OpenAI’s GPT models, excel at general language tasks but have trouble answering specific questions for several reasons:
- LLMs have a broad knowledge base but often lack in-depth industry- or organization-specific context.
- LLMs may generate responses that are incorrect, known as hallucinations.
- LLMs lack explainability, as they can’t verify, trace, or cite sources.
- An LLM’s knowledge is based on static training data that doesn’t update with real-time information.
This doesn’t have to be the case. Imagine a different scenario: interacting with a chatbot that provides detailed, precise responses. This chatbot sounds like a human with deep institutional knowledge about the company and its products and policies. This chatbot is actually helpful. The second scenario is possible through a machine learning approach called Retrieval-Augmented Generation (RAG).
RAG is a technique that enhances Large Language Model (LLM) responses by retrieving source information from external data stores to augment generated responses. These data stores, including databases, documents, or websites, may contain domain-specific, proprietary data that enable the LLM to locate and summarize specific, contextual information beyond the data the LLM was trained on.
RAG applications are becoming the industry standard for organizations that want smarter generative AI applications. With RAG, we can reduce hallucination, provide explainability, draw upon the most recent data, and expand the range of what our LLM can answer. As we improve the quality and specificity of its response, we also create a better user experience.
How Does RAG Work?
At a high level, the RAG architecture involves 3 key processes:
- understanding queries: the process begins when a user asks a question. The query goes through the LLM API to the RAG application, which analyzes it to understand the user’s intent and determine what information to look for.
- retrieving information: the application uses advanced algorithms to find the most relevant pieces of information in the company’s database. These algorithms match vector embeddings based on semantic similarity to identify the information that can best answer the user’s question.
- generating responses: the application combines the retrieved information with the user’s original prompt to create a more detailed and context-rich prompt. It then uses the new prompt to generate a response tailored to the organization’s internal data.
Before implementing an RAG application, it’s important to clean up our data to make it easy for the RAG application to quickly search and retrieve relevant information. This process is called data indexing.
Frameworks like LangChain make it easy to build RAG applications by providing a unified interface to connect LLMs to external databases via APIs. Neo4j vector index on the LangChain library helps simplify the indexing process.
GraphRAG
Rather than using documents as a source to vectorize and retrieve from, Knowledge Graphs can be used. One can start with a set of documents, books, or other bodies of text, and convert them to a knowledge graph using one of many methods, including language models. Once the knowledge graph is created, subgraphs can be vectorized, stored in a vector database, and used for retrieval as in plain RAG. The advantage here is that graphs has more recognizable structure than strings of text and this structure can help retrieve more relevant facts for generation. This approach is called GraphRAG