Are commercially available neural ICs digital? Apparently, one can buy a special-purpose integrated circuit (an IC like this one, for instance) to host a convolutional neural network.

QUESTION

Is such a circuit digital? Except for digital random-number generation, is the circuit's behavior deterministic?

What kind of hardware is this?

REFERENCE

Already asked and answered: "If digital values are mere estimates, why not return to analog for AI?"

FURTHER DETAILS

What I mean is this: suppose that you and I each acquired a special-purpose neural IC, same make, same model. Suppose that you and I configured and trained our circuits alike. Except for digital random-number generation, would our neural nets behave identically? Or would analog effects cause our nets to turn oppositely on some closely balanced edge case?

If it is plain to you that a misconception has caused me to pose the question improperly, then a correction to the question along with an answer would be appreciated.

If you wish to know my background, I am an electrical power engineer in my 50s.

Intel's Movidius uses digital circuitry for signal paths.   It is a parallel processing VLSI chip that can host a sequence of convolution layers and other types of parallel operations, just as CUDA cores in NVidia products do.  These all are extensions of the idea of DSPs (digital signal processors).  They are adept as front ends to real time vision systems in robots and vehicle automation.  They are also stuffed into racks and used for massively parallel operations in data centers, leveraged for large batch or mini-batch jobs related to indexing or supporting transaction based services.

There are three broad signal theory characteristics referenced conceptually in this question which may benefit from some disambiguation.

Analog versus digital
Deterministic versus stochastic
Predictable versus unpredictable outcome

Of the eight permutations, any of these five can be realized or reasonably accurately approximated.  Under what conditions they are repeatable is in parentheses.

Analog, deterministic, predictable outcome — Yes, within the bounds of specifications such as signal to noise ratio
Analog, deterministic, unpredictable outcome — Usually no
Analog, stochastic, unpredictable — No
Digital, deterministic, predictable outcome — Yes
Digital, stochastic, unpredictable — No

The commercially available ICs used for artificial neural networks mentioned above are digital, but they may not be deterministic.  For instance, the seed of random number generators can be the system time.  When embedded into larger computing systems entropy can also be collected digitally from mouse movement, microphones, camera frames, or secure network sources and then used in the digital signal processing algorithms, including artificial network ones.

Future chips may actually return to analog processing for some of the workload.  The accuracy of digital circuitry may be worth sacrificing in exchange for increase complexity and throughput per unit area on the VLSI substrate.  The storage and retrieval advantage of flip flops and other digital structures can still be maintained by interfacing the storage to the forward signal paths with A-to-D and D-to-A conversion. It is difficult to predict whether the trade-off will gain traction and, if so, when.

The term, "Balanced edge case," references what mathematicians familiar with chaos theory sometimes call initial input sensitivity, colloquially known as, "The Butterfly Effect."  Chaos can occur in nature where the only discrete operations are at the quantum level.  Chaos can also occur in digital systems with no greater mathematical complexity than the Logistic Equation: $x_{t+1} = r \, x_t (1 - x_t)$, where interesting behavior is observed for values of $r > 2.0$.

In electrical power engineering, much of what appears on an oscilloscope in triphase circuits are not sine waves but chaos that exhibits a strong peak in the power spectrum at 50 or 60 Hertz.


What is the difference between a language model and a word embedding? I am self-studying applications of deep learning on the NLP and machine translation.
I am confused about the concepts of "Language Model", "Word Embedding", "BLEU Score".
It appears to me that a language model is a way to predict the next word given its previous word. Word2vec is the similarity between two tokens. BLEU score is a way to measure the effectiveness of the language model.
Is my understanding correct? If not, can someone please point me to the right articles, paper, or any other online resources?

Simplified: Word Embeddings does not consider context, Language Models does.
For e.g Word2Vec, GloVe, or fastText, there exists one fixed vector per word.
Think of the following two sentences:

The fish ate the cat.

and

The cat ate the fish.

If you averaged their word embeddings, they would have the same vector, but, in reality, their meaning (semantic) is very different.
Then the concept of contextualized word embeddings arose with language models that do consider the context, and give different embeddings depending on the context.
Both word embeddings (e.g Word2Vec) and language models (e.g BERT) are ways of representing text, where language models capture more information and are considered state-of-the-art for representing natural language in a vectorized format.
BLEU score is an algorithm for evaluating the quality of text which has been machine-translated from one natural language to another. Which is not directly related to the difference between traditional word embeddings and contextualized word embeddings (aka language models).


Is it a good idea to use BERT to answer a FAQ with semantic similarity? I have been looking for BERT for many tasks. I would like to compare the performance to answer an FAQ, using BERT semantic similarity and BERT Q/A.
However, I'm not sure it is a good idea to use semantic similarity for this task. If it is, do you think it is possible to find a dataset to fine-tune my algorithm?

Maybe the following article can help you:

FAQ Retrieval using Query-Question Similarity and BERT-Based Query-Answer Relevance (2019)

They evaluate their model in localgovFAQ and StackExchange datasets.


What is the internal state of a Simple Neural Attentive Meta-Learner(SNAIL)? In the paper A Simple Neural Attentive Meta-Learner, the authors mentioned right before Section 3.1:

  we preserve the internal state of a SNAIL across episode boundaries, which allows it to have memory that spans multiple episodes. The
  observations also contain a binary input that indicates episode termination.

As far as I can understand, SNAIL uses temporal convolutions to aggregate contextual information, from which causal attention learns to distill specific pieces of information. Temporal convolutions does not seems to maintain any internal state, and neither does the attention mechanism they use after this paper. This makes me wonder: "What is the internal state of a SNAIL?"

Here's what I understand, welcome to point out any mistakes.

When starting a new episode(but still in the same task), SNAIL does not clear its batches. Instead, it makes decisions based on the current observation and observation-action pairs from the previous episode. In this way, it keeps knowledge of the previous episode whereby achieving few-shot learning in the test time.


How can a neural network approximate all functions when the weights are not allowed to grow exponentially? It has been proven in the paper "Approximation by Superpositions of a Sigmoidal Function" (by Cybenko, in 1989) that neural networks are universal function approximators.  I have a related question.

Assume the neural network's input and output vectors are of the same dimension $n$. Consider the set of binary-valued functions from $\{ 0,1 \}^n$ to $\{ 0,1 \}^n$.  There are $(2^n)^{(2^n)}$ such functions. The number of parameters in a (deep) neural network is much smaller than the above number.  Assume the network has $L$ layers, each layer is $n \times n$ fully-connected, then the total number of weights is $L \cdot n^2$.

If the number of weights is not allowed to grow exponentially as $n$, can a deep neural network approximate all the binary-valued functions of size $n$?

Cybenko's proof seems to be based on the denseness of the function space of neural network functions.  But this denseness does not seem to guarantee that a neural network function exists when the number of weights are polynomially bounded.

I have a theory. If we replace the activation function of an ANN with a polynomial, say cubic one，then after $L$ layers, the composite polynomial function would have degree $3^L$.  In other words, the degree of the total network grows exponentially. In other words, its "complexity" measured by the number of zero-crossings, grows exponentially. This seems to remain true if the activation function is sigmoid, but it involves the calculation of the "topological degree" (a.k.a. mapping degree theory), which I have not the time to do yet.

According to my above theory, the VC dimension (roughly analogous to the zero-crossings) grows exponentially as we add layers to the ANN, but it cannot catch up with the doubly exponential growth of Boolean functions. So the ANN can only represent a fraction of all possible Boolean functions, and this fraction even diminishes exponentially. That's my current conjecture.

What is Proven
The question references the proof of Approximation by Superpositions of a Sigmoidal Function, G. Cybenko, 1989, Mathematics of Control, Signals, and Systems.
The 1989 proof stated that the network, made of activations that were required to be, "Of continuous sigmoidal non-linearity," could, "Uniformly approximate any continuous function of n real variables," so, as the question stated, the proof doesn't directly apply to 1-bit discrete outputs.  Note that the network is expected to merely approximate the desired circuit behavior.
The question defines the system as an arbitrary mapping from input bit vector

$I: { i_1, \; \dots, \; i_n}$

to output bit vector

$O: { o_1, \; \dots, \; o_n}$

It was further back proven that such a mapping can be accomplished with one Boolean expressions for each output bit.  For all $2^n$ possible input vector permutations, there exists a Boolean expression made up of AND and NOT operations that calculates a result that matches any arbitrary logical truth table.
There are techniques for reducing redundancy in the array of Boolean expressions, which is critical to VLSI chip layout.
Without the retention of state anywhere in the network other than the attenuation matrix (parameters), the system is not Turing complete.  However, with regard to the ability to realize Boolean expressions in describing the mapping, given an arbitrary number of layers, the network is complete.
Estimating Layer Depth Requirements
Only one inner layer is required in the 1989 proof, so how many layers would it take for an accurate n-bit-to-n-bit mapping to be learned?
The question proposes that there are $2^n$ to the power of $2^n$ permutations.  The mapping of each input bit vector to the desired output bit state can be represented by a truth table of $n$ binary dimensions.
Each output is an independent bit, meaning the $2^n$-bit representations of unique Boolean functions that could produce each output bit is not tied to any other output channel.  As would be expected, there are $2n$ freedoms of motion for the mapping of I to O.
For the case where the input is a bit vector of $n$ bits, where $n$ is the number of activations for any one of $L$ layers, the total number of activations in the network $a_t$ and the total number of scalar elements for all attenuation matrices (the parameters that represent training state) $q_t$ for the network is as follows.

