text:
Can we use ML to do anything else other than predicting (in the case of mathematical problems)?
(The math problem here just serves as an example, my question is on this type of problems in general).
Given two Schur polynomials, $s_\mu$, $s_\nu$, we know that we can decompose their product into a linear combination of other Schur polynomials.
$$s_\mu s_\nu = \sum_\lambda c_{\mu,\nu}^\lambda s_\lambda$$
and we call $c_{\mu,\nu}^\lambda$ the LR coefficient (always an non-negative integer).
Hence, a natural supervised learning problem is to predict whether the LR coefficient is of a certain value or not given the tuple $<\mu, \nu, \lambda>$. This is not difficult.
My question is: can we either use ML/RL to do anything else other than predicting (in this situation) or extract anything from the prediction result? In other words, a statement like "oh, I am 98% confident that this LR coefficient is 0" does not imply anything mathematically interesting?

I've edited this post in order to try to clarify what you're asking. I'm still not sure what you were asking and the given answer below just confirms that your question was a bit open to interpretation, which is bad. Please, now that you probably have a clearer idea of what you had in mind, review this post (including the title that I've added) and try to clarify what you were really asking. What does it mean "do anything else other than predicting"? Are you asking whether an ML model can do something else other than what it was trained to do?

There are quite a few examples of papers where they try and 'teach' neural networks to 'learn' how to solve math problems. Most of the time, sadly, it comes down to training on a large dataset after which the network can 'solve' the sort of basic problems, but is unable to generalize this to larger problems. That is, if you train a neural network to solve addition, it will be inherently constrained by the dataset. It might be able to semi-sufficiently solve addition with 3 or even 4 digits, depending on how big your dataset is, but throw in an addition question containing 2 10 digit numbers, and it will almost always fail.
The latest example that I can remember where they tried this is in the General Language Model GPT-3, which was not made to solve equations per se, but does 'a decent job' on the stuff that was in the dataset. Facebook AI made an 'advanced math solver' with a specific architecture that i have not looked into which might disproof my point, but you can look into that.
In the end, this comes down to 'what is learning' and 'what do you want to accomplish'. Most agree that these network are not able to generalize beyond their datasets. Some might say that not being able to generalize does not mean that it is not learning. It might just be learning slower. I believe that these models are inherently limited to what is presented in the dataset. Given a good dataset, it might be able to generalize to cases 'near and in-between', but I have yet to see a case where this sort of stuff generalizes to cases 'far outside' the dataset.

Are all known types of neural networks equal in terms of this? In other words, regardless of their validation accuracy, is there some types of neural network that get closer to conclusive results than others?

So specific architectures will always outperform more 'general' architectures on specific problems, right. This is also what FacebookAI did with their advanced math solver. Though this will most likely not be the best approach for the specific problem once we get more data and more computational power. For a nice thought experiment, make sure to look up 'The Bitter Lesson' by Rich Sutton who also talks about this.

Crutch of it is: yes, if we put 'our own knowledge' into structures/processes/techniques they will perform better right now, but in 10 years someone will come along and demolish these results with more computational power in a generic structure.

So, not all known types of neural networks perform equal in terms of this, but in my opinion this is not the way you should want to look at this. There is no 'proven' benefit of some specific structures for this kind of learning like CNNs have over ANNs for images.

How then they managed to teach it to program?

Sorry, but i do not understand your comment. Could you please elaborate on what exactly what you are asking, and how it is related to this particular question?


text:
Is the VC Dimension meaningful in the context of Reinforcement Learning?
Is the VC dimension meaningful for reinforcement learning (RL), as a machine learning (ML) method? How?

Yes, it is. This article (Approximate Planning in Large POMDPs via Reusable Trajectories) explain about it by means of the trajectory tree:

A trajectory tree is a binary tree in which each node is labeled by a state and observation
pair, and has a child for each of the two actions. Additionally, each link to a child is
labeled by a reward, and the tree's depth will be $H_\epsilon$, so it will have about $2^{H_\epsilon}$ nodes. The root is labeled by $s_0$ and the observation there, $o_0$.

Now a policy $\pi$ will be defined like the following base on the trajectory tree:

For any deterministic strategy $\pi$ and any trajectory tree $T$, $\pi$ defines a path through
$T$: $\pi$ starts at the root, and inductively, if $\pi$ is at some internal node in $T$, then we feed to $\pi$ the observable history along the path from the root to that node, and $\pi$ selects and moves to a child of the current node. This continues until a leaf node is reached, and we define $R(\pi, T)$ to be the discounted sum of returns along the path taken. In the case that $\pi$ is stochastic, $\pi$ defines a distribution on paths in $T$, and $R(\pi, T)$ is the expected return according to this distribution.  Hence, given $m$ trajectory trees $T_1 , \ldots , T_m$, a natural estimate for $V^\pi(s_0)$ is $V^\pi(s_0) = \frac{1}{m}\sum_{i=1}^mR(\pi, T_i)$. *Note that each tree can be used to evaluate any
strategy, much the way a single labeled example $\langle x, f(x)\rangle$ can be used to evaluate any hypothesis $h(x)$ in supervised learning. Thus in this sense, trajectory trees are reusable.

Now similar to definition of VC theory for classification methods:

Our goal now is to establish uniform convergence results that bound the error of the estimates $V^\pi(s_0)$ as a function of the "sample size" (number of trees) $m$.

And finally, we have the following theorem:

Let $\Pi$ be any finite class of deterministic strategies for an arbitrary two-action POMDP $M$. Let $m$ trajectory trees be created using a generative model for $M$, and
$\widehat{V}^\pi(s_0)$ be the resulting estimates. If $m = O((V_{\max}/\epsilon)^2(\log(|\Pi|) + \log(1/\delta)))$, then with probability $1 - \delta$, $|V^\pi(s_0) - \widehat{V}^\pi(s_0)|\leqslant \epsilon$ holds simultaneously for all $\pi \in \Pi$.

About the VC dimension of $\Pi$, if we suppose we have two actions $\{a_1, a_2\}$ (it can be generalized to more actions), we can say:

If $\Pi$ is a (possibly infinite) set of deterministic strategies, then each strategy $\pi \in \Pi$ is simply a deterministic function mapping from the set of observable histories to the set $\{a_1, a_2\}$,
and is thus a boolean function on observable histories. We can, therefore, write $\mathcal{VC}(\Pi)$ to
denote the familiar VC dimension of the set of binary functions $\Pi$. For example, if $\Pi$ is
the set of all thresholded linear functions of the current vector of observations (a particular
type of memoryless strategy), then $\mathcal{VC}(\Pi)$ simply equals the number of parameters.

and the following theorem:

Let $\Pi$ be any class of deterministic strategies for an arbitrary two-action
POMDP $M$, and let $\mathcal{VC}(\Pi)$ denote its VC dimension. Let $m$ trajectory trees be created using a generative model for $M$, and $\widehat{V}^\pi(s_0)$ be the resulting estimates. If:
$$
m = O((V_{\max}/\epsilon)^2(H_\epsilon\mathcal{VC}(\Pi)\log(V_{\max}/\epsilon) + \log(1/\delta)))
$$
then with probability $1 - \delta$, $|V^\pi(s_0) - \widehat{V}^\pi(s_0)|\leqslant \epsilon$ holds simultaneously for all $\pi \in \Pi$.

source: Stack Exchange

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

sort: votes


text:
What do the notations $\sim$ and $\Delta (A) $ mean in the paper "Fairness Through Awareness"?
In this paper Fairness Through Awareness, the notation $\mathbb{E}_{x \sim V} \mathbb{E}_{a \sim \mu_x} L(x,a)$ is being used (page 5 top line), where $V$ denotes the set of individuals (so I guess set of feature vectors?) and the meaning of the other variables can be found in the paragraph above the mentioned notation. What does the $\sim$ in the expectation stand for?
Another notation that I do not know is $\Delta (A) $, where $A$ is the set of outcomes, for instance, $A = \{ 0,1\}$. What does it stand for?

The $\sim$ symbol means that a random variable is drawn from the given distribution, i.e. if I were to say $X$ has a Standard Normal distribution I would write $X \sim \text{Normal}(0,1)$. They write two explicit expectations here because $a$ is a random variable with distribution $\mu_x$ but $X$ is also a random variable with distribution $V$. I believe you are right that $V$ would be analogous to a set of features. So we are saying that $X$ is a random variable over the distribution over the features, or individuals in this context.
As for the $\Delta(A)$, I have never seen this notation used before -- I am not sure if it is standard notation. I Googled to see if it was something that I just hadn't seen before, but there was no such answer. However, from the context of the paper they define $M: V \rightarrow \Delta (A)$ to be mappings from individuals to probability distributions over $A$, so I guess that $\Delta (A) $ is probability distributions over $A$.

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


text:
What are the main algorithms used in computer vision?
Nowadays, CV has really achieved great performance in many different areas. However, it is not clear what a CV algorithm is.
What are some examples of CV algorithms that are commonly used nowadays and have achieved state-of-the-art performance?

