text:
How would the probability of a document $P(d)$ be computed in the Naive Bayes classifier?
In naive Bayes classification, we estimate the class of a document as follows
$$\hat{c} = \arg \max_{c \in C}  P(c \mid d) = \arg \max_{c \in C} \dfrac{ P(d \mid c)P(c) }{P(d)} $$
It has been said in page 4 of this textbook that we can ignore the probability of document since it remains constant across classes.

We can conveniently simplify the above equation by dropping the denominator $p(d)$.  This is possible because we will be computing $\dfrac{P(d \mid  c)P(c)}{P(d)}$for each possible class. But $P(d)$ doesn't change for each class; we are always asking about the most likely class for the same document $d$, which must have the same probability $P(d)$.  Thus, we can choose the class that maximizes this simpler
formula
$$\hat{c} = \arg \max_{c \in C}  P(c \mid d) = \arg \max_{c \in C}
 P(d \mid  c)P(c)  $$

Since the value of the document does not influence the choice of the class, naive Bayes algorithm does not consider that.
But, I want to know the value of $P(d)$. Is it $\dfrac{1}{N}$, if total number of documents are $N$? How should I calculate $P(d)$?

I suppose that the frequency of the document in the corpus would be the natural estimate of the probability of that document appearing in the corpus. So, generally, you could have the probability $M_d/N$, where $M_d$ is the number of times the specific document appears in the corpus. So, yeah, I would say that you're right, but I am not an expert on this topic, so I don't know what people are doing in this context (and that's also why I didn't post this as a formal answer).

The probability of "the cat sat on the mat" is high; the probability of "fghkjrthwerwerwec" is low.

$P(d)$ (aka evidence) is a probability of your data (observation) and is defined as follows:
$$
P(d) = \sum_i P(d|c_i)P(c_i)
$$
for all classes $c$.
According to the book, $P(c)=\frac{N_c}{N_{doc}}$ and $P(d|c)$ is a likelihood and, applying the assumptions from the book, can be defined as $P(w_i
|c)=\frac{\text{count}(w_i, c)+1}{\sum_{w \in V}\text{count}(w, c) + |V|}$, where $V$ consists of the union of all the word types in all classes.
Taking the example from Section 4.3 of the book,

Dataset
Cat
Documents

Training
-
just plain boring

-
entirely predictable and lacks energy

-
no surprises and very few laughs

+
very powerful

+
the most fun film of the summer

Test
?
predictable with no fun

we'll get:
$$
P(-) = \frac{3}{5}\\
P(+) = \frac{2}{5}\\
P(S|−) = \frac{2\times 2\times 1}{34^3}\\
P(S|+) = \frac{1\times 1 \times 2}{29^3}\\
P(d) = P(S|−)P(−) + P(S|+)P(+) = 6.1\times 10^{−5} + 3.2\times 10^{−5}
$$

Yes, this seems to make sense (as you're just applying marginalization), although I had not thought about it in this way, probably because I had not read that section of the book, so I didn't know whether the likelihood and evidence were given or how to compute them in this context. In any case, how would this be different from just computing the frequency of the document in the corpus (as the OP and I suggest in the comment above)?

@nbro The denominator is just a normalization constant and hence related to the likelihood times prior. Thus, the sum of the posterior for all categories is always equal to 1, which allows us to judge how confident we are in our predictions.

Yes, I know that the denominator is a normalization constant, but you're not answering my question. So, if someone asked you to estimate the probability of a document, how would you estimate it? Why wouldn't you just compute the frequency of the document in the corpus? That's my question. Yes, sure, you can compute P(d) by marginalizing over $c$, but why wouldn't you simply use the frequency? Anyway, how do you get from $(w_i \mid c)$ to the likelihood? It may be something you should explain more in detail.

@nbro Bayes' rule is difficult to comprehend. I would argue we cannot consider all documents with the same probability. This would only be true if we had exact duplicates in the dataset, which doesn't make any sense. As for $(w_i \mid c)$, it is taken from Eq. 4.12 in the book, which we compute as the fraction of times each word $w_i$ of a sentence $S$  appears among all words in all documents of topic $c$.

Bayes' rule is usually very easy to comprehend. Not sure what you mean by that. Of course, not all documents may have the same probability, but this is reflected in their potentially different frequency. Also not sure why you think that, generally, documents would have the same frequency. Finally, my question was: how do you relate $P(w_i \mid c)$ to $P(d \mid c)$, which is not explained in your answer.


text:
Can some of the weights be fixed during the training of a neural network?
Is it possible to exclude specific layers from the optimization?
For example, let's say I have an input layer, 2 hidden layers, and the output layer. I know there is a perfect solution for my problem with this setup and I already know the perfect weights between the first and the second hidden layer.
Can I have the weights between the first and the second hidden layer be fixed during the training phase?
I understand that I could just not update these specific weights after I computed the backpropagation for the entire network. But if I throw away those specific weights, will this affect the optimization of the rest of my weights?

Yes, you can fix (or freeze) some of the weights during the training of a neural network. In fact, this is done in the most common form of transfer learning (which is described here). I don't know exactly how this affects learning in general. In transfer learning, this is definitely beneficial, as we are freezing the weights that are associated with the learned general features of objects, such as corners (where general here is defined intuitively), which can be useful for other tasks, so, by having them frozen, we reuse them.

You may have more success freezing weights in the central corridor rather than in layers.  The central corridor is the middle of all the layers.  https://medium.com/@mbonsign/training-neural-networks-a-new-perspective-on-core-stability-and-peripheral-learning-5bd7bf3a7fce.

source: Stack Exchange

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

sort: votes


text:
Should I continue training if the neural network attains 100% training accuracy?
I have a neural network where there are two hidden layers. Each hidden layer has 128 neurons. The input layer has 20 inputs, and the output layer has 3 outputs.
I have 1 million records of data. 80% is used to train the network, 20% is used for validation. I run the training for 100000 epochs.
I see that the neural network attains 100% accuracy on the training data after only 12000 epochs.
Should I stop training or continue until all 100000 epochs are complete? Please, explain why.

You don't appear to have enough splits for normal best practice here. There should be a three-way split. How are you selecting between models, and following that how are you assessing accuracy in an unbiased fashion?

As a rule of thumb, generally 100% training accuracy means you've overtrained. Training accuracy isn't what you should be looking at anyway, as mentioned in the other comments, you should be looking at validation accuracy.

First of all, as mentioned by @Neil Slater in the comment - you need to have three splits into the train, validation and test set.
One sometimes disregards the difference between validation and test set. However they serve for different purposes. Here I would like to cite https://machinelearningmastery.com/difference-test-validation-datasets/ :

Validation Dataset: The sample of data used to provide an unbiased
evaluation of a model fit on the training dataset while tuning model
hyperparameters. The evaluation becomes more biased as skill on the
validation dataset is incorporated into the model configuration.
Test Dataset: The sample of data used to provide an unbiased
evaluation of a final model fit on the training dataset.

Secondly, in order to understand what's happening plot jointly the train and validation loss. In case the performance on validation data becomes much worse, that on the training - It is better to terminate training, since it is the indication of overfitting.
A good practice is to use early stopping, there is an implementation of this callback in Tensorflow - https://www.tensorflow.org/api_docs/python/tf/keras/callbacks/EarlyStopping.
It a kind of regularization procedure https://en.wikipedia.org/wiki/Early_stopping.

Does anyone talk about "orders of validation".  Ie, you have your order-0 validation (your training set), your order-1 validation (your validation set, which is used to determine what your model hyperparameters should be), then order-2 validation (your "test" dataset, which is not used to tune hyperparameters, but to determine if you screwed up), your order-3 validation (which you use only if your "test" dataset told you that your result was junk); the idea is that order-N validation is used to validate after previous validations where used as input into your model, which adds bias.

@Yakk Maybe you're talking about k-fold cross-validation?

@nbro No, something different. Yakk is generalizing the difference between test and validation sets. The reason you need two is because your training loop has two levels of nesting. If you somehow needed, say, three more levels of nesting, you'd need 5 of those sets.

As far as I am aware, this idea is not common in ML, but it's possible that something along those lines has been applied. Typically, you use the same validation data for early stopping or/and hyper-parameter tuning. I agree that, if you used a certain validation dataset for hyper-parameter tuning, then selected a specific function using another validation dataset, you could be biased (and the bias would come from the choice of the specific hyper-parameters with the previous val. data, which, of course, also limits the specific function from the specific hypothesis class you can choose).

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


text:
What does it mean by overfitting the test set?
Consider the following statement from p14 of Naive Bayes and Sentiment Classification

While the use of a devset avoids overfitting the test set, having a
fixed training set, devset, and test set creates another problem: in
order to save lots of data for training, the test set (or devset)
might not be large enough to be representative.

I heard about overfitting on train data. A model is said to be overfit on train data if it is giving low train error and high test error.
But, what does it mean overfitting on test set?

Essentially, any data you use to train or develop the model shouldn't be used as test data. In principle, "unseen" data gives a good estimate for the generalisation performance of the model; but this is only valid if the data really is unseen and hasn't been used in the model development process. If you've been tuning a model to increase its accuracy on the test set, then that data has influenced the model, so it's not unseen any more!
An example of what is wrong:

Train a neural network on the training set.
Evaluate the performance on the test set, and then change the parameters of the model in some way to try and increase the test set performance.
Use the best parameters you found, and get a final evaluation of performance on the test set.

To make this procedure legitimate, you should have a three way split: train, dev, test. Do the tuning on the dev set, and then you can get a final estimate of generalisation using the test set.
If you don't do this, you'll generally think your model is a lot more accurate than it actually is. It's just like trying to estimate your generalisation performance from the training set, which I'm sure you know is a bad idea!
This phenomenon is what is sometimes known as overfitting the test set. To see why this name is used, just consider what overfitting the training data is: picking parameters that seem to fit the training data well, but don't generalise well. Likewise, overfitting the test set involves picking hyperparameters that seem to work well, but don't generalise. In each case, the solution is to have an additional set so you can get an unbiased estimate of what's actually happening.

I think the name "dev" is becoming more popular, and is better than "cross validation" because the cv set is often used in the role of test set in other circumstances (such as other stats disciplines than ML). However, worth noting that the alternative names for dev set are "validation", "cross validation" or "cv".

I've never seen the terms "cross-validation" or "cv" being used to refer to the "validation set", but I've seen the term "developmental set" being used to refer to the validation set. Cross-validation typically either refers to k-fold cross-validation, the simple training-test split, or the training-validation-test split approaches.


text:
How to design a neural network with arbitrary input and output length?
I am trying to build a neural network that has an input of $n$ pairs of integer values (where $n$ is random) and a corresponding output of a binary array with length $n$.
The input will be a set of integer value coordinates $[(x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3}), \dots, (x_{50}, y_{50}), \dots]$, where each instance can be of various lengths, like $[(x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3}), \dots, (x_{52}, y_{52})]$ or $[(x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3}), \dots, (x_{101}, y_{101})]$, etc.
The output is a set of binary arrays with each instance having the same length as the corresponding input.

