text:
How do transformers understand data and answer custom questions?
I recently heard of GPT-3 and I don't understand how the attention models and transformers encoders and decoders work. I heard that GPT-3 can make a website from a description and write perfectly factual essays. How can it understand our world using algorithms and then recreate human-like content? How can it learn to understand a description and program in HTML?

It can't "understand" anything. It just matches patterns to something it encountered in the training data.

Two years after the original question was made I feel it is time to provide an updated answer:

How can it understand our world using algorithms and then recreate
human-like content?

GPT-3, GPT-4 (transformers, Chat-GPTs and the likes) do not understand our world. They do provide answers based on any info available on the "training datasets" and on any additional "training dataset" used to "fine-tune" the model. Those answers recreate human-like content even if the models/algorithms do not understand nor have a representation of the world.

GPT-3 (and the likes) don't really have any understanding of the semantics nor pragmatics involved in the language. However, they are good at constructing text content similar to the contents created by a person (when the texts and the concepts are not too "complicated").

But how do the different layers and math formulas work to create this type of intelligence?

There are many questions regarding this issue on this  platform, though I wouldn't call it "intelligence". Attention is all you need....

So then what is "Attention". I simply want to understand the working principle of GPT-3

@DragonflyRobotics We don't have a great idea, we know the general principle of neural networks is to make something that can in principle do the computation, and then spend hundreds of thousands of dollars (in the worst case) renting GPUs to tweak it quadrillions of times until it performs well.

@DragonflyRobotics The attention unit is, AFAIK, the major contribution of the transformers paper. If you want to know what attention is then I suggest you focus your question around that.


text:
While fine-tuning a decoder only LLM like LLaMA on chat dataset, what kind of padding should one use?
While fine-tuning a decoder only LLM like LLaMA on chat dataset, what kind of padding should one use?
Many papers use Left Padding, but is right padding wrong since transformers gives the following warning if using right padding " A decoder-only architecture is being used, but right-padding was detected! For correct generation results, please set padding_side='left' when initializing the tokenizer."
The attention mask will anyways ignore the padding tokens.

Next time, please, put your question in the title. Thanks.

I'm concerned about this as well, and the generate() method in the transformers library explicitly suggests that decoder-only models should use the left padding method. Is there some correlation? I would also like to know the reason for this left padding.

I got an answer to this question, probably a correct explanation.
In decoder-only model architectures, the output of the model is a continuation of the model input.
For example, input: I love apple [pad] [pad]. The output of the model will contain the input and add additional output information.
For example, output: I love apple [pad] [pad],because it is delicious.
This would result in [pad] being stuck in the middle of the text. It is very bad for the model to process text. If we use left-padding, the output of this model will be
output : [pad] [pad] i love apple,because it is delicious.
Such complete semantic information is continuous.
ref:https://github.com/huggingface/transformers/issues/18388#issuecomment-1204369688

I don't think this a complete answer. We could simply take the output probabilities correponding to the input "apple" and overwrite the first pad token with the new token. I think the real answer is just that it's slightly more convenient not to have to worry about this by leftpadding everything

Decoder only text LLMs are autoregressive. Like any autoregressive function if you do not left pad there will be no prior token to your intial token for efficient gradient descent.
In most text generation models, the process of token generation is AutoRegressive, which means that the model generates one token at a time, conditioned on the previous tokens it has generated 2.
In the equation you provided, X = (A, b, c)  X = F(X(-1)), it seems like X is a vector of length 3, and F is a function that takes the previous value of X as input and returns the next value of X. This is a recursive definition of X, where the current value of X depends on the previous value of X. This is similar to the AutoRegressive process used in text generation models, where the current token depends on the previous tokens generated by the model.
MarvsAI

source: Stack Exchange

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

sort: votes


text:
Which search algorithm expands nodes closest to the goal?
I want to know which search algorithm among A* and Best-First Search and Greedy First Search expands nodes closest to the goal. I have three opinions about A* and Best-First Search and Greedy First Search. As far as I know, Best-First Search is a category of search algorithms that includes A* and Greedy First Search as special cases.
So, which one is the correct choice for this question, as all three are based on the heuristic function?

Update: A*, BFS and GFS are all informed search strategies meaning that they expand the nodes according to an evaluation function, $f(n) = g(n) + h(n)$, where $g(n)$ is the cost of the path from start node to current node $n$, and $h(n)$ is a heuristic function, which provides an estimate of the cheapest path to from current node $n$ to the goal node.

GFS expands the nodes using only the heuristic, so $f(n)=h(n)$, so it tries to expand the nodes that the heuristic tells to be closest to the goal. As a consequence GFS is neither complete nor optimal.

Considering BFS, if $f(n)=g(n)$ then the uniform cost search is recovered, which considers only the cost path $g$.
A* is an instantiation of BFS (thanks @nbro) which can achieve, under certain assumptions, completeness and optimality (if $g$ and $h$ are optimal, or at least $h$ is admissible never overestimating the cost.)

A* is in general more efficient than BFS and GFS because it employs a heuristic function that basically provides the remaining distance between the actual node and the goal node (indeed, it depends on how you implement it.) So, in this way, A* tends to explore less nodes in general because it focuses more on the most important (nearest to the goal) ones.
For example, say you perform A* on a grid in which you can explore following 4 directions (up, down, left, and right). The heuristics would be the Manhattan distance telling the remaining distance from the actual position to the goal. So when this information is combined with the cost of the edge (or weight) it enables A* to be more efficient when exploring nodes.

A* is a BFS algorithm (note that this is not breadth-first search), so I don't think that "A* is in general more efficient than BFS" makes a lot of sense. Moreover, the heuristic function does not provide the remaining distance between the "actual node" (which should have been the "current node") and the goal node. It merely provides an estimate of this distance. Note also that the heuristic function is not really fixed. You can have many heuristic functions. If these heuristic functions satisfy certain conditions, then A* is optimal.

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


text:
What's the architecture that allows the generation of new images based on input image in tools like Midjourney?
I understand that the high-level architecture of tools like Midjourney use diffusion models to generate images from text. What I don't understand is which type of network architecture allow the second step of their workflow - generating new, similar images conditioned on a selected input image. This post seems to mention ControlNet as a way to condition image output based on image input, but it seems like ControlNet would require additional training to yield useful results, so I don't see how that would work in a Midjourney-like workflow.
Any links to relevant publications or blog articles would help as well.

Midjourney (and DALL-E 2 I think) uses a concept vector (or "embedding") to condition its image outputs, which can be produced in at least two ways:

By summarising text input
By converting an image

The concept space is the same for these two processes, although the input stages of the analysis are different architectures (an RNN for text, a CNN for images). So the results of multiple text prompts and image prompts can be combined using a weighted mean, and this is how multi-prompts plus image weighting work. Everything goes into the same embedding vector that is used to condition the diffusion reversal functions.
The CLIP model by OpenAI is an example architecture which does this. It is trained with image and caption pairs to produce a pair of models which can convert either text or image inputs into a shared embedding or "concept space". Midjourney is likely using their own version of CLIP, perhaps trained on their own dataset, or something very similar - their models are proprietry though, so this is an educated guess.
Note this model is separate to the diffusion model, and helps produce inputs to it. When you start a generation with multiple image and text prompts:

Each image prompt is passed to the image encoder, and a mean of all the image output vectors taken
Each text sub-prompt is passed to the text encoder, and a mean of all the text output vectors taken
The mean image and mean text vectors are combined, weighted by the --iw parameter. This is done once, before the main image generation starts
The final combined vector is used to condition the steps in the diffusion denoising image generator

ControlNet is an entirely different way to influence the diffusion denoising function. Midjourney, as of version 5.2, does not have any equivalent.
The Midjourney base process also does not use img2img - which is another way to use an input image. This uses a partially-noised version of the image as a starting point, instead of pure noise. The Midjourney variations, zoom and pan features do use this kind of influence, so it appears the raw model does support the feature, but Midjourney service does not allow customers to control it in full, for instance by uploading their own images, because of potential for abuse.


text:
How are sentences numerically encoded before passing them to neural networks?
I'm trying to understand NLP, how sentences can be used as input output in neural network architecture. As we know ANN is only compatible with number data. That's mean the sentences must be convert to number, right?
Suppose I have this sentence
Hello world, the world is saying hello.

How it looks like when it converted to number?
I think it will looks like this...
1 2 3 2 4 5 1

Where:
hello = 1
world = 2
...

But what if there's typo? For example hello worlf

On a very basic level, you are absolutely correct about the encoding of the attached sentence. But, practically, when you have a set n number of documents to be encoded, things happen differently.

Let's say we have n=1000 independent sentences.

Now, doing it by hand is a little difficult, but let's say we have to do it. What you will start with is making a list of all the unique words there are and assigning each of them a number, let's call this our vocabulary. It might look like this

{
    'the': 1,
    'menace': 2,
    'shirt': 3,
     ...
}

Now each possible word has a separate id assigned, you will go back to each of the sentences and encode them based on the number you assigned to each word in the last step. Note that in this method you need to be completely neutral about misspelled words assigning them different numbers as you find them. Of course, you can choose to correct the spelling if you wish, but you already are analyzing 1000 lines, why add one more task? Each line will now look something like what you mentioned in your question.

You can use this encoded information in algorithms.

But, to have better results, as mentioned you will need to correct the misspelled words, right? What if instead of n=1000 it was n=1,000,000 or like some trained models out there, with n=4 Billion documents, you can't possibly think to correct the spellings by hand (manually) right?
So, researchers found more standardized methods. Essentially, we define a set of tokens, that might be a word like the, hell etc., or tokens (a sequence of letters) 1, a, b, c, blad, ght, etc. These tokens are designed based on multiple statistics the most important of which are length, and occurrence. Basically, if a word is too large it is taking space in the set, and if it is too rarely used, it can be broken into smaller tokens that might be a part of other words as well. The idea is to have tokens with similar frequency of occurrence when analyzed over a large corpus of data, but also include smaller tokens like a, b, etc. which can be used to account for new and previously unseen words. As you very correctly put it, computers understand numbers, and numbers can be anything as long as they make sense to computers.
These sets contain a vocabulary of tokens that can be used to encode any word. Here are some examples to help consolidate my points-

Revolution (correct spelling)
tokenized - ['rev', 'ol', 'u', 'tion']

Revoluton (incorrect spelling)
tokenized - ['rev', 'ol', 'u', 't', 'on']

Hi
tokenized - ['Hi']

