What does "hard for AI" look like? In theoretical computer science, there is a massive categorization of the difficulty of various computational problems in terms of their asymptotic worst-time computational complexity. There doesn't seem to be any analogous analysis of what problems are "hard for AI" or even "impossible for AI." This is in some sense quite reasonable, because most research is focused on what can be solved. I'm interested in the opposite. What I do need to prove about a problem to prove that it is "not reasonably solvable" by AI?

Many papers say something along the lines of

  AI allows us to find real-world solutions to real-world instances of NP-complete problems.

Is there a theoretical, principled reason for saying this instead of "... PSPACE-complete problems"? Is there some sense in which AI doesn't work on PSPACE-complete, or EXPTIME-complete, or Turing complete problems?

My idea answer would be a reference to a paper that shows AI cannot be used to solve a particular kind of problem based on theoretical or statistical reasoning. Any answer exhibiting and justifying a benchmark for "too hard for AI" would be fine though (bonus points if the benchmark has a connection to complexity and computability theory).

If this question doesn't have an answer in general, answers about specific techniques would also be interesting to me.

Nice Question!

This is a perennial topic of discussion among AI researchers. The short answer is "we don't really know which topics are hard in general, but we do know which we haven't got good techniques for yet."

Let's start by explaining why AI is not concerned with notions of computational complexity like NP-Completeness. AI researchers figured out in the 90's that most problems that are computationally hard in theory aren't actually hard in practice at all! For example, Boolean Satisfiability, the canonical NP-Hard problem, is known to have hard instances, but in practice, these almost never show up. Even when they do, we can usually get good approximate solutions with minimal computation time. Since many AI problems are reducible to SAT, whole areas of the field just use these approximation techniques and solvers. There's a good, if a bit old, survey here. Since 2008, things have only gotten better. Basically, NP-Hard stuff just isn't that hard. Worst-case complexity is therefore probably the wrong tool to guess at which problems are hard for AI.

At the other end of the scale, we have subjective complexity based on things like how "large" the problem is. This has proven to be pretty unreliable. One example is Go, which I was told would "never be solved by AI" as late as 2010. Clearly, we were completely wrong. We just didn't know which techniques to use yet. Another example is language. Rule-based AI'ers tried at it for decades with minimal success. Probabilistic methods have achieved essentially human-level performance in less time. If you asked a researcher in the 1970s if language was hard for AI, they'd have said yes, but they'd have been wrong. This has been closely related to the advances in computing hardware: techniques that seemed wasteful and slow 40 years ago are now entirely practical. Sometimes they turn out to solve problems really well.

Part of this ties into the issue that AI'ers don't really know or agree on what intelligence is, or what it means to solve a problem. Some AI'ers maintain that language really is hard, and that the systems we use now aren't really solving language, they're just making blind guesses that happen to be right a lot. Under that view, language is still hard. Fodor was a strong proponent of this view in the past, and his writings are a good place to read about it, but I've still heard people espouse views like this at AI conferences as recently as 2015.

Something this usually considered hard right now is making a good general intelligence, that integrates knowledge across many domains and could plausibly pass something like the Turing test. Yet, there has been some progress here (look at virtual assistants), and some AI'ers reckon this might not be as hard as we thought either.

So, basically, we don't know what's hard because we don't know when someone will come up with a new exciting technique that solves problems previously thought to be hard, we know that worst-case complexity isn't a good measurement system for "intelligence" requirements, and we don't know what intelligence really is.


In number classification using neural network, is training with edge image better than gray image? i'm trying to identify numbers and letters in license plate. License plate images are taken at different lighting condtion and converted to gray image. My concern with type of data for training is:

Gray Image:

Since they are taken at different lighthing condition, gray image have different pixel intensity for same number. Which means, i have to get many training data for different lighting condition to train.

Edge Image:

They lack enough pixel information since only edge is white while others(background) are black. So i think they will be very weak for translational difference like shearing or shifting.

I want to get some information about which type of image is better for training number in different lighting condition. I wish to use edge image if they don't  differ much since i can prepare edge image right now.

Theoretically you will have no gain in the error ratio if the system preprocess the images with a linear high-pass filter before to send the image to the NN.

Let see a simple 1-dimension case that supports this statement:

Assume inputs are "a", "b" and "c". A node at first hidden layer will receive an input to the activation function equal to s=w1*a+w2*b*w3*c+... being w1, w2, w3, ... the weights for this node.

Now, assume a simple differential case, where inputs will be ... , b'=b-a, c'=c-b, ... being the input to the hidden node s=w1'a'+w2'b'+w3'c'+...=...+w2'(b-a)+w3'(c-b)+...=...+(w2'-w3')b+...

Note both inputs to hidden node are the same if w1=w1'-w2', w2=w2'-w3', ... . So, the NN can itself perform the equivalent of the linear high-pass filtering adjusting the weights of the first hidden layer.

However, changes in learning speed (convergence time) can be expected.

(ps: please, activate tex/latex in this site, urgently ! )


Which libraries can be used for image caption generation? Which libraries can be used for image caption generation?

Image Caption Generation is an interesting problem to work on. I think your question was to know if there are any open-source libraries with built-in functions for Image Captioning. You can build Image Caption Generation models using Frameworks like Tensorflow, PyTorch, and Trax.
I'd also recommend you to read the following papers:

Show and Tell: A Neural Image Caption Generator. Link
Transfer learning from language models to image caption generators: Better models may not transfer better. Link
Image Captioning with Unseen Objects. Link

Also, here are a couple of blog posts you can read:

How to Develop a Deep Learning Photo Caption Generator from Scratch
Learn to Build Image Caption Generator with CNN & LSTM
Image Captioning with Keras


How are continuous actions sampled (or generated) from the policy network in PPO? I am trying to understand and reproduce the Proximal Policy Optimization (PPO) algorithm in detail.  One thing that I find missing in the paper introducing the algorithm is how exactly actions $a_t$ are generated given the policy network $\pi_\theta(a_t|s_t)$.
From the source code, I saw that discrete actions get sampled from some probability distribution (which I assume to be discrete in this case) parameterized by the output probabilities generated by $\pi_\theta$ given the state $s_t$.
However, what I don't understand is how continuous actions are sampled/generated from the policy network. Are they also sampled from a (probably continuous) distribution? In that case, which type of distribution is used and which parameters are predicted by the policy network to parameterize said distribution?
Also, is there any official literature that I could cite which introduces the method by which PPO generates its action outputs?

As long as your policy (propensity) is differentiable, everything's is good. Discrete, continuous, other, doesn't matter! :)
A common example for continuous spaces is the reparameterization trick, where your policy outputs $\mu, \sigma = \pi(s)$ and the action is $a \sim \mathcal{N}(\mu, \sigma)$.


How to compute dominant colors in an image? I was trying Google Cloud's Vision API, and how the dominant colors part shows. I uploaded a sample image, and here is the results for the dominant colors. I realized it doesn't simply count pixel colors and cluster them. The background has many gray pixels which are not included.
How does it perform dominant colors? How can I do something similar?

You can find an explanation here (github of the googleapi):

My current understanding of a color's score is a combination of two things:

What is the focus of the image?
What is the color of that focus?

For example, given the following image:

The focus is clearly the cat, and therefore the color annotation for this image with the highest score (0.15) will be RGB = (232, 183, 135) which is the beige color:

The green of the grass (despite having more pixels in the image dedicated to it) has a much lower score by virtue of the algorithm's detection that it's the background and not the focus of the image.

In other words, higher "scores" means higher confidence that the color in question is prominent in the central focus of the image.

It is analogous to your case. Therefore, using a background removal this can help to find the focus of the image, and then make the histogram of the remaining objects' color. An example of the background removal using deep learning can be found in this post.


Are there RL algorithms that also try to predict the next state? So far I've developed simple RL algorithms, like Deep Q-Learning and Double Deep Q-Learning. Also, I read a bit about A3C and policy gradient but superficially.
If I remember correctly, all these algorithms focus on the value of the action and try to get the maximum one. Is there an RL algorithm that also tries to predict what the next state will be, given a possible action that the agent would take?
Then, in parallel to the constant training for getting the best reward, there will also be constant training to predict the next state as accurately as possible? And then have that prediction of the next state always be passed as an input into the NN that decides on the action to take. Seems like a useful piece of information.

Yes, there are algorithms that try to predict the next state. Usually this will be a model based algorithm -- this is where the agent tries to make use of a model of the environment to help it learn. I'm not sure on the best resource to learn about this but my go-to recommendation is always the Sutton and Barto book.
This paper introduces PlanGAN; the idea of this model is to use a GAN to generate a trajectory. This will include not only predicting the next state but all future states in a trajectory.
This paper introduces a novelty function to incentivise the agent to visit unexplored states. The idea is that for unexplored states, a model that predicts the next state from the state-action tuple will have high error (measured by Euclidean distance from true next state) and they add this error to the original reward to make a modified reward.
This paper introduces Dreamer. This is where all learning is done in a latent space and so the transition dynamics of this latent space must be learned, another example of needing to learn the next state.
These are just some examples of papers that try to predict the next state, there are many more out there that I would recommend you look for.


Method to check goodness of combinatorial optimization algorithm implementation How do I check which algorithm solves my problem best?

Given a optimaization problem, I apply different well known optimization algorithms (genetic algorithm, simulated annealing, ant colony etc.) to solve my problem. However, how do I know if my implementation ( e.g. cost function) is working for every case? How can I compare the algorithms or their goodness in the context of my problem?

This is a very large question that could be answered in a variety of ways depending on the context.

For some optimization problems operating under specific conditions you can make theoretical guarantees that your optimization will solve your problem.  A specific example of this is running the gradient descent algorithm on a convex function.  If the function being optimized is convex then gradient descent is guaranteed to converge to the correct solution.  Given the nice properties of convex functions, there are many types of optimization where you can make these theoretical guarantees.

