text:
What's the difference between estimation and approximation error?
I'm unable to find online, or understand from context - the difference between estimation error and approximation error in the context of machine learning (and, specifically, reinforcement learning).
Could someone please explain with the help of examples and/or references?

Section 5.2 Error Decomposition of the book Understanding Machine Learning: From Theory to Algorithms (2014) gives a description of the approximation error and estimation error in the context of empirical risk minimization (ERM) and, in particular, in the context of the bias-complexity tradeoff (which is strictly related to the bias-variance tradeoff).
Error/risk decomposition
The expected risk (error) of a hypothesis $h_S \in \mathcal{H}$ selected based on the training dataset $S$ from a hypothesis class $\mathcal{H}$ can be decomposed into the approximation error, $\epsilon_{\mathrm{app}}$, and the estimation error, $\epsilon_{\mathrm{est}}$, as follows
\begin{align}
L_{\mathcal{D}}\left(h_{S}\right)
&=
\epsilon_{\mathrm{app}}+\epsilon_{\mathrm{est}} \\
&=
\epsilon_{\mathrm{app}}+ \left( L_{\mathcal{D}}\left(h_{S}\right)-\epsilon_{\mathrm{app}} \right) \\
&=
\left( \min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)\right) + \left( L_{\mathcal{D}}\left(h_{S}\right)-\epsilon_{\mathrm{app}} \right) \label{1}\tag{1}
\end{align}
Approximation error
The approximation error (AE), aka inductive bias, defined as
$$\epsilon_{\mathrm{app}} = \min _{h \in \mathcal{H}} L_{\mathcal{D}}(h) $$
is the error due to the specific choice of hypothesis class (or set) $\mathcal{H}$. So, $\min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)$ is minimal risk/error that can be achieved with a hypothesis class $\mathcal{H}$. In other words, if you limit yourself to $\mathcal{H}$ and you select the "best" hypothesis in $\mathcal{H}$, then $\min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)$ is the expected risk of that hypothesis.
Here are some properties.

The larger $\mathcal{H}$ is, the smaller this error is (because it's more likely that a larger hypothesis class contains the actual hypothesis we are looking for). So, if $\mathcal{H}$ does not contain the actual hypothesis we are searching for, then this error could not be zero.

This error does not depend on the training data. You can see in the formula above that there's no $S$ (the training dataset), but only on $D$ (the distribution over the space of inputs and labels from which $S$ was assumed to have been sampled)

Estimation error
The estimation error (EE) is the difference between the approximation error $\epsilon_{\mathrm{app}}$ and the error achieved by the ERM predictor $L_{\mathcal{D}}\left(h_{S}\right)$, i.e.
\begin{align}
\epsilon_{\mathrm{est}}
&=L_{\mathcal{D}}\left(h_{S}\right)-\epsilon_{\mathrm{app}} \\
&= L_{\mathcal{D}}\left(h_{S}\right) - \min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)
\end{align}
Here are some properties.

The estimation error depends on the training dataset $S$. You can see $S$ in the formula above.

$\epsilon_{\mathrm{est}}$ also depends on the choice of the hypothesis class (given that it is defined as a function of $\epsilon_{\mathrm{app}}$).

Bias-complexity tradeoff
If we increase the size and complexity of the hypothesis class, the approximation error decreases, but the estimation error may increase (i.e. we may have over-fitting). On the other hand, if we decrease the size and complexity of the hypothesis class, the estimation error may decrease, but the bias may increase (i.e. we may have under-fitting). So, we have a bias-complexity trade-off (where the bias refers to the approximation error or inductive bias) and the complexity refers to the complexity of the hypothesis class.
Error excess
In section 4.1 of this book also describes a similar (but equivalent) error decomposition, which is called error excess because it's a difference between the expected risk and the Bayes error (which is sometimes called inherent error or irreducible error), which they denote by $R^{*}$, while the other book above, which also points out that there's this equivalent error excess decomposition, denote it by $\epsilon_{\mathrm{Bayes}}$. So, here's the error excess
$$R(h)-R^{*}=\underbrace{\left(\inf _{h \in \mathcal{H}} R(h)-R^{*}\right)}_{\text {approximation excess}} + \underbrace{\left(R(h)-\inf _{h \in \mathcal{H}} R(h)\right)}_{\text {estimation error}}$$
So, if you take $R^{*} = \epsilon_{\mathrm{Bayes}}$ from both sides of the equation, you end up with
$$R(h)=\underbrace{\left(\inf _{h \in \mathcal{H}} R(h) \right)}_{\epsilon_{\mathrm{app}}} + \underbrace{\left(R(h)-\inf _{h \in \mathcal{H}} R(h)\right)}_{\epsilon_{\mathrm{est}}} \label{2}\tag{2}$$
which is equivalent to equation \ref{1}, where

$L_{\mathcal{D}}\left(h_{S}\right)    \equiv R(h)$
$\min _{h \in \mathcal{H}} L_{\mathcal{D}}(h)     \equiv \inf _{h \in \mathcal{H}} R(h)$

Illustration
A nice picture that illustrates the relationship between these terms can be found in figure 4.1 of this book (p. 62).

Here, the red points are specific hypotheses. In this illustration, we can see that the best hypothesis (the Bayes hypothesis) lies outside our chosen hypothesis class $\mathcal{H}$. The distance between the risk of $h \in \mathcal{H}$ and the risk of $h^* = \operatorname{arg inf} _{h \in \mathcal{H}} R(h)$ is the estimation error, while the distance between $h^*$ and the Bayes hypothesis (i.e. the hypothesis that achieves the Bayes error) is the approximation excess in equation \ref{2}.

Could you please elaborate if the training error on my dataset can ever be zero ? Looking at equation above seems no. However I always thought these equations explain why the difference between train and test error can never be zero.

@SiddhantTandon I will try to answer your question later. In the first book, they use $L$ to refer to the training error, while, in the second, they refer to it as the expected risk of the hypothesis. I think that this use of different terminology may cause confusion because here the training error is not defined. The second book actually calls what I called the "approximation excess" the "approximation error", but I was trying to connect the definitions of the two books in this answer. There's also a clear distinction between expected risk and empirical risk.

I think this is best explained by pictures. Please note that $h_{S}$ is the output of the ERM learner (under the hypothesis class $\mathcal{H}$) is denoted by $ERM_{\mathcal{H}}$, $f$ is the target hypothesis or the true labeling function. Also:

By definition, the approximation error $=\epsilon_{app} := \underset{h\in \mathcal{H}}{min}\ L_{\mathcal{D}}(h)$ is always less than or equal to the estimation error (or the generalization risk/error) $=\epsilon_{est}=\mathcal{L}_{\mathcal{D}}(h_{\mathcal{S}})$.
The estimation error $\epsilon_{est}=L_{\mathcal{D}}(h_{S})$ is NOT the training error (or empirical risk/error) $L_{S}(h_{S})$, rather the estimation error results because of the training error.

A small hypothesis class (or space) $\mathcal{H}$ not containing the target hypothesis $f$, the hypothesis $h_{S} \in \mathcal{H}$ found by the $ERM_{\mathcal{H}}$ learner via training, by some chance - say - small training set size, is not $h^{\star}$. Increasing the training set size may often help (i.e. make $h_{S}$ move closer or even equal to $h^{\star}$):