May I know if anyone has any recommendations on what neural network would fit this use case?

A recurrent neural network (RNN, specifically either an LSTM or GRU)  will work well for variable length sequences like you’ve described. Assuming the order of the sequence is meaningful (I.e. you can’t just break up the sequence into individual inputs and associated target value) an RNN model will learn how the sequence of inputs maps to the sequence of outputs.

If the sequence is not meaningful, then the OP could take advantage of that symmetry and sort the items using a consistent rule, which may make the learning task easier.

Look for padding.
There are even versions of it: pre-padding, post-padding.
https://stackoverflow.com/questions/46298793/how-does-choosing-between-pre-and-post-zero-padding-of-sequences-impact-results


text:
In a DDQN architecture, why is the value of a state assumed to be the average of the Q values of the actions?
In a Dueling DQN agent (Wang et al.), the Q function is decomposed as
$$
Q(s, a)=V(s) + A(s, a) - \frac{1}{|A|}\sum_{a'\in \mathcal{A}}A(s, a')
$$
representing the value of the state, plus the advantage of the action, minus the average advantage of all actions available in that state.
However, this formulation means that the value of the given state is skewed, even after subtracting out the mean advantage of all actions available. Why isn't it set up so that the advantage of the best action is 0 (with the other actions' advantages being negative), thus leading to a more accurate $V(s)$?

This is considered in the original paper, but is rejected due to training instability. To quote:

[The average-advantage formulation] increases the stability of the optimization...the advantages only need to change as fast as the mean, instead of having to compensate any change to the optimal action's advantage in [the formulation where $Q(s, a) is normalized with the best action's advantage].

Furthermore, the authors attempt a softmax version, but they find it doesn't perform that differently than the average-advantage version. I couldn't find any additional experiments using this, but it may be worth trying if it is absolutely necessary to obtain an accurate $V(s)$.


text:
Is there any model that is probabilistic but not statistical?
While studying about the n-gram models, I encountered the terms "statistical model" and "probabilistic model" several times.
I got a basic doubt that will there be any probabilistic model that is not statistical restricted to models that works on datasets.
In machine learning, we use datasets. Any model that uses dataset can be called as a statistical model since statistics is a branch of mathematics that tries to find insights related to data.
All the models that calculates probabilities using datasets, for any task, are called (empirical) probabilistic models.
Thus, if I am not wrong, every probabilistic model has to be a statistical model since it uses data. Am I wrong?
Is there any model in literature that is a statistical model but not probabilistic?

First of all, I don't know of any textbook that clarifies these terms, but, although I am not a statistician, in addition to the other answer, one possible way to look at it is as follows.
You use probability theory to model your problem. For example, if it's a classification problem, you could define the conditional probability distribution $p(y \mid x)$, which would compute the probability of a label $y$ given an input $x$. In other words, you assume that there is a probability distribution of the form $p(y \mid x)$ that generates your data, so here $p$ is the "model". If you want to generate images, for instance, you could model the process that generates them as the marginal distribution $p(x)$, which, ideally, would tell you the probability of sampling a specific image $x$. This is the theory. So, no observed data is still involved here. By the way, this is exactly how people usually model the machine learning problems in the sub-field of statistical learning theory.
In practice, you need to estimate these probability distributions. To estimate them, you can use data. The type of data depends, of course, on the problem and model. For example, in the case of $p(y \mid x)$, you may need a  labelled dataset $D$. So, if you estimate $p(y \mid x)$ with $D$ to obtain $\hat{p}(y \mid x)$, then $\hat{p}$ would be a statistical model, in the sense that you estimated it from observed/empirical data. In general, statistics is all about taking data and using it to build "models" that can be used for prediction or forecasting (of future inputs) or inference (i.e. understanding the properties of the data-generating process or probability distribution) or just to compute the so-called "statistics" (hence the name of the field!), such as the "sample average" (i.e. the average of your observe data points, where the "sample" here refers to your dataset of points, which are also sometimes known as "samples", just to make things even more confusing!)
So, let me address your questions and comments, but take my comments below with a grain of salt, because I am not a statistician.

All the models that calculates probabilities using datasets, for any task, are called (empirical) probabilistic models.

To me, this would be a reasonable statement. In this example, you seem to be talking about $\hat{p}(y \mid x)$, which I would also call a probabilistic model, although it's just an estimate of the theoretical/ideal one.

Is there any model in literature that is a statistical model but not probabilistic?

If we follow my reasoning above, initially, if you do not explicitly  model your problem as the estimation of some probability distribution that generated the data, then we would be estimating something from data (so we would be building a statistical model), but it wouldn't be clear whether this "statistical model" is an estimate of some theoretical/probabilistic one. So, I don't really have a definitive answer to your question. I suppose that any statistical model could be modelled with the tools of probability theory, so I would be more inclined to think that the answer to your question is "no".
In addition to what I just said above, if you take a book like Machine Learning: A Probabilistic Perspective, here are a few examples of how the author uses the terms "statistical model" and "probabilistic model". For example, he writes (section 7.3, page 217)

A common way to estimate the parameters of a statistical model is to compute the MLE, which is defined as
$$
\hat{\boldsymbol{\theta}} \triangleq \arg \max _{\boldsymbol{\theta}} \log p(\mathcal{D} \mid \boldsymbol{\theta})
$$