and so on.
NOTE - The aforementioned tokens are only for illustration and might (probably will) differ from tokenizer to tokenizer.
So, now instead of defining our own tokenizers which need to be designed with multiple aspects and considerations, you can choose to use a standardized one already designed and available online. Some examples would be, NLTK's tokenizer, Spacy's tokenizer, Gensim, WordPeice (used for BERT) for your case.
Additionally, not having tokenizers has its own shortcomings, some of which are-

If you add independent words to the vocabulary, then the vocabulary quickly gets out of hand (consider that the English language has around 1 million words, not to mention other languages if you plan on training a translator). Great tokenizers have achieved good results with a token vocabulary of as small as 30,000 tokens.

As noted, the same words but wrong spellings hold space of their own and make the vocabulary unnecessarily longer. With standard tokens, you don't have to care about these misspelled words as they can be accounted for easily.

Vocabulary based on words will fail in case of new words, and so every time new information comes up, you will have to add a new element to the vocabulary. As was with misspelled words, new words can be accounted for with standard token-based vocabularies as well.

Hope this helps.


text:
Which algorithm do I need to use to calculate the error?
I am building a neural network for a AI whose goal is to learn to implement the XOR logical function.I have this code so far:
class Node:
  prevNodes = []
  b = 0.5;

def __init__(self,value,nextNode):
    self.value = value
    self.nextNode = nextNode
    self.nextNode.value += self.value * b
    self.nextNode.prevNodes.append(self)

def changeB(error):
    b +=error;

def printVal(self):
    print(self.value+"\n")

class Network:

def __init__(self,nodes):
    self.nodes = nodes

def calcOutput(self):
    finalNode = self.nodes
    while self.nodes.nextNode is not None:
        finalNode = self.nodes.nextNode
    return 1-pow(e,-(finalNode.value))

def digitize(val):
    if val<0.5:
        val = 0
    else:
        val = 1

def correctBiases():

def checkAnswer():

    if input("is this answer correct?") is not digitize(calcOutput()):

        correctBiases()

Now I am writing the correctBiases() function. Which algorithm do I need to use to calculate the error?

