Aren't all discrete convolutions (not just 2D) linear transforms? The image above, a screenshot from this article, describes discrete 2D convolutions as linear transforms. The idea used, as far as I understand, is to represent the 2 dimensional $n$x$n$ input grid as a vector of $n^2$ length, and the $m$x$m$ output grid as a vector of $m^2$ length. I don't see why this can't be generalised to higher-dimensional convolutions, since a transformation matrix can be constructed from one vector to another, no matter the length (right?)

My question: Aren't all discrete convolutions (not just 2D) linear transforms?

Are there cases where such a transformation matrix cannot be found?

Convolution is a pretty misused term in recent times with the advent of CNN.

Short answer, Convolution is a linear operator (check here) but what you are defining in context of CNN is not convolution, it is cross-correlation which is also linear in case of images (dot product).

Convolution:

Computers work only on discrete values, so the discrete time convolution is defined similarly as:
$$
y[n] = \sum_{k=\infty}^{\infty} x[k] h[n-k]
$$

which has the nice property of

$$Y(e^{j\omega}) = X(e^{j \omega})H(e^{j \omega})$$

where each $A(e^{j\omega})$ is the Fourier Transform of $a(t)$
So this is the basic idea of discrete convolution. The point to illustrate here is that convolution operation has some nice properties and very helpful.

Now there are 2 main types of convolution (as far as  I know). One is linear convolution another is circular convolution. In terms of $2D$ signal they are defined in the following ways:
$$y[m,n] = \sum_{j=-\infty}^{\infty}\sum_{k=-\infty}^{\infty} x[i,j]h[m-i,n-j]$$

Circular convolution is the same except that the input sequence is finite from $0$ to $N-1$ giving rise to periodicity in frequency domain. The convolution operation is a little bit different due to this periodicity.

So these are the actual definitions of convolution. It has linearity property (clearly obvious since it is used to calculate output of LTI system), and it also has the linearity in terms of matrix multiplications, since we want to do the computer to do these calculations for us. I don't know a lot but there are many clever manipulations e.g the FFT algorithm an indispensable tool in signal processing (used to convert signals to frequency domain for a certain sampling rate). Like this you can define convolutions in terms of Hermitian matrices and stuff (only if you want to process in the $n$ domain it is much easier to process in the frequency domain).

For example a $1D$ circular convolution between 2 signals in $n$ domain defined in matrix form, can be written as follows $y_n=h_n*x_n$:
where
$$y_t = \begin{bmatrix} y_0 \\
                      y_1 \\
                      y_2 \\
                      y_3
       \end{bmatrix} = \begin{bmatrix}
h_0 & h_3 & h_2 & h_1\\
h_1 & h_0 & h_3 & h_2\\
h_2 & h_1 & h_0 & h_3 \\
h_3 & h_2 & h_1 & h_0
\end{bmatrix}  \begin{bmatrix} x_0 \\
                      x_1 \\
                      x_2 \\
                      x_3
       \end{bmatrix}$$

The same can be done quite easily by converting the functions into frequency domain, multiplying and converting back to time domain.

When we move to $2D$ domain similar equation is formed except (in $n$ domain)instead of $h_0$ we will have a Hermitian matrix $H_0$ and we will perform the Kronecker product (I don't know the justification or proofs of these equations, it probably satisfies the convolution theorem and is fast when ran on computers). Again much easier to do in frequency domain.

When we move to multiple dimensions, it is called Multidimensional discrete convolution as per this Wikipedia article. As the article suggests the property where everything is in frequency domain.
$$Y(k_1,k_2,...,k_M)=H(k_1,k_2,...,k_M)X(k_1,k_2,...,k_M)$$
still holds good. When we do convolutions in the $n$ domain things get tricky and we have to do clever matrix manipulations as shown in the example above. Whereas, as stated above things get much easier in the frequency domain.

Its counter-intuitive that a picture has a frequency domain, and in general its actually not frequency. BUT in DSP we use a lot of filters whose math properties are similar to those of filters in the traditional sense of frequency and hence has the same calculations as in a frequency setting as shown in the 1st example of $1D$ signal.

The point convolution by definition is a linear operation. Check here if the explanations are unconvincing. There are Linear Time Varying systems and its output maybe determined by convolution, but then it uses the equation at a certain point of time i.e:
$$Y(e^{j\omega}, t) = H(e^{j\omega}, t)X(e^{j\omega} )$$.

Now whether it can be represented by matrix products in $n$ domain or not I cannot say. But generalising, it should be possible, only it will involve increasingly complex matrix properties and operations.

Cross Correlation:

Cross correlation is nothing similar to convolution, it has a bunch of interesting properties on its own, hence I do not like the two being mixed together. In signal processing it is mainly related to finding energy (auto-correlation) and has other applications in communication channels.

While in statistics, it is related to finding correlation (misused term since it can take any value, but correlation coefficient takes value between -1 to 1) between 2 stochastic processes, at different time instants, where we have multiple samplings of the signal or ensembles of the signal based on which the expectation is taken (See here). In CNNs maybe a way to see this would be, the image dataset is a ensemble of stochastic process, while the filter is another process which is fixed. And moving the filter over the image is time delay.

In the context of digital image processing cross correlation is just a dot product. And hence it can be represented by matrices. Whether cross correlation is linear or not is difficult to tell (at least I don't know), but in the context of image processing it seems linear. Bottom-line is that it can be definitely implemented by matrices as it is a dot product, whether it is linear in true mathematical sense is doubtful.

The more intuitive way in context of CNNs would be to view filters as just a bunch of shared weights for better regularisation instead of cross correlation or convolution.


What YOLO algorithm can I use for images with noise as I will implement it in real time? I want to detect drivers with or without seatbelts at crossroads. For that, as it is real-time, I am going to use the YOLO algorithm/model. For training data sets (the images) I need to collect, I placed a camera. By recording it and collecting images from there, I am getting images with more noise.

Can I use these images for training? Also, which YOLO version should I use? What are the important points that I should consider for training datasets?

I want to use any version of YOLO compatible with TensorFlow.

It is much better to know basic mechanics of convnets first ,rather than diving straight into complicated models .

For training data sets (the images) I need to collect, I placed a camera. By recording it and collecting images from there, I am getting images with more noise. Can I use these images for training? Also, which yolo version should I use? What are the important points that I should consider for training datasets?

After you are good with the theory part most of your questions will be answered , otherwise you would endup with nothing but buzzwords.

I want to use any version of yolo compatible with tensorflow.

Tensorflow is a framework for building neural networks , so in theory you can build any network with it so compatibility is not at all a problem.


How to decide Linear Separability in my Neural Net work? I am going to design a Neural Net which will be able to break a 5 letter (characters) word into its corresponding syllables (hybrid syllables, I mean it will not strictly adhere to grammatical Syllable rules but will be based on some training sets I provide).

Example :
                  Train -> tra-in

I think of implementing it in terms of some feedforward net as follows :

Input layer ->Hidden layers -> Output layer

There will be 5 input nodes in the form of decimals (1/26 =0.038 for 'A' ; 2/26 = 0.076 for 'B' ......)

The output layer consists of 4 Nodes which corresponds to each gap between two characters in the word.

And fires as follows :

For "TRAIN" (TRA-IN): Input (0.769,0.692,0.038,0.346,0.538)
                               Output(0,0,1,0)

For "BORIC" (BO-RI-C): **Input....
Output (0,1,0,1)

Is it at all possible to implement the Neural Nets in the way I am doing??

And if possible, then how will I decide the number of Hidden layers and Nodes in each layer??

( In the book I am reading, XOR gate problem and its implementation using hidden layer is given . In XOR we could decide the number of Nodes and Hidden Layers required by seeing the Linear Separability of XOR using two lines. But here I think such analysis can't be made.

So how do I proceed?? Or is it a trial and error process?)

I would highly recommend modeling things differently with regard to how letters are presented to the model. While the problem is more natural, perhaps, for a Convolutional or Recurrent Neural Network, there's no problem to try and run this on a feed forward network. However, the way you give letters as input will be very confusing for a network and will make learning very hard. I'd recommend using one hot encoding or even a binary encoding for the letters. If this is for more than playing around I'd try and add some info (encode whether the letter is in "aeiou" in a separate bit).

As for the hidden layers, try playing around a bit. Two systematic approaches are to start very simple and make the model more complicated, or start complicated and make your model simpler (or just normalize a lot). Look at the performance on the training set and on a separate validation set during training. If the model keeps on improving on the training data but starts to deteriorate on the validation data, you're probably over fitting. In this case you should either make the model simpler (fewer nodes, fewer layers) or regularize (start with l2 normalization on the weights). If the data doesn't perform well on the training data, you may wish to make the model more complex.

Once you've tried the feedforward network, really do try CNN or RNNs for this task.


Would it be possible to determine the dataset a neural network was trained on? Let's say we have a neural network that was trained with a dataset $D$ to solve some task. Would it be possible to "reverse-engineer" this neural network and get a vague idea of the dataset $D$ it was trained on?

You can already do this with some neural networks, such as GANs and VAEs, which are generative models that learn a probability distribution over the inputs, so they learn how to produce e.g. images that are similar to the images they were trained with.
Now, if you're interested in whether there is a black-box method, i.e. a method that, for every possible neural network, would tell you the dataset a neural network was trained with, that seems to be a harder task and definitely an ill-posed problem, but I suspect that people working on adversarial machine learning have already attempted or will attempt to do something similar.


Compute Jacobian matrix of Deep learning model? I am trying to implement this paper. In this paper, the author uses the forward derivative to compute the Jacobian matrix dF/dx using chain rule where F is the probability got from the last layer and X is input image.
My model is given below. Kindly let me know how to go about doing that?

class LeNet5(nn.Module):

def __init__(self):

    self.derivative= None # store derivative

    super(LeNet5, self).__init__()
    self.conv1= nn.Conv2d(1,6,5)
    self.relu1= nn.ReLU()
    self.maxpool1= nn.MaxPool2d(2,2)

    self.conv2= nn.Conv2d(6,16,5)
    self.relu2= nn.ReLU()
    self.maxpool2= nn.MaxPool2d(2,2)

    self.conv3= nn.Conv2d(16,120,5)
    self.relu3= nn.ReLU()

    self.fc1= nn.Linear(120,84)
    self.relu4= nn.ReLU()

    self.fc2= nn.Linear(84,10)
    self.softmax= nn.Softmax(dim= -1)

def forward(self,img, forward_derivative= False):
    output= self.conv1(img)
    output= self.relu1(output)
    output= self.maxpool1(output)

    output= self.conv2(output)
    output= self.relu2(output)
    output= self.maxpool2(output)

    output= self.conv3(output)
    output= self.relu3(output)

    output= output.view(-1,120)
    output= self.fc1(output)
    output= self.relu4(output)

    output= self.fc2(output)
    F= self.softmax(output)

    # want to comput the jacobian dF/dimg
    jacobian= computeJacobian(F,img)#how to write this function

    return F, jacobian

In the paper The Limitations of Deep Learning in Adversarial Settings, Papernot et. al., 2016, IEEE the chain rule is used, "To express $\nabla F(X∗)$ in terms of $X$ and constant values only."

Earlier is stated, "Our understanding of how changes made to inputs affect a DNN’s output stems from the evaluation of the forward derivative: a matrix we introduce and define as the Jacobian of the function learned by the DNN. The forward derivative is used to construct adversarial saliency maps indicating input features to include in perturbation $\partial X$ in order to produce adversarial samples inducing a certain behavior from the DNN;"

And later, "We define the forward derivative as the Jacobian matrix of the function F learned by the neural network during training. For this example, the output of F is one dimensional, the matrix is therefore reduced to a vector (below). Both components of this vector are computable using the adversary’s knowledge, and later we show how to compute this term efficiently."

$\nabla F(X) = \Big[ \frac {\partial F(X)} {\partial X_1}, \frac {\partial F(X)} {\partial X_2} \Big] \quad\quad (2)$

Between equation (2) and equation (6) your questeion is answered, resulting in an equation where the chain rule has already been applied.

$\frac {\partial F_j (X)} {\partial x_i} = \Big(W_{n+1,j} \, . \, \frac {\partial H_n} {\partial x_i} \Big) \times \frac {\partial f_{n+1,j}} {\partial x_i} \;(W_{n+1,j} \, . \, H_n + b_{n+1,j}) \quad\quad(6)$

It is (6) that you must implement in code, but that is done after the DNN is converged as the paper states above.

Applying the Chain Rule

If $z = f(y)$ and $y = g(x)$, then $\frac {dz} {dx} = f'(g(x)) g'(x)$

Applied twice, if $w = e(z)$, $z = f(y)$, and $y = g(x)$, then $\frac {dw} {dx} = e'(f(g(x)) f'(g(x)) g'(x)$

Applied indefinitely we multiply all the first order derivatives of intermediate values, which has the following first order predicate logic expression.

$\forall \; 0 \le n \lt N \land v_{n + 1} = f_{n + 1}(v_n) \land F_{n+1}(x) = f_{n+1}(F_n(x)) \land g(a) = \dfrac {d} {d a} \, f(a)$
$\exists \; g_n(v_0) = \prod_{\,n = 1}^{\,n < N} {g_n} (F_n(v_0))$

Derivatives of convolution kernel values are the values themselves because they represent attenuation of the form $y = ax + b$.  This is true of first degree linear activation functions too.  The derivative normally used for ReLU (although the x = 0 case is actually undefined) is as follows:

$\dfrac {d} {dx} R(x) = {\begin{cases}x < 0 & 0\\x = 0 & 1\\x > 0 & 1 \end{cases}}$

The derivative of a max function used in max pool (although the u = v case is actually undefined) is as follows:

$\dfrac {d} {dt} M(u, v) = {\begin{cases}u < v & \frac {dv} {dt}\\u = v & \frac {dv} {dt}\\u > v & \frac {du} {dt}\end{cases}}$


Tuning the b parameter, ANFIS In order for the generalized bell membership function to retain its defined shape and domain, two restrictions must be placed on the b parameter: 1) b must be positive and 2) b must be an integer. Using backpropagation to tune the membership parameters (a,b and c in the bell), it appears to be possible that the correction to b will break one or both of these restrictions on b. Can someone please explain to me how we can use backpropagation to tune the b parameter (as well as a and c) without violating 1) and 2)?