When evolutionary algorithms (and many non-derivative based optimizations) are run, it's much harder to make these types of guarantees.  Often in the literature I've seen people try their functions on several baseline optimization functions and report back the minimum or maximum found.  Many of these are included in Facebook's nevergrad optimization library to be used for evaluation.  An example of one of these functions is included below,

Even if you can prove that your algorithm minimizes several objective functions you could be testing on, there could be other properties that should be considered.  Some of these include the following: the speed at which the algorithm converges; the number of evaluations of the objective function (if not closed form), and even the amount of space in memory which is required for your optimization.  All of these (and many more) factors could come into play when evaluating your algorithm.

Scientists may use functions like this one to evaluate their optimization and compare it to other algorithms that are similar.  To answer your final question though, "How can I see if my optimization works for every problem", I would say that's a bit of a loaded question.  Most of the time these optimizations need some sort of constraint to make a generalized guarantee.  I would look at the constraints of your problem and go from there.

If you're interested, here's a good paper that goes much more in depth than I did here.


Is it illegal to use pictures of public figures to train a neural network? I want to train a neural network with pictures of public figures (politicians, singers, etc), but I do not know if it's legal, I do not plan to show them in my project I only want to use them to train the neural network, can this cause legal problems?

If you use any pictures you find online, you can use them as you wish: as long as you don't (re)publish them under your name. Also, if you really want to play safe, never upload them at all. Download them, use them, disregard them.

People can't proof you used certain pictures to train your network by looking at your network data.

And the 'big' companies out there, like Google, train their networks by using public photos.

And follow this chart:

As you are using it for a personal/educational project, it shouldn't be a problem.


