Will the target network, which is less trained than the normal network, output inferior estimates?

However, if you use a target network, which is less trained than the normal net — especially at early stages of the training — wouldn't the state/action/advantage value be updating towards an inferior estimate?

Possibly, but a critical part of stability of TD learning with function approximation when adding a target network is that any updates will be consistent in the short term.

Consider that with a single network, the TD target calculation will also be biased (and by the same amounts on the first few passes), but they will not be consistent. Each learning update shifts the estimates by a value that is biased. Problems occur with stability when instead of the bias decaying over time due to real data from each step, that the bias amount is enough to form a positive feedback loop.

As a concrete example, suppose an initial random network calculating $\hat{q}(s,a,\theta)$ where

The reward is 1.0
The true value function $q^*(s,a)$ is 10.0 (it is not really relevant) and that would make $q^*(s',a') = 9.0$
The NN initially, predicts 5.0 for $\hat{q}(s,a,\theta)$ and 7.0 for $\text{max}_{a'}\hat{q}(s',a',\theta)$.
We also have a learning network using parameters $\theta$ that change on each learning update.
We have a frozen copy of the initial network using parameter $\bar{\theta}$
We have some learning rate $\alpha$ that for arguments sake we say reduces error in this case by 50% each time it sees this example.
The approximation process in the NN means that $\hat{q}(s,a,\theta)$ and $\text{max}_{a'}\hat{q}(s',a',\theta)$ are linked. This is a real feature of neural networks, but hard to model as it evolves over time. Let's say that with the initial setup that any learning of $\hat{q}(s,a,\theta)$ in isolation will make $\text{max}_{a'}\hat{q}(s',a',\theta)$ change towards $\hat{q}(s,a,\theta)$ by a 50% step. These steps sizes are not that important, they could be just 1% and the problem still occurs.

You can control the learning rate directly, but cannot really control the "generalisation link strength" of the approximation.

To really trigger the problem I want to show, let's say that these single steps are occurring far enough away from the end of an episode, or other moderating feedback, that we effectively get a few hundred visits to our $(s,a)$ pair without impact from other items (in fact it is likely that many will be going through the same issues)

Without the target network, the first TD target is $1.0 + 7.0 = 8.0$. After update $\hat{q}(s,a,\theta) = 6.5$ and $\text{max}_{a'}\hat{q}(s',a',\theta)$ = 6.75$. This looks good, right? Getting closer to the real values . . . but keep going . . . the next updates work like this:

q(s,a)      max q(s',a')
 7.125       6.938
 7.531       7.234
 7.882       7.559
 8.221       7.889

Again, this looks OK? But let's come back to it after 100 [isolated, so a bit fake] iterations:

40.222      39.889
40.556      40.222
40.889      40.556
41.222      40.889
41.556      41.222

This has overshot, and both values are increasing exponentially. The initial neural network bias is caught in a positive feedback loop.

Now if we use the target network that always predicts 7.0, what happens is what you expect. After 100 iterations we have:

 8.0         7.5
 8.0         7.5
 8.0         7.5
 8.0         7.5
 8.0         7.5

These values are still incorrect, but the updates have made a more conservative and stable step towards the correct values. Note the second value is what the learning network would predict for $\text{max}_{a'}\hat{q}(s',a',\theta)$, but we have used the other prediction $\text{max}_{a'}\hat{q}(s',a',\bar{\theta})$ on each step.

In reality the feedback loops are more complex that this, because this is function approximation so action value estimates from different $(s,a)$ pairs interact in ways that are hard to predict. But the worry is that bias causes divergence in estimates, and this does happen in practice. It is more likely to happen in environments with long episodes, or where state loops are possible.

It is also worth noting that using the frozen target network has not solved the problem, it has just significantly throttled runaway feedback. The amount of throttling required to keep learning stable will vary depending on the problem. The number of steps between target network updates is a hyperparameter. Set it too low and you risk seeing stability problems. Set it too high and learning will take longer.

  I've tried implementing DQNs and DDPGs on Cartpole, and I've found that the algorithms fail to converge when target networks are used, but work fine when those target networks are removed.

In that case, your implementations are incorrect. Definitely I have observed DQN with a target network working many times on Cartpole.

Whether or not using a target network makes convergence faster or more stable is more complex, and it may be for your network design or hyperparameter choices that adding the target network is making performance worse.


You're unsure about the definition of life (which the other answers clarify) but also most people are unclear about the definition of AI. Do you mean an AI that can accomplish a routine task (such as the path finder in a GPS) or a General AI that is able to find a creative solution to any directive given to it (such an AI does not yet exist and may not ever exist) or do you mean a SENTIENT computer program? Here is a simple article introducing some different concepts refered to as AI

Some people believe that a sentient computer program would be entitled to human rights. Not technically 'alive' in the biological sense, but having self awareness, will, desires, etc. Others disagree and believe that the program is a mere simulation that artificially mimics the actions of a human with a human soul, and is no more human than a washing machine. This is a very deep philosophical and meta-physical debate. For example, in A.I. the movie the overall message is that an android can simulate the emotion of love in a way that is more loyal and sincere than any human.

What I find interesting about this purely theoretical debate is that in almost every instance of sci-fi media that deals with the theme, the AI exists inside of a human-like android. But technically, the shape of the robot should be irrelevant.


How to define Agar.io state and action space?

The state space is certainly continuous, assuming that you can somehow feed that AI exact coordinates. You may have to resort to CNNs if you do not have access to this information. For the action space, you should consider how the game actually plays. Since you use a mouse to simply show the direction, you could use (x,y) positions of the mouse as an action, or even just the angle $\theta$ of the mouse cursor in a circle around the agent. If you are playing on the site, then your observations would have to be from a CNN, it should be possible to use the score as your reward, as well as the possibility for eating things or distance from opponents that are bigger or smaller as intermediate rewards. The number of nodes in your network is something that you must find experimentally, you may like to research what kind of architectures other people have used in this field. You shouldn't need to account for different numbers of players. Nothing special needs to be done to get a single node giving a continuous output to represent the angle $\theta$, or alternatively two nodes representing x and y. You can then use tanh or sigmoid to limit the output node values for eject and split actions.


Are any organisations using AI to predict weather?

People have used machine learning models on aspects of weather forecasting, as here: Convolutional LSTM Network: A Machine Learning Approach for Precipitation Nowcasting or here Predicting Solar Generation from Weather Forecasts using Machine Learning.  I've been loosely associated with an effort to use ML techniques to predict utility demand from weather data.  But note that these are looking to predict the implications of the weather forecast, not the forecast itself.  Lots of effort goes into refining the physics-based models that underlie our everyday weather forecasts, and AFAIK machine learning hasn't resulted in any "secret sauce" that gives better results than these models provide.


How to build a test set for a model in industry?

I am not sure whether that solves your problem at hand, but one approach you could look into is k-fold Cross Validation (CV).
In this approach, you split your combined train, development, and test data into $k$ randomized and equally-sized partitions.
Afterwards, you train and evaluate your model $k$ times. In the $i^{th}$ iteration, you train your model on all but the $i^{th}$ partition. After training on the $k-1$ partitions is done, you evaluate your model on the $i^{th}$ partition. You repeat this process for all $i \in {1, 2, ..., k}$.
To be clear, you keep your initially randomized partitions fixed during k-fold CV.
Then, you take the average performance over all $k$ performed test runs to assess the quality of your model based on the averaged test performance. Afterwards, you could train your model on all train, development, and test data and deliver the resulting model as your final one.
In the most extreme case, you would perform Leave-One-Out-CV, where you set $k$ equal to the number of all the data points at your disposal. That is the most expensive approach, but yields the most accurate performance estimates.
For more information, see this website.
Generally, using that approach, you don't waste any data by reserving it exclusively for development/testing. Also, it might be important to mention that this approach is compatible with other sampling techniques as well. For example, in the $i^{th}$ iteration of your CV algorithm, you could apply stratified sampling to your $k-1$ partitions used for training during that ($i^{th}$) iteration.
I am not entirely sure whether I get the second part of your question right.
If it is about how to later introduce the new feature to a given model, I would say the following.
When it comes to introducing new features, I think you are pretty much out of luck with respect to recycling your old model. Of course, (assuming that the introduction of new features to the existing model is technically possible) there might be types of models which allow continual learning under certain circumstances, but in the worst case that might cause catastrophic forgetting since you change the distribution of your underlying training data when adding new features, which not all models might be able to deal with.
An example of this case is when you add more diverse training images for a given Convolutional Neural Net (CNN), which the CNN then has to learn to map to an already existing set of classes.
In other cases, introducing new features might not even be technically possible if their introduction would require adding new input (or output) nodes to an existing model.
However, when your second part of the question asks for how to fill gaps in your older data, caused by missing data, there are different strategies you could try for imputing the missing data, some of which are briefly mentioned here.


How does PCA work when we reduce the original space to 2 or higher-dimensional space?

You might want to have a look at the wikipedia article of PCA, where it says:
"The $k$th component can be found by subtracting the first $k − 1$ principal components from $\mathbf{X}$:"
$$\hat{\mathbf{X}}_k = \mathbf{X} - \sum_{s=1}^{k-1}\mathbf{X}\mathbf{w}_s\mathbf{w}_s^T$$
Then you repeat the process to find the next component:
$$\mathbf{w}_k = \arg\max \mathbf{w}^T\mathbf{\hat{X}}^T_k\mathbf{\hat{X}}_k\mathbf{w}$$
$$\text{s.t. } \mathbf{w}_k^T\mathbf{w}_k = 1$$


Are there Python packages for random search hyper-parameter optimisation?

Welcome to AI.SE Enes.

I think by random search, you are referring to so-called "black-box optimization". Random search is sometimes used as a name for this, but BBO is a more common name, and might be easier to search for.

There are many BBO techniques. 'random search' is usually used to refer to a hill-climbing algorithm where you start at a random location, sample from 'adjacent' points in the input space, and then pick the best one to move to.

Scikit-optimize is fairly easy to use package, and implements some of the most reasonable algorithms (gaussian process is particularly strong on most problems). The package's website includes many good examples showing how to use the methods the package provides.

If you're not happy with those methods, then you are likely entering 'unsupported land'. There are lots of more complex, esoteric, methods, but I don't believe they are well consolidated into a single package (or even a single language). There's a nice collection on the Sahindis lab's website, but those are in a mixture of C and Fortran. There are also a huge number of algorithms submitted to recurring competitions, like this one at GECCO each year, but the implementations of these algorithms may not be available at all, or might be available only through the websites of their respective authors.


Are there any learning algorithms as powerful as "deep" architectures?

Have you read the book The Master Algorithm: by Pedro Domingos?

He discusses the present day machine learning algorithms... Their strengths, weaknesses and applications...

Deep Neural Network
Genetic Algorithm
Bayesian Network
Support Vector Machine
Inverse Deduction


Why is my implementation of Q-learning not converging to the right values in the FrozenLake environment?

I was able to solve the problem.
The main issue for non-convergence was that I was not decaying the learning rate appropriately. I put a decay rate of $-0.00005$ on the learning rate lr, and subsequently Q-Learning also converged to the same value as value iteration.


What are the differences between SARSA and Q-learning?

The main difference between the two is that Q-learning is an off policy algorithm. That is, we learn about an policy that is different to the one we choose to make actions. To see this, lets look at the update rule.

Q-Learning

$$Q(s,a) = Q(s,a) + \alpha (R_{t+1} + \gamma \max_aQ(s',a) - Q(s,a))$$

SARSA

$$Q(s,a) = Q(s,a) + \alpha (R_{t+1} + \gamma Q(s',a') - Q(s,a))$$

In SARSA we chose our $a'$ according to what our policy tells us to do when we are in state $s'$, so the policy we are learning about is also the policy that we choose to make our actions.

In Q-learning, we learn about the greedy policy whilst following some other policy, such as $\epsilon$-greedy. This is because when we transition into state $s'$ our TD-target becomes the maximum Q-value for whichever state we end up in, $s'$, where the max is taken over the actions.

Once we have actually updated our Q-function and we need to choose an action to take in $s'$, we do so from the policy we are using to generate our actions from -- thus we are learning about the greedy policy whilst following some other policy, hence off policy. In SARSA when we move into $s'$ our TD-target is chosen by the Q-value for the state we transition into and then the action we would choose based on our policy.

  Within the Q-learning episode loop the $a$ value is not updated, is an update made to $a$ during Q-learning?

It will be, because the policy we use to choose our actions is ensured to explore sufficiently around all of the state-action pairs and so it is guaranteed to be encountered at some point.

  Sarsa, unlike Q-learning, does not include the arg max as part of the update to Q value.

It is not an $\arg \max$, it is a $\max$. This is defined as
$$\max_x f(x) = \{f(x) | \forall y\; : f(y) \leq f(x) \}$$

  Sarsa, unlike Q-learning, the current action is assigned to the next action at the end of each episode step. Q-learning does not assign the current action to the next action at the end of each episode step

Kind of - the action that you chose for your TD-target in SARSA becomes the next action that you consider in the next step of the episode. This is natural because essentially you are in state $s$, you take action $a$ and observe a new state $s'$, at which point you can use your policy to see which action you will take, call this $a'$, and then perform the SARSA update, and then execute that action in the environment.

  Sarsa and Q learning in choosing the initial action for each episode both use a "policy derived from Q", as an example, the epsilon greedy policy is given in the algorithm definition. But any policy could be used here instead of epsilon greedy?

Yes, any policy can be used although you want to choose a policy that allows sufficient exploration of the state-space.

  Q learning does not utilise the next state-action pair in performing
  the td update, it just utilises the next state and current action,
  this is given in the algorithm definition as $Q(S',a)$ what is $a$ in
  this case ?

in the algorithm it actually has $\max_a Q(S',a)$, which if you refer back to my earlier definition of what the $\max$ operator does, should answer this question.


Why are Target Networks used in Deep Q-Learning as opposed to the Expected Value equation?

In short, because for many problems, this learns more efficiently.
It is the difference between Monte Carlo (MC) methods and Temporal Difference (TD) learning.
You can use MC estimates for expected return in deep RL. They are slower for two reasons:

It takes far more experience to collect enough data to train a neural network, because to fully sample a return you need a whole episode. You cannot just use one episode at a time because that presents the neural network with correlated data. You would need to collect multiple episodes and fill a large experience table.

As an aside, you would also need to discard all the experience after each update, because sampled full returns are on-policy data. Or you could implement importance sampling for off-policy Monte Carlo control and re-calculate the correct updates when the policy starts to improve, which is added complexity.

Samples of full returns have a higher variance, so the sampled data is noisier.

In comparison, TD learning starts with biased samples. This bias reduces over time as estimates become better, but it is the reason why a target network is used (otherwise the bias would cause runaway feed back).
So you have a bias/variance trade off with TD representing high bias and MC representing high variance.
It is not clear theoretically which is better in general, because it depends on the nature of MDPs that you are solving with each method. In practice, on the types of problems Deep RL has been tried on, single-step TD learning appears to do better than MC sampling of returns, in terms of goals such as sample efficiency and learning time.
You can compromise between TD and MC using eligibility traces, resulting in TD($\lambda$). However, this is awkward to implement in Deep RL due to the experience replay table. A simpler compromise is to use $n$-step returns e.g. $r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \gamma^3 \text{max}_a(Q(s_{t+4},a))$, which was one of the refinements used in the "Rainbow" DQN paper - note that even though strictly in their case, this handled off-policy incorrectly (it should use importance sampling, but they didn't bother), it still worked well enough for low $n$ on the Atari problems.


How would DeepMind's new differentiable neural computer scale?

Examining the architecture of the DNC indeed shows many similarities to the LSTM. Consider the diagram in the DeepMind article that you linked to:

Compare this to the LSTM architecture (credit to ananth on SlideShare):

There are some close analogs here:

Much like the LSTM, the DNC will perform some conversion from input to fixed-size state vectors (h and c in the LSTM)
Likewise, the DNC will perform some conversion from these fixed-size state vectors to potentially arbitrarily-lengthed output (in the LSTM we repeatedly sample from our model until we are satisfied/the model indicates we are done)
The forget and input gates of the LSTM represent the write operation in the DNC ('forgetting' is essentially just zeroing or partially zeroing memory)
The output gate of the LSTM represents the read operation in the DNC

However, the DNC is definitely more than an LSTM. Most obviously, it utilizes a larger state which is discretized (addressable) into chunks; this allows it to make the forget gate of the LSTM more binary. By this I mean that the state is not necessarily eroded by some fraction at every time step, whereas in the LSTM (with the sigmoid activation function) it necessarily is. This might reduce the problem of catastrophic forgetting that you mentioned and thus scale better.

The DNC is also novel in the links that it uses between memory. However, this might be a more marginal improvement on the LSTM than it seems if we re-imagine the LSTM with complete neural networks for each gate instead of just a single layer with an activation function (call this a super-LSTM); in this case, we can actually learn any relationship between two slots in memory with a sufficiently powerful network. While I don't know the specifics of the links that DeepMind is suggesting, they imply in the article that they are learning everything just by backpropagating gradients like a regular neural network. Therefore whatever relationship they are encoding in their links should theoretically be learnable by a neural network, and so a sufficiently powerful 'super-LSTM' should be able to capture it.

With all that being said, it is often the case in deep learning that two models with the same theoretical capability for expressiveness perform vastly different in practice. For example, consider that a recurrent network can be represented as a huge feed-forward network if we just unroll it. Similarly, the convolutional network isn't better than a vanilla neural network because it has some extra capacity for expressiveness; in fact, it is the constraints imposed on its weights that makes it more effective. Thus comparing the expressiveness of two models isn't necessarily a fair comparison of their performance in practice, nor an accurate projection of how well they will scale.

One question I have about the DNC is what happens when it runs out of memory. When a classical computer runs out of memory and another block of memory is requested, programs start crashing (at best). I'm curious to see how DeepMind plans to address this. I assume it will rely on some intelligent cannibalization of memory currently in use. In some sense computers currently do this when an OS requests that applications free up non-critical memory if memory pressure reaches a certain threshold.


Are there ensemble methods for regression?

? This means that there are not promising versions of this algorithm fro regression until 2012.
After your question, I have found one of the survey research paper which is done or ensemple methods for regression. This table also extracted from this paper.
Read this paper, it will help you a lot more
This one is latest paper published on object detection with an ensemble approach


Could we update the policy network with previous trajectories using supervised learning?

You cannot really do that because you have no way of knowing how good the action really is to make reasonable labels for supervised learning (that's the whole point why we need reinforcement learning). The only way to possibly know that is to make labels based on the return that you got from that action but the return is based on an old trajectory with the old policy. The return for that specific action depends on actions that happened after that action in the trajectory and return for those actions change with time.

To make things clearer, consider a simple case. Let's say you take action $a_1$ and you end up in state $s_1$ with reward $0$. Then you have two possibilities, you take action $a_2$ and end up in terminal state $s_2$ with reward $-10$ or you take action $a_2'$ and end up in terminal state $s_2'$ with reward $10$. Let's say you use trajectory $a_1 \rightarrow s_1 \rightarrow a_2 \rightarrow s_2$ with return $-10$ to learn about action $a_1$. Then your label for that action would probably be that that action is bad, but it actually isn't, if you took action $a_2'$ after $a_1$ your return for action $a_1$ would be $10$. So you learned that your action is bad even though it might not be. Now, if later you learn that taking action $a_2'$ is good to take after $a_1$ then you would also learn that $a_1$ might be good but if you keep using that old data with return $-10$ you will keep learning that $a_1$ is bad.

You can only use data gathered from the current policy to learn about it because older data might be outdated.


What is the difference between a learning algorithm and a hypothesis?

In computational learning theory, a learning algorithm (or learner) $A$ is an algorithm that chooses a hypothesis (which is a function) $h: \mathcal{X} \rightarrow \mathcal{Y}$, where $\mathcal{X}$ is the input space and $\mathcal{Y}$ is the target space, from the hypothesis space $H$.
For example, consider the task of image classification (e.g. MNIST). You can train, with gradient descent, a neural network to classify the images. In this case, gradient descent is the learner $A$, the space of all possible neural networks that gradient descent considers is the hypothesis space $H$ (so each combination of parameters of the neural network represents a specific hypothesis), $\mathcal{X}$ is the space of images that you want to classify, $\mathcal{Y}$ is the space of all possible classes and the final trained neural network is the hypothesis $h$ chosen by the learner $A$.

For example, would the decision tree and random forest be considered two different learning algorithms?

The decision tree and random forest are not learning algorithms. A specific decision tree or random forest is a hypothesis (i.e. function of the form as defined above).
In the context of decision trees, the ID3 algorithm (a decision tree algorithm that can be used to construct the decision tree, i.e. the hypothesis), is an example of a learning algorithm (aka learner).
The space of all trees that the learner considers is the hypothesis space/class.

Would a shallow neural network (that ends up learning a linear function) and a linear regression model, both of which use gradient descent to learn parameters, be considered different learning algorithms?

The same can be said here. A specific neural network or linear regression model (i.e. a line) corresponds to a specific hypothesis. The set of all neural networks (or lines, in the case of linear regression) that you consider corresponds to the hypothesis class.

Anyway, from what I understand, one way to vary the hypothesis $f$ would be to change the parameter values, maybe even the hyper-parameter values of, say, a decision tree.

If you consider a neural network (or decision tree) model, with $N$ parameters $\mathbf{\theta} = [\theta_i, \dots \theta_N]$, then a specific combination of these parameters corresponds to a specific hypothesis. If you change the values of these parameters, you also automatically change the hypothesis. If you change the hyperparameters (such as the number of neurons in a specific layer), however, you will be changing the hypothesis class, so the set of hypotheses that you consider.

Are there other ways of varying $f$?

Off the top of my head, only by changing the parameters, you change the hypothesis.

And how can we vary $A$?

Let's consider gradient descent as the learning algorithm. In this case, to change the learner, you could change, for example, the learning rate.


How to mathematically describe the convolution operation (with a Gaussian kernel)?

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

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

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

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

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

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

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


How do I prove that $\mathcal{H}$, with $\mathcal{VC}$ dimension $d$, shatters all subsets with size less than $d-1$?

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


Why do value iteration and policy iteration obtain similar policies even though they have different value functions?

Both value iteration (VI) and policy iteration (PI) algorithms are guaranteed to converge to the optimal policy, so it is expected that you get similar policies from both algorithms (if they have converged).

However, they do this differently. VI can be seen as truncated version of PI.

Let me first illustrate the pseudocode of both algorithms (taken from Barto and Sutton's book), which I suggest you get familiar with (but you are probably already familiar with them if you implemented both algorithms).

As you can see, policy iteration updates the policy multiple times, because it alternates a step of policy evaluation and a step of policy improvement, where a better policy is derived from the current best estimate of the value function.

On the other hand, value iteration updates the policy only once (at the end).

In both cases, the policies are derived from the value functions in the same way. So, if you obtain similar policies, you may think that they are necessarily derived from similar final value functions. However, in general, this may not the case, and this is actually the motivation for the existence of value iteration, i.e. you may derive an optimal policy from an non-optimal value function.

Barto and Sutton's book provide an example. See figure 4.1 on page 77 (p. 99 of the pdf). For completeness, here's a screenshot of the figure.


Why does KL divergence not satisfy the triangle inequality?

To prove that the KL divergence does not satisfy the triangle inequality, you just need a counterexample.

Definitions

KL divergence

Let's first recapitulate the definition of KL divergence for discrete probability distributions $p$ and $q$ (for simplicity).

$$
D_{\text{KL}}(p\parallel q)
=
\sum_{x\in {\mathcal {X}}}
p(x)\log
\left(
\frac {p(x)}{q(x)}
\right)
$$

Triangle inequality

Let's also recap the definition of the triangle inequality for distance $d$, which can be expressed as

$$
d(p,q) \leq d(p, r) + d(r, q),
$$
where $p, q$ and $r$ are probability distributions.

Proof

For simplicity, let the sample space be $\mathcal{X} = \{0, 1 \}$. Consider now the following three discrete probability distributions.

$$
p(x)=
\begin{cases}
\frac{1}{2}& \text{if } x = 0\\
\frac{1}{2}& \text{if } x = 1
\end{cases}
$$

$$
r(x)=
\begin{cases}
\frac{1}{4}& \text{if } x = 0\\
\frac{3}{4}& \text{if } x = 1
\end{cases}
$$

$$
q(x)=
\begin{cases}
\frac{1}{10}& \text{if } x = 0\\
\frac{9}{10}& \text{if } x = 1
\end{cases}
$$

Let's now apply the definition of the triangle inequality and the KL divergence for these discrete probability distributions. So, we want to show the following inequality does not hold.

$$
D_{\text{KL}}(p\parallel q)
\leq
D_{\text{KL}}(p\parallel r)
+
D_{\text{KL}}(r\parallel q)
$$

which can be expanded to

\begin{align}
\sum_{x\in \{0, 1 \}}
p(x)\log
\left(
\frac {p(x)}{q(x)}
\right)
&\leq
\sum_{x\in \{0, 1 \} }
p(x)\log
\left(
\frac {p(x)}{r(x)}
\right)
+
\sum_{x\in \{0, 1 \}}
r(x)\log
\left(
\frac {r(x)}{q(x)}
\right)
\end{align}

which roughly corresponds to

\begin{align}
0.51 &\leq 0.14 + 0.09 \\
0.51 &\leq 0.24
\end{align}
which is clearly false.

Given that the triangle inequality does not hold in one case, it doesn't hold in all cases, so the triangle inequality does not hold for the KL divergence.

$$\tag*{$\blacksquare$}$$

For reproducibility, I have used the following Python (3.7) program to compute the KL divergences.

from math import log

one = (1 / 2 * log((1 / 2) / (1 / 10))) + (1 / 2 * log((1 / 2) / (9 / 10)))
two = (1 / 2 * log((1 / 2) / (1 / 4))) + (1 / 2 * log((1 / 2) / (3 / 4)))
three = (1 / 4 * log((1 / 4) / (1 / 10))) + (3 / 4 * log((3 / 4) / (9 / 10)))

print(one)
print(two)
print(three)
print(two + three)
print(one <= two + three)


Why does regular Q-learning (and DQN) overestimate the Q values?

The overestimation comes from the random initialisation of your Q-value estimates. Obviously these will not be perfect (if they were then we wouldn't need to learn the true Q-values!). In many value based reinforcement learning methods such as SARSA or Q-learning the algorithms involve a $\max$ operator in the construction of the target policy. The most obvious case is, as you mentioned, Q-learning. The learning update is
$$Q(s, a) = Q(s, a) + \alpha \left[r(s, a) + \gamma \max_a Q(s', a) - Q(s, a) \right] \;.$$
The Q-function for the state-action tuple we are considering is shifted towards the max Q-function at the next state where the $\max$ is taken with respect to the actions.
Now, as mentioned our initial estimates of the Q-values are initialised randomly. This naturally leads to incorrect values. The consequence of this is that when we calculate $\max_aQ(s', a)$ we could be choosing values that are grossly overestimated.
As Q-learning (in the tabular case) is guaranteed to converge (under some mild assumptions) so the main consequence of the overestimation bias is that is severely slows down convergence. This of course can be overcome with Double Q-learning.
The answer above is for the tabular Q-Learning case. The idea is the same for the the Deep Q-Learning, except note that Deep Q-learning has no convergence guarantees (when using a NN as the function approximator) and so the overestimation bias is more of a problem as it can mean the parameters of the network get stuck in sub-optimal values.
As someone asked in the comments about always initialising the values to be very low numbers, this would not really work.
Consider the following MDP taken from Sutton and Barto:
We start in state A, from which we can either go right with reward 0 leading to a terminal state or go left with reward 0 to state B. From state B we can take, say, 100 different actions, all of which lead to a terminal state and have reward drawn from a Normal distribution with mean -0.1 and variance 1.
Now, clearly the optimal action from state A is to go right. However, when we go left and take an action in state B there is an (almost) 0.5 probability of getting a reward bigger than 0. Now, recall that the Q-value is shifted towards $r(s, a) + \max_a Q(s', a)$; because of the stochastic rewards when transitioning out of state B and the fact that we will likely see a positive reward the $\max_a Q(s', a)$ will be positive.
This means that when we take the left action the Q-value (Q(A, left)) is shifted towards a positive value, meaning that when we are in state A the value of moving left will be higher than moving right (which will gradually be being shifted towards the true value of 0) and so when following the $\epsilon$-greedy policy the greedy action will be to go left when in fact this is sub-optimal.
Now, of course, we know that the true Q-values will eventually converge but if we do have, say, 100 actions then you can probably see that the time it will take for the Q-values to converge to the true value will potentially be a long time as we would have to keep choosing all the overestimated values until we had convergence.


Should we focus more on societal or technical issues with AI risk

Neither AI alignment nor AI governance are important yet. We are so far away from AGI that we don't even know what is missing.

We don't set up safety instructions for interstellar travel, so why should we do it for AGI? I can also come up with a lot of dangers of that...

There are real dangers of AI, though. Including societal issues:

Blind trust:  Trusting a machine, although it is not perfect. Just because it is good in most cases and seems to be rational/objective. Example: Machine Bias
Unemployment: AI has the potential to replace a lot of low-skill jobs with very few super high skilled jobs. For example, self-driving cars (< 100 people for one manufacturer, I guess) could replace all jobs in trasportation (1,076,200 of 31,373,700 in Germany (source) - that is 3.4%!). See CG gray video.
Weapon Systems: The thread of leathal autonomous weapons is real. There is the danger of efficient slaughterbots and the danger of errors - similar to the Wech Baghtu wedding party airstrike or that one

There are a couple of other problems, but I think they are less severe:

Better fakes: lyrebird.ai gives a good demo
Spam: I think it's easier to improve the spam filters, but humans might have a harder time
Data is dominance: Companies like Amazon will have a dominant position on the market as they were the first to aquire important customer information
Bubbles / false hopes: AI (or let's better say Machine learning)  is often seen as a golden hammer. It is not.


Why does potential-based reward shaping seem to alter the optimal policy in this case?

The same $\gamma = 0.9$ that you use in the definition $F \doteq \gamma \Phi(s') - \Phi(s)$ should also be used as the discount factor in computing returns for multi-step trajectories. So, rather than simply adding up all the rewards for your different time-steps for the different trajectories, you should discount them by $\gamma$ for every time step that expires.

Therefore, the returns of the blue route are:

$$0 + (0.9 \times -1) + (0.9^2 \times 0) + (0.9^3 \times 1) = -0.9 + 0.729 = -0.171,$$

and the returns of the red route are:

$$(0 + 0.9 \times 100 - 0) + 0.9 \times (1 + 0.9 \times 0 - 100) = 90 - 89.1 = 0.9.$$


What are the differences between machine learning, pattern recognition and data mining?

Terms in a field are sometimes defined unambiguously. For instance, we know what convergence means when communicating about machine learning algorithms in academic publications because it has a formal definition in an older field, mathematics. However, the term machine learning is defined ambiguously across academic publications.

Perspectives on Machine Learning

Some see it as a branch of applied probability and statistics involving models with curvature (not usefully approximated by a first degree polynomial) and the application of those principles in digital computing. Some see it as an extension of the work of James Watt and Le Roy MacColl the application of the feedback control concept to digital control. Some see it as the natural result of the pioneering AI work of Norbert Wiener and John Von Neumann, where the adaptive qualities of nature, including neurochemistry, are simulated with the intention of birthing artificial life.

Some don't see that deeply into ML and imagine that its a set of classes and libraries the mastery over which will make for a great career. As shallow as that may seem, that concept may be as true as the other three deeper conceptions.

Perspectives on Data Mining

The term data mining is like that. Each book, and sometimes each chapter within the same book, seems to have its own distinct conception of the verb mining. Although these definitions have some similarity, the term is nothing like the term convergence or even database in IT or melody in music.

Unfolding the metaphor contained in the two words of the term, data mining is digging up data, and perhaps that's a satisfactory definition for the most general use of the term. The information sought is not on the surface, like diamonds dropped onto the ground, but rather underneath and covered with other materials so that one has to survey, dig, and process to get past the worthless material and reveal the gems.

This term has another vantage point. In systems theory there is an important distinction between noise and signal. In data science, what an electrical engineer would call the signal is the listing of statistics, table, graphic, or other visualization miner's client needs to make management decisions. The noise is everything obscuring the signal through complexity, volume, or prominence.

Perspectives on Pattern Recognition

The term pattern recognition is perhaps the most ambiguous because neither of the two words arose in a scientific context.

Early uses of the word pattern in English (and its equivalent in other languages) are related to shelter construction, farming, or early textiles. The notion that the shape of a letter or other symbol or a sequence of phonetic elements that make up a spoken word were patterns only arose recently. Much of the early and current work in pattern recognition involving computers had to do with converting natural language expressions into some functional machine representation.

The term pattern is also ambiguous because of gestalt, the dependence of perception on the orientation of the recognizer at the time of recognition. A sand castle may have an architecture to an architect, a chemical composition to a chemist, an indication of civilization to the starving passengers of a boat adrift, an obstacle in the way to a crayfish, and an imaginary home for a child.

To a mathematician, it may be a three dimensional form with particular surface topology, feature curvature, and dimensions. To a physicist, there may be no significant difference between the sand castle and the seagull flying over it or the air in between them (unless the sand castle is the triumph of the physicists own child).

The orientation of the machine is even more a constraint on the emulation of some aspect of human perception than demonstrated in gestalt psychology experiments. The human can adjust perception when a new kind of pattern or structure is pointed out. Until AI progresses further, that kind of experience, where the computer would say, "Oh, yes. Now I see the old woman in the picture of the young woman," is only realizable in software to the most primitive degree.

Taken literally, the term recognition means the repetition of a cognitive event, but that is not what we mean when we say, "I recognize that," in common speech. We usually mean that a mental search for some set of sensory features (not necessarily any more a pattern than anything else in the sensory stream) is identified and associated with some internal object or concept.

The most common use of a convolutional network (CNN) is neither of these. It is usually used to categorize objects or as a feature extracting sensory front end to a much larger AI design.

Overlap and Associations

With all these ambiguities present, some overlap may be apparent, in that some AI activities may thoroughly involve two or all three of these terms. Certainly some associations between the three terms are obvious.

When mining data, we may be looking for a particular kind of structure in a sea of data and have a particular search strategy to narrow the search and make it manageable for computing resources available. The test use during the search may be called pattern recognition.
In machine learning, we may train a network of artificial cells to assist in locating data or features in data that are meaningful to the stakeholders in the project. That would be using ML for data mining projects.

A large number of other associations between the three terms can be made. Which ones would appear most prominent to the expert would depend on the scientific, research, and career orientation of the expert.

Not Sufficient Overlap to be Synonyms

It would be difficult however to declare any two of the three to be synonymous. The three arose out of different kinds of research and from different orientations. Only some of that etymology is preserved in the terms themselves.


How to calculate the number of parameters of a convolutional layer?

What are the parameters in a convolutional layer?

The (learnable) parameters of a convolutional layer are the elements of the kernels (or filters) and biases (if you decide to have them). There are 1d, 2d and 3d convolutions. The most common are 2d convolutions, which are the ones people usually refer to, so I will mainly focus on this case.

2d convolutions

Example

If the 2d convolutional layer has $10$ filters of $3 \times 3$ shape and the input to the convolutional layer is $24 \times 24 \times 3$, then this actually means that the filters will have shape $3 \times 3 \times 3$, i.e. each filter will have the 3rd dimension that is equal to the 3rd dimension of the input. So, the 3rd dimension of the kernel is not given because it can be determined from the 3rd dimension of the input.

2d convolutions are performed along only 2 axes (x and y), hence the name. Here's a picture of a typical 2d convolutional layer where the depth of the kernel (in orange) is equal to the depth of the input volume (in cyan).

Each kernel can optionally have an associated scalar bias.

At this point, you should already be able to calculate the number of parameters of a standard convolutional layer.  In your case, the number of parameters is $10 * (3*3*3) + 10 = 280$.

A TensorFlow proof

The following simple TensorFlow (version 2) program can confirm this.

import tensorflow as tf

def get_model(input_shape, num_classes=10):
    model = tf.keras.Sequential()
    model.add(tf.keras.layers.Input(shape=input_shape))
    model.add(tf.keras.layers.Conv2D(10, kernel_size=3, use_bias=True))
    model.add(tf.keras.layers.Flatten())
    model.add(tf.keras.layers.Dense(num_classes))

    model.summary()

    return model

if __name__ == '__main__':
    input_shape = (24, 24, 3)
    get_model(input_shape)

You should try setting use_bias to False to understand how the number of parameters changes.

General case

So, in general, given $M$ filters of shape $K \times K$ and an input of shape $H \times W \times D$, then the number of parameters of the standard 2d convolutional layer, with scalar biases, is $M * (K * K * D) + M$ and, without biases, is $M * (K * K * D)$.

See also these related questions How is the depth of filters of hidden layers determined? and 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?.

1d and 3d convolutions

There are also 1d and 3d convolutions.

For example, in the case of 3d convolutions, the kernels may not have the same dimension as the depth of the input, so the number of parameters is calculated differently for 3d convolutional layers. Here's a diagram of 3d convolutional layer, where the kernel has a depth different than the depth of the input volume.

See e.g. Intuitive understanding of 1D, 2D, and 3D convolutions in convolutional neural networks.


Do I need classification or regression to predict the availability of a user given some features?

Yes. For instance, the popular softmax regression gives you probability distribution for each class.
Yes. Softmax is a regression over a set of discrete classes.

We can use regression for classification, the most common strategy is to grab the most likely class for the prediction.


Are neurons in layer $l$ only affected by neurons in the previous layer?

It depends on the architecture of the neural network. However, in general, no, neurons at layer $l$ are not only affected by neurons at layer $l-1$.

In the case of a multi-layer perceptron (or feed-forward neural network), only neurons at layer $l-1$ directly affect the neurons at layer $l$. However, neurons at layers $l-i$, for $i=2, \dots, l$, also indirectly affect the neurons at layer $l$.

In the case of recurrent neural networks, the output of neuron $j$ at level $l$ can also affect the same neuron but at a different time step.

In the case of residual networks, the output of a neuron at a layer $l-i$, for $i=2, \dots, l$, can directly affect the neurons at layer $l$. These non-neighboring connections are called skip connections because they skip layers.

There are probably other combinations of connections between neurons at different layers or the same layer.


Are there RL techniques to deal with incremental action spaces?

Is there some solutions to update the model with only minor changes?

In general, assuming the new action choices are meaningful - in at least some states, the expected return from taking one of the new actions is higher than the current optimal policy using just the old action selection - then the answer here is "no".

At the very least you will need to re-train your agent such that it explores the new action choices, and learns the new value function and policy. You can of course start this re-training using data and internal representations learned from the earlier environment, and that may help if the new actions have not changed things too radically.

There are a couple of things that might help improve performance on this re-training:

If the actions are not entirely discrete, but have some features that could be generalised from, you could base your value function or policy function estimators on those features instead of discrete actions. So for example in DQN your input to the neural network would be concatenated state, action feature vectors, and output a single value. Then it may generalise to the new actions quickly, in some cases perhaps even getting close to the correct value estimates from the start.
If you were training using DynaQ+, this includes an exploration term (which is added to planning assessments of immediate reward) that will prioritise exploring new state/action pairs when they appear. Other planning algorithms may have similar adjustments, although I am not aware of specific ones that could be dropped straight into a DQN agent.

If you know in advance which states the new actions are likely to be most useful in, you may be able to insert that knowledge into some initial action selection or value estimate helpers to avoid the need to train from scratch.


Name of paper for encoding/representing XY coordinates in deep learning

So this paper is by google, but is very similar where they use 2D positional embeddings and perform MHA on the flattened image. Are you talking about Attention Augmented Convolutional Networks


Has anybody tried unsupervised deep learning from youtube videos?

Yes, it is possible, and yes, it probably has been done before. Odds are, however, the person(s) who tried were disappointed with the results and forgot to tell others.

The reasons they might be disappointed could be any of the following:

Took to long to train
Even when fully trained, (or appeared to be), it did not give the expected output
Too sensitive to variations in the input


Can a convolutional neural network classify text document images?

Yes, it is possible, CNNs can also be used for OCR (see the MNIST task and this blog), although it's not the common way for OCR because it is considered a bit overkill and inefficient. Furthermore, OCR is considered a solved problem already and don't need deep learning to do well, unless perhaps under unfavorable conditions like dark lighting, complex background of the document, weird fonts, occlusion of text, etc.
Breaking down your questions:

a CNN can likely classify an image as "this image has a word document in it" vs "this image does not have a word document in it". The word document itself, and the outline of the words, should form distinct enough features for the CNN to discriminate against
a CNN can likely identify the vendor based on the logo of the vendor if you have enough training images of it at various distortions (angles, occlusions, different lighting, etc)
a CNN can likely do OCR well enough to extract the text, and then an entity extraction model can identify the vendor from the words. However, this approach would be uncommon as OCR is already considered a solved problem. But a neural network can potentially help preprocessing difficult OCR images (rotating image, identifying text boundaries, fix lighting, perform super-resolution, etc) to increase OCR accuracy


Why would neural network dream scenes mirror the hallucinations people experience when they're tripping?

The similarity of artificial neural networks and the human visual cortex goes very deep, and in many ways the human visual cortex was the inspiration for the techniques we use for the design and implementation of ANNs designed for image recognition. So in that direction, the similarity seems obvious to me.

The reverse direction, though, is a question about how the human mind works under the influence of LSD, which you'll probably get a better answer asking about in the biology or cognitive science stack exchange sites.

Some brief details to add to the answer, though: the human visual cortex is arranged in layers that correspond to increasing layers of abstraction. In the eyes themselves, photons are detected by light-sensitive cells and added together to make what are essentially the color elements of pixels. Those are then routed to another layer which does something like edge detection, and then the next layer does something like shape detection, and so on up to higher level concepts like "a cat's face.' If LSD lowers the activation threshold for those neurons, or makes them more excitable, then more things will be interpreted as having the higher level concept (and so a patch of rough texture may have a face jump out of it, for example).

The way that CNN "deep dreaming' works is that the base image is amplified. That is, to make a particular patch look more like a dog, the shapes are nudged to be more dog-like, and the shapes nudge the edges, and the edges nudge the pixels.


Should we also shuffle the test dataset when training with SGD?

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

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

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


What machine learning algorithm should be used to analyze the relationship between strings?

Here is a good approach to achieve the task you want:

Step 1- Compute the Vector representation (i.e embeddings) of all the words you want to include. There are many algorithms out there to achieve this task.

Step 2- Choose the #words corresponding to your input word (e.g dog) by applying K-Nearest Neighbors (KNN) or similar algorithms. You basically compute the distances using the embeddings.

  Steps Detailed:

Step 1-

In NLP we represent human language as a vector of values instead of a set of characters in order to process it. To do so there are 3 approaches in the literature:

- Word Level Embeddings: Represent each word as a vector of values.
   Algorithms: Word2Vec by Google (paper), fastText by Facebook, GloVe by Stanford University (paper) ...

- Character Level Embeddings: Represent each character as a vector of values. Algorithms: ELMo (paper) ...

- Sentence Level Embeddings: Represent a sentence as a vector of values. Algorithms: Universal Sentence Encoder by Google (paper) ...

In your case I suggest to use GloVe or ElMo if you have only words and Universal Sentence Encoder if you have words and sentences.  . Compute all your words embeddings and move to the next step.

Step 2-

Now that you have your embeddings, compute the distances between all your words (use Euclidian, Minkowski or any other distance). Notice that the computation may take some time but will only be executed once.

Now each time you have a word (e.g dog) you apply the KNN algorithm using the computed distances and you will get the most related words to this word.

  Note: No need to compute distances and apply KNN if you use Universal Sentence Encoder as the similarity is easily computed using a dot product of the embeddings. See my quick implementation example here for details.


How is the gradient calculated for the middle layer's weights?

The main doubt here is about the intuition behind the derivative part of back-propagation learning. First, I would like to point out 2 links about the intuition about how partial derivatives work Chain Rule Intuition and Intuitive reasoning behind the Chain Rule in multiple variables?.

Now that we know how the chain rule works, let's see how we can use it in Machine Learning. So basically in machine learning, the final output is a function of input variables and the connection weights
$f\left(x_1, x_2, \ldots, x_n, w_1, w_2, \ldots, w_n\right)$, where $f$ encloses all the activation functions and dot products lying between input and output. The $x_1, x_2, \ldots, x_n, w_1, w_2, \ldots, w_n$ are called independent variables because they don't affect each other pairwise as well as in groups meaning you cannot find a function $g(x_i, \dots, w_i, \dots) =  h(x_j, \dots, w_j, \dots)$. So, basically its a black box from input to output.

So now our purpose is to minimize the Loss/Cost function, by changing the parameters that can be 'controlled by us' i.e the weights only, we cannot change the input variables. So this is done by taking the derivative of the cost function w.r.t to the variable that 'can be changed'. Here is an explanation of why taking derivative and subsequently subtracting it reduces the value of cost function given by the 'maximal' amount. Also here.

Now, to calculate $dL/dw_n$ you have to keep few things in mind:

Only differentiate $L$ w.r.t to those functions which affect $L$.
And to reach your end goal of differentiation w.r.t to an independent variable you must differentiate $L$ w.r.t to those functions only which are dependent on that particular independent variable.

A crude algorithm assuming $L$ also as a normal function (along the lines of activation function, so that I can express the idea recursively) differentiate $f_n$ w.r.t to functions in the previous layer say $f_{n-1}$, $f_{n-2}$, $w_n$. Check which of these functions depends on $w_1$. Only $f_{n-1}$ and $f_{n-2}$ do. Differentiate them again w.r.t to previous layer functions. Check again and go on till you reach $w_1$.

This approach is the fool-proof version, but it has 2 flaws:

First, $w_n$ is not a function. People are making this mistake of assuming $w_n$ to be a function due to misinterpretation of a simple NN diagram. To reach $w_1$, you don't need to go through $w_n$. But you definitely need to go through the activation functions and dot products. Think of this as painting a wall where color mixing occurs (not over-writing). So you paint the wall with some color (weights) then 2nd color and so on. Is the final product affected by color 1. Yes. Is the 'rate of change' caused by color 1 also affected by color 2. Yes. But does it mean we can find the 'change'of color n w.r.t to color 1? No its meaningless (bad example, couldn't think of a better one)
The second flaw is that this approach is not followed because with experience it is apparent which function affects whom and which independent variable affects which function (saves computation).

To answer your question the equation is incorrect and the correct equation will be:

$$
\frac{\partial L}{\partial w_{1}}=\frac{\partial h_{1}}{\partial w_{1}} \frac{\partial o_{2}}{\partial h_{1}} \frac{\partial L}{\partial o_{2}}+\frac{\partial h_{1}}{\partial w_{1}} \frac{\partial o_{1}}{\partial h_{1}} \frac{\partial L}{\partial o_{1}}
$$

I have simply followed the algorithm I have given above.

As for why your equation is wrong, your equation contains the term $dw7/dh1$. Does $w_7$ vary with $h_1$? This means that $w_7$ is directly related to the input as $h_1$ is related with the input, but this is not the case for a single iteration(the whole algorithm run makes $w_n$ dependent on the inputs since you are trying to minimize the loss function w.r.t given inputs and weights, for a different set of inputs you will have different final weights).

So, in a nutshell, the aim of back-propagation is to identify the change in the loss function w.r.t to a given weight. To calculate that, you have to make sure in the chain rule of derivative you don't have any meaningless terms like the derivative of an independent variable w.r.t to any function. I recommend checking Khan Academy for a better understanding and clarity in concepts as I think the intuitions are hard to provide in a written answer.


Do I need to rotate the masks, if I also rotate the images and the masks are generated from the input?

Yes! This is crucial.
If you rotate your input images for segmentation, you need to rotate the output masks as well. Otherwise the loss of your network will not be correctly calculated and your network will not learn how to generalize to rotated input images.
If you use keras, you can use two ImageDataGenerator classes, one for the images and one for the masks, with the same random seed and augmentation parameters. It looks something like this:
data_gen_args = dict(rotation_range=45)

image_datagen = ImageDataGenerator(**data_gen_args)
mask_datagen = ImageDataGenerator(**data_gen_args)

image_generator = image_datagen.flow(train,seed=SEED)
mask_generator = mask_datagen.flow(y_train,seed=SEED)
train_generator = zip(image_generator, mask_generator)

model.compile(...)
model.fit_generator(train_generator, ...)


You have 3 inputs going to 3 nodes in the input layer. Each connection has a weight so you have  3 X 3 =9 weights. Plus each node has a bias weight so that adds 3 more weights for a total of 12. Your output layer has 3 inputs and is a single node so you have 3 weights for the inputs to the node plus a bias weight for a total of 4. So the total weights in your network is 16.


Could there be existential threats to humanity due to AI?

There is no doubt that AI has the potential to pose an existential threat to humanity.

  The greatest threat to mankind lies with superintelligent AI.

An artificial intelligence that surpasses human intelligence will be capable of exponentially increasing its own intelligence, resulting in an AI system that, to humans, will be completely unstoppable.

At this stage, if the artificial intelligence system decides that humanity is no longer useful, it could wipe us from the face of the earth.

As Eliezer Yudkowsky puts it in Artificial Intelligence as a Positive and Negative Factor in Global Risk,

"The AI does not hate you, nor does it love you, but you are made out of atoms which it can use for something else."

  A different threat lies with the instruction of highly intelligent AI

Here it is useful to consider the paper clip maximiser thought experiment.

A highly intelligent AI instructed to maximise paper clip production might take the following steps to achieve its goal.

1) Achieve an intelligence explosion to make itself superintelligent (this will increase paperclip optimisation efficiency)

2) Wipe out mankind so that it cannot be disabled (that would minimise production and be inefficient)

3) Use Earth's resources (including the planet itself) to build self replicating robots hosting the AI

4) Exponentially spread out across the universe, harvesting planets and stars alike, turning them into materials to build paper clip factories

  Clearly this is not what the human who's business paperclip production it was wanted, however it is the best way to fulfil the AI's instructions.

This illustrates how superintelligent and highly intelligent AI systems can be the greatest existential risk mankind may ever face.

Murray Shanahan, in The Technological Singularity, even proposed that AI may be the solution to the Fermi paradox: the reason why we see no intelligent life in the universe may be that once a civilisation becomes advanced enough, it will develop an AI that ultimately destroys it.
This is known as the idea of a cosmic filter.

In conclusion, the very intelligence that makes AI so useful also makes it extremely dangerous.

Influential figures like Elon Musk and Stephen Hawking have expressed concerns that superintelligent AI is the greatest threat we will ever have to face.

Hope that answers your question :)


Is it better to make neural network to have hierchical output?

Just use one network with a larger Softmax output layer and more hidden units. If you have enough training data, it will work just fine. In fact it could emulate the architecture you propose.


Neural machine translation, that outputs multiple alternative, ambiguous translations?

The LSTM seq2seq model typically used for language translation actually can output multiple variations, and does in many implementations.

The decoder stage outputs confidence/probabilities for each word, and it is possible to run the decoder multiple times, taking different samples on each run.

Not only is it possible, but this is actually done by translation engines. A technique called BEAM search is used to manage multiple translations in progress and pick an eventual one to display, based on whether the language model predicts an overall high or low probability for a sentence (this allows for sentences that start with an unusual initial word choice but that are a better choice in context of what is being translated). It would be a minor change to existing algorithms to display a selection of these instead.

Technically you don't need to sample randomly, and can just take the top N probabilities on each step, and recalculate each time on combined probabilities, culling partial sentences that have low probability in favour of continuing more of the high probability sentences.


With AI technology at its current stage (or at least reasonably close to this stage), the jobs you proposed may very well be openings created by AI automation. However, sufficiently advanced AI technology--- the kind that can function as general purpose labor replacement--- will make even these jobs obsolete. This is because such an AI would be able to improve itself and as a result would surpass human level intelligence---meaning that it would take actions which we would not necessarily be able to understand or justify.

This is all assuming that the intelligence of humans is not some kind of upper limit on the possibilities of intelligence in general. As far as I know there is no reason to think we represent such an upper limit.

To summarize...will such jobs exist?

Sub-human artificial intelligence: sure.
Beyond-human artificial intelligence: no reason to think they would be necessary as the AI can do them itself.


Does the alpha/beta value of parent nodes change if the alpha beta value of the child node changes?

I couldn't understand your question clearly, however, it think you are making a slim mistake. let's look at the flowing code from "Russell " and do pruning step by step:

Assume your are In D and you have traversed its both children, Alpha at D becomes 20. We then return back to B, Beta becomes 20 (note that Alpha is -Inf in D). We go to E then L and then back to E. 30 is greater than Beta, so the rest is pruned. Not that Alpha remains -Inf in E, though its value here isn't important. we go back to B the value of Beta remains on changed 20. If we go to F and return back to B Beta remains unchanged and is still 20 (Note that Alpha is still -Inf). We return to A, Alpha becomes 20, And Beta remains +Inf.
So, Considering the code, the max node does not get the Alpha value from its children, rather it decides on its own by setting Alpha = max(Alpha, and returned value of its child) after visiting each child. the same is true for Beta.


Why is the perplexity a good evaluation metric for chatbots?

With perplexity you are trying to evaluate the similarity between the token (in your case probably sentences) distribution generated by the model and the one in the test data.

For instance, assuming you have $M$ sentences $s_1, \dots, s_M$, each with probability $P(s_i)$, the perplexity is $$2^{-l},$$ where $l = \frac{1}{M} \sum P(s_i) \log P(s_i)$ for $i \in [1 \dots M]$.

Note that while perplexity might be useful to capturing certain aspects of the model, it is by no means perfect, and, even if you are able to reach great perplexity scores, it will not necessarily translate to a good or even working chat bot.


This is relevant when you have two or more neural networks serving as components to a larger architecture. Training this architecture in an end-to-end manner means simultaneously training all components (i.e. training it as a single network).

The best example I can think of are image captioning architectures. These usually comprise of two networks: a CNN whose role is to extract features from the input images and a RNN that accepts the CNN's features and generates the output captions.

You have two options for training:

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


Feature scaling is making your features have an equal representation or say in the final loss of the function. Intuitively as your picture suggests the contour will be elongated along one axes (feature with higher values).

Another example is lets say you have to separate two data clusters, one is  (x,2) and another is (x,5) where x is variable. Now if you are using sigmoid activation, sigmoid always gives positive values, but to separate the two classes you need to have negative value for (x,2) in the second last layer, thus the NN will for a longer time have to adjust the weights to be negative (assuming positive weight initialisation) of bias and other features until (x,2) gives negative value in the second last layer. But with feature normalisation the initial value would have been already negative something like (x,-1/3).

EDIT: From my answer on DataScience.SE:

Purpose: Normalisation is done so that the Neural Network weights converge faster. In CNN's and Deep Neural Nets this is of particular help especially in CNN this helps to prevent exploding/vanishing gradients.

The most common explanation for normalisation I have come across is that if you have 2 features, one of them has a significant larger scale than the other e.g house price and house area then the feature with a larger scale will dominate the output. This is quite incorrect according to me, since when you back-propagate through the Neural Net the weight updates are directly proportional to the activations, so larger activation means larger feedback and hence weights get reduced faster and become smaller until w1*house price = w2*house area approximately this relation holds true. Yes, it will lead to more oscillations (intuitionally, since learning rate also becomes multiplied with a larger scale) but it will ultimately probably converge.

So the best 3 reasons for using normalisation are:

If scale of a feature is large the weights connected to that feature will have larger oscillations resulting in slower convergence and if deep NN is used probably no convergence, whereas normalisation helps in making the values small -1 to 1 so the gradient updates are also small resulting in faster convergence.
The best intuition for normalisation can be found from this video of Stanford and its subsequent video. Since we know weight updates is directly proportional to inputs it will also take the sign of the inputs (or exact opposite sign) always. Now we know house price and area is always positive (in our Universe at least!). So the weight updates will always have definite sign either both positive or both negative (depending the sign of downstream gradients). But the weight updates may have a optimal value in the 4th quadrant, so the weight updates will have to follow a zig zag pattern to effectively make a weight update in the 4th quadrant.

Finally when you are dealing with Deep Neural Nets like CNN if you do not normalise pixels it will result in exponentially large/vanishing gradients. Since generally softmax/sigmoid is used in the last layer, it squashes the outputs. If you have a large output, generally due to un-normalized data, it'll result in wither exact 0 or exact 1 output, which is fed into a log function and BAM! overflow. The error becomes inf or NaN in python. So inf error means exploding gradients and NaN means gradient cannot be calculated. This can probably be remedied by using higher floating point precision but it will result in higher memory and processor consumption ultimately inefficiency.

TL;DR: Normalisation is used for faster weight convergence. Issues faced by un-normalised data are larger weight oscillations, weight updation in non optimal direction, overflow in precision in Deep Neural Nets.

Here are a few great links for better insight:

How and why do normalization and feature scaling work?

Why feature scaling?


How could you generate sentences from lists of facts

When you parse sentences you use grammatics to sentences to get the meaning (semantics).

Now you use sematics (tuples) and grammatics to make a sentence.

Your knowledge includes verb, noun and some kind of notion of readiness of the task defined by them.

To form sentences you also need knowledge / rules about the extra eligible words between these categories, as well as how time relates to verb grammatical tense.

You have to code a parser for tuples that codes the tuple in the three parts, formulate the grammatics,
and then apply the grammatics to the parsed tuple data.

After that you'll get the sentences.

More precise information on how to code that and this information plus the picture source:

http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/node93.html#l14.sec.nlg


Why are neural networks preferred to other classification functions optimized by gradient decent

You can indeed fit a polynomial to your labelled data, which is known as polynomial regression (which can e.g. be done with the function numpy.polyfit). One apparent limitation of polynomial regression is that, in practice, you need to assume that your data follows some specific polynomial of some degree $n$, i.e. you assume that your data has the form of the polynomial that you choose, which may not be true.
When you use a neural network to solve a classification or regression problem, you also need to choose the activation functions, the number of neurons, how they are connected, etc., so you also need to limit the number and type of functions that you can learn with neural networks, i.e. the hypothesis space.
Now, it is not necessarily a bad thing to limit the hypothesis space. In fact, learning is generally an ill-posed problem, i.e. in simple terms, there could be multiple solutions or no solutions at all (and other problems), so, actually, you often need to limit the hypothesis space to find some useful solutions (e.g. solutions that generalise better to unseen data). Regularisations techniques are ways of constraining the learning problem, and the hypothesis space (i.e. the set of functions that your learning algorithm can choose from), and thus making the learning problem well-posed.
Neural networks are not preferred over polynomial regression because they are theoretically more powerful. In fact, both can approximate any continuous function [1], but these are just theoretical results, i.e. these results do not give you the magical formula to choose the most appropriate neural network or polynomial that best approximates the desired unknown function.
In practice, neural networks have been proven to effectively solve many tasks (e.g. translation of natural language, playing go or atari games, image classification, etc.), so I would say that this is the main reason they are widely studied and there is a lot of interest in them. However, neural networks typically require large datasets to approximate well the desired but unknown function, it can be computationally expensive to train or perform inference with them, and there are other limitations (see this), so neural networks are definitely not perfect tools, and there is the need to improve them to make them more efficient and useful in certain scenarios (e.g. scenarios where uncertainty estimation is required).
I am not really familiar with research on polynomial regression, but it is possible that this and other tools have been overlooked by the ML community. You may want to have a look at this paper, which states that NNs are essentially doing polynomial regression, though I have not read it, so I don't know the details about the main ideas and results in this paper.


What are methods human actors use to imitate robots?

The great acting teacher Stella Adler wrote about mannerisms being a powerful tool for actors. Method acting in general focuses on natural performances based roughly on understanding the mindset of the character portrayed.

It's possible actors who have portrayed androids have observed industrial robots to inform their physicality, and many performances convey the idea, via movement, of a mechanical inner structure.  (It is often said that an "actor's body is their instrument".)

What is more interesting is actors trying to convey the cognitive structure of the androids.

With Arnold, and Terminator robots in general, the baseline performance is decidedly robotic, to convey their inhumanity. But the more advanced Terminators are able to mimic naturalistic human mannerisms, and even established human characters, to trick humans.

Lieutenant Data often used head motions, such as cocking his head slightly, to convey computation.  Here the character arc involved working to become more human, as this character draws heavily on Pinocchio, the wooden puppet that became a boy.  Overall Data's performance conveyed a lack of emotion, a definite reference to the logic-oriented Mr. Spock, although I recall episodes where Data experimented with "emotional circuits" and "humor circuits", where the output was intentionally inconsistent with natural human behavior.

Blade Runner, where the Tyrell Corporation's motto was "More Human than Human", presented the cutting edge Nexus-6 androids as having emotions, but, due to their artificially short life-spans, were portrayed as childlike in trying to reconcile extremely powerful feelings.  The Voight-Kampff Test, a form of Turing Test, used in the film to identify androids, relied on the emotional response to questions.

The key plot point of Do Androids Dream of Electric Sheep, the novel the film was based on, utilized what would be formalized as evolutionary game theory to hypothesize that empathy is a natural function of intelligence sufficiently advanced.  Deckard, who may or may not have been an android, and Rachel, who definitely was, are both capable of love.  This capacity informed their performances, to the extent that the androids came off as more human than the actual humans, due to the depth of their emotion.  This is also reflected in Blade Runner 2049 via the girlfriend-bot Joi, who us the most limited android, but the most human character in the film per her capacity to love (or at least simulate it.)

In the recent HBO Westworld reboot, the Androids replicate natural human mannerisms when playing their designated roles, but reset to more mechanical mannerisms when acting under their own agency.  This is reflected in Ex Machina, where the android mimics human emotions to pass a Turing Test and trick the human subject, only to revert to purely alien mannerisms after the android is free.  ("Alien" here used in the sense of non-human--it's possible the android is sentient as it seems to convey some degree of emotion in regarding the simulated human skin it will wear.)

The most interesting recent android performance may come from the recent Alien: Covenant where Michael Fassbender plays two identical androids, David and Walter, which have two distinct neural structures.  (David has the capacity to be creative, where Walter cannot.  In the film it is mentioned that David made people uncomfortable, so the creative functions were removed from subsequent models.)  The key difference in the performance seems to be that David demonstrates passion, and even emotions, where Walter is more clearly "robotic".

In general, the underlying approach of actors seems to have been to show the androids being distinct from humans, drawing a clear, though sometimes subtle, contrast.
Actors portraying androids have typically utilized robotic mannerisms to convey an artificial entity.


How should I interpret the surrogate and mean_noise_std plots of training a PPO model (from the Nvidia's Isaac gym)?

Loss. In the context of Deep Learning and Deep Reinforcement Learning, "training" is just a fancy word for "optimization". You are essentially looking for an optimum point in some huge-dimensional parameter space. For the Reinforcement Learning problems, the optimal point is supposed to maximize the expected return - while most of the Deep Learning classification problems are minimizing some loss.
Most of the modern Deep Learning programming frameworks was created with the classification problems in mind, so they call the optimization goals "losses": tf.keras, pytorch. The good news is that you can easily convert return-maximization problem to loss-minimization problem by just changing the sign of your target function.
Given all the above, the fact that your loss is going up instead of going down doesn't seem to be a good sign.
Value Function. Given an agent's state, Reinforcement Learning tries to find the best agent's action that maximized the expected return. The problem is that the expected return is also unknown. Note on the difference between "reward" and "return". Rewards $r_t$ are immediate bits of positive/negative reinforcement that the agent receives obtain after taking an action. The "return" $G_t$ is the function of a particular trajectory - it is the discounted sum of future rewards starting from step $t$:
$$G_t = \sum_k \gamma^k r_{t+k+1}$$
The expectation of the return at state $s$ given a policy $\pi$ is called value $V^\pi(s)$:
$$V^\pi(s) = \mathbb{E}_{a\sim\pi}\left[ G_t\right|\left. s_t=s\right]$$
In principle, it is possible to estimate $V^\pi(s)$ by doing Monte Carlo: start from the state $s$ and run many simulations following $\pi$ and average all the returns you've got. For most practical cases this approach is infeasible. Modern Deep Reinforcement Learning algorithms try to reduce computational load by using neural networks to approximate $V(s)$.
Having the value function approximation $V(s)$, one can then try to optimize the policy approximation function $\pi(a|s)$ using the policy gradient update. Such setup: with one approximator for policy and another approximator for value function is called an "Actor-Critic" family of Reinforcement Learning algorithms.
BTW, it doesn't look like your value function "stabilizes" during training. And it also doesn't change too much if you look at the vertical scale of your plot.
Surrogate Loss. In practice, the policy gradient optimization step above suffers from instabilities. The gradient step tends to change the policy too strongly, which makes the approximation error of the value function too large.
To deal with this, the TRPO/PPO algorithms introduce a kind of clipping of the loss gradient that constrains the policy gradient changes from being too large. The new function that produces these clipped/constrained gradients is called a "surrogate loss".
mean_noise_std. This doesn't look like a standard name for anything, but I suspect that this is a version of PPO with artificial noise added for better exploration of the agent.


What are the main advantages of using declarative programming languages for building AI?

There's no objective reason to state that declarative languages are better suited for AI development. However, there's indeed a bias towards them in practice. Although most functional languages are impure (that is, they allow side effects), and such can't count as "declarative", a few languages are purely functional (that is, they don't allow side effects), most prominently Haskell. Purity is key here. In Haskell, even I/O is pure.

The key difference between imperative languages and (purely) functional languages is in the way they describe the program. An imperative program describes how to do stuff, that is, algorithms. It specifies the specific instructions that the machine must carry on in order to perform the computation. OTOH, purely functional languages describe what is to be computed, that is, the relationship between the input and the output. In mathematics, "function" is just a fancy name for a relationship between an input and an output.

Again, in the mathematical sense, the only variability is that of the function's arguments. That is, the function's output depends solely on its input (arguments). This is known as referential transparency. Referential transparency states that:

$$
\forall f \in \varphi, \forall x \in \delta_f, fx = fx
$$

Where $\varphi$ is the set of all functions, and $\delta_f$ is $f$'s domain. For the typical imperative language's definition of "function", the above doesn't hold. For instance, C's getchar() does not always return the same value.

Let's say we want to calculate the set of the ten least prime numbers whose least significant digit is $3$. First, in mathematical notation:

$$
\mathbb{S} = \mathbb{G}_{10} = \{ x \mid x \in \{ p \mid p \in \mathbb{N} \setminus \{0, 1 \} \text{ and } (\forall q \in \mathbb{N} \setminus \{0, 1, p \}, p \text{ mod } q = 0) \},  x \text{ mod } 10 = 3 \}
$$

Where G(n, s) is the set of the lesser nth elements from s. In mathematics, you don't worry about how is the set $\mathbb{S}$ supposed to be computed, but rather about $\mathbb{S}$'s definition itself.

Now, in Python (in imperative style):

def is_prime(n):
  for x in range(2, n):
    if n % x == 0:
      return False

  return True

def foo():
  s = set()
  n = 2
  while len(s) < 10:
    if is_prime(n) and n % 10 == 3:
       s.append(n)

  return set(s)

In Python, we care about (and are responsible for) the algorithm being used to compute the set. We specify, pretty much in recipe-style, how to build the set from scratch. If there's an algorithm that may be better suited for checking whether a number is prime or odd, but we don't use it, it's our fault, not Python's.

Finally, Haskell steps in:

import qualified Data.Set as Set

isPrime :: Integer -> Bool
isPrime n = ( == 1 ) . length . filter ( == 0 ) . map ( n `mod` ) $ [ 2 .. n ]

s = Set.fromList . take 10 . filter ( ( == 3 ) . ( `mod` 10 ) ) . filter isPrime $ [1..]

Haskell's version is a lot more like the mathematical model than Python is. We define the isPrime function in terms of the constraints that a prime number must obey, not by describing a step-by-step algorithm to do such a check. Moreover, s (the set we have been defining so far) is defined in terms of the constraints its members must obey, rather than in terms of an algorithm to compute s itself. The compiler, more often than not The Glorious Glasgow Haskell Compilation System (a.k.a GHC), is the one responsible for generating an algorithm. GHC's optimizer is known to be one of the strongest in the world, not because its the best compiler of 'em all, but because Haskell's nature allows for this.

Haskell (and other functional languages), in summary, have several features that make it look, taste, and behave like pure math:

Referential transparency and purity.
Haskell is lazy.
A very strong type system, with such exotic (but very useful!) stuff as recursive (and algebraic) data types.

So, the bottom line is that AI researchers often prefer functional languages over imperative languages (or, more assertively, pure over impure languages), because they are attempting to define artificial intelligence itself, by means of functions (relationship between an input and an output). At the end, we do this because we have no real algorithm for human-level intelligence to raise from a handful of transistors. Also, there's been a historical bias towards these kind of languages, starting with John McCarthy, Lisp's creator and a pioneer in early AI research.


Is a binary attribute type the same as binomial attribute type?

@SmallChess's answer is a good start, but there are some additional parts to the question.

binary variables or binary data consist of data with the values 0 or 1, and no other values. We usually don't talk about "binary distributions", because it's only data, variables, or outcomes that can be binary. A distribution might produce binary data, but is not itself binary because its parameters typically take on real-values.

A binomial distribution is a distribution that produces binary data. In particular, it is a random process that produces the value 1 with probability $$p$$, and the value 0 with probability $$1-p$$. Notice that although it makes binary data, it is not itself a kind of data, and is in fact charactorized by a non-binary number (p).

Boolean data takes on the values true or false. Often, but not always, these are stored as 0's and 1's. The distinction is that boolean data may not be stored numerically. There might also be different expectations about how Boolean data should be processed (for instance, $$true + true = true$$, but $1 + 1 = 2$.

I am not aware of the term polynomial being applied to data. However, multinomial distributions are probability distributions that produce 0 with probability $p_0$, 1 with probability $p_1$, 2 with probability $p_2$, and so on, producing $p_n$ with probability $1 - \sum_{i=0}^{n-1} p_i$ for $n$ different numbers. Like binomial distributions, multinomial distributions are characterized by a set of real-valued numbers, and are distinct from the kind of data they generate.

Categorical data takes on values from a set of categories. The example you give (yes, no, maybe) is not strictly multinomial data, but could be generated from a multinomial distribution by mapping the values 0, 1 and 2 onto yes, no and maybe. Note again that categorical data might be non-numeric. Operations like adding might be non-sensical.

Cardinal data isn't something you asked about, but arises when data can be nicely ordered. For example, playing cards are easily mapped to the numbers 1-13, and can have reasonable semantic meaning when represented this way (e.g. A + 2 = 3, and 1 + 2 = 3).

Nominal Data is just literal numbers that mean exactly what they purport to mean. For example, if you store the number of cans of beer a customer purchased, that would be nominal data.