text:
Is there a fundamental difference between an environment being stochastic and being partially observable?
In AI literature, deterministic vs stochastic and being fully-observable vs partially observable are usually considered two distinct properties of the environment.
I'm confused about this because what appears random can be described by hidden variables. To illustrate, take an autonomous car (Russel & Norvig describe taxi driving as stochastic). I can say the environment is stochastic because I don't know what the other drivers will do. Alternatively, I can say that the actions of the drivers are determined by their mental state which I cannot observe.
As far as I can see, randomness can always be modeled with hidden variables. The only argument I came up with as to why the distinction is necessary is Bell's inequality, but I don't think that AI researchers had this in mind.
Is there some fundamental difference between stochasticity and partial observability or is this distinction made for practical reasons?

Going in slightly the other direction... it seems pretty easy to make a system that is only partially observable but not stochastic. Say, a Game of Life implementation where all the cells outside of the starting configuration are masked out. So the two can't be exact synonyms.

@DanielWagner but the masked cells are in theory deducible from the other cells right? If not, then it is in fact stochastic

@JohnJiang Right, the masked cells are deducible.

I think the distinction is made more for conceptual reasons, which has practical implications, so let me review the usual definitions of a stochastic and partially observable environment.
A stochastic environment can be modeled as a Markov Decision Process (MDP) or Partially Observable MDP (POMDP). So, an environment can be

stochastic and partially observable
stochastic and fully observable

The stochasticity refers to the dynamics of the environment and, more specifically, to how the environment stochastically moves from one state to the other after an action is taken (basically, a Markov chain with actions and rewards). In other words, in a stochastic environment, we have the distribution $p(s' \mid s, a)$ (or, in some cases, the reward is also included $p(s', r \mid s, a)$). If $p(s' \mid s, a)$ gave a probability of $1$ to one of the states and $0$ to all other states, we would have a deterministic environment.
The partial observability refers to the fact that we don't know in which state the agent is, so we can think of having or maintaining a probability distribution over states, like $b(s)$. So, in the case of POMDP, we not only are uncertain about what the next state $s'$ might be after we have taken $a$ in our current state $s$, but we are not even sure about what $s$ currently is.
So, the difference is made so that we can deal with uncertainties about different parts of the environment (dynamics and actual knowledge of the state). Think about a blind guy that doesn't have the full picture (I hope this doesn't offend anyone) and think about a guy that sees well. The guy that sees well still isn't sure about tomorrow (maybe this is not a good example as you can argue that this is also due to the fact that the guy that sees well doesn't know the full state, but I hope this gives you the intuition).
Of course, this has practical implications. For example, it seems that you cannot directly apply the solutions that you use for MDPs to POMDPs. More precisely, for an MDP, if you learn the policy $\pi(a \mid s)$, i.e. a probability distribution over actions given states, if you don't know the state you are in, this policy is quite useless.
To deal with the uncertainty about the state the agent is in, in POMDPs, we also have the concept of an observation, which is the information that the agent gathers from the environment about the current state (e.g., in the example of a blind guy, the observations would be the sounds, touch, etc.), in order to update its belief about the current state. In practice, some people tried to apply the usual RL algorithms for MDPs to POMDPs (see e.g. DQN or this), but they made a few approximations, which turned out to be useful and successful.
If the difference wasn't still clear, just take a look at the equation that can be used to relate the belief state and the transition model (dynamics) of the environment
$$
\underbrace{b^{\prime}\left(s^{\prime}\right)}_{\text{Next belief state}}=\alpha \underbrace{P\left(o \mid s^{\prime}\right)}_{\text{Probability of observation }o \text{ given }s'} \sum \underbrace{P\left(s^{\prime} \mid s, a\right)}_{\text{Transition}\\ \text{model}} \underbrace{b(s)}_{\text{Previous belief state}}
$$
So, in a POMDP, the policy, as stated above, in theory, cannot depend on $s$, but needs to depend on $b(s)$, the belief state, i.e. a probability distribution over states.
If this answer wasn't still satisfactory, although you probably already did it, you should read the section 2.3.2 Properties of task environments of the AIMA book (3rd edition). Their description of stochastic and partially observable environment seems to be consistent with what I wrote here, but maybe their description of a stochastic environment is not fully clear, because they say

If the next state of the environment is completely determined by the current state and the action executed by the agent, then we say the environment is deterministic; otherwise, it is stochastic

The unclear part is completely determined. They should have said deterministically determined (which you can use for a rap song).
However, they later clarify their definition by saying

our use of the word "stochastic" generally implies that uncertainty about outcomes is quantified in terms of probabilities

In addition to that, they call an environment that is either stochastic or partially observable uncertain. It makes sense to do this because uncertainty makes the problems harder, so we can differentiate between certain and uncertain environments.
To be honest, I don't know if there's some kind of mathematical formalism that doesn't differentiate between stochastic or partially observable environments, but I am not sure how useful it might be.

I think there is cross-over between stochastic and partially observable where state knowledge is partial but revealed without any impact/bias within the system. A good example to use is the difference between card games Blackjack (effectively stochastic, and no need to model as POMDP, even though you cannot see the dealer's hand or the non-revealed cards) and Poker (where hidden state of opponent's hands radically impacts results of actions non-randomly)

@NeilSlater I think if you elaborate on these examples (i.e. why they don't need to be modeled as POMDP), it may be a good answer, in addition to this canonical answer (let's say), which can be useful.

Dennis beat me to it and covered what I wanted to say :-)

A few points I'd like to add (without repeating the info already provided by nbro's answer):

I think you're half-right, in that indeed we can probably always model randomness as hidden information (e.g., as the hidden random seed in a software implementation of an environment). However, the other way around does not work; we can not always model any partially observable environment as a stochastic one!

So we probably have a subset relation here, not an equivalence relation. Personally, I often find stochastic environments to be somehow "easier" to handle than partially observable ones. So, it is generally beneficial to simply treat them as such, rather than unnecessarily casting them into the often-more-difficult format of partially observable environments.

In stochastic (but fully observable) environments, there always exists an optimal deterministic policy, but in partially observable environments an optimal policy may need to be non-deterministic. As a corollary, I would say that this indeed implies that there really is some fundamental difference between the two.

If an environment is just stochastic, but fully observable, non-deterministic policies may still also be optimal, but there is also always guaranteed to be at least one fully deterministic policy; a policy $\pi$ that, for any state $s$ assigns a probability of $\pi(a \mid s) = 1$ to just one action $a$ (and $0$ to any other action for that same state). Sometimes it may be fine to be indifferent (and distribute the probability mass over more than a single action), but this is never strictly required for optimality.
In a partially-observable environment, it is possible that an optimal policy must be non-deterministic. Consider this "drawing" of an environment, consisting of a few squares, with the current position of the agent labelled as $A$, and the position of the goal labelled as $G$. The possible actions are to move either left or right.
$$\square A \square \square G \square \square \square$$
Suppose that this environment is partially observable to the extreme extent that the agent never has any idea where it is, i.e. all states are aliased (look the same to the agent). A deterministic policy would then always go left or always go right, but, depending on whether the agent is currently to the left or to the right of the goal, one of those two deterministic policies would never reach the goal. And the agent has no way at all to tell which one would be the bad policy. The optimal policy in this environment is to simply go left with probability $0.5$, and go right with probability $0.5$. Eventually, the agent will get lucky and end up in the goal position. The partially observable nature of this environment really makes it necessary to follow a stochastic policy.

In partially observable environments, we often consider the possibility that there can be actions that allow us to obtain new information. These are not necessarily actions that directly lead to any rewards or future returns, but really only allow us to observe things that we could not observe before (and hence possibly allow us to, with more certainty, follow a better policy afterwards). This idea does not really exist in fully observable stochastic environments.

In multi-agent environments (consider, for example, many card games), other agents (often opponents but could also be agents with similar goals to our own) may have access to different information/observations from our own agent. This means that, for example through counterfactual reasoning or even explicit communication, we may gain full information or at least update our beliefs with respect to unobservable (to us) parts of the state. For example, based on the actions of an opponent in a card game, we may infer that it is very likely or very unlikely for them to have certain cards, because otherwise they very likely would not have acted in the way that they did. This sort of reasoning does not apply to fully observable stochastic environments.

Just one remark about your example of the POMDP. The agent still gets an observation from the environment in a POMDP. So, even if the policy is deterministic, it doesn't necessarily always go right or left, it can go right or left, depending on the observation it receives (if you define a policy as $\pi(a \mid o)$). However, if the observations are not informative, yes, I guess a deterministic policy has no way of saying "ok, now I need to go right, after I went left". In other words, in your explanation, it seems that you don't define a policy to be conditioned on $o$ or the belief state.

For the POMDP example, the agent can look at the history of its moves - its actions can be 1 square left, 2 squares right, 3 squares left, etc. I suppose in a more complicated environment the movement can be noisy so that the agent doesn't know how much it moved exactly. Then some form of randomness is necessary.

