Why is it harder to achieve good results using neural network based algorithms for multi step time series forecasting? There are different kinds of machine learning algorithms, both univariate and multivariate, that are used for time series forecasting: for example ARIMA, VAR or AR.

Why is it harder (compared to classical models like ARIMA) to achieve good results using neural network based algorithms (like ANN and RNN) for multi step time series forecasting?

ANNs & RNNs can be used to create some great models in many different domains, including time-series forecasting. However, across all of these domains, they suffer from the problem of hyper-parameter optimization. Because neural networks are so flexible, it is not clear, at the outset, which arrangement of neurons will be most effective to solve a given problem. It is also not clear how fast the network should learn from new signals, what sorts of activation functions to use in the different layers of the network, and which of several possible regularization methods might be best. Making these decisions well requires either years of practice and experience, or a lot of trial and error (or, maybe both!).

In contrast, a regression-based method like ARMA will typically have just a couple of simple hyperparameters, each of which has a clear, intuitive, meaning. This means that an untrained practitioner can probably get an ARMA result that is close to the result of a trained practitioner using ARMA.

Essentially: neural networks are brittle and sensitive to the choice of hyper-parameters, while regression generally is not.


How does Monte Carlo have high variance? I was going through David Silver's lecture on reinforcement learning (lecture 4). At 51:22 he says that Monte Carlo (MC) methods have high variance and zero bias. I understand the zero bias part. It is because it is using the true value of value function for estimation. However, I don't understand the high variance part. Can someone enlighten me?

When using terms like "high" for high variance, this is in comparison to other methods, mainly in comparison to TD learning, which bootstraps between single time steps.

It is worth spelling out what the variance applies to and where it comes from: Namely the Monte Carlo return $G_t$ distribution, which can be calculated as follows:

$$G_t = \sum_{k=0}^{T-t-1}\gamma^k R_{t+k+1}$$

I am using a common convention here by the way that capital letters such as $G_t$ stand for random distributions of variables and lower case letters such as $g_t$ stand for examples/samples from those distributions. It is not always strictly used, especially in pseudo-code, but is important to make clear for this answer.

So a value function, such as action value function $q_{\pi}(s,a)$ can be written:

$$q_{\pi}(s,a) = \mathbb{E}_{\pi} [ \sum_{k=0}^{T-t-1}\gamma^k R_{t+k+1} | S_t=s, A_t=a] = \mathbb{E}_{\pi} [ G_t | S_t=s, A_t=a]$$

