Will robots rebel against their human creators? There are several science fiction movies where the robots rebel against their creators: for example, the Terminator's series or I Robot.

In the future, is it possible that robots will rebel against their human creators (like in the mentioned movies)?

I don't like to be a killjoy, but this question seems premature (that's why it's hd the "mythology of AI" tag added to it). The kinds of emergent artificial general intelligence depicted in the movies you mention are in science fiction films because they are science fiction. Most AI researchers do not think they are likely to appear anytime soon. The overwhelming majority of researchers think the most likely times for such a system to appear are "More than 50 years [from now]" or "Never". In part, this is because AI researchers thought we were close to such systems for several decades, despite failing to create them. This suggests that making an artificial general intelligence is much harder than we might expect.

Despite AGI being a long show, there's a lot of recent interest in the AI research community in the social impact of our technologies. The study of these systems is called "ethical AI", and this is the path that the research community as a whole has begun to embark on. A promising approach is to model the process by which humans decide to treat each other well, in the hopes of creating programs act according to that process.


What is the difference between expected return and value function? I've seen numerous mathematical explanations of reward, value functions $V(s)$, and return functions. The reward provides an immediate return for being in a specific state. The better the reward, the better the state.

As I understand it, it can be better to be in a low-reward state sometimes because we can accumulate more long term, which is where the expected return function comes in. An expected return, return or cumulative reward function effectively adds up the rewards from the current state to the goal state. This implies it's model-based. However, it seems a value function does exactly the same.

Is a value function a return function? Or are they different?

There is a strong relationship between a value function and a return. Namely that a value function calculates the expected return from being in a certain state, or taking a specific action in a specific state. A value function is not a "return function", it is an "expected return function" and that is an important difference.

A return is a measured value (or a random variable, when discussed in the abstract) representing the actual (discounted) sum of rewards seen following a specific state or state/action pair.

Typically there is no need to express an individual return as a "return function", although you may find many formulae in RL for sampling or estimating specific return values in order to calculate targets or errors for the value function.

  A return (or cumulative reward) function effectively adds up the rewards from the current state to the goal state. This implies it's model-based.

If you have a simple MDP, already accurately modelled, where you can calculate expected return directly from that model, then, yes, in theory, that would be a value function. However, this could be more computationally intensive to resolve than dynamic programming (e.g. Policy Iteration or Value Iteration), and in many cases you don't have any such model, but can still apply RL approaches to learn a value function from experience.


Choosing the right neural network settings I'm trying to train a neural network on evaluating chess positions if rather white (0.0) or black would win (1.0)

Currently the input consists of 4 bits per chess field (piece id 0 - 12, equals 64*4). Factors like castling are being ignored for now. Also, all training sets are random positions from popular games where it's white's turn and the desired output is the outcome of the game (0.0, 0.5, 1.0).

Are my input values the right choice?
How many hidden layers / neurons for each layer should be used and what's the best learning rate?
What type of NN's and which activation function would you recommend for this project?

Easy ones first:

