text:
Is this LSTM model underfitting?
I think this model is underfitting. Is this correct?

_________________________________________________________________
Layer (type)                 Output Shape              Param #
=================================================================
lstm_1 (LSTM)                (50, 60, 100)             42400
_________________________________________________________________
dropout_1 (Dropout)          (50, 60, 100)             0
_________________________________________________________________
lstm_2 (LSTM)                (50, 60)                  38640
_________________________________________________________________
dropout_2 (Dropout)          (50, 60)                  0
_________________________________________________________________
dense_1 (Dense)              (50, 20)                  1220
_________________________________________________________________
dense_2 (Dense)              (50, 1)                   21
=================================================================

The above is a summary of the model.
Any advice on how the model could be improved?

I'd recommend renaming the Question Title to "Is this LSTM model underfitting?" rather than "Is this Keras LSTM model underfitting?" because there is nothing specific to keras in this question.

You need to include optimizer you used to make sure it is correct.
By the way, your drop-out layers are not going to do anything, so you should take them away.
You likely don’t have test and train data in time-series because all data points are connected. It just has prediction value and ground truth of each period.
I recommend you use the whole dataset and rotate changing hyper-parameters of LSTM to find the best model.


text:
What is exactly the role of commutative property in a Constraint Satisfaction Problem?
I have been looking into the backtracking search for CSPs, and understand that if we just plainly do a typical depth-limited search we have a vast tree with leaves size $n!d^n$ where $n$ is the number of variables and $d$ the domain size. It can also be easily understood that there exists instead only $d^n$ complete assignments. So the reason for the the tree being so large is attributed to the fact that we are ignoring the commutative way of variable assignments in CSP. Can anyone please explain, as to how exactly this commutative property affects?

I just want to comment on my own understanding of commutative variable selection. So, if I correctly understand that if we select only a single variable at an instance and then select another one (minus the previous one) it is similar to as if we would have done the selection vice versa (commutative). So, isn't DFS following this naturally?

