text:
Is the minimum and maximum of a set of admissible and consistent heuristics also consistent and admissible?
Let's suppose I have a set of heuristics $H$ = {$h_1, h_2, ..., h_N$}.

If all heuristics in $H$ are admissible, does that mean that a heuristic that takes the $\min(H)$ (or $\max(H)$ for that matter) is also admissible?
If all heuristics in $H$ are consistent, does that mean that a heuristic that takes the $\min(H)$ (or $max(H)$ for that matter) is also consistent?

I'm thinking about a search problem in a bi-dimensional grid that every iteration of an algorithm, the agent will have to find a different goal. Therefore, depending on the goal node, a certain heuristic can possibly better guide the agent than the others (hence the use of $\min$ and $\max$).

Yes, in both cases. Below I give two very simple proofs that directly follow from the definitions of admissible and consistent heuristics. However, in a nutshell, the idea of the proofs is that $h_{\max}(n)$ and $h_{\min}(n)$ are, by definition (of $h_{\max}$ and $h_{\min}$), equal to one of the given admissible (or consistent) heuristics, for all nodes $n$, so $h_{\max}(n)$ and $h_{\min}(n)$ are consequently admissible (or consistent).
Definitions
Consider the graph $G=(V, E, \mathcal{G})$ representing the search space, where $V$, $E$ and $\mathcal{G} \subseteq V$ are respectively the set of nodes, edges and goal nodes, and the function $w\colon E \times E \rightarrow \mathbb{R}$, which gives you the cost of each edge $e = (u, v) \in E$, where $u, v \in V$, that is, $w(e) = w(u, v) \in \mathbb{R}$ is the cost of the edge $e$.
A heuristic $h$ is admissible if $$h(n) \leq h^*(n), \forall n \in V,$$
where $h^*(n)$ is the optimal cost to reach a goal from node $n$ (that is, it is the optimal heuristic).
On the other hand, a heuristic $h$ is consistent if
\begin{align}
h(n) &\leq w(n, s) + h(s), \forall n \in V \setminus \mathcal{G}, \text{ and} \\
h(n) &= 0, \forall n \in \mathcal{G},
\end{align}
where $s$ is a successor of $n$.
Theorem 1
Given a set of admissible heuristics $H = \{ h_1, \dots, h_N \}$, then, for every $n \in V$, the heuristics $h_{\max}(n) = \max(h_1(n), \dots, h_N(n))$ and $h_{\min}(n) = \min(h_1(n), \dots, h_N(n))$ are also admissible.
Proof
Given that, $h_i(n) \leq h^*(n), \forall n \in V$ and $\forall i \in \{ 1, \dots N \}$, then $h_{\max}(n) = h_j(n) \leq h^*(n)$ (for some $j \in \{ 1, \dots N \}$)  and $h_{\min}(n) = h_k(n) \leq h^*(n)$ (for some $k \in \{ 1, \dots N \}$), so $h_{\max}$ and $h_{\min}$ are also admissible.
$\tag*{$\blacksquare$}$
Theorem 2
Given a set of consistent heuristics $H = \{ h_1, \dots, h_N \}$, then, for every $n \in V$, the heuristics $h_{\max}(n) = \max(h_1(n), \dots, h_N(n))$ and $h_{\min}(n) = \min(h_1(n), \dots, h_N(n))$ are also consistent.
Proof
Given that, for every $i \in \{ 1, \dots, N \}$,
\begin{align}
\begin{cases}
h_i(n) \leq w(n, s) + h_i(s), & \text{ if }  n \in V \setminus \mathcal{G}\\
h_i(n) = 0, & \text{ if }  n \in \mathcal{G}
\end{cases}
\end{align}
then, if $n \in V \setminus \mathcal{G}$, $h_{\max}(n) = h_j(n) \leq w(n, s) + h_j(s)$, for some $j \in \{1, \dots, N \}$, and, similarly, $h_{\min}(n) = h_k(n) \leq w(n, s) + h_{k}(s)$, for some $k \in \{1, \dots, N \}$. Similarly, if $n \in \mathcal{G}$, $h_{\max}(n) = h_{\min}(n) = h_i(n) = 0, \forall i \in \{1, \dots, N \} $. Thus, $h_{\max}$ and $h_{\min}$ are also consistent.
$\tag*{$\blacksquare$}$
Notes
$h_{\max}$ and $h_{\min}$ have been defined in the only possible reasonable way, because, given two (admissible or consistent) heuristics, one may not always dominate the other (or vice-versa), even if both are admissible and consistent.

When you say "hmax(n)=hj(n)≤w(n,s)+hj(s), for some j∈{1,…,N}", aren't you implicity assuming nodes n and s both using ith heuristic, but this may not be the case. What you need to show is "hmax(n) = hi(n) ≤ w(n, s) + hj(s), for some i,j ∈{1,…,N}" or am I mistaken?


text:
Why is the Jensen-Shannon divergence preferred over the KL divergence in measuring the performance of a generative network?
I have read articles on how Jensen-Shannon divergence is preferred over Kullback-Leibler in measuring how good a distribution mapping is learned in a generative network because of the fact that JS-divergence better measures distribution similarity when there are zero values in either distribution.
I am unable to understand how the mathematical formulation of JS-divergence would take care of this and also what advantage it particularly holds qualitatively apart from this edge case.
Could anyone explain or link me to an explanation that could answer this satisfactorily?

Lets start with question 1) how does JS-divergence handles zeros?
by definition:
\begin{align}
D_{JS}(p||q) &= \frac{1}{2}[D_{KL}(p||\frac{p+q}{2}) + D_{KL}(q||\frac{p+q}{2})] \\
&= \frac{1}{2}\sum_{x\in\Omega} [p(x)log(\frac{2 p(x)}{p(x)+q(x)}) + q(x)log(\frac{2 q(x)}{p(x)+q(x)})]
\end{align}
Where $\Omega$ is the union of the domains of $p$ and $q$. Now lets assume one distribution is zero where the other is not (without loss of generality due to symmetry we can just say $p(x_i) = 0$ and $q(x_i) \neq 0$. We then get for that term in the sum
$$\frac{1}{2}q(x_i)log(\frac{2q(x_i)}{q(x_i)}) = q(x_i)\frac{log(2)}{2}$$
Which isn't undefined as it would be the KL case.
Now onto 2) In GANS why does JS divergence produce better results than KL
The asymmetry of KL divergence places an unfair advantage to one distribution over the other where in this case, its not ideal to consider it this way from an optimization perspective. Additionally KL divergences inability to handle non-overlapped distributions is crushing given that these are approximated through sampling schemes, and therefore there are no guarantees. JS solves both those issues and leads to a smoother manifold which is why its generally preferred. A good resource is this paper where they go more in detail investigating this.

source: Stack Exchange

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

sort: votes


text:
What could be the problem when a neural network with four hidden layers with the sigmoid activation function is not learning?
I have a large set of data points describing mappings of binary vectors to real-valued outputs. I am using TensorFlow, and would like to train a model to predict these relationships. I used four hidden layers with 500 neurons in each layer, and sigmoidal activation functions in each layer.
The network appears to be unable to learn, and has high loss even on the training data. What might cause this to happen? Is there something wrong with the design of my network?

When training our neural network, you need to scale your dataset in order to avoid slowing down the learning or prevent effective learning.
Try normalizing your output.
This Tutorial might help

@AggrajGupta See me answer. You should also scale your data, but that's probably not the root of your problem.

Your code suggests a likely problem here: It looks like you are training a very deep neural network with sigmoidal activation functions at every layer.
The sigmoid has the property that its derivative (S*(1-S)) will be extremely small when the activation function's value is close to 0 or close to 1. In fact, the largest it can be is about 0.25.
The backpropigation algorithm, which is used to train a neural network, will propagate an error signal backwards. At each layer, the error signal will be multiplied by, among other things, the derivative of the activation function.
It is therefore the case that by the 4th layer your signal is at most $0.25^4 = \frac{1}{256}$ the size that it was at the start of the network. In fact, it is likely much smaller than this. With a smaller signal, your learning rates at the bottom of the nextwork will effectively be much smaller than the learning rates at the top, which will make it very difficult to pick a learning rate that is effective overall.
This problem is known as the vanishing gradient.
To fix this, if you want to use a deep architecture, consider using an activation function that does not suffer from a vanishing gradient. The Rectified Linear activation function, used in so-called "ReLU" units, is a non-linear activation that does not have a vanishing gradient. It is common to use ReLUs for the earlier layers in a network, and a sigmoid at the output layer, if you need outputs to be bounded between 0 and 1.

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


text:
How is gradient being calculated in Andrej Karpathy's pong code?
I was going through the code by Andrej Karpathy on reinforcement learning using a policy gradient. I have some questions from the code.

Where is the logarithm of the probability being calculated? Nowhere in the code I see him calculating that.
Please explain to me the use of dlogps.append(y - aprob) line. I know this is calculating the loss, but how is this helping in a reinforcement learning environment, where we don't have the correct labels?
How is policy_backward() working? How are the weights changing to the loss function mentioned above? More specifically, what's dh here?

logp seen in code is actually logit p which has this story behind:

Given a probability p, the corresponding odds are calculated as p / (1 – p). For example if p=0.75, the odds are 3 to 1: 0.75/0.25 = 3.
The logit function is simply the logarithm of the odds: logit(x) = log(x / (1 – x)).

Sigmoid near logp is like follows:

The inverse of the logit function is the sigmoid function. That is, if you have a probability p, sigmoid(logit(p)) = p.

Source: [1]

In reinforcement learning we know in the end of game, if taken actions were successful or not. Then before next round we can adjust the gradients. From your link (commentary section):

For example in Pong we could wait until the end of the game, then take the reward we get (either +1 if we won or -1 if we lost), and enter that scalar as the gradient for the action we have taken (DOWN in this case). In the example below, going DOWN ended up to us losing the game (-1 reward). So if we fill in -1 for log probability of DOWN and do backprop we will find a gradient that discourages the network to take the DOWN action for that input in the future (and rightly so, since taking that action led to us losing the game).

In the very same commentary section (later) there is a pic, and explanation of what h is. Unfortunately, you have to check it by yourself, pic was not compatible to be attached here. By describing the pic I could say h is equal to weights in hidden layer and in gradient case the dh is the derivative of h.