Is there multi-agent reinforcement learning model in which (some of the) reward is given by other agent and not by the external environment? The traditional setting of multiagent reinforcement learning (MARL) is the mode in which there is set of agents and external environment. And the reward is given to each agent - individually or collectively - by the external environment.
My question is - is there MARL model in which the reward is given by one agent to the other agent, meaning that one agent is incurring costs and other agent - revenue (or maybe even a profit?
Effectively that means distributed supervision: only some agents face the environment with real reward/supervision and then this supervision is more or less effectively propgated to other agents that learn/do their own specialized tasks that are part of collective task ececuted/solved distributively in MARL.

This is mostly an implementation architecture problem, and the thing is that basically you can implement anything in the traditional setting. To do so instead of having Env<->Agent1<->Agent2, you should have Agent1<->SuperEnv<->Agent2 where SuperEnv contains Env, and simply uses the reward given to SuperEnv by Agent1 and passes it to Agent2.
I know this might seem a little counter-intuitive when comparing the implementation to the real-world problem setting, but the consistency of the RL structure (i.e. Environment that interacts with all the agent) is very important for your solutions to be easily understandable by others.


Is Monte Carlo Tree Search appropriate for problems with large state and action spaces? I'm doing a research on a finite-horizon Markov decision process with $t=1, \dots, 40$ periods. In every time step $t$, the (only) agent has to chose an action $a(t) \in A(t)$, while the agent is in state $s(t) \in S(t)$. The chosen action $a(t)$ in state $s(t)$ affects the transition to the following state $s(t+1)$.

In my case, the following holds true: $A(t)=A$ and $S(t)=S$, while the size of $A$ is $6 000 000$ (6 million) and the size of $S$ is $10^8$. Furthermore, the transition function is stochastic.

Would Monte Carlo Tree Search (MCTS) an appropriate method for my problem (in particular due to the large size of $A$ and $S$ and the stochastic transition function?)

I have already read a lot of papers about MCTS (e.g. progressive widening and double progressive widening, which sound quite promising), but maybe someone can tell me about his experiences applying MCTS to similar problems or about appropriate methods for this problem (with large state/action space and a stochastic transition function).

MCTS is often said to be a good choice for problems with large branching factors... but the context where that sentiment comes from is that it originally became popular for playing the game of Go, as an alternative to older game-playing approaches such as alpha-beta pruning. The branching factor of Go is more like 250-300 though, which is often viewed as a large branching factor for board games. It's not such an impressive branching factor anymore when compared to your branching factor of $6,000,000$...

I don't see MCTS working well out of the box when you have 6 million choices at every step. Maybe it could do well if you have an extremely efficient implementation of your MDP (e.g. if you can simulate millions of roll-outs per second), and if you have a large amount of "thinking time" (probably in the order of hours or days) available.

To have any chance of doing better with such a massive branching factor, you really need generalization across actions. Are your 6 million actions really all entirely different actions? Or are many of them somehow related to each other? If you gather some experience (a simulation in MCTS, or just a trajectory with Reinforcement Learning approaches), can you generalize the outcome to other actions for which you did not yet collect experience?

If there is some way of treating different actions as being "similar" (in a given state), you can use a single observation to update statistics for multiple different actions at once. The most obvious way would be if you can define meaningful features for actions (or state-action pairs). Standard Reinforcement Learning approaches (with function approximation, maybe linear or maybe Deep Neural Networks) can then relatively "easily" generalize in a meaningful way across lots of actions. They can also be combined with MCTS in various ways (see for example AlphaGo Zero / Alpha Zero).

Even with all that, a branching factor of 6 million still remains massive... but generalization across actions is probably your best bet (which may be done inside MCTS, but really does need a significant number of bells and whistles on top of the standard approach).


Which photo is more artistic? I would like to develop a machine learning algorithm, given two photos, that can decide which image is more "artistic".

I am thinking about somehow combining two images, giving it to a CNN, and get an output 0 (the first image is better) or 1 (the second image is better). Do you think this is a valid approach? Or could you suggest an alternative way for this? Also, I don't know how to combine two images.

Thanks!

Edit: Let me correct "artistic" as "artistic according to me", but it doesn't matter, I am more interested in the architecture. You can even replace "artistic" with something objective. Let's say I would like to determine which photo belongs to a more hotter day.

You need to define a scoring function, which returns a value of whatever criterion you are interested in, be it 'artisticity' or 'heat'. This could be something you use a machine learning algorithm for, provided you have a set of training data with labelled images.

You then need to extract features from the images. In the case of 'heat' this could be a colour spectrum (ie distribution of colours across the image), or whatever. If it's a reasonably small image, pixel values might be feasible. These features you can feed into your algorithm, and try to learn an association between the feature values and the (assigned by you) label of the image. You will end up with a classifier that takes image features as input, and returns the labels as output. The quality of the classifier depends on your images, the features you selected, and the task.  If there is no structure in the data, then a classifier will not work properly.

If you have a continuous value (eg temperature in degrees C) you would run your two sample images through the classifier, and then compare the output values.


Is there any grid world dataset or generator for reinforcement learning? I would like to start programming a multi task reinforcement learning model. For this, I need not just one maze or grid world (or just model-based), but many with different reward functions. So, I am wondering if exists a dataset or a generator for such thing, or do I need to code everything by my self?

Depending on your needs and the size of the project, you might be better off making a custom set of environments. If you'd rather not do that, though, you should take a look at OpenAI's CoinRun environment. A high-level description can be found in their blog post.

The "RandomMazes" version of this environment might be useful to you. And if you want to make the mazes smaller, you can redefine MAX_MAZE_DIFFICULTY in coinrun.cpp.

Note that, although the levels are procedurally generated, reward is only ever given when the agent picks up the single coin. So, this might not be as much variety in reward function as you wanted.


How to estimate the AI player's strength in multiplayer game? I have implemented multiple MCTS based AI players for the Love Letter game (rules). It is a 2-4 players zero sum card game where players make alternating moves. I am struggling with how to properly conduct experiments for estimating AI player strength against human players:

In 2 player game where one of the players is AI bot
In 4 player game where one (or multiple) of players is AI bot

The following are extremely simple ways of tackling this problem.
A very simple way
It can simply be
strength of AI=(# of games won)/(total # of games).

In case data for each move is available
Something like
score per game=# of correct decisions/total number of decisions.
Then
strength of AI=sum(score per game)/total # of games.

If each move/decision has a score associated with it
then you doscore per move=scored points by taking a decision/maximum possible score.
then
score per game=sum(score per move)/total # of moves
and finally,
strength of AI=sum(score per game)/total # of games.

How to choose optimal number of games to play?
It depends on your requirements. If you want to report your AI's strength in percentage of the games it played correct to 1 decimal place (for example, this AI won 95.1%) then 10000 is an optimal number of games your AI needs to play. Suppose your AI won 9508 games out of 10000 then you will have 95.08% strength of AI. To be able to correctly round it to 1 decimal place you need to have an additional decimal place so that you can quote the strength of you AI with reasonable confidence, in this case 95.1%.


CNN High Variance across multiple trained models, what does it mean? Background:

I have a 2D CNN model that I am applying to a regression task with some uniquely extracted spectrograms. The specifics of the data set are mostly irrelevant and very domain specific so I won't go into detail, but it is essentially just image classification with a MSE loss function for each label and a unique image of 100x4000. When I re-train the model from scratch multiple times then provide it my testing data set, it has predictions that vary significantly across each iteration and thus a high variance. Supposedly the only difference between a trained model versus another would be the random initialization of weights and the random train/validation split. I feel that the train/validation split has been ruled out by when I've done k-fold cross validation and my model has done very good for all segments of my train/validation splits and acquired good results for the validation in each split. But these same models persist to have high variance in the test data set.

Question:

If I am seeing a high variance for the predictions from my trained model across multiple different runs of re-training, what do I attack first to reduce my variance on my predictions for my test data set?

I've found many articles talking about bias and variance in the data set but not as much criticism directed towards model design. What things can I explore in my dataset or model design, and/or tools I can use to strengthen my model? Does my model need to be bigger/smaller?

Ideas/Solutions:
A few Ideas I'd like to acquire some criticism for.

Regularization applied to model such as L1/L2 Regularization, dropout, or early stopping.
Data augmentation applied to dataset (inconveniently not an option right now, but in a more general scenario it could be).
Bigger or smaller model?
Is the random initialization of weight actually very important? Maybe train multiple models and take the average of their collective answers to get the best prediction on real world data (test set).

Personal Note:
I have had experience with all these items before on other projects and with personal projects and have some moderate confidence justifying regularization and data augmentation. However, I lack some perspective as to any other tools that might be useful to explore the cause of model variance. I wanted to ask this question here to start a discussion in a general sense of this problem.

Cheers

EDIT: CLARIFICATION. When I say 'variance' I mean specifically variance across models, not variance of predictions from 1 trained model across the test set. Example: Instead lets say I am trying to predict a value somewhere between 1 and 4 (expected_val=3). I train 10 models to do this and 4 of the models accurately predict 3 with a VERY low standard deviation across all the test set samples. Thus a low variance and high accuracy/precision for these 4 models. But the other 6 models predict wildly and some predict 1 very confidently every time and the others could be 4. And I've even had models that predicted negative values even though I have NO training or testing samples that have negative labels.

Firstly if you're doing spectrogram classification, you'd probably want to use a loss function like cross entropy. That would give you less "high-variance" like results when you're calculating your evaluation metrics.

About your ideas:

Dropout and early stopping would be enough
Data augmentation with speech is quite helpful, and there are a few libraries to help you with volume/speed/noise augmentation. Volume/speed augmentation is actually really important and you'd want to do it anyway for decent results in production. Speech processing is sometimes a bit tricky, in the sense that what we hear may not be what ends up in the spectrogram and parameters like noise, recording setup, encoding, accent end up causing a domain-mismatch (covariate shift)
In general, a smaller model (less parameters) helps with high variance. Start with small and simple models first, make sure eval metrics look ok, and then try larger models.
Random initialization doesn't really affect the results in a systematic way. You can indeed ensemble predictions of models trained with different initialization; that does help with variance but don't expect a lot of difference. The gain is not worth the computation cost for models applied in practice (ie not kaggle)

Other ideas:

Check that you shuffle data properly in train/test, and between folds
Do some error analysis on the mis-predicted test samples, do they have something in common. Check the label distribution in your dev/test set.
If the test set was captured in a process different from your dev set (total blind), don't expect a robust performance. In general, speech recognition is really data hungry with a decent "generic* model needing hundreds of hours of recording from different domains (tv, news, movies, telephone, lecture, echo, etc.).


Can someone explain R1 regularization function in simple terms? I'm trying to understand the R1 regularization function, both the abstract concept and every symbol in the formula.
According to the article, the definition of R1 is:

It penalizes the discriminator from deviating from the Nash Equilibrium via penalizing the gradient on real data alone: when the generator distribution produces the true data distribution and the discriminator is equal to 0 on the data manifold, the gradient penalty ensures that the discriminator cannot create a non-zero gradient orthogonal to the data manifold without suffering a loss in the GAN game.
$R_1(\psi  ) = \frac{\gamma}{2}E_{pD(x)}\left [ \left \| \bigtriangledown D_{\psi}(x) \right \|^2 \right ]$

I have basic understanding of how GAN's and back-propagation works. I understand the idea of punishing the discriminator when he deviates from the Nash equilibrium. The rest of it gets murky, even if it might be basic math. For example, I'm not sure why it matters if the gradient is orthogonal to the data.
On the equation part, it's even more unclear. The discriminator input is always an image, so I assume $x$ is an image. Then what is $\psi$ and $\gamma$?
(I understand this is somewhat of a basic question, but seems there are no blogs about it for us simple non-researchers, math challenged people who fail to understand the original article )

Here is how I understand this regularization.
$R_1$ is simply the norm of the gradients, which indicates how fast the weights will be updated. Gradient regularization penalizes large changes in the output of some neural network layer.
$$
R_{1}\left(\psi\right) = \frac{\gamma}{2}E_{p_{D}\left(x\right)}\left[||\nabla{D_{\psi}\left(x\right)}||^{2}\right]\text{,}
$$
where $\psi$ is discriminator weights, $E_{p_{D}\left(x\right)}$ means that we sample data only form the real distribution (i.e. only real images) and $\gamma$ is a hyperparameter.
Since we don't know if $G$ can already generate data from real distribution, we apply this regularization to $D$ only on real data, because we don't want the discriminator to create a non-zero gradient without suffering a loss if we are already in a Nash Equilibrium. I guess this also prevents $G$ from updating if it generates data from the real distribution.
The authors also investigate which value is best for $\gamma$ by analyzing the eigenvalues of the Jacobian of the the associated gradient vector field, but in my opinion, this value is highly dependent on dataset and architecture.
"Gradient orthogonal to the data manifold" simply means zero gradients. From a GAN perspective, the data manifold is a lower-dimensional latent features manifold embedded in a higher-dimensional space and our goal is to approximate it. Since the gradient vector shows the direction in which we need to update our function, if it is orthogonal to this manifold, we do not need to update the function.


How to avoid rapid actuator movements in favor of smooth movements in a continuous space and action space problem? I'm working on a continuous state / continuous action controller. It shall control a certain roll angle of an aircraft by issuing the correct aileron commands (in $[-1, 1]$).
To this end, I use a neural network and the DDPG algorithm, which shows promising results after about 20 minutes of training.
I stripped down the presented state to the model to only the roll angle and the angular velocity, so that the neural network is not overwhelmed by state inputs.
So it's a 2 input / 1 output model to perform the control task.
In test runs, it looks mostly good, but sometimes, the controller starts thrashing, i.e. it outputs flittering commands, like in a very fast bangbang-controlm which causes a rapid movement of the elevator.

Even though this behavior kind of maintains the desired target value, this behavior is absolutely undesirable. Instead, it should keep the output smooth. So far, I was not able to detect any special disturbance that starts this behavior. Yet it comes out of the blue.
Does anybody have an idea or a hint (maybe a paper reference) on how to incorporate some element (maybe reward shaping during the training) to avoid such behavior? How to avoid rapid actuator movements in favor of smooth movements?
I tried to include the last action in the presented state and add a punishment component in my reward, but this did not really help. So obviously, I do something wrong.

After some research on the subject, I found a possible solution to my problem of high frequency oscillations in continuous control using DDPG:

I added a reward component based on the actuator movement, i. e. the delta of actions from one step to the next.

Excessive action changes are punished now and this could mitigate the tendency to oscillate. The solution is nnot really perfect, but it works for the moment.

This finding is detailed out in the "Reward Engineering" section of my master's thesis. Please have a look into https://github.com/opt12/Markov-Pilot/tree/master/thesis

I'll be glad to get feedback on it. And I'll be glad to hear better solutions than adding a delta-punishment.

Regards, Felix


Is algorithmic bias due to the training dataset used? I recently read about algorithmic bias in facial recognition.

Is algorithmic bias due to the training dataset used, or is it due to something else?

As the name implies, algorithmic bias is related with the used algorithm. Due to the way it was programmed or devised, the algorithm will be biased in some of its samples.

From Communications of the ACM:

  [Algorithms] often inadvertently pick up the human biases that are incorporated when the algorithm is programmed, or when humans interact with that algorithm.

A machine learning model can be biased if the wrong data-set is used, of course. That is usually only referred to as bias, and often associated with the bias-variance tradeoff.


Intutitive explanation of why Experience Replay is used in a Deep Q Network? I understand that Experience Replay is used for data efficiency reasons and to remove correlations in sequences of data. How exactly do these sequences of correlated data affect the performance of the algorithm?

It is the neural network approximation that suffers, when it attempts to learn from correlated data. Intuitively, this is because the learning algorithm takes gradient steps assuming that the examples it are shown are representative of the dataset as a whole. A neural network update step uses a mini-batch of examples to calculate the gradient of its weights and biases with respect to a cost function. If that mini-batch is not fairly sampled, then the expected value of the loss and of the gradient will not be representative of the population as a whole. They will be biased and can cause an update step to parameters in the wrong direction.

In addition, if you are using a bootstrapping method - any form of TD learning - then the value estimates used to set learning update targets are sensitive to bias in the estimator. This is already something that can cause instability due to positive feedback loops. Adding another source of systemic bias from correlated input data can only make it worse.

You can gain some experience for the effect of this with a simple non-RL experiment.

Goal: To approximate the function $y = x^2$ in the range $-2 < x < 2$. These numbers chosen to make the task simple for a neural network.

Setup: Generate training data in the form $x_i, y_i$ for a few thousand sample points with true values of the function. Optionally add some noise to make the task harder. Keep the data set ordered by $x_i$ values. Create a simple neural network for regression (e.g. 2 hidden layers with 50 neurons and tanh activation), and set it up with a simple optimiser (e.g. SGD)

Run: Train the network twice, using small minibatches (e.g. size 10). Once without shuffling the data on each epoch (or using any shuffling algorithm on the minibatches), and once with standard shuffling and assignment to minibatches. Plot a learning curve of loss vs epoch for each run.

You should find that the ordered, non-shuffled version learns much slower than when using some randomisation to decorrelate the data. Depending on precise hyperparameters, the ordered version may even oscillate with loss quite far away from converging.

It is this effect, or a more subtle version of it, that impacts RL combined with neural networks when learning direct from trajectories. In addition, there is existing starting bias in bootstrap methods, which this effect makes worse.


Are we technically able to make, in hardware, arbitrarily large neural networks with current technology? If neurons and synapses can be implemented using transistors, what prevents us from creating arbitrarily large neural networks using the same methods with which GPUs are made?

In essence, we have seen how extraordinarily well virtual neural networks implemented on sequential processors work (even GPUs are sequential machines, but with huge amounts of cores).

One can imagine that using GPU design principles - which is basically to have thousands of programmable processing units that work in parallel - we could make much simpler "neuron processing units" and put millions or billions of those NPUs in a single big chip. They would have their own memory (for storing weights) and be connected to a few hundred other neurons by sharing a bus. They could have a frequency of for example 20 Hz, which would allow them to share a data bus with many other neurons.

Obviously, there are some electrical engineering challenges here, but it seems to me that all big tech companies should be exploring this route by now.

Many AI researchers say that superintelligence is coming around the year 2045. I believe that their reasoning is based on Moore's law and the number of neurons we are able to implement in software running on the fastest computers we have.

But the fact is, we today are making silicon chips with billions of transistors on them. SPARK M7 has 10 billion transistors.

If implementing a (non-programmable) neuron and a few hundred synapses for it requires for example 100 000 transistors, then we can make a neural network in hardware that emulates 100 000 neurons.

If we design such a chip so that we can simply make it physically bigger if we want more neurons, then it seems to me that arbitrarily large neural networks are simply a budget question.

Are we technically able to make, in hardware, arbitrarily large neural networks with current technology?

Remember: I am NOT asking if such a network will in fact be very intelligent. I am merely asking if we can factually make arbitrarily large, highly interconnected neural networks, if we decide to pay Intel to do this?

The implication is that on the day some scientist is able to create general intelligence in software, we can use our hardware capabilities to grow this general intelligence to human levels and beyond.

The approach you describe is called neuromorphic computing and it's quite a busy field.

IBM's TrueNorth even has spiking neurons.

The main problem with these projects is that nobody quite knows what to do with them yet.

These projects don't try to create chips that are optimised to run a neural network. That would certainly be possible, but the expensive part is the training not the running of neural networks. And for the training you need huge matrix multiplications, something GPUs are very good at already. (Google's TPU would be a chip optimised to run NNs.)

To do research on algorithms that might be implemented in the brain (we hardly know anything about that) you need flexibility, something these chips don't have. Also, the engineering challenge likely lies in providing a lot of synapses, just compare the average number of synapses per neuron of TrueNorth, 256, and the brain, 10,000.

So, you could create a chip designed after some neural architecture and it would be faster, more efficient, etc …, but to do that you'll need to know which architecture works first. We know that deep learning works, so google uses custom made hardware to run their applications and I could certainly imagine custom made deep learning hardware coming to a smartphone near you in the future. To create a neuromorphic chip for strong AI you'd need to develop strong AI first.


Can the law of iterated expectation be used on the inner expectation of the DQN cost function described in the DQN paper Is the expression for the DQN cost function, Equation (2) of the DQN paper
$$\begin{align}L_1 &= E_{\mu,\pi}\left[\left(y_i - q(s,a;\theta)\right)^2\right]\\
&=E_{\mu,\pi}\left[\left(E_{\mathcal{E}}[r + \gamma \max\limits_{a'}q(s',a';\theta^-)] - q(s,a;\theta)\right)^2\right] \end{align}$$
equivalent to this? (Substituting the expression for $y_i$ defined in the paragraph directly after, $\mathcal{E}$ represents the transition distribution governed by the environment, $\pi$ represents the behaviour policy and $\mu$ represents the stationary distribution of states)
$$L_2 = E_{\mu,\pi,\mathcal{E}}\left[\left(r + \gamma \max\limits_{a'}q(s',a';\theta^-) - q(s,a;\theta)\right)^2\right]$$
Can the law of iterated expectation be used to derive the second expression from the first, if not, is there another way to go about showing their equivalence IF they are equivalent.
It seems as though $L_2$ is used for sampling but I'm not sure how it's possible to get here from the original cost function $L_1$. If it is possible to use $L_2$ to sample I assume that means the two expressions must be equivalent. The second expression is used for sampling in the DQN paper here.
I do realise that the gradient for each function is the same and thus so is the $n^{th}$ derivative for some $n\geq1$ and since the curvature and optimas align I guess that also means they are the same function (minus some constant difference)?
$$\nabla_{\theta} L = E_{\mu,\pi,\mathcal{E}}\left[\left(r + \gamma \max\limits_{a'}q(s',a';\theta^-) - q(s,a;\theta)\right)\nabla q(s,a;\theta)\right]$$

Related Question
A related problem that concerns equivalence of sampling from $L_1$ and $L_2$. Is it possible to sample from a nested expectation that is squared as follows?
$$E[E[X|Y]^2] \approx \frac{1}{n}\sum X^2$$
Where $X$ is generated according to the marginalised distribution $P(X)$. I don't think it is true  since $E[X]^2 \neq E[X^2]$ which should mean sampling from $L_1$ and $L_2$ are not equivalent.

Using the related question and simplifying notation
$$\begin{align} E_{\mu,\pi}[E_{\mathcal{E}}[s'|s,a]^2] &= \sum_\limits{s,a}\left(\sum_\limits{s'}s'p(s'|s,a)\right)^2p(s,a) \\
&=\sum_\limits{s,a}\left(\sum_\limits{s_1'}s_1'p(s'_1|s,a)\cdot\sum_\limits{s_2'}s_2'p(s'_2|s,a)\right)p(s,a) \\
&= \sum_\limits{s,a,s_1',s_2'}s_1's_2'p(s_1'|s,a)p(s_2'|s,a)p(s,a) \\
&= E_{\mathcal{E}\sim (s_1',s_2'),\mu,\pi}[s_1'\cdot s_2']
\end{align}$$
This is the closest I could come up with, basically instead of the same sample squared, we pick two samples independently given the pair $(s,a)$.


Does neuroevolution require a labelled dataset? A neuroevolution algorithm, such as DXNN, can be used to refine the topology and weights of an artificial neural network (ANN). The GA will require a fitness function, which means you need labeled data for comparison.

Can neuro-evolution be used with unlabelled data? I have no labeled datasets.

The GA will require a fitness function, which means you need labeled data for comparison.

That conclusion is wrong. Yes, sometimes your fitness function will use labeled data. For example, if you want to train an XOR gate or any other known function.

However, there is arguably no advantage of training a function with neuroevolution versus backpropagation, except for the fact that you might discover some new architectures which solve the solution very well.

You don't always need a labelled dataset for neuroevolution.

Take for example IAMDinosaur, which trains neural networks through a genetic algorithm - however, the optimal solution is not known. There is no labelling of input data, all it does is calculate the fitness from the score.


Is anybody still using Conceptual Dependency Theory? Roger Schank did some interesting work on language processing with Conceptual Dependency (CD) in the 1970s. He then moved somewhat out of the field, being in Education these days. There were some useful applications in natural language generation (BABEL), story generation (TAILSPIN) and other areas, often involving planning and episodes rather than individual sentences.

Has anybody else continued to use CD or variants thereof? I am not aware of any other projects that do, apart from Hovy's PAULINE which uses CD as representation for the story to generate.

Although this model played an important role in contributing  to our present understanding of NLP and NLU, it is no longer useful in production systems and currently no successful commercial product follows this approach.

In CDT the goal was to design an AI system that could draw logical inferences from sentences. In this system the goal was to make the meaning independent of the words used in the input.

CDT modeled sentences by using tokens such as: locations, time, real world actions and real world objects. However as computational power became more common and less expensive, interest diverted to statistical models which were now outperforming the previous rule based systems.

The problem with rule based approaches such as CDT is that they require manual development of linguistic rules which can be costly and which usually don't generalize well to other languages.

On the other hand, statistical approaches use  human language resources (multilingual textual corpora) more efficiently. Rather than using a rule based approach, statistical models make soft probabilistic decisions based on attaching real weights to the features making up the input data. (Wikipedia NLP)

This efficient use of human language resources leads to a model that is more accurate and robust especially when given unfamiliar input or input that contains errors. Statistical models also generalise well to other languages.


Could artificial intelligence cause problems for humanity after figuring out human behavior? This BBC article suggests that intelligent algorithms, like those that select news stories and advertisements for display, could control our experience of the world and manipulate us.

Will Artificial Intelligence someday become a problem to humanity after learning human behaviors and characteristics?

Will Artificial Intelligence some day become a problem to humanity
  after learning human behaviors and characteristics?

It can be answered in both ways, I think.

Yes, they may become a problem.

With the increasing integration of loads of apps and smart devices in our life, almost everything defining an individual human being is digitalised. For instance, our fingerprints, voice, facial image etc. Apart from these data, we use those apps and devices to track our health (heart rate, calorie intake etc), to plan our schedules, and most importantly to communicate. If some sort of AI engine is integrated into a chat application, for instance, it can learn our typing patterns, conversation style, and hundreds of other unforeseen parameters. Imagine what can be learned about a person if such AI is coded inside every device and every app in your day-to-day use.

We use smart devices and apps to harness their functionalities and features which ease our way of life, and we give them, unintentionally, our identity and sometimes, even our personality. For them, these are the parameters that can be input to some machine-learning algorithm and predict what we will do the next day, or what will happen to us the next day.

This sounds like a major problem, especially when these technologies are indispensable.

No, they may not become a problem.

Humans are really complex creatures and possess the most advanced intelligence technology called the brain. I think the brain can be thought of as a technology in this context. There are several tissues inside the brain that can learn to do certain things themselves. It was proven in a research that some tissues have the capability to perform the functions of other tissues using neuro-rewiring techniques. Imagine that the same tissue that has helped you see until now can be made to help you hear instead. Now imagine mimicking such a technology.

While it is not impossible, for an AI to achieve the brilliance of a human brain is a topic of ongoing research. To train a machine for the purpose, we would have to feed it with gazillion behaviors and characteristics, which it may not be able to handle! After learning some behavior and characteristics, the AI would be said to be smart, but it would still predate us.

So, they may not become a problem at all because of our brain.

The algorithms (like recommender systems) used by Amazon and Facebook influence us or even manipulate us. But, that manipulation is either very obvious (like viewing promoted products) or is in company's best interests (like viewing a certain news piece). It may be even possible that several external parameters are used by these systems to improve your experience. For instance, Google ads show us what we were looking for on an online store when we visit any random website. In most cases, what you see is a result of what you were looking for before. If any attempt to influence does happen, we may learn to avoid it through careful observation or even experience.


How do I compute the structural similarity between sentences? I am working on a problem where I need to determine whether two sentences are similar or not.  I implemented a solution using BM25 algorithm and wordnet synsets for determining syntactic & semantic similarity.  The solution is working adequately, and even if the word order in the sentences is jumbled, it is measuring that two sentences are similar. For example

Python is a good language.
Language a good python is.

My problem is to determine that these two sentences are similar.

What could be the possible solution for structural similarity?
How will I maintain the structure of sentences?

Firstly, before we commence I recommend that you refer to similar questions on the network such as https://datascience.stackexchange.com/questions/25053/best-practical-algorithm-for-sentence-similarity and https://stackoverflow.com/questions/62328/is-there-an-algorithm-that-tells-the-semantic-similarity-of-two-phrases

To determine the similarity of sentences we need to consider what kind of data we have. For example if you had a labelled dataset i.e. similar sentences and disimilar sentences then a straight forward approach could have been to use a supervised algorithm to classify the  sentences.

An approach that could determine sentence structural similarity would be to average the word vectors generated by word embedding algorithms i.e word2vec. These algorithms create a vector for each word and the cosine similarity among them represents semantic similarity among words. (Daniel L 2017)

Using word vectors we can use the following metrics to determine the similarity of words.

Cosine distance between word embeddings of the words
Euclidean distance between word embeddings of the words

Cosine similarity is a measure of the similarity between two non-zero vectors of an inner product space that measures the cosine of the angle between them. The cosine angle is the measure of overlap between the sentences in terms of their content.

The Euclidean distance  between two word vectors provides an effective method for measuring the linguistic or semantic similarity of the corresponding words. (Frank D 2015)

Alternatively you could calculate the eigenvector of the sentences to determine sentence similarity.

Eigenvectors are a special set of vectors associated with a linear system of equations (i.e. matrix equation). Here a sentence similarity matrix is generated for each cluster and the eigenvector for the matrix is calculated. You can read more on Eigenvector based approach to sentence ranking on this paper https://pdfs.semanticscholar.org/ca73/bbc99be157074d8aad17ca8535e2cd956815.pdf

For source code Siraj Rawal has a Python notebook to create a set of word vectors. The word vectors can then be used to find the similarity between words. The source code is available here https://github.com/llSourcell/word_vectors_game_of_thrones-LIVE

Another option is a tutorial from Oreily that utilizes the gensin Python library to determine the similarity between documents. This tutorial uses NLTK to tokenize then creates a tf-idf (term frequency-inverse document frequency) model from the corpus.  The tf-idf is then used to determine the similarity of the documents. The tutorial is available here https://www.oreilly.com/learning/how-do-i-compare-document-similarity-using-python


Would you categorize policy iteration as an actor-critic reinforcement learning approach? One way of understanding the difference between value function approaches, policy approaches and actor-critic approaches in reinforcement learning is the following:

A critic explicitly models a value function for a policy.
An actor explicitly models a policy.

Value function approaches, such as Q-learning, only keep track of a value function, and the policy is directly derived from that (e.g. greedily or epsilon-greedily). Therefore, these approaches can be classified as a "critic-only" approach.

Some policy search/gradient approaches, such as REINFORCE, only use a policy representation, therefore, I would argue that this approach can be classified as an "actor-only" approach.

Of course, many policy search/gradient approaches also use value models in addition to a policy model. These algorithms are commonly referred to as "actor-critic" approaches (well-known ones are A2C / A3C).

Keeping this taxonomy intact for model-based dynamic programming algorithms, I would argue that value iteration is an actor-only approach, and policy iteration is an actor-critic approach. However, not many people discuss the term actor-critic when referring to policy iteration. How come?

Also, I am not familiar with any model-based/dynamic programming like actor only approaches? Do these exist? If not, what prevents this from happening?

Keeping this taxonomy intact for model-based Dynamic programming algorithms, I would argue that value iteration is a Actor only approach, and policy iteration is a Actor-Critic approach. However, not many people discuss the term Actor-Critic when referring to Policy Iteration. How come?

Both policy iteration and value iteration are value-based approaches. The policy in policy iteration is either arbitrary or derived from a value table. It is not modelled separately.

To count as an Actor, the policy function needs to modelled directly as a parametric function of the state, not indirectly via a value assessment. You cannot use policy gradient methods to adjust an Actor's policy function unless it is possible to derive the gradient of the policy function with respect to parameters that control the relationship bewteen state and action. An Actor policy might be noted as $\pi(a|s,\theta)$ and the parameters $\theta$ are what make it possible to learn improvements.

Policy iteration often generates an explicit policy, from the current value estimates. This is not a representation that can be directly manipulated, instead it is a consequence of measuring values, and there are no parameters that can be learned. Therefore the policy seen in policy iteration cannot be used as an actor in Actor-Critic or related methods.

Another way to state this is that the policy and value functions in DP are not separate enough to be considered as an actor/critic pair. Instead they are both views of the same measurement, with the value function being closer to raw measurements and policy being a mapping of the value function to policy space.

  Also, I am not familiar with any model-based/dynamic programming like actor only approaches? Do these exist? If not, what prevents this from happening?

The main difference between model-based dynamic programming and model-free methods like Q-learning, or SARSA, is that the dynamic programming methods directly use the full distribution model (which can be expressed as $p(r, s'|s,a)$) to calculate expected bootstrapped returns.

There is nothing in principle stopping you substituting expected returns calculated in this way into REINFORCE or Actor-Critic methods. However, it may be computationally hard to do so - these methods are often chosen when action space is large for instance.

Basic REINFORCE using model-based expectations would be especially hard as you need an expected value calculated over all possible trajectories from each starting state - if you are going to expand the tree of all possible results to that degree, then a simple tree search algorithm would perform better, and the algorithm then resolves to a one-off planning exhaustive tree search.

Actor-Critic using dynamic programming methods for the Critic should be viable, and I expect you could find examples of it being done in some situations. It may work well for some card or board games, if the combined action space and state space is not too large - it would behave a little like using Expected SARSA for the Critic component, except also run expectations over the state transition dynamics (whilst Expected SARSA only runs expectations over policy). You could vary the depth of this too, getting better estimates theoretically at the expense of extra computation (potentially a lot of extra computation if there is a large branching factor)


What is a "learned policy" in Q-learning? I am completing an assignment at the moment. One of the assignment questions asks how you identified the learned policy and how you obtained it. The question is a reinforcement learning question, and the task is to apply the Q-learning algorithm to fill out a Q-table (which I've done) but confused on what it may mean by the learned policy.
So, what is a "learned policy" in Q-learning?

A Q table allows you to look up any state/action pair in it and find the associated action value. It is not itself a policy. However, in order to calculate the action values, you will have assumed something about the policy.
The most common policy scenarios with Q learning are that it will converge on (learn) the values associated with a given target policy, or that it has been used iteratively to learn the values of the greedy policy with respect to its own previous values. The latter choice - using Q learning to find an optimal policy, using generalised policy iteration - is by far the most common use of it.
A policy is not a list of values, it is a map from state to actions. The question wants you to show the policy that you have learned the Q values for.
The policy in your case is therefore likely to be to pick the action that has the highest action value in each state. You may be able to decribe your answer in text ("always turn left unless next to the exit") or as a graphic (draw arrows on a grid world to show the preferred direction). Or you could write out a table of states showing the chosen action in each one.
The maths notation for how you derive the policy from a Q table can be written:
$$\pi(s) = \text{argmax}_a Q(s,a)$$
Or a bit more formally:
$$\pi: \mathcal{S} \rightarrow \mathcal{A} = \text{argmax}_{a \in \mathcal{A}(s)} Q(s,a)\qquad \forall s \in \mathcal{S}$$


How to reduce amount of species in NEAT? I am using the following library:
https://github.com/vishnugh/evo-NEAT

which seems to be a pretty simple NEAT-implementation.
Therefore I am using the following Config:

package com.evo.NEAT.com.evo.NEAT.config;

/**
 * Created by vishnughosh on 01/03/17.
 */
public class NEAT_Config {

    public static final int INPUTS = 11;
    public static final int OUTPUTS = 2;
    public static final int HIDDEN_NODES = 100;
    public static final int POPULATION =300;

    public static final float COMPATIBILITY_THRESHOLD = Float.MAX_VALUE;
    public static final float EXCESS_COEFFICENT = 1;
    public static final float DISJOINT_COEFFICENT = 1;
    public static final float WEIGHT_COEFFICENT = 5;

    public static final float STALE_SPECIES = 2;

    public static final float STEPS = 0.1f;
    public static final float PERTURB_CHANCE = 0.9f;
    public static final float WEIGHT_CHANCE = 0.5f;
    public static final float WEIGHT_MUTATION_CHANCE = 0.5f;
    public static final float NODE_MUTATION_CHANCE = 0.1f;
    public static final float CONNECTION_MUTATION_CHANCE = 0.1f;
    public static final float BIAS_CONNECTION_MUTATION_CHANCE = 0.1f;
    public static final float DISABLE_MUTATION_CHANCE = 0.1f;
    public static final float ENABLE_MUTATION_CHANCE = 0.2f ;
    public static final float CROSSOVER_CHANCE = 0.1f;

    public static final int STALE_POOL = 10;
}

However, there are way too much species (about 60). I do not know how to reduce this number, given the fact that the COMPATIBILITY_THRESHOLD is already maximized.

So what's my fault?

Note: I am not using: http://nn.cs.utexas.edu/keyword?stanley:ec02
since this algorithm seems not to work in a changing environment (where fitness can vary hardly)

Your species count will increase as the chance of mutation increases. This is because in every generation, so many genes will be mutated that they have little resemblance of each other, and the distance function doesn't factor in historical markings / innovation numbers.

Try lowering the mutation rates.

Below is the distance function from here page 110

$$\delta = \frac{c_1E}{N} + \frac{c_2D}{N} + c_3 \cdot \overline{W}.  $$

If your fitness vary a lot, try ranking the fitnesses in each specie and setting the survival chance based on its rank.

If you mean a large action space by changing environment, you can set the number of output nodes to the total number of actions, and rank each action, best to worst, then pick the best available action for the state.


How and when should we update the Q-target in deep Q-learning? I have recently watched David silver's course, and started implementing the deep Q-learning algorithm.

I thought I should make a switch between the Q-target and Q-current directly (meaning, every parameter of Q-current goes to Q-target), but I found a repository on GitHub where that guy updates Q-target as follows:

$$Q_{\text{target}} = \tau * Q_{\text{current}} + (1 - \tau)*Q_{\text{target}}$$.

where $\tau$ is some number probably between 0 and 1.

Is that update correct or I miss something?

I thought after some iterations (e.g. 2000 iteration), we should update Q-target as: $Q_{\text{target}}=Q_{\text{current}}$.

The update form $\theta^{\prime} \leftarrow \tau \theta+(1-\tau) \theta^{\prime}$ (where $\theta'$ and $\theta$ represent the weights of the target network and the current network, respectively) does exist and is correct.

It is called soft update and it has been used in the Deep Deterministic Policy Gradient (DDPG) paper, which uses the concept of a target network like DQN. The authors of the paper state that:

  The weights of these target networks are then updated by having them slowly track the learned networks: $\theta ' \leftarrow \tau \theta + (1 − \tau )\theta'$ with $\tau << 1$. This means that the target values are constrained to change slowly, greatly
  improving the stability of learning.

This update will be made in each time step as follows. For example, for $\tau= 0.001$, the new weights for the target network will take $0.1\%$ of the main network’s weights and $99.9 \%$ of the old target network weights. This does not go against the purpose of fixed target networks (which have been introduced to address the problem of “moving targets”). In fact, by keeping $99.9\%$ of the old target network weights, they can still be considered as fixed.

Seeing that this resulted in improvements in DDPG, some DQN implementations/tutorials started to use soft updates for the target network.

This is opposed to the hard update scheme used in the original DQN paper, i.e. the weights are copied every $C$ steps. This means that the target network is kept fixed for $C$ steps (10000 in the paper) and then gets a significant update.


Training a classifier on different datasets with different image conditions for different labels causes the model to infer using the background I have an interesting problem related to training the model on two different datasets for the target feature on images taken on different conditions, which might affect the model's ability to generalize.
To explain I will give examples of images from the two different datasets.
Dataset 1 sample image:

Dataset 2 sample image:

As you see the images are captured in two completely different conditions. I am afraid that the model will infer from the background information that it shouldn't use to predict the plant diseases, what makes the problem worse is that some plant diseases only exist in one dataset and not the other, if all the diseases are contained in both datasets then I wouldn't think there would be a problem.
I am assuming I need a way to unify the background by somehow detecting the leaf pixels in the images and unifying the background in a way that makes the model focuses on the important features.
I've tried some segmentation methods but the methods I tried don't always give desirable results for all the images.
What is the recommended approach here? All help is appreciated
Further explanation of the problem.
Ok so I will explain one more thing, my model on the two datasets works fine when training and validating, It got a 94% accuracy.
The problem is, even though the model performs well on the datasets I have, I am afraid that when I use the model on real-life conditions (say someone capturing an image with their phone) the model will be heavily biased towards predicting labels in the second dataset (the one with actual background) since the background is similar and it somehow associated the background with the inference process.
I have tried downloading a leaf image of a label that is contained on the first dataset ( the one with the white background), where the image had a real-life background, the model as expected failed to predict the correct label and predicted a label contained in the second dataset, I am assuming it was due to the background. I have tried this experiment multiple times, and the model consistently failed in similar scenarios
I used some Interpretability techniques as well to visualize the important pixels and it seems like the model is using the background for inference, but I am not an expert in interpreting these graphs so I am not 100% sure.

I am afraid that the model will infer from the background information that it shouldn't use to predict the plant diseases, what makes the problem worse is that some plant diseases only exist in one dataset and not the other

I am afraid that when I use the model on real-life conditions (say someone capturing an image with their phone) the model will be heavily biased towards predicting labels in the second dataset (the one with actual background) since the background is similar and it somehow associated the background with the inference process.

You are right to be concerned about this. However, you are not alone in having a neural network model that relies heavily on the background or other confounding factors for your classification task.
A small paper that addresses a similar issue is Context Augmentation for Convolutional Neural Networks. Table 1 from this paper shows how the model trained and tested on only the background performs better than model trained and tested on only the foreground. They address this by making a training set where the foreground objects are given many backgrounds. Given your imbalanced datasets, with some diseases only present in one dataset and not the other, I think context augmentation might work for you. The main barrier here is that you do not have segmentation maps for these. Are your datasets too large to segment yourself? You might consider automatic segmentation networks - especially for the images with white backgrounds.
As for your interpretability methods, you should not expect too much from them though some groups are able to get good results with them using GradCAM.
Here is an alternative idea that may also solve your problem: If you are trying to make a system that can be used in the field, is it possible to have the technician or photographer put a white board under the diseased leaf?


Why doesn't stability in prediction imply stability in control in off-policy reinforcement learning? Prediction's goal is to get an estimate of a performance of a policy given a specific state.

Control's goal is to improve the policy wrt. the prediction.

The alternation between the two is the basis of reinforcement learning algorithms.

In the paper “Safe and Efficient Off-Policy Reinforcement Learning.” (Munos, 2016), the section 3.1) "Policy evaluation" assumes that the target policy is fixed, while the section 3.2) "Control" extends to where the target policy is a sequence of policies improved by a sequence of increasingly greedy operations.

This suggests that even a proof of convergence is established with a fixed target policy, one cannot immediately imply that of the case where the target policy is a sequence of improving policies.

I wonder why it is the case. If an algorithm converges under a fixed target policy assumption, any policy during the chain of improvement should have no problem with this algorithm as well. With the merit of policy improvement, each policy in sequence is increasingly better hence converging to an optimal policy.

This should be obvious from the policy improvement perspective and should require no further proof at all?

It is a mathematical problem. Usually, we use contraction mapping theorem for the proof of convergence. You should apply the Banach fixed point theorem for Bellman's functions.


Additional (Potential) Action for Agent in MazeGrid Environment (Reinforcement Learning) In a classic GridWorld Environment where the possible actions of an agent are (Up, Down, Left, Right), can another potential output of Action be "x amount of steps" where the agent takes 2,3,.. steps in the direction (U,D,L,R) that it chooses? If so, how would one go about doing it?

You can definitely define an environment that accepts more types of action, including actions that take multiple steps in a direction.

The first thing you would need to do is implement support for that action in the environment. That is not really a reinforcement learning issue, but like implementing the rules of a board game. You will need to decide things such as what happens if the move would be blocked - does the move succeed up the point of being blocked, does it fail completely, is the reward lower depending on how much the agent tries to overshoot, etc.

After you do that, you will want to write an agent that can choose the new actions. You have a few choices here:

Simplest would be to enumerate all the choices separately and continue to use the same kind of agent as you already have. So instead of $\{U, D, L, R\}$ you might have $\{U1, U2, U3, D1, D2, D3, L1, L2, L3, R1, R2, R3\}$.
If you want to take advantage of generalisation between similar actions (e.g. that action $U3$ is similar to $U2$ and also to $R3$), then you can use some form of coding for the action, such as the relative x,y movement that it is attempting. So you could express $U2$ as $(0,2)$ and $L3$ as $(-3,0)$. For that to then work with Q values, you cannot easily use a table. Instead, you would need to use function approximation, for example a neural network, so you can implement $q(s,a)$ as a parametric function - combining $s,a$ into the input vector, and learn the parameters to that the neural network outputs the correct action value. This is what the Q learning variation DQN can do, as well as other similar RL algorithms that use neural networks.

Using a neural network, instead of tabular Q-learning, is not something you see often with grid world environments. It is a step up in complexity, but it is often required if state space or action space becomes large and might benefit from the generalisation possible from trainable function approximators.


Does artificial intelligence write its own code? Does artificial intelligence write its own code and then execute it? If so, does it create separate functions for each purpose?

Does artificial intelligence write its own code and then execute it? If so, does it create separate functions for each purpose?

Artificial intelligence comprises more than one technique. Here you seem to be asking about machine learning, a subfield of AI which itself contains many subfields.

Self-modifying code is one of the (many) techniques used in some applications of artificial intelligence.  So, in that sense, the answer to your question is "yes".

In Neural Networks (NNs), for example, the NN isn't writing any code, it is just running through an optimization algorithm (and back-propagation) that incrementally changes some weights (or coefficients) such that when you enter a certain input, you get an output that's close to the desired output.

You also have genetic algorithms (GA) to evolve the weights of a neural network, as opposed to using back-propagation. GAs are closer to the idea of "an AI coding itself" (although not exactly).


Optimal RL function approximation for TicTacToe game I modeled the TicTacToe game as a RL problem - with an environment and an agent.

At first I made an "Exact" agent - using the SARSA algorithm, I saved every unique state, and chose the best (available) action given that state. I made 2 agents learn by competing against each other.

The agents learned fast - it took only 30k games for them to reach a tie stand-off. And the agent clearly knew how to play the game.

I then tried to use function approximation instead of saving the exact state. My function was a FF-NN. My 1st (working) architecture was 9 (inputs) x 36 x 36 x 9 (actions). I used the semi-gradient 1-step SARSA. The agents took much longer time to learn. After about 50k games they were still less good than the exact agent. I then made a stand off between the Exact and the NN agent - the exact agent won 1721 games from 10k, the rest were tied. Which is not bad.

I then tried reducing the number of units in the hidden layers to 12, but didn't get good results (even after playing for 500k+ games total, tweaking stuff). I also tried playing with convolution architectures, again - not getting anywhere.

I am wondering if there's some optimal function approximation solution that can get as-good of results as the exact agent. TicTacToe doesn't seem like such a hard problem for me.

Conceptually I think there should be much less complexity involved in solving it then can be expressed in a 9x36x36x9 network. Am I wrong, and it's just an illusion of simplicity? Or are there better ways? Maybe modeling the problem differently?

I think you can break this problem down into two parts to try and find the solution.

1. Can the neural network model the desired function?

Take the tabular function you have learned in the exact agent, and treat it as training data for the neural network model, using the same loss function and other hyperparameters as you intend to use when the NN is being used online inside the RL inner loops.

You can answer two related questions with this:

Does the loss reduce down to a low value after a suitable number of epochs? If so, then the NN has capacity to learn and can learn fast enough. If not, you need to look at the hyperparameters of the NN.
Does the trained NN play well against the exact agent? Ideally it plays the same, but it is possible that even though the loss is low, one or two key values in the function are compromised, meaning it still loses. I am not entirely sure what you would do in this case, but either try changing the hyperparameters to increase the capacity of the NN, or try augmenting the data so that there are more examples of the "difficult" action values to learn, to see if the issue is something that can be solved in learning.

Probably you will find your NN architecture is good, or only requires minor changes to become useful. The more likely issues are in next section.

2. Is the RL framework set up correctly for function approximation?

It is quite hard to get this right. Bootstrapping value based methods can easily become unstable if converted naively from tabular to function approximation approaches. Some variants are moderately stable - most stable would probably be Monte Carlo approaches.

If you don't want to use Monte Carlo control, then the answer here would be to take ideas from DQN used originally to play Atari games:

Don't learn online. Store transitions in an experience replay table - store $(s, a, r, s', done)$ tuples where $done$ is true if $s'$ is a terminal state - and sample a minibatch from it on every step. Reconstruct the bootstrap estimates of value functions to train from each time you sample, don't store and re-use the estimate from the time the action was taken.
Optionally use two value estimators - the current learning one, used to select plays and which is updated on each step, and a "target" one used to calculate TD targets. Update the target network by cloning the learning network every N steps (e.g. every 100 games).
To avoid figuring out hyperparameters for SARSA epsilon decay, I suggest use one-step Q learning. Also one issue you may be facing with SARSA combined epsilon decay is "catastrophic forgetting" where the agent gets good, starts to train itself only on play examples by good players, and forgets the values of states that it has not seen in the training data for many time steps. With Q learning you can avoid that by having a relatively high minimum epsilon e.g. 0.1.

In fact with TicTacToe learning through self-play, you can get away with $\epsilon = 1$ and Q learning should still work - i.e. it can learn optimal play by observing random self-play. This should apply equally tabular and function approximation agents. It doesn't scale to more complex games where random play would take too long to discover optimal strategies.


Which machine learning algorithm is suitable for detecting text w.r.t set of words Considering the scenario where supervised training data-set in the form of sentence will be given to train the machine

  The Bomb which had been planted by Terrorist on this morning was
  defused by the Counter Terrorist on joining hands with the
  Intelligence Force

Input strings in the sentence containing each words are broken into tokenised
arrays of single words with stop words removed.

Each word in the given sentence gets assigned a label w1, w2 and so on i.e,
w2  = Bomb
w6  = planted
w13 = defused

Calculating the scores for individual word combinations, the result should yield something like:
w2.w6  = Scores should be Positive (or > some threshold value)
w2.w13 = Scores should be Negative (or < some threshold value)

In case of words with polarity changers
Eg.: Bomb wasn't/haven't/didn't got defused.
The resulting scores should be positive

To accomplish this task I had implemented Sentiment Analysis with the threshold = 2.5 and ended up with the following scores

Actual Output:

  < 2.5 : Low
  = 2.5 : Neutral
  > 2.5 : High

Expected Output:

  Case 1: score = negative, since that bomb was defused or removed in the given sentence
  Case 2: score = positive, vice versa of "Case 1"
  Case 3: Otherwise score = 0, in case it can't predict either of the above two cases, it should be neutral

I am facing a severe problem every time I need to update the vocabulary list with upcoming new words that were not in the dictionary list, which is turning out to be Semi-supervised learning.

Referring to the above sentence to calculate the w(n-(1/2/3/...n) and wn word with reference to word = Bomb. The final resulting score should yield as negative.

So which machine learning algorithm would be appropriate that fits to yield a better solution and based on the given data set how will I train the machine to learn the above things?

Finally should I try to implement by keeping the model persistence. So that it doesn’t have to be trained on each run.

If your main issue is dealing with new vocabulary, you could try using a parts-of-speech tagger as a pre-processing step. You would then effectively discover relationships between "noun" and "verb", which does not change with new words. Taggers usually can handle unknown words by using contextual information.

So you'd tag the words with their word class labels, and use those for training.

In 'application mode' you use p-o-s tags again, calculate the scores, and then map them back onto your original word tokens.

This does of course loose you some information, as you're only dealing with N-V, rather than bomb-plant or bomb-defuse. To solve this I'd use a hybrid approach: for your known vocabulary you use the word tokens, whereas for unknown words you fall back on tags. If you train two classifiers, one with tokens, one with tags, you have the tags one as a 'safety net' to handle out-of-vocab words.


Why do we need target network in deep Q learning? I already know deep RL, but to learn it deeply I want to know why do we need 2 networks in deep RL. What does the target network do? I now there is huge mathematics into this, but I want to know deep Q-learning deeply, because I am about to make some changes in the deep Q-learning algorithm (i.e. invent a new one). Can you help me to understand what happens during executing a deep Q-learning algorithm intuitively?

In DQN that was presented in the original paper the update target for the Q-Network is $\left(r_t + \max_aQ(s_{t+1},a;\theta^-) - Q(s_t,a_t; \theta)\right)^2$ were $\theta^-$ is some old version of the parameters that gets updated every $C$ updates, and the Q-Network with these parameters is the target network.
If you didn't use this target network, i.e. if your update target was $\left(r_t + \max_aQ(s_{t+1},a;\theta) - Q(s_t,a_t; \theta)\right)^2$,  then learning would become unstable because the target, $r_t + \max_aQ(s_{t+1},a;\theta)$, and the prediction, $Q(s_t,a_t; \theta)$, are not independent, as they both rely on $\theta$.
A nice analogy I saw once was that it is akin to a dog chasing it's own tail - it will never catch it because the target is non-stationary; this non-stationarity is exactly what the dependence between the target and the prediction cause.


What's the likelihood in Bayesian Neural Networks? I'm trying to understand the concept behind BNN.
Their are based on the Bayes Theorem:
$$p(w \mid \text{data}) = \frac{p(\text{data} \mid w)*p(w)}{p(\text{data})}$$
which boils down to
$$\text{posterior} = \frac{\text{likelihood} * \text{prior}}{\text{evidence}}.$$
I understand that if we assume a Gaussian distribution for the model, the likelihood function comprises a product (or sum if we use log) of each data point inserted into the Gaussian pdf. The parameters which we can change are $\mu$ and $\sigma^2$. We want to increase the likelihood because higher values of the Gaussian pdf means higher probability.
How do things work when using a neural network? I assume that the likelihood function looks s.th. like inserting each data point inside the calculation (weighted sums) of the neural network. But does the neural network need a softmax layer at the end so that we can interpret the outputs as probabilities/likelihoods? Or do we measure likelihood by applying some error measurement like cross-entropy or squared-loss?

The likelihood depends on the task that you are solving, so this is similar to traditional neural networks (in fact, even these neural networks have a probabilistic/Bayesian interpretation!).

For binary classification, you should probably use a Bernoulli, which, in practice, corresponds to using a sigmoid with a binary cross-entropy (you can show that the minimization of the cross-entropy is equivalent to the maximization of Bernoulli p.m.f.)

If it's a multi-class classification problem, you should use a categorical distribution, which corresponds to a softmax with a categorical cross-entropy; see e.g. this implementation

If it's a regression problem, the likelihood could be a Gaussian (which is equivalent to using the MSE: you can also show this).

In the case of (mean-field) variational BNNs (VBNNs) (note that not all neural networks denoted as BNNs are VBNNs, but here I will only focus on VBNNs), rather than directly performing Bayesian inference (i.e. applying the Bayes theorem directly), you will perform approximate inference and, more specifically, you cast the inference problem as an equivalent optimization problem, where you typically optimize the loss function known as the evidence lower bound (ELBO), which is composed of two terms

the (log-)likelihood of the parameters (so the Bernoulli/categorical/Gaussian)
the KL divergence (the regularization part)

Theoretically, given that I am not a statistician, I cannot tell you right now why we can have a Bernoulli likelihood and a Gaussian prior (which is typically the case and, more specifically, in the case of this paper, they assume the weights to be independent, which is kind of a strong assumption but simplifies the computations, so this leads to a factorized multi-variate Gaussian over the weights), but this is what I had seen in practice.


What happens when the agent faces a state that never before encountered? I have a network with nodes and links, each of them with a certain amount of resources (that can take discrete values) at the initial state. At random time steps, a service is generated, and, based on the agent's action, the network status changes, reducing some of those nodes and links resources.
The number of all possible states that the network can have is too large to calculate, especially since there is the random factor when generating the services.
Let's say that I set the state space large enough (for example, 5000), and I use Q-Learning for 1000 episodes. Afterwards, when I test the agent ($\max Q(s,a)$), what could happen if the agent faces a state that did not encounter during the training phase?

Having too many states to actually visit is a common problem in RL. This is exactly why we often use function approximation. If you replace your q table with a good function approximator such as a neural network, it should be able to generelize well to states it has not yet encountered.
If you do not use a function approximator but stick with a table, the agent will have no idea what to do when it encounters a new state. For more information,  see Reinforcement Learning  by Sutton and Barto, chapter 9.


Why is embedding important in NLP, and how does autoencoder work? People say embedding is necessary in NLP because if using just the word indices, the efficiency is not high as similar words are supposed to be related to each other. However, I still don't truly get it why.

The subword-based embedding (aka syllable-based embedding) is understandable, for example:

biology   --> bio-lo-gy
biologist --> bio-lo-gist

For the 2 words above, when turning them into syllable-based embeddings, it's good because the 2 words will be related to each other due to the sharing syllables: bio, and lo.

However, it's hard to understand the autoencoder, it turns an index value into vector, then feed these vectors to DNN. Autoencoder can turn vectors back to words too.

How does autoencoder make words related to each other?

The subword-based embedding is rather visual and easily understandable. However, the autoencoder embedding is what machines understand the componential meaning of words.

1) An autoencoder embedding layer can be trained together with other layers to fit with the relation of data in dataset.

2) Or the embedding layer can be kept unchanged as used as a function, required that the embedding layer must have been trained on a similar task like said in 1)

And as stated in the question, embedding is important in NLP as word indices don't show the full meanings of words, they must be separated into embedding values for better efficiency.

TensorFlow random uniform trainable embedding: https://www.tensorflow.org/api_docs/python/tf/keras/layers/Embedding

TensorFlow utility class for creating subword-based encoder: https://www.tensorflow.org/datasets/api_docs/python/tfds/features/text/SubwordTextEncoder


DQN layers when state space and action space are multi dimensional I have built my own RL environment, where a state is composed of two elements: the agent's position and a matrix of 0s and 1s (1 if a user has requested a service from the agent, 0 otherwise); an action is composed of 3 elements: the movement the agent chooses (up, down, left or right), a matrix of 0s and 1s (1 if a resource has been allocated to a user, 0 otherwise), and a vector representing the allocation of another type of resource (the vector contains the values allocated to the users).
I am currently trying to build a Deep Q Learning agent, I am a bit confused however as to what model (example Sequential), what type of layers (example Dense layers), how many layers, what activation mode I should use, and what the state and action sizes are. (Taking this code as a reference cartpole dqn agent)
I also do not know what my inputs and outputs should be.
The examples I have come across are rather simple and I don't know how to approach setting it all up for my agent.

This is not necessarily the only way to do this but it would be the approach I'd take.
Assuming your agents position is a vector in $\mathbb{R}^d$, then I would have the network take as input this position vector and pass it through a fully connected layer. I would also take as input the matrix and pass it through a convolutional layer(s) and flatten the output so it is now also a vector in $\mathbb{R}^{d'}$. I would then concatenate these together so you have a vector in $\mathbb{R}^{d + d'}$ and pass this through some fully connected layers as usual.
As for how many layers and which activation to use this is something you'll have to do by trial and error as this really is problem specific.
Your output would typically be a score for each of the action combinations, though as one of your outputs is a matrix this could potentially make things expensive to compute as you would need $2^{n \times m}$ binary representations just for the matrix ($n$ is the number of rows and $m$ is the number of columns).


Can I have different rewards for a single action based on which state it transitions to? I am working on an MDP where there are four states and ten actions. I am supposed to derive the optimal policy to reach the desired state. At any state, a particular action can take you to any of the other states.
For ex. If we begin with state S1 -> performing action A1 on S1 can take you to S2 or S3 or S4 or just stay in the same state S1. Similarly for other actions.

My question is - is it mandatory to have only a single reward value for a single action A? Or is it possible to give a reward of 10 if action a1 on state s1 takes you to s2, give a reward of 50 if action a1 on state s1 takes you to s3, give a reward of 100 if action a1 on state s1 takes you to s4 which is the terminal state or give zero reward if that action results in the state being unchanged.

Can I do this??

Because in my case every state is better than its previous state. i.e S2 is better than S1, S3 is better than S2 and so on. So if an action on S1 is directly taking u to S4 which is the final state i would like to award it the maximal reward.

The reward function can be a function of the current state, current action, and next state: $R(s_t, a_t, s_{t+1})$. It's valid to use the Bellman operator in this setting because it's still a contraction and will yield the optimal value function.

NOTE: I'm assuming that you will be solving the MDP with the Bellman equation.


Why does AlphaGo Zero select move based on exponentiated visit count? From the AlphaGo Zero paper, AlphaGo Zero uses an exponentiated visit count from the tree search.

Why use visit count instead of the mean action value $Q(s, a)$?

The answer is surprisingly hidden in the original AlphaGo paper:

  At the end of search AlphaGo selects the action with maximum visit count; this
  is less sensitive to outliers than maximizing action value.

Unfortunately, there did not appear to be further details in the paper or in the related reference. The root child node (corresponding to an action) with maximum visit count is fittingly known as the robust child, as described here and referenced in a MCTS survey here.


How do I identify a monologue or dialogue in a conversation? How do I identify monologues and dialogues in a conversation (or transcript) using natural language processing? How do I distinguish between the two?

There are a few different ways you could frame the problem...

For example, the simplest, yet probably not the most effective, would be to treat it as a supervised classification task.

In this case, you would gather data, split it into 2 classes(binary). With one dataset consisting of dialogues and the other monologues. Obviously, this framing comes with it's own set of problems. Namely, how do you prepare the dataset, or how do you deal with live examples?

Of course, there are other ways you could tackle the problem, perhaps the detection context. It all depends on what you feel is the easiest tenable solution given the variables involved in your specific instance.


How should I handle action selection in the terminal state when implementing SARSA? I recently started learning about reinforcement learning. Currently, I am trying to implement the SARSA algorithm. However, I do not know how to deal with $Q(s', a')$, when $s'$ is the terminal state. First, there is no action to choose from in this state. Second, this $Q$-factor will never be updated either because the episode ends when $s'$ is reached. Should I initialize $Q(s', a')$ to something other than a random number? Or should I just ignore the $Q$-factors and simply feed the reward $r$ into the update?

The value $Q(s', ~\cdot~)$ should always be implemented to simply be equal to $0$ for any terminal state $s'$ (the dot instead of an action as second argument there indicates that what I just wrote should hold for any action, as long as $s'$ is terminal).

It is easier to understand why this should be the case by dissecting what the different terms in the update rule mean:

$$Q(s, a) \gets \color{red}{Q(s, a)} + \alpha \left[ \color{blue}{r + \gamma Q(s', a')} - \color{red}{Q(s, a)} \right]$$

In this update, the red term $\color{red}{Q(s, a)}$ (which appears twice) is our old estimate of the value $Q(s, a)$ of being in state $s$ and executing action $a$. The blue term $\color{blue}{r + \gamma Q(s', a')}$ is a different version of estimating the same quantity $Q(s, a)$. This second version is assumed to be slightly more accurate, because it is not "just" a prediction, but it's a combination of:

something that we really observed: $r$, plus
a prediction: $\gamma Q(s', a')$

Here, the $r$ component is the immediate reward that we observed after executing $a$ in $s$, and then $Q(s', a')$ is everything we expect to still be collecting afterwards (i.e., after executing $a$ in $s$ and transitioning to $s'$).

Now, suppose that $s'$ is a terminal state, what rewards do we still expect to be collecting in the future within that same episode? Since $s'$ is terminal, and the episode has ended, there can only be one correct answer; we expect to collect exactly $0$ rewards in the future.


Does data skew matter in classification problem? I'm working on a image classification problem using neural-network. In the training data set, 90% of the samples fall into 10% of all categories, while 10% of the sample fall into the other 90% categories. So example is not evenly distributed among all categories. If we assume this distribution reflects the real world distribution, do I need to filter my dataset before training so that each category has similar number of samples?

Thanks a lot!

Yes. Skewed data is one of the biggest problems in AI applications. As you rightly identified, the real world distribution is skewed. Doing a random sampling results in one major issue of an uneven sampling (like in your case). Even worse could happen, all of the samples may fall into a single class and other classes may not even be recognized by your classifier. This is called as the class imbalance problem.

There are many ways to mitigate this problem. Few of them have been mentioned here. I'll summarize them for you:

Sampling based mitigation (when you try to deal with skewed data)
Cost function based mitigation (when you try to improve the classifier, in case skewed data cannot be avoided)

Sampling based mitigation can be done by oversampling from the minority class(es), or undersampling from the majority class(es) or using a combination of both.

Another fairer method to do this is by doing a stratified sampling. If class A has 1/6th, class B has 2/6th and class C has 3/6th of the total population, then, you should take 1/6th of the samples by random sampling from objects in class A, 2/6th from class B and 3/6th from class C. This way all of the sample may represent the population in the right proportion, and none of the classes will be missed.

In case this doesn't help (say, you dataset is small and sampling doesn't make sense) and the data is skewed too much), the cost function can be modified to make a more sensible classifier. Keep different costs for misclassification and/or correct classification. Misclassification could be given a higher penalty. This could help in reaching to a better classifier with a skewed data.