(Assuming we don't consider some objective function) a CSP has a finite depth that corresponds with its goal state. Think of Sudoku - every solution necessarily fills up the whole board. That is, anytime we reach a depth equal to $n$, where $n$ is the total variables, then we have a reached a goal. Therefore, we don't care about the path that gets us to the goal. In other types of problems where we care about finding the shortest path, assigning the wrong variable might lead us to a goal with an inefficient path. In CSP though, we're happy to end up at any goal so any path we take will not affect the outcome. If we reach a dead end we can always backtrack and try a different branch.

source: Stack Exchange

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

sort: votes


text:
NEAT - Managing species across generations
I (mis?)understood the NEAT algorithm has the following steps:

Create a genome pool with N random genomes
Calculate each genome fitness
Assign each genome to a species
Calculate the adjusted fitness and the number of offspring of each species
Breed each species through mutation/crossover from the stronger genomes
go to step 2.

Step 3 is tricky: speciation is made placing each genome G in the first species in which it is compatible with the representative genome of that species, or in a new species if G is not compatible with any existing species. Compatible is meant as having compabilitity distance below a certain threshold. Regarding representative genome NEAT paper says:

Each existing species is represented by a random genome inside the
  species from the previous generation

Somewhere I've found that keeping the number of species stable is good, and this is achieved automatically with dynamic thresholding. However, dynamic thresholding makes hard to evaluate species behaviour across generations.
Let me give one example:
Assume that in Generation 20, Species 1 has Genome A as representative and Species 2 has Genome B as representative. Assume elitism is implemented.
As the representative genome is taken from previous generation, assume that in Generation 21, Genome A and B are still representatives for Species 1 and 2, however assume compatibility threshold has changed (i.e. bigger) in order to reach the target species number. With this change, A and B have now a compatibility distance lower than threshold and should be placed in the same Species, however they are representatives of different species.
How to solve this issue?
More in general, with dynamic thresholding, how to make sure species management across generations is consistent? E.g. NEAT paper also says:

If the maximum fitness of a species did not improve in 15 generations,
  the networks in the stagnant species were not allowed to reproduce.

How to make sure that across all 15 generations, we are still considering that same single species and this has not drastically changed (so that they are actually different 'objects'?). E.g. in the example above, if A and B are both placed in Species 1 in Generation 21, Species 2 no longer represents what it represented in Generation 20.

In SharpNEAT v2 I dropped the speciation scheme described in the original NEAT paper and replaced it with k-means applied to the genomes (see: http://sharpneat.sourceforge.net/research/speciation-kmeans.html), however, I believe the speciation approach as a whole remains an untested hypothesis.

I think in the specific case you described if the representatives are now compatible you would move the lower fitness representative into the higher fitness representatives species, then with the remainder of the lower representatives species (all other genomes that didnt have compat distances close enough to move into the other species) you would just randomly pick a new representative and carry on with the process.

In some implementations, the specie representatives change each generation. This allows for a dynamic definition of what a specie is. If you speciate from scratch(meaning each specie is assigned a new representative) every generation, you won't have the problem where a representative leaves its specie.

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


text:
How do I calculate the gradient of the hinge loss function?
With reference to the research paper entitled Sentiment Embeddings with Applications to Sentiment Analysis, I am trying to implement its sentiment ranking model in Python, for which I am required to optimize the following hinge loss function:
$$\operatorname{loss}_{\text {sRank}}=\sum_{t}^{T} \max \left(0,1-\delta_{s}(t) f_{0}^{\text {rank}}(t)+\delta_{s}(t) f_{1}^{\text {rank}}(t)\right)$$
Unlike the usual mean square error, I cannot find its gradient to perform backpropagation.
How do I calculate the gradient of this loss function?

You will either need to contact the authors and hope at least one responds with the equation or you need to calculate it yourself.  The following article might help you: https://twice22.github.io/hingeloss/

Hinge loss is difficult to work with when the derivative is needed because the derivative will be a piece-wise function. max has one non-differentiable point in its solution, and thus the derivative has the same. This was a very prominent issue with non-separable cases of SVM (and a good reason to use ridge regression).
Here's a slide (Original source from Zhuowen Tu, apologies for the title typo):

Where hinge loss is defined as max(0, 1-v) and v is the decision boundary of the SVM classifier. More can be found on the Hinge Loss Wikipedia.
As for your equation: you can easily pick out the v of the equation, however without more context of those functions it's hard to say how to derive. Unfortunately I don't have access to the paper and cannot guide you any further...

I disagree with the earlier answer that this is difficult to calculate. If we have the function
\begin{align*}
\sum_{t\in\mathcal{T}}  \max \{0, 1 - d(t) \, y(t, \theta)\}
\end{align*}
the gradient with respect to $\theta$ is
\begin{align*}
& \sum_{t\in\mathcal{T}}g(t) \\
& g(t) := \begin{cases}
 0 & \text{ if }1 - d(t) y(t, \theta) < 0 \\
 -d(t)\dfrac{\partial y}{\partial \theta} & \text{ otherwise} \\
\end{cases}
\end{align*}
Theoretically this is ok, it just means that the gradient is not continuous. However, the objective is still continuous assuming that $d$ and $y$ are both continuous.
In practice, it's not a problem either. Any automatic differentiation software (tensorflow, pytorch, jax) will handle something like this automatically and correctly.


text:
Optimize parametric Log-Likelihood with a Decision Tree
Suppose there are some objects with features, and the target is parametric density estimation. Density estimation is model-based. Parameters are obtained by maximizing log-likelihood.
$LL = \sum_{i \in I_1} \log \left( \sum_{j \in K_i} \theta_j \right) + \sum_{i \in I_2} \log (1 - \sum_{j \in L_i} \theta_i)$
Assume that parameters $\theta_j$ are probabilities, i.e.  $0 < \theta_j < 1$, and that $\sum_{j\in L_i} \theta_i < 1$. From practical perspective, it seems natural to make parameters $\theta_j$ themselves functions of features, i.e. $\theta_j = F(x_j^1, \ldots, x_j^m)$.
Is there any known standard method or heuristic to optimize such objective with a decision tree, i.e. we assume that our function $F$ is a decision tree?
Any related results are welcome.


text:
Why are optimization algorithms for deep learning so simple?
From my knowledge, the most used optimizer in practice is Adam, which in essence is just mini-batch gradient descent with momentum to combat getting stuck in saddle points and with some damping to avoid wiggling back and forth if the conditioning of the search space is bad at any point.
Not to say that this is actually easy in absolute terms, but after a few days, I think I got most of it. But when I look into the field of mathematical (non-linear) optimization, I'm totally overwhelmed.

What are the possible reasons that optimization algorithms for neural networks aren't more intricate?

There are just more important things to improve?
Just not possible?
Is Adam and others already so good that researchers just don't care?

Can you give some examples from mathematical optimisation that compare well with problems ADAM tries to address?

I think that 1 or more of your questions are already partially answered here. I am not an expert on this topic, so I can't say more about it. By the way, if you think that post and answer are useful, you should upvote them!. Finally, I am not going to close (for now) this post as a duplicate of that one because you're not asking the same question, although they are very related. It seems that your question is slightly more general.


text:
Recommended way to spilt image sequence for training/validation/testing
For object detection tasks I have a few minutes of video footage from a surveillance camera, converted to a sequence of images and ground truth bounding boxes for all people walking by.
Now what's the best way to split this into training, validation and test sets (80/10/10)?

I could randomly select 10% for testing and 10% for validation and rest into training.
The first 80% go into training, next 10% to validation, rest to testing.

The first way has the advantage of having a good distribution of different people walking by and also more varying densities and locations of people in the test set. But the disadvantage would be that for each testing image a very similar image exists in the training set.
The second way would have the advantage of the testset being more truly "never seen" during training, but at cost of less variety.


text:
Derive information for sub-scoring from one scoring model
I am currently working in Python with a random forest algorithm to perform a scoring. My output is binary.
The idea now is to derive sub-scores from the above model that give an opinion on different topics within my dataset.
Unfortunately, I don't have an output variable for these sub-scores in my dataset, so I have the idea of deriving the information from the feature importance of the larger model.
Any ideas on how to do this methodically?
As an example:
The goal is to determine if a person is creditworthy. The dataset contains a lot of information about the person's occupation, the area where he/she lives, past payment history etc. Now I want a score for overall creditworthiness and sub-scores for

Job features
Features on the housing situation
Features on the payment history/behaviour


text:
Is there any concept like 'applying affine transformation on multiple inputs'?
Affine transformation on $X$ is a transformation of the following form
$$Y = wX + b$$
In general, $w, X, Y$ and $b$ tensors.
We generally call tensor $X$ as an input to affine transformation or the tensor which we want to transform. We call $w, b$ as weight and bias tensors respectively. We call $Y$ as output tensor after transformation. Every layer of multi layer percetron contains an affine transformation.
Suppose I have two types of inputs, say $X_1, X_2$.  Now, I want to apply affine transformation on them using other.
Consider the following
#1: Combining using individual affine transformations
$$Y_1 = w_1X_1 + b_1$$
$$Y_2 = w_2X_2 + b_2$$
$$Y_1Y_2 = w_1w_2X_1X_2 + w_1b_2X_1 +w_2b_1X_2 + b_1b_2$$
#2 multiplying them and applying affine
$$Y = wX_1X_2 + b$$
#3 concatenating them and applying affine
$$Y = w (X_1, X_2) + b$$
Does anyone of the above eligible to call affine transformation in terms of $X$ and $Y$ (not $XY$)? If not, is it true that there is nothing like affine transformation on two inputs taken together?


text:
Are mean and standard deviation in variational autoencoders unique?
In general, if I have a collection of data then mean(Expectation) and standard deviation are calculated as follows
$$\text{mean } = \mu = \mathbb{E}[X] = \sum\limits_{i = 1}^n p_ix_i $$
$$\text{Variance =}\sigma (X) = \sqrt{\sum\limits_{i = 1}^{n}p_i{(x_i - \mu)^2}{}}$$
where $X$ is a random vector having support $\{x_1, x_2, x_3, \cdots, x_n\}$.
Thus a dataset of samples have a single mean and single variance.
Now, let us discuss about the case of variational auto-encoders. They look like follows

Suppose I trained the above auto-encoder on a training set, then for each sample I will get a mean and standard deviation at latent layer. Here, we can get a new $\mu$ and $\sigma$  for each data sample. But, as we see earlier, mean and standard deviation exists for a dataset and not for each sample.
I am confused about "how can we say that mean and standard deviation are obtained at latent layer if they are not constant in nature"?

I don't want to edit your question, but I believe you have put "Variance" where you should have put "Standard Deviation" in the formula with $\sigma (X)$.  However, the formula on the right hand side isn't quite right for stddev (or certainly for variance)

Mean $\mu(x)$ and standard deviation $\sigma(x)$ are actually learnable functions, whose parameters are adjusted via the back propagation procedure.
Mean and standard deviation are not computed on the input vector $x$ or any transform of it.
The procedure is the following:

Pass the sample $x$ from the training data

Propagate this vector $x$ through some NN (Feedforward MLP) and obtain some other vector $\tilde{x}$
Get the mean $\mu(x)$ and std $\sigma(x)$ from $\tilde{x}$ from two more neural networks (maybe single layer)

Generate random noise $\varepsilon$ and get a point in the latent space $\mu(x) + \sigma(x) \varepsilon$ (it is known as reparametrization trick)

You can think about the procedure as follows - you have Normal distribution around each point of the input data in the latent space, and the mean $\mu(x)$ and $\sigma(x)$ are the parameters of this distribution (different for each point). The generated data is expected to resemble the training example, but differ in some reasonable sense, belong to the manifold of realistic images.

But, what is the gaurentee for us that those single feed forward layers are indeed calculating mean and standard deviation? Is there any reason behind calling them as mean and standard deviation?

@hanugm they are defined to do this. Given any reference sample $x$ during many enough forward passes with the fixed parameters of networks $\mu(x)$ and $\sigma(x)$ - the point cloud to which this point will be mapped will have mean $\mu(x)$ and standard deviation $\sigma(x)$. It is guaranteed by the reparametrization trick.

The answer relies in the KL item of the loss function -
it regularizes (=enforce) the distribution of z (represented by mu and sigma)
to be close to N(0,1).
That's the meaning of the KL divergence - a distance measure between probabilities and in order to minimize that penalty item - the network will tune it's parameters such that the z would be very close to N(0,1).


text:
How do I select the class weights for the loss function in the case of more than 2 classes?
I have a machine learning task where I would like to weight losses based on the frequency of the categorical values appearing in the data. The binary solution can be seen below, but I'd like to know what to do about the case of n>2 categories.
w_0 = (n_0 + n_1) / (2.0 * n_0)
w_1 = (n_0 + n_1) / (2.0 * n_1)

The frequencies for the samples n0-n5 are:
n_0:     1552829
n_1:     14479
n_2:     13445
n_3:     13781
n_4:     18795
n_5:     64187

What do you hope to get out of weighting the loss function?

Is that what you want?
w_0 = (n_0+n_1+ ... +n_5) / (5.0 * n+0)

If so, it can be achieved by:
    n = [n_0, n_1, n_2, ...]
    w = []
    for i in range(len(n)):
      w[i] = sum(n) / (len(n)*(n[i]))

Notice that Sum(n)/Len(n) = Average(n), so you'd basically saying your loss-function is avg(n)/ni.


text:
Should I need to use BERT embeddings while tokenizing using BERT tokenizer?
I am new to BERT and NLP and I am a little confused with tokenization and word embedding.
My doubt is if I use the BertTokenizer for tokenizing a sentence then do I have to compulsorily use BertEmbedding for generating its corresponding word vectors of the tokens or I can train my own word2vec model to generate my word embedding while using BertTokenizer?
Pardon me if this question doesn't make any sense.

Generally speaking, the power of BERT for applications like NER is that the authors (of whichever implementation you use) performed a large-scale pretraining effort to create the embeddings. You can then “fine-tune” those for your specific task using far less computation, but the rub is that you need to use the same tokenization scheme (I.e. the BERT Tokenizer) in order to have your input “fit” the existing embeddings. Intuitively, tokenization is mapping a word in your text to an index number. If the embedding was trained thinking that word number 42 is “cat” then things won’t work well if you tokenize differently and provide a 43 instead when “cat” pops up in your text.
Unless you’re training on a sparse language that hasn’t been well-represented by one of the public embeddings, the above is almost certainly your wisest approach. If, however you really want to train the BERT architecture on new embeddings, then you can technically use any embedding scheme you like.
The BERT Tokenizer uses subwords along with a few specific administrative tokens. If you were going to explore further, a byte pair encoder might be useful, especially if the language starts to beer away from eg English.

word2vec and BERT are completely different things. You don't need to use BERT Tokenizer for training word2vec model. But, if you want to go ahead. Here's a link which can help you.

Sorry, but I didn't ask that. My question was if I want to use BertTokenizer for a particular NLP task, say NER then is it mandatory to use BertEmbedding to generate the word embedding or I can train my own embeddings and use it along with BertTokenizer for that particular task (NER).

It is only mandatory if you are using BERT to create the embeddings. That's what I wrote in the answer also. You first tokenize then give it to BERT for generating embeddings.

Oh! thank you. Can you suggest to me any link or article for generating word embedding from BERT.

https://mccormickml.com/2019/05/14/BERT-word-embeddings-tutorial/#1-loading-pre-trained-bert


text:
"Porpoising" in latter stages of validation loss and MSE charts in Keras
Performing a prediction of a continuous y target using Keras, the simple structure of the code revolves around;
model = Sequential()
model.add(Dense(200, input_dim=15, activation= "relu"))
model.add(Dense(750, activation= "relu"))
model.add(Dense(500, activation= "relu"))
model.add(Dense(750, activation= "relu"))
model.add(Dense(500, activation= "relu"))
model.add(Dense(200, activation= "relu"))
model.add(Dense(100, activation= "relu"))
model.add(Dense(50, activation= "relu"))
model.add(Dense(1))

model.compile(loss= 'mse' , optimizer='adam', metrics=['mse','mae'])
history=model.fit(X_train, y_train, batch_size=50,  epochs=150,
                  verbose=1, validation_split=0.2)

This has resulted in the following metric chart;

What might be causing these, and how to eliminate (or greatly reduce) them?
UPDATE: Just reduced the learning rate to 0.0001 per Neil Slater's suggestion, and the loss curve may have had the spikes reduced, though the scale of the graph has changed. The training loss has increased from 0.00007 to 0.00037, the validation loss from 0.0014 to 0.002, and the prediction error increased from 0.037 to 0.046.

I then changed epsilon from it's value of 1e-07 to 0.1 and increased the epochs from 150 to 500. The validation loss increased to 0.0082 and the prediction error increased to 0.093, with the corresponding model loss shown below.

While not an overall improvement at either step, this did remove the spikes as I requested, hence Neil's advice gives me additional considerations to explore and measure within the Adam optimizer (along with other optimizers), so I consider this to have been an important learning experience. One such exploration uncovered this more detailed explanation of optimizers than I had been exposed to before, as well as this 3D visualization of loss topologies and the effect differing optimizers and parameters have on finding the optimal minima (keep a sharp eye on the options being chosen in the upper right corner).

What might be causing these, and how to eliminate (or greatly reduce) them?

It is difficult to be sure just from the graph, but I note you are using the Adam optimiser. It shares with a few other optimisers (most notably RMSProp) that it divides current gradients by a rolling mean of recent gradients to set step sizes. This can cause some minor instability when gradients get close to zero for a long while before growing again. This might happen at a saddle point where only some fraction of the network parameters are critical to results for a few iterations before hitting some other direction of slope where changing the "quiet" parameters becomes important again. This is more likely to occur as loss values become small, and close to perfect convergence.
There are a couple of hyperparameters in Adam that may reduce the effect:

Reduce learning rate. The default learning rate in Adam is often set to 0.001, but you will find a lot of researchers will reduce that to magnitudes around 0.0001 or 0.00001

Increase epsilon. This is effectively the minimum rolling average gradient. The default is 1e-7 but it sometimes needs to be increased significantly, it depends on the loss surface. The official documentation suggests that it may even be useful to increase it up to 1.0


text:
How do we express $q_\pi(s,a)$ as a function of $p(s',r|s,a)$ and $v_\pi(s)$?
The task (exercise 3.13 in the RL book by Sutton and Barto) is to express $q_\pi(s,a)$ as a function of $p(s',r|s,a)$ and $v_\pi(s)$.
$q_\pi(s,a)$ is the action-value function, that states how good it is to be at some state $s$ in the Markov Decision Process (MDP), if at that state, we choose an action $a$, and after that action, the policy $\pi(s,a)$ determines future actions.
Say that we are at some state $s$, and we choose an action $a$. The probability of landing at some other state $s'$ is determined by $p(s',r|s,a)$. Each new state $s'$ then has a state-value function that determines how good is it to be at $s'$ if all future actions are given by the policy $\pi(s',a)$, therefore:
$$q_\pi(s,a) = \sum_{s' \in S} p(s',r|s,a) v_\pi(s')$$
Is this correct?

Not quite. You are missing the reward at time step $t+1$.
The definition you are looking for is (leaving out the $\pi$ subscripts for ease of notation)
$$q(s,a) = \mathbb{E}[R_{t+1} + \gamma v(s') | S_t=s,A_t=a] = \sum_{r,s'}(r +\gamma v(s'))p(s',r|s,a)\;.$$
Because $q(s,a)$ relates to expected returns at time $t$, and returns are defined as $G_t = \sum_{b = 0}^\infty \gamma ^b R_{t+b+1}$, thus $R_{t+1}$ is also a random variable at time $t$ that we need to take expectation with respect to, not just the state that we transition into.


text:
Which topics about/in OpenCog could be researched in a Ph.D. thesis
In this interview with Lex Fridman and Ben Goertzel, at 2:23:48, Lex asks about possibilities for young people in the domain of AGI research. Ben Goertzel then answers that there are various possibilities we can find on the OpenCog framework, including Ph.D. theses.
I was wondering if anyone here knows what exactly he meant when he said we can find Ph.D. theses there? (He said about them at 2:25:18)
(I am considering doing a Ph.D. in AI, so I am interested in finding interesting topics for research)

Ask your potential PhD advisor.

I would also formulate this question so that you say that you're looking for people that can really answer this question (i.e. know OpenCog and have e.g. advised PhD students in the past).


text:
Policy and Discount Factor
This question is similar to this question, however it has a different question.
I'm learning MDP's and I'd like to know if I'm doing these exercises correctly:
Consider the following MDP:

Suppose a behavioural scientist was doing an experiment where they gave rewards to an animal. Suppose $X=5$ (e.g., 5 food pellets at that location). It turns out that, after repeatedly exploring the grid, the animal seems to prefer going up to the rewards of $+2$.
Question 1: In this setting, prove that no scalar discount $\gamma\in[0,1]$ exists for which the optimal policy is to go to $+2$.
Question 2: Consider a Monte Carlo return $$G_t=R_{t+1}+f(R_{t+1}+f(R_{t+2}+f(...))).$$
Standard discounting can be seen as applying a linear transformation $f(x) = \gamma x$, by multiplying the remaining return after each step by a factor $\gamma$. Consider the following alternative where instead of multiplying with a factor $\gamma$, we raise the value to power: $f(x)=x^{\gamma}$. Does this mathematical model better explain
the observed behaviour, in the sense that a $γ$ exists for which the optimal policy
goes to $+2$? If so, give such a value for $γ$. If not, prove why not.
My answer to question 1: For the optimal policy to go to $2$, we need the return for going to $+2$ to be greater than both the return of going to $+1$ and $+5$, i.e., mathematically
\begin{align}
2\gamma > \gamma^25 \cap 2\gamma>1 \\
\frac{2}{5} > \gamma \cap \gamma > \frac{1}{2}
\end{align}
Since $(\frac{1}{2},\infty) \cap (-\infty, \frac{2}{5}) = \emptyset$, this means that there is no such $\gamma$ for which the optimal policy is $+2$.
Answer to question 2:
Again the return of $+2$ should be both greater than $+1$ and $+5$:
\begin{align}
2^{\gamma} > (5^{\gamma})^{\gamma} \cap 2^{\gamma}>1 \\
\gamma \ln 2 > \gamma^2 \ln 5 \cap \gamma > 0 \\
\frac{\ln 2}{\ln 5} > \gamma \cap \gamma > 0 \\
0.43 > \gamma \cap \gamma > 0
\end{align}
Hence for $0< \gamma < 0.43$, the optimal policy will be to go to $+2$. Is this correct?

Why are people voting to close this as opinion-based? So, now mathematics is an opinion?! What the...!

@nbro The 3 questions look very similar so I was confused thinking they are duplicates

@ArayKarjauv Ha, ok, don't worry then! ;)

Both look correct


text:
What's the likelihood in Bayesian Neural Networks?
I'm trying to understand the concept behind BNN.
Their are based on the Bayes Theorem:
$$p(w \mid \text{data}) = \frac{p(\text{data} \mid w)*p(w)}{p(\text{data})}$$
which boils down to
$$\text{posterior} = \frac{\text{likelihood} * \text{prior}}{\text{evidence}}.$$
I understand that if we assume a Gaussian distribution for the model, the likelihood function comprises a product (or sum if we use log) of each data point inserted into the Gaussian pdf. The parameters which we can change are $\mu$ and $\sigma^2$. We want to increase the likelihood because higher values of the Gaussian pdf means higher probability.
How do things work when using a neural network? I assume that the likelihood function looks s.th. like inserting each data point inside the calculation (weighted sums) of the neural network. But does the neural network need a softmax layer at the end so that we can interpret the outputs as probabilities/likelihoods? Or do we measure likelihood by applying some error measurement like cross-entropy or squared-loss?

The likelihood depends on the task that you are solving, so this is similar to traditional neural networks (in fact, even these neural networks have a probabilistic/Bayesian interpretation!).

For binary classification, you should probably use a Bernoulli, which, in practice, corresponds to using a sigmoid with a binary cross-entropy (you can show that the minimization of the cross-entropy is equivalent to the maximization of Bernoulli p.m.f.)

If it's a multi-class classification problem, you should use a categorical distribution, which corresponds to a softmax with a categorical cross-entropy; see e.g. this implementation

If it's a regression problem, the likelihood could be a Gaussian (which is equivalent to using the MSE: you can also show this).

In the case of (mean-field) variational BNNs (VBNNs) (note that not all neural networks denoted as BNNs are VBNNs, but here I will only focus on VBNNs), rather than directly performing Bayesian inference (i.e. applying the Bayes theorem directly), you will perform approximate inference and, more specifically, you cast the inference problem as an equivalent optimization problem, where you typically optimize the loss function known as the evidence lower bound (ELBO), which is composed of two terms

the (log-)likelihood of the parameters (so the Bernoulli/categorical/Gaussian)
the KL divergence (the regularization part)

Theoretically, given that I am not a statistician, I cannot tell you right now why we can have a Bernoulli likelihood and a Gaussian prior (which is typically the case and, more specifically, in the case of this paper, they assume the weights to be independent, which is kind of a strong assumption but simplifies the computations, so this leads to a factorized multi-variate Gaussian over the weights), but this is what I had seen in practice.

Does this mean that if I have a bayesian neural network with sigmoid with a binary cross-entropy (which in fact is similar to bernoulli) we could use a prior that is conjugate to the likelihood (i.e. bernoulli) and thus avoid to calculate the evidence? If I understood correctly, your examples are comparisons, aren't they? So I don't have to explicitly define a Bernoulli distribution, but the use of sigmoid with a binary cross-entropy is comparable to an experiment where we assume the data is Bernoulli distributed?

@MichaChrist I don't know the answer to your first question, but, typically, in BNNs we don't calculate the evidence anyway because it's intractable. To answer your second question, I think the answer is "yes", but I am not fully about the accurateness of that statement.


text:
Why is the denominator ignored in the Bayes' rule?
The naïve Bayes' generative algorithm is often represented by the following formula:
$$\text{argmax}_{y} p(y|x) = \text{argmax}_y \frac{p(x|y)p(y)}{p(x)} \approx \text{argmax}_y p(x|y)p(y)$$
Why do we have $p(x)=1$ which allows the approximation $\text{argmax}_y \frac{p(x|y)p(y)}{p(x)} \approx \text{argmax}_y p(x|y)p(y)$?

They have eliminated it because in comparing probability for best outcome, it would just introduce additional division and the divisor p(x) is same for all candidates. For example, if I tell you to compare the largest of the following numbers: 3/2, 5/2, 1/2, you will without thinking pick 5/2 since the divisors are same and 5 is greatest of all.

The answer from @kiner_shah in the comments has solved it:

They have eliminated it because in comparing probability for best outcome, it would just introduce additional division and the divisor p(x) is same for all candidates. For example, if I tell you to compare the largest of the following numbers: 3/2, 5/2, 1/2, you will without thinking pick 5/2 since the divisors are same and 5 is greatest of all.

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


text:
How can rewards and loss calculation be extended to multiple agents in a vanilla policy gradient RL setting?
Say I have a simple multi-agent reinforcement learning problem using vanilla policy gradient methods (i.e. REINFORCE) that is currently running with one network per agent. If I can say that each of my agents:

are all of the same class
have ~equivalent environmental contexts (on average)
have no privileged state relative to other agents
performs updates equally to all other agents
DO use LSTMs (but store and reset memory states separately)
DO receive rewards for individual actions based on their individual states

...is it possible to use one network for all agents so as to minimize training time? And if so, how do I combine rewards and generate losses? For instance, if I calculate loss as the -logprob * reward (in the REINFORCE case), could I simply sum or average this over all agents and then backprop accordingly?

Yes, this can be done and is widely applied in recent literature on multi-agent RL, at least with the collaborative setting where agents are optimizing a shared reward. This is also known as parameter sharing between agents. Note that, even if the agents share the parameters in their policy networks, you can still get different behavior if the agents get different inputs, e.g., perceive different observations, or have different LSTM states.
In terms of the loss function, no changes are required compared to the case where each agent has its own network with private parameters, as long as you make sure the network with shared parameters correctly processes the individual inputs of each agent.
A concrete example is mentioned here - see Appendix C. They also use the trick of appending a one-hot encoding of the agent index with the observation to enable learning of policies that differ based on agent identity. Or, if you prefer to see an implementation of the idea in code, check out how agents are defined in this repository.

very helpful answer. I am however skeptical that "no change" is required. If I calc loss for each agent and backpropagate individually, the network is no longer the same after the first weight update (and so the second agent's backprop is now on a different set of weights). I think for there to be no change it would require that the agents take actions and update sequentially, but this would not be valid if they moved in parallel, right?

That's a good point, this is true at least for the case of cooperative agents that are optimizing a shared reward - this is also the setting covered by the resources I linked. I've clarified this point. I am not quite sure about the competitive setting where each agent has its own reward function - perhaps parameter sharing generally is not terribly appropriate in such a setting (why would one tell competitors what policy one is using?).

In my case the agents are "cooperative" in that they share a team reward, but they have individual rewards related to their individual movement that helps them learn the behavior of the more complex team reward swiftly. I believe in such a case I should be able to backprop all at once either by averaging or summing and can find that out empirically.

Adding for relevance of any others reading later, I honestly just averaged the losses and it worked fine. In fact it reduced some of the variance in learning as one might intuitively expect.


text:
Do text compression tests qualify winRar or 7zip as intelligent?
I read this paper Text Compression as a Test for Artificial Intelligence, Mahoney, 1999.
So far I understood the following:
Text Compression tests can be used as an alternative to Turing Tests for intelligence.
The Bits per character score obtained from compression of a standard benchmark corpus, can be used as a quantitative measure for intelligence
My questions:

Is my understanding of the topic correct?
Does this mean that applications like 7zip/WinRar are intelligent?
How are the ways a human compresses information (as in form of summary) and ways a computer compresses (using Huffman coding or something) are compatible? How can we compare that?

The paper suggests an alternative test to the famous Turing test, which tests a machine's ability to exhibit intelligent behavior equivalent to, or indistinguishable from, that of a human.
In this test, if winRar or 7zip will compress a file similarly to how a human would compress a file (how does a human compress a file?!), then, yes, those programs will pass the test and will be considered intelligent.

... thus compression ratio on a standard benchmark corpus could be used as an objective and quantitative alternative test for AI (Mahoney, 1999).

How does the paper think that the way a human compresses some information (in form of summary or something) and the way a computer program does (through Huffman coding or frequency tables) are compatible?

I have no idea.  I think that your question is valid and the paper does not answer it.

Matt Mahoney is one of the organizers of the Prize for Compressing Human Knowledge (Hutter prize), with Jim Bowery and Marcus Hutter. The prize is awarded to progress in compressing 1GB of Wikipedia text, so let us try to work out an example from it.
We read in the Wikipedia that Marcus Hutter was born "April 14, 1967". From our prior knowledge of the world (or reading the Wikipedia!), we know there are $12$ months per year, up to $31$ days per month and we are in $2022$ now, luckily close to $2048$. Therefore, we can safely use $4$ bits for the month ($2^4>12$), $5$ for the day ($2^5>31$) and $11$ for the year ($2^{11}>2022$), totalling $20$ bits for a lossless compression of a birth date (CE).
The original string "April 14, 1967" is $14$ characters long, so $112$ bits assuming $8$ bits/character.
Thus some understanding of this tiny bit of information gets a $\frac{112}{20}$ compression factor, about $5.6$. Maybe the comparison makes little sense here, but $5.6$ is similar to the initial $5.46$ compression factor by Matt Mahoney. Of course there are a lot of much more complex information structures in the Wikipedia. Besides, the month length can go up and down some characters, so this sample value is far from a constant for all dates.
Anyway, hopefully this simple example shows some relationship between text compression and understanding.


text:
Is it likely that a sentient AI experience synesthesia?
The reason I ask this question is because we humans tend to compartmentalize our sensory inputs, except in some individuals that experience synesthesia.  If an Artificial Intelligence Entity (AIE) can correlate all sensory input (as a bunch of tensors), wouldn't that be the ultimate form of synesthesia?
An AIE geometry / color synesthesia might lead to an explanation of how Joan Miro colorized his doodles.


text:
Bayesian Perceptron: Why to marginalize over neuron's output instead of it's weights?
I found a very interesting paper on the internet that tries to apply Bayesian inference with a gradient-free online-learning approach: Bayesian Perceptron: Towards fully Bayesian Neural Networks.
I would love to understand this work, but unfortunately I am reaching my limits with my Bayesian knowledge. Let us assume that we have the weights $\mathcal{w}$ of our model and observed the data $\mathcal{D}$. Using the Bayes rule, we obtain the posterior according to $$p(\mathcal{w}|D)=\frac{p(D|\mathcal{w})p(\mathcal{w})}{p(D)}$$.
In words: we update our prior belief over our weights by multiplying the prior with the likelihood and divide everything by the evidence. In order to calculate the true posterior, we would need to calculate the evidence by marginalizing over (intergrating out) our unknown parameters. This gives the integral $$p(D) = \int p(D|\mathbf{w})p(\mathbf{w})dw$$.
So far so good. Now I refer to the paper mentioned above. Here, the approach is presented exemplarily on a neuron whose weighted sum is called $a$, which is then given to the activation function $f(.)$. Moreover it is assumed that $\mathbf{w}\sim N (\mu_w, \mathbf{C}_w)$. Because of the linearity it can be exploited that also $\mathbf{a}\sim N (\mu_a, \mathbf{C}_a)$.
What I am confused about now is formula (14), which seems to show the compute the true posterior:
$$p(w) = \int p(a, w|D_i)da = \int p(w|a, D_i)p(a|D_i)da$$
Why is $a$ integrated out here and not $w$? We want a distribution over $w$, don't we? But without marginalization over $w$ there is still uncertainty inside $w$
Glad about any help and food for thought;)

We want a distribution over $w$, don't we?

Yes. You want to obtain a distribution over the parameters, which models the uncertainty about the parameters. This distribution over the parameters can induce a probability distribution over the possible functions consistent with your data.

Why is $a$ integrated out here and not $w$?

This is just the definition of marginalization.
For simplicity, consider 2 discrete random variables $X$ and $Y$, which can take values $x_i$ and $y_i$, respectively, and for which you can have (at least conceptually) a joint distribution $p_{(X, Y)}(x, y)$. Then the marginal probability that $X$ takes the value $x_i$ independently of any outcome of the r.v. $Y$ (and this is the intuition behind the marginal distribution!) is given by
$${\displaystyle p_{X}(x_{i})=\sum _{j}p(x_{i},y_{j})}, \tag{1}\label{1}$$
So, in the case of equation 14 of the paper, there's the assumption that you have $p(w, a)$. Then $p(w)$ is a marginal distribution over $w$ (the parameters or weights of the neural network), independently of the values of the activations. Of course, $w$ and $a$ can be dependent or correlated, and that's why you also have $p(w, a)$, i.e. the probability distribution that describes how these two r.v.s vary together, but what you want to know is the probability distribution over $w$ independently of $a$, so you "marginalize out" the possible values of $a$ (not $w$).
Remember that $p(x, y) = p(x \mid y) p(y) = p(y \mid x) p(x)$ (this is known as the chain rule of probability for two r.v.s, which leads to the Bayes' theorem), so you could write equation (\ref{1}) as follows
$${\displaystyle p_{X}(x_{i})=\sum _{j}p(x_{i},y_{j})} = \sum _{j}p(x_{i} \mid y_{j}) p(y_j), \tag{2}\label{2}$$
In the case of real-valued r.v.s, you will have an integral rather than a summation, but the idea is roughly the same.

But without marginalization over $w$ there is still uncertainty inside $w$.

What we want to know is $p(w)$, i.e. a distribution over $w$, which models the uncertainty about the possible values that $w$ can take. So, once you know $p(w)$, depending on its shape, we will have more or less uncertainty about the possible values of $w$. For example, let's say $p(w)$ is a Gaussian distribution. Then, depending on the variance, you will have more or less uncertainty about the possible values of $w$.
Your doubt seems to be that you thought that marginalization is a way to not have uncertainty, but that's not true. So, the goal in Bayesian machine/deep learning is not to be certain about the values of the parameters, but to model the uncertainty about the values of the parameters.

By the way, I didn't read that paper (maybe later if I have more time I will read it). This answer is based on my knowledge of probability theory. So, I am not really sure why the author is doing what is doing, but, conceptually, it's possible (I think). I would need to read the paper to fully answer the question in the title (which is slightly different than, although related to, the questions in the body).


text:
Using similarity score within lstm embedding for attention based mechanism
Yesterday, I found this fascinating paper about predicting various clinical conditions using an attention based LSTM. I don't have any practical experience with attention mechanism or transformers, which might be the reason why I struggle to understand why this approach work. Well, let me first try to summarize what the authors accomplished

As a first step, the use some sort of model to predict the future course of some important clinical variables. Their outcome is denoted by $X_0...X_t$. As a second step, these features (no timeseries data!) are passed into a transformer like architecture:

as an embedding step, the predicted clinical variables along with some static ones are passed to an LSTM that computes several hidden states: $H_0...H_t$
the attention step receives  $h_0...h_t$. For computing the contribution of each hidden state, the author states that each hidden state $h_i$ is passed to a function that computes the similarity between $h_i$ and $h_t$, that is the last hidden state of the lstm. From each resulting score $s_i$, a weight is computed with the softmax function $$w_i = \frac{exp(s_i)}{\sum_{j=0}^texp(s_j)}$$. The context vector cv is then calculated by computing the weighted sum of hidden states.
the decoder receives the context vector concatenated with $h_t$ and computes the output using two dense layers.

What I don't understand are two things:

Is it legit to use a lstm as embedding, while the input is no time series data but independent features?
In the presented approach, the weight of an hidden state $h_i$ depends on the similarity to the output of the lstm, i.e. $h_t$. But isn't an attention-based architecture used precisely to let every input variable contribute equally to the output, and to combat lstm's problem of struggling with long dependencies? With long inputs, i guess that $h_0$ tends to be likely to have larger differences from $h_t$ than, e.g. $h_{t-1}$ simply because it is more in the past. If this is true, $h_t$ automatically would receive a smaller weight.

Are my thoughts correct or have I missed something?


text:
What is the difference between the definition of "accuracy" in machine learning and federated learning?
What is the difference between the definition of "accuracy" in machine learning and federated learning?
In particular, how is the accuracy calculated in the following paper:

Cai, Lingshuang, et al. "Dynamic Sample Selection for Federated Learning with Heterogeneous Data in Fog Computing." ICC 2020-2020 IEEE International Conference on Communications (ICC). IEEE, 2020.

Could you please at least quote the parts of the paper that define the "accuracy" in federated learning or simply in that paper/context? If you're asking this question, it's because you think that accuracy in FL is defined differently than in ML, so it would be a good idea to explain why that is the case.

There isn't much to go on here. I did my best and posted an answer, but, as I stated in the disclaimer at the end, it's totally possible that it's wrong.

The paper in question is called Dynamic Sample Selection for Federated Learning with Heterogeneous Data in Fog Computing, by L. Cai, D. Lin, J. Zhang, and S. Yu. As the title suggests, the paper focuses on a machine learning methodology called federated learning.

Downloading the paper in question and doing a search for all occurrences of the word 'accuracy', I get 6 results. Going through these 6 results, I don't see anything that details the methodology used to assess 'accuracy'; the authors seem to assume that the author already knows how 'accuracy' is being measured. However, it seems to me that this in itself might tell us something: if the paper is exploring the federated learning methodology, and if the authors do not detail the methodology used to assess 'accuracy', and instead write as if the reader is assumed to know how 'accuracy' is being measured, then it is likely that the methodology used to assess 'accuracy' is that which is typically used in federated learning, including the earlier and more fundamental papers on federated learning, which the authors are likely (and reasonably) assuming that readers of their paper are already familiar with and have already studied. Furthermore, it seems to me that, if we want to maximise the probability that the ('other' federated learning) paper is using the same methodology for 'accuracy' as the authors (of this paper), then, rather than searching through papers that the authors haven't referenced, we should search one of the papers that they have.
Given what I said above, of the 6 occurrences of the word 'accuracy' in the paper, the second one, in section I. Introduction, seems to me to be the most promising:

With the growing use of internet devices, federated learning becomes increasingly popular in machine learning, which is typically to train models using decentralized data residing on end devices. The learning task does not use the data required for the aggregation model training to perform centralized calculations, but rather distributes the computation of machine learning to the distributed computing of participation parties’ databases. It can solve the “data island” problem in the loT, and can ensure the data privacy of devices. Federated learning is a viable and emerging framework which pushes AI frontiers to the network edge and trains machine learning models for fog computing [17]. It provides several benefits for the edge big data processing, including energy efficiency, privacy protection, and communication cost. However, the data is distributed across millions of devices in a highly uneven manner 2, 3–4, [9]. In addition, these devices have higher latency, lower throughput connections, and can only be used intermittently for training. McMahan et al. 2 proposed a Federated Averaging Algorithm based on the optimization of synchronized stochastic gradient descent (SGD), which averaged the gradients updates by all users (or random parts) as the update parameters of the central model. It can effectively reduce communication rounds compared with SGD. Moreover, some performance optimization methods like structured updates and sketched updates aimed to improve communication efficiency and test accuracy in federated learning [9].

(Emphasis mine.)
Reference 9 is for the paper Federated Learning: Strategies for Improving Communication Efficiency by J. Konečný, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon. Downloading the paper in question and doing a search for all occurrences of the word 'accuracy', I get 13 results. Going through these 13 results, the only one that seems relevant is from section 4. Experiments, under 4.2 LSTM Next-Word Prediction on Reddit Data:

We constructed the dataset for simulating Federated Learning based on the data containing publicly available posts/comments on Reddit (Google BigQuery), as described by Al-Rfou et al. (2016). Critically for our purposes, each post in the database is keyed by an author, so we can group the data by these keys, making the assumption of one client device per author. Some authors have a very large number of posts, but in each round of FedAvg we process at most 32 000 tokens per user. We omit authors with fewer than 1600 tokens, since there is constant overhead per client in the simulation, and users with little data don’t contribute much to training. This leaves a dataset of 763 430 users, with an average of 24 791 tokens per user. For evaluation, we use a relatively small test set of 75 122 tokens formed from random held-out posts.

Based on this data, we train a LSTM next word prediction model. The model is trained to predict the next word given the current word and a state vector passed from the previous time step. The model works as follows: word $s_t$ is mapped to an embedding vector $e_t \in \mathbb{R}^{96}$, by looking up the word in a dictionary of 10 017 words (tokens). $e_t$ is then composed with the state emitted by the model in the previous time step $s_{t1} \in \mathbb{R}^{256}$ to emit a new state vector $s_t$ and an “output embedding” $o_t \in \mathbf{R}^{96}$. The output embedding is scored against the embedding of each item in the vocabulary via inner product, before being normalized via softmax to compute a probability distribution over the vocabulary. Like other standard language models, we treat every input sequence as beginning with an implicit “BOS” (beginning of sequence) token and ending with an implicit “EOS” (end of sequence) token. Unlike standard LSTM language models, our model uses the same learned embedding for both the embedding and softmax layers. This reduces the size of the model by about 40% for a small decrease in model quality, an advantageous tradeoff for mobile applications. Another change from many standard LSTM RNN approaches is that we train these models to restrict the word embeddings to have a fixed L2 norm of 1.0, a modification found to improve convergence time. In total the model has 1.35M parameters.
In order to reduce the size of the update, we sketch all the model variables except some small variables (such as biases) which consume less than 0.01% of memory. We evaluate using AccuracyTop1, the probability that the word to which the model assigns highest probability is correct. We always count it as a mistake if the true next word is not in the dictionary, even if the model predicts ‘unknown’.

In Figure 4, we run the Federated Averaging algorithm on Reddit data, with various parameters that specify the sketching. In every iteration, we randomly sample 50 users that compute update based on the data available locally, sketch it, and all the updates are averaged. Experiments with sampling 10, 20, and 100 clients in each round provided similar conclusions as the following.

And later in the paper we have the following:

Note the following:

We evaluate using AccuracyTop1, the probability that the word to which the model assigns highest probability is correct.

So it seems that AccuracyTop1, whatever that is, is how 'accuracy' is being calculated. Googling "AccuracyTop1", we get this Stackoverflow question, and this answer to the question seems to explain how it works.

Disclaimer: This is all beyond my current knowledge and understanding, and I came to these conclusions purely through critical thinking and investigative research. It's totally possible that everything in my answer is nonsense, so feel free to correct me (or use my answer to find the correct answer).


text:
Getting started with training local LLM using python
As I'm completely new to this field, I find it hard to get started given the requirements I have. I'm a bit overwhelmed by all the models and options that are available. Even though it wasn't difficult to run an LLM locally:
$> brew install llm
$> llm -m gpt4all-13b-snoozy-q4_0  "Tell me a joke"

despite being very nice, it is not what I'm looking for. I want to train a model with my own data. Also, I want to build a website around it, so it means I can access the LLM with APIs.
So, as you can see I have some requirements. What would be a great place to start reading? A good tutorial to get started would be very much appreciated!

Depending on how much you want to understand about transformers, it always helps knowing the math first and to really understand how transformers work. So, to answer your question, what is a place to start reading:
As a good start I would suggest you read the paper "Attention is all you need" alongside the Annotated Transformer tutorial, which is a good “annotated” version of the paper in the form of a line-by-line implementation. Furthermore Andrej Karpathy provides a very helpful and understandable tutorial on LLMs and on how to build GPT from scratch, check out his website for more information.


text:
How LSTM really decide what to forget and not?
Currently, I am learning about LSTM, and I understand the intuition behind it, such as how forget gate works (sigmoid function yields a value between 0 and 1; if it is 0 it "completely" forgets, if it is 1 "it remembers everything"). What I don't understand is how this process unfolds. I mean, is it because of embeddings, as in, we store and keep them, thus deciding what to forget based on them?
A clear explanation would be helpful.

LSTMs use gates (forget, input, and output gates) and memory cells to control the flow of information through the network over time. As you've mentioned, these gates and memory cells allow the newtork to keep or discard information from previous time steps. In more detail, the forget gate uses the current input and previous hidden state to compute a value between 0 and 1 that represents the proportion of information from the previous cell state to forget. This gate, together with the input gate and the cell state update, enables the LSTM to selectively remember or forget information over time. As you pointed out, it's simply a sigmoid function that outputs values between 0 (forget completely) and 1 (remember everything).
Although the forget gate directly influences the forgetting process in an LSTM, it uses information from the current input and previous hidden state to decide how much of the previous cell state to retain or discard. So no, the the forget gate doesn't "decide forgetting" based on embeddings or so.
However, keep in mind that each gate has its own set of learnable parameters, which are trained during the learning process through backpropagation, aiming to minimise the cost function. Based on these weights, the forget gate can determine how much of the past information to forget, and these weights are adjusted during training to improve the model's performance on the given task.


text:
What is the reason we loop over epochs when training a neural network?
After reading through this thread and some other resources online, I still do not understand the role of epochs in training a neural network. I understand that one epoch is one iteration through the entire data set. But I don't understand what happens when we finish one epoch and start the second, i.e., what is happening such that the error is reduced after each epoch?
Assuming we have an outer loop over epochs, and an inner loop for the gradient descent iteration. What happens is the following, at least to my understanding:
For the first epoch, we take some random initial parameters and perform, say, 1000 gradient descent steps until we have found a local minima where the loss is minimised. So we have landed in a local minima, but it could be a bad one and we want to find a better one, preferably even the global minima. However, this is what I was thinking about:
The only way we can escape a bad local minima is to start a new gradient descent search with different initial parameters, but it seems like starting a new epoch is not just taking different parameters and repeating the process. According to the loss plotted over epochs, the loss is decreasing after each iteration, so it seems like the parameters are not chosen randomly, instead it looks like there is some knowledge used from the previous epoch. First, I assumed that a new epoch just means starting a new search over the loss landscape, this time with another set of random initial values, such that we end up in a different local minima. However, it is not guaranteed that this local minima is a better one, so we could also land in a worse local minima.
But if I look at graphs where the loss is plotted over epochs, it almost always decreases quite smoothly with each epoch, indicating that every epoch does indeed lead to a better minima. This is where I get confused. How is this possible? What is happening at the start of a new epoch? In order to decrease the error, we must have knowledge from the previous iteration, which means that we do not just simply start with a different random set of initial parameters. So, how does a new epoch iteration contribute to a better result? What is happening that the loss is decreasing without ever rising due to worse local minima?
------------ EDIT ------------
I want to add this simple example:
consider a simple linear network, no activation function. We have 2 inputs, each multiplied by a weight to generate a scalar output, i.e. the first step would look like:
x1[0]*w1 + x2[1]*w2 = out

where x1[0] contains the initial value and x2 is a different, known value. We want to find the weights w1 and w2 which minimise the loss between the output and the ground truth. In this case, I will work with one batch only, which contains the 2 inputs. The goal is to approximate a function linearly, given a known initial value. Then, I would run the training loop as follows
...
net = Net(2,1)
criterion = nn.MSELoss()
optimizer = optim.SGD(net.parameters(),lr=0.01)

for m in range(1,11):
    inputs = torch.Tensor(x[m-1], x[m]])
    for iteration in range(5000):
        net.zero_grad()
        out = net(inputs)
        loss = criterion(out, truth)
        loss.backward()
        optimizer.step()

This is just as snapshot of the loop, but basically the idea here is to find the appropriate weights for each point m of the function I want to approximate, by repeating the gradient descent search until we have found the local minima, and then proceed to the next point m+1 and so on. Using this example, how and why would a third loop over epochs decrease the error?

I am not expert on optimization, but I can share with you my knowledge of the topic.
I think that the source of your confusion is that you assumed that, after the first epoch, we have reached a local minimum. This is not necessarily true, although we might be on our way to get there, so that's why we usually have more than one epoch, and this should also explain why the loss decreases over epochs.
Moreover, as you correctly realised, we don't start the next epoch with new random weights. We start it with the weights that we found in the previous epoch.
Lastly, we might train the neural network with mini-batch (stochastic) gradient descent, which means that we split the original training dataset into $M = \lceil N / B \rceil$ batches, where $N$ is the size of the original dataset and $B$ is the batch size (typical numbers are 32 or 64). So, if you have, say, $N=10000$ and $B = 32$, then we have $M = 312$ mini-batches; so, for each epoch, you will perform 312 gradient steps, one for each mini-batch.
Now, although we use the same training data in different epochs, there are at least 2-3 reasons why the result of GD at the end of these epochs is different

at the beginning of each epoch, we may randomly shuffle the original training dataset before splitting it into mini-batches
even if that's not the case, we may feed the mini-batches in different order to the neural network
we start the epochs with different weights (e.g. in the first epoch, we start with random weights, in the second, we start with the weights found in the first epoch, and so on); think of a loss landscape with multiple minima (figure 1 here): the result of the optimization process depends on the starting point on this loss landscape

but why would I terminate the inner loop which is the optimisation loop when I have not found a stationary point? I do as many iterations as needed until the gradients vanish, so I know I am at a local min. And if the new epoch starts, with the parameters from the last epoch, well we are at the same point again, so how do we escape from there?
Or, is the loop over epochs what I call here the optimisation loop? For simplicity, lets assume I do not have multiple batches, but one batch with all the data

I guess the answer to your question is in the 1st and 2nd point (regarding GD) in my answer, i.e. at the beginning of every epoch, you may randomly shuffle the training dataset before splitting it into mini-batches or, alternatively, you may feed the model with another (probably random) order of the mini-batches (wrt the previous epoch).

You could do what you say, i.e. not have epochs, but, if after you've gone through all your training data (with the mini-batches), you shuffle the training data again, conceptually, it makes sense to highlight that point in time (i.e. the beginning of another epoch). Right now, I don't remember whether libraries like Keras or PyTorch do exactly this (i.e. whether they shuffle the training dataset at the beginning of every epoch before splitting). You may want to look at that ;)

In any case, this is just a conceptual distinction, i.e. even if you shuffle the training data at some point, you could not have the epochs and just have "GD updates". One library (which I know of) that does something similar, but in the context of reinforcement learning, is stable-baselines. It doesn't have episodes (which would be the rough equivalent of epochs in supervised learning) but just "training steps".

thank you for your thoughtful explanations! after going through the documentation of PyTorch and some introductory videos I figured out where the confusion comes from:
I approached the training of a neural network from an optimisation methods point of view. What you explained makes totally sense, however, I was picturing a very simple linear regression problem with 2 inputs and one output. For anyone having the same confusion, I will post an answer to my own question where I have more characters left:)

While writing out the answer, I figured out in the end that it does not actually answer my question, which is why I did not post it. So, let's keep it simple and do a thought experiment, I have edited my question to include this too


text:
Can RNNs get inputs and produce outputs similar to the inputs and outputs of FFNNs?
RNN and LSTM models have many architectures that can be modified. We can also compose their input and output data. However, in the examples that I found on the web, the inputs and outputs of RNNs/LSTMs are usually sequences.
Let's say we have a 3-column dataset:
data= np.array([[1.022 0.94  1.278]
                [2.096 1.404 2.035]
                [1.622 2.348 1.909]
                [1.678 1.638 1.742]
                [2.279 1.878 2.045]])

where the first two columns contain the inputs (features) and the third one contains the labels.
Usually, when modeling with feedforward neural networks (FFNNs), the input and output look like this:
Input:
x_input = np.vstack((data[:, 0], data[:, 1])).reshape(5, 2)

[[1.022 2.096]
 [1.622 1.678]
 [2.279 0.94 ]
 [1.404 2.348]
 [1.638 1.878]]

Output:
y_output = np.vstack((data[:, 2])).reshape(5, 1)

[[1.278]
 [2.035]
 [1.909]
 [1.742]
 [2.045]]

When modeling with RNN, the input and output are:
Input:
[[1.022 0.94  1.278]
 [2.096 1.404 2.035]
 [1.622 2.348 1.909]

Output (as a sequence):
 [1.678 1.638 1.742]
 [2.279 1.878 2.045]]

I would like to ask: Is it possible to model the input and output as an ANN model when modeling with RNN? Would it be correct?

Yes, it is possible. What you have shown in case of ANN is what happens in a regression model using NNs. What you have shown in case of RNN is what happens when you are doing sequence-to-sequence translation (like French to English).
If you want to get single values like in case of ANN, suppose you are doing regression, then, in the end, you will flatten the features aggregated by RNN (in case of Tensorflow, use Flatten layer and in case of PyTorch, you can directly do it). It should be then followed by a dense layer of 3 (in case of Tensorflow) or linear layer of 3 (in case of PyTorch), if I am talking about your example.
Since, you have shown values above 1, I presume you are doing some kind of regression. But, it would be good idea to normalize your outputs in case of regression, it makes the optimization easier.
If you want to classification then in the last layer, use Dense layer with softmax (in case of Tensorflow) and softmax followed by a linear layer (in case of PyTorch).

f(x, y, z) = ans, if you are trying to approximate the f here. Then, you don't need a RNN. A simple Dense layer network would work here. Or is there a concept of timestep? In that you will have to decide upon a window size. For flatten layer: https://www.tensorflow.org/api_docs/python/tf/keras/layers/Flatten. Look at the example in here. Basically, RNN would give 3D output while Dense layer requires 2D input, so you need to flatten the output of RNN.

The function is simpler f(x,y) = ans. No there is no timestep. Yes I can do that with simple ANN model. I tried to do that with LSTM It worked. But still I am not sure is it correct, since I am using for the task sequential model.

If your data is not sequential, you should not use LSTM or RNN. They will work but they will try to find dependencies between data that should not exist. I am not saying it is wrong. They can approximate the function. But, you are better off using 1D CNN or just Dense layers which are light on compute. In this case, it will better if you use Dense layer. Or just linear regression will work since you have a very small number of features.

I have example of this article: https://www.sciencedirect.com/science/article/pii/S0959652619325892. It shows interpolation, yes it is made also with time. What I am trying to do is only one epizode.

Ok I saw their network structure. If you trying to replicate that, then, just add flatten layer after lstm layers and then fc layer would work. They are concatenating Srw, Lat and Long data and then, feeding to the lstm layers.

Yes, both papers are doing the same thing. Just try it out.


text:
Where does 0.2023 for normalization on cifar10 come from?
i'm studying a resnet50 tutorial, which contains the following piece of code
def create_dataset_cifar10(dataset_dir, usage, resize, batch_size, workers):

    data_set = ds.Cifar10Dataset(dataset_dir=dataset_dir,
                                 usage=usage,
                                 num_parallel_workers=workers,
                                 shuffle=True)

    trans = []
    if usage == "train":
        trans += [
            vision.RandomCrop((32, 32), (4, 4, 4, 4)),
            vision.RandomHorizontalFlip(prob=0.5)
        ]

    trans += [
        vision.Resize(resize),
        vision.Rescale(1.0 / 255.0, 0.0),
        vision.Normalize([0.4914, 0.4822, 0.4465], [0.2023, 0.1994, 0.2010]),
        vision.HWC2CHW()
    ]
    ...

I'm aware that normalization is an important step of data pre-processing. I'd just like to know where do the values such as 0.2023 come from.
Some friends guessed the values referred to the means and standard deviations of the dataset. The following code is to verify the assumption.
(train_images, train_labels), (test_images, test_labels) = datasets.cifar10.load_data()
train_images, test_images = train_images / 255.0, test_images / 255.0
all_images = np.vstack((test_images, train_images))

reshaped_images = np.copy(all_images)
reshaped_images = reshaped_images.reshape((3, 60000, 32, 32))
reshaped_images = reshaped_images.reshape((3, 60000 * 32 * 32))
print(np.mean(reshaped_images, axis=1))
print(np.std(reshaped_images, axis=1))

gives
[0.47562782 0.47245647 0.47361567]
[0.25186847 0.25178283 0.25087802]

while
reshaped_images = np.copy(train_images)
reshaped_images = reshaped_images.reshape((3, 50000, 32, 32))
reshaped_images = reshaped_images.reshape((3, 50000 * 32 * 32))
print(np.mean(reshaped_images, axis=1))
print(np.std(reshaped_images, axis=1))

gives
[0.47410759, 0.4726623 , 0.47331911]
[0.2520572 , 0.25201249, 0.25063239]

neither is consistent with 0.2023

These are the precalculated values over the train split of the CIFAR10 dataset.
See this link, for example. You can try calculating these values for yourself to see if they match up.

thank you. the discussion you linked doesn't give steps of how to get the values.

They should be the means and standard deviations over the RGB channels of images in the training dataset


text:
Is $(y_i - \hat y_i)x_i$, part of the formula for updating weights for perceptron, the gradient of some kind of loss function?
A post gives a formula for perceptron to update weights

I understand almost all the parts of it, except for the part $(y_i - \hat y_i)x_i$ where does it come from? Is it the gradient of some kind of loss function? If yes, what is the definition of the loss function?
The OP seems doesn't give the hypothesis, so that $\hat y_i = h(x_i)$
However, this hypothesis seems prevalent
\begin{align}
\hat{y} &= sign(\mathbf{w} \cdot \mathbf{x} + b) \tag{1}\\
&= sign({w}_{1}{x}_{1}+{w}_{2}{x}_{2} + ... + w_nx_n + b) \\
\end{align}
where
$$
sign(z) =
\begin{cases}
1, & z \ge 0 \\
-1, & z < 0
\end{cases}
$$
How do I get $(y_i - \hat y_i)x_i$ from function (1)

I'm only adding this comment because you asked, "Is it the gradient of some kind of loss function?"  The direct answer is "No... It is, in itself, a simple loss function."  I just want to make sure that you recognize that the author seems to be presenting a simplified approach and not what we tend to use in a deep learning neural network.  More typically we will be performing backpropagation with partial differentials to determine how the weights and biases are adjusted.  Andrew Ng has a very, very good video explaining this that simplifies the math significantly if you search around.

It depends on your hypothesis $h$. The author of the original article compares the dot product with a threshold:

So for a binary classification problem $h$ can be defined as follows:
$$
h  = \begin{cases}
      1 & \text{if $f>z$}\\
      0 & \text{otherwise}
    \end{cases}
$$
That is, $\hat y_i$ is your prediction and $\hat y_i = h(x_i)$, $y_i$ is a real label and $x_i$ is a sample.
Finally, you can update your weghts $w_n = w_n + \eta(y_i - \hat y_i)x_i$, where $n$ is a number of the weight and $i$ denotes a number of the label/sample pair.
Depending on how you define your hypothesis you will have a different optimization algorithm. Take a look at this answer for more details.

Thank you. How do I get $(y_i - \hat y_i)x_i$ from this hypothesis \begin{align}
\hat{y} &= sign(\mathbf{w} \cdot \mathbf{x} + b) \
&= sign({w}{1}{x}{1}+{w}{2}{x}{2} + ... + w_nx_n + b) \
\end{align}

sign extracts a sign of a number. According to the article, it is defined exactly as I described: $sign(\mathbf{w} \cdot \mathbf{x} + b) = \begin{cases}
1 & \text{if $\mathbf{w} \cdot \mathbf{x} + b>0$}\
0 & \text{otherwise}
\end{cases}$

Your reference's training algo is called error correction rule or simply perceptron 0-1 rule which doesn't have the usual mean squared error (MSE) or cross entropy (CE) loss function associated with LMS/delta training rules leveraging various forms of gradient descent (GD) methods because its activation function is the non-differentiable Heaviside sign function breaking any GD applicability via chain rule to update each weight. Yet instead it could be approximately viewed as having MSE loss function optimized with stochastic gradient descent (SGD) method iterating over every training sample to update each weight incrementally following your referenced perceptron rule.
This can be intuited from simply replacing your sign activation function with a very similarly shaped differentiable function such as sigmoid, then your concerned 0-1 training rule can be derived just as the usual delta rule reflected in the Widrow-Hoff SGD version algo or the popular MLP backpropagation's SGD version algo to update any weight parameter, and better yet in your case, the derivative of activation function is approximately 1 since the activation function is assumed to be very like the sign function as intuited above.
Of course this is just some intuition, even for linearly separable dataset we cannot assure your concerned rule would converge at all. Fortunately there was Perceptron convergence theorem proved by Rosenblatt et al to affirm such convergence in the cases data is linearly separable. Even in non-separable cases there is no way for a single perceptron to converge, however, we still have Perceptron cycling theorem to give some upper bound estimate for the weight vector norm.


text:
Where does this variation of the importance sampling weight come from?
I have seeing a variation in importance sampling (IS) in Prioritized Experience Replay (PER) in some implementations regarding the original paper approach stated as (in section 3.4):
$$
w_{i}=\left(\frac{1}{N} \cdot \frac{1}{P(i)}\right)^{\beta}
$$
For something like this:
$$
w_{i}=\left(\frac{\min (P(i))}{P(i)}\right)^{\beta}
$$
Does anyone know where it comes from? A reference that explains the reason for that new formula and improvements obtained?
My intuition guides me to some conclusions, not necessarily correct, using this new formula:

In the beginning, supposing that the PER stills have empty positions, $\min(P(i)) \sim 0$, not giving too much weight for samples. But it grows substantially once the capacity is achieved as well as when the error becomes low (plus the incrementing Beta)

A code on github that applies this: link


text:
Learning rate and rewards in Deep Reinforcement Learning
In environments with sparse and (sometimes) binary rewards such as Taxi Cab, Mountain Car and Frozen Lake, where agents rarely encounter positive outcomes, I've observed that the gradient descent's learning rate is typically higher than in environments with dense reward functions. This makes sense because when a positive outcome is finally achieved, it is crucial to make significant updates to the policy. Conversely, finer adjustments are preferable to refine the policy in more intricate tasks. However, I haven't found any research papers addressing this observation. Are my thoughts accurate, and is there any literature that supports them?

Could you provide examples of RL agents used for sparse reward environments ?

I added them in the question.

I think that you should use quite different approaches when training on environments with sparse rewards compared to training on environments with dense rewards. It is not just the learning rate.
With dense rewards you can make progress even with partial trajectories. Because you get some reward signal, you can update the weights of the model after some steps (even at every step if you want to). In general, training on dense rewards is much easier and that is why most of the times people try to design a dense reward function for their environment.
With sparse rewards you cannot really make progress with partial trajectories. You need a full rollout that has reached a terminal state, so that you can propagate the reward signal from that terminal state. Algorithms like DQN, and PPO that use partial trajectories (n-step return) will not really work on an environment with a sparse reward func. You could try Monte-Carlo Policy Gradient, which works on full trajectories, but this algo is quite ineffective and I wouldn't recommend it.
Most of the times when you have a sparse reward function, your environment is actually fully observable (think Go, Chess, Rubik's cube). In the case of a fully-observable environment people tend to use some kind of a policy-guided tree-search algorithm, instead of model-free algorithms. So you would create full rollouts until a terminal state is reached and then update the weights of the policy. See for example AlphaGo and Rubik's cube.
Regarding your question about any research on this topic:
I think that you are looking at this the wrong way. It is not about "Here are some RL algos, lets see how to tweak them so that they work on this and that environment"... It is about "I have this problem, let's see what solution I can use to solve it".

If the problem is fully-observable, then you shouldn't be looking at model-free algorithms. There are other much more appropriate solutions, like tree-search, value iteration, dynamic programming, etc.
If the problem is partially-observable, then try to design a good dense reward function. If you manage to do that, then model-free RL (PPO, DQN, etc.) is a good fit.
If the problem is partially-observable and you cannot design a dense reward function, then you could either try imitation learning, which is quite similar to supervised learning from data (I wouldn't really call this RL), or you could try learning from human feedback, which again involves learning from data, but you are actually learning the reward func instead of the policy.

I'm quite familiar with all those techniques to handle environments with dense or sparse rewards. The previous answer raise the idea of "common sense" that we should use higher learning rates for problems with sparse rewards, but why and when this would work? I'm looking for studies to support it, if there's any.

I think that your learning rate depends mostly on the neural net architecture that you are using, whether u have normalization layers, the optimizer that you are using (adam, sgd, etc.). Regarding rewards, in order to stabilize your training, you would usually scale/clip your rewards, and you would also normalize your returns. No need to adjust learning rate depending on sparsity/density of rewards.

I guess that the more intricate the task, the bigger the network should be to accommodate the knowledge required. However, since it is hard to find rewards in environments with sparse ones, it would make sense to "shake" things a bit whenever you get them. Usually, I see higher learning rates for environments involving grid worlds, for instance.

If you don't find any rewards, then you shouldn't propagate anything because your model will learn to predict only 0s (already mentioned in the other answer). You should learn only from trajects that contain a reward. There's nothing to "shake up", you should just throw away anything that doesn't contain a reward. Since you have very few trajects that contain rewards, you get to make very few updates. Naturally this would mean that you should use a higher learning rate, so that you could learn things with fewer updates. However, this is unstable, that is why people use small learning rates.

Grid worlds are considered baby environments in RL and are only used for teaching purposes. You see higher learning rates in this tasks because the state space is really small and everything can be learned easily. If the model has more parameters than the size of the state space then this actually reduces down to a using a table method. If you want to do somewhat of a fair comparison, then take the LunarLander env and modify the reward space so that you get 1 when the spacecraft lands and 0 otherwise (or sth similar). Try to see if model-free RL can solve this task and what LR you need

If you have sparse binary reward, most of the rewards are $0$, so if you are using DQN, the network quickly learns to always predict $0$ (and the gradient would be 0 since there is no error), and in case of Actor critic methods, same happens when you do $G\ln(p(a|s))$... so there it not much to observe, is the expected behavior

Yes, but I'm looking for a more formal definition, perhaps a paper diving into theory or empirical results to support it.

@HenDoNR to support what?... usually you don't publish a paper that "dives" in something that aligns with the expectation


text:
AlphaGo Zero: does $Q(s_t, a)$ dominate $U(s_t, a)$ in difficult game states?
AlphaGo Zero
AlphaGo Zero uses a Monte-Carlo Tree Search where the selection phase is governed by $\operatorname*{argmax}\limits_a\left( Q(s_t, a) + U(s_t, a) \right)$, where:

the exploitation parameter is $Q(s_t, a) = \displaystyle \frac{\displaystyle \sum_{v_i \in (s_t, a)} v_i}{N(s_t, a)}$ (i.e. the mean of the values $v_i$ of all simulations that passes through edge $(s_t, a)$)
the exploration parameter is $U(s_t, a) = c_{puct} P(s_t,a) \frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ (i.e. the prior probability $P(s_t, a)$, weighted by the constant $c_{puct}$, the number of simulations that passes through $(s_t, a)$, as well as the number of simulations that passes through  $s_t$).

The prior probability $P(s_t, a)$ and simulation value $v_i$ are both outputted by the deep neural network $f_{\theta}(s_t)$:

This neural network takes as an input the raw board representation s of the position and its history, and outputs both move probabilities and a value, (p, v) = fθ(s). The vector of move probabilities p represents the probability of selecting each move a (including pass), pa = Pr(a| s). The value v is a scalar evaluation, estimating the probability of the current player winning from position s.

My confusion
My confusion is that $P(s_t, a)$ and $v_i$ are probabilities normalized to different distributions, resulting in $v_i$ being about 80x larger than $P(s_t,a)$ on average.
The neural network outputs $(p, v)$, where $p$ is a probability vector given $s_t$, normalized over all possible actions in that turn. $p_a = P(s_t, a)$ is the probability of choosing action $a$ given state $s_t$. A game of Go has about 250 moves per turn, so on average each move has probability $\frac{1}{250}$, i.e. $\mathbb{E}\left[ P(s_t, a) \right] = \frac{1}{250}$
On the other hand, $v$ is the probability of winning given state $s_t$, normalized over all possible end-game conditions (win/tie/lose). For simplicity sake, let us assume $\mathbb{E} \left[ v_i \right] \ge \frac{1}{3}$, where the game is played randomly and each outcome is equally likely.
This means that the expected value of $v_i$ is at least 80x larger than the expected value of $P(s_t, a)$. The consequence of this is that $Q(s_t, a)$ is at least 80x larger than $U(s_t, a)$ on average.
If the above is true, then the selection stage will be dominated by the $Q(s_t, a)$ term, so AlphaGo Zero should tend to avoid edges with no simulations in them (edges where  $Q(s_t, a) = 0$) unless all existing $Q(s_t, a)$ terms are extremely small ($< \frac{1}{250}$), or the MCTS has so much simulations in them that the $\frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ term in $U(s_t, a)$ evens out the magnitudes of the two terms. The latter is not likely to happen since I believe AlphaGo Zero only uses $1,600$ simluations per move, so $\sqrt{\sum_b N(s_t, b)}$ caps out at $40$.
Selecting only viable moves
Ideally, MCTS shouldn't select every possible move to explore. It should only select viable moves given state $s_t$, and ignore all the bad moves. Let $m_t$ is the number of viable moves for state $s_t$, and let $P(s_t, a)$ = 0 for all moves $a$ that are not viable. Also, let's assume the MCTS never selects a move that is not viable.
Then the previous section is partly alleviated, because now $\mathbb{E} \left[ P(s_t, a) \right] = \frac{1}{m_t}$. As a result, $Q(s_T, a)$ should only be $\frac{m_t}{3}$ times larger than $U(s_t, a)$ on average. Assuming $m_t \le 6$, then there shouldn't be too much of an issue
However, this means that AlphaGo Zero works ideally only when the number of viable moves is small. In a game state $s_t$ where there are many viable moves ($>30$) (e.g. a difficult turn with many possible choices), the selection phase of the MCTS will deteriorate as described in the previous section.
Questions
I guess my questions are:

Is my understanding correct, or have I made mistake(s) somewhere?
Does $Q(s_t, a)$ usually dominate $U(s_t, a)$ by this much in practice when the game state has many viable moves? Is the selection phase usually dominated by $Q(s_t, a)$ during these game states?
Does the fact that $Q(s_t, a)$ and $U(s_t, a)$ being in such different orders of magnitude (when the game state has many viable moves) affect the quality of the MCTS algorithm, or is MCTS robust to this effect and still produces high quality policies?
How common is it for a game state to have many viable moves (>30) in Go?

Too many questions in a single post and this is a big post. I suggest that you simplify this post as much as possible (i.e. to contain only the necessary info), and ask each question in its separate post.

I don't think you've necessarily made any real mistakes in your calculations or anything like that, that all seems accurate. I can't really confidently answer your questions about "Does X usually happen?" or "How common is X?", would have to experiment to make sure of that. I think we can also confidently immediately answer the question about whether MCTS is robust and can still produce high quality policies with "yes", since we've seen state-of-the-art, superhuman results in a bunch of games using these techniques.
But I do think there's a few important details that may change your perception:

MCTS does not compare $Q(s, a)$ values to $U(s, a)$ values in its selection phase. It compares $Q(s, a) + U(s, a)$ expressions of actions $a$, to $Q(s, b) + U(s, b)$ expressions for different actions $b$. So, the difference in magnitudes $Q(s, a) - U(s, a)$ is not nearly as important as the difference in magnitude $Q(s, a) - Q(s, b) + U(s, a) - U(s, b)$!

For any single given state $s$, it is certainly not the case that we expect the different $Q$-values to be have a nice average like $0.5$ or anything like that. There will likely be plenty of states $s$ where we're already in such a strong position that we can afford to make a mistake or two and still expect to win; all the $Q$ values here will be close to $1.0$. There will also be many states where we're in such a terrible position that we expect to lose no matter what; all the $Q$ values here will be close to $0.0$. And then there will of course be states that a network is not sure about, which will have $Q$ values somewhere in between. I suspect that "in between" won't often be a nice mix of all sorts of different values though. If it's something like $0.7$, and there's higher values that attract more attention, during training the MCTS + network will likely become very interested in learning more about that state, and very quickly learn whether that should really just be a $1.0$ or whether it should be lowered. For this reason, I imagine that in unsure states, values will have a tendency to hover around $0.5$.

MCTS will only let the $Q(s, a)$ term dominate the selection phase for as long as it believes that this is actually likely to lead to a win. If this is correct and indeed leads to a win, well, that's great, no need to explore anything else! During the tree search, if further investigation of this action leads the MCTS to believe that it actually is a loss, the $Q$ value will drop (ideally towards $0$), and then it will automatically stop being a dominant term. If the tree search fails to adjust for this in time, and we end up wandering down this losing path anyway, we'll get a value signal of $0$ at the end and update our value network and in the future we'll know better than to repeat this mistake.


text:
Transformers: how to get the output (keys and values) of the encoder?
I was reading the paper Attention Is All You Need.
It seems like the last step of the encoder is a LayerNorm(relu(WX + B) + X), i.e. an add + normalization. This should result in a $n$ x $d^{model}$ matrix, where $n$ is the length of the input to the encoder.
How do we convert this $n$ x $d^{model}$ matrix into the keys $K$ and values $V$ that are fed into the decoder's encoder-decoder attention step?
Note that, if $h$ is the number of attention heads in the model, the dimensions of $K$ and $V$ should both be $n$ x $\frac{d^{model}}{h}$. For $h=8$, this means we need a $n$ x $\frac{d^{model}}{4}$ matrix.
Do we simply add an extra linear layer that learns a $d^{model}$ x $\frac{d^{model}}{4}$ weight matrix?
Or do we use the output of the final Add & Norm layer, and simply use the first $\frac{d^{model}}{4}$ columns of the matrix and discard the rest?

I have read the OpenNMT source code (https://github.com/OpenNMT/OpenNMT-py/blob/cd29c1dbfb35f4a2701ff52a1bf4e5bdcf02802e/onmt/modules/multi_headed_attn.py).
It seems like an extra linear layer learns the weights $W^{key}$ and $W^{value}$ (plus biases), so to get the output (keys and values), you multiply the output of the encoder's final add + norm layer by $W^{key}$ to get the keys, and by $W^{value}$ to get the values.
Additionally, these weights and biases seem to be independent across each of the decoding layer. So you feed the same encoder output (add + norm layer output), but multiply by different $W^{key}$ and $W^{value}$ matrices and add by different biases for each of the decoding layer, resulting in different keys and values for each layer


text:
What is the cost function of a transformer?
The paper Attention Is All You Need describes the transformer architecture that has an encoder and a decoder.
However, I wasn't clear on what the cost function to minimize is for such an architecture.
Consider a translation task, for example, where give an English sentence $x_{english} = [x_0, x_1, x_2, \dots, x_m]$, the transformer decodes the sentence into a French sentence $x_{french}' = [x_0', x_1', \dots, x_n']$. Let's say the true label is $y_{french} = [y_0, y_1, \dots, y_p]$.
What is the object function of the transformer? Is it the MSE between $x_{french}'$ and $y_{french}$? And does it have any weight regularization terms?

I took a look at the Tensor2Tensor's source code implementation, and it seems like the loss function is the cross-entropy between the predicted probability matrix $\|\text{sentence length}\| \times \|\text{vocab}\|$ (right before taking the argmax to find the token to output), and the $\|\text{sentence length}\|$-length vector of token IDs as the true label.

Note that they reshape the out_logits variable there, in the line that you're linking us to, i.e. tf.reshape(out_logits, [-1, VOCAB_SIZE]), so the cross-entropy seems to be computed between two vectors and not a matrix and a vector (but I didn't really executed that code and tried to output the shape of those tensors/variables). It may be a good idea to do it, just to confirm the exact shape.

@nbro I just ran the code, and can confirm that is the case. out_logits originally has the shape (3, 7, 1, 1, 10), which is to (BATCH_SIZE, SENTENCE_LENGTH, ??, ??, VOCAB_SIZE). The ?? are bookkeeping dimensions because the tensor2tensor model expects a 5-D tensor, but are then immediately stripped out afterwards. Then, tf.reshape(out_logits, [-1, VOCAB_SIZE]) resizes out_logits to (21, 10), which is (BATCH_SIZE * SENTENCE_LENGTH, VOCAB_SIZE). Btw, for tf.reshape, seems like adding a -1 as a dimension makes it a flexible sized dimension, so it results in a 2D matrix rather than a 1D vector.