Why is the stationary distribution independent of the initial state in the proof of the policy gradient theorem?

I think your doubt is completely reasonable. Probably there is an additional assumption that they (both Lilian Weng and Rich Sutton (pag.269)) do not make explicit in the proof and that is that your MDP is not only stationary, but also ergodic. A particular property of those systems is that the probability of eventually reaching a state $s$ from a starting point $s_0$ is 1. In such a case it is clear that $\eta(s)$ exists and is independent of any $s_0$ chosen.

Clearly, an MDP with block-diagonal transition matrix does not satisfy such an assumption since the starting point completely restricts those states you can reach in an infinite time.

What I do not understand is why Rich Sutton does mention ergodicity as a necessary condition in the case of a "continuing task", as opposed to "episodic tasks" (pag.275). For me, their proof requires this condition in both cases.

As an additional note, I also think that Lilian Weng does not really explain why we should buy that from the initial reasonable definition $J(\theta)=\sum_\mathcal S d^{\pi_\theta}(s)V^{\pi_\theta}(s)$ we should accept the much simpler one $J(\theta)=V^{\pi_\theta}(s_0)$. I guess the only reason is that the gradient of the initial expression does require to know the gradient of $d^{\pi_\theta}(s)$ and so you would be accepting the approximation:

$$\nabla_\theta J(\theta)=\nabla_\theta\left(\sum_\mathcal S d^{\pi_\theta}(s)V^{\pi_\theta}(s)\right)\approx\sum_\mathcal S d^{\pi_\theta}(s)\nabla_\theta V^{\pi_\theta}(s),$$

where the last term is just $\nabla_\theta V^{\pi_\theta}(s_0)$ under the ergodicity assumption.


Prove that in such cases, it is possible to ﬁnd an ERM hypothesis for $H_n$ in the unrealizable case in time $O(mnm^{O(n)})$

Here's a rough proof sketch that might be clearer, but is probably less precise, than the solution you already have.

We have a sequence of hypotheses classes, but the problem actually only asks us to consider a single class. A hypothesis class is a set of possible models for classification that differ only in a set of parameter values.
We are told that the algorithm for selecting a hypothesis from $H_n$ uses only $O(n)$ samples from the training set, and that using those samples, it takes the algorithm $O(n)$ to find the hypothesis that minimizes the empirical risk for the class, provided that the ERM minimizing hypothesis has an empirical risk of 0 (i.e. it is realizable).
Further, if we pick some hypothesis at random from the class, we are told that the cost of determining its exact empirical risk is $O(nm)$, where $m$ is the total size of the training set, and $n$ is just a parameter associated with this particular hypothesis class $H_n$.
Observer that, in the unrealizable case, we cannot use the algorithm to find the risk minimizing hypothesis (which, by 2, runs in O(n)). No other algorithm is mentioned, but we are also told (in 2) that the algorithm can construct a hypothesis from $O(n)$ datapoints in $O(n)$ time, even if no feasible hypothesis can be found for those $O(n)$ points.
Suppose we wanted to find the hypothesis with minimal risk via brute force. We could compute every subset of the training dataset that is of the size $O(n)$ that the algorithm may be able to use to construct a hypothesis in $O(n)$ time. There are $O(m^{O(n)})$ such subsets (e.g. $m*(m-1)/2$ possible pairs, $m*(m-1)*(m-2)/6$ possible triplets, etc.).
Since there are $O(m^{O(n)})$ possible subsets of size $O(n)$, and our algorithm can compute a candidate hypothesis in $O(n)$ time, it costs us $O(nm^{O(n)})$ to find all possible hypotheses that our algorithm can produce for this dataset.
Since it costs us $O(nm)$ time to compute the emperical risk of a hypothesis generated by this algorithm, we can minimize risk by computing risk for each of the $O(m^{O(n)})$ hypotheses we made in step 6, and then selecting the one with lowest empirical risk. This costs us $O(mnm^{O(n)})$ time total. Our total runtime is then the sum of the cost to generate the models in step 6, and the cost to evaluate them here in step 7: $O(mnm^{O(n)})+O(nm^{O(n)})$.
Since $O(mnm^{O(n)})+O(nm^{O(n)}) \in O(mnm^{O(n)})$, we have proven the desired bound on runtime.


Is A2C loss function taking smaller steps for larger mistakes?

So this question is due to a misunderstanding I had with how the loss function works in A2C.

Usually loss functions are always positives, but in A2C it can be negative as well. I thought that minimizing the loss function means moving it closer to zero, but in fact reducing the loss is indifferent to the sign of the loss value and is about making the loss value smaller.

In other words, the loss for 0.1 is smaller than the loss for 0.9 prediction for a disadvantageous action.

When the advantage is positive, $-log (p) * advantage$ will be smaller if $p$ is growing, and when the advantage is negative, $-log (p) * advantage$ will be smaller if $p$ is decreasing.


What is the effect of picking action deterministicly at inference with Policy Gradient Methods?

When evaluating the policy in an environment, what would be the effect of always picking the action that has the highest probability instead of sampling from the probability distribution?

Depends what you mean by "evaluating the policy". Unlike in value-based methods, such as Q learning, the policy in gradient methods is not implied by anything else, it is described directly by the probability density function that is being optimised.

Taking the maximum probability item will technically change the policy (unless you are already using deterministic policy gradient), and you would be evaluating a different but related policy to that found by your policy gradient.

However, in a standard MDP environment, and after at least some training, this should be a reasonable process that would give some indication of how well the agent is performing.

In some cases, the nature of the environment means the agent is relying on a stochastic policy. In some partially-observable scenarios it may be better to decide randomly - a simple example is a corridor that needs to be traversed, but where the state features don't give enough information to determine the true direction. A deterministic policy will not be able to traverse the corridor in both directions, but a stochastic policy will get through it both ways, eventually. Another example is in adversarial situations where another agent can learn your agent's policy (the classic version of that being Scissor/Paper/Stone where two ideal opposed agents would learn probability $\frac{1}{3}$ for each action according to Nash equilibrium)

If you don't think you have these special cases, then it should be OK to derive a deterministic policy from your policy gradient agent, and assess that. That's not quite the same as assessing the "learned policy", but is quite sensible to do once you think the agent has converged anyway, since it may still be selecting non-optimal actions at some low probability, and you could get closer to optimal behaviour by removing that.


Why are state-values alone not sufficient in determining a policy (without a model)?

why is it not possible to suggest a policy solely on the basis of state-values; why do we need state-action values?