Another relatively small but slightly better hypothesis space $\mathcal{H}^{'}$: The approximation error (generalization error comes from the best hypothesis) is smaller than that one, i.e. $h^{\star}$ closely approximates the target function:

A good hypothesis space $\mathcal{H^{''}}$, of course the best hypothesis class is $\mathcal{H^{'''}}=\{f\}$ but most of the time we don't know what the (class of the) target hypothesis function $f$ is (if we know the function $f$ then learning is redundant), and especially under the assumption of agnostic PAC learning, it's often not a labeling function but rather a data generating distribution:


text:
Why is regret so defined in MABs?
Consider a multi-armed bandit(MAB). There are $k$ arms, with reward distributions $R_i$ where $1 \leq i \leq k$. Let $\mu_i$ denote the mean of the $i^{th}$ distribution.
If we run the multi-armed bandit experiment  for $T$ rounds, the "pseudo regret" is defined as $$\text{Regret}_T = \sum_{t=1}^T \mu^* - \mu_{it},$$ where $\mu^*$ denotes the highest mean among all the $k$ distributions.
Why is regret defined like this? From what I understand, at time-step $t$, the actual reward received is $r_t \sim R_{it} $ and not $\mu_{it}$ - so shouldn't that be a part of the expression for regret instead?

We don’t care what happens for one instance at one time step, we care about what happens in expectation at that time step, hence the mean

Another reason is that, if we were to define regret with respect to the observed rewards, we might get negative regret whenever the agent just happens to be lucky.

In short, you don't regret your bad luck that you could do nothing about, you regret your bad choices that you could have done something about if only you knew.
The point of regret as a metric therefore is to compare your choices with the ideal choices. This makes sense in MABs, because although the primary goal is to gain the most reward, the learning part of the goal is to calculate from experience what are the best choices - usually whilst sacrificing as little as possible in the process.
The formula captures that concept, so does not concern itself with individual rewards in the past that could have been due to good or bad luck. Hence it uses expected (or mean) rewards.

source: Stack Exchange

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

sort: votes


text:
Why do my rewards reduce after extensive training using D3QN?
I am running a drone simulator for collision avoidance using a slight variant of D3QN. The training is usually costly (runs for at least a week) and I have observed that reward function gradually increases during training and then drastically drops. In the simulator, this corresponds to the drone exhibiting cool collision avoidance after a few thousand episodes. However, after training for more iterations it starts taking counterintuitive actions such as simply crashing into a wall (I have checked to ensure that there is no exploration at play over here).
Does this have to do with overfitting? I am unable to understand why my rewards are falling this way.

It is not 100% clear, but this seems like an instance of catastrophic forgetting. This is something that often impacts reinforcement learning.
I have answered a very similar question on Data Science stack exchange, and reproduce the same answer here.

This is called "catastrophic forgetting" and can be a serious problem in many RL scenarios.
If you trained a neural network to recognise cats and dogs and did the following:

Train it for many epochs on a full dataset until you got a high accuracy.

Continue to train it, but remove all the cat pictures.

Then in a relatively short space of time, the NN would start to lose accuracy. It would forget what a cat looks like. It would learn that its task was to switch the dog prediction as high as possible, just because on average everything in the training population was a dog.
Something very similar happens in your DQN experience replay memory. Once it gets good at a task, it may only experience success. Eventually, only successful examples are in its memory. The NN forgets what failure looks like (what the states are, and what it should predict for their values), and predicts high values for everything.
Later on, when something bad happens and the NNs high predicted value is completely wrong, the error can be high. In addition the NN may have incorrectly "linked" features of the state representation so that it cannot distinguish which parts of the feature space are the cause of this. This creates odd effects in terms of what it learns about values of all states. Often the NN will behave incorrectly for a few episodes but then re-learn optimal behaviour. But it is also possible that it completely breaks and never recovers.
There is lots of active research into catastrophic forgetting and I suggest you search that term to find out some of the many types of mitigation you could use.
For Cartpole, I found a very simple hack made the learning very stable. Keep aside some percentage of replay memory stocked with the initial poor performing random exploration. Reserving say 10% to this long term memory is enough to make learning in Cartpole rock solid, as the NN always has a few examples of what not to do. The idea unfortunately does not scale well to more complex environments, but it is a nice demonstration. For a more sophisticated look at similar solutions you could see the paper "The importance of experience replay database composition in deep reinforcement learning"

Great explanation !

This answer is fantastic and I know its been a couple of years but I wonder if leaving the final exploration rate >0 (say 0.05 or so) is sufficient to counteract this? It should mean that the agent will always be sampling some random actions (of which there will inevitably be things the agent shouldn't do)

@Jarym: It might help to tweak this as a hyperparameter. However, catastrophic forgetting is often observed in DQN-based learning systems where there already is a mimimum exploration rate, so it is not a fix. Setting a high exploration rate can compromise overall earning rate and eventual optimality, especially in harder problems with long episodes.

@Jarym: Different exploration schemes, as opposed to tweaking the exploration rate, could help. For instance, an approach like DynaQ+, where exploration rates increase over time and tend to encourage large, multi-step explorations, or coherent noise approaches which tend to explore or exploit over multiple timesteps. Both these approaches will sample data further away from current successful trajectories on a routine basis

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


text:
How to mathematically describe the convolution operation (with a Gaussian kernel)?
I have to build a model where I pre-process the data with a Gaussian kernel. The data are an $n\times n$ matrix (i.e one channel), but not an image, thus I can't refer to this matrix as an image and to its elements as pixels. The Gaussian kernel is built by the following function (more i.e. here)
$$\begin{equation}
\begin{aligned}
g(x,y,\sigma) =
\dfrac{1}{2\pi\sigma^2} e^{\dfrac{-(x^2+y^2)}{2\sigma^2}}.
\end{aligned}
\end{equation}$$
This kernel is moving one by one element and doing convolution. In my case, most of the elements are zero, the matrix is sparse.
How can I describe/understand the process of convolving the original data with a Gaussian kernel?
I have been looking for some articles, but I am unable to find any mathematical explanations, only explanation in words or pseudo-code.

Mathematically, the convolution is an operation that takes two functions, $f$ and $g$, and produces a third function, $h$. Concisely, we can denote the convolution operation as follows
$$f \circledast g = h$$
In the context of computer vision and, in particular, image processing, the convolution is widely used to apply a so-called kernel (aka filter) to an input (typically, an image, but this does not have to be the case). The input (e.g. an image), the kernel, and the output of the convolution, in this context, is usually a matrix or a tensor. In image processing, the convolution is typically used to e.g. blur images or maybe to remove noise.
However, in the beginning, I said that the convolution is an operation that takes two functions (and not matrices) and produces a third one, so these two explanations of the convolution do not seem to be consistent, right?
The answer to this question is that the two explanations are consistent with each other. More precisely, if you have a function $f : X \rightarrow Y$ (assuming that $X$ is discrete/countable), you can represent it in a vector form as follows $\mathbf{f} = [y_1, y_2, \dots, y_n]$, i.e. $\mathbf{f}$ is a vector that contains all outputs of the function $f$ (for all possible inputs).
In image processing, an image and a kernel can also be thought of as a function with a discrete domain (i.e. the pixels), so the matrices that represent the image or the kernel are just the vector forms of the corresponding functions. See this answer for more details about representing an image as a function.
Once you understand that the convolution in image processing is really the convolution operation as defined in mathematics, then you can simply look up the mathematical definition of the convolution operation.
In the discrete case (i.e. you can think of the function as vectors, as explained above), the convolution is defined as
$${\displaystyle h[n] =  (f  \circledast g)[n]=\sum _{m=-M}^{M}f[n-m]g[m].} \tag{1}\label{1}$$
You can read equation $1$ as follows

$f  \circledast g$ is the convolution of the input function (or matrix) $f$ and the kernel $g$
$(f  \circledast g)[n]$ is the output of the convolution $f  \circledast g$ at index (or input position) $n$ (so you need to apply equation \ref{1} for all $n$, if you want to have $h$ and not just $h[n]$)
So, the result of the convolution at $n$, $h[n]$, is defined as $\sum _{m=-M}^{M}f[n-m]g[m]$, a sum that goes from $m = -M$ to $m = M$. Here $M$ may be half of the length of the kernel matrix. For example, if you use the following Gaussian kernel, then $M = 2$ (and I assume that the center of the kernel is at coordinate $(0, 0)$).

$$
\mathbf{g} =
\frac{1}{273}
\begin{bmatrix}
1 & 4 & 7 & 4 & 1 \\
4 & 16 & 26 & 16 & 4 \\
7 & 26 & 41 & 26 & 7 \\
4 & 16 & 26 & 16 & 4 \\
1 & 4 & 7 & 4 & 1
\end{bmatrix}
\label{2}\tag{2}
$$
Here are some notes:

The kernel \ref{2} is symmetric around the $x$ and $y$ axes: this actually implies that the convolution is equal to the cross-correlation, so you don't even have to worry about their equivalence or not (in case you have ever worried about it, which would have happened only if you already came across the cross-correlation). See this question for more info.

The kernel \ref{2} is the vector form of the function form of the 2d Gaussian kernel (the one in your question): more precisely, an integer-valued approximation of the 2D Gaussian kernel when $\sigma = 1$ (as stated in your slides).

The convolution can be implemented as matrix multiplication. This may not be useful now, but it's something useful to know if you want to implement it. See this question for more info.

Question for you: what is the result of the application of this Gaussian kernel to any input? What does this kernel intuitively do? Once you fully understand the convolution, you can answer this question.

Thank you for clear answer, this is exactly what I needed to further understand the convolution! So the kernel intuitively multiplies corresponding elements of the input vector with kernel values and count it together, since my matrix is very sparse in most cases and radius arround non-zero element are often only 0s, the result is only multiplication of the one (or few) non-zero element plus 0 times rest.

@Ruli Note that if you use a matrix instead of a vector (to represent the input and kernel), you will need 2 sums (one that goes horizontally across the kernel and image and one that goes vertically) in the definition of the discrete convolution (rather than just 1, like I wrote above, which is the definition for 1-dimensional signals, i.e. vectors). Maybe this Wikipedia article will clarify more what I mean. Maybe I will edit my answer later to be more precise and include this info.


text:
What is the best resources to learn Graph Convolutional Neural Networks?
For the past few days, I am trying to learn graph convolutional networks. I saw some of the lectures on youtube. But I can not able to get any clear concept of how those networks are trained. I have a vague understanding of how to perform convolution, but I can not understand how we train them. I want a solid mathematical understanding of graph convolutional networks. So, can anyone please suggest me how to start learning graph convolutional network from start to expert level?

See What is a graph neural network?.

I believe Graph Representation Learning book by William L. Hamilton is a great resource to start

thank u for this suggestion. which pages (part) of this book is about GCN?

There is also the proto-book Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges (2021), written by some of the experts on the topic. The book does not focus only on graphs and graph neural networks (GNNs), but also covers manifolds, geodesics, and other mathematical concepts related to geometric deep learning and other GDL models.


text:
Is GAIL applicable if the expert's trajectories are for the same task but are in a different environment?
Is the GAIL applicable if the expert's trajectories (sample data) are for the same task but are in a different environment (modified but will not be completely different)?
My gut feeling is, yes, otherwise we can just simply adopt behavioural cloning. Furthermore, since the expert's trajectories are from a different environment, the dimension/length of state-action pairs will most likely be different. Will those trajectories still be useful for GAIL training?

What do you mean by "behavioural cloning" here?

I mean the supervised imitation learning approach where the agent tries to copy the demonstrated labeled data.

The authors of the paper Learning Robust Rewards with Adversarial Inverse Reinforcement Learning (2018, published in ICRL), which introduced the inverse RL technique AIRL, argue that GAIL fails to generalize to different environment's dynamics. Specifically, in section 7.2 (p. 7), they describe an experiment where they disable and shrink the two front legs of the ant, then, based on the results, they conclude

GAIL learns successfully in the training domain, but does not acquire a representation that is suitable for transfer to test domains.

On the other hand, according to their experiments, AIRL is more robust to changes in the environment's dynamics.


text:
Why is the completeness of UCS guaranteed only if the cost of every step exceeds some small positive constant?
I was reading Artificial Intelligence: A Modern Approach 3rd Edition, and I have reached to the UCS algorithm.
I was reading the proof that UCS is complete.
The book state that:

Completeness is guaranteed provided the cost of every step exceeds some small positive constant $\epsilon .$

And that's because UCS will be stuck if there is a path with an infinite
sequence of zero-cost actions.
Why the step cost must exceed $\epsilon$? Isn't enough for it to be greater than zero?

Let's consider a problem where all edge costs are greater than zero, but not above some $\epsilon$:
Image a problem where we have an infinite path where the first edge is cost $\frac{1}{2}$, the next is $\frac{1}{4}$, the following is $\frac{1}{8}$, and so on forever. Every edge is greater than zero, meeting the condition being proposed in the question. However, this path overall has finite cost (1) even through there are an infinite number of states on that path. So, on this problem UCS will never reach paths with cost greater than 1. Thus, if the solution cost is 2, UCS will not find any solution to this problem, and thus it would not be a complete algorithm. So, all edges being greater than zero is not sufficient.
For most search algorithms to be complete, there must be a finite number of states with any given cost. (To be slightly more precise, there must exist some fixed $\epsilon$ such that in each range size $\epsilon$ there are a finite number of states.)


text:
Is continuous learning possible with a deep convolutional neural network, without changing its topology?
In general, is continuous learning possible with a deep convolutional neural network, without changing its topology?
In my case, I want to use a convolutional neural network as a classifier of heartbeat types. The ECG signal is split, and a color image is created using feature extraction. These photos (the inputs) are fed into a deep CNN, but they must be labeled by someone first.
Are there ways to implement continuous learning in a deep neural network for image recognition? Does such an implementation make sense if the labels have to be specially prepared in advance?

Your question is very similar to this (which is asking about the state-of-the-art approaches, which is not your question), this (which does not seem to focus on CNNs and image recognition), this (which focuses on the case where new classes are incrementally given) or this (which asks if a CNN can be trained incrementally, without putting any restriction on the topology) questions.

Here, you are specifically asking about "incremental/continual learning for image recognition without changing the NN's topology", so I will not close this post as a duplicate of those.

In general, is continuous learning possible with a deep convolutional neural network, without changing its topology?

Your intuition that it is possible to perform incremental (aka continual, continuous or lifelong) learning by changing the NN's topology is correct. However, dynamically adapting the NN's topology is just one approach to continual learning (a specific example of this approach is DEN). So, there are other approaches, such as

regularization approaches (examples are LwF, EWC and SI)

ensemble approaches (examples are Learn++, FEL and PathNet)

rehearsal approaches (an example is iCaRL)

For more details about these and other approaches (and problems related to continual learning and catastrophic forgetting in neural networks), take a look at this very nice review of continual learning approaches in neural networks. You should also check this answer.

Are there ways to implement continuous learning in a deep neural network for image recognition?

Yes. Many of the approaches focus on image recognition and classification, and often the experiments are performed on MNIST or similar datasets (e.g. see this paper).

Does such an implementation make sense if the labels have to be specially prepared in advance?

Yes, you can prepare your dataset in advance, and then later train incrementally (in fact, in the experiments I have seen in some of these papers, they usually do this to simulate the continual learning scenario), but I am not sure about the optimality of this approach. Maybe with batch learning (i.e. the usual offline learning where you train on all data), you would achieve higher performance.


text:
How to calculate probability from fuzzy membership grade?
Suppose we have the fuzzy membership grade for a person $x$ with a set $S = \text{set of tall people}$ be $0.9$, i.e. $\mu_S(x)=0.9$.
Does this mean that the probability of person $x$ being tall is $0.9$?

No, you can't extract any probability from a fuzzy membership grade. The uncertainty expressed by fuzzy logic is about partial truth, not about probability. $ \mu_S(x) = 0.9 $ doesn't mean that "$ x $ is tall" is true with a probability of 0.9, but that "$ x $ is tall" is 90% true (notice the difference in semantics). You have to think about fuzzy logic as an extension of logic (as its name implies), rather than an extension of probability.
It's true, however, that fuzzy logic is flexible and lets you define how the membership grades are combined in logic formulae, to the extend you can replicate probability theory within the fuzzy logic framework. Wikipedia has a good overview on this: https://en.wikipedia.org/wiki/Fuzzy_logic#Comparison_to_probability.
However, please understand that, in general, fuzzy membership $ \neq $ probability. How we come up with the fuzzy membership grade is subjective and application-dependent. Conversely, probabilities have a well-defined and unambiguous interpretation. The point of being fuzzy is to replicate our reasoning process which, even if is not necessarily formal and rigorous, is often very accurate. To do so it needs a set of (admittedly arbitrary) rules on how to calculate the "truthfulness" of logical formulae. This may turn to be very useful in applications where manipulating probabilities or coming up with them in the first place is not tractable.


text:
How does the implementation of the VAE's objective function equate to ELBO?
For a lot of VAE implementations I've seen in code, it's not really obvious to me how it equates to ELBO.
$$L(X)=H(Q)-H(Q:P(X,Z))=\sum_ZQ(Z)logP(Z,X)-\sum_ZQ(Z)log(Q(Z))$$
The above is the definition of ELBO, where $X$ is some input, $Z$ is a latent variable, $H()$ is the entropy. $Q()$ is a distribution being used to approximate distribution $P()$, which in the above case both $P()$ and $Q()$ are discrete distributions, because of the sum.
A lot of the times when VAEs are built for reconstructing discrete data types, let's say for example an image, where each pixel can be black or white or $0$ or $1$. The main steps of a VAE that I've seen in code are as follows:

$\text{Encoder}(Y) \rightarrow Z_u, Z_{\sigma}$
$\text{Reparameterization Trick}(Z_\mu, Z_\sigma) \rightarrow Z$
$\text{Decoder}(Z) \rightarrow \hat{Y}$
$L(Y)= \text{CrossEntropy}(\hat{Y}, Y) - 0.5*(1+Z_{\sigma}-Z_{\mu}^2-exp(Z_\sigma))$

where

$Z$ represents the latent embedding of the auto-encoder
$Z_\mu$ and $Z_\sigma$ represent the mean and standard deviation for sampling for $Z$ from a Gaussian distribution.
$Y$ represents the binary image trying to be reconstructed
$\hat{Y}$ represents its reconstruction from the VAE.

As we can see from the ELBO, it's the entropy of the latent distribution being learned, $Q()$, which is a Gaussian, and the cross entropy of the latent distribution being learned $Q()$ and the actual distribution $P()$ with $Z$ intersected with $X$.
The main points that confuse me are

how $\text{CrossEntropy}(\hat{Y}, Y)$ equates to the CE of the distribution for generating latents and its Gaussian approximation, and
how $(0.5*(1+Z_{\sigma}-Z_{\mu}^2-exp(Z_\sigma)))$ equates to the entropy

Is it just assumed the CE of $Y$ with $\hat{Y}$ also leads to the CE of the latent distribution with it's approximation, because they're part of $\hat{Y}$'s generation? It still seems a bit off because you're getting the cross entropy of $Y$ with it's reconstruction, not the Gaussian distribution for learning latents $Z$.
Note: $Z_\sigma$ is usually not softplused to be strictly positive as required by a Gaussian distribution, so I think that's what $exp(Z_\sigma)$ is for.

I don't want to think about the correctness of your supposed ELBO equation now. Nevertheless, it's true that the ELBO can be rewritten in different ways (e.g. if you expand the KL divergence below, by applying its definition, you will end up with a different but equivalent version of the ELBO). I will use the most common (and definitely most intuitive, at least to me) one, which you can find in the paper that originally introduced the VAE, which you should use as a reference, when you are confused (although that paper may require at least 2 readings before you fully understand it).
Here's the most common form of the ELBO (for the VAE), which immediately explains the common VAE implementations (including yours):
$$\mathcal{L}\left(\boldsymbol{\theta}, \boldsymbol{\phi} ; \mathbf{x}^{(i)}\right)=
\underbrace{
\color{red}{
-D_{K L}\left(q_{\boldsymbol{\phi}}\left(\mathbf{z} \mid \mathbf{x}^{(i)}\right) \| p_{\boldsymbol{\theta}}(\mathbf{z})\right)
}
}_{\text{KL divergence}}
+
\underbrace{
\color{green}{
\mathbb{E}_{q_{\boldsymbol{\phi}}\left(\mathbf{z} \mid \mathbf{x}^{(i)}\right)}\left[\color{blue}{ \log p_{\boldsymbol{\theta}}\left(\mathbf{x}^{(i)} \mid \mathbf{z}\right)}\right]
}
}_{\text{Expected log-likelihood}},
$$
where

$p_{\boldsymbol{\theta}}(\mathbf{z})$ is the prior over $\mathbf{z}$ (i.e. the latent variable); in practice, the prior is not actually parametrized by $\boldsymbol{\theta}$ (i.e. it's just a Gaussian with mean zero and variance one, or whatever, depending on your assumptions about $\mathbf{z}$!), but in the paper they assume that $\mathbf{z}$ depends on $\boldsymbol{\theta}$ (see figure 1).

$q_{\boldsymbol{\phi}}\left(\mathbf{z} \mid \mathbf{x}^{(i)}\right)$ is the encoder parametrized by $\boldsymbol{\phi}$

$p_{\boldsymbol{\theta}}$ is the decoder, parametrized by $\boldsymbol{\theta}$

If you assume that $p_{\boldsymbol{\theta}}(\mathbf{z})$ and $q_{\boldsymbol{\phi}}\left(\mathbf{z} \mid \mathbf{x}^{(i)}\right) $ are Gaussian distributions, then it turns out that the KL divergence has an analytical form, which is also derived in appendix B of the VAE paper (here is a detailed derivation)
$$
\color{red}{
-D_{K L}\left(q_{\boldsymbol{\phi}}\left(\mathbf{z} \mid \mathbf{x}^{(i)}\right) \| p_{\boldsymbol{\theta}}(\mathbf{z})\right)}
=
\color{red}{
\frac{1}{2} \sum_{j=1}^{J}\left(1+\log \left(\left(\sigma_{j}\right)^{2}\right)-\left(\mu_{j}\right)^{2}-\left(\sigma_{j}\right)^{2}\right)
}
$$
Hence this implementation, which should be equivalent to your term $0.5*(1+Z_{\sigma}-Z_{\mu}^2-exp(Z_\sigma))$
The expected log-likelihood is actually an expectation, so you cannot compute it exactly, in general. Hence, you can approximate it with Monte Carlo sampling (aka sampling averages: remember the law of large numbers?). More concretely, if you assume that you have a Bernoulli likelihood, i.e. $p_{\boldsymbol{\theta}}\left(\mathbf{x}^{(i)} \mid \mathbf{z}\right)$ is a Bernoulli, then its definition is (again from the VAE paper, Appendix C.1)
$$
\color{blue}{ \log p(\mathbf{x} \mid \mathbf{z})}= \color{blue}{ \sum_{i=1}^{D} x_{i} \log y_{i}+\left(1-x_{i}\right) \cdot \log \left(1-y_{i}\right) }\tag{1}\label{1},
$$
where $\mathbf{y}$ is the output of the decoder (i.e. the reconstruction/generation of the original input).
This formula should be very familiar to you if you are familiar with the cross-entropy. In fact, minimizing the cross-entropy is equivalent to maximizing the log-likelihood (this may still be confusing because of the flipped signs in the ELBO above, but just remember that maximizing a function is equivalent to minimizing its negative!). Hence this loss.
To answer/address some of your questions/doubts directly

how $(0.5*(1+Z_{\sigma}-Z_{\mu}^2-exp(Z_\sigma)))$ equates to the entropy?

I answered this above. That's just the analytical expression for the KL divergence (by the way, the KL divergence is also known as relative entropy). See this answer for a derivation.

It still seems a bit off because you're getting the cross entropy of $Y$ with it's reconstruction, not the Gaussian distribution for learning latents $Z$.

As you can see from the definition of the ELBO above (from the VAE paper), the expected log-likelihood is, as the name suggests, an expectation, with respect to the encoder (i.e. the Gaussian, in case you choose a Gaussian). However, the equivalence is between the log-likelihood (which is the term inside the expectation) and the cross-entropy, i.e. once you have sampled from the encoder, you just need to compute the term inside the expectation (i.e. the cross-entropy). Your term $\text{CrossEntropy}(\hat{Y}, Y)$ represents the CE but after you have sampled a latent variable from the encoder (or Gaussian), otherwise, you could not have obtained the reconstruction $\hat{Y}$ (i.e. the reconstruction depends on this latent variable, see figure 1).
In equation \ref{1}, note that there is no expectation. In fact, in the implementations, you may just sample once from the encoder, and then immediately compute the ELBO. I have seen this also in the implementations of Bayesian neural networks (basically, normal neural networks with the same principles of the VAE). However, in principle, you could sample multiple times from the Gaussian encoder, compute \ref{1} multiple times, then average it, to compute a better approximation of the expected log-likelihood.
Hopefully, some of the information in this answer is clear. Honestly, I don't have much time to write a better answer now (maybe I will come back later). In any case, I think you can find all answers to your questions/doubts in the VAE paper (although, as I said, you may need to read it at least twice to understand it).
By the way, the simplest/cleanest implementation of the VAE that I have found so far is this one.

Really good explanation, every part of my question is answered except maybe the $CE(\hat{Y}, Y)$ being equivalent to expected log likelihood.

@user8714896 I think you can find the answer to that question on the web. If not, you can ask another separate question, and maybe later I will answer.


text:
Why is an embedding of dimension 400 enough to represent 70000 words?
I am learning PyTorch on Udacity. In lesson 8, section 11: Training the Model, the instructor writes:

Then I have my embedding and hidden dimension. The embedding dimension is just a smaller representation of my vocabulary of 70k words and I think any value between like 200 and 500 or so would work, here. I've chosen 400. Similarly, for our hidden dimension, I think 256 hidden features should be enough to distinguish between positive and negative reviews.

There are more than 70000 different words. How could those more than 70000 unique words be represented by just 400 embeddings? How does an embedding look like? Is it a number?
Moreover, why would 256 hidden features be enough?

The specific term you are looking for is "word embedding" and not just "embedding".
How to numerically represent textual data?
Neural networks (typically) require as inputs (and produce as outputs) numerical data (i.e. numbers, vectors, matrices, or higher-dimensional arrays). So, when processing textual data, we first need to encode (or convert) the text into a numerical representation. There are different ways to do it, such as

one-hot encoding (in that case, if you have 70000 words, you would have sparse vectors with 70000 entries where only one of those entries is equal to $1$ and all other entries are $0$: see this article  for more info)

map each word to a number (in this case, you would have 70000 numbers, one for each word)

word embeddings

Each of these representations has different benefits and drawbacks. For instance, if you map each word to a number, then you just need to keep track of $70000$ numbers. In the case of one-hot encoding or word embeddings, you will need more memory. However, nowadays, word embeddings are widely used in natural language processing/understanding/generation tasks (and given that your question is about word embeddings), so let me briefly describe them.
Word embeddings
There are different word embedding techniques (such as word2vec). However, they are all based on the same ideas

Words that are similar (or related) in meaning should be mapped to vectors (i.e. the "word embeddings") that are also similar in some sense (for instance, their cosine similarity should be high). For instance, the words "man" and "boy" should be mapped to vectors that are similar.

These word embeddings are learned (rather than hard-coded or manually specified) given the data

The size of the word embeddings is a hyper-parameter (this should answer your question!)

Hyper-parameters
To answer your question(s) more directly, the choice of the dimension of the embeddings or the number of "hidden features" (which are both hyper-parameters) was probably more or less arbitrary or based on the instructor's experience. In general, it is difficult to determine the optimal choice of any hyper-parameter. Sometimes you can just use numbers that other people have used in the past and have noticed that work "well enough". If you really want to find more appropriate values of the hyper-parameters, you could use some hyper-parameter optimization technique, such as Bayesian optimization or a simple grid search.
Further reading
You can find many resources online that explain the concept of "word embeddings" more in detail. For instance

What Are Word Embeddings for Text? (by Jason Brownlee)
Word embeddings (A TensorFlow article/tutorial on word embeddings).

thanks! the references mentioned in your answer is hugely informative and helpful!

It's useful to know, if the instructor hasn't mentioned it, that you develop intuitions based on empirical (experimental) evidence in this space.  In other words, why 256?  Because I've done this before and 256 seemed to work well. :). It can be more specific... If you have a high degree of expertise in a domain, or you apply statistical methods to identify relevant features, you can select features and other parameters with more rigorous methods, but otherwise, it's guessing with fancy names. :)

@DavidHoelzer You're right that those numbers might have been picked by guessing. My point is that these are hyper-parameters, so there isn't a strict rule to decide their values. You can use some hyper-parameter optimization technique, but more often than not you will use some specific value because someone else used it (and that's good enough for your purposes for now). Again, of course, this is not a very rigorous/scientific way of solving the problem and, if (small) differences in performance really count, you should solve this hyper-parameter optimization problem more rigorously.

Yes, exactly... I wasn’t disagreeing at all... Just saying the same thing a little differently and in a way I find my students understand it better.. :)

I finally grasped the concept of word embedding. Thanks to @nbro, after reading the 2 articles s/he recommended

What Are Word Embeddings for Text? and

Word embeddings

the 1st article gives me a good idea about the big picture of the Word Embeddings; whereas the 2nd article is actually the one which clears my mind.
I am an visual person, I understand things better if I could see how the things, in this case the Word Embeddings, look like(This answered my 2nd questions).

After seeing this image, my 1st question is answered and I realized that Word Embeddings is a 2 dimensional array where the number of rows of the array is decided by the number of unique words in your vocabulary and the columns/width is decided by yourself. Normally between 8 up to 1024 according to the 2nd article.
The columns/width within the course I am learning from is called embedding_dim, which I found hard to comprehend. Since each word embedding is a vector (this answered my 3rd question), for example the cat is [1.2, -0.1, 4.3, 3.2], and the vector is a meta concept for me which is easy to understand, I would like to call the embedding_dim : embedding_vector_width or embedding_vector_length.
For the 256 hidden features, how many of them would be enough, I think it's the same concept of how to figure out how many embedding_vector_width should be.


text:
Intuitively, how does it make sense to take an action $A'$ when the environment already ended?
The update equation for SARSA is $Q(S,A) = R + \gamma Q(S',A')$. Consider this: I take an action $A$ that leads to the terminal state. Now my $S'$ would be one of the terminal states. So...

Intuitively, how does it make sense to take an action $A'$ when the environment already ended? Or is this something you just do anyway?

Once a terminal state-action pair is reached, you update the previous state-action pair and then start the game loop all over again. But this means that the terminal state-action pair ($Q(S',A')$ in my example) is never updated. So, if your initial estimate of $Q(S',A')$ was wrong, you would never be able to fix it which would be very problematic. (And you can't set all the terminal values to zero because you are using function approximators)

So, how do I resolve these issues?

Intuitively, how does it make sense to take an action A' when the environment already ended?

It doesn't make sense, in that nothing can happen once the agent reaches a terminal state. However, it is often modelled as an "absorbing state" where the action is unimportant (either null or value ignored) with value by definition of $0$.

And you can't set all the terminal values to zero because you are using function approximators

The value is zero by definition. There is no need to approximate it. So don't use function approximators for action values in terminal states.  When $S'$ is terminal, the update becomes:
$Q(S,A) \leftarrow Q(S,A) + \alpha(R - Q(S,A))$
Look at any implementation of Q learning and you will see a conditional calculation for the update value, that uses some variant of the above logic when $S'$ is terminal. For OpenAI Gym environments for instance, it will use the done flag.


text:
What exactly is the eigenspace of a graph (in spectral clustering)?
When we find the eigenvectors of a graph (say in the context of spectral clustering), what exactly is the vector space involved here? Of what vector space (or eigenspace) are we finding the eigenvalues of?

Well, I am not really familiar with these clustering algorithms, but aren't you actually finding the eigenvectors of matrices such as the adjacency or similarity matrices of the graph? See also https://en.wikipedia.org/wiki/Spectrum_of_a_matrix.

Yes we are, but these adjacency matrices are transformations from one vector space to another. I wanted to know if there exists any interpretation of either this  transformation or the domain and range vector spaces  in terms of the original graph.

In spectral clustering we not find the eigenvectors of a graph (a graph is not a matrix) but the eigenvalues/eigenvectors of the Laplacian matrix related to the adjacency matrix of the graph:
graph => adjacency matrix => Laplacian matrix => eigenvalues (spectrum).
The adjacency matrix describes the "similarity" between two graph vertexs. In the most simple case (undirected unweighted simple graph), a value "1" in the matrix means two vertex joined by an edge, a value "0" means no edge between these vertex.
So, the space under the adjacency matrix is the space of connectivity, being row "i" of a column vector a measure of the connectivity with vertex "i". In other words, the adjacency and Laplacian matrix map from vertexs to vertex connectivity.
Example
Assume a simple graph with 3 vertex {1,2,3} and edges (1,2) and (2,3). The respective Laplacian matrix is:
$$
A=\begin{pmatrix}
1 & -1 & 0\\
-1 & 2 & -1\\
0 & -1 & 1
\end{pmatrix}
$$
a) vertex 1, than in vertex space is (1,0,0) maps to:
$$
A\begin{pmatrix}
1\\
0\\
0
\end{pmatrix}
=
\begin{pmatrix}
1\\
-1\\
0
\end{pmatrix}
$$
if we analyze the product result, component by component, it means:

vertex 1 is connected to 1 node.
vertex 2 is connected to vertex 1
vertex 3 is not connected to vertex 1.

b) the set of vertexs 1 and 2, that is represented in vertex space as (1,1,0), maps to:
$$
A\begin{pmatrix}
1\\
1\\
0
\end{pmatrix}
=
\begin{pmatrix}
0\\
1\\
-1
\end{pmatrix}
$$
meaning that:

vertex 1 is internal or external to the set {1,2}, not frontier (in this concrete case, it is internal: belongs to set and has no edge with any node out of the set).
vertex 2 is a vertex in the set and connected to one vertex out of the set (internal frontier).
vertex 3 is a vertex not in the set but connected to it (external frontier).

Finally, see what happens if multiply (inner/scalar product) previous result by the vertex vector again:
$$
\begin{pmatrix}
1 & 1 & 0
\end{pmatrix}
A\begin{pmatrix}
1\\
1\\
0
\end{pmatrix}
= 1
$$
it gives the number of edges that connects the set of nodes {1,2} with the remainder graph.

Thank you for this beautiful answer! I have one follow up question. As you have told, we see the Laplacian as a linear transformation from the vertex space to the connectivity space. Are vertex and connectivity spaces vector spaces? Do they have an algebra equivalent to closure properties(like + and scalar multiplication)? If yes, how are these properties defined?

@ManishKausikHariBaskar: yes, they are. Fiedler value and vector is an example of its application. The problem that surpasses my mathematical knowledge is the meaning of a vertex vector not-unary (component values different of 0 and 1), as the ones present in the eigenvectors of the Laplacian. Could be something to ask in math stack exchange.


text:
What could cause a big fluctuation of the loss in the last epochs of training an AlexNet?
I am training an AlexNet neural network, with about 12000 images which 80% is for training, 10% is for validation and another 10% is for testing.
I have a problem in my plots. There is a big fluctuation in epoch 47,
how can I have a smooth plot? What is the problem?

I tried to increase my validation data because the fluctuation was for validation loss. but nothing changed.
I decreased learning rate, but it stucks in a local optimum.

I solved my problem with data augmentation and decreasing learning rate value and more epochs.


text:
How is the performance of a model affected by adding a ReLU to fully connected layers?
How significant is adding a ReLU to fully connected (FC) layers? Is it necessary, or how is the performance of a model affected by adding ReLU to FC layers?

ReLU is piecewise linear function that outputs the received input directly if it's positive, or outputs a zero. i.e., $max(0, x)$

How significant is adding relu to full connected layers?
ReLU, being an activation function, will determine what the output of the nodes in your FCs are. Since it's a non-linear function, one significance is it will allow the nodes in your model to learn  complex mappings between the inputs and the outputs. Compared to using a linear function, it will allow back-propagation since it has a derivative, allowing the neural network to have the advantage of stacking of multiple FC layers.
Is it necessary?
ReLU (and non-linear activation functions in general) will introduce non-linear properties in a neural network that enables it to learn more complex arbitrary structures in the inputs. Without activation functions between the layers, your neural network will simply be a linear function, regardless of the number of layers it has. Why? A linear function + linear function gives a linear function. Additionally, see this answer.
How is the performance affected by adding ReLU?
Compared to no activation function at all, it will be slower to train but will only behave like a linear regression model. So ReLU will increase the power of the model by making it non-linear.
However, compared to other non-linear activation functions like tanH, ReLU will speed up training as (1) its computation step is cheaper i.e., $0.0$ or $x$ without additional operations (2) its gradient just depends on the sign of the input $x$. See this answer


text:
Should we also shuffle the test dataset when training with SGD?
When training machine learning models (e.g. neural networks) with stochastic gradient descent, it is common practice to (uniformly) shuffle the training data into batches/sets of different samples from different classes. Should we also shuffle the test dataset?

There is no point to shuffle the test or validation data. It's only done in the training time.

Short answer
Shuffling affects learning (i.e. the updates of the parameters of the model), but, during testing or validation, you are not learning. So, it should not make any difference whether you shuffle or not the test or validation data (unless you are computing some metric that depends on the order of the samples), given that you will not be computing any gradient, but just the loss or some metric/measure like the accuracy, which is not sensitive to the order or the samples you use to compute it. However, the specific samples that you use affects the computation of the loss and these quality metrics. So, how you split your original data into training, validation and test datasets affects the computation of the loss and metrics during validation and testing.
Long answer
Let me describe how gradient descent (GD) and stochastic gradient descent (SGD) are used to train machine learning models and, in particular, neural networks.
Gradient descent (GD)
When training ML models with GD, you have a loss (aka cost) function $L(\theta; D)$ (e.g. the cross-entropy or mean squared error) that you are trying to minimize, where $\theta \in \mathbb{R}^m$ is a vector of parameters of your model and $D$ is your labeled training dataset.
To minimize this function using GD, you compute the gradient of your loss function $L(\theta; D)$ with respect to the parameters of your model $\theta$ given the training samples. Let's denote this gradient by $\nabla_\theta L(\theta; D) \in \mathbb{R}^m$. Then we perform a step of gradient descent
$$
\theta \leftarrow \theta - \alpha \nabla_\theta L(\theta; D) \label{1}\tag{1}
$$
Stochastic gradient descent (SGD)
You can also minimize $L$ using stochastic gradient descent, i.e. you compute an approximate (or stochastic) version of $ \nabla_\theta L(\theta; D)$, which we can denote as $\tilde{\nabla}_\theta L(\theta; B) \approx \nabla_\theta L(\theta; D)$, which is typically computed with a subset of $B$ of your training dataset $D$, i.e. $B \subset D$ and $|B| < |D|$. The step of SGD is exactly the same as the step of GD, but we use $\tilde{\nabla}_\theta L(\theta; B)$
$$
\theta \leftarrow \theta - \alpha \tilde{\nabla}_\theta L(\theta; B) \label{2}\tag{2}
$$
If we split $D$ into $k$ subsets (or batches) $B_i$, for $i=1, \dots, k$ (and these subsets usually have the same size, i.e. $|B_i| = |B_j|, \forall i$, apart from one of them, which may contain fewer samples), then the SGD step needs to be performed $k$ times, in order to go through all training samples.
Sampling, shuffling, and convergence
Given that $\tilde{\nabla}_\theta L(\theta; B_i) \approx \nabla_\theta L(\theta; D), \forall i$, it should be clear that the way you split the samples into batches can affect learning (i.e. the updates of the parameters).
For instance, you could consider your dataset $D$ as an ordered sequence/list, and just split it into $k$ sub-sequences. Without shuffling this ordered sequence before splitting, you will always get the same batches, which means that, if there's some information associated with the specific ordering of this sequence, then it may bias the learning process. That's one of the reasons why you may want to shuffle the data.
So, you could uniformly choose samples from $D$ to create your batches $B_i$ (and this is a way of shuffling, in the sense that you will be uniformly building these batches at random), but you can also sample differently and you could also re-use the same samples in different batches (i.e. sampling with replacement). Of course, all these approaches can affect how learning proceeds.
Typically, when analyzing the convergence properties of SGD, you require that your samples are i.i.d. and that the learning rate $\alpha$ satisfies some conditions (the Robbins–Monro conditions). If that's not the case, then SGD may not converge to the correct answer. That's why sampling or shuffling can play an important role in SGD.
Testing and validation
During testing or validation, you are just computing the loss or some metric (like the accuracy) and not a stochastic gradient (i.e. you are not updating the parameters, by definition: you just do it during training). The way you compute the loss or accuracy should not be sensitive to the order of the samples, so shuffling should not affect the computation of the loss or accuracy. For instance, if you use the mean squared error, then you will need to compute
\begin{align}
L(\theta; D_\text{test})
&= \operatorname {MSE} \\
&= {\frac {1}{n}}\sum _{i=1}^{n}(f_\theta(x_i)-{\hat {y_{i}}})^{2}\\
&= {\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-{\hat {y_{i}}})^{2}
\end{align}
where

$f_\theta$ is your ML model
$x_i$ is the $i$th input
$y_{i}$ is the true label for input $x_i$
$\hat {y_{i}}$ is the output of the model
$n$ is the number of samples you use to compute the MSE

This is an average, so it doesn't really matter whether you shuffle or not. Of course, it matters which samples you use though!
Further reading
Here you can find some informal answers to the question "Why do we shuffle the training data while training a neural network?". There are other papers that partially answer this and/or other related questions more formally, such as this or this.


text:
What is the definition of a loss function in the context of neural networks?
I have read what the loss function is, but I am not sure if I have understood it. For each neuron in the output layer, the loss function is usually equal to the square of the difference value of the neuron and the result we want. Is that correct?

A loss function is what helps you "train" your neural network to do what you want it to do. A better way to word it to begin with would be an "objective" function. This function describes what objective you'd like your neural network to fit to (or to be good at).
The loss function that you've described is "squared error", which, as the name suggests, is the squared difference between the expected output and the output from the neural network. This trains the network to match the expected output value.
Other loss (or "objective") functions could train your network to look for different things. For example, training on cross entropy loss helps your network learn certain probabilities. That's why it's usually used for classification, like when you want to determine which digit from 0-9 was fed into your MNIST classifier.


text:
How can I improve the performance of my approach to solving a 1-player version of the card game "The Game" by Steffen Benndorf?
I would like to create an AI for the 1 player version of the card game called "The Game" by Steffen Benndorf (rules here: https://nsv.de/wp-content/uploads/2018/05/the-game-english.pdf).
The game works with four rows of cards. Two rows are in ascending order (numbers 1–99), and two rows are in descending order (numbers 100–2). The goal is to lay as many cards as possible, all 98 if possible, in four rows of cards. The player can have a maximum of 8 cards in his hand and has to play at least 2 cards before drawing again. He can only play a greater value on an ascending row and a smaller value on a descending row with one single exception that lets him play in the reverse order: whenever the value of the number card is exactly 10 higher or lower.
I already implemented a very simple hard-coded AI that just picks the card with the smallest difference and prioritizes a +10/-10 play when possible. With some optimizations, I can get the AI to score 20 points (the number of cards left) on average which is decent (less than 10 points in an excellent score) but I'm stuck there and I would like to go further.
As there is randomness because of the draw pile, I was wondering if it was possible to implement a robust and not hard-coded AI to play this game.
Currently, my AI is playing piecemeal with a very simple heuristic. I do not see how to improve this heuristic, so I am wondering if it is possible to improve the performance by having a view over several turns for example. But I don't see how to simulate the next rounds since they will depend on the cards drawn.

What do you mean by "robust and not hard coded"? There are two high-level game constructs that game-playing AI systems use - evaluation (heuristics, such as your rules for picking plays) and search (looking ahead at possible outcomes). You can use a lot of different approaches for each part - e.g. machine learning to establish heuristic scores. Together these combine to create a wide range of decision and planning algorithms. It's a bit much to give an overview of all possibilities, so it would help to understand what kind of thing you are looking for in more detail

Currently my ia is playing piecemeal with a very simple heuristic. I do not see how to improve this heuristic so I am wondering if it is possible to improve the performance by having a view over several turns for example. But I don't see how to simulate the next rounds since they will depend on the cards drawn.

There are a few different ways to improve on your simple heuristic approach, but they mostly resolve to these three things:

Find a better heuristic. This could be done by calculating probabilities of results, or running loads of training simulations and somehow tuning the heuristic function.

Look-ahead search/planning. There are many possible search algorithms. Most rely on you being able to simulate the impact of future decisions before taking them.

Take account of more player knowledge. So far your simple heuristic does not take account of which cards have already been played (thus which values remain to be drawn).

Currently my AI is playing piecemeal with a very simple heuristic. I do not see how to improve this heuristic so I am wondering if it is possible to improve the performance by having a view over several turns for example. But I don't see how to simulate the next rounds since they will depend on the cards drawn.

I think the main conceptual barrier you have to improvements is how to account for the complex behaviour of probabilities for drawing specific useful cards. There are a few ways to do this, but I think the simplest would be some kind of rollout (simulated look ahead), which might lead to more sophisticated algorithm such as Monte Carlo Tree Search (MCTS).
Here's how a really simple variant might work:

For each possible choice of play in the game that you are currently looking at:

Simulate the remaining deck (shuffle a copy of the known remaining cards)

Play a simulation (a "rollout") to the end of game against the simulated deck using a simple heuristic (your current greedy choice version should be good as long as it is fast enough, but even random choices can work). Take note of the final score.

Repeat 1.1 and 1.2 as many times as you can afford to (given allowed decision time). Average the result and save it as a score for the choice of play being considered.

Instead of choosing the next play by your heuristic, choose the one that scores best out of all the simulations.

This statistical mean of samples works in a lot of cases because it avoids the complexity and time-consuming calculations that would be required to make a perfect decision analytically from probability theory. The important things it does in your case is look-ahead planning plus taking account of additional knowledge that the player has about the state of the game.
MCTS is like the above but nested so that the simulations are made from multiple starting points.
In terms of robustness, provided you run enough rollouts per decision to be confident about the mean scores, then it should be OK.


text:
Is it possible to perform neuroevolution without a fitness function?
My question is about neuroevolution (genetic algorithm + neural network): I want to create artificial life by evolving agents. But instead of relying on a fitness function, I would like to have the agents reproduce with some mutation applied to the genes of their offspring and have some agents die through natural selection. Achieve evolution in this manner is my goal.
Is this feasible? And has there been some prior work on this? Also, is it somehow possible to incorporate NEAT into this scheme?
So far, I've implemented most of the basics in amethyst (a parallel game engine written in Rust), but I'm worried that the learning will happen very slowly. Should I approach this problem differently?

How can you assess the quality of any solution without a measure of quality, which, in the context of genetic algorithms, is known as fitness function (but can take any form, really)? You need some kind of fitness function in genetic algorithms. Mutations alone just change the solutions, but how do you know that the new solutions are better than the previous ones? You cannot know this without a fitness/performance function, so you cannot also logically decide which individuals to kill before the next generation.

You do not always need an explictly coded fitness function to perform genetic algorithm searches. The more general need is for a selection process that favours individuals that perform better at the core tasks in an environment (i.e. that are "more fit"). One way of assessing performance is to award a numerical score, but other approaches are possible, including:

Tournament selection where two or more individuals compete in a game, and the winner is selected.

Opportunity-based selection, where agents in a shared environment - typically with limited resources and chances to compete - may reproduce as one of the available actions, provided they meet some criteria such as having collected enough of some resource. I was not able to find a canonical name for this form of selection, but it is commonly implemented in artificial life projects.

A key distinction between A-life projects and GA optimisation projects is that in A-life projects there is no goal behaviour or target performance. Typically A-life projects are simulations with an open ended result and the developer runs a genetic algorithm to "see what happens" as opposed to "make the best game-player". If your project is like this then you are most likely looking for the second option here.
To discover more details about this kind of approach, you could try searching "artifical life genetic algorithms" as there are quite a few projects of this type published online, some of which use NEAT.
Technically, you could view either of the methods listed above as ways of sampling comparisons between individuals against an unknown fitness function. Whether or not a true fitness function could apply is then partly a matter of philosophy. More importantly for you as the developer, is that you do not have to write one. Instead you can approximately measure fitness using various methods of individual selection.

So far I've implemented most of the basics in amethyst (a parallel game engine written in rust), but I'm worried that the learning will happen very slowly. Should I approach this problem differently?

It is difficult to say whether you should approach the problem differently. However, the biggest bottlenecks against successful GA approaches are:

Time/CPU resources needed to assess agents.

Size of search space for genomes.

Both of these can become real blockers for ambitious a-life projects. It is common to heavily simplify agents and environments in attempts address these issues.

So, can we say that in these cases there is not a fitness function, or that we don't need to define it explicitly?

@desertnaut Yes. You could potentially twist the definition of a fitness function to match those selection methods and claim that there is one. However, I think it is simpler to say that there is not one. Instead there is some threshold to being selected, such as beating an opponent in a game or meeting a prospective mate whilst having enough resources. You do still need to define the event or threshold that makes the selection.

Thanks, approach two is what I was talking about.
My primary problem was also that I couldn't find a canonical name for this and therefore I can't really do any research on this topic. Do you know of any resources where I could learn some more?

@LU15.W1R7H I would suggest searching for "artificial life genetic algorithms"

As it is, the answer seems a few far from the main point of the question. I think it will improve a lot, and be a very useful answer, if it starts by the "artificial life genetic algorithms" reference and resumes the main points of the state of art applicable to this question.

@pasabaporaqui You're correct that your title would have been more fitting. But the whole problem with this question was, that I wasn't sure how to call the problem. As Neil said, there is no canonical name for what I'm trying to accomplish.

I think this answer is highly misleading or even wrong. How can you measure the quality of solutions without a measure of quality, which, in the context of genetic algorithms, is known as fitness function (which can take any form, really)? If you look at the pseudocode of the tournament selection they even write "choose the best individual". How can you choose the best solution without a fitness function? See my comment under the post for other details.

Let us continue this discussion in chat.

@nbro: I've re-worded the answer to try and make it more disctinct between "a fitness function exists always in theory" (I don't believe it always does in a useful sense, but that is not part of this answer which tries to give OP some practical solutions) and "you have to write a fitness function in order to develop genetic algorithms" (which is demonstrably not true). More details of my thinking and link to teaching example referencing A-life saying much the same thing are in the chat

@NeilSlater Right, you may not necessarily need to "code" it (procedurally), but let's say that it somehow needs to exist and you somehow need to use it for selection. I think now that your answer is not so misleading with respect to the existence of or need for a fitness function, but I would like to note that tournament selection actually requires a fitness, so I wouldn't give it as an example of a way of assessing the quality/performance that doesn't require a fitness. Tournament selection is, as the name says, a selection procedure, defined as a function of fitness [continued]

[continued] as the pseudocode suggests (i.e. you choose the best, i.e. according to the fitness, individual with probability $p$, then the second-best individual with some other probability, and so on)

@nbro:  The wikipedia pseudocode gives a very generic view of tournament selecton. Tournament selection needs an internal ranking between the opponents who are randomly selected from the whole population. It can be extremely minimal, e.g. "winner = 1, loser =0" for a two-player game. That is not the same as the fitness function over the population (which might be analogous to the ELO score). Again, importantly, the OP would not need to code such a function, they can just pick the winner of each game directly in a selection process, oblivious to any "scoring"

@NeilSlater Well, yes, you need a way of ordering the solutions according to their "quality", and that way of evaluating the quality is typically called fitness function in genetic algorithms. The way you calculate fitness, of course, depends on different factors, including how you represent the solutions (i.e. genotypes) and your goal (i.e. what you are trying to optimize).

@nbro: Another link that differentiates A-life by calling out that when a fitness function applies: https://en.wikipedia.org/wiki/Artificial_life quote: "Evolutionary algorithms are a practical application of the weak alife principle applied to optimization problems. Many optimization algorithms have been crafted which borrow from or closely mirror alife techniques. The primary difference lies in explicitly defining the fitness of an agent by its ability to solve a problem"

How can you assess the quality of any solution without a measure of quality, which, in the context of genetic algorithms, is known as fitness function? The term fitness function is due to the well-known phrase "Survival of the Fittest", which is often used to describe the Darwinian theory of natural selection (which genetic algorithms are based on). However, note that the fitness function can take any form, such as

How well this solution performs in a game? (in this case, solutions could, for example, be policies to play a game), or
How close this solution is to a minimum/maximum of some function $f$ (more precisely, if you want to find the maximum of the function $f(x) = x^2$, then individuals are scalars in $\hat{x} \in \mathbb{R}$, and the fitness could be determined by $f'(\hat{x})$ or by how big $f(\hat{x})$ with respect to other individuals); check how I did it here)?

The definition of the fitness function depends on what problem you want to solve and which solutions you want to find.
So, you need some kind of fitness function in genetic algorithms to perform selection in a reasonable way, so that to maintain the "best solutions" in the population. More precisely, while selecting the new individuals for the new generation (i.e. iteration), if you don't use a fitness (which you can also call performance, if you like) function to understand which individuals deserve to live or die, how do you know that the new solutions are better than the previous ones? You cannot know this without a fitness/performance function, so you cannot also logically decide which individuals to kill before the next generation. Mutations alone just change the solutions, i.e. they are used to explore the space of solutions.
Genetic algorithms are always composed of

a population of solutions/individuals/chromosomes (i.e. usually at least $2$ solutions)
operations to randomly (or stochastically) change existing solutions to create new ones (typically mutations and crossovers)
a selection process that selects the new solutions/individuals for the next generation (or to be combined and mutated)
a fitness function to help you decide which solutions need to be selected (or even combined and mutated)

For more info about genetic algorithms or, more generally, evolutionary algorithms, take a look at chapter 8 and 9 of the book Computational Intelligence: An Introduction by Andries P. Engelbrecht.


text:
Is there an equivalent model to the Hidden Markov Model for continuous hidden variables?
I understand that Hidden Markov Models are used to learn about hidden variables $z_i$ with the help of observable variables $\xi_i$. On Wikipedia, I read that while the $\xi_i$'s can be continuous (say Gaussian), the $z_i$'s are discrete. Is this necessary, and why? Are there ways in which I could extend this to continuous domains?

Kalman filter is what you're looking for.
According to Wikipedia:

The Kalman filter may be regarded as analogous to the hidden Markov model, with the key difference that the hidden state variables take values in a continuous space (as opposed to a discrete state space as in the hidden Markov model).


text:
Is there a common way to build a neural network that seeks to extract spatial and temporal information simultaneously?
Is there a common way to build a neural network that seeks to extract spatial and temporal information simultaneously? Is there an agreed up protocol on how to extract this information?
What combination of layers works: convolution + LSTM? What would be the alternatives?

Yes, there are different ways. What I think you are looking for is under the research field of Localization and Mapping. Which divides in the following subfields:

For getting current (the robot) position and trajectory go to models for Odometry Estimation
For getting a representation of the world around the robot go to models for Mapping
If you want both of them (I am guessing you want). Go for SLAM (Simultaneous Localization and Mapping) models

Here it is the amazing survey that links you to tons of papers with different models for each category. If you want to know what are the most common architectural blocks (LSTM, ConvLSTM, RNN...) used for your problem, read the most promising papers under your target category.
References:
Survey: https://arxiv.org/abs/2006.12567


text:
What do we mean by "infrequent features"?
I am reading this blog post: https://ruder.io/optimizing-gradient-descent/index.html. In the section about AdaGrad, it says:

It adapts the learning rate to the parameters, performing smaller updates (i.e. low learning rates) for parameters associated with frequently occurring features, and larger updates (i.e. high learning rates) for parameters associated with infrequent features.

But I am not sure about the meaning of infrequent features: is it that the value of a given feature changes rarely?

We will describe the input to the network as a vector, called features vector. Each component of this vector is usually related to some "real world" information, by example "age of the person", "number of atoms", "...".
In very usual situations, a specific component of the input vector will have near than always the same value. This is more usual in binary components or components that has a small set of possible values.
However, usually in the cases where this component has a value different from the most usual one, this component is very important and informative.
These values of this kind of components are called infrequent features.
(example: "rains?" is in my city 99.9% of time "false". However, when it is true, it is a key factor to all questions about the behavior of the population).
The problem with these features: as unusual values are infrequent, the net has few chances to learn from them, and some learning algorithms could fail to give them the weight that they must (taken into account that, as has been said, these components are very important when they take a value different to the most frequent one).
Some adaptive learning rate algorithms as AdaGrad tries to solve this issue.

Thank you very much for your answer, it is very clear :)

OK thank you for the advice ! Edit: for now my vote is counted but not taken into account because i am a new user, but i do appreciate your help


text:
How can I determine whether a video's frame is realistic (was recorded by a camera) or contains computer-generated graphics?
Given a video, I'm trying to classify whether it is a graphical (computer-generated) or realistic scene. For instance, if it contains computer-generated graphics, credit, moving bugs, blue screen, etc. it will be computer-generated graphics, and if it is a realistic scene captured by camera, it will be a realistic scene.
How can we achieve that with AI? Do we have any working solutions available?
Some examples of graphical scenes:

Why not you try ELA(Error Level Analysis). Using ELA you can identifyedited scenes and non edited scenes.

Since neural networks are very good at finding patterns, you can try to just train a neural network (e.g. CNN) on you examples given the labels whether it is real or CGI.  If you want then to understand what your NN has learned, you can visualize its layers

Should it be CNN only, or LSTM with multiple frames?! I need it to be lightweight.

It depends. If you have a series of images (i.e. a video), you can use LSTM to improve stability. But I would suggest starting simple. To make it lightweight, you can also downscale the images to smaller resolution and make them b&w. You can also use maxpooling layers/strides in your CNN

Umm I'm not yet much into architecting deep layers. If you could post a sample in python using Keras, it would be great.

I posted my answer. Feel free to ask me if anything is unclear. If the answer is helpful, don't forget to accept it.

As per your requirements, I would suggest that you start with any simple CNN network.

CNNs take advantage of the hierarchical pattern in data and assemble
more complex patterns using smaller and simpler patterns. Therefore,
on the scale of connectedness and complexity, CNNs are on the lower
extreme.

Here is a Keras example:
model = models.Sequential()
model.add(layers.Conv2D(32, kernel_size=(3, 3), activation='relu', input_shape=image_shape))
model.add(layers.MaxPooling2D((2, 2)))
model.add(layers.Conv2D(64, kernel_size=(3, 3), activation='relu'))
model.add(layers.MaxPooling2D((2, 2)))
model.add(layers.Conv2D(64, kernel_size=(3, 3), activation='relu'))
model.add(layers.Flatten())
model.add(layers.Dense(64, activation='relu'))
# output layer
model.add(layers.Dense(1))

where image_shape is the resolution and number of channels of images (e.g. 128x128x3 for RGB images). I also suggest you downscaling the images to a lower resolution. You will also have to crop the images as they must all be the same image_shape.
Also take a look at the MaxPooling2D  and BatchNormalization layers.
Since you only have real and CGI images, this becomes a binary classification problem. Therefore you can have a single output (0 - CGI, 1 - real). Such problems can be solved with BinaryCrossentropy loss.
model.compile(loss=losses.BinaryCrossentropy(from_loits=True), optimizer='adam')

Finally, you can fit your model
history = model.fit(train_images, train_labels, epochs=1000, validation_data=(test_images, test_labels))

You can find a complete example here.
Please note that depending on your data, the model can become biased if your dataset is unbalanced. That is, if all of your CGI images have text, and only a small fraction of the real images also have text, they might be misclassified. Therefore, I recommend that you visualize your model to better understand what it has learned. Here is an example of such a problem we faced at our university.
There are also more advanced CNN architectures such as ResNet, VGG or YOLO. You can also extend your model with time series (i.e. video) using LSTM or GRU architecture.

Thanks. I guess now i need to collect a few hundreds of samples for dataset. One qq: what's the rationale behind the node size 32,64,64? If I add another layer, it should go 128?

And is there any relationship between the number of layers and dataset size? Jut some intuition?

As far as I know, there is no relationship between the number of layers and dataset size. More layers mean more  hidden features. ResNet and VGG networks use up to 100 hidden layers.

32, 64 and 64 are the number of filters. Filters present hidden features of the images. The first layer will usually be activated by straight lines (so the layer should be small), whereas the last layers will be activated by some abstract features and colors. Basically, you decide how many filter layers to contain.

Thanks. One last question: Do you know of any open dataset for this?!

I haven't come across such a dataset


text:
Why are there two versions of softmax cross entropy? Which one to use in what situation?
I have seen 2 forms of softmax cross-entropy loss and are confused by the two. Which one is the right one?
For example in this Quora answer, there are 2 answers:

$L(\mathbf{w})=\frac{1}{N} \sum_{n=1}^{N} H\left(p_{n}, q_{n}\right)=-\frac{1}{N} \sum_{n=1}^{N}\left[y_{n} \log \hat{y}_{n}+\left(1-y_{n}\right) \log \left(1-\hat{y}_{n}\right)\right]$

$\mathrm{L}(y, \hat{y})=-\Sigma y(i) \log \hat{y}(i)$, which is only the first part of the version one.

It's the same thing, first version is the special case of the more general one. In the first case you only have two classes, it's binary cross-entropy, and they also included iteration over batch of samples. In the second case you have multiple classes and in the current form it's only for a single sample.
In the first case there is only one output, if you had two outputs it would have been
\begin{equation}
-\frac{1}{N} \sum_{n=1}^N \sum_{j=1}^2 y_{n,j} \log(\hat y_{n,j})
\end{equation}
where $n$ iterates over batch samples, and $j$ over two classes. The reason why it was written like that is that if you have two classes you can have only one output because you can immediately conclude about probability of the second class if you have the probability of the first class, it would simply be $p_1 = 1-p_0$.
In the second case, with batch samples included, it would be
\begin{equation}
 -\frac{1}{N} \sum_{n=1}^N \sum_{j=1}^c y_{n,j} \log(\hat y_{n,j})
\end{equation}
wheren $n$ iterates over batch samples, and $j$ over $c$ output classes.


text:
Is reinforcement learning only about determining the value function?
I started reading some reinforcement learning literature, and it seems to me that all approaches to solving reinforcement learning problems are about finding the value function (state-value function or action-state value function).
Are there any algorithms or methods that do not try to calculate the value function but try to solve a reinforcement learning problem differently?
My question arose because I was not convinced that there is no better approach than finding the value functions. I am aware that given the value function we can define an optimal policy, but are there not other ways to find such an optimal policy?
Also, is the reason why I don't encounter any non value-based methods that these are just less successful?

There are many algorithms that are not based on finding a value function. The most common ones are policy gradients. These methods attempt to map states to actions through a neural network. They learn the optimal policy directly, not through a value function.

The important part of the image is when Model-Free RL splits into  Policy Optimization (which includes policy gradients) and Q-Learning. Later you can see the two sections coming back together in algorithms that are a mix of both techniques. Even the bottom three methods in policy optimization involve some form of learning a value function. The best and most advanced algorithms use value function learning and policy optimization. The value function is only for training. Then when the agent is tested, it only uses the policy.
The most likely reason you have only heard of value function methods is because policy gradients are more complicated. There are many algorithms more advanced than ones that only use value functions and policy gradients can learn to operate in continuous actions spaces (an action can be between -1 and 1, like when moving a robot arm) while value functions can only operate with discrete action spaces (move 1 right or 1 left).
Summary: Yes, there are other methods that learn the optimal policy without a value function. The best algorithms use both types of reinforcement learning.
The SpinningUp website has a lot of information about reinforcement learning algorithms and implementations. You can learn more about direct policy optimization there. That is also where I got the image from.
This answer is specific to the most common types of Model-Free RL. There are other algorithms related to the RL problem that do not learn value functions, like inverse reinforcement learning and imitation reinforcement learning.


text:
Why is the perceptron criterion function differentiable?
I'm reading chapter one of the book called Neural Networks and Deep Learning from Aggarwal.
In section 1.2.1.1 of the book, I'm learning about the perceptron. One thing that book says is, if we use the sign function for the following loss function: $\sum_{i=0}^{N}[y_i - \text{sign}(W * X_i)]^2$, that loss function will NOT be differentiable. Therefore, the book suggests us to use, instead of the sign function in the loss function, the perceptron criterion which will be defined as:
$$ L_i = \max(-y_i(W * X_i), 0) $$
The question is: Why is the perceptron criterion function differentiable? Won't we face a discontinuity at zero? Is there anything that I'm missing here?

$\max(-y_i(w x_i), 0)$ is not partial derivable respect $w$ if $w x_i=0$.
Loss functions are problematic when not derivable in some point, but even more when they are flat (constant) in some interval of the weights.
Assume $y_i = 1$ and $w x_i < 0$ (that is, an error of type "false negative").
In this case, function $[y_i - \text{sign}(w x_i)]^2 = 4$. Derivative on all interval $w x_i < 0$ is zero, thus, the learning algorithm has no any way to decide if it is better increase or decrease $w$.
In same case, $\max(-y_i(w x_i), 0) = - w x_i$, partial derivative is $-x_i$. The learning algorithm knows that it must increase $w$ value if $x_i>0$, decrease otherwise. This is the real reason this loss function is considered more practical than previous one.
How to solve the problem at $w x_i = 0$ ? simply, if you increase $w$ and the result is an exact $0$, assign to it a very small value, $w=\epsilon$. Similar logic for remainder cases.

Since we're dealing with real-values variables, it is almost certainly the case that the argument of the function will not be $0$.
If you care strongly about that point, you can just use sub-gradients instead (and we do have sub-gradients for this function, so there is no problem).


text:
How to manually draw a $k$-NN decision boundary with $k=1$ given the dataset and labels?
How to manually draw  a $k$-NN decision boundary with $k=1$ knowing the dataset

the labels are

and the euclidean distance between two points is defined as

This is a rather involved task. What to do from a high-level theoretical perspective might be easy to see, but it's difficult putting that into code from scratch.
Doing this in Python using existing libraries in not too complicated, though.
See for example this tutorial or this StackOverflow post.
Edit:
Theoretically, I would first plot (draw) the points from your dataset in a graph and then watch out for "decision points" half-way in between any two near-by points (from the dataset) from distinct classes.
For the next step, keep in mind those decision points. Given close-by data points from classes (e.g.) A and B, imagine a straight line connecting these two points from separate classes. Next, take the point half-way along that imaginary line (i.e. your decision point) and draw a "soft" line (maybe using pencil instead of pen) orthogonal/perpendicular to that imaginary line which intersects the imaginary line in the decision point.
Do that for all combinations of "reasonably" close points from different classes.
Parts of the lines you have just drawn will define the final decision boundary. Next, think of each line as consisting of multiple elements, which are separated from one another by means of the points of intersection with other drawn lines. In other words, split lines into elements wherever they intersect other lines. Now, decide which of these elements to outline as the eventual decision boundary (finally using a pen instead of pencil). This step simply involves human intelligence and is difficult to describe. Whenever a line's element accurately separates (logically speaking) two classes, indicate it using a pen. Otherwise, if it does not contribute to separating two classes, don't indicate it.
After having indicated the final decision boundary using a pen, simply erase the pencil drawings. Now, you should be left with a decision boundary.
I hope this is clear and accurate enough.

The question is come from a old exam. So the decision boundaries can be drawn by hand. I am not even sure how to do it

Yes, I realized and corrected that already. I went through a few examples and encountered problems with the previous proposal indeed.

ok now, thus I delete my answer. Hint: think about the problem as if each point was an independent class. After draw the perpendiculars, each point is enclosed by a convex polygon formed by these perperndiculars. This is the area the point "owns". Latter, just paint of same color the areas of points with same labels.


text:
Is there a system that automatically designs a set of rules from the examples?
Being by no means an expert in the field, I do however know of solvers such as Z3 that can generate a correct program, provided you can express your constraints as a set of logical rules, such as here.
However, in the example given above, logical rules are designed "by hand" from a set of examples, so the "compilation step" from the examples to the set of rules must be done in the user's head.
Does a system automating this "compilation step" exist (i.e automated rule set deduction from a set of examples), that would allow the user to see and make use of the set of rules?

This is an active research topic.
Consider reading

J.Pitrat's Artificial Beings, the conscience of a conscious machine book

This Understanding machine learning book

old Lenat's papers on Eurisko.

and recent papers such as Learning Structured Embeddings of Knowledge Bases and several others in Artificial Intelligence Journal

about the MILEPOST GCC and Ctuning projects

this paper on Reconciling deep learning with symbolic artificial intelligence: representing objects and relations

My hope is to get funded so that RefPerSys could (in a few years) be able to deduce some rules and metarules.


text:
Why is my Keras prediction always close to 100% for one image class?
I am using Keras (on top of TF 2.3) to train an image classifier. In some cases I have more than two classes, but often there are just two classes (either "good" or "bad"). I am using the tensorflow.keras.applications.VGG16 class as base model with a custom classifier on top, like this:
input_layer = layers.Input(shape=(self.image_size, self.image_size, 3), name="model_input")
base_model = VGG16(weights="imagenet", include_top=False, input_tensor=input_layer)
model_head = base_model.output
model_head = layers.AveragePooling2D(pool_size=(4, 4))(model_head)
model_head = layers.Flatten()(model_head)
model_head = layers.Dense(256, activation="relu")(model_head)
model_head = layers.Dropout(0.5)(model_head)
model_head = layers.Dense(len(self.image_classes), activation="softmax")(model_head)

As you can see in the last (output) layer I am using a softmax activation function. Then I compile the whole model with the categorical_crossentropy loss function and train with one-hot-encoded image data (labels).
All in all the model performs quite well, I am happy with the results, I achieve over 99% test and validation accuracy with our data set. There is one thing I don't understand though:
When I call predict() on the Keras model and look at the prediction results, then these are always either 0 or 1 (or at least very, very close to that, like 0.000001 and 0.999999). So my classifier seems to be quite sure whether an image belongs to either class "good" or "bad" (for example, if I am using only two classes). I was under the assumption, however, that usually these predictions are not that clear, more in terms of "the model thinks with a probability of 80% that this image belongs to class A" - but as said in my case it's always 100% sure.
Any ideas why this might be the case?

Traditional neural networks can be over-confident (i.e. give a probability close to $0$ or $1$) even when they are wrong, so you should not interpret the probability that it produces as a measure of uncertainty (i.e. as a measure of how much it is confident that the associated predicted class is the correct one), as that it is essentially wrong. See this and this answers for more details about this.
Given that this overconfidence is not desirable in many scenarios (such as healthcare, where doctors also want to know how confident the model is about its predictions, in order to decide whether to give a certain medication to the patient or not), the ML community has been trying to incorporate uncertainty quantification/estimation in neural networks. If you are interested in this topic, you could read the paper Weight Uncertainty in Neural Network (2015) by Blundell et al., which proposes a specific type of Bayesian neural network, i.e. a neural network that models the uncertainty over the actual values of the weights, from which we may also quantify/estimate the uncertainty about the inputs. This paper should not be too difficult to read if you are already familiar with the details of variational-autoencoders.
So, the answer to your question is: yes, it's possible that the output probability is close to $1$ because neural networks can be over-confident. (I am assuming that the values returned by tf.keras's predict method are probabilities: I don't remember anymore, so I assumed that you did not make any mistake).
A similar question was already asked in the past here. The accepted answer should provide more details about different types of uncertainty and solutions.

Without more details about the nature of the dataset, it is impossible to know for sure. However, here are a few likely causes:

You were calling predict on training data, not testing data. The network will be a lot more sure about images that it trained on than on images it has never seen before.

Your model overfit the data. This can happen when you use an overly complex model on a small dataset. You may want to experiment with regularization.

You were looking at too small a sample of images. Did you run predict on every image, or just a few? If the latter, it is possible you just picked a sample that the network is very confident about.