text:
Why do transformers have a fixed input length?
From what I understand, Transformer Encoders and Decoders use a fixed number of tokens as input, e.g., 512 tokens. In NLP for instance, different text sentences have a different number of tokens, and the way to deal with that is to truncate the longer sentences and pad the shorter ones. As an additional input, a padding mask must be supplied to the Transformer so that its attention is only focused on the relevant tokens.
My question is: Is there something in the architecture that forces the transformer to have a fixed number of tokens as input? (and not adopt dynamically to the actual input length like RNNs for instance?)
For comparison, I think of fully-convolutional networks or RNNs with variable input lengths. They are agnostic to the actual input dimension because they perform pointwise operations on the different patches.
When applying an RNN model to an n-tokens sentence, you compute the same block n times, and when computing it on a k-tokens sentence you will apply it k times. So this architecture does not require padding or truncating (at least not in theory, I do not refer here to implementation considerations).
In transformers: embedding the tokens, computing attention, and feed-forward can be performed on different lengths of sequences since the weights are applied per token, right? So why do we still truncate and pad to a fixed size? Or perhaps it is feasible but not implemented in practice for other reasons?
I must be missing something...
I'll ask it differently to make my question more clear:
Say I have an already-trained transformer model, trained on 512 fixed-sized inputs (truncated and padded). At inference time, if I would like to process a single, shorter sentence. Do I have to pad it or not?
Thanks

It's important to remember that all machine learning and deep learning is at the core matrix algebra and multiplications. So it makes lot of sense to have fixed dimensions of matrices.

You mean that the reason for forcing a fixed sentence length is for computation performance?

In Keras, I trained CNN+Bidirectional LSTM with fixed length 512 during training, and then I save the weight, and then I instantiate untrained model with length 5000, then load the weight, it worked, the performance is about/same.

Edits to reflect edits in question:
If you train your transformer on length = n then yes, you need to pad inputs to length = n. This is not a requirement in the mathematical architecture, it's a requirement in the implementation.

There seem to be two separate ideas in your question:

Why do transformers have a fixed input length?
Why do transformers have input length limitations?

I am not sure which one you are asking, so I will answer both.

1) Saying transformers have a fixed input length is misleading.
Transformers accept variable length inputs just like RNNs. You can think of padding/truncating as an extra embedding step if you want.
We don't need padding in RNNs because they process inputs (sentences) one element (token/word) at a time.
Transformers process inputs all at once. If you are passing in several sentences, you have to do something to regularize sentence length, hence padding and truncating.

2) Transformers often limit input length to 512 or 1024 because of performance issues.
If you are wondering why we don't let our transformers accept inputs as long as possible, the answer is that there are computational and performance limitations. The algorithm complexity is quadratic.
This is where the max_length parameter of a transformer comes in. If your input has length 1,000, the transformer will throw an error because it can only handle inputs up to 512 in length.

I’m not sure I understood what you mean. If it’s the tokenization algorithm that you’re talking about, so that is not what I’m asking. I doubt the limit on the sequence length of the model (ie the number of tokens, regardless of the embedding dimension or the vocabulary size.

@A.Maman I just updated my answer to be more detailed. I hope it helps, but if not, you might want to provide an example in your question so we know exactly what you are asking :)

@A.Maman I just realized maybe the answer to your question is that RNN are recurrent, processing one word at a time along with the previous state. They do "pointwise operation" like you said. Transformers try to solve this extremely expensive method by processing whole sentences at a time, without the need for recursion. That's why you need to choose an input length from the start, because you are feeding the complete sentence at once.

Hi! thanks for the answer! I understand that max_length is not constant in a sense of being numerically identical among all transformers and that it is actually a parameter of the architecture. That's why you're right that it is more accurate to say that it is "fixed" and not "constant". I edited my question to try making it more clear but what I basically ask is: if we disregard training matters, do transformers know to process different lengths of inputs or not? because how I understand the architecture, they do. And if so, whey do I have to pad a short sentence to process it?thanks!

regarding the matrix multiplication explanation: I understand that weight matrices have fixed dimensions. But all those matrices in transformers work pointwise on each token (embedding matrix, query, key, value projections, and feed-forward is performed pointwise as well) , and the token embedding dimension remains the same regardless of the sequence length. So that should not be a problem for processing variable lengths.

is attention can be performed on each token independently correct? self-attention is a contextual matrix relating all tokens in the same input (sentence) with each other. this is dependent on input length. i have a feeling this might be the answer we're looking for (doing lots of reconsidering at this stage, so i'm grateful for your question haha). at the end of the day, what is the transformer training? that's the piece we're going to reuse in prediction which dictates dimensions. well, it's a set of weights relating inputs to outputs, "fixing input length."

additionally, perhaps an RNN can "process an input of any length" because it's processing one word at a time, so it's actually processing many inputs of length 1 sequentially (="fixed length of 1")?

Hi, you're right - this sentence was not accurate, so I've changed it in the question. I meant to claim that applying the weights in all layers (including attention layer) is done per token. In self-attention for instance, you compute the Q, K, V projections (which can be done on any length) and then compute the dot product between all pairs, which can also be done on different lengths. That point is that self-attention can be computed on two different lengths in two adjacent iterations.

ok so your question is can the Q, K, V projections have different dimensions for each different sample in your training data? (particularly, is this possible from a theoretical standpoint and not computationally, because we know that computationally, we need to perform matmul on a constant dimension throughout the problem). is this what you are asking?

(1) Hi, No. The weights matrices' ($W_q$; $W_k$; $W_v$) dimensions are $d_{emb}$ on $d_q$, $d_k$ and $d_v$ respectively. None of those dimensions rely on the sequence length. In the attention mechanism, those projections apply to each token, not one at a time, but the same projection on each token (you can see it as a weight sharing). This does occur in parallel on each token, but can be done on an n-long sequence as it does on a k-long sentence - you take each token and compute the projection (since each projection is simply taking the individual token and multiplying it with a matrix).