$a_t = \sum_{\, 0 = v}^{L - 1} \; n_v$

$= n \, L$

$p_t = \sum_{\, 0 = v}^{L - 2} \; n_v^2$

$= n^2 \, (L-1)$

If IEEE 64 bit floating point numbers are used for each element in the attenuation matrix, we can calculate the number of bits available in the training parametrization.

$b_t = 64 \, (L - 1) \, n^2$

It would be normal today to use ReLU, leaky ReLU, or some other more quickly convergent activation instead of sigmoid for all layers but the last and use a simple binary threshold for the last.
Thus we have a formulation of the information theory comparison inferred by the question, and can reduce it.

$2^{2n} \le 64 \, (L - 1) \, n^2$
$L \ge 1 + \frac {2^{2n-6}} {n^2}$

This is a rough threshold.  For a highly reliable training for the binary inputs to binary outputs, the number of layers should be well above the threshold.
Below the threshold the trainability of the mapping will degrade to an inadequate approximation for most applications because of signal saturation in the back propagation mechanism.


Is it possible to build an AGI with neural networks on neuromorphic chips? I read a lot about the structure of the human brain and artificial neural networks.
Is it possible to build an AGI (or human-level AI) with artificial neural networks on neuromorphic chips, which would be divided into centers, like the brain is, e.g. centers responsible for feelings, abstract thinking, speech, memory, etc.?

No. The reasons include but are not limited to:

lack of understanding of how the brain works

current ANNs are mostly good at pattern recognition and generative   tasks, but lack the capacity to create abstractions on their own

we can't match the size/number of artificial neurons to the number of biological neurons

even with a much smaller ANN size, performance is an issue (i.e. state of the art image categorization ANNs have to be trained few weeks on multi GPU rigs to match human level).


Why do we need both encoder and decoder in sequence to sequence prediction? Why do we need both encoder and decoder in sequence to sequence prediction?

We could just have a single RNN that, given input $x$, outputs some value $y(t)$ and hidden state $h(t)$. Next, given $h(t)$ and $y(t)$, the next output $y(t+1)$ and hidden state $h(t+1)$ should be produced, and so on. The architecture shall consists of only one network instead of two separate ones.

(Old question, I know...)

It is not that we need both an encoder and decoder for sequence-to-sequence models - this decoupling of "reading" and "generating" just works better very often.

Example for Sequence-to-sequence without two RNNs

To prove my point above, here is an example from machine translation. Current machine translation systems are sequence-to-sequence models, and virtually all models have the bipartite structure of encoder and decoder.

Approaches like Eager Translation break this implied convention. They learn translation models that do not encode and decode with separate RNNs, but at every time step 1) read a source token and 2) produce a target token - with a single RNN.

Why encoder-decoder works better very often

Sequence-to-sequence modeling with encoder-decoder structure almost always implies attention in-between encoder and decoder. Attention relays information between the encoder and decoder, in the sense that every time the decoder has to generate the next item in the target sequence, an attention network computes a dynamic, useful "summary" of all encoder states.

This attention summary is different and recomputed for every decoding step. On the other hand, encoding the source sequence is done only once and then all encoder states are kept in memory.

The ability to have a direct view of the source sequence (using as a proxy the entire sequence of encoder states) via attention is what makes the encoder-decoder approach superioir to a single RNN.

In comparison, a single RNN only has a direct view on one element of the input sequence. Some interesting scenarios for a single RNN:

At every time step, read one source token, then write one target token: Previous elements in the source sequence are represented only in lossy recurrent states, while future elements cannot be accessed at all.
First read all source tokens, then write all target tokens.: the meaning of the entire source sentence has to be compressed into a fixed-size recurrent state vector.


Can supervised learning be used to solve the inverted pendulum problem? I know that reinforcement learning has been used to solve the inverted pendulum problem.

Can supervised learning be used to solve the inverted pendulum problem?

For example, there could be an interface (e.g. a joystick) with the cart-pole system, which the human can use to balance the pole and, at the same time, collect a dataset for supervised learning. Has this been done before?

Of course, you can, and yes this has been researched and done before. By using supervised learning, you give the machine some data, and it will try to figure the best way to analyze and predict the next movement in case of an inverted pendulum problem.
I found a complete paper for this problem: Neural network control of an inverted pendulum on a cart by Valeri Mladenov et al.


How to reproduce neural network training with keras I want to see the effects of changing some training parameters (batch size, learning rate, optimizer...) to the accuracy obtained.
The problem is that with the same parameters I get significantlly different results (up to 5%).

I load the same weights before training and I deactivated the shuffle. To my understanding this should be enough to get the same results. The only randomness of the backpropagation comes from the initial weight values, right? What am I missing?

This is how I compiled the model:

model.compile(loss="categorical_crossentropy",
              optimizer=keras.optimizers.SGD(lr=0.1, decay=1e-6),
              metrics=['accuracy'])

And this is the code that I repeat:

model.load_weights("./saved_weights.h5", by_name=False)

model.fit(x_train, y_train,
          batch_size=32,
          epochs=1,
          initial_epoch=0,
          validation_data=(x_test, y_test),
          shuffle=False)

I'm using tensorflow 2.0 as a backend in a colabs's CPU.

As @codeblooded said, you should set random seed for numpy and keras, and also set pythonhashseed. The seeds set the state of the random number generator which makes the results different.

This method only works when you train the network on CPU. The problem with getting same result on GPU every single time is that cuDNN is not deterministic. Specifically, the reduce_sum() function in tensorflow is known to have different results even if a random seed is set. You can see this for more details. But simply said, reduce sum is not deterministic in tensorflow, but however it is used in bias gradient calculation. This can be avoided by using matmul in place of reduce sum, and you can see the implementation in the article mentioned.

To get reproducible results, you can try using different framework, like pytorch. I have done experiments on pytorch and it seems to be reproducible. See this colab notebook. All you need to do is add a couple lines to the code. Theano based keras seems to work as well but I haven't tested it.

However for hyperparameter testing and searching 0.3% should not affect the result, and if you really want very accurate result, average the accuracy of 30 or more tries to get an accurate result. If you do this you don't need to set the random seed.


Why is informed search more efficient than uninformed search? Why does informed search more efficiently finds a solution than an uninformed search?

There are several informed and uninformed search algorithms. They do not all have the same time and space complexity (which also depends on the specific implementation). I could come up with an informed search algorithm that is highly inefficient in terms of time or space complexity. So, in general, informed search algorithm are not more efficient than uninformed ones, in terms of space and time complexity.

However, given that informed search algorithms use "domain knowledge" (that is, an heuristic function that estimates the distance to the goal nodes), in practice, they tend to find the goal node more rapidly, given a more informed "heuristic" (which needs to be admissible in order to find the optimal solution). For example, in theory, A* has exponential time and space complexities (with respect to the branching factor and the depth of the tree), but, in practice, it tends to perform decently well. It tends to have an effective branching factor (that is, the branching factor for specific problem instances) quite "small" (for several problems).

What is a more informed heuristic? Intuitively, it is an heuristic that more rapidly focuses on the promising parts of the search space. Let's denoted by $h$ the heuristic function. If $h(n)=0$, for all nodes $n$, then this is an admissible heuristic, because it always underestimates the distance to the goal (that is, it always returns $0$). However, it is a quite uninformed heuristic: either if you are at the start or goal nodes, the estimation is always the same (so you cannot distinguish the start and goal nodes, in terms of estimates). Given two admissible heuristics $h_1$ and $h_2$, $h_2$ is more informed than $h_1$ if $h_1(n) \leq h_2(n)$, for all nodes $n$.

An uninformed search algorithm performs an exhaustive search. There are several ways of performing such exhaustive search (e.g. breadth-first or depth-first), which are more efficient than others (depending on the search space or problem). Given that they perform an exhaustive search, they tend to explore "uninteresting" parts of the search space. Hence, in practice, they might be more inefficient than informed search algorithms (that is, they might require more time to find the solution).


Predict frequently purchased items under certain conditions with customer purchasing history data I have purchasing history data for grocery shopping. I am trying to get abnormally frequently purchased items under certain conditions. For instance, I am trying to find frequently purchased items, when customers shop online and are willing to pay an extra shipping fee.

In order to find items that are particularly (or abnormally) frequently purchased under that situation (through online stores by paying shipping fee), how and what Machine Learning Algorithm  should I apply and identify those items?

I found arules R package which is using the association rules with purchasing history and tried to apply it. But it seems the package might be based on different principle from my idea.

Anyone has an idea about my problem? If there is an R package related to the problem, it would be perfect.

Let start by the concrete question, and follow talking about the general problem.

a)

The concrete question "find items that are particularly frequently purchased through online stores by paying shipping fee" needs few or none usage of applied AI, just a few of statistics.

The question talks about "item purchased" and "buy method", thus, we have an information database with entries like:

  sale(online,item1).

  sale(shop,item2).

  sale(online,item2).

  sale(online,item2).

  ...

(note records can be repeated)

the percentage of online sales of item "X" is defined as the fraction of sales online of this item, sale(online,X), over the total sales of this item, sale(_,X):

In the previous data examples, p(item1)=1/1, p(item2)=2/3.