Activations are going to be RELU all the way down, until your final softmax layer (win probability?) (because empirically, RELU does great on most problems, except when your model is an RNN, and it makes the gradient explode, or in the final layer of a regression model - numerical stability etc.).
You probably to structure this with some layers of convolutions with max pooling between them, then 1 or 2 fully connected layers (FC) near the end (because if you only have FC layers, you probably won't have enough data to train them)
Well worth trying some 1D convolutions (which cleverly combine channels from convolutions created by previous layers).
Learning rate: take the SGD default to begin with, then tune later. Problem dependent, I'm afraid!  The returns to tuning can be large though (my kids twigged to this quite quickly when playing with a toy problem).

Now the hard bit - encoding your input:

Categorical encoding using a single integer per board position could cause your model some grief (it is an input that "looks like" a real number, but of course it isn't, and values that seem numerically close may represent pieces with radically different abilities (perhaps the code for King is 1 and Queen is 2 and Bishop is 3, but all those pieces have such different attributes).
I would strongly consider thinking of each piece/player combo as a "colour channel" - a 64 cell grid where each value is either zero or one (so, one channel for White's pawns, another for White's knights, and so on).

Finally, those labels of yours: do think about what you'll do with drawn games - perhaps you have 3 possible outcomes, not 2?

We would all be fascinated to hear how you get on - I hope you'll write your work up in some form (and that you'll come back and complain/praise our advice, as appropriate!).


In reinforcement learning, is the value of terminal/goal state always zero? Let's assume we are in a $3 \times 3$ grid world with states numbered as $0,1, \dots, 8$. Suppose that the goal state is $8$, the reward of landing in the goal state is $10$, and the reward of just wandering around in the grid world is $0$. Is the state-value of state $8$ always $0$?

In reinforcement learning, is the value of terminal/goal state always zero?

Yes, always for episodic problems, the value of a terminal state is always zero, from the definition.
The value of a state $v(s)$ is the expected sum (perhaps discounted) of rewards from all future time steps. There are no future time steps when in a terminal state, so this sum must be zero.
For the sake of consistent maths notation, you can consider a terminal state to be "absorbing", i.e. any transition out of it results in zero reward and returning to the same terminal state. Then you can use the definition of value function to show the same thing:
$$v_{\pi}(s) = \mathbb{E}_{\pi}[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_{t} = s]$$
If $s = s_T$, the terminal state, then all the "future rewards" from $k=0$ onwards starting with reward $R_{t+1}$ must be zero. This is consistent with the reward $R_{t}$, i.e. the reward when transitioning to the terminal state, being any value.
You can show similar using action value functions, if you accept a "null" action in the terminal state.


If the i.i.d. assumption holds, shouldn't the training and validation trends be exactly the same? If the i.i.d. (independent and identically distributed) assumption holds for a training-validation set pair, shouldn't their loss trends be exactly the same, since every batch from the validation set is equivalent to having a batch from the training set instead?

If the assumption was to be true wouldn't that make any method that was aware of the fact that there were two separate sets (regularization methods such as early stopping) meaningless?

Do we work with the fact that there is a certain degree of wrongness to the assumption or am I interpreting it wrongly?

P.S - The question stems from an observation made on MNIST (where I suppose the i.i.d assumption holds strongly). The training and validation trends (losses and accuracy both) on MNIST were almost exactly identical for any network (convolutional and feedforward) trained using negative log-likelihood, making regularization meaningless.

If the i.i.d (independent and identically distributed) assumption holds, shouldn't the training and validation trends be exactly the same?

No, not necessarily. Let me explain why.

If you assume your samples (aka examples, observations, data points, etc.) are i.i.d., this means

that they come from the same distribution, e.g. a Gaussian $\mathcal{N}(0, 1)$ (the identically distributed part), and
that they are independently drawn from it, i.e., intuitively, each sample provides the same kind of information independently of the others

However, even if samples are independently drawn from a certain distribution, they can be different. For example, if you draw a sample $x$ from $\mathcal{N}(0, 1)$, an operation often denoted as $x \sim \mathcal{N}(0, 1)$, $x$ could have the value $0$, $1$, $13$ or $50$ (or any other number), so they could be variable, although your samples will tend to be mainly around $0$, because that's where your Gaussian puts more density (and your standard deviation is just $1$). If your standard deviation was higher, then there would be even more variability in the sampling process.

So, if you assume that your samples are independently drawn from a certain distribution, it doesn't mean that you will always get the same pattern of samples. In other words, you can still have variability in your samples, and this also depends on the distribution you sample from.

To answer your question more directly, there's a chance that your training data and your validation data don't necessarily have the same patterns, even if the independence assumption holds. Therefore, the training and validation trends (and I assume you mean e.g. the performance) are not necessarily the same, but, although this may also depend on the training method, I would say that they shouldn't be very different (if the assumption holds) because, intuitively, each sample should be as informative as any other sample (independence assumption).

  Do we work with the fact that there is a certain degree of wrongness to the assumption or am I interpreting it wrongly?

It is often convenient to make the i.i.d. assumption even, if it doesn't hold, for several reasons:

your training procedure may converge faster (because, intuitively, each sample will be as informative as any other sample)
your models may be simpler (e.g., in naive Bayes, you make the i.i.d. assumption only to simplify the model and, in general, the mathematical formulations)

Sometimes, if it doesn't hold, your training procedure can be highly affected. In those cases, you can find workarounds and try to make it hold. For example, the usage of the experience replay in deep Q-learning is an example of a trick used to overcome the dependence of successive samples, which causes learning to be highly variable. See this question Why exactly do neural networks require i.i.d. data?.

The answers to the question On the importance of the i.i.d. assumption in statistical learning on CrossValidated provide more information and details, so you may want to have a look at it too. Here's another answer, which is related to shuffling and how it can or not make the independence assumption hold, that I highly recommend that you read.


How to manually collect rectangular training data samples from images? I want to collect training samples from images.
That can mean different things depending on the context. I think of the simplest case, which should be most commonly required. Because it is so common, there may be a standard tool for it.
An example would be to have a collection of images of random street scenes and manually collect images of nonoccluded cars from them into separate files.
What is a common way or tool to do this:
For a large number of images, select one or more rectangles (of arbitrary size and with edges parallel to the image edges) in the image and save them to separate image files.
Of course, it can be done with any general image editing program, but in this case, most of the work time would be used for opening new images, closing old images, saving sample images and the most time-consuming part of entering a non-conflicting file name for the individual sample image files.
For small numbers of samples per input file, this may need about an order of magnitude more time, and also more complex interaction.
I would prefer a tool running on Linux/Ubuntu.
If this does not exist, I'd be curious why.

Maybe LabelImg is what you are looking for?

LabelImg is a graphical image annotation tool and label object
bounding boxes in images.

If not, maybe you can find other options for your problem on this summary of computer vision tools.


Which NLP applications are based on recurrent neural networks? Some of the NLP applications taken from this link NLP Applications:

Machine Translation
Speech Recognition
Sentiment Analysis
Question Answering
Automatic Summarization
Chatbots
Market Intelligence
Text Classification
Character Recognition
Spell Check

Which are the NLP applications that supports recurrent neural network?

Speech recognition and Character recognition are not part of NLP. Everything else on your list can in principle be done with RNNs. But the field is quickly moving towards using transformers.


Cold start collaborative filtering with NLP I’m looking to match two pieces of text - e.g. IMDb movie descriptions and each person’s description of the type of movies they like. I have an existing set of ~5000 matches between the two. I particularly want to overcome the cold-start problem: what movies to recommend to a new user? When a new movie comes out, to which users should it be recommended? I see two options:

Run each description of a person through an LSTM; do the same for each movie description; concatenate the results for some subset of possible combinations of people and movies, and attach to a dense net to then predict whether it’s a match or not
Attempt to augment collaborative filtering with the output from running the movie description and person description through a text learner.

Are these tractable approaches?

From what I understood you will not have any cold start problem because you basically process the user preferences description against movies descriptions to get recommendations. So you don't use other users feedback at any time of the process which is not collaborative filtering.

  Here is instead the approach I would suggest in your case to get movies recommendations for each user:

Compute the similarity between the user description and each movie description. This can be done using the Universal Sentence Encoder. It's an 2018 paper by Google which represents any sentence as a vector of 215 values (i.e embeddings).
The semantic similarity between 2 sentences is computed using the dot product of their embeddings. Fortunately, the implementation was integrated to Tensorflow Hub and easily be used (see my answer here for details).
Choose the highest similarity values and recommend the corresponding movies to the user. Notice that you can still use this approach along with a collaborative filtering one.


Should forecasting with neural networks only be treated as a supervised learning (regression) problem? I have recently made a work about the application of neural networks to time series forecasting, and I treated this as a supervised learning (regression) problem. I have come across the suggestion of treating this problem as an unsupervised, semi-supervised, or reinforcement learning problem. The ones that made this suggestion didn't know how to explain this approach and I haven't found any paper of this. So I found myself now trying to figure it out without any success. To my understanding:
Unsupervised learning problems (clustering and segmentation reduction) and semi-supervised learning problems (semi-supervised clustering and semi-supervised classification) can be used to decompose the time series but not forecast it.
Reinforcement learning problems (model-based and non-model-based on/off-policy) is to decision taken problems, not to forecast.
It is possible to treat forecasting time series with neural networks as an unsupervised, semi-supervised, or reinforcement learning problem? How it is done?

I think the choice of technique strongly depends on how fine-grained your forecast-predictions need to be.
When it comes to forecasting by Reinforcement Learning (RL), one prominent example is the stock-trading RL agent. The agent must decide which stock to buy or sell, thereby drawing upon predictions concerting the expected future development of some stock.
Given this approach, you would not necessarily let the RL agent explicitly generate estimates of how stock prices are gonna develop at any point, but instead you would only observe the predicted decision concerning whether to buy or sell etc.
But if you think hard enough, I am certain that you could come up with setups of RL agents that would allow you to explicitly generate future estimates of values to be forecast. In this case, the final buy/sell decision would have to depend on the explicit future stock price predictions to enforce accurate predictions.
Concerning unsupervised learning, you could cluster data points (training samples) with respect to how some value(s) of interest changed $t$ time steps in the future (after having observed the training sample). Then, you could associate clusters with rough forecast-estimates. After all, you would treat the forecast value as a label associated with data points.
Afterwards, you could use some kind of nearest neighbor approach to determine which cluster is closest to some novel data sample. Then, you take as a prediction for the new data sample the forecast prediction (i.e. label) that is associated with the closest cluster/prototype etc. But strictly speaking, as soon as you start turning forecast values (which were previously part of some unlabeled time-series dataset) into labels, you turn the training procedure of course into a supervised technique again.
How well especially the latter training approach would work, I can't tell since I have never heard anyone using this method. But if training data is too scarce to employ some deep learning method, why not giving it at least a try if accuracy doesn't have to be too precise?
After all, it's just a matter of creativity and testing which method works best given your specific machine learning problem at hand.


What is an activity vector in capsule neural networks? I was reading the paper Dynamic Routing Between Capsules and didn't understand the term "activity vector" in the abstract.

  A capsule is a group of neurons whose activity vector represents the instantiation parameters of a specific type of entity such as an object or object part. We use the length of the activity vector to represent the probability that the entity exists and its orientation to represent the instantiation parameters. Active capsules at one level make predictions, via transformation matrices, for the instantiation parameters of higher-level capsules. When multiple predictions agree, a higher level capsule becomes active. We show that a discrimininatively trained, multi-layer capsule system achieves state-of-the-art performance on MNIST and is considerably better than a convolutional net at recognizing highly overlapping digits. To achieve these results we use an iterative routing-by-agreement mechanism: A lower-level capsule prefers to send its output to higher level capsules whose activity vectors have a big scalar product with the prediction coming from the lower-level capsule.

I thought a vector is like an array of data that you are running through the network.

I started working through Andrew Ng's deep learning course, but it's all new and terms go over my head.

In a traditional neural network, the network's vertices are neurons and the output of a single neuron is a single value (a "scalar"). This number is called its activation. A layer of neurons in the network outputs a vector of activations. We should not confuse this with the activity vectors in a Capsule Network.
Capsule Networks are different since the network vertices are Capsules rather than neurons. They are a higher-dimensional: the output of a Capsule is not a scalar but a vector representing a group of parameters related to the input. Hence the name activation vector.
Motivation
In a neural network, there is no inherent structure between the scalar outputs of the neurons, this is something the following layers have to learn. In Capsule Networks the output of a capsule represents all the parameters related to that together in a vector including a prediction for the activation of deeper layer Capsules. This adds a useful local structure.
For example, consider face recognition. If you have a capsule that knows how to recognize eyes it could output an activity vector representing e.g. "since I have recognized an eye position $(x,y)$ with probability $p=0.97$ I predict the parameters for the whole face will be $(f_1,\dots, f_n)$".
As explained in the Dynamic Routing Between Capsules paper you refer to this information is then used in the way that the capsules in earlier layers (the parts: eye, mouth, nose) predict the activations of deeper layers (face). For example, a face recognizer will only be strongly activated when there is an agreement between the eye, nose and mouth recognizers (the parts) and the face recognizer (the whole) about where the face is located (the $(f_1,\dots, f_n)$ parameters).
Historical Inspiration
Older computer vision algorithms like SIFT work in a similar way where recognition is based on agreement between the configuration of multi-dimensional features (key points) and the reference configuration.


Positioning of batch normalization layer when converting strided convolution to convolution + blurpool I'm trying to replace the strided convolutions of Keras' MobileNet implementation with the ConvBlurPool operation as defined in the Making Convolutional Networks Shift-Invariant Again paper. In the paper, a ConvBlurPool is implemented as follows:

$$
Relu \circ Conv_{k,s} \rightarrow Subsample_s \circ Blur_m \circ Relu \circ Conv_{k,1}
$$
where k is the convolution's output kernels, s is the stride, m is the blurring kernel size and the subsample+blur is implemented as a strided convolution with a constant kernel.

My issues start when batch normalization enter the picture.
In MobileNet, a conv block is defined as follows (omitting the zero-padding):

$$
Relu \circ BatchNorm \circ Conv_{k,s}
$$

I am leaning towards converting it to:

$$
Subsample_s \circ Blur_m \circ Relu \circ BatchNorm \circ Conv_{k,1}
$$

i.e., putting the BN before the activation as it's normally done. This is not equivalent though, because the first BN operates on the downsampled signal.

Another possibility would be:

$$
BatchNorm \circ Subsample_s \circ Blur_m \circ Relu \circ Conv_{k,1}
$$

with the BN as last operation. This is also not equivalent, because now the BN comes after the ReLu.

Is there any reason to prefer one option over the other? Are there any other options I'm not considering?

After finding the paper authors' Github, I saw that, although they only have a MobileNet V2 model implemented, they choose the Subsample-after-ReLu option (the first one in the question).
Although this doesn't fully answer my question, I'll take "the paper authors do it this way" as enough reason to prefer this over the alternative.


When training a DQN, how should we update the value of actions that were not taken? Let's say that we have three actions. The highest-valued action of the three choices is the first. When training the DQN, what do we do with the other two, as we don't have a target for them, since they weren't taken?
I've seen some code that leaves the target for off actions as whatever the prediction returned, which feels a bit wrong to me as two or more similar behaving actions might never be differentiated well after random action selection dwindles.
I've also seen some implementations that set the target for all actions to zero and only adjust the target for the action taken. This would help regarding action differentiation long term, but it also puts more reliance on taking random actions for any unfamiliar states (I believe) as an off action might never be taken otherwise.

The loss function for DQN algorithm is
\begin{equation}
L(\theta_i) = \mathbb E_{s, a, r, s'} [(y - Q(s, a;\theta_i))^2]
\end{equation}
Like you said, we only take one action per timestep. We can only shift weights of the network that had the effect in calculating action value $Q(s, a)$ for that particular action that we took. For that action, variable $y$ would have value
\begin{equation}
y = r + \gamma \max_{a'} Q(s', a', \theta^-_i)
\end{equation}
and we would have standard form of DQN loss. We calculate the gradient of that loss with respect to network parameters $\theta$, backprop it and slightly shift weights so to more accurately estimate $Q(s, a)$ for that specific state-action pair.

We never took other actions. Since we never took them we didn't get reward $r$ and we can't estimate $\max_{a'} Q(s', a', \theta^-_i)$ for those other actions. We don't want to change weights that had effect on calculating actions values for those other actions because we have no way of estimating how accurate they were. Standard approach is to set
\begin{equation}
y = Q(s, a;\theta_i)
\end{equation}
this way the loss for those other actions would be $0$ and it would result in not changing the weights that had influence in calculating their action values.

Setting target $y$ to $0$ for all other actions would mean that we want $Q(s, a)$ for them all to slightly shift to $0$. That would not be correct since we have no way of knowing their true value. I think you misinterpreted that part in the implementations.


Does the neural network calculate different relations between inputs automatically? Suppose you want to predict the price of some stock. Let's say you use the following features.

OpenPrice
HighPrice
LowPrice
ClosePrice

Is it useful to create new features like the following ones?

BodySize = ClosePrice - OpenPrice

or the size of the tail

TailUp = HighPrice - Max(OpenPrice, ClosePrice)

Or we don't need to do that because we are adding noise and the neural network is going to calculate those values inside?

The case of the body size maybe is a bit different from the tail, because for the tail we need to use a non-linear function (the max operation). So maybe is it important to add the input when it is not a linear relationship between the other inputs not if it's linear?

Another example. Consider a box, with height $X$, width $Y$ and length $Z$.
And suppose the real important input is the volume, will the neural network discover that the correlation is $X * Y * Z$? Or we need to put the volume as input too?

Sorry if it's a dumb question but I'm trying to understand what is doing internally the neural network with the inputs, if it's finding (somehow) all the mathematically possible relations between all the inputs or we need to specify the relations between the inputs that we consider important (heuristically) for the problem to solve?

On paper, one expects a complex enough network to determine any complicated function of a limited number of inputs, given a large enough dataset. But in practice, there is no limit to the possible difficulty of the function to be learnt, and the datasets can be relatively small on occasion. In such cases - or arguably in general - it is definitely a good idea to define some combination of the inputs depending on some heuristics as you suggested. If you think some combination of inputs is an important variable by itself, you definitely should include it in your inputs.

We can visualize this situation in TensorFlow playground. Consider the circular pattern dataset on top left corner with some noise. You can use the default setting: $x_1$ and $x_2$ as inputs with 2 hidden layers with 4 and 2 neurons respectively. It should learn the pattern in less than 100 epochs. But if you reduce the number of neurons in the second layer to 2, it is not going to get as good as before. So, you are making the model more complicated to get the correct answer.

You can experiment and see that one needs at least one 3 neuron layer to get the correct classification from just $x_1$ and $x_2$. Now, if we examine the dataset, we see the circles so we know that instead of $x_1$ and $x_2$, we can try $x_1^2$ and $x_2^2$. This will learn perfectly without any hidden layers as the function is linear in these parameters. The lesson to be learnt here is that, our prior knowledge of the circle ($x_1^2 + x_2^2 = r^2$)  and familiarity with the data helped us in getting a good result with a simpler model (smaller number of neurons), by using derived inputs.

Take the spiral data at the lower right corner for a more challenging problem. For this one, if you do not use any derived features, it is not likely to give you the correct result, even with several hidden layers. Keep in mind that every extra neuron is a potential source of overfitting, on top of being a computational burden.

Of course the problem here is overly simplified but I expect the situation to be more or less the same for any complicated problem. In practice, we do not have infinite datasets or infinite compute times and the model complexity is always a restriction, so if you have any reason to think some relation between your inputs is relevant for your final result, you definitely should include it by hand at the beginning.


What is the relation between the context in contextual bandits and the state in reinforcement learning? Conceptually, in general, how is the context being handled in contextual bandits (CB), compared to states in reinforcement learning (RL)?
Specifically, in RL, we can use a function approximator (e.g. a neural network) to generalize to other states. Would that also be possible or desirable in the CB setting?
In general, what is the relation between the context in CB and the state in RL?

The notion of a state in reinforcement learning is (more or less) the same as the notion of a context in contextual bandits. The main difference is that, in reinforcement learning, an action $a_t$ in state $s_t$ not only affects the reward $r_r$ that the agent will get but it will also affect the next state $s_{t+1}$ the agent will end up in, while, in contextual bandits (aka associative search problems), an action $a_t$ in the state $s_t$ only affects the reward $r_r$ that you will get, but it doesn't affect the next state the agent will end up in. The typical problem that can be formulated as a contextual bandit problem is a recommender system.
In CBs, like in RL, the agent also needs to learn a policy, i.e. a function from states to actions, but actions that you take in a certain state are independent of the actions you take in other states.
So, as Sutton and Barto put it (2nd edition, section 2.9, page 41), contextual bandits are an intermediate problem between (context-free) bandits (where there is only one state or, equivalently, no state at all) and the full reinforcement learning problem.
Another important characteristic of many RL algorithms, such as Q-learning, is that they assume that the state is Markov, i.e. it contains all necessary info to take the optimal action, but, of course, RL is not just applicable to fully observable MDPs. In fact, even Q-learning has been applied to POMDPs, with some approximations and tricks.
Regarding the use of neural networks to approximate $q(s, a)$ or a policy in CBs, in principle, this is possible. However, given that the optimal action in a state $s$ is independent of the optimal action in another state $s'$, this is probably not useful, but I cannot guarantee you that this has not been successfully done, because I've not yet read the relevant literature (maybe someone else will provide another answer to address this aspect).


Recommended Time serie forecasting model for Fibonacci levels classification I have a set of time series data which gives me fibonacci levels and the duration at which the value is at this level.
Data structure to look like:
Date / Duration (minutes) / Level

201201 / 380 / 2
.....

210422 / 400 / 4

I'd like to create a NN model (LSTM maybe) that would forecast the next level, the probability it reaches it and this for several steps ahead (1 step = 400 minutes).
Which time series forecasting model would you recommend ?
Thanks in advance.

It seems like you are trying to produce two outputs here. This usually makes the models more complex. What if you only predicted the Fibonacci levels for each time step? Then count how many time steps it stays at that level.
As for producing the Fibonacci levels themselves, you can look into categorical time series where the values are categories instead of real numbers.
You have a many-to-one problem. So, yes the model takes two inputs, Duration and Level, but only produces one output, the Level.
The times septs in a model will always be the same. You have to choose a range that is appropriate and all your predictions will be based on that. It's important to note that finding the best time step size is a trial and error process. For example, you could first try using 10 time steps and if you find the model needs more you retrain it with 20 and compare the results.


How is the error calculated with multiple output neurons in the neural network? Machine Learning books generally explains that the error calculated for a given sample $i$ is:
$e_i = y_i - \hat{y_i}$
Where $\hat{y}$ is the target output and $y$ is the actual output given by the network. So, a loss function $L$ is calculated:
$L = \frac{1}{2N}\sum^{N}_{i=1}(e_i)^2$
The above scenario is explained for a binary classification/regression problem. Now, let's assume a MLP network with $m$ neurons in the output layer for a multiclass classification problem (generally one neuron per class).
What changes in the equations above? Since we now have multiple outputs, both $e_i$ and $y_i$ should be a vector?

Assuming you're using softmax on the last layer for classification, it sounds like a simple application of cross entropy loss from here on out: https://datascience.stackexchange.com/questions/20296/cross-entropy-loss-explanation
Edit:


Using a DQN with a variable amount of Valid Moves per turn for a Board Game I have created a game on an 8x8 grid and there are 4 pieces which can move essentially like checkers pieces (Forward left or Forward right only). I have implemented a DQN in order to pull this off.

Here is how I have mapped my moves:

self.actions = {"1fl": 0, "1fr": 1,"2fl": 2,
  "2fr": 3,"3fl": 4, "3fr": 5,"4fl": 6, "4fr": 7}

essentially I assigned each move to an integer value from 0-7 (8 total moves).

  My question is: During any given turn, not all 8 moves are valid, how do I make sure when model.predict(state) the resulting prediction will be a move that is valid? Here is how I am currently handling it.

def act(self, state, env):
    #get the allowed list of actions
    actions_allowed = env.allowed_actions_for_agent()

    #Do a random move if random # greater than epsilon
    if np.random.rand(0,1) <= self.epsilon:
        return actions_allowed[random.randint(0, len(actions_allowed)-1)]

    #get the prediction from the model by passing the current game board
    act_values = self.model.predict(state)

    #Check to see if prediction is in list of valid moves, if so return it
    if np.argmax(act_values[0]) in actions_allowed:
        return np.argmax(act_values[0])

    #If prediction is not valid do a random move instead....
    else:
        if len(actions_allowed) > 0:
            return actions_allowed[random.randint(0,len(actions_allowed)-1)]

I feel like if the agent predicts a move, and if that move is not in the actions_allowed set I should punish the agent.

But because it doesn't pick a valid move I make it do a random one instead, but I think this a problem. Because its bad prediction may ultimately end up still winning the game since the random move may have a positive outcome. I am at a total loss. The agent trains....but it doesn't seem to learn.... I have been training it for over 100k games now, and it only seems to win 10% of it games.... ugh.

Other helpful information:
- I am utilizing experience replay for the DQN which I have based on the code from here:

Here is where I build my model as well:

self.action_size = 8
LENGTH = 8
def build_model(self):
    #builds the NN for Deep-Q Model
    model = Sequential() #establishes a feed forward NN
    model.add(Dense(64,input_shape = (LENGTH,), activation='relu'))
    model.add(Dense(64, activation='relu'))
    model.add(Dense(self.action_size, activation = 'linear'))
    model.compile(loss='mse', optimizer='Adam')

I think instead of:

if np.argmax(act_values[0]) in actions_allowed:
        return np.argmax(act_values[0])

you can use something like:

if np.argmax(actions_allowed_values[0]):
        return np.argmax(actions_allowed_values[0])

So you didn't random your act if the best action is not allowed, but you choose the best action that allowed. You can do that by checking for each action value, whether it is a valid action or not, then take the best value. Or you can change invalid action value to a very small number.


Is there a way to classify sounds To classify images we are using the tensorflow incection v3 NN.

Is there a similar approach to classify sounds? As for example to be able to recognize the person who is talking or classify a general sound?

There are probably many different approaches to doing what you are talking about, but the most common would probably be using long short term memory recurrent neural networks to operate on the data through time. You would be able to train your neural network to do the things that you want to do such as classify the speaker, and classify noises into different categories. However, to train neural networks like these, it requires a lot of training data as does any other deep neural network. So, if you want to apply these kinds of neural networks to practical problems you will need a lot of training data. Or, you could just use a smaller simpler neural network.


How to calculate probability from fuzzy membership grade? Suppose we have the fuzzy membership grade for a person $x$ with a set $S = \text{set of tall people}$ be $0.9$, i.e. $\mu_S(x)=0.9$.
Does this mean that the probability of person $x$ being tall is $0.9$?

No, you can't extract any probability from a fuzzy membership grade. The uncertainty expressed by fuzzy logic is about partial truth, not about probability. $ \mu_S(x) = 0.9 $ doesn't mean that "$ x $ is tall" is true with a probability of 0.9, but that "$ x $ is tall" is 90% true (notice the difference in semantics). You have to think about fuzzy logic as an extension of logic (as its name implies), rather than an extension of probability.
It's true, however, that fuzzy logic is flexible and lets you define how the membership grades are combined in logic formulae, to the extend you can replicate probability theory within the fuzzy logic framework. Wikipedia has a good overview on this: https://en.wikipedia.org/wiki/Fuzzy_logic#Comparison_to_probability.
However, please understand that, in general, fuzzy membership $ \neq $ probability. How we come up with the fuzzy membership grade is subjective and application-dependent. Conversely, probabilities have a well-defined and unambiguous interpretation. The point of being fuzzy is to replicate our reasoning process which, even if is not necessarily formal and rigorous, is often very accurate. To do so it needs a set of (admittedly arbitrary) rules on how to calculate the "truthfulness" of logical formulae. This may turn to be very useful in applications where manipulating probabilities or coming up with them in the first place is not tractable.


Confused with backprop in pytorch with BCE loss I've a prediction matrix(P) of dimension 3x3 and one-hot encoded label matrix(L) of dimension 3x3 as shown below.

    |0.5 0.3 0.1|      |1 0 0|
P = |0.3 0.2 0.1|  L = |0 1 0|
    |0.2 0.5 0.8|      |0 0 1|

each column in 'P' corresponds to prediction of a label in 'L'

How is the BCELoss calculated using pytorch?, my experimentation by giving these two matrices as parameters to loss function yielded me poor results and pytorch's loss calculation function doesn't disclose on how loss calculation is done for this case.
How is the loss averaged for each instance and across the a batch?
if loss is calculated column wise and averaged for each instance and across the batch, then how can loss be backprop'd in pytorch?

Thanks in advance.

BCELoss ( Binary Cross Entropy Loss) is used for binary classifier, which is a neural network that have a binary output, 0 or 1. It is not used for multi-output neural network like your case. For that kind of networks, you can use MSELoss or CrossEntropyLoss as your loss for the network.
For the calculation of BCE, it is shown on pytorch documentation.
https://pytorch.org/docs/stable/nn.html#BCELoss
For across batch, it either sum the loss or take the mean. you can set that through the reduction="" argument.
As i said, the loss is either summed or taken the mean. Then there will be a single value so pytorch can do backdrop.

Hope I can help you


What kind of road and weather conditions can a self-driving car deal with? Can self-driving cars deal with snow, heavy rain, or other weather conditions like these? Can they deal with unusual events, such as ducks on the road?

No, smart cars do not know what to do when surrounded with ducks or flood waters, and it's possible they never will.

As with all machine learning, a computer knows only what it's taught.  If an event arises that's unusual, the AI will have less relevant training on how to respond, so its reaction behavior necessarily will be inferior to its routine "standard operating procedure", for which is has been heavily trained.  (Of course this is true of humans too.)

Due to liability concerns, when encountering an outlier condition, smart cars will almost certainly be designed by their makers to immediately pull off the road and wait to be explicitly told what to do -- by the human in the car or by communicating with a central command office that exists to disambiguate such confusion and resolve cognitive impasses.  When confused, just like a child, a smart car will be designed to seek external assistance -- and is likely to do so indefinitely, I suspect.

That's why, despite Google's recent cars that lack steering wheels, smart cars most certtainly will retain some means of manual control -- be it a wheel and pedals, or at least verbal commands.  Given the many forms of weirdness that are possible on the road, it's possible smart cars will never be fully autonomous.

As for bad weather conditions, how well do smart cars currently perform?  Nobody outside of a car manufacturer can say for certain.  Lidar and radar are superior to the human eye in seeing through fog and snow.  But (competent) humans are likely to remain better than a smart car at dynamically learning the limit of adhesion and compensating (since this is a learned skill few smart cars will already know or can learn quickly -- given this car, these tires, this road surface, this angle of road, etc).

Initially smart cars will turn to the human when the going gets rough, ceding control back to them.  Once smart cars have driven a few million miles in snow, slush, high wind, floods, and ice, and encountered many ducks, angry mooses, and irate pedestrians, they will have been taught to do more for themselves.  Until then, and perhaps for decades yet, I suspect they will turn to mommy and ask for help.


Why am I getting better performance with Thompson sampling than with UCB or $\epsilon$-greedy in a multi-armed bandit problem? I ran a test using 3 strategies for multi-armed bandit: UCB, $\epsilon$-greedy, and Thompson sampling.

The results for the rewards I got are as follows:

Thompson sampling had the highest average reward
UCB was second
$\epsilon$-greedy was third, but relatively close to UCB

Can someone explain to me why the results are like this?

The first thing to note here is that your results seem aligned with the results commonly found in the bandit literature.
Second thing to note would be that the performance of bandit algorithms is usually measured in terms of regret. This is the difference between (i) the amount of rewards accumulated by an oracle policy having prior knowledge about the true rewards of the bandit arms and (ii) the amount of rewards accumulated by the bandit strategy you are evaluating. In other words, this measures the loss your incur due to not knowing what the optimal arm is.
Ideally, the regret should be logarithmic. In theory, all three algorithms achieve logarithmic regret.
See [1] for the regret of decaying $\epsilon$-greedy and UCB and [2] for the regret of Thompson sampling.
Despite their similar regret bounds, these algorithms may behave differently in practice.
For example, according to experiments in [3]:

It appears that Thompson
sampling is more robust than UCB when the delay is long. Thompson sampling alleviates the
influence of delayed feedback$^*$ by randomizing over actions; on the other hand, UCB is deterministic
and suffers a larger regret in case of a sub-optimal choice.

For decaying $\epsilon$-greedy, the fact that it obtained the lowest rewards may be due to the fact that the action selected for exploration is chosen uniformly at random (even if it has a bad reward estimate). In addition, it will explore actions even if they have already been selected many times, unlike UCB which considers the number of action selections to refine the confidence bound.
That said, besides these aspects, there may be other factors that could influence the results obtained by a given bandit algorithm. These may include:

The reward distributions you chose to model your actions, and their
characteristics.
The number of actions you have, and how far each
action’s reward is from the optimal action’s reward.

$^*$ Delayed feedback occurs when the outcome of an action selection is not revealed immediately but after some time delay.


Is it better to rely on an intention file or a database for a web chatbot? Currently, I'm making a chatbot that is going to be functioning in a website, so I was wondering, is it better to train the chatbot with intentions files or use the database as the intention file, if it the latter, then how would I do it? With SQLite or with Excel? Any guides or tutorial would be appreciated.

I'm planning to use Flask + Python + Html for the chatbot.

Recognising intents is only a small step in developing a chatbot. It's fine to use an ML classifier with training data for that, no need to keep the original list of intents.

However, you should really think about the next step: how are you getting your bot to conduct a dialogue, rather than firing off single responses to user queries. That is where things get difficult, and that is also what distinguishes a good chatbot from a simple-minded Eliza-clone.

The programming language/framework you use is not relevant.


Where can I discuss with deep learning beginners? I did some self-study to learn Neural network, object detection, and deep learning. Now I started implementing YOLOv3. I am looking for some website that I can communicate with people and make friends who are learning and implementing deep learning algorithms like me.
It will speed up my learning since self-studying gets boring sometimes.

I was wondering if you could introduce some website that I can find peoples like myself.

I highly recommend to get a local peer group. Meetups might be a good way to get to know some people. As a student at university you also have a lot of other options like going to lectures, creating a student group, organizing a local AI event / hackathon, ...

If this is not possible for you, here is what you can do online:

Reddit: r/deeplearning seems to have a couple of discussions. r/MachineLearning is cool if you want to discuss super recent stuff, but I would not say it is beginner level.
Google+
Coursera: if you take one of their courses, you will see a forum for discussions


How do you distinguish between a complex and a simple model in machine learning? How do you distinguish between a complex and a simple model in machine learning? Which parameters control the complexity or simplicity of a model? Is it the number of inputs, or maybe the number of layers?
Moreover, when should a simple model be used instead of a complex one, and vice-versa?

Consider a continuum of complexity in models.

Trivial: $y = x + a$
Simple: $y = x \, \log \, (a x + b) + c$
Moderately complex: A wind turbine under constant wind velocity
Very complex: Ray tracing of lit 3-D motion scenes to pixels
Astronomically complex: The weather

Now consider a continuum regarding the generality or specificity of models.

Very specific: The robot for the Mars mission has an exact mechanical topology, materials call-out, and set of mechanical coordinates contained in the CAD files used to machine the robot's parts.
Somewhat specific: The formulas guiding the design of an internal combustion engine, which are well known.
Somewhat general: The phenomenon is deterministic and the variables and their domains are known.
Very general: There's probably some model because it works in nature but we know little more.

There are twenty permutations at the above level of granularity. Every one has purpose in mathematical analysis, applied research, engineering, and monetization.

Here are some general correlations between input, output, and layer counts.

Higher complexity often corresponds to larger layer count.
Higher i/o dimensionality corresponds to higher width to the corresponding i/o layers.
Mapping generality to or from specificity generally requires complexity.

Now, to make this answer even less appealing to those who want formula answer they can memorize, ...

Each artificial network is a model of an arbitrary function before training and a model of a specific function afterward.
Loss functions are models of disparity.
An algorithm is a model of a process created by spreading a recursive definition out in time to map into a model of centralized computation called a CPU.
The recursive definition is a model too.

There is almost nothing in science that is a not a model except ideas or data that are not yet modeled.


Intuition behind $\gamma$-discounted state frequency At the appendix A of paper "near-optimal representation learning for hierarchical reinforcement learning", the authors express the $\gamma$-discounted state visitation frequency $d$ of policy $\pi$ as

$$
d=(1-\gamma)A_\pi(I-\gamma^cP_\pi^c)^{-1}\mu\tag 1
$$

I've simplifed the notation for easy reading, hoping it does not introduce any error. In the above definition, $P_\pi^c$ the $c$-step transition matrix under the policy $\pi$, i.e., $P_{\pi}^c=P_\pi(s_{c}|s_0)$, $\mu$ a Dirac $\delta$ distribution centered at start state $s_0$ and
$$
A_\pi=I+\sum_{k=1}^{c-1}\gamma^kP_\pi^k\tag 2
$$
They further give the every-$c$-steps $\gamma$-discounted state frequency of $\pi$ as
$$
d^c_\pi=(1-\gamma^c)(I-\gamma^cP_\pi^c)^{-1}\mu\tag 3
$$
To my best knowledge, $A_\pi$ seems to be the unnormalized $\gamma$-discounted state frequency, but I cannot really make sense of the rest.
I'm hoping that someone can shed some light on these definitions.

Update

Thank @Philip Raeisghasem for pointing out the paper CPO. Here's what I've gotten from that.
Applying the sum of the geometric series to Eq.$(2)$, we have
$$
A={(I-\gamma^cP_\pi^c)(I-\gamma P_\pi)^{-1}}\tag4
$$
Plugging Eq.$(4)$ back into Eq.$(1)$, we get the same result as Eq.$(18)$ in the CPO paper:
$$
d=(1-\gamma)(I-\gamma P_\pi)^{-1}\mu\tag 5
$$
where $(1-\gamma)$ normalizes all weights introduced by $\gamma$ so that they are summed to one. However, I'm still confused. Here are the questions I have

Eq.$(5)$ indicates Eq.$(1)$ is the state frequency in the infinite horizon. But I do not understand why we have it in the hierarchical policy. To my best knowledge, policies here are low-level, which means they are only valid in a short horizon ($c$ steps, for example). Computing state frequency in the infinite horizon here seems confusing.
What should I make of $d_\pi^c$ defined in Eq.$(3)$, originally from Eqs.$(26)$ and $(27)$ in the paper? The authors define them as every-$c$-steps $\gamma$-discounted state frequencies of policy $\pi$. But I do not see why it is the case. To me, they are more like the consequence of Eq.$(30)$ in the paper.

Sorry if anyone feels that this update makes this question too broad. This is kept since I'm not so sure whether I can get a satisfactory answer without these questions.
Any partial answer will be sincerely appreciated. Thanks in advance.

Update: I rewrote the first part due to major mistake in the first version

Notice: The notation $P^k$ from Eq.$(20)$ and $(21)$ in the paper does not mean the kth power of some $P$. Instead, $P^k$ should be thought as the $k$ step transition probability of a non-homogeneous Markov chain.

According to the CPO paper, the discounted future state distribution is defined as
$$
d_\pi(s)=(1-\gamma)\sum_{k=0}^\infty \gamma^kProb(s_k=s|\pi,s_0)\mu(s_0)\tag{1}
$$
Consider function form. Let $Prob_{\pi,k}$ denote the $k$ step probability transition operator induced by $\pi$; here $\pi$ can be a hierarchical policy, $k$ can be larger than $c$.
$$
d_\pi=(1-\gamma)\sum_{k=0}^\infty \gamma^kProb_{\pi,k}\mu\tag{2}
$$
Now apply the similar definition as Eq.$(20)$ and $(21)$ in the paper, let $P^k_\pi$ denote the $k$ step transition probability of the non-homogeneous Markov chain induced by the low level policy, with $k$ smaller or equal to $c$.
\begin{align}
d_\pi&=(1-\gamma)\sum_{m=0}^\infty\gamma^{mc}\sum_{k=0}^{c-1}\gamma^kP^k_\pi(P^c_\pi)^m\mu\\
&=(1-\gamma)\sum_{k=0}^{c-1}\gamma^kP^k_\pi(\sum_{m=0}^\infty\gamma^{mc}(P^c_\pi)^m)\mu\\
&=(1-\gamma)A_\pi(I-\gamma^cP^c)^{-1}\mu\tag{3}
\end{align}
which is exactly the form of Eq.$(22)$ and $(23)$ in the paper, with $A_\pi$ defined similar as Eq.$(24)$ and $(25)$.
The "every-$c$-step discounted state frequency" builds on $(3)$, but it lumps the $c$ steps into one "high level" step where the discount factor is $\gamma^c$ and the transition operator is $P_\pi^c$. Starting with $(3)$, replace $c$ with 1, we get the "every one step future state distribution"
$$
d_\pi=(1-\gamma)(I-\gamma P_\pi)^{-1}\mu\tag{4}
$$
Then replace $\gamma$ and $P_\pi$ in $(4)$ with $\gamma^c$ and $P_\pi^c$, we get the "every-$c$-step discounted state frequency", or "every-$c$-step future state distribution"
$$
d_\pi^c=(1-\gamma^c)(I-\gamma^c P_\pi^c)^{-1}\mu\tag{5}
$$
By the way, I read your blogpost on this paper. It's very helpful for me, thank you!


Standard deviation in the # of neurons per layer In a neural network, by how much does the # of neurons typically vary from layer to layer?

PLEASE NOTE:
I am NOT asking how to find the optimal # of neurons per lyr.

As a hardware design engineer with no practical experience programming neural networks, I would like to glean for example...

By how much does the number of neurons in hidden layers typically vary from that of the input layer?
What is the maximum deviation in the # of hidden lyr neurons to the # of input layer neurons?
How commonly do you see a large spike in the number of neurons?

It likely depends on the application so I would like to hear from as many people as possible. Please tell me about your experience.

Input layers will always have the dimensionality of your input data(for every model I can think of).
See above, the deviation between hidden layers can be significant. For example, 128 in the first hidden and 64 in the rest(or vice versa).
This question in particular will always be problem dependent. It is decided via architecture search or intuition/experience combined with some exploratory search.


Why isn't Nilsson's Sequence Score an admissible heuristic function? I understand what an admissible heuristic is, I just don't know how to tell whether one heuristic is admissible or not. So, in this case, I'd like to know why Nilsson's sequence score heuristic function isn't admissible.

I will use the 8-puzzle game to show you why Nilson's sequence score heuristic function is not admissible.  In the 8-puzzle game, you have a $3 \times 3$ board of (numbered) squares as follows.

+---+---+---+
| 0 | 1 | 2 |
+---+---+---+
| 7 | 8 | 3 |
+---+---+---+
| 6 | 5 | 4 |
+---+---+---+

The numbers in these squares are just used to refer to the specific squares (to avoid saying the "middle square" or the "upper-left square"). So, when I say square 1, I refer to the upper-left square. In these games, you have 8 "tiles". Let's denote these tiles by $A, B, C, D, E, F, G$ and $H$. So, in this game, there is always one square which is free (or empty), given that there are $9$ squares. The goal of this game is to reach the following configuration of tiles

+---+---+---+
| A | B | C |
+---+---+---+
| H |   | D |
+---+---+---+
| G | F | E |
+---+---+---+

Note that, in the case of the 8-puzzle game, a "state" is a configuration of the board. So, the following two board configurations are two distinct states

+---+---+---+
|   | A | C |
+---+---+---+
| H | B | D |
+---+---+---+
| G | F | E |
+---+---+---+

and

+---+---+---+
|   | C | A |
+---+---+---+
| H | B | D |
+---+---+---+
| G | F | E |
+---+---+---+

The rules of the 8-puzzle are simple. You can move one tile (at a time) from its current position (or square) to another position, provided that the destination square is free. You can only move a tile horizontally and vertically (and one square at a time).

I will not explain in this answer how the Nilson's sequence score heuristic works. Here is a explanation of how is used in the case of the 8-puzzle game. You should read this explanation and make sure you understand how Nilson's heuristic works before proceeding! You can also find an explanation of how this heuristic works in the book "Principles of Artificial Intelligence" (at page 85), by Nils J. Nilsson (1982).

  Why isn't then Nilson's sequence score admissible?

A heuristic function $h$ is admissible if $h(n) \leq h^*(n)$, for all states $n$ in the state space, where $h^*(n)$ is the actual distance to reach the goal (which is often unknown in practice, hence the need to use heuristics to estimate such distance).

Note that admissibility is a property that must hold for all states. So, if we find a state where the condition above is not satisfied for the Nilson's sequence score heuristic function, then we show that the Nilson's sequence score is not admissible.

Let us create the following state

+---+---+---+
| A | B | C |
+---+---+---+
|   | H | D |
+---+---+---+
| G | F | E |
+---+---+---+

Note that this state only differs from the goal state by one move: if we move the tile $H$ to square $7$, then we reach the goal state. So, the actual distance to reach the goal state is $1$ move. But what does the Nilson's score function tell us regarding the distance of this state to the goal state? You can see from the algorithm presented in this answer to compute the Nilson's sequence score (of a board configuration) that the score of the configuration (or state) above would be more than $1$ (you can immediately see this because you need to multiply by $3$). Therefore, Nilson's sequence score overestimated the distance to the goal (at least for one state), thus it cannot be admissible (by definition).


AI natural voice generator I want to create a solution, which clones my voice. I tried my commercial solutions or implementation of Tacotron. Unfortunately, results not sound natural, generated voice sounds like a robot. Anybody could recommend good alternative?

The reason for robot like speech may be because tacotron uses griffin lim for vocoder, which cannot reproduce sound with perfection, often introducing robot like sound artifects.

A vocoder is a network that transforms a transform a spectrogram image back to speech waveform. Tacotron and many other speech generation neural network uses CNN to generate spectrogram instead of raw waveforms as output. Spectrogram is a lossy representation of raw audio waveform, so a perfect reconstruction of audio waveform is not possible. Griffin-Lim is a vocoder that uses algorithmic way to transform spectrogram to audio waveform, but often introduces a robot-like quality to generated waveforms. A neural network based vocoder can solve the problem. The wavenet vocoder is often used in speech generation as it can transform the spectrogram to audio with little artifects. Many new speech generation models use the wavenet vocoder as the deafult vocoder of the generation model. For a public implementation, this is a good github repository: https://github.com/r9y9/wavenet_vocoder

You can also use the newer tacotron 2 which uses the wavenet vocoder as the default vocoder. You can check it out here: https://github.com/Rayhane-mamah/Tacotron-2


Why most imperfect information games usually use non machine learning AI? To provide a bit of context, I'm a software engineer & game enthusiast (card games, especially). The thing is I've always been interested in AI oriented to games. In college, I programmed my own Gomoku AI, so I'm a bit familiar with the basic concepts of AI applied to games and have read books & articles about Game Theory as well.
My issue comes when I try to analyze AI's for Imperfect Information games like (Poker, Magic the gathering, Hearthstone, etc). In most cases, when I found an AI for Hearthstone, it was either some sort of Monte Carlo or MinMax strategy. I honestly think, although it might even provide some decent results, it will still be always quite flat and linear, since it doesn't take into account what deck the opponent is playing and almost always tries to follow the same game-plan, since it will not change based on tells your opponent might give away via cards played (a hint that a human would catch).
I would like to know if using Neural Networks would be better than just using a raw evaluation of board state + hands + Hp each turn without taking into account learning about possible threads the opponent might have, how to deny the opponent the best plays he could make, etc.
My intuition tells me that this is way harder and far more complex.
Is that the only reason the NN method is not used? Has there been any research to prove how much efficiency edge would be between those 2 approaches?

A heuristic search using MCTS + minimax + alphabeta pruning is a highly efficient AI planning process. What the AI techniques of reinforcement learning (RL) plus neural networks (NNs) typically add to this is a way to establish better heuristics.

  My intuition tells me that this is way harder and far more complex.

It's not actually that much more complex in concept. Replace the hand-coded heuristic with a learning engine, e.g. DQN or AC3. Train the learning engine from human expert play examples and/or from self play.

It is harder though, because there are many things that can go wrong with an NN-based estimator in a RL context. You will need to make many experiments with different hyper-parameters of the learning engine. For complex games, you may have to invest many 100s of hours of training, which you might want to compare against the end result of a similar amount of time spent refining expert heuristic systems.

For imperfect information games, you may also want to use something that can learn an internal state representation. That could be some kind of explicit belief state that you maintain like an expert system, or something that attempts to learn a good representation, such as an RNN (e.g. LSTM). This may not be necessary for a first try at an agent though, since the MCTS search will make up for some inadequacies of low accuracy heuristics.

  Is that the only reason the NN method is not used?

Up until quite recently, approaches using RL and NN were far harder to find examples of outside of academic machine learning research, and there were not any pre-written frameworks for LSTM or e.g. AC3. In the last few years, RL and NN frameworks have started to appear making an AI self-learning approach far more approachable.

I would expect that many hobby-level coders considering game-playing AI nowadays would seriously take a look at RL and NNs in order to learn robust heuristics for their game projects. However, the "traditional" search-based methods still work in conjunction with these for a completed agent.

  Has there been any research to prove how much efficiency edge would be between those 2 approaches?

For card games, I am not aware of any specific research, although I am just a hobbyist, yet to write any specific game engine more complex than tic-tac-toe.

For perfect information board games, the chess playing variant of AlphaZero demonstrates applicability of RL+NN self-play approach versus "traditional" heuristics plus search (represented by Stockfish). However, the framing of the tournament has been criticised as unfair to Stockfish, so it is not necessarily an open-and-shut case that RL is strictly better.


What is the difference between image processing and computer vision? What is the difference between image processing and computer vision? They are apparently both used in artificial intelligence.

The Wikipedia article related to computer vision gives, in my opinion, a good description of the field and its relation to image processing. Below, I will only cite the most relevant parts of the article.

Computer vision is an interdisciplinary scientific field that deals with how computers can be made to gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to automate tasks that the human visual system can do.
The image data can take many forms, such as video sequences, views from multiple cameras, or multi-dimensional data from a medical scanner.
Sub-domains of computer vision include scene reconstruction, event detection, video tracking, object recognition, 3D pose estimation, learning, indexing, motion estimation, and image restoration.
The fields most closely related to computer vision are image processing, image analysis and machine vision. There is a significant overlap in the range of techniques and applications that these cover. This implies that the basic techniques that are used and developed in these fields are similar, something which can be interpreted as there is only one field with different names. On the other hand, it appears to be necessary for research groups, scientific journals, conferences and companies to present or market themselves as belonging specifically to one of these fields and, hence, various characterizations which distinguish each of the fields from the others have been presented.
Image processing and image analysis tend to focus on 2D images, how to transform one image to another, e.g., by pixel-wise operations such as contrast enhancement, local operations such as edge extraction or noise removal, or geometrical transformations such as rotating the image. This characterization implies that image processing/analysis neither require assumptions nor produce interpretations about the image content.

What is the difference between computer vision and image processing?
Computer vision is about gaining high-level understanding from images or videos. For example, object recognition, which is the task of identifying the type of objects (e.g. apples or humans) in an image, is a computer vision problem. Of course, this task requires a high-level understanding of the image, that is, an understanding of the image similar to the way humans understand visual inputs, given that an apple is a high-level object that is composed of atoms, can be green, etc. For example, a neural network that attempts to classify the type of object in an image (assuming, for simplicity, there is just one type of object) would be a computer vision technique. In computer vision, you receive an image as input and you can produce an image as output or some other type of information (e.g. the type of objects in the image).
On the other hand, image processing does not necessarily imply a high-level understanding of the image. Image processing is a subfield of signal processing but applied to images, which are $2$d signals (or functions of a fixed domain). So, for example, if you have a blurred or noisy image, the task of deblurring or denoising it is part of image processing. The typical tasks in image processing are filtering (e.g. using the Gaussian filter or the mean filter), noise removal, edge detection and color processing. In image processing, you receive an image as input and you produce another image as output.
However, note that, in many cases, to gain a high-level understanding of the images, you first need to e.g. denoise them, so you could use an image processing technique to partially solve a computer vision task. In this sense, computer vision is an interdisciplinary field.
To conclude, computer vision is not a subfield of image processing, given that image processing does not necessarily involve a high-level understanding of images. On the other hand, computer vision can use image processing techniques to gain a high-level understanding of images.


What happens if 2 genes have the same connection but a different innovation number? I have read the Evolving Neural Networks through Augmenting Topologies (NEAT) paper, but some doubts are still bugging me, so I have two questions.

When do mutations occur? Between which nodes?
When mating, what happens if 2 genes have the same connection but a different innovation number? As far as I know, mutations occur randomly and thus it is possible that 2 genomes have the same mutation.

When do mutations occur and between which nodes?

There are two types of mutations in the NEAT model, each of them appears randomly during one epoch on different individuals; the number of structures affected by mutations may vary depending upon the nature of the problem.

A new gene/node is added to the structure and properly linked.
A new connection between two nodes is added.

  When mating, what happens if 2 genes have the same connection but a different innovation number?

During a single epoch/generation every mutation is tracked and if the same mutation appears it can't have the same global innovation number. Same mutation, same innovation number. In that way, during the mating phase, there is no decisional problem which leads to prefer one structure to the other.


Accuracy metric for Clustering I have a model that outputs a latent N-dimensional embedding for all data points, trained in a way that clusters data-points from the same class together, while being separated from other clusters belonging to other different classes.
The N-dimensional embedding is projected down to 2D using UMAP. At each epoch, I wish to test the clustering capability of the model on these 2D projections for use as validation accuracy. I have the labels for each class.
How should I proceed?

You can compute "Silhouette Coefficient" for your aim. Its values mean:

1: Means clusters are well apart from each other and clearly distinguished.
0: Means clusters are indifferent, or we can say that the distance between clusters is not significant.
-1: Means clusters are assigned in the wrong way.

Also other measures such as purity and mutual information can be possible by ``computing an external criterion that evaluates how well the clustering matches the gold standard classes.''.


How to choose the activation function in neuroevolution? I am developing a NEAT flappy bird game, and it doesn't work, the system stays stupid for 300 generations. I chose tanh() for activation, just because it's included in JS.

I can't find a good discussion on the internet of activation functions in the context of neuroevolution, most of what I see is about derivative and other gradient descent issues which I suspect are irrelevant to forward only networks.

If you need a fixed point to answer, I have 8 inputs, one output and the problem is a classification ("jump", "don't jump"). But please explain your answer. I currently use tanh() for all the hidden and output nodes, and the output is considered "jump" if the output neuron value is >0.85

For some context, the code is here: https://github.com/nraynaud/nraygame and the game here: https://nraynaud.github.io/nraygame/

When it comes to genetic algorithms (neuroevolution), you can pretty much evolve any kind of parameters. You just need to have a fairly complex system where each parameter changes the way the inputs are affecting the outputs.

So, to answer your question, any activation function should work! It would be surprising that the activation function is your problem. But if you want to test some activation functions, here's a list of activation functions. But tanh should work perfectly fine.

As I already mentioned in another answer, the key to have a great neuroevolution algorithm is the fitness function. Your rewards should reflect the goal you're aiming for. You didn't mentioned what fitness function you used, but here's what I suggest: reward a player ONLY if he progresses in the game. For example, your fitness function could simply be the distance traveled by your birds. This could maybe solve your problem...


Do you know any examples of geometric deep learning used in industry? I'm interested in the industrial use of GDL (see https://arxiv.org/abs/1611.08097). Is it used in industry? That is, does any company have access to non-Euclidean data and process it directly instead of converting it to a more standard format?

Recursive artificial networks are a type aligned well with GDL, and it is an increasingly popular one. Using non-orthogonal geometries is natural when using directed graphs as semantic association, data flow, or composition networks.

This more free-form approach enters into industry slowly because most programming languages use orthogonal structures designed around multidimensional arrays and nested loops to iterate through them, made popular in the FORTRAN era. It is common that a student learns to loop through an array before learning to call a function or test and branch. Computer science is, in some ways, entrenched in the orthogonal structure.

To call the two categories Euclidean and non-euclidean is inaccurate. The initial trend in machine learning followed a Cartesian paradigm, one locked into 90° angles in data structures. The free-form graph is non-cartesian but still just as Euclidean, as Euclid worked with angles other than 90° frequently.

Apple and Google are likely candidates for this seepage of recursive networks into industry data centers, for NLP applications. Language associations are free-form even though these structures are serialized for speech and written text.

Cognition is also non-cartesian. Graph based optimization (pre-GDL) has been part of cognitive research since the 1970s, especially in the LISP space at MIT and CMU and the U.S. Naval Research facilities for strategic analysis, Optimal strategies for a class of constrained sequential problems by JB Kadane, HA Simon, The Annals of Statistics, 1977. Algorithm 2 is a convergence strategy, but without layers of cells, yet the searching concepts of gradient are already present in the maximal and minimal operations in the search in steps c and f.

The aeronautics and auto industry is a likely candidates for seepage into the embedded computing for automated driving and flight. Most of this is either company confidential or classified.

This answer to the question about topological sophistication provides some background why non-euclidean space may be a more natural way to map associations, flow, and composition.

These are some practical applications.

Convolutional networks on graphs for learning molecular fingerprints by DK Duvenaud, D Maclaurin, J Iparraguirre, Advances in neural, 2015
CD-aware recursive neural networks for jet physics by Gilles Louppe, Kyunghyun Cho, Cyril Becot, Kyle Cranmer, 2019
Stability Properties of Graph Neural Networks by Fernando Gama, Joan Bruna, Alejandro Ribeiro
Isospectralization, or how to hear shape, style, and correspondence by Luca Cosmo, Mikhail Panine, Arianna Rampini, Maks Ovsjanikov, Michael M. Bronstein, Emanuele Rodolà
Fake News Detection on Social Media using Geometric Deep Learning, by Federico Monti, Fabrizio Frasca, Davide Eynard, Damon Mannion, Michael M. Bronstein

We've used recursive networks to align complex models with data acquired during laboratory experimentation and hope to publish on that approach as part of another publication. It is effective, since the relationships between features in the real world form squares and cubes only by chance, so it is not very common. Research into materials and energy cannot be confined by Cartesian conceptions, even if the graphs published are on Cartesian coordinate axes, so that others with traditional analytic geometry backgrounds can understand the graphs quickly.


Type of artificial neural network suitable for learning and then predicting forest growth I'm trying to use an ANN to learn from a large amount of forest measurement data obtained from sampling plots across Ontario, Canada and associated climate data provided by regional climate modelling in this province.

So the following are the inputs to the ANN:

Location (GPS coordinates)
Measurement year and month
Tree species
Age
Soil type
Soil moisture regime
Seasonal or monthly average temperature
Seasonal or monthly average precipitation
Some more data are available to select

And the targets include:
- Average total tree height
- Average tree diameter at breast height

For each sampling plot, the trees have been measured for 1-4 times.
So my question is what type of ANN can best used to learn from the data and then it can be used for predicting with a set of new input data?

My suggestion is not to use an ANN, but instead to use a simpler regression algorithm. The main reason for this is that ANNs take a long time to train, and work better when a lot of data is used. They also require a lot of expertise in parameter tuning to apply well. Since you say you don't have a lot of data, and also don't have a lot of experience using them, I think you will be better off applying something else first. If the other techniques don't work at all, then you might think about using ANNs, but again, they tend to want a lot of data.

If you have tried ordinary least squares regression, and found it does not work well, my next choice would be a Classification And Regression Tree. These models can make good decisions with small amounts of data, and do not require a lot of time to train. They can handle real-valued outputs like the height and width of a tree. Weka's REPTree might be a good starting place.

If Trees don't work out, my next suggestion would be to try regression using a Support Vector Machine. SciKitLearn's SVR is a good choice for this. SVRs can sometimes be very effective when data is limited, because they make assumptions about how to handle data-poor regions that seem to be generally applicable. An SVM can also report low confidence when estimating in those regions. They also train fairly fast when using small amounts of data, and can learn non-linear functions from the data.

If you really want to use an ANN, I would start with a simple Multi-layer perceptron. This model has few parameters to play with, and can probably fit well to your regression. It may make strange decisions in regions with less data however.

Hope this helps!


Why does the discrepancy measure involve a supremum over the hypothesis space? I am referring specifically to the disc defined by Kuznetsov and Mohri in https://arxiv.org/pdf/1803.05814.pdf

This is a kind of worst case path dependent generalization error. But what is the intuitive way of seeing why a worst case is needed? I am probably missing something or reading something incorrectly.

The formula $G=\mathbb{E}\left[ f(Z_{T+1}) \mid \mathbf{Z}_1^T\right] - \sum_{t=1}^Tq_t \mathbb{E}\left[ f(Z_t) \mid \mathbf{Z}_1^{t-1} \right]$ actually represents a set, for all possible values of $f$. Therefore, $\text{disc}(\mathbf{q}) = \operatorname{sup}_{f \in \mathcal{F}} \left( \mathbb{E}\left[ f(Z_{T+1}) \mid \mathbf{Z}_1^T\right] - \sum_{t=1}^Tq_t \mathbb{E}\left[ f(Z_t) \mid \mathbf{Z}_1^{t-1} \right] \right)$ is the element not necessarily in that set $G$ that is greater than all elements in that set $G$, but is the smaller than any other element that is greater than any element in that set $G$. In other words, $\text{disc}(\mathbf{q})$ represents an upper bound on the discrepancy $G$, but it is the smallest possible upper bound. See also this answer for more details about the supremum and the relationship between the supremum and upper bounds.

So, unless I am wrong, this is not necessarily a worst-case analysis (but I am not even sure how one would define the worst-case analysis in this context), but we are looking for the smallest upper bound. In the context of algorithms, the worst-case analysis is with respect to the input (i.e. the worst-case input), but you can have upper or lower bounds for worst and best-case scenarios. See, for example, this answer that illustrates this. Why do we want an upper bound? Because we can be certain that we won't have a generalization error worse than it. You can't do this with e.g. a lower bound.


What is the input to the left most LSTM cell c(t-1) and h(t-1)? Given an LSTM model with 3 cells shown below, what would be the input to the left most cell c(t-1) and h(t-1)?

Your question is related to the initial states of LSTM, where c(t-1) is the cell state (memory) and h(t-1) is the previous LSTM block output.
As pointed out here, it is reasonable to assume that those are random values.


How Machine Learning Studies Correlation? This is my problem:

I have 10 variables that I intend to evaluate two by two (in pairs). I want to know which variables have the strongest relationships with each other. And I'm only interested in evaluating relationships two by two. Well, one suggestion would be to calculate the pairwise correlation coefficient of these variables. And then list the pairs with the highest correlation coefficient to the lowest correlation. That way I would have a ranking between the most correlated to the lowest correlated pairs.

My question is: Is there anything analogous in the world of artificial intelligence to the correlation coefficient calculation? That is, what tools can the world of A.I / Machine Learning offer me to extract this kind of information? So that in the end I can have something like a ranking among the most "correlated" pairs from the point of view of A.I / Machine Learning?

In other words, how do I know which variable among these 10 best "relates" (or "correlates") with variable 7, for example?

Welcome to AI.SE @Laura!

It sounds like you have a series of data points, each with 10 related measurements, and you want automatically assess which of the measurements are most closely related to each other.

You are right that the correlation coefficient is a good choice for this.

Other techniques used in some AI algorithms include the Information Gain measurement (where you measure the reduction in entropy of one variable that follows from partitioning on another one), and embedded feature selection approaches, like the one in this paper.


How does LSTM in deep reinforcement learning differ from experience replay? In the paper Deep Recurrent Q-Learning for Partially Observable MDPs, the author processed the Atari game frames with an LSTM layer at the end. My questions are:

How does this method differ from the experience replay, as they both use past information in the training?
What's the typical application of both techniques?
Can they work together?
If they can work together, does it mean that the state is no longer a single state but a set of contiguous states?

How does this method differ from the experience replay, as they both use past information in the training? What's the typical application of both techniques?

Using a recurrent neural network is one way for an agent to build a model of hidden or unobserved state in order to improve its predictions when direct observations do not give enough information, but a history of observations might give better information. Another way is to learn a Hidden Markov model. Both of these approaches build an internal representation that is effectively considered part of the state when making a decision by the agent. They are a way to approach solving POMDPs.

You can consider using individual frame images from Atari games as state as a POMDP, because each individual frame does not contain information about velocity. Velocity of objects in play is an important concept in many video games. By formulating the problem as a POMDP with individual image inputs, this challenges the agent to find some representation of velocity (or something similar conceptually) from a sequence of images. Technically a NN may also do this using fixed inputs of 4 frames at a time (as per the original DQN Atari paper), but in that case the designers have deliberately "solved" the partially observable part of the problem for the agent in advance, by selecting a better state representation from the start.

Experience replay solves some different problems:

Efficient use of experience, by learning repeatedly from observed transitions. This is important when the agent needs to use a low learning rate, as it does when the environment has stochastic elements or when the agent includes a complex non-linear function approximator like a neural network.
De-correlating samples to avoid problems with function approximators that work best with i.i.d. data. If you didn't effectively shuffle the dataset, the correlations between each time step could cause significant issues with a feed-forward neural network.

These two issues are important to learning stability for neural networks in DQN. Without experience replay, often Q-learning with neural networks will fail to converge at all.

  Can they work together?

Sort of, but not quite directly, because LSTM requires input of multiple related time steps at once, as opposed to randomly sampled individual time steps. However, you could keep a history of longer trajectories, and sample sections from it for the history in order to train a LSTM. This would still achieve the goal of using experience efficiently. Depending on the LSTM architecture, you may need to sample quite long trajectories or even complete episodes in order to do this.

From comments by Muppet, it seems that is even possible to sample more randomly with individual steps by saving LSTM state. For instance, there is a paper "Deep reinforcement learning for time series: playing idealized trading games" where the authors get a working system doing this. I have no experience of this approach myself, and there are theoretical reasons why this may not work in all cases, but it is an option.

  If they can work together, does it mean that the state is no longer a single state but a set of contiguous states?

Not really, the state at any time step is still a single state representation, is separate conceptually from an observation, and is separate conceptually from a trajectory or sequence of states used to train a RNN (other RL approaches such as TD($\lambda$) also require longer trajectories). Using an LSTM implies you have hidden state on each time step (compared to what you are able to observe), and that you hope the LSTM will discover a way to represent it.

One way to think of this is that the state is the current observation, plus a summary of observation history. The original Atari DQN paper simply used the previous three observations hard-coded as this "summary", which appeared to capture enough information to make predicting value functions reliable.

The LSTM approach is partly of interest, because it does not rely on human input to decide how to construct state from the observations, but discovers this by itself. One key goal of deep learning is designs and architectures that are much less dependent on human interpretations of the problem (typically these use feature engineering to assist in learning process). An agent that can work directly from raw observations has solved more of the problem by itself without injection of knowledge by the engineers that built it.


Can a machine learning approach solve this constrained optimisation problem? I had done with different classification, regression and clustering approaches for predictions of values, etc. I was wondering if there is a machine learning approach for distribution of a whole based on some features (I do not know if there is an approach for that I just could not find one with my research).

An easy example might be lets consider we have height and weight data of many children and we have to distribute a given number of pizza slices amongst them so that skinny children get more pizza as compared to obese ones because pizza is more beneficial for skinny as compared to obese. So might have to find out the optimum number of slices for each child out of the total number of slices so that each child gets maximum possible nutrients. A more complex version could incorporate more features like age, overall health, blood sugar content, physical activity index, daily calorie consumption, and others.

A similar example might be to find out the optimal value of fuel to be allocated to each vehicle if we have a total of 100 gallons. Features might be distance they have to travel, mpg, driver competency, engine horsepower, etc., so that all of them might travel the maximum distance possible.

So, can we achieve a task like this with machine learning/deep learning approaches? If not what are the hurdles achieving this?

Sounds more like a optimization problem than a deep learning / machine learning problem to me.

For machine learning you would have the features of every child / vehicle and the optimal amount of pizza / fuel already given, but you don't know how exactly the optimal amount is computed. So the target is to find a function which maps features to target.

However in your case you don't know the optimal value, you just have a number of constraints. So my suggestion would be to use linear programming.

Here is an simple example: drive the maximum distance with a given amount of fuel

$$\text{max }\ m_1 \cdot x_1 + ... + m_n \cdot x_n$$
$$\text{s.t. }\ x_1 + ... + x_n \leq F$$
$$m_i \cdot x_i \geq T_i\  \forall\  1 \leq i \leq n$$

$x_i$ is the amount of fuel (in gallons) given to car $i$, $m_i$'s are miles-per-gallon for car $i$. $F$ is the total amount of fuel available, this is our first constraint, we cannot distribute more fuel than we have. The second constraint say's that we like to drive at least $T_i$ miles with car $i$. This ensures we do not just give all the fuel to the most efficient car.

You can come up with more constraints for drivers competency, engine horse power etc. In order so solve your problem with linear programming, you just have to make sure it is still linear and convex. Problems of this kind can be solved using the Simplex algorithm (scipy.optimize.linprog).
If your objective or your constraints are more complex you can use numerical methods for non-linear constrained optimization problems (see scipy.optimize for algorithms).


Can Machine Learning be applied to decipher the script of lost ancient languages? Can Machine Learning be applied to decipher the script of lost ancient languages (namely, languages that were being used many years ago, but currently are not used in human societies and have been forgotten, e.g. Avestan language)?

If yes, is there already any successful experiment to decipher the script of unknown ancient languages using Machine Learning?

I would guess no, because if the language is unknown (no data available on it), then we would not have training data with which the machine learning algorithm could learn from.

If it is related to some known language, then some statistical analysis can lead to a guess at decipherment (assuming certain similarities among the two languages).

If interested on general language decipherment, see the following where they decipher scripts using available information on the language of interest: http://www.aclweb.org/anthology/W99-0906. They utilize the Expectation Maximization algorithm.

I'm sure more google searching can lead to other examples that use machine learning algorithms, but they would most likely have some known information or a body of assumptions to make our problem scope easier.


Which Reinforcement Learning algorithms are efficient for episodic problems? I have some episodic datasets extracted from a turn-based RTS game in which the current actions leading to the next state doesn’t determine the final solution/outcome of the episode.

The learning is expected to terminate at a final state/termination condition (when it wins or losses) for each episode and then move on to the next number of episodes in the dataset.

I have being looking into Q learning, Monte Carlo and SARSA but I am confused about which one is best applicable.

If any of the mentioned algorithm is implemented, can a reward of zero be given in preliminary states before termination state of each episodes at which it will be rewarded with a positive/negative (win/loss) value?

When applying techniques like SARSA(which are on-policy), one needs to have control over a simulator. If one is able to access only the episodic dataset, then the only choice is to opt for Q-learning or Off-policy Monte-Carlo(or off-policy methods in general).

  Can a reward of zero
  be given in preliminary states before termination state of each
  episodes at which it will be rewarded with a positive/negative
  (win/loss) value?

With regards to the above question, the answer is yes. The task would be a sparse reward task with a reward occurring only at the last transition. The issue that one faces in a sparse reward task is that of slow convergence(or even lack of convergence).

Some guidelines for tackling sparse reward tasks are as follows :

Monte-Carlo, and n-step Q-learning are preferred over Q-learning/SARSA.

Consider the 10-step chain MDP, where the only reward is +1 when the transition from s10 to END occurs.

Let us consider the first episode in training to be start->s1->s2->s3->....->s10->end. The Q-learning update would result in no sane updates to states s1, s2, s3, s9 because the Q-value of the next state is random-value. The only state with a sane update is s10

However, if we use n-step Q-learning or a Monte-Carlo based update. The Q-values of all the states are updated in a logical manner since the reward from the end of the episode propagates to all states in the episode.

n-step Q-learning would be ideal since by adjusting the value of n, one can trade-off the benefits of Monte-Carlo methods(described above) and Q-learning(low variance).
The use of pseudo/auxiliary rewards.

This is not something necessarily recommended since the addition of new reward-structures can cause unintended behaviour. On the flip-side, it could lead to faster convergence.

A simple example is as follows: Consider a game of chess, where the only reward is at the end of the game. Since the game of chess has very long episodes, one can introduce the following reward-structure instead :

+100 for winning the game
+1 for capturing any piece on the board

Hence, the pseudo reward may provide some direction for learning. Note the different scales in the two rewards(100:1). This is necessary because the primary goal of the task should not shift to capturing pieces, but to win the match.


What are the state space and the state transition function in AI? I'm studying for my AI final exam, and I'm stuck in the state space representation. I understand initial and goal states, but what I don't understand is the state space and state transition function. Can someone explain what are they with examples?
For example, one of the questions was this on my previous exam:

Given $k$ knights on an infinite (in all directions) chessboard and k selected squares of the board. Our task to move the knights to these selected squares obeying the following simple rules:

All knights move parallel, following their movement rule (L-shape jump)
No knights can move to a square on which a knight stood anytime before

Give the state space of the problem, the starting and goal states, and the state transition function!

Initial state
How things are at first.
In your particular example, it would be where your k knights are placed on the board initially. Your problem doesn't precisely state this, so you could either place them at the bottom or at random.
Goal state
The board with the k knights placed on the target squares.
State transition function
A function that takes actions (bound presumably by rules) and returns a new state.
In the k knight problem, the legal actions are moving parallel and in L shape movements, after which the knight will be in a new position and the board in a new state.
State space
The set of all states reachable from the initial state by any sequence of actions.
So, in the case of the k knight problem, your state space would start at the top with your initial state followed down by each individual movement of the k knights and the resulting new state. A graph where lines are actions and nodes are new states or a table are common representations of state space.

Reference
Artificial Intelligence: A Modern Approach, by S. Russell and P. Norvig.