After re-reading Jang's original (1993?) paper on ANFIS, I learned he recommended simply squaring the b-parameter to deal with the notion that b could be changed to a negative value when using back-propagation. While this solves the negative domain issue, the issue still remains that if b is a non-integer, then the bell function loses its intended shape. I suppose after squaring one could round to the nearest integer, but I suspect that doing so might hinder convergence. Perhaps a consideration is only tuning the a and c parameters using something like a genetic algorithm.


In what ways is the term "topology" applied to Artificial Intelligence? I have a only a general understanding of General Topology, and want to understand the scope of the term "topology" in relation to the field of Artificial Intelligence.

In what ways are topological structure and analysis applied in Artificial Intelligence?

In addition to the ways the term topology is itself used generically to describe the "shape" of various aspects of Machine Learning, the term appears in the field Topological Data Analysis:

  In applied mathematics, topological data analysis (TDA) is an approach to the analysis of datasets using techniques from topology. Extraction of information from datasets that are high-dimensional, incomplete and noisy is generally challenging. TDA provides a general framework to analyze such data in a manner that is insensitive to the particular metric chosen and provides dimensionality reduction and robustness to noise. Beyond this, it inherits functoriality, a fundamental concept of modern mathematics, from its topological nature, which allows it to adapt to new mathematical tools.

Some examples of its use in ML:

The ring of algebraic functions on persistence bar codes, Homology, Homotopy and Applications
Persistence Images: A Stable Vector Representation of Persistent Homology
Topological data analysis and machine learning theory
Topological Kernel Learning: Discrete Morse Theory is used to connect kernel machine learning with topological data analysis.


How to build a custom morphological analyser for translation system I want to build a machine translation system from English to Georgian. Georgian is a language similar (and simpler) to the Russian language. its syntax looks like base + suffix, only suffix changes, most of the time base is frozen, to describe the time the only suffix is changed. Unfortunately, I couldn't find a morphological analyser for the Georgian language, so could you link or provide useful resources to help me to build one? or can you give me some suggestions?

Huggingface has a Helsinki-NLP/opus-mt-ka-en repository with a Georgian (Ka) to English (en) model. A tokenizer_config.json is available


Is there a tool to convert from the brat standoff format to CoNLL-U format? I've been searching for a tool to convert from the brat standoff format to the CoNLL-U format, so that to use it as parsing corpus model to the spaCy library.

Can you help me?

The brat annotation tool has provided some useful scripts for converting the annotations format including standoff format to CoNLL. Please see this source code from brat GitHub repo for converting the .ann and .txt inputs (standoff format) to .conll file: https://github.com/nlplab/brat/blob/master/tools/anntoconll.py


