The idea is to train multiple expert neural networks and apply weighted sum of their results. The weights is decided by another neural network based on the same input but connected to a softmax layer to generate weights. The vector from the weighted sum is then feed into another neural network layer to predict a aggression task.
When multiple predictions (targets) are made, they shared the same expert neural networks, but each target has its own neural network for weight generation, and succeeding neural network to process the vector from weighted sum.
When 1 weight is close to 1 and other weights are are close to 0, only 1 expert neural network performs work, skipping all other expert networks. This polarization would be an unexpected setup that wastes resource. To avoid polarization in the weights, Dropout operation is performed on the softmax output during training to give 10% of the chance to drop the result from an expert network. As a result, the solution of putting all logic into 1 expert networks leads to poor performance - this in turn encourages multiple expert networks are trained at the same time.
Often classifiers are trained on unequal amount of positive data and negative data. It is a common practice to reduce the negative data (by a rate a to the positive samples). The reducing the negative samples causes the predicted value larger than the actual occurrence. However, the value can be adjusted by:
Let
P_true = n_positive / (n_positive + n_negative)
P_pred = n_positive / (n_positive + n_negative * a)
And the adjusted expectation can be derived:
P_true = a * P_pred / ((1-P_pred) + a * P_pred )
So the predicted expectation can be adjusted to scale as if trained based on equal amount of samples from both sides.
Deep Retrieval considers features vector of an item as a path. It is an online method to find the matching user.
Make a lookup of a list of items by path and make a lookup of a list of paths by item. Have a prediction model to match a path to a user. During online recommendation, given a user, match a set of paths and follow the path to get to the recommended item.
How an item is expressed as a path: each path is a sequential traverse of an ordered layer. Each layer has k possible node for step, and let the number of layers to be 3 for an example. We call this depth = 3 and width = k. A path is described as 3 nodes.
Given a path [a,b,c], multiple items will be retrieved:
At layer 1, given a user feature vector x, the prediction model for node a is P1(a | x)
At layer 2, given user x and node a, prediction model for node b is P2(b | a ; x)
At layer 3, given user x and node a, b, prediction model for node c is P3(c | a,b ; x)
The input of the prediction model is x, and the output of the prediction model is a k-dimension vector. Take a softmax on this value to direct path walking. The next step could be taking the largest value, or to perform beam search.
The next layer has a different prediction model taking dim(x) + k dimensions. (The input will be x concatenated with the output (k dimension) from the first layer). And likewise have a prediction model and apply softmax function.
Likewise for the succeeding layers.
So, each path consists a series of nodes for a user. P(a,b,c | x). For an item, multiply P with 1 for user x who clicked on the item and multiply 0 for user who didn't click. Take a summation of the P values for all users. This summation is the score for the given path to an item.
Item feature:
Take a summation of the item scores of a few paths, and the negation of this summation is the loss function for the item. We'd like to minimize this negation so that the model give large scores for the item.
Note that there could be a popular path that give large scores for many items. To avoid the popular path from happening, add penalty on paths with many items (How? By subtracting the penalty from the score function of item given a path).
Let reg (path) be the number of items represented by a path. Then to find a path that represents an item with the smallest loss:
Often we have data that have features (keywords) but no classification information. For example, videos in a website can have keywords, but we haven't yet have user information to know if a certain feature can lead to a user to like the video. However, since there are many keywords on the same video, it is logical to believe that the feature vectors based on different keywords on the same video are close to each other - and more distant between the feature vectors based on different keywords on different videos. Separating the feature vectors based on this information is a self-supervised learning process.
Random mask: randomly task keywords at a certain attributes.
Dropout are techniques in collecting features during training from the same item. Dropout is to randomly take away a percentage of keywords (assuming there are many keywords). In this way, the feature on an item is more generalized.
Complementary features: split keywords on 1 item into two sets, and each set map into a feature vector (Thus the two are complementary features) by only seeing 50% of the keywords at a time. Since they are on the same item, the two vectors should large cosine similarity.
Mask related features: calculate the mutual information between two keywords on the items. (Calculated as the sum of all keywords (u,v) MI(U,V) = sum( p(u,v) * log (p(u,v) / (p(u) * p(v) ), where p(u,v) are the probability that the two keywords on the same item. Then, for each keyword k, find half of other keywords that are related to this keyword k. Mask the half of the keywords that are closely related to this keyword k, and use the 50% of less related keywords.
(In practice, the method of masking related features is hard to calculate and hard to maintain.)
How to train: convert all records into vectors: by applying multiple mask techniques and let it multiply matrix to convert it into a vector. Pair vectors to calculate similarity. Take the similarity into a softmax layer. Let expected the cosine similarity of the vectors from the same object be 1 and let the vectors from different object be 0. Take the crossEntropyLoss between the calculated value and expected value.
It is also possible to combine the loss function of self-supervised learning with the loss function of the Contrast Learning, by taking a simple summation.
Contrast learning is a way to setup the loss function. At point-wise loss function, negative samples and positive samples are considered separately. At Contrast Learning, the loss function (aka pair-wise loss) is constructed by taking 3 items: 2 positively related item and 1 unrelated item. The cosine similarity of the 2 positively related items should be large, and the similarity of the unrelated pair item should be small. The difference of the two similarity values is used as the loss function - the further apart of the two values the better. Since the optimization step is to reduce the loss, the training will lead it to fit both samples.
To make the positive sample and the negative sample separate better, usually a desired distance m is defined. If the difference is larger than m, it is considered as no loss. If the difference is less than m, loss will be the difference.
List-wise loss is a similar idea of the pairwise loss function, but considers more samples in the same loss function. Each a training record consists 1 pair of positive samples (a, b) pairing with the input, and multiple negative samples (b_neg_1, b_neg_2, etc) , and take cosine similarity between the pairs: cos(a,b), cos(a, b_neg_1), cos(a, b_neg_2), etc. Put all results in a Softmax function. Let the expected result to be (1, 0, 0, 0, ... ). Train it with CrossEntropyLoss between the result and the expected result.
Note: When trying point-wise loss function (that is training negative and positive samples separately), the ratio of the amount of positive samples and negative samples should be from 1:2 to 1:3,
You probably have heard of Collaborative Filtering, which is to find similarity of two items by counting the number of shared interested users. They are matched via a cosine similarity (or dot product in another word).
There comes a problem: two users are within the same interest group, the shared items may not be that similar.
Swing takes one more step: assign a weight for each pair of shared users - if the two users have shared a lot of items, let the weight of the pair of the user be smaller: 1 / (a + overlap(u1, u2) . (a is a positive term to avoid dividing by zero).
Collaborative Filtering may also happen in similarity of users. Recommendation is made from similar users' list of items. To avoid popular item from appearing in every recommendation, weight of item is reduced by the popularity with 1/ log(1+ num_users_like_the_item)
1. Draw a circle around the image (roughly around the object). This is the initial contour.
2. Calculate the gradient of the image.
3. Blur the gradient values in the images so that the value spread to other part of the image, creating a slope to guide a point to the position with large gradient value.
4. Apply greedy search from the contour to move control point to the points with large gradient values.
5. It is almost done, but the contour is not smooth. A modification to this solution could be to adjust the gradient value with smoothness and elasticity of the contour. The two values are defined as the derivative and second derivative on the contour.
The overall idea is to find large supporting evidence / small standard deviation: if this value is large, it is background. Else, foreground.
The evidence is probably the value for the point in the Gaussian model. Or it can be simply the distance from the mean of the Gaussian model. The lesson didn't mention clearly.
For each pixel there will be a Gaussian Mixture Model. Compute a pixel color histogram for the first N frames of a video. Normalize the histogram, and model it as a mixture of 3 to 5 Gaussians.
During detection, for a value X, | X - gaussian_center | < 2.5 standard_deviation, it is considered part of the Gaussian distribution.
To make the model adapt to new data, update Histogram H using the new pixel intensity. If new histogram differs from the old histogram a lot, refit the GMM.
GMM can be calculated using Expectation Maximization - Start by randomly picking means and standard deviations, cluster data points using these Gaussian distributions; then refine means and standard deviations. Repeat this process until the Gaussian distributions don't change any more (converged). Or, just use Python sklearn.mixture GaussianMixture.
Reinforcement learning is typically used to generate a sequence of actions to achieve a goal. Note that it is different from the classification problem, which answers a question like whether a given feature vector should have a yes/no (or categorical) answer. However, each step of the sequence of actions may be decided similar to a classification problems: given a feature vector for the current environment state, what is the next action to generate in the sequence to achieve a goal state. Main differences:
a sequence of actions (trajectory) vs. a single decision
environment may be a black box.
The goal state is assigned with a reward to guide the action. There are 2 approaches to solve it: find a policy function that given a state S, returns the probability to pick an action a. Or, find a value function that predict the reward in this state - use this value function to greedily pick an next action a that gives the most award (the observed reward at the next state S + the guessed reward moving from S).
Note that with a policy function, the actions are picked randomly by their probability. The policy function could be used to randomly sample a few trajectories to test out the rewards, and take an average to represent how good a state is. In reality there could be many trajectories. We just need a few sample to have a Monte Carlo estimation.
Describe RL in a more human-understandable fashion
It is a maze game, you are asked to find a path from point A to point B.
But you don't know how the maze looks like. However, putting a BBQ chicken at point B, you can follow the smell from point A to reach point B. The BBQ chicken here is the reward, and the smell is the expected future reward (call it return).
But the smell isn't there, either. To implement the smell, we need to assign every step toward the food a greater imagined smell value. This is the discounted return.
But we don't know where the food is, either. So we take random actions until reaching the BBQ, and then assign our steps with imagined smell values.
If we step on poop during the random exploration, assign our steps with negative smell values, so that they are visited less often. And try walking again following the imagined smell.
How to assign an imagined smell value to a step? Use a neural network, or any model.
Applications:
Chatbot - outputs a sequence of words, to provide answer to a question
AlphaGo - chess, use a sequence of moves to value best state
Control - plan a trajectory to control robot / game to reach a certain state.
Q Function
Q function is the quality of an action in an state S. It is usually guessed from a observed trajectory - by the sum of the observed rewards from an intermediate step i to the end state. This sum also have a named called discounted return. (It is called discounted because the sum is a weighted sum - a reward at a further step has less weight in the sum)
Actor Critic
In Actor Critic, two networks are trained. Critic network gives a score of how well an action is under an environment state. (So it takes 2 variables: action and state) Critic network is trained based on reward from the system. Actor network chooses a sequence of actions under each environment state so that the average score from the Critic network is higher. (So it takes 1 variable: state) It is trained based on the scores from the Critic network.
Proximal Policy Optimization
PPO is an improvement based on Actor Critic, where the learning on actor is capped to avoid taking too large of a step. It can be done by 2 ways: limit the loss - it is too large, clip to the max allowed value; Or, use a ratio between the probability of an action in the new policy and the old policy.
Trust Region Policy Optimization
In Trust Region policy optimization, use a function L to approximate a target function which we want to find parameters for. L and the target function are only similar within a small range. In this range, find the parameters for the max value of L, assuming it has the same parameter of the target function. Then start over from finding the the approximate function L again. The process repeats between Approximation and Maximization.
The Monte Carlo method can be used to make the approximation L, by taking sample trajectories.
To make sure the new parameters after maximization are within a small region to the old parameters, KL divergence is used to compare the probability distribution of the policy function. Or it is also possible to measure the distance of the parameters directly.
Sample on datapoints with a higher loss at a higher probability.
Give sample datapoints of a higher loss of a large learning rate, and give datapoints of a smaller loss at a smaller learning rate, as suggested in this RL: Experience Replay video (in Chinese).
Dueling network:
Write the Q* function to be the sum of two neural networks:
Q(s, a) = V(s) + A(s,a) - max A(s,a)
Note that since Q depends on the sum of two neural networks, under the same Q value, the two Neural networks could be unstable by shifting the center from network output 1 and adding the shifted portion to the network output 2. Fortunately, the max A(s,a) term prevents this from happening, as changing shifting value would the max A(s,a) term to change, resulted as varying Q. The max A(s,a) term in practice can be replaced with mean A(s,a) for better performance.
Neural Architecture Search
You have laid out a set of neural network layers for the same purpose, or maybe the esame neural network layer but with different choices of number of parameter - should I use 20 neurons or 30 neurons? or should ResNet works better one part of the layer than just FullyConnected? etc. The goal of the neural architecture search is to find out a better configuration.
Naiveapproach: give every configuration a try. If there are 3 candidates neural network layer, train on every one configuration. This becomes out of hand quickly when there are layers connected in series - the numbers of choices are multiplied.
Differentiable Neural Architecture Search:
Construct a super net by connecting all candidate layers that you want to try in 1 single network in parallel, and sum the results from each layer by a weighted sum using a Softmax layer. The weights are learnable parameters. Then train the super net. All layers will be trained, and their importance will be listed in the learned weight. The one with the largest weight is the winner. Keep that layer and throw away those layers with smaller weights.
It was explained in this video (Chinese). It is also possible to add running time to the weight so that the choice from this process considers both accuracy and performance.
Bipartite graph is one with two sets of nodes. Edges can exist between the sets, but not among a set.
Algorithm to identify if a Graph is Bipartite: given 2 colors, traverse nodes color them color them and color the neighbor nodes with different colors. If a node has a conflicted color with earlier color decision, the graph is not a Bipartite graph.
I am trying to write data in DeltaTable format from an AWS Lambda Function, but AWS Lambda Function limits to 250MB. The deltalake library takes 247MB, which exceeds the limit along with pandas. Since the deltalake library included pyarrow, I need to find a way to write a data frame without including pandas.
I assume you already heard of Kalman Filter. In general, you are controlling a moving vehicle and would like to know where it is at the next moment.
You made your guess of the vehicle's next moment based on your current speed, and at the next moment you also measured the vehicle's next location. Neither of them were accurate. Thus, both of them were in Normal distributions, with some room for errors / noise. The best estimation is to take a product of the two Normal distributions.
Here is how to take the product of two Normal distributions, based on this video (voiced in Chinese):
Taking a product of two Gaussian Distribution X ~ ( µ1, δ1) , Y, ~ ( µ2, δ2), the result Gaussian Distribution is:
k = δ1 / (δ1 + δ2)
µ = µ1 + k * ( µ2 - µ1 )
δ** 2 = δ1** 2 + k * δ2 ** 2
How do I guess my next location? Use middle school math: knowing the current location p and speed v, we could guess the location of the vehicle in the next moment to be:
pk = pk-1 + vk-1 * t
vk = vk-1
(Since there is no external force, the next speed u is constant.)
Let state X = (p, v) be the current position and speed of the vehicle, rewrite the two formulas into a matrix form. That is:
pk = 1* pk-1 + t * vk-1
vk = 0* pk-1 + 1 * vk-1
Then write (pk, vk) as Xk and ((pk-1, vk-1) as Xk-1 and rewrite the expressions above as matrix multiplication
Xk = [1 , t ] * Xk-1
[0, 1]
Call the matrix as F in front of Xk-1 . The formula becomes Xk = F * Xk-1 . We will use the matrix F later.
If there is an external acceleration a, then next p needs to add a * t**2 / 2. and next u needs to add a * t, middle school math again. See this part of the video . The external acceleration is your control. It is how much force to apply to make the vehicle faster.
Xk = [1 , t ] * Xk-1 + [ t**2 / 2 ] * a
[0, 1] + [ t ]
(Note: some articles use a different variable name for acceleration a as u. )
Let P be the covariance matrix of X along p and u axis. P represents the noise / errors in the prediction. It is a 2x2 matrix. This covariance matrix defines the oval shape and rotation of the Gaussian distribution in the (p, v) space.
Given the covariance matrix P at the k-1 moment, we'd like to calculate the covariance matrix at the next moment k. So given the covariance cov(Xk-1) = Pk-1 , we'd like to find out cov(Xk), which is
cov(Xk) = cov(F * Xk-1)
Co-variance function has the following property: cov(A*X ) = A * cov(X) * AT . Use this property, thus:
cov(Xk) = cov(F * Xk-1) = F * cov(Xk-1) * FT
So, given the covariance matrix at the moment k-1, we can calculate the covariance matrix at moment k. (So, the Gaussian distribution of the next moment can be calculated based on Gaussian distribution of the current moment.)
How do I know my measurement?
In your measurement device, create a few samples and compare them with known distances. Calculate the standard deviation in the data collected from the measurement device.
Take the product
Now we have two Normal distributions of the next position: one by the linear equation, and another by measurement device. Use the equation µ = µ1 + k * ( µ2 - µ1 ) to take a product of two Normal distributions, as shown in the first section. Since X is in (p, u) space. So the equation should be in vector form, instead of in scalar form. The value of k and mean value are calculated the same, exception k is now calculated based on covariance. Covariances are combined in this way:
K' = ∑1 / ( ∑1 + ∑2 )
∑' = ∑1 + K' * ∑1
The result looks crazy after plugging in the guessed values based on matrix F, but really they are just the result of the product of two Gaussian distributions.
After Xk is calculated, it will be used as the position to predict in the next round (at k+1 moment). And the calculated ∑' will be used as the covariance matrix for the next round.
In Shushen Wang's video Few-shot learning (3/3), there introduced a simple fine-tuning idea.
1. Softmax classifier
Let x be the raw input, given your feature vector f(x), multiply it with a matrix W plus a bias b. For example, if your classifier generates 3 classes, then the matrix W and b should also have 3 rows. Then take a Softmax.
p = Softmax(W* f(x) + b)
To initialize matrix W, let each row of the matrix W be the average vector of 1 class to be predicted. Let b to be 0. W and b are trainable (fine-tuning).
For example, if there are 3 classes, and class 1 has 5 support vectors (from few shot examples), take an average of the 5 support vectors, call it w1, and let that be row 1 in W.
2. Regularization
Since this trick may lead to overfitting, a regularization term is introduced during loss minimization. Since p is a probability, Entropy regularization can be taken on p and seeking smaller entropy becomes part of the loss function.
For example, a prediction p is made for 3 classes, and p = [0.33, 0.33, 0.34]. This prediction may work, but it is pretty bad. So take an entropy at this number:
entropy = sum( p.map( x => - x * Math.log(x) ) )
That is - 0.33 * Math.log(0.33) + - 0.33 * Math.log(0.33) + - 0.34 * Math.log(0.34) = 1.09 in this example.
Include that as part of your loss function (multiply it with a weight) so that training will discourage this kind of the output.
3. Replace Matrix multiplication with Cosine similarity
Say W has 3 classes and thus 3 rows w1, w2, w3. In W* f(x), each row is multiplying f(x) with a dot product. For example w1 * f(x). Instead of a dot product, take a cosine similarity between w1 and f(x).
Basically a dot product first, and divide the determinant of w1 and f(x). (Basically making f(x) and w1 unit vectors before performing the dot product.)
StatQuest uploaded a good video at explaining how a Decorder-Only transformer works. Most of the content talked about how Key, Query, Value Matrices are calculated. It is quite complex. So here I am going to explain it in a more intuitive way (based on my own understanding).
A sentence is first parsed to tokens, and each token has an embedding and its position i in the sentence. The word embedding + the position encoding make a vector for the word at the position i. Nothing special so far.
Now at each token at position i, using this vector (call it word_vector_i), we'd like to encode another vector to represent the context in the sentence so far. This new vector at i should be based on the vector for this word at i and all the previous words from [0, i -1]. To combine these vectors, we are going to take a weighted sum. This is the overall idea.
But wait, it is not nice to directly use the embedding + positional encoding (word_vector_i) as the value_vector_i. Instead, we will transform it with a matrix (Mv). Mvwill be adjustable and learned. So,
value_vector_i = Mv * word_vector_i
Weight w1 is how similar the 1st word is related to the ith word. Weight w2 is how similar the 2nd word is related to the ith word, etc. To find out how similar the two words are, we are going to apply a dot product on the vector for two words.
But wait, it is not nice to directly use the embedding + positional encoding (word_vector_i), so we again are going to transform word_vector_i with a matrix... Actually, two matrices - one matrix (Mq) for transforming word_vector_i and one matrix (Mk) for transforming word_vector before ith position.
query_vector_i = Mq * word_vector_i
key_vector_1 = Mk * word_vector_1
key_vector_2 = Mk * word_vector_2
...
key_vector_(i-1) = Mk * word_vector_(i-1)
Mq and Mk will be adjustable and learned. The weight can be calculated
wj = query_vector_i * key_vector_j
But wait, these weights are not nice. So, we are going to take all the weights and run a softmax to get a better scaled weights (which sum to 1). Applying these weights and value_vector's, vector_with_context(i) is calculated. vector_with_context(i) is called Masked Self-Attention.
To predict the next word at i+1 position, just apply vector_with_context(i) to a fully connected layer to a result vector representing probability at each word in the dictionary.
But wait, using only masked self-attention (vector_with_context(i) ) isn't nice, we'd like to sum it with embedding and positional encoding (aka word_vector_i as described above). So the prediction of next word is really depending on 3 things. Since we are summing a later vector with an earlier vector, this becomes a residual link in the network.
(Note: since the residual link will sum the masked self-attention and the word embedding, that means their dimensions have to match. This also means Mk, Mq, Mv have to produce the same size. So the size of the Matrix is predetermined.)
Of course, the result vector will apply a softmax to scale probability better.
- What if it predicted the next word wrong, in my prompt?
Run your optimizer to train Mk, Mq, Mv and the fully connected layer to make it right.
- What if I want to generate a reply?
Repeat the process (without training) to run at every position in your prompt. At the end of the prompt, (at the end-of-sentence token), let the transformer predict the next word. Your transformer is now generating a reply! Keep output the next word and add to the end of the sentence until it outputs the end-of-sentence token.
Many pretrained large language models are out there for us to use. However, they may not be accurate for our purpose. Thus, the model needs fine tuning.
Since the model is large, the idea is to: make a copy of the existing model, and select a small percentage of trainable features to retrain. With the new copy of the model, train the new copy with your data.
Note that the library does not work with any random model that you created, as the parameter in LoraConfig task_type=TaskType.SEQ_2_SEQ_LM sets an expectation of the model.
LoRa applies the summation with the existing matrices with Low-Rank Matrices to adjust the weights, which is a trick to create a large matrix by adding small amount of parameters
(I explained it earlier in this post. ) Since only a small percentage of the features are trainable, the training is relatively fast.
This video explains how the LoRA training works internally:
When training a large matrix M with size WxH parameters is expensive, instead take the matrix into the multiplication of 2 smaller matrices. For example: matrix A is in size of (Wx3) and matrix B is in size of (3xH). And let A * B = M to give back a matrix of WxH dimensions. Since W * 3 + 3 * H < W *H, less amount of parameters are required.
This technique is mentioned in both of the following videos:
The Attention is all you needpaper mentioned positional encoding without lacking some details. I am going to write my understanding at those details
The formula is the following:
PE(pos,2i) =sin(pos/100002i/dmodel)
PE(pos,2i+1) =cos(pos/100002i/dmodel)
The paper mentioned that the i is the dimension index of and dmodel is dimension of the embedding. If so, given the last i = dmodel -1, 2i will be out of the bound. So, that is not the correct explanation.
2i and 2i+ 1 here suggest even and odd dimension indices. At the even dimension indices, apply sine function; at the odd dimension indices, apply cosine function. So i is ranged from [0, to dmodel/2) and for each i, it generates 2 dimensions.
Once having the PE (Positional Encoding) value for a position, by the diagram in page 3, it is added to the embedding of the input.
The embedding variable here is the embedding for each word in a sentence, and pos is the position of the sentence. (It is a sentence - not the whole dictionary.)
The Attention is all you needpaper mentioned about an attention function with construction of three matrices Q, K, V without much explanation. Fortunately, this Youtube tutorial on attention explained well (voiced in Chinese). Here is a note that I took from the video.
In self attention, there is only one input, as a list of tokens, each of which is a word expressed as a vector embedding. Call this input X of m elements. Each Xi is the embedding of the ith word. The task to guess the ith word to output, by looking at all words and the i-th word in the input.
Wk, Wq, Wv are the parameter matrices to be learned. Each of them multiplies X to get Q, K, V.
1. It needs to look at all words, which is the Wk matrix multiply X. This matrix is called key matrix as it looks at all keys (words). K = Wk * X
2. It needs to look at the ith word Xi, which is transformed by Q matrix, aka query matrix. qi = Wq * Xi
3. Take the result of K from step 1 and multiply the qi in step 2 and take a softmax. Call this result Ai = Softmax(K.transpose * qi)
4. The context vector at ith location Ai and multiply it with V. Call this result Ci = V * Ai. Since Ai came from step 3 with a softmax , Ci is essentially a weighted sum of V, based on the weight Ai.
5. Take Ci into a Softmax Classifier to get an output word.
Also, Self Attention is a special case of Attention. For self attention, qi is calculated by the ith word in the input Xi. For attention, qi is calculated by looking at the previous output of ith word ( For the very first position, <start> token is considered as the previous output.)