This is a summarized version of the explanation in Haykin 1994, section 4.3.  (Rumelhart et al 1986 being the original reference, but Haykin breaks it down nicely for beginners.)
$\underbrace{\Delta w_{ji}(n)}_\textrm{weight correction} = \underbrace{\eta}_\textrm{learning rate }\cdot \underbrace{\delta_i(n)}_\textrm{ local gradient }\cdot \underbrace{y_i(n)}_\textrm{ input signal of neuron j }$
$\delta_j(n) = \psi^{'}_j\left(v_j\left(n\right)\right)\, e_j(n)$
$e_j(n) = d_j(n) - y_j(n)$ is the error for output neuron $j$
$e_j(n) = \sum\limits_k \delta_k(n)\, w_{kj}(n)$ is the error for hidden neuron $j$.
$\psi$ is the activation function. $d$ is the correct value. $y$ is the predicted value. $w$ is the weight matrix.
Note that what you're calling the error in the question is more commonly the "weight correction". The error is just one part of that.

I havent taken a  Deep learning class at my university yet so my terms are layman terms.Thanks a lot btw!

Not a problem. I just wanted to avoid confusion since I've got an "error" term here that isn't what you meant by error.


text:
What is the difference between Machine Learning model, algorithm and hypothesis?
I'm fairly new to Machine Learning field and still to grasp the basics, so this question may seem very stupid, but what is the difference between Machine Learning model, algorithm and hypothesis?
Like the terms are interrelated, but how exactly are they different from each other? They are used interchangeably, so I don't really understand them.
If someone can help to explain these words in simplest terms it would be very helpful.

An algorithm is a sequence of instructions to tell the computer (or a human) what to do. The computer executes the algorithm and produces or not (may not halt) an output (e.g. prints a message). A Python program is an algorithm. Any program is an algorithm. So, think of an algorithm as a recipe that you use to cook/compute something.
A model can have different meanings in different contexts, but they are related. Here I provide more details. For example, in supervised learning, a model can refer to a parametrized function (so kind of a set of functions) or a function. A good model is a model that approximates well some target function (e.g. a function that differentiates between cats and dogs). You need to define good and well, which depends on the context in practice.
A hypothesis is roughly equivalent to the idea of a model. However, this term is used more in computational learning theory. Given your knowledge of ML, I'd ignore this term for now.
Models that run on computers are, by definition, algorithms or part of algorithms. However, it's not always clear why a model (like a neural network) is a sequence of instructions. In fact, in many cases, that's not clear at all. But it turns out that algorithms can compute functions and models approximate, compute or are functions. If you want to think of a model as an algorithm, the best example I know of is a decision tree model.


text:
Why is automatic differentiation still used, if today's computers can calculate symbolic derivatives quite fast?
Today's computers can calculate symbolic derivatives quite fast, why is automatic differentiation still used? For example, Mathematica can handle algebraic operations with arrays. Doesn't automatic differentiation cause significant overhead? Calculating the symbolic gradient of an MLP should not be too difficult, or am I wrong?

That depends on the point-of-view. If you have some function given as a string of its mathematical formula and the output is the fully inserted string of its derivative, then the chain rule $(u\circ v)'(x)=u'(v(x))v'(x)$ quasi duplicates the occurrence of $v$. This happens for each composition, so one can get an exponential growth in the string length from input to output.
If you keep common sub-expressions separate, then what you do is parsing the function into a computational graph and taking the derivative of it. But this is already in the territory of algorithmic/automatic differentiation. If you do not keep the derivatives inside the original nodes, but split off additional nodes, then the output graph will double to triple in size relative to the original graph. This is a very compact representation of the symbolic derivative. Such structures have long been used and sometimes also exposed in CAS systems like Maple.
The aim of AD is the fast evaluation of derivatives, so if evaluating in a point in a first sweep the node values and derivatives relative to the node input are computed, and each additional forward or backward sweep is just linear operations to compute tangents or gradients.

In a ANN the network itself represents the computational graph, matrix-vector multiplication nodes/layers have the matrix and the input vector as the required node derivatives, for the scalar values of the activation function the node derivative needs to be computed separately. As the gradient computation has only one backward pass for each input, they can be computed just when they are needed.
In short, backprop networks are already a part or an application of AD, there is not really a way to make this more efficient. In some cases (sparse graphs, multiple outputs,...) it can be useful to apply AD techniques to compress parts of the network, if the organizational overhead justifies the gains.


text:
Why will every action be sampled an infinite number of times?
I am reading the book Reinforcement Learning: An Introduction. Second edition (Richard S. Sutton and Andrew G. Barto). In the k-armed bandit problem using $\varepsilon$-greedy selection method, the authors say that

An advantage of these methods is that, in the limit as the number of steps increases,
every action will be sampled an infinite number of times, thus ensuring that all the $Q_t(a)$
converge to their respective $q_*(a)$.

May I ask why "every action will be sampled an infinite number of times" since at each time step $t$ (for limited time steps), we only select one action $A_t = a$?

Welcome to AI stack exchange. I'm not quite getting what your issue is, and why you are focused on the single action per time step? Can you explain what you understand by the phrase "in the limit as the number of steps increases" from the quote?

in the limit as the number of steps increases

Means for the value we are interested in (number of samples for action $a$, let's call that $N(a)$), then we want to find
$$\lim\limits_{t \to \infty} N(a)$$
$$ \approx \lim\limits_{t \to \infty} tp(a)$$
Where $p(a)$ is the probability of taking action $a$.
Provided $p(a)$ is not zero, the limit for this expression when $t$ tends to infinity also tends to infinity as it is (on average) a fraction of $t$. This also relies on the law of large numbers - the innaccuracy of the approximation becomes smaller relative to the total value as $t$ increases.
In an $\epsilon$-greedy policy, then this sets a lower bound for $p(a)$, and we can use that to set a lower bound of the expected value of $N(a)$ in the limit of $t \to \infty$. Provided you don't set $\epsilon = 0$, then this lower bound limit for $N(a) \approx \epsilon t$ still tends to $\infty$ along with $t$.

Thank you very much, I misunderstand this part: "in the limit as the number of steps increases". If it is mean time step $t \to \infty$ then everything is clear now.


text:
How does not learning far inputs make the RNN forget far inputs?
I am totally aware of the problem of the vanishing gradient. It usually occurs with vanilla RNN, where with a long sequence of data, the gradient will vanish or explode for far input sequence, and hence, the network will not learn from far inputs. This is fine, however, the side effect of this problem is making the RNN lose the ability to memorize long sequences (memorizing far inputs). I don't understand what is the relationship between not learning the far inputs and not memorizing the far inputs.
In other words, how does not learning far inputs make the RNN forget far inputs?

It is actually very simple, it is not about forgetting, but not learning at all means no memorization at all.
For long term dependencies, since the gradient is very small, what is learned is very little, so nothing was memorized either.


text:
What is the difference between these two versions of the Bellman equation?
The first version is the one I am most familiar with:
$$V_\pi(s) = \sum_{a}^{}\pi(a|s)  \sum_{s'}^{}T(s, a, s')[R(s, a, s') + \gamma V_\pi(s')]$$
where $T(s, a, s')$ represents the probability of transitioning from state $s$ to state $s'$ given action $a$.
And where $R(s, a, s')$ represents the expected value of the reward from transitioning from state $s$ to state $s'$ given action a.
In another textbook, I saw this version of the equation:
$$V_\pi(s) = \sum_{a}^{}\pi(a|s)  \sum_{s',r}^{}p(s',r |s,a)[r + \gamma V_\pi(s')]$$
Is the second equation more general since it considers the probability of going to $s'$ AND getting a reward $r$?
Or are they somehow the same (if so, why)?
Or maybe they are the same under certain circumstances (like conditional independence of $s'$ and $r$)?

@RLControl The second edition of that book uses that second form, but the first edition doesn't (if I remember correctly).

The two are equivalent.
\begin{align}
V_\pi(s) &= \sum_{a}^{}\pi(a|s)  \sum_{s',r}^{}p(s',r |s,a)[r + \gamma V_\pi(s')]\\
&= \sum_{a}^{}\pi(a|s)  \sum_{s',r}^{}p(s'|s,a)p(r| s',a,s)[r + \gamma V_\pi(s')] \\
&= \sum_{a}^{}\pi(a|s)  \sum_{s'}^{}T(s',s,a)\sum_{r}p(r| s',a,s)[r + \gamma V_\pi(s')]\\
&= \sum_{a}^{}\pi(a|s)  \sum_{s'}^{}T(s',s,a)\left[\sum_{r}p(r| s',a,s)r + \gamma \sum_{r}p(r| s',a,s)V_\pi(s')] \right]\\
&= \sum_{a}^{}\pi(a|s)  \sum_{s'}^{}T(s',s,a)\left[R(s',a,s) + \gamma V_\pi(s')] \right]\\
\end{align}
We first split $p(s',r|s,a) = p(s'|s,a)p(r|s',a,s)$ by law of conditional probability, and we note that $p(s'|s,a) = T(s',a,s)$ by definition. We split the sum to parts over $s'$ and $r$, and then split it further to separate the two terms taking the expectation over $r$ and $\gamma V_\pi(s')$. By definition, the first expectation equals $R(s',a,s)$. In the second expecation, $V_\pi$ is independent of $r$ so the probability sums to one and vanishes.

Just one note for people that get confused with the last part. If $k$ is a constant and we have $k \sum_{i=1}^N f(i)$, then this is equivalent to $k f(1) + k f(2) + \dots + k f(N) = k * (f(1) + f(2) + \dots + f(N))$. In this specific case, $p$ is a distribution. So, the sum of all $f(i)$ is equal to one, so we multiply $1$ times $k$, which in this case is $V_\pi(s')$.


text:
What is the meaning of $ (I - \gamma P^{\pi})^{-1} \left[\frac{\mu(a|s)}{\hat \pi_{\beta}(a|s)} \right](s, a)$?
In Theorem 3.1 of the conservative q-learning paper, what is the meaning of
$$ (I - \gamma P^{\pi})^{-1} \left[\frac{\mu(a|s)}{\hat \pi_{\beta}(a|s)} \right](s, a)$$?
I thought $(I - \gamma P^{\pi})^{-1}$ is to be interpreted as an operator on function space over state and action space, but it is unclear to me how it is being applied to a $\frac{\mu(a|s)}{\hat \pi_{\beta}(a|s)}$, which is a scalar.
Also, it is unclear what $(I - \gamma P^{\pi})^{-1} \frac{C_{r, T, \delta}R_{\max}}{1 - \gamma}$ means?

We have for $\gamma < 1$:
$$ (I-\gamma P^{\pi})^{-1}=I+\gamma P^{\pi} + \gamma^2 (P^{\pi})^2 + \cdots $$
What they mean by $(I-\gamma P^{\pi})^{-1}\frac{\mu(a\mid s)}{\hat{\pi}_{\beta}(a\mid s)}(s,a) $ is the function from $\mathcal{S}\times\mathcal{A}\longrightarrow \mathbb{R}$, sending $(s,a)\mapsto (I-\gamma P^{\pi})^{-1}\frac{\mu(a\mid s)}{\hat{\pi}_{\beta}(a\mid s)}$.
Now, we have
$$P^{\pi}\frac{\mu(a\mid s)}{\hat{\pi}_{\beta}(a\mid s)}=\mathbb{E}_{s'\sim p(\cdot\mid s,a), a'\sim \pi(\cdot\mid s')}\left[ \frac{\mu(a'\mid s')}{\hat{\pi}_{\beta}(a'\mid s')} \right]. $$
Similarily,
$$(P^{\pi})^2\frac{\mu(a\mid s)}{\hat{\pi}_{\beta}(a\mid s)}=\mathbb{E}_{s'\sim p(\cdot\mid s,a), a'\sim \pi(\cdot\mid s'), s''\sim p(\cdot\mid s',a'), a''\sim \pi(\cdot\mid s'')}\left[ \frac{\mu(a''\mid s'')}{\hat{\pi}_{\beta}(a''\mid s'')} \right]. $$
Adding this together, we have
$$(I-\gamma P^{\pi})^{-1}\frac{\mu(a\mid s)}{\hat{\pi}_{\beta}(a\mid s)}(s,a)=\mathbb{E}_{\pi}\left[\sum_{t\geq 0} \gamma^t\frac{\mu(a_t\mid s_t)}{\hat{\pi}_{\beta}(a_t\mid s_t)}\bigg\rvert s_0=s, a_0=a \right]. $$
The last quantity is easier, as it does not depend on $(s,a)$, so:
$$(I-\gamma P^{\pi})^{-1}\frac{C_{r,T,\delta}R_{\max}}{1-\gamma}=\sum_{t\geq 0}\gamma^t\frac{C_{r,T,\delta}R_{\max}}{1-\gamma}=C_{r,T,\delta}R_{\max} $$

This makes a lot of sense, thanks @matorbi


text:
Why are neural networks used as reinforcement learning model value functions?
My understanding is that a value function in reinforcement learning returns a value that represents how "good" it is to be in a given state.
How does a network, such as the network in this example , represent how good it is to be in the given state?
Is the neural network value function the best method of achieving such a "goodness" value in an environment with many possible states and indefinite length?

There is a much simpler answer than the ones already given. The value function represents the expected (discounted) returns from the current state when following policy $\pi$, i.e:
$$v_\pi(s) = \mathbb{E}\left[\sum_{k=0}^\infty \gamma^k R_{t+k} | S_t = s\right]\;.$$
This is just a scalar value that we would like to predict given some input, i.e. the state. So, predicting this quantity can be thought of (loosely) as a regression task. In regression, we typically want to learn a function $\hat{f}$ which, when given some input $x$, can approximate well the output $y$ under the true (but unknown) function $f$, i.e. we want to learn $\hat{f}$ such that $\hat{f}(x) \approx f(x)$.
Now, supposing our state space is too large (e.g. infinite) to be enumerated in a lookup table, we need to parameterise our approximate value function. This can be done using any parametrisable function $\hat{v}_\pi(s; \textbf{w})$, where $\textbf{w}$ are the learnable parameters of the function, to approximate $v_\pi(s)$. We choose neural networks because they have been successful empirically at approximating the true value function.
To answer your question as to whether these are the best approximators for the value function, my answer would be currently yes, but there is a huge amount of research in the field of Reinforcement Learning and it is impossible to say whether or not they will remain state of the art.

Informally I would agree with your understanding of the value function.
To answer your questions, it seems explaining some motivation for parametric modeling/machine learning is necessary: In general if we are not in a tabular setting, we wish to take advantage of the nature of our (continuous) data by leveraging relationships between states and rewards. In other words, we may think that there exists some underlying pattern in the states that relates to how much reward we can attain. More formally, one may posit some sort of parametric model, which implicitly assumes there is some parameter vector $\theta_0$ s.t. $V(s)=\theta_0' s, \forall s \in S$. Or similarly for the Q value function.
This kind of assumption is similar to any linear regression model, or just any model that wants to take advantage of potential underlying patterns in the data to learn (like in any other machine learning problem). The choice of a neural network is motivated well by the amount of data available in certain domain areas and the recent advent of empirical success of neural nets.
With this setup, to more specifically answer your last two questions: the network represents this value because we model it to be that way as we model $y=\theta'x$ in linear regression. Is this the best method? So far, this is one of the best methods we have available provided we have enough data. The reason can be supported by empirical success seen in other applications, and mathematically by results like the universal approximation theorem (which states that any continuous function can be represented arbitrarily well by a NN), or other more modern results from high dimensional statistics.

I am not sure why this question was downvoted. I am trying to see where the big problem is.

The goodness of the state in the network is determined by the activation_fn. The primary role of the Activation Function is to transform the summed weighted input from the node into an output value to be fed to the next hidden layer or as output. That adds non-linearity to the neural network, without that learning would be impossible. It allows the model to create complex mappings between the network’s inputs and outputs.
The activation function used in hidden layers is typically chosen based on the type of neural network architecture. You need to match your activation function for your output layer based on the type of prediction problem that you are solving—specifically, the type of predicted variable.
Also see the update, halfway through this answer.
That can be set as follows:

Activation function descriptor.
Supported values are: "tanh", "relu", "swish" (or "silu"), "linear" (or None).
"fcnet_activation": "tanh",

With a linear transfer function the value would look like this:

Fig: Linear Activation Function - Equation: f(x) = x
It doesn’t help with the complexity or various parameters of usual data that is fed to the neural networks. All layers of the neural network will collapse into one if a linear activation function is used. No matter the number of layers in the neural network, the last layer will still be a linear function of the first layer. So, essentially, a linear activation function turns the neural network into just one layer.
The Nonlinear Activation Functions are the most used activation functions.

Sigmoid or Logistic Activation Function

The Sigmoid Function curve looks like a S-shape.

Fig: Sigmoid Function
The main reason why we use sigmoid function is because its valued between 0 to 1. It's used for models where we have to predict the probability as an output.
Since probability of anything exists only between the range of 0 and 1, the sigmoid is a useful function and is differentiable. That means, we can find the slope of the sigmoid curve at any two points.
The function is monotonic but the function’s derivative is not. The logistic sigmoid function can cause a neural network to get stuck at the training time.

Tanh or hyperbolic tangent Activation Function
The tanh is also like a logistic sigmoid but better. The range of the tanh function is from -1 to 1. tanh is also sigmoidal (s-shaped).

Fig: tanh v/s Logistic Sigmoid
The advantage is that the negative inputs will be mapped strongly negative and the zero inputs will be mapped near zero in the tanh graph.
The function is differentiable and monotonic, while its derivative is not monotonic.
The tanh function is mainly used for classification between two classes.
Both tanh and the logistic sigmoid activation functions are used in feed-forward nets.

ReLU (Rectified Linear Unit) Activation Function
The ReLU is the most used activation function in the world right now, since it's used in almost all the convolutional neural networks or deep learning.

Fig: ReLU v/s Logistic Sigmoid
The ReLU is half rectified (from bottom), f(z) is zero when z is less than zero and f(z) is equal to z when z is above or equal to zero, with a range of 0 to infinity.
The function and its derivative both are monotonic, but the issue is that all the negative values become zero immediately; which decreases the ability of the model to fit or train from the data properly.
That means any negative input given to the ReLU activation function turns the value into zero immediately in the graph, which in turns affects the resulting graph by not mapping the negative values appropriately.

Leaky ReLU
It's an attempt to solve the dying ReLU problem.

Fig: ReLU v/s Leaky ReLU
The leak helps to increase the range of the ReLU function. Usually, the value of $\LARGE{a}$ is 0.01 or so.
When a is not 0.01 then it is called Randomized ReLU.
The range of the Leaky ReLU is -infinity to infinity.
Both Leaky and Randomized ReLU functions are monotonic in nature, and their derivatives are also monotonic in nature.
What is a Good Activation Function?
A proper choice has to be made in choosing the activation function to improve the results in neural network computing. All activation functions must be monotonic, differentiable, and quickly converging with respect to the weights for optimization purposes.
Why derivative/differentiation is used ?
When updating the curve, to know in which direction and how much to change or update the curve depending upon the slope, we use differentiation.
It makes it easy for the model to generalize or adapt with variety of data and to differentiate between the output.

You can learn more about differentiation at these blogs: "Mathematics behind Machine Learning – The Core Concepts you Need to Know" and "Application of differentiations in neural networks".
An excellent resource for activation functions is: "Ultimate Guide to Activation Functions".

"Is the neural network value function the best method of achieving such a "goodness" value in an environment with many possible states and indefinite length?".

Yes, a properly trained neural network can not only answer what it was trained for but can also infer additional questions and provide correct answers from a relatively compact representation.
The optimization algorithm is what carries out the learning process in a neural network. There are many different optimization algorithms. They are different in terms of memory requirements, processing speed, and numerical precision
The loss index plays a vital role in the use of neural networks. It defines the task the neural network is required to do and provides a measure of the quality (goodness) of the representation it is required to learn. The choice of a suitable loss index depends on the application.
When setting a loss index, two different terms must be chosen: an error term and a regularization term.
$$\text{loss_index}=\text{error_term}+\text{regularization_term}$$
The error term is the most important term in the loss expression. It measures how the neural network fits the data set.
All those errors can be measured over different subsets of the data. In this regard, the training error refers to the error measured on the training samples, the selection error is measured on the selection samples, and the testing error is measured on the testing samples.
A solution is regular when small changes in the input variables led to small changes in the outputs. An approach for non-regular problems is to control the effective complexity of the neural network. We can achieve this by including a regularization term in the loss index.
Regularization terms usually measure the values of the parameters in the neural network. Adding that term to the error will cause the neural network to have smaller weights and biases, which will force its response to be smoother (with a greater goodness of fit).

"The learning problem is formulated as the minimization of a loss index, $\LARGE{f}$. It is a function that measures the performance of a neural network on a data set.

The loss index includes, in general, an error and a regularization terms. The error term evaluates how a neural network fits the data set. The regularization term prevents overfitting by controlling the model's complexity.

The loss function depends on the adaptative parameters (biases and synaptic weights) in the neural network. We can group them into a single n-dimensional weight vector $\LARGE{w}$.".

For further details see: "5 algorithms to train a neural network".

Thank you for posting an answer. I have taken the time to read your answer and the provided links at the bottom. I still fail to see how a network represents the "goodness" of a given state in reinforcement learning. In your answer you say that it is the activation_fn which determines the "goodness" of a state, but I don't see why that is. Can you explain why "the goodness of the state in the network is determined by the activation_fn"?

Goodness is not determined by the activation function, although activation functions certainly play a role on the neural network's output. The goodness is determined by a loss or objective function. This answer is too long and focus too much on the activation functions, which are not really the key to answer the question.

@nbro, you've mis-read the question and didn't read the code  The question is: "... the network in this example , represent how good ...", and the code for slimFC is called to use a linear function without an activation layer. It's not a different question than what they asked, don't edit away the question and downvote answers. Answer the question as asked. This is your 3rd action here.

@Rob I didn't misread the question. The question is, how can a neural network represent how good it's to be in a state? The other question is why are neural networks used as value functions in RL? You went on to explain things about activation functions, which are not very relevant to answer these questions. The user wrote "like this" and he didn't even mention activation functions anywhere. I don't think that the point was about the activation functions of the specific NN. I think the point was that it was unclear to them how a neural network can represent $v(s)$ or $q(s, a)$.

Sure, activation functions are a part of the explanation of why neural networks can approximate, compute or are functions, but your answer goes too much in detail of activation functions and I don't think that was the key. And your answer is simply wrong. The goodness of a state is not determined by the activation function alone, but it's what the neural network outputs. The goodness of state is a $v(s)$ and that's what a neural network can output.


text:
How do neural network topologies affect GPU/TPU acceleration?
I was thinking about different neural network topologies for some applications. However, I am not sure how this would affect the efficiency of hardware acceleration using GPU/TPU/some other chip.
If, instead of layers that would be fully connected, I have layers with neurons connected in some other way (some pairs of neurons connected, others not), how is this going to affect the hardware acceleration?
An example of this is the convolutional networks. However, there is still a clear pattern, which perhaps is exploited by the acceleration, which would mean that if there is no such pattern, the acceleration would not work as well?
Should this be a concern? If so, is there some rule of thumb for how the connectivity pattern is going to affect the efficiency of hardware acceleration?

The answer is going to depend on details - e.g. how sparse the connections are, whether they can be arranged meaningfully into layers etc. Also whether you have training data available in large batches. Do you have any specific use case or scenario that would narrow the scope down a little? Or are you looking for a broad but shallow answer?

I am interested in a broad but shallow answer. Or even better, to some place where I could read more.

Yes, it matters, and I think you have to manually decide how to divide it up, and hello pre-covid-19 question.

The topology of a neural network can have a significant impact on the performance of GPU and TPU acceleration.

The most important factor is the number of layers and the connectivity between them.

Simple topologies require less data movement and can be more easily parallelized. a shallower network with fewer layers will often be faster to train on a GPU or TPU than a deeper network with more layers. This is because each layer in a neural network must be fully connected to the previous and next layers, and a deep network will have many more connections than a shallow network.
Additionally, the activation function used for each layer can also impact performance. ReLU is a common activation function that is often used in networks that are accelerated by GPUs or TPUs.
GPU-based acceleration of CNN

GPU is widely used in neural network applications due to a large number of ALU units which helps in faster data processing (multiplication and summation operations in NN), and also the GPU caches, which help in data reuse.

The GPU is capable of merging multiple data access requests using the controllers, and it helps in massive parallel and pipelined processing.
GPU is a temporal architecture paradigm with a large number of ALUs, but the ALUs lack direct data communication, and they communicate using direct memory access.

GPU has around $3,000–5,000$ ALU But the Von Neumann bottleneck exists in GPU due to the access to registers and the shared memory for intermediate data storage in every ALU operation.

The GPU has specialized libraries for CNN acceleration like fbfft (Vasilache et al., 2015). While using a high working set, the shared memory cannot be used, and there is a need for global memory access in GPU, and this leads to more memory footprints and memory access.

TPU-based acceleration of CNN

TPU is a custom-made ASIC with a matrix processor which is specially designed for neural networks. it effectively handles the addition and multiplication in neural nets at a very high speed with very little power consumption.

The von Neumann bottleneck in CPU and GPU is overcome in TPU with the systolic array structure. TPU v2 single processor has 16-bit two 128 × 128 systolic arrays with 32,768 ALUs.

Systolic array in TPU helps in data reuse which makes the performance high and execution energy efficient in CNN.

The two-dimensional multiply unit helps in matrix multiplication faster compared to the one-dimensional multiply units in CPU and GPU.

In TPU, eight-bit integers are used in place of the 32-bit floating-point operations, and this makes the computations faster and memory efficient.

Unlike CPU and GPU TPU drops features that are not used in the neural network, which helps in saving energy.

CNN implementation in TPU will have both TPU and CPU usage in parallel to run the linear and non-linear elements in CNN.

In CNN the convolution and classification layer is executed in TPUsince it is a GEMM operation, and the Pooling and Flattening are executed in the CPU.

Here is the paper that analyzed CNN model performance for the three-image processing application in GPU/TPU platforms in Colab for various batch sizes. The analysis was done by varying the final feed-forward network and the hidden layers, and this gives an inference on how the performance is affected when the model structure changes

Fig(a): Training time for single and multiple convolutional layer networks.
In the paper, analysis was done using a single convolutional layer followed by all other layers for the mask detection application for binary class, and the training time was analyzed for GPU and TPU for both networks. The training time increases when the convolutional layers are removed because the number of nodes gets more, and thereby training time increases. The training time for Single layer convolution and multiple-layer Convolution for different batch sizes is shown in Fig(a).
The analysis clearly shows that the time decreases when the number of convolutions increases due to a reduction in the number of nodes. The training time is less for the multiple layers CNN compared to single-layer CNN and also with an increase in the batch size.

Fig(b): Execution time for multi and binary classes.
The overall training time for each of the three applications was in GPU and TPU for both binary, and multiple classifications were analyzed and shown in Fig(b).
From Fig(b), it is clear that compared to TPU, GPU has a low time for execution of the CNN. This occurs due to the bottleneck that occurs in TPU due to the in-between CPU access.

GPU: GPU performs well for small batches and gives better flexibility and easy programming. For small data, batch sizes GPU fits better due to the execution pattern in wraps and scheduling id easy on-stream multiprocessors. For large dataset and network models, GPU performs well by optimizing memory reuse. In fully connected neural networks, weight reuse is less, so as the model size increases, this leads to high memory traffic. In GPU, the memory bandwidth makes it practical for applications with memory requirements. Large neural networks work better on GPU compared to CPU due to the extra parallelism feature. For fully connected neural networks, GPU works better compared to CPU, but for large batch sizes, TPU performs well.

TPU: TPU performs well on CNN with large batches to give high throughput in training time using the systolic array structure. Large batches of data are needed for the full utilization of the matrix multiply units in the systolic array of TPU. In CNN, the speedup increases with batch size. For enormous batch sizes and complex CNN, TPU is the best because of the spatial reuse characteristics of CNNs. But in fully connected networks, the weight reuse is less, and so TPU is not preferred.

Different neural network topologies may require different amounts of resources (memory, computational power, etc.), which could affect the efficiency of hardware acceleration. There is no easy rule of thumb, however, as it depends on the specific architecture and implementation.


text:
Are my proofs that the Bellman operators are contractions correct?
Introduction
I'm studying Reinforcement Learning, and in order to increase my understanding I've been challenging myself by trying to write proofs that show that the right hand side of the Bellman equations and Bellman optimality equations for state-value and action-value functions are contraction operators. The fact that the Bellman operators are contractions is of great importance, since this proves that the Bellman equations have unique fixed points that can be solved for iteratively, due to the Banach fixed-point theorem.
Below are my attempts at the proofs, my questions are:

Are the proofs correct?
Any feedback on what can be improved (I'm very inexperienced in writing proofs and would like to get better)?

I will assume some knowledge about finite Markov Decision Processes (MDPs), please let me know if you want me to elaborate.
Bellman equations
Let $\mathcal{S}$ denote the finite set of all states, $\mathcal{R} \subset \mathbb{R}$ the finite set of all rewards, and $\mathcal{A}(s)$ the finite set of all available actions $a$ in state $s$. Let $r_\pi(s)$ denote the expected immediate reward and $p_\pi(s^\prime | s)$ the probability of transitioning to state $s^\prime$ when following policy $\pi$ from state $s$. Let $\gamma \in (0, 1)$ denote the discount rate for future rewards. The Bellman equation for the state-value function for policy $\pi$ can be defined as follows:
$$
\begin{aligned}
v_{\pi}(s) &= \mathbb{E}_\pi \big[R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t = s \big] \\
&= \sum_{a \in \mathcal{A}(s)} \pi(a | s) \bigg[\sum_{r \in \mathcal{R}} p(r | s, a) r + \gamma \sum_{s^\prime \in \mathcal{S}} p(s^\prime | s, a) v_{\pi}(s^\prime) \bigg] \\
&= r_\pi(s) + \gamma \sum_{s^\prime \in \mathcal{S}} p_\pi(s^\prime | s) v_{\pi}(s^\prime)
\end{aligned} \tag 1
$$
for all $s \in \mathcal{S}$. Let $n = |\mathcal{S}|$, we can write the equation in matrix form:
$$
\begin{bmatrix}
v_\pi(1) \\
\vdots \\
v_\pi(n)
\end{bmatrix}=
\begin{bmatrix}
r_\pi(1) \\
\vdots \\
r_\pi(n)
\end{bmatrix}
+\gamma
\begin{bmatrix}
p_\pi(1 | 1) & \dots & p_\pi(n | 1) \\
\vdots & \ddots & \vdots\\
p_\pi(1 | n) & \dots & p_\pi(n | n)
\end{bmatrix}
\begin{bmatrix}
v_\pi(1) \\
\vdots \\
v_\pi(n)
\end{bmatrix} \tag 2
$$
More compactly:
$$
v_\pi = r_\pi + \gamma P_\pi v_\pi \tag 3
$$
We can define an expected Bellman operator $\mathcal{T}^\pi : \mathbb{R}^n \to \mathbb{R}^n$ as:
$$
\mathcal{T}^\pi(v) = r_\pi + \gamma P_\pi v \tag 4
$$
for any $v \in \mathbb{R}^n$.
Let $||\cdot||$ be a norm in $\mathbb{R}^n$. If there exists a $\gamma \in (0, 1)$ such that $||\mathcal{T}^\pi(v_1) - \mathcal{T}^\pi(v_2)|| \leq \gamma ||v_1 - v_2||$ for all $v_1, v_2 \in \mathbb{R}^n$, then $\mathcal{T}^\pi$ is a contraction mapping. In all proofs in this post $|\cdot|$ and $\leq$ are elementwise, and the norm used is the max norm $||x||_\infty = \max(|x|) = \max(|x_1|, \dots, |x_n|)$, where $\max(\cdot) : \mathbb{R}^n \to \mathbb{R}$ chooses the largest element in a vector.
$$
\begin{aligned}
||\mathcal{T}^\pi(v_1) - \mathcal{T}^\pi(v_2)||_\infty &= \max \big(|r_\pi + \gamma P_\pi v_1 - (r_\pi + \gamma P_\pi v_2)| \big) \\
&= \gamma \max \big(|P_\pi(v_1 - v_2)| \big) \\
&\leq \gamma \max \big(P_\pi|v_1 - v_2| \big) \\
&\leq \gamma \max \big(|v_1 - v_2| \big) \\
&= \gamma ||v_1 - v_2||_\infty
\end{aligned}
\tag 5
$$
Thus $\mathcal{T}^\pi$ is a contraction. The last inequality is due to the rows of $P_\pi$ containing only non-negative elements that sum to 1.
Let $r(s, a)$ denote the expected immediate reward when selecting action $a$ in state $s$, and $p_\pi(s^\prime, a^\prime | s, a)$ the probability of transitioning to state $s^\prime$ and selecting action $a^\prime$ when selecting action $a$ in state $s$ and following policy $\pi$ after. The Bellman equation for the action-value function for policy $\pi$ can be defined as follows:
$$
\begin{aligned}
q_{\pi}(s, a) &= \mathbb{E}_\pi \big[R_{t+1} + \gamma q_{\pi}(S_{t+1}, A_{t+1}) | S_t = s, A_t = a \big] \\
&=  \sum_{r \in \mathcal{R}} p(r | s, a) r + \gamma \sum_{s^\prime \in \mathcal{S}} p(s^\prime | s, a) \sum_{a^\prime \in \mathcal{A}(s^\prime)} \pi(a^\prime | s^\prime) q_{\pi}(s^\prime, a^\prime) \\
&= r(s, a) + \gamma \sum_{s^\prime \in \mathcal{S}} \sum_{a^\prime \in \mathcal{A}(s^\prime)} p_\pi(s^\prime, a^\prime | s, a) q_{\pi}(s^\prime, a^\prime)
\end{aligned} \tag 6
$$
for all $s \in \mathcal{S}$, $a \in \mathcal{A}(s)$. Let $n_s = |\mathcal{A}(s)|$, we can write the equation in matrix form:
$$
\begin{bmatrix}
q_\pi(1, 1) \\
q_\pi(1, 2) \\
\vdots \\
q_\pi(n, n_n)
\end{bmatrix}=
\begin{bmatrix}
r_\pi(1, 1) \\
r_\pi(1, 2) \\
\vdots \\
r_\pi(n, n_n)
\end{bmatrix}
+\gamma
\begin{bmatrix}
p_\pi(1, 1 | 1, 1) & p_\pi(1, 2 | 1, 1) & \dots & p_\pi(n, n_n | 1, 1) \\
p_\pi(1, 1 | 1, 2) & p_\pi(1, 2 | 1, 2) & \dots & p_\pi(n, n_n | 1, 2) \\
\vdots & \vdots & \ddots & \vdots \\
p_\pi(1, 1 | n, n_n) & p_\pi(1, 2 | n, n_n) & \dots & p_\pi(n, n_n | n, n_n)
\end{bmatrix}
\begin{bmatrix}
q_\pi(1, 1) \\
q_\pi(1, 2) \\
\vdots \\
q_\pi(n, n_n)
\end{bmatrix} \tag 7
$$
More compactly:
$$
q_\pi = r_\pi + \gamma P_\pi q_\pi \tag 8
$$
The only difference compared to the equation for the state-value function is that the vectors and matrices are larger. Thus, we can define an expected Bellman operator in identical fashion (with $n$ denoting the number of state-action pairs rather than the number of states) and the proof will be identical (the rows of $P_\pi$ still contain only non-negative elements that sum to 1).
Bellman optimality equations
For brevity I will go directly into the compact matrix form of the Bellman optimality equation for the optimal state-value function:
$$
v_* = \max_\pi(r_\pi + \gamma P_\pi v_*) \tag 9
$$
We can define an expected Bellman optimality operator $\mathcal{T}^* : \mathbb{R}^n \to \mathbb{R}^n$ as:
$$
\mathcal{T}^*(v) = \max_\pi(r_\pi + \gamma P_\pi v) \tag {11}
$$
The rest of the post will focus on trying to prove that this is a contraction operator, because once again I believe that an identical proof works for the action-value function (please correct me if this is wrong).
Consider any two vectors $v_1, v_2 \in \mathbb{R}^n$, and let $\pi_1^* = \text{argmax}_\pi(r_\pi + \gamma P_\pi v_1)$ and $\pi_2^* = \text{argmax}_\pi(r_\pi + \gamma P_\pi v_2)$. Then we have:
$$
\mathcal{T}^*(v_1) = \max_\pi(r_\pi + \gamma P_\pi v_1) = r_{\pi_1^*} + \gamma P_{\pi_1^*} v_1 \geq r_{\pi_2^*} + \gamma P_{\pi_2^*} v_1 \\
\mathcal{T}^*(v_2) = \max_\pi(r_\pi + \gamma P_\pi v_2) = r_{\pi_2^*} + \gamma P_{\pi_2^*} v_2 \geq r_{\pi_1^*} + \gamma P_{\pi_1^*} v_2 \tag{12}
$$
$$
\begin{aligned}
\mathcal{T}^*(v_1) - \mathcal{T}^*(v_2) &= r_{\pi_1^*} + \gamma P_{\pi_1^*} v_1 - (r_{\pi_2^*} + \gamma P_{\pi_2^*} v_2) \\
&\leq r_{\pi_1^*} + \gamma P_{\pi_1^*} v_1 - (r_{\pi_1^*} + \gamma P_{\pi_1^*} v_2) \\
&= \gamma P_{\pi_1^*} (v_1 - v_2)
\end{aligned}
$$
Similarly we have $\mathcal{T}^*(v_2) - \mathcal{T}^*(v_1) \leq \gamma P_{\pi_2^*} (v_2 - v_1)$, which implies that $\mathcal{T}^*(v_1) - \mathcal{T}^*(v_2) \geq \gamma P_{\pi_2^*} (v_1 - v_2)$, and thus we have:
$$
\gamma P_{\pi_2^*} (v_1 - v_2) \leq \mathcal{T}^*(v_1) - \mathcal{T}^*(v_2) \leq \gamma P_{\pi_1^*} (v_1 - v_2) \tag{13}
$$
Let $\max\{\cdot, \cdot \} : \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}^n$ choose the largest values between two vectors elementwise, we have:
$$
\begin{aligned}
|\mathcal{T}^*(v_1) - \mathcal{T}^*(v_2)| &\leq \max \{|\gamma P_{\pi_2^*} (v_1 - v_2)|, |\gamma P_{\pi_1^*} (v_1 - v_2)| \} \\
&\leq \gamma \max \{P_{\pi_2^*} |v_1 - v_2|, P_{\pi_1^*} |v_1 - v_2| \}
\end{aligned}
$$
Let $\max(\cdot) : \mathbb{R}^n \to \mathbb{R}$ choose the largest element in a vector (as previously defined), we have:
$$
\begin{aligned}
||\mathcal{T}^*(v_1) - \mathcal{T}^*(v_2)||_\infty &= \max \big(|\mathcal{T}^*(v_1) - \mathcal{T}^*(v_2)| \big) \\
&\leq \gamma \max \big(\max \{P_{\pi_2^*} |v_1 - v_2|, P_{\pi_1^*} |v_1 - v_2| \} \big) \\
&\leq \gamma \max \big(|v_1 - v_2| \big) \\
&= \gamma ||v_1 - v_2||_\infty
\end{aligned}
$$
Thus $\mathcal{T}^*$ is a contraction. Note that the last inequality is once again due to the rows of $P_\pi$ containing only non-negative elements that sum to 1.
Thank you for reading this far! If you have the time, please let me know if the proofs are correct, if the proofs for the state-value and action-value functions are identical as I suggest, and any other feedback.

This post is way too long. You should have simplified it or split it into multiple ones, for example, if you're concerned about multiple proofs, which seems to be the case.

My first impression is that the proofs are correct, but there is a shorter way. If you first prove that the Bellman optimality operator is a contraction, then it is a corollary that the other two operators are also contractions. For the state-value function, let the set over which you maximize in (9) and (11) be a singleton. For the action-value function, let the set over which you maximize in (9) and (11) be a singleton containing a Dirac measure. By the way, you did not specify the set of admissible policies and a few other things.


text:
Sutton & Barto: what are parametrized functions?
From "Reinforcement Learning: An introduction (2nd ed.)" by Richard S. Sutton and Andrew G. Barto, on page 59

Instead, the agent would have to maintain $v_\pi$ and $q_\pi$ as parameterized functions (with fewer parameters than states) and adjust the parameters to better match the observed returns.

What do they mean by "parametrized functions" here? The part of "adjust parameters to better match observed returns" also sounds odd to me.

I won't post a full answer since this comment might not fit the requirements for a good answer. A parameterized function is just where you model a real world function, g(x), as f(x,theta) and then find the theta that makes f agree with g. A neural network has inputs as well as unit weights and biases.

A parameterized function is a function that is defined by a set of parameters. If you change the parameters, you also change the actual function. For example, let's define this linear function
$$f: \mathcal{X} \rightarrow \mathcal{Y}$$ as follows
$$f(x; a, b) = ax + b \in \mathcal{Y}.$$
Here, $x \in \mathcal{X}$ is the input to $f$, while $a \in \mathbb{R}$ and $b \in \mathbb{R}$ are the parameters. Clearly, if you change $a$ and $b$, you actual get different functions. If that's not obvious, you can graph them with a tool (e.g. this one). So, a parametrized function can actually be thought of a set of functions or a model. For more details about how functions and models are related in AI, see this answer.
Now, back to the specific context. $v_\pi$ and $q_\pi$ are value functions, so they give you the value of a state or state-action pair, respectively, i.e. the expected return (reward in the long run). The goal in RL is really to learn these functions or a policy. Now, Sutton & Barto mean that we can use a model like $f$ above and adjust the parameters $a$ and $b$ in order to learn the optimal value functions. Now, I will not define what an optimal value function is. It's defined in the book. Once you have a good grasp of the notion of a value function and optimality, you can also check this post (written by me) for more mathematical details on Bellman equations and value functions.
Now, why would you want to use a function like $f$ to approximate these value functions? The same book tells you why in the sentence before - for finite MDPs, we could use an array to represent these functions, but if there are many states, actions, etc., it becomes hard to learn these functions in this way. If we use parameterized functions, we do not need to maintain so many entries (one for each state or state-action pair) and we hope that the function can generalise to unseen or rarely seen inputs.
Finally, in practice, people have been using neural networks to learn value functions. The difference between neural networks and $f$ above is that neural networks are non-linear, more powerful, but they also provide fewer guarantees.


text:
Is it necessary to have a constant reward in the terminal state?
I have downloaded the grid world project form this link. I have executed the project multiple times using:
python gridworld.py -k 20 -a q -r -0.2 -s 90

I have noticed that the reward of the terminal states are changing with time. The grid world at time $t$ is as follows:

The grid world at some later time $t+k$ is as follows:

First of all, I am assuming that the values written inside the terminal states are the rewards and not the values of these states since we don't have $q$-values calculated for these states like the other states. If you see for example the green terminal state, at time $t$ the reward is equal to 0.75 but after some time it has converged to 1. So can we have a changing reward in an episodic task, and if so, why?

First of all, I am assuming that the values written inside the
terminal states are the rewards and not the values of these states
since we don't have $q$-values calculated for these states like the
other states.

Correct. The value of a terminal state is zero by convention. This topic is beyond the scope of the question, so I will provide a link to a relevant AI Stack Exchange question with explanation.

If you see for example the green terminal state, at time $t$ the reward
is equal to 0.75 but after some time it has converged to 1. So can
we have a changing reward in an episodic task, and if so, why?

Definitions: This gridworld environment, along with most RL environments, possesses an underlying Markov decision process (MDP). Using the Wikipedia definition, an MDP is endowed with a state space $\mathcal{S}$, an action space $\mathcal{A}$, a state transition function $P_a(s, s')$, and a reward function $R_a(s, s')$. The reward function details the reward $r$ received by taking action $a$ in state $s$ and resulting in next state $s'$. In the case of finite MDPs, see equation 3.6 of Sutton and Barto for the mathematical formulation of the reward function.
Answer: To answer your question, yes, there can exist changing rewards in an episodic task. This amounts to having an underlying nonstationary MDP, where the reward function changes over time. In this case, the reward function may be viewed as stochastic instead of deterministic since the realized reward of transitioning to a state can attain various values. Another possible viewpoint is that the reward function would be deterministic if the state were to encode the current time $t$ and if the reward function of $a$, $s$, $s'$, and $t$ were deterministic. This is an example in which encoding more relevant information into the state when designing the MDP could increase the speed and performance of the learning algorithm.
Example: As a toy example, assume that your gridworld problem is to navigate to a specific beach by the ocean. In this problem, each episode is one day, and the reward is the happiness or recreational value achieved at the beach. Perhaps the terminal state with positive reward is the correct beach, and the terminal state with negative reward is the wrong beach (assume that navigating to the wrong beach spoils your day and provides a large negative reward). In this case, the reward function for reaching the terminal state of the correct beach may not be constant and could be dictated by external factors such as the weather, occupancy, entertainment, availability of amenities, etc. For example, having bright, sunny weather may provide a high positive reward, while having gloomy weather may provide low positive reward.
Conclusion:  Nonstationary reward functions can easily occur in environments that possess a temporal aspect such as the stock market, retail sales, an electrical grid, etc. The state transition function could also be nonstationary, for instance, when playing against increasingly better opponents in board games such as Go (e.g. self-play algorithms). Many of the factors discussed above make it especially important to understand and investigate the MDP before designing a corresponding learning algorithm.

Excellent answer. Thank you so much. I think also one possible reason for a changing reward in my example is that initially all the q values are set to zero, so they are estimates  in earlier times and not accurate, so one way to have accurate updates for the q values is through the changing reward that represents concrete data . See this  https://towardsdatascience.com/reinforcement-learning-explained-visually-part-4-q-learning-step-by-step-b65efb731d3e


text:
Would the node with value 5 in this tree be pruned if doing left-to-right alpha-beta pruning?
I'm trying to understand if the node with value 5 would be pruned if doing left-to-right alpha-beta pruning in a minimax game. I can see two interpretations:

Initialize $\alpha = -\infty$ and $\beta = \infty$. When you reach the leaf node of 15, $\alpha$ gets updated to 15. The algorithm stops if $\alpha \geq \beta$, and it is not. So, the node with value 5 is searched.

The leaf node 15 is searched from the perspective of the MAX player (colored blue). Since the parent node of MAX is MIN (colored green), it is trying to minimize the value, there is no need to search the right child of the MAX player. That node would be chosen if it is >15. But MIN already has a 10 available to it, and the 5 node can be pruned.

I think your confusion stems from forgetting that minimax and alphabeta is almost exclusively implemented as a depth first search.
As a result, the node valued 5 would not be pruned, simply because we will explore it before ever getting to the node valued 10.
If the tree structure was such that the children of the green node were flipped, then we would encounter the 10 node first. In this case, the 5 node would indeed be pruned.
This illustrates a key aspect of alpha beta pruning, how the order we explore nodes is very important.
If this is confusing, I suggest looking into depth first search and the order of when nodes are explored.

Thanks, I just realized this after posting and thinking for 10 more minutes. I understand DFS, and the 10 node would not have been discovered yet.

@maxutil no problem. I added some more info as well. If this answers your question please mark it with the green check.


text:
How does ChatGPT retain the context of previous questions?
One of the innovations with OpenAI's ChatGPT is how natural it is for users to interact with it.
What is the technical enabler for ChatGPT to maintain the context of previous questions in its answers? For example, ChatGPT understands a prompt of "tell me more" and expands on it's previous answer.
Does it use activations from previous questions? Is there a separate input for the context? How does it work?

ChatGPT says: "ChatGPT uses a type of natural language processing called "transformer" architecture, which is a type of neural network that is designed to process and generate language. One of the key features of transformer architecture is that it allows the model to maintain a "context" of previous inputs. This is achieved through the use of self-attention mechanisms, which allow the model to weight different parts of the input differently based on how relevant they are to the current context. This allows the model to generate more nuanced and context-aware responses."

It does, indeed, but the transformer architecture alone does not explain this capability. Maintaining context requires something else. In fact, I think being a transformer is irrelevant for this purpose.

My best guess is that the whole conversation is fed as input for the next reply. But looking into openai labelling guidance, it looks that the data collection is single Q&A only.

If my guess is correct, when the conversation is very long ChatGPT should start forgetting previous bits, due to the maximum sequence size.

The ability to maintain context is very mysterious.  What is most mysterious to me is that if I continuously converse with ChatGPT it has no problem maintaining context.  On the other hand, if I break in the middle of a conversation, and then come back to it some time later, it's as if ChatGPT has had a memory wipe and has a lot of trouble regaining the thread of the conversation.  Since ChatGPT is a neural network where the output is generated based on the previous 2048 input tokens, the amount of time between responses should have no bearing on the output generated.

Great observation @yters. Could it be a bug: the interface correctly shows the previous conversation, but the service fails to send this to the OpenAI APIs after some time.

I don't have enough reputation to answer this question, but I've been playing around with text-davinci-003 quite a bit and can simulate the history that ChatGPT achieves with a relatively simple trick: in the prompt I ask it to summarize the conversation so far. I then pass that summary into the next prompt along with as much of the conversation as I think is appropriate to fit inside the token limit. text-davinci-003 does a very nice job of concisely summarizing the conversation. It's not as good as ChatGPT, but I do believe this is part of the magic.

@Rainb why didn’t you put that as an answer?  Follow up question - do you have a bit of references about these “transformer” models? Does OpenAI have any available to public?

@Antonio the transformer is now a standard building block of deep neural networks used widely in image, audio and language processing. Hence that answer by ChatGPT is not really informative. There are plenty of transformer models available in Huggingface for example, and most definitely all of OpenAIs language and image processing models employ the architecture.

I imagine something like the “memorizing Transformer” architecture will be adapted in time, if not already for GPT4. https://arxiv.org/abs/2203.08913

Based on an answer by OpenAI, it appears that the illusion of understanding context is created by the model's capacity to accept very long input sequences. The OpenAI FAQ states that approximately 3000 words can be given as input. This together with the fact that GPT-3 was trained to produce text that continues a given prompt could explain the context feature.
In practice, each prompt is probably extended with the previous outputs and prompt, as much as the input sequence length allows. So, all of the context is actually in the prompt.
Edit 18.2.2023
After spending some time with large language models and reading up the theory, I think my old answer is an understatement of ChatGPT's capabilities.
It is likely that there are several engineering approaches to improve the context after the maximum content length is exceeded. These include (but are probably not limited to)

Using language models to summarize the conversation thus far, and using that as context
Using language models to search for the relevant context from the previous discussion (can be done by embedding questions and answers and doing a distance-based lookup in vector space), and feeding those as context with clever prompting like "If this information improves your answer, update your answer accordingly".

So does that imply that if you keep chatting long enough, that ChatGPT starts to lose context as well, since you pass the threshold? That would certainly explain some brain dead responses I get sometimes.... like "I just told you that, you already forgot!?"

Yes, I think so. Most likely the latest messages (up to the token limit) are included as context, so that is the effective working memory ChatGPT has.

I did some experiments and it seems the token limit is not a hard one. Or at least the context doesn't completely go away. I don't know how they determine what is kept, but after flushing ChatGPT with a lot of content (or rather having it flood me), it still remembered the fine details of the conversation's start. It's rather impressive.

Agreed. Mathematically, they can retain the previous content through marginalization (https://www.quora.com/What-is-marginalization-in-probability). This can be done using Bayesian assumptions or simply a DL model. Of course there are a lot of good engineering involved. The amazing part is most folks in NLU space knows how to create ChatGPT in theory but it takes a very good engineering / science team, plus resources, to get this done correctly and efficiently.

Do you think ChatGPT used my interactions in the current session to enhance their answers? I think so based on my experience, but not sure.

@Avv yes it can use previous interactions in the current chat. But those will not carry over to future discussions. Not in real time anyway. Unless you opt out of the training data collection, your discussions on the chat UI may be used to train OpenAI models.

@milez. from my experience I noticed that it's aware of all my previous interactions and use them to answer current interactions, but you might be right that it does not use them in a separate chat unless I start all over.

@Keeeeeenw What is marginalization for conversation or LLM specifically?

What I wish we knew, and as far as I know OpenAI hasn't disclosed, is the actual strategy they use for managing context in lengthy conversations. I've noticed it can still remember "old" bits of the convo while quickly forgetting "new" things sometimes, so I think it's not simply truncating the oldest messages. Rather, they're doing some more advanced processing to conversation history before loading it into context, but unfortunately, I don't know exactly what, and we may not have any avenue to find out. Like @RLC suggested, summarization probably plays some part in that.

Based on nothing but my own experience trying to build a similar chatbot using text-davinci-003, I think they are using the model itself to summarize the conversation, then feeding that summary back into the prompt. I get good results when doing this - though obviously the team behind ChatGPT does a better job.
Here is an example using the discussion under the question above:

You are a user named "AI" in an online forum. Below is a conversation
about a question. Please add your contribution to the conversation.
Question: """ One of the innovations with OpenAI's ChatGPT is how
natural it is for users to interact with it.
What is the technical enabler for ChatGPT to maintain the context of
previous questions in its answers? For example, ChatGPT understands a
prompt of "tell me more" and expands on it's previous answer.
Does it use activations from previous questions? Is there a separate
input for the context? How does it work? """
Rainb: """
ChatGPT says:
"ChatGPT uses a type of natural language processing called
"transformer" architecture, which is a type of neural network that is
designed to process and generate language. One of the key features of
transformer architecture is that it allows the model to maintain a
"context" of previous inputs. This is achieved through the use of
self-attention mechanisms, which allow the model to weight different
parts of the input differently based on how relevant they are to the
current context. This allows the model to generate more nuanced and
context-aware responses." """
milez: """ It does, indeed, but the
transformer architecture alone does not explain this capability.
Maintaining context requires something else. In fact, I think being a
transformer is irrelevant for this purpose. """
Rexcirus: """ My best
guess is that the whole conversation is fed as input for the next
reply. But looking into openai labelling guidance, it looks that the
data collection is single Q&A only. """
Rexcirus: """ If my guess is
correct, when the conversation is very long ChatGPT should start
forgetting previous bits, due to the maximum sequence size. """
yters:
""" The ability to maintain context is very mysterious. What is most
mysterious to me is that if I continuously converse with ChatGPT it
has no problem maintaining context. On the other hand, if I break in
the middle of a conversation, and then come back to it some time
later, it's as if ChatGPT has had a memory wipe and has a lot of
trouble regaining the thread of the conversation. Since ChatGPT is a
neural network where the output is generated based on the previous
2048 input tokens, the amount of time between responses should have no
bearing on the output generated. """
milez: """ Great observation
@yters. Could it be a bug: the interface correctly shows the previous
conversation, but the service fails to send this to the OpenAI APIs
after some time.  """
AI: """ It is possible that the OpenAI API may
be designed to automatically discard the context after some time to
avoid the system being overburdened with large conversations. Another
possibility is that the system may be storing the context, but using a
different mechanism than the transformer architecture to access it.
"""

Now, I'll ask it to summarize the conversation so far:

You are a user named "AI" in an online forum. Below is a conversation
about a question. Please summarize the interaction so far.
[I then pasted in everything from the Question down in the previous prompt/response]
The conversation so far has focused on understanding the technical
enablers that allow ChatGPT to maintain context in its answers. Rainb
has suggested that this is done through transformer architecture and
self-attention mechanisms. Rexcirus has suggested that the whole
conversation may be fed as input for the next reply. Yters has then
posed the interesting question of why, when the conversation is broken
off and then resumed, ChatGPT has difficulty regaining the thread.
Milez has suggested that this could be a bug in the interface.

Finally, I delete most of the conversation except for the summary and last few responses and alter the prompt a little to alert it to the presence of the summary:

You are a user named "AI" in an online forum. Below is a summary of
the conversation so far about a question, and the last few responses
to that question. Please add your contribution to the conversation.
Summary: The conversation so far has focused on understanding the
technical enablers that allow ChatGPT to maintain context in its
answers. Rainb has suggested that this is done through transformer
architecture and self-attention mechanisms. Rexcirus has suggested
that the whole conversation may be fed as input for the next reply.
Yters has then posed the interesting question of why, when the
conversation is broken off and then resumed, ChatGPT has difficulty
regaining the thread. Milez has suggested that this could be a bug in
the interface.
yters: """
The ability to maintain context is very mysterious. What is
most mysterious to me is that if I continuously converse with ChatGPT
it has no problem maintaining context. On the other hand, if I break
in the middle of a conversation, and then come back to it some time
later, it's as if ChatGPT has had a memory wipe and has a lot of
trouble regaining the thread of the conversation. Since ChatGPT is a
neural network where the output is generated based on the previous
2048 input tokens, the amount of time between responses should have no
bearing on the output generated. """
milez: """
Great observation
@yters. Could it be a bug: the interface correctly shows the previous
conversation, but the service fails to send this to the OpenAI APIs
after some time.  """
AI: That is an interesting point, @Milez. It could be that the
interface does not accurately display the previous conversation to the
API, or that there is a bug in the API that causes it to not be able
to accurately generate a response with the 2048 input tokens when the
conversation is broken off and then resumed. It would be interesting
to investigate further.

I've had some success with this method, though it does still lose detail. Improving the prompt to create a more detailed summary helps. It's amazing how much of a conversation is full of repetitive filler, and how concisely it can be summarized. Maybe this is some kind of lingual compression? :)

Lemme run your answer through GPT-4...


text:
Are my attempts to write "There exists a student studying all the subjects of the information technology subject" in FOL correct?
I have the following sentence, which I need to write in FOL

There exists a student studying all the subjects of the information technology subject

I don't know how $\forall$ can be combined with the $\land$.
It was written by my teacher as follows
$$\exists x, \forall y: \text{student}(x) \land \text{learn}(x, y) \land \text{ITsubject}(y)$$
However, I was thinking this sentence should be written like this:
$$\exists x \text{student}(x) \land \forall y(\text{ITsubject}(y) \rightarrow \text{learn}(x, y))$$
or maybe
$$\exists x \text{student}(x) \land \forall y(\text{learn}(x, y) \rightarrow \text{ITsubject}(y))$$
Is this right?

Your two trials are obviously wrong since the occurrence of the latter $x$ are both free if you pay attention to its scope and paranthesis, and your last trial cannot be salvaged since such student may possibly learn non-IT subjects too. You can salvage your first trial as $∃x (student(x) \land ∀y(ITsubject(y) \to learn(x, y)))$, which could be further converted to prenex normal form $∃x∀y (student(x) \land (ITsubject(y) \to learn(x, y)))$ or $∃x∀y (student(x) \land (\lnot ITsubject(y) \lor learn(x, y)))$. And from this it shows your teacher's translation is incorrect or there's some typo in between, which is also apparent semantically since your teacher's version means every subject in your universe is ITsubject which is trivial here and most likely false in most 1-sorted context.

sorry i forgot the parenthesis, and you say the statement of my teacher is trivial so that its neither false nor true in some case?

It should be $∃x∀y(student(x)∧(¬ITsubject(y)∨learn(x,y)))$ as shown in the end of my above answer which is obviously not logically equivalent to your teacher's version or entail it (unless you can show how to derive from mine to your teacher's version). Also semantically your teacher's version is wrong translation per common sense, and by "trivial" here I mean your teacher's version is false unless your FOL is 2-sorted and in the universe for $y$ there're only ITsubject(s), nothing else, which is trivial per common sense.

Also u say the last trial not salvaged but like this sentences: There is an agent who sells policies only to people who are not insured.Translation : (∃x )(Agent(x) ∧ ( ∀ y) SellsPolicy(x,y) => ~Insured(y)) why this wouldnt be (∃x )(Agent(x) ∧ ( ∀ y) ~Insured(y) => SellsPolicy(x,y)) why don't they invert the SellsPolicy(x,y)) after the =>


text:
Why is the time complexity of the Triplet Loss $O(N^3)$
The triplet loss function uses an anchor, positive, and negative examples. If $N$ are the number of examples in the training set with $C$ classes, then I think that the time complexity should be $O(NN_cN_{c'})$ not $O(N^3)$ from Probabilistic Machine Learning, Murphy (2022)

Naively minimzing the triplet loss takes $O(N^3)$ time

Because for every example in the training set, we have $N_c$ possible positive examples in a class $C=c$ and $N_{c'}$ possible negative examples not in class $C=c$
(I've seen other research papers used that however with a modification in the denominator: $\mathcal{O}(N^3/C)$, where $C$ is the number of classes)

Can you please provide source tha claims that the complexity is $O(N^3)$?

@nbro In "Probabilistic Machine Learning, Murphy (2022)" - "Naively minimzing the triplet loss takes $O(N^3)$ time". I've seen other research papers used that however with a modification in the denominator: $O(N^3/C)$ where $C$ is the number of classes

Please, edit your post to include all this info directly there.

For each anchor data point $x_i^a$ in class $j$, the intra-distance should be computed $g_j$ times, where $g_j$ is the sample size of that class and the inter-distance should be computed as $N$ times, where $N$ is the sample size of the dataset. In other words, for each data point, the triplet loss computes all possible distance between the intra-distance and the inter-distance, and the computation cost for $x_i^a$ should be $g_i \cdot N$.
For the dataset, the total computation cost is  $\Sigma_j^c (g_j^2 \cdot N)$.
$$
\begin{align*} O(*) &= \Sigma_j^c (g_j^2 \cdot N) \\      &= N \cdot \Sigma_j^c g_j^2 \\      \end{align*}
$$
According to the arithmetic mean and quadratic mean inequality[28], $\frac{\Sigma_i^n x_i}{n} \leq \sqrt{\frac{\Sigma_i^n x_i^2}{n}}$, when $x_1 = x_2 = x_3 ... = x_n$ the arithemtic mean is equal to the quadratic mean.
Therefore,
$$
\begin{align*}N \cdot (\frac{\Sigma_j^c g_j}{c})^2 \cdot c &\leq O(*) < N \cdot \Sigma_j^c N^2 \\N \cdot \frac{N^2}{c} &\leq O(*) < c \cdot N^3 \\ \frac{N^3}{c} &\leq O(*) < c \cdot N^3\\\end{align*}
$$
The lower boundary of $O(*)$ is consistent with the paper result.


text:
What is the intuition behind self-attention?
I've been watching a few lectures on transformers, especially for language translation, though it seemingly becomes more confusing the more I watch.
In this lecture, there seems to be two conflicting views of self-attention. First, there's an Iron Man example (at around 44:25) where the lecturer claims that self-attention helps identify the important aspects of the input, but she details the math in which a "self-attention heat map", which is the dot product of the query and key matrices, is multiplied by a value matrix giving an output, which I assume is an attention head. It seems like this attention head just encodes how words are related to each other (the map) and the words themselves (the value).
I don't understand how this extracts the important information, or why you only want the important information anyways for translation. Is it extracting the important relationships between words, because that would make more sense, but in what way does that relate to her Iron Man example then? What's the relationship of Iron Man to himself? Also, would each attention head contain its own set of three matrices? Is the idea perhaps that words that more words depend on are important? But wouldn't that simply remove single words that still are important for translation?
TLDR: Essentially, how does the idea of relationships between words translate to selecting important words in a sentence (if this is even what self-attention does).

Seems multiple questions here and not sure what's the most pertinent one for your understanding. One common difficulty facing NLP and translation is poly-semantic indeterminacy even for some word (not to mention the sense of whole sentence or paragraph), so self-attended multiple heads of words relations could often help to fix such indeterminacy issues such as the ubiquitous "it", "this", "that" in a parallel fashion. The Iron Man case using image to illustrate the same idea to perhaps help fix the caption or title of such image. Another attention head of spaceship may decide another caption.

First of all, I totally agree that the Iron Man example is a little off the topic and not really clear to explain the concept of self-attention.
But she had a point there. Just like what you said, the self-attention mechanism extracts the relationships between words and then after being scaled down and multiply with the value tensor, it makes more sense for what are the important keys that need to be attended by the model.
Now let's get back to the Iron Man example. I think the idea is that our brains can immediately know which parts are the important part of the image to focus on because we all have that attention filter that is always turning on.
It's different from the CNN or the RNN model, which needs to know the feature first (feature extraction). The self-attention calculates the relationship between each token and the importance on the whole image first and then can use that information to focus on feature extraction on those really important parts.

One way to think about this is that self-attention does a summary of what is going on, either in text or images. But rather than creating a new representation for the summary, the summary is represented by assigning weights to units of the original content it's summarizing.
Somewhat like instead of reading the whole paragraph above, or summarizing, you just read what's written in bold.
When it comes to text, that weight is given to the most "representative" words within the sentence, in pictures you can think of an heat map perhaps indeed.
To determine what units (say words) could be most representative, you look at the data itself, and see what words have stronger relationships with others. This is the same philosophy behind search and the page rank algorithm
Lastly to clarify a remark the OP made: this is not the only information an ML model (say a Transformer) would look at. But it is an approach the model uses to extract some meaningful information (i.e. create some meaningful features), which is then further processed by other parts of the model.


text:
Does this property in product fuzzy logic have a name and any consequences?
In product fuzzy logic, the $AND$ operator of two variables $x_0$ and $x_1$ is the product $x_0x_1$.
Using the $NOT(x)$ as $1-x$, expressions for the other three minterms are easily obtained.
$$\overline{x_0}x_1 = (1-x_0)x_1$$
$$x_0\overline{x_1} = x_0(1-x_1)$$
$$\overline{x_0}\overline{x_1} = (1-x_0)(1-x_1)$$
These four expressions have the property that they sum up to $1$, as in bivalued logic.
$$ x_0x_1+(1-x_0)x_1+x_0(1-x_1)+(1-x_0)(1-x_1)=1$$
This is not the case when the conjunction is the Zadeh operator $min(x_0,x_1)$, where the sum of the four minterms happens to be a square pyramid over the unit cube, neither other possible definitions of fuzzy operators.

Does this property have a name, and any consequences?

In the bivalued logic case the two variables $x_0$ and $x_1$ are discrete with values of either $0$ or $1$, and your four-terms sum is the disjunctive normal form (DNF) of truism whose graph is the upper half vertices of the unit cube under your context. While in the fuzzy logic with Zadeh operator case, the two variables are continuous real numbers ranging from $0$ to $1$, and the graph of your four-terms sum as you showed is a convex pyramid. One consequence is the unique maximum function value of $2$ when surprisingly both $x$ and $y$ take the value of $0.5$ instead of $1$!
If you replace $+$ in your fuzzy case with the corresponding Zadeh $OR$ operator which takes the maximum, the sum of your four-terms would take maximum value back to $1$ at the four corners and ceases to be a truism formula since the sum is strictly less than $1$ when either variable is not $0$ or $1$. This suggests fuzzy logic aptly tracks degree of truth of complex composite propositions on a continuous basis based on continuously valued fuzzy inputs and meanwhile it's not the same usual concept of probability. Thus fuzzy logic is used in control applications a lot where controller's complex CNF/DNF condition's degree of truth may be more easy and accurate to estimate than probabilities in many vague cases without many propagated rounding errors.

Well, my $x_0$ and $x_1$ are continuous in the interval [0,1], and the truism is not only the upper four vertices of the unit cube, but the upper flat face. Should have added that plot as well and written "continuous" before.$x_0$ and $x_1$... I start with one hyperbolic parabola and write the other three. Another beautiful sum is that of adjacent terms, which leads to ramps in a single variable when the and is the product but not when it is the minimum.

Yes pls add that plot with your Boolean operator applied to continuous variable fuzzy logic case to make it clear and we can see difference with the Zadeh operator more visually.


text:
Are there techniques for estimating optimal neural network size?
Are there techniques for estimating optimal neural network size?
To replicate "AND gate", one does not need 1e1000 nodes in hidden layer. What would be the metric hinting at "too much nodes"?

Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking.

There are several techniques for estimating the optimal size of a neural network, including cross-validation, Bayesian optimization, and early stopping. In general, having too many nodes in a hidden layer can lead to overfitting, which means that the model will perform well on the training data but will not generalize well to new, unseen data. One way to detect overfitting is to monitor the performance of the model on a validation set during training. If the performance on the training set continues to improve while the performance on the validation set starts to deteriorate, this is a sign of overfitting and suggests that the model may have too many nodes.
There are some general rules of thumb for determining the size of a neural network, but these are only rough guidelines and may not be applicable in all cases. For example, one common rule of thumb is to start with a small network and gradually increase the size until the performance on the validation set stops to improve. However, this rule of thumb does not take into account the complexity of the problem being solved or the amount of training data available, so it may not always produce optimal results/be applicable. In general, it is best to use a combination of techniques, such as cross-validation and early stopping, to determine the optimal size of a neural network for a given problem.

Hey! This answer looks like it may have been (partially) generated by an AI-based tool like ChatGPT. If this is the case, this should be explicitly stated in the post. Furthermore, there is a new policy in effect (see https://ai.meta.stackexchange.com/questions/2905/please-do-not-post-ai-generated-content-as-actual-posts) which means that such tools should not continue to be used to generate content for future posts on StackExchange.

I'd also like to ask you for a clarification: for the technique of starting with a small network, and gradually increasing its size, you wrote that you should do that until the performance on the validation set starts to improve. Shouldn't that be stops? Afterwards, you wrote that this rule of thumb doesn't account for problem complexity or training data availability. Why not? Wouldn't performance stop improving earlier on an easy problem, for example?

@DennisSoemers thanks for the concern. It was not generated by ChatGPT. You are right that i typod and it should be stops (see edit). Regarding your second, im not saying they are not correlated, they are. However, networks that are too large can cause an optimizer to never converge at all, and some problems do not even have a validation loss. There are various circumstances under which the rule of thumb ddoes not hold.


text:
Are there versions of attention that do not require a key-value pair, but just act on one input?
Are there versions of attention that do not require a key-value pair, but just act on one input? Or does this idea simply not make sense?

Self attention only acts on one input sequence. This is actually arguable the most common form of attention seen today, as popularized by transformers. In self attention, the keys and values are the same, thus there is only a single input sequence.
As described in the paper "Attention is All You Need"

Self-attention, sometimes called intra-attention, is an attention mechanism relating different positions of a single sequence in order to
compute a representation of the sequence.

If you are unfamiliar with self attention, in addition to the paper linked above, this blog post may be useful. Also see the Pytorch transformer layer documentation, which is an example of self attention that only takes a single input sequence.

Transformers work by generating keys, values and queries from the same input.