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

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

I provided some details but the most important excerpt is from Stuart Russell and Peter Norvig's AIMA book:
A learning model that summarizes data with a set of parameters of fixed size (independent of the number of training examples) is called a parametric model. No matter how much data you throw at a parametric model, it won’t change its mind about how many parameters it needs.
For nonparametric models ask yourself a question: What is the number of parameters of the decision tree?
As the decision tree is an example of nonparametric model the number of parameters in a decision tree depends on the quantity of the data. The more data we have means more parameters.

What are the parameters of a decision tree?

Criterion such as Gini, and max deep are consider as hyper parameters, DT do not have weights and biases in the same way as neural networks or other linear models and DT are considered as non parametric models.

I didn't ask about hyperparameters, I asked about "parameters". The distinction between parametric and non-parametric models boils down to whether the number of parameters varies with data. So, in a decision tree what qualifies as a parameter? If we don't have a definition of what is a "parameter" in a decision tree, then statements like "the number of parameters in a decision tree vary/grow with data" are meaningless. The parameters of a decision tree could be the regions of the tree and these indeed can vary with different amount of data.

So you would like to say that  DT is a parametric model.  LOL.

Apologize, I realized that my second comment does not make sense and I will remove it. Nevertheless, is there any definition of what a parameter, not hyperparameter is in a decision tree?


text:
How do weak learners become strong in boosting?
Boosting refers to a family of algorithms which converts weak learners to strong learners. How does it happen?

No weak learner becomes strong; it is the ensemble of the weak learners that turns out to be strong.

As @desertnaut mentioned in the comment

No weak learner becomes strong; it is the ensemble of the weak learners that turns out to be strong

Boosting is an ensemble method that integrates multiple models(called as weak learners) to produce a supermodel (Strong learner).

Basically boosting is to train weak learners sequentially,  each trying to correct its predecessor. For boosting, we need to specify a weak model (e.g. regression, shallow decision trees, etc.), and then we try to improve each weak learner to learn something from the data.
AdaBoost is a boosting algorithm where a decision tree with a single split is used as a weak learner. Also, we have gradient boosting and XG boosting.

You say "and then improves it.", who improves what?

we try to improve each weak learner to learn something from the data

In Boosting, we improve the overall metrics of the model by sequentially building weak models and then building upon the weak metrics of previous models.
We start out by applying basic non-specific algorithms to the problem, which returns some weak prediction functions by taking arbitrary solutions (like sparse weights or assigning equal weights/attention). We improve upon this in the following predictions by adjusting weights to those having a higher error rate. After going through many iterations, we combine it to create a single Strong Prediction Function which has better metrics.

Some popular Boosting Algorithms :

AdaBoost
Gradient Tree Boosting
XGBoost

What are "weak prediction functions" and "Strong Prediction Function"? These terms are ambiguous because you did not define what you mean by "weak" and "strong" and you also have not defined "prediction function". Also, what do you mean by "weak metrics"? Do you mean metrics according to which the model performs bad?

You take a bunch of weak learners, each of them trained on a subset of the data.
You then just get all of them to make a prediction, and you learn how much you can trust each one, resulting in a weighted vote or other type of combination of the individual predictions.

source: Stack Exchange

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

sort: votes


text:
Why is the learning rate generally beneath 1?
In all examples I've ever seen, the learning rate of an optimisation method is always less than $1$. However, I've never found an explanation as to why this is. In addition to that, there are some cases where having a learning rate bigger than 1 is beneficial, such as in the case of super-convergence.
Why is the learning rate generally less than 1? Specifically, when performing an update on a parameter, why is the gradient generally multiplied by a factor less than 1 (absolutely)?

If the learning rate is greater than or equal to $1$ the Robbins-Monro condition
$$\sum _{{t=0}}^{{\infty }}a_{t}^{2}<\infty\label{1}\tag{1},$$
where $a_t$ is the learning rate at iteration $t$, does not hold (given that a number bigger than $1$ squared becomes a bigger number), so stochastic gradient descent is not generally guaranteed to converge to a minimum [1] (although the condition \ref{1} is a sum from $t=0$ to $t=\infty$, but, of course, we only iterate for a finite number of iterations). Moreover, note that, if the learning rate is bigger than $1$, you are essentially giving more weight to the gradient of the loss function than to the current value of the parameters (you give weight $1$ to the parameters).
This is probably the main reason why the learning rate is usually in the range $(0, 1)$ and there are methods to decay the learning rate, which can be beneficial (and there are several explanations of why this is the case [2]).

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


text:
How does a neural network that has been trained keep learning while in a real world scenario
Say I trained a Neural Network (not RNN or CNN) to classify a particular data set.
So I train using a specific data set & then I test using another and get an accuracy of 95% which is good enough.
I then deploy this model in a production level environment where it will then be processing real world data.
My question is, will this trained NN be constantly learning even in a production scenario? I can't figure out how it will because say it processes a dataset such as this:
[ [1,2,3] ] and gets an output of [ 0, 0.999, 0 ]
In a training scenario it will compare the predicted output to the actual output and back propagate but in a real world scenario it will not know the actual value.
So how does a trained model learn in a real world scenario?
I am still very much a beginner in this field and I am not sure if the technology used is going to affect the answer to this question, but I am hoping to use Eclipse Deeplearning4J to create a NN. That being said the answer does not need to be restricted to this technology in particular as I am hoping more for the theory behind it and how it works.

You are right. If you don't continuously train the neural network after you have deployed it, there is no way it can continuously learn or be updated with more information. You need to program the neural network to learn even after it has been deployed. There is no such thing as a neural network that decides what it does without a human deciding first what it needs to do: this is a very common misconception (probably caused by the media and science fiction movies). It's also true that you need to label your data if you intend to train the neural network in a supervised fashion, but there are other ways to train neural networks (e.g. by reinforcement learning), depending also on the problem you want to solve.
If you want to develop neural networks that can learn continually, you probably want to look into continual learning techniques for neural networks. Another term that you may be looking for is online machine learning.

Thanks for the answer and the edit! "incremental learning" and "continuous learning" learning were the terms I was looking for. Saved the linked research paper for a later day as it looked slightly intimidating at present.

@user3536523 No problem. Yes, I suggest that you first get familiar with the basic concepts of machine learning and neural networks before reading that paper, although it's not a very difficult paper to read, but you would not understand many concepts if you are not familiar with the basics.


text:
Is there a connection between the bias term in a linear regression model and the bias that can lead to under-fitting?
Here is a linear regression model
$$y = mx + b,$$
where $b$ is known as $y$-intercept, but also known as the bias [1], $m$ is the slope, and $x$ is the feature vector.
As I understood, in machine learning, there is also the bias that can cause the model to underfit.
So, is there a connection between the bias term $b$ in a linear regression model and the bias that can lead to under-fitting in machine learning?

In machine learning, the term bias can refer to at least 2 related concepts

A (learnable) parameter of a model, such as a linear regression model, which allows you to learn a shifted function. For example, in the case of a linear regression model $y = f(x) = mx + b$, the bias $b$ allows you to shift the straight-line up an down: without the bias, you would only be able to control the slope $m$ of the straight-line. Similarly, in a neural network, you can have a neuron that performs a linear combination of the inputs, then it uses a bias term to shift the straight-line, and you could also use the bias after having applied the activation function, but this will have a different effect.

Anything that guides the learning algorithm (e.g. gradient descent with back-propagation) towards a specific set of solutions. For example, if you use regularization, you are biasing the learning algorithm to choose, typically, smoother or simpler functions. The bias term in the linear regression model is also a way of biasing the learning algorithm: you assume that the straight-line function does not necessarily go through zero, and this assumption affects the type of functions that you can learn (and this is why these two concepts of bias are related!). So, there are many ways of biasing a learning algorithm.

The bias does not always lead you to the best solutions and can actually lead to the wrong solutions, but it is often useful in many ways, for example, it can speed up learning, as you restrict the number of functions that can be learned and searched. The bias (as described in point 2) is often discussed in the context of the bias-variance trade-off, and both the bias and the variance are related to the concepts of generalization, under-fitting, and over-fitting. The linked Wikipedia article explains these concepts quite well and provides an example of how the bias and variance are decomposed, so you should probably read that article for more details.


