<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Ambrose Ling on Medium]]></title>
        <description><![CDATA[Stories by Ambrose Ling on Medium]]></description>
        <link>https://medium.com/@lingambrose?source=rss-e6b3bc2634c3------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*wPFwFGeIcRKpBcIv</url>
            <title>Stories by Ambrose Ling on Medium</title>
            <link>https://medium.com/@lingambrose?source=rss-e6b3bc2634c3------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 16:31:53 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@lingambrose/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[CPU Branch Prediction — Earliest forms of Machine Learning]]></title>
            <link>https://medium.com/demistify/cpu-branch-prediction-earliest-forms-of-machine-learning-c43936c25f7f?source=rss-e6b3bc2634c3------2</link>
            <guid isPermaLink="false">https://medium.com/p/c43936c25f7f</guid>
            <category><![CDATA[computer-architecture]]></category>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[branch-prediction]]></category>
            <dc:creator><![CDATA[Ambrose Ling]]></dc:creator>
            <pubDate>Wed, 29 Jan 2025 22:07:10 GMT</pubDate>
            <atom:updated>2025-01-29T22:07:10.575Z</atom:updated>
            <content:encoded><![CDATA[<h3>CPU Branch Prediction — Earliest forms of Machine Learning</h3><h3>Introduction</h3><p>Before the big boom of neural networks and deep learning, the idea of learning from data has certainly not been a new one. Computer scientists and computer architects take advantage of this idea to build computers and to make them operate as fast as possible. One of the earliest application of data-driven decision making was in branch prediction. But what is branch prediction anyways? why does it matter? and how does it affect the development of the processors we see today? In this article, we will seek to answer these questions.</p><h3>Background</h3><p>Computers, on the lowest level, executes instructions according to a clock. Whenever you open up Minecraft, your web browser to look for that funny cat meme or running your C program, they all get turned into instructions. There are many different fundamental types of instructions.</p><ol><li>Data Movement Instructions: instructions that transfer data between memory LD (load data from memory to a register), ST (store data from register to memory), MOV (data from register to register)</li><li>Arithmetic Instructions: instructions that do quick maths with that data ADD`(add 2 register values together), SUB (subtracts 2 register values together), MUL(multiplies 2 regiser values together), DIV (divide a register value by the other)</li><li>Control flow instructions: instructions that direct the CPU to execute instructions in a different order. JMP, BEQ (branch). These instructions are usually translated from conditional statements such as if or while conditionals.</li></ol><p>When you write a simple program in C, like adding two numbers, it is translated into assembly code, which is a human-readable representation of the instructions a processor can execute. This assembly code is then further converted into machine code, which the processor understands directly. To begin understanding how do computers execute these instructions, there are different types of processors that have evolved from</p><p><strong>Single Cycle Processors</strong></p><p>These are processors that execute 1 instruction per cycle, each cycle requires some constant amount of time, regardless of how complicated your instruction is. But people realized this was way too slow, why is that?</p><p>Because in one clock cycle, our slowest instruction has to be able to finish what its doing, meaning that the machine has to operate at the speed of the slowest instruction. So then people realized that what if we split the execution of an instruction into multiple chunks or stages. We roughly imagine it as these following stages 1) Fetch 2) Decode 3) Execute 4) Memory 5) Writeback (The specific stages can vary depending on the design ).</p><p>FETCH : the instruction code gets loaded into the Instruction Register (IR), Program Counter (PC) will get incremented on the next cycle.</p><p>DECODE: the instruction code in the IR decodes the source and destination operands to determine the type of instruction it is.</p><p>MEM: If needed, data loaded onto the register is written to or read from memory.</p><p>EXEC: the Arithmetic Logic Unit (ALU) is passed appropriate control signals to complete arithmetic operations such as ADD, SUB, MULT etc. The ALU completes the required computation and loads the result to an intermediate register. In this stage, the processor usually resolves the branch condition and knows if a branch is taken or not.</p><p>WRITEBACK: any result computed by the instruction is written back to the register file (a place where we store all the values for our registers) to reflect the completion of the instruction.</p><p>We split up the work of each instruction into these different stages, which leads us to the idea of multi-cycle processors.</p><p><strong>Multi Cycle Processors</strong></p><p>In a multi-cycle processor, each instruction is divided into several stages (e.g. Fetch, Decode, Execute, Memory, Writeback). Instead of the entire instruction being executed in 1 clock cycle, each stage is much shorter and is what determines the cycle duration. To understand how they work, let’s look at the following diagram.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*TExEly1INW1Asdz3DDslCw.png" /><figcaption>Figure 1: Multi cycle processor timing diagram with instructions</figcaption></figure><p>In this diagram we’re executing a series of very simple instructions (3 ALU instructions) ultimately perform D[8] = D[8] + RF[1] + RF[4]. You can see that each instruction is broken up into 3 stages (Fetch, Decode, Execute). At every clock cycle, we complete 1 stage of an instruction. Instructions in this example take 3 cycles each to complete. Because of the multi-cycle design, shorter instructions can also take less cycles to complete. For example, a MULT instruction may take more instructions than an ADD instruction because of the more complex arithmetic logic in the MULT instruction. Hence simpler programs take less time to complete.</p><p>However, even with multi-cycle processors there is a still some inefficiencies — only 1 instruction is processed at any given time. For example, instruction 1 goes through all stages sequentially. Then, instruction 2 begins only after instruction 1 completes. This is where pipelining steps in.</p><p><strong>Pipelined Processors: </strong>The core idea of pipelining is to overlap the execution of multiple instructions. The need of pipelined processors come from the fact that executing 1 instruction at a time severely limits the throughput of the processor.</p><p>You can think of a pipelined processor as an assembly line or the process of washing your clothes. There is a stage 1 — washing machine station, stage 2 — a dryer station and stage 3 — a folding station, and stage 4 — putting clothes back in your closet . Each stage works on a different instruction simultaneously. If you washed your clothes like a non-pipelined multi-cycle processor, you would first enter the washing machine station, then move to the dryer station then the folding station. One-by-one you move across each station and the next load of clothes will enter the station ONLY when the previous load of clothes completes all stages. However this is slow and inefficient, we can speed up the throughput (the amount of work completed per unit time) of us washing clothes by starting the next load in the washing machine once it is unoccupied.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/529/1*Bi7TxDxRDMHrpSnnrxU7qg.gif" /><figcaption>Figure 2a: Top: Non pipelined laundry washing, Bottom: pipelined laundry washing</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*-lFUrAmsHwU3XTAQ6Dcb2w.png" /><figcaption>Figure 2b: MIPS pipelined processor diagram</figcaption></figure><p>Pipelining is a highly effective technique that significantly improves efficiency by allowing multiple instructions to be processed simultaneously at different stages of execution. However, branch instructions in particular introduce complications in pipelining because of how these types of instructions alter the flow of instruction execution. They are different from ALU or Memory instructions in that they can alter the Program Counter (PC), which determines which instruction to fetch next. In a pipelined processor, this uncertainty can cause delays if the processor fetches the wrong instruction. To address this challenge, processors use branch prediction to anticipate the outcome of branch instructions. Let’s use an example to demonstrate how branch instructions in a pipelined processor can cause stalls.</p><h3>Branch Prediction</h3><p>The idea of branch prediction is for the microprocessor to try and predict whether the branch instruction would evaluate to Taken or Not Taken early on in the pipeline, usually in the Fetch stage. Based on this prediction, the microprocesor decides which instructions to load into the pipeline. It will know for sure<strong> </strong>if it branches or not in the EXE stage. If the prediction is wrong, we would have to flush the pipeline, causing the microprocessor to stall and wait. But if it is correct, it will help save a lot of time and we can reduce the penalty we have to pay for flushing the pipeline every time, reduce the number of clock cycles waster for stalling and waiting until the branch condition is resolved.</p><p>There are 2 types of branch prediction — static branch prediction and dynamic branch prediction. In static branch prediction, the prediction is purely based on the current instruction, does not care about what instruction was executed in the past and does not consider the history of the program. On the other hand, a dynamic branch predictor uses historical information of past TAKENs or NOT-TAKENs to make a prediction. We will introduce a few of the most impactful predictors in computer architecture .</p><h3>1-level Predictors</h3><h4>1-bit Predictor</h4><p>In a 1-bit predictor, we simply use our previous branch outcome as the prediction. If the prediction is wrong, we update the predictor (flip from T to NT or NT to T). A 1-bit predictor is very unstable because a single mis-prediction can immediately change the prediction direction.</p><p>Let’s take this sequence of branch outcomes T,T,NT,T,NT,NT,T to illustrate how a 1-bit predictor works.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*O2iL_3UZOwDG9TF8i_QS2w.png" /><figcaption>Figure 3: Branch outcome table of 1 bit predictor</figcaption></figure><p>In order to reduce the number of mis-predictions, we can also introduce the ability to keep track of past branch outcomes using a history bit. Adding a history bit provides us a way to rely on information from the past (the previous prediction) to improve our prediction. It is a design choice to select how many number of bits for your history. In the following example with branch sequence T,NT,T,T,NT,NT,T , we will just use 1 history bit, which means we will have a prediction for each history (T,NT).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-y_AWuK7toTk1RgWnslnIA.png" /><figcaption>Figure 4: Branch outcome table of 1 bit predictor and 1 history bit</figcaption></figure><p>This predictor is more so introduced to illustrate the idea of a branch prediction. Such a predictor is not very practical because of its low accuracy.</p><h4>2-bit Saturated Predictor</h4><p>In a 2-bit saturated predictor reduces the chances of a misprediction. It allows occasional mis-predictions before completely flipping its prediction from Taken to Not-Taken. This predictor maintains 4 states (Strongly Not Taken, Weak Not Taken, Weak Taken, Strong Taken). If a Taken or Not-Taken is encountered, the predictor updates the state of the predictor according to the diagram below. But it is clear that it takes 2 mis-predictions to change its prediction. This design of the predictor reduces instability when predictions are made and allows it to adapt to branch patterns over time.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2vM_iXx7-kZEt87hXMvFIA.png" /><figcaption>Figure 5: state diagram of 2-bit saturated predictor</figcaption></figure><p>As an example to show how it works, consider the following branch instruction sequence T,T,NT,T,NT,NT and we always initialize the counter as Weakly Taken.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KXZjLw3_1UUpo7BwTfsmNA.png" /><figcaption>Figure 6: Branch outcome table of 2-bit sat predictor</figcaption></figure><p>In this example, we see that our predictor is intialized to Weakly Taken. Since we encounter a branch instruction that is Taken, it means our prediction was correct. Hence on instruction 2, the state of our prediction has been updated from Weakly Taken to to Strongly Taken. On instruction 3, we predicted Taken but the actual outcome was Not Taken. We then update our predictor from Stronly Taken to Weakly Taken. We continue this for the rest of the instruction.</p><h3>2-level Predictors</h3><p>We can improve our prediction by exploiting some properties of branches.</p><ol><li>A branch’s outcome can be correlated with other branches outcomes (global branch correlation)</li><li>A branch’s outcome can be correlated with past outcomes of the same branch (local branch correlation)</li></ol><h4>2 level global branch predictor</h4><p>The idea is to keep track of the global Taken or Not-Taken history of all branches in a register, which we call the Global History Register (N bits that represent the branch direction of the last N branches). This register is used to index into a Pattern History Table, where each history entry in this table contains a saturating counter. In the diagram below, there are 2 bit saturating counters in each entry.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xKa4wk2BDp4p8xcQSjNnsw.png" /><figcaption>Figure 7 : 2 level global branch predictor</figcaption></figure><p>One example of a industry processor that leveraged this predictor was the Intel Pentium Pro Branch Predictor. You can learn more it <a href="https://backend.orbit.dtu.dk/ws/portalfiles/portal/133978907/BranchPredictionDrDobbs1998.pdf">here</a>.</p><p>There are also ways of improving the global predictor accuracy by XORing the Global History Register with the PC of the branch instruction. This helps to provide more contextual information to the predictor. On top of that, XORing both registers help spread branch accesses more uniformly across the table and prevents aliasing (multiple branches mapping to the same Pattern History Table entry). Such a predictor is also called the gshare predictor.</p><pre><strong>Why does XORing two values allow us to include more information?  <br></strong>XOR is a very unique bit-wise operation because it is reversible.<br>Meaning you can always retrieve one of the original values if you know <br>the result and the other operand. This ensures that no information is <br>lost during the operation. In contrast, other bitwise operations like <br>AND and OR may result in information loss, as their results can be ambiguous<br>and cannot always be reversed.<br><br>Let’s see an example:<br><br>Suppose you have two binary values:  <br>A = 1011 <br>B = 1101<br><br>When you perform XOR on these values:  <br>A XOR B = 0110<br><br>Now, if you know the result (`0110`) and either `A` or `B`, <br>you can recover the other value. For example:  <br><br>Result XOR A = B<br>Result XOR B = A<br><br><br>In comparison, if you use AND or OR:  <br>A AND B = 1001  <br>A OR B = 1111<br><br>In both cases, it’s impossible to fully reconstruct the original values <br>from just the result. For example, multiple pairs of inputs could produce<br> the same result for AND or OR. <br><br>In branch prediction, XORing values (such as the branch address<br> and global history) helps combine both pieces of information while <br>retaining their uniqueness, allowing predictors like Gshare to <br>efficiently incorporate more context for making decisions. <br>This ability to merge information without loss is why XOR is <br>particularly useful in hardware and algorithms.</pre><h4>2 level local branch predictor</h4><p>These predictors leverage the idea of curating a history register for <strong>each </strong>branch, rather than for all branches. Hence, a prediction for a branch instruction uses the Taken or Not Taken history of the same branch.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-T7ab-Ua01r4GAVlGzOnHw.png" /><figcaption>Figure 8: 2 level local branch predictor</figcaption></figure><p>On the first level, we have a set of local history registers, so each branch instruction has a local history register. Hence this register is selected based on the PC of the branch. This register allows us to index into the Pattern History Table on the next level.</p><p>To summarize the overall 2-level predictor taxonomy, Yeh and Patt provides a classification for different types of 2-level predictors seen with the diagram below. We can have history registers that track global or local branches or sets of local branches, these registers can act as an index into the pattern history tables. Pattern History Tables can also have counters that belong to either a global history or a per-address history.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*F8fWamWZBgMwSoF9Ihkusw.png" /><figcaption>Figure 9: 2 level predictors under Yeh and Patt classification</figcaption></figure><p>From the diagram, GAg represents the 2-level global predictor discussed above. PAg has a similar idea, but with history registers local to each branch instruction. PAp has history registers local to each branch instruction, and a unique pattern history table for each branch instruction.</p><h3>Perceptron Predictor</h3><p>In this type of predictor, you may notice some similarities with ideas in the perceptron model used in deep learning. There is a single-layer perceptron that learns a target Boolean function. The output represents whether the branch is taken or not.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/570/1*vlHdc8UNrPua1T_IlDyLCA.png" /><figcaption>Figure 10: perceptron inputs</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/239/1*utsZXu4GS0jXM8ejouI_fQ.png" /><figcaption>Figure 11: dot product of history register and weights</figcaption></figure><p>In the equation above, w_i represents the weight connection to the neuron for bit i . Then x_i represents bit i of the global history register, it takes on either -1 (Taken) or 1 (Taken). The output of this function is the dot product between the weights and the history. As for how do we train the perceptron predictor, this illustrates the training algorithm:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/431/1*XL_HkzKiloftr-U5xVHRhQ.png" /><figcaption>Figure 12: training algorithm of perceptron predictor</figcaption></figure><p>In the training algorithm, we compare the perceptron output y with the actual branch outcomet , if y has a different sign than t or if y is less than some threshold theta , then we update the weights w_i . We can see that if x_i and t have the same sign (meaning they are positively correlated), the weight would be larger. Conversely, the weight would be lower if there is a negative correlation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*Bl1wdW5bIlqzZRPEz3e7qw.png" /><figcaption>Figure 13: perceptron predictor diagram</figcaption></figure><p>In this diagram, we see that we use the address of the branch instruction in order to index into the table of perceptions. From here we obtain the ith perceptron and that provides us the weights to be dot-producted with the global history register. The output of the perceptron then provides the prediction. If the prediction is incorrect, we update the weights of the perceptrons and it is written back to the ith entry of the table.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*93Zb5NRMblrRW2xayhxnbA.png" /><figcaption>Figure 14: perceptron predictor benchmarks on SPEC 2000</figcaption></figure><p>It has been realized that the perceptron predictor or hybrid versions of the perceptron predictor can learn branch patterns much faster than other predictors, leading to superior performance in branch prediction benchmarks. The history length also significantly has an impact on the performance of these predictors. In gshare for example, a longer history length means that there are more 2-bit counters that need to be initialized, where as perceptron predictors do not have this problem as it always performs well with a longer history length.</p><h3>The Influence of Branch Prediction on Machine Learning</h3><p>Branch prediction serves as one of the earliest examples of machine learning principles applied to computer architecture, showcasing how data-driven decision-making can optimize complex systems. By leveraging historical data to predict outcomes — such as whether a branch in a program will be taken or not — branch predictors demonstrate the foundational concept of pattern recognition, a core element of machine learning. Techniques like 2-level predictors and perceptron predictors illustrate the evolution from simple heuristics to more advanced algorithms, employing ideas like global and local correlations, weighting, and iterative training to refine predictions. These principles directly inspire modern machine learning methods, where algorithms use historical data and feedback loops to improve over time. The perceptron predictor, in particular, foreshadows neural networks by combining inputs (branch history) with learned weights to make predictions, laying the groundwork for how artificial intelligence processes and learns from data in systems today.</p><h3>References</h3><ol><li><a href="https://course.ece.cmu.edu/~ece740/f15/lib/exe/fetch.php?media=18-740-fall15-lecture05-branch-prediction-afterlecture.pdf">https://course.ece.cmu.edu/~ece740/f15/lib/exe/fetch.php?media=18-740-fall15-lecture05-branch-prediction-afterlecture.pdf</a></li><li><a href="https://www.cs.utexas.edu/~lin/papers/hpca01.pdf">https://www.cs.utexas.edu/~lin/papers/hpca01.pdf</a></li><li><a href="https://backend.orbit.dtu.dk/ws/portalfiles/portal/133978907/BranchPredictionDrDobbs1998.pdf">https://backend.orbit.dtu.dk/ws/portalfiles/portal/133978907/BranchPredictionDrDobbs1998.pdf</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c43936c25f7f" width="1" height="1" alt=""><hr><p><a href="https://medium.com/demistify/cpu-branch-prediction-earliest-forms-of-machine-learning-c43936c25f7f">CPU Branch Prediction — Earliest forms of Machine Learning</a> was originally published in <a href="https://medium.com/demistify">deMISTify</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Memory optimization: Cure Out Of Memory errors like a doctor]]></title>
            <link>https://medium.com/demistify/memory-optimization-cure-out-of-memory-errors-like-a-doctor-fe3d9b8a6b5e?source=rss-e6b3bc2634c3------2</link>
            <guid isPermaLink="false">https://medium.com/p/fe3d9b8a6b5e</guid>
            <category><![CDATA[pytorch]]></category>
            <category><![CDATA[memory-improvement]]></category>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[attention-mechanism]]></category>
            <category><![CDATA[large-model-training]]></category>
            <dc:creator><![CDATA[Ambrose Ling]]></dc:creator>
            <pubDate>Sun, 28 Apr 2024 22:49:21 GMT</pubDate>
            <atom:updated>2024-04-28T22:49:21.840Z</atom:updated>
            <content:encoded><![CDATA[<p>Have you ever tried training your own LlaMA model, or fine-tuning your own Mistral 7B, or trying to fine tune your own version of Stable Diffusion or just ANY machine learning model but you keep getting CUDA Out Of Memory (OOM) errors mid way. Maybe its exactly because of these errors that are preventing you from turning these exciting ML ideas into a reality on your consumer-level hardware. So you may think “oh why not just buy a GPU with bigger memory?” Well, when you’re a broke uni student like me and for many others in the world that don’t have this capability, we need to find a better solution,<strong> so how can we reduce the significant training cost associated with these large models in regards to memory</strong>?</p><p>In this article I wish to break down how memory is consumed by your model during training and help you understand why memory is allocated the way it is and how can some of the latest research advances in memory optimization be applied to reduce different aspects of memory used by your model during training.</p><p>What I realized is that the process of debugging OOM errors share a lot in common with how a doctor treats their patients. The patient first comes to the doctor with certain symptoms and the doctor thoroughly analyzes where these symptoms are coming from or which parts of their body are showing these symptoms. Based on the doctor’s professional knowledge and experience, they make a diagnosis of what could be the cause of the disease. They then are able to provide the appropriate treatment to the patient. Let’s see how we can apply this analogy to memory optimization!</p><h3>Consultation &amp; Diagnosis: Breaking down memory allocations</h3><p>To start a consultation session with a patient, doctors usually ask them questions, use tools like stethoscopes, blood pressure monitors, thermometers to get a better sense of the patient’s health situation. In our case, the patient we have is a memory-faulty model. In order to obtain a better understanding of how memory is used during model training, we can use tools to help us make a diagnosis. One of the tools that I found very useful is using the <strong>torch memory profiler.</strong> The torch memory profiler allows you to visualize memory allocations of your training run. With their comprehensive API, it allows you to see the execution times as well as the amount of memory allocated for certain operations in the model. One very useful feature is viewing the categorized memory usage over time by your model during training. <a href="https://pytorch.org/docs/main/profiler.html">(Here is a detailed blog post on how to use the torch profiler)</a>[1].</p><p>Before we dive into all the specifics on the profiler and all that jazz, let’s try to understand what happens under the hood in your typical training loop. In my example, I’m simply training a model to perform image classification.</p><pre>for epoch in range(epochs):<br>  for batch in dataloader:<br>    y = model(x) #FORWARD PASS<br>    loss = loss_fn(y,batch.y) #LOSS COMPUTATION<br>    loss.backward() #BACKWARD PASS<br>    optimizer.step() #GRADIENT DESCENT</pre><p>As you iterate through each epoch, you extract a batch of data from your dataloader. In forward pass, your model takes an input batch of data and passes it through the hidden layers of the model. During that process, PyTorch dynamically constructs a computation graph (See Figure 2 below). In this computation graph, a node represents a tensor operation and an edge represents a parent-child relationship between operations (the output of operation A is the input to operation B). During forward pass, torch computes the forward pass operations and each node stores intermediate outputs of the operations which we call <strong>activations. </strong>Simultaneously when an operation is executed, torch obtains the derivative of that operation and constructs a graph for our backward pass using <a href="https://pytorch.org/blog/overview-of-pytorch-autograd-engine/#:~:text=PyTorch%20computes%20the%20gradient%20of,ways%3B%20forward%20and%20reverse%20mode.">automatic differentiation</a>. Only after we compute the loss and run loss.backwards() aka backward pass, the nodes of the backward pass graph get evaluated and thus <strong>gradients</strong> would be computed and stored in memory[2].</p><p>With the gradients ready, we can apply a gradient descent step with optimizer.step() which nudges the weights in a certain direction in order to minimize the loss.</p><p>If we use the torch profiler, we can obtain a memory consumption graph corresponding to our training loop. And the profiler has helped us categorize the memory usage over time.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/830/1*39ShYbhp3P2u_CgwYTjzTw.png" /><figcaption>Figure 1: Memory graph over time for training a ViT for image classification</figcaption></figure><p>Lets break down the categories that consume the most memory in more detail and understand the behaviors observed:</p><ol><li><strong>Parameters (green)</strong></li></ol><p>These are the weights of your model that store the strength of connections we have between artificial neurons. These weights get multiplied with the input in order to propagate to the output. When we train our neural network, we increase or decrease these weights depending on the data it sees in order to optimize a loss function. The parameters occupy constant memory as there is only 1 copy of the weights and biases for the model. We do not need to allocate additional memory as training the model only requires us to update the values of these weights and biases.</p><p><strong>2. Gradients (dark blue)</strong></p><p>Gradients refer to the change in the weights with respect to change in loss. Each layer of your deep learning model is essentially a series of functions chained together that are differentiable. In order to perform gradient descent, we must compute the gradients of the loss with respect to the weights in order to perform <a href="https://developers.google.com/machine-learning/crash-course/reducing-loss/gradient-descent">gradient descent</a>.</p><p><strong>3. Activations (red)</strong></p><p>Activations are intermediate results of your model that are stored in memory when we construct the computation graph. It is sometimes hard to predict how much memory activations would consume as it depends on batch size and the model architecture.</p><p><strong>NOTE on both activations and gradients!!!</strong></p><p>From Figure 1, an interesting observation is that we can observe cyclic peaks in activation memory. Another observation is that as activation memory decreases, we allocate more and more memory for gradients. To explain this, we may use this animation created by the creators of one of the memory optimization techniques we will cover later. This animation represents the vanilla back-propagation algorithm.</p><p>Each node on the top row represents activations of different layers in your model while nodes on the bottom represent the gradients of the loss with respect to activations and parameters of these layers. During the forward pass we evaluate the nodes in order and in reverse order during backward pass. Purple nodes represent nodes that are taking up memory at a given time. An arrow represents a data dependency for computation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/541/0*EnNZ7G834uLFnQZf.gif" /><figcaption>Figure 2: Diagram of a full computation graph with vanilla back-propagation from <a href="https://github.com/cybertronai/gradient-checkpointing">https://github.com/cybertronai/gradient-checkpointing</a></figcaption></figure><p>This computation graph helps us explain the memory behavior we see from Figure 1. The activation memory (red) increases as more and more layers are evaluated and we store more activation tensors, keeping in mind that we have not evaluated the backward graph. When that is complete, we perform backward pass and gradually release activation nodes from memory and we only keep activations that are necessary for gradient computation (blue) until we complete it for all layers.</p><p><strong>4. Optimizer States (yellow)</strong></p><p>Optimizer states store the attributes of the optimizer for parameter groups. The role of the optimizer is to update the parameters of a network by using the gradient of the loss with respect to the weight ∂L/∂w at a certain iteration t.</p><p>For this article, we will focus on one of the most popular optimizers used in modern deep learning models which is the Adam optimizer. It is well known for its memory efficiency and training stability compared to other optimizers such as AdaGrad and RMSProp.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-ztDuv4Al49_kWZk5v420g.png" /><figcaption>Figure 3:Adam Optimization algorithm</figcaption></figure><p>In the <a href="https://towardsdatascience.com/the-math-behind-adam-optimizer-c41407efe59b#e382">Adam optimization algorithm</a>, we update the parameters based on a moving average of the first moment vector and a second moment vector[3]. What makes Adam unique is that we can apply individual learning rates to each parameter influenced by the first moment (momentum of the paramters) and the second moment (variability of the parameters), which allows for more efficient training with larger models. In terms of memory consumption, this algorithm requires us to store a first moment vector and a second moment vector, each has the same size as the number of parameters you have in your model, which is why you see that the optimizer states occupy approximately 2x the amount of memory than the parameters. This is logical because under the Adam optimizer, we keep track of 2 quantities for each parameter in our model (momentum and variance). And you may notice that memory is not allocated until the first training iteration. This is because optimizer states are not computed and stored until the completion of the first forward and backward pass.</p><p>We now observe these memory behaviors and provided some preliminary diagnosis. What comes after that? Treatment! Once a doctor understands what the underlying illness is and makes a medically reasoned diagnosis, they will decide on a treatment plan for their patient in order for them to combat their illness and recover. Picking the right memory optimization technique is the exact same idea. Different methods tackle different memory bottlenecks and may be effective towards your use case depending on where your bottleneck is. Here I propose 5 research advances in optimization that you may find helpful.</p><h3>Treatment: Memory optimization techniques</h3><ol><li><strong>Gradient check-pointing (</strong><a href="https://arxiv.org/pdf/1604.06174.pdf"><strong>Paper</strong></a><strong>)</strong></li></ol><p>Gradient check-pointing finds a way to balance between recomputing activation nodes and memory cost. Developed by Tim Salimans and Yaroslav Bulatov, they proposed a way of checkpointing or preserve some nodes in memory and we utilize these checkpointing to compute other remaining nodes at most once. One thing to note is that the checkpoint node is kept in memory after the forward pass.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*OxzQFzLkCCqFl4ne.png" /><figcaption>Figure 4: adding a checkpoint node to computation graph</figcaption></figure><p>Let’s assume that we mark the circled node as the checkpoint.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/541/0*Kk5ckpIX3GWTCw4S.gif" /><figcaption>Figure 5: gradient checkpointed computation graph</figcaption></figure><p>If we pay attention to the computation graph with a checkpoint node, we release the stored activation nodes as soon as they are no longer required.</p><p>Authors of this work found that dividing the entire network into K chunks and marking the node at every K = sqrt(n) chunk as a checkpoint is the most optimal, where n is the number of layers in your network[4]. To calculte the activations of all the other nodes is equivalent to at most running forward pass once. Doing so allows us to reduces the amount of memory sub-linearly proportional to the number of layers in our network rather than linearly. Intuitively, you can compare the vanilla backprop with gradient checkpointed backprop and see that less nodes are actively consuming memory at a given time (less purple nodes at once).</p><p><strong>2. Flash Attention (</strong><a href="https://arxiv.org/pdf/2205.14135.pdf"><strong>Paper</strong></a><strong>)</strong></p><p>In a lot of models with transformer-based architectures, the attention mechanism is the main backbone for their ability to establish meaningful connections between tokens in sequential data, yet this operation can impose significant overhead as well as memory consumption. Researchers of this method take advantage of the hierarchical structure of GPU memory and running attention computations on GPU SRAM which has greater memory speed, rather than HBM (high bandwidth memory)[5].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*pjscGWLNvBlTp0oCo3iNmA.png" /><figcaption>Figure 6: Flash attention diagram with memory hierarchy</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZRVoBNHPgXjgX0co-dvpwQ.png" /><figcaption>Figure 7: Standard attention algorithm</figcaption></figure><p>In original attention implementation the operation Q•K^T involves computing the attention weights between all tokens. This procedure along with the softmax operation requires repeatedly reading and writing within the HBM, which leads to a large amount of memory accesses for every block. Furthermore, previous implementations requires storing intermediate tensors S and P in order to compute gradients with respect to Q,K,V for backpropagation, which can increase memory usage.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*970AsdeZW21Sj9UE6JB6Nw.png" /><figcaption>Figure 8: Flash Attention algorithm. Red box indicates section of faster attention computation moved to SRAM</figcaption></figure><p>With flash attention, the authors propose to use tiling and recomputation to reduce memory accesses as well as to lower memory usage on storing intermediate activations. <strong>Tiling</strong> basically divides the attention computation into blocks, each block is moved to SRAM for fast computation and we combine the results and move it back to HBM. <strong>Recomputation</strong> allows us to omit saving intermediate tensors S and P (selective form of gradient checkpointing). With the output O and softmax normalization statistics (m and l), we can recompute S and P easily with block of Q,K,V already in SRAM.</p><p><strong>3. 8-bit Adam optimizers (</strong><a href="https://arxiv.org/pdf/2110.02861.pdf"><strong>Paper</strong></a><strong>)</strong></p><p>As discussed optimizer states keep track of gradient statistics over the course of training. However, these statistics from the Adam optimizer for instance consume a considerable amount of memory. This work leverages quantization to maintain 8-bit statistics of the optimizer states rather than 32 bits, while preserving performance through block-wise dynamic quantization[6].</p><p>In brief, quantization is the act of mapping k-bit integers to a real element, usually represented by 32bits. We do so by mapping the input tensor to a domain in the desired quantization data type, then find the closet value in domain D and finally store the quantized value.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/576/1*PROhvRxrqkGeJH9WhaFgGw.png" /><figcaption>Figure 9: equation for quantization</figcaption></figure><p>This equation establishes the relationship between quantized (T^Q)and de-quantized tensors (T^D). N represents the normalization constant for transforming to the quantized range (usually N = max(|T|)), Q^map represents the mapping from [0,(2^k)-1]-&gt;D. If you wish to learn more about the details of quantization, you can check out this awesome article by <a href="https://medium.com/@qujeremy3/b1212160d86a">Jeremy Qu</a>!</p><p>Building on top of his explanations, block wise quantization is a method of reducing quantization error and improves training stability by chunking the optimizer state tensors into different blocks and computing a normalization constant for each block.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mZIN0Ro8ZU4pIYMLUXkLcA.png" /><figcaption>Figure 10: block wise dynamic quantization</figcaption></figure><p>This blocking mechanism allows for more robust outliers in the input tensor by minimizing the unused range of the quantization bucket and restricting the effect of outliers to a single block. (Learn more about it here!)</p><p><strong>4. LoRA fine-tuning (</strong><a href="https://arxiv.org/pdf/2106.09685.pdf"><strong>Paper</strong></a><strong>)</strong></p><p>Low Rank Adaptation is a fine tuning technique that significantly reduces memory consumption by making the weight updates much more parameter efficient.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/363/1*OKIt3GsRE215jzKL48xZ3w.png" /><figcaption>Figure 11: LoRA parametrization, x is the input to both W and A•B</figcaption></figure><p>When we talk about low rank matrices, we are essentially saying that the matrix has columns or rows that can be expressed as a linear combination of each other (not linearly independent). Hence we can find a representation that is lower dimensional but still captures the essential information of this matrix[7].</p><p>This idea of using low rank matrices for weight updates makes it easier to fine tune large models to different downstream tasks. When we perform fine-tuning on for example a weight matrix W of a linear layer, instead of performing W+ΔW, we use low rank decomposition to represent ΔW (d x r) with 2 matrices A and B where B is d x r and A is r x k. Thus during fine-tuning the pre-trained weights W are frozen while AB are trainable. Authors of LoRA realises that there exists some low “intrinsic dimension” to the update matrices and can achieve similar performance as full parameter training[8].</p><p>With this new method, our forward pass would look something like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/459/1*MOgGeE-1N8rGRn1loqY1Dg.png" /><figcaption>Figure 11: LoRA modified forward pass equation (W_o is frozen, BA are low rank adapted matrices)</figcaption></figure><p>LoRA has allowed many researchers to fine tune large language models, diffusion models etc to their own applications and use cases. In terms of memory reduction, LoRA allows us to reduce the number of training parameters by a significant portion (on GPT3 with 175B parameters, GPU memory was reduced by 3x).</p><p><strong>5. GaLoRe Gradient Low Rank Projection (</strong><a href="https://arxiv.org/pdf/2403.03507.pdf"><strong>Paper</strong></a><strong>)</strong></p><p>GaLore is a much more recent work (literally published 2 weeks ago) that made significant breakthroughs in memory efficiency and builds upon the idea of low rank projections from LoRA. Instead of limiting the parameters to low-rank, this work performs a low rank update on the gradients instead of the parameters[9].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/740/1*V521ZWssX_cZj70wE33RQQ.png" /><figcaption>Figure 12: GaLore pseudocode algorithm</figcaption></figure><p>Their formulation retains all the original parameters of the pretrained model. However, GaLore proposes to compute 2 projection matrices P and Q that projects the gradient matrix to and from a low dimensional sub-space when we perform a gradient update optimizer.step(). GaLoRE is much more memory efficient AND than LoRA due to several properties in their methodology:</p><p>a) LoRA requires storing the activations of the original parameters as well as the non-LoRA parameters while GaLore only requires the activations of the full parameters set.</p><p>b) GaLore does not require storing seperate low rank matrices A•B as the ΔW is directly applied to the pretrained weights during a weight update (i.e. the last step in Figure ).</p><p>c) GaLore is adaptable to Adam and further saves memory on optimizer states as theses statistics would have the same dimensionality as the low rank gradients. They can also be adapted to 8-bit Adam, which further reduces memory requirements for storing the statistics.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/619/1*s6pB5APMibh0XBbF1NmfZg.png" /><figcaption>Figure 13: GaLore VS LoRA comparison</figcaption></figure><p>GaLore made it possible for a consumer level GPU RTX4090 24GB to perform pretraining on a LLaMA model with 7B parameters without applying any other memory optimization tricks. This marks a significant milestone of making billion parameter model training, fine-tuning much more accessible to the ML/AI community.</p><h3>Final Remarks</h3><p>To summarize all the methods described above, this table is an overview of the memory bottlenecks these methods may help with.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/481/1*jyP80OSqMGnsWZeezTwNaQ.png" /><figcaption>Figure 14: Overall comparison of all the methods</figcaption></figure><p>With the right memory optimization methods, you can reduce training costs on your models significantly and bring those ML project ideas of yours into a reality on your hardware!</p><h4>References</h4><ol><li><a href="https://pytorch.org/blog/understanding-gpu-memory-1/">https://pytorch.org/blog/understanding-gpu-memory-1/</a></li><li><a href="https://pytorch.org/blog/computational-graphs-constructed-in-pytorch/">https://pytorch.org/blog/computational-graphs-constructed-in-pytorch/</a></li><li><a href="https://towardsdatascience.com/the-math-behind-adam-optimizer-c41407efe59b#e382">https://medium.com/r/?url=https%3A%2F%2Ftowardsdatascience.com%2Fthe-math-behind-adam-optimizer-c41407efe59b%23e382</a></li><li><a href="https://github.com/cybertronai/gradient-checkpointing">https://github.com/cybertronai/gradient-checkpointing</a></li><li><a href="https://arxiv.org/pdf/2205.14135.pdf">https://arxiv.org/pdf/2205.14135.pdf</a></li><li><a href="https://arxiv.org/pdf/2110.02861.pdf">https://arxiv.org/pdf/2110.02861.pdf</a></li><li><a href="https://blog.ml6.eu/low-rank-adaptation-a-technical-deep-dive-782dec995772#:~:text=Low%2DRank%20Matrix%3A%20A%20rank,min(m%2C%20n).">https://blog.ml6.eu/low-rank-adaptation-a-technical-deep-dive-782dec995772#:~:text=Low%2DRank%20Matrix%3A%20A%20rank,min(m%2C%20n).</a></li><li><a href="https://arxiv.org/pdf/2106.09685.pdf">https://arxiv.org/pdf/2106.09685.pdf</a></li><li><a href="https://arxiv.org/pdf/2403.03507.pdf">https://arxiv.org/pdf/2403.03507.pdf</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fe3d9b8a6b5e" width="1" height="1" alt=""><hr><p><a href="https://medium.com/demistify/memory-optimization-cure-out-of-memory-errors-like-a-doctor-fe3d9b8a6b5e">Memory optimization: Cure Out Of Memory errors like a doctor</a> was originally published in <a href="https://medium.com/demistify">deMISTify</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Adversarial Diffusion Distillation: the return of GANs in generative modelling???]]></title>
            <link>https://medium.com/demistify/adversarial-diffusion-distillation-the-return-of-gans-in-generative-modelling-bc56b59b765f?source=rss-e6b3bc2634c3------2</link>
            <guid isPermaLink="false">https://medium.com/p/bc56b59b765f</guid>
            <category><![CDATA[diffusion-models]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[generative-adver]]></category>
            <category><![CDATA[distillation]]></category>
            <dc:creator><![CDATA[Ambrose Ling]]></dc:creator>
            <pubDate>Tue, 16 Jan 2024 18:00:07 GMT</pubDate>
            <atom:updated>2024-01-16T18:00:07.071Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DIOgrAMhxDOkAWPcK40mHg.png" /><figcaption>Image generated by DALL-E with the prompt: “A very powerful diffusion model”</figcaption></figure><h3>Introduction</h3><p>Generative AI is a familiar phrase that has infiltrated every part of our lives. Whether it is helping you write that essay due tomorrow with ChatGPT or using Adobe generative fill to make yourself look like you’re 6 foot 2, it is a piece of technology we cannot stop talking about. In particular, image generation with diffusion models, such as <a href="https://www.midjourney.com/home?callbackUrl=%2Fexplore">Midjourney</a>, <a href="https://stablediffusionweb.com/WebUI">Stable Diffusion</a>, <a href="https://openai.com/dall-e-2">DALL-E</a>, has been a rapidly developing field of research within generative AI over the past decade. Deep learning scientists and researchers are constantly discovering new ways to improve the generation quality as well as the generation speed of diffusion models, because who would want to wait 5 minutes just to generate something that’s not what you’re looking for?</p><p>In this article, I will introduce a recently developed method of image generation called Adversarial Diffusion Distillation (ADD), that leverages the power of GANs as well as knowledge distillation techniques to reduce generation time while maintaining high-quality samples. I will first give a brief overview of each of the components of this new method and gradually put them all together. Let’s dive into it!</p><h3>Adversarial</h3><p>When we talk about adversarial, we are referring to a framework very similar to Generative Adversarial Networks (GANs). GANs are a type of generative models that are comprised of 2 components, a generator and a discriminator.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*EF0rU_DY1sbmBzOwdEC7Ow.png" /><figcaption>Architecture of a GAN model, taken from <a href="https://developers.google.com/machine-learning/gan/gan_structure">https://developers.google.com/machine-learning/gan/gan_structure</a></figcaption></figure><p>You can imagine the generator as the counterfeiters and the discriminator as the police. The counterfeiters are constantly trying to generate fake currency as realistic as possible, while the police are trying to detect the fake currency. The generator takes in random noise and tries to generate a denoised, clean sample/image. The generator plays the role of learning an input data distribution and tries to samples from this distribution during generation. The discriminator receives input samples and plays the role of determining the probability that this sample belongs to either the real data distribution or the generator distribution. Both models are trained simultaneously with the same objective. From the original GAN paper, the training objective can be formulated as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FEWA_UA7pO-HzzTG97fTYw.png" /></figure><p>This objective tells us that we are training the discriminator D to maximize this entire loss expression (maximize the probability that D assigns the correct label to the given sample). On the contrary, the generator G is trained to minimze log(1-D(G(z)) (minimize the probability that D identifies the correct label given a sample from the generator).</p><p>One strength of GANs is that it allows for quick and efficient sampling since there is no iterative process. You can directly retrieve a generated sample by inputting noise into the generator. However, GANs are difficult to train because of several reasons:</p><ol><li>Mode collapse — This occurs when the generator fails to generate a diverse variety of images in order to fool the discriminator, which greatly impacts generation quality.</li><li>Vanishing gradients — If samples from the generator are poor in the beginning, the discriminator could result in high confidence, which results in small losses and gradient updates to the generator.</li></ol><p>For these reasons, there has been a barrier for GANs to achieve greater performance when it comes to generation diversity or capturing the full range of the data distribution.</p><h3><strong>Diffusion</strong></h3><p>Diffusion models are a different type of generative model with a iterative diffusion (forward) and denoising (reverse) process.</p><p><strong>In the forward process</strong>, we iteratively destroy structure in the data by injecting Gaussian noise into the original signal x_0 for a certain number of steps until it is transformed into pure noise x_T with normal distribution N(0,I). We use a noise scheduler to control how much noise is added to the original signal at each step.</p><p>In ADD, the forward diffusion process looks something like this via the reparametrisation trick:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/210/1*LBZbgR_HgJzTOvuBCQ_C4Q.png" /></figure><p>x_0 represents the original signal and epsilon represents noise sampled from a Gaussian distribution. x_s represent the noisy signal after applying noise for s steps. The coefficients of x_0 and epsilon represent the noise schedule (dictating how much of the original signal should I keep and how much pure noise shoud be added). For more about how noise schedules work, you can check out these <a href="https://arxiv.org/pdf/2301.10972.pdf">resources</a>. On a high level, it is just a way of representing the noise level present in our current sample.</p><p><strong>In the reverse process,</strong> we train a neural network to either predict how much noise should be removed from x_T to obtain the original signal x_0 at each step <strong>OR</strong> we predict the original signal x_0 directly (which is what ADD’s diffusion model does). We repeatedly remove noise until we get to a denoised version of the image. We usually refer to the reverse process as the sampling process and the number of times we repeat this noise removal as sampling steps.</p><p>The sampling process is an entire field of research itself and can be completely indepedent from the forward process. There have been many different samplers developed to reduce the number of sampling steps required while maintaining the sample quality. We won’t cover much about sampling in this article as ADD’s architecture enables a very simple sampling process. However, I will attach some useful links you can explore if you are interested.</p><p>The most common model architecture used for this neural network is a U-Net, which is composed of a series of residual and attention blocks with a large number of convolutional layersr that capture crucial spatial information about the image.</p><p><strong>How are diffusion models trained?</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*y1ip1_X1PZoBXn6x0GU-Xg.png" /><figcaption>Standard training procedure for diffusion models, taken from <a href="https://arxiv.org/pdf/2202.00512.pdf">https://arxiv.org/pdf/2202.00512.pdf</a></figcaption></figure><p>Here is a standard way of training diffusion models:</p><ol><li>Sample a random image <strong>x</strong> from your dataset, a random timestep <strong>t</strong> and a random noise vector <strong>epsilon</strong></li><li>Add noise to the image for <strong>t</strong> amount of time steps</li><li>Predict the denoised version of the image and compute the loss btw the original image and the predicted</li><li>Perform gradient descent until convergence</li></ol><h4>Distillation</h4><p>Distillation or Knowledge Distillation is a technique developed to “distill” the knowledge from of a much more powerful model to a smaller model. Distillation can generally be applied when we want to deploy smaller models on edge devices or when we wish to decrease the memory demands from our model while maintaining the performance of a powerful model.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8_eGGeMFZxBCTSx6gXiyIA.png" /></figure><p>Above is a simple example of a basic knowledge distillation framework, where we denote the difference between the teacher logits and student logits as distillation loss. And the students weights are updated based on that loss.</p><p>In diffusion models, distillation can also be as a method used to reduce the number of iterative sampling steps. This can be achieved by distilling knowledge from a teacher model trained on a larger number of sampling steps to a student model capable of achieving similar generation quality but with fewer steps. Methods such as <a href="https://arxiv.org/pdf/2202.00512.pdf">Progressive Distillation</a>, <a href="https://arxiv.org/pdf/2303.01469.pdf">Consistency Model Distillation</a> have been applications of distillation in diffusion models.</p><h3>Adversarial Diffusion Distillation</h3><p>This paper puts together the 3 aforementioned concepts together to form ADD. ADD aims to solve a few problems:</p><ol><li>Sampling speed is too slow for diffusion models with a large number of sampling steps</li><li>Exsiting distillation methods still exhibit some blurriness in generation results</li><li>Sample quality deteriorates with less sampling steps</li></ol><p>ADD’s method combines the superior sample quality of existing pretrained diffusion models as well as the speed of GANs. Let’s break down their whole training procedure:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*TR9uLrBYCoRketNFuFT4nw.png" /></figure><p>ADD first samples an image from the real data distribution x_0. It applies the forward diffusion process to get a noisy image. The student and teacher model are both initizlied as a pretrained diffusion model (specifically a Stable Diffusion UNet). However only the teacher parameters are frozen. The student predicts the original signal given some noisy signal that has applied forward diffusion. Generated samples from the student are passed to a discriminator. The discriminator has 2 parts: a feature network F that is a ViT (Vision Transformer) and a discriminator head that is a classifier.</p><p>The authors also used techniques to condition the discriminator on additional information such as text or the original image, which encourages the ADD student model to extract meaningful information from the input.</p><p>We then take the denoised prediction from the student and apply forward diffusion again, that acts as the input to the teacher model. We then take the denoised predictions from the teacher and we use that as a reconstruction target (an example for the student to mimic).</p><p>The overall objective used to train the ADD-student model can be summarized as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/954/1*TRDEyPi5YRFW4NfEsYl1UA.png" /></figure><p><strong>Adversarial Loss:</strong></p><p>The introduction of an adversarial loss term essentially helps the student model generate images as realistic as possible, pushing the generated samples close to the actual data distribution.</p><p><strong>Distillation Loss:</strong></p><p>The distillation loss term (see from the figure) uses a distance metric <strong>d</strong> to measure the mismatch between the teacher’s generation and the student’s generation. This term is what forces the student to mimic the compositionality that is present in the teacher predictions. Notice how we needed to apply noise to the student generation result , that is because the pretrained unet was trained on a distribution of diffused inputs (we always apply noise to the image, then give it to the model). Giving it a denoised version by the student would fall out of the input training distribution.</p><h3>Notable Results</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9JlZ85RiH1LhLHfAhy-1IA.png" /></figure><p>The authors showed that their method was able to outperform a great variety of SOTAs in both inference speed and <a href="https://en.wikipedia.org/wiki/Fr%C3%A9chet_inception_distance">FID</a> score (a score to evaluate the quality of generation, lower is better) with it being able to perform only 1 sampling step.</p><p>The authors also conducted a variety of ablation experiments to help them make a few important decisions:</p><ol><li>Conditioning the discriminator on both the text and the image was shown to improve generation quality.</li><li>The adversarial loss was incredibly crucial to its high fidelity samples. Both the adversarial and distillation loss are needed to achieve optimal performance.</li><li>Initialisation of the student to a pre-trained stable diffusion UNet was crucial to its performance.</li></ol><p>The authors also performed user preference studies to evaluate the generation quality. Their method was shown to have an ELO score that surpassed other SOTAs.</p><h3>Impact</h3><p>ADD was truly a jaw dropper as it was surprising to see GANs return to generative modelling in a way that compliments existing diffusion models. It has demonstrated its strong capability in maintaining generatin quality while enabling fast sampling, which puts them ahead of the state-of-the arts. Diffusion models have always experienced this barrier of deployment because of its large model size and need for iterative sampling. However, these new training techniques proposed by ADD could potentially enable the rise in popularity for diffusion models to be easily deployed on edge devices at a scale greater than before. Users can embrace creative endeavours in image generation with great ease, bringing their artistic ideas to life in a matter of seconds. These possibilities are what make these small breakthroughs super exciting to see.</p><h3>References</h3><ol><li><a href="https://arxiv.org/abs/2202.00512">https://arxiv.org/abs/2202.00512</a></li></ol><p><a href="https://arxiv.org/pdf/2311.17042.pdf">2. https://arxiv.org/pdf/2311.17042.pdf</a></p><p>3. <a href="https://arxiv.org/abs/1406.2661">https://arxiv.org/abs/1406.2661</a></p><p>4. <a href="https://www.youtube.com/watch?v=tT9Lnt6stwA">https://www.youtube.com/watch?v=tT9Lnt6stwA</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=bc56b59b765f" width="1" height="1" alt=""><hr><p><a href="https://medium.com/demistify/adversarial-diffusion-distillation-the-return-of-gans-in-generative-modelling-bc56b59b765f">Adversarial Diffusion Distillation: the return of GANs in generative modelling???</a> was originally published in <a href="https://medium.com/demistify">deMISTify</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Multi-Agent Trajectory Prediction: Bringing deep learning to the beautiful game.]]></title>
            <link>https://medium.com/demistify/multi-agent-trajectory-prediction-bringing-deep-learning-to-the-beautiful-game-6a60191faf6c?source=rss-e6b3bc2634c3------2</link>
            <guid isPermaLink="false">https://medium.com/p/6a60191faf6c</guid>
            <category><![CDATA[graph-neural-networks]]></category>
            <category><![CDATA[sports-analysis]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[temporal-convolutional]]></category>
            <category><![CDATA[deep-learning]]></category>
            <dc:creator><![CDATA[Ambrose Ling]]></dc:creator>
            <pubDate>Tue, 14 Nov 2023 00:55:40 GMT</pubDate>
            <atom:updated>2023-11-14T00:55:40.294Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*3Bg3IPwkAXHXGue5jzf7wA.jpeg" /><figcaption>Picture from <a href="https://www.thestandard.com.hk/section-news/fc/4/254535/Saved-by-the-ball">https://www.thestandard.com.hk/section-news/fc/4/254535/Saved-by-the-ball</a></figcaption></figure><h3>Introduction</h3><p>Growing up as a fan of football, I almost never said no to a pick up game with friends after school. I was practically addicted to the game. For me, what makes the game so exhilarating isn’t just the satisfaction you get from dribbling past a defender, but also the ability to advance forward as a unit, making those crucial passes and creating space for your teammates to score as a team. When I was first exposed to the sport, I started to admire how players in top professional football teams, such as Barcelona, were extremely intelligent in the way they manipulated space and formed these networks to maximize passing efficiency and success rates. Every player was purposeful with their movement and how they influence the movement of others. With the perfect symphony of precise passes, clever movement and individual skill, you get a winning team that is to be feared.</p><p>However when it comes to understanding all the intricate variables that could lead to victory or defeat, it is certainly not an easy task. A lot of clubs are trying to better understand the patterns that naturally occur in a successful team through various statistical methods. With the rise of artificial intelligence, there has been growing applications of machine learning algorithms in helping teams learn strategies, player interactions and movement around the court during a game. In this article, I will talk about how authors of [1] used deep learning in the form of graph attention networks (GAN) and temporal convolutional networks (TCN) were employed for predicting the players position during a game.</p><h3>The Problem</h3><p><strong>What is multi-agent trajectory prediction?</strong></p><p>In simple terms, we want to predict how the players and the ball move.</p><p>We can treat each entity that we find interesting as an agent. In the context of sports games, each player along with the ball would be an agent. So for instance in basketball, we would say there are 11 agents in basketball (5 players per team x 2 teams +1 ball) or 23 agents in football (11 players per team x 2 teams + 1 ball). For a given time step t, an agent’s location can be represented by a 2-D vector x_k^t, where i ≤ K, K is the number of agents. Hence all agents can be represented by:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/461/1*hn8mp3-HcI2HokBVquEqDg.png" /></figure><p>We can represent a series of snapshots of the agent’s location as a demonstration D_i:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/322/1*p8TpTEPLOriNVUAOjMeGvQ.png" /></figure><p>Our full dataset can be represented as a collection of these demonstrations D:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/310/1*k_ZLDuPYJl17Z2hCkCa0kA.png" /></figure><p>Our goal is to predict the future states of all the agents M time steps into the future, where M is some constant.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/237/1*Eo4Ypx0BlpjwEJtyngCV5w.png" /></figure><p><strong>Why perform multi-agent trajectory prediction?</strong></p><p>The goal of multi-agent trajectory prediction is to forecast the movement of each of these agents some time steps into the future, given the past movement of all agents. For sports, being able to successfully predict the agent trajectories could become extremely useful in devising tactics, tailoring attacking strategies to exploit weaknesses of opponents, discovering partnerships between players and many more. These predictions could inspire small improvements in team play, potentially leading to the team securing those 3 points.</p><p>There are also other applications of multi-agent trajectory prediction such as autonomous driving. In this context, agents are now vehicles. Its difficulty lies in accurately predicting the behaviour of different agents based on the complex scene context (what is happening in the environment). Powerful predictive methods can help autonomous vehicles make informed decisions that keep the drivers safe. However we are going to focus on the sports application in this article.</p><h3>Method</h3><p><strong>Introduction to proposed architecture</strong></p><p>A new neural network architecture<strong> </strong>has been developed that combines the power of graph attention networks and temporal convolutional networks to to learn intricate spatial relationships of players and the evolution of movement and agent coordinates over time simultaneously. Let’s dive into how they work!</p><p><strong>What are graph attention networks?</strong></p><p>We can start by representing all the agents as nodes in a graph. A graph G with a set of nodes V and a set of edges E. We denote the 2-dimensional location of an agent k at time t with a vector x^t,k for t in R (time step of interest), and for k ≤ K (number of agents).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/125/1*ZEmLv4y0cMhRYnFISkgnGw.png" /></figure><p>We can then denote a vector of agent i as h_i that describes the features of the agent in our graph, and our graph attention layer will receive h, the node feature matrix, as input for all agents and outputs a new learned node embedding matrix h’.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/272/1*DK1r_Um9oImtp4MJXo3TIQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/282/1*dPoxvPXAsTg6XtiLx5fy6w.png" /></figure><p>The key idea behind this graph attention layer is to weigh the importance of a nodes to all other nodes in the graph by computing a pair-wise attention score.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/562/1*cvXWOwAXUIO9KmMZvjC3Gg.png" /></figure><p>We can do so by performing a series of linear transformations with the node feature vectors hi and hj with learnable weight matrices W and a, and this score would represent the importance of node j’s feature to node i. I personally like visualizing the step by step matrix transformations so here’s a diagram to show it:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/695/1*uP4GhiXV2qhvKwb7fHmEVA.png" /><figcaption>Figure showing the attention score computation in matrix form.</figcaption></figure><p>We then normalize all the scores across all neighbors of node i using the SoftMax function, and this principle is called masked attention: you are masking away unimportant nodes / not allowing nodes to attend to distant, unrelated nodes. Below shows the row-wise normalization with Softmax:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/260/1*dHgp0CCONynKwBQiLBh9PA.png" /></figure><p>With the attention scores computed, we can compute new embeddings for agent i by aggregating the weighted node embeddings over the neighborhood of i.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/269/1*qw6jZw8Wo7V5yBe1jZx8kw.png" /></figure><p>Lastly we perform a pooling/aggregation step to create an overall representation of the entire graph by summing all the final agent embedding vectors into one graph embedding at some time t.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/138/1*jK6F0EGpDENPDNVulmU0tA.png" /></figure><p><strong>What are Temporal Convolutional Networks?</strong></p><p>Now since we want to predict how the agents evolve over time in their movement, we would need to use a method of aggregating past information of the agent’s movement. The authors of this paper used a sequence model called Temporal Convolutional Networks, which are essentially stacks of 1-D dilated causal convolutional networks.</p><p>The model takes in an input sequence of graph embeddings that is generated from the attention block / spatial module:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/279/1*TTM9VI0_PMh0lQy1r2mmBA.png" /></figure><p>and predicts a sequence of graph embeddings:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/349/1*ZHSPb0BrBViJvolJLPJjFQ.png" /></figure><p>To refresh your memory on 1-D causal convolution, I made the following diagram to illustrate the idea. Every entry in the output sequence is resulted by convolving a kernel filter with the input sequence. (i.e. the last element of output sequence is the convolution of the last 3 elements of the input sequence with a filter of size 3) [3].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/265/1*kl2rnx3FngABw-lSG23UGg.png" /><figcaption>Figure showing 1D convolution; every 3 lines represents a convolution with a kernel of size 3</figcaption></figure><p>For a convolution to be causal, every entry in the output sequence must be dependent on entries in the input sequence that come before it. (i.e. Within my sequence, information at time t+1 should not influence what happens at time t or any time before it). In order to do so, zero-padding is applied, where zero-valued elements are added to the beginning of the sequence (boxes in grey).</p><p>But there is a limitation currently because ideally an element in the output should be contributed by all the elements that come before it in the input. (A player could result in this movement because of space created by another player a number of time-steps ago or a decision made by a teammate at the beginning of the game, not just 3 time steps ago for example). This is where dilation comes in, which expands the size of the kernel by inserting gaps in between consecutive elements.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/516/1*djuulazRIP0UnJa12hd0yw.png" /><figcaption>Figure showing 2 layers of 1D convolution with; first layer has 1 dilation, second layer has 2 dilations (1 gap in between consecutive elements in the kernel filter)</figcaption></figure><p>If you stack 1-D convolutional layers with an exponential number of dilations in each layer (the why is covered in this <a href="https://unit8.com/resources/temporal-convolutional-networks-and-forecasting/">article</a>), you will be able to form a TCN where full history coverage is achieved, meaning each element of the output is influenced by all the elements that come before it in the input.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/739/1*FwWoUuJhDs65CaCBJ0h6gQ.png" /><figcaption>Figure showing overall TCN architecture; each block represents a series of 1D convolution layers with exponentially increasing number of dilations (d) with base 2.</figcaption></figure><p>The authors also used non-linear activation functions to introduce non-linearities to the outputs for learning more complex representations. Residual connections and dropout was also used as a regularization technique to combat overfitting.</p><p><strong>The Final Model</strong></p><p>Putting everything together, you get a graph attention encoder that encodes the spatial relationships between all agents into a global graph embedding at each time-step. And a sequence of these embeddings gets passed into the TCN decoder to learn the temporal dependencies and predict a sequence of future graph embeddings. These graph embeddings are later passed to a fully connected layer and converted back to x,y coordinates.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6BhunkOBR4CErAv5Ekj4fQ.png" /><figcaption>Figure showing overall architecture of the multi-agent trajectory prediction model</figcaption></figure><h3>Results</h3><p>Their results show that for a majority of the metrics, this model showed promising performance in predicting the agents trajectory by a significant margin for mixed teams . The authors used L2 error , max error as well as miss rate as their evaluation metrics. They then observed the performance of their model on a football dataset as well as a basketball dataset where each demonstration was 10 seconds.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*k0tDFctxIrsNoNh3-Uowrg.png" /><figcaption>Table showing the result comparisons between SOTAs and the author’s model tested on both basketball and football datasets.</figcaption></figure><p>An interesting result that they reported was that attention-based techniques showed higher performance in predictions with specific teams compared to predictions with mixed teams. This could possibly be because of attention having the ability to attend to event specific patterns for a specific team.</p><h3>Next Steps</h3><p>As machine learning methods continue to advance, there are going to be more and more opportunities to improve sports analytics. Although the authors did not explore other intentions beyond trajectory prediction, I personally think the possibility for deep learning models to learn abstract representations of tactics is getting closer and closer, even generative AI models for creating new attacking plans. I surely see these models being extended outside of basketball or football to inspire new strategies for other sports driven by artificial intelligence.</p><h3>Sources</h3><ol><li><a href="https://arxiv.org/abs/2012.10531">https://arxiv.org/abs/2012.10531</a></li><li><a href="https://arxiv.org/abs/1611.05267">https://arxiv.org/abs/1611.05267</a></li><li><a href="https://unit8.com/resources/temporal-convolutional-networks-and-forecasting/">https://unit8.com/resources/temporal-convolutional-networks-and-forecasting/</a></li><li><a href="https://arxiv.org/abs/1710.10903">https://arxiv.org/abs/1710.10903</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6a60191faf6c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/demistify/multi-agent-trajectory-prediction-bringing-deep-learning-to-the-beautiful-game-6a60191faf6c">Multi-Agent Trajectory Prediction: Bringing deep learning to the beautiful game.</a> was originally published in <a href="https://medium.com/demistify">deMISTify</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>