There are many computer vision (CV) algorithms and models that are used for different purposes. So, of course, I cannot list all of them, but I can enumerate some of them based on my experience and knowledge. Of course, this answer will only give you a flavor of the type of algorithm or model that you will find while solving CV tasks.
For example, there are algorithms that are used to extract keypoints and descriptors (which are often collectively called features, although the descriptor is the actual feature vector and the keypoint is the actual feature, and in deep learning this distinction between keypoints and descriptors does not even exist, AFAIK) from images, i.e. feature extraction algorithms, such as SIFT, BRISK, FREAK, SURF or ORB. There are also edge and corner detectors. For example, the Harris corner detector is a very famous corner detector.
Nowadays, convolutional neural networks (CNNs) have basically supplanted all these algorithms in many cases, especially when enough data is available. Rather than extracting the typical features from an image (such as corners), CNNs extract features that are most useful to solve the task that you want to solve by taking into account the information in the training data (which probably includes corners too!). So, sometimes CNNs are more specifically called data-driven feature extractors. There are different types of CNNs. For example, CNNs that were designed for semantic segmentation (which is a CV task/problem), such as the u-net, or CNNs that were designed for instance segmentation, such as mask R-CNN.
There are also algorithms that can be used to normalize features, such as the bag-of-features algorithm, which can be used to create fixed-size feature vectors. This can be particularly useful for tasks like content-based image retrieval.
There are many other algorithms that could be considered CV algorithms or are used to solve CV tasks. For example, RanSaC, which is a very general algorithm to fit models to data in the presence of outliers, can be used to fit homographies (matrices that are generally used to transform planes to other planes) that transform pixels of one image to another coordinate system of another image. This can be useful for the purpose of template matching (which is another CV task), where you want to find a template image in another target image. This is very similar to object detection.
There are also many image processing algorithms and techniques that are heavily used in computer vision. For example, all the filters (such as Gaussian, median, bilateral, non-local means, etc.) that can be used to smooth, blur or de-noise images. Nowadays, some deep learning techniques have also replaced some of these filters and image processing techniques, such as de-noising auto-encoders.
All these algorithms and models have something in common: they are used to process images and/or get low- or high-level information from images. Most of them are typically used to extract features (i.e. regions of the images that are relevant in some way) from images, so that they can later be used to train a classifier or regressor to perform some kind of task (e.g. find and distinguish the objects, such people, cars, dogs, etc. in an image). The classifiers/regressors are typically machine learning (ML) models, such as SVMs or fully-connected neural networks, but there's a high degree of overlap between CV and ML because some ML tools are used to solve CV tasks (e.g. image classification).

Why doesn't this have more upvotes?  This is exactly what I was looking for to refresh my memory after years since my last Computer Vision course

Computer vision is a wide field, and besides the fact that deep learning dominates, there are still many, many other algorithms that see widespread use in both academia and industry.
For tasks such as image classification / object recognition, the typical paradigm is some CNN architecture such as a ResNet or VGG. There has been lots of works to extend and improves the CNNs, but the basic architecture has not really changed much over the years. Interestingly, there's been some work to encode more complex inductive biases / invariants into the deep learning modelling process, such as Spatial Transformer Networks and Group Equivariant Networks. More classical vision approaches to such problems typically include computing some form of hand-crafted feature (HOG, LBP), and training any off-the-shelf classifier.
For object detection, the de-facto for many years was Viola-Jones for it's combination of performance and speed (even though there were more accurate systems at the time, but they were slower). More recently, object detection has been dominated by deep learning, with architectures such as SSD, YOLO, all the RCNN variants, etc.
A related problem to object detection is segmentation. Deep learning again dominates in this area with algorithms such as Mask RCNN. However, many other approaches exist and see some use, such as superpixels (e.g. SLIC), watershed, and normalized cuts.
For problems such as image search, vision approaches such as Fisher vectors and VLAD (computed from image descriptors such as SIFT or SURF) are still competitive. However, CNN features have also seen use in this domain.
For video analysis, CNNs (typically, 3D CNNs) are popular. However, they often leverage other vision techniques such as optical flow. The most popular optical flow algorithms are Brox, TVL-1, KLT, and Farneback. There are more recent approaches which attempt to use deep learning to actually learn the optical flow, though.
An overarching set of techniques that has so many varying applications are interest point detectors, image descriptors, and feature encoding techniques. Interest point detectors attempt to localise interest points in an image or video, and popular detectors include Harris, FAST, and MSER. Image descriptors are used to describe those interest points. Example descriptors include SIFT, SURF, KAZE, and ORB. The descriptors themselves can be used to do various things such as estimate homographies using the RANSAC algorithm (for applications such as panorama and camera stabilisation). However, the descriptors can also be encoded and pooled into a single fixed-length feature vector, which serves as the representation of the image. The most common approach to this encoding is bag of feature / bag of visual words. This is based on K-means. However, popular extensions / variants include Fisher vectors and VLAD.
Self-supervised and semi-supervised learning is also very popular nowadays in academia, and seeks to get the most of out the abundant unlabelled data. In a computer vision context, popular techniques include MoCo and SimCLR, but new methods are released almost weekly!
Another problem domain in computer vision is the ability to generate / synthesize images. The is not unique to computer vision, but the common algorithms for this are variational autoencoders (VAEs) and generative adversarial networks (GANs).


text:
From an implementation point of view, what are the main differences between an RNN and a CNN?
I understand that in general an RNN is good for time series data and a CNN image data, and have noticed many blogs explaining the fundamental differences in the models.
As a beginner in machine learning and coding, I would like to know from the code perspective, what the differences between an RNN and CNN are in a more practical way.
For instance, I think most CNNs dealing with image data use Conv1D  or Conv2D and MaxPooling2D layers and require reshaping input data with code looks something like this Input(shape=(64, 64, 1)).
What are some other things that distinguish CNNs from RNNs from a coding perspective?

In Convolutional Neural Networks (CNNs) you have small kernels (or filters) that you slide over an input (e.g. image). The value resulting from the convolution of the filter with a subset of the image over which the filter is currently positioned is then put into its respective cell in the output of that layer. Essentially, training CNNs boils down to training small filters, for example for detecting edges or corners etc. in input data, which most frequently happens to be images indeed. The assumption here is that features can be detected locally in the input volume, which entails that the nature of the input data shall be coherent over the entire volume of input data.
Recurrent Neural Networks (RNNs) do not work locally, but are applied to sequences of arbitrary input data, where one input node may receive sensor readings, while the next node receives the date on which the sensor reading was measured. Of such arbitrary data, you feed a sequence through the RNN, which always keeps its own internal state from processing the previous instance/sample in the sequence in memory while processing the next data point/sample in the sequence. Depending on the kind of recurrent cell type that is employed to construct a RNN layer, the memory of the previous internal state then affects the computation of the next internal state and/or output computed when working on the next data sample. So, information of past data points/samples is carried forward while iterating though a sequence.
In short, CNNs are meant to detect local features in volume data, while RNNs preserve information over their previous internal state while processing the next data sample.
Probably one of the best online resources walking you through all the related concepts step by step is the following lecture series offered by the Stanford University.


text:
What is the relationship between gradient accumulation and batch size?
I am currently training some models using gradient accumulation since the model batches do not fit in GPU memory. Since I am using gradient accumulation, I had to tweak the training configuration a bit. There are two parameters that I tweaked: the batch size and the gradient accumulation steps. However, I am not sure about the effects of this modification, so I would like to fully understand what is the relationship between the gradient accumulation steps parameter and the batch size.
I know that when you accumulate the gradient you are just adding the gradient contributions for some steps before updating the weights. Normally, you would update the weights every time you compute the gradients (traditional approach):
$$w_{t+1} = w_t - \alpha \cdot \nabla_{w_t}loss$$
But when accumulating gradients you compute the gradients several times before updating the weights (being $N$ the number of gradient accumulation steps):
$$w_{t+1} = w_t - \alpha \cdot \sum_{0}^{N-1} \nabla_{w_t}loss$$
My question is: What is the relationship between the batch size $B$ and the gradient accumulation steps $N$?
By example: are the following configurations equivalent?

$B=8, N=1$: No gradient accumulation (accumulating every step), batch size of 8 since it fits in memory.
$B=2, N=4$: Gradient accumulation (accumulating every 4 steps), reduced batch size to 2 so it fits in memory.

My intuition is that they are but I am not sure. I am not sure either if I would have to modify the learning rate $\alpha$.

There isn't any explicit relation between the batch size and the gradient accumulation steps, except for the fact that gradient accumulation helps one to fit models with relatively larger batch sizes (typically in single-GPU setups) by cleverly avoiding memory issues. The core idea of gradient accumulation is to perform multiple backward passes using the same model parameters before updating them all at once for multiple batches. This is unlike the conventional manner, where the model parameters are updated once every batch-size number of samples. Therefore, finding the correct batch-size and accumulation steps is a design trade-off that has to be made based on two things: (i) how much increase in the batch-size can the GPU handle, and (ii) whether the gradient accumulation steps result in at least as much better performance than without accumulation.
As for your example configurations, there are the same in theory. But, there are a few important caveats that need to be addressed before proceeding with this intuition.

Using Batch Normalization with gradient accumulation generally does not work well, simply because BatchNorm statistics cannot be accumulated. A better solution would be to use Group Normalization instead of BatchNorm.
When performing a combined update in gradient accumulation, it must be ensured that the optimizer is not initialized to zero (i.e. optimizer.zero_grad()) for every backward update (i.e. loss.backward()). It is easy to include both statements in the same for loop while training which defeats the purpose of gradient accumulation.

Here are some interesting resources to find out more about it detail.

Thomas Wolf's article on different ways of combating memory issues.
Kaggle discussions on the effect on learning rate: here and here.
A comprehensive answer on gradient accumulation in PyTorch.

Thank you for your answer. The caveats section was specially helpful. I was already aware of point (2) but point (1) was very ilustrative. As you hint, it seems it is better to move to multi GPU... I'll add it to the TODO list.

What happens if we have a variable batch-size during gradient accumulation? I used to normalize my gradients by the number of accumulation steps but now I've moved to a bucketing technique that results in lesser samples the longer the input sequence gets.

As I understand it, can accumulating gradients be used to simulate arbitrarily large batch sizes? If the gradients are just added for each minibatch, then shouldn't one be able to scale N (the number of iterations before accumulation) to be arbitrarily large?

Don't you mean "multiple forward passes"? "Multiple backward passes before updating parameters" is a sentence that doesn't make any sense because a backward pass is updating parameters.


text:
Do convolutional neural networks perform convolution or cross-correlation?
Typically, people say that convolutional neural networks (CNN) perform the convolution operation, hence their name. However, some people have also said that a CNN actually performs the cross-correlation operation rather than the convolution. How is that? Does a CNN perform the convolution or cross-correlation operation? What is the difference between the convolution and cross-correlation operations?

The difference between them is that convolution "flips" the filter kernel, but cross-correlation does not. Mathematically, cross-correlation and convolution are adjoints of each other