A policy function takes state as an argument and returns an action $a = \pi(s)$, or it may return a probability distribution over actions $\mathbf{Pr}\{A_t=a|S_t=s \} =\pi(a|s)$.
In order to do this rationally, an agent needs to use the knowledge it has gained to select the best action. In value-based methods, the agent needs to identify the action that has the highest expected return. As an aside, whilst learning it may not take that action because it has decided to explore, but if it is not capable of even identifying a best action then there is no hope of it ever finding an optimal policy, and it cannot even perform $\epsilon$-greedy action selection, which is a very basic exploration approach.
If you use an action value estimate, then the agent can select the greedy action simply:
$$\pi(s) = \text{argmax}_a Q(s,a)$$
If you have state values, then the agent can select the greedy action directly only if it knows the model distribution $p(r,s'|s,a)$:
$$\pi(s) = \text{argmax}_a \sum_{r,s'}p(r,s'|s,a)(r + \gamma V(s'))$$
In other words, to find the best action to take the agent needs to look ahead a time step to find out what the distribution of next states would be following that action. If the only values the agent knows are state values, this is the only way the agent can determine the impact of any specific action.
Although there are alternatives to this specific equation, there is no alternative that does not use a model in some form. For instance, if you can simulate the environment, you could simulate taking each action in turn, and look over multiple simulation runs to see which choice ends up with the best $(r + \gamma V(s'))$ on average. That would be a type of planning, and perhaps the start of a more sophisticated approach such as MCTS. However, that simulation is a model - it needs access to the transition probabilities in some form in order to correctly run.
It is possible to have an entirely separate policy function that you train alongside a state value function. This is the basis of Actor-Critic methods, which make use of policy gradients to adjust the policy function, and one of the value-based methods, such as TD learning, to learn a value function that assists with calculating the updates to the policy function. In that case you would not be using a value-based method on its own, so the quote from that part of Sutton & Barto does not apply.


Has anyone thought about making a neural network ask questions, instead of only answering them?

Maybe neural networks are not the best tool for this.

It seems to me that an equivalent of the your notion of 'a question to help the classification' would be to use Machine Learning (ML) to obtain a human-readable ruleset which performs the classification. The idea is that, if you follow an applicable chain of rules all the way through to the end, you have a classifier, if you stop before that, you have an indicator of which features of the input give more coarse-grained classifications, which can be seen as a progressively detailed sequence of questions that 'help the classification'.

More detail on various options for using ML to create rulesets can be found in my answer to this question.


What is self-supervised learning in machine learning?

Introduction
The term self-supervised learning (SSL) has been used (sometimes differently) in different contexts and fields, such as representation learning [1], neural networks, robotics [2], natural language processing, and reinforcement learning. In all cases, the basic idea is to automatically generate some kind of supervisory signal to solve some task (typically, to learn representations of the data or to automatically label a dataset).
I will describe what SSL means more specifically in three contexts: representation learning, neural networks and robotics.
Representation learning
The term self-supervised learning has been widely used to refer to techniques that do not use human-annotated datasets to learn (visual) representations of the data (i.e. representation learning).
Example
In [1], two patches are randomly selected and cropped from an unlabelled image and the goal is to predict the relative position of the two patches. Of course, we have the relative position of the two patches once you have chosen them (i.e. we can keep track of their centers), so, in this case, this is the automatically generated supervisory signal. The idea is that, to solve this task (known as a pretext or auxiliary task in the literature [3, 4, 5, 6]), the neural network needs to learn features in the images. These learned representations can then be used to solve the so-called downstream tasks, i.e. the tasks you are interested in (e.g. object detection or semantic segmentation).
So, you first learn representations of the data (by SSL pre-training), then you can transfer these learned representations to solve a task that you actually want to solve, and you can do this by fine-tuning the neural network that contains the learned representations on a labeled (but smaller dataset), i.e. you can use SSL for transfer learning.
This example is similar to the example given in this other answer.
Neural networks
Some neural networks, for example, autoencoders (AE) [7] are sometimes called self-supervised learning tools. In fact, you can train AEs without images that have been manually labeled by a human. More concretely, consider a de-noising AE, whose goal is to reconstruct the original image when given a noisy version of it. During training, you actually have the original image, given that you have a dataset of uncorrupted images and you just corrupt these images with some noise, so you can calculate some kind of distance between the original image and the noisy one, where the original image is the supervisory signal. In this sense, AEs are self-supervised learning tools, but it's more common to say that AEs are unsupervised learning tools, so SSL has also been used to refer to unsupervised learning techniques.
Robotics
In [2], the training data is automatically but approximately labeled by finding and exploiting the relations or correlations between inputs coming from different sensor modalities (and this technique is called SSL by the authors). So, as opposed to representation learning or auto-encoders, in this case, an actual labeled dataset is produced automatically.
Example
Consider a robot that is equipped with a proximity sensor (which is a short-range sensor capable of detecting objects in front of the robot at short distances) and a camera (which is long-range sensor, but which does not provide a direct way of detecting objects). You can also assume that this robot is capable of performing odometry. An example of such a robot is Mighty Thymio.
Consider now the task of detecting objects in front of the robot at longer ranges than the range the proximity sensor allows. In general, we could train a CNN to achieve that. However, to train such CNN, in supervised learning, we would first need a labelled dataset, which contains labelled images (or videos), where the labels could e.g. be "object in the image" or "no object in the image". In supervised learning, this dataset would need to be manually labelled by a human, which clearly would require a lot of work.
To overcome this issue, we can use a self-supervised learning approach. In this example, the basic idea is to associate the output of the proximity sensors at a time step $t' > t$ with the output of the camera at time step $t$ (a smaller time step than $t'$).
More specifically, suppose that the robot is initially at coordinates $(x, y)$ (on the plane), at time step $t$. At this point, we still do not have enough info to label the output of the camera (at the same time step $t$). Suppose now that, at time $t'$, the robot is at position $(x', y')$. At time step $t'$, the output of the proximity sensor will e.g. be "object in front of the robot" or "no object in front of the robot". Without loss of generality, suppose that the output of the proximity sensor at $t' > t$ is "no object in front of the robot", then the label associated with the output of the camera (an image frame) at time $t$ will be "no object in front of the robot".


Is there a limit to the increase of intelligence?

Absolutely, regardless of how you define "intelligence".

If intelligence is merely information, as in "a piece of intelligence", as in data, or an algorithm, the structure is finite.  (Structure, here, refers to the information, which may be reduced to a single string in either case.)

See: Turning Machine.

If intelligence is the rational capability of an automata, it is likewise bounded by the tractability of the decision problem, the structure of the algorithm, and the time available to make the decision.

See: Bounded Rationality

Both answers are really the same, because "intelligence" in the first sense is limited by physical constraints on information density, sophistication of the algorithm, and time.

See also: Computational complexity of mathematical operations, Computational complexity, Time Complexity


Machine mathematical reasoning by clever substitutions, How to do with AI

What you're asking here is actually not reasoning but rather symbolic computation.  Sympy is an example of a library which does it.
Explaining computer algebra systems could be a series of lectures and this is too broad for a single question. To give you an idea: (1) represent equations symbolically (2) bring them in a normal form (3) substitute.
Although it is not elegant, you can simplify the problem by brute Force: try all combinations of solving for a variable and substituting it in the other equations.
Related:

How do symbolic math software work? | Mathematics Stack Exchange


What is the difference between logic-based and rule-based AI?

Rule-based systems cover a wide range of systems. Some make use of boolean if/then/else rules, others may use weighting or even probabilistic inference. Some operate on frames, some on java objects, some on propositions that can be formulated in predicate logic. An example of a popular rule system is Drools.
Some rule systems can be expressed as a subset of predicate logic. For example, SWRL is a W3C standard rule language that extends OWL Description Logic (DL) with horn rules. Both OWL-DL and SWRL are expressible in first-order predicate logic. However, not all rule languages are directly expressible in this way, as rule languages encompass such a range of semantics. Even in cases like Prolog, there are subtleties. Pure Prolog is a subset of FOL, but actual existing Prolog implementations are not FOL subsets (e.g. order of precedence matters).
The W3C Rules Interchange Format (RIF) working group has done a lot of work attempting to unify these different perspectives. I'm not sure the best place to start to see a summary, but you can see some useful material on the group charter page.


How to stop DQN Q function from increasing during learning?

You can use discount factor gamma less then one.
You can use finite time horizon - only for states which are no farther away then T time steps reward propagate back
You can use sum of rewords averaged over time for Q

All of those are legitimate approaches.


$Q$-learning (and also its deep variant, and most of the other well-known reinforcement learning algorithms) are inherently learning approaches for single-agent environments. The entire problem setting that these algorithms are developed for (Markov decision processes, or MDPs) is always framed in terms of a single agent situated in some environment, where that agent can take actions that have some level of influence over the states that they lead to, and rewards may be observed.
If you have a problem that is, in reality, a multi-agent environment, there is a way to translate this environment to a single-agent setting; you simply have to assume that all other agents (i.e. your opponent in Go) are an inherent part of "the world" or "the environment", and that all the states in which these other agents make moves are not really states (not visible to your agent), but just intermediate steps where these part-of-the-environment-agents cause the environment to change and, as a result, create state transitions.
The primary issue with this approach is; we still need to model the decision-making of these agents in order to implement this new view of "the world", where our opponents are really a part of the world. Whatever implementation we give them, that is what our single-agent RL algorithm will learn to play against. We can just implement our opponents to be random agents, and run a single-agent RL algorithm like DQN, and then we will likely learn to play well against random agents. We'll probably still be very bad against strong opponents though. If we want to use a single-agent RL algorithm to learn to play well against strong opponents, we need to have an implementation for those strong opponents first. But if we already have that... why even bother with learning at all? We've already got the strong Go player, so we're already done and don't need to learn!
MCTS is a tree search algorithm, one that actively takes into account the fact that there is an opponent with opposing goals, and tries to model the choices that this opponent can make, and can do so better the more computation time we give it. This algorithm, and learning approaches built around it, are inherently designed to tackle the multi-agent setting (with agents having opposing goals).


What is a non-starving policy in reinforcement learning?

A non-starving policy is a (behavior) policy that is theoretically guaranteed to visit each state and take all possible actions from each state an infinite number of times, so that to always update $Q(s, a)$, $\forall s, \forall a$, an infinite number of times. In the context of off-policy prediction, this criterion implies that any trajectory will have no zero probability under a behavior policy. As a consequence, the experience from the behavior policy sufficiently covers the possibilities of any target policy.

An example of a non-starving policy is the $\epsilon$-greedy policy, which, with $0 < \epsilon \leq 1$ (which is usually a small number between $0$ and $1$) probability, takes a random action from a given state, and, with $1-\epsilon$ probability, takes the current best action, that is, the action with the highest value from a given state, according to the current value function.


Which machine learning technique can I use to match one set of data points to another?

OK, so I found the answer - it is to use multiple linear regression. I think this can be marked a solved, but I don't have enough rep to do that.


How should I define the reward function in the case of Connect Four?

The classic working reward scheme for two player zero sum games (i.e. if I win, you lose and vice versa) is simply:

+1 for a win
0 for a draw
-1 for a loss

These rewards should be associated with the last move made by the player before the game is resolved.

  I thought about giving a negativ reward for the move played before the winning move.

That is what is normally done.

  Thinking about this I came to the conclusion that this is a bad idea. There'll be always a looser (except for ties), therefor there always be a last move from the loosing player. This one hasn't to be a bad one. Mistakes could have been made much earlier.

It's OK, what the agent is learning is the value of a combination of state and action. It will, eventually, correctly associate the negative reward with a chain of board states that decrease in value and that it will then try to avoid.

This scenario of delayed rewards, not necessarily related to the choice of the current action, is handled correctly by reinforcement learning algorithms. It is still a tough problem though - a more delayed and difficult to predict reward makes for a tougher RL problem. However, even basic learners, such as Q-learning, can eventually solve this.

To get better performance, you might want to look into adding planning algorithms to the RL part.


In short, it's possible to achieve occupation detection via face but it's highly doubtful that it can be done with Face API that you mentioned.

Now some details,

Face preception is a very complex job. You have so many parameters to consider before even beginning to design the model.

  Many different types of important information are visible in faces and
  the processes and mechanisms involved in extracting this information
  are complex and can be highly specialized.

and

  Face perception serves as the basis for much of human social exchange.
  Diverse information can be extracted about an individual from a single
  glance at their face, including their identity, emotional state, and
  direction of attention.

Extracting that much information is not easy.

Face API:

Face API gives you

Face Similarity (checks how similar two or more faces are)
Face Identification (gives you 27 landmarks like age, gender, facial hair, smile etc confidence level)
Emotion detection (check what kind of emotion the face has)

However, in my view, occupation detection via face will going to need a lot more than these basic parameters.

However, previous work utilizing single person’s nearly frontal clothing information and fore/background context preliminarily proves that occupation recognition is computationally feasible in computer vision.

However, in practice, multiple people with arbitrary poses are common in a photo, and recognizing their occupations is even more challenging.

You have to appropriately built visual attributes, co-occurrence, and spatial configuration model that is learned through structure SVM or deep neural nets to recognize multiple people’s occupations in a photo simultaneously.

I am attaching some research papers so you can review them to get more insight.

Reference Papers:

A Comparative View of Face Perception

The many faces of research on face perception

What Do You Do? Occupation Recognition in a Photo via Social Context

Note:

Please state your question clearly (like: tell us your problem in detail, and your approach to solve it), and also tell what research you have done before asking the question. Please see how much research effort is expected of stackoverflow users before they post any new questions.


Which is a better form of regularization: lasso (L1) or ridge (L2)?

The following graph shows the constraint region (green), along with contours for Residual sum of squares (red ellipse). These are iso-lines signifying that points on an ellipse have the same RSS.

Figure: Lasso (left) and Ridge (right) Constraints  [Source: Elements of Statistical Learning]
As Ridge regression has a circular constraint ($\beta_1^2 + \beta_2^2 <= d$) with no edges, the intersection will not occur on an axis, signifying that the ridge regression parameters will usually be  non-zero.
On the contrary, the Lasso constraint ($|\beta_1| + |\beta_2| <= d$) has corners at each of the axes, and so the ellipse will often intersect the constraint region at an axis. In 2D, such a scenario would result in one of the parameters to become zero whereas in higher dimensions, more of the parameter estimates may simultaneously reach zero.
This is a disadvantage of ridge regression, wherein the least important predictors never get eliminated, resulting in the final model to contain all predictor variables. For Lasso, the L1 penalty forces some parameters to be exactly equal to zero when $\lambda$ is large. This has a dimensionality reduction effect resulting in sparse models.
In cases where the number of predictors are small, L2 could be chosen over L1 as it constraints the coefficient norm retaining all predictor variables.


How do I create a custom gym environment based on an image?

The question is conceptually wrong, because of misunderstanding of area. Explanation: The idea is to replace open ai gym by something different. For example: web-site or computer game. There is no way to create an environment based on image. If you want to use implemented algorithm for open ai gym and want to change environment for your own, could do something like this: https://towardsdatascience.com/creating-a-custom-openai-gym-environment-for-stock-trading-be532be3910e. If need to change env complitely than it is necessary to rewrite your algorithm for your tasks.


Effects of translating RL action probability through non linearity

Have you considered using a continuous action space? It might be worth looking into. If you aren't familiar with it, here are a few resources for discrete vs continuous action spaces -

Modeling and Planning in Large State and Action Spaces

Deep Reinforcement Learning in Continuous Action Spaces:a Case Study in the Game of Simulated Curling


What is the expectation of an empirical model in model based RL?

If I understand your question correctly, the significance of this is due to the fact that $s'$ is random. In the RHS of the equation it is assumed that $V(\cdot)$ is known for each state, but the quantity is measuring the expected value of the next state given the current state and action.


Are there reinforcement learning algorithms that scale to large problems?

This is a big question. I'm not going to try to cover the state-of-the-art, but I'll try to cover some of the main ideas.

Function Approximation [1]
An essential strategy for scaling up RL algorithms is to reduce the effective size of your state and/or action space through function approximation. For example, you could parameterize your value function using fewer parameters than there are states. Optimization would then take place in the much smaller parameter space, which can be substantially faster. Note that using function approximation almost always loses you any convergence guarantees you would have had otherwise in the tabular setting. It has been very successful in practice, though.

Sampling[2]
Value iteration and other dynamic programming algorithms sweep through the entire state space when computing value functions. Sample-based approaches instead update value functions for states as they are visited. These include Monte Carlo and Temporal Difference methods. Sampling allows us to focus on a subset of the states, freeing us from the computation required to get accurate value estimates of potentially irrelevant states. This is essential in real-world settings, where almost all possible states of the world are irrelevant or even impossible to reach.

Sample Efficiency/Experience Replay
All else equal, a sample efficient agent is one that learns more with the same experience. Doing this reduces learning time, especially if the time bottleneck is in interacting with the environment. One basic way of improving sample efficiency is to store and reuse experience with something like the experience replay buffer popularized in the DQN paper. Another, more recent, algorithm called Hindsight Experience Replay improves sample efficiency by allowing the agent to learn more from its failures (trajectories with no reward).

Model-Based Methods[3]
While technically also about sample efficiency (maybe all of these points are?), model-based methods are important enough to warrant their own section. Usually, the MDP dynamics aren't known to the agent beforehand. Learning and maintaining an estimate of the MDP is therefore often a good idea. If an agent can use its internal model of the world to simulate experience, it can then learn from that simulated experience (called planning) in addition to learning from actual experience. Because simulated experience is much cheaper to gather than actual experience, this can reduce the time needed to learn.

Search[4]
If our value estimates were perfect, then behaving optimally would only be a matter of moving to the neighboring state with the highest value. This is hardly ever the case, though, so we would like to make decisions more intelligently. One way, called forward search, is to use a model to consider many possible trajectories starting from the current state. The most popular and successful example of forward search is Monte Carlo Tree Search (MCTS), which was famously used in AlphaGo Zero. Because search allows us to make better decisions given imperfect value estimates, we can focus on more promising trajectories, saving time and computation.

Exploration
Only ever taking what we think is the "best" action in a given state is usually not a very good idea. When sampling trajectories through large state and/or action spaces, this strategy can completely fail. Taking exploratory actions can help ensure that high-value states are discovered at all. Deciding when to explore and which actions to take is active area of research. In general, though, exploratory actions are ones that reduce an agent's uncertainty of the environment.

Injecting Human Knowledge
Finally, and maybe obviously, reducing the time complexity of an RL algorithm can be accomplished by giving the agent more information about the world. This can be done in many ways. If using linear function approximation, for example, an agent could be given useful information through the features it uses. If it makes use of a model, the model could be initialized with reasonable priors for the reward and transition probability distributions. "Reward shaping", the practice of manually engineering a (dense) reward function to facilitate learning a specific task, is a more general approach. An agent could also learn directly from human demonstrations with inverse reinforcement learning or imitation learning.

References
All references not already linked to are chapters out of Sutton and Barto's RL book.
[1] Linear function approximation is discussed in depth in Chapter 9.
[2] Monte Carlo and Temporal Difference methods are discussed in Chapters 5 and 6.
[3] Model-based methods are discussed in the first part of Chapter 8.
[4] MCTS and search in general are discussed in the second half of Chapter 8.


Are embeddings in multi-lingual language models comparable across languages?

Embeddings generated by transformers like Bert or XLM-R are fundamentally different from embeddings learned through language models like GloVe or Word2Vec.
The latter are static, i.e. they are just dictionaries containing a vocabulary with n-dimensional vectors associated to each word. Because of this they can be plotted through PCA and the distance between them can be easily calculate with whatever metrics you prefer.

When training Bert or XLM-R instead you are not learning vectors, but the parameters of a transformer. The embedding for each token are then generated once a token is fed into the transformer. This implies several things, the most important being that the hidden representation (the embedding) for the token change depending on the context (recall that XML-R use as input also the hidden states generated by the previous token). This means that there are no static vectors to compare by plotting them or by calculating the cosine similarity.
Nevertheless, there are way to analyse and visualise the syntax and semantics encoded in the parameters, this paper show some strategies: https://arxiv.org/pdf/1906.02715.pdf

On a more linguistic side, I would also ask why vectors of same words should show the same semantic properties across languages. Surely there are similarities for lot of words translated literally, but the use of some expressions is inherently different across languages. To make a quick example: in English the clock 'works', in Dutch the clock 'lopen' (it walks) and in Italian the clock 'funziona' (it functions). Same expression, three different words in different languages that do not necessarily share the same neighbours in their monolingual latent spaces.
The point of transformers is exactly to move from static representations to dynamic ones that are able to learn that all those three verbs (in their specific language) can appear early in a sentences and close to the word clock.


How parameter adjustment works in Gradient Descent?

Imagine we have the curve $f(x) = x^2$, and we want to find the minimum of this function. The derivate of $f$ with respect to $x$ is $2x$. Now, gradient descent works by updating our current estimate of the minimum, say $c_t$, by the following iterative process
$$c_{t+1} = c_t - \alpha \times \nabla_xf(x=c_t),$$
where $\alpha$ is some constant to control how much we shift towards the gradient.
Intuitively, this should make sense. Imagine our current estimate of the minimum is $c_t = -1$. The update would then give us $c_{t+1} = -1 - \alpha \times -2 = -1 + 2\alpha > -1$. As you can see, the update has shifted our estimate in the direction of the minimum. If our estimate were $+1$ then you can probably see that the update would again have shifted us in the direction of the minimum again.
Now, what happens in machine learning is we have a loss function $L$ that we typically want to find the minimum of in terms of the parameters of our model. By applying gradient descent on the loss function as we did above with $f(x)$ we iteratively apply the update rule which will eventually lead us to the minimum of our loss function with respect to the weights. The process is exactly the same as above except it is likely to happen in higher dimensions, where the derivative of $f$ becomes a vector of partial derivates. Note that whilst $w_i$'s are scalar values, we are not differentiating these values, rather we are differentiating the loss function with respect to these scalars.
I would recommend you to try this out with a simple linear model of maybe 2 or 3 parameters. After a quick Google I found this article that may be useful.


Is it a good idea to pay for an deep learning course?

It doesn't seem expensive at $399* (although the asterix needs to be taken into consideration.)

If you're interested in this subject, this may be a decent course, however it is certainly not an accredited institution, thus any "degree" you get from this course will be meaningless in an academic sense.  On the other hand, a certificate shows that you've committed resources toward training.

My high level take on this is that the "Foundation" is looking to capitalize on the recent publicity for Deep Learning, per the AlphaGo milestones.

One thing I can tell you for certain is that this field requires advanced mathematics from a research perspective, and people who work in that area spend years training to gain the requisite skills.

The requirements for this class seem to be restricted to "Python knowledge" with no mention of mathematics, which raises some alarm bells, although it's worth mentioning that once solutions/applications arise, they can be applied to varying degrees without having to understand the mathematics. [See mindcrime's comment]


Why don't people use projected Bellman error with deep neural networks?

I have found some clues in Maei's thesis (2011): “Gradient Temporal-Difference Learning Algorithms.”

According to the thesis:

GTD2 is a method that minimizes the projected Bellman error (MSPBE).
GTD2 is convergent in non-linear function approximation case (and off-policy).
GTD2 converges to a TD-fixed point (same point as semi-gradient TD).
GTD2 is slower to converge than usual semi-gradient TD.

  It doesn't readily apply to non-linear function approximation.

No, it does.

  It doesn't yield a good solution.

No, it does. TD-fixed point is the same point for the solution of semi-gradient TD (which is generally used). There is no edge on that.

The only explanation seems to be practical convergence rate.

To quote his words:

  Some of our empirical results suggest that gradient-TD method maybe slower than conventional TD methods on problems on which conventional TD methods are sound (that is, on-policy learning problems).


Relationship between Rewards and Q Value (Graph between Q(s, a) vs episodes)

TLDR;
The output of Q-value function will eventually saturate. Can't say when, but it will surely do.
Detailed Answer

if you don't have TD error

It meant, if I don't have logs of the error.

$Q(s, a)$ vs Episodes Graph

To understand, how $Q(s, a)$ behaves as the episodes increase.
I was under a wrong impression that, the $Q(s, a)$ will saturate around the values given by the reward function.
As evident from Loss vs Training Episodes Curve, we can see that loss (TD Error) is almost saturated.
However, $Q(s, a)$ vs training episodes curve is not saturated yet.

The only explanation for the above two graphs could be given as follows:
The target estimate ($r + \gamma Q(s', a')$) and $Q(s, a)$ are almost similar due to which, the error is quite low. But, $Q(s, a)$ is still nowhere near optimal value $Q^{*}(s, a)$.
Hence, I gave it another shot and made it run for twice training episodes i.e. 20000, and below are the results.
A nearly saturated loss

and a nearly saturating $Q(s, a)$.
.
Note that, the value of $Q(s, a)$ saturating is around 250 - 300 (will run it for more iterations) and it is nowhere around the reward values $ \in [-100, 35]$.
Hence, the $Q(s, a)$ vs episodes will saturate.


What is the maximum number of dichotomies in a square?

The number of dichotomies of 4 data points will clearly be $2^4 = 16$. According to these slides the definition of dichotomy in context of Statistical Learning is:

  Different ‘hypotheses’ over the finite set of $N$ input points.

Which basically means hypotheses with unique behaviours over the input points. Two or more different hypotheses can have same behaviour on the data points (consider the case of a square covering the $4$ data points, an even larger square will also cover the $4$ data points. Thus they are different hypotheses but have same behaviour) and hence emphasis on the term unique.

The proof of axis aligned squares having $\mathcal V \mathcal C$ dimension $3$ can be found here. It's pretty straightforward so I don't want to explain it here.


How to make a LSTM network to predict sequence only after input sequence is finished?

You should try an architecture with an encoder and a decoder. The encoder will consume all the data you give as in put and decoder will give out the series of output.


Can artificial intelligence create the next wonder material?

Artificial intelligence has already gotten to the point where machines are as good as humans at many tasks, and even outperform humans at several more. The general goal of AI is to improve machines to be as good or better than humans at a wide variety of tasks. There's no theoretical reason why materials science is any different; we may well someday have a machine that can out-think all human materials scientists. There's not much reason to suppose that humans will always reign supreme at any particular task (especially objective ones like science), so yes, it's entirely possible that the next "wonder material" will be invented by a machine.


What are some programming-oriented resources for reinforcement learning?

Arthur Juliani has some interesting Medium articles on reinforcement learning with TensorFlow backed up with code on GitHub.

Part 0 — Q-Learning Agents
Part 1 — Two-Armed Bandit
Part 1.5 — Contextual Bandits
Part 2 — Policy-Based Agents
Part 3 — Model-Based RL
Part 4 — Deep Q-Networks and Beyond
Part 5 — Visualizing an Agent’s Thoughts and Actions
Part 6 — Partial Observability and Deep Recurrent Q-Networks
Part 7 — Action-Selection Strategies for Exploration
Part 8 — Asynchronous Actor-Critic Agents (A3C)

As nbro pointed out Denny Britz has a good repository: https://github.com/dennybritz/reinforcement-learning
As you have seen with Sutton & Barto's book the code is mostly in Lisp.  Shangtong Zhang has replicated the code in Python: https://github.com/ShangtongZhang/reinforcement-learning-an-introduction
Sudharsan and Ravichandiran wrote a book "Hands-On Reinforcement Leraning with Python" which uses OpenAI Gym and TensorFlow.  You can find more information on the book along with their code repository at Hands-On Reinforcement Learning with Python


Is this dataset with only two features suitable for clustering with k-means?

One problem with clustering algorithms is that they will typically find you a solution, ie they will split your data set into clusters, but it will find you a structure even if there isn't one. Your data looks like it could consist of about 5 to 7 clusters, but it could equally well just be 2 or only 1.

What you need to do after the clustering is to assess the quality of the result. I recommend having a look at Finding Groups in Data by Kaufman & Rousseeuw. They discuss various clustering algorithms and also a procedure that works out how cohesive your clusters are. Though it is 30 years old, it is an excellent book on the topic.

You also have the issue of choosing a value for k in your clustering: I usually start with two, and increase it from there; at each step I compute the cohesion of the result using their method, until I get the best score. This is an objective way of finding a good value for k and usually a reasonable clustering result.

The ultimate test, of course, is then if looking at the result makes sense to you. No cluster algorithm can do that for you.


What are the available selection methods in genetic algorithms?

Overview
There are many selection operators (or methods) for evolutionary algorithms. These selection methods differ in the way they evaluate the individuals given their fitness or how they compute their fitness in the first place. Some selection operators select individuals deterministically, while others select them stochastically, which can prevent premature convergence, given that, for instance, in fitness proportionate selection (aka roulette wheel selection), a well-known selection operator, all individuals can be selected, although the fitter individuals have a higher probability of being selected. Each selection operator has different advantages and disadvantages compared to other selection operators.
All these details are covered from chapter 22 (p. 166 and 203 of the linked pdf) onwards of the well-written book Evolutionary Computation 1 Basic Algorithms and Operators by Thomas Bäck et al. These concepts are also described in Computational Intelligence: An Introduction (section 8.5, p. 135), in case you want to have an alternative reading.
For completeness, I will enumerate and briefly describe some of the well-known selection operators.
Fitness proportionate selection (FPS)
This selection method is also known as roulette wheel selection (RWS). In FPS, the probability of an individual being selected is proportional to its fitness. More precisely, let $f_i$ be the fitness of individual $i$, then the probability of that individual being selected is
$$p_{i}={\frac {f_{i}}{\Sigma _{j=1}^{N}f_{j}}}$$
FPS does not handle minimization problems directly and it requires the fitnesses to be non-negative (given that probabilities are in the range $[0, 1]$), but the minimization problem can be transformed into a maximization one. The solutions are thus selected probabilistically in this case. There are other problems/issues with this selection method, which are described in the cited book (chapter 23, p. 172).
Tournament selection (TS)
In TS, at each generation, a set/group $Q = \{ a_1, \dots, a_q \}$ of $|Q| = q$ individuals is sampled (with or without replacement) at random from the current population of all individuals $P$. Successively, this group $Q$ takes part in a so-called tournament, i.e. a loop of $\lambda$ iterations, where, for each iteration $j$, the individual from the group $Q$ with the highest fitness $a_1'$ is selected (deterministically or stochastically) and inserted in a new set $S$, which will contain the individuals that you will mutate and recombine. After this first iteration $j$, $S$ contains only one individual, $S = \{a_1' \}$. In the second iteration, we perform the same thing, and obtain $S = \{a_1', a_2' \}$, and so on. So, after $\lambda$ iterations, $S$ contains $\lambda$ individuals, i.e. $|S| = \lambda$. Note that $a_1'$ is not necessarily equal to $a_1 \in Q$. The individuals in $S$ are the ones that undergo mutation and cross-over in this generation. In the next generation, you repeat this tournament process for selecting the best $q$ individuals. Typically, you need to have at least $q = 2$ (i.e. binary tournament selection), so that you have the opportunity to choose 2 different individuals for the cross-over. If $q=1$, individuals are picked randomly from the population (given that you do not perform any tournament at all).
Rank-based selection (RS)
In RS, only the rank ordering of the individuals within the current population determines the probability of being selected. So, in RS, an individual has a probability of being selected not proportional to its fitness (as in FPS), but it is based on its rank (order) with respect to the other individuals. So, if the individual $a$ has is ranked $1$st and individual $b$ is ranked $2$nd, even if $a$ had a fitness a lot higher than individual $b$, then its probability of being selected would not be a lot higher than the probability of selecting $b$, while, in FPS, this would be the case. There are different ways of computing the rank, such as linear or non-linear. The details of how the rank can be computed are described in chapter 25 of the cited book.
Other selection methods

Boltzmann selection (chapter 26)
Soft brood selection (chapter 27)
Disruptive selection (chapter 27)
Competitive selection (chapter 27)
Truncation selection (chapter 29)

Other related concepts
There's also the related concept of elitism, where the best individuals of the current population are carried over to the next population/generation, and hall of fame, which is a data structure that stores the best individual for each generation.


Why are state transitions in MDPs probabilistic rather than deterministic?

Your understanding is right!

Using a probabilistic transition function allows the model to explore a bigger search space before making a decision. One of the most important use cases of MDP is in POS tagging in NLP using a Hidden Markov Model.

In case of a deterministic model, search space is limited by the number of transitions and hence at each step, a definite decision is made. This does not take into regard the possibility of relationship between the previous states, rather only deals with the current and next state. These model are good for solving a certain range of tasks like decision trees etc.

When it come to tasks such as weather prediction, there is significance to the historical weather data. In such cases, we cannot make use of a deterministic approach. You always predict the chance of rainfall etc.

This example can also be extended to predict the weather for future days


An (artificial) neural network (NN) can be described at different levels of detail, but, essentially, an NN is a data structure (or model), which behaves like a function: that is, it can receive one or more inputs and it produces one or more outputs.

Most of the NNs can be thought of as graph-like data structures that contain nodes which are connected by weighted edges, where some of the nodes are associated with the inputs and some of the nodes are associated with the outputs. The remaining nodes are often called "hidden nodes". However, there are NNs which might not be easily understood as a graph-like structure: for example, convolutional neural networks.

The number of nodes and the connections between them defines the architecture of the NN and, intuitively, its "expressivity", that is, the number or type of functions it can approximate. Each node in an NN often computes a "function" of its inputs: for example, it could sum the inputs.

The weights of the edges connecting the nodes can change, during a "learning or training phase", so that the NN produces the desired outputs given certain inputs. For example, we can train an NN to "approximate" the function $f(x) = x$. Thus, an NN is often described as a "function  approximator".

There are several algorithms that can be used to "train" an NN to approximate a desired (and often unknown) function. The most common one is based on an optimisation algorithm (like gradient descent) and the back-propagation algorithm. In order to approximate a function, an NN requires data, often in the form of pairs of inputs and outputs, $(x, y)$, where $x$ is the input and $y$ is the output of the function $f$ (that we want to approximate). Intuitively, after the learning phase, an NN that receives an input similar to $x$, denoted by $x'$, will then produce an output similar to $y$, $y'$.

There are a lot of tasks that can be thought of as functions. For example, the task of machine translation can be thought of as a function $f(x) = y$, where the input, $x$, is a sentence in one language (e.g. English) and the output, $y$, is a sentence in another language (e.g. Chinese). In this case, $f$ is unknown (to a lot of people), but an NN can still learn (from the data) an approximation of it. Therefore, NNs have wide applicability and are thus quite useful.


Which "assumptions" made about the state space are Russell and Norvig referring to in their book?

The complexity results depend very strongly on the assumptions made about the state space. The simplest model studied is a state space that has a single goal and is essentially a tree with reversible actions.

The assumptions are the following:

  The simplest model studied is a state space

  that has a single goal

  and is essentially a tree with reversible actions.


Would this relatively small dataset be enough to train a CNN?

It is somewhat risky to discuss data independently with your learning mechanism.  There is actually no such thing as good data or a good learner.  There is only data that is good WITH a particular learner.  That is even true of human intelligence after all the standardized education and testing done today.

There are also exceptional learners that find data to be good when most others fumble with it.

If by good data and deep learning you mean image sets that will lead to proper categorization of unsuspected images presented in production, your intuitive understanding of statistics can provide you with a general answer.  The images on which the deep learner develops its activation weights and meta-parameters to provide adequate production behavior must be representative of the range of images that will be found in the production feeds.

If you intended to do a study of men and women to determine if the old belief that women are more motivated by the prospect of love and men are more motivated by the prospect of sex, you wouldn't pick 43 men and 40,000 women for the study.  The study's value is limited by the lower of the two numbers.

You can train the network with the category frequencies you have, but some deep learners may capitalize fully on feature extraction for Indian Tigers and Hyenas but exhibit an unacceptable level mis-categorization of Zebras and Giraffes.

Returning to the concept above, the skew in category frequency can be accounted for by the deep learner.  It is theoretically possible to create an exceptional learner or one that is well attuned to this kind of frequency skew.  A simple approach is to develop a scheme that recognizes frequency skew and allocates additional computing resources to the training that focuses on the differentiation of similar animals with infrequent labeled training instances.

I don't recall who has done that, but I know it has been done.

There are several ways you can give extra attention to the infrequent categories manually in the code, but then it would be a less general solution and the resulting program would neither be an exceptional learner nor particularly reusable.

It is more cost effective to hunt for a skew resistant deep learning scheme and test its accuracy for infrequent animals than sending a photographer to Africa.  If you can find more images of the less frequent animals without a monumental effort, I would do that too.


What are the main algorithms used in computer vision?

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


Is my approach to building an RNN to predict the probability that the word is in English appropriate?

while using a neural network for this type of problem is not the ideal use-case, it is a good exercise.
In terms of conceptual issues, the most concerning that I see is the loss: $\sum_{i=1}^N L_i$.
First issue, is that it validates loss at each time step equivalently. This is probably not ideal because in the example (cat), we dont expect it to know its English from just c or ca, but at cat. The quickest fix and probably the best, is to just use $L = L_N$. Though an argument would be that the model should become more and more aware as it gets more letters, and this loss function doesnt achieve that, so another solution would be to add another fixed parameter that you can play with: $L = \sum_i r^{-i}L_i$ where $0 \lt r \lt 1$. Note that $r^{-i}$ can be replaced with any function that increases in size.
Another issue with the loss is it doesnt normalize, meaning on average, larger words will hold more weight to the model than smaller ones, while this may be intended it should be noted and considered (also note if you do end up going with $L=L_N$ this will no longer be a concern.
Hope this helps


How can an AI system develop its domain knowledge? Is there more than just Machine Learning?

Well, we are talking about a system (a machine) which develops knowledge (learns), so it is kind of difficult for such a technique to not fall within machine learning.

But you could argue that inference engines which work on a graph based knowledge database to derive new propositions or probabilities are not part of machine learning. Of course in that case part of the knowledge is not acquired at all, but rather entered by the developers.

I'm still reading up on this, but my impression is that these knowledge databases and inference engines became rather popular in the nineties and many AGI-researchers today still work in that direction.


Combining machine learning with languages like ProLog?

In reference to your exact question there is published research that attempts to bring these two areas together.

“HolStep: A Machine Learning Dataset for Higher-order Logic Theorem Proving” by Cezary Kaliszyk, François Chollet, Christian Szegedy (2017)
https://arxiv.org/abs/1703.00426

That group also has other published work related to the subject.

Regardless of their results they list several areas of logical systems that are highly suited to machine learning methods:

• Predicting whether a statement is useful in the proof of a given conjecture

• Predicting the dependencies of a proof statement (premise selection)

• Predicting whether a statement is an important one (human named)

• Predicting which conjecture a particular intermediate statement originates from

• Predicting the name given to a statement

• Generating intermediate statements useful in the proof of a given conjecture

• Generating the conjecture the current proof will lead to

It’s tough to know whether or not you can combine Higher Order Logic and Machine Learning in an effective way without needing to create a general AI. This is equivalent to wondering if an effective merging of the two areas is an AI-complete / AI-hard problem.

There are active attempts at general AI by researchers such as Ben Goertzel (many others as well but just to give a popular name for googling). Research into general AI would give you an idea of whether or not other pieces of the puzzle are needed in order to create something “highly intelligent”.


How do we test if an model or algorithm is AI-complete?

According to the Wikipedia definition, a problem is said to be AI-complete if it requires generalized, human-level intelligence, that is, requires strong AI. The Turing test and its variants are the best ways we have of measuring this. See, for example, Turing Test as a Defining Feature of AI-Completeness.

As suggested in this paper, in order for the Turing test to be meaningful, the interrogator has a responsibility to ask questions which are both deep and meaningful.

It, therefore, seems likely that testing for strong AI is in itself an AI-complete task.


What kind of functions can be used as activation functions?

Not completely sure your question. Do you mean

Q. why should we use activation function?

Ans: we need to introduce non-linearity to the network. Otherwise, multiple layers are no difference from single layer network. (It is obvious as we write things in matrix form, and say when we have two layers with weights $W_1$ and $W_2$, the two layer is no difference from a single layer with weight $W_2 W_1$.

Q. why they need to be differentiable?

Ans: Just for sake that we can back-propagate gradients back to earlier layers. Note that back-propagation is nothing but the chain rule in calculus. Say $f(\cdot)$ is an activation function in one layer and the output of that activation function is $\bf y$ and the input is ${\bf u}=W \bf x$, where $\bf x$ is output from the previous layer and mix with weights $W$ in current layer. Of course, the final loss $L$ will depend on ${\bf y} = f({\bf u})= f(W {\bf x})$. Say, loss $L=g(\bf y)$ somehow. To train the weights $W$, we have to find the gradient $\frac{\partial L}{\partial W}$ so that we can adjust weight $W$ to minimize $L$. But $\frac{\partial L}{\partial W}=\frac{\partial g({\bf y})}{\partial W}=\frac{\partial g({\bf y})}{\partial \bf y}\frac{\partial {\bf y}}{\partial {\bf u}}\frac{\partial {\bf u}}{\partial W}$. Each of these product terms can be computed locally and will be accumulatively multiplied as we apply backprop.  And note that the middle term $\frac{\partial {\bf y}}{\partial {\bf u}}=\frac{\partial f({\bf u})}{\partial {\bf u}}$ is just "derivative" of $f(\cdot)$, thus we require the activation function to be differentiable and "informative"/non-zero (at least most of the time). Note that ReLU is not differentiable everywhere and that is why researchers (at least Yoshua Bengio) worried about that when they first tried to adopt ReLU. You may check out the interview of Bengio by Andrew Ng for that.

Q. why step function is a bad activation function?

Ans: Note that step function is differentiable almost everywhere but is not "informative" though. For places (flat region) where it is differentiable, the derivative is simply zero. Consequently, any later layer gradient (information) will get cut off as it passes through a step function activation function.


Why did "Artificial Intelligence" stay intact as a coherent, unified field of study?

AI is a rather unusual research field in that the label persists more because it represents a highly desired goal, rather than (as with most other fields) the means, substrate or methodology by which that goal is achieved.

  we still talk of AI as a unified, coherent field of study

Despite recent efforts in AGI, I don't think that AI is actually a very unified or coherent field. This is not necessarily a bad thing - when attempting to mimic the most complex phenomenon known to us (i.e. human intelligence) then multiple, sometimes seemingly conflicting perspectives may be our best way of making progress.


What are some conferences for publishing papers on graph convolutional networks?

Based on past publications, here are some journals and conferences where you can possibly publish or present a research paper on geometric deep learning or graph neural networks

Neural Information Processing Systems (NIPS)
International Conference on Learning Representations (ICLR)
Conference on Computer Vision and Pattern Recognition (CVPR)
International Conference on Machine Learning (ICML)

The website http://geometricdeeplearning.com/ also provides some information about the topic and links you to several workshops, papers, and tutorials.

Here are some links to some of the past workshops on GDL.

Representation Learning on Graphs and Manifolds (and the related homepage)
Workshop IV: Deep Geometric Learning of Big Data and Applications
Geometric Deep Learning on Graphs and Manifolds.


How likely is it that Watson-like AI will replace Wikipedia-like encyclopedias?

I get the impression that (perhaps even more than Bluemix) this is what the Wolfram Language is looking to offer in the longer term.

Seems to me that the main pros and cons are two sides of the same coin:

With Wikipedia, there's no 'search filter' between you and the text. Adding an algorithmic level of indirection between the user and the knowledge that they're looking for is subject to hidden biases.

If those biases are intended in your best interests, and the search is context-sensitive enough to present you with information in the form that is most useful and digestible to you, then this is a good thing. Otherwise, not. Like many topics in AI, problems arise because we're simply not that good at modelling human context yet.

Of course, we're already subject to this filter bubble effect via search engines and social media. The current consensus seems to be that even more of this would not be a good thing for society.


Why don't ELUs multiply the linear portion by α?

Probably not worth the hassle.

I guess that simply nobody cares. I'm all for having my function be differentiable at all points, but I don't think that having a single jump in the derivative matters much. The neuron basically either repeats its input (x>0) or outputs nearly nothing (x<0) and the point in between is not that important.

Replacing

ELU(x) = x > 0 ? x : α * (exp(x) - 1)

by your proposal

ELU(x) = x > 0 ? α * x : α * (exp(x) - 1)

would have far more consequences. For example, after n layers, the output would get multiplied by α**n, assuming all x on the path being positive. This could be countered by dividing each weight by α, but the derivatives would change. You surely could adjust everything (initial rates, learn rate and whatever), so it'd work as usual, but it could laborious, especially when testing multiple learning algorithms.

I'd suggest to use

ELU(x) = x > 0 ? x : α * (exp(x/α) - 1)

instead, as it just changes the less important part of the curve.

  Or did they not bother, because α=1 is definitely the hyperparameter to use?

I can imagine that everyone tried α=1 and was happy with it. It prevented the gradient from being zero and that's it.

I don't have any support of my claim (having never read about something doesn't mean that it doesn't get written about).


What are some datasets to train an MLP on simple tasks?

There are a ton of sample datasets our there you can play with. A bunch of good ones install with R in the datasets package.  Luckily you can download them independently if you're not an R user.  Try  https://vincentarelbundock.github.io/Rdatasets/datasets.html

You might also be interested in the MNIST database which is one of the canonical databases used in handwriting recognition research.

Beyond that, you can look at / ask on http://datasets.reddit.com and/or http://opendata.reddit.com and you'll find all sorts of useful datasets.

And finally, don't overlook the UCI Machine Learning Repository.


Is it possible to have a fixed trajectory size in the vanilla policy gradient algorithm?

Trajectory size can be fixed, but in this case problem would be formulated as something similar to the multi-armed bandit problem where there is a single state and a set of actions to choose from. There is no sequential decision making since samples are not correlated, they are picked at random. So, if you take a batch of 20 examples then you would basically have 20 single state trajectories. For each of those trajectories you can calculate policy gradient and average it over the batch size (which would be 20 in this case).


GraphSage does not have attention at all. Yes, it randomly samples (not  most important as you claim) a subset of neighbors, but it does not compute attention score for each neighbor.


Why some neural network models in the 1980s shown as circuit models

In the early days of neural networks the theorists and practitioners were educated in mathematics, psychology, neurophysiology, electrical engineering, and neurobiology. Computer science was still in its infancy. The first neural networks were modeled as electrical circuits.
There is evidence of this in the 1943 paper by Warren McCulloch and Walter Pitts [1], and a 1956 paper by Rochester et al. [2].
The latter paper uses terms such as 'circuits' and 'switching'.  One idea in the paper is explained in terms of a "Eccles-Jordan Flip Flop circuit" although there are no drawings.  Nathanial Rochester had designed the IBM 701k [3] and "led the first effort to simulate a neural network" [4]
Brain structure was discussed in terms of 'neural circuits' as early as 1937 [5].
I am not sure when the first electrical circuit diagram appeared in publication, but it makes sense that early neural network designers, would have thought of their implementation as such.
References:

[1] McCulloch, W. S., and Walter Pitts, W. (1943) A Logical Calculus of the Ideas Immanent in Nervous Activity. https://jontalle.web.engr.illinois.edu/uploads/498-NS.21/McCulloch-Pitts-1943-neural-networks-ocr.pdf
[2] Rochester, N., Holland, J., Haibt, L., & Duda, W. (1956). Tests on a cell assembly theory of the action of the brain, using a large digital computer. IRE Transactions on Information Theory, Information Theory, IRE Transactions on, IRE Trans. Inf. Theory, 2(3), 80–93. https://doi-org/10.1109/TIT.1956.1056810
[3] Brief History of Neural Networks
https://www.linkedin.com/pulse/data-science-term-neural-networks-70-year-old-anchit-sharma/?trk=public_profile_article_view
[4] This Data Science term - Neural Networks is 70-Year-Old Technology!
https://medium.com/analytics-vidhya/brief-history-of-neural-networks-44c2bf72eec:
[5] Papez circuit, https://en.wikipedia.org/wiki/Papez_circuit


How do I choose the best algorithm for a board game like checkers?

tl;dr:

None of these algorithms are practical for modern work, but they are good places to start pedagogically.
You should always prefer to use Alpha-Beta pruning over bare minimax search.
You should prefer to use some form of heuristic guided search if you can come up with a useful heuristic. Coming up with a useful heuristic usually requires a lot of domain knowledge.
You should prefer to use Monte Carlo Tree search when you lack a good heuristic, when computational resources are limited, and when mistakes will not have outsize real-world consequences.

More Details:

In minimax search, we do not attempt to be very clever. We just use a standard dynamic programming approach. It is easy to figure out the value of difference moves if we're close to the end of the game (since the game will end in the next move, we don't have to look very far ahead). Similarly, if we know what our opponent will do in the last move of the game, it's easy to figure out what we should do in the second last move. Effectively we can treat the second last move as the last move of a shorter game. We can then repeat this process. Using this approach is certain to uncover the best strategies in a standard extensive-form game, but will require us to consider every possible move, which is infeasible for all but the simplest games.

Alpha-Beta pruning is a strict improvement on Minimax search. It makes use of the fact that some moves are obviously worse than others. For example, in chess, I need not consider any move that would give you the opportunity to put me in checkmate, even if you could do other things from that position. Once I see that a move might lead to a lose, I'm not going to bother thinking about what else might happen from that point. I'll go look at other things. This algorithm is also certain to yield the correct result, and is faster, but still must consider most of the moves in practice.

There are two common ways you can get around the extreme computational cost of solving these kinds of games exactly:

Use a Heuristic (A* search is the usual algorithm for pedagogical purposes, but Quiescence search is a similar idea in 2 player games). This is just a function that gives an estimate of the value of a state of the game. Instead of considering all the moves in a game, you can just consider moves out to some finite distance ahead, and then use the value of the heuristic to judge the value of the states you reached. If your heuristic is consistent (essentially: if it always overestimates the quality of states), then this will still yield the correct answer, but with enormous speedups in practice.
Use Rollouts (like Monte Carlo Tree Search). Basically, instead of considering every move, run a few thousand simulated games between players acting randomly (this is faster than considering all possible moves). Assign a value to states equal to the average win rate of games starting from it. This may not yield the correct answer, but in some kinds of games, it performs reliably. It is often used as an extension of more exact techniques, rather than being used on its own.


Is there a formal name for this philosophical AI problem?

If something is indistinguishable from a human it is as intelligent as a human. There is no such thing as simulated intelligence.

Consciousness of course is a different matter and I suspect that's what you really have in mind (no pun intended).

The question how to distinguish somebody who is truly conscious from somebody who just acts outwardly like a conscious being is often discussed under the term philosophical zombie.


What kind of road and weather conditions can a self-driving car deal with?

No, smart cars do not know what to do when surrounded with ducks or flood waters, and it's possible they never will.

As with all machine learning, a computer knows only what it's taught.  If an event arises that's unusual, the AI will have less relevant training on how to respond, so its reaction behavior necessarily will be inferior to its routine "standard operating procedure", for which is has been heavily trained.  (Of course this is true of humans too.)

Due to liability concerns, when encountering an outlier condition, smart cars will almost certainly be designed by their makers to immediately pull off the road and wait to be explicitly told what to do -- by the human in the car or by communicating with a central command office that exists to disambiguate such confusion and resolve cognitive impasses.  When confused, just like a child, a smart car will be designed to seek external assistance -- and is likely to do so indefinitely, I suspect.

That's why, despite Google's recent cars that lack steering wheels, smart cars most certtainly will retain some means of manual control -- be it a wheel and pedals, or at least verbal commands.  Given the many forms of weirdness that are possible on the road, it's possible smart cars will never be fully autonomous.

As for bad weather conditions, how well do smart cars currently perform?  Nobody outside of a car manufacturer can say for certain.  Lidar and radar are superior to the human eye in seeing through fog and snow.  But (competent) humans are likely to remain better than a smart car at dynamically learning the limit of adhesion and compensating (since this is a learned skill few smart cars will already know or can learn quickly -- given this car, these tires, this road surface, this angle of road, etc).

Initially smart cars will turn to the human when the going gets rough, ceding control back to them.  Once smart cars have driven a few million miles in snow, slush, high wind, floods, and ice, and encountered many ducks, angry mooses, and irate pedestrians, they will have been taught to do more for themselves.  Until then, and perhaps for decades yet, I suspect they will turn to mommy and ask for help.


Yes you can vectorize a CNN. See this github file for details: https://github.com/parasdahal/deepnet/blob/master/deepnet/layers.py

After looking through it it basically transposes the input to some dimension and apply matrix multiplication to the weight with some other kind of transfromation. Pls refer to the github repository for details.

Hope this can help you and have a nice day!


Does a data structure that models the encoding specificity principle in memory exist?

Beyond the basic requirement of storage, it seems you are looking for some explicitly defined data organization providing a query interface which allows specifying, alongside the fundamental query params,
a context and is able to use both these information items (instead of the first one only) to boost the query.

If this interpretation of mine is correct, the context-aware query database comes to my mind, here are some examples:

Context-Aware Query Classification

  In this paper, we propose a logical model and an abstract query language as a foundation of context-aware database management systems. The model is a natural extension of the relational model in which contexts are first class citizens and can be described at different levels of granularity.

Querying Context-Aware Databases


I think you would be interested in Neural-Symbolic Learning and Reasoning, a recent survey on the intersection between connectionist models (e.g. neural nets) and symbolic reasoning. It's a long paper, but it has a lot in it that is relevant to your question, if you're willing to dig. For example, it talks about learning networks that implement boolean logic.

  This
  network searches for satisfying solutions for the weighted conjunctive normal form (CNF):$\text{(¬X ∨ ¬Y ∨ Z) ∧ (X ∨ Y )}$.

The closest thing I could find to the "functionals" you mentioned was a discussion on learning "relations" with neural networks. For this, it cited Neural-Symbolic Cognitive Reasoning, a book also about the intersection between neural networks and symbolic reasoning. In Chapter 10, it gives the example of teaching a neural network to learn the relation of "grandparent."

  Our goal is to learn a description of grandparent from examples of the father, mother, and grandparent relations such as father(charles, william), mother(elisabeth, charles), and grandparent(elisabeth, william).

I could imagine something like this being done with the example inputs being image features from a CNN. Perhaps then you could start learning functionals like "on the shirt."


Is it possible that every class has a higher recall than precision for multi-class classification?

In the case of binary classification, i.e. when you have two classes $A$ and $B$, the recall is defined as
$${\displaystyle {\text{Recall}}={\frac {tp}{tp+fn}}}$$
Similarly, the precision as
$${\displaystyle {\text{Precision}}={\frac {tp}{tp+fp}}}$$
where, if you choose and fix a class $A$ as your main class (or class of interest),

$tp$ is the number of true positives (i.e. the number of observations that have been classified as $A$ and actually belong to class $A$, i.e. they have been correctly classified)

$fn$ is the number of false negatives (i.e. the number of observations that have been incorrectly classified as $B$, so, in this case of binary classification, they actually belong to class $A$)

$fp$ is the number of false positives (i.e. the number of observations that have been incorrectly classified as $A$)

In this context, the confusion matrix will be a $2 \times 2$ matrix because you have two predictions (one for each of the two classes) compared against the two ground-truth labels (or classes).
In the context of multi-class classification, where you have $N > 2$ classes, you will have a $N \times N$ confusion matrix, for the same reason. In this case, the recall and precision are just an extension of the binary classification problem. More precisely, let $M$ represent your confusion matrix, so $M_{ij}$ is the entry of this confusion matrix at row $i$ and column $j$. Then the recall, for class $i$ (i.e. your main class, as $A$ above), is defined as
$$\text{Recall}_{~i} = \cfrac{M_{ii}}{\sum_j M_{ij}}$$
$$\text{Precision}_{~i} = \cfrac{M_{ii}}{\sum_j M_{ji}}$$
In other words, the recall for a certain class $i$ is computed as the fraction of the diagonal element $M_{ii}$ and the sum of all elements in that row $i$. Similarly, the precision is computed as the fraction of $M_{ii}$ and the sum of all elements in column $i$.
If the true positives (i.e. the diagonal elements $M_{ii}$) of all classes are indeed bigger compared to the denominator, the recall can indeed be bigger than the precision for all classes.


What are the strengths of the Hierarchical Temporal Memory model compared to competing models?

IMO, the greatest "strength" of HTM is that it is modeled after the human neocortex, which is the most intelligent thing we know of.

But to understand the importance of this simple idea one must contrast it with the most familiar form of AI - Neural Networks (NNs).

Traditional Neural Network AI has been under development for a long time and has many more people working on it than HTM. NNs are capable of performing a bewildering number of tasks, and the list of its accomplishments grows with every passing day.

However, NNs are not thinking. They perform their magic only after being trained on (typically) massive amounts of training data. Training a NN is essentially an advanced form of curve-fitting. If your training data encompasses closely enough what it encounters in new data then it will likely perform very well. However, if it encounters something new (which is sometimes difficult to know beforehand) then it can fail abysmally, and often in a way that humans would never fail.

One example I heard about was on a NN trained on millions of images that could briefly describe what was in new images it had never seen before. It performed fabulously - something like 95-97% accuracy. However, when it was shown an image of a baby holding a toothbrush, it said, "A boy holding a baseball bat." This is not a human-like error. Humans know the difference between a boy and a baby, and a bat and a toothbrush. This is just an example, but it reveals a fundamental problem of NNs - they are not thinking. Useful? Yes. Thinking? No.

Back to HTM. HTM is new and currently has only a handful of researchers working on it. It is "better" than NNs in only a small number of cases - it has a long way to go.

So if by "strengths" you're thinking about what tasks can currently be done better with HTM than with NNs, then most people should still chose NNs.

However, if by "strengths" you're thinking about what has the best chance of achieving general intelligence someday, then I would say hands-down it is HTM.


DQN exploration strategy for large grid-world environment

What does your Q-network look like?

If you're using Convolutional Neural Networks (CNNs), I would advise against using pooling layers since the spatial translation data matters in this application (i.e. a cell with '1' top right of the agent is not the same as a cell with '1' below).

  1) How I might encourage exploration that will not always "cancel out" to only explore a very local region to my starting location?

This is referred to as exploration vs exploitation dilemma.

One way to add tackle this is by adding extra logic to the way you're choosing random actions. To elaborate, the chosen random action shouldn't be the same as the opposite of the previous action: if the agent went LEFT, the next random shouldn't be RIGHT as that is not exploring.

Another method is to use different action selection strategies such as Boltzmann Policy rather than epsilon-greedy. Click here for a quick crash course on the mainstream strategies by Arthur Juliani.

  2) Is this approach a good way to accomplish this task (assuming I want to use RL)?

RL is well suited for this application. Try different parameters for your network. I'd start with a small network and add more layers/neurons as necessary if it does not converge. However, keep in mind that it might take a while (hours or days) to converge so don't get hasty.

  3) I would think that attempting to work with a "continuous" action space (model outputs indexes of "1" elements) would be more difficult to achieve convergence. Is it wise to always try to use discrete action spaces?

