Why can't pure KG embedding methods discover multi-hop relations paths? According to Reinforcement Knowledge Graph Reasoning for Explainable Recommendation

  pure KG embedding methods lack the ability to discover multi-hop relational paths.

Why is it so?

To put this insert to context, we should take at least this much of text from the paper:

  One line of research focuses on making recommendations using knowledge graph embedding models, such as TransE [2] and node2vec [5]. These approaches align the knowledge graph in a regularized vector space and uncover the similarity between entities by calculating their representation distance [30]. However,pure KG embedding methods lack the ability to discover multi-hop relational paths.

In my understanding the pure KG embedding here refers to TransE and node2vec solutions. To learn more about those, we should read links [1] and [2]. From [1]:

  Usually, we use a triple (head, relation, tail) to represent a knowledge. Here, head and tail are entities. For example, (sky tree, location, Tokyo). We can use the one-hot vector to represent this knowledge.

Later on same source there is an explanation on the end of definition section of TransE solution:

  But this model only can take care with one-to-one relation, not suitable for one-to-many/many-to-one relation, for example, there is two knowledge, (skytree, location, tokyo) and (gundam, location, tokyo). After training, the 'sky tree' entity vector will be very close with 'gundam' entity vector. But they do not have such similarity in real.

On other hand, [3] tells:

  Knowledge graphs as described above represents a static snapshot of our knowledge. It does not reflect the process of it’s how the knowledge built up. In the real world, we learn by observing temporal patterns. While it’s possible to learn the similarity between nodes A and node B, it will be hard to see the similarity between node A and node C as it was 3 years ago.

Solution in paper states "--,each recommended item is associated with around 1.6 reasoning paths." which is supposedly impossible for TransE solution.

So, knowledge graph, purely, is a static snapshot that can identify by great accuracy one to one findings. Actually according what [2] tells how node2vec works, they can describe and combine also more information (node2vec combines different types of similarities at same time), but anyways I think the main point is actually in one word in the citation: discover!

The model suggested on paper adds Reinforcement Learning principles to the KG modeling, so to say, the pure KG embedding always tells one distance based statistical solution, but a RL based solution may learn more aspects behind the scenes as it learns by try and error more complex paths underlying in the behavior.

On the other hand, the paper says, when relating their solution to pure TransE:

  It can be regarded as a single-hop latent matching method, but the post-hoc explanations do not necessarily reflect the true reason of generating a recommendation. In contrast, our methods generate recommendations through an explicit path reasoning process over knowledge graphs, so that the explanations directly reflect how the decisions are generated, which makes the system transparent.

So, whether TransE and those could actually recommend things in the given environment, the recommendation reasoning paths may stay obscure.

Sources:

[1] https://towardsdatascience.com/summary-of-translate-model-for-knowledge-graph-embedding-29042be64273

[2] https://towardsdatascience.com/node2vec-embeddings-for-graph-data-32a866340fef

[3] https://towardsdatascience.com/extracting-knowledge-from-knowledge-graphs-e5521e4861a0


Support Vector Machine Convert optimisation problem from argmax to argmin I'm new to the AI Stackexchange and wasn't certain if this should go here or to Maths instead but thought the context with ML may be useful to understand my problem. I hope posting this question here could help another student learning about Support Vector Machines some day.
I'm currently learning about Support Vector Machines at university and came across a weird step I could not understand. We were talking about basic SVMs and formulated the optimisation problem $\max_{w,b} \{ \frac{1}{||w||} \min_n(y^{(n)}f(x^{(n)}))\}$ which we then simplified down to $\max_{w,b} \{ \frac{1}{||w||}\}$ by introducing $\kappa$ as a scaling factor for $w$ and $b$ according to the margin of the SVM. Now our lecturer converted it without explanation into a quadratic optimisation problem as $\min_{w,b}\{\frac{1}{2} ||w||^2\}$ which I could not explain myself. I hope someone with context can help me how this is possible and what math or trick is behind this approach?

Notation information:

$w$ - weight matrix
$b$ - bias (sometimes denoted $w_0$ I believe?)
$x^{(n)}$ - Independent variable (vector)
$y^{(n)}$ - Dependent variable (scalar classifying the input in a binary classifcation as $y=1$ or $y=-1$)

Thank you very much!

So actually I managed to get hold of my lecturer to explain the argmax to argmin conversion.
Generally speaking maximising $\frac{1}{||w||}$ is identical to minimising $||w||$. As $||w||$ in $\frac{1}{||w||}$ decreases, the overall value increases, i.e. we maximise it. The reason for choosing $\frac{1}{2}||w||^2$ turns out to be a less mathematic and more practical one as our optimisation algorithms used perform better on quadratic functions and the $\frac{1}{2}$ seems to be a rather arbitrary scaling choice.
If anyone has something to add, I'd love to hear any details though!


How can I design an AI that knows when its being spoken to? I am trying to make an intelligent agent similar to Jarvis from Iron Man, but much less complex. However, I want my AI to be able to determine if I am talking to it or not. So, I plan on having it always listen to my voice and convert that to text. However, I am not sure how I can train the AI to recognize if it is being spoken to or not?

Phrase detection instead of text-to-speech

It's worth noting that detection of particular phrases or commands is considered a distinct problem, different from text to speech / text transcription.

While you can simply convert everything it hears to text and then look up keywords there, a specialized detector that directly tries to match incoming audio to a small subset of commands can be done with better accuracy and less processing power required. For this reason, this would generally be the preferred approach in commercial products.

However, for beginner experiments with home automation, you should probably start with choosing an existing speech analysis API where all the audio and natural language parts are appropriately implemented by someone else. Building a good speech command analysis system from scratch is a major undertaking by itself, and you will have your hands full with developing an "artificial intelligent agent"; as a rule, you don't want a project where you have to tackle two major open-ended problems, pick one of them and then you'll have a chance to achieve something interesting there.


In RL, if I assign the rewards for better positional play, the algorithm is learning nothing? I'm creating an RL application for the game Connect Four.

If I tell the algorithm which moves/token positions will receive greater rewards, surely it's not actually learning anything; it's just a basic lookup for the algorithm? "Shall I place the token here, or here? Well, this one receives a greater reward, so I choose this one."

For example, some pseudocode:

function get_reward()
    if 2 in a line
        return 1
    if 3 in a line
        return 2
    if 4 in a line
        return 10
    else
        return -1

foreach columns
    column_reward_i = get_reward(column_i)
    if column_reward_i >= column_rewards
        place_token(column_i)

What you are proposing is closer to a heuristic for searching than a reward for RL. This is a blurred line, but generally if you start analysing the problem yourself, breaking it down into components and feeding that knowledge into the algorithm, then you place more emphasis on your understanding of the problem, and less on any learning that an agent might do.

Typically in a RL formulation of a simple board game, you would choose rewards or +1 for a win (the goal), 0 for a draw, and -1 for a loss. All non-terminal states would score 0 reward. The point of the RL learning algorithm is that the learning process would assign some nominal value to interim states due to observing play. For value-based RL approaches, such as Q learning or Monte Carlo Control, the algorithm does this more or less directly by "backing up" rewards that it experiences in later states into average value estimates for earlier states.

Most game-playing agents will combine the learning process, which will be imperfect given the limited experience an agent can obtain compared to all possible board states, with a look-ahead search method. Your heuristic scores would also make a reasonable input to a search method too - the difference being you may need to search more deeply using your simple heuristic than if you used a learned heuristic. The simplest heuristic would just be +1 for a win, 0 for everything else, and is still reasonably effective for Connect 4 if you can make it search e.g. 10 moves ahead.

The combination of deep Q learning and negamax search is quite effective in Connect 4. It can make near perfect agents. However, if you actually want a perfect agent, you are better off skipping the self-learning approach and working on optimised look-ahead search with some depth of opening moves stored as data (because search is too expesnive in the early game, even for a simple game like Connect 4).


Why object detection algorithms are poor in optical character recognition? OCR is still a very hard problem. We don't have universal powerful solutions. We use the CTC loss function
An Intuitive Explanation of Connectionist Temporal Classification | Towards Data Science
Sequence Modeling
With CTC | Distill
which is very popular, but it's still not enough.
The simple solution would be to use object detection algorithms for recognizing every single character and combine them to form words and sentences.
We already have really powerful object detection algorithms like Faster-RCNN, YOLO, SSD. They can detect even very complicated objects that are not fully visible.
But I read that these object detection algorithms are very poor if you use them for recognizing characters. It's very strange since these are very simple objects, just a few lines and circles. And mainly grayscale images. I know that we use object detection algorithms to detect the regions of text on big images. And then we recognize this text. Why can't we just use object detection algorithms (small versions of popular neural networks) for recognizing single characters?
Why we use CTC or other approaches (besides the fact that it would require much more labeling)?
Why not object detection?

Good question! Using Yolo to recognise characters would be a good experiment to try. It may be because of the density of characters on a page -- systems like Yolo are very good at detecting a small number e.g. 2,3 or 10, objects, but don't work so well when the number of objects  is the hundreds as you might have with OCR. A better approach might be to try face detection methods that work well with large crowds.


What is the difference between parametric and non-parametric models? A model can be classified as parametric or non-parametric. How are models classified as parametric and non-parametric models? What is the difference between the two approaches?

Parametric Methods
A parametric approach (Regression, Linear Support Vector Machines) has a fixed number of parameters and it makes a lot of assumptions about the data. This is because they are used for known data distributions. i.e, it makes a lot of presumptions about the data
Non-Parametric Methods
A non-parametric approach (k-Nearest Neighbours, Decision Trees) has a flexible number of parameters, there are no presumptions about the data distribution. The model tries to "explore" the distribution and thus has a flexible number of parameters.
Comparision
Comparatively speaking, parametric approaches are computationally faster and have more statistical power when compared to non-parametric methods