Short answer
Theoretically, convolutional neural networks (CNNs) can either perform the cross-correlation or convolution: it does not really matter whether they perform the cross-correlation or convolution because the kernels are learnable, so they can adapt to the cross-correlation or convolution given the data, although, in the typical diagrams, CNNs are shown to perform the cross-correlation because (in libraries like TensorFlow) they are typically implemented with cross-correlations (and cross-correlations are conceptually simpler than convolutions). Moreover, in general, the kernels can or not be symmetric (although they typically won't be symmetric). In the case they are symmetric, the cross-correlation is equal to the convolution.
Long answer
To understand the answer to this question, I will provide two examples that show the similarities and differences between the convolution and cross-correlation operations. I will focus on the convolution and cross-correlation applied to 1-dimensional discrete and finite signals (which is the simplest case to which these operations can be applied) because, essentially, CNNs process finite and discrete signals (although typically higher-dimensional ones, but this answer applies to higher-dimensional signals too). Moreover, in this answer, I will assume that you are at least familiar with how the convolution (or cross-correlation) in a CNN is performed, so that I do not have to explain these operations in detail (otherwise this answer would be even longer).
What is the convolution and cross-correlation?
Both the convolution and the cross-correlation operations are defined as the dot product between a small matrix and different parts of another typically bigger matrix (in the case of CNNs, it is an image or a feature map). Here's the usual illustration (of the cross-correlation, but the idea of the convolution is the same!).

Example 1
To be more concrete, let's suppose that we have the output of a function (or signal) $f$ grouped in a matrix $$f = [2, 1, 3, 5, 4] \in \mathbb{R}^{1 \times 5},$$ and the output of a kernel function also grouped in another matrix $$h=[1, -1] \in \mathbb{R}^{1 \times 2}.$$  For simplicity, let's assume that we do not pad the input signal and we perform the convolution and cross-correlation with a stride of 1 (I assume that you are familiar with the concepts of padding and stride).
Convolution
Then the convolution of $f$ with $h$, denoted as $f \circledast h = g_1$, where $\circledast$ is the convolution operator, is computed as follows
\begin{align}
f \circledast h = g_1
&=\\
[(-1)*2 + 1*1, \\
(-1)*1 + 1*3, \\
(-1)*3 + 1*5, \\
(-1)*5+1*4]
&=\\
[-2 + 1, -1 + 3, -3 + 5, -5 + 4]
&=\\
[-1, 2, 2, -1] \in \mathbb{R}^{1 \times 4}
\end{align}
So, the convolution of $f$ with $h$ is computed as a series of element-wise multiplications between the horizontally flipped kernel $h$, i.e. $[-1, 1]$, and each $1 \times 2$ window of $f$, each of which is followed by a summation (i.e. a dot product). This follows from the definition of convolution (which I will not report here).
Cross-correlation
Similarly, the cross-correlation of $f$ with $h$, denoted as $f \otimes h = g_2$, where $\otimes$ is the cross-correlation operator, is also defined as a dot product between $h$ and different parts of $f$, but without flipping the elements of the kernel before applying the element-wise multiplications, that is
\begin{align}
f \otimes h = g_2
&=\\
[1*2 + (-1)*1, \\
1*1 + (-1)*3, \\
1*3 + (-1)*5, \\
1*5 + (-1)*4]
&=\\
[2 - 1, 1 - 3, 3 - 5, 5 - 4]
&=\\
[1, -2, -2, 1] \in \mathbb{R}^{1 \times 4}
\end{align}
Notes

The only difference between the convolution and cross-correlation operations is that, in the first case, the kernel is flipped (along all spatial dimensions) before being applied.

In both cases, the result is a $1 \times 4$ vector. If we had convolved $f$ with a $1 \times 1$ vector, the result would have been a $1 \times 5$ vector. Recall that we assumed no padding (i.e. we don't add dummy elements to the left or right borders of $f$) and stride 1 (i.e. we shift the kernel to the right one element at a time). Similarly, if we had convolved $f$ with a $1 \times 3$, the result would have been a $1 \times 3$ vector (as you will see from the next example).

The results of the convolution and cross-correlation, $g_1$ and $g_2$, are different. Specifically, one is the negated version of the other. So, the result of the convolution is generally different than the result of the cross-correlation, given the same signals and kernels (as you might have suspected).

Example 2: symmetric kernel
Now, let's convolve $f$ with a $1 \times 3$ kernel that is symmetric around the middle element, $h_2 = [-1, 2, -1]$. Let's first compute the convolution.
\begin{align}
f \circledast h_2 = g_3
&=\\
[(-1)*2 + (2)*1 + (-1)*3,\\
(-1)*1 + (2)*3 + (-1)*5,\\
(-1)*3 + (2)*5 + (-1)*4]
&=\\
[-2 + 2 + -3,\\
-1 + 6 + -5,\\
-3 + 10 + -4]
&=\\
[-3, 0, 3]
\in \mathbb{R}^{1 \times 3}
\end{align}
Now, let's compute the cross-correlation
\begin{align}
f \otimes h_2 = g_4
&=\\
[(-1)*2 + (2)*1 + (-1)*3, \\
(-1)*1 + (2)*3 + (-1)*5, \\
(-1)*3 + (2)*5 + (-1)*4]
&=\\
[-3, 0, 3]
\in \mathbb{R}^{1 \times 3}
\end{align}
Yes, that's right! In this case, the result of the convolution and the cross-correlation is the same. This is because the kernel is symmetric around the middle element. This result applies to any convolution or cross-correlation in any dimension. For example, the convolution of the 2d Gaussian kernel (a centric-symmetric kernel) and a 2d image is equal to the cross-correlation of the same signals.
CNNs have learnable kernels
In the case of CNNs, the kernels are the learnable parameters, so we do not know beforehand whether the kernels will be symmetric or not around their middle element. They won't probably be. In any case, CNNs can perform either the cross-correlation (i.e. no flip of the filter) or convolution: it does not really matter if they perform cross-correlation or convolution because the filter is learnable and can adapt to the data and tasks that you want to solve, although, in the visualizations and diagrams, CNNs are typically shown to perform the cross-correlation (but this does not have to be the case in practice).
Do libraries implement the convolution or correlation?
In practice, certain libraries provide functions to compute both convolution and cross-correlation. For example, NumPy provides both the functions convolve and correlate to compute both the convolution and cross-correlation, respectively. If you execute the following piece of code (Python 3.7), you will get results that are consistent with my explanations above.
# Using Python 3.11.9 and NumPy 2.0.2

import numpy as np

f = np.array([2.0, 1.0, 3.0, 5.0, 4.0])

h = np.array([1.0, -1.0])

conv = np.convolve(f, h, mode="valid")
cross = np.correlate(f, h, mode="valid")

print(f"Convolution of f = {f} and h = {h} = {conv}")
print(f"Correlation of f = {f} and h = {h} = {cross}")

h2 = np.array([-1.0, 2.0, -1.0])

conv = np.convolve(f, h2, mode="valid")
cross = np.correlate(f, h2, mode="valid")

print(f"Convolution of f = {f} and h2 = {h} = {conv}")
print(f"Correlation of f = {f} and h2 = {h} = {cross}")

Result
Convolution of f = [2. 1. 3. 5. 4.] and h = [ 1. -1.] = [-1.  2.  2. -1.]
Correlation of f = [2. 1. 3. 5. 4.] and h = [ 1. -1.] = [ 1. -2. -2.  1.]
Convolution of f = [2. 1. 3. 5. 4.] and h2 = [ 1. -1.] = [-3.  0.  3.]
Correlation of f = [2. 1. 3. 5. 4.] and h2 = [ 1. -1.] = [-3.  0.  3.]

However, NumPy is not really a library that provides out-of-the-box functionality to build CNNs.
On the other hand, TensorFlow's and PyTorch's functions to build the convolutional layers actually perform cross-correlations. As I said above, although it does not really matter whether CNNs perform the convolution or cross-correlation, this naming is misleading. Here's a proof that TensorFlow's tf.nn.conv1d actually implements the cross-correlation.
# Using Python 3.11.9 and TensorFlow 2.18.0

import tensorflow as tf

f = tf.constant([2.0, 1.0, 3.0, 5.0, 4.0], dtype=tf.float32)
h = tf.constant([1.0, -1.0], dtype=tf.float32)

# Reshaping the inputs because conv1d accepts only certain shapes.
f = tf.reshape(f, [1, int(f.shape[0]), 1])
h = tf.reshape(h, [int(h.shape[0]), 1, 1])

c = tf.nn.conv1d(f, h, stride=1, padding="VALID")

# Using tf.squeeze to improve readability.
print(f"conv1d of f = {tf.squeeze(f)} and h = {tf.squeeze(h)} = {tf.squeeze(c)}")

Result
conv1d of f = [2. 1. 3. 5. 4.] and h = [ 1. -1.] = [ 1. -2. -2.  1.]

Further reading
After having written this answer, I found the article Convolution vs. Cross-Correlation (2019) by Rachel Draelos, which essentially says the same thing that I am saying here, but provides more details and examples.

Just as a short and quick answer to build of nbros:
The way CNNs are typically taught, they are taught using a correlation on the forward pass, rather than a convolution. In reality, Convolutional neural networks is a bit of a misleading name, but not entirely incorrect.
CNNs do in fact use convolutions every time they are trained and run. If a correlation is used on the forward pass, a convolution is used on the backward pass. The opposite is true if a convolution is used on the forward pass (which is equally valid as using a correlation). I couldn't seem to find this information anywhere, so had to learn it myself the hard way.
So to summarise, a typical CNN goes like this: Correlation forward, convolution backward.

I'd also like to say this a really good question and a pretty important one for anyone who wants to properly understand the inner workings of a CNN. It can be very confusing when you go to do an actual convolution and find it's not doing what you expect.

Maybe you should explain why if the forward pass performs a convolution (or cross-correlation) the backward pass performs a cross-correlation (and, respectively, convolution). It was also my intention (although I haven't yet done it) to provide links to libraries and explain how they implement CNNs (in particular, the convolutional layers). If you know how certain libraries implement the CNNs (e.g. TensorFlow, PyTorch, etc.), then feel free to add this info to your answer.

Also, I don't think that convolutional neural network is a misleading name. You could have called them "cross-correlation neural networks" (but that would be long and without any benefit) or, to be more precise, "convolutional or cross-correlation, down- or/and up-sampling, fully or not, with possible other layers, such as skip layers, neural networks", but that name would be quite ridiculous.

@nbro I still think it's slightly misleading in the sense that it's very easy to assume that a convolution is being performed when calculating an output, when in reality it's normally a correlation. Given that this is the core element that makes a CNN what it is, it can be a bit confusing. I know I personally found it confusing.

@nbro As for why for the relationship between correlation/convolution and how libraries implement CNNs, this I don't know. I figured out the correlation forward convolution backward by just mucking around and doing a few forward and backward passes by hand, and I haven't much looked into the implementation within libraries such as Tensorflow or Pytorch.


text:
Why can't we fully exploit the environment after the first episode in Q-learning?
During the first episode, it's 100% exploration, because all our Q values are 0. Suppose we have 1000 time steps, and it's terminated by meeting a reward. So, after the first episode, why can't we make it 100% exploitation? Why do we still need exploration?

You can't guarantee that you have taken every action from every state, even with  1000 time steps. There would be multiple outcomes:

The episode terminates, either by success or failure before the 1000
time steps. The agent is trying to maximise reward, if this is achieved by taking less than 1000 steps then it will do. It won't just walk around until it hits an arbitrary number of time steps.
If you have more states than time steps then you will
never be unable to visit all states and so you cannot guarantee that
the policy you followed was optimal (and hence would still want to explore). Even if you have #states = #time-steps then you will almost certaintly have more state-action pairs than timesteps. The only time this would be equal is if from every state there is only one action, which would be a trivial problem that wouldn't need RL to solve.

Ok this makes sense, it’s more like since we’re not sure it has taken every action possible from every state , we can’t rely on the Q values as they might not be correct, ok suppose we do 2000 episodes or more, can we now make it 100% exploitation

Our estimated Q values will asymptotically approach the optimal Q values (Q^* in most textbooks) as the number of episodes approaches infinite. The exact number of episodes would be a function of the number of state-action pairs however, so we can not say conclusively if 2000 episodes would be enough.

We can decay the exploration rate (epsilon in most books) as the number of episodes increases though so after many thousands of episodes the probability of exploration is  neglible.

Oh okay, so everything is basically on saying we’re not sure if 2000 episodes would be enough especially if the state space is large, but we’ve gotten better Q values on state action pairs so we can make y 90% exploitation and 10%exploration

Exactly but now think if you continue until 20,000 episodes, your Q values are becoming more accurate and you have explored more of the state space and know that certain state-action pairs are terrible so exploring them even more is pointless, so you reduce exploration to say 9% and so on.
If you have only been to a state a handful of times (especially if the resulting state is stochastic) you are unsure if it's a bad state - so you keep coming back. However, if you've been to a state 100 times and most of the time it sucked, you would be uninterested in going back.

On that makes sense, thank you, so if we’re certain that the Q values have converged and are accurate,can we make it 100% exploitation or is there still a need of exploring

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

authors: رمح العرب_Al Arab


text:
What is Reinforcement Learning?
What is the cleanest, easiest way to explain someone who is a non-STEM work colleague the concept of Reinforcement Learning? What are the main ideas behind Reinforcement Learning?

Humans are set loose in the world and go about their days doing stuff.
Whenever they do specific things, their brain sends them good signals (endorphins, joy, etc.) or bad signals (pain, sadness, etc.). They learn through these signals which things they should be doing and which things they shouldn't be doing.
Sometimes the signal is immediate and you know exactly what you're being "rewarded" or "punished" for (e.g. touch a hot stove and it hurts). Sometimes it takes a bit longer and there could be many possible reasons for the brain signal (even a combination of reasons), but you can hopefully figure out what caused it after it happens a few times (e.g. getting a stomach ache a few hours after eating a specific food).
That's basically what Reinforcement Learning is.

Good "in plain language" answer based on everyday human experience!

The famous book Reinforcement learning: an introduction by Sutton and Barto provides an intuitive description of reinforcement learning (that everyone is possibly able to understand).

Reinforcement learning is learning what to do — how to map situations to actions — so as to maximize a numerical reward signal. The learner is not told which actions to take, but instead must discover which actions yield the most reward by trying them.
In the most interesting and challenging cases, actions may affect not only the immediate reward but also the next situation and, through that, all subsequent rewards. These two characteristics — trial-and-error search and delayed reward — are the two most important distinguishing features of reinforcement learning.

In chapter 3, the book also introduces the agent-environment interface, which summarises the cyclic interaction between the agent (aka policy) and the environment (which represents the task/problem that you need to solve).

Every RL algorithm implements a cyclic interaction between an agent and an environment (as illustrated above), where, on each time step $t$, the agent takes an action $A_t$, the environment emits a reward $R_{t+1}$, and the agent and the environment move from state $S_t$ to the state $S_{t+1}$. This interaction continues until some termination criterion is met (for example, the agent dies). While this interaction occurs, the agent is supposed to reinforce the actions that lead to better outcomes (i.e. higher reward).

Reinforcement Learning can be explained by a few equations. However I assume that this is not what you are looking at since the explanation should be for someone having a non-STEM background. Not to say non-STEM folks are not able to understand math equations, but intuition comes easier with words and examples in my opinion.

Reinforcement Learning is about learning an optimal behavior by
repeatedly executing actions, observing the feedback from the
environment and adapting future actions based on that feedback.

Let's break down the last sentence by the concrete example of learning how to play chess:
Imagine you sit in front of a chess board, not knowing how to play. The optimal behavior you'd like to learn is what moves to execute in order to win the game. So you start learning the game by playing a few moves (actions) with some figures and observing what is happening on the board (environment) and identifying which moves bring you closer victory or give you a better position on the board (feedback). Therefore in future games you will prefer moves which gave you a positive outcome in previous games.
Admittedly this is a very slow process of learning if you don't have a teacher which helps you in the beginning and you would have to play a lot of games until your first victory. But this essentially how computers (and sometimes humans in some sense) learn to do certain things by Reinforcement Learning. Behaviors which lead to positive experiences are collected, memorized and thus reinforced.


text:
How to express $v_\pi(s)$ in terms of $q_\pi(s,a)$?

This is exercise 3.18 in Sutton and Barto's book.
The task is to express $v_\pi(s)$ using $q_\pi(s,a)$.
Looking at the diagram above, the value of $q_\pi(s,a)$ at $s$ for each $a \in A$ we take gives us the value function at $s$ after taking the action $a$ and then following the policy $\pi$.
This is probably wrong, but if
$$v_\pi(s) = E_\pi[G_t | S_t = s]$$
and
$$q_\pi(s) = E_\pi[G_t | S_t = s, A_t = a]$$
isn't then $v_\pi(s)$ just the expected action value function at $s$ over all actions $a$ that are given by the policy $\pi$, namely
$$v_\pi(s) = E_{a \sim \pi}[q_\pi(s,a) | S_t = s, A_t = a] = \sum_{a \in A}\pi(a|s) q_\pi(s,a)$$?

isn't then $v_\pi(s)$ just the expected action value function at $s$ over all actions $a$ that are given by the policy $\pi$, namely

$v_\pi(s) = E_{a \sim \pi}[q_\pi(s,a) | S_t = s, A_t = a] = \sum_{a \in A}\pi(a|s) q_\pi(s,a)$?

Yes this is 100% correct.
There is no "trick" to this or deeper thought needed. You have correctly isolated the key part of the MDP description that controls relationship between $v_{\pi}$ and $q_{\pi}$ in that direction.
Note that for a deterministic policy, with $\pi(s): \mathcal{S} \rightarrow \mathcal{A}$ then the relationship is
$$v_\pi(s) = q_\pi(s, \pi(s))$$
The related exercise in the book - expressing $q_{\pi}$ in terms of $v_{\pi}$ and the MDP characteristics - is more complex because it involves a time step.

It's worth noting that your expression for the deterministic policy is really just a shorter notation for the general case, given that, in the general case, for a deterministic policy, you will multiply $1$ by $q$ and put $a = \pi(s)$ in there for the only possible action, and have $0$ multiplied by $q$ for all other actions. So, the general formula still applies to the deterministic policy case. It's just a shorter notation, but they are mathematically equivalent/equal.


text:
Connection between the Bellman equation for the action value function $q_\pi(s,a)$ and expressing $q_\pi(s,a) = q_\pi(s, a,v_\pi(s'))$
When deriving the Bellman equation for $q_\pi(s,a)$, we have
$q_\pi(s,a) = E_\pi[G_t | S_t = s, A_t = a] = E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a]$ (1)
This is what is confusing me, at this point, for the Bellman equation for $q_\pi(s,a)$, we write $G_{t+1}$ as an expected value, conditioned on $s'$ and $a'$ of the action value function at $s'$, otherwise, there is no recursion with respect to $q_\pi(s,a)$, and therefore no Bellman equation. Namely,
$ = \sum_{a \in A} \pi(a |s) \sum_{s' \in S} \sum_{r \in R} p(s',r|s,a)(r + \gamma E_\pi[G_{t+1}|S_{t+1} = s', A_{t+1} = a'])$ (2)
which introduces the recursion of $q$,
$ = \sum_{a \in A} \pi(a |s) \sum_{s' \in S} \sum_{r \in R} p(s',r|s,a)(r + \gamma q_\pi(s',a'))$ (3)
which should be the Bellman equation for $q_\pi(s,a)$, right?
On the other hand, when connecting $q_\pi(s,a)$ with $v_\pi(s')$, in this answer, I believe this is done
$q_\pi(s,a) = \sum_{a\in A} \pi(a |s) \sum_{s' \in S}\sum_{r \in R} p(s',r|s,a)(r + \gamma E_{\pi}[G_{t+1} | S_{t+1} = s'])$ (4)
$q_\pi(s,a) = \sum_{a\in A} \pi(a |s) \sum_{s' \in S}\sum_{r \in R} p(s',r|s,a)(r + \gamma v_\pi(s'))$ (5)
Is the difference between using the expectation $E_{\pi}[G_{t+1} | S_{t+1} = s', A_{t+1} = a']$ in (3) and the expectation $E_{\pi}[G_{t+1} | S_{t+1} = s']$ in $(4)$ simply the difference in how we choose to express the expected return $G_{t+1}$ at $s'$ in the definition of $q_\pi(s,a)$?
In $3$, we express the total return at $s'$ using the action value function

leading to the recursion and the Bellman equation, and in $4$, the total return is expressed at $s'$ using the value function

leading to $q_\pi(s,a) = q_\pi(s,a,v_\pi(s'))$?

Your understanding of the Bellman equation is not quite right. The state-action value function is defined as the expected (discounted) returns when taking action $a$ in state $s$. Now, in your equation (2) you have conditioned on taking action $a'$ in the inner expectation - this is not what happens in the state-action value function, you do not condition on knowing $A_{t+1}$, it is chosen according to the policy $\pi$ as per the definition of a bellman equation.
If you want to see a 'recursion' between state action value functions, note that
$$v_\pi(s) = \sum_a \pi(a|s)q_\pi(s,a)\;,$$
Your equation (5) is incorrect -- you need to drop the outter sum over $a$ as we have conditioned on knowing $a$. I will drop the $\pi$ subscripts for ease on notation, and we can see a 'recursion' for state-action value functions as:
$$q(s,a) = \sum_{s',r}p(s',r|s,a)\left(r + \gamma \left[\sum_{a'} \pi(a'|s')q(s',a')\right]\right)\;.$$


text:
What is a convolutional neural network?
Given that this question has not yet been asked on this site, although similar questions have already been asked in the past (e.g. here or here), what is essentially a convolutional neural network (CNN)? Why are they heavily used in image recognition applications of machine learning?

I'm not sure this is the best place to ask as broad a question as this. However, I would recommend watching this lecture if you want some insight: Lecture 1 | Introduction to Convolutional Neural Networks for Visual Recognition by Standford.

I can't recommend this series of blog posts enough: A Beginner's Guide To Understanding Convolutional Neural Networks. They've helped me a lot to understand CNNs back in the day when I was studying them.

(Of course, similar questions have been asked in the past and there are many sites, papers, video lessons, online that explain how CNNs work, but I think it's still a good idea to have a reference answer that hopefully will give you the main ideas behind CNNs.)
A convolutional neural network (CNN) is a neural network that performs the convolution (or cross-correlation) operation typically followed by some downsampling (aka pooling) operations.
The convolution operation comes from the mathematical equivalent operation, which is an operation that takes as inputs two functions $f$ and $h$ and produces another function $g$ as output, which is often denoted as $f \circledast h = g$, where $\circledast$ is the convolution operation (or operator).
In image processing, the convolution is used to process images in multiples ways. For example, it is used to remove noise (e.g. the convolution of a noisy image with a Gaussian kernel produces a smoother image) or to compute derivatives of the image, which can then be used e.g. to detect edges or corners, which are usually the main features of an image. For example, the Harris corner detector makes use of the partial derivatives (in the $x$ and $y$ direction) of the image to find corners (or interest points) in the image.
In the context of CNNs, $f$ is the image (in the case of the first layer of the CNN) or a so-called feature map (in the case of hidden layers), $h$ is the kernel (aka filter) and $g$ is also a feature map. (In this answer, I explain these concepts, including how an image can be viewed as a function, more in detail, so I suggest that you read it).
Here's an illustrative example of how the convolution works.

where the $\color{blue}{\text{blue}}$ grid is the image, the $\color{gray}{\text{gray}}$ grid is the kernel and $\color{green}{\text{green}}$ grid is the feature map (i.e. the output of the convolution between the image and the kernel). The white squares are around the images represent the padding that is added around the image so that the convolution operation produces a feature map of a specific dimension.
Essentially, the convolution is a series of dot products between the kernel and different patches (or parts) of the image. The convolution can even be represented as matrix multiplication, so the name convolution shouldn't scare you anymore, if you are familiar with dot products and matrix multiplications.
As opposed to many operations in image processing where the kernels are typically fixed, in the context of CNNs, the kernels are learnable parameters, i.e. they change depending on the loss function, so they are supposed to represent functions that when convolved with their respective input functions are useful to extract meaningful information (i.e. features) to solve the task the CNN is being trained to solve. For this reason, the convolution is often thought of as an operation that extracts features from images. In fact, the output of the convolution, in the context of CNNs, is often called feature map. Moreover, a CNN is typically thought of as a data-driven feature extractor for the same reason.
There are many different variations of the standard convolution operation. For example, there are transposed convolutions, dilated convolutions, etc., which are used to solve slightly different problems. For example, the dilated convolution can be used to increase the receptive field of an element of a feature map (which is typically a desirable property for several reasons). There are also upsampling operations which are particularly useful in the context of image segmentation. These different convolutions and their arithmetic are explained very well in the paper A guide to convolution arithmetic for deep learning by Vincent Dumoulin and Francesco Visin. Here's also the associated Github repository that contains all the images in this paper that show how the convolution operations work (from which I also took the gif above).
To conclude, CNNs are very useful to process images and extract features from them because they use convolution operations (and downsampling and upsampling operations). They can be used for image (or object) classification, object detection (i.e. object localization with a bounding box + object classification), image segmentation (including semantic segmentation and instance segmentation), and possibly many other tasks where you need to learn a function that takes as input images and needs to extract information from those images to get someone high-level (but also low-level) output (e.g. the name of the object in the image), given some training data.


text:
Why is my Soft Actor-Critic's policy and value function losses not converging?
I'm trying to implement a soft actor-critic algorithm for financial data (stock prices), but I have trouble with losses: no matter what combination of hyper-parameters I enter, they are not converging, and basically it caused bad reward return as well. It sounds like the agent is not learning at all.
I already tried to tune some hyperparameters (learning rate for each network + number of hidden layers), but I always get similar results.
The two plots below represent the losses of my policy and one of the value functions during the last episode of training.

My question is, would it be related to the data itself (nature of data) or is it something related to the logic of the code?

I would say it is the nature of data. Generally speaking, you are trying to predict a random sequence, especially if you use the history data as an input and try to get the future value as an output.

Yes , I am trying another approach now by extracting more data from the temporal series ( historical prices ) by augmenting the data itself, it shows better results but still unstable.


text:
Why is the "reward to go" replaced by Q instead of V, when transitioning from PG to actor critic methods?
While transitioning from simple policy gradient to the actor-critic algorithm, most sources begin by replacing the "reward to go" with the state-action value function (see this slide 5).
I am not able to understand how this is mathematically justified. It seems intuitive to me that the "reward to go" when sampled through multiple trajectories should be estimated by the state-value function.
I feel this way since nowhere in the objective function formulation or resulting gradient expression do we tie down the first action after reaching a state. Alternatively, when we sample a bunch of trajectories, these trajectories might include different actions being taken from the state reached in timestep $t$.
So, why isn't the estimation/approximation for the "reward to go" the state value function, in which the expectation is also over all the actions that may be taken from that state as well?

When you say simple policy gradient, I assume you mean something like REINFORCE.
The main difference between actor-critic and REINFORCE-like algorithms is in how they estimate the reward to go:

in REINFORCE, you wait until a trajectory terminates to make any updates, and your estimator of the reward to go is the actual reward to go that was observed in the trajectory.
in actor critic algorithms, instead of using an entire trajectory to estimate a reward to go, you use the action value function (note that this way, you can compute updates at every time step). The reason why you use the action-value function is because at each transition, you have already committed to some action.

The benefit of the actor critic estimator is that it exhibits much less variance. REINFORCE estimators are Monte Carlo estimators, which are known to exhibit extremely high variance.
Now, the actor critic method in the slides you posted takes variance reduction one step further. Instead of estimating reward to go, it's estimating advantage -- that is, the difference between the current action value and your estimated state value. The state value function term doesn't depend on the action, so it doesn't affect the expected value of the policy gradient. However, it serves as a 'baseline', which helps reduce the variance of the reward to go estimator even further.

I see. Just to be clear, in REINFORCE is there a single update after a trajectory terminates or are there T updates, where for each timestep the gradient is approximated as grad log prob of policy at that timestep multiplied by reward to go from that timestep? Also then in the case of on policy actor critic, the advantage is Q-V is given as r + gammaV'. But then we also try to get V to converge to r+gammaV'. Could you please elaborate a bit more on the mathematical justification in using Q and V?

Firstly, in REINFORCE, there should be T updates after each trajectory as you suggested

For your second question, especially in the on-policy setting, you need to account for the action you took (V doesn't do this). Let's say you just observed the following transition, (s, a, r, s'). You want to use this transition to approximate the reward to go. To do this with the data you have, you're assuming the next state is s', but this is correlated with the fact that you took action a. That's why you need to use Q instead of, V, otherwise r + gamma * V(s') wouldn't necessarily be a valid estimate of the reward to go.

Okay. But I am still unable to understand why the advantage goes to zero once the critic gets better. We seem to set the target for V as r + gamma*V'. But the difference between the two is what we call Advantage

Right, because once the critic and policy have converged, the best actions are chosen by the policy, so the Q value should equal V (so advantage is 0).

"To do this with the data you have, you're assuming the next state is s', but this is correlated with the fact that you took action a. That's why you need to use Q instead of, V, otherwise r + gamma * V(s') wouldn't necessarily be a valid estimate of the reward to go." I understand V(s') is not the reward to go, but r + gamma * V(s') should be the reward to go on convergence? Is your point that we need to use Q(s,a) - V(s) (approximated as r + V(s')) rather than V(s') - V(s) when training the policy?


text:
What are the differences between SARSA and Q-learning?
From Sutton and Barto's book Reinforcement Learning (Adaptive Computation and Machine Learning series), are the following definitions:

To aid my learning of RL and gain an intuition, I'm focusing on the differences between some algorithms. I've selected Sarsa (on-policy TD control) for estimating Q ≈ q * and Q-learning (off-policy TD control) for estimating π ≈ π *.
For conciseness I'll refer to Sarsa (on-policy TD control) for estimating Q ≈ q * and Q-learning (off-policy TD control) for estimating π ≈ π * as Sarsa and Q-learning respectively.
Are my following assertions correct?
The primary differences are how the Q values are updated.
Sarsa Q value update:
$ Q ( S, A ) ← Q ( S, A ) + α [ R + \gamma Q ( S ′ , A ′ ) − Q ( S, A ) ] $
Q-learning Q value update:
$ Q ( S, A ) ← Q ( S, A ) + α [ R + \gamma \max_a Q ( S ′ , a ) − Q ( S, A ) ] $
Sarsa, in performing the td update subtracts the discounted Q value of the next state and action, S', A' from the Q value of the current state and action S, A.
Q-learning, on the other hand, takes the discounted difference between the max action value for the Q value of the next state and current action S', a.  Within the Q-learning episode loop the $a$ value is not updated, is an update made to $a$ during Q-learning?
Sarsa, unlike Q-learning, the current action is assigned to the next action at the end of each episode step. Q-learning does not assign the current action to the next action at the end of each episode step
Sarsa, unlike Q-learning, does not include the arg max as part of the update to Q value.
Sarsa and Q learning in choosing the initial action for each episode both use a "policy derived from Q", as an example, the epsilon greedy policy is given in the algorithm definition. But any policy could be used here instead of epsilon greedy?
Q learning does not utilise the next state-action pair in performing the td update, it just utilises the next state and current action, this is given in the algorithm definition as  $ Q ( S ′ , a ) $ what is $a$ in this case ?

here is an answer that shows when the two are (almost) the same.

Hi. Please, next time, ask one question per post. Here you're asking too many questions. When you have multiple questions, ask each of them in its separate post, even though they are related. This helps answerers to focus on a single problem, so it facilitates the life of everyone that reads the posts. Please, read our on-topic page to understand the ideal question we are looking for.

The main difference between the two is that Q-learning is an off policy algorithm. That is, we learn about an policy that is different to the one we choose to make actions. To see this, lets look at the update rule.
Q-Learning
$$Q(s,a) = Q(s,a) + \alpha (R_{t+1} + \gamma \max_aQ(s',a) - Q(s,a))$$
SARSA
$$Q(s,a) = Q(s,a) + \alpha (R_{t+1} + \gamma Q(s',a') - Q(s,a))$$
In SARSA we chose our $a'$ according to what our policy tells us to do when we are in state $s'$, so the policy we are learning about is also the policy that we choose to make our actions.
In Q-learning, we learn about the greedy policy whilst following some other policy, such as $\epsilon$-greedy. This is because when we transition into state $s'$ our TD-target becomes the maximum Q-value for whichever state we end up in, $s'$, where the max is taken over the actions.
Once we have actually updated our Q-function and we need to choose an action to take in $s'$, we do so from the policy we are using to generate our actions from -- thus we are learning about the greedy policy whilst following some other policy, hence off policy. In SARSA when we move into $s'$ our TD-target is chosen by the Q-value for the state we transition into and then the action we would choose based on our policy.

Within the Q-learning episode loop the $a$ value is not updated, is an update made to $a$ during Q-learning?

It will be, because the policy we use to choose our actions is ensured to explore sufficiently around all of the state-action pairs and so it is guaranteed to be encountered at some point.

Sarsa, unlike Q-learning, does not include the arg max as part of the update to Q value.

It is not an $\arg \max$, it is a $\max$. This is defined as
$$\max_x f(x) = \{f(x) | \forall y\; : f(y) \leq f(x) \}$$

Sarsa, unlike Q-learning, the current action is assigned to the next action at the end of each episode step. Q-learning does not assign the current action to the next action at the end of each episode step

Kind of - the action that you chose for your TD-target in SARSA becomes the next action that you consider in the next step of the episode. This is natural because essentially you are in state $s$, you take action $a$ and observe a new state $s'$, at which point you can use your policy to see which action you will take, call this $a'$, and then perform the SARSA update, and then execute that action in the environment.

Sarsa and Q learning in choosing the initial action for each episode both use a "policy derived from Q", as an example, the epsilon greedy policy is given in the algorithm definition. But any policy could be used here instead of epsilon greedy?

Yes, any policy can be used although you want to choose a policy that allows sufficient exploration of the state-space.

Q learning does not utilise the next state-action pair in performing
  the td update, it just utilises the next state and current action,
  this is given in the algorithm definition as $Q(S',a)$ what is $a$ in
  this case ?

in the algorithm it actually has $\max_a Q(S',a)$, which if you refer back to my earlier definition of what the $\max$ operator does, should answer this question.

"It is not an argmax, it is a max." thanks for pointing this out, I mixed up taking the arg max in the function epsilon greedy with the calculation of the updated Sarsa Q value .

When you say "In SARSA we chose our $a'$ according to what our policy tells us to do when we are in state $s'$, so the policy we are learning about is also the policy that we choose to make our actions.". It's important to note that this is definitely not clear only from the update rule of SARSA, because the update rule in SARSA doesn't tell you anything about how the actions $a$ and $a'$ are chosen from the corresponding states. You need to explicitly say it. In Q-learning, this is less of a problem, one can understand that the max "represents the target policy".

What you need to clarify here (which you try to do) is that the behavior policy, such as $\epsilon$-greedy, is used to pick up the tuples $(s, a)$ for which you update $Q(s, a)$ in both the Q-learning and SARSA. The difference is that in SARSA you also use $\epsilon$-greedy (or any other behaviour policy that you used before to select $a$ from $s$) to take action $a'$ from $s'$ (as opposed to just select the greedy action, as in Q-learning).

In my opinion, the best way to understand the difference between SARSA and Q-learning is really to read the pseudocode of both algorithms (actually provided in the question), and not just the update rules, which are not self-explanatory, as I am trying to say.


text:
What are the main ideas behind NER?

Named entity recognition (NER), also known as entity chunking/extraction, is a popular technique used in information extraction to identify and segment the named entities and classify or categorize them under various predefined classes.

Briefly, how does NER work? What are the main ideas behind it? And which algorithms are used to perform NER?

There are different algorithms, each with their advantages and disadvantages.

Gazetteers: these have lists of the entities to be recognised, eg list of countries, cities, people, companies, whatever is required. They typically use a fuzzy matching algorithm to capture cases where the entity is not written in exactly the same way as in the list. For example, USA or U.S.A., United States, United States of America, US of A, etc. Advantage: generally good precision, ie can identify known entities. Disadvantage: can only find known entities
Contextual Clues: here you have patterns that you find in the text, eg [PERSON], chairman of [COMPANY]. In this case, sentences like Jeff Bezos, chairman of Amazon, will match, even if you have never come across either Bezos or Amazon. Advantage: can find entities you didn't know about. Disadvantages: could end up with false positives, might be quite labour-intensive to come up with patterns; patterns depend on the domain (newspapers vs textbooks vs novels etc_
Structural description: this is basically a 'grammar' describing what your entities look like, eg (in some kind of pseudo-regex): title? [first_name|initial] [middle_name|initial]? surname would match "Mr J. R. Ewing" or "Bob Smith". Similar descriptions could match typical company names; you'd probably still need lists of possible surnames or firstnames. Advantages: some flexibility, and potentially good precision. Disadvantages: patterns need to be developed and maintained.

Ideally you would want to combine all three approaches for a hybrid one to get the advantages of recognising unknown entities while keeping excess false positives in check.
There might also be other machine-learning approaches, but I'm not too familiar with those. The main problem is that they are hard to fine-tune or work out why they do what they do.
UPDATE: A good starting point would be to use a gazetteer-based approach to annotate some training data, and use that to identify contextual patterns. You can then use that data to train a machine learning approach (see OmG's answer on CRF) to broaden the approach; and then you add newly recognised entities to your list.
Ideally you would want to have a gazette as your main database to avoid false positives, and use machine-learning or contextual patterns to just capture previously unseen entities.

One of the renowned learning algorithms for NER tagging is the conditional random field (CRF). As you can see in the provided link, sequence labeling algorithms such as RNN with LSTM can be used to named entity recognition as well. By the way, you can find an implementation of the CRF for NER tagging in this source.
Notice that, the method of providing training data can be helpful to pass the data into the standard libraries of CRF without any extra preprocessing. One of the standard methods is BIO method(B (Begin), I (Interior), and E (End)). You can find more about it in this post.

I think if you summarize the BIO method a bit, it can be a big lightbulb moment for understanding machine learning for language tasks. A tokenizer divides a text into a sequence of tokens, and the NER system labels each token as beginning, interior, or end of a name.

@Jetpack I've refered it through a link. There is a summaried version of the BIO.


text:
Is there any difference between reward and return in reinforcement learning?
I am reading Sutton and Barto's book on reinforcement learning. I thought that reward and return were the same things.
However, in Section 5.6 of the book, 3rd line, first paragraph, it is written:

Whereas in Chapter 2 we averaged rewards, in Monte Carlo methods we average returns.

What does it mean? Are rewards and returns different things?

Return refers to the total discounted reward, starting from the current timestep.

As the accepted answer states, the return at the current timestep is equal to the sum of discounted rewards from all future timesteps until the end of the episode. In Chapter 5 of Sutton and Barto, returns must be used to estimate the state-value and action-value functions because episode lengths are unrestricted and may be greater than one. In contrast, Chapter 2 deals with the very special case of multi-armed bandits in which episode lengths are always equal to one: The agent begins each episode in a fixed start state, takes an action, receives a reward, and then the episode terminates and the agent begins the next episode at the same start state. Therefore, a return is equivalent to a reward in Chapter 2 because all episodes have length one.


text:
What is the difference between one-shot learning, transfer learning and fine tuning?
Lately, there are lots of posts on one-shot learning. I tried to figure out what it is by reading some articles. To me, it looks like similar to transfer learning, in which we can use pre-trained model weights to create our own model. Fine-tuning also seems a similar concept to me.
Can anyone help me and explain the differences between all three of them?

They are all related terms.
From top to bottom:
One-shot learning aims to achieve results with one or very few examples. Imagine an image classification task. You may show an apple and a knife to a human and no further examples are needed to continue classifying. That would be the ideal outcome, but for algorithms.
In order to achieve one-shot learning (or close) we can rely on knowledge transfer, just like the human in the example would do (we are trained to be amazing at image processing, but here we would also exploit other knowledge like abstract reasoning abilities, and so on).
This brings us to transfer learning. Generally speaking, transfer learning is a machine learning paradigm where we train a model on one problem and then try to apply it to a different one (after some adjustments, as we'll see in a second).
In the example above, classifying apples and knives is not at all trivial. However, if we are given a neural network that already excels at image classification, with super-human results in over 1000 categories... perhaps it is easy to adapt this model to our specific apples vs knives situation.
This "adapting", those "adjustments", are essentially what we call fine-tuning. We could say that fine-tuning is the training required to adapt an already trained model to the new task. This is normally much less intensive than training from scratch, and many of the characteristics of the given model are retained.
Fine-tuning usually covers more steps. A typical pipeline in deep learning for computer vision would be this:

Get trained model (image classifier champion)
Note the head of our model does not match our needs (there's probably one output per category, and we only need two categories now!)
Swap the very last layer(s) of the model, so that the output matches our needs, but keeping the rest of the architecture and already trained parameters intact.
Train (fine-tune!) our model on images that are specific to our problem (only a few apples and knives in our silly example). We often only allow the last layers to learn at first, so they "catch up" with the rest of the model (in this case we talk about freezing and unfreezing and discriminative learning rates, but that's a bit beyond the question).

Note that some people may sometimes use fine-tuning as a synonym for transfer learning, so be careful about that!

The TensorFlow tutorial on transfer learning https://www.tensorflow.org/tutorials/images/transfer_learning also explains transfer learning quite well. It uses the term transfer learning to refer to the situation where you freeze all convolutional layers, added new dense trainable layers for the new classification task, then train the new architecture. It uses the term fine-tuning for the scenario where you train some of the convolution layers (typically, not all of them, but only the last ones) and the classifier (dense) layers.

It makes sense. I would argue that even if you train all layers (not only the last ones) we should talk about fine tuning, as learning is not starting from scratch and will normally not need nearly as many epochs as if you do start from scratch. But it's good to know the minor differences in use of these terms to avoid confusion!

I've just noticed that the Deep Learning book by Goodfellow et al. provides a chapter and several sections to this topic. You should provide read the relevant sections and make sure that your answer is consistent with the definitions in that widely cited book. If not, you should probably point out the differences at least.

I believe the definitions I have given cover most cases of general use. It will never be possible to make sure that all authors agree on the smallest details of these definitions, though. Since this is only a chapter and it may be interesting, I'll try to read it. If I notice anything that does not agree with my answer, I'll be sure to say why or provide the link at least. But this will not happen right away! Hopefully in the next few weeks I'll find the time. Thanks for the link!

When one makes a prompt to generate texts with GPT-3 with some examples, is it few short learning?

Hi Julien. I don't think it is. GPT-3 is trained with millions of documents to continue predicting words, which is what you do when you generate text, so I'd say that's normal inference, kind of (because you predict a long sequence, not just a few words). You have "zero-shot", where you present language models with problems like "Peter was born in bla bla bla bla bla bla" then prompt: "Where is Peter from?" and see what it writes. There are some very interesting results in that stuff.

My opinion on Julien's question is more nuanced now. I have definitely seen large language models used for few-shot (even zero-shot) learning. The example "Peter was born in bla bla bla bla bla bla" then prompt: "Where is Peter from?" should work! As for example using a prompt like "Germany, Berlin; France, Paris; Italy" and get "Rome" (and then more examples). Large language models are fascinating from this point of view.


text:
How do I recognise a bandit problem?
I'm having difficulty understanding the distinction between a bandit problem and a non-bandit problem.
An example of the bandit problem is an agent playing $n$ slot machines with the goal of discovering which slot machine is the most probable to return a reward. The agent learns to find the best strategy of playing and is allowed to pull the lever of one slot machine per time step. Each slot machine obeys a distinct probability of winning.
In my interpretation of this problem, there is no notion of state. The agent potentially can utilise the slot results to determine a state-action value? For example, if a slot machine pays when three apples are displayed, this is a higher state value than a state value where three apples are not displayed.
Why is there just one state in the formulation of this bandit problem? As there is only one action ("pulling the slot machine lever" ), then there is one action. The slot machine action is to pull the lever, which starts the game.
I am taking this a step further now. An RL agent purchases $n$ shares of an asset and its not observable if the purchase will influence the price. The next state is the price of the asset after the purchase of the shares. If $n$ is sufficiently large, then the price will be affected otherwise there is a minuscule if any effect on the share price. Depending on the number of shares purchased at each time step, it's either a bandit problem or not.
It is not a bandit problem if $n$ is large and the share price is affected? It is a bandit problem if $n$ is small and the share price is not affected?
Does it make sense to have a mix of a bandit and non-bandit states for a given RL problem? If so, then the approach to solving should be to consider the issue in its entirety as not being a bandit problem?

The bandit problem has one state, in which you are allowed to choose one lever among $n$ levers to pull.

Why is there just one state in the formulation of this bandit problem?

There is one state because the state does not change over time. Two notable consequences are that (i) pulling a lever does not change the internals of any slot machine (e.g. the distribution of rewards) and (ii) you are allowed to choose any lever without restrictions.  More generally, there is no sequential aspect of the state in this problem, as future states are unaffected by past states, actions, and rewards.

It is not a bandit problem if $n$ is large and the share price is affected?

Correct! If the share price is affected, then future states would be influenced by past actions. This is because the price per share is affected, which is one aspect of the state. Thus, you would need to plan a sequential strategy for your purchases.

It is a bandit problem if $n$ is small and the share price is not affected?

It all depends on the problem: as long as the state before buying shares remains completely the same after you purchase some shares, then yes. Share price being unaffected is only one of the requirements; another example requirement is that the maximum number of shares purchased is fixed at each time step, independent of the shares purchased previously.

Does it make sense to have a mix of a bandit and non-bandit states for a given RL problem? If so, then the approach to solving should be to consider the issue in its entirety as not being a bandit problem?

It makes sense to allow the share price to either be affected or unaffected based on $n$ in the same problem. Since some actions (large $n$) change the state, then there are multiple states, and actions sequentially affect the next state. Hence it is not a bandit problem as a whole, as you correctly stated.

The agent potentially can utilise the slot results to determine a state-action value?

Correct! I suggest reading Chapter 2 of Sutton and Barto to learn some fundamental algorithms of developing such strategies.
Nice work on analyzing this problem! To help solidify your understanding and formalize the arguments above, I suggest that you rewrite the variants of this problem as MDPs and determine which variants have multiple states (non-bandit) and which variants have a single state (bandit).


text:
How to fairly conduct a model performance with 5-fold cross validation after augmentation?
I have, say, a (balanced) data-set with 2k images for binary classification. What I have done is that

randomly divided the data-set into 5 folds;
copy-pasted all 5-fold data-set to have 5 exact copies of data-set (folder_1 to folder_5, all absolutely same data-set)
first fold in folder_1 is saved as test folder and remaining (fold_2, fold_3, fold_4, fold_5) are combined as one train folder
second fold in folder_2 is saved as test folder and remaining (namely, fold_1, fold_3, fold_4, fold_5) are combined as one train folder
third fold in folder_3 is saved as test folder and remaining (namely, fold_1, fold_2, fold_4, fold_5) are combined as one train folder.
similar process has been done on folder_4 and foder_5.

I hope, by now, you got the idea of how I distributed the data-set.
The reason I did so is as follows:
I have augmented the training data (train folder) in each of the folders and used test folders respectively to evaluate (ROC-AUC score). Now I kind of have 5 ROC-AUC scores which I evaluated using test folders. If I get the average value out of those 5 scores.
(Assuming the above cross-validation process is done right) If I were to perform some manual hyperparameter optimizations (like an optimizer, learning rate, batch size, dropout, activation) and perform the above cross-validation with data augmentation and find the best so-called "mean ROC-AUC", does it mean I successfully conducted hyper-parameter optimization?
FYI: I have no problem with computing power OR/AND time at all to loop through the hyper-parameters for this type of cross-validation with data augmentation

If you used your five $X_{test}$ sets multiple times (to measure the average AUC) to decide on the best set of hyperparameters (i.e. optimizer, learning rate, batch size, dropout, activation) then yes, you successfully conducted hyper-parameter optimization. However, the AUC you received for the best set of hyperparameters found (by manual tuning) is not representative of the real performance of your model.
This is because the act of using a test set to tune the parameters of your model degenerates it back to a "training" set, because the data is not being used to measure the performance of the model but to improve it instead (although on a different level of abstraction, i.e. not to directly influence the parameters of the model, such as neural network weights), making the resulting AUC an overly optimistic biased estimator of the real AUC (that it could have resulted in for an unseen test dataset).
That's why, if you care both about hyperparameter optimisation and being able to measure the "real" performance of your model, you need to split your dataset into three "buckets": training set $X_{train}$, validation st $X_{val}$ and test set $X_{test}$. $X_{test}$ should only be used once (after you've trained and tuned the model), and assuming it has enough samples and the samples are representative of the unseen data, you should get a good estimate of your model performance. $X_{val}$, on the other hand, is your validation set which you can reuse as many times as you want to find the optimal set of hyperparameters that result in the highest performance (i.e. AUC).

thanks for your answer, please provide some research references if possible


text:
How does policy evaluation work for continuous state space model-free approaches?
How does policy evaluation work for continuous state space model-free approaches?
Theoretically, a model-based approach for the discrete state and action space can be computed via dynamic programming and solving the Bellman equation.
Let's say you use a DQN to find another policy, how does model-free policy evaluation work then? I am thinking of Monte Carlo simulation, but that would require many many episodes.

Hi calveeen. Great question! To clarify - by policy evaluation, do you mean finding the true action-value function $q_{\pi}(s, a)$ of the current policy $\pi$ during training? Do you mean gauging the performance of the agent after constructing a final, trained policy? Or something else?

Hi @DeepQZero, thank you for replying. This question seems rather silly as policy evaluation for DQN can be simply done by observing average reward returns. In my case I was not able to work with running the policy in real life. Hence, the way I found to estimate the value of a learnt policy would be through off policy value evaluation, which is the importance sampling and it's variant.

Ok I see. For future reference, policy evaluation has a very specific definition in the context of reinforcement learning. It is the process of determining the true state-value $v_{\pi}(s)$ function or action-value function $q_{\pi}(s,a)$ under the current policy $\pi$ for every state and action. It seems that you are interested in gauging the agent's performance in the environment - that is equivalent to determining the state-value of only the start state(s) and separate from the policy evaluation problem. Both are good questions though.

How does policy evaluation work for continuous state space model-free approaches? ... Let's say you use a DQN to find another policy, how does model-free policy evaluation work then?

Policy evaluation is the process of determining state-value $v_{\pi}(s)$ or action-value $q_{\pi}(s, a)$ functions for the current policy. In the context of continuous state and action spaces without a model of the environment, policy evaluation must incorporate the agent's past experience instead of the model dynamics and will generally use a function approximator such as a neural network to estimate the action-values. Many popular approaches apply online updates to the function approximator; e.g., DQN combines Temporal-Difference targets and gradient descent to change the weights of the neural network and the resultant action-value estimates. Since

we gradually change the weights of the neural network at each gradient descent step,
the estimated action-values are solely dependent on the weights of the neural network,
the current policy is solely dependent on the estimated action-values (e.g. DQN takes the action with largest action-value),

then policy evaluation (updating the estimated action-value function to better match the true action-value function under the current policy) and policy improvement (greedily changing the current policy based on the new estimated action-value function) occur simultaneously at each gradient descent step. In DQN, a gradient descent step occurs at each time step.

I am thinking of Monte Carlo simulation, but that would require many many episodes.

After changing the action-value function, we may get a new policy. We assume that the action-value function of the old policy is similar to that of the new policy (although it is not guaranteed) because the change in weights of the neural network was small. Therefore, we use the estimated action-value function of the old policy as an initial estimate of the action-value function of the new policy. Specifically, we use the same neural network with the same weights as the initial approximation. This is computationally convenient, as it prevents the need to start the next policy evaluation update from scratch (e.g. with a Monte Carlo simulation over a painfully large number of episodes).

Theoretically, a model-based approach for the discrete state and action space can be computed via dynamic programming and solving the Bellman equation.

This same technique of using the estimated action-values of the old policy as the initial estimates for the action-values of the new policy is employed by some Dynamic Programming methods such as value iteration, albeit with known dynamics. Generalized Policy Iteration (GPI) is the notion of letting policy evaluation and policy iteration interact on whatever granularity deemed necessary for the problem at hand. A consequence of adopting the GPI paradigm is the choice to halt policy evaluation before convergence of the action-value function. Many deep reinforcement learning algorithms take this to an extreme and perform policy evaluation and policy improvement simultaneously during a single gradient descent step. For reference, Chapter 4 of Sutton and Barto provides a brief summary of these ideas.

I think OP has a fixed policy to evaluate (indirectly asked here by calling out evaluation only, and implied from other questions by same OP), so the parts of the answer referring to deriving policy from Q or GPI need to be adjusted - either separated out to make it clearer which part is which, or could even be removed entirely.

Hi @NeilSlater, and thank you very much for the good advice. It looks like I answered a different question than OP meant to ask - OP was wondering about agent performance (like you pointed out), while I provided an answer about policy eval in the context of GPI for continuous, model-free DRL. Since my answer was accepted, how should I proceed? Should I edit my response to provide more context for my particular answer? I'm very new here and just need some guidance.

If it has been accepted, probably better to leave as-is. The OP is clearly able to extract the information that they want from the answer, and there's a risk you remove something important to them if you make a major edit as I suggested.


text:
What is a fully convolution network?
I was surveying some literature related to Fully Convolutional Networks and came across the following phrase,

A fully convolutional network is achieved by replacing the parameter-rich fully connected layers in standard CNN architectures by convolutional layers with $1 \times 1$ kernels.

I have two questions.

What is meant by parameter-rich? Is it called parameter rich because the fully connected layers pass on parameters without any kind of "spatial" reduction?
Also, how do $1 \times 1$ kernels work? Doesn't $1 \times 1$ kernel simply mean that one is sliding a single pixel over the image? I am confused about this.

Fully convolution networks
A fully convolution network (FCN) is a neural network that only performs convolution (and subsampling or upsampling) operations. Equivalently, an FCN is a CNN without fully connected layers.
Convolution neural networks
The typical convolution neural network (CNN) is not fully convolutional because it often contains fully connected layers too (which do not perform the convolution operation), which are parameter-rich, in the sense that they have many parameters (compared to their equivalent convolution layers), although the fully connected layers can also be viewed as convolutions with kernels that cover the entire input regions, which is the main idea behind converting a CNN to an FCN. See this video by Andrew Ng that explains how to convert a fully connected layer to a convolutional layer.
An example of an FCN
An example of a fully convolutional network is the U-net (called in this way because of its U shape, which you can see from the illustration below), which is a famous network that is used for semantic segmentation, i.e. classify pixels of an image so that pixels that belong to the same class (e.g. a person) are associated with the same label (i.e. person), aka pixel-wise (or dense) classification.

Semantic segmentation
So, in semantic segmentation, you want to associate a label with each pixel (or small patch of pixels) of the input image. Here's a more suggestive illustration of a neural network that performs semantic segmentation.

Instance segmentation
There's also instance segmentation, where you also want to differentiate different instances of the same class (e.g. you want to distinguish two people in the same image by labeling them differently). An example of a neural network that is used for instance segmentation is mask R-CNN. The blog post Segmentation: U-Net, Mask R-CNN, and Medical Applications (2020) by Rachel Draelos describes these two problems and networks very well.
Here's an example of an image where instances of the same class (i.e. person) have been labeled differently (orange and blue).

Both semantic and instance segmentations are dense classification tasks (specifically, they fall into the category of image segmentation), that is, you want to classify each pixel or many small patches of pixels of an image.
$1 \times 1$ convolutions
In the U-net diagram above, you can see that there are only convolutions, copy and crop, max-pooling, and upsampling operations. There are no fully connected layers.
So, how do we associate a label to each pixel (or a small patch of pixels) of the input? How do we perform the classification of each pixel (or patch) without a final fully connected layer?
That's where the $1 \times 1$ convolution and upsampling operations are useful!
In the case of the U-net diagram above (specifically, the top-right part of the diagram, which is illustrated below for clarity), two $1 \times 1 \times 64$ kernels are applied to the input volume (not the images!) to produce two feature maps of size $388 \times 388$. They used two $1 \times 1$ kernels because there were two classes in their experiments (cell and not-cell). The mentioned blog post also gives you the intuition behind this, so you should read it.

If you have tried to analyze the U-net diagram carefully, you will notice that the output maps have different spatial (height and weight) dimensions than the input images, which have dimensions $572 \times 572 \times 1$.
That's fine because our general goal is to perform dense classification (i.e. classify patches of the image, where the patches can contain only one pixel), although I said that we would have performed pixel-wise classification, so maybe you were expecting the outputs to have the same exact spatial dimensions of the inputs. However, note that, in practice, you could also have the output maps to have the same spatial dimension as the inputs: you would just need to perform a different upsampling (deconvolution) operation.
How $1\times 1$ convolutions work?
A $1 \times 1$ convolution is just the typical 2d convolution but with a $1\times1$ kernel.
As you probably already know (and if you didn't know this, now you know it), if you have a $g \times g$ kernel that is applied to an input of size $h \times w \times d$, where $d$ is the depth of the input volume (which, for example, in the case of grayscale images, it is $1$), the kernel actually has the shape $g \times g \times d$, i.e. the third dimension of the kernel is equal to the third dimension of the input that it is applied to. This is always the case, except for 3d convolutions, but we are now talking about the typical 2d convolutions! See this answer for more info.
So, in the case we want to apply a $1\times 1$ convolution to an input of shape $388 \times 388 \times 64$, where $64$ is the depth of the input, then the actual $1\times 1$ kernels that we will need to use have shape  $1\times 1 \times 64$ (as I said above for the U-net). The way you reduce the depth of the input with $1\times 1$ is determined by the number of $1\times 1$ kernels that you want to use. This is exactly the same thing as for any 2d convolution operation with different kernels (e.g. $3 \times 3$).
In the case of the U-net, the spatial dimensions of the input are reduced in the same way that the spatial dimensions of any input to a CNN are reduced (i.e. 2d convolution followed by downsampling operations). The main difference (apart from not using fully connected layers) between the U-net and other CNNs is that the U-net performs upsampling operations, so it can be viewed as an encoder (left part) followed by a decoder (right part).

Thanks for your detailed reply, I really appreciate it!

Could Xception be considered an FCN? As it seems it can support any image size due to the final phase being global max pooling (Hence the final size before the Dense layers is independent of input size).

@Royi If it doesn't use the fully connected layers, but only convolutional and poolings, yes. I don't remember all the other details of the inception now.

It does use Fully Connected. But just after GlobalMaxPooling namely the size is only a function of the channels and not the 2D dimensions. In this case I abuse FCN as any net which supports arbitrary input size.

Search "1x1" on this page for another take on 1x1 convolutions:
https://cs231n.github.io/convolutional-networks/