I'm not sure I fully understand your question. Mind elaborating? What do you mean by the indexes of "1" elements that the model outputs?


How can I deal with images of variable dimensions when doing image segmentation?

There are 2 problems you might face.

Your neural net (in this case convolutional neural net) cannot physically accept images of different resolutions. This is usually the case if one has fully-connected layers, however, if the network is fully-convolutional, then it should be able to accept images of any dimension. Fully-convolutional implies that it doesn't contain fully-connected layers, but only convolutional, max-pooling, and batch normalization layers all of which are invariant to the size of the image.

Exactly this approach was proposed in this ground-breaking paper Fully Convolutional Networks for Semantic Segmentation. Keep in mind that their architecture and training methods might be slightly outdated by now. A similar approach was used in widely used U-Net: Convolutional Networks for Biomedical Image Segmentation, and many other architectures for object detection, pose estimation, and segmentation.
Convolutional neural nets are not scale-invariant. For example, if one trains on the cats of the same size in pixels on images of a fixed resolution, the net would fail on images of smaller or larger sizes of cats. In order to overcome this problem, I know of two methods (might be more in the literature):

multi-scale training of images of different sizes in fully-convolutional nets in order to make the model more robust to changes in scale; and
having multi-scale architecture.

A place to start is to look at these two notable papers: Feature Pyramid Networks for Object Detection and High-Resolution Representations for Labeling Pixels and Regions.