text:
How can we estimate the transition model and reward function?
In reinforcement learning (RL), there are model-based and model-free algorithms. In short, model-based algorithms use a transition model $p(s' \mid s, a)$ and the reward function $r(s, a)$, even though they do not necessarily compute (or estimate) them. On the other hand, model-free algorithms do not use such a transition model or reward function, but they directly estimate a value function or policy by interacting with the environment, which allows the agent to infer the dynamics of the environment.
Given that model-based RL algorithms do not necessarily estimate or compute the transition model or reward function, in the case these are unknown, how can they be computed or estimated (so that they can be used by the model-based algorithms)? In general, what are examples of algorithms that can be used to estimate the transition model and reward function of the environment (represented as either an MDP, POMDP, etc.)?

A similar question had already been asked here, but it focuses on the case where the transition matrix can be very big (in my question above, I don't put this restriction). Here is another related question, but specific to POMDPs.

Given that model-based RL algorithms do not necessarily estimate or compute the transition model or reward function, in the case these are unknown, how can they be computed or estimated (so that they can be used by the model-based algorithms)?

A generally reliable approach to creating learned models from interacting with the environment, then using those models internally for planning or explicitly model-based learning, is still something of a holy grail in RL. An agent that can do this across multiple domains might be considered a significant step in autonomous AI. Sutton & Barto write in Reinforcement Learning: An Introduction (Chapter 17.5):

More work is needed before planning with learned models can be effective. For example,the learning of the model needs to be selective because the scope of a model strongly affects planning efficiency. If a model focuses on the key consequences of the most important options, then planning can be efficient and rapid, but if a model includes details of unimportant consequences of options that are unlikely to be selected, then planning may be almost useless. Environment models should be constructed judiciously with regard to both their states and dynamics with the goal of optimizing the planning process. The various parts of the model should be continually monitored as to the degree to which they contribute to, or detract from, planning efficiency. The field has not
yet addressed this complex of issues or designed model-learning methods that take into account their implications.

[Emphasis mine]
This was written in 2019, so as far as I know still stands as a summary of state-of-the-art. There is ongoing research into this - for instance, the paper Model-Based Reinforcement Learning via Meta-Policy Optimization considers using multiple learned models to assess reliability. I have seen a similar recent paper which also assesses the reliability of the learned model and chooses how much it should trust it over a simpler model-free prediction, but cannot recall the name or find it currently.
One very simple form of a learned model is to memorise transitions that have been experienced already. This is functionally very similar to the experience replay table used in DQN. The classic RL algorithm for this kind of model is Dyna-Q, where the data stored about known transitions is used to perform background planning. In its simplest form, the algorithm is almost indistinguishable from experience replay in DQN. However, this memorised set of transition records is a learned model, and is used as such in Dyna-Q.
The basic Dyna-Q approach creates a tabular model. It does not generalise to predicting outcomes from previously unseen state, action pairs. However, this is relatively easy to fix - simply feed experience so far as training data into a function approximator and you can create a learned model of the environment that attempts to generalise to new states. This idea has been around for a long time. Unfortunately, it has problems - planning accuracy is strongly influenced by the accuracy of the model. This applies for both background planning and looking forward from the current state. Approximate models like this to date typically perform worse than simple replay-based approaches.
This general approach - learn the model statistically from observations - can be refined and may work well if there is any decent prior knowledge that restricts the model. For example, if you want to model a physical system that is influenced by current air pressure and local gravity, you could have free parameters for those unknowns starting with some standardised guesses, and then refine the model of dynamics when observations are made, with strong constraints about the form it will take.
Similarly, in games of chance with hidden state, you may be able to model the unknowns within a broader well-understood model, and use e.g. Bayesian inference to add constraints and best guesses. This is typically what you would do for a POMDP with a "belief state".
Both of the domain-specific approaches in the last two paragraphs can be made to work better than model-free algorithms alone, but they require deep understanding/analysis of the problem being solved by the researcher to set up a parametric model that is both flexible enough to match the environment being learned, but also constrained enough that it cannot become too inaccurate.

I think it's not strictly correct to say this "this memorised set of transition records is a learned model" or to say that the experience replay buffer is a model. I think it's more accurate to say that it "induces" a model, i.e. you can build a model from the dataset/buffer or stored transitions. For example, you might have more evidence for more tuples than others, so you may be more uncertain for certain tuples/transitions than others. So, the dataset alone doesn't define the model. You still need to define the probabilities (will you just use the empirical frequencies?) or how to sample.

@nbro Yes I see what you mean. What I was going for was more like this: kNN with k=1 is a model, so what is missing from the experience replay table to make it an explicit model like kNN is only lookup by $s,a$. I'm not sure whether "induces a model" is how I would phrase that.

The original question about both the estimation of the transition model, often denoted as $T$, and the reward function, sometimes denoted as $R$, arose because I was thinking about the probability distribution often denoted as
$$\color{red}{p}\left(s^{\prime}, r \mid s, a\right) \doteq \operatorname{Pr}\left\{S_{t}=s^{\prime}, R_{t}=r \mid S_{t-1}=s, A_{t-1}=a\right\},$$
which is often called the model (and Sutton & Barto also call it the dynamics function, given that it defines the dynamics of the environment), which incorporates both the transition model and reward function. In fact, both the transition probability distribution (of the next state $s'$ given $s$ and $a$) and different types of reward functions can be written as a function of this dynamics function. More precisely, we have the following results

$\color{orange}{p}\left(s^{\prime} \mid s, a\right) \doteq \operatorname{Pr}\left\{S_{t}=s^{\prime} \mid S_{t-1}=s, A_{t-1}=a\right\}=\sum_{r \in \mathcal{R}} \color{red}{p}\left(s^{\prime}, r \mid s, a\right)$

$\color{blue}{r}(s, a) \doteq \mathbb{E}\left[R_{t} \mid S_{t-1}=s, A_{t-1}=a\right]=\sum_{r \in \mathcal{R}} r \sum_{s^{\prime} \in \mathcal{S}} \color{red}{p}\left(s^{\prime}, r \mid s, a\right)$

$\color{cyan}{r}\left(s, a, s^{\prime}\right) \doteq \mathbb{E}\left[R_{t} \mid S_{t-1}=s, A_{t-1}=a, S_{t}=s^{\prime}\right]=\sum_{r \in \mathcal{R}} r \frac{\color{red}{p}\left(s^{\prime}, r \mid s, a\right)}{\color{orange}{p}\left(s^{\prime} \mid s, a\right)}$

Given that this answer already (partially) answers the question

How can we estimate the transition model?

but not the question

How can we estimate the reward function?

I will provide here an answer to this second question.
We can use inverse reinforcement learning techniques, i.e. techniques that estimate the reward function given trajectories of the form $$\tau = (s_1, a_1, r_1, s_{2}, \dots, s_{T-1}, a_{T-1}, r_{T-1}, s_{T}),$$ which are often assumed to have been generated by some optimal policy $\pi^*$, to estimate the reward function. An example of such a technique is AIRL.


text:
How to determine the number of hidden layers and units of a deep auto-encoder?
I am using a deep autoencoder for my problem. However, the way I choose the number of hidden layers and hidden units in a hidden layer is still based on my feeling.
The size of the model that indicates the number of hidden layers and units should not be too much or too few for the model can capture useful features from the dataset.
So, how do I choose the right size of the deep autoencoder model is enough to good?

You are right!
1- the number of hidden layers shouldn't be too high! Because of the gradient descent when the number of layers is too large, the gradient effect on the first layers become too small! This is why the Resnet model was introduced.
2- the number of hidden layers shouldn't be too small to extracts good features. It's proved that in CNN networks the first layers extract very simple elements like lines and curves but last layers extracts more complex features.
3- number of hidden units is a hyper-parameters and usually you should find it by testing or based on your background knowledge.
But what can you do at all?
As you can tests different parameters and compare their results there is some other options! One option is grid search you can check this tutorial https://towardsdatascience.com/grid-search-for-model-tuning-3319b259367e


text:
What are trap functions in genetic algorithms?
What are trap functions in genetic algorithms? Suppose you ran a GA with a trap function and examined the population midway through the run. Can someone explain what you would expect the population to look like?

Traps are functions that are designed to have a very obvious gradient that leads to basically the second-best solution, with the best one being very far removed from that, often the complement of the second-best.
Take the 1-max problem. You have N bits, and the fitness of each individual is just the number of 1 bits in the string. If you run a GA on that, you'd expect to see an initial random distribution of 1s and 0s across the population fairly quickly start to converge to strings of all 1s. Now let's add one more clause to the fitness criteria. Instead of f(0)=0, let f(0)=N+1. This gives you a trap function. The "trap" is the solution of all 1s. Everything in the search space points to this being the best solution, but it's actually maximally far away from the best solution.
In terms of dyanmics, now the optimal solution is the string of all 0s. But unless you happen to very quickly stumble across that string, you likely never will. That is, there's some slight chance that your initial population included 00001111 and 11110000 and you crossed them over in the middle and got the optimum. Or maybe you had 00001000 and you got lucky and mutated that one bit to a zero. But if you don't do that immediately, you're screwed, because the algorithm is going to pretty relentless drive all the zero bits out of the population. No matter what it does, flipping a 0 to a 1 is always better unless it would otherwise lead to the single string of all 0s, so there's constant pressure to find more and more 1 bits. A few generations in, you might have 11110110, but you're never realistically going to randomly mutate all six of those 1s to 0s. And you have to get it all in one shot. Any subset of fewer than six of those bits being flipped will have worse fitness than you started with, and be selected against.


text:
What is the meaning of "exploration" in reinforcement and supervised learning?
While exploration is an integral part of reinforcement learning (RL), it does not pertain to supervised learning (SL) since the latter is already provided with the data set from the start.
That said, can't hyperparameter optimization (HO) in SL be considered as exploration? The more I think about this the more I'm confused as to what exploration really means. If it means exploring the environment in RL and exploring the model configurations via HO in SL, isn't its end goal "mathematically" identical in both cases?

In reinforcement learning, exploration has a specific meaning, which is in contrast with the meaning of exploitation, hence the so-called exploration-exploitation dilemma (or trade-off). You explore when you decide to visit states that you have not yet visited or to take actions you have not yet taken. On the other hand, you exploit when you decide to take actions that you have already taken and you know how much reward you can get. It's like in life: maybe you like cereals $A$, but you never tried cereals $B$, which could be tastier. What are you going to do: continue to eat cereals $A$ (exploitation) or maybe try once $B$ (exploration)? Maybe cereals $B$ are as tasty as $A$, but, in the long run, $B$ are healthier than $A$.
More concretely, recall that, in RL, the goal is to collect as much reward as you can. Let's suppose that you are in state $s$ and, in the past, when you were in that state $s$, you had already taken the action $a_1$, but not the other actions $a_2, a_3$ and $a_4$. The last time you took action $a_1$, you received a reward of $1$, which is a good thing, but what if you take action $a_2, a_3$ or $a_4$? Maybe you will get a higher reward, for example, $10$, which is better. So, you need to decide whether to choose again action $a_1$ (i.e. whether to exploit your current knowledge) or try another action that may lead to a higher (or smaller) reward (i.e. you explore the environment). The problem with exploration is that you don't know what's going to happen, i.e. you are risking if you already get a nice amount of reward if you take an action already taken, but sometimes exploration is the best thing to do, given that maybe the actions you have taken so far have not led to any good reward.
In hyper-parameter optimization, you do not need to collect any reward, unless you formulate your problem as a reinforcement learning problem (which is possible). The goal is to find the best set of hyper-parameters (e.g. the number of layers and neurons in each layer of the neural network) that performs well, typically, on the validation dataset. Once you have found a set of hyper-parameters, you usually do not talk about exploiting it, in the sense that you will not continually receive any type of reward if you use that set of hyper-parameters, unless you conceptually decide that this is the case, i.e., whenever you use that set of hyper-parameters you are exploiting that model to get good performance on the test sets that you have. You could also say that when you are searching for new sets of hyper-parameters you are exploring the search space, but, again, the distinction between exploitation and exploitation, in this case, is typically not made, but you can well talk about it.
It makes sense to talk about the exploitation-exploration trade-off when there is stochasticity involved, but in the case of the hyper-parameter optimization there may not be such a stochasticity, but it's usually a deterministic search, which you can, if you like, call exploration.

Your last paragraph lies at the crux of my problem, it seems. Why would exploration in RL be any less deterministic than HO for SL? And vice-versa: After all, there is such a thing as stochastic gradient descent which also could be used in the context of HO. From your answer it seems that the difference in the is just in the semantics, but is there a more fundamental one?

@Tfovid There usually no stochasticity in hyper-parameter optimization. It's just like this: try this set $A$, $B$, and $C$ of hyper-parameters, then choose the best one among them to test on the test dataset, and that's it (end of the story). Stochastic gradient descent is called stochastic for another reason: it's because you are using "noisy" approximations of the "true gradient". In a way, there's stochasticity in SGD, but it's conceptually different than in RL.

In RL, you need to think of actions, rewards and environments, and think there's an agent that goes around in the environment taking actions and receiving rewards and the agent needs to decide which actions to take. The exploration-exploitation dilemma is one of the most important concepts of RL (if not the most important) because all RL algorithms need to face it. You really need to understand that exploration and exploitation have specific meanings in RL (which I describe in my answer above), but may not have specific meanings in other machine learning techniques.

In RL, the environment is stochastic, i.e. in the sense that it's governed by probabilities. Maybe that will answer your question of why RL is "more stochastic". For example, if you take action $a$ in the state $s$, you may not always end up in the same next state or receive always the same reward. Have a look at the Markov decision process, which is the mathematical framework that underlies all RL algorithms. You will see that the MDP is composed of probabilities.

If you want to show a mathematical difference between "exploration" in HO and RL, may be worth explaining the concept of regret. Although there is still an analogy (how much time/effort spent searching in HO), the definition in RL does not carry over to HO.

Just to add up to the answer above.
In fact if the reward that you get are not stochastic in RL then you simply take a step into your parameter space that guaranteed you the best reward so far (after the evaluation of all other states). So for example if action up is the best one so far, nothing motivates you to try an other one.
When you are doing naïve HO it could be seen as an exploration of the space. The environment is not stochastic but the reward (loss decrease) that you will get are not known by the agent beforehand. That's enough to make the exploration step mandatory. So let's say the combination (up, up, down) has got you the best loss so far, you need to actually try other combinations to know if they are the best above all others. In that sense you are exploring too.
So when are you not exploring ? If the next step in your HO is given by an optimization step, let's say by a function $f$, then you are not exploring anymore. You are progressing toward the objective given by $f$.
Thus, you have to make sure that $f$ correctly gives you the best combination of parameters - mathematically $f$ is converging to a global optimum.
So grid search could be viewed as exploration, Bayesian optimization HO not that much.

This "if action up is the best one so far, nothing motivates you to try an other one." is wrong. If you haven't tried all actions, how can you know that action "up" is the best among all other actions even if it's the best so far?

When I wrote "so far" I meant when you have tried actually performed an estimation of the value of all actions. That's why I state that in that case you will always repeat that ''up'' action and be guaranteed that you are executing the best action so far because the environement is not stochastic.

Your answer can potentially be useful, but there are some parts that could be written more clearly. For example, "So when you are not ?", when you are not what? Maybe you should also explain why in BO you don't just explore.


text:
How is BERT different from the original transformer architecture?
As far as I can tell, BERT is a type of Transformer architecture. What I do not understand is:

How is Bert different from the original transformer architecture?

What tasks are better suited for BERT, and what tasks are better suited for the original architecture?

What is a transformer?
The original transformer, proposed in the paper Attention is all you need (2017), is an encoder-decoder-based neural network that is mainly characterized by the use of the so-called attention (i.e. a mechanism that determines the importance of words to other words in a sentence or which words are more likely to come together) and the non-use of recurrent connections (or recurrent neural networks) to solve tasks that involve sequences (or sentences), even though RNN-based systems were becoming the standard practice to solve natural language processing (NLP) or understanding (NLU) tasks. Hence the name of the paper "Attention is all you need", i.e. you only need attention and you don't need recurrent connections to solve NLP tasks.
Both the encoder-decoder architecture and the attention mechanism are not novel proposals. In fact, previous neural network architectures to solve many NLP tasks, such as machine translation, had already used these mechanisms (for example, take a look at this paper).  The novelty of the transformer and this cited paper is that it shows that we can simply use attention to solve tasks that involve sequences (such as machine translation) and we do not need recurrent connections, which is an advantage, given that recurrent connections can hinder the parallelization of the training process.
The original transformer architecture is depicted in figure 1 of the cited paper. Both the encoder and decoder are composed of

attention modules
feed-forward (or fully connected) layers
residual (or skip) connections
normalization layers
dropout
label smoothing
embedding layers
positional encoding

The decoder part is also composed of a linear layer followed by a softmax to solve the specific NLP task (for example, predict the next word in a sentence).
What is BERT?
BERT stands for Bidirectional Encoder Representations from
Transformers, so, as the name suggests, it is a way of learning representations of a language that uses a transformer, specifically, the encoder part of the transformer.
What is the difference between the transformer and BERT?

BERT is a language model, i.e. it represents the statistical relationships of the words in a language, i.e. which words are more likely to come after another word and stuff like that. Hence the part Representations in its name, Bidirectional Encoder Representations from
Transformers.
BERT can be trained in an unsupervised way for representation learning, and then we can fine-tune BERT on the so-called downstream tasks in a supervised fashion (i.e. transfer learning). There are pre-trained versions of BERT that can be already fine-tuned (e.g. this one) and used to solve your specific supervised learning task. You can play with this TensorFlow tutorial to use a pre-trained BERT model.
On the other hand, the original transformer was not originally conceived to be a language model, but to solve sequence transduction tasks (i.e. converting one sequence to another, such as machine translation) without recurrent connections (or convolutions) but only attention.

BERT is only an encoder, while the original transformer is composed of an encoder and decoder. Given that BERT uses an encoder that is very similar to the original encoder of the transformer, we can say that BERT is a transformer-based model. So, BERT does not use recurrent connections, but only attention and feed-forward layers. There are other transformer-based neural networks that use only the decoder part of the transformer, for example, the GPT model.

BERT uses different hyper-parameters than the ones used in Attention is all you need to achieve the best performance. For example, it uses 12 and 16 "attention heads" (please, read the transformer paper to know more about these "attention heads") rather than 8 (although in the original transformer paper the authors experimented with a different number of heads).

BERT also uses segment embeddings, while the original transformer only uses word embeddings and positional encodings.

There are probably other small differences that I missed, but, after having read the paper Attention is all you need and quickly read some parts of the BERT paper, these seem to be the main differences.
When to use BERT and the transformer?
Although I never used them, I would say that you want to use BERT whenever you want to solve an NLP task in a supervised fashion, but your labeled training dataset is not big enough to achieve good performance. In that case, you start with a pre-trained BERT model, then fine-tune it with your small labeled dataset. You probably need to add specific layers to BERT to solve your task.

Well explained!

You said it was supposed to solve seq2seq tasks without convolution, but it does use convolution doesn't it? Right after the attention mechanism dense layers are convolved across the attention outputs + positional embeddings, albeit not with the traditional conventions of CNNs (e.g. there is no flexible stride).

@profPlum There are no convolutions in the transformer. The original paper even says "Since our model contains no recurrence and no convolution...".

@nbro There are convolutions, though the authors call them "Point-wise feed-forward networks" and they discard the traditional conventions of CNNs (hence your quote).
BUT the original paper also said this:
"Another way of describing this [point-wise feedforward network] is as two convolutions with kernel size 1."

@profPlum Thanks for sharing this info. As you can imagine, I gave this answer already a long time ago, so I forgot the details of the paper. However, note that you could also view a "normal" fully connected layer as a convolution layer with a kernel that has the same dimensions as the input. See also this.

@nbro Perhaps, but IIRC the point-wise FFNs 'slide' across the time-dimension (https://paperswithcode.com/method/position-wise-feed-forward-layer), which is perhaps a meaningful distinction.
But ya, I can't blame you. ...The paper itself could stand to be much clearer on the matter haha


text:
How could facts be distinguished from opinions?
As a software engineer, I am searching for an existing solution or, if none exists, willing to create one that will be able to process texts (e.g. news from online media) to extract/paraphrase dry facts from them, leaving all opinions, analysis, speculations, humor, etc., behind.
If no such solution exists, what would be a good way to start creating it (considering that I have zero experience in AI/machine learning)?
It would be no problem to manually create a set of examples (pairs of original news + dry facts extracted), but is that basically what it takes? I doubt so.
(This knowledge domain is already huge, so which parts of it need to be learned first and foremost to figure out how to achieve the goal?)

I will be starting my PhD in natural language processing in a few days and this is very similar to my proposed topic. It's an open problem that ties NLP and AI into philosophy of science and epistemology and is, I think, extremely interesting. I say all this to drive home the point that this is not a simple problem.
Two major theoretical concerns come to my mind:

What is a "fact"? Is it a universal truth, if there is such a thing? Or is it a generally accepted theory, and if so how do you measure acceptance? That is, accepted by whom, where, when?

Are there any linguistic markers of opinions vs. facts? Only in rare cases, such as when the speaker prefaces their statement with something like "I believe". In most cases, I think, opinions will be stated linguistically similarly to facts. For example, compare "Cats are felines." (a "fact") with "Cats are aliens." (an opinion some may hold). They have the exact same syntactic structure. The difference here is deeply semantic, and probably relates to the speaker's intention. I'd venture that often people state their opinions with the intention of communicating a "fact".

Some more practical concerns are:

Information extraction (also called relationship extraction, text mining, etc.), which for the most part assumes that the "facts" given in the labeled datasets are correct, is far from a solved problem. E.g. the state of the art model developed for a task released in 2010 has an F1 of only 76! What you propose adds significant uncertainty to these types of tasks.

I suspect that even if you were able to compile a dataset of facts and opinions with corresponding labels you would encounter a number of modeling problems. Given the linguistic similarity between the statements of facts and opinions, I'd guess that your model will simply memorize the dataset, making it generalize poorly to your test set. Either that or it would would pick up on random, hidden correlations in the data to solve the problem (neural nets are really good at this), perhaps generalizing to the test set, but failing to apply to any other data.

Fact vs. opinion is something that is embedded in a cultural milieu, so a model would, I think, need access to some proxy for what is culturally accepted in order to make this distinction, perhaps a via knowledge base. This may be feasible for limited, highly curated domains (e.g. biomedicine), but there is currently nothing suitable for a general-purpose fact finder.

tldr: No, it is not enough to simply create a dataset of facts vs. opinions. This problem poses major theoretical concerns related to epistemology, linguistics, and cognitive science. Additionally, there are more mundane (but non-trivial!) modeling issues to consider. @Sceptre is right that it will be impossible to start this without knowledge of AI/ML/NLP, especially a rather deep knowledge of what current AI systems are really capable of.

@DuttaA By saying a fact is based on truth you've just redirected the question: what is truth? Many believe that truth is conditional on a set of assumptions or a context. To riff off your sunrise example, the sun does not, in fact, rise at 5AM where I live; perhaps I use a different time system where the day is cut into 20 hours, so it rises at approximately 4.167AM; if one looks deeply enough the sun never rises at exactly 5AM, but "close enough" to 5AM; etc. So the real question might be "what is true given these assumptions?"


text:
Which loss function should I use in REINFORCE, and what are the labels?
I understand that this is the update for the parameters of a policy in REINFORCE:
$$
\Delta \theta_{t}=\alpha \nabla_{\theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) v_{t},
$$
where $v_t$  is usually the discounted future reward and  $\pi_{\theta}\left(a_{t} \mid s_{t}\right)$ is the probability of taken the action that the agent took at time $t$. (Tell me if something is wrong here)
However, I don't understand how to implement this with a neural network.
Let's say that probs = policy.feedforward(state) returns the probabilities of taking each action, like [0.6, 0.4]. action = choose_action_from(probs) will return the index of the probability chosen. For example, if it chose 0.6, the action would be 0.
When it is time to update the parameters of the policy network, what should we do? Should we do something like the following?
gradient = policy.backpropagate(total_discounted_reward*log(probs[action])
policy.weights += gradient

And I only backpropagate this through one output neuron?
Which loss function should I use in this case? What would the labels be?
If you need more explanation, I have this question on SO.

I use a cross entropy loss when I implement this in PyTorch. I tried doing a forward pass of the network evaluated at the current action and taking the log but it didn't seem to work when I implemented it, so I stuck with cross entropy loss.

Is this question related to a specific library (eg. pytorch or tensorflow)? Or is this just a question for a more specific but still general pseudocode?

@David Ireland Cross entropy with what? What would be the label, y hat, or correct answer in the equation?

@Hai Nguyen It is a lot about the general pseudocode, but if you click on the link you can see I built my own neural network out of just NumPy.

@S2673 It is cross-entropy loss using as the label the action you actually took during sampling. Multiplying by the value function is really critical addition though, it can even reverse the sign of all the gradients (which makes sense - if you have chosen an action and it was a bad choice, you want to reduce the chance of taking it again)

@Neil Slater So if you had the probabilities [0.7,0.3] and the policy chose 0.7 then you would cross entropy loss with [0.7,0.3] and label [1,0] then multiply the gradient by the total reward? And is that what happens in REINFORCE or is that something different?

@S2673: Yes, that is essentially what happens in REINFORCE. You can (and often would) choose different multiplier, with baselines, but basic REINFORCE just uses the measured return. A common choice is some estimate of advantage (action value minus state value).

The loss function you are looking for is cross entropy loss. The 'label' that you use is the action you took at the time point you are updating for.

Okay, thank you. It was not working with my code so I had to build a new, simpler one to test it and it worked. That’s why it took so long. There’s just one more thing... How do I know to do this given the equation in my question? Or is this not what the equation meant?

Should have clarified in my answer that I was referring to the cross entropy loss in pytorch — if you read the documentation you see that this loss function is the log of the policy for the action you give it.

Thanks. Do you, by any chance, know how this works for a policy gradient with a continuous action space where the neural network outputs a Gaussian distribution? The equation for this update is the same but it is the log of a different output.

@S2673 The algorithm doesn't change in this situation. Say your NN outputs the mean parameter of the Gaussian, then $\log_\pi(a_t | s_t)$ is just the log of the normal density evaluated at the action you took where the mean parameter in the density is the output of your NN. You are then able to backpropagate through this to update the weights of your network.

Thank you. I had figured this out a bit ago.

@S2673 Apologies, I forgot to reply sooner


text:
Should I remove the text overlaying some images in the dataset before training the CNN?
If I am attempting to train a CNN on some image data to perform image classification, but some of the images have pieces of text overlaying them (for the purpose of description to humans), then is it better for the CNN to remove the text? And if so, then how do I remove the text? Furthermore, is it a good idea to use both the images with text overlaying them and the images with the removed text for training, since it might act as a form of data augmentation?

Removing the overlayed text might increase accuracy, but you'd need to train a different model to do this, and that is an entirely different task as it is no longer classification, but generation. There are easier ways to augment your data and probably get similar benefits to your accuracy. However, if you would still like to do this, there is a lot of examples you can find by simple searching "Watermark removal machine learning" in google. Here's an example I found.
Overall, a CNN will be able to look past the overlayed text without issue, and perform classification like it would without the overlayed text. There is the possibility that it actually learns relationships between the overlayed text and the expected output, but that depends on the data, and is likely a harder task then simply identifying features.
The only issue you might run into is if the real data this model will be used on is different to the data provided, as in the real word images do not contain overlayed text describing what the image is.

I should have said: Not all of the data will have text overlaying it, so I guess that would help train the CNN to look past the text as "noise"?

Furthermore, with regards to my other question, if I use some method to remove the overlaying text, then should I still keep both versions of the images for training, just treating it the same way as we would augmented data (for the same benefit as we strive for when augmenting data)? Or is there some downside scenario where keeping the images with overlaying text actually decreases performance somehow?

The CNN will probably then just learn to ignore the text, but it depends on how many images contain the text and how many don't.
No if the testing dataset contains images with text you should definitely keep these images in the training data.

The only scenario I'd say removing the text with some method is necessary is if the amount of images without text is very small when compared to the amount that does have text. That way you will have a better balanced dataset, and the network shouldn't under-perform on images without text


text:
What does $r : \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$ mean in the article Hindsight Experience Replay, section 2.1?
Taken from section 2.1 in the article:

We consider the standard reinforcement learning formalism consisting of an agent interacting with an environment. To simplify the exposition we assume that the environment is fully observable. An environment is described by a set of states $S$, a set of actions $A$, a distribution of initial states $p(s_0)$, a reward function $r : \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$, transition probabilities $p(s_{t+1} \mid s_t, a_t)$, and a discount factor $\gamma \in [0, 1]$.*

How should one interpret the maths behind it?

This answer assumes that you only have a problem with this notation from the article:

$r : \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$

This is a standard notation, used in many disciplines, for defining a function and its input and output domains. It is a bit like the method signature for the function - it does not fully define it, but does enough to show how it can interact with other expressions.
All functions can be thought of as maps between the input domain and output domain. You provide an input value, and it returns an output value. The values can be arbitrary mathematical objects. To show what kind of objects the inputs and outputs are allowed to be, the notation for sets is used.
Importantly the symbol $\mathbb{R}$ at the end does not refer to the set of possible rewards in the environment (although it is a reward function, and that will be its output), but the set of all real numbers, because a reward is always a real number*.
As a concrete example, if you had the function $f(x) = x^2 - 2x + 7$ defined for a real number $x$, then its equivalent notation might be $f : \mathbb{R} \rightarrow \mathbb{R}$. If you allowed $x$ to be complex then it would be $f : \mathbb{C} \rightarrow \mathbb{C}$, because $\mathbb{C}$ is the standard symbol for the set of all complex numbers.
So now we can break down the notation $r : \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$

$r$

The function is called $r$

$:$

It has an input domain of . . .

$\mathcal{S} \times \mathcal{A}$

The cartesian product of the set of all possible states $\mathcal{S}$ and the set of possible actions $\mathcal{A}$.
That is much the same as saying the function has a signature $r(s, a)$ where $s \in \mathcal{S}$ and $a \in \mathcal{A}$

$\rightarrow$

It has an output domain of . . .

$\mathbb{R}$

any single real number.

* This choice (of declaring the more general $\mathbb{R}$ instead of specific $\mathcal{R}$) is made partly because operators like $+$ and $\times$ are well defined for real numbers. This is a useful thing to assert about the behaviour of the reward function output when defining how value functions work for instance. Of course you could be more specific, defining $\mathcal{R}$ as some subset of $\mathbb{R}$, that would be correct and more precise definition, but it is not needed for general theory in reinforcement learning. The less precise definition is fine for nearly all purposes.


text:
When are multiple hidden layers necessary?
I know that my question probably seems like being asked many times, but Ill try
to be more speciffic:
Limitations to my question:

I am NOT asking about convolutional neural networks, so please, try not to mention this as an example or as an answer as long as it is possible. (maybe only in question number 3)

My question is NOT about classification using neural networks

I am asking about a "simple" neural network designed to solve the regression type of problem. Let's say it has 2 inputs and 1 output.

Preambula:
As far as I understood, from the universal approximation theorem, in such a case, even if the model is nonlinear, only one hidden layer can perfectly fit a nonlinear model, as shown here
http://neuralnetworksanddeeplearning.com/chap4.html.
Question 1
In this specific case, is there any added value in using extra layers?
(maybe the model will be more precise, or faster training?)
Question 2
Suppose in 1st question the answer was there is no added value. In such a case will the added value appear if I enlarge inputs from two inputs as described above, to some larger number?
Question 3
Suppose in 2nd question the answer was there is no added value. I am still trying to pinpoint the situation where it STARTS making sense in adding more layers AND where it makes NO sense at all using one layer.

Please, ask one question per post. If you have multiple questions, ask each of them in its separate post. Take a look at https://ai.stackexchange.com/help/on-topic for more info about our site.

A very wide but shallow neural network is going to be harder to train.
You can check that with the playground of tensorflow or with the MPG example in Google Colab.
The relationship between architecture and learning capabilities is not fully understood, but, empirically, thats what you see.
But making the network too deep creates more problems:

Vanishing gradients.
Less parameters for the same amount of neurons.
Exploding gradients.

It is for that reason that humans and neural networks are the one deciding a good architecture.

"understud" => understood. Also, vanishing gradients typically occur as you increase the depth and not width?


text:
Why do all states appear identical under the function approximation in the Short Corridor task?
This is the Short Corridor problem taken from the Sutton & Barto book. Here it's written:

The problem is difficult because all the states appear identical under the function approximation

But this doesn't make much sense as we can always choose states as 0,1,2 and corresponding feature vectors as
x(S = 0,right) = [1  0  0  0  0  0]
x(S = 0 , left)  = [0  1  0  0  0  0]
x(S = 1,right) = [0  0  1  0  0  0]
x(S = 1 , left) = [0  0  0  1  0  0]
x(S = 2,right) = [0  0  0  0  1  0]
x(S = 2 , left) = [0  0  0  0  0  1]\
So why is it written that all the states appear identical under the function approximation?

You can choose those states, but is the agent aware of the state it is in? From the text, it seems that the agent cannot distinguish between the three states. Its observation function is completely uninformative.
This is why a stochastic policy is what is needed. This is common for POMDPs, whereas for regular MDPs we can always find a deterministic policy that is guaranteed to be optimal.

In toy problems like the Short Corridor task, you can choose the state representation to explore a key property, such as the ability of a particular method to solve it. Often this is done to extremes and heavily simplified.
That is what is going on here. The state space that the agent is allowed to use is made highly degenerate with respect to the problem. This stands in for perhaps more complex partially observable systems, but in a way that is really clear to the reader. Also, it is still possible to derive analytically what the best policy should be, so methods can be examined as to how well they deal with the core issue (here, that state data is ambiguous).


text:
When should one prefer using Total Variational Divergence over KL divergence in RL
In RL, both the KL divergence (DKL) and Total variational divergence (DTV) are used to measure the distance between two policies. I'm most familiar with using DKL as an early stopping metric during policy updates to ensure the new policy doesn't deviate much from the old policy.
I've seen DTV mostly being used in papers giving approaches to safe RL when placing safety constraints on action distributions. Such as in Constrained Policy Optimization and Lyapunov Approach to safe RL.
I've also seen that they are related by this formula:
$$
D_{TV} = \sqrt{0.5 D_{KL}}
$$
When you compute the $D_{KL}$ between two polices, what does that tell you about them, and how is it different from what a $D_{TV}$ between the same two policies tells you?
Based on that, are there any specific instances to prefer one over the other?

I did not read those two specified linked/cited papers and I am not currently familiar with the total variation distance, but I think I can answer some of your questions, given that I am reasonably familiar with the KL divergence.

When you compute the $D_{KL}$ between two polices, what does that tell you about them

The KL divergence is a measure of "distance" (or divergence, as the name suggests) between two probability distributions (i.e. probability measures) or probability densities. In reinforcement learning, (stochastic) policies are probability distributions. For example, in the case your Markov decision process (MDP) has a discrete set of actions, then your policy can be denoted as $$\pi(a \mid s),$$which is the conditional probability distribution over all possible actions, given a specific state $s$. Hence, the KL divergence is a natural measure of how two policies are similar or different.
There are 4 properties of the KL divergence that you always need to keep in mind

It is asymmetric, i.e., in general, $D_{KL}(q, p) \neq D_{KL}(p, q)$ (where $p$ and $q$ are p.d.s); consequently, the KL divergence cannot be a metric (because metrics are symmetric!)
It is always non-negative
It is zero when $p = q$.
It is unbounded, i.e. it can be arbitrarily large; so, in other words, two probability distributions can be infinitely different, which may not be very intuitive: in fact, in the past, I used the KL divergence and, because of this property, it wasn't always clear how I should interpret the KL divergence (but this may also be due to my not extremely solid understanding of this measure).

and how is it different from what a $D_{TV}$ between the same two policies tells you?

$D_{TV}$ is also a measure of the distance between two probability distributions, but it is bounded, specifically, in the range $[0, 1]$ [1]. This property may be useful in some circumstances (which ones?). In any case, the fact that it lies in the range $[0, 1]$ potentially makes its interpretation more intuitive. More precisely, if you know the maximum and minimum values that a measure can give you, you can have a better idea of the relative difference between probability distributions. For instance, imagine that you have p.d.s $q$, $p$ and $p'$. If you compute $D_{TV}(q, p)$ and $D_{TV}(q, p')$, you can have a sense (in terms of percentage) of how much $p'$ and $p$ differ with respect to $q$.
The choice between $D_{TV}$ and $D_{KL}$ is probably motivated by their specific properties (and it will probably depend on a case by case basis, and I expect the authors of the research papers to motivate the usage of a specific measure/metric). However, keep in mind that there is not always a closed-form solution not even to calculate the KL divergence, so you may need to approximate it (e.g. by sampling: note that the KL divergence is defined as an expectation/integral so you can approximate it with a sampling technique). So, this (computability and/or approximability) may also be a parameter to take into account when choosing one over the other.
By the way, I think that your definition of the total variational divergence is wrong, although the DTV is related to the DKL, specifically, as follows [1]
\begin{align}
D_{TV} \leq \sqrt{\frac{1}{2} D_{KL}}
\end{align}
So the DTV is bounded by the KL divergence. Given that the KL divergence is unbounded (e.g. it can take very big values, such as 600k, this bound should be very loose).
Take a look at the paper On choosing and bounding probability metrics
 (2002, by Alison L. Gibbs and  Francis Edward Su) or this book for information about $D_{TV}$ (and other measures/metrics).

So $D_{TV}$ being bounded is a distinguishing property.  "the fact that it lies in the range [0,1] potentially makes its interpretation more intuitive". Please clarify what it "...makes its interpretation more intuitive" means because I don't understand that part well. Thanks for pointing out the correct definition of $D_{TV}$. I'll look at the paper and book you've pointed out.

@mugoh When I say that boundedness makes it more intuitive it's because you know exactly what is the maximum, but in the case of the KL divergence you don't know if the current value of the KL divergence is really big or actually not so big.

Anyway, the bound shown in my answer is probably very loose, given that the KL divergence can really be arbitrarily large (e.g. 600k) and the total variational is between $0$ and $1$ (according to the sources I've seen).

That's much clear. Emphasizing that the bound is very loose especially gives a better picture on the difference between the two.

I've looked at the referenced book and paper. And they both explain $D_{TV}$ in depth. One point I picked is that $D_{TV}$ as a metric, converges fast because it's insensitive to element-wise differences when total difference remains the same. So $D_{TV}$ converges while $D_{KL}$, being a non-metric, doesn't. This might also influence the choice. (2) It admits natural interpretations and bounding techniques, as you emphasized in your answer.

To add to nbro's answer, I'd say also that much of the time the distance measure isn't simply a design decision, rather it comes up naturally from the model of the problem. For instance, minimizing the KL divergence between your policy and the softmax of the Q values at a given state is equivalent to policy optimization where the optimality at a given state is Bernoulli with respect to the exponential of the reward (see maximum entropy RL algorithms). As another example, the KL divergence in the VAE loss is a result of the model and not just a blind decision.
I'm less familiar with total variation distance, but I know there's a nice relationship between the total variation distance of a state probability vector and a Markov chain stationary distribution relative to the timestep and the mixing time of the chain.
Finally, another thing to consider is the properties of the gradients of these divergence measures. Note that the gradient of the total variation distance might blow up as the distance tends to $0$. Additionally, one must consider if unbiased estimators of the gradients from samples can be feasible. While this is generally the case with KL divergence, I'm not sure about total variation distance (as in, I literally don't know), and this is generally not the case with the Wasserstein metric (see Marc G. Bellemare et. al's paper "The Cramér distance as a solution to biased wasserstein gradients"). However, of course there's other scenarios where the tables are turned -- for instance, the distributional bellman operator is a contraction in the supremal Wasserstein metric but not in KL or total variation distance.
TL; DR: Many times mathematical/statistical constraints suggest particular metrics.

This point is quite useful. I've looked at the Constrained Policy Optimization paper again and I identify their use for $D_{TV}$ as a choice that relates to satisfying a mathematical constraint, if I'm not wrong. Specifically, in deriving a safe policy improvement, the authors bound the difference in objective between 2 policies $J(\pi') - J(\pi)$ to an equation where the $D_{TV}({\pi^\prime ||  \pi}) $ is a multiplying factor of the advantange $A_{\pi'}$. Something I'm guessing the $D_{KL}$ will probably not hold

Interesting. I haven't read that paper yet, but I'll likely take a look. As I understand it TRPO uses KL to stop the policy from changing too drastically, and the paper "Taylor Expansion Policy Optimization" from ICML this year generalized it. Cool stuff.

I'll have a look at the mentioned mentioned paper. Coincidentally, Constrained Policy Optimization tries to make TRPO safe. It's safe policy search algorithms in general, but authors used TRPO as their example


text:
Why is the fraction of time spent in state $s$, $\mu(s)$, not in the update rule of the parameters?
I am reading "Reinforcement Learning: An Introduction (2nd edition)" authored by Sutton and Barto. In Section 9, On-policy prediction with approximation, it first gives the mean squared value error objective function in (9.1):
$\bar{VE}(\boldsymbol{w}) = \sum_{s \in S} \mu(s)[v_{\pi}(s) - \hat{v}(s,\boldsymbol{w})]^2$. (9.1)
$\boldsymbol{w}$ is a vector of the parameterized function $\hat{v}(s,\boldsymbol{w})$ that approximates the value function $v_{\pi}(s)$. $\mu(s)$ is the fraction of time spent in $s$, which measures the "importance" of state $s$ in $\bar{VE}(\boldsymbol{w})$.
In (9.4), it states an update rule of $\boldsymbol{w}$ by gradient descent:
$\boldsymbol{w}_{t+1} = \boldsymbol{w} -\frac{1}{2}\alpha \nabla[v_{\pi}(S_t) - \hat{v}(S_t,\boldsymbol{w})]^2$. (9.4)
I have two questions regarding (9.4).

Why $\mu(s)$ is not in (9.4)?
Why is it the "minus" instead of "+" in (9.4)? In other words, why is it $\boldsymbol{w} -\frac{1}{2}\alpha \nabla[v_{\pi}(S_t) - \hat{v}(S_t,\boldsymbol{w})]^2$ instead of $\boldsymbol{w} +\frac{1}{2}\alpha \nabla[v_{\pi}(S_t) - \hat{v}(S_t,\boldsymbol{w})]^2$?

I think your equation number 9.4 is not correct? There is indeed + sign in Sutton's book and also $\nabla{V(s,w)}$ at the end.

They are giving same importance to all the states, so there is no $\mu(s)$

@SwaksharDeb the + sign is in (9.5) because it expands the gradient equation. But why it is a - sign in the first place in (9.4)?

@SwaksharDeb So in (9.4) it "assumes" all the states are equally important, otherwise $\mu(s)$ will appear in the equation?

This is a stochastic gradient descent update. I think your problem is related to gradient descent.

Yes. for simplicity they are treating all-state with the same importance

I now understand why it is a minus sign in (9.4). The objective is to minimize $VE(w)$, so it needs to move to the negative of the gradient direction.

$\mu(s)$ is not in equation (9.4) because we are assuming that the examples by which we update our parameter $w$, i.e. the frequency of which we will observe the states during online training, is the same. That is, it is a constant with respect to $w$ and since we are differentiating it can be somewhat disregarded as a constant of proportionality -- it essentially can be 'absorbed' by $\alpha$.

The minus is there because we are performing gradient descent. For more information on this, see e.g. the wikipedia page


text:
Is the state transition matrix known to the agents in a Markov decision processes?
The question is more or less in the title.
A Markov decision process consists of a state space, a set of actions, the transition probabilities and the reward function. If I now take an agent's point of view, does this agent "know" the transition probabilities, or is the only thing that he knows the state he ended up in and the reward he received when he took an action?

In reinforcement learning (RL), there are some agents that need to know the state transition probabilities, and other agents that do not need to know. In addition, some agents may need to be able to sample the results of taking an action somehow, but do not strictly need to have access to the probability matrix. This might be the case if the agent is allowed to backtrack for instance, or to query some other systems that simulates the target environment.
Any agent that needs to have access to the state transition matrix, or look-ahead samples of the environment is called model-based. The model in this case can either be a distribution model i.e. the state transition matrix, or it can be a sampling model that simulates the outcome from a given state/action combination.
The state transition function $p(r, s'|s, a)$ which returns the probability of observing reward $r$ and next state $s'$ given the start state $s$ and action $a$, is another way to express the distribution model. It often maps simply to the state transition matrix, but can be a more complete description of the model.
One example model-based approach is Value Iteration, and that requires access to the full distribution model in order to process value update steps. Also, any reinforcement learning that involves planning must use some kind of model. MCTS, as used in AlphaGo, uses a sampling model for instance.
Many RL approaches are model-free. They do not require access to a model. They work by sampling from the environment, and over time learn the impact on expected results due to behaviour of the unknown state transition function. Example methods that do this are Monte Carlo Control, SARSA, Q learning, REINFORCE.
It is possible to combine model-free and model-based methods by using observations to build an approximate model of the environment, and using it in some form of planning. Dyna-Q is an approach which does this by simply remembering past transitions and re-using them in the background to refine its value estimates. Arguably, the experience replay table in DQN is a similar form of background planning (the algorithm is essentially the same). However, more sophisticated model-learning and reuse is not generally as successful, and is not seen commonly in practice. See How can we estimate the transition model and reward function?
In general, model-based methods on the same environment can learn faster than model-free methods, since they start with more information that they do not need to learn. However, it is quite common need to learn without having an accurate model available, so there is lots of interest in model-free learning. Sometimes an accurate model is possible in theory, but it would be more work to calculate predictions from the model than to work statistically from the observations.


text:
What is the need for so many filters in a CNN?
Consider the following coding line related to CNNS
Conv2D(64, (3,3), strides=(2, 2), padding='same')

It is a convolution layer with filter size $3 \times 3$ and step size of $2\times 2$.
I am confused about the need for $64$ filters.
Are they doing the same task? Obviously, it is no. (one is enough in this case)
Then how do each filter differ by? Is it in hovering over the input matrix? Or is it in the values contained by filter itself? Or differs in both hovering and content?
I am finding difficulty in visualizing it.

Then how do each filter differ by? Is it in hovering over the input matrix? Or is it in the values contained by filter itself? Or differs in both hovering and content?

The filters (aka kernels) are the learnable parameters of the CNN, in the same way that the weights of the connections between the neurons (or nodes) are the learnable parameters of a multi-layer perceptron (or feed-forward neural network).
So, the value of these filters is not fixed or pre-determined, but will depend on how you train the CNN, i.e. the learning algorithm, the objective function and the data. If you use gradient descent as the learning algorithm, you will be minimizing a loss (aka cost or error) function (e.g. the cross-entropy, in the case of classification problems). To do that, you need to find the gradient of the loss function with respect to the filters. You then apply a step of gradient descent (i.e. you add a scaled version of the gradient of the loss function with respect to the parameters to the parameters), so that this loss decreases.
To answer your question more directly, the only thing that usually changes is just the value of the filters. The convolution (or cross-correlation) operation is the same for all filters.
Why do you use more than one filter? The usual explanation is that each filter, when convolved with the input, will extract different features from it, and the specific features that they will extract will depend on the specific values of the filters, which, in turn, depend on the data, so we can say that CNNs are data-driven feature extractors. If you are familiar with image processing techniques, then you know that different filters, when convolved with the same image, can have different effects (e.g. blurring or de-noising).

All filters move across the same area, but the filter values (also called filter kernels) are different for each filter. This makes it possible to "filter out" different features.


text:
Evaluate model multiple times in loss function? Is this reinforcement learning?
I am interested in models that exhibit behavior. My goal is a model that survives indefinitely on a two dimensional resource landscape. One dimension represents the location (0 to 1) and the second says if there is a resource available at that location (-1 = resource one, 0 = no resource, 1 = resource two).
The landcape looks like this:
location = [0, 0.2, 0.4, 0.6, 0.8, 1]
resource = [-1, 0,   0,   0,   0,  1] (I added spaces so the elements line up)

My model represents an organism deciding if it will move or rest on the landscape at each time step. The organism has reserves of each resource. The organism fills its reserve of a resource if it rests on the resource and loses 1 unit of both resources at each time step. I am considering neural networks to represent my organisms. The input would be 4 values; The location on the landscape, the resource value at that location, and the reserve levels of resource one and two. The output would be 3 values; move right, rest, move left. The highest value decides what happens. To survive indefinitely the model will have to bounce between the ends of the landscape, briefly resting on the resource. Model evaluation would go like this: start the model in the middle of the landscape with full resource reserves. Allow time to pass until one of the resource reserves is depleted (the organism dies).
My question is this: Can my loss function be evaluating the model until it dies? 1/survival time could be the loss value to be minimized by gradient descent. Is this a reinforcement learning problem (I don't think so..?) Thanks!!

Can my loss function be evaluating the model until it dies? 1/survival time could be the loss value to be minimized by gradient descent.

In order to use backpropagation and gradient descent, you have to relate the loss function directly to the output of the neural network. Your proposed loss function is too indirect, it is not possible to turn it directly into a gradient that could be used to alter the neural network weights.
In addition, the specific function of time you have chosen will be difficult to optimise, as incrememental improvements from e.g. 10 to 11 time steps surviving will provide a much lower signal for adjusting behaviour than the improvement from  e.g. 2 to 3 lifetime. If the environment has enough randomness (and typically these kind of a-life scenarios do), then the signal here could be swamped by random events and very hard to optimise, requiring a larger number of samples in order to extract expected improvements to the loss function.

Is this a reinforcement learning problem (I don't think so..?)

It is very close to a definition of reinforcement learning (RL) problem. For a RL problem you need the following things:

An environment in which an agent exists, and which has a measurable state.

A set of actions = sequential decisions that need to be made, and that have consequences.

The consequences of any action are:

A consistent (but allowing for some randomness) change to the state of the environment. Here you have change to agent's location and resource levels.
A consistent scalar reward value that measures how well the agent is achieving a goal. This can also be partially random, and can also be sparse, only achieved in certain specific states.

In your problem definition you don't have a reward signal, but it would be easy to add one. A suitable one would be $+1$ per time step.
Technically your problem would also be partially observable (sometimes called a POMDP), in that the agent does not get to see resources available in other locations. It only knows its current location, its internal state and resources available at its current location. This is not a major issue, although you should note that adding some kind of memory (either open-ended memory as in a recurrent neural network, or explicitly added to the state) would allow for more efficient agents. That's not a RL issue as such, any learning process without ability to form or use memories would be limited in this environment, and you might want to look into that as a later experiment.
How RL helps is that it provides a framework to convert your problem definition into measurements and gradients for the neural network to improve its performance.
As you have set up your neural network to predict best action choice, this would naturally lend itself to policy gradient methods in RL, such as REINFORCE. As it is a simple problem, I would expect REINFORCE with baseline to perform well enough for it.
I will not explain the algorithm here in full detail, but the basic approach is to have the agent act with the current network for a few episodes, collecting data on its choices and performance. You will get a dataset of (state, action, return = sum of rewards to end of episode). You then use that as a labelled dataset to train a minibatch as if the action choice was correct ground truth, but multiply each gradient by (return - baseline) where the baseline is typically the average return seen so far from that state. You may need a second neural network during training to estimate that expected return (aka state value). After using a minibatch once, you will need to discard it, as it represents results for the previous iteration of the network before the weight updates. There are ways around this, but not typically done in REINFORCE - instead the approach is to just keep generating data and train on the new mini-batch as fast as you can go.
RL offers other methods which may work just as well to solve your problem, but I suspect REINFORCE will serve you well since it will allow the agent to randomise direction choice which is important when it cannot see where the resources are and has no memory of where it has searched.
You don't have to use RL for this problem. An alternative that may work for you is using genetic algorithms to tune the network architecture and weights. It avoids using gradients, but I would still recommend a simple fitness function equal to number of time steps survived. There is a framework called NEAT which is ideal for this sort of a-life control problem.

Thanks! I'm checking out the neat-python library as I originally wanted to do this with genetic algorithms!


text:
What are proxy reward functions?
The understanding I have is that they somehow adjust the objective to make it easier to meet, without changing the reward function.

... the observed proxy reward function is the approximate solution to a reward design problem

(source: Inverse Reward Design)
But I have trouble getting how they fit the overall reward objective and got confused by some examples of them.
I had the idea of them being small reward functions (as in the case of solving for sparse rewards) eventually leading to the main goal. But the statement below, from this post, made me question that.

Typical examples of proxy reward functions include “partial credit” for behaviors that look promising; artificially high discount rates and careful reward shaping;...

What are they, and how would one go about identifying and integrating proxy rewards in an RL problem?

In the examples above, how would high discount rates form a proxy reward?

I'm also curious about how they are used as a source of multiple rewards

Maybe have a look at https://ai.stackexchange.com/q/20040/2444, although I think that you know what "proxy" usually means.

So "proxies" are intermediaries. This helped add clarity into the "what are they" part of the question

Please, read my answer below https://ai.stackexchange.com/a/24074/2444, if you haven't yet. You should accept it, if it answers your question. I read that IRD paper and other related papers, so I'm pretty confident that the answer is correct. If something is still unclear, let me know. Please, take a look at https://ai.stackexchange.com/help/someone-answers for more details.

Thanks for pointing this out  @nbro. I was also seeking clarity on how high discount rates form proxy rewards and hiw proxies can be used as a source of multiple rewards

It's not indeed clear what the article's author meant by "artificially high discount rates". It's not even clear if they are referring to the discount factor of the RL algorithm. Even if that was the case, it's not very clear why that would be a "proxy reward function". The discount factor is the way to weight short-term and long-term rewards, but it's not very clear why one would consider that a "proxy reward function". Maybe this has to do with the "long time horizon" part of that article. Maybe the best thing to do is e-mail the article's author and ask him to answer your other questions.

Regarding how multiple "proxies" can be used as a source for multiple rewards, I think that the idea is that you can specify partial reward functions, i.e. reward functions that specify some type of partial behaviour that you want to agent to have. So, for instance, if you want to train an agent to play football/soccer, you may have a proxy reward function that specifies how the agent is supposed to kick the ball and another that specifies how the agent needs to move in the field. This is at least the idea that I have after having read that article.

In the paper that you cite, Inverse Reward Design (2017), the authors actually define what they mean by "proxy reward function".

We formalize this in a probabilistic model that relates the proxy (designed) reward to the true reward

So, the proxy reward function is the reward function designed by the human, which may not necessarily be the reward function that he/she intended (i.e. it may be a misspecified reward function), given that the human may have forgotten to model/incorporate certain (unpredicted by the human) scenarios or situations that the agent may face. This usage of the word "proxy" is thus consistent with the general usage of the word in computer science, i.e. a "proxy reward function" is a reward function that is used instead of the intended (optimal) reward function.


text:
What is the difference between neural networks and other ways of curve fitting?
For simplicity, let's assume we want to solve a regression problem, where we have one independent variable and one dependent variable, which we want to predict. Let's also assume that there is a nonlinear relationship between the independent and dependent variables.
No matter the way we do it, we just need to build a proper curved line based on existing observations, such that the prediction is the best.
I know we can solve this problem with neural networks, but I also know other ways to create such curves. For example:

splines

kriging

lowess

Something I think would also work (do not know if exists): fitting curve using a series of Fourier sine waves, and so on

My questions are:

Is it true that neural networks are just one of the ways to fit a non-linear curve to the data?

What are the advantages and disadvantages of choosing a neural network over other approaches? (maybe it becomes better when I have many independent variables, and another little guess: maybe the neural network is better in omitting the effect of linear dependent input variables?)

In some sense, you're right that a neural net is just another tool to fit data. However, it's quite the tool! There's this universal approximation theorem saying that, under decent conditions, a neural network can get as close as you want to a wide class of functions. This means that you can get the network to give you complicated shapes with squiggles all over if that's the right trend.

The universal approximation theorem is a big upside. You don't have to specify that you want to model with sine curves or a particular type of spline. You just let the computer figure that out for you. The result is the ability to model complex patterns and make accurate predictions. The drawback is that the modeling can pick up on coincidences in the data that look like a trend but are not. This causes overfitting. When your goal is to make accurate predictions, a model that has badly overfit does nothing for you. A second drawback is that neural networks are hard to interpret. A third drawback is that they can take a long time to train, while a linear regression is just a matrix inversion and a few matrix products (the $\hat{\beta}=(X^TX)^{-1}X^Ty$).

Not an expert but is the universal approximation theorem really saying something very special about neural networks? Paraphrasing a neural network expert: "The universal approximation theorem does NOT guarantee that you will converge to an arbitrarily good approximation of a wide class functions. It just means that this approximation is in the search space. There is no guarantee you will converge to it and in fact you almost never will." This sounds very similar to guarantees that are available when fitting with many other bases (sin/cos, polynomials, etc...)

@Kvothe It is not clear if that quote refers to convergence in terms of training (converging to the optimum for a given architecture) or convergence of network to a function as more and more nodes are added to it. I am on board with the former but not the latter. The universal approximation theorems say, much like the Stone-Weierstrass theorem for polynomials or Carlson's theorem for Fourier series, that you can approximate any function (of a particular class, specified by the theorem details) by making a sufficiently complex neural network.

I think I meant the former. In the latter part of your reply: Are you agreeing that there is nothing too special about neural networks and that universal approximation theorem basically just gives you a completeness of your basis that you also get in most other fitting methods?

@Kvothe Completeness as in Cauchy completeness?

I might be incorrectly borrowing language from intuitively similar spaces (e.g. Hilbert spaces). With "complete basis" in this case I mean a set of functions which give an arbitrarily good approximation for any function in a certain class of functions (the space for which these functions act as a "basis").

@Kvothe The various universal approximation theorems give the conditions under which a neural network can approximate a function to any degree of accuracy. That sounds like what you’re saying, yes.

Right, my point being that there are many alternatives, making neural nets not that special. It is not that clear from your answer what advantages it has over other approaches that come with very similar theorems. For that matter it sounds like you would also say that polynomial fits or Fourier series are also "quite the tool!". What really sets neural networks apart?

@Kvothe To a large extent, I don’t think neural networks are that special, just popular (warranted or not). Perhaps you could consider posting your question formally, either here or on the statistics Stack, Cross Validated, where a more thorough answer could be posted (not just by me).


text:
Why does the training time of SVMs dramatically decrease after applying dimensionality reduction to the features?
Training an SVM with an RBF kernel model with c = 5.5 and gamma = 1.06, for a 5-class classification problem on the NSL-KDD train data-set with 122 features using one vs rest strategy takes $2162$ seconds. Also, considering binary classification (c = 10, gamma = 4), it takes $520.56$ seconds.
After dimensionality reduction, from 122 to 30, using a sparse auto-encoder, the training time falls dramatically, from $2162$ to $240$ and $520$ to $170$, while using the same hyperparameters for the RBF-kernel.
What is the reason for that? Is it not true that using kernel neutralized the effect of high dimensions?

SVM complexity is $O(\max(n,d)\min(n,d)^2)$ according to Chapelle, Olivier. "Training a support vector machine in the primal." Neural Computation 19.5 (2007): 1155-1178.
$n$ is the number of instances and $d$ is the number of dimensions. I'm assuming that you have more instances than dimensions giving a complexity of $O(nd^2)$. Hopefully this explains fully why reducing the number of dimensions will reduce the training time.

thank you for your answer. but; is this true after using RBF kernel? because its map data form original feature space to an other space.  The SVM used this space for training, which means its don't matter the dimension of original space.

I do know that the RBF kernel does not scale well with training samples or input feature dimensions, so I would assume unfavourable complexity would still hold in terms of input dimensions. But that's about the extent of my knowledge sorry!


text:
Is it possible to classify the subject of a conversation?
I would like to classify the subject of a conversation. I could classify each messages of the conversation, but I will loose some imformation because of related messages.
I also need to do it gradually and not at the end of the conversation.
I searched near recurrent neural network and connectionist classification but I'm not sure it answer really well my issue.

I think you are looking for "text summarization". Maybe take a look at this paper (although I haven't yet read it).

@nbro Summarisation is a different task: it usually selects salient sentences from a text, and would not work in a conversation.

@OliverMason Ok. I don't have experience with any "text summarization" technique, but aren't these techniques also able to summarise singles sentences, and don't they attempt to extract the important parts of the text anyway (which may be the subject of the conversation, assuming the text is a conversation)?

@nbro, thanks for the "text summarization". I've never heard about it. It's not really what I want, because i'm searching for a classification. But the idea is good and could be another aproach  to find the subject of a conversation without predifined labels.

Thank you very much for your help, all of you.
I finally find on the Internet key words : "Dialog act classification".
I don't know yet how to implement it, but it's a good start !

This is a difficult problem.
First, how do you define 'subject'? Do you have a (closed) lists of labels you want to assign? What about subjects that overlap, or don't occur in your list? What even is a subject? This is a non-trivial issue.
Second, and this is even harder, how do you want to recognise subjects? A simple solution could be using a list of associated keywords, but this is problematic as many words have multiple meanings, and words are not really a good indicator of a conversation topic in the first place.
Instead of jumping to an implementation method, be clear about how you want to tackle these two items first. Start by annotating a conversation transcript by hand. You will then get a feeling for the problems and possible solutions. After you have done this, you can think about how to get a machine to do it efficiently.
UPDATE: For a scheme to annotate the functions of lines within a conversation have a look at Francis & Hunston (1992) Analysing Everyday Conversation.  In Coulthard, M. (ed.) "Advances in Spoken Discourse Analysis". London: Routledge. pp.123-161.  This is more oriented towards linguistics, but might give you some ideas on how to proceed.

Hello @oliver-mason. Yes, subject is a set of labels. I didn't determinated them yet, but it will be the case. I read litterature about classifying texts. So it can be a good start to classify message from the converstation. But we could lack some information because message are interconnected. So my second idea is to concatenate all the message from a conversation to create a large text and classify it. What do you think about it ?

That wouldn't work; conversations are interleaved. Have a look at papers in Conversation Analysis, which discuss turn-taking etc.

Ok, thanks, I will look at Conversation Analysis.


text:
Is it legal to license and sell the output of a neural network that was trained on data that you don't own the license to?
Is it legal to license and sell the output of a neural network that was trained on data that you don't own the license to?  For example, suppose you trained WaveNet on a collection of popular music. Could you then sell the audio that the WaveNet produces? There are copyright restrictions on using samples to produce music, but the output of a generative neural network might not include any exact replicas from the training data, so it's not clear to me whether those laws apply.

I think you'll need to ask a lawyer. Intellectual copyright issues for music are far from trivial, and sometimes get decided counter to intuition.

Thanks for the pointer @RobbyGoetschalckx. I'm new to this space, and I'd assumed there would a lot of questions and common knowledge around this topic, but I can see why it might be nuanced.

Great question!!!  I'm glad you asked it here because it is fairly specialized.  I've posted a  comprehensive basic answer, and will likely come back to amend and clarify, so feel free to post any followups in comments.

Disclaimer: I am not an attorney and this does not constitute formal legal advice.

If the output is novel the copyright resides with the creator

In this case, almost certainly the human who utilizes the algorithm†.  There was a recent US patent case "Dabus" [U.S. Patent Application No.: 16/524,350] where the human programmers tried to claim an AI as an inventor, which was rejected by USPTO.  This is largely because an inventor is defined as a "natural person".  But it's an interesting challenge to the notion of inventorship and authorship.
An argument regarding output specifically as a salable commodity would be that most human creative endeavor is result of previous work that forms the basis for the novel arrangement of elements in the form of an original work.
Music is more specific because melodies are mathematical, and what are traditionally protected, although Blurred Lines case blurred this line, in that the ruling there was the production aspect, the "feel", was what was plagiarized.
And, in fact, algorithmic music generation, which is heavily utilized in pop music, depends on combinatorial functions producing novel sequences, not protected by prior copyright.
Samples are clear cut—it is excerpting from copyrighted work.  A wave form is then copyrightable, in that a work of recorded music is simply an arrangement of waveforms in some combination and sequence.
If the output is procedural, and a process that can be automated, that would enter the domain of patent law, utility patents specifically.
Design output would also be in the realm of design patents, which are specific/generalized arrangements of elements in products that are not processes.

A note on liability:
Law is a process, where precedent plays a major factor.  Because law uses natural language, there is ambiguity, and jurisprudence is the process of clarifying the meaning and application via challenges.  Especially when in uncharted territory "no one knows" until a case has been ruled on, and rulings can be challenged all the way up to the Supreme Court, which may or may not accept a suit.
Damages for copyright are 3x, but damages can be very hard to prove.  Intellectual Property litigation is also enormously expensive, thus unlikely to be pursued unless there is a potential financial benefit.  (The first step in any potential copyright violation is typically a "cease and desist" letter, with no legal action if acceded to. In a case such as "Blurred Lines", where there is significant financial return to the alleged infringer, the award or settlement presumably exceeds the cost of litigation.)
However, deep-pocket players can use litigation, or threat of litigation, to disincentivize competitors, and, if the target has limited resources, can produce the desired outcome regardless of the strength of the claim.  (It's not uncommon in law in general to file frivolous suits as a strategy, although there is typically a financial penalty  such as reimbursement of the defendant's legal fees if the suit is found to be frivolous and dismissed.) "Patent trolling" became so much of a problem before 2013, the entire philosophy of patentability, what is patentable, had to be revisited.

†Who has rights to an algorithmic process is also a legal question.
Software is patentable, being simply a type of computer, regardless of medium, but most software is not patented, and protected instead as "trade secrets" and via non-disclosure agreements.  (This may be due to the glacial pace of the patent process compared to the software development process, but also per the from the necessity of making patents public.  i.e. if Google patented their search algorithm, it would be an instruction manual on how to exploit it.)
Software is copyrightable as the specific lines of code.  Copyright naturally resides with the creator, but the process of copyright is be utilized to document the right against potential infringement.

Stanford did patent  the google page rank scheme https://patents.google.com/patent/US6285999B1 and https://patents.google.com/patent/US6754873B1  includes equations!

There may be a can of worms here: Rights inhere to the creator, but the creator is an algorithm, and legal rights can only be afforded to natural person.

The patents George posted are a good example of the type of novel software functions  one might want to patent, in that they are likely "basic patents" (patents subsequent patents build on.) In this case, the patent excludes competitors from using the identical process, where alternatives may be less efficient (greater Kolmogorov complexity.)

The first one US 6285999 has been cited by over 850 other subsequent patents or applications according to google patents.