How do I convert an MDP with the reward function in the form $R(s,a,s')$ to and an MDP with a reward function in the form $R(s,a)$? The AIMA book has an exercise about showing that an MDP with rewards of the form $r(s, a, s')$ can be converted to an MDP with rewards $r(s, a)$, and to an MDP with rewards $r(s)$ with equivalent optimal policies.
In the case of converting to $r(s)$ I see the need to include a post-state, as the author's solution suggests. However, my immediate approach to transform from $r(s,a,s')$ to $r(s,a)$ was to simply take the expectation of $r(s,a,s')$ with respect to s' (*). That is:
$$ r(s,a) = \sum_{s'} r(s,a,s') \cdot p(s'|s,a) $$
The authors however suggest a pre-state transformation, similar to the post-state one. I believe that the expectation-based method is much more elegant and shows a different kind of reasoning that complements the introduction of artificial states. However, another resource I found also talks about pre-states.
Is there any flaw in my reasoning that prevents taking the expectation of the reward and allow a much simpler transformation? I would be inclined to say no since the accepted answer here seems to support this. This answer mentions Sutton and Barto's book, by the way, which also seems to be fine with taking the expectation of $r(s, a, s')$.
This is the kind of existential question that bugs me from time to time and I wanted to get some confirmation.
(*) Of course, that doesn't work in the $r(s, a)$ to $r(s)$ case, as we do not have a probability distribution over the actions (that would be a policy, in fact, and that's what we are after).

I think I may be in position to answer my own question. The Bellman equation (for the optimal policy) for a MDP with $r(s,a,s')$ rewards would look like this:

$$V(s) = \max_a \left\{ \sum_{s'} p(s'|s,a)(r(s,a,s') + \gamma V(s')) \right\} $$
$$V(s) = \max_a \left\{ \sum_{s'} p(s'|s,a) \cdot r(s,a,s') + \gamma \sum_{s'} p(s'|a,s) \cdot V(s') \right\} $$

Now, $ \sum_{s'} p(s'|s,a) \cdot r(s,a,s') $ is precisely $ \mathbb{E}\left[ r(s,a,s') | s,a \right] = r(s,a) $.

So all in all, the resulting Bellman equation looks like this:

$$V(s) = \max_a \left\{r(s,a) + \gamma \sum_{s'} p(s'|s,a) \cdot V(s') \right\} $$

It is clear, then, that a process with $ r(s,a,s') $ rewards can be transformed to a $ r(s,a) $ process without introducing artificial states and maintaining the optimal policies.

As a side note unrelated to the question itself, that leads me to believe that $ r(s,a,s') $ functions may be convenient in some scenarios, but they do not add "expressive power", in the sense that they do not allow to model problems more compactly (as it happens when we extend $ r(s) $ to $ r(s,a) $).


Are hill climbing variations always optimal and complete? Are hill climbing variations (like steepest ascent hill climbing, stochastic hill climbing, random restart hill climbing, local beam search) always optimal and complete?

No, they are prone to get stuck in local maxima, unless the whole search space is investigated.
A simple algorithm will only ever move upwards; if you imagine you're in a mountain range, this will not get you very far, as you will need to go down before going up higher. You can see that going down a bit will have a net benefit, but the search algorithm will not be able to see that.
Random restart (and similar variations) allow you to do that, up to a point. Imagine you have ten people that you parachute over your mountain range, but they can only go upwards. Now you've got a better chance of finding a higher peak, but there's still no guarantee that any of them will reach the highest one.


Training accuracy vs validation accuracy on deep models I'm training a deep network in Keras on some images for a binary classification (I have around 12K images). Once in a while, I collect some false positives and add them to my training sets and re-train for higher accuracy.

I split my training into 20/80 percent for training/validation sets. Now my question is which resulting model should I use? Always the one with higher validation accuracy, or maybe the higher mean of training and validation acc? In specfic, which one the two would you prefer?

Epoch #38: training acc: 0.924, validation acc: 0.944
Epoch #90: training acc: 0.952, validation acc: 0.932

Neither of the above mentioned methods could be a potent indicator of the performance of a model.

A simple way to train the model just enough so that it generalizes well on unknown datasets would be to monitor the validation loss. Training should be stopped once the validation loss progressively starts increasing over multiple epochs. Beyond this point, the model learns the statistical noise within the data and starts overfitting.

This technique of Early stopping could be implemented in Keras with the help of a callback function:

class EarlyStop(tf.keras.callbacks.Callback):
    def on_epoch_end(self, epoch, logs={}):
        if(logs.get('val_loss') < LOSS_THRESHOLD and logs.get('val_categorical_accuracy') > ACCURACY_THRESHOLD):
            self.model.stop_training = True

callbacks= EarlyStop()
model.fit(...,callbacks=[callbacks])

The Loss and Accuracy thresholds can be estimated after a trial run of the model by monitoring the validation/training error graph.


How do I prove that $\mathcal{H}$, with $\mathcal{VC}$ dimension $d$, shatters all subsets with size less than $d-1$? If a certain hypothesis class $\mathcal{H}$ has a $\mathcal{VC}$ dimension $d$ over a domain $X$, how can I prove that $H$ will shatter all subsets of $X$ with size less than $d$, i.e. $\mathcal{H}$ will shatter $A \subset X$ where $|A| \leq d-1$?

We can show that it is not true by a counterexample. For example, $X = \{1,2,3\}$ and $\mathcal H = \{\{\},\{1\},\{2\},\{1,2\}\}$ is the finite set hypothesis class. By definition, in this case, the $\mathcal{VC}$ dimension of $\mathcal H$ over the domain $X$ is $d=2$. Although $A = \{3\} \subset X$, whose size is smaller than the $\mathcal{VC}$ dimension, i.e $|A|<d=2$, it is not shattered by $\mathcal H$.


Is it okay to calculate the validation loss over batches instead of the whole validation set for speed purposes? I have about 2000 items in my validation set, would it be reasonable to calculate the loss/error after each epoch on just a subset instead of the whole set, if calculating the whole dataset is very slow?
Would taking random mini-batches to calculate loss be a good idea as your network wouldn't have a constant set? Should I just shrink the size of my validation set?

I assume you intended to write compute the evaluation metric over the validation set in batches; you do not compute loss over the validation set!
That is quite a standard practice in many academic implementations (because, when the validation set is large enough, the memory will be a constraint), however, be sure to take the average of the values over all the batches. Using a K-fold setup will increase the confidence in the reported values.


Reinforcement learning objective as conditional expectations In one of his lectures Levine describes the objective of reinforcement learning as: $$J(\tau) = E_{\tau\sim p_\theta(\tau)}[r(\tau)]$$
where $\tau$ refers to a single trajectory and $p_\theta(\tau)$ is the probability of having taken that trajectory so that $p_\theta(\tau) = p(s_1)\prod_{t = I}^T \pi_{\theta}(a_t, s_t)p(s_{t+1}|s_t, a_t))$.

Starting from this definition, he writes the objective as $J(\tau) =\sum_{t=1}^T E_{(s_t, a_t)\sim p_\theta(\tau)}[r(s_t, a_t)]$ and argues that this sum can be decomposed by using conditional expectations, so that it becomes:

$$J(\tau) = E_{s_1 \sim p(s_1)}[E_{a_1 \sim \pi(a_1|s_1)}[r(s_1, a_1) + E_{s_2 \sim p(s_2|s_1, a_1)}[E_{a_2 \sim \pi(a_2|s_2)}[r(s_2, a_2)] + ...|s_2]|s_1,a_1]|s_1]]$$

Can anyone explain this last step? I guess the law of total expectation is involved, but I can not figure out how exactly.

In the YouTube depiction of CS294-112 fall 2017 lecture 3 Reinforcement Learning, Levine, the transition of the finite horizon expected reward to a form where each transition is decoupled from the entire Markov chain of state-action marginals is explained between $t_{video}$ = 44:04 and $t_{video}$ = 45:22.

At t=44:29, the probabilistic expectation where no actions take place is given as a starting point.  It's a distribution already known, the initial state distribution.

The statement, "Inside that expectation ...," at $t_{video}$ = 44:39, begins the description of how to build an expectation expression for the first two vertices of the Markov chain.  This is the beginning of a process where expectations $E$ are factored recursively.  The purpose of the expansions is to decouple the expectation at each vertex from those of other vertices in the Markov chain, clarifying dependencies and exposing the mathematical features of the recursion.

The right-hand factor is the integrated expectation of reward over the achievement of the next state-action marginal, where the action is distributed according to the fixed policy.

How a state and action pair fits into a state-action marginals which can then form a Marcov Chain, provided the policy is fixed and known, was explained at $t_{video}$ = 21:40 in this same lecture.  Each vertex in the chain is taken to be the aggregation of a state with the proposed action to be applied to it, leading to a reward $r(s, a)$.

Returning to $t_{video}$ = 44:39, notice the plus sign without the right-hand addend, waiting for another recursion.  When the recursion is expressed later in the process, the right-hand factor becomes the integrated expectation of reward over the achievement of the finite sequence represented by the remainder of the Markov chain.

Multiplication is implied because we are now conditioning on both probabilities of the initial state and a transition from it.  Notice also that the second vertex in the Marcov Chain is a state-action marginal.

Notice now that rewards are additive because the goal of learning was defined as a sum of products, which is a simplifying assumption.

Also notice that each expectation distributions of reward after the first one can be expressed as a product of single-vertex expectation distributions.  Each factor is a localized expectation along the sequence of vertices in the Markov chain of state-action marginals.  This is the factoring of expectation distributions.

This factoring is the application of Product distribution, which can be proven using the "law" of total expectations.

At $t_{video}$ = 44:51, the pattern recursion is expressed with a single ellipsis.  Recognition of the recursion pattern can be facilitated by re-expressing with a few modifications of mathematical style.

Use of the original variable to represent the value objective
Extending the equality
Using two ellipses instead of one clarify the recursion is a continuation of conditions from right to left as well as continuation of rewards from left to right
Strategically placing line returns

$$\pi_{\theta}(\tau) = \sum_{t=1}^T \operatorname{E}_{(s_t, a_t)\sim p_\theta(\tau)}[r(s_t, a_t)] \\ = E_{s_1 \sim p(s_1)}[E_{a_1 \sim \pi(a_1|s_1)}[r(s_1, a_1) \\ + E_{s_2 \sim p(s_2|s_1, a_1)}[E_{a_2 \sim \pi(a_2|s_2)}[r(s_2, a_2)] \\ + \; ... \\ ...|s_2]|s_1,a_1]|s_1]]$$

Inverting the transformation, recombining the expansion back to its original form may also be illustrative.


What are some tools for labelling images and videos? I am looking for AI tools for image and video labeling. It would be great if someone could share its own experience as well suggest tools.

I also have some questions

Which tools are available? (state of the art)
What are their benefits, how do they compare?
Why did we choose the specific tool?

There are a few.

Sloth
LabelBox
RectLabel
LabelMe

OpenCV also has some facilitation for annotating.

Annotation is the more common name used in software suites for tools that facilitate adding labels to images and frames of movies because.  Simple categorization is of limited use in the real world, especially with moving pictures where action may be important and requires recognizing consistent position and size change.

Annotation is more than adding a number or concept class instance in object recognition. There are five numbers that define the frame, potentially seven if both certainty and pixel depth layers are independently annotated as in the case of heat signatures.

$h_0$: Box horizontal min
$h_1$: Box horizontal max
$v_0$: Box vertical min
$v_1$: Box vertical max
$t$: Time or frame index
$P$: Optional probability that the object in the box qualifies if the annotation involves doubt
$\lambda$: Optional pixel layer depth indicating range of wavelengths, important for discriminating warm blooded people and pets from immobile objects for vehicle automation or the heat signatures to discriminate ballistic missiles from benign aeronautics


How is a ResNet-50 used for deep feature extraction? I'm trying to implement the vehicle re-identification model described in https://arxiv.org/pdf/2004.06271.pdf.
My question focuses on Section 3.2 of the paper, which uses a ResNet-50 for deep feature extraction in order to generate discriminative features which can be used to compare images of vehicles by Euclidean distance for re-identification. It takes a 256x256x3 image as input.
My understanding of ResNet-50 is that its output is of the shape N, where N is the number of classes which an input image could be, and ground truth labels take the form of a one-hot encoding where the '1' value represents the node in the output layer which is associated with the given class.
I am therefore confused by the usage of ResNet-50 in a re-identification task in which the goal is to generate an array of discriminative features which can be compared by Euclidean distance. There is no discrete set of N classes, as the model should work on any of the infinite number of vehicles in the world.
What is the ground truth label in a ResNet-50 in the context of a re-identification task?

The authors use so-called embeddings, it's a form to represent the images in some meaningful vector form.
The procedure to get embedding as follows. First, keep in mind most of the popular convolutional net architectures starts with convolutional layers and then have few fully connected layers. Then do the following.

Train the full network with one-hot encoded labels as usual
Take away the last fully connected layer and use the values on the previous layer as a representation.

In the case of resnet50, you will get a 2048-value float vector. The property of a neural network is that semantically close images usually have close representation on the last layers and you could use euclidian distance to measure the similarity of images in some sense (not really, but it's another long discussion)
I don't know the paper, but I glimpsed through it. You could see in formula 4 the $x$ is embedding representation. Loss at formula 5 is cross-entropy after applying the last linear layer ($Wx + b$) and then softmax.
As a side note, you could skip the first step completely and use pretrained weights as a starting point. I.e. in pytorch you could take pretrained on ImageNet classification weights as follows
import torchvision.models as models
resnet = models.resnet50(pretrained=True)


Can a single neural network handle recognizing two types of objects, or should it be split into two smaller networks? In particular, an embedded computer (with limited resources) analyzes live video stream from a traffic camera, trying to pick good frames that contain license plate numbers of passing cars. Once a plate is located, the frame is handed over to an OCR library to extract the registration and use it further.

In my country two types of license plates are in common use - rectangular (the typical) and square - actually, somewhat rectangular but "higher than wider", with the registration split over two rows.

(there are some more types, but let us disregard them; they are a small percent and usually belong to vehicles that lie outside our interest.)

Due to the limited resources and need for rapid, real-time processing, the maximum size of the network (number of cells and connections) the system can handle is fixed.

Would it be better to split this into two smaller networks, each recognizing one type of registration plates, or will the larger single network handle the two types better?

Well, I do not know what type of features you are giving to your neural network. However, in general, I would go with a single neural network. It seems that you have no limitation in resources for training your network and the only problem is resources while you apply your network.

The thing is that probably the two problems have things in common (e.g. both types of plates are rectangular). This means that if you use two networks, each has to solve the same sub-problem (the common part) again. If you use only one network the common part of the problem takes fewer cells/weights to be solved and the remaining weights/cells can be employed for better recognition.

In the end, if I was in your place I would try both of them. I think that is the only way to be really sure what is the best solution. When speaking theoretically it is possible that we do not include some factors.


How to find the subject in a text? I often develop bots and I need to understand what some people are saying.

Examples:
- I want an apple
- I want an a p p l e

How do I find the object (apple)? I honestly don't know where to start looking. Is there an API that I can send the text to which returns the object? Or perhaps I should manually code something that analyses the grammar?

It depends on the complexity on your sentences. If you have a limited range, you could do simple pattern matching on part-of-speech tags. Put your sentence through a tagger (there are plenty of them around) and look for the first noun following a verb:

I       want an         apple
Pronoun verb determiner noun

(I assume you mean the object, as the subject in that sentence would be I). Scan through the list until you hit a verb, then pick the next noun. This should work for most English sentences.

It gets a bit more complicated if your nouns have additional words around them, for example red apple (where red is an adjective) or bottle of beer (where you have the pattern noun OF noun). So if you want to capture those fully, you might need a few more complex matching rules.

Overall it should still be a lot easier than implementing a full-blown syntactic parser which creates a comprehensive structural analysis of your sentence, most of which you wouldn't need in the first place.


What are the differences between transfer learning and meta learning? What are the differences between meta-learning and transfer learning?

I have read 2 articles on Quora and TowardDataScience.

  Meta learning is a part of machine learning theory in which some
  algorithms are applied on meta data about the case to improve a
  machine learning process. The meta data includes properties about the
  algorithm used, learning task itself etc. Using the meta data, one can
  make a better decision of chosen learning algorithm(s) to solve the
  problem more efficiently.

and

  Transfer learning aims at improving the process of learning new tasks
  using the experience gained by solving predecessor problems which are
  somewhat similar. In practice, most of the time, machine learning
  models are designed to accomplish a single task. However, as humans,
  we make use of our past experience for not only repeating the same
  task in the future but learning completely new tasks, too. That is, if
  the new problem that we try to solve is similar to a few of our past
  experiences, it becomes easier for us. Thus, for the purpose of using
  the same learning approach in Machine Learning, transfer learning
  comprises methods to transfer past experience of one or more source
  tasks and makes use of it to boost learning in a related target task.

The comparisons still confuse me as both seem to share a lot of similarities in terms of reusability. Meta-learning is said to be "model agnostic", yet it uses metadata (hyperparameters or weights) from previously learned tasks. It goes the same with transfer learning, as it may reuse partially a trained network to solve related tasks. I understand that there is a lot more to discuss, but, broadly speaking, I do not see so much difference between the two.

People also use terms like "meta-transfer learning", which makes me think both types of learning have a strong connection with each other.

I also found a similar question, but the answers seem not to agree with each other. For example, some may say that multi-task learning is a sub-category of transfer learning, others may not think so.

Meta-learning is more about speeding up and optimizing hyperparameters for networks that are not trained at all, whereas transfer learning uses a net that has already been trained for some task and reusing part or all of that network to train on a new task which is relatively similar. So, although they can both be used from task to task to a certain degree, they are completely different from one another in practice and application, one tries to optimize configurations for a model and the other simply reuses an already optimized model, or part of it at least.


Why are VAE's useful? I am not sure I understand what is the advantage of using a VAE's over a deterministic Auto Encoder? For example, assuming we have just 2 labels, a deterministic Auto Encoder will always map a given image to the same latent vector. However, one expects that after the training, the 2 classes will form separate clusters in the encoder space.

In the case of the VAE an image is mapped to an encoding vector probabilistically. However, one still ends up with 2 separate clusters. Now, if one passes a new image (at the test time), in both cases the network should be able to place that new image in one of the 2 clusters.

How are these 2 clusters created using the VAE better than the ones from the deterministic case?

The main difference between a variational auto-encoder (VAE) and an auto-encoder is that the VAE is a generative and statistical model  while an auto-encoder (AE) is just a data compressor and decompressor (it is just a function approximator), so an AE is not a statistical model. They both have an encoder and a decoder and they both convert the inputs to a latent representation, but their inner workings are different and their purpose is also slightly different. An AE could be considered a generative model, in the sense that it generates objects that are similar to the input (but they might not be the same as the input). However, it is not a generative model according to the usual statistical definition of a generative model.

In the case of an AE, given an input $x$ (e.g. an image), the encoder produces one latent vector $z_x$, which can be decoded into $x'$ (another image which should be similar or related to $x$). Compactly, this can be presented as $x'=f(z_x=g(x))$, where $g$ is the encoder and $f$ is the decoder. This operation is deterministic, in the sense that, given the same $x$, the same $z_x$ and $x'$ are produced.

In the case of a VAE, given an input $x \in \mathcal{X}$ (e.g. an image), more than one latent vector, $z_{x}^i \in \mathcal{Z}$, can be produced, because the encoder part of the VAE models the inputs as a probability distribution. In other words, the encoder of a VAE assumes that the inputs $\mathcal{X}$ are drawn from a probability distribution, which can be denoted by $\mathcal{X} \sim q$, where $q$ is some computable probability distribution (e.g. a Gaussian distribution with mean zero, $\mu =0$, and a finite standard deviation, $\sigma$). $q$ is defined over $\mathcal{Z}$ (the space of possible latent vectors). More specifically, $q$ is a conditional probability distribution, which can be denoted by $q(z \mid x)$.

So, the encoder of a VAE, while being trained, creates a probability distribution, which, in practice, can be represented by neural networks, that is, you can train a neural network to represent the parameters of e.g. a Gaussian distribution (which is defined by two parameters: the mean and standard deviation). You can thus more precisely denote $q$ by $q_\phi$, where $\phi$ are the parameters of a neural network that e.g. output two numbers: the mean and a standard deviation of $q$.

Given a probability distribution $q_\phi$, we can sample several $z_{x}^i$ from $q_\phi$. Why is this useful? Given the same input $x$ (e.g. a graphical representation of a molecule $m$), we can sample e.g. $N$ latent vectors $z_{x}^1, z_{x}^2, \dots, z_{x}^N$, which can all be decoded (e.g. into $K$ new molecules). Why would this be useful? For example, in the case you need to generate molecules which have a similar structure to the input molecule $m$. Why would you need this? In some cases, molecules with a similar structure can have similar effects, but could e.g. be more easy or inexpensive to synthesise.

Why can we generate $K$ new molecules out of $N$ latent vectors, where $K$ can be greater than $N$? We have not yet mentioned the details of a decoder of a VAE. The decoder of a VAE also models its inputs, $\mathcal{Z}$, as a probability distribution defined over $\mathcal{X}$, which can be denoted by $p_\theta(x \mid z)$, where $z$ is a latent vector. In other words, given the $i$th latent vector sampled from the latent distribution (the distribution of the encoder), $z_{x}^i$, we can sample more than one reconstructed input from the probability distribution of the decoder. Hence, a VAE often constructs two probability distributions: one that is associated with the encoder, $q_\phi(z \mid x)$, and one that is associated with the decoder, $p_\theta(x \mid z)$.

Given that VAEs create these distributions, they are considered statistical models. An auto-encoder has no notion of a probability distribution. An AE only maps inputs to outputs deterministically, so it is a function approximator (given that it approximates a function that compresses the input and then another function that decompresses it). VAEs are thus a lot more flexible than AEs.


What is the difference between applying shallow-learning methods repeatedly and deep learning? In the book Deep Learning with Python, François Chollet writes (section 1.2.6, page 18)

In practice, there are fast-diminishing returns to successive applications of shallow-learning methods, because the optimal first representation layer in a three-layer model isn't the optimal first layer in a one-layer or two-layer model. What is transformative
about deep learning is that it allows a model to learn all layers of representation jointly, at the same time, rather than in succession (greedily, as it's called).

By shallow learning, we mean traditional machine learning models that aren't deep learning, such as support vector machines.
I understood the above as below.

Using a model with three-layer shallow-learning methods has the same output (predicted) value as using one-layer shallow learning method. The effect of using multiple layers of shallow learning methods is to 'increase running time or repetition'.

Did I understand properly?

Quite surprising to find someone reading this same book. I read this part a week ago and the explanation is quite clear in the book :

If you use successive shallow learning methods, you first train one model, then you train another model with the outputs of your first model, and then a third with the outputs of your 2nd model. The problem with that is that each model is trained to get good results at his task, not to send information, so there can be an increase when adding successive models, but it is a very weak increase.
If you use deep learning, all the layers are trained at the same time, so each layer learns how to efficiently transfer important information to the next layer of the model. This is why it is much more efficient.

Hope I made it clearer


Can I use one-hot vectors for text classification? For an upcoming project I'm trying to write a text classifier for the IMDb sentiment analysis dataset. This needs to vectorize words using an embedding layer and then reduce the dimensions of the output with global average pooling. This is proving however to be very difficult for my low experience level, and I am struggling to wrap my head around the dimensionality involved, bearing in mind I must avoid libraries such as tensorflow that would make it very basic exercise. I am hoping that I could make it easier by encoding each word in the reviews as a one-hot vector, and passing it through a few regular dense layers. Would this work and yield decent results?

One hot encoding is a good strategy to apply with categorical variables that assume few possible values. The problem with text data is that you easily end up with corpora with a really large vocabulary. If I remember correctly the IMDb dataset contains around 130.000 unique words, which means that you should create a network with an input matrix of size 130.000 x max_length where max_length is the fixed maximum length allowed for each review. Apart from the huge size, this matrix would also be extremely sparse, and that's another big issue in using one-hot encoding with text.
For these reasons, I really doubt you would achieve any good results with a simple one-hot encoding. Embeddings where actually designed precisely to overcome all these issues, they have fixed reasonable size, they assume continue values between 0 and 1, which is desirable for deep neural networks, and they can be treated as "extra" trainable weights of a network.
If you really want to avoid embeddings I would suggest you to use (or implement, I don't think it will be so hard) a term frequency–inverse document frequency vectoriser. It is closer to one-hot encoding in the fact that it is based on the creation of a huge co-occurances matrix between words, but at least the values are continuous and not dichotomous. Nevertheless I would not expect high performances with the tf-idf either, simply because this type of encoding works best with shallow models like the Naive Bayes rather than deep models.


5 years later, are maxout networks dead, and why? Maxout networks were a simple yet brilliant idea of Goodfellow et al. from 2013 to max feature maps to get a universal approximator of convex activations. The design was tailored for use in conjunction with dropout (then recently introduced) and resulted of course in state-of-the-art results on benchmarks like CIFAR-10 and SVHN.

Five years later, dropout is definitely still in the game, but what about maxout? The paper is still widely cited in recent papers according to Google Scholar, but it seems barely any are actually using the technique.

So is maxout a thing of the past, and if so, why — what made it a top performer in 2013 but not in 2018?

Basically, if you read the full paper (especially, the abstract and the section 7), you find that the main accomplishment remains a marginal contribution on top of dropout.

If you see the empirical results on Table 5 (of the page 5) of the maxout's original paper, you find that the misclassification rate is only very, very slightly lower than that of dropouts. (2.47 % instead of 2.78%)

That could explain the relatively lower interest in the work.


When will artificial intelligence equal human intelligence? What are the current best estimates as to what year artificial intelligence will be able to score 100 points on the Stanford Binet IQ test?

Not going into details of Stanford–Binet test, but just looking at wikipedia page it shows many subtests like knowledge, reasoning, verbal tests etc. Most of the efforts in the artificial intelligence today is directed into research of specific areas like computer vision, natural language processing, machine learning, but also combination of fields like implementation of self driving cars.

Within every field there are still other subfields and problems that are not solved yet. For example, development of human-like natural language processing (NLP) is necessary for intelligent agent to pass any verbal tests, or even non-verbal tests that requires processing of sentences of human language. Famous test that tests intelligence by asking questions in natural language and expects answers in the same form is Turing test. NLP still struggles with many (basic) human skills like listening, speaking, parsing and forming sentences. No one knows when we'll have system that can do these things as good as human. Since this system is crucial, but also far from human-like it's likely cause of delay in developing AI that passes intelligence test. Are these problems AI-hard? Do we need to develop strong AI to solve them?

You can look at speech and listening as interfaces used for expressing and affecting inner processes of human brain. Same goes for other senses like eyesight which is being approximated by computer vision. One could say that we only need to develop convincing mimics of human senses and incorporate them in one big system that will become first human-like AI. That is the minimum requirement. I doubt this will be achieved in this century.

(Other thoughts)
What truly defines intelligence is brain activity. Since it's really complex and one artificial neuron is not equal to one neuron in brain, increase in computation power will not necessarily help achieving human-like AI. Also recognizing such system by mere intelligence test is questionable. For now it's only philosophical discussion but by the time we are able to design such machine I think we'll also have better understanding of human brain. Someone in 2100 might not read this answer on quantum computer with integrated AI OS powered from fusion reactor in his self-flying car, but will probably have many systems that help him in everyday tasks far more than we imagine today.


What is the best measure against overfitting? I wanted to ask about the methodology of testing the ML models against overfitting. Please note that I don't mean any overfitting reducing methods like regularisation, just a measure to judge whether a model has overfitting problems.

I am currently developing a framework for tuning models (features, hyperparameters) based on evolutionary algorithms. And the problem that I face is the lack of a good method to judge if the model overfits before using the test set. I encountered the cases where the model that was good on both training and validation sets, behaved poorly on the test set for both randomized and not randomized training and validation splits. I used k-fold cross-validation with additionally estimating the standard deviation of all folds results (the smaller deviation means better model), but, still, it doesn't work as expected.

Summing up, I usually don't see a correlation (or a very poor one) between training, validation and k-fold errors with test errors. In other words, tuning the model to obtain lower values of any of the above mentioned measures usually does not mean lowering the test error.

Could I ask you, how in practice you test your models? And maybe there are some new methods not mentioned in typical ML books?

tl;dr
The safest method I've found is to use cross-validation for hyperparameter selection and a hold-out test set for a final evaluation.
Why this isn't working for you...
In your case, I suspect you're either running a large number of iterations during for hyperparameter selection or you have a fairly small dataset (or even a combination of both). If you can't find more data or use a larger dataset, I'd suggest limiting the exhaustiveness of your hyperparameter selection phase. If you run the process enough times the model is bound to overfit on the validation sets.
Note that there is no guaranteed safe way of detecting overfitting before the test set!
Why I consider this strategy to be the safest
There are two different types of overfitting you need to be able to detect.
The first is the most straightforward: overfitting on the training set. This means that the model has memorized the training set and can't generalize beyond that. If the test set even slightly differs from the training set (which is the case in most real-world problems), then the model will perform worse on it than on the training set. This is simple to detect and, in fact, the only thing you need to catch this is a test set!
The second type of overfitting you need to detect is on the test set. Imagine you have a model and you make an exhaustive hyperparameter selection using a test set. The you evaluate on the same test set. By doing this, you have adjusted your hyperparameters to achieve the best score for the specific test set. These hyperparameters are thus overfit to that test set even though the samples from that set were never seen during training. This is possible because during the iterative hyperparameter selection process, you have passed information about your test set to your model!
This is much harder to detect. In fact the only way to do so is to split the original data into three parts: the training, the validation and the test sets. The first is used for training the model, the second for hyperparameter selection and the final is used only once for a final evaluation. If your model has overfit (i.e. test performance is worse than training and validation) you need to start from scratch. Shuffle your data, split it again and repeat the process. This is usually referred to as a hold-out strategy.
To make the model even less prone to overfitting, you can use cross-validation instead of a hold-out validation set. Because your model now has to be trained on $k$ slightly different training sets and evaluated on $k$ completely different validation sets, it is much harder for it to overfit on the validation sets (because it needs to fool $k$ different validation sets instead of one).
Cases where this might not be applicable
Depending on the circumstances, it might not be practical to apply both of these techniques.

Cross-validation is pretty robust regarding overfitting but it imposes a computational burden to your process as it requires multiple trainings of the same model. This obviously isn't practical for computationally expensive models (e.g. image classifiers). In this case use a hold-out strategy as mentioned previously.

Using a hold-out test set means that you are reducing the size of your training set, which might actually make your model more prone to overfitting (i.e. have a higher-variance) for small datasets. In this case (if your model is practically untrainable due to the small size) you can resort to cross-validation, but you risk overfitting on the validation set and not having any way to detect it.

How to combat overfitting
Since it is fairly related I'll post a link to an answer on how to combat overfitting.


How can abstract graphs be recognized by neural nets? Recognition of optical patterns (as pixel maps) by neural networks is standard. But optical patterns may be only slightly distorted or noisy, and may not be arbitrarily scrambled – e.g. by permutations of rows and columns of the pixel map – without losing the possibility to recognize them. This in turn is the normal case for abstract graphs in their standard representation as adjacency matrices: only under some permutations of nodes a possible pattern is visible. In general, for almost all random graphs under no permutation a pattern is visible, but for all graphs under almost all permutations a pattern is invisible.
How can this be handled in the context of either unsupervised or supervised learning? Assume you have a huge set of graphs with 100 nodes and 1,000 edges, given as 100$\times$100 adjacency matrices under arbitrary permutations, but with only two isomorphism classes. How could a neural network find this out and learn from the samples?
Is this possibly common knowledge: that it can not? Or are there any tricks?
(One trick might be to draw the graph force-directed and hope that it settles in a recognizable configuration. But this to be detectable would require a much larger pixel map than 100$\times$100. But why not?)

The OP's (i.e. my) assumption is wrong. It is not true that for almost all random graphs under no permutation a pattern is visible, as can be  seen in Tiago P. Peixoto's paper Bayesian stochastic blockmodeling, p. 4:

The opposite seems to be correct: For almost all random graphs there are permutations such that patterns are visible.


Training methods for bipedal robot I am looking to train a bipedal robot using unity as a scape with a genetic algorithm. I will import the CAD into unity so the hardware is exact. My questions:

Is Unity physics accurate enough to train a neural network that will perform in the real world?
Should I optimize the network using reinforcement learning in the real world (after trained in scape)?
I am looking to use air muscles for my build. If the physics aren’t exactly right in unity (elasticity, max length, torque) will the bot still perform in the real world?
Are there any other programs that would be better than unity to train a robot inside a scape?
Any other approaches or new ideas on how to train the bot more efficiently would be greatly appreciated.

Not really. Unity physics is just an approximation of an approximation. It has to look more or less real but at the same time the performances are very important, so it has not the realistic level you would hope to "bring things to the real world". There are some physics engine you can install that usually work a bit better. Still, don't expect "real-world level".
Based on 1, yes. If, once you got it to the real world you still give it the chance to optimize, it can only make things better.
This is difficult to say. You should try to use the best possible approximation in Unity, maybe testing multiple scenarios and seeing that they perform more or less in the same way. Then train. Then bring this "approximated model" to the real world and let it train more to adjust to the real physics.
I don't know this. Unity seems the most versatile around (together with other game engines). This versatility is its strength and weakness, as it cannot focus on solving perfectly a single problem. It rather has to aim at generalizing as much as possible. There might be "more specialized" programs around, but I doubt.
Just try different algorithms/methods. Usually with complex problems neuroevolutionary techniques perform better, but the amount of code is hugely higher.


Using reinforcement learning to find a preconditioner for linear systems of the form Ax = b Sparse linear systems are normally solved by using solvers like MINRES, Conjugate gradient, GMRES.

Efficient preconditioning, i.e., finding a matrix P such that PAx = Pb is easier to solve than the original problem, can drastically reduce the computational effort to solve for x. However, preconditioning is normally problem-specific and there is not ONE preconditioner that works well for every problem.

I thought this would be an interesting problem to apply RL since there are certain norms (e.g. condition number of matrix PA) to measure if P is a good preconditioner, but I could not find any research in this field.

Is there a specific problem why RL could not be applied?

Reinforcement Learning is a method for learning to perform beneficial actions in an environment. One way this is accomplished is by learning to predict useful actions as a function of the observed state of the environment. Another is by learning to predict the expected utility gain of doing an action in a particular observed state. Usually the fact that the agent executes a sequence of actions is exploited to learn more rapidly.

In contrast, the problem you describe is to solve a linear system of equations, which is to say, to learn some hidden values $x$ such that $Ax = b$ for known $A$ and $b$. Gradient decent is a natural way to solve this problem because it is easy to calculate the gradient, and, since the matrices and vectors have the same dimensionality, it is reasonable to expect that the optimization surface is smooth with a single global minima.

While RL techniques could be applied to solve this problem (I guess by predicting values of X in response to inputs b?), none of the usual features that privilege the RL approach over a standard supervised learning approach are present (there's no sequential relationship between datapoints, there's just a list of constraints essentially).


Are there any strategies that would help me visualize the 'behavior space' and make a novelty function? In “Abandoning Objectives: Evolution through the Search for Novelty Alone”, it is explained how the novelty search is a function that is domain specific, depending on the differing behaviors that can potentially emerge.

The primary test is a deceptive maze and it seems like they define novelty as a function that is dependent on each actor's ending position as a distance from other actors' ending position.

I am wanting to try implementing this on some tasks. Some simple AI tasks such as playing pong, or recreating MarI/O, or sticking them in an arena as an actor who can move, turn, and shoot (with other actors in the arena with them).

I have a really hard time thinking of how to model the behavior functions for these kinds of instances without making it into an objective.
For pong, I imagine I could determine novelty by the AI's point score, but isn't this basically making the score an objective since it can only go up? For MarI/O, I've seen some implementations that look at the list of unique grid locations that Mario visited in what order, but I didn't come up with that myself.

For the arena example, my first impulse is to have a score based on how long the actor survived and how many other actors the AI eliminated; but again, this can only go up and seems to me like it is defining an objective.

Are there any strategies or ways to think about the problems that would help me better visualize the 'behavior space' and make a better novelty function?

I think that the best approach is to "switch point of view" from the general, objective-oriented, Genetic Algorithm's behaviours.

Usually GAs rely on individualism: the best survives. To do this you have to define what 'best' means and this is done through a fitness function that measures something objective, independent from the individual (i.e. a score, classical example).

If you want to measure novelty, collectivism becomes more important, as the whole population (present and past) must be considered. You have to think about measuring how different the individual X did from 'the rest' (i.e. location never reached before).

Another interesting point is that you should think in a more multidimensional way: a score is uni-dimensional, everyone wants to get higher, that is easy. A location in space is more difficult to achieve and that is why novelty becomes interesting.

To sum up: stay multidimensional, always treat the population as a multi-organism rather than focusing on the single individual. I hope this helps :)


What is the relationship between robustness and adversarial machine learning? I have been reading a lot of articles on adversarial machine learning and there are mentions of "best practices for robust machine learning".

A specific example of this would be when there are references to "loss of efficient robust estimation in high dimensions of data" in articles related to adversarial machine learning. Also, IBM has a Github repository named "IBM's Adversarial Robustness Toolbox".
Additionally, there is a field of statistics called 'robust statistics' but there is no clear explanation anywhere about its relation to adversarial machine learning.

I would therefore be grateful if someone could explain what robustness is in the context of Adversarial Machine Learning.

A robust ML model is one that captures patterns that generalize well in the face of the kinds of small changes that humans expect to see in the real world.

A robust model is one that generalizes well from a training set to a test or validation set, but the term also gets used to refer to models that generalize well to, e.g. changes in the lighting of a photograph, the rotation of objects, or the introduction of small amounts of random noise.

Adversarial machine learning is the process of finding examples that break an otherwise reasonable looking model. A simple example of this is that if I give you  a dataset of cat and dog photos, in which cats are always wearing bright red bow ties, your model may learn to associate bow ties with cats. If I then give it a picture of a dog with a bow tie, your model may label it as a cat. Adversarial machine learning also often includes the ability to identify specific pieces of noise that can be added to inputs to confound a model.

Therefore, if a model is robust, it basically means that it is difficult to find adversarial examples for the model. Usually this is because the model has learned some desirable correlations (e.g. cats have a different muzzle shape than dogs), rather than undesirable ones (cats have bow ties; pictures containing cats are 0.025% more blue than those containing dogs; dog pictures have humans in them more often; etc.).

Approaches like GANs try to directly exploit this idea, by training the model on both true data and data designed by an adversary to resemble the true data. In this sense, GANs are an attempt to create a robust discriminator.


Can I use neural networks for a problem (in description)? I am modelling a process with 4 input parameters x1 x2 x3 x4. The output of the process is 2 variable y1 y2that varies with length and time.
I also have data from experiments basically recording the trends in the two output variables as I vary my input variable.
So far I have only seen neural network examples which will take input x1 x2 x3 x4 t
(t  is time) and predict y1 y2 at said time t (no consideration of location). I would however like to also like to see variation with length as well at a given time t [y1a y1b... y1z; y2a y2b... y2z] where (a, b...z) are location points at an incremental distance dh from the start.
Any help is appreciated. TIA

To answer the titular question first: Yes, of course you can. Whether a neural network can give you better results than a simpler model, however, depends on:

How complex/non-linear the relationship between your input and output variables is;
Whether the neural network you have specified is able to learn this relationship efficiently;
How much training data you have.

With the information you have provided in the question, there's really no telling how it will perform against a simpler model, so I would advice trying both.

As for how your output varies over time and location, just include both in your model. In case of a linear regression model, accounting for spatiotemporal autocorrelation could be done with a mixed model using an appropriate covariance structure. The challenge for a neural network would be how to specify one that can learn this type of relationship (for starters, read up on RNNs for longitudinal data).


How to deal with a huge action space, where, at every step, there is a variable number of legal actions? I am working on creating an RL-based AI for a certain board game. Just as a general overview of the game so that you understand what it's all about: It's a discrete turn-based game with a board of size $n \times n$ ($n$ depending on the number of players). Each player gets an $m$ number of pieces, which the player must place on the board. In the end, the one who has the least number of pieces wins. There are of course rules as to how the pieces can be placed so that not all placements are legal at every move.
I have the game working in an OpenAI's gym environment (i.e. control by step function), have the board representation as the observation, and I have defined the reward function.
The thing I am struggling with right now is to meaningfully represent the action space.
I looked into how AlphaZero tackles chess. The action space there is $8*8*73 = 4672$: for every possible tile on the board, there are 73 movement-related modalities. So, for every move, the algorithm comes up with 4672 values, the illegal ones are set to zero and non-zero ones are re-normalized.
Now, I am not sure if such an approach would be feasible for my use-case, as my calculations show that I have a theoretical cap of ~30k possible actions ($n * n * m$) if using the same way of calculation. I am not sure if this would still work on, especially considering that I don't have the DeepMind computing resources at hand.
Therefore, my question: Is there any other way of doing it apart from selecting the legal actions from all theoretically possible ones?
The legal actions would be just a fraction of the ~30k possible ones. However, at every step, the legal actions would change because every new piece determines the new placement possibilities (also, the already placed pieces are not available anymore, i.e. action space generally gets smaller with every step).
I am thinking of games, like Starcraft 2, where action space must be larger still and they demonstrate good results, not only by DeepMind but also by private enthusiasts with for example DQN.
I would appreciate any ideas, hints, or readings!

One way I can think of is to redefine "actions" in a game to make them more fragmented, in such a way that a player has multiple actions per turn. In chess, for example, we can define an action as choosing a tile from which to move, or choosing the motion from the chosen tile, as 2 separate actions.

As an example a turn might consist of the following two actions:

Choose E4
Move forward 2 spaces

That way there are 64 + 73, rather than 64 * 73 possible actions. The transition model would indicate that it's still the same player's turn after a "tile selection" action is done.

Of course, this would require increasing the state space in such a way that you can determine which action is legal. So there's a difference between a board state where nothing is "selected" and the same board state where one tile is selected by one player. In the chess example, this would require 2 more boolean CNN layers, one for each player, indicating which tile (if any) is "selected".

I never tried this myself, and I imagine that this might make the learning slower and more difficult, since it requires a deeper tree in the MCTS for the same set of actions.


Which machine learning algorithm can be used to identify patterns in a dataset of the cache performance of a CPU? I need a machine learning algorithm to identify patterns in a dataset (saved in a CSV file) that contains details of the cache performance of a CPU. More specifically, the dataset contains columns like Readhits, Readmiss or Writehits.

The patterns the algorithm identifies should be helpful in the following ways.

help the user to increase the performance of the workload next time,
help to identify any problems based on the features, or
help the user to predict future data values or future events that may occur based on the patterns.

Which ML algorithms can I use?

You're basically looking for is unsupervised learning (UL).  There are a lot of UL techniques around, but I'm not sure you'll find one that does exactly what you want with no user input at all. Still, if you skim the literature on these approaches, you may well find something useful.

One option is DBSCAN, a very popular clustering algorithm that does not require the user to input an initial target number of clusters (something that most clustering algorithms do require).  But even then, you still have to give the algorithm values for epsilon (a distance used in calculating the clusters) and minPts (the minimum number of points required to constitute a "dense" region).

You might also look at self-organizing maps, an approach to unsupervised learning for neural networks.

Some other search terms that might lead you in a useful direction include "data mining" and "knowledge discovery in databases" (KDD).


Is it common to have extreme policy's probabilities? I have implemented several policy gradient algorithms (REINFORCE, A2C, and PPO) and am finding that the resultant policy's action probability distributions can be rather extreme. As a note, I have based my implementations on OpenAI's baselines. I've been using NNs as the function approximator followed by a Softmax layer. For example, with Cartpole I end up with action distributions like $[1.0,3e-17]$. I could understand this for a single action, potentially, but sequential trajectories end up having a probability of 1. I have been calculating the trajectory probability by $\prod_i \pi(a_i|s_i)$. Varying the learning rate changes how fast I arrive at this distribution, I have used learning rates of $[1e-6, 0.1]$. It seems to me that a trajectory's probability should never be 1.0 or 0.0 consistently, especially with a stochastic start. This also occurs for environments like LunarLander.
For the most part, the resulting policies are near-optimal solutions that pass the criteria for solving the environments set by OpenAI. Some random seeds are sub-optimal
I have been trying to identify a bug in my code, but I'm not sure what bug would be across all 3 algorithms and across environments.
Is it common to have such extreme policy's probabilities? Is there a common way to handle an update so the policy's probabilities do not end up so extreme? Any insight would be greatly appreciated!

Your policy gradient algorithms appear to be working as intended. All standard MDPs have one or more deterministic optimal solutions, and those are the policies that solvers will converge to. Making any of these policies more random will often reduce their effectiveness, making them sub-optimal. So once consistently good actions are discovered, the learning process will reduce exploration naturally as a consequence of the gradients, much like a softmax classifier with a clean dataset.
There are some situations where a stochastic policy can be optimal, and you could check your implementations can find those:

A partially observable MDP (POMDP) where one or more key states requiring different optimal actions are indistinguishable to the agent. For example, the state could be available exits in a corridor trying to get the end in a small maze, where one location secretly (i.e. without the agent having any info in the state representation that the location is different) reverses all directions, so that progressing along it is not possible for a deterministic agent, but a random agent would eventually get through.

In opposing guessing games where a Nash equilibrium occurs for specific random policies. For example scissor, paper, stone game where the optimal policy in self-play should be to choose each option randomly with 1/3 chance.

The first example is probably easiest to set up a toy environment to show that your implementations can find stochastic solutions when needed. A concrete example of that kind of environment is in Sutton & Barto: Reinforcement Learning, An Introduction chapter 13, example 13.1 on page 323.
Setting up opposing agents in self-play is harder, but if you can get it to work and discover the Nash equilibrium point for the policies, it would be further proof that you have got something right.


Recommendation system based on content type I am new to this field and would like to know that for what kind of data types other than images, recommendation system can be created using machine learning. Suppose for contents like audio or video, is it necessary to use data set of actual audio files or video files or just text information about the file is enough for this system ?

Recommendation systems can be applied for anything, as long as you have sufficient training data.

The most important inputs to the recommendation system are not "audio files or video files".

Wikipedia gives you the list:

Similarity matrix
Item attributes
User activities and behaviours
User profile

  https://en.wikipedia.org/wiki/Recommender_system


AI becoming sentient plausibility? In lots of sci-fi, it seems that AI becomes sentient (Terminator, Peter F Hamilton's SI (commonwealth saga), etc.)

However, I'm interested in whether this is actually plausible, whether an AI could actually break free form being controlled by us, and if that is possible, whether there is any research as to about what sort of complexity / processing power an AI would need to be able to do this.

There are already programs that have broken free of our control (Morris worm) so that in itself doesn't imply any great computational demands.

Sentience is ill-defined but is certainly not a pre-requisite for a program to do mischief beyond what its creators intend.

It's difficulty to estimate what sort of processing power is required to support human-like intelligence, since we don't know what the most efficient way to achieve that would be.  If the most processing efficient would be to implement a neural network approaching the number of neurons and interconnects of the human brain processing signals at the same rate, the fastest artificial neural network implementations extant are at least 4-5 orders of magnitude short, is thousands of times less power efficient, and doesn't seem to have a realistic way to scale to the number of interconnects required (see this question)


Should Q values be changing within an epoch/episode or should they change after one episode/epoch? I am trying to use Deep-Q learning environment to learn Super Mario Bros. The implementation is on Github.

I have a neural network that Q values update within an episode for a very small learning rate (0.00005). However, even if I increase the learning rate to 0.00025, the Q values do not change within an episode as they are predicting the same Q values regardless of what state it is in. For example, if Mario moves right, the Q value is the same. When I start a new episode, the Q values change though.

I think that the Q values should be changing within an episode as the game should be seeing different parts and taking different actions. Why don't I observe this?

I was attaining negative values out of my convolutional layers and then using relu on them resulted in the gradient of the activation being 0. Hence, my Q values were not being updated. I've since updated my activations to be ELU. Thanks for the help.


How can we create an AI to develop mobile apps? There are AI creating game, content and more.

I'm thinking on how can AI develop mobile app itself?

The computer languages might easy for AI to learn.

AI can learn a lot from good open source project in github.

The trend prediction can help AI to select the topic for creating a great apps.

There are lots of details to let AI create a great apps.

We don't know how to do that yet. The problem is one of scale:

Despite many years of research into program synthesis via heuristic methods, it's still not possible to automatically create programs (e.g. via Genetic Programming (GP), Grammatical Evolution (GE) or Learning Classifier Systems (LCS)) that are thousands of lines long, whether that's for mobile or any other application area.

Contrary to popular belief, alternative formal methods approaches can indeed be used to create sizeable programs, but the kind of interaction that a mobile app would typically require is not easily specified in this way.

The scale at which heuristic approaches are currently viable is closer to the scale of expressions (e.g. single program statements) than entire programs. An intermediate approach is therefore to provide a program template and let GP etc generate the missing parts of the template.

This paper describes how to combine Machine Learning with the 'Template Method' Design Pattern in order to create larger programs than would otherwise be possible, giving the specific example of a 'hyper-quicksort'.


How could I use machine learning to detect text and non-text regions in scanned documents? I have a collection of scanned documents (which come from newspapers, books, and magazines) with complex alignments for the text, i.e. the text could be at any angle w.r.t. the page. I can do a lot of processing for different features extraction. However, I want to know some robust methods that do not need many features.
Can machine learning be helpful for this purpose? How could I use machine learning to detect text and non-text regions in these scanned documents?

TextDetector, Tesseract and other open source packages implement text detection (object detection for text). There's also a pretrained Tensorflow model that does text detection. A text detector will give you the bounding boxes in your image for any text that it recognizes. In the case of Tesseract, it will also output the text (OCR is built in). So you can read the code in these packages to get ideas for your own machine learning pipeline. Basically you need both a regressor (for the bounding boxes) and a classifier (to detect whether the box contains text or not).


Does changing the order of the convolution layers in a CNN have any impact? Could changing the order of convolution layers in a CNN improve accuracy or training time?

Conventionally, CNN layers downsample over and over, which enables them to capture details at different levels of abstractions. Usually, it is observed that the initial layers do nothing more than detecting edges, or filtering color channels; the combinations of these edges are what we perceive as 'features'.

If you reverse the order, you essentially are changing sampling modes down the line.
CNNs detect by 'downsampling' the inputs and therefore 'extracting' features.

It may not work as expected!


How do I choose the optimal batch size? Batch size is a term used in machine learning and refers to the number of training examples utilised in one iteration. The batch size
can be one of three options:

batch mode: where the batch size is equal to the total dataset thus making the iteration and epoch values equivalent
mini-batch mode: where the batch size is greater than one but less than the total dataset size. Usually, a number that can be divided into the total dataset size.
stochastic mode: where the batch size is equal to one. Therefore the gradient and the neural network parameters are updated after each sample.

How do I choose the optimal batch size, for a given task, neural network or optimization problem?
If you hypothetically didn't have to worry about computational issues, what would the optimal batch size be?

Here are a few guidelines, inspired by the deep learning specialization course, to choose the size of the mini-batch:

If you have a small training set, use batch gradient descent (m < 200)

In practice:

Batch mode: long iteration times
Mini-batch mode: faster learning
Stochastic mode: lose speed up from vectorization

The typically mini-batch sizes are 64, 128, 256 or 512.

And, in the end, make sure the minibatch fits in the CPU/GPU.

Have also a look at the paper Practical Recommendations for Gradient-Based Training of Deep Architectures (2012) by Yoshua Bengio.


Why are there transition layers in DenseNet? The DenseNet architecture can be summarizde with this figure:

Why there are transition layers between each block?

In the papers, they justify the use of transition layers as follow :

  The concatenation operation used in Eq. (2) is not viable when the size of feature-maps changes. However,  an essential part of convolutional networks is pooling layers that change the size of feature-maps. To facilitate pooling in our architecture we divide the network into multiple densely connected dense blocks

So, if I understood correctly, the problem is that the feature map size can change, thus we can't concatenate. But how does the addition of transition layers solve this problem?

And how can several dense blocks connected like this be more efficient that one single bigger dense block?

Furthermore, why are all standard DenseNets made of 4 dense blocks? I guess I will have the answer to this question if I understood better the previous questions.

The point of DenseNet was to go as deep as ResNets, if not deeper, and keep multiple skip connections to preserve the gradient flow back better as well as to keep the earlier layers context (which prevents overfitting). With layers as deep as 120, having a single block being fully concatenated to all the previous ones would mean having a way large feature map, which, I guess, would be computationally very expensive and not feasible.

About transition layers (convolution + pooling), I think it's just a way of downsampling the representations calculated by DenseBlocks slowly upto the end as after transition layers the representations go from $56 \times 56$ to $28 \times 28$ to $14 \times 14$, and so on.

The authors state it this way

  To further improve model compactness, we can reduce the number of feature-maps at transition layers


What is a model and how is it designed? I read these things on the internet like

  My model determines the future scope..."

or

  My model gives accurate readings about what the score would be..."

What are these models? How are they designed?

A model is exactly what the name suggests.  A simplified representation of a solution to a real life problem.

For example, if you think of a simple formula for a falling object you may not take into account real life variables such as the imperfections on the surface of the object, atmospheric conditions, the exact composition of the air the object is falling through and how it may affect friction.  you just use a simple model to "model" the fall and get a reasonably accurate result.  its a model, it doesnt have all the details.  just like a model car wouldnt have all the details of a real car.

Here's a good read to get you started:
https://en.wikipedia.org/wiki/Mathematical_model


What kind of algorithm is used by StackGAN to generate realistic images from text? What kind of algorithm is used by StackGAN to generate realistic images from text? How does StackGAN work?

The paper StackGAN: Text to Photo-realistic Image Synthesis
with Stacked Generative Adversarial Networks should provide the answers to your questions.
Here's an excerpt from the abstract of the paper.

Synthesizing photo-realistic images from text descriptions is a challenging problem in computer vision and has many practical applications. Samples generated by existing text-to-image approaches can roughly reflect the meaning of the given descriptions, but they fail to contain necessary details and vivid object parts. In this paper, we propose stacked Generative Adversarial Networks (StackGAN) to generate photo-realistic images conditioned on text descriptions. The Stage-I GAN sketches the primitive shape and basic colors of the object based on the given text description, yielding Stage-I low resolution images. The
Stage-II GAN takes Stage-I results and text descriptions as inputs, and generates high resolution images with photorealistic details. The Stage-II GAN is able to rectify defects and add compelling details with the refinement process.


Deep Q-Learning poor convergence on Stochastic Environment I'm trying to implement a Deep Q-network in Keras/TF that learns to play Minesweeper (our stochastic environment). I have noticed that the agent learns to play the game pretty well with both small and large board sizes. However, it only converges/learns when the layout of the mines is the same for each game. That is, if I randomize the mine distribution from game to game, the agent learns nothing - or near to it. I tried using various network architectures and hyperparameters but to no avail.
I tried a lot of network architectures including:

The input to the network is the entire board matrix, with the individual cells having values of -1 if unrevealed, or 0 to 8 if revealed.
The output of the network is also the entire board representing the desirability of clicking each cell.
Tried fully connected hidden layers (both wide and deep).
Tried Convolutional hidden layers (tried stacked them, using different kernel sizes, padding, etc.).
Tried adding Dropout after hidden layers too.

Is DQN applicable for environments that change every episode or have I approached this from the wrong side?
It seems no matter the network architecture, the agent won't learn. Any input is greatly appreciated. Please let me know if you require any code or further explanations.

The inputs that you describe seem like they should be sufficient for a DQN-based agent to learn a good strategy for playing Minesweeper, regardless of whether or not the starting layout changes. The inputs contain all information that is necessary.

However, the problem certainly becomes much easier (probably too easy) if the initial problem is always the same. The DQN algorithm will be very likely to "pick up" on this trend and "exploit" it. The inputs may be sufficient to learn a more general Minesweeper strategy, but if it is consistently faced with the same "level" every single time, it will be much easier for the DQN algorithm to just memorize exactly where the mines are and play perfectly based on that memory, rather than any actual strategy. Due to the way learning is implemented (based on gradient descent), the algorithm will generally tend to converge to such an easily-reachable "memorization" strategy rather than something that is actually "smart".

For that reason, I do think training will be much slower in the case where the layout is randomized. I'm not just thinking along the lines of e.g. twice as slow here, but would expect multiple orders of magnitude more experience required for successful learning. That's just my educated guess though, never tried training DQN for minesweeper specifically so can't tell for sure. It might also require more elaborate hyperparameter tuning, and maybe require a different network architecture (probably require a larger network).


When updating the state-action value in the Monte Carlo method, is the return the same for each state-action pair? Referring to this post, in the following formula to update the state-action value
$$ Q(s,a) = Q(s,a) + \alpha (G − Q(s,a)),$$
is the value of $G$ (the return) the same for every state-action $(s,a)$ pair?
I am a little confused about this point, so I will thank any clarification.

The discussion uses poor notation, there should be a time index. You obtain a list of tuples $(s_t, a_t, r_t, s_{t+1})$ and then, for every visit MC, you update
$$Q(s_t, a_t) = Q(s_t, a_t) + \alpha (G_t - Q(s_t, a_t))\;;$$
where $G_t = \sum_{k=0}^\infty \gamma^k r_{t+k}$, for each $t$ in the episode. You can see that the returns for each time step are calculated for time timestep onwards, and so are not necessarily the same across time steps.


Solving a planning if finding the goal state is part of the problem I having trouble finding some starting points for solving an occupancy  problem which seems like a good candidate for ai.

Assume the following situation:
In a company I have n cars and m employees. Not every employee can drive any car (f. e. a special driving license is required). A car can only be used by one employee at a specific point in time.

There is a plan which states which employee must be somewhere within some time (therefor they must use a car, so the car is blocked for that amount of time).

The goal is to find a near optimal occupancy of the cars according to that plan.

This problem is easy to specify, but I'm stumped as to which methods to implement.

As it can be represented by a graph I think the right way to solve such a problem is using searching techniques, but a problem here is that I don't know the goal state (and there is no efficient way to compute it - thats the task I want the ai to do...). Neither finding the goal state is in fact part of the problem.

So my question is: What ai techniques could be used to solve such a problem ?

Edit: Some clarification:

Assmume we have two sets - one of the employees (E) and one of cars (C). |C| < |E| is most likely true.
Each car has an assigned priority which corresponds to the costs of using it (for example using a Ferrari costs more than using a Dacia, therefore a Dacia has a higher priority (ex. 1) compred to the Ferrari (ex. 10))).
Assume further that having employees which are not using a car at a specific time slice are a bad thing - they cost an individual penalty (you want the employeed to be at the customer and sell things etc.).
The goal is to find the occupation of employees and cars which has a low total cost.

One Example: If you assign an employee to a car at a specific time slice  it may turn out that another employee gets no car within that time slice.
This can be either because

a car is free, but he has no license for it
because a car is free, but the costs of using this car would be higher than having the employee staing at the head quater
because no car is free anymore

Of cause it could be better in terms of costs to change the occupation and give that employee which got no car in this solution a car and therefore having another employee getting no car or not using all cars or ...

Note: There is no need to find an exact optimal solution (=lowest total cost of all possible occupations), as this would require checking out all possible occupations of the exponential solution space.
Insetad finding a more or less good approximation of a near-optimal low total cost is sufficent.

Your question is still nearly perfectly unclear, but let's make a few guesses in order to make some progress.

The biggest mystery are your time slices:

How many of them you need? With more granular time, you get more unknowns and more constraints and the complexity grows quickly.
When someone gets a car, they probably use it to travel somewhere, so it may be necessary to assign the driver to the car for multiple subsequent slices depending in the distance. That's something completely missing from your description (so I'll ignore it).

As already said, you need a cost function, i.e., something to minimize. Even before that, you need to define your variables. Let's say, you need binary variables

x[t, c, e]

such that x[t, c, e] = 1 when at time slice t the car c is assigned to the employee e (otherwise, it's zero). Now, we can specify some constraints

x[t, c, e] = 0 for each t, when the employee e can't drive the car c
for each t and c, the sum of x[t, c, e] over all e is at most one (as no employee can use two cars at the same time)
for each t and e, the sum of x[t, c, e] over all c is at most one (as no car can be use twice at the same time)

I may have missed some constraints, but that's no big deal; I hope you've got the idea.

Your cost function will be a sum of a few terms.

What you wrote about priorities is unclear to me, too, but you can define a weight w[c, e] (or maybe just w[c]), so let the sum of w[c, e] * x[t, c, e] over all t, c and e be the term describing these priorities.
Let u[e] be the cost of giving the employee e no car. The expression y[t, e] = 1 - sum over all c of x[t, c, e] equals to one, when the employee e has no car at time slice t. Now, the corresponding cost term can be expressed as the sum of u[e] * y[t, e] over all e and t.

Again, there may be more of this.

What I described so far is a integer linear programming formulation of your problem. Convert my text into ILP generating code, get an ILP solver, feed it and run it....

When you problem is small, you may even get the optimum. Otherwise, you'll get some solution (this is guaranteed) and a bound on the optimum, so you can know how far you might improve.

That's more than any heuristic solver (e.g., simulated annealing) can offer. OTOH arriving at a good solution may be faster using some heuristic solver. But that's all irrelevant until you get a clear problem definition.


What are examples of promising AI/ML techniques that are computationally intractable? To produce tangible results in the field of AI/ML, one must take theoretical results under the lens of computational complexity.
Indeed, minimax effectively solves any two-person "board game" with win/loss conditions, but the algorithm quickly becomes untenable for games of large enough size, so it's practically useless asides from toy problems.
In fact, this issue seems to cut at the heart of intelligence itself: the Frame Problem highlights this by observing that any "intelligent" agent that operates under logical axioms must somehow deal with the explosive growth of computational complexity.
So, we need to deal with computational complexity: but that doesn't mean researchers must limit themselves with practical concerns. In the past, multilayered perceptrons were thought to be intractable (I think), and thus we couldn't evaluate their utility until recently. I've heard that Bayesian techniques are conceptually elegant, but they become computationally intractable once your dataset becomes large, and thus we usually use variational methods to compute the posterior, instead of naively using the exact solution.
I'm looking for more examples like this: What are examples of promising (or neat/interesting) AI/ML techniques that are computationally intractable (or uncomputable)?

AIXI is a Bayesian, non-Markov, reinforcement learning and artificial general intelligence agent that is incomputable, given the involved incomputable Kolmogorov complexity. However, there are approximations of AIXI, such as AIXItl, described in Universal Artificial Intelligence:  Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability (2005), by Marcus Hutter (the original author of AIXI), and MC-AIXI-CTW (which stands for Monte Carlo AIXI Context-Tree Weighting). Here is a Python implementation of MC-AIXI-CTW: https://github.com/gkassel/pyaixi.


How to describe an keras Model in a scientific report how would you describe a machine learning model in a scientific report? It should be detailed but I just listed the hyperparameters... Have you got more important properties?

Some other details you could mention are:

total number of model parameters (e.g. 1.2M or 0.15M) & depth of the network (e.g. 38-layered network)
family/style of the network architecture (e.g. encoder-decoder arch., LSTM)
specifics of connections between network layers (e.g. residual-, dense-, skip-connections)
specifics of individual components of the network structure (e.g. dilated-convs. (CNNs), attention (LSTMs))
description/reasoning of why you chose a particular structure/sequence of connections in your deep learning model
specifics of training/validation/testing procedures (e.g. augmented training data, cross-validation, test-time-augmentation (TTA), frozen network weights)
other specific details/caveats that allow the results of your deep learning model be easily reproduced from the scientific report

For more info on the best kinds of details to be included in the report, refer to "Methodology"/ "Training"/ "Implementation"/ "Proposed Architecture" sections of the deep learning research papers in your relevant area.


Shortening the development time of a neural network I am developing an LSTM for sequence tagging.
During the development, I do various changes in the system, for example, add new features, change the number of nodes in the hidden layers, etc.
After each change, I check the accuracy using cross-validation on a development corpus.

Currently, in each check, I use 100 iterations to train the system, which takes a lot of time. So I thought that maybe, during development, I can use only e.g. 20 iterations. Then, each check will be faster. After I find the best configuration, I can switch back to 100 iterations to get better accuracy.

My question is: is this consideration correct? I.e, if feature-set A is better than feature-set B with 20 training iterations, is it likely that A will be better than B also with 100 training iterations?

Alternatively, is there a better way to speed up the development process?

Your scenario is common.

The most straightforward approach is to subsample your data randomly. Unless your data or your model has strong bias, your performance to the smaller data set should be comparable. The accuracy might be lower, but the purpose is to do quick sanity check.


What language is the GPT-3 engine written in? I know that the API is python based, but what's the gpt-3 engine written in mostly? C? C++? I'm having some trouble finding this info.

The GPT-3 source code hasn’t been released but the creators say it uses the “same model and architecture as GPT-2” (source) with some exceptions.
The GPT-2 source code is written in 100% Python. The model is based on Tensorflow and NumPy which are written using C and C++. My best guess is that GPT-3 is also written in Python using libraries based on C.


Is a non-linear activation function needed if we perform max-pooling after the convolution layer? Is there any need to use a non-linear activation function (ReLU, LeakyReLU, Sigmoid, etc.) if the result of the convolution layer is passed through the sliding window max function, like max-pooling, which is non-linear itself? What about the average pooling?

Let's first recapitulate why the function that calculates the maximum between two or more numbers, $z=\operatorname{max}(x_1, x_2)$, is not a linear function.

A linear function is defined as $y=f(x) = ax + b$, so $y$ linearly increases with $x$. Visually, $f$ corresponds to a straight line (or hyperplane, in the case of 2 or more input variables).

If $z$ does not correspond to such a straight line (or hyperplane), then it cannot be a linear function (by definition).

Let $x_1 = 1$ and let $x_2 \in [0, 2]$. Then $z=\operatorname{max}(x_1, x_2) = x_1$ for all $x_2 \in [0, 1]$. In other words, for the sub-range $x_2 \in [0, 1]$, the maximum between $x_1$ and $x_2$ is a constant function (a horizontal line at $x_1=1$). However, for the sub-range $x_2 \in [1, 2]$, $z$ correspond to $x_2$, that is, $z$ linearly increases with $x_2$. Given that max is not a linear function in a special case, it can't also be a linear function in general.

Here's a plot (computed with Wolfram Alpha) of the maximum between two numbers (so it is clearly a function of two variables, hence the plot is 3D).

Note that, in this plot, both variables, $x$ and $y$, can linearly increase, as opposed to having one of the variables fixed (which I used only to give you a simple and hopefully intuitive example that the maximum is not a linear function).

In the case of convolution networks, although max-pooling is a non-linear operation, it is primarily used to reduce the dimensionality of the input, so that to reduce overfitting and computation. In any case, max-pooling doesn't non-linearly transform the input element-wise.

The average function is a linear function because it linearly increases with the inputs. Here's a plot of the average between two numbers, which is clearly a hyperplane.

In the case of convolution networks, the average pooling is also used to reduce the dimensionality.

To answer your question more directly, the non-linearity is usually applied element-wise, but neither max-pooling nor average pooling can do that (even if you downsample with a $1 \times 1$ window, i.e. you do not downsample at all).

Nevertheless, you don't necessarily need a non-linear activation function after the convolution operation (if you use max-pooling), but the performance will be worse than if you use a non-linear activation, as reported in the paper Systematic evaluation of CNN advances on the
ImageNet (figure 2).


What is the point of using 1D and 2D convolutions with a kernel size of 1 and 1x1 respectively? I understand the gist of what convolutional neural networks do and what they are used for, but I still wrestle a bit with how they function on a conceptual level. For example, I get that filters with kernel size greater than 1 are used as feature detectors, and that number of filters is equal to the number of output channels for a convolutional layer, and the number of features being detected scales with the number of filters/channels.
However, recently, I've been encountering an increasing number of models that employ 1- or 2D convolutions with kernel sizes of 1 or 1x1, and I can't quite grasp why. It feels to me like they defeat the purpose of performing a convolution in the first place.
What is the advantage of using such layers? Are they not just equivalent to multiplying each channel by a trainable, scalar value?

Traditional CNNs used for image classification (and related tasks) are composed of 1 or more fully connected layers (FCs), after the convolutional and pooling layers, which take as input the features extracted from the convolutional and pooling layers, in order to perform classification or regression.
One problem with FCs in CNNs is that the number of parameters can be very big, with respect to the number of parameters in the convolutional layers.
There are tasks, such as image segmentation, where this big number of parameters is not really needed. An example of a neural network that does not make use of fully connected layers but only uses convolutions, downsampling (aka pooling), and upsampling operations is the U-net, which is used for image segmentation. A neural network that only uses convolutions is known as a fully convolutional network (FCN). Here I give a detailed description of FCNs and $1 \times 1$, which should also answer your question.
In any case, to answer your question more directly, $1 \times 1$ convolutions have been used for image segmentation tasks, i.e. dense classification tasks, i.e. tasks where you want to assign a label to each pixel (or a group of pixels), as opposed to sparse classification tasks such as image classification (where the goal is to assign 1 label to the whole image). Moreover, in comparison with FC layers, they have fewer parameters and, more importantly, the number of parameters in an FCN does not depend on the dimensions of the images (as in the case of traditional CNNs), which is a good thing (especially, when your images have high resolutions), but typically it depends on the number of kernels and instances (of objects), in the case of instance segmentation.
The FCN paper discusses this reduction of the number of parameters (and computation time), so you should probably read this paper for more details.


What is the difference between hypothesis space and representational capacity? I am reading Goodfellow et al Deeplearning Book. I found it difficult to understand the difference between the definition of the hypothesis space and representation capacity of a model.

In Chapter 5, it is written about hypothesis space:

  One way to control the capacity of a learning algorithm is by choosing its hypothesis space, the set of functions that the learning algorithm is allowed to select as being the solution.

And about representational capacity:

  The model speciﬁes which family of functions the learning algorithm can choose from when varying the parameters in order to reduce a training objective. This is called the representational capacity of the model.

If we take the linear regression model as an example and allow our output $y$ to takes polynomial inputs, I understand the hypothesis space as the ensemble of quadratic functions taking input $x$, i.e $y = a_0 + a_1x + a_2x^2$.

How is it different from the definition of the representational capacity, where parameters are $a_0$, $a_1$ and $a_2$?

A hypothesis space/class is the set of functions that the learning algorithm considers when picking one function to minimize some risk/loss functional.
The capacity of a hypothesis space is a number or bound that quantifies the size (or richness) of the hypothesis space, i.e. the number (and type) of functions that can be represented by the hypothesis space. So a hypothesis space has a capacity. The two most famous measures of capacity are VC dimension and Rademacher complexity.
In other words, the hypothesis class is the object and the capacity is a property (that can be measured or quantified) of this object, but there is not a big difference between hypothesis class and its capacity, in the sense that a hypothesis class naturally defines a capacity, but two (different) hypothesis classes could have the same capacity.
Note that representational capacity (not capacity, which is common!) is not a standard term in computational learning theory, while hypothesis space/class is commonly used. For example, this famous book on machine learning and learning theory uses the term hypothesis class in many places, but it never uses the term representational capacity.
Your book's definition of representational capacity is bad, in my opinion, if representational capacity is supposed to be a synonym for capacity, given that that definition also coincides with the definition of hypothesis class, so your confusion is understandable.


What is a time-step in a Markov Decision Process? The "discounted sum of future rewards" (or return) using discount factor $\gamma$ is
$$\gamma^1 r_1 +\gamma^2 r_2 + \gamma^3 r_2 + \dots \tag{1}\label{1}$$
where $r_i$ is the reward received at the $i$th time-step.
I am confused as to what constitutes a time-step. Say, I take an action now, so I will get a reward in 1 time-step. Then, I will take an action again in timestep 2 to get a second reward in time-step 3.
But the formula \ref{1} suggests something else.
How does one define a time-step? Can we take action as well receive a reward in a single step?
Examples are most helpful.

In a Markov Decision Process (MDP) model, we define a set of states ($S$), a set of actions ($A$), the rewards ($R$), and the transition probabilities $P(s' \mid s, a)$. The goal is to figure out the best action to take in each of the states, i.e. the policy $\pi$.
Policy
To calculate the policy we make use of the Bellman equation:
$$V_{i+1}(s)=R(s)+\gamma \max _{a \in A}\left(\sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) V_{i}\left(s^{\prime}\right)\right)$$
When starting to calculate the values we can simply start with:
$$V_{1}(s)=R(s)$$
To improve this value, we should take into account the next action, which can be taken by the system and will result in a new reward:
$$V_{2}(s)=R(s)+\gamma \max _{a \in A}\left(\sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) V_{1}\left(s^{\prime}\right)\right)$$
Here you take into account the reward of the current state $s$: $R(s)$, and the weighted sum of possible future rewards. We use $P(s' \mid s, a)$ to give the probability of reaching state $s'$ from $s$ with action $a$. $\gamma$ is a value between $0$ and $1$ and is called the discount factor because it reduces the importance of future rewards since these are uncertain. An often-used value is $\gamma = 0.95$.
When using value iteration this process is continued until the value function has converged, which means that the value function does not change significantly when doing new iterations:
$$\left\|V_{i+1}(s)-V_{i}(s)\right\|<\epsilon, \; \forall_{s \in S},$$
where $\epsilon$ is a really small value.
Discounted sum of future rewards
If you look at the Bellman equation and execute it iteratively you'll see:
$$ {\scriptstyle  V(s)=R(s) + \gamma \max _{a \in A}\left(\sum_{a \in A} P\left(s^{\prime} \mid s, a\right)\left[R\left(s^{\prime}\right) +  \gamma \max _{a \in A}\left(\sum_{s^{\prime \prime} \in S} P\left(s^{\prime \prime} \mid s^{\prime}, a\right)\left(R\left(s^{\prime \prime}\right) + \gamma \max _{a \in A}\left(\sum_{s^{\prime \prime \prime} \in S} P\left(s^{\prime \prime \prime} \mid s^{\prime \prime}, a\right) V\left(s^{\prime \prime \prime}\right)\right)\right]\right)\right.\right. }$$
This is like (without transition functions):
$$R(s)+\gamma R\left(s^{\prime}\right)+\gamma^{2} R\left(s^{\prime \prime}\right)+\gamma^{3} R\left(s^{\prime \prime \prime}\right)+\ldots$$
To conclude
So when we start in state s we want to take the action that gives us the best total reward taking into account not only the current, or next state, but all possible next states until we reach the goal. These are the time steps you refer to, i.e. each action taken is done in a time step. And when we learn the policy we try to take into account as many time steps as possible to choose the best action.

You can find quite a large number of examples if you search on the internet, for example, in the slides of the CMU, the UC Berkeley or the UW.


How is REINFORCE used instead of Backpropagation? In neural networks with stochastic layers I've seen the use of the REINFORCE estimator for estimating the gradient (because it can't be computed directly).

Some such examples are Show, Attend and Tell, Recurrent models of visual attention and Multiple Object Recognition with Visual Attention.

However, I haven't figured out how this exactly works. How do we "bypass" the gradient's computation by using the REINFORCE learning rule? Does anyone have any insight on this?

REINFORCE is called a gradient estimator because it doesn't work on the true gradient, that comes from a loss function and the whole data, but makes up a heuristic loss, so that the gradient it ends up with isn't the true one. Let's see that with the REINFORCE equation:

$$
{\huge
\Delta \mathbf{\theta}_t = \alpha \nabla_{\mathbf{\theta}} \log \pi_{\mathbf{\theta}} (a_t \mid s_t) v_t
}%
$$

As this shows, the gradient is still there ($\nabla_\theta$). But the policy corresponds to the network's output, so we can use backpropagation to compute the gradient of that heuristic loss with respect to the weights. The real gradient is unknown to us, but this estimation will do the job.