(2) Because the projections are computed at the token level, there is no problem computing it on 16 tokens or on 512 tokens (it's simply taking the sentence matrix of dimensions $16\times d_{emb}$ and multiplying it with $W_q$ for instance which is $d_{emb}\times d_q$). The result in the first case will be $16\times{}d_q$ and in the second case $512\times d_q$. But that is not a problem since the attention is computed by softmax($Q\times K^T)\times V$, so the dimensions of the activation matrix will be $16\times 16$, which you multiply by $V$ ($16\times d_v$).

(3) The whole computation will results in a $16\times d_v$ matrix, or $n\times d_v$ in general for variable $n$. So when computing attention on n-long sentence you get n-long contextualized representation sequence which is effectively what happens when you truncate -> pad -> mask. The point is that the loss eventually computes only on the non-masked tokens, so I'm asking why to do this padding (except for the implementation/computation considerations) and not simply compute it with dynamically changing input-output length?

don't forget we're not processing one sentence at a time, but batches of sentences. so the "whole computation" results in a $batchsize \times n \times d_{v}$ matrix. you can't have variable lengths of $n$ in this batch matrix. additionally, once you tell your model to expect a fixed value of $n$ here, you have to provide predictors of the same length, otherwise you'll get tensor shape errors.

I believe wav2vec is a variable length transformer?

This answers the question but doesn't really resolve the confusion. If we limit the context length to 1024 for performance reasons, why do we always talk about context length as though it's a hard parameter of the architecture? For example, you wouldn't talk about batch size as though it's an architectural parameter. The higher the batch size, the more memory you'll need, sure - but you wouldn't say "hey guys, this architecture cannot support a batch of more than 128 sentences. Its max batch size is 128". That would be ridiculous.

To add something to pip.pip answer (thumbs up cause is totally on point), consider that transformers can't be fully convolutional, since as the name suggest, a fully convolutional model perform only convolutions, while transformers include dense layers, which expect a fixed input dimension.
Despite being possible to overcome the limit of fixed dimensionality imposed by the dense layers, for example by using pyramid pooling, that would only add complexity to the training regime and there's no guarantee that the performance will increase.
lastly, from a linguistic perspective, 512 and 1024 tokens are already quite a lot to learn most long dependencies (which let's recall was the main issue why transformers were introduced in place of RNNs). So the game of making transformers input size independent  is not really worth the effort.

Hi @Edoardo Guerriero Thanks! I didn't mean to ask whether transformers can be fully-convolutional or not. I meant to compare fully-convolutional networks' ability to process different sizes of input resolutions to transformers' in-practice training method of processing fixed-size sequence lengths. That is: can the same instance of a transformer process n-sequence input and k-sequence input without padding. And I mainly ask whether this is theoretically possible by the architecture and not from memory/compute resources or implementation perspective. Thanks again!


text:
Multi Armed Bandits with large number of arms
I'm dealing with a (stochastic) Multi Armed Bandit (MAB) with a large number of arms.
Consider a pizza machine that produces a pizza depending on an input $i$ (equivalent to an arm). The (finite) set of arms $K$ is given by $K=X_1\times X_2 \times X_3\times X_4$ where $X_j$ denote the set of possible amounts of ingredient $j$.
e.g.
$X_1=\{$ small, medium, large $\}$ (amount of cheese) or
$X_2=\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ (slices of salami)
Thus, running the pizza machine with input $i$ is equivalent to pulling arm $i\in K$. Due to the different permutations, the number of arms $|K|$ is very large (between 100,000 and 1,000,000). Depending on the pulled arm $i$, the machine generates a pizza (associated with a reward that indicates how delicious the pizza is).
However, the machine's rewards are non-static. Pulling an arm $i$ generates a reward according to an unknown (arm specific) distribution $P_i$, with all rewards drawn from $P_i$ beeing i.i.d.. In addition, it is possible to normalize all rewards to the interval [0,1].
The above problem corresponds to the standard problem of a stochastic MAB, but is characterized by the large number of arms. In the case of the pizza machine, several days of computation time are available to determine the best pizza, so the number of itarations is allowed to be large as well.
In my investigation of MAB algorithms addressing a large number of arms, I came across studies that could call up to a few thousand arms.
Are there algorithms that exist in the MAB domain, which specifically deal with large problem instances (e.g.with $|K|>100,000$)?

I'm not an expert on MAB so I don't know off the top of my head, but this dissertation (http://file:///tmp/mozilla_kevin0/Xu_cornellgrad_0058F_11968.pdf) might be interesting for  you. Section 2 has a literature review of MAB with many arms, and Section 3 has a literature review of MAB with memory constraints. The papers referenced by these sections would be a good place to start. If you end up finding an answer, would appreciate if you answer your own post, as I would be interested in learning more as well!

Without any knowledge on the references you came across, I am assuming that the authors were considering common applications of MAB (planning, online learning, etc.) for which the time horizon is usually small. In such applications, we usually cannot afford a large average regret which is inevitable for standard MAB algorithms due to the $\sqrt{|K|}$ factor.
Depending on the application or additional constraints you can impose on your problem, there are several works that consider structured stochastic MABs in which there are much better guarantees than the pessimistic $\sqrt{K}$ bounds. One variant of structured MABs is learning on graphs [1], where one can obtain regret bounds growing with $\sqrt{\beta(G)}$, where $\beta(G)$ is the independence number of a graph $G$.
[1] F. Liu, Z. Zheng, N. Shroff, "Analysis of Thompson Sampling for Graphical Bandits Without the Graphs", ArXiv. 2018.

I appreciate the reply and the reference to the paper. Sincere thank you for this one. However, in the above problem, the time horizon may also be very large: "In the case of the pizza machine, several days of computation time are available to determine the best pizza, so the number of itarations is allowed to be very large as well."

Isn't the problem resolved then? Either (1) run a standard MAB algorithm for a long time and you will find the best pizza or if the large number of actions is still an issue, (2) model similar toppings (e.g. sausage and Italian sausage) as "neighbors" and run a graphical MAB algorithm as in [1].

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
On learning to rank tasks. Could it be that the input of the Siamese network is a vector, or should it be exclusively raw text?
I'm developing a method to document and query representation as concept vectors (bag-of-concepts). I want to train a machine learning model on ranking (learning to rank a task). So I have document vector V1 and query vector V2. How should I use these two numerical vectors in learning the way to rank a task? What are the possible scenarios?
Do I calculate relevance (similarity) by cosine and then enter the result as a single feature into a neural network? Is it correct to apply Hadamard to produce a single vector representing the features of a document and query pair, and then train a neural network with it? Can two vectors (document and query vector) be entered into the Siamese network in order to evaluate the relevance? One told me this is not possible because the network only take raw text as input and extracts features. Hence, it is useless to enter a vector that was generated by my vectorization method.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Hairstyle Virtual Try On
I want to help people with cancer who are under chemotherapy, and generally people who have lost their hair to Virtually Try-On Toupees/Wigs on their head.
VTO must support both the frontal and side positions of the head.
At first, I thought I could use traditional deep-learning to find landmarks, then place the hairstyle on the head.
But the results were unrealistic and inaccurate.
2D Placing of Hair:
Some Hairstyles and Portraits fit well together:

But some don't:

They need manual modification:

Sometimes the original hair needs to be erased:

GANs promise more natural results with less manual engineering
changing hairstyle using GAN:

changing hairstyle using GAN:

So, I decided to use GANs for this Task.
Is it a good choice or is there an alternate solution?

You really need to provide more details. What are you using the GAN for? Moreover, try to ask a question that will not lead to opinions. Edit your post to clarify that.

@nbro I edited mu question, I don't know if its enough or not?

Where does this conclusion "GANs promise more natural results with less manual engineering" come from?

@nbro because a well architected and  well trained GAN tends to generate realistic fakes, but the traditional approach of placing a transparent hairstyle on the head, needs a lot of refining to the both hairstyle and the portrait itself

Have you tried to search for research work that attempts to do similar things? Maybe someone has already tried to do that. Feel free to edit your post to include more info.


text:
Appropriate convolutional neural network architecture when the input consists of two distinct signals
I have a dataset consisting of a set of samples. Each sample consists of two distinct desctized signals S1(t), S2(t). Both signals are synchronous; however, they show different aspects of a phenomena.
I want to train a Convolutional Neural Network, but I don't know which architecture is appropriate for this kind of data.
I can consider two channels for input, each corresponding to one of the signals. But, I don't think convolving two signals can produce appropriate features.
I believe the best way is to process each signal separately in the first layers, then join them in the classification layers in the final step. How can I achieve this? What architecture should I use?

I don't know what you mean by desctized signals but if I understand your question correctly, separating two signal and passing them through same architecture of CNN (even with different parameters) is not a good idea. Because when they are together (as different channels) they will be treated differently by the CNN (each channel has its own parameters) and even this way the network is able to combine these two signals and get better results by information extracted from this combination.

I meant it is not analog, and the analog signal is sampled using some algorithm (which is always the case in computers), thanks for the answer.

You can safely give both signals as input in different channels. Actually, it's the best way. This way, the network is able to find low-degree patterns that involve both signals early in training. This will therefore enable the early discovery of more complex patterns, too.
Differently from what one might understand from your question, the two signals will not be convolved against eachother, as it's typically done in signal processing. The convolution taking place is that of the first layer kernels with a two-component signal (the one you give as input). It can happen that there's a first order pattern that can only be recognised by looking at both signals at the same time. If that's not the case, the kernels will ignore one signal or the other (having the corresponding weights a value of zero).

"Differently from what one ..." your right, this part may be written poorly. I meant each application of a kernel is performed on both channels at the same time, which mixes them together in the output...

It's ok. It would be good if you edit your question to fix that. However, the important bit is that performing the convolution on both channels at the same time is what allows recognizing patterns like "both signals high" or "A is high and B is low", which is very convenient.


text:
Is it possible that the fittest individuals in an Artificial Life population may be successful by not actively pursuing the rules of the environment?
I'm trying to understand Artificial Life (e.g. here for a simple background) in Computational Evolution.
I understand that in this set of methods, you set up a dynamic environment (e.g. the ecology of the environment) and then you set a series of rules; e.g.:

You need energy to reproduce.
You intake energy from food sources.
For nourishment, you can
eat plants, animals, or steal food.
You must stay alive until you reproduce.
Every action consumes energy.
When you have no energy left, you die.

I think I need a set of rules that govern the survival of an artificial life. You run the environment and see what persists (there's a set of rules instead of a fitness score), and the individuals that survive are said to be successful.
I can imagine a scenario where a successful organism in this environment consumes a lot of food, reproduces, but possibly runs out of energy and dies. I'm wondering if there's ever a situation where an organism does very little (or nothing), and still be successful? I'm not sure if this question makes sense, please let me know if clarification is needed. Given the specified environment, I want to know if the most active organism will always be the most successful. The most active organism would be the one that obtains the most food/energy/reproduces the most. Or is it possible to not be the most active organism and still be successful?

beautiful thing about a complex system which you are simulating is its unpredictable ...  given sufficient opportunity ( time and variability ) you will see a wide range of surprises ...  essence of evolution is (1) genetic inheritance (2) diversity of offspring (3) individual organism exposure to the vagaries of the environment which determines survival or death ... its very good to have real time plots showing several different dynamics as well as instrumentation to record when predicted events happen ... have fun

It is entirely possible!
You see, the agents will perform whatever actions are available to them, and if the evolutionary algorithm is setup correctly, whatever set of actions provides them with a bigger survival rate will be the one that gets explored and reproduced the most.
Here is a very interesting list of "Specification Gaming" in AI, where the agents happened to "game" the rules to reach their goals (metric optimization) without actually doing what the creators intended: https://docs.google.com/spreadsheets/u/1/d/e/2PACX-1vRPiprOaC3HsCf5Tuum8bRfzYUiKLRqJmbOoC-32JorNdfyTiRRsR7Ea5eWtvsWzuxo8bjOxCG84dAg/pubhtml (second link)


text:
Extending FaceNet’s triplet loss to object recognition
FaceNet uses a novel loss metric (triplet loss) to train a model to output embeddings (128-D from the paper), such that any two faces of the same identity will have a small Euclidean distance, and such that any two faces of different identities will have a Euclidean distance larger than a specified margin. However, it needs another mechanism (HOG or MTCNN) to detect and extract faces from images in the first place.
Can this idea be extended to object recognition? That is, can an object detection framework (e.g. MaskR-CNN) be used to extract bounding boxes of an object, cropping the object feeding this to a network that was trained on triplet loss, and then compares the embeddings of objects to see if they’re the same object?
Is there any research that has been done or any published public datasets for this?

Check this page out, it describes how to develop apply triplet loss to a network: https://towardsdatascience.com/image-similarity-using-triplet-loss-3744c0f67973


text:
Will parameter sweeping on one split of data followed by cross validation discover the right hyperparameters?
Let's call our dataset splits train/test/evaluate. We're in a situation where we require months of data. So we prefer to use the evaluation dataset as infrequently as possible to avoid polluting our results. Instead, we do 10 fold cross validation (CV) to estimate how well the model might generalize.
We're training deep learning models that take between 24-48 hours each, and the process of parameter sweeping is obviously very slow when performing 10-fold cross validation.
Does anyone have any experience or citations for how well parameter sweeping on one split of the data followed by cross validation (used to estimate how well it generalizes) works?
I suspect it's highly dependent on the distribution of data and local minima & maxima of the hyper parameters, but I wanted to ask.

One problem: you might slightly overfit when testing on the set that the parameter sweep was tested on. A more rigorous approach is to test the parameter sweep on a validation set, which is held out during cross validation. But you would still end up testing on the set that you trained the parameter sweep on, which has the potential to overfit.

Depending on the number of features you have you might want to try reducing features in order to reduce overfitting and speed up your model. I assume you are using proper regularization as well. PCA may be an option to help if time is the main issue, medium PCA. As the medium article states PCA can be used to reduce the dimensionality of the data while keeping retaining variance. If you run a random forest on the different sets and the feature importance ranking is at all different that is a big issue and the number of features should be reduced. Ideally, the features should be cropped till they have the same (structure/feature importance) but slightly different weights associated with those features. Here is a article demonstrating feature selection.
Here are some publications I believe are relevant to your problem. More in line with your desire to try to validate after one sweep. You may want to look up applications of LSTM or Yolo to your model I have a feeling these technologies will help direct your final decisions on what to do.
Subspace regularization method for the single-trial estimation of evoked potentials (1999) by P.A. Karjalainen, J.P. Kaipio, A.S. Koistinen, M. Vauhkonen
On Quadratic Penalties in Elastic Weight Consolidation (2017) by Ferenc Huszár
Parameter space exploration with Gaussian process trees (2014) by  Robert B. Gramacy   University of California, Santa Cruz, CA
Herbert K. H. Lee   University of California, Santa Cruz, CA
William G. Macready
Optimal Hyperparameters for Deep LSTM-Networks for Sequence Labeling Tasks (2017) by Nils Reimers, Iryna Gurevych
Evaluating Hospital Case Cost Prediction Models Using Azure Machine Learning Studio (2018) by Alexei Botchkarev -evaluation of regression performance


text:
What is the impact of using multiple BMUs for self-organizing maps?
Here's a sort of a conceptual question. I was implementing a SOM algorithm to better understand its variations and parameters. I got curious about one bit: the BMU (best matching unit == the neuron that is more similar to the vector being presented) is chosen as the neuron that has the smallest distance in feature space to the vector. Then I updated it and its neighbours.
This makes sense, but what if I used more than one BMU for updating the network? For example, suppose that the distance to one neuron is 0.03, but there is another neuron with distance 0.04. These are the two smallest distances. I would use the one with 0.03 as the BMU.
The question is, what would be the expected impacts on the algorithm if I used more than one BMU? For example, I could be selecting for update all neurons for which the distance is up to 5% more than the minimum distance.
I am not asking for code. I can implement it to see what happens. I am just curious to see if anyone have any insight on the pros and cons (except additional complexity) of this approach.

The following is my intuition about the behavior of the algorithm considering your question, based on my knowledge and experience with single BMU SOMs. I didn't verify it experimentally.
At early stages of training:
It should disturb the SOM topology preserving properties, as you're assigning the same pattern to different (and probably distant) locations in the lattice, making the distribution multimodal. This is not terrible on its own, as different positions could encode different relationships to neighbors, overcoming the limitations of a single 2D/3D neighborhood. But if your SOM is not large enough, the multiple modes may collapse, resulting in unimodal distributions covering large portions of the map, wasting space. It all depends on your training schedule.
At later stages of training:
If you started with a single BMU at early stages, it wouldn't provide any meaningful impact, as a SOM, by definition, clusters similar patterns at close positions of its lattice. In other words, the neurons closest to your input are already inside the BMU update radius. If you trained with multiple BMUs since the beginning, you would keep finding / activating the multiple maxima of your multimodal distributions for each pattern. The dimensionality reduction would become even more nonlinear than it already is with single BMUs. This may or may not be a problem, depending on your application.


text:
What is the equation to update the weights in the perceptron algorithm?
I'm trying to understand the solution to question 4 of this midterm paper.
The question and solution is as follows:

I thought that the process for updating weights was:
error = target - guess
new_weight = current_weight + (error)(input)

I do not understand for example, for number 2 below, how that sum is determined. For example, I want to understand whether to update the weight or not. The calculation is:
x1(w1) + x2(w2)
(10)(1) + (10)(1) = 20
20 > 0, therefore update.

But the equation to obtain the same answer in the solution is:
1(10 + 10) 20
20 > 0, therefore update.

I understand that these two equations are essentially the same, but written differently. But for example, in step 5, what do the elements in g5 mean. What do the -8, -16 and -2 represent?
p.s. I know in a previous (now deleted) post of mine, I asked a question related to the use of LaTeX instead for maths equations. If someone can show me a simple way to convert these equations online, I'm more than happy to use it. However, I'm unfamiliar with this software, so I need some sort of converter.

I will tell you my knowledge, correct me if I am wrong.
Perceptron Learning Algorithm (PLA) is a simple method to solve the binary classification problem.
Define a function:
$$
f_w(x) = w^Tx + b
$$
where $x \in \mathbb{R}^n$ is an input vector that contains data points and $w$ is a vector with the same dimension as $x$ which present for the parameters of our model.
Call $y=label(x)=\{1,-1\}$ where $1$ and $-1$ are the label of each $x$ vector.
The PLA will predict a class like this:
$$
y=label(x)=sgn(f_w(x))=sgn(w^Tx+b)
$$
(The definition of sgn function can be found in this wiki)
We can understand that PLA tries to define a line (in 2D, or a plane in 3D, and hyperplane in more than 3 dimensions coordinate, I will assume it in 2D from now on) which separate our data into two areas. So how can we find that line? Just like every other machine learning problems, define a cost function, then optimize the parameters to have the smallest cost value.
Now, let define the cost function first, you can see that if a data point lies in the correct area, $y$ and $f(x)$ have the same sign, which means $y(w^Tx+b) > 0$ and otherwise. Similar to your example, I will define:
$$
g(x)=y(w^Tx+b)
$$
We ignore all the points in the safe zone ($g(x)>0$), only update to rotate or move the line to adapt with the misclassified points ($g(x)\le 0$), here, you can understand why we only update if $g(x)\le0$.
We need to define a cost function to minimize it, so our cost function will become:
$$
L(w)=\displaystyle\sum_{x_i\in U}(-y_i(w^Tx_i+b))
$$
where

$U$is the set of the misclassified points
$y_i$ is the label of data point $i$-th
$x_i$ is the $i$-th data vector
$w$ and $b$ is parameters of our model

For each data point, we have the derivative is
$$
\frac{\partial L}{\partial w} = -y_ix_i \\
\frac{\partial L}{\partial b} = -y_i
$$
Finally, update them by Stochastic gradient descent (SGD), we get:
$$
w = w - \frac{\partial L}{\partial w} = w + y_ix_i \\
b = b - \frac{\partial L}{\partial b} = b + y_i
$$
For your last question, notice that the weight and bias changed from $4$-th updated, so we have:
$$
y_5 = 1, x_5 = (4,8), w = (-2,-2), b = -2 \\
\Rightarrow g_5 = +1 \times (4\times(-2) + 8\times(-2)+ (-2)) = -8 -16 -2
$$


text:
Is it possible to integrate the GPT-3 by OpenAPI inside Unity3D or any game-engine?
My company has full access to beta testing for GPT-3. We wanted to try it for some games or game mechanics within Unity3D. Is it possible to use it for dialogues or with unity scripts?
The Documents of OpenAI does not say anything about this possibility, so I'm not sure.

Yes, OpenAI will release an API for GPT-3, so any developer can integrate it into their application. I don't believe the document for their API is public yet, so we don't know what the final interface will look like, but it's likely to be a simple REST API. In the future, I imagine your developers can take advantage of their API, or alternatively there will be community-made scripts for you to use/copy.
The pricing for using their API is explained here. Note that they charge per token, which might be important in case your game plans to make live calls to GPT-3 during gameplay (as opposed to mining a huge corpus of answers to build an offline database).
The use cases of GPT-3 suggests that you can legally use them for commercial products, although I couldn't find a definitive license or user agreement document.

I found these links so hopefully they help.
https://openai.com/blog/openai-api/
https://nordicapis.com/on-gpt-3-openai-and-apis/


text:
How to do early classification of time series event with small dataset?
I would like to build a real-time binary classifier that can predict an event of interest that is occurring as soon as it starts. These are electromyographic signals, and the event classification should be able to classify the event as early as possible. This is because the next stage of the algorithm has to make a decision before the end of the event.
I don't know what kind of algorithm/approach I should use here. I suppose RNN with LSTM cells should do the job, but the dataset is quite small as physiological signals are not easy to gather.
I have seen many algorithms that windowed the signals (from the training set) and labeled each window as an event of interest if at least part of the event is contained in the window. Each window is then fed to a machine learning algorithm. Then, the prediction uses a sliding window in real-time. But this approach doesn't take into account the temporal aspect of the event as there is no link between each window seen by the ML algorithm.
Do you have any tips or resources I could use to solve the problem?

One kind of system you could look into are Echo State Networks (ESNs).
They are relatively cheap to train and can learn to predict output signals to an  arbitrary degree of precision.
All you need to train the system is some labeled training data.
Thus, if you have a sequence of measurements/feature values and the corresponding sequence of class labels, you can train and fine-tune these kinds of systems to output some required class label very quickly after the onset of an event encoded in the measured feature values.

Thanks ! this seems to fit my needs. I'll still look for several solutions to compare them but i'll definitly dive into it. What do you mean by "arbitrary degree of precision" ? due to randomly assigned weights in the reservoir ?

Input and Reservoir (i.e. recurren) weights are both assigned and KEPT random(ly), indeed. Only the output weights are trained. However, a number of possible "tricks" (motivated by some theory) exist which you can use to increase the precision in how well the signal generated by the ESN fits the target output signal. This kind of variability in the quality of the outcome is what I essentially meant by "arbitrary degree of precision". See, for example, this practical guide.

thanks for the link ! One final question. are ESN able to deal with noise (like white gaussian noise for instance) ? my data are Electromyographic signals which usually have low signal to noise ratio as events are often with low amplitude (but never with SNR below 1).

Actually, I am not an expert in using ESNs myself yet. In preparation for some project, I played a bit with them and I have been told about their great capabilities. So, my guess is that it's definitely gonna be worth giving them a try and then observing whether things work as expected or not. The nice thing is that a basic model is really quickly implemented any training times are low due to the fact that often models obtained via linear regression suffice for modelling output weights. But I think how sensitive these models are depends a lot on the final configuration of the model.


text:
How to know if a real-time classifier is achivable in a low-power emdedded system?
Say I have an Machine/Deep learning algorithm I developed on a desktop pc to achieve a real-time classification of time series events from a sensor. Once the algorithm is trained and performs good, I want to implement it on an low power embbeded system, with the same sensor, to classify events in real-time:

How can I know if the low power embedded system is fast enough to allow real-time classification regarding the algorithm (knowing it in advance would avoid to implement and try multiple architectures) ?
Machine/Deep learning algorithm are usually developed in python. Is there easy ways to transfer the code from python to a more embeddable langage ?

Regarding your first point, it depends on what neural network you would like to use, the sensor temporal resolution, and the capabilities of the embedded system. You can figure out the number of operations required for a forward pass of your network, then when combined with the internal clock of the embedded system, you can calculate the approximate time it would take for one classification event in real time.
A good explanation is given here
What is the computational complexity of the forward pass of a convolutional neural network?
If you have the computational complexity of your network, and the number of CPU cycles per seconds, you can roughly approximate the time.


text:
How to embed/deploy an arbitrary machine learning model on microcontrollers?
Say I have a machine learning model trained on a laptop and I then want to embed/deploy the model on a microcontroller. How can I do this?
I know that TensorflowLite Micro generates a C header to be added in the project and then be embedded, but every example I read shows how it is done with neural networks, which seems legit as TensorFlow is primarily used for deep learning.
But how can I do the same with any type of model, like the ones there is in scikit-learn? So, I'm not interested in necessarily doing this with TensorflowLite Micro, but I'm interested in the general approach to solve this problem.

Please, rather than editing your post to add an answer to your own question, add a formal answer below and provide the relevant details from that blog post in it.

There are a few possible approaches to deploying a ML model to a microcontroller.
The main limiting factor to deployment on microcontollers is that ML models are usually a representation of a set of parameters that are intended to be used as input to a prediction algorithm alongside a new datapoint. Most such models assume the presence of an accompanying library that implements the algorithm in question. However, a microcrontoller may use an exotic chip architecture, or have very several or unusual resource constraints that prevent these standard libraries from being deployed easily.
Presumably you will already have some way to get input into your microcontroller and to program it in order to call some function that you can write. If not, you will need to first figure out how to do that, and the right methods depend on your microcontroller. A common approach is to write assembly code or code in a very limited subset of C or another language. An alternative is to find a distribution of an interpreter for another language (e.g. Java, Python) that has been compiled to work on your chip. Either way, you will need some way to program the chip.
Presuming you can program the chip, you have two fundamental challenges in deploying the model:

Most models are trained with very wide floating point numbers for their parameters. For example, 128-bit numbers may be used. On a standard computing environment, the CPU or GPU will be equipped to perform operations on wide datatypes efficiently. On a microcontroller, you may be limited to 8-bit or 16-bit integers. To work with your model parameters in an environment like this, you will need to either make the parameters smaller (usually by rounding them to fit in a much smaller numeric format, a process called "quantization"), or by finding or writing software that can simulate the operations you want (probably addition and multiplication) on a large datatype that is represented as a collection of smaller datatypes. The first approach may make the model perform poorly. The second may make model prediction very slow.

You need an implementation of the algorithm. Some algorithms like linear regression, linear discriminant analysis, or even decision trees are extremely easy to implement prediction for, and may require only addition, multiplication, and/or comparison. You might be able to write these yourself in a simple subset of C, or even in assembly (for example, prediction with linear regression should be just a simple loop). Other algorithms, like deep neural networks, may contain more complex operations, and may contain many such operations performed in complicated sequences. For these, you generally will need to find an distribution of a library that implements the algorithms, or compile one yourself. Compiling one yourself will require setting up a build toolchain for your specific microcontroller, and can be quite involved.

I found:

For scikit-learn like models: MicroML, Micro-LM, Micro Learn, sklearn-porter, emlearn
For deep learning models: tensorflow Lite Micro, X-CUBE-AI, Glow, NNoM
Both: EdgeML, ELL

These seems to partly fit my needs. But i am surprised that i cannot find something more general that either convert Python to C or to object file with ML support (to be used in C projects). Indeed, once trained, ML algo are "just" a bunch of additions/multiplications/comparisons.
It would help to be able to convert scikit-learn pipeline for instance, as ML projects are rarely composed of only a single ML model taking raw data. But it seems that EdgeAI/TinyML is mainly focused on compiling deep learning models when it comes to deploy ML models on "bare-metal" microcontrollers.
Thanks for your answers btw, it helps.

Is there any particular preprocessing / feature extraction things you have in mind, apart from the model itself?

say the signal comes online. The pipeline could be: the signal is acqquired for n samples (windowed) and some features are extracted from it (mean, var, and other dedicated ones). An ACP can then be used to reduce the dimentionality, and then the reduced vector is fed to a classifier. This is a classic approach actually, but i did not find a simple way to covert the whole pipeline (at the time. But i did not search recently). But i will need to go back to it in the coming weeks.

Yes the overlapped windows and feature calculation is something one almost always have to do with time-series. However this is not entirely standardized even in Python, tends to be custom per project. But I am interested in implementing this in emlearn, with C implementations tailored for microcontroller use (streaming, low-memory, no dynamic allocations).

What is ACP? Did you mean PCA dimensionality reduction?

oops indeed, PCA ! ACP is the french name. I will further explore what is possible to do in the coming weeks, and come back here if anything relevant to add.

If the library running the model can be compiled for your microcontroller,
then you can run your model on that microcontroller.
If you train using one library and deploy using another library, you possible can convert your model to that library: ONNX.
Some library links on Edge Computing in ML:

Microcontroller support for Tensorflow Lite
Edge ML
PyTorch supports android
scikit-learn uses only python libraries. ulab partly replaces numpy for  micropython.

To speed things up specific hardware is used: GPU's of course, but also Tensor Processing Units.
One can manually transfer an NN trained model to C code
(paper),
but there are also compilers:

XLA of tensorflow
Glow of pytorch
NNCG

XLA and Glow support x86-64 and ARM64.
The NNCG approach generates C code and thus should be more readily portable to general MCU's (paper).
Further links: adge-ai,
stackoverlow question

Isn't ONNX only for neural networks? The OP is interested in deploying any ML model (so not just NNs). By the way, welcome to AI SE :)

ONNX is for NN exchange. ML can be seen as a very broad field. Any C code can do ML. As such a one for all exchange/deploy format would mean quite a bit of coordination and standardization. As the previous answer said, ML models normally are split into two parts: data relative to a library. Every model has its own library. One needs to have that availability on the target platform.

One can use simpler approach with deepC compiler and convert exported onnx model to c++.
Check out simple example at deepC compiler sample test
Compile onnx model for your target machine
Checkout mnist.ir
Step 1:
Generate intermediate code
% onnx2cpp mnist.onnx

Step 2:
Optimize and compile
% g++ -O3 mnist.cpp -I ../../../include/ -isystem ../../../packages/eigen-eigen-323c052e1731/ -o mnist.exe

Step 3:
Test run
% ./mnist.exe
Here is a link to YouTube Video for elaborate instructions.
Fur details, read more at  https://link.medium.com/IhbcJzi4jgb


text:
How will the filter size affect the transpose convolution operation?
After a series of convolutions, I am up-sampling a compressed representation, I was curious what is the methodology I should follow to choose an optimum kernel size for up-sampling.

How will the filter (or kernel) size affect the transpose convolution operation (e.g. when using ConvTranspose2d)? Will a larger kernel help upsample with better detail or a small-sized kernel? And how would padding fit in this scenario?

At what rate should the depth(Channels i.e number of filters) decrease while upsampling i.e from (Dx24x24) to (D/2 or D/4, 48, 48)
Eg: If i/p to TransposeConvolution is (cxhxw)64x8x8 how o/p quality be different for o/p of shape 32x16x16 and 16x16x16?

Would you specify the purpose of up sampling and what final expected output of your convolution, thanks.

@CloudCho I was looking for more of a general approach, so that while applying transpose convolution I could chose these hyperparameters more decisively.

thanks for details. How about Depth Decrease? Would you add more details in the question?

@CloudCho I have edited the question.

Take a look at an article on a similar topic.


text:
Why is it easier to construct adversarial examples relative to training neural networks?
I was having looking at this lecture by Ian Goodfellow and my doubt is around 18:00 timestamp where he explains generation of adversarial examples using FGSM.
He mentions that the there is a linear relationship between the input to the model and the output as the activation functions are piece-wise linear with a small number of pieces. I'm not very clear what he means by input and output. Is he referring to inputs and outputs of a single layer or the input image and final output?
He states that the relation between the parameters (weights) of a model and the output are non-linear which is what makes it difficult to train a neural network, thus it is much easier to find an adversarial example.
Could someone explain what is linear in what? and how linearity helps in adversarial example construction?
EDIT: As per my understanding FGSM method relies on the linearity of the loss function with respect to the input image. It constructs an adversarial example by perturbing the input in the direction of the gradient of the loss function w.r.t image. I am not able to understand why this works?

input to output is linear refers to the input X i.e image and output is the output logits/softmax from the network.
So how does linearity help in constructing adversarial examples? Imagine a simple logistic regressor and a simple 2D space. There is a definite boundary beyond which the label that the model(i.e logisitc regressor in this case) changes. So if we move perpendicular to the boundary (i.e the line represented by the model in this case) we can get to another class's space. So if we perturb the input in this direction, the model outputs wrong class. { Refer the slide with the title Adversarial Examples from Excessive Linearity for diagram }
Now imagine the neural network trained on imagenet, there are so many boundaries and a small change can just shift change the class the model would predict. Now it is important to note that these subspaces of the image remain nearly the same if we train VGG or ResNet etc. So this explains how an adversarial example on one network effects another.
You may ask how such small change can effect. this is because the vectors we deal it is not 2d or 3d, it is very large and small changes add up.

Computing the derivative of the loss function w.r.t the image would involve similar steps as of back-prop just that we would have the propagate the gradients from the 1st hidden layer to the input. In that case doesn't the gradient w.r.t image involve similar amount of non-linearity as the weights itself?

Let's take a simple nn, 1st we multiply W.x, now multiplication is linear. Next say we apply ReLUs, they are linear too in the majority of the domain. Even sigmoid can be nearly considered linear in the non-saturating region. So we say dnn are very piecewise linear. i.e overall we can assume they're linear.  Yes some amount of nonlinearity is present but experiments have been done to show they act linearly. Note that I am only talking about the linearity of the network, not that of loss function.

I get what you're saying, but the FGSM takes a step in the direction of the gradient of the loss w.r.t input image. And as you said if the inter-class decision boundary is linear then on moving farther in this direction would yield an adversarial example. Doesn't FGSM rely on linearity of gradients w.r.t image and not gradients of outputs w.r.t input [which is linear somewhat by your above explaination].

The input image is like a reference, we don't take any gradient with respect to it, rather with the perturbation that is added to the input image. By the way, your question in title and OP are different. It would help if you can be a bit clear.

Have edited the question.


text:
What progress has been made in computerized bridge play?
Computer programs have been produced for games such as Chess, Go, Poker, StarCraft 2, Dota. The best ones, Deep Blue and AlphaGo , AlphaZero, Pluribus,... are now considered better than the best human players. More to the point, the computers' game results have been influencing human play.
Apparently, computers are not yet better than human players in Bridge. There can be computer simulations of various hands and hypothetical opposing hands. But what progress have computers made in playing human players in tournaments? Have any new theories of bidding or play evolved as a result of computer-human interaction in Bridge?

This is question was asked at Board & Card Games Q&A however I think here it might get better answer


text:
What are the best practices of adding noise to game-playing bots?
I write bots that play card games. From time to time, I add noise to their decisions, mainly for two reasons:

Reduce predictability: In games with hidden information the optimal play is a mix between several actions.
Reduce strength: allows to create several bots on a spectrum of strength.

My first question is: What are the best practices of adding noise to decisions?
I implement noise in two ways: assume each action receives a score $S$.

Each action also receives $\text{noise} \sim \text{Uniform}(0, \text{constant})$.  The action with the highest $S+\text{noise}$ is chosen.
Each action is chosen with probability proportional to its $S$. I.e., $\text{Pr}(i)=\dfrac{S_i+W}{\Sigma_j (S_j)} $, where $W$ is a winner bias, that increases the probability of the best $X$ actions.

What are the pros and cons in the two implementations that I use?


text:
Which RL algorithm should I use to learn an optimal weight vector?
What is the best practice in order to learn the optimal weight vector $W^*$?  By optimal I mean the weights that will produce the agent with the highest win-rate.
I have an agent that plays a imperfect information game and I want to find the optimal weights via Reinforcement learning.  Each turn, for each move $a$, the agent calculates a heuristic value, $h(a)$ that is a linear function of $n$ features.  That is to say, the heuristic value for move $a$ is
$$h(a) = w_1f_1(a)+ w_2f_2(a)+...+w_nf_n(a)$$
where $\forall i, w_i \in[0,1]$
The Heuristic agent plays a distribution over the moves that is corelated to the value of the moves (moves with higher value have higher probability to be played)

This question might be very basic, I am new to RL.
Currently, the agent uses $n=13$ features.
I have access to daily data of $10^6$ games of agent vs human.
I have a game engine that allows me to run agent-vs-agent games.
The Heuristic agent is a bit weaker than average recreational
humans (win rate of 49%).
The MCTS agent is a bit stronger than average human recreational (win rate of 58%).
I have no good reason to think that linear weights are optimal.  Just thought it's an easier start.
The Reward is observed only at the round's end.  There is no good way to evaluate the reward before the round's end.

It would help if there was a question-mark around the part you are asking.  I see a sequence of statements, not a question.  Help me out here.

Very broad question.  Not sure I understand where 10^36 comes from.  Are the feature weights continuous or discrete?

@EngrStudent, you right, fixed my mistake.   weights are continuous w_i \in [0,1]   The space 10^26 come from my assumption that I will discretize the space and let each weight to be a number between 0 and 1 in jumps of 0.01, thus each weight has 101 options.  Therefore, 100^13 features is equal to 10^26

In a discrete game, like some versions of the knapsack problem, you have to touch every discrete state to be able to find the universal best.  In this you are rounding your continuous variables, so discretization is allowed.  This means that within a single "bin" the values are essentially the same, which implies there exists something like a slope.  I would push in 2 ways: can you discretize more, and does gradient descent (aka slope-climbing) work. You aren't discretizing 2-way or 3-way (or 13-way) interactions.  Extreme chunking: 2^13 = 8192, which is a cheap search.

Consider the options shown here for gradient-free optimization: https://github.com/SimonBlanke/Gradient-Free-Optimizers

Just to clarify, do you want to find $W$ with a reinforcement learning algorithm? Edit your post to clarify that and to further change the title to be specific. Use the tag [tag:algorithm-request], if you're looking for an algorithm.

One thing missing - what are the optimal weights for your problem? Is it the weights that have least error when predicting score, or weights that drive a policy to get the highest score? These require related but different approaches

@NeilSlater, the optimal weights will produce the highest win rate.  Either vs humans or vs a baseline agent.

I think one reason you are not getting many answers is there is more than one thing you need to do to get to a practical self-play game-playing algorithm. Doubly so if the reinforcement-learning tag needs to be applied. Dealing with them all would make for a long answer, thus a lot of work for someone considering writing one.

@NeilSlater, I think that I don't know even what I don't know.  Could you explain what are those things? Currently, I have a game-playing algorithm and I have access to a game engine that can run many agent-vs-agent games.

In brief, search, heuristics used with search, self-play, and for reinforcement learning how to structure  the reward, and the dozen or so RL algorithms that could be employed in your case. Also choosing between linear models with feature engineering vs non-linear models.

Thanks @NeilSlater!  I think that I know part of the material but lucking some fundamentals.  First I made a fair heuristic ~49% win-rate vs humans.  Second step was implementing MCTS (Monte Carlo Tree Search) which produce ~58% win-rate.  Now I want to further improve the the agent.  So I want to use local search or some RL-algorithm in order to find the optimal weights.  For a start I want to find the optimal linear weights.  I think that the reward structure is just win-rate vs a base-line opponent.

@NeilSlater, can you reference some of the simple RL-algorithms that might find strong linear/non linear weights?

My friend propose local random search:
Initialize:

$W_0 = (0.5,...,0.5)$
step = 0.1, $K < N$, MAX_ITERATIONS

Each iteration:

$W_{new}$ <- $W$
randomly choose up to $K$ weights, change each one step up/down.
simulate 5000 games between the 2 agents: $W$ vs $W_{new}$
if the win-rate of $W_{new}$ is higher than 50% then $W$ <- $ W_{new}$

Stop condition: if for 10 iterations $W_{new}$'s win rate < 50%$ or reach MAX_ITERATIONS.

This is a very basic local random search algorithm. You tagged the question "reinforcement-learning" though, and the suggested algorithm is quite far from that.

@NeilSlater, while local search is basic, I it so easy to implement that I will try it, then hill climbing.

Another popular option like LRS is a genetic algorithm. That's just randomly creating a lot of agents, testing them, keeping the best, then creating a new generation of agents from combinations of the best agents plus some random mutations.

And BTW, you might want to specify that the agent chooses the action with the best calculated score. I misunderstood and thought the score was something provided by the game that you were trying to estimate, which was confusing.


text:
What is the state-space complexity of Spades?
AI reached super-human level in many complex games, including imperfect information games such as six-player no-limit Texas hold’em poker.  However, it still did not reached that level in Trick-taking card games such as Spades, Bridge, Skat and Whist.  In a related question, I am asking Why Trick-Taking games are a challenge for AI.
An important factor that makes those games a challenge for AI is their size, to be precise lets talk about the State-space complexity which is define as the number of legal game positions reachable from the initial position of the game  [Victor Allis (section 6.2.4)].
What is the size of Spades?

I have calculated an upper bound and modified a calculation of a lower bound for a similar game.  I assume the real size is closer to the upper bound.
$$ 7.36 \cdot 10^{27} \leq |SPADES| \leq 3.09 \cdot 10^{72} $$
Upper bound
The State-space complexity of Spades can be computed by counting for each possible starting state (deal), all the possible sequences of actions.  While that calculation could be hard, an upper bound is easy to achieve by multiplying the number of initial positions $|S_0|$ by an upper bound on the number of different possible histories $|\bar{H}|$.
$$ |SPADES| = \sum_{s \in S_0} |H_{s}| \leq |S_0| \cdot |\bar{H}| $$
The number of possible starting positions $|S_0|$ is the number of different ways to deal a 52 cards deck into 4 players
$$|S_0| = \frac{52!}{13!^4} \approx 5.3\cdot10^{28}$$
An information set in Spades contains two objects: the player's hand, and the sequence of actions each of the players have made from the start of the round.  Before any card is played, each information set (a single hand) can be completed into a full game-state (4 hands) in the following number of ways
$$ |\bar{S}| = \frac{39!}{13!^3} \approx 8.45 \cdot 10^{16} $$
During a round, each player first decide upon a bid, then choose one out of her 13 cards, than choose one out of 12, etc. Thus, the size of the decision tree, which is the number of histories is bounded by
$$|H| \leq {14!}^4 \approx 5.77 \cdot 10^{43}$$
This is an upper bound since some of those histories violates the rules of the game.
Therefore, the number of legal positions in Spades is bounded by
$$ |SPADES| = \sum_{s \in S_0} |H_{s}| \leq |S_0| \cdot |H| \leq \frac{52!}{13!^4} \cdot {14!}^4  \approx 3.09 \cdot 10^{72} $$
Lower bound
In the paper: Understanding the Success of Perfect Information Monte Carlo Sampling in Game Tree Search, Sturtevant et al. describe a loose lower bound for the size of Skat:

Skat is a 3-player card game with 32 cards, from which 10 are dealt
to each player. There are $$ {32 \choose 10} = 364, 512, 240 $$hands each
player can have and
$$ H := {22 \choose10} \cdot {12\choose10} = 42, 678, 636 $$
hands for the other players which is what constitutes an information set at the start of a game. At the beginning of each trick, the trick leader can choose to play any of his remaining cards. Therefore, there are at least
$$ 10!H \approx 1.54 · 10^{14}$$
information sets. But, from an opponents perspective there
are actually 20 or 22 unknown cards that can be lead, so this
is only a loose lower bound on the size of the tree. This
should clearly establish that even when using short decks it
is infeasible to solve even a single game instance of a trick-based
card game.

Using the same logic to produce a loose lower bound on the size of Spades tree produce the following:
$$ H := {39 \choose 13} \cdot {26 \choose 13} = 8.45 \cdot 10^{16} $$
At the start of the round (before bidding has been made) the number of information sets is lower bounded by
$$ 14!H \approx  7.36 \cdot 10^{27}$$


text:
Is it a requirement/recommendation to normalize my inputs into [0,1] range?
All features of my input dataset, which is going to be used for training a simple multi-layered neural network, are in range $[-1,+1]$ and the output of $NN$ is a single number again in range $[-1,+1]$.
Is it a requirement/recommendation to normalize my inputs into $[0,1]$ range? Or can I feed the first layer (input) straight from the $[-1,+1]$ values?
Also, should I initialize weights and biases to $0$, or to random values with standard distribution?

[0,1] and [+1,-1] won't make much difference most likely

Generally, between -1 and 1 are ideal, though you can get away with a wider range.  For example, using the z-score as the range, you will be outside of this range, sometimes by quite a bit (say, -30 for significantly distant outliers in some cases I've seen), but even then you will be fine.
Anecdotally, you might try training a toy problem like MNIST with and without feature scaling.  You might be surprised that even the range of 0 to 255 will be just fine.
When you start dealing with really large numbers is when you start running into problems.  The learning rate will simply not be large enough to move the weights far enough to learn in any reasonable amount of time.

So using normalized inputs is recommended but the normalization range is not strictly enforced. Right? My voncern was rooted in the fact that many tutorials and examples used normalized inputs in range [0,1], and had ReLU as activation function. I thiught there's a relation between these two (the input range, and the activation function used). Can a NN be trained efficiently using ReLU if the inputs are in range [-1,1] ? Or it's better to use another activation function than is more symmetrical around 0? Like tanh?

That is correct.  Yes.  Don't forget that the bias term can move the data into a range that is useful as needed before it passes through the ReLU.


text:
Why learning with backward process is need in diffusion model despite knowing $q(x_{t-1}|x_t)$
I recently learnt about the diffusion model in deep learning, can someone explain to me if we can induce noise to an input data and make it a gaussian like data, why can't we use the same process in reverse without training a network for denoising to deconstruct the gaussian data to the real image?
in other words, in $q(x_{t-1}|x_t) q(x_t) = q(x_{t-1})q(x_{t}|x_{t-1})$ we do have $q(x_t)$ at the very last step which has become an gaussian through introducing noise in iterative manner, and we know what conditional probabilities are, why we try to approximate $q(x_{t-1}|x_t)$, if it just a gaussian.

If you read the paper High-Resolution Image Synthesis with Latent Diffusion Models, you'll notice that the Gaussian is actually $q(x_{t-1}|x_t, x_0)$, whereas $q(x_{t-1}|x_t)$ is intractable. In this case, even if we know the appropriate distribution, we do not know $x_0$ in the denoising step (as that is ultimately what we are trying to predict) and hence we still have to approximate the posterior with some neural network approximation $p_{\theta}(x_{t-1}|x_t)$.


text:
Continuous state and continuous action Markov decision process time complexity estimate: backward induction VS policy gradient method (RL)
Model Description: Model based (assume known of the entire model) Markov decision process.

Time($t$): Finite horizon discrete time with discounting factor
State($x_t$): Continuous multi-dimensional state
Action($a_t$): Continuous multi-dimensional action (deterministic action)
Feasible(possible action) ($A_t$): possible action is a continuous multi-dimensional space, no discretization for the action space.
Transition kernel($P$): known and have some randomness associated with the current state and next state

Reward function: known in explicit form and terminal reward is know.
The method I tried to solve the model:
Discretize the state space and construct multi-dimensional grid for state space, starting from the terminal state, I used backward induction to reconstruct value function from the previous period. By using the Bellman equation, I need to solve an optimization problem, selecting the best action that gives me the best objective function.
$$V_t(x_t) = max_{a_t \in A_t}[R_t(x_t,a_t) + E[\tilde{V}_{t+1}(x_{t+1})|x_t, a_t]]$$
where $\tilde{V}_{t+1}$ here is an approximation using interpolation method, since the discrete values are calculated from the previous time episode. In other words: $\tilde{V}_{t+1}$ is approximated by some discrete value: $$V_{t+1}(x_0),V_{t+1}(x_1),V_{t+1}(x_2)\cdots V_{t+1}(x_N)$$ where $x_0,x_1,x_2\cdots x_N$ are grid points from discretizing the state space.
In this way, for every time steps $t$, I could have a value function for every grid point and my value function could be approximated by using some interpolation method(probably cubic spline).
But here are some of the problems:

what kind of interpolation is suitable for high dimensional data.
Say we have five dimension for the state, then I discretize the state by giving 5 grid points to every dimension, then there are $5^5 = 3125$ discrete state values I need to calculate through the optimization (curse of the dimensionality).
What kind of optimizer should I use? Since I do not know the shape of the objective function, I do not know if it is a smooth function and I do not know if the function is concave. So I may have to use a robust optimizer, probably some evolutionary optimizer. So eventually I end up with this computational complexity and it takes too long for the computation.

And recently I learned the techniques of policy gradient from OpenAI.
This method avoids using this backward induction and approximating the value function by using interpolation. And obtained the approximated policy by firstly guessing a functional form of the policy and take approximated gradient of the policy function by using sampling (simulation) method. Since the model is known, every time it could sample new trajectories and use that to update the policy by using the stochastic gradient assent method. In this way updating the policy until it gets some sort of convergence.
I am wondering if this type of technique could potentially reduce the computational complexity significantly. Any advice helps, thanks a lot.

Discretizing state/action space will always be a very expensive strategy, in fact I don't think you can do better than exponential time in state/action dimension that way.
Now, you still haven't really explained your algorithm with the discretized states and actions. Given your known models, it sounds like you're planning on doing dynamic programming. This would definitely be an exponential time algorithm. You also haven't explained how you'd use your knowledge of the model in your policy gradient implementation. If you're just using it to sample some trajectories to have more data for updates, policy gradient methods will be much more efficient (poly-time). Otherwise, if you're planning on using your model for some sort of MCTS planning, depending on how you implement that, it could be very inefficient as well.

Thank you for the respond, I agree if I discretize the state space it will be exponential time. And what's really costly is the optimization part, since I do not really know the shape of the function.  So I have to choose my optimizer carefully.

And indeed, my knowledge of the model is used to simulate the some trajectories in order to update my policy.


text:
Transformers: How to use the target mask properly?
I try to apply Transformers to an unusual use case - predict the next user session based on the previous one. A user session is described by a list of events per second, e.g. whether the user watches a particular video, clicks a specific button, etc. Typical sessions are around 20-30 seconds, I pad them to 45 seconds. Here's a visual example of 2 subsequent sessions:

x axis is time in seconds, y axis is the list of events (black line divides the 2 sessions). I extend the vocabulary with 2 additional tokens - start and end of a session (<sos> and <eos>), where <sos> is a one-hot vector at the very beginning and <eos> - similar vector at the end of the session (which makes this long red line).
Now I use these extended vectors of events as embeddings and want to train a Transformer model to predict the next events in the current session based on previous events in this (target) session and all events in the previous (source) session. So pretty much like seq2seq autoregressive models, but in a bit unusual settings.
Here's the problem. When I train a Transformer using the built-in PyTorch components and square subsequent mask for the target, my generated (during training) output is too good to be true:

Although there's some noise, many event vectors in the output are modeled exactly as in the target. After checking train-val-test split is correct, my best guess is that the model cheats by attending to the same day in the target, which the mask should have prevented. The mask is (5x5 version for brevity):
[[0., -inf, -inf, -inf, -inf],
 [0., -inf, -inf, -inf, -inf],
 [0., 0., -inf, -inf, -inf],
 [0., 0., 0., -inf, -inf],
 [0., 0., 0., 0., -inf]]

Note that since I use <sos> in both - source and target - mask[i, i] is set to -inf (except for mask[0, 0] for numerical reasons), so the output timestamp i should not attend to the target timestamp i.
The code for the model's forward method:
def forward(self, src, tgt):
    memory = self.encoder(src)
    out = self.decoder(tgt, memory, self.tgt_mask.type_as(tgt))
    out = torch.sigmoid(out)
    return out

I also tried to avoid the target mask altogether and set it to all -inf (again, except for the first column for numerical stability), but the result is always the same.
Am I using the mask the wrong way? If the mask looks fine, what other reasons could lead to such a "perfect" result?

After shifting the target to the right as suggested in the accepted answer I get the following result:

Which is much more realistic. One suspicious thing is that out[t] now resembles tgt[t - 1], but it can be explained by the fact that the user state tends to be "sticky", e.g. if a user watches a video at t - 1, most likely he will watch it at t as well.

When you say "I use these extended vectors of events as embeddings", do you mean that you do not learn the initial $|dict|$ x $d_{model}$ weight matrix to embed the inputs, but instead feed the inputs raw into the first layer of the transformer? And do you perform any positional encoding? Also, what is the dimension of your model ($d_{model}$ in some papers), and what is the dimension of your mask?

It would also help if we can read the code of your entire Transformer model. Something like the code under "Define the Model" section here (https://pytorch.org/tutorials/beginner/transformer_tutorial.html). Would help us clarify some details like what is self.encoder, self.decoder, etc.

@user3667125 Here's the code for the whole model. It's a PyTorch Lightning module, but you can safely ignore all methods except for __init__() and forward(). The loss should also be irrelevant. Regarding "embeddings", yes, you got it right: my sequences are not tokens, but instead vectors of events, so I decided to use them directly instead of usual embeddings, without learnable matrix or positional encoding. $d_{model} = 14$, sequences are padded to 45 seconds and thus mask is 45x45.

Can you confirm if a single instance have dimension $45$ x $14$ (and therefore a batch has dimension $45$ x $batchSize$ x $14$)? And can you explain why the mask diagonal entries mask[i, i] = -inf? Normally they would be 0.

Also, what is the reasoning behind type-casting the mask? self.tgt_mask.type_as(tgt) -- have you tried without using the .type_as typecasting?

@user3667125 That's correct, single instances of both - source and target - have shape $45 \times 14$. As far as I understand, PyTorch uses an additive mask, so -inf is what is suggested in the tutorial you pointed to earlier as well as in the Transformer module docs. I use .type_as() to convert mask to the same device because for whatever reason Lightning doesn't move it to GPU automatically. But on CPU and without .type_as() the problem still persists.

By the way, thank you for your quick replies!

My understanding of the tutorial I linked is that generate_square_subsequent_mask() creates a mask matrix similar to yours, but the diagonals mask[i, i] are all 0. This is so that the current token/time step can attend to itself, as well as the past tokens/time steps. Can you try with the mask where all the diagonals are 0? Also, I'm not sure on the .type_as() usage, since the docs says .type_as() is meant to typecast the tensor (e.g. from an int to a float). Can you try moving the device via .to(device), and remove the .type_as() function entirely?

Also, just to confirm, both src and tgt have dimensions $45$ x $batchSize$ x $14$ right? And not $batchSize$ x $45$ x $14$? The dimensionality is a bit counter-intuitive to me, but that seems to be what PyTorch is expecting for the Transformer functions.

@user3667125 Yep, source, target and generated output all have size $45 \times batchSize \times 14$. Removing .type_as() didn't change the result. Mask with all zeros on the main diagonal (and below it) didn't change the result too. Shouldn't we avoid zeros (i.e. unmasked positions) on the main diagonal? As far as I understand, in autoregressive settings when generating output at position i we should avoid attending to target at position i, i.e. set mask[i, I] = -inf.

Note that in the tutorial they use the mask for the source sequence, while I want to attend to the whole source (no mask) and only to the previous positions in the target sequence (square matrix with -inf on the main diagonal and below). But the results suggest I'm doing something wrong.

Let us continue this discussion in chat.

The main issue during training is that you haven't right-shifted the input of the decoder, which is probably why you set the diagonals of mask to -inf (when it should be $0$).
Also, just an FYI, although you haven't focused on evaluation/prediction yet, I will explain the evaluation/prediction here as well for completeness, since it works so differently than training, and also since you will need it when generating the graphs for debugging.
Training
Both tgt and tgt_mask should be changed to simulate auto-regressive properties.
You are feeding in tgt as the input to the decoder, where tgt is the ground truth target sequence to predict. tgt should have dimension length(sequence) x batchSize x $\|dict\|$. Additionally, you are feeding in mask where the diagonals are -inf.
Instead, you should do the following:

Add 2 new special tokens to your vocabulary that signals the start and end of decoding, i.e. <START> and <END>. So your vocabulary will need to be extended to 16 events.
Every input to the decoder (training, evaluation, prediciton) should have <START> as the first token. So during training, when you want to feed in tgt to the decoder, you should right-shift tgt by adding in the <START> token at the beginning.

tgt_shifted will now be of dimension length(sequence)+1 x batchSize x $\| dict \|$
tgt_shifted_mask will now be of dimension length(sequence)+1 x length(sequence)+1. Diagonal should be all $0$
the inputs to the decoder should be tgt_shifted, tgt_shifted_mask, and memory
the output of the decoder will have dimension length(sequence)+1 x batchSize x $\| dict\|$, and will not be right-shifted because it will not have <START> as the first word. But it should have <END> as the last word.
Append <END> to the ground truth tgt, and turn it into one-hot encoding, so tgt should have dimension length(sequence)+1 x batchSize x $\|dict\|$. Your loss operator should be some sort of element-wise comparison between tgt and the output of the decoder.

Note that you only run the decoder once per training batch during training, i.e. the decoder simultaneously predicts the logits of all length(sequence) tokens at the same time. On the other hand, during evaluation/prediction, you must run the decoder length(sequence) times, since you can only use the decoder to predict one token at a time.
Evaluation/Prediction
During evaluation/prediction, the model should generate its own sentence entirely from scratch, one word at a time:

out should be initialized as a single token, <START>, and have dimensions $1$  x batchSize x $\|dict\|$.
Do the following in a loop until termination or max output length is reached:

Generate a out_mask for the current version of out. out_mask should be a matrix with dimension length(out) x length(out). Diagonal should be all $0$
Pass out, out_mask, and memory into the decoder layer. The output of the decoder will be a length(out) x batchSize x $d_{model}$ tensor (note that in your case, $d_{model} = \|dict\|$), which indicates tokenIdx x batchIdx x vocabularyIdx
Convert the last time step (e.g. decoderOutput[-1,:,:] if all sequences in your batch have the same length) into probabilities, and take all the events that surpasses some probability threshold and set them to $1$. Set all other events to $0$. This is the new time step that the decoder layer predicts. So add this time step to out to append it's length by $1$.
Repeat the previous 3 steps in a loop until you reach the <END> token, which signals the end of decoding, or until the max output length is reached.

During evaluation, you can calculate the validation loss by using the logits of only the final iteration of the decoder (which should have dimension length(sequence)+1 x batchSize x $\|dict\|$), and compare those logits with the ground truth with the <END> token added at the end (resulting in dimensions length(sequence)+1 x batchSize x $\|dict\|$).

Sorry, I wasn't clear about this - I get this issue specifically during training, not inference time. Here's how I understand training should go: for an output token at timestamp t we  give a model the whole src sequence as well as tgt[0 : t-1]. It's not like generating the whole sentence in English given a sentence in French, but instead like predicting the next word user is going to write given previous sentence and previous words in this sentence user has already written. IIUC, for each out[t] mask should hide tgt[t : ] even though training loop sees the whole tgt.

But visualization in the question shows that out[t] is extremely similar to tgt[t]. I can think of 2 reasons for this - overfitting or wrong usage of the mask. I have already checked that the visualization is done on the test set, so the problem must be the mask.

Perhaps, the question can be reduced to: is decoder(tgt, memory, subsequent_mask) the correct way to predict all outputs in parallel, restricting each out[t] to see only true values tgt[ : t - 1]?

Thanks for the clarification. I have edited my answer which should help with all the things you mentioned. Let me know if there's anything further to clarify.

Thanks! I appreciate your time and patience. Indeed, I used a shifted mask instead of shifted target for the same reason you described, but I could have made a mistake in it and your version looks more common anyway. So I'm going to update the code as you suggest and come back with the result!

After shifting the target the prediction during training looks much more realistic - see the edited post for visualization. I still have some doubts regarding my implementation, but anyway, your answer is a great tutorial for people coming here with similar issues. Thanks a lot for your help!

Glad it helped! One more thing I'd verify is why out[t] resembles tgt[t-1] though -- it does seem weird. Wouldn't be surprised if there's an off-by-one somewhere, since we shift things so many times by 1 token.

It's pretty natural for my task to have tgt[t] resembling tgt[t - 1], so the model is expected to learn something like this. But yes, having a similar mistake previously I look at it very carefully :)

@user3667125 so should we also using the mask during the testing time? I thought during the testing the masks should be set to None, am I wrong?

@Alex I think this answers your question.


text:
A way to leverage machine learning to reduce DFS/BFS search time on a tree graph?
I'm not very knowledgeable in this field but I'm wondering if any research or information already exists for the following situation:
I have some data that may or may not look similar to each other. Each represents a node that represents a vector of size 128.

And they are inserted into a tree graph according to similarity.

and a new node is created with an edge connecting the most similar vertex node found in the entire tree graph.
Except I'm wasting a lot of time searching through the entire graph to insert each new node when I could narrow down my search according to previous information. Imagine a trunk node saying "Oh, I saw a node like you before, it went down this branch. And don't bother going down that other branch." I could reduce the cost of searching the entire tree structure if there was a clever way to remember if a similar node went down a certain path.
I've thought about some ways to use caching or creating a look-up table but these are very memory intensive methods and will become slower the longer the program runs on. I have some other ideas I am playing around with but I was hoping someone could point me in the right direction before I started trying out weird ideas.
Edit: added a better (more realistic) graph picture

might be late, but if your similarity metric abide the triangle inequality $d(a,c) \leq d(a,b) + d(b,c)$, you can use M-Tree (metric tree) to store/retrieve the node more efficiently. You can also query K-closest node by using M-Tree.

Thank you for answering! That's a great idea to explore, as I haven't seen a good solution to tackle this problem yet

It sounds like you may be looking for the A* search algorithm. It is a search algorithm, like DFS and BFS, but it will explore only the most promising branches based on a heuristic function you supply. The difficult part of implementing this is deciding on a low-cost, admissible heuristic.
Excited to reflect nbro's suggestion from comments.

A* does not really prune branches, but it explores branches according to the admissible heuristic, so, more intuitively, we could say that it explores branches based on how promising they are, but it doesn't really discard any branch. I'm not sure if A* is really the solution the problem.

I would say that within the search space branches are "pruned" if they are never explored. Is there other terminology for that you would look for?

The reason why I think "prune" may not be the most appropriate term here is that, if there's no goal and the graph is finite, for instance, A* should explore all nodes, so, in that case, it doesn't prune anything. However, you're right that it may not visit certain parts of the search space if all paths that lead to the goal from a start node have already been explored, so, in those cases, we can think of certain parts of the search space being pruned. So, I was a bit imprecise in my previous comment, so your description was right (but not applicable in all cases).

In any case, I'm still not sure whether A* is the right tool to solve OP's problem. Maybe you should try to explain more in detail how A* should be applied in the OP's case.

Thank you guys for answering my question! I didn't know that kind of search algorithm was called the A* search algorithm. But nbro has a point since it seems like the A* algorithm requires a destination to work towards. This problem is a real head-scratcher because the data isn't discrete; it's like drawing lines in the sand to mark how far the waves reach into the beach. Using a heuristic has it's merits but it breaks down when that heuristic comes down to a razor's margin at a fork in the road.

I also edited my post to include a better picture of a graph I'd be dealing with. Each branch represents a cluster/sub-cluster. And it would reduce my search time exponentially if I could just "prune" the first few major branches and contain my DFS/BFS in a sub-cluster. The best way to do that would be keep some memory about where previous nodes ended up. At first the associations would be weak but grow stronger with more nodes being placed, and stronger associations would translate to greater confidence in which path a node should take.


text:
Why isn't RL considered a continual learning strategy itself?
I have read about methods that apply continual learning strategies to reinforcement learning.
Since reinforcement learning also learns step by step (i.e., task by task, in a sense) during the training phase, why isn't it itself considered a continual learning strategy?
Of course, I understand that if an agent catastrophically forgets previously learned tasks, there is a need to prevent this and therefore develop strategies to mitigate catastrophic forgetting, but my question is more about the definition. If continuous learning (or online learning) is about learning one task at a time, and RL somehow does this, why is it not considered a continual learning strategy (regardless of the fact that it may not be as effective)?
To clarify, I haven't read anywhere the claim that RL is not a CL approach, but also none that it would be. Only the fact that CL methods are proposed for RL gives me the impression that RL is not considered an approach. Nor have I seen anyone mention RL for this purpose. I'm just wondering why that is.

To support your claims that RL is not a continual learning approach, you should probably cite 2-3 research papers that claim that.

I didn't see any papers particularly stating that it is not, but since there are suggestions for other methods on top of RL, it seems like that it isn't considered as CL. But that might be just an impression on me, perhaps it is wrong. That's why I'm asking

The reason why I am asking this is because I know people that have done research on RL by considering it a continual learning technique, which is a reasonable thing to do. In any case, I know, as you also know, that people have developed approaches to deal with catastrophic forgetting in RL too, and that's probably why you're asking this question. So, I suggest that you at least cite 1-2 papers that do this and that made you ask this question.

Anyway, I think the answer to your question is that it depends on your definition of "continual learning". If, by continual learning, you mean "continually learning without catastrophic forgetting", then, RL, is generally not a continual learning technique, because we are aware of the fact that certain RL algorithms suffer from CF. However, if you just mean "the potential ability to continually learn from more and more data", then RL could be considered a continual learning technique.

Ah okay! I'm glad you support my assumption that it depends on the definition. Can you give me some examples for papers in which RL was used as CL technique?


text:
Is object-based representation of the observation space feasible?
I just started working on a DRL project from scratch. The state of each episode can be expressed as a state set $S=(S^A, S^B, S^C, S^D)$. Each subset is a feature set of a constituent component of the environment, say, $S^A=(a_1, a_2, a_3)$. To model components, I decided to create four pythonic classes with attributes as features. For example, class A is like:
class A:
    def __init__(self, a1, a2, a3):
        self.a1 = a1
        self.a2 = a2
        self.a3 = a3

Each class has some methods that help in the interaction with other components (classes) and is used in the environment's step function to generate actions.
I am going to create one instance of class A, 10 instances of class B, 20 instances of class C, and a random number of between 1-10 instances of class D at the beginning of each episode. So, my observation includes 33-42 states of entities.
As far as I know, the observation space is usually encoded in n-dimensional arrays as it is in OpenAI Gym. Is it possible, feasible, or considered good practice to store instances as a sub-state of the whole observation space? In my case, it would be like storing 33-42 instances in an array (list) of 33-42 elements.
Thanks for your time and suggestions!


text:
How to express a fully connected neural network succintly using linear algebra?
I'm currently reading the paper Federated Learning with Matched Averaging (2020), where the authors claim:

A basic fully connected (FC) NN can be formulated as: $\hat{y} = \sigma(xW_1)W_2$ [...]
Expanding the preceding expression
$\hat{y} = \sum_{i=1}^{L} W_{2, i \cdot } \sigma(\langle x, W_{1,\cdot i} \rangle))$, where $ i\cdot$ and $\cdot i$ denote the ith row and column correspondingly and $L$ is the number of hidden units.

I'm having a hard time wrapping my head around how it can be boiled down to this. Is this rigorous? Specifically, what is meant by the ith row and column? Is this formula for only one layer or does it work with multiple layers?
Any clarification would be helpful.

The equation $$\hat{y} = \sigma(xW_\color{green}{1})W_\color{blue}{2} \tag{1}\label{1}$$ is the equation of the forward pass of a single-hidden layer fully connected and feedforward neural network, i.e. a neural network with 3 layers, 1 input layer, 1 hidden layer, and 1 output layer, where

the input layer is connected to the hidden layer (all scalar inputs are connected to every neuron in the hidden layer)
the hidden layer is connected to the output layer (all neurons in the hidden layer are connected to all neurons in the output layer

As an example, suppose that we have $N$ real-valued features, there are $L$ hidden units (or neurons) and $M$ output units, then the elements (feature vector and parameters) of equation \ref{1} would have the following shape

$x \in \mathbb{R}^{1 \times N}$
$W_\color{green}{1} \in \mathbb{R}^{N \times L}$
$W_\color{blue}{2} \in \mathbb{R}^{L \times M}$

$\sigma$ is an activation function that is applicable to all elements of the matrix separately (i.e. component-wise). So, $\hat{y} \in \mathbb{R}^{1 \times M}$.
The equation
$$
\hat{y} = \sum_{\color{red}{i} = 1}^{L} W_{\color{blue}{2}, \color{red}{i} \cdot} \sigma(\langle x, W_{\color{green}{1}, \cdot \color{red}{i}} \rangle )\label{2}\tag{2}
$$
is another way of writing equation \ref{1}.
Before going to the explanation, let's try to understand equation \ref{2} and its components.

$W_{\color{green}{1}, \cdot \color{red}{i}} \in \mathbb{R}^N$ is the $\color{red}{i}$th column of the matrix that connects the inputs to the hidden neurons, so it is a vector of $N$ elements (note that we sum over the number of hidden neurons, $L$).

Similarly, $ W_{\color{blue}{2}, \color{red}{i} \cdot} \in \mathbb{R}^M$ is also a vector, but, in this case, it is a row of the matrix $ W_{\color{blue}{2}}$ (rather than a column: why? because we use $\color{red}{i} \cdot$ instead of $\cdot \color{red}{i}$, which refers to the column).

So, $\langle x, W_{\color{green}{1}, \cdot \color{red}{i}} \rangle$ is the dot (or scalar) product between the feature vector $x$ and the $\color{red}{i}$th column of the matrix that connects the inputs to the hidden neurons, so it's a number (or scalar). Note that both $x$ and $W_{\color{green}{1}, \cdot \color{red}{i}}$ have $N$ elements, so the dot product is well-defined in this case.

$ W_{\color{blue}{2}, \color{red}{i}} \sigma(\langle x, W_{\color{green}{1}, \color{red}{i}} \rangle))$ is the product between a vector of shape $M$ and a number $\sigma(\langle x, W_{\color{green}{1}, \cdot \color{red}{i}} \rangle )$. This is also well-defined. You can multiply a real-number with a vector, it's like multiplying the real-number with each element of the vector.

$\sum_{\color{red}{i} = 1}^{L} W_{\color{blue}{2}, \color{red}{i} \cdot} \sigma(\langle x, W_{\color{green}{1}, \cdot \color{red}{i}} \rangle )$ is thus the sum of $L$ vectors of size $M$, which makes $\hat{y}$ also have size $M$, as in equation \ref{1}.

Now, the question is: is equation \ref{2} really equivalent to equation \ref{1}? This is still not easy to see because $xW_\color{green}{1}$ is a vector of shape $L$, but, in equation \ref{2}, we do not have any vector of shape $L$, but we have vectors of shape $N$ and $M$ (and the vectors of shape $M$ are summed $L$ times). First, note that $\sigma(xW_\color{green}{1}) = h\in \mathbb{R}^L$, so $hW_\color{blue}{2}$ are $M$ dot products collected in a vector (i.e. $\hat{y} \in \mathbb{R}^M$), where the $j$th element of $\hat{y}$ was computed as a summation of $L$ elements (a dot product of two vectors is the element-wise multiplication of the elements of the vectors followed by the summation of these multiplications). Ha, still not clear!
The easiest way (for me) to see that they are equivalent is to think that $\sigma(xW_\color{green}{1})$ is a vector of $L$ elements $\sigma(xW_\color{green}{1}) = \ell = [l_1, l_2, \dots, l_L]$. Then you know that to multiply this vector with $\ell$ (from the left), you actually perform a dot product between $\ell$ and each column $W_\color{blue}{2}$. A dot product is essentially a sum, and that's why we sum in equation \ref{2}. So, essentially, in equation \ref{2}, we first multiple $l_1$ with the first row of $W_\color{blue}{2}$ (i.e. by all elements of the first row). Then we multiply $l_2$ by the second row of $W_\color{blue}{2}$. We do this for all $L$ rows, then we sum the rows (to conclude the dot product). So, you can think of equation 2 as first perform all multiplications, then summing, rather than dot product-by-dot product.
So, in my head, I have the following picture. To simplify the notation, let $A$ denote $W_\color{blue}{2}$, so $A_{ij}$ is the element at the $i$th row and $j$th column of matrix $W_\color{blue}{2}$. So, we have the following initial matrix
$$
A =
\begin{bmatrix}
A_{11} & A_{12} & A_{13} & \dots & A_{1M} \\
A_{21} & A_{22} & A_{23} & \dots & A_{2M} \\
\vdots & \vdots & \vdots & \dots & \vdots \\
A_{L1} & A_{L2} & A_{L3} & \dots & A_{LM} \\
\end{bmatrix}
=
\begin{bmatrix}
W_{\color{blue}{2}, \color{red}{1} \cdot}  \\
W_{\color{blue}{2}, \color{red}{2}  \cdot} \\
\vdots  \\
W_\color{blue}{2, \color{red}{L}  \cdot} \\
\end{bmatrix}
$$
Then, in the first iteration of equation \ref{2}, we do the following
$$
\begin{bmatrix}
l_1 A_{11} & l_1 A_{12} & l_1 A_{13} & \dots & l_1 A_{1M} \\
A_{21} & A_{22} & A_{23} & \dots & A_{2M} \\
\vdots & \vdots & \vdots & \dots & \vdots \\
A_{L1} & A_{L2} & A_{L3} & \dots & A_{LM} \\
\end{bmatrix}
$$
In the second, we do the following
$$
\begin{bmatrix}
l_1 A_{11} & l_1 A_{12} & l_1 A_{13} & \dots & l_1 A_{1M} \\
l_2 A_{21} & l_2 A_{22} & l_2 A_{23} & \dots & l_2 A_{2M} \\
\vdots & \vdots & \vdots & \dots & \vdots \\
A_{L1} & A_{L2} & A_{L3} & \dots & A_{LM} \\
\end{bmatrix}
$$
Until we have
$$
\begin{bmatrix}
l_1 A_{11} & l_1 A_{12} & l_1 A_{13} & \dots & l_1 A_{1M} \\
l_2 A_{21} & l_2 A_{22} & l_2 A_{23} & \dots & l_2 A_{2M} \\
\vdots & \vdots & \vdots & \dots & \vdots \\
l_L A_{L1} & l_L A_{L2} & l_L A_{L3} & \dots & l_L A_{LM} \\
\end{bmatrix}
$$
Then we do a reduce sum across the rows to end the dot product (i.e. for each column we sum the elements in the rows). This is exactly equivalent to first performing the dot product between $\ell$ and the first column of $W_\color{blue}{2}$, then the second column, and so on.