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

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

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

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

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

I presume this question was prompted by the paper Geometric deep learning:
going beyond Euclidean data (2017). If we look at its abstract:

Many scientific fields study data with an underlying structure that is a non-Euclidean space. Some examples include social networks in computational social sciences, sensor networks in communications, functional networks in brain imaging, regulatory networks in genetics, and meshed surfaces in computer graphics. In many applications, such geometric
  data are large and complex (in the case of social networks, on the scale of billions), and are natural targets for machine learning techniques. In particular, we would like to use deep neural networks, which have recently proven to be powerful tools for a broad range of problems from computer vision, natural language processing, and audio analysis. However,
  these tools have been most successful on data with an underlying Euclidean or grid-like structure, and in cases where the invariances of these structures are built into networks used to model them.

We see that the authors use the term "non-Euclidean data" to refer to data whose underlying structure is non-Euclidean.
Since Euclidean spaces are prototypically defined by $\mathbb{R}^n$ (for some dimension $n$), 'Euclidean data' is data which is sensibly modelled as being plotted in $n$-dimensional linear space, for example image files (where the $x$ and $y$ coordinates refer to the location of each pixel, and the $z$ coordinate refers to its colour/intensity).
However some data does not map neatly into $\mathbb{R}^n$, for example, a social network modelled by a graph. You can of course embed the physical shape of a graph in 3-d space, but you will lose information such as the quality of edges, or the values associated with nodes, or the directionality of edges, and there isn't an obvious sensible way of mapping these attributes to higher dimensional Euclidean space. And depending on the specific embedding, you may introduce spurious correlations (e.g. two unconnected nodes appearing closer to each other in the embedding than to nodes they are connected to).
Methods such as Graph Neural Networks seek to adapt existing Machine Learning technologies to directly process non-Euclidean structured data as input, so that this (possibly useful) information is not lost in transforming the data into a Euclidean input as required by existing techniques.

This answer clarifies my original main doubt, given that you emphasize that, in fact, graphs could be represented as a set of vectors (i.e. nodes and edges could be represented as vectors), but you correctly say that there isn't necessarily a natural way of mapping these graphs to a Euclidean space while maintaining their original properties or not introducing properties that did not exist. Maybe the only thing that is missing from this post is the answer to the question: "How would a dataset of non-Euclidean data look like?".

For instance, it could be a list of triplets in the form of entity_1, relation, entity_2. And all these triplets form a graph.

@brazofuerte Would text be classified as non-euclidean data? I mean we don't use the term geometric deep learning when we are doing nlp.

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

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

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

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

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

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

To conclude, non-Euclidian data is everywhere.

I think that your example of the points and this sentence "Clearly, 2 of the images are more similar to each other than the third one is but if we looked at the pixels alone, the euclidean distance between the pixel values don't represent this similarity." is really a stretch. Actually, I think you're mixing the concepts of "relation between inputs and classes" and "non-Euclidean data". Why would the fact that there isn't a linear relation between inputs and outputs imply that the data is non-Euclidean?!