Is the play of strong Chess AI easily distinguishable from human play?

There are three cases in which it is easily possible to distinguish strong AI play from the strong human play:

The AI is playing at superhuman skill level

This seems obvious, but I want to mention it for the sake of completeness. The current skill ceiling of top-level chess is well known and an opponent playing way above this skill ceiling must either be an AI or a chess guru who hid in a cave for the last centuries. Applying Occam's razor I would go with the AI. So to mimic human play the AI must make sure to stay at a human ELO level.

The AI plays an obvious weak move in a losing or strange situation

When the AI is in a bad situation and still tries to win the game without any reasonable move available, it might be tempted to play an obviously bad move, because the decision engine assigns it the highest probability of success. Such moves are considered rude at high-level play and a human player would not play them but resign. The most famous example of this is move 101 in the fourth game between Lee Sedol and AlphaGo. AlphaGo just lost a big group but still played T9 to extend it even further. This is a move a rookie player stops making after his first 10 games because it is that obvious that it does not work. A professional go player would never do this under normal circumstances. AlphaGo was out of options and played the rude move instead of resigning. This doesn't mean an AI cannot be programmed to avoid such behavior, but dire or simply very strange situations might induce moves like this, giving the nature of the AI away.

Other factors than the actual moves are considered

Depending on the test scenario, the AI might give away its nature through other means than the actual moves. Things like moving too fast or playing without breaks for hours. But I assume the question was just focused on the actual play and not the surrounding factors.
Those are the obvious examples where an AI might give away his true nature. I highly doubt that a strong AI, playing at the strong human level, can really be identified because of his "inhuman" style. I think it is more of a psychological pitfall to consider innovative moves from an AI "inhuman" and the same move from a pro player as "brilliant" if you know who is who. I am an amateur 3dan Go player - far from the top but with several years of experience under the belt - and at least I wasn't able to see anything "inhuman" in AlphaGos play so far. Ingo, it is well known that there are different styles of play, and after reviewing enough pro games one gets a sense of which player might have been educated in Korea, China, or Japan because certain patterns of strategies are more or less common in those countries. The lack of such an individual nuance might be an indication, that the player is actually a strong AI, but I am confident, that even the strongest pro wouldn't have a high success rate guessing who is human and who is the AI.
In chess, there are significantly fewer options at every move, many fixed patterns especially in the opening, and therefore less room for an individual style. Therefore I consider the same challenge even more difficult than in go. So if an AI has reason to "play like a human", this should be possible with the current level of AI technology.


