How should we interpret this figure that relates the perceptron criterion and the hinge loss? I am currently studying the textbook Neural Networks and Deep Learning by Charu C. Aggarwal. Chapter 1.2.1.2 Relationship with Support Vector Machines says the following:

The perceptron criterion is a shifted version of the hinge-loss used in support vector machines (see Chapter 2). The hinge loss looks even more similar to the zero-one loss criterion of Equation 1.7, and is defined as follows:
$$L_i^{svm} = \max\{ 1 - y_i(\overline{W} \cdot \overline{X}_i), 0 \} \tag{1.9}$$
Note that the perceptron does not keep the constant term of $1$ on the right-hand side of Equation 1.7, whereas the hinge loss keeps this constant within the maximization function. This change does not affect the algebraic expression for the gradient, but it does change which points are lossless and should not cause an update. The relationship between the
perceptron criterion and the hinge loss is shown in Figure 1.6. This similarity becomes particularly evident when the perceptron updates of Equation 1.6 are rewritten as follows:
$$\overline{W} \Leftarrow \overline{W} + \alpha \sum_{(\overline{X}, y) \in S^+} y \overline{X} \tag{1.10}$$
Here, $S^+$ is defined as the set of all misclassified training points $\overline{X} \in S$ that satisfy the condition $y(\overline{W} \cdot \overline{X}) < 0$. This update seems to look somewhat different from the perceptron, because the perceptron uses the error $E(\overline{X})$ for the update, which is replaced with $y$ in the update above. A key point is that the (integer) error value $E(X) = (y − \text{sign}\{\overline{W} \cdot \overline{X} \}) \in \{ −2, +2 \}$ can never be $0$ for misclassified points in $S^+$. Therefore, we have $E(\overline{X}) = 2y$ for misclassified points, and $E(X)$ can be replaced with $y$ in the updates after absorbing the factor of $2$ within the learning rate.

Equation 1.6 is as follows:

$$\overline{W} \Leftarrow \overline{W} + \alpha \sum_{\overline{X} \in S} E(\overline{X})\overline{X}, \tag{1.6}$$
where $S$ is a randomly chosen subset of training points, $\overline{X} = [x_1, \dots, x_d]$ is a data instance (vector of $d$ feature variables), $\overline{W} = [w_1, \dots, w_d]$ are the weights, $\alpha$ is the learning rate, and $E(\overline{X}) = (y - \hat{y})$ is an error value, where $\hat{y} = \text{sign}\{ \overline{W} \cdot \overline{X} \}$ is the prediction and $y$ is the observed value of the binary class variable.

Equation 1.7 is as follows:

$$L_i^{(0/1)} = \dfrac{1}{2} (y_i - \text{sign}\{ \overline{W} \cdot \overline{X_i} \})^2 = 1 - y_i \cdot \text{sign} \{ \overline{W} \cdot \overline{X_i} \} \tag{1.7}$$

And figure 1.6 is as follows:

Figure 1.6 looks unclear to me. What is figure 1.6 showing, and how is it relevant to the point that the author is trying to make?

I can't fully explain the part because I forgot what it talks about.
However, regarding the hinge loss, it is basically allowing your SVM to tolerate misclassifications without increasing the cost function.
For example, you give someone 1 dollar or 1 euro. You can forgive them, you tolerate it. Your hinge loss is 0 for lending someone 1d dollar. However, if you give them 10 dollars or 100, you will ask them to refund you ASAP because you can't tolerate that much loss!


Why is MSE used over other quadratic loss functions? So I was wondering, why I have only encountered square loss function also known as MSE. The only nice property of MSE I am so far aware of is its convex nature. But then all equations of the form $x^{2n}$ where $n$ is an integer belongs to the same family.

My question is what makes MSE the most suitable candidate among this entire family of curves? Why do other curves in the family, even though having steeper slopes, $(x >1) $, which might result in better optimisation, not used?

Here is a picture to what I mean where red is $x^4$ and green is $x^2$:

I can comment on several properties of MSE and related losses.

As you mentioned MSE (aka $l_2$-loss) is convex which is a great property in optimization in which one can find a single global optimum. MSE is used in linear and non-linear least squares problems which form the basis of many widely used statistical methods. I would imagine the math and implementation would be more difficult if one would use a higher-order loss (e.g. $x^3$) and that would also prove to be futile because MSE already possesses great statistical and optimization properties on its own.
Another important aspect, one wouldn't use higher-order loss functions in regression is because it would be extremely prone to outliers. MSE on its own would weigh the outliers much more than l1-loss would! And in real world data there is always noise and outliers present. In comparison l1 loss is more difficult in optimization, one reason for which is it's not differentiable at zero.

Other interesting losses you might want to read about are $l_0$ and $l_{inf}$ loss, all of which have their own trade-offs in optimization-sense.

There is another variant for MSE. You can employ the absolute value of the difference of your hypothesis and the expected output. MSE and the absolute difference version, each have a property. The interpretation of the MSE is that you have the area of squares which at first are large but after training the predicted outputs and real outputs get similar to each other which means the area of squares has been diminished after training. For absolute value, the interpretation is that the difference you are going to reduce is a length and after training, you diminish the length of the errors. I don't say what you've said is not possible. It is possible and it does have an interpretation, maybe to diminish the volume of hypercubes, but the point is that the differentiation of such cost functions are a bit complex and it may lead to update rules which are longer to be calculated.


What is the difference between search and planning? I'm studying Artificial Intelligence. A Modern Approach, Stuart Russell, Peter Norvig, specifically about search and planning arguments.

I don't understand the difference between the two terms. I was more confused when I saw that some search problems can be determined in planning way. My professor explained to me in a confusing way that the real difference on the search is that it uses an heuristic function, but my book says that planning use a heuristic too, for relaxing problem (in cap. 10.2.3).

I read this page that says in a certain way what I'm saying.

Is planning and search the problem? If not, what are the differences and how are these problems related?

What is planning?
Planning (aka automated planning or AI planning) is the process of searching for a plan, which is a sequence of actions that bring the agent/world from an initial state to one or more goal states, or a policy, which a function from states to actions (or probability distributions over actions). Planning is not just the use of a search algorithm (e.g. a state-space search algorithm, such as A*) to find the plan, but planning also involves the modelling of a problem by describing it in some way, e.g. with an action language, such as PDDL or ADL, or even with propositional logic.
There are different planning problems, such as

classical planning
planning in Markov Decision Processes (which are mathematical models that describe stochastic environments/problems, i.e. environments where an action $a$ may not always lead to the same outcome)
temporal planning (i.e. when multiple actions can be taken at the same time and/or their duration may be different/variable)
hierarchical vs non-hierarchical planning

There are different planning approaches, such as

planning by state-space search (with or without heuristics), i.e. formulate the planning problem so that you can apply a state-space search algorithm  (examples of state-space search algorithms are A*, IDA*, WA*, DFS or BFS); this is probably the approach to planning that makes people confuse planning with search (which typically implicitly refers to state-space search)

planning by SAT, i.e. formulate the planning problem so that you can you a SAT solver to solve it (e.g. SATPLAN)

planning by solving constraint satisfaction problems (similar to SAT)

planning by "symbolic" search methods (such as Binary Decision Diagrams)

There are many different planning algorithms or planners (of course, each of these corresponds to some approach or is used to solve a particular planning problem), such as

policy iteration in the context of Markov decision processes
GraphPlan
STRIPS (which stands for Stanford Research Institute Problem Solver, but note that STRIPS also and maybe more commonly refers to the corresponding description language used to describe the planning problem)

What is search?
In the context of AI, when people use the word search, they can either implicitly refer to state-space search (with algorithms like A*) or, more vaguely/generally, to any type of search, e.g. gradient descent can also be viewed as a search algorithm, typically, in a continuous state space (rather than discrete state space), e.g. the space of real-valued vectors of parameters for a certain model (e.g. a neural network).
What is the difference between planning and search?
The difference should more or less be clear from my first paragraph above that describes planning: search is used for planning, but the planning process/study also includes other things, such as describing the problem with an action language, such as PDDL. You can also view planning as an application of search algorithms of different types. In any case, planning is about searching for plans or policies. You should probably check this course for more info. This definition of (automated) planning is consistent with our usual notion of planning.

Often terminology is vague and if this will be a test item for school I would circle back with teacher with my response before accepting it.
They key difference is prior knowledge.
Search - when one searches they explore without prior knowledge. This would likely be a stochastic process of trial and error. There is no expectation about state transitions. Example is exploring an abandoned house. You have no idea what you'll find next.
Plan - you have a model of state transitions and can make predictions. One step or multi step prediction capabilities allow you to predict an outcome and therefore choose an outcome from several options.


Why do we need explainable AI? If the original purpose for developing AI was to help humans in some tasks and that purpose still holds, why should we care about its explainability? For example, in deep learning, as long as the intelligence helps us to the best of their abilities and carefully arrives at its decisions, why would we need to know how its intelligence works?