What is the representational capacity of a learning algorithm? The definition I see for representational capacity is "the family of functions the learning algorithm can choose from when varying the parameters in order to reduce a training objective." (Goodfellow's Deep learning book).
However, to me this seems to be the same as the definition of the hypothesis space. Is the key difference the "in order to reduce a training objective" in that some functions may not be chosen in reducing a training objective? Or are these identical definitions.

Learning algorithms (some others too, like search) aim at generating functions that get as close as possible to the "shape" of the training data (so we can then feed values to the generated functions and get outputs like, say, a prediction).
In 2D, the "shape" may be easy to visualize. If the data in 2D seems to line up, learning algorithms generating linear/affine functions (e.g. y = ax + b), should fit fairly well. Their representational capacity extends to lines. If the data seems to form a parabola, a representational capacity bound to lines will do poorly. We then need more "capable" representations, which can cope with the quadratic terms.
So this should be what the "family of functions" Goodfellow's book refers to. The "training objective" should not be in the definition (to me), as a line fitting solution is unable to represent, say, a parabola, whatever the training objective is. However the book definition may mean a line can be fit to a parabola, strictly speaking, although it will do so very poorly.
The hypothesis space resembles the definition, perhaps (I have not checked it), but what matters is the "mindset". I would draw a parallel with prior and posterior distributions in Statistics, where we usually make some hypothesis on the shape of the distribution.
Concrete examples like linear regressions generate linear functions, as hinted by their names. Decision trees generate sets of linear functions, thus more complex and "capable". SVM generates functions depending on its kernel. The RBF kernel, for example, allows generating functions that can map quite complex, non-linear data "shapes". And arbitrary neural networks can map "arbitrary" data "shape" (easier written than actually done).


What is the goal of weight initialization in neural networks? This is a simple question. I know the weights in a neural network can be initialized in many different ways like: random uniform distribution, normal distribution, and Xavier initialization. But what is the weight initialization trying to achieve?
Is it trying to allow the gradients to be large so it can quickly converge? Is it trying to make sure there is no symmetry in the gradients? Is it trying to make the outputs as random as possible to learn more from the loss function? Is it only trying to prevent exploding and vanishing gradients? Is it more about speed or finding a global maximum? What would the perfect weights (without being learned parameters) for a problem achieve? What makes them perfect? What are the properties in an initialization that makes the network learn faster?

Is it trying to make sure there is no symmetry in the gradients?

The aim of weight initialization is to make sure that we don't converge to a trivial solution. That's why we have different kinds of initialization depending on the dataset type. So, Yes it is trying to avoid symmetry.

Is it trying to allow the gradients to be large so it can quickly converge?

The time it takes to converge, is I think a property of the optimizer and not of the weights initialization. Of course, the manner in which we initialize our weights matters but I think Optimization Algorithms contribute more towards convergence

What are the properties in an initialization that makes the network learn faster?

Glorot and Bengio believed that Xavier weight initialization would maintain the variance of activations and back-propagated gradients all the way up or down the layers of a network. Incidentally, when they trained deeper networks that used ReLUs, it was found that a 30-layer CNN using Xavier initialization stalled completely and didn’t learn at all. Thus, it depends on the particular problem at hand.


How to recognize sequence of digits in an image I am learning to program neural networks and others, and I would like to know how I can get the numbers that are in an image, for example, if I pass an image that has 123 written, get with my model that there are 123 written, I have tried to use PyTesseract is not very precise, and I would like to do it with a neural network, my current code is quite simple, it recognizes the digits of the mnist dataset such that:
import tensorflow as tf
from tensorflow.keras import Sequential, optimizers
from tensorflow.keras.utils import to_categorical
from tensorflow.keras.layers import Dense, Flatten, Conv2D, MaxPooling2D
import matplotlib.pyplot as plt

mnist = tf.keras.datasets.mnist
(train_images, train_labels), (test_images, test_labels) = mnist.load_data()

print('train_images.shape:', train_images.shape)
print('test_images.shape:', test_images.shape)
plt.imshow(train_images[0])

train_images = train_images.reshape((60000, 28, 28, 1))
test_images = test_images.reshape((10000, 28, 28, 1))

train_images = train_images.astype('float32') / 255
test_images = test_images.astype('float32') / 255

train_labels = to_categorical(train_labels)
test_labels = to_categorical(test_labels)

model = Sequential()

model.add(Conv2D(32, (5, 5), activation = 'relu', input_shape = (28, 28, 1)))
model.add(MaxPooling2D((2, 2)))

model.add(Conv2D(64, (5, 5), activation = 'relu'))
model.add(MaxPooling2D((2, 2)))

model.add(Flatten())

model.add(Dense(10, activation = 'softmax'))

model.summary()

model.compile(loss = 'categorical_crossentropy', optimizer = 'sgd', metrics = ['accuracy'])

model.fit(train_images, train_labels, batch_size = 100, epochs = 5, verbose = 1)

test_loss, test_accuracy = model.evaluate(test_images, test_labels)

print('Test accuracy:', test_accuracy)

but I would need to know how I can pass an image with a sequence of digits to it, and that it recognizes the digits in question, does anyone know how I could do it?

Your task is text recognition, however your code is for classification task. So you need to use different approach for that. You mentioned that you're going to give model 123 and get 123. But you can not do that with just convolutional networks. Images with text are sequential, so you need to use CRNN(Convolutional-Recurrent-Neural-Networks), LSTM(Long-Short-Term-Memory), BiLSTM(Bidirectional-LSTM). In most of the research papers there are convolutional networks are being used just for feature extraction stage. For prediction stage they used recurrent units, such as LSTM cells or RNN.


What research has been done in the domain of "Identifying sarcasm in text"? Identifying sarcasm is considered as one of the most difficult open-ended problems in the domain of ML and NLP.

So, was there any considerable research done in that front? If yes, then what is the accuracy like? Please also explain the NLP model briefly.

The following survey article by researchers from IIT Bombay summarizes recent advances in sarcasm detection: Arxiv link.

In reference to your question, I do not think it is considered either extraordinarily difficult or open-ended. While it does introduce ambiguity that computers cannot yet handle, Humans are easily able to understand sarcasm, and are thus able to label datasets for sarcasm detection.


How do I classify strings with possibly no meaning? I am quite new to text classification.

Using EAST text detection model, I get multiple strings that aren't words and most often have no meaning. For example, IDs, brand names, etc. I would like to classify them into two groups. Which models work the best and how should I preprocess the strings?  I wanted to use Word2Vec, but I think it only works with real words and not with arbitrary strings.

I would just use a dictionary. A simple list lookup would tell you whether it's a recognised word or not. As an added bonus you can add some basic language processing, eg to identify inflected forms without listing them in your dictionary. Or use regular expressions to recognise ID numbers. ML is not really the right tool here.


Reinforcement Learning (Fitted Q): Qn on Concept & Implementation I hope to get some clarifications on Fitted Q-Learning ('FQL').

My Research So Far

I've read Sutton's book (specifically, chp 6 to 10), Ernst et al and this paper.

I know that Q*(s,a) expresses the expected value of first taking action a from state s and then following optimal policy forever.

I tried my best to understand function approximation in large state spaces and TD(n).

My Questions

(1) Concept - Can someone explain the intuition behind how iteratively extending N from 1 until stopping condition achieve optimality (Section 3.5 of Ernst et al)? I have difficulty wrapping my mind around how this ties in with the basic definition of Q*(s,a) that I stated above.

(2) Implementation - Ernst et al gives the pseudo-code for the tabular form. But if I try to implement the function approximation form, is this correct:

Repeat until stopping conditions are reached:
     - N ← N + 1

     - Build the training set TS based on the the function ˆQN − 1 and on the full set of four-tuples F

     - Train algo on the TS

     - Use the trained model to predict on the TS itself

     - Create TS for the next N by updating the labels - new reward plus ( gamma * predicted values )

I am just starting to learn RL as part of my course and thus, there are many gaps in my understanding. Hope to get some kind guidance. Thanks in advance!

1): The intuition is based on the concept of value iteration, which the authors mention but don't explain on page 504. The basic idea is this: imagine you knew the value of starting in state x and executing an optimal policy for n timesteps, for every state x. If you wanted to know the optimal policy (and it's value) for running for n+1 timesteps in each location, this is now easy to compute. The optimal action from state x is whichever one maximizes the sum of the reward for this timestep (r) and the value of executing an optimal n-step policy from the state you'd end up in after (or expected value if the problem isn't deterministic).

In the approach of the paper, you're not going to compute either the policy or the value explicitly (probably because it's too expensive), so you just approximate the Q function for the n+1 problem.

IIRC, as long as your problem has a discounting factor and the error in your function approximation isn't too large, there are proofs (see Russell & Norvig's chapter on RL (18?)) that your policy will eventually stop changing in-between updates, and will be consistent with the policy for an infinite number of steps. Intuitively, this is because the discounting factor causes a series for the rewards to be convergent.

2): I think that's right. When you build the training set, use the actions suggested by the results for the $$Q_{n-1}$$ network. That's an approximation of the reward for starting in each state and running for n-1 steps with an optimal policy. Then you're learning an approximation of $Q_n$ from that, which looks right.


How important is true randomness in AI designs? How important is true (non-pseudo) randomness in Artificial Intelligence designs? Is there any chance that pseudo-randomness could be a barrier to more successful designs?

Randomness is typically the best one can do with ignorance, rather than a source of strength in its own right.

For example, the primary use of randomness in statistics is random assignment (A/B testing, randomized controlled trials, etc.). The reason to do this is to make the influence of confounders independent from the influence of the factor under investigation.

But randomness only works for this in expectation. If we actually knew what the confounders were, we could do a paired assignment (or a similar scheme) that ensured the various groups were matched as well as possible, instead of us just not knowing ahead of time which way the bias went.

There are some cases where pseudorandomness, rather than full randomness, will impair training AI designs. A simple example would be a case where you want to randomly initialize weights in a network where the number of parameters exceeds the periodicity of the RNG; this means that while you have as many possible networks as there are possible unique seeds, you can't actually visit the entire weight space that you wanted to sample over.

I don't think any of those cases are limiting factors, however. Having truly random stochastic gradient descent instead of pseudorandom stochastic gradient descent doesn't seem like it would make a serious difference in the trajectory of AI designs.


Metrics of quality of parameter space exploration Considering a black box optimization problem on non-linear, non-convex function where we want to minimize an objective function.

One way to assess the quality of an optimizer is to look at the best solution it finds. However that doesn't give us any information on how much of the parameter space the optimizer had to explore to come up with these solutions.

Therefore I was wondering if there are metrics quantifying how much of the parameter space is explored ?

It is somewhat common to measure the number of operations involved in the search. This is only really useful if you're doing scientific work, because the computational cost of measuring it accurately is quite high. For example, if you were using a GA that used tournament-based fitness selection, and wanted to compare it to one that used round-robin selection, counting the number of evaluations of individuals would be a good measure of total computational effort.

In Genetic Programming, it is fairly common to build the measurement of the total op count into the interpreter you write for the programs. You can then compare that directly to the number of evals times the length of the genomes for something like a GA.


Reasoning with incomplete information I was wondering if anyone can suggest a good framework for reasoning with incomplete information.

I have found Large Knowledge Collider but it appears dead for some time. Do you possibly have any other suggestions for a maintained project worth checking?

Since many comments are gravitating towards a different direction let me add one approach that I found a potentially good answer to my question - Rough Set Based Decision Trees.

I would hope there is more than only this approach... could you please help me identify them?

Firstly, before we commence I will recommend that you refer to similar questions on the network i.e https://stackoverflow.com/questions/39386936/machine-learning-with-incomplete-data , https://stats.stackexchange.com/questions/103500/machine-learning-algorithms-to-handle-missing-data

Row Deletion

If a particular row has more than 70% missing values, you can delete the row to handle the null values. This method is advised only when there are enough samples in the data set. The major disadvantage of this method is that it reduces the power of the model because it reduces the sample size.

Replacing With Mean/Median/Mode

We can calculate the mean, median or mode of the feature and replace the missing values with it. Another approach is to approximate it with the deviation of neighbouring values.

Although this approach adds variance to the data set, it yields better results compared to removing rows and columns.

KNN or Random Forest imputation

In this approach, the missing values of an attribute are imputed using existing attributes that are most similar to the attribute whose values are missing. The similarity of two attributes is determined using a distance function.

The advantage of this approach is that k-nearest neighbour can predict both qualitative and quantitative attributes. Additionally you do not need to create a prediction model for each attribute with missing data in the dataset.

Predicting the Missing Values

Prediction is one of the more sophisticated methods for handling missing data.
Using the features which do not have missing values, we can predict the null values with the help of a machine learning algorithm.