I think that non-Euclidean data is data that doesn't have the Euclidean properties. For example, in an image, there's the notion of the left pixel of a certain pixel  (i.e. there's an order). In a graph, there isn't such a notion between vertices, so a graph can't be "Euclidean data". I think that data where you can naturally perform dot products and norms is likely Euclidean (at least in the sense that I initially intended or in geometric deep learning).

In GDL, the input to the models are usually vector features of the vertices. However, these are "just" feature vectors associated with the vertices (so one could think that graphs are also Euclidean because you can calculate the dot product between two vectors), but they do not describe the structure of the graph, which can be described e.g. using an adjacency matrix.

You're intuition about non-euclidean data not having euclidean properties is correct but only in the specific notion that "similar things are close together" which is what I tried to highlight. The fact that a dot product (or https://en.wikipedia.org/wiki/Inner_product_space#Examples) can be computed doesn't imply a euclidean space. However this doesn't prevent one from assuming that the space is euclidean and using an approximation of euclidean distance which can sometimes be fruitful.

Again, I think you are mixing inputs with outputs (or classes). I don't think your answer is completely correct (as I stated above). Apparently, the definition of Euclidean space isn't actually well accepted (as e.g. the notion of a vector space). I don't get why this 'but only in the specific notion that "similar things are close together"'.

in polar coordinates, the 1st red/blue statistics is linearly separable; though this would also depend on how you interpret the source of the data...

"the shortest path between 2 points isn't necessarily a straight line." this sentence is slightly problematic because "path" and "straight line" are not well-defined if you are not already in some well-defined space (such as euclidian geometry)

@k.c.sayz'k.csayz' I agree. Thats why I prefaced it with "can be generally boiled down to" as in "This is not well defined but this is the gist in order to get an intuition". Either way, I am open to edits.

no worries, i was being a bit pedantic here: i am under the humble assumption that the phrase just refers to a loose set of research goals rather than a specific idea. specifically, i think i've also seen it mentioned as training to constraint parameters to fit some manifold, but the specifics are unclear to me and maybe i'm miss understanding something...

Who voting such an answer up?

It's hard to say because Euclidean space is defined with respect to some kind of metric, so without any clearer exposition on the nature of the data/problem, the phrase itself may or may not be clear.
A metric $d: A \times A \rightarrow \mathbb{R}$ is a function that defines distance between any two points in the space with respect to axioms that 1. two points have zero distance iff they are the same: $d(a,b) = 0 \Leftrightarrow a = b$.  2. symmetric: $d(a,b) = d(b,a)$. 3. triangle inequality: $d(a,b) + d(b,c) ≥ d(a,c)$.
A Euclidian metric is a metric that also obeys Pythagoras theorem , or at least: the distance between some point $(x,y) \in \mathbb{R}^2$ is equal to $\sqrt{x^2 + y^2}.$ You will find that all Euclidian spaces are isomorphic to $\mathbb{R}^n$, meaning that the two notions are in some sense identical.
Any graph/data whose underlying data does not "naturally come" from $\mathbb{R}^n$, or a graph that does not admit a natural embedding in $\mathbb{R}^n$ might not be Euclidian, since $\mathbb{R}^n$ is isomorphic to any euclidian space.

Where does this type of data arise?

In terms of learning on non-Euclidean data, it was probably first coined by prof. Bronstein here. Recently, prof. Bronstein published, along with other top authors in the field, a book about geometric deep learning, which in essence presents a unified mathematical framework for symmetries-based learning, and exemplifies the extension of concepts from classical ML/DL to the domain of higher-dimensional geometric domains (chapter 4).

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

According to the unified mathematical framework presented in prof. Bronstein's book, the blueprint of geometric DL consists of an underlying domain $\Omega$ and signals $\mathcal{X}(\Omega)$ and functions $\mathcal{F}(\mathcal{X}(\Omega))$.
The domain is the geometric/algebraic structure behind any instance of that data type (basically shows how its composing features are arranged). Associated with this domain is a symmetry group (all the transformations under which the domain is invariant).
The signal is the observable state/value/quantity/features in the points of the domain.
The function(s) are the blocks/layers that we want to build as functions of the signals on the domain. Here is where we can inject inductive biases.
Translation equivariance is a property of the domain of images (among other groups). Convolutions as functions of a signal on the domain $R^2$ are translation equivariant, meaning that if you move an object in an image, you would still find the same features (at different locations) when applying the same kernel over the two images. This is the (geometric prior) "inductive bias", as the function used is aware of the domain, knows its properties, and uses them.
The underlying domain of an image is $\mathbb{R}^2$ (the position of the pixels in the (x, y) plane). In this context, one can say that the signal of an is simply the colour/intensity of the pixels. As pointed out in this answer, this group admits the Euclidean distance between two points in the plane as $d(x, y) = \sqrt{\sum_{i=0}^{1} (x_i - y_i)^2}$.
In broad terms, non-Euclidean data is data whose underlying domain does not obey Euclidean distance as a metric between points in the domain. For visualization simplicity, think of $\mathbb{Z}^2$ instead, which can be seen as a "grid" of integer-valued points separated by a distance of 1. You can easily "visualize" the distance between the points of the domain.
Now let's move to graphs. What is the underlying domain of the graph? It's a set of nodes $\mathcal{V}$ and a set of edges $\mathcal{E}$. There is no such thing as distance in the Euclidean sense between the nodes of a graph. If you ask "What is the distance between point A and B?", the answer is probably a function of the connectivity of the graph (which is part of the domain), and is not the same for arbitrary points in the graph.

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

Usually, a data point (sample) consists of a domain and a signal.

The domain can be for example a weighted adjacency matrix of the graph, which lists the "distances" between nodes, for those that exist.
Features can be either per node, per edge or both.

In a concrete example, the domain can be a road network graph with distances and connectivity between road intersections, and the signal can be per-node features indicating how many cars are in the intersection at a given point.
Of course, the domain can also be different between data points (i.e. in the PROTEINS dataset, where each protein is a graph connected (edges) aminoacids (nodes), with different structures).
A non-Euclidean dataset simply consists of multiple such data points, which may or may not have the same underlying domain (i.e. same graph structure defined by an adjacency matrix).

Thanks for this answer and welcome to our community! There are a few unclear things in this answer. First, you don't explain exactly what a signal is. It seems that you define a (non-Euclidean) "data point" as something that has a "domain" and a "signal", so it seems that you define it similar to a function, which has also a "domain". But what is a signal? Of course, the term signal pops up in signal processing, but maybe you should explain what it really is in signal processing and why you call the features of a "non-Euclidean data point" a signal.

Second, you also call "Euclidean data" a "data point", why? Third, you talk about data points and you give an example at the end, but what is a dataset of non-Euclidean data? Note that I assume that a dataset is not the same thing as a data point, which is just one element of a dataset. So, what is the difference between a "data point" and a "dataset" in the context of Euclidean data and geometric deep learning?

Thanks for pointing out the mistakes, I made some corrections. I have tried to explain it in broad terms as I am not very good at formal mathematics formulations. For the last item, I simply forgot to define the dataset after defining a data point, haha. Hope it's better now :)

Ok, thanks, now, it's a bit clearer. But are you saying that you would train, e.g., a graph neural network with multiple graphs (so one graph would be one data point)? I am not sure that's the case. Moreover, you say that the "domain is usually incorporated into architectures via inductive biases.". What do you mean by that exactly?

Yes, you can train a GNN with multiple different graphs. Look at the PROTEINS dataset, where each data point (sample) is a different protein that is represented as a graph. The nodes are amino-acids and the edges are connections between them (based on some rules). The underlying domain (the individual nodes and edges -- their existence, not their values) is different for each protein. One can have 3 amino-acids with 4 edges, one can have 4 amino-acids with 5 edges. The values of the amino-acids (node features / signals) are also different from sample to sample.

For the part with the inductive biases, there is the CNN example in my initial comment. CNNs are built such that convolutions (which are translation equivariant) take advantage of the nature of the image, which is also translation equivariant/invariant because its underlying domain is R2.

Your example of the dataset with multiple graphs that represent different molecules. is good! Yes, I am familiar with CNNs. But what would be the inductive bias in the case of graphs and GNNs?

Permutation invariance is a property of a graph - there is no order relationship between the nodes (as there is in $\mathbb{R}^2$ where you can say the coordinate (1, 0) is to the right of (0, 0)). So you can permute the nodes however you want (without changing the edges), and you would have the same graph. The question is how do you exploit this property, or how do you make use of this in the context of a neural network. Most of the "Message Passing" architectures in GNNs (GAT, GCN, etc.) are formulated so that their update rule is permutation invariant. Please refer to the respective papers.

Yes, I am aware of these architectures that take as input adjacency matrices and perform some kind of message passing, which some people call graph convolution. But I wouldn't say that "domain is usually incorporated into architectures via inductive biases". Isn't the input to these graph neural networks e.g. adjacency matrices that represent the structure/domain of the graphs? Then you would work on this input by performing some kind of message passing or conv, right? Isn't this the intuition? So, I wouldn't say that the structure of the graph (or domain) is incorporated in the architecture.

However, there's definitely an inductive bias in graph neural networks, because they "assume" (in the way they are designed and by performing these message passing algorithms) that the data they get is non-Euclidean. So, rather than writing what you wrote, I would write that GNNs have an inductive bias that assumes that the inputs are graphs. It's possible I am missing something because it's been a while I had to deal with GNNs and I forgot the details.

You are correct that "domain is usually incorporated into architecture via inductive biases" is a very vague and possibly incorrect explanation. I made some more edits to the original post. Your last comment is on point, and somehow reflects what I was trying to say. They know the input is a graph, so the "blocks"/"layers" are designed so that they exploit the symmetries of the group (I suppose permutation invariance, at least). Hope my answer is more clear now.

As far as I understand, the concept of non-Euclidean space doesn't bring the ordinality or hierarchy among the features, compared to that with the data formed in the Euclidean space.
The difference between both these techniques is not remarkable for discriminative tasks like classification. But, for generative modeling, the non-Euclidean techniques helps in defining the latent manifold space for the given data distribution. This can further help in traversing the manifold from the same distribution (to generate similar samples from the same or underlying manifold) even with $n$ degrees of freedom in the latent space. This is not possible with Euclidean techniques. One cannot fully traverse/generate samples from or outside the manifold without the minimal change in the Euclidean space. More precisely, it can, but it will only present it as noisy data.

Maybe you should define the concept of a manifold and why it is important to understand the concept of Euclidean and non-Euclidean data.


text:
Is there an open-source implementation for graph convolution networks for weighted graphs?
Currently, I'm using a Python library, StellarGraph, to implement GCN. And I now have a situation where I have graphs with weighted edges. Unfortunately, StellarGraph doesn't support those graphs
I'm looking for an open-source implementation for graph convolution networks for weighted graphs. I've searched a lot, but mostly they assumed unweighted graphs. Is there an open-source implementation for GCNs for weighted graphs?

You can take a look at "Diffusion Convolutional Recurrent Neural Network: Data-Driven Traffic Forecasting" (you can find it on Github). In there you can find an implementation of the diffusion convolution which is applied to a weighted graph, the traffic adjacency matrix.

A Comprehensive Survey on Graph Neural Networks (2019) presents a list of ConvGNN's. All of the following accept weighted graphs, and three accept those with edge weights as well:

And below is a series of open source implementations of many of the above:

You can use Pytorch_Geometric library for your projects. Its supports weighted GCNs. It is a rapidly evolving open-source library with easy to use syntax. It is mentioned in the landing page of Pytorch. It is the most starred Pytorch github repo for geometric deep learning. Creating a GCN model which can process graphs with weights is as simple as:
import torch
import torch.nn.functional as F
from torch_geometric.nn import GCNConv

class Net(torch.nn.Module):
    def __init__(self):
        super(Net, self).__init__()
        self.conv1 = GCNConv(dataset.num_node_features, 16)
        self.conv2 = GCNConv(16, dataset.num_classes)

    def forward(self, data):

        # data has the following 3 attributes
        x, edge_index, edge_weight = data.x, data.edge_index, data.edge_weight

        x = self.conv1(x, edge_index, edge_weight)
        x = F.relu(x)
        x = F.dropout(x, training=self.training)
        x = self.conv2(x, edge_index, edge_weight)

        return F.log_softmax(x, dim=1)

See this for getting started.
Check out its documentation on different variants of GCNs for further details. One of the best thing is that like Pytorch, its documentation are self-sufficient.

Is there any reason why Pytorch Geometric wouldn't deal with negative weights in GCNConv()? When I use positive weights it works just fine. When I use negative ones it sometimes returns nans and causes problems. Any ideas why?

You can use Graph Attention Networks for weighted graphs. This model can handle negative weights. Check out its documentation.

While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference.  Link-only answers can become invalid if the linked page changes. - From Review

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
What is the difference between latent and embedding spaces?
In general, the word "latent" means "hidden" and "to embed" means "to incorporate". In machine learning, the expressions "hidden (or latent) space" and "embedding space" occur in several contexts. More specifically, an embedding can refer to a vector representation of a word. An embedding space can refer to a subspace of a bigger space, so we say that the subspace is embedded in the bigger space. The word "latent" comes up in contexts like hidden Markov models (HMMs) or auto-encoders.
What is the difference between these spaces? In some contexts, do these two expressions refer to the same concept?

Embedding vs Latent Space
Due to Machine Learning's recent and rapid renaissance, and the fact that it draws from many distinct areas of mathematics, statistics, and computer science, it often has a number of different terms for the same or similar concepts.
"Latent space" and "embedding" both refer to an (often lower-dimensional) representation of high-dimensional data:

Latent space refers specifically to the space from which the low-dimensional representation is drawn.
Embedding refers to the way the low-dimensional data is mapped to ("embedded in") the original higher dimensional space.

For example, in this "Swiss roll" data, the 3d data on the left is sensibly modelled as a 2d manifold 'embedded' in 3d space. The function mapping the 'latent' 2d data to its 3d representation is the embedding, and the underlying 2d space itself is the latent space (or embedded space):

Synonyms
Depending on the specific impression you wish to give, "embedding" often goes by different terms:

Term
Context

dimensionality reduction
combating the "curse of dimensionality"

feature extraction feature projection feature embedding feature learning representation learning
extracting 'meaningful' features from raw data

embedding manifold learning latent feature representation
understanding the underlying topology of the data

However this is not a hard-and-fast rule, and they are often completely interchangeable.

The expression "latent space" explicitly indicates that the space is associated with the mathematical concept of an hidden (or latent) variable, which cannot be observed directly, but only indirectly.
The expression "embedding space" refers to a vector space that represents an original space of inputs (e.g. images or words). For example, in the case of "word embeddings", which are vector representations of words. It can also refer to a latent space because a latent space can also be a space of vectors. However, an embedding space is not necessarily an hidden space. It is just another (vector) representation of another space.
These two expressions can be used interchangeably, also because the expression "embedding space" is often not formally defined.

To give a statistician's answer, the distinction is empirical (embedding) versus theoretical (latent positions). You define a statistical model which has latent positions that you could then try to estimate, given data. Or, given data, you might simply find a vector representation of each object of interest in a way that makes sense for the applications considered - and you would call that set of representations an embedding. There's a lot of work going on trying to re-interpret popular embeddings as estimating a compatible model's latent positions, but that's not always straightforward.

The words latent space and embedding space are often used interchangeably. However, latent space can more specifically refer to the sample space of a stochastic representation, whereas embedding space more often refers to the space of a deterministic representation.
This comes from latent referring to an unobserved random variable, for which we can infer a belief distribution over its plausible values, for example using an encoder network. You can then draw samples of the predicted distribution for further processing. To learn more, you can look into VAEs.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Monte Carlo epsilon-greedy Policy Iteration: monotonic improvement for all cases or for the expected value?
I was going through university slides and this particular slide is trying to prove that in a Monte Carlo Policy Iteration algorithm using an epsilon-greedy policy, the state Values (V-Values) are monotonically improving.

My question is about the first line of computation.

Isn't this actually the formula for the expected value of Q? It is calculating a probability of occurrence following the policy times actual Q values, then doing the summation.
If that is the case, could you help me understand the relationship between the expected value of Q and the expected value of V ?
Also, if above is true, in a real world scenario, depending on how many episodes we sample and on stochasticity, does it mean that the V values of the new policy could be worse than the V values of the old policy ?

I think this equation answer your question:
$$ q_{\pi^{i}}(s,\pi^{i+1}(s)) = \mathbf{E}[q_{\pi^{i}}(s,\pi^{i+1}(s))] = \sum_{a \in A}\pi^{i+1}(a|s)q_{\pi^{i}}(s,a)$$
value of the Q while taking action from policy $\pi^{i+1}$ and thereafter following the policy $\pi^{i}$ is equal to the expected q value while taking action from policy $\pi^{i+1}$ and thereafter following the policy $\pi^{i}$. And for the second part of your question the answer is:
$$ V_{\pi^{i}}(s) = q_{\pi^{i}}(s,\pi^{i}(s))$$
state Value function following the policy $\pi^{i}$ is the same as action-value function while taking action from policy $\pi^{i}$ and thereafter following the policy $\pi^{i}$.


text:
How is the log-derivative trick of a trajectory derived?
I am looking at this formula which breaks down the gradient of $P(\tau |\theta)$ the first part is clear as is the derivative of $\log(x)$, but I do not see how the first formula is rearranged into the second.

The screenshot comes from the OpenAI page. It's not a rearrangement or derivation. It is just a statement. $\nabla f(x) = f(x) \nabla log f(x)$. Instead of $f(x)$ you have a parametrized probability which you want to maximize. The next point (3) on that page uses this statement and applies it on the trajectory

The identity $$\nabla_{\theta} P(\tau \mid \theta) = P(\tau \mid \theta) \nabla_{\theta} \log P(\tau \mid \theta)\tag{1}\label{1},$$
which can also be written as
\begin{align}
\nabla_{\theta} \log P(\tau \mid \theta)
&=
\frac{\nabla_{\theta} P(\tau \mid \theta)}{P(\tau \mid \theta)}\\
&=\frac{1}{P(\tau \mid \theta)} \nabla_{\theta} P(\tau \mid \theta)
\end{align}
directly comes from the general rule to derive the logarithm of a function and the chain rule
\begin{align}
\frac{d \log f(x)}{d x}
&= \frac{1}{f(x)} \frac{d f}{dx}.
\end{align}
Note that $\log f(x)$ is a composite function and that's why we apply the chain rule and that the derivative of $\log x = \frac{1}{x}$, as your text says.
People shouldn't call this a trick. There's no trick here. It's just basic calculus.
Why do you need identity \ref{1}? Because that identity tells you that the derivative of the probability of the trajectory given the parameter $\theta$ with respect to $\theta$ is $P(\tau \mid \theta)$ times the gradient of the logarithm of that same probability. How is this useful? Because the logarithm will turn your product into a sum (and the derivative of a sum is the sum of the derivatives of the elements of the sum), Essentially, the identity \ref{1} will help you to compute the gradient is an easier way (at least, conceptually).

Thank you for your answer, it is clear how the derivative of log fits into the equation but not how the first form is rearranged to fit the second form. Are you able to elaborate on this?

@JacobB The first form is not rearranged to fit the second form in your example. The gradient of $P$ is given by your 2nd equation. Your 1st equation only tells you the definition of the probability of the trajectory. Then you can use your 2nd identity to find the gradient of the 1st. Why do you need the 2nd identity? Because there's a log there and your product in the 1st equation will become a sum.

I see thanks, I misunderstood the transition between 1&2 it seemed they were building off the last equation.

In your follow up you state we use the log of probabilities to make our computation easier, but we still have to compute the original probability don't we? So we can't completely avoid a long chain of multiplications.

@JacobB Multiplications (especially of small numbers) can easily be numerically unstable. For example, if you multiply $0.5$ and $0.5$, you get $0.25$. If you keep multiplying small numbers, you can easily go to zero with finite-precision numbers. In your example, if $T$ is a big number, that can easily happen. However, summations do not suffer from this (i.e. $0.5+0.5 > 0.5$). That's another reason to use that trick. But, essentially, you use that trick because computing the gradient of a summation is easier than computing the gradient of a product.

Right, but in the formula we don't avoid this unstable multiplication only part of the formula is contained in a log

The reason for using the log here is indeed to turn a product into a sum. But I don't believe it's for numerical reasons. Instead the reason is that the trajectory likelihood is a product of terms $p_\theta(a_t|s_t)p(s_{t+1}|a_t, s_t)$, with a policy $p_\theta(a_t|s_t)$ with parameters $\theta$. Once taking the log, we get a sum and the derivatives of the dynamics terms $p(s_{t+1}|a_t, s_t)$ with respect to the policy parameters $\theta$ drop out.


text:
What are the differences between 1-step SARSA and SARSA?
SARSA is on-policy, while n-step SARSA is off-policy. But when n = 1, is it like an off-policy version of SARSA? Any similarity and difference between 1-step SARSA and SARSA?

N-step SARSA can be both off policy and on-policy. I think you already know the n step on-policy SARSA. So I am just telling you how n-step SARSA can be off-policy.
Off-policy n-step SARSA: Now you have two policies, one is target policy, $\pi$, (let's say it is a greedy policy), another one is behavior policy, $b$, (you are actually following this behavior policy). Since this is off-policy, you do importance sampling for that. So the update rule is like this:
$$Q_{t+n}(S_{t},A_{t}) = Q_{t+n-1}(S_{t},A_{t}) + \alpha \rho_{t+1:t+n-1}[G_{t:t+n} - Q_{t+n-1}(S_{t},A_{t})],$$
where
$$\rho_{t:h} = \prod_{t=k}^{h} \frac{\pi(A_{k}|S_{k})}{b(A_{k}|S_{k})}$$
You are following the behavior policy $b$, but shifting the Q values towards the target policy, $\pi$.
Off-policy one-step SARSA: You can think of Q learning as one-step off policy SARSA.

Thanks for your reply. Does that mean on-policy 1-step SARSA is the same as SARSA?

Yes, one-step on-policy SARSA is called SARSA

Then what is the difference between Q-learning and 1-step off policy SARSA? I understand the algorithms are different. 1-step off policy SARSA uses importance sampling, and Q learning seems just following behavior policy. What would be different results applying these two algorithms? Are they equivalent theoretically?

Q learning and 1step off policy SARA are not exactly the same algorithm. But both are off policy and both follow the behavior policy. But in Q learning you need not consider the importance sampling ratio but in 1 step off policy SARSA you have to know both the behavior policy and target policy (since you have to find the sampling ratio).


text:
Is radial basis function network appropriate for small datasets?
I'm a computer engineering student and I'm about to work on my master thesis. My professor gave me a small dataset with brain Computed Axial Tomography records. I would like to use deep learning to help doctors diagnose a certain disease (obviously, I've also got the data for doing supervised learning).
Since the dataset is small, is radial basis function network a good solution? What do you think?
Btw, if you have any type of tips in using the RBF network for this kind of project I would be really grateful.

Not familiar with RBF but when you have a small data set image augmentation can help. You can do this easily with the Keras ImageDataGenerator, documentation is here. Alternatively you can create image augmentation yourself using image processing models like PIL or CV2.


text:
What types of AI agents are Djikstra's algorithm and Prim's Minimum Spanning Tree algorithm?
From the perspective of the type of AI Agents, I would like to discuss Prim's Minimum Spanning Tree algorithm and Dijkstra's Algorithm.
Both are model-based agents and both are "greedy algorithms".
Both have their memory to store the history of vertices and their path distance. Prim's is more greedy than Dijkstra's algorithm whereas Dijkstra's algorithm is more efficient than Prim's.
Can we say that Dijkstra's algorithm is a utility-based agent, whereas Prim's is a goal-based agent, with the justification that Prim's is more goal-oriented as compared to finding the optimum (shortest) path?

Why do you want to think of these algorithms as agents?
An agent is an abstract and higher-level concept than the concept of an algorithm, which is just a set of instructions.
You could have two agents, one that is supposed to find the minimum spanning tree and another that is supposed to find the shortest path between a source and goal nodes.  In both cases, these two agents have a goal, so they are both goal-oriented agents, but the algorithms they use to reach the goal are irrelevant, as long as they have one or more goals. If you have an agent that performs optimally with respect to some metric, you may want to call that agent an optimal agent.
A similar logic applies to utility-based agents.
So, in short, algorithms are used by agents to act, but the algorithms themselves are not the agents (unless you want to have a philosophical debate or use different definitions of agents). See this answer for more details about the definition of agents.


text:
How to estimate a behavior policy for off-policy learning based on data?
I have a dataset which includes states, actions, and reward. The dataset includes information on the transition, i.e., $p(r,s' \mid s,a)$.
Is there a way to estimate a behavior policy from this dataset so that it can be used in an off-policy learning algorithm?

Is there a way to estimate a behavior policy from this dataset so that it can be used in an off-policy learning algorithm?

If you have enough examples of $(s,a)$ pairs for each instance of $s$ then you can simply estimate
$$b(a|s) = \frac{N(a,s)}{N(s)}$$
Where $N$ counts the number of instances in your dataset. This might be enough to use off-policy with importance sampling.
Alternatively, you can use an off-policy approach that doesn't need importance sampling. The most straightforward one here would be single-step Q learning. The update step for 1-step Q-learning does not depend on behaviour policy, because:

The action value being updated $Q(s,a)$ already assumes $a$ is being taken, so you don't need any conditional probability there.
The TD target $r + \gamma \text{max}_{a'}[Q(s',a')]$ does not need to be adjusted for behaviour policy, it works with the target policy directly (implied as $\pi(s) = \text{argmax}_{a}[Q(s,a)]$)

A 2-step Q learning algorithm would need to adjust for likelihood $b(a'|s')$ in the TD target $\frac{\pi(a'|s')}{b(a'|s')}(r + \gamma r' + \gamma^2\text{max}_{a''}[Q(s'',a'')])$ - typically $\pi(a'|s')$ is either 0 or 1, thus making $b(a'|s')$ irrelevant some of the time. But you would still prefer to know it for performing updates it you can.
If you are making updates offline and off-policy, then single-step Q learning is probably the simplest approach. It will require more update steps overall to reach convergence, but each one will be simpler.

You can simply train a policy from the inputs to predict the actions in your dataset. You can use the cross entropy loss for this, i.e. maximize the the log probability that the policy assigns to the actions in the data set when given the corresponding inputs. This is called behavioral cloning.
The result is an approximation of the behavioral policy that lets you compute probability densities of actions. It is an approximation because the dataset is finite, and even more so when you restrict the learned policy to a class of distributions, e.g. Gaussians.

If your data look like this $(s_{1},a_{1},r_{1},s_{2}),(s_{2},a_{2},r_{2},s_{3}),....,$ then this sample drawn from a particular behavior policy. So, you do not need to find the behavior policy just Q-Learning to find the optimal policy while following the behavior policy.
If the MDP is too big then consider applying Deep Q Learning. In both cases, the transition probability they have given has no use. But if you use on-policy learning and you know the dynamics of the system(means transition probabilities), I will recommend you to use dynamic programming(if state-space is not quite large). But for your above problem setting, you can not use dynamic programming, you have only one choice to use off-policy learning.

The behavior policy is given, so there is no need to find the behavior policy(since this data is drawn from a particular behavior policy).

The samples you have drawn is from the behavior policy. Someone gave him access to this data. So now he can just use Q-Learning to find the optimal policy. In case of Q-Learning, you do not need the $b(a|s)$.

The edit makes it better. Might be worth clarifying that you mean single-step Q-learning, although that is the most common variant.

Yes, this statement "So, you do not need to find the behavior policy" is wrong in some cases. But for Q-Learning you still do not need to know this behavior policy.

I'm going backwards and forwards on n-step Q learning :-). Actually I stand by my first statement - you need to know behaviour policy for n-step Q learning, because the wieghtings may vary when considering any non-zero update.

I do not mention the n-step Q-Learning(since I do not know the n-step Q-Learning algorithm). I refer to the Q-Learning algorithm(you may say it is one-step Q-Learning), there you do not need to know the behavior policy. But still, if you do not agree with me, feel free to command.


text:
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!


text:
What do we mean by saying "VC dimension gives a LOOSE, not TIGHT bound"?
From what I understand VC dimension is what establishes the feasibility of learning for infinite hypothesis sets, the only kind we would use in practice.
But, the literature (i.e. Learning from Data) states that VC gives a loose bound, and that in real applications, learning models with lower VC dimension tend to generalize better than those with higher VC dimension. So, a good rule of thumb would be to require at least 10xVC dimension examples in order to get decent generalization.
I am having trouble interpreting what loose bound means. Is the VC generalization bound loose due to its universality? Meaning, its results apply to all hypothesis sets, learning algorithms, input spaces, probability distributions, and binary target functions.

But, the literature (i.e. Learning from Data) states that VC gives a loose bound and that in real applications, learning models with lower VC dimension tend to generalize better than those with higher VC dimension.

It's true that people often use techniques such as regularisation to avoid over-parametrized models. However, I think it's dangerous to say that, in real applications, those models are really generalizing better, given that you're typically assessing their generalization ability by using a finite validation dataset (possibly selected in a biased way). Moreover, note that the validation dataset is often ignored in certain bounds and the only thing that is taken into account is the expected risk and the empirical risk (on the training data).
In any case, the $\mathcal{VC}$ bounds may be "loose" because

the $\mathcal{VC}$ dimension is often expressed with the big-$\mathcal{O}$ notation (e.g. see this answer)
the bounds often involve probabilities and uncertainties (e.g. see this other answer)
there aren't stricter bounds (i.e. no one found better bounds yet)

Is the VC generalization bound loose due to its universality? Meaning, its results apply to all hypothesis sets, learning algorithms, input spaces, probability distributions, and binary target functions.

I think the answer is yes. In fact, often, the specific tasks or learning algorithms are ignored in the analyses, but, in general, you may exploit your knowledge of the problem to improve e.g. the number of useful examples that the learning algorithm could use.

Great. A comment about "(i.e. no one found better bounds yet)": "There exist lower bounds on the rate of uniform convergence where the order of magnitude is close to the order of magnitude obtained for the upper bounds (Vapnik and Chervonenkis, 1974)"


text:
Why do value iteration and policy iteration obtain similar policies even though they have different value functions?
I am trying to implement value and policy iteration algorithms. My value function from policy iteration looks vastly different from the values from value iteration, but the policy obtained from both is very similar. How is this possible? And what could be the possible reasons for this?

Both value iteration (VI) and policy iteration (PI) algorithms are guaranteed to converge to the optimal policy, so it is expected that you get similar policies from both algorithms (if they have converged).
However, they do this differently. VI can be seen as truncated version of PI.
Let me first illustrate the pseudocode of both algorithms (taken from Barto and Sutton's book), which I suggest you get familiar with (but you are probably already familiar with them if you implemented both algorithms).

As you can see, policy iteration updates the policy multiple times, because it alternates a step of policy evaluation and a step of policy improvement, where a better policy is derived from the current best estimate of the value function.

On the other hand, value iteration updates the policy only once (at the end).
In both cases, the policies are derived from the value functions in the same way. So, if you obtain similar policies, you may think that they are necessarily derived from similar final value functions. However, in general, this may not the case, and this is actually the motivation for the existence of value iteration, i.e. you may derive an optimal policy from an non-optimal value function.
Barto and Sutton's book provide an example. See figure 4.1 on page 77 (p. 99 of the pdf). For completeness, here's a screenshot of the figure.

That cleared it up a little! Thank you! Thanks for making the question more clear too! I also have an implementation related question, in the policy iteration, policy evaluation subroutine how is V(s) exactly updated? I get that in value iteration we are taking the value of the action that gives the maximum value, but what are we doing in the policy evaluation case?

@PyWalker27 There are actually two possible implementations of PE: one where you update V in place and the other where you maintain two arrays. Sutton and Barto's book explain this. Have a look at chapter 4.

The algorithm above, it appears is doing in an inplace update, right?

@PyWalker27 Yes, it appears to be in-place (but I suggest you read the section about the topic of chapter 4 to confirm that this is the case). If it wasn't in-place, we should be using a different V(s) on the left-hand side of $\leftarrow$.


text:
What are examples of machine learning techniques inspired by neuroscience?
What are examples of machine learning techniques (i.e. models, algorithms, etc.) inspired (to different extents) by neuroscience?
Particularly, I'm interested in recent developments, say less than 10 years old, that have their basis in neuroscience to some degree.

This question is related to Which artificial neural network can mimic biological neurons the most?, but it isn't an exact duplicate, because here the OP is asking about machine learning techniques (so, in this sense, this question is more general) and, in particular, developed in the last years (so, in this sense, more specific).

There is a category of neural networks that more closely attempt to mimic biological neural networks by incorporating also time (i.e. not all neurons fire at the same time). They are called spiking neural networks (SNNs) and their name comes from the fact that they use spiking neurons (i.e. neurons that fire discrete signals and affect other neurons at possibly different times).
SNNs are mainly used in neuroscience, and aren't commonly used in machine learning because they currently have some apparent limitations (e.g. non-differentiability, so gradient descent and back-propagation can't be applied, but GD and BP aren't really biologically realistic anyway, although some people already tried to apply GD to SNNs) and their performance isn't still as good as the performance of traditional deep learning models, which make them not so appealing to the deep learning community (which is currently mainly driven by performance and utility). Nevertheless, the performance gap between traditional neural networks and spiking neural networks is decreasing. See Deep Learning in Spiking Neural Networks (2019) by Amirhossein Tavanaei et al. for more details.
There are already commercial implementations of a hardware-accelerated SNNs (e.g. BrainChip provides this service). These hardware-accelerators are often called neuromorphic chips (or processors) and all computing based on SNNs or processors that attempt to implement biological neural networks is known as neuromorphic computing.
There's also the related area called reservoir computing, which studies neural networks (such as liquid-state machines or echo state machines) that make use of reservoirs (which are fixed during learning) to attempt e.g. to improve training efficiency. See An overview of reservoir computing: Theory, applications and implementations (2007) by Benjamin Schrauwen et al. for an overview.
Numenta (and, in particular, Jeff Hawkins, the founder of Numenta and author of an interesting book called On Intelligence) has also been studying neuroscience for a long time in order to develop models and theories of human intelligence. They call their new theory The Thousand Brains Theory of Intelligence, which is inspired by biological grid cells. This is also related and similar to capsule networks (often associated with Hinton).


text:
How are the Bellman optimality equations and minimax related?
Is the philosophy between Bellman equations and minimax the same?
Both the algorithms look at the full horizon and take into account potential gains (Bellman) and potential losses (minimax).
However, do the two differ besides the obvious on the fact that Bellman equations use discounted potential rewards, while minimax deals with potential losses without the discount? Are these enough to say they are similar in philosophy or is are they dissimilar? If so, then in what sense?

They have similar philosophies, in the sense that minimax and algorithms based on the Bellman optimality equations are used to solve optimization problems, but they are also different because they solve different problems.
Minimax (at least, the minimax version that I am aware of) is typically used to solve two-player games (e.g. chess, tic-tac-toe, etc.), while Bellman optimality equations (I assume you are referring to the Bellman equations that algorithms such as policy iteration are based on) do not assume the existence of two players (unless you consider the environment a player).

Allright so the assumption of "two-players" sets them apart?

@gfdsal I guess so (at least in most cases), but minimax may also be used in other context and I don't exclude the existence of "Bellman equations" for two-player games (I am just not aware of them right now).


text:
Why can't MLPs perform non-linear regression and classification?
In this page it's told:

In Single Perceptron / Multi-layer Perceptron(MLP), we only have linear separability because they are composed of input and output layers(some hidden layers in MLP)

What does it mean? I thought the MLP was a non-linear classifier. Could you explain it to me?

In Single Perceptron / Multi-layer Perceptron(MLP), we only have linear separability because they are composed of input and output layers(some hidden layers in MLP)

This is wrong.
A multi-layer perceptron (i.e. a feed-forward neural network) with non-linear activation functions can perform non-linear classification and regression. In fact, an MLP with one hidden layer with an arbitrary number of hidden nodes, each of them with a sigmoid (which is a non-linear function), can approximate any continuous function (up to an approximation error).
On the other hand, perceptrons can't do that. They perform only linear classification/regression.

I thought the MLP was a non-linear classifier.

You're right, unless the MLP only uses linear activation functions. In that case, it won't be able to perform non-linear classification/regression.
(P.S.: I suggest you always question the truth and correctness of what you read on the web, especially, on sites like Medium, as you actually did!)

Is it true to say that, in a MLP the neurons in the hidden layer can use only nonlinear activation functions while the neurons in the output layer can use or a linear or a non linear activation function ?

@AleWolf They can use linear or non-linear activation functions everywhere, in principle.

But, if they use linear activation function everywhere then that particular MLP would be linear, right ?

@AleWolf It would be linear in the sense that it would represent a straight-line.

authors: Николай Сурмай


text:
Have capsule neural networks been used to NLP problems?
The capsule neural network seems to be a good solution for problems that involve hierarchies. For example, a face is composed of eyes, a nose and ears; a hand is made of fingers, nails, and a palm; and a human is composed of a face and hands.
Many problems in NLP can be seen as hierarchical problems: there are words, sentences, paragraphs, and chapters, whose meaning changes based on the style of lower levels.
Are there any research papers (which I should be aware of) on the application of capsule neural networks to NLP problems?
Are there related research papers, which have been investigating hierarchical complexity within the domain of NLP, which could be easily translated to Capsule Network?

I think there might be something like NNP "Natural Narrative Processing", which would be the superset of NLP.

Geoffrey Hinton has started working on Thought Vectors at Google: https://en.wikipedia.org/wiki/Thought_vector
The basic idea is similar to his original idea with Capsule Networks, where activation happens by vectors instead of scalars, which allows the network to capture transformations: for example while traditional CNN needs to see object from all perspectives of three dimensional space, the Capsule networks are able to extrapolate transformations such as stretching much better.
Thought Vectors guide NLP similarly; one could say that there are two grammars, the linguistic grammar and the narrative grammar which is more universal (Vladimir Propp, Joseph Campbell, John Vervake). While dependency grammars do great job at understanding linguistic grammar, we lack tools for meaning extraction, which is narrative bound. Thus Thought Vectors could, at least in theory, give us a framework for matching the meaning of a word within a context rather than just lexically and grammarly trying to approximate the meaning through average co-occurances.
Neural Networks with Thought Vectors would be highly complex and beyond our computational resources today (Hinton predicts in one paper, that we would get there around 2035), however, one could conduct empirical research already by giving a heuristic structure for Thought Vectors by utilizing narrative systems that do compute more easily. One could for example have text segments annotated with writing theories or other such devices that would approximate the Thought Vectors conceptually. For example annotating the text with state transformations of conflict driven partially ordered causal link planner (cPOCL, Gervas et al.) or use a writing theory framework such as Dramatica to annotate known movie scripts (http://dramatica.com/theory http://dramatica.com/analysis).
Hinton himself is currently active in NLP research: https://research.google/people/GeoffreyHinton/
Here is a nice explanation of Thought Vectors: https://pathmind.com/wiki/thought-vectors

For us to answer this question. First, we need to look at why capsule networks outperform convolution neural networks by as much as 45% in recognizing images that have been rotated, translated or are under a different pose. We can find Geof Hinton's paper on capsule networks here for reference https://arxiv.org/pdf/1710.09829v1.pdf
In a CNN architecture, a convolution layer is usually followed by a max-pooling layer. This is so that the lower levels can detect low-level features, like edges, while the high-level layers can detect abstraction like eyes. However, the application of max-pooling leads to the loss of important information regarding the location and spatial relationship between certain features.
On the other hand, this is where capsule networks excel, the way they represent certain features is locally invariant. This is why capsule networks can recognize images under different lighting conditions and deformations. They are likely to excel at applications such as video and object tracking but not necessarily NLP.
The current approach in NLP maps words and phrases to vectors. From there, we exploit the concept of vectors and distances between them (cosine, euclidean, etc.) to perform operations such as: finding the similarity between words and even documents, machine translation, and natural language understanding (NLU).
Capsule networks are unlikely to succeed in NLP. This is because algorithms that aim to find the hierarchical structure of natural languages or approaches that focus on grammar have met little success. Research by Stanford University aiming at finding the hierarchical structure of natural languages can be found here https://nlp.stanford.edu/projects/project-induction.shtml
Although conclusive research regarding other applications of capsule networks has not yet been conducted. They are likely to excel at applications such as video intelligence and object tracking but not necessarily NLP.

It seems that it no longer is true that "Capsule Networks are unlikely to succeed in NLP" as Hinton himself is conducting research on this at Google; thus I think I should uncorrect this answer. I do understand that conceptually it is hard to distinct where NLP ends and something else starts, however, I would believe Thought Vectors for example could provide a similar addition to NLP as Dependency Grammars; they could detect the difference of thematic meaningness of words far better than n-gram based methods.

There has been some recent work on this: Investigating Capsule Networks with Dynamic Routing for Text Classification
Seems some are having some success with it.

Instead of just a link, it would be more useful if you could list the title of the paper and what it is about, so that people can assess the relevance before downloading it.

Well, it would be about Capsule networks and NLP.  That doesn't seem to be to great a conceptual leap for most people to make.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
How can a machine learning problem be reduced as a communication problem?
I once heard that the problem of approximating an unknown function can be modeled as a communication problem. How is this possible?

Information-theoretic view of Bayesian learning

I once heard that the problem of approximating an unknown function can be modeled as a communication problem. How is this possible?

Yes, this is indeed possible. More precisely, there is an information-theoretic view of Bayesian learning in neural networks, which can also be thought of as a communication problem, which explains both maximum a posteriori estimation (MAPE) and full Bayesian learning [1], i.e. finding the posteriors over the weights of the neural network: the neural networks that maintain a probability distribution over the weights are now known as Bayesian neural networks (and, in terms of theory, they are strongly related/similar to the famous variational auto-encoders).
The oldest relevant paper (I am aware of) that interprets Bayesian learning in neural networks as a communication problem is the 1993 paper by Hinton and Van Camp entitled Keeping the neural networks simple by minimizing the description length of the weights (COLT), which is the paper that introduces variational Bayesian neural networks (sometimes called ensemble learning in some papers from the 1990s), i.e. variational inference (VI) applied to neural networks (yes, the same VI used in VAEs). Hinton (yes, the famous Hinton that won the Turing award) and Van Camp (who is this? probably a Dutch guy from the name!) write in this paper

We can think in terms of a sender who can see both the input vector and the correct output and a receiver who can only see the input vector. The sender first fits a neural network, of pre-arranged architecture, to the complete set of training cases, then sends the weights to the receiver. For each training case, the sender also sends the discrepancy between the net's output and the correct output. By adding this discrepancy to the output of the net, the receiver can generate exactly the correct output.

You should read this seminal paper if you want to understand all the details.
Another relevant paper is Practical Variational Inference for Neural Networks (2013, NeurIPS) by Graves, who cites the 1993 paper immediately at the beginning of the paper. Essentially, as the title of the paper suggests, Graves tries to make VI in neural networks practical.
There are other relevant papers that still attempt to provide this information-theoretic view of Bayesian learning, such as Variational learning and bits-back coding: An information-theoretic view to bayesian learning (2004, IEEE Transactions on Neural networks), but most current papers on Bayesian neural networks, such as Weight Uncertainty in Neural Networks (2015, PMLR) don't do it (at most they may mention that this interpretation exists, but they don't go into the details).
Minimum description length
To give you a few more details, the information-theoretic view of Bayesian learning in these papers is that of the minimum description length (MDL), i.e. Bayesian learning (i.e. the application of Bayes rule to find the posteriors over the parameters of the model) is equivalent to finding a model that gives the "shortest description of the data" (hence the name MDL), where a description is some code/encoding of the data: in the case of the NNs, this encoding is contained in their weights.
Given that you want to find the simplest code, then this is a direct application of Occam's razor: if you have multiple hypotheses/functions that describe your data (or are consistent with your observations), then choose the simplest one. Occam's razor underlies many other mathematical/ML theories and frameworks, for example, AIXI, a framework for artificial general intelligence developed by Marcus Hutter. Jürgen Schmidhuber is also a good fan of Occam's razor and compression as a means to act intelligently (see e.g. the speed prior). If you are familiar with deep learning, a light bulb should turn on in your brain now. Yes, regularization techniques to avoid over-fitting and improve generalization can also be viewed as an application of Occam's razor principle.
Bits-back coding
How do we find the simplest weights? The bits-back coding, used by the 1993 paper and described in the 2004 and 2013 papers, essentially states that you can find the simplest encoding (i.e. posterior over the weights) by minimizing the Kullback-Leibler divergence (aka relative entropy: say what?!) between the posterior (which is unknown: so how can we compute the KL divergence?) and some prior (coding distribution), which is zero when the prior is equal to the posterior (but we don't know the posterior) [1]. Given that we don't know the posterior, we need to use a proxy objective function that doesn't involve the posterior, such as the Evidence Lower BOund (ELBO), also known as variational free-energy, which leads to a non-optimal coding (i.e. possibly, you will find some posteriors that are not optimal given the data).
Conclusions
Using MAPE or performing (approximate) Bayesian learning in a neural network (which finds one function or a probability distribution over functions, respectively) can be interpreted as finding the MDL, i.e. an optimal or near-optimal encoding of the data that needs to be communicated from a sender to a receiver.
Side notes
Information theory was pioneered by Claude Shannon in his 1948 seminal paper A Mathematical Theory of Communication.
Claude Shannon was also one of the participants at the Dartmouth workshop, which officially started the field of artificial intelligence, so he is one of the fathers of the AI field, and his impact on the field is definitely huge (although most people are not aware of it, but, hopefully, this answer will change that).
Further reading
Apart from the papers that I cited above, you may also be interested in Information Theory and its Relation to Machine Learning (2015) by Hu.


text:
What is the difference between a Bayesian Network and a Markov Chain?
I am trying to understand the difference between a Bayesian Network and a Markov Chain.
When I search for this one the web, the unanimous solution seems to be that a Bayesian Network is directional (i.e. it's a DAG) and a Markov Chain is not directional.
However, often a Markov Chain example is overtime, where the weather today is impacting the weather tomorrow, but the weather tomorrow is not (obviously) impacting the weather today. So I am quite confused how is a Markov Chain not directional?
I seem to be missing something here. Can someone please help me understand?

The main difference between a Bayesian network and a Markov chain is not that a Markov Chain is not directional, it is that the graph of the Bayesian network is not trivial whereas the graph of a Markov chain would be somewhat trivial, as all the previous $k$ nodes would just point to the current node. To illustrate further why this would be trivial, we let each node represent a random variable $X_i$. Then the nodes representing $X_i$ for $ t-k \leq i < t$ would be connected by a directed edge to $X_t$. That is, the edges $(X_i, X_t) \in E$ for $ t-k \leq i < t$ and where $E$ is the set of edges of the graph.
To illustrate this please see the examples below.
Assume that we have a $k$th order Markov chain, then by definition we have $\forall t > k$ $\mathbb{P}(X_t = x | X_0,...,X_{t-1}) = \mathbb{P}(X_t = x | X_{t-k},...,X_{t-1})$.
The main difference between the above definition and the definition of a Bayesian Network is that due to the direction of the graph we can have different dependencies for each $X_t$. Consider the Bayesian Network in the Figure below

We would get that $\mathbb{P}(X_4 = x| X_1, X_2, X_3) = \mathbb{P}(X_4 = x | X_2, X_3)$ and $\mathbb{P}(X_5 = x| X_1, X_2, X_3, X_4) = \mathbb{P}(X_5 = x | X_3)$.
So, the past events that the current random variable depends on don't have to have the same 'structure' in a Bayesian Network as in a Markov Chain.


text:
How does publishing in the deep learning world work, with respect to journals and arXiv?
Let's say I implemented a new deep learning model that pushed some SOTA a little bit further, and I wrote a new paper about for publication.
How does it work now? I pictured three options:

Submit it to a conference. Ok, that's the easy one, I submit it to something like NeurIPS or ICML and hope to get accepted. At that point, how do you make your paper accessible? Are there problems in uploading it to arXiv later, in order to get read by more people?
Upload it on arXiv directly. If I do that it would not be peer-reviewed, and technically speaking it would be devoid of "academic value". Right? It could easily be read by anyone, but there would be no formal "proof" of its "scientific quality". Correct me if I'm wrong.
Submit it to a peer-reviewed journal. Avoid desk rejection, avoid reviewers' rejection, after a long painful process it ends up on some international scientific journal. At that point, since the article is formally the editor's property, can you still upload it on arXiv, or on your blog, so that it can be accessible by many people?
How do the big stars of deep learning research do when they have some hot new paper ready for publication? And what publications are the most valued in the professional and the academic world?

Let me answer your questions one by one.
Submit it to a conference
Let's start with the optimistic case. Say your paper gets accepted! You can upload your preprint on arXiv with the "arXiv.org perpetual, non-exclusive license to distribute this article (Minimal rights required by arXiv.org)". It is a non-Creative Common License that does not provide any exclusive rights to arXiv as per. This is the default permission of arXiv (which does not interfere with the license of the conferences). You can easily find papers from ICML, NeurIPS, and AAAI on their websites as well as arXiv. For, e.g., NeurIPS 2017 began on 4th Dec 2017 and this paper has the latest submission on 6th Dec 2017.
If you say your work was rejected or you are about to submit it, you need to check for the restrictions on uploading the manuscript online before submitting it to the conference. Some conference allows papers to be submitted only if they are not uploaded to sites like arXiv within say 30 days prior to the paper submission deadline.
AAAI does not have restrictions on arXiv as per their policy. ACM also allows non-profit organizations like arXiv as per their policy.
Among all the info on the major publications I could find, I found a common phrase that the paper should not be uploaded to a for-profit digital library. ArXiv is certainly not among them. The reason why editors do not oppose arXiv papers could be that there are a lot of papers that are uploaded to arXiv in order to claim to be first, so banning them would be a big loss for the editors.
Say you comply with the restrictions of the conference and have uploaded your preprint then it brings the risk that reviewers can know who the authors are. They might be biased once they know who the authors are. This works in the favor of renowned/superstars scientists of the field. The reviewer might be a Ph.D. who admires this superstar and hence would try to get it accepted. Or the author might be a known colleague of the author and would hence be biased into accepting it. On the other hand, if the reviewer has some personal bias towards the author then that may be reflected in their scores.
Upload it on arXiv directly
Only uploading to arXiv is of not much academic value because it is not peer-reviewed as you pointed out. Anyone can write an absurd paper with false results and get it published on arXiv. That is why peer-reviewed papers are important.
One reason to upload to arXiv first is to make your work safe from other people coming up with similar approaches. It is not rare at all for people coming up with similar ideas within a duration of 3 months. Deep Learning is a fast-paced domain as it is a hot research field. So getting your paper out first in the name of work in progress saves you from potential rejects from the conference pointing to a similar work done available online before you.
Submit it to a peer-reviewed journal
Same thing as a conference. You can upload your preprint after acceptance of your manuscript with the default license of arXiv. For submitting it before on arXiv needs cross-checking with the rules of the journal. For, e.g., IEEE allows the work to be submitted to arXiv as per.
How do big stars publish?
Coming to your question of how big stars publish. They either publish directly in a conference and then upload to arXiv or they first upload on arXiv, get publicity and citations and then submit to a top conference. Having the preprint available online can also bias the reviewer into accepting their research (as mentioned before). This way they reduce their chance of rejection.
Fun fact
Interestingly, if the preprints become very famous then the reviewer might get confused that your work is a derivative of a popular work which in reality is the preprint of your submitted work! In such cases, you would need to imply this diplomatically. For example, Music Transformer by the Google Brain team (which consisted of authors of the famous Transformer paper "Attention is all you need") was available on arXiv in 2018 and was already being cited by others. When it was submitted to ICLR 2019, a reviewer mistakenly took it as a derivative work of the 2018 arXiv paper and suggested a rejection of the paper. However, after further inspection, he/she realized the confusion which blew their mind! Immediately the paper was given a suitable high score. Source: https://openreview.net/forum?id=rJe4ShAcF7
Where to publish?
Unlike in core electronics and other branches where a journal is much more important than conference papers, in machine learning, conference papers are at par or better than any journal out there. Mostly the quality depends on the Impact Factor of the journal or conference. For example, NeurIPS is a top venue to publish and it's a conference and not a journal.
One reason for conferences to be so important is that they are more popular among researchers. Conferences are fast with their review as compared to the lengthy journal review. This allows researchers to meet and discuss the progress of the field with like-minded people much faster. This is crucial for a rapidly evolving field like artificial intelligence. This makes conference popular which attracts the best researchers to publish their cutting edge which in turn makes the conference more lucrative for other researchers to publish in the same venue as the big stars.
Conferences also allow people from the industry to meet the researchers and hire them. The quick meeting opportunity provided by the conference is beneficial for both the academic researchers as well as the industry for attracting talent.

To improve the reliability of this answer, can you provide some references for 1. "You can upload your preprint on arXiv with the default permission of arXiv (which does not interfere with the license of the conferences" and 2. "You can upload your preprint after acceptance of your manuscript with the default license of arXiv. For submitting it before on arXiv needs cross-checking with the rules of the journal."? In general, if you can provide references to your claims, that would make this answer more reliable.

Thank you for the suggestion. What I have mentioned is from my experience while reading the top tier conference papers like NeurIPS, ICML, ICLR, AAAI, CVPR, ACL, EMNLP to name a few.

https://academia.stackexchange.com/questions/103713/what-license-to-use-while-putting-papers-on-the-arxiv
The default permission I mentioned, is actually: "arXiv.org perpetual, non-exclusive license to distribute this article (Minimal rights required by arXiv.org)". It is a non-Creative Common License that does not provide any exclusive rights to arxiv thereby being allowed in almost all the conference whose paper I have read. Wherever I am reading, people are saying to ask the editor directly to play safe. In reality, I see all papers from all conference on arxiv.

Among all the info on the major publications I could find, I found a common phrase that the paper should not be uploaded to a for-profit digital library. Arxiv is certainly not among them. The reason why editors do not oppose arxiv papers could be that there are a lot of papers that are uploaded to arxiv in order to claim to be first, so banning them would be a big loss.

IEEE: https://academia.stackexchange.com/questions/16831/is-it-legal-to-upload-a-paper-to-arxiv-when-it-is-under-double-blind-review-for
AAAI: https://www.quora.com/Can-I-upload-a-paper-to-arXiv-before-submitting-to-AAAI

@nbro, could you refer me to a major ML conference which strictly prohibits arxiv? Or would you suggest me to edit my answer which says it is better to ask the editor but in most cases the conference/jounals allow them?

For NeurIPS: The NeurIPS 2017 was held from 4th Dec whereas the latest version of this paper is of 6th Dec 2017: https://arxiv.org/abs/1706.03762

Please, just edit your post to include this information.


text:
How can I model and solve the Knight Tour problem with reinforcement learning?
I've read about the Knight Tour problem. And I wanted to try to solve it with a reinforcement learning algorithm with OpenAI's gym.
So, I want to make a bot that can move on the chess table like the knight. And it is given a reward each time it moves and does not leave the table or step in an already visited place. So, it gets better rewards if it survives more.
Or there is a better approach to this problem? Also, I would like to display the best knight in each generation.
I'm not very advanced at reinforcement learning (I'm still studying it), but this project really caught my attention. I know well machine learning and deep learning.
Do I need to start implementing a new OpenAI's gym environment and start all from scratch, or there is a better idea?

Hi and welcome to AI SE! Do you know how the Q-learning algorithm works?

Yes, but not in too complex situations

Model your problem as an MDP
To solve a problem with reinforcement learning, you need to model your problem as a Markov decision process (MDP), so you need to define

the state space,
the action space, and
the reward function

of the MDP.
Understand your problem and the goal
To do define these, you need to understand your problem and define it as a goal-oriented problem.
In the knight tour problem, there's a knight that needs to visit each square of a chessboard exactly once. The knight can perform only $L$-shaped moves (as for the rules of chess). See the animation below (taken from the related Wikipedia article).

The goal is then, by making $L$ moves, to find a path through the squares such that each square is visited exactly once.
What is the state space?
You could think that the state space $S$ could be the set of all squares of the chessboard. So, if you have an $n \times n$ chessboard, then $|S| = n^2$, i.e. you will have $n^2$ states.
However, this can be problematic because a square alone doesn't tell you all the information that you need to know to take the optimal action. So, you need to define the states such that all available information is available to the agent, i.e. you need to define a state as the position of the current square and the position of the other available squares.
What is the action space?
The action space could be defined as the set of all actions that the knight can take across all states. Given that the knight can only take $L$ moves, whenever the knight is in state $s$, only $L$-shaped actions are available. Of course, it is possible that, for each state $s$, there's more thane one valid $L$-shaped action. That's fine. However, the chosen $L$-shaped action will definitely affect your next actions, so we need a way of guiding the knight. That's the purpose of the reward function!
What is the reward function?
The reward function is typically the most crucial function that you need to define when modeling your problem as an MDP that needs to be solved with an RL algorithm.
In this case, you could give a reward of e.g. $1$ for each found path. More precisely, you will let your RL agent explore the environment. If it eventually finds a correct path (or solution), you will give it $1$. You could also penalise the knight if it ends in a situation where it cannot take an $L$-shaped action anymore. Given that you don't really want this to happen, you could give it a very small reward e.g. $-100$. Finally, you could give it a reward of $0$ for each action taken, which could imply that you don't really care about the actions that the knight takes, as long as it reaches the goal, i.e. find a path through the chessboard.
The design of the reward function will highly affect the behaviour and performance of your RL agent. The above-suggested reward function may actually not work well, so you may need to try different reward functions to get some satisfactory results.
Which RL algorithm to use?
Of course, you will also need to choose an RL algorithm to solve this problem numerically. The most common one is Q-learning. You can find its pseudocode here.
How to implement this with OpenAI's gym?
You probably need to create a custom environment and define the state and action spaces, as well as the reward function. I cannot tell you the details, but I think you can figure them out.
Is RL the right approach to solve this problem?
RL isn't probably the most efficient approach to solve this problem. There are probably more efficient solutions. For example, there's a divide-and-conquer approach, which I am not familiar with, but that you may also try to use and compare with the RL approach.
You could also read the paper Solution of the knight's Hamiltonian path problem on chessboards (1994), especially, if you are already familiar with the Hamiltonian path problem (HPP). Note that the knight tour problem is an instance of the HPP.

Thank you very much for your answer! I do really appreciate it! I'll try to implement it! :) And thanks a lot for the 2 links you put into your answer, I'll also read them!

I was redirected from StackOverflow to here and I'm surprised by how well you organized your answer:)

@MarcVana I like to write good answers (especially when they are related to a topic that I really like, in this case RL). I try my best to achieve that, but I know they are not perfect, but, hopefully, they will be at least useful :)

But I need to create an environment, right? So I need to type the line gym.make('some_string_here')'. What do I type in there? Or I need to create a new custom gym environment as shown here?

@MarcVana In this answer, I tried only to give you the foundations so that you could implement an RL algorithm to solve this problem. As I said in the answer, I think you will need to create a custom environment. How? I think you can figure these things out. Honestly, so far, I haven't used Gym but for simple or toy problems. If you have problems while using gym to solve this problem, I suggest you ask another more specific question. Note that my answer is already quite long. That means that your question was already quite broad.

Ok alright, I'm sorry for any inconvenience:) thanks again! I'll try it

@MarcVana To answer your question more directly, yes, I think you will need to create a custom environment (I edited my answer to say this).

@MarcVana Also, note that this site focus more on theoretical problems. We don't like programming issues :) See our on-topic page https://ai.stackexchange.com/help/on-topic for more details. Hopefully, I will see you around asking new questions (and maybe answer questions too) in the next days, weeks and months :)

Of course! For sure :)

Just to add to this answer that modeling state space isn't as simple as defining $n \times n$ board. If you do that you will not have fully observable environment so you would have to model it as POMDP. To make it MDP you would also need to have a set of flags to know which states you already visited. So to make it MDP, number of states is much larger than $n^2$

@Brale Yes, I also thought that my suggestion was problematic. But I didn't have a solution at the time. Thanks for pointing this out.

@Brale Let me know if you think that my last edit is sufficient to correct the answer. I think so.

@MarcVana Please, see my last edit to my question. As Brale pointed out above in a comment, it's problematic to define the states as the squares of the chessboard.

Yes, I see it now and I understand what you mean. Thanks both of you!


text:
How can we compute the ratio between the distributions if we don't know one of the distributions?
Here is my understanding of importance sampling. If we have two distributions $p(x)$ and $q(x)$, where we have a way of sampling from $p(x)$ but not from $q(x)$, but we want to compute the expectation wrt $q(x)$, then we use importance sampling.
The formula goes as follows:
$$
E_q[x] = E_p\Big[x\frac{q(x)}{p(x)}\Big]
$$
The only limitation is that we need a way to compute the ratio. Now, here is what I don't understand. Without knowing the density function $q(x)$, how can we compute the ratio $\frac{q(x)}{p(x)}$?
Because if we know $q(x)$, then we can compute the expectation directly.
I am sure I am missing something here, but I am not sure what. Can someone help me understand this?

The rationale behind importance sampling is that $q(x)$ is difficult to sample from but easy to evaluate. Or at least you can easily evaluate some $\tilde{q}$ such that:
$$
\tilde{q}(z) = Zq(z)
$$
where $Z$ (scalar) might be unknown. The geometrical example would be here e.g. sampling uniformly from an area under the curve $q(x)$ (in general it's not easy).

Because if we know $q(x)$, then we can compute the expectation directly.

That's the task we're trying to solve to begin with. And calculating expectation might be hard if we can't sample efficiently from $q$.
Say you want to compute an expectation of $x$, $E[x]$. For this you need to calculate the following integral:
$$
E[x] = \int{xq(x)dx}
$$
where $q$ is a probability distribution of $x$ for which you have an expression - so you can evaluate $q(x)$ (up to the constant of proportionality). This integral might be hard to evaluate analytically so we need to use other methods such as Monte Carlo. Let's say it is hard to generate samples from $q$ (as per example above, e.g. generating samples from the area under the curve $q(x)$ uniformly).
What you can do is to calculate an expectation under a simple distribution $p$ (proposal distribution) which is a distribution of your choice that needs to allow you to easily sample from it (say Gaussian). Then you can rewrite your integral as:
$$
E_q[x] = \int{xq(x)dx} = \int{xq(x) \color{blue}{\frac{p(x)}{p(x)}} dx}
= \int{x \frac{q(x)}{\color{blue}{p(x)}} \color{blue}{p(x)} dx}
= E_p \Big[{x\frac{q(x)}{p(x)}}\Big]
$$
(added index $p$ and $q$ to expectation to denote the sampling distribution). Now you can approximate the last expectation by Monte Carlo:
$$
E_p \Big[{x\frac{q(x)}{p(x)}}\Big] = \frac{1}{S} \sum_{s}{x^{(s)} \frac{q(x^{(s)})}{p(x^{(s)})} }, \ x^{(s)} \sim q(x)
$$

Comments are not for extended discussion; this conversation has been moved to chat.

It is common in Bayesian statistics to only know the posterior up to a constant of proportionality. This means that we can't directly sample from the posterior. However, using importance sample we are able to.
Consider our posterior density $\pi$ is only known up to some constant, i.e. $\pi(x) = K \tilde{\pi}(x)$, where $K$ is some constant and we only have $\tilde{\pi}$. Then by importance sampling we can evaluate the expectation of $X$ (or any function thereof) as follows by using a proposal density $q$:
\begin{align}
 \mathbb{E}_\pi[X] & = \int_\mathbb{R} x \frac{\pi(x)}{q(x)}q(x)dx \; ; \\
& = \frac{\int_\mathbb{R} x \frac{\pi(x)}{q(x)}q(x)dx}{\int_\mathbb{R}\frac{\pi(x)q(x)}{q(x)}dx} \; ;\\
& = \frac{\int_\mathbb{R} x \frac{\tilde{\pi}(x)}{q(x)}q(x)dx}{\int_\mathbb{R}\frac{\tilde{\pi}(x)q(x)}{q(x)}dx} \; ; \\
& = \frac{\mathbb{E}_q[xw(x)]}{\mathbb{E}_q[w(x)]} \; ;
\end{align}
where $w(x) = \frac{\tilde{\pi}(x)}{q(x)}$. Note that on line two we have not done anything crazy - as $\pi$ is a density we know that it integrates to one and then we multiply the integral by $1 = \frac{q(x)}{q(x)}$. The thing to notice is that the if we were to write $\pi(x) = K \tilde{\pi}(x)$ then the constants $K$ in the integrals would cancel, and so we have our result.
To summarise - we can sample from a distribution that is difficult/impossible to sample from (e.g. because we only know the density up to a constant of proportionality) by using importance sampling, as this allows us to calculate the importance ratio and use samples that are generated from a distribution of our choosing that is easier to sample from.
Note that importance sampling isn't just used in Bayesian statistics - for instance it could be used in Reinforcement Learning as an off policy way of sampling from the environment whilst still evaluating the value of the policy you're interested in.
edit: as requested I have added a concrete example
As an example to make things concrete - suppose we have $Y_i | \theta \sim \text{Poisson}(\theta)$ and we are interested in $\theta \in (0, \infty)$. The likelihood function for the Poisson distribution is
    $$ f(\textbf{y} | \theta) = \prod\limits_{i=1}^n \frac{\theta^{y_i}\exp(-\theta)}{y_i\!}\;.$$
We can then assign a gamma prior to $\theta$, that is we say that $\theta \sim \text{Gamma}(a,b)$ with density
    $$\pi(\theta) \propto \theta^{a-1} \exp(-b\theta)\;.$$
By applying Bayes rule our posterior is then
    \begin{align}
    \pi(\theta|\textbf{y}) & \propto f(\textbf{y} | \theta) \pi(\theta) \\
    & = \prod\limits_{i=1}^n \frac{\theta^{y_i}\exp(-\theta)}{y_i\!} \times \theta^{a-1} \exp(-b\theta) \\
    & = \theta^{\sum\limits_{i=1}^n y_i + a - 1} \exp(-[n+b]\theta)\;.
\end{align}
Now we know that this is the kernel of a Gamma($\sum\limits_{i=1}^n y_i + a$, $n+b$) distribution, but assume that we didn't know this and didn't want to calculate the normalising integral. This would mean that we are not able to calculate the mean of our posterior density, or even sample from it. This is where we can use importance sampling, for instance we could choose an Exponential(1) proposal distribution.
We would sample say 5000 times from the exponential distribution and then calculate the two expectations using MC integration and obtain an estimate for the mean of the posterior. NB that in this example $X$ from earlier would be $\theta$ in this example.
Below is some Python code to further demonstrate this.
import numpy as np

np.random.seed(1)

# sample our data
y = np.random.poisson(lam=0.5,size = 100)

# sample from proposal
samples_from_proposal = np.random.exponential(scale=1,size=5000)

# set parameters for the prior
a = 5; b = 3

def w(x, y, a, b):
    # calculates the ratio between our posterior kernel and proposal density
    pi = x ** (np.sum(y) + a - 1) * np.exp(-(len(y) + b) * x)
    q = np.exp(-x)
    return pi/q

# calculate the top expectation
top = np.mean(samples_from_proposal * w(samples_from_proposal,y,a,b))

# calculate the bottom expectation
bottom = np.mean(w(samples_from_proposal,y,a,b))

print(top/bottom)

# calculate the true mean since we knew the posterior was actually a gamma density
true_mean = (np.sum(y) + a)/(len(y) + b)
print(true_mean)

Running this you should see that the Expectation from importance sampling is 0.5434 whereas the true mean is 0.5436 (both of which are close to the true value of $\theta$ that I used to simulate the data from) so importance sampling approximates the expectation well.


text:
What's the difference between LSTM and GRU?
I have been reading about LSTMs and GRUs, which are recurrent neural networks (RNNs). The difference between the two is the number and specific type of gates that they have. The GRU has an update gate, which has a similar role to the role of the input and forget gates in the LSTM.
Here's a diagram that illustrates both units (or RNNs).

With respect to the vanilla RNN, the LSTM has more "knobs" or parameters. So, why do we make use of the GRU, when we clearly have more control over the neural network through the LSTM model?
Here are two more specific questions.

When would one use Long Short-Term Memory (LSTM) over Gated Recurrent Units (GRU)?

What are the advantages/disadvantages of using LSTM over GRU?

Did you see this post? When to use GRU over LSTM? at Data Science SE.

On the same problems, sometimes GRU is better, sometimes LSTM.
In short, having more parameters (more "knobs") is not always a good thing. The training process needs to learn those parameters. There is a higher chance of over-fitting, amongst other problems.
The parameters are assigned specific roles inside either GRU or LSTM, so if that role is less important for a specific learning challenge, then it can be wasteful or even counter-productive to have the system attempt to learn values for them.
The only way to find out if LSTM is better than GRU on a problem is a hyperparameter search. Unfortunately, you cannot simply swap one for the other, and test that, because the number of cells that optimises a LSTM solution will be different to the number that optimises a GRU.

When would one use Long Short-Term Memory (LSTM) over Gated Recurrent Units (GRU)?

When it proves better, experimentally. In some problem domains, this may be established and you can check. However, in other problem domains if either GRU or LSTM works well enough to solve a problem (and the superiority of either LSTM or GRU is not the main point of the work), then it may not so clear.

Overall, this answer seems to be correct, but I think this answer would improve considerably if you provided some concrete examples of applications/problems where GRU was used over LSTM (or vice-versa) and why it was used. This would at least provide some more "proof" that the preference for one or the other may be context-dependent.


text:
Is the test time the phase when the model's accuracy is calculated with test data set?
When papers talk about the "test time", does this mean the phase when the model is passed with new data instances to derive the accuracy of the test data set? Or is "test time" the phase when the model is fully trained and launched for real-world input data?

If it is not defined otherwise, testing is the phase where the model is passed with new data instances to derive the score of the test set. It should not be confused with validation set.
A validation dataset is a sample of data held back from training your model that is used to give an estimate of model skill while tuning model’s hyperparameters during training. There are a lot of methods of validation with k-fold cross-validation being one of the most popular.
In k-fold cross-validation, the original training set is randomly partitioned into k equal sized subsamples. Of the k subsamples, a single subsample is retained as the validation data for validating the model, and the remaining k − 1 subsamples are used as training data. The cross-validation process is then repeated k times, with each of the k subsamples used exactly once as the validation data for the each epoch. The k results can then be averaged to produce a single estimation. The advantage of this method over repeated random sub-sampling is that all observations are used for both training and validation, and each observation is used for validation exactly once.
The validation dataset is different from the test set that is also held back from the training of the model, but is instead used to give an unbiased estimate of the skill of the final tuned model when comparing or selecting between final models.


text:
How is the Jacobian a generalisation of the gradient?
I came across these slides Natural Language Processing with Deep Learning CS224N/Ling284, in the context of natural language processing, which talk about the Jacobian as a generalization of the gradient.
I know there is a lot of topic regarding this on the internet, and trust me, I've googled it. But things are getting more and more confused for me.
In simple words, how is the Jacobian a generalization of the gradient? How can it be used in gradient descent?

In short, the Jacobian matrix is a generalization of the gradient for vector-valued functions.
Recall that the gradient is a vector of partial derivatives of a multi-variable function. So, consider a multi-variable function of the form $f: \mathcal{X}_1 \times \mathcal{X}_2 \times \dots \times \mathcal{X}_N \rightarrow \mathcal{Y}$. The output of this function is $f(x_1, x_2, \dots, x_N) = y$, where $x_i \in \mathcal{X}_i$, for $i=1, \dots, N$ and $y \in \mathcal{Y}$. And the gradient is $\nabla f = \left[ \frac{\partial f}{\partial x_1}, \dots, \frac{\partial f}{\partial x_N} \right] \in \mathbb{R}$.
A vector-valued function is a function whose output is a vector, i.e. a function of the form $f: \mathcal{X} \rightarrow \mathcal{Y}_1 \times \mathcal{Y}_2 \times \dots \times \mathcal{Y}_M$ (I am not sure if this notation is rigorous enough!), so the output of this function is a vector $f(x) = [y_1, y_2, \dots, y_M]$, where $x \in \mathcal{X}$ and $y_i \in \mathcal{Y}_i$, for $i = 1, \dots, M$. You can also view a vector-valued function $f$ as a vector of scalar-valued functions $[f_1, f_2, \dots, f_M]$, where $f_i: \mathcal{X} \rightarrow \mathcal{Y}_i$, for all $i$.
You can also have multi-variable vector-valued functions, i.e. functions of the form
$$f: \mathcal{X}_1 \times \mathcal{X}_2 \times \dots \times \mathcal{X}_N \rightarrow \mathcal{Y}_1 \times \mathcal{Y}_2 \times \dots \times \mathcal{Y}_M.$$
The Jacobian matrix is an $N \times M$ matrix with one partial derivative for each combination of inputs and outputs (i.e. $f_i$).
If you want to optimize a multi-variable vector-valued function, you can make use of the Jacobian, in a similar way that you make use of the gradient in the case of multi-variable functions, but, although I've seen it in the past, I can't provide now a concrete example of an application of the Jacobian (but the linked slides probably do that).

authors: حسام الشاذلي