What is the weight matrix in self-attention?

The answer is actually really simple: they are all randomly initialised. So they are to all intents and purposes "normal" weights of a neural network.
This is also the reason why in the original paper the authors tested several setting with single and multiple attention heads. If these matrices were somehow "special" or predetermined they would all serve the same purpose. Instead, because of their random initialisation, each attention head learn to contribute to solve a different task, like they show in Figure 3 and 4.


Given statements $A$ and $B$, are the formulae $(\lnot A) \land (\lnot B)$ and $(\lnot A) \lor (\lnot B)$ equivalent?

One way of verifying whether two boolean expressions are equivalent is to assign all possibilities to all variables, and comparing all results.

A
B
f1
f2

T
T
F
F

T
F
F
T

F
T
F
T

F
F
T
T

We can see (F, F, F, T) does not equal (F, T, T, T), for example for the assignment (A, B) = (T, F) we get result (f1, f2) = (F, T) , meaning f1 != f2.


How is MuZero's second binary plane for chess defined?

Is the second binary plane all zeros or all ones? Or, something else? How is it known if the move is off the board? For my game, I know if it is a legal move on the board, but do not know if the move is off the board.

The second binary plane is one-hot by definition, there is a single one and everything else is zero. If this definition is not met, it's no longer "one-hot".
The paper doesn't state how exactly to implement "off the board" implementation. Research paper wouldn't go into coding level. However, detecting "off the board" is not a challenging task.