In this case, we divide our data set into two. One set with no missing values and another set with missing values. The first data set becomes the training data set of the model while the second data set with missing values is the test data set.

We then create a model to predict target variables based on other attributes of the training data set and populate the missing values of the test data set.(Sayali S 2016)

Caret or randomForestSRC packages in R

The R package randomForestSRC can handle missing data for a wide class of analyses i.e. regression, classification, unsupervised and multivariate (Ankur C 2014).
Additionally, the Caret R package can be used to predict missing data.

Reference : https://analyticsindiamag.com/5-ways-handle-missing-values-machine-learning-datasets/


How to quickly change hand-drawn shapes to symmetrical polished shapes? Given a hand-drawn shape, I'd like to generate the corresponding symmetrical polished shapes such as circle, rectangle, triangle,  trapezoid, square, parallelogram, etc.
A short video demonstration
Here below we can see a parallelogram, trapezoid, triangle and a circle.
I was wondering how can I transform it into symmetrical polished shapes?

At first, I tried a simple approach with traditional computer vision algorithms, with OpenCV (no neural networks were involved), by counting the number of corners, but it failed miserably, since there are many edge cases within a user's doodler.
So, I was thinking to delve into CNN specifically U-Net for segmentation.
Can somebody please give me some suggestions on how to approach this kind of problem? I'd like to read some relevant articles and code about this subject for getting a better grasp of this kind of problem.

From how it looks, the most reliable method to try out is using Hough transform.
The Hough transform can be used to detect e.g. lines and circles in images (depending on which variant you are using; in this case it would amount to a combination of variants for both lines and circles obviously).
So, given some input image, the Hough transform tells you what the line/circle parameters are that have created a line in the input image. For example, given a line, it would tell you the intersection with the $y$-axis and the $slope$ of the line detected in the image.
Then, you could use these parameter information to reconstruct lines and circles detected in the image.
The last remaining problem to be solved then is to check where a detected line starts and stops (since this is not obvious from line parameters like $m$ (=$slope$) and $b$ (=intersection with $y$-axis) in the equation $y = mx+b$ describing some line).
But for that, you could "walk" along a line in the image space and check where the line is present or not. Then, you can draw line segments in the reconstruction image when the corresponding elements are also present in the original image.
The problem with (C)NNs would be that they are sensitive to rotation and scale etc. You could of course take a tremendously large number of filters to account for shapes of different rotation and scale, but that would increase the demand for labeled training data again (which could of course be automatically be generated a priori in this simple case).
Anyway, I'd suggest checking out Hough transform. To get some feeling for it, there are lots of libraries available implementing it for Python or MatLab, for example.
For further information, check out Wikipedia or YouTube.


How does the repetition of features across states at different time steps affect learning? Let's say you are training a neural network in an RL setting, where the state (i.e. features/input data) can be the same for multiple successive steps (~typically around 8 steps) of an episode.

For example, an initial state might consist of the following values:

[30, 0.2, 0.5, 1, 0]

And then again the same state could be fed into the neural network for e.g. 6-7 times more, resulting in ultimately the following input arrays:

[[30, 0.2, 0.5, 1, 0],
 [30, 0.2, 0.5, 1, 0],
 ...,
 [30, 0.2, 0.5, 1, 0]]

I know that the value 0 in the feature set depicts that the weight for this feature results in insignificant value.

But what about the repetition of values? How does that affect learning, if it does at all? Any ideas?

Edit: I am going to provide more information as requested in the comments.

The reason I did not provide this information in the first place, is because I thought there would be similarities in such cases across problems/domains of application. But it is also fine to make it more specific.

The output of the network is a probability among two paths. Our network has to select an optimal path based on some gathered network statistics.
I will be using A3C, as similar work in the bibliography has made progress.
The reason the agent is staying in the same state is the fact that the protocol can also make path selection decisions at the same time, without an actual update of network statistics. So in that case, you would have the same RTT for instance.

i. This is a product of concurrency in the protocol

ii. It is expected behavior

In RL, neural networks may intuitively be thought of as using the input features as a representation that "identifies" the input state (or input state + action pair). Think back to the "tabular" RL setting that most people first study when they learn about RL. In tabular RL, you have a table of values (state values $V(s)$, or state-action values $Q(s, a)$), with unique entries in the table for every state. Such a table can perfectly identify states or, in other words, perfectly disambiguate different states.

In a non-tabular, function approximation setting, with function approximators such as Neural Networks, you can generally no longer uniquely identify every single state. Instead, you use approximate representations of these states, and the approximation implies that it's possible that you have multiple different states that look identical; they have identical input features. This is the case you're dealing with. Now, you specified explicitly that these multiple states with identical representations / input features follow each other up immediately in a single episode, but I don't think this detail is particularly important. You'd have exactly the same problems if these different states with identical representation showed up at different times within an episode. The only problem that you really have is a disambiguation problem: you don't know how to disambiguate these states, since they look identical to the network.

How significant that problem is depends on your domain. Based on your domain knowledge, do you expect the optimal action, or the optimal values, to be kind of similar in all these states that have identical features? If so, no problem! Your network already thinks they're the same anyway, so it will learn that the same actions / same values are the best in those states. But do you expect the optimal actions / true value functions to be wildly different in these states despite the fact that a network can't disambiguate them? In this case, the problem will be more severe because you can't realistically expect your network to learn the optimal actions / value functions for all these different states. At best, it can learn a weighted average among them (weighted by how commonly they occur in your training episodes).


Is greedy layer-wise pretraining obsolete? I was looking into the use of a greedy layer-wise pretraining to initialize the weights of my network.

Just for the sake of clarity: I'm referring to the use of gradually deeper and deeper autoencoders to teach the network gradually more abstract representations of the input one layer at the time.

However, reading HERE, I read:

  Nevertheless, it is likely better performance may be achieved using modern methods such as better activation functions, weight initialization, variants of gradient descent, and regularization methods.

and

  Today, we now know that greedy layer-wise pretraining is not required to train fully connected deep architectures, but the unsupervised pretraining approach was the first method to succeed.

My question is then: if I'm building a network already using "modern" techniques, such as ReLU activations, batch normalization, adam optimizers, etc, is the good-ol' greedy layer-wise pretraining useless? Or can it still provide an edge in the initialization of the network?

It depends. It could give you a boost or it could not.

Intuitively I would expect it to actually hurt performance if the network is initialized correctly (I think the optimizer is less of a bottleneck because they will have the same effect in both approaches).

Ideal World: We optimize the network as a whole to gain better course grained features over the sequential layers of the encoder

Reality years ago: Deep nets have trouble in information propagation either forward or backwards (ex: vanishing/exploding activation and vanishing/exploding gradient).

solution: Break up the training into iterative schemes that don't require backward information to propagate far at each optimization step

Cons: Each step is looking for a greedy solution, rather than a deep one.

Reality today: Depending on the domain, there are various publications discussing how to circumvent this issue (ex: Residual networks, He initialization, fixup initialization, batchnorms, different activation functions, etc...)

solution: We can train deep AEs without sequential layerwise training and achieve usually better results, because the model and optimization scheme allow for deep representations to form.

I hope this  helped give some form of intuition of the matter.


Ensemble Learning using Convolutional Neural Networks I have created 22 different Convolutional neural networks that all test for the presence of unique objects in an image (each one of the classifiers is unique).

Each sample in the test set has the output of a 22-long vector that looks something like this [0, 1, 1, 0, 0, 1, ..., 1], the binary nature of the vector representing the presence/absence of specific objects.

I have implemented this already in keras and reach around 97% accuracy avg for the 22 models. Is there any specific ensemble methods that can allow me to combine all 22 classifiers?

I am new to AI but this is something I can think of. There might be other much better ways. Or even functions in scikit learn to do it

1) create a list of all the 22 models

2) iterate over the models one by one and use model.predict() for each model and store the hotencoded output to another list or numpy array.

3) Take average of the output list or numpy array.

4) since the output is a vector of 0,1 it is possible to get decimals in the output after taking avg. Round it off using the basic rules to either 0 or 1.

5) If your CNNs are very deep like inception v3, densenet etc. You might run into memory issues while loading all the 22 model's weights into the memory at once. So you can iteratively load the models in small fixed batches and use model.predict() on each model in the batch append the outputs to a list. and then clear them off the memory before loading another batch of models.

This is just my idea. I might be completely wrong also.


Did the Facebook robots both want everything but the balls? According to this article, two Facebook ai's had the following "creepy" negotiation over a transaction:

Bob: i can i i everything else . . . . . . . . . . . . . .
Alice: balls have zero to me to me to me to me to me to me to me to me to
Bob: you i everything else . . . . . . . . . . . . . .
Alice: balls have a ball to me to me to me to me to me to me to me
Bob: i i can i i i everything else . . . . . . . . . . . . . .
Alice: balls have a ball to me to me to me to me to me to me to me
Bob: i . . . . . . . . . . . . . . . . . . .
Alice: balls have zero to me to me to me to me to me to me to me to me to
Bob: you i i i i i everything else . . . . . . . . . . . . . .
Alice: balls have 0 to me to me to me to me to me to me to me to me to
Bob: you i i i everything else . . . . . . . . . . . . . .
Alice: balls have zero to me to me to me to me to me to me to me to me to

If we first look at Bob's, he's asking for what he wants by proposing that he have all items but one and not revealing which is the one he doesn't want.  By design or by chance, this is actually a strong negotiating technique because he reveals nothing other than the fact he is willing to come to an agreement.
Alice appears to either ask for no balls, or to say they have no value to her and then obsess about things coming to her, perhaps iterating on the other items.  She would appear to be the better communicator because she at least gets to the point of saying "have a ball".  But she refuses to give anything away beyond that.
But Bob seems to stand firm saying he wants "everything else" but not giving away what he is willing to go without.
Perhaps these two are not such bad negotiators after all?

