Judea Pearl's 2018 comment on ACM.org, in his To, Build Truly Intelligent Machines, Teach Them Cause and Effect is piercing truth.

All the impressive achievements of deep learning amount to just curve fitting.

It may be less sensational and more technically correct to state that it is not, "Just curve fitting," but rather, "sophisticated surface fitting." Nonetheless, his general assessment indicates the need to look beyond tuning nonlinear functions to fit a surface in $\mathbb{R}^n$ and consider whether cognition is achievable with a deep network. The split in answers to this question is odd. We have two conflicting assertions, often strongly stated.

Artificial networks cannot perform logic.
Artificial networks are the best approach to AI.

How can rationality be excluded from the list of important human features of intelligence, which is what these two assertions are taken together would mean?
Is the human brain a network of sophisticated curve fitters?  Marvin Minsky's famous quote, "The brain happens to be a meat machine," was offered without proof, and neither a proof of his trivialization of the human brain nor a proof that the brain is beyond the reach of Turing computability has been offered since.
When you read these words, are your neural networks doing the following sequence of curve fits?

Edges from retinal rods and cones
Lines from edges
Shapes from lines
Letters from shapes
Linguistic elements from groups of letters
Linguistic structures from elements
Understanding from linguistic structures

The case is strong for the affirmation that the first five is a convergence mechanism on a model, and all the machine learning structure is just a method to fit the data to the model.
Those last two bullet items are where the paradigm breaks down and where many AI researchers and authors have correctly stated that machine learning has significant limitations when based solely on layers of multi-layer perceptrons and convolution kernels.  Furthermore, the last bullet item is grossly oversimplified in its current state, probably by orders of magnitude.  Even if Minsky is correct that a computer can perform what the brain does, the process of reading and understanding this paragraph could easily have a thousand different kinds of unique process components in patterns of internal workflow with massive parallelism.  Imaging technology indicates this probability.  We have computers modelling only the simplest peripheral layers.

Is there any scientific/mathematical argument that prevents deep learning from ever producing strong AI? — No. But there is no such argument that guarantees it either.

Other questions here investigate whether these sophisticated curve fitters can perform elements of cognition or reasoning.

Could a neural network detect primes?
Can neural networks be used to prove conjectures?

The totem of three in the question's image, seeing, doing, and imagining, is not particularly complete, accurate, or insightful.

There are at least five sensory paradigms in humans, not one
Doing preceded human senses by billions of years — bacteria do
Imagining is not a significantly higher process than scenario replay from models of past experience with some method to apply set functions to combine them and inject random mutations
Creativity may just be imagining in the previous bullet item followed by weeding out useless imagination results with some market-oriented quality criteria, leaving the impressive creative products that sell

The higher forms are appreciation, a sense of realities beyond the scope of scientific measurement, legitimate doubt, love, sacrifice for the good of others or humanity.
Many recognize that the current state of AI technology is nowhere near the procurement of a system that can reliably answer, "How can I make Y happen?" or "If I have acted differently, will X still occur?"
There is no mathematical proof that some combination of small curve fitting elements can or cannot achieve the ability to answer those questions as well a typical human being can, mostly because there is insufficient understanding of what intelligence is or how to define it in mathematical terms.
It is also possible that human intelligence doesn't exist at all, that references to it are based on a religious belief that we are higher as a species than other species.  That we can populate, consume, and exterminate is not actually a very intelligent conception of intelligence.
The claim that human intelligence is an adaptation that differentiates us from other mammals conflicts with whether we adapt well.  We have not been tested.  Come the next meteoric global killer with a shock wave of the magnitude of that of the Chicxulub crater's meteor, followed by a few and a thousand years of solar winter and we'll see whether it is our 160,000-year existence or bacteria's 4,000,000,000 year existence that proves more sustainable.  In the timeline of life, human intelligence has yet to prove itself significant as an adaptive trait.
What is clear about AI development is that other kinds of systems are playing a role along with deep learners based on the multi-layer perceptron concept and convolution kernels which are strictly surface fitters.
Q-learning components, attention-based components, and long-short term memory components are all strictly a surface fitter too, but only by stretching the definition of surface fitting considerably.  They have real-time adaptive properties and state, so they can be Turing complete.
Fuzzy logic containers, rules-based systems, algorithms with Markovian properties, and many other component types also play their role and are not surface fitters at all.
In summary, there are points made that have a basis in more than plausibility or a pleasing intuitive quality, however, many of these authors do not provide a mathematical framework with definitions, applications, lemmas, theorems, proofs, or even thought experiments that can be scrutinized in a formal way.


Can the English language ever be generalized using a set of grammar rules?

Can there ever be a functionally complete set of grammar rules which can parse any statement in English (locale-specific) accurately and which can be possibly implemented for use in AI-based projects?

Parse it yes, accurately most likely no.

Why ?

According to my understanding on how we derive meaning from sounds, there are 2 complementary strategies:

Grammar Rules:
A rule based system for ordering words to facilitate communication, here meaning is derived from interaction of discrete sounds and their independent meaning, so you could parse a sentence based on a rule book.

E.G. "This was a triumph" : the parser would extract a pronoun (This) with corresponding meaning ( a specific person or thing ) ; a verb (was) with corresponding meaning ( occurred ); ( a) and here we start with some parsing problems , what would the parser extract, a noun or an indefinite article ? An so we consult the grammar rule book, and settle for the meaning ( indefinite article any one of ), you have to parse the next word  and refer to it though, but let's gloss over that for now, and finally (triumph) a noun ( it could also be a verb, but thanks to the grammar rule book we settled for a noun with meaning: ( victory,conquest), so in the end we have ( joining the meanings ):

A specific thing occurred of victory. Close enough and I am glossing over a few other rules, but that's not the point, the other strategy is:

A lexical dictionary (or lexicon)
Where words or sounds are associated with specific meaning. Here meaning is derived from one or more words or sounds as a unit. This introduces the problem to a parser, since well, it shouldn't parse anything.

E.G. "Non Plus Ultra" And so the AI parser would recognize that this phrase is not to be parsed and instead matched with meaning :

The highest point or culmination

Lexical units introduce another issue in that they themselves could be part of the first example, and so you end up with recursion.

  if it is possible for a computer to parse a well-versed sentence written in English as if it were parsed by an adult English-speaking human?

I believe it could be possible, most examples I've seen deal effectively with the grammar rule book or the lexicon part, but I am not aware of a combination of both, but in terms of programming, it could happen.

Unfortunately even if you solve this problem, your AI would not really understand things in the strict sense, but rather present you with very elaborate synonyms, additionally context (as mentioned in the comments) plays a role into the grammar and lexicon strategies.

  If it cannot be represented using simple grammar rules, what kind of semantic structure can be used to generalize it?

A mixed one where there are both grammar rules and a lexicon and both can change and be influenced based on the AI specific context and experience as well as a system for dealing with these objects could be one way.


Understanding a few terms in Andrew Ng's definition of the cost function for linear regression

Linear regression is always associated with an activation function, the weights between layers and the structure of the network. The weights between layers are $\theta_0$ and $\theta_1$. These weights and the input features undergo the dot product operation, which is then the input to the activation function of the next layer's nodes.

An apparently different but the same use of $\theta_0$ and $\theta_1$ is as coefficients to one or more number of terms which themselves are a combination of the input vectors.

Broadly, $\theta_i$ denotes a weight, i.e. how much preference you want to give to a feature.


Is there any research on neural networks with multiple outputs for hierarchical label classification?

Sounds like a very interesting idea! I dont know existing work on the idea, but the implementation should be pretty simple with separate training with tied weights. It should be noted however that such behaviour occurs naturally in CNN's already. (See: http://www.cs.toronto.edu/~guerzhoy/321/lec/W07/HowConvNetsSee.pdf)


Nim was actually one of the first games ever played by an electronic machine. It was called the Nimatron and was displayed at the 1940 New York World's Fair.
It is also well known that neural networks can model the Xor-function, if they have enough layers. Despite that, Marvin Minsky is supposed to have killed neural networks in the sixties, by asserting that networks with a single hidden layer, cannot model XOR.
I think there were also some large scale projects to classify finite groups using computers.
Additionally, there have long been automated theorem-proving programs, that had some success in mathematical logic. I recently saw a paper that used deep learning to improve one of these theorem provers.
That being said, doing real mathematics is probably as difficult as real language understanding. There doesn't seem to have been a real breakthrough yet.


Use Machine/Deep Learning to Guess a String

As Andreas has commented this is a problem of statistical language model (a probability distribution over a sequence of words). The important thing you need is a hash table mapping fixed-length to the expected ending chains of words in your dictionary.
Things that can make your prediction better:

Add better and more words to your dictionary.
Use text expansion.

What you are looking for will require a pinch of Reinforcement Learning too. You need to figure out a way to penalize and award the predictions and then use the result in future. Your case also requires you to build your own corpus, which is the hardest part. If your corpus is good, it will give better results.
This is the research paper that will help you a lot.


Training a convolutional network to recognize object location

To use a convolutional net that isn't spatially invariant, you can make the convolution matrix of size equal to your input image size. Afterwards, just use any desired number of fully connected layers and your network should be able to learn your dataset.


Why can we approximate the joint probability distribution using the output vector of an LSTM?

In section 2.1 of the paper, the authors state that the goal of character-level language model is to estimate the following joint probability distribution

$$P(\boldsymbol{x}_{0:T}) = P(\boldsymbol{x}_{0}, \boldsymbol{x}_{1}, \dots, \boldsymbol{x}_{T}),$$