@martinkunev Sure, adding knowledge about the history can often help a little bit to deal with imperfect observations. For instance, in environments with pixel/image/camera-based observations (like Atari games), it is also common to augment the states with a few of the previous frames, because multiple frames combined can tell you about the velocities/directions in which objects are moving. But this may not always suffice (imagine a card game, or the blocks example above with an incredibly long chain of blocks such that after $100$ moves to the left you still don't know where you might be).

This answer is enlightening, but I have two follow ups: "We can not always model any partially observable environment as a stochastic one". Isn't the belief MDP a stochastic representation of the underlying POMDP (it just requires us to define the belief)? "As a corollary, I would say that this indeed implies that there really is some fundamental difference between the two." But the belief MDP does have a deterministic policy, in which case it actually suggests some equivalence? Can you help me square these issues?

@Snowball In the definition of a BMDP, we have the set of belief states $B$ replacing the set of states $S$. $B$ is typically much bigger than $S$ ($B$ is continuous and infinite even if $S$ is finite). In a POMDP the policy would still be defined like $\pi : S \times A \mapsto [0, 1]$, whereas in a BMDP it would be $\pi : B \times A \mapsto [0, 1]$. So, you're essentially assuming that you have a mechanism by which you are able to provide more detailed and fine-grained information as input to your policy, which recovers the ability to encode optimal deterministic policies.

That does assume that you actually have the ability to track and update belief states in a meaningful way though (which would typically consist of tracking and memorising relevant stuff from the history, as was discussed in previous comments above we could also do in POMDPs). In a pathological case where we gain no new information for our agent at all and deterministically map from observations to belief states, we would only actually use a small (discrete, probably finite) subset of $B$, and given this subset there may be no optimal deterministic policy.

@DennisSoemers It seems to me you're almost saying this comes down to an issue of intractability given practical computational limits (since B is the set of all distributions over S), and the distinction is relevant in an applied sense as we cannot just magically obtain correct beliefs. It does not seem like you're arguing that conceptually there is a meaningful difference between the two, would that be a fair characterization? i.e. If there was a powerful enough model to take histories to beliefs, would you agree the POMDP vs. stochastic MDP distinction would be less meaningful?

@Snowball No there still is a fundamental distinction. In the BMDP, which is no longer partially observable w.r.t. its belief state space $B$, we will indeed have a deterministic optimal policy. But that optimal policy is only optimal with respect to the beliefs. This will only map back to a policy that is optimal in the original POMDP if the beliefs are perfect (i.e. if beliefs have no uncertainty and assign full probability to the single correct state). If there is any uncertainty in beliefs at all, a policy that is optimal w.r.t. the BMDP may not be optimal w.r.t. the original POMDP.

And, if we assume that we are capable of building truly perfect belief states, I suppose it becomes debatable whether the original POMDP was ever really a POMDP instead of just an MDP to begin with.


text:
Would it be possible to enforce the same $s_{t + 1}$ between the model's estimate and the target function's Q-value?
Say I have a game of blackjack, and I am trying to teach a single forward-pass neural network to approximate the Q value of the current state and action.
There are 3 inputs: The current card in hand, the cards in the deck, and the cards in the pile. It outputs the Q-value of two actions, namely, holding or adding the current card to the pile.
My loss function is $$L(Q,Q_E)=  \sum({Q(s,a_i)- Q_E(s,a_i) )^2},$$
where $Q_E$ is the estimated Q-value of the current state from the policy network. And $Q$ is the target function, which is calculated using the Bellman equation.
As I understand it, the Bellman equation assumes the setting to be deterministic, meaning that, if you're in state $s_t$ as you take action $a_1$, you should always reach the same $s_{t+1}$.
Of course, in blackjack, this is not the case, as the state $s_{t+1}$ is purely dependent on the card you draw, which is a stochastic process.
Would it be possible to omit some of this noise or "stochasticity" by enforcing the same $s_{t + 1}$ between the model's estimate and the target function's Q-value?
In other words, say we're in state $s_t$, and the target function picks action $a_1$ and draws a 10 reaching state $s_{10}$ as the next state. For the training of the policy network, it loads the state $s_t$ from the experience replay, it also picks action $a_1$ and draws a 7 reaching state $s_7$ as the next state.
Would it somehow ruin the training, if I then just hardcoded it, such that the next state reverted to state $s_{10}$ if the policy network picked action $a1$? Are there any counter-productive consequences to this?

As I understand it, the Bellman equation assumes the setting to be deterministic, meaning that, if you're in state $s_t$ as you take action $a_1$, you should always reach the same $s_{t+1}$.

This is not correct, which is a good thing for you. The Bellman equation for action values for an arbitrary policy $\pi(a|s): \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R} = \mathbf{Pr}\{A_t=a|S_t=s \}$ looks like this:
$$q_\pi(s,a) = \sum_{r,s'}p(r,s'|s,a)(r+\gamma\sum_{a'}\pi(s',a')q_{\pi}(s',a'))$$
The environment model in this equation is $p(r,s'|s,a)$ which is the probability of observing reward $r$ and next state $s'$, given current state $s$ and action $a$. This is stochastic.
When using a model-free approach learning from experience, you cannot use the full equation each time, because you only have one sample and do not know anything about $p()$. However, things will still work, because if you take many samples, on average they will follow the probability distribution for $p()$, and your update rule will converge to the average/expected return for each action value.
The same sampling also applies to the policy, which means the above Bellman equation can be expressed as:
$$q_\pi(s,a) = \mathbb{E}_{A_{t+1} \sim \pi}[R_{t+1} + \gamma q_{\pi}(S_{t+1},A_{t+1})|S_t=s, A_t=a]$$
which in turn means you can use samples of $r, s'$ and $a'$ (or for Q-learning, the maximising $a'$), and an update rule that averages between the values you observe. You can do this with both deterministic and stochastic environments, because the theory behind it works with both.

Would it somehow ruin the training, if I then just hardcoded it, such that the next state reverted to state $s_{10}$ if the policy network picked action $a1$? Are there any counter-productive consequences to this?

For some environments, and some setups of the hardcoding, it may work. However, you should not do this because it is not necessary, and in general it is a bad idea, as it may impact the sampling in a way that causes incorrect learning.

source: Stack Exchange

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

sort: votes


text:
What are knowledge graph embeddings?
What are knowledge graph embeddings? How are they useful? Are there any extensive reviews on the subject to know all the details? Note that I am asking this question just to give a quick overview of the topic and why it might be interesting or useful, I am not asking for all the details, which can be given in the reference/survey.

Knowledge graph embeddings (KGE) are embeddings created in the context of a knowledge graph (KG), which can be viewed as a visual/graphical representation of a knowledge base, where nodes are entities (e.g. "a car" or "Lewis Hamilton") and edges are relations between those entities (e.g. "drives"), so a (directed) connection from "Lewis Hamilton" to "a car" through the edge "drives" would represent the fact "Lewis Hamilton drives a car".
A KGE is a vector representation of an entity or relation in the KG that, hopefully, preserves the semantics of the entities and relations. For example, we expect the embedding of the entity "man" to be closer to the embedding of the entity "woman" than to the embedding of a "turtle". The idea of learning a lower-dimensional vector representation of objects that preserves some notion of semantics or meaning between those objects also appears in other AI subfields, like natural language processing (see e.g. word embeddings), or ML applied to software engineering (see code embeddings).
A KGE can be useful because a KG is most likely incomplete, so one of the tasks that you need to solve when using a KG is determining whether a fact is true or false. So, if we denote the fact as a triple $f = \langle s, r, o \rangle$, where $s$ stands for the subject, $r$ for the relation, and $o$ the object, then we want to determine whether this fact $f$ is true or false. In the context of KGEs, this is known as triple classification. Of course, in our KG, we don't have the fact $f$, but maybe we have the entities $s$ and $o$ but there's no edge between them that is labeled with $r$. So, given the embeddings of $s$, $r$, and $o$ (which was previously learned), we can then use a so-called score function to determine the likelihood of this fact. So, KGEs can be used to discover new "likely" knowledge, but it's a different approach than using deduction to derive new knowledge from a set of axioms or facts. It's an inductive/probabilistic approach, which has advantages (e.g. you don't need a deductive system) but also disadvantages (e.g. the fact may not actually be true even if our approach tells us that's the case).
There are many similar/related ways to learn KGEs. Just to give you an idea of how these are learned, a simple approach (TransE) is as follows. You learn the vectors $s$, $r$ and $o$ such that the constraint $s + r = o$ is satisfied. Of course, this constraint only makes sense if $o$ can only go with $s$ and $r$, so this approach is not realistic, as it doesn't model e.g. many-to-many relations. For this reason, people have introduced other approaches (like RotatE or ConvE), which have advantages but also disadvantages. There are also other issues that arise when learning these embeddings, like generating synthetic negative/false facts (i.e. if you have a KG, you only have known true facts, so how do you know if a fact is false? You need examples of false facts!).
The Wikipedia page on KGEs is already quite comprehensive, but there are many other resources on the topic. For example, the survey Knowledge Graph Embedding: A Survey of Approaches and Applications (2017) or the (long but very useful) tutorial Knowledge Graph Embeddings Tutorial: From Theory to Practice by some of the people that are currently doing research on this topic.

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


text:
Are there any resources that introduce the basics of online machine learning?
Are there any resources (either books, articles, or tutorials) that introduce the basics of online machine learning?
For example, this website has nice lecture notes (from lec16) on some of the aspects. Or this book.
I can't seem to find many resources on this. I'm trying to understand the basics, not read research papers.

Although you don't seem to want to read papers, you should be able to follow the first pages of the following two papers, if you are familiar with the basics of machine learning (ML).

Online learning: A comprehensive survey (2019) by Steven C. H. Hoi et al.

Online Learning and Online Convex Optimization (2011), by Shai Shalev-Shwartz

So, after having read these initial pages, you should have an overview of what online learning is. After that, you can dive into the details, if you think that you have the knowledge to understand them. Otherwise, you should probably pick an introductory ML book.

Duplicate of answer previously posted on DataScience.SE:
On-line learning algorithms trains new data as it arrives. It is often referred to as incremental learning or continuous learning as it trains continuous stream of data incrementally
As requested some resources in the form of books, tutorial, lecture notes, YouTube links, pdf documents along with available packages that support online learning algorithms are mentioned
BOOKS

Online Algorithms: The State of the Art
Online learning and Online convex optimization
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
Convex Optimization: Algorithms and Complexity
Introduction to
Online Convex Optimization
Introduction to Online Optimization

TUTORIAL

An Introduction To Online Machine Learning
A Simple Introduction to Online Machine Learning
Beginner’s Guide to Online Machine Learning
what is online machine learning
Online Machine Learning Wikipedia
Online learning simplified

LECTURE

Online Methods in Machine Learning
Theory and Applications
Coursera lecture on online machine learning

YOU TUBE

Introduction to online machine learning algorithms
what is Online Machine learning
Online Machine learning with creme

PDF

Online Learning:
Theory, Algorithms, and Applications

Online Learning: A Comprehensive Survey

14 chapter on-line learning algorithms in machine learning

Utilisation of on-line machine learning for SCADA system alarms forecasting

Online Machine Learning Algorithms Review and Comparison in Healthcare

ONLINE LEARNING ALGORITHMS

Vowpal Wabbit : provides support for reinforcement learning and supervised learning

Creme

Scikit-multiflow

River - online machine learning python package that combines python packages creme and scikit-multiflow

LIBOL: A Library for Online Learning Algorithms

Quasi-additive Online Classification Algorithms

Game Theory, on-line prediction and boosting Freund and Schapire relates boosting algorithms to online learning(Adaboost)

Note that I didn't even know that your answer existed on another site. I didn't even know that this question had also been asked on Data Science. So, I didn't copy from your answer, so I didn't plagiarise you, as you're attempting to demonstrate (with your flagging). In addition to that, you're not the author of those papers. Even if I had read your answer on the other site (which did not happen, again!), my answer is completely different from yours. Plagiarism happens you copy and paste and don't give proper attribution, which is not the case at all.

By the way, you flagged my answer as plagiarism, while, in reality, it seems that you copied and pasted the sentence "It is called online machine learning because the ML programming must be connected to a network that provides a dynamic input stream." from https://www.techopedia.com/definition/32818/online-machine-learning. If you don't edit your answer to give proper attribution to the author of that sentence, this answer, as much as it can be useful, will be deleted, as plagiarism is not allowed here.

In addition to that, you also copied "Vowpal Wabbit provides fast, efficient, and flexible online machine learning techniques for reinforcement learning, supervised learning, and more" from https://vowpalwabbit.org/

This answer was partially copied from sources without attribution, so this is considered plagiarism (which is forbidden and subject to deletion), so I deleted it. To fix that and if you think your answer should be undeleted, remove the copied parts and vote to undelete it.


text:
Does higher FLOPS mean higher throughput?
I understand that FLOPS means floating-point operations per second, and throughput is the number of inputs (for example, images) per second. If a model has higher FLOPS, it means it performs faster.
However, in the article Container: Context Aggregation Network, they show that:

The container has higher FLOPS and less throughput, while the container-light has lower FLOPS and higher throughput.
What is the reason for that?

In the context of Deeplearning:

FLOPS: Floating Point Ops per Second
FLOPs: Floating Point Ops

FLOPS, refers to the number of floating point operations that can be performed by a computing entity in one second. It is used to quantify the performance of a hardware.
FLOPs, simply means the total number of floating point operations required for a single forward pass. The higher the FLOPs, the slower the model and hence low throughput.
This thread on stack overflow might help to get a deeper insight:
https://stackoverflow.com/questions/58498651/what-is-flops-in-field-of-deep-learning


text:
Why is the effective branching factor used for measuring performance of a heuristic function?
For search algorithms with heuristic functions, the performance of heuristic functions are measured by the effective branching factor ${b^*}$, which involves the total number of nodes expanded ${N}$ and the depth of the solution ${d}$.
I'm not able to find out how different values of ${d}$ affect the performance keeping the same ${N}$. Put another way, why not use just the ${N}$ as the performance measure instead of ${b^*}$?

I also walked into that trap the first few times. The difference is the following:

$N$ is the number of expanded nodes
$b^*$ is the effective branching factor

$b^*$ depends on the depth $d$ of the goal and the number of generated nodes, lets call that $M$
$b^*$ is the solution to $M+1=1+b^*+(b^*)^2+(b^*)^3+...+(b^*)^d$

So, you could argue that instead of comparing $b_1^*$ and $b_2^*$ of two algorithms, you can also directly compare $M_1$ and $M_2$, because $b_1^*>b_2^*\Leftrightarrow M_1>M_2$.
But you can imagine an algorithm $A_2$ that expands fewer nodes than $A_1$ (so $N_1>N_2$), but also different nodes so that it generates more nodes (so $M_1<M_2$).
Since the cost is defined by the number of generated nodes, comparing $N$ might give the wrong result.
The effective branching factor is more general than the number of generated nodes, because you can average $b^*$ for one algorithm over many search problems, but averaging over the number of nodes (which might differ greatly) is not possible or rather nonsensical.

Averaging over different sizes of the “same” search problem (e.g., N-queens with different Ns) seems to be the motivation. Otherwise, the number of generated nodes are a superior measure.

Why is it M+1 in the formula? (Instead of the plain M)

@HappyFace The "+1" is the root node which is not generated by the search algorithm. It already exists at the beginning. Technically, the "1+" on the right side is also the root node and could be omitted, but with "1+" the right side becomes a geometric series and can be simplified

As you found $N$ is the number of nodes that are expanded. The cost of expansion of each node is equal to the number of children of that node. Hence, we use $b^*$ for each node. In other words, the total number of nodes that are involved in the expansion process is $N \times b^*$.

@ OmG - Why not ${N}$ since you agreed that the cost solely depends on ${N}$?

@KGhatak because the total number of expanded node is $N \times b^*$.

@ OmG - Not sure if this is the right understanding. Can you provide some reference for it! Just think, we calculated expected ONLY when we don't know for sure. If we know actual N, there is no need to estimate/guess (aka Expected value of) N. What say!

@KGhatak Unfortunately I don't know which part is confusing for you. In the search, we expand $N$ nodes, and each node has $b^$ children at most. Hence,  the complexity is related to $N$ and $b^$. Now, suppose we do not apply $b^$ in the complexity, and another algorithm try to search and expand $N$ nodes to find the solution, but the branching factor of the current algorithm would be $2^{b^}$! Which of them will be a better algorithm in terms of complexity?

@ OmG - Let me put it in a different way. Two algorithms, say 1 and 2, try to solve a problem. Their respective values are ${N_1}, {b_1^}, {N_2}$, and ${b_2^}$ such that ${N_1b_1^}={N_2b_2^}$. Which algorithm is efficient given ${N_1>N_2}$. Would you pls explain!


text:
How is $Q(s', a')$ calculated in SARSA and Q-Learning?
I have a question about how to update the Q-function in Q-learning and SARSA. Here (What are the differences between SARSA and Q-learning?) the following updating formulas are given:
Q-Learning
$$Q(s,a) = Q(s,a) + \alpha (R_{t+1} + \gamma \max_aQ(s',a) - Q(s,a))$$
SARSA
$$Q(s,a) = Q(s,a) + \alpha (R_{t+1} + \gamma Q(s',a') - Q(s,a))$$
How can we calculate the $Q(s', a')$ in both SARSA and Q-learning for updating the Q-function? After having taken an action $a$ at state $s$, we get the reward $r$, which we can observe. But we cannot observe $Q(s',a')$ from the environment as far as I see it.
Can anyone maybe think about a comprehensive example where you can see how it is done (or a link to a website)?

I have deleted my answer as it did not answer your question. Reading the first few chapters of Sutton&Barto may help you a lot, it covers the details that you are currently studying. A free version, provided by one of the authors, can be found at http://incompleteideas.net/book/RLbook2020.pdf

Can you explain why the deleted answer doesn't answer your question? Did you understand that, when performing the update in SARSA, we do not really compute $Q(s', a')$, but we just use the estimate that we have saved in our table or neural network $Q$? If you understand that, then what's your question? Having said that, there are 2 questions. If you wanted to consider your doubts clarified only if people answer the 2 questions, that's not good. You should ask the other question about the example in another post.

@nbro: Thanks for your comment.You wrote "Did you understand that, when performing the update in SARSA, we do not really compute $Q(s′,a′)$, but we just use the estimate that we have saved in our table or neural network Q?" --> Actually I do not understand this. How can we estimate $Q(s′,a′)$? After having taken an action $a$ at state $s$, we get the reward $r$, which we can observe. But now my question is how to derive $Q(s′,a′)$ out of it? As far as I understand $Q(s′,a′)$ is the Q value of the next state $s'$. When we are at time $t$ how can we estimate the value of time $t+1$?

It seems that your problem is that you think that we must know the true value of $Q(s', a')$ in order to perform the SARSA update. This is not the case! SARSA is a reinforcement learning algorithm, not a supervised learning algorithm (although you can also view RL as a form of SL).
If you are familiar with supervised learning (SL), then you know that, to train a model, you need the ground-truth labels. The typical SL example is that of binary classification of dogs and cats. So, you are given an image of a dog or cat $x$, you pass it to your neural network $f$, which produces a prediction $\hat{y} = f(x)$. Now, if $x$ is a dog but $\hat{y}$ is cat, the neural network $f$ made a mistake. So, we need to change the weights of this model so that $\hat{y} = \text{dog}$ when $x$ is an image of a dog (of course, this reasoning also applies to the case when $x$ is an image of a cat). A typical way to solve this problem in SL is to use a loss function that computes some notion of distance between $\hat{y}$ (the prediction) and $y$ (the true label). The usual loss function, in this case, is the binary cross-entropy, but you don't need to know the details now.
In reinforcement learning, you don't really have ground-truth labels, but you have experience, which is just the tuples $\langle s_t, a_t, r_{t+1}, s_{t+1} \rangle $, where

$s_t$ is the state of the agent/environment at time step $t$
$a_t$ is the action that the agent takes at time step $t$ in state $s_t$
$r_{t+1}$ is the reward the agent receives after having taken action $a_t$ in $s_t$; this reward indicates how good that action is, but it doesn't tell whether you took the correct/optimal (or ground-truth) action or not (this is the main difference between reinforcement learning and supervised learning!)
$s_{t+1}$ is the state the agent ends up in after having taken $a_t$ in $s_t$.

Now, in reinforcement learning, there are many problems that you may want to solve. However, the main goal of an RL agent is to maximize expected reward in the long run (known also as expected return), so you could say that your objective function is $$\mathbb{E} \left[ \sum_{t=0}^\infty R_t \right],$$
where $G = \sum_{t=0}^\infty R_t$ is the so-called return (i.e. the cumulative reward or reward in the long run). The goal is to maximize this expectation.
In practice, what you do is ESTIMATE a so-called (state-action or just action) value function. In the case of SARSA, it's defined as $q: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$, where $\mathcal{S}$ and $\mathcal{A}$ are respectively the set of states and actions of the environment (aka MDP).
Why do you want to estimate a value function? In the case of $q$ (so SARSA and Q-learning), $q(s, a)$, for some $s \in \mathcal{S}$ and $a \in \mathcal{A}$, is defined as the expected cumulative reward that you will get from taking action $a$ in the state $s$. So, if you know that you will get more reward by taking action $a_1$ rather than action $a_2$ in state $s$, then $q(s, a_1) > q(s, a_2)$, so you will take action $a_1$ when in state $s$. In fact, you can also define $q(s, a)$ as follows $q(s, a) = \mathbb{E}\left[ G \mid s, a \right]$, where $G$ is our cumulative reward, aka return (for simplicity, I ignore a few details).
HOWEVER, we do not (usually) know $q$. That's why we need Q-learning and SARSA, i.e. to estimate the state-action value function. So, in SARSA, you know $s'$ and $a'$ (read the pseudocode!), but we do not know the true value of $q(s', a')$. So, you say, but then why do we use it in the update of SARSA?
The reason is: initially, SARSA uses possibly wrong estimates of $q$ to learn $q$ itself. We denote these estimates with the capital letter $Q$. So, we don't know the true value of $a'$ in $s'$. Or, more precisely, at the beginning of SARSA, if $q$ is implemented as a 2d array (or matrix), then $Q[s', a']$ is not a good estimate of the true value of $a'$ in state $s'$, i.e. $q(s', a')$. In other words, $Q[s', a'] \approx q(s', a')$.
Now, you ask: why can we use a possibly wrong estimate, $Q(s', a')$, to compute $Q(s, a)$ (another estimate)? The idea of using possibly wrong estimates of the state-value function to update other estimates of the value function is present in all temporal-difference algorithms (including Q-learning): this is called bootstrapping. However, the specific reason why tabular SARSA converges to the true estimates is a different (although related) story (more info here).
Now, if you didn't understand this answer, then you really need to pick up a book and read it carefully from the beginning. It takes time to understand RL at the beginning, but then it becomes easy. The most common textbook for RL is Reinforcement Learning: An Introduction by Sutton and Barto. You can find other books here.

Thanks a lot for this answer and your effort. I really appreciate it. Actually I understand everything until the estimation of the $Q$ by using bootstrapping. This is also the core of my question (and the problem is not as you assumed that I "think that we must know the true value of $Q(s′,a′)$ "). Where do we get these possibly wrong estimate, $Q(s′,a′)$, to compute $Q(s,a)$ from. I know that in TD learning you don't wait until the full reward at the end but you get a reward after every time step. But what I don't understand is how I can estimate or calculate the $Q(s′,a′)$ values

@PeterBe Let's say that you have 2 states and 2 actions. So, you can represent $Q$ as $2 \times 2$ matrix. So far, do you understand? Now, in SARSA, we initialise this matrix randomly. So, $Q[s', a']$ is initially a random number. So, this "estimates" are random numbers at the beginning. Then they are updated using the SARSA algorithm, the more experience (aka tuples) we get. Do you understand now?! If you don't understand this, read the book. Alternatively, just simulate the SARSA algorithm yourself. Take a $2 \times 2$ matrix and simulate it by hand.

Thanks for the comment nbro. I think I need to have a look at an example to see how it fully works (before I can simulate it on my own). But with your comment I can at least somehow imagine how it works. So I accepted and upvoted your answer.

@PeterBe Feel free to ask another separate question like "Given a 2x2 matrix that represents Q (so there are 2 states and 2 actions), can you simulate how SARSA would update the values of Q". Maybe, before asking, this question, try to do it yourself and tell us where you are stuck.


text:
What is a generalized MDP?
What is a generalized MDP?
Here are a few sub-questions.

How is it different than a "regular" MDP?
How does it generalize the notion of an MDP?
Why do we need a generalized MDP?
Do generalized MDPs have some practical usefulness or they are just theoretical tools?

(This answer is based on info that you can find in the paper $\varepsilon $-MDPs: Learning in Varying Environments, 2002, by István Szita et al. and [Szepesvári and Littman(1996)], the paper that proposed generalised MDPs. I just adapted the notation to be more consistent with Sutton & Barto's book and provided additional info and links).
What is an MDP?
Let's first start with the usual definition of an MDP.
An MDP is defined by the tuple $\langle \mathcal{S}, \mathcal{A}, R, \color{blue}{P} , \gamma \rangle$, where

$\mathcal{S}$ is the set of states
$\mathcal{A}$ is the set of actions
$R: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R}$ is the reward function; so $R(s, a, s')$ is the reward for taking action $a \in \mathcal{A}$ in state $s \in \mathcal{S}$ and ending up in $s' \in \mathcal{S}$.
$\color{blue}{P}: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow [0, 1]$ is the transition model; so $\color{blue}{P}(s, a, s')$ is the probability of arriving in state $s'$ after having taken action $a$ in the state $s$. You could also define the transition model to include the reward, denoted by $\color{blue}{P}(s', r \mid s, a)$ to emphasize that it's a conditional probability distribution), but let's ignore this for now.
$0 \leq \gamma < 1$ is a discount factor, which can be useful for infinite-horizon problems

Given this formulation of a decision problem, the goal is to maximize the expected reward. The objective function can be defined as follows
$$
\mathbb{E}\left[ \sum_{t=0}^{\infty} \gamma^{t} R_{t} \right] = \mathbb{E}\left[ G_{t} \right],
$$
where $R_{t}$ is the reward that we get at time step $t$.
There are multiple ways to solve this problem. The most common is probably Q-learning.
Q-learning
In Q-learning, we try to estimate the state-action (or action) value function. The optimal value function is defined as follows
$$
Q^{*}(s, a)=\sum_{s'} \color{blue}{P}(s, a, s')\left(R(s, a, s')+\gamma \color{red}{\max} _{a^{\prime}} Q^{*}(s', a^{\prime})\right) \label{1}\tag{1},
$$
for all $s \in \mathcal{S}$.
So, it's a function of the form $Q^{*}: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$. To emphasize the main purpose of this function, it can be denoted/defined as $Q^{*}(s, a) = \mathbb{E}\left[G_t \mid a, s \right]$, so it's the expected return ($G_t$ is the return or cumulative reward) for taking action $a$ in state $s$ under the optimal policy $\pi^*$ (hence the $*$).
The equation (\ref{1}) is a recursive equation because $Q^{*}(s, a)$ is defined in terms of itself, i.e. we use $Q^{*}(s', a^{\prime})$ to define it. In this context, this type of recursive equation is also known as Bellman equation (due to Richard Bellman, who contributed to the theory of dynamic programming, which is related to MDPs, as dynamic programming algorithms can be used to solve MDPs, given a transition model).
One thing to keep in mind is that the optimal policy can be derived from the optimal state-action value function by acting greedily with respect to it.
What is a Generalized MDP?
Now, there's one reason why I colored the transition model and the max operation in the Bellman equation \ref{1} in $\color{blue}{\text{blue}}$ and $\color{red}{\text{red}}$, respectively, and this is related to generalized MDPs.
The Bellman equation in \ref{1} is defined with respect to

the transition model $\color{blue}{P}$, which describes the dynamics of the environment,

$\color{red}{\max}$, which is related to the assumption that the optimal agent acts greedily with respect to the optimal value function (keep in mind that the max operation is non-expansive)

A generalised MDP [Szepesvári and Littman(1996)] is a generalisation of multiple versions/definitions of MDPs that circulate around in the literature, including the definition above. More specifically, 2 concepts are generalised: transition model and the max operator.
Mathematically, we can define a generalised MDP as a tuple $\langle \mathcal{S}, \mathcal{A}, R, \color{blue}{\oplus}, \color{red}{\otimes}, \gamma \rangle$, where $\mathcal{S}, \mathcal{A}$ and $R$ are defined as above and

$\color{blue}{\oplus}: (\mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R}) \rightarrow(\mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R})$ is a "expected value-type" operator that generalises $\color{blue}{P}$; the intuition of this operator is the same as the input of $\color{blue}{P}$ that I described above

$\color{red}{\otimes}:(\mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}) \rightarrow(\mathcal{S} \rightarrow \mathbb{R})$ is a "maximization-type" operator that generalises $\color{red}{\max}$; the intuition of $\color{red}{\otimes}$ is also the same as the intuition of $\color{red}{\max}$ (i.e. it represents how the optimal agent would behave).

So, these are operators (like the gradient operator or the Bellman operator) because they take as input a function and produce another function.
Now, if we set

$(\color{blue}{\oplus} U)(s, a)=\sum_{s'} \color{blue}{P}(s, a, s') U(s, a, s')$ (so, in this case, it takes as input the function $U$; note that, in this case, $\color{blue}{\oplus}$ is an expected value operator, with respect to the probability distirbution $\color{blue}{P}(s, a, s')$)

$(\color{red}{\otimes} Q)(s)=\color{red}{\max}_{a} Q(s, a)$ (note that this just uses the $\color{red}{\max}$)

Then we get the usual expected-reward MDP model.
What are the advantages of Generalised MDPs?
In the literature, there are different versions of MDPs, such as

Markov games [Littman(1994)]
alternating Markov games [Boyan(1992)]
discounted expected-reward MDPs [Watkins and Dayan(1992)]
risk-sensitive MDPs [Heger(1994)]
exploration-sensitive MDPs [John(1994)]

Generalised MDPs generalise all these MDPs for different values of $\color{blue}{\oplus}$ and $\color{red}{\otimes}$.
The paper [Szepesvári and Littman(1996)] (that introduced GMDPs) provides more info about how we should set $\color{red}{\otimes}$ and $\color{blue}{\oplus}$ to get these different MDPs (see table 1).
Bellman equations in Generalised MDPs
The Bellman equation for the state value function can be expressed as follows in the context of GMDP
$$
V^{*}=\color{red}{\otimes} \color{blue}{\oplus} \left(R + \gamma V^{*}\right)
$$
For the state-action value function, you can have the following Bellman equation
$$
K Q=\color{blue}{\oplus} (R+\gamma \color{red}{\otimes} Q)
$$
or the one that relates $Q^{*}$ to $V^{*}$
$$
Q^{*}=\color{blue}{\oplus} \left(R+\gamma V^{*}\right)
$$


text:
What does "Gau" in GauGAN stand for?
GauGAN is a neural network architecture from NVIDIA that can create realistic images from semantic maps (and nowadays also textual descriptions).

As you know, GauGAN is the following (from this post):

GauGAN was a Microsoft Paint-style platform that let uses create landscape images, with the model then able to turn them into photorealistic images.

So, it is a generative adversarial network (GAN) to create images. As it works like an artist, its authors named it GauGAN after "Paul Gauguin" who was a French Post-Impressionist artist (refer into this post).


text:
What components of reinforcement learning influence the result the most?
I'm working on my thesis concerning a reinforcement learning problem and am trying to prioritise my time on different components of it:

Formalising the agent environment (like the design of state-, action-space and reward-structure)
Selection of learning algorithm
Selection of network architecture and size
Design of the training setup

It is an agent in a 3D environment with simulated physics (in Unity), the domain being a real-time strategical game. It is an environment with constraint training data, so sample efficiency is very important.
Now my question: I do anticipate that the design of the state- and action space will have a big impact on the training result, especially in this environment with little training data.
However, is there a way one can clearly prioritise what components will be the most important ones for an RL setting?
Time is limited, and, for me, as a beginner, it seems to be quite difficult to determine what component will be the most important one and needs the most focus. Testing only the hyper-parameters of a learning algorithm thoroughly will take in itself a long time. And obviously disregarding any component will result in bad results.
Is there a way to know on which component one should focus more?

I don't think there's a strategy that applies to all cases. In some cases, the reward function may need to be carefully designed (e.g. a self-driving car), but, in other cases, the reward function might be quickly designed (e.g. chess) and other parts of the RL system may require more care.
Here you can find tips to approach an RL problem. For example, one tip that I find useful, although probably obvious once you hear of it, is to compare your policy with a random policy. See also these tips.

I wanted to infer the amount of time spent for each component by some literature, but this seems not to work out then. Anyway, the links you provided are very useful for designing the task, thank you very much!


text:
For the VAE, should the input, output and latent variable code be random variables?
For a variational autoencoder, we have input $x$ (assume 1 data point for now, like an image), a latent code sampled from the decoder, $z$, and an output $\hat{x}$.
If I were to draw a diagram for the VAE with the input, output, and latent code sample, is it appropriate to write those three as random variables/vectors? Or as instances of random variables/vectors?
I thought it was random variables/vectors, but I saw this discussion, where they talk about the dataset being instances.

The VAE attempts to model a specific probabilistic (directed) graphical model (Bayesian network)

So, in this PGM, $\mathbf{z}$ and $\mathbf{x}$ are random variables. In principle, I think you could also model $\phi$ and $\theta$ as random variables (in Bayesian statistics, you can also model parameters as random variables and put priors on them).
In practice, the VAE attempts to learn a generative model given a dataset. In fact, the technical part of the VAE paper (section 2.1) starts with

Let us consider some dataset $\mathbf{X}=\left\{\mathbf{x}^{(i)}\right\}_{i=1}^{N}$ consisting of $N$ i.i.d. samples of some continuous or discrete variable $\mathbf{x}$. We assume that the data are generated by some random process, involving an unobserved continuous random variable $\mathbf{z}$.

Later, they use this dataset to define the likelihood
$$\log p_{\theta}\left(\mathbf{x}^{(i)}\right)=D_{K L}\left(q_{\phi}\left(\mathbf{z} \mid \mathbf{x}^{(i)}\right) \| p_{\theta}\left(\mathbf{z} \mid \mathbf{x}^{(i)}\right)\right)+\mathcal{L}\left(\boldsymbol{\theta}, \boldsymbol{\phi} ; \mathbf{x}^{(i)}\right)$$
and, consequently, also the objective function (the Evidence Lower BOund, aka ELBO).
$$
\mathcal{L}\left(\boldsymbol{\theta}, \phi ; \mathbf{x}^{(i)}\right)=-D_{K L}\left(q_{\phi}\left(\mathbf{z} \mid \mathbf{x}^{(i)}\right) \| p_{\theta}(\mathbf{z})\right)+\mathbb{E}_{q_{\phi}\left(\mathbf{z} \mid \mathbf{x}^{(i)}\right)}\left[\log p_{\theta}\left(\mathbf{x}^{(i)} \mid \mathbf{z}\right)\right]
$$
Note that we use $\mathbf{x}^{(i)}$ in the formulas above, so the distributions are conditioned on the given samples/dataset and the likelihood function is defined in terms of the samples (that's what a likelihood usually is: a function of the parameters given the usually fixed data).
In the other more extensive paper about VAEs (by the same authors of the VAE), you also have a diagram of the VAE.

So, I think an answer to your question depends on what you actually want to show with the diagram. If you want to show how VAEs are trained, then you definitely need to show that we have a dataset. If your diagram is supposed to show the distributions that the VAE attempts to model, then you can probably use a PGM.

So like when we are sampling from the encoder, we use the reparameterization trick, $\epsilon \sim p(\epsilon)$, $z=\mu+ z\odot \sigma$, and then input $z$ into the decoder. As far as I know, when we are sampling from a distribution, like $\epsilon \sim p(\epsilon)$, $\epsilon$ is a random variable/vector, and then . Is there some point along the way that we start treating it (either $\epsilon$ or $z$) as an instance instead of a random variable/vector?

@a12345 Before you sample, you can think that there's a random variable $\epsilon$ that follows a distribution $p$. Once you sample $z$ using the re-parametrization trick, you can think of it as a real data sample/instance. I think that people talk about random variables a little bit imprecisely in machine learning. Sometimes, they might say that $\epsilon$ is a random variable because it was randomly sampled from a distribution. What we can say is that, once we sample $z$, which we pass to the decoder, $z$ is no more a random variable, it's a (random) sample, i.a. sample chosen randomly.

Note that, in my comment above, I used the letter $\epsilon$ once to refer to a random variable and other times to refer to a sample from that probability distribution associated with that random variable.


text:
Are we choosing the same action in every step in SARSA?
Here is the pseudocode for SARSA (which I took from here)

Do we only select one action at the very beginning and then we always choose the same action for each step? Does it really make sense to choose the same initially chosen action $a$ regardless of the state $s$?

Do we only select one action at the very beginning and then we always choose the same action for each step?

No.
The pseudocode is clear on this, by using the word Choose and referencing a policy.
If you were expected to take the same action again, then the pseudocode already has the previous action in variable a, so it would not need to state anything about making a choice or using a policy.
The $a \leftarrow a'$ notation is common way to describe copying values*, so the variable a is changed at the end of each loop.

Does it really make sense to choose the same initially chosen action $a$ regardless of the state $s$?

Not in this case. Some learning algorithms do use a form of "sticky" exploration where a single exploratory action is committed to for multiple time steps. It can be useful in some environments. But not basic SARSA as described in the question.

* It avoids the ambiguity of $=$ as assignment or equality operator. You may also see $:=$ for assignment as an alternative, but for instance Sutton & Barto use $\leftarrow$ consistently, and a lot of RL literature follows this convention.


text:
How to uniquely associate a directed graph with a feedforward neural network?
I want to write an algorithm that returns a unique directed graph (an adjacency matrix) that represents the structure of a given feedforward neural network (FNN). My idea is to deconstruct the FNN into the input vector and some nodes (see definition below), and then draw those as vertices, but I do not know how to do so in a unique way.
Question: Is it possible to construct such an algorithm, and if so, how would you formalize it?

Example [Shallow Feedforward Neural Network (SNN)]
To illustrate the problem, consider an SNN, defined as a mapping $f=\left(f_1(\mathbf{x}), \ldots, f_m(\mathbf{x})\right): \mathbb{R}^n\rightarrow\mathbb{R}^m$ where for $k=1,\ldots,m$
\begin{align}
        f_k(\mathbf{x}) &= \sum_{j=1}^{\ell} w_{j,k}^{(2)} \rho \left( \sum_{i=1}^n w_{i,j}^{(1)} x_i + w_{0,j}^{(1)} \right) + w_{0,k}^{(2)}, \quad \mathbf{x}=(x_1,\ldots,x_n)\in\mathbb{R}^n
\end{align}
and $w_{i,j}^{(k)}\in\mathbb{R}$ is fixed for all $i,j,k \in \mathbb{N}$ and $\rho:\mathbb{R}\rightarrow\mathbb{R}$ is a continuous mapping.
I want to determine the nodes that make up the FNN, where a node $N^{\rho}: \mathbb{R}^n\rightarrow\mathbb{R}$ is defined as a mapping
\begin{align} \label{eq:node}
        && \quad && N^{\rho}(\mathbf{x}) &= \rho\left(\sum_{i=1}^n w_i x_i + w_0 \right), & \mathbf{x}=(x_1,\ldots,x_n)\in\mathbb{R}^n
\end{align}
where $\mathbf{w}=(w_0, \ldots,w_n)\in\mathbb{R}^{n+1}$ is fixed.
Clearly (to me) I can write each $f_k$ as
\begin{align}
    f_k(\mathbf{x}) &= \sum_{j=1}^{\ell} w_{j,k}^{(2)} N^{\rho}_j(\mathbf{x}) + w_{0,k}^{(2)},
\end{align}
where $N^{\rho}_{j}$ is a node for $j=1,\ldots,\ell$. Now I see that $f_k$ is a node which takes as input the output of other nodes. But how can I formalise this in an algorithm? And does it generalize to Deep Feedforward Neural Networks?

I'm not sure what you're asking here. You say the output of the algorithm should be a graph, while the inputs are FNNs. But isn't a neural network already a graph? Do you want the algorithm to produce, for example, an adjacency matrix?

The input should be a function (specifically an FNN) and the output should be a set of vertices and edges.
My problem is that I informally consider neural networks as graphs, but in my project, I have defined neural networks as a class of functions. Now I want to formally associate a graph with a given neural network.

What should the edges be? Should they just represent the connectivity? So, are you effectively looking for an adjacency matrix that represents the neural network's connectivity between the neurons? Or maybe the edges should have weights? If yes, which ones?

Exactly, the edges should just represent connectivity, so an adjacency matrix is sufficient.

I think you can do this in multiple ways.
The easiest algorithm that comes to my mind right now produces a sparse (which is also some kind of block matrix) $N \times N$ adjacency matrix for a typical MLP/FFN with a total of $N$ neurons (including input and output neurons), where each neuron $n_l^k$ at layer $l$ has a directed edge that goes into all neurons at layer $l+1$.
This is the algorithm.

Create an $N \times N$ matrix $G \in \{0, 1\}^{N \times N}$ with zeros

Comment 1: $G_{ij}$ is the element of the matrix at row $i$ and column $j$.

Comment 2: Indices $i$ and $j$ start at $1$ and end at $N$

Comment 3: if we set $G_{ij} = 1$, then there's a directed edge from neuron $i$ to neuron $j$ (but not necessarily vice-versa: for that to be true, we would also need $G_{ji} = 1$)

Comment 4: we need to create a mapping between the indices $i$ and $j$ and the neurons in the neural network; this is done below!

Let $c(l)$ be the number of neurons at layer $l$

For each layer $l = 0, \dots, L - 1$

Comment 5: $l = 0$ is the input layer and $L$ is the output layer

For $k=1, \dots, c(l)$

Comment 6: for example, $n_l^k = n_2^3$ is the third neuron at the first hidden layer

Let $M = \sum_{h=0}^{l-1} c(h)$

Comment 7: $M$ is the number of neurons processed so far in the previous layers (excluding the neurons in the current layer)

$i = k + M$
For $t = 1, \dots, c(l+1)$

$j = t + c(l) + M$

$j$ is basically the index of the graph $G$ that corresponds to the neuron $t$ in the next layer $l+1$

Set $G_{ij} = 1$

Return the matrix $G$

The time complexity of this algorithm should roughly be $\mathcal{O}(L* {\max_l c(l)}^2)$. So, for example, for a neural network with 3 layers, 2 inputs, 5 hidden neurons, and 2 outputs, what would be the number of operations?

Ah, I see the idea! To directly associate the FFN $f$ with the graph, I would probably not count the neurons (since they do not appear in the formulation of $f$) but instead, count the non-zero weights (since I only want to draw edges if the weights are non-zero). Perhaps my problem formulation was unclear.
To answer your question, I guess the number of operations would be 20 (not counting the calculation of $M$, $i$, and $j$).

The algorithm above can also be applied to the case of non-zero weights (although note that maybe you will not have many exactly zero weights, with real-valued weights). Rather than setting $G_{ij}=1$ in all cases, you also check the weight of the connection. Of course, as you said, the number of neurons may not be in the formulation of the neural network, but this information should be retrievable from the implementation of the layers.

Exactly, it is just minor adjustments.
Regarding the note on non-zero weights: To clarify, I am writing a theoretical project on neural networks, so it does not matter if they are exactly zero.
Thanks for the algorithm!


text:
Why are we choosing more than 1 action in SARSA?
Here is the pseudocode for SARSA (which I took from here)

Why are we choosing more than 1 action in SARSA? One for going into the next state and the other one for updating the Q function?

Why are we choosing more than 1 action in SARSA?

There is never a state where more than one action is chosen.
The appearance of two Choose statements is an artifact of the loop design and variable management in the pseudocode.

One for going into the next state and the other one for updating the Q function?

Sort of. There is only ever one chosen action for each state.
However, you need to have two actions in scope - the current action (just taken and observed) and planned next action, in order to process the update rule. Hence there are two variables a and a' and the code needs to generate one or other outside the main loop, or have some other way to ensure that it has access to current and next values. This is also why at the end of the loop, the "next" values $s', a'$ get copied to the "current" values $s, a$.


text:
How to train an ML model to convert the given lyrics into a song by a particular singer?
I am interested in training a machine algorithm to convert the lyrics I give into a song by a particular singer.
My language is non-English (south Indian) The songs are mostly monophonic (very few instruments, if at all). I have data of a bunch of songs sung by this singer, I want to try new lyrics and imagine how to singer would have sung.

OpenAI used a modified version of VQ-VAE-2 combined with sparse transformers to do something similar to what you want to do. Their approach, called Jukebox, is able to produce music by conditioning on certain styles, lyrics, and artists, which you might explore to do what you want. You can explore here the produced songs. For example, the model was able to produce a hip-hop song that uses the lyrics of Eminem's Lose Yourself, but with a Kanye West's style. You can find the original research paper here and the associated codebase here.


text:
What is the meaning of the shaded area in the reinforcement learning literature graphs?
In most of the reinforcement learning literature, I see that there is a shaded area in the graphs. I couldn't understand what it exactly represents?
For example, from the A3C paper:

Or another example from the PPO paper:

Is it for multiple runs or it's for something else? How I can reproduce such graphs (which library and what type of data from my training episode do I need)?

They train the agent multiple times, then plot the mean +- standard deviation of the agent performance (the shaded region is representing the standard deviation).


text:
Why are logarithms used in GANs minimax equation?
The minimax equation for generative adversarial networks
$$\min_G \max_D V(D,G) = \mathbb{E}_{\boldsymbol{x}\sim p_{data}(\boldsymbol{x})}[\log D(\boldsymbol{x})] + \mathbb{E}_{\boldsymbol{z}\sim p_{\boldsymbol{z}}(\boldsymbol{z})}[\log(1 - D(G(\boldsymbol{z}))]  $$
Why do we use logarithms instead of just
$$\min_G \max_D V(D,G) = \mathbb{E}_{\boldsymbol{x}\sim p_{data}(\boldsymbol{x})}[ D(\boldsymbol{x})] + \mathbb{E}_{\boldsymbol{z}\sim p_{\boldsymbol{z}}(\boldsymbol{z})}[(1 - D(G(\boldsymbol{z}))]  $$

It's common in machine learning to do this log-trick, i.e. rather than optimizing $f(\mathbf{x})$, you optimize $\log f(\mathbf{x})$.
There are 3 main reasons why we (can) do this.

When your objective function is the product of multiple probabilities (or, more generally, small numbers), i.e. $f(\mathbf{x}) = \prod_{i=1}^N p(x_i)$, then $\log f(\mathbf{x}) = \log \left( \prod_{i=1}^N p(x_i) \right) = \sum_{i=1}^N \log p(x_i)$ (see this), which is more numerical stable because we got rid of multiplication of possibly very small numbers, which can lead to underflow.

For the same reason, we can also compute derivatives more easily, as we can simply compute the derivatives of each component (because derivatives are linear)

The logarithm is monotonically increasing, so $\log f(\mathbf{x})$ has the same optima as $f(\mathbf{x})$ (simple proof here).

Because Binary Cross-Entropy Loss is a commonly used loss function for binary classification problems in machine learning:
$$
L = - \frac{1}{N} \sum_{i=1}^{N} \left[ y_i \cdot \log(\hat{y_i}) + (1 - y_i) \cdot \log(1 - \hat{y_i}) \right]
$$

$N$ is the number of samples.
$y_i$ is the true label of the $i$-th sample (0 or 1).
$\hat{y_i}$ is the predicted probability for the $i$-th sample (i.e., the probability of predicting 1).

If the true label $y_i=0$, the loss is $\log(1 - \hat{y}_i)$, and similarly, if $y_i=1$, the loss is $\log(\hat{y}_i)$.
By dividing the samples based on their true labels, we arrive at the form used in GANs:
$$
\mathbb{E}_{\boldsymbol{x} \sim p_{\text {data }}(\boldsymbol{x})}[\log D(\boldsymbol{x})]+\mathbb{E}_{\boldsymbol{z} \sim p_{\boldsymbol{z}}(\boldsymbol{z})}[\log (1-D(G(\boldsymbol{z})))]
$$
As for why Binary Cross-Entropy Loss is chosen for binary classification problems, that is a broader question.
Additionally, it's important to note that GANs do not only train the discriminator but also the generator. The choice of such a joint optimization objective can be explained by the fact that the generator's optimization goal is to minimize the Jensen-Shannon (JS) divergence between the real data distribution $p_{\text{data}}$ and the generated data distribution $p_g$.
The original paper proves that when optimizing the discriminator $D$, fixing $G$, it becomes a maximization problem. The optimal solution for the discriminator is:
$$
D^*_G(\boldsymbol{x}) = \frac{p_{\text{data}}(\boldsymbol{x})}{p_{\text{data}}(\boldsymbol{x}) + p_g(\boldsymbol{x})}
$$
Substituting $D^*_G$ into $V(D, G)$ gives:
$$
V(D^*_G, G) = \mathbb{E}_{\boldsymbol{x} \sim p_{\text{data}}} \left[ \log \frac{p_{\text{data}}(\boldsymbol{x})}{p_{\text{data}}(\boldsymbol{x}) + p_g(\boldsymbol{x})} \right] + \mathbb{E}_{\boldsymbol{x} \sim p_g} \left[ \log \frac{p_g(\boldsymbol{x})}{p_{\text{data}}(\boldsymbol{x}) + p_g(\boldsymbol{x})} \right]
$$
This simplifies to:
$$
V(D^*_G, G) = -\log 4 + 2 \cdot JS(p_{\text{data}} \| p_g)
$$
Therefore, the optimization objective $\min_G V(D^*_G, G)$ is equivalent to minimizing the JS divergence:
$$
\min_G JS(p_{\text{data}} \| p_g)
$$
However, with the alternative optimization objective you mentioned, after a similar derivation, we find:
$$
V'(D^*, G) = \mathbb{E}_{\boldsymbol{x} \sim p_{\text{data}}} \left[ \frac{p_{\text{data}}}{p_{\text{data}} + p_g} \right] + \mathbb{E}_{\boldsymbol{x} \sim p_g} \left[ \frac{p_g}{p_{\text{data}} + p_g} \right] = 1
$$
Unlike the original GAN, the alternative loss function does not directly express a divergence measure between $p_{\text{data}}$ and $p_g$. The original GAN provides a symmetric and meaningful distribution alignment measure through JS divergence, while the alternative loss function lacks this theoretical foundation and cannot guarantee that $p_{\text{data}} = p_g$ at the optimum.


text:
What specifically is the gradient of the log of the probability in policy gradient methods?
I am getting tripped up slightly by how specifically the gradient is calculated in policy gradient methods (just the intuitive understanding of it).
This Math Stack Exchange post is close, but I'm still a little confused.
In standard supervised learning, the partial derivatives can be acquired specifically because we want to learn about the derivative of the cost with respect to input parameters and then adjust in the direction of minimising this error.
Policy gradients are the opposite, as we want to maximise the likelihood of taking good actions. However, I don't understand what we are getting partial derivatives with respect to - in other words, what is the 'equivalent' of the cost function, specifically for $\nabla_\theta \log\pi_\theta$?

I would recommend not trying to think of this in relation to supervised learning.
The policy $\pi(\cdot; \theta)$ is simply a function that is parameterised by $\theta$. If we take a $\log$ of this function, it is still just a function. We want to take the (partial) derivative(s) of this function with respect to the parameters so that we can perform a gradient ascent step on the parameters.
A simple example can be shown by letting $\pi(a; \alpha, \beta) = \exp(\alpha + \beta a)$. In the policy gradient theorem we must first take a log of the policy which would give us $\log(\pi(a; \alpha, \beta)) = \alpha + \beta a$, and the partial derivatives wrt to the parameters are $\nabla_\alpha \log(\pi(a; \alpha, \beta)) = 1$ and $\nabla_\beta \log(\pi(a; \alpha, \beta)) = a$. We can then use these partial derivatives to perform a gradient ascent update in the direction of the gradient of our objective (the value function, which is of course what we want to maximise) for $\alpha$ and $\beta$ for a given return $G_t$ and action $a_t$ by
\begin{equation}
\alpha' = \alpha + G_t \times \nabla_\alpha \log(\pi(a_t; \alpha, \beta)) = \alpha + G_t \times 1 \; \\
\beta' = \beta + G_t \times \nabla_\beta \log(\pi(a_t; \alpha, \beta)) = \beta + G_t a_t\;.
\end{equation}
In practice, however, you're likely to need a much more complex function for the policy, typically a neural network of some description. However, everything translates to these more complex functions, you're just going to have many more partial derivatives to calculate.

this is perfect - thank you very much! i was having trouble relating the policy itself to still being a differentiable function. thank you for the very clear explanation

Consider a function $f(x)$ where $x$ is a random variable, whose distribution depends on $\theta$. The objective is to minimize
\begin{align*}
\mathbb{E}_x[f(x)] = \int_x f(x) \pi(x, \theta) dx
\end{align*}
where $\pi(x, \theta)$ is the probability density of $x$ given the parameters $\theta$ (to be formal, you should use dummy variables in place of x). The gradient is then
\begin{align*}
\nabla_{\theta} \mathbb{E}_x[f(x)] = \int_x f(x) \nabla_{\theta}\pi(x, \theta) dx \label{1}\tag{1}
\end{align*}
Eq. (1) is essentially the policy gradient. I think when written like Eq. (1), it's clear to see what the gradient actually means.
To see why this is the policy gradient, first we have
\begin{align*}
\int_x f(x) \nabla_{\theta}\pi(x, \theta) dx = \int_x f(x) \nabla_{\theta}\pi(x, \theta) \dfrac{\pi(x, \theta)}{\pi(x, \theta)}dx = \mathbb{E}_x[ f(x) \nabla_{\theta}\log \pi(x, \theta)].
\end{align*}
Now interpret $x$ as the actions, and interpret $f(x)$ to be the expected return. I omit the full details of this, but hopefully you get the idea.
The policy gradient is simply the gradient of the expected returns, with respect to the parameters of the action distribution.

thank you! i upvote both answers for their detail and clear explanations


text:
Is it valid to implement hyper-parameter tuning and THEN cross-validation?
I have a multi-label classification task I am solving. I have done hyperparameter tuning (with Keras Tuner) to determine the best configuration for my neural network.
Is it valid to do this (determine the best hyper-parameters) and then do cross-validation to get a more accurate test estimation of the dataset?
I don't see how this would be invalid, given that the cross-validation examples I have seen already have network architectures known a priori, presumably because this is what they chose or feel is the best way of proceeding.
For hyperparameter tuning, all data is split into training and test sets - the training set is further split, when fitting the model, for a 10% validation set - the optimal model is then used to predict on the test set.
For k-fold cross-validation, all data (same as above) is used, but I just split (with sklearn) the data into training and test datasets (so no validation dataset). The test set is used to determine the model performance at each iteration of k-fold cross-validation.

You should not use the training data for hyper-parameter tuning. In other words, when doing the hyper-parameter tuning, you should not optimize the training objective. You should optimize an objective computed on a dataset that is different than the training dataset. This dataset is sometimes called validation dataset, which can also be used for early stopping, which is not a way of hyper-parameter tuning but to avoid over-fitting.
In the Keras Tuner, you can specify the validation data (which is passed to the fit method under the hood) and the objective of the hyper-parameter optimization. You should specify that the objective is computed on the validation data (e.g. val_loss or val_accuracy), which should be different than the training data. Here you have a complete example.
Once you have selected your hyper-parameters, you can train again the best model on a training dataset, which can or not be the same as the training dataset you used during hyper-parameter optimization, but you should use a test dataset to assess the generalization ability of your model. The main requirement is that the training, validation, and test datasets are disjoint in order to avoid bias.
If you use k-fold cross-validation, you will be training and testing your model with different parts of your whole dataset each time. So, if you have $k$ folds, you will use $k - 1$ folds for training and one for testing. You will do this $k$ times, each time with a different fold for testing and the rest for training. This means that you will be using all your data for training and testing, but, each time, the training and test datasets are separate. You use k-fold CV in order to compute an average (and/or variance) estimate of generalisation of your model (you do this especially when your dataset is small).
In principle, I don't see any big problem with doing k-fold cross-validation after you have selected the best hyper-parameters (e.g. architecture), as long as you used a separate validation dataset, which is disjoint from the data you used for k-fold CV. However, make sure to shuffle your data before hyper-parameter tuning (i.e. before selecting the validation dataset), so that the distribution of the training, validation, and test datasets is roughly the same.
If I understand your descriptions correctly, it seems that you used the validation data also during k-fold CV. I don't think this was a good idea, as you're training and testing a model using data that you used to select that model itself (so this can introduce some kind of bias). You also don't specify which metric you optimize during hyper-parameter optimization.

thank you! this answers my question. so would you recommend just throwing away the validation data used for hyperparameter tuning during k-fold cross val?
so for example, if my training set for HP tuning is 10 total samples with 1 sample used for validation, would you simply remove that one sample for k-fold and train on 9 samples?

@user9317212 Yes, I would recommend that you remove the validation data before doing the k-fold CV. However, if your dataset is really that small, I don't know if it even makes sense to perform HP optimization with 1 sample.

great! thank you! no - it is not, but i wanted to use the most simple example just be concrete about my point -


text:
What is a policy training target in AlphaZero?
In AlphaZero's attached pseudocode, they create a training target for the policy network in this way.
def store_search_statistics(self, root):
    sum_visits = sum(child.visit_count for child in root.children.itervalues())
    self.child_visits.append([
        root.children[a].visit_count / sum_visits if a in root.children else 0
        for a in range(self.num_actions)
    ])

In other words, the training target probability for a certain move is proportional to its visit count.
However, in the paper, they describe the usage of softmax sampling of visit counts with temperature. This temperate is equal to 1 for the first 30 moves (in this case the policy training target is the same as in the pseudocode above) and for subsequent moves they set infinitesimal temperature -> 0, which essentially means they are picking the move with the highest visit count.
Since these are 2 different things (if the game has more than 30 moves), my question is: which approach should be used for creating the training target for the policy?

I've been so confused about this for the longest time. But yes, it seems that DeepMind make an error in their Nature paper. Yes, Policy is matched to the Visit count. Policy is fundamentally a predictor of final Visit count, and based on PUCT, the algorithm uses the Prior Policy when selecting child nodes in MCTS. In other words, PUCT will cause MCTS to start visiting nodes in the distribution that the neural network predicts the final visit distribution will be, but MCTS will deviate from the NN's prediction if one of the paths has a more attractive Q.

For real-life usage of Dennis's answer, Lc0

The training target for the policy is always exactly the one described by the pseudocode; distribution proportional to visit counts, without any other kind of scaling.
The softmax sampling with the temperature (different for first 30 moves than after that) is not used for the policy target, but is used for the "real" move selection by the agent in the self-play game (i.e. after it has run its search of 800 or 1600 or however many iterations it was for the root game state encountered in the self-play game).

Generally, in my experience, you really wouldn't want the policy target to become too close to deterministic, except if really your entire MCTS already is extremely convinced about one move being clearly the best one all by itself (without getting pushed towards something more deterministic by a low-temperature softmax). If your policy becomes too deterministic too quickly, it destroys the exploration that we normally want MCTS to do inside its selection phase. Using a low-temperature softmax for the policy training target would introduce quite a big risk of this happening.


text:
What does "at inference time" on Tesla's cars mean?
I've watched Tesla AI Day 2021 and there was a question Tesla staff tried to answer, but I did not quite understand the question (Note: quote taken from autogenerated subtitles, I do not hear differently, but may you will):

or you'd be training a lot more complex models which would be
potentially significantly more expensive to run at inference time on
the cars

I've found a definition of "inference time" in How to Optimize a Deep Learning Model for faster Inference?

The inference time is how long is takes for a forward propagation

But what does "AT inference time on the cars" mean? Is it just badly worded, or does this "at" actually add proper meaning? Also, does it make sense to run training models on the cars themselves and what can that phrase mean? Overall I do not make sense of the question. Do you?
Note: I'm not a native English speaker.

"At inference time" means "when you perform inference". If "inference" is a synonym for "forward pass" (aka "forward propagation") (which is not always the case in ML), then "at inference time", again, means "when you perform the forward pass". "At" is just a preposition in English and it's often associated with location or time.
So, the sentence

you'd be training a lot more complex models which would be potentially significantly more expensive to run at inference time on the cars

can be rewritten as follows

you'd be training a lot more complex models which would be potentially significantly more expensive to run when performing the forward pass (i.e computing the predictions, for example, whether the traffic light is green or red) on the cars

thank you. my confusion was due to at meaning more "at point of time" whereas "forward propagation" means some duration. What your answer tells me is that, in the context of training, duration of one "forward propagation" is small enough to be talked about as "at point of time". Am I correct at that understanding of the answer?

The "forward propagation" is just the algorithm that we use to compute the predictions or output of the neural network. "At inference time" means when we run this algorithm (i.e. not when we're training the neural network).

"(i.e. not when we're training " that comment re-ignited my confusion with the question in the video. second reason (not clearly stated in the question, I see that) is the person compares "training models" (on supercomputer, as far as I recall) with doing it "at inference time on the cars". You write second part on the cars is not training. Why does he compare costs in that case?

@Martian2020 "at inference time on the cars" means when you're using the trained models to perform predictions about the traffic situation or whatever.

I've understood that already. The person: "would be potentially significantly more expensive to run". Please explain clearly. 1. What would be and 2. more expensive to what? P.S. as of now I see he compares computing cost of training to computing cost of making prediction. What is the point in that?

What is the point to compare costs if one cannot train while also making a prediction?

Ok. I see now where your other doubts lie. They are talking about training multiple models and then they say that this would imply that it's more expensive to run "at inference time". The only explanation that I have is that having multiple models not only makes training more expensive but also making predictions (i.e. inference) more expensive (once the models have been trained, because we need to perform multiple forward passes: one for each model?). This is just a guess of what they could have meant. I didn't watch that video.

Now that you explained it clearly, I have hard time recalling the way I understood it first time I've watched it. Probably my English is not that good (and knowledge of machine learning ;-), that is why I misunderstood complex long sentence. Thanks again!       P.S. in the question the link is to exact time of the sentence.


text:
Can AI be used for grading code copy exercises and adjust difficulty based on these scores?
I'm a senior in a bachelor Multimedia and Creative Technology. My experience is mostly full-stack web app development.
For my bachelor's thesis, I need to do research in a subject I have no experience in. I want to build an application where students can exercise HTML and CSS. Teachers can upload simple code pieces (e.g. h1, h2, and list with elements) with difficulty levels and students can try to copy these exercises with a code editor on the web with live preview.
My question:

Is it possible to use AI for grading these "copies", give the students scores, and, based on these scores, adjust the difficulty level so the next exercise is harder or easier?

And if so, could you put me in the right direction?

I might be wrong, but I would suggest you approach this problem more simply rather than using neural networks or other machine learning constructs. Machine learning is concerned with making a computer learn from a lot of data. You do not need a lot of data to score how well the student's code compares to the teacher's code. You also do not need recommender systems to suggest the next question. Recommender systems suggest by infering the user's preferences, whereas in your case you can simply suggest the next question based on how well the student did on the current question and the type of current question.
I would first identify the following three subproblems:

Scoring and assigning a difficulty score to a teacher's code piece.
Scoring how similar the student's solution is to the true solution.
Predicting next question based on the current problem difficulty and student score for the current problem.

For the first you can develop some algorithms to do feature extraction from the html, css or whatever code piece you want to evaluate. Features can be the following: length of the code piece, number of tags, number of different tags, number of attributes and so on. Combine them in a mathematical formula to calculate a difficulty score for the code piece. I would suggest a linear combination like the following: $Y = \sum{a_i X_i}$ where $X_i$ is the $i$th feature. Then, normalizing all the scores of all questions to a range of $[0, 100]$. You can even have an upper decision boundary such that whenever a certain score is reached, the normalized difficulty score will be $100$.
For the second you should start by checking if the student's code compiles, i.e. there are no syntax errors. Then, you can use Levenshtein Distance to calculate how many characters the student was wrong from the original solution. The goal of a good training should be for the student to infer the exact tags and attributes, so the exact sequence of characters. Calculate the percentage of mistakes over total length of code piece and assign it to $x$. Use a mathematical formula of your liking to score how well the student did given $x$. I would suggest you consider the following formula: $e^{-0.1x}$. It is $100\%$ score for $0$ mistakes and $50\%$ score for having $8\%$ of mistakes. Have a look at the graph at desmos.com.
Similarly, you can construct a formula or recipe for choosing the difficulty of the next problem. It should be based on the current score and the current problem's difficulty. You can even force the student to repeat the question, or a question of similar difficulty if the score is below $50\%$. If the score is above $50\%$, you can for example increase the difficulty level of the questions by 1 point every 3 correctly solved problems. Nevertheless, there are many ways you can approach this.
Hope this helps. Good luck in your thesis.

Sorry for this very late reply. Your answer helped a lot in deciding the flow and building this application. Thank you!


text:
When to use the state value function $V(s)$ and when to use the state-action value function $Q(s, a)$?
I saw the difference between value function $V(s)$ and $Q(s, a)$. But when do I use each one? When I coded in Matlab I only used $Q(s, a)$ directly (as I was thinking of a tabular approach). So, when is more beneficial than the other? I have a large state space.

Here, here and here are 3 related questions.

The core differences between using $V(s)$ or $Q(s,a)$ are:
$V(s)$ cannot be used stand-alone to decide a policy.
You either need a separate policy function $\pi(a|s)$ that it is the value function for, or you can derive a policy from it if you have access to the environment's distribution model $p(r,s'|s,a)$ - the probability of receiving reward $r$ and arriving in next state $s'$ given start $s,a$. The derived policy would be deterministic $\pi(s) = \text{argmax}_a \sum_{r,s'} p(r,s'|s,a)(r + \gamma V(s'))$
In comparison, $Q(s,a)$ can be used to derive a policy without reference to any model: $\pi(s) = \text{argmax}_a Q(s,a)$. This makes the action value function Q necessary for model-free value-based control methods. Hence Monte-Carlo Control, SARSA, Q-Learning will all use action values.
$V(s)$ is usually more compact than $Q(s,a)$.
Space used by a state value table is $O(|\mathcal{S}|)$
Space used by an action-value table is $O(|\mathcal{S} \times \mathcal{A}|)$
These space concerns also apply when you are using approximation - the input domain you need to learn to approximate $Q(s,a)$ is larger than the one you need to learn $V(s)$. Although for large state spaces with lots of dimensions, the relative difference after approximation may be small enough that you don't really care.
The smaller space makes $V(s)$ a good choice if you can use it. The benefits are smaller memory footprint, and often faster learning because there are fewer separate values to learn (not always faster, as you still need to explore all actions in all states to learn accurate values).
Typical scenarios where you can use $V(s)$ instead of $Q(s,a)$

You have access to the full environment model, as described in the first section, above.

or

You are working with a separate policy function. In optimal control, this typically occurs in actor-critic methods, which are relatively advanced RL approach, but a popular one, especially when the action space is large. The situation also occurs in prediction problems where the task is not to optimise anything, but to evaluate a fixed policy.

or

Your actions are directly choosing the next state. This is called afterstate representation, and is subtly different to state values $V(s)$, but has similar benefit of smaller space used. It is useful in determining values in board games and similar environments.

If none of these situations applies, then you will have to use action-value function $Q(s,a)$. You might also choose to use $Q(s,a)$ because it is easier to stick with it in whatever framework you are working in. Sometimes the benefits of using $V(s)$ instead are not large enough to be worth the effort.

@NeilSlater, Thank you answering my question.  I have now asked my scenario specific question. Can you please see if you can answer or suggest something to that as well? Maybe then you can know why  I asked the question on this page. I really need help on this please.


text:
What is the "temperature" in the GPT models?
What does the temperature parameter mean when talking about the GPT models?
I know that a higher temperature value means more randomness, but I want to know how randomness is introduced.
Does temperature mean we add noise to the weights/activations or do we add randomness when choosing a token in the softmax layer?

In sequence generating models, for vocabulary of size $N$ (number of words, parts of words, any other kind of token), one predicts the next token from distribution of the form:
$$
\mathrm{softmax} (x_i/T) \quad i = 1, \ldots N,
$$
Here $T$ is the temperature. The output of the softmax is the probability that the next token will be the $i$-th word in the vocabulary.
The temperature determines how greedy the generative model is.
If the temperature is low, the probabilities to sample other but the class with the highest log probability will be small, and the model will probably output the most correct text, but rather boring, with small variation.
If the temperature is high, the model can output, with rather high probability, other words than those with the highest probability. The generated text will be more diverse, but there is a higher possibility of grammar mistakes and generation of nonsense.

The difference between the low-temperature case (left) and the high-temperature case for the categorical distribution is illustrated in the picture above, where the heights of the bars correspond to probabilities.
Example
A good sample is provided in the Deep Learning with Python by François Chollet in chapter 12. An extract from the tutorial, refer to this notebook.
import numpy as np

tokens_index = dict(enumerate(text_vectorization.get_vocabulary()))

def sample_next(predictions, temperature=1.0):
    predictions = np.asarray(predictions).astype("float64")
    predictions = np.log(predictions) / temperature
    exp_preds = np.exp(predictions)
    predictions = exp_preds / np.sum(exp_preds)
    probas = np.random.multinomial(1, predictions, 1)
    return np.argmax(probas)

What is the range of the parameter $T$?

@nbro $T$ can be any positive number $T \in (0, \infty)$. Reasonable choice dependents on the particular model since different model produce logits with different magnitude. I added the reference to the popular book on DL. Seems like the idea itself is pretty old.

Yes, I guess it's an old idea. The concept of a "temperature" also pops up in other contexts, like simulated annealing, but I am not sure they have a similar role in both cases. Although you don't mention GPT-3, I suspect that your definition of temperature is what is being used also in that context. It might be worth checking.

I guess this is what NovelAI labels as "randomness"

How does T=0 work without causing divide-by-zero errors ? Is there an epsilon in the denominator of the formula to keep this well posed ?

@firdaus If you read spiridon_the_sun_rotator's comment, Zero is not inclusive.

@firdaus For the T=0 case, observe that in the limit as T approaches 0, the probability of choosing the token with the highest log-prob tends towards 100%. So to avoid dividing by zero, I imagine inference algorithms would typically treat T=0 as a special case to always choose the most likely token (see e.g. this line in the llama.cpp implementation).


text:
Best way to resize 3d to 2d matrix
I have a (5, 128, 768) matrix, that is, I have 5 embedding spaces of shape (128, 768). Since they all keep a relation, and for the sake of my model, I need to combine them into a unique output: (1, 128, 768*5). If I just concat them all along axis=-1, will I be losing some info?
Making that concatenation is the only way I can think of solving this. Is there any better option?

I don't fully understand your problem. You have 5 embedding spaces of shape (128, 768), which you store together in the tensor (5, 128, 768). Now, my question is, why do you want to convert the tensor of shape (5, 128, 768) to (1, 128, 768*5)? You don't explain this.

I think if you want to resize and reduce your matrix size, you can use one of the dimension reduction techniques.
Here there is a link that may be helpful to you.

thank you for answering. By doing dim reduction, will I lose info?

techniques are different and in that link, it is written for every technique that is lossless or lossy decomposition.