Roughly speaking the backpropagation is correcting the weights backwards the network after the round is done. More thorough explanation is in the mentioned comments section.
Sources:
[1] https://www.google.com/amp/s/nathanbrixius.wordpress.com/2016/06/04/functions-i-have-known-logit-and-sigmoid/amp/

Thanks a lot for this superb explanation. I do have one question. One other implementation uses one hot encoding to train the neural network but Andrej doesn't do that. Would you be able to be tell me why the difference?

Does that another neural network do the same thing (try to play pong)? I don't see how one hot decoding, or any decoding plays part on this task. For categorizing apples and oranges from peaches I see it useful.

See: https://hackernoon.com/what-is-one-hot-encoding-why-and-when-do-you-have-to-use-it-e3c6186d008f

So this is Keras implementation of Karpathy's code. This person is also implementing RL on pong. Checkout line 108. I think the person is doing one-hot encoding here
https://github.com/Alexander-H-Liu/Policy-Gradient-and-Actor-Critic-Keras/blob/master/agent_dir/agent_pg.py

Maybe ask another question about the comparison of these solutions?

can you tell me that I'm the discounted reward function, he adds a reset condition for reward sum and says that it's pong specific. Can you tell me why did he do that?


text:
Can you build a pure CNN phoneme classification model?
I was making a simple phoneme classification model for a 10 week-long class project and I ran into a small question.
Is it possible to create a model that takes a 1-second (the longest phoneme is 0.2 second but the large image is kept for context) spectrogram as input? Some people suggest creating an RNN for phoneme classification, but can you build a pure CNN phoneme classification model?

Yes you can, a few years ago I made a simple CNN for a single Arabic phoneme classification. You can use spectogram or using MFCC / MFSC as features, as long all data has the same size (use padding or cropping if needed).
You may need RNN if you want to combine some phonemes to recognize a single word or longer.

Wow, thanks a lot! Any suggestions for the model shape (how many layers and how many filters)?

Actually, it all depends on your case, for a simple case I think you only need one or two convolutional layers and a single fully-connected layer. I usually use around 30 filters. But, just try it to find your best values :)

Okay, well I actually I have a full model written down but it isn't running well (not increasing in accuracy). Where should I post my code and give a better description of my model?

You can ask another question if you think there are some errors in your models. But, you may ask an implementation question that out of topic in AI.SE if your question is about errors in your code/implementation, you should ask that in Data Science SE

Okay thanks, I put the question on this link, so you can look over it if you want to, 'https://datascience.stackexchange.com/questions/63376/cnn-model-not-converging'

@HozaifaBhutta if this or any answer in the future solved your question please consider accepting it by clicking the check-mark. This indicates to the wider community that you've found a solution. There is no obligation to do this.

Quick question, I have a 2 layer network (one convolution, 30 filters, and one output layer). What should the dropout amount be?

What do you mean by "amount"?

So I currently made the dropout rate 35% for my convolution layer. Is this a good rate? Should I add dropout for my output layer?

the dropout rate is one of the hyperparameters that you need to tune, but, in many papers people use 50% rate.

for placement you can read explanations here and here

How big was your input size? As in how long was each utterance


text:
Can Google's patented ML algorithms be used commercially?
I just find that Google patents some of the widely used machine learning algorithms. For example:

System and method for addressing overfitting in a neural network (Dropout?)
Processing images using deep neural networks
Methods and apparatus for reinforcement learning (Q-Learning?)

Does that mean I can't use those algorithms commercially?

Can you use them commercially?
Yes.
Is Google able to sue you any time they want?
Yes.
Will they do that...
Probably not.
Google isn't a known patent bully, I would give them the benefit of the doubt in this kind of situation and say, unless you start really giving them real trouble, they wouldn't do anything. Some companies/people know an idea can really be used for good and patent it to protect its use not to inhibit its use. By patenting the idea and setting a precedent of not suing they are effectively allowing everyone to benefit. Maybe in the future Google cloud, Azure and Amazon web services will lose some money in a legal battle, but I doubt you personally will be hit with a lawsuit.

As a small note: in the unlikely case that you do develop software based on this patent that directly competes with Google, and even in such a way that it threatens their revenue, they will find any and all possible ways to shut you down - including patent infringement (as is their right). I agree that you should just use it, but keep it in the back of your head that they still can sue if they want.


text:
What is a "surrogate model"?
In the following paragraph from the book Automated Machine Learning: Methods, Systems, Challenges (by Frank Hutter et al.)

In this section we first give a brief introduction to Bayesian optimization, present alternative surrogate models used in it, describe extensions to conditional and constrained configuration spaces, and then discuss several important applications to hyperparameter optimization.

What is an "alternative surrogate model"? What exactly does "alternative" mean?

What is Bayesian optimization?
Introduction
Bayesian optimization (BO) is an optimization technique used to model an unknown (usually continuous) function $f: \mathbb{R}^d \rightarrow Y$, where typically $d \leq 20$, so it can be used to solve regression and classification problems, where you want to find an approximation of $f$. In this sense, BO is similar to the usual approach of training a neural network with gradient descent combined with the back-propagation algorithm, so that to optimize an objective function. However, BO is particularly suited for regression or classification problems where the unknown function $f$ is expensive to evaluate (that is, given the input $\mathbf{x} \in \mathbb{R}^d$, the computation of $f(x) \in Y$ takes a lot of time or, in general, resources). For example, when doing hyper-parameter tuning, we usually need to first train the model with the new hyper-parameters before evaluating the specific configuration of hyper-parameters, but this usually takes a lot of time (hours, days or even months), especially when you are training deep neural networks with big datasets. Moreover, BO does not involve the computation of gradients and it usually assumes that $f$ lacks properties such as concavity or linearity.
How does Bayesian optimization work?
There are three main concepts in BO

the surrogate model, which models an unknown function,
a method for statistical inference, which is used to update the surrogate model, and
the acquisition function, which is used to guide the statistical inference and thus it is used to update the surrogate model

The surrogate model is usually a Gaussian process, which is just a fancy name to denote a collection of random variables such that the joint distribution of those random variables is a multivariate Gaussian probability distribution (hence the name Gaussian process). Therefore, in BO, we often use a Gaussian probability distribution (the surrogate model) to model the possible functions that are consistent with the data. In other words, given that we do not know $f$, rather than finding the usual point estimate (or maximum likelihood estimate), like in the usual case of supervised learning mentioned above, we maintain a Gaussian probability distribution that describes our uncertainty about the unknown $f$.
The method of statistical inference is often just an iterative application of the Bayes rule (hence the name Bayesian optimization), where you want to find the posterior, given a prior, a likelihood and the evidence. In BO, you usually place a prior on $f$, which is a multivariate Gaussian distribution, then you use the Bayes rule to find the posterior distribution of $f$ given the data.
What is the data in this case? In BO, the data are the outputs of $f$ evaluated at certain points of the domain of $f$. The acquisition function is used to choose these points of the domain of $f$, based on the computed posterior distribution. In other words, based on the current uncertainty about $f$ (the posterior), the acquisition function attempts to cleverly choose points of the domain of $f$, $\mathbf{x} \in \mathbb{R}^d$, which will be used to find an updated posterior.  Why do we need the acquisition function? Why can't we simply evaluate $f$ at random domain points? Given that $f$ is expensive to evaluate, we need a clever way to choose the points where we want to evaluate $f$. More specifically, we want to evaluate $f$ where we are more uncertain about it.
There are several acquisition functions, such as expected improvement, knowledge-gradient, entropy search, and predictive entropy search, so there are different ways of choosing the points of the domain of $f$ where we want to evaluate it to update the posterior, each of which deals with the exploration-exploitation dilemma differently.
What can Bayesian optimization be used for?
BO can be used for tuning hyper-parameters (also called hyper-parameter optimisation) of machine learning models, such as neural networks, but it has also been used to solve other problems.
What is an alternative surrogate model?
In the book Automated Machine Learning: Methods, Systems, Challenges (by Frank Hutter et al.) that you are quoting, the authors say that the commonly used surrogate model Gaussian process scales cubically in the number of data points, so sparse Gaussian processes are often used. Moreover, Gaussian processes also scale badly with the number of dimensions. In section 1.3.2.2., the authors describe some alternative surrogate models to the Gaussian processes, for example, alternatives that use neural networks or random forests.

A surrogate model is a simplified model. It is a mapping $y_S=f_S(x)$ that approximates the original model $y=f(x)$, in a given domain, reasonably well. Source: Engineering Design via Surrogate Modelling: A Practical Guide
In the context of Bayesian optimization, one wants to optimize a function $y=f(x)$ which is expensive (very time consuming) to evaluate, therefore one optimizes the surrogate model $y_S=f_S(x)$ which is cheaper (faster) to evaluate.

Forgive my ignorance, but why exactly is yS=fS(x) faster to evaluate?

Imagine that the original model is computed from Finite Element simulations (x would be some geometric parameter or material constant for instance and f(x) some quantity of interest) and f_S is a polynomial approximation like a0 + a1x + a2x^2. f(x) can take some hours to evaluate whereas f_S(x) can be calculated pretty fast

Recently, I've been thinking this question as well. After reading several papers, finally came up with some thoughts about the surrogate model.
In FEM(finite element method), we try to find a weak form to approximate the strong form so that we can solve the weak form analytically. (weak form: approximation equation; strong form: PDE in real world) In my opinion, the surrogate model can be regarded as 'weak form'. There are many methods can form a surrogate model. And if we use a NN model as the surrogate model, the training process is equivalent to 'solving analytically'.


text:
Is k-fold cross-validation more effective than splitting the dataset into training and test datasets to prevent overfitting?
I want to prevent my model from overfitting. I think that k-fold cross-validation (because it is doing this each time with different datasets) may be more effective than splitting the dataset into training and test datasets to prevent overfitting, but a colleague (who has little experience in ML) says that, to prevent overfitting, the 70/30% split performs better than the k-fold cross-validation. In my opinion, k-fold cross-validation provides a reliable method to test the model performance.
Is k-fold cross-validation more effective than splitting the dataset into training and test datasets to prevent overfitting? I am not concerned with computational resources.