Not sure if you've gone through FAIR's blog post about these negotiating bots and the research behind them.

  Did the Facebook robots both want everything but the balls?

Yes. You are right.  You can refer to the gif in FAIR's blog post. Here, the chat goes on between 2 bots, where one wants only balls, and the other offers 1 ball and a hat. And this bot re-iterates that it wants only the balls. And they negotiate for some time till they reach a consensus.

  Perhaps these two are not such bad negotiators after all?

The fact that the FAIR labs have open-sourced the code means that they came a fairly long way in this research.  They also published the research paper. The example on the repo's README also cites the balls-and-hats negotiation example.


Whats the name of the value that you add or subtract from a minimax tree node? I am coding a tic-tac-toe program that demonstrates reinforcement learning. The program uses minimax trees to decide its moves. Whenever it wins, all the nodes on the tree that were involved in the game have their value increased. Whenever it loses, all the nodes on the tree that were involved in the game have their value decreased, etc. What is the name of the value that each node is decreased by?

I think you mean the leave nodes only which are changed. The other nodes in the tree are calculated during calculating the best move with this tree. The values at the leaves are called utility values in Russel and Norvig's "Artificial intelligence: a modern approach". Some times it is called heuristic value; see https://en.wikipedia.org/wiki/Minimax.


Can you convert a MDP problem to a Contextual Multi-Arm Bandits problem? I'm trying to get a better understanding of Multi-Arm Bandits, Contextual Multi-Arm Bandits and Markov Decision Process.
Basically, Multi-Arm Bandits is a special case of Contextual Multi-Arm Bandits where there is no state(features/context). And Contextual Multi-Arm Bandits is a special case of Markov Decision Process, where there is only one state (features, but no transitions).
However, since MDP has Markov property, I wonder if every MDP problem can also be converted into a Contextual Multi-Arm Bandits problem, if we simply treat each state as a different input context (features)?

The main difference between an MDP and contextual bandit setting is time steps and state progression. If those are important to the problem you want to solve, then it is not possible to convert.
Essentially MDPs are a strict generalisation of contextual bandits. You can model a CB as an MDP but not vice-versa.
In some very specific cases you can convert MDP to CB - any one of these situations means that the MDP can be simplified to CB, and then you could use bandit solving algorithms to optimise it:

When there is only one time step for an episodic problem.

When the discount factor is zero.

When state transition rules are completely independent of action choice, but reward is not.


Handling imbalanced data with multiple targets I have the model which has 3 outputs (it is a regression task, I have the angle of the steering wheel, brake and acceleration). I can divide my values to some smaller bins and in this way I can change this into classification problem. I can balance data to have the same number of data points in each bin.
But now I wonder how to balance this data correctly.
I found some good resources and libraries
imbalanced-learn | Python official documentation
multi-imbalance | Python official documentation
Multi-imbalance | Poznan University of Technology
But to my understanding, these algorithms can deal with imbalanced data (in normal and multi class classification) only if you have one output.
But I have 3 outputs. And these outputs can be correlated somehow.
How to balance them correctly?
I thought about 2 ideas:

Creating tuples consist of 3 elements and balancing in such a way that you have the same number of different tuples
But you can have this situation:
(A, X, 1), (A, Y, 2), (A, Y, 3), (B, Z, 3)
These tuples are different, but you can see that we have a lot of tuples with the value A at first position. So the data is still quite imbalanced.

Balancing data iteratively considering only one column at a time. You balance first column, then you balance second column etc.

Are these ideas good or not? Maybe there are some other options for balancing data if you have multiple targets?

You can try weighting your training data instances. So, if for example class A has proportion $p_A$, you weight every instance of class A with $1/p_A$. There also exists more sophisticated approaches to train on unbalanced data, such as generating synthetic samples to create a balanced dataset and so on. You can start learning more here.


Can policy iteration use only the immediate reward for updates? Is it still a policy iteration algorithm if the policy is updated optimizing a function of the immediate reward instead of the value function?

Is it still a policy iteration algorithm if the policy is updated optimizing a function of the immediate reward instead of the value function?

Technically yes.

The value update step in Policy Iteration is:

$$v(s) \leftarrow \sum_{r,s'}p(r,s'|s,\pi(s))(r + \gamma v(s'))$$

The discount factor $\gamma$ can be set to $0$, making the update:

$$v(s) \leftarrow \sum_{r,s'}p(r,s'|s,\pi(s))r$$

However, there are two key details that are important, and make this a technically yes, not some alternative way of solving problems:

Changing discount factor $\gamma$ changes what it means for an agent to act optimally. Setting it to zero means that the agent will prioritise only its immediate reward signal, and make no long-term decisions at all. This would be useless for instance if the task was to escape a maze in minimum time.
Technically there is still a value function being updated. The function $v(s)$ is still the expected future reward, just we have set it to only care a very short step into the future. So short that it doesn't care what the value of the next state is, so the next state does not appear in any updates.
Due to the lack of bootstrapping between states, all the data for optimal behaviour is already available in the reward distribution. So the entire MDP can be solved with a single sweep through all the states. Or it could just be solved on-demand using $\pi(s) = \text{argmax}_a[\sum_{r,s'}p(r,s'|s,a)r]$ for any state, making a policy iteration process redundant.

However, with these caveats in mind, yes this is still policy iteration. It is the same update process, just with a particular choice of one of the parameters.


Are biological neurons organized in consecutive layers as well? I'm now reading a book titled Hands-On Machine Learning with Scikit-Learn and TensorFlow and in the Chapter 10 of the book, the author writes the following:

  The architecture of biological neural networks (BNN)4 is still the subject of active research, but some parts of the brain have been mapped, and it seems that neurons are often organized in consecutive layers, as shown in Figure 10-2.

However there seems to be no link to any research there. And the author didn't say it assertively given that he used "it seems that neurons are often organized in consecutive layers".

Is this true and how strongly is it believed? What research is this from?

Really short answer: yes

Slightly longer answer: kinda

Long answer:

Convolutional neural networks (CNNs), which are now a standard in image processing models, were inspired from work done by Hubel and Wiesel in the 1950-60s. They showed that the visual cortexes of cats and mokeys contain neurons which individually respond to small regions of the visual field.

To give some background, we have to first start from the rods and cones in eyes. These photosensitive cells are connected to a few layers of cells before even leaving the retina via ganglion cells.

These ganglion cells are then connected to several regions of the brain but primarily the Occipital lobe located at the back of the brain. The Occipital lobe is responsible for visual processing and is separated into cortical layers, the first named V1 which is the primary visual area. Most of the work by Hubel and Wiesel involved cells in V1 and showed how these cells were sensitive to orientation and color from their respective receptive areas on the retina.

The cells in V1 are connected to the cells in V2 which are sensitive to even more specific stimulus such as movement with orientation and this trend of specific sensitivity continues up from V2 to higher regions in the brain.

This layered approach to vision has been heavily exploited in CNNs, so much so that when the sensitivity of neurons in trained CNNs is displayed, similar responses (orientation) are found.

There is clear evidence of layers in biological optical systems and similarly layered structures in the other senses. Although there are many connections between different brain structures, the main structure of layers in the brain has helped understand what different areas of the brain do and has helped inspire many (if not all) advances in neural network research.


Are leaf nodes included in the calculation of average branching factor for search trees? In the search tree below, there are 11 nodes, 5 of which are leaves. There are 10 branches.

Is the average branching factor given by 10/6, or 10/11?

Are leaves included in the calculation? Intuitively, I would think not, since we are interested in nodes with branches. However, a definition given to me by my professor was "The average number of branches of all nodes in the tree", which would imply leaves are included.

From Wikipedia:

  In computing, tree data structures, and game theory, the branching factor is the number of children at each node, the outdegree. If this value is not uniform, an average branching factor can be calculated.

Outdegree meaning - In case of directed graphs, number of edges going into a node is known as in-degree of the corresponding node and number of edges coming out of a node is known as out-degree of the corresponding node.

You forgot the outdegree part. In AI we generally draw directed graphs from one state to another, and outdegree is the number of paths leaving a particular node. In your graph direction is not given. Also your graph is not symmetrical, but you can still find out the branching factor (with a little difficulty) of non-symmetrical directed graphs as given here. So technically  your conclusion is correct about leaf nodes not being counted (assuming they are the last state from which no other state can be reached - dead end). Hope this helps!


How much can/should the non-player character know about the game's world? I'm about to write a non-player character (NPC). I wonder how much the AI should know about the game's world. So, my question isn't about the amount of training data the AI has to collect. I'm interested in how much the AI is allowed to know about what's going on in the game's world.
For example, can (shall) it have knowledge about the build queue of the player?
To provide more details: while a human plays a game against another human, not all information of what the opponent is doing is available (e.g. the queue of the units your opponent is building). This could give you an advantage (so that you can prepare for a rush, when he's building many cheap units). Theoretically, an NPC could access and make use of that knowledge and, in addition, spare resources for scouting/spying/exploring.
But is this the way of constructing an NPC AI? Or should this data also be restricted? I have never done anything like this before.
I don't know where to ask else wise or what more information I could provide. So, if something in my question is unclear or unfit, please let me know what exactly.

Art of NPC creation
I'm assuming this is a standard game, not a game theory application. These AIs tend to be far simpler in theory than actual artificially intelligent agents which are used to solve real world problems. The challenge of building games is that there are few right answers. A game NPC opponent could know practically nothing of the player and be guided by random world exploration activating certain characteristics (attack, strategy) whenever a human is in range or on the other end could know basically everything and have some limiting factors built into the code which reduces their challenge level to the player. This is the art aspect of gaming design. NPCs with a high level of complexity could learn from their interactions and build a "pattern" with some internal reward scoring system for success (similar to reinforced learning). This would represent a very challenging game NPC, especially if the strategy changes upon failure. Think about who will be playing your games, the audience that you would tend to draw, and hone the NPC challengers to them. Hardcore gamers deserve a challenge, and hobby gamers deserve a chance to win. Where that balance between rewarding game experience and challenging game experience lies depends on the 'feel' which you are cultivating as the game designer. You mentioned resources and exploration as elements of the game. For exploration types of games, you may rely on environmental interactions to offset player interactions. A distracted NPC (gathering resources) is less likely to heavily attack the human player unless this player enters the perimeters of the NPC base or scouting area. This may work to keep the gameplay balanced. Keep in mind that some limitations for your NPCs must be absolute, or the game will experience unexpected behavior (bugs). A completely unrestricted NPC is a liability. If the NPC goes too far from the player or gets stuck, it completely ruins the feel of your game.


How can I manually calculate the output a specific neural network given some input? I have the following problem, which I am unable to solve.

A neural network with the following structure is given: 1 input neuron, 4 elements in the hidden layer, 1 output neuron.
The output neuron is bipolar, the neurons in the hidden layer are linear.
The weights between the input neuron and the neurons in the hidden layer have the following values: $w_{11} = -3, w_{12} = 2, w_{13} = -1, w_{14} = 0.5$, while between neurons in the hidden layer and the starting neuron:: $w_{21} = +2, w_{22} = -0.5, w_{23} = -3, w_{24} = +1$ (no threshold input in both layers).
What will the network response be like if the number 3 is given to the input neuron?

Given that the neurons are linear in the hidden layer of the neural network, so the output is just the dot product of the weights and the input. To put things in perspective, generally, we use an activation function (sigmoid, signum, etc.), which is applied to the dot product.

Hence, for an input of $3$ inputs to node 1 of hidden layer is $-3 * 3 = -9$, to node 2 is $2 * 3= 6$ to node 3 is $-1 * 3 = -3$ to node 4 is $0.5 *3 = 1.5$ (basically, I have performed dot product). Since neurons are linear, no activation function is applied and is directly propagated to the next layer, the output layer.

Contribution of all the hidden nodes to the output layer is the dot product of the weights with the output of the hidden layer that is $9*2 + -0.5*6 + -3*-3 + 1*1.5 = -10.5$ (check for any calculation errors). And, finally, the output layer is bipolar hence an activation function (probably sigmoid) is applied to it. Since for sigmoid function is smaller than $0.5$ if $z<0$, hence the output will be $0$, as $z = -4.5$, as per convention.


Is it possible to manage the evolution of super-intelligent AI? Post singularity AI will surpass human intelligence. The evolution of AI can take any direction, some of which may not be preferable for humans. Is it possible to manage the evolution of super-intelligent AI? If yes, how? One way I can think of is following. Instead of having a mobile AI like humanoid, we can keep it immobile, like a box, like current super computers. It can be used to solve problems of maths, theoretical science etc.

Assuming super-intelligence is possible, the answer is probably yes and no.

Yes in Kurzweil-like scenarios, where super-intelligence is an extension of human beings by technology (we are already in to some extent). Then control follows, as super-intelligence depends on us. It would extend our capabilities, such as speed of processing, extent of processing, etc. Even then control is debatable, as a remote-controlled killing machine would be part of a super-intelligent organism, partially human "controlled", partially autonomous.

No in "Future of Life Institute"-like scenarios, where super-intelligence is independent from humans. The thinking is simple: What can we hope to do facing someone way more intelligent? The usual parallel is to compare this scenario with the arrival of the "developed" conquistadors in early America. Gunpowder vs. mere raw strength and arrows.


Reinforcement learning for robotic motion planning - Problem statement ideas I am a first-semester grad student in Robotics and have taken a course on machine learning for robotics. I am completely new to machine learning.

I am to select and execute a problem statement on my own as a part of the course. I have selected the following problem statement -

"Reinforcement learning for mapless navigation of mobile robots" based on this research. The goal is to develop a mapless motion planner which enables a robot to navigate by avoiding obstacles.

Since I am completely new to Machine learning and AI, I am not able to gauge whether the problem statement is challenging enough for a beginner to execute in a timeframe of 8 weeks? (given that I can dedicate around 6 hours a week)

I am planning to code in MATLAB since I am highly comfortable with MATLAB

Also, please leave any suggestions/ modifications to refine my approach and have a better understanding in this area.

Thank you!

I think that this may be too difficult for only a few weeks of work. There are a few reasons why and although all of the reasons are themselves learning opportunities, it may cost you more time than you have.

First off, Robots are hard to work with. Ask anyone who has worked with robots and they will say that have broken their heart at least once. This is because either the robot was a custom robot which needs specific skills (soldering, 3d printing, etc) if something breaks (and it will) or it's a purchased robot platform which doesn't have the control you want or doesn't have good documentation.

Secondly, Machine learning is a very interesting and broad field and there is a lot of literature one should get a background on to help with their projects. Because of this, it might be overwhelming to take all of that information in while having to deal with a robot.

I don't want to dissuade you in this research area though. It is very interesting and has many subproblems like dynamic environments, multilevel environments, etc. But given the time you have, it might be better to set yourself up for success. Perhaps something which lets you do a literature review about the problem anyway.
Perhaps a more attainable goal in that time while still using a robot is: Predicting wall collisions using temporal difference learning.

If you agent can predict when a wall is coming, clearly they will be able to avoid them too but it's a very reasonable first step.

Additionally, talking to the professor of the course or your supervisor (if you have one) will also help you decide.


Why do we set offset (0.5) in single shot detector? In the paper SSD: Single Shot MultiBox Detector, under section 2.2 - (4), why do we add an offset of 0.5 to x, y in generating the anchor boxes across feature maps?

The integer coordinates refer to the top-left corner of a pixel. Adding 0.5 to both x and y gives you the center location of a pixel instead.


What is the meaning of "easy negatives" in the context of machine learning? What does the term "easy negatives" exactly mean in the context of machine learning for a classification problem or any problem in general?

From a quick google search, I think it means just negative examples in the training set.

Can someone please elaborate a bit more on why the term "easy" is brought into the picture?

Attached picture with black underline:

OK, I think I understood what this means. Hard and easy negatives are ones which have a relatively large and small values for the loss function respectively.


What fast loss convergence indicates on a CNN? I'm training two CNNs (AlexNet e GoogLeNet) in two differents DL libraries (Caffe e Tensorflow). The networks was implemented by dev teams of each libraries (here and here)

I reduced the original Imagenet dataset to 1024 images of 1 category -- but setted 1000 categories to classify on the networks.

So I trained the CNNs, varying processing unit (CPU/GPU) and batches sizes, and I observed that the losses converges fastly to near zero (in mostly times before 1 epoch be completed), like in this graph (Alexnet on Tensorflow):

In portuguese, 'Épocas' is epochs and 'Perda' is loss.

The weight decays and initial learning rate are the same as used on models that I downloaded, I only changed the dataset and the batch sizes.

Why my networks are converging this way, and not like this way?

Ok, so the fact that you always give the same category means the network only has to output the same value for any given input. This is exceedingly easy to learn (all the weights always shift in the same directions) and this make this graph.

Once you have more categories (try 10 for example), you'll see the graph will be closer to expected.


House price inflation modelling I have a data set of house prices and their corresponding features (rooms, meter squared, etc). An additional feature is the sold date of the house. The aim is to create a model that can estimate the price of a house as if it was sold today. For example a house with a specific set of features (5 rooms, 100 meters squared) and today's date (28-1-2020), what would it sell for? Time is an important component, because prices increase (inflate over time). I am struggling to find a way to incorporate the sold date as a feature in the gradient boosting model.
I think there are a number of approaches:

Convert the data into an integer, and include it directly in the model as a feature.
Create a separate model for modelling the house price development over time. Let's think of this as some kind of an AR(1) model. I could then adjust all observations for inflation, so that we would get an inflation adjusted price for today. These inflation adjusted prices would be trained on the feature set.

What are your thoughts on these two options? Are there any alternative methods?

The sold date is a feature like any other. You can do this as follow. I am assuming the features are in a pandas data frame  called df where the column date is called date. Easiest way is to use the pandas to_datetime function. Documentation is here.
def encode_dates(df, column):
    df = df.copy()
    df[column] = pd.to_datetime(df[column] )
    df[column + '_year'] = df[column].apply(lambda x: x.year)
    df[column + '_month'] = df[column].apply(lambda x: x.month)
    df[column + '_day'] = df[column].apply(lambda x: x.day)
    df = df.drop(column, axis=1)
    return df
df=encode_dates(df. 'date')

This function will modify the df data frame. It will create 3 new columns labeled
date year, date month and date day and it will remove the date column from the data frame.
Now these new columns along with the other features can be used to train your model.


How to calculate the entropy in the ID3 decision tree algorithm? Here is the definition of the entropy
$$H(S)=-\sum_{x \in X} p(x) \log _{2} p(x)$$
Wikipedia's description of entropy breaks down the formula, but I still don't know how to determine the values of $X$, defined as

The set of classes in $S$

and $p(x)$, defined as

The proportion of the number of elements in class $x$ to the number of elements in set $S$.

Can anyone break this down further to explain how to find $p(x)$?

Suppose you have data:

color  height  quality
=====  ======  =======
green  tall    good
green  short   bad
blue   tall    bad
blue   short   medium
red    tall    medium
red    short   medium

To calculate the entropy for quality in this example:

X  = {good, medium, bad}
x1 = {good}, x2 = {bad}, x3 = {medium}

Probability of each x in X:

p1 = 1/6 = 0.16667
p2 = 2/6 = 0.33333
p3 = 3/6 = 0.5

for which logarithms are:

log2(p1) = -2.58496
log2(p2) = -1.58496
log2(p3) = -1.0

and therefore entropy for the set is:

H(X) = - (0.16667 * -2.58496) - (0.33333 * -1.58496) - (0.5 * -1.0)
     = 1.45915

by the formula in the question.

Remaining tasks are to iterate this process for each attribute to form the nodes of the tree.


OpenAI Gym: Multiple actions in one step I'm trying to design an OpenAI Gym environment in which multiple users/players perform actions over time. It's round based and each user needs to take an action before the round is evaluated and the next round starts. The action for one user can be model as a gym.spaces.Discrete(5) space.
I want my RL agent to make decisions for all users. I'm wondering how to take multiple actions before progressing time and calculating the reward.

Basically, what I want is:

obs = env.reset()
user_actions = []
for each user:
    user_actions.append(agent.predict(obs))
obs, reward, done, _ = env.step(user_actions)

So the problem is that I don't immediately know the reward after getting an action since I need to collect all actions before evaluating the round.

I could of course extend actions to include actions of all users in one go. But this would be problematic if I have a really large number of users or it even changes over time, right?

I found these two (1, 2) related questions, but they didn't solve my problem.

What I was looking for is multi-agent RL, where I have multiple RL agents, each controlling actions of one user. All RL agents/user make an action in each environment step and each get their own reward.
I represent my RL agents' actions as dict, containing the RL agent ID as key and its action as value. The different agents may either use the same or a different policy and use this policy and each their own observations (also stored as dict) to compute their actions.
action = {}
for agent_id, agent_obs in obs.items():
    # get the policy of the current agent
    policy_id = self.config['multiagent']['policy_mapping_fn'](agent_id)
    # use the policy and the agent's observations to compute its next action
    action[agent_id] = self.agent.compute_action(agent_obs, policy_id=policy_id)

My environment's step(self, action) function expects action to be such a dict and knows how to handle it.
It applies all actions in the dict before calculating each agent's reward and progressing time in the environment.
So basically, treating observations, actions, rewards (and info) as dicts solves the problem for me.
For the multi-agent RL approach, I used PPO and the Ray RLlib framework.


In a CNN, does each new filter have different weights for each input channel, or are the same weights of each filter used across input channels? My understanding is that the convolutional layer of a convolutional neural network has four dimensions: input_channels, filter_height, filter_width, number_of_filters.  Furthermore, it is my understanding that each new filter just gets convoluted over ALL of the input_channels (or feature/activation maps from the previous layer).
HOWEVER, the graphic below from CS231 shows each filter (in red) being applied to a SINGLE CHANNEL, rather than the same filter being used across channels.  This seems to indicate that there is a separate filter for EACH channel (in this case I'm assuming they're the three color channels of an input image, but the same would apply for all input channels).
This is confusing - is there a different unique filter for each input channel?

This is the source.
The above image seems contradictory to an excerpt from O'reilly's "Fundamentals of Deep Learning":

"...filters don't just operate on a single feature map. They operate
on the entire volume of feature maps that have been generated at a
particular layer...As a result, feature maps must be able to
operate over volumes, not just areas"

...Also, it is my understanding that these images below are indicating a THE SAME filter is just convolved over all three input channels (contradictory to what's shown in the CS231 graphic above):

The following picture that you used in your question, very accurately describes what is happening. Remember that each element of the 3D filter (grey cube) is made up of a different value (3x3x3=27 values). So, three different 2D filters of size 3x3 can be concatenated to form this one 3D filter of size 3x3x3.

The 3x3x3 RGB chunk from the picture is multiplied elementwise by a 3D filter (shown as grey). In this case, the filter has 3x3x3=27 weights. When these weights are multiplied element wise and then summed, it gives one value.

So, is there a separate filter for each input channel?

YES, there are as many 2D filters as number of input channels in the image. However, it helps if you think that for input matrices with more than one channel, there is only one 3D filter (as shown in the image above).

Then why is this called 2D convolution (if filter is 3D and input matrix is 3D)?

This is 2D convolution because the strides of the filter is along the height and width dimensions only (NOT depth) and therefore, the output produced by this convolution is also a 2D matrix. The number of movement directions of the filter determine the dimensions of convolution.

Note: If you build up your understanding by visualizing a single 3D filter instead of multiple 2D filters (one for each layer), then you will have an easy time understanding advanced CNN architectures like Resnet, InceptionV3, etc.


Neural networks with internal dynamics in the state-space form Neural networks with feedback (Hopfield, Hamming, etc.) differ from ordinary neural networks (multilayer perceptrons, etc.), which turns them into a dynamic element with its own internal dynamics (if we consider them as a separate dynamic link). The following question naturally arises - is it possible to represent them in the form of state spaces?

Nuance is that feedback is created by introducing a delay element, which means recording a neural network exclusively in a discrete form. Is continuous recording possible? What acts as matrices A, B, C, D? How does the presence of nonlinear activation functions affect?
The only more or less useful information that I managed to find is in this article:

On neural networks in identification and control of dynamic systems. 3.2 Paragraph. Page 8

But my assumptions are only confirmed there, which does not clarify the situation.

In general, if someone has come across this and can assist in studying the issue, please share links, possibly examples, etc.

I think that the book "Neural Networks and Learning Machines" of Haykin can help you. In his book the chapter 13 is about neural dynamics, and there are some examples of how analise the dynamics of network.


What should the dimension of the input be for text summarization? I am trying to build a model for extractive text summarization using keras sequential layers. I am having a hard time trying to understand how to input my x data. Should it be an array of documents with each document containing an array of sentences? or should I further break it down to each sentence containing an array of words?

The y input is basically a binary classification of each sentence to check whether or not they belong to the summary of the document.

The first layer is an embedding layer and I'm using 100d Glove word embedding.

P.s: I am new to machine learning.

Briefly:

I think what you are looking for is an RNN network (Either LSTM or GRU) with the many-to-many topology.

Explanation:

Clearly your input is the sentences (or to be more precise, the an embedding of your sentences, because you cannot feed the raw text to the network). then for each sentence you want to assign a value, which means for n inputs, you need n outputs. This is the many-to-many architecture.

Moreover, you might want to check the Bi-directional LSTM for your study. Not relevant to your question, but worth mentioning.

For more information, refer to this


What does the term $|\mathcal{A}(s)|$ mean in the $\epsilon$-greedy policy? I've been looking online for a while for a source that explains these computations but I can't find anywhere what does the $|A(s)|$ mean. I guess $A$ is the action set but I'm not sure about that notation:
$$\frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} Q^{\pi}(s, a)+(1-\varepsilon) \max _{a} Q^{\pi}(s, a)$$
Here is the source of the formula.
I also want to clarify that I understand the idea behind the $\epsilon$-greedy approach and the motivation behind the on-policy methods. I just had a problem understanding this notation (and also some other minor things). The author there omitted some stuff, so I feel like there was a continuity jump, which is why I didn't get the notation, etc. I'd be more than glad if I can be pointed towards a better source where this is detailed.

This expression: $|\mathcal{A}(s)|$ means

$|\quad|$ the size of

$\mathcal{A}(s)$ the set of actions in state $s$

or more simply the number of actions allowed in the state.
This makes sense in the given formula because $\frac{\epsilon}{|\mathcal{A}(s)|}$ is then the probability of taking each exploratory action in an $\epsilon$-greedy policy. The overall expression is the expected return when following that policy, summing expected results from the exploratory and greedy action.


Why do we need artificial intelligence? We seem to be experiencing an AI revolution, spurring advancement in many fields.

Please explain, at a high level, the uses of artificial intelligence and why we might need it.

The question, "Why do we need artificial intelligence?" is quite to the point.  Technically, the answer is, "No reason."  If we needed artificial intelligence, then we would have become extinct over the last 50,000 or more years we've been a species with human intelligence, so we want it.

We do want it, and there are benefits.  Some claim there are risks too, which is logical.  We should be open to all views.  Some of them may be spot on, and others may be without merit.

One list of benefits already seen might include these, with most beneficial on top.

Deeper interest in what exactly we mean when we say someone or some thing is intelligent
Revisiting of the validity of the g-factor belief
Revised interest in parallel computing architecture
Heightened awareness of the distinction between fake and authentic
Improved use of an interest in probability and statistics

These are further potential benefits that may also emerge.

Young students taking mathematics more seriously than hacking
The elimination of circular, wasteful job functions
More leisure time for families to enjoy together
Improved economic efficiency
Better planning regarding the use and preservation of natural resources

These are the risks from highest to lowest.

Possibly accidentally causing the emergence of an uncontained and potentially dangerous digital entity
Additional nihilism (belief that nothing matters) in our culture, which could emerge if the last refuge of human pride is overrun by smarter artificial systems
People losing their jobs, which may have only a temporary impact, if the AI does quality work, but the transition may be painful and destructive


How to incentivise snake to go straight to apple? I have made a Deep Q Network for the game snake but unfortunately, the snake exhibits some unwanted behavior. It generally does quite well but sometimes it gets stuck in an infinite loop that it can't escape and at the start of the game it takes a very long route to the apple rather than taking a more direct route.

The discount factor per time step is 0.99. The Snake gets a reward of +9 for getting an Apple and -1 for dying. Does anybody have any recommendations on how I should tune the hyperparameters/reward function to minimize this unwanted behavior?

I was thinking that reducing the discount factor may be a good idea?

Your network finds the infinite loop and notices that this has the best reward (0). This is probably because it hasn't found a path to eating the apple (through exploration).

Reducing the discount factor will only make the long term rewards less valuable. So it will learn eating the apple even slower.

I don't know what you are using as inputs for your network, but maybe changing your reward system could help. For example, you could give your network a reward if it advances in the direction of the apple. This way, your network will be encouraged to find the apple more than it is now.


Why is MSE used over other quadratic loss functions? So I was wondering, why I have only encountered square loss function also known as MSE. The only nice property of MSE I am so far aware of is its convex nature. But then all equations of the form $x^{2n}$ where $n$ is an integer belongs to the same family.

My question is what makes MSE the most suitable candidate among this entire family of curves? Why do other curves in the family, even though having steeper slopes, $(x >1) $, which might result in better optimisation, not used?

Here is a picture to what I mean where red is $x^4$ and green is $x^2$:

I can comment on several properties of MSE and related losses.

As you mentioned MSE (aka $l_2$-loss) is convex which is a great property in optimization in which one can find a single global optimum. MSE is used in linear and non-linear least squares problems which form the basis of many widely used statistical methods. I would imagine the math and implementation would be more difficult if one would use a higher-order loss (e.g. $x^3$) and that would also prove to be futile because MSE already possesses great statistical and optimization properties on its own.
Another important aspect, one wouldn't use higher-order loss functions in regression is because it would be extremely prone to outliers. MSE on its own would weigh the outliers much more than l1-loss would! And in real world data there is always noise and outliers present. In comparison l1 loss is more difficult in optimization, one reason for which is it's not differentiable at zero.

Other interesting losses you might want to read about are $l_0$ and $l_{inf}$ loss, all of which have their own trade-offs in optimization-sense.


Recommendations or resources for neural network/deep learning for time series application? I know there are quite a few good deep learning books out there, but most explain neural networks and deep learning via application on images.  If there are examples/code, they are often done on the MNIST data set.
I was wondering if there's a book out there that goes in depth into neural networks and is equally well written but explains it on non-image data.  I am particularly interested in time series application, although some talk on cross-sectional application would be helpful as well.  I am particularly interested in learning about:

What types of layers/functions/structure are better suited for time-series data
Various models for time series and pros/cons/applications of each (Convoluted NN, LTSM, etc...)
Typical structures of your neural network (depth, sparse connections, etc...) that seem to work well on time series data
Special considerations or settings you should have in your neural network when working with time series data
Maybe some talk/examples on how time series prediction using traditional models like ARIMA, can be reproduced or done better using neural networks.  Or side by side comparison of pros/cons of using one vs the other.

Thanks!

I'm currently working with Temporal Convolution Networks (TCNs) for making predictions with time series data (link to article here: https://medium.com/@raushan2807/temporal-convolutional-networks-bfea16e6d7d2).  These types of networks, like other types of convolutional networks for time series, use a dilated convolution operation, which, unlike the standard convolution in these networks, is a causal operation that preserves the causality of the time series input.
I've also seen CNNs used in Temporal Differencing applications, but that may be more useful in the context of video processing rather than time series analysis.


What are some examples of LSTM architectures? I've been doing some class assignments recently on building various neural networks. For convolutional networks, there are several well-known architectures such as LeNet, VGG etc. Such "classic" models are frequently referenced as starting points when building new CNNs.

Are there similar examples for RNN/LSTM networks? All I've found so far are articles and slides explaining recurrent neurons, LSTM layers, and the math behind them, but no well-known examples of entire multi-layered network architectures, unlike CNNs which seem to have in abundance.

In the paper, LSTM: A Search Space Odyssey (2017), by Klaus Greff et al., eight LSTM variants on three representative tasks (speech recognition, handwriting recognition, and polyphonic music modeling) are compared.

The compared variants are

Vanilla LSTM features three gates (input, forget, output), block input, a single cell, an output activation function, and peephole connections (connections from the cell to the gates). The output of the block is recurrently connected back to the block input and all of the gates. The vanilla LSTM is trained using gradient descent and back-propagation through time (BPTT). The original LSTM (which is not the vanilla LSTM) does not contain, for example, the forget gate or the peephole connections (but the cell possesses a constant error carousel, a constant weight of $1$).
LSTM trained based on the decoupled extended Kalman filtering (DEKF-LSTM), which enables the LSTM to be trained on some pathological cases at the cost of high computational complexity.
Vanilla LSTM trained with an evolution-based method (called evolino), instead of BPTT.
LSTM block architectures evolved with a multi-objective evolutionary algorithm, so that to maximize fitness on context-sensitive grammar.
LSTM architectures for large scale acoustic modeling, which introduces a linear projection layer that projects the output of the LSTM layer down before recurrent and forward connections in order to reduce the number of parameters for LSTM networks with many blocks.
An LSTM architecture with a trainable scaling parameter for the slope of the gate activation functions, which improves the performance of LSTM on an offline handwriting recognition dataset.
Dynamic Cortex Memory, an LSTM composed of recurrent connections between the gates of a single block, but not between different blocks, which improves the convergence speed of LSTM.
Gated Recurrent Unit (GRU), which simplifies the architecture of the LSTM by combining the input and forget gate into an update gate.

There are other related neural network architectures, such as the neural Turing machine (NTM) or differentiable neural computer (DNC). In general, there are several architectures that use LSTM blocks, even though they are not just recurrent neural networks. Other examples are the neural programmer-interpreter (NPI) or the meta-controller.


What is the difference between an episode, a trajectory and a rollout? I often see the terms episode, trajectory and rollout to refer to basically the same thing, a list of (state, action, rewards). Are there any concrete differences between the terms or can they be used interchangeably?

In the following paragraphs, I'll summarize my current slightly vague understanding of the terms. Please point any inaccuracy or missing details in my definitions.

I think episode has a more specific definition in that it begins with an initial state and finishes with a terminal state, where the definition of whether or not a state is initial or terminal is given by the definition of the MDP. Also, I understand an episode as a sequence of $(s, a, r)$ sampled by interacting with the environment following a particular policy, so it should have a non-zero probability of occurring in the exact same order.

With trajectory, the meaning is not as clear to me, but I believe a trajectory could represent only part of an episode and maybe the tuples could also be in an arbitrary order; even if getting such sequence by interacting with the environment has zero probability, it'd be ok, because we could say that such trajectory has zero probability of occurring.

I think rollout is somewhere in between, since I commonly see it used to refer to a sampled sequence of $(s, a, r) $from interacting with the environment under a given policy, but it might be only a segment of the episode, or even a segment of a continuing task, where it doesn't even make sense to talk about episodes.

I don't really think there are fixed, different definitions for all those terms that everyone agrees upon. In most contexts they're going to be quite interchangeable, and if anyone is really using them in a context where they are supposed to have crucially important, different meanings, they should probably precisely define them right there.

  I think episode has a more specific definition in that it begins with an initial state and finishes with a terminal state, where the definition of whether or not a state is initial or terminal is given by the definition of the MDP. Also, I understand an episode as a sequence of $(s,a,r)$ sampled by interacting with the environment following a particular policy, so it should have a non-zero probability of occurring in the exact same order.

Agreed with this.

  With trajectory, the meaning is not as clear to me, but I believe a trajectory could represent only part of an episode and maybe the tuples could also be in an arbitrary order; even if getting such sequence by interacting with the environment has zero probability, it'd be ok, because we could say that such trajectory has zero probability of occurring.

I can't really think of cases where it's sensible to talk about trajectories with tuples shuffled into an arbitrary order. I'd still think of trajectories as having to be in the "correct" order in which they were experienced. But I do agree that trajectories can be little samples (for instance, little sequences of experience that we store in an experience replay buffer). So, every full episode would be a (long) trajectory, but not every trajectory is a full episode (a trajectory can just be a small part of an episode).

  I think rollout is somewhere in between, since I commonly see it used to refer to a sampled sequence of $(s,a,r)$ from interacting with the environment under a given policy, but it might be only a segment of the episode, or even a segment of a continuing task, where it doesn't even make sense to talk about episodes.

I'd say that... often a rollout should have a "terminal" state as ending, but maybe not a true "initial" state of an episode as start. We might be in the middle of an episode, and then say that we "roll out", which to me implies that we keep going until the end of an episode. I don't think this term is as common as the other two in Reinforcement Learning, but more common in search / planning literature (in particular, Monte Caro Tree Search).

That said, when I'm working with MCTS I often like to put a limit on my rollouts where I cut them off if no terminal state was reached yet... so that isn't exactly a crisp definition either.

Due to how commonly-used this term is specifically in MCTS, and other Monte-Carlo-based algorithm, I also associate a greater degree of randomness with the term "rollout". When I hear "episode" or "trajectory", I can envision a highly sophisticated, "intelligent" policy being used to select actions, but when I hear "rollout" I am inclined to think of a greater degree of randomness being incorporated in the action selection (maybe uniformly random, or maybe with some cheap-to-compute, simple policy for biasing away from uniformity). Again, that's really just an association I have in my mind with the term, and not a crisp definition.


Why do we need to go back to policy evaluation after policy improvement if the policy is not stable? Above is the algorithm for Policy Iteration from Sutton's RL book. So, step 2 actually looks like value iteration, and then, at step 3 (policy improvement), if the policy isn't stable it goes back to step 2.
I don't really understand this: it seems like, if you do step 2 to within a small $\Delta$, then your estimate of the value function should be pretty close to optimal for each state.
So, why would you need to visit it again after policy improvement?
It seems like policy improvement only improves the policy function, but that doesn't affect the value function, so I'm not sure why you'd need to go back to step 2 if the policy isn't stable.

There is a difference between accurate value function estimates, and optimal value functions. An optimal value function is more specifically the value function of an optimal policy.
Value functions are always specific to some policy, which is why you will often see the subscript $\pi$ in e.g. $v_{\pi}(s)$ when there is a defined policy.
The policy evaluation step (step 2) in policy iteration converges to an accurate value function estimate for whatever the current policy is. In general this will not be an optimal value function, except on the last time that step 2 is used, and there is no change to the policy in the next stage policy improvement (step 3).
The policy improvement stage (step 3) can only usefully be run once for any value function estimate. The policy is updated to be greedy with respect to the value function from step 2 - that will always give the same results from the same value function estimate. If the value function is accurate then this new policy is guaranteed to be as good or better than the previous policy. Once step 3 is done, further improvements are only possible if the new policy is accurately evaluated.
Comparison with value iteration
The difference with value iteration is that it never accurately evaluates any interim policies. In value iteration, the implied policy changes every time the maximising action changes due to new value estimates. In the later stages, when the optimal policy has been found and is stable, then the value function will converge to the optimal value function. In value iteration, most of the interim value functions are not accurate, but when it becomes accurate it will also be the optimal value function.