Video wird geladen...
Video konnte nicht geladen werden
[Graph Convolutional Network] by hand ✍️ Graph Convolutional Networks (GCNs), introduced by Thomas Kipf and Max Welling in 2017, have emerged as a powerful tool in the analysis and interpretation of data structured as graphs. This exercise demonstrates how GCN works in a simple application: binary classification. -- Goal... show more
46,779 Aufrufe • vor 2 Jahren •via X (Twitter)
0 Kommentare
Keine Kommentare verfügbar
Kommentare vom Original-Post werden hier angezeigt
![[Deep RNN] by Hand ✍️ A Deep Recurrent Neural Network (RNN) extends a basic single-layer RNN into multiple layers of hidden states, effectively incorporating deep learning into the RNN architecture. How does a Deep RNN work? [1] Given ↳ A sequence of four inputs X1, X2, X3, X4 ⬛️ ↳ Recurrent weights and biases for hidden layers a 🟩, b 🟧, c 🟪, and the output layer y 🟦. [2] Initialize Hidden States ↳ Set a0, b0, c0 to zeros — Process X1 (t = 1)— [3] First Hidden Layer (a) 🟩: a0 → a1 ↳ The transformation matrix is horizontal concatenation of input weights, hidden state weights and biases, visualized as [⬛️ | 🟩 | ⬜️] . ↳ The state matrix is vertical concatenation of input X1, previous hidden state a0, and an extra 1, visualized as [⬛️ ; 🟩 ; 1]. ↳ Multiply the two matrices to obtain new hidden state a1 = [0 ; 1]. [4] Second Hidden Layer (b) 🟪: b0 → b1 ↳ First layer a1 🟩 becomes the input. ↳ The transformation matrix is visualized as [🟩 | 🟪 | ⬜️]. ↳ The state matrix is the combination of a1, b0, and 1, visualized as [🟩; 🟪 ; 1]. ↳ Multiply the two matrices to obtain new hidden state b1 = [1; -1]. [5] Third Hidden Layer (c) 🟧: c0 → c1 ↳ Second layer b 🟪 becomes the input. ↳ The transformation matrix is visualized as [🟪 | 🟧 | ⬜️]. ↳ The state matrix is the combination of a1, b0, and 1, visualized as [🟪; 🟧; 1]. ↳ Multiply the two matrices to obtain new hidden state b1 = [1; -1]. [6] Output Layer (Y) 🟦 ↳ The transformation matrix is visualized as [🟧 | ⬜️]. ↳ The state matrix is the combination of c0 and , visualized as [🟧; 1]. ↳ Multiply the two matrices to obtain output Y1 = [3; 0; 3]. — Process X2 (t = 2)— [7] Previous Hidden States ↳ Copy the values of a1, b1, c1. [8] Hidden 🟩🟪🟧 + Output 🟦 ↳ Repeat [3]-[6] to obtain output Y2 = [5; 0; 4] — Process X3 (t = 3)— [9] Previous Hidden States ↳ Copy the values of a2, b2, c2. [10] Hidden 🟩🟪🟧 + Output 🟦 ↳ Repeat [3]-[6] to obtain output Y3 = [13; -1; 9] — Process X4 (t = 4)— [11] Previous Hidden States ↳ Copy the values of a3, b3, c3. [12] Hidden 🟩🟪🟧 + Output 🟦 ↳ Repeat [3]-[6] to obtain output Y4 = [15; 7; 2]](https://image.24vids.com/tw-1809362848054993158/ext_tw_video_thumb/1809362489563631616/pu/img/khsrKXTM6woSuL4P.jpg)
![[Dropout] by hand ✍️ Dropout is a simple yet effective way of reducing overfitting and improving generalization. This by-hand exercise lets students practice calculating dropout, thereby gaining insight into its inner workings. As an additional bonus, students get to practice calculating the gradients of the Mean Square Error (MSE) loss. After the practice, students are often surprised by how simple it is. -- 𝗡𝗲𝘁𝘄𝗼𝗿𝗸 𝗔𝗿𝗰𝗵𝗶𝘁𝗲𝗰𝘁𝘂𝗿𝗲 -- 1. Linear(2,4) 2. ReLU 3. Dropout(0.5) 4. Linear(4,3) 5. ReLU 6. Dropout(0.33) 7. Linear(3,2) -- 𝗪𝗮𝗹𝗸𝘁𝗵𝗿𝗼𝘂𝗴𝗵 -- 🏋️ Training [1] Given ↳ A training set of 2 examples X1, X2 [2] 🟧 Random: p > 0.5 ↳ Draw 4 random numbers ↳ For each random number, if it is above 0.5, we keep and denote it as ◯. Otherwise we drop and denote it as ╳. ↳ The result is [◯, ╳, ◯, ╳] [3] 🟧 Dropout: Matrix ↳ Calculate the scaling factor: 1 / (1-p) = 2 ↳ Set the diagonal based on [◯, ╳, ◯, ╳], where ◯ = 2 and ╳ = 0 ↳ The purpose is to drop the 2nd and the 4th nodes, and scale the remaining two nodes by 2. [4] 🟦 Random: p > 0.33 ↳ Draw 3 random numbers ↳ For each random number, if it is above 0.33, we keep and denote it as ◯. Otherwise we drop and denote it as ╳. ↳ The result is [◯, ◯, ╳] [5] 🟦 Dropout: Matrix ↳ Calculate the scaling factor: 1 / (1-p) = 1.5 ↳ Set the diagonal based on [◯, ◯, ╳], where ◯ = 1.5 and ╳ = 0 ↳ The purpose is to drop the 3rd node, and scale the remaining two nodes by 1.5. [6] Feed Forward ↳ Now we have all the matrices ready across the layers, perform the feed forward pass by calculating a series of matrix multiplications from the top to the bottom ↳ ReLU activation function is applied along the way to set negative feature values to zeroes, denoted by ╳. ↳ The outputs are Y. [7] 🟥 Loss Gradients of Mean Square Error (MSE) ↳ The formula is 2 * (Y - Y') ↳ First we calculate Outputs (Y) - Targets (Y') ↳ Second we multiply each element by 2 [8] Update Weights ↳ Use loss gradients to start back propagation ↳ Update some weights (light red) ↳ The values of the new weights are for demonstration purpose only, not based on real calculation. 🔍 Inference [9] Deactivate Dropout ↳ We set both dropout matrices to identity matrices ↳ The effect is to keep all the features as is. [10] Feed Forward ↳ Take the forward pass to make predictions about unseen data.](https://image.24vids.com/tw-1836044959020900392/ext_tw_video_thumb/1836044944273735680/pu/img/HAksFrOwf0Ct8B5_.jpg)
![[VAE] by Hand ✍️ A Variational Auto Encoder (VAE) learns the structure (mean and variance) of hidden features and generates new data from the learned structure. In contrast, GANs only learn to generate new data to fool a discriminator; they may not necessarily know the underlying structure of the data. The International Conference on Learning Representations (ICLR) this year announced its first ever "Test of Time Award" to recognizes the VAE paper, published 10 years ago. This exercise demonstrates how to calculate a VAE by hand. [1] Given: ↳ Three training examples X1, X2, X3 ↳ Copy training examples to the bottom ↳ The purpose is to train the network to reconstruct the training examples. ↳ Since each target is a training example itself, we use the Greek word "auto" which means "self." This crucial step is what makes an autoencoder "auto." [2] Encoder: Layer 1 + ReLU ↳ Multiply inputs with weights and biases ↳ Apply ReLU, crossing out negative values (-1 -> 0) [3] Encoder: Mean and Variance ↳ Multiply features with two sets of weights and biases ↳ 🟩 The first set predicts the means (𝜇) of latent distributions ↳ 🟪 The second set predicts the standard deviation (𝜎) of latent distributions [4] Reparameterization Trick: Random Offset ↳ Sample epsilon ε from the normal distribution with mean = 0 and variance = 1. ↳ The purpose is to randomly pick a offset away from the mean. ↳ Multiply the standard deviation values with epsilon values. ↳ The purpose is to scale the offset by the standard deviation. [5] Reparameterization Trick: Mean + Offset ↳ Add the sampled offset to predicted mean ↳ The result are new parameters or features 🟨 as inputs to the Decoder. [6] Decoder: Layer 1 + ReLU ↳ Multiply input features with weights and biases ↳ Apply ReLU, crossing out negative values. Here, -4 is crossed out. [7] Decoder: Layer 2 ↳ Multiply features with weights and biases ↳ The output is Decoder's attempt to reconstruct the input data X from reparameterized distributions described by 𝜇 and 𝜎. [8]-[10] KL Divergence Loss [8] Loss Gradient: Mean 𝜇 ↳ We want 𝜇 to approach 0. ↳ A lot of math called SGVB simplifies the calculation of loss gradients to simply 𝜇 [9,10] Loss Gradient: Stdev 𝜎 ↳ We want 𝜎 to approach 1. ↳ A lot of math simplifies the calculation to 𝜎 - (1/ 𝜎) [11] Reconstruction Loss ↳ We want the reconstructed data Y (dark 🟧) to be the same as the input data X. ↳ Some math involving Mean Square Error simplifies the calculation to Y - X.](https://image.24vids.com/tw-1817192583191564496/ext_tw_video_thumb/1817192009591091200/pu/img/XAVt6rAbRS292En_.jpg)
![Batch Normalization by hand ✍️ ~ 7 steps walkthrough below Batch normalization is common practice for improving training and achieving faster convergence. It sounds simple. But it is often misunderstood. 🤔 Does batch normalization involve trainable parameters, tunable hyper-parameters, or both? 🤔 Is batch normalization applied to inputs, features, weights, biases, or outputs? 🤔 How is batch normalization different from layer normalization? So I drew and calculated one entirely by hand. Goal: normalize a mini-batch of 4 examples to mean 0 and variance 1, then let the network scale it back. = 1. Given = A mini-batch of 4 training examples, each with 3 features. = 2. Linear layer = Let us multiply by the weights and add the biases. Batch norm sits after this, which answers the second question: what gets normalized is features, not inputs, weights or biases. = 3. ReLU = We apply the activation, and -2 becomes 0. Negative values are suppressed before any statistic is taken. = 4. Batch statistics = Let us compute the sum, mean, variance and standard deviation, one row at a time. A row is a feature and the four columns are the four examples, so every number here measures one feature against the rest of the batch. That is the "batch" in batch normalization, and it is exactly what layer normalization does not do. The statistics are rounded to whole numbers, which is what keeps the rest of the page doable in pen. = 5. Shift to mean 0 = We subtract the mean, in green. The four values in each feature now average to zero. = 6. Scale to variance 1 = Let us divide by the standard deviation, in orange. Each feature now has variance one, whatever scale it arrived at. = 7. Scale and shift = We multiply by a linear transformation and pass the result on. The diagonal and the last column are trainable, so having just forced every feature to mean 0 and variance 1, we hand the network the means to undo it. The outputs: Mean of each feature = [2, 1, 2] Std dev of each feature = [1, 1, 2] To the next layer = [2, -2, 2, 0], [-3, 3, 6, -3], [2, 0, 1, 2] The answers: 🤔 Both. The scale and shift are trainable, the statistics are not. Epsilon and the momentum on the running statistics are the hyper-parameters, and one mini-batch by hand needs neither. 🤔 Features, after the linear layer, not inputs, weights or biases. 🤔 Batch norm measures across the batch, one feature at a time. Layer norm measures across the features, one example at a time. 💾 Save this post!](https://image.24vids.com/tw-2079570896423911664/ext_tw_video_thumb/2079570876530298880/pu/img/w_TJ6G4bD69KBKuz.jpg)
![[LSTM] by Hand ✍️ LSTMs have been the most effective architecture to process long sequences of data, until our world was taken over by the Transformers. LSTMs belong to the broader family of recurrent neural network (RNNs) that process data sequentially in a recurrent manner. Transformers, on the other hand, abandon recurrence and use self-attention instead to process data concurrently in parallel. Recently, there is renewed interest in recurrence as people realized self-attention doesn’t scale to extremely long sequences, like hundreds of thousands of tokens. Mamba is a good example to bring back recurrence. All of a sudden, it is cool to study LSTMs. How do LSTMs work? [1] Given ↳ 🟨 Input sequence X1, X2, X3 (d = 3) ↳ 🟩 Hidden state h (d = 2) ↳ 🟦 Memory C (d = 2) ↳ Weight matrices Wf, Wc, Wi, Wo Process t = 1 [2] Initialize ↳ Randomly set the previous hidden state h0 to [1, 1] and memory cells C0 to [0.3, -0.5] [3] Linear Transform ↳ Multiply the four weight matrices with the concatenation of current input (X1) and the previous hidden state (h0). ↳ The results are feature values, each is a linear combination of the current input and hidden state. [4] Non-linear Transform ↳ Apply sigmoid σ to obtain gate values (between 0 and 1). • Forget gate (f1): [-4, -6] → [0, 0] • Input gate (i1): [6, 4] → [1, 1] • Output gate (o1): [4, -5] → [1, 0] ↳ Apply tanh to obtain candidate memory values (between -1 and 1) • Candidate memory (C’1): [1, -6] → [0.8, -1] [5] Update Memory ↳ Forget (C0 .* f1): Element-wise multiply the current memory with forget gate values. ↳ Input (C’1 .* o1): Element-wise multiply the “candidate” memory with input gate values. ↳ Update the memory to C1 by adding the two terms above: C0 .* f1 + C’1 .* o1 = C1 [6] Candiate Output ↳ Apply tanh to the new memory C1 to obtain candidate output o’1. [0.8, -1] → [0.7, -0.8] [7] Update Hidden State ↳ Output (o’1 .* o1 → h1): Element-wise multiply the candidate output with the output gate. ↳ The result is updated hidden state h1 ↳ Also, it is the first output. Process t = 2 [8] Initialize ↳ Copy previous hidden state h1 and memory C1 [9] Linear Transform ↳ Repeat [3] [10] Update Memory (C2) ↳ Repeat [4] and [5] [11] Update Hidden State (h2) ↳ Repeat [6] and [7] Process t = 3 [12] Initialize ↳ Copy previous hidden state h2 and memory C2 [13] Linear Transform ↳ Repeat [3] [14] Update Memory (C3) ↳ Repeat [4] and [5] [15] Update Hidden State (h3) ↳ Repeat [6] and [7]](https://image.24vids.com/tw-1806285518126317877/ext_tw_video_thumb/1806285245903482880/pu/img/9-DANs-lC9ghBLvA.jpg)
![[Backpropagation] by Hand✍️ [1] Forward Pass ↳ Given a multi layer perceptron (3 levels), an input vector X, predictions Y^{Pred} = [0.5, 0.5, 0], and ground truth label Y^{Target} = [0, 1, 0]. [2] Backpropagation ↳ Insert cells to hold our calculations. [3] Layer 3 - Softmax (blue) ↳ Calculate ∂L / ∂z3 directly using the simple equation: Y^{Pred} - Y^{Target} = [0.5, -0.5, 0]. ↳ This simple equation is the benefit of using Softmax and Cross Entropy Loss together. [4] Layer 3 - Weights (orange) & Biases (black) ↳ Calculate ∂L / ∂W3 and ∂L / ∂b3 by multiplying ∂L / ∂z3 and [ a2 | 1 ]. [5] Layer 2 - Activations (green) ↳ Calculate ∂L / ∂a2 by multiplying ∂L / ∂z3 and W3. [6] Layer 2 - ReLU (blue) ↳ Calculate ∂L / ∂z2 by multiplying ∂L / ∂a2 with 1 for positive values and 0 otherwise. [7] Layer 2 - Weights (orange) & Biases (black) ↳ Calculate ∂L / ∂W2 and ∂L / ∂b2 by multiplying ∂L / ∂z2 and [ a1 | 1 ]. [8] Layer 1 - Activations (green) ↳ Calculate ∂L / ∂a1 by multiplying ∂L / ∂z2 and W2. [9] Layer 1 - ReLU (blue) ↳ Calculate ∂L / ∂z1 by multiplying ∂L / ∂a1 with 1 for positive values and 0 otherwise. [10] Layer 1 - Weights (orange) & Biases (black) ↳ Calculate ∂L / ∂W1 and ∂L / ∂b1 by multiplying ∂L / ∂z1 and [ x | 1 ]. [11] Gradient Descent ↳ Update weights and biases (typically a learning rate is applied here). 💡 Matrix Multiplication is All You Need: Just like in the forward pass, backpropagation is all about matrix multiplications. You can definitely do everything by hand as I demonstrated in this exercise, albeit slow and imperfect. This is why GPU's ability to multiply matrices efficiently plays such an important role in the deep learning evolution. This is why NVIDIA is now close to $1 trillion in valuation. 💡Exploding Gradients: We can already see the gradients are getting larger as we back-propagate up, even in this simple 3-layer network. This motivates using methods like skip connections to handle exploding (or diminishing) gradients as in the ResNet. I did the calculations entirely by hand. Please let me know if you spot any error or have any questions!](https://image.24vids.com/tw-1818652735535038715/ext_tw_video_thumb/1818652595235569664/pu/img/fBeCqhUByyXiDBbp.jpg)
![[SVM] by Hand ✍️ Support Vector Machines (SVMs) reigned supreme in machine learning before the ascendancy of the deep learning revolution. This exercise compares Linear vs RBF SVMs---how they classify two test vectors, after SVMs are trained from six training vectors. [1] Given xi: Six training vectors (blue rows 🟦) yi: Labels Using xi and yi, we learned ai and b (red borders): ↳ai: coefficient for each training vector i. • Non-zero: A Support Vector that defines the decision boundary • Zero: Too far from the decision boundary, ignored ↳b: bias (how much the decision boundary should be shifted) x’j: Two test vectors (yellow columns 🟨) (To simplify hand calculation, training and test vectors are not normalized.) ~ 𝗟𝗶𝗻𝗲𝗮𝗿 𝗦𝗩𝗠 ~ 🟩 Kernel Matrix (K) [2]-[3] [2] Test Vector 1 ↳ Take dot product between the test vector 🟨 and every training vector 🟦 ↳ The dot product approximates the “cosine similarity” between two vectors ↳ Output: 1st column of K [3] Test Vector 2 ↳ Similar to [2] ↳ Output: 2nd column of K 🟧 Decision Boundary [4]-[6] [4] Unsigned Coefficients → Signed Weights ↳ Multiply each coefficient with the corresponding label ↳ The 2nd training vector is NOT a support vector because its coefficient is 0. [5] Weighted Combination ↳ Multiply weights and bias with K ↳ Output: “signed” distance to the decision boundary ... X'1: (2)*13+0+(1)*12+(-1)*15+(1)*19+(-1)*27+(2) = 17 X'2: (2)*2+0+(1)*3+(-1)*4+(1)*8+(-1)*8+(2) = 5 ... [6] Classify ↳ Take the sign ... X'1: 1 > 0 → Positive + X'2: 5 > 0 → Positive + ... ~ 𝗥𝗕𝗙 𝗦𝗩𝗠 ~ Given ai: Learned coefficients b: Learned bias 🟩 Kernel Matrix (K) [7]-[15] 𝘛𝘦𝘴𝘵 𝘝𝘦𝘤𝘵𝘰𝘳 (𝘟’1) 🟨 L2 Distance 🟪 [7]-[9] [7] Squared Difference ... i=1: (1-2)^2=1, (2-4)^2=4, (1-3)^2=4 ... [8] Sum [9] Square Root [10] Negative Scaling ↳ Multiply by -1: Note that L2 is a distance metric. The negation converts distance to similarity. ↳ Multiply by gamma γ: The purpose is to control how much influence each training example has. A small gamma means each training example pulls the decision boundary more lightly, resulting in smoother decision boundaries. ↳ The result is “negative scaled L2” [11] Exponentiate ↳ Raise e to the power of the “negative scaled L2” ↳ Use the provided table to look up the value of e^ ↳ Output: The 1st column of K 𝘛𝘦𝘴𝘵 𝘝𝘦𝘤𝘵𝘰𝘳 2 (𝘟’2) 🟨 L2 Distance 🟪 [12]-[14] [12] Squared Difference [13] Sum [14] Square Root [15] Negative Scaling [16] Exponentiate ↳Output: The 2nd column of K 🟧 Decision Boundary [17]-[19] [17] Unsigned Coefficients → Signed Weights [18] Weighted Combination ... X'1: (20)*0.7+(-10)*0.8+(10)*0.9+(-10)*0.7+0+(-10)*0.9+(-1) = -2 X'2: (20)*0.9+(-10)*0.7+(10)*0.8+(-10)*0.8+0+(-10)*0.9+(-1) = 1 ... [19] Classify ... X'1: -2 0 → + ... ↳Output: The 2nd column of K 🟧 Decision Boundary [17]-[19] [17] Unsigned Coefficients → Signed Weights [18] Weighted Combination ... X'1: (20)*0.7+(-10)*0.8+(10)*0.9+(-10)*0.7+0+(-10)*0.9+(-1) = -2 X'2: (20)*0.9+(-10)*0.7+(10)*0.8+(-10)*0.8+0+(-10)*0.9+(-1) = 1 ... [19] Classify ... X'1: -2 0 → + ...](https://image.24vids.com/tw-1814290527942242427/ext_tw_video_thumb/1814289813929095168/pu/img/z-ZHM-dmz_lg-Qo0.jpg)
![Vector Database by Hand ✍️ Vector databases are revolutionizing how we search and analyze complex data. They have become the backbone of Retrieval Augmented Generation (#RAG). How do vector databases work? [1] Given ↳ A dataset of three sentences, each has 3 words (or tokens) ↳ In practice, a dataset may contain millions or billions of sentences. The max number of tokens may be tens of thousands (e.g., 32,768 mistral-7b). Process "how are you" [2] 🟨 Word Embeddings ↳ For each word, look up corresponding word embedding vector from a table of 22 vectors, where 22 is the vocabulary size. ↳ In practice, the vocabulary size can be tens of thousands. The word embedding dimensions are in the thousands (e.g., 1024, 4096) [3] 🟩 Encoding ↳ Feed the sequence of word embeddings to an encoder to obtain a sequence of feature vectors, one per word. ↳ Here, the encoder is a simple one layer perceptron (linear layer + ReLU) ↳ In practice, the encoder is a transformer or one of its many variants. [4] 🟩 Mean Pooling ↳ Merge the sequence of feature vectors into a single vector using "mean pooling" which is to average across the columns. ↳ The result is a single vector. We often call it "text embeddings" or "sentence embeddings." ↳ Other pooling techniques are possible, such as CLS. But mean pooling is the most common. [5] 🟦 Indexing ↳ Reduce the dimensions of the text embedding vector by a projection matrix. The reduction rate is 50% (4->2). ↳ In practice, the values in this projection matrix is much more random. ↳ The purpose is similar to that of hashing, which is to obtain a short representation to allow faster comparison and retrieval. ↳ The resulting dimension-reduced index vector is saved in the vector storage. [6] Process "who are you" ↳ Repeat [2]-[5] [7] Process "who am I" ↳ Repeat [2]-[5] Now we have indexed our dataset in the vector database. [8] 🟥 Query: "am I you" ↳ Repeat [2]-[5] ↳ The result is a 2-d query vector. [9] 🟥 Dot Products ↳ Take dot product between the query vector and database vectors. They are all 2-d. ↳ The purpose is to use dot product to estimate similarity. ↳ By transposing the query vector, this step becomes a matrix multiplication. [10] 🟥 Nearest Neighbor ↳ Find the largest dot product by linear scan. ↳ The sentence with the highest dot product is "who am I" ↳ In practice, because scanning billions of vectors is slow, we use an Approximate Nearest Neighbor (ANN) algorithm like the Hierarchical Navigable Small Worlds (HNSW).](https://image.24vids.com/tw-1795076707386360227/ext_tw_video_thumb/1795076436019023872/pu/img/Ne2RjvPwQ1ouSr32.jpg)