which is a joint probability distribution of all characters of a sequence of $T+1$ characters, where $\boldsymbol{x}_i$ is the $i$th character of the sequence. Ideally, the joint probability distribution, $P(\boldsymbol{x}_{0:T})$, should put more mass (or density) on the combination of $T-1$ characters that are more likely (in a given language). For example, in English, the combination of the characters "the" is more likely than the combination "bibliopole". Hence, $P(\text{t}, \text{h}, \text{e})$ should be higher than $P(\text{b}, \text{i}, \text{b}, \text{l}, \text{i}, \text{o}, \text{p}, \text{o}, \text{l}, \text{e})$, where, in this case, $T=2$. So, $P(\boldsymbol{x}_{0:T})$ is the actual character-level language model, which is represented by a joint probability distribution.

Similarly and intuitively, the conditional probability distribution $$P(\boldsymbol{x}_{t} \mid \boldsymbol{x}_{0:t-1})$$

tells us the probability of the next character of the sequence $\boldsymbol{x}_{t}$ given (that is, having observed) the previous characters of the sequence $\boldsymbol{x}_{0:t-1} = (\boldsymbol{x}_{0}, \dots, \boldsymbol{x}_{t-1})$. In general, the next character of a sequence $\boldsymbol{x}_{t}$ can depend on all previous characters of the same sequence, $\boldsymbol{x}_{0:t-1}$. If we are able to learn the conditional model $P(\boldsymbol{x}_{t} \mid \boldsymbol{x}_{0:t-1})$, given a sequence of $t$ characters, $\boldsymbol{x}_{0:t-1}$, we can sample the next character according to the same conditional probability distribution.

Recall that, given two events (or random variables) $A$ and $B$, the joint distribution of them is defined as $P(A, B) = P(A \mid B)P(B) = P(B \mid A)P(A)$, which gives rise to the Bayes' theorem. This can be easily generalised to multiple variables. More specifically, if you consider $B$ to a set of $N$ events (rather than just one), that is, $B=B_1 \cap B_2\cap \dots \cap B_N = B_1, B_2, \dots, B_N$, then $P(A, B) = P(A \mid B)P(B)$ still holds, but we can further decompose it

\begin{align}
P(A, B) = P(A, B_1, B_2, \dots, B_N)
&= P(A \mid B_1, B_2, \dots, B_N)P(B_1, B_2, \dots, B_N) \\
&= P(A \mid B_1, B_2, \dots, B_N)P(B_1 \mid B_2, \dots, B_N) P(B_2, \dots, B_N) \\
&= \cdots
\end{align}

This is called the chain rule (or product rule) of probability. Essentially, we apply the rule $P(A, B) = P(A \mid B)P(B)$ recursively.

Analogously, in the paper, the authors apply this chain rule to express the joint distribution $P(\boldsymbol{x}_{0:T})$ as a product of conditional probability distributions, that is

$$
P(\boldsymbol{x}_{0:T}) = \prod_{t=0}^T P(\boldsymbol{x}_{t}\mid \boldsymbol{x}_{0:t-1})
$$

In the case of the LSTM, the vector $\boldsymbol{h}_t$ is supposed to keep track of the past. More specifically, in the case of the character-level language model, we train an LSTM-based RNN, so that $\boldsymbol{h}_t$ is approximately equal to $\boldsymbol{x}_{0:t-1}$, that is, $\boldsymbol{h}_t \approx \boldsymbol{x}_{0:t-1}$. Hence, the joint probability distribution of the characters above can be now be approximately defined as a function of the vector $\boldsymbol{h}_t$

$$
P(\boldsymbol{x}_{0:T}) \approx \prod_{t=0}^T P(\boldsymbol{x}_{t}\mid \boldsymbol{h}_t; \boldsymbol{\theta})
$$

where $\boldsymbol{\theta}$ are the parameters of the LSTM-based RNN. Note that this is not an equality but an approximation. Intuitively, we train the LSTM so that it learns the interactions of the past characters.


How to detect when human voice / speech appears in an microphone stream?

Your problem is an old one. There are many methods, referred to as Voice Activity Detection (VAD) methods, which detect speech from an audio signal.

The typical design of a VAD algorithm follows one of more of these 3 approaches:

A noise reduction stage, e.g. via spectral subtraction.
Some features or quantities are calculated from a section of the input signal.
A classification rule is applied to classify the section as speech or non-speech – often this classification rule finds when a value exceeds a threshold.

There may be some feedback in this sequence, where parameters (like the noise threshold or the classification threshold) are tuned to improve the estimate or to adaptively vary the threshold(s). These feedback operations improve the VAD performance in non-stationary noise (i.e. when the noise varies a lot).

Check out this wiki page on Voice Activity Detection for more information.


Several questions regarding the NEAT algorithm

What is the definition of "structural innovation", and how do I store these so I can check if an innovation has already happened before?

Structural innovation is anything added that changes the topology of the network. So a structural innovation is any added connection or added node. I don't want to get too much into the implementation, but something similar to a dictionary global variable will work. When adding a connection (or node) between two nodes, we check if a connection (or node) has ever been placed between these two nodes before. If it has then we have stored an innovation number for what this connection (or node) is identical and we set its innovation number to that. We identify each node by its number.

  Is there a reason for storing the type of a node (input, hidden, output)?

Yes, there are many structural innovations that we do not want to happen. An innovation between two input node or an innovation between two output nodes are two examples of structural innovations we don't want.

  In the original paper, only connections have an innovation number, but in other sources, nodes do as well. Is this necessary for crossover? (This has already been asked here.)

Although I am unsure if it is explicitly stated, it is implied that nodes have an identifying number. You can see this in Figure 2 and 3 of the paper where each node is labeled with a number.

  How could I limit the mutation functions to not add backpropagation connections?

By backpropagation connections I assume you mean recurrent connections (correct me if I am wrong). You can prevent recurrent connections in many ways, but one way is to maintain a partially ordered set. When adding a connection between two nodes you check to see the order of those two nodes in the partially ordered set. The one that comes first will be the node from which the connection starts, while the second will be the node at which the connection ends.

As a note, we can prevent recurrent connections but often times allowing them provides opportunities to find a better solution (as @PaulG comments)


The paper Connectionist Temporal Classification: Labeling Unsegmented Sequence Data with Recurrent Neural Networks (2006), by Alex Graves et al., mentioned in the linked TensorFlow documentation, presents and explains the CTC loss and the CTC forward-backward algorithm (in section 4.1).

Have also a look at this article Sequence Modeling With CTC (2017) by Awni Hannun.


Disabling of genes during crossover (NEAT)

In your example, the output node would still get a value from Input1, even though Input2 is disabled.

If the child was:

Child = {
          (1, Input1, Output1),
          (2, Input2, Output2) //Disabled
         }

Then Output2 would return 0, meaning it wasn't activated.

For your second question, it is up to your implementation. You could:

1.) Use only the connection genes in crossover, and derive your node genes from the connection genes

2.) Test if every node is in use, and delete the ones that are not


What evolutionary algorithms are there that model epigenetics?

Over the last few years, evolutionary computation research has shown increasing interest in including some aspect of epigenetics. For example:

A 2008 paper by Tanev and Yuta
Work from Lee Spector's genetic programming group
A recent paper by Ricalde and Banzhaf


Training network to detect spelling mistakes

I'd personally be more inclined to try longstanding deterministic methods such as Damerau (for typing errors) or Soundex (for homonyms arising from transcribed speech). At the very least, I'd use those as a baseline for any more 'AI-based' approach.


Which neural network architectures are there that perform 3D convolutions?

There are many approaches for training CNN on 3d data, but the decision to use a particular architecture is heavily dependant upon the format of your dataset.

If you are using 3d point cloud data, I would suggest you go through PointNet and PointCNN.

But training a CNN on 3d point clouds is very tough.

There is also a way to train CNNs by posing the 3d structure from different viewpoints (Multiview CNNs).

But remember that training CNN on 3d data is really a tough task.

If you plan to use a voxelized input data format, I suggest going through VoxelNet.

Since you are mentioning deconvolution, the most relevant paper I can come across is 3D U-Net: Learning Dense Volumetric Segmentation from Sparse Annotation.

But deconvolution in its own right is a very expensive operation, which acting on 3d data makes it very hard, so I would suggest you check for alternate methods.


Do we also need to model a probability distribution for the decoder of a VAE?

Thanks @nbro for pointing this out.

The pictorial architecture in the slides uses the Gaussian loss, which when coupled with Maximum Likelihood Estimation gives the squared error loss (not to remove any tractability issues). The main reason we do the encoder Gaussian trick is to force the latent variable $z$ to be normal so that we can apply $KL$ $Divergence$ to optimise an otherwise intractable integral. You can get a better intuition and reasoning in this video.

The pictorial architecture is basically taking the Gaussian loss so that the final loss becomes the squared error loss effectively. Also the loss term used in your blog link is exactly the same loss term used in the original paper, but the blog is using CE loss (it is the more common loss used for classification). I am not sure how they are using the CE loss though, since it is only valid for $0$ and $1$ values and AFAIK MNIST data-set has grayscale images.

I am not exactly sure how they implement the randomness of the Gaussian loss in the decoder structure, but in the simplest of cases they just take the MSE

Check out this blog on VAE's (where they have taken the mean $\Sigma$ which they have abbreviated as mean, I have not checked their implementation detail to know what they exactly mean by that) and also this answer on Data Science on implementation of VAE's4 (both of which gives a more general form of loss). Also for the exact Mathematics check out Appendix C of the original paper.


Reinforcement Learning with more actions than states

As far as I understood, most RL applications have much more states than there are actions to choose from.

Yes, this is quite common, but in no way required by the underlying theory of Markov Decision Processes (MDPs). The most extreme version of the opposite thing - with one state (or effectively no state, as state is not relevant)  - are k-armed bandit problems, where an agent tries to find a single best long-term action in general from a selection of actions. These problems typically would not use RL algorithms such as Q-learning or policy-gradients. However, that is partly because they are described with different goals in mind (e.g. minimising "regret" or simply gaining as much reward as possible during the learning process), and RL algorithms will work to solve them, albeit less efficiently than algorithms designed to work on bandit problems directly.

  I am thinking about using RL for a problem where I have got a lot of actions to choose from, but only very few states.