So, in this case, is $p$ a statistical or probabilistic model, according to my definitions above? Of course, ignoring the potentially different notation being used here to refer to a statistical model, i.e. without the $\hat{}$, I think that this $p$ could be considered a statistical model (in the sense that $\hat{\boldsymbol{\theta}}$ would be estimated from the observed dataset $\mathcal{D}$, assuming it's the observed dataset and not some random variable) but at the same time also a probabilistic one, in the sense that, here, we are assuming that we have some kind of "theoretical likelihood". In any case, the likelihood is something that can make this discussion even more confusing, because the likelihood is not really a probability distribution (if you integrate with respect to the parameters). In any case, here, you could consider $p(\mathcal{D} \mid \boldsymbol{\theta})$ as a (Bayesian) probabilistic model, i.e. you assume that there's some parameters that generate the data and, if you consider it as a conditional probability distribution over the data, rather than the parameters, then this would be  consistent with what I said above.
Here's another example (section 1.3.1, p. 10).

In this book, we focus on model based clustering, which means we fit a probabilistic model to the data, rather than running some ad hoc algorithm.

This usage also seems consistent with my description above. Here, I interpret the part "we fit a probabilistic model to the data" as "we estimate the probability distribution given the data".
Or, in section 1.4.1 (p. 16)

In this book, we will be focussing on probabilistic models of the form $p(y \mid x)$ or $p(x)$, depending on whether we are interested in supervised or unsupervised learning respectively.

The discussion can become even more complicated, if we start to consider parametric vs non-parametric models, which are mentioned in that same section, where you make or not assumptions about the data-generating process.
So, to conclude, I think that these terms are often used vaguely and sometimes interchangeably, so the confusion is normal.

It is purely terminological. A probabilistic model uses probabilities, but one usually does not know what the 'correct' probabilities are, or where they come from. This is where statistics comes into play:
You can estimate probabilities from (empirical) data[*]. For example, if you develop a probabilisitc parts-of-speech tagger, you need probabilities typically for the probability of a certain word to be of a particular class, and for transition probabilities, ie how likely is it for tag a to be followed by tag b rather than tag c. So you might devise an equation that states that the probability of a token being assigned a particular tag is the product of the probability of the tag given the word and the tag given the previous two tags.
But you don't know what these probabilities are, and you cannot derive them from any formula. Instead, you get these values by looking at your training data, ie you count how often each event occurs, and normalise it to be in the range $[0..1]$.
In practice therefore, probabilities and statistical likelihoods are pretty much identical; probabilities are the theoretical values used in your model, and the actual values are derived using statistics. To make clear in equations that they aren't strictly the same, probabilities are usually denoted by $p$, whereas estimates based on statistics are marked $\hat{p}$.
[*] Another way to get probabilities is to calculate them, but looking at large-scale open-ended problems this is not easily possible. That's why you take samples to estimate the values -- this is then called training data.

You can compute statistics from the data, such as the sample mean, and, although I am not a statistician, it doesn't sound very natural to me to say "statistical data", but it makes some sense to say "empirical data", although it sounds redundant, as data is usually empirical, in the sense that it's something that we collect/observe and it's not just some theoretical thing.

I would also remove the sentence "To a non-mathematician therefore probabilities and statistical likelihoods are pretty much identical". To me it doesn't make much sense to talk about "probabilistic likelihood" or "statistical likelihood". You define a probabilistic model, e.g. $p(y \mid x)$ or the likelihood, then you try to maximize it. So, you model your problem with probability theory, but then you estimate a statistical model, because the "model" is based on the data.

In any case, this is just one interpretation and, as you say, it's definitely not clear from the literature and books if there's any consensus on these definitions. Apart from these 2 things, I like your answer. I think it

@nbro Thanks for your comments, I have amended my answer.


text:
How do I represent sample efficiency of RL rewards in mathematical notation?
I define sample efficiency as the area under the curve/graph, where $x$-axis is the number of episodes while y-axis is the cumulative reward for that episode. I would like to formally define it with a mathematical function.
If the notation for cumulative reward for $x$th episode is:
$$R_x = \sum_{t=0}^{t=T} r_t,$$
where $r_t$ is the reward for timestep $t$ and $T$ is the max number if steps per episode.
So is the equation for area under the graph/curve the one below?
$$\text{Sample Efficiency} =\int_{a}^{b} R_x \ dx$$
I will be just using a Python library to get the area under the graph which uses Simpson's rule for integrating.

Episodes are discrete, there is no need for calculus. Your "sample efficiency" metric is:
$$\sum_{x=a}^b R_x$$
The quantity you are measuring per episode is the return (undiscounted). The sum of this over many episodes does not measure sample efficiency as the term is usually meant, although the sample efficiency of the algorithm you use should impact the numbers you see. Getting a high value of this metric, averaged over many training runs, implies two things:

The algorithm learns to exploit the environment quickly. This is related to sample efficiency.

The algorithm does not pay a high cost for exploring. This is not directly related to sample efficiency, and may in fact be in conflict with learning an environment quickly.

These are both desirable properties of a reinforcement learning algorithm. They often need to be considered in balance, this is the exploration versus exploitation dilemma in RL, which can be studied in a simplified form in mult-arm bandit problems. You may be able to take inspiration from how bandit algorithms are measured for other metrics related to efficient learning.
Your metric is most useful when considering learning agents run in a live environment, where costs of mistakes during learning are real.
If instead you are training an agent in a safe environment - e.g. in simulation - then you may not be interested in the undiscounted returns $R_x$ during training. Your goal may be to train the agent using the least CPU time, the least number of simulation runs etc. In which case, you care most about the mean return achievable by the trained algorithm after spending a certain amount of whatever resource you are managing. This is more closely related to the concept of sample efficiency, and to measure that you could plot the returns from separate test episodes at routine intervals, with exploration removed (e.g. if you were using DQN, then with $\epsilon = 0$

Thanks for this. I am using policy gradient algorithms like SAC and TD3 for continuous action space. Episode has NO terminal state so all episodes are of the same length. Which sample efficiency metric do you think I'd use? And yes, I am using a simulation

I would use a metric of minimising the resource spend that I am most concerned about, whilst reaching either acceptable, near optimal or optimal behaviour, averaged over enough runs that differences between approaches can be shown to be significant. So if you are truly interested only in number of simulated time steps required (a fairly pure measure of sample efficiency), then count the number of simulated time steps required to reach some close-to-optimal mean reward per time step.


text:
Is the formula $\frac {1}{s}\sum _{j=1}^{s}|d_{j}-y_{j}(t)|$ the correct form of 0-1 loss function, in the context of Perceptron?
Per page 7 of this MIT lecture notes, the original single-layer Perceptron uses 0-1 loss function.
Wikipedia uses
$${\displaystyle {\frac {1}{s}}\sum _{j=1}^{s}|d_{j}-y_{j}(t)|} \tag{1}$$
to denote the error.
Is the formula (1) the correct form of 0-1 loss function?

There is no loss function for this particular case since this algorithm iteratively updates each weight separately. The wiki says this formula is used to stop training if it is less than a certain threshold. Take a look at this and this answers for more details.

@ArayKarjauv Thank you. What does "this particular case" refer to? Both sources claim there is a loss function.

This (particular) iterative learning algorithm presented in the provided articles implies a non-differentiable loss function (usually sign) that does not quantify the predictions, but only says whether they were correct or not, so you cannot optimize it using gradient descent. Therefore, it is not a loss function in the usual sense. There is a loss function if your activation is differentiable. For instance, sigmoid. Then, the loss will be binary cross-entropy.

I've created a chat room about perceptrons. Feel free to join it: https://chat.stackexchange.com/rooms/126900/perceptron-learning-algorithm

@ArayKarjauv I don't think that a "loss function" necessarily needs to be differentiable, although this is probably just a matter of convention. Anyway, if you have an answer to this question, feel free to write it below. Comments are meant to be temporary and to provide additional info rather than full answers.


text:
Are there any algorithms (even backtracking variations) that solve the sudoku in a way more similar to this approach?
I looked a bit online for Sudoku solvers and it seems like all the answers I found involve a backtracking algorithm.
However, this is not how humans (at least not me) solve Sudoku. We don't place in the first empty square, the first digit that works and go on until we solve it or hit a dead end. Usually, we try to find an empty square (which can be anywhere on the board) where there is a unique solution and then we repeat this. We might have to do some backtracking-like approach if we are out of squares with unique solutions, but that is not the main part of our approach.
Are there any algorithms (even backtracking variations) that solve the sudoku in a way more similar to this approach?

Surely you can implement such algorithm, since you already know the details. Iterative steps:

Determine possible numbers in all empty squares
Find the square with the least number of possible numbers
Does this square have an unique solution? If yes, set it and GOTO 1
Else apply the backtracking logic and guess a number, GOTO 1

People who are good with sudokus know various advanced tricks, which I have seen on Youtube at Cracking The Cryptic channel. He has even tested a sudoku's difficulty on a specific solver site, in which you can choose that which advanced techniques you want it to apply. In my understanding the site's algorithm does not use any backtracking, and it might conclude that it cannot solve the problem with given techniques. Sadly I don't remember this website's name, or the video in which it was used.
Arguably this is more of a Computer Science answer than AI, but then again for example chess engines can be approached from either direction.
Edit: I found the video and thus the solver by  Andrew Stuart! It has 39 distinct, human-like algorithms and describes how each of them work.


text:
How does NEAT find the most successful generation without gradients?
I'm new to NEAT, so, please, don't be too harsh. How does NEAT find the most successful generation without gradient descent or gradients?

NEAT is a genetic algorithm (GA). A genetic algorithm maintains a population of individuals (or chromosomes) and evolves it using operations like the crossover or the mutation, so that the fittest individuals keep living and most other individuals die. The nature of the individuals depends on the problem. For example, in the case of NEAT, the individuals are neural networks. However, these individuals need first to be encoded into a (compressed) reprentation (for example, a vector) that allows the operations like mutation to be efficiently applied: this representation is often called the genotype (or chromosome).
How do you decide which individuals are the fittest? A function called the fitness function needs first to be defined. The fitness function measures the fitness (or quality) of the individuals (or solutions). In the case of neural networks, a fitness function could, for example, be the accuracy of the neural networks on a validation dataset.
Why don't GAs need gradients? The fitness (or quality) of the solutions is given by the fitness function in the case of GAs, so gradients are not strictly needed, even though they can also be used.
NEAT is a little bit more complex (and it is described in detail in the paper that introduced it Evolving Neural Networks through Augmenting Topologies), but this is the basic idea behind all genetic algorithms (including NEAT).


text:
Why is an average of all returns used to update the value in the first-visit MC control?
In Sutton & Barto's Reinforcement Learning: An Introduction,  in page 83 (101 of the pdf), there is a description of first-visit MC control. In the phase where they update $Q(s, a)$, they do an average of all the returns $G$ for that state-action pair.
Why don't they just update the value with a weight for the value from previous episodes $\alpha$ and a weight $1- \alpha$ for the new episode return as it is done in TD-Learning?
I have also seen other books (for example, Algorithms for RL (page 22) where they update it using $\alpha$. What is the difference?

there's no difference it's the same thing. Incremental update is more appropriate because you don't have to save returns in the memory .

@Brale_ Thanks for your comment. Can you mathematically show why it is the same in an answer?

Why don't they just update the value with a weight for the value from previous episodes $\alpha$ and a weight $1- \alpha$ for the new episode return as it is done in TD-Learning?

In my opinion, this is a mistake in the book. I went back and checked that this is still the same in the finished second edition, and it is still there.
Keeping all returns and taking averages works fine in a prediction scenario with a fixed policy, and it is somewhat simpler and more intuitive to explain as "this is the mean value" (efficiency can come later, after comprehension). However, the pseudo-code is incorrect for a control scenario where older returns (that you still refer in the list) will not reflect the current policy, so will be biased.
In practice, no-one really uses the MC Control algorithms as written. Nearly always a learning rate parameter, $\alpha$ is used to update estimates.

What is the difference?

In a prediction scenario, where you want to evaluate a fixed policy, it would be slightly more efficient to use a count of samples for each $s,a$ pair and variable $\alpha = \frac{1}{N(s,a)}$ which is mathematically identical to keeping a list and taking the average as needed.
In a control scenario using a list of old return values is not only memory inefficient, it is also sample inefficient as you would need samples from each improved policy to outnumber the older samples in order to remove sampling bias due to using returns from initial worse policies. A fixed, or slowly decaying $\alpha$ is a simple and efficient way of "forgetting" the old return values as they become less relevant to the task.
Another way to achieve similar forgetting may be to have a maximum size for each $Returns(s,a)$ list. However, that is not mentioned in the MC Control pseudocode.
Perhaps I am missing something, as the book has been through significant review process. However, it may be that this detail is overlooked because the basic MC Control scenarios are not as interesting as all the extensions and combinations with TD, where you will find the book does use a learning rate $\alpha$ - including when making comparison charts of MC vs TD approaches etc. The explicit list of returns and averaging over them for control only occurs in a couple of places in the text in this pseudocode, and is not mentioned again.


text:
Does AlphaZero use Q-Learning?
I was reading the AlphaZero paper Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm, and it seems they don't mention Q-Learning anywhere.
So does AZ use Q-Learning on the results of self-play or just a Supervised Learning?
If it's a Supervised Learning, then why is it said that AZ uses Reinforcement Learning? Is "reinforcement" part primarily a result of using Monte-Carlo Tree Search?

Note: you mentioned in the comments that you are reading the old, pre-print version of the paper describing AlphaZero on arXiv. My answer will be for the "official", peer-reviewed, more recent publication in Science (which nbro linked to in his comment). I'm not only focusing on the official version of the paper just because it is official, but also because I found it to be much better / more complete, and I would recommend reading it instead of the preprint if you are able to (I understand it's behind a paywall so it may be difficult for some to get access). The answer to this specific question would probably be identical for the arXiv version anyway.

No, AlphaZero does not use $Q$-learning.
The neural network in AlphaZero is trained to minimise the following loss function:
$$(z - \nu)^2 - \pi^{\top} \log \mathbf{p} + c \| \theta \|^2,$$
where:

$z \in \{-1, 0, +1\}$ is the real outcome observed in a game of self-play.
$\nu$ is a predicted outcome / value.
$\pi$ is a distribution over actions derived from the visit counts of MCTS.
$\mathbf{p}$ is the distribution over actions output by the network / the policy.
$c \| \theta \|^2$ is a regularisation term, not really interesting for this question/answer.

In this loss function, the term $(z - \nu)^2$ is exactly what we would have if we were performing plain Monte-Carlo updates, based on Monte-Carlo returns, in a traditional Reinforcemet Learning setting (with function approximation). Note that there is no "bootstrapping", no combination of a single-step observed reward plus predicted future rewards, as we would have in $Q$-learning. We play out all the way until the end of a game (an "episode"), and use the final outcome $z$ for our updates to our value function. That's what makes this Monte-Carlo learning, rather than $Q$-learning.
As for the $- \pi^{\top} \log \mathbf{p}$ term, this is definitely not $Q$-learning (we're directly learning a policy in this part, not a value function).

If it's a Supervised Learning, then why is it said that AZ uses Reinforcement Learning? Is "reinforcement" part primarily a result of using Monte-Carlo Tree Search?

The policy learning looks very similar to Supervised Learning; indeed it's the cross-entropy loss which is frequently used in Supervised Learning (classification) settings. I'd still argue it is Reinforcement Learning, because the update targets are completely determined by self-play, by the agent's own experience. There are no training targets / labels that are provided externally (i.e. no learning from a database of human expert games, as was done in 2016 in AlphaGo).

Dennis, can I ask about the convention of using || around the theta?

@DukeZhou Sure. The two bars on each side of the vector basically denotes that we take the $\ell_2$-norm, or Euclidean norm, of the vector: $\sqrt{\theta_0^2 + \theta_1^2 + \dots + \theta_n^2}$. This could've been made a bit more clear with an additional subscript $2$, but I just followed the notation from the paper :) Afterwards the superscript $2$ just means that we square it again, which cancels out the square root in the Euclidean norm, meaning we just end up with the sum of the squared elements of the vector.


text:
Examples of time-varying graph-structured data in real world
I'm looking for examples of time-varying graph-structured data for time-varying graph CNNs. First, I came up with the idea of infection network. Is there anything more? If possible, I want data that can be easily obtained online.

So, you're looking for applications and related datasets?

@nbro yes, do  you have any recommendations?

You can take a look at traffic data for example if you follow
link1, link2 you can find 3 publicly available traffic datasets which are already preprocessed. You cold also look at air quality datasets offered by the government link3


text:
Can neuroevolution be combined with gradient descent?
Is there any precedent for using a neuroevolution algorithm, like NEAT, as a way of getting to an initialization of weights for a network that can then be fine-tuned with gradient descent and back-propagation?
I wonder if this may be a faster way of getting to a global minimum before starting a decent to a local using backpropagation with a large set of input parameters.

The paper The Comparison and Combination of Genetic and Gradient Descent Learning in Recurrent Neural Networks: An Application to Speech Phoneme Classification (2007), by Rohitash Chandra and Christian W. Omlin, uses genetic algorithms to train a recurrent neural network and then uses gradient descent to fine tune the trained model.
The paper Evolutionary Stochastic Gradient Descent for Optimization of Deep Neural Networks (2018), by Xiaodong Cui, Wei Zhang, Zoltán Tüske and Michael Picheny, also combines evolutionary algorithms and gradient descent, but, in this case, they alternate between a gradient descent step and an evolution step. This is an example of a evolutionary stochastic gradient descent (ESGD) method, as opposed to a population-based training (PBT) method, which uses only evolutionary algorithms to train neural networks.

Yes it can be in addition to the papers that nbro linked to above uber's ai research team has a very interesting combination of sgd and neuroevolution which they have dubbed "safe mutations". In the algorithm each genome undergoes a bit of sgd to improve its fitness before the speciation, elitism, and reproduction processes. I imagine this has an effect of searching for genomes which are well suited for sgd optimization, and in my opinion does really provide the best of both a worlds. Here is the link to the paper https://arxiv.org/abs/1712.06563 . What I think would be a cool for this combination of the two would be its use in conjunction with the es-hyperneat/hyperneat neuroevolution algorithms in which a small genome cppn encodes large phenotype rnns using the rnns substrate (its structure represented with cartesian coordinates) as the cppns input. If a small amount sgd is used on the rnn's to improve fitness then what you end up with is a cppn is being evolved to encode very general rnn networks that can then be optimized to specific domains via sgd. I like this because then your neuroevolution doesnt occur on a massive rnn and you can create cppns that recognize the general problem you wish to solve if your clever with your fitness evaluation.


text:
Which loss function should I use for binary classification?
I plan to create a neural network using Python, Keras, and TensorFlow. All the tutorials I have seen so far are concerned with image recognition. However, the goal of my program would be to take in 10+ inputs and calculate a binary output (true/false) instead.
Which loss function should I use for my task?

There are several loss functions that you can use for binary classification. For example, you could use the binary cross-entropy or the hinge loss functions.
See, for example, the tutorials Binary Classification Tutorial with the Keras Deep Learning Library (2016) and How to Choose Loss Functions When Training Deep Learning Neural Networks (2019) by Jason Brownlee. Have also a look at Keras documentation of its available loss functions.


text:
Why do we need common sense in AI?
Let's consider this example:

It's John's birthday, let's buy him a kite.

We humans most likely would say the kite is a birthday gift, if asked why it's being bought; and we refer to this reasoning as common sense.
Why do we need this in artificially intelligent agents? I think it could cause a plethora of problems, since a lot of our human errors are caused by these vague assumptions.
Imagine an AI ignoring doing certain things because it assumes it has already been done by someone else (or another AI), using its common sense.
Wouldn't that bring human errors into AI systems?

Comments are not for extended discussion; this conversation has been moved to chat.

Why do human beings need common sense?

Commonsense knowledge is the collection of premises that everyone, in a certain context (hence common sense knowledge might be a function of the context), takes for granted. There would exist a lot of miscommunication between a human and an AI if the AI did not possess common sense knowledge. Therefore, commonsense knowledge is fundamental to human-AI interaction.
There are also premises that every human takes for granted independently of the country, culture, or, in general, context. For example, every human (almost since its birth) has a mechanism for reasoning about naive physics, such as space, time, and physical interactions. If an AI does not possess this knowledge, then it cannot perform the tasks that require this knowledge.
Any task that requires a machine to have common sense knowledge (of an average human) is believed to be AI-complete, that is, it requires human-level (or general) intelligence. See section D of AI-Complete, AI-Hard, or AI-Easy – Classification of Problems in AI (2012) by Roman V. Yampolskiy.
Of course, the problems that arise while humans communicate because of different assumptions or premises might also arise between humans and AIs (that possess commonsense knowledge).

Comments are not for extended discussion; this conversation has been moved to chat.

We need this kind of common sense knowledge if we want to get computers to understand human language. It's easy for a computer program to analyse the grammatical structure of the example you give, but in order to understand its meaning we need to know the possible contexts, which is what you refer to as "common sense" here.
This was emphasised a lot in Roger Schank et al.'s work on computer understanding of stories, and lead to a lot of research into knowledge representation, scripts, plans, goals. One example from Schank's work is Mary was hungry. She picked up a Michelin Guide. -- this seems like a non-sequitur: if you are hungry, why pick up a book? Until you realise that it is a restaurant guide, and that Mary is presumably planning to go to a restaurant to eat. If you know that going to a restaurant is a potential solution to the problem of being hungry, then you have no problem understanding this story fragment.
Any story needs common sense to be understood, because no story is completely explicit. Common things are "understood" and aren't explicitly mentioned. Stories relate to human experience, and a story that would make everything explicit would probably read like a computer program. You also need common sense to understand how characters in a story behave, and how they are affected by what is happening. Again, this is very subjective, but it is necessary. Some common sense might be generally applicable, other aspects of it won't be. It's a complex issue, which is why researchers have struggled with it for at least half a century of AI research.
Of course this would introduce "human errors" into an AI system. All this is very subjective and culture-specific. Going to a restaurant in the USA is different from going to one in France -- this is why going abroad can be a challenge. And my reading of a story will probably be different from yours. But if you want to simulate human intelligence, you cannot do that without potential human "errors".

Comments are not for extended discussion; this conversation has been moved to chat.

I'll answer this question in several parts:

Why do AGI systems need to have common sense?

Humans in the wild reason and communicate using common sense more than they do with strict logic, you can see this by noting that it is easier to appeal to someone's emotion than logic. So any system that seeks to replicate human cognition (as in AGI) should also replicate this tendency to use common sense.
More simply put, we'd wish that our AGI system can speak to us in common sense language simply because that is what we understand best (otherwise we wouldn't understand our friendly AGI would we?). Obtuse theory and strict logic might technically be correct, but don't appeal to our understanding.

Isn't the goal of AGI the create the most cognitively advance system? Why should the "most perfect" AGI system need to deal with such imperfections and impreciseness present in common sense?

First, it might only appear to be the case that common sense logic is "irrational". Perhaps there is a consistent mathematical way to model common sense such that all the subtleties of common sense are represented in a rigour fashion.
Second, the early study of Artificial Intelligence started in the study of cognitive science, where researchers tried to replicate "algorithms of the mind", or more precisely: decidable procedures which replicated human thought. To that extent then, the study of AI isn't to create the "most supreme cognitive agent" but to merely replicate human thought/behavior. Once we can replicate human behavior we can perhaps try to create something super-human by giving it more computational power, but that is not guaranteed.

I still don't see why common sense is needed in AGI systems. Isn't AGI about being the most intelligent and powerful computational system? Why should it care or conform towards the limits of human understanding, which requires common sense?

Perhaps then you have a bit of a misaligned understanding of what AGI entails. AGI doesn't mean unbounded computational power (physically impossible due to physical constraints on computation such as Bremermann's limit) or unbounded intelligence (perhaps physically impossible due to the prior constraint). It usually just means artificial "general intelligence", general meaning broad and common.
Considerations about unbounded agents are studied in more detail in fields such as theoretical computer science (type theory I believe), decision theory, and perhaps even set theory, where we are able to pose questions about agents with unbounded computational power. We might say that there are questions even an AGI system with unbounded power can't answer due to the Halting Problem, but only if the assumptions on those fields map onto the structure of the given AGI, which might not be true.
For a better understanding of what AGI might entail and its goals, I might recommend two books: Artificial Intelligence: The Very Idea by John Haugeland for a more pragmatic approach (as pragmatic as AI-philosophy can be, and On the Origin of Objects by Brian Cantwell Smith for a more philosophically inclined approach.
As a fun aside, the collection of Zen koan's: The Gateless Gate, includes the following passage: (quoted and edited from wikipedia)

A monk asked Zhaozhou, a Chinese Zen master, "Has a dog Buddha-nature or not?" Zhaozhou answered, "Wú"

Wú (無) translates to "none", "nonesuch", or "nothing", which can be interpreted as to avoid answering either yes or no. This enlightened individual doesn't seek to strictly answer every question, but just to respond in a way that makes sense. It doesn't really matter as to wether the dog has Buddha-nature or not (whatever Buddha-nature means), so the master defaults to absolve the question rather than resolving it.

It would have been much funnier if the master had answered "wúf wúf!"

Perhaps it would help to give an example of what can go wrong without common sense: At the start of the novel "The Two Faces of Tomorrow" by James Hogan, a construction supervisor on the Moon files a request with an automated system, asking that a particular large piece of construction equipment be delivered to his site as soon as possible.  The system replies that it will arrive in twenty minutes.  Twenty minutes later, the supervisor is killed as the equipment crashes into his construction site.  The system had determined that the fastest way to deliver the equipment to that site was to mount it on a mass-driver and launch it at the site.  Had the system in question been given common sense, it would have inferred additional unstated constraints on the query, such as 'the equipment should arrive intact', 'the arrival of the equipment should not cause damage or loss of life', and so on.  (the rest of the novel describes an experiment designed to produce a new system with common sense)

Quite interesting example. Though, maybe it could go the other way around as well. Imagine an AI checking in on a patient, and by seeing the patient's overall normal looks, conclude that the patient might/should be fine (based on it's common sense that if you look fine then probably you are); however, the patient is in need of serious help. However, I think it's clear by now that common sense is not the problem, it's faulty common sense/knowledge that might turn out to be dangerous in critical situations. So I guess we should control and make sure that the AI has a flawless common sense.

Is this common sense, or is this natural language understanding?
It's been said that natural language understanding is one of the hardest AI tasks. This is one of the examples showing why. The first part of the sentence is related to the second part, that how sentences work.
Now the relevant question is  how the two parts are related. There are a few standard relations that we encounter, for instance a temporal order. In this specific example, the nature of the relation is closer to a cause-and-effect.
You see this effect when we insert a word to make this relation explicit:

It's John's birthday, so let's buy him a kite.
  or
  Let's buy John a kite, because it's his birthday.

This is a technique for humans to make these implicit relations explicit.
Now, as curiousdannii notes, you also need the cultural knowledge to understand how a birthdays can be a cause for a present. No amount of common sense helps with that.

We use the "common sense" we have to understand a sentence like that. NLP is really hard, I agree, and that's because so far AI hasn't possessed this comprehensive knowledge and model of the world that we humans have; hence it lacks in connecting the dots and understanding those implicit relations. That "cultural knowledge" you mentioned is basically considered our common sense.


text:
Can a vanilla neural network theoretically achieve the same performance as CNN?
I perfectly understand that CNN takes into account the local dependency of each pixel to the nearby pixels. In addition, CNNs are spatially invariant which means that they are able to detect the same feature anywhere in the image. These qualities are useful in image classification problems given the nature of the problem.
How does a vanilla neural net exactly falls short on these properties? Am I right in claiming that a vanilla neural net has to learn a given feature in every part of the image? This is different than how a CNN does it, which learns the feature once and then detects it anywhere in the image.
How about local pixel dependancy? Why can't a vanilla neural network learn the local dependency by relating one pixel to its neighbors in the 1D input?
In other words, is there more information present while training a CNN that are simply absent when training a normal NN? Or is a CNN just better at optimizing in the space of image classification problems?

All CNNs can be represented as vanilla networks on the flattened image data. Just to do so, you would need A LOT of parameters (most of which would be 0) for what CNNs do freely. You can think of a CNN as reusing a filter on a masked input (whichever receptive field it's looking at whatever point during the convolution) repetitively.
In other words, fully connected layers use all the information, so it can still learn spatial dependence as a CNN does, while CNNs for each neuron only look at a specific receptive field and will reuse that filter for all neurons in that channel. This constraint saves computation and allows wider and deeper models under some budget.
This is nice because the hypothesis of why CNN's work are, is that at each point in the network we care about looking at localized features rather than global ones and that creating a composition of these makes it so even if each neuron only relates to a handful of neurons in the previous layer, the receptive field from the initial image can still be quite large if not the whole thing.
Take away: CNNs are an efficient implementation of a vanilla NN, given the locality constraint that each neuron only looks at a small localized subset of neurons from the previous layer.

Comments are not for extended discussion; this conversation has been moved to chat.


text:
What is "dense" in DensePose?
I've recently come across an amazing work for human pose estimation: DensePose: Dense Human Pose Estimation In The Wild by Facebook.
In this work, they have tackled the task of dense human pose estimation using discriminative trained models.
I do understand that "correspondence" means how well pixels in one image correspond to pixels in the second image (specifically, here - 2D to 3D).
But what does "dense" means in this case?

In computer vision, the adjectives dense and sparse are used in a variety of tasks (e.g. optimal flow), but they are commonly used in the context of the correspondence problem, which is the problem of finding a map (or correspondence) between pixels of two images (e.g. two successive frames of a video). In this context, these adjectives thus refer to the number of pixels of the image that are used to solve this specific task. A dense correspondence is thus a correspondence between two images using all (or, at least, many) pixels. In other words, a dense correspondence attempts to map all (or many) pixels of an image to all (or many) pixels of another image.
In the case of DensePose, the correspondences are between RGB images and surface-based representation of the human body (the figures of the paper illustrates this).


text:
How should I detect an object in a camera image?
I would like to create a model, that will tell me if one type of object is in an image or not.
So, for example, I have a camera and I would like to see when one object gets into the shot.

Object detection: This could be an overkill, because I don't need to know the bounding box around. Also, this means that I would need to label a lot of images, and draw the bounding box to have train data (a lot of time)
Image classification: This doesn't solve the problem, because I don't know what else could not be an object. It would be impossible to train for 2 classes: object / not object.

My idea is to have Autoencoder. Train it only on data with the object. Then, if Autoencoder produces a result with a high difference with the original, I detect it as an anomaly - no object.
Is this a good approach? Will I have a lot of trouble with different backgrounds?

Is this a good approach? Will I have a lot of trouble with different backgrounds?

A lot will depend on the nature of the backgrounds you have, and how well they encode/decode by themselves without the object in frame. My gut feeling is that your system will have poor performance compared to a properly trained classifier, as the autoencoder will naturally have to get good at constructing background elements in order to score well, so unless your object is very consistently always in a similar place with radically different appearance to the background then the autoencoder will get good reconstructions of background-only frames, and your anomaly detection would need to be set too sensitive. That would cause the detector to fail to spot the object when in frame.
There is a catch-all answer to "how well will my idea work" with ML projects. You should try it and see. Data science is essentially an empirical approach, and building practical models is an engineering discipline where testing is a core part of the process.
In order to test your model, you are going to need a lot of images of just background, including all the kinds of background that you expect the system to be used. Which begs the question, why not collect a range of suitable images without your target object, and use them as the second class?

This doesn't solve the problem, because I don't know what else could not be an object. It would be impossible to train for 2 classes: object / not object.

Actually, it is easy. Just collect suitable images from locations where you expect your system to be used, without the object in frame. These are your "Not Object" class. A "Not Object" does not have to include some substitute foreground object. Although I recommend that you do have some images like this to prevent accidentally creating an "object is in the foreground" detector*. The primary goal should be to be collect data that matches how the model will be used once deployed. That will depend a lot on how much control and consistency you get over the production cameras where the trained detector will be put to use.
I would do this, then train a standard binary classifier.
If you are still interested in how well your auto-encoder idea could work, you then have plenty of test data to evaluate it.

*  This is one area where your auto-encoder idea might do better than a classifier - reconstructing unfamiliar foreground objects should be hard for it leading to high error.
It is too difficult to tell in advance whether this effect is strong enough to make your auto-encoder approach better than a classifier.

thank you. Yes I will test it out, but before I start collecting data, I would like to bounce my ideas with someone :D After your post, it get me thinking regarding the background. My object would naturally occupy most of the image (60% or more). I could have train data with white background. In this case only object would be reconstructed good, and the background not. Then I can distinguish, if outoencoder reconstruct half of he image or completely fail (only background).

@MarkoZadravec: With the object takingu p such a large part of the image, your autoencoder idea seems more possible. I would not train with white background though. You need to train with real data. The more your training data and production data are different, the more problems you will have with accuracy when deploying your model


text:
Is explainable AI more feasible through symbolic AI or soft computing?
Is explainable AI more feasible through symbolic AI or soft computing?
How much each paradigm, symbolic AI and soft computing (or hybrid approaches), addresses explanation and argumentation, where symbolic AI refers e.g. to GOFAI or expert systems, and soft computing refers to machine learning or probabilistic methods.

XAI is relevant to "black box" AI (machine learning methods where the decision making rationale is not apparent, only the structure of the system that led to that decision.)
Symbolic AI, GOFAI, and Expert Systems are both explainable and understood, in that the the decision-making process is designed by humans.  (Symbolic AI involves human-readable representations of problems.)
To directly answer, XAI is not only feasible in the latter cases, it is a prerequisite. The difficulty is in making black box decision-making explainable.


text:
Is there any difference between a control and an action in reinforcement learning?
There are reinforcement learning papers (e.g. Metacontrol for Adaptive Imagination-Based Optimization) that use (apparently, interchangeably) the term control or action to refer to the effect of the agent on the environment at each time step.
Is there any difference between the terms control or action or are they (always) used interchangeably? If there is a difference, when is one term used as opposed to the other?
The term control likely comes from the field of optimal control theory, which is related to reinforcement learning.

There's no difference. As they too often do, ML researchers take concepts from other disciplines, conveniently forget to cite sources and change the terminology, leading to much confusion. RL is a textbook example (pun intended). Optimal control researchers have been studying very similar problems long before RL ones, and used standard symbols and terms ($x$ for states, $u$ for controls). Then RL researchers came and changed just about everything.
See the paper A Tour of Reinforcement Learning: The View from Continuous Control (2018), by Benjamin Recht, which discusses reinforcement learning from a control and optimization perspective.
See also this tweet https://twitter.com/beenwrekt/status/1134536093980864514?s=21 (by Benjamin Recht) regarding the presentation of Sham Kakade.


text:
How to stop evaluation phase in reinforcement learning with epsilon-greedy Monte Carlo agent?
I have implemented an epsilon-greedy Monte Carlo reinforcement learning agent like suggested in Sutton and Barto's RL book (page 101). As far as I understood epsilon-greedy agents so far, the evaluation has to stop at some point to exploit the gained knowledge.
I do not understand, how to stop the evaluation here, because the policy update is linked to epsilon. So just setting epsilon equal to zero at some point does not seem to make sense to me.

I do not understand, how to stop the evaluation here, because the policy update is linked to epsilon. So just setting epsilon equal to zero at some point does not seem to make sense to me.

If by evaluation you mean the act of exploring new paths, it does not need to stop by changing epsilon to 0 instantly. Instead, in order to facilitate the convergence of the algorithm, the epsilon can be progressively decreased until it reaches 0.
I do not think your question is meant to be related with monte carlo specifically, but if this was not what you wanted to know, please comment.

But would not a epsilon value of 0 lead to an unintended policy update?

No, a value of epsilon equal to 0 will make you always choose your action according to the policy. I think what is confusing is that the "update" they make to the policy on the last for, is not an update. It is a statement saying the probability of taking such action. What it means is the following:
For action $a$, the probability of taking $a$ in state $S_t$, when $\epsilon$ is 0 is:

1 if action $a$ is the action with the best value
0 if action  $a$ is not the action with the best value

What this means is that when epsilon is 0, the action taken will always be the greedy action.

But would not a epsilon value of 0 lead to an unintended policy update?

@Jan I will update my answer give me 5min

Before answering how to stop the evaluation phase and begin exploitation of those results, one must first answer when to stop it whereby the balance the project stakeholder wants between quality and cost is found. You won't always find that in books discussing pure research, so your question is an excellent one.
The algorithm the authors are discussing on that page (101) is based on the policy improvement theorem on page 78, and the appearance of the endless loop in the algorithm in the pseudo-code line "Repeat forever (for each episode)" is obviously worse than useless in a data center if the loop is not terminated, unless it is multi-agent, exploiting multiple threads, processes, virtual hosts, hardware accelerators, cores, or hosts, and the improvements are accessed for exploitation independently or symbiotically using some scheme.
In a deployed robot, an endless loop often has a legitimate a use case. "Repeat until shutdown," might be appropriate in a production algorithm or hardware embodiment if the robot's goal is, "Keep the living room clean." One must always try to place this theory in context when taking pure research and considering the applied research that may stem from it.
In real product and service development environments, how the balance is struck between quality of action and cost of determining it depends upon the problem size, expectations of the user or business, and the architecture of the computational resources you have. Consider some of these factors in more detail.

Maximum number of rounds of evaluation-exploitation cycles
Requirements for precision in terms of optimality
Requirements for reliability in terms of completion
Distribution of the number branches from nodes
Distribution of lengths of possible action traversal sequences to the goal
Average cost (in time and energy) of each evaluation
Average cost (in time and energy) of each exploitation

In a single thread, single core, von Neumann architecture, as is sometimes the case in an embedded environment, evaluation and exploitation are time sliced. In such a case, evaluation should stop and exploitation should begin when the probability that further evaluation will produce an improved result drops below the cost of further evaluation, based on some estimation of return and cost. This is a function of the above factors, although not a linear one.
We have considered training an LSTM network to determine the function in the epoch domain (roughly related to the time domain), although it is low on our priority list.
In an embedded process, a function that approximates return on further evaluation cost can be constructed, based on statistics gathered up to that point in current learning or over a longer period of operations. The function should be fast and inexpensive. In each cycle within the evaluation phase, the function can be evaluated and compared against a configurable probability threshold. Its configuration value can be an educated guess based on the perception of the value of further path exploration.
In a simulation environment, when more computing resources for parallel processes, exploiting OS or hardware facilities for that, the time slicing is either opaque or nonexistent respectively. In those cases, continuous improvement may be unbounded because the state-action graph is not finite.


text:
Why does the DQN not converge when the start or goal states can change dynamically?
I'm trying to apply a DQN to a stochastic environment, but I'm having trouble getting it to converge.
I found some similar questions asked here, but no solutions yet.
I can easily get the DQN to converge on a static environment, but I am having trouble with a dynamic environment where the end is not given.
Example: I have made a really simple model of the Frozen Lake (without any holes) - simply navigation from A to B. This navigation works fine when A and B are always the same, but when I shuffle the position of A or B for each session, the DQN cannot converge properly.
I am using the grid (3x3, 4x4 sizes) as input neurons. Each with "0" value. I assign the current position "0.5" and the end position "1". 4x4 grid gives us 16 input neurons. Example of 3x3 grid:
 0.5  0  0
  0   0  0
  0   0  1

I have a few questions in this regard:

When training the DQN, how do I apply Q-values? (Or do I really need to? I'm not sure how to correctly "reward" the network. I'm not using any adversarial network or target network at this point.)

I train the network using only a short replay memory of the last move, or the last N moves that led to success. Is this the right way to approach this?

I use Keras, and am simply training the network every time it does something right - and ignoring failed attempts. - But is this anywhere near the right approach?

Am I missing something else?

Perhaps I should note that my math skills are not that strong, but I try my best.
Any input is appreciated.

Please clarify what your state representation is in the modified environment. I think this will be critical to explanations of why it doesn't work. I think you are still using the basic grid position as state?

Also please clarify your first question. What do you mean by "apply Q-values" - what process or calculation are you wondering about?

Thanks, the edit is really useful, and I was wrong in my assumption about the state. I think your state representation is workable (although maybe not the fastest, it should work)

Thanks, i have tried to clarify it above. Yes, i am using the grid as state. - By Q-value i mean, i'm a bit unsure of how to correctly use reward policies in the DQN. At present, i do not use any Q-values at all, but only train the network when it does something successful. (Finds the route) - But is this a good way to approach this, or should i use more nuances somehow? (I know it's kind of simple, but it works for grid where the goal-position is static)

Your problem is not that the environment is stochastic or dynamic. In fact you are using the terms slightly incorrectly. These terms do not usually refer to the fact that starting state can differ or goal locations can move episode-by-episode. They typically refer to behaviour of state transitions.
Although in your case you could view the initial state as stochastic, this is not a big deal, and not likely to be the cause of your problems.
From your questions, it seems to me that you are not really running a DQN algorithm yet. It is not 100% clear what your neural network is predicting, but my best guess is that you have 4 outputs to select "best" action and are treating the neural network as a classifier. This training approach seems closest to Cross Entropy Method (CEM) due to how you are selecting "successful" navigation only.

When training the DQN, how do i apply Q-values?

This question is the most revealing that you are not using DQN. This is too complex to describe in full in an answer, but the basics are:

Your neural network (NN) should be estimating Q values. Typically in DQN, you input the state and the NN outputs an array of estimates for Q of each action (although other architectures are possible). This should be a regression problem, so last layer of network needs to be linear.
Current best guess of optimal policy is to run the NN forward and find the maximising action.
In DQN you also have a "behaviour policy" - a simple and popular choice is to use $\epsilon$-greedy action selection, which just means to take the maximising action (as calculated above), except with probability $\epsilon$ (some small value, e.g. 0.1) to take a random action.
To figure out your training data to improve the NN, you need Q values to calculate a TD Target. In single-step Q learning that would be $r + \gamma Q(s',a*)$ where $r$ is the immediate reward $s'$ is the next state seen, and $a*$ is the maximising action in that state. You should force $Q(s', a*) = 0$ (i.e. not use the NN) if $s'$ is a terminal state.

This means you typically need to work with Q values in 2 or 3 places in your inner loop. Your inner loop should look something like this per time step, given a current state current_state:
# Figure out how to act
current_q_values = NN_predict(current_state)
current_action = argmax(current_q_values)
if random() < epsilon:
  current_action = random_action()

# Take an action
reward, next_state, done = call_environment(current_state, current_action)

# Remember what happened
store_in_replay_memory(current_state, current_action, reward, next_state, done)

# Train the NN from memory
repeat N times: # This can be vectorised for efficiency
  mem_state, mem_action, mem_reward, mem_next_state, mem_done = sample_replay_memory()
  mem_q_values = NN_predict(mem_next_state)
  mem_max_action = argmax(mem_q_values)
  if done:
    td_target = mem_reward
  else
    td_target = mem_reward + gamma * mem_q_values[mem_max_action]
  target_q_values = NN_predict(mem_state)
  target_q_values[mem_action] = td_target
  NN_train(mem_state, target_q_values)

# Maybe end an episode (this can include generating new map)
if done:
  current_state = reset_environment()
else:
  current_state = next_state

You can see above, NN_predict is called three different times to get Q values in slightly different contexts. I have ignored extras such as using a separate target network.

I train the network using only a short replay memory of the last move, or the last N moves that led to success. Is this the right way to approach this?

It is important to include moves that lead to failure so that the NN learns the difference. Typically you will need a replay memory with from a few hundred to a few hundred thousand entries. You would get away with a few hundred perhaps for your simple problem. The idea is to use this training data a bit like a dataset from supervised learning.

I use Keras, and am simply training the network every time it does something right - and ignoring failed attempts. - But is this anywhere near the right approach?

This is not the right approach for DQN, although perhaps could be considered a crude version of CEM.

Thanks a bunch for the greatly detailed answer. It’s highly appreciated. I will go over every one of the details you describe in your post, as i’ve had a really hard time understanding these networks properly. I get the normal NNs and the normal Q-learning, but not the DQNs, so admittedly i am fumbling my way through the jungle herr. - I hope that going meticulously through the details in your answer, will help me on this path. Thanks again.


text:
What sort of mathematical problems are there in AI that people are working on?
I recently got a 18-month postdoc position in a math department. It's a position with relative light teaching duty and a lot of freedom about what type of research that I want to do.
Previously I was mostly doing some research in probability and combinatorics. But I am thinking of doing a bit more application oriented work, e.g., AI. (There is also the consideration that there is good chance that I will not get a tenure-track position at the end my current position. Learn a bit of AI might be helpful for other career possibilities.)
What sort of mathematical problems are there in AI that people are working on? From what I heard of, there are people studying

Deterministic Finite Automaton
Multi-armed bandit problems
Monte Carlo tree search
Community detection

Any other examples?

Optimization. Probably is the most impactful field to AI ML.  Proof of convergence, like in reinforcement learning, is lacking.

In artificial intelligence (sometimes called machine intelligence or computational intelligence), there are several problems that are based on mathematical topics, especially optimization, statistics, probability theory, calculus and linear algebra.
Marcus Hutter has worked on a mathematical theory for artificial general intelligence, called AIXI, which is based on several mathematical and computation science concepts, such as reinforcement learning, probability theory (e.g. Bayes theorem and related topics) measure theory, algorithmic information theory (e.g. Kolmogorov complexity), optimisation, Solomonoff induction, universal Levin search and theory of compution (e.g. universal Turing machines). His book Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability, which is a highly technical and mathematical book, describes his theory of optimal Bayesian non-Markov reinforcement learning agents. Here I list other similar works.
There is also the research field called computational learning theory, which is devoted to studying the design and analysis of machine learning algorithms (from a statistical perspective, known as statistical learning theory, or algorithmic perspective, algorithmic learning theory). More precisely, the field focuses on the rigorous study and mathematical analysis of machine learning algorithms using techniques from fields such as probability theory, statistics, optimization, information theory and geometry. Several people have worked on the computational learning theory, including Michael Kearns and Vladimir Vapnik.
There is also a lot of research effort dedicated to approximations (heuristics) of combinatorial optimization and NP-complete problems, such as ant colony optimization.
There is also some work on AI-completeness, but this has not received much attention (compared to the other research areas mentioned above).

Most of the math work being done in AI that I'm familiar with is already covered in nbro's answer. One thing that I do not believe is covered yet in that answer is proving algorithmic equivalence and/or deriving equivalent algorithms. One of my favourite papers on this is Learning to Predict Independent of Span by Hado van Hasselt and Richard Sutton.
The basic idea is that we may first formulate an algorithm (in math form, for instance some update rules/equations for parameters that we're training) in one way, and then find different update rules/equations (i.e. a different algorithm) for which we can prove that it is equivalent to the first one (i.e. always results in the same output).
A typical case where this is useful is if the first algorithm is easy to understand / appeals to our intuition / is more convenient for convergence proofs or other theoretical analysis, and the second algorithm is more efficient (in terms of computation, memory requirements, etc.).

Specifically for mathematical apparatus of Neural Networks - random matrix theory.  Non-asymptotic random matrix theory was used in some proofs of convergence of gradient descent for Neural Networks, high dimensional random landscapes in connection to Hessian spectrum have relation to loss surfaces of Neural Networks.
Topological data analysis is another area of intense research related to ML, AI and applied to Neural Networks.
There were some works on Tropical Geometry of Neural Networks
Homotopy Type Theory also have connection to AI


text:
What are the differences between network analysis and geometric deep learning on graphs?
Both of them deal with data of graph structure like a network community. Is there a big difference there?

Network analysis does not necessarily use deep learning techniques, while geometric deep learning (GDL) on graphs uses only deep learning techniques (that is, you train a neural network using gradient descent or other optimization methods). You can do some network analysis using GDL.

Both study properties of a network. The literature under respective titles seems to focus on certain topics.
Network analysis seems to focus on understanding the structure of a network. Centrality , modularity, assortativity etc are metrics used to study properties of networks. Key areas of research are for egs community detection, centrality measures, clustering algorithms, link prediction
GDL is oriented more towards using dataset structured as a graph as an input to machine learning problems like classification, regression.
Key areas of research include graph representation, neural architecture.
Some problems like link prediction for example are present in both domains.
Some problems like network construction for egs isn't covered deeply in both areas.
Some disciplines like algebraic graph theory appear in both disciplines.
Fiedler vector for egs  is studied in network analysis for community
detection . Spectral analysis, matrix factorisation are ideas being explored in representation learning.


text:
How are exploding numbers in a forward pass of a CNN combated?
Take AlexNet for example:

In this case, only the activation function ReLU is used. Due to the fact ReLU cannot be saturated, it instead explodes, like in the following example:
Say I have a weight matrix of [-1,-2,3,4] and inputs of [ReLU(4), ReLU(5), ReLU(-2), Relu(-3)]. The resultant matrix from these will have large numbers for the inputs of ReLU(4) and ReLU(5), and 0 for ReLU(-2) and ReLU(-3). If there are even just a few more layers, the numbers are quick to either explode or be 0.
How is this typically combated? How do you keep these numbers towards 0? I understand you can take subtract the mean at the end of each layer, but for a layer that is already in the millions, subtracting the mean will still result in thousands.

The most effective way to prevent both the forward and backward propagation of exploding is keeping the weights in a small range. The main way this is accomplished is through their initialization.
For example in the case of He initialization, the authors show (given some assumptions) that the variance of the output of the final layer $L$ of the network is:
$$
Var[y_L] = Var[y_1] \left( \prod_{i=2}^L{\frac{1}{2} \, n_l \, Var[w_l]} \right)
$$
where $n_l$ and $w_l$ are the number of connections and weights of layer $l$. In order to keep the outputs from exploding the product above should not exponentially magnify its inputs. In order to do this the authors elect to initialize the weights so that:
$$
\frac{1}{2} \, n_l \, Var[w_l] = 1
$$
Now this is helps keeping the outputs from exploding. They then go and prove that the same strategy helps preventing the gradients from exploding.
Another similar strategy is the so-called Glorot (or Xavier) Initialization.
These techniques are extremely effective in helping the models converge!

I had thought maybe this could be a solution, but assumed there was a way of applying this such that it was independent of the number of weights/layers. Thankyou for linking the paper, I'll give it a read when I get the time


text:
What is the purpose and benefit of applying CNN to a graph?
I'm new to the graph convolution network. I wonder what is the main purpose of applying data with graph structure to CNN?

Does this answer your question? What benefits can be got by applying Graph Convolutional Neural Network instead of ordinary CNN?

There are some problems that involve graphs and manifolds (sometimes collectively called non-Euclidean data), such as molecule design and generation, drug repositioning, social networks analysis, brain imaging, fake news detection, recommender systems, neutrino detection, computer vision and graphics and shape (e.g. hand or face) completion or generation (generative models).
The main benefit of geometric deep learning (deep learning applied to graphs and manifolds) is that you do not lose the information encoded in the graphs (or manifolds), which, otherwise, you would likely lose because you would need to convert your graphs (or manifolds) to an equivalent vector representation that you can feed into the existing CNN or other standard neural networks.
Note that you cannot directly apply the usual convolution operation to graphs, because, for example, graphs do not have the notion of relative positions of the nodes. Furthermore, note that graph networks have little to do with CNNs, even if they are sometimes called graph convolution networks.


text:
How do I know if my dataset is ready for a machine learning model?
I am new in this area of Machine Learning and Neural Networks. Currently, I'm taking some courses on Udemy and reading a book about it, but I still have one big question regarding data pre-processing.
In all of those Udemy's lessons, people always use a perfect dataset and ready to input in a model. So all you have to do is run it.
How do I know if my dataset is ready for a model? What do I have to do to make it ready? Which evaluations?
I had a few statistics classes in college already and I learned a lot about correlations matrices, autocorrelation functions, and its lags, etc. and I didn't see yet in anywhere someone explaining how can I evaluate my data and then proceed to implement a model to solve my problem.
If anyone could point me a direction, give me some material, show me where I can learn this, anything, it would be really helpful!

Before jumping to modeling, there are a few tasks a data scientist (or ML/AI practitioner) must do:

Ideation (or hypothesizing): Before applying any modeling approach, we need to ask the right questions. We must clearly mention our assumptions and declare how we want to measure the effectiveness of the pipeline. Note that, some tools/algorithms might not fit to the made assumptions or may not lead to the best values in the defined metrics. So, the pipeline must be designed in a way it serves the purpose of answering the defined questions.
Data Cleansing: Real-world data sets are usually not clean. They have all sorts of data issues such as missing value, duplicates, outliers, wrong measurements, fragments, inconsistency, etc. Most of the ML techniques are sensitive (to different extents, of course) to such issues. Therefore, the data should be cleaned before any modeling can be done.
Data Wrangling (or Feature Engineering): In many cases, the gathered data (even cleaned) is not immediately suitable for any modeling/analysis. For example, we may need to convert the documents of a text corpus to vectors of numbers (via TF-IDF or Embedding techniques) before being able to apply a text classifier simply because our classifier only takes numeric data. Converting measurements to other units, breaking addresses to their components, converting times and dates to different formats or timezones are just a few examples of data wrangling tasks (in a broader context, feature engineering may also refer to dimension reduction or feature selection/projection).
Exploratory Data Analysis (EDA): To do the cleansing, understanding the data set features, and ideation, we often need to explore the given data set using visual (e.g., dashboards and diagrams) or summary statistics tools.

Disclaimer: I have no business interest with Udemy. The links are just shared because @pedro-de-sá mentioned they take some courses from Udemy.

I would add that data cleansing and feature engineering are often part of the data preprocessing phase.

Thank you so much, @Borhan Kazimipour! Also if you have any books, articles or anything else to indicate me, works just fine too! It doesn't necessarily need to be Udemy's courses. Thanks once again!


text:
Why can a fully convolutional network accept images of any size?
On this article, it says that:

The UNET was developed by Olaf Ronneberger et al. for Bio Medical Image Segmentation. The architecture contains two paths. First path is the contraction path (also called as the encoder) which is used to capture the context in the image. The encoder is just a traditional stack of convolutional and max pooling layers. The second path is the symmetric expanding path (also called as the decoder) which is used to enable precise localization using transposed convolutions. Thus it is an end-to-end fully convolutional network (FCN), i.e. it only contains Convolutional layers and does not contain any Dense layer because of which it can accept image of any size.

What I don't understand is how an FCN can accept images of any size, while an ordinary object detector, such as YOLO with a dense layer at the very end, cannot accept images of any size.
So, why can a fully convolutional network accept images of any size?

Because it don't have dense layers obviously. Convolutional layer work for any input size (more then kernel size)

The reason is that when using a convolutional layer, you select the size of the filter kernels, which are independent of the image/layer input size (provided that images smaller than the kernels are padded appropriately).
When using a dense layer, you specify the size of the layer itself and the resulting weight matrix is a function of both the size of the dense layer and the upstream layer. This is because each neuron in the upstream layer makes a connection to each neuron in the dense layer. So, if you have 50 neurons in the upstream layer and 20 neurons in the dense layer, then the weight matrix has $50 \times 20=1000$ values. Those weights are what get determined during the training phase, and so those layer sizes are fixed.
Now, the output of a CNN layer is a number of images/tensors (specified by the number of filters chosen), whose size is determined by the kernel size and any padding option chosen. If those are fed into a dense layer, then that fixes the the size that those images can be (because of the reason given in the previous paragraph).
On the other hand, if no dense layer is used in the whole network, then the input to the first CNN layer can be any size because the weights are just the individual parameters of the filter kernels, and the filter kernels remain the same size regardless of the input tensor size.

If you feed a FCN (fully convolutional network) with a input of size $50\times 50$ and $300 \times 300$, although you have no problem processing with convolutions and pooling layers, how you output class score since the output size of convolutional layers depends on the size of their input?


text:
How do I locate a specific object in an image?
Some pictures contain an elephant, others don't. I know which of the pictures contain the elephant, but I don't know where it is or how does it look like.
How do I make a neural network which locates the elephant on a picture if it contains one? There are no pictures with more than one elephant.

so assuming your not allowed to use transfer methodologies (like take an already exisiting elephant object detector) my recommendation is to train a CNN classifier (labels are binary-- elephant exist, elephant doesnt exist) and then use strategies founded in like grad cam. Note there does exist a gradcam++ but because you can assure theres only one instance, it isnt necessary and is just more complicated.
Note that since you just need the location and not the pixel specificity, you dont even need to do the guided backprop, but just the relation with respect to the last convoluitional map.
A quick description is that its using the gradient of the class loss w.r.t the last feature map to see which locations helped make the classification, and from there you can upscale to the receptive field that those neurons touch
Hope this helped!