High p(X) means items that are preferred for online shopping.

Other probabilities can be defined for similar cases.

b)

About the general case, we are talking about data mining. The are very good packages (open source, ...) for them: weka, IBM DWE, ... . By example, using Weka J48 over a database defined as:

  sale( purchase_identifier, buy method, item )

where "purchase_identifier" must group item that has been purchased in a single buyout (cash ticket). J48 will then provide as answer rules as: item "foo" is usually purchased in online shop when also item "bar" is purchased.


Can autoencoders be used for supervised learning? Can autoencoders be used for supervised learning without adding an output layer? Can we simply feed it with a concatenated input-output vector for training, and reconstruct the output part from the input part when doing inference? The output part would be treated as missing values during inference and some imputation would be applied.

One such paper I know of and which I implemented is Semi-Supervised Learning using Ladder Networks . I quote here their description of the model:

  Our approach follows Valpola (2015), who proposed a Ladder network where the auxiliary task is
  to denoise representations at every level of the model.  The model structure is an autoencoder with
  skip connections from the encoder to decoder and the learning task is similar to that in denoising
  autoencoders but applied to every layer, not just the inputs. The skip connections relieve the pressure
  to represent details in the higher layers of the model because,  through the skip connections, the decoder can recover any details discarded by the encoder.

For further explanations on the architecture check Deconstructing the Ladder Network Architecture by Yoshua Bengio.


Genetic Algorithms: Trade-off between time and variance with regards to fitness function I'm developing an AI to play a card game with a genetic algorithm.  Initially, I will evaluate it against a player that plays randomly, so there will naturally be a lot of variance in the results.  I will take the mean score from X games as that agents fitness. The actual playing of the game dominates the time to evaluate the actual genetic algorithm.

My question is should I go for a low X e.g. 10, so I would be able to move through generations quite fast but the fitness function would quite inaccurate.  Alternatively, I could go for a high X e.g. 100 and would move very slowly but with a more accurate function.

You can probably get away with a relatively low X for two reasons:

The Central Limit Theorem. This tells us that the accuracy in the estimate of an agent's fitness will improve as the square root of the number of games played.
In a GA, you don't need an absolute ranking of individuals, because your selection mechanism (see "related articles" here) typically isn't completely elitist. For example, if individuals in the top half of the population are allowed to breed, then your fitness function really just needs to separate the good from the bad reasonably well. It need not be perfect to work.

The correct value of X will still depend on the variance in the scores an agent might receive from playing the game, but this is easy to track. A good approach might be to incorporate this directly into your estimate. Compute the variance, and then prefer agents that not only score highly, but do so with low variance.


Why L1/L2 regularization technique did not improve my accuracy? I am training a Multilayer Neural Nets with 146 samples (97 for training set, 20 for validation set and 29 for testing set). I am using:
automatic differentiation,
SGD method,
fixed learning rate + momentum term,
logistic function,
quadratic cost function,
L1 and L2 regularization technique,
adding some artificial noise 3%.

When I used L1 or L2 regularization technique my problem (overfitting problem) got worst.
i tried different values for lambdas (the penalty parameter  0.0001, 0.001, 0.01, 0.1, 1.0 and 5.0). After 0.1 i just killed my ANN. The best result that i took it was using 0.001 (but it is worst comparing the one that i didnt use regularization technique). The graph represent the error functions for different penalty parameters and also a case without using L1.

and the accuracy

What can be?
Thanks!!

Regularization is one of the important prerequisites for improving the reliability, speed, and accuracy of convergence, but it is not a solution to every problem.  Irregularity in data is only one of many root causes for slow or otherwise inadequate learning results, and as the results in the question indicates, it can reduce reliability, speed, or accuracy in some cases.

For those who are new to this topic, these are a few other root causes.

Complexity beyond the capacity of the computing machinery to model adequately
Insufficient number of examples for training
Poor distribution alignment between data sets (training, testing, validation, production)
Saturation of back propagation values in floating point
Outliers cause by error in example creation or labeling
Local optimization minima in the loss function combined with insufficient stochastic injection in SGD
Leaning to heavily on artificial network convergence and neglecting using other known algorithms as part of an overall system architecture
Using activation functions or hyper-parameters that are not well tuned to the example set or the model

In the case of regularization, L1 and L2 have known properties that have been proven in theorem form to guarantee convergence in fewer examples or epochs, but they rely on very specific models toward which convergence is targetted.  L1 and L2 are not always beneficial for polynomial models.  Trying to make them so tends to lead to over-fitting.

The resulting trained networks lack the needed generalization to produce reliable behavior upon receiving data outside the training set.  Irregularities might not always be caught during test and verification.  Deployed systems can exhibit the signs of over-fitting over time because the network learned time-specific features.

Overfitting can be prevented using dropout regularization, another technique first proposed in Dropout: A Simple Way to Prevent Neural Networks from Overfitting by Srivastava, et al. 2014.

Another two things to look at ...

Is the logistic function is the best choice and for which layers?  It seems to be down-trending.  More people are using ReLU and its softer varieties because of higher performance shown in a number of problem domains and models.
Is the noise injection clean in that it is a good pseudo noise source and is it configured properly with whatever SGD methods and libraries being used.

I am training a Multilayer Neural Nets with 146 samples (97 for training set, 20 for validation set and 29 for testing set). I am using: automatic differentiation, SGD method, fixed learning rate + momentum term, logistic function, quadratic cost function, L1 and L2 regularization technique, adding some artificial noise 3%.

The question indicated the best results for the current training set and model.

  The best result was obtained using a lambda of 0.001 without regularization.

That's the starting point for improving further.  Since complete automated convergence is not yet something libraries and frameworks provide, the engineer normally has to converge on the combination of techniques and settings that best help the network's convergence.


Recommended Modelling Technique for Influencer Marketing Scenario I have an approximately 90,000 row dataset that has information of social media profiles which has columns for biography, follower count, language spoken, name, username and the label (to identify whether the profile is that of an influencer, brand or news and media).

Task: I have to train a model that predicts the label. I then need to produce a confidence interval for each prediction.

As I have never come across a problem like this, I am just after some suggestions of what models I should be using for a situation like this? I am thinking Natural Language Processing (NLP), but not sure.

Also, for NLP (if a suitable method), any codes or advice to help me implement for the first time on Python would be greatly appreciated! Thanks in advanced

It depends very much on the structure of the data.

I would think about feature extraction first, which could be certain words occurring in the bio, and a class of user name ('real' name, numerical id, etc). Once you have a set of features for each data item, turn them into a list of feature vectors.

Then run them through a number of machine learning algorithms. This is where the shape of the data matters, as some algorithms will work better than others. I would try eg decision trees (ID3), which are very efficient once trained (but they don't give you a confidence interval). But any other ML algorithm might work. They will all have trade-offs with speed of training, memory requirements, and speed of classification; some will give you a class-label probability, others will just give you one label.

The best way would be to use a sample, and identify which algorithm works well and fits your specific requirements. Then use that for the full data set.

Alternatively you could just use, for example, the Stanford ML classifier. That will give you a confidence interval, and will probably work reasonably well.


Is it possible to create a 'logic system' equivalent to humans? I've heard of AI that can solve math problems. Is it possible to create a 'logic system' equivalent to humans that can solve mathematics in the so called 'beautiful' manner?  Can AI find beauty in mathematics and solve problems other than using brute force? Can you please provide with examples where work on this is being done?

There is of course a vast amount of work in the area of Automatic Theorem Proving, but most of it is simply concerned with proof, rather than human notions of beauty, elegance, parsimony etc.

There has however been some work in this general area over the years:

Douglas Lenat's famous AM ('Amateur Mathematician').
Douglas Hofstadter's NUMBO program for number sequence extrapolation.
A range of publications by Simon Colton
Shalosh B. Ekhad, the automated proof assistant for Artificial Combinatorics created by Doron Zeilberg and credited by him as a co-author on numerous papers.


Can't solve Towers of Hanoi in PDDL I'm using PDDL to generate a plan to solve this tower of Hanoi puzzle. I'll give the problem, the rules, the domain and fact sheet for everything.

PDDL is telling me that the goal can be simplified to false; however, I know for a fact that this puzzle is solvable.

Puzzle:

  There are 3 posts. Each has rings on it. From bottom to top on each post. The first post has the
  second largest ring. The second post has the smallest ring, with the second smallest ring on top of it.
  The third post has the third largest ring, with the largest ring stacked on top of it.

Rules:

  The rules of this game are that you may only stack a ring on top of a larger ring. Your goal is to get all of the rings onto the same post, stacked from largest to smallest.

My Code

Domain

(define (domain hanoi)
  (:requirements :strips)
  (:predicates (clear ?x) (on ?x ?y) (smaller ?x ?y))

  (:action move
    :parameters (?disc ?from ?to)
    :precondition (and (smaller ?to ?disc) (on ?disc ?from)
               (clear ?disc) (clear ?to))
    :effect  (and (clear ?from) (on ?disc ?to) (not (on ?disc ?from))
          (not (clear ?to))))
  )

Problem

(define (problem hanoi5)
  (:domain hanoi)
  (:objects peg1 peg2 peg3 d1 d2 d3 d4 d5)
  (:init
    (smaller peg1 d1) (smaller peg1 d2) (smaller peg1 d3)
    (smaller peg1 d4) (smaller peg1 d5)
    (smaller peg2 d1) (smaller peg2 d2) (smaller peg2 d3)
    (smaller peg2 d4) (smaller peg2 d5)
    (smaller peg3 d1) (smaller peg3 d2) (smaller peg3 d3)
    (smaller peg3 d4) (smaller peg3 d5)

    (smaller d2 d1) (smaller d3 d1) (smaller d3 d2) (smaller d4 d1)
    (smaller d4 d2) (smaller d4 d3) (smaller d5 d1) (smaller d5 d2)
    (smaller d5 d3) (smaller d5 d4)

    ;(clear peg2) (clear peg3) (clear d1)
    ;(on d5 peg1) (on d4 d5) (on d3 d4) (on d2 d3) (on d1 d2))
    (clear d2) (clear d4) (clear d1)
    (on d2 peg1) (on d5 peg2) (on d4 d5) (on d3 peg3) (on d1 d3))

  (:goal (and (on d5 d4) (on d4 d3) (on d3 d2) (on d2 d1)))
)