https://webcache.googleusercontent.com/search?q=cache:djj-G4T_PwgJ:https://craftychess.com/hyatt/boardrep.html+&cd=2&hl=en&ct=clnk&gl=au

The next step in board representation evolution is to enclose the board inside a larger array, so that illegal squares are "off" the edge and are easily detectable.

A possibility is add borders to your board. Crafty did that. Extend the board to 10x10. Not 9x9 because you need to deal with knight jumping.
Exactly how you should be doing it is implementation defined. We don't know what Google did because AlphaZero is not open source. I'm here just giving you an example.


What makes multi-layer neural networks able to perform nonlinear operations?

Nonlinear relations between input and output can be achieved by using a nonlinear activation function on the value of each neuron, before it's passed on to the neurons in the next layer.


Some RL algorithms (especially policy gradients) initialize with random policies, which often manifests as random jitter on spot for a long time?

Where can I find sources showing that policy gradients initialize with random policies, whereas Q-Learning uses epsilon-greedy policies?

You can find example algorithms for Q learning and policy gradients in Sutton & Barto's Reinforcement Learning: An Introduction - Q learning is in chapter 6, and policy gradients explained in chapter 13.

Neither of these things are strictly true in all cases. However, both are very common situations for the two kinds of learning agent:

Policy gradient solvers learn a policy function $\pi(a|s)$ that gives the probability of taking action $a$ given observed state $s$. Typically this is implemented as a neural network. Neural networks are initialised randomly. For discrete action selection using softmax output layer, the initial function will roughly be choosing evenly from all possible actions. So if some actions oppose and undo each other, e.g. move left and move right are options - then the situation as described in your quote can easily happen. Nowadays there are many other solutions using policy gradients that don't suffer as much with this effect. For instance, deterministic policy gradient methods such as A2C or DDPG.
For Q learning, and many variants of it, $\epsilon$-greedy is a very commonly used action selection mechanism. It is convenient and simple, and allows a simple parameter to control balance between exploration and exploitation whilst learning. However, Q learning can work with any action selection mechanism that has some possibility of acting optimally at least occasionally.

The best approach to action selection during the learning process in both policy-based methods and value-based methods is an active area of research. So if you read the RL literature you may find a lot of variation. The blog you quoted from has identified two quite common choices.

  Also, what does "max operation" have to do with epsilon-greedy policies?

The "max operation" is finding the maximum value of some function produced when varying a parameter. The related "argmax operation" is finding the value of the parameter that produces the maximum value. Q learning can use both types of operation, but specifically uses $\text{argmax}$ for $\epsilon$-greedy action selection.

An $\epsilon$-greedy policy requires acting optimally (according to current estimates of value function) with probability $p=1-\epsilon$, and randomly with equal probability of each action with probability $p=\epsilon$

In order to do this, the algorithm usually (with probability $p=1-\epsilon$) needs to know what the current best guess at an optimal solution is. That is the greedy action with respect to the current Q values i.e. $\text{argmax}_a Q(s,a)$  -