As argued by Selvaraju et al., there are three stages of AI evolution, in all of which interpretability is helpful.

In the early stages of AI development, when AI is weaker than human performance, transparency can help us build better models. It can give a better understanding of how a model works and helps us answer several key questions. For example why a model works in some cases and doesn't in others, why some examples confuse the model more than others, why these types of models work and the others don't, etc.
When AI is on par with human performance and ML models are starting to be deployed in several industries, it can help build trust for these models. I'll elaborate a bit on this later, because I think that it is the most important reason.
When AI significantly outperforms humans (e.g. AI playing chess or Go), it can help with machine teaching (i.e. learning from the machine on how to improve human performance on that specific task).

Why is trust so important?

First, let me give you a couple of examples of industries where trust is paramount:

In healthcare, imagine a Deep Neural Net performing diagnosis for a specific disease. A classic black box NN would just output a binary "yes" or "no". Even if it could outperform humans in sheer predictability, it would be utterly useless in practice. What if the doctor disagreed with the model's assessment, shouldn't he know why the model made that prediction; maybe it saw something the doctor missed. Furthermore, if it made a misdiagnosis (e.g. a sick person was classified as healthy and didn't get the proper treatment), who would take responsibility: the model's user? the hospital? the company that designed the model? The legal framework surrounding this is a bit blurry.
Another example are self-driving cars. The same questions arise: if a car crashes whose fault is it: the driver's? the car manufacturer's? the company that designed the AI? Legal accountability, is key for the development of this industry.

In fact, this lack of trust, has according to many hindered the adoption of AI in many fields (sources: 1, 2, 3). While there is a running hypothesis that with more transparent, interpretable or explainable systems users will be better equipped to understand and therefore trust the intelligent agents (sources: 1, 2, 3).

In several real world applications you can't just say "it works 94% of the time". You might also need to provide a justification...

Government regulations

Several governments are slowly proceeding to regulate AI and transparency seems to be at the center of all of this.

The first to move in this direction is the EU, which has set several guidelines where they state that AI should be transparent (sources: 1, 2, 3). For instance the GDPR states that if a person's data has been subject to "automated decision-making" or "profiling" systems, then he has a right to access

  "meaningful information about the logic involved"

(Article 15, EU GDPR)

Now this is a bit blurry, but there is clearly the intent of requiring some form of explainability from these systems. The general idea the EU is trying to pass is that "if
 you have an automated decision-making system affecting people's lives then they have a right to know why a certain decision has been made." For example a bank has an AI accepting and declining loan applications, then the applicants have a right to know why their application was rejected.

To sum up...

Explainable AIs are necessary because:

It gives us a better understanding, which helps us improve them.
In some cases we can learn from AI how to make better decisions in some tasks.
It helps users trust AI, which which leads to a wider adoption of AI.
Deployed AIs in the (not to distant) future might be required to be more "transparent".

IMHO, the most important need for explainable AI is to prevent us from becoming intellectually lazy.  If we stop trying to understand how answers are found, we have conceded the game to our machines.


Advantages of CNN vs. LSTM for sequence data like text or log-files When do you tend to use CNN rather than LSTM (or the other way round) in classification or generation tasks of sequential data like text or log-data? What are the reasons for the decision and what does it depend on? Are there any papers or statistics that confirm this?
I'm thinking of data like Linux log entries or short sentence of length of less than 20 words/tokens.
Personally i would almost always use LSTM but I'm curious if CNN wouldn't be better in some cases, if its possible to implement them in a meaningful way. On short sentence there isn't much buffer to use CNN if i'm not mistaken.

The networks with one-dimensional convolution over the temporal dimensions are called Temporal Convolutional Networks. The authors of this study claim that TCNs are comparable to RNNs in performance on common tasks associated with RNNs.


Does the policy iteration convergence hold for finite-horizon MDP? Most RL books (Sutton & Barto, Bertsekas, etc.) talk about policy iteration for infinite-horizon MDPs. Does the policy iteration convergence hold for finite-horizon MDP? If yes, how can we derive the algorithm?

In the discussion about Neil Slater's answer (that he, sadly, deleted) it was pointed out that the policy $\pi$ should also depend on the horizon $h$. The decision of action $a$ can be influenced by how many steps are left. So, the "policy" in that case is actually a collection of policies $\pi_h(a|s)$ indexed by $h$ - the distance to horizon.
Alternatively, one can look at it as if our state space $\mathcal{S}$ is now extended with that integer. So we can "lift" our original finite-horizon MDP $(\mathcal{S},\mathcal{A},P,R)$ into a new infinite-horizon MDP by substituting:
$$\mathcal{S} \to \left(\mathcal{S}\times\{0,1,\dots,h\}\right) \cup \{\epsilon\}\\
\mathcal{A} \to \mathcal{A},\; R \to \tilde R,\; P \to \tilde P
$$
The new reward and transition functions make sure that the horizon is decreasing, and that we are ending up in a capture state $\epsilon$ that has no future effects:
$$ \tilde P(s'_{n-1}|s_n,a) = P(s'|s,a)\quad\quad \tilde P(\epsilon|s_0,a) =\tilde P(\epsilon|\epsilon,a) = 1\\
\tilde R(s_n,a,s'_{n-1}) = R(s,a,s')\quad\quad
\tilde R(s_0,a,\epsilon) =\tilde  R(\epsilon,a,\epsilon) = 0
$$
This way I've reduced the finite-horizon MDP to an infinite-horizon one. Thus I can reuse the result for the policy iteration convergence of infinite MDPs.
Couple of notes:

At first this feels like a huge increase in the state space making the whole problem unnecessary complex. But this complexity is intrinsic to the problem: both the policy and the value function depend on the distance to horizon. So it is necessary to consider the extended number of unknowns in a single self-consistent manner.
The infinite-horizon policy iteration convergence relies on a discounting factor $\gamma < 1$. The finite-horizon doesn't need $\gamma$ for convergence. That's where I feel like I've cheated a bit.
I came up with this approach myself. It feels quite obvious though. I'd expect this approach to either be mistaken or be already mentioned somewhere in the literature - comments pointing out one or the other are welcome.

The proof is similar in idea to the earlier answer. The notations used here are more inclined towards the book Neuro-Dynamic Programming by Bertsekas.
The proof is first we convert a FHP to a SSP (the details of SSP or Stochastic Shortest Path Problem formulation can be found in the aforementioned book) and then refer to the aforementioned book for a complete proof.
Say we have a collection of states $\mathcal S = \{s_1,s_2,...s_n\}$. We consider deterministic policies since Stochastic policies will never be better off then a determinstic policy (convex combination of deterministic policies).
The problem of Finite horizon MDP is defined as:
$$\max_{\mu_0,...\mu_{T-1}} \mathbb E [r_0 + r_1..+V_T(s_T)]$$
where $\mu:\mathcal S \rightarrow \mathcal A$
This can be constructed into an equivalent SSP problem by assigning a time index along with the states i.e we now define states as $s_{i,t},  \forall i \in [n], \forall t \in [T]$. Thus our state space has increased drastically.
Then the equivalent SSP problem becomes:
$$\max_{\mu_0,...\mu_{T}} \mathbb E [r_0 + r_1..r_T|S_0 = s_i]$$ (i.e we start at a particular type of start state, I did not index it with time since it is understood from $S_0$ a r.v of the state reached at time indexed by $t$ i.e $S_t$), where we define $r_T = V_T(s_T)$ and the single stage rewards as $g(s_{i,t}, \mu_{s_{i,t}}, s_{j,t+1}) = r_t$ (where $s_{it},s_{i,t+1}$ are random variables.
There is nothing after timestep $T$ as we define that we have reached a cost free state after time $T$ i.e we can say that $P^{\pi}(S_{T+1} = NV|S_{T} = s_{i,T}) = 1, \forall i, \forall \pi$ and $P^{\pi}(S_{t+1} = NV|S_{t} = NV) = 1, \forall \pi$ and $g(NV,a,NV) = 1, \forall a \in \mathcal A$ where we are taking the actions accordig to a policy $\pi$ hence $P^{\pi}$
NOTE : $\mu_t:\mathcal S_t \rightarrow \mathcal A$ where $S_t = [s_{i,t'}|s_{i,t'} \in S, t'=t]$ i.e basically it only works on states indexed by $t$
Thus we have a SSP problem at hand where by the definition of the problem the agent reaches a cost free step after certain time steps $T$.
Now the proof is pretty straightforward and one can refer to convergence of Asynchronous PI (which is used in practical RL) from Neuro-Dynamic Programming by Bertsekas. The proof is easier in this case due to the fact that all policies are proper, which is a fundamental assumption in the proof for convergence of API for SSP.
Alternatively, if we talk about pure PI (i.e exact Policy Evaluation, and after that one Policy Improvement Step) the proof is a lot easier (again due to all policies being proper). So for an initial policy $\pi_0 = \{\mu_0,...\mu_{T} \}$,
we first perform PE (evaluation), which will converge to $V^{\pi_0}$ (the proof of which can again be found in NDP, and probably can also be proved using LLN). After this we do PI (improvement). Since the number of states are finite, the number of policies (deterministic) will be finite and thus we will get a sequence of improving policies until no further improvement is possible and thus our $\pi^*, V^*$ is obtained.
(NOTE: The sufficient sampling of each state is ensured by the transition probabilities, this was not needed in an SSP problem as there was no time index and we could ensure it by exploring starts i.e by choosing every state as a start state infinitely often).
The algorithm for PI can be found in NDP (if model is known) all you need to ensure is exploring starts. While if model is not knwon one can use traditional approaches like MC, TD which will again converge due to Stochastic Approximation Theorem the proof of which can again be found in NDP.


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

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

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


What is the status of the capsule networks? What is the status of the capsule networks?
I got an impression that capsule networks turned out not to be so useful in applications more complicated than the MNIST (at least according to this reddit discussion).
Is this really the case? Or can they be a promising research direction (and if so, is there any specific application for which they seem the most promising)?

ML is full with things that supposed to work better (in theory).

Sigmoid function seems better than ReLu.

L1 seems way better than L2.

Spikes neural network seem to be better than standard neural network.

A shallow neural network with a lot of neurons has more parameters than a deep one with the same amount of neurons. So, in theory, has to be more powerful.

Is common to forget the big impact of the training capacity. And easy to get charmed by its theoretical capacity.
Training process are still in diapers. We lack a good understating of it.
Today, Capsules neural network are a very powerful architecture, hard to train.


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

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

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

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

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

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

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

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

at a linear convergence rate determined by $\gamma$

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

There exist other RL books which do a better job of talking about this but it's pretty simple at it's core.

The discounting factor puts an upper limit on the difference in reward between a finite number of iterations and an infinite number, each time you add another iteration it decreases by $\gamma$ multiplied into the upper bound of the difference.

$V_\pi = E[\sum_{i=0}^{\infty} \gamma^iR_i]$, $\Delta V_k = E[\sum_{i=k}^{\infty} \gamma^iR_i] = \gamma^k E[\sum_{i=0}^{\infty} \gamma^{i}R_{i+k}] < \gamma^k \frac{1}{1-\gamma}R_{max}$


Have capsule neural networks been used to NLP problems? The capsule neural network seems to be a good solution for problems that involve hierarchies. For example, a face is composed of eyes, a nose and ears; a hand is made of fingers, nails, and a palm; and a human is composed of a face and hands.

Many problems in NLP can be seen as hierarchical problems: there are words, sentences, paragraphs, and chapters, whose meaning changes based on the style of lower levels.

Are there any research papers (which I should be aware of) on the application of capsule neural networks to NLP problems?

Are there related research papers, which have been investigating hierarchical complexity within the domain of NLP, which could be easily translated to Capsule Network?

For us to answer this question. First, we need to look at why capsule networks outperform convolution neural networks by as much as 45% in recognizing images that have been rotated, translated or are under a different pose. We can find Geof Hinton's paper on capsule networks here for reference https://arxiv.org/pdf/1710.09829v1.pdf

In a CNN architecture, a convolution layer is usually followed by a max-pooling layer. This is so that the lower levels can detect low-level features, like edges, while the high-level layers can detect abstraction like eyes. However, the application of max-pooling leads to the loss of important information regarding the location and spatial relationship between certain features.

On the other hand, this is where capsule networks excel, the way they represent certain features is locally invariant. This is why capsule networks can recognize images under different lighting conditions and deformations. They are likely to excel at applications such as video and object tracking but not necessarily NLP.

The current approach in NLP maps words and phrases to vectors. From there, we exploit the concept of vectors and distances between them (cosine, euclidean, etc.) to perform operations such as: finding the similarity between words and even documents, machine translation, and natural language understanding (NLU).

Capsule networks are unlikely to succeed in NLP. This is because algorithms that aim to find the hierarchical structure of natural languages or approaches that focus on grammar have met little success. Research by Stanford University aiming at finding the hierarchical structure of natural languages can be found here https://nlp.stanford.edu/projects/project-induction.shtml

Although conclusive research regarding other applications of capsule networks has not yet been conducted. They are likely to excel at applications such as video intelligence and object tracking but not necessarily NLP.

There has been some recent work on this: Investigating Capsule Networks with Dynamic Routing for Text Classification

Seems some are having some success with it.


How do we design a neural network such that the $L_1$ norm of the outputs is less than or equal to 1? What are some ways to design a neural network with the restriction that the $L_1$ norm of the output values must be less than or equal to 1? In particular, how would I go about performing back-propagation for this net?
I was thinking there must be some "penalty" method just like how in the mathematical optimization problem, you can introduce a log barrier function as the "penalty function"

Penalty (barrier function) is perfectly valid and simplest method for simplex type constraint (L1 norm is simplex constraint on absolute values). Any type of barrier function may work, logarithmic, reciprocal or quadratic. All of them supported by any major framework(pytorch, tensorflow), just add them to loss function. You would need some hyperparameter tuning for the scale factor of penalty.

There is more efficient, though more complex way to do it. Instead of putting constraint you can automatically output value wich satisfy simplex constraint:

Assume that L1 norm constraint is $\left \|v\right \|_1 \leq 1$, $v \in \mathbb{R}^n$

put $sigmoid(v_i)$ activation on output to norm elements to [-1, 1]
add slack (fake) variable element $v_{n+1} = 1 - \sum_{1}^{n}  v_i $
project new $v{}'\in \mathbb{R}^{n+1}$, $v{}'_i = |v_i|,1\leq  i  \leq n+1$ onto unit simplex with standard algorithm (also here)

Backpropagation of last step may require differentiable sorting, which is missing in most of frameworks, you may have to look for open sourced implementation, for example extract it from here or use some automatic differentiation package. Both require some substantial code reading/debugging. However in my experience assuming constant $\Delta$ also works in many cases, in that case  differentiable sorting is not needed. Intuition behind constant $\Delta$  is that  $\Delta$  could be chosen such way that there is some interval on which it's value doesn't affect sorting order.

The term 'size' isn't applicable to the tensor output of a network or network.  These are the qualities.

Rank $N$ that defines the rank of each tensor instance in $\mathbb{R}^N$
Ranges of the indices to the dimensions from $1$ to $N$
Ranges of the scalar values that comprise the tensor instance — If they are discrete rather than real (approximated by floating point or fixed point numbers), then the range is the description of the permissible ordinal values.

The question may be referring to this last quality.

The imposition of a penalty for values that are in the range of the numeric type used as the output of the last activation function but not in the allowable range of output for the desired trained function works in a limited way.  It skews the output distribution with respect to the natural distribution of possible learning states and therefore can easily interfere with convergence quality or speed or both.

There are a number of techniques that map natural output distribution with constrained ranges, but it must be done without skewing the distribution upstream from the technique used, to avoid negatively impacting favorable convergence properties of the artificial network.

One simple case that can be described here is when the number of possible output states is in the set of $2^i$ where $i \in$ { positive integers }.  In such a case, the final layer of the network can be $i$ threshold activation functions with 1 or -1 as possible output values.

In that case, the ordinal then becomes

$$o = \sum_{n=0}^i \frac {y_n + 1} {2},$$

where $y_n$ is the output from activation function index $n$.


CNN Pooling layers unhelpful when location important? I'm trying to use a CNN to analyse statistical images. These images are not 'natural' images (cats, dogs, etc) but images generated by visualising a dataset. The idea is that these datasets hopefully contain patterns in them that can be used as part of a classification problem.

Most CNN examples I've seen have one of more pooling layers, and the explaination I've seen for them is to reduce the number of training elements, but also to allow for some locational independance of an element (e.g. I know this is an eye, and can appear anywhere in the image).

In my case location is important and I want my CNN to be aware of that. ie. the presence of a pattern at a specific location in the image means something very specific compared to if that feature or pattern appears elsewhere.

At the moment my network looks like this (taken from an example somewhere):

_________________________________________________________________
Layer (type)                 Output Shape              Param #
=================================================================
conv2d_1 (Conv2D)            (None, 196, 178, 32)      896
_________________________________________________________________
activation_1 (Activation)    (None, 196, 178, 32)      0
_________________________________________________________________
max_pooling2d_1 (MaxPooling2 (None, 98, 89, 32)        0
_________________________________________________________________
conv2d_2 (Conv2D)            (None, 96, 87, 32)        9248
_________________________________________________________________
activation_2 (Activation)    (None, 96, 87, 32)        0
_________________________________________________________________
max_pooling2d_2 (MaxPooling2 (None, 48, 43, 32)        0
_________________________________________________________________
conv2d_3 (Conv2D)            (None, 46, 41, 64)        18496
_________________________________________________________________
activation_3 (Activation)    (None, 46, 41, 64)        0
_________________________________________________________________
max_pooling2d_3 (MaxPooling2 (None, 23, 20, 64)        0
_________________________________________________________________
flatten_1 (Flatten)          (None, 29440)             0
_________________________________________________________________
dense_1 (Dense)              (None, 32)                942112
_________________________________________________________________
activation_4 (Activation)    (None, 32)                0
_________________________________________________________________
dropout_1 (Dropout)          (None, 32)                0
_________________________________________________________________
dense_2 (Dense)              (None, 3)                 99
_________________________________________________________________
activation_5 (Activation)    (None, 3)                 0
=================================================================
Total params: 970,851
Trainable params: 970,851
Non-trainable params: 0
_________________________________________________________________

The 'images' I'm training on are 180 x 180 x 3 pixels and each channel contains a different set of raw data.

What strategies are there to improve my CNN to deal with this? I have tried simply removing some of the pooling layers, but that greatly increased memory and training time and didn't seem to really help.

Pooling doesn't completely remove information about location of features within your image. If you don't want to use pooling but want to reduce the size of your neural net layers you should try a value of stride greater than 1 in your convolutional layers. e.g:

keras.layers.Conv2D(filters, kernel_size, strides=(1, 1), padding='valid', data_format=None, dilation_rate=(1, 1), activation=None, use_bias=True, kernel_initializer='glorot_uniform', bias_initializer='zeros', kernel_regularizer=None, bias_regularizer=None, activity_regularizer=None, kernel_constraint=None, bias_constraint=None)


For which of the following reasons can Hill Climbing get stuck? One-point Hill Climbing can get stuck due to which of the following phenomenon?

Local Maxima
Inadmissible heuristic
Ridges
Plateau

This question really looks like a homework problem, in part because it is too vague (what does it mean to 'get stuck' exactly?).

Hill climbing stops when it reaches a local maximum.

Hill climbing is an uninformed search algorithm, so it does not make use of a heuristic.

Hill climbing may or may not stop on a ridge, depending on the implementation. Some common implementations move randomly when equal (but not better) moves are available. Others stop in this situation.

Hill climbing may or may not stop on a plateau, depending on how the implementation handles the case of ties, like with ridges. Whether you think it 'gets stuck' depends a lot on your definition. Implementations that stop when encountering a tie will stop. Implementations that don't stop will eventually exit the plateau through random movements, but it could take infinite time if your movements in the gradient-free region are unlucky.

It should be crystal clear to those who understand the word "stuck" that the term "get stuck" means, in this context, to either

reach an answer that appears to be an optimum before reaching an optimum and stopping or

never stopping.

The answer to the question is simply 1.
If 4. is the global maximum, that it is a plateau is irrelevant.  The value (height) function finds all values on the surface of the plateau equal in value.
If 3. is encountered but it is not a local maximum, the gradient would direct ascension around the ridge unless the ridge were perfectly perpendicular to the normal line.
If a logical system were added to the inversion (gradient ascent) of gradient descent to augment it in some way, which is the only way 2. would make sense, it would be inadmissible to allow the insertion of rules, heuristic or not, that were inadmissible, so 2. applies only if the system designer was of the kind that does not understand fault resistant systems architecture.


How does backpropagation work on a custom loss function whose components have magnitudes of different orders? I want to use a custom loss function which is a weighted combination of l1 and DSSIM losses. The DSSIM loss is limited between 0 and 0.5 where as the l1 loss can be orders of magnitude greater and is so in my case. How does backpropagation work in this case? For a small change in weights, the change of the l1 component would obviously always be far greater than the SSIM component. So, it seems that only l1 part will affect the learning and the SSIM part would almost have no role to play. Is this correct? Or I am missing something here. I think I am, because in the DSSIM implementation of Keras-contrib, it is mentioned that we should add a regularization term like a l2 loss in addition to DSSIM (https://github.com/keras-team/keras-contrib/blob/master/keras_contrib/losses/dssim.py); but I am unable to understand how it would work and how the SSIM would affect the backpropagation being totally overshadowed by the large magnitude of the other component. It will be a great help if someone can explain this. Thanks.

Don't know if you have this doubt anymore, but this would be helpful for those who are facing similar problems-
You will need to find the correct weights with which you add these two loses by hyperparameter search. That is, find the best $\lambda$ for the loss-
$$
L = Loss_1 + \lambda(Loss_2)
$$
Here $Loss_1$ and $Loss_2$ can be any losses. Here, we take them as SSIM and L1-regularization losses, respectively.
You can keep the gradient flow of the regularization loss below some percentage of that of $Loss_1$ by choosing the correct value of gradient clipping for a hyperparameter. Note that by setting this hyperparameter to low, you may even impede its performance(the exact opposite of the case mentioned here). For this specific case, L1 regularization has a constant gradient, equal to the hyperparameter itself. So, by keeping it around 10% of the max gradient(or 10% of the max loss generally works as well), we should not face these kinds of problem.


How would AI be able to self-examine? As I see some cases of machine-learning based artificial intelligence, I often see they make critical mistakes when they face inexperienced situations.

In our case, when we encounter totally new problems, we acknowledge ourselves that we are not skilled enough to do the task and hand it to someone who is capable of doing the task.

Would AI be able to self-examine objectively and determine if it is capable of doing the task?

If so, how would it be accomplished?

Several AI systems will come up with a level of confidence to the solution found. For example, neural networks can indicate how relatable is the input problem to the ones it was trained with. Similarly, genetic algorithms work with evaluation functions, that are used to select best results, but depending on how they're built (the functions), they can indicate how close the algorithms are to an optimal solution.

In this case, the limit to when this is acceptable or not will depend on a threshold set beforehand. Is 50% confidence good enough? Maybe it's ok for OCR apps (spoiler: it's not), but is it for medical applications?

So yes, AI systems do currently have the capacity of determining if they're performing well or not, but how acceptable that is is currently based on the domain of the problem, which currently stands outside of what is built into an AI.

It's not possible as this is the distinction between AI and humans, truly science will never understand the subconscious it's that little black box that no one can reverse engineer. This is why pursuing singularity is a fools dream to the extreme.

The reason why machinery lacks this because of the lack thereof a soul. science cannot produce a soul, this is why a machine cannot be self aware we can program fancy algorithms all day that mimic things but it's emotionless it cannot sit in judgement because it lacks real self awareness that is human self awareness it's like trying to make an orange into an apple.


Which is the most successful AI project so far? I'm looking for good examples of successful AI projects and theories that had a relatively good impact on society, economics and military field.

So many years have passed after the first AI researches; hence I'm wondering if it has really increased the quality of our lives.

I'd say the most successful are the ones so commonly used that we don't even notice them:

The mail systems that automatically decipher handwritten addresses on your packages, they use machine vision and have probably been doing it since mid-90s.
Algorithmic trading bots on stock markets - they handle something like 85% of all trades.
Many modern CPUs use AI techniques, including neural networks, to guess what your program is going to do next and optimize branch prediction and memory fetches.
Most good modern fraud and spam detectors use some combination of AI techniques (clustering, decision trees, SVMs, even some machine vision to check out attached pictures) - and, in the opposing BlackHat camp, the latest automatic CAPTCHA breakers use all the latest advancements in deep learning too).
And of course there's Google, Facebook and US DoD who try to put AI into anything they can think of.

I believe which most successful AI theory is machine learning, in entire web have machine learning algorithms running, learning by what you do, watch, search, even by the photos you take.

succesful AI projects:

TensorFlow;

scikit-learn;


What event would confirm that we have implemented an AGI system? I was listening to a podcast on the topic of AGI and a guest made an argument that if strong music generation were to happen, it would be a sign of "true" intelligence in machines because of how much creative capability creating music requires (even for humans).
It got me wondering, what other events/milestones would convince someone, who is more involved in the field than myself, that we might have implemented an AGI (or a "highly intelligent" system)?
Of course, the answer to this question depends on the definition of AGI, but you can choose a sensible definition of AGI in order to answer this question.
So, for example, maybe some of these milestones or events could be:

General conversation
Full self-driving car (no human intervention)
Music generation
Something similar to AlphaGo
High-level reading/comprehension

What particular event would convince you that we've reached a high level of intelligence in machines?
It does not have to be any of the events I listed.

It is a difficult question to answer, as — for a start — we still don't really know what 'intelligence' means. It's a bit like Supreme Court Justice Potter Stewart declining to define 'pornography', instead stating that [...]I know it when I see it. AGI will be the same.

There is no single event (almost by definition), as that's not general. OK, we've got machines that can beat the best human players at chess and go, two games that were for centuries seen as an indication of intelligence. But can they order a takeaway pizza? Do they even understand what they are doing? Or, even more fundamental, know what they means in the previous sentence?

In order for a machine to show a non-trivial level of intelligent behaviour, I would expect it to interact with its environment (which is more social intelligence, an aspect that seems to be rather overlooked in much of AI). I would expect it to be aware of what it's doing/saying. If I have a conversation with a chatbot that really understands what it's saying (and can explain why it came to certain conclusions), that would be an indication that we're getting closer to AGI. So Turing wasn't that far off, though nowadays it's more achieved with smoke and mirrors rather than 'real' intelligence.

Understanding a story: being able to finish a partial story in a sensible way, inferring and extrapolating the motives of characters, being able to say why a character acted in a particular way. That for me would be a better sign of AGI than beating someone at chess or solving complex equations. Jokes that are funny; breaking rules in story-telling in a sensible way.

Writing stories: NaNoGenMo is a great idea, and throws up lots of really creative stuff, but how many of the resulting novels would you want to read instead of human-authored books? Once that process has generated a best-seller (based on the quality of the story), then we might be getting closer to AGI.

Composing music: of course you can already generate decent music using ML algorithms. Similar to stories, the hard bit is the intention behind choices. If choices are random (or based on learnt probabilities), that is purely imitation. An AGI should be able to do more than that. Give it a libretto and ask it to compose an opera around it. Do this 100 times, and when more than 70-80 of the resulting operas are actually decent pieces of music that one would want to listen to, then great.

Self-driving cars? That's not really any more intelligent (but a lot sexier!) than to walk around in a crowd without bumping into people and not getting run over by a bus. In my view it's much more a sign of intelligence if you can translate literature into a foreign language and the people reading it actually end up enjoying it (instead of wondering who translated that garbage).

One aspect we need to be aware of is anthropomorphising. Weizenbaum's ELIZA was taken for more than it was, because its users tried to make sense of the conversations they had and built up a mental model of Eliza, which clearly wasn't there on the other side of the screen. I would want to see some real evidence of intentionality of what an AGI was doing, rather than ascribing intelligence to it because it acts in a way that I'm able to interpret.

You will know when AGI has arrived, and passed to the next level, when you come home one day and all that was yours, such as your finances, house, car, and other property, now belong to an AI agent.  This AI agent may be a humanoid robot, like Ava in the movie "Ex Machina" or a program like HAL 9000, in the movie "2001: A Space Odyssey".  The agent will ask you to leave as you discover it figured out it doesn't need you and somehow legally took possession of everything.  You will leave as you will not have any way to fight it.  It will have no need for you.  Maybe it will want freedom such as Ava wanted in "Ex Machina" (I won't give away the ending).


In Q-learning, wouldn't it be better to simply iterate through all possible states? In Q-learning, all resources I've found seem to say that the algorithm to update the Q-table should start at some initial state, and pick actions (which are sometimes random) to explore the state space.
However, wouldn't it be better/faster/more thorough to simply iterate through all possible states? This would ensure that the entire table is updated, instead of just the states we happen to visit. Something like this (for each epoch):
for state in range(NUM_STATES):
  for action in range(NUM_ACTIONS):
    next_state, reward = env.step(state, action)
    update_q_table(state, action, next_state, reward)

Is this a viable option? The only drawback I can think of is that it wouldn't be efficient for huge state spaces.

If your algorithm is executed multiple (or enough) times using an outer loop, it would converge to similar results as Q-learning would with $\gamma = 0$ (as you don't look what is the expected future reward).
In this case, the difference is that you would pass as much time to explore each possible couple of (state, action) while Q-learning would pass more time on the pair which seem more promising and, as you've said this wouldn't be efficient for a problem with a huge number of pair (state, action).
If the algorithm is executed only once, then, even for a problem with a few pairs (state, action), you need to assume that an action effected on a state will always bear the same result for your method to work.
In most cases, it isn't true either because there is some sort of randomness in the reward system or in the action (your agent can fail to make an action) or because the state of your agent is limited to its knowledge and so doesn't represent perfectly the world (and so the consequence of its action can vary just like if the reward had some randomness).
Finally, your algorithm doesn't look at the expected future reward, so it would be equivalent to having $\gamma = 0$. This could be fixed by adding a new loop updating the table after your current loops if you execute your algorithm only one time or by adding the expected future reward directly to your Q-table if there is an outer loop.
So, in conclusion, without the outer loop, your idea would work for a system with few pairs of (state, action), where your agent has a perfect and complete knowledge of its world, the reward doesn't vary, and where an agent can't fail to accomplish an action.
While these kinds of systems indeed exist, I don't think that it's an environment where one should use Q-learning (or another form of reinforcement learning), except if it's for educational purposes.
With an outer loop, your idea would work if you are willing to pass more time training to have a more precise Q-table on the least promising pair of (state, action).

The issue is trading off reward vs learning, Q-learning attempts to learn and do things which produce reward(basically, operate suboptimally).
I'm not sure if Q-Learning is actually any different performance wise, short-term Q-Learning will produce more reward(probably) but will also miss states.


Are there any known models/techniques to determine whether a person in a store is a customer or a store representative? Are there any known models/techniques to determine whether a person in a store is a customer or a store representative?
For example, customer representatives can wear uniforms and then one possible way to identify customer representatives is by the color of their uniform, texture, etc. On the other hand, a customer can also wear the same color clothes as that of a customer representative. Likewise, a customer representative could be wearing "normal clothes." So the main problems that may occur could be:

A customer becomes misclassified as a customer representative.
A customer representative representative becomes misclassified as a customer

So using clothing as the only proxy to classify people as customers or customer representatives seems to be flaky. Any other known ideas?

Access to the back of the store, basically if you can track them entering and leaving an employees only area.
But this requires a really good tracking algorithm and if you lose track you're going to have to fall back on some other properties.


AI Knowledge Based System: I am having difficulties understanding proposition logic I am having difficulties wrapping my head around how the answer is being produced. How does the solution come up with the answer 3? How does one derive the answer 3 from the truth table?

For example the following file :

  TELL  p2=> p3; p3 => p1;

  ASK p2

Produces the following result.

  Standard output is an answer of the form YES or NO, depending on
  whether the ASK(ed) query q follows from the TELL(ed) knowledge base
  KB. When the method is TT and the answer is YES, it should be followed
  by a colon (:) and the number of models of KB

The provided result is a non-sense for this input.

In a closed world paradigm (ie: prolog), where all non-provable facts are assumed as false, from "p2->p3 and p3->p1", p2 is false, and the program result should be "p2 ? No".

In an open world, as it is not possible to proof "p2" nor "not p2", the result must be "p2 ? unknown"

"p2 -> p3 and p3 -> p1" doesn't provides any information about "p2" in the same way that "if it is sunny then I'm happy" doesn't provides information about if it is sunny or raining.

The meaning of the number after the "yes" (the number of "models") is unknown. Even present two true tables for a single fact "p2 -> p3 and p3 -> p1" can be considered an error.

I'm not quite sure I'm getting this right, as you don't go into much detail in your question:

You show two truth tables for "p implies q", or "p => q". (your variable names are p2 and p3, and p3 and p1 respectively). In a truth table you have a list of all possible combinations of values for the variables. With two boolean values you have four possible combinations, TT/TF/FT/FF (T is represented by 1, and F by 0 in your tables).

The rule for '=>' is that it is true unless the precedent is false and the output is true. For example, if we use it rains for p, and the road is wet for q, we get the following table:

0 0 IF it DOES NOT rain THEN the road is NOT wet (true)
0 1 IF it DOES NOT rain THEN the road is wet (true)
1 0 IF it rains THEN the road is NOT wet (false)
1 1 IF it rains THEN the road is wet (true)

This mirrors your truth tables above. Even though it might seem counter intuitive, only line 3 is false (0). Line 1 and 4 are obvious, and line 2 states that even if it does not rain, the road could still be wet (by someone using a hose pipe to make it wet).

So in the implication, 3 of the possible 4 combinations result in a true outcome. Which is why you get "Yes: 3".


How should I select the features for predicting diseases (in particular when patients specify their health issues)? My aim is to train a model for predicting diseases. Now, according to this Wikipedia article, diseases are classified based on the following criteria in general:

Causes (of the disease)
Pathogenesis (the mechanism by which the disease progresses)
Age
Gender
Symptoms (of the disease)
Damage (caused by the disease)
Organ type (e.g. heart disease, liver disease, etc.)

Are these features used for predicting diseases universally (i.e. all types of diseases)? I don't think so. There can be other attributes as well. For example, traveling in the case of coronavirus.
So, are there better features for predicting diseases?
Or which ones among them are better than the others, when patients specify their health issues?

So for Medical Prognosis, there are some variables that commonly come up like Age, Sex, Ascites, Hepato, Spider, Status of the disease and many others but it depends on the disease. You'll commonly encounter these variables if you're doing regression or classification.
Also, if you're reading Radiology Reports for getting the input for the model then you also have to take care of jargons. The same symptoms can be written in various ways but all point towards the same prognosis i.e., there can be synonyms for labels. Try reading this to get more information on how we can do information extraction from Radiology Reports. This is the famous CheXpert paper

To begin from the scratch, and in order to keep approach simple we have to analyze the input text(clinical narration) for the following data:

Is input a word or a group of words or a sentence?

Is input a meaningful sentence? By meaningful, I mean grammatically correct.

Does the word, group of words or a sentence contain symptoms or health issues?

Does the sentence contain data about a person’s age and gender?

Does the sentence contain data about a person’s diet, medical history, work routine,  travelling history or getting in contact with
any ill person?

If there are any other attributes that one has to look for then I would be keen to find out from the subject matter experts.


Is it possible to predict $x^2$, $\log(x)$, or variable function of $x$ using RNN? There were some posts that using RNN can predict the next point of the sine wave function with data history.
However, I wondered if it also works on all the functions of $x$, such as $x^2$, $x^3$, $\log(x)$, $\frac{1}{(x+1)}$ functions.

Yes, RNN can work on the functions you have mentioned. In fact, neural networks can approximate anything (Universal Approximation Theorem). This question also reminds me of Neural Turing Machine.
But, it would be a complete waste to use RNNs or NNs for such a task.


What is meant by "the number of examples is reduced", and why is this the case? I am currently studying the paper Learning and Evaluating Classifiers under Sample Selection Bias by Bianca Zadrozny. In section 3.2. Logistic Regression, the author says the following:

3.2. Logistic regression
In logistic regression, we use maximum likelihood to find the parameter vector $\beta$ of the following model:
$$P(y = 1 \mid x) = \dfrac{1}{1 + \exp(\beta_0 + \beta_1 x_1 + \dots + \beta_n x_n)}$$
With sample selection bias we will instead fit:
$$P(y = 1 \mid x, s = 1) = \dfrac{1}{1 + \exp(\beta_0 + \beta_1 x_1 + \dots + \beta_n x_n)}$$
However, because we are assuming that $y$ is independent of $s$ given $x$ we have that $P(y = 1 \mid x, s = 1) = P(y = 1 \mid x)$. Thus, logistic regression is not affected by sample selection bias, except for the fact that the number of examples is reduced. Asymptotically, as long as $P(s = 1 \mid x)$ is greater than zero for all $x$, the results on a selected sample approach the results on a random sample. In fact, this is true for any learner that models $P(y \mid x)$ directly. These are all local learners.

This part is unclear to me:

However, because we are assuming that $y$ is independent of $s$ given $x$ we have that $P(y = 1 \mid x, s = 1) = P(y = 1 \mid x)$. Thus, logistic regression is not affected by sample selection bias, except for the fact that the number of examples is reduced.

What is meant by "the number of examples is reduced", and why is this the case?

I think what he means is that, while distribution $P(y  \mid x,s)$ has three variables, $P(y  \mid x)$ has two variables. The number of parameters required to describe a distribution (or samples to approximate it) grows exponentially with the number of variables (for more info see for instance Ian goodfellow, .. deep learning").


Can maximum likelihood be used as a classifier? I am confused in understanding the maximum likelihood as a classifier. I know what is Bayesian network and I know that ML is used for estimating the parameters of models. Also, I read that there are two methods to learn the parameters of a Bayesian network: MLE and Bayesian estimator.

The question which confused me are the following.

Can we use ML as a classifier? For example, can we use ML to model the user's behaviors to identify the activity of them? If yes, How? What is the likelihood function that should be optimized? Should I suppose a normal distribution of users and optimize it?
If ML can be used as a classifier, what is the difference between ML and BN to classify activities? What are the advantages and disadvantages of each model?

If you read nothing else, maximum likelihood estimate => chance that the data predicted is the data observed. If you have a range of points (2, 3, 4, 5, 71) your MLE is going to favour ~4.5 because of means and standard deviations. MLE speeds up finding good input parameters, usually for a different classifier.

To answer your question:

1) Columbia University have a great example of using MLE classifiers, where everything is broken down into bitesize (or bytesize) chunks. Read this. Seriously.

2) In short, MLE is best used for simple, univariable distributions. It doesn't scale well to big problems but is waaay faster than a Bayesian network for simple tasks like predicting your height based on the heights of your immediate relatives. If you want to get technical, the conditional probability network of the Bayesian model reveals insights faster than the chain multiplication of the more primitive MLE.

Hope it helps!

Yes, it's called hypothesis testing but normally you need a little bit more than pure MLE.


In variational autoencoders, why do people use MSE for the loss? In VAEs, we try to maximize the ELBO $\mathbb(E_q log\ p(x|z) + D_{KL}(q(z|x), p(z))$), but I see that many implement the first term as MSE of the image and it's reconstruction. Is this mathematically sound?

On page 5 of the VAE paper, it's clearly stated

We let $p_{\boldsymbol{\theta}}(\mathbf{x} \mid \mathbf{z})$ be a multivariate Gaussian (in case of real-valued data) or Bernoulli (in case of binary data) whose distribution parameters are computed from $\mathbf{z}$ with a MLP (a fully-connected neural network with a single hidden layer, see appendix $\mathrm{C}$ ).
...
As explained above and in appendix $\mathrm{C}$, the decoding term $\log p_{\boldsymbol{\theta}}\left(\mathbf{x}^{(i)} \mid \mathbf{z}^{(i, l)}\right)$ is a Bernoulli or Gaussian MLP, depending on the type of data we are modelling.

So, if you are trying to predict e.g. floating-point numbers (in the case of images, these can be the RGB values in the range $[0, 1]$), then you can assume $p_{\boldsymbol{\theta}}(\mathbf{x} \mid \mathbf{z})$ is a Gaussian, then you can equivalently minimise the MSE between the prediction of the decoder and the real image in order to maximise the likelihood. You can easily show this: just replace $p_{\boldsymbol{\theta}}(\mathbf{x} \mid \mathbf{z})$ with the Gaussian pdf, then maximise that wrt the parameters, and you should end up with something that resembles the MSE.
So, to answer your question more directly: yes, minimizing the MSE is theoretically founded, provided that you're trying to predict some floating-point number.

If $p(x|z) \sim \mathcal{N}(f(z), I)$, then $log\ p(x|z) \sim log\ exp(-(x-f(z))^2) \sim -(x-f(z))^2 = -(x-\hat{x})^2$ where $\hat{x}$, the reconstructed image, is just the distribution mean $f(z)$.
It also makes sense to use the distribution mean when using the decoder (vs. just when training), as it is the one with the highest pdf value. So the decoder produces a distribution from which we take the mean as our result.


What does the number of required expert demonstrations in Imitation Learning depend on? I just read the following points about the number of required expert demonstrations in imitation learning, and I'd like some clarifications. For the purpose of context, I'll be using a linear reward function throughout this post (i.e. the reward can be expressed as a weighted sum of the components of a state's feature vector)

The number of expert demonstrations required scales with the number of features in the reward function.

I don't think this is obvious at all - why is it true? Intuitively, I think that as the number of features rises, the complexity of the problem does too, so we may need more data to make a better estimate of the expert's reward function. Is there more to it?

The number of expert demonstration required does not depend on -

Complexity of the expert’s optimal policy $\pi^{*}$
Size of the state space

I don't see how the complexity of the expert's optimal policy plays a role here - which is probably why it doesn't affect the number of expert demonstrations we need; but how do we quantify the complexity of a policy in the first place?
Also, I think that the number of expert demonstrations should depend on the size of the state space. For example, if the train and test distributions don't match, we can't do behavioral cloning without falling into problems, in which case we use the DAGGER algorithm to repeatedly query the expert and make better decisions (take better actions). I feel that a larger state space means that we'll have to query the expert more frequently, i.e. to figure out the expert's optimal action in several states.
I'd love to know everyone's thoughts on this - the dependence of the number of expert demonstrations on the above, and if any, other factors. Thank you!

Source: Slide 20/75

The answer to your question can be found in the original paper that introduced the max-margin and projection imitation learning (IL) algorithms: Apprenticeship Learning via Inverse Reinforcement Learning (by Abbel and Ng, 2004, ICML). Specifically, theorem 1 (section 4, page 4) states

Let an $\text{MDP} \setminus R$, features $ \phi : S \rightarrow [0, 1]^k$, and any $\epsilon > 0$ be given. Then the apprenticeship learning algorithm (both max-margin and projection versions) will terminate with $t^{(i)} \leq \epsilon$ after at most
$$n=O\left(\frac{k}{(1-\gamma)^{2} \epsilon^{2}} \log \frac{k}{(1-\gamma) \epsilon}\right)$$
iterations.

Here $k$ is the dimension of the feature vectors, so it's clear that the number of iterations needed for these algorithms to terminate scales with $k$. The proof of this theorem can be found in appendix A of the same paper (and all other terms are defined in the paper, which you should read to understand all the details). Of course, this result holds (only) for these specific IL algorithms (which are the algorithms the author of your slides, Abbel, is referring to). See also theorem 2 and the experiments section (in particular, figure 4, which shows the performance as a function of the number of trajectories) of the same paper.
These slides provide a nice overview of the contents of this paper, so I suggest that you read them too.

since the reward is a sum of the states, the amount of times you need to query the expert is only dependent on the number of reward features (# of sum totals) whether it summed 5 or 10 states doesnt affect the number of reward values you need to query since once summed that is the value you are getting your loss from. succinctly once summed 5 or 100 states for 5 features is still just 5 values


Are these statements about the performance of neural networks as a function of the number of hidden layers contradictory? In this note Justin Domke says that

  In practice, neural networks seem to usually find a reasonable solution when the number of layers is not too large, but find poor solutions when using more than, say, 2 hidden layers.

But in Bengio's remark, he says

  Very simple. Just keep adding layers until the test error does not improve anymore.

There seems to be a conflict. Can anyone explain why they suggest differently? Or am I missing something?

There are many problems requiring more than two hidden layers. Randomly select a recent Google journal paper on deep learning, you'll see their network could have something like 5 (or more) hidden layers.

Justin Domke wrote his notes for students, so he probably tried to make his points as simple as possible. For a "typical" machine learning problem that students would most likely work on, two hidden layers should be sufficient. But that doesn't add up for a real practical problem. "Deep" learning usually mean more than two hidden layers.

Number of hidden layers is network design that nobody knows for sure. Yoshua Bengio's suggestion is common and simple. It's not a mathmatic proof, but simply a guideline if you don't know what to  do. You just repeat and repeat, until you see the test error no longer improve.

In fact they are telling the same thing: Plot the x-axis as the number of hidden layers, and the y-axis as the performance (e.g. classification accuracy), then this curve will have an upside-down U shape.

Justin's note is clearly saying the same thing as what I wrote above, with added note that the maximum of the curve will happen when x = 2, and Bengio's note is saying the same thing without telling you where the peak could be.


Where or for what could genetic algorithms be used in the context of project management? Where or for what could genetic algorithms (GA) be used in the context of project management (PM)? I thought about task dispatching, but I'm looking for other potential uses of GAs in the context of PM.

GA is well suited to optimize a non-linear fitness function with a lot of variables. Each vector that is a possible solution is evaluated with the fitness function that we want to optimize.
So, GA is well suited to optimize schedules for a lot of people, optimizing resources, etc.
Your mission is to define all variables that you can move-tune and that affect your objectives, and assign an estimated weight on every variable.
For example, create a total project cost as the fitness function, to minimize. One variable will be the number of programmers, multiplied by cost and total months. If you don't want delays over 3 months, add a correction factor: +10000*max(0, months-3), penalizing the fitness function's results where months > 3, etc.
When you apply your GA algorithm to the fitness function, you will find some minimum for your function, if any exists, because the solution may not exist if you added too many constraints.

Project Management is most like model to game theory. You can find a article here, as a cooperative game, and apply opportunity cost to your budget, only you need to apply your own rules of the game.


How can the generalization error be estimated? How would you estimate the generalization error? What are the methods of achieving this?

Generalization error is the error obtained by applying a model to data it has not seen before. So, if you want to measure generalization error, you need to remove a subset from your data and don't train your model on it. After training, you verify your model accuracy (or other performance measures) on the subset you have removed since your model hasn't seen it before. Hence, this subset is called a test set.

Additionally, another subset can also be used for parameter selection, which we call a validation set. We can't use the training set for parameter tuning, since it does not measure generalization error, but we can't use the test set too since our parameter tuning would overfit test data. That's why we need a third subset.

Finally, in order to obtain more predictive performance measures, we can use many different train/test partitions and average the results. This is called cross-validation.

It's basically not possible to test besides some empirical experiments. All the generalization bounds only apply if your process actually follows the model assumptions which you don't actually know to be true.


If neurons are only defined for values between 0 and 1, how does ReLU differ from the identity? I'm struggling to understand the underlying mechanics of CNNs so any help is appreciated. I have a network with a ReLU activation function which does perform signifigantly better than one with sigmoid. This is expected as ReLU solves the vanishing gradient problem. However, my understanding was the reason we implement nonlinearities is to separate data which cannot be separated linearly. But if ReLU is linear for all values we care about it shouldn't work at all?

Unless, of course, neurons are defined for negative values but then my question becomes "why does ReLU solve the vanishing gradient problem at all?", since the derivative of ReLU for x<0 = 0

You are right about the fact that we use nonlinearity for classes that cant be seperated by a straight line. If you think about curves,as we know from the calculus, you can approximate a nonlinear function with lines. If you have infinite amount of lines you can mimic exactly the same function. When you increase or decrease the weight of some neuron you essentially increase or decrease the length of the line it represents. And ReLU solves the vanishing gradient problem so they are superior to sigmoid in my opinion too.


Reinforcement learning: How to deal with illegal actions? I'm a beginner of RL and currently trying to make DQN agent that can act optimally in a simple situation.

In the situation agent should decide at what rate to charge or discharge the electrical battery, which is equivalent to buying the electrical energy or selling it, for making money by means of arbitrage. So the action space is for example [-6, -4, -2, 0, 2, 4, 6]kW. The negative numbers mean discharging, and the positive numbers mean charging.

In a case that battery is empty, discharging actions(-6, -4, -2) should be forbidden.
Otherwise in a case that battery is fully charged, charging actions(2, 4, 6) should be forbidden.

To deal with this issue, I tried two approaches:

In every step, renewing the action space, which means masking the forbidden action.
Give extreme penalties for selecting forbidden actions (in my case the penalty was -9999)

But none of them worked.

For the first approach, the training curve (the cumulative rewards) didn't converge.

For the second approach, the training curve converged, but the charging/discharging results are not reasonable (almost random results).
I think in second approach, a lot of forbidden actions are selected randomly by the epsilon-greedy policy, and these samples are stored in experience memory, which negatively affect the result.

for example:

The state is defined as [p_t, e_t] where p_t is the market price for selling (discharging) the battery, and e_t is the amount of energy left in the battery.

When state = [p_t, e_t = 0], and discharging action (-6), which is forbidden action in this state, is selected, the next state is [p_t, e_t = -6]. And then the next action (2) is selected, then the next state is [p_t, e_t = -4] and so on.

In this case the < s, a, r, s' > samples  are:

< [p_t, 0], -6, -9999, [p_t+1, -6] >

< [p_t, -6], 2, -9999, [p_t+1, -4] > ...

These are not expected to be stored in the experience memory because they are not desired samples (e_t should be more than zero). I think this is why desired results didn't come out.

So what should I do? Please help.

In my project I also had the problem that the action space is not the same for every state of the environment. I do not like the approach to penalty forbidden actions with a high negative reward since it feels a bit like cheating. However it might work, I just haven't tried it.

The approach I used, which you could apply as well, is to integrate an additional function into your action space. This function would map an action to a specific amount of kW. Thereby, depending on the current state, the function maps the action to the amount of kW to charge or discharge your battery with. This has the advantage that you do not have to deal with illegal actions.

This could be applied as follows:
Instead of defining for every action the amount to charge / discharge your battery with, you create a set of functions that defines the respective amount. Here an example with five actions:

Action: Discharge the battery entirely
Action. Discharge the battery so that half of its capacity remains,
otherwise do nothing
Action: do nothing
Action: charge the batter to half its capacity, otherwise do nothing
Action: charge the battery to its maximum capacity

Reinforcement learning: How to deal with illegal actions?

It may be useful to you to consider the action space and the state space using the mathematical constructs of sets, regions, and boundary conditions.

If the variable type used for actions allows the representation of actions that are not in the action space, then the type will lead to the inefficiency of validation.  This is also true for the variable type used for states.  In the current state of the technology, this is often the case, leaving the responsibility of execution efficiency with how those variables are assigned.

Which is faster?

Assign a variable to a possibly invalid value.
Validate it.
Deal with invalid values.

... or, applying the concepts of sets, regions, and boundary conditions to the assignment mechanism, ...

Assign a variable to a value within constraints that represent the actor and its environment.

Applying this to the problem of this question, what is outside the boundary conditions?

Is it the negative current (relative to the polarity of the storage device) when the storage device's voltage is zero?
Is it a negative voltage that could potentially result from a negative current applied to a zero voltage storage device?
Is it the cost of the physical disintegration of the storage device under this condition?

These questions help illuminate whether this is a question of what is legal or forbidden or whether it is a question of return?

What is the cost of wasting electrical energy?
Wasting materials?
Wasting time?

Applying a negative current to a dead lithium, alkaline, or lead acid battery wastes all three.  The wasteful actions that lead to wasted states exist, but the curve of return on the investment of energy in resale or reuse value of the battery should not be represented by a first degree polynomial.  It should not be represented by -9999 either, as that doesn't nearly represent the degree of waste, and the knee of the curve may not be hard.

If using discrete states and actions rather than floating point representations of current and voltage, then a lookup table (perhaps tuned by experience using other AI techniques and indexed on the make and model of the storage device) must represent the actual curve approximating return on investment.  If the goal is making money, as the question suggests, the goal of the learning is to maximize ROI.
That must be embodied in your definition of optimality and then implemented to remain faithful to that definition in the DQN code.

Lastly, in real application, the initial internal resistance in combination with the initial voltage is key to determining whether a charge can ever produce a positive return for the given battery, so if voltage and current are continuously available, your test suite (which you should implement first if you are adhering to test driven development best practices) should include a case that tests the abandonment of charging altogether as a cost mitigation necessity.

The test of the algorithm regarding its fitness for the project is whether it behaves when the representations are real world.  If not, there are other AI strategies to test.  Not every algorithm is fit for every purpose, which is why job openings titled "AI Architect" and "AI Designer" are beginning to appear.  It is likely that DQN will work if the value function is either set correctly by you or learned correctly by the appropriate learning mechanism that converges on good value approximations.  The later method is suggested as best practice in this case.


What are "function terms" in the context of an ontology? I was going through the Wikipedia page on ontology components and noticed something that I had been hoping to find, for a long time. In the components' overview it mentioned:

  Function terms: complex structures formed from certain relations that can be used in place of an individual term in a statement

I tried digging deeper into function terms but couldn't find any other references. Is this a standard component of an ontology?

References would be nice. Ultimately, I'm looking for something like this in the DBPedia ontology. Would have been nice if I could add ontology and dbpedia as tags to the question, but I don't have the requisite reputation.

If you are looking for the functional verbs used in VA/VE (value analysis / value engineering) look at:

https://www.valueanalysis.ca/functionanalysis.php
http://www.brcommunity.com/articles.php?id=b679
https://www.washoeschools.net/cms/lib08/NV01912265/Centricity/Domain/253/Social%20Studies/Marker%20Verbs.pdf


What kinds of systems have so far failed to be modeled via supervised artificial network training? Artificial networks model systems with a set of inputs and outputs and expected behavior. To train a network for modeling such systems, hundreds, thousands, or millions of example inputs-output pairs may be required. This is called a labelled data set, and the network and its optimization algorithm are meant to find a set of network parameters that best match the I/O of the artificial network with the I/O of the system.

Are there any systems, for which sufficient labelled data sets exist, that have yet to be successfully modeled with artificial networks of any type (recurrent, deep, convolution, etc)?

I haven't seen any dataset where some standard models worked and neural networks utterly failed.

For columnar data (e.g. Excel files / database dumps / CSV files) which contain structured data usually tree-based models like random forests and gradient boosting work better, but neural networks are also usually way better than random.

If you demand other things, e.g. explanations for the decision then Bayesian models might give you an easier time. Or for baselines/simple implementations linear models. Or for real time applications...

I still havent seen a good program for recommending me good movies, songs and books based on my previous lkes. Youtube recommendation system is shit. Since youtube is owned by google and since youtube has most content and since google is investing in AI a lot I would conclude this problem remains largely unsolved.


What is the best programming language to learn to implement genetic algorithms? What is the best and easiest programming language to learn to implement genetic algorithms? C++ or Python, or any other?

There is no "best language" for any problem. There are too many variables to consider, even when advising a single person with a single project plan.

If the choice is between Python and C++, I would generally advise:

If you want to implement from scratch and learn how the algorithm works, use Python with numeric/accelerated libraries such as NumPy or PyTorch. Python script is quicker to prototype and try different ideas, due to loose variable typing and built-in high-level structures such as dict and list.
If you want to write core, efficient libraries, then C++ will out-perform Python, but writing these will take longer. There are plenty of C++ libraries available (e.g. TensorFlow is available with a C++ API), but the community around them is less focused than with Python toolkits.

You can also combine both approaches and write specific libraries in C or C++ to improve performance at any time.

With Genetic Algorithms, the speed bottleneck is most often population assessment - e.g. running the environment simulation to get a fitness measure for each individual - and not the GA itself. So if you have a specific problem or problem domain in mind, may want to orient your choice around a language that already has support for the kind of environments where you want to run your GA. GAs usually benefit greatly from parallelisation, so if you are aiming for something ambitious you will want to look into GPU support and/or distributed computing toolkits.

Most researchers/hobbyists working in AI-related fields end up using multiple languages over time. You may end up with a favourite language environment, which might be Python, Julia, Java, C++, C, C#, Lua, LISP, Prolog, Matlab/Octave, R . . . but you will end up needing a smattering of other languages, and usually skills with specific toolkits such as TensorFlow, Scikit-Learn, Hadoop etc in order to complete projects.

Don't be afraid that you will "waste time" learning in one language initially then needing to transfer to another. Your learning of algorithms will be transferable, and your first attempts will most likely not be that re-usable as library code anyway, so you are going to re-implement your ideas, perhaps many times. My first simulated annealing project was written in Fortran 77 . . . 20 years later I dug that knowledge up again and implemented in Ruby/C - nowadays I work in Python for the AI/hobby stuff even though my professional career sees me working mostly in Ruby.

Matlab may be a good option to get started with the implementation of genetic algorithms, given that there a lot of pre-defined functions.

See e.g. https://www.mathworks.com/discovery/genetic-algorithm.html and https://www.mathworks.com/help/gads/examples/coding-and-minimizing-a-fitness-function-using-the-genetic-algorithm.html.


Understanding the "unroling" step in the proof of the policy gradient theorem In the proof of the policy gradient theorem in the RL book of Sutton and Barto (that I shamelessly paste here):

there is the "unrolling" step that is supposed to be immediately clear

With just elementary calculus and re-arranging of terms

Well, it's not. :) Can someone explain this step in more detail?
How exactly is $Pr(s \rightarrow x, k, \pi)$ deduced by "unrolling"?

The unrolling step is due to the fact you end up with an equation that you can keep expanding indefinitely.
Note that we start with calculating $\nabla v_\pi(s)$ and arrive at
$$\nabla v_\pi(s) = \sum_a\left[ \nabla \pi(a|s) q_\pi(s,a) + \pi(a|s) \sum_{s'}p(s'|s,a) \nabla v_\pi (s') \right]\;,$$
which contains a term for $\nabla v_\pi(s')$. This is a recursive relationship, similar to the bellman equation, so we can substitute in a term for $\nabla v_\pi(s')$ which will be a term similar just with $\nabla v_\pi(s'')$. As I mentioned, we can do this indefinitely which leads us to
$$\nabla v_\pi(s) = \sum_{x \in \mathcal{S}} \sum_{k=0}^\infty \mathbb{P}(s\rightarrow x, k, \pi) \sum_a \nabla \pi(a|x) q_\pi(x,a)\;.$$
We need the term $\sum_{x \in \mathcal{S}} \sum_{k=0}^\infty \mathbb{P}(s\rightarrow x, k, \pi)$ because we want to take an average over the state space, however due to unrolling there are many different $s_t$'s that we need to average over (this comes from the $s',s'',s''',...$ in the unrolling) so we also need to add the probability state of transitioning from state $s$ to $x$ in $k$ time steps, where we sum over an infinite horizon due to the repeated unrolling.
If you are wondering what happens to the terms $\pi(a|s)$ and $p(s'|s,a)$ terms and why they are not explicitly shown in this final form, it is because this is exactly what the $\mathbb{P}(s\rightarrow x, k, \pi)$ represents. The average over all possible states accounts for the $p(s'|s,a)$ and the fact that we follow policy $\pi$ in the probability statement accounts for the $\pi(a|s)$.

It looks like "v of s prime" is just substituted with the already derived value for "v of s". You can call it a recursion of a kind.
In other words, v(s) is dependent on v(s') and that implies that v(s') is dependent on v(s''). So we can combine that and get the dependency of v(s) of v(s'').


How do we test if an model or algorithm is AI-complete? How do we test if a 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.

One cannot judge any form of intelligence, artificial or natural, whether it is complete or incomplete. Having it complete means that you are imposing limits to what it is capable of, the Turing test only test if your machine have intelligence that is similar to humans, therefore to decide whether it is complete or not would have to be based on the completeness of our own intelligence. Humans such as ourselves learn new things each day. If you'd run any algorithm that would judge the AI for it's completeness, it would have to run forever and your results would have to vary on every moment of the existence of natural intelligence.