Hope this cleared your doubts


Is it ethical to create a chatbot to answer questions on Stack Overflow? I was wondering if I should do this, because 2 out of 5 questions on Stack Overflow don't ever get answered, or if they do get (an) answer (s), most of the time they're not helpful.

So I was thinking -- why not create a chat bot to answer Stack Overflow's questions & provide necessary information to the general public?

I mean why not? I've always been interested in AI, and all I'd need to do is create a basic logic database and a context system, pack an artificial personality with (partial) human instincts, and bam I'm done.

But then again, would it be ethical?

Yes, it is possible, and has actually been done in the past.

The University of Antwerp created a bot to answer questions (this is the technical report). It focused on the git tag only though (even though it did answer one mysql question).

Its accuracy was pretty good, and the bots in the tests did earn some reputation. So I assume it is possible.

But do note that the last bot in the tests revealed that it was a bot, and thus got banned. So if you reveal that the account you are running the bot on is a bot, there is a high chance that it will get banned.


Using three image datasets with different image sizes to train a CNN I've just started with AI and CNN networks.

I have two NIFTI images dataset, one with (240, 240) dimensions and the other one with (256, 132). Each dataset is front a different hospital and machine.

If I want to use both to train my model. What do I have to do?

The model needs to have all the train data with the same shape. I've thought to reshape all the data to have the same shape, but I don't know if I'm going to lose information if I reshape the images.

By the way, I have also a third dataset with (232, 256).

Resizing the images will work.But if you significantly reduce the image dimensions information IS lost. Here is a simple example. Suppose you have a 500 X 500 image. That has 250,000 pixels. Assume in these images the object of interest( lets say a bird in a forest) only occupies 10% of the pixels in the image(25,000 pixels). Now assume you reduce the image to 100 X 100 and thus have 10,000 pixels. Your object of interest (the bird) now only occupies 1000 pixels. These are the pixels the neural net will learn from.
Now a better way to do this is to first crop your original 500 X 500 images to maximize the percentage of bird pixels in the cropped image. For example assume the resulting cropped image comes out to be say a 200 X 200 image but in that image the subject of interest(the bird) occupies 50% of the pixels (20,000 pixels). Now if you reduce the cropped image down to a 100 X 100 the object of interest will occupy(5000 pixels).
Cropping images is of course a hassle. For some types like images for example images of people, and you are just interested in the faces there are routines available that will automatically crop the image to just the face. In general you will have to crop the images yourself.
If you want to build high accuracy classifiers you have to start with a "robust" data set.
The larger the percentage the object of interest takes up in the images the better your classifier will perform.


Is there a place where people can share (or buy) ready made neural networks? Is there a place where people can share (or buy) ready made neural networks instead of creating them themselves?
Something like a Wikipedia for DNNs?

It's not a specific web for sell or share neural network models, but actually you can easily find other people models in Github! Just search it! For example, this is a random repo I've found for Cat Classification.
But.. the problem is everyone have different problems. So you can't easily use other people neural network models and then use it for your problem. That's why there's a "trick" called transfer learning or fine tuning. That method show you how to train other people models (it's called: pre-trained models) from different problems for your specific problem.
Tensorflow and PyTorch provide a lot of pre-trained model for common problems:

Pytorch Image Classification Pre-Trained models
Tensorflow Object Detection Model Zoo
PyTorch Detectron Model Zoo

You can also find other pre-trained models in Github! This is an official PyTorch tutorial how to use that pre-trained model to your specific case.


What is the difference between reinforcement learning and optimal control? Coming from a process (optimal) control background, I have begun studying the field of deep reinforcement learning.
Sutton & Barto (2015) state that

particularly important (to the writing of the text) have been the contributions establishing and developing the relationships to the theory of optimal control and dynamic programming

With an emphasis on the elements of reinforcement learning - that is, policy, agent, environment, etc., what are the key differences between (deep) RL and optimal control theory?
In optimal control we have, controllers, sensors, actuators, plants, etc, as elements. Are these different names for similar elements in deep RL? For example, would an optimal control plant be called an environment in deep RL?