I'm really at a loss here. Thank you!

Ah hah!

The way I had defined the disks made d5 the LARGEST disk, not the smallest. So, the last few lines of the file should be:

   (clear d4) (clear d2) (clear d5)
    (on d4 peg1) (on d1 peg2) (on d2 d1) (on d3 peg3) (on d5 d3))

  (:goal (and (on d1 d2) (on d2 d3) (on d3 d4) (on d4 d5)))
)

However

If I wanted the opposite to be true, d1 to be the largest, the changes would have been as following:

; Swapped ?disc & ?to in (smaller ...) statement
:precondition (and (smaller ?disc ?to) (on ?disc ?from)

And

; Swapped all d* and peg* objs within (smaller ...) staements
(smaller d1 peg1) (smaller d2 peg1) (smaller d3 peg1)
(smaller d4 peg1) (smaller d5 peg1)
(smaller d1 peg2) (smaller d2 peg2) (smaller d3 peg2)
(smaller d4 peg2) (smaller d5 peg2)
(smaller d1 peg3) (smaller d2 peg3) (smaller d3 peg3)
(smaller d4 peg3) (smaller d5 peg3)

:)


How to turn a ternary constraint into three binary constraints? I'm trying to solve problem 6.6 from the book Artificial Intelligence: A Modern Approach, by Peter Norvig and Stuart Russell.
This is in the context of Constraint Satisfaction Problem and how you can re-formulate some problems with the constraints expressed as a bunch of binary constraints to use the generalized solver CSP algorithm.
But I'm stuck with that exercise, I can't sketch a demonstration.

6.6  Show how a single ternary constraint such as "A + B = C" can be turned into three binary constraints by using an auxiliary variable. You may assume finite domains.
(Hint: Consider a new variable that takes on values that are pairs of others values, and consider constraints such as "X is the first element of the pair Y.") Next, show how constraints can be eliminated by altering the domain of variables. This completes the demonstration that any CSP can be transformed into a CSP with only binary constraints.

Let $D_a$ be the domain for A, and $a_i$ the elements of $D_a$.  Let $D_b$ and $D_c$ work similarly for $B$ and $C$ respectively.

We introduce $D_t = \{t | t = (c_i - b_j, c_i)\}$ for all $c_i$ in $D_c$ and $b_j$ in $D_b$.  We can see that $\{t[0]\}$ (i.e. $\{c_i - b_j, \forall i,j\}$) must be equal to $D_a$.

So we can represent the constraint on $A$ by the relation $R_At = { (a_k, t_l) | a_k = t_l[0]}$ for $a_k$ in $D_a$ and $t_l$ in $D_t$.  That is, $a_k$ must equal the first element in the pair from $t_l$, which means there is a $b_j$ and a $c_i$ consistent with that $a_k$.

The constraint on $B$ is the relation $R_{Bt} = \{(b_j, t_l) | b_j + t_l[0] = t_l[1]\}$.  Since $t_l$[0] = $c_i - b_j$, $t_l$[0] + $b_j$ must equal $c_i$, which is t[1], so if this holds, there is a $b_j$ in $D_b$ that is consistent with $t_l$.

Lastly, $R_{Ct} = \{ (c_i, t_l) | c_i = t_l[1]\}$, which is really just an identity.  So what we've done is solved $A + B = C$ for $A$ and encoded that into $R_{At}$.  From that solution and knowledge of the original $C$ (stored in t[1]) we can re-create $C$ from a valid $B$, which is the $R_{Bt}$ relation.

And lastly $C$ must be in the original set of $C$'s used to build all the $t$'s.  If all three of these constraints hold, then we must have a $C$, a $B$ used to solve for $A$, and an $A$ that matches that solution.

The second part is really just path-consistency.  For every $A$, choose a $B$, and see if there's a possible $C = A + B$.  If so, Add that those values to final domains $D_a$, $D_b$, and $D_c$.  I forget if there's a better performing algorithm than this, but I doubt it since here you can use associativity of addition to avoid checking the opposite order of selecting $A$ and $B$.  In general, you have to consider both orders.


How to determine the probability of an "existence" question I am having a go at creating a program that does math like a human. By inventing statements, assigning probabilities to statements (to come back and think more deeply about later). But I'm stuck at the first hurdle.

If it is given the proposition

   ∃x∈ℕ: x==123

So, like a human it might test this proposition for a hundred or so numbers and then assign this proposition as "unlikely to be true". In other words it has concluded that all natural numbers are not equal to 123. Clearly ludicrous!

On the other hand this statement it decides is probably false which is good:

 ∃x∈ℕ: x+3 ≠ 3+x

Any ideas how to get round this hurdle? How does a human "know" for example that all natural numbers are different from the number 456. What makes these two cases different?

I don't want to give it too many axioms. I want it to find out things for itself.

A human has an abstract concept of numbers in mind. So 456 is a unique entity which is by definition unlike any other number because that are other unique entities. If you give ∃x ∈ ℕ: x==123 to your system it could check the property of natural numbers by counting from 0 to 123 to conclude that the statement is true. A human does it in another way. A human would "see" that it is a natural number because it has no decimal point. Because of the concept of natural numbers the statement is immediately clear. To get a faster result here the machine could check just the decimal point.

In your second case you have to apply the commutative property of addition and you are done because the syntax is equal then.

The second problem is more syntactic while the first is semantic. Your machine may "know" the commutative property of addition but not the concept of natural numbers. Therefore, it has to count.


“Outside-in” versus “Inside-out” machine learning A little background... I’ve been on-and-off learning about data science for around a year or so, however, I started thinking about artificial intelligence a few years ago.  I have a cursory understandings of some common concepts but still not much depth.  When I first learned about deep learning, my automatic response was “that’s not how our minds do it.”  Deep learning is obviously an important topic, but I’m trying to think outside the black box.
I think of deep learning as being “outside-in” in that a model has to rely on examples to understand (for lack of a better term) that some dataset is significant.  However, our minds seem to know when something is significant in the absence of any prior knowledge of the thing (i.e., “inside-out”).
Here’s a thing:

I googled “IKEA hardware” to find that.  The point is that you probably don’t know what this is or have any existing mental relationship between the image and anything else, but you can see that it’s something (or two somethings).  I realize there is unsupervised learning, image segmentation, etc., which deal with finding order in unlabeled data, but I think this example illustrates the difference between the way we tend to think about machine learning/AI and how our minds actually work.
More examples:
1)

2)

3)

Let’s say that #1 is a stock chart.  If I were viewing the chart and trying to detect a pattern, I might mentally simplify the chart down to #2.  That is, the chart can be simplified into a horizontal segment and a rising segment.
For #3, let’s say this represents log(x).  Even though it’s not a straight line, someone with no real math background could describe it as an upward slope that it decreasing as the line gets higher.  That is, the line can still be reduced to a small number of simple ideas.
I think this simplification is the key to the gap between how our minds work and what currently exists in AI.  I’m aware of Fourier transforms, polynomial regression, etc., but I think there’s a more general process of finding order in sensory data.  Once we identify something orderly (i.e., something that can’t reasonably be random noise), we label it as a thing and then our mental network establishes relationships between it and other things, higher order concepts, etc.
I’ve been trying to think about how to use decision trees to find pockets of order in data (to no avail yet - I haven’t figured out to apply it to all of the scenarios above), but I’m wondering if there are any other techniques or schools of thought that align with the general theory.

It sounds like you are interested in the ideas of intrinsic motivation and attention in the context of machine learning. These are big topics, and the subject of much active research.

Intrinsic motivation says that the key to identifying interesting patterns and skills that are worth learning is to give the agent some intrinsic reason to learn to do new things. This is not dissimilar from what humans have: learning new things, and improving or exercising our capabilities to the fullest is what Aristotle identified as the good life. There are thus good reasons to think that intrinsic motivation for AI might solve the problem you identify. Current research in this domain is exploring different mathematical ways to represent intrinsic motivation.

Attention was the subject of a large burst of research in deep neural networks during the last few years. Here's a recent talk from AWS at ICML that provides a good overview. The idea here is that an agent can learn both a reasonable mapping from inputs to outputs for some problem, and a separate mapping that describes how different future inputs should "activate" certain parts of the input/output mapping that the agent has learned. Essentially attention-driven models include a second component that learns which features of the input to pay attention to when engaging in certain kinds of tasks.