K-fold cross-validation is probably preferred in terms of completeness and generalization: you ensure that the system has seen the complete dataset for training. However, in deep learning this is often not feasible due to time and power constraints. They can both be used, and there is not one better than the other. It really depends on the specific case, the size of the dataset and the time and hardware available. Note that overfitting can be (partially) remedied by things such as dropout.
To be fair: it is fine to have a discussion about this with your colleagues, but as so often there is no one correct answer. If you really want proof, you can test it out and compare them. But performance-wise (i.e. the model's predictive power), the difference will be small.

Purely in terms of overfitting, and assuming you train both for equal amounts of time, 70/30 is probably better but performance is not going to be very good. Not training on %30 of data will make both training and test results equally bad (in my opinion). But it won't overfit, that is for sure. Cross validation (you have in mind 90/10, I assume) will take a long time, so that won't have enough time to train and it might be overfitting more compared to 70/30, but as it is going to see all training samples %90 at a time, there is a good chance it will train better. So, at the end of the day, it will overfit more but perform better.
If you are asking which is better overall, performance and overfitting, I say it depends on the size of your dataset. If you have millions of samples in it, you can even use a 98/1/1 for training, testing and validation and still be OK.
Edit: Thinking a little more about it, even if the time is not an issue the situation will roughly be the same. But you will know the performance of the model on new data to a higher certainty with cross validation.

What do you mean with: ",it will overfit a more but perform better"?

Using loss as a criteria, I mean both training and test results will be higher, but the ratio of test loss to training loss will be lower compared to 70/30 split.

I meant both training and test results will be lower, not higher in above comment. And also training loss to test loss ratio. It is loss, not accuracy so the lower the better. I am unable to edit the comment, sorry for the second comment.

No i understood what you are trying to say, thank you

Both methods are fine if used properly. As a rule of thumb, when training time is not an issue, use split method if you have more data than you can use in your model and cross-validation if not. I would suggest handling overfitting by some other means.

I think this decision will be different from case to case.
For example, when deep learning networks are used in new architectures such as using a pre-trained network to extract features and using machine learning classifiers to classify data.
You can no longer use the fold method here!! Because the network is no longer fine-tuning!
In the 15-15-70 method, we can use more number of runs to reduce the variance.
In this way, the problem can be solved according to the requested example.


text:
What are examples of books or papers on the details of convolutional neural networks?
I'm studying a master's degree and my final work is going to be about the convolutional neural network.
I read a lot of books and I did Convolutional Network Standford's course, but I need more.
Are there books or papers on the details of convolutional neural networks (in particular, convolutional layer)?

Chapter 9 of the book Deep Learning (2016), by Goodfellow et al., describes the convolutional (neural) network (CNN), its main operations (namely, convolution and pooling) and properties (such as parameter sharing).
There's also the article From Convolution to Neural Network, which first introduces the mathematical operation convolution and then describes its connection with signal processing (where images can be viewed as 2D signals) and, finally, describes the CNN.

Chris Olah's work is always inspired, and not too technical as one would expect. He has several papers on CNNs on his website. In particular, check the series titled "Convolutional Neural Networks" with four papers on the topic.

You can look at the paper Gradient-Based Learning Applied to Document
Recognition (1998) by Yann LeCun et al., which reviews and compares various methods applied to handwritten character recognition and shows that CNNs outperform all other methods.
Also, I suggest Andrew Ng's CNN videos.

I'm not sure if this is what you are looking for but I find Goodfellow's book a pretty good resource:
Goodfellow, specifically Section 2, Chapter 9 deals with convolutional neural networks: https://www.deeplearningbook.org/
'Pattern Recognition and Machine Learning' by Bishop Might contains a section (5.5.5, pg 267 onwards) as well as an exercise, and a general discussion about neural networks in image recognition.
If you edit your question to post a bit more detail, we can offer better answers, for example, what is about the convolutional layer?  How it's implemented?
If you are looking for a more basic introduction to convolutional layers I would also suggest:
A Comprehensive Guide to Convolutional Neural Networks — the ELI5 way gives a pretty general overview, starting at the difference between CNNs and ANNs and explains why CNNs are superior to ANNs (for certain problems).  It also gives some details about how the convolution actually works.
Demystifying the transpose convolution explains the transpose convolution operation in the context of how a traditional convolution; this may not be relevant if you are strictly using CNNs and not transpose-CNNs.
Understanding of Convolutional Neural Network (CNN) — Deep Learning is quite similar to "A Comprehensive..." link above, but it also includes information about filtering and shows the effect that different filters have on an image, which is certainly very import to an understanding of why we use CNNs.
Building a Convolutional Neural Network (CNN) in Keras (or one of the other thousand similar pages) are pretty good for just starting out and building your own CNN classifier.  You can also check out examples from Keras, e.g. CIFAR10 CNN, but these tend to give you a very little information about why they designed the network the way that they did.
If, on the other hand, you are looking for some more advanced resources, here are is one that springs to mind:
Deep Residual Learning for Image Recognition by He et al., deals with a major advance in image recognition, using Residual Networks (ResNet).  This type of network has become pretty popular, so I highly recommend giving it a read.

Thanks, I thought I could only ask one question. You can add all of the details that you want to your answer without asking it explicitly.

I meant, expand on your existing question, what about convolutional layers are you interested in?

I'm interested in everything related to CNN.


text:
What does end-to-end training mean?
In simple words, what does end-to-end training mean, in the context of deep learning?

You have a couple of good answers to the following Quora question What does it mean for a neural network to be trained end-to-end?.

Another explanation of deep learning as an end-to-end framework is in deep learning, pre-processing or feature extraction steps are not necessary. So it only uses a single processing step, which is to train the deep learning model. In other traditional machine learning methods, some separated feature extraction steps usually required.

For example in image classification, deep learning frameworks like CNN can receive a raw image and then trained to classify it directly. If we didn't use deep learning, we need to extract some features using more steps, like edge detection, corner detection, color histogram, etc.
you can also watch Andrew Ng's explanation here

Technically you often need a stage of feature preparation/pre-processing, to normalise inputs into ranges suitable for NNs. However, that is quite simple.

This is relevant when you have two or more neural networks serving as components to a larger architecture. Training this architecture in an end-to-end manner means simultaneously training all components (i.e. training it as a single network).
The best example I can think of are image captioning architectures. These usually comprise of two networks: a CNN whose role is to extract features from the input images and a RNN that accepts the CNN's features and generates the output captions.

You have two options for training:

First, train the CNN first for some arbitrary task (e.g. image classification) in hopes that it learns how to extract features. Then use the CNN to extract features from the input images and use those as inputs to train the RNN. This procedure trains the two components in two completely separate phases.
Treat the whole architecture as a single network and backpropagete the gradients to the CNN so that it also can be trained. This procedure trains the two components simultaneously. This is what we call end-to-end training.

End to end means deep learning is the only thing that is used.
Many people have doubts on its viability though, I certainly do. I wouldn't trust an end-to-end DL based self driving car.

I think that this answer is more consistent with the usage of end-to-end training.

I have done stuff in the robotics department at my university and End to End DL explicitly refers to DL being used to generate "intelligent" responses in an end to end fashion.


text:
Why does a Lipschitz continuous discriminator in GANs assure statistical boundedness?
I have been reading the paper which introduced spectral normalization in GANs.
At some point the paper mentions the following:

The machine learning community has been pointing out recently that the
  function space from which the discriminators are selected crucially
  affects the performance of GANs. A number of works (Uehara et al.,
  2016; Qi, 2017; Gulrajani et al., 2017) advocate the importance of
  Lipschitz continuity in assuring the boundedness of statistics.

What does it mean that the Lipschitz continuity assures the boundedness of statistics and why does that happen?

To put it simply GANs suffer from a problem of uneven learning rate. Imagine the learning rate of a pitcher and hitter if the pitcher gets to a point where they can throw much better than the hitter can hit then the hitter may fall into a 'training pit' as to be unable to ever learn how to hit from the pitcher.
This follows a continues relationship in between the two learning rates where if the pitcher is becoming a much better pitcher at a faster rate they could become too good and make learning impossible for the hitter. So the rate must be 'slowed down' as to ensure the pitcher doesn't ruin the hitter.
If the cone of the Lipschitz continuity function of either function is outrunning/outpacing the other than the learning for the one who is in front must be slowed down so the other catches up.
Two runners trying to push each other athletically is another example. If one outpaces the other an injury may occur in the one lagging behind while trying to keep pace this happens, when the adversarial network becomes too good at generating training material that the behind network is not ready to learn with.
The GAN will do best when the learning rates are adjusted to slow down the fast learner artificially.
The statistics will not be bounded correctly if the learning rates are not kept in check similarly to how step size needs to be right to find local minimum and maximum. If the learning is not artificial augmented so both keep relatively same pace getting stuck at local minimum and maximum of the solution space will occur.

What do you mean by saying that the cone of one function is outrunning the other? I know that for a Lipschitz function there should exist a cone which you can move along the x axis and have the whole graph outside the cone, but I do not understand what do you mean by this.

If the two functions representing the two problems learning space differ and the slope of one is steeper then the other then the learning rates will be unequal. If one of the models out runs the other than it wrecks the two runners keeping pace phenomenon. For learning problems a function exists that represents different phases of learning the problem. Like a discriminators may have a nearly flat line learning the difference between black boots and white boots but may have a very steep(difficult) time learning the difference  between black stilettos and black pumps.


text:
What do the subscripts mean in $N_{t,n,\sigma,L}$?
A neural network can apparently be denoted as $N_{t,n,\sigma,L}$. What do these subscripts  $t, n, \sigma$ and $L$ mean? Could you link me to a paper, article or webpage with an explanation for this?

Here is a paper with the mathematical definition of each term:

Let Nt,n,σ,L be all target functions that can be implemented using a
  neural network of depth t, size n, activation function σ, and when we
  restrict the input weights of each neuron to be |w|1 + |b| ≤ L.

Does "size $n$" mean that the network has $n$ input nodes?

Check the introduction: "The depth of the network is the number of layers and the size of the network is the total number of neurons."


text:
How do I combine models trained on different data to increase classification accuracy?
I have two trained models. One is using a LinearSVC algorithm and is trained on numerical data from medical examination from patients with diabetic retinopathy. The second one is a neural network trained on images of retina scans from patients with the same disease.
The models predict if the patient has retinopathy or not. Both are written using Python 3.6 and Keras and have accuracy around 0.84.
Is it possible to combine those two models in any way to increase the accuracy of predictions?
I'm not sure in what way it could be achievable as they are using a different kinds of data. I have tried using ensembling methods but didn't get better scores with them.

What exactly have you tried with regards to ensembling as mentioned at the end of your question?

basically methods from this

You can try using a multi-input model. Here is a recent post with a similar discussion, with the required architecture defined in the answer.
Instead of combining the separate models, you can create a model which uses image and numerical data side by side. Keras allows you to use different types of data using multi input structure via functional API. And then you can combine them to create a single machine learning model. Basic idea is like this:

This image was taken from here, where you can find further details and the code implementation as well. Actually, the discussion in the introduction of that post is almost the same as your question: What to do when the inputs are:

Numeric/continuous values, such as age, heart rate, blood pressure
Categorical values, including gender and ethnicity
Image data, such as any MRI, X-ray, etc.

Also, section 5.1 of this blogpost details the same process.

Can you argue/elaborate why a multi-input model would be useful in this case?

Is this case much different from the one I provided the link above, except for the use of SVC instead of a dense model? It is a valid way to combine different input types, and can be achieved using Keras. Whether it will improve the accuracy or not is subject to experiment.

I've not read the other post, but I think you should at least argue in this question why the solution given in another place may be useful.


text:
Is it better to adjust the natural lighting (while recording the video) or to subsequently apply filters on the original video?
For the purpose of object detection, is it better to adjust the natural lighting (while recording the video) or to apply filters (e.g. brightness filters, etc.) on the original video to make it brighter?
My intuition is that it shouldn't matter when you adjust the natural lighting or do it after with video filters.

Personally, I'd say as long as the object is visible don't do either. If the model has been well built and if lighting changes would help, the convolution operation weights would learn an operation similar to contrast or brightness changes.
On the other hand if the object visibility is an issue, then natural lighting changes would be better, due to the lack of potential artefacts a filter would create.
So overall, I'd say natural lighting changes should be more helpful (Assuming model is built well) and brightness filters would not be very helpful as the convolution operations would learn them if they were useful, also there would be  artefacts in the input which can lead to the model learning irrelevant details.
Hope this helped!


text:
How does the policy gradient's derivative work?
I am trying to understand the policy gradient method using a PyTorch implementation and this tutorial.
My first question is about the end result of this gradient derivation,
\begin{aligned}
\nabla \mathbb{E}_{\pi}[r(\tau)] &=\nabla \int \pi(\tau) r(\tau) d \tau \\
&=\int \nabla \pi(\tau) r(\tau) d \tau \\
&=\int \pi(\tau) \nabla \log \pi(\tau) r(\tau) d \tau \\
\nabla \mathbb{E}_{\pi}[r(\tau)] &=\mathbb{E}_{\pi}[r(\tau) \nabla \log \pi(\tau)]
\end{aligned}
Mainly in this equation
$$\nabla \mathop{\mathbb{E}_\pi }[r(\tau )] = \mathop{\mathbb{E}_\pi }[r(\tau )\nabla log \pi (\tau )]$$
Does expectation follow a distributive or associative property?
I know that expectations of a function can be written as below
$$\mathop{\mathbb{E}}[f(x)] =\sum p(x)f(x)$$
Then can we rewrite the first equations as
$$\mathop{\mathbb{E}_\pi }[r(\tau )\nabla log \pi (\tau )] \\= \mathop{\mathbb{E}_\pi }[r(\tau )] \,\, \mathop{\mathbb{E}_\pi }[\nabla log \pi (\tau )] \\= \sum p(\tau)r(\tau ) \,\, \sum p(\tau)\nabla log \pi (\tau ) \\
= p(\tau) \sum r(\tau ) \nabla log \pi (\tau )$$
The problem is when I compare  this to PyTorch implementation (line 71-74)
for log_prob, R in zip(policy.saved_log_probs, returns):
    policy_loss.append(-log_prob * R)
optimizer.zero_grad()
policy_loss = torch.cat(policy_loss).sum()

The  pytorch implementation simply multiplied log probability and reward -log_prob * R and then summed the vector torch.cat(policy_loss).sum() there is no $p(\tau)$. What is really happening here?
The second question is the multiplication of log probability and reward in PyTorch implementation -log_prob * R, PyTorch implementation has a negative log probability and derived equation has a positive one $\mathop{\mathbb{E}_\pi }[r(\tau )\nabla log \pi (\tau )]$. What is the need for multiplying log probability with a negative value in PyTorch implementation?
I have only a basic understanding of maths and that's why I am asking this question here.

Edit: found a better derivation of above equation https://youtu.be/Ys3YY7sSmIA?t=3622

You cannot do this:

$\mathop{\mathbb{E}_\pi }[r(\tau )\bigtriangledown log \pi (\tau )] \\= \mathop{\mathbb{E}_\pi }[r(\tau )] \,\, \mathop{\mathbb{E}_\pi }[\bigtriangledown log \pi (\tau )]$

That is because $r(\tau )$ and $\bigtriangledown log \pi (\tau )$ are correlated by their dependence on $\tau$. In a simpler concrete example, if your expectation was over simple equiprobable discrete distribution where $\tau$ could be any integer in range $[1,10]$, then $\mathop{\mathbb{E} }[\tau^2] = 38.5$ whilst $\mathop{\mathbb{E} }[\tau]\mathop{\mathbb{E} }[\tau] = 30.25$

The  pytorch implementation simply multiplied log probability and reward -log_prob * R and then summed the vector torch.cat(policy_loss).sum() there is no $p(\tau)$. What is really happening here?

The purpose of transforming the gradient into an expectation $\mathbb{E}$ for the policy gradient theorem, is so that you can estimate it using samples taken from the distribution. Typically, you don't know $p(\tau)$, but you do know that if you follow the same process where $p(\tau)$ applies (i.e. measure the return from the environment whilst following the policy represented by the policy function) that you will get an unbiased sample from that distribution.
So what is going on here is that you throw away the outer expectation $\mathbb{E}_{\pi}[]$ and replace it with a stochastic estimate for the same value based on taking samples. The samples are naturally obtained with distribution described by $p(\tau)$, if you follow the policy function when making action choices.

The second question is the multiplication of log probability and reward in pytorch implementation -log_prob * R, pytorch implementation has a negative log probability and derived equation has a positive one $\mathop{\mathbb{E}_\pi }[r(\tau )\bigtriangledown log \pi (\tau )]$. What is the need for multipling log probability with negative value in pytorch implementaion?

I don't know the code, but this very likely because of a sign change brought on by considering how to respond to the gradient estimate.
There is a clue in the use of the name "loss". To maximise return in policy gradient methods, you can perform gradient ascent based on the estimated gradient as the goal is to find higher values. However, it is more usual in NN libraries to perform gradient descent in order to minimise a loss function. That is a likely cause of the sign reversal here.

you throw away the outer expectation Eπ[]Eπ[] and replace it with a stochastic estimate for the same value based on taking samples. When I see  an expectation equation such as this $\mathop{\mathbb{E}}[f(x)]$ I always consider it as an "average" of that function. When replacing it with stochastic estimate  are we now calculating the "total" instead of the "average"?  Like we see in the code policy_loss = torch.cat(policy_loss).sum()

@eka: It will still be an average, but averaged over the samples you took instead of over a distribution function that you (probably) don't know. Although the code you show does indeed caclulate a total. If the batch size is always the same, this is just a scale difference though, and might be corrected for in later code, or in the learning rate etc.

I am really weak in the area of math and I really appreciate that you took your time to explain my queries. Thank you


text:
What happens when the output length in the brevity penalty is zero?
The brevity penalty is defined as
$$bp = e^{(1- r/c)},$$
where $r$ is the reference length and $c$ is the output length.
But what happens if the output length gets zero? Is there any standard way of coping with that issue?

Division by zero is not mathematically defined.
A usual or standard way of dealing with this issue is to raise an exception. For example, in Python, the exception ZeroDivisionError is raised at runtime if you happen to divide by zero.
If you execute the following program
zero = 0
numerator = 10
numerator / zero

You will get
Traceback (most recent call last):
  File "main.py", line 3, in <module>
    numerator / zero
ZeroDivisionError: division by zero

However, if you want to avoid this runtime exception, you can check for division by zero and deal with this issue in a way that is appropriate for your program (without needing to terminate it).
In the paper BLEU: a Method for Automatic Evaluation of Machine Translation that introduced the BLEU (and brevity penalty) metric, the authors defined the brevity penalty as
\begin{align}
BP =
\begin{cases}
1, & \text{if } c > r\\
e^{(1- r/c)} & \text{if } c \leq r\\
\end{cases} \label{1} \tag{1}
\end{align}
This definition does not explicitly take into account the division by zero.
The Python package nltk does not raise an exception, but it (apparently, arbitrarily) returns zero when c == 0. Note that the BLEU metric ranges from 0 to 1. For example, if you execute the following program
from nltk.translate.bleu_score import brevity_penalty, closest_ref_length

reference1 = list("hello") # A human reference translation.
references = [reference1] # You could have more than one human reference translation.

# references = [] Without a reference, you will get a ValueError.

candidate = list() # The machine translation.
c = len(candidate)

r =  closest_ref_length(references, c)
print("brevity_penalty =", brevity_penalty(r, c))

You will get
brevity_penalty = 0

In the example above, the only human reference (translation) is reference1 = list("hello") and the only candidate (the machine translation) is an empty list. However, if references = [] (you have no references), then you will get the error ValueError: min() arg is an empty sequence, where references are used to look for the closest reference (the closest human translation) to the  candidate (the machine translation), given that there could be more than one human reference translation, and one needs to be chosen to compute the brevity penalty, with respect to your given candidate.
In fact, in the documentation of the brevity_penalty function, the following comment is written
# If hypothesis is empty, brevity penalty = 0 should result in BLEU = 0.0.

where hypothesis is a synonym for candidate (the machine translation) and the length of the candidate is $c$ in the formula \ref{1} (and c in the example above).
To answer your second question more directly, I don't think there's a standard way of dealing with the issue, but I've not fully read the BLEU paper yet.


text:
Are deep learning models more prone to overfitting than machine learning ones?
In my opinion, deep learning algorithms and models (that is, multi-layer neural networks) are more sensitive to overfitting than machine learning algorithms and models (such as the SVM, random forest, perceptron, Markov models, etc.). They are capable of learning more complex patterns. At least that's how I look at it. Still, I and my colleagues disagree about this and I cannot really find any information about this. My colleagues say that deep learning algorithms are hardly vulnerable to overfitting.
Are there statements (or opinions) about this aspect?

I've not seen significant research done on this, as it is an unusual and specific thing to compare between these models. But at a glance, I would agree that a CNN for example would be much more prone to over-fitting than an SVM, especially without the significant effort put in to ensure it doesn't over fit (dropout, regularisation and so on).

Deep learning is a subset of machine learning.

It might be better to view this as a problem of data; traditional methods are simpler and, while they can overfit, the techniques used do not reuse the training data repeatedly. Deep learning, however, is capable of modeling much more complex relationships and tends to require a great deal more data; with insufficient data, we are forced to pass the same data through multiple training epochs which directly increases the likelihood of overfiiting.

Your reasoning isn't wrong. Deep Neural Networks (DNNs) have a much larger capacity than simpler ML algorithms (excluding NNs) and can easily memorize even a very complex dataset and overfit.
DNNs, however, are so effective because they usually are applied on tasks that are harder, so it's not as easy to overfit. For example an image classifier might be trained on a dataset with millions of images; a task much harder to overfit on.
In cases where this isn't possible (e.g. an image classification task with a couple thousand images), transfer learning is used. You can initialize your weights from a model pre-trained on a large dataset, use its already-trained feature extraction layers and simply fine tune the last layer.
Data augmentation also helps a lot here, which effectively increases size of the training set and discourages the DNN from memorizing the samples. It is so effective that it is used even in large datasets, where it is harder to overfit.
Additionally, DNNs employ several methods to prevent them from overfitting. The most prominent of these is dropout, which is a very effective regularizer. Batch Normalization has also proven an effective regularizer. SGD allows you to explore more parameters than GD, which also is effective against overfitting. Finally, early stopping and parameter norm penalties aren't uncommon in DNNs.


text:
What is the formula used to calculate the loss in the FaceNet model?
The FaceNet model returns the loss of the predictions and ground-truth classes. How is this loss calculated?

The loss function used is the triplet loss function.

Let me explain it part by part.
Notation
The $f^a_i$ means the anchor input image. The $f^p_i$ means the postive input image, which corresponds to the same people as the anchor image. The $f^n_i$ corresponds to the negative sample, which is a different person(input image) then the anchor image.
The formula explained step by step
The first part, $||f^a_i - f^p_i||^2_2$ basically calculates the distance between the anchor image output features and the postive image output features, which you want the distance to be as small as possible as the input is the same person. For the second part, $||f^a_i - f^n_i||^2_2$ , it calculates the distance of the output features of the anchor image and the negative image. You wnat the distance to be as large as possible as they are not the same person. Finally, the $\alpha$ term is a constant(hyperparameter) that adds to the loss to prevent negative loss.
How it works
The loss function optimizes for the largest distance between the anchor and negative sample and the smallest distance of the positive and anchor sample. It cleverly combines both metrics into one loss function. It can optimize for both case simultaneously in one loss function. If there is no negative sample, the model will not be able to differciate different person and vice versa.
Hope I can help you and have a nice day!

The question which i am linked ,what i want to ask is :Suppose i trained the images of two people say Bob , Thomas  .When i run the algorithm to detect the face of a totally different person from these two say John , then John is recognized as Bob or Thomas.How to avoid this ?

If you know how percentage is calculated , then can you explain it using an example (using image matrix) .You can explain this in this answer or in https://ai.stackexchange.com/questions/16175/three-step-threshold-in-facenet-model-of-face-recogniton or i can ask new question if you want


text:
Does a neural network exist that can learn every possible training data?
The universal approximation theorem states, that a feed-forward network with a single hidden layer containing a finite number of neurons can approximate continuous functions on compact subsets of $R^n$.
Michael Nielsen states

No matter what the function, there is guaranteed to be a neural network so that for every possible input, $x$, the value $f(x)$ (or some close approximation) is output from the network.

So, for continuous functions, this seems plausible. Interestingly, in the same article, Nielsen mentioned "any function".
Later, he writes

However, even if the function we'd really like to compute is discontinuous, it's often the case that a continuous approximation is good enough.

The last statement leaves open a gap, to ask how well an approximation practically can be.
Let's ignore contradictory input/output training pairs like $f(0)=0$ and $f(0)=1$, which actually don't event represent a function anyway.
Furthermore, assume that the training data is generated randomly, which would practically result in a discontinuous function.
How does a neural network learn such data? Will a learning algorithm always be able to find a neural network that approximates the function represented by the input-output pairs?

The branch of AI research that answers questions like this is called computational learning theory.
For the specific question you have asked, the universal approximation theorem does indeed prove that any function can be modeled by a sufficiently wide neural network. The definition of a function includes the requirement that each input be mapped to exactly one output, so contradictory labels in training data are excluded explicitly.
Here is a rough sketch that can provide an intuition behind why this is true. This is not a proper proof, but it gives you an idea of the power of "finite number of neurons" in a hidden layer:

A single neuron can essentially learn to draw a straight line across the space of input features. It outputs a value arbitrarily close to 1 for things on one side of the line, and arbitrarily close to 0 for things on the other side of the line.
For any given datapoint, it is possible to enclose the hyper-volume containing that datapoint, and no others by drawing a series of lines in the input space, and defining one side of each line as "inside" the hyper-volume, and the other side as "outside". In 2-d space, this corresponds to drawing the 4 sides of a square around a point.
An output neuron learns to draw lines across the outputs of the hidden layer neurons. It can therefore decide to output 1 only when, say, 4 other neurons are all simultaneously active.

It should seem natural then that a sufficiently wide neural network can memorize all of an input pattern. Since memorization is sufficient for "learning" to fit a pattern this should give you an intuition for the ability of neural networks to fit things.


text:
What is the difference between reinforcement learning and AutoML?
My vague understanding of reinforcement learning (RL) is that it's very similar to supervised learning except that it updates on a continuous feed of data/activity, this to me sounds very similar to AutoML (which I've started to notice being used).
Do they use different algorithms? What is the fundamental difference between RL and AutoML?
I'm after an explanation for somebody who understands technology but does not work with machine learning tools regularly.