As a supplement to nbro's nice answer, I think a major difference between RL and optimal control lies in the motivation behind the problem you're solving. As has been pointed out by comments and answers here (as well as the OP), the line between RL and optimal control can be quite blurry.
Consider the Linear-Quadratic-Gaussian (LQG) algorithm, which is generally considered to be an optimal control method. Here a controller is computed given a stochastic model of the environment and a cost function.
Now, consider AlphaZero, which is obviously thought of as an RL algorithm. AlphaZero learns a value function (and thus a policy/controller) in a perfect information setting with a known deterministic model.
So, it's not the stochasticity that separates RL from optimal control, as some people believe. It's also not the presence of a known model. I argue that the difference between RL and optimal control comes from the generality of the algorithms.
For instance, generally, when applying LQG and other optimal control algorithms, you have a specific environment in mind and the big challenge is modeling the environment and the reward function to achieve the desired behavior. In RL, on the other hand, the environment is generally thought of as a sort of black box. While in the case of AlphaZero the model of the environment is known, the reward function itself was not designed specifically for the game of chess (for instance, it's +1 for a win and -1 for a loss, regardless of chess, go, etc.). Furthermore, the neat thing with AlphaZero is that we can use it to train agents in virtually any perfect information game without changing the algorithm at all. Another difference with RL here is that the agent iteratively improves itself, while optimal control algorithms learn controllers offline and then stay fixed.


How can active learning be used in the case of complex models that require a lot of data? We have a series of data and we want to label the parts of each series. As we do not have any training data, we could try to use active learning as a solution, but the problem is that our classifier is something like RNN which needs a lot of data to be trained. Hence, we have a problem in converging fast to just label proportional small parts of unlabeled data.

Is there any article about this problem (active learning and some complex classifiers, like RNN)?

Is there any good solution to this problem or not? (as data is a series of actions)

As I found this case backs to the sequence labeling. Sequence labeling has some classic solution such as conditional random fields (CRFs) and hidden Markov model (HMM). Also, have some solution in Active learning (AL) which use from algorihtms such as struct SVM ($\text{SVM}^{\text{strcut}}$) like this paper.

Also, some NLP solutions in active learning could help to solve these kind of problems such as this paper which is about active learning in named entity recognition (NER).

Besides, the combination of active learning with Deep networks such as CNN happens. For example, this paper explains more about the idea.


What is the relation between semi-supervised and self-supervised visual representation learning? What's the differences between semi-supervised learning and self-supervised visual representation learning, and how they are connected?

Semi-supervised learning
Semi-supervised learning is the collection of machine learning techniques where there are two datasets: a labelled one and an unlabelled one.
There are two main problems that can be solved using semi-supervised learning:

transductive learning (i.e. label the given unlabelled data) and
inductive learning (generalization) (i.e. find a function that maps inputs to outputs, like classification).

Self-supervised learning
Self-supervised learning (SSL) is a machine learning approach where the supervisory signal is automatically generated. More precisely, SSL can either refer to

learn data representations (i.e. learn to represent the data) by solving a so-called pretext (or auxiliary) task, in a self-supervised fashion, i.e. you automatically generate the supervised signal from the unlabelled

automatically label an unlabelled dataset by exploiting data coming from different sensors (this is the usual definition of SLL in the context or robotics)

What is the relationship between the two?
SSL (for data representation) can be considered a semi-supervised learning approach, if you fine-tune the learned data representations with a labeled dataset to solve supervised learning problem (i.e. the so-called downstream task), which you will probably do otherwise the data representations are pretty useless. Read this answer for other details.


Can residual connections be beneficial when we have a small training dataset? I have a classification problem, for which an inadequate amount of training data is available. Also, there is no known practical data augmentation approach for this problem (as no unlabelled data is available either), but I am working on it.
As we know, deep neural networks require a large amount of data for training, especially when a deep architecture with many layers is used. Using these complex architectures with less data can easily lead to over-fitting. Residual connections can shortcut some blocks or layers, which can result in simpler models, while we have the benefit of complex structures.
Can residual connections be beneficial when we have a small training dataset?

Can residual connections be beneficial when we have a small training dataset?

The usual rule of data science investigations applies here: Try it, measure the results, then you will know.
It is very hard to tell, a priori, whether a specific architectural or hyperparameter choice will impact the performance of a neural network on a given problem.
In this case, you are wondering whether residual networks using skip connections might help when you have a relatively low amount of training data.

On the pro side, effects of skip connections that help correct vanishing gradients, and treat each block as learning the difference from an identity function, will still work for your problem. That means you will have some freedom to explore adding layers without worrying about the negative impacts of doing so.

On the con side, it is unlikley that you will benefit from very deep networks as there will not be enough examples to learn truly complex functions from.

You may find that adding depth, but reducing "width", i.e. the number of artificial neurons in each layer, will work.
If you have a low amount of training data and a difficult problem to solve, then residual networks are not a magic fix. The best you could hope for is a relatively stable statistical model that works on the simpler differences between your training examples. However, it may be possible that tuning a neural network by searching through different architectures will be a worthwhile exercise.
I would also suggest that for one of the good networks that you vary the number of examples used to train the network in multiple training runs, and plot a learning graph showing number of examples versus accuracy (or other metric that you may be interested in). This graph will help you decide whether collecting more training data would be worthwhile because you will have a rough estimate of the gradient for how much new training examples could improve your results.


Why isn't my Neural Network based calculator working? I am playing around with neural networks in Tensorflow and I figured an interesting test would be whether I can write a calculator using a Tensorflow Neural Network.

I started with simple addition and it kinda worked (so given 2, 4 it would get around 5.9 or 6.1).

Then I wanted to add the ability to calculate using "+", "-", and "*".

Here is the code I came up with in the end:

import numpy as np
import tensorflow as tf
from random import randrange

def generate_input(size):
    nn_input = []
    for i in range(0,size):
        symbol = float(randrange(3))
        nn_input.append([
                float(randrange(1000)),
                float(randrange(1000)),
                1 if symbol == 0 else 0,
                1 if symbol == 1 else 0,
                1 if symbol == 2 else 0,
                ])
    return nn_input

def generate_output(input_data):
    return [[generate_single_output(i)] for i in input_data]

def generate_single_output(input_data):
    plus = input_data[2]
    minus = input_data[3]
    multiplication = input_data[4]

    if (plus):
        return input_data[0] + input_data[1]

    if (minus):
        return input_data[0] - input_data[1]

    if (multiplication):
        return input_data[0] * input_data[1]

def user_input_to_nn_input(user_input):
    symbol = user_input[1]
    return np.array([[
            float(user_input[0]),
            float(user_input[2]),
            1 if symbol == '+' else 0,
            1 if symbol == '-' else 0,
            1 if symbol == '*' else 0,
            ]])

if __name__ == '__main__':
    model = tf.keras.models.Sequential([
        tf.keras.layers.Dense(64, activation='relu', input_shape=(5,)),
        tf.keras.layers.Dense(64, activation='relu'),
        tf.keras.layers.Dense(1),
        ])

    model.compile(tf.keras.optimizers.RMSprop(0.001), loss=tf.keras.losses.MeanSquaredError())

    input_data = np.array(generate_input(10000))
    output_data = np.array(generate_output(input_data))

    model.fit(input_data, output_data, epochs=20)

    while True:
        user_calculation = input("Enter expression (e.g. 2 + 3):")
        user_input = user_calculation.split()
        nn_input = user_input_to_nn_input(user_input)
        print(model.predict(nn_input)[0][0])

The idea is built on this tutorial: https://www.tensorflow.org/tutorials/keras/basic_regression

The input is 5 fields: number 1, number 2, plus?, minus?, multiplication?

Where the last 3 are simply 1 or 0 depending on whether that is the calculation I am trying to do.

As an output for say [1,4,1,0,0] I would expect 1 + 4 = 5
for [1,4,0,1,0] I would expect 1 - 4 = -3 etc.

For some reason though the numbers I am getting are completely off and seem random.

Basically I am trying to understand what I went wrong?
The data being input to the NN seems correct and the model is based on the model used in the tutorial I quoted (and the problems seem fairly similar so I expect if one would work the other would too).

A neural network is not good at selecting a function based on those 3 input parameters, because of the way a neuron is setup.

What you should do is either make a neural network for each operation, or use different input neurons for each operation. E.g. 2 input neurons for the addition operation, 2 for the multiplication, and 2 for the minus. 6 inputs in total of which 4 will always be 0.

This will make it easier for the neural network to calculate the result.


Does learning content from additional encyclopedias consume much less amount of storage? Complex AI that learns lexical-semantic content and its meaning (such as collection of words, their structure and dependencies) such as Watson takes terabytes of disk space.

Lets assume DeepQA-like AI consumed whole Wikipedia of size 10G which took the same amount of structured and unstructured stored content.

Will learning another 10G of different encyclopedia (different topics in the same language) take the same amount of data? Or will the AI reuse the existing structured and take less than half (like 1/10 of it) additional space?

It seems easy for this to be sublinear growth or superlinear growth, depending on context.

If we imagine the space of the complex AI as split into two parts--the context model and the content model (that is, information and structure that is expected to be shared across entries vs. information and structure that is local to particular entries), then expanding the source material means we don't have much additional work to do on the context model, but whether the additional piece of the content model is larger or smaller depends on how connected the new material is to the old material.

That is, one of the reasons why Watson takes many times the space of its source material is because it stores links between objects, which one would expect to grow with roughly order n squared. If there are many links between the old and new material, then we should expect it to roughly quadruple in size instead of double; if the old material and new material are mostly unconnected and roughly the same in topology, then we expect the model to roughly double; if the new material is mostly unconnected to the old material and also mostly unconnected to itself, then we expect the model to not grow by much.


Can a neural network work out the concept of distance? Imagine a game where it is a black screen apart from a red pixel and a blue pixel. Given this game to a human, they will first see that pressing the arrow keys will move the red pixel. The next thing they will try is to move the red pixel onto the blue pixel.

Give this game to an AI, it will randomly move the red pixel until a million tries later it accidentally moves onto the blue pixel to get a reward. If the AI had some concept of distance between the red and blue pixel, it might try to minimize this distance.

Without actually programming in the concept of distance, if we take the pixels of the game can we calculate a number(s), such as "entropy", that would be lower when pixels are far apart than when close together? It should work with other configurations of pixels. Such as a game with three pixels where one is good and one is bad. Just to give the neural network more of a sense of how the screen looks? Then give the NN a goal, such as "try to minimize the entropy of the board as well as try to get rewards".

Is there anything akin to this in current research?

Answer

I'm going to take your question at face value, and go really deep into this topic.

Yes, they can. The typical human mind can. But consider the human mind. Millions, if not billions, of neurons. In fact, one can consider distance as a human concept, simply a theory developed from interactions with the world.

Therefore, given a year or two, with a ton of neurons on your hand, you could replicate this scenario. That is if your computer is as parallel as the human mind. The short explanation is that the human mind is very parallel.

However, it would be simpler to calculate the distance with a program, not an AI, and simply feed the result to the AI that would make the decisions.

Consider the amount of time you have spent looking at a screen. If you can tell the (approximate) distance between two pixels, so can a Neural Network, as you are one. However, add the amount of time you have spent alive and learning into the equation, and it becomes a disaster.

Further reading

The human brain is parallel

This is a result of the fact that all of the neurons in the human brain are independent of each other. They can run true simultaneous actions, thus making the action of interpreting images and such much easier, as blocks of neurons can "think" independent of the operations of the others, limiting what would be "lag" to a minuscule amount.


Is it possible to use self-supervised learning on different images for the pretext and downstream tasks? I have just come across the idea of self-supervised learning. It seems that it is possible to get higher accuracies on downstream tasks when the network is trained on pretext tasks.
Suppose that I want to do image classification on my own set of images. I have limited data on these images and maybe I can use self-supervised learning to achieve better accuracies on these limited data.
Let's say that I try to train a neural network on a pretext task of predicting the patch position relative to the center patch on different images that are readily available in quantity, such as cats, dogs, etc.
If I try to initialise the weights of my neural network, then do image classification on my own images, which are vastly different from that of the images used in the pretext task, would self-supervised learning work because the images for the pretext and downstream tasks are different?
TLDR: Must the images used in the pretext task and the downstream tasks be the same?

No, the images do not need to be same. You can use different images for downstream task however you need to do some changes in model definition while loading model state_dict as CNN architecture used for pretext task 'relative patch location', assume Alexnet will expect 2 patches as input.


What does the notation $\partial \theta_{\pi}$ mean in this actor-critic update rule? One of the steps in the actor-critic algorithm is $$\partial \theta_{\pi} \gets \partial \theta_{\pi} + \nabla_{\theta}\log\pi_{\theta} (a_i | s_i) (R - V_{\theta}(s_i))$$

For me, $\theta$ are just the weights. Can you explain to me what mean $\partial \theta_{\pi}$?

The whole algorithm comes from Maxim Lepan's book Deep Reinforcement Learning Hands-on page 269.

Here is a picture of the algorithm :

In reinforcement learning, you can distinguish algorithms based on the functions they use to ultimately find the policy (which is the goal in RL anyway!).

algorithms that attempt to find an optimal value function (an example is Q-learning, which attempts to find a state-action value function), then derive the policy from the value function
algorithms that directly attempt to find a policy (e.g. REINFORCE and other so-called "policy gradients" algorithms)
algorithms that use a value function to guide the search for an optimal policy (i.e. actor-critic methods)

More specifically, in actor-critic methods, you have a policy $\pi$ (known as the "actor") and a value function $v$ (known as the "critic"). Hence the name "actor-critic". The idea is that you will use this critic $v$ to "criticize" the policy (or actor) $\pi$, i.e. to guide the search for a good policy. This article 6.6 Actor-Critic Methods (from Sutton and Barto's book) explains the concept quite well.

In your specific example, the policy and value function are assumed to be differentiable (otherwise, you wouldn't be able to compute the derivatives anyway!). They are typically neural networks. $\theta_\pi$ are the parameters of the neural network that represent the policy (i.e. a neural network that receives as input a state and produces as output an action or probability distribution over actions). Similarly, $\theta_v$ are the parameters of the neural network that represent the critic. Then $\partial \theta_\pi$ and $\partial \theta_\pi $ will represent an accumulation of the gradients with respect to the actor and critic,  respectively. (The accumulation is probably over the steps from $i=t-1$ to $i = t_{\text{start}}$, but I can't say more because I never implemented actor-critic methods). This should give you an idea, though!


What is the difference between a fitness function and a reward function? In reinforcement learning (RL), the reward function (RF), which can be denoted as $r(s)$, $r(s, a)$, $r(s, a, s')$, $r(s, s')$ depending on its specific definition, provides the learning signal, which guides the RL algorithm/agent towards the desirable behaviour. As opposed to a loss (or cost) function in supervised learning, an RF determines the goodness (or quality) of an action in a certain state (in the case of $r(s, a)$) with respect to an optimal behavior/policy. The reward function is typically hand-designed, but it can also be learned with inverse RL techniques.
In evolutionary algorithms, a fitness function (FF) is the function we use to evaluate an individual (or chromosome). The fitness of an individual, a number, represents the quality of that individual.
Both the fitness function and the reward function are very similar, so what's the difference between them? Can a fitness function be thought of as a reward function? Can it be thought of as a cost function in SL problems?

In many cases, a fitness function (FF) is indeed similar to a reward function (RF), but, in other cases, it's more similar to a cost function (CF) as used in supervised learning (SL), and I explain below why. The FF, RF, and CF are used to evaluate the individuals, actions, and predictions, respectively, hence they can all be thought of as evaluation functions (although this latter term has a more specific meaning in the context of search algorithms, like A*). Their primary difference is their purpose and how they are used (i.e. for which problems they are used or what they evaluate), and not much what they return, which is typically a number (in all cases).
Reward function
As stated in the question, an RF can be viewed as evaluating different situations, depending on its definition or what we are interested in.

$r(s)$ evaluates the goodness of being state $s$
$r(s, a)$ evaluates the goodness of taking $a$ in the state $s$
$r(s, s')$ evaluates the goodness of being in state $s$, at the current state time step, then, independently of the action $a$ taken in $s$, ending up in state $s'$
$r(s')$ similar to $r(s)$
$r(s, a, s')$ the quality of being in state $s$, taking action $a$ and ending up in state $s'$.

Although I will not dwell on the details in this answer (and you can find more details here), depending on the problem or the RL algorithms that you want to use to solve the problem, one definition may be more interesting or useful than another.
Fitness function
In evolutionary algorithms (EA), such as genetic algorithms (GA) or genetic programming (GP), the solutions are generally known as individuals, which can be represented in different ways depending on the specific approach.
However, in all cases, we often distinguish between genotypes (aka genomes or chromosomes), which are representations of the actual solutions to a problem, which are more amenable to changes (i.e. to the mutation and crossover operations), and phenotypes, which are the actual solutions to the problem. The reason why we use genotypes is that, often, it's easier to find solutions in a different but related space rather than in the original space of solutions, although some EAs can also just work with phenotypes.
To be more concrete, in traditional genetic algorithms, the genotypes are binary vectors $\{0, 1 \}^N$, which restricts the space of possible solutions, which, in certain cases, it's a good thing, because the original space may be too huge (so it may be harder to converge to a good solution). These binary vectors can then be converted to the actual solutions using some encoding-decoding mechanism that we need to specify depending on the problem. More precisely, maybe each element of a binary vector corresponds to some binary choice in some game where you need to take a sequence of choices, and each time you can either say "yes" or "no".
So, in EAs, an FF evaluates the quality (or fitness) of an individual and, more precisely, either a genotype or a phenotype (depending on the representation of the solutions).
Often, the fitness function is really a cost function (CF), like in supervised learning. For example, if you want to solve a symbolic regression problem using genetic programming (i.e. find an analytical or closed-form expression of a function), then the fitness function is really just a cost function, i.e. an individual would be like a prediction and the label would be generated by the actual true function (provided that we know it). More concretely, let's say that we want to find the analytical expression
$$f(x) = x^2.$$
In this case, we can generate a labeled dataset of input-output pairs by just evaluating $f$ at different inputs, so we may get the following labeled dataset
$$
D = \{(1, 1), (2, 4), (3, 9) \}
$$
We can then evaluate an individual, which in the case of GP is a function (or program) $g(x)$, using e.g. the mean squared error (MSE). For example, if we have the individual $g(x) = x^3$, we can compute the mean squared error as follows
$$
\text{MSE}(D, g(x)) = \frac{1}{3} \left( (1 - 1)^2 + (4 - 8)^2 + (9  - 27)^2 \right)
$$
So, in this case, the FF is the MSE. Of course, we could have bigger datasets than $D$. In any case, the point is that you can use GP to solve SL problems.
You could also use EAs to solve other types of problems, i.e. not just SL problems, for instance, RL or unsupervised learning problems. In the case of RL problems, the FF is more similar to an RF in RL, given that you will probably need to define the FF as a function that evaluates the qualities of actions, states, or combinations of these.
So, to conclude, the definition of the FF in EAs depends on the problem that you want to solve, and it can be more similar to an RF or CF, depending on the problem you want to solve.
Further reading
If you are interested in how to design reward functions or fitness functions for your problem, you can take a look at this (and this) and this questions, respectively. This answer provides a brief explanation of the difference between RL and EAs.


What happens with policy gradient methods if rewards are differentiable? I would like some help with understanding why there is no explicit flow of information from the reward gradient to the parameters of the policy in policy gradient methods.
What I mean is the following, there are 2 scenarios:
1st - deterministic framework with given initial state $s_0$, actions $a_t = \mu_\theta(s_t)$, rewards $r(s_t, a_t, s_{t+1})$, and transitions $s_{t+1}=f(s_t, a_t)$. Assume all of these things are differentiable (maybe all is continuous). By drawing the computational graph I found I can compute the gradient of $J(\mu_\theta) = \sum_{t} r(s_t, a_t, s_{t+1})$ with respect to $\theta$. I could optimize for cumulative reward by doing gradient ascent on this objective.
2nd - framework in https://spinningup.openai.com/en/latest/spinningup/rl_intro3.html#id16 , which seems general, reading $\nabla_\theta J(\pi_\theta) = \nabla_\theta E_{\tau \sim \pi_\theta}[R(\tau)] = E_{\tau \sim \pi_\theta}[R(\tau)\sum_{t=0}^T \nabla_\theta \log{\pi_\theta (a_t | s_t)}]$.
What I don't understand (and I certainly feel confused about in an ignorant way) is why the derivation assumes that $\nabla_\theta R(\tau) = 0$ when this scenario (as it is stochastic) should include the 1st as a particular case, which does have a derivative!
It makes sense that $R(\tau)$ is only affected by $\theta$ through the change in probability of the trajectories $\tau$, but it still feels strange that $\tau = (s_0, a_0, \dots)$ is indeed one sample of $\tau = (s_0\sim \rho(s_0), a_0 \sim \pi_\theta(s_0), \dots)$ which depends on $\theta$. The deterministic reduction is obvious, but one could also think about reparametrization tricks in order to show the same point.
In other words, if the reward function were differentiable, i.e. fully differentiable known environment, how could I use this information?

That's exactly the point of the Policy Gradient Theorem. Let's go through he proof of this theorem - it relies on our ability to "loop" the reward expression $J(\theta,s)$, expressing it through $J(\theta,s')$ in the next state:
$$J(\theta,s) = \mathbb{E}_{\tau\sim\pi_\theta}\left[ R(\tau) | s_0 = s\right]$$
$$\begin{align}
J(\theta,s) & = \sum_a\pi_\theta(a|s)\sum_{s',r}P(s',r|s,a)(r + J(\theta, s'))\\
& = \sum_aJ(\theta,a,s)
\end{align}
$$
Here, I've introduced the notation $J(\theta,a,s)$ to keep further derivation sane. Taking the gradient:
$$\begin{align}
\nabla_\theta J(\theta,s) = \sum_{a}\left(\vphantom{\sum_a}\right.&\nabla_\theta  \pi_\theta(a|s) \left(\sum_{s',r}P(s',r|s,a)(r + J(s',\theta))\right)  + \\
&+\pi_\theta(a|s) \nabla_\theta \sum_{s',r}P(s',r|s,a)(r + J(s',\theta)\left.\vphantom{\sum_a}\right)\end{align}
$$
With the first term in the sum we do the log trick:
$$
\frac{\nabla_\theta  \pi_\theta(a|s)}{\pi_\theta(a|s)} \left(\pi_\theta(a|s)\sum_{s',r}P(s',r|s,a)(r + J(s',\theta))\right) = J(\theta,a,s)\nabla_\theta\log\pi_\theta(a|s)
$$
And the second term simplifies to:
$$\pi_\theta(a|s) \nabla_\theta \sum_{s',r}P(s',r|s,a)(r + J(s',\theta)) =
\pi_\theta(a|s)  \sum_{s'}P(s'|s,a) \nabla_\theta J(s',\theta)
$$
The last equality is exactly where we loose the rewards $r$ - the gradient of the constant $r$ is zero, and we can sum over $r$ because of the transition probability normalization $\sum_{r}P(s',r|s,a) = P(s'|s,a)$.
So we've finally get the expression for the gradient:
$$\nabla_\theta J(\theta,s) = \sum_{a}\left(J(\theta,a,s)\nabla_\theta\log\pi_\theta(a|s) + \pi_\theta(a|s)  \sum_{s'}P(s'|s,a) \nabla_\theta J(s',\theta) \right)$$
The Policy Gradient Theorem proof goes on though a couple more steps: unroll the last expression, rewrite through the distribution over states, then convert back from summation to the expectation over trajectories -- going through all this in detail here would too long. While we've already passed the crucial point for your question - we've got rid of the gradient of the rewards.
Edit:
In response to your comment, let me just stress again that this expression is a statement of the Policy Gradient Theorem.
$$\nabla_\theta J(\theta) = \mathbb{E}_{\tau\sim\pi}\left[R(\tau)\sum\nabla_\theta\log \pi_\theta(a_t|s_t)\right]$$
The proof of Policy Gradient Theorem is pretty involved and certainly is not as simple as saying that $\nabla_\theta R(\tau) = 0$. Some authors abuse notation or cut corners when going through the proof of the theorem - for a reasonably strict exposition of the PG theorem I recommend Sutton and Barto, Chapter 13.
Another potential point of confusion is the notation $r(s_t,a_t,s_{t+1})$ that you've been using. In the most general MDP formulation rewards are random variables $r$. The probability of getting a reward $r$ and ending up in state $s_{t+1}$ is encoded in the transition probability $P(s_{t+1},r|s_t,a_t)$. (This covers the case of deterministic rewards by having a deterministic distribution over $r$ ). The derivation above uses this, most general, formulation of the MDP.


Which movies have the most realistic artificial intelligence? I want to give some examples of AI via movies to my students. There are many movies that include AI, whether being the main character or extras.
Which movies have the most realistic (the most possible or at least close to being made in this era) artificial intelligence?

Just A Rather Very Intelligent System (J.A.R.V.I.S.) in Iron Man (and related films, such as The Avengers) is something (a personal assistant) that people are already trying to develop, so JARVIS is a quite realistic artificial intelligence. Examples of existing personal assistants are Google Assistant (integrated into Google Home devices), Cortana, Siri and Alexa. There are other virtual assistants, but, unfortunately, there aren't many reliable open-source ones. Note that JARVIS is way more intelligent and capable than the other mentioned personal assistants.

Similarly, HAL 9000, in 2001: A Space Odyssey, is a sentient artificial intelligence which can be considered a personal assistant.


What are the best hyper-parameters to tune in reinforcement learning? Obviously, this is somewhat subjective, but what hyper-parameters typically have the most significant impact on an RL agent's ability to learn? For example, the replay buffer size, learning rate, entropy coefficient, etc.
For example, in "normal" ML, the batch size and learning rate are typically the main hyper-parameters that get optimised first.
Specifically, I am using PPO, but this can probably be applied to a lot of other RL algorithms too.

Personally, I would choose the following two as the most important:

epsilon: When using an epsilon-greedy policy, epsilon determines how often the agent should explore and how often it should exploit. Balancing exploration and exploitation is crucial for the success of the learning agent. Too little exploration might not teach anything to the agent and too much exploration might just waste your time.
learning rate: The learning rate determines how fast do you learn from new states of experience. A learning rate that is too high might not be good in cases when the environment has many states with high probabilities of negative rewards, i.e. many penalizations. This might make your agent move back and forth in the same place in order to avoid getting penalized. Also, a learning rate that is too low might make your agent learn very slowly and depending on your epsilon, the agent might enter a phase of exploitation with very little knowledge of an optimal policy.


Doubt regarding the proof of convergence of $\epsilon$ soft policies without exploring starts In page 125 of Sutton and Barto (second last paragraph) the proof for equality of $v_{\pi}$ and $v_*$ for $\epsilon$ soft policies is given. But I could not understand the statement explaining the proof:

  Consider a new environment that is just like the original environment, except with the requirement that policies be $ε$-soft “moved inside” the environment. The new environment has the same action and state set as the original
  and behaves as follows. If in state $s$ and taking action $a$, then with probability
  $1 − ε$ the new environment behaves exactly like the old environment. With
  probability $ε$ it repicks the action at random, with equal probabilities, and
  then behaves like the old environment with the new, random action. The best
  one can do in this new environment with general policies is the same as the
  best one could do in the original environment with $ε$-soft policies.

What is the meaning of environment here? And what is this new thing/argument (provided above) the authors are describing to arrive at the proof?

Let's first clarify a couple of details:

The policy $\pi$ we're talking about is an $\epsilon$-soft policy (defined to mean that $\pi(a \vert s) \geq \frac{\epsilon}{\vert \mathcal{A}(s) \vert}$ for all states and all actions).
We're not trying to prove equality of $v_{\pi}$ and $v_*$, but of $v_{\pi}$ and $\tilde{v}_*$, where $\tilde{v}_*$ denotes the optimal value function in this "new environment" that we're constructing.

So, "environment" is basically the "world" that our agent "lives" and acts in. You can think of it as the "rules" that we "play" by. So, you could think of the definitions of our complete state and action spaces as part of the environment, and the function that tells us which successor state $s'$ we end up in whenever we pick an action $a$ in a state $s$ (i.e. the state transition dynamics) are a part of the environment. And the function that tells us what Rewards we'll obtain in what situations is also a part of the environment. The policy $\pi$ is not a part of the environment; this is the "brain" of the agent itself.

Now, recall that here we're not interested in proving that $v_{\pi}$ moves towards the true optimal value function $v_*$ of the "real" environment. We know for a fact that we won't ever become completely equal to that, because we're forcing our policies to have exploratory behaviour by requiring them to be $\epsilon$-soft, so it would be hopeless to prove such a thing. Instead, we're interested in proving that $v_{\pi}$ will move towards whatever value function is the best one that we could possibly achieve under the restriction that we must have an $\epsilon$-soft policy.

What we do in the book here is that we slightly "transform" our environment into a new environment (i.e. we change the rules that we play by just a little bit). This is done in a clever way, such that the thing I just described that we want to prove becomes mathematically equivalent to just proving that $v_{\pi}$ moves towards (or becomes equal to) $\tilde{v}_*$. Now, if we can prove this for the new environment, we'll automatically have proven the thing that we actually wanted to prove for the "real" environment.


Getting better results in improving the configuration Currently, I found the right recipe for a time series regression problem to finally get acceptable to good results.

Here is the config file

{
    "data": {
        "sequence_length":45,
        "train_test_split": 0.85,
        "normalise": false,
        "num_steps": 10
    },
    "training": {
        "epochs":30,
        "batch_size": 32
    },
    "model": {
        "loss": "mse",
        "optimizer": "adam",
        "layers": [
            {
                "type": "lstm",
                "neurons": 161,
                "input_timesteps": 45,
                "input_dim": 161,
                "return_seq": true,
                "activation": "relu"
            },
            {
                "type": "dropout",
                "rate": 0.1
            },
            {
                "type": "lstm",
                "neurons": 161,
                "activation": "relu",
                "return_seq": false
            },
            {
                "type": "dense",
                "neurons": 128,
                "activation": "relu"
            },
            {
                "type": "dense",
                "neurons": 1,
                "activation": "linear"
            }
        ]
    }
}

Here is the results I got

What can be good improvements I can bring to my model so that I can get better results? There are a lot of small spikes and other places where the curve is rather constant that I should get a rise or fall of the curve.

Try using an RMSProp optimizer instead of Adam optimizer. Also try decreasing the batch size and keep a small learning rate like 0.001.


What chatbots can answer this type of simple question that only requires to keep track of the context? I have tried with two chat-bots Cleverbot and Alan, and I got disappointing results.

me: Socrates is a man
bot: blah blah (common bot nonsense instead of an "ok")
me: Who is a man?

alan1: The people that write my answers haven't provided an answer for
this.

Another example of the mediocre "clever bot"

me: Socrates is the name of my dog.
clever bot: I don't know!
me: What is the name of my dog?
clever bot: That's a nice name.

Another example.

me: Socrates is a man.
clever bot: When does the narwhal bacon?
me: Who is a man?
clever bot: Men are man.

And they dare name this thing "clever"...
So, is there any chatbot that can actually answer this straightforward question?

I think the issue here is that the chatbots you're using aren't very good at "short-term memory". What I mean by is that the bots construct responses that are slowly and incrementally tuned according to the overall usage of the chat bot, from every user. The bots are responding to each message based on how a new user would expect them to. As Alan1 notes, "Men are Man". It's making this response based solely off your single most recent message.

Instead, you are looking for a bot who focuses moreso on persistent memory of the individual conversation. The problem here becomes you're now almost asking for a Natural Language Parser, a big problem many people are working on and something that's years away from existing as robustly as you suggest.

The chat bot not only has to recognize the words 'Socrates', 'Name', and 'Dog'; but that in this sentence, it's the dog's name that is Socrates. That's a lot of information to gain beyond just the words. Which is why from a server / implementation standpoint, the above method is also a lot easier to program (every message just query your server, no need to maintain state - that is, memory of the conversation).

The chat bots can't possibly get enough information from one person to train how to speak and respond, so they 'crowd-source' that information for training. But that means that Clever Bot (or any similar caliber chat bot) won't respond in terms of parsing the meaning of what you're asking.

Taking this even further, one can consider the notion of such a program being Turing-Complete. Supposing we had a chat bot like you're suggesting, we could perhaps show equivalence to a Turing-Machine, or even perhaps show we can do something like decide the halting problem. Off the top of my head I imagine the procedure being basically showing you would be able to decide halting given initial conditions. E.g. Given "Socrates is a man" and "All men die" can we decide if the chat bot will ever be able to deduce if Socrates dies?

I'll work on a formal proof from the latter and post it if it works out.


Machine Learning in relation to personality and behaviors predictions I am tasked with making a machine learning model that predicts personality traits and behaviours of children based on simple and interactive quizzes.
Currently I am lost and have no idea where to start!
I am looking for guidance and where can start my research and the actual coding part and is NLP a good place to start from.

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

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

Another comercial tool is Symanto:

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

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


Why is the Turing test so popular? I know there are different AI tests but I'm wondering why other tests are little-known. Is the Turing test hyped? Are there any scientific reasons to prefer one test to the other?

  Why is the Turing test so popular?

Because it is:

Easy to explain. (Its essentially a game, the "imitation game")
Intuitively plausible as a metric.
The idea of "people v.s. AI" is very marketable.
At the time we thought that we can analyze cognition strictly in terms of input/output (per behaviorism). Cognitivism, embodied cognition, developmental cognition are all sub-fields that have a right to challenge the Turing Test, but they weren't developed at the time of Turing.

Of course, it also helps that Turing is a very important figure in AI/CS.


Can neuro-evolution methods be combined with A3C? As a amateur researcher and tinkerer, I've been reading up on neuro-evolution networks (e.g. NEAT) as well as the A3C RL approach presented by Mnih et al and got to wondering if anyone has contemplated the merging of both these techniques.

Is such an idea viable? Has it been tried?

I'd be interested in any research in this area as it sounds like it could be compelling.

Is such an idea viable?

Yes.

One approach that should work in terms of underlying theory is to start with population of NEAT-generated networks that describe the policy, and instead of measuring fitness of them on the task whilst keeping all weights static, measure fitness whilst applying any policy gradient algorithm like A3C. In addition, the final weights of the networks could be fed into the next generation. A bit Lamarckian* perhaps, but that is already a thing in evolutionary algorithms.

  Has it been tried?

Yes, a recent paper (July 2018) is "NEAT for large-scale reinforcement learning through evolutionary feature learning and policy gradient search".

I suspect there are more, including hobby efforts without academic publishing, but that is the first paper that popped up on a brief search.

* Jean-Baptiste Lamarck believed that offspring of animal parents could inherit traits based on parental behaviour and desires, such as a giraffe's neck evolving over time as the animals strived to reach higher food sources. Interestingly, although the core of this theory is not generally accepted, recent theories around phenotypic plasticity and discoveries in epigenetics show that biological systems can make use of the idea - although very far from the idea of children using parental memories directly to aid in tasks (which has more in common with science fiction for humans, but possible in neural networks where we can "copy brains").


Choice of inputs features for Snake game I am designing a neural network using Deep Q-Learning, which teaches an agent how to play Snake (The classic Nokia game from the 90'ies). The goal of the game is to navigate the snake on a playing field (2D), and to eat a randomly placed fruit. As the Snake eats the fruit, it grows in length. The game ends if the snake hits the game border, or it self, so as the number of fruits consumed increases, so does the difficulty of navigating without hitting something.

I have trained the Snake game on a 10x10 playing field using the following inputs:

x direction of the snake
y direction of the Snake
The fraction of playing field occupied by the snake itself
A bool which says if the fruit is in front of the snake (from it's current direction)
A bool which says if the fruit is to the left of the snake (from
it's current direction)
A bool which says if collision (game over) in front of the snake is possible
A bool which says if collision to the right is possible
A bool which says if collision to the left is possible

With this choice of inputs I am getting the Snake agent to work reasonably well, and score until it plateaus out. I have examined the cases where the snake dies, and it all happens when it has no way of escaping, for example, it turns around and blocks its own path, until it finally has no where to go. This is more likely to happen as the Snake increases in lenght.

I was thinking on how I could improve this performance. It seems to me, that the reason the Snake can make a self-blocking turn is because of the inputs. Since the path it takes is clear, there's no information, that the next path is not, or that continuing further down will eventually lead to game over. If the Snake agent was aware of all obstacles in each step, i.e. the entire state-space, then I could imagine that would help train the network towards finding the optimal path without ending up blocking itself.

Since I have made the Snake game myself, I can return to the agent a matrix, or an unfolded vector, which contains the inputs for each column / row on the playing field. A blocked cell would be set to 0, a free cell 1, the fruit cell has value 0.75 and the snake head (which moves) could be assigned value 0.25. After trying this approach, I have to say I was unsuccesful. The snake ends up just turning in circles, even if I use the same reward system as the 8 input case shown above.

I am therefore trying to understand what is happening here. Am I missing information? I would think the full 10x10 state space would give me exactly enough information to lead to the correct evaluation of the next path. I would very much like to hear someone elses input to this approach.

Thanks a lot

Before we start to tweak with you Agent-Environment setup, there are couple of important things to note

Q-Learning

Q-learning as a fundamental is a greedy approach based on Action Value functions. When I say action value what I mean to say is this
$q_\pi(s,a) = p(\hat{s},r | s, a)[r + \gamma(V(\hat{s}))]$.

This means according to $\pi$ policy the Action value for taking action "$a$" at state "$s$" is the probability of taking reaching state "$\hat{s}$" and getting a reward "$r$" given the current state is "$s$" and action taken is "$a$" multiplied by sum of immediate reward "$r$" and expected future reward given by future state value(s) "$V(\hat{s})$".

Please note the $p(\hat{s},r | s, a)$ is only available in deterministic modelling technique (model based methods) and this part is not available for stochastic modelling techniques (model-free methods). For model-free methods we execute multiple experiments and take the expected value in accordance with Law of Large Numbers. Which is what we do in common Deep Reinforced Learning implementations.

The above formulation for future rewards can be expanded in series using the state-value formulation as $V(s) = \pi(a,s)q_\pi(s,a)$, where $\pi$ is the policy we are following aka probability of taking action $a$ when in state $s$.

Why is it termed Greedy?

This is because while using the fundamental of multiple experiments, with every action I take the immediate reward, and the max q_value ($q$) associated with the next_state to update my current q_value.

In Q-learning the future state reward is what you calculate by submitting the next_state to the network and taking max of the q_values attained. (Hence, Greedy!!)

Crux of the above

Having said all the above (Duh!), what is in it for us?

In Q-Learning, your reward is key for your model learn, i.e. "$r$" immediate reward and the future reward ($V(\hat{s})$)

When the state-space is limited

For example, a numerical tic-tac-toe game, in such cases it is ideal to have discrete reward system, such as the one suggested by you.
When the state-space is very large (the problem statement you are tackling)

In such cases, it is ideal to have a continuous reward mechanism, i.e. rewards should be more variable in nature, like continuous values.
Suggestions

You can define the reward function in the environment has the 10$\sqrt{2}$ - Euclidean distance between the face of your snake and the fruit it is trying to reach. The reason I am doing it (10$\sqrt{2}$ minus) is because the maximum distance could be 10$\sqrt{2}$ (considering it is 10X10 board). This would help you to have a more variable/continuous rewards for your model to learn with (since you are using neural networks for training them). As your Snake goes closer to the fruit this value will keep on increasing. One cavet, if by taking an action, your snake reaches fruit, you can provide it a specific constant (extra) reward, and if it hits its own self, or the borders you penalize it with a specific constant. So that the model understand better.
You can define your state (input vector to your NN) as 100 dimension array (10X10 grid) with each element signifying if there a object in the that area or not. 1 means it is fruit, 0 means it is snakes own body and 0.5 means it is free for movement. The idea is to limit the input values of the vectors between 0~1.  As your agent takes action, the values in the state will keep on changing.
The output of your network should have 3 neurons, each signifying the $q$ of each of action (front/right/left movement). For get_action function you will get the action pertaining to max(q_value), and keep on adding things in your memory d_que. Subsequently you can trigger model_train methods at every episode/or even at after every step.
Lastly, the hyper parameters would be the discount factor $\gamma$ you choose and the learning rate $\alpha$ you use for the NN network. That's something you will have to experiment. Along the depth of your ANN. I think a single hidden layer should be enough.
For the last layer of your NN, please use a linear activation function, and not a relu activation function.
Please run many-many-many experiments, something in millions for optimum training. There could be multiple ways of monitoring your model's learning process. How many games won, how much fruit eating it is able to achieve in 1 game etc.

Hope the above helps.


What is geometric deep learning? What is geometric deep learning (GDL)?
Here are a few sub-questions

How is it different from deep learning?
Why do we need GDL?
What are some applications of GDL?

To complete the first answer that is rather graph oriented, I will write a little about deep learning on manifolds, which is quite general in terms of GDL thanks to the nature of manifolds.

Note that the description of GDL through the explanation of what are DL on graphs and manifolds, in opposition to DL on euclidean domains, comes from the 2017 paper Geometric deep learning: going beyond Euclidean data (this paper is excellent at clarifying both the intuition and the mathematics of what I'm writing).

1. In case you don't know what a manifold is

As the previously cited paper puts it:

  Roughly, a manifold is a space that is locally Euclidean. One of the
  simplest examples is a spherical surface modeling our planet: around a
  point, it seems to be planar, which has led generations of people to
  believe in the flatness of the Earth. Formally speaking, a
  (differentiable) d-dimensional manifold X is a topological space where
  each point x has a neighborhood that is topologically equivalent
  (homeomorphic) to a d-dimensional Euclidean space, called the tangent
  space.

Good other not-so-technical explanation on stats.stackexchange

Other Wikipedia examples to develop not too abstract understanding

Very shortly put, it's an interesting mathematical set on which to work (different kinds exist, see papers at the end of this answer for DL related manifolds uses). By work, you can typically understand that you constrain the neural net parameters to the manifold you chose (e.g. training with parameters constrained on a hypersphere, among the geomstats paper examples).

Your data can also be represented thanks to a practical manifold. For example, you can choose to work on images and videos by representing the samples using Symmetric Positive Definite (SPD) matrices (see this paper), the space of SPD matrices being a manifold itself.

2. Why bother learning on manifolds ?

Defining a clearer/better adapted set (understand that it's a sort of constraint!) on which to learn parameters and features can make it simpler to formally understand what your model is doing, and can lead to better results. I see it as a part of the effort of deep learning formalization. One could say you're looking for the best information geometry for your task, the one that best captures the desirable data distribution properties.To develop this intuition consider the solar system analogy for manifold learning of this Kaggle kernel:

  Perhaps a good analogy here is that of a solar system: the surface of our planets are the manifolds we're interested in, one for each digit. Now say you're on the surface of the earth which is a 2-manifold and you start moving in a random direction (let's assume gravity doesn't exist and you can go through solid objects). If you don't understand the structure of earth you'll quickly find yourself in space or inside the earth. But if you instead move within the local earth (say spherical) coordinates you will stay on the surface and get to see all the cool stuff.

This analogy reminds us of the spherical surface planet model from Bronstein's paper already quoted above. This paper also describes a typical case for which manifolds are interesting: where graphs (the other example of GDL/DL on non euclidean data) are better at handling data from social or sensor networks, manifolds are good at modeling 3D objects endowed with properties like color texture in computer vision.

3. Regarding deep neural networks on manifolds

I would advise reading the geomstats associated paper, which does a great job at showing what it is and how it can be used, along with example codes (e.g. MNIST on hyperspheres manifold example code here). This library implements manifolds and associated metrics on Keras. The choice of metrics is essential to understand the point of working on manifolds: it's because you need to work on an adapted mathematical set (ie with the right properties) with an adapted distance definition (so that the measure actually means something when considering the problem you're trying to solve) that you switch to working on manifolds.

If you want to dive in the details and examples of deep learning on manifolds here are some papers:

A Riemannian Network for SPD Matrix Learning: new backpropagation to learn SPD matrices on Riemannian manifolds
Learning a Robust Representation via a Deep Network on Symmetric Positive Definite Manifolds: using SPD matrices to aggregate convolutional features

4. Why Riemannian manifolds ?

TL;DR: you need a metric to do machine learning (otherwise, how could you evaluate how much you actually learned !)

Still based on Bronstein's paper:

  On each tangent space, we define an inner product [...]. This inner
  product is called a Riemannian metric in differential geometry and
  allows performing local measurements of angles, distances, and
  volumes. A manifold equipped with a metric is called a Riemannian
  manifold.

5. What's the relation between a Riemannian manifold and a Euclidean space ?

Still based on Bronstein's paper:

  a Riemannian manifold can be realized as a subset of a Euclidean space
  (in which case it is said to be embedded in that space) by using the
  structure of the Euclidean space to induce a Riemannian metric.

I leave the details to the paper, otherwise this answer will never end.

6. Answers to questions in comments

Will only answer once I think I've found a relatively well-argued answer, so won't answer everything at once.

Isn't manifold learning just a way of dimensionality reduction?

I don't think so, it isn't just that. I haven't seen any dimensional reduction constraint (yet ?) in the papers I've read (cf. geomstats again).

In the hypersphere/MNIST geomstats code example, you can see the chosen manifold dimension hypersphere_dimension = 17. Since we're working with MNIST data I guess this would mean a dimension reduction in this particular case. I admit I would need to check exactly what that dimension implies on the neural net architecture, I haven't discussed my understanding of this yet.

Disclaimer

I'm still developing a more rigorous mathematical understanding of manifolds, and shall update this post to make additional necessary clarifications: exactly what can be considered as a manifold in a traditional deep learning context, why do we use the word manifold when speaking about the hidden state of auto-encoders (see the previously cited Kaggle kernel that quotes Goodfellow's book on this). All of this if the perfectly clear answer doesn't show up here before !


What is the proof that policy evaluation converges to the optimal solution? Although I know how the algorithm of iterative policy evaluation using dynamic programming works, I am having a hard time realizing how it actually converges.

It appeals to intuition that, with each iteration, we get a better and better approximation for the value function and we can thus assure its convergence, but with this said simply, it seems that this method is very inefficient contrary to the reality that it actually is quite efficient.

What is the rigorous mathematical proof of the convergence of the policy evaluation algorithm to the actual answer? How is it that the value function obtained this way is close to the actual values computed by solving the set of bellman equations?

First of all, efficiency and convergence are two different things. There's also the rate of convergence, so an algorithm may converge faster than another, so, in this sense, it may be more efficient. I will focus on the proof that policy evaluation (PE) converges. If you want to know about its efficiency, maybe ask another question, but the proof below also tells you about the rate of convergence of PE.

What is the proof that policy evaluation converges to the optimal solution?

To provide some context, I will briefly describe policy evaluation and what you need to know to understand the proof.
Policy evaluation
Policy evaluation (PE) is an iterative numerical algorithm to find the value function $v^\pi$ for a given (and arbitrary) policy $\pi$. This problem is often called the prediction problem (i.e. you want to predict the rewards you will get if you behave in a certain way).
Two versions: synchronous and asynchronous
There are (at least) two versions of policy evaluation: a synchronous one and an asynchronous one.
In the synchronous version (SPE), you maintain two arrays for the values of the states: one array holds the current values of the states and the other array will contain the next values of the states, so two arrays are used in order to be able to update the value of each state at the same time.
In the asynchronous version (APE), you update the value of each state in place. So, first, you update the value of e.g. $s_1$, then $s_2$, etc., by changing your only array of values (so you do not require a second array).
SPE is similar in style to the numerical method called Jacobi method, which is a general iterative method for finding a solution to a system of linear equations (which is exactly what PE is actually doing, and this is also explained in the cited book by Sutton and Barto). Similarly, APE is similar in style to the Gauss–Seidel method, which is another method to solve a system of linear equations.
Both of these general numerical methods to solve a system of linear equations are studied in detail in Parallel and Distributed Computation Numerical Methods (1989) by Bertsekas and Tsitsiklis, which I haven't read yet, but provides convergence results for these numerical methods.
The book Reinforcement learning: an introduction by Sutton and Barto provides a more detailed description of policy evaluation (PE).
Proof of convergence
I will provide a proof for the SPE based on these slides by Tom Mitchell. Before proceeding, I suggest you read the following question  What is the Bellman operator in reinforcement learning? and its answer, and you should also get familiar with vector spaces, norms, fixed points and maybe contraction mappings.
The proof that PE finds a unique fixed-point is based on the contraction mapping theorem and on the concept of $\gamma$-contractions, so let me first recall these definitions.

Definition ($\gamma$-contraction): An operator on a normed vector space $\mathcal{X}$ is a $\gamma$-contraction, for $0 < \gamma < 1$, provided for all  $x, y \in \mathcal{X}$
$$\| F(x) - F(y) \| \leq \gamma \| x - y\|$$
Contraction mapping theorem: For a $\gamma$-contraction $F$ in a complete normed vector space $\mathcal{X}$

Iterative application of $F$ converges to a unique fixed point in $\mathcal{X}$ independently of the starting point

at a linear convergence rate determined by $\gamma$

Now, consider the vector space $\mathcal{V}$ over state-value functions $v$ (i.e. $v \in \mathcal{V})$. So, each point in this space fully specifies a value function $v : \mathcal{S} \rightarrow \mathbb{R}$ (where $\mathcal{S}$ is the state space of the MDP).
Theorem (convergence of PE): The Bellman operator is a $\gamma$-contraction operator, so an iterative application of it converges to a unique fixed-point in $\mathcal{V}$. Given that PE is an iterative application of the Bellman operator (see What is the Bellman operator in reinforcement learning?), PE finds this unique fixed-point solution.
So, we just need to show that the Bellman operator is a $\gamma$-contraction operator in order to show that PE finds this unique fixed-point solution.
Proof
We will measure the distance between state-value functions $u$ and $v$ by the $\infty$-norm, i.e. the largest difference between state values:
$$\|u - v\|_{\infty} = \operatorname{max}_{s \in \mathcal{S}} |u(s) - v(s)|$$
Definition (Bellman operator): We define the Bellman expectation operator as
$$F^\pi(v) = \mathbf{r}^\pi + \gamma \mathbf{T}^\pi v$$
where $v \in \mathcal{V}$, $\mathbf{r}^\pi$ is an $|\mathcal{S}|$-dimensional vector whose $j$th entry gives $\mathbb{E} \left[ r \mid s_j, a=\pi(s_j) \right]$ and $\mathbf{T}^\pi$ is an $|\mathcal{S}| \times |\mathcal{S}|$ matrix whose $(j, k)$ entry gives $\mathbb{P}(s_k \mid s_j, a=\pi(s_j))$.
Now, let's measure the distance (with the $\infty$-norm defined above) between any two value functions $u \in \mathcal{V}$ and $v \in \mathcal{V}$ after the application of the Bellman operator $F^\pi$
\begin{align}
\| F^\pi(u) - F^\pi(v) \|_{\infty}
&= \| (\mathbf{r}^\pi + \gamma \mathbf{T}^\pi u) - (\mathbf{r}^\pi + \gamma \mathbf{T}^\pi v)\|_{\infty} \\
&= \| \gamma \mathbf{T}^\pi (u - v)\|_{\infty} \\
&\leq \| \gamma \mathbf{T}^\pi ( \mathbb{1} \cdot \| u - v \|_{\infty})\|_{\infty} \\
&\leq \| \gamma (\mathbf{T}^\pi \mathbb{1}) \cdot \| u - v \|_{\infty}\|_{\infty} \\
&\leq \gamma \| u - v \|_{\infty}
\end{align}
where $\mathbb{1} = [1, \dots, 1]^T$. Note that $\mathbf{T}^\pi \cdot \mathbb{1} = \mathbb{1}$ because $\mathbf{T}^\pi$ is a stochastic matrix.
By the Bellman expectation equation (see Barto and Sutton's book and What is the Bellman operator in reinforcement learning?), $v^\pi$ is a fixed-point of the Bellman operator $F^\pi$. Given the contraction mapping theorem, the iterative application of $F^\pi$ produces a unique solution, so $v^\pi$ must be this unique solution, i.e. SPE finds $v^\pi$.
Notes
I didn't prove the contraction mapping theorem, but you can find more info about the theorem and its proof in the related Wikipedia article.


How to represent integer values in sequence to sequence prediction task in encoder-decoder LSTM? I have a large 2D grid having 30k rows and 35k columns, so a total of 30x35k grid cells. Each grid cell is represented by a unique integer number (identity of grid cell). I have several trajectories that passes through these grid cells. Each trajectory is represented by a sequence of numbers (that are grid cells through which the trajectory passes through).

I want to solve the problem of trajectory prediction by giving the partial trajectory as input and predict the full trajectory. This becomes a sequence to sequence problem, where all sequences are integer values by default.

I am trying to solve this problem through encoder-decoder LSTM architecture. Most tutorials/examples regarding sequence to sequence on net are on machine translations in which vocabularies or characters are one-hot-encoded to represent the text as integer values. When I hot-encode my sequence values the one-hot vector becomes very large because there are (30x35)k grid cells, the program has given memory overflow error (because each vector has of size 1 million).

I am confused here, do I need to treat grid identity as categorical variable? because all grid identities are numeric numbers but these identities are not comparable (like prices).

Do I need to hot-encode my integer values in my sequence? Or is there any other alternative to solve this problem? I also appreciate if you suggest me the similar tutorials having the sequence to sequence prediction problem.

One hot encoding helps a lot. You can actually one hot encode each batch just before the training to reduce memory usage. One hot encoding makes the input data more intuitive for the network as a numeric value requires the network to do multiple comparisons to understand the value. For examples please tell me which deep learning framework you are using so I can give you some links or code. Hope I can help you.


What are standard datasets for fully connected neural networks? I am looking for datasets that are used as a testing standard in the fully connected neural networks (FCNN). For example, in the image recognition and CNN, CIFAR datasets are used in most of the papers, but can't find anything like that for the FCNN.

You can use MNIST obviously but I'd also suggest you have a look at UC Irvine's datasets: https://archive.ics.uci.edu/ml/datasets.php


Are A2C or A3C suitable for episodic tasks where the reward is delivered only at the end of the episode? My understanding of the main idea behind A2C / A3C is that we run small segments of an episode to estimate the return using a trainable value function to compensate for the unseen final steps of the episode.

While I can see how this could work in continuing tasks with relatively dense rewards, where you can still get some useful immediate rewards from a small experience segment, does this approach work for episodic tasks where the reward is only delivered at the end? For example, in a game where you only know if you win or lose at the end of the game, does it still make sense to use the A2C / A3C approach?

It's not clear to me how the algorithm could get any useful signal to learn anything if almost every experience segment has zero reward, except for the last one. This would not be a problem in a pure MC approach for example, except for the fact that we might need a lot of samples. However, it's not clear to me that arbitrarily truncating episode segments like in A2C / A3C is a good idea in this case.

My understanding of the main idea behind A2C / A3C is that we run small segments of an episode to estimate the return using a trainable value function to compensate for the unseen final steps of the episode.

This seems fairly accurate. The important thing to note is that the trainable value function is trained to predict values (specifically, advantage values of state-action pairs in the case of A2C / A3C, where the first A stands for "advantage"). These value estimates can intuitively be understood as estimates of long-term (discounted) rewards, they're not just short-term rewards.

So yes, initially when the agent only observes a reward at the end of a long trajectory, only state-action pairs close to the end will receive credit for that reward. For example, when using $n$-step returns, approximately only the last $n$ state-action pairs receive credit. However, in the next episode, that longer-term reward will already become "visible" in the form of an advantage value prediction when you're still $n$ steps away from the end, and then that update can again get propagated back $n$ steps further into the history of state-action pairs.

My explanation above is very informal... there are all kinds of nuances that I skipped over. Use of function approximation is likely to speed up the propagation of reward observations through the space of state-action pairs even more, and of course in reality things won't be as "clean" as getting the propagation to get $n$ steps further in the next episode in comparison to the previous episode, since selected actions and random state transitions can be different... but hopefully it gets the idea across.


Is There A Need For Stochastic Inputs To Mimic Real-World Biology And Environment? I'm kind of new to machine learning/AI, but I was wondering if using thresholds/fuzzy logic-like functions and even networks of dependent, stochastic variables that change over time (LTL maybe?), would be ample enough to emulate natural processes like emotions, hunger, maybe even pain.

My dilemma is whether creating a basic library to do this for the developer community is worth it if everything can be modeled more-or-less mathematically deterministic, even if the formulas are really complicated (see research like: https://engineering.stanford.edu/news/virtual-cell-would-bring-benefits-computer-simulation-biology).

My initial reasoning was biological processes are connected to psychological functionality (e.g., being hungry might make someone irritable, but that irritability may wear-off, which triggers different paths of thought but not others).  But these are so inter-dependent that it may be random or it is essentially PRNG, in order to properly simulate the mood fluctuations and biological processes computers don't have but humans do have.

Would we be better-off waiting for these complex physical/neurological models to come out?

Quite an interesting question, this sort of computational representation of biological systems are at the forefront of what we are trying to accomplish algorithmically.

This can be tackled via a variety of coordinate frames and problem formulations and could be thought of quite philosophically, as it pokes at some deep questions such as free-will and consciousness more generally.

For example, we could take the assumption that based on everything we know physically, the universe is completely deterministic. In this case, implementing deterministic functions for these variables makes quite a bit of sense and seems like the obvious choice. However, we can easily imagine that for at least some of this dynamic variables a stochastic representation would be both simpler(computationally) as well as giving better approximations to what we see in the real-world.

So it really is a question of how much value you see from implementing a system like this, and which representation you think would be most effective.


This is not a bug, assuming you hve implemented the SOM properly with best decay rules of learning rate and neighbourhood strength (in short best hyperparameters).

Think of the map as finding many local clusters in the Iris-Versicolor class. Since SOM's behave somewhat like k-means clustering, I would say this implies Iris Versicolor has many local clusters which are as closely knit together as the entire classes of Iris setosa and Iris virginica.


What is the difference between distant supervision and self-supervision? Weak supervision is supervised learning, with uncertainty in the labeling, e.g. due to automatic labeling or because non-experts labelled the data [1].
Distant supervision [2, 3] is a type of weak supervision that uses an auxiliary automatic mechanism to produce weak labels / reference output (in contrast to non-expert human labelers).
According to this answer

Self-supervised learning (or self-supervision) is a supervised learning technique where the training data is automatically labelled.

In the examples for self-supervised learning, I have seen so far, the labels were extracted from the input data.
What is the difference between distant supervision and self-supervision?

Is it that for self-supervision, the labels must come from the input data and for distant supervision it can come from anywhere (which would make self-supervision a type of distant supervision)?
Or must the labels from distant supervision come from somewhere else than the input data?
If "In robotics, this can be done by finding and exploiting the relations or correlations between inputs coming from different sensor modalities." then for self-supervised learning, the labels do not even have to originate from the input data. (Or did I misinterpret the quote?)

(Setup mentioned in discussion:

The main difference between distant supervision (as described in the link you provided) and self-supervision lies on the task the network is trained on.
Distant supervision focuses on generating weak labels for the very same task that would be tackled with supervised labels, and the final result could be directly used for that matter.
Self-supervision is a means for learning a data representation. It does so by learning a surrogate task, which is defined by inputs and labels derived exclusively from the original input data.
I can imagine cases in which an implementation of self-supervision could be considered distant supervision (if the task casually matches the target task). On the other hand, if external data sources would be employed for training on a surrogate task, that would be a case of representation learning (that could incorporate self-supervision too).


Why is cross-over a part of genetic algorithms? Genetic Algorithms has come to my attention recently when trying to correct/improve computer opponents for turn-based strategy computer games.
I implemented a simple Genetic Algorithm that didn't use any cross-over, just some random mutation. It seemed to work in this case, and so I started thinking:
Why is cross-over a part of genetic algorithms? Wouldn't mutation be enough?
This is from a data dump on an old AI site. The asker had the UID of 7.

Mutation is usually defined to be a global operator, i.e. iterated mutation is (eventually) capable of reaching every point in the vector space defined by the geneome. In that sense, mutation alone is certainly 'enough'.

Regarding the motivation for crossover - from Essentials of Metaheuristics, p42:

  Crossover was originally based on the premise that highly fit individuals often share certain traits, called building blocks, in common.
  For example, in the boolean individual 10110101, perhaps
  ***101*1 might be a building block

(where * means "either 0 or 1")

So the idea is that crossover works by spreading building blocks quickly throughout the population.

  Crossover methods also assume that there is some degree of linkage between genes on the chromosome: that is, settings for certain genes in groups are strongly correlated to fitness improvement. For example, genes A and B might contribute to fitness only when they’re both set to 1: if either is set to 0, then the fact that the other is set to 1 doesn’t do anything.

Also note that crossover is not a global operator. If the only operator is crossover then (also from p42):

  Eventually the population will converge, and often (unfortunately) prematurely
  converge, to copies of the same individual. At this stage there’s no escape: when an individual crosses over with itself, nothing new is generated.

For this reason, crossover is generally used together with some global mutation operator.


What is the input for the prior model of VQ-VAE? I'm trying to implement the VQ-VAE model. In there, a continuous variable $x$ is encoded in an array $z$ of discrete latent variables $z_i$ that are mapped each to an embedding vector $e_i$. These vectors can be used to generate an $\hat{x}$ that approximates $x$.

In order to obtain a reasonable generative model $p_\theta(x)=\int p_\theta(x|z)p(z)$, one needs to learn the prior distribution of the code $z$. However, it is not clear in this paper, or its second version, what should be the input of the network that learns the prior. Is it $z=[z_i]$ or $e=[e_i]$? The paper seems to indicate that it is $z$, but if that's the case, I don't understand how I should encode $z$ properly. For example, a sample of $z$ might be an $n\times n$ matrix with discrete values between $0$ and $511$. It is not reasonable to me to use a one-hot encoding, nor to simply use the discrete numbers as if they were continuous, given that there is no defined order for them. On the other hand, using $e$ doesn't have this problem since it represents a matrix with continuous entries, but then the required network would be much bigger.

So, what should be the input for the prior model? $z$ or $e$? If it is $z$, how should I represent it? If it is $e$, how should I implement the network?

Some notes about VQ-VAE:

In the paper, they used PixelCNN to learn the prior.
PixelCNN is trained on images.
The discrete latent variables are just the indices of the
embedding vectors. For example, you can put your embedding vectors
in an array.

For a single input image, the number of the output channels of the encoder before quantization equals the dimensionality of the embedding vectors. For an analogy, the output of the encoder is like an image but with a number of channels that equals to the dimensions in the embedding space. With that, each pixel is a vector in the space of the embedding vectors1. The quantization is done on each pixel by mapping each pixel to the nearest embedding vector $e$.
Now, each pixel can be represented by a single integer number which equals to the index of its nearest embedding (what you call the discrete latent variables). Thus, you have two representations for the quantized output, one is a large tensor with many channels (embedding vectors), and another is a simple discrete image with one channel (discrete latent variables).
The one channel discrete images are used to train PixelCNN. This is great because they are small size images. while the large tensor with the embedding vectors is used for the decoder as it holds the information needed for reconstruction.
So, the discrete latent variables for the prior model and the embedding vectors for the encoder.
1This is just an analogy, pixels values belong to a closed interval.