That should work, provided your problem is still a MDP. That means for instance that the state evolves according to rules depending on which action was taken in which starting state. If the state evolution is instead arbitrary or random, then you may have a contextual bandit problem instead.

There is an important difference here between:

a large number of entirely different actions, each with different results, which need enumeration and have to be explored separately

and

a large action space due to measurable values which are part of an action, such as how much force to apply in a motor

The former will require lots of exploration, since any specific combination of action and state could be the ideal. With the latter, you can use that fact that numerical values that are similar will often give similar results, which will make generalisation via function approximation (e.g. neural networks) work efficiently in your favour.

  The algo should render (for whatever reason) a sentence with three words. I always want to have a sentence with three words, but I have many words to choose from. After choosing the words, I get some sort of reward

This seems more like the first bullet-point above, although that may depend if a natural language model could be applied for example. E.g. if "This is good" and "This is great" would produce similar rewards in a specific state, then there is maybe some benefit to generalisation, although I am not quite sure where you would fit this knowledge - possibly in a generator for a sentence vector as the "raw" action and then have a LSTM-based language model produce the actual action from that vector, similar to seq2seq translation models.

  Are RL algorithms an efficient way to solve this?

Yes, but whether or not it is the most efficient will depend on other factors, such as:

Whether the environment is stochastic or deterministic with regard to both reward and state progression.
Whether state progression is key to obtaining the best rewards in the long term (e.g. there is some "goal" or "best" state that can only be reached by a certain route).
What the actual size of the MDP is $|\mathcal{S}| \times |\mathcal{A}|$. Small MDPs can be fully enumerated, allowing you to estimate action values in a simple table. If you have 10 states and 1,000,000 discrete actions, with no real pattern of actions mapping to results, then a big 10 million entry table will actually be reasonably efficient.

Competitive algorithms to RL here might be global search and optimisation ones, such as genetic algorithms. The more arbitrary and deterministic your environment is, the more likely it is that an exhaustive search will find your optimal policy faster than RL.

  I am thinking about using policy gradients with an ε-greedy algorithm to explore a lot of the possible actions before exploiting the knowledge gained.

This should be fine. Exploration here is definitely important, but finding the sweet spot for the right amount of it will be hard, and depend on other traits of the environment.

You may want to use something like upper confidence bound action selection or simply optimistic initial values, in order to ensure exploration does not miss certain actions. An epsilon greedy approach will miss a certain fraction of actions over time, and the expectation of that fraction grows smaller progressively more slowly, so it may be possible to miss an important action for a long time if you rely on being able to randomly select it.

  To give a handy example: The algo should render (for whatever reason) a sentence with three words. I always want to have a sentence with three words, but I have many words to choose from. After choosing the words, I get some sort of reward.

I would consider modelling this as sequences of 3 actions, each of which chooses a word, with the state being a start token (whatever the state you already have) plus the sentence so far, and on every 3 words the environment is consulted to reset the state to the next start token and to gather a reward (rewards for interim steps would be zero).

Doing this immediately makes the state space much larger than the action space, as your state includes history of up to two actions. If you had 10 different start states, and 100 word choices, then your state space would be 101,010 and action space 100.

This will fit available designs of RL algorithms, and allow for learning some internal language modelling if it is relevant. It will reduce your need to model sentence construction outside of the agent. Most importantly, if "good" or "bad" sentences tend to start or end with certain words, and you use function approximation, then the algorithm may discover combinations more efficiently than iterating over all sentences as if they were completely independent.


How Euclidean distance algorithm calculate two different face images are match or not match in face recognition?

Simply put, Euclidean distance measures how far away two items are (see Neil Slater's comment).

In order to apply this to a pattern recognition task, you will need to convert the items to compare (in your case images of faces) into feature vectors (ie lists of numerical values), and then you do a pairwise comparison to work out how distant two faces are. You will then need to set a threshold where you treat two images as being the same face (typically where the distance between the feature vectors is small).

Selecting the right features is obviously crucial here. I'm not an expert on face descriptions, but it would probably be something like

the distance between the eyes
the distance between the bottom of the nose and the top of the upper lip
...

Once you have these measurements, store the values for each image in a vector and you can apply the Euclidean distance. Effectively, each image is represented as a point in the  $m$-dimensional feature space, where each measurement is a dimension. To select good features make sure they are not correlated (ie they are independent of each other) and are the same scale (eg all are distances, so not eye colour)

The choice of Euclidean distance is fairly minor: there are other distance metrics which might work equally well or even better. As I mentioned, the key point is selecting appropriate feature values.


Are there other mathematical frameworks of artificial general intelligence apart from AIXI?

Gödel machine
There is another mathematical framework for AGI: the Gödel machine, which was proposed by Jürgen Schmidhuber (who also worked with Marcus Hutter). In the paper Gödel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements (2003), Schmidhuber describes the Gödel machine as follows

They are universal problem solving systems that interact with some (partially observable) environment and can in principle modify themselves without essential limits apart from the limits of computability. Their initial algorithm is not hardwired; it can completely rewrite itself, but only if a proof searcher embedded within the initial algorithm can first prove that the rewrite is useful, given a formalized utility function reflecting computation time and expected future success (e.g., rewards). We will see that self-rewrites due to this approach are actually globally optimal (Theorem 4.1, Section 4), relative to Gödel's well-known fundamental restrictions of provability. These restrictions should not worry us; if there is no proof of some self-rewrite's utility, then humans cannot do much either.
The initial proof searcher is $O$()-optimal (has an optimal order of complexity) in the sense of Theorem 5.1, Section 5. Unlike hardwired systems such as Hutter's and Levin's (Section 6.4), however, a Gödel machine can in principle speed up any part of its initial software, including its proof searcher, to meet arbitrary formalizable notions of optimality beyond those expressible in the $O$()-notation. Our approach yields the first theoretically sound, fully self-referential, optimal, general problem solvers.

Space-time embedded agents
This work combines Russell's bounded rationality with Legg's and Hutter's definition of universal intelligence to provide a framework for AGI that takes into account resource (space and time) constraints and other issues (such as that the environment can modify or even destroy the agent).


How to fairly conduct a model performance with 5-fold cross validation after augmentation?

If you used your five $X_{test}$ sets multiple times (to measure the average AUC) to decide on the best set of hyperparameters (i.e. optimizer, learning rate, batch size, dropout, activation) then yes, you successfully conducted hyper-parameter optimization. However, the AUC you received for the best set of hyperparameters found (by manual tuning) is not representative of the real performance of your model.

This is because the fact of using a test set to tune the parameters of your model degenerates it back to a "training" set, because the data is not being used to measure the performance of the model but to improve it instead (although on a different level of abstraction, i.e. not to directly influence the parameters of the model, such as neural network weights), making the resulting AUC an overly optimistic biased estimator of the real AUC (that it could have resulted in for an unseen test dataset).

That's why, if you care both about hyperparameter optimisation and being able to measure the "real" performance of your model, you need to split your dataset into three "buckets": training set $X_{train}$, validation st $X_{val}$ and test set $X_{test}$. $X_{test}$ should only be used once (after you've trained and tuned the model), and assuming it has enough samples and the samples are representative of the unseen data, you should get a good estimate of your model performance. $X_{val}$, on the other hand, is your validation set which you can reuse as many times as you want to find the optimal set of hyperparameters that result in the highest performance (i.e. AUC).


Consider the task of sequence prediction, so you want to predict the next element of a sequence $e_t$ given the previous elements of this sequence $e_{t-1}, e_{t-2}, \dots, e_{1} = e_{t-1:1}$. Teacher forcing is about forcing the predictions to be based on correct histories (i.e. the correct sequence of past elements) rather than predicted history (which may not be correct). To be more concrete, let $\hat{e}_{i}$ denote the $i$th predicted element of the sequence and let $e_{i}$ be the corresponding ground-truth. Then, if you use teacher forcing, to predict $e_{t}$, rather than using $\hat{e}_{t-1:1}$, you would use $e_{t-1:1}$.