Is the word "pose" used correctly in the paper "Matrix Capsules with EM Routing"? In traditional computer vision and computer graphics, the pose matrix is a $4 \times 4$ matrix of the form

$$
\begin{bmatrix}
r_{11}  & r_{12}  &  r_{12}   & t_{1} \\
r_{21}  &  r_{22}   & r_{22} &   t_{2} \\
r_{31}   & r_{32}  &  r_{32}  &  t_{3} \\
0   &   0    &  0   &   1
\end{bmatrix}
$$

and is a transformation to change viewpoints from one frame to another.

In the Matrix Capsules with EM Routing paper, they say that the "pose" of various sub-objects of an object are encoded by each capsule lower layer. But from the procedure described in the paper, I understand that the pose matrix they talk about doesn't conform to the definition of the pose matrix. There isn't any restriction on keeping the form of the pose matrix shown above.

So, is it right to use the word "pose" to describe the $4 \times 4$ matrix of each capsule?
Moreover, since the claim is that the capsules learn the pose matrices of the sub-objects of an object, does it mean they learn the viewpoint transformations of the sub-objects, since the pose matrix is actually a transformation?

Great question, and one that I think we could have done a better job of answering in the paper.

Essentially, the pose matrix of each capsule is set up so that it could learn to represent the affine transformation between the object and the viewer, but we are not restricting it to necessarily do that. So we talk about the output of a capsule as though it is an affine transformation matrix, but we can't ensure that it will be. We do things explicitly that make it more like such a matrix — like adding in the coordinates to the right-hand column — but we can't be sure. This somewhat embodies a large part of the capsule network theory — we set up scaffolding so that the network can learn to be equivalent to transformations that we think it ought to be invariant to, but we don't ensure that it is.


What is the name of a human-inspired machine learning approach? I once came across a neural network being trained without back-propagation or genetic algorithms (or using any kind of data sets). It was based on how the human brain learns and adjusts its connections between neurons.

What is the name of such a machine learning approach?

If it was based on how the human brain learns, it might have used hebbian learning.

One example for such a network would be HTM.


Why do we need common sense in AI? Let's consider this example:

  It's John's birthday, let's buy him a kite.

We humans most likely would say the kite is a birthday gift, if asked why it's being bought; and we refer to this reasoning as common sense.

Why do we need this in artificially intelligent agents? I think it could cause a plethora of problems, since a lot of our human errors are caused by these vague assumptions.

Imagine an AI ignoring doing certain things because it assumes it has already been done by someone else (or another AI), using its common sense.

Wouldn't that bring human errors into AI systems?

Commonsense knowledge is the collection of premises that everyone, in a certain context (hence common sense knowledge might be a function of the context), takes for granted. There would exist a lot of miscommunication between a human and an AI if the AI did not possess common sense knowledge. Therefore, commonsense knowledge is fundamental to human-AI interaction.
There are also premises that every human takes for granted independently of the country, culture, or, in general, context. For example, every human (almost since its birth) has a mechanism for reasoning about naive physics, such as space, time, and physical interactions. If an AI does not possess this knowledge, then it cannot perform the tasks that require this knowledge.
Any task that requires a machine to have common sense knowledge (of an average human) is believed to be AI-complete, that is, it requires human-level (or general) intelligence. See section D of AI-Complete, AI-Hard, or AI-Easy – Classification of Problems in AI (2012) by Roman V. Yampolskiy.
Of course, the problems that arise while humans communicate because of different assumptions or premises might also arise between humans and AIs (that possess commonsense knowledge).


After having selected the best model with cross-validation, for how long should I train it? When using k-fold cross-validation in a deep learning problem, after you have computed your hyper-parameters, how do you decide how long to train your final model? My understanding is that, after the hyperparameters are selected, you train your model one more time on the entire set of data, but it's not clear to me when you decide to stop training.

Short answer: training "duration" or number of epochs/updates should be cross-validated too: you want to early-stop your training to prevent overfitting.

Longer answer:

  Think of accuracy on the validation set as an estimate of accuracy on future data, given the value of some hyperparameter. In this case, the hyperparameter of interest is the number of training epochs. So: for each CV fold, train the network (e.g. up to some maximum number of epochs). After each epoch, record accuracy on the validation set. Compute the average validation set accuracy (across CV folds) for each number of epochs. Choose the number of epochs that maximizes this value.

https://stats.stackexchange.com/questions/298084/k-fold-cross-validation-for-choosing-number-of-epochs