i.e. it is fairly clear that the mean of Monte Carlo return $\mathbb{E}[G_t]$ from any specific starting point is the same as the value function from the same starting point, by definition (see Sutton & Barto or David Silver's definitions) so samples from it - taking specific measures $g_t$ - are unbiased estimates of it.

The variance $\text{Var}(G_t)$ might be written

$$\text{Var}(G_t) = \text{Var}(\sum_{k=0}^{T-t-1}\gamma^k R_{t+k+1}) \le \sum_{k=0}^{T-t-1}\gamma^k \text{Var}(R_{t+k+1})$$

The second step is technically equal only in a "worst case" scenario since to add variances directly, we need the variables to be independently sampled, whilst $R_{t}$ and $R_{t+1}$ could be correlated, and often are. So, technically we should account for covariance here between distribitions on different time steps. The maths for that is fiddly, and I won't show it here.

What you can say intuitively about the inequality, is unless $R_{t}$ and $R_{t+1}$ are perfectly correlated throughout each trajectory, then variance of $G_t$ will increase depending on the number of timesteps and possible rewards in the return, by some fraction between 0 and 1 of the total variance of all time steps. You can either add zero variance on a timestep, or some fraction of $\text{Var}(R_{t+n})$ depending on whether the relationship between [$R_t$ to $R_{t+n-1}$] and $R_{t+n}$ is fully deterministic ($+0$) or completely independent ($+\gamma^{n-1}\text{Var}(R_{t+n})$)*

The amount of covariance involved relies on details of the policy, state transition and reward functions. In general, the policy during RL will include some stochastic behaviour -such as $\epsilon$-greedy that will add to the variance on each time step. The state transition and reward functions might add yet more. In any case:

$$\text{Var}(G_t) \ge \text{Var}(R_{t+1})$$

and in practice, when $t+1 \neq T$, the inequality can be large, although highly dependent on the details of the MDP. For off-policy Monte Carlo with basic importance sampling in fact the variance can be unbounded.

This variance might be considered high, compared to the variance of typical single-step TD returns:

$$G_{t:t+1} = R_{t+1} + \gamma q_{\pi}(S_t, A_t)$$

The variance of which is limited to that inherent in a single time step (one reward function, one state transition and one policy decision). The problem of course being that

$$\mathbb{E}[G_{t:t+1}] \neq \mathbb{E}[G_{t}]$$

. . . unless $q_{\pi}(s, a)$ is perfect. Which is why we can say that TD returns are biased (whilst $q_{\pi}(s, a)$ is not converged, the expectation of the TD target does not equal the true value), but Monte Carlo returns are higher variance (when number of timesteps to end of trajectory is more than one, the effects of random factors in policy, state transition and reward function accumulate).

* You could explicitly construct an environment with covariance between time steps that can reduce overall variance of a MDP's retrun, e.g. the state includes reward so far, and future rewards are manipulated so that the return fits to a certain distribution. This would be a special case where variance of the return from some starting points could be lower than the variance from the first step, but this is an unusual set up and likely to be impossible for an agent to learn optimal control.


What AI conferences in Europe should I consider submitting papers to explaining the ongoing work on RefPerSys? https://afia.asso.fr/journee-hommage-j-pitrat/ is a seminar on March 6th, 2020, in Paris (France, European Union), in honor of the late Jacques Pitrat, who advocated during all his professional life a meta-knowledge and reflective approach. (You need to register to attend that seminar).

Pitrat's blog is available (in spring 2020) on http://bootstrappingartificialintelligence.fr/WordPress3/ (and some snapshot of his CAIA system is downloadable here - but no documentation; however you might try to type L EDITE on stdin to caia). He wrote the Artificial Beings : the conscience of a conscious machine book describing the software architecture of, and the motivations for (some previous version of) CAIA. See also this A Step toward an Artificial Artificial Intelligence Scientist paper by J.Pitrat.

What AI conferences (or AGI workshops) in Europe should I consider submitting papers to explaining the ongoing work on RefPerSys?

That RefPerSys project (open source, open science, work-in-progress, with contact information) is explicitly following J.Pitrat's meta-knowledge approach. Feel free to follow or join that ambitious open-source (actually free software) project.

Probably to as many as possible. Average accept rate of papers is around 20%. You can find the best conferences on AI & ML Event.


What are the most challenging tasks aiming to achieve the lowest error rate? For example there is the MNIST database which is used to test artificial neural network (ANN), however it's not so challenging, because some hierarchical systems of convolutional neural networks manages to get an error rate of 0.23 percent.

Are there any similar, especially the most challenging tasks with dataset which are used as benchmark tests to challenge the AI which are fairly reliable and it's possible to pass, but most AAN are struggling to achieve the lower error rate?

Yes. Here are some of the most prominent ones and their respective state-of-the-art errors:

CIFAR-10: ~3.5% error
CIFAR-100: ~24% error
STL-10: ~26% error
SVHN: ~1.7% error
ImageNet tasks: the best 2012 classification task solution got 15% top-5 error, better results are currently available

You can check an updated list of solutions here. Also, a more comprehensive list of modern datasets can be found here.


Is Prolog still used in AI? According to Wikipedia,

  Prolog is a general-purpose logic programming language associated with artificial intelligence and computational linguistics.

Is it still used for AI?

This is based off of a question on the 2014 closed beta. The author had the UID of 330.

Remembering that artificial intelligence has been an academic endeavour for the longest time, Prolog was amongst one of the early languages used as part of the study and implementation of it. It has rarely made its way into large commercial applications, having said that, a famous commercial implementation is in Watson, where prolog is used for NLP.

The University of Edinburgh contributed to the language and it was sometimes referred to as "Edinburgh Prolog". It is still used in academic teachings there as part of the artificial intelligence course.

The reason why Prolog is considered powerful in AI is because the language allows for easy management of recursive methods, and pattern matching.

To quote Adam Lally from the IBM Thomas J. Watson Research Center, and Paul Fodor from Stony Brook University:

  the Prolog language is very expressive allowing recursive rules to represent reachability in parse trees and the operation of negation-as-failure to check the absence of conditions.


What type of reinforcement learning can I do restricted to ~200MB on an average smartphone? This concerns a set of finite, non-trivial, combinatorial games [M] in the form of an app. A sample game can be found here.

Because this is a mass market product, we can't take up too much space, and the AI needs to be able to run locally since connectivity cannot be assumed. The current size of the Android kernel is < 7MB.

The goal is not sheer AI strength, but respectable AI strength, sufficient to beat the above-average human player. (The current strongest, weak automata, using a few heuristics, is already capable of beating the average human player.)

Because the games are finite, the gametrees eventually become tractable, allowing for perfect endgames.  Resource stealing strategies and trap-avoidance can also be effected with shallow look-ahead at all phases, and the patterns are much easier for automata to recognize than for humans.

In this context, reinforcement would be mostly utilized to "tune the automata to the style of the human player," and produce different automata on different devices, which could subsequently play against each other as proxies for their human partners.

The game data can be stored efficiently, initially requiring only 2 bytes per position (a value 0-9 and a coordinate 1-81, although the number of coordinates will grow in basic game extensions, and require 2 bytes for larger-order gameboards such as "Samurai" Sudoku.) So the first turn on a given game requires only 2 bytes, the second turn bytes, etc., up to between 50 and 70 turns on an 81 cell gameboard.  Additionally, because it's a square grid, we can reduce for symmetry.  But even with an average number of turns at 50, that's only about 40,000 games for 200MB.

Weighting Openings

My feeling is that reinforcement would be useful in weighting openings.  If the game data is a string, these strings can be compared, and the smaller the sample size (the fewer the turns included,) the more connections there will be. In this case, the sequence doesn't matter, only the set of value/coordinates for a given turn. Abstraction can be utilized in that certain individual value/coordinates are interchangeable. My thought is the automata can weight openings based on how often they lead to desirable outcomes in the form of a win.

Weighting Heuristics

Since we're having good, initial results with heuristics, and these are the most efficient method of decision-making, I'm thinking about weighting evaluation functions so that certain heuristics take precedence under different conditions.  (For instance, when to expand vs. when to consolidate. When to make a choice with immediate benefit over a choice with long-term benefit. Introduction of meta-strategies that modify foundation strategies.)

Database pruning

Because the allocated volume will be capped, it's probably going to be necessary to "prune" the database when info is no longer relevant. (For instance, when a new strategy emerges that renders previous strategies obsolete.) We also probably need a method to help the automata to recognize such situations, so it doesn't persist in potentially obsolete strategies for more than two games without starting to try alternatives.

Q: Can reinforcement learning be meaningfully applied toward these goals under these restrictions?

Q: Are my inclinations for approaching this useful or problematic?

Q: Are there methods I'm not considering that could be applicable under these restrictions?

I skimmed through your question and understood that the state/action space is finite, so in this case, RL would be a good option for storage.

The most basic RL technique will keep track of a matrix Q ∈ ℝs×a, where s is number of possible states, and a is number of possible actions.

In addition to a small overhead of agent's parameters:

α ∈ [0,1] learning parameter
γ ∈ [0,1] discount rate,
ε ∈ [0,1]  exploration rate

If you have a total of 81 states and 10 actions, then your storage would be in the neighborhood of 850 double words.

If your AI will track different states per location, e.g. possible values 0 to 9 + a null, then your state space will grow to 11 * 81 = 968 and the final value matrix will be Q ∈ ℝ968×10 ≈ 20Kb.

Update

I am terrible sorry, I made a terrible mistake in my calculations.
if you are to keep track of 11 possible values in 81 locations, then the correct number should be 1181× double word size, that is a big number.

Of course, if this is Sudoku and you  and you are not considering illegal moves as possible states, then definitely this will be a way smaller number, but you will still keep track of an action space that is as big as the state space.

You might need to use function approximation instead, or some sort of action state space compression.

sorry


Why is 100% exploration bad during the learning stage in reinforcement learning? Why can't we during the first 1000 episodes allow our agent to perform only exploration?
This will give a better chance of covering the entire space state. Then, after the number of episodes, we can then decide to exploit.

Why can’t we during the first 1000 episodes allow our agent perform only exploration

You can do this. It is fine to do so either to learn the value function of a simple random policy, or when performing off-policy updates. It is quite normal when learning an environment from scratch in a safe way - e.g. in simulation - to collect an initial set of data from behaving completely randomly. The amount of this random data varies, and usually the agent will not switch from fully random to fully deterministic based on calculated values as a single step, but will do so gradually.

this will give a better chance of covering the entire space state

That will depend on the nature of the problem. For really simple problems, it may explore the space sufficiently to learn from. However, for many problems it is just a starting point, and not sufficient to cover parts of the space that are of interest in optimal control.
When behaving completely randomly, the agent may take a very long time to complete an episode, and may never complete its first episode. So you could be waiting for a long time to collect data for the first 1000 such episodes. An example of this sort of environment would be a large maze - the agent will move back and forth in the maze, revisiting same parts again and again, where in theory it could already be learning not to repeat its mistakes.
In some environments, behaving completely randomly will result in early failure, and never experiencing postive rewards that are available in the environment. An example of this might be a robot learning to balance on a tightrope and get from one end to the other. It would fall off after a few random actions, gaining very little knowledge for 1000 episodes.
The state space coverage you are looking for ideally should include the optimal path through the space - at least at some point during learning (not necessarily the start). This does not have to appear in one single perfect episode, because the update rules for value functions in reinforcement learning (RL) will eventually allocate the correct values and find this optimal path in the data. However, the collected data does need to include the information about this optimal path amongst all the alternatives so that the methods in RL can evaluate and select it. In simple environments acting randomly may be enough to gain this data, but becomes highly unlikely when the environments are more complex.

then after the number of episodes, we can then decide to exploit

Again this might work for very simple environments, where you have collected enough information through acting randomly to construct a useful value function. However, if acting randomly does not find enough of the optimal path, then the best that exploitation can do is find some local optimum based on the data that was collected.
I suggest you experience this difference for yourself: Set up a toy example environment, and use it to compare different approaches for moving between pure exploration and pure exploitation. You will want to run many experiments (probably 100s for each combination, averaged) to smooth out the randomness, and you can plot the results to see how well each approach learns - e.g. how many time steps (count time steps, not episodes, if you are interested in sample efficiency) it takes for the agent to learn, and whether or not it actually finds the correct optimal behaviour. Bear in mind that the specific results will only apply in your selected environment - so you might also want to do this comparison on a small range of environments.


Should I prefer the model with the lowest validation loss or the highest validation accuracy to deploy? I trained a ResNet20 on Cifar10 and obtained the following learning curves.

From the figures, I see at epoch 52, my validation loss is 0.323 (the lowest), and my validation accuracy is 89.7%.

On the other hand, at the end of the training (epoch 120), my validation loss is 0.413 and my validation accuracy is 91.3% (the highest).

Say I'd like to deploy this model on some real-world application. Should I prefer the snapshotted model at epoch 52, the one with lowest validation loss, or the model obtained at the end of training, the one with highest validation accuracy?

Okay, I think it's better if we distinguish loss and accuracy first via Jeremy's answer, and I agree with him with the sentence "low or huge loss is a subjective metric".
The loss value is easy to affect by noise from data and significant increase with a few error data points. My advice in this case is to use more evaluation metrics, and understand correctly what you need from your model.
For example, with Cifar 10, and you need the more correct label the better, you can believe in accuracy. However, if you want your model to make sure its result is the correct, area under receiver operating characteristic curve (AUROC) maybe the better choice.
For example, classification problem with 3 class, correct label y = 1:

Good accuracy, bad AUROC: the output probability from softmax [0.3,0.4,0.3]
Good accuracy, good AUROC: [0.1,0.8,0.1]

And with imbalanced dataset, Precision, Recall and F1-score will be more suitable.


Why do all states appear identical under the function approximation in the Short Corridor task? This is the Short Corridor problem taken from the Sutton & Barto book. Here it's written:

The problem is difficult because all the states appear identical under the function approximation

But this doesn't make much sense as we can always choose states as 0,1,2 and corresponding feature vectors as
x(S = 0,right) = [1  0  0  0  0  0]
x(S = 0 , left)  = [0  1  0  0  0  0]
x(S = 1,right) = [0  0  1  0  0  0]
x(S = 1 , left) = [0  0  0  1  0  0]
x(S = 2,right) = [0  0  0  0  1  0]
x(S = 2 , left) = [0  0  0  0  0  1]\
So why is it written that all the states appear identical under the function approximation?

You can choose those states, but is the agent aware of the state it is in? From the text, it seems that the agent cannot distinguish between the three states. Its observation function is completely uninformative.
This is why a stochastic policy is what is needed. This is common for POMDPs, whereas for regular MDPs we can always find a deterministic policy that is guaranteed to be optimal.


Levenshtein Distance between each word in a given string From Calculate Levenshtein distance between two strings in Python it is possible to calculate distance and similarity between two given strings(sentences).

And from Levenshtein Distance and Text Similarity in Python to return the matrix for each character and distance for two strings.

Are there any ways to calculate distance and similarity between each word in a string and print the matrix for each word in a string(sentences)?

a = "This is a dog."
b = "This is a cat."

from difflib import ndiff

def levenshtein(seq1, seq2):
    size_x = len(seq1) + 1
    size_y = len(seq2) + 1
    matrix = np.zeros ((size_x, size_y))
    for x in range(size_x):
        matrix [x, 0] = x
    for y in range(size_y):
        matrix [0, y] = y

    for x in range(1, size_x):
        for y in range(1, size_y):
            if seq1[x-1] == seq2[y-1]:
                matrix [x,y] = min(
                    matrix[x-1, y] + 1,
                    matrix[x-1, y-1],
                    matrix[x, y-1] + 1
                )
            else:
                matrix [x,y] = min(
                    matrix[x-1,y] + 1,
                    matrix[x-1,y-1] + 1,
                    matrix[x,y-1] + 1
                )
    print (matrix)
    return (matrix[size_x - 1, size_y - 1])

levenshtein(a, b)

Outputs

>> 3

Matrix

[[ 0.  1.  2.  3.  4.  5.  6.  7.  8.  9. 10. 11. 12. 13. 14.]
 [ 1.  0.  1.  2.  3.  4.  5.  6.  7.  8.  9. 10. 11. 12. 13.]
 [ 2.  1.  0.  1.  2.  3.  4.  5.  6.  7.  8.  9. 10. 11. 12.]
 [ 3.  2.  1.  0.  1.  2.  3.  4.  5.  6.  7.  8.  9. 10. 11.]
 [ 4.  3.  2.  1.  0.  1.  2.  3.  4.  5.  6.  7.  8.  9. 10.]
 [ 5.  4.  3.  2.  1.  0.  1.  2.  3.  4.  5.  6.  7.  8.  9.]
 [ 6.  5.  4.  3.  2.  1.  0.  1.  2.  3.  4.  5.  6.  7.  8.]
 [ 7.  6.  5.  4.  3.  2.  1.  0.  1.  2.  3.  4.  5.  6.  7.]
 [ 8.  7.  6.  5.  4.  3.  2.  1.  0.  1.  2.  3.  4.  5.  6.]
 [ 9.  8.  7.  6.  5.  4.  3.  2.  1.  0.  1.  2.  3.  4.  5.]
 [10.  9.  8.  7.  6.  5.  4.  3.  2.  1.  0.  1.  2.  3.  4.]
 [11. 10.  9.  8.  7.  6.  5.  4.  3.  2.  1.  1.  2.  3.  4.]
 [12. 11. 10.  9.  8.  7.  6.  5.  4.  3.  2.  2.  2.  3.  4.]
 [13. 12. 11. 10.  9.  8.  7.  6.  5.  4.  3.  3.  3.  3.  4.]
 [14. 13. 12. 11. 10.  9.  8.  7.  6.  5.  4.  4.  4.  4.  3.]]

General Levenshtein distance for character level shown in below fig.

  Is it possible to calculate Levenshtein Distance for Word Level?

Required Matrix

          This is a cat

This
is
a
dog

well... simply put a .split() at the end of your first two lines:

a = "This is a dog.".split()
b = "This is a cat.".split()

Your algorithm works with the iterables, and the string is broken into it's characters. You do the split, and a,b would be a list of words, then your algorithm works on the word-level

Output on your example:

[[0. 1. 2. 3. 4.]
 [1. 0. 1. 2. 3.]
 [2. 1. 0. 1. 2.]
 [3. 2. 1. 0. 1.]
 [4. 3. 2. 1. 1.]]

1.0


Is there any classifier that works best in general for NLP based projects? I've written a program to analyse a given piece of text from a website and make conclusary classifications as to its validity. The code basically vectorizes the description (taken from the HTML of a given webpage in real time) and takes in a few inputs from that as features to make its decisions. There are some more features like the domain of the website and some keywords I've explicitly counted.

The highest accuracy I've been able to achieve is with a RandomForestClassifier, (>90%). I'm not sure what I can do to make this accuracy better except incorporating a more sophisticated model. I tried using an MLP but for no set of hyperparameters does it seem to exceed the previous accuracy. I have around 2000 datapoints available for training.

Is there any classifier that works best for such projects? Does anyone have any suggestions as to how I can bring about improvements? (If anything needs to be elaborated, I'll do so.)

Any suggestions on how I can improve on this project in general? Should I include the text on a webpage as well? How should I do so? I tried going through a few sites, but the next doesn't seem to be contained in any specific element whereas the description is easy to obtain from the HTML. Any help?

What else can I take as features? If anyone could suggest any creative ideas, I'd really appreciate it.

The accuracy depends on various factors. Might not always be the algorithm. For example a cleaner data with a poor algorithm might still give better results and vice versa.

What are the preprocessing techniques you are using? This preprocessing techniques article is a good starting point for html data. And by vectorising I assume you mean word2vec, use a pre-trained word2vec model. Like google's word2vec model it's trained on a lot of data(about 100 billion words).

LSTM performs good whenever the intent of the sentence is important. Check out this.
Ram hit Vijay and Vijay hit Ram, might mean the same to most algorithms. Example, Naive Bayes.


How does Watson find and evaluate its evidence to the answer? Is there any simple explanation how Watson finds and scores evidence after gathering massive evidence and analyzing the data?

In other words, how does it know which precise answer it needs to return?

Watson starts off by searching its massive database of sources for stuff that might be pertinent to the question. Next, it searches through all of the search results and turns them into candidate answers. For example, if one of the search results is an article, Watson might pick the title of the article as a possible answer. After finding all of these candidate answers, it proceeds to iteratively score them to determine which one is best.

The scoring process is very complicated, and involves finding supporting evidence for each answer, and then combining many different scoring algorithms to determine which candidate answer is the best. You can read a more detailed (but still very conceptual) overview here, by the creators of Watson.


Basic Functions and Results If the number of input neurons and output neurons doesn't change, what will change if I have one hidden layer, but first with 1 neuron, then with 4 neurons?

Taking into consideration the fact that each perceptron is able to linearly separate points on an unknown/unwritten linear function, would this then be able to, theoretically, instead of simply linearly separate points, separate points into those that occur inside a square, and those that occur outside?

This is, of course, without a bias neuron present.

If the number of input neurons and output neurons doesn't change, what will change if I have one hidden layer, but first with 1 neuron, then with 4 neurons?

I recommend that you try to implement a dense layer with Tensorflow (not using the Dense implementation, of course).

A dense layer is the full connection between to layers. What actually is learned/optimized in a neural network are the weights in between layers. Each weight is just a single floating point number. It's the connection between two nodes. If you increase the number of nodes of one layer, the two neighboring layers get more weights. Hence the optimization algorithm can adapt better.

For simplicity, I'll now assume you don't use biases.

If you have A input neurons and Z output neurons, a single hidden layer with 1 neutron means you have two matrices of shape Ax1 and 1xZ. if you change it to 4 hidden neurons the two matrices have the shape Ax4 and 4xZ


What AI concept is behind the Mars Exploration Rover (MER)? The Mars Exploration Rover (MER) Opportunity landed on Mars on January 25, 2004. The rover was originally designed for a 90 Sol mission (a Sol, one Martian day, is slightly longer than an Earth day at 24 hours and 37 minutes). Its mission has been extended several times, the machine is still trekking after 11 years on the Red Planet.

How it has been working for 11 years? Can anyone please explain how smart this rover is? What AI concepts are behind this?

The Mars Rover is a highly successful example of the 'New AI' that emerged from work by Rodney Brooks in the 1990s.

In a quote from Brooks:

  In 1984 I joined the faculty at MIT where I have been ever since. I set up a mobile robot group there and started developing robots that led to the Mars planetary rovers.

Together with the 'Allen' paper, the foundational AI articles in this area are:

"Elephants don't play chess"
"Intelligence without representation"

Although Brooks initially had difficulty getting this work published, preprints were widely circulated within the AI community. Brook's "Physical Grounding Hypothesis" (essentially: "intelligence requires a body") has now largely supplanted the preceding symbolist approach.

The capabilities of the MARS Rover are organized in a Subsumption Architecture. Rather than maintaining an integrated and complex 'world model', increasingly sophisticated behaviors are stacked in hierarchical layers. For example, 'walking' is a relatively low-level competence, with 'avoiding obstacles' and 'wandering around' being higher-level ones.

Each layer is represented by a Finite State Machine that reacts to stimuli appropriate to that level. The activity of lower levels can be suppressed ('subsumed') by higher level ones.

Here is a schematic of the bottom two layers of 'Allen', Brook's first subsumption robot:


How close have we come to passing the Turing Test? The Turing Test has been the classic test of artificial intelligence for a while now. The concept is deceptively simple - to trick a human into thinking it is another human on the other end of a conversation line, not a computer - but from what I've read, it has turned out to be very difficult in practice.

How close have we gotten to tricking a human in the Turing Test? With things like chat bots, Siri, and incredibly powerful computers, I'm thinking we're getting pretty close. If we're pretty far, why are we so far? What is the main problem?

No one has attempted to make a system that could pass a serious Turing test. All the systems that are claimed to have "passed" Turing tests have done so with low success rates simulating "special" people.  Even relatively sophisticated systems like Siri and learning systems like Cleverbot are trivially stumped.

To pass a real Turing test, you would both have to create a human-level AGI and equip it with the specialized ability to deceive people about itself convincingly (of course, that might come automatically with the human-level AGI).  We don't really know how to create a human-level AGI and available hardware appears to be orders of magnitude short of what is required.  Even if we were to develop the AGI, it wouldn't necessarily be useful to enable/equip/motivate? it to have the deception abilities required for the Turing test.


What is the best approach for writing a program to identify objects in a picture then crop them a specific way? My works quality control department is responsible for taking pictures of our products at various phases through our QC process and currently the process goes:

Take picture of product
Crop the picture down to only the product
Name the cropped picture to whatever the part is and some other relevant data

Depending on the type of product the pictures will be cropped a certain way. So my initial thought would be to use a reference to an object identifier and then once the object is identified it will use a cropping method specific to that product. There will also be QR codes within the pictures being taken for naming via OCR in the future so I can probably identify the parts that way if this proves slow or problematic.

The part I am unsure about is how to get the program to know how to crop based on a part. For example I would like to present the program with a couple before crop and after crop photos of product X then make a specific cropping formula for product X based on those two inputs.

Also if it makes any difference my code is in C#

Depending on kind and amount of data you posess, there are few approaches that you might consider.

Marking target objects on dataset and training CNN that returns coordinates of target object. In this case, remember that it is usually faster when training data ROIs have their coordinates relative to image size.
Use some kind of focus mechanism, like spatial transformer network:

https://arxiv.org/abs/1506.02025

This kind of network component is able to learn image transformation (including crop) that maximazes target metric for main classifier. This tutorial on pytorch:

https://pytorch.org/tutorials/intermediate/spatial_transformer_tutorial.html

shows some nice visualizations of STN results. Good thing about this kind of network is that, given enough data, it might learn proper transformation from image classification data (photo -> class). One does not need to explicitly mark target objects on image!
Object detection networks, like YOLO, Faster-RCNN. There are many tutorials on that matter, eg:

https://www.datacamp.com/community/tutorials/object-detection-guide

Saliency extraction. Simple idea is to generate heatmap showing what parts of input image activates classifier the most. I guess you could try calculate bounding box basing on such heatmap. Example research paper:

https://arxiv.org/abs/1805.08249

Points 1 and 2 are probably easies to implement, so I would start with them.


Why did a Tesla car mistake a truck with a bright sky? Do we know why Tesla's autopilot mistaken empty sky with a high-sided lorry which resulted in fatal crash involving a car in self-drive mode? Was it AI fault or something else? Is there any technical explanation behind this why this happened?

The articles Tesla Driver In First Self-Drive Fatal Crash and Tesla driver killed in crash with Autopilot active, NHTSA investigating talk about this topic, but do not go in detail.

Tesla's technology is assistive, as Alexey points out, so this is not a case of an autonomous system (e.g. an AGI) doing some fatal stunt (the product name AutoPilot is famously misleading). Now on why the car assistance led to this tragic accident, there is some information related to AI technologies.

Warning: I cannot find again the source critical to the next paragraph, and reading again pages over pages, I cannot find similar argument in other reports. I still remember vividly the point below, but please keep in mind it may be incorrect. The rest of the answer is weakly related, so I leave it all, with this warning.

An independent report (link needed, I can't find it...) explained that the assistive system was unable to detect the truck due to an exceptionally low contrast (bright sky perceived as white---colour of the truck). The report also said that a human driver would have been unable to make the difference either. In other words, it is possible that car sensors (presumably camera) and the human eye could not have detected an obstacle, and could not have triggered any safety measure. This short graphical explanation sums up the car sensors: Camera, radar, GPS, etc.

The assistive sub-system is based on proprietary AI technologies. We can only speculate under some hypothesis. _This is not very useful, honestly, except for illustration purpose. Assuming the assistive system relies on ML technologies to learn about obstacles from a video stream (such systems do exist):

It may be that the learning data was not "good enough" to cover the truck scenario.
It may be the technology was not powerful enough yet (lack generalization power, or simply too slow).
It may be a hardware problem, notably from the sensors: If the "car's eyes" are defective, the "car's brain" (the assistive system) is unable to react properly.

Why those technologies did not work in that case will remain a secret. We can say however that any system---whether built with AI technology or not---has limits. Beyond these limits, the system reaction is unpredictable: It could stop, reset, shutdown. The difficulty here is to define what a "default behaviour" is. A machine will basically do whatever it is designed to do, so an AI-based system too.

We could speculate even more on what would happen if the assistive system was really autonomous, the elusive AGI, but that is really not the case here.


How does being on-policy prevent us from using the replay buffer with the policy gradients? One of the approaches to improving the stability of the Policy
Gradient family of methods is to use multiple environments in
parallel. The reason behind this is the fundamental problem we
discussed in Chapter 6, Deep Q-Network, when we talked about the
correlation between samples, which breaks the independent and
identically distributed (i.i.d) assumption, which is critical for
Stochastic Gradient Descent (SDG) optimization. The negative
consequence of such correlation is very high variance in gradients,
which means that our training batch contains very similar examples,
all of them pushing our network in the same direction. However, this
may be totally the wrong direction in the global sense, as all those
examples could be from one single lucky or unlucky episode. With our
Deep Q-Network (DQN), we solved the issue by storing a large amount of
previous states in the replay buffer and sampling our training batch
from this buffer. If the buffer is large enough, the random sample
from it is much better representation of the states distribution at
large. Unfortunately, this solution won't work for PG methods, at most
of them are on-policy, which means that we have to train on samples
generated by our current policy, so, remembering old transitions is
not possible anymore.

The above excerpt is from Maxim Lapan in the book Deep Reinforcement Learning Hands-on page 284.
How does being on-policy prevent us from using the replay buffer with the policy gradients? Can you explain to me mathematically why we can't use replay buffer with A3C for instance?

Let's say your old policy is $\pi_b$ and your current one is $\pi_a$. If you collected trajectory by using policy $\pi_b$ you would get return $G$ whose expected value is
\begin{align}
E_{\pi_b}[G_t|S_t = s] &= E_{\pi_b}[R_{t+1} + G_{t+1}]\\
&= \sum_a \pi_b(a|s) \sum_{s', r} p(s', r|s, a) [r + E_{\pi_b}[G_{t+1}|S_{t+1} = s']]\\
\end{align}
You can see if you write out this recursively that this expectation depends on $\pi_b(a|s), \pi_b(a'|s'), \ldots$

If you collect trajectory with policy $\pi_a$ you would get expected return that depends on $\pi_a(a|s), \pi_a(a'|s'), \ldots$ Since these are two different policies then $\pi_b(a|s) \neq \pi_a(a|s)$ for some $(s, a)$. That would mean that returns have different expected values and are sampled through different distributions. You cannot then use some return $G$ sampled by following policy $\pi_b$ to update policy $\pi_a$ because it's not sampled according to the proper distribution, if we did, we would be updating policy $\pi_a$ with biased gradient update that does not reflect how policy $\pi_a$ performed.


What are some online courses on artificial general intelligence? Although no artificial general intelligence (AGI) has yet been created, probably, there are already some courses on the topic. So, what are some online (preferably free) courses on AGI?

There are at least three free courses.

MIT 6.S099: Artificial General Intelligence, organized by Lex Fridman, is a series of lessons and talks primarily given by a diverse set of guest appearances, such as

Josh Tenenbaum (researcher and professor in computational cognitive science),
Nate Derbinsky (who gives a lesson on cognitive architectures, Soar, etc.),
Stephen Wolfram (creator of Mathematica, Wolfram Alpha and the Wolfram Language; he talks about his work throughout the years, especially, the development of Wolfram Alpha and Language),
Marc Raibert (CEO of Boston Dynamics, who gives a lesson on his work at Boston Dynamics and the robots they have developed),
Lisa Feldman Barrett (professor of psychology, who gives a very insightful lesson on emotions and feelings, with possibly different perspectives),
Rosalind Picard (a professor at MIT, director of the Affective Computing Research Group at the MIT Media Lab, and co-founder of two companies, Affectiva and Empatica; in her talk with Lex, she talks about affective computing and other interesting concepts and issues)
Marcus Hutter (inventor of a mathematical theory of general intelligence, AIXI; in his talk with Lex, he talks about Occam's razor, Solomonoff induction, Kolmogorov complexity, the definition of intelligence, AIXI, rewards, bounded rationality and consciousness)

Knowledge-Based AI: Cognitive Systems (taught by Ashok Goel and David Joyner)

The Society of Mind (taught by Marvin Minsky, who also wrote a book and developed a theory of natural intelligence with the same name)

CS 294-149: Safety and Control for Artificial General Intelligence (Fall 2018) (see also these notes)


Deep Q Learning Algorithm for Simple Python Game makes player stuck I made a simple Python game. A screenshot is below:

Basically, a paddle moves left and right catching particles. Some make you lose points while others make you gains points.
This is my first Deep Q Learning Project, so I probably messed something up, but here is what I have:
model = Sequential()
model.add(Dense(200, input_shape=(4,), activation='relu'))
model.add(Dense(200, activation='relu'))
model.add(Dense(3, activation='linear'))
model.compile(loss='categorical_crossentropy', optimizer='adam')

The four inputs are X position of player, X and Y position of particle (one at a time), and the type of particle. Output is left, right, or don't move.
Here is the learning algorithm:
def learning(num_episodes=500):
    y = 0.8
    eps = 0.5
    decay_factor = 0.9999
    for i in range(num_episodes):
        state = GAME.reset()
        GAME.done = False
        eps *= decay_factor
        done = False
        while not done:
            if np.random.random() < eps: #exploration
                a = np.random.randint(0, 2)
            else:
                a = np.argmax(model.predict(state))
            new_state, reward, done = GAME.step(a) #does that step
            #reward can be -20, -5, 1, and 5
            target = reward + y * np.max(model.predict(new_state))
            target_vec = model.predict(state)[0]
            target_vec[a] = target
            model.fit(state, target_vec.reshape(-1, 3), epochs=1, verbose=0)
            state = new_state

After training, this usually results in the paddle just going to the side and staying there. I am not sure if the NN architecture (units and hidden layers) is appropriate for given complexity. Also, is it possible that this is failing due to the rewards being very delayed? It can take 100+ frames to get to the food, so maybe this isn't registering well with the neural network.
I only started learning about reinforcement learning yesterday, so would appreciate advice!

This is probably the most major factor:

model.compile(loss='categorical_crossentropy', optimizer='adam')

you have set the loss function for a multiclass classifier. It is going to have some weird results when values - either predicted or target - are outside of range 0..1

You should use this instead:

model.compile(loss='mean_squared_error', optimizer='adam')

because your Q network outputs the expected future return on each action. This could easily be outside of the range that 'categorical_crossentropy' is designed for.

In addition, you really need to look into experience replay. It is not an optional extra when using neural networks with Q learning - it is pretty much required for anything but the most trivial environments. It is very likely your agent will still fail to learn without experience replay, if you correct all other problems with your code.

  I am not sure if the NN architecture (units and hidden layers) is appropriate for given complexity.

It looks more complex than it needs to be, assuming that your 4 inputs represent paddle x position, particle x,y position and colour. I would suggest making the network simpler (maybe just 40 neurons per layer at a guess), to speed things up a little.

Check your input scaling. Neural networks like to train on inputs that have mean 0, standard deviation 1, and it is worth scaling them so that they fit roughly into -1..1 or similar. Your feature engineering is not shown in your code, so it might be an issue.

  Also, is it possible that this is failing due to the rewards being very delayed?

This can be a factor that makes learning harder.

  It can take 100+ frames to get to the food, so maybe this isn't registering well with the neural network.

100 time steps delay between rewards is not much for DQN. It should be correctly predicting Q values - it will just take more episodes to learn to predict the best movement when the food is further away.


When are Q values calculated in experience replay? In experience replay, the update rule follows the loss:

$$
L_i(\theta_i) = \mathbb{E}_{(s_t, a_t, r_t, s_{t+1}) \sim U(D)} \left[ \left(r_t + \gamma \max_{a_{t+1}} Q(s_{t+1}, a_{t+1}; \theta_i^-) - Q(s_t, a_t; \theta_i)\right)^2 \right]
$$

I can't get my head around the order of calculation of the terms in that equation:
An experience element is

$(s_t, a_t, r_t, s_{t+1} )$

where

$s_t$ is the state at time $t$
$a_t$ is the action taken from $s_t$ at time $t$
$r_t$ is the reward received by taking that action from $s_t$ at time
$t$
$s_{t+1}$ is the next state

In the on policy case, as I understand it, Q of the equation above is the same Q, which is the only approximator.
As I understand the algorithm, at time $t$ we save an experience

$(s_t, a_t, r_t, s_{t+1} )$.

Then, later, at time $t+x$, we attempt to learn from that experience.
However, at the time of saving the experience, $Q(s_t,a_t)$ was something different than at the time of attempting to learn from that experience, because the parameters $\theta$ of $Q$ have since changed. This could actually be written as

$Q_t(s_t, a_t) \neq Q_{t+x}(s_t,a_t)$

Because the Q value is different, I don't see how the reward signal at time $t$ is of any relevance for $Q_{t+x}(s_t,a_t)$ at $t+x$, the time of learning.
Also, it is likely that following a policy that is derived from $Q_t$ would lead to $a_{t}$, whereas following a policy that is derived from $Q_{t+x}$ would not.
I don't see in the experience replay algorithm that the Q value $Q_t(s_t, a_t)$ is saved, so I must assume that is not.
Why does calculating the Q value again at a later time make sense FOR THE SAME SAVED REWARD AND ACTION?

Because the Q value is different, I don't see how the reward signal at time $t$ is of any relevance for $Q_{t+x}(s_t,a_t)$ at $t+x$, the time of learning.

The $r_t$ value for any single step is not dependent on $Q$ or the current policy. It is purely dependent on $(s_t,a_t)$. That means you can use the Q update equation to use it to calculate new TD targets, by combining your knowledge of the old reward signal and the value functions of the latest policy.

The value $r_t + \gamma \max_{a_{t+1}} Q(s_{t+1}, a_{t+1}; \theta_i^-)$ is the TD target in the loss function you show. There are many possible variations to calculate the TD target value in RL, with different properties. The one you are using is biased towards initial random values unrelated to the problem, and also deliberately biased towards older Q values to prevent runaway feedback. It is also low variance compared to other possibilities, and simpler to calculate.

  Also, it is likely that following a policy which is derived from $Q_t$ would lead to $a_{t}$, whereas following a policy which is derived from $Q_{t+x}$ would not.

Yes that is correct. However, you don't care about that for a single step, you just care about calculating a better estimate for $Q(s,a)$ regardless of whether you would choose $a$ in state $s$ with the current policy. That is what an action value measures - the utility of taking action $a$ in state $s$ and thereafter following a given policy.

This is a strength of experience replay, that you are constantly refining your estimates of off-policy action values to determine which is the best.

This does become more of an issue when you want to use longer trajectories in the update step (which you may want to do to reduce bias of your TD target estimate). A series of steps in history $s_t,a_t,r_t ... s_{t+1}, a_{t+1},r_{t+1}...s_{t+n}$ may not have the same chance of occurring under the latest policy as it did when it was stored in memory. For the first step $s_t,a_t$ again you don't care if it is one you would currently take because the point is to refine your estimate of that action value. However, if you want to use $r_{t+1}, r_{t+2}$ etc plus $s_{t+n}$ to create a TD target, then you have to care whether your current policy and the one used to populate the history table would be different.

It is a problem if you want to use more sophisticated estimates of TD target that use multiple sample steps along with experience replay. There are some approaches you can take to allow for this, such as importance sampling. For a single step update mechanism you don't need to worry about it.

  I don't see in the experience replay algorithm that the Q value $Q_t(s_t, a_t)$ is saved, so I must assume that is is not.

This is correct. You must re-calculate the TD target from a more up-to-date policy to get better estimates of the action value. With experience replay, you are not interested in collecting a history of values of Q. Instead you are interested in the history of state transitions and rewards.

  Why does calculating the Q value again at a later time make sense FOR THE SAME SAVED REWARD AND ACTION?

Because it will change, due to the learning process summarising effects of state transitions.

As a toy example, consider a maze solver with traps (negative rewards) and treasures (positive rewards). At one point in history, the agent finds itself in a location and its policy told it to move into a trap on the next step. The agent would initially score location and steps leading up to it with negative Q values. Later it discovers through exploration that there is also some treasure if it takes a different turning towards the end of the the same series of steps. With experience replay, and re-calculating Q values each time, it can figure out which section of that path should be converted to high scores because they lead to treasure as well as the trap and now the agent has a better policy for the end of the path it has better estimates of value there.


Model-based RL for time series data I have time-series data. When I take an action, it impacts the next state, because my action directly determines the next state, but it is not known what the impact is.
To be concrete: I have $X(t)$ and $a(t-1)$, where $X(t)$ is n-dimensional time-series data and $a(t)$ is 1-dimensional time-series data. At time $t$, they together represent the observation/state space. Also, at time $t$, the agent makes a decision about $a(t)$. This decision (action) $a(t)$ directly defines the next state space $X(t+1)$ and rewards, by some function $f$ & $g$, $f(a(t), X(t)) = X(t+1)$ and $g(a(t), X(t)) = R(t+1)$.
I have to estimate this impact, i.e. where I will end up (what will be the next state). I decided to use a model-based RL algorithm, because, from my knowledge, model-based RL does exactly this.
Can you advise me on a good paper and Github code, to implement this project?
As I noticed, there do not exist many works on Model-based RL.

To my knowledge, there does not exist anything along the lines of model-based reinforcement learning with time-sensitive data. I think the best chance you have is to try to abstract the data that you have into a model which is not time-sensitive.
What would happen when you get past the timestamps of your original data? I am guessing that when testing this model, you will have states with time stamps past your original latest timestamp. Or are you only using your model in the time stamps of your training data? Is it going to be a useful model then?
Firstly, please note that the topics of this forum are mostly theoretical. This question leans on the boundary. If you frame your question a bit differently, ending your post with a clear question and also putting that question in the title, you will get more responses.
I feel like the question is 'What are the possibilities for model-based reinforcement learning for time-sensitive data?' But this question is inherently vague as it implies that you have a model according to the definitions of models in RL, which are not time sensitive. If you would like a better answer then please provide more information or ask your question on a more practical forum if it is more practical than what I guessed.
Disclaimer: would have just put some comments under the post as this is not a real sufficient answer, but my reputation is not high enough for that :P


How to properly use Flatten layer? Context
I'm trying to create net that will be able to recognize printed-like digits. Something like MNIST, but only for standard printing font.
Images are of the size 40x40 and I'd like to put them into feedforward net since ConvNet seems too powerful for this task.
Question
How should I use Flatten layer in this task?
Code
My current net:
X, test_X, y, test_y = train_test_split(X, y, test_size=0.25, random_state=42)

self.model = Sequential()
self.model.add(Flatten())
self.model.add(Dense(64, activation='relu', input_shape=X.shape[1:]))
self.model.add(Dense(no_classes, activation='softmax'))
self.model.compile(loss="categorical_crossentropy",
                   optimizer="rmsprop",
                   metrics=['accuracy'])

self.history = self.model.fit(X, y, batch_size=256, epochs=20, validation_data=(test_X, test_y))
print(self.model.summary())

Example images

Current results

The Flatten layer is used for collapsing an ND tensor into a 1D tensor. In your case, the inputs appear to be $28\times28$ images, so Flatten will convert that into a tensor with shape $1\times768$. Note that no information is lost. Flatten layers are usually used where you have a convolutional layer with dimensions $N\times M \times C$ (where $N$,$M$ are the feature map sizes and $C$ is the number of channels) and want to fully connect with a Dense layer or another layer that only accepts 1D inputs. Flatten can also be used when the network is meant to output a feature vector from a final convolutional layer for image classification purposes using a different technique.


How to classify this environment? Consider an environment, where an agent intends to move from cell "A" to cell "G", avoiding obstacles (cells marked with shading). The agent can move forward, rotate 90º to the left, or rotate 90º to the right, and can identify the type of cell in front of him. Here's a diagram.

Classify the characteristics of the environment, according to:

Accessible or non-accessible
Deterministic or non‐deterministic
Episodic or non‐episodic
Discrete or continuous
Static or dynamic

The environment is :

Deterministic : the future state of the environment (and the agent) is defined by the agent's action.
Partially Observable (partially accessible) : since his sensors don't see what's beyond the shaded barrier, the environment is partially observable (accessible).
Sequential (non-episodic): Since the agent's current action will constrain and affect the space of possibilities (options, choices) of future actions, current decisions are not independent of future ones.
Discrete : Environment is not continuous, that is, every action/step/case is finite (either turn left, right, forward or backward), you don't have other actions, which makes it a discrete task environment.
Static : the environment is not changing, it's static, only the agent is moving.


In the multi-head attention mechanism of the transformer, why do we need both $W_i^Q$ and ${W_i^K}^T$? In the Attention is all you need paper, on the 4th page, we have equation 1, which describes the self-attention mechanism of the transformer architecture
$$
\text { Attention }(Q, K, V)=\operatorname{softmax}\left(\frac{Q K^{T}}{\sqrt{d_{k}}}\right) V
$$
Everything is fine up to here.
Then they introduce the multi-head attention, which is described by the following equation.
$$
\begin{aligned}
\text { MultiHead }(Q, K, V) &=\text { Concat}\left(\text {head}_{1}, \ldots, \text {head}_{\mathrm{h}}\right) W^{O} \\
\text { where head}_{\mathrm{i}} &=\text {Attention}\left(Q W_{i}^{Q}, K W_{i}^{K}, V W_{i}^{V}\right)
\end{aligned}
$$
Once the multi-head attention is motivated at the end of page 4, they state that for a single head (the $i$th head), the query $Q$ and key $K$ inputs are first linearly projected by $W_i^Q$ and $W_i^K$, then dot product is calculated, let's say $Q_i^p =  Q W_i^Q$ and $K_i^p = K W_i^K$.
Therefore, the dot product of the projected query and key becomes the following from simple linear algebra.
$$Q_i^p {K_i^p}^\intercal = Q W_i^Q {W_i^K}^T K^T =  Q W_i K^T,$$
where
$$W_i = W_i^Q {W_i^K}^T$$
Here, $W$ is the outer product of query projection by the key projection matrix. However, it is a matrix with shape $d_{model} \times d_{model}$. Why did the authors not define only a $W_i$ instead of $W_i^Q$ and $W_i^K$ pair which have $2 \times d_{model} \times d_{k}$ elements? In deep learning applications, I think it would be very inefficient.
Is there something that I am missing, like these 2 matrices $W_i^Q$ and $W_i^K$ should be separate because of this and that?

I'll use notation from the paper you cited, and any other readers should refer to the paper (widely available) for definitions of notation.  The utility of using $W^Q$ and $W^K$, rather than $W$, lies in the fact that they allow us to add fewer parameters to our architecture.  $W$ has dimension $d_{model} \times d_{model}$, which means that we are adding $d_{model}^2$ parameters to our architecture.  $W^Q$ and $W^K$ each have dimension $d_{model} \times d_k$, and $d_k=\frac{d_{model}}{h}$. If we use these two matrices, we only add $2\frac{d_{model}^2}{h}$ parameters to our architecture, even though their multiplication (with the transpose) allows us to have the correct dimensions for matrix multiplication with $Q$ and $K$.
We do use $h$ attention heads, which then brings our number of parameters back up, but the multiple heads let the model attend to different pieces of information in our data.


How to make minimax optimal? By optimal I mean that:

If max has a winning strategy then minimax will return the strategy for max with the fewest number of moves to win.
If min has a winning strategy then minimax will return the strategy for max with the most number of moves to lose.
If neither has a winning strategy then minimax will return the strategy for max with the most number of moves to draw.

The idea is that you want to win in the fewest number of moves possible but if you can't win then you want to drag out the game for as long as possible so that the opponent has more chances of making mistakes.

So, how do you make minimax return the best strategy for max?

Minimax deals with two kinds of values:

Estimated values determined by a heuristic function.
Actual values determined by a terminal state.

Commonly, we use the following denotational semantics for values:

A range of values centered around 0 denote estimated values (e.g. -999 to 999).
A value less than the smallest heuristic value denotes a loss for max (e.g. -1000).
A value more than the biggest heuristic value denotes a win for max (e.g. 1000).
The value 0 denotes either an estimated draw or an actual draw.

The advantage of this denotational semantics is that comparing values is the same as comparing numbers (i.e. you don't need a special comparison function). We can extend this denotational semantics to incorporate optimality of winning and losing as follows:

A range of values centered around 0 denote estimated values (e.g. -999 to 999).
A range of values less than the smallest heuristic value denote loss (e.g. -2000 to -1000).
A range of values more than the biggest heuristic value denote win (e.g. 1000 to 2000).
The value 0 denotes either an estimated draw or an actual draw.
A loss in n moves is denoted as -(m - n) where m is a sufficiently large number (e.g. 2000).
A win in n moves is denoted as (m - n) where m is a sufficiently large number (e.g. 2000).

Using this denotational semantics for values requires only a small change to the minimax algorithm:

function minimax(node, depth, max)
    if max
        return negamax(node, depth, 1)
    else
        return -negamax(node, depth, -1)

function negamax(node, depth, color)
    if terminal(node)
        return -2000

    if depth = 0
        return color * heuristic(node)

    value = -2000

    foreach child of node
        v = -negamax(child, depth - 1, -color)

        if v > 1000
            v -= 1

        if v > value
            value = v

    return value

Incorporating optimality for draws is a lot more difficult.


Can AI be understood as a generalized statistics tool? I am a (soon-to-become, to be honest) theoretical physicist. I want to learn a bit about AI. So as you know in physics we develop theories based on as few and as simple basic equations as possible which shall explain as much of the experimental results and observations as possible. I feel that this is kind of not how AI solves problems.
My understanding is that AI can be understood as a very generalized and abstract statistics software package handling input data in a general way to find the "best fit" to some form of problem. Is that correct? I know it isn't. But is it vaguely correct?
I give you an example. In weather prediction there is a technique called MOS (model output statistics). It collects output from numerical weather prediction models (simulation software) as well as observational data and finds statistical relations between them to correct the model output for errors. For example, it might be that the intensity of precipitation in London is on average underestimated by the model by 10 %, so MOS will correct for that. Over time, it improves itself, because it collects more and more data. Is this already a form of AI?

My understanding is that AI can be understood as a very generalized and abstract statistics software package handling input data in a general way to find the "best fit" to some form of problem. Is that correct? I know it isn't. But is it vaguely correct?

No. It's not correct, in my opinion, not even vaguely and in many ways.

AI is not (necessarily) abstract (although there are examples of theoretical frameworks of AI, such as AIXI, which may be of interest to you, given that you are about to become a theoretical physicist)
AI does not necessarily generalize statistics or statistical concepts
AI is not just machine learning or, more precisely, supervised learning. You're very likely referring to supervised learning when you say "best fit", but there are other forms of learning (such as reinforcement learning) and there are other aspects of AI apart from learning, such as perception, control, etc. Some people sometimes claim that machine learning is glorified statistics, but, although the two are similar and related, I don't think that's exactly correct.

To know what AI is, you should read the book Artificial Intelligence: A Modern Approach. If you want to know what machine learning is, then there are many books that you can read, such as Machine Learning (1997) by Tom M. Mitchell. If you are interested in the relationship between machine learning and statistics, you may be interested in this post. You should also read this answer, which describes what AI is or may refer to. This answer gives a nice brief description of the difference between AI and ML.


Does overfitting imply an upper bound on model size/complexity? Suppose that I have a model M that overfits a large dataset S such that the test error is 30%. Does that mean that there will always exist a model that is smaller and less complex than M that will have a test error less than 30% on S (and does not overfit S).

over-fitting does seem to imply an upper bound on model complexity.

As complexity of the model increases, its generality tends to decrease.  This is not an indisputable fact, but an identifiable trend, provided that the model is not inundated with redundancy.

For polynomial expressions, a Taylor series of 100 terms can always perfectly represent the position of 100 points in a time series, although no predictive general information can be ascertained from the 100 coefficients of the Taylor series.  This is also true for spectral analysis, Lyapunov exponent estimation, spline fitting, or artificial network convergence.

What is generally accepted as the definition of over-fitting does not come from the AI field.  It originates from the mathematics of surface approximation using closed forms.  The closed forms may be derived from a single differential equation or systems of them, but not usually, since closed forms do not exist for many such systems.

The information science principles behind feature extraction are closely aligned to the correlation between generality and predictive usefulness.

Still, we can't conclude, "There will always exist a model that is smaller and less complex than $M$ that will have a test error less than 30% on $S$."  Counter examples can probably be constructed with a little thought and effort.


What happens when the output length in the brevity penalty is zero? The brevity penalty is defined as

$$bp = e^{(1- r/c)},$$

where $r$ is the reference length and $c$ is the output length.

But what happens if the output length gets zero? Is there any standard way of coping with that issue?

Division by zero is not mathematically defined.

A usual or standard way of dealing with this issue is to raise an exception. For example, in Python, the exception ZeroDivisionError is raised at runtime if you happen to divide by zero.

If you execute the following program

zero = 0
numerator = 10
numerator / zero

You will get

Traceback (most recent call last):
  File "main.py", line 3, in <module>
    numerator / zero
ZeroDivisionError: division by zero

However, if you want to avoid this runtime exception, you can check for division by zero and deal with this issue in a way that is appropriate for your program (without needing to terminate it).

In the paper BLEU: a Method for Automatic Evaluation of Machine Translation that introduced the BLEU (and brevity penalty) metric, the authors defined the brevity penalty as

\begin{align}
BP =
\begin{cases}
1, & \text{if } c > r\\
e^{(1- r/c)} & \text{if } c \leq r\\
\end{cases} \label{1} \tag{1}
\end{align}

This definition does not explicitly take into account the division by zero.

The Python package nltk does not raise an exception, but it (apparently, arbitrarily) returns zero when c == 0. Note that the BLEU metric ranges from 0 to 1. For example, if you execute the following program

from nltk.translate.bleu_score import brevity_penalty, closest_ref_length

reference1 = list("hello") # A human reference translation.
references = [reference1] # You could have more than one human reference translation.

# references = [] Without a reference, you will get a ValueError.

candidate = list() # The machine translation.
c = len(candidate)

r =  closest_ref_length(references, c)
print("brevity_penalty =", brevity_penalty(r, c))

You will get

brevity_penalty = 0

In the example above, the only human reference (translation) is reference1 = list("hello") and the only candidate (the machine translation) is an empty list. However, if references = [] (you have no references), then you will get the error ValueError: min() arg is an empty sequence, where references are used to look for the closest reference (the closest human translation) to the  candidate (the machine translation), given that there could be more than one human reference translation, and one needs to be chosen to compute the brevity penalty, with respect to your given candidate.

In fact, in the documentation of the brevity_penalty function, the following comment is written

# If hypothesis is empty, brevity penalty = 0 should result in BLEU = 0.0.

where hypothesis is a synonym for candidate (the machine translation) and the length of the candidate is $c$ in the formula \ref{1} (and c in the example above).

To answer your second question more directly, I don't think there's a standard way of dealing with the issue, but I've not fully read the BLEU paper yet.


Why am I getting a difference between training accuracy and accuracy calculated with Keras' predict_classes on a subset of the training data? I'm trying to solve a binary classification problem with AlexNet. I split the original dataset into training and validation datasets using a 70/30 ratio. I have trained my neural network with a dataset of 11200 images, and I obtained a training accuracy of 99% and a validation accuracy was 96%. At the end of the training, I saved my model's weights to a file.
After training, I loaded the saved weights to the same neural network. I chose 738 images out of the 11200 training images, and I tried to predict the class of each of them with my model, and compare them with true labels, then again I calculated the accuracy percentage and it was 74%.
What is the problem here? I guess its accuracy should be about 96% again.
Here's the code that I'm using.
prelist=[]
for i in range(len(x)):
    prediction = model.predict_classes(x[i])
    prelist.append(prediction)
count = 0
for i in range(len(x)):
    if(y[i] == prelist[i]):
        count = count + 1
test_precision = (count/len(x))*100
print (test_precision)

When I use predict_classes on 11200 images that I used to train the neural network and compare its result with true labels and calculated accuracy again its accuracy is 91%.

One problem could be with the selection of the validation set. For your model to work well on data it has not seen as training data is to have a high validation accuracy, but that is not sufficient on its own. The validation set must be large enough and varied enough that its probability distribution is an accurate representation of the probability distribution of all the images. You could have 1000 validation images, but, if they are similar to each other, they would be an inadequate representation of the probability distribution. Therefore, when you run your trained model to make predictions on the test set its performance would be poor.
So the question is: how many validation images did you use and how were they selected (randomly or handpicked)?
Try increasing the number of validation images and use one of the available methods to randomly select images from the training set, remove them from the training set, and use them as validation images.
Keras's flow_from_directory can achieve that or sklearn's train_test_split. I usually have the validation set be selected randomly and have at least 10% as many images as the test set does.
Overtraining is a possibility, but I think unlikely given your validation accuracy is high.
Another thing is how were the test set images selected? Maybe their distribution is skewed. Again, the best thing to do is to select these randomly.
What was your training accuracy? Without a high training accuracy, the validation accuracy may be a meaningless value. Training accuracy should be in the upper 90's for the validation accuracy to be really meaningful.
Finally, is there any possibility your test images were mislabeled? Try switching your test set as the validation set and see what validation accuracy you get.
Here is an example of what I mean. A guy built a CNN to operate on a set of images separated into two classes. One class as "dogs", the other class was "wolves". He trained the network with great results almost 99.99% training accuracy and 99.6% validation accuracy. When he ran it on the test set, his accuracy was about 50%. Why? Well, it turns out all the images of wolves were taken with snow in the background. None of the images of dogs had snow in the background. So, the neural network figures out if snow must be a wolf, if no snow must be a dog. However, in his test set, he had a mixture of wolves in or not in snow, dogs in or not in snow. Great training and validation results but totally useless performance.


Should I use C# or Python for AI? I've been seeing a lot of tutorials on the internet about AI that are mostly done with Python. Apart from these, I've seen C# being used in AI topics, but in things like self-driving cars.

I already know C# and I wanted to become more professional in it. However, now that I see that Python is being used a lot, so I'm getting intrigued by it.

Do you recommend Python (or other languages) or should I keep up with C#?

Just to mention, I'm 14 years old and I have enough time to learn more and it doesn't really matter what I love to do, because, I love coding and AI especially, so, it doesn't really matter.

If you recommend Python, please, tell me which compiler I should use. I don't really know if it has a compiler, but I want to know where I should start.

If you're doing deep learning (which I assume you are, if you say you want to learn "AI"), then Python is a MUST. Virtually all the big frameworks are Python wrappers over a C++ core.

C# has no real deep learning frameworks. There are a couple such as the Microsoft Cognitive Toolkit, but they are on a completely different level from PyTorch or Tensorflow. No serious ML practitioner would do the majority of their research in a framework like that.

For more information, see: Why is Python the most popular language in the AI field?


How to refine K-means clustering on a data set? I'm working with a data set where the data is stored in a string such as AxByCyA where A, B and C are actions and v,w,x,y,z are times between the actions (each letter represents an interval of time). It's worth noting that B cannot occur without A, and C cannot occur without B, and C is the action I'm attempting to study (ie: I'd like to be able to predict whether a user will do C based on their prior actions).

I intend to create 2 clusters: people who do C and those who don't.

From this data set I build a training array to run the sci-kit (python) k-means algorithm on, containing the number of As, the number of Bs, the mean time between actions (calculated using the average of each interval) and the standard deviation between each interval.

This gives me an overall success rate of 82% on the test set, but is there anything I can do for more accuracy?

The usual parameters to adjust in a k-means:

Number of clusters (recall many clusters can have same label).
Distance definition (euclidean is the most basic, Gauss is an
improvement)
Selection of initial cluster positions.
Data preprocessing (data normalization, ...)


Maximum number of neurons in a layer given number of neurons in previous layer Consider an extremely complicated feed-forward neural network training example but with no need of computational efficiency or limiting of processing time.

What is the maximum number of hidden neurons h that a hidden layer should possess to detect all unique features/ correlations between input data from the previous layer which has n nodes?

In other words if we wanted to create a neural network with a large number of neurons in a hidden layer, what is the maximum neuron count possible that helps the network train (give n neurons are in the previous layer)?

The Universal Approximation Theorem states: In the mathematical theory of artificial neural networks, the universal
  approximation theorem states that a feed-forward network with a single
  hidden layer containing a finite number of neurons can approximate
  continuous functions on compact subsets of Rn, under mild assumptions
  on the activation function. The theorem thus states that simple neural
  networks can represent a wide variety of interesting functions when
  given appropriate parameters; however, it does not touch upon the
  algorithmic learnability of those parameters.

So clearly if you do not have infinite number of hidden neurons you cannot approximate a function with $\epsilon$ error tending to 0. So if we assume that the previous layer gives some sort of representation of the function to be approximated you still need infinite hidden neurons to approximate this representative function.

But probably it'll be more clear to you if we go into basic physical laws of mathematical approximation.

  According to the Fourier Theorem by Joseph Fourier: A Fourier series is a way to
  represent a function as the sum of simple sine waves. More formally,
  it decomposes any periodic function or periodic signal into the
  weighted sum of a (possibly infinite) set of simple oscillating
  functions, namely sines and cosines (or, equivalently, complex
  exponentials).

So theoretically, if your function is periodic it maybe perfectly approximated by an activation function like $sin$ or $cos$. The simple reason you cannot use an activation like $ReLu$ or $Sigmoid$ is because they are non-periodic and as per another related theorem called Fourier Transform you would require infinite number of sine waves to approximate non-periodic curves so the problem collapses in itself.

Since there are various ways to train a Neural Network other than Gradient Descent theoretically speaking you just might approximate a periodic function with some other methods (if activation is sine or cos), it is almost imposiible via methods like Gradient Descent.

So in short the answer to your question will be $\infty$ for the aforementioned reasons.


What is the value of a state when there is a certain probability that agent will die after each step? We assume infinite horizon and discount factor $\gamma = 1$. At each step, after the agent takes an action and gets its reward, there is a probability $\alpha = 0.2$, that agent will die. The assumed maze looks like this

Possible actions are go left, right, up, down or stay in a square. The reward has a value 1 for any action done in the square (1,1) and zero for actions done in all the other squares.

With this in mind, what is the value of a square (1,1)?

The correct answer is supposed to be 5, and is calculated as $1/(1\cdot 0.2) = 5$. But why is that? I didn't manage to find any explanation on the net, so I am asking here.

The value of a state depends on the policy that you use, so I'll make the assumption here that you're talking about value using the optimal policy.

According to the optimal policy, the agent would choose to stay in the square (1,1) every time, but since it has a 0.8 probability of actually staying (and 0.2 probability of dying), we can compute the value of the agent using the Bellman equation as:

$$
V(1,1) = 1 + 0.8 V(1,1) + 0.2 V(\text{death state}) \\
\implies V(1,1) = 1 + 0.8 V(1,1) \\
\implies V(1,1) = \frac{1}{1 - 0.8} \\
\implies V(1,1) = 5
$$

There are other ways of deriving the same number (value function has multiple definitions) but they are equivalent.


It is possible to solve a problem with continuous action spaces and no states with reinforcement learning? I want to use Reinforcement Learning to optimize the distribution of energy for a peak shaving problem given by a thermodynamical simulation. However, I am not sure how to proceed as the action space is the only thing that really matters, in this sense:

The action space is a $288 \times 66$  matrix of real numbers between $0$ and $1$. The output of the simulation and therefore my reward depend solely on the distribution of this matrix.

The state space is therefore absent, as the only thing that matters is the matrix on which I have total control. At this stage of the simulation, no other variables are taken into consideration.

I am not sure if this problem falls into the tabular RL or it requires approximation. In this case, I was thinking about using a policy gradient algorithm for figuring out the best distribution of the $288 \times 66$ matrix. However, I do not know how to behave with the "absence" of the state space. Instead of a tuple $\langle s,a,r,s' \rangle$, I would just have $\langle a, r \rangle$, is this even an RL-approachable problem? If not, how can I reshape it to make it solvable with RL techniques?

A stateless RL problem can be reduced to a Multiarmed Bandit (MAB) problem. In such a scenario, taking an action will not change the state of the agent.

So, this is the setting of a conventional MAB problem: at each time step, the agent selects an action to either perform an exploration or exploitation move. It then records the reward of the taken action and updates its estimation/expectation of the usefulness of the action. Then, repeats the procedure (selection, observing, updating).

To chose between exploration and exploitation moves, MAB agents adopt a strategy. The simplest one would probably be $\epsilon$-greedy which agent chooses the most rewarding actions most of the time (1-$\epsilon$ probability) or randomly selects an action ($\epsilon$ probability).


How to express accuracy of a regression ANN that uses MSE loss function? I have a regression MLP network with all input values between 0 and 1, and am using MSE for the loss function. The minimum MSE over the validation sample set comes to 0.019. So how to express the 'accuracy' of this network in 'lay' terms? If RMSE is 'in the units of the quantity being estimated', does this mean we can say: "The network is on average (1-SQRT(0.019))*100 =  86.2% accurate"?

Also, in the validation data set, there are three 'extreme' expected values. The lowest MSE results in predicted values closer to these three values, but not as close to all the other values, whereas a slightly higher MSE results in the opposite - predicted values further from the 'extreme' values but more accurate relative to all other expected values (and this outcome is actually preferred in the case I'm dealing with). I assume this can be explained by RMSE's sensitivity to outliers?

You can not use error to reliably measure accuracy. Error is best used as a measure of how fast the model is currently learning.

As an example, using different loss functions (cross entorpy vs MSE) results in massively different values for the error at similar accuracy.

Also considering this, an error of 0.0000000001 quite often has lower validation set accuracy then and error of 0.1, as the prior is likely over trained.

As for you second question, yes this is because MSE has a huge bias towards outliers. I have personally found regression networks to struggle in most circumstances, so if it is at all possible to turn the network into a classifier, you may see an improvement.


Does Google's deep dream project have a specific website for playing with it? Does Google's deep dream project have a specific website so that it can be used to run edits and renderings on images and provide an output?

Here are a few websites that help run the deep dream generator:

1) http://deepdream.psychic-vr-lab.com/deepdream/

2) https://dreamscopeapp.com/deep-dream-generator

This blog by Google AI explains the concept and here is the GitHub repo for the same. It has a python notebook for reproducing the results.


What is "planning" in the context of reinforcement learning, and how is it different from RL and SL? This is an excerpt taken from Sutton and Barto (pg. 3):

Another key feature of reinforcement learning is that it explicitly considers the whole problem of a goal-directed agent interacting with an uncertain environment. This is in contrast with many approaches that address subproblems without addressing how they might fit into a larger picture. For example, we have mentioned that much of machine learning research is concerned with supervised learning without explicitly specifying how such an ability would finally be useful. Other researchers have developed theories of planning with general goals, but without considering planning's role in real-time decision-making, or the question of where the predictive models necessary for planning would come from. Although these approaches have yielded many useful results, their focus on
isolated subproblems is a significant limitation.

I have an idea of supervised learning (SL), but what exactly does the author mean by planning? And how is the RL approach different from planning and SL?
(Illustration with an example would be nice).

The concept of "planning" is not just related to RL. In general (as the name suggests), planning consists in creating a "plan" which you will use to reach a "goal". The goal depends on the context or problem. For example, in robotics, you can use a "planning algorithm" (e.g. Dijkstra's algorithm) in order to find the path between two points on a map (given e.g. the map as a graph).
In RL, planning usually refers to the use of a model of the environment in order to find a policy that hopefully will help the agent to behave optimally (that is, obtain the highest amount of return or "future cumulative discounted reward"). In RL, the problem (or environment) is usually represented as a Markov Decision Process (MDP). The "model" of the environment (or MDP) refers to the transition probability distribution (and reward function) associated with the MDP. If the transition model (and reward function) is known, you can use an algorithm that exploits it to (directly or indirectly) find a policy. This is the usual meaning of planning in RL. A common planning algorithm in RL is e.g. value iteration (which is a dynamic programming algorithm).

Other researchers have developed theories of planning with general goals, but without considering planning's role in real-time decision- making, or the question of where the predictive models necessary for planning would come from.

Planing is often performed "offline", that is, you "plan" before executing. While you're executing the "plan", you often do not change it. However, often this is not desirable, given that you might need to change the plan because the environment might also have changed. Furthermore, the authors also point out that planning algorithms often have a few limitations: in the case of RL, a "model" of the environment is required to plan.

For example, we have mentioned that much of machine learning research is concerned with supervised learning without explicitly specifying how such an ability would finally be useful.

I think the authors simply want to say that supervised learning is usually used to solve specific problems. The solutions to supervised problems often are not directly applicable to other problems, so this makes them limited.

Another key feature of reinforcement learning is that it explicitly considers the whole problem of a goal-directed agent interacting with an uncertain environment.

In RL, there is the explicit notion of a "goal": there is an agent that interacts with an environment in order to achieve its goal. The goal is often to maximize the "return" (or "future cumulative discounted reward", or, simply, the reward in the long run).

How is RL different from planning and supervised learning?

RL and planning (in RL) are quite related. In RL, the problem is similar to the one in planning (in RL). However, in RL, the transition model and reward function of the MDP (which represents the environment) are usually unknown. Therefore, the only way of finding or estimating an optimal policy that will allow the agent to (near-optimally) behave in this environment is to interact with the environment and gather some info regarding its "dynamics".
RL and supervised learning (SL) are quite different. In SL, there isn't usually the explicit concept of "agent" or "environment" (and their interaction), even though it might be possible to describe supervised learning in that way (see this question). In supervised learning, during the training or learning phase, a set of inputs and the associated expected outputs is often provided. Then the "objective" is to find a map between inputs and outputs, which generalizes to inputs (and corresponding outputs) that have not been observed during the learning phase. In RL, there isn't such a set of inputs and associated expected outputs. In RL, there is just a scalar signal emitted by the environment, at each time step, which roughly indicates how well the agent is currently performing. However, the goal of the agent is not just to obtain rewards, but to behave optimally (in the long run).
In short, in RL, there is the explicit notion of agent, environment and goal, and the reward is the only signal which tells the agent how well it is performing, but the reward does not tell the agent which actions it should take at each time step. In supervised learning, the objective is to find a function that maps inputs to the corresponding outputs, and this function is learned by providing explicit examples of such mappings during the training phase.
There are some RL algorithms (like the temporal-difference ones), which could roughly be thought of as self-supervised learning algorithms, where the agent learns from itself (or from the experience it has gained by interacting with the environment). However, even in these cases, the actions that the agent needs to take are not explicitly taught.


What is non-Euclidean data? What is non-Euclidean data?
Here are some sub-questions

Where does this type of data arise? I have come across this term in the context of geometric deep learning and graph neural networks.

Apparently, graphs and manifolds are non-Euclidean data. Why exactly is that the case?

What is the difference between non-Euclidean and Euclidean data?

How would a dataset of non-Euclidean data look like?

Non-Euclidian geometry can be generally boiled down to the phrase

the shortest path between 2 points isn't necessarily a straight line.

Or, put in a way that lends itself very much to machine learning,

things that are similar to each other are not necessarily close if one uses Euclidean distance as a metric (aka the triangle inequality doesn't hold).

You mention graphs and manifolds as being non-Euclidian, but, really, the majority of problems being worked on don't have Euclidian data. Take the below images for example:
Clearly, 2 of the images are more similar to each other than the third one is, but if we looked at the pixels alone, the Euclidean distance between the pixel values don't represent this similarity.

If there was a function, $F(\text{image})$, that mapped images to a space of values where similar images produced values that were closer together, we could better understand the data, infer some statistics about the distributions, and make predictions on data we have yet to see. This is what classic techniques of image recognition have done and it's also what modern machine learning is doing. Taking data and mapping it to a space such that the triangle inequality holds.
Let's look at a more concrete example, some points I drew in MSPaint.
On the left is some space that we are interested in where points have 2 classes (red or blue). Even though there are points that are close to each other, they may have different colors/classes. Ideally, we could have a function that converts these points to some space where we can draw a line to separate these 2 classes. In general, there would be many lines, or hyper-planes in dimensions > 3, but the goal is to transform the data so that it will be "linearly separable".

To conclude, non-Euclidian data is everywhere.


Interpolating image to increase resolution before feeding it to a neural network Interpolation is a common way to make an image fit the right input shape for a neural network.

But is there any point in using interpolation to make it easier for the network to learn?

I assume interpolation adds no extra information to the input; It only uses existing information to increase the resolution and fill missing values.

However, sometimes I have observed that while I can not see anything with my human eye, using some kind of advanced interpolation technique such as b-spline interpolation makes it crystal clear that the object i am looking for is in the image, especially in the domain of infrared images.

So, is there any benefit for using interpolation rather than feeding a low dimensional image to a neural network?

One of the used is to use a neural interpolation, this is using a pretrained model to zoom our images, in some sense training with this kind of images is like combining this pretrainined model with our new data, and can be seen as transfer learning technique


RL agent's view of state transitions The above environment is DeepTraffic

Now consider this situation in the above environment, the Red car (we control it with our RL agent) is on the extreme right lane.

During the exploration phase, we take a 'move right' action, which ofcourse will result in the car not moving right,but the other cars will be moving, state changes due to the rules of the environment.

I'm using CNN to solve this, the state representation is the image itself and its a Q-Learning algorithm as described in DQN paper from deepmind.

In the above situation I mentioned, wont the agent think due to 'move right' action the state has changed, which is not really the case?

and when remembering the state transition (s,a,r,s') should i remember the actual action 'move right'(invalid) or 'do nothing'(correct as per env) ?

In the above situation I mentioned, wont the agent think due to 'move right' action the state has changed, which is not really the case?

Generally the agent does not need to "think" what the next state will be. After taking an action, it should observe the reward and the next state.

The logic for the next state is controlled by the environment. In your case, the environment of the simulator should accept the action choice and then not allow the sideways movement off the road, and present the correct logical next state. It may in addition alter the reward signal if you want to penalise this choice (in comments you say this is not done - that's fine, it's a choice you make on problem set up, what behaviour to reward or penalise).

A more advanced agent might also try to predict what the next state will be, especially if it was using a planning algorithm (e.g. Dyna-Q). Even then there is no reason or rule that it should have to predict an impossible next state - a well-trained agent should in fact predict correctly that moving right is same as "do nothing" when the car is in far right-hand lane. For a value-based approach, like Q-learning the agent may do this simply by scoring the two actions with the same value.

In your case, you do not need to try and second-guess what the agent will predict. Provided your state information is enough for the agent to observe that it is in the far left or far right lane, it should [eventually, after training] correctly predict the value functions and/or optimal actions as it learns the environment. That includes, after a few examples, that it will predict the outcome when moving right when already on right hand side. For that to happen reliably, you do need to check your state representation is adequate, and function approximation hyper-parameters are suited to the problem (the latter part could take some experimentation)

If the state data that the car receives does not contain enough information for the agent to tell that it is in extreme left or right lane, then you will have a problem. This is entirely possible in general, although from the image you show, that does not seem to be an issue.

One possible related issue is if the other cars in the scene all have different velocities. This velocity information is not shown in the state, and could cause your agent problems as it cannot tell the difference between a stationary car in front of it, and one which better matches its own velocity. You could treat this missing data as a partially observable state, and adjust you agent. Or you might be able to do the same as the Deep Mind DQN team for Atari games and use a sequence of e.g. last 4 images as the state, which should then include enough velocity data to make reliable estimates of state/action values.


What is the difference between artificial intelligence and machine learning? These two terms seem to be related, especially in their application in computer science and software engineering.  Is one a subset of another?  Is one a tool used to build a system for the other?  What are their differences and why are they significant?

Machine learning has been defined by many people in multiple (often similar) ways [1, 2]. One definition says that machine learning (ML) is the field of study that gives computers the ability to learn without being explicitly programmed.
Given the above definition, we might say that machine learning is geared towards problems for which we have (lots of) data (experience), from which a program can learn and can get better at a task.
Artificial intelligence has many more aspects, where machines may not get better at tasks by learning from data, but may exhibit intelligence through rules (e.g. expert systems like Mycin), logic or algorithms, e.g. path-finding).
The book Artificial Intelligence: A Modern Approach shows more research fields of AI, like Constraint Satisfaction Problems, Probabilistic Reasoning or Philosophical Foundations.


How do I determine the genomes to use for crossover in NEAT? If I have the fitness of each genome, how do I determine which genome will crossover with which, and so on, so that I get a new population?

Unfortunately, I can't find anything about it in the original paper, so I ask here?

The good thing about genetic algorithms is that they are exchangeable.
If you have the fitness of each individual, any algorithm (i.e. roulette, rank, tournament) will do.