Recall that supervised learning can also be thought of as learning with a teacher. Hence the expression "teacher forcing", i.e. you force the predictions to be based on correct histories (the teacher's labels).

Of course, intuitively, teacher forcing should help to stabilize training, given that the predictions are not based on noisy or wrong histories.

See also the blog post What is Teacher Forcing for Recurrent Neural Networks? by Jason Brownlee.


Does it have to do with the reward function?

This seems likely to me. You have chosen a reward that is unusual in that it cross-links episodes. It is not really a reinforcement problem to optimise behaviour with respect to results of previous episode behaviour in this way. This might be an option for an evolutionary fitness context, if you have competing teams against the same environment in a tournament style selection.

Reinforcement learning should really take as direct measure of your goal as you can construct. In this case you want to minimise some scalar quantity, and that is an obvious candidate as a negative reward. So the reward should be the negative of the total non-renewable energy consumption. The maximum possible value in theory for any single episode would be zero.

You may still have problems with a multi-agent setup oscillating using Q-learning, it will depend on how much each agent views the full, relevant state, and whether you are training several distinct agents at the same time (more likely to oscillate), or a single type of agent with multiple instances in each environment (less likely to oscillate, but still can if it has too blinkered a view of the environment as experienced by the other agents). But having a single shared goal with shared reward like you do here should in theory help with stability.


What is the difference between a Hopfield Network and a Neural Network or a Perceptron?

Hopfield stores some predefined patterns (lower energy states) and when an non seen pattern is fed to the Hopfield net, it tries to find the closest match among the stored patterns. Hence the output of a Hopfield is always one of the predefined patterns which matches closely to the unseen input pattern.

This is not the case with Feed Forward Neural Nets (where no such predefined patterns are stored) and every input generates a corresponding output. Here (in Feedforward) the output is generated by a predefined function (which is self-adjusted during training session) where as in Hopfield predefined patterns are stored and outputted (no such functions exist).


How to understand the 4 steps of Monte Carlo Tree Search

Imagine a game with a very clear first move, such as a game where choosing to go first if you win a coin toss brings a clear and obvious advantage.

In this situation standard MCTS does little exploration down the side of the tree that branches at the win toss > let opponent start step, as the basic simulations of the rest of the game at this split quickly show the large gain you get when always starting when you win the coin toss.

As a result, you would end up with a tree with very little expansion on the side of win the toss > put your opponent in, as every simulation step you do from even the most senior nodes ends with much worse expected outcome values than the alternatives on the other side of the tree where you do the correct move of always playing first.

These nodes on the side of letting your opponent start have huge potential sub trees (as the whole game would still need to be played out if your opponent started), but would have very little searching down them. As a result, on this side of the tree, you would have many leaf nodes with large (but as yet unexplored, outside of the basic, early simulations down that side) sub trees that you could search if you modified the exploration vs exploration algorithm.

As a basic example, take the 0/3 node at the far right on level one of the wiki example below, which would get much less attention than the much more promising 7/10 and 3/8 nodes, despite having potentially many subsequent children it could explore. If you took this node as your L node, you would expand it's children that you have not yet searched, and thus find out more about why this side of the tree is bad and update our now more granular probabilities accordingly, just as it does for the 3/3 node here:


Is a VGG-based CNN model sometimes better for image classfication than a modern architecture?

VGG is a more basic architecture which uses no residual blocks. Reset usually perform better then VGG due to it's more layers and residual approach. Given that resnet-50 can get 99% accuracy on MNIST and 98.7% accuracy on CIFAR-10, it probably should achieve better than VGG network. Also, the validation accuracy should not be 100%. You could try increasing the size of your validation set to improve accuracy on validation. VGG network should perform worst than ResNet in most scenario, but experimenting is the way to go. Try and experiment more to get a method that works for your data. Hope that I can help you and have a nice day!


How to map X to Y for TensorFlow RNN training data

I found out how to get 3D output from LSTMCell so that I can matmul with output weights + biases and subtract with expected values:

Inputs & expecteds should be: placeholder(,[times,batch_size,num_inp]) instead of batch_size first then times. However, tf.keras.layers.LSTM will ask for [batch_size,times,num_inp]
Use tf.nn.static_rnn with a list of inputs, instead of 1 input

Source code:

import tensorflow as tf;

x = [[[1],[2],[3]],[[4],[5],[6]]];
times = 2;
bsize = 3;

#3d input
inputs = tf.placeholder(tf.float32, [times,bsize,1]);

cell   = tf.nn.rnn_cell.BasicRNNCell(20);
hids,_ = tf.nn.static_rnn(cell,tf.unstack(inputs,times),dtype=tf.float32);

sess = tf.Session();
init = tf.global_variables_initializer();
sess.run(init);

#results in 2d
print(sess.run(hids, {inputs:x}));


Why would the reward of A3C with LSTM suddenly drop off after many episodes?

The thing you're explaining is not impossible for a RL model, but it's rare. That's a known thing that some RL algorithms work or don't work depending on a random seed. I implemented the same model once to play KungFuMaster-v0. It was during a university RL course and the code seemed fine (actually 2 people including teacher looked at it very carefully and they didn't find any bugs). I remember calling it 10 times a row and one time out of ten it showed that nasty behavior. There were teacher's notes in the task: if the reward suddenly drops to 0 and stay there for a long time, check your code, there's a high probability of a bug. So I'd say if your net works just fine 9 times out of 10, probably there are no bugs, otherwise if I were you, I'd carefully check the code.


Is my understanding of back-propogation correct?

Your understanding seems to be correct (although your explanation isn't completely precise), apart from "adding it to your original gradient vector". You add the gradient vector to the parameters/weights vector.
(Note that back-propagation is just the algorithm that computes the gradient vector. The update of the parameters with the gradient of the loss function is the gradient descent/ascent step, even though it's true that some people, at least in the context of deep learning, refer to the combination of gradient descent and the computation of the gradients as the back-propagation algorithm, but this is just a terminology issue, which you should not dwell too much on.)

Also, how can this be done in iterations over training examples?

If I understand this question correctly, you want to know how we would update the parameters when there's more than one training example. In that case, you compute a gradient vector for each training example. Then the average of the gradient vectors (which is also a vector) is the actual gradient vector that you use to update the parameters. See this answer for more info.


The back propagation must be done in two steps.

Transfer derivative

Given the output value, you must calculate its slope. This is simple as you are using the sigmoid activation function. So the derivative can be calculated as follows

# Calculating slope
def transfer_derivative(output):
    return output * (1.0 - output)

Back propagate the error

Calculate the errors for the various layers of the network and update the weights and bias.

# Error calculation

# For output layer
error = (expected - output) * transfer_derivative(output)

# Hidden layers
error = (weight_k * error_j) * transfer_derivative(output)

Where error_j is the error signal from the jth neuron in the output layer, weight_k is the weight that connects the kth neuron to the current neuron and output is the output for the current neuron.

And finally updating weights

weight = weight + learning_rate * error * input

Here is a detailed explanation of implementing neural networks from scratch using Python along with sample code. Give it a read.


Why is neural networks being a deterministic mapping not always considered a good thing?

Your intuition is right. The main reason why a deterministic function can be undesirable (or even dangerous, as I will explain below with an example) is that we may not have enough data to learn the correct function, so we may end up learning the incorrect one. Right now, no other reason, from a theoretical point of view, comes to my mind, but below I will mention a few applications/cases where a deterministic function may not be desirable.
If we had all data pairs $\{(x_i, y_i)\}$, where $x_i \in \mathcal{X}$ and $y_i = \mathcal{Y}$ are, respectively, an input and output from the unknown function that you want to learn $f: \mathcal{X} \rightarrow \mathcal{Y}$, i.e. $f(x_i) = y_i$, then you could reconstruct $f$: whenever $x_i$ is given, you just need to return $y_i$.
Of course, in reality, we almost never have a large enough (training) dataset to approximate out desired (but usually unknown) function. If we learn only one (deterministic) function, then, in principle, you can catastrophically fail, i.e. your approximation of $f$, denoted as $f_\theta$ (where $\theta$ are the parameters of the neural network or any other model), can produce outputs that are completely wrong.
Let me try to give you a simple example. Let's say that $f$ is defined as follows
$$f: \mathbb{N} \rightarrow \{0, 1\}$$
You are given a training labelled dataset $$D = \{(4, 1), (11, 0), (8, 1), (31, 0), (16, 1), (7, 0) \}.$$
Apparently, our unknown function is defined as
\begin{align}
h_1(x)=
\begin{cases}
1, &x \text{ mod } 2 \equiv 0\\
0, &\text{otherwise}
\end{cases}\tag{1}\label{1}
\end{align}
Given that $D$ is small, your neural network, $f_\theta$, can easily overfit $D$, i.e. learn to output $1$ when $x$ is even and $0$ otherwise.
However, what if $f$ is not that function in equation \ref{1} and we collected just a dataset that doesn't represent $f$ well enough? If you look at $D$ more carefully, you will see that another possible hypothesis for $f$ is the following
\begin{align}
h_2(x)=
\begin{cases}
1, &x \text{ mod } 4 \equiv 0\\
0, &\text{otherwise}
\end{cases}\tag{2}\label{2}
\end{align}
However, given that your neural network can only compute one of these functions at a time, it could compute the wrong one. Let's say that $f_\theta \approx h_1$, then it should produce $1$ when $x = 6$ (an even number). If the correct unknown function was $h_2$, i.e. $f = h_2$, then $f_\theta(6) = 1$ would be wrong (because $6$ is not a multiple of $4$).
Of course, this is just a toy example. However, there are many other cases where this can happen, which may not be desirable, such as healthcare, medicine or self-driving cars, where the wrong prediction can lead to catastrophic consequences, such as the death of a person.
If we maintain a probability distribution over the possible functions that are consistent with the observed data so far, we can (partially) avoid this issue. So, continuing with the example above, this probability distribution over functions should be highly uncertain about $x = 6$, whether it produces $0$ or $1$, because it has never seen the label for $x=6$, so a medical doctor or the human driver could intervene in the case of (high) uncertainty.
For this reason, in the last decade, people have started to incorporate uncertainty estimation in neural networks. Neural networks that model uncertainty (to some degree) are often called Bayesian neural networks (BNNs), and there are different approaches (such as variational BNNs, MC dropout or Monte Carlo-based approaches). If you are interested in this topic, the paper Weight Uncertainty in Neural Network (2015) is a good start, especially if you are already familiar with VAEs. Given that this is a very new research area, the current solutions are still not very satisfactory. For example, you can find examples in the literature that report that MC dropout can produce very bad estimates of uncertainty (even in my master's thesis I have observed and thus concluded that this is the case), i.e. they can be highly certain when they should be highly uncertain.


What is the best algorithm to solve the regression problem of predicting the number of languages a Wikipedia article can be translated to?

I think it's difficult to tell wich algorithm is "the best" or "the simplest".
I had the same issue of choosing the suited NLP algorithm for my dataset and I used :
https://scikit-learn.org/stable/tutorial/machine_learning_map/index.html
Then I recommanded you to test many algorithms as you can to find the best for your needed.


How can I measure an object using Computer Vision and neural network techniques?

Father Ted explains why this is a hard problem.

Seriously -- if you have stereo images it should be possible, since that's what we use for depth perception. If you know how far away points x1 and x2 are, then you can measure distance using trigonometry. No neural networks needed, I guess. https://en.wikipedia.org/wiki/Triangulation_(computer_vision)


When training a Deep Q network with experienced replay, you accumulate what is known as training experiences $e_t = (s_t, a_t, r_t, s_{t+1})$. You then sample a batch of such experiences and for each sample you do the following.

Feed $s_t$ into the network to get $Q(s,a;\theta)$.
Feed $s_{t+1}$ into the network to get $Q(s’,a’,\theta)$.
Choose $max_aQ(s’,a’,\theta)$ and set $ \gamma max_aQ(s’,a’,θ)$ + $r_t$ as the target of the network.
Train the network with $s_t$ as input to update $\theta$. The output from the input of $s_t$ is $Q(s,a,\theta)$ and the gradient descent step minimises the squared distance between $Q(s,a,\theta)$ and $\gamma max_aQ(s’,a’,θ)$ + $r_t$


Which algorithm should I use to map an input sentence to an output sentence?

In your case you can use either RNN (especially BiLSTM with ELMo and attention mechanism for better accuracy) or Transformer based architectures (the best of them today is BERT). But for both cases you need data to train the model (i.e sequences of input/output like in your question).

I believe the best choice in your case is BERT as it's achieving state of the art performance in most NLP tasks and is already pretrained so you don't need a massive data to retrain the model. Also, BERT is pretrained on "Next Sentence Prediction" and allows "2 separate sentences" as input which helps a lot in your case. The only drawback, compared to other methods, is that you need fine-tuning the model so it's not a completly "ready to use" model.

For more information:

Here is the github repository of BERT: BERT-repo. For quick explanation check: The Illustrated BERT. For detailed explanation see BERT paper: BERT-paper.


Can dropout layers not influence LSTM training?

A couple of points:

Have you firstly scaled your data, e.g. using MinMaxScaler? This could be one reason why your loss readings remain high.
Additionally, consider that while Dropout can be useful for reducing overfitting, it is not necessarily a panacea.

Let's take an example of using LSTM to forecast fluctuations in weekly hotel cancellations.

Model without Dropout

# Generate LSTM network
model = tf.keras.Sequential()
model.add(LSTM(4, input_shape=(1, previous)))
model.add(Dense(1))
model.compile(loss='mean_squared_error', optimizer='adam')
history=model.fit(X_train, Y_train, validation_split=0.2, epochs=20, batch_size=1, verbose=2)

Over 20 epochs, the model achieves a validation loss of 0.0267 without Dropout.

Model with Dropout

# Generate LSTM network
model = tf.keras.Sequential()
model.add(LSTM(4, input_shape=(1, previous)))
model.add(Dropout(0.5))
model.add(Dense(1))
model.compile(loss='mean_squared_error', optimizer='adam')
history=model.fit(X_train, Y_train, validation_split=0.2, epochs=20, batch_size=1, verbose=2)

However, validation loss is slightly higher with Dropout at 0.0428.

Make sure you have specified the loss function correctly. If you are forecasting a time series, then you are most likely working with interval data. Therefore, mean_squared_error is an appropriate loss function as one is trying to estimate the deviation between the predicted and actual values.

As a counterexample, binary_crossentropy would not be suitable as the time series is not a classification set. However, misspecifying the loss function is a common error. Therefore, you also want to make sure you are using the appropriate loss function and then work from there.


When should I use Reinforcement Learning vs PID Control?

I think the comments are basically on the right track.

PID controllers are useful for finding optimal policies in continuous dynamical systems, and often these domains are also used as benchmarks for RL, precisely because there is an easily derived optimal policy. However, in practice, you'd obviously prefer a PID controller for any domain in which you can easily design one: the controller's behaviors are well understood, while RL solutions are often difficult to interpret.

Where RL shines is in tasks where we know what good behaviour looks like (i.e., we know the reward function), and we know what sensor inputs look like (i.e. we can completely and accurately describe a given state numerically), but we have little or no idea what we actually want the agent to do to achieve those rewards.

Here's a good example:

If I wanted to make an agent to maneuver a plane from in front of an enemy plane with known movement patterns to behind it, using the least amount of fuel, I'd much prefer to use a PID controller.
If I wanted to make an agent to control a plane and shoot down an enemy plane with enough fuel left to land, but without a formal description of how the enemy plane might attack (perhaps a human expert will pilot it in simulations against our agent), I'd much prefer RL.


How can I find a specific word in an audio file?

After some research on the internet, I realized that using VOSK toolkit in python, it can be found (detect) any particular word in audio file or real time audio streaming.
https://alphacephei.com/vosk/


Why should the number of neurons in a hidden layer be a power of 2?

I have read somewhere on the web (I lost the reference) that the number of units (or neurons) in a hidden layer should be a power of 2 because it helps the learning algorithm to converge faster.

I would quite like to see a reference to this suggestion, in case it has been misunderstood.
As far as I know, there is no such effect in normal neural networks. In convolutional neural networks, it might potentially be true in a minor way because some FFT approaches work better with $2^n$ items.

Is this a fact? If it is, why is this true? Does it have something to do with how the memory is laid down?

I would say that this is not a general fact. Instead, it seems like misunderstood advice to search some hyperparameters such as number of neurons in each layer, by increasing or decreasing by a factor of 2. Doing this and trying layer sizes of 32, 64, 128 etc should increase the speed of finding a good layer size compared to trying sizes 32, 33, 34 etc.
The main reason to pick powers of 2 is tradition in computer science. Provided there is no driver to pick other specific numbers, may as well pick a power of 2 . . . but equally you will see researchers picking multiples of 10, 100 or 1000 as "round numbers", for a similar reason.
One related factor: If a researcher presents a result for some new technique where the hidden layer sizes were tuned to e.g. 531, 779, 282 etc, then someone reviewing the work would ask the obvious question "Why?" - such numbers might imply the new technique is not generic or requires large amounts of hyperparameter tuning, neither of which would be seen as positive traits. Much better to be seen using an obvious "simple" number . . .


Since you only have fixed types.

For colour, I think it is fairly straight forward.
For number, simplest way is to plot a projection histogram and count the points of discontinuity.

An example of the projection histogram

For fill, You can find the number of islands. Islands of background colour.
For shape, Like Clement Hui suggested you can use shape detection


What is the state-of-the-art algorithm for neural style transfer?

So for neural style transfer, using the particular method described in Gatys paper, nobody has done better than using VGG net. This is seemingly due to VGGs inherent stability and inability to learn non-robust features of images. More on this here: https://reiinakano.com/2019/06/21/robust-neural-style-transfer.html
That being said, GANs have had huge success in the field of style transfer, getting much better results than the neural style transfer method described in the paper you mentioned. Cyclegan is one of the best in this respect: https://machinelearningmastery.com/what-is-cyclegan/


In DQN, when do the parameters in the Neural Network update based on the reward received?

However, all this is doing is updating the parameters of the Neural Network to produce an output that matches the Target Q values as close as possible.

Yes. That is all it needs to do because we have defined the policy around the Q values like so:
$$\pi(s) = \text{argmax}_a \hat{q}(s,a,\theta)$$
Where $\theta$ is the neural network weights.
Therefore, if the estimates of Q are approximately the same as the action value of the optimal policy, the policy in DQN is approximately the optimal policy.

How does the algorithm know +10 is good?

It does not, at least not directly. The algorithm knows, approximately, what the action values are if it acts consistently with their current estimates by always choosing the maximising action at each step.
The learning process will learn that +10 is relatively good in your scenario because it never finds anything better when exploring.


Reinforcement Learning for an environment that is non-markovian

RL is currently being applied to environments which are definitely not markovian, maybe they are weakly markovian with decreasing dependency.
You need to provide details of your problem, if it is 1 step then any optimization system can be used.


Several questions related to UCT and MCTS

Is this the only big difference? Or in other words, can I do the same implementation as in a simple MCTS with the 4 stages: selection, expansion, simulation and backpropagation, where the result of the simulation is the accumulated reward instead of a value between 0 and 1? How would the UCT selection be adjusted in this case?

No, this is not the only difference. The important differences between the "original UCT" (as described in the paper you linked), and the "standard UCT" (as typically implemented in game AI research) are nicely summarised in Subsection 2.4 of "On Monte Carlo Tree Search and Reinforcement Learning". I'd recommend reading the entire paper, or large parts of it, if you have the time, but to summarise the key differences:

Original stores as many nodes as allowed by memory limitations per iteration, standard only expands one node per iteration.
Original uses transpositions, standard implementation does not
Original uses discount factor $\gamma$, standard does not (equivalent to picking $\gamma = 1$)
Original takes into account at which point in time rewards were observed, standard does not

That last point is the one your question mainly seems to be about. Your idea of using a standard implementation, but accumulating any intermediate rewards and treating them as one large terminal reward, would not be the same. Actually taking into account the times at which rewards were observed, as done in the original UCT, can lead to more accurate value estimates in nodes in the middle of the tree (or at least to finding them more quickly). Your idea would be equivalent to learning from Monte-Carlo backups in Reinforcement Learning literature (e.g. Sutton and Barto's book), whereas the original UCT implementation would be more similar to learning from TD($0$) backups.

Note that, when talking about the "standard" implementation of UCT, that's very often in papers about two-player zero-sum games in which all intermediate rewards have a value of $0$, discounting is considered to be unimportant (i.e. $\gamma = 1$), and only terminal game states have a non-zero reward. In this special case, the two ideas do become equivalent.

  What does the UpdateValue function in line 12 does exactly? In the text it says it is used to adjust the state-action pair value at a given depth, will this be used to the selection? How is this calculated exactly?

This would be done in the "standard" way. The visit count is incremented, and $q$ could be added to a sum of all $q$ values ever observed during the search for that state-action pair, such that the average score can be computed as the sum of $q$ scores divided by visit count. This average score is the $\bar{X}$ used in Selection.

  What is the depth parameter needed for? Is it related with the UpdateValue?

I think it's usually not really needed. In the paper they describe that it may be considered to have a depth cut-off. From paper:

  "This can be the reach of a terminal state, or episodes can be cut at a certain depth (line 8)."


Is the negative of the policy loss function in a simple policy gradient algorithm an estimator of expected returns?

If I understand your question correctly, you are wondering whether the
policy gradient objective coincides with some real measure of progress.
This is exactly what the Policy Gradient Theorem proves (see Sutton et
al. (2000) or Sutton and Barto (2018), chapter 13). In particular,
policy gradient methods optimize the value of the start state $s_0$ under the
current policy, $v_\pi(s_0)$. Since this value is defined as an
expectation over returns, then your conclusion is correct.

Sutton, Richard S., and Andrew G. Barto. 2018. Reinforcement Learning -
an Introduction. Adaptive Computation and Machine Learning. MIT Press.
http://www.worldcat.org/oclc/37293240.

Sutton, Richard S, David A McAllester, Satinder P Singh, and Yishay
Mansour. 2000. “Policy Gradient Methods for Reinforcement Learning with
Function Approximation.” In Advances in Neural Information Processing
Systems, 1057–63.


How does Hearthstone AI deal with random events

The most "standard" implementation of MCTS probably involves storing copies of game states inside nodes. This works fine for deterministic games, but not for non-deterministic games due to the reasons you mentioned.

In non-deterministic games, one of the easiest ways to make MCTS work is to take the perspective that every node in your tree should map to / represent / encode a trajectory or sequence of actions, rather than a state. This means that every node collects statistics (num wins / num visits etc.) for the trajectory of actions it represents, rather than for the state it represents.

This perspective can be implemented very easily by simply not storing any game states in nodes at all. Instead, whenever you traverse the tree (in the Selection phase of MCTS), you should simply re-simulate all the actions along that path through the tree, starting from the root state again. This way, different visits through a single node can result in different game states being "observed" in that node due to nondeterministic game state transitions. In the limit (after an infinite amount of time), every node will estimate the expected value of the trajectory of actions leading to that node, rather than the game-theoretic value of a single, deterministic resulting game state. This whole idea is sometimes referred to as "Open-Loop MCTS", for example in this paper.

What I described above is a simple way to get better performance from MCTS in games involving nondeterministic state transitions as you described (such as random amounts of damage being dealt), but there are many much more complicated ideas out there too. I suspect more complex approaches will especially be necessary to deal with more "drastic" forms of nondeterminism (resulting from random card draws, or resulting from randomization-based approaches for dealing with imperfect information such as not knowing which cards your opponent has).

There was a Hearthstone AI competition relatively recently, and some useful ideas may be found, for example, on this page of work related to that competition.


How to choose the first action in a Monte Carlo Tree Search?

Yeah, it seems that you're right and based on the description of the paper it would indeed behave uniformly random at the very first iteration (or maybe just always deterministically pick whichever action happens to be the first one in the list). I can't find anything that would suggest otherwise in the paper, and also the pseudocode they put on arXiv suggests the same behaviour.
I can't really think of any reason why this would be better than playing according to $P(s, a)$ in the very first iteration though. Maybe it creates a tiny little bit more variety in the tree search results you get? I suppose all the stochasticity that is normally inherent to a vanilla MCTS is no longer present in MuZero (or AlphaZero), because they always run for exactly the same number of iterations, and don't have any sort of random rollouts anymore; this would at least introduce a tiny bit of variation.
On the other hand, I also can't imagine this choice really making a meaningful difference in practice, except maybe if you go down to extremely low iteration counts (like if you run fewer iterations than there are legal actions in the root node).


Is there a service that can search for answers to general questions?

You can use Google

https://encrypted.google.com/search?hl=en&q=when%20was%20Einstein%20born
and parse the response.

Wolfram ALPHA is another candidate.

http://m.wolframalpha.com/input/?i=what+year+was+Einstein+born&x=0&y=0

You can parse the returned html and see "Result:" div.


What heuristic to use when doing A* search with multiple targets?

If by "visit multiple targets", you mean "visit several points in the fastest order", you are no longer in a simple path-finding-style search problem, but instead in an optimization problem. This is roughly the difference between chapters 3 & 6 of Russell & Norvig's section on search.

To do this, you can't just change your heuristic, instead you need to reframe your problem:

Instead of states in your search being locations, they should be tours. Each state is a list of all the places you need to visit, in a specific order.
Instead of actions being movements from one location to another, they need to be transformations from one tour to another. For example, if you swap the order that you visit two adjacent locations, then you'll get a different tour. This gives you a way to "move" between tours.
A solution means visiting all the locations as fast as possible. If you know how to get between two locations, just store the distances, and then sum all the distances together to get the cost of a tour. If you don't know, you can just run A* from each place to each other place once, and then cache the distances afterwards.
A heuristic will depend on your domain. A reasonable start might be to assume that you can visit each location from the nearest other location you've already visited. Generally, heurstics based on the idea of minimum spanning trees are effective for this domain.

The real answer though, is to try a technique that is meant for this kind of problem, like a local search algorithm. Notice that if we know the cost of moving between any two points, we can just adopt a greedy approach: make the move that improves things the most each time. This is often faster than waiting for A* in practice if you just want a good solution, but it doesn't need to be the very best one.


Are activation functions applied to feature maps?

Yes, it is applied element-wise on every single value of the feature map.
Assuming ReLU as your nonlinearity function, all negative values of the image feature map are set to zero, and the rest of the elements stay unchanged.


The dictionary's definition of off-the-shelf is

used to describe a product that is available immediately and does not need to be specially made to suit a particular purpose

The same dictionary provides several examples

You can purchase off-the-shelf software or have it customized to suit your needs.
If you have complex needs, we don't recommend that you buy software off the shelf.
For this, off-the-shelf algorithms included in the robot's programming libraries are used.

So, your intuition is correct! An off-the-shelf model, software, product, etc., is any model, software or, respectively, product that would be easily (or immediately) available or applicable to the specific context, but, at the same time, it may also be applicable to many other contexts or problems.
An off-the-shelf convolutional neural network is thus a typical or standard CNN that can be applied immediately in that context (but that is potentially applicable to many other contexts or problems). Examples of CNNs that could be used as off-the-shelf models are AlexNet or LeNet-5, but the actual choice depends on the context and needs.
An off-the-shelf model can also be a baseline model (i.e. a very simple model that is used in experiments as the model that every other model should outperform), but not necessarily.
Alex Graves uses this term/expression in his paper Practical Variational Inference for Neural Networks.


Could a neural network be capable to diferentiate between two boards of a game?

For optimal performance, the network complexity should fit the complexity of the game. Since we do not know the latter, your question is not answerable.


Creating a classifier for simpler classifiers trained on few training samples

The voting technique that you described is called Ensemble Learning and its improvement over time is guaranteed if each classifier is at least a little better than random.


Can the rewards be stochastic when the transition model is deterministic?

My question is, would $r_1 =r_2$?

That's usually up to you as the designer of the system.

Usually when you declare that you have "a deterministic environment", you imply that both $s'$ and $r$ are fixed values depending on $(s,a)$. So in your examples, you would expect your observations to also have $r_1 = r_2$

However, it is possible to define a MDP where transition to state $s'$ is deterministic, but $r$ is not. For instance, you could define reward in a game equal to the sum of a number of dice rolled, with better rewards (on average) resulting in more dice. This is still a valid MDP and can be solved using RL techniques.

A real-world example of this might be managing a queue of work, where you want to minimise lead time, but don't know for certain how long each task will take. Your state progression moves deterministically - you have a queue of pending tasks, current tasks and workers, and assigning a task to a worker is completely deterministic. However, you don't know how efficiently tasks will be performed until after they are done, so you don't know the reward perfectly from the assignment (whether you can treat this as random or hidden state is a more complex issue - it is often pragmatic to treat such unknown data as random though).


What is the derivative of the Leaky ReLU activation function?

Derivative gives the rate of change in $y$ for a small change in $x$ or the slope of a function at point $x$.

In the above function,

y = x      for x >= 0,     i.e. y/x = 1
y = x/20   for x < 0,      i.e.  y/x = 1/20

The following function returns the derivative of leaky ReLU as explained

private double leaky_relu_derivative(double x)
{
    if (x >= 0)
        return 1;
    else
        return 1.0 / 20;
}


How do LSTMs work if the following two matrices are not able to be multiplied?

Turns out the reason is because, for places where a dot is shown in the image above, they're actually element-wise multiplications, not dot products. A lot of sources use an X or . to denote multiplication, but don't clearly indicate they mean element-wise multiplication.


Please check this book with the normalization infos:

https://jamesmccaffrey.wordpress.com/2014/06/03/neural-networks-using-c-succinctly/

Freely available and gives good explanation to encoding with code example.

Check the part: "Effects Encoding and Dummy Encoding"


Machine Learning in relation to personality and behaviors predictions

I would start by reviewing any available tools in NLP that can help you. I know two: Watson Personality Insights and Symanto thar provide API to develop this kind of solutions.
The first one was one available in the past (Watson personality Insights) but unfortunately has been discontinued.

The IBM Watson Personality Insights service enables applications to
derive insights from social media, enterprise data, or other digital
communications. The service uses linguistic analytics to infer
individuals' intrinsic personality characteristics, including Big
Five, Needs, and Values, from digital communications such as email,
text messages, tweets, and forum posts.
The service can automatically infer, from potentially noisy social
media, portraits of individuals that reflect their personality
characteristics. The service can infer consumption preferences based
on the results of its analysis and, for JSON content that is
timestamped, can report temporal behavior.

Another comercial tool is Symanto:

Symanto Insights Platform is an AI-powered analysis tool that gives
you qualitative insights about your textual data. Just upload your
data sets or crawl information from different sources such as online
review sites or online surveys, and Symanto’s AI immediately analyses
your data and provides you qualitative insights about the author.
Symanto Insights Platform reveals the opinions of your customers and
employees by analysing text data, giving you insights about current
topics, general performances or the psychographic structure of your
audience. Whether it’s psychographic marketing, customer service,
product development or employee satisfaction, Symanto Insights
Platform helps you answer a wide range of business questions.

I´m somehow working in this field in my Master thesis so if you need any further info just let me know.


How are neural networks built in practice?

A "software library" is a codebase that includes many commonly used functions/algorithms, you do not need to write the same function again if you "import" the library.
In practice, practitioners/researchers don't often code the nitty gritty details of well-used algorithms, they just use existing libraries such as sklearn or TensorFlow that already has an existing implementation.
In the case of sklearn, ignoring some details, you can create a muti-layer perceptron in this line of code:
>>> clf = MLPClassifier(activation = 'relu', alpha=1e-5, hidden_layer_sizes((5,2))

...in which clf is an "object" that refers to the neural network, MLPClassifier is a function provided by sklearn that "creates" a neural net depending on the parameters provided.
In this case, the parameters provided are that the activation function is ReLU, where the network has two layers, with the first having 5 nodes, and the second has 2 nodes.
All other parameters that are not explicitly provided are set to a default value, in this case, the learning rate, among others.
It should be noted that this is not complete yet, we still have not completed training. Luckily, this is as simple as:
>>> clf.fit(X, y)

Where X and y are some array-shaped data/target set.
I recommend sklearn as i think its more beginner friendly.
https://scikit-learn.org/stable/getting_started.html


What kind of problems is DQN algorithm good and bad for?

I don't currently have much practical experience with DQN, but I can partially answer this question also based on my theoretical knowledge and other info that I found.
DQN is typically used for

discrete action spaces (although there have been attempts to apply it to continuous action spaces, such as this one)

discrete and continuous state spaces

problems where the optimal policy is deterministic (an example where the optimal policy is not deterministic is rock-paper-scissors)

off-policy learning (Q-learning is an off-policy algorithm, but the point is that, if you have a problem/application where data can only be or has been gathered by a policy that is unrelated to the policy you want to estimate, then DQN is suitable, though there are other off-policy algorithms, such as DDPG)

This guide also states that DQN is slower to train, but more sample efficient than other approaches, due to the use of the experience replay buffer.
Moreover, if you have a small state and action space, it is probably a good idea to just use tabular Q-learning (i.e. no function approximation), given that it is guaranteed to converge to the optimal value function.
See also this and this questions and this article (which compares DQN with policy gradients).


What is a state in a recurrent neural network?

So the equation that you mentioned is used during the backward pass in which back proppogation is performed in order to make the neural network more accurate. I think you are talking about the state during the forward pass which is completely different. In the forward pass, the neural network is simply run in order to evaluate or it is simply used as a model. The repeating module in long short term memory networks looks like this:

As you can see there are many different parts to this module. There are three main parts. The first is the forget gate layer. This layer tells the cell state or the line running across the stop what to keep. The cell state is kept by this line:
The entire network is based off of manipulating this cell state in order to get accurate results. The equation that you mentioned was related to backprop which is used to train the neural network. This is related to the cell state because it is used to calculate it during the backwards pass. @BlueMoon93 mentioned that this equation has t+1 one in it, but this is because as the recurrent neural network propogates backwards through each module the time goes from high to low. So to conclude, the cell state in an LSTM is one of the vectors that the neural network modifies based on input.


The example given based on the yolov1 paper:

The last layer has a tensor of the dimension 7x7x30. but the dimension of the last tensor is not in every case 7x7x30.

let be:
S: the number of grid cells in X and Y direction
C: the number classes to train
B: the number of bounding boxes in every grid cell

The dimension of the output tensor is calculated with this formula: SxSx(5*B+C). The given example in their paper has the following values:
S:7
B:2
C:20
(7X7X(5*2+20) = 7x7x30)

With this configuration you can detect at most 96 object (SSB -> 7*7*2) and 2 objects per grid cell. (e.g. it's not possible to detect many small object in a few grid cells)

now lets consider what are each feature map of the last tensor used for:

The data of every bounding box is stored in 5 feature maps:
- 1 Feature map for the bounding box center in x direction
- 1 Feature map for the bounding box center in y direction
- 1 Feature map for the height of the bounding box
- 1 Feature map for the width of the bounding box
- 1 Feature map for the "confidence score" of the feature map

(confidence score = P(Object)*IoU(BoundingBox,Object))

P(Object): the probability that in this cell is an object
IoU: Intersection over Union. A ration between the overlapping area and the union area:

additional there are a feature map for every class. In every cell the following probability is calculated: P(Cass|Object)

Long story short:
If the bounding box is bigger than one grid cell, then some neurons share the same values (they share the bounding box center, the bounding box size and the confidence score, because they refer to the same bounding box).

Source:
https://pjreddie.com/media/files/papers/yolo_1.pdf

edit no Bounding boxes on the image

if there are no bounding boxes on the image, then the confidence score would be zero, because there are no overlapping area. you can configure the threshold of the confidence score. look at this sample picture with threshold 0:

additionally the feature maps of the classes would be zero because every neuron represents this probability P(Class|Object) because P(Class|Object) = P(Class And Object) / p(Object); (P(Class) = 0 -> P(Class and Object) = 0)

Is adding images without bounding boxes to the training set useful?
I think it helps to lower the number of false positive matches. But that is just a guess. I have trained yolo to detect this plant https://en.wikipedia.org/wiki/Rumex_obtusifolius and I added a lot of picture without bouding boxes, becuase a low number of false positive matches was important. The result: the specificity was >99%.

Hope this helps


Is a dataset of roughly 700 sentences of an average length of 15 words enough for text classification?

It depends on the number of classes; we are getting good results with about 40 training examples per class.

A good way to get an idea about this is to run a test with an increasing set of training data, evaluating the result as you go along. Obviously, with a small set (eg 3 sentences per class), it will be very poor, but the accuracy should quickly increase and then stabilise at a higher level. With larger amounts of data you will probably only find a small increase or no change at all.

Collecting this data would not only give you confidence in your conclusion, it would also be a good supporting argument when you have to ask for more training data, or have to justify the poor performance of the classifier if you do find the data set is too small.

So, set up an automated 10-fold cross validation, feed an increasing amount of your available data into it, sit back, and graph the results.


Why doesn't the set $\{ -2, +2 \}$ in $E(X) = (y − \text{sign}\{\overline{W} \cdot \overline{X} \}) \in \{ −2, +2 \}$ include $0$?

It is important to note that the exact statement is the eqation given below can never be 0 for misclassified points in $ S^+$
$$ E(X) = (y - \text{sign}\{\overline{W} \cdot \overline{X}\}) $$
And $S+$ is defined as the set of all misclassified training points $X \in S$ that satisfy the condition $y(\overline{W} \cdot \overline{X})<0 $ which means that $y$ and $ (\overline{W} \cdot \overline{X}) $ will have different signs i.e if $y < 0$ then $(\overline{W} \cdot \overline{X}) > 0$ and vice versa.
Finally the condition on $S^+$ constraints the the $ E(X)$ to these values when $ y < 0$ and $(\overline{W} \cdot \overline{X}) > 0$
$$ E(X) = (-1 - \text{sign}(+ve)) = -2 $$
or when $ y > 0$ and $(\overline{W} \cdot \overline{X}) < 0$
$$ E(X) = (1 - \text{sign}(-ve)) = 2 $$


How do I find whether this heuristic is or not admissible and consistent?

Welcome to AI.SE @hpr16!

Your understanding of when a heuristic is admissible is correct, but your heuristic is inadmissible. An admissible heuristic must always underestimate the cost to move from a given state to a goal state.

Notice that states in the search are not the same as positions on the circle in your problem. A state needs to capture all the information about the current environment the agent is in. In your problem, agents have a speed as well as a position. A state must, therefore, contain both.

To see why your heuristic is inadmissible because the agent can move (n-z) segments in less than n-z steps: it can speed up, and do them in, for example, (n-z)/2 steps, by moving with speed 2.


How to create an AI to solve a word search?

This sounds like a problem that might be solvable with a LSTM-DQN approach, as described in Language Understanding for Text-based Games using Deep
Reinforcement Learning by Narasimhan et al., 2015, and then extended to a domain very similar to your problem in Deep Reinforcement Learning for Syntactic Error Repair in Student Programs by Gupta et al., 2019.

The basic idea is to treat the array of letters each of which can be 'circled' or not, plus the position of a cursor as a state. An action is to move the cursor or toggle the state of a letter. You then model the problem as a reinforcement learning problem, with rewards given every time an entire new word becomes 'circled', probably with a caveat about not circling any invalid letters (otherwise, it'll just learn to circle everything).

This is just a guess, but it seems like it's very closely related to your problem, so it's likely to be effective.


Why can't we fully exploit the environment after the first episode in Q-learning?

BlueTurtle's answer is good, but I'd like to add something.
Your question realistically has nothing to do with Q Learning, in fact, you can ask the same thing about just about any RL algorithm. In fact, even in multi-armed bandits, you can easily see why your proposed method is suboptimal (please don't interpret this as a criticism, because I think your question is a very natural one). My suggestion to you is to read up on multi-armed bandits since they're much simpler to analyze. I think even the Sutton and Barto book deals with your proposed method explicitly, and mathematically proves that other strategies are better.


Is the temperature equal to epsilon in Reinforcement Learning?

Your are correct that epsilon in epsilon-greedy and temperature parameter in the "softmax distribution" are different parameters, although they serve a similar purpose. The original author of the code has taken a small liberty with variable names in the select_action method in order to use just one simple name as a positional argument.

  Should the temperature be a fixed value over time?

Not necessarily, if your goal is to converge on an optimal policy you will want to decrease temperature. A slow decay factor applied after each update or episode, as you might use for epsilon (e.g. 0.999 or other value close to 1), can also work for temperature decay. A very high temperature is roughly equivalent to epsilon of 1. As temperature becomes lower, differences in action value estimates become major differences in action selection probabilities, with a sometimes desirable effect of picking "promising" action choices more often, plus with very low probabilities of picking the actions with the worst estimates.

Using a more sophisticated action selection such as the temperature based on in the example code can speed learning in RL. However, this particular approach is only good in some cases - it is a bit fiddly to tune, and can simply not work at all.

The tricky part of using a temperature parameter is choosing good starting point, as well as the decay rate and end values (you have to do the last for epsilon-decay as well). The problem is that the impact of using this distribution depends on the actual differences between action choices. You need a temperature value on roughly the same scale as the Q value differences. This is difficult to figure out in advance. In addition, if the Q value differences are more pronounced in some states than in others, you risk either having next to no exploration or having too much in some parts of the problem.


Learning policy where action involves discrete and continuous parameters

There is a recent paper: Continuous-Discrete Reinforcement Learning for
Hybrid Control in Robotics published by DeepMind that aims to solve this problem, as stated in the abstract:

  Many real-world control problems involve both discrete decision variables – such as the choice of control modes, gear switching or digital outputs – as
  well as continuous decision variables – such as velocity setpoints, control gains or
  analogue outputs. However, when defining the corresponding optimal control or reinforcement learning problem, it is commonly approximated with fully continuous
  or fully discrete action spaces. These simplifications aim at tailoring the problem
  to a particular algorithm or solver which may only support one type of action
  space. Alternatively, expert heuristics are used to remove discrete actions from
  an otherwise continuous space. In contrast, we propose to treat hybrid problems
  in their ‘native’ form by solving them with hybrid reinforcement learning, which
  optimizes for discrete and continuous actions simultaneously.

The idea is that they use a hybrid policy that uses a Gaussian distribution for the continuous decision variables and a categorical distribution for the discrete decision variables. Then, they extend the Maximum a Posteriori Policy Optimisation (MPO) algorithm (also by DeepMind) to allow it to handle hybrid policies.

Here is a video showing how they used the resulting hybrid MPO policy in a robotics task, where in addition to the continuous actions, the robot can choose a discrete action which is the control mode to be used (coarse vs. fine).


How powerful a computer is required to simulate the human brain?

H+ magazine wrote an estimate in 2009 that seems broadly comparable to other things I've seen; they think the human brain is approximately 37 petaflops. A supercomputer larger than that 37 petaflop estimate exists today.

But emulation is hard. See this SO question about hardware emulation or this article on emulating the SNES, in which they require 140 times the processing power of the SNES chip to get it right. This 2013 article claims that a second of human brain activity took 40 minutes to emulate on a 10 petaflop computer (a 2400-times slowdown, not the 4-times slowdown one might naively expect).

And all this assumes that neurons are relatively simple objects! It could be that the amount of math we have to do to model a single neuron is actually much more than the flops estimate above. Or it could be the case that dramatic simplifications can be made, and if we knew what the brain was actually trying to accomplish we could do it much more cleanly and simply. (One advantage that ANNs have, for example, is that they are doing computations with much more precision than we expect biological neurons to have. But this means emulation is harder, not easier, while replacement is easier.)


Is the following neural network architecture considered deep learning?

"Deep learning" is not formally defined. However, typically even simple RNNs are taught as advanced neural network subject alongside other topics labelled "deep learning".

Technically, given the time dimension, the depth of a RNN can include many layers of processing (as opposed to many layers of parameters). As such, some of the knowledge and experience used to help with deep feed-forward networks also applies to RNNs. You could consider the LSTM architecture one such thing, because it is designed to address the vanishing gradient problem that plagues simpler RNN architectures.

So, yes you can call your model a "deep learning model" and have that generally accepted.

I'd be slightly concerned if anyone important to the success of a project thought that label was a big deal - either placed on your CV as or as a buzzword on a resulting product. However, it is not unrealistic marketing  because it is essentially true.


If two perfect chess AI's played each other, would it always be a stalemate or would white win for an inherent first-move advantage?

This relates to the concept of "solved games". In general, two player turn-based games with perfect information - of which chess is an example - can result in all three possible outcomes: a forced win for white, a forced win for black, or a forced draw.

The short, although unsatisfactory answer is that chess is not solved, and it is not clear whether it can be. There is generally thought to be an advantage to white for the first move, so likely results are considered to be a forced win for white, or a forced draw.

No current AI attempts to "solve" chess, although some of the techniques such as MCTS might be adapted theoretically to find a solution, the available computing power to run that search to completion from the start positions is too low by a few orders of magnitude.


What are the connections between ethics and artificial intelligence?

This is a good related read from Nature: There is a Blind Spot in AI Research

  Fears about the future impacts of Artificial Intelligence are distracting researchers from the real risks of deployed systems


What is meant by "known" in "A knowledge-base exhibits complete knowledge if and only if, for every $P$, $P$ or $\neg P$ is known"?

It seems that they are stating that a knowledge base is consistent if and only if it never asserts the truth of both the truth and the negation of a particular P. In other words, a knowledge base is consistent if it never contradicts itself. Their definition allows incomplete knowledge bases to be considered consistent; by their definition, an empty knowledge base is still considered a consistent one.


What is the best measure against overfitting?

tl;dr
The safest method I've found is to use cross-validation for hyperparameter selection and a hold-out test set for a final evaluation.
Why this isn't working for you...
In your case, I suspect you're either running a large number of iterations during for hyperparameter selection or you have a fairly small dataset (or even a combination of both). If you can't find more data or use a larger dataset, I'd suggest limiting the exhaustiveness of your hyperparameter selection phase. If you run the process enough times the model is bound to overfit on the validation sets.
Note that there is no guaranteed safe way of detecting overfitting before the test set!
Why I consider this strategy to be the safest
There are two different types of overfitting you need to be able to detect.
The first is the most straightforward: overfitting on the training set. This means that the model has memorized the training set and can't generalize beyond that. If the test set even slightly differs from the training set (which is the case in most real-world problems), then the model will perform worse on it than on the training set. This is simple to detect and, in fact, the only thing you need to catch this is a test set!
The second type of overfitting you need to detect is on the test set. Imagine you have a model and you make an exhaustive hyperparameter selection using a test set. The you evaluate on the same test set. By doing this, you have adjusted your hyperparameters to achieve the best score for the specific test set. These hyperparameters are thus overfit to that test set even though the samples from that set were never seen during training. This is possible because during the iterative hyperparameter selection process, you have passed information about your test set to your model!
This is much harder to detect. In fact the only way to do so is to split the original data into three parts: the training, the validation and the test sets. The first is used for training the model, the second for hyperparameter selection and the final is used only once for a final evaluation. If your model has overfit (i.e. test performance is worse than training and validation) you need to start from scratch. Shuffle your data, split it again and repeat the process. This is usually referred to as a hold-out strategy.
To make the model even less prone to overfitting, you can use cross-validation instead of a hold-out validation set. Because your model now has to be trained on $k$ slightly different training sets and evaluated on $k$ completely different validation sets, it is much harder for it to overfit on the validation sets (because it needs to fool $k$ different validation sets instead of one).
Cases where this might not be applicable
Depending on the circumstances, it might not be practical to apply both of these techniques.

Cross-validation is pretty robust regarding overfitting but it imposes a computational burden to your process as it requires multiple trainings of the same model. This obviously isn't practical for computationally expensive models (e.g. image classifiers). In this case use a hold-out strategy as mentioned previously.

Using a hold-out test set means that you are reducing the size of your training set, which might actually make your model more prone to overfitting (i.e. have a higher-variance) for small datasets. In this case (if your model is practically untrainable due to the small size) you can resort to cross-validation, but you risk overfitting on the validation set and not having any way to detect it.

How to combat overfitting
Since it is fairly related I'll post a link to an answer on how to combat overfitting.


Thanks for everyone's help. I have now solved the problem. I hadn't quite understood the back propagation algorithm. I invite people to take a look at this link: backpropagation @ AGH UST which has solved my problem.

Code:

clear
pkg load image
graphics_toolkit("gnuplot")
tic
sigmoid = @(z) 1./(1 + exp(-z));
sig_der = @(y) sigmoid(y).*(1-sigmoid(y));

function [cost, mid_layer, last_layer] = forward(w1,w2,data,sigmoid,i)
  mid_layer(:,1)=sum(w1.*data(1:2,i));
  mid_layer(:,2)=sigmoid(mid_layer(:,1));
  last_layer(:,1)=sum(mid_layer(:,2).*w2);
  last_layer(:,2)=sigmoid(last_layer(:,1));
  cost = data(3,i)-last_layer(:,2);
end

function [w1, w2] = backprop(w1,w2,mid_layer,last_layer,data,cost,sig_der,sigmoid,i)
  delta(1) = cost;
  delta(2:4) = cost .* w2;
  w2 = w2 + 0.99 .* delta(1) .* mid_layer(:,2) .* sig_der(last_layer(:,1));
  w1 = w1 + 0.99 .* delta(2:4) .* sig_der(mid_layer(:,1))' .* data(1:2,i);
  %b2 = b2 + 0.01 .*
  %b1 = b1 + 0.01 .*
end

tic

data(:,1)=[0; 0; 0];
data(:,2)=[1; 0; 1];
data(:,3)=[0; 1; 1];
data(:,4)=[1; 1; 0];

w1=rand(2,3)./2.*(rand(2,3).*-2+1);
w2=rand(3,1)./2.*(rand(3,1).*-2+1);
%b1=ones(1,3);%rand(1,3)./2;
%b2=ones(1,1);%rand(1,1)./2;

for j=1:10000
  for i=[randperm(4)]
    [cost, mid_layer, last_layer] = forward(w1,w2,data,sigmoid,i);
    [w1, w2] = backprop(w1,w2,mid_layer,last_layer,data,cost,sig_der,sigmoid,i);
    cost_mem(j,i)=cost;
  end
end

toc

%{
dlmwrite("/tmp/weights_1",w1);
dlmwrite("/tmp/weights_2",w2);
%}