In imitation learning, do you simply inject optimal tuples of experience $(s, a, r, s')$ into your experience replay buffer? Due to my RL algorithm having difficulties learning some control actions, I've decided to use imitation learning/apprenticeship learning to guide my RL to perform the optimal actions.  I've read a few articles on the subject and just want to confirm how to implement it.
Do I simply sample a state $s$, then perform the optimal action $a^*$ in that state $s$, calculate the reward for the action $r$, and then observe the next state $s'$, and finally put that into the experience replay?
If this is the case, I am thinking of implementing it as follows:

Initialize the optimal replay buffer $D_O$
Add the optimal tuple of experience $(s, a^*, r, s')$ into the replay buffer $D_O$
Initialize the normal replay buffer $D_N$
During the simulation, initially sample $(s, a^*, r, s')$ only from the optimal replay buffer $D_O$, while populating the normal replay buffer $D_N$ with the simulation results.
As training/learning proceeds, anneal out the use of the optimal replay buffer, and sample only from the normal replay buffer.

Would such an architecture work?

That seems to be functional.
That is a great approach, as long as you are using an off-policy algorithm (since the samples you are using to learn are not the policy currently being performed), like Q-learning.
By annealing the sample rate from the optimal buffer to the regular one, you introduce noise into the network and emphasize exploration (albeit more limited). This is helpful when you (the researcher) have no access to optimal policies, but merely "good" ones, and you still want the network to try and improve on those.


Am I able to visualize the differentiation in backprop as follows? I'm wondering if I can visualize the backprop process as follows (please excuse me if I have written something terrible wrong). If the loss function $L$ on a neural network represents the function has the form
$$L = f(g(h(\dots u(v(\dots))))$$
then we can visualize the derivative of $L$ wrt the $i$th function $v$ as
$$\frac{\partial L}{\partial v} = \frac{\partial f}{\partial g}\frac{\partial g}{\partial h}\dots\frac{\partial u}{\partial v}.$$

Am I able to view all neural networks as having a loss function of the form of $L$ given above? That is, am I correct in saying that any neural network is just a function composition and that I can write the partial derivative wrt any parameter as written above (I know I took the partial with respect to the function $v$).

Thanks

Yes, a neural network plus loss function can be viewed as a function composition as you have written, and back propagation is just the chain function repeated. Your equations $L = f(g(h(\dots u(v(\dots))))$ and $\frac{\partial L}{\partial v} = \frac{\partial f}{\partial g}\frac{\partial g}{\partial h}\dots\frac{\partial u}{\partial v}$ are useful for high level intuition.

At some point you need to look at the actual forms of the functions, and that introduces a bit more complexity. For instance, the loss function for a mini-batch can be expressed in terms of the output. This is the equivalent of $L = f(g)$ for a batch or mini-batch with mean squared error loss, where I am using $J$ (for cost) in place of $L$ and the output of the neural network $\hat{y}$ in place of $g$:

$$J = \frac{1}{2N}\sum_{i=1}^{N}(\hat{y}_i - y_i)^2$$

The gradient of $J$ with respect to $\hat{y}$ is equivalent to your first part $\frac{\partial f}{\partial g}$:

$$\nabla_{\hat{y}} J = \frac{1}{N}\sum_{i=1}^{N}(\hat{y}_i - y_i)$$

Many of the functions in a neural network involve sums over terms. They can be expressed as vector and matrix operations, which can make them look simpler, but you still need to have code somewhere that works through all the elements.

There is one thing that the function composition view does not show well. The gradient you want to calculate is $\nabla_{\theta} J$, where $\theta$ represents all the parameters of the neural network (weights and biases). The parameters in each layer are end points of back propagation - they are not functions of anything else, and the chain rule has to stop with them. That means you have a series of "dead ends" - or possibly another way of thinking about it would be that your $\frac{\partial L}{\partial v} = \frac{\partial f}{\partial g}\frac{\partial g}{\partial h}\dots\frac{\partial u}{\partial v}$ is the "trunk" of the algorithm that links layers together, and every couple of steps there is a "branch" to calculate the gradient of the parameters that you want to change.

More concretely, if you have weight parameters in each layer noted as $W^{(n)}$, and two functions for each layer (the sum over weights times inputs, and an activation function) then your example ends up looking like this progression:

$$\frac{\partial L}{\partial W^{(n)}} = \frac{\partial f}{\partial g}\frac{\partial g}{\partial h}\frac{\partial h}{\partial W^{(n)}}$$

$$\frac{\partial L}{\partial W^{(n-1)}} = \frac{\partial f}{\partial g}\frac{\partial g}{\partial h}\frac{\partial h}{\partial i}\frac{\partial i}{\partial j}  \frac{\partial j}{\partial W^{(n-1)}}$$

$$\frac{\partial L}{\partial W^{(n-2)}} = \frac{\partial f}{\partial g}\frac{\partial g}{\partial h}\frac{\partial h}{\partial i}\frac{\partial i}{\partial j}\frac{\partial j}{\partial k}\frac{\partial k}{\partial l}  \frac{\partial l}{\partial W^{(n-2)}}$$

. . . this is the same idea but showing the goal of calculating $\nabla_{W} L$ which doesn't fit into a single chain of gradients. Notice the last term on each line does not appear in the next line. However, you can keep all the terms prior to that and re-use them in the next line - this matches the layer-by-layer calculations in many implementations of back propagation.


Need examples for the following definitions I am currently reading the paper "Similarity of Narratives" by Loizos Michael (link below) and I am having a hard time figuring out the definitions listed (p.107 - p.109).

Could someone please give me a practical example for each of the definitions?

Article: http://narrative.csail.mit.edu/cmn12/proceedings.pdf

The 'vocabulary' used is:

$\mathscr{F}$ - fluents, conditions that change over time. The predicate holds(<fluent>,<state>) defines whether a condition applies in a given state.
$\mathscr{A}$ - actions, describe, erm, actions that happen. The predicate occurs(<action>,<state>) specifies that a given action happens at a particular state (presumably triggering a change to a new state, and changing the value of one or more fluents)
$\mathscr{T}$ - time points, which specify a chronological ordering.

Now we can look at the actual definitions: a discourse combines events (actions) and facts (fluents) and provides a (partial) ordering, ie a sequence in which they occur. This is represented in an acyclic graph. So the discourse describes a sequence of events that happen in a particular order and have an effect on facts. The ordering is relative, as there are no absolute time reference points give. Actions and facts are expressed in predicate calculus by the predicates mentioned above. Actions can involve a character moving from location A to location B; the fluent describing the location of the character will have been changed through that action.

An embedding assigns a given point in time to each state in the discourse. Each state is assigned a time point in a way that is consistent with the relative timings of the states in the discourse. So you have a general story, and you fix each action in time. The absolute time of an action in the embedding has to be before/after other actions according to their order in the discourse.

A domain adds two further predicates to a discourse, namely static($\phi$) and causes($\phi$,<fluent>). These formulas $\phi$ express logical constraints, that add consistency to the discourse. For example, if an action involves killing a character, the consequence has to be that the character is dead afterwards. So that action mandates a particular change, which would be encoded by such a formula. If the character was then to do some action after having been killed, that would invalidate the discourse in that domain. Different domains might have different constraints etc.

A model then works out if the domain is consistent, by evaluating all the actions and events using the domain constraints, and assigning it a truth value depending on whether it is possible or not. I might be wrong there, as I'm not sure I have interpreted the definition correctly — please let me know in a comment if that is the case.

Basically, if a model for a domain exists, it means that the actions and facts are consistent, and hence the narrative works (it is "a discourse compatible with a given domain"): a narrative is a discourse in a domain which, when embedded in a timeline, is consistent.

A default domain is one domain out of a set of other domains which seems preferable over the others.

(I have to stop here for lack of time — I might be able to expand this answer later)


Why is it ok to calculate the reward based on a hidden state? I'm looking at this source code, where the reward is calculated with

reward = cmp(score(self.player), score(self.dealer))

Why is it ok to calculate the reward based on a hidden state?

A player only sees the dealer's first card.

self.dealer[0]

The code you reference is not part of the learning agent. It is part of:

class BlackjackEnv(gym.Env):

If, as in this case, the environment is provided entirely by software simulation, it is absolutely necessary for it to include a full working model of all state transitions and rewards. That is independent of whether any hidden state makes the problem harder.

  Why is it ok to calculate the reward based on a hidden state?

In the case of Blackjack, this can be treated not as a hidden state that would affect the outcome if only known, but as randomness in the environment over which the agent has no control. Critically, the dealer has no options to behave differently depending on the unknown card, and the dealer's eventual score is entirely unaffected by the player's earlier choices.

It is a subtle difference. If you applied the same environment rules to Poker, where an opponent could behave differently depending on this hidden knowledge, then a simple MDP model is not enough theory to result in an optimal solution. In that case, you would need to look into Partially Observable MDPs (POMDPs). Note this would not affect reward calculation in the environment, just the choices of which agent type to use. If you are just learning RL, you probably don't know of any algorithms that could solve this yet.

In practice, a lot of problems are somewhere between a classic MDP and a POMDP - they contain elements which, if the agent could know them, may allow it to achieve a higher expected reward. In many cases though, these elements can either be treated as random (as here in Blackjack) and thus the system is still theoretically an MDP, or they have a very small effect on the optimal policy, so can be ignored for practical purposes (e.g. think of all the physical details in a real cart pole balancing system - friction, temperature, flexing motions, etc).


What makes Google Translate fail on the Latin language? As it is discussed here, and I saw it on other Latin language forums too, everybody complains about how Google Translate fails to translate the Latin language. From my personal experience, it is not that much bad on other languages, including romance languages.
So, what makes Google Translate fail so much to translate the Latin language? Is it about its syntax and grammar or lack of data?

I don't know what model Google is using for their translations, but it's highly likely that they're using one of today's SOTA deep learning models.
The latest NLP models are trained on data scraped from the web, e.g. OpenAI's GPT-2 was trained on a dataset of 8 million web pages, Google's BERT was trained on the BookCorpus (800M words) and English Wikipedia (2.500M words) pages.
Now think about the amount of latin web pages and notice that there are over 6 million english wikipedia articles but less than 135.000 in latin (see here).
As you can see, massive amounts of data are crucial for neural machine translation and I assume there is simply not enough out there for latin. Plus latin is one of the most complex and complicated languages, this makes the task not easier. Maybe Google and Co also focus less on a 'dead' language which is not spoken anymore and has it's right to exist more for educational purposes.


Are iterative deepening, principal variation search or quiescence search extensions of alpha-beta pruning? I know that there are several optimizations for alpha-beta pruning. For example, I have come across iterative deepening, principal variation search, or quiescence search.

However, I am a little bit confused about the nature of these algorithms.

Are these algorithms an extension of the alpha-beta algorithm, or
Are they completely new algorithms, in that they have got nothing to do the alpha-beta algorithm?

On this site, these algorithms fall into one of 4 categories, namely

mandatory
selectivity
scout and friends
Alpha-beta goes best-first

Does this mean that the alpha-beta algorithm is split into four areas and that they are specialized optimization algorithms for each area?

How do I even begin to decide which optimized algorithm to pick?

I advise people to visit this site:
http://www.fierz.ch/strategy2.htm

Are these algorithms an extension of the alpha-beta algorithm, or
  Are they completely new algorithms, in that they have got nothing to do the alpha-beta algorithm?

Most of them are extensions of the Alpha-Beta pruning algorithm. For example, Iterative Deepening is almost the same as Alpha-Beta pruning, but automatically keeps repeating the algorithm with gradually-increasing depth limits until some time limit is reached, rather than just running once for a pre-determined depth limit.

Principal Variation Search also still uses Alpha-Beta as a basis, but performs many searches with significantly smaller [alpha, beta] windows than the standard Alpha-Beta pruning algorithm.

In most cases, these extensions would start out from an existing Alpha-Beta implementation, and build from there with some adaptations in the code. This is not necessarily the case for all of those extensions though, just for most. For example, Transposition Tables are kind of a separate extension that could be plugged into vanilla Minimax, or Alpha-Beta, or Principal Variation Search, or whatever you're using.

  On this site, these algorithms fall into one of 4 categories, namely

  mandatory
  selectivity
  scout and friends
  Alpha-beta goes best-first

  Does this mean that the alpha-beta algorithm is split into four areas and that they are specialized optimization algorithms for each area?

Those four categories are not mutually exclusive, they're more like... broad "flavours". What they list under Obligatory are some of the more basic extensions that any programmer should probably look into first if they were developing a chess-playing program. The other category are different "flavours", different "broad ideas". For example, everything listed under "Selectivity" is about searching "interesting" or "exciting" parts of the search tree deeper than "less interesting" or "boring" parts. Many of those ideas could be used regardless of whether you're using Alpha-Beta, Iterative Deepening, or PVS, and probably all could be combined with Transposition Tables as well.

  How do I even begin to decide which optimized algorithm to pick?

This is really really difficult to decide just based on the names. In theory, which algorithm is the "best" will also highly depend on your specific game, and maybe even hardware. And, in many cases it's not even a choice between mutually exclusive parts; different ideas can be combined with each other in different ways.

The only solution here is really just to do lots of reading, lots of research, try implementing different things to better understand them.


Testing, Validation Percentage & Test, Validation Batch Size Difference? I'm doing transfer learning using Inception on Tensorflow. The code that I used for training is https://raw.githubusercontent.com/tensorflow/hub/master/examples/image_retraining/retrain.py

If you take a look at the Argument Parser section at the bottom of the code, you will find these parameters :

testing_percentage
validation_percentage
test_batch_size
validation_batch_size

So far, I understand that testing and validation percentage is the amount of images that we want to train at 1 time. But I don't really understand the use of test batch size and validation batch size. What is the difference between percentage and batch size?

The percentages refer to the number of samples to use (out of full dataset) as the validation and test datasets. So if you pass a dataset that consists of 100,000 samples to the model and set the validation and testing percentages to be 10% each, your model will train on 80,000 samples, validate them on 10,000 and save additional 10,000 samples for the final test.

The batch sizes refer to the number of samples in each batch during the test and validation evaluations.
Your model probably can't process 10,000 samples in a single run (due to memory limitations) so during evaluation it breaks the dataset into batches, which are processed sequentially and the result is the mean of all batches.

When you are training, the batch size is an important hyper-parameter which has an affect on the properties and final results of the training process. During test/validation it has no affect and only needs to be small enough for your model to be able to run it (evaluation with different batch sizes will produce the same results).


In Artificial Intelligence, what are semantic analyses used for? Semantics means the meaning and interpretation of words, signs, and sentence structure. Semantics largely determine our reading comprehension, how we understand others, and even what decisions we make as a result of our interpretations. Semantics can also refer to the branch of study within linguistics that deals with language and how we understand meaning. This has been a particularly interesting field for philosophers as they debate the essence of meaning, how we build meaning, how we share meaning with others, and how meaning changes over time.so actually in artificial intelligence what do semantic analysis used for ?

In Natural Language Processing (NLP), you are dealing with knowledge/intents/... expressed in linguistic structures. For example, if you have a text understanding system, you would read the text, usually sentence by sentence, analyse the syntactic structure, and then the meaning (composed of the word meaning and the structural meaning, plus the pragmatic meaning (based on the situation/context)); in other words, looking at the semantic content of a sentence helps you understand what it is about. An AI system can then process the content towards the goal of understanding the text.

In natural language generation, a semantic representation is turned into text. Here the process in reversed: the meaning of the sentence is known, but the appropriate words and sentence structures have to be chosen by the generator.

These are two examples where semantic analysis is used in NLP; there are plenty of others, as meaning is central to the processing of natural language.


DQN Q-values are static I am working on a DDQN with 5 LSTM layers and 3 actions as output and state space of 21 features. I am dividing the dataset into episodes of 720 timesteps, for each episode the agent acts greedily for the first 480 steps without training, collecting a replay memory, and then update the parameters each step for the subsequent 240 steps using a window size (of 96 steps) randomly sampled from the replay memory (that always saves the last 480).

My problem is that so far the agent learned the optimal policy just once, and it looks like this
(on the test set, training is off) where, as you can see, the agent dynamically changes its evaluation of the state and acts greedily accordingly. All works fine and the performances are optimal, however, I have to slightly change the normalization of the database and rerun the training to get new parameters fitted to the new database.

Trying to get to the same result has been proven impossible so far, (even keeping all settings the same!) because most of the time the agent learns to keep its q-values static such as .
Note: this is an extract of the end of an episode and the beginnig of a new one, the noisy behaviour at the extreme is due to the model being trained for each step, in the middle the training is off and the agent acts greedily (as I explained above). The problem is that the learned parameters give rise to static q values that do not change while the state does and inevitably make the agent stuck in suboptimal strategy, as they never changes actions, even on longer sequences on the test set. The middle part of the second picture, where trainig is off, should look like the first picture, however, I am unable to get back to that optimal behaviour, even keeping all the parameters as they were.

Any idea on what can be the cause of this anomalous behaviour?

It is likely converging to a far worse local optimum from which it can't recover, so yes I would guess if all else is the same, that is where the issue would be. I would first try to adjust hyperparameters from a static seed for weight initialization.  ε and α, are likely good places to start.

If that fails, adjust some architecture params like the number of units or layers in the network as well as the starting seed value.

You seemingly have run into a core problem at the heart of ML research which is reproducibility, which is often predicated by initialization.


Is a learned policy, for a deterministic problem, trained in a supervised process, a stochastic policy? If I trained a neural network with 4 outputs (one for each action: move down, up, left, and right) to move an agent through a grid (deterministic problem). The output of the neural network is a probability distribution over the 4 actions, due to the softmax activation function.
Is the policy (based on the neural network) a stochastic policy, even if the action space is discrete?

Is the policy (based in the neural network) a stochastic policy? even if the action space is discrete?

Yes. A discrete action space does not require a deterministic policy - it is possible to assign arbitrary probabilities to each action in each state provided each probability is in the range $[0,1]$ and the sum across all allowed actions is $1$. The two concepts of determinism and discrete actions are entirely separate.
The optimal policy in many situations can be deterministic. If there is only one deterministic optimal policy, your learned policy should be also close to deterministic if the learning process has been successful. That is, the probabilities of optimal actions should all be close to $1$, all the rest close to $0$.
If there is more than one possible optimal policy, your learning agent may have learned a stochastic "mix" of them where in some states it is equally good to take more than one action and the probabilities may be split between those good actions. This will still be optimal and not a problem. If that is the case you should expect to see many action choices close to $0$ and in each state a select few (maybe one) that sum to close to $1$ between them.
In the case of discrete actions, you can derive a deterministic policy from your neural network function by taking the argmax of the action probabilities. This is worth trying. It will round away bad actions that are close to 0 probability due to approximation in the neural network.
In practice sometimes a little randomness in a policy works better for real-world problems with imprecise measurements or other unknowns. It may even be necessary for adversarial environments or where there is key information missing. The only way to find out though is to try both stochastic and deterministic interpretations of the neural network output for your policy.


How to choose an activation function for the hidden layers? I choose the activation function for the output layer depending on the output that I need and the properties of the activation function that I know. For example, I choose the sigmoid function when I'm dealing with probabilities, a ReLU when I'm dealing with positive values, and a linear function when I'm dealing with general values.
In hidden layers, I use a leaky ReLU to avoid dead neurons instead of the ReLU, and the tanh instead of the sigmoid. Of course, I don't use a linear function in hidden units.
However, the choice for them in the hidden layer is mostly due to trial and error.
Is there any rule of thumb of which activation function is likely to work well in some situations?
Take the term situations as general as possible: it could be referring to the depth of the layer, to the depth of the NN, to the number of neurons for that layer, to the optimizer that we chose, to the number of input features of that layer, to the application of this NN, etc.
The more activation functions I discover the more I'm confused in the choice of the function to use in hidden layers. I don't think that flipping a coin is a good way of choosing an activation function.

It seems to me that you already understand the shortcomings of ReLUs and sigmoids (like dead neurons in the case of plain ReLU).
You may want to look at ELU (exponential linear units) and SELU (self-normalising version of ELU). Under some mild assumptions, the latter has the nice property of self-normalisation, which mitigates the problem of vanishing and exploding gradients. In addition, they propagate normalisation - i.e., they guarantee that the input to the next layer will have zero mean and unit variance.
However, it would be incredibly difficult to recommend an activation function (AF) that works for all use cases, although I believe that SELU was designed so that it would do the right thing with pretty much any input.
There are many considerations - how difficult it is to compute the derivative (if it is differentiable at all!), how quickly a NN with your chosen AF converges, how smooth it is, whether it satisfies the conditions of the universal approximation theorem, whether it preserves normalisation, and so on. You may or may not care about some or any of those.
The bottom line is that there is no universal rule for choosing an activation function for hidden layers. Personally, I like to use sigmoids (especially tanh) because they are nicely bounded and very fast to compute, but most importantly because they work for my use cases. Others recommend leaky ReLU for the input and hidden layers as a go-to function if your NN fails to learn. You can even mix and match activation functions to evolve NNs for fancy applications.
At the end of the day, you are probably going to get as many opinions as there are people about the right choice of activation function, so the short answer should probably be: start with the AF of the day (leaky ReLU / SELU?) and work your way through other AFs in order of decreasing popularity if your NN struggles to learn anything.


What is the intuition behind grid-based solutions to POMDPs? After spending some time reading about POMDP, I'm still having a hard time understanding how grid-based solutions work.

I understand the finite horizon brute-force solution, where you have your current belief distribution, enumerate every possible collection of action/observation combinations for a given depth and find the expected reward.

I have tried to read some sources about grid-based approximations, for example, these slides describe the grid-based approach.

However, it's not clear to me what exactly is going on. I'm not understanding how the value function is actually computed. After you take an action, how do you update your belief states to be consistent with the grid? Does the grid-based solution simply reduce the set of belief states? How does this reduce the complexity of the problem?

I'm not seeing how this reduces the number of actions, observation combinations needed to be considered for a finite-horizon solution.

I will attempt to provide an answer to your questions based on the information you can find in the papers A Heuristic Variable Grid Solution Method for POMDPs (1997) by Ronen I. Brafman and Point-based value iteration: An anytime algorithm for POMDPs (2003) by Joelle Pineau et al.

A grid-based approximate solution to a POMDP attempts to estimate a value function only at a subset of the number of belief states. Why? Because estimating the value function for all belief states is typically computationally infeasible for non-small POMDPs, given that the belief-space MDP (i.e. an MDP where the state space consists of probability distributions over the original states of the POMDP) of a POMDP with $n$ states has an uncountably large state space. Why? Because of the involved probability distributions.

How do we compute the value for the belief states that do not correspond to a point of the grid? We can use e.g. interpolation, i.e. the value of a belief state that does not correspond to a point of the grid is computed as a function of the value of the belief states that correspond to other grid points (typically, the neighboring grid points).

Why is this approach feasible? The assumption is that interpolation is not as expensive as computing the value of a belief state. However, note that you may not need to interpolate at every step of your algorithm, i.e. interpolation could be performed only when the value of a certain belief state is required.

How do you compute the value of a belief state that corresponds to a grid point? It can be computed with a value iteration (dynamic programming) algorithm for POMDPs. An overview of a value iteration algorithm can be found in section 2 of the paper Point-based value iteration: An anytime algorithm for POMDPs. Here's an example of the application of the value iteration algorithm for POMDPs.

The grid-based approach, introduced in Computationally Feasible Bounds for Partially Observed Markov Decision Processes (1991) by William S. Lovejoy, is very similar to the point-based approach, which was introduced in Point-based value iteration: An anytime algorithm for POMDPs. The main differences between the two approaches can be found in section 3 of Point-based value iteration: An anytime algorithm for POMDPs.

The idea of discretizing your problem or simply computing the desired value at a  subset of the domain has been applied in other contexts too. For example, in the context of computer vision, you can approximate the derivative (or gradient) of an image (which is thus considered a function) at discrete points of the domain (i.e. the pixels).

There's a Julia implementation of the first grid-based approximative solution to POMDP. There's also a Python implementation of the point-based approach. These implementations may help you to understand the details of these approaches.


How to perform gradient checking in a neural network with batch normalization? I have implemented a neural network (NN) using python and numpy only for learning purposes. I have already coded learning rate, momentum, and L1/L2 regularization and checked the implementation with gradient checking.

A few days ago, I implemented batch normalization using the formulas provided by the original paper. However, in contrast with learning/momentum/regularization, the batch normalization procedure behaves differently during fit and predict phases - both needed for gradient checking. As we fit the network, batch normalization computes each batch mean and estimates the population's mean to be used when we want to predict something.

In a similar way, I know we may not perform gradient checking in a neural network with dropout, since dropout turns some gradients to zero during fit and is not applied during prediction.

Can we perform gradient checking in NN with batch normalization? If so, how?

You should be able to do gradient checking as long as you fix the randomness by fixing the random seed, on python you might want to look at numpy.random.seed.

From http://cs231n.github.io/neural-networks-3/#ensemble :

  When performing gradient check, remember to turn off any non-deterministic effects in the network, such as dropout, random data augmentations, etc. Otherwise these can clearly introduce huge errors when estimating the numerical gradient. The downside of turning off these effects is that you wouldn’t be gradient checking them (e.g. it might be that dropout isn’t backpropagated correctly). Therefore, a better solution might be to force a particular random seed before evaluating both (f(x+h)) and (f(x-h)), and when evaluating the analytic gradient.


Network representation for Q-Learning in carrom I am trying to build an agent to play carrom. The problem statement is roughly to estimate three parameters (normalized) :

force
angle of striker
position of strike

Since the state and action space both are continuous, I thought of discretizing the output such that I have 270 [ valid angles from -45 to 225 degrees ] outputs for the angle, 10 outputs for force [ranging from 0 to 1] and 20 outputs for the position [ranging from 0 to 1].

Thus I will have 300 output of my neural network, but this number seems a bit too high compared to normal neural networks in practice.

I was wondering if there is a better way of approaching the problem considering the fact that there are multiple parameters to a particular action.

Is there a generic way to approach such problems represented in 2D space.

Discretizing the output will probably be counter-productive in this situation; it would remove flexibility by taking away the fine-grained continuous ranges between each discretization bucket, but also blow up the size of the network, reducing manageability and performance. Fragmenting the outputs into buckets in this way may also lead to information loss and more difficulty in convergence because of the fact that each bucket is partially isolated from the others.

After causing myself needless hassle in the past by mismatching input and output dimensions, I'd simply do this if I were in your shoes: 1) keep it simple and use 3 continuous (well, semi-continuous, depending on the highest precision your programming framework allows) outputs for all of the above reasons; 2) clamp the angles between -45 to 225 by whatever method works best for you, like ceiling/floor hard clamping, adding weight terms, etc.; 3) go big on the hidden layer(s) to maximize information sharing across the inputs and eventual outputs, force, angle of strike, position of strike, etc. This is more likely to fine-tune the precision of the outputs, thereby making good use of the semi-continuous scales.

I'm also wondering if a convolutional neural net might work in this situation; their most popular use case is in image processing, but I don't see why you can't treat the force, angle and position as surrogate spatial dimensions. I'm not sure how many or what type of inputs you have, but 3 continuous outputs might be conducive to a 3D rather than a 2D space. Convolutionals are often used for those, as well as higher-dimensional and temporal data. I hope that helps.


Does eligibility traces and epsilon-greedy do the same task in different ways? I understand that, in Reinforcement Learning algorithms, such as Q-learning, to prevent selecting the actions with greatest q-values too fast and allow for exploration, we use eligibility traces.
Here are some questions

Does $\epsilon$-greedy solve the same problem?

Do these two approaches aim to attain the same objective?

What are the advantages of each over the other?

Epsilon-greedy is one method of making an agent explore the state space to ensure that the agent doesn't settle on a sub-optimal policy. By taking random actions, even with a small probability, the agent can get to places in the state space it normally wouldn't see and on the chance that the outcome is better than what it normally would have seen, it can modify its value function (or Q function) for that state (or action) to ensure that that action is taken in the future. An alternative to Epsilon-greedy methods is modifying the policy directly using Policy Gradient methods.
Eligibility traces attempt to solve a different problem. Their function is to keep a short term memory of what states have been recently visited. They unify and generalize TD and Monte Carlo methods producing a family of methods spanning a spectrum that has Monte Carlo methods at one end ($\lambda = 1$) and one-step TD methods at the other ($\lambda = 0$). Using traces, one can keep the features of previous states around, but at faded values depending on the choice of $\lambda$. Choosing a low $\gamma$ (near $0$) makes the traces myopic in that the traces quickly go to $0$. If a larger $\lambda$ is used (near $1$) the traces stay around for much longer and can help an agent determine the difference between what would otherwise be 2 identical states.
For more information, check out Reinforcement Learning: An Introduction, chapter 2 (page 30 introduces $\epsilon$-greedy methods) and chapter 12 (eligibility traces).


Is my interpretation of the return correct? Sutton and Barto 2018 define the discounted return $G_t$ the following way (p 55):

Is my interpretation correct?

Or should all "1" be in the same column?

Your table is almost correct. It is a minor difference, you should not have a $R_0$, the top row, leftmost column of numbers should be empty. That is because the first reward is $R_1$ (a result of taking action $A_0$ in state $S_0$). The alignment of the columns on the right hand side is correct though.

It might help to add the time step number at the top. But the important detail is that $G_t$ is a measure of all future rewards.

For instance it should always be zero when you reach a terminal state, which is what your example shows. Whilst it is quite common to receive a reward at the end of an episode (i.e. whilst arriving at a terminal state), also as your example shows.

The decision to have reward time step match that of next state is a convention that can be altered. A few RL sources, but not Sutton & Barto, will have reward on same time step as state and action that decided it, and thus $R_0$ will exist. The reward of 1 for reaching the terminal state would then be 1 time step earlier in your table, and there would be no $R_4$. The definition of $G_t$ would need to change to match ($G_t = R_t + \gamma G_{t+1})$, as well as other equations. That would change your table also - the reward sequence (top row) would shift to the left.


Will the target network, which is less trained than the normal network, output inferior estimates? I'm having some trouble understanding some parts of the usage of target networks.

I get that having the same network predict the state/action/advantage values for both the current networks can lead to instability.

Based on my understanding, the intuition behind 1-step TD error that going a step into the future will give you a better estimate, that can then be used to update your original state/action/advantage value.

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

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

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

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

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

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

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

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

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

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

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

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

40.222      39.889
40.556      40.222
40.889      40.556
41.222      40.889
41.556      41.222

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

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

 8.0         7.5
 8.0         7.5
 8.0         7.5
 8.0         7.5
 8.0         7.5

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

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

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

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

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

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


How can both agents know the terminal reward in self-play reinforcement learning? There seems to be a major difference in how the terminal reward is received/handled in self-play RL vs "normal" RL, which confuses me.
I implemented TicTacToe the normal way, where a single agent plays against an environment that manages the state and also replies with a new move. In this scenario, the agent receives a final reward of $+1$, $0$ and $-1$ for a win, draw, and loss, respectively.
Next, I implemented TicTacToe in a self-play mode, where two agents perform moves one after the other, and the environment only manages the state and gives back the reward. In this scenario, an agent can only receive a final reward of $+1$ or $0$, because, after his own move, he will never be in a terminal state in which he lost (only agent 2 could terminate the game in such a way). That means:

In self-play, episodes end in such a way that only one of the players sees the terminal state and terminal reward.

Because of point one, an agent can not learn if he made a bad move that enabled his opponent to win the episode. Simply because he does not receive a negative reward.

This seems very weird to me. What am I doing wrong?  Or if I'm not wrong, how do I handle this problem?

When one agent makes a move, that move should be perceived as part of the "state transition" executed "by the environment" from the perspective of the other agent.

For example, suppose that, as a "neutral third party" we view the game as follows, as a sequence of states, actions and a terminal reward. I use A to denote actions selected by the first player, and B to denote actions selected by the second player:

S1 -> A1 -> S2 -> B1 -> S3 -> A2 -> S4 -> B2 -> S5 -> A3 -> Terminal Reward

Then, the first player should only get the following observations:

S1 -> A1 -> S3 -> A2 -> S5 -> A3 -> Terminal Reward

note how states S2 and S4 are skipped entirely, they are not really states from the perspective of the first player, they're just halfway through the transition caused by the first player's action and are not interesting for the first player.

Similarly, the second player should only get the following observations:

S2 -> B1 -> S4 -> B2 -> Terminal Reward