Automated machine learning (AutoML) is an umbrella term that encompasses a collection of techniques (such as hyper-parameter optimization or automated feature engineering) to automate the design and application of machine learning algorithms and models.
Reinforcement learning (RL) is a sub-field of machine learning concerned with the task of making decisions and taking actions in an environment so as to maximize (long-term) reward (which is the goal of the so-called RL agent). RL is (at least partially) based on the way animals (including humans) learn. For example, the usual way of training a dog to perform a certain task is to reward it with food whenever it takes the correct action (for example, jumping, if you want the dog to jump whenever you make a certain gesture with your hand). In this case, the RL agent is the dog, the task the dog needs to perform (e.g. jumping) is the environment, food is the reward and the goal is to get food.
Given that reinforcement learning (RL) is a sub-field of machine learning, then, in principle, AutoML can also be used to automate the design of RL algorithms, models or agents. For example, if you use a neural network to represent the policy (the function the determines which action to take in the environment), then you can potentially use AutoML to find the most appropriate architecture (for example, the most appropriate number of layers) for this neural network.

RL can be used in the context of Neural Architecture Search (NAS), with is a form of automated ML. A model searches for an architecture that performs a given task. How well this task is performed guides how the architecture will be modified (improved) on the next pass. It works but is very computation-intensive (think hundreds of GPUs).
See for instance:

B. Zoph and Q. V. Le (2016), arxiv: 1611.01578.
B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le (2017), arxiv: 1707.07012.
M. Tan, B. Chen, R. Pang, V. Vasudevan, and Q. V. Le (2018), arxiv: 1807.11626.


text:
What kind of data structures are needed to efficiently do back-propagation in a feedforward neural network?
In a feed-forward neural network, in order to efficiently do backpropagation, what kind of data structure is needed?
I know the weights can just be stored in an array, and you need pointers of some kind to represent connections from one layer to the next (or just a default scheme/pattern), but is anything else needed for backpropagation to work?

TL;DR: You'll need to store a little bit more to perform backward passes. You'll need to store data from the forward pass. This stored information is used for calculating the gradient.
Overview (warning: not trivial)

I know the weights can just be stored in an array

You'll need a little more:
To update the weights you need to keep a "cache" of the forward pass intermediate terms. That is, forward propagation can be seen as a series of transformations on your input $X$:
$$X\xrightarrow{\Theta^{[1]}+b^{[1]}} [ Z^{[1]} \xrightarrow{\alpha^{[1]}} A^{[1]}] \xrightarrow{\Theta^{[2]}+b^{[2]}}
\dots
\xrightarrow{\Theta^{[L]}+b^{[L]}} [ Z^{[L]} \xrightarrow{\alpha^{[L]}} A^{[L]}]\xrightarrow{\frac{1}{m}\sum\limits_m\sum\limits_{n_L} loss\{A^{[L]},y\}} J
$$
where:
$Z^{[1]}=\Theta^{[1]}X+b^{[1]}$ (ie the linear part)
$A^{[l]}=\alpha^{[l]}(Z^{[l]})$ (ie element wise activation over linear part)
You need to store the $Z^{[l]}$ & $A^{[l]}$ terms in said "cache." You could store these in an array or some other similar data structure. You need these for calculating the gradient during the backwards pass.
Syntax
$A^{[k]}$ - this means we are indexing by layer (eg $\alpha^{[k]}$ is the activation for k-th layer)
$m$ - is the number of examples in the batch
$n_k$ - denotes the number of neurons in the k-th layer
$L$ - the number of layers (so $n_L$ is the number of neurons in last layer)
$\Theta$ - The set of all weights (notice no superscript)
Backprop
In the case of neural networks the cost is a scalar function of inputs and parameters. To get backprop started calculate the scalar by matrix derivative of the cost with respect to the activations of the last layer call this matrix $dA^{[L]}$. Observe:
$dA^{[L]} = \frac{\partial J(\Theta,X)}{\partial A^{[L]}}$
Next, we calculate scalar-by-matrix derivative of $Z^{[L]}$. Doing this one realizes:
$dZ^{[L]} = \frac{\partial J(\Theta,X)}{\partial Z^{[L]}} = dA\odot\alpha'^{[L]}(Z^{[L]})$
Where $\odot$ denotes element wise (Hadamard) product.
With the above one can make use of the matrix definitions for back propagation:
$\text{(A)}\quad d\Theta^{[l]} = \frac{1}{m}dZ^{[l]}\times (A^{[l-1]})^T$
$\text{(B)}\quad db^{[l]} = \frac{1}{m}\sum_{c=1}^m dZ^{[l](c)}$ (where the new superscript in $dZ^{[l](c)}$ denotes summing along the batch dimension )
$\text{(C)} \quad dZ^{[l]}= dA^{[l]}\odot \alpha^{'[l]}(Z^{[l]})$
$\text{(D)}\quad dA^{[k]} = (\Theta^{[k+1]})^T\times dZ^{[k+1]}$
And of course the wight updates are:
$\Theta^{[L]} \leftarrow \Theta^{[L]} - \frac{\eta}{m}d\Theta $
$b^{[L]} \leftarrow b^{[L]} - \frac{\eta}{m}db $
(where $\eta$ is the learning rate)
Observe, how the forward pass terms are used during the backprop calculations.
A recommendation
Take the A. Ng deep learning specialization. He does a good job explaining the intuition and even has a project to implement this. Though, he does not derive the back propagation equations. You can find a not so easy derivation here.

During the backward pass can we "free" some cache? I mean when we calculate the gradient of loss $L$ with respect to layer $\ell_n$, i.e. $\frac{dL}{d\ell_{n}}$, we only need $\frac{dL}{d_{\ell-1}} \cdot \frac{d\ell_{n-1}}{d\ell_{n}}$. So can we remove from cache all terms above $\ell_{n-1}$?

@adosar You could: (1) free it as you do the backward pass (2) free it all at the end of the backward pass (3) Use a mutable data-structure and replace the data during the next pass. Depends on you preferences/needs/constraints.

When I check the Tensorflow tool code, it looks like they implemented own data structure for neural network operation including back propagation. The custom data structure is EagerTensor.
I think to speed up the operation speed, the Tensorflow used the TFRECORD file type/format.
Additionally, for neural network structure (they called Graph), they used the Protocol Buffer format.


text:
How to calculate the precision and recall given the predictions and targets in this case?
I'm using three pre-trained deep learning models to detect vehicles and count from an image data set. The vehicles belong to one of these classes ['car', 'truck', 'motorcycle', 'bus']. So, for a sample I have manually counted number of vehicles in each image. Also, I employed the three deep learning models and obtained the vehicle counts. For example:
    Actual        | model 1 count| model 2 count  | model 3 count
------------------------------------------------------------------
    4 cars, 1 bus | 2 cars       | 2 cars, 1 truck| 4 cars
    2 cars        | 0            | 1 truck        | 1 car, 1 bus

In this case, how can I measure accuracy scores such as precision and recall?

Precision is the number of true positives over the number of predicted positives(PP), and recall is the number of true positives(TP) over the number of actual positives(AP) you get. I used the initials just to make it easier ahead.
A true positive is when you predict a car in a place and there is a car in that place.
A predicted positive is every car you predict, being right or wrong does not matter.
A actual positive is every car that actually is in the picture.
You should calculate these values separately for each category, and then sum over the examples you sampled, if I am not mistaken.
So for the CAR category you have (assuming the predictions do match with the target, i.e., you are not predicting a truck as a car for example) :
model 1
line 1  -> 2 TP, 2 PP, 4 AP
line 2  -> 0 TP, 0 PP, 2 AP

So in total precision  is 2/2 = 1 and recall is 2/6 = 0.3(3).
You can then do the same for the other categories, and for the other models. This way you can check if a model is predicting one category better than the other. For example, model 1 can be better at finding cars in a picture whilst model 3 can be better at finding buses.
The important part is that you know if the objects the model predicted actually correspond to what is in the picture. A very unlikely example would be a picture with 1 car and 1 truck where the algorithm recognizes the car as a truck and the truck as a car. From the info that is in the table I cannot be sure if the 2 cars you predict are the actual cars in the picture, or in other words, if they are actually True Positives or are actually False Positives.

Thanks a lot for your answer!. Yes, it is more complex than I thought. For example, there is one model which draws two bounding boxes over one car. However, your answer is so helpful!

@NilaniAlgiriyage that would make one box with higher IoU with ground truth the true positive and the other box false positive. You'd want your model to give better confidence to this TP box


text:
How is the loss value calculated in order to compute the gradient?
The gradient descent step is the following
\begin{align}
\mathbf{W}_i = \mathbf{W}_{i-1} - \alpha * \nabla L(\mathbf{W}_{i-1})
\end{align}
were $L(\mathbf{W}_{i-1})$ is the loss value, $\alpha$ the learning rate and $\nabla L(\mathbf{W}_{i-1})$ the gradient of the loss.
So, how do we get to the $L(\mathbf{W}_{i-1})$ to calculate the gradient of $L(\mathbf{W}_{i-1})$? As an example, we can initialize the set of $\mathbf{W}$ to 0.5. How can you explain it to me?

Are you asking how to calculate the gradient of $f$ or how to calculate the loss value itself?

Wow, Thanks for your edition. Before I can to calculate the gradient of f(W), I should have the f function. So, how can I have the f function at the first?

In your case, $L$ is the loss (or cost) function, which can be, for example, the mean squared error (MSE) or the cross-entropy, depending on the problem you want to solve. Given one training example $(\mathbf{x}_i, y_i) \in D$, where $\mathbf{x}_i \in \mathbb{R}^d$ is the input (for example, an image) and $y_i \in \mathbb{R}$ can either be a label (aka class) or a numerical value, and $D$ is your training dataset, then the MSE is defined as follows
$$L(\mathbf{W}) = \frac{1}{2} \left(f(\mathbf{x}_i) - y_i \right)^2,$$
where $f(\mathbf{x}_i) \in \mathbb{R}$ is the output of the neural network $f$ given the input $\mathbf{x}_i$.
If you have a mini-batch of $M$ training examples $\{(\mathbf{x}_i, y_i) \}_{i=1}^M$, then the loss will be an average of the MSE for each training example. For more info, have a look at this answer https://ai.stackexchange.com/a/11675/2444. The https://ai.stackexchange.com/a/8985/2444 may also be useful.
See the article Loss and Loss Functions for Training Deep Learning Neural Networks for more info regarding different losses used in deep learning and how to choose the appropriate loss for your problem.

Is that true to say : L(w) = 1/2 * (f(x,w) - y)**2 ?

I did not get my answer completely however, your answer was very helpful.
You said in this answer: (
https://ai.stackexchange.com/questions/11667/is-back-propagation-applied-for-each-data-point-or-for-a-batch-of-data-points/11675#11675 )
"For simplicity, assume that we are able to calculate the gradient of L, that is, delat(L)". So, how can I calculate the gradient of L function according to W set, because I need to update my W set. I mean that, do we have such a function like f(x) = 2x and then calculate the L(w)=1/2*(2x-y)*2 and delta(L) = 2(2x-y)?

$f(x, w)$ or $f(x)$ are "just" notations, in the sense that $w$ is clearly a parameter (or weight) of the neural network $x$, but $w$ is not an input to the neural network: $x$ is the input! The way you calculate the gradient of $L$ with respect to any of the parameters is with back-propagation and it depends on the architecture of the neural network and the loss function you choose. To understand back-propagation, you need to understand the basics of calculus.

Thanks and I got the point :
https://towardsdatascience.com/linear-regression-using-gradient-descent-97a6c8700931


text:
How does the forget layer of an LSTM work?
Can someone explain the mathematical intuition behind the forget layer of an LSTM?
So as far as I understand it, the cell state is essentially long term memory embedding (correct me if I'm wrong), but I'm also assuming it's a matrix. Then the forget vector is calculated by concatenating the previous hidden state and the current input and adding the bias to it, then putting that through a sigmoid function that outputs a vector then that gets multiplied by the cell state matrix.
How does a concatenation of the hidden state of the previous input and the current input with the bias help with what to forget?
Why is the previous hidden state, current input and the bias put into a sigmoid function? Is there some special characteristic of a sigmoid that creates a vector of important embeddings?
I'd really like to understand the theory behind calculating the cell states and hidden states. Most people just tell me to treat it like a black box, but I think that, in order to have a successful application of LSTMs to a problem, I need to know what's going on under the hood. If anyone has any resources that are good for learning the theory behind why cell state and hidden state calculation extract key features in short and long term memory I'd love to read it.

TL;DR Here is a beautiful explanation with diagrams: source.
To address:

the cell state is essentially long term memory embedding (correct me if I'm wrong)

The embedding can be long or short term and it is a vector.
To answer:

Why is the previous hidden state, current input and the bias put into a sigmoid function? Is there some special characteristic of a sigmoid that creates a vector of important embeddings?

Excerpt from source:

The sigmoid layer outputs numbers between zero and one, describing how much of each component should be let through. A value of zero means “let nothing through,” while a value of one means “let everything through!”

Formally the forget vector is:
$$f_t = \sigma(W_f\cdot[h_{t-1},x_t],+b_f)$$
So we see that it is actually a linear operation followed by a non-linear operation, which restricts the values to be between 0 and 1. This is followed by an element-wise operation on the previous cell state. That is we "gate"/"filter" the previous cell state doing:
$$C_{t-1}\odot f_t,$$
where $\odot$ is element-wise multiplication.
Thus we see that the forget gate really is acting like a gate: It either lets values pass through or it pushes them toward zero. So, it's purpose is to assign what values to forget/remember.
To answer:

How does a concatenation of the hidden state of the previous input and the current input with the bias help with what to forget?

This concatenation takes into account the "rolling" hidden state and the current input. That is, the linear operation results in a new vector which can be seen as a "consideration embedding" of the current input and a "summary" of past inputs and cell states. The sigmoid then converts this "consideration embedding" into the forget vector.
In summary, the forget gate has the primary purpose of forming a vector of values between zero and one. This vector results by considering the current input and the previous hidden state. The vector is used to forget/remember parts of the previous cell state via element-wise multiplication. So, no, it is not a black box, it is a highly considerate non-linear operation through time.
Additional Intuition - More Mathematical
Recall that multiplying a matrix on the right by a column vector produces a vector, which is a linear combination of the columns of the matrix. So each column of $W_f$ can be seen as a column of "toggles" that push up to 1 or pull down to 0 (once we apply sigmoid). That is, the columns of $W_f$ form a sort of "basis" for a "toggle space."
When we concatenate to form $[h_{t-1},x_t]$ and then multiply we see that the term $W_f\cdot[h_{t-1},x_t]$ gives consideration to the hidden state and the input. That is, both $h_{t-1}$ and $x_t$ have there hand in toggling the gate.
The LSTM has learned from the data how to make this toggling "meaningful." Below is a simple pictographic example.

That is, $W_f\cdot[h_{t-1},x_t]$ will be a vector in the column space of $W_f$ (ie the "toggle space"). Thus, the concatenated vector will "point" to the best "toggle" in the column ("toggle") space of $W_f$. This "toggle" is then transformed into a "gate" in the "gate space."
So intuitively, the range of the forget component is a sort of "gate space" where the domain is all vectors of form $[h_{t-1},x_t]$. Formally:
$$f_t:[h_{t-1},x_t]\mapsto g_t$$
That is to say that the forget gate learns the best mapping from the domain of concatenated hidden/input's to the range of possible gates.
Important Note
The LSTM is only one of many types of forget-gate mappings. The main takeaway is that the LSTM works empirically for many applications.
That is a forget gate is an instance of a general "gate mapping":
$$f_t:v_t \mapsto g_t,$$
where $v_t$ could be any number of vectors resulting from any number of concatenations.
Conclusion
Some data from the past is irrelevant to the current time step. We need a way to correctly "forget" irrelevant information. One way to "forget" is to use a forget gate mapping (like the one in LSTMs). Then we need to optimize the parameters of that forget gate. One implementation is used in the common LSTM architecture. Finally, the concatenation of the previous hidden state provides contextual information to the current input which is very helpful with forgetting.
More Mathematical Intuition
Here is another view of what is happening in the LSTM from a dynamic point of view: video.

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


text:
How does the decision tree implicitly do feature selection?
I was talking with an ex-fellow worker and he told me that the decision tree implicitly applies a feature selection. He told me that the most important feature is higher in the tree because of the usage of information gain criteria.
What does he mean with this and how does this work?

Hi Jennifer! Do you know how a decision tree is created? Have you ever looked at the details of a decision tree learning algorithm?

@nbro Yes, I think this is due to usage of the information gain criteria is that correct?

@jenniferruurs There are different ways of creating decision trees. IG is one metric that can be used to guide the creation of the decision tree (how to split the dataset). There are other metrics, such as Gini impurity or variance reduction.

@nbro thank you, so Gini impurity and variance reduction are implicitly also feature selection criteria?

Consider a dataset $S \in \mathbb{R}^{N \times (M + 1)}$ with $N$ observations (or examples), where each observation $S_i \in \mathbb{R}^{M + 1}$ is composed of $M$ elements, one value for each of the $M$ features (or independent variables), $f_1, \dots f_M$, and the corresponding target value $t_i$.
A decision tree algorithm (DTA), such as the ID3 algorithm, constructs a tree, such that each internal node of this tree corresponds to one of the $M$ features, each edge corresponds to one value (or range of values) that such a feature can take on and each leaf node corresponds to a target. There are different ways of building this tree, based on different metrics to choose the features for each internal node and based on whether the problem is classification or regression (so based on whether the targets are classes or numeric values).
For example, let's assume that the features and the target are binary, so each $f_k$ can take on only one of two possible values, $f_{k} \in \{0, 1\}, \forall k$, and $t_i \in \{0, 1\}$ (where the index $i$ correspond to the $i$th observation, while the index $k$ correspond to the $k$th column or feature of $S$). In this case, a DTA first chooses (based on some metric, for example, the information gain) one of the $M$ features, for example, $f_j$, to associate it with the root node of the tree. Let's call this root node $f_j$. Then $f_j$ will have two branches, one for each of the binary values of $f_j$. If $f_j$ were a ternary variable, then the node corresponding to $f_j$ would have three branches, and so on. The DTA recursively chooses one of the remaining features for each node of the child branches. The DTA does this until all features have already been selected. In that case, we will have reached a leaf node, which will correspond to one value of the target variable. When the DTA chooses a feature for a node, all observations of the dataset $S$ that take on the first binary value of that feature will go in the branch corresponding to that value and all other observations will go in the other branch. So, in this way, the DTA splits the dataset based on the features.
The following diagram represents a final decision tree built by a DTA.

You can see that the first feature selected (for the root node) by the DTA is "Is it male?", which is a binary variable. If yes, then, on the left branch, we have another internal node, which corresponds to another feature and, at the same time, to all observations associated with a male. However, on the right branch, we have a leaf node, which corresponds to one value of the target, which, in this case, is a probability (or, equivalently, a numerical value in the range $[0, 1]$). The shape of the tree depends on the dataset and DTA algorithm. Therefore, different datasets and algorithms might result in different decision trees.
So, yes, you can view a decision tree algorithm as a feature selection or, more precisely, feature splitting algorithm.

You are very good at explaining things, i have read a lot of literature but could not find a explanation that was this clear!

@jenniferruurs I'm glad I helped you, but note that I've simplified a little bit the explanation (but, at the same time, I've tried to introduce a rigorous notation to clarify the concepts). It's been a while I've not worked with decision trees. However, if you want to go into the details, you should read about the specific algorithms, like ID3 algorithm.


text:
How can I convert the probability score between 0 to 1 to another format?
I have trained a multi-class CNN model using fastai. The model splits out probabilites for each of the three classes, which, of course, sum up to 1. The class with highest probability becomes the predicted class.
Is there any way I can convert them into 0 to 1 scale, where near to 0 value would mean class 1, near to 0.5 would mean class 2 and near to 1 would mean class 3?

You could maybe do something like this, it's a bit hackish
\begin{equation}
y = C_1\cdot 1 + C_2 \cdot 0.5 + C_3 \cdot 0
\end{equation}
$y$ represents the output and its bounded $\in [0, 1]$. $C_i$ is probability for class $i$. This way when $C_1 \approx 1, C_2 \approx 0, C_3 \approx 0$ you have
\begin{equation}
 y \approx 1\cdot 1 + 0.5 \cdot 0 + 0 \cdot 0 \approx 1
\end{equation}
when $C_1 \approx 0, C_2 \approx 1, C_3 \approx 0 $ you have
\begin{equation}
 y \approx 1\cdot 0 + 0.5 \cdot 1 + 0 \cdot 0 \approx 0.5
\end{equation}
and when $C_1 \approx 0, C_2 \approx 0, C_3 \approx 1 $ you have
\begin{equation}
 y \approx 1\cdot 0 + 0.5 \cdot 0 + 0 \cdot 1 \approx 0
\end{equation}

Thats what I thought to do and it would work in best scenario. If C1 = 0.5 and C3 = 0.5, then the y would be 0.5, which would be incorrect. Sorry, if I wasnt clear in the begining, the predicted probalitites for each class can be between 0 to 1, not just binary.

Right, the assumption is that model is well trained. If you have a model that gives you 50%-50% you might want to train a better model.

@user1631306: What is the correct result for you if "If C1 = 0.5 and C3 = 0.5"? You say that a value of 0.5 would be incorrect. So what would you want the output to be, and why?

Alternatively, you could replace softmax with sigmoid and change labels for classes to 0, 0.5, 1. That's the only other solution I can think of because I'm not sure if there is practical way to make bijection  from $R^3 \rightarrow R$ without doing some more abstract mathematical constructions.

@Brale_: I should be ready for the worse scenario. Model usually predicts with high probability. But these are cell assay images and they are bound to have nearly equal probabilites in two or more classes.

@NeilSlater I dont know either. but on second thought, that shouldnt even happen. It should be a tie between two adjacent classes not on extreme, in my model. The classes are progressive. So, either it there would be tie between C1 and C2 or C2 and C3.

@user1631306: Your objection to this answer does not stand then, and it should work for you. Or you need to state a clearer goal for some example cases that show what you want

@NeilSlater I agree with you

In such cases, you can have just 1 final neuron and treat the problem as a regression problem where the output distance from all 3 classes is calculated and the class with least distance becomes the predicted class.
If you want independent values for 3 classes (such as [0.8, 0.5, 0.3]) which don't add up to 1, (something like multilabel/multiclass classification), you can use sigmoid in such cases( you won't get the probability ).

I am not worried about predicted class, thats been taken care of. I was wondering if somehow I could normalize the probablity score. Seems like I might be on wrong track and I am not asking the question correctly.


text:
What is the difference between linear and non-linear regression?
In machine learning, I understand that linear regression assumes that parameters or weights in equation should be linear. For Example:
$$y = w_1x_1 + w_2x_2$$
is a linear equation where $x_1$ and $x_2$ are feature variables and $w_1$ and $w_2$ are parameters.
Also
$$y = w_1(x_1)^2 + w_2(x_2)^2$$
is also linear as parameters $w_1$ and $w_2$ are linear with respect to $y$.
Now, I read some articles stating that in the equation like
$$y = \log(w_1)x_1 + \log(w_2)x_2$$
can also be made linear by considering other variables $v_1$ and $v_2$ as:
\begin{align}
v_1 &= \log(w_1)\\
v_2 &= \log(w_2)
\end{align}
Thus,
$$y = v_1x_1 + v_2x_2$$
So, in this sense, any non-linear equation can be made linear, then what is non-linear regression here? I think I am missing something important here. I am a beginner in the field of Machine Learning. Can somebody help me?

non-linear regression is that dependent variable values does not depend on the linear combination. We can perform some transformations, like log or any transformation and make them linear. Though not every non linear relationship can be transformed into linear. Also even if we are able to do that.. that might be a complex transformation.

The difference is simply that non-linear regression learns parameters that in some way control the non-linearity - e.g. any weight or bias that is applied before a non-linear function.
For instance:
$$y = (w_1 x_1 + w_2 x_2)^2 + w_3$$
With such a function to learn, you cannot separate out transformed values of $w_1$ and $w_2$ and turn this into a linear function of just $x_1$ and $x_2$.
What you are describing as non-linearities in your examples are instead all applied by the machine learning engineer to create new candidate features for linear regression. This is not usually described as non-linear regression, but feature transformation or feature engineering.
There is also a kind of middle ground where a central linear algorithm e.g. linear regression, is trained on many variations of the original features, by automated generation and filtering of transformed features. The most general variants of this approach are not hugely popular because they suffer from same risks of overfitting as non-linear models whilst not offering much in the way of improved performance. However, if you narrow down the types of feature and transformation combinations based on some knowledge of how you expect the target function to behave, it leads to many useful variants of linear regression - e.g. regression on fourier transforms, radial basis functions etc.


text:
Could you share with me the tree size, search time and search depth of your implementation of Gomoku with minimax and alpha-beta prunning?
Currently, I am working on a Gomoku AI implementation with minimax + alpha-beta pruning.
I'm targeting these two rules from 'acceptable implementation' in terms of search time and search depth :

Search time (over 0.5 seconds is "bad", less 0.5 seconds is ok)
Search depth (less than 10 search depth levels is "bad", over 10 search depth levels is ok)

The minimax algorithm generates, by recursive function calls, a tree of nodes, each node represented by a function call with a specific game state.
Increasing the depth search increases the number of nodes in the tree, and therefore search time.
There is a compromise between search time and search depth.
Alpha-beta pruning tends to help this compromise by pruning useless nodes search and reducing tree size. The pruning is directly related to the evaluation/heuristic function. Bad implementation of heuristic may lead to bad efficiency of alpha-beta pruning.

If you are working on or have done a Gomoku AI, sharing your stats of tree size, search depth and time search from your implementation at some game steps, and explain how you reach it may help to investigate.

The implementation at this time does not fit the 'is not acceptable' for me, having search time over 1sec for a search depth of 4 at first step ... on IntelCore i7 3.60GHz CPU ...
Here are the properties of the actual implementation:

Board of size 19x19
Implements search window of size 5x5 around stones to reduce search nodes
Implements heuristic computation at each node on the played stone instead of computation on all board size on leaf nodes number.
Implements alpha-beta pruning
No multi thread

Here are the current stats it is reaching for search depth of 4 at the first step:

Timing minimax algorithm: 1.706175 seconds
Number of nodes in that compose the tree: 2850

. . . . . . . . . . . . . . . . . . . 00
. . . . . . . . . . . . . . . . . . . 01
. . . . . . . . . . . . . . . . . . . 02
. . . . . . . . . . . . . . . . . . . 03
. . . . . . . . . . . . . . . . . . . 04
. . . . . . . . . . . . . . . . . . . 05
. . . . . . . . . . . . . . . . . . . 06
. . . . . . . . . . . . . . . . . . . 07
. . . . . . . . . . . . . . . . . . . 08
. . . . . . . . . . . . . . . . . . . 09
. . . . . . . . . . . . . . . . . . . 10
. . . . . . . . . . . . . . . . . . . 11
. . . . . . . . . . . . . . . . . . . 12
. . . . . . . . . . . . . . . . . . . 13
. . . . . . . . . . . . . . . . . . . 14
o x . . . . . . . . . . . . . . . . . 15
. . . . . . . . . . . . . . . . . . . 16
. . . . . . . . . . . . . . . . . . . 17
. . . . . . . . . . . . . . . . . . . 18
A B C D E F G H I J K L M N O P Q R S
Player: o - AI: x

Bad stats might be lead to bad heuristics, causing inefficient pruning. Waiting for other stats/replies to validate this hypothesis may help.
Edit 1
Coming back from a new search campaign on this question.

The implementation was facing a 19*19 loop index at each heuristic computation ... Removed this by heuristic computation at a specific index (not the entire board)

The implementation was facing a 19*19 loop index to check win state ... Removed this by checking only around played index any alignment at each step.

The implementation was facing a 19*19 loop index to check where it can play (even with the windows) ...
Removed by propagating indexes array of valid indexes through the recursion updated at each step.
The array is a dichotomic array (with $O(n)$ insertion, $O(\log n)$ search and $O(1)$ deletion by index)

The implementation was lacking a Zobrist hash table, a very nice idea from the below answer. It is now implemented with unit tests to prove that implementation is working. An array sorted by hash is updated at each new node, with the hash-node association. The array is a dichotomic array (with $O(n)$ insertion, $O(\log n)$ search and $O(1)$ deletion by index)

The implementation is at each step trying each index in a random way (not computation order or evaluation score order).

The before edit example is not great because it is playing on a sideboard and the allowed indexes window is half max size.
Here are the newly obtained performances :

with Zobrist table off and seed at 42 for search depth of 4 at the first step

Timing minimax algorithm: 0.083288 seconds
Number of nodes that compose the tree: 6078

. . . . . . . . . . . . . . . . . . . 00
. . . . . . . . . . . . . . . . . . . 01
. . . . . . . . . . . . . . . . . . . 02
. . . . . . . . . . . . . . . . . . . 03
. . . . . . . . . . . . . . . . . . . 04
. . . . . . . . . . . . . . . . . . . 05
. . . . . . . . . . . . . . . . . . . 06
. . . . . . . . . . . . . . . . . . . 07
. . . . . . . . . . . . . . . . . . . 08
. . . . . . . . . . . . . . . . . . . 09
. . . . . . . . . . . . . . . . . . . 10
. . . . . . . . . x . . . . . . . . . 11
. . . . . . . . o . . . . . . . . . . 12
. . . . . . . . . . . . . . . . . . . 13
. . . . . . . . . . . . . . . . . . . 14
. . . . . . . . . . . . . . . . . . . 15
. . . . . . . . . . . . . . . . . . . 16
. . . . . . . . . . . . . . . . . . . 17
. . . . . . . . . . . . . . . . . . . 18
A B C D E F G H I J K L M N O P Q R S
Player: o - AI: x

with Zobrist table on and seed at 42 for search depth of 4 at the first step

Timing minmax_algorithm: 0.434098 seconds
Number of nodes that compose the tree: 9320

. . . . . . . . . . . . . . . . . . . 00
. . . . . . . . . . . . . . . . . . . 01
. . . . . . . . . . . . . . . . . . . 02
. . . . . . . . . . . . . . . . . . . 03
. . . . . . . . . . . . . . . . . . . 04
. . . . . . . . . . . . . . . . . . . 05
. . . . . . . . . . . . . . . . . . . 06
. . . . . . . . . . . . . . . . . . . 07
. . . . . . . . . . . . . . . . . . . 08
. . . . . . . . . . . . . . . . . . . 09
. . . . . . x . . . . . . . . . . . . 10
. . . . . . . . . . . . . . . . . . . 11
. . . . . . . . o . . . . . . . . . . 12
. . . . . . . . . . . . . . . . . . . 13
. . . . . . . . . . . . . . . . . . . 14
. . . . . . . . . . . . . . . . . . . 15
. . . . . . . . . . . . . . . . . . . 16
. . . . . . . . . . . . . . . . . . . 17
. . . . . . . . . . . . . . . . . . . 18
A B C D E F G H I J K L M N O P Q R S
Player: o - AI: x

Actually, it is ok for search depth 4, but not for more than 6. The node number is becoming exponential (over 20 000) ...
Found here great implementation in the same language/techno than can go to 10 depth in less than 1sec, without Zobrist or smart trick, and followed the logic.
The issue must be somewhere else, causing exponential growth of node - inefficient pruning.

Intuitively I kind of doubt expecting a search depth of 10 in half a second is reasonable, especially for the initial game state where there's a rather large branching factor and no immediately-winning moves that help to prune some branches quickly.
I've never implemented any Alpha-Beta agents for Gomoku specifically, but I can provide some numbers for our Alpha-Beta implementation in the Ludii General Game System. Note that this is a general game system that implements a wide variety of games in a single game description language. Due to its generality, it's unlikely that any single game runs as efficiently as it would in a highly-optimised game-specific implementation. Therefore, you should consider these numbers to be lower bounds on what you can achieve in a Gomoku-only game-specific implementation.

We can reach a search depth of 3 for the initial game state in half a second.
Increasing this to 10 seconds is still not enough for a depth of 4. I don't know how much I'd have to increase it to reach a depth of 4.
At a max search time of 1 second, it actually seems to play quite well against a few different MCTS-based baselines. So I'm not sure if you really need a depth of 10 before you consider it "acceptable".
I'm not keeping track of the number of visited nodes, so can't provide those.

Note that it's very important to take into account the computational cost of your heuristic evaluation function. We're using a somewhat expensive heuristic which computes all potential lines of a length of 5 (because this is appears in the end rules in Gomoku) through all pieces that have been placed so far, as described on pages 82-84 of Automatic generation and evaluation of recombination games (but with a simpler scoring rule than the union of probabilities as described there).

CPU:
- Intel Core i5-6500 CPU @ 3.20GHz
Game implementation details:

General game system (so not optimised for this specific game).
I updated the board size to 19x19 to match your test, but as far as I'm aware 15x15 is more common (and the default in Ludii).
Implemented in Java

Alpha-Beta implementation details:

Iterative deepening (so when I write that we reach depth 3, I mean that we completed searches of depth 1, followed by 2, followed by 3, and were probably in progress with a depth-4 search when we ran out of time).
Ludii does not provide undo operations for moves, only apply operations. This means we have to create lots of copies of states, because we cannot undo moves after exiting out of a recursive call.
No negamax (because we also want to support games in which players may have multiple moves in a row before control switches over to another player)
No transposition tables yet (we do already compute the Zobrist hashes, just didn't get around to implementing the TT yet).
No move ordering (other than in between the iterations of iterative deepening).
No smaller search windows than just the regular alpha-beta windows.
Also built-in support to handle games with more than 2 players (with Paranoid search), which probably adds a little bit of overhead to the algorithm.
No smart tricks like the ones you mentioned about only looking at windows around placed stones; we need to support general games.

Back from focusing on your great great post and especially Ludii document, the part you mentioned. This portion is totally targeting the problematic the current implementation i have is facing on (search depth / search time). I did not already investigate enough time to look the wide of Ludii and the these. Just commenting back fast here to tell you that your work is currently showing lot of interest and i'm taking time to focus on. I'll probably go back to you here in few times to keep you informed ! Thanks again